Hello again! In this video, we are going to look at algorithms with predicates. Many of the algorithms
work by having a function which they call on each iteration. The function returns bool.
For example, in the find() algorithm, this calls the equality operator on each iteration.
It has the current element as one argument and the target value,
the thing we are sorting for, as the other arguments, and it returns a bool, depending on whether they match
or not.
This function, which returns a bool, is known as a predicate, and the algorithms which do this, also
allow us to supply our own predicate.
We can do that by passing any callable object as an optional extra argument to the algorithm call.
Obviously, the callable object has to be of the right type.
If we are providing one for the find() algorithm, it would need to take two arguments of the element's
type, one for the current element and one for the target value, and return bool.
Another example is the sort() algorithm.
This works by comparing pairs of elements, and it compares them by calling the less-than operator with the
pair of elements as the arguments.
And then the sort function uses the result of this comparison, and it moves the smaller element
towards the front of the container and the larger element towards the back of the container.
And eventually the container is completely sorted.
And if you have studied this in detail, you will know that the important bit is deciding how you
choose which pair of elements you are going to compare.
And if you do that right, you can make the algorithm much more efficient.
(Bring myself into the picture!)
So let's quickly remind ourselves of the sort() function.
We had this code in the video on the less-than operator.
We have this vector of names, of string objects.
Then we print it out. Then we call the sort() function.
This will use the less-than operator by default, of the element type, which is the library string.
And then we print out the vector again.
So there we are.
We get the elements in ascending alphabetical order, because that is how the string's less-than operator
works.
But supposing we wanted to use some different criteria for sorting these.
For example, we could sort them by length, so that the shortest words would be at the front of the vector
and the longest words would be at the back.
And we can do that by providing our own predicate, which does the comparison by looking at the lengths
of the words. As opposed to the string's less-than operator, which looks at the characters.
So we can do this by calling the sort() function with a callable object, which compares the length
of the two arguments.
We are going to use a function pointer. So here is a non-member function, which does the comparison.
This takes two arguments which are of the element's type, string.
We pass them by reference to const because we are not going to modify the arguments, and we want to be
efficient.
And we return a bool, because that is what the predicate has to do.
And then, in the body of this function, we do our comparison.
So we compare the number of characters in each of these strings.
If the first argument has fewer characters, we return true, otherwise false.
And then we pass this function pointer as an extra argument to the sort() function.
So when the sort() function does the comparison, it is going to call this function, through the function
pointer, and that will do the comparison.
And then the sort() function will use the results of this to rearrange the elements in the vector.
And there is the results. So that is the alphabetical sort again, and this is sorted by length.
So this is calling the function, is_shorter().
We can also do this by using a functor, which is a class with an overloaded function call operator.
So here is the class. So this time, is_shorter is the name of the class.
It just has one member, which is a public member function, which is the function call operator.
So this is exactly the same as the function we had before, except that it is implemented as a member.
And then when we call the sort algorithm, we need to provide a callable object.
So we need to provide an object of this class, so we call the constructor.
So this will create a temporary object.
And then the sort() function will call the member function, every time it does a comparison.
So this will actually execute exactly the same code as the function pointer before.
And there you are.
We get the same result.
So you may be wondering what the point of having a functor is, because we can use a function pointer and
actually the syntax is slightly easier, and there is less codes to write up here.
The reason is something called a lambda expression, which is an even easier way of doing this.
But before I can explain that, you need to understand about functors.
So that is why I am doing this.
All will be revealed very shortly!
Okay, so that is it for this video.
I will see you next time.
But until then, keep coding!