Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(for example, containers and ranges) 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
i
supports the expression
*i,
resulting in a value of some object type
T,
called the
*value type*
of the iterator.

An output iterator i has a non-empty set of types that are
*writable* to the iterator;
for each such type T, the expression *i = o
is valid where o is a value of type T.

For every iterator type
X,
there is a corresponding signed integer type called the
*difference type*
of the iterator.

Since iterators are an abstraction of pointers, their semantics are
a generalization of most of the semantics of pointers in C++.

This ensures that every
function template
that takes iterators
works as well with regular pointers.

This document defines
six categories of iterators, according to the operations
defined on them:
*input iterators*,
*output iterators*,
*forward iterators*,
*bidirectional iterators*,
*random access iterators*,
and
*contiguous iterators*,
as shown in Table 72.

Table 72 — Relations among iterator categories

Contiguous | → Random Access | → Bidirectional | → Forward | → Input |

→ Output |

The six categories of iterators correspond to the iterator concepts
InputIterator ([iterator.concept.input]),
OutputIterator ([iterator.concept.output]),
ForwardIterator ([iterator.concept.forward]),
BidirectionalIterator ([iterator.concept.bidir])
RandomAccessIterator ([iterator.concept.random.access]),
and
ContiguousIterator ([iterator.concept.contiguous]),
respectively.

The generic term *iterator* refers to any type that models the
Iterator concept ([iterator.concept.iterator]).

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;
Contiguous iterators also satisfy all the requirements of random access
iterators and can be used whenever a random access iterator is specified.

Iterators that further satisfy the requirements of output iterators are
called *mutable iterators*.

Nonmutable iterators are referred to
as *constant iterators*.

In addition to the requirements in this subclause,
the nested *typedef-name*s specified in [iterator.traits]
shall be provided for the iterator type.

[ Note

: *end note*

]Either the iterator type must provide the *typedef-name*s directly
(in which case iterator_traits pick them up automatically), or
an iterator_traits specialization must provide them.

— 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
*past-the-end*
values.

The library never assumes that past-the-end values are dereferenceable.

Iterators can also have singular values that are not associated with any
sequence.

[ Example

: *end example*

]After the declaration of an uninitialized pointer
x
(as with
int* x;),
x
must always be assumed to have a singular value of a pointer.

—
Results of most expressions are undefined for singular values;
the only 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
Cpp17DefaultConstructible requirements, using a value-initialized iterator
as the source of a copy or move operation.

[ Note

: *end 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.

—
In these cases the singular
value is overwritten the same way as any other value.

Dereferenceable
values are always non-singular.

Most of the library's algorithmic templates that operate on data structures have
interfaces that use ranges.

An iterator and a sentinel denoting a range are comparable.

A range [i, s)
is empty if i == s;
otherwise, [i, s)
refers to the elements in the data structure starting with the element
pointed to by
i
and up to but not including the element, if any, pointed to by
the first iterator j such that j == s.

A counted range [i, n) is empty if n == 0; otherwise, [i, n)
refers to the n elements in the data structure starting with the element
pointed to by i and up to but not including the element, if any, pointed to by
the result of n applications of ++i.

A counted range
[i, n) is valid if and only if n == 0; or n is positive,
i is dereferenceable, and [++i, --n) is valid.

All the categories of iterators require only those functions that are realizable for a given category in
constant time (amortized).

Therefore, requirement tables and concept definitions for the iterators
do not specify complexity.

Destruction of a non-forward iterator may invalidate pointers and references
previously obtained from that iterator.

Iterators are called *constexpr iterators*
if all operations provided to meet iterator category requirements
are constexpr functions, except for

- a pseudo-destructor call ([expr.prim.id.dtor]), and
- the construction of an iterator with a singular value.

The sentinel denoting the end of a range
may have the same type as the iterator denoting the beginning of the range, or a
different type.

To implement algorithms only in terms of incrementable types,
it is often necessary to determine the difference type that
corresponds to a particular incrementable type.

Accordingly,
it is required that if WI is the name of a type that models the
WeaklyIncrementable concept ([iterator.concept.winc]),
the type

iter_difference_t<WI>be defined as the incrementable type's difference type.

namespace std { template<class> struct incrementable_traits { }; template<class T> requires is_object_v<T> struct incrementable_traits<T*> { using difference_type = ptrdiff_t; }; template<class I> struct incrementable_traits<const I> : incrementable_traits<I> { }; template<class T> requires requires { typename T::difference_type; } struct incrementable_traits<T> { using difference_type = typename T::difference_type; }; template<class T> requires (!requires { typename T::difference_type; } && requires(const T& a, const T& b) { { a - b } -> Integral; }) struct incrementable_traits<T> { using difference_type = make_signed_t<decltype(declval<T>() - declval<T>())>; }; template<class T> using iter_difference_t = see below; }

To implement algorithms only in terms of readable types, it is often necessary
to determine the value type that corresponds to a particular readable type.

Accordingly, it is required that if R is the name of a type that
models the Readable concept ([iterator.concept.readable]),
the type

iter_value_t<R>be defined as the readable type's value type.

template<class> struct cond-value-type { }; // exposition only template<class T> requires is_object_v<T> struct cond-value-type { using value_type = remove_cv_t<T>; }; template<class> struct readable_traits { }; template<class T> struct readable_traits<T*> : cond-value-type<T> { }; template<class I> requires is_array_v<I> struct readable_traits<I> { using value_type = remove_cv_t<remove_extent_t<I>>; }; template<class I> struct readable_traits<const I> : readable_traits<I> { }; template<class T> requires requires { typename T::value_type; } struct readable_traits<T> : cond-value-type<typename T::value_type> { }; template<class T> requires requires { typename T::element_type; } struct readable_traits<T> : cond-value-type<typename T::element_type> { }; template<class T> using iter_value_t = see below;

To implement algorithms only in terms of iterators, it is sometimes necessary to
determine the iterator category that corresponds to a particular iterator type.

Accordingly, it is required that if
I
is the type of an iterator,
the type

iterator_traits<I>::iterator_categorybe defined as the iterator's iterator category.

In addition, the types

iterator_traits<I>::pointer iterator_traits<I>::referenceshall be defined as the iterator's pointer and reference types; that is, for an iterator object a of class type, the same type as decltype(a.operator->()) and decltype(*a), respectively.

The type
iterator_traits<I>::pointer
shall be void
for an iterator of class type I
that does not support operator->.

Additionally, in the case of an output iterator, the types

iterator_traits<I>::value_type iterator_traits<I>::difference_type iterator_traits<I>::referencemay be defined as void.

The definitions in this subclause make use of the following
exposition-only concepts:

template<class I> concept cpp17-iterator = Copyable<I> && requires(I i) { { *i } -> can-reference; { ++i } -> Same<I&>; { *i++ } -> can-reference; }; template<class I> concept cpp17-input-iterator = cpp17-iterator<I> && EqualityComparable<I> && requires(I i) { typename incrementable_traits<I>::difference_type; typename readable_traits<I>::value_type; typename common_reference_t<iter_reference_t<I>&&, typename readable_traits<I>::value_type&>; *i++; typename common_reference_t<decltype(*i++)&&, typename readable_traits<I>::value_type&>; requires SignedIntegral<typename incrementable_traits<I>::difference_type>; }; template<class I> concept cpp17-forward-iterator = cpp17-input-iterator<I> && Constructible<I> && is_lvalue_reference_v<iter_reference_t<I>> && Same<remove_cvref_t<iter_reference_t<I>>, typename readable_traits<I>::value_type> && requires(I i) { { i++ } -> const I&; { *i++ } -> Same<iter_reference_t<I>>; }; template<class I> concept cpp17-bidirectional-iterator = cpp17-forward-iterator<I> && requires(I i) { { --i } -> Same<I&>; { i-- } -> const I&; { *i-- } -> Same<iter_reference_t<I>>; }; template<class I> concept cpp17-random-access-iterator = cpp17-bidirectional-iterator<I> && StrictTotallyOrdered<I> && requires(I i, typename incrementable_traits<I>::difference_type n) { { i += n } -> Same<I&>; { i -= n } -> Same<I&>; { i + n } -> Same<I>; { n + i } -> Same<I>; { i - n } -> Same<I>; { i - i } -> Same<decltype(n)>; { i[n] } -> iter_reference_t<I>; };

The members of a specialization iterator_traits<I> generated from the
iterator_traits primary template are computed as follows:

- If I has valid ([temp.deduct]) member types difference_type, value_type, reference, and iterator_category, then iterator_traits<I> has the following publicly accessible members:
using iterator_category = typename I::iterator_category; using value_type = typename I::value_type; using difference_type = typename I::difference_type; using pointer = see below; using reference = typename I::reference;

If the*qualified-id*I::pointer is valid and denotes a type, then iterator_traits<I>::pointer names that type; otherwise, it names void. - Otherwise, if I satisfies the exposition-only concept cpp17-input-iterator, iterator_traits<I> has the following publicly accessible members:
using iterator_category = see below; using value_type = typename readable_traits<I>::value_type; using difference_type = typename incrementable_traits<I>::difference_type; using pointer = see below; using reference = see below;

- If the
*qualified-id*I::iterator_category is valid and denotes a type, iterator_category names that type.Otherwise, iterator_category names:- random_access_iterator_tag if I satisfies cpp17-random-access-iterator, or otherwise
- bidirectional_iterator_tag if I satisfies cpp17-bidirectional-iterator, or otherwise
- forward_iterator_tag if I satisfies cpp17-forward-iterator, or otherwise
- input_iterator_tag.

- Otherwise, if I satisfies the exposition-only concept cpp17-iterator, then iterator_traits<I> has the following publicly accessible members:
using iterator_category = output_iterator_tag; using value_type = void; using difference_type = see below; using pointer = void; using reference = void;

If the*qualified-id*incrementable_traits<I>::difference_type is valid and denotes a type, then difference_type names that type; otherwise, it names void. - Otherwise, iterator_traits<I> has no members by any of the above names.

Explicit or partial specializations of iterator_traits may
have a member type iterator_concept that is used to indicate
conformance to the iterator concepts ([iterator.concepts]).

iterator_traits is specialized for pointers as

namespace std { template<class T> requires is_object_v<T> struct iterator_traits<T*> { using iterator_concept = contiguous_iterator_tag; using iterator_category = random_access_iterator_tag; using value_type = remove_cv_t<T>; using difference_type = ptrdiff_t; using pointer = T*; using reference = T&; }; }

[ Example

: *end example*

]To implement a generic
reverse
function, a C++ program can do the following:

template<class BI> void reverse(BI first, BI last) { typename iterator_traits<BI>::difference_type n = distance(first, last); --n; while(n > 0) { typename iterator_traits<BI>::value_type tmp = *first; *first++ = *--last; *last = tmp; n -= 2; } }—

The expression ranges::iter_move(E) for some subexpression E is
expression-equivalent to the following:

The name ranges::iter_swap denotes
a customization point object ([customization.point.object])
that exchanges the values ([concept.swappable]) denoted by its
arguments.

```
template<class X, class Y>
constexpr iter_value_t<remove_reference_t<X>> iter-exchange-move(X&& x, Y&& y)
noexcept(noexcept(iter_value_t<remove_reference_t<X>>(iter_move(x))) &&
noexcept(*x = iter_move(y)));
```

Effects: Equivalent to:

iter_value_t<remove_reference_t<X>> old_value(iter_move(x)); *x = iter_move(y); return old_value;

The expression ranges::iter_swap(E1, E2) for some subexpressions
E1 and E2 is expression-equivalent to the following:

- (void)iter_swap(E1, E2), if that expression is valid, with overload resolution performed in a context that includes the declaration
template<class I1, class I2> void iter_swap(I1, I2) = delete;

and does not include a declaration of ranges::iter_swap.If the function selected by overload resolution does not exchange the values denoted by E1 and E2, the program is ill-formed with no diagnostic required. - Otherwise, if the types of E1 and E2 each model Readable, and if the reference types of E1 and E2 model SwappableWith ([concept.swappable]), then ranges::swap(*E1, *E2).
- Otherwise, if the types T1 and T2 of E1 and E2 model IndirectlyMovableStorable<T1, T2> and IndirectlyMovableStorable<T2, T1>, then (void)(*E1 = iter-exchange-move(E2, E1)), except that E1 is evaluated only once.
- Otherwise, ranges::iter_swap(E1, E2) is ill-formed.

For a type I, let ITER_TRAITS(I) denote
the type I if iterator_traits<I> names
a specialization generated from the primary template.

- If the
*qualified-id*ITER_TRAITS(I)::iterator_concept is valid and names a type, then ITER_CONCEPT(I) denotes that type. - Otherwise, if the
*qualified-id*ITER_TRAITS(I)::iterator_category is valid and names a type, then ITER_CONCEPT(I) denotes that type. - Otherwise, if iterator_traits<I> names a specialization generated from the primary template, then ITER_CONCEPT(I) denotes random_access_iterator_tag.
- Otherwise, ITER_CONCEPT(I) does not denote a type.

[ Note

: *end note*

]ITER_TRAITS enables independent syntactic determination
of an iterator's category and concept.

— [ Example

: — *end example*

]struct I { using value_type = int; using difference_type = int; int operator*() const; I& operator++(); I operator++(int); I& operator--(); I operator--(int); bool operator==(I) const; bool operator!=(I) const; };iterator_traits<I>::iterator_category denotes input_iterator_tag, and ITER_CONCEPT(I) denotes random_access_iterator_tag.

Types that are readable by applying operator*
model the Readable concept, including
pointers, smart pointers, and iterators.

template<class In> concept Readable = requires { typename iter_value_t<In>; typename iter_reference_t<In>; typename iter_rvalue_reference_t<In>; } && CommonReference<iter_reference_t<In>&&, iter_value_t<In>&> && CommonReference<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> && CommonReference<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;

The Writable concept specifies the requirements for writing a value
into an iterator's referenced object.

template<class Out, class T> concept Writable = requires(Out&& o, T&& t) { *o = std::forward<T>(t); // not required to be equality-preserving *std::forward<Out>(o) = std::forward<T>(t); // not required to be equality-preserving const_cast<const iter_reference_t<Out>&&>(*o) = std::forward<T>(t); // not required to be equality-preserving const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) = std::forward<T>(t); // not required to be equality-preserving };

Let E be an an expression such that decltype((E)) is T,
and let o be a dereferenceable object of type Out.

Out and T model Writable<Out, T> only if

If E is an xvalue ([basic.lval]), the resulting
state of the object it denotes is valid but unspecified ([lib.types.movedfrom]).

[ Note

: *end note*

]Writable has the awkward const_cast expressions to reject
iterators with prvalue non-proxy reference types that permit rvalue
assignment but do not also permit const rvalue assignment.

Consequently, an iterator type I that returns std::string
by value does not model Writable<I, std::string>.

— The WeaklyIncrementable concept specifies the requirements on
types that can be incremented with the pre- and post-increment operators.

The increment operations are not required to be equality-preserving,
nor is the type required to be EqualityComparable.

template<class I> concept WeaklyIncrementable = Semiregular<I> && requires(I i) { typename iter_difference_t<I>; requires SignedIntegral<iter_difference_t<I>>; { ++i } -> Same<I&>; // not required to be equality-preserving i++; // not required to be equality-preserving };

I models WeaklyIncrementable<I> only if

[ Note

: *end note*

](Equality does not guarantee the substitution property or referential
transparency.)

Algorithms on weakly incrementable types should never attempt to pass
through the same incrementable value twice.

They should be single-pass algorithms.

These algorithms
can be used with istreams as the source of the input data through the istream_iterator class
template.

— The Incrementable concept specifies requirements on types that can be incremented with the pre-
and post-increment operators.

The increment operations are required to be equality-preserving,
and the type is required to be EqualityComparable.

[ Note

: *end note*

]This supersedes the annotations on the increment expressions
in the definition of WeaklyIncrementable.

— template<class I> concept Incrementable = Regular<I> && WeaklyIncrementable<I> && requires(I i) { { i++ } -> Same<I>; };

I models Incrementable only if

The Iterator concept forms the basis
of the iterator concept taxonomy; every iterator models Iterator.

This concept specifies operations for dereferencing and incrementing
an iterator.

Most algorithms will require additional operations
to compare iterators with sentinels ([iterator.concept.sentinel]), to
read ([iterator.concept.input]) or write ([iterator.concept.output]) values, or
to provide a richer set of iterator movements ([iterator.concept.forward],
[iterator.concept.bidir], [iterator.concept.random.access]).

template<class I> concept Iterator = requires(I i) { { *i } -> can-reference; } && WeaklyIncrementable<I>;

The Sentinel concept specifies the relationship
between an Iterator type and a Semiregular type
whose values denote a range.

```
template<class S, class I>
concept Sentinel =
Semiregular<S> &&
Iterator<I> &&
weakly-equality-comparable-with<S, I>; // See [concept.equalitycomparable]
```

The SizedSentinel concept specifies
requirements on an Iterator and a Sentinel
that allow the use of the - operator to compute the distance
between them in constant time.

```
template<class S, class I>
concept SizedSentinel =
Sentinel<S, I> &&
!disable_sized_sentinel<remove_cv_t<S>, remove_cv_t<I>> &&
requires(const I& i, const S& s) {
{ s - i } -> Same<iter_difference_t<I>>;
{ i - s } -> Same<iter_difference_t<I>>;
};
```

S and I model SizedSentinel<S, I> only if

[ Example

: *end example*

]The SizedSentinel concept is modeled by pairs of
RandomAccessIterators ([iterator.concept.random.access]) and by
counted iterators and their sentinels ([counted.iterator]).

— The InputIterator concept defines requirements for a type
whose referenced values can be read (from the requirement for
Readable ([iterator.concept.readable])) and which can be both pre- and
post-incremented.

[ Note

: *end note*

]Unlike the Cpp17InputIterator requirements ([input.iterators]),
the InputIterator concept does not need
equality comparison since iterators are typically compared to sentinels.

— template<class I> concept InputIterator = Iterator<I> && Readable<I> && requires { typename ITER_CONCEPT(I); } && DerivedFrom<ITER_CONCEPT(I), input_iterator_tag>;

The OutputIterator concept defines requirements for a type that
can be used to write values (from the requirement for
Writable ([iterator.concept.writable])) and which can be both pre- and post-incremented.

template<class I, class T> concept OutputIterator = Iterator<I> && Writable<I, T> && requires(I i, T&& t) { *i++ = std::forward<T>(t); // not required to be equality-preserving };

Let E be an expression such that decltype((E)) is T, and let i be a
dereferenceable object of type I.

I and T model OutputIterator<I, T> only if
*i++ = E; has effects equivalent to:

*i = E; ++i;

The ForwardIterator concept adds equality comparison and
the multi-pass guarantee, specified below.

template<class I> concept ForwardIterator = InputIterator<I> && DerivedFrom<ITER_CONCEPT(I), forward_iterator_tag> && Incrementable<I> && Sentinel<I, I>;

The domain of == for forward iterators is that of iterators over the same
underlying sequence.

However, value-initialized iterators of the same type
may be compared and shall compare equal to other value-initialized iterators of the same type.

Pointers and references obtained from a forward iterator into a range [i, s)
shall remain valid while [i, s) continues to denote a range.

The BidirectionalIterator concept adds the ability
to move an iterator backward as well as forward.

template<class I> concept BidirectionalIterator = ForwardIterator<I> && DerivedFrom<ITER_CONCEPT(I), bidirectional_iterator_tag> && requires(I i) { { --i } -> Same<I&>; { i-- } -> Same<I>; };

I models BidirectionalIterator only if:

The RandomAccessIterator concept adds support for
constant-time advancement with +=, +, -=, and -,
as well as the computation of distance in constant time with -.

Random access iterators also support array notation via subscripting.

template<class I> concept RandomAccessIterator = BidirectionalIterator<I> && DerivedFrom<ITER_CONCEPT(I), random_access_iterator_tag> && StrictTotallyOrdered<I> && SizedSentinel<I, I> && requires(I i, const I j, const iter_difference_t<I> n) { { i += n } -> Same<I&>; { j + n } -> Same<I>; { n + j } -> Same<I>; { i -= n } -> Same<I&>; { j - n } -> Same<I>; { j[n] } -> Same<iter_reference_t<I>>; };

Let a and b be valid iterators of type I
such that b is reachable from a
after n applications of ++a,
let D be iter_difference_t<I>,
and let n denote a value of type D.

I models RandomAccessIterator only if

- For any two positive values x and y of type D, if (a + D(x + y)) is valid, then (a + D(x + y)) is equal to ((a + x) + y).

The ContiguousIterator concept provides a guarantee that
the denoted elements are stored contiguously in memory.

template<class I> concept ContiguousIterator = RandomAccessIterator<I> && DerivedFrom<ITER_CONCEPT(I), contiguous_iterator_tag> && is_lvalue_reference_v<iter_reference_t<I>> && Same<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>>;

In the following sections,
a
and
b
denote values of type
X or const X,
difference_type and reference refer to the
types iterator_traits<X>::difference_type and
iterator_traits<X>::reference, respectively,
n
denotes a value of
difference_type,
u,
tmp,
and
m
denote identifiers,
r
denotes a value of
X&,
t
denotes a value of value type
T,
o
denotes a value of some type that is writable to the output iterator.

The Cpp17Iterator requirements form the basis of the iterator
taxonomy; every iterator satisfies the Cpp17Iterator requirements.

This
set of requirements specifies operations for dereferencing and incrementing
an iterator.

Most algorithms will require additional operations to
read ([input.iterators]) or write ([output.iterators]) values, or
to provide a richer set of iterator movements ([forward.iterators],
[bidirectional.iterators], [random.access.iterators]).

A type X satisfies the Cpp17Iterator requirements if:

- X satisfies the Cpp17CopyConstructible, Cpp17CopyAssignable, and Cpp17Destructible requirements ([utility.arg.requirements]) and lvalues of type X are swappable ([swappable.requirements]), and

A class or pointer type
X
satisfies the requirements of an input iterator for the value type
T
if
X satisfies the Cpp17Iterator ([iterator.iterators]) and
Cpp17EqualityComparable (Table 23) requirements and
the expressions in Table 74 are valid and have
the indicated semantics.

In Table 74, the term
*the domain of ==*
is used in the ordinary mathematical sense to denote
the set of values over which
== is (required to be) defined.

This set can change over time.

Each algorithm places additional requirements on the domain of
== for the iterator values it uses.

[ Example

: *end example*

]The call find(a,b,x)
is defined only if the value of a
has the property p
defined as follows:
b has property p
and a value i
has property p
if
(*i==x)
or if
(*i!=x
and
++i
has property
p).

— Table 74 — Cpp17InputIterator requirements (in addition to Cpp17Iterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

a != b | contextually convertible to bool | !(a == b) | |

*a | reference, convertible to T | ||

a->m | (*a).m | ||

++r | X& | Ensures: r is dereferenceable or r is past-the-end; any copies of the previous value of r are no longer required to be dereferenceable nor to be in the domain of ==. | |

(void)r++ | equivalent to (void)++r | ||

*r++ | convertible to T | { T tmp = *r; ++r; return tmp; } |

[ Note

: *end note*

](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
*single pass*
algorithms.

These algorithms can be used with istreams as the source of the input data through the
istream_iterator
class template.

— A class or pointer type
X
satisfies the requirements of an output iterator
if X satisfies the Cpp17Iterator requirements ([iterator.iterators])
and the expressions in Table 75
are valid and have the indicated semantics.

[ Note

: *end note*

]The only valid use of an
operator*
is on the left side of the assignment statement.

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 single-pass algorithms.

Equality and inequality might not be defined.

— A class or pointer type
X
satisfies the requirements of a forward iterator if

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.

[ Note

: *end note*

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

— Table 76 — Cpp17ForwardIterator requirements (in addition to Cpp17InputIterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

r++ | convertible to const X& | { X tmp = r; ++r; return tmp; } | |

*r++ | reference |

If a and b are equal, then either a and b
are both dereferenceable
or else neither is dereferenceable.

A class or pointer type
X
satisfies the requirements of a bidirectional iterator if,
in addition to satisfying the Cpp17ForwardIterator requirements,
the following expressions are valid as shown in Table 77.

Table 77 — Cpp17BidirectionalIterator requirements (in addition to Cpp17ForwardIterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

--r | X& | ||

r-- | convertible to const X& | { X tmp = r; --r; return tmp; } | |

*r-- | reference |

A class or pointer type
X
satisfies the requirements of a random access iterator if,
in addition to satisfying the Cpp17BidirectionalIterator requirements,
the following expressions are valid as shown in Table 78.

Table 78 — Cpp17RandomAccessIterator requirements (in addition to Cpp17BidirectionalIterator)

Expression | Return type | Operational | Assertion/note |

semantics | pre-/post-condition | ||

r += n | X& | { difference_type m = n; if (m >= 0) while (m--) ++r; else while (m++) --r; return r; } | |

a + n n + a | X | { X tmp = a; return tmp += n; } | a + n == n + a. |

r -= n | X& | return r += -n; | |

a - n | X | { X tmp = a; return tmp -= n; } | |

b - a | difference_type | return n | |

a[n] | convertible to reference | *(a + n) | |

a < b | contextually
convertible to bool | b - a > 0 | < is a total ordering relation |

a > b | contextually
convertible to bool | b < a | |

a >= b | contextually
convertible to bool | !(a < b) | |

a <= b | contextually
convertible to bool. | !(a > b) |

There are several concepts that group requirements of algorithms that
take callable objects ([func.def]) as arguments.

The indirect callable concepts are used to constrain those algorithms
that accept callable objects ([func.def]) as arguments.

namespace std { template<class F, class I> concept IndirectUnaryInvocable = Readable<I> && CopyConstructible<F> && Invocable<F&, iter_value_t<I>&> && Invocable<F&, iter_reference_t<I>> && Invocable<F&, iter_common_reference_t<I>> && CommonReference< invoke_result_t<F&, iter_value_t<I>&>, invoke_result_t<F&, iter_reference_t<I>>>; template<class F, class I> concept IndirectRegularUnaryInvocable = Readable<I> && CopyConstructible<F> && RegularInvocable<F&, iter_value_t<I>&> && RegularInvocable<F&, iter_reference_t<I>> && RegularInvocable<F&, iter_common_reference_t<I>> && CommonReference< invoke_result_t<F&, iter_value_t<I>&>, invoke_result_t<F&, iter_reference_t<I>>>; template<class F, class I> concept IndirectUnaryPredicate = Readable<I> && CopyConstructible<F> && Predicate<F&, iter_value_t<I>&> && Predicate<F&, iter_reference_t<I>> && Predicate<F&, iter_common_reference_t<I>>; template<class F, class I1, class I2 = I1> concept IndirectRelation = Readable<I1> && Readable<I2> && CopyConstructible<F> && Relation<F&, iter_value_t<I1>&, iter_value_t<I2>&> && Relation<F&, iter_value_t<I1>&, iter_reference_t<I2>> && Relation<F&, iter_reference_t<I1>, iter_value_t<I2>&> && Relation<F&, iter_reference_t<I1>, iter_reference_t<I2>> && Relation<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>; template<class F, class I1, class I2 = I1> concept IndirectStrictWeakOrder = Readable<I1> && Readable<I2> && CopyConstructible<F> && StrictWeakOrder<F&, iter_value_t<I1>&, iter_value_t<I2>&> && StrictWeakOrder<F&, iter_value_t<I1>&, iter_reference_t<I2>> && StrictWeakOrder<F&, iter_reference_t<I1>, iter_value_t<I2>&> && StrictWeakOrder<F&, iter_reference_t<I1>, iter_reference_t<I2>> && StrictWeakOrder<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>; }

Class template projected is used to constrain algorithms
that accept callable objects and projections ([defns.projection]).

It combines a Readable type I and
a callable object type Proj into a new Readable type
whose reference type is the result of applying
Proj to the iter_reference_t of I.

namespace std { template<Readable I, IndirectRegularUnaryInvocable<I> Proj> struct projected { using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>; indirect_result_t<Proj&, I> operator*() const; // not defined }; template<WeaklyIncrementable I, class Proj> struct incrementable_traits<projected<I, Proj>> { using difference_type = iter_difference_t<I>; }; }

There are several additional iterator concepts that are commonly applied
to families of algorithms.

These group together iterator requirements
of algorithm families.

There are three relational concepts that specify
how element values are transferred between Readable and
Writable types:
IndirectlyMovable,
IndirectlyCopyable, and
IndirectlySwappable.

There is one relational concept for comparing values from different sequences:
IndirectlyComparable.

[ Note

: *end note*

]The ranges::less function object type
used in the concepts below imposes constraints on the concepts' arguments
in addition to those that appear in the concepts' bodies ([range.cmp]).

— The IndirectlyMovable concept specifies the relationship between
a Readable type and a Writable type between which
values may be moved.

template<class In, class Out> concept IndirectlyMovable = Readable<In> && Writable<Out, iter_rvalue_reference_t<In>>;

The IndirectlyMovableStorable concept augments
IndirectlyMovable with additional requirements enabling
the transfer to be performed through an intermediate object of the
Readable type's value type.

template<class In, class Out> concept IndirectlyMovableStorable = IndirectlyMovable<In, Out> && Writable<Out, iter_value_t<In>> && Movable<iter_value_t<In>> && Constructible<iter_value_t<In>, iter_rvalue_reference_t<In>> && Assignable<iter_value_t<In>&, iter_rvalue_reference_t<In>>;

In and Out model IndirectlyMovableStorable<In, Out>
only if after the initialization of the object obj in

iter_value_t<In> obj(ranges::iter_move(i));obj is equal to the value previously denoted by *i.

If
iter_rvalue_reference_t<In> is an rvalue reference type,
the resulting state of the value denoted by *i is
valid but unspecified ([lib.types.movedfrom]).

The IndirectlyCopyable concept specifies the relationship between
a Readable type and a Writable type between which
values may be copied.

template<class In, class Out> concept IndirectlyCopyable = Readable<In> && Writable<Out, iter_reference_t<In>>;

The IndirectlyCopyableStorable concept augments
IndirectlyCopyable with additional requirements enabling
the transfer to be performed through an intermediate object of the
Readable type's value type.

It also requires the capability
to make copies of values.

template<class In, class Out> concept IndirectlyCopyableStorable = IndirectlyCopyable<In, Out> && Writable<Out, const iter_value_t<In>&> && Copyable<iter_value_t<In>> && Constructible<iter_value_t<In>, iter_reference_t<In>> && Assignable<iter_value_t<In>&, iter_reference_t<In>>;

In and Out model IndirectlyCopyableStorable<In, Out>
only if after the initialization of the object obj in

iter_value_t<In> obj(*i);obj is equal to the value previously denoted by *i.

If
iter_reference_t<In> is an rvalue reference type, the resulting state
of the value denoted by *i is
valid but unspecified ([lib.types.movedfrom]).

The IndirectlySwappable concept specifies a swappable relationship
between the values referenced by two Readable types.

template<class I1, class I2 = I1> concept IndirectlySwappable = Readable<I1> && Readable<I2> && requires(I1& i1, I2& i2) { ranges::iter_swap(i1, i1); ranges::iter_swap(i2, i2); ranges::iter_swap(i1, i2); ranges::iter_swap(i2, i1); };

The IndirectlyComparable concept specifies
the common requirements of algorithms that
compare values from two different sequences.

template<class I1, class I2, class R, class P1 = identity, class P2 = identity> concept IndirectlyComparable = IndirectRelation<R, projected<I1, P1>, projected<I2, P2>>;

The Mergeable concept specifies the requirements of algorithms
that merge sorted sequences into an output sequence by copying elements.

template<class I1, class I2, class Out, class R = ranges::less, class P1 = identity, class P2 = identity> concept Mergeable = InputIterator<I1> && InputIterator<I2> && WeaklyIncrementable<Out> && IndirectlyCopyable<I1, Out> && IndirectlyCopyable<I2, Out> && IndirectStrictWeakOrder<R, projected<I1, P1>, projected<I2, P2>>;