当前位置: 首页 > article >正文

【C++、数据结构】封装map和set(用红黑树实现)

文章目录

  • 📖 前言
  • 1. 如何复用同一棵红黑树⚡
      • 1.1 🌀 修改后结点的定义:
  • 2. 模拟实现中何实现数据比较大小🌟
  • 3. 红黑树迭代器的实现🔥
      • 3.1 💥红黑树begin()和 end()的定义
      • 3.2 💥 operator* 和 operator->
      • 3.3 💥 operator++ 和 operator- -
      • 3.4 💥 operator== 和 operator!=
  • 4. 封装map和set⭕

📖 前言

在这之前我们学习了红黑树的模拟实现,学习了如何使用map和set,同时我们也了解到,map和set底层都是用红黑树来实现的,本文我们就要自己动手封装一下map和set这两大容器,用我们之前学的红黑树来实现一下……🙋 🙋 🙋 🙋 🙋

前情回顾:手撕红黑树 👉 传送门

前情回顾:map和set 👉 传送门


1. 如何复用同一棵红黑树⚡

前提疑问:

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

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

答案:

很显然根据STL的设计理念,是不可能是两个容器各自用一棵红黑树的,这不符合泛型编程的理念,实际上确实是用的同一棵树,只是对我们之前的红黑树做了一些改动。

我们来看一下STL官方库的原码:

在这里插入图片描述
通过翻看原码我们得知:

  • map和set都是在复用同一棵红黑树
  • 它们实现的都是Key_value模型

这样设计的好处,两个容器都可以复用同一棵红黑树,体现了泛型编程的思想。

我们设T为红黑树的结点:

  • 对于set而言,T就是RBTree<K, K>
  • 对于map而言,T就是RBTree<K, pair<K, V>>

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

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

因为map的这个类中,无论怎么省略都会有一个查找函数…
在这里插入图片描述
如果将Key省略的话,map中查找数据就不知道数据的类型了,所以必须保留Key。

综上所述:

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

1.1 🌀 修改后结点的定义:

enum Colour
{RED,BLACK,
};//上层维度的一个泛型
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;	//数据Colour _col;RBTreeNode(const T& data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};

2. 模拟实现中何实现数据比较大小🌟

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

pair比较大小:

在这里插入图片描述
很显然这种比较规则不是我们所想要的,并且map和set想要取到用来比较的数据是不同的。

为了取到我们想要的数据,我们引入了仿函数:

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

在这里插入图片描述
通过仿函数,直接从红黑树的一个结点中取出想要的数据。

因为map和set中需要比较的数据取出方式不同,所以分别在map和set类中实现不同的仿函数。

map中的仿函数:
在这里插入图片描述
set中的仿函数:

在这里插入图片描述
使用方法:
在这里插入图片描述
此时仿函数的方便之处就体现出来了。

代码演示:

//红黑树的实现
//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// cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//双旋//    g//  p//    celse{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//     cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//双旋//  g//    p//  celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//父亲为空就出循环,将根节点设置成黑色_root->_col = BLACK;return make_pair(iterator(newnode), true);}
}

3. 红黑树迭代器的实现🔥

虽然map和set这种关联式容器的迭代器使用起来和序列式容器使用起来一样,但是底层实现却不尽相同。

3.1 💥红黑树begin()和 end()的定义

在这里插入图片描述

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

而库中的红黑树则是设计了一个哨兵位的头结点:
在这里插入图片描述
库中实现的end就和我们所实现的不同了,我们实现的是简化版的。

先直接见代码:

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;}
};
  • T:数据
  • Ref:引用
  • Ptr:指针
  • Sef:iterator本身

3.2 💥 operator* 和 operator->

在这里插入图片描述
就是正常的运用operator。


3.3 💥 operator++ 和 operator- -

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

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

在这里插入图片描述
it走到哪,说明哪个结点已经访问过了,接下来我们的操作不是递归,但是胜似递归

我们大致的思路:

  • 跟着中序遍历的方式,it肯定是从5->6->7->8
  • 很显然这时我们只需要看当前位置右子树是否是空

分如下两种情况:(重点)

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

为什么右子树为空时,不能直接跳到该结点的父亲节点吗?

答案是不行的,如图所示:

在这里插入图片描述

如果按照问题中那样右子树为空直接跳到父亲的话,5->6,6的右子树不为空,6->7,然后7的右子树为空,7->6,然后6的右子树不为空,6->7,然后7的右子树为空,7->6……这样就反复横跳了……

所以我们找到一个办法:那就是找孩子是祖先的左的那个祖先节点。

这样就实现了非递归,这种非递归的前提是(一定是三叉链)

在这里插入图片描述
前置- - :

我们大致的思路:

  • 很显然这时我们只需要看当前位置左子树是否是空

前置- -就是倒着走,同样还是对当前位置分两种情况:(重点)

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

在这里插入图片描述
只要前置++理解了,那么前置- -完全就是前置++倒过来走一遍。

后置++、后置- - :

和之前实现容器的得带器一样,我们这里直接复用即可:
在这里插入图片描述

3.4 💥 operator== 和 operator!=

直接见下图所示:
在这里插入图片描述
红黑树中查找函数:

iterator 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 iterator(cur);}return End();}
}

4. 封装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;
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章:

【C++、数据结构】封装map和set(用红黑树实现)

文章目录&#x1f4d6; 前言1. 如何复用同一棵红黑树⚡1.1 &#x1f300; 修改后结点的定义&#xff1a;2. 模拟实现中何实现数据比较大小&#x1f31f;3. 红黑树迭代器的实现&#x1f525;3.1 &#x1f4a5;红黑树begin&#xff08;&#xff09;和 end&#xff08;&#xff09…...

Python-项目实战--飞机大战-pygame快速入门(3)

4.理解精灵和精灵组4.1精灵和精灵组在刚刚完成的案例中&#xff0c;图像加载、位置变化、绘制图像都需要程序员编写代码分别处理为了简化开发步骤&#xff0c;pygame提供了两个类pygame.sprite.Sprite --存储图像数据 image和位置rect的对象pygame.sprite.Group注意&#xff1a…...

【2007NOIP普及组】T4.Hanoi双塔问题 试题解析

【2007NOIP普及组】T4.Hanoi双塔问题 试题解析 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有空的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。现要…...

Camtasia2023免费屏幕录像软件支持MP4/AVI/WMV等多种格式

微课教学现在越来越受欢迎&#xff0c;如果你是一名教师&#xff0c;肯定知道喀秋莎的存在&#xff0c;可能曾经在哪儿相遇过&#xff0c;现在甚至还念念不忘&#xff01;如果真的喜欢&#xff0c;这里可以觅到她的倩影了。camtasia是一款十六进制编辑器的软件&#xff0c;camt…...

MySQL中的事务(隔离性详解)

1.什么是事务事务是指逻辑上的一组操作,组成这组操作的各个单元,要么全部成功,要么全部失败(通俗的说一组SQL语句,要么全部执行成功,一条语句出错则全部出粗);在不同的环境中,都可以有事务,对应在数据库中,就是数据库事务.2.为什么使用事务事务的核心逻辑就是多条SQL语句要么全…...

iPhone苹果手机Apple id帐号如何永久性注销删除数据?

原文来源&#xff1a;https://www.caochai.com/article-4120.html 注本方法&#xff1a;将会将您的iPhone苹果手机Apple id帐号从所有 Apple App、服务和 iCloud&#xff08;由云上贵州运营&#xff09; 中永久删除你的帐户和相关联的数据。 iPhone苹果手机Apple id帐号如何永…...

CSDN第26期周赛赛后总结(第一次AK)

文章目录前言一、 等差数列1、题目描述2、思路分析3、代码详解二、阿波罗的魔力宝石1、题目描述2、思路分析3、代码详解三、任务分配问题1、题目描述2、思路分析3、代码详解四、单词逆序1、题目描述2、思路分析3、代码详解总结前言 第一次AK&#xff0c;记录与反思一下。 一、 …...

MySQL面试题:MySQL锁机制

文章目录1. 封锁粒度2. 封锁类型读写锁意向锁3. 封锁协议1. 一级封锁协议&#xff08;修改-事务&#xff09;2. 二级封锁协议&#xff08;读取-立即&#xff09;3. 三级封锁协议&#xff08;读取-事务&#xff09;4. 封锁协议与隔离级别5. 两段锁协议a. 概念b. 例子c. 两段锁是…...

带你三分钟了解网络用语之计算机网络概述

计算机网络概述 结点 &#xff08;node&#xff09; &#xff1a;网络中的结点可以是计算机&#xff0c;集线器&#xff0c;交换机或路由器等。主机&#xff08;host&#xff09; &#xff1a;连接在因特网上的计算机。ISP&#xff08;Internet Service Provider&#xff09; …...

【博客613】tcp重置防火墙原理:构造RST报文来终结非法活跃连接

tcp重置防火墙原理&#xff1a;构造RST报文来终结非法活跃连接 1、场景 如何关闭一个 TCP 连接&#xff1f; 可能大家第一反应是「杀掉进程」不就行了吗&#xff1f; 是的&#xff0c;这个是最粗暴的方式&#xff0c;杀掉客户端进程和服务端进程影响的范围会有所不同&#…...

(2023Q2模拟题JAVA)华为OD机试 - 最多提取子串数目

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:最多提取子串数目 题目 给定…...

docker-compose部署rabbitmq集群

1、集群分类 RabbitMQ的是基于Erlang语言编写&#xff0c;而Erlang又是一个面向并发的语言&#xff0c;天然支持集群模式。 RabbitMQ的集群以下分类&#xff1a; 标准集群&#xff1a;是一种分布式集群&#xff0c;将队列分散到集群的各个节点&#xff0c;从而提高整个集群的并…...

如何实现手势识别功能?

本文选自StackOverflow&#xff08;简称&#xff1a;SOF&#xff09;精选问答汇总系列文章之一&#xff0c;本系列文章将为读者分享国外最优质的精彩问与答&#xff0c;供读者学习和了解国外最新技术&#xff0c;本文为大家讲解cocos2dx中&#xff0c;如何实现手势识别功能。 问…...

Cocos2d-x 屏幕适配新解(比较全面比较详细)

本文出自 [无间落叶]原文地址&#xff1a;http://blog.leafsoar.com/archives/2013/05-10-19.html 为了适应移动终端的各种分辨率大小&#xff0c;各种屏幕宽高比&#xff0c;在 cocos2d-x&#xff08;当前稳定版&#xff1a;2.0.4&#xff09; 中&#xff0c;提供了相应的解决…...

如何优雅的管理游戏资源

[叶落归根]&#xff1a; http://blog.leafsoar.com/archives/2013/11-27.html 在游戏的开发过程中&#xff0c;前期的规划 往往比 后期的“优化”更为重要&#xff01;比如多分辨率适配&#xff0c;如果前期没有规划好&#xff0c;可能导致的情况是&#xff0c;画面只在当前测试…...

【SQL开发实战技巧】系列(三十):数仓报表场景☞树形(分层)查询如何排序?以及如何在树形查询中正确的使用where条件

系列文章目录 【SQL开发实战技巧】系列&#xff08;一&#xff09;:关于SQL不得不说的那些事 【SQL开发实战技巧】系列&#xff08;二&#xff09;&#xff1a;简单单表查询 【SQL开发实战技巧】系列&#xff08;三&#xff09;&#xff1a;SQL排序的那些事 【SQL开发实战技巧…...

修建灌木顺子日期

题目 有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修剪灌木。直到修剪了最左的灌木后再次调转方…...

ARM LCD 编程实战

一、LCD编程实战1 - LCD 控制器初始化 参考代码 lcd_init 函数详解 (1) 要想 LCD 工作&#xff0c;必须给 LCD 屏幕和显存之间建立一个映射&#xff08;映射是在 CPU 初始化 LCD 控制器来完成的&#xff09;。本部分就是在完成这个过程&#xff08;这也是 LCD 显示的 2 个阶段…...

被大厂废掉的年轻人

作者| Mr.K 编辑| Emma来源| 技术领导力(ID&#xff1a;jishulingdaoli)朋友M总的公司招人&#xff0c;有两个候选人&#xff0c;一个是有大厂经验的“毕业生”&#xff0c;另一个曾在某腰部企业工做过团队主管。M总有点拿不准&#xff0c;问K哥的意见。对比两人的简历后&…...

华为OD机试真题 - 猜字谜(Python)

题目描述 小王设计了一个简单的猜字谜游戏,游戏的谜面是一个错误的单词,比如nesw,玩家需要猜出谜底库中正确的单词。猜中的要求如下: 对于某个谜面和谜底单词,满足下面任一条件都表示猜中: 变换顺序以后一样的,比如通过变换w和e的顺序,“nwes”跟“news”是可以完全对…...