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;
		}

	};

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

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对象转换成整形取模和K⽐较相等(去重)，因为pair的value不需要参与计算取模，且pair默认⽀持的是key和value⼀起⽐较相等，但实际上我们需要的是任何时候只需要⽐较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给 HashTable的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(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; //表中存储数据个数
	};

}

二、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);
	}
}