23 Iterators library [iterators]

23.3 Iterator requirements [iterator.requirements]

23.3.2 Associated types [iterator.assoc.types]

23.3.2.3 Iterator traits [iterator.traits]

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 =
  Copyable<I> && requires(I i) {
    {   *i } -> can-reference;
    {  ++i } -> Same<I&>;
    { *i++ } -> can-reference;
  };

template<class I>
concept cpp17-input-iterator =
  cpp17-iterator<I> && EqualityComparable<I> && requires(I i) {
    typename incrementable_traits<I>::difference_type;
    typename readable_traits<I>::value_type;
    typename common_reference_t<iter_reference_t<I>&&,
                                typename readable_traits<I>::value_type&>;
    *i++;
    typename common_reference_t<decltype(*i++)&&,
                                typename readable_traits<I>::value_type&>;
    requires SignedIntegral<typename incrementable_traits<I>::difference_type>;
  };

template<class I>
concept cpp17-forward-iterator =
  cpp17-input-iterator<I> && Constructible<I> &&
  is_lvalue_reference_v<iter_reference_t<I>> &&
  Same<remove_cvref_t<iter_reference_t<I>>, typename readable_traits<I>::value_type> &&
  requires(I i) {
    {  i++ } -> const I&;
    { *i++ } -> Same<iter_reference_t<I>>;
  };

template<class I>
concept cpp17-bidirectional-iterator =
  cpp17-forward-iterator<I> && requires(I i) {
    {  --i } -> Same<I&>;
    {  i-- } -> const I&;
    { *i-- } -> Same<iter_reference_t<I>>;
  };

template<class I>
concept cpp17-random-access-iterator =
  cpp17-bidirectional-iterator<I> && StrictTotallyOrdered<I> &&
  requires(I i, typename incrementable_traits<I>::difference_type n) {
    { i += n } -> Same<I&>;
    { i -= n } -> Same<I&>;
    { i +  n } -> Same<I>;
    { n +  i } -> Same<I>;
    { i -  n } -> Same<I>;
    { i -  i } -> Same<decltype(n)>;
    {  i[n]  } -> iter_reference_t<I>;
  };
The members of a specialization iterator_­traits<I> generated from the iterator_­traits primary template are computed as follows:
  • 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.
  • 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 readable_traits<I>::value_type;
      using difference_type   = typename incrementable_traits<I>::difference_type;
      using pointer           = see below;
      using reference         = see below;
    
    • 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.
    • If the qualified-id I::reference is valid and denotes a type, reference names that type.
      Otherwise, reference names iter_­reference_­t<I>.
    • If the qualified-id I::iterator_­category is valid and denotes a type, iterator_­category names that type.
      Otherwise, iterator_­category names:
      • random_­access_­iterator_­tag if I satisfies cpp17-random-access-iterator, or otherwise
      • bidirectional_­iterator_­tag if I satisfies cpp17-bidirectional-iterator, or otherwise
      • forward_­iterator_­tag if I satisfies cpp17-forward-iterator, or otherwise
      • input_­iterator_­tag.
  • 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.
  • 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&;
  };
}
[Example
:
To implement a generic reverse function, a C++ program can do the following:
template<class BI>
void reverse(BI first, BI last) {
  typename iterator_traits<BI>::difference_type n =
    distance(first, last);
  --n;
  while(n > 0) {
    typename iterator_traits<BI>::value_type
     tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}
end example
]