Map and Multimap Operations

The member functions provided by the map and multimap data types will shortly be described in more detail. Note that while member functions provide basic operations, the utility of the data structure is greatly extended through the use of the generic algorithms described in Chapters 13 and 14.

The declaration of a map follows the pattern we have seen repeatedly in the standard library. A map is a template data structure, specialized by the type of the key elements, the type of the associated values, and the operator to be used in comparing keys. If your compiler supports default template types (a relatively new feature in C++ not yet supported by all vendors), then the last of these is optional, and if not provided, the less than operator for the key type will be assumed. Maps 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
    map<double, string, less<double> > map_one;
    // map indexed by integers, containing integers   
    map<int, int> map_two(aContainer.begin(), aContainer.end());
    // create a new map, initializing it from map two
    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 (in a manner analogous to other standard library containers).

The classes map and multimap include a number of type definitions. These are most commonly used in declaration statements. For example, an iterator for a map of strings to integers can be declared in the following fashion:

map<string, int>::iterator location;
 

In addition to iterator, the following types are defined:

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 data type value_type associated with the map.

   map_three.insert (map<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.

   cout << "Index value 7 is " << map_three[7] << endl;
       // now change the associated value
    map_three[7] = 5;
    cout << "Index value 7 is " << map_three[7] << 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; as, for example, the iterator yielded by a find() operation. A pair of iterators can be used to erase an entire range of elements.

   // erase the 4th element 4
    map_three.erase(4);
    // erase the 5th element 
    mtesttype::iterator five = map_three.find(5);
    map_three.erase(five);
    
    // erase all values between the 7th and 11th elements
    mtesttype::iterator seven = map_three.find(7);
    mtesttype::iterator eleven = map_three.find(11);
    map_three.erase (seven, eleven);
    

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

No Iterator Invalidation

The member functions begin() and end() produce bidirectional iterators for both maps and multimaps. Dereferencing an iterator for either a map or a multimap will yield 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 will be 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.

The member function size() will yield the number of elements held by a container. The member function empty() will return 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. In the case of 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())
       cout << "contains a 4th element" << 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 will be presented later in this section.

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))
       cout << "contains a 4th element" << 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 will have any effect on the container.

if (map_two.key_comp (i, j)) 
    cout << "element i is less than j" << endl;
 

Because maps and multimaps are ordered collections, and because the iterators for maps return pairs, many of the functions described in Sections 13 and 14 are meaningless or difficult to use. However, there are a few notable exceptions. The functions for_each(), adjacent_find(), and 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.