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

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

назад()
push_back()
pop_back()

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

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

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

Обновлено на основе нижеприведенных ответов:

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

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

Ответ 1

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

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

Ответ 2

См. Herb Sutter Guru of the Week 54 относительно относительных достоинств vector и deque, где бы это ни было.

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