______________________________________________________________________

  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.

2 In  Table  3, the term the domain of == is used in the ordinary mathe­
  matical sense to denote the set of values over which ==  is  (required
  to be) defined.  This set can change over time.  Each algorithm places
  additional requirements on the domain of == for the iterator values it
  uses.  These requirements can be inferred from the uses that algorithm
  makes of == and !=.  [Example: the call find(a,b,x) is defined only if
  the value of a has the property p defined as follows: b has property p
  and a value i has property p if (*i==x) or if (*i!=x and ++i has prop­
  erty p).  ]

                   Table 3--Input iterator requirements

  +----------------------------------------------------------------------------------------+
  |operation          type                      semantics, pre/post-conditions             |
  +----------------------------------------------------------------------------------------+
  |X u(a);     X                     post: u is a copy of a                                |
  |                                  A destructor is assumed to be present and accessible. |
  +----------------------------------------------------------------------------------------+
  |u = a;      X                     result: u                                             |
  |                                  post: u is a copy of a                                |
  +----------------------------------------------------------------------------------------+
  |a == b      convertible to bool   == is an equivalence relation over its domain.        |
  +----------------------------------------------------------------------------------------+
  |a != b      convertible to bool   bool(a==b) != bool(a!=b) over the domain of ==        |
  +----------------------------------------------------------------------------------------+
  |*a          T                     pre: a is dereferenceable.                            |
  |                                  If a==b and (a,b) is in the domain of ==              |
  |                                  then *a is equivalent to *b.                          |
  +----------------------------------------------------------------------------------------+
  |a->m                              pre: (*a).m is well-defined                           |
  |                                  Equivalent to (*a).m                                  |
  +----------------------------------------------------------------------------------------+
  |++r         X&                    pre: r is dereferenceable.                            |
  |                                  post: r is dereferenceable or r is past-the-end.      |
  |                                  post: any copies of the previous value of r are no    |
  |                                  longer required either to be dereferenceable or to be |
  |                                  in the domain of ==.                                  |
  +----------------------------------------------------------------------------------------+
  |(void)r++                         equivalent to (void)++r                               |
  +----------------------------------------------------------------------------------------+
  |*r++        T                     { T tmp = *r; ++r; return tmp; }                      |
  +----------------------------------------------------------------------------------------+

3 [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.  ]

  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 determine the value and distance types that  correspond  to  a
  particular  iterator type.  Accordingly, it is required that if Itera­
  tor is the type of an iterator, the types

          iterator_traits<Iterator>::distance_type
          iterator_traits<Iterator>::value_type
          iterator_traits<Iterator>::iterator_category
  be defined as the iterator's distance type, value  type  and  iterator
  category, respectively.  In the case of an output iterator, the types
          iterator_traits<Iterator>::distance_type
          iterator_traits<Iterator>::value_type
  are both defined as void.

2 [Example:  To  implement a generic reverse function, a C++ program can
  do the following:
  template <class BidirectionalIterator>
  void reverse(BidirectionalIterator first, BidirectionalIterator last) {
     iterator_traits<BidirectionalIterator>::distance_type n =
           distance(first, last);
     --n;
     while(n > 0) {
         iterator_traits<BidirectionalIterator>::value_type tmp = *first;
         *first++ = * --last;
         *last = tmp;
         n -= 2;
     }
  }

3  --end example]

4 The template iterator_traits<Iterator> is defined as
    template<class Iterator> struct iterator_traits {
      typedef Iterator::distance_type distance_type;
      typedef Iterator::value_type value_type;
      typedef Iterator::iterator_category iterator_category;
    };
  It is specialized for pointers as
    template<class T> struct iterator_traits<T*> {
      typedef ptrdiff_t distance_type;
      typedef T value_type;
      typedef random_access_iterator_tag iterator_category;
    };
  [Note: If there is an additional pointer type __far such that the dif­
  ference of two __far is of type long, an implementation may define
    template<class T> struct iterator_traits<T __far*> {
      typedef ptrdiff_t distance_type;
      typedef T value_type;
      typedef random_access_iterator_tag iterator_category;
    };
   --end note]

5 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_itera­
  tor_tag,    output_iterator_tag,    forward_iterator_tag,     bidirec­
  tional_iterator_tag   and   random_access_iterator_tag.    For   every

  iterator of type  Iterator,  iterator_traits<Iterator>::iterator_cate­
  gory  must  be  defined  to  be  the  most  specific category tag that
  describes the iterator's behavior.

6 [Example: For a program-defined iterator BinaryTreeIterator, it  could
  be  included  into the bidirectional iterator category by specializing
  the iterator_traits template:
    template<class T> struct iterator_traits<BinaryTreeIterator<T> > {
      typedef ptrdiff_t distance_type;
      typedef T value_type;
      typedef bidirectional_iterator_tag iterator_category;
    };
  Typically, however, it would be easier to derive BinaryTreeIterator<T>
  from  iterator<bidirectional_iterator_tag,T,ptrdiff_t>.    --end exam­
  ple]

7 [Example: If evolve() is well defined for bidirectional iterators, but
  can  be implemented more efficiently for random access iterators, then
  the implementation is as follows:
    template <class BidirectionalIterator>
    inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {
      evolve(first, last,
        iterator_traits<BidirectionalIterator>::iterator_category());
    }
    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]

8 [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 iterator<bidirectional_iterator_tag, double, long> {
    // code implementing ++, etc.
    };

9 Then there is no need to specialize the iterator_traits,  template.
  --end example]

  24.2  Header <iterator> synopsis               [lib.iterator.synopsis]
  namespace std {
  // subclause _lib.library.primitives_, primitives:
    struct input_iterator_tag {};
    struct output_iterator_tag {};
    struct forward_iterator_tag: public input_iterator_tag {};
    struct bidirectional_iterator_tag: public forward_iterator_tag {};
    struct random_access_iterator_tag: public bidirectional_iterator_tag {};

    template<class Category, class T, class Distance=ptrdiff_t> struct iterator;

    template<class Iterator> struct iterator_traits;
    template<class T> struct iterator_traits<T*>;
  // subclause _lib.iterator.operations_, iterator operations:
    template <class InputIterator, class Distance>
      void advance(InputIterator& i, Distance n);
    template <class InputIterator>
      iterator_traits<InputIterator>::distance_type
      distance(InputIterator first, InputIterator last);
  // 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 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;

    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>
      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>
      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);
  // subclause _lib.stream.iterators_, stream iterators:
    template <class T, class charT, class traits = char_traits<charT>,
        class Distance = ptrdiff_t>
    class istream_iterator;
    template <class T, class charT, class traits, class Distance>
      bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
                      const istream_iterator<T,charT,traits,Distance>& y);
    template <class T, class charT, class traits, class Distance>
      bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
                      const istream_iterator<T,charT,traits,Distance>& y);

  +-------                      BEGIN BOX 1                     -------+
  Stockholm  motion  43,  N0974=96-0156, said to add a base class to the
  forward declaration of istream_iterator.  However,  the  C++  language
  does  not  support  such  syntax.   Upon  further investigation, other
  instances of base classes on forward declarations were  discovered  in
  this clause.  They have all been removed by the post-Stockholm editing
  group, because the information is redundant with the base class infor­
  mation  on the full class definition.  The change is marginally edito­
  rial, because the prior specification did not  convey  normative  con­
  tent.
  +-------                       END BOX 1                      -------+

    template <class T, class charT, class traits = char_traits<charT> >
        class ostream_iterator;

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

  24.3  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.3.1  Standard iterator tags                 [lib.std.iterator.tags]
  namespace std {
    struct input_iterator_tag {};
    struct output_iterator_tag {};
    struct forward_iterator_tag: public input_iterator_tag {};
    struct bidirectional_iterator_tag: public forward_iterator_tag {};
    struct random_access_iterator_tag: public bidirectional_iterator_tag {};
  }

  +-------                      BEGIN BOX 2                     -------+
  Clause lib.basic.iterators (formerly 24.3.2) deleted based  on  review
  by David Dodgson, 7/2/96
  +-------                       END BOX 2                      -------+

  24.3.2  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  itera­
  tors 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>
        iterator_traits<InputIterator>::distance_type
           distance(InputIterator first, InputIterator last);

  Effects:
    Returns the number of times it takes to get from first to last.
  Requires:
    last must be reachable from first.

  24.4  Predefined iterators                      [lib.predef.iterators]

  24.4.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>.  The interface thus allows one to use reverse itera­
  tors with those iterator types for which operator*  returns  something
  other than a reference type.

  24.4.1.1  Template class                      [lib.reverse.bidir.iter]
       reverse_bidirectional_iterator

  namespace std {
    template <class BidirectionalIterator,
              class T = iterator_traits<BidirectionalIterator>::value_type,
              class Reference = T&, class Pointer = T*,
              class Distance = iterator_traits<BidirectionalIterator::distance_type> >
    class reverse_bidirectional_iterator
      : public iterator<bidirectional_iterator_tag,T,Distance> {
    protected:
      BidirectionalIterator current;
    public:
      typedef BidirectionalIterator iterator_type;
      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);
    };
    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 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
  24.4.1.2                                  [lib.reverse.bidir.iter.ops]
       reverse_bidirectional_iterator
       operations

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

  explicit reverse_bidirectional_iterator(BidirectionalIterator x);

  Effects:
    Initializes current with x.

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

  BidirectionalIterator base() const;   // explicit

  Returns:
    current

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

  Reference operator*() const;

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

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

  Pointer operator->() const;

  Effects:
      return &(operator*());

  24.4.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.4.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.4.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.4.1.3  Template class reverse_iterator       [lib.reverse.iterator]
  namespace std {
    template <class RandomAccessIterator,
              class T = iterator_traits<RandomAccessIterator>::value_type&,
              class Reference = T&, class Pointer = T*,
              class Distance =
                    iterator_traits<RandomAccessIterator>::distance_type> >
    class reverse_iterator :
              public iterator<random_access_iterator_tag,T,Distance> {
    protected:
      RandomAccessIterator current;
    public:
      typedef RandomAccessIterator iterator_type;
      reverse_iterator();
      explicit reverse_iterator(RandomAccessIterator x);
      RandomAccessIterator base() const;        // explicit
      Reference operator*() const;
      Pointer   operator->() const;
      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;
    };
  }

      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>
        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>
        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.4.1.4  reverse_iterator operations           [lib.reverse.iter.ops]

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

  explicit reverse_iterator(RandomAccessIterator x);

  Effects:
    Initializes current with x.

  24.4.1.4.2  Conversion                         [lib.reverse.iter.conv]

  RandomAccessIterator base() const;    // explicit

  Returns:
    current

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

  Reference operator*() const;

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

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

  Pointer operator->() const;

  Effects:
      return &(operator*());

  24.4.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.4.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.4.1.4.7  operator+                           [lib.reverse.iter.op+]

  reverse_iterator operator+(Distance n) const;

  Returns:
    reverse_iterator(current-n)

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

  reverse_iterator& operator+=(Distance n);

  Effects:
    current -= n;
  Returns:
    *this

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

  reverse_iterator operator-(Distance n) const;

  Returns:
    reverse_iterator(current+n)

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

  reverse_iterator& operator-=(Distance n);

  Effects:
    current += n;
  Returns:
    *this

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

  Reference operator[](Distance n) const;

  Returns:
    current[-n-1]

  24.4.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.4.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.4.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.4.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.4.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.4.2.1  Template class                    [lib.back.insert.iterator]
       back_insert_iterator
  namespace std {
    template <class Container>
    class back_insert_iterator : public iterator<output_iterator_tag,void,void> {
    protected:
      Container& container;
    public:
      typedef Container container_type;
      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.4.2.2  back_insert_iterator              [lib.back.insert.iter.ops]
       operations

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

  explicit back_insert_iterator(Container& x);

  Effects:
    Initializes container with x.

  24.4.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.4.2.2.3                                  [lib.back.insert.iter.op*]
       back_insert_iterator::operator*

  back_insert_iterator<Container>& operator*();

  Returns:
    *this.

  24.4.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.4.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.4.2.3  Template class                   [lib.front.insert.iterator]
       front_insert_iterator
  namespace std {
    template <class Container>
    class front_insert_iterator : public iterator<output_iterator_tag,void,void> {
    protected:
      Container& container;
    public:
      typedef Container container_type;
      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);

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

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

  explicit front_insert_iterator(Container& x);

  Effects:
    Initializes container with x.

  24.4.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.4.2.4.3                                 [lib.front.insert.iter.op*]
       front_insert_iterator::operator*

  front_insert_iterator<Container>& operator*();

  Returns:
    *this.

  24.4.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.4.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.4.2.5  Template class insert_iterator         [lib.insert.iterator]
  namespace std {
    template <class Container>
    class insert_iterator : public iterator<output_iterator_tag,void,void> {
    protected:
      Container& container;
      typename Container::iterator iter;
    public:
      typedef Container container_type;
      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.4.2.6  insert_iterator operations             [lib.insert.iter.ops]

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

  insert_iterator(Container& x, typename Container::iterator i);

  Effects:
    Initializes container with x and iter with i.

  24.4.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.4.2.6.3  insert_iterator::operator*           [lib.insert.iter.op*]

  insert_iterator<Container>& operator*();

  Returns:
    *this.

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

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

  Returns:
    *this.

  24.4.2.6.5  inserter                                    [lib.inserter]

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

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

  24.5  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, char>(cin),
    istream_iterator<double, char>(),
    ostream_iterator<double, char>(cout, "\n"));
  reads  a  file  containing floating point numbers from cin, and prints
  the partial sums onto cout.   --end example]

  24.5.1  Template class istream_iterator         [lib.istream.iterator]

1 istream_iterator reads (using operator>>) successive elements from the
  input  stream  for which it was constructed.  After it is constructed,
  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 itera­
  tor  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 charT, class traits = char_traits<charT>,
        class Distance = ptrdiff_t>
    class istream_iterator : public iterator<input_iterator_tag,T,Distance> {
    public:
      typedef charT char_type
      typedef traits traits_type;
      typedef basic_istream<charT,traits> istream_type;
      istream_iterator();
      istream_iterator(istream_type& s);
      istream_iterator(const istream_iterator<T,charT,traits,Distance>& x);
     ~istream_iterator();

      const T& operator*() const;
      const T* operator->() const;
      istream_iterator<T,charT,traits,Distance>& operator++();
      istream_iterator<T,charT,traits,Distance>  operator++(int);
    };

  +-------                      BEGIN BOX 3                     -------+
  Stockholm  motion 43, N0974=96-0156, was obviously meant to change the
  template parameters of istream_iterator globally  and  uniformly,  but
  operator++ appears to have been overlooked.  It's been changed.
  +-------                       END BOX 3                      -------+

    template <class T, class charT, class traits, class Distance>
      bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
                      const istream_iterator<T,charT,traits,Distance>& y);
    template <class T, class charT, class traits, class Distance>
      bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
                      const istream_iterator<T,charT,traits,Distance>& y);
  }

  24.5.2  Template class ostream_iterator         [lib.ostream.iterator]

1 ostream_iterator  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 charT, class traits = char_traits<charT> >
    class ostream_iterator : public iterator<output_iterator_tag,void,void> {
    public:
      typedef charT char_type;
      typedef traits traits_type;
      typedef basic_ostream<charT,traits> ostream_type;
      ostream_iterator(ostream_type& s);
      ostream_iterator(ostream_type& s, const charT* delimiter);
      ostream_iterator(const ostream_iterator<T,charT,traits>& x);
     ~ostream_iterator();
      ostream_iterator<T,charT,traits>& operator=(const T& value);
      ostream_iterator<T,charT,traits>& operator*();
      ostream_iterator<T,charT,traits>& operator++();
      ostream_iterator<T,charT,traits>  operator++(int);
    };

  24.5.3  Template class                       [lib.istreambuf.iterator]
       istreambuf_iterator

  namespace std {
    template<class charT, class traits = char_traits<charT> >
    class istreambuf_iterator
       : public iterator<input_iterator_tag, charT, typename traits::off_type> {
    public:
      typedef charT                         char_type;
      typedef traits                        traits_type;
      typedef typename traits::int_type     int_type;
      typedef basic_streambuf<charT,traits> streambuf_type;
      typedef basic_istream<charT,traits>   istream_type;
      class proxy;
      public:
        istreambuf_iterator() throw();
        istreambuf_iterator(istream_type& s) throw();
        istreambuf_iterator(streambuf_type* s) throw();
        istreambuf_iterator(const proxy& p) throw();
        charT operator*() const;
        istreambuf_iterator<charT,traits>& operator++();
        proxy operator++(int);
        bool equal(istreambuf_iterator& b);
      private:
        streambuf_type* sbuf_;   exposition only
    };
    template <class charT, class traits>
      bool operator==(const istreambuf_iterator<charT,traits>& a,
                      const istreambuf_iterator<charT,traits>& b);

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

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_type::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 value 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.

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.5.3.1  Template class              [lib.istreambuf.iterator::proxy]
       istreambuf_iterator::proxy
  namespace std {
    template <class charT, class traits = char_traits<charT> >
    class istreambuf_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_; }
    };
  }

  +-------                      BEGIN BOX 4                     -------+
  Note:  The  member  class proxy is identified in the issues list as an
  implementation detail.  Expect it to be replaced by an opaque, unnamed
  type  to  which operator* can be applied yielding char_type, and which
  can be implicitly converted to istreambuf_iterator<>, but is otherwise
  unspecified.
  +-------                       END BOX 4                      -------+

1 Class  istreambuf_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.5.3.2  istreambuf_iterator           [lib.istreambuf.iterator.cons]
       constructors

  istreambuf_iterator() throw();

  Effects:
    Constructs the end-of-stream iterator.

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

  Effects:
    Constructs  an istreambuf_iterator<> that uses the basic_streambuf<>
    object *(s.rdbuf()), or *s,  respectively.   Constructs  an  end-of-
    stream iterator if s.rdbuf() is null.

  istreambuf_iterator(const proxy& p) throw();

  Effects:
    Constructs  a  istreambuf_iterator<> that uses the basic_streambuf<>
    object pointed to by the proxy object's constructor argument p.

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

  charT operator*() const

  Returns:
    The character obtained via the streambuf member sbuf_->sgetc().

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

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

  Effects:
    sbuf_->sbumpc().
  Returns:
    *this.

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

  Returns:
    proxy(sbuf_->sbumpc(), sbuf_).

  24.5.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 at end-of-stream, or neither
    is at end-of-stream, regardless of what streambuf object they use.

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

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

  Returns:
    a.equal(b).

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

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

  Returns:
    !a.equal(b).

  24.5.4  Template class                       [lib.ostreambuf.iterator]
       ostreambuf_iterator
  namespace std {
    template <class charT, class traits = char_traits<charT> >
    class ostreambuf_iterator : iterator<output_iterator_tag,void,void>{
    public:
      typedef charT                         char_type;
      typedef traits                        traits_type;
      typedef basic_streambuf<charT,traits> streambuf_type;
      typedef basic_ostream<charT,traits>   ostream_type;
    public:
      ostreambuf_iterator(ostream_type& s) throw();
      ostreambuf_iterator(streambuf_type* s) throw();
      ostreambuf_iterator& operator=(charT c);
      ostreambuf_iterator& operator*();
      ostreambuf_iterator& operator++();
      ostreambuf_iterator  operator++(int);
      bool failed() const throw();
    private:
      streambuf_type* sbuf_;     exposition only
    };

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 character value out of the output iterator.

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

  ostreambuf_iterator(ostream_type& s) throw();

  Requires:
    is not null.
  Effects:
    : sbuf_(s.rdbuf()) {}

  ostreambuf_iterator(streambuf_type* s) throw();

  Effects:
    : sbuf_(s) {}

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

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

  Effects:
    If  failed()  yields  false, calls sbuf_->sputc(c); otherwise has no
    effect.
  Returns:
    *this.

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

  Returns:
    *this.

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

  Returns:
    *this.

  bool failed() const throw();

  Returns:
    true  if  in  any  prior  use  of  member  operator=,  the  call  to
    sbuf_->sputc() returned traits::eof(); or false otherwise.