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.

There are several concepts that group requirements of algorithms that take callable objects ( ISO/IEC 14882:2014 §[func.require]) as arguments.

The indirect callable concepts are used to constrain those algorithms that accept callable objects ( ISO/IEC 14882:2014 §[func.def]) as arguments.

  template <class F, class I>
  concept bool IndirectUnaryInvocable =
    Readable<I> &&
    CopyConstructible<F> &&
    Invocable<F&, value_type_t<I>&> &&
    Invocable<F&, reference_t<I>> &&
    Invocable<F&, iter_common_reference_t<I>> &&
    CommonReference<
      result_of_t<F&(value_type_t<I>&)>,
      result_of_t<F&(reference_t<I>&&)>>;

  template <class F, class I>
  concept bool IndirectRegularUnaryInvocable =
    Readable<I> &&
    CopyConstructible<F> &&
    RegularInvocable<F&, value_type_t<I>&> &&
    RegularInvocable<F&, reference_t<I>> &&
    RegularInvocable<F&, iter_common_reference_t<I>> &&
    CommonReference<
      result_of_t<F&(value_type_t<I>&)>,
      result_of_t<F&(reference_t<I>&&)>>;

  template <class F, class I>
  concept bool IndirectUnaryPredicate =
    Readable<I> &&
    CopyConstructible<F> &&
    Predicate<F&, value_type_t<I>&> &&
    Predicate<F&, reference_t<I>> &&
    Predicate<F&, iter_common_reference_t<I>>;

  template <class F, class I1, class I2 = I1>
  concept bool IndirectRelation =
    Readable<I1> && Readable<I2> &&
    CopyConstructible<F> &&
    Relation<F&, value_type_t<I1>&, value_type_t<I2>&> &&
    Relation<F&, value_type_t<I1>&, reference_t<I2>> &&
    Relation<F&, reference_t<I1>, value_type_t<I2>&> &&
    Relation<F&, reference_t<I1>, reference_t<I2>> &&
    Relation<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;

  template <class F, class I1, class I2 = I1>
  concept bool IndirectStrictWeakOrder =
    Readable<I1> && Readable<I2> &&
    CopyConstructible<F> &&
    StrictWeakOrder<F&, value_type_t<I1>&, value_type_t<I2>&> &&
    StrictWeakOrder<F&, value_type_t<I1>&, reference_t<I2>> &&
    StrictWeakOrder<F&, reference_t<I1>, value_type_t<I2>&> &&
    StrictWeakOrder<F&, reference_t<I1>, reference_t<I2>> &&
    StrictWeakOrder<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;

  template <class> struct indirect_result_of { };

  template <class F, class... Is>
    requires Invocable<F, reference_t<Is>...>
  struct indirect_result_of<F(Is...)> :
    result_of<F(reference_t<Is>&&...)> { };

The projected class template is intended for use when specifying the constraints of algorithms that accept callable objects and projections ([defns.projection]). It bundles a Readable type I and a function Proj into a new Readable type whose reference type is the result of applying Proj to the reference_t of I.

  template <Readable I, IndirectRegularUnaryInvocable<I> Proj>
  struct projected {
    using value_type = remove_cv_t<remove_reference_t<indirect_result_of_t<Proj&(I)>>>;
    indirect_result_of_t<Proj&(I)> operator*() const;
  };

  template <WeaklyIncrementable I, class Proj>
  struct difference_type<projected<I, Proj>> {
    using type = difference_type_t<I>;
  };

[ Note: projected is only used to ease constraints specification. Its member function need not be defined. — end note ]

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 between Readable and Writable types: IndirectlyMovable, IndirectlyCopyable, and IndirectlySwappable. There are three relational concepts for rearrangements: Permutable, Mergeable, and Sortable. There is one relational concept for comparing values from different sequences: IndirectlyComparable.

[ Note: The equal_to<> and less<> ([comparisons]) function types used in the concepts below impose additional constraints on their arguments beyond those that appear explicitly in the concepts' bodies. equal_to<> requires its arguments satisfy EqualityComparableWith ([concepts.lib.compare.equalitycomparable]), and less<> requires its arguments satisfy StrictTotallyOrderedWith ([concepts.lib.compare.stricttotallyordered]). — end note ]

The IndirectlyMovable concept specifies the relationship between a Readable type and a Writable type between which values may be moved.

  template <class In, class Out>
  concept bool IndirectlyMovable =
    Readable<In> &&
    Writable<Out, rvalue_reference_t<In>>;

The IndirectlyMovableStorable concept augments IndirectlyMovable with additional requirements enabling the transfer to be performed through an intermediate object of the Readable type's value type.

  template <class In, class Out>
  concept bool IndirectlyMovableStorable =
    IndirectlyMovable<In, Out> &&
    Writable<Out, value_type_t<In>> &&
    Movable<value_type_t<In>> &&
    Constructible<value_type_t<In>, rvalue_reference_t<In>> &&
    Assignable<value_type_t<In>&, rvalue_reference_t<In>>;

The IndirectlyCopyable concept specifies the relationship between a Readable type and a Writable type between which values may be copied.

  template <class In, class Out>
  concept bool IndirectlyCopyable =
    Readable<In> &&
    Writable<Out, reference_t<In>>;

The IndirectlyCopyableStorable concept augments IndirectlyCopyable with additional requirements enabling the transfer to be performed through an intermediate object of the Readable type's value type. It also requires the capability to make copies of values.

  template <class In, class Out>
  concept bool IndirectlyCopyableStorable =
    IndirectlyCopyable<In, Out> &&
    Writable<Out, const value_type_t<In>&> &&
    Copyable<value_type_t<In>> &&
    Constructible<value_type_t<In>, reference_t<In>> &&
    Assignable<value_type_t<In>&, reference_t<In>>;

The IndirectlySwappable concept specifies a swappable relationship between the values referenced by two Readable types.

  template <class I1, class I2 = I1>
  concept bool IndirectlySwappable =
    Readable<I1> && Readable<I2> &&
    requires(I1&& i1, I2&& i2) {
      ranges::iter_swap(std::forward<I1>(i1), std::forward<I2>(i2));
      ranges::iter_swap(std::forward<I2>(i2), std::forward<I1>(i1));
      ranges::iter_swap(std::forward<I1>(i1), std::forward<I1>(i1));
      ranges::iter_swap(std::forward<I2>(i2), std::forward<I2>(i2));
    };

Given an object i1 of type I1 and an object i2 of type I2, IndirectlySwappable<I1, I2> is satisfied if after ranges::iter_swap(i1, i2), the value of *i1 is equal to the value of *i2 before the call, and vice versa.

The IndirectlyComparable concept specifies the common requirements of algorithms that compare values from two different sequences.

  template <class I1, class I2, class R = equal_to<>, class P1 = identity,
    class P2 = identity>
  concept bool IndirectlyComparable =
    IndirectRelation<R, projected<I1, P1>, projected<I2, P2>>;

The Permutable concept specifies the common requirements of algorithms that reorder elements in place by moving or swapping them.

  template <class I>
  concept bool Permutable =
    ForwardIterator<I> &&
    IndirectlyMovableStorable<I, I> &&
    IndirectlySwappable<I, I>;

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 = less<>, class P1 = identity, class P2 = identity>
  concept bool Mergeable =
    InputIterator<I1> &&
    InputIterator<I2> &&
    WeaklyIncrementable<Out> &&
    IndirectlyCopyable<I1, Out> &&
    IndirectlyCopyable<I2, Out> &&
    IndirectStrictWeakOrder<R, projected<I1, P1>, projected<I2, P2>>;

The Sortable concept specifies the common requirements of algorithms that permute sequences into ordered sequences (e.g., sort).

  template <class I, class R = less<>, class P = identity>
  concept bool Sortable =
    Permutable<I> &&
    IndirectStrictWeakOrder<R, projected<I, P>>;

For the sake of backwards compatibility, this document specifies the existence of an iterator_traits alias that collects an iterator's associated types. It is defined as if:

  template <InputIterator I> struct __pointer_type {        // exposition only
    using type = add_pointer_t<reference_t<I>>;
  };
  template <InputIterator I>
    requires requires(I i) { { i.operator->() } -> auto&&; }
  struct __pointer_type<I> {                                    // exposition only
    using type = decltype(declval<I>().operator->());
  };
  template <class> struct __iterator_traits { };                // exposition only
  template <Iterator I> struct __iterator_traits<I> {
    using difference_type = difference_type_t<I>;
    using value_type = void;
    using reference = void;
    using pointer = void;
    using iterator_category = output_iterator_tag;
  };
  template <InputIterator I> struct __iterator_traits<I> {  // exposition only
    using difference_type = difference_type_t<I>;
    using value_type = value_type_t<I>;
    using reference = reference_t<I>;
    using pointer = typename __pointer_type<I>::type;
    using iterator_category = iterator_category_t<I>;
  };
  template <class I>
    using iterator_traits = __iterator_traits<I>;

[ Note: iterator_traits is an alias template to prevent user code from specializing it.  — end note ]

[ Example: To implement a generic reverse function, a C++ program can do the following:

template <BidirectionalIterator I>
void reverse(I first, I last) {
  difference_type_t<I> n = distance(first, last);
  --n;
  while(n > 0) {
    value_type_t<I> tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}

 — end example ]

To facilitate interoperability between new code using iterators conforming to this document and older code using iterators that conform to the iterator requirements specified in ISO/IEC 14882, three specializations of std::iterator_traits are provided to map the newer iterator categories and associated types to the older ones.

namespace std {
  template <experimental::ranges::Iterator Out>
  struct iterator_traits<Out> {
    using difference_type   = experimental::ranges::difference_type_t<Out>;
    using value_type        = see below;
    using reference         = see below;
    using pointer           = see below;
    using iterator_category = std::output_iterator_tag;
  };
}

The nested type value_type is computed as follows:

• (2.1)

  If Out::value_type is valid and denotes a type, then std::iterator_traits<Out>::value_type is Out::value_type.

• (2.2)

  Otherwise, std::iterator_traits<Out>::value_type is void.

The nested type reference is computed as follows:

• (3.1)

  If Out::reference is valid and denotes a type, then std::iterator_traits<Out>::reference is Out::reference.

• (3.2)

  Otherwise, std::iterator_traits<Out>::reference is void.

The nested type pointer is computed as follows:

• (4.1)

  If Out::pointer is valid and denotes a type, then std::iterator_traits<Out>::pointer is Out::pointer.

• (4.2)

  Otherwise, std::iterator_traits<Out>::pointer is void.

namespace std {
  template <experimental::ranges::InputIterator In>
  struct iterator_traits<In> { };

  template <experimental::ranges::InputIterator In>
    requires experimental::ranges::Sentinel<In, In>
  struct iterator_traits<In> {
    using difference_type   = experimental::ranges::difference_type_t<In>;
    using value_type        = experimental::ranges::value_type_t<In>;
    using reference         = see below;
    using pointer           = see below;
    using iterator_category = see below;
  };
}

The nested type reference is computed as follows:

• (5.1)

  If In::reference is valid and denotes a type, then std::iterator_traits<In>::reference is In::reference.

• (5.2)

  Otherwise, std::iterator_traits<In>::reference is experimental::ranges::reference_t<In>.

The nested type pointer is computed as follows:

• (6.1)

  If In::pointer is valid and denotes a type, then std::iterator_traits<In>::pointer is In::pointer.

• (6.2)

  Otherwise, std::iterator_traits<In>::pointer is experimental::ranges::iterator_traits<In>::pointer.

Let type C be experimental::ranges::iterator_category_t<In>. The nested type std::iterator_traits<In>::iterator_category is computed as follows:

• (7.1)

  If C is the same as or inherits from std::input_iterator_tag or std::output_iterator_tag, std::iterator_traits<In>::iterator_category is C.

• (7.2)

  Otherwise, if experimental::ranges::reference_t<In> is not a reference type, std::iterator_traits<In>::iterator_category is std::input_iterator_tag.

• (7.3)

  Otherwise, if C is the same as or inherits from experimental::ranges::random_access_iterator_tag, std::iterator_traits<In>::iterator_category is std::random_access_iterator_tag.

• (7.4)

  Otherwise, if C is the same as or inherits from experimental::ranges::bidirectional_iterator_tag, std::iterator_traits<In>::iterator_category is std::bidirectional_iterator_tag.

• (7.5)

  Otherwise, if C is the same as or inherits from experimental::ranges::forward_iterator_tag, std::iterator_traits<In>::iterator_category is std::forward_iterator_tag.

• (7.6)

  Otherwise, std::iterator_traits<In>::iterator_category is std::input_iterator_tag.

[ Note: Some implementations may find it necessary to add additional constraints to these partial specializations to prevent them from being considered for types that conform to the iterator requirements specified in ISO/IEC 14882. — end note ]

It is often desirable for a function template specialization to find out what is the most specific category of its iterator argument, so that the function can select the most efficient algorithm at compile time. To facilitate this, the library introduces category tag classes which can be used as compile time tags for algorithm selection. [ Note: The preferred way to dispatch to more specialized algorithm implementations is with concept-based overloading. — end note ] The category tags are: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag and random_access_iterator_tag. For every input iterator of type I, iterator_category_t<I> shall be defined to be the most specific category tag that describes the iterator's behavior.

namespace std { namespace experimental { namespace ranges { inline namespace v1 {
  struct output_iterator_tag { };
  struct input_iterator_tag { };
  struct forward_iterator_tag : input_iterator_tag { };
  struct bidirectional_iterator_tag : forward_iterator_tag { };
  struct random_access_iterator_tag : bidirectional_iterator_tag { };
}}}}

[ Note: The output_iterator_tag is provided for the sake of backward compatibility.  — end note ]

[ Example: For a program-defined iterator BinaryTreeIterator, it could be included into the bidirectional iterator category by specializing the difference_type, value_type, and iterator_category templates:

template <class T> struct difference_type<BinaryTreeIterator<T>> {
  using type = ptrdiff_t;
};
template <class T> struct value_type<BinaryTreeIterator<T>> {
  using type = T;
};
template <class T> struct iterator_category<BinaryTreeIterator<T>> {
  using type = bidirectional_iterator_tag;
};

 — end example ]

Since only types that satisfy RandomAccessIterator provide the + operator, and types that satisfy SizedSentinel provide the - operator, the library provides customization point objects ([customization.point.object]) advance, distance, next, and prev. These customization point objects use + and - for random access iterators and ranges that satisfy SizedSentinel (and are, therefore, constant time for them); for output, input, forward and bidirectional iterators they use ++ to provide linear time implementations.

The name advance denotes a customization point object ([customization.point.object]). It has the following function call operators:

template <Iterator I> constexpr void operator()(I& i, difference_type_t<I> n) const;

The name distance denotes a customization point object. It has the following function call operators:

template <Iterator I, Sentinel<I> S> constexpr difference_type_t<I> operator()(I first, S last) const;

The name next denotes a customization point object. It has the following function call operators:

template <Iterator I> constexpr I operator()(I x) const;

The name prev denotes a customization point object. It has the following function call operators:

template <BidirectionalIterator I> constexpr I operator()(I x) const;

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. The fundamental relation between a reverse iterator and its corresponding underlying iterator i is established by the identity: *make_reverse_iterator(i) == *prev(i).

To make it possible to deal with insertion in the same way as writing into an array, a special kind of iterator adaptors, called insert 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 with result being an insert iterator will insert corresponding elements into the container. This device allows all of the copying algorithms in the library to work in the insert mode instead 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 satisfy OutputIterator. operator* returns the insert iterator itself. The assignment operator=(const T& x) is defined on insert iterators to allow writing into them, it inserts x right 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_iterator inserts elements at the end of a container, front_insert_iterator inserts elements at the beginning of a container, and insert_iterator inserts elements where the iterator points to in a container. back_inserter, front_inserter, and inserter are three functions making the insert iterators out of a container.

Class template common_iterator is an iterator/sentinel adaptor that is capable of representing a non-bounded range of elements (where the types of the iterator and sentinel differ) as a bounded 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: 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:

template <class ForwardIterator>
void fun(ForwardIterator begin, ForwardIterator end);

list<int> s;
// populate the list s
using CI =
  common_iterator<counted_iterator<list<int>::iterator>,
                  default_sentinel>;
// call fun on a range of 10 ints
fun(CI(make_counted_iterator(s.begin(), 10)),
    CI(default_sentinel()));

 — end example ]

The class template istream_iterator is an input iterator ([iterators.input]) that reads (using operator>>) successive elements from the input stream for which it was constructed. After it is constructed, and every time ++ is used, the iterator reads and stores a value of T. If the iterator fails to read and store a value of T (fail() on the stream returns true), the iterator becomes equal to the end-of-stream iterator value. The constructor with no arguments istream_iterator() always constructs an end-of-stream input iterator object, which is the only legitimate iterator to be used for the end condition. The result of operator* on an end-of-stream iterator is not defined. For any other iterator value a const T& is returned. The result of operator-> on an end-of-stream iterator is not defined. For any other iterator value a const T* is returned. The behavior of a program that applies operator++() to an end-of-stream iterator is undefined. It is impossible to store things into istream iterators.

Two end-of-stream iterators are always equal. An end-of-stream iterator is not equal to a non-end-of-stream iterator. Two non-end-of-stream iterators are equal when they are constructed from the same stream.

namespace std { namespace experimental { namespace ranges { inline namespace v1 {
  template <class T, class charT = char, class traits = char_traits<charT>,
      class Distance = ptrdiff_t>
  class istream_iterator {
  public:
    typedef input_iterator_tag iterator_category;
    typedef Distance difference_type;
    typedef T value_type;
    typedef const T& reference;
    typedef const T* pointer;
    typedef charT char_type;
    typedef traits traits_type;
    typedef basic_istream<charT, traits> istream_type;
    constexpr istream_iterator();
    constexpr istream_iterator(default_sentinel);
    istream_iterator(istream_type& s);
    istream_iterator(const istream_iterator& x) = default;
    ~istream_iterator() = default;

    const T& operator*() const;
    const T* operator->() const;
    istream_iterator& operator++();
    istream_iterator  operator++(int);
  private:
    basic_istream<charT, traits>* in_stream; // exposition only
    T value;                                 // exposition only
  };

  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);
  template <class T, class charT, class traits, class Distance>
    bool operator==(default_sentinel x,
            const istream_iterator<T, charT, traits, Distance>& y);
  template <class T, class charT, class traits, class Distance>
    bool operator==(const istream_iterator<T, charT, traits, Distance>& x,
            default_sentinel y);
  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);
  template <class T, class charT, class traits, class Distance>
    bool operator!=(default_sentinel x,
            const istream_iterator<T, charT, traits, Distance>& y);
  template <class T, class charT, class traits, class Distance>
    bool operator!=(const istream_iterator<T, charT, traits, Distance>& x,
            default_sentinel y);
}}}}

ostream_iterator writes (using operator<<) successive elements onto the output stream from which it was constructed. If it was constructed with charT* as a constructor argument, this string, called a delimiter string, is written to the stream after every T is written. It is not possible to get a value out of the output iterator. Its only use is as an output iterator in situations like

while (first != last)
  *result++ = *first++;

ostream_iterator is defined as:

namespace std { namespace experimental { namespace ranges { inline namespace v1 {
  template <class T, class charT = char, class traits = char_traits<charT>>
  class ostream_iterator {
  public:
    typedef ptrdiff_t difference_type;
    typedef charT char_type;
    typedef traits traits_type;
    typedef basic_ostream<charT, traits> ostream_type;
    constexpr ostream_iterator() noexcept;
    ostream_iterator(ostream_type& s) noexcept;
    ostream_iterator(ostream_type& s, const charT* delimiter) noexcept;
    ostream_iterator(const ostream_iterator& x) noexcept;
    ~ostream_iterator();
    ostream_iterator& operator=(const T& value);

    ostream_iterator& operator*();
    ostream_iterator& operator++();
    ostream_iterator& operator++(int);
  private:
    basic_ostream<charT, traits>* out_stream;  // exposition only
    const charT* delim;                        // exposition only
  };
}}}}

The class template istreambuf_iterator defines an input iterator ([iterators.input]) that reads successive characters from the streambuf for which it was constructed. operator* provides access to the current input character, if any. Each time operator++ is evaluated, the iterator advances to the next input character. If the end of stream is reached (streambuf_type::sgetc() returns traits::eof()), the iterator becomes equal to the end-of-stream iterator value. The default constructor istreambuf_iterator() and the constructor istreambuf_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 of operator*() on an end-of-stream iterator is undefined. For any other iterator value a char_type value is returned. It is impossible to assign a character via an input iterator.

namespace std { namespace experimental { namespace ranges { inline namespace v1 {
  template <class charT, class traits = char_traits<charT>>
  class istreambuf_iterator {
  public:
    typedef input_iterator_tag             iterator_category;
    typedef charT                          value_type;
    typedef typename traits::off_type      difference_type;
    typedef charT                          reference;
    typedef unspecified                   pointer;
    typedef charT                          char_type;
    typedef traits                         traits_type;
    typedef typename traits::int_type      int_type;
    typedef basic_streambuf<charT, traits> streambuf_type;
    typedef basic_istream<charT, traits>   istream_type;

    class proxy;                           // exposition only

    constexpr istreambuf_iterator() noexcept;
    constexpr istreambuf_iterator(default_sentinel) 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;
    charT operator*() const;
    istreambuf_iterator& operator++();
    proxy operator++(int);
    bool equal(const istreambuf_iterator& b) const;
  private:
    streambuf_type* sbuf_;                // exposition only
  };

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

The class template ostreambuf_iterator writes successive characters onto the output stream from which it was constructed. It is not possible to get a character value out of the output iterator.