Using Duplicate Keys with a multimap

By John Paul Mueller, Jeff Cogswell

A map provides a method for quickly working with lists of data in such a manner that you can access each element easily with a key. Using a map is convenient because you can access the items in a random order. However, every key must be unique. It’s not as if your application will fail if you assign a value to a duplicate key — the duplicate will simply overwrite the original value. Here’s an example:

#include <iostream>
#include <map>
using namespace std;
int main()
{
    map<string, string> marriages;
    marriages["Tom"] = "Suzy";
    marriages["Harry"] = "Harriet";
    marriages["Tom"] = "Amy";
    cout << marriages["Tom"] << endl;
    cout << marriages["Harry"] << endl;
    return 0;
}

Note that there are actually two men named Tom, but they have wives with different names. When you run this example, you don’t get the expected output:

Amy
Harriet

The original value is lost because a map can only have one key named Tom. You can use a multimap to overcome this problem. A multimap has the same basic premise of letting you assign values based on a key, but the resulting variable can have duplicate entries. Here is an example of a multimap that addresses our issue:

#include <iostream>
#include <map>
using namespace std;
int main()
{
    multimap<string, string> marriages;
    marriages.insert(pair<string, string>("Tom", "Suzy"));
    marriages.insert(pair<string, string>("Harry", "Harriet"));
    marriages.insert(pair<string, string>("Tom", "Amy"));
    for (multimap<string, string>::iterator Values = marriages.begin();
        Values != marriages.end(); ++Values)
        {
            cout << (*Values).first << " is married to " <<
                (*Values).second << endl;
        }
    cout << endl << "Women Married to Men Named Tom" << endl;
    multimap<string, string>::const_iterator Values =
        marriages.find("Tom");
    int Number = marriages.count("Tom");
    for (int i = 0; i < Number; i++)
    {
        cout << Values->second << endl;
        ++Values;
    }
    return 0;
}

In this case, you still create an object containing two string objects, the first of which is the key. An insert() function lets you add new entries to marriages. The technique is different from using a standard map, but the result is the same. Each entry consists of two string values.

To display the entries, you must work with iterators. The example shows two approaches you can use. The first lists all of the entries in marriages. It begins by creating an iterator that points to the beginning of marriages using the marriages.begin() function. The loop continues while Values isn’t equal to marriages.end(). Notice the prefix notation used to update Values to the next entry in the list. It’s also important to note that Values provides a pointer to the data, so you must use either (*Values).first to access the first string in the entry or Values->first.

A multimap is actually quite flexible. You can count the number of duplicate key entries using the count() function. In order to use this function, you must provide the key value you want to locate. The find() function makes it possible to create an iterator that only contains the entries for a specific key. The example shows a technique for iterating through the values that you find. The output from this example looks like this:

Harry is married to Harriet
Tom is married to Suzy
Tom is married to Amy
Women Married to Men Named Tom
Suzy
Amy