10.5.1. Пять категорий итераторов

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

Таким образом, итераторы можно классифицировать на основании набора функций, которыми они обладают, а категории формируют своего рода иерархию. За исключением итераторов вывода, итераторы более высокой категории поддерживают все функции итераторов более низких категорий.

Стандарт определяет минимальную категорию для каждого параметра итератора обобщенных и числовых алгоритмов. Например, алгоритм find(), реализующий перебор последовательности только для чтения и в одном направлении, минимально требует только итератор ввода. Алгоритму replace() требуется два итератора, являющихся, по крайней мере, прямыми итераторами. Аналогично алгоритм replace_copy() требует прямые итераторы для своих первых двух итераторов. Его третий итератор, представляющий назначение, должен, по крайней мере, быть итератором вывода и т.д. Итератор для каждого параметра должен обладать не меньшим набором параметров, чем предусмотренный минимум. Передача итератора с меньшими возможностями недопустима.

Категории итераторов

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

• Операторы равенства и неравенства (==, !=), используемые для сравнения двух итераторов.

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

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

• Оператор стрелки (->), равнозначный выражению (*it).member. То есть обращение к значению итератора и доступ к члену класса объекта.

Итераторы ввода могут быть использованы только последовательно. Гарантирована допустимость инкремента *it++, но приращение итератора ввода может сделать недопустимыми все другие итераторы в потоке. В результате нет никакой гарантии того, что можно сохранить состояние итератора ввода и исследовать элемент с его помощью. Поэтому итераторы ввода можно использовать только для однопроходных алгоритмов. Алгоритмам find() и accumulate() требуются итераторы ввода, а итератор istream_iterator — имеет тип итератора ввода.

Итератор вывода (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()?