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:
map <string, string> addresses;
To add an item to a map, use the subscript operator.
Here, the string Paul W. serves as the index or key, and firstname.lastname@example.org its associated value. If the map already contains this key, the current associated value is replaced with the new associated value:
"email@example.com"; //overrides "firstname.lastname@example.org"
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.");
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.", "email@example.com")).second
// 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:
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;
//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++.