Intuition The one core ideaAn iterator is a small object that acts like a finger pointing at one element of a collection, with two basic powers: "read/write what I point at" and "move me to the next element". Everything else — categories, ++, --, +n — is just a list of which moves this particular finger is allowed to make and how fast .
Before you can understand the six iterator categories in the parent note , you must be fluent in a handful of tiny symbols. This page builds every one of them from nothing. We go slowly and in an order where each idea leans only on the ones above it.
Start with the most concrete picture: a row of boxes, each holding a value.
Definition Container (informal)A container is a thing that stores many values and lets you visit them. In C++ examples: std::vector, std::list, std::set. See STL Containers — vector, list, deque, map .
Picture: the row of boxes above. Each box is one element ; the value inside is the element's value .
We are NOT yet saying how the boxes are laid out in memory. That difference (all-in-a-line vs. scattered) is exactly what will separate the categories later. For now: boxes, values, done.
it
The letters it in the parent note are just a variable name for an iterator — an object that "points at" one element. Think of it as a finger resting on one box.
Picture: the small orange arrow in the figure below, sitting under exactly one box.
Why the topic needs it: algorithms like find and copy never touch the container directly; they only ever hold a finger and move it. That is the whole decoupling trick.
The finger is a separate object from the box. You can have two fingers on the same row, move one, and the other stays put — that idea (multi-pass) becomes important later.
*it
The star * in front of an iterator means "give me the element the finger is resting on ". Reading *it gets the value; writing *it = 7 puts 7 into that box.
Picture: an arrow going from the finger up into the box, pulling out (or dropping in) a value.
Intuition Why a symbol at all — why notbox.value?
The star is borrowed from pointers (see Pointers and pointer arithmetic ). A pointer p holds an address, and *p fetches what lives there. An iterator copies that exact spelling on purpose: if you already know pointers, you already know iterators. This is why the parent calls an iterator a "generalized pointer".
it and *it are the same thing."
Why it feels right: you always seem to write them together.
The fix: it is the finger (a position); *it is the value it touches. it == end compares positions ; *it == 7 compares values . Confusing them is the number-one beginner bug.
++it
++it moves the finger one box to the right . It changes the finger, not the boxes.
Picture: the finger slides from box k k + 1 Why the topic needs it: every iterator category supports ++it. It is the one universal move. A category that could not even step forward would be useless.
--it (in the figure, the gray arrow going left) is the mirror move: one box to the left . Notice it is drawn faded — not every finger is allowed to go backward. That restriction is exactly what will define bidirectional vs forward later.
begin() and end()
begin() gives a finger on the first box.end() gives a finger to a phantom box one past the last — a stopping post, not a real element.
Picture: begin under box 0; end hovering just after the final box, over empty space.
Intuition Why "one past the end" and not "the last element"?With a past-the-end marker, a loop reads cleanly: "keep going while my finger is not end." The moment the finger reaches end, stop. If end were the last real box you'd have to special-case the final step. The half-open range [ begin , end ) begin == end.
== / inequality !=
it1 == it2 asks "are these two fingers on the same box ?" it1 != it2 is the opposite.
Picture: two fingers; == is true only when they sit under the identical box.
Why the topic needs it: the loop above lives or dies on it != c.end(). Without a way to test "have I arrived at the stop-post yet?", you could not know when to stop.
Note this compares positions , never values . Two fingers on two different boxes that happen to hold the same number are not equal.
Definition Random-access arithmetic
it + n = a finger n boxes to the right in one leap .it - n = n boxes to the left in one leap.it[n] = the value n boxes right, i.e. *(it + n).
Picture: one long arrow hopping straight from box k k + n
Intuition The crucial word: "in one leap" (cost)Anyone can reach box k + n ++it n it + n claims something stronger: it gets there in one constant-time step , no matter how big n vector (line of boxes) but false for a list (scattered boxes linked by arrows). This single cost distinction is the heart of the parent's category hierarchy, and it comes straight from Pointers and pointer arithmetic .
it2 - it1
Subtracting two fingers gives how many boxes apart they are (a count, e.g. 5).
Picture: count the gaps between the two fingers.
Why the topic needs it: end - begin is the size of the range. Only categories with fast jumping can compute this in one step.
Definition Order comparison<
it1 < it2 asks "is it1's box further left than it2's?"
Picture: compare positions along the row; left is smaller.
Why the topic needs it: algorithms that split a range in half (like std::sort, see STL Algorithms — sort, find, copy ) must ask "is this finger before that one?". This needs a straight line of positions — again only the random-access family qualifies.
This is the densest symbol in the parent, so we unpack it letter by letter.
&
&x means "==the memory address where x lives==" — like a house number for a value. From Pointers and pointer arithmetic .
Picture: a label under a box reading "house #1000".
Now read &*(it + n) right-to-left, one symbol at a time:
it + n — finger n *(...) — the value under that finger (§2).&(...) — the address of that value.
So &*(it+n) is "the house number of the box n &*(it+n) == &*it + n says:
stronger than random access
A deque can do it + n fast (random access) yet stores boxes in separate chunks , so the house numbers jump between chunks — the even-line promise breaks. vector/array/string keep every box in one unbroken block, so the promise holds and you may hand &v[0] to a plain C function expecting a pointer. Contiguous = random access plus the even-address line.
⊂
A ⊂ B every A is also a B, and B has more ". The parent writes
Input ⊂ Forward ⊂ Bidirectional ⊂ RandomAccess ⊂ Contiguous Reading: every capability of the earlier category is kept by the later one, which then adds more. A contiguous iterator can do everything an input iterator can, plus much more.
Picture: nested rings — a small circle inside a bigger circle inside a bigger one.
This is why the parent's operation table never removes a ✓ as you move right: once a power appears, all richer categories inherit it.
A tag is an empty label-struct (it holds no data) whose only job is to name which category an iterator belongs to, e.g. std::random_access_iterator_tag.
Picture: a coloured sticker on the finger saying "I'm a random-access finger."
Why the topic needs it: at compile time the library reads this sticker to pick the fastest code path — this is Templates and Tag Dispatch , surfaced through iterator_traits and type introspection . No sticker-reading happens while the program runs; it costs nothing. The modern Ranges library (C++20) builds on the same category ideas.
Iterator it = finger on one box
star it = read or write the value
plus plus it = step forward
begin end and the stop post
equals and not equals compare positions
it plus n = jump many boxes fast
address of gives contiguous line
Refinement chain of six categories
Category tags select fast code at compile time
Cover the right side and answer aloud. If any answer is fuzzy, re-read that section before the parent note.
What does it (an iterator) represent in one word? A finger pointing at one element of a collection.
What is the difference between it and *it? it is the position (the finger); *it is the value under it.
What does ++it change — the boxes or the finger? Only the finger; it slides one box to the right.
Where does end() point, and why not at the last element? One box past the last, so loops can stop cleanly with it != end.
Does it1 == it2 compare positions or values? Positions — same box or not, regardless of value.
What extra promise does it + n make beyond pressing ++it n times? It reaches the target in one constant-time leap, no matter how big n is.
Read &*(it + n) right-to-left in plain words. Address-of the value under the finger that is n boxes to the right.
What does A ⊂ B mean for categories? Every capability of A is kept by B, and B adds more (refinement).
Why can a deque do it + n but fail the contiguous test? Its boxes live in separate chunks, so addresses don't rise in one even line.
What is a category tag and when is it read? An empty label-struct naming the category, read at compile time to pick the fastest code.
