STL map與Boost unordered_map - orzlzro的專欄 - 博客頻道 - CSDN.NET

?

STL map與Boost unordered_map

分類：
C++

2011-12-24 11:05
1182人閱讀
評論 (0)
收藏
舉報

?

今天看到? 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 copy print ?

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. }??

        #include<string>
#include<iostream>
#include<map>

using namespace std;

struct person
{
	string name;
	int age;

	person(string name, int age)
	{
		this->name =  name;
		this->age = age;
	}

	bool operator < (const person& p) const
	{
		return this->age < p.age;
	}
};

map<person,int> m;
int main()
{
	person p1("Tom1",20);
	person p2("Tom2",22);
	person p3("Tom3",22);
	person p4("Tom4",23);
	person p5("Tom5",24);
	m.insert(make_pair(p3, 100));
	m.insert(make_pair(p4, 100));
	m.insert(make_pair(p5, 100));
	m.insert(make_pair(p1, 100));
	m.insert(make_pair(p2, 100));

	for(map<person, int>::iterator iter = m.begin(); iter != m.end(); iter++)
	{
		cout<<iter->first.name<<"\t"<<iter->first.age<<endl;
	}

	return 0;
}

      

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 copy print ?

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. }??

        #include<string>
#include<iostream>

#include<boost/unordered_map.hpp>

using namespace std;

struct person
{
	string name;
	int age;

	person(string name, int age)
	{
		this->name =  name;
		this->age = age;
	}

	bool operator== (const person& p) const
	{
		return name==p.name && age==p.age;
	}
};

size_t hash_value(const person& p)
{
	size_t seed = 0;
	boost::hash_combine(seed, boost::hash_value(p.name));
	boost::hash_combine(seed, boost::hash_value(p.age));
	return seed;
}

int main()
{
	typedef boost::unordered_map<person,int> umap;
	umap m;
	person p1("Tom1",20);
	person p2("Tom2",22);
	person p3("Tom3",22);
	person p4("Tom4",23);
	person p5("Tom5",24);
	m.insert(umap::value_type(p3, 100));
	m.insert(umap::value_type(p4, 100));
	m.insert(umap::value_type(p5, 100));
	m.insert(umap::value_type(p1, 100));
	m.insert(umap::value_type(p2, 100));

	for(umap::iterator iter = m.begin(); iter != m.end(); iter++)
	{
		cout<<iter->first.name<<"\t"<<iter->first.age<<endl;
	}

	return 0;
}

      

輸出

Tom1 ? ?20

Tom5 ? ?24

Tom4 ? ?23

Tom2 ? ?22

Tom3 ? ?22

必須要自定義operator==和hash_value。 重載operator==是因為，如果兩個元素的hash_value的值相同，并不能斷定這兩個元素就相同，必須再調用operator==。
當然，如果hash_value的值不同，就不需要調用operator==了。

STL map與Boost unordered_map - orzlzro的專欄 - 博客頻道 - CSDN.NET