unordered_map与unordered_set封装实现C++

STL容器中unordered_set与unordered_map的底层实际上是一个哈希表。

1. unordered_set类与unordered_map类的框架

1.1 unordered_set

在pc这个命名空间中，参数SetCompare是仿函数，实现下面讲解

namespace pc
{
	template<class K,class Hash=HashFunc<K>>
	class unordered_set
	{
	public:
//成员函数
	private:
		HashTable<K, const K, SetCompare,Hash> _ht;
	};
}

1.2 unordered_map

也存放在pc空间中，同样MapCompare也是仿函数

namespace pc
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
	public:
    //成员函数
	private:
		HashTable<K, pair<const K, V>, MapCompare,Hash> _ht;
	};
}

2. 改造哈希

2.1 节点改造

将哈希节点存储的值改变为一个可操控的T(因为有可能是unordered_set调用也可能是unordered_map调用)

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
	HashNode(const T& data)
		:_next(nullptr)
		, _data(data)
	{
	}
};

2.2 改造哈希链地址法实现

template<class K, class T,class Compare,class Hash>

四个模板参数，K是键值的数据类型，T是存储数据的数据类型，Compare是仿函数实现如下。Hash是将键值K转换为数字(string类型进行一个模板特化)如下。

        //unordered_map的仿函数
    	struct MapCompare
		{
			const K& operator()(const pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
        //unordered_set的仿函数
		struct SetCompare
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};

template<class K>
struct HashFunc
{
	size_t operator()(const K& k)
	{
		return size_t(k);
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& k)
	{
		size_t hash = 0;
		for (auto e : k)
		{
			hash *= 131;
			hash += e;
		}
		return hash;
	}
};

（1）查找的改造

利用仿函数进行比较，返回值变为迭代器，后面进行讲解。

	Iterator Find(const K& k)
	{
		Hash hs;
		Compare com;
		size_t hashi = hs(k) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (com(cur->_data) == k)
				return Iterator(cur, this);
			cur = cur->_next;
		}

		return Iterator(nullptr, this);
	}

（2）插入改造

将参数类型改为T，返回类型变为一个pair类型，first类型为迭代器，second类型为一个布尔类型判断是否插入成功。

	pair<Iterator,bool> Insert(const T& data)
	{
		Compare com;
		Iterator it = Find(com(data));
		if (it != Iterator(nullptr, this))
			return make_pair(it, false);
		Hash hs;

		if (_n * 10 / _table.size() > 10)//平衡因子
		{
			vector<Node*> newht;
			newht.resize(__stl_next_prime(_table.size()));
			//将旧表节点头插到新表，更加方便
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;

					size_t hashi = hs(com(cur->_data)) % newht.size();
					cur->_next = newht[hashi];
					newht[hashi] = cur;

					cur = next;
				}
				_table[i] = nullptr;
			}
			_table.swap(newht);
		}
		size_t hashi = hs(com(data)) % _table.size();
		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];//头插
		_table[hashi] = newnode;
		_n++;
		return make_pair(Iterator(newnode, this), true);
	}

（3）删除改造

利用仿函数来比较

	bool Erase(const K& k)
	{
		Hash hs;
		Compare com;
		size_t hashi = hs(k) % _table.size();

		Node* prev = nullptr;
		Node* tmp = _table[hashi];

		while (tmp && com(tmp->_data) != k)
		{
			prev = tmp;
			tmp = tmp->_next;
		}
		if (tmp == nullptr)
			return false;
		if (prev)
		{
			prev->_next = tmp->_next;
		}
		else
		{
			_table[hashi] = tmp->_next;
		}
		delete tmp;
		tmp = nullptr;
		_n--;
		return true;
	}

3. 迭代器实现

迭代器的模板参数需要六个

分别是键值类型，节点数据类型，节点的引用，节点的指针，Compare，Hash

迭代器存储的数据有当前所在节点与哈希表

我们需要再前面声明一下HashTable，因为迭代器需要使用哈希表来寻找数据

template<class K,class T,class Compare,class Hash>
class HashTable;

template<class K,class T,class Ref,class Ptr,class Compare,class Hash>
class HashTableIterator
{
	typedef HashNode<T> Node;
	typedef HashTableIterator<K, T, Ref, Ptr,Compare,Hash> Self;

	template<class K, class T, class Compare, class Hash>
	friend class HashTable;
public:
	HashTableIterator(Node* node,const HashTable<K,T,Compare,Hash>* pht)
		:_node(node)
		,_pht (pht)
	{
	}

	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	Self& operator++()
	{
		if(_node->_next)//当前桶还有节点
		{
			_node = _node->_next;
		}
		else//找下一个桶
		{
			Compare com;
			Hash hs;
			size_t hashi = hs(com(_node->_data)) % _pht->_table.size();
			hashi++;
			while (hashi < _pht->_table.size())
			{
				if (_pht->_table[hashi])//如果此节点存在
				{
					break;
				}
				hashi++;
			}
			if (hashi == _pht->_table.size())//如果到尾都找不到
			{
				_node = nullptr;
			}
			else
			{
				_node = _pht->_table[hashi];
			}
		}
		return *this;
	}
private:
	Node* _node;
	const HashTable<K, T, Compare, Hash>* _pht;
};

构造函数中第一个参数不能加const因为后面要改变不然_node权限会变const，第二个参数要加const因为在哈希表中是传this指针来构造的

++的实现

哈希表中存储的是链表，node遍历完当前链表的时候就要寻找哈希表中下一个非空的值了，因为要用到哈希表里的的成员所以在哈希表里要加一个友元声明如下随时

在哈希表中写迭代器函数，begin() end()等

	template<class K, class T, class Ref, class Ptr, class Compare, class Hash>
	friend class HashTableIterator;

    typedef HashTableIterator<K, T, T&, T*, Compare, Hash> Iterator;
	typedef HashTableIterator<K, T, const T&, const T*, Compare, Hash> ConstIterator;

	Iterator Begin()
	{
		if (_n == 0)
			return End();
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[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 < _table.size(); i++)
		{
			Node* cur = _table[i];
			if (cur)
				return ConstIterator(cur, this);
		}
		return End();
	}
	ConstIterator End() const
	{
		return ConstIterator(nullptr, this);
	}

unordered_set与unordered_map的完整实现如下

namespace pc
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
	public:
		struct MapCompare
		{
			const K& operator()(const pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
		//当 typedef 声明的是一个类中的 类型成员 而不是数据成员时，需要 typename 修饰声明的类型成员：
		typedef typename HashTable<K, pair<const K, V>, MapCompare, Hash>::Iterator iterator;
		typedef typename HashTable<K, pair<const K, V>, MapCompare, 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 pair<const 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);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		} 

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

namespace pc
{
	template<class K,class Hash=HashFunc<K>>
	class unordered_set
	{
	public:
		struct SetCompare
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};

		typedef typename HashTable<K, const K, SetCompare, Hash>::Iterator iterator;
		typedef typename HashTable<K, const K, SetCompare, 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& k)
		{
			return _ht.Insert(k);
		}
		iterator Find(const K& key)
		{
			return _ht.Find(key);
		}
		bool Erase(const K& key)
		{
			return _ht.Erase(key);
		}

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

4. 源代码

hash.h

#pragma once
#include<iostream>
#include<vector>
using namespace std;
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
	HashNode(const T& data)
		:_next(nullptr)
		, _data(data)
	{
	}
};

template<class K>
struct HashFunc
{
	size_t operator()(const K& k)
	{
		return size_t(k);
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& k)
	{
		size_t hash = 0;
		for (auto e : k)
		{
			hash *= 131;
			hash += e;
		}
		return hash;
	}
};

template<class K,class T,class Compare,class Hash>
class HashTable;

template<class K,class T,class Ref,class Ptr,class Compare,class Hash>
class HashTableIterator
{
	typedef HashNode<T> Node;
	typedef HashTableIterator<K, T, Ref, Ptr,Compare,Hash> Self;

	template<class K, class T, class Compare, class Hash>
	friend class HashTable;
public:
	HashTableIterator(Node* node,const HashTable<K,T,Compare,Hash>* pht)
		:_node(node)
		,_pht (pht)
	{
	}

	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	Self& operator++()
	{
		if(_node->_next)//当前桶还有节点
		{
			_node = _node->_next;
		}
		else//找下一个桶
		{
			Compare com;
			Hash hs;
			size_t hashi = hs(com(_node->_data)) % _pht->_table.size();
			hashi++;
			while (hashi < _pht->_table.size())
			{
				if (_pht->_table[hashi])//如果此节点存在
				{
					break;
				}
				hashi++;
			}
			if (hashi == _pht->_table.size())//如果到尾都找不到
			{
				_node = nullptr;
			}
			else
			{
				_node = _pht->_table[hashi];
			}
		}
		return *this;
	}
private:
	Node* _node;
	const HashTable<K, T, Compare, Hash>* _pht;
};

template<class K, class T,class Compare,class Hash>
class HashTable
{
public:
	typedef HashNode<T> Node;

	template<class K, class T, class Ref, class Ptr, class Compare, class Hash>
	friend class HashTableIterator;

	typedef HashTableIterator<K, T, T&, T*, Compare, Hash> Iterator;
	typedef HashTableIterator<K, T, const T&, const T*, Compare, Hash> ConstIterator;

	Iterator Begin()
	{
		if (_n == 0)
			return End();
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[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 < _table.size(); i++)
		{
			Node* cur = _table[i];
			if (cur)
				return ConstIterator(cur, this);
		}
		return End();
	}
	ConstIterator End() const
	{
		return ConstIterator(nullptr, this);
	}

	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
	 1543, 3079, 6151, 12289, 24593,
	 49157, 98317, 196613, 393241, 786433,
	 1572869, 3145739, 6291469, 12582917, 25165843,
	 50331653, 100663319, 201326611, 402653189, 805306457,
	 1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list +
			__stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);//返回大于等于n的第一个位置，找不到返回首元素地址
		return pos == last ? *(last - 1) : *pos;
	}

	HashTable()
	{
		_table.resize(__stl_next_prime(_table.size()));
	}
	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			//DestroyList(_table[i]);
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			cur = nullptr;
		}
	}
	Iterator Find(const K& k)
	{
		Hash hs;
		Compare com;
		size_t hashi = hs(k) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (com(cur->_data) == k)
				return Iterator(cur, this);
			cur = cur->_next;
		}

		return Iterator(nullptr, this);
	}
	pair<Iterator,bool> Insert(const T& data)
	{
		Compare com;
		Iterator it = Find(com(data));
		if (it != Iterator(nullptr, this))
			return make_pair(it, false);
		Hash hs;

		if (_n * 10 / _table.size() > 10)//平衡因子
		{
			vector<Node*> newht;
			newht.resize(__stl_next_prime(_table.size()));
			//将旧表节点头插到新表，更加方便
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;

					size_t hashi = hs(com(cur->_data)) % newht.size();
					cur->_next = newht[hashi];
					newht[hashi] = cur;

					cur = next;
				}
				_table[i] = nullptr;
			}
			_table.swap(newht);
		}
		size_t hashi = hs(com(data)) % _table.size();
		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];//头插
		_table[hashi] = newnode;
		_n++;
		return make_pair(Iterator(newnode, this), true);
	}
	bool Erase(const K& k)
	{
		Hash hs;
		Compare com;
		size_t hashi = hs(k) % _table.size();

		Node* prev = nullptr;
		Node* tmp = _table[hashi];

		while (tmp && com(tmp->_data) != k)
		{
			prev = tmp;
			tmp = tmp->_next;
		}
		if (tmp == nullptr)
			return false;
		if (prev)
		{
			prev->_next = tmp->_next;
		}
		else
		{
			_table[hashi] = tmp->_next;
		}
		delete tmp;
		tmp = nullptr;
		_n--;
		return true;
	}
private:
	vector<Node*> _table;
	size_t _n;//节点个数
};

unordered_set.h

#include"hash.h"

namespace pc
{
	template<class K,class Hash=HashFunc<K>>
	class unordered_set
	{
	public:
		struct SetCompare
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};

		typedef typename HashTable<K, const K, SetCompare, Hash>::Iterator iterator;
		typedef typename HashTable<K, const K, SetCompare, 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& k)
		{
			return _ht.Insert(k);
		}
		iterator Find(const K& key)
		{
			return _ht.Find(key);
		}
		bool Erase(const K& key)
		{
			return _ht.Erase(key);
		}

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

unordered_map.h

#include"hash.h"

namespace pc
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
	public:
		struct MapCompare
		{
			const K& operator()(const pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
		//当 typedef 声明的是一个类中的 类型成员 而不是数据成员时，需要 typename 修饰声明的类型成员：
		typedef typename HashTable<K, pair<const K, V>, MapCompare, Hash>::Iterator iterator;
		typedef typename HashTable<K, pair<const K, V>, MapCompare, 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 pair<const 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);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		} 

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

这篇就到这里啦  (๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤

ヾ(￣▽￣)Bye~Bye~