Hello again! In this video, we are going to look at merging algorithms.
These are functions which take two
iterator ranges.
They assume that the ranges are sorted. And then they combine the elements from these ranges and write
them to a destination.
The only difference in these algorithms is in the way that they combine the results.
The first one we are going to look at is merge.
And this is pretty straightforward.
It just combines all the elements from both the ranges.
And then the result is sorted. By default,
it uses the less-than operator, but we can provide our own comparison if we prefer.
We call this with the two
iterator ranges.
And then the destination.
And if you are into set theory, then you will know that this is the sum of the ranges. And maybe you can
explain it to me some day(!)
The way this works is that it just does combine all the elements.
So we have 1 in here twice.
We have 2, once.
We have 3 twice and 4.
And that is the result after sorting.
So here is some code for trying this out. We have two vectors.
We have a few more elements here, just to make it slightly more interesting.
(We hope!) We sort both the vectors.
So these are going to be the arguments to merge(). And then we have an empty vector and an insert iterator
for that vector.
So this code will populate "vec3" with the merged elements of "vec1" and "vec2".
And that is what we get.
So that just does simply combine all the elements.
We can also get the intersection, and this is called set_intersection(), which is a
pretty good description of what it does!
In this case, the algorithm will only write elements which are present in both the ranges.
If an element is only in one of the ranges, it will be ignored.
So in our example, 3 is present in both the ranges, so that will be written.
1 is present in both ranges, so that will be written. 4 is only present in this range.
So that will be ignored.
And 2 is only present in this range, so it will be ignored as well.
So the result is 1 and 3.
So I have changed this code to call set_intersection(), so let's see what that does.
And we get to 1, 3 and 4. So it ignores 2, 8, 5 and 9, which are only in one
of the ranges.
And finally, we can get the set union of the ranges.
This will contain elements which are in either range.
But if an element appears in both ranges, it will only appear once in the result.
So with our example, three appears in both the ranges, so it only appears once in the results. 1 appears
in both the ranges, so it only appears once, and then 4 and 2 appear once as well.
So 1, 2, 3, 4 is the result. And then we can call set_union() in our example.
So 4 appears in both the ranges, but it is only once in the output.
We have 1 twice.
And that is because it appears twice in vec1.
So you can have duplicates within one range.
But if the duplicates are across the two ranges, then the second duplicate is ignored.
And in fact, the duplicate of 1 is ignored here as well.
Okay, so that is it for this video.
I will see you next time, but until then, keep coding!