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
.
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.
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.
In practice, what’s important is that a type that defines a <
operator that “behaves normally” can be used as a key.
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.
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
.