unordered_map和unordered_set的简易实现

我们在学习了哈希概念，模拟实现了简单的哈希表后，就可以着手来模拟实现unordered_map和unordered_set了，承接上一篇博客对哈希的学习哈希概念讲解及哈希表简单实现 。
我们要把哈希表修改一下，加入迭代器，参数模板化，方便上层map和set封装同一个哈希表。

上层map和set中都要分别实现一个仿函数，方便取出key值来操作。

template<class K, class V,class Hash = opentable::hashfunc<K>> //哈希函数同上篇博客哈希函数一样
class unordered_map      //这里是map的仿函数用来在哈希表数据类型T中取key来操作
	{
		struct mapKey
		{
			const K& operator()(const pair<K, V>& val)
			{
				return val.first;
			}
		};
		public:
		//这里就是map中的常规方法
		private:
		opentable::hashtable<K, pair<K,V>, mapKey, Hash>_Htable;//封装一个哈希表，传入两个仿函数，一个是哈希函数，
		//一个是在哈希表中T数据类型中取出key，这里就和红黑树实现的map，set是一样的
	};
//unordered_set封装哈希表类似
template<class K,class Hash=opentable::hashfunc<K>>
	class unordered_set
	{
		struct setKey
		{
			const K& operator()(const K& val)
			{
				return val;
			}
		};
	public:
	//set中常用的方法
	private:
		opentable::hashtable<K, K, setKey, Hash>_Htable;
	};
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

再来看如果将哈希表改造一下适配这里要封装使用哈希表的map和set。

template<class T>
	struct hashdata         //用到的哈希表是开散列的，节点存储的数据类型是模板化的T
	{ 
		T data;
		struct hashdata<T>* next;
		hashdata(const T&val)
			:data(val)
			,next(nullptr)
		{}
	};
	template<class K>
	struct hashfunc                   //哈希函数就放一下在这里
	{
		size_t operator()(const K& val)
		{
			return val;
		}
	};
	template<>
	struct hashfunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t ret = 0;
			for (int i = 0; i < s.size(); ++i)
			{
				ret *= 31;
				ret += s[i];
			}
			return ret;
		}
	};
	template<class K, class T, class KofT, class func>
	class hashtable;  //因为迭代器中要用到哈希表，所以要先声明哈希表
	template<class K,class T,class KofT,class func,class Ref,class Ptr>
	struct Htiterator   //unordered系列的map和set的迭代器要存节点指针和哈希表指针，方便迭代器的++ 向后移动操作
	{
		typedef hashdata<T> Node;   //三个重命名
		typedef hashtable<K, T, KofT, func> table;
		typedef Htiterator<K, T, KofT, func, Ref, Ptr> self;
		Node* _t;  //这里就是迭代器存储的数据两个指针
		table* _h;
		Htiterator(Node*n,table*b)  //迭代器构造函数
			:_t(n)
			,_h(b)
		{}
		Ref operator*()     //迭代器的解引用返回节点数据T
		{
			return _t->data;  
		}
		Ptr operator->()   //迭代器->返回数据地址
		{
			return &_t->data;
		}
		self& operator++() //++操作就要在表中找该节点的下一个节点的地址了
		{
			if (_t->next)   //如果这个桶还有数据，就继续向下遍历
			{
				_t = _t->next;
				return *this;
			}
			KofT kt;
			func hf;     //传入的两个仿函数来找当前节点的哈希地址
			size_t start = hf(kt(_t->data)) % _h->_table.size(); //从这桶开始找下一个桶
			++start;
			while (start != _h->_table.size())
			{
				if (_h->_table[start])        //找到下一个桶，也就是下一个链表，更新迭代器结点指针指向下一个链表的头节点
				{
					_t = _h->_table[start];
					return *this;
				}
				++start;
			}
			_t = nullptr;  //走到尾部，节点指针就置空
			return *this;
		}
		self operator++(int)       //后置++    
		{
			Node* cur = _t;
			if (_t.next)
			{
				_t = _t->next;
			}
			else
			{
				KofT kt;
				func hf;
				size_t start = hf(kt(_t->data)) % _h->_table.size();
				++start;
				while (start != _h->_table.size())
				{
					if (_h->_table[start])
					{
						break;
					}
					++start;
				}
				if (start == _h->_table.size())
					_t = nullptr;
				else
					_t = _h->_table[start];
			}
			return self(cur, _h);
		}
		bool operator!=(const self& it)const   //迭代器的!=  和==比较
		{
			return _t != it._t;
		}
		bool operator==(const self& it)const
		{
			return _t == it._t;
		}
	};
	class hashtable
	{
		typedef hashdata<T> Node;
	public:
		typedef Htiterator<K, T, KofT, func, T&, T*> iterator;
		typedef Htiterator<K, T, KofT, func, const T&, const T*> const_iterator;
		typedef hashtable<K, T, KofT, func> self;
		friend iterator;    //这里要将迭代器设置为友元类，迭代器要访问哈希表的vector
		friend const_iterator;
		/*hashtable() //   手动写默认构造方式一                在上层set和map中是自定义类型hashtable,上层没有写构造函数，
		{}*/              // 默认生成的构造函数回去调用hashtable的默认构造，hashtable实现了拷贝构造，就不会自动生成默认构造。需手动写
		hashtable() = default;    //手动写默认构造方式二， 显示要求系统生成默认构造，两种方式都会在初始化列表阶段初始化成员数据，就是又去调用vector的构造函数
		hashtable(const self& co)       //哈希表的拷贝构造，将传入的哈希表的每个桶上的节点挨个深拷贝过去
		{ 
			_table.resize(co._table.size());
			n = co.n;
			for (int i = 0; i < co._table.size(); ++i)
			{
				if (co._table[i])
				{
					Node* cur = co._table[i];
					while (cur)
					{
						Node* newnode = new Node(cur->data);
						newnode->next = _table[i];  //按对应的下标i拷贝过去
						_table[i] = newnode;
						cur = cur->next;
					}
				}
			}
		}
		~hashtable()
		{
			for (int i = 0; i < _table.size(); ++i)
			{
				if (_table[i])
				{
					Node* cur = _table[i];
					while (cur)   //析构哈希表，挨个找到每条链，析构一条链上的节点前保存下一个节点的地址
					{
						Node* next = cur->next;
						delete cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
			}
		}
		self& operator=(self co)    //现代写法
		{
			_table.swap(co._table);
			n = co.n;
			return *this;
		}
		iterator begin()  //找到数组中第一条链第一个节点，没有就返回end()
		{
			if (n == 0)
				return end();
			Node* cur = _table[0];
			size_t i= 0;
			while (cur == nullptr)
			{
				++i;
				cur = _table[i];
			}
			return iterator(cur, this);  //以第一个节点地址和哈希表地址构造迭代器
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
		iterator find(const K& key)   //K 类型形参接受传入的key值
		{
			if (n == 0)
				return end();
			func hf;
			KofT kt;
			size_t start = hf(key) % _table.size();  //K模板参数就是用来接受key的类型的
			Node* cur = _table[start];
			while (cur)
			{
				if (kt(cur->data) == key)
					return iterator(cur,this);  //找到了就返回以该节点构造的迭代器
				cur = cur->next;
			}
			return end();  //没找到就返回end（）
		}
         bool erase(const K& key)   //没有其他变化就是多了一个仿函数来提取元素数据的作比较
         {
			if (_table.empty())
				return false;
			func hf;
			KofT kt;
			size_t start = hf(key) % _table.size();  
			Node* prev = nullptr, * cur = _table[start];
			while (cur&&kt(cur->data) != key)
			{
				prev = cur;
				cur = cur->next;
			}
			if (cur == nullptr)
				return false;
			else
			{
				--n;
				if (cur == _table[start])
				{
					_table[start] = cur->next;
					delete cur;
				}
				else
				{
					prev->next = cur->next;
					delete cur;
				}
				
				return true;
			}
		}
         pair<iterator,bool> insert(const T&val)   //插入的返回类型是修改为pair<iterator,bool>
         {
			func hf;
			KofT kt;
			auto it = find(kt(val));    //取val的key值查找key是否已经存在
			if (it != end())
			{
				return pair<iterator, bool>(it, false);   //存在就返回存在位置的迭代器为first false为second的pair值
			}
			/*if (find(kt(val)))
				return  false;*/
			
			if (n == _table.size())       //扩容
			{
			size_t newsize = _table.size() == 0 ? 10 : 2 * _table.size();  
				if (newsize != _table.size())
				{
					vector<Node*>tem;
					tem.resize(newsize);
					for (auto& e : _table)
					{
						if (e)
						{
							Node* cur = e;
							while (cur)
							{
								size_t start = hf(kt(cur->data)) % newsize;
								Node* next = cur->next;
								cur->next = tem[start];
								tem[start] = cur;
								cur = next;
							}
							e = nullptr;
						}
					}
					_table.swap(tem);
				}	
			}	
			size_t start = hf(kt(val)) % _table.size();
			Node* newnode = new Node(val);
			newnode->next = _table[start];
			_table[start] = newnode;
			++n;
			return make_pair(iterator(newnode, this), true);  //返回插入节点迭代器为first，true为second的pair
		}
		private:
		vector<Node*> _table;
		size_t n = 0;
	};
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282

上层map和set的插入、查找和删除就调用哈希表相应的方法就行了。

template<class K, class V,class Hash = opentable::hashfunc<K>>
	class unordered_map
	{
		struct mapKey
		{
			const K& operator()(const pair<K, V>& val)
			{
				return val.first;
			}
		};
	public:
		typedef typename opentable::hashtable<K, pair<K, V>, mapKey, Hash>::iterator iterator;  //重命名类模板中的自定义类型要加typename说明
		iterator begin()
		{
			return _Htable.begin();
		}
		iterator end()
		{
			return _Htable.end();
		}
		pair<iterator,bool> insert(const pair<K, V>& val)
		{
			return _Htable.insert(val);
		}
		V& operator[](const K& val)   //[]的封装调用
		{
			auto it = _Htable.insert(pair<K, V>(val, V()));
			return it.first->second;
		}
		iterator find(const K& val)
		{
			return _Htable.find();
		}
		bool erase(const K& val)
		{
			return _Htable.erase();
		}  //map和set都不用实现构造函数，拷贝，析构等，自定义类型的哈希表会去自动调用它的相应构造，拷贝析构函数等
	private:
		opentable::hashtable<K, pair<K,V>, mapKey, Hash>_Htable;
	};
template<class K,class Hash=opentable::hashfunc<K>>
	class unordered_set
	{
		struct setKey
		{
			const K& operator()(const K& val)
			{
				return val;
			}
		};
	public:
		typedef typename opentable::hashtable<K, K, setKey, Hash>::iterator iterator;
		iterator begin()
		{
			return _Htable.begin();
		}
		iterator end()
		{
			return _Htable.end();
		}
		pair<iterator,bool> insert(const K& val)
		{
			return _Htable.insert(val);
		}
		iterator find(const K& val)
		{
			return _Htable.find(val);
		}
		bool erase(const K& val)
		{
			return _Htable.erase(val);
		}
	private:
		opentable::hashtable<K, K, setKey, Hash>_Htable;
	};
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