The <iterator>
header declares classes and templates for defining and
using iterators. (See Chapter 10.)
Iterators are especially important when using the standard algorithms in
<algorithm>
.
An iterator gives a program access to the contents of a container
or other sequence, such as an I/O stream. You can think of an iterator
as an abstraction of a pointer; the syntax for using iterators resembles
that of pointers. Conceptually, an iterator points to a single element
in a container or sequence and can be advanced to the next element with
the ++
(increment) operator. The
unary *
(dereference) operator
returns the element that the iterator points to. Iterators (except for
output iterators) can be compared: two iterators are equal if they point
to the same position in the same sequence, or if they both point to one
position past the end of the same sequence.
There are five categories of iterators:
Permit one pass to read a sequence. The increment operator advances to the next element, but there is no decrement operator. The dereference operator does not return an lvalue, so you can read elements but not modify them.
Permit one pass to write a sequence. The increment operator advances to the next element, but there is no decrement operator. You can dereference an element only to assign a value to it. You cannot compare output iterators.
Are like a combination of an input and an output iterator. You can use a forward iterator anywhere an input iterator is required or where an output iterator is required. A forward iterator, as its name implies, permits unidirectional access to a sequence. You can refer to a single element and modify it multiple times before advancing the iterator.
Are like forward iterators but also support the decrement
operator (--
) to move the
iterator backward by one position.
Are like bidirectional iterators but also support the
[]
(subscript) operator to
access any index in the sequence. Also, you can add or subtract an
integer to move a random access iterator by more than one position
at a time. Subtracting two random access iterators yields an
integer distance between them. Thus, a random access iterator is
most like a conventional pointer, and, in fact, a pointer can be
used as a random access iterator.
An input, forward, bidirectional, or random access iterator can be
a const_iterator
. Dereferencing a
const_iterator
yields a constant (an
rvalue or a const
lvalue). Chapter 10 discusses const_iterator
s in more depth.
An iterator can point to any element in a sequence or to one position past the end. You cannot dereference an iterator that points to one past the end, but you can compare it with other iterators (provided it is not an output iterator) or, if it is a bidirectional or random access iterator, decrease its position so it points to a valid element of the sequence.
Iterators are often used in ranges. A range
has two iterators: a starting point and an ending point. The end
iterator typically points to one position past the last element in the
range. Thus, a range is often written using the mathematical notation of
[first
, last
), in which the square bracket means
first
is included in the range, and
the parenthesis means last
is
excluded from the range.
Like ordinary pointers, iterators can be uninitialized or
otherwise have invalid values, such as x.begin(
)
-
1
, in which x
is any container. It is your responsibility
to ensure that you dereference only valid iterators, that you don't let
iterators run past their valid end-points, and so on.
To create your own iterator class, see the iterator
class template.