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

Question

标准说：

双端队列是支持随机访问迭代器（27.2.7）的序列容器。此外，它支持在开头或结尾的恒定时间插入和擦除操作；在中间插入和擦除需要线性时间。

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

本条款中的所有复杂性要求仅根据对所包含对象的操作数量进行说明。[ 示例： type 的复制构造函数vector<vector<int>>具有线性复杂性，即使复制每个包含的复杂性vector<int>本身也是线性的。— 结束示例 ]

不这是否意味着在插入的，刚开始说，deque<int>被允许采取线性时间，只要不超过固定数量的执行更多操作上的int那些已经在双端队列和新的Sint对象插入?

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

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

Answer 1

例如，假设我们使用“大小为 K 个向量的向量”来实现双端队列。

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

但现在我们先忽略这一点。

但这似乎是标准所允许的，因为移动大小为 K 的向量不会移动其任何元素，并且“复杂性要求”“仅根据所包含的 int 对象的操作数量来说明” 。

是的，这是允许的。事实上， 的实际实现deque与此并没有那么不同（尽管它们出于明显的原因不使用std::vector自身）。实现的大致轮廓deque是指向块的指针数组（在前面和后面都有增长空间），每个块包含最多 X 个项目以及指向下一个/上一个块的指针（以使得单块）元素迭代快）。

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

如果没有这个规定，我不确定独特的功能集deque（快速前/后插入和随机访问）是否可以实现。