10.4.3. Реверсивные итераторы
Реверсивный итератор (reverse iterator) перебирает контейнер в обратном направлении, т.е. от последнего элемента к первому. Реверсивный итератор инвертирует смысл инкремента (и декремента): оператор ++it переводит реверсивный итератор на предыдущий элемент, а оператор --it — на следующий.
Реверсивные итераторы есть у всех контейнеров, кроме forward_list. Для получения реверсивного итератора используют функции-члены rbegin(), rend(), crbegin() и crend(). Они возвращают реверсивные итераторы на последний элемент в контейнере и на "следующий" (т.е. предыдущий) перед началом контейнера. Подобно обычным итераторам, существуют константные и неконстантные реверсивные итераторы.
Взаимное положение этих четырех итераторов на гипотетическом векторе vec представлено на рис. 10.1.
Рис. 10.1. Взаимное положение итераторов, возвращаемых функциями begin()/cend() и rbegin()/crend()
Рассмотрим, например, следующий цикл, выводящий элементы вектора vec в обратном порядке:
vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
// реверсивный итератор вектора (от конца к началу)
for (auto r_iter = vec.crbegin(); // связывает r_iter с последним
// элементом
r_iter != vec.crend(); // crend ссылается на 1 элемент
// перед 1-м
++r_iter) // декремент итератора на один элемент
cout << *r_iter << endl; // выводит 9, 8, 7, ... 0
Хотя смысл оператора декремента реверсивного итератора может показаться неправильным, этот оператор позволяет применять для обработки контейнера стандартные алгоритмы. Например, передав функции sort() два реверсивных итератора, вектор можно отсортировать в порядке убывания.
sort(vec.begin(), vec.end()); // сортирует вектор vec
// в "нормальном" порядке
// обратная сортировка: самый маленький элемент располагается
// в конце вектора vec
sort(vec.rbegin(), vec.rend());
Реверсивным итераторам необходим оператор декремента
Нет ничего удивительного в том, что реверсивный итератор можно создать только из такого класса итератора, для которого определены операторы -- и ++. В конце концов, задача реверсивного итератора заключается в переборе последовательности назад. Кроме контейнера forward_list, итераторы всех стандартных контейнеров поддерживают как инкремент, так и декремент. Однако потоковые итераторы к ним не относятся, поскольку невозможно перемещать поток в обратном направлении. Следовательно, создать из потокового итератора реверсивный итератор невозможно.
Предположим, что существует объект line класса string(строка), содержащий разделяемый запятыми список слов. Используя функцию find(), можно отобразить, например, первое слово строки line:
// найти первый элемент в списке, разделенном запятыми
auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;
Если в строке line есть запятая, итератор comma будет указывать на нее, в противном случае он будет равен итератору, возвращаемому функцией line.cend(). При выводе содержимого строки от позиции line.cbegin() до позиции comma будут отображены символы от начала до запятой или вся строка, если запятых в ней нет.
Но если понадобится последнее слово в списке, то вместо обычных можно использовать реверсивные итераторы:
// найти последний элемент в списке, разделенном запятыми
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 в обратном порядке.