【C++】map与set的封装

2023-09-19 15:31:55

文章目录

前言

 在学习了红黑树之后，我们便可以尝试初步的在红黑树的基础上封装出map与set，好了，话不多说，进入今天的学习吧！

所需知识：

  1. 模板,主要为typename的特殊用法，模板参数，类模板。
  2. 迭代器与const迭代器
  3. 仿函数、反向迭代器
  4. 红黑树

正文

1. 类型的泛化

 我们先分析map与set以及红黑树的模板参数。

  1. map 存的是key——val，键值对。
  2. set 存的是key。
  3. 红黑树存的是 key——val。

 因此，为了适配set，红黑树里面存的是key，为了适配map红黑树存的是key——val, 如何实现呢？

那不如，设红黑树的存放的val是T类型，可以是key，也可以是key——val。

  • 既然这样，我们就将原先的结点改为T类型的。
template<class T>
struct RBTreeNode
{

	typedef RBTreeNode<T> Node;
	RBTreeNode(const T& data)
		:_data(data)
		,_right(nullptr)
		,_left(nullptr)
		,_parent(nullptr)
		,_col(RED)
	{}

	Node* _right;
	Node* _left;
	Node* _parent;
	T _data;
	Color _col;
};

那既然这样，又会引出两个问题：

  1. 模板参数的Key还有用吗？
  2. 插入的数据类型也要变为T，如何进行比较？

先来解决第一个问题，Key有用吗？首先要明白Key是一个类型，在定义变量或者作为函数参数时要使用，很显然红黑树的查找的函数的参数类型是Key，因此有用，且不能舍弃。

2.仿函数

 接着解决第二个问题，插入时既然T可以是key，也可以是pair<key,val> ,我们在找结点的位置的过程中，是通过key值进行查找的,因此又面临两种情况：

  1. T是key时，结点中存的是key可以直接进行比较。
  2. T是pair<key,val>,结点中存的是pair<key,val>直接比较，是无法得出正确结果的，我们看库里的实现即可清楚。
    在这里插入图片描述
    库里的实现涉及到第二参数，因此无法准确的得出正确结果，因此需要我们自己写一个仿函数，那因为map需要写，set也要适配红黑树，因此也需要写一个仿函数，返回key即可。

set实现：

template<class K>
struct SetOfT
{
	K operator()(const K& val)
	{
		return val;
	}
};

map实现:

template<class K, class V>
struct MapOfT
{
	const K operator()(const  pair<const K, V>& val)
	{
		return val.first;
	}
};

3.迭代器

3.1正向迭代器

 根据之前的内容的学习，我们是封装出来一个通用的正向迭代器，通过模板参数控制其为const还是非const迭代器。

基本框架：

	template<class T,class Ref,class Ptr>
	struct __TreeIterator
	{
		
		typedef __TreeIterator<T, T&, T*> iterator;
		typedef RBTreeNode<T> Node;
		typedef __TreeIterator<T,Ref,Ptr> self;

		__TreeIterator(Node* val)
			:_node(val)
		{}
		//此构造用于将非const迭代器转换为const迭代器，从而实现类型转换的功能。
		__TreeIterator(const iterator& val)
			:_node(val._node)
		{}
		//前置++
		self& operator++();
		//后置++
		self operator++(int);
		//后置--
		self operator--(int);
		//解引用
		Ref operator*();
		//箭头
		Ptr operator->();
		//不等于
		bool operator!=(const __TreeIterator& it);

		Node* _node;
	};
3.1.1 ++

由于三叉链的结构，父节点是很容易找到的，因此可以直接用循环写一个。

原理： 中序遍历

  1. 开始节点树的最小节点。
  2. 根据中序遍历的过程遍历整棵树。

图解：
在这里插入图片描述

		self& operator++()
		{
			Node* cur = _node;
			assert(cur);
			if (cur->_right)
			{
				//如果右子树不为空，访问其右子树的最左结点。
				Node* MostLeft = cur->_right;
				while (MostLeft && MostLeft->_left)
				{
					MostLeft = MostLeft->_left;
				}
				_node = MostLeft;
			}
			else
			{
				//右子树为空，访问其祖先

				Node* parent = cur->_parent;

				//结点为其父节点的左边，访问父节点即可
				if (parent && parent->_left == cur)
				{
					_node = parent;
				}
				//结点为其父节点的右边，访问父亲的父亲
				else
				{
					while (parent && parent->_right == cur)
					{
						cur = parent;
						parent = parent->_parent;
					}
					_node = parent;
				}
			}
			return *this;
		}
3.1.2 - -
  • 与 ++同思路。

图解：
在这里插入图片描述
注意：当为空时，–我在这实现的是不可以的，但是库里面的是可以的，因为库里的结构是这样的。

在这里插入图片描述
库里的判断条件是这样的：当node为header时，node就转换其右边结点，也就是右树的最大结点。
在这里插入图片描述
说明一下：这样实现可能会导致增加了维护最大和最小节点的成本，每次插入和删除都得判断一下，不过也还好。

因此：这里我们只是实现正向的迭代器，反向的迭代器我们没有写，如果不采用库里的结构，我们也可以用友元+指针+前置类型声明的方式进行实现。

self& operator--()
{
	Node* cur = _node;
	if (cur->_left)
	{
		//访问最右结点
		Node* most_right = cur->_left;
		while (most_right && most_right->_right)
		{
			most_right = most_right->_right;
		}
		_node = most_right;
	}
	else
	{
		Node* parent = cur->_parent;
		if (parent->_right == cur)
		{
			//父节点右为cur，该访问父节点了。
			_node = parent;
		}
		else
		{
			//找到父亲作为cur的结点。
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
	}

	return *this;
}
3.1.3 *
Ref operator*()
{
	return _node->_data;
}
3.1.4 ->
Ptr operator->()
{
	return &(_node->_data);
}
3.1.5 !=
bool operator!=(const __TreeIterator& it)
{
	return _node != it._node;
}
完整版代码
	template<class T,class Ref,class Ptr>
	struct __TreeIterator
	{

		typedef __TreeIterator<T, T&, T*> iterator;
		typedef RBTreeNode<T> Node;
		typedef __TreeIterator<T,Ref,Ptr> self;

		__TreeIterator(Node* val)
			:_node(val)
		{}
		__TreeIterator(const iterator& val)
			:_node(val._node)
		{}

		//前置++
		self& operator++()
		{
			Node* cur = _node;
			assert(cur);
			if (cur->_right)
			{
				//如果右子树不为空，访问其右子树的最左结点。
				Node* MostLeft = cur->_right;
				while (MostLeft && MostLeft->_left)
				{
					MostLeft = MostLeft->_left;
				}
				_node = MostLeft;
			}
			else
			{
				//右子树为空，访问其祖先

				Node* parent = cur->_parent;

				//结点为其父节点的左边，访问父节点即可
				if (parent && parent->_left == cur)
				{
					_node = parent;
				}
				//结点为其父节点的右边，访问父亲的父亲
				else
				{
					while (parent && parent->_right == cur)
					{
						cur = parent;
						parent = parent->_parent;
					}
					_node = parent;
				}
			}
			return *this;
		}

		self operator++(int)
		{
			 self tmp(_node);
			 ++(*this);
			 return tmp;
		}
		self& operator--()
		{
			Node* cur = _node;
			if (cur->_left)
			{
				//访问最右结点
				Node* most_right = cur->_left;
				while (most_right && most_right->_right)
				{
					most_right = most_right->_right;
				}
				_node = most_right;
			}
			else
			{
				Node* parent = cur->_parent;
				if (parent->_right == cur)
				{
					//父节点右为cur，该访问父节点了。
					_node = parent;
				}
				else
				{
					//找到父亲作为cur的结点。
					while (parent && parent->_left == cur)
					{
						cur = parent;
						parent = parent->_parent;
					}
					_node = parent;
				}
			}

			return *this;
		}
		self operator--(int)
		{
			self tmp(_node);
			(*this)++;
			return tmp;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &(_node->_data);
		}
		bool operator!=(const __TreeIterator& it)
		{
			return _node != it._node;
		}
		Node* _node;
	};

4.[]（map）

我们要实现的insert接口为：
在这里插入图片描述

因此我们实现的红黑树的接口为：

pair<iterator,bool> insert(const T& val)
{
	//第一步：插入操作
	//如果根节点为空
	if (_root == nullptr)
	{
		_root = new Node(val);
		_root->_col = BLACK;
		return make_pair(iterator(_root), true);
	}
	else
	{
		KeyOfT sel;//select里面的key
		Node* cur = _root, *parent = _root;
		while (cur)
		{
			if (sel(cur->_data) > sel(val))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (sel(cur->_data) < sel(val))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		cur = new Node(val);
		if (sel(parent->_data) > sel(val))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//变色逻辑略，重点在框架。
		return make_pair(iterator(newnode), true);
	}
}

map接口的实现为：

pair<iterator,bool> insert(const pair<K,V>& data)
{
	return _tree.insert(data);
}
mapped_type& operator[](const key_type& data)
{
	pair<iterator, bool> x = _tree.insert(val_type(data,mapped_type()));
	return x.first->second;
}

set的接口为：

pair<iterator,bool> insert(const K& data)
{
	pair<typename rb_type::iterator, bool> k = _tree.insert(data);
	return pair<iterator,bool>(k.first,k.second);
}

补充小知识：迭代器转const迭代器

先强调：

  1. const迭代器与非const迭代器是两种完全不同的自定义类型。
  2. 内置类型默认支持隐式类型转换，自定义类型需要有合适的构造函数才可实现隐式类型的转换，且explict可阻止隐式类型转换的发生。

因此：我们需要在模板内部写一个合适的构造函数，且其成员是公有的，才可实现自定义类型的转换。

框架

1.红黑树

运用封装知识的框架：

	template<class Key,class T,class KeyOfT>
	class RBTree
	{
	public:
		typedef RBTreeNode<T> Node;
		typedef __TreeIterator<T,T&,T*> iterator;
		typedef __TreeIterator<T, const T&, const T*> const_iterator;
		const_iterator begin()const
		{
			Node* mostleft = _root;
			while (mostleft && mostleft->_left)
			{
				mostleft = mostleft->_left;
			}
			return mostleft;
		}
		iterator begin()
		{
			Node* mostleft = _root;
			while (mostleft && mostleft->_left)
			{
				mostleft = mostleft->_left;
			}
			return mostleft;
		}
		const_iterator end()const
		{
			return nullptr;
		}
		iterator end()
		{
			return nullptr;
		}
		Node* find(const Key& key)
		{
			KeyOfT sel;
			Node* cur = _root;
			while (cur)
			{
				if (sel(cur->_data) > key)
				{
					cur = cur->_right;
				}
				else if (sel(cur->_data) < key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}
		pair<iterator,bool> insert(const T& val)
		{
			//第一步：插入操作
			//如果根节点为空
			if (_root == nullptr)
			{
				_root = new Node(val);
				_root->_col = BLACK;
				return make_pair(iterator(_root), true);
			}
			else
			{
				KeyOfT sel;
				Node* cur = _root, * parent = _root;
				while (cur)
				{
					if (sel(cur->_data) > sel(val))
					{
						parent = cur;
						cur = cur->_left;

					}
					else if (sel(cur->_data) < sel(val))
					{
						parent = cur;
						cur = cur->_right;

					}
					else
					{
						return make_pair(iterator(cur), false);
					}
				}
				cur = new Node(val);
				if (sel(parent->_data) > sel(val))
				{
					parent->_left = cur;
				}
				else
				{
					parent->_right = cur;
				}

				//根节点可能为红色,不管红色还是黑色都弄成黑色
				_root->_col = BLACK;
				return make_pair(iterator(newnode), true);
			}
		}
	private:

		Node* _root = nullptr;
	};
};

2.set

	template<class K>
	class set
	{
		template<class K>
		struct SetOfT
		{
			K operator()(const K& val)
			{
				return val;
			}
		};
		//typedef
		//类型
		typedef K key_type;
		typedef K val_type;
		typedef SetOfT<K> set_of_key;
		typedef RBTree<key_type, val_type, set_of_key> rb_type;
		typedef K key_type;
		typedef K val_type;
		typedef SetOfT<K> set_of_key;
		typedef RBTree<key_type, val_type, set_of_key> rb_type;
		//typename的作用：声明其为类型。
		typedef typename rb_type::Node Node;
	public:
		//迭代器
		typedef typename rb_type::const_iterator const_iterator;
		//不管是普通还是const迭代器set的key值都不可被修改。
		typedef const_iterator iterator;
		const_iterator begin() const
		{
			return _tree.begin();
		}
		const_iterator end() const
		{
			return _tree.end();
		}
	public:
		Node* find(const K& key)
		{
			return _tree.find(key);
		}
		pair<iterator,bool> insert(const K& data)
		{
			pair<typename rb_type::iterator, bool> k = _tree.insert(data);
			//这里涉及到普通迭代器转换成const迭代器。
			return pair<iterator,bool>(k.first,k.second);
		}
	private:
		rb_type _tree;
	};

3.map

template<class K,class V>
class map
{
	//类型
	typedef K key_type;
	typedef pair<const K, V> val_type;
	template<class K, class V>
	struct MapOfT
	{
		const K operator()(const  pair<const K, V>& val)
		{
			return val.first;
		}
	};
	typedef MapOfT<K, V> map_of_key;
	typedef RBTree<key_type, val_type, map_of_key> rb_type;
public:
	
	typedef typename rb_type::Node Node;
	//迭代器
	typedef typename rb_type::iterator iterator;
	typedef typename rb_type::const_iterator const_iterator;
	typedef V mapped_type;
	iterator begin()
	{
		return _tree.begin();
	}
	const_iterator begin()const
	{
		return _tree.begin();
	}
	iterator end()
	{
		return _tree.end();
	}
	const_iterator end()const
	{
		return _tree.end();
	}
	bool find(const K& key)
	{
		return _tree.find(key);
	}
	pair<iterator,bool> insert(const pair<K,V>& data)
	{
		return _tree.insert(data);
	}
	mapped_type& operator[](const key_type& data)
	{
		pair<iterator, bool> x = _tree.insert(val_type(data,mapped_type()));
		return x.first->second;
	}

private:

	rb_type _tree;
};

总结

 模板，迭代器，仿函数，分开起来，或许不难，但是合起来，还是有点难度的，毕竟封装也是套娃，也挺麻烦的，尤其是模板的一大缺陷，增加了编译器识别问题的难度。

 如果有所帮助，不妨点个赞鼓励一下吧！

更多推荐

【LLM】金融大模型场景和大模型Lora微调实战

文章目录一、金融大模型背景二、大模型的研究问题三、大模型技术路线四、LLaMA家族模型五、Lora模型微调的原理六、基于mt0-large进行Lora微调实战七、对chatglm2进行lora微调Reference一、金融大模型背景金融行业需要垂直领域LLM，因为存在金融安全和数据大多数存储在本地，在风控、精度、实时性

基于中文金融知识的 LLaMA 系微调模型的智能问答系统：LLaMA大模型训练微调推理等详细教学

项目设计集合（人工智能方向）：助力新人快速实战掌握技能、自主完成项目设计升级，提升自身的硬实力（不仅限NLP、知识图谱、计算机视觉等领域）：汇总有意义的项目设计集合，助力新人快速实战掌握技能，助力用户更好利用CSDN平台，自主完成项目设计升级，提升自身的硬实力。专栏订阅：项目大全提升自身的硬实力[专栏详细介绍：项目设计

malloc与free

目录前提须知：malloc：大意：头文件：申请空间：判断是否申请成功：使用空间：结果：整体代码：malloc申请的空间怎么回收呢?注意事项：free:前提须知：为什么要有动态内存分配？我们已经掌握的内存开辟⽅式有：intval=20;//在栈空间上开辟四个字节chararr[10]={0};//在栈空间上开辟10个字节

postgresql-索引与优化

postgresql-索引与优化索引简介索引类型B-树索引哈希索引GiST索引SP-GiST索引GIN索引BRIN索引创建索引唯一索引多列索引函数索引部分索引覆盖索引查看索引维护索引删除索引索引简介索引（Index）可以用于提高数据库的查询性能；但是索引也需要进行读写，同时还会占用更多的存储空间；因此了解并适当利用索引

Web 3.0 发展到什么水平了？

最初，有互联网：电线和服务器的物理基础设施，让计算机和它们前面的人相互交谈。美国政府的阿帕网在1969年发出了第一条消息，但我们今天所知道的网络直到1991年才出现，当时HTML和URL使用户可以在静态页面之间导航。将此视为只读Web或Web1。在2000年代初期，情况开始发生变化。首先，互联网的互动性越来越强;这是一

金融投资公司如何实现创新， 盛创汇凭借人工智能站上硬科技C位

作为硬科技产业的重要组成部分,近年人工智能受到了国家政策的高度重视。在《“十四五”规划和2035年远景目标纲要》中,人工智能被摆放在科技前沿领域攻关方面的首要位置,先后八次被提及。《规划》指出,对新一代人工智能,要在前沿基础理论突破,专用芯片研发,深度学习框架等开源算法平台构建,学习推理与决策、图像图形、语音视频、自然

深入思考redis面经

1redission分布式锁1.1为了保证数据一致性，引入了redission的锁，你是为了抗住高并发而去为了引入这个锁还是说为了保证数据一致性去引入的答：主要是为了抗住高并发问题，解决redis的缓存击穿问题，但是也能解决一定的数据一致性问题。是的，当我们谈到“击穿”问题时，通常指的是缓存击穿，即当某个热点缓存失效时

C++ PrimerPlus 复习 第一章 命令编译链接文件 make文件

第一章命令编译链接文件C++有什么呢？C++源代码文件后缀运行C++过程可执行代码：编译语法：makeMakefile基础语法编写完make只要和将要编译的文件放一起就行然后在该目录使用make命令，就将自动运行；基础的Makefile版本现在的缺点也大\^-\^更加健全的Makefile但还是有不小的缺点常用版本C+

C++设计模式_04_Strategy 策略模式

接上篇，本篇将会介绍C++设计模式中的Strategy策略模式，和上篇模板方法TemplateMethod一样，仍属于“组件协作”模式，它与TemplateMethod有着异曲同工之妙。文章目录1.动机（Motivation）2.代码演示Strategy策略模式2.1传统方法处理2.2怎么用扩展的方式来支持未来的变化呢

PROB: Probabilistic Objectness for Open World Object Detection（论文解析）

PROB:ProbabilisticObjectnessforOpenWorldObjectDetection摘要2相关工作摘要开放世界目标检测（OWOD）是一个新的、具有挑战性的计算机视觉任务，它弥合了传统的目标检测（OD）基准和现实世界中的目标检测之间的差距。除了检测和分类已知/标记的对象外，OWOD算法还应该能够

【论文阅读】Untargeted Backdoor Attack Against Object Detection（针对目标检测的无目标后门攻击）

文章目录一.论文信息二.论文内容0.摘要1.论文概述2.背景介绍3.作者贡献4.重点图表一.论文信息论文题目：UntargetedBackdoorAttackAgainstObjectDetection（针对目标检测的无目标后门攻击）发表年份：2023-ICASSP（CCF-B）作者信息：ChengxiaoLuo（清华

热文推荐
  1. AVL 树

    文章目录一、AVL树的概念二、AVL树的实现1.AVL树的存储结构2.AVL树的插入一、AVL树的概念在二叉搜索树中，当我们连续插入有序的数据时，二叉搜索树可能会呈现单枝树的情况，此时二叉搜索树的查找效率为O(N)俄罗斯的两位数学家G.M.Adelson-Velsky和E.M.Landis发明了AVL树可以解决上述问题

  2. 【计算机毕业设计】基于SpringBoot+Vue贵州旅游系统的设计与实现

    博主主页：一季春秋博主简介：专注Java技术领域和毕业设计项目实战、Java、微信小程序、安卓等技术开发，远程调试部署、代码讲解、文档指导、ppt制作等技术指导。主要内容：毕业设计(Java项目、小程序等)、简历模板、学习资料、面试题库、技术咨询。🍅文末获取联系🍅精彩专栏推荐订阅👇🏻👇🏻不然下次找不到哟Sp

  3. 0/17 SAP Master Data Governance(SAP 主数据治理）

    SAPMasterDataGovernanceTheComprehensiveGuidetoSAPMDG(SAP主数据治理-SAPMDG综合指南）HowThisBookIsOrganized这本书是如何组织的Chapter1Thischapterstartswithanintroductionintothevariou

  4. C++ 太卷，转 Java？

    最近看到知乎、牛客等论坛上关于C++很多帖子，比如：2023年大量劝入C++2023年还建议走C++方向吗？看了一圈，基本上都是说C++这个领域唯一共同点就是都使用C++语言，其它几乎没有相关性。的确是这样，比如量化交易、自动驾驶，客户端，图形学，存储数据库开发，后台开发，嵌入式等等基本上都有各自的领域知识。那么为什么

  5. 循环经济下的新赛道妃鱼助力二手奢侈品行业变革

    自2016年以来，随着国家对于闲置物品利用的政策文件连续发布，我们可以明确地看到一个趋势：我国正在积极鼓励和支持循环经济的发展，这不仅是政策层面的指导，更是反映了新一代消费者的消费观念的转变，在这样的大背景趋势下，二手奢侈品市场开始崭露头角，国泰君安研究报告显示，中国闲置高端消费品零售市场规模已从2016年162亿元增

  6. 【光伏系统】将电流从直流转换为交流电的太阳能逆变器、太阳能跟踪系统来提高系统的整体性能及集成电池解决方案（Simulink仿真）

    💥💥💞💞欢迎来到本博客❤️❤️💥💥🏆博主优势：🌞🌞🌞博客内容尽量做到思维缜密，逻辑清晰，为了方便读者。⛳️座右铭：行百里者，半于九十。📋📋📋本文目录如下：🎁🎁🎁目录💥1概述📚2运行结果🎉3参考文献🌈4Simulink仿真实现💥1概述本文介绍了太阳能仿真技术及其各个组成部分。太阳

  7. NoSQL之 Redis配置与优化

    目录1、关系数据库与非关系型数据库1.1关系型数据库1.2非关系型数据库1.3关系型数据库和非关系型数据库区别1.4非关系型数据库产生背景2、Redis2.1简介2.2Redis具有以下几个优点2.3Redis为什么这么快？3、Redis安装部署3.1Redis命令工具3.2redis-cli命令行工具3.3redis

  8. 金融领域：产业链知识图谱包括上市公司、行业和产品共3类实体，构建并形成了一个节点10w+，关系边16w的十万级别产业链图谱

    项目设计集合（人工智能方向）：助力新人快速实战掌握技能、自主完成项目设计升级，提升自身的硬实力（不仅限NLP、知识图谱、计算机视觉等领域）：汇总有意义的项目设计集合，助力新人快速实战掌握技能，助力用户更好利用CSDN平台，自主完成项目设计升级，提升自身的硬实力。专栏订阅：项目大全提升自身的硬实力[专栏详细介绍：项目设计

  9. SpaceX预计到2022年Starlink用户将达到2000万，但最终达到了100万

    SpaceX的Starlink部门还没有接近实现客户和收入的预测，该公司在建立卫星网络之前与投资者分享了这一点华尔街日报报道今天出版。据报道，2015年的一份题为“SpaceX用来从投资者那里筹集资金”的报告预计，到2022年，Starlink的订户将达到2000万人，并产生近120亿美元的收入和70亿美元的营业利润。