当前位置：首页 > article >正文

C++：unordered_map与unordered_set详解

article 2024/12/5 3:27:40

在这里插入图片描述

文章目录

前言
一、KeyOfT
- 1. 为什么需要仿函数？
- 2. MapKeyOfT与SetKeyOfT代码实现
二、迭代器
- 1. 设计背景
- 2. 为什么需要存储哈希表指针
- 3. operator++ 的逻辑
- 4. begin() 和 end() 的实现
- 5. 友元和前置声明的作用
- 6. 完整代码
三、迭代器map与set的复用
- 1. map的复用，数据pair<K, V>
- 2. Set的复用，数据Key
- 3. 测试代码_1
四、const迭代器——增加Ref与Ptr模板参数
五、const迭代器权限放大的问题
六、解决值不能修改的问题
七、解决Insert返回值改为pair<iterator, bool>中Set的大坑
八、operator[ ]
unordered_map与unordered_set封装代码总结

前言

参考源码框架，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 比较相等。

具体细节参考如下代码实现。

一、KeyOfT

1. 为什么需要仿函数？

首先还是老问题，因为map与set存储的数据不同，泛型编程我们将数据改为T后对于map来说就是pair<K, V>，对于set来说就是key。

因此我们在插入的时候，比如要取出原来的kv.first全部都要变成kot(data)。

在这里插入图片描述

这样用：
在这里插入图片描述

在这里插入图片描述

2. MapKeyOfT与SetKeyOfT代码实现

#pragma once
#include"HashTable.h"

namespace jyf
{
	template<class K, class V>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:

	private:
		hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
	};
}

#pragma once
#include"HashTable.h"

namespace jyf
{
	template<class K>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:

	private:
		hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
	};
}

二、迭代器

接下来我们来实现迭代器：

1. 设计背景

哈希表的数据存储分散在多个桶（bucket）中，每个桶可能是一个链表，存储若干节点。因此，迭代器的实现不仅需要遍历链表中的节点，还需要跳跃到下一个非空桶继续遍历。为了实现这一功能，需要一个特殊的迭代器 HTIterator。

2. 为什么需要存储哈希表指针

HTIterator 除了保存当前节点指针 _node，还需要保存一个指向哈希表对象的指针 _pht，主要原因是为了跨桶查找下一个节点：

template<class K, class T, class KeyOfT, class HashFunc>
struct HTIterator
{
	typedef HashNode<T> Node;
	typedef HTIterator<K, T, KeyOfT, HashFunc> Self;

	Node* _node;
	HashTable<K, T, KeyOfT, HashFunc>* _pht;

	HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
		:_node(node)
		, _pht(pht)
	{}

桶定位需要哈希表结构：
- 当遍历完当前桶后，operator++ 需要从当前桶的索引位置开始，查找下一个不为空的桶。
- 这些桶存储在哈希表的 _table 成员中，迭代器需要通过 _pht 访问它。
简化设计：
- 如果不存储哈希表指针，HTIterator 无法跨桶查找下一个节点，导致实现复杂且效率低下。
- 存储 _pht 后，可以直接使用哈希表的结构信息（如桶的数量和内容）进行遍历。
提升代码灵活性：
- _pht 提供了迭代器与哈希表的关联性，使得 HTIterator 能够独立于具体的哈希表实现，在其他类似结构中复用。

3. operator++ 的逻辑

operator++ 的核心任务是移动迭代器到下一个可访问的节点。分为两种情况：

当前桶的链表还有剩余节点：
- 如果当前节点有 _next 指针，直接移动到链表中的下一个节点。
当前桶已经遍历完：
- 获取当前桶索引： 根据当前节点的数据，通过哈希函数计算出当前桶的索引。
- 查找下一个非空桶：
  - 从当前桶的下一个位置开始遍历 _table。
  - 找到第一个不为空的桶后，将 _node 指向该桶的第一个节点。
  - 如果遍历到表尾仍未找到，将 _node 设置为 nullptr，表示迭代结束。

在这里插入图片描述

再次理解为什么要存储哈希表指针，如下图，我们需要表的数据记录hashi以及size。

在这里插入图片描述

代码实现：

Self& operator++()
{
	if (_node->_next)
	{
		// 当前桶还没完
		_node = _node->_next;
	}
	else
	{
		KeyOfT kot;
		HashFunc hf;
		size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
		// 从下一个位置查找查找下一个不为空的桶
		++hashi;
		while (hashi < _pht->_table.size())
		{
			if (_pht->_table[hashi])
			{
				_node = _pht->_table[hashi];
				return *this;
			}
			else
			{
				++hashi;
			}
		}

		_node = nullptr;
	}

	return *this;
}

4. begin() 和 end() 的实现

begin()：
- 从第一个桶开始查找，找到第一个非空桶，返回其第一个节点对应的迭代器。
- 如果所有桶为空，返回空迭代器（iterator(nullptr, this)）。
end()：
- 返回一个空迭代器（iterator(nullptr, this)），用于标志迭代结束。

5. 友元和前置声明的作用

前置声明：
- HTIterator 的定义在 HashTable 之后依赖于 HashTable 的定义，但 HashTable 的接口（如 begin()、end()）需要返回 HTIterator。
- 前置声明解决了这种相互依赖的问题，确保在定义 HashTable 时能够使用 HTIterator。

在这里插入图片描述

友元声明：
- HTIterator 需要访问 HashTable 的私有成员 _table 和 _table.size()，这是其实现 operator++ 所必需的。
- 通过友元声明，使 HTIterator 可以直接访问 HashTable 的私有成员，简化了代码设计。

在这里插入图片描述

6. 完整代码

#pragma once
#include

namespace hash_bucket
{
template
struct DefaultHashFunc
{
size_t operator() (const K& key)
{
return (size_t)key;
}
};

template<>
struct DefaultHashFunc<string>
{
	size_t operator() (const string& str)
	{
		// BKDR
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

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 HashFunc>
class HashTable;

template<class K, class T, class KeyOfT, class HashFunc>
struct HTIterator
{
	typedef HashNode<T> Node;
	typedef HTIterator<K, T, KeyOfT, HashFunc> Self;

	Node* _node;
	HashTable<K, T, KeyOfT, HashFunc>* _pht;

	HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
		:_node(node)
		, _pht(pht)
	{}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		if (_node->_next)
		{
			// 当前桶还没完
			_node = _node->_next;
		}
		else
		{
			KeyOfT kot;
			HashFunc hf;
			size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
			// 从下一个位置查找查找下一个不为空的桶
			++hashi;
			while (hashi < _pht->_table.size())
			{
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					return *this;
				}
				else
				{
					++hashi;
				}
			}

			_node = nullptr;
		}

		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
	typedef HashNode<T> Node;

	// 友元声明
	template<class K, class T, class KeyOfT, class HashFunc>
	friend struct HTIterator;
public:
	typedef HTIterator<K, T, KeyOfT, HashFunc> iterator;

	iterator begin()
	{
		// 找第一个桶
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			if (cur)
			{
				return iterator(cur, this);
			}
		}

		return iterator(nullptr, this);
	}

	iterator end()
	{
		return iterator(nullptr, this);
	}

	HashTable()
	{
		_table.resize(10, nullptr);
	}

	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}

			_table[i] = nullptr;
		}
	}

	bool Insert(const T& data)
	{
		// 仿函数控制
		KeyOfT kot;

		if (Find(kot(data)))
		{
			return false;
		}

		// 仿函数控制
		HashFunc hf;

		// 如果需要扩容
		if (_n == _table.size())
		{
			size_t newSize = _table.size() * 2;
			vector<Node*> newTable;
			newTable.resize(newSize, nullptr);

			// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;

					// 头插到新表
					size_t newhashi = hf(kot(cur->_data)) % newSize;
					cur->_next = newTable[newhashi];
					newTable[newhashi] = cur;

					cur = next;
				}

				_table[i] = nullptr;
			}

			_table.swap(newTable);
		}

		// 如果不需要扩容
		size_t hashi = hf(kot(data)) % _table.size();

		// 头插
		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;

		++_n;
		return true;
	}

	Node* Find(const K& key)
	{
		HashFunc hf;
		KeyOfT kot;

		size_t hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];

		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return cur;
			}

			cur = cur->_next;
		}

		return nullptr;
	}

	bool Erase(const K& key)
	{
		HashFunc hf;
		KeyOfT kot;

		size_t hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];
		Node* prev = nullptr;

		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					_table[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}

				delete cur;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}

		return false;
	}

	void Print()
	{
		KeyOfT kot;

		for (size_t i = 0; i < _table.size(); i++)
		{
			printf("[%d]->", i);
			Node* cur = _table[i];
			while (cur)
			{
				cout << cur->_kv.first << ":" << cur->_kv.second << "->";
				cur = cur->_next;
			}
			printf("NULL\n");
		}
		cout << endl;

	}

private:
	vector<Node*> _table;     // 指针数组
	size_t _n = 0;            // 存储了多少个有效数据
};

}

三、迭代器map与set的复用

1. map的复用，数据pair<K, V>

#pragma once
#include"HashTable.h"

namespace jyf
{
	template<class K, class V>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		bool insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

	private:
		hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
	};
}

2. Set的复用，数据Key

#pragma once
#include"HashTable.h"

namespace jyf
{
	template<class K>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

		iterator end()
		{
			return _ht.end();
		}

		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private:
		hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
	};
}

3. 测试代码_1

#include <iostream>
using namespace std;

#include"UnOrderedMap.h"
#include"UnOrderedSet.h"

int main()
{
	jyf::unordered_set<int> us;
	us.insert(3);
	us.insert(1);
	us.insert(3);
	us.insert(4);
	us.insert(5);
	us.insert(0);

	jyf::unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	jyf::unordered_map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("insert", "插入"));
	dict.insert(make_pair("sort", "xxx"));

	for (auto& kv : dict)
	{
		cout << kv.first << ":" << kv.second << endl;
	}

	return 0;
}

运行结果：
在这里插入图片描述

四、const迭代器——增加Ref与Ptr模板参数

const迭代器复用普通迭代器的代码，唯一不同的是operator*与operator->的返回值，const迭代器返回的是const T*与const T&，因此我们加入两个模板参数Ref与Ptr，通过typedef，我们实例化的时候就可以获得两种模式的迭代器：

在这里插入图片描述

这样子使用：
在这里插入图片描述

对于const迭代器来说：

const_iterator begin() const
{
	// 找第一个桶
	for (size_t i = 0; i < _table.size(); i++)
	{
		Node* cur = _table[i];
		if (cur)
		{
			return const_iterator(cur, this);
		}
	}

	return const_iterator(nullptr, this);
}

const_iterator end() const
{
	return const_iterator(nullptr, this);
}

五、const迭代器权限放大的问题

上述const迭代器还没有结束，const迭代器对于哈希这里还有一个坑！

在这里插入图片描述

那我们提供一个重载，用const HashTable<>*来接收可不可以呢？
在这里插入图片描述

因此我们需要把成员变量直接设置为const HashTable<>*
在这里插入图片描述
当然这样做了之后，我们就可以不用提供非const版本了~

在这里插入图片描述

六、解决值不能修改的问题

对于Set来说，key不可以修改，对于Map来说，pair<K,V>中的K不能修改，因此我们需要采取对应的措施。

对于Set来说：

普通迭代器与const迭代器都是const迭代器

对于Map来说：

Map的成员中的pair改为pair<const K, V>
迭代器正常走：

测试代码：

jyf::unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(3);
us.insert(4);
us.insert(5);
us.insert(0);

jyf::unordered_set<int>::iterator it = us.begin();
while (it != us.end())
{
	// 不能修改key
	//*it += 10;
	cout << *it << " ";
	++it;
}
cout << endl;

jyf::unordered_map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("insert", "插入"));
dict.insert(make_pair("sort", "xxx"));

jyf::unordered_map<string, string>::iterator dit = dict.begin();
while (dit != dict.end())
{
	// 不能修改key
	//dit->first += 'x';
	dit->second += 'x';

	cout << dit->first << ":" << dit->second << endl;


	++dit;
}
cout << endl;

七、解决Insert返回值改为pair<iterator, bool>中Set的大坑

接下来要做Insert返回值的修改，为重载operator[ ]做准备：

第一步，更改返回值：
在这里插入图片描述

第二步：find返回值也要对应修改
在这里插入图片描述

这里就会出现大问题：
现在跑不过了，是因为Set的大坑！
在这里插入图片描述

对于Map来说：
在这里插入图片描述

对于Set来说：
在这里插入图片描述

因此我们需要提供const_iterator的构造函数，使用iterator构造const_iterator.

在这里插入图片描述

八、operator[ ]

对于Map，我们还需要重载operator[]，就像数组一样使用，可以插入，也可以查找，改Value。

这里我们要借助insert实现。

V& operator[] (const K& key)
{
	pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
	return ret.first->second;
}

unordered_map与unordered_set封装代码总结

HashTable.h

#pragma once
#include<vector>
#include <string>


namespace hash_bucket
{
	template<class K>
	struct DefaultHashFunc
	{
		size_t operator() (const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct DefaultHashFunc<string>
	{
		size_t operator() (const string& str)
		{
			// BKDR
			size_t hash = 0;
			for (auto ch : str)
			{
				hash *= 131;
				hash += ch;
			}

			return hash;
		}
	};

	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 HashFunc>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;

		typedef HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

		Node* _node;
		const HashTable<K, T, KeyOfT, HashFunc>* _pht;

		/*HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			, _pht(pht)
		{}*/

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			, _pht(pht)
		{}

		// 普通迭代器时，他是拷贝构造
		// const迭代器时，他是构造
		HTIterator(const iterator& it)
			: _node(it._node)
			, _pht(it._pht)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				// 当前桶还没完
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
				// 从下一个位置查找查找下一个不为空的桶
				++hashi;
				while (hashi < _pht->_table.size())
				{
					if (_pht->_table[hashi])
					{
						_node = _pht->_table[hashi];
						return *this;
					}
					else
					{
						++hashi;
					}
				}

				_node = nullptr;
			}

			return *this;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}
	};

	template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
		typedef HashNode<T> Node;

		// 友元声明
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
		friend struct HTIterator;
	public:
		typedef HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;
		typedef HTIterator<K, T, const T&, const T*, KeyOfT, HashFunc> const_iterator;

		iterator begin()
		{
			// 找第一个桶
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					return iterator(cur, this);
				}
			}

			return iterator(nullptr, this);
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin() const
		{
			// 找第一个桶
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					return const_iterator(cur, this);
				}
			}

			return const_iterator(nullptr, this);
		}

		const_iterator end() const
		{
			return const_iterator(nullptr, this);
		}

		HashTable()
		{
			_table.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				_table[i] = nullptr;
			}
		}

		pair<iterator, bool> Insert(const T& data)
		{
			// 仿函数控制
			KeyOfT kot;

			iterator it = Find(kot(data));
			if (it != end())
			{
				return make_pair(it, false);
			}

			// 仿函数控制
			HashFunc hf;

			// 如果需要扩容
			if (_n == _table.size())
			{
				size_t newSize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);

				// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						// 头插到新表
						size_t newhashi = hf(kot(cur->_data)) % newSize;
						cur->_next = newTable[newhashi];
						newTable[newhashi] = cur;

						cur = next;
					}

					_table[i] = nullptr;
				}

				_table.swap(newTable);
			}

			// 如果不需要扩容
			size_t hashi = hf(kot(data)) % _table.size();

			// 头插
			Node* newnode = new Node(data);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;

			++_n;
			return make_pair(iterator(newnode, this), true);
		}

		iterator Find(const K& key)
		{
			HashFunc hf;
			KeyOfT kot;

			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];

			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}

				cur = cur->_next;
			}

			return end();
		}

		bool Erase(const K& key)
		{
			HashFunc hf;
			KeyOfT kot;

			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;

			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

		void Print()
		{
			KeyOfT kot;

			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->_next;
				}
				printf("NULL\n");
			}
			cout << endl;

		}

	private:
		vector<Node*> _table;     // 指针数组
		size_t _n = 0;            // 存储了多少个有效数据
	};
}

UnOrderedMap.h

#pragma once
#include"HashTable.h"

namespace jyf
{
	template<class K, class V>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator 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;
		}

	private:
		hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
	};
}

UnOrderedSet.h

#pragma once
#include"HashTable.h"

namespace jyf
{
	template<class K>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;

		const_iterator begin() const
		{
			return _ht.begin();
		}

		const_iterator end() const
		{
			return _ht.end();
		}

		pair<iterator, bool> insert(const K& key)
		{
			pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
			return pair<iterator, bool>(ret.first, ret.second);
		}
	private:
		hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
	};
}

test.cpp

#include <iostream>
using namespace std;

#include"UnOrderedSet.h"
#include"UnOrderedMap.h"

int main()
{
	jyf::unordered_set<int> us;
	us.insert(3);
	us.insert(1);
	us.insert(3);
	us.insert(4);
	us.insert(5);
	us.insert(0);

	jyf::unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		// 不能修改key
		//*it += 10;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	jyf::unordered_map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("insert", "插入"));
	dict.insert(make_pair("sort", "xxx"));

	jyf::unordered_map<string, string>::iterator dit = dict.begin();
	while (dit != dict.end())
	{
		// 不能修改key
		//dit->first += 'x';
		dit->second += 'x';

		cout << dit->first << ":" << dit->second << endl;


		++dit;
	}
	cout << endl;

	dict["sort"] = "排序";
	dict["insert"] = "插入";
	dict["string"] = "字符串";
	dict["right"];

	for (auto& kv : dict)
	{
		cout << kv.first << ":" << kv.second << endl;
	}

	return 0;
}