%!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 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> T* begin(T (&array)[N]);

template <class T, size_t N> T* end(T (&array)[N]);

template <class C> auto cbegin(const C& c) -> decltype(std::begin(c));

template <class C> auto cend(const C& 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},