无序关联容器 (STL)

C++程序设计语言中，unordered_map、unordered_multimap、unordered_set、unordered_multiset是标准模板库（STL）提供的一类无序关联容器（unordered associative containers）。是通过哈希表实现的数据结构。无序是指元素的名字（或者键值）的存储是无序的；这与用平衡二叉树实现的元素名字是有序存储的“关联容器”是相对概念。
历史
SGI的STL提供了hash_map, hash_set, hash_multimap, hash_multiset等类模板。由于其有用性，很快其它的C++编译器也支持了这一特性，如GCC、 libstdc++ 以及MSVC （在stdext命名空间）。

C++ TR1语言标准中提出了增加hash_类模板，最终接受为unordered_。 Boost C++ Libraries也提供了一种实现。.

类成员函数
头文件中定义了类模板unordered_map。并满足[http://www.sgi.com/tech/stl/Container.html 容器] 概念，这意味着它支持begin()、end()、size()、max_size()、empty()、 swap()等方法。

例子
#include
#include
#include

int main()
{
std::unordered_map months;
months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
std::cout " " " "

定制哈希函数
定制的哈希函数的参数为到定制类型的const引用，返回类型为size_t

struct X{int i,j,k;};

struct hash_X{
size_t operator()(const X &x) const{
return hash()(x.i) ^ hash()(x.j) ^ hash()(x.k);
}
};

定制哈希函数作为std::unordered_map的模板参数使用。
std::unordered_map my_map;

或者通过特化std::hash来使用。

namespace std {
template <>
class hash{
public :
size_t operator()(const X &x ) const{
return hash()(x.i) ^ hash()(x.j) ^ hash()(x.k);
}
};
}

//...
std::unordered_map my_map;

参考文献