The STL containers and their cost models

Lesson 12 showed how templates let one piece of code work for many types at zero runtime cost by stamping out a concrete version per type at compile time. The Standard Template Library's containers are that machinery's biggest payoff: ready-made, type-safe data structures. But a container is not a neutral box. Every one of them is a frozen pair of decisions you already learned to make by hand — who owns the elements (Lesson 07) and how they are laid out in memory (Lesson 08) — wrapped in a template. This lesson adds the one new idea that lets you choose between them on purpose: each container has a cost model, and the right choice is almost never the one your big-O intuition from a textbook would pick.

The thesis, here

A container's interface tells you what it can do; its layout tells you what it costs. vector, list, and map all "store a sequence of things," but they compile to wildly different machine behavior because they place memory differently — and on real hardware the placement, not the asymptotic complexity, usually decides the winner. Picking a container is the cost-model habit applied to a one-line decision you make dozens of times a day.

Linear position

Prerequisite: Lesson 08 (the cache, the cache line, why contiguous memory beats pointer-chasing, the ~1ns-hit-vs-~100ns-miss latency gap) and Lesson 12 (templates: a container is a class template instantiated for your element type). You also lean on Lesson 04's invalidation preview and Lesson 07's ownership.
New capability: choose the right STL container for a given access pattern by reasoning about its memory layout, per-operation big-O and its real cache cost, and its iterator/reference invalidation rules — not by reflex.

The plan

Six moves. (1) Why a container is an ownership + layout decision. (2) std::vector as the default, and the geometric-growth trick that makes push_back amortized O(1). (3) The fixed and segmented siblings: array and deque. (4) std::list, and the worked timing argument for why it is almost always the wrong choice. (5) Ordered map vs hashed unordered_map. (6) Iterator and reference invalidation, per container — then the full cost table.

1 · A container is an ownership + layout decision

You already know how to store a sequence of integers three different ways. You can put them in one contiguous block and walk it with pointer arithmetic (Lesson 03). You can put each one in its own heap allocation and link them with pointers. You can keep them sorted in a tree of nodes. Each choice owns its elements — when the structure dies, the elements die with it (Lesson 07) — and each chooses a layout that fixes its performance (Lesson 08). The STL containers are exactly these hand-rolled structures, written once as templates (Lesson 12) so they work for any element type and you never write the bookkeeping again.

So "which container?" is not a style question. It is the same question as "contiguous or pointer-chasing? owned where? freed when?" — the questions this series has been training. The container hides the bookkeeping, not the cost model. Your job is to read the cost model off the layout.

2 · std::vector — the default, and why

std::vector<T> is a dynamically-sized contiguous array: it owns one heap block holding its elements back-to-back, exactly like a C array but it manages the block for you. Make it your default and only switch when a measured reason appears. Two reasons it wins: contiguous layout means iterating it is the cache-friendliest access pattern there is (one cache line fetched, ~16 ints served — Lesson 08), and its memory management is genuinely cheap to amortize.

The key distinction is size vs capacity. Size is how many elements you have put in. Capacity is how many the current heap block can hold before it must be replaced. When you push_back and size would exceed capacity, the vector allocates a bigger block, copies (or moves — Lesson 06) the elements over, frees the old block, and continues. That reallocation is O(n). If it happened on every push_back, building an n-element vector would be O(n²).

Worked example — geometric growth and amortized O(1)

The trick is that capacity does not grow by one; it grows by a factor (typically ×2). Watch the capacity as we push 1, 2, 3, … onto an empty vector. Each "× reallocate" copies all current elements:

push size capacity event 1 1 1 reallocate, copy 0 -> cap 1 2 2 2 reallocate, copy 1 -> cap 2 3 3 4 reallocate, copy 2 -> cap 4 4 4 4 (fits — no realloc) 5 5 8 reallocate, copy 4 -> cap 8 6..8 (fit — no realloc) 9 9 16 reallocate, copy 8 -> cap 16 ...

To insert n elements, the total copying work is 1 + 2 + 4 + 8 + … + n < 2n. So n pushes cost < 2n copies total: O(n) total, or O(1) amortized per push — "amortized" meaning the rare expensive reallocation, spread across the many cheap pushes that preceded it, averages out to constant. Doubling is what makes the geometric series sum to a constant multiple of n; growing by a fixed +k would give O(n²). If you know the final size, call v.reserve(n) once to set capacity up front and pay zero reallocations.

std::vector<int> v;
v.reserve(1000);          // capacity = 1000 now; size still 0
for (int i = 0; i < 1000; ++i)
    v.push_back(i);       // no reallocation happens — all 1000 fit
v.size();                 // 1000
v.capacity();             // >= 1000
v[42];                    // O(1) random access — pointer + offset, no check

3 · std::array and std::deque — the siblings

std::array<T, N> is a fixed-size array whose size N is a compile-time constant. It is not a heap allocation at all — it lives wherever you put it, typically on the stack (Lesson 02), so creating it is nearly free (no new). Use it when the count is known and small; it is the zero-overhead replacement for a C array T[N], with a safe interface bolted on.

std::deque<T> (double-ended queue) is segmented: a sequence of fixed-size contiguous chunks tracked by an index. It gives you O(1) push_back and O(1) push_front, and (unlike vector) pushing at either end never moves the existing elements. The price is that the storage is not one contiguous block, so iteration is slightly less cache-friendly than vector and you cannot get a single pointer to all of it. Reach for it specifically when you need cheap growth at the front; otherwise prefer vector.

4 · std::list — and why it is almost always wrong

std::list<T> is a doubly-linked list: each element is its own separate heap allocation (a node) holding the value plus two pointers, to the previous and next nodes. Its textbook selling point is O(1) insertion and deletion anywhere, given an iterator to the spot — you just rewire four pointers, no shifting. By the asymptotic table, that crushes vector's O(n) middle-insert (which must shift every following element). And yet on real hardware list is almost always the wrong choice. This is the cheque from Lesson 08 coming due.

Worked example — why O(n) vector beats O(1) list

The nodes of a list are scattered across the heap, so visiting them is pointer-chasing: every next step jumps to an unpredictable address the CPU could not prefetch — a likely cache miss at ~100ns (Lesson 08). A vector is one contiguous block, so walking it is ~16 elements per ~1ns cache-line fetch and the prefetcher sees the linear pattern coming.

Take "insert into a sorted sequence of n ints." Both must first find the spot. For the vector, find + shift is one linear pass over contiguous memory — n cheap cache-friendly element touches. For the list, find is n cache-missing pointer hops; the O(1) rewire that follows is irrelevant because the search already paid ~100× per step. The "expensive" O(n) shift on the vector moves bytes the CPU has already pulled into cache; the "free" O(1) list insert sits at the end of a ~100ns-per-hop walk. Measured, vector wins for n into the thousands and beyond. The big-O hides the constant, and on modern hardware the constant is the cache-miss latency — which dominates.

So when is list right? When elements are large and expensive to move (so shifting genuinely hurts), and you hold iterators that must stay valid across insertions (see §6), and you splice whole sub-ranges between lists in O(1). That is a narrow, real, but rare profile. The default answer is: don't reach for list; reach for vector and measure before believing the asymptotics.

5 · std::map vs std::unordered_map — ordered tree vs hash table

Both are associative containers: they store key→value pairs and let you look up by key. They differ in layout and therefore in cost and in what guarantees they give.

std::map — balanced BST

A balanced binary search tree (typically a red-black tree) of separately-allocated nodes. Keys are kept sorted, so iteration visits them in order. Lookup, insert, erase are all O(log n) — but each step is a pointer-chase to another node (cache misses, like list). Needs operator< on the key. Use when you need ordering: range queries, "next key after k," in-order traversal.

std::unordered_map — hash table

A hash table: keys are hashed into buckets. Lookup, insert, erase are O(1) average (O(n) worst case, on pathological collisions or a bad hash). Iteration order is unspecified. Needs std::hash + operator== on the key. Use when you only need "is k present / give me k's value" and don't care about order — usually faster than map in practice.

The decision rule: if you need keys in sorted order or range queries, use map; otherwise default to unordered_map for the better average lookup. Note both store nodes out-of-line, so neither is cache-friendly the way vector is — for small collections, a sorted vector of pairs searched with std::lower_bound (Lesson 14) often beats both.

6 · Iterator and reference invalidation

Lesson 04 previewed a hazard: a pointer, reference, or iterator into a container can become dangling if the container moves or frees the element it points at — a use-after-free waiting to happen. Now we can state the rules, because they fall straight out of each container's layout.

An iterator is a generalized pointer into a container (Lesson 14 develops this); a reference here means a T& or raw pointer to an element. Invalidation means that handle no longer points at a live element — using it afterward is undefined behavior. The layout dictates the rules: anything that moves elements invalidates handles to the moved ones.

The classic vector trap

std::vector<int> v = {1, 2, 3};
int& first = v[0];        // reference into the block
v.push_back(4);           // may exceed capacity -> REALLOCATE
std::cout << first;       // DANGLING: 'first' points at the freed old block — UB

If the push_back triggers a reallocation, the whole block moves and every iterator, reference, and pointer into the vector is invalidated. This is the price of contiguous storage: growth can relocate everything. The fix is reserve up front, or re-fetch the reference after modifying. list, by contrast, never moves a node — so it makes the opposite trade, which is exactly its narrow use case from §4.

7 · The cost model, in one table

Container	Layout	Key ops (big-O)	Invalidation on insert/grow	Reach for it when…
`vector`	one contiguous heap block	index O(1); push_back amortized O(1); middle insert/erase O(n)	realloc (grow past capacity) invalidates all iters/refs; erase invalidates from the point on	the default — sequential storage, fast iteration, random access
`array`	fixed, inline (usually stack)	index O(1); fixed size — no insert/erase	never resizes; no invalidation from size changes	count known at compile time; want a safe C-array
`deque`	segmented contiguous chunks	index O(1); push_back/push_front O(1); middle O(n)	push at ends invalidates iterators but not refs; middle ops invalidate	cheap growth at both ends (e.g. a queue)
`list`	scattered linked nodes	splice/insert/erase O(1) given an iterator; no random access; find O(n)	insert/erase invalidate only the erased element's handles	rarely — large elements + stable iterators + O(1) splice
`map`	balanced BST of nodes	lookup/insert/erase O(log n); ordered iteration	insert never invalidates; erase invalidates only the erased element	need keys kept sorted / range queries
`unordered_map`	hash table + buckets	lookup/insert/erase O(1) average, O(n) worst	rehash (on grow) invalidates iterators but not refs/pointers to elements	fast keyed lookup, order doesn't matter (the default map)

Common mistakes / failure modes

Picking list from the big-O table

"O(1) insert" looks great until you remember finding the spot is n cache-missing hops. On real hardware vector usually wins even at middle insertion. Measure, don't assume (§4).

Holding a reference across push_back

A growth reallocation moves the whole block and dangles every handle into it — silent UB. reserve first, or re-fetch after modifying (§6).

Not calling reserve in a hot loop

Without it, building a big vector pays log₂(n) reallocations and copies. One reserve(n) turns that into zero (§2).

Using map when you don't need order

O(log n) cache-missing pointer hops where unordered_map would give O(1). Default to unordered_map unless you need sorted keys (§5).

Checkpoint exercise

Try it

Write a program that pushes 1,000,000 ints onto an empty std::vector, printing capacity() only when it changes. Predict the sequence first (it should be the powers of two from §2, up to your library's growth factor) — then run it and confirm. Now reproduce the §6 dangling-reference bug: take int& r = v[0]; before the loop, read r after, and run under g++ -fsanitize=address. ASan should report a heap-use-after-free at the first reallocation. Finally, add v.reserve(1000000) before the loop and confirm capacity never changes and the bug disappears.

Where this points next

You can now choose a container by its cost model — but a container is only half of a useful program; you also need operations over the elements: sort them, find one, sum them, transform them. The STL's masterstroke is that those operations are written once, decoupled from any specific container, by talking to it only through iterators — the generalized pointers we just used to discuss invalidation. Lesson 14 develops the iterator as the abstraction that lets a single std::sort work on a vector, an array, or a sub-range, introduces the half-open range [begin, end), and shows C++20 ranges composing these into lazy pipelines — the same "compose small pieces" idea you'll meet again everywhere.

Takeaway

Every STL container is a frozen pair of decisions — who owns the elements (Lesson 07) and how they are laid out (Lesson 08) — wrapped in a template (Lesson 12), and each comes with a cost model you read off its layout. std::vector is the default: contiguous, cache-friendly, with amortized-O(1) push_back from geometric (×2) growth — but a growth reallocation invalidates every reference into it, so reserve when you can. array is fixed and stack-cheap; deque is segmented for O(1) growth at both ends; list is linked nodes that look great in big-O and lose on real hardware because pointer-chasing means cache misses, so an O(n) vector insert routinely beats an "O(1)" list one. map is an ordered O(log n) tree; unordered_map is an O(1)-average hash table and the right default when order doesn't matter. The whole lesson is one habit: the asymptote tells you the trend, but the layout — and the cache — tells you the cost.

Interview prompts

Why is vector::push_back amortized O(1) and not O(1) per call? (§2 — capacity grows by a factor (×2), so n pushes do < 2n total copies; the rare O(n) reallocation averaged over the cheap pushes is constant. Linear +k growth would be O(n²).)
Explain capacity vs size, and what reserve buys you. (§2 — size = elements present, capacity = block's room before it must be replaced; reserve(n) sets capacity up front, eliminating all reallocations and the references they would dangle.)
list has O(1) insertion and vector O(n) — why does vector usually win? (§4 — list nodes are scattered, so traversal/find is cache-missing pointer-chasing at ~100ns/hop; vector is contiguous and prefetchable, and you must find the spot first; the cache-miss constant dominates the asymptotics.)
When is std::list actually the right choice? (§4 — large, costly-to-move elements + iterators that must stay valid across inserts + O(1) splicing of sub-ranges between lists. Narrow and rare.)
map vs unordered_map — how do you choose? (§5 — need sorted keys / range queries / in-order iteration → map (O(log n) tree); only need keyed lookup, order irrelevant → unordered_map (O(1) average hash), the better default.)
Why can a reference into a vector dangle, but a reference into a list not? (§6 — vector growth reallocates and relocates the whole contiguous block, invalidating all handles; list nodes never move, so only the erased node's handles invalidate — the layout dictates the rule.)
You need a small key→value map of ~20 entries in a hot path — what's faster than both standard maps? (§5 — a sorted vector of pairs with std::lower_bound: contiguous and cache-friendly, beating the node-chasing of both map and unordered_map at small n.)