The associative containers provide various ways to find a given element, which are described in Table 11.7 (p. 438). Which operation to use depends on what problem we are trying to solve. If all we care about is whether a particular element is in the container, it is probably best to use find
. For the containers that can hold only unique keys, it probably doesn’t matter whether we use find
or count
. However, for the containers with multiple keys, count
has to do more work: If the element is present, it still has to count how many elements have the same key. If we don’t need the count, it’s best to use find
:
Exercise 11.24: What does the following program do?
map<int, int> m;
m[0] = 1;
Exercise 11.25: Contrast the following program with the one in the previous exercise
vector<int> v;
v[0] = 1;
Exercise 11.26: What type can be used to subscript a map
? What type does the subscript operator return? Give a concrete example—that is, define a map
and then write the types that can be used to subscript the map
and the type that would be returned from the subscript operator.
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1); // returns an iterator that refers to the element with key == 1
iset.find(11); // returns the iterator == iset.end()
iset.count(1); // returns 1
iset.count(11); // returns 0
find
Instead of Subscript for map
sFor the map
and unordered_map
types, the subscript operator provides the simplest method of retrieving a value. However, as we’ve just seen, using a subscript has an important side effect: If that key is not already in the map
, then subscript inserts an element with that key. Whether this behavior is correct depends on our expectations. Our word-counting programs relied on the fact that using a nonexistent key as a subscript inserts an element with that key and value 0.
Sometimes, we want to know if an element with a given key is present without changing the map
. We cannot use the subscript operator to determine whether an element is present, because the subscript operator inserts a new element if the key is not already there. In such cases, we should use find
:
if (word_count.find("foobar") == word_count.end())
cout << "foobar is not in the map" << endl;
multimap
or multiset
Finding an element in an associative container that requires unique keys is a simple matter—the element is or is not in the container. For the containers that allow multiple keys, the process is more complicated: There may be many elements with the given key. When a multimap
or multiset
has multiple elements of a given key, those elements will be adjacent within the container.
For example, given our map from author to titles, we might want to print all the books by a particular author. We can solve this problem in three different ways. The most obvious way uses find
and count
:
string search_item("Alain de Botton"); // author we'll look for
auto entries = authors.count(search_item); // number of elements
auto iter = authors.find(search_item); // first entry for this author
// loop through the number of entries there are for this author
while(entries) {
cout << iter->second << endl; // print each title
++iter; // advance to the next title
--entries; // keep track of how many we've printed
}
We start by determining how many entries there are for the author by calling count
and getting an iterator to the first element with this key by calling find
. The number of iterations of the for
loop depends on the number returned from count
. In particular, if the count
was zero, then the loop is never executed.
We are guaranteed that iterating across a multimap
or multiset
returns all the elements with a given key in sequence.
Alternatively, we can solve our problem using lower_bound
and upper_bound
. Each of these operations take a key and returns an iterator. If the key is in the container, the iterator returned from lower_bound
will refer to the first instance of that key and the iterator returned by upper_bound
will refer just after the last instance of the key. If the element is not in the multimap
, then lower_bound
and upper_bound
will return equal iterators; both will refer to the point at which the key can be inserted without disrupting the order. Thus, calling lower_bound
and upper_bound
on the same key yields an iterator range (§ 9.2.1, p. 331) that denotes all the elements with that key.
Of course, the iterator returned from these operations might be the off-the-end iterator for the container itself. If the element we’re looking for has the largest key in the container, then upper_bound
on that key returns the off-the-end iterator. If the key is not present and is larger than any key in the container, then the return from lower_bound
will also be the off-the-end iterator.
The iterator returned from lower_bound
may or may not refer to an element with the given key. If the key is not in the container, then lower_bound
refers to the first point at which this key can be inserted while preserving the element order within the container.
Using these operations, we can rewrite our program as follows:
// definitions of authors and search_item as above
// beg and end denote the range of elements for this author
for (auto beg = authors.lower_bound(search_item),
end = authors.upper_bound(search_item);
beg != end; ++beg)
cout << beg->second << endl; // print each title
This program does the same work as the previous one that used count
and find
but accomplishes its task more directly. The call to lower_bound
positions beg
so that it refers to the first element matching search_item
if there is one. If there is no such element, then beg
refers to the first element with a key larger than search_item
, which could be the off-the-end iterator. The call to upper_bound
sets end
to refer to the element just beyond the last element with the given key. These operations say nothing about whether the key is present. The important point is that the return values act like an iterator range (§ 9.2.1, p. 331).
If there is no element for this key, then lower_bound
and upper_bound
will be equal. Both will refer to the point at which this key can be inserted while maintaining the container order.
Assuming there are elements with this key, beg
will refer to the first such element. We can increment beg
to traverse the elements with this key. The iterator in end
will signal when we’ve seen all the elements. When beg
equals end
, we have seen every element with this key.
Because these iterators form a range, we can use a for
loop to traverse that range. The loop is executed zero or more times and prints the entries, if any, for the given author. If there are no elements, then beg
and end
are equal and the loop is never executed. Otherwise, we know that the increment to beg
will eventually reach end
and that in the process we will print each record associated with this author.
If lower_bound
and upper_bound
return the same iterator, then the given key is not in the container.
equal_range
FunctionThe remaining way to solve this problem is the most direct of the three approaches: Instead of calling upper_bound
and lower_bound
, we can call equal_range
.
This function takes a key and returns a pair
of iterators. If the key is present, then the first iterator refers to the first instance of the key and the second iterator refers one past the last instance of the key. If no matching element is found, then both the first and second iterators refer to the position where this key can be inserted.
We can use equal_range
to modify our program once again:
// definitions of authors and search_item as above
// pos holds iterators that denote the range of elements for this key
for (auto pos = authors.equal_range(search_item);
pos.first != pos.second; ++pos.first)
cout << pos.first->second << endl; // print each title
This program is essentially identical to the previous one that used upper_bound
and lower_bound
. Instead of using local variables, beg
and end
, to hold the iterator range, we use the pair
returned by equal_range
. The first
member of that pair
holds the same iterator as lower_bound
would have returned and second
holds the iterator upper_bound
would have returned. Thus, in this program pos.first
is equivalent to beg
, and pos.second
is equivalent to end
.
Exercise 11.27: What kinds of problems would you use count
to solve? When might you use find
instead?
Exercise 11.28: Define and initialize a variable to hold the result of calling find
on a map
from string
to vector
of int
.
Exercise 11.29: What do upper_bound
, lower_bound
, and equal_range
return when you pass them a key that is not in the container?
Exercise 11.30: Explain the meaning of the operand pos.first->second
used in the output expression of the final program in this section.
Exercise 11.31: Write a program that defines a multimap
of authors and their works. Use find
to find an element in the multimap
and erase
that element. Be sure your program works correctly if the element you look for is not in the map
.
Exercise 11.32: Using the multimap
from the previous exercise, write a program to print the list of authors and their works alphabetically.