【C++高阶七】unorder_set和unorder_map封装

Pacify_The_North

894人浏览 · 2025-08-28 17:43:16

Pacify_The_North · 2025-08-28 17:43:16 发布

【C++高阶七】unorder_set和unorder_map封装

1.unorder_set和unorder_map的使用
2.封装
3.完整代码

1.unorder_set和unorder_map的使用

set和map 与 unordered_set和unordered_map的使用功能基本相同，但是两者的底层结构不同
set和map的底层是红黑树，红黑树是一种搜索二叉树，搜索二叉树又称为排序二叉树，所以迭代器遍历是有序的，在map中存在rbegin以及rend反向迭代器：
在这里插入图片描述

unordered_map和unordered_set的底层是哈希表，而哈希表对应的迭代器遍历是无序的
在unordered_map中不存在rbegin以及rend的反向迭代器：
在这里插入图片描述

unordered_set的使用：大部分功能与set基本相同，要注意的是unordered_set是无序的，插入数据，并使用迭代器打印，会按照插入的顺序输出，但若插入的数据已经存在，则会插入失败
unordered_map的使用：map统计时，会按照元素的ASCII值排序，而unordered_map元素是无序的

2.封装

对于unordered_set和unordered_map的封装是针对于哈希桶HashBucket（哈希开散列）进行的

2.1修改结构

哈希桶HashBucket中我们要修改HashNode的模板参数，从template<class K, class V>修改为template<class T>，同时我们不清楚传入的数据是什么类型的，所以使用T类型的data代替

template<class T>
struct HashNode
{
	HashNode(const pair<K, V>& data)
		: _data(data)
		, _next(nullptr)
	{}

	HashNode<K, V>* _next;//指向下一个节点
	T _data;//记录数据
};

同样我们要对哈希表也进行修改，之前实现的模板参数K,V分别代表key和value，修改后保留第一个K用于拿到单独的K类型以使用Find和Erase等函数，第二个模板参数改为T，第三个仿函数KeyOfT用来决定拿到的数据是K类型还是K,V类型，第四个仿函数Hash不变

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
	typedef HashNode<T> Node;
private:
	vector<Node*> _table;//指针数组
	size_t _num = 0;//存储的数据个数
};

同理Insert函数也要修改函数参数，将pair<K, V>&改为T&，并将内部所有kv改为data

2.2建立set和map并复用哈希桶的insert

创建unordered_set.h头文件并复用哈希桶的insert

#include "HashTable.h"

namespace lhc
{
	template<class K,class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		
		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}
	private:
		Hash_Bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
	};
}

创建unordered_map.h头文件并复用哈希桶的insert

#include "HashTable.h"

namespace lhc
{
	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;
			}
		};

		bool insert(const pair<K,V>& kv)
		{
			return _ht.Insert(kv);
		}
	private:
		Hash_Bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
	};
}

2.3KeyOfT模板参数的作用

在这里插入图片描述
假设为unordered_set，使用kot对象调用operator()，返回的是key
假设为unordered_map，则使用kot对象调用operator()，返回的是KV模型中的key

2.4 迭代器

2.4.1建立迭代器存储节点的指针和哈希表

//前置声明
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable;

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

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

	_HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht,)
		:_node(node)
		,_pht(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
	}
};

template<class K, class T, class KeyOfT,class Hash = HashFunc<K>>
class HashTable
{
	typedef HashNode<T> Node;
public:
	typedef _HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
	typedef _HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
	//......
}

在迭代器内存储节点的指针以及哈希表本身
在迭代器中使用哈希表，在哈希表中使用迭代器，存在相互引用，需要使用前置声明
对于 operator * operator-> operator!= 跟list的模拟实现基本类似
在自己实现的迭代器_HTIterator中，添加参数Ref和Ptr
当为普通迭代器时，Ref作为T& ，Ptr作为T*
当为const迭代器时，Ref作为const T& ，Ptr作为const T*

2.4.2 operator++

Self& operator++()
{
	//当前桶还有节点
	if (_node->_next)
	{
		_node = _node->_next;
	}
	//当前桶走完了，找下一个桶
	else
	{
		Hash hf;
		KeyOfT kot;
		size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
		hashi++;

		if (_hashi == _pht->_table.size())
		{
			_node = nullptr;
		}
		while (_hashi < _pht->_table.size())
		{
			if (_pht->_table[_hashi])
			{
				_node = _pht->_table[_hashi];
				break;
			}
			_hashi++;
		}
	}
	return *this;
}

2.4.3 begin与end

在HashTable内部实现 begin，使用自己实现的_hashiterator 作为迭代器

iterator begin()
{
	for (size_t i = 0; i < _table.size(); i++)
	{
		if (_table[i])
		{
			return iterator(_table[i], this);
		}
	}
	return end();
}

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

unordered_set对于 begin和end的复用：

typedef typename Hash_Bucket::_HTIterator<K, T, T&, T*, KeyOfT, Hash>::const_iterator iterator;
typedef typename Hash_Bucket::_HTIterator<K, T, const T&, const T*, KeyOfT, Hash>::const_iterator const_iterator;

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

在unordered_set中，使用哈希桶中的HashTable的迭代器来实现unordered_set的迭代器
因为编译器无法识别Hash_Bucket::_HTIterator<K, T, T&, T*, KeyOfT, Hash>是静态变量还是类型，加入typename告诉编译器这是类型
在STL中，是不允许 unordered_set去 *it 修改数据的，在STL中将 unordered_set的普通迭代器也为哈希桶的const 迭代器
调用begin时，虽然看似返回普通迭代器，但是当前普通迭代器是作为哈希桶的const迭代器存在的，而返回值依旧是哈希桶的普通迭代器

unordered_map对于 begin和end的复用：

typedef typename Hash_Bucket::_HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
iterator begin()
{
	return _ht.begin();
}
iterator end() 
{
	return _ht.begin();
}

2.4.4 insert修改

pair<iterator,bool> Insert(const T& data)
{
	//负载因子等于1时扩容//first
	Hash hf;
	KeyOfT kot;

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

	if (_num == _table.size())
	{
		size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
		vector<Node*> new_table;
		new_table.resize(newsize, nullptr);

		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* temp = _table[i];
			while (temp)
			{
				Node* next = temp->_next;
				//挪动到新表
				size_t hashi = hf(kot(temp->_data)) % new_table.size();
				temp->_next = new_table[i];
				new_table[hashi] = temp;
				temp = next;
			}
			_table[i] = nullptr;
		}
		_table.swap(new_table);
	}

	size_t hashi = hf(kot(data)) % _table.size();
	Node* newnode = new Node(data);
	//头插
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;
	_num++;

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

将insert的返回值变为pair类型，第一个参数为迭代器，第二个参数为布尔值
若返回成功，则调用新插入位置的迭代器
过Find寻找哈希桶中是否有相同的数据，若有则返回该迭代器以及false

2.4.5operator[]

unordered_map中operator[]的实现：

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

3.完整代码

HashTable.h

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

using namespace std;

//仿函数
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 *= 31;//乘31或者131都行，为了避免数字重复
			hash += e;
		}
		return hash;
	}
};

//开散列（哈希桶）
namespace Hash_Bucket
{
	template<class T>
	struct HashNode
	{
		HashNode(const pair<K, V>& data)
			: _data(data)
			, _next(nullptr)
		{}

		HashNode<K, V>* _next;//指向下一个节点
		T _data;//记录数据
	};

	//前置声明
	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
	class HashTable;

	//迭代器
	template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
	struct _HTIterator
	{
		typedef HashNode<T> Node;
		typedef _HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

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

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

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

		Self& operator++()
		{
			//当前桶还有节点
			if (_node->_next)
			{
				_node = _node->_next;
			}
			//当前桶走完了，找下一个桶
			else
			{
				Hash hf;
				KeyOfT kot;
				size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
				hashi++;

				if (_hashi == _pht->_table.size())
				{
					_node = nullptr;
				}
				while (_hashi < _pht->_table.size())
				{
					if (_pht->_table[_hashi])
					{
						_node = _pht->_table[_hashi];
						break;
					}
					_hashi++;
				}
			}
			return *this;
		}

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

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

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

	//哈希表
	template<class K, class T, class KeyOfT,class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<T> Node;
	public:
		typedef _HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef _HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i])
				{
					return iterator(_table[i], this);
				}
			}
			return end();
		}

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

		pair<iterator,bool> Insert(const T& data)
		{
			//负载因子等于1时扩容//first
			Hash hf;
			KeyOfT kot;

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

			if (_num == _table.size())
			{
				size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
				vector<Node*> new_table;
				new_table.resize(newsize, nullptr);

				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* temp = _table[i];
					while (temp)
					{
						Node* next = temp->_next;
						//挪动到新表
						size_t hashi = hf(kot(temp->_data)) % new_table.size();
						temp->_next = new_table[i];
						new_table[hashi] = temp;
						temp = next;
					}
					_table[i] = nullptr;
				}
				_table.swap(new_table);
			}

			size_t hashi = hf(kot(data)) % _table.size();
			Node* newnode = new Node(data);
			//头插
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_num++;

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

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

			if (_table.size() == 0)
			{
				return nullptr;
			}

			size_t i = hf(key) % _table.size();
			Node* temp = _table[i];
			while (temp)
			{
				if (kot(temp->_kv) == key)
				{
					return temp;
				}
				temp = temp->_next;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Hash hf;
			KeyOfT kot;

			size_t i = hf(key) % _table.size();
			Node* prev = nullptr;//记录前一个结点
			Node* temp = _table[i];
			while (temp)
			{
				if (kot(temp->_kv) == key)
				{
					if (prev == nullptr)//删除头节点
					{
						_table[i] = temp->_next;
					}
					else
					{
						prev->_next = temp->_next;
					}
					delete temp;
					return true;
				}
				prev = temp;
				temp = temp->_next;
			}
			return false;
		}
	private:
		vector<Node*> _table;//指针数组
		size_t _num = 0;//存储的数据个数
	};
}

My_unordered_set.h

#pragma once
#include "HashTable.h"

namespace lhc
{
	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::_HTIterator<K, T, T&, T*, KeyOfT, Hash>::const_iterator iterator;
		typedef typename Hash_Bucket::_HTIterator<K, T, const T&, const T*, KeyOfT, Hash>::const_iterator const_iterator;

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

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

My_unordered_map.h

#pragma once
#include "HashTable.h"

namespace lhc
{
	template<class K, class V,class Hash = HashFunc<K>>
	class unordered_map
	{
	public:
		typedef typename Hash_Bucket::_HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end() 
		{
			return _ht.begin();
		}

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

		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};
		bool insert(const pair<K,V>& kv)
		{
			return _ht.Insert(kv);
		}
	private:
		Hash_Bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
	};
}