WEBVTT 00:00.120 --> 00:03.510 Hello again! In this video, we are going to look at merging algorithms. 00:03.990 --> 00:05.990 These are functions which take two 00:06.000 --> 00:06.900 iterator ranges. 00:07.290 --> 00:14.520 They assume that the ranges are sorted. And then they combine the elements from these ranges and write 00:14.520 --> 00:16.020 them to a destination. 00:17.460 --> 00:21.660 The only difference in these algorithms is in the way that they combine the results. 00:23.340 --> 00:25.590 The first one we are going to look at is merge. 00:26.100 --> 00:27.630 And this is pretty straightforward. 00:27.900 --> 00:30.210 It just combines all the elements from both the ranges. 00:30.900 --> 00:34.090 And then the result is sorted. By default, 00:34.120 --> 00:38.910 it uses the less-than operator, but we can provide our own comparison if we prefer. 00:40.290 --> 00:41.580 We call this with the two 00:41.580 --> 00:42.540 iterator ranges. 00:42.900 --> 00:44.730 And then the destination. 00:45.480 --> 00:50.970 And if you are into set theory, then you will know that this is the sum of the ranges. And maybe you can 00:50.970 --> 00:51.990 explain it to me some day(!) 00:53.940 --> 00:57.540 The way this works is that it just does combine all the elements. 00:57.780 --> 00:59.790 So we have 1 in here twice. 01:00.060 --> 01:01.200 We have 2, once. 01:01.710 --> 01:03.360 We have 3 twice and 4. 01:04.380 --> 01:06.600 And that is the result after sorting. 01:09.170 --> 01:12.350 So here is some code for trying this out. We have two vectors. 01:13.070 --> 01:16.280 We have a few more elements here, just to make it slightly more interesting. 01:16.670 --> 01:19.610 (We hope!) We sort both the vectors. 01:20.840 --> 01:26.060 So these are going to be the arguments to merge(). And then we have an empty vector and an insert iterator 01:26.060 --> 01:26.990 for that vector. 01:27.620 --> 01:33.770 So this code will populate "vec3" with the merged elements of "vec1" and "vec2". 01:36.180 --> 01:37.380 And that is what we get. 01:38.190 --> 01:40.860 So that just does simply combine all the elements. 01:44.150 --> 01:50.000 We can also get the intersection, and this is called set_intersection(), which is a 01:50.000 --> 01:51.590 pretty good description of what it does! 01:52.490 --> 01:57.350 In this case, the algorithm will only write elements which are present in both the ranges. 01:58.190 --> 02:01.910 If an element is only in one of the ranges, it will be ignored. 02:04.800 --> 02:09.540 So in our example, 3 is present in both the ranges, so that will be written. 02:09.930 --> 02:15.410 1 is present in both ranges, so that will be written. 4 is only present in this range. 02:15.420 --> 02:16.470 So that will be ignored. 02:16.980 --> 02:20.190 And 2 is only present in this range, so it will be ignored as well. 02:20.910 --> 02:23.010 So the result is 1 and 3. 02:26.020 --> 02:30.850 So I have changed this code to call set_intersection(), so let's see what that does. 02:33.490 --> 02:40.120 And we get to 1, 3 and 4. So it ignores 2, 8, 5 and 9, which are only in one 02:40.120 --> 02:40.720 of the ranges. 02:43.440 --> 02:46.380 And finally, we can get the set union of the ranges. 02:46.980 --> 02:49.620 This will contain elements which are in either range. 02:50.190 --> 02:55.200 But if an element appears in both ranges, it will only appear once in the result. 02:58.980 --> 03:07.350 So with our example, three appears in both the ranges, so it only appears once in the results. 1 appears 03:07.350 --> 03:11.610 in both the ranges, so it only appears once, and then 4 and 2 appear once as well. 03:12.210 --> 03:20.070 So 1, 2, 3, 4 is the result. And then we can call set_union() in our example. 03:23.210 --> 03:27.500 So 4 appears in both the ranges, but it is only once in the output. 03:28.220 --> 03:29.420 We have 1 twice. 03:29.660 --> 03:32.210 And that is because it appears twice in vec1. 03:33.410 --> 03:35.720 So you can have duplicates within one range. 03:36.200 --> 03:41.450 But if the duplicates are across the two ranges, then the second duplicate is ignored. 03:42.440 --> 03:45.140 And in fact, the duplicate of 1 is ignored here as well. 03:47.400 --> 03:49.380 Okay, so that is it for this video. 03:49.800 --> 03:52.800 I will see you next time, but until then, keep coding!