What are the benefits of using reserve() in a vector?

Question

What are the benefit of using reserve when dealing with vectors. When should I use it? I couldn't find a clear cut answer on this but I assume it is faster when you reserve in advance before using them.

Georg

Thank you everyone for the reply. Additionally, does using reserve(20) mean that there are 20 elements now or just that the memory for 20 elements has been allocated? – Georg

Just the memory has been allocated. The memory is not initialized. – Allargando

reserve() adds capacity, but doesn't add elements. What gets returned by size() will be unchanged (however, capacity() will return at least 20 in your example). – Codicodices

Answer 1

It's useful if you have an idea how many elements the vector will ultimately hold - it can help the vector avoid repeatedly allocating memory (and having to move the data to the new memory).

In general it's probably a potential optimization that you shouldn't need to worry about, but it's not harmful either (at worst you end up wasting memory if you over estimate).

One area where it can be more than an optimization is when you want to ensure that existing iterators do not get invalidated by adding new elements.

For example, a push_back() call may invalidate existing iterators to the vector (if a reallocation occurs). However if you've reserved enough elements you can ensure that the reallocation will not occur. This is a technique that doesn't need to be used very often though.

Codicodices

...and doing repeated allocate/copy/move sequences when the currently available space runs out can lead to heap fragmentation. – Infantry

"..ensure that existing iterators do not get invalidated by adding new elements." this is true for specific kinds of adds (the push_back example is one such kind). But an insert() will invalidate all iterators from the insertion point on, even with ample capacity available (and of course, if capacity requires a resize everything falls off the table). The extreme version is, of course, an insert(v.begin(), ...) which invalidates all iterators always. Thankfully, there are better containers than vector to handle that if it is frequent operation by one's code. – Alded

Answer 2

This excellent article deeply explains differences between deque and vector containers. Section "Experiment 2" shows the benefits of vector::reserve().

Calicut

Answer 3

It can be ... especially if you are going to be adding a lot of elements to you vector over time, and you want to avoid the automatic memory expansion that the container will make when it runs out of available slots.

For instance, back-insertions (i.e., std::vector::push_back) are considered an ammortized O(1) or constant-time process, but that is because if an insertion at the back of a vector is made, and the vector is out of space, it must then reallocate memory for a new array of elements, copy the old elements into the new array, and then it can copy the element you were trying to insert into the container. That process is O(N), or linear-time complexity, and for a large vector, could take quite a bit of time. Using the reserve() method allows you to pre-allocate memory for the vector if you know it's going to be at least some certain size, and avoid reallocating memory every time space runs out, especially if you are going to be doing back-insertions inside some performance-critical code where you want to make sure that the time to-do the insertion remains an actual O(1) complexity-process, and doesn't incurr some hidden memory reallocation for the array. Granted, your copy constructor would have to be O(1) complexity as well to get true O(1) complexity for the entire back-insertion process, but in regards to the actual algorithm for back-insertion into the vector by the container itself, you can keep it a known complexity if the memory for the slot is already pre-allocated.

Allargando

Answer 4

If you know the eventual size of the vector then reserve is worth using.

Otherwise whenever the vector runs out of internal room it will re-size the buffer. This usually involves doubling (or 1.5 * current size) the size of the internal buffer (can be expensive if you do this a lot).

The real expensive bit is invoking the copy constructor on each element to copy it from the old buffer to the new buffer, followed by calling the destructor on each element in the old buffer.

If the copy constructor is expensive then it can be a problem.

Tisman

If the copy constructor is expensive, using std::deque may be a better option. gotw.ca/gotw/054.htm – Stannary

Answer 5

Although its an old question, Here is my implementation for the differences.

#include <iostream>
#include <chrono>
#include <vector>

using namespace std;

int main(){
    vector<int> v1;
    chrono::steady_clock::time_point t1 = chrono::steady_clock::now();
    for(int i = 0; i < 1000000; ++i){
        v1.push_back(1);
    }
    chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
    chrono::duration<double> time_first = chrono::duration_cast<chrono::duration<double>>(t2-t1);
    cout << "Time for 1000000 insertion without reserve: " << time_first.count() * 1000 << " miliseconds." << endl;

    vector<int> v2;
    v2.reserve(1000000);
    chrono::steady_clock::time_point t3 = chrono::steady_clock::now();
    for(int i = 0; i < 1000000; ++i){
        v2.push_back(1);
    }
    chrono::steady_clock::time_point t4 = chrono::steady_clock::now();
    chrono::duration<double> time_second = chrono::duration_cast<chrono::duration<double>>(t4-t3);
    cout << "Time for 1000000 insertion with reserve: " << time_second.count() * 1000 << " miliseconds." << endl;
    return 0;
}

When you compile and run this program, it outputs:

Time for 1000000 insertion without reserve: 24.5573 miliseconds.

Time for 1000000 insertion with reserve: 17.1771 miliseconds.

Seems to be some improvement with reserve, but not that too much improvement. I think it will be more improvement for complex objects, I am not sure. Any suggestions, changes and comments are welcome.

Clemenciaclemency

Answer 6

Faster and saves memory

If you push_back another element, then a full vector will typically allocate double the memory it's currently using - since allocate + copy is expensive

Homogeneity

Answer 7

Don't know about people smarter than you, but I would say that you should call reserve in advance if you are going to perform lots in insertion operations and you already know or can estimate the total number of elements, at least the order of magnitude. It can save you a lot of reallocations in good circumstances.

Target

Answer 8

It's always interesting to know the final total needed space before to request any space from the system, so you just require space once. In other cases the system may have to move you in a larger free zone (it's optimized but not always a free operation because a whole data copy is required). Even the compiler will try to help you, but the best is to to tell what you know (to reserve the total space required by your process). That's what i think. Greetings.

Bedpost

Answer 9

There is one more advantage of reserve that is not much related to performance but instead to code style and code cleanliness.

Imagine I want to create a vector by iterating over another vector of objects. Something like the following:

std::vector<int> result;
for (const auto& object : objects) {
  result.push_back(object.foo());
}

Now, apparently the size of result is going to be the same as objects.size() and I decide to pre-define the size of result.

The simplest way to do it is in the constructor.

std::vector<int> result(objects.size()); 

But now the rest of my code is invalidated because the size of result is not 0 anymore; it is objects.size(). The subsequent push_back calls are going to increase the size of the vector. So, to correct this mistake, I now have to change how I construct my for-loop. I have to use indices and overwrite the corresponding memory locations.

std::vector<int> result(objects.size());
for (int i = 0; i < objects.size(); ++i) {
  result[i] = objects[i].foo();
}

And I don't like it. Indices are everywhere in the code. This is also more vulnerable to making accidental copies because of the [] operator. This example uses integers and directly assigns values to result[i], but in a more complex for-loop with complex data structures, it could be relevant.

Coming back to the main topic, it is very easy to adjust the first code by using reserve. reserve does not change the size of the vector but only the capacity. Hence, I can leave my nice for loop as it is.

std::vector<int> result;
result.reserve(objects.size());

for (const auto& object : objects) {
  result.push_back(object.foo());
}

Carlinecarling