Iterator Operations and Their Meanings

Suppose you are writing a loop that walks through a collection of records. You need some way to point at one record, move on to the next one, and read the record you are pointing at. The language gives you a tool for exactly this job, and it is called an iterator.

A natural first question is which specific iterator type you should write down. The answer this article builds toward is that, for most day-to-day work, you do not need to know it. What you need to know is how iterators behave, and where to find the name when you do need it.

Think of an iterator less as a particular kind of thing and more as a role that many different objects can play. What makes an object an iterator is that it responds to the same operations in the same way. The operations are named consistently across all iterators, and their meanings are shared. Whatever the underlying object looks like, if it honors these shared meanings, it counts as an iterator.

This is why the idea of a single iterator type can be misleading. Two different objects can have different concrete types and still both be iterators, because they both support the same operations with the same meanings. The thing you are learning is the shared behavior, not the internal shape of any one object.

The clearest way to see the shared behavior is to follow an iterator step by step. Imagine a list holding three names, in order: Ada, Grace, and Alan. Picture an iterator that starts out referring to Ada.

Read the diagram from left to right. Each arrow is one application of the increment operator. The position of the iterator moves along the list one element at a time: first from Ada to Grace, then from Grace to Alan. At every point, the element you would get by dereferencing the iterator is the element it currently refers to, not the element it used to refer to.

The two core operations pull in different directions. The increment operator changes which element the iterator points to, moving it forward to the next one. Applying it yields an iterator that refers to the next element.

The dereference operator does not move anything. It reads through the iterator and gives you the element currently being referred to. Applying it yields the element to which the iterator refers, and the iterator itself stays exactly where it was.

If iterators are defined by shared behavior, you might expect every program to name a separate iterator type for every container it uses. The source describes a convenience instead. Each container knows the iterator types that belong to it, and it makes those types available under two conventional names: iterator and const_iterator.

The container is the one that owns and advertises these types. That means you look the name up through the container rather than memorizing a separate name for each collection. If you have a list of Entry values, the iterator type you need is found through that list, not invented from scratch.

This article concentrates on the naming. How the two names differ in what they permit is a separate question and is not settled by the material covered here, so do not infer more from the names than the source states.

A qualified name such as list<Entry>::iterator identifies the general iterator type of that container. You rarely need to know how that type is defined, but you should be able to read the name and say what it refers to.

Read the name from left to right. The part before the double colon names the container and the element type it holds. The part after the double colon names the iterator type that belongs to that container. So list<Entry>::iterator means the iterator type of a list whose elements are Entry values.

Here is a different list, generated for practice, holding three colors in order: red, green, and blue. Suppose an iterator starts out referring to red. Work through the following steps before checking the answers.

The answer is blue. The first increment moves the iterator from red to green, and the second moves it from green to blue. Dereferencing then returns blue, and the iterator still refers to blue because dereferencing does not move it.