【C++进阶】unordered_set和unordered_map的模拟实现（附源码）

系统管理员 2024-04-22 12:14 68阅读 0赞

> 今天是1024程序员节，祝大家节日快乐哦~~~???????????

> unordered\_se和unordered\_map的底层都是哈希桶。
> 
> 哈希桶之前已经模拟实现过->[哈希表的开散列和闭散列][Link 1]
> 
> 但是之前并没有实现哈希表的迭代器，接下来将会实现。

## 一.哈希表迭代器的实现 ##

### 模板参数的设计 ###

因为 set存储的是key，而map存储的是 K-V 键值对，两个数据类型不一样，但底层又用的都是哈希表，所以在哈希表的模板参数中直接写成 T，但是还需要一个 K 模板参数，因为实际用map或是set的Find接口的时候，都是传的 Key，所以这个用于 Find 接口的实现

*  如果是 set ，那么 T 实例化成 Key
 *  如果是 map ，那么 T 实例化成 pair<K,V>

但是当数据类型是 T 的时候，它可能是 K ，也可能是 pair<K,V> ，该 K 倒是没关系，

那 pair<K,V> 该怎么对它取余呢？

解决方法是使用仿函数 KeyofT ！

这个 KeyofT 是在 unordered\_set 和unordered\_map 层传过来的。

//KeyofT 用于取出 T 中的 K
    //HF 是哈希函数，除留余数时用到
    template<class K, class T,class Ref,class Ptr, class KeyofT, class HF >

### 关于接口实现 ###

我们需要实现这些接口：运算符重载 \* -> ++ != ==

\* 和 -> 倒是没什么好说的、非常简单，问题是 ++ ，该如何实现。

实现 ++ 时分为两种情况：

1.  \++的下一个节点正好在当前桶
2.  \++的下一个节点不在当前桶，也就是说 ++ 为nullptr

第一种情况很简单，第二种情况怎么办？如何找到下一个桶？

所以迭代器在实现时，成员变量中不仅需要一个节点，还需要一个哈希桶指针，帮助找到下一个桶。

Node* _node;    //节点指针
    		const HashBucket<K, T, KeyofT, HF>* _pht;   //哈希桶指针
    
    		Iterator(Node*node, const HashBucket<K, T, KeyofT, HF>* pht)
    			:_node(node)
    			,_pht(pht)
    		{}

需要注意的是，这里要使用到哈希桶，哈希桶又需要用到迭代器，那么谁在前谁在后？

此时只需前置声明一下哈希桶就行了。

只有这个 ++ 实现稍微有点麻烦，其他的都比较简单，在博主之前的文章里也有讲到过。

### 源码 ###

//前置声明
    template<class K, class T, class KeyofT, class HF>
    class HashBucket;
    
    //KeyofT用来取出 T 中的key
    template<class K, class T,class Ref,class Ptr, class KeyofT, class HF >
    struct Iterator
    {
    	KeyofT kot;
    	HF hf;
    	typedef HashBucketNode<T> Node;
    	typedef Iterator<K, T,Ref,Ptr, KeyofT, HF > Self;
    	
    	Node* _node;   //节点指针
    	const HashBucket<K, T, KeyofT, HF>* _pht;  //哈希桶指针
    
    	Iterator(Node*node, const HashBucket<K, T, KeyofT, HF>* pht)
    		:_node(node)
    		,_pht(pht)
    	{}
    
    	Ref operator*()
    	{
    		return _node->_data;
    	}
    
    	Ptr operator->()
    	{
    		return &_node->_data;
    	}
    
    	bool operator!=(const Self& s)
    	{
    		return _node != s._node;
    	}
    
    	bool operator==(const Self& s)
    	{
    		return _node == s._node;
    	}
    
    	Self& operator++()
    	{
    		KeyofT kot;
    		HF hf;
    		if (_node->_pNext != nullptr)   //++ 的下一个节点在当前桶中
    			_node = _node->_pNext;
    		else    //++ 的下一个节点不在当前桶中
    		{
    			Node* cur = _node;
    			size_t hashi = hf(kot(cur->_data)) % _pht->_table.size();
    			hashi++;
    			while (hashi < _pht->_table.size())  //寻找下一个桶
    			{
    				if (_pht->_table[hashi] != nullptr)
    				{
    					_node = _pht->_table[hashi];
    					return *this;
    				}
    				else
    					hashi++;
    		    }
    			_node = nullptr;
    			return *this;
    		}
    	    return *this;
    	}
    };

--------------------

## 二.哈希表的修改 ##

因为迭代器中要用到哈希表的私有成员，所以在哈希表中声明 迭代器 为友元。

为了适应unordered\_set和unordered\_map，Insert ，Find，Erase地接口的返回值都要修改。

Insert 的返回值改为 pair<Iterator,bool>

Find和Erase 的返回值改为 Iterator

增加 begin ，end 接口

此时取模的方式也有所变化，先用 KeyofT 从 T 中取出 Key，然后再调用哈希函数。

namespace OpenHash
    {
    	template<class K,class T, class KeyofT,class HF = HashFunc<K>>
    	class HashBucket
    	{
    		typedef HashBucketNode<T> Node;
    		typedef HashBucket<K,T,KeyofT,HF> Self;
    
    	public:
    		template<class K, class T, class Ref, class Ptr, class KeyofT, class HF >
    		friend struct Iterator;   //声明迭代器友元
    		typedef Iterator<K, T, const T&, const T*, KeyofT, HF> const_Iterator;/
    		typedef Iterator<K, T, T&, T*, KeyofT, HF> Iterator;
    		
    		Iterator begin()
    		{
    			for (size_t i = 0; i < _table.size(); i++)
    			{
    				if (_table[i] != nullptr)
    					return Iterator(_table[i], this);
    			}
    			return Iterator(nullptr, this);
    		}
    
    		Iterator end()
    		{
    			return Iterator(nullptr, this);
    		}
    
    		const_Iterator begin() const
    		{
    			for (size_t i = 0; i < _table.size(); i++)
    			{
    				if (_table[i] != nullptr)
    					return const_Iterator(_table[i], this);
    			}
    			return const_Iterator(nullptr, this);
    		}
    
    		const_Iterator end() const
    		{
    			return const_Iterator(nullptr, this);
    		}
    
    		HashBucket()
    		{
    			_table.resize(10, nullptr);
    			_size = 0;
    		}
    
    		~HashBucket()
    		{
    			Clear();
    		}
    
    		// 哈希桶中的元素不能重复
    		pair<Iterator,bool> Insert(const T& data)
    		{
    			Iterator ret = Find(data);
    			if (ret!=end())
    				return { Iterator(nullptr,this),false};
    			HF hf;
    			KeyofT kot;
    			if (_size == _table.size())
    			{
    				size_t newsize = 2 * _table.size();
    				vector<Node*> newtable(newsize, nullptr);
    				for (size_t i = 0; i < _table.size(); i++)
    				{
    					Node* cur = _table[i];
    					while (cur)
    					{
    						Node* next = cur->_pNext;
    						size_t hashi = hf(kot(data)) % newsize;
    						Node* newnode = new Node(cur->_data);
    						if (newtable[hashi] == nullptr)
    							newtable[hashi] = newnode;
    						else
    						{
    							newnode->_pNext = newtable[hashi]->_pNext;
    							newtable[hashi]->_pNext = newnode;
    						}
    						cur = next;
    					}
    					_table[i] = nullptr;
    				}
    				_table.swap(newtable);
    			}
    			Node* newnode = new Node(data);
    			size_t hashi = hf(kot(data)) % _table.size();  //注意取模方式
    			if (_table[hashi] == nullptr)
    				_table[hashi] = newnode;
    			else
    			{
    				newnode->_pNext = _table[hashi]->_pNext;
    				_table[hashi]->_pNext = newnode;
    			}
    			_size++;
    			return { Iterator(newnode,this),true };
    		}
    
    		 //删除哈希桶中为data的元素(data不会重复)
    		Iterator Erase(Iterator pos)
    		{
    			HF hf;
    			KeyofT kot;
    			Iterator it = begin();
    			while (it != end())
    			{
    				if (it == pos)
    				{
    					Iterator tmp = it;
    					delete it;
    					return Iterator(++tmp, this);
    				}
    				++it;
    			}
    			return Iterator(nullptr, this);
    		}
    
    		Iterator Find(const T& data)
    		{
    			HF hf;
    			KeyofT kot;
    			size_t hashi = hf(kot(data)) % _table.size();
    			Node* cur = _table[hashi];
    			while (cur)
    			{
    				if (cur->_data == data)
    					return Iterator(cur, this);
    				else
    					cur = cur->_pNext;
    			}
    			return end();
    		}
    
    	private:
    		size_t HashFunc(const T& data)
    		{
    			return HF()(data) % _table.capacity();
    		}
    	private:
    		vector<Node*> _table;
    		size_t _size;      // 哈希表中有效元素的个数
    	};
    }

--------------------

## 三.unordered\_map 的模拟实现 ##

因为 unordered\_map 的 Key 是不可以修改的，所以直接写成 const K

但是 unordered\_map 的 Value 可以修改。

### 插入 ###

因为 unordered\_map 要实现 \[\] ，所以 insert 要返回一个 pair<iterator,bool>

namespace KM
    {
    	template<class K>   //哈希函数
    	struct DefHF
    	{
    		size_t operator()(const K& key)
    		{
    			return (size_t)key;
    		}
    	};
    	template<class K,class V>
    	class unordered_map
    	{
    		struct MapKeyofT   //从 pair 中取出 K
    		{
    			const K& operator()(const pair<const K, V>& kv)
    			{
    				return kv.first;
    			}
    		};
    		
    	public:
            //注意这里要使用 typename ，否则编译器无法分清 Iterator 是类型还是函数
    		typedef typename OpenHash::HashBucket<K, pair<const K, V>, MapKeyofT>::Iterator iterator;   //普通迭代器
    		typedef typename OpenHash::HashBucket<K, pair<const K, V>,  MapKeyofT>::const_Iterator const_iterator;    //常量迭代器
    
    		iterator begin()
    		{
    			return  _ht.begin();  //调用哈希桶的 begin
    		}
    
    		iterator end()
    		{
    			return _ht.end();    //调用哈希桶的 end
    		}
    
    		const_iterator begin() const 
    		{
    			return  _ht.begin();
    		}
    
    		const_iterator end() const 
    		{
    			return _ht.end();
    		}
    
            //插入
    		pair<iterator,bool> insert(const pair<K, V>& kv)
    		{
    			return _ht.Insert(kv);
    		}
            //删除
    		iterator erase(iterator pos)
    		{
    			return _ht.Erase(pos);
    		}
    
    		// Acess
    		V& operator[](const K& key)
    		{
    			pair<iterator, bool> ret = _ht.Insert({key,V()});
    			iterator it = ret.first;
    			return it->second;
    		}
    		const V& operator[](const K& key)const
    		{
    			pair<const_iterator, bool> ret = _ht.Insert({ key,V() });
    			const_iterator it = ret.first;
    			return it->second;
    		}
    
    		// capacity
    		size_t size()const 
    		{
    			return _ht.size(); 
    		}
    		bool empty()const 
    		{ 
    			return _ht.empty();
    		}
    
    		// lookup
    		iterator find(const K& key) 
    		{
    			return _ht.Find(key); 
    		}
    		size_t count(const K& key)
    		{ 
    			return _ht.Count(key); 
    		}
    
    		// bucket
    		size_t bucket_count() 
    		{
    			return _ht.BucketCount();
    		}
    		size_t bucket_size(const K& key) 
    		{
    			return _ht.BucketSize(key);
    		}
    		
    	private:
            //传入 MapKeyofT
    		OpenHash::HashBucket<K, pair<const K, V>, MapKeyofT> _ht;  //底层是哈希桶
    	};
    
    }

--------------------

## 四.unordered\_set的模拟实现 ##

set 有点麻烦，因为它的 Key 是不允许修改的，所以它的普通迭代器也就是 const 迭代器，const迭代器就是 const 迭代器。

这就会造成一些问题。

因为 insert 接口返回的是一个 pair ，你以为它是普通迭代器，但实际上它是一个 const 迭代器，而底层哈希桶 Insert 接口返回的是一个普通迭代器，这就造成了类型不匹配的问题。该如何解决？

其实，只需要在迭代器的实现中多加一个构造函数

*  当是 iterator 是这个函数就是拷贝构造
 *  当时 const\_iterator 时，这个函数就是构造，支持普通迭代器构造 const 迭代器

typedef Iterator<K, T, K&, K*, KeyofT, HF> iterator;  //普通迭代器
    
    Iterator(const iterator& it)
    		:_node(it._node)
    		,_pht(it._pht)
    	{}

namespace KM
    {
    	template<class K>
    	class unordered_set   
    	{
    		struct SetKeyofT   //unordered——set 的 KeyofT
    		{
    			const K& operator()(const K& key)
    			{
    				return key;
    			}
    		};
    	public:
            //普通迭代器其实是 const 迭代器
    		typedef typename OpenHash::HashBucket<K, K, SetKeyofT>::const_Iterator iterator;
    		typedef typename OpenHash::HashBucket<K, K, SetKeyofT>::const_Iterator const_iterator;
    
    		const_iterator begin() const
    		{
    			return _ht.begin();
    		}
    
    		const_iterator end() const
    		{
    			return _ht.end();
    		}
    
    		pair<const_iterator, bool> insert(const K& key)
    		{
    			pair<typename OpenHash::HashBucket<K, K, SetKeyofT>::Iterator, bool> ret = _ht.Insert(key);
                //普通迭代器构造 const 迭代器
    			return pair<const_iterator, bool>(ret.first, ret.second);  
    		}
    
    		iterator erase(iterator pos)
    		{
    			return _ht.Erase(pos);
    		}
    
    		// capacity
    		size_t size()const 
    		{
    			return _ht.size(); 
    		}
    
    		bool empty()const 
    		{ 
    			return _ht.empty();
    		}
    
    		// lookup
    		iterator find(const K& key) 
    		{
    			return _ht.Find(key); 
    		}
    
    		size_t count(const K& key) 
    		{
    			return _ht.Count(key);
    		}
    
    		// bucket
    		size_t bucket_count()
    		{
    			return _ht.BucketCount();
    		}
    
    		size_t bucket_size(const K& key) 
    		{
    			return _ht.BucketSize(key);
    		}
    
    	private:
    		OpenHash::HashBucket<K, K, SetKeyofT> _ht;  //底层是哈希桶，传入 SetKeyofT
    	};
    }

--------------------

> **??本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；?️?**
> 
> **??希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；??**
> 
> **??谢谢你的阅读。??**

[Link 1]: http://t.csdnimg.cn/WBXiA