Associative Containers
An associative container is another refinement of the container concept. An associative container associates a value with a key and uses the key to find the value. For example, the values could be structures representing employee information, such as name, address, office number, home and work phones, health plan, and so on, and the key could be a unique employee number. To fetch the employee information, a program would use the key to locate the employee structure. Recall that for a container X, in general, the expression X::value_type indicates the type of value stored in the container. For an associative container, the expression X::key_type indicates the type used for the key.
The strength of an associative container is that it provides rapid access to its elements. Like a sequence, an associative container allows you to insert new elements; however, you can’t specify a particular location for the inserted elements. The reason is that an associative container usually has a particular algorithm for determining where to place data so that it can retrieve information quickly.
Associative containers typically are implemented using some form of tree. A tree is a data structure in which a root node is linked to one or two other nodes, each of which is linked to one or two nodes, thus forming a branching structure. The node aspect makes it relatively simple to add or remove a new data item, much as with a linked list. But compared to a list, a tree offers much faster search times.
The STL provides four associative containers: set, multiset, map, and multimap. The first two types are defined in the set header file (formerly separately in set.h and multiset.h), and the second two types are defined in the map header file (formerly separately in map.h and multimap.h).
The simplest of the bunch is set; the value type is the same as the key type, and the keys are unique, meaning there is no more than one instance of a key in a set. Indeed, for set, the value is the key. The multiset type is like the set type except that it can have more than one value with the same key. For example, if the key and value type are int, a multiset object could hold, say 1, 2, 2, 2, 3, 5, 7, and 7.
For the map type, the value type is different from the key type, and the keys are unique, with only one value per key. The multimap type is similar to map, except one key can be associated with multiple values.
There’s too much information about these types to cover in this chapter (but Appendix G does list the methods), so let’s just look at a simple example that uses set and a simple example that uses multimap.
A set Example
The STL set models several concepts. It is an associative set, it is reversible, it is sorted, and the keys are unique, so it can hold no more than one of any given value. Like vector and list, set uses a template parameter to provide the type stored:
set<string> A; // a set of string objects
An optional second template argument can be used to indicate a comparison function or object to be used to order the key. By default, the less<> template (discussed later) is used. Older C++ implementations may not provide a default value and thus require an explicit template parameter:
set<string, less<string> > A; // older implementation
const int N = 6;
string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};
set<string> A(s1, s1 + N); // initialize set A using a range from array
ostream_iterator<string, char> out(cout, " ");
copy(A.begin(), A.end(), out);
Like other containers, set has a constructor (refer to Table 16.6) that takes a range of iterators as arguments. This provides a simple way to initialize a set to the contents of an array. Remember that the last element of a range is one past-the-end, and s1 + N points to one position past-the-end of array s1. The output for this code fragment illustrates that keys are unique (the string "for" appears twice in the array but once in the set) and that the set is sorted:
buffoon can for heavy thinkers
Mathematics defines some standard operations for sets. For example, the union of two sets is a set that combines the contents of the two sets. If a particular value is common to both sets, it appears just once in the union because of the unique key feature. The intersection of two sets is a set that consists of the elements that are common to both sets. The difference between two sets is the first set minus the elements common to both sets.
The STL provides algorithms that support these operations. They are general functions rather than methods, so they aren’t restricted to set objects. However, all set objects automatically satisfy the precondition for using these algorithms—namely, that the container be sorted. The set_union() function takes five iterators as arguments. The first two define a range in one set, the second two define a range in a second set, and the final iterator is an output iterator that identifies a location to which to copy the resultant set. For example, to display the union of sets A and B, you can use this:
set_union(A.begin(), A.end(), B.begin(), B.end(),
ostream_iterator<string, char> out(cout, " "));
Suppose you want to place the result into a set C instead of displaying it. In this case, you would want the last argument to be an iterator into C. The obvious choice is C.begin(), but that doesn’t work for two reasons. The first reason is that associative sets treat keys as constant values, so the iterator returned by C.begin() is a constant iterator and can’t be used as an output iterator. The second reason not to use C.begin() directly is that set_union(), like copy(), overwrites existing data in a container and requires the container to have sufficient space to hold the new information. C, being empty, does not satisfy that requirement. But the insert_iterator template discussed earlier solves both problems. Earlier you saw that it converts copying to insertion. Also it models the output iterator concept, so you can use it to write to a container. So you can construct an anonymous insert_iterator to copy information to C. The constructor, recall, takes the name of the container and an iterator as arguments:
set_union(A.begin(), A.end(), B.begin(), B.end(),
insert_iterator<set<string> >(C, C.begin()));
The set_intersection() and set_difference() functions find the set intersection and set difference of two sets, and they have the same interface as set_union().
Two useful set methods are lower_bound() and upper_bound(). The lower_bound() method takes a key-type value as its argument and returns an iterator that points to the first member of the set that is not less than the key argument. Similarly, the upper_bound() method takes a key as its argument and returns an iterator that points to the first member of the set that is greater than the key argument. For example, if you had a set of strings, you could use these methods to identify a range encompassing all strings from "b" up to "f" in the set.
Because sorting determines where additions to a set go, the class has insertion methods that just specify the material to be inserted, without specifying a position. If A and B are sets of strings, for example, you can use this:
string s("tennis");
A.insert(s); // insert a value
B.insert(A.begin(), A.end()); // insert a range
Listing 16.13 illustrates these uses of sets.
// setops.cpp -- some set operations
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <iterator>
int main()
{
using namespace std;
const int N = 6;
string s1[N] = {"buffoon", "thinkers", "for", "heavy", "can", "for"};
string s2[N] = {"metal", "any", "food", "elegant", "deliver","for"};
set<string> A(s1, s1 + N);
set<string> B(s2, s2 + N);
ostream_iterator<string, char> out(cout, " ");
cout << "Set A: ";
copy(A.begin(), A.end(), out);
cout << endl;
cout << "Set B: ";
copy(B.begin(), B.end(), out);
cout << endl;
cout << "Union of A and B:
";
set_union(A.begin(), A.end(), B.begin(), B.end(), out);
cout << endl;
cout << "Intersection of A and B:
";
set_intersection(A.begin(), A.end(), B.begin(), B.end(), out);
cout << endl;
cout << "Difference of A and B:
";
set_difference(A.begin(), A.end(), B.begin(), B.end(), out);
cout << endl;
set<string> C;
cout << "Set C:
";
set_union(A.begin(), A.end(), B.begin(), B.end(),
insert_iterator<set<string> >(C, C.begin()));
copy(C.begin(), C.end(), out);
cout << endl;
string s3("grungy");
C.insert(s3);
cout << "Set C after insertion:
";
copy(C.begin(), C.end(),out);
cout << endl;
cout << "Showing a range:
";
copy(C.lower_bound("ghost"),C.upper_bound("spook"), out);
cout << endl;
return 0;
}
Here is the output of the program in Listing 16.13:
Set A: buffoon can for heavy thinkers
Set B: any deliver elegant food for metal
Union of A and B:
any buffoon can deliver elegant food for heavy metal thinkers
Intersection of A and B:
for
Difference of A and B:
buffoon can heavy thinkers
Set C:
any buffoon can deliver elegant food for heavy metal thinkers
Set C after insertion:
any buffoon can deliver elegant food for grungy heavy metal thinkers
Showing a range:
grungy heavy metal
Like most of the examples in this chapter, the code in Listing 16.13 takes the lazy route for handling the std namespace:
using namespace std;
It does so in order to simplify the presentation. The examples use so many elements of the std namespace that using directives or the scope-resolution operators would tend to make the code look a bit fussy:
std::set<std::string> B(s2, s2 + N);
std::ostream_iterator<std::string, char> out(std::cout, " ");
std::cout << "Set A: ";
std::copy(A.begin(), A.end(), out);
A multimap Example
Like set, multimap is a reversible, sorted, associative container. However, with multimap, the key type is different from the value type, and a multimap object can have more than one value associated with a particular key.
The basic multimap declaration specifies the key type and the type of value, stored as template arguments. For example, the following declaration creates a multimap object that uses int as the key type and string as the type of value stored:
multimap<int,string> codes;
An optional third template argument can be used to indicate a comparison function or an object to be used to order the key. By default, the less<> template (discussed later) is used with the key type as its parameter. Older C++ implementations may require this template parameter explicitly.
To keep information together, the actual value type combines the key type and the data type into a single pair. To do this, the STL uses a pair<class T, class U> template class for storing two kinds of values in a single object. If keytype is the key type and datatype is the type of the stored data, the value type is pair<const keytype, datatype>. For example, the value type for the codes object declared earlier is pair<const int, string>.
Suppose that you want to store city names, using the area code as a key. This happens to fit the codes declaration, which uses an int for a key and a string as a data type. One approach is to create a pair and then insert it into the multimap object:
pair<const int, string> item(213, "Los Angeles");
codes.insert(item);
Or you can create an anonymous pair object and insert it in a single statement:
codes.insert(pair<const int, string> (213, "Los Angeles"));
Because items are sorted by key, there’s no need to identify an insertion location.
Given a pair object, you can access the two components by using the first and second members:
pair<const int, string> item(213, "Los Angeles");
cout << item.first << ' ' << item.second << endl;
What about getting information about a multimap object? The count() member function takes a key as its argument and returns the number of items that have that key. The lower_bound() and upper_bound() member functions take a key and work as they do for set. Also the equal_range() member function takes a key as its argument and returns iterators representing the range matching that key. In order to return two values, the method packages them into a pair object, this time with both template arguments being the iterator type. For example, the following would print a list of cities in the codes object with area code 718:
pair<multimap<KeyType, string>::iterator,
multimap<KeyType, string>::iterator> range
= codes.equal_range(718);
cout << "Cities with area code 718:
";
std::multimap<KeyType, std::string>::iterator it;
for (it = range.first; it != range.second; ++it)
cout << (*it).second << endl;
Declarations like those just listed helped motivate the C++11 automatic type deduction feature, which allows you to simplify the code as follows:
auto range = codes.equal_range(718);
cout << "Cities with area code 718:
";
for (auto it = range.first; it != range.second; ++it)
cout << (*it).second << endl;
Listing 16.14 demonstrates most of these techniques. It also uses typedef to simplify some of the code writing.
// multmap.cpp -- use a multimap
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
typedef int KeyType;
typedef std::pair<const KeyType, std::string> Pair;
typedef std::multimap<KeyType, std::string> MapCode;
int main()
{
using namespace std;
MapCode codes;
codes.insert(Pair(415, "San Francisco"));
codes.insert(Pair(510, "Oakland"));
codes.insert(Pair(718, "Brooklyn"));
codes.insert(Pair(718, "Staten Island"));
codes.insert(Pair(415, "San Rafael"));
codes.insert(Pair(510, "Berkeley"));
cout << "Number of cities with area code 415: "
<< codes.count(415) << endl;
cout << "Number of cities with area code 718: "
<< codes.count(718) << endl;
cout << "Number of cities with area code 510: "
<< codes.count(510) << endl;
cout << "Area Code City
";
MapCode::iterator it;
for (it = codes.begin(); it != codes.end(); ++it)
cout << " " << (*it).first << " "
<< (*it).second << endl;
pair<MapCode::iterator, MapCode::iterator> range
= codes.equal_range(718);
cout << "Cities with area code 718:
";
for (it = range.first; it != range.second; ++it)
cout << (*it).second << endl;
return 0;
}
Here is the output of the program in Listing 16.14:
Number of cities with area code 415: 2
Number of cities with area code 718: 2
Number of cities with area code 510: 2
Area Code City
415 San Francisco
415 San Rafael
510 Oakland
510 Berkeley
718 Brooklyn
718 Staten Island
Cities with area code 718:
Brooklyn
Staten Island