The associative containers provide direct access to store and retrieve elements via keys (often called search keys). The four ordered associative containers are multiset
, set
, multimap
and map
. Each of these maintains its keys in sorted order. There are also four corresponding unordered associative containers—unordered_multiset
, unordered_set
, unordered_multimap
and unordered_map
—that offer the most of the same capabilities as their ordered counterparts. The primary difference between the ordered and unordered associative containers is that the unordered ones do not maintain their keys in sorted order. In this section, we focus on the ordered associative containers.
The unordered associative containers might offer better performance for cases in which it’s not necessary to maintain keys in sorted order.
Iterating through an ordered 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 themselves are the keys. 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 container member functions, ordered associative containers also support several member functions that are specific to associative containers. Examples of each of the ordered associative containers and their common member functions are presented in the next several subsections.
multiset
Associative ContainerThe 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 int
s with keys that are sorted in ascending order. Containers multiset
and set
(Section 15.6.2) provide the same basic functionality.
multiset
Line 11 creates a multiset
of int
s ordered in ascending order, using the function object less<int>
. Ascending order is the default for a multiset
, so less<int>
can be omitted and line 11 can be written as
multiset<int> intMultiset; // multiset of ints
C++11 fixed a syntax issue with spacing between the closing >
of less<int>
and the closing >
of the multiset
type. Before C++11, if you specified this multiset
’s type as we did in line 11, the compiler would treat the >>
in
multiset<int, less<int>>
as the >>
operator and generate a compilation error. For this reason, you were required to put a space between the closing >
of less<int>
and the closing >
of the multiset
type (or any other similar template type, such as vector<vector<int>>
). As of C++11, the preceding declaration compiles correctly.
multiset
Member Function count
Line 13 uses function count
(available to all associative containers) to count the number of occurrences of the value 15
currently in the multiset
.
multiset
Member Function insert
Lines 16–17 use one of the several overloaded 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.
multiset
Member Function find
Line 22 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
(depending on whether the multiset
is const
) pointing to the 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 calling end
on the container. Line 31 demonstrates this case.
multiset
Line 37 uses function insert
to insert the elements of the vector
named a
into the multiset
. In line 40, the copy
algorithm copies the elements of the multiset
to the standard output in ascending order.
multiset
Member Functions lower_bound
and upper_bound
Lines 44 and 45 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 iterator
s or const_iterator
s pointing to the appropriate location or the iterator returned by end
if the value is not in the multiset
.
pair
Objects and multiset
Member Function equal_range
Line 49 creates and intializes a pair
object called p
. Once again, we use C++11’s auto
keyword to infer the variable’s type from its initializer—in this case, the return value of multiset
member function equal_range
, which is a pair
object. Such objects associate pairs of values. The contents of p
will be two const_iterator
s for our multiset
of int
s. The multiset
function equal_range
returns a pair
containing the results of calling both lower_bound
and upper_bound
. Type pair
contains two public
data members called first
and second
. Line 49 uses function equal_range
to determine the lower_bound
and upper_bound
of 22
in the multiset
. Line 52 uses p.first
and p.second
to access the lower_bound
and upper_bound
. We dereferenced the iterators to output the values at the locations returned from equal_range
. Though we did not do so here, you should always ensure that the iterators returned by lower_bound
, upper_bound
and equal_range
are not equal to the container’s end iterator before dereferencing the iterators.
tuple
C++ also includes class template tuple
, which is similar to pair
, but can hold any number of items of various types. As of C++11, class template tuple
is implemented using variadic templates—templates that can receive a variable number of arguments. We discuss tuple
and variadic templates in Chapter 24, C++11 and C++14 Additional Features.
Prior to C++14, when searching for a key in an associative container, the argument provided to a search function like find
was required to have the container’s key type. For example, if the key type were string
, you could pass find
a pointer-based string to locate in the container. In this case, the argument would be converted into a temporary object of the key type (string
), then passed to find
. As of C++14, the argument to find
(and other similar functions) can be of any type, provided that there are overloaded comparison operators that can compare values of the argument’s type to values of the container’s key type. If there are, no temporary objects will be created. This is known as heterogeneous lookup.
set
Associative ContainerThe 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 double
s.
Line 12 creates a set
of double
s 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 set
s don’t allow duplicate keys. In this case, p.first
in the returned pair
points to the existing 9.5
in the set
.
multimap
Associative ContainerThe 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 multiset
s and set
s are also used with multimap
s and map
s. The elements of multimap
s and map
s are pair
s 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.
A multimap
is implemented to efficiently locate all values paired with a given key.
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 pair
s 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.
In this example, we used separate calls to member function insert to place key–value pairs in a multimap
. If you know the key–value pairs in advance, you can use list initialization when you create the multimap
. For example, the following statement initializes a multimap
with three key–value pairs that are represented by the sublists in the main intializer list:
multimap<int, double, less<int>> pairs{
{10, 22.22}, {20, 9.345}, {5, 77.54}};
map
Associative ContainerThe 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 pair
s, as we showed for a multimap
in Section 15.6.3.