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

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

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 (). Это, вероятно, делает вектор лучшим выбором, поскольку добавление элемента все равно амортизируется константой.

Ответы на вопрос(2)

Ваш ответ на вопрос