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

据我所知，deque背后的动机是提供一个高效的随机存取容器push_front。为什么std :: deque不是在索引0之前保留内存的向量？

相比双端队列矢量的通常引用的优点包括更快的遍历和at()，但主要是其C兼容性，因为它保证连续存储器。 Deque没有，因为它是一个内存块的集合，每个都拥有许多值。

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

为了最大限度地减少插入期间移位，被移位的包含的值将取决于插入点。如果在位于size()/2之前的索引n处插入，则将偏移值最大为n。否则，将n后的值正确移位。

我错过了什么是非常重要的，双端队列为值数组的集合，而不是一个大阵？

2013-02-10 Gabriel

按摊余成本，也许？快速'push_front'不是'deque'唯一的要求' – 2013-02-10 00:05:37

你会保留多少内存？ 1KB，10KB，1M，1GB，24GB？不管你做什么，有人会抱怨它的太多或不够...... – 2013-02-10 00:07:47

据我所知这是Qt的实现了它的QList – BeniBela 2013-02-10 00:10:48

According to Wikipedia，什么你所描述的确实是一个可能的实现，至少在一般。

然而，C++标准强加的要求，基本上禁止以此作为std::deque的实现; [deque.modifiers]指出：

在deque的两端插入...对引用deque元素的有效性没有影响。

（感谢@BenjaminLindley！）

2013-02-10 00:09:37

我STFW的答案，但维基百科通常不会想到这样的话题（： – Gabriel 2013-02-10 00:11:20

23.3.3.4/1和/ 4说，插入或删除在deque的末尾不应使参考无效，那不会使'如果deque是这样工作的（我之前说过迭代器，但它只是引用） – 2013-02-10 00:17:38

因此，依赖与realloc相邻的内存的实现不符合标准吗？我猜其他实现可以提供与c_array的C兼容性函数，就像'string :: c_str'一样，它会重新包装一个大块中的所有块，并被插入无效化。 – Gabriel 2013-02-10 13:20:52

回答