stl · high

Vector Growth & Reallocation

Watch push_back fill free slots cheaply, then reallocate to double capacity and move elements when full.

The code

std::vector<char> v;       // size & capacity grow on demand
// v already holds A, B with capacity 4
v.push_back('C');          // free slot -> O(1)
v.push_back('D');          // fills capacity (4/4)
v.push_back('E');          // full -> reallocate (2x), move, add
// a reallocation invalidates iterators, pointers & references

What this lesson walks through

1. 01size vs capacity
2. 02push_back('C') - free slot, O(1)
3. 03push_back('D') - now full
4. 04push_back('E') - full, allocate 2x
5. 05move elements to the new buffer
6. 06construct E; old buffer freed
7. 07Why push_back is amortized O(1)
8. 08reserve() avoids reallocations

A vector tracks two numbers: size (elements in use) and capacity (slots allocated). Here it holds A and B but has room for 4.