Возможности С++: от стандартных алгоритмов до диапазонов (Ranges)

Привет, Хабр! Меня зовут Николай, я разработчик С++ в SimbirSoft. В предыдущей статье мы с вами рассмотрели применение стандартных алгоритмов в повседневном коде и их преимущества над обычными циклами. В продолжение этой темы мне хотелось бы рассказать о недостатках стандартных алгоритмов и способах их решения с помощью библиотеки Ranges. Практические примеры я разбил на три части: в первой показаны обычные циклы, во второй — вариант написания с помощью алгоритмов (но не всегда можно это сделать), в третьей — с использованием Ranges. Этот материал будет полезен тем разработчикам, которые хотят применять новые стандарты и подходы у себя на проектах.

Мы не будем подробно разбирать библиотеку Ranges, поскольку о ней в сети есть много различных статей, например, как это руководство. Поэтому для начала обратимся к описанию используемых адаптеров в Ranges (так как не совсем корректно называть этот термин функцией, здесь и далее буду использовать слово адаптер):

ranges::iota_view(views::iota) – данный адаптер генерирует последовательность элементов путем многократного увеличения начального значения. Хотя в описании сказано, что функция генерирует последовательность, но на самом деле возвращается легковесный объект, который выдаёт значения в ограниченном или в бесконечном диапазоне.

ranges::stride_view(views::stride) — возвращает последовательность из элементов другой последовательности с заданным шагом.

ranges::filter_view(views::filter) — аналог copy_if, за исключением того, что он не создаёт новый объект, а возвращает отображения на диапазон элементов, удовлетворяющих условию.

ranges::transform_view(views::transform) — аналог std::transform.

ranges::to — создает новый объект на основании входного отображения.

ranges::take_view(views::take) — возвращает первые N элементов последовательности.

ranges::drop_view(views::drop) — возвращает элементы последовательности, начиная с N.

ranges::chunk_view(views::chunk) — разделяет заданный диапазон на поддиапазоны с заданным количеством элементов. Последний поддиапазон может не совпадать с заданным количеством элементов.

ranges::join_with_view(views::join_with) — объединяет несколько диапазонов в один, добавляя между ними разделитель.

ranges::join_view(views::join) — объединяет несколько диапазонов в один.

ranges::adjacent_transform_view(views::adjacent_transform) — адаптер применяет функцию к смежным элементам, их количество задается шаблонным параметром. 

Итак, перейдем к практической части, где мы рассмотрим проблемы, возникающие при работе со стандартными алгоритмами в С++ .

1) Непростой квест с обычной последовательностью чисел

struct Rect { //... std::array<int, 4> buffer = { 0,0,0,0 }; }; struct ContainerRect { std::vector<Rect> rectangles; void calc(int index, int width, int height) { Rect rect; //... rectangles.push_back(std::move(rect)); } }; void fill(int count_rect, int width, int height) { ContainerRect container; for (int i = 0; i < count_rect; ++i) { container.calc(i, width, height); } //... }

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

void fill(int count_rect, int width, int height) { ContainerRect container; std::vector<int> numbers; numbers.resize(count_rect); std::iota(std::begin(numbers), std::end(numbers), 0); std::for_each(std::begin(numbers), std::end(numbers), [&](auto item) { container.calc(item, width, height); }); //... }

Из примера выше видно — для того чтобы пройтись по числовой последовательности, необходимо создать контейнер соответствующего размера, а это — дополнительное использование памяти. Также нужно заполнить контейнер последовательностью значений. Если значение count_rect невелико, то выделение памяти не так и уж критично, но при большом диапазоне стандартными инструментами пользоваться будет накладно.

Вид функций fill при использовании Ranges:

void fill(int count_rect, int width, int height) { ContainerRect container; const auto numbers = std::ranges::iota_view{ 0, count_rect}; std::for_each(std::begin(numbers), std::end(numbers), [&](auto item) { container.calc(item, width, height); }); //... }

Если нужно итерироваться с определённым шагом, то стандартные алгоритмы вряд ли помогут, но в Ranges есть такой адаптер, как std::ranges::views::stride.

И данный цикл:

for (int i = 0; i < count; i += 3) { ... }

будет эквивалентен следующей конструкции:

for (auto&& i : std::ranges::iota_view{0, count_rect} | std::ranges::views::stride(3)) { ... }

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

Для контейнеров применение std::ranges::views::stride будет выглядеть таким образом:

std::string s = "qwertyuiop"; auto res = s | std::ranges::views::stride(4);

2) Ограничитель

Из предыдущего примера можно заметить, что в функцию std::for_each передавался ограничитель (std::end). Алгоритмы из пространства имён Ranges позволяют передавать как сам объект std::ranges::iota_view, так и контейнеры без использования begin и end. После этого функция fill принимает следующий вид:

void fill(int count_rect, int width, int height) { ContainerRect container; std::ranges::for_each(std::ranges::iota_view{ 0, count_rect }, [&](auto item) { container.calc(item, width, height); }); //... }

Использование контейнера в адаптере будет выглядеть следующим образом:

std::vector<int> temp; std::ranges::transform_view(temp, [](auto item) { return item * 10; });

Здесь хотелось бы кратко отметить: если не писать ограничитель, то можно нарваться на проблему провисшего итератора, но она решается с помощью типа std::ranges::dangling, что позволит компилятору выдавать сообщение об ошибке.

Пример провисшего итератора:

std::vector<int> get_vector() { std::vector<int> temp; //... return temp; } int main() { auto item = std::ranges::find(get_vector(), 10); std::cout << item << std::endl; }

3) Проблема энергичного поведения

struct Point { int x; int y; }; using Points = std::vector<Point>; using VecString = std::vector<std::string>; VecString calc(const Points& points, int pos) { VecString temp; for (auto&& it : points) { if (it.y > pos) { temp.push_back("x=" + std::to_string(it.x) + " y=" + std::to_string(it.y)); } } return temp; }

В данном примере нужно использовать два алгоритма — это copy_if и transform. Так как алгоритмы выполняются последовательно, необходим дополнительный контейнер для хранения отфильтрованных данных. В итоге функция calc будет выглядеть следующим образом:

VecString calc(const Points& points, int pos) { Points t; std::copy_if(points.begin(), points.end(), std::back_inserter(t), [pos](auto it) { return it.y > pos; }); VecString temp; std::transform(t.begin(), t.end(), std::back_inserter(temp), [](auto it) { return "x=" + std::to_string(it.x) + " y=" + std::to_string(it.y); }); return temp; }

А вот функция, переписанная с помощью Ranges: 

VecString calc(const Points& points, int pos) { return points | std::ranges::views::filter([pos](auto it) {return it.y > pos; }) | std::ranges::views::transform([](auto it) { return "x=" + std::to_string(it.x) + " y=" + std::to_string(it.y); }) | std::ranges::to<VecString>(); }

Данная реализация похожа на конвейер (что является еще одним преимуществом), где каждый элемент (разделённый оператором «|») проходит все шаги, если он удовлетворяет условию, до конечного результата. Это позволяет выполнять код лениво и без лишних выделений памяти.

4) Проблема использования полей структуры или класса в алгоритмах

struct User { int id; std::string name; }; std::vector<int> get_id_users(const std::vector<User> &users) { std::vector<int> vector_id; for (auto&& i : users) { vector_id.push_back(i.id); } return vector_id; }

Вариант с использованием алгоритма transform:

std::vector<int> get_id_users(const std::vector<User>& users) { std::vector<int> vector_id; std::transform(users.begin(), users.end(), std::back_inserter(vector_id), [](auto item) { return item.id; }); return vector_id; }

Как видно из примера, для копирования поля структуры необходимо в transform передать лямбду и оттуда возвращать конкретное поле. В Ranges введено понятие проекций, которое позволяет указывать, какое поле структуры мы хотим использовать. Окончательный вариант будет таким:

std::vector<int> get_id_users(const std::vector<User>& users) { std::vector<int> vector_id; std::ranges::transform(users, std::back_inserter(vector_id), &User::id); return vector_id; }

В предыдущей статье мы разобрали пример с применением алгоритмов, продублирую его в итоговом варианте:

std::vector<int> getIdUser() { int k = std::count_if(users.cbegin(), users.cend(), [](auto i) { return i.flag_2; }); if (std::exchange(k, count - k) >= count) { return {}; }; auto end = std::stable_partition(users.begin(), users.end(), [&k](auto i) { return i.flag_1 && i.flag_2 && (k-- > 0); }); std::vector<int> id_users; std::transform(users.begin(), end, std::back_inserter(id_users), [](auto i) { return i.id; }); return id_users; }

Здесь есть явный недостаток в условии stable_partition (k— > 0), который будет проверяться для всех элементов. В Ranges есть специальный адаптер для ограничения std::ranges::views::take. С имеющимися знаниями о Ranges этот вариант можно упростить следующем образом:

std::vector<int> getIdUser_range() { int k = std::ranges::count_if(users.cbegin(), users.cend(), &User::flag_2); if (std::exchange(k, count - k) >= count) { return {}; }; auto temp = users | std::ranges::views::filter([](auto item) {return item.flag_1 && item.flag_2; }) | std::ranges::views::take(k); std::vector<int> id_users; std::ranges::transform(temp, std::back_inserter(id_users), &User::id); return id_users; }

5) Разбиение и объединение диапазонов

Пример 1

В этом примере функция convert преобразует строку buffer (постоянный размер этой строки – 14), вставляя на позиции 3,5,7,9 разделитель ‘-‘.

std::string convert(const std::string& buffer) { std::string uuid; for (int i = 0, count = buffer.size(); i < count; ++i) { uuid.push_back(buffer[i]); if ((i == 3) || (i == 5) || (i == 7) || (i == 9)) { uuid.push_back('-'); } } return uuid; }

Для данного примера нет алгоритмов, которые смогли бы решить данную задачу. Поэтому сразу перейду к Ranges. Здесь будем использовать следующие адаптеры: std::ranges::views::chunk и std::ranges::views::join_with. В итоге функция convert примет вид:

std::string convert(const std::string& buffer) { using namespace std::ranges::views; using namespace std::ranges; auto res1 = buffer | take(4) | to<std::string>(); auto res2 = buffer | drop(buffer.size() - 4) | to<std::string>(); auto res3 = buffer | drop(4) | take(2 * 4) | chunk(2) | join_with('-') | to<std::string>(); return std::vector<std::string_view>{ res1, res3, res2 } | join_with('-') | to<std::string>(); }

Пример 2

В этом пример необходимо расшифровать строку (длина которой кратна 4) по определённому правилу, где 4 символа преобразуются в 3.

int convert(char symbol) { int value; //... return value; } std::string decode(std::string temp) { size_t buffer_size = temp.length() * 3 / 4 + 1; std::string buffer; buffer.resize(buffer_size); for (size_t i = 0; i < temp.length(); i += 4) { int b_index = i * 3 / 4; unsigned char values[4]; values[0] = convert(temp[i]); values[1] = convert(temp[i + 1]); values[2] = convert(temp[i + 2]); values[3] = convert(temp[i + 3]); buffer[b_index] = (values[0] << 0x2) ^ (values[1] >> 0x4); buffer[b_index + 1] = ((values[1] & 0xF) << 0x4) ^ (values[2] >> 0x2); buffer[b_index + 2] = ((values[2] & 0x3) << 0x6) ^ values[3]; } buffer[buffer_size - 1] = 0x0; return buffer; }

Здесь можно применить алгоритм transform, а основной цикл оставить без изменения.

std::string decode(const std::string &temp) { std::string str; std::transform(temp.cbegin(), temp.cend(), std::back_inserter(str), [](auto item) { return convert(item); }); std::string buffer(str.length() * 3 / 4 + 1, '\0'); for (size_t i = 0; i < str.length(); i += 4) { int b_index = i * 3 / 4; int index = i % 4; buffer[b_index] = (str[index] << 0x2) ^ (str[index + 1] >> 0x4); buffer[b_index + 1] = ((str[index + 1] & 0xF) << 0x4) ^ (str[index + 2] >> 0x2); buffer[b_index + 2] = ((str[index + 2] & 0x3) << 0x6) ^ str[index + 3]; } return buffer; }

Как и в предыдущем примере, будем использовать адаптер std::ranges::views::chunk для разделения, а для объединения – std::ranges::views::join, так как нам нужно просто объединить поддиапазоны без разделителя.

std::string decode(const std::string& temp) { auto temps = temp | std::ranges::views::transform([](auto item) {return convert(item); }) | std::ranges::views::chunk(4); std::string buffer(3 * temps.size(), '\0'); auto chunk_buf = buffer | std::ranges::views::chunk(3) | std::ranges::views::transform([it = &temps.begin()](auto item) { auto old = *std::exchange(*it, std::next(*it)); item[0] = (old[0] << 0x2) ^ (old[1] >> 0x4); item[1] = ((old[1] & 0xF) << 0x4) ^ (old[2] >> 0x2); item[2] = ((old[2] & 0x3) << 0x6) ^ old[3]; return item; }) | std::ranges::views::join | std::ranges::to<std::string>(); chunk_buf.push_back('\0'); return chunk_buf; }

6) Использование элементов одного контейнера в вычислении

В примере приведен вектор с множеством точек, где между двумя точками нужно вычислить промежуточные точки с помощью функции get_splitting_segment.

struct Point { int x; int y; int z; }; std::vector<Point> get_points(const std::vector<Point>& points) { auto get_splitting_segment = [](const Point& p1, const Point& p2) { std::vector<Point> points; //... return points; }; std::vector<Point> result; for (int i = 0, size = points.size() - 1; i < size; ++i) { auto temp = get_splitting_segment(points[i], points[i + 1]); for (auto&& i : temp) { result.push_back(std::move(i)); } } return result; }

С использованием алгоритмов функция get_points будет выглядеть так:

std::vector<Point> get_points(const std::vector<Point>& points) { auto get_splitting_segment = [](const Point& p1, const Point& p2) { std::vector<Point> points; //... return points; }; std::vector<std::vector<Point>> temp; std::transform(points.begin(), std::prev(points.end()), std::next(points.begin()), temp, get_splitting_segment); std::vector<Point> result; std::for_each(temp.cbegin(), temp.cend(), [&result](auto item) { std::copy(item.cbegin(), item.cend(), std::back_inserter(result)); }); return result; }

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

В Ranges для таких случаев существуют специальные адаптеры ranges::views::adjacent или ranges::views::adjacent_transform. Второй нам подходит больше. Тогда получаем в итоге:

std::vector<Point> get_points(const std::vector<Point> &points) { auto get_splitting_segment = [](const Point& p1, const Point& p2) { std::vector<Point> points; //... return points; }; auto view = points | std::ranges::views::adjacent_transform<2>(get_splitting_segment) | std::ranges::views::join; }

Заключение

В этой статье мы с вами рассмотрели практические примеры кода на С++, где применение стандартных алгоритмов проблематично или совсем невозможно, а также решение этих проблем с новым механизмом абстракции Ranges. У библиотеки Ranges есть ряд преимуществ:

• итерация по числовой последовательность, с ограничением и без;

• энергичное поведение;

• отображения для использования внутренних полей класса;

• новые адаптеры, аналогов которых нет в алгоритмах.

А также свои недостатки: 

• небольшое количество адаптеров по сравнению со списком алгоритмов; 

• нельзя распараллелить вычисления;

• на существующих реализациях компиляторов Ranges плохо оптимизированы. 

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