C++20 Ranges. Полное руководство
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();
// член данных
std::ranges::sort(acc,{},&Account::owner);
// функция-член
std::ranges::sort(acc,{},&Account::value);
// лямбда
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, которому принадлежит единственный просматриваемый элемент.
Представления компонуются во время компиляции с прицелом на то, что компилятор заинлайнит код.
Например, следующий код распечатает последние три элемента диапазона. Сначала мы переворачиваем диапазон, затем берем первые три элемента и, наконец, снова переворачиваем диапазон (обратите внимание, что существует 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, доступна здесь.