Итераторы и алгоритмы

Итераторы

Итератор --- это объект, указывающий на некоторый элемент цепочки элементов, позволяющий перебирать элементы цепочки с помощью некоторого набора операций. Процесс перебора элементов цепочки называется итерированием.

Наиболее очевидный пример итератора --- это указатель: указывает на объект, позволяет итерировать массив через инкремент и декремент. В C++ синтаксис итераторов заимствован у указателей.

Классификация

Выделяют пять типов итераторов. Ниже представлены итераторы в порядке убывания их силы.

1. Random Access. Это наиболее мощный тип итераторов. Random access поддерживает произвольный доступ к последовательности элементов. По сути равносилен указателем: поддерживает операции инкремента(++), декремента (--), прибавления целого числа (+ val, - val), разыменования (*), разыменования со сдвигом ([]), доступа к члену (->). Как пример, итераторы такого типа предоставляет vector.
2. Bidirectional. Двунаправленный итератор является более слабым типом итераторов: позволяет двигаться только вперед и назад, проходя через каждый элемент. Операции: ++, --, *, ->. Как пример, итераторы такого типа предоставляет list.
3. Forward. Однонаправленный итератор позволяет двигаться только в одном направлении. Операции: ++, *, ->
4. Input. Однонаправленный итератор, позволяющий только считывать данные, но не записывать.
5. Output. Однонаправленный итератор, позволяющий только записывать данные, но не считывать.

Вне данной классификации лежит Reverse iterator. Reverse iterator обращает направление для bidirectional и random access итераторов. Для получения начала и конца итератора необходимо вызвать rbegin() и rend() соответственно. Reverse iterator реализует функцию base(), возвращающую обычный итератор. Для того, чтобы получить из обычного (bidirectional и random access) итератора reverse, достаточно использовать оператор присваивания.

set< int > s;
set< int > :: reverse_iterator i = s.rbegin();
set< int > :: iterator j = i.base();
i = j

Внимание, вопрос. Почему в одну сторону можно написать i = j, а в другую только j = i.base()?
Внимание, вопрос. Почему нельзя менять значения в set?

Служебная информация

Для описания итератора в С++ существует шаблон iterator_traits. Стандартные алгоритмы получают необходимую информацию об итераторах из специализаций этого шаблона для конкретного итератора.

Определение iterator_traits выглядит следующим образом.

template <class Iterator> struct iterator_traits {
  typedef typename Iterator::difference_type difference_type;
  typedef typename Iterator::value_type value_type;
  typedef typename Iterator::pointer pointer;
  typedef typename Iterator::reference reference;
  typedef typename Iterator::iterator_category iterator_category;
}

• difference_type описывает тип разности итераторов.
• value_type --- тип объекта, на который указывает итератор.
• pointer --- тип указателя на объект
• reference --- тип ссылки
• iterator_category_tag --- категория итератора. Может быть
  • input_iterator_tag
  • output_iterator_tag
  • forward_iterator_tag
  • bidirectional_iterator_tag
  • random_access_iterator_tag

Стандартные функции

advance(iterator, n) --- сдвигает итератор на n элементов. Для random access и bidirectional значение n может быть отрицательным. Работает со всеми типами итераторов вплоть до input. Для random access сдвигается сразу на n элементов, для остальных --- использует инкремент (или декремент).

distance(iterator first, iterator last) находит число элементов между first и last. Для radnom access использует значение разности итераторов, для остальных --- использует линейный поиск.

Алгоритмы

C++ поддерживает набор функций, позволяющий работать с цепочками элементов (range of elements). Джентльменский набор функций объявлен в хедере <algorithm>.

Общие функции

swap(T& a, T& b) меняет местами значения объектов.

iter_swap(forward_iter1 a, forward_iter2 b) меняет местами значения, на которые указывают итераторы (равносилен swap(*a, *b)).

min(const T& a, const T&b [, Compare cmp ]) находит минимум двух элементов и возвращает ссылку на минимальный. Может на вход принимать третий аргумент: компоратор.

max(const T& a, const T&b [, Compare cmp ]) аналогичен минимуму.