电子元器件网站怎么做,微信订阅号怎么做网站,wordpress 默认html5,wordpress 列表页输出熟悉STL或熟悉ACM/ICPC的话#xff0c;其中的set, map, multiset, multimap一定用过无数次了#xff0c;它们都是用平衡二叉树#xff08;红黑树#xff09;实现的#xff0c;复杂度为O(lgn)。我们也知道set, map可以通过哈希来实现#xff0c;复杂度只有O(1)#xff0c… 熟悉STL或熟悉ACM/ICPC的话其中的set, map, multiset, multimap一定用过无数次了它们都是用平衡二叉树红黑树实现的复杂度为O(lgn)。我们也知道set, map可以通过哈希来实现复杂度只有O(1)可惜直到现在unsorted_set或hash_map都没能成为C标准的一部分C0x- -b。不过无论在GNU GCC中还是Microsoft Visual Studio中都有对hash_set, hash_map, hash_multiset, hash_multimap的支持。 GCC中的hash_map定义在ext/hash_map文件namespace __gnu_cxx中。要定义一个hash_mapint, int非常简单 #include ext/hash_map using namespace __gnu_cxx; hash_mapint, int hm; 在使用map时如果我们想要改变元素顺序或以自定义的struct/class作为key的时候可以设定map第三个模板参数默认是lessKey即operator。对于hash_map我们需要设定其第三个(hashKey)和第四个模板参数(equal_toKey, 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_mapmy_type, any_type, my_hash, my_equal_to my_hash_map; 对与int等基本类型系统提供有hashint等版本的模板特化所以只需要指定前两个模板参数就足够了。实现了模板特化的有以下类型 [const] char*, crope, wrope, [signed|unsigned] char, [unsigned] short, [unsigned] int, [unsigned] long 如果需要的话我们也可以为其他类型实现模板特化 1 // hash_mapKey, Tp, HashFnhashKey, EqualKeyequal_toKey, AllocallocatorTp 2 #include cstdio 3 #include utility 4 #include hash_map 5 using namespace std; 6 using namespace __gnu_cxx; 7 8 namespace __gnu_cxx { 9 template 10 struct hashpairint, int { 11 size_t operator()(const pairint, int key) const { 12 return key.first * key.second; 13 } 14 }; 15 } 16 hash_mappairint, int, int hm; Visual C的hash_map定义在hash_map文件namespace stdext中早先在namespace std中。其实现与GCC的不同模板参数也不一样比如上面的例子在VC版本如下 1 // hash_mapKey, Type, Traitshash_compareKey, lessKey , Allocatorallocatorpairconst Key, Type 2 3 class hash_map 4 #include cstdio 5 #include utility 6 #include hash_map 7 using namespace std; 8 using namespace stdext; 9 10 template 11 struct hash_comparepairint, int { 12 // the mean number of elements per bucket 13 static const size_t bucket_size 4; 14 // the minimum number of buckets 15 static const size_t min_buckets 8; 16 // hash function 17 size_t operator()(const pairint, int key) const { 18 return key.first * key.second; 19 } 20 // compare function 21 bool operator()(const pairint, int lhs, const pairint, int rhs) const { 22 return lhs rhs; 23 } 24 }; 25 hash_mappairint, int, int hm; 相比前面的hash上面的hash_compare显然要复杂不少。 不过二者提供的方法基本一致也和std::map和其他STL容器相似。所以对于上面定义的hash_map我们都可以用下面的代码进行测试 1 ... 2 int main() { 3 int n; 4 scanf(%d, n); 5 for (int i 0; i n; i) { 6 hm[make_pair(i, i)] i; 7 } 8 for (hash_mappairint, int, int::iterator i hm.begin(); i ! hm.end(); i) { 9 printf(%d , i-second); 10 } 11 printf(\n%d / %d\n, hm.size(), hm.bucket_count()); 12 return 0; 13 } n取12时GCC 4.4.1得到的结果是 0 1 2 3 4 5 6 7 8 9 10 11 12 / 193 而Visual Studio 2010得到的结果是 0 4 8 1 3 5 7 9 11 2 6 10 12 / 8 由此我们可以看出二者在hash_map实现上的不同。__gnu_cxx::hash_map保持sizebucket_count而以193, 389, 769, 1543…这样近似成倍增长的质数作为bucket_count。stdext::hash_map则保持sizebucket_size*bucket_countbucket_count起初为min_buckets8不足时以8倍增长。 之所以我们要选择hash_map是为了获得更高的效率。hash_map比map到底快多少呢我们通过下面的程序来测试一下。通过__GNUC__和_MSC_VER这两个宏我们可以把两个版本的代码写到一起 1 #include map 2 #include ctime 3 #include cstdio 4 using namespace std; 5 6 #if defined(_MSC_VER) 7 # include hash_map 8 using stdext::hash_map; 9 #elif defined(__GNUC__) 10 # include ext/hash_map 11 using __gnu_cxx::hash_map; 12 #else 13 # error 悲剧啊 14 #endif 15 16 int main() { 17 clock_t S; 18 19 S clock(); 20 for (int i 0; i 20; i) { 21 hash_mapint, int H; 22 for (int i 0; i (1 20); i) { 23 H[i] i; 24 } 25 } 26 printf(hash_map: %.2lfs\n, (double)(clock() - S) / CLOCKS_PER_SEC); 27 28 S clock(); 29 for (int i 0; i 20; i) { 30 mapint, int M; 31 for (int i 0; i (1 20); i) { 32 M[i] i; 33 } 34 } 35 printf(map: %.2lfs\n, (double)(clock() - S) / CLOCKS_PER_SEC); 36 37 return 0; 38 } 结果得到的是gcc和VS的结果分别来自不同机器因此没有可比性 * g -O2 hash_map: 5.39s map: 12.35s * VS2010 Release hash_map: 9.53s map: 9.44s 发现g里hash_map确实要比map快不少而Visual Studio 2010就是个悲剧信hash_map不如信春哥啊。 嘛hash_map确实可能带来一些performance但不那么stable所以我们可以考虑优先使用hash_map而将map最为fallback备胎。 1 #define USE_HASH_MAP ? 2 #if USE_HASH_MAP 3 #include ext/hash_map 4 typedef __gnu_cxx::hash_mapint, int Hash; 5 #else 6 #include map 7 typedef std::mapint, int Hash; 8 #endif 不过在浙大校赛这种judge是优秀的gcc而比赛环境是混乱的VC6的比赛里。hash_map什么的还是能不用就不用吧…… This entry was posted on Thursday, March 25th, 2010 at 9:34 pm and is filed under summary. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
