C++进阶：map与set简单自实现

目录

  • 1. map与set封装红黑树的方式
    • 1.1 大概实现思路
    • 1.2 红黑树模板抽象
    • 1.3 红黑树的迭代器
  • 2. 红黑树模板的实现
    • 2.1 结点结构的定义
    • 2.2 红黑树迭代器的实现
      • 2.2.1 迭代器的结构
      • 2.2.2 迭代器的方法实现
    • 2.3 树结构的定义
    • 2.4 红黑树接口实现
      • 2.4.1 插入
      • 2.4.2 查找
      • 2.4.3 迭代器相关
  • 3. map与set的自实现
    • 3.1 set封装
    • 3.2 map封装

1. map与set封装红黑树的方式

1.1 大概实现思路

  1. STL库中，实现的map与set其底层都为红黑树这种数据结构，在前面的学习中，我们已经简单模拟实现了红黑树。
  2. 因此，对于map与set的实现无需再去从零开始一一构建，而是可以采用类似于栈与队列这两个容器适配器的形式，直接将红黑树进行封装，调用其的各种方法接口间接实现。

1.2 红黑树模板抽象

  1. 虽然map与set的底层数据结构都为红黑树，但是，它们也并不是完全相同，map中存储的数据结点为KV类型，而set中存储的数据结点为K类型，所以，两者在接口与使用上也有所不同。
  2. 可仅仅因此不大的差别就再写一份高度类同的红黑树代码，就不免冗余性过高，由此，我们仿照库中实现的类似方式，将红黑树抽象为模板，通过模板参数来调整细节的方式，来同时适配map与set的需求。
//红黑树模板参数
template<class K, class T, class KeyOfT>
//参数K：set与map的key值类型，K参数的存在是必要的，否则无法进行此类型函数参数的声明
//参数T：set中也为key值类型，而map中为pair<K, V>类型
//参数KeyOfT：仿函数类型，从T类型结点中提取出key值，进行查找，插入等操作必须获知与比对key值

1.3 红黑树的迭代器

  1. 当调用库中的map与set容器时，我们使用相应迭代器遍历其中存储数据，得到的是一串排序好的有序数据。
  2. 因为map与set的底层本质上为一棵搜索二叉树，这种遍历后得到的数据特点，我们不难知道，迭代器底层实则是在由整颗树最左侧结点做中序遍历，那么，其底层的逻辑究竟应该怎么去实现呢？

2. 红黑树模板的实现

2.1 结点结构的定义

//结点结构
enum colour
{
	Red,
	Black
};

template<class K, class T>
struct RBTreeNode
{
	RBTreeNode<K, T>* _left;
	RBTreeNode<K, T>* _right;
	RBTreeNode<K, T>* _parent;
	T _kv;
	colour _col;

	RBTreeNode(const T& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(Red)
	{}
};

2.2 红黑树迭代器的实现

2.2.1 迭代器的结构

//定义一个迭代器模板，适配出普通迭代器与const迭代器
template<class K, class T, class Ref, class Ptr>
class RBTree_iterator
{
	typedef RBTreeNode<K, T> RBTNode;
public:
	//构造
	RBTree_iterator(RBTNode* node)
		:_node(node)
	{}
	
	//拷贝构造
	RBTree_iterator(const RBTree_iterator& it)
	{
		_node = it._node;
	}

	//后置++，左根右
	RBTree_iterator operator++(int);
	
	//后置--，右根左
	RBTree_iterator operator--(int);

	//const T&
	Ref operator*();

	//const T*
	Ptr operator->();

	//指向结点相同
	bool operator==(RBTree_iterator it);

	bool operator!=(RBTree_iterator it);

private:
	RBTNode* _node;
};

2.2.2 迭代器的方法实现

  1. 杂项
//const T&
Ref operator*()
{
	return _node->_kv;
}

//const T*
Ptr operator->()
{
	return &_node->_kv;
}

//指向结点相同
bool operator==(RBTree_iterator it)
{
	return _node == it._node;
}

bool operator!=(RBTree_iterator it)
{
	return _node != it._node;
}
  1. 后置++与–
    在这里插入图片描述
//先使用，再++
//operator++，左根右
RBTree_iterator operator++(int)
{
	RBTree_iterator cp(*this);

	//左根右
	if (_node->_right)
	{
		//向左找
		RBTNode* SubLeft = _node->_right;
		while (SubLeft->_left)
		{
			SubLeft = SubLeft->_left;
		}

		_node = SubLeft;
	}
	else
	{
		RBTNode* cur = _node;
		RBTNode* parent = cur->_parent;
		if (cur == parent->_left)
		{
			_node = parent;
		}
		else
		{
			//一层一层向上找，空结点检测
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_parent;
			}

			_node = parent;
		}
	}

	return cp;
}

//operator--，右根左
RBTreeNode_iterator operator--(int)
{
	RBTree_iterator cp(*this);

	//右根左
	if (_node->_left)
	{
		//向右找
		RBTNode* SubRight = _node->_left;
		while (SubRight->_right)
		{
			SubRight = SubRight->_right;
		}

		_node = SubRight;
	}
	else
	{
		RBTNode* cur = _node;
		RBTNode* parent = _node->_parent;
		while (parent && cur == parent->_left)
		{
			cur = parent;
			parent = cur->_parent;
		}

		_node = parent;//处理逻辑同时符合两种情况
	}

	return cp;
}

2.3 树结构的定义

//树结构
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<K, T> RBTNode;
public:
	//查找
	bool Find(const K& key);

	//插入
	pair<iterator, bool> Insert(const T& kv);
	
private:
	RBTNode* _root = nullptr;
	KeyOfT con;
}

2.4 红黑树接口实现

2.4.1 插入

//插入
pair<iterator, bool> Insert(const T& kv)
{
	//找到插入位置
	RBTNode* cur = _root;
	RBTNode* parent = nullptr;
	while (cur)
	{
		if (con(kv) < con(cur->_kv))
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (con(kv) > con(cur->_kv))
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			//有相同值，插入失败
			//return false;
			return make_pair(iterator(cur), false);
		}
	}

	//插入
	RBTNode* newnode = new RBTNode(kv);
	cur = newnode;
	if (_root == nullptr)//根结点
	{
		_root = cur;
		_root->_col = Black;
		//return true;
		return make_pair(iterator(cur), true);
	}
	else
	{
		if (con(kv) < con(parent->_kv))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
	}

	//判断与调整
	while (parent)
	{
		//父亲结点为黑色
		if (parent->_col == Black)
		{
			break;
		}
		else//父结点为红色
		{
			RBTNode* grandparent = parent->_parent;
			RBTNode* uncle = grandparent->_left;
			if (parent == grandparent->_left)
			{
				uncle = grandparent->_right;
			}

			//叔叔结点存在且为红色
			if (uncle && uncle->_col == Red)
			{
				parent->_col = uncle->_col = Black;
				grandparent->_col = Red;
				cur = grandparent;
				//注，父节点存放变量也需重置
				parent = cur->_parent;
			}
			else//叔叔结点为黑色/不存在
			{
				if (parent == grandparent->_left)//左外高
				{
					if (cur == parent->_left)//右单旋
					{
						//      g
						//   p      u
						//c
						RotateR(grandparent);
						parent->_col = Black;
						grandparent->_col = Red;
					}
					else//左右双旋
					{
						//      g
						//   p      u
						//     c
						RotateLR(grandparent);
						cur->_col = Black;
						grandparent->_col = Red;
					}
				}
				else//右外高
				{
					if (cur == parent->_right)//左单旋
					{
						//   g
						//u      p
						//          c
						RotateL(grandparent);
						parent->_col = Black;
						grandparent->_col = Red;
					}
					else//右左双旋
					{
						//   g
						//u      p
						//     c
						RotateRL(grandparent);
						cur->_col = Black;
						grandparent->_col = Red;
					}
				}

				break;
			}
		}
	}

	_root->_col = Black;

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

2.4.2 查找

//查找
bool Find(K key)
{
	RBTNode* cur = _root;
	while (cur)
	{
		if (key < con(cur->_kv))
		{
			cur = cur->_left;
		}
		else if (key > con(cur->_kv))
		{
			cur = cur->_right;
		}
		else
		{
			return true;
		}
	}

	return false;
}

2.4.3 迭代器相关

typedef RBTree_iterator<K, T, T&, T*> iterator;
typedef RBTree_iterator<K, T, const T&, const T*> const_iterator;

iterator begin()
{
	RBTNode* cur = _root;
	while (cur->_left)
	{
		cur = cur->_left;
	}

	return cur;
}

iterator end()
{
	return nullptr;
}

const iterator cbegin() const
{
	RBTNode* cur = _root;
	while (cur->_left)
	{
		cur = cur->_left;
	}

	return cur;
}

const iterator cend() const
{
	return nullptr;
}

3. map与set的自实现

3.1 set封装

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

	typedef RBTree_iterator<K, K, K&, K*> iterator;
	typedef RBTree_iterator<K, K, const K&, const K*> const_iterator;
public:
	bool Find(K key)
	{
		return tree.Find(key);
	}

	pair<iterator, bool> Insert(K key)
	{
		return tree.Insert(key);
	}

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

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

	const_iterator cbegin() const
	{
		return tree.cbegin();
	}

	const_iterator cend() const
	{
		return tree.cend();
	}

	void InOrder()
	{
		tree.InOrder();
	}

private:
	RBTree<K, K, KeyOfT> tree;
};

3.2 map封装

template<class K, class V>
class mymap
{
	struct KeyOfT
	{
		K operator()(const pair<const K, V> kv)
		{
			return kv.first;
		}
	};
	typedef RBTree_iterator<K, pair<const K, V>, pair<const K, V>&, pair<const K, V>*> iterator;
	typedef RBTree_iterator<K, pair<const K, V>, const pair<const K, V>&, const pair<const K, V>*> const_iterator;
public:
	bool Find(K key)
	{
		return tree.Find(key);
	}

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

	//迭代器
	iterator begin()
	{
		return tree.begin();
	}

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

	const_iterator cbegin() const
	{
		return tree.cbegin();
	}

	const_iterator cend() const
	{
		return tree.cend();
	}

	V& operator[](const K key)
	{
		pair<iterator, bool> ret = Insert(make_pair(key, V()));

		return ret.first->second;
	}

private:
	RBTree<K, pair<const K, V>, KeyOfT> tree;
};

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

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

相关文章

HTML4（二）

HTML4（二）

文章目录 1 开发者文档2 基本标签2.1 排版标签2.2 语义化标签2.3 行内元素与块级元素2.4 文本标签2.5 常用标签补充 3 图片标签4 超链接标签4.1 跳转页面4.2 跳转文件4.3 跳转锚点4.4 唤起指定应用 5 列表5.1 有序列表5.2 无序列表5.3 自定义列表 6 表格6.1 基本结构6.2 表格标…
阅读更多...
企业计算机服务器中了rmallox勒索病毒怎么破解，rmallox勒索病毒解密工具步骤

企业计算机服务器中了rmallox勒索病毒怎么破解，rmallox勒索病毒解密工具步骤

科技技术的发展&#xff0c;为企业的生产运营注入了新的活力&#xff0c;越来越多的企业利用网络走向了数字化办公模式&#xff0c;网络也极大地方便了企业的生产运营&#xff0c;大大提高了企业的生产效率&#xff0c;加快了企业发展的步伐。但是网络数据安全问题一直是企业关…
阅读更多...
基于大语言模型的Agent的探索与实践

基于大语言模型的Agent的探索与实践

AI代理是人工智能领域的核心概念之一&#xff0c;它指的是能够在环境中感知、做出决策并采取行动的计算实体。代理可以是简单的&#xff0c;如自动化的网页爬虫&#xff0c;也可以是复杂的&#xff0c;如能够进行战略规划和学习的自主机器人。 AI代理的概念最早源于哲学探讨&am…
阅读更多...
ssrf漏洞学习——基础知识

ssrf漏洞学习——基础知识

一、SSRF是什么&#xff1f; SSRF(Server-Side Request Forgery:服务器端请求伪造) 是一种由攻击者构造形成由服务端发起请求的一个安全漏洞。 一般情况下&#xff0c;SSRF攻击的目标是从外网无法访问的内部系统。&#xff08;正是因为它是由服务端发起的&#xff0c;所以它能…
阅读更多...
大数据手册(Spark)--Spark 简介

大数据手册(Spark)--Spark 简介

Spark 简介 Apache Spark 是一种用于大数据工作负载的分布式开源处理系统。它使用内存中缓存和优化的查询执行方式&#xff0c;可针对任何规模的数据进行快速分析查询。Apache Spark 提供了简明、一致的 Java、Scala、Python 和 R 应用程序编程接口 (API)。 Apache Spark 是专…
阅读更多...
Rust Postgres实例

Rust Postgres实例

Rust Postgres介绍 Rust Postgres是一个纯Rust实现的PostgreSQL客户端库&#xff0c;无需依赖任何外部二进制文件2。这意味着它可以轻松集成到你的Rust项目中&#xff0c;提供对PostgreSQL的支持。 特点 高性能&#xff1a;Rust Postgres提供了高性能的数据库交互功能&#…
阅读更多...
DI-engine强化学习入门（九）环境包裹器（Env Wrapper）

DI-engine强化学习入门（九）环境包裹器（Env Wrapper）

在强化学习中&#xff0c;环境&#xff08;Environment&#xff09;是智能体&#xff08;Agent&#xff09;进行学习和互动的场所&#xff0c;它定义了状态空间、动作空间以及奖励机制。Env Wrapper&#xff08;环境包装器&#xff09;提供了一种方便的机制来增强或修改原始环境…
阅读更多...
揭秘新时代的内容创作：一键生成的AI黑科技

揭秘新时代的内容创作：一键生成的AI黑科技

在数字媒体的浪潮下&#xff0c;内容创作已成为连接人与信息的重要桥梁。然而&#xff0c;头条、公众号等平台上的爆文创作&#xff0c;对很多内容创作者来说却是一项挑战。“从选题到找素材&#xff0c;再到成文&#xff0c;”这个过程不仅耗时至少1到2个小时&#xff0c;而且…
阅读更多...
【go项目01_学习记录08】

【go项目01_学习记录08】

学习记录 1 模板文件1.1 articlesStoreHandler() 使用模板文件1.2 统一模板 1 模板文件 重构 articlesCreateHandler() 和 articlesStoreHandler() 函数&#xff0c;将 HTML 抽离并放置于独立的模板文件中。 1.1 articlesStoreHandler() 使用模板文件 . . . func articlesSt…
阅读更多...
产品评测：SmartX 与 Nutanix 超融合在数据库场景下的性能表现

产品评测：SmartX 与 Nutanix 超融合在数据库场景下的性能表现

重点内容 SmartX 与 Nutanix 超融合分布式存储设计差异如何影响数据库性能表现。重点测试结论&#xff1a;数据库场景下&#xff0c;SmartX 超融合基于单卷部署的性能&#xff0c;依旧优于 Nutanix 超融合基于多卷部署最佳配置的性能。更多 SmartX、VMware、Nutanix 超融合技术…
阅读更多...
高防护皮带机巡检机器人：适应恶劣环境的智能助手

高防护皮带机巡检机器人：适应恶劣环境的智能助手

在众多工业领域中&#xff0c;皮带机作为一种重要的物料输送设备&#xff0c;广泛应用于发电厂、煤栈等场所。然而&#xff0c;长期以来&#xff0c;皮带机的巡检工作一直依赖人工&#xff0c;存在着劳动强度大、检测效率低、安全性差等问题。为了解决这些痛点&#xff0c;皮带…
阅读更多...
Day05-JavaWeb开发-请求响应(postman工具/参数/案例)分层解耦(三层架构/IOC-DI引入)

Day05-JavaWeb开发-请求响应(postman工具/参数/案例)分层解耦(三层架构/IOC-DI引入)

1. 请求响应 1.1 概述 1.2 请求-postman工具 1.3 请求-简单参数&实体参数 1.3.1 简单参数 1.3.2 实体参数 1.4 请求-数组集合参数 1.5 请求-日期参数&json参数 1.6 请求-路径参数 1.7 响应-ResponseBody 1.8 响应-案例 2. 分层解耦 2.1 三层架构 2.2 分层解耦(IOC-D…
阅读更多...
GitHub Actions 手动触发方式

GitHub Actions 手动触发方式

目录 前言 Star Webhook 手动触发按钮 前言 GitHub Actions 是 Microsoft 收购 GitHub 后推荐的一款 CI/​CD 工具早期可能是处于初级开发阶段&#xff0c;它的功能非常原生&#xff0c;甚至没有直接提供一个手动触发按钮一般的触发方式为代码变动&#xff08;push 、pull…
阅读更多...
使用Processing和PixelFlow库创建交互式流体太极动画

使用Processing和PixelFlow库创建交互式流体太极动画

使用Processing和PixelFlow库创建交互式流体太极动画 引言准备工作效果展示代码结构代码解析第一部分&#xff1a;导入库和设置基本参数第二部分&#xff1a;流体类定义MyFluidDataConfig 类详解MyFluidData 类详解my_update 方法详解流体类定义完整代码 第三部分&#xff1a;太…
阅读更多...
无监督式学习

无监督式学习

1.是什么&#xff1f; 无监督式学习与监督式学习**最大的区别就是&#xff1a;**没有事先给定的训练实例&#xff0c;它是自动对输入的示例进行分类或者分群&#xff1b; 优点&#xff1a;不需要标签数据&#xff0c;极大程度上扩大了我们的数据样本&#xff0c;其次不受监督信…
阅读更多...
部署 Sentinel 控制台：实现流量管理和监控

部署 Sentinel 控制台：实现流量管理和监控

序言 Sentinel 是阿里巴巴开源的一款流量防护与监控平台&#xff0c;它可以帮助开发者有效地管理微服务的流量&#xff0c;实现流量控制、熔断降级、系统负载保护等功能。本文将介绍如何在项目中部署和配置 Sentinel 控制台&#xff0c;实现微服务的流量防护和监控。 一、Sen…
阅读更多...
WEB基础--单元测试与三层架构

WEB基础--单元测试与三层架构

单元测试 为什么要进行单元测试 减少创建类&#xff0c;我们希望在一个类中&#xff0c;并且测试时不需要改代码&#xff0c;那么我们就要用到junit单元测试 常见测试分类 黑盒测试 黑盒测试也叫功能测试&#xff0c;主要关注软件每个功能是否实现&#xff0c;并不关注软件代…
阅读更多...
【websocket-客户端可视化工具】

【websocket-客户端可视化工具】

postman 新版postman (版本v11以上) &#xff0c;除了http协议&#xff0c;还支持了Websocket&#xff0c;MQTT&#xff0c;gRPC等多种连接协议&#xff0c;可以作为多种协议的客户端&#xff0c;使用起来非常方便。 使用 服务端代码 这里以websocket协议举例&#xff0c;代…
阅读更多...
【Linux】网络接口绑定和组合的操作实例

【Linux】网络接口绑定和组合的操作实例

网络接口绑定和组合的操作实例 &#xff08;一&#xff09;网卡1. 增2. 查3. 激活——设置网络接口 &#xff08;二&#xff09;网络接口绑定1. 概述2. 实验操作3. 删除绑定 &#xff08;三&#xff09;网络接口组合1. 概述2. 实验操作 &#xff08;一&#xff09;网卡 1. 增 …
阅读更多...
分割模型Maskformer系列

分割模型Maskformer系列

maskformer&#xff1a;Per-Pixel Classification is Not All You Need for Semantic Segmentation 论文地址&#xff1a;https://arxiv.org/pdf/2107.06278 1.概述 传统的语义分割方法通常采用逐像素分类&#xff08;per-pixel classification&#xff09;&#xff0c;而实…
阅读更多...
最新文章

Copyright @ 2022~2023