在 std::vector::resize 和 std::vector::push_back 中摊销

Question

我们知道重新分配机制负责分配更多我们在调用时实际需要的内存 std::vector::push_back()。通常容量随着乘数 2x 或黄金比例数增长 ~1.618...

假设，我们按如下方式添加元素：

std::vector<int> v;
for(unsigned i = 0; i < 100000; ++i)
{
    v.resize(v.size() + 1);
}

如果发生重新分配，是否可以保证向量的容量为"doubled"？换句话说：“+1 调整大小”是否会以与 push_back.

相同的方式分配内存

还是纯粹依赖于实现？

Answer 1

Is it guaranteed that the capacity of the vector is "doubled" if the reallocation takes place?

没有。内存重新分配的复杂性是摊销常数。对象的容量是在需要时加倍还是增加另一个因素取决于实现。

would the "+1 resize" allocate the memory the same way as it is done for push_back

是的。

当 sz 大于 size() 时，

std::vector::resize(size_type sz) 将 sz - size() 个值初始化的元素附加到序列中。那相当于：

 insert(end(), sz-size(), <value initialized object>);

std::vector::insert、std::vector::emplace 和 std::vector::push_back 具有相同的内存分配复杂度 - 均摊常数。

Answer 2

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

和

If size() < sz , appends sz - size() default-inserted elements to the sequence.

调整大小。恕我直言，是的，如果重新分配发生

，则可以保证向量的容量为"doubled"

Amortizing in std::vector::resize and std::vector::push_back