【C++】unordered系列容器使用及封装-EW帮帮网

• unordered_set的声明如下，Key就是unordered_set底层关键字的类型

• unordered_set默认要求Key支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将Key转成整形的仿函数传给第二个模板参数

• unordered_set默认要求Key支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将Key比较相等的仿函数传给第三个模板参数

• unordered_set底层是用哈希桶实现，增删查平均效率是 O(1),迭代器遍历无序。

因为unordered系列容器底层是通过哈希桶实现，因为要支持哈希函数、以及处理哈希冲突的方式，所以Key要支持转换成整形并且要求支持比较相等，并且针对不能转换成整形的类型，支持通过传入仿函数进行转换。

• unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数，一般情况下，我们都不需要传后三个模板参数。

其实一开始STL库先提供了map/set容器（红黑树封装实现），不过后来鉴于哈希桶实现的map和set确实有自身优势，STL就又提供相关哈希桶实现容器，不过因为map、set的命名已经确定了，如果以hashmap/hashset新容器命名，无法很好凸显不同容器的特点。因为红黑树实现的map、set迭代器遍历有序，哈希表实现的遍历不再有序，所以STL中取名为unordered_set/unordered_map。

前面部分我们已经学习了set容器的使用，set和unordered_set的功能高度相似，只是底层结构不同，有一些性能和使用的差异，这里我们只讲他们的差异部分。

template < class Key, //
	unordered_set::key_type / value_type
		class Hash = hash<Key>, // unordered_set::hasher
		class Pred = equal_to<Key>, // unordered_set::key_equal
		class Alloc = allocator<Key> // unordered_set::allocator_type
		> class unordered_set;

1.3 unordered_set和set的使用差异

• 查看文档我们会发现unordered_set的支持增删查且跟set的使用一模一样，关于使用我们这里就不再赘述和演示了。

• unordered_set和set的第一个差异是对key的要求不同，set要求Key支持小于比较，而
unordered_set要求Key支持转成整形且支持等于比较，要理解unordered_set的这个两点要求要我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

• unordered_set和set的第二个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set是单向迭代器，其次set底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以set迭代器遍历是有序+去重。而unordered_set底层是哈希表，迭代器遍历是无序+去重。

• unordered_set和set的第三个差异是性能的差异，整体而言大多数场景下，unordered_set的增删查改更快一些，因为红黑树增删查改效率是 $O(logN)$ ，而哈希表增删查平均效率是O(1) ，具体可以参看下面代码的演示的对比差异。

pair<iterator, bool> insert(const value_type& val);
size_type erase(const key_type& k);
iterator find(const key_type& k);
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<iostream>
using namespace std;
int test_set2()
{
	const size_t N = 1000000;
	unordered_set<int> us;
	set<int> s;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand()); // N比较大时，重复值比较多
		v.push_back(rand() + i); // 重复值相对少
		//v.push_back(i); // 没有重复，有序
	}
	// 21:15
	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();
	cout << "set insert:" << end1 - begin1 << endl;
	size_t begin2 = clock();
	us.reserve(N);
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl;
	int m1 = 0;
	size_t begin3 = clock();
	for (auto e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
	int m2 = 0;
	size_t begin4 = clock();
	for (auto e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	size_t end4 = clock();
	cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;
	cout << "插入数据个数：" << s.size() << endl;
	cout << "插入数据个数：" << us.size() << endl << endl;
	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase:" << end5 - begin5 << endl;
	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
	return 0;
}
int main()
{
	test_set2();
	return 0;
}

1.4 unordered_map和map的使用差异

• 查看文档我们会发现unordered_map的支持增删查改且跟map的使用一模一样，关于使用我们这里就不再赘述和演示了。

• unordered_map和map的第一个差异是对key的要求不同，map要求Key支持小于比较，而unordered_map要求Key支持转成整形且支持等于比较，要理解unordered_map的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

• unordered_map和map的第二个差异是迭代器的差异，map的iterator是双向迭代器，
unordered_map是单向迭代器，其次map底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以map迭代器遍历是Key有序+去重。而unordered_map底层是哈希表，迭代器遍历是Key无序+去重。

• unordered_map和map的第三个差异是性能的差异，整体而言大多数场景下，unordered_map的增删查改更快一些，因为红黑树增删查改效率是O(logN) ，而哈希表增删查平均效率是 O(1)，具体可以参看下面代码的演示的对比差异。

pair<iterator, bool> insert(const value_type& val);
size_type erase(const key_type& k);
iterator find(const key_type& k);
mapped_type& operator[] (const key_type& k);

1.5 unordered_multimap/unordered_multiset

• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，支持Key冗余。

• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个方面的差异，
key的要求的差异，iterator及遍历顺序的差异，性能的差异。

1.6 unordered_xxx的哈希相关接口

Buckets和Hash policy系列的接口分别是跟哈希桶和负载因子相关的接口，日常使用的角度我们不需要太关注。

Buckets	接口说明
bucket_count	返回容器中的桶数量
max_bucket_count	返回容器可以拥有的最大桶数
bucket_size	返回桶 n 中的元素数量
bucket	返回元素值 k 所在的桶号

Hash policy	接口说明
load_factor	返回容器中的当前负载因子
max_load_factor	获取或设置最大负载因子
rehash	将容器中的桶数量设置为 n 或更多，如果 n 大于容器中当前的桶数量（bucket_count），则会强制执行重新散列。新的桶数量可以等于或大于 n；如果 n 小于容器中当前的桶数量（bucket_count），该函数可能对桶数量没有影响，也可能不会强制执行重新散列，这取决于底层实现。rehash是哈希表的重建：容器中的所有元素将根据其哈希值重新排列到新的桶集中。这可能改变容器内元素的迭代顺序，当容器的负载因子即将超过其最大负载因子时，容器会自动执行rehash，请注意，此函数需要桶的数量作为参数。存在一个类似的函数 unordered_set::reserve，它需要容器中元素的数量作为参数。
reserve	将容器中的桶数量（bucket_count）设置为最适合至少包含 n 个元素的数量，如果 n 大于当前 bucket_count 乘以 max_load_factor，则容器中的 bucket_count 会增加，并强制进行重新哈希，如果 n 小于这个值，该函数可能没有任何效果(这取决于底层实现)。

二、用哈希表封装myunordered_map和myunordered_set

1. 源码及框架分析

SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只容器的名字是hash_map和hash_set，他是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中hash_map和hash_set的实现结构框架核心部分截取出来如下：

// stl_hash_set
template <class Value, class HashFcn = hash<Value>,
	class EqualKey = equal_to<Value>,
	class Alloc = alloc>
class hash_set
{
private:
	typedef hashtable<Value, Value, HashFcn, identity<Value>,
		EqualKey, Alloc> ht;
	ht rep;
public:
	typedef typename ht::key_type key_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;
	typedef typename ht::const_iterator iterator;
	typedef typename ht::const_iterator const_iterator;
	hasher hash_funct() const { return rep.hash_funct(); }
	key_equal key_eq() const { return rep.key_eq(); }
};
// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>,
	class EqualKey = equal_to<Key>,
	class Alloc = alloc>
class hash_map
{
private:
	typedef hashtable<pair<const Key, T>, Key, HashFcn,
		select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
	ht rep;
public:
	typedef typename ht::key_type key_type;
	typedef T data_type;
	typedef T mapped_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;
	typedef typename ht::iterator iterator;
	typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template <class Value, class Key, class HashFcn,
	class ExtractKey, class EqualKey,
	class Alloc>
class hashtable {
public:
	typedef Key key_type;
	typedef Value value_type;
	typedef HashFcn hasher;
	typedef EqualKey key_equal;
private:
	hasher hash;
	key_equal equals;
	ExtractKey get_key;
	typedef __hashtable_node<Value> node;
	vector<node*, Alloc> buckets;
	size_type num_elements;
public:
	typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
		Alloc> iterator;
	pair<iterator, bool> insert_unique(const value_type& obj);
	const_iterator find(const key_type& key) const;
};
template <class Value>
struct __hashtable_node
{
	__hashtable_node* next;
	Value val;
};

• 这里我们就不再画图分析了，通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复用同一个hashtable实现key和key/value结构，hash_set传给hash_table的是两个key，hash_map传给hash_table的是pair<const key, value>

• 需要注意的是源码里面跟map/set源码类似，命名风格比较乱。下面我们模拟一份自己的出来，就按自己的风格走了。

2. 模拟实现unordered_map和unordered_set

2.1 实现出复用哈希表的框架，并支持insert

• 参考源码框架，unordered_map和unordered_set复用之前我们实现的哈希表。

• 我们这里相比源码调整一下，key参数就用K，value参数就用V，哈希表中的数据类型，我们使用T。

• 其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为HashTable实现泛型时从内部无法知道模版参数T是K，还是pair<K, V>，并且insert内部进行插入时要用K对象转换成整形取模和K比较相等，因为pair的value不参与计算取模，且默认支持的是key和value一起比较相等，我们任何时候只需要比较K对象，所以我们在unordered_map和unordered_set层分别实现一个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K比较相等，具体细节参考如下代码实现。

// MyUnorderedSet.h
namespace zlr
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private:
		hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
	};
}

// MyUnorderedMap.h
namespace zlr
{
	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:
		bool insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
	private:
		hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
	};
}

// HashTable.h
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{
		}
	};
	// 实现步骤：
	// 1、实现哈希表
	// 2、封装unordered_map和unordered_set的框架 解决KeyOfT
	// 3、iterator
	// 4、const_iterator
	// 5、key不支持修改的问题
	// 6、operator[]
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		typedef HashNode<T> Node;
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			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);
			return pos == last ? *(last - 1) : *pos;
		}
	public:
		HashTable()
		{
			_tables.resize(__stl_next_prime(_tables.size()), 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;
			}
		}
		bool Insert(const T& data)
		{
			KeyOfT kot;
			if (Find(kot(data)))
				return false;
			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();
			// 负载因子==1扩容
			if (_n == _tables.size())
			{
				vector<Node*> newtables(__stl_next_prime(_tables.size()),
					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 true;
		}
	private:
		vector<Node*> _tables; // 指针数组
		size_t _n = 0; // 表中存储数据个数
	};
}

2.2 支持iterator的实现

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_set的iterator也不支持修改，因此这里我们就参考前面set/map的设计，我们把unordered_set的第二个模板参数改成const K即可， HashTable<K, const K, SetKeyOfT, Hash> _ht;

• unordered_map的iterator不支持修改key但是可以修改value，我们把unordered_map的第二个模板参数pair的第一个参数改成const K即可， HashTable<K, pair<const K, V>,
MapKeyOfT, Hash> _ht;

在封装迭代器时，与前文map/set中不同，这里因为operator++()遍历，我们需要根据哈希表的数组、哈希函数确定桶的位置，而后面封装的哈希表接口又会返回迭代器，所以这里实际上相互包含，我们需要在迭代器上方声明一下哈希表。

// HashTable.h
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
// 特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 131;
			hash += e;
		}
		return hash;
	}
};

//封装的哈希桶
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)
		{
		}
		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
			{
				// 当前桶走完了，找下一个不为空的桶
				KeyOfT kot;
				Hash hs;
                //取出key,并转换成整形
				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;
		}
	};

    //封装实现的哈希表内部功能
	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);
		}

		inline unsigned long __stl_next_prime(unsigned long n)
		{
			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);
			return pos == last ? *(last - 1) : *pos;
		}

		HashTable()
		{
			_tables.resize(__stl_next_prime(_tables.size()), 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())
			{
				vector<Node*>
					newtables(__stl_next_prime(_tables.size() + 1), 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 = 0; // 表中存储数据个数
	};
}

2.3 map支持[]

• unordered_map要支持[]主要需要修改insert返回值支持，修改HashTable中的insert返回值为
pair<Iterator, bool> Insert(const T& data)。
• 有了insert支持[]实现就很简单了，具体参考下面代码实现

		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())
			{
				vector<Node*>
					newtables(__stl_next_prime(_tables.size() + 1), 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);
		}

2.4 bit::unordered_map和bit::unordered_set代码实现

有了哈希表及其迭代器的封装后，我们在这基础上再封装一层来实现unordered系列容器

// MyUnorderedSet.h
namespace zlr
{
	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 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;
	}
}

// MyUnorderedMap.h
namespace zlr
{
	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();
		}
		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}
		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;
	}
}

// HashTable.h
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
// 特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 131;
			hash += e;
		}
		return hash;
	}
};

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)
		{
		}
		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
			{
				// 当前桶走完了，找下一个不为空的桶
				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;
		}
	};
	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);
		}
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			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);
			return pos == last ? *(last - 1) : *pos;
		}
		HashTable()
		{
			_tables.resize(__stl_next_prime(_tables.size()), 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())
			{
				vector<Node*>
					newtables(__stl_next_prime(_tables.size() + 1), 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 = 0; // 表中存储数据个数
	};
}

【C++】unordered系列容器使用及封装

一、unordered_map和unordered_set的使用

1. unordered_set系列的使用

1.1 unordered_set和unordered_multiset参考文档

1.2 unordered_set类的介绍