• 利用哈希表封装unordered_map和unordered_set

    目录

    一、迭代器

    1.1 普通迭代器

    1.1.1 operator++

    对于哈希桶结构，它的迭代器应该如何设计呢？我们仅封装一个Node的指针就行了吗？其实这里是仅用一个指针是不够的，因为在迭代器重载operator++的时候，如果当前位置的链表还没有遍历完，那就是直接_node=_node->_next就行了，但是如果哈希表中当前位置的链表已经遍历完了，那么就要计算当前迭代器是在哈希表中的哪一个位置，然后从哈希表的下一个位置开始遍历找出下一个不为空的_node，这个_node构造的迭代器就是iterator++的结果，所以现在的问题是我们要知道当前迭代器在哪一个桶，就要知道这个哈希表的size，然后用_node->_data的key%size得到的余数才是当前的位置，但是_node节点中并没有size呀，所以我们选择把哈希表的指针传过来，有这个表的指针就什么数据都有啦！
    所以迭代器应该有一个Node    和一个HashTable*构成。

    代码实现：

    		Self& operator++()
		{
			KeyOfT kot;
			HashFunc hf;
			Node* cur = _node;
			//如果当前桶的链表还没有遍历完，那就遍历链表的下一个节点就好了
			if (_node && _node->_next)
			{
				_node = _node->_next;
			}
			//如果当前桶的链表已经遍历完了，就要在哈希表中往后找下一个不为空的链表的节点
			else
			{
				//重点
				if (_node)
				{
					//利用两层仿函数把_node->_data的key以及key对应的整形取出来，并且通过
					//HashTable的指针取出哈希表的size，通过除留余数法计算出当前桶的位置。
					size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
					//然后++hashi从哈希表的下一个桶开始往后找不为空的链表节点
					hashi++;
					for (size_t i = hashi; i < _pht->_table.size(); i++)
					{
						//找到不为空的节点，那么这个节点就是迭代器下一个要访问的链
						// 表的头节点，即把_node更新为这个节点即可
						if (_pht->_table[i] != nullptr)
						{
							_node = _pht->_table[i];
							return *this;
						}
					}
					//来到这里说明找完了整个哈希表都没有找到一个不为空的链表，说明哈希表
					//已经遍历完了，这时要把_node设置为nullptr，表示到达了结尾
					_node = nullptr;
				}
			}

			return *this;
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    1.2 const迭代器

    在这里插入图片描述

    1.3 代码实现

    	//利用哈希桶封装unordered_map和unordered_set时，因为unordered_map和unordered_set存储的数据
	//的类型不一样，unordered_map存放的是pair，而unordered_set存储的是key，所以我们要
	// 把要存储的类型设置成模板参数，具体类型是什么由用户实例化的时候指定，如果是unordered_set就是T就
	//是key，如果是unordered_map那么T就是pair
	template <class T>
	struct HashNode
	{
		//T具体是什么我不管，反正把它设置成模板参数
		//_data根据这个模板参数的类型来定义
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};

	//前置声明，因为迭代器里面用了HashTable，而HashTable是在后面定义的，编译器编译时只会从前面的代码
	//找，所以这里需要声明一下HashTable是存在的，否则编译器会报错，声明时需要带上模板参数
	template <class K, class T, class KeyOfT, class HashFunc>
	class HashTable;

	//迭代器，因为迭代器里面需要用到HashTable中的size来计算当前桶的位置，所以我们需要
	//把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;

		//无论是构造普通迭代器对象还是const迭代器对象，这个iterator都是写死的普通迭代器
		//目的是写一个使用普通迭代器构造const迭代器的构造函数
		typedef HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

		typedef HashTable<K, T, KeyOfT, HashFunc> HT;


		//节点指针
		Node* _node;

		//哈希表的指针
		//这里HT*一定要加上const修饰，因为下面的构造函数的第二个参数是const HT* pth，所以
		//在初始化列表赋值的时候是const类型的指针赋值给这个_pht，如果这里不用const类型，就
		//等于是权限放大，会报错，所以这两个pht都必须是const类型的
		const HT* _pht;

		//这里的HT一定要加上const修饰，否则会报错，因为传过来的pht指针可能是const修饰的
		//如果这里不用const HT* 接收，那么HT* pht无法接收const修饰的指针，等于是const
		//类型赋值给了普通类型，权限放大，这里会报错
		HTIterator(Node* node,const HT* pht)
			:_node(node)
			,_pht(pht)
		{}

		//重点：类模板传不同的模板参数得到的是不同的类型

		//1、当HTIterator构造的是const迭代器对象时，这个函数是一个构造函数。因为iterator本身是一个普通迭代器，
		// 当HTIterator构造的对象是一个const迭代器的时候，这两个迭代器的类型并不相同，所以这是一个构造函数，
		//即该函数是用一个普通迭代器构造一个const迭代器。
		// 
		//2、当HTIterator构造的是一个普通迭代器对象时，这个函数是一个拷贝构造函数。因为iterator本身是一个普通迭代器，
		//当HTIterator构造的对象也是一个普通迭代器时，这两个迭代器的类型是相同的，所以这是一个拷贝构造函数，即该函
		// 数用一个普通迭代器拷贝构造一个普通迭代器
		HTIterator(const iterator& it)
			:_node(it._node)
			,_pht(it._pht)
		{}


		Self& operator++()
		{
			KeyOfT kot;
			HashFunc hf;
			Node* cur = _node;
			//如果当前桶的链表还没有遍历完，那就遍历链表的下一个节点就好了
			if (_node && _node->_next)
			{
				_node = _node->_next;
			}
			//如果当前桶的链表已经遍历完了，就要在哈希表中往后找下一个不为空的链表的节点
			else
			{
				//重点
				if (_node)
				{
					//利用两层仿函数把_node->_data的key以及key对应的整形取出来，并且通过
					//HashTable的指针取出哈希表的size，通过除留余数法计算出当前桶的位置。
					size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
					//然后++hashi从哈希表的下一个桶开始往后找不为空的链表节点
					hashi++;
					for (size_t i = hashi; i < _pht->_table.size(); i++)
					{
						//找到不为空的节点，那么这个节点就是迭代器下一个要访问的链
						// 表的头节点，即把_node更新为这个节点即可
						if (_pht->_table[i] != nullptr)
						{
							_node = _pht->_table[i];
							return *this;
						}
					}
					//来到这里说明找完了整个哈希表都没有找到一个不为空的链表，说明哈希表
					//已经遍历完了，这时要把_node设置为nullptr，表示到达了结尾
					_node = nullptr;
				}
			}

			return *this;
		}

		//*解引用返回的是节点存储的数据的引用
		Ref operator*()
		{
			return _node->_data;
		}

		//->是返回的是节点存储的数据的地址
		Ptr operator->()
		{
			return &_node->_data;
		}

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

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

	};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133

    二、封装unordered_set

    template <class K>
class Unordered_Set
{
public:
	//仿函数，用于取出节点存放的数据的类型
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	//和红黑树的原理一样，这里的unordered_set的key值也是不能被修改的，所以只向外面提供了const_iterator，
	//因为这里的iterator本质也是const_iterator
	typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;

	void Print() const
	{
		_ht.SetPrint();
	}

	pair<const_iterator,bool> insert(const K& key)
	{
		//Insert返回的是普通迭代器，无法直接转化成const迭代器。因为就算是同一个类模板，当我们传的模板参数不同时
		//它们是两个不同的类型，不同类型无法直接转化，需要先用普通迭代器的pair接收Insert的返回值，然后再在迭代器
		// 类中增加一个由普通迭代器构造const迭代器的构造函数，这样我们才能构造出一个const迭代器作为该insert函数
		//的返回值
		pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);

		//ret.first是普通迭代器，而pair的第一个参数是const迭代器，所以这里实际是利用一个普通迭代器构造出
		//一个const迭代器，所以会调用iterator的构造函数构造出一个const迭代器，再用const迭代器构造pair
		//所以在迭代器中必须提供一个由iterator构造const_iterator的构造函数，否则会报错的
		return pair<const_iterator, bool>(ret.first, ret.second);
	}

	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}

	//因为set的key是不可修改的，所以只需要提供一个const版本的迭代器就可以了
	const_iterator begin() const
	{
		return _ht.begin();
	}

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

	iterator find(const K& key)
	{
		return _ht.Find(key);
	}

private:
	//虽然对于unordered_set来说只存储一个K，但是为了能够和unordered_map更好地复用
	//同一份代码，所以这里的unordered_set也是采用了和unordered_map同样的K-V模型存
	//储数据，所以需要传两个K，第一个K表示节点的key值，第二个K表示节点存储的数据的类型
	//两个K的含义是不一样的
	hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    三、封装unordered_map

    template <class K,class V>
class Unordered_Map
{
public:
	//仿函数，用于取出节点存放的数据的类型
	struct MapKeyOfT
	{
		const K& operator()(const pair<const K,V>& kv)
		{
			return kv.first;
		}
	};

	//普通迭代器，因为对于unordered_map来说，key值是不能修改的，但是value值是可以被修改的，所以我们不能像
	//unordered_set那样直接把两个迭代器都设计成const迭代器，那样的话这里的value也不能修改了，所以我们在
	//pair的key前加上const修饰，这样的话pair的key就不能被修改，而value是可以被修改的
	// 
	//同时这里要加上typename告诉编译器hash_bucket::HashTable, MapKeyOfT>::iterator
	//是一个类型，否则会报错
	typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
	//const迭代器
	typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

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

	bool erase(const K& key)
	{
		return _ht.Erase(key);
	}

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

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

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

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

	void Print() const
	{
		_ht.MapPrint();
	}

	iterator find(const K& key)
	{
		return _ht.Find(key);
	}

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

private:
	//同时这里也要的pair也要加上const
	//这里的K代表存放的数据的类型，pair代表节点存放的数据的类型
	hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    以上就是利用哈希表封装unordered_map以及unordered
    _set的内容啦，因为unordered_map和unordered的接口太多了，这里只是把插入接口和迭代器封装出来，其它的接口就不一一封装了，感兴趣的老铁可以自己尝试一下封装其它有用的接口哟。以上就是今天想要跟大家分享的内容咯，你学会了吗？如果你感觉到有所收获，可以点点小心心，点点关注哦，后期还会持续更新C++的相关知识哦，我们下期见！！！！！！！！！！！

  • 相关阅读:
    免费AI软件开发工具测评：iFlyCode VS CodeFlying
    SIT1044 5V 供电，IO 口兼容 3.3V，5Mbps，(CAN FD)待机模式总线收发器
    Gmail发送邮件的配置方法
    Node.js 零基础入门 Node.js 零基础入门第三天 3.3 Express 中间件
    【附源码】计算机毕业设计java智慧后勤app设计与实现
    【数据结构】 双向循环链表链表的实现
    网课查题公众号搭建——内含查题接口及独立后台
    基于微信小程序的高校毕业论文管理系统#毕业设计
    《论文阅读》Generating Responses with a Specific Emotion in Dialog
    软件测试缺陷报告---定义，组成，缺陷的生命周期，缺陷跟踪产后处理流程，缺陷跟踪处理流程，缺陷跟踪的目的，缺陷管理工具
  • 原文地址：https://blog.csdn.net/weixin_70056514/article/details/133025437