C++ Reference Guide

< Back Page 222 of 530 Next >

Choosing the Right Container, Part III

Last updated Jan 1, 2003.

This last section of the container series is dedicated to the associative containers: map, multimap, set and multiset. Here, I will show how to create and use such containers and discuss their applications.

Fundamentals of Associative Containers

Sequence containers can store any date type. However, they offer only two retrieval methods: subscripting and searching. If the container doesn't support subscripting (list, for example), the only way to retrieve an element is to perform a search.

Associative containers, on the other hand, store pairs of objects, where one element serves as the key and the other as the associated value. You access the associated value by using its key.

What are the applications of such containers? Think of a symbolic debugger. It can use an associative container that maps strings (variable names) to memory addresses (the variables' addresses). This way, when you evaluate or modify a variable by its name, the debugger knows where that variable is stored in memory. Another example is a phone book, in which names serve as keys, and telephone numbers are their associated values.

Unique Keys versus non-Unique Keys

In certain associative containers, the keys must be unique. Thus, if you want to store several telephone numbers of the same person (where the person's name serves as the key), you cannot use such a container. Instead, use a multi-key associative container.

Pairs

The concept of a pair is essential for understanding how associative containers work. A pair binds a key (known as the first element) with an associated value (known as the second element). The Standard Library defines a pair template which behaves like a special tuple of two elements:

#include <utility> //definition of pair
#include <string>
pair <string, string> don_and_course("Horvath", "syntax101");
pair <string, void *> symbol ("mynum", 0x410928a8);

NOTE

Historically, pair dates back to C++98, whereas tuple was added later to C++0x as a generalization of the pair concept.

`map`

Just as vector serves as the default sequence container, map is the default associative container. The class template map defined in <map> is an associative container that uses a pair of types. The first is the index, or key, and the second is the associated value.

Let's look at a concrete example of a map that contains a pair of strings, the first of which is a name and the second one is an e-mail address. We create the map like this:

#include <map>
#include <string>

map <string, string> emails;

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

emails["J. Horvath"]="jhorvath@mail.com";

If the map already contains the key "J. Horvath", the current associated value remains unchanged:

emails ["J. Horvath "]="newaddr@com.net"; //has no effect

The subscript operator is used both for accessing an existing value and for inserting a new value. To examine whether a certain value exists without inserting it to the map, use the find() algorithm. find() has two overloaded versions:

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

The following code sample searches for the key "J. Horvath" in the map:

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

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

`multimap`

A multimap is like a map except that it allows duplicate key. Because multimap keys aren't necessarily unique, it doesn't support the subscript notation. To insert an element to a multimap, use the insert() member function. insert() takes as an argument a pair type. The Standard Library defines the helper function make_pair() that takes two arguments: a and b, and returns pair <x,y> where x is the type of a and y is the type of b. The following example inserts two pairs with the same key to a multimap:

multimap <string, string> emails;
emails.insert(make_pair("J. Horvath","jhorvath@mail.com"));
//duplicate keys allowed:
emails.insert(make_pair("J. Horvath","newaddr@com.net"));

Searching a `multimap`

Instead of find(), the equal_range(), lower_bound(), and upper_bound() operations are used for accessing multiple values with the same key. equal_range(k) finds all of the values with the key k. It returns a pair of iterators that mark the first and last elements in the range. The following example display all values whose key is "J. Horvath":

typedef multimap<string, string>::const_iterator CIT;
pair<CIT, CIT> range=emails.equal_range("J. Horvath");
for(CIT i=range.first; i!= range.second; ++i)
 cout<<i->second<<endl;

lower_bound(k) finds the first value whose key is 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 "J. Horvath" (when the key is a string, a lexicographical comparison is performed):

emails.insert(make_pair("M. Jones","majones@com.net"));
CIT it=emails.upper_bound("J. Horvath");
if (it!=emails.end())
 cout<<it->second<<endl; //display "majones@com.net"

`set`

The set container is similar to map, except that it stores only keys. There are many applications for this type of a container. Think, for example, of a Web browser that stores favorite URLs as keys to Web pages. The browser needs to store only the keys; their associated values are stored remote servers. Relational databases are another example. A database engine often performs optimizations with respect to how keys are organized, such as sorting indexing them. In such cases, the values (the records to which the keys point) are irrelevant.

Obviously, set doesn't support the subscript operator because the associated value isn't stored in it.

`multiset`

A multiset is a set that allows duplicate keys. Here again, the primary means of retrieving elements is by calling the member functions equal_range(), lower_bound() and upper_bound().

Summary

The Standard Library Technical Report (TR1) defines a new category of generic containers known as hashed containers, or in their official name: Unordered Associative Containers. The Unordered Associative Containers are: unordered_set, unordered_map, unordered_multiset, and unordered_multimap. They are declared in new headers: <unordered_set>, <unordered_map>, <unordered_multiset>, and <unordered_multimap>, respectively. I will discuss these containers in another article.