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* =
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).