WEBVTT 00:00.120 --> 00:06.450 Hello again! In this video, we are going to look at algorithms with predicates. Many of the algorithms 00:06.450 --> 00:11.490 work by having a function which they call on each iteration. The function returns bool. 00:12.360 --> 00:17.700 For example, in the find() algorithm, this calls the equality operator on each iteration. 00:18.240 --> 00:22.570 It has the current element as one argument and the target value, 00:22.590 --> 00:28.890 the thing we are sorting for, as the other arguments, and it returns a bool, depending on whether they match 00:28.890 --> 00:29.400 or not. 00:31.020 --> 00:37.410 This function, which returns a bool, is known as a predicate, and the algorithms which do this, also 00:37.410 --> 00:39.570 allow us to supply our own predicate. 00:40.410 --> 00:46.050 We can do that by passing any callable object as an optional extra argument to the algorithm call. 00:46.890 --> 00:50.160 Obviously, the callable object has to be of the right type. 00:50.640 --> 00:55.960 If we are providing one for the find() algorithm, it would need to take two arguments of the element's 00:55.980 --> 01:01.200 type, one for the current element and one for the target value, and return bool. 01:03.590 --> 01:05.960 Another example is the sort() algorithm. 01:06.380 --> 01:13.280 This works by comparing pairs of elements, and it compares them by calling the less-than operator with the 01:13.280 --> 01:15.170 pair of elements as the arguments. 01:16.670 --> 01:22.220 And then the sort function uses the result of this comparison, and it moves the smaller element 01:22.220 --> 01:26.540 towards the front of the container and the larger element towards the back of the container. 01:26.870 --> 01:29.360 And eventually the container is completely sorted. 01:30.380 --> 01:35.000 And if you have studied this in detail, you will know that the important bit is deciding how you 01:35.000 --> 01:37.970 choose which pair of elements you are going to compare. 01:38.450 --> 01:41.960 And if you do that right, you can make the algorithm much more efficient. 01:45.060 --> 01:46.500 (Bring myself into the picture!) 01:48.570 --> 01:51.240 So let's quickly remind ourselves of the sort() function. 01:51.570 --> 01:54.600 We had this code in the video on the less-than operator. 01:55.290 --> 01:58.380 We have this vector of names, of string objects. 01:59.100 --> 02:01.980 Then we print it out. Then we call the sort() function. 02:02.640 --> 02:08.340 This will use the less-than operator by default, of the element type, which is the library string. 02:09.390 --> 02:11.100 And then we print out the vector again. 02:12.840 --> 02:13.620 So there we are. 02:13.680 --> 02:19.530 We get the elements in ascending alphabetical order, because that is how the string's less-than operator 02:19.530 --> 02:19.890 works. 02:20.280 --> 02:24.540 But supposing we wanted to use some different criteria for sorting these. 02:25.050 --> 02:30.090 For example, we could sort them by length, so that the shortest words would be at the front of the vector 02:30.540 --> 02:32.340 and the longest words would be at the back. 02:33.830 --> 02:39.070 And we can do that by providing our own predicate, which does the comparison by looking at the lengths 02:39.080 --> 02:43.280 of the words. As opposed to the string's less-than operator, which looks at the characters. 02:47.270 --> 02:54.380 So we can do this by calling the sort() function with a callable object, which compares the length 02:54.380 --> 02:55.430 of the two arguments. 02:57.050 --> 03:02.990 We are going to use a function pointer. So here is a non-member function, which does the comparison. 03:03.530 --> 03:07.460 This takes two arguments which are of the element's type, string. 03:08.120 --> 03:13.550 We pass them by reference to const because we are not going to modify the arguments, and we want to be 03:13.550 --> 03:14.030 efficient. 03:15.200 --> 03:18.500 And we return a bool, because that is what the predicate has to do. 03:19.370 --> 03:22.580 And then, in the body of this function, we do our comparison. 03:23.120 --> 03:26.420 So we compare the number of characters in each of these strings. 03:27.200 --> 03:31.700 If the first argument has fewer characters, we return true, otherwise false. 03:35.220 --> 03:40.260 And then we pass this function pointer as an extra argument to the sort() function. 03:40.860 --> 03:45.630 So when the sort() function does the comparison, it is going to call this function, through the function 03:45.630 --> 03:47.790 pointer, and that will do the comparison. 03:48.180 --> 03:52.890 And then the sort() function will use the results of this to rearrange the elements in the vector. 03:56.220 --> 04:01.620 And there is the results. So that is the alphabetical sort again, and this is sorted by length. 04:01.830 --> 04:04.650 So this is calling the function, is_shorter(). 04:07.600 --> 04:12.930 We can also do this by using a functor, which is a class with an overloaded function call operator. 04:13.480 --> 04:17.410 So here is the class. So this time, is_shorter is the name of the class. 04:18.190 --> 04:24.010 It just has one member, which is a public member function, which is the function call operator. 04:25.060 --> 04:31.390 So this is exactly the same as the function we had before, except that it is implemented as a member. 04:33.270 --> 04:38.490 And then when we call the sort algorithm, we need to provide a callable object. 04:38.880 --> 04:43.080 So we need to provide an object of this class, so we call the constructor. 04:43.110 --> 04:45.300 So this will create a temporary object. 04:45.990 --> 04:51.030 And then the sort() function will call the member function, every time it does a comparison. 04:51.930 --> 04:56.910 So this will actually execute exactly the same code as the function pointer before. 04:58.680 --> 04:59.310 And there you are. 04:59.340 --> 05:00.300 We get the same result. 05:01.080 --> 05:06.960 So you may be wondering what the point of having a functor is, because we can use a function pointer and 05:07.500 --> 05:11.250 actually the syntax is slightly easier, and there is less codes to write up here. 05:11.880 --> 05:17.040 The reason is something called a lambda expression, which is an even easier way of doing this. 05:17.640 --> 05:20.400 But before I can explain that, you need to understand about functors. 05:20.850 --> 05:22.320 So that is why I am doing this. 05:23.610 --> 05:25.410 All will be revealed very shortly! 05:26.490 --> 05:28.680 Okay, so that is it for this video. 05:29.070 --> 05:29.940 I will see you next time. 05:29.940 --> 05:32.010 But until then, keep coding!