9 Iterators library [iterators]

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. All input iterators i support the expression *i, resulting in a value of some object type T, called the value type of the iterator. All output iterators support the expression *i = o where o is a value of some type that is in the set of types that are writable to the particular iterator type of i. For every iterator type X there is a corresponding signed integer type called the difference type of 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 five categories of iterators, according to the operations defined on them: input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators, as shown in Table [tab:iterators.relations].

The five categories of iterators correspond to the iterator concepts InputIterator, OutputIterator, ForwardIterator, BidirectionalIterator, and RandomAccessIterator, respectively. The generic term iterator refers to any type that satisfies Iterator.

Forward iterators satisfy all the requirements of input iterators and can be used whenever an input iterator is specified; Bidirectional iterators also satisfy all the requirements of forward iterators and can be used whenever a forward iterator is specified; Random access iterators also satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified.

Iterators that further satisfy the requirements of output iterators are called mutable iterators. Nonmutable iterators are referred to as constant iterators.

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. These values are called past-the-end values. Values of an iterator i for 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. [ Example: After the declaration of an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular value of a pointer.  — end example ] 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 using a value-initialized iterator as the source of a copy or move operation. [ Note: 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 sentinel that 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.

An iterator and a sentinel denoting a range are comparable. The types of a sentinel and an iterator that denote a range must satisfy Sentinel ([iterators.sentinel]). 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 by i and up to but not including the element 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 range.

A counted range [i,n) is empty if n == 0; otherwise, [i,n) 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 pointed to by the result of incrementing i n times.

A range [i,s) is valid if and only if s is reachable from i. A counted range [i,n) is valid if and only if n == 0; or n is positive, i is dereferenceable, and [++i,--n) is valid. The result of the application of functions in the library to invalid ranges is undefined.

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

Destruction of an iterator may invalidate pointers and references previously obtained from that iterator.

An invalid iterator is an iterator that may be singular.3

To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types that correspond to a particular iterator type. Accordingly, it is required that if WI is the name of a type that satisfies the WeaklyIncrementable concept ([iterators.weaklyincrementable]), R is the name of a type that satisfies the Readable concept ([iterators.readable]), and II is the name of a type that satisfies the InputIterator concept ([iterators.input]) concept, the types

difference_type_t<WI>
value_type_t<R>
iterator_category_t<II>

be defined as the iterator's difference type, value type and iterator category, respectively.

The Readable concept is satisfied by types that are readable by applying operator* including pointers, smart pointers, and iterators.

  template <class In>
  concept bool Readable =
    requires {
      typename value_type_t<In>;
      typename reference_t<In>;
      typename rvalue_reference_t<In>;
    } &&
    CommonReference<reference_t<In>&&, value_type_t<In>&> &&
    CommonReference<reference_t<In>&&, rvalue_reference_t<In>&&> &&
    CommonReference<rvalue_reference_t<In>&&, const value_type_t<In>&>;

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

  template <class Out, class T>
  concept bool 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 reference_t<Out>&&>(*o) =
        std::forward<T>(t); // not required to be equality preserving
      const_cast<const 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. Writable<Out, T> is satisfied only if

• (2.1)

  If Readable<Out> && Same<value_type_t<Out>, decay_t<T>> is satisfied, 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 ( ISO/IEC 14882:2014 §[basic.lval]), the resulting state of the object it denotes is valid but unspecified ( ISO/IEC 14882:2014 §[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 ]

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 bool WeaklyIncrementable =
    Semiregular<I> &&
    requires(I i) {
      typename difference_type_t<I>;
      requires SignedIntegral<difference_type_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. WeaklyIncrementable<I> is satisfied 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 &++i is equal to &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 ]

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 requirement supersedes the annotations on the increment expressions in the definition of WeaklyIncrementable.  — end note ]

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

Let a and b be incrementable objects of type I. Incrementable<I> is satisfied only if

• (2.1)

  If bool(a == b) then bool(a++ == b).

• (2.2)

  If bool(a == b) then bool((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 satisfy Incrementable. — end note ]

The Iterator concept forms the basis of the iterator concept taxonomy; every iterator satisfies the Iterator requirements. This concept specifies operations for dereferencing and incrementing an iterator. Most algorithms will require additional operations to compare iterators with sentinels ([iterators.sentinel]), to read ([iterators.input]) or write ([iterators.output]) values, or to provide a richer set of iterator movements ([iterators.forward], [iterators.bidirectional], [iterators.random.access]).)

  template <class I>
  concept bool Iterator =
    requires(I i) {
      { *i } -> auto&&; // Requires: i is dereferenceable
    } &&
    WeaklyIncrementable<I>;

[ Note: The requirement that the result of dereferencing the iterator is deducible from auto&& means that it cannot be void. — end note ]

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 bool Sentinel = Semiregular<S> && Iterator<I> && WeaklyEqualityComparableWith<S, I>;

The domain of == can change over time. Given an iterator i and sentinel s such that [i,s) denotes a range and i != s, [i,s) is not required to continue to denote a range after incrementing any iterator equal to i. Consequently, i == s is no longer required to be well-defined.

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 bool 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<difference_type_t<I>>&&; { i - s } -> Same<difference_type_t<I>>&&; };

[ Note: disable_sized_sentinel provides a mechanism to enable use of sentinels and iterators with the library that meet the syntactic requirements but do not in fact satisfy SizedSentinel. A program that instantiates a library template that requires SizedSentinel with an iterator type I and sentinel type S that meet the syntactic requirements of SizedSentinel<S, I> but do not satisfy SizedSentinel is ill-formed with no diagnostic required unless disable_sized_sentinel<S, I> evaluates to true ([structure.requirements]).  — end note ]

[ Note: The SizedSentinel concept is satisfied by pairs of RandomAccessIterators ([iterators.random.access]) and by counted iterators and their sentinels ([counted.iterator]). — end note ]

The InputIterator concept is a refinement of Iterator ([iterators.iterator]). It defines requirements for a type whose referenced values can be read (from the requirement for Readable ([iterators.readable])) and which can be both pre- and post-incremented. [ Note: Unlike in ISO/IEC 14882, input iterators are not required to satisfy EqualityComparable ([concepts.lib.compare.equalitycomparable]). — end note ]

  template <class I>
  concept bool InputIterator =
    Iterator<I> &&
    Readable<I> &&
    requires { typename iterator_category_t<I>; } &&
    DerivedFrom<iterator_category_t<I>, input_iterator_tag>;

The OutputIterator concept is a refinement of Iterator ([iterators.iterator]). It defines requirements for a type that can be used to write values (from the requirement for Writable ([iterators.writable])) and which can be both pre- and post-incremented. However, output iterators are not required to satisfy EqualityComparable.

  template <class I, class T>
  concept bool 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. OutputIterator<I, T> is satisfied 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. Algorithms that take output iterators can be used with ostreams as the destination for placing data through the ostream_iterator class as well as with insert iterators and insert pointers.  — end note ]

The ForwardIterator concept refines InputIterator ([iterators.input]), adding equality comparison and the multi-pass guarantee, specified below.

  template <class I>
  concept bool ForwardIterator =
    InputIterator<I> &&
    DerivedFrom<iterator_category_t<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 ([](X x){++x;}(a), *a) is equivalent to the expression *a.

[ Note: The requirement that a == b implies ++a == ++b (which is not true for weaker iterators) 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 ]

The BidirectionalIterator concept refines ForwardIterator ([iterators.forward]), and adds the ability to move an iterator backward as well as forward.

  template <class I>
  concept bool BidirectionalIterator =
    ForwardIterator<I> &&
    DerivedFrom<iterator_category_t<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 s such that ++s == r. Decrementable iterators r shall be in the domain of the expressions --r and r--.

Let a and b be decrementable objects of type I. BidirectionalIterator<I> is satisfied only if:

• (3.1)

  &--a == &a.

• (3.2)

  If bool(a == b), then bool(a-- == b).

• (3.3)

  If bool(a == b), then after evaluating both a-- and --b, bool(a == b) still holds.

• (3.4)

  If a is incrementable and bool(a == b), then bool(--(++a) == b).

• (3.5)

  If bool(a == b), then bool(++(--a) == b).

The RandomAccessIterator concept refines BidirectionalIterator ([iterators.bidirectional]) and adds support for constant-time advancement with +=, +, -=, and -, and the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.

  template <class I>
  concept bool RandomAccessIterator =
    BidirectionalIterator<I> &&
    DerivedFrom<iterator_category_t<I>, random_access_iterator_tag> &&
    StrictTotallyOrdered<I> &&
    SizedSentinel<I, I> &&
    requires(I i, const I j, const difference_type_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];
      requires Same<decltype(j[n]), reference_t<I>>;
    };

Let a and b be valid iterators of type I such that b is reachable from a. Let n be the smallest value of type difference_type_t<I> such that after n applications of ++a, then bool(a == b). RandomAccessIterator<I> is satisfied only if:

• (2.1)

  (a += n) is equal to b.

• (2.2)

  &(a += n) is equal to &a.

• (2.3)

  (a + n) is equal to (a += n).

• (2.4)

  For any two positive integers x and y, if a + (x + y) is valid, then a + (x + y) is equal to (a + x) + y.

• (2.5)

  a + 0 is equal to a.

• (2.6)

  If (a + (n - 1)) is valid, then a + n is equal to ++(a + (n - 1)).

• (2.7)

  (b += -n) is equal to a.

• (2.8)

  (b -= n) is equal to a.

• (2.9)

  &(b -= n) is equal to &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.