【C++】map set 底层刨析

文章目录

  • 1. 红黑树的迭代器
  • 2. 改造红黑树
  • 3. map 的模拟实现
  • 4. set 的模拟实现

在这里插入图片描述

在 C++ STL 库中，map 与 set 的底层为红黑树，那么在不写冗余代码的情况下使用红黑树同时实现 map 与 set 便是本文的重点。

1. 红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以下问题：

  • begin() 与 end()

    STL 明确规定，begin() 与 end() 代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin() 可以放在红黑树中最小节点（即最左侧节点）的位置，end() 放在最大节点（最右侧节点）的下一个位置。

    iterator begin()
{Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);
}const_iterator begin() const
{Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return const_iterator(subLeft);
}iterator end()
{return iterator(nullptr);
}const_iterator end() const
{return const_iterator(nullptr);
}

  • operator++() 与 operator--()

    Self& operator++()
{if (_node->_right){// 右子树的中序第一个（最左节点）Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}Self& operator--()
{// 跟++逻辑相反return *this;
}

2. 改造红黑树

#pragma onceenum Color
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;T _data;RBTreeNode(const T& data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T, class Ptr, class Ref>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ptr, Ref> Self;Node* _node;RBTreeIterator(Node* node): _node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){if (_node->_right){// 右子树的中序第一个（最左节点）Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 祖先里面孩子是父亲左的那个Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){// 跟++逻辑相反return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};// set->RBTree<K, K, SetKeyOfT>
// map->RBTree<K, pair<K, V>, MapKeyOfT>// 因为关联式容器中存储的是<key, value>的键值对，因此
// K为key的类型
// T：如果是map，则为pair<K, V>；如果是set，则为K
// 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);}const_iterator begin() const{Node* subLeft = _root;while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return const_iterator(subLeft);}iterator end(){return iterator(nullptr);}const_iterator end() const{return const_iterator(nullptr);}iterator Find(const K& key){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 end();}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);}}cur = new Node(data);	// 红色的Node* newnode = cur;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;if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况一：叔叔存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续往上处理cur = grandfather;parent = cur->_parent;}// 情况二：叔叔不存在或者存在且为黑else{// 旋转+变色if (cur == parent->_left){//     g//   p   u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g// p     u//   cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}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// u   p//       cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g// u     p//     cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}private:Node* _root = nullptr;
};

3. map 的模拟实现

map 的底层结构就是红黑树，因此在 map 中直接封装一棵红黑树，然后将其接口包装下即可。

#pragma once#include "RBTree.h"namespace tjq
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, const K, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}iterator find(const K& key){return _t.Find(key);}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>, MapKeyOfT> _t;};
}

4. set 的模拟实现

set 的底层为红黑树，因此只需在 set 内部封装一棵红黑树，即可将该容器实现出来。

#pragma once#include "RBTree.h"namespace tjq
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};
}
END

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

openGauss学习笔记-255 openGauss性能调优-使用Plan Hint进行调优-Hint的错误、冲突及告警

openGauss学习笔记-255 openGauss性能调优-使用Plan Hint进行调优-Hint的错误、冲突及告警

文章目录 openGauss学习笔记-255 openGauss性能调优-使用Plan Hint进行调优-Hint的错误、冲突及告警 openGauss学习笔记-255 openGauss性能调优-使用Plan Hint进行调优-Hint的错误、冲突及告警 Plan Hint的结果会体现在计划的变化上&#xff0c;可以通过explain来查看变化。 …
阅读更多...
Flutter Don‘t use ‘BuildContext‘s across async gaps.

Flutter Don‘t use ‘BuildContext‘s across async gaps.

Flutter提示Don‘t use ‘BuildContext‘s across async gaps.的解决办法—flutter里state的mounted属性
阅读更多...
JAVAEE之Spring Boot日志

JAVAEE之Spring Boot日志

1. 日志概述 1.1 学习日志的原因 ⽇志对我们来说并不陌生, 从JavaSE部分, 我们就在使用 System.out.print 来打印日志了. 通过打印日志来发现和定位问题, 或者根据日志来分析程序的运行过程. 在Spring的学习中, 也经常根据控制台的日志来分析和定位问题. 随着项⽬的复杂…
阅读更多...
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

本文涉及的知识点 图论 分类讨论 本题同解 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 LeetCode3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中&#xff0c;存在编号从 1 到 n 的房屋&#xff0c;由 n 条街道相连。对所有 …
阅读更多...
Python 基于列表实现的通讯录管理系统(有完整源码)

Python 基于列表实现的通讯录管理系统(有完整源码)

目录 通讯录管理系统 PersonInformation类 ContactList类 menu函数 main函数 程序的运行流程 完整代码 运行示例 通讯录管理系统 这是一个基于文本的界面程序&#xff0c;用户可以通过命令行与之交互&#xff0c;它使用了CSV文件来存储和读取联系人信息&#xff0c;这…
阅读更多...
Docker实战教程 第1章 Linux快速入门

Docker实战教程 第1章 Linux快速入门

2-1 Linux介绍 为什么要学Linux 三个不得不学习 课程需要&#xff1a;Docker开发最好在Linux环境下。 开发需要&#xff1a;作为一个后端程序员&#xff0c;是必须要掌握Linux的&#xff0c;这是找工作的基础门槛。 运维需要&#xff1a;在服务器端&#xff0c;主流的大型服…
阅读更多...
Java栈和队列的实现

Java栈和队列的实现

目录 一.栈(Stack) 1.1栈的概念 1.2栈的实现及模拟 二.队列(Queue) 2.1队列的概念 2.2队列的实现及模拟 2.3循环队列 2.4双端队列&#xff08;Deque&#xff09; 一.栈(Stack) 1.1栈的概念 栈:一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作…
阅读更多...
element-ui result 组件源码分享

element-ui result 组件源码分享

今日简单分享 result 组件的源码实现&#xff0c;主要从以下三个方面&#xff1a; 1、result 组件页面结构 2、result 组件属性 3、result 组件 slot 一、result 组件页面结构 二、result 组件属性 2.1 title 属性&#xff0c;标题&#xff0c;类型 string&#xff0c;无默…
阅读更多...
11-1(2)-CSS 背景+CSS 精灵图

11-1(2)-CSS 背景+CSS 精灵图

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 一、CSS 背景1 背景颜色2 背景色半透明3 背景图片4 背景平铺5 背景图片位置6 …
阅读更多...
linux操作系统安装及命令初识，上岸蚂蚁金服

linux操作系统安装及命令初识，上岸蚂蚁金服

310 包&#xff09; desktop 1800个包左右 内容必须大于 768M 系统设置 分区设置 挂载点 /boot / swap 交换分区–占用磁盘容量 网络配置 网卡配置 设置为ON 主机名配置 Begin installation 设置 root 用户密码 命令初识 命令 选项 参数&#xff1a; 命令选项参数…
阅读更多...
JavaEE 初阶篇-生产者与消费者模型（线程通信）

JavaEE 初阶篇-生产者与消费者模型（线程通信）

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 生产者与消费者模型概述 2.0 在生产者与消费者模型中涉及的关键概念 2.1 缓冲区 2.2 生产者 2.3 消费者 2.4 同步机制 2.5 线程间通信 3.0 实现生产者与消费者模…
阅读更多...
iOS开发进阶（十三）：脚手架创建iOS项目

iOS开发进阶（十三）：脚手架创建iOS项目

文章目录 一、前言二、xcode-select 命令三、拓展阅读 一、前言 项目初期&#xff0c;需要搭建项目基本框架&#xff0c;为此离不开辅助工具&#xff0c;即脚手架。当然&#xff0c;IDE也可以实现新建空白项目&#xff0c;但是其新建后的项目结构可能不符合预期设计&#xff0…
阅读更多...
AWS-EKS 给其他IAM赋予集群管理权限

AWS-EKS 给其他IAM赋予集群管理权限

AWS EKS 设计了权限管理系统&#xff0c;A用户创建的集群 B用户是看不到并且不能管理和使用kubectl的&#xff0c;所以我们需要共同管理集群时就需要操场共享集群访问给其他IAM用户。 两种方式添加集群控制权限&#xff08;前提&#xff1a;使用有管理权限的用户操作&#xff…
阅读更多...
顺序表相关习题

顺序表相关习题

&#x1f308; 个人主页&#xff1a;白子寰 &#x1f525; 分类专栏&#xff1a;python从入门到精通&#xff0c;魔法指针&#xff0c;进阶C&#xff0c;C语言&#xff0c;C语言题集&#xff0c;C语言实现游戏&#x1f448; 希望得到您的订阅和支持~ &#x1f4a1; 坚持创作博文…
阅读更多...
Java笔试题总结

Java笔试题总结

HashSet子类依靠()方法区分重复元素。 A toString(),equals() B clone(),equals() C hashCode(),equals() D getClass(),clone() 答案:C 解析: 先调用对象的hashcode方法将对象映射为数组下标,再通过equals来判断元素内容是否相同 以下程序执行的结果是&#xff1a; class X{…
阅读更多...
【项目实战经验】DataKit迁移MySQL到openGauss（上）

【项目实战经验】DataKit迁移MySQL到openGauss（上）

前言 本文将分享DataKit迁移MySQL到openGauss的项目实战&#xff0c;供广大openGauss爱好者参考。 1. 下载操作系统 https://www.openeuler.org/zh/download https://support.huawei.com/enterprise/zh/doc/EDOC1100332931/1a643956 https://support.huawei.com/enterprise…
阅读更多...
CSS基础选择器 小案例复习（画三个小盒子）

CSS基础选择器 小案例复习（画三个小盒子）

&#xff08;大家好&#xff0c;前面我们学习了基础的选择器&#xff0c;俗话说&#xff1a;温故而知新。所以今天我们将通过小案例来复习前面学过的小知识点。另&#xff0c;十分感谢大家对我文章的支持❤️&#xff09; 通过这个案例复习两个地方&#xff1a; 类选择器的使用…
阅读更多...
基于ZooKeeper的Kafka分布式集群搭建与集群启动停止Shell脚本

基于ZooKeeper的Kafka分布式集群搭建与集群启动停止Shell脚本

下载Kafka压缩包 下方是Kafka官网下载地址&#xff0c;本文使用Kafka 3.0.0在虚拟机环境中搭建分布式集群。 Apache Kafka Downloads link 虽然在Kafka 2.8.0之后可以使用KRaft模式搭建高可用的集群以提高数据处理效率&#xff0c;但是目前还有许多企业依然使用ZooKeeper搭建K…
阅读更多...
uni-app如何实现高性能

uni-app如何实现高性能

这篇文章主要讲解uni-app如何实现高性能的问题&#xff1f; 什么是uni-app&#xff1f; 简单说一下什么是uni-app&#xff0c;uni-app是继承自vue.js&#xff0c;对vue做了轻度定制&#xff0c;并且实现了完整的组件化开发&#xff0c;并且支持多端发布的一种架构&#xff0c…
阅读更多...
申请SSL证书

申请SSL证书

有很多方法可以确保您的网站安全。添加SSL证书可针对恶意攻击提供额外且关键的保护层。 即使网站不接受交易&#xff0c;您仍然需要保护用户的登录详细信息、地址和其他个人信息。 没有SSL证书的网站使用HTTP&#xff08;一种基于文本的协议&#xff09;&#xff0c;这意味着…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023