Ленивые вычисления

"Кто ни разу не ошибался в индексировании цикла, пусть первый бросит в деструкторе исключение."

Древняя мудрость

Циклы ужасны. Циклы сложно читать вместо того, чтобы сразу понять намерение автора, приходится сначала вникать в код, чтобы понять, что именно он делает. В цикле легко ошибиться с индексированием и переопределить индекс цикла во вложенном цикле. Циклы сложно поддерживать, исправлять в случае ошибок, сложно вносить текущие изменения, и т.д. и т.п.

В конце концов, это просто некрасиво.

Человечество издревле пытается упростить написание циклов. Вначале программисты подметили часто повторяющиеся циклы и выделили их в отдельные функции. Затем они придумали ленивые итераторы, а потом и диапазоны. И каждая из этих идей была прорывом. Но, несмотря на это, идеал до сих пор не достигнут, и люди продолжают искать способы улучшить свой код.

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

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

Содержание

1. Существующие модели
2. Базовые понятия
   
   1. Определение 1: свёртка
   2. Определение 2: ядро свёртки
3. Идеология
   
   1. Факт 1: каждый цикл можно представить в виде свёртки
   2. Факт 2: большинство циклов расладываются на простые составляющие
   3. Факт 3: каждую свёртку можно представить в виде автомата
   4. Факт 4: автоматы комбинируются
   5. Снова к свёртке
4. Я птичка, мне такое сложно, можно я сразу код посмотрю?
   
   1. Простой пример
   2. constexpr
5. Многопоточность
6. Сравнительная таблица
7. Ссылки

Существующие модели

Основные на текущий момент способы избавления от циклов это алгоритмы из стандартной библиотеки и ленивые итераторы и диапазоны из библиотек Boost.Iterator, Boost.Range и range-v3.

range-v3 частично попали в стандартную библиотеку C++20, но, во-первых, попали они туда в достаточно усечённом виде, а во-вторых, соответствующих реализаций на текущий момент пока нет.

Стандартные алгоритмы прекрасны, и помогают избаваться от циклов, но, к сожалению, только в самых простых случаях, посколько несколько таких алгоритмов невозможно скомбинировать в единое вычисление. Для каждого шага придётся хранить промежуточный результат. А это и перерасход по памяти, и сложности с выводом типов для промежуточных результатов, то есть усложнение кода.

Именно из-за этого появились ленивые итераторы и диапазоны в сторонних библиотеках, а в C++17 появились гибриды семейства std::transform_reduce.

Ленивые итераторы и диапазоны решают многие проблемы. Но они сами не лишены своих собственных проблем. В частности, поскольку они отделены от схемы вычислений (они определяют только операции над отдельными элементами последовательности), их сложно параллелить. А стандартные алгоритмы уже с C++17 имеют параллельные версии, способные более эффективно использовать многоядерные архитектуры.

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

Базовые понятия

Для того, чтобы двинуться далее, необходимо разобраться с тем, что такое свёртка.

Определение 1: свёртка

Свёртка это вычислительный процесс, производимый над некоторой последовательностью значений по правилу, задаваемому ядром свёртки.

Результат свёртки значение, полученное последовательным применением ядра свёртки к текущему значению и очередному элементу последовательности.

Определение 2: ядро свёртки

Ядро свёртки это действие, производимое на каждом шаге свёртки. Применяется к текущему значению свёртки и очередному элементу последовательности.

На этом рисунке изображена свёртка последовательности с ядром и начальным значением . результат свёртки.

В стандартной библиотеке свёртка представлена алгоритмами std::accumulate и std::reduce.

Идеология

Итак, для того, чтобы понять основную идею данного подхода, нужно обратить внимание на несколько известных фактов.

Факт 1: каждый цикл можно представить в виде свёртки

И действительно:

1. Контекст программы перед началом цикла начальное значение;
2. Набор индексов, контейнер, диапазон и т.п. последовательность элементов;
3. Итерация цикла применение двуместной операции (ядра свёртки) к текущему значению и очередному элементу последовательности, в результате чего текущее значение изменяется.

auto v = 0;                   // Начальное значение: v_0for (auto i = 0; i < 10; ++i) // Последовательность: [x_0, x_1, ...]{    v = f(v, i);              // Двуместная операция, изменяющая                              // значение: v_{i + 1} = f(v_i, x_i)}

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

Пример 1: отображение через свёртку

template <ForwardIterator I, OutputIterator J, UnaryFunction F>J transform (I begin, I end, J result, F f){    // Начальное значение  это выходной итератор.    auto initial_value = result;    // Ядро свёртки.    auto binary_op =        [] (auto iterator, auto next_element)        {            // Записываем в текущий итератор результат отображения...            *iterator = f(next_element);            // ... и возвращаем продвинутый итератор.            return ++iterator;        };    // Свёртка.    return accumulate(begin, end, initial_value, binary_op);}

Пример 2: фильтрация через свёртку

template <ForwardIterator I, OutputIterator J, UnaryPredicate P>J copy_if (I begin, I end, J result, P p){    // Начальное значение.    auto initial_value = result;    // Ядро свёртки.    auto binary_op =        [p] (auto iterator, auto next_element)        {            if (p(next_element))            {                *iterator = next_element;                ++iterator;            }            return iterator;        };    // Свёртка.    return accumulate(begin, end, initial_value, binary_op);}

Аналогичным образом выражаются и все остальные последовательные алгоритмы. Любознательный читатель может проделать это в качестве упражнения.

Факт 2: большинство циклов расладываются на простые составляющие

Если присмотреться, то станет понятно, что большинство циклов типовые. Они раскладываются на простые составляющие:

• Преобразование;
• Фильтрация;
• Группировка;
• Подсчёт;
• Суммирование;
• Запись в массив;
• ...
• и т.д.

Это значит, что нужно подобрать достаточно выразительный базис операций, чтобы их комбинациями покрыть подавляющее большинство возможных циклов, а также научиться легко и удобно составлять эти комбинации с точки зрения программного кода.

Факт 3: каждую свёртку можно представить в виде автомата

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

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

Важно:

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

Кроме того, наш автомат может обладать памятью.

Пример 1: автомат для отображения

Например, так будет выглядеть автомат для отображения (transform, или map в функциональном программировании).

Здесь входной символ, функция преобразования.

Данный автомат имеет одно состояние и один переход. Каждый входной символ он преобразует с помощью функции , и результат этого преобразования подаёт на выход. После этого возвращается в исходное состояние.

Пример 2: автомат для фильтрации

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

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

Факт 4: автоматы комбинируются

Если у автомата есть выход, то, очевидно, этот выход можно подать на вход другому автомату.

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

Снова к свёртке

Чтобы получить нужную нам свёртку, в конец цепочки мы поставим автомат, который представляет собой ядро свёртки.

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

Итак, мы разложили цикл на простые составляющие и представили с помощью свёртки. В теории всё прекрасно, но как же это будет выглядеть в коде?

Код

На основе изложенных выше идей разработана библиотека Проксима.

Простой пример

#include <proxima/compose.hpp>#include <proxima/kernel/sum.hpp>#include <proxima/reduce.hpp>#include <proxima/transducer/stride.hpp>#include <proxima/transducer/take_while.hpp>#include <proxima/transducer/transform.hpp>#include <cassert>int main (){    const int items[] = {1, 2, 3, 4, 5};    const auto kernel =        proxima::compose        (            proxima::transform([] (auto x) {return x * x;}),   // 1. Каждый элемент возведён в квадрат;            proxima::stride(2),                                // 2. Берутся только элементы с номерами,                                                               //    кратными двойке (нумерация с нуля);            proxima::take_while([] (auto x) {return x < 10;}), // 3. Элементы берутся до тех пор, пока                                                               //    они меньше десяти;            proxima::sum                                       // 4. Результат суммируется.        );    const auto x = proxima::reduce(items, kernel);    assert(x == 10); // 1 * 1 + 3 * 3}

constexpr

Можно отметить, что код из примера может быть выполнен на этапе компиляции:

#include <proxima/compose.hpp>#include <proxima/kernel/sum.hpp>#include <proxima/reduce.hpp>#include <proxima/transducer/stride.hpp>#include <proxima/transducer/take_while.hpp>#include <proxima/transducer/transform.hpp>int main (){    constexpr int items[] = {1, 2, 3, 4, 5};    constexpr auto kernel =        proxima::compose        (            proxima::transform([] (auto x) {return x * x;}),   // 1. Каждый элемент возведён в квадрат;            proxima::stride(2),                                // 2. Берутся только элементы с номерами,                                                               //    кратными двойке (нумерация с нуля);            proxima::take_while([] (auto x) {return x < 10;}), // 3. Элементы берутся до тех пор, пока                                                               //    они меньше десяти;            proxima::sum                                       // 4. Результат суммируется.        );    constexpr auto x = proxima::reduce(items, kernel);    static_assert(x == 10); // 1 * 1 + 3 * 3}

Большая часть Проксимы может быть выполнена на этапе компиляции.

Многопоточность

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

В Проксиме существует механизм, с помощью которого очень легко распараллеливать вычисления. Это делается с помощью фиктивного преобразователя pipe, который выполняет роль "разделителя потоков":

proxima::reduce(values,    proxima::compose    (        proxima::for_each(hard_work), // | Поток 1                                      // ----------        proxima::pipe,                //            Разделитель потоков                                      // ----------        proxima::for_each(hard_work), // | Поток 2                                      // ----------        proxima::pipe,                //            Разделитель потоков                                      // ----------        proxima::for_each(hard_work), // | Поток 3        proxima::sum                  // | Поток 3    ));

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

Чтобы показать эффективность такого разбиения, рассмотрим пример (полный код лежит на Гитлабе).

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

auto hard_work (std::int32_t time_to_sleep){    std::this_thread::sleep_for(std::chrono::microseconds(time_to_sleep));}const auto proxima_crunch_parallel =    [] (auto b, auto e)    {        return            proxima::reduce(b, e,                proxima::compose                (                    proxima::for_each(hard_work),                    proxima::pipe,                    proxima::for_each(hard_work),                    proxima::pipe,                    proxima::for_each(hard_work),                    proxima::sum                ));    };const auto proxima_crunch =    [] (auto b, auto e)    {        return            proxima::reduce(b, e,                proxima::compose                (                    proxima::for_each(hard_work),                    proxima::for_each(hard_work),                    proxima::for_each(hard_work),                    proxima::sum                ));    };const auto loop_crunch =    [] (auto b, auto e)    {        auto sum = typename decltype(b)::value_type{0};        while (b != e)        {            hard_work(*b);            hard_work(*b);            hard_work(*b);            sum += *b;            ++b;        }        return sum;    };

Если сгенерировать 1000 случайных засыпаний в диапазоне от 10 до 20 микросекунд, то получим следующую картину (показано время работы соответствующего обработчика чем меньше, тем лучше):

proxima_crunch_parallel | 0.0403945proxima_crunch          | 0.100419loop_crunch             | 0.103092

И чем "жирнее" будут вычислительные функции, тем больше будет отрыв многопоточной версии. Например, если взять случайные засыпания в диапазоне от 100 до 200 микросекунд, то картина будет следующей:

proxima_crunch_parallel | 0.213352proxima_crunch          | 0.624727loop_crunch             | 0.625393

То есть почти в три раза быстрее, как было бы при идеальном разложении на три потока.

Сравнительная таблица

*) Параллелизация в STL ещё не везде реализована.

**) constexpr диапазонов, видимо, будет лучше, когда они попадут в STL.

***) constexpr Проксимы зависит от STL. Всё, что своё уже constexpr. Всё, что зависит от STL, будет constexpr как только в STL оно будет таковым.

Ссылки

1. Проксима
2. Алгоритмы STL
3. atria::xform
4. Boost.Iterator
5. Boost.Range
6. range-v3
7. Абстрактный автомат

В C++ нет понятия "множество". Есть std::set, но это всё-таки конкретный контейнер. Есть функции для работы с упорядоченными диапазонами: merge, inplace_merge, includes, set_difference, set_intersection, set_symmetric_difference, set_union, но это алгоритмы, они не ленивые, и при вызове сразу вычисляют результат. К тому же они предназначены для работы строго с двумя диапазонами.

Что же делать, если, во-первых, диапазонов много (больше двух), а во-вторых, мы хотим вычислять результат не сразу, а по необходимости?

В данной публикации я хочу показать, как спроектировать ленивый диапазон, который будет производить какую-либо операцию с N множествами.

В публикации Ленивые итераторы и диапазоны в C++ я разбирал, что такое ленивые диапазоны.

Содержание

1. Операции с несколькими диапазонами
2. Алгоритм слияния
3. Переложение на итераторы
4. Дизайн
   
   1. Базируется на итераторах
   2. Быстрое копирование
   3. Деструктивность по отношению к внутренним диапазонам
   4. Можно создать диапазон
   5. Быстрое создание
   6. Изменяемость
   7. Есть адапторы
5. Пример с кодом
6. Заключение
7. Ссылки

Операции с несколькими диапазонами

Для начала определимся с терминологией.
Множеством я буду называть диапазон, элементы которого упорядочены.
Таким образом, первый элемент множества, задаваемого диапазоном с порядком "меньше", это наименьший элемент этого множества.

Все операции с несколькими множествами сводятся к двум этапам:

• Продвинуть диапазоны-множества так, чтобы достичь следующего элемента итогового множетсва.
• Выбрать один элемент среди текущих элементов всех диапазонов-множеств;

Процесс удобно представлять в виде движущихся входных лент, с которых выбранные элементы переписываются на выходную ленту.

В качестве примера рассмотрим слияние нескольких множеств.

В начале у нас есть три ленты: первая состоит из элементов {1, 2, 3}, вторая из элементов {2, 3, 5}, а третья {3, 5, 6}. Текущий элемент каждой ленты это её первый элемент.

Поскольку нам требуется произвести слияние множеств, то на каждом шаге нужно выбирать наименьший элемент. На первом шаге выбираем элемент 1 на первой ленте и выписываем его на выходную ленту.

После чего продвигаем первую ленту на один элемент. Затем выбираем элемент 2, снова с первой ленты.

Продвигаем первую ленту. Теперь на первой ленте тройка, а на второй двойка. Двойка меньше, так что выписываем двойку на выходную ленту, продвигаем вторую ленту.

На этом шаге на всех лентах стоят тройки. Выбираем тройку с первой ленты.

Снова продвигаем первую ленту. После продвижения оказывается, что первая лента закончилась. Это значит, что она выбывает из рассмотрения, и дальнейшие шаги будут произведены только для второй и третьей лент.

И так далее.

В итоге на выходной ленте будет записано {1, 2, 2, 3, 3, 3, 5, 5, 6}. Что, собственно, и ожидалось.

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

Алгоритм слияния

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

Подготовка:

1. Определим операцию сравнения двух множеств. Множество U будет считаться меньше множества V, если наименьший элемент множества U меньше наименьшего элемента множества V (напомню, что наши диапазоны упорядочены, так что наименьший элемент всегда стоит в начале диапазона);
2. Пустые множества выбросим из рассмотрения;
3. Сложим множества в пирамиду (кучу) таким образом, что на вершине пирамиды будет лежать наименьшее множество.

Шаг слияния:

1. Вынимаем из пирамиды наименьшее множество;
2. Выписываем наименьший элемент этого множества;
3. Продвигаем это множество на один элемент вперёд;
4. Если множество стало пусто, выбрасываем его;
5. Если множество всё ещё непусто, кладём его обратно в пирамиду.

Таким образом мы выпишем все элементы всех множеств в порядке их неубывания за время O(k + logk * n), где k количество множеств, n суммарный размер всех множеств.

В результате можно написать следующий код.

Переложение на итераторы

Из описания алгоритма и кода видно, что он хорошо разбивается на три части:

1. Предподготовка;
2. Выбор текущего элемента (он всегда на вершине пирамиды);
3. Переход к следующему элементу.

И это прекрасно ложится на то, что мы умеем делать с итераторами, а именно:

1. Инициализация;
2. Разыменование;
3. Продвижение.

Поэтому, долго не думая, берём Iterator Facade и делаем свой итератор.

Код итератора тут: Burst Merge Iterator.

Дизайн

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

Базируется на итераторах

Исходные множества, которые мы планируем слить воедино, задаются двумя итераторами, то есть одним диапазоном. При этом каждый элемент этого внешнего диапазона это сам по себе диапазон, то есть одно из тех множеств, которые мы будем сливать (тут можно вспомнить историю про ленты).

Внешний диапазон должен обладать произвольным доступом (random access range) именно он и будет выступать пирамидой, которую мы будем переупорядочивать в процессе слияния.

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

Результат итератор слияния также будет однопроходным (input iterator).

Быстрое копирование

Итератор должен быстро копироваться. Все стандартные алгоритмы принимают итератор по значению и не стесняются копировать внутри себя.

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

Деструктивность по отношению к внутренним диапазонам

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

Поэтому для работы итератора слияния нужно создавать отдельное хранилище для внутренних диапазонов, а сами внутренние диапазоны уничтожаются (схлопываются) в процессе продвижения итератора слияния.

Но это не проблема: благодаря этому мы уже получили гибкость и эффективность самого итератора, а организовать красивый интерфейс для обхода явного создания хранилища тоже можно (см. Быстрое создание).

Можно создать диапазон

Итератор-конец для итератора слияния это не совсем итератор, а ограничитель (sentinel в терминах C++20). Простейший пример такого ограничителя это ноль для классической сишной строки: у нас нет указателя на конец строки, но мы знаем, что если значение разыменованного итератора равно нулю, то это и есть конец строки.

Это значит, что можно не мучить пользователя, и сразу создавать диапазон, минуя создание отдельных итераторов.

const auto odd = std::vector{1, 3, 5, 7};const auto even = std::vector{0, 2, 4, 6, 8};auto range_to_merge =    std::vector    {        boost::make_iterator_range(odd),        boost::make_iterator_range(even)    };const auto merged_range = burst::merge(range_to_merge);const auto expected = {0, 1, 2, 3, 4, 5, 6, 7, 8};assert(merged_range == expected);

Код построения диапазона на основе итератора здесь: Burst Merge

Быстрое создание

По умолчанию итератор слияния конструируется из диапазона (см. выше). Но есть и другая возможность.

Можно просто передать кортеж из ссылок на исходные контейнеры:

const auto odd = std::vector{1, 3, 5, 7};const auto even = std::vector{0, 2, 4, 6, 8};const auto merged_range = burst::merge(std::tie(odd, even));const auto expected = {0, 1, 2, 3, 4, 5, 6, 7, 8};assert(merged_range == expected);

В этом случае библиотека берёт на себя создание и обработку промежуточного хранилища для "технических" итераторов.

Изменяемость

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

auto first = std::vector{50, 100};auto second = std::vector{30, 70};auto merged_range = burst::merge(std::tie(first, second));boost::for_each(merged_range, [] (auto & x) { x /= 10; });assert(first[0] == 10);assert(first[1] == 5);assert(second[0] == 7);assert(second[1] == 3);

Есть адапторы

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

const auto first = std::vector{1, 4, 7};const auto second = std::vector{2, 5, 8};const auto third = std::forward_list{3, 6, 9};const auto square = [] (auto x) {return x * x;};const auto merged =    std::tie(first, second, third)        | burst::merged        | boost::adaptors::transformed(square);const auto expected = {1, 4, 9, 16, 25, 36, 49, 64, 81};assert(merged == expected);

Пример с кодом

Вы спросите: "зачем?!" А я отвечу: для упрощения написания и понимания кода.

Конкретно слияние нескольких упорядоченных диапазонов довольно полезная операция. С её помощью, например, можно написать внешнюю сортировку.

Полный пример внешней сортировки можно почитать здесь.

Заключение

Ленивые операции над множествами достаточно интересная штука. Можно реализовать слияние, объединение, пересечение, разность, симметрическую разность в общем, всё, что угодно.

И всё это с сохранением эффективности и достаточно приятного интерфейса.

Ссылки

• Ленивые операции над диапазонами в библиотеке Burst
• Boost Iterator Facade
• Boost Range Adaptors

Для того, чтобы упростить написание и чтение кода, программисты периодически придумывают всякие техники. Об одной из таких техник я уже писал в публикации Долой циклы, или Неленивая композиция алгоритмов в 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  8auto 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++.

Ссылки

• Итераторы
• Boost.Iterator
• Boost.Range
• range-v3
• Ranges (C++20)