51 KiB
[iterator.concepts]
24 Iterators library [iterators]
24.3 Iterator requirements [iterator.requirements]
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-idITER_TRAITS(I)::iterator_concept is valid and names a type, then ITER_CONCEPT(I) denotes that type.
-
Otherwise, if the qualified-idITER_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.
templateconcept indirectly-readable-impl = // exposition onlyrequires(const In in) {typename iter_value_t; typename iter_reference_t; typename iter_rvalue_reference_t; { *in } -> same_as<iter_reference_t>; { ranges::iter_move(in) } -> same_as<iter_rvalue_reference_t>; } &&common_reference_with<iter_reference_t&&, iter_value_t&> &&common_reference_with<iter_reference_t&&, iter_rvalue_reference_t&&> &&common_reference_with<iter_rvalue_reference_t&&, const iter_value_t&>;
templateconcept indirectly_readable =indirectly-readable-impl<remove_cvref_t>;
Given a value i of type I, I models indirectly_readable only 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); // not required to be equality-preservingstd::forward(o) = std::forward(t); // not required to be equality-preservingconst_cast<const iter_reference_t&&>(*o) = std::forward(t); // not required to be equality-preservingconst_cast<const iter_reference_t&&>(*std::forward(o)) = std::forward(t); // not required to be equality-preserving};
Let E be an expression such that decltype((E)) is T, and let o be a dereferenceable object of type Out.
Out and T model indirectly_writable<Out, T> only if:
If Out and T model indirectly_readable && same_as<iter_value_t, decay_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.
If E is an xvalue ([basic.lval]), the resulting state of the object it denotes is valid but unspecified ([lib.types.movedfrom]).
[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::string by 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.
templateconstexpr bool is-integer-like = see below; // exposition onlytemplateconstexpr bool is-signed-integer-like = see below; // exposition onlytemplateconcept weakly_incrementable =movable &&requires(I i) {typename iter_difference_t; requires is-signed-integer-like<iter_difference_t>; { ++i } -> same_as<I&>; // not required to be equality-preserving i++; // not required to be equality-preserving};
A type I is an integer-class type if it is in a set of implementation-defined types that behave as integer types do, as defined below.
[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 â2Nâ1 to 2Nâ1â1 (inclusive) for some integer N, in which case it is a signed-integer-class type, or0 to 2Nâ1 (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-like if it models integral or if it is an integer-class type.
An integer-like type I is signed-integer-like if it models signed_integral or if it is a signed-integer-class type.
An integer-like type I is unsigned-integer-like if 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 2N, where N is the width of the destination type.
Let a be an object of integer-class type I, let b be an object of integer-like type I2 such that the expression b is implicitly convertible to I, let x and y be, respectively, objects of type B(I) and B(I2) as described above that represent the same values as a and b, and let c be an lvalue of any integral type.
-
The expressions a++ and a-- shall be prvalues of type I whose values are equal to that of a prior to the evaluation of the expressions. The expression a++ shall modify the value of a by adding 1 to it. The expression a-- shall modify the value of a by 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 x is 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 as x @ y and y @ x, respectively. If x @ y or y @ x has type B(I), then a @ b or b @ a, respectively, has type I; if x @ y or y @ x has type B(I2), then a @ b or b @ a, respectively, has type I2; if x @ y or y @ x has any other type, then a @ b or b @ a, respectively, has that type.
An expression E of integer-class type I is contextually convertible to bool as if by bool(E != I(0)).
All integer-class types modelregular ([concepts.object]) andthree_way_comparable<strong_ordering> ([cmp.concept]).
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 m has the same value as numeric_limits<B(I)>::m, and each static member function f returns I(numeric_limits<B(I)>::f()).
For any two integer-like types I1 and I2, at least one of which is an integer-class type,common_type_t<I1, I2> denotes an integer-class type whose width is not less than that of I1 or I2.
If both I1 and I2 are signed-integer-like types, then common_type_t<I1, I2> is also a signed-integer-like type.
is-integer-like is true if and only if I is an integer-like type.
is-signed-integer-like is true if 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, then addressof(++i) is equal to addressof(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 ++a equals ++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]
templateconcept 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:
[Note 2:
The requirement thata equals b implies++a equals ++b (which is not true for weakly incrementable types) allows the use of multi-pass one-directional algorithms with types that model incrementable.
â 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]).
templateconcept 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.
template<class S, class I> concept [sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]") = [semiregular](concepts.object#concept:semiregular "18.6 Object concepts [concepts.object]")<S> && [input_or_output_iterator](#concept:input_or_output_iterator "24.3.4.6 Concept input_or_output_iterator [iterator.concept.iterator]")<I> && [weakly-equality-comparable-with](concept.equalitycomparable#concept:weakly-equality-comparable-with "18.5.4 Concept equality_comparable [concept.equalitycomparable]")<S, I>; // see [[concept.equalitycomparable]](concept.equalitycomparable "18.5.4 Concept equality_comparable")
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:
-
i == s is well-defined.
-
If bool(i != s) then i is dereferenceable and [++i, s) denotes a range.
-
assignable_from<I&, S> is either modeled or not satisfied.
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_for that allow the use of the - operator to compute the distance between them in constant time.
template<class S, class I> concept [sized_sentinel_for](#concept:sized_sentinel_for "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]") = [sentinel_for](#concept:sentinel_for "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<S, I> && !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> && requires(const I& i, const S& s) { { s - i } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_as [concept.same]")<iter_difference_t<I>>; { i - s } -> [same_as](concept.same#concept:same_as "18.4.2 Concept same_as [concept.same]")<iter_difference_t<I>>; };
Let i be an iterator of type I, and s a sentinel of type S such that [i, s) denotes a range.
Let N be the smallest number of applications of ++i necessary 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 âN is representable by iter_difference_t, then i - s is well-defined and equals âN.
template<class S, class I> constexpr bool disable_sized_sentinel_for = false;
Remarks: Pursuant to [namespace.std], users may specialize disable_sized_sentinel_for for cv-unqualified non-array object types S and I if 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]
templateconcept 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.
[Note 1:
Output iterators are not required to model equality_comparable.
â end note]
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); // not required to be equality-preserving};
Let E be an expression such that decltype((E)) is T, and let i be a dereferenceable object of type I.
I and T model 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.
templateconcept 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 X offer the multi-pass guarantee if
a == b implies ++a == ++b and
the expression((void)[](X x){++x;}(a), *a) is equivalent to the expression *a.
[Note 2:
The requirement thata == b implies++a == ++b and 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.
templateconcept 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, then bool(--(++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.
templateconcept 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 I such that b is reachable from a after 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:
-
(a += n) is equal to b.
-
addressof(a += n) is equal to addressof(a).
-
(a + n) is equal to (a += n).
-
For any two positive values x and y of type D, if (a + D(x + y)) is valid, then (a + D(x + y)) is equal to ((a + x) + y).
-
(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.
-
(b -= n) is equal to a.
-
addressof(b -= n) is equal to addressof(b).
-
(b - n) is equal to (b -= n).
-
If b is dereferenceable, then a[n] is valid and is equal to *b.
-
bool(a <= b) is true.
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.
templateconcept 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 I such 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).