Iterators: The Interface Between Containers and Algorithms

Part I · Module 20 · Chapter 20.1 · Iterators: The Interface Between Containers and Algorithms

1. The Problem Iterators Solve

Module 19 measured five storage strategies, and each one reaches its elements differently. A std::vector computes an address from an index. A std::list follows a next pointer. A std::map descends a tree. A std::deque does two steps of arithmetic through a block index.

Suppose you want a function that finds a value in a sequence. Written against a std::vector it indexes; against a std::list it walks links; against a std::map it descends. Three functions, three bodies, and a fourth container means a fourth function. With roughly a hundred useful operations and ten containers, that is a thousand functions, and every new container multiplies the work again.

An iterator is the abstraction that collapses this. It is an object that holds a position in a sequence and offers a small fixed vocabulary: dereference it to get the element, increment it to move to the next position, compare it with another to see whether they are the same place. Every container supplies iterators that implement that vocabulary over its own machinery, so an algorithm written against the vocabulary works on all of them.

The gain is multiplicative rather than additive. One hundred algorithms plus ten containers, each supplying iterators, replaces one thousand member functions — and a container written tomorrow gets all hundred algorithms for free, as does an algorithm written tomorrow for all containers. Chapter 18.2 §3's operations-not-types stance is exactly what makes this work: the algorithms are templates that require only the operations they use.

2. What an Iterator Actually Is

The most useful way to think about an iterator is as a generalised pointer, and this is not a loose analogy — a raw pointer is a fully conforming iterator, and the standard library treats it as one:

int raw[5] = {10,20,30,40,50};
int* b = std::begin(raw);
int* e = std::end(raw);
std::printf("e - b = %ld\n", (long)(e - b));
long long s = 0;
for (int* p = b; p != e; ++p) s += *p;      // the vector loop, verbatim

std::begin/end on int[5]: e - b = 5
the same loop that works on a vector sums to 150

The loop body is character-for-character what you would write for a std::vector. That is the point: pointers already had the vocabulary — *, ++, !=, and subtraction — and iterators generalise it to things that are not addresses.

What an iterator costs:

sizeof(int*)                      =  8  (a raw pointer IS an iterator)
sizeof(vector<int>::iterator)     =  8
sizeof(array<int,8>::iterator)    =  8
sizeof(list<int>::iterator)       =  8
sizeof(map<int,int>::iterator)    =  8
sizeof(deque<int>::iterator)      = 16  (needs the block index too)

Five of the six are a single pointer, which is what you would hope: the abstraction is free. A std::vector's iterator is a pointer in every implementation worth using. A std::list's is a pointer to a node. A std::map's is a pointer to a tree node.

std::deque's is 16 bytes and the reason is Chapter 19.4 §4's block structure: to find the next element a deque iterator must know both where it is inside the current block and where the block index is, so one pointer is not enough. That is the structural cost of giving up contiguity, showing up in the iterator rather than in the container.

3. The Vocabulary

Four operations, and not every iterator offers all four — Chapter 20.2 is entirely about which offers what.

std::vector<std::string> v{"alpha","beta","gamma"};
auto it = v.begin();

*it            -> "alpha"
it->size()     -> 5   (-> is sugar for (*it).)
after ++it     -> "beta"
it != v.end()  -> true   (comparison, not <, for non-random-access)

Dereference (*it) yields the element — a reference, so *it = x assigns to the container's element rather than to a copy. Arrow (it->m) is the same thing for a member, exactly as with a pointer. Increment (++it) advances one position. Equality (it != other) asks whether two iterators denote the same position.

The last one deserves attention, because the obvious alternative is wrong. A loop condition written it < v.end() compiles for a std::vector and fails for a std::list, since ordering two positions in a linked structure has no cheap meaning. Writing it != v.end() works for every iterator in the library, which is why it is the universal form and why every example in this module uses it.

Prefer ++it to it++ for the reason Chapter 4.7 §5 gives: the postfix form must produce a copy of the old value, and for a non-trivial iterator that copy is real work the loop discards.

4. The Half-Open Range

This is the convention the rest of the library is built on, and it is worth stating precisely. A range is a pair of iterators written [begin, end) — square bracket, round bracket — meaning: begin is included, end is not. end() denotes the position one past the last element. There is no element there, and dereferencing it is undefined behaviour.

end() - begin() = 5 == size() = 5
*begin() = 1   *(end()-1) = 5
an empty range: begin()==end() is true, so the loop body never runs
and size of a sub-range [1,4) = 3

Four properties fall out, and all four are reasons the convention was chosen.

The length is a subtraction. end - begin is the element count, with no +1 anywhere. Measured above as exactly size().

An empty range needs no special case. begin() == end() and every loop written while (it != end) runs zero times, correctly, with no test for emptiness. A closed range [first, last] cannot express "no elements" at all without a sentinel.

Splitting is seamless. A range divides into [begin, mid) and [mid, end) with mid appearing in both halves and belonging to neither twice:

split at 2: [begin,mid) has 2, [mid,end) has 3, total 5

Two and three make five, with no adjustment. Every divide-and-conquer algorithm in the library relies on this, which is why std::sort and std::partition return or take a single iterator to mean a boundary.

Termination is an equality test, which §3 explained is the only comparison every iterator supports.

The last element is therefore *(end() - 1) for a random-access range, or *std::prev(end()) in general — and both are undefined on an empty range, so the check comes first.

5. Where Ranges Come From

begin() and end() are members on every standard container. There are also the free functions std::begin(c) and std::end(c), which call the members when they exist and do the right thing for built-in arrays when they do not — that is what §2's int raw[5] example used.

Prefer the free functions in generic code, precisely because they also work on arrays. A template written with c.begin() silently refuses arrays; one written with std::begin(c) accepts them. Chapter 18.2 §3's point applies: the requirement you state is the requirement you get.

Range-based for is sugar over exactly this:

for (const auto& x : v) use(x);
// means, approximately:
for (auto it = std::begin(v), e = std::end(v); it != e; ++it) { const auto& x = *it; use(x); }

Which is why range-based for works on anything with begin/end, including your own types and including built-in arrays. Note end is evaluated once, before the loop — which is why modifying the container inside a range-based for is the bug Chapter 20.3 is about.

6. Const Iterators

A const_iterator yields a reference to const, so the elements cannot be modified through it. cbegin() and cend() return them explicitly, and calling begin() on a const container gives you one too.

std::vector<int> v{1,2,3};
auto ci = v.cbegin();
*ci = 9;                  // does this compile?

constit.cpp:3:67: error: cannot assign to return value because function
    'operator*' returns a const value

One error, seven diagnostic lines, named at the right place. Use cbegin/cend when the loop only reads: it documents the intent, and it is the difference between a compile error and a successful modification you did not mean to make. This is Chapter 8.7 §5's propagate-const-through-an-interface argument applied to iteration.

7. Reverse Iterators

rbegin() and rend() traverse backwards, and rbegin() points at the last element rather than one past it — the mirror image of the forward convention, so that [rbegin, rend) is again half-open:

reverse: 5 4 3 2 1
*rbegin() = 5   *(rbegin().base()-1) = 5

Incrementing a reverse iterator moves towards the front. The base() member converts back to the corresponding forward iterator, and the -1 in that measurement is the part people get wrong: rit.base() is one ahead of what rit points at, because that is what makes the two half-open conventions line up. If you find yourself reasoning about base(), the measurement above is the fact to re-derive from.

crbegin/crend are the const forms, and they compose exactly as you would expect.

8. distance and advance

Not every iterator supports + n or - other. The two free functions work on every category by doing whatever that category permits:

distance(vector) = 100   (O(1): subtraction)
distance(list)   = 100   (O(n): it counts steps)
advance(list_it, 50) works; l.begin() + 50 does NOT compile

std::distance(a, b) returns the number of increments from a to b. For a random-access iterator it is one subtraction; for anything else it counts, so it is O(n). Chapter 20.2 §4 measures that difference as a shape — flat against linear — and the mechanism is that std::distance inspects the iterator's category and picks an implementation.

std::advance(it, n) moves an iterator n positions, by subtraction where possible and by n increments otherwise. std::next(it, n) and std::prev(it, n) are the non-mutating forms that return a new iterator, which usually read better.

And the error when you reach for arithmetic a category does not have:

noplus.cpp:3:57: error: invalid operands to binary expression
    ('iterator' (aka '__list_iterator<int, void *>') and 'int')

One error — in 49 diagnostic lines, because the compiler lists every operator+ it considered. That verbosity is the pre-concepts diagnostic problem Chapter 18.10 §6 discussed, and §9 of Chapter 20.2 has a much worse example.

9. Iterators That Are Not Positions In a Container

Two kinds of iterator do not point into a container at all, and they are worth knowing because they turn algorithms into tools for things that are not containers.

Insert iterators turn an assignment into an insertion. std::back_inserter(c) returns an iterator whose *it = x calls c.push_back(x):

std::vector<int> dst;                                  // EMPTY
std::transform(src.begin(), src.end(), std::back_inserter(dst), f);

Without it, an algorithm writing to dst.begin() on an empty vector writes into no storage at all — Chapter 20.7 §5 measures why the algorithm cannot detect this. front_inserter and inserter are the variants.

Stream iterators make a stream look like a range. std::istream_iterator<int> reads integers on each increment; std::ostream_iterator<int> writes them on each assignment. Chapter 20.2 §5 measures the consequence that matters: a stream iterator is single-pass, so a range built from one can be consumed exactly once.

Both are ordinary iterators as far as an algorithm is concerned, which is the whole point of having a vocabulary rather than a container.

10. The Operations Table

11. What to Actually Do

• Write it != end, never it < end. The first works on every container.
• Prefer ++it to it++ in a loop that discards the result.
• Use std::begin(c) / std::end(c) in generic code, so built-in arrays work too.
• Use cbegin/cend when the loop only reads. It is a compile error instead of an accidental write.
• Treat end() as a position, never a value. Dereferencing it is undefined behaviour, so the != end() check comes before the *.
• Use std::distance and std::advance rather than arithmetic, in code that must accept any container.
• Use std::next(it) rather than it + 1 unless you know the category.
• Use std::back_inserter when an algorithm writes to a container that has no room yet.
• Prefer range-based for when you need the elements and not the positions.

12. Mistakes Worth Making Once

*v.end(). There is no element there. With a vector it reads the first byte past the data and usually returns something plausible.

it < v.end() in a loop. Works on a vector, fails to compile the day the container becomes a std::list — which is the good outcome, but it is a surprise if you thought the loop was generic.

l.begin() + 50 on a list. One error in 49 diagnostic lines. The fix is std::next(l.begin(), 50), and the cost is still O(n).

Reaching for the last element as *v.end() minus intuition. It is *(v.end() - 1) or v.back(), and both are undefined on an empty container.

Assuming rbegin().base() points at the same element. It points one past it; the measured identity is *rbegin() == *(rbegin().base() - 1).

Writing to dst.begin() from an algorithm when dst is empty. No storage, no diagnostic. Use std::back_inserter.

Calling std::distance in a loop condition on a non-random-access container. It is O(n) per call, so the loop becomes O(n²) and looks innocent.

13. Interview Relevance

The frozen curriculum marks this chapter Critical, and these questions are common because the answers reveal whether someone has read the library or guessed at it.

"What is an iterator?" A generalised position: an object supporting dereference, increment and equality comparison, which lets algorithms be written once against positions rather than once per container. The strong answer adds that a raw pointer is a conforming iterator and that the abstraction is pointer-sized.

"Why does end() point one past the last element?" §4's four reasons — the length is a subtraction, the empty range needs no special case, splitting is seamless, and termination uses equality rather than ordering. Giving two of the four is a good answer; giving the ordering one is a strong answer because it connects to iterator categories.

"Why it != end rather than it < end?" Because < requires a random-access iterator and != does not, so only the first is generic.

"What is the difference between ++it and it++ here?" The postfix form copies the iterator to return its old value; for a non-trivial iterator that is wasted work.

"How do you move a list iterator forward by ten?" std::advance(it, 10) or std::next(it, 10), and it costs ten increments — + 10 does not compile.

"What does std::back_inserter do?" Returns an iterator whose assignment performs push_back, which is how an algorithm writes into a container that has no room.

14. What You Should Be Able to Say Now

• That an iterator is a generalised position, and why that collapses containers × algorithms into containers + algorithms.
• That a raw pointer is a conforming iterator, and that std::begin/std::end work on built-in arrays.
• That five of the six measured iterators are 8 bytes, and why a std::deque's is 16.
• The four universal operations, and that ordering is not one of them.
• The four reasons the range is half-open, including the one about equality versus ordering.
• That end is evaluated once by a range-based for.
• That rbegin() points at the last element and base() is one ahead.
• That std::distance is O(1) or O(n) depending on the category, and + n simply does not exist for some.

15. Exercises

Exercise 1 — the vocabulary. Write one function template that sums a range, and call it with a std::vector, a std::list, a std::set, a std::deque and a built-in array. Use std::begin/std::end.

Exercise 2 — the sizes. Reproduce §2's sizeof table on your platform. Explain any value that is not 8.

Exercise 3 — the convention. Write a function that splits a range in half and returns both halves as iterator pairs. Then write it for a closed [first, last] convention and count the ±1 adjustments you needed.

Exercise 4 — the ordering trap. Write a loop with it < end over a std::vector, confirm it works, then change the container to std::list and read the error.

Exercise 5 — empty ranges. For each of the ten standard containers, construct an empty one and verify begin() == end(). Then write a sum function and confirm it returns the identity without a special case.

Exercise 6 — reverse. Print a vector backwards three ways: rbegin/rend, an index loop, and std::reverse on a copy. Then convert an rbegin() to the equivalent forward iterator and verify with an assertion.

Exercise 7 — the quadratic loop. Write a loop over a std::list whose condition calls std::distance, time it against the correct form, and plot both.

Exercise 8 — insert iterators. Use std::copy to append one vector to another with std::back_inserter, then without it, and explain what the second version does.

16. Summary

• An iterator is a generalised position — dereference, increment, compare — which lets one algorithm serve every container.
• A raw pointer is a conforming iterator; measured, the same loop body summed a built-in array to 150.
• Measured: int*, vector, list and map iterators are all 8 bytes; a deque's is 16, because it needs the block index as well.
• A range is half-open [begin, end), and end() denotes a position with no element.
• Measured: end() - begin() equals size(), an empty range satisfies begin() == end(), and a split at 2 gave 2 + 3 = 5 with no adjustment.
• Termination is an equality test because ordering is not available on every iterator — so write it != end.
• Measured: *v.cbegin() = 9 is one error in 7 lines, and l.begin() + 50 is one error in 49.
• std::distance is O(1) or O(n) by category; std::advance, std::next and std::prev work everywhere.
• rbegin() points at the last element, and rbegin().base() is one ahead of it.
• Insert and stream iterators are iterators that are not positions in a container.

The vocabulary in §3 was presented as four operations with a note that not every iterator offers all of them. Chapter 20.2 makes that precise. The standard sorts iterators into categories by exactly which operations they support, every algorithm states the category it needs, and the result is the rule that explains why std::reverse works on a std::list and std::sort does not — along with the diagnostic you get when you try, which runs to four errors across a hundred and thirty-eight lines and names no line of your own code except the call.