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

aosei

发布于 2024-01-23 15:28:30

910

发布于 2024-01-23 15:28:30

文章被收录于专栏：csdn-nagiYcsdn-nagiY

unordered_se和unordered_map的底层都是哈希桶。哈希桶之前已经模拟实现过->哈希表的开散列和闭散列但是之前并没有实现哈希表的迭代器，接下来将会实现。

一.哈希表迭代器的实现

模板参数的设计

因为 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 >

关于接口实现

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

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

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

++的下一个节点正好在当前桶
++的下一个节点不在当前桶，也就是说 ++ 为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
	};
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

源码