Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в C++.
Однако есть и классическая, более распространённая техника для борьбы с циклами — использование итераторов и диапазонов для ленивых операций над последовательностями. Всё это уже сто лет есть в Бусте и других сторонних библиотеках (к примеру, range-v3) и постепенно просачивается в стандартную библиотеку.
Хотя, в некотором смысле, и в стандартной библиотеке ленивые итераторы уже есть давно (см. std::reverse_iterator).Данная публикация — это краткий ликбез о том, что такое ленивые итераторы и диапазоны, зачем они нужны и как ими пользоваться.
Содержание
Итератор
Начнём с простого. Что вообще такое итератор?
Понять суть концепции довольно легко. Сам по себе итератор — это обобщение указателя. При этом главное, что нужно знать — это два способа взаимодействия с итератором:
- Продвижение (например,
++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++.