map\set封装

目录

  • 1. set和map的底层结构
    • 1.1 红黑树
    • 1.2 set
    • 1.3 map
  • 2. 模拟实现
    • 2.1 红黑树
    • 2.1 map和set以及仿函数
    • 2.3 迭代器
      • 2.3.1 const迭代器
    • 2.3 set和map封装

1. set和map的底层结构

1.1 红黑树

这两个容器底层都是对红黑树的封装，因此需要先看一下红黑树结构部分的底层源码：

//树结点的定义：
struct __rb_tree_node_base
{
  typedef __rb_tree_color_type color_type;
  typedef __rb_tree_node_base* base_ptr;

  color_type color; 
  base_ptr parent;
  base_ptr left;
  base_ptr right;
};
//子类继承
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
  typedef __rb_tree_node<Value>* link_type;
  //存储有效数据
  Value value_field;
};

//红黑树部分成员
template <class Key, class Value, class KeyOfValue, class Compare,
          class Alloc = alloc>
class rb_tree {
protected:
  typedef __rb_tree_node<Value> rb_tree_node;
public:
  typedef Key key_type;
  typedef Value value_type;
  typedef rb_tree_node* link_type;
protected:
  size_type node_count; // keeps track of size of tree
  link_type header;  
  Compare key_compare;
 }

可以发现红黑树的结点中存储的元素类型只与第二个模板参数Value有关，对于set而言value是Key，对于map而言value是pair<const K, T>类型。

Key也需要传递，树中有些接口的实现需要用到，比如find等。

1.2 set

set底层结构的部分构成：

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
  // typedefs:
  typedef Key key_type;
  typedef Key value_type;
  typedef Compare key_compare;
  typedef Compare value_compare;
private:
  ///红黑树
  typedef rb_tree<key_type, value_type, 
                  identity<value_type>, key_compare, Alloc> rep_type;
  rep_type t;  // red-black tree representing set
 }

set是K模型，因此key_type是Key，value_type也是Key，实例化后树中要存储的元素类型也是Key类型。

1.3 map

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
  typedef Key key_type;
  typedef T data_type;
  typedef T mapped_type;
  typedef pair<const Key, T> value_type;
  typedef Compare key_compare;

private:
  typedef rb_tree<key_type, value_type, 
                  select1st<value_type>, key_compare, Alloc> rep_type;
  rep_type t;  // red-black tree representing map
}

对于map而言，key_type是Key，而value_type则是一个pair<const Key, T>类型，因此实例化后树中的结点存储的就是pair类型。

2. 模拟实现

2.1 红黑树

由于map和set用到的是同一个类模板，因此红黑树类模板的设计要支持泛型。

树结点的定义：

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

对于set而言，T就是key，而对于map而言T为pair<const K, T>类型。

树的定义：

template<class K, class T, class KeyOfT>
//第三个模板参数为仿函数
//作用是取出date中的key来进行比较
//插入元素时要按照key的关键码进行比较选择合适的插入位置
//但是插入的是data，对于map来说data无法按照预期进行比较
//因为data的类型T为pair，需要取出data中的key
//而对于set而言，可以用data比，因为data的类型T就是key
//不过为了统一处理，都通过仿函数来取出key
class RBTree {
	typedef RBTreeNode<T> Node;
public:
	typedef Iterator<T> iterator;
public:
	pair<iterator, bool> insert(const T& data) {
		if (!_root) {
			_root = new Node(data);
			_root->_col = BLACK;
			return pair<iterator, bool>(_root, true);
		}
		
		Node* cur = _root;
		Node* parent = nullptr;
		//定义仿函数对象
		KeyOfT kot;
		while (cur) {
			//取出data中的key进行比较
			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 pair<iterator, bool>(cur, false);
			}
		}
		cur = new Node(data);
		pair<iterator, bool> ret(cur, true);
		if (kot(parent->_data) < kot(data)) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		cur->_parent = parent;

		//parent为红需要一直往上调整
		while (parent && parent->_col == RED) {
			Node* grandpa = parent->_parent;
			if (grandpa->_left == parent) {
				Node* uncle = grandpa->_right;
				//叔叔存在且为红
				if (uncle && uncle->_col == RED) {
					//把父亲和叔叔染黑
					//爷爷染红继续往上调整
					parent->_col = uncle->_col = BLACK;
					grandpa->_col = RED;

					cur = grandpa;
					parent = cur->_parent;
				}
				//叔叔不存在或者存在且为黑
				else {
					//单纯的一边高(直线)单旋
					if (cur == parent->_left) {
						rotateRight(grandpa);
						parent->_col = BLACK;
						cur->_col = grandpa->_col = RED;
					}
					//折线情况需要双旋
					else {
						rotateLeft(parent);
						rotateRight(grandpa);
						cur->_col = BLACK;
						parent->_col = grandpa->_col = RED;
					}
					break;
				}
			}
			//同样的逻辑
			else {
				Node* uncle = grandpa->_left;
				if (uncle && uncle->_col == RED) {
					parent->_col = uncle->_col = BLACK;
					grandpa->_col = RED;
					
					cur = grandpa;
					parent = cur->_parent;
				}
				else {
					if (parent->_right == cur) {
						rotateLeft(grandpa);
						grandpa->_col = cur->_col = RED;
						parent->_col = BLACK;
					}
					else {
						rotateRight(parent);
						rotateLeft(grandpa);
						parent->_col = grandpa->_col = RED;
						cur->_col = BLACK;
					}
					break;
				}		 
			}
		}
		_root->_col = BLACK;
		return ret;
	}	 
private:
	Node* _root = nullptr;
};

2.1 map和set以及仿函数

set：

template<class K>
class set {
	struct SetKeyOfT {
		const K& operator()(const K& key) {
			return key;
		}
	};
	//显式传递仿函数
	typedef RBTree<K, const K, SetKeyOfT>	rbt;
private:
	rbt t;
};

map：

template<class K, class T>
class map {
	//内部类
	struct MapKeyOfT {
		const K& operator()(const pair<const K, T>& key) {
			return key.first;
		}
	};
	typedef RBTree<K, pair<const K, T>, MapKeyOfT>	rbt;
private:
	rbt t;
};

仿函数的作用在于统一取出结点中的Key进行比较。

2.3 迭代器

map和set通过迭代器进行遍历时，本质是对这颗树进行中序遍历，得到的结果是有序的，因此迭代器中最重要的功能是++和–的实现逻辑，对于++，本质是中序遍历时的下一个位置，具体可分为两步：

  1. 右子树不为空时，需要去找到右子树的最小结点也就是最左节点。
  2. 右子树为空时，说明当前子树遍历完毕，需要去找到一个根结点(可能是整棵树的根也可能是某颗子树的根)，该根结点的左子树是我或者是我的某个祖先结点，因为中序遍历的顺序是：左-根-右
self& operator++() {
	//右子树不为空，去找右树的最左结点
	if (_it->_right) {
		Node* leftMin = _it->_right;
		while (leftMin && leftMin->_left) {
			leftMin = leftMin->_left;
		}
		_it = leftMin;
	}
	//为空
	//去找孩子是父亲的左的那个根结点
	else {
		Node* cur = _it;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right) {
			cur = cur->_parent;
			parent = parent->_parent;
		} 
		_it = parent;
	}
	return *this;
}

2.3.1 const迭代器

由于set中的元素不允许修改，所以set的普通和const迭代器都是树中的const迭代器：
在这里插入图片描述
在这里插入图片描述
但是这种设计会出现一个问题：
在这里插入图片描述

会导致类型不匹配，这是因为树的insert返回值pair中的迭代器类型是普通迭代器，而set中的迭代器的类型是const类型，普通迭代器无法构造const迭代器，所以会报错，解决方法为：设计一个支持普通迭代器转化为cons迭代器的构造函数。
在这里插入图片描述
对于实例化const迭代器类型的模板类而言，该函数是构造函数，而对于实例化普通迭代器类型的模板类而言，该函数是拷贝构造，通过该函数即可解决上述问题。

map的普通和const迭代器的设计则与其它容器是类似的，只是不管是普通还是const迭代器都无法对key进行修改，而value是否能修改则取决于迭代器的具体类型。

迭代器整体实现代码：

template <class T, class Ref, class Ptr>
struct Iterator {
	typedef Iterator<T, Ref, Ptr>			self;
	typedef Iterator<T, T&, T*>				iterator;
	typedef Iterator<T, const T&, const T*> const_iterator;

	typedef RBTreeNode<T> Node;

	Iterator(const iterator& it) :_it(it._it)
	{  }

	Iterator(Node* it) :_it(it)
	{  }

	bool operator!=(const self& s) const {
		return _it != s._it;
	}

	bool operator==(const self& s) const {
		return !(*this != s);
	}

	self& operator++() {
		if (_it->_right) {
			Node* leftMin = _it->_right;
			while (leftMin && leftMin->_left) {
				leftMin = leftMin->_left;
			}
			_it = leftMin;
		}
		else {
			Node* cur = _it;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right) {
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_it = parent;
		}
		return *this;
	}

	self& operator--() {
		if (_it->_left) {
			Node* leftMax = _it->_left;
			while (leftMax && leftMax->_right) {
				leftMax = leftMax->_right;
			}
			_it = leftMax;
		}
		else {
			Node* cur = _it;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left) {
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_it = parent;
		}
		return *this;
	}

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

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

	Node* _it;
};

2.3 set和map封装

set:

#include "RBTree.h"

namespace lzh {
	template<class K>
	class set {
		struct SetKeyOfT {
			const K& operator()(const K& key) {
				return key;
			}
		};
		typedef RBTree<K, K, SetKeyOfT>	rbt;
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

	public:
		iterator begin() const {
			return _t.begin();
		}

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

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

	private:
		rbt _t;
	};
};

map：

#include "RBTree.h"

namespace lzh {
	template<class K, class T>
	class map {
		struct MapKeyOfT {
			const K& operator()(const pair<const K, T>& key) {
				return key.first;
			}
		};
		typedef RBTree<K, pair<const K, T>, MapKeyOfT>	rbt;
	public:
		typedef  typename RBTree<K, pair<const K, T>, MapKeyOfT>::iterator		 iterator;
		typedef  typename RBTree<K, pair<const K, T>, MapKeyOfT>::const_iterator const_iterator;
	public:
		iterator begin() {
			return t.begin();
		}

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

		pair<iterator, bool> insert(const pair<const K, T>& data) {
			return t.insert(data);
		}

		T& operator[](const K& k) {
			return insert({ k, T() }).first->second;
		}
	private:
		rbt t;
	};
};

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

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

相关文章

基于免费敏捷工具Leangoo领歌的Scrum敏捷管理实践

基于免费敏捷工具Leangoo领歌的Scrum敏捷管理实践

Leangoo领歌是一款永久免费的专业的敏捷开发管理工具&#xff0c;提供端到端敏捷研发管理解决方案&#xff0c;涵盖敏捷需求管理、任务协同、进展跟踪、统计度量等。 Leangoo领歌上手快、实施成本低&#xff0c;可帮助企业快速落地敏捷&#xff0c;提质增效、缩短周期、加速创新…
阅读更多...
医学生画图ppt

医学生画图ppt

微信回复&#xff1a;素材 领取
阅读更多...
中睿天下Coremail | 2023年Q3企业邮箱安全态势观察报告

中睿天下Coremail | 2023年Q3企业邮箱安全态势观察报告

10月25日&#xff0c;北京中睿天下信息技术有限公司联合Coremail邮件安全发布《2023年第三季度企业邮箱安全性研究报告》。2023年第三季度企业邮箱安全呈现出何种态势&#xff1f;作为邮箱管理员&#xff0c;我们又该如何做好防护&#xff1f; 以下为精华版阅读&#xff0c;如需…
阅读更多...
Java日志规范总结

Java日志规范总结

打印异常错误 正确应该是&#xff1a; 或者带上入参异常 没有意义的日志 最好带上参数&#xff0c;否则不知道这条日志代表什么意义。 日志不全 这种返回值日志尽量带上全部信息&#xff0c;排查的时候&#xff0c;只用错误信息是排查不出来问题的&#xff0c;顺丰那边…
阅读更多...
【10套模拟】【3】

【10套模拟】【3】

关键字&#xff1a; 物理存储、完全二叉树、出栈入栈时间复杂度、线索二叉树
阅读更多...
数据同步工具调研选型：SeaTunnel 与 DataX 、Sqoop、Flume、Flink CDC 对比

数据同步工具调研选型：SeaTunnel 与 DataX 、Sqoop、Flume、Flink CDC 对比

产品概述 Apache SeaTunnel 是一个非常易用的超高性能分布式数据集成产品&#xff0c;支持海量数据的离线及实时同步。每天可稳定高效同步万亿级数据&#xff0c;已应用于数百家企业生产&#xff0c;也是首个由国人主导贡献到 Apache 基金会的数据集成顶级项目。 SeaTunnel 主…
阅读更多...
跨境国际快递物流API：加速全球贸易的关键

跨境国际快递物流API：加速全球贸易的关键

引言 全球贸易的蓬勃发展在今日商业中扮演着至关重要的角色。而随着全球市场的扩大和商业界的日益复杂化&#xff0c;跨境国际快递物流API正成为推动全球贸易加速发展的关键因素。 为何说跨境国际快递物流API是加速全球贸易的关键&#xff1f; 连接全球商业网络 跨境国际快…
阅读更多...
算法训练 第七周

算法训练 第七周

一、最小栈 本题要求我们实现一个最小栈数据结构&#xff0c;要求它可以实现栈的基本功能&#xff0c;并且还能使用常数时间复杂度来获取栈中的最小值。 1.辅助栈 我们可以在普通栈的基础上再添加一个维护最小值的辅助栈来实现这个数据结构&#xff0c;我们先创建一个普通的栈…
阅读更多...
【蓝桥杯选拔赛真题68】Scratch打地鼠游戏 少儿编程scratch图形化编程 蓝桥杯创意编程选拔赛真题解析

【蓝桥杯选拔赛真题68】Scratch打地鼠游戏 少儿编程scratch图形化编程 蓝桥杯创意编程选拔赛真题解析

目录 scratch打地鼠游戏 一、题目要求 编程实现 二、案例分析 1、角色分析
阅读更多...
目标检测，行人检测，出现了检测框和人物不在一起的情况，怎么解决---一定是配置文件的原因

目标检测，行人检测，出现了检测框和人物不在一起的情况，怎么解决---一定是配置文件的原因

今天测试发现人物检测有结果输出&#xff0c;但是发现检测出来的检测框和人物不匹配 但是奇怪的的是在orin中可以 再nx中就不行 结局复制所有orin的程序到nx就可以运行&#xff0c;最后对比配置文件发现是配置文件里不一样 dstest3_config.xml里的tiler不一样 orin中的 tiler: …
阅读更多...
SAP ABAP 主动调用外部系统的REST接口（x-www-form-urlencoded）

SAP ABAP 主动调用外部系统的REST接口（x-www-form-urlencoded）

如何在SAP ECC中调用外部系统提供的REST接口地址&#xff1f; Postman中使用Body中参数情况&#xff0c;使用链接的情况 x-www-form-urlencoded POST成功调用样例如下&#xff1a; SAP中实现如下&#xff1a; 1. 事务码STRUST,导入对方系统证书 2. 事务码SM59配置destinati…
阅读更多...
接口测试需要验证数据库么？

接口测试需要验证数据库么？

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…
阅读更多...
一篇美创科技“中国政务云数据安全领导者实践”案例，分享给大家

一篇美创科技“中国政务云数据安全领导者实践”案例，分享给大家

政务云作为数字政府建设的底座和基石&#xff0c;经过多年高速建设&#xff0c;已覆盖了我国80%以上地市及经济发达的县域。政务云的业务承载率、数据汇聚率不断提升&#xff0c;对数据安全的需求也进一步提高。加强政务云数据安全建设&#xff0c;成为政务云建设中不可绕过的关…
阅读更多...
SpringBoot项目集成发邮件功能

SpringBoot项目集成发邮件功能

1&#xff1a;引入依赖2&#xff1a;配置设置3&#xff1a;授权码获取&#xff1a;4&#xff1a;核心代码5&#xff1a;postman模拟验证6&#xff1a;安全注意 1&#xff1a;引入依赖 <dependency><groupId>org.apache.commons</groupId><artifactId>c…
阅读更多...
【云上探索实验室】快速入门AI 编程助手 Amazon CodeWhisperer ——码上学堂领学员招募

【云上探索实验室】快速入门AI 编程助手 Amazon CodeWhisperer ——码上学堂领学员招募

目录 一、Amazon CodeWhisperer1.1、大语言模型与AI编程1.2、CodeWhisperer初体验 二、云上探索实验室-码上学堂2.1、码上学堂2.2、学课通道入口 三、领学员招募3.1、报名方式3.2、领学奖励 一、Amazon CodeWhisperer 1.1、大语言模型与AI编程 大语言模型&#xff08;Large L…
阅读更多...
图形学中的噪声

图形学中的噪声

1 value noise 四个点取随机数然后做插值。 float random (in vec2 st) {return fract(sin(dot(st.xy,vec2(12.9898,78.233)))* 43758.5453123); }float noise (in vec2 st) {vec2 i floor(st);vec2 f fract(st);float a random(i);float b random(i vec2(1.0, 0.0));fl…
阅读更多...
OpenHarmony Promise详解

OpenHarmony Promise详解

一&#xff0c;定义 作为一个android开发人员&#xff0c;刚接触Promise可能不好理解&#xff0c;因为android中的异步操作都是开启线程操作或者kotlin的协程&#xff0c;但是Promise并不是单独去开启一个线程来处理异步任务&#xff0c;它是在同一个线程中去处理异步任务。异…
阅读更多...
[sd_scripts]之train

[sd_scripts]之train

https://github.com/kohya-ss/sd-scripts/blob/main/docs/train_README-zh.mdhttps://github.com/kohya-ss/sd-scripts/blob/main/docs/train_README-zh.md 支持模型fine-tune&#xff0c;dreambooth&#xff0c;lora&#xff0c;textual inversion。 1.数据准备 在任意多个…
阅读更多...
zabbix中图形可视化页面中文乱码解决

zabbix中图形可视化页面中文乱码解决

在window 电脑中的 C:\Windows\Fonts 里面是字体文件&#xff0c;里面有一个 SIMKAI.TTF &#xff08;有的是小写&#xff09; 这个是楷体 将该文件复制到虚拟机中 怎么导入应该不需要我说吧 查看zabbix的字体文件在哪个目录下 [rootlocalhost /]# find / -name fonts /boo…
阅读更多...
【java学习—十四】反射获取一个类的父类、接口、构造方法（3）

【java学习—十四】反射获取一个类的父类、接口、构造方法（3）

文章目录 1. 通过反射获取一个类的父类和接口2. 反射获取一个类的构造方法2.1. 获取全部构造器 1. 通过反射获取一个类的父类和接口 使用反射可以取得&#xff1a; 实现的全部接口 public Class<?>[] getInterfaces()&#xff1a;确定此对象所表示的类或接口实现的接口…
阅读更多...
最新文章

Copyright @ 2022~2023