devbox
在线问答5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

unordered_map和unordered_set模拟实现

作者：在线问答5 | 2024-08-05 15:54:33

赞

踩

unordered_map和unordered_set模拟实现

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

一、哈希

1.1哈希概念

构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

1.2哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

1.3哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

常见的哈希函数：

1.直接定址法：

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况

2.除留余数法：

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。

1.4哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

1.4.1闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

1.线性探测

插入：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

删除：删除时不可以物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。因为在查找时，遇到空就查找结束。

线性探测的实现：

  1. template<class K>
  2. struct DefaultHashFunc
  3. {
  4. 	size_t operator()(const K& key)
  5. 	{
  6. 		return (size_t)key;
  7. 	}
  8. };
  9.  
  10. template<>
  11. struct DefaultHashFunc<string>
  12. {
  13. 	size_t operator()(const string& str)
  14. 	{
  15. 		size_t n = 0;
  16. 		for (auto ch : str)
  17. 		{
  18. 			n *= 131;
  19. 			n += ch;
  20. 		}
  21. 		return n;
  22. 	}
  23. };
  24.  
  25. namespace open_address//开放地址法
  26. {
  27. 	//状态
  28. 	enum STATE
  29. 	{
  30. 		EMPTY, EXIST, DELETE//空，存在，删除
  31. 	};
  32.  
  33. 	//数据类型
  34. 	template<class K, class V>
  35. 	struct HashData
  36. 	{
  37. 		pair<K, V> _kv;
  38. 		STATE _state = EMPTY;
  39. 	};
  40.  
  41. 	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  42. 	class HashTable
  43. 	{
  44. 	public:
  45. 		HashTable()
  46. 		{
  47. 			_table.resize(10);
  48. 		}
  49.  
  50. 		bool insert(const pair<K, V>& kv)
  51. 		{
  52. 			//检查是否已经存在
  53. 			if (Find(kv.first))
  54. 				return false;
  55. 			//判断扩容
  56. 			HashFunc ht;
  57. 			int fac = (double)_n / _table.size();//负载因子
  58. 			if (fac >= 0.7)
  59. 			{
  60. 				//扩容之后可能会改变数据的映射关系，所以不能直接扩容
  61. 				size_t newcapacity = _table.capacity() * 2;
  62. 				HashTable<K, V> newHash;
  63. 				newHash._table.resize(newcapacity);
  64. 				//遍历旧表，插入到新表
  65. 				for (int i = 0; i < _table.capacity(); i++)
  66. 				{
  67. 					//只有exist状态的才插入新表
  68. 					if (_table[i]._state == EXIST)
  69. 						newHash.insert(_table[i]._kv);
  70. 				}
  71. 				_table.swap(newHash._table);
  72. 			}
  73.  
  74. 			//插入
  75. 			size_t hashi = ht(kv.first) % _table.size();
  76. 			while (_table[hashi]._state == EXIST)
  77. 			{
  78. 				hashi++;
  79. 				if (hashi == _table.size())//回到0位置
  80. 					hashi = 0;
  81. 			}
  82. 			_table[hashi]._kv = kv;
  83. 			_table[hashi]._state = EXIST;
  84. 			_n++;
  85. 			return true;
  86. 		}
  87.  
  88. 		HashData<const K, V>* Find(const K& key)
  89. 		{
  90. 			HashFunc ht;
  91. 			size_t hashi = ht(key) % _table.size();
  92. 			while (_table[hashi]._state != EMPTY)
  93. 			{
  94. 				if (_table[hashi]._state != DELETE && _table[hashi]._kv.first == key)
  95. 					return (HashData<const K, V>*) & _table[hashi];
  96. 				hashi++;
  97. 				//转回去继续找
  98. 				if (hashi == _table.size())//回到0位置
  99. 					hashi = 0;
  100. 			}
  101. 			return nullptr;
  102. 		}
  103.  
  104. 		bool Erase(const K& key)
  105. 		{
  106. 			HashData<const K, V>* data = Find(key);
  107. 			if (data)
  108. 			{
  109. 				data->_state = DELETE;
  110. 				_n--;
  111. 				return true;
  112. 			}
  113. 			return false;
  114. 		}
  115. 	private:
  116. 		vector<HashData<K, V>> _table;
  117. 		size_t _n = 0;//存储数据的有效个数
  118. 	};
  119. }

哈希表什么情况下扩容？如何扩容？

2.二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：

若当前key与原来key产生相同的哈希地址，则当前key存在该地址后偏移量为（1,-1,2,-2,3,-3...）的二次方地址处
key1：hash(key)+0

key2：hash(key)+1^2

key3：hash(key)+(-1)^2

key4：hash(key)+2^2

key5：hash(key)+(-2)^2

1.4.2开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

开散列的实现：

  1.  
  2. template<class K>
  3. struct DefaultHashFunc
  4. {
  5. 	size_t operator()(const K& key)
  6. 	{
  7. 		return (size_t)key;
  8. 	}
  9. };
  10.  
  11. template<>
  12. struct DefaultHashFunc<string>
  13. {
  14. 	size_t operator()(const string& str)
  15. 	{
  16. 		size_t n = 0;
  17. 		for (auto ch : str)
  18. 		{
  19. 			n *= 131;
  20. 			n += ch;
  21. 		}
  22. 		return n;
  23. 	}
  24. };
  25.  
  26.  
  27. namespace hash_bucket//拉链法——哈希桶
  28. {
  29.  
  30. 	template<class K, class V>
  31. 	struct HashNode
  32. 	{
  33. 		HashNode(const pair<K, V>& kv)
  34. 			:_kv(kv)
  35. 			,_next(nullptr)
  36. 		{}
  37.  
  38. 		pair<K, V> _kv;
  39. 		HashNode<K, V>* _next;
  40. 	};
  41.  
  42. 	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  43. 	class HashTable
  44. 	{
  45. 		typedef HashNode<K, V> Node;
  46. 	public:
  47. 		HashTable()
  48. 		{
  49. 			_table.resize(10, nullptr);
  50. 		}
  51.  
  52. 		~HashTable()
  53. 		{
  54. 			for (int i = 0; i < _table.size(); i++)
  55. 			{
  56. 				Node* cur = _table[i];
  57. 				while (cur)
  58. 				{
  59. 					Node* next = cur->_next;
  60. 					delete cur;
  61. 					cur = next;
  62. 				}
  63. 				_table[i] = nullptr;
  64. 			}
  65. 			_n = 0;
  66. 		}
  67.  
  68. 		bool insert(const pair<K, V>& kv)
  69. 		{
  70. 			//检查是否已经存在
  71. 			if (Find(kv.first))
  72. 				return false;
  73. 			HashFunc ht;
  74. 			size_t fac = (double)_n / _table.size();//负载因子
  75. 			if (fac >= 1)//扩容
  76. 			{
  77. 				size_t newcapacity = _table.size() * 2;
  78. 				HashTable<K, V> newht;
  79. 				newht._table.resize(newcapacity, nullptr);
  80. 				//遍历旧的，链入新的
  81. 				for (int i = 0; i < _table.size(); i++)
  82. 				{
  83. 					Node* cur = _table[i];
  84. 					while (cur)
  85. 					{
  86. 						Node* next = cur->_next;
  87. 						cur->_next = nullptr;//如果用屏蔽的方式，这里要置空
  88. 						size_t hashi = ht(cur->_kv.first) % newcapacity;
  89. 						//头插
  90.  
  91. 						cur->_next = newht._table[hashi];
  92. 						newht._table[hashi] = cur;
  93.  
  94. 						/*if (newht._table[hashi] == nullptr)
  95. 						{
  96. 							newht._table[hashi] = cur;
  97. 						}
  98. 						else
  99. 						{
  100. 							cur->_next = newht._table[hashi];
  101. 							newht._table[hashi] = cur;
  102. 						}*/
  103. 						cur = next;
  104. 					}
  105. 					_table[i] = nullptr;//这里必须要置空，否则不能释放
  106. 				}
  107. 				_table.swap(newht._table);
  108. 			}
  109. 			//头插
  110. 			Node* newnode = new Node(kv);
  111. 			size_t hashi = ht(kv.first) % _table.size();//找第几个桶
  112.  
  113. 			newnode->_next = _table[hashi];
  114. 			_table[hashi] = newnode;
  115.  
  116. 			/*if (_table[hashi] == nullptr)
  117. 			{
  118. 				_table[hashi] = newnode;
  119. 			}
  120. 			else
  121. 			{
  122. 				newnode->_next = _table[hashi];
  123. 				_table[hashi] = newnode;
  125. 			}*/
  126. 			_n++;
  127. 			return true;
  128. 		}
  129.  
  130. 		Node* Find(const K& key)
  131. 		{
  132. 			HashFunc ht;
  133. 			size_t hashi = ht(key) % _table.size();
  134. 			Node* cur = _table[hashi];
  135. 			while (cur)
  136. 			{
  137. 				if (cur->_kv.first == key)
  138. 				{
  139. 					return cur;
  140. 				}
  141. 				cur = cur->_next;
  142. 			}
  143. 			return nullptr;
  144. 		}
  145.  
  146. 		bool Erase(const K& key)
  147. 		{
  148. 			HashFunc ht;
  149. 			size_t hashi = ht(key) % _table.size();
  150. 			Node* prev = nullptr;
  151. 			Node* cur = _table[hashi];
  152. 			while (cur)
  153. 			{
  154. 				if (cur->_kv.first == key)
  155. 				{
  156. 					if (prev == nullptr)
  157. 					{
  158. 						_table[hashi] = cur->_next;
  159. 					}
  160. 					else
  161. 					{
  162. 						prev->_next = cur->_next;
  163. 					}
  164. 					delete cur;
  165. 					return true;
  166.  
  167. 				}
  168. 				else
  169. 				{
  170. 					prev = cur;
  171. 					cur = cur->_next;
  172. 				}
  173. 			}
  174. 			return false;
  175. 		}
  176.  
  177. 		void Print()
  178. 		{
  179. 			for (int i = 0; i < _table.size(); i++)
  180. 			{
  181. 				Node* cur = _table[i];
  182. 				printf("[%d] : ", i);
  183. 				while (cur)
  184. 				{
  185. 					cout << "(" << cur->_kv.first << ":" << cur->_kv.second << ")" << "->";
  186. 					cur = cur->_next;
  187. 				}
  188. 				cout << "NULL" << endl;
  189. 			}
  190. 			cout << endl;
  191. 		}
  192.  
  193. 	private:
  194. 		vector<Node*> _table;
  195. 		size_t _n = 0;//存放有效数据的个数
  196. 	};
  197. }

注意：如果我们要存放的数据是整型，可以使用上面的哈希函数来映射，但是如果我们存的是字符串或自定义类型的数据时，问题就来了，我们如何用除留余数法来计算呢？字符串和自定义类型不可以取模。

我们可以使用仿函数，如果是整型就返回整型，如果是字符串或自定义类型，就将其转换成整型再返回：

  1. template<class K>
  2. struct DefaultHashFunc
  3. {
  4. 	size_t operator()(const K& key)
  5. 	{
  6. 		return (size_t)key;
  7. 	}
  8. };
  9.  
  10. template<>
  11. struct DefaultHashFunc<string>
  12. {
  13. 	size_t operator()(const string& str)
  14. 	{
  15. 		size_t n = 0;
  16. 		for (auto ch : str)
  17. 		{
  18. 			n *= 131;
  19. 			n += ch;
  20. 		}
  21. 		return n;
  22. 	}
  23. };

二、unordered_map和unordered_set的模拟实现

底层哈希桶：

  1. template<class K>
  2. struct DefaultHashFunc
  3. {
  4. 	size_t operator()(const K& key)
  5. 	{
  6. 		return (size_t)key;
  7. 	}
  8. };
  9.  
  10. template<>
  11. struct DefaultHashFunc<string>
  12. {
  13. 	size_t operator()(const string& str)
  14. 	{
  15. 		size_t n = 0;
  16. 		for (auto ch : str)
  17. 		{
  18. 			n *= 131;
  19. 			n += ch;
  20. 		}
  21. 		return n;
  22. 	}
  23. };
  24.  
  25. namespace hash_bucket//拉链法——哈希桶
  26. {
  27.  
  28. 	template<class T>
  29. 	struct HashNode
  30. 	{
  31. 		HashNode(const T& data)
  32. 			:_data(data)
  33. 			,_next(nullptr)
  34. 		{}
  35.  
  36. 		T _data;
  37. 		HashNode<T>* _next;
  38. 	};
  39.  
  40. 	template<class K, class T, class KofT, class HashFunc>
  41. 	class HashTable;//声明一下
  42.  
  43. 	template<class K, class T, class Ref, class Ptr, class KofT, class HashFunc = DefaultHashFunc<K>>
  44. 	struct __HT_Iterator
  45. 	{
  46. 		typedef HashNode<T> Node;
  47. 		typedef __HT_Iterator<K, T, Ref, Ptr, KofT, HashFunc> Self;
  48. 		typedef __HT_Iterator<K, T, T&, T*, KofT, HashFunc> Iterator;
  49.  
  50.  
  51. 		__HT_Iterator(Node* node, const HashTable<K, T, KofT, HashFunc>* pht)
  52. 			:_node(node)
  53. 			,_pht(pht)//_pht为const修饰的指针
  54. 		{}
  55.  
  56. 		//当此时这个类是普通迭代器类时，这个函数为拷贝构造
  57. 		//当此时这个类是const迭代器类时，这个函数为构造
  58. 		__HT_Iterator(const Iterator& it)
  59. 			:_node(it._node)
  60. 			,_pht(it._pht)
  61. 		{}
  62.  
  63.  
  64. 		Ref operator*()
  65. 		{
  66. 			return _node->_data;
  67. 		}
  68.  
  69. 		Ptr operator->()
  70. 		{
  71. 			return &_node->_data;
  72. 		}
  73.  
  74. 		Self operator++()
  75. 		{
  76. 			
  77. 			//走这个桶里的下一个节点
  78. 			if (_node->_next)
  79. 			{
  80. 				_node = _node->_next;
  81. 			}
  82. 			//找其他桶
  83. 			else
  84. 			{
  85. 				KofT kot;
  86. 				HashFunc ht;
  87. 				size_t hashi = ht(kot(_node->_data)) % _pht->_table.size();
  88. 				++hashi;//找下一个桶
  89. 				while (hashi < _pht->_table.size())
  90. 				{
  91. 					if (_pht->_table[hashi])
  92. 					{
  93. 						_node = _pht->_table[hashi];
  94. 						return *this;
  95. 					}
  96. 					else
  97. 					{
  98. 						++hashi;
  99. 					}
  100. 				}
  101. 				_node = nullptr;
  102. 			}
  103. 			return *this;
  104. 		}
  105.  
  106. 		bool operator!=(const Self& it) const 
  107. 		{
  108. 			return _node != it._node;
  109. 		}
  110. 		bool operator==(const Self& it) const
  111. 		{
  112. 			return _node == it._node;
  113. 		}
  114.  
  115.  
  116. 		Node* _node;
  117. 		const HashTable<K, T, KofT, HashFunc>* _pht;
  118.  
  119. 	};
  120.  
  121. 	template<class K, class T, class KofT, class HashFunc = DefaultHashFunc<K>>
  122. 	class HashTable
  123. 	{
  124. 		//友元声明
  125. 		template<class K, class T, class Ref, class Ptr, class KofT, class HashFunc>
  126. 		friend struct __HT_Iterator; 
  127.  
  128. 		typedef HashNode<T> Node;
  129. 	public:
  130. 		typedef __HT_Iterator<K, T, T&, T*, KofT, HashFunc> iterator;
  131. 		typedef __HT_Iterator<K, T, const T&, const T*, KofT, HashFunc> const_iterator;
  132.  
  133.  
  134. 		iterator begin()
  135. 		{
  136. 			for (int i = 0; i < _table.size(); i++)
  137. 			{
  138. 				Node* cur = _table[i];
  139. 				if (cur)
  140. 					return iterator(cur, this);
  141. 			}
  142. 			return iterator(nullptr, this);
  143. 		}
  144.  
  145. 		iterator end()
  146. 		{
  147. 			return iterator(nullptr, this);
  148. 		}
  149.  
  150. 		const_iterator begin() const
  151. 		{
  152. 			for (int i = 0; i < _table.size(); i++)
  153. 			{
  154. 				Node* cur = _table[i];
  155. 				if (cur)
  156. 					return const_iterator(cur, this);
  157. 			}
  158. 			return const_iterator(nullptr, this);
  159. 		}
  160.  
  161. 		const_iterator end() const
  162. 		{
  163. 			return const_iterator(nullptr, this);//这里的this是const修饰的，所以上面的迭代器里的构造的哈希表参数要设置成const
  164. 		}
  165.  
  166. 		HashTable()
  167. 		{
  168. 			_table.resize(10, nullptr);
  169. 		}
  170.  
  171. 		~HashTable()
  172. 		{
  173. 			for (int i = 0; i < _table.size(); i++)
  174. 			{
  175. 				Node* cur = _table[i];
  176. 				while (cur)
  177. 				{
  178. 					Node* next = cur->_next;
  179. 					delete cur;
  180. 					cur = next;
  181. 				}
  182. 				_table[i] = nullptr;
  183. 			}
  184. 			_n = 0;
  185. 		}
  186.  
  187. 		pair<iterator, bool> insert(const T& data)
  188. 		{
  189. 			KofT kot;
  190. 			//检查是否已经存在
  191. 			iterator it = Find(kot(data));
  192. 			if (it != end())//找到了就返回此刻的pair
  193. 				return make_pair(it ,false);
  194. 			HashFunc ht;
  195. 			size_t fac = (double)_n / _table.size();//负载因子
  196. 			if (fac >= 1)//扩容
  197. 			{
  198. 				size_t newcapacity = _table.size() * 2;
  199. 				HashTable<K, T, KofT> newht;
  200. 				newht._table.resize(newcapacity, nullptr);
  201. 				//遍历旧的，链入新的
  202. 				for (int i = 0; i < _table.size(); i++)
  203. 				{
  204. 					Node* cur = _table[i];
  205. 					while (cur)
  206. 					{
  207. 						Node* next = cur->_next;
  208. 						size_t hashi = ht(kot(cur->_data)) % newcapacity;
  209. 						
  210. 						//头插
  211. 						cur->_next = newht._table[hashi];
  212. 						newht._table[hashi] = cur;
  213.  
  214. 						cur = next;
  215. 					}
  216. 					_table[i] = nullptr;//这里必须要置空，否则不能释放
  217. 				}
  218. 				_table.swap(newht._table);
  219. 			}
  220. 			//头插
  221. 			Node* newnode = new Node(data);
  222. 			size_t hashi = ht(kot(data)) % _table.size();//找第几个桶
  223.  
  224. 			newnode->_next = _table[hashi];
  225. 			_table[hashi] = newnode;
  226.  
  227. 			_n++;
  228.  
  229. 			return make_pair(iterator(newnode, this), true);
  230. 		}
  231.  
  232. 		iterator Find(const K& key)
  233. 		{
  234. 			KofT kot;
  235. 			HashFunc ht;
  236. 			size_t hashi = ht(key) % _table.size();
  237. 			Node* cur = _table[hashi];
  238. 			while (cur)
  239. 			{
  240. 				if (kot(cur->_data) == key)
  241. 				{
  242. 					return iterator(cur, this);
  243. 				}
  244. 				cur = cur->_next;
  245. 			}
  246. 			return end();
  247. 		}
  248.  
  249. 		bool Erase(const K& key)
  250. 		{
  251. 			KofT kot;
  252. 			HashFunc ht;
  253. 			size_t hashi = ht(key) % _table.size();
  254. 			Node* prev = nullptr;
  255. 			Node* cur = _table[hashi];
  256. 			while (cur)
  257. 			{
  258. 				if (kot(cur->_data) == key)
  259. 				{
  260. 					if (prev == nullptr)
  261. 					{
  262. 						_table[hashi] = cur->_next;
  263. 					}
  264. 					else
  265. 					{
  266. 						prev->_next = cur->_next;
  267. 					}
  268. 					delete cur;
  269. 					_n--;
  270. 					return true;
  271.  
  272. 				}
  273. 				else
  274. 				{
  275. 					prev = cur;
  276. 					cur = cur->_next;
  277. 				}
  278. 			}
  279. 			return false;
  280. 		}
  281.  
  282. 		void Print()
  283. 		{
  284. 			for (int i = 0; i < _table.size(); i++)
  285. 			{
  286. 				Node* cur = _table[i];
  287. 				printf("[%d] : ", i);
  288. 				while (cur)
  289. 				{
  290. 					cout << "(" << cur->_kv.first << ":" << cur->_kv.second << ")" << "->";
  291. 					cur = cur->_next;
  292. 				}
  293. 				cout << "NULL" << endl;
  294. 			}
  295. 			cout << endl;
  296. 		}
  297.  
  298. 		size_t count(const K& key)
  299. 		{
  300. 			if (Find(key) != end())
  301. 				return 1;
  302. 			else
  303. 				return 0;
  304. 		}
  305. 		size_t size()
  306. 		{
  307. 			return _n;
  308. 		}
  309.  
  310. 		bool empty()
  311. 		{
  312. 			return _n == 0;
  313. 		}
  314.  
  315. 	private:
  316. 		vector<Node*> _table;
  317. 		size_t _n = 0;//存放有效数据的个数
  318. 	};
  319. }

封装unordered_map和unordered_set

  1. template<class K, class V>
  2. struct mapKofT
  3. {
  4. 	K operator()(const pair<K, V>& kv)
  5. 	{
  6. 		return kv.first;
  7. 	}
  8. };
  9.  
  10. template<class K, class V>
  11. class Unordered_map
  12. {
  13. public:
  14. 	typedef typename hash_bucket::HashTable<K, pair<const K, V>, mapKofT<K, V>>::iterator iterator;
  15. 	typedef typename hash_bucket::HashTable<K, pair<const K, V>, mapKofT<K, V>>::const_iterator const_iterator;
  16.  
  17. 	pair<iterator, bool> insert(const pair<K, V>& kv)
  18. 	{
  19. 		return _ht.insert(kv);
  20. 	}
  21.  
  22. 	V& operator[](const K& key)
  23. 	{
  24. 		return _ht.insert(make_pair(key, V())).first->second;
  25. 	}
  26. 	bool Erase(const K& key)
  27. 	{
  28. 		return _ht.Erase(key);
  29. 	}
  30.  
  31. 	iterator find(const K& key)
  32. 	{
  33. 		return _ht.Find(key);
  34. 	}
  35.  
  36. 	size_t count(const K& key)
  37. 	{
  38. 		return _ht.count(key);
  39. 	}
  40. 	size_t size()
  41. 	{
  42. 		return _ht.size();
  43. 	}
  44. 	bool empty()
  45. 	{
  46. 		return _ht.empty();
  47. 	}
  48.  
  49. 	iterator begin()
  50. 	{
  51. 		return _ht.begin();
  52. 	}
  53.  
  54. 	iterator end()
  55. 	{
  56. 		return _ht.end();
  57. 	}
  58. 	const_iterator begin() const
  59. 	{
  60. 		return _ht.begin();
  61. 	}
  62.  
  63. 	const_iterator end() const
  64. 	{
  65. 		return _ht.end();
  66. 	}
  67.  
  68. private:
  69. 	hash_bucket::HashTable<K, pair<const K, V>, mapKofT<K, V>> _ht;
  70. };
  1. template<class K>
  2. struct setKofT
  3. {
  4. 	K operator()(const K& key)
  5. 	{
  6. 		return key;
  7. 	}
  8. };
  9.  
  10. template<class K>
  11. class Unordered_set
  12. {
  13. public:
  14. 	typedef typename hash_bucket::HashTable<K, K, setKofT<K>>::const_iterator iterator;
  15. 	typedef typename hash_bucket::HashTable<K, K, setKofT<K>>::const_iterator const_iterator;
  16.  
  17. 	pair<iterator, bool> insert(const K& key)
  18. 	{
  19. 		return _ht.insert(key);
  20. 	}
  21. 	
  22. 	bool Erase(const K& key)
  23. 	{
  24. 		return _ht.Erase(key);
  25. 	}
  26. 	size_t size()
  27. 	{
  28. 		return _ht.size();
  29. 	}
  30. 	bool empty()
  31. 	{
  32. 		return _ht.empty();
  33. 	}
  34. 	size_t count(const K& key)
  35. 	{
  36. 		return _ht.count(key);
  37. 	}
  38. 	iterator find(const K& key)
  39. 	{
  40. 		return _ht.Find(key);
  41. 	}
  42.  
  43. 	iterator begin() const
  44. 	{
  45. 		return _ht.begin();
  46. 	}
  47.  	iterator end() const
  48. 	{
  49. 		return _ht.end();
  50. 	}
  51.  
  52. private:
  53. 	hash_bucket::HashTable<K, K, setKofT<K>> _ht;
  54. };
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/933034?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号