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

unordered_map unordered_set函数实现_unorderedmap的插入

作者：Li_阴宅 | 2024-08-07 06:02:23

赞

踩

unorderedmap的插入

一.unordered_map特点

1. unordered_map是存储pair<key, value>,通过key查找value
2.unordered_map对数据的存储没有特定的排序顺序。
3. unordered_map搜索比map快，但它遍历效率比较慢。
4. 它的迭代器至少是前向迭代器，不支持反向迭代器。

二.unordered_set特点

1.存储数据没有顺序

2.查找效率高，遍历效率低

3.没有重复值

4.插入效率高

5.不支持修改操作，可以先删除再插入

三.哈希桶

插入规则：对插入的值进行size()大小的取模，eg.14%10=4 头插到下标为4的节点处。

当size()大小==插入节点的个数 就进行扩容

结构：

哈希桶结构：有一个size()大小的顺序表，表中节点存储的是插入节点的指针Node*。

Node结构体能存储数据值，还可以保存下个节点的指针。

结构

  1. template<class T>
  2. struct HashNode
  3. {
  4. 	T _data;
  5. 	HashNode<T>* _next;
  6.  
  7. 	HashNode(const T& data)
  8. 		:_data(data)
  9. 		, _next(nullptr)
  10. 	{}
  11. };
  12.  
  13. template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
  14. class HashTable
  15. {
  16. 	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash >
  17. 	friend struct HashIterator;
  18.  
  19. 	typedef HashNode<T> Node;
  20. private:
  21. 	vector<Node*> _tables;
  22. 	size_t _n;
  23. };

_tables顺序表 _n记录插入的个数 Node插入节点结构 T存储数据类型

KeyOfT用于从T类型中取出key值 Hash将key值转换为一一对应的int值

构造 析构函数

这里定义的Node结构，它没有自己的析构函数，我们要手动释放空间。

vector<list<T>> vector list都有自己的析构，自动调用就可以。

  1. HashTable()
  2. {
  3. 	_tables.resize(10, nullptr);
  4. }
  5. ~HashTable()
  6. {
  7. 	for (size_t i = 0; i < _tables.size(); i++)
  8. 	{
  9. 		Node* cur = _tables[i];
  10. 		while (cur)
  11. 		{
  12. 			Node* next = cur->_next;
  13. 			delete cur;
  14. 			cur = next;
  15. 		}
  16. 		_tables[i] = nullptr;
  17. 	}
  18. }

插入

1.利用find()进行去重。

2.负载因子==1就需要进行扩容。

3.KeyOfTf取出key，再用Hash转换对应int再取模找到映射位置，进行头插。

  1. pair<Iterator, bool> Insert(const T&data)
  2. {
  3. 	Hash hs;
  4. 	KeyOfT kof;
  5.     //去重
  6. 	Iterator it = Find(kof(data));
  7. 	if (it != End())
  8. 	{
  9. 		return make_pair(it,false);
  10. 	}
  11. 	//扩容
  12. 	if (_n == _tables.size())
  13. 	{
  14. 		vector<Node*> newtable(_tables.size() * 2, nullptr);
  15. 		//将原哈希表存在的值重新定位插入
  16. 		for (size_t i = 0; i < _tables.size(); i++)
  17. 		{
  18. 			Node* cur = _tables[i];
  19. 			size_t newi = hs(kof(data)) % newtable.size();
  20. 			while (cur)
  21. 			{
  22. 				Node* next = cur->_next;
  23. 				cur->_next = newtable[newi];
  24. 				newtable[newi] = cur;
  25. 				cur = next;
  26. 			}
  27. 			_tables[i] = nullptr;
  28. 		}
  29.  
  30. 		//交换哈希表的vector 新建哈希表出了作用域自动销毁
  31. 		_tables.swap(newtable);
  32. 	}
  33. 	size_t Hashi = hs(Hash(data)) % _tables.size();
  34.  
  35. 	//头插
  36. 	KeyOfT kof;
  37. 	Node* cur = new Node(kof(data));
  38. 	cur->_next = _tables[Hashi];
  39. 	_tables[Hashi] = cur;
  40. 	_n++;
  41. 	return make_pair(Iterator(cur,this), true);
  42. }

查找

查找值，先找到它映射的位置，再对整个桶进行遍历。找到返回对应位置，反之返回空。

  1. Iterator* Find(const K& key)
  2. {
  3. 	KeyOfT kof;
  4. 	Hash sh;
  5. 	size_t Hashi = hs(key) % _tables.size();
  6. 	Node* cur = _tables[Hashi];
  7. 	while (cur)
  8. 	{
  9. 		if (kof(cur->_data) == key)
  10. 			return Iterator(cur,this);
  11. 		else cur = cur->_next;
  12. 	}
  13. 	return Iterator(nullptr, this);
  14. }

删除

先通过映射找到对应桶的位置，再遍历找。

1.被删除节点是头节点，没有上一个节点。删除节点后，顺序表中存入它的下一个节点的指针。

2.不是头节点，有上一个节点。让它的prev 指向 next 再删除。

记得--_n

没找到返回fasle

  1. bool Erase(const K& key)
  2. {
  3. 	Hash hs;
  4. 	size_t Hashi = hs(key) % _tables.size();
  5. 	Node* prev = nullptr;
  6. 	Node* cur = _tables[Hashi];
  7. 	Node* next = cur->_next;
  8. 	while (cur)
  9. 	{
  10. 		KeyOfT kof;
  11. 		if (kof(cur->_data) == key)
  12. 		{
  13. 			//头节点就是要删除节点
  14. 			if (cur == _tables[Hashi])
  15. 				_tables[Hashi] = next;
  16. 			else
  17. 				prev->_next = next;
  18.  
  19. 			delete cur;
  20. 			_n--;
  21. 			return true;
  22. 		}
  23. 		//找该桶的下一个节点
  24. 		prev = cur;
  25. 		cur = next;
  26. 		next = cur->_next;
  27. 	}
  28. 	return false;
  29. }

迭代器实现

顺序表中每个桶之间是不连续的。迭代器中只有指向Node的指针，遍历完一个桶后，就找不到下一个桶的位置了。

因此还需要顺序表，通过顺序表找到下一个桶的位置。

因为要访问HashNode HashTable结构，但它们的实现在HashIterator的后面，况且HashTable实现也需要迭代器。因此需要前置声明让编译器知道有HashNode HashTable。

  1. //前置声明
  2. template<class T>
  3. struct HashNode;
  4. template<class K, class T, class KeyOfT, class Hash >
  5. class HashTable;
  6. //迭代器
  7. template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash = HashFunc<K>>
  8. struct HashIterator
  9. {
  10. 	typedef HashNode<T> Node;
  11. 	typedef HashIterator< K,  T, Ref,Ptr, KeyOfT,  Hash > Self;
  12.  
  13. 	Node* _node;
  14. 	HashTable< K, T, KeyOfT, Hash >* _pht;
  15.  
  16. 	HashIterator(Node*node, HashTable< K, T, KeyOfT, Hash >*pht)
  17. 		:_node(node)
  18. 		,_pht(pht)
  19. 	{}
  20.  
  21. 	Self& operator++()
  22. 	{
  23. 		//该桶还没遍历完
  24. 		if (_node->_next)
  25. 		{
  26. 			_node = _node->_next;
  27. 		}
  28. 		//遍历完找下一个桶
  29. 		else
  30. 		{
  31. 			KeyOfT kot;
  32. 			Hash sh;
  33. 			size_t hashi = sh(kot(_node->data)) % _pht->_tables.size();
  34. 			hashi++;
  35. 			while (hashi < _pht->_tables.size())
  36. 			{
  37. 				//有桶 遍历桶
  38. 				if (_pht->_tables[hashi])
  39. 				{
  40. 					_node = _pht->_tables[hashi];
  41. 					break;
  42. 				}
  43. 				//没有++找下一个位置
  44. 				else
  45. 					hashi++;
  46. 			}
  47. 			//整个顺序表遍历结束 返回end()
  48. 			if (hashi == _pht->_table.size())
  49. 				_node = nullptr;//end()
  50. 		}
  51. 		return *this;
  52. 	}
  53.  
  54. 	Ref operator*()
  55. 	{
  56. 		return _node->_data;
  57. 	}
  58.  
  59. 	Ptr operator->()
  60. 	{
  61. 		return &_node->_data;
  62. 	}
  63. 	bool operator!=(const Self& s)
  64. 	{
  65. 		return _node != s._node;
  66. 	}
  67.  
  68. };

四.unordered_set封装

因为set的key值不能修改所以传const K

  1. #include"HashTables.h"
  2.  
  3. namespace wws
  4. {
  5. 	template<class K, class Hash = HashFunc<K>>
  6. 	class unordered_set
  7. 	{
  8. 		struct SetKeyOfT
  9. 		{
  10. 			const K& operator()(const K& key)
  11. 			{
  12. 				return key;
  13. 			}
  14. 		};
  15. 	public:
  16. 		typedef typename HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
  17. 		typedef typename HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
  18.  
  19.  
  20. 		iterator begin()
  21. 		{
  22. 			return _ht.Begin();
  23. 		}
  24.  
  25. 		iterator end()
  26. 		{
  27. 			return _ht.End();
  28. 		}
  29.  
  30. 		const_iterator begin() const
  31. 		{
  32. 			return _ht.Begin();
  33. 		}
  34.  
  35. 		const_iterator end() const
  36. 		{
  37. 			return _ht.End();
  38. 		}
  39.  
  40. 		pair<iterator, bool> insert(const K& key)
  41. 		{
  42. 			return _ht.Insert(key);
  43. 		}
  44.  
  45. 		iterator Find(const K& key)
  46. 		{
  47. 			return _ht.Find(key);
  48. 		}
  49.  
  50. 		bool Erase(const K& key)
  51. 		{
  52. 			return _ht.Erase(key);
  53. 		}
  54.  
  55. 	private:
  56. 		HashTable<K, K, SetKeyOfT, Hash> _ht;
  57. 	};
  58. }
  59.  
  60.  
  61.

五.unordered_map封装

map key不能修改 但value可以修改 所以传pair<const K,V>

  1. #include"HashTables.h"
  2.  
  3.  
  4. namespace wws
  5. {
  6. 	template<class K, class V, class Hash = HashFunc<K>>
  7. 	class unordered_map
  8. 	{
  9. 		struct MapKeyOfT
  10. 		{
  11. 			const K& operator()(const pair<K, V>& kv)
  12. 			{
  13. 				return kv.first;
  14. 			}
  15. 		};
  16. 	public:
  17. 		typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
  18. 		typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
  19.  
  20. 		iterator begin()
  21. 		{
  22. 			return _ht.Begin();
  23. 		}
  24.  
  25. 		iterator end()
  26. 		{
  27. 			return _ht.End();
  28. 		}
  29.  
  30. 		const_iterator begin() const
  31. 		{
  32. 			return _ht.Begin();
  33. 		}
  34.  
  35. 		const_iterator end() const
  36. 		{
  37. 			return _ht.End();
  38. 		}
  39.  
  40. 		pair<iterator, bool> insert(const pair<K, V>& kv)
  41. 		{
  42. 			return _ht.Insert(kv);
  43. 		}
  44.  
  45. 		V& operator[](const K& key)
  46. 		{
  47. 			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
  48.  
  49. 			return ret.first->second;
  50. 		}
  51.  
  52. 		iterator Find(const K& key)
  53. 		{
  54. 			return _ht.Find(key);
  55. 		}
  56.  
  57. 		bool Erase(const K& key)
  58. 		{
  59. 			return _ht.Erase(key);
  60. 		}
  61. 	private:
  62. 		HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
  63. 	};
  64. }

哈希表

  1. #include"string"
  2. #include"vector"
  3. #include<iostream>
  4. using namespace std;
  5.  
  6.  
  7. template<class K>
  8. struct HashFunc
  9. {
  10. 	size_t operator()(const K& key)
  11. 	{
  12. 		return (size_t)key;
  13. 	}
  14. };
  15.  
  16. // 特化
  17. template<>
  18. struct HashFunc<string>
  19. {
  20. 	size_t operator()(const string& key)
  21. 	{
  22. 		size_t hash = 0;
  23. 		for (auto e : key)
  24. 		{
  25. 			hash *= 31;
  26. 			hash += e;
  27. 		}
  28.  
  29. 		return hash;
  30. 	}
  31. };
  32. //前置声明
  33. template<class T>
  34. struct HashNode;
  35. template<class K, class T, class KeyOfT, class Hash >
  36. class HashTable;
  37. //迭代器
  38. template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash = HashFunc<K>>
  39. struct HashIterator
  40. {
  41. 	typedef HashNode<T> Node;
  42. 	typedef HashIterator< K,  T, Ref,Ptr, KeyOfT,  Hash > Self;
  43.  
  44. 	Node* _node;
  45. 	HashTable< K, T, KeyOfT, Hash >* _pht;
  46.  
  47. 	HashIterator(Node*node, HashTable< K, T, KeyOfT, Hash >*pht)
  48. 		:_node(node)
  49. 		,_pht(pht)
  50. 	{}
  51.  
  52. 	Self& operator++()
  53. 	{
  54. 		//该桶还没遍历完
  55. 		if (_node->_next)
  56. 		{
  57. 			_node = _node->_next;
  58. 		}
  59. 		//遍历完找下一个桶
  60. 		else
  61. 		{
  62. 			KeyOfT kot;
  63. 			Hash sh;
  64. 			size_t hashi = sh(kot(_node->data)) % _pht->_tables.size();
  65. 			hashi++;
  66. 			while (hashi < _pht->_tables.size())
  67. 			{
  68. 				//有桶 遍历桶
  69. 				if (_pht->_tables[hashi])
  70. 				{
  71. 					_node = _pht->_tables[hashi];
  72. 					break;
  73. 				}
  74. 				//没有++找下一个位置
  75. 				else
  76. 					hashi++;
  77. 			}
  78. 			//整个顺序表遍历结束 返回end()
  79. 			if (hashi == _pht->_table.size())
  80. 				_node = nullptr;//end()
  81. 		}
  82. 		return *this;
  83. 	}
  84.  
  85. 	Ref operator*()
  86. 	{
  87. 		return _node->_data;
  88. 	}
  89.  
  90. 	Ptr operator->()
  91. 	{
  92. 		return &_node->_data;
  93. 	}
  94. 	bool operator!=(const Self& s)
  95. 	{
  96. 		return _node != s._node;
  97. 	}
  98.  
  99. };
  100.  
  101.  
  102.  
  103.  
  104.  
  105. template<class T>
  106. struct HashNode
  107. {
  108. 	T _data;
  109. 	HashNode<T>* _next;
  110.  
  111. 	HashNode(const T& data)
  112. 		:_data(data)
  113. 		, _next(nullptr)
  114. 	{}
  115. };
  116.  
  117. template<class K, class T,class KeyOfT, class Hash = HashFunc<K>>
  118. class HashTable
  119. {
  120. 	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash >
  121. 	friend struct HashIterator;
  122.  
  123. 	typedef HashNode<T> Node;
  124.  
  125. public:
  126. 	typedef HashIterator< K, T, T&, T* , KeyOfT, Hash > Iterator;
  127. 	typedef HashIterator< K, T, const T&,const T*, KeyOfT, Hash > ConstIterator;
  128.  
  129. 	Iterator Begin()
  130. 	{
  131. 		for (size_t i = 0; i < _tables.size(); i++)
  132. 		{
  133. 			if (_tables[i])
  134. 				return Iterator(_tables[i], this);
  135. 		}
  136. 		return Iterator(nullptr, this);
  137. 	}
  138. 	Iterator End()
  139. 	{
  140. 		return Iterator(nullptr, this);
  141. 	}
  142. 	ConstIterator Begin() const
  143. 	{
  144. 		for (size_t i = 0; i < _tables.size(); i++)
  145. 		{
  146. 			if (_tables[i])
  147. 				return Iterator(_tables[i], this);
  148. 		}
  149. 		return Iterator(nullptr, this);
  150. 	}
  151. 	ConstIterator End() const
  152. 	{
  153. 		return Iterator(nullptr, this);
  154. 	}
  155.  
  156. 	HashTable()
  157. 	{
  158. 		_tables.resize(10, nullptr);
  159. 	}
  160. 	~HashTable()
  161. 	{
  162. 		for (size_t i = 0; i < _tables.size(); i++)
  163. 		{
  164. 			Node* cur = _tables[i];
  165. 			while (cur)
  166. 			{
  167. 				Node* next = cur->_next;
  168. 				delete cur;
  169. 				cur = next;
  170. 			}
  171. 			_tables[i] = nullptr;
  172. 		}
  173. 	}
  174. 	pair<Iterator, bool> Insert(const T&data)
  175. 	{
  176. 		Hash hs;
  177. 		KeyOfT kof;
  178. 		Iterator it = Find(kof(data));
  179. 		if (it != End())
  180. 		{
  181. 			return make_pair(it,false);
  182. 		}
  183. 		//扩容
  184. 		if (_n == _tables.size())
  185. 		{
  186. 			vector<Node*> newtable(_tables.size() * 2, nullptr);
  187. 			//将原哈希表存在的值重新定位插入
  188. 			for (size_t i = 0; i < _tables.size(); i++)
  189. 			{
  190. 				Node* cur = _tables[i];
  191. 				size_t newi = hs(kof(data)) % newtable.size();
  192. 				while (cur)
  193. 				{
  194. 					Node* next = cur->_next;
  195. 					cur->_next = newtable[newi];
  196. 					newtable[newi] = cur;
  197. 					cur = next;
  198. 				}
  199. 				_tables[i] = nullptr;
  200. 			}
  201.  
  202. 			//交换哈希表的vector 新建哈希表出了作用域自动销毁
  203. 			_tables.swap(newtable);
  204. 		}
  205. 		size_t Hashi = hs(Hash(data)) % _tables.size();
  206.  
  207. 		//头插
  208. 		KeyOfT kof;
  209. 		Node* cur = new Node(kof(data));
  210. 		cur->_next = _tables[Hashi];
  211. 		_tables[Hashi] = cur;
  212. 		_n++;
  213. 		return make_pair(Iterator(cur,this), true);
  214. 	}
  215. 	Iterator* Find(const K& key)
  216. 	{
  217. 		KeyOfT kof;
  218. 		Hash sh;
  219. 		size_t Hashi = hs(key) % _tables.size();
  220. 		Node* cur = _tables[Hashi];
  221. 		while (cur)
  222. 		{
  223. 			if (kof(cur->_data) == key)
  224. 				return Iterator(cur,this);
  225. 			else cur = cur->_next;
  226. 		}
  227. 		return Iterator(nullptr, this);
  228. 	}
  229. 	bool Erase(const K& key)
  230. 	{
  231. 		Hash hs;
  232. 		size_t Hashi = hs(key) % _tables.size();
  233. 		Node* prev = nullptr;
  234. 		Node* cur = _tables[Hashi];
  235. 		Node* next = cur->_next;
  236. 		while (cur)
  237. 		{
  238. 			KeyOfT kof;
  239. 			if (kof(cur->_data) == key)
  240. 			{
  241. 				//头节点就是要删除节点
  242. 				if (cur == _tables[Hashi])
  243. 					_tables[Hashi] = next;
  244. 				else
  245. 					prev->_next = next;
  246.  
  247. 				delete cur;
  248. 				_n--;
  249. 				return true;
  250. 			}
  251. 			//找该桶的下一个节点
  252. 			prev = cur;
  253. 			cur = next;
  254. 			next = cur->_next;
  255. 		}
  256. 		return false;
  257. 	}
  258. private:
  259. 	vector<Node*> _tables;
  260. 	size_t _n;
  261. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/941225
推荐阅读
相关标签

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

  

闽ICP备14008679号