Самый быстрый контейнер очереди (C ++)

Question

Я использую очереди и очереди с приоритетами, через которые я планирую перекачивать много данных довольно быстро.

Поэтому я хочу, чтобы мои q и pq реагировали на сложения и вычитания.

Каковы относительные преимущества использования вектора, списка или deque в качестве базового контейнера?

Обновление: На момент написания ответов Майк Сэймур и Стив Таунсенд нижестоит читать.Спасибо обоим!

Answer 1

Единственный способ убедиться, как выбор влияет на производительность, - это измерить ее в ситуации, аналогичной ожидаемым сценариям использования.Тем не менее, вот некоторые наблюдения:

Для std::queue:

• std::deque обычно является лучшим выбором;он поддерживает все необходимые операции в постоянное время и распределяет память по частям по мере роста.
• std::list также поддерживает необходимые операции, но может быть медленнее из-за увеличения выделения памяти;в особых случаях вы можете получить хорошие результаты, выделяя из выделенного пула объектов, но это не совсем просто.
• std::vector нельзя использовать, так как у него нет pop_front()операция;такая операция будет медленной, так как она должна будет переместить все оставшиеся элементы.

Потенциально более быстрая, но менее гибкая альтернатива состоит в реализации циклического буфера в массиве фиксированного размера (например,std::array, или std::vector, размер которого вы не изменили).Вам нужно разобраться со случаем его заполнения, либо сообщив об ошибке, либо выделив больший буфер и скопировав все данные.

Для std::priority_queue:

• std::vector обычно лучший выбор;он растет в геометрической прогрессии (сокращая количество распределений памяти) и представляет собой простую структуру данных, к которой очень быстро получить доступ - итератор может быть реализован просто как оболочка вокруг указателя.
• std::deque может быть медленнее, чемобычно он растет линейно (требует большего выделения памяти), и доступ к нему более сложный, чем с вектором.
• std::list нельзя использовать, поскольку он не обеспечивает произвольный доступ.

Подводя итог - по умолчанию, как правило, лучший выбор, но если скорость действительно важна, то измерьте альтернативы.

Answer 2

Я бы использовал std::queue для вашей основной очереди, которая (по крайней мере по умолчанию) является оберткой для deque. Сделайте что-то более специальное, если это не работает для вас.

std::priority_queue также существует (более vector по умолчанию), но добавленная семантика повышает вероятность того, что вам, возможно, придется кататься здесь самостоятельно, в зависимости от производительности, наблюдаемой для вашего конкретного шаблона доступа.

vector имеет характеристики хранения, которые делают его очень плохо приспособленным для удаления из передней части набора данных. Каждый раз, когда вы делаете pop_front, вам нужно будет сделать много перетасовок. Для простой очереди избегайте этого.

list, вероятно, будет слишком дорогим для любой очереди с большим количеством запросов, потому что по контракту она должна предлагать функцию, которая вам не нужна. Это может быть кандидат для использования в качестве приоритетной очереди, но мой инстинкт всегда заключается в доверии STL.

Answer 3

vector будет реализован стек, так как ваша быстрая вставка в конце и быстрое удаление также в конце. Если вы хотите очередь FIFO, vector будет неправильной реализацией для использования.

deque или list оба обеспечивают постоянное время вставки на любом конце. list подходит для кэшей LRU, где вы хотите быстро переместить элементы из середины и где вы хотите, чтобы ваши итераторы оставались в силе независимо от того, сколько вы их перемещаете. deque обычно используется, когда вставки и удаления находятся в конце.

Главное, что мне нужно спросить о вашей коллекции, это доступ к ней через несколько потоков. Я полагаю, что так оно и есть, и в этом случае одной из ваших основных целей является уменьшение блокировки. Лучше всего это сделать, если у вас есть хотя бы функция multi_push и multi_get, так что вы можете включить более одного элемента одновременно без какой-либо блокировки.

Существуют также контейнеры без блокировки или контейнеры без блокировки.

Вы, вероятно, обнаружите, что ваша стратегия блокировки важнее, чем любая производительность в самой коллекции, если все операции выполняются в постоянном времени.