[ новости /+++ | форум | теги | ]

                       Standard C++ Library
             Copyright 1998, Rogue Wave Software, Inc.


NAME
     Iterators

      - Pointer generalizations for traversal and modification of
     collections.



DESCRIPTION
     Iterators are a generalization of pointers that allow a  C++
     program  to  uniformly  interact  with different data struc-
     tures. 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  con-
     tainers,  the nature of the container determines the type of
     iterator it  generates.  Also,  because  algorithms  require
     specific  iterator types as arguments, it is iterators that,
     for the most part, determine which  standard  library  algo-
     rithms can be used with which standard library containers.

     To conform to the C++ standard, all container  and  sequence
     classes must include their own iterator types. Each iterator
     may be a class defined within the container or may be a sim-
     ple pointer, whichever is appropriate.

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

     Because the semantics of iterators are a  generalization  of
     the  semantics of C++ pointers, every template function that
     takes iterators also works using C++ pointers to  contiguous
     memory sequences. For example, both of the following uses of
     the generic algorithm count are valid:


     list<int> 1;
     count(1.begin(), 1.end());
     int buf[4]={1,2,3,4};
     count(buf, buf+4);

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

     Every function included in 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 representing a distance between two iterators



     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 algo-
     rithms.  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  itera-
     tors:

     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.  They  should not pass through the same iterator
     twice.



REQUIREMENTS FOR FORWARD ITERATORS
     The following expressions must be valid for  forward  itera-
     tors:

     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  algo-
     rithm 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.

Партнёры:

Хостинг: