预分配矢量是否更有效？

Question

在C++ Primer第四版中,由Stanley B.Lippman,Josee Lajoie和Barbara E. Moo表示:

因为向量有效增长,所以通常最好通过在元素值已知时动态地向其添加元素来让向量增长.

和

习惯于使用c或java的读者可能期望因为向量元素是连续存储的,所以最好以预期的大小预先分配向量.事实恰恰相反......

和

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

假设这是正确的(作者和他们一样有信誉,一个是C++本身的共同作者)那么任何人都可以给我一个证明这个陈述的案例,并解释原因吗？

Answer 1

这取决于.

如果您不知道最终大小是多少,那么让矢量使用其分配方案进行分配(通常每次都会加倍,或者在那里的某处).这样就可以避免为每个元素重新分配:

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!)
}

Answer 2

有可能.这取决于很多什么的元素是,有多少工作来复制或建立他们,有多少.

如果你预先分配一个向量,你将最终调用每个元素的默认构造函数来创建空元素,然后在空格上复制该项目.如果添加元素,它可以只复制或构造元素,这可能更有效.

Answer 3

我把这个简单的例子计时:

#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++编程语言中的Bjarne Stroustrup(第4次添加)有这样的说法:

我曾经reserve()在阅读矢量时使用时要小心.我惊讶地发现,基本上我的所有用途,调用reserve()并没有显着影响性能.默认增长策略与我的估计一样有效,因此我不再尝试使用提高性能reserve().相反,我使用它来提高重新分配延迟的可预测性,并防止指针和迭代器失效.