C++20 Ranges — Полное руководство

• Ranges vs старая STL
  • Концепции
  • Проекции
  • О мелочах
• Составные представления
  • Представления
  • Объекты замыкания представления
• Написание задачи FizzBuzz тремя способами
• Корутина-генератор
  • Компоновка с использованием представлений
  • Ссылки и технические примечания
  • Благодарности

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

Следует отметить, однако, что Ranges - это одна из фич, которая появилась C++20 в "полусыром" состоянии. C++23 должен существенно приблизить нас к полной реализации Ranges. По этой причине некоторые примеры будут основываться на библиотеке range v3.

Ranges vs старая 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, так как это выражение оказывается всегда true.

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

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

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

Проекции

Масштабная новая функция, которая на первый взгляд кажется тривиальной, — поддержка проекций (Projections). Проекция — это унарный вызываемый (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, ","));

Этот кусок кода немного включает спойлер о представлениях (Views), но я хотел показать другой пример, где в качестве входных данных использовались два диапазона. В таком случае мы получаем две отдельные проекции. Обратите внимание, что эти проекции также могут возвращать различные типы возвращаемых значений, если они совпадают с операцией (здесь 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";

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

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

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

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

Составные представления

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

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

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

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

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

Например, следующий код выведет последние три элемента диапазона. Сначала мы разворачиваем диапазон, затем берем первые три элемента и, наконец, снова разворачиваем диапазон (обратите внимание, что есть 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";

Объекты замыкания представления

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

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

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 тремя способами

Давайте рассмотрим конкретные примеры диапазонов. Мы напишем FizzBuzz тремя способами, используя:

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

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

Корутина-генератор

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

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).

// Resume coroutine to generate new value.
void operator++() { 
    coro_.resume(); 
}
// Grab current value from coroutine.
const T& operator*() const {
    return *coro_.promise().current_value;
}
// We are at the end if the coroutine is finished.
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"));

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

Все примеры кода и скрипты доступны по адресу:

https://github.com/HappyCerberus/article-cpp20-ranges.

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

https://github.com/ericniebler/range-v3.

Благодарности

Спасибо, что прочтение. Вам понравилась статья?

Я также публикую видео на YouTube. У вас есть вопросы? Свяжитесь со мной в Twitter или LinkedIn.