When does a std::vector reallocate its memory array?

Question

I can't find anything that gives a definitive answer. I was just curious if a std::vector reallocate its internal array only when it absolutely must or will it reallocate ahead of time in anticipation (so to speak).

For example:

std::vector<int> myVector;
for (int i = 0; i < 1000; ++i) myVector.push_back(i);

cout << myVector.size() << '\n'      // Gives 1000 as expected
     << myVector.capacity() << endl; // Gives 1024 which makes sense

If I continue to add elements, is there ever any chance that one of the next 24 items I add will change the capacity or will it only reallocate once I put in a 25th item?

Note:

I did run a test using gcc 4.4.3 under Linux, but and it seems like the reallocation is done "on-demand", but I was curious if I was just lucky or if there is something somewhere stating that this is expected behavior.

Answer 1

From C++ standard 23.2.4.2:

size_type capacity() const;

Returns: The total number of elements that the vector can hold without requiring reallocation.

Also from Standard

Notes: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the size specified in the most recent call to reserve().

So yes, you can be sure.

Edit: As @Bo Persson mentioned there is a catch. Standard doesn't say anything if we never call reserve() . However in practice it works well, because no implementation will care to remember if you called reserve, or not. I believe that this is bug. And as @Martin mentioned in his answer in C++0x draft it is corrected.

Answer 2

From the standard: n3092: Draft C++0x

23.3.6.2 vector capacity [vector capacity]

void reserve(size_type n);
2 Effects: A directive that informs a vector of a planned change in size, so that it can manage the storage allocation accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve(). If an exception is thrown other than by the move constructor of a non-CopyConstructible type, there are no effects.

23.3.6.4 vector modifiers [vector.modifiers]
Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyConstructible T, the effects are unspecified.