Hello again! In this video, we are going to look at partitioning algorithms. When we partition a container,
this means that we check whether the elements have a certain property.
If they have that property, we move them to the front.
And if they do not have that property, we move them to the back of the container.
And the boundary between these is called the partition point.
So all the elements with a given property are at the front, and all the elements which do not have the
property are at the back.
This is very useful for writing interactive applications.
For example, if you are displaying messages, you can move the unread messages to the front, and leave the
read messages at the back.
If the user selects items from a drop-down list, you can re-display the list with the selected items
at the top,
nd the other items below. And so on.
There is a partition() algorithm which we can use to partition an iterator range.
This takes the iterator range and some predicate function.
And then when this returns, all the elements for which the predicate is true will be at the front of
the container.
And all the ones for which it is false will be at the back.
The elements may have the order changed within each group.
So let's try this out.
I have added a few extra elements, to make it a bit clearer what is happening.
We are going to call partition() with the iterators for this vector as the range.
And then this lambda expression, which will return true if the element is odd, and false if it is
even. So, we should expect to see all the odd numbers at the front of the vector, and all the even numbers
at the back.
And that is what we get.
So we get the even numbers at the front, and the numbers at the back.
You will notice that the odd numbers were originally 3, 1, 1, 5, 9. And in the results, they are
3, 1, 9, 1, 5.
So they have changed their relative order.
If you want the elements to keep their relative order within each group, then there is a stable_partition(),
which is called exactly the same way.
But obviously, the version which moves them around is faster. It is more optimized.
The stable_partition() has to do more work to retain the ordering. So we have the same code again.
The only difference is, we are calling stable_partition() instead of partition().
And now we have the odd elements in the same relative order. So, 3, 1, 1, 59.
There is also an is_partitioned() algorithm, which will tell us whether an iterator range is partitioned,
using a given predicate function.
So we would call this with the iterator range and some function.
And if the iterator range is already partitioned by this function, it will return true, otherwise
false.
So let's try this with the same vector
again. We are going to use the same lambda expression. And we are going to store it in a variable, because
we are going to use it several times.
So we start off by calling is_partitioned(), before we do anything else, and we expect that to be false.
Because the vector has not been partitioned. And then we partition the vector, using the same lambda expression.
And then we expect that to return
true, when we call is_partitioned() again, with the same predicate.
And that is what we get. The first time, the vector has not been partitioned by oddness.
Then we partition it and then, okay, it has been partitioned.
And finally, there is an algorithm for finding the partition point.
This takes the same arguments as is_partitioned(), and it will return an iterator to the partition point.
The actual implementation is that it returns an iterator to the first element for which the predicate
is false, which is also the partition point.
So here is our code again. We partitioned this vector, then we check that it has been partitioned, and
then we find the partition point.
And it has been partitioned, and the partition is an element with value 4, which is at index 5,
which is that one.
So that is correct.
Okay, so that is it for this video.
I will see you next time.
Until then, keep coding!