Привет, Хабр! Меня зовут Николай, я разработчик С++ в 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 плохо оптимизированы.
Возможно, в будущих стандартах эти проблемы устранят.
