A little research on the use of functors in the standard library STL C ++

This article is for beginners. The use of simple functors in algorithms is considered. It is told about the copying designer. The main goal is to study the number of objects created by functors and simple methods of how this can be done. The sample program is sequentially complicated. Some steps may seem wrong and unnecessary, but this is a typical process of research and debugging. This approach is deliberately chosen. The usual way, when only reasonable steps are taken, is far from reality. And to intrigue, I will say that at the end of the article we get a very unexpected result.

So, let's begin.
For simplicity, we assume that the std namespace is added:

using namespace std; 

Suppose we have a container with objects. In our case, this is a vector with inta.

 vector<int> mas; for( int k = 1; k < 10; k++ ) { mas.push_back(k*10); } 

And we want to print it. You can do this:

 for( int curr = 0; curr < mas.size(); curr++ ) { cout<<"value="<<mas[curr]<<endl; } 

or better with iterators:

 for( vector<int>::iterator iter = mas.begin(); iter != mas.end(); iter++ ) { cout<<"value="<<*iter<<endl; } 

more correctly, but longer.

But it is better not to use the usual for loop, but to take the for_each algorithm, which itself goes through the elements of the container and calls the specified function for each. This will allow you to write more visual code. The for_each algorithm takes the beginning and end of the range and a function as input.
As such a function we will use a functor that will draw a conclusion. A functor is an object that is used as a function. It sounds scary, but really simple. In this case, the functor is a class in which the operator of the bracket operator () is implemented.

 class Print { public: void operator() (int value) { cout<<"value="<<value<<endl; } }; 

The operator will accept an object for processing as a parameter. Now the algorithm can be called as follows:

 for_each( mas.begin(), mas.end(), Print() ); 

Beautiful and neat. What happens when this happens? We create a nameless Print object, which is passed to the for_each function, which iterates through the elements from the first to the last and passes them to the operator () function.
The whole program will look like this:

 #include <iostream> #include <vector> #include <algorithm> using namespace std; class Print { public: void operator() (int value) { cout<<"value="<<value<<endl; } }; int main() { vector<int> mas; for( int k = 1; k < 10; k++ ) { mas.push_back(k*10); } for_each( mas.begin(), mas.end(), Print() ); return 0; } 

It's simple. And now the question is, how many objects of the class Print will be created? It can be assumed that one, when creating an unnamed object with the command Print ().
Add a constructor, destructor and debug output to see the process of creating and deleting objects. Now the class will look like this:

 class Print { public: Print() { cout<<"Print::Print()"<<endl; } ~Print() { cout<<"Print::~Print()"<<endl; } void operator() (int value) { cout<<"value="<<value<<endl; } }; 

Run:

  Print :: Print ()
 value = 10
 value = 20
 value = 30
 value = 40
 value = 50
 value = 60
 value = 70
 value = 80
 value = 90
 Print :: ~ Print ()
 Print :: ~ Print () 

How interesting. One constructor, and two destructors. How can this be? If you call a destructor for an object that has already been deleted, there will be unpredictable behavior. It can not be. Let's try to figure it out. And here we must remember that an object can be created not only in the usual way, but also using a copy constructor. This is the constructor that creates the new object, as a copy of the transferred.

 Print(const Print& print) { cout<<"Print::Print(const Print& )"<<endl; } 

In this case, our object does not contain any data, so we do not copy anything. But we must remember that if we replace our standard copy constructor with our own, then all responsibility falls on us.
All code:

 #include <iostream> #include <vector> #include <algorithm> using namespace std; class Print { public: Print() { cout<<"Print::Print()"<<endl; } Print(const Print& print) { cout<<"Print::Print(const Print& )"<<endl; } ~Print() { cout<<"Print::~Print()"<<endl; } void operator() (int value) { cout<<"value="<<value<<endl; } }; int main() { vector<int> mas; for( int k = 1; k < 10; k++ ) { mas.push_back(k*10); } for_each( mas.begin(), mas.end(), Print() ); return 0; } 

Conclusion:

  Print :: Print ()
 value = 10
 value = 20
 value = 30
 value = 40
 value = 50
 value = 60
 value = 70
 value = 80
 value = 90
 Print :: Print (const Print &)
 Print :: ~ Print ()
 Print :: ~ Print () 

Well, it became better, two constructors, two destructors. But why are there two objects? About the first object is clear, it is created in our code. In the second one, it is created even after the entire output is processed. What for?
Let's look at the description of the for_each function:

 Function for_each(InputIterator first, InputIterator last, Function fn); 

Here, the function returns a functor that we never used. Add the result.

 Print p = for_each( mas.begin(), mas.end(), Print() ); 

We start.
')

  Print :: Print ()
 value = 10
 value = 20
 value = 30
 value = 40
 value = 50
 value = 60
 value = 70
 value = 80
 value = 90
 Print :: Print (const Print &)
 Print :: ~ Print ()
 Print :: ~ Print () 

The conclusion has not changed at all. That is, it was an invisible variable that was passed to us, but we ignored it.
Let's do something similar, but with the transform algorithm. This algorithm iterates over the elements of one container, converts them, and places them in another container. We multiply by 10 and put the result back into the original container.

 #include <iostream> #include <vector> #include <algorithm> using namespace std; class Mul { public: Mul() { cout<<"Mul::Mul()"<<endl; } Mul(const Mul& muk) { cout<<"Mul::Mul(const Mul& )"<<endl; } ~Mul() { cout<<"Mul::~Mul()"<<endl; } int operator() (int value) { cout<<"value="<<value<<endl; return value*10; } }; int main() { vector<int> mas; for( int k = 1; k < 10; k++ ) { mas.push_back(k); } transform( mas.begin(), mas.end(), mas.begin(), Mul() ); return 0; } 

Conclusion:

  Mul :: Mul ()
 value = 1
 value = 2
 value = 3
 value = 4
 value = 5
 value = 6
 value = 7
 value = 8
 value = 9
 Mul :: ~ Mul () 

Well, everything is clear, transform does not return any functors, so only one temporary object is created.
And now the most interesting:
Sort algorithm

 void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); 

The question is how many objects of type Compare will be created? One? And no. Make a vector of three elements and sort. We will need to create a functor that compares two objects, this operator is less than operator <, which takes two objects as input and returns true if the first is considered less than the second.

 #include <iostream> #include <vector> #include <algorithm> using namespace std; class Compare { public: Compare() { cout<<"Compare::Compare()"<<endl; } Compare(const Compare& compare) { cout<<"Compare::Compare(const Compare& )"<<endl; } ~Compare() { cout<<"Compare::~Compare()"<<endl; } bool operator() (int v1, int v2) { cout<<"compare "<<v1<<" "<<v2<<endl; return v1 < v2; } }; int main() { vector<int> mas; for( int k = 1; k <= 3; k++ ) { mas.push_back( rand() ); } sort( mas.begin(), mas.end(), Compare() ); return 0; } 

Conclusion:

  Compare :: Compare ()
 Compare :: Compare (const Compare &)
 Compare :: ~ Compare ()
 Compare :: Compare (const Compare &)
 Compare :: Compare (const Compare &)
 compare 18467 41
 Compare :: Compare (const Compare &)
 compare 18467 41
 Compare :: ~ Compare ()
 compare 6334 41
 Compare :: Compare (const Compare &)
 compare 6334 18467
 compare 6334 41
 Compare :: ~ Compare ()
 Compare :: ~ Compare ()
 Compare :: ~ Compare ()
 Compare :: ~ Compare () 

This is a surprise, five comparisons and six functors!
Well, our one when calling a function, and the rest uses sorting. Why are they there? Most likely due to the recursiveness of the sorting algorithm, where each recursive call creates a new copy that must be passed to the function.
And now let's calculate how many such objects will be on average when sorting large arrays. Add a counter and remove the entire output. The counter is implemented as a static member of the class, which will be one for all created instances.

 #include <iostream> #include <vector> #include <algorithm> using namespace std; class Compare { public: static int num; Compare() { num++; } Compare(const Compare& compare) { num++; } ~Compare() { } bool operator() (int v1, int v2) { return v1 < v2; } }; int Compare::num = 0; int main() { vector<int> mas; int size = 10000; for( int k = 1; k <= size; k++ ) { mas.push_back( rand() ); } sort( mas.begin(), mas.end(), Compare() ); float rate = (float)Compare::num/(float)size; cout<<"rate="<<rate<<endl; return 0; } 

The output of the program:

  rate = 1.4582 

For arrays of a million elements, the value is about the same. Honestly, for me it was a big surprise. That is, on average, one and a half of the functor is created for each element of the sorting array! It’s good that the complexity is linear and it doesn’t affect the total running time of the algorithm so much. What are the conclusions? If your functor contains a lot of data and has a complex copy constructor, then this can lead to a loss of performance.

Literature:
1. Coat of arms of Sutter, Andrei Alexandrescu. C ++ Programming Standards: Trans. from English - M .: Izd. Williams House, 2005.
2. www.cplusplus.com