热爱互联网

c++ 11 —- unordered_set unordered_map

详见: http://www.cplusplus.com/reference/unordered_set/unordered_set/
http://www.cplusplus.com/reference/unordered_set/unordered_multiset/
http://www.cplusplus.com/reference/unordered_map/unordered_map/
http://www.cplusplus.com/reference/unordered_map/unordered_multimap/

unordered_set,unordered_map 的原理是一样的,都是开链哈希,不解释了。
他们不保证任何顺序(包括输出),不能更改key,只能删除和插入。
unorderer_multiset ,unordered_multimap 则允许重复的值。

四种容器大同小异,下面以 unordered_set 作为例子:
基本操作如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<unordered_set>
#include<unordered_map>
using namespace std;
 
/*
	template< class key,   					 // unordered_set::key_type/value_type
			  class Hash = hash<key>,		 // unordered_set::hasher
			  class Pred = equal_to<key>,	 // unordered_set::key_equal
			  class Alloc = allocator<key>,	 // unordered_set::allocator_type
			> class unordered_set;
*/
 
template<typename T>
T cmerge(T a,T b)
{
	T t(a);
	t.insert(b.begin(),b.end());
	return t;
}
 
int main()
{
	// constructor
	unordered_set<string> us1;
	unordered_set<string> us2 = {"red","green","blue"};
	unordered_set<string> us3(us2);
 
	unordered_set<string> us4 (cmerge(us2,us3));
	unordered_set<string> us5 (us4.begin(),us4.end());
 
	for(auto x : us5)
		cout << x << " ";
	cout << endl;
 
	us1 = us2;
	for(auto x : us1)  // blue red green ,输出并不保证顺序
		cout << x << " ";
	cout << endl;
 
	// capacity and buckets
	cout << us1.empty() <<endl;  // 0
	cout << us1.size() <<endl;   // 3
	cout << us1.max_size() <<endl; // 357913941
 
	unordered_set<int> us6;
	cout << us6.empty() <<endl;   // 1
	cout << us6.max_size() <<endl;  // 536870911
	cout << us6.max_bucket_count() <<endl;  // 536870911
	cout << us6.max_load_factor() <<endl;  // 1
	cout << us6.bucket_count() <<endl;  // 11
	cout << us6.load_factor() <<endl;  // 0
 
	// iterators
	for(auto iter = us5.begin(); iter != us5.end(); ++iter)
		cout << *iter << " ";
	cout << endl;
 
	// element lookup and modifiers
	if( us5.find("lijie") == us5.end() )
		cout << "none" <<endl;
 
	cout << us5.count("lijie") <<endl; // 0
	cout << us5.count("red") <<endl;  // 1
 
	us5.insert("lijie");
	for(auto x : us5)
		cout << x << " ";
	cout <<endl;
 
	us5.erase("lijie");   // erasing by key
	// us5.erase(us5.find("lijie"));  // erasing by iterator
 
	us5.erase( us5.find("red"), us5.end() ); // erasing by range
	for(auto x : us5)
		cout << x << " ";
	cout <<endl;
 
	// hash policy and observers
	unordered_set<string> myset;
	myset.rehash(12);
 
	myset.insert("office");
	myset.insert("house");
	myset.insert("gym");
	myset.insert("parking");
	myset.insert("highway");
 
	cout << myset.bucket_count() <<endl;  // 7
 
	// hash function
	unordered_set<string>::hasher fn = myset.hash_function();
 
	cout << fn("that") << endl;
	cout << fn("than") << endl;
 
	// comparisons
	unordered_set<string>
	a = {"AAPL","MSFT","GOOG"},
	b = {"MSFT","GOOG","AAPL"},
	c = {"MSFT","GOOG","AAPL","ORCL"};
 
	if( a == b ) cout << " a and b are equal " <<endl;
	if( b != c ) cout << " b and c are not equal " <<endl;
 
	return 0;
}

下面是自定义自己的hash函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
 
struct Node
{
	string a;
	int b;
	char c;
 
	Node(string _a,int _b,char _c): a(_a),b(_b),c(_c) { }
};
 
template<typename T>
struct myhash
{
	int operator()(const T& a) const  // 用 b 来做 key
	{
		return a.b % 100;
	}
};
 
template<typename T>
struct myequal
{
	bool operator()(const T& a,const T& b) const  // 用 c 来作为值比较大小
	{
		return a.c == b.c;
	}
};
 
int main()
{
	unordered_set<node,myhash<node>,myequal<node>> us;
 
	Node a("lijie",520,'c'),b("dou",52,'d');
	us.insert(a);
	us.insert(b);
 
	for(auto x : us)
		cout << x.a << " " << x.b << " " << x.c <<endl;
 
	return 0;
}

Post a Comment

Your email is kept private. Required fields are marked *