C++之unordered封装的实现

目录

• 一、哈希表的修改
• 1.1、哈希表节点结构
• 1.2、迭代器
• 1.3、哈希表结构
• 1.4、完整代码
• 二、unordered_map的实现
• 三、unordered_set的实现

一、哈希表的修改

注意：这里我们使用哈希桶来封装unordered_map和unordered_set。

1.1、哈希表节点结构

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

因为我们要复用哈希表，即使用同一份哈希表代码来封装unordered_map和unordered_set，所以这里将模版参数改为T，T即要存储的数据类型，对于unordered_set而言，T直接就是要存储的数据类型；对于unordered_map而言，T是pair类型的。

在插入方法中，我们使用有参构造，在创建节点时直接将数据通过构造函数赋值进去，所以这里还实现了一个构造函数。

1.2、迭代器

iterator核心源码：

template <class Value, class Key, class HashFcn,
 class ExtractKey, class EqualKey, class Alloc>

struct __hashtable_iterator {
 typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
 hashtable;
 typedef __hashtable_iterator<Value, Key, HashFcn, 
 ExtractKey, EqualKey, Alloc>
 iterator;
 typedef __hashtable_const_iterator<Value, Key, HashFcn, 
 ExtractKey, EqualKey, Alloc>
 const_iterator;
 typedef __hashtable_node<Value> node;
 typedef forward_iterator_tag iterator_category;
 typedef Value value_type;

 node* cur;
 hashtable* ht;

 __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
 __hashtable_iterator() {}
 reference operator*() const { return cur->val; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR

 pointer operator->() const { return &(operator*()); }

#endif /* __SGI_STL_NO_ARROW_OPERATOR */
iterator& operator++();
 iterator operator++(int);
 bool operator==(const iterator& it) const { return cur == it.cur; }
 bool operator!=(const iterator& it) const { return cur != it.cur; }
};

template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
 const node* old = cur;
 cur = cur->next;
 if (!cur) {
 size_type bucket = ht->bkt_num(old->val);
 while (!cur && ++bucket < ht->buckets.size())
 cur = ht->buckets[bucket];
 }
 return *this;
}

iterator实现思路分析：

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算 符实现，迭代器像指针⼀样访问的⾏为，要注意的是哈希表的迭代器是单向迭代器。
• 这⾥的难点是operator++的实现。iterator中有⼀个指向结点的指针，如果当前桶下⾯还有结点， 则结点的指针指向下⼀个结点即可。如果当前桶⾛完了，则需要想办法计算找到下⼀个桶。这⾥的难点是反⽽是结构设计的问题，参考上面源码，我们可以知道iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶⾛完了，要计算下⼀个桶就相对容易多了，⽤key值计算出当前桶位置，依次往后找下⼀个不为空的桶即可。
• begin()返回第⼀个不为空的桶中第⼀个节点指针构造的迭代器，这⾥end()返回迭代器可以⽤空指针表⽰。
• unordered_map的iterator不⽀持修改key但是可以修改value，我们把unordered_map的第⼆个模板参数pair的第⼀个参数改成const K即可，HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;（不允许修改Key是因为数据在哈希表中存储的地址是通过Key映射的，如果修改Key，破坏了哈希表的结构）。
• unordered_set的iterator也不⽀持修改，我们把unordered_set的第⼆个模板参数改成const K即可，HashTable<K, const K, SetKeyOfT, Hash> _ht;（和unordered_map同理）。

具体代码：

	// 前置声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht;

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				//当前桶还有节点
				_node = _node->_next;
			}
			else
			{
				//当前桶走完了，找下一个不为空的桶
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				++hashi;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						break;
					}

					++hashi;
				}

				if (hashi == _pht->_tables.size())
				{
					_node = nullptr; //end()
				}
				else
				{
					_node = _pht->_tables[hashi];
				}
			}

			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

	};

注意：这里需要对哈希表进行前置声明，因为在迭代器中用到了哈希表，但是编译器编译时是向上查找，而哈希表在下面，会因为找不到而报错，将哈希表放到上面也不行，因为哈希表里也会封装迭代器，如果哈希表在上面向上查找时就会找不到迭代器，总之必须有一个进行前置声明。另外，迭代器中重载++运算符时为了确定当前节点的位置访问了哈希表的私有成员，所以后面在哈希表中还需要进行友元声明。php

1.3、哈希表结构

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		// 友元声明
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
		friend struct HTIterator;

		typedef HashNode<T> Node; //节点不想让外界访问
	public:
		typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要让外界访问
		typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

		Iterator Begin()
		{
			if (_n == 0) //没有有效数据
			{
				return End();
			}

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}

			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}

			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		pair<Iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;

			Iterator it = Find(kot(data));
			//去重
			if (it != End())
			{
				return make_pair(it,false);
			}

			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();

			//负载因子==1  扩容
			if (_n == _tables.size())
			{
				// 需要新建节点和释放旧节点，效率较低
				//	HashTable<K, V, Hash> newHT;
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		Node* cur = _tables[i];
				//		while (cur)
				//		{
				//			newHT.Insert(cur->_kv);
				//			cur = cur->_next;
				//		}
				//	}

				//	_tables.swap(newHT._tables);

				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						//旧表中的节点重新映射在新表中的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}

					//节点都挪到新表上了，旧表置空
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return make_pair(Iterator(newnode,this),true);
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur,this);
				}

				cur = cur->_next;
			}

			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _tables; //指针数组
		size_t _n; //表中存储数据个数
	};

}

为什么需要KeyOfT模版参数：

跟map和set相⽐⽽⾔unordered_map和unordered_set的模拟实现类结构更复杂⼀点，但是⼤框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数是K，还是pair， 那么insert内部进⾏插⼊时要⽤K对象转换成整http://www.devze.com形取模和K⽐较相等(去重)，因为pair的value不需要参与计算取模，且pair默认⽀持的是key和value⼀起⽐较相等，但实际上我们需要的是任何时候只需要⽐较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给 HashQoqxPVJTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K⽐较相等。

返回值的修改：

这里为了符合unordered_map和unordered_set的使用将Find方法的返回值改为迭代器，为了实现unordered_map的 [ ] 运算符重载，将Insert方法的返回值该为pair类型，其中返回的pair对象的first属性的值是新插入节点/原有节点的迭代器，second属性的值是bool类型，代表是否插入成功。

1.4、完整代码

namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	// 前置声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

		Node* _node;
		const HashTable<K, T, KeyOfT, Hash>* _pht;

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Self& operator++()
		{
			if (_node->_next)
			{
				//当前桶还有节点
				_node = _node->_next;
			}
			else
			{
				//当前桶走完了，找下一个不为空的桶
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				++hashi;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						break;
					}

					++hashi;
				}

				if (hashi == _pht->_tables.size())
				{
					_node = nullptr; //end()
				}
				else
				{
					_node = _pht->_tables[hashi];
				}
			}

			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

	};

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		// 友元声明
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
		friend struct HTIterator;

		typedef HashNode<T> Node; //节点不想让外界访问
	public:
		typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; //迭代器需要让外界访问
		typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

		Iterator Begin()
		{
			if (_n == 0) //没有有效数据
			{
				return End();
			}

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}

			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}

			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		pair<Iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;

			Iterator it = Find(kot(data));
			//去重
			if (it != End())
			{
				return make_pair(ijavascriptt,false);
			}

			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();

			//负载因子==1  扩容
			if (_n == _tables.size())
			{
				// 需要新建节点和释放旧节点，效率较低
				//	HashTable<K, V, Hash> newHT;
				//	for (size_t i = 0; i < _tables.size(); i++)
				//	{
				//		Node* cur = _tables[i];
				//		while (cur)
				//		{
				//			newHT.Insert(cur->_kv);
				//			cur = cur->_next;
				//		}
				//	}

				//	_tables.swap(newHT._tables);

				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						//旧表中的节点重新映射在新表中的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[hashi];
						newtables[hashi] = cur;

						cur = next;
					}

					//节点都挪到新表上了，旧表置空
					_tables[i] = nullptr;
				}

				_tables.swap(newtables);
			}

			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;

			return make_pair(Iterator(newnode,this),true);
		}

		Iterator Find(const K& key)
		{
			KeyOfT kot;
			pythonHash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur,this);
				}

				cur = cur->_next;
			}

			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_n;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*> _tables; //指针数组
		size_t _n; //表中存储数据个数
	};

}

二、unordered_map的实现

这里的实现没有什么困难，就是直接套一层壳，所有的调用最终还是去调哈希表的方法，所以这里就不在赘述了，直接上代码。

#include"HashTable.h"

namespace bit
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;

		iterator begin()
		{
			return _ht.Begin();
		}

		iterator end()
		{
			return _ht.End();
		}

		const_iterator begin() const
		{
			return _ht.Begin();
		}

		const_iterator end() const
		{
			return _ht.End();
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));

			return ret.first->second;
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
	};

	void test_map()
	{
		unordered_map<string, string> dict;
		dict.insert({ "sort", "排序" });
		dict.insert({ "left", "左边" });
		dict.insert({ "right", "右边" });

		dict["left"] = "左边，剩余";
		dict["insert"] = "插入";
		dict["string"];

		unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			// 不能修改first，可以修改second
			//it->first += 'x';
			it->second += 'x';

			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
	}
}

三、unordered_set的实现

这里和unordered_map一样，就是直接套一层壳，所有的调用最终还是去调哈希表的方法，所以这里就不在赘述了，直接上代码。

#include"HashTable.h"

namespace bit
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
		typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

		iterator begin()
		{
			return _ht.Begin();
		}

		iterator end()
		{
			return _ht.End();
		}

		const_iterator begin() const
		{
			return _ht.Begin();
		}

		const_iterator end() const
		{
			return _ht.End();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

	private:
		hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
	};

	void Print(const unordered_set<int>& s)
	{
		unordered_set<int>::const_iterator it = s.begin();
		while (it != s.end())
		{
			// *it += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	struct Date
	{
		int _year;
		int _month;
		int _day;

		bool operator==(const Date& d) const
		{
			return _year == d._year
				&& _month == d._month
				&& _day == d._day;
		}
	};

	struct HashDate
	{
		size_t operator()(const Date& key)
		{
			// 112
			// 121
			return (key._year * 31 + key._month) * 31 + key._day;
		}
	};

	void test_set()
	{
		unordered_set<int> s;
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };
		for (auto e : a)
		{
			s.insert(e);
		}

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;

		unordered_set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			//*it += 1;

			cout << *it << " ";
			++it;
		}
		cout << endl;

		unordered_set<Date, HashDate> us;
		us.insert({ 2024, 7, 25 });
		us.insert({ 2024, 7, 26 });

		Print(s);
	}
}

到此这篇关于C++之unordered封装的实现的文章就介绍到这了,更多相关C++ unordered封装内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！