程序员经验分享-hwhale

【C++】封装map和set（红黑树实现）

2023-10-27

前言：

       前面，我们学习了set和map的用法，这两个容器可以完成查找，排序等操作，后来我们在学习过二叉搜索树的基础上又学习了两种特殊的二叉搜索树——AVL树和红黑树，他们俩可以是效率进一步提高，其实set和map的底层就是由红黑树封装而成的！

       所以，本篇文章我们自己学习用红黑树封装set和map。用红黑树封装，特别是用同一棵红黑树实现封装有一定的难度，其中很多操作（比如复用）我们会第一次尝试，所以大家请跟紧作者的脚步来。

目录

（一）如何复用同一棵红黑树

（二）红黑树的改造流程（为封装做铺垫）

1、结点的定义

2、模拟实现结点的比较大小

3、改造后的红黑树

4、map和set迭代器的模拟实现

4.1模版参数的构成

4.2begin()和end()的模拟实现

4.3operator* 和 operator->模拟实现

4.4 operator++ 和 operator--模拟实现

4.5 operator== 和 operator!=模拟实现

4.6迭代器代码详解

 （三）封装map和set

（一）如何复用同一棵红黑树

前提疑问：

在我们这所有的之前我们知道，map和set这两个容器都是用红黑树来实现的，那么就有了接下来的问题。

  • map和set都是用的同一棵红黑树复用的吗
  • 或者这两个容器各自使用一棵红黑树吗

其实在前言中我们就知道了，根据STL的设计理念和泛型编程的理念，我们不会冗余的写两课红黑树，而是用一棵红黑树实现复用的效果。

我们调用STL库中的原码来看：

我们发现：

  • STL库中的原码也确实调用的同一棵红黑树
  • 他们实现的都是key_value模型

我们设set中存放结点的值是K，map中存放的节点是pair<key,value>键值对：

  • 对于set而言，底层红黑树的模版就是RBTree<K, K>
  • 对于map而言，底层红黑树的模版就是RBTree<K, pair<K, V>>

这时我们就有了另一个疑问，两个模板参数的第一个Key，不能省略掉吗？？

  • 首先，答案肯定是不能的
  • 那么原因又是什么呢？

因为map的这个类中，无论怎么省略都会有一个查找函数要单独用到Key

如果第一个Key删去了，那么map和set的查找函数就没法统一实现了，违背了我们一开始泛型编程的思想。

综上所述：

  • map和set都是用了，Key_value模型
  • set中的K是K，V也是K
  • map中的K是K，V是pair<K，V>
  • 并且模板参数中第一个K都不能省

（二）红黑树的改造流程（为封装做铺垫）

1、结点的定义

这里由于set和map存放的结点一个是Key一个是pair<Key,Value>，所以我们使用模版，把存放的结点泛化。

2、模拟实现结点的比较大小

  • 上述提到，在模拟实现中，map和set我们复用同一棵红黑树的时候都是用的是Kye_value的结构
  • 但是红黑树中的数据比较又是Key值的比较，而现在我们用的则是pair的比较
  • 虽然编译上是可以通过但是真的就是我们所想要的吗？

pair的比较大小：

很显然这种比较规则不是我们所想要的，并且map和set想要取到用来比较的数据是不同的。 

为了取到我们想要的数据，我们引入了仿函数：

  • 根据map和set的需求不同
  • 我们在红黑树中新引入了一个模板参数KeyOfT

 

引入KeyOfT模板参数后，我们想要不同方式的比较方法只需要在set和map的封装中给出属于他们自己的比较仿函数。

map中的仿函数： 

set中的仿函数：

使用方法：

 此时前面所说的仿函数的便利之处就体现出来了。

3、改造后的红黑树

具体代码：

//红黑树的实现
//KeyOfT --> 支持取出T对象中key的仿函数
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;

	//构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的

	//迭代器中序遍历，要找最左结点
	iterator Begin()
	{
		Node* subLeft = _root;
		while (subLeft && subLeft->_left)
		{
			subLeft = subLeft->_left;
		}

		//树的迭代器用结点的指针就可以构造
		return iterator(subLeft);
	}

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

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

		//树的迭代器用结点的指针就可以构造
		return const_iterator(subLeft);
	}

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

	pair<iterator, bool> Insert(const T& data)
	{
		//1、搜索树的规则插入
		//2、看是否违反平衡规则，如果违反就需要处理：旋转
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK; //根节点是黑色
			return make_pair(iterator(_root), true);
		}

		KeyOfT kot;

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

		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); 
		Node* newnode = cur;
		cur->_col = RED;

		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;
			assert(grandfather);

			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况一：（叔叔存在且为红）
				if (uncle && uncle->_col == RED)
				{
					//祖父和叔叔变成黑色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况二：（叔叔不存在 or 叔叔存在且为黑）
				else
				{
					//单旋
					//	   g
					//	 p
					// c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//双旋
					//    g
					//  p
					//    c
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			//无论父亲和叔叔是左是右都是一样的
			//grandfather->_right == parent;
			else
			{
				Node* uncle = grandfather->_left;
				//情况一：
				if (uncle && uncle->_col == RED)
				{
					//祖父和叔叔变成黑色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

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

					break;
				}
			}
		}

		//父亲为空就出循环，将根节点设置成黑色
		_root->_col = BLACK;

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

插入（Insert）和寻找（Find）代码：
 


	Node* Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		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<itertaor, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;

			return make_pair(itertaor(_root), true);
		}

		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		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(itertaor(cur), false);
			}
		}

		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) > kot(data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				// 情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//     g
					//   p   u
					// c 
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   p   u
						//     c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						//parent->_col = RED;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // (grandfather->_right == parent)
			{
				//    g
				//  u   p
				//        c
				Node* uncle = grandfather->_left;
				// 情况1：u存在且为红，变色处理，并继续往上处理
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 情况2+3：u不存在/u存在且为黑，旋转+变色
				{
					//    g
					//  u   p
					//        c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						//    g
						//  u   p
						//    c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

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

4、map和set迭代器的模拟实现

上面改造后的红黑树中已经涉及到了迭代器，这里我们来模拟实现。

备注：

  • T：数据
  • Ref：引用
  • Ptr：指针
  • Sef：iterator本身

4.1模版参数的构成

要想实现同一棵红黑树的复用，模版参数的构成极为重要。

之前我们也遇到过相似的情况，我们这里的实现方法参看之前。

迭代器的实现中：

  • 涉及到了*解引用操作，返回的是数据的引用；
  • 涉及到了->指针操作，返回的是数据的地址;
  • 涉及到++，--操作，返回的是操作后迭代器本身的位置。

但是以上的行为，我们都涉及结点，所以结点的数据类型也尤为重要！

综上，模版参数的构成如下图：

4.2begin()和end()的模拟实现

  • 因为是二叉搜索树，为了更有顺序，所以我们采取的是中序遍历。
  • 那么中序遍历Begin（）就应该是最左结点
  • 我们实现的版本中End（）定义为空是（nullptr）

ps：

而库中的红黑树则是设计了一个哨兵位的头结点：

所以我们实现的只是简化版本。

4.3operator* 和 operator->模拟实现

就是正常的运用operator，但是operator->和list中讲的一样，返回的是地址的原因是为了连续访问（连续的operator->会优化成一个->）

4.4 operator++ 和 operator--模拟实现

这里迭代器的++和- - 需要分类一下，分别是：前置++，- - 、后置++，- -

前置++ ：
因为我们是中序遍历，我们访问完自己之后，下一个该访问哪一个结点？

我们观察任何一棵二叉树都能看出，无非是下面两种情况：

分如下两种情况：（重点）

  • 右子树为空：找孩子是父亲的左的那个祖先节点，否则继续往上走，直到空（nullptr）
  • 右子树为非空：找右子树的最左节点

这一过程有点类似于递归思想，但是是非递归实现的

代码实现：

 前置-- ：

有了上面的思路，我们联想一下，现在需要看当前位置左子树是否是空。

前置- -就是倒着走，同样还是对当前位置分两种情况：（重点）

  1. 左子树为空：找孩子是父亲的右的那个祖先节点，否则继续往上走，直到空（nullptr）
  2. 左子树为非空：找左子树的最右节点

只要前置++理解了，那么前置- -完全就是前置++倒过来走一遍。

后置++、后置- - ：

和之前实现容器的得带器一样，我们这里直接复用即可：

4.5 operator== 和 operator!=模拟实现

有了之前封装迭代器的经验，这两个的视线还是比较容易得：

4.6迭代器代码详解

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	Node* _node;

	typedef __RBTreeIterator<T, Ref, Ptr> Self;

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

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

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

	Self& operator++()
	{
		if (_node->_right == nullptr)
		{
			//找祖先里面，孩子是父亲左的那个
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}
		else
		{
			//右子树的最左结点
			Node* subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}

			//左为空
			_node = subLeft;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node->_left == nullptr)
		{
			//找祖先里面，孩子是父亲
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}
		else
		{
			//左子树的最右结点
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}

			_node = subRight;
		}

		return *this;
	}

	Self operator++(int)
	{
		Self tmp(*this);

		++(*this);

		return tmp;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		
		--(*this);

		return tmp;
	}

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

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

 （三）封装map和set

有了上面的红黑树的改装，我们这里的对map和set的封装就显得很得心应手了。

封装主要是把map和set的基本操作封装在一个类中。

map的封装：

template<class K, class V>
class map
{
	//定义一个内部类
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)//operator() 可以像函数一样去使用
		{
			return kv.first;
		}
	};

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

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

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

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

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

这里map中的operator[ ]我们知道其原理之后，模拟实现就非常方便，直接调用插入函数，控制好参数和返回值即可。

对set的封装：

template<class K>
class set    
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)//operator() 可以像函数一样去使用
		{
			return key;
		}
	};
public:

	//加上typename告诉编译器这是个类型，类模板实例化了再去取
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

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

	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);
		auto ret = _t.Insert(key);
		return pair<iterator, bool>(iterator(ret.first._node), ret.second);
	}

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

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

附详细代码：——》红黑树封装map和set

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

数据结构

【C++】封装map和set（红黑树实现） 的相关文章

随机推荐

  • in和=无法查出为NULL的值

    select from base persons x where x pname in null select from base persons x where x pname null 以上两句查询结果为空 虽然表里有相应的值 Id N

  • PAT 1152 Google Recruitment

    原题链接 1152 Google Recruitment 20分 题意 从任一给定的长度为 L 的数字中 找出最早出现的 K 位连续数字所组成的素数 关键词 字符串 判断质数 输入格式 输入在第一行给出 2 个正整数 分别是 L 和 K 接

  • python机器学习之数据的预处理（五种方式数据处理案例详解）

    数据的预处理 数据下载地址 gt 点这里下载 到入文件时可以直接复制地址然后用r 包裹起来 例如 data pd read cav r C work data csv 或者也可以以直接将 换成 也可以导入 1 归一化 在sklearn当中

  • Nginx四层代理和7层反向代理

    Nginx四层代理和7层反向代理 文章目录 Nginx四层代理和7层反向代理 Nginx四层代理配置 Nginx四层代理配置步骤 配置好两台Nginx七层代理服务器 在四层代理的Nginx服务器上做相关配置 测试结果 Nginx四层代理配置

  • vscode设置选项卡换行

    ctrl shift p打开命令输入窗口 输入preference 选择打开工作区设置 输入wrap tabs 勾选wrap tabs 可以多行显示了

  • Vue应用方法、实例属性、实例方法$refs、vm.$nextTick等

    应用方法 实例属性 实例方法 Vue 中对部分特殊的属性和功能方法进行特殊指代定义 用于提供独立的执行和 获取方式 应用方法 mount 所提供 DOM 元素的 innerHTML 将被替换为应用根组件的模板渲 染结果 unmount 卸载

  • java prepare_java中prepareStatement与createStatement的区别

    首先来看两段代码 第一个使用createStatement 1 public void delete intid 2 try 3 Connection c DBUtil getConnection 4 Statement s c creat

  • Nginx之location匹配规则

    什么是location nginx就是通过拦截到的请求去对配置好的location块 location block 进行请求代理的 被代理的URL去对location后边的字符串 或正则 根据一定的规则进行匹配 然后执行对应location

  • 你是否曾质疑过DB-Engine的数据库排名？

    在谈论数据库的最新趋势时 我们习惯了参考DB Engine上所提供的排名信息 每当新的报告出来时 我们也时常看到各个媒体网站争先发布关于最新排名的分析内容 如标题所言 你是否曾质疑过DB Engine所给出的这份排名 如下是2018年3月份

  • php后台接收blob文件流,php – 我们如何访问服务器中的文件blob？

    在上传大于maxChunkSize的文件时 我们如何在服务器中单独访问每个上传的文件blob 我的问题是我需要使用后端api将上传的文件在单独的blob中转发到不同的服务器 到目前为止 看看wiki 对于1 mb的块 我在js中添加了以下内

  • Python logging将日志输出到Kafka

    Python logging用于输出Python程序运行的日志 现实中往往一个项目会部署在多台机器之上 这种情况下 为了方便对各主机运行日志进行收集 往往会使用消息队列 通过消息队列将各台机器上的日志收集并写入日志文件 本文使用Python

  • linux库概念及其编程

    分文件编程案例 好处 分文件编程思想 功能责任划分 方便调试 主程序简洁 例子 demo c include

  • 在外包做了3年，离职后成功入职字节跳动....

    最近换了份工作 当时和群里的朋友也聊过换工作的话题 他们都觉得这是一次非常冒险的行为 说我这是一次豪赌 成了会有更好的职业发展 没成可能就会出现两三年的发展断层 甚至影响职业生涯路径 一步错 步步错 我当时也仔细的考虑过了 的确有很大的风险

  • STM32标准IIC驱动

    IIC Inter Integrated Circuit 总线是一种由 PHILIPS 公司开发的两线式串行总线 用于连接 微控制器及其外围设备 也是目前很流行的通讯总线 使用IIC总线做产品能够很大程度上降低PCB的布线难度 以及布线数量

  • fio使用good blog

    Linux应用 磁盘IO读写测试工具 FIO详解 协议森林的博客 CSDN博客 fio读写测试 编译安装 常用参数 实例 结果说明 SSD测试第一神器 FIO 磁盘IO体系架构与存储解决方案 pudn com 磁盘性能指标 IOPS与吞吐量

  • DC-5靶场（一般详细）

    目录 简介 一 找IP地址 二 扫描IP端口 三 找web漏洞 文件包含 四 拿webshell 五 提权 总结 简介 dc系列靶场是比较适合新手的黑盒测试靶场 其中dc 5靶场下载连接如下 dc 5靶场下载地址 一 找IP地址 netdi

  • 蓝桥杯2013c++真题：振兴中华

    思路一 dfs暴力搜索 从我做起振兴中华分别为12345678 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 迷宫问题模板 dfs x y path 从 x y 深度优先搜索 if x y为终点坐标 x y

  • 静态库的生成与使用

    1 静态库的生成与使用 1 我自己写一个 c 文件 里面存放我定义的函数 1 include

  • 酷炫网页按钮，炫酷变色效果（附源码）

    酷炫网页按钮 效果如下图 目录如下 html代码如下 index html a href sunbtton a css代码 inedex css margin 0px padding 0px body

  • 【C++】封装map和set（红黑树实现）

    前言 前面 我们学习了set和map的用法 这两个容器可以完成查找 排序等操作 后来我们在学习过二叉搜索树的基础上又学习了两种特殊的二叉搜索树 AVL树和红黑树 他们俩可以是效率进一步提高 其实set和map的底层就是由红黑树封装而成的 所

热门标签