C++ Primer, Fifth Edition

Appearance

11.2. Overview of the Associative Containers

Associative containers (both ordered and unordered) support the general container operations covered in § 9.2 (p. 328) and listed in Table 9.2 (p. 330). The associative containers do not support the sequential-container position-specific operations, such as push_front or back. Because the elements are stored based on their keys, these operations would be meaningless for the associative containers. Moreover, the associative containers do not support the constructors or insert operations that take an element value and a count.

In addition to the operations they share with the sequential containers, the associative containers provide some operations (Table 11.7 (p. 438)) and type aliases (Table 11.3 (p. 429)) that the sequential containers do not. In addition, the unordered containers provide operations for tuning their hash performance, which we’ll cover in § 11.4 (p. 444).

The associative container iterators are bidirectional (§ 10.5.1, p. 410).

11.2.1. Defining an Associative Container

Fundamental

As we’ve just seen, when we define a map, we must indicate both the key and value type; when we define a set, we specify only a key type, because there is no value type. Each of the associative containers defines a default constructor, which creates an empty container of the specified type. We can also initialize an associative container as a copy of another container of the same type or from a range of values, so long as those values can be converted to the type of the container. Under the new standard, we can also list initialize the elements:

C++11
c++
map<string, size_t> word_count;  // empty
// list initialization
set<string> exclude = {"the", "but", "and", "or", "an", "a",
                       "The", "But", "And", "Or", "An", "A"};
// three elements; authors maps last name to first
map<string, string> authors = { {"Joyce", "James"},
                                {"Austen", "Jane"},
                                {"Dickens", "Charles"} };

As usual, the initializers must be convertible to the type in the container. For set, the element type is the key type.

When we initialize a map, we have to supply both the key and the value. We wrap each key–value pair inside curly braces:

c++
{key, value}

to indicate that the items together form one element in the map. The key is the first element in each pair, and the value is the second. Thus, authors maps last names to first names, and is initialized with three elements.

Initializing a multimap or multiset

The keys in a map or a set must be unique; there can be only one element with a given key. The multimap and multiset containers have no such restriction; there can be several elements with the same key. For example, the map we used to count words must have only one element per given word. On the other hand, a dictionary could have several definitions associated with a particular word.

The following example illustrates the differences between the containers with unique keys and those that have multiple keys. First, we’ll create a vector of ints named ivec that has 20 elements: two copies of each of the integers from 0 through 9 inclusive. We’ll use that vector to initialize a set and a multiset:

c++
// define a vector with 20 elements, holding two copies of each number from 0 to 9
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
    ivec.push_back(i);
    ivec.push_back(i);  // duplicate copies of each number
}
// iset holds unique elements from ivec; miset holds all 20 elements
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl;    // prints 20
cout << iset.size() << endl;    // prints 10
cout << miset.size() << endl;   // prints 20

Even though we initialized iset from the entire ivec container, iset has only ten elements: one for each distinct element in ivec. On the other hand, miset has 20 elements, the same as the number of elements in ivec.

INFO

Exercises Section 11.2.1

Exercise 11.5: Explain the difference between a map and a set. When might you use one or the other?

Exercise 11.6: Explain the difference between a set and a list. When might you use one or the other?

Exercise 11.7: Define a map for which the key is the family’s last name and the value is a vector of the children’s names. Write code to add new families and to add new children to an existing family.

Exercise 11.8: Write a program that stores the excluded words in a vector instead of in a set. What are the advantages to using a set?

11.2.2. Requirements on Key Type

Fundamental

The associative containers place constraints on the type that is used as a key. We’ll cover the requirements for keys in the unordered containers in § 11.4 (p. 445). For the ordered containers—map, multimap, set, and multiset—the key type must define a way to compare the elements. By default, the library uses the < operator for the key type to compare the keys. In the set types, the key is the element type; in the map types, the key is the first type. Thus, the key type for word_count in § 11.1 (p. 421) is string. Similarly, the key type for exclude is string.

INFO

Callable objects passed to a sort algorithm (§ 10.3.1, p. 386) must meet the same requirements as do the keys in an associative container.

Key Types for Ordered Containers

Just as we can provide our own comparison operation to an algorithm (§ 10.3, p. 385), we can also supply our own operation to use in place of the < operator on keys. The specified operation must define a strict weak ordering over the key type. We can think of a strict weak ordering as “less than,” although our function might use a more complicated procedure. However we define it, the comparison function must have the following properties:

  • Two keys cannot both be “less than” each other; if k1 is “less than” k2, then k2 must never be “less than” k1.
  • If k1 is “less than” k2 and k2 is “less than” k3, then k1 must be “less than” k3.
  • If there are two keys, and neither key is “less than” the other, then we’ll say that those keys are “equivalent.” If k1 is “equivalent” to k2 and k2 is “equivalent” to k3, then k1 must be “equivalent” to k3.

If two keys are equivalent (i.e., if neither is “less than” the other), the container treats them as equal. When used as a key to a map, there will be only one element associated with those keys, and either key can be used to access the corresponding value.

INFO

In practice, what’s important is that a type that defines a < operator that “behaves normally” can be used as a key.

Using a Comparison Function for the Key Type

The type of the operation that a container uses to organize its elements is part of the type of that container. To specify our own operation, we must supply the type of that operation when we define the type of an associative container. The operation type is specified following the element type inside the angle brackets that we use to say which type of container we are defining.

Each type inside the angle brackets is just that, a type. We supply a particular comparison operation (that must have the same type as we specified inside the angle brackets) as a constructor argument when we create a container.

For example, we can’t directly define a multiset of Sales_data because Sales_data doesn’t have a < operator. However, we can use the compareIsbn function from the exercises in § 10.3.1 (p. 387) to define a multiset. That function defines a strict weak ordering based on their ISBNs of two given Sales_data objects. The compareIsbn function should look something like

c++
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}

To use our own operation, we must define the multiset with two types: the key type, Sales_data, and the comparison type, which is a function pointer type (§ 6.7, p. 247) that can point to compareIsbn. When we define objects of this type, we supply a pointer to the operation we intend to use. In this case, we supply a pointer to compareIsbn:

c++
// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*>
    bookstore(compareIsbn);

Here, we use decltype to specify the type of our operation, remembering that when we use decltype to form a function pointer, we must add a * to indicate that we’re using a pointer to the given function type (§ 6.7, p. 250). We initialize bookstore from compareIsbn, which means that when we add elements to bookstore, those elements will be ordered by calling compareIsbn. That is, the elements in bookstore will be ordered by their ISBN members. We can write compareIsbn instead of &compareIsbn as the constructor argument because when we use the name of a function, it is automatically converted into a pointer if needed (§ 6.7, p. 248). We could have written &compareIsbn with the same effect.

INFO

Exercises Section 11.2.2

Exercise 11.9: Define a map that associates words with a list of line numbers on which the word might occur.

Exercise 11.10: Could we define a map from vector<int>::iterator to int? What about from list<int>::iterator to int? In each case, if not, why not?

Exercise 11.11: Redefine bookstore without using decltype.

11.2.3. The pair Type

Before we look at the operations on associative containers, we need to know about the library type named pair, which is defined in the utility header.

A pair holds two data members. Like the containers, pair is a template from which we generate specific types. We must supply two type names when we create a pair. The data members of the pair have the corresponding types. There is no requirement that the two types be the same:

c++
pair<string, string> anon;       // holds two strings
pair<string, size_t> word_count; // holds a string and an size_t
pair<string, vector<int>> line;  // holds string and vector<int>

The default pair constructor value initializes (§ 3.3.1, p. 98) the data members. Thus, anon is a pair of two empty strings, and line holds an empty string and an empty vector. The size_t value in word_count gets the value 0, and the string member is initialized to the empty string.

We can also provide initializers for each member:

c++
pair<string, string> author{"James", "Joyce"};

creates a pair named author, initialized with the values "James" and "Joyce".

Unlike other library types, the data members of pair are public (§ 7.2, p. 268). These members are named first and second, respectively. We access these members using the normal member access notation (§ 1.5.2, p. 23), as, for example, we did in the output statement of our word-counting program on page 421:

c++
// print the results
cout <<  w.first << " occurs " << w.second
     << ((w.second > 1) ? " times" : " time") << endl;

Here, w is a reference to an element in a map. Elements in a map are pairs. In this statement we print the first member of the element, which is the key, followed by the second member, which is the counter. The library defines only a limited number of operations on pairs, which are listed in Table 11.2.

Table 11.2. Operations on pairs

CodeDescription
pair<T1, T2> p;p is a pair with value initialized (§ 3.3.1, p. 98) members of types T1 and T2, respectively.
pair<T1, T2> p(v1, v2);p is a pair with types T1 and T2; the first and second members are initialized from v1 and v2, respectively.
pair<T1, T2> p = {v1, v2};Equivalent to p(v1, v2).
make_pair(v1, v2)Returns a pair initialized from v1 and v2. The type of the pair is inferred from the types of v1 and v2.
p.firstReturns the (public) data member of p named first.
p.secondReturns the (public) data member of p named second.
p1 relop p2Relational operators (<, >, <=, >=). Relational operators are defined as dictionary ordering. For example, p1 < p2 is true if p1.first < p2.first or if !(p2.first < p1.first) && p1.second < p2.second. Uses the element's < operator.
p1 == p2 p1 != p2Two pairs are equal if their first and second members are respectively equal. Uses the element's == operator.
A Function to Create pair Objects

Imagine we have a function that needs to return a pair. Under the new standard we can list initialize the return value (§ 6.3.2, p. 226):

C++11

c++
pair<string, int>
process(vector<string> &v)
{
     // process v
     if (!v.empty())
         return {v.back(), v.back().size()}; // list initialize
     else
         return pair<string, int>(); // explicitly constructed return value
}

If v isn’t empty, we return a pair composed of the last string in v and the size of that string. Otherwise, we explicitly construct and return an empty pair.

Under earlier versions of C++, we couldn’t use braced initializers to return a type like pair. Instead, we might have written both returns to explicitly construct the return value:

c++
if (!v.empty())
    return pair<string, int>(v.back(), v.back().size());

Alternatively, we could have used make_pair to generate a new pair of the appropriate type from its two arguments:

c++
if (!v.empty())
     return make_pair(v.back(), v.back().size());

INFO

Exercises Section 11.2.3

Exercise 11.12: Write a program to read a sequence of strings and ints, storing each into a pair. Store the pairs in a vector.

Exercise 11.13: There are at least three ways to create the pairs in the program for the previous exercise. Write three versions of that program, creating the pairs in each way. Explain which form you think is easiest to write and understand, and why.

Exercise 11.14: Extend the map of children to their family name that you wrote for the exercises in § 11.2.1 (p. 424) by having the vector store a pair that holds a child’s name and birthday.