C++20 Ranges, также известная как STL v2, представляет из себя более эффективную замену существующих алгоритмов и технических средств STL. В этой статье мы пройдемся по изменениям, введенным Ranges (диапазоны/интервалы), обсудим представления (views), которые представляют собой новый подход к композиции алгоритмов, и рассмотрим примеры реализации FizzBuzz с использованием трех разных методов, в каждом из которых используются некоторые аспекты библиотеки Ranges.

Однако сразу следует отметить, что Ranges — это одна из фич, реализованных в C++ 20 в полуготовом состоянии. C++23 должен приблизить нас к полной поддержке всего задуманного в рамках Ranges. Поэтому в некоторых примерах будет использоваться библиотека range v3.

Ranges по сравнению со старым STL

Как уже упоминалось, диапазоны (ranges) — это замещающая замена STL. Они вносят как подкапотные, так и видимые пользователю изменения, которые в целом делают их более полезными.

Концепты (Concepts)

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

Типичный пример — это попытка отсортировать std::list. Здесь очень легко сделать ошибку, если вы новичок в C++.

#include <iostream>
#include <ranges>
#include <list>
#include <algorithm>
int main() {
    std::list<int> dt = {1, 4, 2, 3};
    std::ranges::sort(dt.begin(), dt.end());
    std::ranges::copy(dt.begin(), dt.end(), 
        std::ostream_iterator<int>(std::cout, ","));
}

Вместо того, чтобы получать сбивающую с толку информацию об операторе минус, теперь мы видим более точное сообщении об ошибке:

include/c++/12.0.0/bits/ranges_algo.h:1810:14: note: because 'std::_List_iterator<int>' does not satisfy 'random_access_iterator'

Мы можем посмотреть концепты, определенные библиотекой Ranges, поскольку они являются частью стандарта. Например, концепт range очень простой и всего-навсего требует, чтобы выражения std::ranges::begin(rng) и std::ranges::end(rng) были валидными. Если вы хотите узнать больше о концептах, ознакомьтесь с моим руководством по концептам.

Фундаментальное изменение здесь заключается в том, что end() больше не должен возвращать тот же тип, что и begin(). Возвращаемый ограничитель (sentinel) должен быть сопоставим только с типом итератора, возвращаемым функцией begin().

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

std::vector<int> dt = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::ranges::shuffle(dt, std::mt19937(std::random_device()()));
auto pos = std::ranges::find(dt.begin(), 
                             std::unreachable_sentinel,
                             7);
std::ranges::copy(dt.begin(), ++pos, 
                  std::ostream_iterator<int>(std::cout, ","));

std::unreachable_sentinel всегда возвращает false, когда происходит сравнение с итератором. Поэтому компилятор оптимизирует проверку границы it! = End, так как тогда это выражение всегда истинно.

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

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

std::vector<int> dt = {1, 4, 2, 3};
std::ranges::sort(dt);

Проекции (Projections)

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

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

struct Account {
    std::string owner;
    double value();
    double base();
};
std::vector<Account> acc = get_accounts();
// member
std::ranges::sort(acc,{},&Account::owner);
// member function
std::ranges::sort(acc,{},&Account::value);
// lambda
std::ranges::sort(acc,{},[](const auto& a) { 
    return a.value()+a.base(); 
});

Без проекций нам пришлось бы подключать эту логику как часть кастомного компаратора.

std::vector<int> dt = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> result;
std::ranges::transform(dt, 
                       dt | std::views::reverse,
                       std::back_inserter(result),
                       std::minus<void>(),
                       [](int v) { return v*v; },
                       [](int v) { return v*v; });
std::ranges::copy(result, 
                  std::ostream_iterator<int>(std::cout, ","));

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

Небольшая мелочь

Последняя “маленькая” фича, о которой я хотел бы упомянуть, — это предотвращение зависания итераторов (dangling iterators). В основном потому, что даже если вас это особо не заботит, вы все-равно можете найти применение этого паттерна в своей кодовой базе.

auto good = "1234567890";
auto sep1 = std::ranges::find(std::string_view(good), '0');
std::cout << *sep1 << "\n";
auto bad = 1234567890;
auto sep2 = std::ranges::find(std::to_string(bad), '0');
std::cout << *sep2 << "\n";

Вы можете сразу заметить тут проблему. Если бы мы не использовали варианты алгоритмов c диапазонами, “плохой” вариант вылетел бы во время выполнения. Однако с диапазонами этот код не будет компилироваться. Когда алгоритм на основе диапазонов вызывается с временным диапазоном, которому принадлежат его элементы, алгоритм возвращает специальный итератор std::ranges::dangling.

Обратите внимание, что первый вариант с std::string_view по-прежнему будет работать нормально. String_view — это тип диапазона, который не владеет своими элементами, а его итераторы являются автономными (они не зависят от инстанса string_view), поэтому вполне допустимо передать такое временное значение в алгоритм с диапазонами.

Чтобы ваши диапазоны работали как временные, вам необходимо специализовать константу enable_borrowed_range:

template<typename T>
inline constexpr bool 
    std::ranges::enable_borrowed_range<MyView<T>> = true;

Композиции представлений 

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

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

Представления (Views)

Представления — это просто-напросто диапазоны, которые дешево копировать и перемещать (за константное время). Из-за этого представление не может владеть элементами, которые просматривает. Одно исключение — std::views::single, которому принадлежит единственный просматриваемый элемент.

Представления компонуются во время компиляции с прицелом на то, что компилятор заинлайнит код.

Например, следующий код последние последние три элемента диапазона. Сначала мы reverse’им диапазон, затем берем первые три элемента и, наконец, снова reverse’им диапазон (обратите внимание, что существует std::views::drop, который делает это напрямую).

namespace rv = std::ranges::views;
std::vector<int> dt = {1, 2, 3, 4, 5, 6, 7};
for (int v : rv::reverse(rv::take(rv::reverse(dt),3))) {
    std::cout << v << ", ";
}
std::cout << "\n";

Объекты-замыкания представлений (view closure objects)

Часто из-за глубокой вложенности функциональный синтаксис композиции представлений в плане написания и чтения может быть очень громоздким.

К счастью, диапазоны дают нам еще один подход к композиции представлений. Представления в пространстве имен std::views на самом деле являются объектами-замыканиями представления. Это встроенные constexpr константы с каждым range::xxx_view подвязанным на объект std::std::views::xxx. Эти объекты перегружают operator() для функционального синтаксиса, как показано выше, и operator | для композиции в лаконичном виде.

namespace rv = std::ranges::views;
std::vector<int> dt = {1, 2, 3, 4, 5, 6, 7};
for (int v : dt | rv::reverse | rv::take(3) | rv::reverse) {
    std::cout << v << ", ";
}
std::cout << "\n";

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

namespace rv = std::ranges::views;
std::vector<int> dt = {1, 2, 3, 4, 5, 6, 7};
auto odd = [](std::integral auto v) { return v % 2 == 1; };
for (auto& v : dt | rv::filter(odd)) {
    v *= 2;
}

Три способа реализовать FizzBuzz

Давайте рассмотрим несколько конкретных примеров с использованием Ranges. Мы напишем три версии FizzBuzz:

  • генератор кокрутин с диапазоном значений;

  • генеративный подход с использованием алгоритмов;

  • подход с использованием композиции представлений.

Как упоминалось в начале статьи, в настоящее время в C++20 поддержка диапазонов реализована не полностью. Поэтому я буду полагаться на библиотеку range v3.

Генератор корутин

Написание генератора корутин FizzBuzz почти идентично типовой реализации:

ranges::experimental::generator<std::string> fizzbuzz() {
    for (int i = 1; ; i++) {
        std::string result;
        if (i % 3 == 0) result += "Fizz";
        if (i % 5 == 0) result += "Buzz";
        if (result.empty()) co_yield std::to_string(i);
        else co_yield result;
    }
}

Однако, если мы используем generator<> из библиотеки range v3, мы также можем использовать вызванную корутину как диапазон.

for (auto s : fizzbuzz() | ranges::views::take(20)) {
    std::cout << s << "\n";
}

Основная магия здесь заключается в типе итератора (обратите внимание, что этот код не из библиотеки range v3).

// Возобновляем корутину для генерации нового значения.
void operator++() {
   coro.resume();
}

// Берем текущее значение из корутины.
const T& operator*() const {
   return *coro_.promise().current_value;
}

// Мы находимся в конце, если корутина завершена.
bool operator==(std::default_sentinel_t) const {
   return !coro_ || coro_.done();
}

std::default_sentinel_t предусмотрен стандартом для удобства и предназначен для сравнений с end(). При этом нам просто нужно вернуть этот итератор из типа возврата generator<>:

Iter begin() {
    if (coro_) {
        coro_.resume();
    } 
    return Iter{cor_};
}
std::default_sentinel_t end() { 
    return {}; 
}

Генерация с использованием алгоритмов

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

ranges::generate_n(
    std::ostream_iterator<std::string>(std::cout, "\n"), 
    20,
    [i = 0]() mutable {
        i++;
        std::string result;
        if (i % 3 == 0) result += "Fizz";
        if (i % 5 == 0) result += "Buzz";
        if (result.empty()) return std::to_string(i);
        return result;
});

Композиция представлений

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

FizzBuzz включает два цикла. Fizz с периодом три и Buzz с периодом пять.

std::array<std::string, 3> fizz{"", "", "Fizz"};
std::array<std::string, 5> buzz{"", "", "", "", "Buzz"};

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

const auto inf_fizz = fizz | ranges::views::cycle;
const auto inf_buzz = buzz | ranges::views::cycle;

Затем мы можем объединить их, используя zip_with:

const auto inf_fizzbuzz = ranges::views::zip_with(
    std::plus<>(), 
    inf_fizz, 
    inf_buzz);

Теперь у нас есть бесконечный диапазон, в котором каждый 3-й элемент — это “Fizz”, каждый 5-й элемент — “Buzz”, каждый 15-й элемент — “FizzBuzz”, а остальные — пустые строки.

Нам не хватает простых чисел для элементов, которые не являются Fizz или Buzz. Итак, давайте построим бесконечный диапазон индексов (начиная с одного):

const auto indices = ranges::views::indices
    | ranges::views::drop(1);

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

const auto final_range = ranges::views::zip_with(
    [](auto i, auto s) { 
        if (s.empty()) return std::to_string(i); 
        return s;
    },
    indices,
    inf_fizzbuzz
);
ranges::copy_n(ranges::begin(final_range), 20,
    std::ostream_iterator<std::string>(std::cout, "\n"));

Ссылки и технические примечания

Все примеры кода и скрипты доступны здесь.

Библиотека range v3, используемая для примеров FizzBuzz, доступна здесь.

Спасибо, что прочитали эту статью. Надеюсь, она была для вас полезной. Я также выкладываю видео на YouTube. Если у вас есть какие-либо вопросы — пишите мне в Twitter или LinkedIn.


Материал подготовлен в рамках курса «C++ Developer. Professional».

Новые ключевые слова co_await, co_yield и co_return уже поддерживаются современными компиляторами, но программистам на C++ еще предстоит научиться их использовать на практике. Всех желающих приглашаем на бесплатный двухдневный интенсив «Асинхронный сервер на сопрограммах из C++20».
На данном интенсиве мы рассмотрим, как можно сделать обертку над асинхронными сокетами под Linux, которую можно будет использовать для передачи управления с помощью сопрограмм. Итоговый результат будет интересно сравнить с классическим решением на основе функций обратного вызова, чтобы проверить, насколько для сопрограммы выполняется принцип zero-overhead abstractions.
>> РЕГИСТРАЦИЯ

Комментарии (21)


  1. OlegZH
    08.12.2021 18:40
    +3

    Часто из-за глубокой вложенности функциональный синтаксис композиции представлений в плане написания и чтения может быть очень громоздким.

    Не означает ли это, что давно пора переработать синтаксис самого C++, чтобы избежать излишней громоздкости?


    1. northzen
      08.12.2021 19:55

      С++2.0 в массы!


      1. OlegZH
        08.12.2021 22:50

        Интересно было бы посмотреть на язык программирования ++С.

        Если я ещё/уже не забыл C/C++ (давно не использовал), префиксная запись означает, что, сначала, производится инкремент (то есть — приращение), а уже затем возвращается результат. В постфиксной, вроде бы, всё наоборот, сначала возвращается исходное значение, но, затем, происходит инкремент. То есть: результат операции (возвращаемое значение) является различным, но побочный эффект (в виде инкремента заданной переменной) остаётся одним и тем же. Я ничего не путаю?

        Раньше имелось в виду, что C++ — это тот же язык C (синтаксис — результат), но с новым смыслом (семантика — побочный эффект). Вот я и думаю, что мог бы из себя представлять язык программирования ++С, у которого уже сразу изменён синтаксис, и этот новый синтаксис обеспечивает и новую семантику. В C++ изменение семантики происходило за счёт того, что каждую переменную можно было мыслить как экземпляр некоторого класса. Отсюда и расхожее представление, что C++ — это "C с классами".

        Я мог бы предположить, только, что язык программирования ++С — это язык программирования, в котором сделан упор на перегрузку операторов. Должен действовать принцип: "всё есть оператор и всё может быть перегружено". Это значит, что и обыкновенные скобки должны стать полноценным оператором. Это придаст языку программирования С некоторые черты Python'а. Однако, такой подход означает, что и оператор for тоже может быть перегружен.


        1. skiedr
          09.12.2021 08:21

          Ну это D получается.


          1. OlegZH
            09.12.2021 10:13
            +1

            Не уверен.


      1. win32asm
        08.12.2021 22:52

        Верните нам наш Турбо Си 2.01 и МС Дос 6.0 !

        (Нет, лучше закопайте их поглубже...)


        1. OlegZH
          09.12.2021 10:24
          +1

          [offtopic]

          Turbo Pascal 5.0, 5.5 и 6.0. Turbo Professional и Object Professional. OWL. Watcom C. Foxpro. Lotus 1-2-3. Nowel Netware. PS DOS, DR DOS и OS/2 Warp. Лексикон и ChiWriter. Wolfenstein 3D. The But!

          MODULA, SIMULA, OBERON, REFAL, ADA

          CGA, EGA, VGA, Hercules

          [/offtopic]


    1. drafterleo
      09.12.2021 01:12

      Не означает ли это, что давно пора переработать синтаксис самого C++, чтобы избежать излишней громоздкости?

      А как же обратная совместимость?


      1. OlegZH
        09.12.2021 10:10
        +5

        Обратная совместимость — это зло.


        1. northzen
          09.12.2021 19:57
          +2

          Но иногда -- наименьшее.


    1. DistortNeo
      09.12.2021 21:18

      В C# есть элегантное решение: методы-расширения, когда первый аргумент становится, типа, объектом, а статическая функция — типа, методом. Вместо


      ClassName.Reverse(ClassName.Take(ClassName.Reverse(x), 3));

      можно писать


      x.Reverse().Take(3).Reverse();

      В C++ же такое невозможно, т.к. сломает ADL.


      1. OlegZH
        09.12.2021 23:10

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

        class Foo
        {
          Foo& SomeMethod(){ return *this; };
        }

        Это и ломает ADL?


        1. DistortNeo
          09.12.2021 23:52
          +2

          Нет. Я про Uniform Function Call Syntax.


      1. bfDeveloper
        10.12.2021 02:02

        Я большой любитель ADL и не в курсе, как UFCS его ломает. Может быть есть примеры? Если взять идею из D, где не надо ничего указывать специально и любая функция может быть вызвана как метод на своём первом аргументе, то алгоритм простой:

        1) Ищем метод на объекте, если есть зовём

        2) Если нет, то ищем функцию по старым правилам, включая ADL.

        Что не так?


        1. DistortNeo
          10.12.2021 13:09

          Я большой любитель ADL и не в курсе, как UFCS его ломает.

          Не помню, давно про это читал, в голове почему-то отложилось.

          Что не так?

          Всё логично. Но proposal-ы стабильно не проходят голосование, потому что вечно находятся причины против UFCS: каша с overload resolution или же необходимость всюду писать using namespace и т.д.


          1. bfDeveloper
            10.12.2021 14:29

            Но proposal-ы стабильно не проходят голосование, потому что вечно находятся причины против UFCS

            Вот это, к сожалению, правда. Даже версия с вывернутым наизнанку UFCS не прошла, когда предлагали begin(vec) трактовать как vec.begin(), а не наоборот. В том же D на этом Ranges работают и не надо дополнительно перегружать |. Я не всегда понимаю комитет, порой они уж слишком осторожны.


            1. DistortNeo
              10.12.2021 15:26

              и не надо дополнительно перегружать |

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

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

              ns::ext::take(list, 3)

              В случае расширения нам пришлось бы писать:

              list.ns::ext::take(3)

              Ужасно, не правда ли? Конечно, мы можем обмазаться using-ами, но это будет так себе решение.

              А дальше мы вспоминаем, что в C++ есть ADL, и пытаемся заставить его работать: а именно, сделать так, чтобы один из аргументов функции был из нужного нам пространства имён. Хорошим кандидатом на эту роль оказались бинарные операторы:

              list | ns::ext::take(3)

              P.S. Собственно, вот что я имел виду, когда писал, что расширения ломают ADL — он попросту не работает с ними.


  1. Shiny2
    09.12.2021 10:19

    вот это поворот. А что говорят отцы например Шон Парент?


  1. sborisov
    09.12.2021 11:34

    Сильно ли замедляется скорость компиляции по сравнению с обычными итераторами?
    Публиковался перевод, где сравнивали Си и ranges, конечно шокирует немного, но в Си нет шаблонов, которые нужно инстанцировать на этапе компиляции, а вот как интересно STL vs STL 2.0 себя ведет


  1. Ingulf
    10.12.2021 15:13

    то ли у меня проблемы с восприятием, то ли перевод машинный и "кривой" по части терминологии


  1. monah_tuk
    11.12.2021 10:51

    .