WEBVTT 00:00.120 --> 00:06.900 Hello again! In this video, we are going to look at partitioning algorithms. When we partition a container, 00:07.260 --> 00:11.370 this means that we check whether the elements have a certain property. 00:11.730 --> 00:14.430 If they have that property, we move them to the front. 00:15.090 --> 00:18.390 And if they do not have that property, we move them to the back of the container. 00:19.080 --> 00:22.080 And the boundary between these is called the partition point. 00:22.530 --> 00:27.720 So all the elements with a given property are at the front, and all the elements which do not have the 00:27.720 --> 00:28.890 property are at the back. 00:30.150 --> 00:33.090 This is very useful for writing interactive applications. 00:33.540 --> 00:39.780 For example, if you are displaying messages, you can move the unread messages to the front, and leave the 00:39.780 --> 00:41.130 read messages at the back. 00:42.630 --> 00:47.550 If the user selects items from a drop-down list, you can re-display the list with the selected items 00:47.550 --> 00:48.000 at the top, 00:48.480 --> 00:50.700 nd the other items below. And so on. 00:53.760 --> 00:58.470 There is a partition() algorithm which we can use to partition an iterator range. 00:58.920 --> 01:02.790 This takes the iterator range and some predicate function. 01:03.780 --> 01:08.190 And then when this returns, all the elements for which the predicate is true will be at the front of 01:08.190 --> 01:08.760 the container. 01:09.180 --> 01:11.640 And all the ones for which it is false will be at the back. 01:12.630 --> 01:15.660 The elements may have the order changed within each group. 01:18.000 --> 01:18.900 So let's try this out. 01:19.020 --> 01:22.800 I have added a few extra elements, to make it a bit clearer what is happening. 01:24.090 --> 01:28.500 We are going to call partition() with the iterators for this vector as the range. 01:28.890 --> 01:34.320 And then this lambda expression, which will return true if the element is odd, and false if it is 01:34.320 --> 01:40.170 even. So, we should expect to see all the odd numbers at the front of the vector, and all the even numbers 01:40.170 --> 01:40.650 at the back. 01:41.730 --> 01:42.750 And that is what we get. 01:42.760 --> 01:46.290 So we get the even numbers at the front, and the numbers at the back. 01:47.310 --> 01:53.190 You will notice that the odd numbers were originally 3, 1, 1, 5, 9. And in the results, they are 01:53.190 --> 01:54.960 3, 1, 9, 1, 5. 01:55.290 --> 01:56.970 So they have changed their relative order. 01:59.010 --> 02:04.860 If you want the elements to keep their relative order within each group, then there is a stable_partition(), 02:05.160 --> 02:06.690 which is called exactly the same way. 02:07.070 --> 02:12.690 But obviously, the version which moves them around is faster. It is more optimized. 02:13.050 --> 02:18.480 The stable_partition() has to do more work to retain the ordering. So we have the same code again. 02:18.870 --> 02:22.860 The only difference is, we are calling stable_partition() instead of partition(). 02:25.670 --> 02:30.530 And now we have the odd elements in the same relative order. So, 3, 1, 1, 59. 02:31.400 --> 02:36.470 There is also an is_partitioned() algorithm, which will tell us whether an iterator range is partitioned, 02:36.740 --> 02:39.200 using a given predicate function. 02:40.760 --> 02:43.700 So we would call this with the iterator range and some function. 02:44.300 --> 02:50.160 And if the iterator range is already partitioned by this function, it will return true, otherwise 02:50.180 --> 02:50.570 false. 02:52.940 --> 02:54.680 So let's try this with the same vector 02:54.800 --> 02:59.720 again. We are going to use the same lambda expression. And we are going to store it in a variable, because 02:59.720 --> 03:01.310 we are going to use it several times. 03:02.600 --> 03:07.850 So we start off by calling is_partitioned(), before we do anything else, and we expect that to be false. 03:07.850 --> 03:14.420 Because the vector has not been partitioned. And then we partition the vector, using the same lambda expression. 03:15.560 --> 03:17.120 And then we expect that to return 03:17.120 --> 03:20.660 true, when we call is_partitioned() again, with the same predicate. 03:23.680 --> 03:27.850 And that is what we get. The first time, the vector has not been partitioned by oddness. 03:28.360 --> 03:31.390 Then we partition it and then, okay, it has been partitioned. 03:34.620 --> 03:37.800 And finally, there is an algorithm for finding the partition point. 03:38.190 --> 03:43.770 This takes the same arguments as is_partitioned(), and it will return an iterator to the partition point. 03:45.650 --> 03:49.970 The actual implementation is that it returns an iterator to the first element for which the predicate 03:50.040 --> 03:53.090 is false, which is also the partition point. 03:56.770 --> 04:03.580 So here is our code again. We partitioned this vector, then we check that it has been partitioned, and 04:03.580 --> 04:05.170 then we find the partition point. 04:08.280 --> 04:13.620 And it has been partitioned, and the partition is an element with value 4, which is at index 5, 04:13.620 --> 04:14.580 which is that one. 04:15.060 --> 04:15.750 So that is correct. 04:16.560 --> 04:17.970 Okay, so that is it for this video. 04:18.360 --> 04:19.170 I will see you next time. 04:19.440 --> 04:21.030 Until then, keep coding!