C++修炼：unordered_map和unordered_set的使用和封装

        Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》

欢迎点赞，关注！

        这一期我们来讲解并模拟实现unordered_map和unordered_set。有了前面的铺垫，这一篇就要相对简单很多了。

1、unordered_set和unordered_map的使用

        在C++标准模板库(STL)中，unordered_set和unordered_map是两种非常重要的关联容器，它们基于哈希表实现，提供了高效的查找、插入和删除操作。本文将详细讲解这两种容器的特性、用法、内部实现原理。

      1.1、unordered_set的使用

        unordered_set是一个存储唯一元素的容器，其中每个元素的值同时也是它的键。

        我们把unordered_set的使用快速过一遍。因为在日常使用中，unordered_set的使用和set的使用很相似。接口都是类似的。

#include <unordered_set>
#include <iostream>

int main() {
    // 创建unordered_set
    std::unordered_set<int> numbers = {1, 2, 3, 4, 5};
    
    // 插入元素
    numbers.insert(6);
    numbers.emplace(7);  // 更高效的插入方式
    //下两篇会详细讲解emplace接口
    
    // 查找元素
    if (numbers.find(3) != numbers.end()) {
        std::cout << "3 found in the set\n";
    }
    
    // 删除元素
    numbers.erase(4);
    
    // 遍历元素
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << "\n";
    
    // 获取大小
    std::cout << "Size: " << numbers.size() << "\n";
    
    return 0;
}

         unordered_set的主要特性：

                唯一性：容器中不允许有重复的元素

                无序性：元素不以任何特定顺序存储

                哈希实现：基于哈希表实现，平均情况下提供O(1)的查找复杂度

                动态大小：容器可以根据需要动态扩展或收缩

        我们可以把unordered_set理解成不能排序的set，并且unordered_set的插入，删除，查找平均时间复杂度都是O(1)，效率比set要高。

         1.2、unordered_map的使用

        unordered_map是存储键值对的关联容器，其中每个键都是唯一的。与map不同unordered_map中的元素不以任何特定顺序排序。

        操作我们也不细讲了，因为常用接口和map的接口都差不多。

#include <unordered_map>
#include <iostream>
#include <string>

int main() {
    // 创建unordered_map
    std::unordered_map<std::string, int> word_counts = {
        {"apple", 5},
        {"banana", 3}
    };
    
    // 插入元素
    word_counts.insert({"orange", 2});
    word_counts["pear"] = 4;  // 使用下标操作符插入
    
    // 访问元素
    std::cout << "apple count: " << word_counts["apple"] << "\n";
    
    // 查找元素
    auto it = word_counts.find("banana");
    if (it != word_counts.end()) {
        std::cout << "banana count: " << it->second << "\n";
    }
    
    // 删除元素
    word_counts.erase("orange");
    
    // 遍历元素
    for (const auto& pair : word_counts) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }
    
    // 获取大小
    std::cout << "Size: " << word_counts.size() << "\n";
    
    return 0;
}

        unordered_map的主要特性：

                键唯一性：每个键只能在容器中出现一次

                无序性：键值对不以任何特定顺序存储

                哈希实现：基于哈希表实现，平均情况下提供O(1)的访问复杂度

                快速访问：通过键可以直接访问对应的值

               如果我们想要支持自定义类型的比较和存储，需要让自定义类型支持哈希映射和==的比较。unordered_map和unordered_set同理。

#include<iostream>
#include<unordered_map>
#include<unordered_set>
using namespace std;

struct node
{
	int _a;
	int _b;

	bool operator==(const node& x) const
	{
		return (_a == x._a) && (_b == x._b);
	}
};

class A
{
public:
	//需要注意仿函数的重载()一定是public:
	size_t operator()(const node& x) const
	{
		int ret = x._a;
		ret *= 131;
		ret += x._b;
		ret *= 131;

		return ret;
	}
};

int main()
{
	unordered_set<node, A> s;
	unordered_map<node, string, A> mp;

	s.insert({ 1,1 });
	s.insert({ 2,2 });
	node x = { 1,1 };
	mp[{1, 2}] = "11";
	node x1 = { 2,3 };
	mp.insert({x1, "ss"});//传入pair(key,value)

	return 0;
}

 2、unordered_map和unordered_set的封装

        基于我们上节课实现的哈希表，我们对unordered_set和unordered_map进行封装。需要注意的是我们使用的是链地址法进行封装，因为stl中的unordered_map和unordered_set也是链地址法。

        2.1、KeyOfT

        上期我们的哈希表查找key值，我们是通过直接访问kv.first来实现的。但是由于封装的时候我们想让unordered_set和unordered_map用同一个哈希表，所以我们对哈希表的模板参数中传入KeyOfT，然后在访问key值时使用KeyOfT的方式:

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

        这个KeyOfT是跟着unordered_set和unordered_map的时候写的，所以等我们进一步封装的时候再去实现KeyOfT。 

         2.2、迭代器

        我们对上一次的哈希表进行升级，是他支持迭代器：

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

	Node* _node;
	const HT* _pht;
	HTIterator(Node* node,const HT* pht)
		:_node(node),
		_pht(pht)
	{}

	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])
				{
					_node = _pht->_tables[hashi];
					break;
				}
				//这个地方和线性探测不一样，不要让他成环
				++hashi;
			}

			if (hashi == _pht->_tables.size())
			{
				_node = nullptr;
				//如果跳出循环发现这个位置根本不存在说明没有下一个节点了
			}

			//注意这是前置++
			return *this;
		}

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

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

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

	bool operator==(const Self& s) const
	{
		return _node == s._node;//比较地址
	}
};

        我们模板参数有6个，K,T是存储类型不多说了，和我们哈希表的一样，ref是引用，ptr是指针，大家应该也都知道，keyOfT是提取key值，hash是哈希映射函数。

        对于operator++，首先如果这个节点是链中的一个节点，并且他还有下一个节点，那我们直接加加就可以了。如果没有，那么我们就去找下一个链。首先我们通过哈希哈希函数找到当前节点在的链子，记作hashi。然后把hashi加加跳过当前的链子，之后一直往后遍历知道找到下一个链子的位置。

        接下来我们让哈希表支持迭代器。

	template<class K,class T,class Ref,class Ptr,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++)
		{
			if (_tables[i])
			{
				return Iterator(_tables[i],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++)
		{
			if (_tables[i])
			{
				return ConstIterator(_tables[i], this);
			}
		}
		return End();
	}

	ConstIterator End() const
	{
		return ConstIterator(nullptr, this);
	}

        因为我们在写迭代器类的时候用了hashTable中的私有成员变量，所以要在hashTable中对迭代器类进行友元声明。 

        对于begin来说，我们就通过遍历，找到第一个出现值的位置就行了，如果走到最后了都没出现值，那说明我们当前哈希表是空的，直接返回end(),而end()实际上是返回一个nullptr构造的迭代器。

      2.3、插入

        我们对插入操作改造升级，使他和源码的返回值相同：

pair<Iterator, bool> Insert(const T& data)
{
	KeyOfT kot;
	Iterator it = Find(kot(data));
	if (it != End())
		return { it,false };

	Hash hs;

	if (_n == _tables.size())
	{
		//扩容
		//HashTable<K, V> newht(__stl_next_prime(_tables.size() + 1));

		 遍历旧表，将旧表的数据全部重新映射到新表
		//for (size_t i = 0; i < _tables.size(); i++)
		//{
		//	Node* cur = _tables[i];
		//	while (cur)
		//	{
		//		newht.Insert(cur->_kv);
		//		cur = cur->_next;
		//	}
		//}
		//_tables.swap(newht._tables);
		//我们不采用上面的方式，因为上面的方式每个节点都得拷贝一次
		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);//浅交换
	}

	size_t hashi = hs(kot(data)) % _tables.size();

	Node* newnode = new Node(data);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;

	return { Iterator(newnode,this),true };
}

        这段内容没什么难点，大家看看就好了。 

         2.4、unordered_map的封装

        现在我们新建一个头文件unordered_map.h，然后写一下unordered_map的类：

#include"HashTable.h"

template<class K,class V,class hash=HashFunc<K>>
class unordered_map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) const //仿函数记得加const
		{
			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);
	}

	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 = insert({ key,V() });
		return ret.first->second;
	}
private:
	hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, hash> _ht;
};

        由于我们要保证unordered_map中存储的值的key值不被修改，所以哈希表的私有变量我们第二个传入的模版参数是pair<const K,V>。

        2.5、unordered_set的封装

        说实话这也没啥好说的，大家看看就好。

#include"HashTable.h"
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.Begin();
	}
	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;
 };

3、总结 

        unordered_set经常用于去重以及存在性检查。unordered_map常用于快速键值查找以及频率统计。在后续做算法题时，经常会用到这两个容器。

        好了，今天的内容就分享到这，我们下期再见！