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

Итераторы

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

Наиболее очевидный пример итератора --- это указатель: указывает на объект, позволяет итерировать массив через инкремент и декремент. В 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>.

Каждый алгоритм может работать только с определенными типами итераторов. Необходимый тип будет указываться в качестве типа аргумента. Например, запись count(Input p, Input q, T value) означает, что функция count принимает на вход итератор типа Input.

Под записью "итератор на элемент" следует понимать "итератор, указывающий на элемент".

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

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

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

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

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

Замечание В хедере win.h есть дефайны min и max. Если нужны функции из STL-а, стоит отключить min и max через undef.

Немодифицирующие алгоритмы

count(Input p, Input q, T value) находит число вхождений элемента value в коллекцию [p, q).

count_if(Input p, Input q, UPredicate pr) находит число элементов коллекции [p, q), удовлетворяющий унарному предикату pr.

for_each(Input p, Input q, Func f) вызывает последовательно функцию f для каждого элемента коллекции [p, q).

equal(Input p1, Input q1, Input p2 [, BPredicate pr]) сравнивает две последовательности [p1, q1), [p2, ?). Возвращает true, если первая является префиксом второй, т.е. элементы из [p1, q1) совпадают с первыми q1 - p1 элементами [p2, ?). В качестве дополнительного аргумента можно передать бинарный предикат равенства. Если вторая последовательность оказывается короче первой, поведение функции не определено.

mismatch(Input p1, Input q1, Input p2[, BPredicate pr]) сравнивает две последовательности [p1, q1), [p2, ?). Возвращает пару итераторов, указывающих на первое различие. Если [p1, q1) является префиксом [p2, ?), то mismatch возвращает пару (q1, q2), где q2 является элементов соответствующим q1 в [p2, ?).

lexicographical_compare(Input p1, Input q1, Input p2, Input q2[, Compare cmp]) возвращает меньше ли лексикографически [p1, q1) чем [p2, q2). Имеет дополнительный аргумент: компаратор cmp, сравнивающий два элемента последовательностей.

min_element(Forward p1, Forward q1[, Compare cmp]) возвращает итератор, указывающий на минимальный элемент в последовательности [p1, q1). Имеет дополнительный аргумент: компаратор cmp.

max_element(Forward p1, Forward q1[, Compare cmp]) аналогичен min_element.

search(Forward1 p1, Forward q1, Forward p2, Forward q2[, BPredicate pred]) находит первое вхождение последовательности [p2, q2) в [p1, q1).

search_n(Forward1 p1, Forward q1, Size size, T& val[, BPredicate pred]) находит первое вхождение последовательности size элементов равных val в [p2, q2). Можно передать свой компаратор в качестве пятого параметра pred.

adjacent_find(Forward1 p1, Forward q1, Size size, T& val[, BPredicate pred]) находит первое вхождение двух равных элементов в последовательности [p1, q1). Можно передать свой компаратор в качестве пятого параметра pred.

find(Forward1 p1, Forward q1, T& val), find_if(Forward1 p1, Forward q1, UPredicate pr) находят первое вхождение равное val или удовлетворяющее предикату pr.

find_first_of( Forward p1, Forward q1, Forward p2, Forward q2[, BPredicate pr]) находит первое вхождение последовательности [p2, q2) в [p1, q1). Можно передать свой компаратор в качестве пятого параметра pred.

find_end( Forward p1, Forward q1, Forward p2, Forward q2[, BPredicate pr]) находит последнее вхождение последовательности [p2, q2) в [p1, q1). Можно передать свой компаратор в качестве пятого параметра pred.

Модифицирующие алгоритмы

copy(Input p1, Input q1, Output res) копирует последовтельность [p1, q1) в res.

copy_backward(Bidirectional p1, Bidirectional q1, Bidirectional res) копирует последовательность [p1, q1) в res с конца. При этом res указывает на последний элемент контейнера, и копирование элементы копируются от q1 - 1 элемента к p1 элементу.