Login | Register   
RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Use the <map> Library to Create Associative Containers-2 : Page 2

It's easy to associate values with an index when the index is an int, but what if you need to associate pairings of data of different types? The <map> library has an associative container that will come in handy in pairings of all data types. See how it works.


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 <map>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>
map <string, string> addresses;

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

addresses["Paul W."]="paul@mail.com";

Here, the string Paul W. serves as the index or key, and paul@mail.comis its associated value. If the map already contains this key, the current associated value is replaced with the new associated value:

addresses["Paul W."]=
 "newaddr@com.net"; //overrides "paul@mail.com"

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 <string, string>::const_iterator CIT;

CIT cit=addresses.find("Paul W.");
if (cit==addresses.end())
  cout << "sorry, no such key" << endl;
 cout << cit->first << '\t' << 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<iterator, bool> map::insert(const value_type& x);
// the bool part reports whether the insertion succeeded

if (addresses.insert(make_pair("Paul W.", "newaddr@com.net")).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 35
Bob 90
Jane 80.25
Sue 100
Jane 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 <string, double> bonuses;
string agent;
double bonus=0;
ifstream bonusfile("bonuses.dat");
 //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


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


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 <<'\t' << p->second <<endl;
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++.

Danny Kalev is a certified system analyst and software engineer specializing in C++. He was a member of the C++ standards committee between 1997 and 2000 and has since been involved informally in the C++0x standardization process. He is the author of "The ANSI/ISO Professional C++ Programmer's Handbook" and "The Informit C++ Reference Guide: Techniques, Insight, and Practical Advice on C++."
Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.