STL map与Boost unordered_map

我不是女神ヾ 2022-08-22 03:57 195阅读 0赞

参考：http://blog.csdn.net/orzlzro/article/details/7099231

今天看到 boost::unordered\_map， 它与 stl::map的区别就是，stl::map是按照operator<比较判断元素是否相同，以及比较元素的大小，然后选择合适的位置插入到树中。所以，如果对map进行遍历（中序遍历）的话，输出的结果是有序的。顺序就是按照operator< 定义的大小排序。

而boost::unordered\_map是计算元素的Hash值，根据Hash值判断元素是否相同。所以，对unordered\_map进行遍历，结果是无序的。

用法的区别就是，stl::map 的key需要定义operator< 。 而boost::unordered\_map需要定义hash\_value函数并且重载operator==。对于内置类型，如string，这些都不用操心。对于自定义的类型做key，就需要自己重载operator< 或者hash\_value()了。

最后，说，当不需要结果排好序时，最好用unordered\_map。

其实，stl::map对于与[Java][]中的TreeMap，而boost::unordered\_map对应于java中的HashMap。

stl::map

**\[cpp\]** [ view plain][view plain] [ copy][view plain]

1.  \#include<string>  
2.  \#include<iostream>  
3.  \#include<map>  
4.    
5.  using namespace std;  
6.    
7.  struct person  
8.  \{  
9.      string name;  
10.     int age;  
11.   
12.     person(string name, int age)  
13.     \{  
14.         this\->name =  name;  
15.         this\->age = age;  
16.     \}  
17.   
18.     bool operator < (const person& p) const  
19.     \{  
20.         return this\->age < p.age;  
21.     \}  
22. \};  
23.   
24. map<person,int> m;  
25. int main()  
26. \{  
27.     person p1("Tom1",20);  
28.     person p2("Tom2",22);  
29.     person p3("Tom3",22);  
30.     person p4("Tom4",23);  
31.     person p5("Tom5",24);  
32.     m.insert(make\_pair(p3, 100));  
33.     m.insert(make\_pair(p4, 100));  
34.     m.insert(make\_pair(p5, 100));  
35.     m.insert(make\_pair(p1, 100));  
36.     m.insert(make\_pair(p2, 100));  
37.       
38.     for(map<person, int>::iterator iter = m.begin(); iter != m.end(); iter++)  
39.     \{  
40.         cout<<iter->first.name<<"\\t"<<iter->first.age<<endl;  
41.     \}  
42.       
43.     return 0;  
44. \}

output:

Tom1    20  
Tom3    22  
Tom4    23  
Tom5    24

operator<的重载一定要定义成const。因为map内部实现时调用operator<的函数好像是const。

由于operator<比较的只是age,所以因为Tom2和Tom3的age相同，所以最终结果里面只有Tom3，没有Tom2

boost::unordered\_map

**\[cpp\]** [ view plain][view plain] [ copy][view plain]

1.  \#include<string>  
2.  \#include<iostream>  
3.    
4.  \#include<boost/unordered\_map.hpp>  
5.    
6.  using namespace std;  
7.    
8.  struct person  
9.  \{  
10.     string name;  
11.     int age;  
12.   
13.     person(string name, int age)  
14.     \{  
15.         this\->name =  name;  
16.         this\->age = age;  
17.     \}  
18.   
19.     bool operator== (const person& p) const  
20.     \{  
21.         return name==p.name && age==p.age;  
22.     \}  
23. \};  
24.   
25. size\_t hash\_value(const person& p)  
26. \{  
27.     size\_t seed = 0;  
28.     boost::hash\_combine(seed, boost::hash\_value(p.name));  
29.     boost::hash\_combine(seed, boost::hash\_value(p.age));  
30.     return seed;  
31. \}  
32.   
33. int main()  
34. \{  
35.     typedef boost::unordered\_map<person,int> umap;  
36.     umap m;  
37.     person p1("Tom1",20);  
38.     person p2("Tom2",22);  
39.     person p3("Tom3",22);  
40.     person p4("Tom4",23);  
41.     person p5("Tom5",24);  
42.     m.insert(umap::value\_type(p3, 100));  
43.     m.insert(umap::value\_type(p4, 100));  
44.     m.insert(umap::value\_type(p5, 100));  
45.     m.insert(umap::value\_type(p1, 100));  
46.     m.insert(umap::value\_type(p2, 100));  
47.       
48.     for(umap::iterator iter = m.begin(); iter != m.end(); iter++)  
49.     \{  
50.         cout<<iter->first.name<<"\\t"<<iter->first.age<<endl;  
51.     \}  
52.       
53.     return 0;  
54. \}

输出

Tom1    20  
Tom5    24  
Tom4    23  
Tom2    22  
Tom3    22

必须要自定义operator==和hash\_value。 重载operator==是因为，如果两个元素的hash\_value的值相同，并不能断定这两个元素就相同，必须再调用operator==。 当然，如果hash\_value的值不同，就不需要调用operator==了。

[Java]: http://lib.csdn.net/base/17
[view plain]: http://blog.csdn.net/orzlzro/article/details/7099231#