Is it more efficient to preallocate a vector?

Question

In C++ Primer fourth edition, by Stanley B.Lippman, Josee Lajoie and Barbara E. Moo it states:

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...

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?

Answer 1

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

Answer 2

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.

Bjarne Stroustrup in The C++ programming language (4th addition) has this to say:

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, calling reserve() did not measurably affect performance. The default growth strategy worked just as well as my estimates, so I stopped trying to improve performance using reserve(). Instead I use it to increase predictability of reallocation delays and to prevent invalidation of pointers and iterators.