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

Итераторы

Итератор --- это объект, который указывает на некоторый элемент коллекции (будь то массив или контейнер). Итератор позволяет

• итерировать элементы контейнера;
• задавать последовательность элементов.

В 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)<tt> находит число элементов между first и last. Для radnom access использует значение разности итераторов, для остальных использует линейный поиск.

Алгоритмы

Общие

swap. iter_swap todo

min, max

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

Алгоритмы для отсортированных последовательностей

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