Container-specific Iterator Implementations

Suppose you have a collection of values and want to visit each one in turn. The thing doing the visiting has to keep track of where it currently is. Now suppose there are two different kinds of collection: one stores its elements in a contiguous run of slots, and the other stores them as a chain of linked pieces. Does the visiting thing need the same information in both cases? Working through that question is the best way into this topic, because the answer explains why iterators come in different types at all.

Start with the vector, a container whose elements sit in order and can be reached by position. A vector iterator has a simple option available to it: it can be an ordinary pointer to an element. A pointer is a reasonable way of referring to an element of a vector, so no extra machinery is needed. Holding a pointer is enough to know where you are and to step forward to the neighboring element.

The key idea is that a vector's elements are arranged so that the element after the current one is the neighboring slot. Because the iterator only needs to know which slot it is at, a single pointer carries all of the information the iterator needs to do its job for a vector.

The vector iterator could also be designed differently. Instead of holding only a pointer, it could hold a pointer to the vector itself together with an index, which is a number giving the position within that vector. Both designs are valid for a vector, but they carry different information.

The second design is the one that allows range checking. Because the iterator knows the vector it belongs to and its position within that vector, it can judge whether a requested position actually falls within the vector. A bare pointer carries no such information about the vector around it, so the pointer-only design cannot do this check on its own.

Now turn to the list. A list element cannot be relied on to know where the next element is. Each element is simply a value in its own place, and the link to its neighbor is not something the element itself is guaranteed to carry for the iterator's purposes. Because of this, a pointer to an element is not enough to move from one list element to the next.

The list iterator therefore must be something more complicated than a simple pointer to an element. One natural choice is a pointer to a link, meaning the iterator refers to the connecting piece of the list rather than to the bare element. From the link, the iterator can reach the element it refers to and also the link that leads onward. This is the reason the list iterator and the vector iterator end up with different types.

Taken together, these designs explain the type difference. Each iterator must hold whatever information it needs to do its job for one particular container. A vector iterator can get by with a pointer to an element, or with a pointer to the vector plus an index. A list iterator needs a pointer to a link. Because the held information differs, the iterator types differ as well, and iterator types can differ as much as the containers they serve.

After seeing how varied the designs are, it may seem that every iterator is a different creature. The source emphasizes the opposite. What is common to all iterators is their semantics and the naming of their operations. Two operations do most of the work. Applying the increment operator, written ++, to any iterator yields an iterator that refers to the next element. Applying the dereference operator, which is written as an asterisk, yields the element to which the iterator refers.

This is why one idea can cover all of these types. Any object that obeys a few simple rules like these counts as an iterator, and that shared set of rules is what the concept of an iterator describes. The internal representation can vary widely, but the behavior seen from outside stays consistent. A reader who knows the operations can use an iterator without knowing how it was built.

A natural follow-up question is how a programmer refers to these types without memorizing their details. Users rarely need to know the specific type of a particular iterator. Instead, each container knows its own iterator types and makes them available under the conventional names iterator and const_iterator. The names are the same across containers, even though the types behind them are not.

In that expression, list<Entry>::iterator is the general iterator type for a list of Entry elements. Writing the container name followed by the conventional name lets you refer to the right iterator type for that container. The practical payoff is that you rarely have to worry about how that type is defined, because the container supplies the name.