熟悉STL或熟悉ACM/ICPC的话,其中的set, map, multiset, multimap一定用过无数次了,它们都是用平衡二叉树(红黑树)实现的,复杂度为O(lgn)。我们也知道set, map可以通过哈希来实现,复杂度只有O(1),可惜直到现在,unsorted_set或hash_map都没能成为C++标准的一部分(C++0x,- -b)。不过无论在GNU GCC中还是Microsoft Visual Studio中都有对hash_set, hash_map, hash_multiset, hash_multimap的支持。
GCC中的hash_map定义在<ext/hash_map>文件,namespace __gnu_cxx中。要定义一个hash_map<int, int>非常简单:
#include <ext/hash_map> using namespace __gnu_cxx; hash_map<int, int> hm;
在使用map时,如果我们想要改变元素顺序,或以自定义的struct/class作为key的时候,可以设定map第三个模板参数(默认是less<Key>,即operator<)。对于hash_map,我们需要设定其第三个(hash<Key>)和第四个模板参数(equal_to<Key>, operator==)。
typedef long long my_type; typedef int any_type; struct my_hash { size_t operator()(const my_type& key) const { return (key >> 32) ^ key; } }; struct my_equal_to { bool operator()(const my_type& lhs, const my_type& rhs) const { return lhs == rhs; } }; hash_map<my_type, any_type, my_hash, my_equal_to> my_hash_map;
对与int等基本类型,系统提供有hash<int>等版本的模板特化,所以只需要指定前两个模板参数就足够了。实现了模板特化的有以下类型
[const] char*, crope, wrope, [signed|unsigned] char, [unsigned] short, [unsigned] int, [unsigned] long
如果需要的话,我们也可以为其他类型实现模板特化
// hash_map<Key, Tp, HashFn=hash<Key>, EqualKey=equal_to<Key>, Alloc=allocator<Tp> > #include <cstdio> #include <utility> #include <hash_map> using namespace std; using namespace __gnu_cxx; namespace __gnu_cxx { template<> struct hash<pair<int, int> > { size_t operator()(const pair<int, int>& key) const { return key.first * key.second; } }; } hash_map<pair<int, int>, int> hm;
Visual C++的hash_map定义在<hash_map>文件,namespace stdext中,早先在namespace std中。其实现与GCC的不同,模板参数也不一样,比如上面的例子在VC++版本如下