The multiset ordered associative container (from header <set>) provides fast storage and retrieval of keys and allows duplicate keys. The elements’ ordering is determined by a so-called 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 16.5. For this chapter, we’ll simply show how to use less<int> when declaring ordered associative containers. The data type of the keys in all ordered associative containers must support comparison based on the comparator function object—keys sorted with less<T> must support comparison with operator<. If the keys used in the ordered 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). If the order of the keys is not important, use unordered_multiset (header <unordered_set>).

Figure 15.15 demonstrates the multiset ordered associative container for a multiset of ints with keys that are sorted in ascending order. Containers multiset and set (Section 15.6.2) provide the same basic functionality.

multiset<int> intMultiset; // multiset of ints

multiset<int, less<int>>

The set associative container (from header <set>) 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—this is the intended mathematical behavior of a set, so it’s not considered an error. A set supports bidirectional iterators (but not random-access iterators). If the order of the keys is not important, you can use unordered_set (header <unordered_set>) instead. Figure 15.16 demonstrates a set of doubles.

Line 12 creates a set of doubles ordered in ascending order, using the function object less<double>. The constructor call takes all the elements in vector a and inserts them into the set. Line 16 uses algorithm copy to output the contents of the set. Notice that the value 2.1—which appeared twice in the vector a—appears only once in doubleSet, because container set does not allow duplicates.

Line 21 defines and initializes a pair to store the result of a call to set function insert. The pair returned consists of a const_iterator pointing to the item in the set inserted and a bool value indicating whether the item was inserted—true if the item was not in the set; false if it was.

Line 21 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’s true because the value was inserted. Line 28 attempts to insert 9.5, which is already in the set. The output shows that 9.5 was not inserted again because sets don’t allow duplicate keys. In this case, p.first in the returned pair points to the existing 9.5 in the set.

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 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 15.17 demonstrates the multimap associative container. Header <map> must be included to use class multimap. If the order of the keys is not important, you can use unordered_multimap (header <unordered_map>) instead.

Line 8 creates a multimap 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—the template argument less<int> is the default ordering it’s not required in the multimap declaration. Line 10 uses function count to determine the number of key–value pairs with a key of 15 (none yet, since the container is currently empty).

Line 14 uses function insert to add a new key–value pair to the multimap. The Standard Library function make_pair creates a key–value pair object—in this case first represents a key (15) of type int and second represents a value (99.3) of type double. Function make_pair automatically uses the types that you specified for the keys and values in the multimap’s declaration (line 8). Line 15 inserts another pair object with the key 15 and the value 2.7. Then lines 17–18 output the number of pairs with key 15. As of C++11, you can use list initalization for pair objects, so line 15 can be simplified as

pairs.insert({15, 2.7};

Similarly, you can use C++11 list initialization to initialize an object being returned from a function. For example, the following returns a pair containing an int and a double

return {15, 2.7};

Lines 21–25 insert five additional pairs into the multimap. The range-based for statement in lines 30–32 outputs the contents of the multimap, including both keys and values. We infer the type of the loop’s control variable (a pair containing an int key and a double value) with keyword auto. Line 31 accesses the members of the current pair in each element of the multimap. Notice in the output that the keys appear in ascending order.

multimap<int, double, less<int>> pairs{
   {10, 22.22}, {20, 9.345}, {5, 77.54}};

The map associative container (from header <map>) performs fast storage and retrieval of unique keys and associated values. Duplicate keys are not allowed—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 extensions—4321, 4115 and 5217, respectively. With a map you specify the key and get back the associated data quickly. 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. If the order of the keys is not important, you can use unordered_map (header <unordered_map>) instead.

Figure 15.18 demonstrates a map (created at line 8) and uses the same features as Fig. 15.17 to demonstrate the subscript operator. Lines 27–28 use the subscript operator of class map. When the subscript is a key that’s already in the map (line 27), the operator returns a reference to the associated value. When the subscript is a key that’s not in the map (line 28), the operator inserts the key in the map and returns a reference that can be used to associate a value with that key. Line 27 replaces the value for the key 25 (previously 33.333 as specified in line 15) with a new value, 9999.99. Line 28 inserts a new key–value pair in the map (called creating an association). Note this example’s map, could have been initialized with an initializer list of pairs, as we showed for a multimap in Section 15.6.3.