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

Но если понадобится последнее слово в списке, то вместо обычных можно использовать реверсивные итераторы:

// найти последний элемент в списке, разделенном запятыми

auto rcomma = find(line.crbegin(), line.crend(), ',');

Поскольку функции find() в качестве аргументов передаются результаты выполнения функций crbegin() и crend(), поиск начинается с последнего символа в строке line в обратном порядке. По завершении поиска, если запятая найдена, итератор rcomma будет указывать на последнюю запятую в строке, т.е. первую запятую с конца. Если запятой нет, итератор rcomma будет равен итератору, возвращаемому функцией line.crend().

Весьма интересна та часть, в которой осуществляется вывод найденного слова. Попытка прямого вывода создает несколько странный результат:

// ошибка: создаст слово в обратном порядке

cout << string(line.crbegin(), rcomma) << endl;

Например, если введена строка "FIRST,MIDDLE,LAST", будет получен результат "TSAL"!

Эта проблема проиллюстрирована на рис. 10.2. Здесь реверсивные итераторы используются для перебора строки в обратном порядке. Поэтому оператор вывода выводит строку line назад, начиная от crbegin(). Вместо этого следует выводить строку от rcomma и до конца. Но итератор rcomma нельзя использовать непосредственно, так как это реверсивный итератор, обеспечивающий перебор от конца к началу. Поэтому необходимо преобразовать его назад в обычный итератор, перебирающий строку вперед. Для преобразования итератора rcomma можно применить функцию-член base(), которой обладает каждый реверсивный итератор.

// ok: получить прямой итератор и читать до конца строки

cout << string(rcomma.base(), line.cend()) << endl;

С учетом того, что введены те же данные, в результате отобразится слово "LAST", как и ожидалось.

Рис. 20.2. Отношения между реверсивными и обычными итераторами

Объекты, представленные на рис. 10.2, наглядно иллюстрируют взаимоотношения между обычными и реверсивными итераторами. Например, итераторы rcomma и возвращаемый функцией rcomma.base() указывают на разные элементы, так же как и возвращаемые функциями line.crbegin() и line.cend(). Эти различия вполне обоснованны: они позволяют гарантировать возможность одинаковой обработки диапазона элементов при перемещении как вперед, так и назад.

С технической точки зрения отношения между обычными и реверсивными итераторами приспособлены к свойствам диапазона, включающего левый элемент (см. раздел 9.2.1). Дело в том, что [line.crbegin(), rcomma) и [rcomma.base(), line.cend()) ссылаются на тот же элемент в строке line. Для этого rcomma и rcomma.base() должны возвращать соседние позиции, а не ту же позицию, как функции crbegin() и cend().

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

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

Упражнение 10.34. Используйте итератор reverse_iterator для вывода содержимого вектора в обратном порядке.

Упражнение 10.35. Теперь отобразите элементы в обратном порядке, используя обычные итераторы.

Упражнение 10.36. Используйте функцию find() для поиска в списке целых чисел последнего элемента со значением 0.

Упражнение 10.37. С учетом того, что вектор содержит 10 элементов, скопируйте в список диапазон его элементов от позиции 3 до позиции 7 в обратном порядке.

10.5. Структура обобщенных алгоритмов

Фундаментальное свойство любого алгоритма — это список функциональных возможностей, которые он требует от своего итератора (итераторов). Некоторые алгоритмы, например find(), требуют только возможности получить доступ к элементу через итератор, прирастить итератор и сравнить два итератора на равенство. Другие, такие как sort(), требуют возможности читать, писать и произвольно обращаться к элементам. По своим функциональным возможностям, обязательным для алгоритмов, итераторы группируются в пять категорий (iterator categories), перечисленных в табл. 10.5. Каждый алгоритм определяет, итератор какого вида следует предоставить для каждого из его параметров.

Таблица 10.5. Категории итераторов

Итератор ввода Обеспечивает чтение, но не запись; поддерживает только инкремент Итератор вывода Обеспечивает запись, но не чтение; поддерживает только инкремент Прямой итератор Обеспечивает чтение и запись; поддерживает только инкремент Двунаправленный итератор Обеспечивает чтение и запись; поддерживает инкремент и декремент Итератор произвольного доступа Обеспечивает чтение и запись; поддерживает все арифметические операции итераторов

Второй способ классификации алгоритмов (приведенный в начале этой главы) основан на том, читают ли они элементы, пишут или переупорядочивают их в последовательности. В приложении А все алгоритмы перечислены согласно этой классификации.

Алгоритмы имеют также ряд общих соглашений по передаче параметров и соглашений об именовании, рассматриваемых после категорий итераторов.

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

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

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

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

Большинство компиляторов не заметит ошибки передачи алгоритму итератора неправильный категории.

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

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

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

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

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

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

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