22 Iterators library [iterators]

To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types that correspond to a particular iterator type.

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

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category

be defined as the iterator's difference type, value type and iterator category, respectively.

In addition, the types

iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

shall be defined as the iterator's reference and pointer types, that is, for an iterator object a, the same type as the type of *a and a->, respectively.

In the case of an output iterator, the types

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer

may be defined as void.

If Iterator has valid ([temp.deduct]) member types difference_­type, value_­type, pointer, reference, and iterator_­category, iterator_­traits<Iterator> shall have the following as publicly accessible members:

  using difference_type   = typename Iterator::difference_type;
  using value_type        = typename Iterator::value_type;
  using pointer           = typename Iterator::pointer;
  using reference         = typename Iterator::reference;
  using iterator_category = typename Iterator::iterator_category;

Otherwise, iterator_­traits<Iterator> shall have no members by any of the above names.

It is specialized for pointers as

namespace std {
  template<class T> struct iterator_traits<T*> {
    using difference_type   = ptrdiff_t;
    using value_type        = remove_cv_t<T>;
    using pointer           = T*;
    using reference         = T&;
    using iterator_category = random_access_iterator_tag;
  };
}

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 are used as compile time tags for algorithm selection.

They are: input_­iterator_­tag, output_­iterator_­tag, forward_­iterator_­tag, bidirectional_­iterator_­tag and random_­access_­iterator_­tag.

For every iterator of type Iterator, iterator_­traits<Iterator>​::​iterator_­category shall be defined to be the most specific category tag that describes the iterator's behavior.

namespace std {
  struct input_iterator_tag { };
  struct output_iterator_tag { };
  struct forward_iterator_tag: public input_iterator_tag { };
  struct bidirectional_iterator_tag: public forward_iterator_tag { };
  struct random_access_iterator_tag: public bidirectional_iterator_tag { };
}

Since only random access iterators provide + and - operators, the library provides two function templates advance and distance.

These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.