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.

Answer 3

If you look at the documentation for push_back on cplusplus.com it states:

This effectively increases the vector size by one, which causes a reallocation of the internal allocated storage if the vector size was equal to the vector capacity before the call. Reallocations invalidate all previously obtained iterators, references and pointers.

So I very much doubt the size would change before that but you could always test it. At least on my platform the size changes as stated above:

size vs capacity
1020 vs 1024
1021 vs 1024
1022 vs 1024
1023 vs 1024
1024 vs 1024
1025 vs 2048

Answer 4

std::vector would reallocate itself with the increased capacity on demand -- i.e. when current capacity is exceeded (when size() == capacity()).

How much capacity would be added, depend on the implementation: usually new_capacity = old_capacity * factor, where factor is somewhere from 1.5 to 2 (with theoretical ideal equals to Golden section). This is done so that pushing back new elements to the vector would have amortized constant time.

Answer 5

From cplusplus.com:

But vectors, also have a capacity, which determines the amount of storage space they have allocated, and which can be either equal or greater than the actual size. The extra amount of storage allocated is not used, but is reserved for the vector to be used in the case it grows. This way, the vector does not have to reallocate storage on each occasion it grows, but only when this extra space is exhausted and a new element is inserted (which should only happen in logarithmic frequence in relation with its size).

Answer 6

The standard guarantees which calls do not invalidate iterators. Technically, a std::vector could comply with the standard by only doing resizes that don't require copying the data to a new location, i.e., that don't invalidate iterators. I doubt anybody does, though.

So, resizes happen on calls to reserve() or resize() or any other call that is documented as invalidating iterators.

Answer 7

http://www.sgi.com/tech/stl/Vector.html states

Memory will be reallocated automatically if more than capacity() - size() elements are inserted into the vector. Reallocation does not change size(), nor does it change the values of any elements of the vector. It does, however, increase capacity(), and it invalidates [5] any iterators that point into the vector.

Answer 8

I found these notes helpful:

http://www.sgi.com/tech/stl/Vector.html#2

http://www.sgi.com/tech/stl/FAQ.html (Why does a vector expand its storage by a factor of two when it performs a reallocation?)

However, this is the SGI STL, couldn't find g++ documentation.