[ACCEPTED]-When does a std::vector reallocate its memory array?-vector

From C++ standard 23.2.4.2:

size_type capacity() const;

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

Also 16 from Standard

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

So 8 yes, you can be sure.

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

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

23.3.6.2 21 vector capacity [vector capacity]

void reserve(size_type 20 n);
2 Effects: A directive that informs 19 a vector of a planned change in size, so 18 that it can manage the storage allocation 17 accordingly. After reserve(), capacity() is 16 greater or equal to the argument of reserve 15 if reallocation happens; and equal to the 14 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 13 an exception is thrown other than by the 12 move constructor of a non-CopyConstructible 11 type, there are no effects.

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

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

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

So I very much doubt the size 3 would change before that but you could always 2 test it. At least on my platform the size 1 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

From cplusplus.com:

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

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

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

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

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

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

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

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 3 vector expand its storage by a factor of 2 two when it performs a reallocation?)

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