STL containers — vector, list, deque, array, set, multiset, map, multimap, unordered_map, unordered_set: Worked examples

The scenario matrix

Before any code, here is the full list of case classes container problems come in. Every worked example below is tagged with the cell it covers, and together they cover the whole table.

#	Case class	What makes it tricky	Winning container	Example
A	Random access by index, read-heavy	need $O (1)$ `v[i]`	`vector` / `array`	Ex 1
B	Insert/erase in the middle, many times	shifting cost	`list`	Ex 2
C	Insert at both ends (front + back)	front push on vector is $O (n)$	`deque`	Ex 3
D	Unique keys, fast lookup, order irrelevant	hashing	`unordered_set/map`	Ex 4
E	Keys must stay sorted / range queries	tree ordering	`map` / `set`	Ex 5
F	Duplicate keys must survive	set drops dupes	`multiset` / `multimap`	Ex 6
G	Degenerate / zero input (empty, size 0, single element)	UB traps	any — care needed	Ex 7
H	Limiting behaviour — capacity growth, worst-case collision	amortised vs worst	`vector` / `unordered_map`	Ex 8
I	Real-world word problem — pick from a paragraph	translating needs → costs	mixed	Ex 9
J	Exam twist — iterator invalidation / erase-during-loop	silent dangling bug	vector/map	Ex 10

Recall Quick self-test before you read on

Which container for "front and back inserts, both cheap"? ::: deque Which containers keep unique keys and silently drop duplicates? ::: set and map both enforce unique keys (use multiset/multimap to keep duplicates) erase(value) on a multiset removes how many? ::: all matching copies

Cell A — Random access, read-heavy

Worked example Ex 1 — Sum every 3rd element of a big list of numbers

You have $1 0^{6}$ integers and must repeatedly read element at index $k$ . Which container, and what is the total cost of reading $m$ arbitrary indices?

Forecast: guess the container and whether one read is $O (1)$ or $O (n)$ before reading on.

Choose vector<int>. Why this step? Contiguous memory means the address of element $k$ is base + k*sizeof(int) — one multiply and one add, no walking. That is $O (1)$ per read.
Read indices $0, 3, 6, \dots$ Each v[k] is independent $O (1)$ .
Total for $m$ reads $= m \cdot O (1) = O (m)$ .

vector<int> v(1000000);
long long s = 0;
for (size_t k = 0; k < v.size(); k += 3) s += v[k];

Verify: if instead we used a list, each v[k] needs walking $k$ nodes, so reading indices $0, 3, \dots, 3 (m - 1)$ costs $0 + 3 + 6 + \dots = 3 \cdot \frac{m ( m - 1 )}{2} = O (m^{2})$ . For $m = 1000$ that is $\approx 1, 498, 500$ node-hops versus $1000$ for vector. Vector wins by design.

Cell B — Insert/erase in the middle repeatedly

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

Worked example Ex 2 — Maintain a playlist where songs get inserted mid-list constantly

You already hold an iterator to the insertion spot and do $n$ inserts there. Compare vector vs list.

Forecast: how many element-moves does each insert cost in each container?

vector middle-insert. Why this step? To open a gap at position $p$ , every element after $p$ shifts right by one — up to $n$ moves. Look at the top row of the figure: the pink block slides everything.
list middle-insert. Why this step? A doubly-linked node just relinks 4 pointers (new node's prev/next, and the two neighbours). Bottom row of the figure: nothing else moves. That is $O (1)$ .
Do it $n$ times. vector $= O (n)$ each $\Rightarrow O (n^{2})$ total; list $= O (1)$ each $\Rightarrow O (n)$ total (given the iterator).

list<string> playlist;
auto it = playlist.begin();      // already at the spot
playlist.insert(it, "newSong"); // O(1) pointer surgery

Verify: for $n = 10, 000$ middle inserts, vector does $\sim \frac{n ^{2}}{2} = 5 \times 1 0^{7}$ moves; list does $\sim 4 n = 40, 000$ pointer writes. The ratio $\approx 1250 \times$ — matches the $O (n^{2})$ vs $O (n)$ prediction.

Cell C — Insert at both ends

Worked example Ex 3 — Sliding window / double-ended queue of tasks

You push new tasks to the back and pop finished ones from the front, millions of times.

Forecast: why is vector a trap here?

Reject vector. Why this step? vector has no cheap front operation — insert(begin(), x) shifts all $n$ elements right, $O (n)$ . Doing that per task is $O (n^{2})$ .
Choose deque. Why this step? A deque is a map of fixed-size chunks (see figure). Growing at the front adds a chunk before the first, growing at the back adds one after — both amortised $O (1)$ , and index math across chunks still gives $O (1)$ random access.
Operate.

deque<int> q;
q.push_back(x);   // amortised O(1)
q.push_front(y);  // amortised O(1)
int a = q.front(); q.pop_front();  // O(1)

Verify: processing $n$ tasks with front+back ops costs $O (n)$ on a deque vs $O (n^{2})$ on a vector-with-front-inserts. For $n = 100, 000$ : deque $\sim 2 \times 1 0^{5}$ ops, vector $\sim 5 \times 1 0^{9}$ — the deque is the only viable choice.

Cell D — Fast lookup, order irrelevant

Worked example Ex 4 — "Have I seen this ID before?" across a stream

Stream of $N$ user IDs; for each, answer seen before? in $O (1)$ average.

Forecast: hash or tree? Why?

Choose unordered_set<long>. Why this step? You only need membership, never sorted order. A hash function scatters IDs into buckets, giving average $O (1)$ find/insert. A tree (Red-black trees) would cost $O (lo g n)$ per query — needlessly slower here.
Query then insert.

unordered_set<long> seen;
for (long id : stream) {
    if (seen.count(id)) reportDuplicate(id);
    seen.insert(id);          // O(1) average
}

Know the worst case. Why this step? The $O (1)$ is only an average, and it assumes a good hash function that spreads keys evenly. If many IDs collide into one bucket — a bad hash, or an adversary who picks colliding keys — the bucket becomes a long chain and each lookup degrades to $O (n)$ (see Hash functions and collisions). So $N$ queries are $O (N)$ average but $O (N^{2})$ worst case. A set gives a guaranteed $O (lo g n)$ regardless.

Verify: total average cost $= N \cdot O (1) = O (N)$ . A set would be $O (N lo g N)$ . For $N = 1024$ , $lo g_{2} N = 10$ , so the tree does $\sim 10 \times$ more comparisons on average — hashing wins when order isn't needed and the hash is good; when you cannot trust the hash, prefer the tree's worst-case guarantee.

Cell E — Sorted keys / range queries

Worked example Ex 5 — Leaderboard: names sorted, plus "who scored between 40 and 60?"

Need alphabetical iteration and range queries.

Forecast: why does unordered_map fail this one?

Choose map<string,int> (or set). Why this step? Tree-based ⇒ keys stay sorted, so iteration is alphabetical for free, and lower_bound/upper_bound give $O (lo g n)$ range queries. unordered_map has no order and no lower_bound.
Range query with bounds.

map<string,int> board = {{"banana",3},{"apple",5},{"cherry",4}};
for (auto& [k,v] : board) cout << k << " " << v << "\n";
// prints apple 5, banana 3, cherry 4  (alphabetical)

Verify: iteration order is apple, banana, cherry — strictly sorted, guaranteed by the BST invariant. Search per key is $O (lo g 3)$ . An unordered_map would print in unpredictable bucket order, failing the requirement.

Cell F — Duplicates must survive

Worked example Ex 6 — Keep every score, allow repeats, pop the smallest one at a time

Insert $50, 50, 20$ ; get the smallest; remove exactly one smallest.

Forecast: what does erase(20) do vs erase(begin())? Guess before step 3.

Choose multiset<int>. Why this step? A set would collapse the two 50s into one. multiset keeps duplicates, stays sorted, so begin() is always the minimum in $O (1)$ .
Read the minimum with *scores.begin().
Remove ONE smallest with erase(iterator) — not erase(value).

multiset<int> scores;
scores.insert(50); scores.insert(50); scores.insert(20);
int smallest = *scores.begin();     // 20
scores.erase(scores.begin());       // removes ONE 20 -> {50,50}
// scores.erase(50) would delete BOTH 50s

Verify: after insert(50),insert(50),insert(20) size $= 3$ , begin() $= 20$ . After erase(begin()) size $= 2$ and contents {50,50}. If we then call erase(50) size drops to $0$ (both removed) — confirming value-erase kills all matches.

Cell G — Degenerate / zero input

Worked example Ex 7 — The empty-and-single-element traps

What must you check before calling front(), back(), begin() on possibly-empty containers?

Forecast: what does v.front() return on an empty vector? (Trick: it isn't $0$ .)

Empty vector front() is Undefined Behaviour. Why this step? front() returns *begin(), but on an empty container begin() == end(), so you dereference a non-element. Always guard with !v.empty().
Empty map [] inserts. Why this step? m[k] on a missing key default-constructs and inserts it — so a read can silently grow the map. Use m.find(k) or m.count(k) when you only want to check.
Single element: begin() and --end() point to the same element; erasing it leaves the container empty and any held iterator dangling.

vector<int> v;                  // size 0
// int x = v.front();           // UB — do NOT
if (!v.empty()) use(v.front()); // safe
 
map<string,int> m;
if (m.count("x")) use(m["x"]);  // avoids accidental insert

Verify: v.size()==0 and v.empty()==true for the default-constructed vector — the guard is exactly what stops the UB. On the empty map, m.count("x")==0, so the branch is skipped and no phantom key is created; had we written m["x"], m.size() would have jumped to $1$ .

Cell H — Limiting behaviour (capacity growth & worst case)

Worked example Ex 8 — How many reallocations for a million push_backs?

Starting empty, capacity doubles each time it fills. Push $1 0^{6}$ elements. How many resizes, and how much total copy work?

Forecast: guess "number of resizes" and "total copies" as multiples of $n$ .

Resizes happen at sizes $1, 2, 4, \dots, 2^{k}$ (see the staircase in the figure — each riser is a resize, flat tread is cheap pushes). For $n = 1 0^{6}$ , the largest power of two $\leq n$ is $2^{19} = 524288$ , so $k = 19$ ⇒ 20 resizes ( $2^{0}$ through $2^{19}$ ).
Total copy work $= \sum_{i = 0}^{19} 2^{i} = 2^{20} - 1 = 1, 048, 575 < 2 n$ . Why this step? Geometric series $1 + 2 + \dots + 2^{k} = 2^{k + 1} - 1$ ; see Amortised analysis.
Amortised per push $= O (1)$ . Why this step? Two costs add up over $n$ pushes: (a) the cheap pushes — each of the $n$ elements is written into its slot exactly once, costing $n$ ; (b) the copy work from resizes, which we just bounded by $< 2 n$ . So total work $< 2 n + n = 3 n$ , and dividing by $n$ pushes gives $< 3 = O (1)$ average per push. The contiguous block also keeps those copies cache-friendly.

vector<int> v;
v.reserve(1000000);   // ONE allocation, ZERO resizes — best practice
for (int i = 0; i < 1000000; i++) v.push_back(i);

Verify: for the $2 \times$ model, copies without reserve $= 2^{20} - 1 = 1, 048, 575$ , which is $< 2 \times 1 0^{6}$ ; adding the $n = 1 0^{6}$ cheap writes gives $< 3 \times 1 0^{6}$ total. For a general factor $g$ , total copies $= \frac{g}{g - 1} n$ : at $g = 2$ that is $2 n$ , at $g = 1.5$ it is $3 n$ — both $O (n)$ . Worst-case contrast: an adversarial hash can force every key into one bucket, turning unordered_map find into $O (n)$ — the limiting case the average $O (1)$ hides.

Cell I — Real-world word problem

Worked example Ex 9 — Word-frequency report, printed alphabetically

Read $N$ words, count each, then print counts in alphabetical order. Pick the container from the paragraph's needs.

Forecast: one container or two? Hash for counting, tree for printing?

Needs list: (a) fast count-up per word → favours hash; (b) sorted output → favours tree. Why this step? Translating each sentence clause into a cost requirement is the whole skill.
Simplest correct choice: map<string,int>. Why this step? One structure satisfies both — $O (lo g n)$ counting and free sorted iteration. Total $O (N lo g D)$ for $D$ distinct words.
Faster alternative: unordered_map to count in $O (N)$ , then copy keys to a vector and sort in $O (D lo g D)$ . Why this step? When $N ≫ D$ (many repeats of few distinct words), the $O (N)$ hash counting beats the map's $O (N lo g D)$ , and we pay the sorting cost only once over the $D$ distinct keys, not on every insert (see STL algorithms).

map<string,int> freq;
for (auto& w : words) freq[w]++;     // counts, stays sorted
for (auto& [w,c] : freq) cout << w << " " << c << "\n";  // alphabetical

Verify: for {"pear","apple","apple"}, freq holds apple->2, pear->1, printed as apple 2 then pear 1. Sum of counts $= 3 = N$ — every word accounted for.

Cell J — Exam twist: iterator invalidation

Worked example Ex 10 — Erase all even numbers from a container mid-loop

Naively erasing inside a range-for silently corrupts iteration. Fix it for vector and for map.

Forecast: what breaks if you write erase(it) and then ++it in the same loop turn?

The trap. Why this step? erase(it) on a vector invalidates it (and everything after it, because elements shift). Using or ++-ing the old it afterwards is UB.
Fix — use erase's return value. Why this step? erase returns a valid iterator to the element after the removed one, so you advance correctly instead of touching the dead iterator.

vector<int> v = {1,2,3,4,5,6};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);   // erase returns next valid it
    else ++it;
}
// v == {1,3,5}

For map, erasing one node does not invalidate the other nodes (the tree's remaining links stay put) — but the erased iterator itself dies. Why this step? So you still must not ++ the dead iterator; capture erase's return value (C++11 and later) or use the classic post-increment idiom m.erase(it++):

map<int,int> m = {{1,1},{2,2},{3,3},{4,4}};
for (auto it = m.begin(); it != m.end(); ) {
    if (it->first % 2 == 0) it = m.erase(it);  // returns next valid it
    else ++it;
}
// keys left: {1,3}

Verify: vector result is {1,3,5} (size $3$ , sum $9$ ); map keys left are {1,3} (size $2$ ). Both match the "remove evens" spec. See Iterators in C++ for the full invalidation rules per container.

Recall Final scenario check

Front + back cheap → ::: deque Sorted iteration for free → ::: map / set erase(it) returns → ::: a valid iterator to the next element Empty-vector front() → ::: undefined behaviour — guard with !empty()