When we dereference an iterator, we get a reference to a value of the container’s value_type
. In the case of map
, the value_type
is a pair
in which first
holds the const
key and second
holds the value:
// get an iterator to an element in word_count
auto map_it = word_count.begin();
// *map_it is a reference to a pair<const string, size_t> object
cout << map_it->first; // prints the key for this element
cout << " " << map_it->second; // prints the value of the element
map_it->first = "new key"; // error: key is const
++map_it->second; // ok: we can change the value through an iterator
It is essential to remember that the value_type
of a map
is a pair
and that we can change the value but not the key member of that pair
.
set
s Are const
Although the set
types define both the iterator
and const_iterator
types, both types of iterators give us read-only access to the elements in the set
. Just as we cannot change the key part of a map
element, the keys in a set
are also const
. We can use a set
iterator to read, but not write, an element’s value:
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end()) {
*set_it = 42; // error: keys in a set are read-only
cout << *set_it << endl; // ok: can read the key
}
The map
and set
types provide all the begin
and end
operations from Table 9.2 (p. 330). As usual, we can use these functions to obtain iterators that we can use to traverse the container. For example, we can rewrite the loop that printed the results in our word-counting program on page 421 as follows:
// get an iterator positioned on the first element
auto map_it = word_count.cbegin();
// compare the current iterator to the off-the-end iterator
while (map_it != word_count.cend()) {
// dereference the iterator to print the element key--value pairs
cout << map_it->first << " occurs "
<< map_it->second << " times" << endl;
++map_it; // increment the iterator to denote the next element
}
The while
condition and increment for the iterator in this loop look a lot like the programs we wrote that printed the contents of a vector
or a string
. We initialize an iterator, map_it
, to refer to the first element in word_count
. As long as the iterator is not equal to the end
value, we print the current element and then increment the iterator. The output statement dereferences map_it
to get the members of pair
but is otherwise the same as the one in our original program.
The output of this program is in alphabetical order. When we use an iterator to traverse a map, multimap, set
, or multiset
, the iterators yield elements in ascending key order.
In general, we do not use the generic algorithms (Chapter 10) with the associative containers. The fact that the keys are const
means that we cannot pass associative container iterators to algorithms that write to or reorder container elements. Such algorithms need to write to the elements. The elements in the set
types are const
, and those in map
s are pair
s whose first element is const
.
Associative containers can be used with the algorithms that read elements. However, many of these algorithms search the sequence. Because elements in an associative container can be found (quickly) by their key, it is almost always a bad idea to use a generic search algorithm. For example, as we’ll see in § 11.3.5 (p. 436), the associative containers define a member named find
, which directly fetches the element with a given key. We could use the generic find
algorithm to look for an element, but that algorithm does a sequential search. It is much faster to use the find
member defined by the container than to call the generic version.
In practice, if we do so at all, we use an associative container with the algorithms either as the source sequence or as a destination. For example, we might use the generic copy
algorithm to copy the elements from an associative container into another sequence. Similarly, we can call inserter
to bind an insert iterator (§ 10.4.1, p. 401) to an associative container. Using inserter
, we can use the associative container as a destination for another algorithm.
Exercise 11.15: What are the mapped_type
, key_type
, and value_type
of a map
from int
to vector<int>?
Exercise 11.16: Using a map
iterator write an expression that assigns a value to an element.
Exercise 11.17: Assuming c
is a multiset
of string
s and v
is a vector
of string
s, explain the following calls. Indicate whether each call is legal:
copy(v.begin(), v.end(), inserter(c, c.end()));
copy(v.begin(), v.end(), back_inserter(c));
copy(c.begin(), c.end(), inserter(v, v.end()));
copy(c.begin(), c.end(), back_inserter(v));
Exercise 11.18: Write the type of map_it
from the loop on page 430 without using auto
or decltype
.
Exercise 11.19: Define a variable that you initialize by calling begin()
on the multiset
named bookstore
from § 11.2.2 (p. 425). Write the variable’s type without using auto
or decltype
.