Node:Iterators, Next:Function objects, Previous:Core components, Up:Top
Iterators are a generalization of pointers that allow a programmer 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, we need to 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.
/---> 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 dereferenceable. The library never assumes that past-the-end
values are dereferenceable. 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. Dereferenceable 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, we 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.