c++ - 预分配 vector 是否更有效？

Question

在 Stanley B.Lippman、Josee Lajoie 和 Barbara E. Moo 的 C++ Primer 第四版中，它指出:

Because vectors grow efficiently, it is usually best to let the vector grow by adding elements to it dynamically as the element values are known.

和

Readers accustomed to using c or java might expect that because vector elements are stored contiguously, it would be best to preallocate the vector at its expected size. In fact the contrary is the case...

和

Allthough we can preallocate a given number of elements in a vector, it is usually more efficient to define an empty vector and add elements to it.

假设这是正确的(作者和他们一样有声望，一个是 C++ 本身的合著者)那么谁能给我一个证明这个说法的案例，并解释为什么？

Answer 1

视情况而定。

如果您不知道最终大小是多少，则让 vector 使用其分配方案进行分配(通常每次加倍，或附近的某个地方)。这样可以避免为每个元素重新分配:

std::vector<int> v;

// good:
for (/* populate v */) // unknown number of iterations
{
    v.push_back(i); // possible reallocation, but not often
}

// bad:
for (/* populate v */) // unknown number of iterations
{
    v.reserve(v.size() + 1); // definite reallocation, every time
    v.push_back(i); // (no reallocation)
}

但是如果你提前知道你不会重新分配，那么预分配:

std::vector<int> v;

// good:
v.reserve(10); 
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // no reallocations
}

// not bad, but not the best:
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // possible reallocation, but not often (but more than needed!)
}