std::vector::insert 是否分配备用容量？

Question

代码如下

std::vector<int> a;
for(size_t i = 0; i < n; ++i)
    a.push_back(0);

保证在线性时间内运行n。这是通过在重新分配时分配一些额外的备用容量来实现的（通常将总容量增加一个常数因子）。

但是关于std::vector::insert(pos, x)？即是否保证

std::vector<int> a;
for(size_t i = 0; i < n; ++i)
    a.insert(a.end(), 0);

也是线性的吗？（类似的问题insert(pos, first, last)当然适用）

文档清楚地保证了“摊销常数”的复杂性。push_back

但文档insert说复杂性应该是“常数加上 pos 和容器末端之间距离的线性”。显然，只有在没有发生重新分配的情况下，这才是正确的，因此我不确定。

编辑：答案摘要：当发生重新分配时，实现可以

1. 增加最低限度的容量
2. 或者将容量增加到超过最小值，从而使将来的插入速度更快。

在 的情况下push_back，本质上需要选项 (2) 来实现“摊余常数”运行时间。在 的情况下insert(pos, first, last)，在单遍 InputIterator 的情况下需要选项 (2)（但在多遍 ForwardIterator 的情况下，实现可以并且确实使用 的单次重新分配new_capacity = max(2*old_capacity, new_size)）。所有其他情况均由实现定义。

使用 GCC 11 和 clang 12 进行测试，情况似乎是：

1. reserve并assign以最低限度增加容量，以及
2. push_back并将容量增加一个常数insert因子resize

Answer 1

实际语言是

\n

\n

[ vector.overview ] 矢量是一个序列容器，支持（摊销）末尾的恒定时间插入和擦除操作；中间插入和擦除需要线性时间

\n

\n

更具体地说

\n

\n

[ vector.modifiers 1 ] 复杂性：如果发生重新分配，则与结果向量的元素数量成线性关系；否则，与插入的元素数量加上到向量末尾的距离成线性关系。

\n

\n

但我们都同意插入是大致线性的。

\n

当重新分配发生时，选项有：

\n

\n

1. 重用相同的内部机制来增长向量，如下所示push_back()：

   \n

   这显然仍然是摊销常数时间，因此线性时间元素移动仍然占主导地位

   \n
\n

2. 将向量仅增加一个元素：

   \n

   由于这仍然是线性时间，因此仍在允许的复杂性范围内。然而，这实际上对实施者来说是更多的努力，并且客观上更糟糕

   \n
\n

\n

我认为我从未见过一个实现不仅为这两者重用了一些内部方法，而且花更多的精力做更糟糕的事情在技术上是合法的。grow()

\n

这种推理的例外是范围过载insert(iterator pos, InputIterator begin, InputIterator end)，因为对于严格的LegacyInputIterator，您只能执行一次传递。

\n

如果您无法预先计算要增长的元素数量，则任何增长都必须分摊恒定时间，否则整体复杂性将由N * distance(begin,end)控制，这可能是O(N\xc2\xb2)不符合要求的。

\n\n

太长了；博士

\n

\n
• push_back必须分配额外的容量以保持摊销恒定时间
\n
• insert(pos, begin, end)必须对 的每个元素使用摊余常数时间增长，(begin,end]以保持整体摊余线性时间
\n
• insert(pos, value)不需要分配额外的容量来满足其复杂性要求，但实施者可能会付出更多的努力才能得到更糟糕的结果
\n

\n