Итераторы и алгоритмы
Содержание
Итераторы
Итератор --- это объект, указывающий на некоторый элемент цепочки элементов, позволяющий перебирать элементы цепочки с помощью некоторого набора операций. Процесс перебора элементов цепочки называется итерированием.
Наиболее очевидный пример итератора --- это указатель: указывает на объект, позволяет итерировать массив через инкремент и декремент. В C++ синтаксис итераторов заимствован у указателей.
Классификация
Выделяют пять типов итераторов. Ниже представлены итераторы в порядке убывания их силы.
- Random Access. Это наиболее мощный тип итераторов. Random access поддерживает произвольный доступ к последовательности элементов. По сути равносилен указателем: поддерживает операции инкремента(++), декремента (--), прибавления целого числа (+ val, - val), разыменования (*), разыменования со сдвигом ([]), доступа к члену (->). Как пример, итераторы такого типа предоставляет vector.
- Bidirectional. Двунаправленный итератор является более слабым типом итераторов: позволяет двигаться только вперед и назад, проходя через каждый элемент. Операции: ++, --, *, ->. Как пример, итераторы такого типа предоставляет list.
- Forward. Однонаправленный итератор позволяет двигаться только в одном направлении. Операции: ++, *, ->
- Input. Однонаправленный итератор, позволяющий только считывать данные, но не записывать.
- 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. Запись sort(RandomAccess p, RandomAccess q[, Comparator cmp]) означает, что у функции sort есть дополнительный необязательный параметр cmp. В данном случае --- это компаратор: сущность, которая сравнивает два элемента и возврашает меньше ли первый аргумент второго.
Под записью "итератор на элемент" следует понимать "итератор, указывающий на элемент".
Общие алгоритмы
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.
