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


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


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

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



Содержание


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


Итератор


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


Итератор


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


  • Продвижение (например, ++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++.



Ссылки