unordered_set和unordered_map的封装

2023-09-22 08:00:00

目录

一、前言

二、容器的使用

1、unordered_map

2、unordered_set

​编辑

三、哈希表的改造

1、结点

2、哈希表的迭代器

* 构造函数

* 重载 *

* 重载 ->

* 重载 ++

* 重载 != 和  ==

3、哈希表的析构

4、unordered_map的 [] 实现

5、修改后的哈希表

四、 unordered_set的实现

五、unordered_map的实现

一、前言

在C++11中，STL提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，但是效率却提高了。

unordered系列的关联式容器之所以效率比较高，是因为unordered系列的关联式容器的底层使用了我们前面所讲到的哈希结构。那么今天我们就来看看 unordered_set和unordered_map这两个容器的使用及其实现。

二、容器的使用

1、unordered_map

1、 unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2、 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3、 在内部unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4、 unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5、unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。

int main()
{
	unordered_map<string, int> countMap;
	string arr[] = { "苹果","香蕉","苹果","葡萄"，"西瓜" };
	for (auto& e : arr)
	{
		auto it = countMap.find(e);
		/*if (it == countMap.end())
		{
			countMap.insert(make_pair(e, 1));
		}
		else
		{
			it->second++;
		}*/
		countMap[e]++;
	}
	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	return 0;
}

 从运行结果我们可以看出 unordered_map里面的数据是无序且数据是可以有重复的。 

2、unordered_set

1、不再以键值对的形式存储数据，而是直接存储数据的值。
2、容器内部存储的各个元素的值都互不相等，且不能被修改。
3、不会对内部存储的数据进行排序。

int main()
{
	unordered_set<int> us;
	us.insert(10);
	us.insert(1);
	us.insert(10);
	us.insert(3);
	us.insert(4);
	us.insert(4);
	auto it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	return 0;
}

 从运行结果我们可以看出 unordered_set里面的数据是无序且没有重复的。

三、哈希表的改造

从标准库中我们知道，unordered_set和unordered_map这两个容器的底层结构都是哈希表。但是两个容器所存储的数据类型不同，前者存储的是 key类型的数据，后者存储的是 key/value类型的数据。所以为了方便，我们需要像实现 map和set的底层红黑树那样，去实现一个通用的哈希表。所以我们需要对哈希表改造一下，来满足两个容器都可以使用。

1、结点

首先，我们需要对节点改造，使其能够满足两种存储方式。

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

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

2、哈希表的迭代器

我们需要对哈希表指针和结点指针进行封装。

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

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

	Node* _node;
	HT* _ht;
};

* 构造函数

_HashIterator(Node* node, HT* ht)
	:_node(node)
	, _ht(ht)
{}

* 重载 *

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

* 重载 ->

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

* 重载 ++

思路：如果当前的哈希桶还有节点（即下一个结点不为空），那么++就是当前桶的当前节点的下一个节点，如果当前元素是所在桶的最后一个元素，那么++就是找下一个非空的哈希桶。

    Self& operator++()
	{
		if (_node->_next)
		{
			//当前桶迭代
			_node = _node->_next;
		}
		else
		{
			// 找下一个桶
			Hash hash;
			KeyOfT kot;
			size_t i = hash(kot(_node->_data)) % _ht->_tables.size();
			i++;
			for (; i < _ht->_tables.size(); i++)
			{
				if (_ht->_tables[i])
				{
					_node = _ht->_tables[i];
					break;
				}
			}

			//说明后面没有有数据的桶了
			if (i == _ht->_tables.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

* 重载 != 和  ==

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

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

3、哈希表的析构

~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;
	}
}

4、unordered_map的 [] 实现

我们知道，unordered_map的操作中可以通过[]来访问数据，并修改value值，那么这是怎么做到的呢？

其实要想实现[]，我们需要先把insert的返回值修改成pair<iterator,bool>，最后的返回值也要一起修改。如果有重复的元素就返回这个位置的迭代器，没有重复的就返回新节点newnode的迭代器。

    pair<iterator, bool> insert(const T& data)
	{
		Hash hash;
		KeyOfT kot;
		//去重
		iterator ret = Find(kot(data));
		if (ret != end())
		{
			return make_pair(ret, false);
		}

		//扩容
		if (_size == _tables.size())
		{
			size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 10;
			vector<Node*> newTables;
			newTables.resize(newsize, nullptr);
			//将旧表中结点移动映射到新表
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;

					size_t hashi = hash(kot(cur->_data)) % newTables.size();
					cur->_next = newTables[hashi];
					newTables[hashi] = cur;

					cur = next;
				}
				_tables[i] = nullptr;
			}
			_tables.swap(newTables);
		}

		size_t hashi = hash(kot(data)) % _tables.size();
		Node* newnode = new Node(data);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		_size++;

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

有了上面的插入，我们就可以在unordered_map中实现[]的操作了。 

5、修改后的哈希表

#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

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

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

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

	Node* _node;
	HT* _ht;

	_HashIterator(Node* node, HT* ht)
		:_node(node)
		, _ht(ht)
	{}

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

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

	Self& operator++()
	{
		if (_node->_next)
		{
			//当前桶迭代
			_node = _node->_next;
		}
		else
		{
			// 找下一个桶
			Hash hash;
			KeyOfT kot;
			size_t i = hash(kot(_node->_data)) % _ht->_tables.size();
			i++;
			for (; i < _ht->_tables.size(); i++)
			{
				if (_ht->_tables[i])
				{
					_node = _ht->_tables[i];
					break;
				}
			}

			//说明后面没有有数据的桶了
			if (i == _ht->_tables.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

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

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

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 val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}
		return val;
	}
};

template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
	typedef HashNode<T> Node;

	template<class K, class T, class Hash, class KeyOfT>
	friend struct _HashIterator;
public:
	typedef _HashIterator<K, T, Hash, KeyOfT> iterator;

	iterator begin()
	{
		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);
	}

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

	pair<iterator, bool> insert(const T& data)
	{
		Hash hash;
		KeyOfT kot;
		//去重
		iterator ret = Find(kot(data));
		if (ret != end())
		{
			return make_pair(ret, false);
		}

		//扩容
		if (_size == _tables.size())
		{
			size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 10;
			vector<Node*> newTables;
			newTables.resize(newsize, nullptr);
			//将旧表中结点移动映射到新表
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;

					size_t hashi = hash(kot(cur->_data)) % newTables.size();
					cur->_next = newTables[hashi];
					newTables[hashi] = cur;

					cur = next;
				}
				_tables[i] = nullptr;
			}
			_tables.swap(newTables);
		}

		size_t hashi = hash(kot(data)) % _tables.size();
		Node* newnode = new Node(data);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		_size++;

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

	iterator Find(const K& key)
	{
		if (_tables.size() == 0)
			return end();

		Hash hash;
		KeyOfT kot;
		size_t hashi = hash(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
				return iterator(cur, this);
			else
				cur = cur->_next;
		}
		return end();
	}

	bool erase(const K& key)
	{
		if (_tables.size() == 0)
		{
			return false;
		}

		Hash hash;
		KeyOfT kot;
		size_t hashi = hash(key) % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				// 1、头删
				// 2、中间删
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				_size--;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}

		return false;
	}

private:
	vector<Node*> _tables;
	size_t _size = 0;
};

四、 unordered_set的实现

#pragma once
#include"HashTable.h"

namespace zdl
{
	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;

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

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

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

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

五、unordered_map的实现

#pragma once
#include"HashTable.h"

namespace zdl
{
	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 HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;

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

		iterator end()
		{
			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:
		HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
	};
}

更多推荐

网络安全（黑客）自学

前言我是去年8月22日才正式学习网络安全的，因为在国营单位工作了4年，在广东一个月工资只有5000块，而且看不到任何晋升的希望，如果想要往上走，那背后就一定要有关系才行。而且国营单位的气氛是你干的多了，领导觉得你有野心，你干的不多，领导却觉得你这个人不错。我才24周岁，实在的受不了这种工作氛围，情绪已经压制了很多久，一

网络安全中的欺骗攻击与防御技术

在Internet上计算机之间相互进行的交流建立在两个前提之下：认证、信任。认证是网络上的计算机用于相互间进行识别的一种鉴别过程，经过认证的过程，获准相互交流的计算机之间就会建立起相互信任的关系。信任和认证具有逆反关系，即如果计算机之间存在高度的信任关系，则交流时就不会要求严格的认证。而反之，如果计算机之间没有很好的信

阿里云无影云电脑、VDI以及传统PC电脑有什么区别？

阿里云无影云电脑和传统电脑PC有什么区别？区别大了，无影云电脑是云端的桌面服务，传统PC是本地的硬件计算机，无影云电脑的数据是保存在云端，本地传统PC的数据是保存在本地客户端，阿里云百科分享阿里云无影云电脑和传统PC电脑的详细区别对比：目录无影云电脑和传统电脑区别对比阿里云无影云电脑无影云电脑和传统电脑区别对比阿里云无

webpack打包速度优化

优化WebPack打包速度在开发过程中，WebPack的打包速度是一个非常重要的考虑因素。随着项目规模的增长，打包时间也会越来越长，影响开发效率和用户体验。本文将循序渐进地介绍一些优化WebPack打包速度的方法，先分析打包瓶颈，然后逐步优化。分析打包瓶颈在开始优化之前，我们需要了解当前项目的打包瓶颈在哪里。为了帮助我

Java集成支付宝沙箱支付，详细教程（SpringBoot完整版）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、开发前准备？二、使用步骤1、引入库2、配置在application.yml里面进行配置：3、alipay的java配置：AplipayConfig.java4、支付接口4、回调接口一、开发前准备？easy支付官方文档：https://opend

Ubuntu下 Docker、Docker Compose 的安装教程

Docker是一个开源的应用容器引擎，让开发者可以打包他们的应用以及依赖包到一个可移植的容器中，然后发布到任何流行的Linux机器上，也可以实现虚拟化。容器是完全使用沙箱机制，相互之间不会有任何接口。DockerCompose是用于定义和运行多容器docker应用程序的工具,compose通过一个配置文件来管理多个do

微信小程序python+nodejs+php+springboot+vue 健身教练私教预约系统

管理员的主要功能有：1.管理员输入账户登陆后台2.个人中心：管理员修改密码和账户信息3.用户管理：对注册的用户信息进行删除，查询4.教练管理：对教练信息进行添加，修改，删除，查询5.教练简介管理：对教练的简介信息进行查询，删除6.在线预约信息：用户对教练的预约信息进行查询，删除7.健身指南管理：对用户查看的健身指南信息

Nginx之防盗链及高可用解读

目录防盗链解读盗链是什么？Nginx中配置防盗链高可用解读KeepalivedNginx中配置高可用防盗链解读盗链是什么？网页的加载顺序是先加载HTML相关的内容，然后解析HTML的内容，那些需要加载图片，那些需要加载文件，是逐步加载的，对于我们线上的图片等静态资源，经常会被其他网站盗用，外面可以我们请求到一个页面后，

LeetCode：2603. 收集树中金币 详解（2023.9.21 C++）

目录2603.收集树中金币题目描述：实现代码与解析：拓扑+bfs原理思路：2603.收集树中金币题目描述：给你一个n个节点的无向无根树，节点编号从0到n-1。给你整数n和一个长度为n-1的二维整数数组edges，其中edges[i]=[ai,bi]表示树中节点ai和bi之间有一条边。再给你一个长度为n的数组coins，

SpringBoot

SpringBoot技术简介SpringBoot是一种用于构建现代化、可扩展的Java应用程序的框架，它的出现极大地简化了Java应用程序的开发流程。本文将介绍SpringBoot的关键特性以及为什么它成为Java开发者的首选工具。什么是SpringBoot？SpringBoot是SpringFramework的一个扩

Spring系列文章：Bean的作⽤域

1、singleton默认情况下，Spring的IoC容器创建的Bean对象是单例的<?xmlversion="1.0"encoding="UTF-8"?><beansxmlns="http://www.springframework.org/schema/beans"xmlns:xsi="http://www.w3.

热文推荐
  1. NSS [NISACTF 2022]is secret

    NSS[NISACTF2022]issecret原题是[CISCN2019_华东南赛区]Double_Secret开题蒙蔽。猜测是/secret路由，猜对了。GET提交参数?secret=1，这里应该是一个注入点。看了一下network，后端语言是python2，不确定是哪种漏洞，所有想到的都测一遍，最后在测SSTI时

  2. 【2023年11月第四版教材】第14章《沟通管理》（第二部分）

    第14章《沟通管理》（第二部分）4规划沟通管理4.1规划沟通管理4.2沟通技术4.3沟通模型4.4沟通方法★★★（22下案例）4.5人际关系与团队技能4.6沟通管理计划★★★（18下44）（13上论文）（22下案例）5管理沟通5.1管理沟通5.2沟通技能5.3人际关系与团队技能6监督沟通6.1监督沟通★★★6.2人际关

  3. Tomcat架构设计及组件详解

    继Tomcat配置详解（Tomcat配置server.xml详解）Tomcat配置详解（Tomcat配置server.xml详解）_tomcatxml配置https://blog.csdn.net/imwucx/article/details/132166738文章之后，深入的学习tomcat相关知识，对Tomcat的

  4. 自动驾驶中的决策规划

    参考:【干货篇】轻舟智航：自动驾驶中的决策规划技术（附视频回放+PPT下载）-AIQ如图所示,各模块介绍定位模块主要负责解答的问题是“车现在在哪里”，是在道路上还是在路口，是在高架桥上还是在停车场里。感知模块则负责解答“车周围有什么”这个问题。预测模块，预测模块主要解答“周围的车现在想干什么”，比如前面的车要cutin

  5. 全流程HEC-RAS 1D/2D水动力与水环境模拟丨恒定流模型(1D/2D)、一维非恒定流、二维非恒定流模型、HEC-RAS水质模型

    目录​专题一​水动力模型基础专题二恒定流模型(1D/2D)专题三一维非恒定流专题四二维非恒定流模型（一）专题五二维非恒定流模型（二）专题六HEC-RAS的水质模型专题七高级主题更多应用水动力与水环境模型的数值模拟是实现水资源规划、环境影响分析、防洪规划以及未来气候变化下预测和分析的主要手段。然而，一方面水动力和水环境模

  6. 3D点云目标检测：Centerformer训练waymo数据集

    一、环境准备项目地址:centerformer1.0、基础环境python==3.8.0torch==1.9.1+cu111waymo-open-dataset-tf-2-6-0==1.4.9spconv==1.2.1其余按照requirement.txt里安装就行pipinstall-ihttps://pypi.tu

  7. 用微服务平台框架，实现高效的流程化办公！

    想要实现流程化办公，可以用什么样的软件平台实现？随着市场竞争越来越激烈，很多企业会采用低代码技术平台实现高效管理企业的内部资源，从而减少很多繁琐工作和时间，实现提质增效的目的。流辰信息助力大家采用微服务平台框架低代码技术平台打破信息孤岛，创造高效办公。低代码的便捷性和灵活性就不言而喻了，它在企业的发展过程中扮演了非常重

  8. K8S-存储卷，pv，pvc

    pv，pvc一、emptyDir存储卷1.概述2.示例二、hostPath存储卷1.概述三、nfs共享存储卷1.在stor01节点上安装nfs，并配置nfs服务2.master节点操作3.在nfs服务器上创建index.html4.master节点操作四、PVC和PV1.概述2.PV和PVC之间的相互作用遵循的生命周期

  9. Java高级: 反射

    目录反射反射概述反射获取类的字节码反射获取类的构造器反射获取构造器的作用反射获取成员变量&使用反射获取成员方法反射获取成员方法的作用反射的应用案例接下来我们学习的反射、动态代理、注解等知识点，在以后开发中极少用到，这些技术都是以后学习框架、或者做框架的底层源码。讲这些技术的目的，是为了以后我们理解框架、或者自己开发框架