главе:
□ построение собственного итерабельного диапазона данных;
□ обеспечение совместимости ваших итераторов с категориями итераторов STL;
□ использование оболочек для итераторов для заполнения обобщенных структур данных;
□ реализация алгоритмов с помощью итераторов;
□ перебор (итерирование) в обратную сторону с применением обратных адаптеров для итераторов;
□ завершение перебора диапазонов данных с использованием ограничителей;
□ автоматическая проверка кода итератора с помощью проверяемых итераторов;
□ создание собственного адаптера для итераторов-упаковщиков.
Введение
Итераторы — крайне важная концепция языка С++. Библиотека STL создавалась максимально гибкой и обобщенной, а итераторы способствуют этому. К сожалению, иногда применять их несколько утомительно, и многие новички избегают их и возвращаются к стилю программирования, свойственному языку С. Программист, который избегает использования итераторов, по сути, отказывается от половины потенциала библиотеки STL. В данной главе мы рассмотрим итераторы, постаравшись разобраться в их достоинствах и недостатках. Надеюсь, показанные примеры помогут вам понять основные принципы работы с итераторами.
Многие классы-контейнеры, а также массивы в стиле С так или иначе содержат диапазон неких элементов. Для выполнения множества повседневных задач, связанных с обработкой больших объемов данных, не нужно знать, как эти данные были получены. Однако если у нас есть, например, массив целых чисел и список, содержащий целые числа, то следует воспользоваться двумя разными алгоритмами, представленными ниже.
□ Один алгоритм, который работает с массивом, проверяя его размер и суммируя все его члены, выглядит так:
int sum {0};
for (size_t i {0}; i < array_size; ++i) { sum += array[i]; }
□ Другой алгоритм, который работает со связанным списком и итерирует по нему до конца, выглядит следующим образом:
int sum {0};
while (list_node != nullptr) {
sum += list_node->value; list_node = list_node->next;
}
Оба алгоритма суммируют целые числа, но какая часть введенных нами символов непосредственно связана с решением задачи? Работает ли какой-нибудь из этих алгоритмов с другими видами структур данных, например с std::map, или нужно реализовывать еще одну версию алгоритма суммирования? Отсутствие итераторов приведет к нелепым решениям.
Только с помощью итераторов можно реализовать этот алгоритм в обобщенном виде:
int sum {0};
for (int i : array_or_vector_or_map_or_list) { sum += i; }
Это красивое и короткое выражение, названное «основанный на диапазоне цикл for», существует еще со времен С++11. Оно представляет собой лишь синтаксический сахар, который развертывается в нечто похожее на следующий код:
{
auto && range = array_or_vector_or_map_or_list;
auto begin = std::begin( range);
auto end = std::end( range);
for ( ; begin != end; ++ begin) {
int i = * begin;
sum += i;
}
}
Такие циклы хорошо знакомы всем, кто уже работал с итераторами, но кажутся черной магией для тех, кто еще этого не делал. Представьте, что наш вектор, содержащий целые числа, выглядит следующим образом (рис. 3.1).
Команда std::begin(vector) аналогична команде vector.begin(), она возвращает итератор, который указывает на первый элемент (1). Команда std::end(vector) аналогична команде vector.end(), она возвращает итератор, указывающий на элемент, стоящий за последним элементом (5).
На каждой итерации цикл проверяет, равен ли начальный итератор конечному. Если это не так, то мы разыменовываем начальный итератор и получаем доступ к числовому значению, на которое он указывает. Далее выполняем операцию инкремента для итератора, повторяем сравнение с конечным итератором и т.д. В этот момент полезно прочесть код цикла снова, представляя, что итераторы — обычные указатели, взятые из языка С. Фактически такие указатели тоже являются итераторами.
Категории итераторов
Существует несколько категорий итераторов, каждая из которых имеет разные ограничения. Их несложно запомнить, однако имейте в виду: возможности, требуемые одной категорией, унаследованы из другой, более мощной. Вся суть категорий итераторов заключается в том, что если при реализации алгоритма вы знаете, с каким именно итератором будете работать, то сможете реализовать оптимизированную версию. Таким образом, программисту достаточно просто выразить свое намерение, а компилятор выберет оптимальную реализацию для поставленной задачи.
Рассмотрим их в правильном порядке (рис. 3.2).
Итераторы ввода
Могут быть разыменованы только для того, чтобы прочесть значение, на которое указывают. При их инкрементировании последнее значение, на которое они указывают, становится недействительным во время данной операции, а значит, вы не можете итерировать по такому диапазону данных несколько раз. Примером итератора этой категории является std::istream_iterator.
Однонаправленные итераторы
Аналогичны итераторам ввода, но отличаются тем, что по диапазонам данных, которые они представляют, вы можете проитерировать несколько раз. В качестве примера такого итератора приведем std::forward_list. По такому списку можно проитерировать только вперед, но не назад, однако это можно сделать требуемое количество раз.
Двунаправленные итераторы
Как следует из названия, их можно инкрементировать и декрементировать, что позволяет итерировать вперед и назад. Эту возможность, например, поддерживают итераторы для контейнеров std::list, std::set и std::map.
Итераторы с произвольным доступом
Позволяют перескакивать через несколько значений сразу вместо того, чтобы двигаться пошагово. Примером таких итераторов являются итераторы для контейнеров std::vector и std::deque.
Непрерывные итераторы
Соответствуют всем указанным выше требованиям, но при этом необходимо, чтобы данные, по которым выполняется итерирование, находились в непрерывной памяти, как, например, в массиве std::vector.
Итераторы вывода
Вынесены в отдельную категорию. Причина такова: итератор может быть чистым итератором вывода, который можно только инкрементировать и использовать для записи данных в указываемое им место. При выполнении операции чтения значение будет неопределенным.
Изменяемые итераторы
Если итератор является итератором вывода, а также состоит в какой-то другой категории, то называется изменяемым. С его помощью можно считывать и записывать данные. При получении из неконстантного экземпляра контейнера итератор, как правило, будет состоять именно в этой категории.
Создаем собственный итерабельный диапазон данных
Мы уже знаем, что итераторы в некоторой степени представляют собой стандартный интерфейс для выполнения перебора во всех видах контейнеров. Нужно только реализовать оператор префиксного инкремента ++, оператор разыменования * и оператор сравнения объектов ==, и получится примитивный итератор, подходящий для работы с циклом for, основанным на диапазоне, который появился в C++11.
Чтобы немного освоиться с итераторами, рассмотрим пример реализации одного из них, который просто генерирует диапазон чисел
