Comments 14
Для создания и уничтожения объектов std::vector использует конструкторы и деструкторы, а они в некоторых случаях могут быть значительно медленнее, чем memcpy().
Если конструкторы и деструкторы "значительно медленнее, чем memcpy()" — это верный признак того, что memcpy() там использовать не получится/нельзя.
Вообще, интересный обзорный пост, только я бы не советовал его считать истиной в последней инстанции в 2019 году.
В своё время, для минимизации времени на аллокации при работе с аудио данными в реальном времени, использовал очереди, и дёргал буферы оттуда:
queue<audio_buffer<float>> in_, out_, free_;внутри audio_buffer всё тот же std::vector, и даже если стоял фильтр на выход с другим рэйтом, то change capacity происходил два раза: первый при создании аудио-буфера под размер входящих данных(если в очереди свободных не оказывалось ни одного), и второй (И ТО если на выходе имеем бОльший рэйт) уже непосредственно перед ресэмплингом.
И всё нормально работало (после обработки сигнал подавался на аудио выход): без лагов и тормозов, с ресэмплингом и наложением нескольких фильтров.
Если руки растут откуда надо, можно и на векторах запрогить не хуже bulk-data way storage, конечно будет некоторый оверхэд по RAM, но отпадает необходимость ручками выделять/освобождать/ресайзить.
PS: AVL-ки по сравнению с RBtree имеют худшую производительность на вставках/удалении элементов. Префиксные деревья для строковых ключей хороши.
Для этого понятия не существует распространённого термина (или я о нём не знаю). Я называю «общим массивом данных» (bulk data) любую большую коллекцию похожих объектов
Дак это же обычный односвязный список.
Но на практике мне ни разу не пригождались АВЛ-деревья, красно-чёрные деревья, префиксные деревья, списки с пропусками, и т.д.
Либо человек делает что-то весьма специфическое, либо он чего-то не знает. В той же Java например TreeMap и TreeSet это красно-черное дерево. Да, не самая часто используемая структура данных, но мне ей приходилось достаточно регулярно пользоваться.
Возможно конечно имеется ввиду дерево написанное самим. Тогда соглашусь.
Еще они будут неплохи в случае, если по какой-то причине нельзя гарантировать хорошую хэш функцию, так как в этом случае хэш таблица может деградировать до O(N), а дерево будет lg(N)
А что имеется в виду под «нельзя гарантировать хорошую хэш-функцию»?
Время на генерацию хэша для значения ключа и вставки ноды (unordered structure storage — hash based), превышают, или даже равно времени вставки ноды для ordered structure storage.
UPD: Ну или это связано с коллизиями хэша...
Про хэш ответили выше. Либо ключи такие, что много коллизий, либо хэш считать долго. Но это еще более редкий случай, сам вживую не сталкивался.
Union-find: определение пересекаемости множеств. Есть ли у нас общие друзья на фейсбуке?
Binary space partition: быстрый поиск ближайшего объекта на карте.
Правда, это все из разряда поиграться и забить.
Структуры данных для программистов игр: bulk data