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

WHY do iterators exist at all?

The six categories (the WHAT)

Definition Iterator categories (refinement chain)

Each category is a strict superset (refinement) of capabilities of the one before it: $\text{Input/Output} \subset \text{Forward} \subset \text{Bidirectional} \subset \text{RandomAccess} \subset \text{Contiguous}$

Input: read-only, single-pass. Supports *it (read), ++it, ==, !=. Once advanced, old position is invalid. Example: istream_iterator.
Output: write-only, single-pass. Supports *it = x, ++it. Example: ostream_iterator, back_insert_iterator.
Forward: multi-pass read/write, moves forward only. Adds: you may re-traverse, store a copy and revisit. Example: forward_list, unordered_set.
Bidirectional: adds --it (step backward). Example: list, set, map.
RandomAccess: adds it + n, it - n, it[n], it1 - it2, and <, > in $O(1)$ . Example: deque.
Contiguous (C++17/20): random access plus elements live in one contiguous memory block, so &*(it+n) == &*it + n. Example: vector, array, string, raw pointers.

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

Formula Operation support table (derive the cost, don't memorize)

Operation	Input	Output	Forward	Bidir	Random	Contig
`*it` read	✓	–	✓	✓	✓	✓
`*it = v` write	–	✓	✓	✓	✓	✓
`++it`	✓	✓	✓	✓	✓	✓
`--it`	–	–	–	✓	✓	✓
`it + n`, `it[n]`	–	–	–	–	✓	✓
`it2 - it1`	–	–	–	–	✓	✓
multi-pass	–	–	✓	✓	✓	✓
contiguous storage guarantee	–	–	–	–	–	✓

WHY this layout? Each ✓ that appears is kept in every column to its right (refinement). The first appearance of an op marks the category that introduces it.

HOW the compiler uses categories (tag dispatch)

template<class It>
void advance_impl(It& it, int n, std::random_access_iterator_tag) {
    it += n;                       // O(1) — only legal here
}
template<class It>
void advance_impl(It& it, int n, std::bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++it;  // O(n)
    else        while (n++) --it;
}
template<class It>
void advance_impl(It& it, int n, std::input_iterator_tag) {
    while (n--) ++it;              // O(n), forward only
}
template<class It>
void advance(It& it, int n) {
    advance_impl(it, n,
        typename std::iterator_traits<It>::iterator_category{});
}

Why this step? The empty tag object's type selects the overload at compile time — zero runtime cost, yet each container gets its optimal algorithm. This is the whole point of the hierarchy.

Worked examples

Worked example 1 — Reading numbers with an INPUT iterator

std::istream_iterator<int> in(std::cin), end;
std::vector<int> v(in, end);   // reads until EOF

Why this step? istream_iterator is single-pass input: each ++ consumes one token from the stream. You can't go back — once read, it's gone. That's exactly the input-iterator contract, matching how a stream physically works.

Worked example 2 — Writing with an OUTPUT iterator

std::vector<int> v{1,2,3};
std::copy(v.begin(), v.end(),
          std::ostream_iterator<int>(std::cout, " "));  // prints "1 2 3 "

Why this step? ostream_iterator only supports *it = x (which prints) and ++it. std::copy needs just an output iterator for its destination, so it works. You never read from it.

Worked example 3 — Random access lets you binary-search; bidirectional doesn't

std::vector<int> v{1,3,5,7,9};
auto mid = v.begin() + v.size()/2;   // O(1): random access
 
std::list<int> L{1,3,5,7,9};
// auto m = L.begin() + 2;           // COMPILE ERROR: list iterator has no +
auto m = L.begin(); std::advance(m, 2); // O(n) workaround

Why this step? std::sort requires random access because it jumps around (partitioning). That's why std::list has its own member L.sort() — its iterators are only bidirectional.

Worked example 4 — Contiguous: pointer arithmetic is valid

std::vector<double> v{1.0, 2.0, 3.0};
double* raw = &v[0];
assert(&*(v.begin()+2) == raw + 2);   // guaranteed by contiguous category

Why this step? Only contiguous iterators promise the elements sit in one memory block, so you can hand &v[0] to a C API expecting double*. std::deque is random-access but not contiguous — this would fail.

Common mistakes (Steel-man + fix)

Active recall

What is an iterator, in one phrase?

A generalized pointer giving uniform traversal over a container.

List the six iterator categories in refinement order.

Input/Output → Forward → Bidirectional → RandomAccess → Contiguous.

Which operation does Bidirectional add over Forward?

Backward stepping --it.

Which operations does RandomAccess add over Bidirectional?

it+n, it-n, it[n], it2-it1, ordering </>, all in O(1).

What extra guarantee does Contiguous add over RandomAccess?

Elements occupy one contiguous memory block: &*(it+n) == &*it + n.

What container has only bidirectional iterators, not random access?

std::list (also set, map).

Why is std::deque random-access but NOT contiguous?

Its memory is split into separate fixed-size chunks, so addresses aren't linear.

What does "single-pass" mean and which categories are single-pass?

Each element can be visited once; old positions become invalid. Input and Output iterators.

How does std::advance get O(1) for vectors and O(n) for lists with one name?

Tag dispatch on iterator_traits::iterator_category chooses an overload at compile time.

Example of an input iterator? An output iterator?

istream_iterator; ostream_iterator / back_insert_iterator.

Why does std::sort not work on std::list?

sort needs random-access iterators; list's are bidirectional — use list::sort() instead.

What category does forward add over input?

Multi-pass: you can copy an iterator and re-traverse.

Recall Feynman: explain to a 12-year-old

Imagine different toy boxes. A scroll of paper you can only read once as it unrolls — that's an input iterator. A stamp that only prints, never reads — that's output. A train on a one-way track that you can ride again from the start is forward. A train that can also reverse is bidirectional. A teleporter that jumps straight to seat #50 is random access. And if all the seats are bolted in one straight row with no gaps, that's contiguous. The fancier the toy, the more it can do — and the STL picks the cheapest trick each toy allows.

Connections

Pointers and pointer arithmetic — iterators generalize these.
STL Containers — vector, list, deque, map — each exposes a specific iterator category.
STL Algorithms — sort, find, copy — written against iterator categories.
Templates and Tag Dispatch — the compile-time mechanism behind advance/distance.
iterator_traits and type introspection — how the category tag is read.
Ranges library (C++20) — modern layer built atop iterator concepts.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho iterator ek "smart pointer" hai jo kisi bhi container — vector, list, set, stream — ke upar same tareeke se chalne deta hai. Iska sabse bada faayda: STL algorithms (jaise sort, find, copy) ko ek hi baar likho, aur har container pe chal jaate hain, kyunki sab container iterators expose karte hain. Yahi decoupling C++ ko itna powerful banata hai.

Ab har container same speed se sab kuch nahi kar sakta, isliye iterators ki categories hoti hain. Sabse kamzor Input (sirf padho, ek baar) aur Output (sirf likho, ek baar). Uske upar Forward — dobara ghoom sakte ho. Phir Bidirectional — peeche bhi ja sakte ho (--it), jaise list aur set. Phir Random Access — seedha 50th element pe jump, it+n, O(1) mein, jaise vector aur deque. Aur sabse top Contiguous — elements ek hi continuous memory block mein, isliye &v[0] ko C function ko de sakte ho; ye sirf vector, array, string deti hain.

Important trap: deque random-access hai par contiguous nahi, kyunki uska data alag-alag chunks mein hota hai. Aur list ko std::sort se sort nahi kar sakte kyunki uske iterators sirf bidirectional hain — uske liye list.sort() use karo. std::advance ek hi naam se vector ke liye O(1) aur list ke liye O(n) kaise karta hai? Compile-time pe tag dispatch se — iterator ka category tag dekh kar sahi version chun leta hai. Yahi poori hierarchy ka asli maqsad hai: har container ko uska sabse fast algorithm mil jaaye.

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

WHY do iterators exist at all?

The six categories (the WHAT)

HOW the compiler uses categories (tag dispatch)

Worked examples

Common mistakes (Steel-man + fix)

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — C++ Programming

Connections