Use multimap to Create Associative Containers with Duplicate Keys

n a previous column, I discussed the Standard Library’s map associative container. But this was only one half the story. The Standard Library also defines a multimap container, which is similar to map except that it allows duplicate keys. This property makes multimap more useful than it seems at first: think of a phone book in which the same person may have two or more phone numbers, a file system in which multiple symbolic links are mapped to the same physical file, or to a DNS server that maps several URLs to the same IP address. In such cases, you’d want to do something like this:

//note: pseudo codemultimap  phonebook;phonebook.insert("Harry","8225687"); //homephonebook.insert("Harry","555123123"); //workphonebook.insert("Harry"," 2532532532"); //mobile

The ability to store duplicate keys in multimap heavily affects its interface and usage.


How to create an associative container with non-unique keys?


Use the multimap container defined in the

library.

Presenting the Problem
Unlike with map, multimap may contain non-unique keys. This presents a problem: how can the overloaded subscript operator return multiple associated values for the same key? Consider the following example:

//note: pseudo-codestring phone=phonebook["Harry];

The Standard Library designers resolved this issue by removing the subscript operator from multimap. Consequently, insertion and retrieval of elements require different methods and error handling policies.

Insertion
Suppose you need to develop a DNS daemon (or service, in Windows parlance) that maps an IP address to a matching URL string. You know that in some cases, the same IP address is associated with two or more URLs, all of them pointing to the same site. In this case, you want to use multimap instead of map. You create a multimap like this:

#include #include multimap  DNS_daemon;

Instead of the subscript operator, use the insert() member function to insert elements. insert() takes a pair as its argument. The previous 10-Minute Solution demonstrated how to use the make_pair() helper function to facilitate this task. You can use it here as well:

DNS_daemon.insert(make_pair("213.108.96.7",                            "cppzone.com"));

In the insert() call above the string 213.108.96.7 serves as the key and cppzone.com as its associated value. Here’s a subsequent insertion of the same key but with a different associated value:

DNS_daemon.insert(make_pair("213.108.96.7",                            "cppluspluszone.com"));

Consequently, DNS_daemon contains two elements with the same key. Notice that the return values of multimap::insert() and map::insert() aren’t the same:

typedef pair  value_type;iterator  insert(const value_type&); // #1 multimappair  insert(const value_type&); // #2 map

The multimap::insert() member function returns an iterator pointing to the newly inserted element (multimap::insert() always succeeds). map::insert() however returns pair , where the bool value indicates whether the insertion was successful.

Finding a Single Value
multimap, like map, has two overloaded versions of the find() member function:

iterator find(const key_type& k);const_iterator find(const key_type& k) const;

find(k) returns an iterator to the first pair that matches the key k. This means it’s mostly useful when you want to check whether there is at least one value associated with the key or when you need only the first match. For example:

typedef multimap  mmss;void func(const mmss & dns){ mmss::const_iterator cit=dns.find("213.108.96.7"); if (cit != dns.end())  cout <<"213.108.96.7 found" <

Handling Multiple Associated Values
The count(k) member function returns the number of values associated with a given key. The following example reports how many values are associated with the key 213.108.96.7:

cout<

To access multiple values in a multimap, use the equal_range(), lower_bound() and upper_bound() member functions:

  • equal_range(k): This function finds all of the values associated with the key k. This function returns a pair of iterators that mark the beginning and the end of the range. The following example displays all the values associated with the key 213.108.96.7:
    typedef multimap ::const_iterator CIT; typedef pair Range;Range range=dns.equal_range("213.108.96.7");for(CIT i=range.first; i!=range.second; ++i) cout << i->second << endl; //output: cpluspluszone.com                            //        cppzone.com
  • lower_bound() and upper_bound(): lower_bound(k) finds the first value associated with the key k, and upper_bound(k) finds the first element whose key is greater than k. The following example uses upper_bound() to locate the first element whose key is greater than 213.108.96.7. As usual, when the key is of type string a lexicographical comparison takes place:
    dns.insert(make_pair("219.108.96.70",                      "pythonzone.com"));CIT cit=dns.upper_bound("213.108.96.7");if (cit!=dns.end()) //found anything? cout<second<

    If you wish to display all the subsequent values, use a loop like this:

    //insert multiple values with the same keydns.insert(make_pair("219.108.96.70",                     "pythonzone.com"));dns.insert(make_pair("219.108.96.70",                     "python-zone.com"));//get an iterator to the first valueCIT cit=dns.upper_bound("213.108.96.7");//output: pythonzone.com python-zone.com while(cit!=dns.end()){ cout<second<

Concept Mapping
Although map and multimap have similar interfaces, the crucial difference between the two, with respect to duplicate keys, entails different design and usage. In addition, you should be aware of the subtle differences between the insert() member function of each container.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

The Latest

microsoft careers

Top Careers at Microsoft

Microsoft has gained its position as one of the top companies in the world, and Microsoft careers are flourishing. This multinational company is efficiently developing popular software and computers with other consumer electronics. It is a dream come true for so many people to acquire a high paid, high-prestige job

your company's audio

4 Areas of Your Company Where Your Audio Really Matters

Your company probably relies on audio more than you realize. Whether you’re creating a spoken text message to a colleague or giving a speech, you want your audio to shine. Otherwise, you could cause avoidable friction points and potentially hurt your brand reputation. For example, let’s say you create a

chrome os developer mode

How to Turn on Chrome OS Developer Mode

Google’s Chrome OS is a popular operating system that is widely used on Chromebooks and other devices. While it is designed to be simple and user-friendly, there are times when users may want to access additional features and functionality. One way to do this is by turning on Chrome OS

©2023 Copyright DevX - All Rights Reserved. Registration or use of this site constitutes acceptance of our Terms of Service and Privacy Policy.

Sitemap