Язык программирования C++. Пятое издание - Стенли Липпман

Итератор вывода (output iterator) можно рассматривать как итератор ввода, обладающий дополнительными функциональными возможностями. Итератор вывода применяется для записи в элемент, но чтения он не гарантирует. Для итераторов вывода обязательны следующие функции.

• Префиксный и постфиксный инкременты (++), используемые для перемещения итератора.

• Оператор обращения к значению (*) может быть применен только к операнду, расположенному слева от оператора присвоения. Присвоение при обращении к значению итератора вывода позволяет осуществить запись в элемент.

Значение итератору вывода можно присвоить только однажды. Подобно итераторам ввода, итераторы вывода можно использовать только для однопроходных алгоритмов. Итераторы, используемые как итераторы назначения, обычно являются итераторами вывода. Например, третий параметр алгоритма copy() является итератором вывода. Итератор ostream_iterator имеет тип итератора вывода.

• Прямой итератор (forward iterator) позволяет читать и записывать данные в последовательность. Они перемещаются по последовательности только в одном направлении. Прямые итераторы поддерживают все операции итераторов ввода и вывода. Кроме того, они позволяют читать и записывать значение в тот же элемент несколько раз. Поэтому сохраненное состояние прямого итератора можно использовать. Следовательно, алгоритмы, использующие прямые итераторы, могут осуществить несколько проходов через последовательность. Алгоритму replace() требуется прямой итератор; итераторы контейнера forward_list являются прямыми итераторами.

• Двунаправленный итератор (bidirectional iterator) позволяет читать и записывать данные в последовательность в обоих направлениях. Кроме всех функциональных возможностей прямого итератора, двунаправленный итератор поддерживает также префиксный и постфиксный декременты (--). Алгоритму reverse() требуется двунаправленный итератор. Все библиотечные контейнеры, кроме forward_list, предоставляют итераторы, соответствующие требованиям для двунаправленного итератора.

• Итератор прямого доступа (random-access iterator) обеспечивает доступ к любой позиции последовательности в любой момент. Эти итераторы обладают всеми функциональными возможностями двунаправленных итераторов. Кроме того, они поддерживают операции, приведенные в табл. 3.7.

  • Операторы сравнения <, <=, > и >=, позволяющие сравнить относительные позиции двух итераторов.

  • Операторы сложения и вычитания (+, +=, - и -=), обеспечивающие арифметические действия между итератором и целочисленным значением. В результате получается итератор, перемещенный в контейнере вперед (или назад) на соответствующее количество элементов.

  • Оператор вычитания (-), применяемый к двум итераторам, позволяет получить дистанцию между двумя итераторами.

  • Оператор индексирования (iter[n]), равнозначный выражению *(iter + n).

Итератор прямого доступа необходим алгоритму sort(). Итераторы контейнеров array, deque, string и vector являются итераторами прямого доступа, подобно указателям массива.

Упражнения раздела 10.5.1

Упражнение 10.38. Перечислите пять категорий итераторов и операции, которые каждый из них поддерживает.

Упражнение 10.39. Итератором какой категории обладает список? А вектор?

Упражнение 10.40. Итераторы какой категории нужны алгоритму copy()? А алгоритмам reverse() и unique()?

10.5.2. Параметрическая схема алгоритмов

Эта классификация алгоритмов основана на соглашениях об именах параметров. Понимание этих соглашений поможет в изучении новых алгоритмов: зная, что означает имя данного параметра, можно догадаться, какие операции выполняет соответствующий алгоритм. Большинство алгоритмов получают параметры в одной из четырех форм:

алг(beg, end, другие параметры);

алг(beg, end, dest, другие параметры);

алг(beg, end, beg2, другие параметры);

алг(beg, end, beg2, end2, другие параметры);

где алг — это имя алгоритма, а параметры beg и end обозначают исходный диапазон элементов, с которыми работает алгоритм. Хотя почти все алгоритмы получают исходный диапазон, присутствие других параметров зависит от выполняемых действий. Как правило, остальные параметры, dest, beg2 и end2, также являются итераторами. Кроме них, некоторые алгоритмы получают дополнительные параметры, не являющиеся итераторами.

Алгоритмы с одним итератором назначения

Параметр dest (destination — назначение) — это итератор, обозначающий получателя, используемого для хранения результата. Алгоритмы подразумевают, что способны безопасно записать в последовательность назначения столько элементов, сколько необходимо.

Алгоритмы, осуществляющие запись по итератору вывода, подразумевают, что получатель достаточно велик для содержания вывода.

Если dest является итератором контейнера, алгоритм записывает свой результат в уже существующие элементы контейнера. Как правило, итератор dest связан с итератором вставки (см. раздел 10.4.1) или итератором ostream_iterator (см. раздел 10.4.2). Итератор вставки добавляет новые элементы в контейнер, гарантируя, таким образом, достаточную емкость. Итератор ostream_iterator осуществляет запись в поток вывода, а следовательно, тоже не создает никаких проблем независимо от количества записываемых элементов.

Алгоритмы с двумя итераторами, указывающими исходную последовательность

Алгоритмы, получающие один параметр (beg2) или два параметра (beg2 и end2), используют эти итераторы для обозначения второго исходного диапазона. Как правило, для выполнения необходимых действий эти алгоритмы используют элементы второго диапазона вместе с элементами исходного.

Когда алгоритм получает параметры beg2 и end2, эти итераторы обозначают весь второй диапазон. Такой алгоритм получает два полностью определенных диапазона: исходный диапазон, обозначенный итераторами [beg, end), а также второй, исходный диапазон, обозначенный итераторами [beg2, end2).

Алгоритмы, получающие только итератор beg2 (но не end2), рассматривают итератор beg2 как указывающий на первый элемент во втором исходном диапазоне. Конец этого диапазона не определен. В этом случае алгоритмы подразумевают, что диапазон, начинающийся с элемента, указанного итератором beg2, имеет, по крайней мере, такой же размер, что и диапазон, обозначенный итераторами beg и end.

Алгоритмы, получающие один параметр beg2, подразумевают, что последовательность, начинающаяся с элемента, указанного итератором beg2, имеет такой же размер, как и диапазон, обозначенный итераторами beg и end.

10.5.3. Соглашения об именовании алгоритмов

Кроме соглашений об именовании параметров, алгоритмы также имеют набор однозначных соглашений об именовании перегруженных версий. Эти соглашения учитывают то, как предоставляется оператор, используемый вместо принятого по умолчанию оператора < или ==, а также то, используется ли алгоритм для исходной последовательности или отдельного получателя.

Некоторые алгоритмы используют перегруженные версии для передачи предиката

Как правило, перегружаются алгоритмы, которые получают предикат для использования вместо оператора < или == и не получающие других аргументов. Одна версия функции использует для сравнения элементов оператор типа элемента, а вторая получает дополнительный параметр, являющийся предикатом, используемым вместо оператора < или ==:

unique(beg, end); // использует для сравнения элементов оператор ==

unique(beg, end, comp); // использует для сравнения элементов

                        // предикат comp

Оба вызова переупорядочивают переданную последовательность, удаляя смежные повторяющиеся элементы. Первая версия для проверки на совпадение использует оператор == типа элемента, а вторая вызывает для этого предикат comp. Поскольку эти версии функции отличаются количеством аргументов, нет никакой неоднозначности (см. раздел 6.4) относительно версии вызываемой функции.

Алгоритмы с версиями _if

У алгоритмов, получающих значение элемента, обычно есть вторая (не перегруженная) версия, получающая предикат (см. раздел 10.3.1) вместо значения. Получающие предикат алгоритмы имеют суффикс _if: