Стандарт C++20: обзор новых возможностей C++. Часть 4 «Диапазоны»

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

Мотивация

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

Как вы думаете, сколько строк выведет приведенный ниже код?

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

#include <iostream>
int main() {
    const int days = 3;   // number of days with games
    const int games = 2;  // number of pet games per day
    for (int i = 0; i < days; i++) {
        std::cout << "Day " << i << std::endl;
        for (int j = 0; j < games; i++) {
            std::cout << "  A game " << 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;
// task: divide all even numbers from numbers_in by 2
// and record the results in numbers_out
std:vector<int> intermediate;
// copy only even numbers into intermediate
std::copy_if(numbers_in.begin(), numbers_in.end(),  
             std::back_inserter(intermediate), 
             [](int x) {
                        return x % 2 == 0;
             }
);
// divide them by 2
std::transform(intermediate.begin(), intermediate.end(),
               std::back_inserter(numbers_out),
               [](int x) {
                          return x / 2;
               }
)

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

Что есть у других

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

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

# transform_if in one line using the language:
numbers_out = [x // 2 for x in numbers_in if x % 2 == 0]

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

days = 3   # number of days with games
games = 2  # number of pet games per day
for i in range(days):
    print("Day %d" % i)
    for j in range(games):
        print("  A game %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. Например, так выглядят циклы — обычные, перебирающие все целые числа через определенный интервал:

#include <iostream>
#include <ranges>
namespace rng = std::ranges;
namespace view = rng::views;
int main() {
    const int days = 3;   // number of days with games
    const int games = 2;  // number of pet games per day
    for (int i : view::iota(0, days)) {
        std::cout << "Day " << i << std::endl;
        for (int j : view::iota(0, games)) {
            std::cout << "  A game " << 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
    }
}

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

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

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

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

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

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

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

Еще один бенчмарк, сравнивающий transform_if старую реализацию и новую, основанную на <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. Это необходимо в шаблоне функции, чтобы он принимал объекты диапазона только с точки зрения диапазонов.

В 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();
    // like before
    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, который сравнивает с помощью операции ‹, но благодаря проекции применяется не к элементам вектора, а к значениям лямбда-функции.

Теория

Вернемся к примеру с 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> можно смело использовать.