9.2 map and multimap Operations

This section describes the member functions provided by the map and multimap class templates. While member functions provide basic operations, using generic algorithms on map and multimap containers provide even more flexibility. Generic algorithms are described in Part IV.

The declaration of a map follows the pattern we have seen repeatedly in the C++ Standard Library. A map class template is specialized on the type of the keys, the type of the associated values, and an optional comparison operator to be used in comparing keys. If no comparison operator is provided, keys are compared with operator< for the key type.

A map can be declared with no initial elements, or initialized from another container by providing a pair of iterators. In the latter case, the iterators must denote values of type pair; the first field in each pair is taken to be a key, while the second field is a value. A copy constructor also permits maps to be created as copies of other maps:

// map indexed by doubles containing strings
std::map<double, std::string, std::less<double> > map_one;

// map indexed by integers, containing integers   
std::map<int, int> map_two(aContainer.begin(), aContainer.end());

// create a new map, initializing it from map two
std::map<int, int> map_three (map_two);   // copy constructor

A map can be assigned to another map, and two maps can exchange their values using the swap() operation, like the other C++ Standard Library containers.

The class templates map and multimap include a number of type definitions, most commonly used in declaration statements. For example, an iterator for a map of standard strings to ints can be declared as follows:

std::map<std::string, int>::iterator location;

In addition to iterator, map and multimap define the following types:

Table 15: Type definitions for the classes map and multimap 

Values can be inserted into a map or a multimap using the insert() operation. Note that the argument must be a key-value pair. This pair is often constructed using the datatype value_type associated with the map:

map_three.insert(std::map<int,int>::value_type(5, 7));

Insertions can also be performed using an iterator pair, for example, as generated by another map.

map_two.insert(map_three.begin(), map_three.end());

With a map, but not a multimap, values can be accessed and inserted using the subscript operator. Simply using a key as a subscript creates an entry--the default element is used as the associated value. Assigning to the result of the subscript changes the associated binding.

// show value of element indexed by 7
std::cout << "Index value 7 is " << map_three[7] << std::endl;

// now change the value, and show the change
map_three[7] = 5;
std::cout << "Index value 7 is " << map_three[7] << std::endl;

Values can be removed from a map or a multimap by naming the key value. In a multimap, the erasure removes all elements with the associated key. An element to be removed can also be denoted by an iterator, like the iterator yielded by a find() operation. A pair of iterators can be used to erase an entire range of elements:

std::map<char, int> map_one ;

map_one['a'] = 0;
map_one['b'] = 1;

.
.
.

map_one['z'] = 25;

// erase the entry with 'd' as a key

map_one.erase('d');


// alternate way to erase a single entry

// find the entry with 'f' as a key,
// then erase it.

std::map<char,int>::iterator f_pos = map_one.find('f');
map_one.erase(f_pos);

// erase a range of entries starting at the entry with
// 'h' as a key, and stopping at the entry with 'n'
// as a key.

std::map<char,int>::iterator h_pos = map_one.find('h');
std::map<char,int>::iterator n_pos = map_one.find('n');

map_one.erase(h_pos, n_pos);

If the underlying element type provides a destructor, the destructor is invoked prior to removing the key and value pair from the collection.

The member functions begin() and end() produce bidirectional iterators for both maps and multimaps. Dereferencing an iterator for either a map or a multimap yields a pair of key/value elements. The field names first and second can be applied to these values to access the individual fields. The first field is constant, and cannot be modified. The second field, however, can be used to change the value being held in association with a given key. Elements are generated in sequence, based on the ordering of the key fields.The member functions rbegin() and rend() produce iterators that yield the elements in reverse order.

---

NOTE -- Unlike a vector or deque, the insertion or removal of elements from a map does not invalidate iterators which may be referencing other portions of the container.

---

The member function size() yields the number of elements held by a container. The member function empty() returns a boolean true value if the container is empty, and is generally faster than testing the size against zero.

The member function find() takes a key argument, and returns an iterator denoting the associated key/value pair. For multimaps, the first such value is returned. In both cases, the past-the-end iterator is returned if no such value is found:

if (map_one.find(4) != map_one.end())
   std::cout << "contains an element with the key 4"
             << std::endl;

The member function lower_bound() yields the first entry that matches the argument key, while the member function upper_bound() returns the first value past the last entry matching the argument. Finally, the member function equal_range() returns a pair of iterators, holding the lower and upper bounds. An example showing the use of these procedures is presented later in this chapter.

The member function count() returns the number of elements that match the key value supplied as the argument. For a map, this value is always either zero or one, whereas for a multimap it can be any nonnegative value. If you simply want to determine whether or not a collection contains an element indexed by a given key, using count() is often easier than using the find() function and testing the result against the end-of-sequence iterator:

if (map_one.count(4))
   std::cout << "contains an element with the key 4"
             << std::endl;

The member functions key_comp() and value_comp(), which take no arguments, return function objects that can be used to compare elements of the key or value types. Values used in these comparisons need not be contained in the collection, and neither function has any effect on the container.

if (map_two.key_comp()(i, j)) 
  std::cout << "element i sorts before j"
            << std::endl;

Because maps and multimaps are ordered collections, and because the iterators for maps return pairs, many of the functions described in Part IV (Algorithms), are meaningless or difficult to use. However, there are a few notable exceptions. The functions std::for_each(), std::adjacent_find(), and std::accumulate() each have their own uses. In all cases it is important to remember that the functions supplied as arguments should take a key/value pair as arguments.