12.6unordered_map
The cost of amaplookup isO(log(n))wherenis the number of elements in themap. That’s pretty good. For example, for amapwith 1,000,000 elements, we perform only about 20 comparisons and indirections to find an element. However, in many cases, we can do better by using a hashed lookup rather than a comparison using an ordering function, such as<. The standard-library hashed containers are referred to as “unordered” because they don’t require an ordering function:
For example, we can use anunordered_mapfrom
unordered_mapphone_book { {"David Hume",123456}, {"Karl Popper",234567}, {"Bertrand Arthur William Russell",345678} };
Like for amap, we can subscript anunordered_map:
int get_number(const string& s) { return phone_book[s]; }
The standard library provides a default hash function forstring年代以及其他内置和standard-library types. If necessary, we can provide our own. Possibly, the most common need for a custom hash function comes when we want an unordered container of one of our own types. A hash function is often implemented as a function object (§7.3.2). For example:
struct Record { string name; int product_code; //...};struct Rhash { //a hash function for Recordsize_t operator()(const Record& r) const { return hash()(r.name) ^ hash unordered_set()(r.product_code); } }; my_set; // set of Records using Rhash for lookup
Designing good hash functions is an art and often requires knowledge of the data to which it will be applied. Creating a new hash function by combining existing hash functions using exclusive-or (^)通常很简单,非常有效。然而,是careful to ensure that every value that takes part in the hash really helps to distinguish the values. For example, unless you can have several names for the same product code (or several product codes for the same name), combining the two hashes provides no benefits.
We can avoid explicitly passing thehashoperation by defining it as a specialization of the standard-libraryhash:
namespace std { //make a hash function for Recordtemplate<> struct hash{ using argument_type = Record; using result_type = size_t; result_type operator()(const Record& r) const { return hash()(r.name) ^ hash ()(r.product_code); } }; }
Note the differences between amapand anunordered_map:
Amaprequires an ordering function (the default is<) and yields an ordered sequence.
Aunordered_maprequires an equality function (the default is==); it does not maintain an order among its elements.
Given a good hash function, anunordered_mapis much faster than amapfor large containers. However, the worst-case behavior of anunordered_mapwith a poor hash function is far worse than that of amap.