Итераторы и алгоритмы — различия между версиями

Версия 14:47, 29 мая 2011

Итераторы

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

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

swap_ranges(Forward p1, Forward q1, Forward p2) меняет местами значение каждого элемента последовательности из [p1, q1) со значением соответствующего элемента из [p2, ...).

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, UnaryPredicate pred) находит число элементов коллекции [p, q), удовлетворяющий унарному предикату pred.

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

equal(Input p1, Input q1, Input p2 [, BinaryPredicate 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, сравнивающий два элемента последовательностей. Возвращает bool<tt>.

<tt>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.

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

lower_bound(Forward p1, Forward q1, const T& value), lower_bound(Forward p1, Forward q1, const T& value, Comparator cmp) возвращает итератор, указывающий на первый элемент [p1, q1) не меньший value или не удовлетворяющий компаратору cmp(_, value) (под _ подставляются элементы последовательности).

upper_bound(Forward p1, Forward q1, const T& value), upper_bound(Forward p1, Forward q1, const T& value, Comparator cmp) возвращает итератор, указывающий на первый элемент [p1, q1) больший value или удовлетворяющий компаратору cmp(value, _) (под _ подставляются элементы последовательности).

equal_range(Forward p1, Forward q1, const T& value), equal_range(Forward p1, Forward q1, const T& value, Comparator cmp) возвращает пару итераторов, указывающих на начало и конец подпоследовательности элементов, равных value. Можно передать собственный компаратор.

binary_search(Forward p1, Forward q1, const T& value), binary_search(Forward p1, Forward q1, const T& value, Comparator cmp) возвращает, есть ли элемент, равный value в последовательности [p1, q1)<tt>. Можно передать собственный компаратор.

<tt>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 элементу.

transform(Input p1, Input q1, Output res, UnaryFunctor f), transform(Input p1, Input q1, Input p2, Output res, BinaryFunctor f) записывает в res последовательное применение функции f к каждому элементу последовательности [p1, q1). Есть перегрузка функции для бинарной функции. В этом случае передается дополнительный параметр, указывающий на первый элемент последовательности вторых аргументов [p2, ...).

replace(Forward p1, Forward q1, const T& oldValue, const T& newValue), replace_if(Forward p1, Forward q1, UnaryPredicate pred, const T& newValue) заменяет элементы последовательности [p1, q1), равные oldValue или удовлетворяющие предикату pred, на newValue.

replace_copy(Input p1, Input q1, Output res, const T& oldValue, const T& newValue), replace_copy_if(Input p1, Input q1, Output res, UnaryPredicate pred, const T& newValue) --- клоны replace и replace_if. Записывают результат работы в res.

fill(Forward p1, Forward q1, const T& value), fill_n(Output p1, Size n, const T& value) заполняет последовательность [p1, q1) или [p1, p1 + n) значением value.

generate(Forward p1, Forward q1, Functor f), generate_n(Output p1, Size n, Functor f) аналогичны fill и fill_n. Только элементам последовательности присваивается результат работы функтора f.

remove(Forward p1, Forward q1, const T& value), remove_if(Forward p1, Forward q1, UnaryPredicate pred) удаляют элементы последовательности [p1, q1), равные value или удовлетворяющие предикату pred

remove(Forward p1, Forward q1, const T& value), remove_if(Forward p1, Forward q1, UnaryPredicate pred) удаляют элементы последовательности [p1, q1), равные value или удовлетворяющие предикату pred.

remove_copy(Forward p1, Forward q1, Output res, const T& value), remove_copy_if(Forward p1, Forward q1, Output res, UnaryPredicate pred) --- клоны remove и remove_if. Записывают результат работу в res.

reverse(Bidirectional p1, Bidirectional q1), reverse_copy(Bidirectional p1, Bidirectional q1, Output res) переворачивает последовательность [p1, q1). reverse_copy записывает результат работы в res.

random_shuffle(RandomAccess p1, RandomAccess q1), random_shuffle(RandomAccess p1, RandomAccess q1, RandomNumberGenerator& rnd) перемешивают случайным образом последовательность [p1, q1). Можно передать свой генертор случайных чисел в качестве дополнительного параметра. Генератор на вход принимает число n и генерирует случайные числа в диапазоне [0, n).

unique(Input p1, Input q1), unique(Input p1, Input q1, BinaryPredicate pred) удаляет из последовательности [p1, q1) цепочки равных элеметов, оставляя только один. Пример: (1,2,2,3,3,2,2) -> (1,2,3,2). Можно передать собственный предикат сравнения pred. Возвращает итератор, указывающий на конец новой последовательности.

unique_copy(Input p1, Input q1, Output res), unique_copy(Input p1, Input q1, Output res, BinaryPredicate pred) --- клон unique. Записывает результат своей работы в res.

partition(Bidirectional p1, Bidirectional q1, Predicate pred) упорядочивает элементы последовательности [p1, q1) так, что сначала идут элементы удовлетворяющие предикату pred, а потом --- нет. Возвращает итератор на первый элемент, не удовлетворяющий pred или q1, если таких не оказалось.

stable_partition(Bidirectional p1, Bidirectional q1, Predicate pred) аналог partition. Сохраняет порядок следования элементов внутри удовлетворяющих и не удовлетворяющих pred подпоследовательностях. Возвращает также указатель на первый элемент, не удовлетворяющий pred.

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

merge(Input p1, Input q1, Input p2, Input q2, Output res[, Comparator cmp]) записывает в res упорядоченную последовательность элементов в res, померджив отсортированные последовательности [p1, q1) и [p2, q2). Можно передать собственный компаратор. Возвращает итератор, указывающий на конец последовательности res.

inplace_merge(Bidirectional p1, Bidirectional mid, Bidirectional q1[, Comparator cmp]) мерджит на месте отсортированные последовательности [p1, mid) и [mid, q1). Можно передать собственный компаратор.

includes(Input p1, Input q1, Input p2, Input q2[, Comparator cmp]) определяет, есть ли в последовательности [p1, q1) подпоследовательность, равная [p2, q2). Последовательности равны есть каждый элемент первой равен соответствующему элементу второй и их длины равны. Можно передать свой собственный компаратор. Возвращает bool.

(set_union, set_intersection, set_difference, set_symmetric_difference)(Input p1, Input q1, Input p2, Input q2, Output res[, Comparator cmp]) семейство функций, позволяющих производить стандартные операции над множествами. Множества представлены в отсортированных последовательностях [p1, q1) и [p2, q2). Результат записывается в res. Результат --- множество, представленное в виде отсортированной последовательности. Чтобы результат совпадал с ожидаемым, в последовательностях не должно быть равных элементов. Можно передать свой компаратор. Функция возвращает итератор, указывающий на конец последовательности res.

Сортировки, кучи и перестановки

Сортировка

sort(RandomAccess p1, RandomAccess q1[, Comparator cmp]) сортирует элементы последовательности [p1, q1). Можно передать свой компаратор.

stable_sort(RandomAccess p1, RandomAccess q1[, Comparator cmp]) --- версия стабильной сортировки.

partition_sort(RandomAccess p1, RandomAccess mid, RandomAccess q1[, Comparator cmp]) переставляет последовательность [p1, q1) так, что первые mid - p1 идут в начале в возрастающем порядке, тогда как остальные идут в произвольном. Можно передать собственный компаратор.

partition_sort(Input p1, Input q1, RandomAccess p2, RandomAccess q2[, Comparator cmp]) копирует первые q2 - p2 минимальных элементов из [p1, q1) в [p2, q2) в отсортированном порядке. [p1, q1) остается неизмененной.

nth_element(RandomAccess p1, RandomAccess nth, RandomAccess q1[, Comaparator cmp]) переставляет последовательность [p1, q1) так, что на позиции nth находится элемент, который находился бы там в случае сортировки всей последовательности. При этом все элементы до и после nth могут идти в произвольном порядке. Можно передать свой собственный компаратор.

Перестановки

next_permutation, prev_permutation(Bidirectional p1, Bidirectional q1[, Comparator cmp]) переставляет элементы последовательности получая следующую и предыдущую перестановку в лексикографическом порядке. Можно передать свой компаратор. Порядок зациклен, то есть после последней перестановки идет первая.

Кучи

Куча здесь используется в смысле структуры данных. Последовательность [0, n) --- куча, если для любого 0 <= i < n верно a[i] <= a[2 * i + 1] и a[i] <= a[2 * i + 2]. Более подробно можно посмотреть в Кормене.

push_heap(RandomAccess p1, RandomAccess q1[, Comparator cmp]) расширяет кучу [p1, q1 - 1) до [p1, q1), добавляя элемент q1 - 1. Можно передать свой компаратор.

pop_heap(RandomAccess p1, RandomAccess q1[, Comparator cmp]) переставляет кучу [p1, q1) так, что первый элемент оказывается на q1 - 1 позиции, а [p1, q1 - 1) снова образует кучу.

make_heap(RanddomAccess p1, RandomAccess q1[, Comparator cmp]) переставляет последовательность [p1, q1) так, чтобы она представляла кучу.

sort_heap(RanddomAccess p1, RandomAccess q1[, Comparator cmp]) сортирует кучу.

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

Функции, описанные ниже, находятся в хедере numeric

accumulate(Input p1, Input q1, T init[, BinaryOperation op]) суммирует последовательно от p1 к q1 все элементы последовательности начиная со значения T. Пример: ((1,2,3), 10) -> 16. Вместо суммы можно передать собственную операцию op. Элементы последовательности будут передаваться op в качестве второго аргумента.

adjacent_difference(Input p1, Input q1, Output res[, BinaryOperation op]) записывает в res частичные разности [p1, q1). Так если [p1, q1) = (x0, x1, x2), то в res будет записано (x0, x1 - x0, x2 - x1). Вместо разности можно передать собственную операцию op. Возвращает итератор, указывающий на конец res.

inner_product(Input p1, Input q1, Input p2, T init[, BinaryOperation1 add, BinaryOperation2 mult]) находит сумму попарных произведений элементов последовательностей [p1, q1) и [p2, ...) плюс начальное значение init. Можно задать свои операции сложения и умножения add и mult.

partial_sum(Input p1, Input q1, Output res[, BinaryOperation op]) находит частичные суммы последовательности [p1, q1) и записывает их в res. Можно задать свою операцию сложения op. Возвращает итератор, указывающий на конец res.