11.3. Operations on Associative Containers

In addition to the types listed in Table 9.2 (p. 330), the associative containers define the types listed in Table 11.3. These types represent the container’s key and value types.

Table 11.3. Associative Container Additional Type Aliases

 

For the set types, the key_type and the value_type are the same; the values held in a set are the keys. In a map, the elements are key–value pairs. That is, each element is a pair object containing a key and a associated value. Because we cannot change an element’s key, the key part of these pairs is const:

As with the sequential containers (§ 9.2.2, p. 332), we use the scope operator to fetch a type member—for example, map<string, int>::key_type.

Only the map types (unordered_map, unordered_multimap, multimap, and map) define mapped_type.

11.3.1. Associative Container Iterators

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

Iterating across an Associative Container

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.

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 maps are pairs 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.

11.3.2. Adding Elements

The insert members (Table 11.4 (overleaf)) add one element or a range of elements. Because map and set (and the corresponding unordered types) contain unique keys, inserting an element that is already present has no effect:

vector<int> ivec = {2,4,6,8,2,4,6,8};    // ivec has eight elements
set<int> set2;                           // empty set
set2.insert(ivec.cbegin(), ivec.cend()); // set2 has four elements
set2.insert({1,3,5,7,1,3,5,7});      // set2 now has eight elements

Table 11.4. Associative Container insert Operations

 

The versions of insert that take a pair of iterators or an initializer list work similarly to the corresponding constructors (§ 11.2.1, p. 423)—only the first element with a given key is inserted.

Adding Elements to a map

When we insert into a map, we must remember that the element type is a pair. Often, we don’t have a pair object that we want to insert. Instead, we create a pair in the argument list to insert:

// four ways to add word to word_count
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));

As we’ve seen, under the new standard the easiest way to create a pair is to use brace initialization inside the argument list. Alternatively, we can call make_pair or explicitly construct the pair. The argument in the last call to insert:

For each word, we attempt to insert it with a value 1. If word is already in the map, then nothing happens. In particular, the counter associated with word is unchanged. If word is not already in the map, then that string is added to the map and its counter value is set to 1.

The statement that increments the counter in this version of the word-counting program can be hard to understand. It will be easier to understand that expression by first parenthesizing it to reflect the precedence (§ 4.1.2, p. 136) of the operators:

++((ret.first)->second); // equivalent expression

Explaining this expression step by step:

ret holds the value returned by insert, which is a pair.

ret.first is the first member of that pair, which is a map iterator referring to the element with the given key.

ret.first-> dereferences that iterator to fetch that element. Elements in the map are also pairs.

ret.first->second is the value part of the map element pair.

++ret.first->second increments that value.

Putting it back together, the increment statement fetches the iterator for the element with the key word and increments the counter associated with the key we tried to insert.

For readers using an older compiler or reading code that predates the new standard, declaring and initializing ret is also somewhat tricky:

pair<map<string, size_t>::iterator, bool> ret =
            word_count.insert(make_pair(word, 1));

It should be easy to see that we’re defining a pair and that the second type of the pair is bool. The first type of that pair is a bit harder to understand. It is the iterator type defined by the map<string, size_t> type.

Adding Elements to multiset or multimap

Our word-counting program depends on the fact that a given key can occur only once. That way, there is only one counter associated with any given word. Sometimes, we want to be able to add additional elements with the same key. For example, we might want to map authors to titles of the books they have written. In this case, there might be multiple entries for each author, so we’d use a multimap rather than a map. Because keys in a multi container need not be unique, insert on these types always inserts an element:

11.3.3. Erasing Elements

The associative containers define three versions of erase, which are described in Table 11.5. As with the sequential containers, we can erase one element or a range of elements by passing erase an iterator or an iterator pair. These versions of erase are similar to the corresponding operations on sequential containers: The indicated element(s) are removed and the function returns void.

Table 11.5. Removing Elements from an Associative Container

 

The associative containers supply an additional erase operation that takes a key_type argument. This version removes all the elements, if any, with the given key and returns a count of how many elements were removed. We can use this version to remove a specific word from word_count before printing the results:

 

 

// erase on a key returns the number of elements removed
if (word_count.erase(removal_word))
     cout << "ok: " << removal_word << " removed\n";
else cout << "oops: " << removal_word << " not found!\n";

 

For the containers with unique keys, the return from erase is always either zero or one. If the return value is zero, then the element we wanted to erase was not in the container.

 

For types that allow multiple keys, the number of elements removed could be greater than one:

If authors is the multimap we created in § 11.3.2 (p. 434), then cnt will be 2.

11.3.4. Subscripting a map

The map and unordered_map containers provide the subscript operator and a corresponding at function (§ 9.3.2, p. 348), which are described in Table 11.6 (overleaf). The set types do not support subscripting because there is no “value” associated with a key in a set. The elements are themselves keys, so the operation of “fetching the value associated with a key” is meaningless. We cannot subscript a multimap or an unordered_multimap because there may be more than one value associated with a given key.

Table 11.6. Subscript Operation for map and unordered_map

 

Like the other subscript operators we’ve used, the map subscript takes an index (that is, a key) and fetches the value associated with that key. However, unlike other subscript operators, if the key is not already present, a new element is created and inserted into the map for that key. The associated value is value initialized (§ 3.3.1, p. 98).

For example, when we write

map <string, size_t> word_count; // empty map
// insert a value-initialized element with key Anna; then assign 1 to its value
word_count["Anna"] = 1;

the following steps take place:

• word_count is searched for the element whose key is Anna. The element is not found.

• A new key-value pair is inserted into word_count. The key is a const string holding Anna. The value is value initialized, meaning in this case that the value is 0.

• The newly inserted element is fetched and is given the value 1.

Because the subscript operator might insert an element, we may use subscript only on a map that is not const.

Another way in which the map subscript differs from other subscript operators we’ve used is its return type. Ordinarily, the type returned by dereferencing an iterator and the type returned by the subscript operator are the same. Not so for maps: when we subscript a map, we get a mapped_type object; when we dereference a map iterator, we get a value_type object (§ 11.3, p. 428).

In common with other subscripts, the map subscript operator returns an lvalue (§ 4.1.1, p. 135). Because the return is an lvalue, we can read or write the element:

cout << word_count["Anna"]; // fetch the element indexed by Anna; prints 1
++word_count["Anna"];       // fetch the element and add 1 to it
cout << word_count["Anna"]; // fetch the element and print it; prints 2

The fact that the subscript operator adds an element if it is not already in the map allows us to write surprisingly succinct programs such as the loop inside our word-counting program (§ 11.1, p. 421). On the other hand, sometimes we only want to know whether an element is present and do not want to add the element if it is not. In such cases, we must not use the subscript operator.

11.3.5. Accessing Elements

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:

Table 11.7. Operations to Find Elements in an Associative 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:

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.

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.

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.

If the contents of the word-transformation file are

The function starts by calling buildMap to generate the word-transformation map. We store the result in trans_map. The rest of the function processes the input file. The while loop uses getline to read the input file a line at a time. We read by line so that our output will have line breaks at the same position as in the input file. To get the words from each line, we use a nested while loop that uses an istringstream (§ 8.3, p. 321) to process each word in the current line.

The inner while prints the output using the bool firstword to determine whether to print a space. The call to transform obtains the word to print. The value returned from transform is either the original string in word or its corresponding transformation from trans_map.

Building the Transformation Map

The buildMap function reads its given file and builds the transformation map.

map<string, string> buildMap(ifstream &map_file)
{
    map<string, string> trans_map;  // holds the transformations
    string key;    // a word to transform
    string value;  // phrase to use instead
    // read the first word into key and the rest of the line into value
    while (map_file >> key && getline(map_file, value))
        if (value.size() > 1) // check that there is a transformation
            trans_map[key] = value.substr(1); // skip leading space
        else
            throw runtime_error("no rule for " + key);
    return trans_map;
}

Each line in map_file corresponds to a rule. Each rule is a word followed by a phrase, which might contain multiple words. We use >> to read the word that we will transform into key and call getline to read the rest of the line into value. Because getline does not skip leading spaces (§ 3.2.2, p. 87), we need to skip the space between the word and its corresponding rule. Before we store the transformation, we check that we got more than one character. If so, we call substr (§ 9.5.1, p. 361) to skip the space that separated the transformation phrase from its corresponding word and store that substring in trans_map,

Note that we use the subscript operator to add the key–value pairs. Implicitly, we are ignoring what should happen if a word appears more than once in our transformation file. If a word does appear multiple times, our loops will put the last corresponding phrase into trans_map. When the while concludes, trans_map contains the data that we need to transform the input.

Generating a Transformation

The transform function does the actual transformation. Its parameters are references to the string to transform and to the transformation map. If the given string is in the map, transform returns the corresponding transformation. If the given string is not in the map, transform returns its argument:

We start by calling find to determine whether the given string is in the map. If it is, then find returns an iterator to the corresponding element. Otherwise, find returns the off-the-end iterator. If the element is found, we dereference the iterator, obtaining a pair that holds the key and value for that element (§ 11.3, p. 428). We return the second member, which is the transformation to use in place of s.