【C++练级之路】【Lv.17】【STL】set类和map类的模拟实现



快乐的流畅：个人主页


个人专栏：《C语言》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

文章目录

  • 引言
  • 一、红黑树（改造版）
    • 1.1 结点
    • 1.2 迭代器
      • 1.2.1 operator++
      • 1.2.2 operator- -
    • 1.3 本体
      • 1.3.1 begin和end
      • 1.3.2 Find
      • 1.3.3 Insert
  • 二、set
    • 2.1 成员变量与仿函数
    • 2.2 begin和end
    • 2.3 find
    • 2.4 insert
  • 三、map
    • 3.1 成员变量与仿函数
    • 3.2 begin和end
    • 3.3 find
    • 3.4 insert
    • 3.5 operator[ ]

引言

STL库中的set类和map类，其底层原理都是通过红黑树来实现的。尽管set和map可以各自实现一棵红黑树，但是为了提高代码的复用率，STL库中将红黑树进行了一定的改造，实现以相同的底层实现不同的容器。

一、红黑树（改造版）

1.1 结点

enum Color
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Color _col;

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

细节：

  • 将数据类型改为T，因为要同时适用set（存储键值）和map（存储键值对）

1.2 迭代器

改造后的红黑树，最重要的功能之一就是支持双向迭代器，以最左结点为首，以最右结点为尾。

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

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

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

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

	Ptr operator->()
	{
		return &(operator*());
	}

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

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

细节：

  1. 一些基本的迭代器范式操作已经给出，重点的++与- -操作后面详细实现
  2. 迭代器的拷贝构造函数有两个用途：
    • 以普通迭代器拷贝出普通迭代器（普通迭代器调用时）
    • 以普通迭代器拷贝出const迭代器（const迭代器调用时）

1.2.1 operator++

Self operator++()
{
	if (_node->_right)//右不为空，找右子树的最左结点
	{
		Node* subLeft = _node->_right;
		while (subLeft->_left)
		{
			subLeft = subLeft->_left;
		}
		_node = subLeft;
	}
	else//右为空，向上找孩子是父亲左的那个父亲
	{
		Node* parent = _node->_parent;
		Node* cur = _node;
		while (parent && parent->_right == cur)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

Self operator++(int)
{
	Node* tmp = _node;
	++*this;
	return tmp;
}

细节：

  1. 前置++的思路：
    • 右不为空，找右子树的最左结点
    • 右为空，向上找孩子是父亲左的那个父亲
  2. 后置++：复用前置++，返回临时对象

1.2.2 operator- -

Self operator--()
{
	if (_node->_left)//左不为空，找左子树的最右结点
	{
		Node* subRight = _node->_left;
		while (subRight->_right)
		{
			subRight = subRight->_right;
		}
		_node = subRight;
	}
	else//左为空，向上找孩子是父亲右的那个父亲
	{
		Node* parent = _node->_parent;
		Node* cur = _node;
		while (parent && parent->_left == cur)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

Self operator--(int)
{
	Node* tmp = _node;
	--*this;
	return tmp;
}

细节：

  1. 前置- -的思路：
    • 左不为空，找左子树的最右结点
    • 左为空，向上找孩子是父亲右的那个父亲
  2. 后置- -：复用前置- -，返回临时对象

1.3 本体

template<class K, class T, class KeyOfT>
class RBTree
{
protected:
	typedef RBTreeNode<T> Node;
public:
protected:
	Node* _root = nullptr;
};

细节：

  1. 模板参数第一个为K，键值类型（比较时会用到）
  2. 模板参数第二个为T，同时适用set（存储键值）和map（存储键值对）
  3. 模板参数第三个为KeyOfT（仿函数类型），用于获取不同数据T的键值key来进行比较

1.3.1 begin和end

typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;

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

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

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

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

细节：begin返回最左节点的迭代器，end返回空迭代器

1.3.2 Find

iterator Find(const K& key)
{
	if (_root == nullptr)
	{
		return iterator(nullptr);
	}

	KeyOfT kot;
	Node* cur = _root;
	while (cur)
	{
		if (kot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else if (kot(cur->_data) > key)
		{
			cur = cur->_left;
		}
		else
		{
			return iterator(cur);
		}
	}

	return iterator(nullptr);
}

细节：

  1. 返回迭代器
  2. 运用仿函数进行键值比较

1.3.3 Insert

pair<iterator, bool> Insert(const T& data)
{
	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);
		}
	}

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

	while (parent && parent->_col == RED)
	{
		Node* grandparent = parent->_parent;
		if (grandparent->_right == parent)//uncle在左，parent在右
		{
			Node* uncle = grandparent->_left;
			if (uncle && uncle->_col == RED)//uncle为红，变色+向上调整
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;

				cur = grandparent;
				parent = cur->_parent;
			}
			else//uncle为空或为黑，变色+旋转
			{
				if (parent->_right == cur)//左单旋
				{
					RotateL(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else//右左旋
				{
					RotateR(parent);
					RotateL(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
			}
		}
		else//parent在左，uncle在右
		{
			Node* uncle = grandparent->_right;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;

				cur = grandparent;
				parent = cur->_parent;
			}
			else
			{
				if (parent->_left == cur)//右单旋
				{
					RotateR(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				else//左右旋
				{
					RotateL(parent);
					RotateR(grandparent);
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
			}
		}
	}
	_root->_col = BLACK;

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

细节：

  1. 返回pair，第一个参数为迭代器，第二个参数为布尔值（记录是否插入成功）
  2. 运用仿函数进行键值比较

二、set

2.1 成员变量与仿函数

template<class K>
class set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
protected:
	RBTree<K, K, SetKeyOfT> _t;
};

细节：

  1. set类仿函数，直接返回参数key
  2. 成员变量的第二个模板参数为K，第三个模板参数为SetKeyOfT

2.2 begin和end

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

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

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

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

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

细节：

  1. 加上typename关键字，编译器才能识别类型
  2. set中存储的键值key均不允许修改，所以其普通迭代器和const迭代器均为红黑树的const迭代器
  3. 由于set的普通迭代器也是红黑树的const迭代器，调用普通begin()时，便有从普通迭代器到const迭代器的转换，此时之前写的拷贝构造（以普通迭代器拷贝构造const迭代器）便派上用场了。

2.3 find

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

2.4 insert

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

细节：

  1. 插入参数类型为K（键值）
  2. 此时也有从普通迭代器到const迭代器的转换

三、map

3.1 成员变量与仿函数

template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
public:
protected:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

细节：

  1. map类仿函数，返回参数pair的first
  2. 成员变量的第二个模板参数为pair，第三个模板参数为MapKeyOfT

3.2 begin和end

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

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

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

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

细节：

  1. 加上typename关键字，编译器才能识别类型
  2. map同样不允许修改key，故加上const修饰，但是允许修改存储的value，所以普通和const迭代器一一对应

此时，可能有人会问，那刚刚set不允许修改key，为什么不也直接用const修饰呢？请看以下这段代码：

typedef RBTreeIterator<T, const T&, const T*> const_iterator;

如果变成第二个模板参数T传入const K，那么就会形成两个连续的const，这是不被允许的。所以才想了其他方法来补救。

3.3 find

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

3.4 insert

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

细节：插入参数类型为pair（键值对）

3.5 operator[ ]

map最好用的重载运算符[ ]，我们肯定也要实现，平常插入和修改使用[ ]更加方便。

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

细节：

  1. 插入成功便是插入，插入失败便是查找+修改
  2. 返回value的引用，可以直接插入或修改

真诚点赞，手有余香

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

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

相关文章

【LeetCode热题100】105. 从前序与中序遍历序列构造二叉树（二叉树）

【LeetCode热题100】105. 从前序与中序遍历序列构造二叉树（二叉树）

一.题目要求 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 二.题目难度 中等 三.输入样例 示例 1: 输入: preorder [3,9,20,15,7], inorder…
阅读更多...
考研数学｜第一轮刚完，刷1800惨不忍睹怎么办？

考研数学｜第一轮刚完，刷1800惨不忍睹怎么办？

1800题惨不忍睹&#xff0c;我有办法救你 1800题算是所有习题册里面难度比较低的题集了&#xff0c;特别是1800题基础阶段的题目&#xff0c;我一般推荐基础不好的同学在基础阶段做这个。如果1800题都觉得很难的话&#xff0c;那么其他题集就更不用说了 刷1800题错的很多&…
阅读更多...
[CISCN2019 华北赛区 Day2 Web1]Hack World

[CISCN2019 华北赛区 Day2 Web1]Hack World

本题首先考察的是sql注入 拿过滤字符集先跑一遍 发现以上字符集都被过滤了 尝试id1 id11 尝试id(1)(2) 这里就已经给出了个思路我们可以尝试盲注去打 id(select(ascii(mid(flag,1,1))102)from(flag)) 这里表跟列已经给了我们了&#xff0c;所以我们可以写脚本了 import reque…
阅读更多...
STM32常用的开发工具有哪些

STM32常用的开发工具有哪些

大家好&#xff0c;今天给大家介绍STM32常用的开发工具有哪些&#xff0c;文章末尾附有分享大家一个资料包&#xff0c;差不多150多G。里面学习内容、面经、项目都比较新也比较全&#xff01;可进群免费领取。 STM32常用的开发工具主要包括以下几类&#xff1a; 集成开发环境&…
阅读更多...
C++枚举类型

C++枚举类型

枚举类型 枚举类型使我们可以将一组整型常量组织在一起。 和类一样&#xff0c;每个枚举类型定义了一种新的类型。 枚举属于字面值常量类型。 C包含两种枚举&#xff1a;限定作用域的和不限定作用域的。 限定作用域的枚举类型 C11新标准引入了限定作用域的枚举类型。 定…
阅读更多...
阿里云实时计算Flink的产品化思考与实践【上】

阿里云实时计算Flink的产品化思考与实践【上】

摘要&#xff1a;本文整理自阿里云高级产品专家黄鹏程和阿里云技术专家陈婧敏在 FFA 2023 平台建设专场中的分享。内容主要为以下五部分&#xff1a; 阿里云实时计算 Flink 简介产品化思考产品化实践SQL 产品化思考及实践展望 该主题由黄鹏程和陈婧敏共同完成&#xff0c;前半程…
阅读更多...
插入排序、归并排序、堆排序和快速排序的稳定性分析

插入排序、归并排序、堆排序和快速排序的稳定性分析

插入排序、归并排序、堆排序和快速排序的稳定性分析 一、插入排序的稳定性二、归并排序的稳定性三、堆排序的稳定性四、快速排序的稳定性总结在计算机科学中，排序是将一组数据按照特定顺序进行排列的过程。排序算法的效率和稳定性是评价其优劣的两个重要指标。稳定性指的是在排…
阅读更多...
【地图构建(1)】占用栅格地图构建Occupancy grid mapping

【地图构建(1)】占用栅格地图构建Occupancy grid mapping

本文主要参考Probabilistic Robotics《概率机器人》一书。 其他参考&#xff1a; 弗莱堡大学课件 博客 含代码博客 0.引言 位姿已知的地图构建(mapping with known poses)的定义&#xff1a;已知机器人的位姿 x 1 : t x_{1:t} x1:t​和传感器的观测数据 z 1 : t z_{1:t} z1:t…
阅读更多...
云原生（六）、CICD - Jenkins快速入门

云原生（六）、CICD - Jenkins快速入门

Jenkuns快速入门 一、CICD概述 CICD是持续集成&#xff08;Continuous Integration&#xff09;和持续部署&#xff08;Continuous Deployment&#xff09;的缩写。它是软件开发中的一种流程和方法论&#xff0c;旨在通过自动化的方式频繁地将代码集成到共享存储库中&#xf…
阅读更多...
zotero+word优化管理参考文献

zotero+word优化管理参考文献

写论文&#xff0c;整理参考文献&#xff0c;管理参考文献很麻烦&#xff0c;参考文献格式罗列很麻烦&#xff0c;论文需要修改时&#xff0c;重新调整参考文献顺序很麻烦。 zoteroword可以很好的帮助解决这个问题。 Step1 zotero软件安装 默认word你已经安装好了 step2 安…
阅读更多...
线程局部存储（TLS）

线程局部存储（TLS）

线程局部存储&#xff08;Thread Local Storage&#xff0c;TLS&#xff09;&#xff0c;是一种变量的存储方法&#xff0c;这个变量在它所在的线程内是全局可访问的&#xff0c;但是不能被其他线程访问到&#xff0c;这样就保持了数据的线程独立性。而熟知的全局变量&#xff…
阅读更多...
班级综合测评管理系统的设计与实现|Springboot+ Mysql+Java+ B/S结构(可运行源码+数据库+设计文档)

班级综合测评管理系统的设计与实现|Springboot+ Mysql+Java+ B/S结构(可运行源码+数据库+设计文档)

本项目包含可运行源码数据库LW&#xff0c;文末可获取本项目的所有资料。 推荐阅读100套最新项目持续更新中..... 2024年计算机毕业论文&#xff08;设计&#xff09;学生选题参考合集推荐收藏&#xff08;包含Springboot、jsp、ssmvue等技术项目合集&#xff09; 目录 1. …
阅读更多...
二十 超级数据查看器 讲解稿 功能概述

二十 超级数据查看器 讲解稿 功能概述

二十 超级数据查看器 讲解稿 功能概述 ​ ​​点击此处 以新页面 打开B站 播放当前教学视频 点击访问app下载页面 豌豆荚 下载地址​ ​ 讲解稿 ​ 界面启动 ​ 导入 ​ 选excel文件 导入 ​ 原来的excel文件 ​ 导入进本地数据库sqlite ​ 导入成功 ​ 列…
阅读更多...
MySQL---事务

MySQL---事务

目录 一、事务简介 二、事务操作 1.未控制事务 2.事务控制一 3.控制事务二 三、事务的四大特性 四、并发事务问题 五、事务隔离级别 一、事务简介 事务 是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;事务会把所有的操作作为一个整体一起向系统提交或…
阅读更多...
喜讯！聚铭网络荣获《日志分类方法及系统》发明专利

喜讯！聚铭网络荣获《日志分类方法及系统》发明专利

近日&#xff0c;聚铭网络又喜获一项殊荣&#xff0c;其申报的《日志分类方法及系统》发明专利成功获得国家知识产权局的授权&#xff0c;正式荣获国家发明专利证书。 在信息化时代&#xff0c;网络安全问题日益凸显&#xff0c;日志分析作为保障网络安全的重要手段&#xff…
阅读更多...
【嵌入式——C语言】VScode编写C程序、交叉编译

【嵌入式——C语言】VScode编写C程序、交叉编译

【嵌入式——C语言】VScode编写C程序、交叉编译 第一步第二步第三步第四步第五步第六步第七步第八步 第一步 下载Visual Studio Code下载地址 然后直接安装就可以了。 第二步 前提是你的电脑上安装了WSL。。。 打开vscode的扩展&#xff0c;输入WSL进行安装 安装完之后在窗…
阅读更多...
【深度学习】图片预处理，分辨出模糊图片

【深度学习】图片预处理，分辨出模糊图片

ref:https://pyimagesearch.com/2015/09/07/blur-detection-with-opencv/ 论文 ref:https://www.cse.cuhk.edu.hk/leojia/all_final_papers/blur_detect_cvpr08.pdf 遇到模糊的图片&#xff0c;还要处理一下&#xff0c;把它挑出来&#xff0c;要么修复&#xff0c;要么弃用。否…
阅读更多...
vue组件如何使用？

vue组件如何使用？

今天我随便试两个组件 第一个轮播图 在minn.js 引入 import { createApp } from vue; import { Swipe, SwipeItem } from vant; const app createApp(); app.use(Swipe); app.use(SwipeItem); <van-swipe class"my-swipe" :autoplay"3000" indica…
阅读更多...
uniapp 微信小程序 canvas 手写板文字重复倾斜水印

uniapp 微信小程序 canvas 手写板文字重复倾斜水印

核心逻辑 先将坐标系中心点通过ctx.translate(canvasw / 2, canvash / 2) 平移到canvas 中心&#xff0c;再旋转设置水印 假如不 translate 直接旋转&#xff0c;则此时的旋转中心为左上角原点&#xff0c;此时旋转示意如图所示 当translate到中心点之后再旋转&#xff0c;此…
阅读更多...
逐步学习Go-协程goroutine

逐步学习Go-协程goroutine

参考&#xff1a;逐步学习Go-协程goroutine – FOF编程网 什么是线程&#xff1f; 简单来说线程就是现代操作系统使用CPU的基本单元。线程基本包括了线程ID&#xff0c;程序计数器&#xff0c;寄存器和线程栈。线程共享进程的代码区&#xff0c;数据区和操作系统的资源。 线…
阅读更多...
最新文章

Copyright @ 2022~2023