Вопрос по stl, c++, containers – Почему std :: stack использует std :: deque по умолчанию?

79

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

back() push_back() pop_back()

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

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

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

Updated based on the Answers below:

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

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

Обоснование в вашем "обновлении" не совсем верно. вектор обычно добавляет и удаляет элементы с концаfaster чем deque. Deque быстрее дляgrowing memory, не толкая элементы. Mooing Duck

Ваш Ответ

2   ответа
70

ания всех элементов в новый блок памяти. Растущая ветвь выделяет новый блок и связывает его со списком блоков - копии не требуются.

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

@ Майкл Берр: Тогда почему бы не использоватьlist, Зачемdeque?
@MarcvanLeeuwen в отношении вас говорят, что вам трудно поверить ... не могли бы вы сделать четкую точку зрения? ты имеешь в виду, что ты сейчас веришьstd::deque есть шанс победитьstd::vector на практике, или ты имеешь в виду, что все еще сомневаешься в этом? Благодарю.
@fleix Я не понимаю, почему так важно, чтобы лично мне было легче поверить, чтоstd::deque будет делать так же, какstd::vector в практических приложениях. Но, как бы то ни было, мой личный опыт заключается в том, что мне нужны структуры данных стека и очереди не для одной большой и сложной для решения задачи, а для многих мелких случаев, разбросанных по моему коду. Таким образом, меня больше заботит поведение в малом, чем в целом; и блеск там особенно тусклый. Я предпочитаю использовать ни один, а (самостоятельно реализованные) односвязные списки. Но у вас пробег может отличаться.
Но когда список указателей на блоки увеличивается, этот список должен иногда перераспределяться так же, как и вектор; асимптотически любое повышение эффективности является в лучшем случае постоянным фактором. И манипуляции с итераторами, необходимые для правильного нажатия и выталкивания, намного сложнееstd::deque чем это дляstd::vectorи эти операции, вероятно, будут использоваться гораздо чаще, чем перераспределения. Мне трудно поверить, чтоstd::deque будет битьstd::vector на практике.
12

Гуру Недели 54 для относительных достоинств вектора и deque, где любой сделал бы.

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

@Potatoswatter:priority_queue имеет «магический порядок» это поддерживается, это не отсортировано. Тем не менее, ваша точка зрения остается в силе.
Также,priority_queue должен оставаться отсортированным, поэтому более высокие издержки случайного доступаdeque::iterator более проблематично.
priority_queue фактически не использует push / pop_front, и ссылки на элементы, кроме первого, становятся недействительными операциями кучи. Таким образом, ни одно из преимуществ deque не будет применяться, в отличие от случая с обычной очередью.

Похожие вопросы