当向量可以解决问题时，为什么默认情况下使用双端队列作为堆栈的底层容器？

Question

据我了解，任何支持push_back()、pop_back()和back()的容器都可以用作堆栈的底层容器，但默认情况下使用双端队列。我通常理解双端队列相对于向量的优点（可以在开头和结尾添加元素），但就堆栈而言，我看不出有任何理由更喜欢双端队列。

Answer 1

我看不出有什么理由更喜欢双端队列。

更喜欢适用于堆栈用例的双端队列的一个原因是，与矢量相比，单个推回具有最坏情况下的恒定复杂性，矢量的单个推回在最坏情况下是线性的（它在多个推回上摊销了恒定复杂性）。这在 C++11 之前尤其重要，因为重新分配向量必须复制元素，这可能非常昂贵。考虑元素本身是长字符串的情况。

更喜欢双端队列的另一个原因是它们在收缩时释放内存。向量则不然。因此，如果您的堆栈暂时变大，然后缩小并在其余执行过程中保持较小状态，那么底层向量将浪费大量内存。

从历史上看，当设计 STL 并因此选择默认值时，曾经也存在非常大的向量的问题，因为地址空间的大小没有（显着或根本）超过内存量（这是之前的情况） 64 位处理很常见）。有限地址空间的后果是，内存碎片会使分配大向量所需的大连续内存块变得昂贵或不可能。此外，向量通过释放旧缓冲区来增长的方式是导致此类碎片的行为。