Next : , Previous : Core components, Top : Table of Contents

Iterators

Iterators are a generalization of pointers that allow the user to work with different data structures(containers) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, formalize not just the interfaces but also the semantics and complexity assumptions of iterators. Iterators are objects that have operator* returning a value of some class or built-in type T called a value type of the iterator. For every iterator type X for which equality is defined, there is a corresponding signed integral type called the distance type of the iterator.

Since iterators are a generalization of pointers, their semantics is a generalization of the semantics of pointers in C++. This assures that every template function that takes iterators works with regular pointers. Depending on the operations defined on them, there are five categories of iterators: input iterators See Input iterators, output iterators See Output iterators, forward iterators See Forward iterators, bidirectional iterators See Bidirectional iterators, and random access iterators See Random access iterators. Forward iterators satisfy all the requirements of the input and output iterators and can be used whenever either kind is specified. Bidirectional iterators satisfy all the requirements of the forward iterators and can be used whenever a forward iterator is specified. Random access iterators satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified. 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* behaves as a reference or as a reference to a constant. Constant iterators do not satisfy the requirements for output iterators.

Table 1: Relations among iterator categories
                                                      /---> Input
       Random access --> Bidirectional --> Forward --*
                                                      \---> Output

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* is defined are called dereference able. The library never assumes that past-the-end values are dereference able. Iterators might also have singular values that are not associated with any container. For example, after the declaration of an uninitialized pointer x (as with int* x;), x should always be assumed to have a singular value of a pointer. Results of most expressions are undefined for singular values. The only exception is an assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereference able and past-the-end values are always non-singular.

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

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.

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column. In the following sections, assume: a and b are values of X, n is a value of the distance type Distance, u, tmp, and m are identifiers, r and s are lvalues of X, t is a value of value type T.

 

Top