Поскольку единственными операциями, необходимыми для контейнера, используемого в стеке, являются:
- назад ()
- push_back ()
- pop_back ()
Почему контейнер по умолчанию для него является декой, а не вектором?
Не переделывают ли deque перераспределения буфер элементов перед front (), чтобы push_front () была эффективной операцией? Не потрачены ли эти элементы впустую, поскольку они никогда не будут использоваться в контексте стека?
Если для использования этого способа вместо вектора нет накладных расходов, то почему вектор по умолчанию для priority_queue также не является deque? (priority_queue требует front (), push_back () и pop_back () - по сути, то же самое, что и для стека)
Обновлено на основе ответов ниже:
Кажется, что способ, которым обычно реализуется deque, - это массив переменных размеров массивов фиксированного размера. Это ускоряет рост по сравнению с вектором (который требует перераспределения и копирования), поэтому для чего-то вроде стека, который состоит из добавления и удаления элементов, deque, вероятно, является лучшим выбором.
priority_queue требует интенсивной индексации, поскольку при каждом удалении и вставке необходимо запускать pop_heap () или push_heap (). Это, вероятно, делает вектор лучшим выбором, поскольку добавление элемента все равно амортизируется константой.