N2
Size: a a a
2020 July 22
🎄T
думаю комп зависнет если попытаться создать огромный массив вершин в отсортированном виде с o(n) вставкой
Ну если вставки происходят чаще чтение, то да
🎄T
std::deque не нужно шифтить, но он должен быть намного более кэш-френдли, чем std::set
std::pmr мб можно пофиксить
🎄T
В плане кэша
VS
прямо-таки линейная от всех N элементов? или от размера блока (константы)? Он же должен быть блочный
Constant plus linear in the lesser of the distances between pos and either of the ends of the container.
О
Вставка в середину все равно линейная.
Там же вроде чанками хранится?
CD
прямо-таки линейная от всех N элементов? или от размера блока (константы)? Он же должен быть блочный
Линейная, потому что размеры блоков посередине не могут быть разные
CD
По моим представлениям размер блока в деке фиксированный. И когда-то я смотрел имплементацию, где это точно было так. Но технически, кажется, это не противоречит стандарту.
Вы не сможете реализовать доступ по индексу за константу, если размеры блоков различны
О
Подскажите контейнер, у которого можно по индексу элемент брать и вставлять в середину быстро(относительно вектора с реалокацией) (кроме дека)
🎄T
Вы не сможете реализовать доступ по индексу за константу, если размеры блоков различны
А если одинаковые, то как за константу доступ получить?