23 Iterators library [iterators]

23.3 Iterator requirements [iterator.requirements]

23.3.2 Associated types [iterator.assoc.types]

23.3.2.1 Incrementable traits [incrementable.traits]

To implement algorithms only in terms of incrementable types, it is often necessary to determine the difference type that corresponds to a particular incrementable type.

Accordingly, it is required that if WI is the name of a type that models the weakly_incrementable concept ([iterator.concept.winc]), the type

iter_difference_t<WI>

be defined as the incrementable type's difference type.

namespace std {
  template<class> struct incrementable_traits { };

  template<class T>
    requires is_object_v<T>
  struct incrementable_traits<T*> {
    using difference_type = ptrdiff_t;
  };

  template<class I>
  struct incrementable_traits<const I>
    : incrementable_traits<I> { };

  template<class T>
    requires requires { typename T::difference_type; }
  struct incrementable_traits<T> {
    using difference_type = typename T::difference_type;
  };

  template<class T>
    requires (!requires { typename T::difference_type; } &&
              requires(const T& a, const T& b) { { a - b } -> integral; })
  struct incrementable_traits<T> {
    using difference_type = make_signed_t<decltype(declval<T>() - declval<T>())>;
  };

  template<class T>
    using iter_difference_t = see below;
}

Let

R_{I}

be remove_cvref_t.

The type iter_difference_t denotes

(2.1)
incrementable_traits< $R_{I}$ >::difference_type if iterator_traits< $R_{I}$ > names a specialization generated from the primary template, and
(2.2)
iterator_traits< $R_{I}$ >::difference_type otherwise.

Users may specialize incrementable_traits on program-defined types.

23.3.2.2 Indirectly readable traits [readable.traits]

To implement algorithms only in terms of indirectly readable types, it is often necessary to determine the value type that corresponds to a particular indirectly readable type.

Accordingly, it is required that if R is the name of a type that models the indirectly_readable concept ([iterator.concept.readable]), the type

iter_value_t<R>

be defined as the indirectly readable type's value type.

template<class> struct cond-value-type { };     // exposition only
template<class T>
  requires is_object_v<T>
struct cond-value-type<T> {
  using value_type = remove_cv_t<T>;
};

template<class> struct indirectly_readable_traits { };

template<class T>
struct indirectly_readable_traits<T*>
  : cond-value-type<T> { };

template<class I>
  requires is_array_v<I>
struct indirectly_readable_traits<I> {
  using value_type = remove_cv_t<remove_extent_t<I>>;
};

template<class I>
struct indirectly_readable_traits<const I>
  : indirectly_readable_traits<I> { };

template<class T>
  requires requires { typename T::value_type; }
struct indirectly_readable_traits<T>
  : cond-value-type<typename T::value_type> { };

template<class T>
  requires requires { typename T::element_type; }
struct indirectly_readable_traits<T>
  : cond-value-type<typename T::element_type> { };

template<class T> using iter_value_t = see below;

Let

R_{I}

be remove_cvref_t.

The type iter_value_t denotes

(2.1)
indirectly_readable_traits< $R_{I}$ >::value_type if iterator_traits< $R_{I}$ > names a specialization generated from the primary template, and
(2.2)
iterator_traits< $R_{I}$ >::value_type otherwise.

Class template indirectly_readable_traits may be specialized on program-defined types.

[Note

Some legacy output iterators define a nested type named value_type that is an alias for void.

These types are not indirectly_readable and have no associated value types.

— end note

]

[Note

Smart pointers like shared_ptr<int> are indirectly_readable and have an associated value type, but a smart pointer like shared_ptr<void> is not indirectly_readable and has no associated value type.

— end note

]

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::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_as<I&>;
    { *i++ } -> can-reference;
  };

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_lvalue_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 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 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::pointer names that type; otherwise, it names void.
(3.2)
Otherwise, if I satisfies the exposition-only concept cpp17-input-iterator, iterator_traits has the following publicly accessible members:
```
using iterator_category = see below;
using value_type = typename indirectly_readable_traits::value_type;
using difference_type = typename incrementable_traits::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.
- (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 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::difference_type is valid and denotes a type, then difference_type names that type; otherwise, it names void.
(3.4)
Otherwise, iterator_traits 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

]