Visual walkthrough — Iterators — input, output, forward, bidirectional, random access, contiguous

Everything here builds on the parent topic. If a word here is new, we define it the moment it appears.

---

Step 1 — A pointer is a finger on a row of boxes

WHY start here? Because every iterator is, by the parent's own words, a generalized pointer. If we understand exactly which powers a raw pointer has, we can later ask, one at a time, "which of these powers can a weird container still afford?" That question generates the entire hierarchy.

PICTURE — the finger, the box it opens, and the slide-right move:

See Pointers and pointer arithmetic for the raw-pointer version of all this.

---

Step 2 — Strip powers away: the one-way stream (Input & Output)

WHY does this matter? It shows that not every source can afford both atomic powers fully. The stream keeps ++ (advance to the next drop) but cripples it: advancing destroys the old position. And it splits * into two mutually exclusive halves:

• Input iterator: you may only read the drop — x = *it. (An input stream.)
• Output iterator: you may only write a drop — *it = x. (An output stream/printer.)

The word for "you may pass each spot only once" is single-pass. A copy of the iterator does not save the old spot, because the underlying stream already moved.

PICTURE — one drop caught, then gone; note there is no arrow pointing left:

---

Step 3 — Restore memory of the past: multi-pass (Forward)

This new power is called multi-pass: two iterators to the same element behave identically, and re-traversal is allowed. This is the essence of the Forward category.

WHY is this a genuinely new rung? Because in Step 2 a copy was worthless (the stream moved). Here a copy is a real bookmark. That single difference — does a saved copy stay valid? — is exactly the line between Input/Output and Forward.

PICTURE — a chain of scattered boxes joined by "next" arrows; a bookmark copy revisits the same box:

---

Step 4 — Follow the chain backwards too (Bidirectional)

WHY only now? A singly-linked chain (Step 3) cannot offer --it cheaply — there is no back-link to follow; you'd have to restart from the front, which is $O(n)$. Add the back-pointer and --it becomes $O(1)$. So the container's physical layout (does each node know its predecessor?) decides whether Bidirectional is affordable.

PICTURE — the same chain, now with both forward and backward links; the finger can go either way:

---

Step 5 — Elements on a regular grid: the jump (RandomAccess)

WHY does regularity unlock all this at once? Every one of these is arithmetic on an index. The moment the container can hand you an index-to-position map that is $O(1)$, addition, subtraction, indexing, and ordering all fall out together. That is why they enter as a single bundle.

PICTURE — a finger leaping over $n$ boxes in one green arc, plus two fingers whose gap is measured:

---

Step 6 — One unbroken block of memory: the C-pointer promise (Contiguous)

WHY is this stronger than RandomAccess? With deque, element 5 and element 6 might live in different chunks, so their memory addresses are not related by +1. The distance in index is $O(1)$ to compute, but the distance in bytes is unpredictable. Contiguous forbids the gaps, giving:

$\underset{\text{address of element }n\text{ ahead}}{\underbrace{\&\ast (it+n)}}=\underset{\text{start address}}{\underbrace{\&\ast it}}+\underset{\text{times element size}}{\underbrace{n}}$

Every symbol: &*it takes the iterator, opens its box (*), and asks for that box's real address (&); the equation says stepping $n$ ahead moves the address by exactly $n$ elements — a straight line in memory. This is what lets you pass &v[0] to a C API expecting a bare double*.

PICTURE — deque's gappy chunks (addresses jump) versus vector's solid block (addresses march):

---

Step 7 — The degenerate cases (never leave a scenario unshown)

PICTURE — the empty range where begin and end coincide, and the count-driven output with no sentinel:

---

Step 8 — How the compiler reads this ladder: tag dispatch

WHY tags and not an if? An if (is_random_access) would cost a runtime check and would try to compile it += n even for a list (which doesn't support it → error). The tag lets the compiler discard the illegal branch entirely: zero runtime cost, only legal code compiled. This is the whole payoff of the hierarchy.

PICTURE — one call fanning out to the correct overload by tag type:

More on the machinery: Templates and Tag Dispatch and iterator_traits and type introspection. The modern face of all this is the Ranges library (C++20).

---

The one-picture summary

Recall Feynman retelling — say it in plain words

Picture a finger on a shelf of boxes. Open a box (*), slide right (++) — that's a pointer, and that's the seed of everything. Now weaken it: a stream only lets you catch each item once as it flows past — read-only or write-only, single-pass. That's Input/Output, the floor. Put the items in real memory and let a saved bookmark stay valid — now you can revisit and re-read. That's Forward. Give each item a link to the one before it, and the finger can slide left. That's Bidirectional (--it). Space the items on a regular grid so their positions are computable, and the finger can leap $n$ boxes at once, measure gaps, and compare positions — all in one step. That's RandomAccess. Finally, forbid all gaps so the items sit in one solid block; then iterator math equals real address math and you can hand the start to a C function. That's Contiguous. The reason this ladder exists at all: each new power is only affordable if the container's physical layout supports it. And the compiler reads which rung you're on from a tiny empty tag, choosing the fastest legal code with zero runtime cost.

Recall

The single fact that generates the whole hierarchy is... ::: the container's physical memory layout — what it can do cheaply decides which powers it offers. The line between Input/Output and Forward is... ::: whether a saved copy of the iterator stays valid (multi-pass). The line between Bidirectional and RandomAccess is... ::: whether you can jump it+n in $O(1)$ instead of stepping $n$ times. The line between RandomAccess and Contiguous is... ::: whether &*(it+n) == &*it + n (one unbroken memory block). Tag dispatch picks the right overload at... ::: compile time, from the iterator's category tag type — zero runtime cost.