c++ - 为什么 std::deque 不是在索引 0 之前保留内存的向量？

Question

据我了解，deque 背后的动机是提供一个高效的随机访问容器push_front。

与 deque 相比，vector 的普遍优势包括更快的遍历和at()，但主要是它的 C 兼容性，因为它保证了连续的内存。双端队列没有，因为它是内存块的集合，每个内存块都包含多个值。

我很困惑。为什么 deque 不像向量那样构建，但是0除了在 index 之后保留的内存之外，还保留了在 index 之前的内存size-1？这将保证连续的内存，提高效率push_front，甚至在取消引用迭代器时避免额外的间接。

为了在插入过程中最小化移位，要移位的包含值将取决于插入点。如果在索引n之前插入，则将size()/2值向上移动n。否则右移 之后的值n。

我错过了什么是如此重要，以至于 deque 是值数组的集合而不是一个大数组？

Answer 1

根据 Wikipedia，您所描述的确实是一种可能的实现，至少在一般情况下是这样。

但是，C++ 标准强加了一些要求，基本上禁止将其作为 ; 的实现std::deque。[deque.modifiers] 状态：

在双端队列的任一端插入 ... 对双端队列元素引用的有效性没有影响。

（感谢@BenjaminLindley！）