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

Nothing here assumes you have seen C++ before. We start at the level of "what is a box in memory" and climb, one rung at a time, to the vocabulary the parent topic uses freely.

1. A memory cell, and what "contiguous" means

Before any container, there is memory. Picture computer memory as an infinitely long street of identical houses. Each house is one byte — the smallest addressable unit — and has an address, its house number.

Here is the subtlety the metaphor must not hide: one data value can occupy several bytes. A small integer might fit in 4 bytes, a large one in 8. So a value is not always one house — it may be a block of neighbouring houses. We call the number of bytes one element occupies its size, written $s$.

WHY the topic needs this: the parent note says a vector gives "$O(1)$ random access because index math gives the address." That is meaningless until you can see why. With the three symbols above, element $i$ begins at

$\text{address}(i)=B+i\times s.$

Read it in words: start at the base $B$, then skip past $i$ whole elements, each $s$ bytes wide. That is one multiply ($i\times s$) and one add — a fixed amount of work no matter how big $i$ is. That is what "jump straight to any element" means, and it only works because the elements are in a row.

2. What "$O(\cdot )$" actually says — Big-O from zero

The parent note is drenched in $O(1)$, $O(n)$, $O(\log n)$. These are not numbers. They answer one question: "as the amount of data grows, how does the work grow?"

Read the figure as three growth shapes, worst (slowest) at top:

• $O(1)$ — flat. Work does not grow at all when $n$ grows. "Jump to element $i$" from Section 1 is $O(1)$: one multiply-add whether $n$ is 10 or 10 million.
• $O(\log n)$ — barely rising. Doubling $n$ adds only a constant amount of work. This is what tree containers (set, map) give — see Section 6.
• $O(n)$ — straight line. Double the data, double the work. "Walk through every element looking for a value" is $O(n)$.

3. "Amortised" — the average over a run

The parent claims push_back is amortised $O(1)$. That word "amortised" is doing heavy lifting.

WHY the topic needs this: without "amortised", you would look at the occasional $O(n)$ copy during a resize and wrongly conclude push_back is slow. The full proof lives in Amortised analysis; the parent note derives the $<3n$ total there.

4. Pointers and nodes — the linked world

Section 1 gave us the contiguous world. The other half of the STL — list, and the internals of tree containers — lives in the linked world, and its atom is the pointer.

Look at the figure. The nodes are scattered across memory — node A at 1000, node B at 5000, node C at 2000 — but the red next arrows stitch them into an order. This is the key contrast with Section 1:

• Contiguous array: neighbours are neighbours in memory ⇒ jump to index $i$ instantly, but inserting in the middle means physically shifting every later house over.
• Linked nodes: neighbours are wherever they happen to be; you find them only by following pointers ⇒ no jump-to-index, but inserting is just rewriting two arrows ($O(1)$).

5. Keys, values, and "sorted order"

The parent splits containers into sequence (ordered by insertion) and associative (organised by value). To read that, you need three words.

6. Trees and hash tables — the two ways to organise by key

Two engines power the associative containers. You need a mental picture of each.

Trace the red path in the figure searching for 40: start at 50 (40 < 50 → go left), reach 30 (40 > 30 → go right), reach 40 ✓. Three comparisons out of seven nodes. Each level halves what is left — the same halving that makes binary search $O(\log n)$.

7. Iterators — the universal "position marker"

Finally, the word every worked example uses: iterator.

The parent's list example — L.insert(it, x) is $O(1)$ — only works because it already holds the position. Getting the iterator to that spot may itself cost $O(n)$. That distinction (holding a position vs. finding it) explains half the "gotchas" in the cheat-sheet. Deep dive: Iterators in C++, and the functions that consume them: STL algorithms.

How the foundations feed the topic

Equipment checklist