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
indirectly_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-like type ([iterator.concept.winc]) 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 85.

Table 85: Relations among iterator categories [tab:iterators.relations]

Contiguous | β Random Access | β Bidirectional | β Forward | β Input | |

β Output |

The six categories of iterators correspond to the iterator concepts

- input_iterator ([iterator.concept.input]),
- output_iterator ([iterator.concept.output]),
- forward_iterator ([iterator.concept.forward]),
- bidirectional_iterator ([iterator.concept.bidir]),
- random_access_iterator ([iterator.concept.random.access]), and
- contiguous_iterator ([iterator.concept.contiguous]),

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

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

Iterators that further meet 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 1*: *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.

Such a value is called a *past-the-end value*.

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

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

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 meet the
*Cpp17DefaultConstructible* requirements, using a value-initialized iterator
as the source of a copy or move operation.

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 sentinel s is called *reachable from* an iterator i if
and only if there is a finite sequence of applications of the expression
++i that makes i == s.

A *counted range* is empty if n == 0;
otherwise, 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.

Destruction of an iterator may invalidate pointers and references previously
obtained from that iterator if its type does not meet the
*Cpp17ForwardIterator* requirements and does not model forward_iterator.

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

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
weakly_incrementable 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 indirectly readable types,
it is often necessary
to determine the value type that corresponds to
a particular indirectly readable type.

Accordingly, it is required that if R is the name of a type that
models the indirectly_readable concept ([iterator.concept.readable]),
the type
iter_value_t<R>
be defined as the indirectly 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*<T> {
using value_type = remove_cv_t<T>;
};
template<class T>
concept *has-member-value-type* = requires { typename T::value_type; }; // *exposition only*
template<class T>
concept *has-member-element-type* = requires { typename T::element_type; }; // *exposition only*
template<class> struct indirectly_readable_traits { };
template<class T>
struct indirectly_readable_traits<T*>
: *cond-value-type*<T> { };
template<class I>
requires is_array_v<I>
struct indirectly_readable_traits<I> {
using value_type = remove_cv_t<remove_extent_t<I>>;
};
template<class I>
struct indirectly_readable_traits<const I>
: indirectly_readable_traits<I> { };
template<*has-member-value-type* T>
struct indirectly_readable_traits<T>
: *cond-value-type*<typename T::value_type> { };
template<*has-member-element-type* T>
struct indirectly_readable_traits<T>
: *cond-value-type*<typename T::element_type> { };
template<*has-member-value-type* T>
requires *has-member-element-type*<T>
struct indirectly_readable_traits<T> { };
template<*has-member-value-type* T>
requires *has-member-element-type*<T> &&
same_as<remove_cv_t<typename T::element_type>, remove_cv_t<typename T::value_type>>
struct indirectly_readable_traits<T>
: *cond-value-type*<typename T::value_type> { };
template<class T> using iter_value_t = *see below*;

[*Note 2*: *end note*]

Smart pointers like shared_ptr<int> are indirectly_readable and
have an associated value type, but a smart pointer like shared_ptr<void>
is not indirectly_readable and has no associated value type.

β 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_category
be defined as the iterator's iterator category.

In addition, the types
iterator_traits<I>::pointer
iterator_traits<I>::reference
shall 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>::reference
may be defined as void.

The definitions in this subclause make use of the following
exposition-only concepts:
template<class I>
concept *cpp17-iterator* =
requires(I i) {
{ *i } -> *can-reference*;
{ ++i } -> same_as<I&>;
{ *i++ } -> *can-reference*;
} && copyable<I>;
template<class I>
concept *cpp17-input-iterator* =
*cpp17-iterator*<I> && equality_comparable<I> && requires(I i) {
typename incrementable_traits<I>::difference_type;
typename indirectly_readable_traits<I>::value_type;
typename common_reference_t<iter_reference_t<I>&&,
typename indirectly_readable_traits<I>::value_type&>;
typename common_reference_t<decltype(*i++)&&,
typename indirectly_readable_traits<I>::value_type&>;
requires signed_integral<typename incrementable_traits<I>::difference_type>;
};
template<class I>
concept *cpp17-forward-iterator* =
*cpp17-input-iterator*<I> && constructible_from<I> &&
is_reference_v<iter_reference_t<I>> &&
same_as<remove_cvref_t<iter_reference_t<I>>,
typename indirectly_readable_traits<I>::value_type> &&
requires(I i) {
{ i++ } -> convertible_to<const I&>;
{ *i++ } -> same_as<iter_reference_t<I>>;
};
template<class I>
concept *cpp17-bidirectional-iterator* =
*cpp17-forward-iterator*<I> && requires(I i) {
{ --i } -> same_as<I&>;
{ i-- } -> convertible_to<const I&>;
{ *i-- } -> same_as<iter_reference_t<I>>;
};
template<class I>
concept *cpp17-random-access-iterator* =
*cpp17-bidirectional-iterator*<I> && totally_ordered<I> &&
requires(I i, typename incrementable_traits<I>::difference_type n) {
{ i += n } -> same_as<I&>;
{ i -= n } -> same_as<I&>;
{ i + n } -> same_as<I>;
{ n + i } -> same_as<I>;
{ i - n } -> same_as<I>;
{ i - i } -> same_as<decltype(n)>;
{ i[n] } -> convertible_to<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 indirectly_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.

- random_access_iterator_tag
if
I satisfies

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

[*Example 1*: *end example*]

To indicate conformance to the input_iterator concept
but a lack of conformance to
the *Cpp17InputIterator* requirements ([input.iterators]),
an iterator_traits specialization might have
iterator_concept denote input_iterator_tag
but not define iterator_category.

β 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 2*: *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 a subexpression E is
expression-equivalent to:

- iter_move(E), if E has class or enumeration type and iter_move(E) is a well-formed expression when treated as an unevaluated operand, where the meaning of iter_move is established as-if by performing argument-dependent lookup only ([basic.lookup.argdep]).

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<X>
```*iter-exchange-move*(X&& x, Y&& y)
noexcept(noexcept(iter_value_t<X>(iter_move(x))) &&
noexcept(*x = iter_move(y)));

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

- (void)iter_swap(E1, E2), if either E1 or E2 has class or enumeration type and iter_swap(E1, E2) is a well-formed expression 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, no diagnostic required.[
*Note 1*:This precludes calling unconstrained std::iter_swap.When the deleted overload is viable, program-defined overloads need to be more specialized ([temp.func.order]) to be selected.β*end note*] - Otherwise, if the types of E1 and E2 each model indirectly_readable, and if the reference types of E1 and E2 model swappable_with ([concept.swappable]), then ranges::swap(*E1, *E2).
- Otherwise, if the types T1 and T2 of E1 and E2 model indirectly_movable_storable<T1, T2> and indirectly_movable_storable<T2, T1>, then (void)(*E1 =
*iter-exchange-move*(E2, E1)), except that E1 is evaluated only once.

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.

[*Example 1*: *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;
};
iterator_traits<I>::iterator_category denotes input_iterator_tag,
and *ITER_CONCEPT*(I) denotes random_access_iterator_tag.

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

template<class In>
concept *indirectly-readable-impl* = // *exposition only*
requires(const In in) {
typename iter_value_t<In>;
typename iter_reference_t<In>;
typename iter_rvalue_reference_t<In>;
{ *in } -> same_as<iter_reference_t<In>>;
{ ranges::iter_move(in) } -> same_as<iter_rvalue_reference_t<In>>;
} &&
common_reference_with<iter_reference_t<In>&&, iter_value_t<In>&> &&
common_reference_with<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> &&
common_reference_with<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;

template<class In>
concept indirectly_readable =
*indirectly-readable-impl*<remove_cvref_t<In>>;

Given a value i of type I, I models indirectly_readable
only if the expression *i is equality-preserving.

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

template<class Out, class T>
concept indirectly_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 expression such that decltype((E)) is T,
and let o be a dereferenceable object of type Out.

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

- If Out and T model indirectly_readable<Out> && same_as<iter_value_t<Out>, decay_t<T>>, then *o after any above assignment is equal to the value of E before the assignment.

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

[*Note 2*: *end note*]

indirectly_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 indirectly_writable<I, std::string>.

β The weakly_incrementable 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 equality_comparable.

template<class T>
constexpr bool *is-integer-like* = *see below*; // *exposition only*
template<class T>
constexpr bool *is-signed-integer-like* = *see below*; // *exposition only*
template<class I>
concept weakly_incrementable =
movable<I> &&
requires(I i) {
typename iter_difference_t<I>;
requires *is-signed-integer-like*<iter_difference_t<I>>;
{ ++i } -> same_as<I&>; // not required to be equality-preserving
i++; // not required to be equality-preserving
};

A type I is an *integer-class type*
if it is in a set of implementation-defined types
that behave as integer types do, as defined below.

The range of representable values of an integer-class type
is the continuous set of values over which it is defined.

For any integer-class type,
its range of representable values is
either to (inclusive) for some integer N,
in which case it is a *signed-integer-class type*, or
0 to (inclusive) for some integer N,
in which case it is an *unsigned-integer-class type*.

The width of an integer-class type is greater than
that of every integral type of the same signedness.

A type I other than cv bool is *integer-like*
if it models integral<I> or
if it is an integer-class type.

An integer-like type I is *signed-integer-like*
if it models signed_integral<I> or
if it is a signed-integer-class type.

An integer-like type I is *unsigned-integer-like*
if it models unsigned_integral<I> or
if it is an unsigned-integer-class type.

For every integer-class type I,
let B(I) be a unique hypothetical extended integer type
of the same signedness with the same width ([basic.fundamental]) as I.

[*Note 2*: *end note*]

The corresponding hypothetical specialization numeric_limits<B(I)>
meets the requirements on numeric_limits specializations
for integral types ([numeric.limits]).

β Expressions of integer-class type are
explicitly convertible to any integer-like type, and
implicitly convertible to any integer-class type
of equal or greater width and the same signedness.

Expressions of integral type are
both implicitly and explicitly convertible to any integer-class type.

Conversions between integral and integer-class types
and between two integer-class types do not exit via an exception.

The result of such a conversion is the unique value of the destination type
that is congruent to the source modulo ,
where N is the width of the destination type.

Let a be an object of integer-class type I,
let b be an object of integer-like type I2
such that the expression b is implicitly convertible to I,
let x and y be, respectively,
objects of type B(I) and B(I2) as described above
that represent the same values as a and b, and
let c be an lvalue of any integral type.

- The expressions ++a, --a, and &a shall be expression-equivalent to a += 1, a -= 1, and addressof(a), respectively.
- For every
*unary-operator*@ other than & for which the expression @x is well-formed, @a shall also be well-formed and have the same value, effects, and value category as @x. - For every non-assignment binary operator @ for which x @ y and y @ x are well-formed, a @ b and b @ a shall also be well-formed and shall have the same value, effects, and value category as x @ y and y @ x, respectively.If x @ y or y @ x has type B(I), then a @ b or b @ a, respectively, has type I; if x @ y or y @ x has type B(I2), then a @ b or b @ a, respectively, has type I2; if x @ y or y @ x has any other type, then a @ b or b @ a, respectively, has that type.

An expression E of integer-class type I is
contextually convertible to bool
as if by bool(E != I(0)).

All integer-class types model
regular ([concepts.object]) and
three_way_comparable<strong_ordering> ([cmp.concept]).

For every (possibly cv-qualified) integer-class type I,
numeric_limits<I> is specialized such that
each static data member m
has the same value as numeric_limits<B(I)>::m, and
each static member function f
returns I(numeric_limits<B(I)>::f()).

For any two integer-like types I1 and I2,
at least one of which is an integer-class type,
common_type_t<I1, I2> denotes an integer-class type
whose width is not less than that of I1 or I2.

If both I1 and I2 are signed-integer-like types,
then common_type_t<I1, I2> is also a signed-integer-like type.

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

[*Note 1*: *end note*]

This supersedes the annotations on the increment expressions
in the definition of weakly_incrementable.

β template<class I>
concept incrementable =
regular<I> &&
weakly_incrementable<I> &&
requires(I i) {
{ i++ } -> same_as<I>;
};

[*Note 2*: *end note*]

The requirement that
a equals b
implies
++a equals ++b
(which is not true for weakly incrementable types)
allows the use of multi-pass one-directional
algorithms with types that model incrementable.

β The input_or_output_iterator concept forms the basis
of the iterator concept taxonomy; every iterator models input_or_output_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 input_or_output_iterator =
requires(I i) {
{ *i } -> *can-reference*;
} &&
weakly_incrementable<I>;

[*Note 1*: *end note*]

Unlike the *Cpp17Iterator* requirements,
the input_or_output_iterator concept does not require copyability.

β The sentinel_for concept specifies the relationship
between an input_or_output_iterator type and a semiregular type
whose values denote a range.

```
template<class S, class I>
concept sentinel_for =
semiregular<S> &&
input_or_output_iterator<I> &&
```*weakly-equality-comparable-with*<S, I>; // see [concept.equalitycomparable]

Types
S and I model sentinel_for<S, I> only if

- i == s is well-defined.
- assignable_from<I&, S> is either modeled or not satisfied.

The sized_sentinel_for concept specifies
requirements on an input_or_output_iterator type I and
a corresponding sentinel_for<I>
that allow the use of the - operator to compute the distance
between them in constant time.

```
template<class S, class I>
concept sized_sentinel_for =
sentinel_for<S, I> &&
!disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> &&
requires(const I& i, const S& s) {
{ s - i } -> same_as<iter_difference_t<I>>;
{ i - s } -> same_as<iter_difference_t<I>>;
};
```

```
template<class S, class I>
constexpr bool disable_sized_sentinel_for = false;
```

Such specializations shall
be usable in constant expressions ([expr.const]) and
have type const bool.

[*Note 1*: *end note*]

disable_sized_sentinel_for allows use of sentinels and iterators with
the library that satisfy but do not in fact model sized_sentinel_for.

β [*Example 1*: *end example*]

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

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

[*Note 1*: *end note*]

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

β template<class I>
concept input_iterator =
input_or_output_iterator<I> &&
indirectly_readable<I> &&
requires { typename *ITER_CONCEPT*(I); } &&
derived_from<*ITER_CONCEPT*(I), input_iterator_tag>;

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

template<class I, class T>
concept output_iterator =
input_or_output_iterator<I> &&
indirectly_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.

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

template<class I>
concept forward_iterator =
input_iterator<I> &&
derived_from<*ITER_CONCEPT*(I), forward_iterator_tag> &&
incrementable<I> &&
sentinel_for<I, I>;

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

Two dereferenceable iterators a and b of type X
offer the *multi-pass guarantee* if:

- a == b implies ++a == ++b and
- the expression ((void)[](X x){++x;}(a), *a) is equivalent to the expression *a.

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

template<class I>
concept bidirectional_iterator =
forward_iterator<I> &&
derived_from<*ITER_CONCEPT*(I), bidirectional_iterator_tag> &&
requires(I i) {
{ --i } -> same_as<I&>;
{ i-- } -> same_as<I>;
};

I models bidirectional_iterator only if:

- If a and b are decrementable,
then all of the following are true:
- addressof(--a) == addressof(a)
- bool(a-- == b)
- after evaluating both a-- and --b, bool(a == b) is still true
- bool(++(--a) == b)

- If a and b are incrementable, then bool(--(++a) == b).

The random_access_iterator 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 random_access_iterator =
bidirectional_iterator<I> &&
derived_from<*ITER_CONCEPT*(I), random_access_iterator_tag> &&
totally_ordered<I> &&
sized_sentinel_for<I, I> &&
requires(I i, const I j, const iter_difference_t<I> n) {
{ i += n } -> same_as<I&>;
{ j + n } -> same_as<I>;
{ n + j } -> same_as<I>;
{ i -= n } -> same_as<I&>;
{ j - n } -> same_as<I>;
{ j[n] } -> same_as<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 random_access_iterator 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 contiguous_iterator concept provides a guarantee that
the denoted elements are stored contiguously in memory.

template<class I>
concept contiguous_iterator =
random_access_iterator<I> &&
derived_from<*ITER_CONCEPT*(I), contiguous_iterator_tag> &&
is_lvalue_reference_v<iter_reference_t<I>> &&
same_as<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>> &&
requires(const I& i) {
{ to_address(i) } -> same_as<add_pointer_t<iter_reference_t<I>>>;
};

Let a and b be dereferenceable iterators and
c be a non-dereferenceable iterator of type I
such that b is reachable from a and
c is reachable from b,
and let D be iter_difference_t<I>.

The type I models contiguous_iterator only if

- to_address(a) == addressof(*a),
- to_address(b) == to_address(a) + D(b - a),
- to_address(c) == to_address(a) + D(c - a),
- ranges::iter_move(a) has the same type, value category, and effects as std::move(*a), and
- if ranges::iter_swap(a, b) is well-formed, it has effects equivalent to ranges::swap(*a, *b).

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.

[*Note 1*: β *end note*]

The *Cpp17Iterator* requirements form the basis of the iterator
taxonomy; every iterator meets 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 meets the *Cpp17Iterator* requirements if:

- X meets the
*Cpp17CopyConstructible*,*Cpp17CopyAssignable*,*Cpp17Swappable*, and*Cpp17Destructible*requirements ([utility.arg.requirements], [swappable.requirements]), and - iterator_traits<X>::difference_type is a signed integer type or void, and
- the expressions in Table 86 are valid and have the indicated semantics.

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

In Table 87, 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.

Table 87: *Cpp17InputIterator* requirements (in addition to *Cpp17Iterator*) [tab:inputiterator]

Expression | Return type | Operational | Assertion/note | |

semantics | pre-/post-condition | |||

a != b | decltype(a != b) models boolean-testable | !(a == b) | ||

*a | reference, convertible to T | |||

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

++r | X& | |||

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

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

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

Table 88: *Cpp17OutputIterator* requirements (in addition to *Cpp17Iterator*) [tab:outputiterator]

Expression | Return type | Operational | Assertion/note | |

semantics | pre-/post-condition | |||

*r = o | result is not used | |||

++r | X& | |||

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

*r++ = o | result is not used |

A class or pointer type
X
meets the *Cpp17ForwardIterator* requirements if

- X meets the
*Cpp17InputIterator*requirements ([input.iterators]), - X meets the
*Cpp17DefaultConstructible*requirements ([utility.arg.requirements]), - if X is a mutable iterator, reference is a reference to T; if X is a constant iterator, reference is a reference to const T,
- the expressions in Table 89 are valid and have the indicated semantics, and
- objects of type X offer the multi-pass guarantee, described below.

Two dereferenceable iterators a and b of type X offer the
*multi-pass guarantee* if:

- a == b implies ++a == ++b and
- X is a pointer type or the expression (void)++X(a), *a is equivalent to the expression *a.

[*Note 2*: *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.

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

Table 90: *Cpp17BidirectionalIterator* requirements (in addition to *Cpp17ForwardIterator*) [tab:bidirectionaliterator]

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 |

Table 91: *Cpp17RandomAccessIterator* requirements (in addition to *Cpp17BidirectionalIterator*) [tab:randomaccessiterator]

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 | decltype(a < b) models boolean-testable | Effects: Equivalent to: return b - a > 0; | < is a total ordering relation | |

a > b | decltype(a > b) models boolean-testable | b < a | ||

a >= b | decltype(a >= b) models boolean-testable | !(a < b) | ||

a <= b | decltype(a <= b) models boolean-testable | !(a > b) |

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

To implement algorithms taking projections,
it is necessary to determine the projected type of an iterator's value type.

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 indirectly_unary_invocable =
indirectly_readable<I> &&
copy_constructible<F> &&
invocable<F&, *indirect-value-t*<I>> &&
invocable<F&, iter_reference_t<I>> &&
invocable<F&, iter_common_reference_t<I>> &&
common_reference_with<
invoke_result_t<F&, *indirect-value-t*<I>>,
invoke_result_t<F&, iter_reference_t<I>>>;
template<class F, class I>
concept indirectly_regular_unary_invocable =
indirectly_readable<I> &&
copy_constructible<F> &&
regular_invocable<F&, *indirect-value-t*<I>> &&
regular_invocable<F&, iter_reference_t<I>> &&
regular_invocable<F&, iter_common_reference_t<I>> &&
common_reference_with<
invoke_result_t<F&, *indirect-value-t*<I>>,
invoke_result_t<F&, iter_reference_t<I>>>;
template<class F, class I>
concept indirect_unary_predicate =
indirectly_readable<I> &&
copy_constructible<F> &&
predicate<F&, *indirect-value-t*<I>> &&
predicate<F&, iter_reference_t<I>> &&
predicate<F&, iter_common_reference_t<I>>;
template<class F, class I1, class I2>
concept indirect_binary_predicate =
indirectly_readable<I1> && indirectly_readable<I2> &&
copy_constructible<F> &&
predicate<F&, *indirect-value-t*<I1>, *indirect-value-t*<I2>> &&
predicate<F&, *indirect-value-t*<I1>, iter_reference_t<I2>> &&
predicate<F&, iter_reference_t<I1>, *indirect-value-t*<I2>> &&
predicate<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
predicate<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
template<class F, class I1, class I2 = I1>
concept indirect_equivalence_relation =
indirectly_readable<I1> && indirectly_readable<I2> &&
copy_constructible<F> &&
equivalence_relation<F&, *indirect-value-t*<I1>, *indirect-value-t*<I2>> &&
equivalence_relation<F&, *indirect-value-t*<I1>, iter_reference_t<I2>> &&
equivalence_relation<F&, iter_reference_t<I1>, *indirect-value-t*<I2>> &&
equivalence_relation<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
equivalence_relation<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;
template<class F, class I1, class I2 = I1>
concept indirect_strict_weak_order =
indirectly_readable<I1> && indirectly_readable<I2> &&
copy_constructible<F> &&
strict_weak_order<F&, *indirect-value-t*<I1>, *indirect-value-t*<I2>> &&
strict_weak_order<F&, *indirect-value-t*<I1>, iter_reference_t<I2>> &&
strict_weak_order<F&, iter_reference_t<I1>, *indirect-value-t*<I2>> &&
strict_weak_order<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
strict_weak_order<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 an indirectly_readable type I and
a callable object type Proj into a new indirectly_readable type
whose reference type is the result of applying
Proj to the iter_reference_t of I.

namespace std {
template<class I, class Proj>
struct *projected-impl* { // *exposition only*
struct *type* { // *exposition only*
using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
using difference_type = iter_difference_t<I>; // present only if I
// models weakly_incrementable
indirect_result_t<Proj&, I> operator*() const; // *not defined*
};
};
template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
using projected = *projected-impl*<I, Proj>::*type*;
}

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
indirectly_readable and indirectly_writable types:
indirectly_movable,
indirectly_copyable, and
indirectly_swappable.

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

[*Note 1*: *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 indirectly_movable concept specifies the relationship between
an indirectly_readable type and an indirectly_writable type
between which values may be moved.

template<class In, class Out>
concept indirectly_movable =
indirectly_readable<In> &&
indirectly_writable<Out, iter_rvalue_reference_t<In>>;

The indirectly_movable_storable concept augments
indirectly_movable with additional requirements enabling
the transfer to be performed through an intermediate object of the
indirectly_readable type's value type.

template<class In, class Out>
concept indirectly_movable_storable =
indirectly_movable<In, Out> &&
indirectly_writable<Out, iter_value_t<In>> &&
movable<iter_value_t<In>> &&
constructible_from<iter_value_t<In>, iter_rvalue_reference_t<In>> &&
assignable_from<iter_value_t<In>&, iter_rvalue_reference_t<In>>;

In and Out model indirectly_movable_storable<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 indirectly_copyable concept specifies the relationship between
an indirectly_readable type and an indirectly_writable type
between which values may be copied.

template<class In, class Out>
concept indirectly_copyable =
indirectly_readable<In> &&
indirectly_writable<Out, iter_reference_t<In>>;

The indirectly_copyable_storable concept augments
indirectly_copyable with additional requirements enabling
the transfer to be performed through an intermediate object of the
indirectly_readable type's value type.

It also requires the capability
to make copies of values.

template<class In, class Out>
concept indirectly_copyable_storable =
indirectly_copyable<In, Out> &&
indirectly_writable<Out, iter_value_t<In>&> &&
indirectly_writable<Out, const iter_value_t<In>&> &&
indirectly_writable<Out, iter_value_t<In>&&> &&
indirectly_writable<Out, const iter_value_t<In>&&> &&
copyable<iter_value_t<In>> &&
constructible_from<iter_value_t<In>, iter_reference_t<In>> &&
assignable_from<iter_value_t<In>&, iter_reference_t<In>>;

In and Out model indirectly_copyable_storable<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 indirectly_swappable concept specifies a swappable relationship
between the values referenced by two indirectly_readable types.

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

The indirectly_comparable 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 indirectly_comparable =
indirect_binary_predicate<R, projected<I1, P1>, projected<I2, P2>>;

The permutable concept specifies the common requirements
of algorithms that reorder elements in place by moving or swapping them.

template<class I>
concept permutable =
forward_iterator<I> &&
indirectly_movable_storable<I, I> &&
indirectly_swappable<I, I>;

template<class I1, class I2, class Out, class R = ranges::less,
class P1 = identity, class P2 = identity>
concept mergeable =
input_iterator<I1> &&
input_iterator<I2> &&
weakly_incrementable<Out> &&
indirectly_copyable<I1, Out> &&
indirectly_copyable<I2, Out> &&
indirect_strict_weak_order<R, projected<I1, P1>, projected<I2, P2>>;

template<class I, class R = ranges::less, class P = identity>
concept sortable =
permutable<I> &&
indirect_strict_weak_order<R, projected<I, P>>;