9 Iterators library [iterators]

9.6 Iterator primitives [iterator.primitives]

9.6.3 Standard iterator tags [std.iterator.tags]

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 ]