WEBVTT 00:00.120 --> 00:06.990 Hello again! In this video, we are going to look at searching multimaps. We have seen that we can use 00:07.230 --> 00:13.710 the find() and count() member functions of a multiset or multimap, to find all the elements which have 00:14.040 --> 00:14.700 given key. 00:15.850 --> 00:18.640 And that works, but it would be nice if we could get these elements 00:18.970 --> 00:26.170 as an iterator range, because there are lots of things in C++ that work with iterator ranges. And 00:26.170 --> 00:29.890 the multimap and multiset have member functions which will do that for us. 00:30.820 --> 00:34.560 There are also generic versions of these functions in the algorithm header. 00:35.170 --> 00:40.720 They are not terribly convenient for using with multimap, because of the element type, but they work 00:40.720 --> 00:42.310 very well with sequential containers. 00:42.700 --> 00:47.650 For example, if you want to find all the elements in a vector which have a given value. 00:50.910 --> 00:55.410 The first two member functions we are going to look at are called lower_bound() and upper_bound(). 00:55.770 --> 01:00.840 So if you imagine we have a kind of sub-container within the multimap, where all the elements have 01:00.840 --> 01:05.610 the same key, then these act like begin() and end() for that sub-container. 01:07.810 --> 01:13.990 lower_bound() will return the first element which has this key, and upper_bound() will return the first element 01:14.290 --> 01:19.570 which comes after those elements. So that acts like the end() member function; it returns the last plus 01:19.570 --> 01:20.410 one iterator. 01:21.460 --> 01:25.240 If there are no elements which have this key, then these two return the same 01:25.240 --> 01:25.750 iterator, 01:25.930 --> 01:27.010 and we have an empty range. 01:29.620 --> 01:34.860 So if we iterate from the lower_bound() iterator up to, but not including, the upper_bound() 01:34.870 --> 01:35.110 iterator, 01:35.530 --> 01:37.090 we will get all the elements with that key. 01:37.360 --> 01:39.010 So this defines a half-open range. 01:42.620 --> 01:46.250 And some pseudo-code which might or might not help you understand what is happening. 01:46.610 --> 01:52.790 As usual, do not take this too literally! So lower_bound() will iterate through the elements, until it finds 01:53.010 --> 01:58.140 an element whose key is greater than, or equal to, the one we want. 01:58.160 --> 02:03.500 upper_bound() will iterate through the elements until it finds some element whose key is greater than the 02:03.500 --> 02:04.370 one we are looking for. 02:05.270 --> 02:08.760 So, lower_bound() may return an iterator which has the same key as 02:08.770 --> 02:13.130 its argument. upper_bound() always returns an element which has a greater key. 02:16.500 --> 02:17.770 So let's see how this works. 02:17.790 --> 02:25.760 So, using our usual multimap. So the elements for this multimap are going to be in the order "Grace", 02:25.770 --> 02:27.910 and then three "Grahams", and then "Hareesh". 02:29.260 --> 02:34.120 If we call lower_bound() "Graham", this will return an iterator to the first "Graham", which is 02:34.120 --> 02:37.660 this element. If we call upper_bound() with argument, "Graham", 02:37.990 --> 02:42.650 this will return the first elements after the "Grahams", so that's going to be "Hareesh". 02:44.460 --> 02:50.340 And then if we iterate over those, up to, but not including upper_bound(), that will give us all the "Graham" elements. 02:52.800 --> 02:57.540 If we calle lower_bound() and upper_bound() with an argument, which is not the key of an element. For 02:57.540 --> 03:04.050 example, "Gordon". lower_bound() will return the first element that is greater than or equal to "Gordon", 03:04.050 --> 03:09.180 which is going to be "Grace". upper_bound() will return the first element which is greater than "Gordon", which 03:09.180 --> 03:09.930 is also "Grace". 03:10.350 --> 03:12.570 So these two are going to return the same iterator. 03:13.350 --> 03:16.740 And if we loop over those iterators, we get no results. 03:17.130 --> 03:18.570 And that is how it should be! 03:22.580 --> 03:30.080 So here we are, we have the multimap elements. The scores for "Graham". So lower_bound() will return the first 03:30.470 --> 03:32.660 element and upper_bound()s will return 03:32.670 --> 03:38.720 The next element after "Graham", which is "Hareesh". The lower_bound() and upper_bound() for "Gordon", both return 03:38.720 --> 03:39.800 the "Grace" element. 03:41.200 --> 03:42.790 And we get no scores for "Gordon". 03:44.770 --> 03:49.930 If we want to find an element which has a particular value, then we can just check for that in the loop. 03:50.920 --> 03:53.080 So we can call upper_bound() and lower_bound(), 03:53.680 --> 03:57.070 iterate over the results, and then compare the value. 04:00.110 --> 04:02.910 The other member function we are going to look at is equal_range(). 04:03.290 --> 04:05.660 So this combines lower_bound() and upper_bound(). 04:06.350 --> 04:08.030 It returns a pair object. 04:08.600 --> 04:13.880 The first member of this pair will be the return value from lower_bound(), and the second member 04:13.880 --> 04:16.100 will be the return value from upper_bound(). 04:16.970 --> 04:21.020 So if we call equal_range() with argument "Graham", this will return a pair. 04:21.260 --> 04:27.320 The first member will be the first element with key "Graham", and the second member will be the first 04:27.320 --> 04:29.630 element which comes after the elements with key "Graham". 04:33.080 --> 04:34.490 So here we go again. 04:36.900 --> 04:44.310 We call equal_range(), and then we iterate from the first "Graham" to the first element after "Graham". 04:48.200 --> 04:55.820 And we are. In C++17, we could find this much more neatly. We could use a structured binding, 04:56.270 --> 04:59.930 and then we have nice names in the iterator loop. 05:01.880 --> 05:03.860 So, now we have an iterator range to work withm 05:03.870 --> 05:05.840 we can now use the standard algorithms. 05:06.320 --> 05:12.170 So if we want to find an element which has a particular value, we can use find_if with a lambda 05:12.170 --> 05:14.480 expression, instead of having to write a loop. 05:15.290 --> 05:22.310 So we'd call find_if() with the two iterators from equal_range(). The lambda expression will be called 05:22.310 --> 05:24.170 with an element as the argument. 05:24.230 --> 05:26.270 So that is going to be a pair of string and int. 05:27.920 --> 05:30.860 And then, in the lambda body, we can check for the value that we want. 05:34.070 --> 05:34.610 So. 05:36.400 --> 05:38.290 Same as before. We call equal_range(). 05:38.620 --> 05:41.470 We get the first and second members. 05:42.250 --> 05:45.520 And then we can pass those iterators to the find_if(). 05:45.520 --> 05:51.010 So, this is going to look at all the iterators, from the first "Graham" to the first element after 05:51.010 --> 05:52.510 "Graham", but not including that one. 05:53.380 --> 05:59.530 And it is going to call this lambda expression on each element, and it will return true if the value of 05:59.530 --> 06:00.760 the element is 66. 06:04.860 --> 06:05.550 And there we are. 06:05.700 --> 06:08.370 We do have an element with key "Graham" and value 66. 06:12.570 --> 06:16.590 In fact, in this map, we have two elements with key "Graham" and value 66. 06:17.040 --> 06:19.290 So what happens if we want to get both of those? 06:22.880 --> 06:28.760 So you have to be called to find out if this will give us an iterator to the first element with key 06:28.760 --> 06:29.450 66. 06:30.980 --> 06:35.690 So after we call find_if(), this will return an iterator to the first element with key "Graham" and value 06:35.690 --> 06:43.850 66. If we then increment this iterator, that will take us to the next "Graham" element. And then we can 06:43.850 --> 06:46.760 use that as the start of a range for a new search. 06:47.180 --> 06:53.570 So this is going to search the rest of the elements, from just after the one we found to the "Graham" element. 06:53.810 --> 07:00.620 And then we can write a loop. Once we have seen all the "Graham" elements, then this iterator will be equal to "finish" 07:01.010 --> 07:02.510 and then the loop will terminate. 07:03.440 --> 07:08.930 We are going to store the results in a vector, so we push back the dereferenced iterator into the 07:08.930 --> 07:10.880 vector on each iteration. 07:13.190 --> 07:14.180 So let's see what we get. 07:14.960 --> 07:19.250 So our vector has two elements with key "Graham" and value 66. 07:21.590 --> 07:26.210 Quite often, if you have a handwritten loop, which involves iterators, there is some algorithm that 07:26.210 --> 07:27.500 you can use to replace it. 07:27.920 --> 07:29.840 So let's see how we can do this, in this example. 07:31.280 --> 07:39.200 So after we call equal_range(), we get the pair object. And then we can use the copy_if() algorithm with the 07:39.200 --> 07:40.430 same lambda expression. 07:41.150 --> 07:43.460 So these are going to be elements with key "Graham". 07:43.790 --> 07:49.370 And if any of these elements with key "Graham" also have the value 66, then we are going to add them to 07:49.430 --> 07:49.930 our vector. 07:50.210 --> 07:54.140 And we use a back_inserter as the destination of our copy_if() call. 07:58.270 --> 08:01.900 And there we are. So we get the same results again, but using much less code. 08:02.710 --> 08:04.270 Okay, so that is it for this video. 08:04.630 --> 08:07.480 I will see you next time, but until then, keep coding!