Iterators

Iterators are a generalization of pointers that allow a programmer to work with different data structures (containers) in a uniform manner. An iterator is the glue that allows to write a single implementation of an algorithm that will work for data contained in an array, a list or some other container - even a container that did not yet exist when the algorithm was implemented.

An iterator is a concept, not a programming language construct. It can be seen as a set of requirements. A type is an iterator if it satisfies those requirements. So, for instance, a pointer to an element of an array is an iterator. We will check this later.

Depending on the operations defined for an iterator, there are five categories: input, output, forward, bidirectional and random access iterators. We first have to introduce some terminology.

Mutable versus constant: There is an additional attribute that forward, bidirectional and random access iterators might have, that is, they can be mutable or constant depending on whether the result of the operator \raisebox-1mm* behaves as a reference or as a reference to a constant.

Past-the-end value: Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding container. These values are called past-the-end values. Values of the iterator for which the operator \raisebox-1mm* is defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable.

Reachability An iterator $j$ is called reachable from an iterator $i$ if and only if there is a finite sequence of applications of operator$++$ to $i$ that makes $i\; ==\; j$. If $i$ and $j$ refer to the same container, then either $j$ is reachable from $i$, or $i$ is reachable from $j$, or both ($i\; ==\; j$).

Range: Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range $[i,\; i)$ is an empty range; in general, a range $[i,\; j)$ refers to the elements in the data structure starting with the one pointed to by $i$ and up to but not including the one pointed to by $j$. Range $[i,\; j)$ is valid if and only if $j$ is reachable from $i$. The result of the application of the algorithms in the library to invalid ranges is undefined.

As we mentioned in the introduction we are a little bit sloppy in the presentation of \stl, in order to make it easier to understand. A class is said to be an iterator if it fulfills a set of requirements. In the following sections we do not present the requirements, but we state properties that are true, if the requirements are fulfilled. The difference is best seen by an example: we write that the return value of the test for equality returns a bool, but the requirement is only that the return value is convertible to bool.

• Class declaration of iterator.

• Class declaration of iterator.

• Class declaration of iterator.

• Class declaration of iterator.

• Class declaration of iterator.