Iterator Concept and Shared Semantics

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. That tracking object is an iterator. Visiting a collection is a simple idea, but it raises a question that is worth working through slowly: do two different kinds of collection need the same information to be visited?

The rest of this article follows that question. We will trace what a visitor must remember for a vector, then for a list, and see how the answer shapes the iterator type. Along the way we will find the small set of behaviors that every iterator shares, and how a container advertises its iterator types so that general code can refer to them by name.

Start with the vector, a container whose elements sit in order and can be reached by position. Its elements occupy a contiguous run of slots, so each element sits next to its neighbor in a predictable place. A vector iterator has a simple option available: it can be an ordinary pointer to an element. A pointer is a reasonable way to refer to an element of a vector, so no extra machinery is needed. Holding that one pointer is enough to know where you are and 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. So even for one container, the choice of what to remember changes what the iterator is able to do.

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. Holding the element's location tells you where the value is, but gives no route onward.

The list iterator therefore has to 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, even though both serve the same purpose of visiting values.

Trace what happens when a list iterator moves. It holds a link. Advancing it means following the link to the next piece of the list, so the iterator now refers to that next link and, through it, the next element. The diagram below shows three links in a chain. The iterator starts on the first link, and after one increment it refers to the second.

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. 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.