\rSec0[iterators]{Iterators library}

\rSec1[iterators.general]{General}

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

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}

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

An input iterator

\tcode{i}

supports the expression

\tcode{*i},

resulting in a value of some object type

\tcode{T},

called the

\term{value type}

of the iterator.

An output iterator \tcode{i} has a non-empty set of types that are

\defn{writable} to the iterator;

for each such type \tcode{T}, the expression \tcode{*i = o}

is valid where \tcode{o} is a value of type \tcode{T}.

An iterator

\tcode{i}

for which the expression

\tcode{(*i).m}

is well-defined supports 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.

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}

\textbf{Random Access} & $\rightarrow$ \textbf{Bidirectional} &

$\rightarrow$ \textbf{Forward} & $\rightarrow$ \textbf{Input} \\

& & & $\rightarrow$ \textbf{Output} \\

\end{floattable}

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.

Iterators that further satisfy the requirements of output iterators are

called \defnx{mutable iterators}{mutable iterator}. Nonmutable iterators are referred to

as \defnx{constant iterators}{constant iterator}.

In addition to the requirements in this subclause,

the nested \grammarterm{typedef-name}{s} specified in \ref{iterator.traits}

shall be provided for the iterator type.

\begin{note} Either the iterator type must provide the \grammarterm{typedef-name}{s} directly

(in which case \tcode{iterator_traits} pick them up automatically), or

an \tcode{iterator_traits} specialization must provide them. \end{note}

Iterators that further satisfy the requirement that,

for integral values \tcode{n} and

dereferenceable iterator values \tcode{a} and \tcode{(a + n)},

\tcode{*(a + n)} is equivalent to \tcode{*(addressof(*a) + n)},

are called \defn{contiguous iterators}.

\begin{note}

For example, the type ``pointer to \tcode{int}'' is a contiguous iterator,

but \tcode{reverse_iterator<int *>} is not.

For a valid iterator range $[$\tcode{a}$, $\tcode{b}$)$ with dereferenceable \tcode{a},

the corresponding range denoted by pointers is

$[$\tcode{addressof(*a)}$, $\tcode{addressof(*a) + (b - a)}$)$;

\tcode{b} might not be dereferenceable.

\end{note}

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.

\begin{example}

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.

\end{example}

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. \begin{note} 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.

\end{note}

In these cases the singular

value is overwritten the same way as any other value.

Dereferenceable

values are always non-singular.

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.

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.

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.

Destruction of an iterator may invalidate pointers and references

previously obtained from that iterator.

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.

}

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.

\begin{note} For an iterator type \tcode{X} there must be an instantiation

of \tcode{iterator_traits<X>}~(\ref{iterator.traits}). \end{note}

\rSec2[iterator.iterators]{Iterator}

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

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

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} & \rhdr{Assertion/note} \\

& & \chdr{semantics} & \rhdr{pre-/post-condition} \\ \capsep

\tcode{*r} &

unspecified &

&

\requires \tcode{r} is dereferenceable. \\ \rowsep

\tcode{++r} &

\tcode{X\&} &

&

\\

\end{libreqtab4b}

\rSec2[input.iterators]{Input iterators}

A class or pointer type

\tcode{X}

satisfies the requirements of an input iterator for the value type

\tcode{T}

if

\tcode{X} satisfies the \tcode{Iterator}~(\ref{iterator.iterators}) and

\tcode{EqualityComparable} (Table~\ref{tab:equalitycomparable}) requirements and

the expressions in Table~\ref{tab:iterator.input.requirements} are valid and have

the indicated semantics.

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{!=}.

\begin{example}

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

\textit{p}).

\end{example}

\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

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} & \rhdr{Assertion/note} \\

& & \chdr{semantics} & \rhdr{pre-/post-condition} \\ \capsep

\tcode{a != b} &

contextually convertible to \tcode{bool} &

\tcode{!(a == b)} &

\requires \orange{a}{b} is in the domain of \tcode{==}. \\ \rowsep

\tcode{*a} &

\tcode{reference}, convertible to \tcode{T} &

&

\requires \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} &

\requires \tcode{a} is dereferenceable. \\ \rowsep

\tcode{++r} &

\tcode{X\&} &

&

\requires \tcode{r} is dereferenceable.\br

\postconditions \tcode{r} is dereferenceable or \tcode{r} is past-the-end;\br

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}

\begin{note}

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 \tcode{T} is not required to be a \tcode{CopyAssignable} type (Table~\ref{tab:copyassignable}).

These algorithms can be used with istreams as the source of the input data through the

\tcode{istream_iterator}

class template.

\end{note}

\rSec2[output.iterators]{Output iterators}

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

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} & \rhdr{Assertion/note} \\

& & \chdr{semantics} & \rhdr{pre-/post-condition} \\ \capsep

\tcode{*r = o} &

result is not used &

&

\remarks\ After this operation \tcode{r} is not required to be dereferenceable.\br

\postconditions \tcode{r} is incrementable. \\ \rowsep

\tcode{++r} &

\tcode{X\&} &

&

\tcode{\&r == \&++r}.\br

\remarks\ After this operation \tcode{r} is not required to be dereferenceable.\br

\postconditions \tcode{r} is incrementable. \\ \rowsep

\tcode{r++} &

convertible to \tcode{const X\&} &

\tcode{\{ X tmp = r;}\br

\tcode{ ++r;}\br

\tcode{ return tmp; \}} &

\remarks\ After this operation \tcode{r} is not required to be dereferenceable.\br

\postconditions \tcode{r} is incrementable. \\ \rowsep

\tcode{*r++ = o} &

result is not used &&

\remarks\ After this operation \tcode{r} is not required to be dereferenceable.\br

\postconditions \tcode{r} is incrementable. \\

\end{libreqtab4b}

\begin{note}

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.

\end{note}

\rSec2[forward.iterators]{Forward iterators}

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 \tcode{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 constant 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}

The domain of \tcode{==} 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.

\begin{note} Value-initialized iterators behave as if they refer past the end of

the same empty sequence. \end{note}

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}

\begin{note}

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.

\end{note}

\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

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} & \rhdr{Assertion/note} \\

& & \chdr{semantics} & \rhdr{pre-/post-condition} \\ \capsep

\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}

If \tcode{a} and \tcode{b} are equal, then either \tcode{a} and \tcode{b}

are both dereferenceable

or else neither is dereferenceable.

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}

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

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} & \rhdr{Assertion/note} \\

& & \chdr{semantics} & \rhdr{pre-/post-condition} \\ \capsep

\tcode{\dcr r} &

\tcode{X\&} &

&

\requires there exists \tcode{s} such that \tcode{r == ++s}.\br

\postconditions \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}

\begin{note}

Bidirectional iterators allow algorithms to move iterators backward as well as forward.

\end{note}

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

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

\lhdr{Expression} & \chdr{Return type} & \chdr{Operational} & \rhdr{Assertion/note} \\

& & \chdr{semantics} & \rhdr{pre-/post-condition} \\ \capsep

\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;} &

\requires the absolute value of \tcode{n} is in the range of

representable values of \tcode{difference_type}. \\ \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} &

\requires 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}

\indextext{\idxhdr{iterator}}%

\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 T> struct iterator_traits<const T*>;

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>

constexpr void advance(InputIterator& i, Distance n);

template <class InputIterator>

constexpr typename iterator_traits<InputIterator>::difference_type

distance(InputIterator first, InputIterator last);

template <class InputIterator>

constexpr InputIterator next(InputIterator x,

typename iterator_traits<InputIterator>::difference_type n = 1);

template <class BidirectionalIterator>

constexpr BidirectionalIterator prev(BidirectionalIterator x,

typename iterator_traits<BidirectionalIterator>::difference_type n = 1);

// \ref{predef.iterators}, predefined iterators

template <class Iterator> class reverse_iterator;

template <class Iterator1, class Iterator2>

constexpr bool operator==(

const reverse_iterator<Iterator1>& x,

const reverse_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator<(

const reverse_iterator<Iterator1>& x,

const reverse_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator!=(

const reverse_iterator<Iterator1>& x,

const reverse_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator>(

const reverse_iterator<Iterator1>& x,

const reverse_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator>=(

const reverse_iterator<Iterator1>& x,

const reverse_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator<=(

const reverse_iterator<Iterator1>& x,

const reverse_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr auto operator-(

const reverse_iterator<Iterator1>& x,

const reverse_iterator<Iterator2>& y) ->decltype(y.base() - x.base());

template <class Iterator>

constexpr reverse_iterator<Iterator>

operator+(

typename reverse_iterator<Iterator>::difference_type n,

const reverse_iterator<Iterator>& x);

template <class Iterator>

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

constexpr bool operator==(

const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator!=(

const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator<(

const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator<=(

const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator>(

const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr bool operator>=(

const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

template <class Iterator1, class Iterator2>

constexpr auto operator-(

const move_iterator<Iterator1>& x,

const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());

template <class Iterator>

constexpr move_iterator<Iterator> operator+(

typename move_iterator<Iterator>::difference_type n, const move_iterator<Iterator>& x);

template <class Iterator>

constexpr 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> constexpr auto begin(C& c) -> decltype(c.begin());

template <class C> constexpr auto begin(const C& c) -> decltype(c.begin());

template <class C> constexpr auto end(C& c) -> decltype(c.end());

template <class C> constexpr 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> constexpr auto rbegin(C& c) -> decltype(c.rbegin());

template <class C> constexpr auto rbegin(const C& c) -> decltype(c.rbegin());

template <class C> constexpr auto rend(C& c) -> decltype(c.rend());

template <class C> constexpr auto rend(const C& c) -> decltype(c.rend());

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

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

template <class E> constexpr reverse_iterator<const E*> rbegin(initializer_list<E> il);

template <class E> constexpr reverse_iterator<const E*> rend(initializer_list<E> il);

template <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c));

template <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c));

// \ref{iterator.container}, container access

template <class C> constexpr auto size(const C& c) -> decltype(c.size());

template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept;

template <class C> constexpr auto empty(const C& c) -> decltype(c.empty());

template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept;

template <class E> constexpr bool empty(initializer_list<E> il) noexcept;

template <class C> constexpr auto data(C& c) -> decltype(c.data());

template <class C> constexpr auto data(const C& c) -> decltype(c.data());

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

template <class E> constexpr const E* data(initializer_list<E> il) noexcept;

}

\end{codeblock}

\rSec1[iterator.primitives]{Iterator primitives}

To simplify the task of defining iterators, the library provides

several classes and functions:

\rSec2[iterator.traits]{Iterator traits}

\indexlibrary{\idxcode{iterator_traits}}%

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

If \tcode{Iterator} has valid~(\ref{temp.deduct}) member

types \tcode{difference_type}, \tcode{value_type}, \tcode{pointer},

\tcode{reference}, and \tcode{iterator_category},

\tcode{iterator_traits<Iterator>}

shall have the following as publicly accessible members:

\begin{codeblock}

using difference_type = typename Iterator::difference_type;

using value_type = typename Iterator::value_type;

using pointer = typename Iterator::pointer;

using reference = typename Iterator::reference;

using iterator_category = typename Iterator::iterator_category;

\end{codeblock}

Otherwise, \tcode{iterator_traits<Iterator>}

shall have no members by any of the above names.

It is specialized for pointers as

\begin{codeblock}

namespace std {

template<class T> struct iterator_traits<T*> {

using difference_type = ptrdiff_t;

using value_type = T;

using pointer = T*;

using reference = T&;

using iterator_category = random_access_iterator_tag;

};

}

\end{codeblock}

and for pointers to const as

\begin{codeblock}

namespace std {

template<class T> struct iterator_traits<const T*> {

using difference_type = ptrdiff_t;

using value_type = T;

using pointer = const T*;

using reference = const T&;

using iterator_category = random_access_iterator_tag;

};

}

\end{codeblock}

\begin{example}

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}

\end{example}

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

\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