Posts Tagged “macro”

熟悉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++版本如下

Comments 15 Comments »