C++ / STANDARD CONTAINERS
std::vector and its growth strategy
Predict when a vector reallocates, use reserve to remove the copying, and know exactly which pointers and iterators growth invalidates.
What you will learn
- Read size() and capacity() to predict when the next push_back reallocates
- Call reserve(n) once before a known-length fill to remove all growth copies
- Treat every pointer, reference and iterator as dead after the vector grows
- Release peak memory with shrink_to_fit, because clear() keeps the capacity
Understanding std::vector and its growth strategy
A vector is three values: a pointer to one contiguous heap block, the number of elements constructed in it (size), and the number of slots that block can hold (capacity). push_back constructs into the next free slot and bumps size, which is cheap. When size already equals capacity there is no free slot, and there is no way to extend a heap block in place, so the vector allocates a bigger block, relocates every existing element into it, destroys the originals, and frees the old block.
How much bigger that new block is, is the growth strategy. Growing by a fixed number of slots would reallocate every few pushes and relocate on the order of n squared over the step size elements while filling n items. Multiplying capacity by a constant factor instead makes the relocation counts a geometric series: for doubling they are 1 + 2 + 4 + ... + n/2, which is less than n, so total relocation work is linear and push_back is constant time on average even though one individual call can touch the whole buffer. The standard only mandates that amortized bound; libstdc++ and libc++ double, MSVC multiplies by about 1.5, so the exact capacities you print differ per implementation.
The price of relocation is that the old block is gone: any pointer, reference, iterator, or data() result taken before a growth now points into freed memory, and using it is undefined behaviour. Capacity also only ever goes up on its own — erase, resize downward, and clear destroy elements but keep the block, so capacity behaves as a high-water mark until you call shrink_to_fit or swap with a fresh vector. When you know the final element count, reserve(n) allocates once, removes every relocation, and keeps addresses stable for exactly the first n pushes.
<iostream>
<vector>
int main() {
std::vector<int> v;
auto cap = v.capacity();
std::cout << "start: size=" << v.size() << " capacity=" << cap << '\n';
for (int i = 0; i < 10; ++i) {
v.push_back(i);
if (v.capacity() != cap) {
cap = v.capacity();
std::cout << "grew on push_back(" << i << "): size=" << v.size()
<< " capacity=" << cap << '\n';
}
}
v.reserve(100);
std::cout << "after reserve(100): size=" << v.size()
<< " capacity=" << v.capacity() << '\n';
}
std::vector keeps its elements in one contiguous block and multiplies the block size when it fills up, which buys amortized constant-time push_back at the cost of invalidating everything that pointed into the old block.
Worked examples
Growth moves the whole buffer
Comparing data() before and after a push_back shows that growth relocates the block, and that reserve prevents it.
<iostream>
<vector>
int main() {
std::cout << std::boolalpha;
std::vector<int> v{1, 2, 3};
std::cout << "v: size=" << v.size() << " capacity=" << v.capacity() << '\n';
const int* old_block = v.data();
v.push_back(4);
std::cout << "block moved after push_back: " << (v.data() != old_block) << '\n';
std::vector<int> w;
w.reserve(4);
w.push_back(1);
const int* fixed_block = w.data();
w.push_back(2);
w.push_back(3);
w.push_back(4);
std::cout << "block moved with reserve(4): " << (w.data() != fixed_block) << '\n';
std::cout << "w: size=" << w.size() << " capacity=" << w.capacity() << '\n';
}
Example explained
Line 1The initializer-list constructor allocates exactly three slots, so size == capacity and the next push_back has nowhere to write.
Line 2v.data() is the address of the one heap block; it changes because the vector allocates a new block, relocates the three ints, then frees the old one.
Line 3Comparing addresses is the safe way to observe this: dereferencing old_block after the growth would be undefined behaviour, not a guaranteed crash.
Line 4reserve(4) buys the final block up front, so four pushes fit without relocation and fixed_block still addresses element 0.
Counting the copies growth costs
A type that counts copy constructions shows how many extra element copies doubling adds, and that reserve removes all of them.
<iostream>
<vector>
struct Element {
static int copies;
int value;
explicit Element(int v) : value(v) {}
Element(const Element& other) : value(other.value) { ++copies; }
};
int Element::copies = 0;
int main() {
std::vector<Element> grown;
for (int i = 0; i < 8; ++i) grown.push_back(Element(i));
std::cout << "no reserve: " << Element::copies << " copies, capacity "
<< grown.capacity() << '\n';
Element::copies = 0;
std::vector<Element> reserved;
reserved.reserve(8);
for (int i = 0; i < 8; ++i) reserved.push_back(Element(i));
std::cout << "reserve(8): " << Element::copies << " copies, capacity "
<< reserved.capacity() << '\n';
}
Example explained
Line 1Element declares a copy constructor and no move constructor, so both inserting an element and relocating it during growth go through the counted copy.
Line 2Eight pushes account for 8 copies; the other 7 are the relocations of 1, then 2, then 4 elements as capacity stepped 1, 2, 4, 8.
Line 31 + 2 + 4 is smaller than the 8 elements stored, which is the geometric series that makes push_back amortized constant time.
Line 4reserve(8) allocates the final block first, so nothing is relocated and only the 8 insertions copy.
Capacity does not fall on its own
Shrinking the size of a vector keeps the allocated block until shrink_to_fit is called.
<iostream>
<vector>
int main() {
std::vector<int> v(1000, 7);
std::cout << "built: size " << v.size()
<< ", capacity " << v.capacity() << '\n';
v.resize(10);
std::cout << "after resize(10): size " << v.size()
<< ", capacity " << v.capacity() << '\n';
v.clear();
std::cout << "after clear(): size " << v.size()
<< ", capacity " << v.capacity() << '\n';
v.shrink_to_fit();
std::cout << "after shrink: size " << v.size()
<< ", capacity " << v.capacity() << '\n';
}
Example explained
Line 1The sizing constructor knows the count in advance, so it allocates exactly 1000 slots instead of growing to a power of two.
Line 2resize(10) destroys 990 elements but leaves the block untouched, which is why capacity stays 1000.
Line 3clear() destroys the remaining elements and sets size to 0; keeping the buffer is what makes refilling a reused vector allocation-free.
Line 4shrink_to_fit asks for a block matching the current size, and here the empty vector gives its memory back entirely.
Important notes
Exact capacity values are implementation-defined — libstdc++ and libc++ double, MSVC uses roughly 1.5x — so never write logic that assumes capacity is a power of two, and treat shrink_to_fit as a non-binding request.
Relocation moves elements only when their move constructor is noexcept; if it can throw, vector copies instead to preserve the strong exception guarantee, so mark move constructors noexcept.
Common mistakes
Calling reserve(n) and then writing v[i]: reserve only allocates slots, no elements exist yet, so the writes are undefined behaviour and size() stays 0 — use resize(n) when you want n live elements.
Holding int& first = v[0] (or an iterator, or data()) across a push_back: the first push that grows the vector leaves it pointing into a freed block, which typically reads plausible-looking garbage rather than crashing.
Calling reserve(v.size() + 1) inside the fill loop: that requests a bigger block on every iteration, defeats the geometric growth, and turns a linear fill into quadratic copying.
Try it yourself
Change, predict, then run
Push the numbers 1 to 50 into a vector<int> and print size and capacity only on the pushes where capacity changed. Then add reserve(50) before the loop and compare how many lines each version prints and what the final capacity is.
Open the C++ workspaceCheck your understanding
Filling a vector with 1,000,000 push_back calls costs O(n) in total, even though some individual calls relocate the entire buffer. Why?
- Each reallocation multiplies capacity by a constant factor, so relocations happen exponentially less often and the elements relocated across the whole fill sum to less than n
- Reallocation is O(1) because the allocator can normally extend the existing block in place instead of copying
- push_back never relocates more than one element, so the loop performs n element constructions in total
- The compiler sees the loop bound and hoists the growth out of the loop, so it only allocates once
Show answer
With doubling, the relocation counts are 1 + 2 + 4 + ... + n/2, which is under n, so the extra work averages to a constant per push even though one push can be O(n). Option 2 is tempting because C code can sometimes grow a malloc block in place with realloc, but vector must construct its elements into a fresh block and free the old one, since arbitrary element types are not guaranteed to be relocatable by a raw byte copy.