Выбрать главу

Глава 3

Итераторы

В этой главе:

□ построение собственного итерабельного диапазона данных;

□ обеспечение совместимости ваших итераторов с категориями итераторов 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).

На каждой итерации цикл проверяет, равен ли начальный итератор конечному. Если это не так, то мы разыменовываем начальный итератор и получаем доступ к числовому значению, на которое он указывает. Далее выполняем операцию инкремента для итератора, повторяем сравнение с конечным итератором и т.д. В этот момент полезно прочесть код цикла снова, представляя, что итераторы — обычные указатели, взятые из языка С. Фактически такие указатели тоже являются итераторами.

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

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

полную версию книги