Ranges

25 февраля автор курса Разработчик C++ в Яндекс.Практикуме Георгий Осипов рассказал о новом этапе языка C++ Стандарте C++20. В лекции сделан обзор всех основных нововведений Стандарта, рассказывается, как их применять уже сейчас, и чем они могут быть полезны.

При подготовке вебинара стояла цель сделать обзор всех ключевых возможностей C++20. Поэтому вебинар получился насыщенным. Он растянулся почти на 2,5 часа. Для вашего удобства текст мы разбили на шесть частей:

1. Модули и краткая история C++.
2. Операция космический корабль.
3. Концепты.
4. Ranges.
5. Корутины.
6. Другие фичи ядра и стандартной библиотеки. Заключение.

Это четвёртая часть, рассказывающая о новом модуле стандартной библиотеки, Ranges.

Ranges

До этого рассматривалось ядро языка. Теперь я расскажу про изменение в стандартной библиотеке, которое не добавляет нового в синтаксис, введённый C++20 заголовочный файл <ranges>.

Мотивация

В C++ много стандартных алгоритмов. Но они применимы не всегда. Если действие нестандартное, то для его решения, скорее всего, придётся вводить некрасивые вложенные циклы, флаги. При этом код лавинообразно теряет выразительность.

Слушателям предлагался вопрос. Сколько строк выведет код ниже?

1. 5
2. 6
3. 9
4. Ни одной.
5. Будет выводить, пока не остановим.

Подумайте, прежде чем прочитать ответ.

#include <iostream>int main() {    const int days = 3;   // количество дней с играми    const int games = 2;  // количество игр с питомцем в день    for (int i = 0; i < days; i++) {        std::cout << "День " << i << std::endl;        for (int j = 0; j < games; i++) {            std::cout << "  Игра " << j << std::endl;        }    }}

Во время вебинара правильных ответов оказалось больше, чем я ожидал. Это тест на внимательность, потому что в коде есть ошибка: цикл никогда не завершится. Проблема в том, что я перепутал инкрементируемую переменную во внутреннем цикле. Допустить такую ошибку куда проще, чем её заметить. Если вы ни разу так не ошибались, вряд ли вы программируете на C/C++.

Другой пример. Стандартные алгоритмы принимают два итератора: на первый элемент и на последний, фиктивный. Но передавать пары утомительно. Например, алгоритм merge, который смешивает два отсортированных диапазона, требует сразу пять итераторов две пары и ещё один выходной. Приходится дублировать имя контейнера. Вполне возможно, что контейнер назван не одной буквой, а длинным именем или выражением:

std::merge(  collection_holder.get_left_collection().begin(),   collection_holder.get_left_collection().end(),   collection_holder.get_right_collection().begin(),   collection_holder.get_right_collection().end(),  std::back_inserter(    collection_holder.get_destination_collection()  ));

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

Ещё один пример для мотивации. Для стандартных действий есть алгоритм, скажем, copy_if, который копирует элементы, удовлетворяющие условию. Он используется для фильтрации элементов. Алгоритм transform применяет к каждому элементу функцию. Предположим, нужно выполнить обе операции: отфильтровать элементы и к оставшимся применить функцию. Такой алгоритм можно назвать transform_if, но к сожалению, в стандартной библиотеке его нет.

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

std:vector<int> numbers_in;std:vector<int> numbers_out;// задача: поделить на 2 все чётные числа из numbers_in// и записать результаты numbers_outstd:vector<int> intermediate;// скопируем в intermediate только чётные числаstd::copy_if(numbers_in.begin(), numbers_in.end(),               std::back_inserter(intermediate),              [](int x) {                        return x % 2 == 0;             });// поделим их на 2std::transform(intermediate.begin(), intermediate.end(),               std::back_inserter(numbers_out),               [](int x) {                          return x / 2;               })

Тут пришлось завести промежуточное хранилище. Получили неэффективное решение с двумя проходами по элементам.

Что у других

В Python есть классная фича: можно писать прямо в выражениях квадратные скобки и делать внутри всё что угодно, в том числе фильтровать элементы и применять к ним функции. Это замечательно и удобно. Возможно, Ranges в C++ делали, поглядывая на Python.

Пример с transform_if сокращается до одной строки:

# transform_if в одну строку средствами языка:numbers_out = [x // 2 for x in numbers_in if x % 2 == 0]

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

days = 3   # количество дней с играмиgames = 2  # количество игр с питомцем в деньfor i in range(days):    print("День %d" % i)    for j in range(games):        print("  Игра %d" % j)

В Python не нужно писать i = 0; i < N; ++i. Буква i набирается один раз, и возможности перепутать что-либо у вас нет. Кстати говоря, range даёт не контейнер, который содержит все элементы, а генерирует числа на лету. По производительности это если и будет уступать обычному циклу, то едва-едва.

Приведу преимущества Python списком:

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

Другой пример SQL. Хотя это не язык программирования, мы можем реализовать transform_if даже на нём:

SELECT n / 2 FROM tab WHERE n % 2 == 0;

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

Примеры

В C++20 появилась возможность решать проблемы, озвученные в начале статьи, это библиотека Ranges. Например, так выглядят циклы привычные for, которые перебирают все целые числа в некотором интервале:

#include <iostream>#include <ranges>namespace rng = std::ranges;namespace view = rng::views;int main() {    const int days = 3;   // количество дней с играми    const int games = 2;  // количество игр с питомцем в день    for (int i : view::iota(0, days)) {        std::cout << "День " << i << std::endl;        for (int j : view::iota(0, games)) {            std::cout << "  Игра " << j << std::endl;        }    }}

Теперь не придётся три раза писать i, три раза писать j, и нельзя их перепутать. Вместо привычных циклов с инкрементом итерируемся по std::ranges::views::iota. Как и в Python, функция не будет генерировать контейнер, а выдаст числа на лету.

Range упрощает реализацию transform_if:

#include <iostream>#include <ranges>#include <vector>namespace rng = std::ranges;namespace view = rng::views;int main() {    auto even = [](int i) { return i % 2 == 0; };    auto half = [](int i) { return i / 2; };        std::vector<int> numbers_in = {100, 55, 80, 2, -1};    auto numbers_out = numbers_in | view::filter(even) |  // <-- вся магия                 view::transform(half);        for (auto i : numbers_out) {        std::cout << i << std::endl; // 50, 40, 1    }}

Здесь различные преобразования комбинированы операцией |, или как её ещё называют, pipe. filter, отфильтровывающий нечётные числа, комбинирован с transform, делящим на два. Получаем объект-диапазон, по которому можно итерировать. Этот объект ленивый: он не будет ничего вычислять, пока вы не запросите первое значение. Более того, вернув первое значение, диапазон не будет вычислять второе до тех пор, пока оно не будет запрошено. Это позволяет не хранить в памяти все значения единовременно и применять алгоритмы в один проход. Замечательная функция.

Но если всё же вам необходимо вычислить всё сразу, вы можете по старинке сложить все элементы диапазона в какой-нибудь контейнер: numbers_vector = std::vector(number_out.begin(), numbers_out.end()).

На этом слайде приведено сравнение, как это пишется в C++20, а как в Python. Видно, что Python по-прежнему лаконичнее, но всё-таки C++ уже гораздо ближе.



Такие возможности появились в C++20, и это классно. Разумный вопрос: а что с производительностью?

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

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

Я сделал бенчмарк для сравнения цикла в старом стиле с itoa. Его результат на слайде:



Различия в производительности нет! Оказывается, что цикл с itoa настолько же эффективен, как и простой с инкрементом переменной.

При добавлении сложного синтаксического сахара производительность часто падает. Но только не в C++.

Ещё один бенчмарк, в котором сравнивается transform_if в старой реализации и в новой на основе <ranges>.



Как видно, c Ranges получилось быстрее. Справедливости ради скажу, что если написать функцию вручную с циклом, итерирующимся по контейнеру, то получится ещё небольшой прирост скорости. Я не знаю, в чём причина. Наверное, это будет исправлено в следующих версиях Ranges.

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

Ещё примеры

Это было только начало. В Ranges ещё масса интересного.

Вот код, который сортирует элементы вектора и выводит их:

#include <iostream>#include <vector>#include <algorithm>#include <ranges>namespace rng = std::ranges;template <rng::input_range Range>void Print(const Range& range) {    std::cout << "Elements:";    for (const auto& x : range) {        std::cout << ' ' << x;    }    std::cout << std::endl;}int main() {    std::vector v = { 4, 1, 7, 2, 3, 8 };    rng::sort(v);    Print(v); // Elements: 1 2 3 4 7 8    return 0;}

Заметьте, что здесь применяется не обычный алгоритм std::sort, а sort из пространства имён std::ranges. В этот алгоритм можно передать не пару итераторов, а контейнер то, чего и хотелось.

Я написал функцию Print, которая использует возможности концептов. Используется концепт input_range из пространства имён std::ranges. Он нужен в шаблонной функции для того, чтобы она принимала только объекты-диапазоны с точки зрения Ranges.

В C++20 этот код можно упростить:

void Print(const rng::input_range auto& range) {    std::cout << "Elements:";    for (const auto& x : range) {        std::cout << ' ' << x;    }    std::cout << std::endl;}

Слово template убирается и становится неявным. А const auto& это тип параметра, к нему применён концепт input_range.

Ещё одно заметное преимущество новых алгоритмов в библиотеке <ranges> это параметр проекции. Предположим, что вам требуется написать сортировку по некоторому полю объекта:

struct Lecture {    int course;    int local_idx;    int complexity;};std::vector<Lecture> ReadLectures();int main() {    std::vector<Lecture> lectures = ReadLectures();    // как раньше    std::sort(lectures.begin(), lectures.end(),          [](const Lecture& lhs, const Lecture& rhs) {            return lhs.complexity < rhs.complexity;    });    return 0;}

Пришлось разработать свой компаратор и дублировать название поля complexity. В <ranges> добавлены новые реализации старых алгоритмов, которые помимо передачи диапазона допускают параметр-проекцию. Такой алгоритм применит заданную вами функцию и сравнит её результаты вместо сравнения элементов контейнера напрямую:

struct Lecture {    int course;    int local_idx;    int complexity;};std::vector<Lecture> ReadLectures();namespace rng = std::ranges;int main() {    std::vector<Lecture> lectures = ReadLectures();    // как теперь    rng::sort(lectures, std::less<>{}, [](const Lecture& x) {        return x.complexity;    });    return 0;}

В качестве компаратора взят обычный std::less, который сравнивает, применяя операцию <, но благодаря проекции применяется он не к элементам вектора, а к значениям лямбда-функции.

Теория

На этом слайде приведены новые алгоритмы из пространства имён std::ranges. Работа Комитета впечатляет: 85 алгоритмов, каждый из которых тщательно проработан.



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

Вернёмся к примеру с transform_if.

auto range = numbers_in | view::filter(even) |             view::transform(half);

Мы отфильтровали вектор numbers_in и применили к его элементам функцию. Имена filter и transform примеры адаптеров, то есть таких объектов Ranges, которые меняют диапазон.

В библиотеке есть несколько видов адаптеров. Адаптер drop отбрасывает элементы, а take ограничивает их количество. Предположим, нам нужны элементы с 5-го по 14-й. На SQL это было бы сделано так:

SELECT * FROM tab LIMIT 10 OFFSET 5

На C++ теперь можно сделать похожим образом:

using namespace view = rng::views;for (const auto& x : tab | view::drop(5) | view::take(10)) {    std::cout << x << std::endl;}

Адаптеров в стандартной библиотеке не так много, как алгоритмов, а жаль. Вот список всех: all, filter, transform, take, take_while, drop, drop_while, join, split, counted, common, reverse, elements, keys, values.

Зато можно создавать свои! Этот пример кода я не буду разбирать подробно. Посмотрите, как просто мы создали адаптеры для выделения разных категорий пользователей и комбинировали их:

auto ByGender(Gender gender) {    return view::filter([gender](const Person& person) {        return person.gender == gender;     });}auto ByEmployment(bool is_employed) {    return view::filter([is_employed](const Person& person) {        return person.is_employed == is_employed;     });}template <rng::ForwardRange Range>AgeStats ComputeStats(Range&& persons) {    auto females = ByGender(Gender::FEMALE);    auto males = ByGender(Gender::MALE);      auto employed = ByEmployment(true);    auto unemployed = ByEmployment(false);    return {        ComputeMedianAge(persons),        ComputeMedianAge(persons | females),        ComputeMedianAge(persons | males),            ComputeMedianAge(persons | females | unemployed),        ComputeMedianAge(persons | males | employed)     };}

Статус

Ranges это нововведение стандартной библиотеки. У каждого компилятора есть своя родная реализация.

• К сожалению, в библиотеке Clang диапазоны пока не реализованы.
• В библиотеке Visual Studio 2019 присутствует поддержка <ranges>, но частично. Например, нет некоторых стандартных алгоритмов.
• В библиотеке GCC уже всё хорошо, и <ranges> можно использовать смело.

Они неспроста помечены в стандартной библиотеке GCC как экспериментальные. Прямо сейчас готовится десяток ломающих улучшений, Ranges активно дорабатываются и переделываются уже после релиза. Лучше ближайшие пару лет ими не пользоваться, если нет желания исправлять код с новым релизом компилятора.
Антон Полухин

Заключение

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

• Суперфича 21 (80,77%)
• Так себе фича 2 (7,69%)
• Пока неясно 3 (11,54%)

Больше всего разочаровывает в Ranges небольшое количество стандартных адаптеров. Например, в Python есть функция enumerate, которая к элементу приписывает его порядковый номер. Там есть возможность итерироваться по декартову произведению парам элементов разных диапазонов. Есть zip, при котором итерирование будет происходить по диагонали декартова произведения. Ничего подобного в C++ я не нашёл. Будем надеяться на новые выпуски Стандарта.

Их добавляют в C++23.
Антон Полухин

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

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

Читателям Хабра, как и слушателям вебинара, дадим возможность оценить нововведения.