Hello again! In this video, we are going to look at searching multimaps. We have seen that we can use
the find() and count() member functions of a multiset or multimap, to find all the elements which have
given key.
And that works, but it would be nice if we could get these elements
as an iterator range, because there are lots of things in C++ that work with iterator ranges. And
the multimap and multiset have member functions which will do that for us.
There are also generic versions of these functions in the algorithm header.
They are not terribly convenient for using with multimap, because of the element type, but they work
very well with sequential containers.
For example, if you want to find all the elements in a vector which have a given value.
The first two member functions we are going to look at are called lower_bound() and upper_bound().
So if you imagine we have a kind of sub-container within the multimap, where all the elements have
the same key, then these act like begin() and end() for that sub-container.
lower_bound() will return the first element which has this key, and upper_bound() will return the first element
which comes after those elements. So that acts like the end() member function; it returns the last plus
one iterator.
If there are no elements which have this key, then these two return the same
iterator,
and we have an empty range.
So if we iterate from the lower_bound() iterator up to, but not including, the upper_bound()
iterator,
we will get all the elements with that key.
So this defines a half-open range.
And some pseudo-code which might or might not help you understand what is happening.
As usual, do not take this too literally! So lower_bound() will iterate through the elements, until it finds
an element whose key is greater than, or equal to, the one we want.
upper_bound() will iterate through the elements until it finds some element whose key is greater than the
one we are looking for.
So, lower_bound() may return an iterator which has the same key as
its argument. upper_bound() always returns an element which has a greater key.
So let's see how this works.
So, using our usual multimap. So the elements for this multimap are going to be in the order "Grace",
and then three "Grahams", and then "Hareesh".
If we call lower_bound() "Graham", this will return an iterator to the first "Graham", which is
this element. If we call upper_bound() with argument, "Graham",
this will return the first elements after the "Grahams", so that's going to be "Hareesh".
And then if we iterate over those, up to, but not including upper_bound(), that will give us all the "Graham" elements.
If we calle lower_bound() and upper_bound() with an argument, which is not the key of an element. For
example, "Gordon". lower_bound() will return the first element that is greater than or equal to "Gordon",
which is going to be "Grace". upper_bound() will return the first element which is greater than "Gordon", which
is also "Grace".
So these two are going to return the same iterator.
And if we loop over those iterators, we get no results.
And that is how it should be!
So here we are, we have the multimap elements. The scores for "Graham". So lower_bound() will return the first
element and upper_bound()s will return
The next element after "Graham", which is "Hareesh". The lower_bound() and upper_bound() for "Gordon", both return
the "Grace" element.
And we get no scores for "Gordon".
If we want to find an element which has a particular value, then we can just check for that in the loop.
So we can call upper_bound() and lower_bound(),
iterate over the results, and then compare the value.
The other member function we are going to look at is equal_range().
So this combines lower_bound() and upper_bound().
It returns a pair object.
The first member of this pair will be the return value from lower_bound(), and the second member
will be the return value from upper_bound().
So if we call equal_range() with argument "Graham", this will return a pair.
The first member will be the first element with key "Graham", and the second member will be the first
element which comes after the elements with key "Graham".
So here we go again.
We call equal_range(), and then we iterate from the first "Graham" to the first element after "Graham".
And we are. In C++17, we could find this much more neatly. We could use a structured binding,
and then we have nice names in the iterator loop.
So, now we have an iterator range to work withm
we can now use the standard algorithms.
So if we want to find an element which has a particular value, we can use find_if with a lambda
expression, instead of having to write a loop.
So we'd call find_if() with the two iterators from equal_range(). The lambda expression will be called
with an element as the argument.
So that is going to be a pair of string and int.
And then, in the lambda body, we can check for the value that we want.
So.
Same as before. We call equal_range().
We get the first and second members.
And then we can pass those iterators to the find_if().
So, this is going to look at all the iterators, from the first "Graham" to the first element after
"Graham", but not including that one.
And it is going to call this lambda expression on each element, and it will return true if the value of
the element is 66.
And there we are.
We do have an element with key "Graham" and value 66.
In fact, in this map, we have two elements with key "Graham" and value 66.
So what happens if we want to get both of those?
So you have to be called to find out if this will give us an iterator to the first element with key
66.
So after we call find_if(), this will return an iterator to the first element with key "Graham" and value
66. If we then increment this iterator, that will take us to the next "Graham" element. And then we can
use that as the start of a range for a new search.
So this is going to search the rest of the elements, from just after the one we found to the "Graham" element.
And then we can write a loop. Once we have seen all the "Graham" elements, then this iterator will be equal to "finish"
and then the loop will terminate.
We are going to store the results in a vector, so we push back the dereferenced iterator into the
vector on each iteration.
So let's see what we get.
So our vector has two elements with key "Graham" and value 66.
Quite often, if you have a handwritten loop, which involves iterators, there is some algorithm that
you can use to replace it.
So let's see how we can do this, in this example.
So after we call equal_range(), we get the pair object. And then we can use the copy_if() algorithm with the
same lambda expression.
So these are going to be elements with key "Graham".
And if any of these elements with key "Graham" also have the value 66, then we are going to add them to
our vector.
And we use a back_inserter as the destination of our copy_if() call.
And there we are. So we get the same results again, but using much less code.
Okay, so that is it for this video.
I will see you next time, but until then, keep coding!