STL containers — vector, list, deque, array, set, multiset, map, multimap, unordered_map, unordered_set: Visual walkthrough

We are going to earn the parent note's central formula: $T = \sum_{i = 0}^{⌊ l o g_{2} n ⌋} 2^{i} = 2^{⌊ l o g_{2} n ⌋ + 1} - 1 < 2 n$ one picture at a time. If any of those symbols look scary now — good. By Step 8 they will feel obvious.

Step 1 — What a vector actually is in memory

WHAT. A std::vector is a wrapper around three numbers: a pointer to a block of memory, a size (how many slots are used), and a capacity (how many slots the block can hold before it is full).

WHY. You cannot reason about the cost of growing something until you can see what "full" means. The whole $O (1)$ argument hinges on the gap between size and capacity.

PICTURE. Below, the grey slots are reserved but empty (capacity not yet used); the cyan slots are occupied (the size). Notice: push_back just writes into the next grey slot and bumps the size by one. That is a single write — $O (1)$ — as long as a grey slot exists.

Figure — STL containers — vector, list, deque, array, set, multiset, map, multimap, unordered_map, unordered_set

Step 2 — The cheap case and the expensive case

WHAT. There are exactly two things that can happen when you call push_back:

Cheap ( $s < c$ ): write into a free slot, $s + = 1$ . Constant work.
Expensive ( $s = c$ ): no room — allocate a bigger block, copy all $s$ old elements over, free the old block, then write. This copy is $O (s)$ work.

WHY. If every push were expensive, a vector would be a terrible container. The magic is that the expensive case is rare. To measure "how rare", we first have to fix the rule for how much bigger the new block is.

PICTURE. Left: a push landing in a free slot (one arrow, one write). Right: a full block forcing a reallocation — every existing element gets carried to a new, larger home.

Step 3 — The growth rule: why doubling?

WHAT. When full, the vector allocates a block of capacity $c_{new} = 2 c$ (the typical libstdc++/MSVC choice). It doubles.

WHY doubling and not "+1 each time"? This is the key design decision, so let us justify it, not assume it. Suppose instead we grew by a fixed +1 every time it filled. Then every single push would be a "full" push, copying all $s$ elements: $1 + 2 + 3 + \dots + n \approx n^{2} /2$ total copies — quadratic! Doubling instead makes the full-events get exponentially rarer as the vector grows, which is exactly what turns $O (n^{2})$ into $O (n)$ .

PICTURE. Two timelines of "when does a reallocation fire?" The +1 strategy fires constantly; the doubling strategy fires at $1, 2, 4, 8, 16, \dots$ — the gaps double each time.

Step 4 — List every expensive event

WHAT. Start from an empty vector and push $n$ elements. The reallocations (copies) happen exactly when size hits $1, 2, 4, 8, \dots, 2^{k}$ , where $2^{k}$ is the largest power of two that is $\leq n$ .

WHY. To add up the total cost, we must first enumerate every expensive moment and how much each one costs. A reallocation at capacity $m$ copies exactly $m$ elements (it carries the whole existing block).

PICTURE. A number line of pushes $1 \dots n$ . Amber spikes mark the reallocations; each spike is labelled with its copy cost ( $1, 2, 4, 8, \dots$ ). Everything between spikes is a flat run of cheap $O (1)$ pushes.

Step 5 — Sum the copy work (the geometric series)

WHAT. Total copy work across all reallocations: $T = i = 0 1 + i = 1 2 + i = 2 4 + \dots + i = k 2^{k} = \sum_{i = 0}^{k} 2^{i} .$

WHY this tool — the geometric sum? Each term is double the one before (constant ratio $2$ ). A sum where each term multiplies by a fixed number is a geometric series, and it has a famously clean closed form. We reach for it precisely because "each reallocation copies twice as much as the last" is a doubling pattern — the exact shape geometric series were invented to collapse.

PICTURE. The classic proof-without-words: stack bars of heights $1, 2, 4, 8, \dots, 2^{k}$ . The whole stack is one short of the next bar $2^{k + 1}$ . That single missing unit is the entire content of the closed form.

Step 6 — Bound it by $2 n$

WHAT. Replace the abstract $2^{k + 1} - 1$ with something in terms of $n$ : $T = 2^{k + 1} - 1 < 2^{k + 1} = 2 \cdot 2^{k} \leq 2 n .$

WHY. We defined $k$ so that $2^{k} \leq n$ (Step 4). Multiply both sides by 2: $2^{k + 1} \leq 2 n$ . And dropping the $- 1$ only makes the left side larger, so the strict inequality holds. This converts "sum over reallocations" into a plain bound the reader can feel: all the copying together is less than twice $n$ .

PICTURE. Two bars side by side: the total copy work $T$ , and the ceiling $2 n$ . $T$ never touches the ceiling, no matter how big $n$ grows.

Step 7 — Divide out: the amortised cost

WHAT. Amortised analysis asks: "spread the total cost evenly across all $n$ operations, what does each one cost on average?" $amortised cost per push = \frac{total work}{n} = \frac{< 3 n}{n} < 3 = O (1) .$

WHY divide? Amortised does not mean "every push is cheap" — one push (a reallocation) really is $O (n)$ . It means the bill split across the whole sequence is constant. Dividing the total by the count is exactly that split.

PICTURE. A jagged red line of the true per-push cost (mostly at height 1, with tall spikes at powers of two) and a flat amber line at height $\approx 3$ — the average. The spikes poke above the flat line but the calm valleys pull the average back down.

Step 8 — The degenerate and edge cases

WHAT & WHY. A derivation is not finished until every corner is covered.

$n = 0$ (empty): no pushes, no reallocations, $T = 0$ . The formula gives $\sum_{i = 0}^{⌊ l o g_{2} 0 ⌋}$ which is an empty/undefined sum — we simply treat it as $0$ . No contradiction: zero work for zero pushes.
$n = 1$ (single push): $k = 0$ , one reallocation copying $2^{0} = 1$ element... actually the first push into a fresh empty vector allocates but copies nothing (there is nothing to copy). So real implementations do even better than the bound — the bound is an upper limit, never violated.
reserve(n) first: if you tell the vector its final size up front, it allocates once and every push is the cheap branch — zero reallocations. This is the fix the parent note's mistake box points at.
Growth factor $\neq = 2$ (e.g. $1.5 \times$ in some libraries): the ratio $r > 1$ still gives a geometric series $\sum r^{i} = \frac{r ^{k + 1} - 1}{r - 1}$ , still $O (n)$ total, still $O (1)$ amortised. Any constant factor $> 1$ works — only "+1 growth" (ratio effectively $1$ ) breaks it back to $O (n^{2})$ .

PICTURE. Four mini-panels: empty, single push, pre-reserved (flat, no spikes), and $1.5 \times$ growth (spikes closer together but still exponentially sparse).

The one-picture summary

Everything above compressed: the per-push cost curve (spikes at powers of two), the running total rising along a line bounded by $2 n$ , and the flat amortised average — all on one blueprint.

Recall Feynman retelling — say it like you'd explain to a friend

A vector is a box with spare room. Adding a thing is usually free — you just drop it in a spare slot. But when the box fills up, you have to buy a box twice as big and carry everything over. That carrying is slow. Here's the trick: because you double every time, the box fills up half as often as it grew last time — the slow moves get rarer and rarer. If you add up ALL the carrying you ever do, it's less than twice the number of things you stored. Split that bill across every "add", and each add costs a tiny constant on average. That's what "amortised $O (1)$ " means: rare expensive moves, paid for by a crowd of cheap ones. And if you knew the size all along, just reserve it — then you never carry anything at all.

Recall Quick self-test

Why does growing by "+1" each time give $O (n^{2})$ total? ::: Every push would be a "full" push copying all $s$ elements, so total $= 1 + 2 + \dots + n \approx n^{2} /2$ . What is $⌊ lo g_{2} 100 ⌋$ and what does it mean here? ::: $6$ — the last reallocation before reaching 100 elements copied $2^{6} = 64$ items. A single push_back worst case is what complexity? ::: $O (n)$ — when it triggers a reallocation and copies the whole array. The closed form of $1 + 2 + 4 + \dots + 2^{k}$ ? ::: $2^{k + 1} - 1$ . How do you avoid all reallocations when the size is known? ::: Call reserve(n) first.

Prerequisites revisited: Amortised analysis, Big-O notation, and the memory-layout intuition from Cache locality all feed this result. Back to the parent: STL containers overview.