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

Question

据我所知,deque背后的动机是提供一个有效的随机访问容器push_front.

与deque相比,vector的常见优点包括更快的遍历at(),但主要是它的C兼容性,因为它保证了连续的内存.Deque没有,因为它是一大堆内存,每个都包含许多值.

我糊涂了.0除了索引之后保留的内存之外,为什么deque不是像向量一样构建,而是在索引之前保留内存size-1？这将保证连续内存,启用高效push_front,甚至在解除引用迭代器时避免额外的间接.

为了最小化插入期间的移位,要移位的包含值将取决于插入点.如果在索引n之前插入,则将size()/2值n向左移动.否则后移右值n.

我错过了什么是非常重要的,deque是一组价值数组而不是一个大数组？

Answer 1

根据维基百科,你所描述的确实是一种可能的实现,至少在一般情况下.

但是,C++标准强制要求基本上禁止将其作为实现std::deque; [deque.modifiers]指出:

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

(感谢@BenjaminLindley!)