[iterators] (original) (raw)

24.1 General [iterators.general]

The following subclauses describe iterator requirements, and components for iterator primitives, predefined iterators, and stream iterators, as summarized in Table 74 .

24.3 Iterator requirements [iterator.requirements]

24.3.1 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 arewritable 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 75 .

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

🔗Contiguous	→ Random Access	→ Bidirectional	→ Forward	→ Input
🔗	→ Output

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

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.

For an iterator i of a type that models contiguous_iterator ([iterator.concept.contiguous]), library functions are permitted to replace [i, s) with [to_address(i), to_address(i + ranges::distance(i, s))), and to replace with [to_address(i), to_address(i + n)).

[Note 3:

This means a program cannot rely on any side effects of dereferencing a contiguous iterator i, because library functions might operate on pointers obtained by to_address(i)instead of operating on i.

Similarly, a program cannot rely on any side effects of individual increments on a contiguous iterator i, because library functions might advance i only once.

— _end note_]

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

An invalid iteratoris an iterator that may be singular.200

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

[Note 4:

For example, the types “pointer to int” andreverse_iterator<int*> meet the constexpr iterator requirements.

— _end note_]

24.3.2 Associated types [iterator.assoc.types]

24.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 { };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.

The type iter_difference_t 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.

24.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 T> concept has-member-value-type = requires { typename T::value_type; }; template<class T> concept has-member-element-type = requires { typename T::element_type; }; 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 struct indirectly_readable_traits { using value_type = remove_cv_t<remove_extent_t>;};template<class I> struct indirectly_readable_traits<const I> : indirectly_readable_traits { };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;

Let be remove_cvref_t.

The type iter_value_t 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_]

24.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::iterator_categorybe defined as the iterator's iterator category.

In addition, the typesiterator_traits::pointer iterator_traits::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::pointershall be voidfor an iterator of class type Ithat does not support operator->.

Additionally, in the case of an output iterator, the typesiterator_traits::value_type iterator_traits::difference_type iterator_traits::referencemay 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;template<class I> concept cpp17-input-iterator = cpp17-iterator && equality_comparable && requires(I i) { typename incrementable_traits::difference_type;typename indirectly_readable_traits::value_type;typename common_reference_t<iter_reference_t&&,typename indirectly_readable_traits::value_type&>;typename common_reference_t<decltype(*i++)&&,typename indirectly_readable_traits::value_type&>;requires signed_integral<typename incrementable_traits::difference_type>;};template<class I> concept cpp17-forward-iterator = cpp17-input-iterator && constructible_from && is_reference_v<iter_reference_t> && same_as<remove_cvref_t<iter_reference_t>,typename indirectly_readable_traits::value_type> && requires(I i) { { i++ } -> convertible_to<const I&>;{ *i++ } -> same_as<iter_reference_t>;};template<class I> concept cpp17-bidirectional-iterator = cpp17-forward-iterator && requires(I i) { { --i } -> same_as<I&>;{ i-- } -> convertible_to<const I&>;{ *i-- } -> same_as<iter_reference_t>;};template<class I> concept cpp17-random-access-iterator = cpp17-bidirectional-iterator && totally_ordered && requires(I i, typename incrementable_traits::difference_type n) { { i += n } -> same_as<I&>;{ i -= n } -> same_as<I&>;{ i + n } -> same_as;{ n + i } -> same_as;{ i - n } -> same_as;{ i - i } -> same_as<decltype(n)>;{ i[n] } -> convertible_to<iter_reference_t>;};

The members of a specialization iterator_traits 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_traitshas 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::pointer names that type; otherwise, it names void.
Otherwise, if I satisfies the exposition-only conceptcpp17-input-iterator,iterator_traits has the following publicly accessible members:using iterator_category = see below;using value_type = typename indirectly_readable_traits::value_type;using difference_type = typename incrementable_traits::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.
- 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_traitshas 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::difference_type is valid and denotes a type, then difference_type names that type; otherwise, it names void.
Otherwise, iterator_traitshas 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:

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

— _end example_]

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

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_]

24.3.3 Customization point objects [iterator.cust]

24.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, where the meaning of iter_move is established as-if by performing argument-dependent lookup only ([basic.lookup.argdep]).
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.

24.3.3.2 ranges::iter_swap [iterator.cust.swap]

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

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.
[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 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 2:
This case can result in substitution failure when ranges::iter_swap(E1, E2)appears in the immediate context of a template instantiation.
— _end note_]

24.3.4 Iterator concepts [iterator.concepts]

24.3.4.1 General [iterator.concepts.general]

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

Otherwise, ITER_TRAITS(I) denotesiterator_traits.

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 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::iterator_category denotes input_iterator_tag, and ITER_CONCEPT(I) denotes random_access_iterator_tag.

— _end example_]

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

24.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_]

24.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> constexpr bool is-integer-like = see below; template<class T> constexpr bool is-signed-integer-like = see below; template<class I> concept weakly_incrementable = movable && requires(I i) { typename iter_difference_t;requires is-signed-integer-like<iter_difference_t>;{ ++i } -> same_as<I&>; i++; };

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

[Note 1:

An integer-class type is not necessarily a class type.

— _end note_]

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, or0 to (inclusive) for some integer N, in which case it is an unsigned-integer-class type.

In both cases, N is called the width of the 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-likeif it models integral or if it is an integer-class type.

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

An integer-like type I is unsigned-integer-likeif it models unsigned_integral 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:

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

— _end note_]

For every integral type J, let B(J) be the same type as J.

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 I2such 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++ and a-- shall be prvalues of type Iwhose values are equal to that of a prior to the evaluation of the expressions.
The expression a++ shall modify the value of aby adding 1 to it.
The expression a-- shall modify the value of aby subtracting 1 from it.
The expressions ++a, --a, and &a shall be expression-equivalent toa += 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.
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 assignment operator @=for which x @= y is well-formed,a @= b shall also be well-formed and shall have the same effects as x @= y, except that the value that would be stored into xis stored into a.
The expression a @= b shall be an lvalue referring to a.
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 asx @ 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 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 is specialized such that each static data member mhas the same value as numeric_limits<B(I)>::m, and each static member function freturns 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.

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

is-signed-integer-like 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 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 implementation 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 3:

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_]

24.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 && weakly_incrementable && requires(I i) { { i++ } -> same_as;};

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_]

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

[Note 1:

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

— _end note_]

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

24.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_forthat 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 "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]") = [sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<S, I> && !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t> && 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 - s } -> [same_as](concept.same#concept:same%5Fas "18.4.2 Concept same_as [concept.same]")<iter_difference_t>;};

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, then s - i is well-defined and equals N.
If is representable by iter_difference_t, then i - s is well-defined and equals .

template<class S, class I> 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_]

24.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 && indirectly_readable && requires { typename ITER_CONCEPT(I); } && derived_from<_ITER_CONCEPT_(I), input_iterator_tag>;

24.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 && 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.

24.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 && derived_from<_ITER_CONCEPT_(I), forward_iterator_tag> && incrementable && 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_]

24.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 && derived_from<_ITER_CONCEPT_(I), bidirectional_iterator_tag> && requires(I i) { { --i } -> same_as<I&>;{ i-- } -> same_as;};

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

24.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 && derived_from<_ITER_CONCEPT_(I), random_access_iterator_tag> && totally_ordered && sized_sentinel_for<I, I> && requires(I i, const I j, const iter_difference_t n) { { i += n } -> same_as<I&>;{ j + n } -> same_as;{ n + j } -> same_as;{ i -= n } -> same_as<I&>;{ j - n } -> same_as;{ j[n] } -> same_as<iter_reference_t>;};

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

24.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 && derived_from<_ITER_CONCEPT_(I), contiguous_iterator_tag> && is_lvalue_reference_v<iter_reference_t> && same_as<iter_value_t, remove_cvref_t<iter_reference_t>> && requires(const I& i) { { to_address(i) } -> same_as<add_pointer_t<iter_reference_t>>;};

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.

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),
to_address(I{}) is well-defined,
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).

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

24.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_]

24.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, 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 76 are valid and have the indicated semantics.

Table 76 — Cpp17Iterator requirements [tab:iterator]

🔗Expression	Return type	Operational
🔗	semantics	pre-/post-condition
🔗*r	unspecified	Preconditions: r is dereferenceable.
🔗++r	X&

24.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 28) requirements and the expressions in Table 77 are valid and have the indicated semantics.

In Table 77, 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 77 — 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)	Preconditions: (a, b) is in the domain of ==.
🔗*a	reference, convertible to T	Preconditions: a is dereferenceable. The expression(void)a, a is equivalent to a. If a == b and (a, b) is in the domain of == then a is equivalent to *b.
🔗a->m	(*a).m	Preconditions: a is dereferenceable.
🔗++r	X&	Preconditions: r is dereferenceable. Postconditions: r is dereferenceable or r is past-the-end;any copies of the previous value of r are no longer required to be dereferenceable nor to be in the domain of ==.
🔗(void)r++	equivalent to (void)++r
🔗*r++	convertible to T	{ T tmp = *r;++r;return tmp; }

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

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

— _end note_]

24.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 78are valid and have the indicated semantics.

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

🔗Expression	Return type	Operational	Assertion/note
🔗	semantics	pre-/post-condition
🔗*r = o	result is not used	Remarks: After this operation r is not required to be dereferenceable. Postconditions: r is incrementable.
🔗++r	X&	addressof(r) == addressof(++r). Remarks: After this operation r is not required to be dereferenceable. Postconditions: r is incrementable.
🔗r++	convertible to const X&	{ X tmp = r; ++r; return tmp; }	Remarks: After this operation r is not required to be dereferenceable. Postconditions: r is incrementable.
🔗*r++ = o	result is not used	Remarks: After this operation r is not required to be dereferenceable. Postconditions: r is incrementable.

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 are not necessarily defined.

— _end note_]

24.3.5.5 Forward iterators [forward.iterators]

A class or pointer typeXmeets 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 79are 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 79 — Cpp17ForwardIterator requirements (in addition to Cpp17InputIterator) [tab:forwarditerator]

🔗Expression	Return type	Operational
🔗	semantics	pre-/post-condition
🔗r++	convertible to const X&	{ X tmp = r; ++r; return tmp; }
🔗*r++	reference

If a and b are equal, then either a and 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.

24.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 80 .

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

🔗Expression	Return type	Operational
🔗	semantics	pre-/post-condition
🔗--r	X&	Preconditions: there exists s such that r == ++s. Postconditions: r is dereferenceable. --(++r) == r. --r == --s implies r == s. addressof(r) == addressof(--r).
🔗r--	convertible to const X&	{ X tmp = r; --r; return tmp; }
🔗*r--	reference

[Note 1:

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

— _end note_]

24.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 81 .

Table 81 — 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 + nn + a	X	{ X tmp = a; return tmp += n; }	a + n == n + a.
🔗r -= n	X&	return r += -n;	Preconditions: the absolute value of n is in the range of representable values of difference_type.
🔗a - n	X	{ X tmp = a; return tmp -= n; }
🔗b - a	difference_type	return n;	Preconditions: there exists a value n of type difference_type such that a + n == b. b == a + (b - a).
🔗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	> is a total ordering relation opposite to <.
🔗a >= b	decltype(a >= b) models boolean-testable	!(a < b)
🔗a <= b	decltype(a <= b) models boolean-testable	!(a > b)

24.3.6 Indirect callable requirements [indirectcallable]

24.3.6.2 Indirect callable traits [indirectcallable.traits]

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

For the exposition-only alias template indirect-value-t,indirect-value-t<T> denotes

invoke_result_t<Proj&, _indirect-value-t_>if T names projected<I, Proj>, and
iter_value_t<T>& otherwise.

24.3.6.3 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 && copy_constructible<F> && invocable<F&, _indirect-value-t_> && invocable<F&, iter_reference_t> && common_reference_with< invoke_result_t<F&, _indirect-value-t_>, invoke_result_t<F&, iter_reference_t>>;template<class F, class I> concept indirectly_regular_unary_invocable = indirectly_readable && copy_constructible<F> && regular_invocable<F&, _indirect-value-t_> && regular_invocable<F&, iter_reference_t> && common_reference_with< invoke_result_t<F&, _indirect-value-t_>, invoke_result_t<F&, iter_reference_t>>;template<class F, class I> concept indirect_unary_predicate = indirectly_readable && copy_constructible<F> && predicate<F&, _indirect-value-t_> && predicate<F&, iter_reference_t>;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>>;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>>;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>>;}

24.3.6.4 Class template projected [projected]

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 applyingProj to the iter_reference_t of I.

namespace std { template<class I, class Proj> struct projected-impl { struct type { using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;using difference_type = iter_difference_t; indirect_result_t<Proj&, I> operator*() const; };};template<indirectly_readable I, indirectly_regular_unary_invocable Proj> using projected = projected-impl<I, Proj>::type;}

24.3.7 Common algorithm requirements [alg.req]

24.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_]

24.3.7.2 Concept indirectly_movable [alg.req.ind.move]

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

24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]

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

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

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

24.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 && indirectly_movable_storable<I, I> && indirectly_swappable<I, I>;

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

24.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 && indirect_strict_weak_order<R, projected<I, P>>;

24.4 Iterator primitives [iterator.primitives]

24.4.3 Iterator operations [iterator.operations]

Since only random access iterators provide+and-operators, the library provides two function templatesadvanceanddistance.

These function templates use+and-for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use++to provide linear time implementations.

template<class InputIterator, class Distance> constexpr void advance(InputIterator& i, Distance n);

Preconditions: nis negative only for bidirectional iterators.

Effects: Increments i by n if n is non-negative, and decrements i by -n otherwise.

template<class InputIterator> constexpr typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);

Preconditions: last is reachable from first, orInputIterator meets the Cpp17RandomAccessIterator requirements andfirst is reachable from last.

Effects: If InputIterator meets the Cpp17RandomAccessIterator requirements, returns (last - first); otherwise, incrementsfirst until last is reached and returns the number of increments.

template<class InputIterator> constexpr InputIterator next(InputIterator x,typename iterator_traits<InputIterator>::difference_type n = 1);

Effects: Equivalent to: advance(x, n); return x;

template<class BidirectionalIterator> constexpr BidirectionalIterator prev(BidirectionalIterator x,typename iterator_traits<BidirectionalIterator>::difference_type n = 1);

Effects: Equivalent to: advance(x, -n); return x;

24.4.4 Range iterator operations [range.iter.ops]

24.4.4.1 General [range.iter.ops.general]

The library includes the function templatesranges::advance, ranges::distance,ranges::next, and ranges::prevto manipulate iterators.

These operations adapt to the set of operators provided by each iterator category to provide the most efficient implementation possible for a concrete iterator type.

[Example 1:

ranges::advance uses the + operator to move arandom_access_iterator forward n steps in constant time.

For an iterator type that does not model random_access_iterator,ranges::advance instead performs n individual increments with the ++ operator.

— _end example_]

24.4.4.2 ranges::advance [range.iter.op.advance]

template<[input_or_output_iterator](#concept:input%5For%5Foutput%5Fiterator "24.3.4.6 Concept input_or_output_iterator [iterator.concept.iterator]") I> constexpr void ranges::advance(I& i, iter_difference_t n);

Preconditions: If I does not model bidirectional_iterator,n is not negative.

Effects:

If I models random_access_iterator, equivalent to i += n.
Otherwise, if n is non-negative, incrementsi by n.
Otherwise, decrements i by -n.

template<[input_or_output_iterator](#concept:input%5For%5Foutput%5Fiterator "24.3.4.6 Concept input_or_output_iterator [iterator.concept.iterator]") I, [sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]") S> constexpr void ranges::advance(I& i, S bound);

Preconditions: Either assignable_from<I&, S> || sized_sentinel_for<S, I> is modeled, or [i, bound) denotes a range.

Effects:

If I and S model assignable_from<I&, S>, equivalent to i = std::move(bound).
Otherwise, if S and I model sized_sentinel_for<S, I>, equivalent to ranges::advance(i, bound - i).
Otherwise, while bool(i != bound) is true, increments i.

Preconditions: If n > 0, [i, bound) denotes a range.

If n == 0, [i, bound) or [bound, i) denotes a range.

If n < 0, [bound, i) denotes a range,I models bidirectional_iterator, andI and S model same_as<I, S>.

Effects:

If S and I model sized_sentinel_for<S, I>:
- If |n| ≥ |bound - i|, equivalent to ranges::advance(i, bound).
- Otherwise, equivalent to ranges::advance(i, n).
Otherwise,
- if n is non-negative, while bool(i != bound) is true, increments i but at most n times.
- Otherwise, while bool(i != bound) is true, decrements i but at most -n times.

Returns: n - M, where M is the difference between the ending and starting positions of i.

24.4.4.3 ranges::distance [range.iter.op.distance]

template<class I, [sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]") S> requires (![sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<S, I>) constexpr iter_difference_t ranges::distance(I first, S last);

Preconditions: [first, last) denotes a range.

Effects: Increments first until last is reached and returns the number of increments.

template<class I, [sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<decay_t> S> constexpr iter_difference_t<decay_t> ranges::distance(I&& first, S last);

Effects: Equivalent to: return last - static_cast<const decay_t&>(first);

template<[range](range.range#concept:range "25.4.2 Ranges [range.range]") R> constexpr range_difference_t<R> ranges::distance(R&& r);

Effects: If R models sized_range, equivalent to:return static_cast<range_difference_t<R>>(ranges::size(r));

Otherwise, equivalent to:return ranges::distance(ranges::begin(r), ranges::end(r));

24.4.4.4 ranges::next [range.iter.op.next]

template<[input_or_output_iterator](#concept:input%5For%5Foutput%5Fiterator "24.3.4.6 Concept input_or_output_iterator [iterator.concept.iterator]") I> constexpr I ranges::next(I x);

Effects: Equivalent to: ++x; return x;

Effects: Equivalent to: ranges::advance(x, n); return x;

Effects: Equivalent to: ranges::advance(x, bound); return x;

Effects: Equivalent to: ranges::advance(x, n, bound); return x;

24.4.4.5 ranges::prev [range.iter.op.prev]

template<[bidirectional_iterator](#concept:bidirectional%5Fiterator "24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]") I> constexpr I ranges::prev(I x);

Effects: Equivalent to: --x; return x;

template<[bidirectional_iterator](#concept:bidirectional%5Fiterator "24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]") I> constexpr I ranges::prev(I x, iter_difference_t n);

Effects: Equivalent to: ranges::advance(x, -n); return x;

template<[bidirectional_iterator](#concept:bidirectional%5Fiterator "24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]") I> constexpr I ranges::prev(I x, iter_difference_t n, I bound);

Effects: Equivalent to: ranges::advance(x, -n, bound); return x;

24.5 Iterator adaptors [predef.iterators]

24.5.1 Reverse iterators [reverse.iterators]

24.5.1.1 General [reverse.iterators.general]

Class template reverse_iterator is an iterator adaptor that iterates from the end of the sequence defined by its underlying iterator to the beginning of that sequence.

24.5.1.2 Class template reverse_iterator [reverse.iterator]

namespace std { template<class Iterator> class reverse_iterator { public: using iterator_type = Iterator;using iterator_concept = see below;using iterator_category = see below;using value_type = iter_value_t<Iterator>;using difference_type = iter_difference_t<Iterator>;using pointer = typename iterator_traits<Iterator>::pointer;using reference = iter_reference_t<Iterator>;constexpr reverse_iterator();constexpr explicit reverse_iterator(Iterator x);template<class U> constexpr reverse_iterator(const reverse_iterator& u);template<class U> constexpr reverse_iterator& operator=(const reverse_iterator& u);constexpr Iterator base() const;constexpr reference operator*() const;constexpr pointer operator->() const requires see below;constexpr reverse_iterator& operator++();constexpr reverse_iterator operator++(int);constexpr reverse_iterator& operator--();constexpr reverse_iterator operator--(int);constexpr reverse_iterator operator+ (difference_type n) const;constexpr reverse_iterator& operator+=(difference_type n);constexpr reverse_iterator operator- (difference_type n) const;constexpr reverse_iterator& operator-=(difference_type n);constexpr unspecified operator[](difference_type n) const;friend constexpr iter_rvalue_reference_t<Iterator> iter_move(const reverse_iterator& i) noexcept(see below);template<indirectly_swappable<Iterator> Iterator2> friend constexpr void iter_swap(const reverse_iterator& x,const reverse_iterator<Iterator2>& y) noexcept(see below);protected: Iterator current;};}

The member typedef-name iterator_concept denotes

random_access_iterator_tag if Iterator modelsrandom_access_iterator, and
bidirectional_iterator_tag otherwise.

The member typedef-name iterator_category denotes

random_access_iterator_tag if the typeiterator_traits<Iterator>::iterator_category modelsderived_from<random_access_iterator_tag>, and
iterator_traits<Iterator>::iterator_category otherwise.

24.5.1.3 Requirements [reverse.iter.requirements]

The template parameterIteratorshall either meet the requirements of a_Cpp17BidirectionalIterator_ ([bidirectional.iterators]) or modelbidirectional_iterator ([iterator.concept.bidir]).

Additionally,Iteratorshall either meet the requirements of a_Cpp17RandomAccessIterator_ ([random.access.iterators]) or modelrandom_access_iterator ([iterator.concept.random.access]) if the definitions of any of the members

operator+,operator-,operator+=,operator-= ([reverse.iter.nav]), or
operator[] ([reverse.iter.elem]),

or the non-member operators ([reverse.iter.cmp])

operator<,operator>,operator<=,operator>=,operator-, oroperator+ ([reverse.iter.nonmember])

are instantiated ([temp.inst]).

24.5.1.4 Construction and assignment [reverse.iter.cons]

constexpr reverse_iterator();

Effects: Value-initializescurrent.

constexpr explicit reverse_iterator(Iterator x);

Effects: Initializescurrentwith x.

template<class U> constexpr reverse_iterator(const reverse_iterator& u);

Constraints: is_same_v<U, Iterator> is false andconst U& models convertible_to<Iterator>.

Effects: Initializescurrentwithu.current.

template<class U> constexpr reverse_iterator& operator=(const reverse_iterator& u);

Effects: Assigns u.current to current.

24.5.1.6 Element access [reverse.iter.elem]

constexpr reference operator*() const;

Effects: As if by:Iterator tmp = current;return *--tmp;

constexpr pointer operator->() const requires (is_pointer_v<Iterator> || requires(const Iterator i) { i.operator->(); });

Effects:

If Iterator is a pointer type, equivalent to:return prev(current);
Otherwise, equivalent to:return prev(current).operator->();

constexpr _unspecified_ operator[](difference_type n) const;

Returns: current[-n - 1].

constexpr reverse_iterator operator+(difference_type n) const;

Returns: reverse_iterator(current - n).

constexpr reverse_iterator operator-(difference_type n) const;

Returns: reverse_iterator(current + n).

constexpr reverse_iterator& operator++();

Effects: As if by: --current;

constexpr reverse_iterator operator++(int);

Effects: As if by:reverse_iterator tmp = *this;--current;return tmp;

constexpr reverse_iterator& operator--();

Effects: As if by ++current.

constexpr reverse_iterator operator--(int);

Effects: As if by:reverse_iterator tmp = *this;++current;return tmp;

constexpr reverse_iterator& operator+=(difference_type n);

Effects: As if by: current -= n;

constexpr reverse_iterator& operator-=(difference_type n);

Effects: As if by: current += n;

24.5.1.8 Comparisons [reverse.iter.cmp]

template<class Iterator1, class Iterator2> constexpr bool operator==( const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y);

Constraints: x.base() == y.base() is well-formed and convertible to bool.

Returns: x.base() == y.base().

template<class Iterator1, class Iterator2> constexpr bool operator!=( const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y);

Constraints: x.base() != y.base() is well-formed and convertible to bool.

Returns: x.base() != y.base().

template<class Iterator1, class Iterator2> constexpr bool operator<( const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y);

Constraints: x.base() > y.base() is well-formed and convertible to bool.

Returns: x.base() > y.base().

template<class Iterator1, class Iterator2> constexpr bool operator>( const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y);

Constraints: x.base() < y.base() is well-formed and convertible to bool.

Returns: x.base() < y.base().

template<class Iterator1, class Iterator2> constexpr bool operator<=( const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y);

Constraints: x.base() >= y.base() is well-formed and convertible to bool.

Returns: x.base() >= y.base().

template<class Iterator1, class Iterator2> constexpr bool operator>=( const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y);

Constraints: x.base() <= y.base() is well-formed and convertible to bool.

Returns: x.base() <= y.base().

template<class Iterator1, [three_way_comparable_with](cmp.concept#concept:three%5Fway%5Fcomparable%5Fwith "17.12.4 Concept three_way_comparable [cmp.concept]")<Iterator1> Iterator2> constexpr compare_three_way_result_t<Iterator1, Iterator2> operator<=>(const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y);

Returns: y.base() <=> x.base().

[Note 1:

The argument order in the Returns: element is reversed because this is a reverse iterator.

— _end note_]

24.5.1.9 Non-member functions [reverse.iter.nonmember]

template<class Iterator1, class Iterator2> constexpr auto operator-( const reverse_iterator<Iterator1>& x,const reverse_iterator<Iterator2>& y) -> decltype(y.base() - x.base());

Returns: y.base() - x.base().

template<class Iterator> constexpr reverse_iterator<Iterator> operator+( iter_difference_t<Iterator> n,const reverse_iterator<Iterator>& x);

Returns: reverse_iterator<Iterator>(x.base() - n).

friend constexpr iter_rvalue_reference_t<Iterator> iter_move(const reverse_iterator& i) noexcept(_see below_);

Effects: Equivalent to:auto tmp = i.base();return ranges::iter_move(--tmp);

Remarks: The exception specification is equivalent to:is_nothrow_copy_constructible_v<Iterator> && noexcept(ranges::iter_move(--declval<Iterator&>()))

template<[indirectly_swappable](#concept:indirectly%5Fswappable "24.3.7.4 Concept indirectly_swappable [alg.req.ind.swap]")<Iterator> Iterator2> friend constexpr void iter_swap(const reverse_iterator& x,const reverse_iterator<Iterator2>& y) noexcept(_see below_);

Effects: Equivalent to:auto xtmp = x.base();auto ytmp = y.base(); ranges::iter_swap(--xtmp, --ytmp);

Remarks: The exception specification is equivalent to:is_nothrow_copy_constructible_v<Iterator> &&is_nothrow_copy_constructible_v<Iterator2> && noexcept(ranges::iter_swap(--declval<Iterator&>(), --declval<Iterator2&>()))

template<class Iterator> constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i);

Returns: reverse_iterator<Iterator>(i).

24.5.2 Insert iterators [insert.iterators]

24.5.2.1 General [insert.iterators.general]

To make it possible to deal with insertion in the same way as writing into an array, a special kind of iterator adaptors, calledinsert iterators, are provided in the library.

With regular iterator classes,while (first != last) *result++ = *first++;causes a range [first, last) to be copied into a range starting with result.

The same code withresultbeing an insert iterator will insert corresponding elements into the container.

This device allows all of the copying algorithms in the library to work in theinsert modeinstead of the regular overwrite mode.

An insert iterator is constructed from a container and possibly one of its iterators pointing to where insertion takes place if it is neither at the beginning nor at the end of the container.

Insert iterators meet the requirements of output iterators.

operator*returns the insert iterator itself.

The assignmentoperator=(const T& x)is defined on insert iterators to allow writing into them, it insertsxright before where the insert iterator is pointing.

In other words, an insert iterator is like a cursor pointing into the container where the insertion takes place.

back_insert_iteratorinserts elements at the end of a container,front_insert_iteratorinserts elements at the beginning of a container, andinsert_iteratorinserts elements where the iterator points to in a container.

back_inserter,front_inserter, andinserterare three functions making the insert iterators out of a container.

24.5.2.2 Class template back_insert_iterator [back.insert.iterator]

24.5.2.2.1 General [back.insert.iter.general]

namespace std { template<class Container> class back_insert_iterator { protected: Container* container;public: using iterator_category = output_iterator_tag;using value_type = void;using difference_type = ptrdiff_t;using pointer = void;using reference = void;using container_type = Container;constexpr explicit back_insert_iterator(Container& x);constexpr back_insert_iterator& operator=(const typename Container::value_type& value);constexpr back_insert_iterator& operator=(typename Container::value_type&& value);constexpr back_insert_iterator& operator*();constexpr back_insert_iterator& operator++();constexpr back_insert_iterator operator++(int);};}

24.5.2.2.2 Operations [back.insert.iter.ops]

constexpr explicit back_insert_iterator(Container& x);

Effects: Initializescontainerwith addressof(x).

constexpr back_insert_iterator& operator=(const typename Container::value_type& value);

Effects: As if by: container->push_back(value);

constexpr back_insert_iterator& operator=(typename Container::value_type&& value);

Effects: As if by: container->push_back(std::move(value));

constexpr back_insert_iterator& operator*();

constexpr back_insert_iterator& operator++();constexpr back_insert_iterator operator++(int);

24.5.2.2.3 back_inserter [back.inserter]

template<class Container> constexpr back_insert_iterator<Container> back_inserter(Container& x);

Returns: back_insert_iterator<Container>(x).

24.5.2.3 Class template front_insert_iterator [front.insert.iterator]

24.5.2.3.1 General [front.insert.iter.general]

namespace std { template<class Container> class front_insert_iterator { protected: Container* container;public: using iterator_category = output_iterator_tag;using value_type = void;using difference_type = ptrdiff_t;using pointer = void;using reference = void;using container_type = Container;constexpr explicit front_insert_iterator(Container& x);constexpr front_insert_iterator& operator=(const typename Container::value_type& value);constexpr front_insert_iterator& operator=(typename Container::value_type&& value);constexpr front_insert_iterator& operator*();constexpr front_insert_iterator& operator++();constexpr front_insert_iterator operator++(int);};}

24.5.2.3.2 Operations [front.insert.iter.ops]

constexpr explicit front_insert_iterator(Container& x);

Effects: Initializescontainerwith addressof(x).

constexpr front_insert_iterator& operator=(const typename Container::value_type& value);

Effects: As if by: container->push_front(value);

constexpr front_insert_iterator& operator=(typename Container::value_type&& value);

Effects: As if by: container->push_front(std::move(value));

constexpr front_insert_iterator& operator*();

constexpr front_insert_iterator& operator++();constexpr front_insert_iterator operator++(int);

24.5.2.3.3 front_inserter [front.inserter]

template<class Container> constexpr front_insert_iterator<Container> front_inserter(Container& x);

Returns: front_insert_iterator<Container>(x).

24.5.2.4 Class template insert_iterator [insert.iterator]

24.5.2.4.1 General [insert.iter.general]

namespace std { template<class Container> class insert_iterator { protected: Container* container; ranges::iterator_t<Container> iter;public: using iterator_category = output_iterator_tag;using value_type = void;using difference_type = ptrdiff_t;using pointer = void;using reference = void;using container_type = Container;constexpr insert_iterator(Container& x, ranges::iterator_t<Container> i);constexpr insert_iterator& operator=(const typename Container::value_type& value);constexpr insert_iterator& operator=(typename Container::value_type&& value);constexpr insert_iterator& operator*();constexpr insert_iterator& operator++();constexpr insert_iterator& operator++(int);};}

24.5.2.4.2 Operations [insert.iter.ops]

constexpr insert_iterator(Container& x, ranges::iterator_t<Container> i);

Effects: Initializescontainerwith addressof(x) anditerwith i.

constexpr insert_iterator& operator=(const typename Container::value_type& value);

Effects: As if by:iter = container->insert(iter, value);++iter;

constexpr insert_iterator& operator=(typename Container::value_type&& value);

Effects: As if by:iter = container->insert(iter, std::move(value));++iter;

constexpr insert_iterator& operator*();

constexpr insert_iterator& operator++();constexpr insert_iterator& operator++(int);

24.5.2.4.3 inserter [inserter]

template<class Container> constexpr insert_iterator<Container> inserter(Container& x, ranges::iterator_t<Container> i);

Returns: insert_iterator<Container>(x, i).

24.5.3 Constant iterators and sentinels [const.iterators]

24.5.3.1 General [const.iterators.general]

Class template basic_const_iterator is an iterator adaptor with the same behavior as the underlying iterator except that its indirection operator implicitly converts the value returned by the underlying iterator's indirection operator to a type such that the adapted iterator is a constant iterator ([iterator.requirements]).

Some generic algorithms can be called with constant iterators to avoid mutation.

Specializations of basic_const_iterator are constant iterators.

24.5.3.2 Alias templates [const.iterators.alias]

template<[indirectly_readable](#concept:indirectly%5Freadable "24.3.4.2 Concept indirectly_readable [iterator.concept.readable]") It> using [iter_const_reference_t](#lib:iter%5Fconst%5Freference%5Ft "24.5.3.2 Alias templates [const.iterators.alias]") = common_reference_t<const iter_value_t<It>&&, iter_reference_t<It>>;template<class It> concept [_constant-iterator_](#concept:constant-iterator "24.5.3.2 Alias templates [const.iterators.alias]") = // _exposition only_ [input_iterator](#concept:input%5Fiterator "24.3.4.9 Concept input_iterator [iterator.concept.input]")<It> && [same_as](concept.same#concept:same%5Fas "18.4.2 Concept same_as [concept.same]")<iter_const_reference_t<It>, iter_reference_t<It>>;template<[input_iterator](#concept:input%5Fiterator "24.3.4.9 Concept input_iterator [iterator.concept.input]") I> using [const_iterator](#lib:const%5Fiterator "24.5.3.2 Alias templates [const.iterators.alias]") = _see below_;

Result: If I models constant-iterator, I.

Otherwise, basic_const_iterator.

Result: If S models input_iterator, const_iterator<S>.

Otherwise, S.

24.5.3.3 Class template basic_const_iterator [const.iterators.iterator]

namespace std { template<class I> concept not-a-const-iterator = see below; template<indirectly_readable I> using iter-const-rvalue-reference-t = common_reference_t<const iter_value_t&&, iter_rvalue_reference_t>;template<input_iterator Iterator> class basic_const_iterator { Iterator current_ = Iterator(); using reference = iter_const_reference_t<Iterator>; using rvalue-reference = iter-const-rvalue-reference-t<Iterator>;public: using iterator_concept = see below;using iterator_category = see below; using value_type = iter_value_t<Iterator>;using difference_type = iter_difference_t<Iterator>; basic_const_iterator() requires default_initializable<Iterator> = default;constexpr basic_const_iterator(Iterator current);template<convertible_to<Iterator> U> constexpr basic_const_iterator(basic_const_iterator current);template<different-from<basic_const_iterator> T> requires convertible_to<T, Iterator> constexpr basic_const_iterator(T&& current);constexpr const Iterator& base() const & noexcept;constexpr Iterator base() &&;constexpr reference operator*() const;constexpr const auto* operator->() const requires is_lvalue_reference_v<iter_reference_t<Iterator>> && same_as<remove_cvref_t<iter_reference_t<Iterator>>, value_type>;constexpr basic_const_iterator& operator++();constexpr void operator++(int);constexpr basic_const_iterator operator++(int) requires forward_iterator<Iterator>;constexpr basic_const_iterator& operator--() requires bidirectional_iterator<Iterator>;constexpr basic_const_iterator operator--(int) requires bidirectional_iterator<Iterator>;constexpr basic_const_iterator& operator+=(difference_type n) requires random_access_iterator<Iterator>;constexpr basic_const_iterator& operator-=(difference_type n) requires random_access_iterator<Iterator>;constexpr reference operator[](difference_type n) const requires random_access_iterator<Iterator>;template<sentinel_for<Iterator> S> constexpr bool operator==(const S& s) const;template<not-a-const-iterator CI> requires constant-iterator<CI> && convertible_to<Iterator const&, CI> constexpr operator CI() const &;template<not-a-const-iterator CI> requires constant-iterator<CI> && convertible_to<Iterator, CI> constexpr operator CI() &&;constexpr bool operator<(const basic_const_iterator& y) const requires random_access_iterator<Iterator>;constexpr bool operator>(const basic_const_iterator& y) const requires random_access_iterator<Iterator>;constexpr bool operator<=(const basic_const_iterator& y) const requires random_access_iterator<Iterator>;constexpr bool operator>=(const basic_const_iterator& y) const requires random_access_iterator<Iterator>;constexpr auto operator<=>(const basic_const_iterator& y) const requires random_access_iterator<Iterator> && three_way_comparable<Iterator>;template<different-from<basic_const_iterator> I> constexpr bool operator<(const I& y) const requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;template<different-from<basic_const_iterator> I> constexpr bool operator>(const I& y) const requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;template<different-from<basic_const_iterator> I> constexpr bool operator<=(const I& y) const requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;template<different-from<basic_const_iterator> I> constexpr bool operator>=(const I& y) const requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;template<different-from<basic_const_iterator> I> constexpr auto operator<=>(const I& y) const requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I> && three_way_comparable_with<Iterator, I>;template<not-a-const-iterator I> friend constexpr bool operator<(const I& x, const basic_const_iterator& y) requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;template<not-a-const-iterator I> friend constexpr bool operator>(const I& x, const basic_const_iterator& y) requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;template<not-a-const-iterator I> friend constexpr bool operator<=(const I& x, const basic_const_iterator& y) requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;template<not-a-const-iterator I> friend constexpr bool operator>=(const I& x, const basic_const_iterator& y) requires random_access_iterator<Iterator> && totally_ordered_with<Iterator, I>;friend constexpr basic_const_iterator operator+(const basic_const_iterator& i, difference_type n) requires random_access_iterator<Iterator>;friend constexpr basic_const_iterator operator+(difference_type n,const basic_const_iterator& i) requires random_access_iterator<Iterator>;friend constexpr basic_const_iterator operator-(const basic_const_iterator& i, difference_type n) requires random_access_iterator<Iterator>;template<sized_sentinel_for<Iterator> S> constexpr difference_type operator-(const S& y) const;template<not-a-const-iterator S> requires sized_sentinel_for<S, Iterator> friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);friend constexpr rvalue-reference iter_move(const basic_const_iterator& i) noexcept(noexcept(static_cast<_rvalue-reference_>(ranges::iter_move(i.current_)))) { return static_cast<_rvalue-reference_>(ranges::iter_move(i.current_));} };}

Given some type I, the concept not-a-const-iterator is defined as falseif I is a specialization of basic_const_iterator andtrue otherwise.

24.5.3.4 Member types [const.iterators.types]

basic_const_iterator<Iterator>::iterator_concept is defined as follows:

If Iterator models contiguous_iterator, then iterator_concept denotes contiguous_iterator_tag.
Otherwise, if Iterator models random_access_iterator, then iterator_concept denotes random_access_iterator_tag.
Otherwise, if Iterator models bidirectional_iterator, then iterator_concept denotes bidirectional_iterator_tag.
Otherwise, if Iterator models forward_iterator, then iterator_concept denotes forward_iterator_tag.
Otherwise, iterator_concept denotes input_iterator_tag.

The member typedef-name iterator_category is defined if and only if Iterator models forward_iterator .

In that case,basic_const_iterator<Iterator>::iterator_category denotes the type iterator_traits<Iterator>::iterator_category.

24.5.3.5 Operations [const.iterators.ops]

constexpr basic_const_iterator(Iterator current);

Effects: Initializes current_ with std::move(current).

template<[convertible_to](concept.convertible#concept:convertible%5Fto "18.4.4 Concept convertible_to [concept.convertible]")<Iterator> U> constexpr basic_const_iterator(basic_const_iterator current);

Effects: Initializes _current__with std::move(current.current_).

Effects: Initializes current_ with std::forward<T>(current).

constexpr const Iterator& base() const & noexcept;

Effects: Equivalent to: return current_;

constexpr Iterator base() &&;

Effects: Equivalent to: return std::move(current_);

constexpr _reference_ operator*() const;

Effects: Equivalent to: return static_cast<_reference_>(*current_);

constexpr const auto* operator->() const requires is_lvalue_reference_v<iter_reference_t<Iterator>> && [same_as](concept.same#concept:same%5Fas "18.4.2 Concept same_as [concept.same]")<remove_cvref_t<iter_reference_t<Iterator>>, value_type>;

Returns: If Iterator models contiguous_iterator,to_address(current_); otherwise, addressof(*current_).

constexpr basic_const_iterator& operator++();

Effects: Equivalent to:++current_;return *this;

constexpr void operator++(int);

Effects: Equivalent to: ++current_;

constexpr basic_const_iterator operator++(int) requires [forward_iterator](#concept:forward%5Fiterator "24.3.4.11 Concept forward_iterator [iterator.concept.forward]")<Iterator>;

Effects: Equivalent to:auto tmp = *this;++*this;return tmp;

constexpr basic_const_iterator& operator--() requires [bidirectional_iterator](#concept:bidirectional%5Fiterator "24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]")<Iterator>;

Effects: Equivalent to:--current_;return *this;

constexpr basic_const_iterator operator--(int) requires [bidirectional_iterator](#concept:bidirectional%5Fiterator "24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]")<Iterator>;

Effects: Equivalent to:auto tmp = *this;--*this;return tmp;

constexpr basic_const_iterator& operator+=(difference_type n) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;constexpr basic_const_iterator& operator-=(difference_type n) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;

Effects: Equivalent to:current_ op n;return *this;

constexpr _reference_ operator[](difference_type n) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>

Effects: Equivalent to: return static_cast<_reference_>(_current__[n]);

template<[sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<Iterator> S> constexpr bool operator==(const S& s) const;

Effects: Equivalent to: return current_ == s;

template<[_not-a-const-iterator_](#concept:not-a-const-iterator "24.5.3.3 Class template basic_const_iterator [const.iterators.iterator]") CI> requires [_constant-iterator_](#concept:constant-iterator "24.5.3.2 Alias templates [const.iterators.alias]")<CI> && [convertible_to](concept.convertible#concept:convertible%5Fto "18.4.4 Concept convertible_to [concept.convertible]")<Iterator const&, CI> constexpr operator CI() const &;

Returns: std::move(current_).

constexpr bool operator<(const basic_const_iterator& y) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;constexpr bool operator>(const basic_const_iterator& y) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;constexpr bool operator<=(const basic_const_iterator& y) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;constexpr bool operator>=(const basic_const_iterator& y) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;constexpr auto operator<=>(const basic_const_iterator& y) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator> && [three_way_comparable](cmp.concept#concept:three%5Fway%5Fcomparable "17.12.4 Concept three_way_comparable [cmp.concept]")<Iterator>;

Effects: Equivalent to:return current_ op y.current_;

Effects: Equivalent to: return current_ op y;

template<[_not-a-const-iterator_](#concept:not-a-const-iterator "24.5.3.3 Class template basic_const_iterator [const.iterators.iterator]") I> friend constexpr bool operator<(const I& x, const basic_const_iterator& y) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator> && [totally_ordered_with](concept.totallyordered#concept:totally%5Fordered%5Fwith "18.5.5 Concept totally_ordered [concept.totallyordered]")<Iterator, I>;template<[_not-a-const-iterator_](#concept:not-a-const-iterator "24.5.3.3 Class template basic_const_iterator [const.iterators.iterator]") I> friend constexpr bool operator>(const I& x, const basic_const_iterator& y) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator> && [totally_ordered_with](concept.totallyordered#concept:totally%5Fordered%5Fwith "18.5.5 Concept totally_ordered [concept.totallyordered]")<Iterator, I>;template<[_not-a-const-iterator_](#concept:not-a-const-iterator "24.5.3.3 Class template basic_const_iterator [const.iterators.iterator]") I> friend constexpr bool operator<=(const I& x, const basic_const_iterator& y) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator> && [totally_ordered_with](concept.totallyordered#concept:totally%5Fordered%5Fwith "18.5.5 Concept totally_ordered [concept.totallyordered]")<Iterator, I>;template<[_not-a-const-iterator_](#concept:not-a-const-iterator "24.5.3.3 Class template basic_const_iterator [const.iterators.iterator]") I> friend constexpr bool operator>=(const I& x, const basic_const_iterator& y) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator> && [totally_ordered_with](concept.totallyordered#concept:totally%5Fordered%5Fwith "18.5.5 Concept totally_ordered [concept.totallyordered]")<Iterator, I>;

Effects: Equivalent to: return x op y.current_;

friend constexpr basic_const_iterator operator+(const basic_const_iterator& i, difference_type n) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;friend constexpr basic_const_iterator operator+(difference_type n, const basic_const_iterator& i) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;

Effects: Equivalent to: return basic_const_iterator(i.current_ + n);

friend constexpr basic_const_iterator operator-(const basic_const_iterator& i, difference_type n) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]")<Iterator>;

Effects: Equivalent to: return basic_const_iterator(i.current_ - n);

template<[sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<Iterator> S> constexpr difference_type operator-(const S& y) const;

Effects: Equivalent to: return current_ - y;

template<[_not-a-const-iterator_](#concept:not-a-const-iterator "24.5.3.3 Class template basic_const_iterator [const.iterators.iterator]") S> requires [sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<S, Iterator> friend constexpr difference_type operator-(const S& x, const basic_const_iterator& y);

Effects: Equivalent to: return x - y.current_;

24.5.4 Move iterators and sentinels [move.iterators]

24.5.4.1 General [move.iterators.general]

Class template move_iterator is an iterator adaptor with the same behavior as the underlying iterator except that its indirection operator implicitly converts the value returned by the underlying iterator's indirection operator to an rvalue.

Some generic algorithms can be called with move iterators to replace copying with moving.

[Example 1: list<string> s; vector<string> v1(s.begin(), s.end()); vector<string> v2(make_move_iterator(s.begin()), make_move_iterator(s.end())); — _end example_]

24.5.4.2 Class template move_iterator [move.iterator]

namespace std { template<class Iterator> class move_iterator { public: using iterator_type = Iterator;using iterator_concept = see below;using iterator_category = see below; using value_type = iter_value_t<Iterator>;using difference_type = iter_difference_t<Iterator>;using pointer = Iterator;using reference = iter_rvalue_reference_t<Iterator>;constexpr move_iterator();constexpr explicit move_iterator(Iterator i);template<class U> constexpr move_iterator(const move_iterator& u);template<class U> constexpr move_iterator& operator=(const move_iterator& u);constexpr const Iterator& base() const & noexcept;constexpr Iterator base() &&;constexpr reference operator*() const;constexpr move_iterator& operator++();constexpr auto operator++(int);constexpr move_iterator& operator--();constexpr move_iterator operator--(int);constexpr move_iterator operator+(difference_type n) const;constexpr move_iterator& operator+=(difference_type n);constexpr move_iterator operator-(difference_type n) const;constexpr move_iterator& operator-=(difference_type n);constexpr reference operator[](difference_type n) const;template<sentinel_for<Iterator> S> friend constexpr bool operator==(const move_iterator& x, const move_sentinel<S>& y);template<sized_sentinel_for<Iterator> S> friend constexpr iter_difference_t<Iterator> operator-(const move_sentinel<S>& x, const move_iterator& y);template<sized_sentinel_for<Iterator> S> friend constexpr iter_difference_t<Iterator> operator-(const move_iterator& x, const move_sentinel<S>& y);friend constexpr iter_rvalue_reference_t<Iterator> iter_move(const move_iterator& i) noexcept(noexcept(ranges::iter_move(i.current)));template<indirectly_swappable<Iterator> Iterator2> friend constexpr void iter_swap(const move_iterator& x, const move_iterator<Iterator2>& y) noexcept(noexcept(ranges::iter_swap(x.current, y.current)));private: Iterator current; };}

The member typedef-name iterator_concept is defined as follows:

If Iterator models random_access_iterator, then iterator_concept denotes random_access_iterator_tag.
Otherwise, if Iterator models bidirectional_iterator, then iterator_concept denotes bidirectional_iterator_tag.
Otherwise, if Iterator models forward_iterator, then iterator_concept denotes forward_iterator_tag.
Otherwise, iterator_concept denotes input_iterator_tag.

The member typedef-name iterator_category is defined if and only if the qualified-id iterator_traits<Iterator>::iterator_categoryis valid and denotes a type.

In that case, iterator_category denotes

random_access_iterator_tag if the typeiterator_traits<Iterator>::iterator_category modelsderived_from<random_access_iterator_tag>, and
iterator_traits<Iterator>::iterator_category otherwise.

24.5.4.3 Requirements [move.iter.requirements]

The template parameter Iterator shall either meet the Cpp17InputIterator requirements ([input.iterators]) or model input_iterator ([iterator.concept.input]).

Additionally, if any of the bidirectional traversal functions are instantiated, the template parameter shall either meet the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) or model bidirectional_iterator ([iterator.concept.bidir]).

If any of the random access traversal functions are instantiated, the template parameter shall either meet the Cpp17RandomAccessIterator requirements ([random.access.iterators]) or modelrandom_access_iterator ([iterator.concept.random.access]).

24.5.4.4 Construction and assignment [move.iter.cons]

constexpr move_iterator();

Effects: Value-initializes current.

constexpr explicit move_iterator(Iterator i);

Effects: Initializes current with std::move(i).

template<class U> constexpr move_iterator(const move_iterator& u);

Constraints: is_same_v<U, Iterator> is false andconst U& models convertible_to<Iterator>.

Effects: Initializes current with u.current.

template<class U> constexpr move_iterator& operator=(const move_iterator& u);

Effects: Assigns u.current tocurrent.

24.5.4.5 Conversion [move.iter.op.conv]

constexpr const Iterator& base() const & noexcept;

constexpr Iterator base() &&;

Returns: std::move(current).

24.5.4.6 Element access [move.iter.elem]

constexpr reference operator*() const;

Effects: Equivalent to: return ranges::iter_move(current);

constexpr reference operator[](difference_type n) const;

Effects: Equivalent to: return ranges::iter_move(current + n);

constexpr move_iterator& operator++();

Effects: As if by ++current.

constexpr auto operator++(int);

Effects: If Iterator models forward_iterator, equivalent to:move_iterator tmp = *this;++current;return tmp;

Otherwise, equivalent to ++current.

constexpr move_iterator& operator--();

Effects: As if by --current.

constexpr move_iterator operator--(int);

Effects: As if by:move_iterator tmp = *this;--current;return tmp;

constexpr move_iterator operator+(difference_type n) const;

Returns: move_iterator(current + n).

constexpr move_iterator& operator+=(difference_type n);

Effects: As if by: current += n;

constexpr move_iterator operator-(difference_type n) const;

Returns: move_iterator(current - n).

constexpr move_iterator& operator-=(difference_type n);

Effects: As if by: current -= n;

24.5.4.8 Comparisons [move.iter.op.comp]

template<class Iterator1, class Iterator2> constexpr bool operator==(const move_iterator<Iterator1>& x,const move_iterator<Iterator2>& y);template<[sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<Iterator> S> friend constexpr bool operator==(const move_iterator& x,const move_sentinel<S>& y);

Constraints: x.base() == y.base() is well-formed and convertible to bool.

Returns: x.base() == y.base().

template<class Iterator1, class Iterator2> constexpr bool operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

Constraints: x.base() < y.base() is well-formed and convertible to bool.

Returns: x.base() < y.base().

template<class Iterator1, class Iterator2> constexpr bool operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

Constraints: y.base() < x.base() is well-formed and convertible to bool.

template<class Iterator1, class Iterator2> constexpr bool operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

Constraints: y.base() < x.base() is well-formed and convertible to bool.

template<class Iterator1, class Iterator2> constexpr bool operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);

Constraints: x.base() < y.base() is well-formed and convertible to bool.

template<class Iterator1, [three_way_comparable_with](cmp.concept#concept:three%5Fway%5Fcomparable%5Fwith "17.12.4 Concept three_way_comparable [cmp.concept]")<Iterator1> Iterator2> constexpr compare_three_way_result_t<Iterator1, Iterator2> operator<=>(const move_iterator<Iterator1>& x,const move_iterator<Iterator2>& y);

Returns: x.base() <=> y.base().

24.5.4.9 Non-member functions [move.iter.nonmember]

template<class Iterator1, class Iterator2> constexpr auto operator-( const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());template<[sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<Iterator> S> friend constexpr iter_difference_t<Iterator> operator-(const move_sentinel<S>& x, const move_iterator& y);template<[sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<Iterator> S> friend constexpr iter_difference_t<Iterator> operator-(const move_iterator& x, const move_sentinel<S>& y);

Returns: x.base() - y.base().

template<class Iterator> constexpr move_iterator<Iterator> operator+(iter_difference_t<Iterator> n, const move_iterator<Iterator>& x);

Constraints: x.base() + n is well-formed and has type Iterator.

friend constexpr iter_rvalue_reference_t<Iterator> iter_move(const move_iterator& i) noexcept(noexcept(ranges::iter_move(i.current)));

Effects: Equivalent to: return ranges::iter_move(i.current);

template<[indirectly_swappable](#concept:indirectly%5Fswappable "24.3.7.4 Concept indirectly_swappable [alg.req.ind.swap]")<Iterator> Iterator2> friend constexpr void iter_swap(const move_iterator& x, const move_iterator<Iterator2>& y) noexcept(noexcept(ranges::iter_swap(x.current, y.current)));

Effects: Equivalent to: ranges::iter_swap(x.current, y.current).

template<class Iterator> constexpr move_iterator<Iterator> make_move_iterator(Iterator i);

Returns: move_iterator<Iterator>(std::move(i)).

24.5.4.10 Class template move_sentinel [move.sentinel]

Class template move_sentinel is a sentinel adaptor useful for denoting ranges together with move_iterator.

When an input iterator typeI and sentinel type S model sentinel_for<S, I>,move_sentinel<S> and move_iterator modelsentinel_for<move_sentinel<S>, move_iterator> as well.

[Example 1:

A move_if algorithm is easily implemented withcopy_if using move_iterator and move_sentinel:template<input_iterator I, sentinel_for S, weakly_incrementable O,indirect_unary_predicate Pred> requires indirectly_movable<I, O> void move_if(I first, S last, O out, Pred pred) { ranges::copy_if(move_iterator{std::move(first)}, move_sentinel<S>{last}, std::move(out), pred);}

— _end example_]

namespace std { template<semiregular S> class move_sentinel { public: constexpr move_sentinel();constexpr explicit move_sentinel(S s);template<class S2> requires convertible_to<const S2&, S> constexpr move_sentinel(const move_sentinel<S2>& s);template<class S2> requires assignable_from<S&, const S2&> constexpr move_sentinel& operator=(const move_sentinel<S2>& s);constexpr S base() const;private: S last; };}

24.5.4.11 Operations [move.sent.ops]

constexpr move_sentinel();

Effects: Value-initializes last.

If is_trivially_default_constructible_v<S> is true, then this constructor is a constexpr constructor.

constexpr explicit move_sentinel(S s);

Effects: Initializes last with std::move(s).

template<class S2> requires [convertible_to](concept.convertible#concept:convertible%5Fto "18.4.4 Concept convertible_to [concept.convertible]")<const S2&, S> constexpr move_sentinel(const move_sentinel<S2>& s);

Effects: Initializes last with s.last.

template<class S2> requires [assignable_from](concept.assignable#concept:assignable%5Ffrom "18.4.8 Concept assignable_from [concept.assignable]")<S&, const S2&> constexpr move_sentinel& operator=(const move_sentinel<S2>& s);

Effects: Equivalent to: last = s.last; return *this;

constexpr S base() const;

24.5.5 Common iterators [iterators.common]

24.5.5.1 Class template common_iterator [common.iterator]

Class template common_iterator is an iterator/sentinel adaptor that is capable of representing a non-common range of elements (where the types of the iterator and sentinel differ) as a common range (where they are the same).

It does this by holding either an iterator or a sentinel, and implementing the equality comparison operators appropriately.

[Note 1:

The common_iterator type is useful for interfacing with legacy code that expects the begin and end of a range to have the same type.

— _end note_]

[Example 1: template<class ForwardIterator> void fun(ForwardIterator begin, ForwardIterator end); list<int> s;using CI = common_iterator<counted_iterator<list<int>::iterator>, default_sentinel_t>; fun(CI(counted_iterator(s.begin(), 10)), CI(default_sentinel)); — _end example_]

namespace std { template<input_or_output_iterator I, sentinel_for S> requires ( $same\_as$ <I, S> && copyable) class common_iterator { public: constexpr common_iterator() requires default_initializable = default;constexpr common_iterator(I i);constexpr common_iterator(S s);template<class I2, class S2> requires convertible_to<const I2&, I> && convertible_to<const S2&, S> constexpr common_iterator(const common_iterator<I2, S2>& x);template<class I2, class S2> requires convertible_to<const I2&, I> && convertible_to<const S2&, S> && assignable_from<I&, const I2&> && assignable_from<S&, const S2&> constexpr common_iterator& operator=(const common_iterator<I2, S2>& x);constexpr decltype(auto) operator*();constexpr decltype(auto) operator*() const requires dereferenceable<const I>;constexpr auto operator->() const requires see below;constexpr common_iterator& operator++();constexpr decltype(auto) operator++(int);template<class I2, sentinel_for S2> requires sentinel_for<S, I2> friend constexpr bool operator==( const common_iterator& x, const common_iterator<I2, S2>& y);template<class I2, sentinel_for S2> requires sentinel_for<S, I2> && equality_comparable_with<I, I2> friend constexpr bool operator==( const common_iterator& x, const common_iterator<I2, S2>& y);template<sized_sentinel_for I2, sized_sentinel_for S2> requires sized_sentinel_for<S, I2> friend constexpr iter_difference_t<I2> operator-( const common_iterator& x, const common_iterator<I2, S2>& y);friend constexpr decltype(auto) iter_move(const common_iterator& i) noexcept(noexcept(ranges::iter_move(declval<const I&>()))) requires input_iterator;template<indirectly_swappable I2, class S2> friend constexpr void iter_swap(const common_iterator& x, const common_iterator<I2, S2>& y) noexcept(noexcept(ranges::iter_swap(declval<const I&>(), declval<const I2&>())));private: variant<I, S> v_; };template<class I, class S> struct incrementable_traits<common_iterator<I, S>> { using difference_type = iter_difference_t;};template<input_iterator I, class S> struct iterator_traits<common_iterator<I, S>> { using iterator_concept = see below;using iterator_category = see below; using value_type = iter_value_t;using difference_type = iter_difference_t;using pointer = see below;using reference = iter_reference_t;};}

24.5.5.2 Associated types [common.iter.types]

The nested typedef-name iterator_category of the specialization of iterator_traits for common_iterator<I, S>is defined if and only if iter_difference_t is an integral type.

In that case,iterator_category denotes forward_iterator_tag if the qualified-id iterator_traits::iterator_categoryis valid and denotes a type that models derived_from<forward_iterator_tag>; otherwise it denotes input_iterator_tag.

The remaining nested typedef-names of the specialization ofiterator_traits for common_iterator<I, S> are defined as follows:

iterator_concept denotes forward_iterator_tagif I models forward_iterator; otherwise it denotes input_iterator_tag.
Let a denote an lvalue of type const common_iterator<I, S>.
If the expression a.operator->() is well-formed, then pointer denotes decltype(a.operator->()).
Otherwise, pointer denotes void.

24.5.5.3 Constructors and conversions [common.iter.const]

constexpr common_iterator(I i);

Effects: Initializes v_ as if by v_{in_place_type, std::move(i)}.

constexpr common_iterator(S s);

Effects: Initializes v_ as if byv_{in_place_type<S>, std::move(s)}.

template<class I2, class S2> requires [convertible_to](concept.convertible#concept:convertible%5Fto "18.4.4 Concept convertible_to [concept.convertible]")<const I2&, I> && [convertible_to](concept.convertible#concept:convertible%5Fto "18.4.4 Concept convertible_to [concept.convertible]")<const S2&, S> constexpr common_iterator(const common_iterator<I2, S2>& x);

Preconditions: x.v_.valueless_by_exception() is false.

Effects: Initializes v_ as if byv_{in_place_index, get(x.v_)}, where i is x.v_.index().

Preconditions: x.v_.valueless_by_exception() is false.

Effects: Equivalent to:

If v_.index() == x.v_.index(), thenget(v_) = get(x.v_).
Otherwise, v_.emplace(get(x.v_)).

where i is x.v_.index().

24.5.5.4 Accessors [common.iter.access]

constexpr decltype(auto) operator*();constexpr decltype(auto) operator*() const requires [_dereferenceable_](#concept:dereferenceable "24.2 Header <iterator> synopsis [iterator.synopsis]")<const I>;

Preconditions: holds_alternative(v_) is true.

Effects: Equivalent to: return *get(v_);

constexpr auto operator->() const requires _see below_;

The expression in the requires-clause is equivalent to:indirectly_readable<const I> && (requires(const I& i) { i.operator->(); } || is_reference_v<iter_reference_t> || constructible_from<iter_value_t, iter_reference_t>)

Preconditions: holds_alternative(v_) is true.

Effects:

If I is a pointer type or if the expressionget(v_).operator->() is well-formed, equivalent to: return get(v_);
Otherwise, if iter_reference_t is a reference type, equivalent to:auto&& tmp = *get(v_);return addressof(tmp);
Otherwise, equivalent to:return proxy(*get(v_)); where_proxy_ is the exposition-only class:class proxy { iter_value_t keep_;constexpr proxy(iter_reference_t&& x) : keep_(std::move(x)) {} public: constexpr const iter_value_t* operator->() const noexcept { return addressof(keep_);} };

constexpr common_iterator& operator++();

Preconditions: holds_alternative(v_) is true.

Effects: Equivalent to ++get(v_).

constexpr decltype(auto) operator++(int);

Preconditions: holds_alternative(v_) is true.

Effects: If I models forward_iterator, equivalent to:common_iterator tmp = *this;++*this;return tmp;

Otherwise, ifrequires(I& i) { { *i++ } -> can-reference; }is true orindirectly_readable && constructible_from<iter_value_t, iter_reference_t> && move_constructible<iter_value_t> is false, equivalent to:return get(v_)++;

Otherwise, equivalent to:postfix-proxy p(**this);++*this;return p;where postfix-proxy is the exposition-only class:class postfix-proxy { iter_value_t keep_;constexpr postfix-proxy(iter_reference_t&& x) : keep_(std::forward<iter_reference_t>(x)) {} public: constexpr const iter_value_t& operator*() const noexcept { return keep_;} };

24.5.5.6 Comparisons [common.iter.cmp]

template<class I2, [sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]") S2> requires [sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<S, I2> friend constexpr bool operator==( const common_iterator& x, const common_iterator<I2, S2>& y);

Preconditions: x.v_.valueless_by_exception() and y.v_.valueless_by_exception()are each false.

Returns: true if i == j, and otherwise get(x.v_) == get<j>(y.v_), where i is x.v_.index() and j is y.v_.index().

template<class I2, [sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]") S2> requires [sentinel_for](#concept:sentinel%5Ffor "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<S, I2> && [equality_comparable_with](concept.equalitycomparable#concept:equality%5Fcomparable%5Fwith "18.5.4 Concept equality_comparable [concept.equalitycomparable]")<I, I2> friend constexpr bool operator==( const common_iterator& x, const common_iterator<I2, S2>& y);

Preconditions: x.v_.valueless_by_exception() and y.v_.valueless_by_exception()are each false.

Returns: true if i and j are each 1, and otherwiseget(x.v_) == get<j>(y.v_), wherei is x.v_.index() and j is y.v_.index().

template<[sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]") I2, [sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]") S2> requires [sized_sentinel_for](#concept:sized%5Fsentinel%5Ffor "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<S, I2> friend constexpr iter_difference_t<I2> operator-( const common_iterator& x, const common_iterator<I2, S2>& y);

Preconditions: x.v_.valueless_by_exception() and y.v_.valueless_by_exception()are each false.

Returns: 0 if i and j are each 1, and otherwiseget(x.v_) - get<j>(y.v_), wherei is x.v_.index() and j is y.v_.index().

24.5.5.7 Customizations [common.iter.cust]

friend constexpr decltype(auto) iter_move(const common_iterator& i) noexcept(noexcept(ranges::iter_move(declval<const I&>()))) requires [input_iterator](#concept:input%5Fiterator "24.3.4.9 Concept input_iterator [iterator.concept.input]");

Preconditions: holds_alternative(i.v_) is true.

Effects: Equivalent to: return ranges::iter_move(get(i.v_));

template<[indirectly_swappable](#concept:indirectly%5Fswappable "24.3.7.4 Concept indirectly_swappable [alg.req.ind.swap]") I2, class S2> friend constexpr void iter_swap(const common_iterator& x, const common_iterator<I2, S2>& y) noexcept(noexcept(ranges::iter_swap(declval<const I&>(), declval<const I2&>())));

Preconditions: holds_alternative(x.v_) and holds_alternative<I2>(y.v_)are each true.

Effects: Equivalent to ranges::iter_swap(get(x.v_), get<I2>(y.v_)).

24.5.6 Default sentinel [default.sentinel]

namespace std { struct default_sentinel_t { };}

Class default_sentinel_t is an empty type used to denote the end of a range.

It can be used together with iterator types that know the bound of their range (e.g., counted_iterator ([counted.iterator])).

24.5.7 Counted iterators [iterators.counted]

24.5.7.1 Class template counted_iterator [counted.iterator]

Class template counted_iterator is an iterator adaptor with the same behavior as the underlying iterator except that it keeps track of the distance to the end of its range.

It can be used together with default_sentinelin calls to generic algorithms to operate on a range of N elements starting at a given position without needing to know the end position a priori.

[Example 1: list<string> s; vector<string> v; ranges::copy(counted_iterator(s.begin(), 10), default_sentinel, back_inserter(v)); — _end example_]

Two values i1 and i2 of typescounted_iterator<I1>andcounted_iterator<I2>refer to elements of the same sequence if and only if there exists some integer n such thatnext(i1.base(), i1.count() + n)andnext(i2.base(), i2.count() + n)refer to the same (possibly past-the-end) element.

namespace std { template<input_or_output_iterator I> class counted_iterator { public: using iterator_type = I;using value_type = iter_value_t; using difference_type = iter_difference_t;using iterator_concept = typename I::iterator_concept; using iterator_category = typename I::iterator_category; constexpr counted_iterator() requires default_initializable = default;constexpr counted_iterator(I x, iter_difference_t n);template<class I2> requires convertible_to<const I2&, I> constexpr counted_iterator(const counted_iterator<I2>& x);template<class I2> requires assignable_from<I&, const I2&> constexpr counted_iterator& operator=(const counted_iterator<I2>& x);constexpr const I& base() const & noexcept;constexpr I base() &&;constexpr iter_difference_t count() const noexcept;constexpr decltype(auto) operator*();constexpr decltype(auto) operator*() const requires dereferenceable<const I>;constexpr auto operator->() const noexcept requires contiguous_iterator;constexpr counted_iterator& operator++();constexpr decltype(auto) operator++(int);constexpr counted_iterator operator++(int) requires forward_iterator;constexpr counted_iterator& operator--() requires bidirectional_iterator;constexpr counted_iterator operator--(int) requires bidirectional_iterator;constexpr counted_iterator operator+(iter_difference_t n) const requires random_access_iterator;friend constexpr counted_iterator operator+( iter_difference_t n, const counted_iterator& x) requires random_access_iterator;constexpr counted_iterator& operator+=(iter_difference_t n) requires random_access_iterator;constexpr counted_iterator operator-(iter_difference_t n) const requires random_access_iterator;template<common_with I2> friend constexpr iter_difference_t<I2> operator-( const counted_iterator& x, const counted_iterator<I2>& y);friend constexpr iter_difference_t operator-( const counted_iterator& x, default_sentinel_t);friend constexpr iter_difference_t operator-( default_sentinel_t, const counted_iterator& y);constexpr counted_iterator& operator-=(iter_difference_t n) requires random_access_iterator;constexpr decltype(auto) operator[](iter_difference_t n) const requires random_access_iterator;template<common_with I2> friend constexpr bool operator==( const counted_iterator& x, const counted_iterator<I2>& y);friend constexpr bool operator==( const counted_iterator& x, default_sentinel_t);template<common_with I2> friend constexpr strong_ordering operator<=>( const counted_iterator& x, const counted_iterator<I2>& y);friend constexpr decltype(auto) iter_move(const counted_iterator& i) noexcept(noexcept(ranges::iter_move(i.current))) requires input_iterator;template<indirectly_swappable I2> friend constexpr void iter_swap(const counted_iterator& x, const counted_iterator<I2>& y) noexcept(noexcept(ranges::iter_swap(x.current, y.current)));private: I current = I(); iter_difference_t length = 0; };template<input_iterator I> requires same_as<_ITER_TRAITS_(I), iterator_traits> struct iterator_traits<counted_iterator> : iterator_traits { using pointer = conditional_t<contiguous_iterator, add_pointer_t<iter_reference_t>, void>;};}

24.5.7.2 Constructors and conversions [counted.iter.const]

constexpr counted_iterator(I i, iter_difference_t n);

Effects: Initializes current with std::move(i) andlength with n.

template<class I2> requires [convertible_to](concept.convertible#concept:convertible%5Fto "18.4.4 Concept convertible_to [concept.convertible]")<const I2&, I> constexpr counted_iterator(const counted_iterator<I2>& x);

Effects: Initializes current with x.current andlength with x.length.

template<class I2> requires [assignable_from](concept.assignable#concept:assignable%5Ffrom "18.4.8 Concept assignable_from [concept.assignable]")<I&, const I2&> constexpr counted_iterator& operator=(const counted_iterator<I2>& x);

Effects: Assigns x.current to current andx.length to length.

24.5.7.3 Accessors [counted.iter.access]

constexpr const I& base() const & noexcept;

Effects: Equivalent to: return current;

Returns: std::move(current).

constexpr iter_difference_t count() const noexcept;

Effects: Equivalent to: return length;

24.5.7.4 Element access [counted.iter.elem]

Preconditions: length > 0 is true.

Effects: Equivalent to: return *current;

constexpr auto operator->() const noexcept requires [contiguous_iterator](#concept:contiguous%5Fiterator "24.3.4.14 Concept contiguous_iterator [iterator.concept.contiguous]");

Effects: Equivalent to: return to_address(current);

constexpr decltype(auto) operator[](iter_difference_t n) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]");

Preconditions: n < length.

Effects: Equivalent to: return current[n];

constexpr counted_iterator& operator++();

Preconditions: length > 0.

Effects: Equivalent to:++current;--length;return *this;

constexpr decltype(auto) operator++(int);

Preconditions: length > 0.

Effects: Equivalent to:--length;try { return current++; } catch(...) { ++length; throw; }

constexpr counted_iterator operator++(int) requires [forward_iterator](#concept:forward%5Fiterator "24.3.4.11 Concept forward_iterator [iterator.concept.forward]");

Effects: Equivalent to:counted_iterator tmp = *this;++*this;return tmp;

constexpr counted_iterator& operator--() requires [bidirectional_iterator](#concept:bidirectional%5Fiterator "24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]");

Effects: Equivalent to:--current;++length;return *this;

constexpr counted_iterator operator--(int) requires [bidirectional_iterator](#concept:bidirectional%5Fiterator "24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]");

Effects: Equivalent to:counted_iterator tmp = *this;--*this;return tmp;

constexpr counted_iterator operator+(iter_difference_t n) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]");

Effects: Equivalent to: return counted_iterator(current + n, length - n);

friend constexpr counted_iterator operator+( iter_difference_t n, const counted_iterator& x) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]");

Effects: Equivalent to: return x + n;

constexpr counted_iterator& operator+=(iter_difference_t n) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]");

Preconditions: n <= length.

Effects: Equivalent to:current += n; length -= n;return *this;

constexpr counted_iterator operator-(iter_difference_t n) const requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]");

Effects: Equivalent to: return counted_iterator(current - n, length + n);

template<[common_with](concept.common#concept:common%5Fwith "18.4.6 Concept common_with [concept.common]") I2> friend constexpr iter_difference_t<I2> operator-( const counted_iterator& x, const counted_iterator<I2>& y);

Preconditions: x and y refer to elements of the same sequence ([counted.iterator]).

Effects: Equivalent to: return y.length - x.length;

friend constexpr iter_difference_t operator-( const counted_iterator& x, default_sentinel_t);

Effects: Equivalent to:return -x.length;

friend constexpr iter_difference_t operator-( default_sentinel_t, const counted_iterator& y);

Effects: Equivalent to: return y.length;

constexpr counted_iterator& operator-=(iter_difference_t n) requires [random_access_iterator](#concept:random%5Faccess%5Fiterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]");

Preconditions: -n <= length.

Effects: Equivalent to:current -= n; length += n;return *this;

24.5.7.6 Comparisons [counted.iter.cmp]

template<[common_with](concept.common#concept:common%5Fwith "18.4.6 Concept common_with [concept.common]") I2> friend constexpr bool operator==( const counted_iterator& x, const counted_iterator<I2>& y);

Preconditions: x and y refer to elements of the same sequence ([counted.iterator]).

Effects: Equivalent to: return x.length == y.length;

friend constexpr bool operator==( const counted_iterator& x, default_sentinel_t);

Effects: Equivalent to: return x.length == 0;

template<[common_with](concept.common#concept:common%5Fwith "18.4.6 Concept common_with [concept.common]") I2> friend constexpr strong_ordering operator<=>( const counted_iterator& x, const counted_iterator<I2>& y);

Preconditions: x and y refer to elements of the same sequence ([counted.iterator]).

Effects: Equivalent to: return y.length <=> x.length;

[Note 1:

The argument order in the Effects: element is reversed because length counts down, not up.

— _end note_]

24.5.7.7 Customizations [counted.iter.cust]

friend constexpr decltype(auto) iter_move(const counted_iterator& i) noexcept(noexcept(ranges::iter_move(i.current))) requires [input_iterator](#concept:input%5Fiterator "24.3.4.9 Concept input_iterator [iterator.concept.input]");

Preconditions: i.length > 0 is true.

Effects: Equivalent to: return ranges::iter_move(i.current);

template<[indirectly_swappable](#concept:indirectly%5Fswappable "24.3.7.4 Concept indirectly_swappable [alg.req.ind.swap]") I2> friend constexpr void iter_swap(const counted_iterator& x, const counted_iterator<I2>& y) noexcept(noexcept(ranges::iter_swap(x.current, y.current)));

Preconditions: Both x.length > 0 and y.length > 0 are true.

Effects: Equivalent to ranges::iter_swap(x.current, y.current).

24.5.8 Unreachable sentinel [unreachable.sentinel]

Class unreachable_sentinel_t can be used with any weakly_incrementable type to denote the “upper bound” of an unbounded interval.

[Example 1: char* p;char* nl = find(p, unreachable_sentinel, '\n');

Provided a newline character really exists in the buffer, the use ofunreachable_sentinel above potentially makes the call to find more efficient since the loop test against the sentinel does not require a conditional branch.

— _end example_]

namespace std { struct unreachable_sentinel_t { template<weakly_incrementable I> friend constexpr bool operator==(unreachable_sentinel_t, const I&) noexcept { return false; } };}

24.6 Stream iterators [stream.iterators]

24.6.1 General [stream.iterators.general]

To make it possible for algorithmic templates to work directly with input/output streams, appropriate iterator-like class templates are provided.

[Example 1:

partial_sum(istream_iterator<double, char>(cin), istream_iterator<double, char>(), ostream_iterator<double, char>(cout, "\n"));reads a file containing floating-point numbers fromcin, and prints the partial sums ontocout.

— _end example_]

24.6.2 Class template istream_iterator [istream.iterator]

24.6.2.1 General [istream.iterator.general]

The class template istream_iteratoris an input iterator ([input.iterators]) that reads successive elements from the input stream for which it was constructed.

namespace std { template<class T, class charT = char, class traits = char_traits<charT>,class Distance = ptrdiff_t> class istream_iterator { public: using iterator_category = input_iterator_tag;using value_type = T;using difference_type = Distance;using pointer = const T*;using reference = const T&;using char_type = charT;using traits_type = traits;using istream_type = basic_istream<charT,traits>;constexpr istream_iterator();constexpr istream_iterator(default_sentinel_t); istream_iterator(istream_type& s);constexpr istream_iterator(const istream_iterator& x) noexcept(see below);~istream_iterator() = default; istream_iterator& operator=(const istream_iterator&) = default;const T& operator*() const;const T* operator->() const; istream_iterator& operator++(); istream_iterator operator++(int);friend bool operator==(const istream_iterator& i, default_sentinel_t);private: basic_istream<charT,traits>* in_stream; T value; };}

The type T shall meet the Cpp17DefaultConstructible,Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.

24.6.2.2 Constructors and destructor [istream.iterator.cons]

constexpr istream_iterator();constexpr istream_iterator(default_sentinel_t);

Effects: Constructs the end-of-stream iterator, value-initializing value.

Postconditions: in_stream == nullptr is true.

Remarks: If the initializer T() in the declaration auto x = T();is a constant initializer ([expr.const]), then these constructors are constexpr constructors.

istream_iterator(istream_type& s);

Effects: Initializes in_stream with addressof(s), value-initializes value, and then calls operator++().

constexpr istream_iterator(const istream_iterator& x) noexcept(_see below_);

Effects: Initializes in_stream with x.in_stream and initializes value with x.value.

Remarks: An invocation of this constructor may be used in a core constant expression if and only if the initialization of value from x.valueis a constant subexpression ([defns.const.subexpr]).

The exception specification is equivalent tois_nothrow_copy_constructible_v<T>.

~istream_iterator() = default;

Remarks: If is_trivially_destructible_v<T> is true, then this destructor is trivial.

24.6.2.3 Operations [istream.iterator.ops]

const T& operator*() const;

Preconditions: in_stream != nullptr is true.

const T* operator->() const;

Preconditions: in_stream != nullptr is true.

Returns: addressof(value).

istream_iterator& operator++();

Preconditions: in_stream != nullptr is true.

Effects: Equivalent to:if (!(*in_stream >> value)) in_stream = nullptr;

istream_iterator operator++(int);

Preconditions: in_stream != nullptr is true.

Effects: Equivalent to:istream_iterator tmp = *this;++*this;return tmp;

template<class T, class charT, class traits, class Distance> bool operator==(const istream_iterator<T,charT,traits,Distance>& x,const istream_iterator<T,charT,traits,Distance>& y);

Returns: x.in_stream == y.in_stream.

friend bool operator==(const istream_iterator& i, default_sentinel_t);

24.6.3 Class template ostream_iterator [ostream.iterator]

24.6.3.1 General [ostream.iterator.general]

ostream_iteratorwrites (usingoperator<<) successive elements onto the output stream from which it was constructed.

If it was constructed withcharT*as a constructor argument, this string, called adelimiter string, is written to the stream after everyTis written.

namespace std { template<class T, class charT = char, class traits = char_traits<charT>> class ostream_iterator { public: using iterator_category = output_iterator_tag;using value_type = void;using difference_type = ptrdiff_t;using pointer = void;using reference = void;using char_type = charT;using traits_type = traits;using ostream_type = basic_ostream<charT,traits>; ostream_iterator(ostream_type& s); ostream_iterator(ostream_type& s, const charT* delimiter); ostream_iterator(const ostream_iterator& x);~ostream_iterator(); ostream_iterator& operator=(const ostream_iterator&) = default; ostream_iterator& operator=(const T& value); ostream_iterator& operator*(); ostream_iterator& operator++(); ostream_iterator& operator++(int);private: basic_ostream<charT,traits>* out_stream; const charT* delim; };}

24.6.3.2 Constructors and destructor [ostream.iterator.cons.des]

ostream_iterator(ostream_type& s);

Effects: Initializes out_stream with addressof(s) anddelim with nullptr.

ostream_iterator(ostream_type& s, const charT* delimiter);

Effects: Initializes out_stream with addressof(s) anddelim with delimiter.

24.6.3.3 Operations [ostream.iterator.ops]

ostream_iterator& operator=(const T& value);

Effects: As if by:*out_stream << value;if (delim) *out_stream << delim;return *this;

ostream_iterator& operator*();

ostream_iterator& operator++(); ostream_iterator& operator++(int);

24.6.4 Class template istreambuf_iterator [istreambuf.iterator]

24.6.4.1 General [istreambuf.iterator.general]

The class templateistreambuf_iteratordefines an input iterator that reads successive_characters_from the streambuf for which it was constructed.

operator*provides access to the current input character, if any.

Each timeoperator++is evaluated, the iterator advances to the next input character.

If the end of stream is reached (streambuf_type::sgetc() returnstraits::eof()), the iterator becomes equal to theend-of-streamiterator value.

The default constructoristreambuf_iterator()and the constructoristreambuf_iterator(nullptr)both construct an end-of-stream iterator object suitable for use as an end-of-range.

All specializations of istreambuf_iterator shall have a trivial copy constructor, a constexpr default constructor, and a trivial destructor.

The result ofoperator*()on an end-of-stream iterator is undefined.

For any other iterator value achar_typevalue is returned.

It is impossible to assign a character via an input iterator.

namespace std { template<class charT, class traits = char_traits<charT>> class istreambuf_iterator { public: using iterator_category = input_iterator_tag;using value_type = charT;using difference_type = typename traits::off_type;using pointer = unspecified;using reference = charT;using char_type = charT;using traits_type = traits;using int_type = typename traits::int_type;using streambuf_type = basic_streambuf<charT,traits>;using istream_type = basic_istream<charT,traits>;class proxy; constexpr istreambuf_iterator() noexcept;constexpr istreambuf_iterator(default_sentinel_t) noexcept; istreambuf_iterator(const istreambuf_iterator&) noexcept = default;~istreambuf_iterator() = default; istreambuf_iterator(istream_type& s) noexcept; istreambuf_iterator(streambuf_type* s) noexcept; istreambuf_iterator(const proxy& p) noexcept; istreambuf_iterator& operator=(const istreambuf_iterator&) noexcept = default; charT operator*() const; istreambuf_iterator& operator++();proxy operator++(int);bool equal(const istreambuf_iterator& b) const;friend bool operator==(const istreambuf_iterator& i, default_sentinel_t s);private: streambuf_type* sbuf_; };}

24.6.4.2 Class istreambuf_iterator::proxy [istreambuf.iterator.proxy]

Classistreambuf_iterator<charT,traits>::_proxy_is for exposition only.

An implementation is permitted to provide equivalent functionality without providing a class with this name.

Classistreambuf_iterator<charT, traits>::_proxy_provides a temporary placeholder as the return value of the post-increment operator (operator++).

It keeps the character pointed to by the previous value of the iterator for some possible future access to get the character.

namespace std { template<class charT, class traits> class istreambuf_iterator<charT, traits>::proxy { charT keep_; basic_streambuf<charT,traits>* sbuf_;proxy(charT c, basic_streambuf<charT,traits>* sbuf) : keep_(c), sbuf_(sbuf) { } public: charT operator*() { return keep_; } };}

24.6.4.3 Constructors [istreambuf.iterator.cons]

For each istreambuf_iterator constructor in this subclause, an end-of-stream iterator is constructed if and only if the exposition-only member sbuf_ is initialized with a null pointer value.

constexpr istreambuf_iterator() noexcept;constexpr istreambuf_iterator(default_sentinel_t) noexcept;

Effects: Initializes sbuf_ with nullptr.

istreambuf_iterator(istream_type& s) noexcept;

Effects: Initializes sbuf_ with s.rdbuf().

istreambuf_iterator(streambuf_type* s) noexcept;

Effects: Initializes sbuf_ with s.

istreambuf_iterator(const _proxy_& p) noexcept;

Effects: Initializes sbuf_ with p.sbuf_.

24.6.4.4 Operations [istreambuf.iterator.ops]

Returns: The character obtained via thestreambufmembersbuf_->sgetc().

istreambuf_iterator& operator++();

Effects: As if by sbuf_->sbumpc().

Returns: proxy(sbuf_->sbumpc(), sbuf_).

bool equal(const istreambuf_iterator& b) const;

Returns: trueif and only if both iterators are at end-of-stream, or neither is at end-of-stream, regardless of whatstreambufobject they use.

template<class charT, class traits> bool operator==(const istreambuf_iterator<charT,traits>& a,const istreambuf_iterator<charT,traits>& b);

friend bool operator==(const istreambuf_iterator& i, default_sentinel_t s);

24.6.5 Class template ostreambuf_iterator [ostreambuf.iterator]

24.6.5.1 General [ostreambuf.iterator.general]

The class template ostreambuf_iteratorwrites successive characters onto the output stream from which it was constructed.

namespace std { template<class charT, class traits = char_traits<charT>> class ostreambuf_iterator { public: using iterator_category = output_iterator_tag;using value_type = void;using difference_type = ptrdiff_t;using pointer = void;using reference = void;using char_type = charT;using traits_type = traits;using streambuf_type = basic_streambuf<charT,traits>;using ostream_type = basic_ostream<charT,traits>; ostreambuf_iterator(ostream_type& s) noexcept; ostreambuf_iterator(streambuf_type* s) noexcept; ostreambuf_iterator& operator=(charT c); ostreambuf_iterator& operator*(); ostreambuf_iterator& operator++(); ostreambuf_iterator& operator++(int);bool failed() const noexcept;private: streambuf_type* sbuf_; };}

24.6.5.2 Constructors [ostreambuf.iter.cons]

ostreambuf_iterator(ostream_type& s) noexcept;

Preconditions: s.rdbuf()is not a null pointer.

Effects: Initializes sbuf_ with s.rdbuf().

ostreambuf_iterator(streambuf_type* s) noexcept;

Preconditions: sis not a null pointer.

Effects: Initializes sbuf_ with s.

24.6.5.3 Operations [ostreambuf.iter.ops]

ostreambuf_iterator& operator=(charT c);

Effects: Iffailed()yieldsfalse, callssbuf_->sputc(c); otherwise has no effect.

ostreambuf_iterator& operator*();

ostreambuf_iterator& operator++(); ostreambuf_iterator& operator++(int);

bool failed() const noexcept;

Returns: trueif in any prior use of memberoperator=, the call tosbuf_->sputc()returnedtraits::eof(); orfalseotherwise.

24.7 Range access [iterator.range]

In addition to being available via inclusion of the header, the function templates in [iterator.range] are available when any of the following headers are included:,,,,,,,,,,,,,,, and .

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

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

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

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

template<class C> constexpr auto cbegin(const C& c) noexcept(noexcept(std::begin(c))) -> decltype(std::begin(c));

Returns: std::begin(c).

template<class C> constexpr auto cend(const C& c) noexcept(noexcept(std::end(c))) -> decltype(std::end(c));

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

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

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

Returns: reverse_iterator<T*>(array + N).

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

Returns: reverse_iterator<T*>(array).

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

Returns: reverse_iterator<const E*>(il.end()).

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

Returns: reverse_iterator<const E*>(il.begin()).

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

Returns: std::rbegin(c).

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

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

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

template<class C> constexpr auto ssize(const C& c) -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>;

Effects: Equivalent to:return static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>>(c.size());

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

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

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

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

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

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

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

[iterators] (original) (raw)

24.1 General [iterators.general]

24.3 Iterator requirements [iterator.requirements]

24.3.1 General [iterator.requirements.general]

24.3.2 Associated types [iterator.assoc.types]

24.3.2.1 Incrementable traits [incrementable.traits]

24.3.2.2 Indirectly readable traits [readable.traits]

24.3.2.3 Iterator traits [iterator.traits]

24.3.3 Customization point objects [iterator.cust]

24.3.3.1 ranges​::​iter_move [iterator.cust.move]

24.3.3.2 ranges​::​iter_swap [iterator.cust.swap]

24.3.4 Iterator concepts [iterator.concepts]

24.3.4.1 General [iterator.concepts.general]

24.3.4.2 Concept indirectly_readable [iterator.concept.readable]

24.3.4.3 Concept indirectly_writable [iterator.concept.writable]

24.3.4.4 Concept weakly_incrementable [iterator.concept.winc]

24.3.4.5 Concept incrementable [iterator.concept.inc]

24.3.4.6 Concept input_or_output_iterator [iterator.concept.iterator]

24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]

24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]

24.3.4.9 Concept input_iterator [iterator.concept.input]

24.3.4.10 Concept output_iterator [iterator.concept.output]

24.3.4.11 Concept forward_iterator [iterator.concept.forward]

24.3.4.12 Concept bidirectional_iterator [iterator.concept.bidir]

24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]

24.3.4.14 Concept contiguous_iterator [iterator.concept.contiguous]

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

24.3.5.1 General [iterator.cpp17.general]

24.3.5.2 Cpp17Iterator [iterator.iterators]

24.3.5.3 Input iterators [input.iterators]

24.3.5.4 Output iterators [output.iterators]

24.3.5.5 Forward iterators [forward.iterators]

24.3.5.6 Bidirectional iterators [bidirectional.iterators]

24.3.5.7 Random access iterators [random.access.iterators]

24.3.6 Indirect callable requirements [indirectcallable]

24.3.6.2 Indirect callable traits [indirectcallable.traits]

24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]

24.3.6.4 Class template projected [projected]

24.3.7 Common algorithm requirements [alg.req]

24.3.7.1 General [alg.req.general]

24.3.7.2 Concept indirectly_movable [alg.req.ind.move]

24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]

24.3.7.4 Concept indirectly_swappable [alg.req.ind.swap]

24.3.7.5 Concept indirectly_comparable [alg.req.ind.cmp]

24.3.7.6 Concept permutable [alg.req.permutable]

24.3.7.7 Concept mergeable [alg.req.mergeable]

24.3.7.8 Concept sortable [alg.req.sortable]

24.4 Iterator primitives [iterator.primitives]

24.4.3 Iterator operations [iterator.operations]

24.4.4 Range iterator operations [range.iter.ops]

24.4.4.1 General [range.iter.ops.general]

24.4.4.2 ranges​::​advance [range.iter.op.advance]

24.4.4.3 ranges​::​distance [range.iter.op.distance]

24.4.4.4 ranges​::​next [range.iter.op.next]

24.4.4.5 ranges​::​prev [range.iter.op.prev]

24.5 Iterator adaptors [predef.iterators]

24.5.1 Reverse iterators [reverse.iterators]

24.5.1.1 General [reverse.iterators.general]

24.5.1.2 Class template reverse_iterator [reverse.iterator]

24.5.1.3 Requirements [reverse.iter.requirements]

24.5.1.4 Construction and assignment [reverse.iter.cons]

24.5.1.6 Element access [reverse.iter.elem]

24.5.1.7 Navigation [reverse.iter.nav]

24.5.1.8 Comparisons [reverse.iter.cmp]

24.5.1.9 Non-member functions [reverse.iter.nonmember]

24.5.2 Insert iterators [insert.iterators]

24.5.2.1 General [insert.iterators.general]

24.5.2.2 Class template back_insert_iterator [back.insert.iterator]

24.5.2.2.1 General [back.insert.iter.general]

24.5.2.2.2 Operations [back.insert.iter.ops]

24.5.2.2.3 back_inserter [back.inserter]

24.5.2.3 Class template front_insert_iterator [front.insert.iterator]

24.5.2.3.1 General [front.insert.iter.general]

24.5.2.3.2 Operations [front.insert.iter.ops]

24.5.2.3.3 front_inserter [front.inserter]

24.5.2.4 Class template insert_iterator [insert.iterator]

24.5.2.4.1 General [insert.iter.general]

24.5.2.4.2 Operations [insert.iter.ops]

24.5.2.4.3 inserter [inserter]

24.5.3 Constant iterators and sentinels [const.iterators]

24.3.3.1 ranges::iter_move [iterator.cust.move]

24.3.3.2 ranges::iter_swap [iterator.cust.swap]

24.4.4.2 ranges::advance [range.iter.op.advance]

24.4.4.3 ranges::distance [range.iter.op.distance]

24.4.4.4 ranges::next [range.iter.op.next]

24.4.4.5 ranges::prev [range.iter.op.prev]

24.6.4.2 Class istreambuf_iterator::proxy [istreambuf.iterator.proxy]