9 Iterators library [iterators]

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;