27 Iterators library [iterators]

Часто бывает желательно, чтобы специализация шаблона функции определяла наиболее конкретную категорию аргумента итератора, чтобы функция могла выбрать наиболее эффективный алгоритм во время компиляции. Чтобы облегчить это, в библиотеке представлены category tag классы, которые используются в качестве тегов времени компиляции для выбора алгоритма. Они являются input_­iterator_­tag, output_­iterator_­tag, forward_­iterator_­tag, bidirectional_­iterator_­tag и random_­access_­iterator_­tag. Для каждого итератора типа Iterator, iterator_­traits<Iterator>​::​iterator_­category должны быть определены наиболее конкретной категории тег , который описывает поведение итератора.

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 { };
}

[  Example: Для программного итератора BinaryTreeIteratorон может быть включен в категорию двунаправленных итераторов путем специализации iterator_­traits шаблона:

template<class T> struct iterator_traits<BinaryTreeIterator<T>> {
  using iterator_category = bidirectional_iterator_tag;
  using difference_type   = ptrdiff_t;
  using value_type        = T;
  using pointer           = T*;
  using reference         = T&;
};

 — end example ]

[  Example: Если evolve() это хорошо определено для двунаправленных итераторов, но может быть реализовано более эффективно для итераторов с произвольным доступом, то реализация выглядит следующим образом:

template <class BidirectionalIterator>
inline void
evolve(BidirectionalIterator first, BidirectionalIterator last) {
  evolve(first, last,
    typename iterator_traits<BidirectionalIterator>::iterator_category());
}

template <class BidirectionalIterator>
void evolve(BidirectionalIterator first, BidirectionalIterator last,
  bidirectional_iterator_tag) {
  // more generic, but less efficient algorithm
}

template <class RandomAccessIterator>
void evolve(RandomAccessIterator first, RandomAccessIterator last,
  random_access_iterator_tag) {
  // more efficient, but less generic algorithm
}

 — end example ]