______________________________________________________________________

  24   Iterators library                       [lib.iterators]

  ______________________________________________________________________

1 This clause describes components that C++ programs may use to  perform
  iterations     over     containers     (_lib.containers_),     streams
  (_lib.iostream.format_), and stream buffers (_lib.stream.buffers_).

2 The following subclauses describe iterator  requirements,  and  compo­
  nents for iterator primitives, predefined iterators, and stream itera­
  tors, as summarized in Table 1:

                    Table 1--Iterators library summary

       +-----------------------------------------------------------+
       |                  Subclause                     Header(s)  |
       +-----------------------------------------------------------+
       |_lib.iterator.requirements_ Requirements                   |
       +-----------------------------------------------------------+
       |_lib.iterator.primitives_ Iterator primitives              |
       |_lib.predef.iterators_ Predefined iterators     <iterator> |
       |_lib.stream.iterators_ Stream iterators                    |
       +-----------------------------------------------------------+

  24.1  Iterator requirements                [lib.iterator.requirements]

1 Iterators are a generalization of pointers that allow a C++ program 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, the library formal­
  izes not just the interfaces but also  the  semantics  and  complexity
  assumptions  of iterators.  All iterators i support the expression *i,
  resulting in a value of some class, enumeration, or built-in  type  T,
  called  the value type of the iterator.  All iterators i for which the
  expression (*i).m is well-defined, support the  expression  i->m  with
  the  same  semantics  as  (*i).m.  For every iterator type X for which
  equality is defined, there is a  corresponding  signed  integral  type
  called the distance type of the iterator.

2 Since  iterators  are an abstraction of pointers, their semantics is a
  generalization of most of the semantics  of  pointers  in  C++.   This
  ensures  that  every  template  function that takes iterators works as
  well with regular pointers.  This Standard defines five categories  of
  iterators,  according  to the operations defined on them: input itera­
  tors, output iterators, forward iterators, bidirectional iterators and

  random access iterators, as shown in Table 2.

               Table 2--Relations among iterator categories

       +----------------------------------------------------------+
       |Random access   -> Bidirectional   -> Forward   -> Input  |
       |                                                -> Output |
       +----------------------------------------------------------+

3 Forward iterators satisfy all the requirements of the input and output
  iterators and can be used whenever either kind is specified;  Bidirec­
  tional  iterators  also  satisfy  all  the requirements of the forward
  iterators and can be used whenever a forward  iterator  is  specified;
  Random  access iterators also satisfy all the requirements of bidirec­
  tional iterators and can be used whenever a bidirectional iterator  is
  specified.

4 Besides its category, a forward, bidirectional, or random access iter­
  ator can also be mutable or constant depending on whether  the  result
  of  the  expression  *i  behaves as a reference or as a reference to a
  constant.  Constant iterators do not satisfy the requirements for out­
  put iterators, and the result of the expression *i (for constant iter­
  ator i) cannot be used in an expression where an lvalue is required.

5 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 an iterator i for which the  expression  *i
  is defined are called dereferenceable.  The library never assumes that
  past-the-end values are dereferenceable.  Iterators can also have sin­
  gular values that are not associated with any container.  For example,
  after the declaration of an uninitialized pointer x (as with int* x;),
  x  must  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 over­
  written  the  same  way as any other value.  Dereferenceable and past-
  the-end values are always non-singular.

6 An iterator j is called reachable from an iterator i if  and  only  if
  there  is a finite sequence of applications of the expression ++i that
  makes i == j.  If j is reachable from i, they refer to the  same  con­
  tainer.

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

8 All  the categories of iterators require only those functions that are
  realizable for a given category in constant time (amortized).   There­
  fore,  requirement  tables  for the iterators do not have a complexity
  column.

9 In the following sections, a and b denote values of  X,  n  denotes  a
  value of the distance type Distance, u, tmp, and m denote identifiers,
  r denotes a value of X&, t denotes a value of value type T.

  24.1.1  Input iterators                          [lib.input.iterators]

1 A class or a built-in type X satisfies the requirements  of  an  input
  iterator  for the value type T if the following expressions are valid,
  where U is the type of any specified member of type  T,  as  shown  in
  Table 3:

                   Table 3--Input iterator requirements

  +----------------------------------------------------------------------------------+
  |expression       return type        operational            assertion/note         |
  |                                     semantics           pre/post-condition       |
  +----------------------------------------------------------------------------------+
  |X(a)                                               a == X(a).                     |
  |                                                   note: a destructor is assumed. |
  +----------------------------------------------------------------------------------+
  |X u(a);                                                                           |
  |X u = a;                                           post: u == a.                  |
  +----------------------------------------------------------------------------------+
  |a == b       convertible to bool                   == is an equivalence relation. |
  +----------------------------------------------------------------------------------+
  |a != b       convertible to bool   !(a == b)                                      |
  +----------------------------------------------------------------------------------+
  |*a           T                                     pre: a is dereferenceable.     |
  |                                                   a == b implies *a == *b.       |
  +----------------------------------------------------------------------------------+
  |a->m         U                     (*a).m          pre: (*a).m is well-defined.   |
  +----------------------------------------------------------------------------------+
  |++r          X&                                    pre: r is dereferenceable.     |
  |                                                   post: r is dereferenceable or  |
  |                                                   r is past-the-end.             |
  |                                                   &r == &++r.                    |
  +----------------------------------------------------------------------------------+
  |r++          convertible to con­   { X tmp = r;                                   |
  |             st X&                   ++r;                                         |
  |                                     return tmp;                                  |
  |                                   }                                              |
  +----------------------------------------------------------------------------------+
  |*r++         T                                                                    |
  +----------------------------------------------------------------------------------+

2 [Note: For input iterators, a == b does not imply ++a == ++b.  (Equal­
  ity does not guarantee the substitution property or referential trans­
  parency.)  Algorithms on input iterators should never attempt to  pass
  through  the  same  iterator  twice.  They should be single pass algo­
  rithms.  Value type T is not required to be  an  lvalue  type.   These
  algorithms  can  be used with istreams as the source of the input data
  through the istream_iterator class.   --end note]

  24.1.2  Output iterators                        [lib.output.iterators]

1 A class or a built-in type X satisfies the requirements of  an  output
  iterator if the following expressions are valid, as shown in Table 4:

                  Table 4--Output iterator requirements

  +---------------------------------------------------------------------------------+
  |expression      return type        operational            assertion/note         |
  |                                    semantics           pre/post-condition       |
  +---------------------------------------------------------------------------------+
  |X(a)                                              a = t is equivalent to X(a) =  |
  |                                                  t.                             |
  |                                                  note: a destructor is assumed. |
  +---------------------------------------------------------------------------------+
  |X u(a);                                                                          |
  |X u = a;                                                                         |
  +---------------------------------------------------------------------------------+
  |*a = t       result is not used                                                  |
  +---------------------------------------------------------------------------------+
  |++r          X&                                   &r == &++r.                    |
  +---------------------------------------------------------------------------------+
  |r++          convertible to       { X tmp = r;                                   |
  |             const X&               ++r;                                         |
  |                                    return tmp;                                  |
  |                                  }                                              |
  +---------------------------------------------------------------------------------+
  |*r++ = t     result is not used                                                  |
  +---------------------------------------------------------------------------------+

2 [Note: The only valid use of an operator* is on the left side  of  the
  assignment statement.  Assignment through the same value of the itera­
  tor happens only once.  Algorithms on output  iterators  should  never
  attempt  to pass through the same iterator twice.  They should be sin­
  gle pass algorithms.  Equality and inequality might  not  be  defined.
  Algorithms that take output iterators can be used with ostreams as the
  destination for placing data through  the  ostream_iterator  class  as
  well as with insert iterators and insert pointers.   --end note]

  24.1.3  Forward iterators                      [lib.forward.iterators]

1 A  class  or a built-in type X satisfies the requirements of a forward
  iterator if the following expressions are valid, as shown in Table 5:

                  Table 5--Forward iterator requirements

  +-------------------------------------------------------------------------------------+
  |expression       return type        operational             assertion/note           |
  |                                     semantics            pre/post-condition         |
  +-------------------------------------------------------------------------------------+
  |X u;                                               note: u might have a singular     |
  |                                                   value.                            |
  |                                                   note: a destructor is assumed.    |
  +-------------------------------------------------------------------------------------+
  |X()                                                note: X() might be singular.      |
  +-------------------------------------------------------------------------------------+
  |X(a)                                               a == X(a).                        |
  +-------------------------------------------------------------------------------------+
  |X u(a);                            X u; u = a;     post: u == a.                     |
  |X u = a;                                                                             |
  +-------------------------------------------------------------------------------------+
  |a == b       convertible to bool                   == is an equivalence relation.    |
  +-------------------------------------------------------------------------------------+
  |a != b       convertible to bool   !(a == b)                                         |
  +-------------------------------------------------------------------------------------+
  |r = a        X&                                    post: r == a.                     |
  +-------------------------------------------------------------------------------------+
  |*a           T&                                    pre: a is dereferenceable.        |
  |                                                   a == b implies *a == *b.          |
  |                                                   If X is mutable, *a = t is valid. |
  +-------------------------------------------------------------------------------------+
  |a->m         U&                    (*a).m          pre: (*a).m is well-defined.      |
  +-------------------------------------------------------------------------------------+
  |++r          X&                                    pre: r is dereferenceable.        |
  |                                                   post: r is dereferenceable or r   |
  |                                                   is past-the-end.                  |
  |                                                   r == s and r is dereferenceable   |
  |                                                   implies ++r == ++s.               |
  |                                                   &r == &++r.                       |
  +-------------------------------------------------------------------------------------+
  |r++          convertible to con­   { X tmp = r;                                      |
  |             st X&                   ++r;                                            |
  |                                     return tmp;                                     |
  |                                   }                                                 |
  +-------------------------------------------------------------------------------------+
  |*r++         T&                                                                      |
  +-------------------------------------------------------------------------------------+

2 [Note: The condition that a == b implies ++a == ++b (which is not true
  for input and output iterators) and the removal of the restrictions on
  the  number  of the assignments through the iterator (which applies to
  output iterators) allows the use of multi-pass  one-directional  algo­
  rithms with forward iterators.   --end note]

  24.1.4  Bidirectional iterators          [lib.bidirectional.iterators]

1 A  class or a built-in type X satisfies the requirements of a bidirec­
  tional iterator if, in addition to  satisfying  the  requirements  for
  forward  iterators,  the  following  expressions are valid as shown in
  Table 6:

  Table 6--Bidirectional iterator requirements (in addition to forward iterator)

  +----------------------------------------------------------------------------+
  |expression     return type       operational          assertion/note        |
  |                                  semantics         pre/post-condition      |
  +----------------------------------------------------------------------------+
  |--r          X&                                 pre: there exists s such    |
  |                                                that r == ++s.              |
  |                                                post: s is dereferenceable. |
  |                                                --(++r) == r.               |
  |                                                --r == --s implies r == s.  |
  |                                                &r == &--r.                 |
  +----------------------------------------------------------------------------+
  |r--          convertible to     { X tmp = r;                                |
  |             const X&             --r;                                      |
  |                                  return tmp;                               |
  |                                }                                           |
  +----------------------------------------------------------------------------+
  |*r--         convertible to T                                               |
  +----------------------------------------------------------------------------+

2 [Note: Bidirectional iterators  allow  algorithms  to  move  iterators
  backward as well as forward.   --end note]

  24.1.5  Random access iterators          [lib.random.access.iterators]

1 A  class  or  a built-in type X satisfies the requirements of a random
  access iterator if, in addition to  satisfying  the  requirements  for
  bidirectional  iterators, the following expressions are valid as shown
  in Table 7:

  Table 7--Random access iterator requirements (in addition to bidirectional iterator)

  +------------------------------------------------------------------------------------+
  |expression       return type         operational             assertion/note         |
  |                                      semantics            pre/post-condition       |
  +------------------------------------------------------------------------------------+
  |r += n       X&                    { Distance m =                                   |
  |                                   n;                                               |
  |                                     if (m >= 0)                                    |
  |                                       while (m--)                                  |
  |                                   ++r;                                             |
  |                                     else                                           |
  |                                       while (m++)                                  |
  |                                   --r;                                             |
  |                                     return r; }                                    |
  +------------------------------------------------------------------------------------+
  |a + n                              { X tmp = a;                                     |
  |             X                       return tmp +=   a + n == n + a.                |
  |                                   n; }                                             |
  |n + a                                                                               |
  +------------------------------------------------------------------------------------+
  |r -= n       X&                    return r += -n;                                  |
  +------------------------------------------------------------------------------------+
  |a - n        X                     { X tmp = a;                                     |
  |                                     return tmp -=                                  |
  |                                   n; }                                             |
  +------------------------------------------------------------------------------------+
  |b - a        Distance              { TBS }           pre: there exists a value n of |
  |                                                     Distance such that a + n == b. |
  |                                                     b == a + (b - a).              |
  +------------------------------------------------------------------------------------+
  |a[n]         convertible to T      *(a + n)                                         |
  +------------------------------------------------------------------------------------+
  |a < b        convertible to bool   b - a > 0         < is a total ordering relation |
  +------------------------------------------------------------------------------------+
  |a > b        convertible to bool   b < a             > is a total ordering relation |
  |                                                     opposite to <.                 |
  +------------------------------------------------------------------------------------+
  |a >= b       convertible to bool   !(a < b)                                         |
  +------------------------------------------------------------------------------------+
  |a <= b       convertible to bool   !(a > b)                                         |
  +------------------------------------------------------------------------------------+

  24.1.6  Iterator tags                              [lib.iterator.tags]

1 To implement algorithms only in terms of iterators, it is often neces­
  sary  to  infer  both of the value type and the distance type from the
  iterator.  To enable this task it is required that for an  iterator  i
  of   any   category   other   than  output  iterator,  the  expression
  value_type(i) returns  (T*)(0)  and  the  expression  distance_type(i)

  returns  (Distance*)(0).   For output iterators, these expressions are
  not required.

2 [Example: To implement a generic reverse function, a C++  program  can
  do the following:
  template <class BidirectionalIterator>
  inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
    __reverse(first, last, value_type(first), distance_type(first));
  }

3 where __reverse is defined as:
    template <class BidirectionalIterator, class T, class Distance>
    void __reverse(BidirectionalIterator first, BidirectionalIterator last, T*,
                   Distance*)
    {
      Distance n;
      distance(first, last, n); // see Iterator operations section
      --n;
      while (n > 0) {
        T tmp = *first;
        *first++ = *--last;
        *last = tmp;
        n -= 2;
      }
    }
   --end example]

4 [Note:  For  all  the  regular  pointer  types,  value_type() and dis­
  tance_type() can be defined with the help of:
    template <class T>
    inline T* value_type(const T*) { return (T*)(0); }
    template <class T>
    inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }

5 If there is an additional pointer type __far such that the  difference
  of  two  __far  pointers  is  of  the type long, an implementation may
  define:
    template <class T>
    inline T* value_type(const T __far *) { return (T*)(0); }
    template <class T>
    inline long* distance_type(const T __far *) { return (long*)(0); }
   --end note]

6 It is often desirable for a template function to find out what is  the
  most  specific category of its iterator argument, so that the function
  can select the most efficient algorithm at compile time.   To  facili­
  tate  this, the library introduces category tag classes which are used
  as  compile  time   tags   for   algorithm   selection.    They   are:
  input_iterator_tag,  output_iterator_tag,  forward_iterator_tag, bidi­
  rectional_iterator_tag and random_access_iterator_tag.  Every iterator
  i  must  have  an  expression  iterator_category(i) defined on it that
  returns the most specific category tag that describes its behavior.

7 [Example: If the pointer types are defined to be in the random  access
  iterator category by:
    template <class T>
    inline random_access_iterator_tag
      iterator_category(const T*)
        { return random_access_iterator_tag(); }

8 For  a program-defined iterator BinaryTreeIterator, it can be included
  into the bidirectional iterator category by saying:
    template <class T>
    inline bidirectional_iterator_tag iterator_category(
      const BinaryTreeIterator<T>&) {
      return bidirectional_iterator_tag();
    }
   --end example]

9 [Example: If a template function evolve() is well defined for bidirec­
  tional  iterators,  but can be implemented more efficiently for random
  access iterators, then the implementation is like:
    template <class BidirectionalIterator>
    inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {
      evolve(first, last, iterator_category(first));
    }
    template <class BidirectionalIterator>
    void evolve(BidirectionalIterator first, BidirectionalIterator last,
                bidirectional_iterator_tag) {
    // ... more generic, but less efficient algorithm
    }
    template <class RandomAccessIterator>
    void evolve(RandomAccessIterator first, RandomAccessIterator last,
      random_access_iterator_tag) {
    // ... more efficient, but less generic algorithm
    }
   --end example]

10[Example: If a C++ program wants to define  a  bidirectional  iterator
  for  some data structure containing double and such that it works on a
  large memory model of the implementation, it can do so with:
    class MyIterator : public bidirectional_iterator<double, long> {
    // code implementing ++, etc.
    };

11Then there is no need to  define  iterator_category,  value_type,  and
  distance_type on MyIterator.   --end example]

  Header <iterator> synopsislib.iterator.synopsis

  #include <cstddef>      // for ptrdiff_t
  #include <iosfwd>       // for istream, ostream
  #include <ios>          // for ios_traits
  #include <streambuf>    // for streambuf

  namespace std {
  // subclause _lib.library.primitives_, primitives:
    struct input_iterator_tag {};
    struct output_iterator_tag {};
    struct forward_iterator_tag {};
    struct bidirectional_iterator_tag {};
    struct random_access_iterator_tag {};
    template <class T, class Distance = ptrdiff_t> struct input_iterator {};
    struct output_iterator {};
    template <class T, class Distance = ptrdiff_t> struct forward_iterator {};
    template <class T, class Distance = ptrdiff_t>
      struct bidirectional_iterator {};
    template <class T, class Distance = ptrdiff_t>
      struct random_access_iterator {};
    template <class T, class Distance>
      input_iterator_tag iterator_category(const input_iterator<T,Distance>&);
    output_iterator_tag  iterator_category(const output_iterator&);
    template <class T, class Distance>
      forward_iterator_tag
        iterator_category(const forward_iterator<T,Distance>&);
    template <class T, class Distance>
      bidirectional_iterator_tag
        iterator_category(const bidirectional_iterator<T,Distance>&);
    template <class T, class Distance>
      random_access_iterator_tag
        iterator_category(const random_access_iterator<T,Distance>&);
    template <class T> random_access_iterator_tag iterator_category(const T*);
    template <class T, class Distance>
      T* value_type(const input_iterator<T,Distance>&);
    template <class T, class Distance>
      T* value_type(const forward_iterator<T,Distance>&);
    template <class T, class Distance>
      T* value_type(const bidirectional_iterator<T,Distance>&);
    template <class T, class Distance>
      T* value_type(const random_access_iterator<T,Distance>&);
    template <class T> T* value_type(const T*);
    template <class T, class Distance>
      Distance* distance_type(const input_iterator<T,Distance>&);
    template <class T, class Distance>
      Distance* distance_type(const forward_iterator<T,Distance>&);
    template <class T, class Distance>
      Distance* distance_type(const bidirectional_iterator<T,Distance>&);
    template <class T, class Distance>
      Distance* distance_type(const random_access_iterator<T,Distance>&);
    template <class T> ptrdiff_t* distance_type(const T*);

  // subclause _lib.iterator.operations_, iterator operations:
    template <class InputIterator, class Distance>
      void advance(InputIterator& i, Distance n);
    template <class InputIterator, class Distance>
      void distance(InputIterator first, InputIterator last, Distance& n);
  // subclause _lib.predef.iterators_, predefined iterators:
    template <class BidirectionalIterator, class T, class Reference = T&,
        class Pointer = T*, class Distance = ptrdiff_t>
      class reverse_bidirectional_iterator;
    template <class BidirectionalIterator, class T,
        class Reference, class Pointer, class Distance>
      bool operator==(
        const reverse_bidirectional_iterator
          <BidirectionalIterator,T,Reference,Pointer,Distance>& x,
        const reverse_bidirectional_iterator
          <BidirectionalIterator,T,Reference,Pointer,Distance>& y);
    template <class RandomAccessIterator, class T, class Reference = T&,
        class Pointer = T*, class Distance = ptrdiff_t>
      class reverse_iterator : public random_access_iterator<T,Distance>;
    template <class RandomAccessIterator, class T, class Reference,
        class Pointer, class Distance>
      bool operator==(
        const reverse_iterator
              <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
        const reverse_iterator
              <RandomAccessIterator,T,Reference,Pointer,Distance>& y);
    template <class RandomAccessIterator, class T, class Reference,
        class Pointer, class Distance>
      bool operator<(
        const reverse_iterator
              <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
        const reverse_iterator
              <RandomAccessIterator,T,Reference,Pointer,Distance>& y);
    template <class RandomAccessIterator, class T, class Reference,
        class Pointer, class Distance>
      Distance operator-(
        const reverse_iterator
              <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
        const reverse_iterator
              <RandomAccessIterator,T,Reference,Pointer,Distance>& y);
    template <class RandomAccessIterator, class T, class Reference,
        class Pointer, class Distance>
      reverse_iterator<RandomAccessIterator,T,Reference,Pointer,Distance>
        operator+(
          Distance n,
          const reverse_iterator
                <RandomAccessIterator,T,Reference,Pointer,Distance>& x);
    template <class Container> class back_insert_iterator;
    template <class Container>
      back_insert_iterator<Container> back_inserter(Container& x);
    template <class Container> class front_insert_iterator;
    template <class Container>
      front_insert_iterator<Container> front_inserter(Container& x);

    template <class Container> class insert_iterator;
    template <class Container, class Iterator>
      insert_iterator<Container> inserter(Container& x, Iterator i);
  // subclauses _lib.stream.iterators_, stream iterators:
    template <class T, class Distance = ptrdiff_t> class istream_iterator;
    template <class T, class Distance>
      bool operator==(const istream_iterator<T,Distance>& x,
                      const istream_iterator<T,Distance>& y);
    template <class T> class ostream_iterator;
    template<class charT, class traits = ios_traits<charT> >
      class istreambuf_iterator;
    template <class charT, class traits = ios_traits<charT> >
      bool operator==(istreambuf_iterator<charT,traits>& a,
                      istreambuf_iterator<charT,traits>& b);
    template <class charT, class traits = ios_traits<charT> >
      bool operator!=(istreambuf_iterator<charT,traits>& a,
                      istreambuf_iterator<charT,traits>& b);
    template <class charT, class traits = ios_char_traits<charT> >
      class ostreambuf_iterator;
    output_iterator iterator_category (const ostreambuf_iterator&);
    template<class charT, class traits = ios_char_traits<charT> >
      bool operator==(ostreambuf_iterator<charT,traits>& a,
                      ostreambuf_iterator<charT,traits>& b);
    template<class charT, class traits = ios_char_traits<charT> >
      bool operator!=(ostreambuf_iterator<charT,traits>& a,
                      ostreambuf_iterator<charT,traits>& b);
  }

  24.2  Iterator primitives                    [lib.iterator.primitives]

1 To simplify the task of defining the iterator_category, value_type and
  distance_type for user definable iterators, the library  provides  the
  following predefined classes and functions:

  24.2.1  Standard iterator tags                 [lib.std.iterator.tags]
  namespace std {
    struct input_iterator_tag {};
    struct output_iterator_tag {};
    struct forward_iterator_tag {};
    struct bidirectional_iterator_tag {};
    struct random_access_iterator_tag {};
  }

  24.2.2  Basic iterators                          [lib.basic.iterators]

  namespace std {
    template <class T, class Distance = ptrdiff_t>
       struct input_iterator {};
    struct output_iterator{};
    template <class T, class Distance = ptrdiff_t>
       struct forward_iterator {};
    template <class T, class Distance = ptrdiff_t>
       struct bidirectional_iterator {};
    template <class T, class Distance = ptrdiff_t>
       struct random_access_iterator {};
  }

1 [Note:  output_iterator  is not a template because output iterators do
  not have either value type or distance type defined.   --end note]

  24.2.3  iterator_category                      [lib.iterator.category]

  template <class T, class Distance>
    input_iterator_tag
      iterator_category(const input_iterator<T,Distance>&);

  Returns:
    input_iterator_tag().

  output_iterator_tag iterator_category(const output_iterator&);

  Returns:
    output_iterator_tag().

  template <class T, class Distance>
    forward_iterator_tag
      iterator_category(const forward_iterator<T,Distance>&);

  Returns:
    forward_iterator_tag().

  template <class T, class Distance>
    bidirectional_iterator_tag
      iterator_category(const bidirectional_iterator<T,Distance>&);

  Returns:
    bidirectional_iterator_tag().

  template <class T, class Distance>
    random_access_iterator_tag
      iterator_category(const random_access_iterator<T,Distance>&);

  Returns:
    random_access_iterator_tag().

  template <class T>
    random_access_iterator_tag iterator_category(const T*);

  Returns:
    random_access_iterator_tag().

  24.2.4  value_type                                    [lib.value.type]

  template <class T, class Distance>
    T* value_type(const input_iterator<T,Distance>&);
  template <class T, class Distance>
    T* value_type(const forward_iterator<T,Distance>&);
  template <class T, class Distance>
    T* value_type(const bidirectional_iterator<T,Distance>&);
  template <class T, class Distance>
    T* value_type(const random_access_iterator<T,Distance>&);
  template <class T> T* value_type(const T*);

  Returns:
    (T*)(0).

  24.2.5  distance_type                              [lib.distance.type]

  template <class T, class Distance>
    Distance* distance_type(const input_iterator<T,Distance>&);
  template <class T, class Distance>
    Distance* distance_type(const forward_iterator<T,Distance>&);
  template <class T, class Distance>
    Distance* distance_type(const bidirectional_iterator<T,Distance>&);
  template <class T, class Distance>
    Distance* distance_type(const random_access_iterator<T,Distance>&);

  Returns:
    (Distance*)(0).

  template <class T> ptrdiff_t* distance_type(const T*);

  Returns:
    (ptrdiff_t*)(0).

  24.2.6  Iterator operations                  [lib.iterator.operations]

1 Since only random access iterators provide  +  and  -  operators,  the
  library  provides  two template functions advance and distance.  These
  functions use + and - for random access iterators (and are, therefore,
  constant   time  for  them);  for  input,  forward  and  bidirectional

  iterators they use ++ to provide linear time implementations.

  template <class InputIterator, class Distance>
    void advance(InputIterator& i, Distance n);

  Requires:
    n may be negative only for random access  and  bidirectional  itera­
    tors.
  Effects:
    Increments (or decrements for negative n) iterator reference i by n.

  template <class InputIterator, class Distance>
    void distance(InputIterator first, InputIterator last, Distance& n);

  Effects:
    Increments n by the number of times it takes to get  from  first  to
    last.1)

  24.3  Predefined iterators                      [lib.predef.iterators]

  24.3.1  Reverse iterators                      [lib.reverse.iterators]

1 Bidirectional  and  random access iterators have corresponding reverse
  iterator adaptors that iterate through the data structure in the oppo­
  site  direction.   They  have the same signatures as the corresponding
  iterators.  The fundamental relation between a  reverse  iterator  and
  its   corresponding   iterator  i  is  established  by  the  identity:
  &*(reverse_iterator(i)) == &*(i - 1).

2 This mapping is dictated by the fact that  while  there  is  always  a
  pointer  past  the end of an array, there might not be a valid pointer
  before the beginning of an array.

3 The formal class parameter T of reverse iterators should be  instanti­
  ated  with the type that Iterator::operator* returns, which is usually
  a reference type.  For example, to obtain a reverse iterator for int*,
  one should declare reverse_iterator<int*, int&>.  To obtain a constant
  reverse iterator for int*, one should  declare  reverse_iterator<const
  int*, const int&>.

  +-------                 BEGIN BOX 1                -------+
  Corfield:  Shouldn't  the  above  be  reverse_iterator<int*,  int> and
  reverse_iterator<const int*, const int> respectively?  Later  template
  parameters  are  defined  as  T&  and T* which would lead to the (ill-
  formed) types int&&, const int&& and int&*, const int&*  respectively.
  +-------                  END BOX 1                 -------+
  _________________________
  1)  distance must be a three argument function storing the result into
  a reference instead of returning the result because the distance  type
  cannot be deduced from built-in iterator types such as int*.

  The  interface  thus  allows  one  to use reverse iterators with those
  iterator types for which operator* returns something other than a ref­
  erence type.

  24.3.1.1  Template class                      [lib.reverse.bidir.iter]
       reverse_bidirectional_iterator
  namespace std {
    template <class BidirectionalIterator, class T,
              class Reference = T&, class Pointer = T*,
              class Distance = ptrdiff_t>
    class reverse_bidirectional_iterator
      : public bidirectional_iterator<T,Distance> {
    protected:
      BidirectionalIterator current;
    public:
      reverse_bidirectional_iterator();
      explicit reverse_bidirectional_iterator(BidirectionalIterator x);
      BidirectionalIterator base() const;       // explicit
      Reference operator*() const;
      Pointer   operator->() const;
      reverse_bidirectional_iterator& operator++();
      reverse_bidirectional_iterator  operator++(int);
      reverse_bidirectional_iterator& operator--();
      reverse_bidirectional_iterator  operator--(int);
    };

  +-------                 BEGIN BOX 2                -------+
  Corfield: Motion 34 from Monterey added const to  the  following  mem­
  bers:  base,  operator*  and operator->.  Whilst this may well be fine
  for base, it seems wrong to have  const  member  functions  returning,
  respectively, a reference to non-const T and a pointer to non-const T.
  I think this should be reconsidered.
  +-------                  END BOX 2                 -------+

    template <class BidirectionalIterator, class T,
        class Reference, class Pointer, class Distance>
      bool operator==(
        const reverse_bidirectional_iterator
          <BidirectionalIterator,T,Reference,Pointer,Distance>& x,
        const reverse_bidirectional_iterator
          <BidirectionalIterator,T,Reference,Pointer,Distance>& y);
  }

1 [Note: There is no way a default for T can be expressed  in  terms  of
  BidirectionalIterator  because  the  value type cannot be deduced from
  built-in iterators such as int*.  Otherwise, it would have been  writ­
  ten as:
    template <class BidirectionalIterator,
      class T = typename BidirectionalIterator::reference_type,
      class Distance = typename BidirectionalIterator::difference_type>
    class reverse_bidirectional_iterator: bidirectional_iterator<T,Distance> {
    /* ... */
    };

   --end note]

  24.3.1.2                                  [lib.reverse.bidir.iter.ops]
       reverse_bidirectional_iterator
       operations

  24.3.1.2.1                               [lib.reverse.bidir.iter.cons]
       reverse_bidirectional_iterator
       constructor

  explicit reverse_bidirectional_iterator(BidirectionalIterator x);

  Effects:
    Initializes current with x.

  24.3.1.2.2  Conversion                   [lib.reverse.bidir.iter.conv]

  BidirectionalIterator base();   // explicit

  Returns:
    current

  24.3.1.2.3  operator*                 [lib.reverse.bidir.iter.op.star]

  Reference operator*();

  Effects:
      BidirectionalIterator tmp = current;
      return *--tmp;

  24.3.1.2.4  operator->                  [lib.reverse.bidir.iter.opref]

  Pointer operator->();

  Effects:
      return &(operator*());

  24.3.1.2.5  operator++                   [lib.reverse.bidir.iter.op++]

  reverse_bidirectional_iterator& operator++();

  Effects:
    --current;
  Returns:
    *this

  reverse_bidirectional_iterator operator++(int);

  Effects:
      reverse_bidirectional_iterator tmp = *this;
      --current;
      return tmp;

  24.3.1.2.6  operator--                   [lib.reverse.bidir.iter.op--]

  reverse_bidirectional_iterator& operator--();

  Effects:
    ++current
  Returns:
    *this

  reverse_bidirectional_iterator operator--(int);

  Effects:
      reverse_bidirectional_iterator tmp = *this;
      ++current;
      return tmp;

  24.3.1.2.7  operator==                   [lib.reverse.bidir.iter.op==]
  template <class BidirectionalIterator, class T,
      class Reference, class Pointer, class Distance>
    bool operator==(
      const reverse_bidirectional_iterator
        <BidirectionalIterator,T,Reference,Pointer,Distance>& x,
      const reverse_bidirectional_iterator
        <BidirectionalIterator,T,Reference,Pointer,Distance>& y);
  Returns:
    x.current == y.current.

  24.3.1.3  Template class reverse_iterator       [lib.reverse.iterator]
  namespace std {
    template <class RandomAccessIterator, class T,
              class Reference = T&, class Pointer = T*,
              class Distance = ptrdiff_t>
    class reverse_iterator : public random_access_iterator<T,Distance> {
    protected:
      RandomAccessIterator current;
    public:
      reverse_iterator();
      explicit reverse_iterator(RandomAccessIterator x);
      RandomAccessIterator base();        // explicit
      Reference operator*();
      Pointer   operator->();
      reverse_iterator& operator++();
      reverse_iterator  operator++(int);
      reverse_iterator& operator--();
      reverse_iterator  operator--(int);

      reverse_iterator  operator+ (Distance n) const;
      reverse_iterator& operator+=(Distance n);
      reverse_iterator  operator- (Distance n) const;
      reverse_iterator& operator-=(Distance n);
      Reference operator[](Distance n) const;
    };
  }

  +-------                 BEGIN BOX 3                -------+
  Corfield:  Motion  34 from Monterey added const to operator[].  Now we
  have a const member function that returns a reference to  non-const  T
  which I think is wrong.
  +-------                  END BOX 3                 -------+

      template <class RandomAccessIterator, class T,
                class Reference, class Pointer, class Distance>
        bool operator==(
          const reverse_iterator
             <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
          const reverse_iterator
             <RandomAccessIterator,T,Reference,Pointer,Distance>& y);
      template <class RandomAccessIterator, class T,
                class Reference, class Pointer, class Distance>
        bool operator<(
          const reverse_iterator
             <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
          const reverse_iterator
             <RandomAccessIterator,T,Reference,Pointer,Distance>& y);
      template <class RandomAccessIterator, class T,
                class Reference, class Pointer, class Distance>
        Distance operator-(
          const reverse_iterator
             <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
          const reverse_iterator
             <RandomAccessIterator,T,Reference,Pointer,Distance>& y);
      template <class RandomAccessIterator, class T,
                class Reference, class Pointer, class Distance>
        reverse_iterator
           <RandomAccessIterator,T,Reference,Pointer,Distance> operator+(
               Distance n,
               const reverse_iterator
                   <RandomAccessIterator,T,Reference,Pointer,Distance>& x);

  24.3.1.4  reverse_iterator operations           [lib.reverse.iter.ops]

  24.3.1.4.1  reverse_iterator constructor       [lib.reverse.iter.cons]

  explicit reverse_iterator(RandomAccessIterator x);

  Effects:
    Initializes current with x.

  24.3.1.4.2  Conversion                         [lib.reverse.iter.conv]

  RandomAccessIterator base();    // explicit

  Returns:
    current

  24.3.1.4.3  operator*                       [lib.reverse.iter.op.star]

  Reference operator*();

  Effects:
      RandomAccessIterator tmp = current;
      return *--tmp;

  24.3.1.4.4  operator->                        [lib.reverse.iter.opref]

  Pointer operator->();

  Effects:
      return &(operator*());

  24.3.1.4.5  operator++                         [lib.reverse.iter.op++]

  reverse_iterator& operator++();

  Effects:
    --current;
  Returns:
    *this

  reverse_iterator operator++(int);

  Effects:
      reverse_iterator tmp = *this;
      --current;
      return tmp;

  24.3.1.4.6  operator--                         [lib.reverse.iter.op--]

  reverse_iterator& operator--();

  Effects:
    ++current
  Returns:
    *this

  reverse_iterator operator--(int);

  Effects:
      reverse_iterator tmp = *this;
      ++current;
      return tmp;

  24.3.1.4.7  operator+                           [lib.reverse.iter.op+]

  reverse_iterator operator+(Distance n) const;

  Returns:
    reverse_iterator(current-n)

  24.3.1.4.8  operator+=                         [lib.reverse.iter.op+=]

  reverse_iterator& operator+=(Distance n);

  Effects:
    current -= n;
  Returns:
    *this

  24.3.1.4.9  operator-                           [lib.reverse.iter.op-]

  reverse_iterator operator-(Distance n) const;

  Returns:
    reverse_iterator(current+n)

  24.3.1.4.10  operator-=                        [lib.reverse.iter.op-=]

  reverse_iterator& operator-=(Distance n);

  Effects:
    current += n;
  Returns:
    *this

  24.3.1.4.11  operator[]                     [lib.reverse.iter.opindex]

  Reference operator[](Distance n) const;

  Returns:
    current[-n-1]

  +-------                 BEGIN BOX 4                -------+

  Corfield:  Motion  34  at Monterey did not ascribe semantics to opera­
  tor[] which I think was an accidental omission. I  think  returning  a
  reference to non-const T is a bad thing.
  +-------                  END BOX 4                 -------+

  24.3.1.4.12  operator==                        [lib.reverse.iter.op==]

  template <class RandomAccessIterator, class T,
            class Reference, class Pointer, class Distance>
    bool operator==(
      const reverse_iterator
         <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
      const reverse_iterator
         <RandomAccessIterator,T,Reference,Pointer,Distance>& y);

  Returns:
    x.current == y.current

  24.3.1.4.13  operator<                          [lib.reverse.iter.op<]

  template <class RandomAccessIterator, class T,
            class Reference, class Pointer, class Distance>
    bool operator<(
      const reverse_iterator
         <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
      const reverse_iterator
         <RandomAccessIterator,T,Reference,Pointer,Distance>& y);

  Returns:
    x.current < y.current

  24.3.1.4.14  operator-                       [lib.reverse.iter.opdiff]

  template <class RandomAccessIterator, class T,
            class Reference, class Pointer, class Distance>
    Distance operator-(
      const reverse_iterator
         <RandomAccessIterator,T,Reference,Pointer,Distance>& x,
      const reverse_iterator
         <RandomAccessIterator,T,Reference,Pointer,Distance>& y);

  Returns:
    y.current - x.current

  24.3.1.4.15  operator==                       [lib.reverse.iter.opsum]

  template <class RandomAccessIterator, class T,
            class Reference, class Pointer, class Distance>
    reverse_iterator
     <RandomAccessIterator,T,Reference,Pointer,Distance> operator+(
      Distance n,
      const reverse_iterator
       <RandomAccessIterator,T,Reference,Pointer,Distance>& x);

  Returns:
    reverse_iterator<RandomAccessIterator,T,Reference,Pointer,Distance>(x.current
    - n)

  24.3.2  Insert iterators                        [lib.insert.iterators]

1 To make it possible to deal with insertion in the same way as  writing
  into  an  array,  a  special  kind of iterator adaptors, called insert
  iterators,  are  provided  in  the  library.   With  regular  iterator
  classes,
    while (first != last) *result++ = *first++;

2 causes  a  range [first, last) to be copied into a range starting with
  result.  The same code with  result  being  an  insert  iterator  will
  insert  corresponding elements into the container.  This device allows
  all of the copying algorithms in the library to  work  in  the  insert
  mode instead of the regular overwrite mode.

3 An insert iterator is constructed from a container and possibly one of
  its iterators pointing to where insertion takes place if it is neither
  at  the  beginning  nor at the end of the container.  Insert iterators
  satisfy the requirements of output iterators.  operator*  returns  the
  insert  iterator  itself.   The  assignment  operator=(const  T& x) is
  defined on insert iterators to allow writing into them, it  inserts  x
  right  before  where the insert iterator is pointing.  In other words,
  an insert iterator is like a cursor pointing into the container  where
  the  insertion  takes place.  back_insert_iterator inserts elements at
  the end of a container, front_insert_iterator inserts elements at  the
  beginning  of  a container, and insert_iterator inserts elements where
  the iterator points to in a container.  back_inserter, front_inserter,
  and  inserter are three functions making the insert iterators out of a
  container.

  24.3.2.1  Template class                    [lib.back.insert.iterator]
       back_insert_iterator
  namespace std {
    template <class Container>
    class back_insert_iterator : public output_iterator {
    protected:
      Container& container;
    public:
      explicit back_insert_iterator(Container& x);
      back_insert_iterator<Container>&
        operator=(const typename Container::value_type& value);

      back_insert_iterator<Container>& operator*();
      back_insert_iterator<Container>& operator++();
      back_insert_iterator<Container>  operator++(int);
    };
    template <class Container>
      back_insert_iterator<Container> back_inserter(Container& x);
  }

  24.3.2.2  back_insert_iterator              [lib.back.insert.iter.ops]
       operations

  24.3.2.2.1  back_insert_iterator           [lib.back.insert.iter.cons]
       constructor

  explicit back_insert_iterator(Container& x);

  Effects:
    Initializes container with x.

  24.3.2.2.2                                  [lib.back.insert.iter.op=]
       back_insert_iterator::operator=

  back_insert_iterator<Container>&
    operator=(const typename Container::value_type& value);

  Effects:
    container.push_back(value);
  Returns:
    *this.

  24.3.2.2.3                                  [lib.back.insert.iter.op*]
       back_insert_iterator::operator*

  back_insert_iterator<Container>& operator*();

  Returns:
    *this.

  24.3.2.2.4                                 [lib.back.insert.iter.op++]
       back_insert_iterator::operator++

  back_insert_iterator<Container>& operator++();
  back_insert_iterator<Container>  operator++(int);

  Returns:
    *this.

  24.3.2.2.5  back_inserter                          [lib.back.inserter]

  template <class Container>
    back_insert_iterator<Container> back_inserter(Container& x);

  Returns:
    back_insert_iterator<Container>(x).

  24.3.2.3  Template class                   [lib.front.insert.iterator]
       front_insert_iterator
  namespace std {
    template <class Container>
    class front_insert_iterator : public output_iterator {
    protected:
      Container& container;
    public:
      explicit front_insert_iterator(Container& x);
      front_insert_iterator<Container>&
        operator=(const typename Container::value_type& value);
      front_insert_iterator<Container>& operator*();
      front_insert_iterator<Container>& operator++();
      front_insert_iterator<Container>  operator++(int);
    };
    template <class Container>
      front_insert_iterator<Container> front_inserter(Container& x);
  }
  Returns:
    front_insert_iterator<Container>(x).

  24.3.2.4  front_insert_iterator            [lib.front.insert.iter.ops]
       operations

  24.3.2.4.1  front_insert_iterator         [lib.front.insert.iter.cons]
       constructor

  explicit front_insert_iterator(Container& x);

  Effects:
    Initializes container with x.

  24.3.2.4.2                                 [lib.front.insert.iter.op=]
       front_insert_iterator::operator=

  front_insert_iterator<Container>&
    operator=(const typename Container::value_type& value);

  Effects:
    container.push_front(value);
  Returns:
    *this.

  24.3.2.4.3                                 [lib.front.insert.iter.op*]
       front_insert_iterator::operator*

  front_insert_iterator<Container>& operator*();

  Returns:
    *this.

  24.3.2.4.4                                [lib.front.insert.iter.op++]
       front_insert_iterator::operator++

  front_insert_iterator<Container>& operator++();
  front_insert_iterator<Container>  operator++(int);

  Returns:
    *this.

  24.3.2.4.5  front_inserter                        [lib.front.inserter]

  template <class Container>
    front_insert_iterator<Container> front_inserter(Container& x);

  Returns:
    front_insert_iterator<Container>(x).

  24.3.2.5  Template class insert_iterator         [lib.insert.iterator]
  namespace std {
    template <class Container>
    class insert_iterator : public output_iterator {
    protected:
      Container& container;
      typename Container::iterator iter;
    public:
      insert_iterator(Container& x, typename Container::iterator i);
      insert_iterator<Container>&
        operator=(const typename Container::value_type& value);
      insert_iterator<Container>& operator*();
      insert_iterator<Container>& operator++();
      insert_iterator<Container>  operator++(int);
    };
    template <class Container, class Iterator>
      insert_iterator<Container> inserter(Container& x, Iterator i);
  }

  24.3.2.6  insert_iterator operations             [lib.insert.iter.ops]

  24.3.2.6.1  insert_iterator constructor         [lib.insert.iter.cons]

  insert_iterator(Container& x, Iterator i);

  Effects:
    Initializes container with x and iter with i.

  24.3.2.6.2  insert_iterator::operator=           [lib.insert.iter.op=]

  insert_iterator<Container>&
    operator=(const typename Container::value_type& value);

  Effects:
        iter = container.insert(iter, value);
        ++iter;
  Returns:
    *this.

  24.3.2.6.3  insert_iterator::operator*           [lib.insert.iter.op*]

  insert_iterator<Container>& operator*();

  Returns:
    *this.

  24.3.2.6.4  insert_iterator::operator++         [lib.insert.iter.op++]

  insert_iterator<Container>& operator++();
  insert_iterator<Container>  operator++(int);

  Returns:
    *this.

  24.3.2.6.5  inserter                                    [lib.inserter]

  template <class Container>
    insert_iterator<Container> inserter(Container& x);

  Returns:
    insert_iterator<Container>(x,typename Container::iterator(i)).

  24.4  Stream iterators                          [lib.stream.iterators]

1 To make it possible for algorithmic templates to  work  directly  with
  input/output  streams,  appropriate iterator-like template classes are
  provided.

2 [Example:
  partial_sum_copy(istream_iterator<double>(cin),  istream_iterator<double>(),
    ostream_iterator<double>(cout, "\n"));
  reads a file containing floating point numbers from  cin,  and  prints
  the partial sums onto cout.   --end example]

  24.4.1  Template class istream_iterator         [lib.istream.iterator]

1 istream_iterator<T>  reads (using operator>>) successive elements from
  the input stream for which it  was  constructed.   After  it  is  con­
  structed,  and  every time ++ is used, the iterator reads and stores a
  value of T.  If the end of stream is reached ( operator void*() on the
  stream returns false), the iterator becomes equal to the end-of-stream
  iterator value.  The constructor with no arguments  istream_iterator()
  always constructs an end of stream input iterator object, which is the
  only legitimate iterator to be used for the end condition.  The result
  of operator* on an end of stream is not defined.  For any other itera­
  tor value a const T& is returned.  The result of operator-> on an  end
  of  stream is not defined.  For any other iterator value a const T* is
  returned.  It is impossible to store things  into  istream  iterators.
  The  main  peculiarity  of  the  istream iterators is the fact that ++
  operators are not equality preserving, that is, i == j does not  guar­
  antee  at  all  that ++i == ++j.  Every time ++ is used a new value is
  read.

2 The practical consequence of this fact is that istream  iterators  can
  be  used  only  for  one-pass algorithms, which actually makes perfect
  sense, since for multi-pass algorithms it is always  more  appropriate
  to  use  in-memory  data  structures.  Two end-of-stream iterators are
  always equal.  An end-of-stream iterator is not equal to a non-end-of-
  stream  iterator.  Two non-end-of-stream iterators are equal when they
  are constructed from the same stream.
  namespace std {
    template <class T, class Distance = ptrdiff_t>
    class istream_iterator : public input_iterator<T,Distance> {
    public:
      istream_iterator();
      istream_iterator(istream& s);
      istream_iterator(const istream_iterator<T,Distance>& x);
     ~istream_iterator();
      const T& operator*() const;
      const T* operator->() const;
      istream_iterator<T,Distance>& operator++();
      istream_iterator<T,Distance>  operator++(int);
    };
    template <class T, class Distance>
      bool operator==(const istream_iterator<T,Distance>& x,
                      const istream_iterator<T,Distance>& y);
  }

  24.4.2  Template class ostream_iterator         [lib.ostream.iterator]

1 ostream_iterator<T> writes (using operator<<) successive elements onto
  the  output  stream  from  which  it  was constructed.  If it was con­
  structed with char* as a constructor argument, this string,  called  a
  delimiter  string,  is written to the stream after every T is written.
  It is not possible to get a value out of  the  output  iterator.   Its
  only use is as an output iterator in situations like
    while (first != last) *result++ = *first++;

2 ostream_iterator is defined as:
  namespace std {
    template <class T>
    class ostream_iterator : public output_iterator {
    public:
      ostream_iterator(ostream& s);
      ostream_iterator(ostream& s, const char* delimiter);
      ostream_iterator(const ostream_iterator<T>& x);
     ~ostream_iterator();
      ostream_iterator<T>& operator=(const T& value);
      ostream_iterator<T>& operator*();
      ostream_iterator<T>& operator++();
      ostream_iterator<T>  operator++(int);
    };

  24.4.3  Template class                       [lib.istreambuf.iterator]
       istreambuf_iterator
  namespace std {
    template<class charT, class traits = ios_traits<charT> >
    class istreambuf_iterator {
    public:
      typedef charT                         char_type;
      typedef traits                        traits_type;
      typedef typename traits::int_type     int_type;
      typedef basic_streambuf<charT,traits> streambuf;
      typedef basic_istream<charT,traits>   istream;
      class proxy;
      public:
        istreambuf_iterator();
        istreambuf_iterator(istream& s);
        istreambuf_iterator(streambuf* s);
        istreambuf_iterator(const proxy& p);
        charT operator*();
        istreambuf_iterator<charT,traits>& operator++();
        proxy operator++(int);
        bool equal(istreambuf_iterator& b);
      private:
        streambuf* sbuf_;   exposition only
    };
  }

1 The template class  istreambuf_iterator  reads  successive  characters
  from  the  streambuf for which it was constructed.  operator* provides

  access to the current input character, if any.  Each  time  operator++
  is  evaluated,  the iterator advances to the next input character.  If
  the   end   of   stream   is   reached   (streambuf::sgetc()   returns
  traits::eof()), the iterator becomes equal to the end of stream itera­
  tor value.  The default constructor istreambuf_iterator() and the con­
  structor istreambuf_iterator(0) both construct an end of stream itera­
  tor object suitable for use as an end-of-range.

2 The result of operator*() on an end of stream is undefined.   For  any
  other  iterator  value  a  char_type is returned.  It is impossible to
  assign a character via an input iterator.

3 Note that in the input iterators, ++ operators are not  equality  pre­
  serving,  that  is,  i == j does not guarantee at all that ++i == ++j.
  Every time ++ is evaluated a new value is used.

  +-------                 BEGIN BOX 5                -------+
  The istream_iterator and ostream_iterator are  defined  only  for  the
  char-oriented,  but not the wchar_t-oriented or parameterized streams.
  This seems simply an oversight, and thus should be considered an  open
  issue.
  +-------                  END BOX 5                 -------+

4 The  practical consequence of this fact is that an istreambuf_iterator
  object can be used only for one-pass algorithms.  Two  end  of  stream
  iterators are always equal.  An end of stream iterator is not equal to
  a non-end of stream iterator.

  24.4.3.1  Template class              [lib.istreambuf.iterator::proxy]
       istreambuf_iterator::proxy
  namespace std {
    template <class charT, class traits = ios_traits<charT> >
    class istream_iterator<charT, traits>::proxy {
      charT keep_;
      basic_streambuf<charT,traits>* sbuf_;
      proxy(charT c,
            basic_streambuf<charT,traits>* sbuf);
        : keep_(c), sbuf_(sbuf) {}
    public:
      charT operator*() { return keep_; }
    };
  }

1 Class   istream_iterator<charT,traits>::proxy   provides  a  temporary
  placeholder as the return value of the post-increment operator  opera­
  tor++).   It  keeps  the character pointed to by the previous value of
  the iterator for some possible future access to get the character.

  24.4.3.2  istreambuf_iterator           [lib.istreambuf.iterator.cons]
       constructors

  istreambuf_iterator();

  Effects:
    Constructs the end-of-stream iterator.

  istreambuf_iterator(basic_istream<charT,traits>& s);

  Effects:
    Constructs  the  istream_iterator  pointing  to  the basic_streambuf
    object *(s.rdbuf()).

  istreambuf_iterator(const proxy& p);

  Effects:
    Constructs the istreambuf_iterator pointing to  the  basic_streambuf
    object related to the proxy object p.

  24.4.3.3                                [lib.istreambuf.iterator::op*]
       istreambuf_iterator::operator*

  charT operator*()

  Effects:
    Extract one character pointed to by the streambuf *sbuf_.

  24.4.3.4                               [lib.istreambuf.iterator::op++]
       istreambuf_iterator::operator++

  istreambuf_iterator<charT,traits>&
      istreambuf_iterator<charT,traits>::operator++();

  Effects:
    Advances the iterator and returns the result

  proxy istreambuf_iterator<charT,traits>::operator++(int);

  Effects:
    Advances the iterator and returns the proxy object keeping the char­
    acter pointed to by the previous iterator.

  24.4.3.5                              [lib.istreambuf.iterator::equal]
       istreambuf_iterator::equal

  bool equal(istreambuf_iterator<charT,traits>& b);

  Returns:
    true  if  and only if both iterators are either at end-of-stream, or
    are the end-of-stream value, regardless of what streambuf they iter­
    ate over.

  24.4.3.6  iterator_category                  [lib.iterator.category.i]

  input_iterator iterator_category(const istreambuf_iterator& s);

  Returns:
    the category of the iterator s.

  24.4.3.7  operator==                   [lib.istreambuf.iterator::op==]

  namespace std {
    template <class charT, class traits = ios_traits<charT> >
      bool operator==(istreambuf_iterator<charT,traits>& a,
                      istreambuf_iterator<charT,traits>& b);
  }

  Returns:
    a.equal(b).

  24.4.3.8  operator!=                   [lib.istreambuf.iterator::op!=]

  namespace std {
    template <class charT, class traits = ios_traits<charT> >
      bool operator!=(istreambuf_iterator<charT,traits>& a,
                      istreambuf_iterator<charT,traits>& b);
  }

  Returns:
    !a.equal(b).

  24.4.4  Template class                       [lib.ostreambuf.iterator]
       ostreambuf_iterator
  namespace std {
    template <class charT, class traits = ios_char_traits<charT> >
    class ostreambuf_iterator {
    public:
      typedef charT                         char_type;
      typedef traits                        traits_type;
      typedef basic_streambuf<charT,traits> streambuf;
      typedef basic_ostream<charT,traits>   ostream;

    public:
      ostreambuf_iterator();
      ostreambuf_iterator(ostream& s);
      ostreambuf_iterator(streambuf* s);
      ostreambuf_iterator& operator=(charT c);
      ostreambuf_iterator& operator*();
      ostreambuf_iterator& operator++();
      ostreambuf_iterator  operator++(int);
      bool equal(ostreambuf_iterator& b);
    private:
      streambuf* sbuf_;     exposition only
    };
    output_iterator iterator_category (const ostreambuf_iterator&);

    template<class charT, class traits = ios_char_traits<charT> >
      bool operator==(ostreambuf_iterator<charT,traits>& a,
                      ostreambuf_iterator<charT,traits>& b);
    template<class charT, class traits = ios_char_traits<charT> >
      bool operator!=(ostreambuf_iterator<charT,traits>& a,
                      ostreambuf_iterator<charT,traits>& b);
  }

1 The template class ostreambuf_iterator  writes  successive  characters
  onto  the output stream from which it was constructed.  It is not pos­
  sible to get a value out of the output iterator.

2 Two output iterators are equal if they are constructed with  the  same
  output streambuf.

  24.4.4.1  ostreambuf_iterator               [lib.ostreambuf.iter.cons]
       constructors

  ostreambuf_iterator();

  Effects:
    : sbuf_(0) {}

  ostreambuf_iterator(ostream& s);

  Effects:
    : sbuf_(s.rdbuf()) {}

  ostreambuf_iterator(streambuf* s);

  Effects:
    : sbuf_(s) {}

  ostreambuf_iterator<charT,traits>&
    operator=(charT c);

  Effects:
        sbuf_->sputc(c);
  Returns:
    *this.

  24.4.4.2  ostreambuf_iterator                [lib.ostreambuf.iter.ops]
       operations

  ostreambuf_iterator<charT,traits>& operator*();

  Returns:
    *this.

  ostreambuf_iterator<charT,traits>& operator++();
  ostreambuf_iterator<charT,traits>  operator++(int);

  Returns:
    *this.

  bool equal(ostreambuf_iterator& b);

  Returns:
    sbuf_ == b.sbuf.

  24.4.4.3                          [lib.ostreambuf.iterator.nonmembers]
       ostreambuf_iterator
       non-member operations

  output_iterator iterator_category (const ostreambuf_iterator&);

  Returns:
    output_iterator().

  template<class charT, class traits = ios_char_traits<charT> >
    bool operator==(ostreambuf_iterator<charT,traits>& a,
                    ostreambuf_iterator<charT,traits>& b);

  Returns:
    a.equal(b).

  template<class charT, class traits = ios_char_traits<charT> >
    bool operator!=(ostreambuf_iterator<charT,traits>& a,
                    ostreambuf_iterator<charT,traits>& b);

  Returns:
    !a.equal(b).