C++:map和set的封装原理

文章目录

  • 红黑树的封装
  • map和set的封装
  • 红黑树迭代器的实现
    • operator ++ 和 -- 的实现
      • ++的实现过程
    • 迭代器的其他模块
  • 整体实现

本篇写于红黑树模拟实现后,对map和set进行封装,模拟实现map和set内部的原理

首先,map和set的底层逻辑是红黑树,那么就意味着不再需要像vector/list这样重新进行写入,而是直接在红黑树的基础上进行适当的封装即可

但是,前面实现的红黑树并不能完美的适配所需要的功能,因此要在一定程度上对红黑树进行改造后,才能很好的使用,那么下面首先要对红黑树进行一定程度的改造

本篇将分析STL库中对红黑树的封装原理,搭建出基础的框架,并进行分析

红黑树的封装

拿出一份关于STL中的源码,分析源码中是如何对这这棵树进行封装的

在红黑树的定义中就不太一样,在前面实现的过程中,是直接将pair键值对当做模板中的参数的,导致只有两种,一种是Key/Key模型,一种是Key/Value模型,而在源码的实现中,则是直接将类型放到模板中来实现,用泛型的思想编程
在这里插入图片描述
在map和set中,传参直接将需要传递的参数传到Value处:

在这里插入图片描述
因此在封装的时候,就可以这样进行封装,先对我们自己完成的红黑树进行一些改善

首先,对节点进行改善

template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Color _col;
};

map和set的封装

下面可以对map和set进行初步封装了

namespace mymap
{
	template<class K, class V>
	class set
	{
	private:
		RBTree<K, pair<K, V>> _t;
	};
}


namespace myset
{
	template<class K>
	class set
	{
	private:
		RBTree<K, K> _t;
	};
}

下一个遇到的问题是,在插入数据的时候如何比较大小呢?例如下面的场景

在这里插入图片描述
上面是在模拟实现红黑树的过程中实现的逻辑,现在问题是,如何对于键值对进行比较?

在库函数中寻找对策:

在这里插入图片描述
比较的规则是比较键值对的第一个元素,因此现在需要做的就是想办法取出来键值对的第一个元素进行比较,因此就可以采取这样的思想,在map和set中都搞一个能把数据取出来的仿函数,在进行比较的时候返回的是Key即可,因此要修改红黑树的模板参数,接收一个仿函数的值,并用其来参与插入数据时的比较

namespace mymap
{
	template<class K, class V>
	class map
	{
	private:
		struct MapKeyOfT
		{
			const K& operator()(const V& data)
			{
				// 对于map来讲,Key是传入的data键值对中的第一个元素
				return data.first;
			}
		};
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};
}

namespace myset
{
	template<class K>
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& data)
			{
				// 对于set来讲,K就是data本身
				return data.first;
			}
		};
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}

此时基本逻辑就已经搭建起来了,在map/set中进行插入元素,实际上就是插入到树中,在外部再对这个插入的过程进行一次封装

在这里插入图片描述

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

红黑树迭代器的实现

于是,要实现出红黑树的迭代器,红黑树的迭代器和链表的迭代器类似,都要借助一个类来构建

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

	// 构造函数:迭代器的本质就是封装了一层指针
	_TreeIterator(Node* node)
		:_node(node)
	{}

	// 迭代器中功能的实现
	// 解引用取数据
	Ref operator*()
	{
		return _node->_data;
	}

	// 取数据的地址
	Ptr operator->()
	{
		return &(_node->_data);
	}

	//  实现++



	// 迭代器的本质是节点的指针
	Node* _node;
};

operator ++ 和 – 的实现

++的实现过程

在这里插入图片描述

以上图为例,此时指向的是17,从正常来说遍历次序是按照中序遍历,因此比17大的下一个数是22,总结出结论就是,++要寻找的是右孩子的最左子树,如果没有右子树如何处理?

在这里插入图片描述

如果没有右子树,就说明此时已经到了遍历结束了左子树,如上图所示,此时要找的是,孩子是父亲左的那个节点的祖先

根据上述逻辑,完善迭代器的代码

	//  实现++
	Self& operator++()
	{
		//  如果右子树存在,就到右子树中找最左节点
		if (_node->_right)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		// 如果右子树不存在,就到孩子是父亲左的那个祖先
		else
		{
			// 左子树 根 右子树
			Node* cur = _node;
			Node* parent = cur->_parent;
			// 只要孩子是父亲的右,就继续向上循环找,直到找到孩子是父亲左的那个节点
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	// 实现--
	Self& operator--()
	{
		//  如果左子树存在,就到左子树中找最右节点
		if (_node->_left)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}

			_node = cur;
		}
		// 如果左子树不存在,就到孩子是父亲右的那个祖先
		else
		{
			// 左子树 根 右子树
			Node* cur = _node;
			Node* parent = cur->_parent;
			// 只要孩子是父亲的左,就继续向上循环找,直到找到孩子是父亲右的那个节点
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

迭代器的其他模块

	// 判断相等和不相等,实际上就是看迭代器内部封装的节点是否是同一个节点即可
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}

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

整体实现

改造过后的红黑树

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

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Color _col;
};

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

	// 构造函数:迭代器的本质就是封装了一层指针
	_TreeIterator(Node* node)
		:_node(node)
	{}

	// 迭代器中功能的实现
	// 解引用取数据
	Ref operator*()
	{
		return _node->_data;
	}

	// 取数据的地址
	Ptr operator->()
	{
		return &(_node->_data);
	}

	//  实现++
	Self& operator++()
	{
		//  如果右子树存在,就到右子树中找最左节点
		if (_node->_right)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		// 如果右子树不存在,就到孩子是父亲左的那个祖先
		else
		{
			// 左子树 根 右子树
			Node* cur = _node;
			Node* parent = cur->_parent;
			// 只要孩子是父亲的右,就继续向上循环找,直到找到孩子是父亲左的那个节点
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	// 实现--
	Self& operator--()
	{
		//  如果左子树存在,就到左子树中找最右节点
		if (_node->_left)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}

			_node = cur;
		}
		// 如果左子树不存在,就到孩子是父亲右的那个祖先
		else
		{
			// 左子树 根 右子树
			Node* cur = _node;
			Node* parent = cur->_parent;
			// 只要孩子是父亲的左,就继续向上循环找,直到找到孩子是父亲右的那个节点
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	// 判断相等和不相等,实际上就是看迭代器内部封装的节点是否是同一个节点即可
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}

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

	// 迭代器的本质是节点的指针
	Node* _node;
};

template<class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef _TreeIterator<T, T*, T&> iterator;
	//  红黑树的构造函数
	RBTree()
		:_root(nullptr)
	{}

	// 红黑树的析构函数
	~RBTree()
	{
		DelNode(_root);
	}

	// 红黑树迭代器部分
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}

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

	// 元素的插入
	pair<iterator, bool> insert(const T& data)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		KeyOfT kot;
		// 根据搜索二叉树的基本逻辑完成
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}
		else
		{
			// 插入数据
			while (cur)
			{
				if (kot(cur->_data) > kot(data))
				{
					// 插入元素小于当前节点元素,插入到左边
					parent = cur;
					cur = cur->_left;
				}
				else if (kot(cur->_data) < kot(data))
				{
					// 插入元素大于当前节点元素,插入到右边
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return make_pair(iterator(cur), false);
				}
			}
			// 此时parent指向最后一个节点,cur为空
			cur = new Node(data);
			if (kot(parent->_data) > kot(cur->_data))
			{
				// 如果插入节点小于它的父亲,就插入到左边
				parent->_left = cur;
				cur->_parent = parent;
			}
			else
			{
				// 如果插入节点大于它的父亲,就插入到右边
				parent->_right = cur;
				cur->_parent = parent;
			}
		}

		// 至此,普通二叉搜索树的插入已经完成,该进行红黑树的高度调整了
		// 终止条件是parent为空,或者parent已经是黑色了,就意味着不需要调整了
		// parent是红色,意味着grandparent一定存在
		while (parent && parent->_col == RED)
		{
			// 更变的核心是舅舅,因此要先找到舅舅
			// 整体来说还有两种情况,parent可能是grandparent的左或者右,舅舅就是另外一边
			Node* grandparent = parent->_parent;
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				// 1. 舅舅存在,并且是红色
				if (uncle && uncle->_col == RED)
				{
					//     g
					//   p   u
					// c

					// 变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 向上处理
					cur = grandparent;
					parent = cur->_parent;
				}

				// 2. 舅舅不存在
				else
				{
					// 如果cur是左孩子
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c

						// 对grandparent进行右旋
						RotateR(grandparent);
						// 变色
						cur->_col = grandparent->_col = RED;
						parent->_col = BLACK;
					}
					// 如果cur是右孩子
					else
					{
						//     g               g
						//  p       -->     c         -->    c
						//    c           p                p   g

						// 对parent左旋,对grandparent右旋
						RotateL(parent);
						RotateR(grandparent);
						// 变色
						cur->_col = BLACK;
						parent->_col = grandparent->_col = RED;
					}

					// 更新之后parent和grandparent顺序乱了,而且也不需要继续调整了,直接break
					break;
				}
			}

			// parent是grandparent的右孩子,相同的逻辑再进行一次
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

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

						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}

					break;
				}
			}
		}
		// 不管上面怎么变都无所谓,只需要保证根节点是黑的就可以了
		_root->_col = BLACK;

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

private:
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;

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

			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

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

			subL->_parent = parentParent;
		}
	}

	void DelNode(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		DelNode(root->_left);
		DelNode(root->_right);
		delete(root);
	}

	Node* _root = nullptr;
};

依据红黑树封装出的set

#pragma once

#include "RBTree.h"

namespace myset
{
	template<class K>
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& data)
			{
				// 对于set来讲,K就是data本身
				return data;
			}
		};
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

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

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

		iterator end()
		{
			return _t.end();
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}

依据红黑树构造出的map

#pragma once

#include "RBTree.h"

namespace mymap
{
	template<class K, class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& data)
			{
				// 对于map来讲,key是键值对的第一个元素
				return data.first;
			}
		};
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		pair<iterator, bool> insert(const pair<K, V>& val)
		{
			return _t.insert(val);
		}

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

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

		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};
}

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

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

相关文章

idea生成代码(一):实现java语言的增删改查功能(基于EasyCode插件)支持自定义模板【非常简单】

idea生成代码&#xff08;一&#xff09;&#xff1a;实现java语言的增删改查功能&#xff08;基于EasyCode插件&#xff09;支持自定义模板【非常简单】 idea生成代码&#xff08;二&#xff09;&#xff1a;实现java语言的增删改查功能&#xff08;基于mybatis-plus代码生成器…

centralwidget 不能布局

必须要在QT ui中添加一个任意的子控件&#xff08;比如添加了一个pushButton&#xff09;&#xff0c;然后在centralwidget 才能右键设置布局&#xff0c;成功去掉centralwidget 右下角的红色的标记。

视频直播点播平台EasyDSS无法删除分组,如何解决?

EasyDSS视频推拉流平台可支持用户自行上传视频文件&#xff0c;也可将上传的点播文件作为虚拟直播进行播放。平台能支持多屏播放&#xff0c;可兼容Windows、Android、iOS、Mac等操作系统&#xff0c;还能支持CDN转推&#xff0c;具备较强的可拓展性与灵活性。 有用户反馈&…

Facebook账号运营技巧

Facebook作为全球知名的社交媒体平台之一&#xff0c;坐拥着庞大的用户群体&#xff0c;吸引大量的跨境电商加入&#xff0c;那么肯定就会有少部分的卖家对于Facebook账号运营不是很了解&#xff0c;下面小编将讲一下Facebook账号运营的一些小技巧。 1、明确目标受众 首先需要明…

STM32F103C8 PC13端口无输出原因

如果开启了RTC功能&#xff0c;就要注意PC13端口的设置。要把RTC OUT 由“Disable”改成“No RTC Output”&#xff0c;才行。

创新旗舰X100:手机周期大考下,vivo的“满分答案”

对于智能手机行业来说&#xff0c;今年是触底反弹&#xff0c;逆转上扬的一年。 利好在于&#xff0c;科技与经济双周期拐点已经到来。在当前消费结构升级的关键阶段&#xff0c;随着经济持续恢复向好&#xff0c;国内总的消费趋势正稳步向上。 一直以来&#xff0c;智能手机…

IP-guard flexpaper远程命令执行漏洞复现 [附POC]

文章目录 IP-guard flexpaper RCE漏洞复现 [附POC]0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 0x06 修复建议 IP-guard flexpaper RCE漏洞复现 [附POC] 0x01 前言 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测…

Center Smoothing Certified Robustness for Networks with Structured Outputs

文章目录 Center Smoothing: Certified Robustness for Networks with Structured OutputsSummaryResearch ObjectiveProblem StatementMethodsEvaluationConclusionNotesGaussian Smoothing常用希腊字母霍夫丁不等式&#xff08;Hoeffdings inequality&#xff09;1.简述2.霍夫…

关于dinput8.dll丢失的问题,提供六种解决办法

不知dinput8.dll文件大家是否有所了解&#xff0c;或者你的电脑中是否出现过关于dinput8.dll文件丢失问题。如果你的电脑中出现了关于dinput8.dll丢失的问题&#xff0c;那么这篇文章给大家提供六种解决dinput8.dll丢失的办法。希望能够帮助大家解决dinput8.dll丢失。 一.dinpu…

今日最新版早安问候大全,创意好看的早上好祝福图片带字温馨

1、阳光照&#xff0c;鸟欢叫&#xff0c;小懒猪&#xff0c;起床了&#xff0c;伸懒腰&#xff0c;笑一笑&#xff0c;深呼吸&#xff0c;精神好&#xff0c;开心到&#xff0c;欢乐抱&#xff0c;幸福随&#xff0c;乐淘淘&#xff0c;好运伴&#xff0c;祝福来&#xff0c;每…

STM32H750之FreeRTOS学习--------(六)FreeRTOS的列表和列表项

六、FreeRTOS的列表和列表项 文章目录 六、FreeRTOS的列表和列表项列表相关结构体列表项相关结构体迷你列表项列表相关API函数介绍初始化列表vListInitialise()函数vListInitialiseItem()函数vListInsert()函数 vListInsertEnd()函数 uxListRemove() 列表就是一个双向链表&…

C++——内存管理(new/delete使用详解)

C内存管理 本章思维导图&#xff1a; 注&#xff1a;本章思维导图对应的xmind文件和.png文件已同步导入至资源 1. C/C内存区域的划分 在C/C中&#xff0c;内存区域主要划分为&#xff1a;内核区域、栈区、内存映射段、堆区、数据段、代码段等区域&#xff0c;如图&#xff1…

Linux系统软件安装方式

Linux系统软件安装方式 1. 绿色安装2. yum安装3. rpm安装3.1 rpm常用命令 4. 源码安装4.1 安装依赖包4.2 执行configure脚本4.3 编译、安装4.4 安装4.5 操作nginx4.6 创建服务器 1. 绿色安装 Compressed Archive压缩文档包&#xff0c;如Java软件的压缩文档包&#xff0c;只需…

面试?看完这篇就够了-深入分析从点击应用图标到应用界面展示

作者&#xff1a;GeeJoe 从点击桌面图标到应用界面展示 从桌面点击图标到应用界面第一帧绘制出来&#xff0c;整个流程涉及的过程复杂&#xff0c;为了便于理解&#xff0c;这里将整个流程分为四个阶段&#xff1a;应用进程启动阶段、应用进程初始化阶段、Activity 启动阶段、…

Linux系统中如何开启和配置OpenGauss数据库的远程连接(1)

文章目录 前言1. Linux 安装 openGauss2. Linux 安装cpolar3. 创建openGauss主节点端口号公网地址4. 远程连接openGauss5. 固定连接TCP公网地址6. 固定地址连接测试 前言 openGauss是一款开源关系型数据库管理系统&#xff0c;采用木兰宽松许可证v2发行。openGauss内核深度融合…

基于ISO13209(OTX)实现EOL下线序列

一 OTX是什么&#xff1f; OTX&#xff0c;全称Open Test sequence eXchange format&#xff0c;即开放式测试序列交换格式&#xff0c;国际标准&#xff1a;ISO13209&#xff0c;是专为汽车行业制定的序列开发标准。在车辆诊断、自动化标定和ECU测试等领域有广泛应用。OTX不仅…

使用Python轻松实现科研绘图

当撰写在学术期刊上发表的文章时&#xff0c;图表的布局和风格应符合预定义的格式要求。这样可以确保该出版物的所有文章都具有一致的风格&#xff0c;并且任何包含的图表在打印时都是高质量的。 Python在科学界广泛使用&#xff0c;并提供了创建科学绘图的好方法。然而&#…

初始化后执行kubectl get nodes报错:The connection to the server localhost:8080

K8S初始化后&#xff0c;worker节点加了master节点&#xff0c;在master执行kubectl get nodes 报错&#xff0c;这个原因看是路径的问题导致 [rootk8s-master01 ~]# kubectl get nodes E1114 16:28:52.032089 2254 memcache.go:265] couldnt get current server API group…

使用Docker本地安装部署Drawio绘图工具并实现公网访问

目录 前言 1. 使用Docker本地部署Drawio 2. 安装cpolar内网穿透工具 3. 配置Draw.io公网访问地址 4. 公网远程访问Draw.io 前言 提到流程图&#xff0c;大家第一时间可能会想到Visio&#xff0c;不可否认&#xff0c;VIsio确实是功能强大&#xff0c;但是软件为收费&…