Почему std :: stack по умолчанию использует std :: deque?

91

Поскольку для использования контейнера в стеке требуются только следующие операции:

  • назад ()
  • отталкивать()
  • pop_back ()

Почему контейнер по умолчанию для него - двухсторонняя очередь, а не вектор?

Разве перераспределение deque не дает буфер элементов перед front (), чтобы push_front () была эффективной операцией? Разве эти элементы не потрачены впустую, поскольку они никогда не будут использоваться в контексте стека?

Если нет накладных расходов на использование двухсторонней очереди таким образом вместо вектора, почему по умолчанию для priority_queue вектор, а не двухсторонняя очередь? (priority_queue требует front (), push_back () и pop_back () - по сути, то же, что и для стека)

Обновлено на основе ответов ниже:

Похоже, что способ, которым deque обычно реализуется, представляет собой массив переменного размера массивов фиксированного размера. Это делает рост быстрее, чем вектор (что требует перераспределения и копирования), поэтому для чего-то вроде стека, который предназначен для добавления и удаления элементов, deque, вероятно, будет лучшим выбором.

priority_queue сильно требует индексации, так как каждое удаление и вставка требует, чтобы вы запускали pop_heap () или push_heap (). Это, вероятно, делает вектор лучшим выбором, поскольку добавление элемента все равно амортизируется константой.

c++ stl containers Грег Роджерс
источник
1
Рассуждения в вашем «обновлении» не совсем правильные. вектор обычно добавляет и удаляет элементы с конца быстрее, чем двухсторонняя очередь. deque быстрее увеличивает память , а не выталкивает элементы.
Mooing Duck,

Ответы:

75

По мере роста контейнера перераспределение вектора требует копирования всех элементов в новый блок памяти. При увеличении двухсторонней очереди выделяется новый блок и он связывается со списком блоков - копий не требуется.

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

Майкл Берр
источник
1
Но когда список указателей на блоки растет, этот список должен иногда перераспределяться, как и вектор; асимптотически любой выигрыш в эффективности в лучшем случае является постоянным фактором. А манипуляции с итератором, необходимые для правильного выполнения push и pop, намного сложнее, std::dequeчем для std::vector, и эти операции, вероятно, будут использоваться гораздо чаще, чем перераспределения. Мне трудно поверить, что std::dequeэто когда-либо победит std::vectorна практике.
Marc van Leeuwen
@ Майкл Берр: Тогда почему бы не использовать list, почему deque?
bappak
@MarcvanLeeuwen относительно того, что вы говорите, что вам трудно поверить ... не могли бы вы высказать ясную точку зрения? Вы имеете в виду, что теперь верите, std::dequeчто у вас есть шанс побить std::vectorна практике, или вы все еще сомневаетесь в этом? Спасибо.
aafulei
@fleix Я не понимаю, почему это так важно, легче ли мне поверить, что это std::dequeбудет работать так же хорошо, как и std::vectorв практических приложениях. Но как бы то ни было, по моему личному опыту, мне нужны структуры данных стека и очереди не для одной большой и важной задачи, а для множества мелких случаев, пропитанных моим кодом. Поэтому меня больше волнует поведение в малом, чем в большом; и deque там светит особенно тускло. Я предпочитаю использовать ни один из них, а (самореализованные) односвязные списки. Но ваш пробег может отличаться.
Марк ван Леувен
12

См. « Гуру недели 54» Херба Саттера, чтобы узнать об относительных достоинствах векторов и двухсторонней очереди, где подойдет любой из них.

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

Джеймс Хопкин
источник
2
priority_queue фактически не использует push / pop_front, а ссылки на элементы, кроме первого, аннулируются операциями с кучей. Таким образом, ни одно из преимуществ deque не применимо, в отличие от обычной очереди.
Potatoswatter
9
Кроме того, они priority_queueдолжны оставаться отсортированными, поэтому более высокие накладные расходы на произвольный доступ deque::iteratorболее проблематичны.
Potatoswatter
1
@Potatoswatter: priority_queueесть "магический порядок", который поддерживается, он не сортируется. Однако ваша точка зрения остается неизменной.
Mooing Duck,