[iterator.concepts] (original) (raw)

23 Iterators library [iterators]

23.3 Iterator requirements [iterator.requirements]

23.3.4 Iterator concepts [iterator.concepts]

23.3.4.1 General [iterator.concepts.general]

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

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

[ Note

:

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

— end note

]

[ Example

:

struct I { using value_type = int; using difference_type = int;

int operator*() const; I& operator++(); I operator++(int); I& operator--(); I operator--(int);

bool operator==(I) const; bool operator!=(I) const; };

iterator_­traits<I>​::​iterator_­category denotes input_­iterator_­tag, and ITER_­CONCEPT(I) denotes random_­access_­iterator_­tag.

— end example

]

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

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

template concept indirectly-readable-impl = requires(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&>;

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

Given a value i of type I, I models indirectly_­readableonly if the expression *i is equality-preserving.

[ Note

:

The expression *i is indirectly required to be valid via the exposition-only dereferenceable concept ([iterator.synopsis]).

— end note

]

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

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

template<class Out, class T> concept indirectly_writable = requires(Out&& o, T&& t) { *o = std::forward(t);
*std::forward(o) = std::forward(t);
const_cast<const iter_reference_t&&>(*o) = std::forward(t);
const_cast<const iter_reference_t&&>(*std::forward(o)) = std::forward(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

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

[ Note

:

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

:

indirectly_­writable has the awkward const_­cast expressions to reject iterators with prvalue non-proxy reference types that permit rvalue assignment but do not also permit const rvalue assignment.

Consequently, an iterator type I that returns std​::​stringby value does not model indirectly_­writable<I, std​::​string>.

— end note

]

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

The weakly_­incrementable concept specifies the requirements on types that can be incremented with the pre- and post-increment operators.

The increment operations are not required to be equality-preserving, nor is the type required to be equality_­comparable.

template inline constexpr bool is-integer-like = see below;

template inline constexpr bool is-signed-integer-like = see below;

template concept weakly_incrementable = default_initializable && 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 class types that behave as integer types do, as defined in below.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Let i be an object of type I.

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

I models weakly_­incrementable<I> only if

[ Note

:

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

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

Algorithms on weakly incrementable types should never attempt to pass through the same incrementable value twice.

They should be single-pass algorithms.

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

— end note

]

23.3.4.5 Concept incrementable [iterator.concept.inc]

The incrementable concept specifies requirements on types that can be incremented with the pre- and post-increment operators.

The increment operations are required to be equality-preserving, and the type is required to be equality_­comparable.

[ Note

:

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

— end note

]

template 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

[ Note

:

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

— end note

]

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

The input_­or_­output_­iterator concept forms the basis of the iterator concept taxonomy; every iterator models input_­or_­output_­iterator.

This concept specifies operations for dereferencing and incrementing an iterator.

Most algorithms will require additional operations to compare iterators with sentinels ([iterator.concept.sentinel]), to read ([iterator.concept.input]) or write ([iterator.concept.output]) values, or to provide a richer set of iterator movements ([iterator.concept.forward],[iterator.concept.bidir], [iterator.concept.random.access]).

template concept input_or_output_iterator = requires(I i) { { *i } -> can-reference; } && weakly_incrementable;

[ Note

:

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

— end note

]

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

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

template<class S, class I> concept sentinel_­for = semiregular<S> && input_­or_­output_­iterator<I> && weakly-equality-comparable-with<S, I>; // See [[concept.equalitycomparable]](concept.equalitycomparable)

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

The domain of == is not static.

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

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

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

The sized_­sentinel_­for concept specifies requirements on an input_­or_­output_­iterator type I and a corresponding sentinel_­for<I>that allow the use of the - operator to compute the distance between them in constant time.

template<class S, class I> concept sized_­sentinel_­for = sentinel_­for<S, I> && !disable_sized_sentinel_for<remove_cv_t<S>, remove_cv_t<I>> && requires(const I& i, const S& s) { { s - i } -> same_­as<iter_difference_t<I>>;{ i - s } -> same_­as<iter_difference_t<I>>;};

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

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

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

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

[ Note

:

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

:

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

— end example

]

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

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

[ Note

:

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 concept input_iterator = input_or_output_iterator && indirectly_readable && requires { typename ITER_CONCEPT(I); } && derived_from<ITER_CONCEPT(I), input_iterator_tag>;

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

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

[ Note

:

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

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;

[ Note

:

Algorithms on output iterators should never attempt to pass through the same iterator twice.

They should be single-pass algorithms.

— end note

]

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

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

template 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

:

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:

[ Note

:

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

— end note

]

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

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

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

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

The random_­access_­iterator concept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -.

Random access iterators also support array notation via subscripting.

template 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<I>, and let n denote a value of type D.

I models random_­access_­iterator only if

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

The contiguous_­iterator concept provides a guarantee that the denoted elements are stored contiguously in memory.

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

The type I models contiguous_­iterator only if