11.2.2. Requirements on Key Type

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.

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.

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

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:

// 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.