Associative Containers

The STL's associative containers provide direct access to store and retrieve elements via keys (often called search keys). The four associative containers are multiset, set, multimap and map. Each associative container maintains its keys in sorted order. Iterating through an associative container traverses it in the sort order for that container. Classes multiset and set provide operations for manipulating sets of values where the values are the keysthere is not a separate value associated with each key. The primary difference between a multiset and a set is that a multiset allows duplicate keys and a set does not. Classes multimap and map provide operations for manipulating values associated with keys (these values are sometimes referred to as mapped values). The primary difference between a multimap and a map is that a multimap allows duplicate keys with associated values to be stored and a map allows only unique keys with associated values. In addition to the common member functions of all containers presented in Fig. 23.2, all associative containers also support several other member functions of all containers presented in Fig. 23.2, all associative containers also support several other member functions, including find, lower_bound, upper_bound and count. Examples of each of the associative containers and the common associative container member functions are presented in the next several subsections.

---

23.3.1. multiset Associative Container

The multiset associative container provides fast storage and retrieval of keys and allows duplicate keys. The ordering of the elements is determined by a comparator function object. For example, in an integer multiset, elements can be sorted in ascending order by ordering the keys with comparator function object less< int >. We discuss function objects in detail in Section 23.7. The data type of the keys in all associative containers must support comparison properly based on the comparator function object specifiedkeys sorted with less< T > must support comparison with operator<. If the keys used in the associative containers are of user-defined data types, those types must supply the appropriate comparison operators. A multiset supports bidirectional iterators (but not random-access iterators).

Figure 23.19 demonstrates the multiset associative container for a multiset of integers sorted in ascending order. Header file must be included to use class multiset. Containers multiset and set provide the same member functions.

Figure 23.19. Standard Library multiset class template.

(This item is displayed on pages 1139 - 1141 in the print version)

 1 // Fig. 23.19: Fig23_19.cpp
 2 // Testing Standard Library class multiset
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include  // multiset class-template definition
 8
 9 // define short name for multiset type used in this program
10 typedef std::multiset< int, std::less< int > > Ims; 
11
12 #include  // copy algorithm
13 #include  // ostream_iterator
14
15 int main()
16 {
17 const int SIZE = 10;
18 int a[ SIZE ] = { 7, 22, 9, 1, 18, 30, 100, 22, 85, 13 };
19 Ims intMultiset; // Ims is typedef for "integer multiset"
20 std::ostream_iterator< int > output( cout, " " );
21
22 cout << "There are currently " << intMultiset.count( 15 )
23 << " values of 15 in the multiset
";
24
25 intMultiset.insert( 15 ); // insert 15 in intMultiset
26 intMultiset.insert( 15 ); // insert 15 in intMultiset
27 cout << "After inserts, there are " << intMultiset.count( 15 )
28 << " values of 15 in the multiset

";
29
30 // iterator that cannot be used to change element values
31 Ims::const_iterator result;
32
33 // find 15 in intMultiset; find returns iterator
34 result = intMultiset.find( 15 ); 
35
36 if ( result != intMultiset.end() ) // if iterator not at end
37 cout << "Found value 15
"; // found search value 15
38
39 // find 20 in intMultiset; find returns iterator
40 result = intMultiset.find( 20 ); 
41
42 if ( result == intMultiset.end() ) // will be true hence
43 cout << "Did not find value 20
"; // did not find 20
44
45 // insert elements of array a into intMultiset
46 intMultiset.insert( a, a + SIZE ); 
47 cout << "
After insert, intMultiset contains:
";
48 std::copy( intMultiset.begin(), intMultiset.end(), output );
49
50 // determine lower and upper bound of 22 in intMultiset
51 cout << "

Lower bound of 22: "
52 << *( intMultiset.lower_bound( 22 ) );
53 cout << "
Upper bound of 22: " << *( intMultiset.upper_bound( 22 ) );
54
55 // p represents pair of const_iterators 
56 std::pair< Ims::const_iterator, Ims::const_iterator > p;
57
58 // use equal_range to determine lower and upper bound
59 // of 22 in intMultiset 
60 p = intMultiset.equal_range( 22 ); 
61
62 cout << "

equal_range of 22:" << "
 Lower bound: "
63 << *( p.first ) << "
 Upper bound: " << *( p.second );
64 cout << endl;
65 return 0;
66 } // end main

 

 There are currently 0 values of 15 in the multiset
 After inserts, there are 2 values of 15 in the multiset

 Found value 15
 Did not find value 20

 After insert, intMultiset contains:
 1 7 9 13 15 15 18 22 22 30 85 100

 Lower bound of 22: 22
 Upper bound of 22: 30

 equal_range of 22:
 Lower bound: 22
 Upper bound: 30

 

Line 10 uses a typedef to create a new type name (alias) for a multiset of integers ordered in ascending order, using the function object less< int >. Ascending order is the default for a multiset, so std::less< int > can be omitted in line 10. This new type (Ims) is then used to instantiate an integer multiset object, intMultiset (line 19).

Good Programming Practice 23.1

Use typedefs to make code with long type names (such as multisets) easier to read.

The output statement at line 22 uses function count (available to all associative containers) to count the number of occurrences of the value 15 currently in the multiset.

---

Lines 2526 use one of the three versions of function insert to add the value 15 to the multiset twice. A second version of insert takes an iterator and a value as arguments and begins the search for the insertion point from the iterator position specified. A third version of insert takes two iterators as arguments that specify a range of values to add to the multiset from another container.

Line 34 uses function find (available to all associative containers) to locate the value 15 in the multiset. Function find returns an iterator or a const_iterator pointing to the earliest location at which the value is found. If the value is not found, find returns an iterator or a const_iterator equal to the value returned by a call to end. Line 41 demonstrates this case.

Line 46 uses function insert to insert the elements of array a into the multiset. At line 48, the copy algorithm copies the elements of the multiset to the standard output. Note that the elements are displayed in ascending order.

Lines 52 and 53 use functions lower_bound and upper_bound (available in all associative containers) to locate the earliest occurrence of the value 22 in the multiset and the element after the last occurrence of the value 22 in the multiset. Both functions return iterators or const_iterators pointing to the appropriate location or the iterator returned by end if the value is not in the multiset.

Line 56 instantiates an instance of class pair called p. Objects of class pair are used to associate pairs of values. In this example, the contents of a pair are two const_iterators for our integer-based multiset. The purpose of p is to store the return value of multiset function equal_range that returns a pair containing the results of both a lower_bound and an upper_bound operation. Type pair contains two public data members called first and second.

Line 60 uses function equal_range to determine the lower_bound and upper_bound of 22 in the multiset. Line 63 uses p.first and p.second, respectively, to access the lower_bound and upper_bound. We dereferenced the iterators to output the values at the locations returned from equal_range.

---

23.3.2. set Associative Container

The set associative container is used for fast storage and retrieval of unique keys. The implementation of a set is identical to that of a multiset, except that a set must have unique keys. Therefore, if an attempt is made to insert a duplicate key into a set, the duplicate is ignored; because this is the intended mathematical behavior of a set, we do not identify it as a common programming error. A set supports bidirectional iterators (but not random-access iterators). Figure 23.20 demonstrates a set of doubles. Header file must be included to use class set.

Figure 23.20. Standard Library set class template.

(This item is displayed on pages 1142 - 1143 in the print version)

 1 // Fig. 23.20: Fig23_20.cpp
 2 // Standard Library class set test program.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include 
 8
 9 // define short name for set type used in this program
10 typedef std::set< double, std::less< double > > DoubleSet;
11
12 #include 
13 #include  // ostream_iterator
14
15 int main()
16 {
17 const int SIZE = 5;
18 double a[ SIZE ] = { 2.1, 4.2, 9.5, 2.1, 3.7 };
19 DoubleSet doubleSet( a, a + SIZE );
20 std::ostream_iterator< double > output( cout, " " );
21
22 cout << "doubleSet contains: ";
23 std::copy( doubleSet.begin(), doubleSet.end(), output );
24
25 // p represents pair containing const_iterator and bool
26 std::pair< DoubleSet::const_iterator, bool > p; 
27
28 // insert 13.8 in doubleSet; insert returns pair in which
29 // p.first represents location of 13.8 in doubleSet and 
30 // p.second represents whether 13.8 was inserted 
31 p = doubleSet.insert( 13.8 ); // value not in set 
32 cout << "

" << *( p.first )
33 << ( p.second ? " was" : " was not" ) << " inserted";
34 cout << "
doubleSet contains: ";
35 std::copy( doubleSet.begin(), doubleSet.end(), output );
36
37 // insert 9.5 in doubleSet 
38 p = doubleSet.insert( 9.5 ); // value already in set
39 cout << "

" << *( p.first )
40 << ( p.second ? " was" : " was not" ) << " inserted";
41 cout << "
doubleSet contains: ";
42 std::copy( doubleSet.begin(), doubleSet.end(), output );
43 cout << endl;
44 return 0;
45 } // end main

 

 doubleSet contains: 2.1 3.7 4.2 9.5

 13.8 was inserted
 doubleSet contains: 2.1 3.7 4.2 9.5 13.8

 9.5 was not inserted
 doubleSet contains: 2.1 3.7 4.2 9.5 13.8

 

---

Line 10 uses typedef to create a new type name (DoubleSet) for a set of double values ordered in ascending order, using the function object less< double >.

Line 19 uses the new type DoubleSet to instantiate object doubleSet. The constructor call takes the elements in array a between a and a + SIZE (i.e., the entire array) and inserts them into the set. Line 23 uses algorithm copy to output the contents of the set. Notice that the value 2.1which appeared twice in array aappears only once in doubleSet. This is because container set does not allow duplicates.

Line 26 defines a pair consisting of a const_iterator for a DoubleSet and a bool value. This object stores the result of a call to set function insert.

Line 31 uses function insert to place the value 13.8 in the set. The returned pair, p, contains an iterator p.first pointing to the value 13.8 in the set and a bool value that is true if the value was inserted and false if the value was not inserted (because it was already in the set). In this case, 13.8 was not in the set, so it was inserted. Line 38 attempts to insert 9.5, which is already in the set. The output of lines 3940 shows that 9.5 was not inserted.

23.3.3. multimap Associative Container

The multimap associative container is used for fast storage and retrieval of keys and associated values (often called key/value pairs). Many of the functions used with multisets and sets are also used with multimaps and maps. The elements of multimaps and maps are pairs of keys and values instead of individual values. When inserting into a multimap or map, a pair object that contains the key and the value is used. The ordering of the keys is determined by a comparator function object. For example, in a multimap that uses integers as the key type, keys can be sorted in ascending order by ordering them with comparator function object less< int >. Duplicate keys are allowed in a multimap, so multiple values can be associated with a single key. This is often called a one-to-many relationship. For example, in a credit-card transaction-processing system, one credit-card account can have many associated transactions; in a university, one student can take many courses, and one professor can teach many students; in the military, one rank (like "private") has many people. A multimap supports bidirectional iterators, but not random-access iterators. Figure 23.21 demonstrates the multimap associative container. Header file must be included to use class multimap.

Figure 23.21. Standard Library multimap class template.

(This item is displayed on pages 1144 - 1145 in the print version)

 1 // Fig. 23.21: Fig23_21.cpp
 2 // Standard Library class multimap test program.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include // map class-template definition
 8
 9 // define short name for multimap type used in this program 
10 typedef std::multimap< int, double, std::less< int > > Mmid;
11
12 int main()
13 {
14 Mmid pairs; // declare the multimap pairs
15
16 cout << "There are currently " << pairs.count( 15 )
17 << " pairs with key 15 in the multimap
";
18
19 // insert two value_type objects in pairs 
20 pairs.insert( Mmid::value_type( 15, 2.7 ) ); 
21 pairs.insert( Mmid::value_type( 15, 99.3 ) );
22
23 cout << "After inserts, there are " << pairs.count( 15 )
24 << " pairs with key 15

";
25
26 // insert five value_type objects in pairs 
27 pairs.insert( Mmid::value_type( 30, 111.11 ) );
28 pairs.insert( Mmid::value_type( 10, 22.22 ) ); 
29 pairs.insert( Mmid::value_type( 25, 33.333 ) );
30 pairs.insert( Mmid::value_type( 20, 9.345 ) ); 
31 pairs.insert( Mmid::value_type( 5, 77.54 ) ); 
32
33 cout << "Multimap pairs contains:
Key	Value
";
34
35 // use const_iterator to walk through elements of pairs
36 for ( Mmid::const_iterator iter = pairs.begin(); 
37  iter != pairs.end(); ++iter ) 
38  cout << iter->first << '	' << iter->second << '
';
39
40 cout << endl;
41 return 0;
42 } // end main

 

 There are currently 0 pairs with key 15 in the multimap
 After inserts, there are 2 pairs with key 15

 Multimap pairs contains:
 Key Value
 5 77.54
 10 22.22
 15 2.7
 15 99.3
 20 9.345
 25 33.333
 30 111.11

 

---

Performance Tip 23.15

A multimap is implemented to efficiently locate all values paired with a given key.

Line 10 uses typedef to define alias Mmid for a multimap type in which the key type is int, the type of a key's associated value is double and the elements are ordered in ascending order. Line 14 uses the new type to instantiate a multimap called pairs. Line 16 uses function count to determine the number of key/value pairs with a key of 15.

---

Line 20 uses function insert to add a new key/value pair to the multimap. The expression Mmid::value_type ( 15, 2.7 ) creates a pair object in which first is the key (15) of type int and second is the value (2.7) of type double. The type Mmid::value_type is defined as part of the typedef for the multimap. Line 21 inserts another pair object with the key 15 and the value 99.3. Then lines 2324 output the number of pairs with key 15.

Lines 2731 insert five additional pairs into the multimap. The for statement at lines 3638 outputs the contents of the multimap, including both keys and values. Line 38 uses the const_iterator called iter to access the members of the pair in each element of the multimap. Notice in the output that the keys appear in ascending order.

23.3.4. map Associative Container

The map associative container is used for fast storage and retrieval of unique keys and associated values. Duplicate keys are not allowed in a map, so only a single value can be associated with each key. This is called a one-to-one mapping. For example, a company that uses unique employee numbers, such as 100, 200 and 300, might have a map that associates employee numbers with their telephone extensions4321, 4115 and 5217, respectively. With a map you specify the key and get back the associated data quickly. A map is commonly called an associative array. Providing the key in a map's subscript operator [] locates the value associated with that key in the map. Insertions and deletions can be made anywhere in a map.

Figure 23.22 demonstrates the map associative container and uses the same features as Fig. 23.21 to demonstrate the subscript operator. Header file must be included to use class map. Lines 33 and 34 use the subscript operator of class map. When the subscript is a key that is already in the map (line 33), the operator returns a reference to the associated value. When the subscript is a key that is not in the map (line 34), the operator inserts the key in the map and returns a reference that can be used to associate a value with that key. Line 33 replaces the value for the key 25 (previously 33.333 as specified in line 21) with a new value, 9999.99. Line 34 inserts a new key/value pair in the map (called creating an association).

---

Figure 23.22. Standard Library map class template.

(This item is displayed on pages 1145 - 1146 in the print version)

 1 // Fig. 23.22: Fig23_22.cpp
 2 // Standard Library class map test program.
 3 #include 
 4 using std::cout;
 5 using std::endl;
 6
 7 #include // map class-template definition
 8
 9 // define short name for map type used in this program
10 typedef std::map< int, double, std::less< int > > Mid;
11
12 int main()
13 {
14 Mid pairs;
15
16 // insert eight value_type objects in pairs 
17 pairs.insert( Mid::value_type( 15, 2.7 ) ); 
18 pairs.insert( Mid::value_type( 30, 111.11 ) ); 
19 pairs.insert( Mid::value_type( 5, 1010.1 ) ); 
20 pairs.insert( Mid::value_type( 10, 22.22 ) ); 
21 pairs.insert( Mid::value_type( 25, 33.333 ) ); 
22 pairs.insert( Mid::value_type( 5, 77.54 ) ); // dup ignored
23 pairs.insert( Mid::value_type( 20, 9.345 ) ); 
24 pairs.insert( Mid::value_type( 15, 99.3 ) ); // dup ignored
25
26 cout << "pairs contains:
Key	Value
";
27
28 // use const_iterator to walk through elements of pairs
29 for ( Mid::const_iterator iter = pairs.begin(); 
30  iter != pairs.end(); ++iter ) 
31  cout << iter->first << '	' << iter->second << '
';
32
33 pairs[ 25 ] = 9999.99; // use subscripting to change value for key 25
34 pairs[ 40 ] = 8765.43; // use subscripting to insert value for key 40
35
36 cout << "
After subscript operations, pairs contains:
Key	Value
";
37
38 // use const_iterator to walk through elements of pairs
39 for ( Mid::const_iterator iter2 = pairs.begin();
40 iter2 != pairs.end(); ++iter2 )
41 cout << iter2->first << '	' << iter2->second << '
';
42
43 cout << endl;
44 return 0;
45 } // end main

 

 pairs contains:
 Key Value
 5 1010.1
 10 22.22
 15 2.7
 20 9.345
 25 33.333
 30 111.11

 After subscript operations, pairs contains:
 Key Value
 5 1010.1
 10 22.22
 15 2.7
 20 9.345
 25 9999.99
 30 111.11
 40 8765.43