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 be remove_­cvref_­t<I>.
The type iter_­difference_­t<I> denotes
  • incrementable_­traits<>​::​difference_­type if iterator_­traits<> names a specialization generated from the primary template, and
  • iterator_­traits<>​::​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 T> concept has-member-value-type = requires { typename T::value_type; }; // exposition only template<class T> concept has-member-element-type = requires { typename T::element_type; }; // exposition only 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<has-member-value-type T> struct indirectly_readable_traits<T> : cond-value-type<typename T::value_type> { }; template<has-member-element-type T> struct indirectly_readable_traits<T> : cond-value-type<typename T::element_type> { }; template<has-member-value-type T> requires has-member-element-type<T> struct indirectly_readable_traits<T> { }; template<has-member-value-type T> requires has-member-element-type<T> && same_­as<remove_cv_t<typename T::element_type>, remove_cv_t<typename T::value_type>> struct indirectly_readable_traits<T> : cond-value-type<typename T::value_type> { }; template<class T> using iter_value_t = see below;
Let be remove_­cvref_­t<I>.
The type iter_­value_­t<I> denotes
  • indirectly_­readable_­traits<>​::​value_­type if iterator_­traits<> names a specialization generated from the primary template, and
  • iterator_­traits<>​::​value_­type otherwise.
Class template indirectly_­readable_­traits may be specialized on program-defined types.
[Note 1:
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 2:
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<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_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<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 indirectly_readable_traits<I>::value_type; using difference_type = typename incrementable_traits<I>::difference_type; using pointer = see below; using reference = see below;
  • 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]).
[Example 1:
To indicate conformance to the input_­iterator concept but a lack of conformance to the Cpp17InputIterator requirements ([input.iterators]), an iterator_­traits specialization might have iterator_­concept denote input_­iterator_­tag but not define iterator_­category.
— end example]
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 2:
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]