Multimap

Multimap

Overview

The map container described previously had the restriction that all of the keys had to be unique. Associating a value with a key overwrote the value previously associated with that key. The multimap container, however, has no such restriction. As many values as you choose can be associated with a particular key. This flexibility comes at the price of making multimap more difficult to use, as will be discussed below. A good understanding of the map container is required to understand this document.

Declaring a Multimap

To use multimap, you must #include <map>. Like all of the C++ Standard Library, multimap is declared with the std namespace. You can declare an instance of a multimap with a declaration similar to the following:

using namespace std;
multimap<string, int> mMap;

The above declaration would specify a map that associates strings with integers. The multimap container provides bidirectional iterators. The following declaration demonstrates how to declare an iterator for multimap:

multimap<string, int>::iterator itr;

Creating Key/Value Associations

You can add a key/value association to a multimap by calling the multimap::insert() method. insert() accepts a pair object that specifies the key/value association you want to add. The "first" member of the pair object is the key, and the "second" member of the pair specifies the value to associate with the key. For example, the following code would add an association of the value 3 with the string "Bob."

mMap.insert(make_pair(string("Bob"), int(3)));

More info on the pair class template and make_pair() can be found in the documentation for map.

How to Access the Value(s) Associated With a Key

The multimap::find() method returns an iterator to the first pair object that is associated with a given key. To access the entire sequence of values associated with a key, you can call multimap::upper_bound() to get an iterator that is one past the last pair object that is associated with the given key. This will give you starting and ending iterators, which you can then use to traverse the sequence of values associated with the key. I know that's a mouthful. Take a deep breath and read it again. :) Here is a clarifying example:

void PrintAllValuesAssociatedWithKey(multimap<string, int> &mMap, string &key)
{
	multimap<string, int>::iterator itr;
	multimap<string, int>::iterator lastElement;
	
	// locate an iterator to the first pair object associated with key
	itr = mMap.find(key);
	if (itr == mMap.end())
		return; // no elements associated with key, so return immediately

	cout << "The following values are associated with the key " << key << endl;
	
	// get an iterator to the element that is one past the last element associated with key
	lastElement = mMap.upper_bound(key);

	// for each element in the sequence [itr, lastElement)
	for ( ; itr != lastElement; ++itr)
		cout << itr->second << endl;

}

Element Requirements

The multimap container's element requirements for both the key and value types are exactly the same as for map. Look at the map document for more information.

Methods

Multimap defines the following methods:

Operation	Description	Time Complexity
swap	Swaps elements with another multimap. This operation is performed in constant time. Ex: multimap1.swap(multimap2);	O(1)
count	Returns the number of values associated with a particular key. Ex: cout << multimap1.count("Bob"); // display the number of values associated with "Bob"	O(log n + m) m=number of values associated with the key
upper_bound	Returns an iterator to the pair object that is one element beyond the last element associated with key. Returns multimap::end() if no such element exists. This function is useful for determining the starting and ending iterators for the sequence of values that are associated with a given key. Ex: if (itr == multimap1.upper_bound("Bob")) cout << "No more values associated with Bob. \n";	O(log n)
lower_bound	Returns an iterator to the first pair object whose key is greater than or equal to the given key. Returns multimap::end() if no such element exists. Ex: itr = multimap1.lower_bound("Bob");	O(log n)
begin	Returns an iterator to the first pair in the multimap. Ex: itr = multimap1.begin();	O(1)
end	Returns an iterator that is just beyond the end of the multimap.	O(1)
size	Returns the number of elements contained by the multimap. You should use empty() to test whether or not size equals 0, because empty() may be much faster. cout << multimap1.size();	O(n) or better.
empty	Returns true if the multimap contains zero elements.	O(1)
find	Accepts a key and returns an iterator to the first pair element that matches the key. If the key is not found in the multimap, this method returns end(). if ( (itr = multimap1.find("Bob")) == multimap1.end()) cerr << "Bob was not found in the multimap." << endl; else cout << "Bob was found in the multimap." << endl;	O(log n)
insert	Adds the key/value association specified by a pair object to the multimap. The first member of the pair is the key, and the second value is the value associated with key. Ex: multimap1.insert(make_pair(string("Bob"), int(5)));	O(log n)
erase	There are three overloaded forms of this method. The first accepts a single iterator, and removes the element implied by the iterator from the multimap. The multimap should be non-empty. O(1). Ex: assert(!multimap1.empty()); multimap1.erase(multimap1.begin()); // remove the first element The second accepts two iterators, that specify a range of values within the multimap to be removed. The time complexity is logarithmic plus linear time for the length of the sequence being removed. The two iterators must be valid iterators within the sequence contained by the multimap. Formally, the range of values [starting, ending) are removed. At worst, this is an O(n) operation. Ex: multimap1.erase(multimap1.begin(), multimap1.end()); // erase the entire multimap The last accepts an object of the key type, and removes all occurrences of the key from multimap. O(log n + m). m=The number of values associated with the given key. Ex: multimap1.erase(string("Bob")); // removes all occurences of "Bob"	See description

Notes on Interpreting the Above Table

For the example code in the above table, <map>, <iostream>, and <string> are assumed to be #include'd, and the line "using namespace std;" is assumed to appear at the top of the source file. Also, the following declarations are assumed:

multimap<string, int> multimap1;

multimap<string, int> multimap2;

mutlimap<string, int>::iterator itr;

Author: Rodney Myers 4/23/00