Section 10.3. The map Type

10.3. The map Type

A map is a collection of keyvalue pairs. The map type is often referred to as an associative array: It is like the built-in array type, in that the key can be used as an index to fetch a value. It is associative in that values are associated with a particular key rather than being fetched by position in the array.

10.3.1. Defining a map

To use a map, we must include the map header. When we define a map object, we must indicate both the key and value type:

      // count number of times each word occurs in the input      map<string, int> word_count; // empty map from string to int 

defines a map object word_count that is indexed by a string and that holds an associated int value.

Table 10.3. Constructors for map

map<k, v> m;	Create an empty map named m with key and value types k and v.
map<k, v> m(m2);	Create m as a copy of m2; m and m2 must have the same key and value types.
map<k, v> m(b, e);	Create m as a copy of the elements from the range denoted by iterators b and e. Elements must have a type that can be converted to pair<const k, v>.

Constraints on the Key Type

Whenever we use an associative container, its keys have not only a type, but also an associated comparison function. By default, the library uses the < operator for the key type to compare the keys. Section 15.8.3 (p. 605) will show how we can override the default and provide our own function.

Whichever comparison function we use must define a strict weak ordering over the key type. We can think of a strict weak ordering as "less than," although we might choose to define a more complicated comparison function. However we define it, such a comparison function must always yield false when we compare a key with itself. Moreover, if we compare two keys, they cannot both be "less than" each other, and if k1 is "less than" k2, which in turn is "less than" k3, then k1 must be "less than" k3. If we have two keys, neither of which is "less than" the other, the container will treat them as equal. When used as a key to a map, either value could be used to access the corresponding element.

In practice, what's important is that the key type must define the < operator and that that operator should "do the right thing."

As an example, in our bookstore problem, we might add a type named ISBN that would encapsulate the rules for ISBNs. In our implementation, ISBNs are strings, which we can compare to determine which ISBN is less than another. Therefore, the ISBN type could support a < operation. Given that we had such a type, we could define a map that would allow us to efficiently search for a particular book held by a bookstore.

      map<ISBN, Sales_item> bookstore; 

defines a map object named bookstore that is indexed by an ISBN. Each element in the map holds an associated instance of our Sales_item class.

The key type needs to support only the < operator. There is no requirement that it support the other relational or equality operators.

Exercises Section 10.3.1

Exercise 10.5:	Define a map that associates words with a list of line numbers on which the word might occur.
Exercise 10.6:	Could we define a map from vector<int>::iterator to int? What about from list<int>::iterator to int? What about from pair<int, string> to int? In each case, if not, explain why not.

10.3.2. Types Defined by map

The elements of a map are keyvalue pairs That is, each element has two parts: its key and the value associated with that key. The value_type for a map reflects this fact. This type is more complicated than those we've seen for other containers: value_type is a pair that holds the key and value of a given element. Moreover, the key is const. For example, the value_type of the word_count array is pair<const string, int>.

Table 10.4. Types Defined by the map Class

map<K, V>::key_type	The type of the keys used to index the map.
map<K, V>::mapped_type	The type of the values associated with the keys in the map.
map<K, V>::value_type	A pair whose first element has type const
	map<K, V>::key_type and second has type
	map<K, V>::mapped_type.

When learning the map interface, it is essential to remember that the value_type is a pair and that we can change the value but not the key member of that pair.

Dereferencing a map Iterator Yields a pair

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:

      // get an iterator to an element in word_count      map<string, int>::iterator map_it = word_count.begin();      // *map_it is a reference to a pair<const string, int> 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 value through an iterator 

Dereferencing the iterator yields a pair object in which first member holds the const key and second member holds the value.

Additional map Typedefs

The map class defines two additional types, key_type and mapped_type, that let us access the type of either the key or the value. For word_count, the key_type is string and mapped_type is int. As with the sequential containers (Section 9.3.1, p. 317), we use the scope operator to fetch a type memberfor example, map<string, int>::key_type.

Exercises Section 10.3.2

Exercise 10.7:	What are the mapped_type, key_type, and value_type of a map from int to vector<int>?
Exercise 10.8:	Write an expression using a map iterator to assign a value to an element.

10.3.3. Adding Elements to a map

Once the map is defined, the next step is to populate it with the keyvalue element pairs. We can do so either by using the insert member or by fetching an element using the subscript operator and then assigning a value to the element returned. In both cases, the fact that there can be only a single element for a given key affects the behavior of these operations.

10.3.4. Subscripting a map

When we write

      map <string, int> word_count; // empty map      // insert default initialzed element with key Anna; then assign 1 to its value      word_count["Anna"] = 1; 

the following steps take place:

1.	word_count is searched for the element whose key is Anna. The element is not found.
2.	A new keyvalue 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.
3.	The new keyvalue pair is inserted into word_count.
4.	The newly inserted element is fetched and is given the value 1.

Subscripting a map behaves quite differently from subscripting an array or vector: Using an index that is not already present adds an element with that index to the map.

As with other subscript operators, the map subscript takes an index (that is, a key) and fetches the value associated with that key. When we look for a key that is already in the map, then the behavior is the same for a map subscript or a vector subscript: The value associated with the key is returned. For maps only, 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: An element of class type is initialized using the default constructor for the element type; a built-in type is initialized to 0.

Using the Value Returned from a Subscript Operation

As usual, the subscript operator returns an lvalue. The lvalue it returns is the value associated with the key. We can read or write the element:

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

Unlike vector or string, the type returned by map subscript operator differs from the type obtained by dereferencing a map iterator.

As we've seen, a map iterator returns a value_type, which is a pair that contains a const key_type and mapped_type; the subscript operator returns a value of type mapped_type.

Programming Implications of the Subscript Behavior

The fact that subscript adds an element if it is not already in the map allows us to write surprisingly succinct programs:

      // count number of times each word occurs in the input      map<string, int> word_count; // empty map from string to int      string word;      while (cin >> word)        ++word_count[word]; 

This program creates a map that keeps track of how many times each word occurs. The while loop reads the standard input one word at a time. Each time it reads a new word, it uses that word to index word_count. If word is already in the map, then its value is incremented.

The interesting part is what happens when a word is encountered for the first time: A new element indexed by word, with an initial value of zero, is created and inserted into word_count. The value of that element is immediately incremented so that each time we insert a new word into the map it starts off with an occurrence count of one.

Exercises Section 10.3.4

Exercise 10.9:	Write a program to count and print the number of times each word occurs in the input.
Exercise 10.10:	What does the following program do? map<int, int> m; m[0] = 1; Contrast the behavior of the previous program with this one: vector<int> v; v[0] = 1;
Exercise 10.11:	What type can be used to subscript a map? What type does the sub-script operator return? Give a concrete examplethat is, define a map and then write the types that could be used to subscript the map and the type that would be returned from the subscript operator.

10.3.5. Using map::insert

The insert members operate similarly to the operations on sequential containers (Section 9.3.3, p. 318), with one important caveat: We must account for the effect of the key. The key impacts the argument types: The versions that insert a single element take a value that is a keyvalue pair. Similarly, for the version that takes an iterator pair, the iterators must refer to elements that are keyvalue pairs. The other difference is the return type from the version of insert that takes a single value, which we will cover in the remainder of this section.

Using insert Instead of Subscripting

When we use a subscript to add an element to a map, the value part of the element is value-initialized. Often we immediately assign to that value, which means that we've initialized and assigned the same object. Alternatively, we could insert the element directly by using the syntactically more intimidating insert member:

      // if Anna not already in word_count, inserts new element with value 1      word_count.insert(map<string, int>::value_type("Anna", 1)); 

Table 10.5. insert Operations on maps

m.insert(e)	e is a value of the value_type for m. If the key(e.first) is not in m, inserts a new element with value e.second. If the key is in m, then m is unchanged. Returns a pair containing a map iterator referring to the element with key e.first and a bool indicating whether the element was inserted or not.
m.insert(beg, end)	beg and end are iterators that denote a range of values that are keyvalue pairs with the same type as m's value_type. For each element in the range, if the given key is not already in m, it inserts the key and its associated value into m. Returns void.
m.insert(iter, e)	e is a value of the value_type for m. If the key(e.first) is not in m, inserts the new element using the iterator iter as a hint for where to begin the search for where the new element should be stored. Returns an iterator that refers to the element in m with given key.

The argument to this version of insert

      map<string, int>::value_type(anna, 1) 

is a newly created pair that is directly inserted into the map. Remember that value_type is a synonym for the type pair<const K, V>, where K is the key type and V is the type of the associated value. The argument to insert constructs a new object of the appropriate pair type to insert into the map. By using insert, we can avoid the extraneous initialization of the value that happens when we insert a new map element as a side-effect of using a subscript.

The argument to insert is fairly unwieldy. There are two ways to simplify it. We might use make_pair:

      word_count.insert(make_pair("Anna", 1)); 

Or use a typedef:

      typedef map<string,int>::value_type valType;      word_count.insert(valType("Anna", 1)); 

Either approach improves readability by making the call less complicated.

Testing the Return from insert

There can be only one element with a given key in a map. If we attempt to insert an element with a key that is already in the map, then insert does nothing. The versions of insert that take an iterator or iterator pair do not indicate whether or how many elements were inserted.

However, the version of insert that takes a single keyvalue pair does return a value. That value is a pair that contains an iterator that refers to the element in the map with the corresponding key, and a bool that indicates whether the element was inserted. If the key is already in the map, then the value is unchanged, and the bool portion of the return is false. If the key isn't present, then the element is inserted and the bool is TRue. In either case, the iterator refers to the element with the given key. We could rewrite our word count program to use insert:

      // count number of times each word occurs in the input      map<string, int> word_count; // empty map from string to int      string word;      while (cin >> word) {          // inserts element with key equal to word and value 1;          // if word already in word_count, insert does nothing          pair<map<string, int>::iterator, bool> ret =                    word_count.insert(make_pair(word, 1));          if (!ret.second)          // word already in word_count              ++ret.first->second;  // increment counter      } 

For each word, we attempt to insert it with a value 1. The if test examines the bool in the return from the insert. If it is false, then the insertion didn't happen and an element indexed by word was already in word_count. In this case we increment the value associated with that element.

Unwinding the Syntax

The definition of ret and the increment may be hard to decipher:

      pair<map<string, int>::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, int> type.

We can understand the increment by first parenthesizing it to reflect the precedence (Section 5.10.1, p. 168) of the operators:

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

Explaining this expression step by step, we have

• ret holds return value from insert, which is a pair. The first member of that pair is a map iterator referring to the key that was inserted.

• ret.first fetches the map iterator from the pair returned by insert.

• ret.first->second dereferences that iterator obtaining a value_type object. That object is also a pair, in which the second member is the value part of the element we added.

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

Putting it back together, the increment statement fetches the iterator for the element indexed by word and increments the value part of that element.

Exercises Section 10.3.5

Exercise 10.12:	Rewrite the word-count program that you wrote in the exercises for Section 10.3.4 (p. 364) to use insert instead of subscripting. Explain which program you think is easier to write and read. Explain your reasoning.
Exercise 10.13:	Given a map<string, vector<int> >, write the types used as an argument and as the return value for the version of insert that inserts one element.

10.3.6. Finding and Retrieving a map Element

The subscript operator provides the simplest method of retrieving a value:

      map<string,int> word_count;      int occurs = word_count["foobar"]; 

As we've 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. In this example, if "foobar" weren't already present, it would be added to the map with an associated value of 0. In this case, occurs gets a value of 0.

Our word-counting programs relied on the fact that subscripting a nonexistent element inserts that element and initializes the value to 0. There are times, though, when we want to know if an element is present but do not want the element inserted if it is not present. In such cases, we cannot use the subscript operator to determine whether the element is present.

There are two operations, count and find, that we can use to determine if a key is present without causing it to be inserted.

Table 10.6. Interrogating a map Without Changing It

m.count(k)	Returns the number of occurrences of k within m.
m.find(k)	Returns an iterator to the element indexed by k, if there is one, or returns an off-the-end iterator (Section 3.4, p. 97) if the key is not present.

Using count to Determine Whether a Key is in the map

The count member for a map always returns either 0 or 1. A map may have only one instance of any given key, so count effectively indicates whether the key is present. The return from count is more useful for multimaps, which we cover in Section 10.5 (p. 375). If the return value is nonzero, we can use the subscript operator to fetch the value associated with the key without worrying that doing so will insert the element into the map:

      int occurs = 0;      if (word_count.count("foobar"))          occurs = word_count["foobar"]; 

Of course, executing count followed by the subscript effectively looks for the element twice. If we want to use the element if it is present, we should use find.

Retrieving an Element Without Adding It

The find operation returns an iterator to the element or the end iterator if the element is not present:

      int occurs = 0;      map<string,int>::iterator it = word_count.find("foobar");      if (it != word_count.end())          occurs = it->second; 

We should use find when we want to obtain a reference to the element with the specified key if it exists, and do not want to create the element if it does not exist.

Exercises Section 10.3.6

Exercise 10.14:	What is the difference between the map operations count and find?
Exercise 10.15:	What kinds of problems would you use count to solve? When might you use find instead?
Exercise 10.16:	Define and initialize a variable to hold the result of a call to find on a map from string to vector of int.

10.3.7. Erasing Elements from a map

There are three variants of the erase operation to remove elements from a map. As with the sequential containers, we can erase a single 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 with one exception: The map operations return void, whereas those on the sequential containers return an iterator to the element following the one that was removed.

The map type supplies an additional erase operation that takes a value of the key_type and removes the element with the given key if the element exists. We could use this version to remove a specific word from word_count before printing the results:

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

The erase function returns a count of how many elements were removed. In the case of a map, that number is either zero or one. If the return value is zero, then the element we wanted to erase was not in the map.

Table 10.7. Removing Elements from a map

m.erase(k)	Removes the element with key k from m. Returns size_type indicating the number of elements removed.
m.erase(p)	Removes element referred to by the iterator p from m. p must refer to an actual element in m; it must not be equal to m.end(). Returns void.
m.erase(b, e)	Removes the elements in the range denoted by the iterator pair b, e. b and e must be a valid range of elements in m: b and e must refer to elements in m or one past the last element in m. b and e must either be equalin which case the range is emptyor the element to which b refers must occur before the element referred to by e. Returns void.

10.3.8. Iterating across a map

Like any other container, map provides begin and end operations that yield iterators that we can use to traverse the map. For example, we could print the map named word_count that we built on page 363 as follows:

      // get iterator positioned on the first element      map<string, int>::const_iterator                              map_it = word_count.begin();      // for each element in the map      while (map_it != word_count.end()) {          // print the element key, value pairs          cout << map_it->first << " occurs "               << map_it->second << " times" << endl;          ++map_it; // increment 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 body of the loop is more complicated than those earlier programs because we must print both the key and value for each element.

The output of our word-count program prints the words in alphabetical order. When we use an iterator to traverse a map, the iterators yield elements in ascending key order.

10.3.9. A Word Transformation Map

We'll close this section with a program to illustrate creating, searching, and iterating across a map. Our problem is to write a program that, given one string, transforms it into another. The input to our program is two files. The first file contains several word pairs. The first word in the pair is one that might be in the input string. The second is the word to use in the output. Essentially, this file provides a set of word transformationswhen we find the first word, we should replace it by the second. The second file contains the text to transform. If the contents of the word transformation file is

'em	them
cuz	because
gratz	grateful
i	I
nah	no
pos	supposed
sez	said
tanx	thanks
wuz	was

and the text we are given to transform is

      nah i sez tanx cuz i wuz pos to      not cuz i wuz gratz 

then the program should generate the following output:

      no I said thanks because I was supposed to      not because I was grateful 

The Word Transformation Program

Our solution, which appears on the next page, stores the word transformation file in a map, using the word to be replaced as the key and the word to use as the replacement as its corresponding value. We then read the input, looking up each word to see if it has a transformation. If so, we do the transformation and then print the transformed word. If not, we print the original word.

Our main program takes two arguments (Section 7.2.6, p. 243): the name of the word transformation file and the name of the file to transform. We start by checking the number of arguments. The first argument, argv[0], is always the name of the command. The file names will be in argv[1] and argv[2].

Once we know that argv[1] is valid, we call open_file (Section 8.4.3, p. 299) to open the word transformation file. Assuming the open succeeded, we read the transformation pairs. We call insert using the first word as the key and the second as the value. When the while concludes, trans_map contains the data we need to transform the input. If there's a problem with the arguments, we throw (Section 6.13, p. 215) an exception and exit the program.

Next, we call open_file to open the file we want to transform. The second while uses getline to read that file a line at a time. We read by line so that our output will have line breaks at the same position as our input file. To get the words from each line we use a nested while loop that uses an istringstream. This part of the program is similar to the sketch we wrote on page 300.

The inner while checks each word to see if it is in the transformation map. If it is, then we replace the word by its corresponding value from the map. Finally, we print the word, transformed or not. We use the bool firstword to determine whether to print a space. If it is the first word in the line, we don't print a space.

     /*      * A program to transform words.      * Takes two arguments: The first is name of the word transformation file      *                      The second is name of the input to transform      */     int main(int argc, char **argv)     {         // map to hold the word transformation pairs:         // key is the word to look for in the input; value is word to use in the output         map<string, string> trans_map;         string key, value;         if (argc != 3)             throw runtime_error("wrong number of arguments");         // open transformation file and check that open succeeded         ifstream map_file;         if (!open_file(map_file, argv[1]))             throw runtime_error("no transformation file");         // read the transformation map and build the map          while (map_file >> key >> value)              trans_map.insert(make_pair(key, value));         // ok, now we're ready to do the transformations         // open the input file and check that the open succeeded         ifstream input;         if (!open_file(input, argv[2]))             throw runtime_error("no input file");         string line;    // hold each line from the input         // read the text to transform it a line at a time         while (getline(input, line)) {             istringstream stream(line);   // read the line a word at a time             string word;             bool firstword = true;   // controls whether a space is printed             while (stream >> word) {                // ok: the actual mapwork, this part is the heart of the program                map<string, string>::const_iterator map_it =                                   trans_map.find(word);                // if this word is in the transformation map                if (map_it != trans_map.end())                    // replace it by the transformation value in the map                    word = map_it->second;                if (firstword)                    firstword = false;                else                    cout << " ";  // print space between words                cout << word;             }             cout << endl;        // done with this line of input     }     return 0;  } 

Exercises Section 10.3.9

Exercise 10.17:	Our transformation program uses find to look for each word: map<string, string>::const_iterator map_it = trans_map.find(word); Why do you suppose the program uses find? What would happen if it used the subscript operator instead?
Exercise 10.18:	Define a map for which the key is the family surname and the value is a vector of the children's names. Populate the map with at least six entries. Test it by supporting user queries based on a surname, which should list the names of children in that family.
Exercise 10.19:	Extend the map from the previous exercise by having the vector store a pair that holds a child's name and birthday. Revise the program accordingly. Test your modified test program to verify its correctness.
Exercise 10.20:	List at least three possible applications in which the map type might be of use. Write the definition of each map and indicate how the elements are likely to be inserted and retrieved.