Understanding Iterator Types

Suppose you have a collection of items and you want to visit each one in turn. Many different kinds of collections exist, and each may store its items in a different way. Yet when you look at the tools used to move through them, a surprising pattern appears. The tools look alike. The same operations keep showing up, and they mean the same things no matter which collection they came from. That shared behavior is what makes a family of objects called iterators.

The question this section answers is simple: what do all iterators have in common? The short answer is their semantics, meaning what their operations do, together with the naming of those operations. Once you understand those two things, you can work with iterators from many different containers without relearning the rules each time.

An iterator is tied to two operations that capture almost everything you do with one. Each one answers a different question: where the iterator goes next, and what it is currently pointing at. The sections below take the two operations one at a time, and then show them working together.

The diagram below is a generated illustration, not taken from the source. It shows a sequence of four elements, each stored at a numbered position. An iterator can be thought of as a marker that refers to one of these positions. Applying * reads the element under the marker, and applying ++ moves the marker to the next position.

Read the diagram from left to right. Each box is one element, and its position number tells you where it sits. An iterator that refers to position 0 gives Entry A when you apply *. Applying ++ to that iterator produces an iterator that refers to position 1, so applying * then gives Entry B. The sequence itself does not change; only the iterator's reference moves.

A natural first guess is that an iterator must belong to some special family of classes, with a required parent and a fixed structure. This section takes a different view. What makes an object an iterator is that it obeys a few simple rules, such as the ones for ++ and *. Any object that follows rules like these is an iterator.

This is why one set of habits works across many collections. A loop written around ++ and * does not need to know whether the thing being advanced is a simple reference into a sequence or a custom object. As long as the shared operations behave as described, the same reasoning applies.

Most of the time you do not need to know the exact type of a particular iterator. Each container knows which iterator types belong to it, and it makes them available under conventional names. Those names are iterator and const_iterator. You reach the type through the container, not by memorizing a separate name for each one.

The source gives one concrete example. The general iterator type for a list of Entry elements is written list<Entry>::iterator. The name combines the container type, list<Entry>, with the conventional member name iterator. Reading the name this way tells you which container the iterator belongs to, even when you do not know anything else about its definition.

Programmers usually do not need the internal definition of an iterator type. You can rely on the shared semantics of ++ and *, and on the conventional naming, without knowing how each iterator type is built inside. The interface is the part you work with; the internal definition is the part that stays out of sight for ordinary use.

The example below is generated to show how the two operations change state. The before and after panels use the same four-element sequence as before. Only the iterator's reference changes; the elements stay where they are.

This section introduces two named ideas that belong to the chapter on type functions in C++: iterator_traits and type predicates. Both are presented here as topics to understand, and the section connects them to each other. The one relationship the section states is that iterator_traits is related to type predicates.