______________________________________________________________________

  24   Iterators library                       [lib.iterators]

  ______________________________________________________________________

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

2 The   following  subclauses  describe  components  for  iterator  tags
  (_lib.iterator.tags_), predefined iterators  (_lib.predef.iterators_),
  stream  iterators  (_lib.stream.iterators_),  and  streambuf iterators
  (_lib.streambuf.iterators_).

3 Headers:

  --<stl iterators (TBD)>

4 Table 1:

              Table 1--Header <stl iterators (TBD)> synopsis

  +--------------------------------------------------------------------------+
  |            Type                                 Name(s)                  |
  +--------------------------------------------------------------------------+
  |Template classes:                                                         |
  |back_insert_iterator            ostream_iterator                          |
  |front_insert_iterator           reverse_bidirectional_iterator            |
  |insert_iterator                 reverse_iterator                          |
  |istream_iterator                                                          |
  +--------------------------------------------------------------------------+
  |Template structs:                                                         |
  |bidirectional_iterator          input_iterator                            |
  |forward_iterator                random_access_iterator                    |
  +--------------------------------------------------------------------------+
  |Template operators:                                                       |
  |operator+  (reverse_iterator)   operator== (reverse_bidir_iter)           |
  |operator-  (reverse_iterator)   operator== (reverse_iterator)             |
  |operator<  (reverse_iterator)   operator== (istream_iterator)             |
  +--------------------------------------------------------------------------+
  |Template functions:                                                       |
  |advance                         distance_type [5]   iterator_category [5] |
  |back_inserter                   front_inserter      value_type [5]        |
  |distance                        inserter                                  |
  +--------------------------------------------------------------------------+
  |Structs:                                                                  |
  |bidirectional_iterator_tag      output_iterator_tag                       |
  |forward_iterator_tag            random_access_iterator_tag                |
  |input_iterator_tag                                                        |
  |output_iterator                                                           |
  +--------------------------------------------------------------------------+
  |Function:                       iterator_category(output_iterator)        |
  +--------------------------------------------------------------------------+

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

  24.1.1  Examples of using iterator tags                 [lib.examples]

1 For all the regular pointer types we can define  value_type  and  dis­
  tance_type 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); }

2 Then,  if  we  want to implement a generic reverse function, we 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;
      }
    }

4 If there is an additional pointer type far such that the difference of
  two far pointers is of the type long, we 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); }

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_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.
  For example, we define that all the pointer types are  in  the  random
  access iterator category by:
    template <class T>
    inline random_access_iterator_tag iterator_category(T*) {
      return random_access_iterator_tag();
    }

6 For  a  user-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();
    }

7 If a template function evolve is well defined for bidirectional itera­
  tors, but can be implemented more efficiently for random access itera­
  tors, 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
    }

8 If a user wants to define  a  bidirectional  iterator  for  some  data
  structure  containing  double and such that it works on a large memory
  model of his computer, he can do it with:
    class MyIterator : public bidirectional_iterator<double, long> {

    // code implementing ++, etc.

  };

9 Then there is no need to  define  iterator_category,  value_type,  and
  distance_type on MyIterator.

  24.1.2  Library defined primitives            [lib.library.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.1.2.1  Standard iterator tags               [lib.std.iterator.tags]
  struct input_iterator_tag : empty {};
  struct output_iterator_tag : empty {};
  struct forward_iterator_tag : empty {};
  struct bidirectional_iterator_tag : empty {};
  struct random_access_iterator_tag : empty {};

  24.1.2.2  Basic iterators                        [lib.basic.iterators]
  template <class T, class Distance = ptrdiff_t> struct input_iterator : empty{};
  struct output_iterator : empty{};
  // output_iterator is not a template because output iterators
  // do not have either value type or distance type defined.

  template <class T, class Distance = ptrdiff_t> struct forward_iterator : empty{};
  template <class T, class Distance = ptrdiff_t> struct bidirectional_iterator
    : empty {};
  template <class T, class Distance = ptrdiff_t> struct random_access_iterator
    : empty {};

  24.1.2.3  iterator_category                    [lib.iterator.category]
  // iterator_category

  template <class T, class Distance>
  inline input_iterator_tag
  iterator_category(const input_iterator<T, Distance>&) {
    return input_iterator_tag();
  }
  inline output_iterator_tag iterator_category(const output_iterator&) {
    return output_iterator_tag();
  }
  template <class T, class Distance>
  inline forward_iterator_tag
  iterator_category(const forward_iterator<T, Distance>&) {
    return forward_iterator_tag();
  }
  template <class T, class Distance>
  inline bidirectional_iterator_tag
  iterator_category(const bidirectional_iterator<T, Distance>&) {
    return bidirectional_iterator_tag();
  }
  template <class T, class Distance>
  inline random_access_iterator_tag
  iterator_category(const random_access_iterator<T, Distance>&) {
    return random_access_iterator_tag();
  }
  template <class T>
  inline random_access_iterator_tag iterator_category(const T*) {
    return random_access_iterator_tag();
  }

  24.1.2.4  value_type                                  [lib.value.type]
  template <class T, class Distance>
  inline T* value_type(const input_iterator<T, Distance>&) {
    return (T*)(0);
  }
  template <class T, class Distance>
  inline T* value_type(const forward_iterator<T, Distance>&) {
    return (T*)(0);
  }

  template <class T, class Distance>
  inline T* value_type(const bidirectional_iterator<T, Distance>&) {
    return (T*)(0);
  }
  template <class T, class Distance>
  inline T* value_type(const random_access_iterator<T, Distance>&) {
    return (T*)(0);
  }
  template <class T>
  inline T* value_type(const T*) { return (T*)(0); }

  24.1.2.5  distance_type                            [lib.distance.type]
  // distance_type of iterator

  template <class T, class Distance>
  inline Distance* distance_type(const input_iterator<T, Distance>&) {
    return (Distance*)(0);
  }
  template <class T, class Distance>
  inline Distance* distance_type(const forward_iterator<T, Distance>&) {
    return (Distance*)(0);
  }
  template <class T, class Distance>
  inline Distance*
  distance_type(const bidirectional_iterator<T, Distance>&) {
    return (Distance*)(0);
  }
  template <class T, class Distance>
  inline Distance*
  distance_type(const random_access_iterator<T, Distance>&) {
    return (Distance*)(0);
  }
  template <class T>
  inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }

  24.1.3  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.   advance
  takes  negative  argument n for random access and bidirectional itera­
  tors only.  advance increments (or decrements for negative n) iterator
  reference  i  by  n.   distance increments n by the number of times it
  takes to get from first to last.
  template <class InputIterator, class Distance>
  inline void advance(InputIterator& i, Distance n);

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

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

  24.2  Predefined iterators                      [lib.predef.iterators]

  24.2.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 iter­
  ators with those iterator types for which operator* returns  something
  other than a reference type.

  24.2.1.1  Template class                      [lib.reverse.bidir.iter]
       reverse_bidirectional_iterator
  template <class BidirectionalIterator, class T, class Distance = ptrdiff_t>
  class reverse_bidirectional_iterator
    : public bidirectional_iterator<T, Distance> {
  protected:
    BidirectionalIterator current;
  public:
    reverse_bidirectional_iterator() {}
    reverse_bidirectional_iterator(BidirectionalIterator x) : current(x) {}
    operator BidirectionalIterator() { return current; }
    T operator*() {
      BidirectionalIterator tmp = current;
      return *--tmp;
    }
    reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>&
    operator++() {
      --current;
      return *this;
    }
    reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
    operator++(int) {
      reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
        tmp = *this;
      --current;
      return tmp;
    }

    reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>&
    operator--() {
      ++current;
      return *this;
    }
    reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
    operator--(int) {
      reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
        tmp = *this;
      ++current;
      return tmp;
    }
  };
  template <class BidirectionalIterator, class T, class Distance>
  inline bool
    operator==(
      const reverse_bidirectional_iterator<BidirectionalIterator,T,Distance>& x,
      const reverse_bidirectional_iterator<BidirectionalIterator,T,Distance>& y)
    {
      return x.current == y.current;
    }

  24.2.1.2  Template class reverse_iterator       [lib.reverse.iterator]
  template <class RandomAccessIterator, class T, class Distance = ptrdiff_t>
  class reverse_iterator : public random_access_iterator<T, Distance> {
  protected:
    RandomAccessIterator current;
  public:
    reverse_iterator() {}
    reverse_iterator(RandomAccessIterator x) : current(x) {}
    operator RandomAccessIterator() { return current; }
    T operator*() {
      RandomAccessIterator tmp = current;
      return *--tmp;
    }
    reverse_iterator<RandomAccessIterator, T, Distance>& operator++() {
      --current;
      return *this;
    }
    reverse_iterator<RandomAccessIterator, T, Distance> operator++(int) {
      reverse_iterator<RandomAccessIterator, T, Distance> tmp = *this;
      --current;
      return tmp;
    }
    reverse_iterator<RandomAccessIterator, T, Distance>& operator--() {
      ++current;
      return *this;
    }
    reverse_iterator<RandomAccessIterator, T, Distance> operator--(int) {
      reverse_iterator<RandomAccessIterator, T, Distance> tmp = *this;
      ++current;
      return tmp;
    }

    reverse_iterator<RandomAccessIterator, T, Distance>
    operator+(Distance n)   const {
      return reverse_iterator<RandomAccessIterator, T, Distance>(current - n);
    }
    reverse_iterator<RandomAccessIterator, T, Distance>&
    operator+=(Distance n) const {
      current -= n;
      return *this;
    }
    reverse_iterator<RandomAccessIterator, T, Distance>
    operator-(Distance n) const {
      return reverse_iterator<RandomAccessIterator, T, Distance>(current + n);
    }
    reverse_iterator<RandomAccessIterator, T, Distance>
    operator-(Distance n) const {
      current += n;
      return *this;
    }
    T operator[](Distance n) { return *(*this + n); }
  };
  template <class RandomAccessIterator, class T, class Distance>
  inline bool operator==(
    const reverse_iterator<RandomAccessIterator, T, Distance>& x,
    const reverse_iterator<RandomAccessIterator, T, Distance>& y)
  {
    return x.current == y.current;
  }
  template <class RandomAccessIterator, class T, class Distance>
  inline bool operator<(
    const reverse_iterator<RandomAccessIterator, T, Distance>& x,
    const reverse_iterator<RandomAccessIterator, T, Distance>& y)
  {
    return y.current < x.current;
  }
  template <class RandomAccessIterator, class T, class Distance>
  inline Distance operator-(
    const reverse_iterator<RandomAccessIterator, T, Distance>& x,
    const reverse_iterator<RandomAccessIterator, T, Distance>& y)
  {
    return y.current - x.current;
  }
  template <class RandomAccessIterator, class T, class Distance>
  inline reverse_iterator<RandomAccessIterator, T, Distance> operator+(
    Distance n,
    const reverse_iterator<RandomAccessIterator, T, Distance>& x)
  {
    return reverse_iterator<RandomAccessIterator, T, Distance>(current - n);
  }

1 There  is no way a default for T can be expressed in terms of Bidirec­
  tionalIterator because the value type cannot be deduced from  built-in
  iterators such as int*.  Otherwise, we would have written

  template <class BidirectionalIterator,
    class T = BidirectionalIterator::reference_type,
    class Distance = BidirectionalIterator::difference_type>
  class reverse_bidirectional_iterator: bidirectional_iterator<T, Distance> {

  /* ... */

  };

  24.2.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.2.2.1  Template class                    [lib.back.insert.iterator]
       back_insert_iterator
  template <class Container>
  class back_insert_iterator : public output_iterator {
  protected:
    Container& container;
  public:
    back_insert_iterator(Container& x) : container(x) {}
    back_insert_iterator<Container>&
    operator=(const Container::value_type& value) {
      container.push_back(value);
      return *this;
    }

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

  24.2.2.2  Template class                   [lib.front.insert.iterator]
       front_insert_iterator
  template <class Container>
  class front_insert_iterator : public output_iterator {
  protected:
    Container& container;
  public:
    front_insert_iterator(Container& x) : container(x) {}
    front_insert_iterator<Container>&
    operator=(const Container::value_type& value) {
      container.push_front(value);
      return *this;
    }
    front_insert_iterator<Container>& operator*() { return *this; }
    front_insert_iterator<Container>& operator++() { return *this; }
    front_insert_iterator<Container> operator++(int) { return *this; }
  };
  template <class Container>
  front_insert_iterator<Container> front_inserter(Container& x) {
    return front_insert_iterator<Container>(x);
  }

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

  24.3  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.  For example,
  partial_sum_copy(istream_iterator<double>(cin),  istream_iterator<double>(),
    ostream_iterator<double>(cout, "\n"));

2 reads  a  file  containing floating point numbers from cin, and prints
  the partial sums onto cout.

  24.3.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.  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 guarantee 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.
  template <class T, class Distance = ptrdiff_t>
  class istream_iterator : 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;
    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.3.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:
  template <class T>
  class ostream_iterator : public output_iterator {
  public:
    ostream_iterator(ostream& s);
    ostream_iterator(const char* delimiter);
    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  Streambuf iterators                    [lib.streambuf.iterators]

  +-------                 BEGIN BOX 1                -------+
  TO BE SPECIFIED.

  istreambuf_iterator  is  currently  part   of   <istream>,   subclause
  _lib.input.streams_.

  ostreambuf_iterator   is   currently   part  of  <ostream>,  subclause
  _lib.output.streams_.

  Both should be moved here.
  +-------                  END BOX 1                 -------+