C++ Primer Plus

Associative containers provide the methods listed in Table G.10. In general, the comparison object need not require that values with the same key be identical; the term equivalent keys means that two values, which may or may not be equal, have the same key. In the table, X is a container class, and a is an object of type X. If X uses unique keys (that is, is set or map), a_uniq is an object of type X. If X uses multiple keys (that is, is multiset or multimap), a_eq is an object of type X. As before, i and j are input iterators referring to elements of value_type, [i, j) is a valid range, p and q2 are iterators to a, q and q1 are dereferenceable iterators to a, [q1, q2) is a valid range, t is a value of X::value_type (which may be a pair), and k is a value of X::key_type. Also il is an initializer_list object.

Table G.10. Operations Defined for Sets, Multisets, Maps, and Multimaps

Unordered Associative Containers (C++11)

As mentioned earlier, the unordered associative containers (unordered_set, unordered_multiset, unordered_map, and unordered_multimap) use keys and hash tables to provide rapid access to data. Let’s take a simple look at these concepts. A hash function converts a key to an index value. For example, if the key were a string, the hash function could sum the numeric codes for the characters in the string and take that sum modulus 13, thus giving an index in the range 0–12. The unordered container would use 13 buckets to store strings. Any string with, say, an index of 4 would be placed in bucket 4. If you wished to search the container for a key, you would apply the hash function to the key and just search the bucket with the corresponding index. Ideally, you would have enough buckets that each one would contain only a few strings.

The C++11 library provides a hash template that the unordered associative containers use by default. Specializations are defined for the various integer and floating-point types, for pointers, and for some template classes, such as string.

Table G.11 lists types used for these containers.

Table G.11. Types Defined for Unordered Associative Containers

The interface for the unordered associative containers is similar to that of the associative containers. In particular, Table G.10 also applies to the unordered associative containers with the following exceptions: The lower_bound() and upper_bound() methods are not required, nor is the X(i,j,c) constructor. The fact that the regular associative containers are ordered allows them to use a comparison predicate that expresses the “less than” concept. Such a comparison doesn’t apply to unordered associative containers, so, instead, they use a comparison predicate that is based on the “is equivalent to” concept.

In addition to the Table G.10 methods, the unordered associative containers require several more methods, as listed in Table G.12. In this table, X is an unordered associative container class, a is an object of type X, b is a possibly constant object of type X, a_uniq is an object of type unordered_set or unordered_map, a_eq is an object of type unordered_multiset or unordered_multimap, hf is a value of type hasher, eq is a value of type key_equal, n is a value of type size_type, and z is a value of type float. As before, i and j are input iterators referring to elements of value_type, [i, j) is a valid range, p and q2 are iterators to a, q and q1 are dereferenceable iterators to a, [q1, q2) is a valid range, t is a value of X::value_type (which may be a pair), and k is a value of X::key_type. Also il is an initializer_list object.

Table G.12. Additional Operations Defined for Unordered Sets, Multisets, Maps, and Multimaps

STL Functions