Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в C++.

Однако есть и классическая, более распространённая техника для борьбы с циклами — использование итераторов и диапазонов для ленивых операций над последовательностями. Всё это уже сто лет есть в Бусте и других сторонних библиотеках (к примеру, range-v3) и постепенно просачивается в стандартную библиотеку.

Хотя, в некотором смысле, и в стандартной библиотеке ленивые итераторы уже есть давно (см. std::reverse_iterator).

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

Содержание

Итератор
Ленивость
1. Transform Iterator
2. Filter Iterator
Ленивые диапазоны
1. Transform Range
2. Stride
Компоновка
Суть итераторов и диапазонов
Ссылки

Итератор

Начнём с простого. Что вообще такое итератор?

Итератор

Понять суть концепции довольно легко. Сам по себе итератор — это обобщение указателя. При этом главное, что нужно знать — это два способа взаимодействия с итератором:

Продвижение (например, ++i или i + n);
Разыменование (*i).

Операции с итератором

И в эти взаимодействия мы можем внедряться и переопределять их так, как нам нужно.

Ленивость

Внедрение в операции над диапазонами может быть сколь угодно хитрым и сложным (простые примеры я привёл ниже). Ленивость же состоит в том, что нет никаких промежуточных результатов. Все вычисления происходят только тогда, когда вызываются операции разыменования или продвижения.

Определение 1. Итератор e достижим из итератора b, если существует схема f продвижения итератора b такая, что f(b) = e.

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

Достижимость

В этом и состоит ленивость — мы получили новую последовательность без изменений в старой. Мы не трогали хранимые объекты, а только переопределили способ их отображения и обхода по ним.

Transform Iterator

Простой пример внедрения в операцию разыменования — это boost::transform_iterator.

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

Преобразующий итератор

Таким образом, каждому итератору i типа I мы поставили в соответствие итератор j типа J такой, что *j = f(*i).

auto v = std::vector{1, 2, 3, 4};
//                   2  4  6  8
auto i = v.begin();
auto t = boost::make_transform_iterator(i, [] (auto x) {return x * 2;});

assert(*t == 2);
++t;
assert(*t == 4);
...

Filter Iterator

Пример внедрения в продвижение — это boost::filter_iterator.

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

Фильтрующий итератор

Таким образом, мы "выбросили" из исходной последовательности итераторы i такие, что p(*i) == false, и в результирующей последовательности, для каждого итератора j типа J выполняется p(*j) == true.

auto v = std::vector{1, 2, 3, 4};
//                      ^     ^
auto i = v.begin();
auto f = boost::make_filter_iterator(i, [] (auto x) {return x % 2 == 0;});

assert(*i == 2);
++i;
assert(*i == 4);

Ленивые диапазоны

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

При этом диапазон — это уже более сложная конструкция, и у него другой интерфейс, похожий на интерфейс контейнеров:

Взятие итераторов на начало и конец (r.begin(), r.end());
Взятие первого элемента диапазона (r.front());
Проверка на пустоту (r.empty()).

Разница только в том, что диапазон не владеет элементами, которые он задаёт. Хотя бы потому что канонический диапазон — это просто пара итераторов (к примеру, std::equal_range).

Важно отметить, что диапазон принято задавать полуинтервалом [b, e). Это значит, что итератор-начало b указывает на первый элемент последовательности, а итератор-конец e указывает на элемент после последнего. Таким образом, когда мы приходим в итератор-конец, мы точно знаем, что последовательность закончилась.

Диапазон

Transform Range

На основе преобразующих итераторов можно собрать диапазон (см. boost::iterator_range).

auto v = std::vector{...};
auto l = [] (auto x) {return x * x;};
auto tb = boost::make_transform_iterator(v.begin(), l);
auto te = boost::make_transform_iterator(v.end(), l);

auto tr = boost::make_iterator_range(tb, te);

for (auto x: tr)
{
    ...
}

Или проще (см. boost::transformed):

auto v = std::vector{...};
auto tr = boost::adaptors::transform(v, [] (auto x) {return x * x;});
for (auto x: tr)
{
    ...
}

В C++20 это std::transform_view:

auto v = std::vector{...};
auto tr = std::ranges::views::transform(v, [] (auto x) {return x * x;});
for (auto x: tr)
{
    ...
}

Stride

Другой пример ленивого диапазона — это boost::strided.

Он оборачивает исходный диапазон так, что в новом диапазоне остаются только кратные позиции исходного диапазона.

Шагающий диапазон

auto v = std::vector{1, 2, 3, 4};
//                   ^     ^
auto s = boost::adaptors::strided(v, 2);

assert(s.front() == 1);
s.advance_begin();
assert(s.front() == 3);

Компоновка

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

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

возвести их в квадрат,
взять только каждый четвёртый элемент,
и оставить только чётные числа,

то можно это сделать так:

auto v = std::vector{...};
auto r = v | transformed([] (auto x) {return x * x;})
           | strided(4)
           | filtered([] (auto x) {return x % 2 == 0;});

Или, в C++20:

auto v = std::vector{...};
auto r = v | std::views::transformed([] (auto x) {return x * x;})
//         | strided(4) // В C++20 такого нет.
           | std::views::filtered([] (auto x) {return x % 2 == 0;});

Ещё раз хочу подчеркнуть, что этот код не производит никаких вычислений. Он только сохраняет "схемы" работы с диапазоном, а настоящие вычисления будут происходить только во время продвижения или разыменования обёрнутого итератора.

Суть итераторов и диапазонов

Помимо C++, в некоторых языках программировани также существует концепция под названием "итератор", но эта концепция зачастую имеет какой-то свой, альтернативный смысл.
К примеру, "итераторы" в языках Java и C# знают свой предел. С точки зрения языка C++ это, скорее, диапазоны.

В C++ итератор — это именно обобщение указателя. По сути указатель — это самый сильный (или наиболее конкретный) итератор, причём иерархия следующая:

Однопроходный итератор (input iterator);
Однонаправленный итератор (forward iterator);
Двунаправленный итератор (bidirectional iterator);
Итератор произвольного доступа (random access iterator);
Непрерывный итератор (contiguous iterator);
Указатель.

Диапазон же можно рассматривать именно как пару итераторов (даже если это на самом деле не так). Диапазон уже знает, где у него конец, может накладывать дополнительную логику на операции с итераторами и т.д. Также диапазон может быть сконвертирован обратно в итераторы (потому что диапазон — это пара итераторов, как уже было сказано выше).

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

Один из примеров создания сложной операции над диапазонами я привёл в статье Ленивые операции над множествами в C++.

Ссылки

Ленивые итераторы и диапазоны в C++