Насколько я понимаю, любой контейнер, который поддерживает push_back(), pop_back() и back(), может использоваться в качестве базового контейнера для стеков, но по умолчанию используются деки. Я понимаю преимущества деков перед векторами в целом (возможность добавлять элементы как в начало, так и в конец), но в случае стеков я не вижу причин предпочитать деки.
Таким образом, векторы имеют (в случае стеков) нерелевантное преимущество непрерывной памяти, в то время как деки имеют (в случае стеков) нерелевантное преимущество поддержки push_front(). И непрерывная память просто казалась БОЛЕЕ неактуальной (более дорогой?), чем поддержка push_front()? Я правильно тебя понимаю?
деки очень хорошо умеют толкать и выталкивать в конце. векторы не плохи в этом, но не настолько.
Действительно? Почему деки лучше пушат и выталкивают в конце?
подробно в ответе
I don't see any reason to prefer deques.
Причина предпочтения deque, применимого к варианту использования стека, заключается в том, что отдельная обратная передача имеет постоянную сложность в наихудшем случае по сравнению с вектором, индивидуальная обратная передача которого в наихудшем случае является линейной (он амортизирует постоянную сложность в течение нескольких обратных перемещений). Это было особенно важно до C++11, когда при перераспределении вектора приходилось копировать элементы, что могло быть очень дорого. Рассмотрим случай, когда сами элементы представляют собой длинные строки.
Еще одна причина предпочесть двухсторонние очереди состоит в том, что они освобождают память при уменьшении. Векторов нет. Следовательно, если у вас есть стек, который временно увеличивается, а затем сжимается и остается маленьким до конца выполнения, то базовый вектор будет тратить много памяти.
Исторически сложилось так, что при разработке STL и, следовательно, при выборе значения по умолчанию также возникали проблемы с очень большими векторами, поскольку размер адресного пространства не превышал (значительно или совсем) объем памяти (это было до 64-битная обработка была обычным явлением). Следствием ограниченного адресного пространства было то, что фрагментация памяти делала дорогостоящим или невозможным выделение больших смежных блоков памяти, которые потребовались бы для большого вектора. Более того, то, как этот вектор растет за счет освобождения старых буферов, является поведением, вызывающим такую фрагментацию.
сформулировать это провокационно: какое вам дело до того, что в стеке есть элементы в непрерывной памяти, если в любом случае вы можете получить доступ только к одному из них в любой момент?