We use standard algorithms in C++. Seven examples
All examples are taken from a real project. In order not to clutter the examples, the code of these functions has been simplified for better understanding.
Before moving on to examples, it is necessary to note the main advantage of algorithms: they allow you to simplify the code and increase readability (or self-documentation, which allows you to understand what is being done based on the name of the algorithm), and generalize the code. Starting with C++17, algorithms can be executed in parallel; the implementation of the algorithm can be rigidly optimized by the compiler compared to regular code.
The examples will use the following algorithms:
accumulate – the function calculates the sum of the elements of the range.
any_of – the function returns true if at least one of the elements of the range satisfies the condition.
copy, copy_if – the function copies the elements of one range to another.
count, count_if – the function returns from a given range the number of elements that satisfy the condition.
fill – the function sets values for the range elements.
find, find_if – the function returns an iterator of the first element of the range that satisfies the condition.
partition, stable_partition – the function divides the range into 2 groups and returns an iterator to the separator. stable_partition preserves the order of the elements.
transform – the function modifies the elements of a range and stores them in another range.
And helper functions:
distance – the function returns the distance between two iterators.
prev – the function returns the previous iterator n-iterator
next – the function returns the next iterator n-iterator
exchange – the function changes the current value of the variable to a new one and returns the old value.
clamp – the function clamps the specified value between the lower and upper limits.
First, let's look at the most popular patterns in code:
1. Search:
for (auto&& item : container){
if (...)
{
//Что-то делаем с элементом item
//Тут может быть return или break
}
}where container is any standard library container.
This loop is replaced by the find or find_if algorithm, depending on the search criteria.
2. Search, but you only need to check for the presence of the element:
for (auto&& item : container){
if (...)
{
//Что-то делаем и выходим из цикла
}
}This loop is replaced by the any_of algorithm.
3. Quantity counting:
int count = 0;
for (auto &&item : container)
{
count++;
}
Или
int count = 0;
for (auto &&item : container)
{
if (…)
count++;
}This loop is replaced by the count or count_if algorithm, depending on whether the condition exists.
4. Sum value:
int sum = 0;
for (auto&& item : container){
sum += item;
}
или
int sum = 0;
for (auto&& item : container){
if(...){
sum += item;
}
}This loop is replaced by the accumulate algorithm.
5. Copy:
for (auto&& item : container){
new_container.push_back(item);
}
Или
for (auto&& item : container){
if(...){
new_container.push_back(item);
}
}Containers may vary in type. For example, copy from vector to list.
This loop is replaced by the copy or copy_if algorithm, depending on the condition.
6. Conversion:
for (auto&& item : container){
item = foo(item);
}
Либо складываем в другой контейнер
for (auto&& item : container){
new_container.push_back(foo(item));
}This loop is replaced by the transform algorithm.
Let's start looking at the use of algorithms with simple examples.
Example No. 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;
}
}Since in the example the array elements are assigned 0, the fill algorithm is suitable in this case:
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);
}As you can see, the code is growing, and writing such code is not advisable. But by replacing the loop with the fill function, we thereby solved the following problems:
If at least the size of one array changes, we do not need to rewrite anything, as would be the case with a loop.
If the container type was changed to, for example, a list, then you would have to write separate code to traverse the list. The algorithm eliminates this, since it is applicable to any standard containers.
Example No. 2.
This example is more theoretical, but sometimes occurs in practice.
int main(){
std::list<std::string> list_str;
//Заполнение контейнера list_str
...
std::string str;
for(auto &&i : list_str){
str += i;
}
}The example is intended to show that the accumulate algorithm can be applied not only to numeric types. After applying the algorithm, the example will look like this.
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>());
}Example No. 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++;
}
}From the loop implementation it is clear that this is a search pattern and can be replaced with the find algorithm. As a result, the code will look like this:
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));
}
}Example No. 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;
}As in the previous example, the search pattern can be traced here, but the difference is that we don’t need the element itself, just fulfilling the condition is enough. The any_of algorithm is suitable for this.
bool hasMid(std::string_view mid){
return std::any_of(entries.begin(), entries.end(), [mid](auto entry){
return entry.mid() == mid;
});
}Further examples will be more complicated.
Example No. 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];
}
}From the line vec_2[i] = temp.vec[i]; You can see that the container is being copied element-by-element; here you can apply the copy algorithm.
From the body of the loop, you can see that the first element of the vec_1 container is assigned a new value, and the rest are already calculated based on the vec_2 container. This assignment can be placed outside the loop and at the same time get rid of the condition. For the remaining elements, the transform algorithm is suitable, since we are changing the elements of the container.
The final form of the func method will look like this:
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>());
}Example No. 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;
}The first loop in the example immediately suggests replacing the count algorithm. The second loop is less obvious; the transform_if algorithm is visible from it, but such a function is not in the standard library. As a result, the cycle can be divided into 2 algorithms, copy_if and transform, but this will require creating another container where, according to the condition, the elements of the users container will be copied. The very idea of creating an additional buffer does not look very good; I would like to use the current container and rearrange the elements.
For such a case, there is a partition algorithm; if you need to preserve the order of the elements, then it is better to use stable_partition. As a result, the function will look like this.
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;
}Example No. 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;
}
}As you can see, I don’t even want to read this code – it’s too cumbersome. But it can be simplified by noting that the values of new_x, new_y, new_w and new_h are calculated according to the same rules. If the new value falls within the boundaries, then it does not change; if it goes beyond the boundaries, then we tighten it to the nearest one. For this purpose, the standard library has a clamp function.
You can also notice that the pointPress_ variable is used, and then a new value is assigned to it; the exchange function is suitable here. As a result, after applying the data to the function and changing the conditions, the function code will look like this.
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();
}
}Conclusion
In this article, we looked at the use of algorithms in everyday code and the criteria by which they can be selected. The main emphasis was placed on replacing conventional loops with algorithms in order to learn how to turn complex and confusing code into more readable and concise code.
Thank you for your attention!
Read more original materials for backend developers from my colleagues on SimbirSoft’s social networks – In contact with And Telegram.
