22 Iterators library [iterators]

22.3 Iterator requirements [iterator.requirements]

22.3.4 Iterator concepts [iterator.concepts]

22.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) denotes iterator_traits.

(1.1)
If the qualified-id ITER_TRAITS(I)::iterator_concept is valid and names a type, then ITER_CONCEPT(I) denotes that type.
(1.2)
Otherwise, if the qualified-id ITER_TRAITS(I)::iterator_category is valid and names a type, then ITER_CONCEPT(I) denotes that type.
(1.3)
Otherwise, if iterator_traits names a specialization generated from the primary template, then ITER_CONCEPT(I) denotes random_access_iterator_tag.
(1.4)
Otherwise, ITER_CONCEPT(I) does not denote a type.

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

— end example

]

22.3.4.2 Concept Readable [iterator.concept.readable]

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

template<class In>
  concept Readable =
    requires {
      typename iter_value_t<In>;
      typename iter_reference_t<In>;
      typename iter_rvalue_reference_t<In>;
    } &&
    CommonReference<iter_reference_t<In>&&, iter_value_t<In>&> &&
    CommonReference<iter_reference_t<In>&&, iter_rvalue_reference_t<In>&&> &&
    CommonReference<iter_rvalue_reference_t<In>&&, const iter_value_t<In>&>;

Given a value i of type I, I models Readable only 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

]

22.3.4.3 Concept Writable [iterator.concept.writable]

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

template<class Out, class T>
  concept Writable =
    requires(Out&& o, T&& t) {
      *o = std::forward<T>(t); // not required to be equality-preserving
      *std::forward<Out>(o) = std::forward<T>(t); // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*o) =
        std::forward<T>(t); // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) =
        std::forward<T>(t); // not required to be equality-preserving
    };

Let E be an an expression such that decltype((E)) is T, and let o be a dereferenceable object of type Out.

Out and T model Writable<Out, T> only if

(2.1)
If Out and T model Readable<Out> && Same<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.

If E is an xvalue ([basic.lval]), the resulting state of the object it denotes is valid but unspecified ([lib.types.movedfrom]).

[ Note

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

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

— end note

]

[ Note

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 Writable<I, std::string>.

— end note

]

22.3.4.4 Concept WeaklyIncrementable [iterator.concept.winc]

The WeaklyIncrementable 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 EqualityComparable.

template<class I>
  concept WeaklyIncrementable =
    Semiregular<I> &&
    requires(I i) {
      typename iter_difference_t<I>;
      requires SignedIntegral<iter_difference_t<I>>;
      { ++i } -> Same<I&>; // not required to be equality-preserving
      i++; // not required to be equality-preserving
    };

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 WeaklyIncrementable only if

(2.1)
The expressions ++i and i++ have the same domain.
(2.2)
If i is incrementable, then both ++i and i++ advance i to the next element.
(2.3)
If i is incrementable, then addressof(++i) is equal to addressof(i).

[ Note

For WeaklyIncrementable types, a equals b does not imply that ++a equals ++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

]

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

[ Note

This supersedes the annotations on the increment expressions in the definition of WeaklyIncrementable.

— end note

]

template<class I>
  concept Incrementable =
    Regular<I> &&
    WeaklyIncrementable<I> &&
    requires(I i) {
      { i++ } -> Same<I>;
    };

Let a and b be incrementable objects of type I.

I models Incrementable only if

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

[ Note

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

— end note

]

22.3.4.6 Concept Iterator [iterator.concept.iterator]

The Iterator concept forms the basis of the iterator concept taxonomy; every iterator models 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 Iterator =
    requires(I i) {
      { *i } -> can-reference;
    } &&
    WeaklyIncrementable<I>;

22.3.4.7 Concept Sentinel [iterator.concept.sentinel]

The Sentinel concept specifies the relationship between an Iterator type and a Semiregular type whose values denote a range.

🔗

template<class S, class I>
  concept Sentinel =
    Semiregular<S> &&
    Iterator<I> &&
    weakly-equality-comparable-with<S, I>; // See [concept.equalitycomparable]

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

Types S and I model Sentinel<S, I> only if

(2.1)
i == s is well-defined.
(2.2)
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.

22.3.4.8 Concept SizedSentinel [iterator.concept.sizedsentinel]

The SizedSentinel concept specifies requirements on an Iterator and a Sentinel that allow the use of the - operator to compute the distance between them in constant time.

🔗

template<class S, class I>
  concept SizedSentinel =
    Sentinel<S, I> &&
    !disable_sized_sentinel<remove_cv_t<S>, remove_cv_t<I>> &&
    requires(const I& i, const S& s) {
      { s - i } -> Same<iter_difference_t<I>>;
      { i - s } -> 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 SizedSentinel<S, I> only if

(2.1)
If N is representable by iter_difference_t, then s - i is well-defined and equals N.
(2.2)
If $- N$ is representable by iter_difference_t, then i - s is well-defined and equals $- N$ .

[ Note

disable_sized_sentinel allows use of sentinels and iterators with the library that satisfy but do not in fact model SizedSentinel.

— end note

]

[ Example

The SizedSentinel concept is modeled by pairs of RandomAccessIterators ([iterator.concept.random.access]) and by counted iterators and their sentinels ([counted.iterator]).

— end example

]

22.3.4.9 Concept InputIterator [iterator.concept.input]

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

[ Note

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

— end note

]

template<class I>
  concept InputIterator =
    Iterator<I> &&
    Readable<I> &&
    requires { typename ITER_CONCEPT(I); } &&
    DerivedFrom<ITER_CONCEPT(I), input_iterator_tag>;

22.3.4.10 Concept OutputIterator [iterator.concept.output]

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

[ Note

Output iterators are not required to model EqualityComparable.

— end note

]

template<class I, class T>
  concept OutputIterator =
    Iterator<I> &&
    Writable<I, T> &&
    requires(I i, T&& t) {
      *i++ = std::forward<T>(t); // not required to be equality-preserving
    };

Let E be an expression such that decltype((E)) is T, and let i be a dereferenceable object of type I.

I and T model OutputIterator<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

]

22.3.4.11 Concept ForwardIterator [iterator.concept.forward]

The ForwardIterator concept adds equality comparison and the multi-pass guarantee, specified below.

template<class I>
  concept ForwardIterator =
    InputIterator<I> &&
    DerivedFrom<ITER_CONCEPT(I), forward_iterator_tag> &&
    Incrementable<I> &&
    Sentinel<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 X offer the multi-pass guarantee if:

(4.1)
a == b implies ++a == ++b and
(4.2)
The expression ((void)[](X x){++x;}(a), *a) is equivalent to the expression *a.

[ Note

The requirement that a == 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

]

22.3.4.12 Concept BidirectionalIterator [iterator.concept.bidir]

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

template<class I>
  concept BidirectionalIterator =
    ForwardIterator<I> &&
    DerivedFrom<ITER_CONCEPT(I), bidirectional_iterator_tag> &&
    requires(I i) {
      { --i } -> Same<I&>;
      { i-- } -> Same<I>;
    };

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

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

Let a and b be equal objects of type I.

I models BidirectionalIterator only if:

(3.1)
If a and b are decrementable, then all of the following are true:
- (3.1.1)
  addressof(--a) == addressof(a)
- (3.1.2)
  bool(a-- == b)
- (3.1.3)
  after evaluating both a-- and --b, bool(a == b) is still true
- (3.1.4)
  bool(++(--a) == b)
(3.2)
If a and b are incrementable, then bool(--(++a) == b).

22.3.4.13 Concept RandomAccessIterator [iterator.concept.random.access]

The RandomAccessIterator 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 RandomAccessIterator =
    BidirectionalIterator<I> &&
    DerivedFrom<ITER_CONCEPT(I), random_access_iterator_tag> &&
    StrictTotallyOrdered<I> &&
    SizedSentinel<I, I> &&
    requires(I i, const I j, const iter_difference_t<I> n) {
      { i += n } -> Same<I&>;
      { j +  n } -> Same<I>;
      { n +  j } -> Same<I>;
      { i -= n } -> Same<I&>;
      { j -  n } -> Same<I>;
      {  j[n]  } -> Same<iter_reference_t<I>>;
    };

Let a and b be valid iterators of type I such that b is reachable from a after n applications of ++a, let D be iter_difference_t, and let n denote a value of type D.

I models RandomAccessIterator only if

(2.1)
(a += n) is equal to b.
(2.2)
addressof(a += n) is equal to addressof(a).
(2.3)
(a + n) is equal to (a += n).
(2.4)
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).
(2.5)
(a + D(0)) is equal to a.
(2.6)
If (a + D(n - 1)) is valid, then (a + n) is equal to ++(a + D(n - 1)).
(2.7)
(b += -n) is equal to a.
(2.8)
(b -= n) is equal to a.
(2.9)
addressof(b -= n) is equal to addressof(b).
(2.10)
(b - n) is equal to (b -= n).
(2.11)
If b is dereferenceable, then a[n] is valid and is equal to *b.
(2.12)
bool(a <= b) is true.

22.3.4.14 Concept ContiguousIterator [iterator.concept.contiguous]

The ContiguousIterator concept provides a guarantee that the denoted elements are stored contiguously in memory.

template<class I>
  concept ContiguousIterator =
    RandomAccessIterator<I> &&
    DerivedFrom<ITER_CONCEPT(I), contiguous_iterator_tag> &&
    is_lvalue_reference_v<iter_reference_t<I>> &&
    Same<iter_value_t<I>, remove_cvref_t<iter_reference_t<I>>>;

Let a and b be dereferenceable iterators of type I such that b is reachable from a, and let D be iter_difference_t.

The type I models ContiguousIterator only if addressof(*(a + D(b - a))) is equal to addressof(*a) + D(b - a).