栈和队列的C++默认实现

Question

在C++ Primer 5th中，它说stack和queue的默认实现是deque。

我想知道为什么他们不使用 list？ Stack和Queue不支持随机访问，总是在两端操作，因此list应该是最直观的实现方式，而deque支持随机访问(具有恒定时间)在某种程度上是不必要的。

谁能解释一下这个实现背后的原因？

Answer 1

与 std::list作为基础容器每个 std::stack::push进行内存分配。鉴于 std::deque以 block 的形式分配内存，并可以重用其空闲容量以避免内存分配。

对于小元素，列表节点的存储开销也会变得很大。例如。 std::list<int>节点大小为 24 字节(在 64 位系统上)，元素仅占用 4 字节 - 至少 83% 的存储开销。