文章目录

  • 前言
  • 红黑树的改变
  • set的模拟实现
    • 基本框架
    • 迭代器
    • 插入
    • 源码
  • map模拟实现
    • 基础框架
    • 迭代器
    • 插入
    • 赋值重载
    • 源码
  • 测试代码

前言

set，map底层使用红黑树这种平衡二叉搜索树来组织元素 ，这使得set, map能够提供对数时间复杂度的查找、插入和删除操作。
下面都是基于红黑树实现的set和map。

红黑树的改变

由于set和map是公用一棵树，set是K 、map是KV的结构，为了适应set与map的结构，红黑树要做出一定的改变.

  • 仿函数是为了取到set内所存储的数据
  • 在set的map中 set所存储的是key而map是pair
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;enum Color
{RED,BLACK
};template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr){}
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node,Node* root):_node(node),_root(root){}//左 -> 根 -> 右Self operator++(){//右不为空，右的最左(小）结点if (_node->_right){Node* min = _node->_right;while (min && min->_left){min = min->_left;}_node = min;}//右为空，找孩子是父亲左的结点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self operator--(){// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点if (_node == nullptr){Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}// 左不为空，中序左的最右(大)结点else if (_node->_left){Node* rightMost = _node->_left;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}// 左为空，孩子是父亲右的那个祖先else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator==(const Self&s) const{return _node == s._node;}bool operator!=(const Self& s) const{return _node != s._node;}
};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*> ConstIterator;Iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}Iterator end(){return Iterator(nullptr, _root);}ConstIterator begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return Iterator(cur, _root);}ConstIterator end() const{return Iterator(nullptr, _root);}pair<Iterator,bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(_root, _root), true);return { Iterator(_root, _root), true };}Node* cur = _root;Node* parent = nullptr;KeyOfT kot;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 { Iterator(cur, _root), false };}}cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;cur->_col = RED;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//  g//p   uif (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{//    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;}}//  g//u   pelse{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 { Iterator(newnode, _root), true };}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* Pparent = parent->_parent;if (subRL){subRL->_parent = parent;}parent->_right = subRL;parent->_parent = subR;subR->_left = parent;if (Pparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (Pparent->_left == parent){Pparent->_left = subR;}else{Pparent->_right = subR;}subR->_parent = Pparent;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* Pparent = parent->_parent;if (subLR){subLR->_parent = parent;}parent->_left = subLR;parent->_parent = subL;subL->_right = parent;if (Pparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (Pparent->_left == parent){Pparent->_left = subL;}else{Pparent->_right = subL;}subL->_parent = Pparent;}}void InOrder(){_InOrder(_root);cout << endl;}int Size(){return _Size(_root);}int Height(){return _Height(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if(cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == RED){return false;}int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){refNum++;}cur = cur->_left;}return Check(_root, 0, refNum);}~RBTree(){Destroy(_root);_root = nullptr;}private:void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << "->" << root->_col << endl;_InOrder(root->_right);}int _Size(Node* root){if (root == nullptr){return 0;}return _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr){return 0;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;//说明一条路径已经走完了if (blackNum != refNum){cout << "存在黑色结点数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "出现连续的红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}
private:Node* _root = nullptr;
};

set的模拟实现

当前的红黑树需要这三个类型参数（键值、数据，通过数据求key的仿函数），这是为了map也能够复用，但是set只传入一个数据，所以采用这样的方式：<K， const K，SetKeyOfT< K >>，因为set中的数据是不能被修改的所以在第二个类型中加上const.

基本框架

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

迭代器

这里的迭代器直接复用红黑树的迭代器.

typedef typename RBTree<K,const K,SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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 K& key)
{return _t.Insert(key);
}

源码

#pragma oncenamespace mihayou
{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>::ConstIterator 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 K& key){return _t.Insert(key);}~set(){}private:RBTree<K, const K,SetKeyOfT> _t;};
}

map模拟实现

map给红黑树传的类型为：<K, pair<const K, V>, MapKeyOfT> ,K类型用于删除、查找等，pair<const K, V>作为数据插入，MapKeyOfT取pair<const K, V,>中的K类型，又因为键值不能修改所以pair<const K, V,>中的K加上const修饰.

基础框架

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

迭代器

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator 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);
}

赋值重载

在map里面，当key不存在时，重载[ ]就会用key进行插入操作并返回插入后key对应数据的引用（此时key对应数据是用其默认构造进行初始化的），当key存在时，返回key对应数据的引用。

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

源码

#pragma oncenamespace mihayou
{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, pair<const K, V>, MapKeyOfT>::ConstIterator 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);}V& operator[](const K& key){pair<iterator, bool> it = insert({ key,V()});return it.first->second;}~map(){}private:RBTree<K, pair<const K,V>,MapKeyOfT> _t;};
}

测试代码

#include "RBTree.h"
#include "Myset.h"
#include "Mymap.h"
#include <string>void Print(const mihayou::set<int>& s)
{mihayou::set<int>::const_iterator it = s.end();while (it != s.begin()){--it;cout << *it << " ";}cout << endl;
}void test01()
{mihayou::set<int> s;s.insert(1);s.insert(5);s.insert(3);s.insert(7);s.insert(6);mihayou::set<int>::iterator itt = s.begin();//*itt += 10;while (itt != s.end()){cout << *itt << " ";++itt;}cout << endl;for (auto& e : s){cout << e << " ";}cout << endl;Print(s);s.~set();mihayou::map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边，剩余";dict["insert"] = "插入";dict["string"];mihayou::map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}dict.~map();
}int main()
{test01();return 0;
}

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

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

相关文章

LabVIEW液压机智能监控

LabVIEW液压机智能监控

​基于LabVIEW平台&#xff0c;结合西门子、研华等硬件&#xff0c;构建液压机实时监控系统。通过 OPC 通信技术实现上位机与 PLC 的数据交互&#xff0c;解决传统监控系统数据采集滞后、存储有限、参数调控不便等问题&#xff0c;可精准采集冲压过程中的位置、速度、压力等参数…
阅读更多...
15. 什么是 xss 攻击？怎么防护

15. 什么是 xss 攻击？怎么防护

总结 跨站脚本攻击&#xff0c;注入恶意脚本敏感字符转义&#xff1a;“<”,“/”前端可以抓包篡改主要后台处理&#xff0c;转义什么是 XSS 攻击&#xff1f;怎么防护 概述 XSS&#xff08;Cross-Site Scripting&#xff0c;跨站脚本攻击&#xff09;是一种常见的 Web 安全…
阅读更多...
更换docker工作目录

更换docker工作目录

使用环境 由于默认系统盘比较小docker镜像很容易就占满&#xff0c;需要挂载新的磁盘修改docker的默认工作目录 环境&#xff1a;centos7 docker默认工作目录: /var/lib/docker/ 新的工作目录&#xff1a;/home/docker-data【自己手动创建&#xff0c;一般挂在新加的磁盘下面】…
阅读更多...
算法学习笔记：26.二叉搜索树（生日限定版）——从原理到实战，涵盖 LeetCode 与考研 408 例题

算法学习笔记：26.二叉搜索树（生日限定版）——从原理到实战，涵盖 LeetCode 与考研 408 例题

二叉搜索树&#xff08;Binary Search Tree&#xff0c;简称 BST&#xff09;是一种特殊的二叉树&#xff0c;因其高效的查找、插入和删除操作&#xff0c;成为计算机科学中最重要的数据结构之一。BST 的核心特性是 “左小右大”&#xff0c;这一特性使其在数据检索、排序和索引…
阅读更多...
共生型企业：驾驭AI自动化（事+AI）与人类增强（人+AI）的双重前沿

共生型企业：驾驭AI自动化（事+AI）与人类增强（人+AI）的双重前沿

目录 引言&#xff1a;人工智能的双重前沿 第一部分&#xff1a;自动化范式&#xff08;事AI&#xff09;——重新定义卓越运营 第一章&#xff1a;智能自动化的机制 第二章&#xff1a;自动化驱动的行业转型 第三章&#xff1a;自动化的经济演算 第二部分&#xff1a;协…
阅读更多...
TypeScript的export用法

TypeScript的export用法

在 TypeScript 中&#xff0c;export 用于将模块中的变量、函数、类、类型等暴露给外部使用。export 语法允许将模块化的代码分割并在其他文件中导入。 1. 命名导出&#xff08;Named Export&#xff09; 命名导出是 TypeScript 中最常见的一种导出方式&#xff0c;它允许你导出…
阅读更多...
数据结构-2(链表)

数据结构-2(链表)

一、思维导图二、链表的反转def reverse(self):"""思路&#xff1a;1、设置previous_node、current、next_node三个变量,目标是将current和previous_node逐步向后循环并逐步进行反转,知道所有元素都被反转2、但唯一的问题是&#xff1a;一旦current.next反转为向…
阅读更多...
ros2 标定相机

ros2 标定相机

一个终端执行&#xff1a; ros2 run image_tools cam2image --ros-args -p width:640 -p height:480 -p frequency:30.0 -p device_id:-1 -r /image:/camera/image_raw另一个终端执行&#xff1a;8x6 是格子角点数量&#xff0c;0.028是格子尺寸 ros2 run camera_calibration …
阅读更多...
IsaacLab学习记录（二）

IsaacLab学习记录（二）

二、导入并训练自己的机器人1、urdf等其他格式转usd&#xff08;工具在./scrips/tools/&#xff09;​​​维度​​​​URDF (Unified Robot Description Format)​​​​USD (Universal Scene Description)​​​​定位​​机器人模型描述标准&#xff08;仅描述单机器人&…
阅读更多...
基于Rust Softplus 函数实践方法

基于Rust Softplus 函数实践方法

Softplus 函数 Softplus 函数是神经网络中常用的激活函数之一，定义为： ​ Softplus函数导数 ​ 是 sigmoid 函数。Softplus 处处可导，并且导数恰好是 sigmoid。 它是 ReLU 函数的平滑近似，具有连续可导的特性，适合需要梯度优化的场景。 数学特性 平滑性：导数为 Sig…
阅读更多...
Ubuntu服务器安装Miniconda

Ubuntu服务器安装Miniconda

下载 Miniconda 安装脚本&#xff08;如果能联网&#xff09;wget https://repo.anaconda.com/miniconda/Miniconda3-py39_24.1.2-0-Linux-x86_64.sh -O Miniconda3.sh安装 Miniconda 到 /opt/condabash Miniconda3.sh -b -p /opt/conda激活 conda/opt/conda/bin/conda init ba…
阅读更多...
Java数组补充v2

Java数组补充v2

一、数组基本概念1. 什么是数组数组是Java中用来存储同类型数据的固定大小的连续内存空间的数据结构。2. 数组特点固定长度&#xff1a;一旦创建&#xff0c;长度不可改变相同类型&#xff1a;所有元素必须是同一数据类型索引访问&#xff1a;通过下标&#xff08;从0开始&…
阅读更多...
【PTA数据结构 | C语言版】前缀树的3个操作

【PTA数据结构 | C语言版】前缀树的3个操作

本专栏持续输出数据结构题目集&#xff0c;欢迎订阅。 文章目录题目代码题目 请编写程序&#xff0c;利用前缀树查找给定字符串是否在某给定字符串集合 S 中。 输入格式&#xff1a; 输入首先给出一个正整数 n&#xff08;≤1000&#xff09;&#xff0c;随后 n 行&#xff0…
阅读更多...
JAVA面试宝典 -《缓存架构：穿透 / 雪崩 / 击穿解决方案》

JAVA面试宝典 -《缓存架构：穿透 / 雪崩 / 击穿解决方案》

&#x1f4a5;《缓存架构&#xff1a;穿透 / 雪崩 / 击穿解决方案》 文章目录&#x1f4a5;《缓存架构&#xff1a;穿透 / 雪崩 / 击穿解决方案》&#x1f9ed; 一、开篇导语&#xff1a;为什么缓存是高并发系统的命脉&#xff1f;✅1.1 缓存的核心价值缓存带来的收益​​&…
阅读更多...
FPGA创意项目网页或博客推荐

FPGA创意项目网页或博客推荐

1. 综合项目平台（开源+教程） ① Hackster.io - FPGA专区 🔗 https://www.hackster.io/fpga 特点： 大量基于FPGA的创意项目（如Zynq游戏机、视觉处理、机器人控制）。 提供完整教程（Vivado工程文件+代码）。 推荐项目： FPGA-Based Oscilloscope（低成本示波器） V…
阅读更多...
Go 程序无法使用 /etc/resolv.conf 的 DNS 配置排查记录

Go 程序无法使用 /etc/resolv.conf 的 DNS 配置排查记录

在最近的一次部署中&#xff0c;我遇到一个奇怪的问题&#xff1a;Go 程序在运行时不使用 /etc/resolv.conf 中的 DNS 设置&#xff0c;导致服务无法正常访问域名。这篇文章记录下完整的排查过程和最终的解决方案。1. 问题现象我有一个部署在 KVM 虚拟机内的 Go 应用&#xff0…
阅读更多...
微服务相关问题（2）

微服务相关问题（2）

1、Spring Cloud相关常用组件注册中心&#xff08;nacos、Eureka等&#xff09;、负载均衡&#xff08;Ribbon、LoadBalancer&#xff09;、远程调用&#xff08;feign&#xff09;、服务熔断&#xff08;Sentinel、Hystrix&#xff09;、网关&#xff08;Gateway&#xff09;2…
阅读更多...
安全初级2

安全初级2

一、作业要求 1、xss-labs 1~8关 2、python实现自动化sql布尔育注代码优化(二分查找) 二、xss-labs 1~8关 1、准备 打开小皮面板&#xff0c;启动MySQL和apacher 下载 xss-labs&#xff0c;并解压后放到 phpstudy_pro 的 WWW 目录下&#xff0c;重命名为 xss-labs 访问链…
阅读更多...
基础算法题

基础算法题

基础算法题 链表 1.1反转链表 描述&#xff1a; 描述 给定一个单链表的头结点pHead(该头节点是有值的&#xff0c;比如在下图&#xff0c;它的val是1)&#xff0c;长度为n&#xff0c;反转该链表后&#xff0c;返回新链表的表头。 数据范围&#xff1a; 0≤&#xfffd;≤…
阅读更多...
Android 15 源码修改：为第三方应用提供截屏接口

Android 15 源码修改：为第三方应用提供截屏接口

概述 在 Android 系统开发中，有时需要为第三方应用提供系统级的截屏功能。本文将详细介绍如何通过修改 Android 15 源码中的 PhoneWindowManager 类，实现一个自定义广播接口来触发系统截屏功能。 修改方案 核心思路 通过在系统服务 PhoneWindowManager 中注册自定义广播监…
阅读更多...
最新文章

Copyright @ 2022~2023