【C++】map，set简单操作的封装实现（利用红黑树）

2023-09-17 15:34:15

文章目录

一、STL中set与map的源码

在这里插入图片描述

在这里插入图片描述

因为关联式容器中存储的是<key, value>的键值对，因此k为key的类型，
ValueType: 如果是map，则为pair<K, V>; 如果是set，则为k
KeyOfValue: 通过value来获取key的一个仿函数类

二、 红黑树结点的意义

我们知道map，和set需要用红黑树来实现，但我们map的数据类型是键值对pair<K,V>类型，key的数据类型是单纯的K类型，那如何写出一个通用的红黑树模板呢？

template<class T>//关键之处
struct RBTreeNode {
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Color _col;//结点颜色
	T _data;
	RBTreeNode(const T&data)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED),
		_data(data)
	{}
};

我们这里把pair<K,V>看成一个整体，我们设计模板的时候就不需要考虑是不是键值对类型，需不需要多传一个模板参数的问题，达到了普适性。

在map中，T传pair<K,V>类型
在set中，T传K类型

三、仿函数的妙用

我们value_type类型用模板参数T代替之后，这个时候就会衍生一个问题，我T可能为键值对类型，我键值对之间怎么比较呢？
例如：T t1与T t2两个变量，我们肯定不能直接比较，肯定要依据他们的键值大小进行比较，所以我们需要自己写一个用于比较的函数，这个时候仿函数刚好能发挥这个用处，可以作为模板参数传入自己写的比较函数

取出他们的键，让他们进行比较，这里set也这样写是为了配合map，因为两者都用的一个红黑树模板

struct SetKeyOfT {
			const K& operator()(const K&key) {
				return key;
			}
		};


struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

示例：红黑树中Find函数的实现：

Node* Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;//KeyOfT为仿函数的类型
		//写好仿函数后先实例化出来
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

四、set，map定义迭代器的区别

因为set插入进去后，set的值不可以被修改，为了实现这一操作我们可以在迭代器上下手

//typename是告诉编译器这里后面跟的是类型不是对象，以免编译器报错
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
//既然不可修改，那我就都用const类型的迭代器

在map中，我们是键不可修改，而其所对应的值可被修改，所以不能用set的那种操作，可以在传模板参数的时候动手脚，传pair的时候直接把K改为const类型

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

五、map，set迭代器的基本操作：

1.begin（） end（）

iterator begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return iterator(leftMin);
	}

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

	const_iterator begin() const
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return const_iterator(leftMin);
	}

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

2.operator++

在这里插入图片描述

1.cur的右不为空访问右树的最左结点
2.cur的右为空，找到cur是parent左子树的位置，此时parent的位置就是++后的位置

Self& operator++()
	{
		if (_node->_right)
		{
			// 右树的最左节点(最小节点)
			Node* subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}

			_node = subLeft;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

3.operator–

–就与++反着来
1.左不为空，找到左树的最右结点
2.左为空，找到cur是parent右的那个结点，此时parent的位置就是–之后的位置

Self& operator--()
	{
		if (_node->_left)
		{
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}

			_node = subRight;
		}
		else
		{
			// 孩子是父亲的右的那个节点
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

六、迭代器拷贝构造特殊处理

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

	__TreeIterator(const Iterator& it)
		:_node(it._node)
	{}

	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}

}；

1.当我们Ptr与Ref分别实例化为T与T&的时候，__TreeIterator(const Iterator& it)就是一个拷贝构造函数，因为Iterator与Self类型相同
2.当我们Ptr与Ref分别实例化为const T与const T&的时候，__TreeIterator(const Iterator& it)是一个构造，支持普通迭代器构造const类型的迭代器因为Self为const类型，Iterator为普通类型
这里支持用普通迭代器去构造const类型的迭代器，就可以满足我们set的插入功能的实现

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
pair<iterator,bool>insert(const K&key){
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
//这里RBTree里面的iterator类型为普通迭代器类型，而我们返回值里面的pair中的iterator为const类型，
//所以要想返回必须先把RBTree中的iterator变为const类型，这个时候可以拷贝构造
//让普通迭代器变为const类型的迭代器
		return pair<iterator, bool>(ret.first, ret.second);
	}

7.源码

这里会涉及到红黑树的一些变色问题，之前的博客有提到过【C++】红黑树插入操作实现以及验证红黑树是否正确
需要的小伙伴可以去看一下

RBTree.h

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

enum Color {
	RED,
	BLACK
};


template<class T>//关键之处
struct RBTreeNode {
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Color _col;//结点颜色
	T _data;
	RBTreeNode(const T&data)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED),
		_data(data)
	{}
};


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

	__TreeIterator(const Iterator& it)
		:_node(it._node)
	{}

	Node* _node;

	__TreeIterator(Node* node)
		:_node(node)
	{}

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

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}

			_node = subRight;
		}
		else
		{
			// 孩子是父亲的右的那个节点
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			// 右树的最左节点(最小节点)
			Node* subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}

			_node = subLeft;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
};


template<class K,class T,class KeyOfT>
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	// 同一个类模板，传的不同的参数实例化出的不同类型
	typedef __TreeIterator<T, T*, T&> iterator;
	typedef __TreeIterator<T, const T*, const T&> const_iterator;

	iterator begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return iterator(leftMin);
	}

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

	const_iterator begin() const
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return const_iterator(leftMin);
	}

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

	Node* Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;//KeyOfT为仿函数的类型
		//写好仿函数后先实例化出来
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}


	pair<iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}

		Node* parent = nullptr;
		Node* cur = _root;

		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}

		cur = new Node(data);
		cur->_col = RED;

		Node* newnode = cur;

		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // u不存在 或 存在且为黑
				{
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   p
						//		c
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				// u存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// g
						//	  p
						//       c
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						// g
						//	  p
						// c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

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


	void RotateL(Node* parent)
	{
		 

		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;
		}

		cur->_left = parent;

		Node* ppnode = parent->_parent;

		parent->_parent = cur;


		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;

			}

			cur->_parent = ppnode;
		}
	}


	void RotateR(Node* parent)
	{
		 

		Node* cur = parent->_left;
		Node* curright = cur->_right;

		parent->_left = curright;
		if (curright)
			curright->_parent = parent;

		Node* ppnode = parent->_parent;
		cur->_right = parent;
		parent->_parent = cur;

		if (ppnode == nullptr)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}

			cur->_parent = ppnode;
		}
	}
private:
	Node* _root = nullptr;
};

2.MyMap.h

#pragma once
#include"RBTree.h"
namespace bit {
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};


	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;


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

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

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

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

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

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


	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;

	};

}

3.MySet.h

#pragma once
#include"RBTree.h"


namespace bit {
	template<class K>
	class set {
		struct SetKeyOfT {
			const K& operator()(const K&key) {
				return key;
			}
		};


	public:
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

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

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

		pair<iterator,bool>insert(const K&key){
			pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
			return pair<iterator, bool>(ret.first, ret.second);
	}


	private:
		RBTree<K, K, SetKeyOfT> _t;

	};
}
更多推荐

前端原生和主流框架是如何dom的

前言随着互联网技术的发展，前端技术也在不断地发展和更新。DOM（DocumentObjectModel）是前端开发中非常重要的一个概念，可以理解为网页上的所有元素都是DOM节点，通过操作这些节点，可以实现网页的动态效果和交互功能。本文将介绍JavaScript操作DOM、jQuery操作DOM、Vue操作DOM、Rea

C++之list

目录一、关于list二、list相关函数三、相关函数的使用1、构造函数2、push_back3、迭代器4、push_front5、pop_back6、insert7、erase关于迭代器失效问题8、splice9、remove10、sort一、关于listlist和string、vector一样，都是容器，都有很强的相

服务器如何提供性能呢？

服务器如何提供性能呢？一、将服务器虚拟化如果同期拥有多个项目，增加额外服务器会显得浪费，成本费用也会大幅度上升，这时不妨通过技术将其划分成多个虚拟空间，而每个空间又可以使用不同操作系统，运行不同应用程序，使得符合项目要求。这种方式通常能增加当前利用率，而不必投资额外的服务器。比如虚拟主机、VPS、云服务器等，就是服务器

spark 数据倾斜优化总结

一、数据倾斜产生原因数据倾斜就是部分task承担了过多的计算任务，导致整个stage都被卡。可能产生数据倾斜的场景如下操作场景join其中一个表比较小，但key值少join大表与大表，但key值中存在过多的特殊值，如0或nulljoinon条件包含key值过滤逻辑，导致部分数据被保留，部分被过滤，最终节点分布不均joi

2023_Spark_实验七：Scala函数式编程部分演示

1、Scala中的函数在Scala中，函数是“头等公民”，就和数字一样。可以在变量中存放函数，即：将函数作为变量的值（值函数）。defmyFun1(name:String):String="Hello"+nameprintln(myFun1("Tom"))defmyFun2():String="HelloWorld"/

大数据-kafka学习笔记

KafkaKafka是一个分布式的基于发布/订阅模式的消息队列（MessageQueue），主要应用于大数据实时处理领域。Kafka可以用作Flink应用程序的数据源。Flink可以轻松地从一个或多个Kafka主题中消费数据流。这意味着您可以使用Kafka来捕获和传输实时数据，并将其发送到Flink进行进一步处理。Fl

创建第一个MyBatis框架--保姆级教学

文章目录前言一、创建一个空的mybatis项目二、创建一个Maven模块三、各个文件的配置四、总结前言在idea上创建我的第一个MyBatis框架一、创建一个空的mybatis项目1、new一个新的项目2、选择最下面，创建一个空项目3、为空项目取一个名字,位置可以自己选4、点击完成后，开始配置以下版本，两个版本得一样，

HDMI字符显示实验

FPGA教程学习第十五章HDMI字符显示实验文章目录FPGA教程学习前言实验原理程序设计像素点坐标模块字符叠加模块实验结果知识点总结前言在HDMI输出彩条的基础上输出osd叠加信息。实验原理实验通过字符转换工具将字符转换为16进制coe文件存放到单端口的ROMIP核中，再从ROM中把转换后的数据读取出来显示到HDMI上

高云FPGA系列教程（9）：cmd-parser串口命令解析器移植

文章目录@[toc]cmd-parser库简介cmd-parser库源码获取GW1NSR-4C移植cmd-parser实际测试cmd-parse命令解析器优化本文是高云FPGA系列教程的第9篇文章。上一篇文章介绍片上ARMCortex-M3硬核处理器串口外设的使用，演示轮询方式和中断方式接收串口数据，并进行回环测试。本

千兆以太网硬件设计及链路层 MAC 协议格式

以太网系列文章：（1）千兆以太网硬件设计及链路层MAC协议格式（2）千兆以太网网络层ARP协议的原理与FPGA实现（3）CRC校验代码原理文章目录前言一、以太网MAC层接口介绍1.MII接口2.GMII接口3.RGMII接口二、以太网（MAC）帧协议介绍前言从本章开始，将分享千兆以太网设计的相关知识。将为大家分享千兆以

基于FPGA的图像sobel锐化实现,包括tb测试文件和MATLAB辅助验证

目录1.算法运行效果图预览2.算法运行软件版本3.部分核心程序4.算法理论概述5.算法完整程序工程1.算法运行效果图预览将FPGA的仿真结果导入到matlab显示图像效果2.算法运行软件版本MATLAB2022a,vivado2019.23.部分核心程序.................................

热文推荐
  1. 贝叶斯人工智能大脑与 ChatGPT

    文章目录一、前言二、主要内容🍉CSDN叶庭云：https://yetingyun.blog.csdn.net/一、前言论文地址：https://arxiv.org/abs/2308.14732这篇论文旨在研究ChatGenerativePre-trainedTransformer（ChatGPT）在贝叶斯推理情况下解

  2. List与ArrayList

    目录一、List及其使用1.1List的概念1.2常见接口的介绍1.3List的使用二、线性表和顺序表2.1线性表2.2顺序表三、ArrayList介绍四、ArrayList的使用4.1ArrayList构造4.2ArrayList的常用方法4.3ArrayList的遍历4.4ArrayList的扩容机制五、Array

  3. 三分钟图解事务隔离级别

    详细见：三分钟图解事务隔离级别，看一遍就懂数据库中事务指的是什么“锁"是数据库系统区别于文件系统的一个关键特性，其对象是事务，用来锁定的是数据库中的对象，如表、页、行等。锁确实提高了并发性，但是却不可避免地存在一些潜在的并发一致性问题。不过好在锁只会带来四种问题（丢失更新、脏读、不可重复读、幻读），如果可以防止这四种情

  4. 项目设计集合（人工智能方向）：助力新人快速实战掌握技能、自主完成项目设计升级，提升自身的硬实力（不仅限NLP、知识图谱、计算机视觉等领域）

    优质项目专栏：提升自身的硬实力：汇总有意义的项目设计集合，助力新人快速实战掌握技能，助力用户更好利用CSDN平台，自主完成项目设计升级，提升自身的硬实力。专栏订阅：项目大全提升自身的硬实力资料合集更优惠第一期资料合集：https://download.csdn.net/download/sinat_39620217/8

  5. 一文详解 requests 库中 json 参数和 data 参数的用法

    在requests库当中，requests请求方法，当发送post/put/delete等带有请求体的请求时，有json和data2个参数可选。众所周知，http请求的请求体格式主要有以下4种：application/jsonapplicaiton/x-www-from-urlencodedmultipart/form

  6. 03-JavaScript-函数

    函数就是将特定功能的代码封装起来，当需要实现特定功能时，直接调用函数实现即可。一、函数定义和使用1.1定义函数语句式命名函数functionsum(a,b){returna+b;}变量函数表达式是一个匿名函数，它没有函数名letsum=function(a,b){returna+b;};1.2调用函数按顺序传入参数co

  7. 网络基础-应用层协议-HTTP/HTTPS

    HTTP/HTTPSHTTP基本概念协议格式请求报文请求方法请求资源地址协议版本应答报文常见Header常见状态码与状态描述Cookie&Sessionhttp协议特点HTTPS基本概念对称加密与非对称加密数据摘要&数据指纹HTTPS工作过程探究只采用对称加密只采用非对称加密双方都采用非对称加密对称加密+非对称加密中间

  8. 手机提词器有哪些？简单介绍这一款

    手机提词器有哪些？手机提词器在现代社会中越来越受欢迎，原因是它可以帮助人们提高演讲和朗读的效果。使用手机提词器可以让人们更加自信地面对演讲和朗读，不至于出现口误或读错字的情况。此外，手机提词器还可以帮助人们节省时间和精力，让人们可以更加专注于演讲和朗读的内容。目前市面上有很多种手机提词器，今天就给大家介绍一款好用的手机

  9. Harmony系统更改手机IP

    在当今的互联网环境中，我们经常需要更改手机的IP地址来绕过限制或保护我们的隐私。虽然在一些操作系统上更改IP地址相对较容易，但在Harmony系统上，这可能会有些困难。因此，本文将分享一种在Harmony系统上免费更改手机IP地址的方法。在Harmony系统上，我们可以通过使用VPN（VirtualPrivateNet