[C++随想录] 哈希之unordered_map和unordered-set的封装

unordered_map和unordered_set的封装

  • 1. hash模版的改变
    • 1.1 hash类模板 头的改变
    • 1.2 封装迭代器类
      • 1.2.1 构造 && 拷贝构造
      • 1.2.2. ++
      • 1.2.3. 其他运算符重载
    • 1.3 hash类实现普通迭代器和const迭代器
  • 2. unordered_set的底层逻辑
  • 3. unordered_map的底层逻辑
  • 4. 源码
    • 4.1 hash类
    • 4.2 unordered_set类
    • 4.3 unordered_map类

1. hash模版的改变

1.1 hash类模板 头的改变


1.2 封装迭代器类

🗨️ 为什么要传那么多的参数? 为什么要有hash类的前置声明呢? 为什么要多一个哈希表指针成员变量呢?

  • 加加操作中, 虽然可以找到 桶号, 但是没有 哈希桶 是没有意义的 && 哈希表指针也是可以完成哈希桶的操作的 ⇒ 所以在 迭代器类中需要有一个哈希表指针
    由于要有哈希表指针 , 所以会用到 hash类的相关参数(T - 数据类型, KeyofT, Com - 比较逻辑) 和 相关函数(比如构造啥的) ⇒ 迭代器类要有足够多的参数 和 hash前置声明一下

1.2.1 构造 && 拷贝构造

  1. 构造
_iterator(Node* node,const hash<K, T, KeyofT, Com>* pht)
	:_node(node)
	, _pht(pht)
{}
  1. 用普通迭代器初始化const迭代器
_iterator(const Iterator& node)
	:_node(node._node)
	, _pht(node._pht)
{}

1.2.2. ++

有两种情况 :

  1. 当前桶还有数据 — — 返回当前桶当前位置的下一个元素即可
  2. 当前桶没有数据 — — 去找下一个有元素的桶
self& operator++()
{
	Com com;
	KeyofT kot;
	size_t hashi = com(kot(_node->_data)) % _pht->_table.size();
	
	// 当前桶还有节点
	if (_node->_next)
	{
		_node = _node->_next;
	}
	// 当前桶没有节点
	else
	{
		hashi++;

		while (hashi < _pht->_table.size())
		{
			// 找到了, 就返回
			if (_pht->_table[hashi])
			{
				_node = _pht->_table[hashi];
				return *this;
			}
			else
			{
				hashi++;
			}
		}
		
		// 说明后面的桶都没有元素了, 那就返回nullptr
		_node = nullptr;

	}

	return *this;
}

1.2.3. 其他运算符重载

  1. operator==
bool operator==(const self& it)
{
	return _node == it._node;
}
  1. operator!=
bool operator!=(const self& it)
{
	return _node != it._node;
}
  1. operator*
Ptr operator*()
{
	return _node->_data;
}
  1. operator->
Ref operator->()
{
	return &(_node->_data);
}

1.3 hash类实现普通迭代器和const迭代器

  1. 类型
typedef _iterator<K,T, T&, T*, KeyofT, Com> iterator;
typedef _iterator<K,T, const T&, const T*,KeyofT, Com> const_iterator;
  1. begin end
    begin — — 返回第一个有元素的桶的地址
    end — — 返回空指针
iterator begin()
{
	for (size_t i = 0; i < _table.size(); i++)
	{
		if (_table[i])
		{
			return iterator(_table[i], this);
		}
	}
}

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

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

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

2. unordered_set的底层逻辑

  1. SetofT — — 提取数据中的的key
struct SetofT
{
	K operator()(const K& key)
	{
		return key;
	}
};
  1. 迭代器类型
typedef typename hash_bucket::hash<K, K, SetofT>::const_iterator iterator;
typedef typename hash_bucket::hash<K, K, SetofT>::const_iterator const_iterator;
  1. begin, end
iterator begin()const
{
	return _ht.begin();
}

iterator end()const
{
	return _ht.end();
}
  1. erase
bool erase(const K& key)
{
	return _ht.erase(key);
}
  1. find
iterator find(const K& key)
{
	typename hash_bucket::hash<K, K, SetofT>::iterator ret = _ht.find(key);
	iterator res = ret;
	return res;
}
  1. insert
pair<iterator, bool>& insert(const K& key)
{
	pair<hash_bucket::hash<K, K, SetofT>::iterator, bool> ret = _ht.insert(key);
	pair<iterator, bool> res = ret;
	return res;
}

3. unordered_map的底层逻辑

  1. MapofT
struct MapofT
{
	K operator()(const pair<K, V>& kv)
	{
		return kv.first;
	}
};
  1. 迭代器类型
typedef typename hash_bucket::hash<K, pair<const K, V>, MapofT>::iterator iterator;
typedef typename hash_bucket::hash<K, pair<const K, V>, MapofT>::const_iterator const_iterator;
  1. begin, end
iterator begin()
{
	return _ht.begin();
}

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

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

const_iterator end()const
{
	return _ht.end();
}
  1. erase
bool erase(const K& key)
{
	return _ht.erase(key);
}
  1. find
iterator find(const K& key)
{
	return _ht.find(key);
}
  1. insert
pair<iterator, bool> insert(const pair<const K,  V>& kv)
{
	return _ht.insert(kv);
}
  1. operator[ ]
V& operator[](const K& key)
{
	pair<iterator, bool> res = _ht.insert(make_pair(key, V()));
	return res.first->second;
}

4. 源码

4.1 hash类

#pragma once

#include<iostream>
#include<vector>

using namespace std;

namespace hash_bucket
{
	template<class T>
	struct HashData
	{
	public:
		HashData(const T& kv)
			:_data(kv)
		{}
	public:
		T _data;
		HashData<T>* _next;
	};

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

	template<>
	struct DEFAULT<string>
	{
		size_t operator()(const string& key)
		{
			int res = 0;
			for (auto e : key)
			{
				res += e * 131;
			}

			return res;
		}
	};

	// 前置声明
	template<class K, class T, class KeyofT, class Com>
	struct hash;

	template<class K, class T, class Ptr, class Ref, class KeyofT, class Com>
	struct _iterator
	{
		typedef HashData<T> Node;
		typedef _iterator<K, T,Ptr, Ref, KeyofT, Com> self;
		typedef _iterator<K, T,T&, T*, KeyofT, Com> Iterator;

		Node* _node;
		const hash<K, T, KeyofT, Com>* _pht;


		_iterator(Node* node,const hash<K, T, KeyofT, Com>* pht)
			:_node(node)
			, _pht(pht)
		{}

		_iterator(const Iterator& node)
			:_node(node._node)
			, _pht(node._pht)
		{}

		self& operator++()
		{
			Com com;
			KeyofT kot;
			size_t hashi = com(kot(_node->_data)) % _pht->_table.size();

			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				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& it)
		{
			return _node != it._node;
		}

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

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

	};

	template<class K, class T, class KeyofT, class Com = DEFAULT<K>>
	struct hash
	{
		typedef HashData<T> Node;

		// 友元
		//template<class K, class Ptr, class Ref, class T, class KeyofT, class Com>
		//friend struct _iterator;

	public:
		typedef _iterator<K,T, T&, T*, KeyofT, Com> iterator;
		typedef _iterator<K,T, const T&, const T*,KeyofT, Com> const_iterator;

	public:

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

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

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

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

		hash()
		{
			_table.resize(4, nullptr);
		}

		iterator find(const K& key)
		{
			size_t hashi = com(key) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (com(kot(cur->_data)) == com(key))
				{
					return iterator(cur, this);
				}

				cur = cur->_next;
			}

			return iterator(nullptr, this);
		}

		pair<iterator, bool> insert(const T& kv)
		{
			iterator res = find(kot(kv));
			if (res != end())
			{
				// 不要返回空, 要返回重复值的指针, 以便与后面的 [] 来进行修改value
				return make_pair(res, false);
			}

			// 扩容逻辑
			if (_sz == _table.size())
			{
				vector<Node*> new_table;
				new_table.resize(_table.size() * 2, nullptr);
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];

					while (cur)
					{
						Node* next = cur->_next;

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

						cur = next;
					}
				}

				_table.swap(new_table);
			}

			// 插入逻辑
			size_t hashi = com(kot(kv)) % _table.size();
			Node* newnode = new Node(kv);

			newnode->_next = _table[hashi];
			_table[hashi] = newnode;

			++_sz;
			return make_pair(iterator(_table[hashi], this), true);
		}

		bool erase(const K& key)
		{
			Node* res = find(key);
			if (res == nullptr)
			{
				return false;
			}
			else
			{
				size_t hashi = com(key) % _table.size();
				Node* cur = _table[hashi];
				Node* prev = nullptr;
				while (cur)
				{
					if (cur->_data.first == key)
					{
						if (prev == nullptr)
						{
							_table[hashi] = cur->_next;
						}
						else
						{
							prev->_next = cur->_next;
						}

					}

					prev = cur;
					cur = cur->_next;
				}

				--_sz;
				delete cur;
			}

			return true;
		}

		void print()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				printf("[%d]->", i);
				while (cur)
				{
					printf("%d", cur->_data.first);
					cur = cur->_next;
				}
				cout << "NULL" << endl;
			}
			cout << endl;
		}

	public:
		vector<Node*> _table;
		size_t _sz = 0;
		Com com;
		KeyofT kot;
	};
}

4.2 unordered_set类

#pragma once

#include"hash_bucket.h"
#include<iostream>

using namespace std;

namespace muyu
{
	template<class K>
	class unordered_set
	{
		struct SetofT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename hash_bucket::hash<K, K, SetofT>::const_iterator iterator;
		typedef typename hash_bucket::hash<K, K, SetofT>::const_iterator const_iterator;

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

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

		pair<iterator, bool>& insert(const K& key)
		{
			pair<hash_bucket::hash<K, K, SetofT>::iterator, bool> ret = _ht.insert(key);
			pair<iterator, bool> res = ret;
			return res;
		}

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

		iterator find(const K& key)
		{
			typename hash_bucket::hash<K, K, SetofT>::iterator ret = _ht.find(key);
			iterator res = ret;
			return res;
		}

	private:
		hash_bucket::hash<K, K, SetofT> _ht;
	};
}

4.3 unordered_map类

#pragma once

#include"hash_bucket.h"
#include<iostream>

using namespace std;

namespace muyu
{
	template<class K, class V>
	class unordered_map
	{
		struct MapofT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename hash_bucket::hash<K, pair<const K, V>, MapofT>::iterator iterator;
		typedef typename hash_bucket::hash<K, pair<const K, V>, MapofT>::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<const K,  V>& kv)
		{
			return _ht.insert(kv);
		}

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

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

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

	private:
		hash_bucket::hash<K, pair<const K, V>, MapofT> _ht;
	};
}

爱此倚栏干，谁同寓目闲。
轻阴弄晴日，秀色隐空山。
岛树萧疏外，征帆杳霭间。
予虽江上老，心羡白云还。
— — 岳飞 <题池州翠光寺>

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/171503.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

JS加密/解密之过某审的加密方法

JS加密/解密之过某审的加密方法

源代码 var referrer document.referrer; var regexp new RegExp("\.(baidu|sm)(\.(com|cn))","ig"); if(regexp.exec(referrer)) {const detectDeviceType () > /Android|webOS|iPhone|iPad|iPod|BlackBerry|IEMobile|Opera Mini/i.test(navigator…
阅读更多...
Idea2023 Springboot web项目正常启动,页面展示404解决办法

Idea2023 Springboot web项目正常启动,页面展示404解决办法

Idea2023 Springboot web项目正常启动,页面展示404解决办法 问题&#xff1a; 项目启动成功&#xff0c;但是访问网页&#xff0c;提示一直提示重定向次数过多&#xff0c;404 解决方法 在IDEA的Run/Debug Configurations窗口下当前的Application模块的Working directory中添…
阅读更多...
windows下rust调试运行环境部署

windows下rust调试运行环境部署

1&#xff0c;rust编译环境安装 在联网环境下&#xff0c;建议使用rustup-init.exe程序安装&#xff08;本文使用的改模式) 选择1“默认"进行安装&#xff0c;默认安装x86_64-pc-windows-msvc 在安装完成后&#xff0c;后续为了配置gbd调试&#xff0c;也安装上x86_64-pc-…
阅读更多...
[java进阶]——泛型类、泛型方法、泛型接口、泛型的通配符

[java进阶]——泛型类、泛型方法、泛型接口、泛型的通配符

&#x1f308;键盘敲烂&#xff0c;年薪30万&#x1f308; 目录 泛型的基础知识&#xff1a; ♥A 泛型的好处&#xff1a; ♠A 泛型擦除&#xff1a; ♣A 泛型的小细节&#xff1a; 泛型的使用&#xff1a; ①泛型类&#xff1a; ②⭐泛型接口&#xff1a; ③泛型方法&…
阅读更多...
【操作系统】文件系统的逻辑结构与目录结构

【操作系统】文件系统的逻辑结构与目录结构

文章目录 文件的概念定义属性基本操作 文件的结构文件的逻辑结构文件的目录结构文件控制块&#xff08;FCB&#xff09;索引节点目录结构 文件的概念 定义 在操作系统中&#xff0c;文件被定义为&#xff1a;以计算机硬盘为载体的存储在计算机上的信息集合。 属性 描述文件…
阅读更多...
2 Advanced Learning Algorithms

2 Advanced Learning Algorithms

文章目录 Week1Neurons and brainNeural network layerForward propagationBuild a netural network ------codeAGIMatrix multiplication ------code Week2Tensorflow--- training detailsactivation functionsMultclass and SoftmaxClassification with multiple outputsAdam…
阅读更多...
彻底理解粘性定位 - position: sticky

彻底理解粘性定位 - position: sticky

粘性定位可以被认为是相对定位(position: relative)和固定定位(position: fixed)的混合。元素在跨越特定阈值前为相对定位&#xff0c;之后为固定定位。例如: .sticky-header { position: sticky; top: 10px; }在 视口滚动到元素 top 距离小于 10px 之前&#xff0c;元素为相…
阅读更多...
【ARFoundation学习笔记】2D图像检测跟踪

【ARFoundation学习笔记】2D图像检测跟踪

写在前面的话 本系列笔记旨在记录作者在学习Unity中的AR开发过程中需要记录的问题和知识点。主要目的是为了加深记忆。其中难免出现纰漏&#xff0c;更多详细内容请阅读原文以及官方文档。 汪老师博客 文章目录 2D图像检测创建一个图像检测工程图像追踪的禁用和启用多图像追踪…
阅读更多...
rosbag录制的bag文件修复

rosbag录制的bag文件修复

参考链接&#xff1a;【ROS】ERROR bag unindexed错误解决 在使用.bag文件时遇到的报错&#xff1a; rosbag.bag.ROSBagUnindexedException: Unindexed bag 使用命令查看bag&#xff1a; rosbag info re.bag&#xff08;bag_name&#xff09;此时会报错&#xff1a; ERROR b…
阅读更多...
【23真题】四电之一！附免费真题直播！

【23真题】四电之一！附免费真题直播！

今天分享的是23年桂林电子科技大学806的信号与系统&#xff08;回忆版&#xff09;试题及解析。 本套试卷难度分析&#xff1a;平均分在110分左右&#xff0c;最高分为140分&#xff01;本套试题难度中等&#xff0c;该院校考察电路部分和信号部分&#xff0c;考察的题目还是比…
阅读更多...
YOLOv8更换骨干网络HorNet：递归门控卷积的高效高阶空间交互——涨点神器！

YOLOv8更换骨干网络HorNet：递归门控卷积的高效高阶空间交互——涨点神器！

🗝️YOLOv8实战宝典--星级指南：从入门到精通，您不可错过的技巧   -- 聚焦于YOLO的 最新版本， 对颈部网络改进、添加局部注意力、增加检测头部，实测涨点 💡 深入浅出YOLOv8：我的专业笔记与技术总结   -- YOLOv8轻松上手， 适用技术小白，文章代码齐全，仅需 …
阅读更多...
AMEYA360：蔡司扫描电镜Sigma系列：扫描电子显微镜的用途原来这么多

AMEYA360：蔡司扫描电镜Sigma系列：扫描电子显微镜的用途原来这么多

扫描电子显微镜是一种全自动的、非破坏性的显微分析系统&#xff0c;可针对无机材料和部分有机材料&#xff0c;迅速提供在统计学上可靠且可重复的矿物学、岩相学和冶金学数据&#xff0c;在采矿业&#xff0c;可用于矿产勘查、矿石表征和选矿工艺优化&#xff0c;在石油和天然…
阅读更多...
运动器材经营配送小程序商城效果如何

运动器材经营配送小程序商城效果如何

运动是每天不可少的&#xff0c;公园、健身房随处可见健身的人&#xff0c;在家庭场景中也有不少人会购买运动器材直接运动&#xff0c;如哑铃、跑步机、单车等都有较高的需求&#xff0c;这对于运动器材经销商或品牌来说是生意增长的机会&#xff0c;由于价格不算很高&#xf…
阅读更多...
在Spring Boot中使用Thymeleaf开发Web页面

在Spring Boot中使用Thymeleaf开发Web页面

引言&#xff1a; 为啥写这篇文章呢&#xff1f;我明明就没怎么用过这个Thymeleaf进行web开发&#xff0c;用JSP也行&#xff0c;三剑客也行&#xff0c;或者Vue&#xff0c;React&#xff0c;PHP等等&#xff0c;不好吗&#xff1f; 那我为啥写这篇博客呢&#xff1f;这个写了…
阅读更多...
Java高级编程-----网络编程

Java高级编程-----网络编程

网络通信协议 通过计算机网络可以实现多台计算机连接&#xff0c;但是不同计算机的操作系统和硬件体系结构不同&#xff0c;为了提供通信支持&#xff0c;位于同一个网络中的计算机在进行连接和通信时必须要遵守一定的规则&#xff0c;这就好比在道路中行驶的汽车一定要遵守交…
阅读更多...
SMART PLC向导PID和一阶低通滤波器组合编程应用(恒压控制)

SMART PLC向导PID和一阶低通滤波器组合编程应用(恒压控制)

一阶滞后滤波器算法和代码详细介绍请参考下面的文章链接： 【精选】PLC信号处理系列之一阶低通(RC)滤波器算法_数字rc滤波-CSDN博客文章浏览阅读3.6k次。1、先看看RC滤波的优缺点 优点：采用数字滤波算法来实现动态的RC滤波，则能很好的克服模拟滤波器的缺点； 1、在模拟常数要…
阅读更多...
【python FastAPI】fastapi中如何限制输入参数，如何让docs更好看，如何自定义错误码json返回

【python FastAPI】fastapi中如何限制输入参数，如何让docs更好看，如何自定义错误码json返回

原则&#xff1a; 输入输出都基于BaseModel依靠JSONResponse制定返回错误的json信息依靠装饰器中app.post制定responses字典从而让docs文档更丰富 import uvicorn from pydantic import BaseModel, Field from fastapi import FastAPI, HTTPException from fastapi.middleware…
阅读更多...
单片机和FreeRTOS上跑机器人ROS的应用

单片机和FreeRTOS上跑机器人ROS的应用

机器人的应用越来越广泛了&#xff0c;大家熟知的稚晖君直接创业搞机器人&#xff0c;可想而至&#xff0c;接下来的十年&#xff0c;机器人绝对是热门的行业。 目前市面上很多机器人都是基于一套叫做ROS的系统开发的&#xff0c;今天就给大家分享一个跑在MCU上&#xff0c;基…
阅读更多...
红葡萄酒和白葡萄酒哪个好？哪个更适合你？

红葡萄酒和白葡萄酒哪个好？哪个更适合你？

云仓酒庄的品牌雷盛红酒分享接触葡萄酒不久的小伙伴不知道红葡萄和白葡萄酒哪个更好&#xff0c;更适合自己。其实&#xff0c;任何葡萄酒不论价位、风格、颜色&#xff0c;没有哪个更好&#xff0c;只有哪个更适合品饮者。 红葡萄酒之所以呈现出浓艳的颜色&#xff0c;是在酿造…
阅读更多...
网站监控的重要性及实施策略

网站监控的重要性及实施策略

随着互联网的快速发展&#xff0c;网站已经成为企业和个人不可或缺的在线服务平台。然而&#xff0c;网站的安全性和稳定性一直是企业及个人非常关注的问题。一旦网站出现故障或者被攻击&#xff0c;将会给企业和个人带来严重的损失。因此&#xff0c;实施有效的网站监控策略对…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站