c++ - 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) 呢？ IE。是否保证

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

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

documentaiton of push_back在保证“摊销常数”复杂性方面很明确。

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

编辑:答案总结:当重新分配发生时，实现可以要么

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

在 push_back 的情况下，选项 (2) 本质上是实现“摊销常量”运行时所必需的。在 insert(pos, first, last) 的情况下，选项 (2) 在单 channel InputIterator 的情况下是必需的(但在多 channel ForwardIterator 的情况下，实现可以并且确实使用了一个使用 new_capacity = max(2*old_capacity, new_size) 进行单次重新分配)。所有其他情况均由实现定义。

用GCC 11和clang 12测试，情况好像是:

1. reserve 和 assign 以最低限度增加容量，并且
2. push_back 和insert 和resize 以常数因子增加容量

Answer 1

实际的语言是

[vector.overview] A vector is a sequence container that supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time

更具体地说

[vector.modifiers 1] Complexity: If reallocation happens, linear in the number of elements of the resulting vector; otherwise, linear in the number of elements inserted plus the distance to the end of the vector.

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

当重新分配发生时，选项是:

1. 重用与 push_back() 相同的内部机制来增长 vector :

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

2. 只增加一个元素的 vector :

   因为这仍然是线性时间，所以它仍然在允许的复杂度之内。但是，对于实现者来说，实际上是付出了更多的努力，客观上更糟

我认为我从未见过没有只是为这两者重用一些内部 grow() 方法的实现，但它会是花更多的精力做更糟糕的事情在技术上是合法的。

此推理的异常(exception)是范围重载insert(iterator pos, InputIterator begin, InputIterator end) 因为对于严格的LegacyInputIterator，您只能执行一次传递.

如果您无法预先计算要增长的元素数量，则任何增长都必须按常数时间摊销，否则整体复杂度将由 N * distance(begin,end) 控制，这可能是 O(N²)，因此不符合标准。

---

tl;博士

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