Iterators — input, output, forward, bidirectional, random access, contiguous: Worked examples

Before anything else, two words we lean on constantly:

The scenario matrix

Every iterator exercise is one of these cells. We will hit each cell with a labelled example. In the "Negative move" cell we require an iterator that can step backward — that means the bidirectional, random access, or contiguous category (the three that define --it).

Cell	What makes it special	Degenerate / limit inside it
A. Positive move, random access	`it += n`, one $O (1)$ jump	`n = 0` (no move)
B. Positive move, bidirectional	must loop `++it`, $O (n)$	reaching `end()` exactly
C. Negative move	`--it`, legal only on bidirectional / random access / contiguous	must not step before `begin()`
D. Single-pass input	read once, no going back	copy-then-advance invalidates the other
E. Output only	write-only, no `==`, no end	knowing how many to write
F. Contiguous vs merely random	`&(it+n) == &it + n`	`deque` breaks it
G. Empty / one-element range	`begin() == end()`	distance $= 0$ ; `--end()` illegal
H. Word problem	pick the minimum category	over-constraining is a design bug
I. Exam twist	which line fails to compile & why	tag-dispatch reasoning

Example 1 — Cell A: positive jump on a `vector` (and the `n = 0` limit)

Worked example Statement

std::vector<int> v{10, 20, 30, 40, 50};
auto it = v.begin();
std::advance(it, 3);      // move 3 forward
int a = *it;
std::advance(it, 0);      // move 0 — degenerate
int b = *it;

What are a and b?

Forecast: guess both values before reading on.

v.begin() points at index 0, value 10. Why this step? Every walk needs a known starting anchor; begin() is index 0 by definition.
advance(it, 3) on a random-access iterator becomes it += 3 — a single $O (1)$ jump to index 3. Why this step? The parent's tag dispatch picks the random_access overload for vector. Because a vector is one flat block, address arithmetic finds index 3 without touching indices 1 or 2 — that is why the cost stays constant ( $O (1)$ ) no matter how big the vector is. Index $0 + 3 = 3$ , value 40. So a = 40.
advance(it, 0) moves zero steps — the loop body never runs / it += 0 is a no-op. Why this step? The degenerate n = 0 must leave the iterator exactly where it was; b = *it = 40.

Verify: index arithmetic $0 + 3 + 0 = 3$ ; v[3] = 40, so a == b == 40. Distance from begin() to final it is 3. ✓

Example 2 — Cell B + G limit: walking a `list` to `end()` exactly

Worked example Statement

std::list<int> L{7, 8, 9};      // 3 elements
auto it = L.begin();
std::advance(it, 3);            // land exactly on end()
bool atEnd = (it == L.end());

Is it == L.end() true, and how many ++ operations actually ran?

Forecast: guess the number of ++ calls and the boolean.

list iterators are only bidirectional, so advance picks the looping overload: while(n--) ++it;. Why this step? A linked list has no contiguous block, so there is no +=; you must physically hop node by node — and since moving $n$ steps costs $n$ separate hops, the work grows in step with $n$ : this is list's $O (n)$ (linear) reality.
Loop runs for n = 3: ++it executes 3 times, landing one past the last element. Why this step? A container of size 3 has valid positions $0, 1, 2$ and the sentinel end() at "position 3". Stepping 3 times from begin() reaches exactly end().
it == L.end() is true. Why this step? This is the limit case: end() is the legal stopping point. Reading *it here would be undefined, but comparing is fine.

Read the figure like this: the three mint boxes on the bottom row are the real elements at positions 0, 1, 2 holding 7, 8, 9. The butter box on the far right, labelled end() at position 3, is the sentinel — notice it has no value inside, which is your visual reminder that dereferencing it is illegal. The lavender arrow dropping onto position 0 is where begin() starts. Now count the three curved coral arrows across the top: each is one ++. Trace them left to right and watch the third arrow land squarely on the empty end() box — that landing is the whole answer. It shows both that exactly three ++ calls ran (three arrows) and why atEnd is true (the last arrow reaches the sentinel, not past it).

Figure — Iterators — input, output, forward, bidirectional, random access, contiguous

Verify: number of ++ calls $= 3 =$ size of L; distance begin()→end() equals size, so atEnd == true. ✓

Example 3 — Cell C: negative move on `bidirectional`, guarding `begin()`

Worked example Statement

std::set<int> s{5, 15, 25, 35};   // sorted: 5 15 25 35
auto it = s.end();
std::advance(it, -2);             // step back twice
int val = *it;

What is val?

Forecast: which element do two backward steps from end() land on?

set is bidirectional, so negative n picks while(n++) --it;. Why this step? Only bidirectional-or-better iterators define --. A std::set is stored as a balanced binary search tree, and --it walks to the in-order predecessor node. That walk may climb up or down the tree, so its worst-case cost is proportional to the tree height, which is $O (lo g n)$ for a balanced tree — cheap, but not the $O (1)$ that a vector gives. (A full front-to-back traversal visits every node exactly once, so it still totals $O (n)$ ; the point is a single -- is bounded by tree height, not constant.) Either way -- is legal here, which is all Cell C needs.
end() is one past the last element 35. First --it lands on 35. Why this step? You must never dereference end(), but you may decrement it — the first -- moves onto the real last element.
Second --it lands on 25. Why this step? Two backward steps from the sentinel: 35 → 25. So val = 25.
Degenerate guard: we stopped with room to spare. Had we written advance(it, -5) from end() of a 4-element set, we'd step before begin() — undefined behaviour. Why this step? Cell C's hidden trap: backward moves must not underflow the range; the standard gives no safety net.

Verify: sorted set {5,15,25,35}; two steps back from end() → element at index size - 2 = 2 → value 25. ✓

Example 4 — Cell D: single-pass input, copy invalidates

Worked example Statement

std::istringstream ss("100 200 300");
std::istream_iterator<int> it(ss), end;
auto copy = it;      // make a "backup"
int first  = *it;    // read
++it;                // advance the ORIGINAL
int viaCopy = *copy; // read the backup — what comes out?

What is viaCopy (many beginners expect 100)?

Forecast: guess viaCopy and whether the copy is trustworthy.

istream_iterator is an input iterator: single-pass. Why this step? It is a thin wrapper over a stream that has already consumed characters — there is no rewind, matching how its `iterator_category` is input_iterator_tag.
*it reads 100 but does not remove it yet; first = 100. Why this step? The first token was buffered when the iterator was constructed.
++it consumes the next token from the shared stream. Why this step? Both it and copy sit on the same underlying ss. Advancing one moves the stream for both — copies are not independent for input iterators.
*copy after the advance is not safe to rely on. Why this step? The Standard's input-iterator requirements (the Cpp17InputIterator rules, [input.iterators]) guarantee validity only for a single pass: once you increment any copy of an input iterator, all other copies are invalidated, and dereferencing an invalidated iterator is undefined behaviour — meaning the program has no defined meaning at all (it may print 200, print garbage, or crash). This is stronger than unspecified behaviour, where you'd at least get some valid value chosen from a known set. The safe conclusion is: never read a copy after advancing another. Only forward iterators upgrade this to multi-pass, where copies are independent.

Verify: the checkable facts are first == 100, and that the category is input (single-pass), so multi-pass reasoning about copy is invalid. ✓

Example 5 — Cell E: output-only, you must count writes

Worked example Statement

std::vector<int> dst;                       // empty
auto out = std::back_inserter(dst);         // output iterator
for (int x : {1, 2, 3, 4}) { *out = x; ++out; }
int n = dst.size();

What is n, and why can't we write while (out != someEnd)?

Forecast: guess dst.size() and why there's no end check.

back_inserter is a pure output iterator. Why this step? *out = x is defined to mean dst.push_back(x); there is no ==, no end sentinel. You cannot ask "am I done?" — you must know the count yourself (here, 4 loop items).
Each *out = x; ++out; appends one element. Why this step? Output iterators support exactly *it = v and ++it; the ++ is a formality (it's a no-op for back-inserters) that keeps the algorithm's shape uniform.
After 4 writes, dst = {1,2,3,4}, so n = 4. Why this step? The number written equals the number of source items — the only "length" information available.

Verify: 4 writes into an empty vector give dst.size() == 4 and dst == {1,2,3,4}. ✓

Example 6 — Cell F: contiguous keeps its promise, `deque` does not

Worked example Statement

std::vector<double> v{1.0, 2.0, 3.0, 4.0};
bool vecOK = (&*(v.begin() + 2) == &*v.begin() + 2);

Is vecOK true? And would the same test on a deque be guaranteed?

Forecast: guess the boolean and the deque verdict.

vector is contiguous, so its elements sit in one block: address of element $k$ is base + k * sizeof(double). Why this step? Contiguity is the one guarantee above random access — see the parent's table row "contiguous storage guarantee".
&*(v.begin()+2) is the address of v[2]; &*v.begin() + 2 is base address plus 2 elements. Why this step? We are comparing "walk the iterator then take the address" vs "take the base address then add 2" — contiguity says these are identical. So vecOK = true.
A deque would it[2] in $O (1)$ (random access) yet may store element 2 in a different chunk. Why this step? Random access is necessary but not sufficient for pointer arithmetic. The address equality can silently fail on deque, which is why you may hand &v[0] (contiguous) but never &deque[0] to a C API expecting a flat array — a fact that flows from pointer arithmetic.

Read the figure like this: compare the two rows box-for-box. The top lavender row is the vector. Its four boxes v[0]..v[3] sit edge to edge with no gaps, and the small grey labels beneath them read base+0, base+1, base+2, base+3 — perfectly linear. Put your finger on v[2] and check its label: it is base+2, so the mint "✓" on the right is earned. The bottom row is the deque: two coral boxes (d[0], d[1]), then a labelled gap (the visual cue that a new memory chunk starts), then two butter boxes (d[2], d[3]). Now put your finger on d[2]: it lives across the gap, so its real address is not base+2 — that broken linearity is exactly what the coral "✗" warns about. The single difference between the two rows — gap vs no gap — is the entire reason only contiguous storage keeps the base + n identity.

Verify: for a contiguous double array, &a[2] == a + 2 is exactly the pointer identity; vecOK == true. ✓

Example 7 — Cell G: empty and single-element ranges

Worked example Statement

std::vector<int> empty;                       // size 0
int d0 = std::distance(empty.begin(), empty.end());
 
std::vector<int> one{99};                     // size 1
int d1 = std::distance(one.begin(), one.end());

What are d0 and d1? Which decrement here is illegal?

Forecast: guess both distances.

For an empty container begin() == end(). Why this step? There is nowhere to point, so both sentinels coincide; the distance between equal iterators is 0. Thus d0 = 0.
For one element, end() is one step past index 0. Why this step? Distance = number of ++ from begin() to end() = size = 1. So d1 = 1.
Degenerate trap: on the empty vector, --empty.end() is undefined — there is no element to land on. Why this step? The limit case: you may decrement end() only when size >= 1. This is Cell G's hidden edge every exam loves.

Verify: distance == size for a forward-or-better range, so d0 == 0, d1 == 1. ✓

Example 8 — Cell H: word problem, pick the minimum category

List the operations you actually use: *it (read), ++it, it != Last. Why this step? The right category is decided by operations used, not by habit — over-constraining rejects valid containers.
You never go backward, never jump, read each element once. Why this step? No --, no +n: bidirectional and random access are unnecessary. Single-pass read + != is exactly the input iterator contract.
Minimum = input iterator; passes = 1. Why this step? Widening the accepted set from random-access down to input lets forward_list, istream, everything work — the whole point of the algorithm/iterator decoupling. The teammate's random_access constraint was an over-specification bug.

Verify: operations used = {read, ++, !=}; the least category providing all three is input (multi-pass not even required), so minimum category index = 1 (input), passes = 1. ✓

Example 9 — Cell I: exam twist, which line fails and why

Worked example Statement

std::list<int> L{2, 4, 6, 8};
auto a = L.begin();
auto b = a + 2;                            // line X
std::advance(a, 2);                        // line Y
int gap = std::distance(L.begin(), a);     // line Z

Exactly one of X / Y / Z fails to compile. Which line, why, and — after you delete it — what is gap?

Forecast: name the failing line and the value of gap.

Line X uses a + 2. Why this step? The + operator on iterators exists only for random-access (and contiguous) iterators. A list iterator is bidirectional, so it defines ++/-- but not operator+. There is no valid overload for a + 2, so the compiler rejects line X. This is the failing line.
Line Y std::advance(a, 2) compiles fine. Why this step? advance is defined for all iterator categories via tag dispatch; for a bidirectional iterator it silently falls back to looping ++a twice ( $O (n)$ ). It never asks for operator+, so it succeeds where line X could not — this is precisely the parent note's advance workaround.
Line Z std::distance(L.begin(), a) also compiles. Why this step? distance likewise dispatches on category and, for bidirectional, counts ++ steps; it needs no operator-. So Z is fine too.
Delete line X and run. After advance(a, 2), a sits at index 2 (value 6), and distance(begin(), a) counts 2 steps. Why this step? This confirms the intended answer: only line X fails, and once removed, gap = 2 with *a == 6.

Verify: removing the illegal +, advance(a,2) puts a at index 2, so gap == 2 and *a == 6. ✓

Active recall

Recall Quick self-test

On a vector, advance(it, 0) does what? ::: Nothing — the degenerate zero move leaves the iterator unchanged. Two -- from set::end() of {5,15,25,35} gives which value? ::: 25 (index size−2). Why is reading a stale copy of an istream_iterator unsafe? ::: Input iterators are single-pass; incrementing any copy invalidates all others, and dereferencing an invalidated iterator is undefined behaviour. distance(begin(), end()) for an empty container equals? ::: 0, because begin() == end(). Which iterator category is the minimum to print a range once? ::: Input iterator. Why does L.begin() + 2 fail for a std::list? ::: operator+ exists only for random-access/contiguous; list iterators are bidirectional, so they have no +. What is the worst-case cost of a single --it on a std::set? ::: $O (lo g n)$ — bounded by the balanced tree's height, not constant. deque supports it[n] in O(1) — is &*(it+n) == &*it + n guaranteed? ::: No; that address identity needs the contiguous category, which deque lacks.