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

Question

我们知道，重分配机制可以在调用std::vector::push_back()时为我们分配比实际需要更多的内存。 通常容量增加的倍乘因子是 2 倍或者黄金比例数 ~1.618...。

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

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

如果重新分配内存，向量的容量是否保证“翻倍”？换句话说，“+1 调整大小”是否与 push_back 相同方式分配内存。

还是这完全取决于实现的事情？

- paceholder

---

我不理解这个问题。你已经提到容量通常会增长两倍或黄金比例。 - 463035818_is_not_a_number

@tobi303 我认为OP是在询问resize与push_back的比较。 - Chris Drew

@ChrisDrew 哦，好的，现在我明白问题了；）尽管我仍然认为它可以改进。 - 463035818_is_not_a_number

Answer 1

“你能保证，如果重新分配内存，向量的容量会“翻倍”吗？” 不是的。内存重新分配的复杂度是摊销常数。当需要时，对象的容量是增加两倍还是增加另一个因素取决于实现。 “+1调整大小”是否以与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在内存分配方面具有相同的复杂度-摊销常数。

- R Sahu

---

OP 询问关于“resize”的问题。 - Chris Drew

由于你的“否定”只是针对“加倍”这个词，而不是针对我认为原帖真正的问题（即resize是否具有与push_back相同的摊销常数行为），我建议，为了澄清，将你的最后一句话（在那里你解释说其他因素也可能存在）移到你的第一句旁边。请注意，“加倍”一词被引用，并且原帖已经提到了其他可能的因素，并在标题中使用了“摊销”的词。 - Benjamin Lindley

@BenjaminLindley，这绝对能提高答案的质量。感谢您的建议。 - R Sahu

我之所以在“double”一词前加上引号是有原因的。而且我明确询问了+1调整大小的问题。请查看澄清后的问题。 - paceholder

@paceholder，关于“+1调整大小”的问题，答案是肯定的。我不确定是否还有什么可以补充到我的答案中以使其更清晰明了。 - R Sahu

Answer 2

一个向量是一个序列容器，支持（摊销）常数时间插入和删除操作在末尾; [vector.overview]

并且

如果 size() < sz，则将 sz - size() 个默认插入的元素附加到序列中。

对于 resize。在我看来，这意味着，如果重新分配发生，向量的容量是“加倍”是有保证的。

- user2672107