c++ - std::deque 实际上在开始时有恒定时间插入吗？

Question

标准说:

A deque is a sequence container that supports random access iterators (27.2.7). In addition, it supports constant time insert and erase operations at the beginning or the end; insert and erase in the middle take linear time.

然而，它也在同一个条款中说:

All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [ Example: The copy constructor of type vector<vector<int>> has linear complexity, even though the complexity of copying each contained vector<int> is itself linear. — end example ]

这是否意味着在 deque<int> 开头的插入被允许花费线性时间，只要它不会对已经在双端队列中的 int 和新的 int 执行超过恒定数量的操作对象被插入？

例如，假设我们使用“大小为 K 个 vector 的 vector ”来实现双端队列。似乎我们在开头每插入 K 次，就必须在开头添加一个新的大小为 K 的 vector ，因此必须移动所有其他大小为 K 的 vector 。这意味着开始时插入的时间复杂度分摊为 O(N/K)，其中 N 是元素总数，但 K 是常数，所以这只是 O(N)。但似乎这是标准允许的，因为移动大小为 K 的 vector 不会移动它的任何元素，并且“复杂性要求”是“仅根据操作数量来说明”对包含的 int 对象.

标准真的允许这样做吗？或者我们应该将其解释为具有更严格的要求，即对所包含对象的恒定操作次数加上恒定的额外时间？

Answer 1

For example, suppose that we implement a deque using a "vector of size-K vectors".

那不会是一个有效的实现。在 vector 前面插入使容器中的所有指针/引用无效。 deque要求在前插入时不使任何指针/引用无效。

但让我们暂时忽略它。

But it seems that this is allowed by the Standard, because moving a size-K vector doesn't move any of its elements, and the "complexity requirements" are "stated solely in terms of the number of operations" on the contained int objects.

是的，那是允许的。确实， deque 的真实实现与那并没有太大不同(尽管出于明显的原因，他们不使用 std::vector 本身)。 deque的大纲实现是一个指向块的指针数组(前后都有增长空间)，每个块包含最多 X 个项目以及指向下一个/上一个块的指针(使单元素迭代更快)。

如果在前面或后面插入足够多的元素，则块指针数组必须增长。这将需要一个相对于 deque 中的项目数量呈线性时间的操作。 ，但实际上并不对项目本身进行操作，因此它不算数。该规范没有说明该操作的复杂性。

如果没有此规定，我不确定 deque 的独特功能集是否存在。 (快速前/后插入和随机访问)将是可以实现的。