Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  Iterators  - Pointer generalizations for traversal and modification of
  collections.

DESCRIPTION

         Input Iterator               Output Iterator
           read only                    write only
           forward moving               forward moving
              |                              |
              |                              |
              --------------------------------
                            |
                            |
                      Forward Iterator
                        read and write
                        forward moving
                            |
                            |
                      Bidirectional Iterator
                        read and write
                        moves forward or backward
                            |
                            |
                      Random Access Iterator
                        read and write
                        random access

  Iterators are a generalization of pointers that allow a C++ program to
  uniformly interact with different data structures.  The illustration below
  displays the five iterator categories defined by the standard library, and
  shows their hierarchical relationship.  Because standard library iterator
  categories are hierarchical, each category includes all the requirements of
  the categories above it.

  Because iterators are used to traverse and access containers, the nature of
  the container determines what type of iterator it generates.  And, because
  algorithms require specific iterator types as arguments, it is iterators
  that, for the most part, determine which standard library algorithms can be
  used with which standard library containers.

  To conform to the C++ standard, all container and sequence classes must
  provide their own iterators.  An instance of a container or sequence's
  iterator may be declared using either of the following:

  class name ::iterator
  class name ::const_iterator

  Containers and sequences must also provide const iterators to the beginning
  and end of their collections.  These may be accessed using the class
  members, begin() and end().

  The semantics of iterators are a generalization of the semantics of C++
  pointers.  Every template function that takes iterators will work using C++
  pointers for processing typed contiguous memory sequences.

  Iterators may be constant or mutable depending upon whether the  result of
  the operator* behaves as a reference or  as a reference to a constant.
  Constant iterators cannot satisfy the requirements of an output_iterator.

  Every iterator type guarantees that there is an iterator value that points
  past the last element of a corresponding container. This value is called
  the past-the-end  value.  No guarantee is made that this value is
  dereferencable.

  Every function provided by an iterator is required to be realized in
  amortized constant time.

KEY TO ITERATOR REQUIREMENTS

  The following key pertains to the iterator requirements listed below:

  a and b   values of type X

  n   value of distance type

  u, Distance, tmp and m   identifiers

  r   value of type X&

  t   value of type T

REQUIREMENTS FOR INPUT ITERATORS

  The following expressions must be valid for input iterators:

  X u(a)   copy constructor, u == a

  X u = a   assignment, u == a

  a == b, a != b   return value convertible to bool

  *a   a == b implies *a == *b

  a->m   equivalent to (*a).m

  ++r   returns X&

  r++   return value convertible to const X&

  *r++   returns type T

  For input iterators, a == b does not imply that ++a == ++b.

  Algorithms using input iterators should be single pass algorithms.  That is
  they should not pass through the same iterator twice.

  The value of type T does not have to be an lvalue.

REQUIREMENTS FOR OUTPUT ITERATORS

  The following expressions must be valid for output iterators:

  X(a)   copy constructor, a == X(a)

  X u(a)   copy constructor, u == a

  X u = a   assignment, u == a

  *a = t   result is not used

  ++r   returns X&

  r++   return value convertible to const X&

  *r++ = t   result is not used

  The only valid use for the operator* is on the left hand side of the
  assignment statement.

  Algorithms using output iterators should be single pass algorithms.  That
  is they should not pass through the same iterator twice.

REQUIREMENTS FOR FORWARD ITERATORS

  The following expressions must be valid for forward iterators:

  X u   u might have a singular value

  X()   X() might be singular

  X(a)   copy constructor, a == X(a)

  X u(a)   copy constructor, u == a

  X u = a   assignment, u == a

  a == b, a != b   return value convertible to bool

  *a   return value convertible to T&

  a->m   equivalent to (*a).m

  ++r   returns X&

  r++   return value convertible to const X&

  *r++   returns T&

  Forward iterators have the condition that a == b implies *a== *b.

  There are no restrictions on the number of passes an algorithm may make
  through the structure.

REQUIREMENTS FOR BIDIRECTIONAL ITERATORS

  A bidirectional iterator must meet all the requirements for forward
  iterators.  In addition, the following expressions must be valid:

  --r   returns X&

  r--   return value convertible to const X&

  *r--   returns T&

REQUIREMENTS FOR RANDOM ACCESS ITERATORS

  A random access iterator must meet all the requirements for bidirectional
  iterators.  In addition, the following expressions must be valid:

  r += n   Semantics of --r or ++r n times depending on the sign of n

  a + n, n + a   returns type X

  r -= n   returns X&, behaves as r += -n

  a - n   returns type X

  b - a   returns Distance

  a[n]   *(a+n), return value convertible to T

  a < b   total ordering relation

  a > b   total ordering relation opposite to <

  a <= b   !(a > b)

  a >= b   !(a < b)

  All relational operators return a value convertible to bool.

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement