Container Iterator Names

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 article answers is simple: what do all iterators have in common? The short answer is their semantics, meaning what their operations do, and 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. The first is the increment operation, written ++. Applying ++ to any iterator produces an iterator that refers to the next element in the sequence. The result is itself an iterator, so the operation can be repeated to keep moving forward.

The second is the dereference operation, written with the asterisk, *. Applying * to an iterator yields the element to which that iterator refers. Where ++ answers the question of where to go next, * answers the question of what is currently being pointed at.

The diagram uses a short list of three made-up items. Each arrow labeled ++ moves the iterator one step forward to the next element. At every position, * is the operation that reads the element the iterator currently points at. The two operations divide the work cleanly: ++ changes which element is referred to, and * retrieves that element.

A good way to see the two operations work together is to trace an iterator through a short sequence and record, after each step, where it refers and what * would return. The example below uses the same three made-up items as the previous diagram.

The before and after view makes the change explicit. Before ++ is applied, the iterator refers to banana. After ++ is applied, the iterator refers to cherry. The iterator itself is what changes position, while the sequence of elements stays the same.

A natural first guess is that an iterator must belong to some special family of classes, with a required parent and a fixed structure. The source 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 the same tools can be used across many different containers. The rules stay the same even when the way each collection stores its items is different. You can rely on the shared meaning of ++ and * rather than on the details of any single container.

Containers make their iterator types available under the conventional names iterator and const_iterator. 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.

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. You reach the type through the container, not by memorizing a separate name for each one.

Programmers usually do not need the internal definition of an iterator type. They can rely on the shared semantics of ++ and * and on the conventional naming. This means that code written against those shared rules can work with iterators from different containers without knowing how each one is built inside.