43

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

因为向量有效地增长，通常最好通过动态添加元素来让向量增长，因为元素值是已知的。

和

习惯使用 c 或 java 的读者可能会期望，由于向量元素是连续存储的，因此最好将向量预分配为其预期大小。事实上，情况恰恰相反……

和

尽管我们可以在向量中预先分配给定数量的元素，但通常更有效的是定义一个空向量并向其添加元素。

假设这是正确的（作者和他们一样有声望，一个是 C++ 本身的合著者）那么任何人都可以给我一个证明这个陈述的案例，并解释为什么？

4

3 回答 3

40

这取决于。

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

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!)
}
于 2012-08-09T17:02:15.970 回答
12

我为这个简单的例子计时：

#include<iostream>
#include<vector>

int main() {

    int limit = 100 * 1000 * 1000;
    std::vector<long> my_vec;
    my_vec.reserve(limit); // comment out this line to not preallocate

    for (int i=0; i < limit; i++) {
        my_vec.push_back(i);
    }

    long my_sum = 0;
    for (int i=0; i < limit; i++) {
        my_sum += my_vec[i];
    }

    std::cout << my_sum << std::endl;
    return 0;
}

符合：

g++ -std=c++11 -O2 my_file.cpp -o my_exec

并发现差异很大：

没有预分配：

real    0m3.366s
user    0m1.656s
sys     0m1.660s

使用预分配：

real    0m1.688s
user    0m0.732s
sys     0m0.936s

我的结论是：如果构建向量是程序的重要组成部分，那么为提高效率而进行预分配是有意义的。然而，一遍又一遍地构建一个更大的向量是不可能的，因此它很少是一个瓶颈。但是，使用reserve()除了预分配之外还有其他优点。

C++ 编程语言（第 4 次添加）中的 Bjarne Stroustrup 有这样的说法：

reserve()当我读入向量时，我曾经很小心使用。我惊讶地发现，对于我的所有用途，调用reserve()并没有显着影响性能。默认的增长策略和我的估计一样有效，所以我停止尝试使用reserve(). 相反，我使用它来增加重新分配延迟的可预测性并防止指针和迭代器失效。

于 2017-05-20T17:25:16.247 回答
6

有可能。这在很大程度上取决于元素是什么，复制或构建它们的工作量以及有多少。

如果您预先分配一个向量，您最终会为每个元素调用默认构造函数以生成空元素，然后稍后将项目复制到空间上。如果您添加元素，它可以只复制或构建元素，这可能更有效。

于 2012-08-09T16:57:50.977 回答