Lesson 19 · Modern C++

STL containers: how std::vector grows

The standard library's containers are objects that own a group of elements and manage their memory for you. Follow the one you will use most, std::vector, through an eleven-line program: a small object on the stack, its elements side by side on the heap, push_back filling spare capacity, and the moment the block is full and the vector moves everything to a bigger one. See why growing invalidates old pointers, why push_back is still fast on average, and how the destructor frees it all.

12 min10 steps5 questionsAdvanced

Fig 19 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01A vector has size 3 and capacity 4. What does that mean?

size is how many elements are really there; capacity is how many fit in the current block. The next push_back fills the spare slot; the one after that makes the vector grow.

02What does v.reserve(2) do to an empty std::vector<int>?

reserve allocates room without making elements. size stays 0; capacity becomes at least the number you asked for. (resize is the call that adds elements.)

03A full vector gets one more push_back. What happens?

A vector keeps all its elements in one contiguous block, so when it is full it must reallocate. libstdc++ (GCC) and libc++ (LLVM) double the capacity; Microsoft's STL grows it by half.

04You took int* p = &v[0]; and then a push_back made v reallocate. What about p?

Reallocation invalidates every pointer, reference and iterator to the elements. Take them after the vector has grown, or reserve enough room first.

05Which container should you reach for first when you need a list of values?

std::vector is the default: contiguous, cache-friendly and amortised constant-time push_back. Choose std::map, std::unordered_map, std::deque or std::list when you need what they offer, such as lookup by key.

Key terms

Glossary

Container: A standard library object that holds a group of elements and owns their memory, such as std::vector, std::list or std::map.
std::vector: The standard dynamic array: elements side by side in one heap block that grows as you add to it.
size: How many elements a container really holds (v.size()).
capacity: How many elements a vector's current block can hold before it must grow (v.capacity()).
push_back: Adds an element at the end of a vector. Amortised constant time: usually instant, now and then a reallocation.
Reallocation: A vector moving its elements into a new, bigger block and freeing the old one, because the old one was full.
Iterator invalidation: After a container changes, some pointers, references and iterators to its elements stop being valid. A vector's reallocation invalidates all of them.
Amortised constant time: Constant on average over many calls, even though a few calls (here the ones that grow the vector) take longer.

Fine print

Notes and sources

The figure draws v as data, size and capacity. GCC's libstdc++ and LLVM's libc++ really store three pointers (start, end of the elements, end of the storage) and compute size and capacity from them; either way sizeof(std::vector<int>) is 24 bytes on 64-bit platforms.
The C++ standard does not fix how much a vector grows, only that push_back takes amortised constant time. GCC's libstdc++ and LLVM's libc++ double the capacity (2 becomes 4); Microsoft's STL grows by half (2 becomes 3). reserve(2) gives a capacity of at least 2; all three give exactly 2.
The addresses 0x5a10 and 0x5a30 are made up and short so they fit. Real ones are longer, change from run to run, and the new block need not sit right after the old one.
An int is 4 bytes on the usual desktop platforms (64-bit Linux, macOS and Windows), so slot [1] sits 4 bytes after slot [0]. The standard only promises at least 16 bits.
Inside a growing push_back, libstdc++ (_M_realloc_append) and libc++ (__push_back_slow_path) build the new element in the new block first and only then move or copy the old elements after it; a logging type prints ctor 30, move 10, move 20. Building it first keeps push_back(v[0]) correct and leaves v unchanged if that step throws. With ints your program cannot tell the difference.
When growing, push_back uses std::move_if_noexcept: it moves each element if its move constructor cannot throw (or the type cannot be copied), and copies it otherwise, so a failed copy leaves the vector unchanged.
The standard containers: sequence containers (array, vector, deque, list, forward_list), sorted associative containers (set, map, multiset, multimap; usually red-black trees, O(log n) lookup) and unordered ones (unordered_set, unordered_map ...; hash tables, average O(1) lookup). Each one owns its elements and frees them in its destructor.
The program on the card is real, standard C++ (C++11 or later). Build it with g++ -std=c++20 -Wall -Wextra grow.cpp -o grow and run ./grow: it prints 10 20 30 .

Quiz Unlocks after the last step.