52

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?

Improve this question
1
  • In many cases it is more efficient. But the real questions should be: "by how much?" and "what is the price we pay for that?". Commented Mar 12, 2023 at 19:47

3 Answers 3

Reset to default
45

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!) }
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

I'll add some more context to my original question, but I think it implies that even if the size is known up front, it is usually more efficient to let the vector grow.
@dangerousdave: Okay, but if you know the size up front, just allocate once and you're done. It truly isn't better to let it grow, which will allocate unnecessarily often.
Most of the time the difference will be small enough that nobody will notice. Then it is more efficient to write less code.
@BoPersson: That's just not true, I think. Memory allocation generally isn't lightweight, and the work done by reallocating does add up, I've seen it in my own applications. I am of course assuming we're talking "real" amounts of data, not tiny sandbox vectors.
@BoPersson: I'm part of the "don't pre-maturely optimize" crowd too, but the reason I'm in that crowd is because people often waste time trying to make optimizations that aren't even in the right spots. If making those optimizations took no time, then I wouldn't stop them. This optimization takes no time, and I would expect any competent programmer to preallocate a buffer to it's required size when possible to do so, it's literally a single line of code. This is like choosing the right sort implementation, a regular design decision, not like trying to optimize i++.
|
17

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.

Improve this answer

Comments

7

It can be. It depends a lot on 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.

Improve this answer

7 Comments

Preallocating doesn't entail default constructing. v.reserve(n); // constructs nothing
However, if you use reserve, it doesn't do any of the construction up front, and only the allocation. Which might be even better.
@GManNickG: I think that the quote, since it says "preallocating elements" and not "preallocating space for elements", it is referring to resize (or the constructor that takes a size), rather than reserve.
A fair bit of semantic ambiguity there, so I could see that. I think more important is what actually should be done, though, and not caring too much for what the author's words literally mean.
to clarify, by "preallocate", given the context, I believe it is referring to vector<string> svec(10,"hi")
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.