c++ - STL 实现中是否有中心分配双端队列或 vector ？

Question

我正在阅读 deque s 与 vector s，并遇到了它的 wikipedia entry ，表示 deque 的三种可能实现之一。使用动态数组是:

Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.

我想知道是否有任何实际使用这种中心分配策略的 STL(或 STL 风格)实现？

我问是因为这个策略看起来相当吸引人，因为它只涉及一个底层数组，因此消除了内存不连续问题，这可能是唯一的主要问题 deque与vector相比有.如果我理解正确的话，这很可能是 std::vector 的替代品。允许 O(1) pop_front (摊销)或替换 deque具有内存连续性保证。我假设这是以将 std::vector 的缓冲空间加倍为代价的，这不是我的用例的主要问题。

此外，在这样的容器中间插入/删除是否真的需要 std::vector 的一半时间？平均？

---

更新:

正如@Lightness Races in Orbit 指出的那样，在当前标准下不会使用这样的实现，因为没有人可以从每份与 STL 的契约(Contract)中获益，而每个人都会遭受不利影响。关于缺点，我还有一个问题是:

是否有可能实现新 vector或 deque像容器(比如 bivector )这样除了 std::vector 的功能/操作符之外,

1) 提供(摊销)常数时间 push_front()和 pop_front()操作和

2) 保证内存连续性但在增长大小后不保证迭代器有效性？

我想象在幕后有一个数组，deque 上有很多间接/性能问题会消失。

Answer 1

没有标准库(不是“STL”)实现会为此烦恼，因为它有您提到的缺点，而优点不是 std::deque 要求的一部分。

这些要求是经过精心构建的，从各种操作的算法复杂性到迭代器失效规则。以没有人可以依赖该实现的优势的方式实现容器没有任何好处。

C++ 委员会能否在未来的标准中引入一个具有不同名称和不同约束的新容器，哪些供应商可以按照您的描述实现？是的，他们可以。