24 Iterators library [iterators]

To implement algorithms only in terms of iterators, it is sometimes necessary to determine the iterator category that corresponds to a particular iterator type.

Accordingly, it is required that if I is the type of an iterator, the type

🔗

iterator_traits<I>::iterator_category be defined as the iterator's iterator category.

In addition, the types

🔗

iterator_traits<I>::pointer iterator_traits<I>::reference shall be defined as the iterator's pointer and reference types; that is, for an iterator object a of class type, the same type as decltype(a.operator->()) and decltype(*a), respectively.

The type iterator_traits<I>​::​pointer shall be void for an iterator of class type I that does not support operator->.

Additionally, in the case of an output iterator, the types iterator_traits<I>::value_type iterator_traits<I>::difference_type iterator_traits<I>::reference may be defined as void.

The definitions in this subclause make use of the following exposition-only concepts: template<class I> concept cpp17-iterator = requires(I i) { { *i } -> can-reference; { ++i } -> same_as<I&>; { *i++ } -> can-reference; } && copyable<I>; template<class I> concept cpp17-input-iterator = cpp17-iterator<I> && equality_comparable<I> && requires(I i) { typename incrementable_traits<I>::difference_type; typename indirectly_readable_traits<I>::value_type; typename common_reference_t<iter_reference_t<I>&&, typename indirectly_readable_traits<I>::value_type&>; typename common_reference_t<decltype(*i++)&&, typename indirectly_readable_traits<I>::value_type&>; requires signed_integral<typename incrementable_traits<I>::difference_type>; }; template<class I> concept cpp17-forward-iterator = cpp17-input-iterator<I> && constructible_from<I> && is_reference_v<iter_reference_t<I>> && same_as<remove_cvref_t<iter_reference_t<I>>, typename indirectly_readable_traits<I>::value_type> && requires(I i) { { i++ } -> convertible_to<const I&>; { *i++ } -> same_as<iter_reference_t<I>>; }; template<class I> concept cpp17-bidirectional-iterator = cpp17-forward-iterator<I> && requires(I i) { { --i } -> same_as<I&>; { i-- } -> convertible_to<const I&>; { *i-- } -> same_as<iter_reference_t<I>>; }; template<class I> concept cpp17-random-access-iterator = cpp17-bidirectional-iterator<I> && totally_ordered<I> && requires(I i, typename incrementable_traits<I>::difference_type n) { { i += n } -> same_as<I&>; { i -= n } -> same_as<I&>; { i + n } -> same_as<I>; { n + i } -> same_as<I>; { i - n } -> same_as<I>; { i - i } -> same_as<decltype(n)>; { i[n] } -> convertible_to<iter_reference_t<I>>; };

The members of a specialization iterator_traits<I> generated from the iterator_traits primary template are computed as follows:

• (3.1)
  If I has valid ([temp.deduct]) member types difference_type, value_type, reference, and iterator_category, then iterator_traits<I> has the following publicly accessible members: using iterator_category = typename I::iterator_category; using value_type = typename I::value_type; using difference_type = typename I::difference_type; using pointer = see below; using reference = typename I::reference;
  If the qualified-id I​::​pointer is valid and denotes a type, then iterator_traits<I>​::​pointer names that type; otherwise, it names void.
• (3.2)
  Otherwise, if I satisfies the exposition-only concept cpp17-input-iterator, iterator_traits<I> has the following publicly accessible members: using iterator_category = see below; using value_type = typename indirectly_readable_traits<I>::value_type; using difference_type = typename incrementable_traits<I>::difference_type; using pointer = see below; using reference = see below;
  • (3.2.1)
    If the qualified-id I​::​pointer is valid and denotes a type, pointer names that type.

    Otherwise, if decltype(​declval<I&>().operator->()) is well-formed, then pointer names that type.

    Otherwise, pointer names void.
  • (3.2.2)
    If the qualified-id I​::​reference is valid and denotes a type, reference names that type.

    Otherwise, reference names iter_reference_t<I>.
  • (3.2.3)
    If the qualified-id I​::​iterator_category is valid and denotes a type, iterator_category names that type.

    Otherwise, iterator_category names:

    • (3.2.3.1)
      random_access_iterator_tag if I satisfies cpp17-random-access-iterator, or otherwise
    • (3.2.3.2)
      bidirectional_iterator_tag if I satisfies cpp17-bidirectional-iterator, or otherwise
    • (3.2.3.3)
      forward_iterator_tag if I satisfies cpp17-forward-iterator, or otherwise
    • (3.2.3.4)
      input_iterator_tag.
• (3.3)
  Otherwise, if I satisfies the exposition-only concept cpp17-iterator, then iterator_traits<I> has the following publicly accessible members: using iterator_category = output_iterator_tag; using value_type = void; using difference_type = see below; using pointer = void; using reference = void;
  If the qualified-id incrementable_traits<I>​::​difference_type is valid and denotes a type, then difference_type names that type; otherwise, it names void.
• (3.4)
  Otherwise, iterator_traits<I> has no members by any of the above names.

Explicit or partial specializations of iterator_traits may have a member type iterator_concept that is used to indicate conformance to the iterator concepts ([iterator.concepts]).

iterator_traits is specialized for pointers as namespace std { template<class T> requires is_object_v<T> struct iterator_traits<T*> { using iterator_concept = contiguous_iterator_tag; using iterator_category = random_access_iterator_tag; using value_type = remove_cv_t<T>; using difference_type = ptrdiff_t; using pointer = T*; using reference = T&; }; }