无序容器（unordered containers）

一个无序容器实际上就是某种形式的蛤希表。C++0x提供四种标准的无序容器：

• unordered_map
• unordered_set
• unordered_multimap
• unordered_multiset

实际上，它们应该被称为hash_map等。但是因为有很多地方已经在使用hash_map这样的名字了，为了保证其兼容性，标准委员会不得不选择新的名字。而unordered_map是我们所能够找到的最好的名字了。无序（“unordered”）代表着map和unordered_map之间一个最本质的差别：当你使用map容器的时候，容器中的所有元素都是通过小于操作（默认情况下使用“<”操作符）排好序的，但是unordered_map并没有对元素进行排序，所以它并不要求元素具有小于操作符。并且，一个哈希表也并添言地提供排序的功能。相反，map容器中的元素也并不要求具有哈希函数。 基本上，当代码的优化是可能的并且我们有理由对其进行优化时，我们可以把unordered_map当作一个优化之后的map容器来使用。例如：

map<string,int> m {
    {“Dijkstra”,1972}, {“Scott”,1976},
    {“Wilkes”,1967}, {“Hamming”,1968}
};
m["Ritchie"] = 1983;
for(auto x : m)
    cout << ‘{‘ << x.first << ‘,’ << x.second << ‘}’;

// 使用优化之后的unordered_map
unordered_map<string,int> um {
    {“Dijkstra”,1972}, {“Scott”,1976},
    {“Wilkes”,1967}, {“Hamming”,1968}
};
um["Ritchie"] = 1983;
for(auto x : um)
    cout << ‘{‘ << x.first << ‘,’ << x.second << ‘}’;

map容器m的迭代器将以字母的顺序访问容器中的所有元素，而unordered_map容器um则并不按照这样的顺序（除非通过一些特殊的操作）。m和um两者的查找功能的实现机制是非常不同的。对于m，它使用的是复杂度为log2(m.size())的小于比较，而um只是简单地调用了一个哈希函数和一次或多次的相等比较。如果容器中的元素比较少（比如几打），很难说哪一种容器更快，但是对于大量数据（比如数千个）而言，unordered_map容器的查找速度要比map容器快很多。

更多内容稍后提供。

参考：

? Standard: 23.5 Unordered associative containers.

(翻译：Yibo Zhu)