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