Containers and Their Elements

Suppose you have a collection of values and want to visit each one in turn. Whatever is doing the visiting has to keep track of where it currently is. Every time it moves on, it needs to know which element comes next. The thing that does this job is called an iterator, and this article asks a deceptively simple question about it: if two collections hold their elements in different ways, does the visitor need the same information to walk each of them?

The answer is no, and that answer explains why iterators come in different types at all. A collection stored in a contiguous run of slots and a collection stored as a chain of linked pieces both hold values in order, but the visitor's job is different in each case. Working through that difference is the best way into the topic.

Picture the two containers side by side. A vector keeps its elements in a contiguous run of slots, so each element sits in order and can be reached by its position. A list keeps its elements as a chain of linked pieces. In the list, each element is a value in its own place, and the connection to the next element lives in the link that joins them. The diagram below sets the two layouts next to each other and marks the spot where an iterator is standing in each one.

Notice what the diagram does not show: the vector iterator needs nothing beyond its own position in the run of slots, while the list iterator is tied to a link. Before going further, decide for yourself which of these two starting positions would let an iterator step forward without any extra help.

A vector is a container whose elements sit in order and can be reached by position. That makes the vector iterator the simplest case. It has a plain option available to it: the iterator can be an ordinary pointer to an element. A pointer is a quite 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 it is enough to step forward to the neighboring element.

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 would allow range checking, meaning the iterator can judge whether a requested position actually falls within the vector.

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 vector iterator could get away with a bare pointer because the vector's elements are reachable by position. The list iterator cannot.

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.

The comparison shows the practical difference. The vector iterator can advance from the information it already holds. The list iterator must go through the link it refers to in order to reach both the element and the onward link. That extra step is the reason its design is more involved.

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, even when their internal representations differ. 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 a single 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. The source notes that 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.

For example, 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 source adds that you rarely have to worry about how that type is defined, which is the practical payoff of the container providing the name. The vector<Entry>::iterator line in the diagram follows the same pattern for a vector and is a generated parallel to the source's list example.