27 Iterators library [iterators]

27.4 Iterator primitives [iterator.primitives]

Чтобы упростить задачу определения итераторов, библиотека предоставляет несколько классов и функций:

27.4.1 Iterator traits [iterator.traits]

Чтобы реализовать алгоритмы только в терминах итераторов, часто необходимо определить типы значений и различий, которые соответствуют конкретному типу итератора. Соответственно, требуется, чтобы if Iterator - тип итератора, типы

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

быть определенным как тип различия итератора, тип значения и категория итератора соответственно. Кроме того, типы

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

должен быть определен как тип ссылки и указателя итератора, то есть для объекта итератора a, тот же тип, что и тип *a и a->, соответственно. В случае итератора вывода типы

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

можно определить как void.

Если Iterator есть действительные ([temp.deduct]) типы элементов difference_­type, value_­type, pointer, reference, и iterator_­category, iterator_­traits<Iterator> должны иметь следующие в качестве публично доступных членов:

  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;

В противном случае не iterator_­traits<Iterator> будет иметь членов ни с одним из вышеуказанных имен.

Он специализируется на указателях как

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

а для указателей на const как

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

[ Example: Чтобы реализовать универсальную reverse функцию, программа на C ++ может делать следующее:

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
  typename iterator_traits<BidirectionalIterator>::difference_type n =
    distance(first, last);
  --n;
  while(n > 0) {
    typename iterator_traits<BidirectionalIterator>::value_type
     tmp = *first;
    *first++ = *--last;
    *last = tmp;
    n -= 2;
  }
}

end example]

27.4.2 Standard iterator tags [std.iterator.tags]

Часто бывает желательно, чтобы специализация шаблона функции определяла наиболее конкретную категорию аргумента итератора, чтобы функция могла выбрать наиболее эффективный алгоритм во время компиляции. Чтобы облегчить это, в библиотеке представлены 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]

27.4.3 Iterator operations [iterator.operations]

Поскольку только итераторы произвольного доступа обеспечивают + и - оператор, библиотека предоставляет два шаблона функции advance и distance. Эти шаблоны функций используют + и - для итераторов произвольного доступа (и, следовательно, являются для них постоянным временем); для входных, прямых и двунаправленных итераторов они используют ++ для реализации линейного времени.

template <class InputIterator, class Distance> constexpr void advance(InputIterator& i, Distance n);

Requires: n должен быть отрицательным только для двунаправленных итераторов и итераторов с произвольным доступом.

Effects: Увеличивает (или уменьшает для отрицательного значения n) ссылкуi на итератор на n.

template <class InputIterator> constexpr typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);

Effects: Если InputIterator соответствует требованиям итератора произвольного доступа, возвращается (last - first); в противном случае возвращает количество приращений, необходимых для перехода от first к last.

Requires: Если InputIterator удовлетворяет требованиям итератора произвольного доступа, last должен быть доступен first или first должен быть доступен из last; в противном случае last должен быть доступен из first.

template <class InputIterator> constexpr InputIterator next(InputIterator x, typename iterator_traits<InputIterator>::difference_type n = 1);

Effects: Эквивалентен: advance(x, n); return x;

template <class BidirectionalIterator> constexpr BidirectionalIterator prev(BidirectionalIterator x, typename iterator_traits<BidirectionalIterator>::difference_type n = 1);

Effects: Эквивалентен: advance(x, -n); return x;