4.4.4 unordered_map

搜索map的时间代价是O（log（n），其中n是map元素的数目。通常情况下，这样的性能非常好。例如，考虑一个包含100万个元素的map，我们只需执行约20次比较和间接寻址操作即可找到元素。不过，在很多情况下我们还可以做得更好，那就是使用哈希查找，而不是使用基于某种序函数的比较操作（如<）。标准库哈希容器被称为“无序”容器，因为它们不需要序函数：

例如，我们可以使用< unordered map>中定义的 unordered map来编写电话簿程序：

unordered_ map<string, int> phone_book 
{
    {"David Hume",123456},
    {"Karl Popper",23456},
    {"Ertrand Arthur William Russell",456894}
};

与map类似,我们也可以对unordered_map使用下标操作:

int get_number(const string&s)
{
    return phone_book[s];
}

标准库 unordered_map为 string提供了默认的哈希函数。如有必要，你也可以定义自己的哈希函数（见31.4.3.4节）。