C++ 预先分配向量是否更有效？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11888265/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is it more efficient to preallocate a vector?
提问by dangerousdave
In C++ Primer fourth edition, by Stanley B.Lippman, Josee Lajoie and Barbara E. Moo it states:
在 C++ Primer 第四版中，Stanley B.Lippman、Josee Lajoie 和 Barbara E. Moo 指出：
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.
由于向量有效地增长，通常最好通过在已知元素值的情况下向其动态添加元素来让向量增长。
and
和
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...
习惯使用 c 或 java 的读者可能会期望，因为向量元素是连续存储的，所以最好按预期大小预先分配向量。事实恰恰相反……
and
和
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.
尽管我们可以在向量中预先分配给定数量的元素，但定义一个空向量并向其添加元素通常更有效。
Assuming this is correct (the authors are as reputable as they come, one is a co-author of C++ itself) then can anyone give me a case that proves this statement, and explain why?
假设这是正确的（作者和他们一样有信誉，一个人是 C++ 本身的合著者）那么谁能给我一个案例来证明这个陈述，并解释为什么？
采纳答案by GManNickG
It depends.
这取决于。
If you don't know what the final size will be, then let the vector allocate using its allocation scheme (usually doubles each time, or somewhere around there). This way you avoid reallocating for every single element:
如果您不知道最终的大小是多少，那么让向量使用其分配方案进行分配（通常每次都翻倍，或附近的某个地方）。这样您就可以避免为每个元素重新分配：
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)
}
But if you know ahead of time you won't be reallocating, then preallocate:
但是如果你提前知道你不会重新分配，那么预分配：
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!)
}
回答by Akavall
I timed this simple example:
我给这个简单的例子计时：
#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;
}
Complied with:
符合：
g++ -std=c++11 -O2 my_file.cpp -o my_exec
And found the difference to be substantial:
并发现差异很大：
Without preallocation:
没有预分配：
real 0m3.366s
user 0m1.656s
sys 0m1.660s
With preallocation:
预分配：
real 0m1.688s
user 0m0.732s
sys 0m0.936s
My conclusion here is: If building a vector is a big part of the program, then preallocating for efficiency makes sense. However, building a larger vector over and over is unlikely, and thus it is rarely a bottle neck. However, using reserve()has other advantages besides preallocating.
我的结论是：如果构建向量是程序的重要组成部分，那么预分配是为了提高效率。然而，一遍又一遍地构建更大的向量是不太可能的，因此它很少成为瓶颈。但是，使用reserve()除了预分配之外还有其他优点。
Bjarne Stroustrup in The C++ programming language (4th addition) has this to say:
Bjarne Stroustrup 在 The C++ 编程语言（第 4 次添加）中有这样的说法：
I used to be careful about using
reserve()when I was reading into a vector. I was surprised to find that for essentially all my uses, callingreserve()did not measurably affect performance. The default growth strategy worked just as well as my estimates, so I stopped trying to improve performance usingreserve(). Instead I use it to increase predictability of reallocation delays and to prevent invalidation of pointers and iterators.
我曾经
reserve()在读入向量时小心使用。我惊讶地发现，对于我的所有用途，调用reserve()并没有显着影响性能。默认的增长策略和我的估计一样有效，所以我停止尝试使用reserve(). 相反，我使用它来增加重新分配延迟的可预测性并防止指针和迭代器失效。
回答by jcoder
It can be. It depends a loton what the elements are, how much work it is to copy or construct them, and how many there are.
有可能。这取决于很多什么的元素是，有多少工作来复制或建立他们，有多少。
If you preallocate a vector you will end up calling the default constructor for each element to make empty elements, and then copying the item over the space later. If you add elements it can just copy or construct the element in place which may be more efficient.
如果您预先分配了一个向量，您最终将调用每个元素的默认构造函数来创建空元素，然后稍后将该项目复制到空间上。如果你添加元素，它可以只复制或构造元素，这可能更有效。
