Iterators — input, output, forward, bidirectional, random access, contiguous: Exercises

Intuition How to use this page

This is a self-testing ladder built on the parent Iterators note. Each problem states the task cleanly; the answer hides inside a collapsible [!recall]- box. Try first, then reveal.

The levels climb Bloom's ladder:

L1 Recognition — can you name the category?
L2 Application — can you use the right operation?
L3 Analysis — can you explain why code compiles or fails?
L4 Synthesis — can you build something from the pieces?
L5 Mastery — can you reason about cost, dispatch, and edge cases?

Before we start, one reminder of the vocabulary you must have from the parent note. An iterator is a "generalized pointer": an object it you can dereference with *it (look at the element it points at) and advance with ++it (step to the next element). A category is a label on the iterator type that says which operations are legal and how fast they are. The six categories, in order of growing power, are:

$Input/Output \subset Forward \subset Bidirectional \subset RandomAccess \subset Contiguous$

Everything below tests exactly that ladder. Prerequisites if you get stuck: Pointers and pointer arithmetic, STL Containers — vector, list, deque, map, iterator_traits and type introspection.

Reference figures

The first figure is the memory picture — the single fact that separates vector (contiguous) from deque (random access but chunked) from list (bidirectional, scattered). Keep it in view for L3–L5.

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

The second figure is the capability ladder — each rung adds exactly one new operation on top of the rung below. Refer to it whenever a problem asks "which category introduces X?"

L1 — Recognition

Recall Solution 1.1

(a) std::vector<int> → Contiguous — elements sit in one memory block. (b) std::list<int> → Bidirectional — a doubly-linked list can step ++ and --, but cannot jump. (c) std::deque<int> → RandomAccess — it + n is $O (1)$ , but memory is chunked, so not contiguous. (d) std::set<int> → Bidirectional — it is a balanced tree; you can walk both directions but not index. (e) std::forward_list<int> → Forward — singly-linked, so it can only step forward and re-traverse.

Recall Solution 1.2

(a) std::istream_iterator<int> → Input — read-only, single-pass; each ++ pulls one token off the stream. (b) std::ostream_iterator<int> → Output — write-only; *it = x prints, ++it is a no-op. (c) std::back_insert_iterator → Output — *it = x calls push_back(x) on the container; no reading, no equality.

Recall Solution 1.3

--it → Bidirectional (backward stepping).
it[n] → RandomAccess ( $O (1)$ indexing).
*it = v write → Output (writing is the defining power of output; Forward keeps it).
multi-pass re-read → Forward (you may copy and revisit).
&*(it+n) == &*it + n → Contiguous (linear address guarantee).

L2 — Application

Recall Solution 2.1

(a) vector (random access): it += 5; — a single $O (1)$ pointer jump. (b) list (bidirectional): std::advance(it, 5); — internally loops ++it five times, $O (5)$ . it += 5 won't compile. (c) istream_iterator (input): std::advance(it, 5); — loops ++it, consuming 5 tokens, $O (5)$ , single-pass. You can never go back.

std::advance is the safe choice everywhere; it uses tag dispatch (see Templates and Tag Dispatch) to pick $O (1)$ vs $O (n)$ automatically.

Recall Solution 2.2

(a) v.end() - v.begin() = 10, computed in $O (1)$ : random-access iterators subtract like pointers. (b) L.end() - L.begin() fails because subtraction needs random access. Use std::distance(L.begin(), L.end()) = 10, computed in $O (10)$ by counting ++ steps.

Recall Solution 2.3

std::sort(v.begin(), v.end()); — works because std::sort requires random access (it jumps around while partitioning).
L.sort(); — the free std::sort won't compile on L (bidirectional only), so list ships its own member sort that rewires node pointers instead of jumping.

L3 — Analysis

Worked example Problem 3.1 — Why does one line compile and the other not?

std::vector<int> v{10,20,30,40};
std::list<int>   L{10,20,30,40};
auto a = v.begin() + 2;   // (A)
auto b = L.begin() + 2;   // (B)

Explain precisely why (A) compiles and (B) is a compile error. What is *a?

Recall Solution 3.1

(A) compiles because vector::iterator is contiguous → random access, so it overloads operator+(iterator, int). *a == 30 (the element at index 2). (B) fails because list::iterator is bidirectional: it defines ++ and -- but not operator+. There is no way to jump n steps in $O (1)$ over scattered nodes, so the language does not even provide the syntax. The correct rewrite is auto b = L.begin(); std::advance(b, 2);.

Worked example Problem 3.2 — The contiguous vs random-access C-API trap

void c_api(double* data, int n);         // expects a raw array
std::vector<double> v{1,2,3,4};
std::deque<double>  d{1,2,3,4};
c_api(&v[0], 4);   // (A)
c_api(&d[0], 4);   // (B)

Which call is safe and which is undefined behaviour? Justify using the memory picture (figure 1).

Recall Solution 3.2

(A) c_api(&v[0], 4) is safe. vector is contiguous: its four doubles occupy one linear block, so &v[0] followed by +1, +2, +3 lands on the real elements — exactly &*(it+n) == &*it + n. (B) c_api(&d[0], 4) is undefined behaviour. deque is random-access but chunked (figure 1, right): elements 0–1 may live in one block and 2–3 in another. &d[0] + 2 points into the first block's off-the-end area, not at d[2]. Random access ≠ contiguous.

Worked example Problem 3.3 — Single-pass invalidation

std::istringstream ss("5 6 7");
std::istream_iterator<int> it(ss), end;
auto copy = it;      // make a copy
int x = *it; ++it;   // read 5, advance the ORIGINAL
int y = *copy;       // what is y?

What value does y hold, and what general rule does this demonstrate?

Recall Solution 3.3

y reads whatever the stream now offers after the original advanced — the copy is invalidated, so *copy does not reliably give back 5. In practice it yields the same value the original now sees (undefined/unspecified to rely on it). This demonstrates that input iterators are single-pass: advancing any iterator over a stream moves the shared underlying stream, so copies do not preserve position. Multi-pass (safe copying and re-reading) begins only at Forward.

L4 — Synthesis

Recall Solution 4.1

template<class It>
void impl(It& it, int n, std::random_access_iterator_tag) {
    it += n;                          // O(1)
}
template<class It>
void impl(It& it, int n, std::bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++it;     // O(n) forward
    else        while (n++) --it;     // O(|n|) backward
}
template<class It>
void impl(It& it, int n, std::input_iterator_tag) {
    while (n--) ++it;                 // O(n), forward only, single-pass
}
template<class It>
void my_advance(It& it, int n) {
    impl(it, n,
         typename std::iterator_traits<It>::iterator_category{});
}

n = 0: every overload does nothing (it += 0, or the while never runs). Correct no-op.
negative n on bidirectional: the else branch runs --it exactly |n| times. On an input iterator negative n is ill-formed (no --), which the tag system correctly refuses to compile.

See iterator_traits and type introspection for how iterator_category is extracted.

Recall Solution 4.2

std::copy(std::istream_iterator<int>(std::cin),   // INPUT source
          std::istream_iterator<int>(),           // end sentinel
          std::ostream_iterator<int>(std::cout, " ")); // OUTPUT sink

Why it works: std::copy needs only an input iterator for the source (read + ++) and an output iterator for the destination (*it = x + ++). Both are single-pass, which is all copy requires. See STL Algorithms — sort, find, copy.

Recall Solution 4.3

The standard tool is std::distance, which is itself tag-dispatched:

template<class It>
auto steps_to_end(It begin, It end) {
    return std::distance(begin, end);   // O(1) if random access, else O(n)
}

std::vector<int> v(7): steps_to_end(v.begin(), v.end()) = 7, computed in $O (1)$ (subtraction).
std::forward_list<int> f{1,1,1}: = 3, computed in $O (3)$ (counting ++).

L5 — Mastery

Worked example Problem 5.1 — Cost accounting for a naive loop

A student writes, over std::list<int> L of size $n$ :

for (int i = 0; i < n; ++i) {
    auto it = L.begin();
    std::advance(it, i);   // touch element i
    use(*it);
}

Give the total time complexity as a function of $n$ , and the fixed version.

Recall Solution 5.1

Each iteration calls std::advance(it, i) on a bidirectional iterator, costing $O (i)$ . Total: $\sum_{i = 0}^{n - 1} i = \frac{n ( n - 1 )}{2} = O (n^{2})$ For $n = 100$ that is $\frac{100 \cdot 99}{2} = 4950$ steps. Fix — walk once, $O (n)$ :

for (auto it = L.begin(); it != L.end(); ++it)
    use(*it);

Recall Solution 5.2

Algorithm	Weakest category needed	Reason
`std::copy`	Input (source) + Output (dest)	single forward pass
`std::find`	Input	linear scan, read + `++`
`std::reverse`	Bidirectional	swaps from both ends inward, needs `--`
`std::binary_search`	Random access for $O (lo g n)$ (works on Forward but degrades to $O (n)$ walking)	needs midpoint jumps
`std::sort`	Random access	partition jumps around

This is why std::list (bidirectional) can do find/reverse but not sort.

Recall Solution 5.3

std::vector<bool> is a specialization that packs each element into a single bit, not a byte. So v[i] returns a proxy object (a bit reference), and there is no addressable bool to take the address of — &v[0] doesn't even yield bool*. Its iterator is therefore not contiguous (arguably not even a true random-access-to-bool). For a real contiguous bool buffer use std::vector<char>, std::array<bool, N>, or std::deque-free flat storage.

Recall Solution 5.4

No, iterators cannot be contiguous. Requirement (i) — cheap growth at both ends — forces the storage into separate blocks (you cannot keep one flat array and still insert at the front in $O (1)$ ). But (ii) $O (1)$ indexing across those blocks is achievable with a block map. So the strongest category is RandomAccess (but not Contiguous) — exactly what std::deque provides. This is the design behind figure 1's middle panel.

Recall Self-test summary (reveal after finishing)

Which container is random-access but not contiguous? ::: std::deque. Total cost of "restart from begin and advance i" for i=0..n-1 on a list? ::: $O (n^{2})$ , specifically $n (n - 1) /2$ . Weakest category std::reverse needs? ::: Bidirectional (it needs --). Why is &vector<bool>[0] not a bool*? ::: It packs bits; [] returns a proxy, no addressable byte-sized bool. When is tag dispatch resolved? ::: At compile time, by the tag's type — zero runtime cost.