I want to talk about a couple of the lesser known member functions of the best known STL container: reserve() and shrink_to_fit(). These members manipulate the vector’s capacity. The reserve() member is original and I discuss it in this post. New with C++11 is shrink_to_fit(). I’ll talk about it in a future post.
How can it be constant time when copying all existing items will take time proportional to the number of existing items? The trick is that when push_back() triggers a reallocation, the new array is not a constant size increase of the existing array, but is proportional to the existing array (e.g. doubling in size). This approach means that although each reallocation is more expensive (due the increased number of exiting items), the allocations end up being required exponentially less often. The result works out to average (or amortized) constant time.
This is a great way to deal with allocations when we don’t know how many items we will need the vector to hold. But what if we do know how many items will be required? Suppose we know in advance that our vector will need to hold a thousand items. If vector initially allocates enough space for eight items and allocates an array twice as large as the existing one with each reallocation, we’ll need seven reallocations (and copies of all existing items) before we are finished adding our thousand items. This may be optimal if we have no idea how many items we’ll need to handle, but it is wasteful if we know in advance that we will need to hold a thousand items. We’d like a way to tell vector upfront that we need to hold a thousand items so it can create this space with one allocation and avoid needlessly copying items.
One way to do this to pre-fill our vector. If we are working with a vector of ints we can do something like this:
#include <iostream>
#include <vector>
using Ints = std::vector<int>;
// some how we know the upper bound of our storage requirement
const int vector_limit(1000);
int main()
{
Ints v(vector_limit); // pre-fill a thousand ints
std::cout << v.size() << std::endl;
std::cout << v.capacity() << std::endl;
}
1000
some value >= 1000, likely 1000
The drawback to this approach is that we’ve not just changed the vector’s capacity, but its content as well. If we know we need to store a thousand ints, pre-filling the vector may not be a problem, but consider some other cases. Suppose we know only the upper bound of the number of items, but not the exact number and the item type has an expensive constructor. Or no default constructor. In these cases, pre-filling the vector is problematic.
What we need is a way to increase a vector’s capacity without changing it’s size.
Enter reserve(). reserve() takes a parameter that tells the vector class how many items we expect to hold. In our example we can call reserve() with the value one thousand before pushing back any items. This would trigger a single allocation and since we haven’t added any items to the vector, there are no existing items that need to be copied. Big win.
#include <iostream>
#include <vector>
using Ints = std::vector<int>;
// some how we know the upper bound of our storage requirement
const int vector_limit(1000);
int main()
{
Ints v; // creates an empty vector
v.reserve(vector_limit); // increase capacity only
std::cout << v.size() << std::endl;
std::cout << v.capacity() << std::endl;
}
0
some value >= 1000, likely 1000
One of the reasons that I wanted to discuss reserve() is because of a discussion I had with some very experienced and knowledgable C++ programmers. I was surprised to learn that they believed that reserve() is only an optimization-enabling hint to the library and that the library has the option of implementing it as a no-op. This is wrong on two counts. The standard does not allow reserve() to be a no-op (unless the passed values is already less than or equal to the vector’s current capacity).
Further, the standard guarantees that adding items to the vector up to the reserve() limit, will not only not cause a reallocation, but that iterators will not be invalidated. This is not just an optimization, but is an important guarantee because in general, we always assume that push_back() and insert() will invalidate iterators. (You can verify that these calls will not invalidate iterators for a specific call by checking the current capacity before the call.)
Because of this guarantee we can be confident that iterators (and references and pointers) are not invalidated as long as don’t increase the size of our vector beyond our reserve.
#include <cassert>
#include <iostream>
#include <vector>
using Ints = std::vector<int>;
// some how we know the upper bound of our storage requirement
const int vector_limit(1000);
int main()
{
Ints v; // creates an empty vector
v.reserve(vector_limit); // increase capacity only
// add a single element and remember its address
v.push_back(0);
const int* start_of_allocated_array(&v[0]);
// fill the vector to our limit
for (int i(1); i < vector_limit; ++i) v.push_back(i);
// verify no invalidation of iterators, pointers, or references
assert(start_of_allocated_array == &v[0]);
}
What if we want to maintain stable access to items in the face of iterator invalidation (where we are adding items beyond the vector's capacity)? The trick is to use index values instead of iterators, pointers, or references. The Nth item in the vector will still be the Nth items after a reallocation.
The other reason I wanted to discuss reserve() is because of a nasty performance bug that some of my co-workers found within the last few days. Proper use of reserve() can be a nice performance win, but there is a gotcha scenario. In the bug, the code was calculating how many items needed to be added to the vector and then calling reserve() before adding them. This seems like a good use, until you realize that this code is being called in a loop. So what is happening is, each time through the loop we find that we need to add a few more items so we call reserve() which has the result of copying all existing items. What leads to this result is one of the characteristic of reserve() that isn't mandated by the standard, but it is usually the way that it is implemented. Let me explain.
As I said before, when a reallocation happens, the new size of the array is some proportion, usually double, of the old size of the array. The standard doesn't mandate any particular ratio. It also doesn't provide an upper limit on the capacity after a call to reserve(). An implementation is free to allocate an array double the value of the reserve() parameter. But that isn't what users would usually want or what most implementations provide. Usually reserve() will create a capacity exactly equal to the value passed. The passed value is a very good hint about the upper bound of the vector's size, and implementations take advantage of this hint.
Consider the implication of this on our performance bug. Without the call to reserve(), the push_back() in the loop would have added items with amortized constant time. But by calling reserve() in the loop, each reserve() resulted in copying every item in the vector every time through the loop and also pinning the capacity to exactly the reserve() value rather than a proportionally larger value, with disastrous performance consequences.
reserve() is a great tool for optimizing vector performance, but keep in mind the optimal use case for it. We want to call reserve() once when we can determine the upper bound on the vector's size requirement before we have added any values to the vector. There are many cases were we can't predict the size requirement upper bound, so we can't implement this optimal strategy and we may have to modify it. But calling reserve() several times with increasing estimates of the required capacity is not a strategy likely to yield success.
Please comment on Google Plus or reddit.