当向量可以解决问题时，为什么默认情况下使用双端队列作为堆栈的底层容器？
据我了解，任何支持push_back()、pop_back()和back()的容器都可以用作堆栈的底层容器，但默认情况下使用双端队列。我通常理解双端队列相对于向量的优点（可以在开头和结尾添加元素），但就堆栈而言，我看不出有任何理由更喜欢双端队列。
As I understand, any container that supports push_back(), pop_back() and back() can be used as the underlying container for stacks, but by default, deques are used. I understand the pros of deques over vectors generally (possibility to add elements at the beginning as well as at the end), but in the case of stacks, I don't see any reason to prefer deques.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
更喜欢适用于堆栈用例的双端队列的一个原因是，与矢量相比，单个推回具有最坏情况下的恒定复杂性，矢量的单个推回在最坏情况下是线性的（它在多个推回上摊销了恒定复杂性）。这在 C++11 之前尤其重要，因为重新分配向量必须复制元素，这可能非常昂贵。考虑元素本身是长字符串的情况。
更喜欢双端队列的另一个原因是它们在收缩时释放内存。向量则不然。因此，如果您的堆栈暂时变大，然后缩小并在其余执行过程中保持较小状态，那么底层向量将浪费大量内存。
从历史上看，当设计 STL 并因此选择默认值时，曾经也存在非常大的向量的问题，因为地址空间的大小没有（显着或根本）超过内存量（这是之前的情况） 64 位处理很常见）。有限地址空间的后果是，内存碎片会使分配大向量所需的大连续内存块变得昂贵或不可能。此外，向量通过释放旧缓冲区来增长的方式是导致此类碎片的行为。
A reason to prefer deque that applies to the stack use case is that individual push back has worst case constant complexity compared to vector whose individual push back is linear in worst case (it has amortised constant complexity over multiple push backs). This was particularly significant prior to C++11 when reallocating vector had to copy the elements which could be very expensive. Consider case where the elements themselves are long strings.
Another reason to prefer deques is that they release memory as they shrink. Vectors don't. Hence, if you have a stack that temporarily grows large, then shrinks and remains small for the rest of the execution, then an underlying vector would be wasting a lot of memory.
Historically, when STL was designed and thus when the default was chosen, there used to also be issues with very large vectors because the size of the address space didn't exceed (significantly, or at all) the amount of memory (this was before 64 bit processing was common). The consequence of the limited address space was that memory fragmentation would make it expensive or impossible to allocate large contiguous blocks of memory that a large vector would require. Furthermore, the way that vector grows by deallocating old buffers is a behaviour that causes such fragmentation.