[iterator.requirements] (original) (raw)

23 Iterators library [iterators]

23.3.1 In general [iterator.requirements.general]

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 iteratorisupports the expression*i, resulting in a value of some object typeT, called thevalue typeof the iterator.

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

For every iterator typeX, there is a corresponding signed integer-like type ([iterator.concept.winc]) called thedifference typeof 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, andcontiguous iterators, as shown in Table 83.

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

The generic term iterator refers to any type that models theinput_­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-names specified in [iterator.traits]shall be provided for the iterator type.

[Note 1:

Either the iterator type must provide the typedef-names directly (in which case iterator_­traits pick them up automatically), or an iterator_­traits specialization must provide them.

— _end note_]

Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding sequence.

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

Values of an iterator ifor which the expression *i is defined are called dereferenceable.

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

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

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.

[Note 2:

This guarantee is not offered for default-initialization, although the distinction only matters for types with trivial default constructors such as pointers or aggregates holding pointers.

— _end note_]

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

Dereferenceable values are always non-singular.

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

A range is an iterator and a sentinelthat designate the beginning and end of the computation, or an iterator and a count that designate the beginning and the number of elements to which the computation is to be applied.234

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

If s is reachable from i, [i, s) denotes a valid range.

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.

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

The result of the application of library functions to invalid ranges is undefined.

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

Therefore, requirement tables 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.

An invalid iteratoris an iterator that may be singular.235

Iterators are called constexpr iteratorsif all operations provided to meet iterator category requirements are constexpr functions.

[Note 3:

For example, the types “pointer to int” andreverse_­iterator<int*> are constexpr iterators.

— _end note_]

23.3.2 Associated types [iterator.assoc.types]

23.3.2.1 Incrementable traits [incrementable.traits]

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 theweakly_­incrementable concept ([iterator.concept.winc]), the typeiter_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;}

Let be remove_­cvref_­t<I>.

The type iter_­difference_­t<I> denotes

• incrementable_­traits<>​::​difference_­typeif iterator_­traits<> names a specialization generated from the primary template, and
• iterator_­traits<>​::​difference_­type otherwise.

Users may specialize incrementable_­traits on program-defined types.

23.3.2.2 Indirectly readable traits [readable.traits]

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 typeiter_value_t<R> be defined as the indirectly readable type's value type.

template<class> struct cond-value-type { }; template<class T> requires is_object_v<T> struct cond-value-type<T> { using value_type = remove_cv_t<T>;};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<class T> requires requires { typename T::value_type; } struct indirectly_readable_traits<T> : cond-value-type<typename T::value_type> { };template<class T> requires requires { typename T::element_type; } struct indirectly_readable_traits<T> : cond-value-type<typename T::element_type> { };template<class T> using iter_value_t = see below;

Let be remove_­cvref_­t<I>.

The type iter_­value_­t<I> denotes

• indirectly_­readable_­traits<>​::​value_­typeif iterator_­traits<> names a specialization generated from the primary template, and
• iterator_­traits<>​::​value_­type otherwise.

Class template indirectly_­readable_­traits may be specialized on program-defined types.

[Note 1:

Some legacy output iterators define a nested type named value_­typethat is an alias for void.

These types are not indirectly_­readableand have no associated value types.

— _end note_]

[Note 2:

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.

— _end note_]

23.3.2.3 Iterator traits [iterator.traits]

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 ifIis the type of an iterator, the typeiterator_traits<I>::iterator_categorybe defined as the iterator's iterator category.

In addition, the typesiterator_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 asdecltype(a.operator->()) anddecltype(*a), respectively.

The typeiterator_­traits<I>​::​pointershall be voidfor an iterator of class type Ithat does not support operator->.

Additionally, in the case of an output iterator, the typesiterator_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_­as<I&>;{ *i++ } -> can-reference;};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_lvalue_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 theiterator_­traits primary template are computed as follows:

• If I has valid ([temp.deduct]) member types difference_­type, value_­type,reference, and iterator_­category, theniterator_­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 conceptcpp17-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​::​pointer is valid and denotes a type,pointer names that type.
    Otherwise, ifdecltype(​declval<I&>().operator->()) is well-formed, thenpointer names that type.
    Otherwise, pointernames void.
  • If the qualified-id I​::​reference is valid and denotes a type, reference names that type.
    Otherwise, referencenames iter_­reference_­t<I>.
  • 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_­tagifI satisfies cpp17-random-access-iterator, or otherwise
    * bidirectional_­iterator_­tag ifI satisfies cpp17-bidirectional-iterator, or otherwise
    * forward_­iterator_­tag ifI satisfies cpp17-forward-iterator, or otherwise
    * input_­iterator_­tag.
• Otherwise, if I satisfies the exposition-only conceptcpp17-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 asnamespace 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 1:

To implement a genericreversefunction, 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;} }

— _end example_]

23.3.3 Customization point objects [iterator.cust]

23.3.3.1 ranges​::​iter_­move [iterator.cust.move]

The expression ranges​::​iter_­move(E) for a subexpression E is expression-equivalent to:

• iter_­move(E), ifE has class or enumeration type anditer_­move(E) is a well-formed expression when treated as an unevaluated operand, with overload resolution performed in a context that does not include a declaration of ranges​::​iter_­movebut does include the declarationvoid iter_move();
• Otherwise, if the expression *E is well-formed:
  • if *E is an lvalue, std​::​move(*E);
  • otherwise, *E.
• Otherwise, ranges​::​iter_­move(E) is ill-formed.
  [Note 1:
  This case can result in substitution failure when ranges​::​iter_­move(E)appears in the immediate context of a template instantiation.
  — _end note_]

If ranges​::​iter_­move(E) is not equal to *E, the program is ill-formed, no diagnostic required.

23.3.3.2 ranges​::​iter_­swap [iterator.cust.swap]

Let iter-exchange-move be the exposition-only function:

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)));

Effects: Equivalent to:iter_value_t<X> old_value(iter_move(x));*x = iter_move(y);return old_value;

The expression ranges​::​iter_­swap(E1, E2) for subexpressionsE1 and E2 is expression-equivalent to:

• (void)iter_­swap(E1, E2), if eitherE1 or E2 has class or enumeration type anditer_­swap(E1, E2) is a well-formed expression with overload resolution performed in a context that includes the declarationtemplate<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.
• Otherwise, if the types of E1 and E2 each modelindirectly_­readable, and if the reference types of E1 and E2model swappable_­with ([concept.swappable]), then ranges​::​swap(*E1, *E2).
• Otherwise, if the types T1 and T2 of E1 andE2 model indirectly_­movable_­storable<T1, T2> andindirectly_­movable_­storable<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.
  [Note 1:
  This case can result in substitution failure when ranges​::​iter_­swap(E1, E2)appears in the immediate context of a template instantiation.
  — _end note_]

23.3.4 Iterator concepts [iterator.concepts]

23.3.4.1 General [iterator.concepts.general]

For a type I, let ITER_­TRAITS(I) denote the type I if iterator_­traits<I> names a specialization generated from the primary template.

Otherwise, ITER_­TRAITS(I) denotesiterator_­traits<I>.

• 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 1:

ITER_­TRAITS enables independent syntactic determination of an iterator's category and concept.

— _end note_]

[Example 1:

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.

— _end example_]

23.3.4.2 Concept indirectly_­readable [iterator.concept.readable]

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_­readableonly if the expression *i is equality-preserving.

23.3.4.3 Concept indirectly_­writable [iterator.concept.writable]

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); *std::forward<Out>(o) = std::forward<T>(t); const_cast<const iter_reference_t<Out>&&>(*o) = std::forward<T>(t); const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) = std::forward<T>(t); };

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 modelindirectly_­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.

After evaluating any above assignment expression, o is not required to be dereferenceable.

[Note 1:

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

Assignment through the same value of the indirectly writable type happens only once.

— _end note_]

[Note 2:

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​::​stringby value does not model indirectly_­writable<I, std​::​string>.

— _end note_]

23.3.4.4 Concept weakly_­incrementable [iterator.concept.winc]

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> inline constexpr bool is-integer-like = see below; template<class T> inline constexpr bool is-signed-integer-like = see below; template<class I> concept weakly_­incrementable = default_initializable<I> && movable<I> && requires(I i) { typename iter_difference_t<I>;requires is-signed-integer-like<iter_difference_t<I>>;{ ++i } -> same_­as<I&>; i++; };

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

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

The values 0 and 1 are part of the range of every integer-class type.

If any negative numbers are part of the range, the type is a signed-integer-class type; otherwise, it is an unsigned-integer-class type.

For every integer-class type I, let B(I) be a hypothetical extended integer type of the same signedness with the smallest width ([basic.fundamental]) capable of representing the same range of values.

The width of I is equal to the width of B(I).

Let a and b be objects of integer-class type I, let x and y be objects of type B(I) as described above that represent the same values as a and b respectively, and let c be an lvalue of any integral type.

• For every unary operator @ 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 provided that value is representable by I.
  If @x has type bool, so too does @a; if @x has type B(I), then @a has type I.
• For every assignment operator @= for which c @= x is well-formed,c @= a shall also be well-formed and shall have the same value and effects as c @= x.
  The expression c @= a shall be an lvalue referring to c.
• For every binary operator @ for which x @ y is well-formed,a @ b shall also be well-formed and shall have the same value, effects, and value category as x @ y provided that value is representable by I.
  If x @ y has type bool, so too does a @ b; if x @ y has type B(I), then a @ b has type I.

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

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

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

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

A value-initialized object of integer-class type has value 0.

For every (possibly cv-qualified) integer-class type I,numeric_­limits<I> is specialized such that:

• numeric_­limits<I>​::​is_­specialized is true,
• numeric_­limits<I>​::​is_­signed is true if and only if I is a signed-integer-class type,
• numeric_­limits<I>​::​is_­integer is true,
• numeric_­limits<I>​::​is_­exact is true,
• numeric_­limits<I>​::​digits is equal to the width of the integer-class type,
• numeric_­limits<I>​::​digits10 is equal to static_­cast<int>(digits * log10(2)), and
• numeric_­limits<I>​::​min() and numeric_­limits<I>​::​max() return the lowest and highest representable values of I, respectively, andnumeric_­limits<I>​::​lowest() returns numeric_­limits<I>​::​​min().

A type I is integer-likeif it models integral<I> or if it is an integer-class type.

A type I is signed-integer-likeif it models signed_­integral<I> or if it is a signed-integer-class type.

A type I is unsigned-integer-likeif it models unsigned_­integral<I> or if it is an unsigned-integer-class type.

is-integer-like<I> is trueif and only if I is an integer-like type.

is-signed-integer-like<I> is trueif and only if I is a signed-integer-like type.

Let i be an object of type I.

When i is in the domain of both pre- and post-increment, i is said to be incrementable.

I models weakly_­incrementable<I> only if

• The expressions ++i and i++ have the same domain.
• If i is incrementable, then both ++i and i++ advance i to the next element.
• If i is incrementable, thenaddressof(++i) is equal toaddressof(i).

Recommended practice: The implementaton of an algorithm on a weakly incrementable type should never attempt to pass through the same incrementable value twice; such an algorithm should be a single-pass algorithm.

[Note 1:

For weakly_­incrementable types, a equals b does not imply that ++aequals ++b.

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

Such algorithms can be used with istreams as the source of the input data through the istream_­iterator class template.

— _end note_]

23.3.4.5 Concept incrementable [iterator.concept.inc]

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:

This supersedes the annotations on the increment expressions in the definition of weakly_­incrementable.

— _end note_]

template<class I> concept incrementable = regular<I> && weakly_­incrementable<I> && requires(I i) { { i++ } -> same_­as<I>;};

Let a and b be incrementable objects of type I.

I models incrementable only if

• If bool(a == b) then bool(a++ == b).
• If bool(a == b) then bool(((void)a++, a) == ++b).

[Note 2:

The requirement thata equals bimplies++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.

— _end note_]

23.3.4.6 Concept input_­or_­output_­iterator [iterator.concept.iterator]

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:

Unlike the Cpp17Iterator requirements, the input_­or_­output_­iterator concept does not require copyability.

— _end note_]

23.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]

The sentinel_­for concept specifies the relationship between an input_­or_­output_­iterator type and a semiregular type whose values denote a range.

Let s and i be values of type S andI such that [i, s) denotes a range.

TypesS and I model sentinel_­for<S, I> only if

• If bool(i != s) then i is dereferenceable and [++i, s) denotes a range.

The domain of == is not static.

Given an iterator i and sentinel s such that [i, s) denotes a range and i != s, i and s are not required to continue to denote a range after incrementing any other iterator equal to i.

Consequently, i == s is no longer required to be well-defined.

23.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]

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](#concept:sized%5Fsentinel%5Ffor "23.3.4.8 Concept sized_­sentinel_­for [iterator.concept.sizedsentinel]") = [sentinel_­for](#concept:sentinel%5Ffor "23.3.4.7 Concept sentinel_­for [iterator.concept.sentinel]")<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](concept.same#concept:same%5Fas "18.4.2 Concept same_­as [concept.same]")<iter_difference_t<I>>;{ i - s } -> [same_­as](concept.same#concept:same%5Fas "18.4.2 Concept same_­as [concept.same]")<iter_difference_t<I>>;};

Let i be an iterator of type I, and sa sentinel of type S such that [i, s) denotes a range.

Let N be the smallest number of applications of ++inecessary to make bool(i == s) be true.

S and I model sized_­sentinel_­for<S, I> only if

• If N is representable by iter_­difference_­t<I>, then s - i is well-defined and equals N.
• If is representable by iter_­difference_­t<I>, then i - s is well-defined and equals .

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

Remarks: Pursuant to [namespace.std], users may specialize disable_­sized_­sentinel_­forfor cv-unqualified non-array object types S and Iif S and/or I is a program-defined type.

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

[Note 1:

disable_­sized_­sentinel_­for allows use of sentinels and iterators with the library that satisfy but do not in fact model sized_­sentinel_­for.

— _end note_]

[Example 1:

The sized_­sentinel_­for concept is modeled by pairs ofrandom_­access_­iterators ([iterator.concept.random.access]) and by counted iterators and their sentinels ([counted.iterator]).

— _end example_]

23.3.4.9 Concept input_­iterator [iterator.concept.input]

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

[Note 1:

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

— _end note_]

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

23.3.4.10 Concept output_­iterator [iterator.concept.output]

The output_­iterator concept defines requirements for a type that can be used to write values (from the requirement forindirectly_­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); };

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 output_­iterator<I, T> only if*i++ = E; has effects equivalent to:*i = E;++i;

Recommended practice: The implementation of an algorithm on output iterators should never attempt to pass through the same iterator twice; such an algorithm should be a single-pass algorithm.

23.3.4.11 Concept forward_­iterator [iterator.concept.forward]

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

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.

[Note 1:

Value-initialized iterators behave as if they refer past the end of the same empty sequence.

— _end note_]

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

[Note 2:

The requirement thata == bimplies++a == ++band the removal of the restrictions on the number of assignments through a mutable iterator (which applies to output iterators) allow the use of multi-pass one-directional algorithms with forward iterators.

— _end note_]

23.3.4.12 Concept bidirectional_­iterator [iterator.concept.bidir]

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

A bidirectional iterator r is decrementable if and only if there exists some q such that++q == r.

Decrementable iterators r shall be in the domain of the expressions--r and r--.

Let a and b be equal objects of type 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, thenbool(--(++a) == b).

23.3.4.13 Concept random_­access_­iterator [iterator.concept.random.access]

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 Isuch that b is reachable from aafter 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

• addressof(a += n) is equal to addressof(a).
• (a + n) is equal to (a += n).
• For any two positive valuesx and y of type D, if (a + D(x + y)) is valid, then(a + D(x + y)) is equal to ((a + x) + y).
• (a + D(0)) is equal to a.
• If (a + D(n - 1)) is valid, then(a + n) is equal to [](I c){ return ++c; }(a + D(n - 1)).
• (b += D(-n)) is equal to a.
• addressof(b -= n) is equal to addressof(b).
• (b - n) is equal to (b -= n).
• If b is dereferenceable, thena[n] is valid and is equal to *b.

23.3.4.14 Concept contiguous_­iterator [iterator.concept.contiguous]

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 andc be a non-dereferenceable iterator of type Isuch that b is reachable from a andc 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), and
• to_­address(c) == to_­address(a) + D(c - a).

23.3.5 C++17 iterator requirements [iterator.cpp17]

23.3.5.1 General [iterator.cpp17.general]

In the following sections,aandbdenote values of typeX or const X,difference_­type and reference refer to the types iterator_­traits<X>​::​difference_­type anditerator_­traits<X>​::​reference, respectively,ndenotes a value ofdifference_­type,u,tmp, andmdenote identifiers,rdenotes a value ofX&,tdenotes a value of value typeT,odenotes a value of some type that is writable to the output iterator.

[Note 1:

For an iterator type X there must be an instantiation of iterator_­traits<X> ([iterator.traits]).

— _end note_]

23.3.5.2 Cpp17Iterator [iterator.iterators]

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, and_Cpp17Destructible_ requirements ([utility.arg.requirements]) and lvalues of type X are swappable ([swappable.requirements]), and
• iterator_­traits<X>​::​difference_­type is a signed integer type or void, and
• the expressions in Table 84 are valid and have the indicated semantics.

Table 84: Cpp17Iterator requirements [tab:iterator]

23.3.5.3 Input iterators [input.iterators]

A class or pointer typeXmeets the requirements of an input iterator for the value typeTifX meets the Cpp17Iterator ([iterator.iterators]) and_Cpp17EqualityComparable_ (Table 25) requirements and the expressions in Table 85 are valid and have the indicated semantics.

In Table 85, the termthe 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.

These requirements can be inferred from the uses that algorithm makes of == and !=.

[Example 1:

The call find(a,b,x)is defined only if the value of ahas the property _p_defined as follows:b has property _p_and a value ihas property p_if (*i==x) or if (*i!=xand++ihas property_p).

— _end example_]

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

Recommended practice: The implementation of an algorithm on input iterators should never attempt to pass through the same iterator twice; such an algorithm should be a single pass algorithm.

[Note 1:

For input iterators, a == b does not imply ++a == ++b.

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

Value type T is not required to be a Cpp17CopyAssignable type (Table 31).

Such an algorithm can be used with istreams as the source of the input data through theistream_­iteratorclass template.

— _end note_]

23.3.5.4 Output iterators [output.iterators]

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

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

Recommended practice: The implementation of an algorithm on output iterators should never attempt to pass through the same iterator twice; such an algorithm should be a single-pass algorithm.

[Note 1:

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.

Equality and inequality might not be defined.

— _end note_]

23.3.5.5 Forward iterators [forward.iterators]

A class or pointer typeXmeets the requirements of a forward iterator 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 87are valid and have the indicated semantics, and
• objects of type X offer the multi-pass guarantee, described below.

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 1:

Value-initialized iterators behave as if they refer past the end of the same empty sequence.

— _end note_]

Two dereferenceable iterators a and b of type X offer themulti-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:

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

— _end note_]

Table 87: Cpp17ForwardIterator requirements (in addition to Cpp17InputIterator) [tab:forwarditerator]

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

If a and b are both dereferenceable, then a == bif and only if*a and *b are bound to the same object.

23.3.5.6 Bidirectional iterators [bidirectional.iterators]

A class or pointer typeXmeets the requirements of a bidirectional iterator if, in addition to meeting the Cpp17ForwardIterator requirements, the following expressions are valid as shown in Table 88.

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

[Note 1:

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

— _end note_]

23.3.5.7 Random access iterators [random.access.iterators]

A class or pointer typeXmeets the requirements of a random access iterator if, in addition to meeting the Cpp17BidirectionalIterator requirements, the following expressions are valid as shown in Table 89.

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

23.3.6 Indirect callable requirements [indirectcallable]

23.3.6.2 Indirect callables [indirectcallable.indirectinvocable]

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&, iter_value_t<I>&> && invocable<F&, iter_reference_t<I>> && invocable<F&, iter_common_reference_t<I>> && common_reference_with< invoke_result_t<F&, iter_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&, iter_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&, iter_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&, iter_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&, iter_value_t<I1>&, iter_value_t<I2>&> && predicate<F&, iter_value_t<I1>&, iter_reference_t<I2>> && predicate<F&, iter_reference_t<I1>, iter_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&, iter_value_t<I1>&, iter_value_t<I2>&> && equivalence_­relation<F&, iter_value_t<I1>&, iter_reference_t<I2>> && equivalence_­relation<F&, iter_reference_t<I1>, iter_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&, iter_value_t<I1>&, iter_value_t<I2>&> && strict_­weak_­order<F&, iter_value_t<I1>&, iter_reference_t<I2>> && strict_­weak_­order<F&, iter_reference_t<I1>, iter_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>>;}

23.3.6.3 Class template projected [projected]

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

It combines a indirectly_­readable type I and a callable object type Proj into a new indirectly_­readable type whose reference type is the result of applyingProj to the iter_­reference_­t of I.

namespace std { template<indirectly_­readable I, indirectly_­regular_­unary_­invocable<I> Proj> struct projected { using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>; indirect_result_t<Proj&, I> operator*() const; };template<weakly_­incrementable I, class Proj> struct incrementable_traits<projected<I, Proj>> { using difference_type = iter_difference_t<I>;};}

23.3.7 Common algorithm requirements [alg.req]

23.3.7.1 General [alg.req.general]

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 betweenindirectly_­readable and indirectly_­writable types:indirectly_­movable,indirectly_­copyable, andindirectly_­swappable.

There are three relational concepts for rearrangements:permutable,mergeable, andsortable.

There is one relational concept for comparing values from different sequences:indirectly_­comparable.

[Note 1:

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

— _end note_]

23.3.7.2 Concept indirectly_­movable [alg.req.ind.move]

The indirectly_­movable concept specifies the relationship between a indirectly_­readable type and a 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 augmentsindirectly_­movable with additional requirements enabling the transfer to be performed through an intermediate object of theindirectly_­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>>;

Let i be a dereferenceable value of type In.

In and Out model indirectly_­movable_­storable<In, Out>only if after the initialization of the object obj initer_value_t<In> obj(ranges::iter_move(i)); obj is equal to the value previously denoted by *i.

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

23.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]

The indirectly_­copyable concept specifies the relationship between a indirectly_­readable type and a 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 augmentsindirectly_­copyable with additional requirements enabling the transfer to be performed through an intermediate object of theindirectly_­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>>;

Let i be a dereferenceable value of type In.

In and Out model indirectly_­copyable_­storable<In, Out>only if after the initialization of the object obj initer_value_t<In> obj(*i); obj is equal to the value previously denoted by *i.

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

23.3.7.4 Concept indirectly_­swappable [alg.req.ind.swap]

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

23.3.7.5 Concept indirectly_­comparable [alg.req.ind.cmp]

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

23.3.7.6 Concept permutable [alg.req.permutable]

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

23.3.7.7 Concept mergeable [alg.req.mergeable]

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 = 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>>;

23.3.7.8 Concept sortable [alg.req.sortable]

The sortable concept specifies the common requirements of algorithms that permute sequences into ordered sequences (e.g., sort).

template<class I, class R = ranges::less, class P = identity> concept sortable = permutable<I> && indirect_­strict_­weak_­order<R, projected<I, P>>;