devxlogo

Use the <map> Library to Create Associative Containers

Why Trust Us

elational databases, scientific apps, and Web-based systems often need a vector-like container whose index can be of any type, not necessarily int. Such containers are known as associative containers or maps. For instance, a directory service application can store private names as indexes and phone numbers as their associated values:

directory["Harry"]=8225687;//insert "Harry" and his #iterator it=directory.find("Harry");//get Harry's phone #

Other applications of associative containers include DNS servers that map URLs to IP addresses, dictionaries, inventories, payrolls, and so on.


How do you implement associative containers whose index type isn’t confined to int?


Use the

library to create and manipulate associative containers.

Pairs and Maps
In a recent 10 Minute Solution, I presented the notion of a tuple, which is a collection of elements of different types. What I didn’t say is that the C++98 Standard Library already has a specialized tuple type called pair. A pair binds a key (known as the first element) with an associated value (known as the second element). For example:

#include  //definition of pair#include pair  prof_and_course("Jones", "Syntax");pair  symbolic_const (0, "false");

The Standard Library also defines a helper function that facilitates the creation of a pair type:

string prof;string course;make_pair(prof,course);//returns pair

Step 1: Constructing and Populating a Map
Suppose you’re developing an address book that contains names and emails. The class template map defined in the header

is an associative container that uses a pair of types, the first of which is the index and the second the associated value.

We can use a map like this:

#include map  addresses;

To add an item to a map, use the subscript operator.

addresses["Paul W."]="[email protected]";

Here, the string Paul W. serves as the index or key, and [email protected]is its associated value. If the map already contains this key, the current associated value is replaced with the new associated value:

addresses["Paul W."]= "[email protected]"; //overrides "[email protected]"

Step 2: Searching
If you wish to check whether a certain element exists without inserting it, use the find() member function. find()has two overloaded versions:

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

As usual, a typedef can make the code less cumbersome:

typedef map ::const_iterator CIT;CIT cit=addresses.find("Paul W.");if (cit==addresses.end())  cout << "sorry, no such key" << endl;else  cout << cit->first << '	' << cit->second << endl;

The expressions cit->first and cit->second return the key and its associated value, respectively.

There is another way to test whether a certain pair is present without changing its associated value, namely, using the insert()member function:

// calls pair map::insert(const value_type& x);// the bool part reports whether the insertion succeededif (addresses.insert(make_pair("Paul W.", "[email protected]")).second== false){      // pair not inserted because the key already has a value      // original value left unchanged}

Step 3: Traversal
Let's look at a more realistic scenario. Suppose you're running a travel agency. Each agent gets a bonus for selling a deal. These bonuses are stored in a file as follows:

Bob 35Bob 90Jane 80.25Sue 100Jane 65.5

Your application has to sum up all these bonuses and print the total for each agent. First, create a map and read the data from the file:

map  bonuses;string agent;double bonus=0; ifstream bonusfile("bonuses.dat");if(!bonusfile){ //report the error and terminate}while (bonusfile >> agent >> bonus){ bonuses[agent]+=bonus;//accumulate bonuses per agent}

Believe it or not, that's all! Let's analyze this loop. After opening the data file, the while-loop reads each pair into the objects agent and bonus. Next, it inserts agent and bonus into the map. The trick here is that if the key (agent) already exists, the += operator adds the newly-read bonus to the current bonus stored in the map. This is possible because the expression

map[key]

returns the value associated with key. This value is then added to the newly-read bonus when the overloaded operator += is invoked. Finally, the sum of these two values overrides the existing associated value in the map.

Luckily, when the map doesn't contain the sought-after key, the expression

map[key]

returns a default-initialized T where Tis double in our example. A default-initialized double equals 0.

At this stage, the map contains pairs of agents and their combined bonus value. The following loop displays these pairs:

for(CIT p=bonuses.begin(); p!=bonuses.end(); ++p){ cout << p->first <<'	' << p->second <
Figure 1. Bonus Boys: The map displays the agents and the associated values that go with them.

The output is shown in Figure 1.

Hashed Associative Containers
The Standard Library doesn't provide a hashed associative containeryet. Such containers can improve performance significantly as they use a hashing algorithm to derive a short key from the original string index. However, many IDEs offer hashed containers as a non-standard extension. Fortunately, the new C++0X standard remedies this omission by adding a set of hashed containers and related algorithms to C++.

Charlie has over a decade of experience in website administration and technology management. As the site admin, he oversees all technical aspects of running a high-traffic online platform, ensuring optimal performance, security, and user experience.

Disclosure

About Our Editorial Process

At DevX, we’re dedicated to tech entrepreneurship. Our team closely follows industry shifts, new products, AI breakthroughs, technology trends, and funding announcements. Articles undergo thorough editing to ensure accuracy and clarity, reflecting DevX’s style and supporting entrepreneurs in the tech sphere.

See our full editorial policy.

Show More