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 和容器末端之间距离的线性”。这显然只有在没有重新分配发生的情况下才是正确的，因此我不确定。

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

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

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

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

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

Answer 1

“摊销常数”的意思是“大部分时间都是常数”。 push_back 大多数调用的复杂度为 O(1)。如果需要重新分配，它将是线性的，但这种情况应该很少发生。

如果 insert 需要重新分配，所有元素都将被移动，即 O(n)。如果不需要重新分配，则移动新插入元素右侧的所有元素，但仍然是O(n)。

Cppreference 似乎没有可靠地提及复杂性部分中的重新分配。例如，resize() mentions possible additional complexity in Complexity section, but push_back() and insert() 仅在函数描述中提及重新分配。可能值得有一天清理它。

Answer 2

实际语言是

[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.

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

重新分配时，选项为：

重用与 push_back():
相同的内部机制来增长向量
这显然仍然是摊销常数时间，所以linear-time元素移动仍然占主导地位
向量只增加一个元素：

由于这仍然是线性时间，因此仍在允许的复杂度范围内。但是，对于实现者来说，其实是比较费力的，客观上更差

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

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

如果你不能pre-calculate增长的元素数量，任何增长都必须按常数时间摊销，否则整体复杂度将由 N * distance(begin, end)，可能是 O(N²)，因此是 non-conformant.

tl;博士

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

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

does std::vector::insert allocate spare capacity?

c++

memory-management

vector