%!TEX root = std.tex
\rSec0[iterators]{Iterators library}

\rSec1[iterators.general]{General}

\pnum
This Clause describes components that \Cpp programs may use to perform
iterations over containers (Clause \ref{containers}),
streams~(\ref{iostream.format}),
and stream buffers~(\ref{stream.buffers}).

\pnum
The following subclauses describe
iterator requirements, and
components for
iterator primitives,
predefined iterators,
and stream iterators,
as summarized in Table~\ref{tab:iterators.lib.summary}.

\begin{libsumtab}{Iterators library summary}{tab:iterators.lib.summary}
\ref{iterator.requirements} & Requirements        &                           \\ \rowsep
\ref{iterator.primitives} & Iterator primitives   &   \tcode{<iterator>}      \\
\ref{predef.iterators} & Predefined iterators     &                           \\
\ref{stream.iterators} & Stream iterators         &                           \\
\end{libsumtab}


\rSec1[iterator.requirements]{Iterator requirements}

\rSec2[iterator.requirements.general]{In general}

\pnum
\indextext{requirements!iterator}%
Iterators are a generalization of pointers that allow a \Cpp 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 formalizes not just the interfaces but also the
semantics and complexity assumptions of iterators.
All input iterators
\tcode{i}
support the expression
\tcode{*i},
resulting in a value of some object type
\tcode{T},
called the
\term{value type}
of the iterator.
All output iterators support the expression
\tcode{*i = o}
where
\tcode{o}
is a value of some type that is in the set of types that are
\term{writable}
to the particular iterator type of
\tcode{i}.
All iterators
\tcode{i}
for which the expression
\tcode{(*i).m}
is well-defined, support the expression
\tcode{i->m}
with the same semantics as
\tcode{(*i).m}.
For every iterator type
\tcode{X}
for which
equality is defined, there is a corresponding signed integer type called the
\term{difference type}
of the iterator.

\pnum
Since iterators are an abstraction of pointers, their semantics is
a generalization of most of the semantics of pointers in \Cpp.
This ensures that every
function template
that takes iterators
works as well with regular pointers.
This International Standard defines
five categories of iterators, according to the operations
defined on them:
\techterm{input iterators},
\techterm{output iterators},
\techterm{forward iterators},
\techterm{bidirectional iterators}
and
\techterm{random access iterators},
as shown in Table~\ref{tab:iterators.relations}.

\begin{floattable}{Relations among iterator categories}{tab:iterators.relations}
{llll}
\topline
\textbf{Random Access}          &   $\rightarrow$ \textbf{Bidirectional}    &
$\rightarrow$ \textbf{Forward}  &   $\rightarrow$ \textbf{Input}            \\
                        &   &   &   $\rightarrow$ \textbf{Output}           \\
\end{floattable}

\pnum
Forward iterators satisfy all the requirements of input
iterators and can be used whenever
an input iterator is specified;
Bidirectional iterators also satisfy all the requirements of
forward iterators and can be used whenever a forward iterator is specified;
Random access iterators also satisfy all the requirements of bidirectional
iterators and can be used whenever a bidirectional iterator is specified.

\pnum
Iterators that further satisfy the requirements of output iterators are
called \defn{mutable iterator}{s}. Nonmutable iterators are referred to
as \defn{constant iterator}{s}.

\pnum
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 sequence.
These values are called
\term{past-the-end}
values.
Values of an iterator
\tcode{i}
for which the expression
\tcode{*i}
is defined are called
\term{dereferenceable}.
The library never assumes that past-the-end values are dereferenceable.
Iterators can also have singular values that are not associated with any
sequence.
\enterexample
After the declaration of an uninitialized pointer
\tcode{x}
(as with
\tcode{int* x;}),
\tcode{x}
must always be assumed to have a singular value of a pointer.
\exitexample
Results of most expressions are undefined for singular values;
the only exceptions are destroying an iterator that holds a singular value,
the assignment of a non-singular value to
an iterator that holds a singular value, and, for iterators that satisfy the
\tcode{DefaultConstructible} requirements, using a value-initialized iterator
as the source of a copy or move operation. \enternote This guarantee is not
offered for default initialization, although the distinction only matters for types
with trivial default constructors such as pointers or aggregates holding pointers.
\exitnote
In these cases the singular
value is overwritten the same way as any other value.
Dereferenceable
values are always non-singular.

\pnum
An iterator
\tcode{j}
is called
\term{reachable}
from an iterator
\tcode{i}
if and only if there is a finite sequence of applications of
the expression
\tcode{++i}
that makes
\tcode{i == j}.
If
\tcode{j}
is reachable from
\tcode{i},
they refer to elements of the same sequence.

\pnum
Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges.
A
\term{range}
is a pair of iterators that designate the beginning and end of the computation.
A range \range{i}{i}
is an empty range;
in general, a range \range{i}{j}
refers to the elements in the data structure starting with the element
pointed to by
\tcode{i}
and up to but not including the element pointed to by
\tcode{j}.
Range \range{i}{j}
is valid if and only if
\tcode{j}
is reachable from
\tcode{i}.
The result of the application of functions in the library to invalid ranges is
undefined.

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

\pnum
Destruction of an iterator may invalidate pointers and references
previously obtained from that iterator.

\pnum
An
\techterm{invalid}
iterator is an iterator that may be singular.\footnote{This definition applies to pointers, since pointers are iterators.
The effect of dereferencing an iterator that has been invalidated
is undefined.
}

\pnum
In the following sections,
\tcode{a}
and
\tcode{b}
denote values of type
\tcode{X} or \tcode{const X},
\tcode{difference_type} and \tcode{reference} refer to the
types \tcode{iterator_traits<X>::difference_type} and
\tcode{iterator_traits<X>::reference}, respectively,
\tcode{n}
denotes a value of
\tcode{difference_type},
\tcode{u},
\tcode{tmp},
and
\tcode{m}
denote identifiers,
\tcode{r}
denotes a value of
\tcode{X\&},
\tcode{t}
denotes a value of value type
\tcode{T},
\tcode{o}
denotes a value of some type that is writable to the output iterator.
\enternote For an iterator type \tcode{X} there must be an instantiation
of \tcode{iterator_traits<X>}~(\ref{iterator.traits}). \exitnote

\rSec2[iterator.iterators]{Iterator}

\pnum
The \tcode{Iterator} requirements form the basis of the iterator concept
taxonomy; every iterator satisfies the \tcode{Iterator} requirements. This
set of requirements specifies operations for dereferencing and incrementing
an iterator. Most algorithms will require additional operations to
read~(\ref{input.iterators}) or write~(\ref{output.iterators}) values, or
to provide a richer set of iterator movements~(\ref{forward.iterators},
\ref{bidirectional.iterators}, \ref{random.access.iterators}).)

\pnum
A type \tcode{X} satisfies the \tcode{Iterator} requirements if:

\begin{itemize}
\item \tcode{X} satisfies the \tcode{CopyConstructible}, \tcode{CopyAssignable}, and
\tcode{Destructible} requirements~(\ref{utility.arg.requirements}) and lvalues
of type \tcode{X} are swappable (\ref{swappable.requirements}), and

\item the expressions in Table~\ref{tab:iterator.requirements} are valid and have
the indicated semantics.
\end{itemize}

\begin{libreqtab4b}
{Iterator requirements}
{tab:iterator.requirements}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead

\tcode{*r}          &
  \tcode{reference} &
                            &
  pre: \tcode{r} is dereferenceable.  \\ \rowsep

\tcode{++r}         &
  \tcode{X\&}       &
                            &
                    \\

\end{libreqtab4b}

\rSec2[input.iterators]{Input iterators}

\pnum
A class or pointer type
\tcode{X}
satisfies the requirements of an input iterator for the value type
\tcode{T}
if
X satisfies the \tcode{Iterator}~(\ref{iterator.iterators}) and
\tcode{EqualityComparable} (Table~\ref{equalitycomparable}) requirements and
the expressions in Table~\ref{tab:iterator.input.requirements} are valid and have
the indicated semantics.

\pnum
In Table~\ref{tab:iterator.input.requirements}, the term
\techterm{the domain of \tcode{==}}
is used in the ordinary mathematical sense to denote
the set of values over which
\tcode{==} is (required to be) defined.
This set can change over time.
Each algorithm places additional requirements on the domain of
\tcode{==} for the iterator values it uses.
These requirements can be inferred from the uses that algorithm
makes of \tcode{==} and \tcode{!=}.
\enterexample
the call \tcode{find(a,b,x)}
is defined only if the value of \tcode{a}
has the property \textit{p}
defined as follows:
\tcode{b} has property \textit{p}
and a value \tcode{i}
has property \textit{p}
if
\tcode{(*i==x)}
or if
\tcode{(*i!=x}
and
\tcode{++i}
has property
\tcode{p}).
\exitexample

\begin{libreqtab4b}
{Input iterator requirements (in addition to Iterator)}
{tab:iterator.input.requirements}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead
\tcode{a != b}                  &
 contextually convertible to \tcode{bool}    &
 \tcode{!(a == b)}                              &
 pre: \orange{a}{b} is in the domain of \tcode{==}. \\ \rowsep

\tcode{*a}                      &
 convertible to \tcode{T}       &
                                &
 pre: \tcode{a} is dereferenceable.\br
 The expression\br \tcode{(void)*a, *a} is equivalent to \tcode{*a}.\br
 If \tcode{a == b} and \orange{a}{b} is in the domain of \tcode{==}
 then \tcode{*a} is equivalent to \tcode{*b}.  \\ \rowsep
\tcode{a->m}                    &
                                &
 \tcode{(*a).m}                                &
 pre: \tcode{a} is dereferenceable. \\ \rowsep
\tcode{++r}                     &
 \tcode{X\&}                    &
                                &
 pre: \tcode{r} is dereferenceable.\br
 post: \tcode{r} is dereferenceable or \tcode{r} is past-the-end.\br
 post: any copies of the previous value of \tcode{r} are no longer
 required either to be dereferenceable or to be in the domain of \tcode{==}.    \\ \rowsep

\tcode{(void)r++}               &
                                &
                                &
 equivalent to \tcode{(void)++r}    \\ \rowsep

\tcode{*r++}                    &
 convertible to \tcode{T}       &
 \tcode{\{ T tmp = *r;}\br
 \tcode{++r;}\br
 \tcode{return tmp; \}} & \\
\end{libreqtab4b}

\pnum
\enternote
For input iterators,
\tcode{a == b}
does not imply
\tcode{++a == ++b}.
(Equality does not guarantee the substitution property or referential transparency.)
Algorithms on input iterators should never attempt to pass through the same iterator twice.
They should be
\term{single pass}
algorithms.
Value type T is not required to be a \tcode{CopyAssignable} type (Table~\ref{copyassignable}).
These algorithms can be used with istreams as the source of the input data through the
\tcode{istream_iterator}
class template.
\exitnote

\rSec2[output.iterators]{Output iterators}

\pnum
A class or pointer type
\tcode{X}
satisfies the requirements of an output iterator
if \tcode{X} satisfies the \tcode{Iterator} requirements~(\ref{iterator.iterators})
and the expressions in Table~\ref{tab:iterator.output.requirements}
are valid and have the indicated semantics.

\begin{libreqtab4b}
{Output iterator requirements (in addition to Iterator)}
{tab:iterator.output.requirements}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead
\tcode{*r = o}      &
 result is not used &
                    &
 \remark\ After this operation \tcode{r} is not required to be dereferenceable.\br
 post: \tcode{r} is incrementable. \\ \rowsep

\tcode{++r}         &
 \tcode{X\&}        &
                    &
 \tcode{\&r == \&++r}.\br
 \remark\ After this operation \tcode{r} is not required to be dereferenceable.\br
 post: \tcode{r} is incrementable. \\ \rowsep

\tcode{r++}         &
 convertible to \tcode{const X\&}   &
 \tcode{\{ X tmp = r;}\br
 \tcode{  ++r;}\br
 \tcode{  return tmp; \}}   &
 \remark\ After this operation \tcode{r} is not required to be dereferenceable.\br
 post: \tcode{r} is incrementable. \\ \rowsep

\tcode{*r++ = o}    &
 result is not used &&
 \remark\ After this operation \tcode{r} is not required to be dereferenceable.\br
 post: \tcode{r} is incrementable. \\
\end{libreqtab4b}

\pnum
\enternote
The only valid use of an
\tcode{operator*}
is on the left side of the assignment statement.
\textit{Assignment through the same value of the iterator happens only once.}
Algorithms on output iterators should never attempt to pass through the same iterator twice.
They should be
\term{single 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
\tcode{ostream_iterator}
class as well as with insert iterators and insert pointers.
\exitnote

\rSec2[forward.iterators]{Forward iterators}

\pnum
A class or pointer type
\tcode{X}
satisfies the requirements of a forward iterator if

\begin{itemize}
\item \tcode{X} satisfies the requirements of an input iterator~(\ref{input.iterators}),

\item X satisfies the \tcode{DefaultConstructible}
requirements~(\ref{utility.arg.requirements}),

\item if \tcode{X} is a mutable iterator, \tcode{reference} is a reference to \tcode{T};
if \tcode{X} is a const iterator, \tcode{reference} is a reference to \tcode{const T},

\item the expressions in Table~\ref{tab:iterator.forward.requirements}
are valid and have the indicated semantics, and

\item objects of type \tcode{X} offer the multi-pass guarantee, described below.
\end{itemize}

\pnum
The domain of == for forward iterators is that of iterators over the same
underlying sequence. However, value-initialized iterators may be compared and
shall compare equal to other value-initialized iterators of the same type.
\enternote value initialized iterators behave as if they refer past the end of
the same empty sequence \exitnote

\pnum
Two dereferenceable iterators \tcode{a} and \tcode{b} of type \tcode{X} offer the
\defn{multi-pass guarantee} if:

\begin{itemize}
\item \tcode{a == b} implies \tcode{++a == ++b} and
\item \tcode{X} is a pointer type or the expression
\tcode{(void)++X(a), *a} is equivalent to the expression \tcode{*a}.
\end{itemize}

\pnum
\enternote
The requirement that
\tcode{a == b}
implies
\tcode{++a == ++b}
(which is not true for input and output iterators)
and the removal of the restrictions on the number of the assignments through
a mutable iterator
(which applies to output iterators)
allows the use of multi-pass one-directional algorithms with forward iterators.
\exitnote

\begin{libreqtab4b}
{Forward iterator requirements (in addition to input iterator)}
{tab:iterator.forward.requirements}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead
\tcode{r++}         &
 convertible to \tcode{const X\&}   &
 \tcode{\{ X tmp = r;}\br
 \tcode{  ++r;}\br
 \tcode{  return tmp; \}}&  \\ \rowsep

\tcode{*r++}        &
 \tcode{reference}     &&  \\
\end{libreqtab4b}

\pnum
If \tcode{a} and \tcode{b} are equal, then either \tcode{a} and \tcode{b}
are both dereferenceable
or else neither is dereferenceable.

\pnum
If \tcode{a} and \tcode{b} are both dereferenceable, then \tcode{a == b}
if and only if
\tcode{*a} and \tcode{*b} are bound to the same object.

\rSec2[bidirectional.iterators]{Bidirectional iterators}

\pnum
A class or pointer type
\tcode{X}
satisfies the requirements of a bidirectional iterator if,
in addition to satisfying the requirements for forward iterators,
the following expressions are valid as shown in Table~\ref{tab:iterator.bidirectional.requirements}.

\begin{libreqtab4b}
{Bidirectional iterator requirements (in addition to forward iterator)}
{tab:iterator.bidirectional.requirements}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead
\tcode{\dcr r}      &
 \tcode{X\&}        &
                    &
 pre: there exists \tcode{s} such that \tcode{r == ++s}.\br
 post: \tcode{r} is dereferenceable.\br
 \tcode{\dcr(++r) == r}.\br
 \tcode{\dcr r == \dcr s} implies \tcode{r == s}.\br
 \tcode{\&r == \&\dcr r}.   \\ \hline

\tcode{r\dcr}           &
 convertible to \tcode{const X\&}   &
 \tcode{\{ X tmp = r;}\br
 \tcode{  \dcr r;}\br
 \tcode{  return tmp; \}}&  \\ \rowsep

\tcode{*r\dcr}      &
 \tcode{reference}   &&  \\
\end{libreqtab4b}

\pnum
\enternote
Bidirectional iterators allow algorithms to move iterators backward as well as forward.
\exitnote

\rSec2[random.access.iterators]{Random access iterators}

\pnum
A class or pointer type
\tcode{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~\ref{tab:iterator.random.access.requirements}.

\begin{libreqtab4b}
{Random access iterator requirements (in addition to bidirectional iterator)}
{tab:iterator.random.access.requirements}
\\ \topline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endfirsthead
\continuedcaption\\
\hline
\lhdr{Expression}   &   \chdr{Return type}  &   \chdr{Operational}  &   \rhdr{Assertion/note}       \\
                    &                       &   \chdr{semantics}    &   \rhdr{pre-/post-condition}   \\ \capsep
\endhead
\tcode{r += n}      &
 \tcode{X\&}        &
 \tcode{\{ difference_type m = n;}\br
 \tcode{  if (m >= 0)}\br
 \tcode{    while (m\dcr)}\br
 \tcode{      ++r;}\br
 \tcode{  else}\br
 \tcode{    while (m++)}\br
 \tcode{      \dcr r;}\br
 \tcode{  return r; \}}&    \\ \rowsep

\tcode{a + n}\br
\tcode{n + a}       &
 \tcode{X}          &
 \tcode{\{ X tmp = a;}\br
 \tcode{  return tmp += n; \}}  &
 \tcode{a + n == n + a}.        \\ \rowsep

\tcode{r -= n}      &
 \tcode{X\&}        &
 \tcode{return r += -n;}    &   \\ \rowsep

\tcode{a - n}       &
 \tcode{X}          &
 \tcode{\{ X tmp = a;}\br
 \tcode{  return tmp -= n; \}}  &   \\ \rowsep

\tcode{b - a}       &
 \tcode{difference_type}   &
 \tcode{return n}   &
 pre: there exists a value \tcode{n} of type \tcode{difference_type} such that \tcode{a + n == b}.\br
 \tcode{b == a + (b - a)}.  \\ \rowsep

\tcode{a[n]}        &
 convertible to \tcode{reference}  &
 \tcode{*(a + n)}   &   \\ \rowsep

\tcode{a < b}       &
 contextually
 convertible to \tcode{bool}    &
 \tcode{b - a > 0}  &
 \tcode{<} is a total ordering relation \\ \rowsep

\tcode{a > b}       &
 contextually
 convertible to \tcode{bool}    &
 \tcode{b < a}      &
 \tcode{>} is a total ordering relation opposite to \tcode{<}.  \\ \rowsep

\tcode{a >= b}      &
 contextually
 convertible to \tcode{bool}    &
 \tcode{!(a < b)}   &   \\ \rowsep

\tcode{a <= b}      &
 contextually
 convertible to \tcode{bool}.    &
 \tcode{!(a > b)}   &   \\
\end{libreqtab4b}

\rSec1[iterator.synopsis]{Header \tcode{<iterator>}\ synopsis}

\indexlibrary{\idxhdr{iterator}}%
\begin{codeblock}
namespace std {
  // \ref{iterator.primitives}, primitives:
  template<class Iterator> struct iterator_traits;
  template<class T> struct iterator_traits<T*>;

  template<class Category, class T, class Distance = ptrdiff_t,
       class Pointer = T*, class Reference = T&> struct iterator;

  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 { };

  // \ref{iterator.operations}, iterator operations:
  template <class InputIterator, class Distance>
    void advance(InputIterator& i, Distance n);
  template <class InputIterator>
    typename iterator_traits<InputIterator>::difference_type
    distance(InputIterator first, InputIterator last);
  template <class ForwardIterator>
    ForwardIterator next(ForwardIterator x,
      typename std::iterator_traits<ForwardIterator>::difference_type n = 1);
  template <class BidirectionalIterator>
    BidirectionalIterator prev(BidirectionalIterator x,
      typename std::iterator_traits<BidirectionalIterator>::difference_type n = 1);

  // \ref{predef.iterators}, predefined iterators:
  template <class Iterator> class reverse_iterator;

  template <class Iterator1, class Iterator2>
    bool operator==(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator!=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);

  template <class Iterator1, class Iterator2>
    auto operator-(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y) ->decltype(y.base() - x.base());
  template <class Iterator>
    reverse_iterator<Iterator>
      operator+(
    typename reverse_iterator<Iterator>::difference_type n,
    const reverse_iterator<Iterator>& x);

  template <class Iterator>
    reverse_iterator<Iterator> make_reverse_iterator(Iterator i);    

  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>
    insert_iterator<Container> inserter(Container& x, typename Container::iterator i);

  template <class Iterator> class move_iterator;
  template <class Iterator1, class Iterator2>
    bool operator==(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator!=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

  template <class Iterator1, class Iterator2>
    auto operator-(
    const move_iterator<Iterator1>& x,
    const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
  template <class Iterator>
    move_iterator<Iterator> operator+(
      typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);
  template <class Iterator>
    move_iterator<Iterator> make_move_iterator(Iterator i);

  // \ref{stream.iterators}, stream iterators:
  template <class T, class charT = char, 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);

  template <class T, class charT = char, 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;

  // \ref{iterator.range}, range access:
  template <class C> auto begin(C& c) -> decltype(c.begin());
  template <class C> auto begin(const C& c) -> decltype(c.begin());
  template <class C> auto end(C& c) -> decltype(c.end());
  template <class C> auto end(const C& c) -> decltype(c.end());
  template <class T, size_t N> constexpr T* begin(T (&array)[N]) noexcept;
  template <class T, size_t N> constexpr T* end(T (&array)[N]) noexcept;
  template <class C> constexpr auto cbegin(const C& c) noexcept(noexcept(std::begin(c)))
    -> decltype(std::begin(c));
  template <class C> constexpr auto cend(const C& c) noexcept(noexcept(std::end(c)))
    -> decltype(std::end(c));
  template <class C> auto rbegin(C& c) -> decltype(c.rbegin());
  template <class C> auto rbegin(const C& c) -> decltype(c.rbegin());
  template <class C> auto rend(C& c) -> decltype(c.rend());
  template <class C> auto rend(const C& c) -> decltype(c.rend());
  template <class T, size_t N> reverse_iterator<T*> rbegin(T (&array)[N]);
  template <class T, size_t N> reverse_iterator<T*> rend(T (&array)[N]);
  template <class E> reverse_iterator<const E*> rbegin(initializer_list<E> il);
  template <class E> reverse_iterator<const E*> rend(initializer_list<E> il);
  template <class C> auto crbegin(const C& c) -> decltype(std::rbegin(c));
  template <class C> auto crend(const C& c) -> decltype(std::rend(c));
}
\end{codeblock}

\rSec1[iterator.primitives]{Iterator primitives}

\pnum
To simplify the task of defining iterators, the library provides
several classes and functions:

\rSec2[iterator.traits]{Iterator traits}

\pnum
To implement algorithms only in terms of iterators, it is often necessary to
determine the value and
difference types that correspond to a particular iterator type.
Accordingly, it is required that if
\tcode{Iterator}
is the type of an iterator,
the types

\begin{codeblock}
iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category
\end{codeblock}

be defined as the iterator's difference type, value type and iterator category, respectively.
In addition, the types

\begin{codeblock}
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
\end{codeblock}

shall be defined as the iterator's reference and pointer types, that is, for an
iterator object \tcode{a}, the same type as the type of \tcode{*a} and \tcode{a->},
respectively. In the case of an output iterator, the types

\begin{codeblock}
iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
\end{codeblock}

may be defined as \tcode{void}.

\pnum
The template
\tcode{iterator_traits<Iterator>}
is defined as

\begin{codeblock}
namespace std {
  template<class Iterator> struct iterator_traits {
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
    typedef typename Iterator::iterator_category iterator_category;
  };
}
\end{codeblock}

\pnum
It is specialized for pointers as

\begin{codeblock}
namespace std {
  template<class T> struct iterator_traits<T*> {
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef random_access_iterator_tag iterator_category;
  };
}
\end{codeblock}

and for pointers to const as

\begin{codeblock}
namespace std {
  template<class T> struct iterator_traits<const T*> {
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef const T* pointer;
    typedef const T& reference;
    typedef random_access_iterator_tag iterator_category;
  };
}
\end{codeblock}

\pnum
\enternote
If there is an additional pointer type
\tcode{\,\xname{far}}
such that the difference of two
\tcode{\,\xname{far}}
is of type
\tcode{long},
an implementation may define

\begin{codeblock}
  template<class T> struct iterator_traits<T @\xname{far}@*> {
    typedef long difference_type;
    typedef T value_type;
    typedef T @\xname{far}@* pointer;
    typedef T @\xname{far}@& reference;
    typedef random_access_iterator_tag iterator_category;
  };
\end{codeblock}
\exitnote

\pnum
\enterexample
To implement a generic
\tcode{reverse}
function, a \Cpp program can do the following:

\begin{codeblock}
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
  typename iterator_traits<BidirectionalIterator>::difference_type n =
    distance(first, last);
  --n;
  while(n > 0) {
    typename iterator_traits<BidirectionalIterator>::value_type
     tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}
\end{codeblock}
\exitexample

\rSec2[iterator.basic]{Basic iterator}

\pnum
The
\tcode{iterator}
template may be used as a base class to ease the definition of required types
for new iterators.

\begin{codeblock}
namespace std {
  template<class Category, class T, class Distance = ptrdiff_t,
    class Pointer = T*, class Reference = T&>
  struct iterator {
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
  };
}
\end{codeblock}

\rSec2[std.iterator.tags]{Standard iterator tags}

\pnum
\indexlibrary{\idxcode{input_iterator_tag}}%
\indexlibrary{\idxcode{output_iterator_tag}}%
\indexlibrary{\idxcode{forward_iterator_tag}}%
\indexlibrary{\idxcode{bidirectional_iterator_tag}}%
\indexlibrary{\idxcode{random_access_iterator_tag}}%
It is often desirable for a
function template specialization
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 facilitate this, the
library introduces
\techterm{category tag}
classes which are used as compile time tags for algorithm selection.
They are:
\tcode{input_iterator_tag},
\tcode{output_iterator_tag},
\tcode{forward_iterator_tag},
\tcode{bidirectional_iterator_tag}
and
\tcode{random_access_iterator_tag}.
For every iterator of type
\tcode{Iterator},
\tcode{iterator_traits<Iterator>::it\-er\-a\-tor_ca\-te\-go\-ry}
shall be defined to be the most specific category tag that describes the
iterator's behavior.

\begin{codeblock}
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 { };
}
\end{codeblock}

\pnum
\indexlibrary{\idxcode{empty}}%
\indexlibrary{\idxcode{input_iterator_tag}}%
\indexlibrary{\idxcode{output_iterator_tag}}%
\indexlibrary{\idxcode{forward_iterator_tag}}%
\indexlibrary{\idxcode{bidirectional_iterator_tag}}%
\indexlibrary{\idxcode{random_access_iterator_tag}}%
\enterexample
For a program-defined iterator
\tcode{BinaryTreeIterator},
it could be included
into the bidirectional iterator category by specializing the
\tcode{iterator_traits}
template:

\begin{codeblock}
template<class T> struct iterator_traits<BinaryTreeIterator<T> > {
  typedef std::ptrdiff_t difference_type;
  typedef T value_type;
  typedef T* pointer;
  typedef T& reference;
  typedef bidirectional_iterator_tag iterator_category;
};
\end{codeblock}

Typically, however, it would be easier to derive
\tcode{BinaryTreeIterator<T>}
from
\tcode{iterator<bidirectional_iterator_tag,T,ptrdiff_t,T*,T\&>}.
\exitexample

\pnum
\enterexample
If
\tcode{evolve()}
is well defined for bidirectional iterators, but can be implemented more
efficiently for random access iterators, then the implementation is as follows:

\begin{codeblock}
template <class BidirectionalIterator>
inline void
evolve(BidirectionalIterator first, BidirectionalIterator last) {
  evolve(first, last,
    typename 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{codeblock}
\exitexample

\pnum
\enterexample
If a \Cpp program wants to define a bidirectional iterator for some data structure containing
\tcode{double}
and such that it
works on a large memory model of the implementation, it can do so with:

\begin{codeblock}
class MyIterator :
  public iterator<bidirectional_iterator_tag, double, long, T*, T&> {
  // code implementing \tcode{++}, etc.
};
\end{codeblock}

\pnum
Then there is no need to specialize the
\tcode{iterator_traits}
template.
\exitexample

\rSec2[iterator.operations]{Iterator operations}

\pnum
Since only random access iterators provide
\tcode{+}
and
\tcode{-}
operators, the library provides two
function templates
\tcode{advance}
and
\tcode{distance}.
These
function templates
use
\tcode{+}
and
\tcode{-}
for random access iterators (and are, therefore, constant
time for them); for input, forward and bidirectional iterators they use
\tcode{++}
to provide linear time
implementations.

\indexlibrary{\idxcode{advance}}%
\begin{itemdecl}
template <class InputIterator, class Distance>
  void advance(InputIterator& i, Distance n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
\tcode{n}
shall be negative only for bidirectional and random access iterators.

\pnum
\effects
Increments (or decrements for negative
\tcode{n})
iterator reference
\tcode{i}
by
\tcode{n}.
\end{itemdescr}

\indexlibrary{\idxcode{distance}}%
\begin{itemdecl}
  template<class InputIterator>
      typename iterator_traits<InputIterator>::difference_type
         distance(InputIterator first, InputIterator last);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
If \tcode{InputIterator} meets the requirements of random access iterator,
returns \tcode{(last - first)}; otherwise, returns
the number of increments needed to get from
\tcode{first}
to
\tcode{last}.

\pnum
\requires
If \tcode{InputIterator} meets the requirements of random access iterator,
\tcode{last} shall be reachable from \tcode{first} or \tcode{first} shall be
reachable from \tcode{last}; otherwise,
\tcode{last}
shall be reachable from
\tcode{first}.
\end{itemdescr}

\indexlibrary{\idxcode{next}}%
\begin{itemdecl}
template <class ForwardIterator>
  ForwardIterator next(ForwardIterator x,
    typename std::iterator_traits<ForwardIterator>::difference_type n = 1);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Equivalent to \tcode{advance(x, n); return x;}
\end{itemdescr}

\indexlibrary{\idxcode{prev}}%
\begin{itemdecl}
template <class BidirectionalIterator>
  BidirectionalIterator prev(BidirectionalIterator x,
    typename std::iterator_traits<BidirectionalIterator>::difference_type n = 1);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Equivalent to \tcode{advance(x, -n); return x;}
\end{itemdescr}

\rSec1[predef.iterators]{Iterator adaptors}

\rSec2[reverse.iterators]{Reverse iterators}

\pnum
Class template \tcode{reverse_iterator} is an iterator adaptor that iterates from the end of the sequence defined by its underlying iterator to the beginning of that sequence.
The fundamental relation between a reverse iterator and its corresponding iterator
\tcode{i}
is established by the identity:
\tcode{\&*(reverse_iterator(i)) == \&*(i - 1)}.

\rSec3[reverse.iterator]{Class template \tcode{reverse_iterator}}

\indexlibrary{\idxcode{reverse_iterator}}%
\begin{codeblock}
namespace std {
  template <class Iterator>
  class reverse_iterator : public
        iterator<typename iterator_traits<Iterator>::iterator_category,
        typename iterator_traits<Iterator>::value_type,
        typename iterator_traits<Iterator>::difference_type,
        typename iterator_traits<Iterator>::pointer,
        typename iterator_traits<Iterator>::reference> {
  public:
    typedef Iterator                                            iterator_type;
    typedef typename iterator_traits<Iterator>::difference_type difference_type;
    typedef typename iterator_traits<Iterator>::reference       reference;
    typedef typename iterator_traits<Iterator>::pointer         pointer;

    reverse_iterator();
    explicit reverse_iterator(Iterator x);
    template <class U> reverse_iterator(const reverse_iterator<U>& u);
    template <class U> reverse_iterator& operator=(const reverse_iterator<U>& u);

    Iterator 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+ (difference_type n) const;
    reverse_iterator& operator+=(difference_type n);
    reverse_iterator  operator- (difference_type n) const;
    reverse_iterator& operator-=(difference_type n);
    @\unspec@ operator[](difference_type n) const;
  protected:
    Iterator current;
  };

  template <class Iterator1, class Iterator2>
    bool operator==(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator!=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<=(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    auto operator-(
      const reverse_iterator<Iterator1>& x,
      const reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base());
  template <class Iterator>
    reverse_iterator<Iterator> operator+(
      typename reverse_iterator<Iterator>::difference_type n,
      const reverse_iterator<Iterator>& x);

  template <class Iterator>
    reverse_iterator<Iterator> make_reverse_iterator(Iterator i);      
}
\end{codeblock}

\rSec3[reverse.iter.requirements]{\tcode{reverse_iterator} requirements}

\pnum
The template parameter
\tcode{Iterator}
shall meet all the requirements of a Bidirectional Iterator~(\ref{bidirectional.iterators}).

\pnum
Additionally,
\tcode{Iterator}
shall meet the requirements of a Random Access Iterator~(\ref{random.access.iterators})
if any of the members
\tcode{operator+}~(\ref{reverse.iter.op+}),
\tcode{operator-}~(\ref{reverse.iter.op-}),
\tcode{operator+=}~(\ref{reverse.iter.op+=}),
\tcode{operator-=}~(\ref{reverse.iter.op-=}),
\tcode{operator\,[]}~(\ref{reverse.iter.opindex}),
or the global operators
\tcode{operator<}~(\ref{reverse.iter.op<}),
\tcode{operator>}~(\ref{reverse.iter.op>}),\\
\tcode{operator\,<=}~(\ref{reverse.iter.op<=}),
\tcode{operator>=}~(\ref{reverse.iter.op>=}),
\tcode{operator-}~(\ref{reverse.iter.opdiff})
or
\tcode{operator+}~(\ref{reverse.iter.opsum})
are referenced in a way that requires instantiation~(\ref{temp.inst}).

\rSec3[reverse.iter.ops]{\tcode{reverse_iterator} operations}

\rSec4[reverse.iter.cons]{\tcode{reverse_iterator} constructor}

\indexlibrary{\idxcode{reverse_iterator}!\tcode{reverse_iterator}}%
\begin{itemdecl}
reverse_iterator();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Value initializes
\tcode{current}.
Iterator operations applied to the resulting iterator have defined behavior
if and only if the corresponding operations are defined on a value-initialized iterator of type
\tcode{Iterator}.
\end{itemdescr}

\indexlibrary{\idxcode{reverse_iterator}!constructor}%

\begin{itemdecl}
explicit reverse_iterator(Iterator x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{current}
with \tcode{x}.
\end{itemdescr}

\indexlibrary{\idxcode{reverse_iterator}!constructor}%

\begin{itemdecl}
template <class U> reverse_iterator(const reverse_iterator<U> &u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{current}
with
\tcode{u.current}.
\end{itemdescr}

\rSec4[reverse.iter.op=]{\tcode{reverse_iterator::operator=}}

\indexlibrary{\idxcode{operator=}!\tcode{reverse_iterator}}%
\begin{itemdecl}
template <class U>
reverse_iterator&
  operator=(const reverse_iterator<U>& u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Assigns \tcode{u.base()} to current.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[reverse.iter.conv]{Conversion}

\indexlibrary{\idxcode{base}!\idxcode{reverse_iterator}}%
\indexlibrary{\idxcode{reverse_iterator}!\idxcode{base}}%
\begin{itemdecl}
Iterator base() const;          // explicit
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{current}.
\end{itemdescr}

\rSec4[reverse.iter.op.star]{\tcode{operator*}}

\indexlibrary{\idxcode{operator*}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
reference operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
Iterator tmp = current;
return *--tmp;
\end{codeblock}

\end{itemdescr}

\rSec4[reverse.iter.opref]{\tcode{operator->}}

\indexlibrary{\idxcode{operator->}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
pointer operator->() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{std::addressof(operator*())}.
\end{itemdescr}

\rSec4[reverse.iter.op++]{\tcode{operator++}}

\indexlibrary{\idxcode{operator++}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
reverse_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{\dcr current;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator++}!\idxcode{reverse_iterator}}%
\indexlibrary{\idxcode{reverse_iterator}!\idxcode{operator++}}%
\begin{itemdecl}
reverse_iterator operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
reverse_iterator tmp = *this;
--current;
return tmp;
\end{codeblock}
\end{itemdescr}

\rSec4[reverse.iter.op\dcr]{\tcode{operator\dcr}}

\indexlibrary{\idxcode{operator\dcr}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
reverse_iterator& operator--();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{++current}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator\dcr}!\idxcode{reverse_iterator}}%
\indexlibrary{\idxcode{reverse_iterator}!\idxcode{operator\dcr}}%
\begin{itemdecl}
reverse_iterator operator--(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
reverse_iterator tmp = *this;
++current;
return tmp;
\end{codeblock}
\end{itemdescr}

\rSec4[reverse.iter.op+]{\tcode{operator+}}

\indexlibrary{\idxcode{operator+}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
reverse_iterator
operator+(typename reverse_iterator<Iterator>::difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator(current-n)}.
\end{itemdescr}

\rSec4[reverse.iter.op+=]{\tcode{operator+=}}

\indexlibrary{\idxcode{operator+=}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
reverse_iterator&
operator+=(typename reverse_iterator<Iterator>::difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{current -= n;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[reverse.iter.op-]{\tcode{operator-}}

\indexlibrary{\idxcode{operator-}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
reverse_iterator
operator-(typename reverse_iterator<Iterator>::difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator(current+n)}.
\end{itemdescr}

\rSec4[reverse.iter.op-=]{\tcode{operator-=}}

\indexlibrary{\idxcode{operator-=}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
reverse_iterator&
operator-=(typename reverse_iterator<Iterator>::difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{current += n;}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[reverse.iter.opindex]{\tcode{operator[]}}

\indexlibrary{\idxcode{operator[]}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
@\unspec@ operator[](
    typename reverse_iterator<Iterator>::difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{current[-n-1]}.
\end{itemdescr}

\rSec4[reverse.iter.op==]{\tcode{operator==}}

\indexlibrary{\idxcode{operator==}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
  bool operator==(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.current == y.current}.
\end{itemdescr}

\rSec4[reverse.iter.op<]{\tcode{operator<}}

\indexlibrary{\idxcode{operator<}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
  bool operator<(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.current > y.current}.
\end{itemdescr}

\rSec4[reverse.iter.op!=]{\tcode{operator!=}}

\indexlibrary{\idxcode{operator"!=}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
  bool operator!=(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.current != y.current}.
\end{itemdescr}

\rSec4[reverse.iter.op>]{\tcode{operator>}}

\indexlibrary{\idxcode{operator>}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
  bool operator>(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.current < y.current}.
\end{itemdescr}

\rSec4[reverse.iter.op>=]{\tcode{operator>=}}

\indexlibrary{\idxcode{operator>=}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
  bool operator>=(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.current <= y.current}.
\end{itemdescr}

\rSec4[reverse.iter.op<=]{\tcode{operator<=}}

\indexlibrary{\idxcode{operator<=}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
  bool operator<=(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.current >= y.current}.
\end{itemdescr}

\rSec4[reverse.iter.opdiff]{\tcode{operator-}}

\indexlibrary{\idxcode{operator-}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
    auto operator-(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base());
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{y.current - x.current}.
\end{itemdescr}

\rSec4[reverse.iter.opsum]{\tcode{operator+}}

\indexlibrary{\idxcode{operator+}!\idxcode{reverse_iterator}}%
\begin{itemdecl}
template <class Iterator>
  reverse_iterator<Iterator> operator+(
    typename reverse_iterator<Iterator>::difference_type n,
    const reverse_iterator<Iterator>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<Iterator> (x.current - n)}.
\end{itemdescr}

\rSec4[reverse.iter.make]{Non-member function \tcode{make_reverse_iterator()}}

\indexlibrary{\idxcode{reverse_iterator}!\idxcode{make_reverse_iterator}~non-member~function}
\indexlibrary{\idxcode{make_reverse_iterator}}%
\begin{itemdecl}
template <class Iterator>
  reverse_iterator<Iterator> make_reverse_iterator(Iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{reverse_iterator<Iterator>(i)}.
\end{itemdescr}

\rSec2[insert.iterators]{Insert iterators}

\pnum
To make it possible to deal with insertion in the same way as writing into an array, a special kind of iterator
adaptors, called
\techterm{insert iterators},
are provided in the library.
With regular iterator classes,

\begin{codeblock}
while (first != last) *result++ = *first++;
\end{codeblock}

causes a range \range{first}{last}
to be copied into a range starting with result.
The same code with
\tcode{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
\techterm{insert mode}
instead of the \techterm{regular overwrite} mode.

\pnum
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.
\tcode{operator*}
returns the insert iterator itself.
The assignment
\tcode{operator=(const T\& x)}
is defined on insert iterators to allow writing into them, it inserts
\tcode{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.
\tcode{back_insert_iterator}
inserts elements at the end of a container,
\tcode{front_insert_iterator}
inserts elements at the beginning of a container, and
\tcode{insert_iterator}
inserts elements where the iterator points to in a container.
\tcode{back_inserter},
\tcode{front_inserter},
and
\tcode{inserter}
are three
functions making the insert iterators out of a container.

\rSec3[back.insert.iterator]{Class template \tcode{back_insert_iterator}}

\indexlibrary{\idxcode{back_insert_iterator}}%
\begin{codeblock}
namespace std {
  template <class Container>
  class back_insert_iterator :
    public iterator<output_iterator_tag,void,void,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=(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);
}
\end{codeblock}

\rSec3[back.insert.iter.ops]{\tcode{back_insert_iterator} operations}

\rSec4[back.insert.iter.cons]{\tcode{back_insert_iterator} constructor}

\indexlibrary{\idxcode{back_insert_iterator}!\idxcode{back_insert_iterator}}%
\begin{itemdecl}
explicit back_insert_iterator(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{container}
with \tcode{std::addressof(x)}.
\end{itemdescr}

\rSec4[back.insert.iter.op=]{\tcode{back_insert_iterator::operator=}}

\indexlibrary{\idxcode{operator=}!\idxcode{back_insert_iterator}}%
\begin{itemdecl}
back_insert_iterator<Container>&
  operator=(const typename Container::value_type& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{container->push_back(value);}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator=}!\idxcode{back_insert_iterator}}%
\begin{itemdecl}
back_insert_iterator<Container>&
  operator=(typename Container::value_type&& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{container->push_back(std::move(value));}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[back.insert.iter.op*]{\tcode{back_insert_iterator::operator*}}

\indexlibrary{\idxcode{operator*}!\idxcode{back_insert_iterator}}%
\begin{itemdecl}
back_insert_iterator<Container>& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[back.insert.iter.op++]{\tcode{back_insert_iterator::operator++}}

\indexlibrary{\idxcode{operator++}!\idxcode{back_insert_iterator}}%
\begin{itemdecl}
back_insert_iterator<Container>& operator++();
back_insert_iterator<Container>  operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[back.inserter]{ \tcode{back_inserter}}

\indexlibrary{\idxcode{back_inserter}}%
\begin{itemdecl}
template <class Container>
  back_insert_iterator<Container> back_inserter(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{back_insert_iterator<Container>(x)}.
\end{itemdescr}

\rSec3[front.insert.iterator]{Class template \tcode{front_insert_iterator}}

\indexlibrary{\idxcode{front_insert_iterator}}%
\begin{codeblock}
namespace std {
  template <class Container>
  class front_insert_iterator :
    public iterator<output_iterator_tag,void,void,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=(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);
}
\end{codeblock}

\rSec3[front.insert.iter.ops]{\tcode{front_insert_iterator} operations}

\rSec4[front.insert.iter.cons]{\tcode{front_insert_iterator} constructor}

\indexlibrary{\idxcode{front_insert_iterator}!\idxcode{front_insert_iterator}}%
\begin{itemdecl}
explicit front_insert_iterator(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{container}
with \tcode{std::addressof(x)}.
\end{itemdescr}

\rSec4[front.insert.iter.op=]{\tcode{front_insert_iterator::operator=}}

\indexlibrary{\idxcode{operator=}!\idxcode{front_insert_iterator}}%
\begin{itemdecl}
front_insert_iterator<Container>&
  operator=(const typename Container::value_type& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{container->push_front(value);}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator=}!\idxcode{front_insert_iterator}}%
\begin{itemdecl}
front_insert_iterator<Container>&
  operator=(typename Container::value_type&& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{container->push_front(std::move(value));}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[front.insert.iter.op*]{\tcode{front_insert_iterator::operator*}}

\indexlibrary{\idxcode{operator*}!\idxcode{front_insert_iterator}}%
\begin{itemdecl}
front_insert_iterator<Container>& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[front.insert.iter.op++]{\tcode{front_insert_iterator::operator++}}

\indexlibrary{\idxcode{operator++}!\idxcode{front_insert_iterator}}%
\begin{itemdecl}
front_insert_iterator<Container>& operator++();
front_insert_iterator<Container>  operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[front.inserter]{\tcode{front_inserter}}

\indexlibrary{\idxcode{front_inserter}}%
\begin{itemdecl}
template <class Container>
  front_insert_iterator<Container> front_inserter(Container& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{front_insert_iterator<Container>(x)}.
\end{itemdescr}

\rSec3[insert.iterator]{Class template \tcode{insert_iterator}}

\indexlibrary{\idxcode{insert_iterator}}%
\begin{codeblock}
namespace std {
  template <class Container>
  class insert_iterator :
    public iterator<output_iterator_tag,void,void,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=(typename Container::value_type&& value);

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

  template <class Container>
    insert_iterator<Container> inserter(Container& x, typename Container::iterator i);
}
\end{codeblock}

\rSec3[insert.iter.ops]{\tcode{insert_iterator} operations}

\rSec4[insert.iter.cons]{\tcode{insert_iterator} constructor}

\indexlibrary{\idxcode{insert_iterator}!\idxcode{insert_iterator}}%
\begin{itemdecl}
insert_iterator(Container& x, typename Container::iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes
\tcode{container}
with \tcode{std::addressof(x)} and
\tcode{iter}
with \tcode{i}.
\end{itemdescr}

\rSec4[insert.iter.op=]{\tcode{insert_iterator::operator=}}

\indexlibrary{\idxcode{operator=}!\idxcode{insert_iterator}}%
\begin{itemdecl}
insert_iterator<Container>&
  operator=(const typename Container::value_type& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
iter = container->insert(iter, value);
++iter;
\end{codeblock}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator=}!\idxcode{insert_iterator}}%
\begin{itemdecl}
insert_iterator<Container>&
  operator=(typename Container::value_type&& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
iter = container->insert(iter, std::move(value));
++iter;
\end{codeblock}

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[insert.iter.op*]{\tcode{insert_iterator::operator*}}

\indexlibrary{\idxcode{operator*}!\idxcode{insert_iterator}}%
\begin{itemdecl}
insert_iterator<Container>& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[insert.iter.op++]{\tcode{insert_iterator::operator++}}

\indexlibrary{\idxcode{operator++}!\idxcode{insert_iterator}}%
\begin{itemdecl}
insert_iterator<Container>& operator++();
insert_iterator<Container>& operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec4[inserter]{\tcode{inserter}}

\indexlibrary{\idxcode{inserter}}%
\begin{itemdecl}
template <class Container>
  insert_iterator<Container> inserter(Container& x, typename Container::iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{insert_iterator<Container>(x, i)}.
\end{itemdescr}

\rSec2[move.iterators]{Move iterators}

\pnum
Class template \tcode{move_iterator} is an iterator adaptor
with the same behavior as the underlying iterator except that its
indirection operator implicitly converts the value returned by the
underlying iterator's indirection operator to an rvalue reference.
Some generic algorithms can be called with move iterators to replace
copying with moving.

\pnum
\enterexample

\begin{codeblock}
list<string> s;
// populate the list \tcode{s}
vector<string> v1(s.begin(), s.end());          // copies strings into \tcode{v1}
vector<string> v2(make_move_iterator(s.begin()),
                  make_move_iterator(s.end())); // moves strings into \tcode{v2}
\end{codeblock}

\exitexample

\rSec3[move.iterator]{Class template \tcode{move_iterator}}

\indexlibrary{\idxcode{move_iterator}}%
\begin{codeblock}
namespace std {
  template <class Iterator>
  class move_iterator {
  public:
    typedef Iterator                                              iterator_type;
    typedef typename iterator_traits<Iterator>::difference_type   difference_type;
    typedef Iterator                                              pointer;
    typedef typename iterator_traits<Iterator>::value_type        value_type;
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef value_type&&                                          reference;

    move_iterator();
    explicit move_iterator(Iterator i);
    template <class U> move_iterator(const move_iterator<U>& u);
    template <class U> move_iterator& operator=(const move_iterator<U>& u);

    iterator_type base() const;
    reference operator*() const;
    pointer operator->() const;

    move_iterator& operator++();
    move_iterator operator++(int);
    move_iterator& operator--();
    move_iterator operator--(int);

    move_iterator operator+(difference_type n) const;
    move_iterator& operator+=(difference_type n);
    move_iterator operator-(difference_type n) const;
    move_iterator& operator-=(difference_type n);
    @\unspec@ operator[](difference_type n) const;

  private:
    Iterator current;   // \expos
  };

  template <class Iterator1, class Iterator2>
    bool operator==(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator!=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator<=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
  template <class Iterator1, class Iterator2>
    bool operator>=(
      const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

  template <class Iterator1, class Iterator2>
    auto operator-(
      const move_iterator<Iterator1>& x,
      const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
  template <class Iterator>
    move_iterator<Iterator> operator+(
      typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);
  template <class Iterator>
    move_iterator<Iterator> make_move_iterator(Iterator i);
}
\end{codeblock}

\rSec3[move.iter.requirements]{\tcode{move_iterator} requirements}

\pnum
The template parameter \tcode{Iterator} shall meet
the requirements for an Input Iterator~(\ref{input.iterators}).
Additionally, if any of the bidirectional or random access traversal
functions are instantiated, the template parameter shall meet the
requirements for a Bidirectional Iterator~(\ref{bidirectional.iterators})
or a Random Access Iterator~(\ref{random.access.iterators}), respectively.

\rSec3[move.iter.ops]{\tcode{move_iterator} operations}

\rSec4[move.iter.op.const]{\tcode{move_iterator} constructors}

\indexlibrary{\idxcode{move_iterator}!\idxcode{move_iterator}}%
\begin{itemdecl}
move_iterator();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Constructs a \tcode{move_iterator}, value
initializing \tcode{current}. Iterator operations applied to the resulting
iterator have defined behavior if and only if the corresponding operations are defined
on a value-initialized iterator of type \tcode{Iterator}.
\end{itemdescr}


\indexlibrary{\idxcode{move_iterator}!constructor}%
\begin{itemdecl}
explicit move_iterator(Iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Constructs a \tcode{move_iterator}, initializing
\tcode{current} with \tcode{i}.
\end{itemdescr}


\indexlibrary{\idxcode{move_iterator}!constructor}%
\begin{itemdecl}
template <class U> move_iterator(const move_iterator<U>& u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Constructs a \tcode{move_iterator}, initializing
\tcode{current} with \tcode{u.base()}.

\pnum
\requires \tcode{U} shall be convertible to
\tcode{Iterator}.
\end{itemdescr}

\rSec4[move.iter.op=]{\tcode{move_iterator::operator=}}

\indexlibrary{\idxcode{operator=}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator=}}%
\begin{itemdecl}
template <class U> move_iterator& operator=(const move_iterator<U>& u);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects Assigns \tcode{u.base()} to
\tcode{current}.

\pnum
\requires \tcode{U} shall be convertible to
\tcode{Iterator}.
\end{itemdescr}

\rSec4[move.iter.op.conv]{\tcode{move_iterator} conversion}

\indexlibrary{\idxcode{base}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{base}}%
\begin{itemdecl}
Iterator base() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{current}.
\end{itemdescr}

\rSec4[move.iter.op.star]{\tcode{move_iterator::operator*}}

\indexlibrary{\idxcode{operator*}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator*}}%
\begin{itemdecl}
reference operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{std::move(}*current).
\end{itemdescr}

\rSec4[move.iter.op.ref]{\tcode{move_iterator::operator->}}

\indexlibrary{\idxcode{operator->}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator->}}%
\begin{itemdecl}
pointer operator->() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{current}.
\end{itemdescr}

\rSec4[move.iter.op.incr]{\tcode{move_iterator::operator++}}

\indexlibrary{\idxcode{operator++}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator++}}%
\begin{itemdecl}
move_iterator& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects \tcode{++current}.

\pnum
\returns \tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator++}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator++}}%
\begin{itemdecl}
move_iterator operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
move_iterator tmp = *this;
++current;
return tmp;
\end{codeblock}
\end{itemdescr}

\rSec4[move.iter.op.decr]{\tcode{move_iterator::operator-{-}}}

\indexlibrary{\idxcode{operator\dcr}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator\dcr}}%
\begin{itemdecl}
move_iterator& operator--();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects \tcode{\dcr{}current}.

\pnum
\returns \tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator\dcr}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator\dcr}}%
\begin{itemdecl}
move_iterator operator--(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
move_iterator tmp = *this;
--current;
return tmp;
\end{codeblock}
\end{itemdescr}

\rSec4[move.iter.op.+]{\tcode{move_iterator::operator+}}

\indexlibrary{\idxcode{operator+}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator+}}%
\begin{itemdecl}
move_iterator operator+(difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{move_iterator(current + n)}.
\end{itemdescr}

\rSec4[move.iter.op.+=]{\tcode{move_iterator::operator+=}}

\indexlibrary{\idxcode{operator+=}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator+=}}%
\begin{itemdecl}
move_iterator& operator+=(difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects \tcode{current += n}.

\pnum
\returns \tcode{*this}.
\end{itemdescr}

\rSec4[move.iter.op.-]{\tcode{move_iterator::operator-}}

\indexlibrary{\idxcode{operator-}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator-}}%
\begin{itemdecl}
move_iterator operator-(difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{move_iterator(current - n)}.
\end{itemdescr}

\rSec4[move.iter.op.-=]{\tcode{move_iterator::operator-=}}

\indexlibrary{\idxcode{operator-=}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator-=}}%
\begin{itemdecl}
move_iterator& operator-=(difference_type n);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects \tcode{current -= n}.

\pnum
\returns \tcode{*this}.
\end{itemdescr}

\rSec4[move.iter.op.index]{\tcode{move_iterator::operator[]}}

\indexlibrary{\idxcode{operator[]}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator[]}}%
\begin{itemdecl}
@\unspec@ operator[](difference_type n) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{std::move(}current[n]).
\end{itemdescr}

\rSec4[move.iter.op.comp]{\tcode{move_iterator} comparisons}

\indexlibrary{\idxcode{operator==}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator==}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
bool operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{x.base() == y.base()}.
\end{itemdescr}

\indexlibrary{\idxcode{operator"!=}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator"!=}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
bool operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{!(x == y)}.
\end{itemdescr}

\indexlibrary{\idxcode{operator<}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator<}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
bool operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{x.base() < y.base()}.
\end{itemdescr}

\indexlibrary{\idxcode{operator<=}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator<=}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
bool operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{!(y < x)}.
\end{itemdescr}

\indexlibrary{\idxcode{operator>}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator>}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
bool operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{y < x}.
\end{itemdescr}

\indexlibrary{\idxcode{operator>=}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator>=}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
bool operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{!(x < y)}.
\end{itemdescr}

\rSec4[move.iter.nonmember]{\tcode{move_iterator} non-member functions}

\indexlibrary{\idxcode{operator-}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator-}}%
\begin{itemdecl}
template <class Iterator1, class Iterator2>
    auto operator-(
    const move_iterator<Iterator1>& x,
    const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{x.base() - y.base()}.
\end{itemdescr}

\indexlibrary{\idxcode{operator+}!\idxcode{move_iterator}}%
\indexlibrary{\idxcode{move_iterator}!\idxcode{operator+}}%
\begin{itemdecl}
template <class Iterator>
  move_iterator<Iterator> operator+(
    typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{x + n}.
\end{itemdescr}

\indexlibrary{\idxcode{make_move_iterator}}%
\begin{itemdecl}
template <class Iterator>
move_iterator<Iterator> make_move_iterator(Iterator i);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{move_iterator<Iterator>(i)}.
\end{itemdescr}

\rSec1[stream.iterators]{Stream iterators}

\pnum
To make it possible for algorithmic templates to work directly with input/output streams, appropriate
iterator-like
class templates
are provided.

\enterexample
\begin{codeblock}
partial_sum(istream_iterator<double, char>(cin),
  istream_iterator<double, char>(),
  ostream_iterator<double, char>(cout, "@\textbackslash@n"));
\end{codeblock}

reads a file containing floating point numbers from
\tcode{cin},
and prints the partial sums onto
\tcode{cout}.
\exitexample

\rSec2[istream.iterator]{Class template \tcode{istream_iterator}}

\pnum
\indexlibrary{\idxcode{istream_iterator}}%
The class template
\tcode{istream_iterator}
is an input iterator~(\ref{input.iterators}) that
reads (using
\tcode{operator\shr})
successive elements from the input stream for which it was constructed.
After it is constructed, and every time
\tcode{++}
is used, the iterator reads and stores a value of
\tcode{T}.
If the iterator fails to read and store a value of \tcode{T}
(\tcode{fail()}
on the stream returns
\tcode{true}),
the iterator becomes equal to the
\term{end-of-stream}
iterator value.
The constructor with no arguments
\tcode{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
\tcode{operator*}
on an end-of-stream iterator is not defined.
For any other iterator value a
\tcode{const T\&}
is returned.
The result of
\tcode{operator->}
on an end-of-stream iterator is not defined.
For any other iterator value a
\tcode{const T*}
is returned.
The behavior of a program that applies \tcode{operator++()} to an end-of-stream
iterator is undefined.
It is impossible to store things into istream iterators.

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

\begin{codeblock}
namespace std {
  template <class T, class charT = char, class traits = char_traits<charT>,
      class Distance = ptrdiff_t>
  class istream_iterator:
    public iterator<input_iterator_tag, T, Distance, const T*, const T&> {
  public:
    typedef charT char_type;
    typedef traits traits_type;
    typedef basic_istream<charT,traits> istream_type;
    @\seebelow@ istream_iterator();
    istream_iterator(istream_type& s);
    istream_iterator(const istream_iterator& x) = default;
   ~istream_iterator() = default;

    const T& operator*() const;
    const T* operator->() const;
    istream_iterator<T,charT,traits,Distance>& operator++();
    istream_iterator<T,charT,traits,Distance>  operator++(int);
  private:
    basic_istream<charT,traits>* in_stream; // \expos
    T value;                                // \expos
  };

  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);
}
\end{codeblock}

\rSec3[istream.iterator.cons]{\tcode{istream_iterator} constructors and destructor}


\indexlibrary{\idxcode{istream_iterator}!constructor}%
\begin{itemdecl}
@\seebelow@ istream_iterator();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs the end-of-stream iterator. If \tcode{T} is a literal type, then this
constructor shall be a \tcode{constexpr} constructor.

\pnum
\postcondition \tcode{in_stream == 0}.
\end{itemdescr}


\indexlibrary{\idxcode{istream_iterator}!constructor}%
\begin{itemdecl}
istream_iterator(istream_type& s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \textit{in_stream} with \tcode{\&s}. \textit{value} may be initialized during
construction or the first time it is referenced.

\pnum
\postcondition \tcode{in_stream == \&s}.
\end{itemdescr}


\indexlibrary{\idxcode{istream_iterator}!constructor}%
\begin{itemdecl}
istream_iterator(const istream_iterator& x) = default;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs a copy of \tcode{x}. If \tcode{T} is a literal type, then this constructor shall be a trivial copy constructor.

\pnum
\postcondition \tcode{in_stream == x.in_stream}.
\end{itemdescr}

\indexlibrary{\idxcode{istream_iterator}!destructor}%
\begin{itemdecl}
~istream_iterator() = default;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
The iterator is destroyed. If \tcode{T} is a literal type, then this destructor shall be a trivial destructor.
\end{itemdescr}

\rSec3[istream.iterator.ops]{\tcode{istream_iterator} operations}

\indexlibrary{\idxcode{operator*}!\idxcode{istream_iterator}}%
\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator*}}%
\begin{itemdecl}
const T& operator*() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\textit{value}.
\end{itemdescr}

\indexlibrary{\idxcode{operator->}!\idxcode{istream_iterator}}%
\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator->}}%
\begin{itemdecl}
const T* operator->() const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{\&(operator*())}.
\end{itemdescr}

\indexlibrary{\idxcode{operator++}!\idxcode{istream_iterator}}%
\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator++}}%
\begin{itemdecl}
istream_iterator<T,charT,traits,Distance>& operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{in_stream != 0}.

\pnum
\effects
\tcode{*in_stream \shr value}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator++}!\idxcode{istream_iterator}}%
\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator++}}%
\begin{itemdecl}
istream_iterator<T,charT,traits,Distance> operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires \tcode{in_stream != 0}.

\pnum
\effects
\begin{codeblock}
istream_iterator<T,charT,traits,Distance> tmp = *this;
*in_stream >> value;
return (tmp);
\end{codeblock}
\end{itemdescr}

\indexlibrary{\idxcode{operator==}!\idxcode{istream_iterator}}%
\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator==}}%
\begin{itemdecl}
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);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{x.in_stream == y.in_stream}.%
\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator==}}
\end{itemdescr}

\indexlibrary{\idxcode{operator"!=}!\idxcode{istream_iterator}}%
\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator"!=}}%
\begin{itemdecl}
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);
\end{itemdecl}

\indexlibrary{\idxcode{istream_iterator}!\idxcode{operator"!=}}%
\begin{itemdescr}
\pnum
\returns
\tcode{!(x == y)}
\end{itemdescr}

\rSec2[ostream.iterator]{Class template \tcode{ostream_iterator}}

\pnum
\indexlibrary{\idxcode{ostream_iterator}}%
\tcode{ostream_iterator}
writes (using
\tcode{operator\shl})
successive elements onto the output stream from which it was constructed.
If it was constructed with
\tcode{charT*}
as a constructor argument, this string, called a
\term{delimiter string},
is written to the stream after every
\tcode{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

\begin{codeblock}
while (first != last)
  *result++ = *first++;
\end{codeblock}

\pnum
\tcode{ostream_iterator}
is defined as:

\begin{codeblock}
namespace std {
  template <class T, class charT = char, class traits = char_traits<charT> >
  class ostream_iterator:
    public iterator<output_iterator_tag, void, void, 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);
  private:
    basic_ostream<charT,traits>* out_stream;  // \expos
    const charT* delim;                       // \expos
  };
}
\end{codeblock}

\rSec3[ostream.iterator.cons.des]{\tcode{ostream_iterator} constructors and destructor}


\indexlibrary{\idxcode{ostream_iterator}!constructor}%
\begin{itemdecl}
ostream_iterator(ostream_type& s);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \textit{out_stream} with \tcode{\&s} and \textit{delim} with null.
\end{itemdescr}


\indexlibrary{\idxcode{ostream_iterator}!constructor}%
\begin{itemdecl}
ostream_iterator(ostream_type& s, const charT* delimiter);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Initializes \textit{out_stream} with \tcode{\&s} and \textit{delim} with \tcode{delimiter}.
\end{itemdescr}


\indexlibrary{\idxcode{ostream_iterator}!constructor}%
\begin{itemdecl}
ostream_iterator(const ostream_iterator& x);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs a copy of \tcode{x}.
\end{itemdescr}

\indexlibrary{\idxcode{ostream_iterator}!destructor}%
\begin{itemdecl}
~ostream_iterator();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
The iterator is destroyed.
\end{itemdescr}

\rSec3[ostream.iterator.ops]{\tcode{ostream_iterator} operations}

\indexlibrary{\idxcode{operator=}!\idxcode{ostream_iterator}}%
\indexlibrary{\idxcode{ostream_iterator}!\idxcode{operator=}}%
\begin{itemdecl}
ostream_iterator& operator=(const T& value);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\begin{codeblock}
*@\textit{out_stream}@ << value;
if(delim != 0)
  *@\textit{out_stream}@ << @\textit{delim}@;
return (*this);
\end{codeblock}
\end{itemdescr}

\indexlibrary{\idxcode{operator*}!\idxcode{ostream_iterator}}%
\indexlibrary{\idxcode{ostream_iterator}!\idxcode{operator*}}%
\begin{itemdecl}
ostream_iterator& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator++}!\idxcode{ostream_iterator}}%
\indexlibrary{\idxcode{ostream_iterator}!\idxcode{operator++}}%
\begin{itemdecl}
ostream_iterator& operator++();
ostream_iterator& operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\rSec2[istreambuf.iterator]{Class template \tcode{istreambuf_iterator}}

\pnum
The
class template
\tcode{istreambuf_iterator}
defines an input iterator~(\ref{input.iterators}) that
reads successive
\textit{characters}
from the streambuf for which it was constructed.
\tcode{operator*}
provides access to the current input character, if any.
\enternote \tcode{operator->} may return a proxy. \exitnote
Each time
\tcode{operator++}
is evaluated, the iterator advances to the next input character.
If the end of stream is reached (\tcode{streambuf_type::sgetc()} returns
\tcode{traits::eof()}),
the iterator becomes equal to the
\term{end-of-stream}
iterator value.
The default constructor
\tcode{istreambuf_iterator()}
and the constructor
\tcode{istreambuf_iterator(0)}
both construct an end-of-stream iterator object suitable for use
as an end-of-range.
All specializations of \tcode{istreambuf_iterator} shall have a trivial copy
constructor, a \tcode{constexpr} default constructor, and a trivial destructor.

\pnum
The result of
\tcode{operator*()}
on an end-of-stream iterator is undefined.
\indextext{undefined behavior}%
For any other iterator value a
\tcode{char_type}
value is returned.
It is impossible to assign a character via an input iterator.

\indexlibrary{\idxcode{istreambuf_iterator}}%
\begin{codeblock}
namespace std {
  template<class charT, class traits = char_traits<charT> >
  class istreambuf_iterator
     : public iterator<input_iterator_tag, charT,
                       typename traits::off_type, @\unspec@, charT> {
  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;                          // \expos

    constexpr istreambuf_iterator() noexcept;
    istreambuf_iterator(const istreambuf_iterator&) noexcept = default;
    ~istreambuf_iterator() = default;
    istreambuf_iterator(istream_type& s) noexcept;
    istreambuf_iterator(streambuf_type* s) noexcept;
    istreambuf_iterator(const proxy& p) noexcept;
    charT operator*() const;
    pointer operator->() const;
    istreambuf_iterator<charT,traits>& operator++();
    proxy operator++(int);
    bool equal(const istreambuf_iterator& b) const;
  private:
    streambuf_type* sbuf_;                // \expos
  };

  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);
}
\end{codeblock}

\rSec3[istreambuf.iterator::proxy]{Class template \tcode{istreambuf_iterator::proxy}}

\indexlibrary{\idxcode{proxy}!\idxcode{istreambuf_iterator}}%
\begin{codeblock}
namespace std {
  template <class charT, class traits = char_traits<charT> >
  class istreambuf_iterator<charT, traits>::proxy { // \expos
    charT keep_;
    basic_streambuf<charT,traits>* sbuf_;
    proxy(charT c, basic_streambuf<charT,traits>* sbuf)
      : keep_(c), sbuf_(sbuf) { }
  public:
    charT operator*() { return keep_; }
  };
}
\end{codeblock}

\pnum
Class
\tcode{istreambuf_iterator<charT,traits>::proxy}
is for exposition only.
An implementation is permitted to provide equivalent functionality without
providing a class with this name.
Class
\tcode{istreambuf_iterator<charT, traits>\colcol{}proxy}
provides a temporary
placeholder as the return value of the post-increment operator
(\tcode{operator++}).
It keeps the character pointed to by the previous value
of the iterator for some possible future access to get the character.

\rSec3[istreambuf.iterator.cons]{\tcode{istreambuf_iterator} constructors}


\indexlibrary{\idxcode{istreambuf_iterator}!constructor}%
\begin{itemdecl}
constexpr istreambuf_iterator() noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs the end-of-stream iterator.
\end{itemdescr}


\indexlibrary{\idxcode{istreambuf_iterator}!constructor}%
\begin{itemdecl}
istreambuf_iterator(basic_istream<charT,traits>& s) noexcept;
istreambuf_iterator(basic_streambuf<charT,traits>* s) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs an
\tcode{istreambuf_iterator<>}
that uses the
\tcode{basic_streambuf<>}
object
\tcode{*(s.rdbuf())},
or
\tcode{*s},
respectively.
Constructs an end-of-stream iterator if
\tcode{s.rdbuf()}
is null.
\end{itemdescr}


\indexlibrary{\idxcode{istreambuf_iterator}!constructor}%
\begin{itemdecl}
istreambuf_iterator(const proxy& p) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
Constructs a
\tcode{istreambuf_iterator<>}
that uses the
\tcode{basic_streambuf<>}
object pointed to by the
\tcode{proxy}
object's constructor argument \tcode{p}.
\end{itemdescr}

\rSec3[istreambuf.iterator::op*]{\tcode{istreambuf_iterator::operator*}}

\indexlibrary{\idxcode{operator*}!\idxcode{istreambuf_iterator}}%
\begin{itemdecl}
charT operator*() const
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
The character obtained via the
\tcode{streambuf}
member
\tcode{sbuf_->sgetc()}.
\end{itemdescr}

\rSec3[istreambuf.iterator::op++]{\tcode{istreambuf_iterator::operator++}}

\indexlibrary{\idxcode{operator++}!\idxcode{istreambuf_iterator}}%
\begin{itemdecl}
istreambuf_iterator<charT,traits>&
    istreambuf_iterator<charT,traits>::operator++();
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
\tcode{sbuf_->sbumpc()}.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator++}!\idxcode{istreambuf_iterator}}%
\indexlibrary{\idxcode{istreambuf_iterator}!\idxcode{operator++}}%
\begin{itemdecl}
proxy istreambuf_iterator<charT,traits>::operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{proxy(sbuf_->sbumpc(), sbuf_)}.
\end{itemdescr}

\rSec3[istreambuf.iterator::equal]{\tcode{istreambuf_iterator::equal}}

\indexlibrary{\idxcode{equal}!\idxcode{istreambuf_iterator}}%
\begin{itemdecl}
bool equal(const istreambuf_iterator<charT,traits>& b) const;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{true}
if and only if both iterators are at end-of-stream,
or neither is at end-of-stream, regardless of what
\tcode{streambuf}
object they use.
\end{itemdescr}

\rSec3[istreambuf.iterator::op==]{\tcode{operator==}}

\indexlibrary{\idxcode{operator==}!\idxcode{istreambuf_iterator}}%
\begin{itemdecl}
template <class charT, class traits>
  bool operator==(const istreambuf_iterator<charT,traits>& a,
                  const istreambuf_iterator<charT,traits>& b);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{a.equal(b)}.
\end{itemdescr}

\rSec3[istreambuf.iterator::op!=]{\tcode{operator!=}}

\indexlibrary{\idxcode{operator"!=}!\idxcode{istreambuf_iterator}}%
\begin{itemdecl}
template <class charT, class traits>
  bool operator!=(const istreambuf_iterator<charT,traits>& a,
                  const istreambuf_iterator<charT,traits>& b);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{!a.equal(b)}.
\end{itemdescr}

\rSec2[ostreambuf.iterator]{Class template \tcode{ostreambuf_iterator}}

\indexlibrary{\idxcode{ostreambuf_iterator}}%
\begin{codeblock}
namespace std {
  template <class charT, class traits = char_traits<charT> >
  class ostreambuf_iterator :
    public iterator<output_iterator_tag, void, void, 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) noexcept;
    ostreambuf_iterator(streambuf_type* s) noexcept;
    ostreambuf_iterator& operator=(charT c);

    ostreambuf_iterator& operator*();
    ostreambuf_iterator& operator++();
    ostreambuf_iterator& operator++(int);
    bool failed() const noexcept;

  private:
    streambuf_type* sbuf_;                // \expos
  };
}
\end{codeblock}

\pnum
The
class template
\tcode{ostreambuf_iterator}
writes successive
\textit{characters}
onto the output stream from which it was constructed.
It is not possible to get a character value out of the output iterator.

\rSec3[ostreambuf.iter.cons]{\tcode{ostreambuf_iterator} constructors}


\indexlibrary{\idxcode{ostreambuf_iterator}!constructor}%
\begin{itemdecl}
ostreambuf_iterator(ostream_type& s) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
\tcode{s.rdbuf()}
shall not null pointer.
\end{itemdescr}

\begin{itemdescr}
\pnum
\effects
Initializes \tcode{sbuf_} with \tcode{s.rdbuf()}.
\end{itemdescr}


\indexlibrary{\idxcode{ostreambuf_iterator}!constructor}%
\begin{itemdecl}
ostreambuf_iterator(streambuf_type* s) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\requires
\tcode{s}
shall not be a null pointer.

\pnum
\effects
Initializes \tcode{sbuf_} with \tcode{s}.
\end{itemdescr}

\rSec3[ostreambuf.iter.ops]{\tcode{ostreambuf_iterator} operations}

\indexlibrary{\idxcode{operator=}!\idxcode{ostreambuf_iterator}}%
\begin{itemdecl}
ostreambuf_iterator<charT,traits>&
  operator=(charT c);
\end{itemdecl}

\begin{itemdescr}
\pnum
\effects
If
\tcode{failed()}
yields
\tcode{false},
calls
\tcode{sbuf_->sputc(c)};
otherwise has no effect.

\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator*}!\idxcode{ostreambuf_iterator}}%
\begin{itemdecl}
ostreambuf_iterator<charT,traits>& operator*();
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{operator++}!\idxcode{ostreambuf_iterator}}%
\begin{itemdecl}
ostreambuf_iterator<charT,traits>& operator++();
ostreambuf_iterator<charT,traits>& operator++(int);
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{*this}.
\end{itemdescr}

\indexlibrary{\idxcode{failed}!\idxcode{ostreambuf_iterator}}%
\begin{itemdecl}
bool failed() const noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns
\tcode{true}
if in any prior use of member
\tcode{operator=},
the call to
\tcode{sbuf_->sputc()}
returned
\tcode{traits::eof()};
or
\tcode{false}
otherwise.
\end{itemdescr}

\rSec1[iterator.range]{range access}

\pnum
In addition to being available via inclusion of the \tcode{<iterator>} header,
the function templates in \ref{iterator.range} are available when any of the following
headers are included: \tcode{<array>}, \tcode{<deque>}, \tcode{<forward_list>},
\tcode{<list>}, \tcode{<map>}, \tcode{<regex>}, \tcode{<set>}, \tcode{<string>},
\tcode{<unordered_map>}, \tcode{<unordered_set>}, and \tcode{<vector>}.

\indexlibrary{\idxcode{begin(C\&)}}%
\begin{itemdecl}
template <class C> auto begin(C& c) -> decltype(c.begin());
template <class C> auto begin(const C& c) -> decltype(c.begin());
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{c.begin()}.
\end{itemdescr}

\indexlibrary{\idxcode{end(C\&)}}%
\begin{itemdecl}
template <class C> auto end(C& c) -> decltype(c.end());
template <class C> auto end(const C& c) -> decltype(c.end());
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{c.end()}.
\end{itemdescr}

\indexlibrary{\idxcode{begin(T (\&)[N])}}%
\begin{itemdecl}
template <class T, size_t N> constexpr T* begin(T (&array)[N]) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{array}.
\end{itemdescr}

\indexlibrary{\idxcode{end(T (\&)[N])}}%
\begin{itemdecl}
template <class T, size_t N> constexpr T* end(T (&array)[N]) noexcept;
\end{itemdecl}

\begin{itemdescr}
\pnum
\returns \tcode{array + N}.
\end{itemdescr}

\indexlibrary{\idxcode{cbegin(const C\&)}}%
\begin{itemdecl}
template <class C> constexpr auto cbegin(const C& c) noexcept(noexcept(std::begin(c)))
  -> decltype(std::begin(c));
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{std::begin(c)}.
\end{itemdescr}

\indexlibrary{\idxcode{cend(const C\&)}}%
\begin{itemdecl}
template <class C> constexpr auto cend(const C& c) noexcept(noexcept(std::end(c)))
  -> decltype(std::end(c));
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{std::end(c)}.
\end{itemdescr}

\indexlibrary{\idxcode{rbegin(C\&)}}%
\begin{itemdecl}
template <class C> auto rbegin(C& c) -> decltype(c.rbegin());
template <class C> auto rbegin(const C& c) -> decltype(c.rbegin());
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{c.rbegin()}.
\end{itemdescr}

\indexlibrary{\idxcode{rend(const C\&)}}%
\begin{itemdecl}
template <class C> auto rend(C& c) -> decltype(c.rend());
template <class C> auto rend(const C& c) -> decltype(c.rend());
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{c.rend()}.
\end{itemdescr}

\indexlibrary{\idxcode{rbegin(T (\&array)[N])}}%
\begin{itemdecl}
template <class T, size_t N> reverse_iterator<T*> rbegin(T (&array)[N]);
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{reverse_iterator<T*>(array + N)}.
\end{itemdescr}

\indexlibrary{\idxcode{rend(T (\&array)[N])}}%
\begin{itemdecl}
template <class T, size_t N> reverse_iterator<T*> rend(T (&array)[N]);
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{reverse_iterator<T*>(array)}.
\end{itemdescr}

\indexlibrary{\idxcode{rbegin(initializer_list<E>)}}%
\begin{itemdecl}
template <class E> reverse_iterator<const E*> rbegin(initializer_list<E> il);
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{reverse_iterator<const E*>(il.end())}.
\end{itemdescr}

\indexlibrary{\idxcode{rend(initializer_list<E>)}}%
\begin{itemdecl}
template <class E> reverse_iterator<const E*> rend(initializer_list<E> il);
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{reverse_iterator<const E*>(il.begin())}.
\end{itemdescr}

\indexlibrary{\idxcode{crbegin(const C\& c)}}%
\begin{itemdecl}
template <class C> auto crbegin(const C& c) -> decltype(std::rbegin(c));
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{std::rbegin(c)}.
\end{itemdescr}

\indexlibrary{\idxcode{crend(const C\& c)}}%
\begin{itemdecl}
template <class C> auto crend(const C& c) -> decltype(std::rend(c));
\end{itemdecl}
\begin{itemdescr}
\pnum \returns \tcode{std::rend(c)}.
\end{itemdescr}
