• 【C++】封装unordered_map和unordered_set（用哈希桶实现）

    前言：
           前面我们学习了unordered_map和unordered_set容器，比较了他们和map、set的查找效率，我们发现他们的效率比map、set高，进而我们研究他们的底层是由哈希实现。哈希是一种直接映射的方式，所以查找的效率很快。与学习红黑树和map、set的思路一样，我们现在学完了unordered_map和unordered_set，本章将模拟实现底层结构来封装该容器！

        作者建议在阅读本章前，可以先去看一下前面的红黑树封装map和set——红黑树封装map和set

    这两篇文章都重在强调泛型编程的思想，上一篇由于是初认识，作者讲解的会更详细一点~

    目录

    （一）如何复用一个哈希桶

    1、结点的定义：

    2、两个容器各自的模板参数类型​编辑

    3、改造哈希桶

    （二）哈希桶的迭代器的模拟实现

    1、begin()和end()的模拟实现

    2、operator*和operator->及operator!=和operator==的模拟实现 

    3、operator ++的模拟实现

    （三）迭代器和改造哈希桶的总代码

    （四）封装unordered_map和unordered_set

    （一）如何复用一个哈希桶

    我们学习过知道，unordered_map和unordered_set容器存放的结点并不一样，为了让它得到复用，我们就需要对哈希桶进行改造，将哈希桶改造的更加泛型一点，既符合Key模型，也符合Key_Value模型。

    1、结点的定义：

     所以我们这里还是和封装map和set时一样，无论是Key还是Key_Value，都用一个类型T来接收，这里高维度的泛型哈希表中，实现还是用的是Kye_Value模型，K是不能省略的，同样的查找和删除要用，故我们可以引出两个容器各自模板参数类型。

    2、两个容器各自的模板参数类型

    如何取到想要的数据：

    • 我们给每个容器配一个仿函数
    • 各传不同的仿函数，拿到想要的不同的数据

    同时我们再给每个容器配一个哈希函数。

    3、改造哈希桶

    通过上面1和2，我们可以把各自存放的数据泛化成data：

    这样我们哈希桶的模板参数算是完成了

    • 哈希函数我们可以自由选择并传
    • 仿函数在各自容器的封装中实现，用于比较时我们可以取出各自容器想要的数据

    我们把上一篇文章封装的哈希桶拿来改造：

    1. //K --> 键值Key，T --> 数据
    2. //unordered_map ->HashTable<K, pair<K, V>, MapKeyOfT> _ht;
    3. //unordered_set ->HashTable<K, K, SetKeyOfT> _ht;
    4. template<class K, class T, class KeyOfT, class HashFunc>
    5. class HashTable
    6. {
    7. 	template<class K, class T, class KeyOfT, class HashFunc>
    8. 	friend class __HTIterator;
    9.  
    10. 	typedef HashNode<T> Node;
    11. public:
    12. 	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
    13.  
    14. 	iterator begin()
    15. 	{
    16. 		for (size_t i = 0; i < _tables.size(); i++)
    17. 		{
    18. 			Node* cur = _tables[i];
    19. 			if (cur)
    20. 			{
    21. 				return iterator(cur, this);
    22. 			}
    23. 		}
    24.  
    25. 		return end();
    26. 	}
    27.  
    28. 	iterator end()
    29. 	{
    30. 		return iterator(nullptr, this);
    31. 	}
    32.  
    33. 	~HashTable()
    34. 	{
    35. 		for (size_t i = 0; i < _tables.size(); i++)
    36. 		{
    37. 			Node* cur = _tables[i];
    38. 			while (cur)
    39. 			{
    40. 				Node* next = cur->_next;
    41. 				delete cur;
    42. 				cur = next;
    43. 			}
    44.  
    45. 			_tables[i] = nullptr;
    46. 		}
    47. 	}
    48.  
    49. 	size_t GetNextPrime(size_t prime)
    50. 	{
    51. 		const int PRIMECOUNT = 28;
    52. 		static const size_t primeList[PRIMECOUNT] =
    53. 		{
    54. 			53,         97,         193,       389,       769,
    55. 			1543,       3079,       6151,      12289,     24593,
    56. 			49157,      98317,      196613,    393241,    786433,
    57. 			1572869,    3145739,    6291469,   12582917,  25165843,
    58. 			50331653,   100663319,  201326611, 402653189, 805306457,
    59. 			1610612741, 3221225473, 4294967291
    60. 		};
    61.  
    62. 		//获取比prime大那一个素数
    63. 		size_t i = 0;
    64. 		for (i = 0; i < PRIMECOUNT; i++)
    65. 		{
    66. 			if (primeList[i] > prime)
    67. 				return primeList[i];
    68. 		}
    69.  
    70. 		return primeList[i];
    71. 	}
    72.  
    73. 	pair<iterator, bool> Insert(const T& data)
    74. 	{
    75. 		HashFunc hf;
    76. 		KeyOfT kot;
    77.  
    78. 		iterator pos = Find(kot(data));
    79. 		if (pos != end())
    80. 		{
    81. 			return make_pair(pos, false);
    82. 		}
    83.  
    84. 		//负载因子 == 1 扩容 -- 平均每个桶挂一个结点
    85. 		if (_tables.size() == _n)
    86. 		{
    87. 			//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    88. 			size_t newSize = GetNextPrime(_tables.size());
    89.  
    90. 			if (newSize != _tables.size())
    91. 			{
    92. 				vector<Node*> newTable;
    93. 				newTable.resize(newSize, nullptr);
    94.  
    95. 				//遍历旧表
    96. 				for (size_t i = 0; i < _tables.size(); i++)
    97. 				{
    98. 					Node* cur = _tables[i];
    99.  
    100. 					//再对每个桶挨个遍历
    101. 					while (cur)
    102. 					{
    103. 						Node* next = cur->_next;
    104. 						size_t hashi = hf(kot(cur->_data)) % newSize;
    105.  
    106. 						//转移到新的表中
    107. 						cur->_next = newTable[hashi];
    108. 						newTable[hashi] = cur;
    109. 						cur = next;
    110. 					}
    111.  
    112. 					//将原表置空
    113. 					_tables[i] = nullptr;
    114. 				}
    115. 				newTable.swap(_tables);
    116. 			}
    117. 			
    118. 		}
    119.  
    120. 		size_t hashi = hf(kot(data));
    121. 		hashi %= _tables.size();
    122.  
    123. 		//头插到对应的桶即可
    124. 		Node* newnode = new Node(data);
    125. 		newnode->_next = _tables[hashi];
    126. 		_tables[hashi] = newnode;
    127.  
    128. 		//有效数据加一
    129. 		_n++;
    130.  
    131. 		return make_pair(iterator(newnode, this), true);
    132. 	}
    133.  
    134. 	iterator Find(const K& key)
    135. 	{
    136. 		if (_tables.size() == 0)
    137. 		{
    138. 			return iterator(nullptr, this);
    139. 		}
    140.  
    141. 		KeyOfT kot;
    142. 		HashFunc hf;
    143. 		size_t hashi = hf(key);
    144. 		//size_t hashi = HashFunc()(key);
    145.  
    146. 		hashi %= _tables.size();
    147. 		Node* cur = _tables[hashi];
    148.  
    149. 		//找到指定的桶之后，顺着单链表挨个找
    150. 		while (cur)
    151. 		{
    152. 			if (kot(cur->_data) == key)
    153. 			{
    154. 				return iterator(cur, this);
    155. 			}
    156.  
    157. 			cur = cur->_next;
    158. 		}
    159.  
    160. 		//没找到返回空
    161. 		return iterator(nullptr, this);
    162. 	}
    163.  
    164. 	bool Erase(const K& key)
    165. 	{
    166. 		if (_tables.size() == 0)
    167. 		{
    168. 			return false;
    169. 		}
    170.  
    171. 		HashFunc hf;
    172. 		KeyOfT kot;
    173. 		size_t hashi = hf(key);
    174. 		hashi %= _tables.size();
    175.  
    176. 		//单链表删除结点
    177. 		Node* prev = nullptr;
    178. 		Node* cur = _tables[hashi];
    179. 		while (cur)
    180. 		{
    181. 			if (kot(cur->_data) == key)
    182. 			{
    183. 				//头删
    184. 				if (prev == nullptr)
    185. 				{
    186. 					_tables[hashi] = cur->_next;
    187. 				}
    188. 				else
    189. 				{
    190. 					prev->_next = cur->_next;
    191. 				}
    192.  
    193. 				delete cur;
    194.  
    195. 				return true;
    196. 			}
    197.  
    198. 			prev = cur;
    199. 			cur = cur->_next;
    200. 		}
    201.  
    202. 		return false;
    203. 	}
    204. private:
    205. 	//指针数组
    206. 	vector<Node*> _tables;
    207. 	size_t _n = 0;
    208. };

    主要改造的地方就是上述所注意的地方：

    • 比较时需要调用各自的仿函数
    • 调用外部传的哈希函数

    还有对扩容的二次思考：

    研究表明：除留余数法，最好模一个素数

    • 通过查STL官方库我们也发现，其提供了一个取素数的函数
    • 所以我们也提供了一个，直接拷贝过来
      • 这样我们在扩容时就可以每次给素数个桶
      • 在扩容时加了一条判断语句是为了防止素数值太大，过分扩容容易直接把空间(堆)干崩了

    （二）哈希桶的迭代器的模拟实现

    1、begin()和end()的模拟实现

    • 以第一个桶中第一个不为空的结点为整个哈希桶的开始结点
    • 以空结点为哈希桶的结束结点

    2、operator*和operator->及operator!=和operator==的模拟实现 

    这两组和之前实现的一模一样，大家自行理解。

    3、operator ++的模拟实现

    注：

    • 这里要在哈希桶的类外面访问其私有成员
    • 我们要搞一个友元类
    • 迭代器类是哈希桶类的朋友
    • 这样就可以访问了

     

    思路：

    • 判断一个桶中的数据是否遍历完
    • 如果所在的桶没有遍历完，在该桶中返回下一个结点指针
    • 如果所在的桶遍历完了，进入下一个桶
    • 判断下一个桶是否为空
    • 非空返回桶中第一个节点
    • 空的话就遍历一个桶
    • 后置++和之前一眼老套路，不赘述

    注意：

    unordered_map和unordered_set是不支持反向迭代器的，从底层结构我们也能很好的理解（单链表找不了前驱）所以不支持实现迭代器的operator- -

    最后注意一点，我们需要知道哈希桶大小，所以不仅要传结点地址，还要传一个哈希桶，这样才能知道其大小，除此，由于哈希桶改造在后面，所以我们要在前面声明一下：

    （三）迭代器和改造哈希桶的总代码

    1. #include<vector>
    2. #include<string>
    3. #include<iostream>
    4. using namespace std;
    5.  
    6. template<class K>
    7. struct DefaultHash
    8. {
    9. 	size_t operator()(const K& key)
    10. 	{
    11. 		return (size_t)key;
    12. 	}
    13. };
    14.  
    15. template<>
    16. struct DefaultHash<string>
    17. {
    18. 	size_t operator()(const string& key)
    19. 	{
    20. 		//BKDR
    21. 		size_t hash = 0;
    22. 		for (auto ch : key)
    23. 		{
    24. 			hash = hash * 131 + ch;
    25. 		}
    26.  
    27. 		return hash;
    28. 	}
    29. };
    30.  
    31. namespace Bucket
    32. {
    33. 	template<class T>
    34. 	struct HashNode
    35. 	{
    36. 		T _data;
    37. 		HashNode<T>* _next;
    38.  
    39. 		HashNode(const T& data)
    40. 			:_data(data)
    41. 			, _next(nullptr)
    42. 		{}
    43. 	};
    44.  
    45. 	template<class K, class T, class KeyOfT, class HashFunc>
    46. 	class HashTable;
    47.  
    48. 	//哈希桶的迭代器
    49. 	template<class K, class T, class KeyOfT, class HashFunc>
    50. 	class __HTIterator
    51. 	{
    52. 		typedef HashNode<T> Node;
    53. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;
    54. 	public:
    55. 		Node* _node;
    56.  
    57. 		__HTIterator() {};
    58.  
    59. 		//编译器的原则是向上查找（定义必须在前面，否则必须先声明）
    60. 		HashTable<K, T, KeyOfT, HashFunc>* _pht;
    61.  
    62. 		__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
    63. 			:_node(node)
    64. 			, _pht(pht)
    65. 		{}
    66.  
    67. 		Self& operator++()
    68. 		{
    69. 			if (_node->_next)
    70. 			{
    71. 				_node = _node->_next;
    72. 			}
    73. 			else//当前桶已经走完了，要走下一个桶
    74. 			{
    75. 				KeyOfT kot;
    76. 				HashFunc hf;
    77. 				size_t hashi = hf(kot(_node->_data)) % _pht->_tables.size();
    78. 				hashi++;
    79.  
    80. 				//找下一个不为空的桶 -- 访问到了哈希表中私有的成员（友元）
    81. 				for (; hashi < _pht->_tables.size(); hashi++)
    82. 				{
    83. 					if (_pht->_tables[hashi])
    84. 					{
    85. 						_node = _pht->_tables[hashi];
    86. 						break;
    87. 					}
    88. 				}
    89.  
    90. 				//没有找到不为空的桶，用nullptr去做end标识
    91. 				if (hashi == _pht->_tables.size())
    92. 				{
    93. 					_node = nullptr;
    94. 				}
    95. 			}
    96.  
    97. 			return *this;
    98. 		}
    99.  
    100. 		T& operator*()
    101. 		{
    102. 			return _node->_data;
    103. 		}
    104.  
    105. 		T* operator->()
    106. 		{
    107. 			return &_node->_data;
    108. 		}
    109.  
    110. 		bool operator!=(const Self& s) const
    111. 		{
    112. 			return _node != s._node;
    113. 		}
    114.  
    115. 		bool operator==(const Self& s) const
    116. 		{
    117. 			return _node == s._node;
    118. 		}
    119. 	};
    120.  
    121. 	//K --> 键值Key，T --> 数据
    122. 	//unordered_map ->HashTable<K, pair<K, V>, MapKeyOfT> _ht;
    123. 	//unordered_set ->HashTable<K, K, SetKeyOfT> _ht;
    124. 	template<class K, class T, class KeyOfT, class HashFunc>
    125. 	class HashTable
    126. 	{
    127. 		template<class K, class T, class KeyOfT, class HashFunc>
    128. 		friend class __HTIterator;
    129.  
    130. 		typedef HashNode<T> Node;
    131. 	public:
    132. 		typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;
    133.  
    134. 		iterator begin()
    135. 		{
    136. 			for (size_t i = 0; i < _tables.size(); i++)
    137. 			{
    138. 				Node* cur = _tables[i];
    139. 				if (cur)
    140. 				{
    141. 					return iterator(cur, this);
    142. 				}
    143. 			}
    144.  
    145. 			return end();
    146. 		}
    147.  
    148. 		iterator end()
    149. 		{
    150. 			return iterator(nullptr, this);
    151. 		}
    152.  
    153. 		~HashTable()
    154. 		{
    155. 			for (size_t i = 0; i < _tables.size(); i++)
    156. 			{
    157. 				Node* cur = _tables[i];
    158. 				while (cur)
    159. 				{
    160. 					Node* next = cur->_next;
    161. 					delete cur;
    162. 					cur = next;
    163. 				}
    164.  
    165. 				_tables[i] = nullptr;
    166. 			}
    167. 		}
    168.  
    169. 		size_t GetNextPrime(size_t prime)
    170. 		{
    171. 			const int PRIMECOUNT = 28;
    172. 			static const size_t primeList[PRIMECOUNT] =
    173. 			{
    174. 				53,         97,         193,       389,       769,
    175. 				1543,       3079,       6151,      12289,     24593,
    176. 				49157,      98317,      196613,    393241,    786433,
    177. 				1572869,    3145739,    6291469,   12582917,  25165843,
    178. 				50331653,   100663319,  201326611, 402653189, 805306457,
    179. 				1610612741, 3221225473, 4294967291
    180. 			};
    181.  
    182. 			//获取比prime大那一个素数
    183. 			size_t i = 0;
    184. 			for (i = 0; i < PRIMECOUNT; i++)
    185. 			{
    186. 				if (primeList[i] > prime)
    187. 					return primeList[i];
    188. 			}
    189.  
    190. 			return primeList[i];
    191. 		}
    192.  
    193. 		pair<iterator, bool> Insert(const T& data)
    194. 		{
    195. 			HashFunc hf;
    196. 			KeyOfT kot;
    197.  
    198. 			iterator pos = Find(kot(data));
    199. 			if (pos != end())
    200. 			{
    201. 				return make_pair(pos, false);
    202. 			}
    203.  
    204. 			//负载因子 == 1 扩容 -- 平均每个桶挂一个结点
    205. 			if (_tables.size() == _n)
    206. 			{
    207. 				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
    208. 				size_t newSize = GetNextPrime(_tables.size());
    209.  
    210. 				if (newSize != _tables.size())
    211. 				{
    212. 					vector<Node*> newTable;
    213. 					newTable.resize(newSize, nullptr);
    214.  
    215. 					//遍历旧表
    216. 					for (size_t i = 0; i < _tables.size(); i++)
    217. 					{
    218. 						Node* cur = _tables[i];
    219.  
    220. 						//再对每个桶挨个遍历
    221. 						while (cur)
    222. 						{
    223. 							Node* next = cur->_next;
    224. 							size_t hashi = hf(kot(cur->_data)) % newSize;
    225.  
    226. 							//转移到新的表中
    227. 							cur->_next = newTable[hashi];
    228. 							newTable[hashi] = cur;
    229. 							cur = next;
    230. 						}
    231.  
    232. 						//将原表置空
    233. 						_tables[i] = nullptr;
    234. 					}
    235. 					newTable.swap(_tables);
    236. 				}
    237.  
    238. 			}
    239.  
    240. 			size_t hashi = hf(kot(data));
    241. 			hashi %= _tables.size();
    242.  
    243. 			//头插到对应的桶即可
    244. 			Node* newnode = new Node(data);
    245. 			newnode->_next = _tables[hashi];
    246. 			_tables[hashi] = newnode;
    247.  
    248. 			//有效数据加一
    249. 			_n++;
    250.  
    251. 			return make_pair(iterator(newnode, this), true);
    252. 		}
    253.  
    254. 		iterator Find(const K& key)
    255. 		{
    256. 			if (_tables.size() == 0)
    257. 			{
    258. 				return iterator(nullptr, this);
    259. 			}
    260.  
    261. 			KeyOfT kot;
    262. 			HashFunc hf;
    263. 			size_t hashi = hf(key);
    264. 			//size_t hashi = HashFunc()(key);
    265.  
    266. 			hashi %= _tables.size();
    267. 			Node* cur = _tables[hashi];
    268.  
    269. 			//找到指定的桶之后，顺着单链表挨个找
    270. 			while (cur)
    271. 			{
    272. 				if (kot(cur->_data) == key)
    273. 				{
    274. 					return iterator(cur, this);
    275. 				}
    276.  
    277. 				cur = cur->_next;
    278. 			}
    279.  
    280. 			//没找到返回空
    281. 			return iterator(nullptr, this);
    282. 		}
    283.  
    284. 		bool Erase(const K& key)
    285. 		{
    286. 			if (_tables.size() == 0)
    287. 			{
    288. 				return false;
    289. 			}
    290.  
    291. 			HashFunc hf;
    292. 			KeyOfT kot;
    293. 			size_t hashi = hf(key);
    294. 			hashi %= _tables.size();
    295.  
    296. 			//单链表删除结点
    297. 			Node* prev = nullptr;
    298. 			Node* cur = _tables[hashi];
    299. 			while (cur)
    300. 			{
    301. 				if (kot(cur->_data) == key)
    302. 				{
    303. 					//头删
    304. 					if (prev == nullptr)
    305. 					{
    306. 						_tables[hashi] = cur->_next;
    307. 					}
    308. 					else
    309. 					{
    310. 						prev->_next = cur->_next;
    311. 					}
    312.  
    313. 					delete cur;
    314.  
    315. 					return true;
    316. 				}
    317.  
    318. 				prev = cur;
    319. 				cur = cur->_next;
    320. 			}
    321.  
    322. 			return false;
    323. 		}
    324. 	private:
    325. 		//指针数组
    326. 		vector<Node*> _tables;
    327. 		size_t _n = 0;
    328. 	};
    329. }

    （四）封装unordered_map和unordered_set

    有了上面的哈希桶的改装，我们这里的对map和set的封装就显得很得心应手了。

    unordered_map的封装：

    1. #include "HashTable.h"
    2.  
    3. namespace zc
    4. {
    5. 	template<class K, class V, class HashFunc = DefaultHash<K>>
    6. 	class unordered_map
    7. 	{
    8. 		struct MapKeyOfT
    9. 		{
    10. 			const K& operator()(const pair<K, V>& kv)
    11. 			{
    12. 				return kv.first;
    13. 			}
    14. 		};
    15. 	public:
    16. 		typedef typename Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc>::iterator iterator;
    17.  
    18. 		iterator begin()
    19. 		{
    20. 			return _ht.begin();
    21. 		}
    22.  
    23. 		iterator end()
    24. 		{
    25. 			return _ht.end();
    26. 		}
    27.  
    28. 		pair<iterator, bool> insert(const pair<K, V>& kv)
    29. 		{
    30. 			return _ht.Insert(kv);
    31. 		}
    32.  
    33. 		iterator find(const K& key)
    34. 		{
    35. 			return _ht.Find(key);
    36. 		}
    37.  
    38. 		bool erase(const K& key)
    39. 		{
    40. 			return _ht.Erase(key);
    41. 		}
    42.  
    43. 		V& operator[](const K& key)
    44. 		{
    45. 			pair<iterator, bool> ret = insert(make_pair(key, V()));
    46. 			return ret.first->second;
    47. 		}
    48.  
    49. 	private:
    50. 		Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;
    51. 	};
    52.  
    53. 	void test_map()
    54. 	{
    55. 		unordered_map<string, string> dict;
    56. 		dict.insert(make_pair("sort", "排序"));
    57. 		dict.insert(make_pair("left", "左边"));
    58. 		dict.insert(make_pair("left", "下面"));
    59. 		dict["string"];
    60. 		dict["left"] = "上面";
    61. 		dict["string"] = "字符串";
    62.  
    63. 		unordered_map<string, string>::iterator it = dict.begin();
    64. 		while (it != dict.end())
    65. 		{
    66. 			cout << it->first << " " << it->second << endl;
    67. 			++it;
    68. 		}
    69. 		cout << endl;
    70.  
    71. 		for (auto e : dict)
    72. 		{
    73. 			cout << e.first << " " << e.second << endl;
    74. 		}
    75. 	}
    76.  
    77. }

    这里unordered_map中的operator[ ]我们知道其原理之后，模拟实现就非常方便，直接调用插入函数，控制好参数和返回值即可。

    对unordered_set的封装：

    1. #include "HashTable.h"
    2.  
    3. #include "HashTable.h"
    4.  
    5. namespace zc
    6. {
    7. 	template<class K, class HashFunc = DefaultHash<K>>
    8. 	class unordered_set
    9. 	{
    10. 		
    11. 		struct SetKeyOfT
    12. 		{
    13. 			const K& operator()(const K& key)
    14. 			{
    15. 				return key;
    16. 			}
    17. 		};
    18.  
    19. 	public:
    20. 		//2.48
    21. 		typedef typename Bucket::HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
    22.  
    23. 		iterator begin()
    24. 		{
    25. 			return _ht.begin();
    26. 		}
    27.  
    28. 		iterator end()
    29. 		{
    30. 			return _ht.end();
    31. 		}
    32.  
    33. 		pair<iterator, bool> insert(const K& key)
    34. 		{
    35. 			return _ht.Insert(key);
    36. 		}
    37.  
    38. 		iterator find(const K& key)
    39. 		{
    40. 			return _ht.Find(key);
    41. 		}
    42.  
    43. 		bool erase(const K& key)
    44. 		{
    45. 			return _ht.Erase(key);
    46. 		}
    47. 	private:
    48. 		Bucket::HashTable<K, K, SetKeyOfT, HashFunc> _ht;
    49. 	};
    50.  
    51. 	struct Date
    52. 	{
    53. 		Date(int year = 1, int month = 1, int day = 1)
    54. 			:_year(year)
    55. 			, _month(month)
    56. 			, _day(day)
    57. 		{}
    58.  
    59. 		bool operator==(const Date& d) const
    60. 		{
    61. 			return _year == d._year
    62. 				&& _month == d._month
    63. 				&& _day == d._day;
    64. 		}
    65.  
    66. 		int _year;
    67. 		int _month;
    68. 		int _day;
    69. 	};
    70.  
    71. 	struct DateHash
    72. 	{
    73. 		size_t operator()(const Date& d)
    74. 		{
    75. 			//return d._year + d._month + d._day;
    76. 			size_t hash = 0;
    77. 			hash += d._year;
    78. 			hash *= 131;
    79. 			hash += d._month;
    80. 			hash *= 1313;
    81. 			hash += d._day;
    82.  
    83. 			//cout << hash << endl;
    84.  
    85. 			return hash;
    86. 		}
    87. 	};
    88.  
    89. 	void test_set()
    90. 	{
    91. 		unordered_set<int> s;
    92. 		//set<int> s;
    93. 		s.insert(2);
    94. 		s.insert(3);
    95. 		s.insert(1);
    96. 		s.insert(2);
    97. 		s.insert(5);
    98. 		s.insert(12);
    99.  
    100. 		unordered_set<int>::iterator it = s.begin();
    101. 		//auto it = s.begin();
    102. 		while (it != s.end())
    103. 		{
    104. 			cout << *it << " ";
    105. 			++it;
    106. 		}
    107. 		cout << endl;
    108.  
    109. 		for (auto e : s)
    110. 		{
    111. 			cout << e << " ";
    112. 		}
    113. 		cout << endl;
    114.  
    115. 		unordered_set<Date, DateHash> sd;
    116. 		sd.insert(Date(2022, 3, 4));
    117. 		sd.insert(Date(2022, 4, 3));
    118. 	}
    119. }

    最后大家可以利用代码中给的测试函数进行测试！

    感谢你的阅读！

  • 相关阅读:
    小程序怎么做？个人小程序怎么做？新手教程
    Kafka高性能
    【云原生】Kubernetes----Metrics-Server组件与HPA资源
    PythonStudy5
    【无标题】
    而今迈步从头越｜nacos逼我在mac上重新安装java8与环境变量的配置
    jQuery【菜单功能、淡入淡出轮播图(上)、淡入淡出轮播图(下)、折叠面板】(五)-全面详解（学习总结---从入门到深化）
    阿里云与信通院邀您参与云原生安全用户调研
    综述 | 关于点云配准的全面综述（一）
    Python&C++相互混合调用编程全面实战-21依赖的QT环境安装和信号槽机制的讲解
  • 原文地址：https://blog.csdn.net/m0_67821824/article/details/132839930