Привет, Хабр! Меня зовут Николай, я разработчик С++ в SimbirSoft. В этой статье я хочу поделиться своим опытом применения алгоритмов.
Каждый из нас знает, что существуют алгоритмы стандартной библиотеки, и что они делают. Но не все и не всегда используют их. Я тоже их не использовал до той поры, пока не узнал, когда их применять.
Все примеры взяты из реального проекта. Чтобы не загромождать примеры, код этих функций был упрощён для лучшего восприятия.
Прежде чем перейти к примерам, необходимо отметить основное преимущество алгоритмов: они позволяют упростить код и повысить читаемость (или самодокументирование, которое позволяет на основании названия алгоритма понять, что делается), обобщить код. Начиная с C++17, алгоритмы могут выполняться параллельно, реализация алгоритма может быть жестко с оптимизирована компилятором по сравнением с обычным кодом.
В примерах будут использоваться следующие алгоритмы:
accumulate – функция вычисляет сумму элементов диапазона.
any_of – функция возвращает true, если хотя бы один из элементов диапазона удовлетворяет условию.
copy, copy_if – функция копирует элементы одного диапазона в другой.
count, count_if – функция возвращает из заданного диапазона количество элементов удовлетворяющих условию.
fill – функция задаёт значения элементам диапазона.
find, find_if – функция возвращает итератор первого элемента диапазона, удовлетворяющий условию.
partition, stable_partition – функция делит диапазон на 2 группы и возвращает итератор на разделитель. stable_partition при этом сохраняет порядок элементов.
transform – функция модифицирует элементы диапазона и сохраняет в другом диапазоне.
И вспомогательные функции:
distance – функция возвращает расстояние между двумя итераторами.
prev – функция возвращает предыдущий итератор n-итератор
next – функция возвращает следующий итератор n-итератор
exchange – функция изменяет текущие значение переменной на новое и возвращает старое значение.
clamp – функция зажимает заданное значение между нижний и верхний границей.
Сначала рассмотрим наиболее популярные паттерны в коде:
1. Поиск:
for (auto&& item : container){
if (...)
{
//Что-то делаем с элементом item
//Тут может быть return или break
}
}где container — это любой контейнер стандартной библиотеки.
Данный цикл заменяется алгоритмом find или find_if в зависимости от критерия поиска.
2. Поиск, но нужно только проверить наличие элемента:
for (auto&& item : container){
if (...)
{
//Что-то делаем и выходим из цикла
}
}Данный цикл заменяется алгоритмом any_of.
3. Подсчёт количества:
int count = 0;
for (auto &&item : container)
{
count++;
}
Или
int count = 0;
for (auto &&item : container)
{
if (…)
count++;
}Данный цикл заменяется алгоритмом count или count_if в зависимости от того, есть ли условие.
4. Суммирование значения:
int sum = 0;
for (auto&& item : container){
sum += item;
}
или
int sum = 0;
for (auto&& item : container){
if(...){
sum += item;
}
}Данный цикл заменяется алгоритмом accumulate.
5. Копирование:
for (auto&& item : container){
new_container.push_back(item);
}
Или
for (auto&& item : container){
if(...){
new_container.push_back(item);
}
}Контейнеры по типу могут быть разные. К примеру, из vector копируем в list.
Данный цикл заменяется алгоритмом сopy или copy_if в зависимости от того если условие.
6. Преобразование:
for (auto&& item : container){
item = foo(item);
}
Либо складываем в другой контейнер
for (auto&& item : container){
new_container.push_back(foo(item));
}Данный цикл заменяется алгоритмом transform.
Начнём рассмотрение применения алгоритмов с простых примеров.
Пример №1
int main(){
int pitch[4];
int visiblePitch[4];
int lines[4];
int visibleLines[4];
for (int i = 0; i < 4; ++i) {
pitch[i] = 0;
visiblePitch[i] = 0;
lines[i] = 0;
visibleLines[i] = 0;
}
}Так как в примере элементам массива присваивается 0, то в данном случае подходит алгоритм fill:
int main(){
int pitch[4];
int visiblePitch[4];
int lines[4];
int visibleLines[4];
std::fill(std::begin(pitch), std::end(pitch), 0);
std::fill(std::begin(visiblePitch), std::end(visiblePitch), 0);
std::fill(std::begin(lines), std::end(lines), 0);
std::fill(std::begin(visibleLines), std::end(visibleLines), 0);
}Как можно заметить, код увеличивается, и написание такого кода не целесообразно. Но заменив цикл на функцию fill, мы тем самым решили такие проблемы:
Если изменится хотя бы размер у одного массива, нам не нужно ничего переписывать, как было бы с циклом.
Если тип контейнера поменялся, к примеру, на список, то пришлось бы писать отдельный код для прохода по списку. Алгоритм избавляет от этого, так как он применим к любым стандартным контейнерам.
Пример №2.
Этот пример является больше теоретическим, но иногда встречается в практике.
int main(){
std::list<std::string> list_str;
//Заполнение контейнера list_str
...
std::string str;
for(auto &&i : list_str){
str += i;
}
}Пример нацелен показать, что алгоритм accumulate можно применять не только в числовым типам. После применения алгоритма пример будет выглядеть следующим образом.
int main(){
using Acc = std::string;
std::list<Acc> list_str;
//Заполнение контейнера list_str
...
auto str = std::accumulate(std::begin(list_str), std::end(list_str), Acc(), std::plus<Acc>());
}Пример №3.
struct User{
int id;
};
struct Users{
void func(const User &item);
void changed(int row);
std::vector<User> items;
};
void Users::func(const B& item)
{
int row = 0;
for (auto&& i : items)
{
if (item.id == i.id)
{
i = item;
changed(row);
return;
}
row++;
}
}Из реализации цикла видно, что это паттерн поиска и его можно заменить на алгоритм find. В итоге код будет выглядеть следующим образом:
void Users::update(const B& item)
{
auto it = std::find_if(items.begin(), items.end(), [id = item.id](auto i){
return i.id == id;
});
if(it != items.end()){
*it = item;
changed(std::distance(items.begin(), it));
}
}Пример №4.
struct Entry{
std::string mid() const;
};
std::vector<Entry> entries;
bool hasMid(std::string_view mid) {
for (const auto &entry : entries)
if (entry.mid() == mid)
return true;
return false;
}Как и в предыдущем примере, здесь прослеживается паттерн поиск, но отличие в том, что сам элемент нам не нужен, достаточно только выполнения условия. Для этого подойдёт алгоритм any_of.
bool hasMid(std::string_view mid){
return std::any_of(entries.begin(), entries.end(), [mid](auto entry){
return entry.mid() == mid;
});
}Дальше примеры уже будут посложнее.
Пример №5.
struct Temp{
int a;
std::vector<int> vec;
};
class A{
public:
void func(const Temp &temp);
private:
std::vector<int> vec_1;
std::vector<int> vec_2;
};
void A::func(const Temp &temp)
{
for (size_t i = 0; i < vec_1.size(); i++) {
if (i > 0)
vec_1[i] = vec_1[i - 1] + vec_2[i - 1];
else
vec_1[0] = temp.a;
vec_2[i] = temp.vec[i];
}
}Из строки vec_2[i] = temp.vec[i]; видно, что идёт поэлементное копирование контейнера, тут можно применить алгоритм copy.
Из тела цикла можно заметить, что первому элементу контейнера vec_1 присваивается новое значение, а остальные уже высчитываются на основании контейнера vec_2. Данное присваивание можно вынести вне цикла, и при этом избавиться от условия. Для остальных элементов подходит алгоритм transform, так как у нас идёт изменения элементов контейнера.
Итоговый вид метода func будет выглядеть так:
void A::func(const Temp &temp)
{
std::copy(temp.vec.begin(), temp.vec.end(), vec_2.begin());
vec_1[0] = temp.a;
std::transform(vec_1.begin(), std::prev(vec_1.end()), vec_2.begin(), std::next(vec_1.begin()), std::plus<int>());
}Пример №6.
struct User{
int id;
bool flag_1;
bool flag_2;
};
std::vector<User> users;
int count;
std::vector<int> getId()
{
int k = 0;
for(auto &&i : users){
(i.flag_2){
++k;
}
}
std::vector<int> id_users;
if (k >= count)
{
return id_users;
}
int d = count - k;
for (auto&& i : users)
{
if (i.flag_1 && i.flag_2)
{
id_users.push_back(i.id);
--d;
}
if (d == 0)
{
break;
}
}
return id_users;
}Первый цикл в примере сразу напрашивается на замену алгоритма count. Второй цикл менее очевидный, из него виден алгоритм transform_if, но такой функции нет в стандартной библиотеке. В итоге можно цикл можно разбить на 2 алгоритма copy_if и transform, но при этом потребуется создать ещё один контейнер, куда по условию будут скопированы элементы контейнера users. Сама идея создания дополнительного буфера выглядит не очень хорошей, хотелось бы использовать текущий контейнер, при этом переставить элементы.
Для такого случая есть алгоритм partition, если нужно сохранить порядок элементов, то лучше применить stable_partition. В итоге функция будет выглядеть следующим образом.
std::vector<int> getIdUser()
{
int k = std::count_if(users.cbegin(), users.cend(), [](auto i){
return i.flag2;
});
if(std::exchange(k, count - k) >= count){
return {};
};
auto end = std::stable_partition(users.begin(), users.end(),[&k](auto i){
return i.flag1 && i.flag2 && (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;
}Пример №7.
void VisualRect::move(MouseEvent *event)
{
auto pos = event->pos();
int d = 10;
if(isPress_){
auto d_pos = pos - pointPress_;
auto new_x = rect_.x() + d_pos.x();
new_x = (new_x < 0) ? 0 : (new_x > (width() - rect_.width())) ? width() - rect_.width() : new_x;
auto new_y = rect_.y() + d_pos.y();
new_y = (new_y < 0) ? 0 : (new_y > (height() - rect_.height())) ? height() - rect_.height() : new_y;
rect_ = Rect(new_x, new_y, rect_.width(), rect_.height());
update();
pointPress_ = pos;
return;
}
if(isPressLeft_){
auto d_pos = pos - pointPress_;
auto new_x = rect_.x() + d_pos.x();
new_x = (new_x < 0) ? 0 : (new_x > (rect_.x() + rect_.width() - d)) ? rect_.x() + rect_.width() - d : new_x;
rect_.setX(new_x);
update();
pointPress_ = pos;
return;
}
if(isPressRight_){
auto d_pos = pos - pointPress_;
auto new_w = rect_.width() + d_pos.x();
new_w = (new_w > width() - rect_.x()) ? width() - rect_.x() : (new_w < d) ? d : new_w;
rect_.setWidth(new_w);
update();
pointPress_ = pos;
return;
}
if(isPressTop_){
auto d_pos = pos - pointPress_;
auto new_y = rect_.y() + d_pos.y();
new_y = (new_y < 0) ? 0 : (new_y > (rect_.y() + rect_.height() - d)) ? rect_.y() + rect_.height() - d : new_y;
rect_.setY(new_y);
update();
pointPress_ = pos;
return;
}
if(isPressBottom_){
auto d_pos = event->pos() - pointPress_;
auto new_h = rect_.height() + d_pos.y();
new_h = (new_h > height() - rect_.y()) ? height() - rect_.y() : (height() < d) ? d : new_h;
rect_.setHeight(new_h);
update();
pointPress_ = event->pos();
return;
}
}Как можно заметить, этот код и читать не хочется — слишком он громоздкий. Но его можно упростить, заметив, что значения new_x, new_y, new_w и new_h вычисляются по одинаковым правилам. Если новое значение попадает в границы, то оно не меняется, если выходит за границы, то стягиваем его к ближайшей. Для это в стандартной библиотеке есть функция clamp.
Ещё можно заметить, что используется переменная pointPress_, а потом ей присваивается новое значение, тут подойдет функция exchange. В итоге после применения данных функция и изменения условий код функции будет выглядеть следующим образом.
void VisualRect::move(MouseEvent *event)
{
auto pos = event->pos();
int d = 10;
if(isPress_){
auto d_pos = pos - std::exchange(pointPress_, pos);
auto new_x = std::clamp(rect_.x() + d_pos.x(), 0, width() - rect_.width());
auto new_y = std::clamp(rect_.y() + d_pos.y(), 0, height() - rect_.height());
rect_ = Rect(new_x, new_y, rect_.width(), rect_.height());
update();
}
else if(isPressLeft_){
auto new_x = rect_.x() + (pos - std::exchange(pointPress_, pos)).x();
rect_.setX(std::clamp(new_x, 0, rect_.x() + rect_.width() - d));
update();
}
else if(isPressRight_){
auto new_w = rect_.width() + (pos - std::exchange(pointPress_, pos)).x();
rect_.setWidth(std::clamp(new_w, d, width() - rect_.x()));
update();
}
else if(isPressTop_){
auto new_y = rect_.y() + (pos - std::exchange(pointPress_, pos)).y();
rect_.setY(std::clamp(new_y, 0, rect_.y() + rect_.height() - d));
update();
}
else if(isPressBottom_){
auto new_h = rect_.height() + (pos - std::exchange(pointPress_, pos)).y();
rect_.setHeight(std::clamp(new_h, d, height() - rect_.y()));
update();
}
}Заключение
В этой статье мы рассмотрели применение алгоритмов в повседневном коде и критерии, по которым их можно выбрать. Основной упор сделали на замещения обычных циклов алгоритмами, чтобы научится превращать сложный и запутанный код в более читаемый и лаконичный.
Спасибо за внимание!
Больше авторских материалов для backend-разработчиков от моих коллег читайте в соцсетях SimbirSoft – ВКонтакте и Telegram.
kovserg
А почему собственно они называются алгоритмами если это просто функции?
SSul Автор
Да всё верно, это функции, но алгоритмами они называются, так как реализуют конкретную последовательность действий, например: поиск, сортировку, разбиение и т.д.
MiyuHogosha
Закрою форточку: это шаблоны функций и функциональных объектов. Т е. Не функции.
Sklott
Потому что в C/C++ все функции - это функции. Тавталогия да. Я это к чему: если назвать этот класс функций просто функциями, то как понять о каких функциях идет речь? А так выделили "функции реализующие стандартные алгоритмы обработки информации" в отдельный "модуль", назвали его "алгоритмы" и всем сразу понятно о чем речь.
Для меня это немного больная тема, т.к. у нас в одном легаси проекте какие-то умники сделали класс Function, от которого наследуются "функции", которые рализуют БЛ. И вот очень блин все время выбешивает когда надо эти классы как-то обозвать...
MiyuHogosha
Класс DefaultFunction и функция DefaultClass. Было, было ...