红黑树封装map和set（c++版）

embedded/2025/1/21 4:12:05/

前言

在前面，我们介绍了c++中map和set库的使用，也实现了一颗简单的红黑树。那么现在我们就利用这两部分的知识，实现一个简单的myMap和mySet。

源码阅读

在我们实现之前，我们可以阅读一些标准库的实现，学习标准库的实现思路。这里我们选取的是SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件
中

下面我们就分别把这几个头文件中核心代码拎出来阅读一下

// set
#ifndef __SGI_STL_INTERNAL_TREE_H //条件编译
#include <stl_tree.h> //红黑树
#endif
#include <stl_set.h> //不允许键值冗余
#include <stl_multiset.h> //允许键值冗余
// map
#ifndef __SGI_STL_INTERNAL_TREE_H //条件编译
#include <stl_tree.h> //红黑树
#endif
#include <stl_map.h> //不允许键值冗余
#include <stl_multimap.h> //允许键值冗余

我们发现map和set都是包含其他头文件，调用其他头文件的实现，这里也是再封装一层的体现，方便调用者的使用

// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:// typedefs:typedef Key key_type;typedef Key value_type;
private:typedef rb_tree<key_type, value_type,identity<value_type>, key_compare, Alloc> rep_type;rep_type t; // 表示set的红黑树
};
// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:// typedefs:typedef Key key_type;typedef T mapped_type;typedef pair<const Key, T> value_type;
private:typedef rb_tree<key_type, value_type,select1st<value_type>, key_compare, Alloc> rep_type;rep_type t; //表示map的红黑树
};

Key是键；T是map中值的值；Compare是一个比较的仿函数，通过传入不同的仿函数，实现降序或升序；Alloc是空间配置器，我们不关注

不难发现，map和set共用了同一颗红黑树，这颗红黑树存在的是键值对。对于set来说键和值都是Key，对于map来说键是Key值是pair<const Key, T>的一个容器，作用是保证Key值不被修改

identity<value_type>和select1st<value_type>是两个仿函数，作用是从value_type类型中取出Key值的大小，本质上就是兼容上的处理，这个我们在后面还会展开。同理set传入两个Key类型给tree也是兼容上的处理。

下面我们就可以来看一下tree的实现

我们可以先来看看treeNode节点的实现

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;
}；

下面我们看一下tree的实现

// stl_tree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc
= alloc>
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;typedef rb_tree_node* link_type;typedef Key key_type;typedef Value value_type;
public:// insert⽤的是第⼆个模板参数左形参pair<iterator,bool> insert_unique(const value_type& x); //插入，不允许键值冗余// erase和find⽤第⼀个模板参数做形参size_type erase(const key_type& x); //删除iterator find(const key_type& x); //查找
protected:size_type node_count; //记录树节点的数量link_type header; //根节点
};

我们发现这里的命令还是比较混乱的，我们建议后续的实现中，将键值定义为Key和Value，将红黑树存储的值定义为T，统一命名风格。我们这里也修改为这种命名风格

红黑树的实现

这里红黑树的实现我们复用我们之前实现的代码，这里实现的具体细节我们不在展开，需要进一步了解的可以查阅我们之前的博客

定义颜色

enum Color //颜色枚举
{RED, //红BLACK //黑
};

定义节点

template<class T>
class RBTreeVal
{template<class K, class T,class KFromT>friend class RBTree; //将红黑树提前声明为友元类，方便红黑树使用节点template<class T, class Ref,class Ptr>friend class RBTreeIterator; //将迭代器提前声明为友元类，方便迭代器使用节点
public:RBTreeVal(const T& t) //构造函数:_t(t){}
private://左右子节点和父节点RBTreeVal<T>* _left = nullptr;RBTreeVal<T>* _right = nullptr;RBTreeVal<T>* _parent = nullptr;//存储数据T _t = T();//节点默认为红色Color _col = RED;
};

这里我们在实现迭代器的时候使用了模板，是普通迭代器和const迭代器复用同一个类，等到具体实现的时候我们会再介绍一次

KFromT是从T类型中得到K值的仿函数

定义红黑树

首先我们需要将红黑树的框架搭好

template<class K,class T,class KFromT>
class RBTree
{typedef RBTreeVal<T> Node;
public:typedef RBTreeIterator<T, T&, T*> Iterator;//普通迭代器 typedef RBTreeIterator<T, const T&, const T*> constIterator;//const迭代器
private:	Node* _root=nullptr; //根节点
};

这里我们现将迭代器定义好，在后面再展开实现

加入红黑树旋转的逻辑

    //左单选void rotateL(Node*par){Node* chi = par->_right;Node* chiL = chi->_left;par->_right = chiL;if (chiL != nullptr){chiL->_parent = par;}chi->_parent = par->_parent;chi->_left = par;par->_parent = chi;if (chi->_parent != nullptr && chi->_parent->_left == par){chi->_parent->_left = chi;}else if (chi->_parent != nullptr && chi->_parent->_right == par){chi->_parent->_right = chi;}if (_root == par){_root = chi;}}//右单旋void rotateR(Node* par){Node* chi = par->_left;Node* chiR = chi->_right;par->_left = chiR;if (chiR != nullptr){chiR->_parent = par;}chi->_parent = par->_parent;chi->_right = par;par->_parent = chi;if (chi->_parent != nullptr && chi->_parent->_left == par){chi->_parent->_left = chi;}else if (chi->_parent != nullptr && chi->_parent->_right == par){chi->_parent->_right = chi;}if (_root == par){_root = chi;}}//右左双旋void rotateRL(Node* par){Node* chi = par->_right;rotateR(chi);rotateL(par);}//左右双旋void rotateLR(Node* par){Node* chi = par->_left;rotateL(chi);rotateR(par);}

统一接口的风格，传入旋转的支点节点就可以实现旋转

我想我们可能需要先实现迭代器，因为插入，寻找可能都需要用到迭代器

我们先搭建一个迭代器的框架

template<class T,class Ref,class Ptr>
class RBTreeIterator
{typedef RBTreeVal<T> Node;typedef RBTreeIterator<T,Ref,Ptr> Self;template<class K, class T, class KFromT>friend class RBTree;
public:RBTreeIterator(Node* node=nullptr,Node* root = __nullptr):_node(node),_root(root){}
private:Node* _node = nullptr;//当前节点Node* _root = nullptr;//根节点，
};

这里我们把迭代器就是封装一层Node*，采用中序遍历的方式，遍历结果是有序的

下面我们就可以加入迭代器++的逻辑

这里++的逻辑可能比较复杂，要分两种情况，如果此迭代器还有右子节点，则找右子树中的最左节点；如果此节点没有右节点，则代表这个节点所在的这颗子树是某个祖先节点的左子树，而左子树已经遍历完，这个祖先节点就是++后的下一个节点，或者这是最后一个有效节点此时会返回一个nullptr标记的迭代器

我们按照这个逻辑完成迭代器++

Self operator++(){if (_node->_right != nullptr){Node* cut = _node->_right;while ( cut->_left){cut = cut->_left;}_node = cut;return *this;}Node* par = _node->_parent;Node* chi = _node;while (par != nullptr){if (par->_left == chi){_node = par;return *this;}chi = par;par = par->_parent;}_node = nullptr;return *this;}

--的逻辑和++的逻辑为镜像，注意的是，如果用到nullptr的迭代器则返回最后一个有效的节点，此时需要用到_root，如果是根节点--则返回nullptr节点

Self operator--(){if (_node == nullptr){Node* cut = _root;while (cut && cut->_right){cut = cut->_right;}_node = cut;return *this;}if (_node->_left != nullptr){Node* cut = _node->_left;while (cut->_right){cut = cut->_right;}_node = cut;return *this;}Node* par = _node->_parent;Node* chi = _node;while (par != nullptr){if (par->_right == chi){_node = par;return *this;}chi = par;par = par->_parent;}_node = nullptr;return *this;}

实现迭代器 == 和 != 比较的逻辑，只需要比较地址是否相同即可

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

在加入迭代器取值的操作 * 和 ->

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

有了这些，我们就可以在红黑树中实现普通迭代器和const迭代器的begin和end了

	Iterator begin(){if (_root == nullptr){return Iterator(nullptr,_root);}Node* cut = _root;while (cut->_left != nullptr){cut = cut->_left;}return Iterator(cut, _root);}constIterator begin() const{if (_root == nullptr){return constIterator(nullptr, _root);}Node* cut = _root;while (cut->_left != nullptr){cut = cut->_left;}return constIterator(cut, _root);}Iterator end(){return Iterator(nullptr, _root);}constIterator end() const{return constIterator(nullptr, _root);}

我们接着实现插入元素的逻辑。

插入节点传入的参数是T类型，仿函数KFromT会从T类型中返回K的值，返回值遵从标准库返回一个pair<Iterator,bool>，迭代器指向插入元素的位置，bool值返回插入是否成功，如果存在则返回失败，插入的逻辑和红黑树插入的逻辑相同，这里就不展开了

//插入元素pair<Iterator,bool> insert(const T& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return { Iterator(_root,_root),true };}Node* chi = _root;Node* par = nullptr;KFromT tToK;while (chi !=nullptr){if (tToK(kv) > tToK(chi->_t)){par = chi;chi = chi->_right;}else if (tToK(kv) < tToK(chi->_t)){par = chi;chi = chi->_left;}else if (tToK(kv) == tToK(chi->_t)){//已经存在return { Iterator(chi, _root), false };}else{assert(false);}}chi = new Node(kv);Node* rem = chi;chi->_parent = par;if (tToK( par->_t) > tToK(kv)){par->_left = chi;}else if (tToK(par->_t) < tToK(kv)){par->_right = chi;}else{assert(false);}while (par !=nullptr && par->_col != BLACK){Node* gra = par->_parent;if (gra == nullptr){break;}Node* unc = nullptr;if (gra->_left == par){unc = gra->_right;}else if (gra->_right == par){unc = gra->_left;}else{assert(false);}//叔叔存在且为红if (unc != nullptr && unc->_col == RED){unc->_col = BLACK;par->_col = BLACK;gra->_col = RED;chi = gra;par = chi->_parent;}else if (unc == nullptr || unc->_col == BLACK){//右单旋if (chi == par->_left && par == gra->_left){rotateR(gra);gra->_col = RED;par->_col = BLACK;}//右左双旋else if(chi == par->_left && par == gra->_right){rotateRL(gra);chi->_col = BLACK;gra->_col = RED;}//左右双旋else if (chi == par->_right && par == gra->_left){rotateLR(gra);chi->_col = BLACK;gra->_col = RED;}//左单旋else if (chi == par->_right && par == gra->_right){rotateL(gra);gra->_col = RED;par->_col = BLACK;}else{assert(false);}break;}else{assert(false);}}_root->_col = BLACK;return { Iterator(rem,_root),true };}

查找的逻辑比较简单，和插入找合适位置的逻辑相似，返回对应的迭代器，不存在则返回最后一个元素迭代器的下一个位置标识即可，这里也不展开实现了

删除的代码我们也不再展开了，我们在红黑树的介绍中介绍过删除的逻辑，还是比较复杂的，感兴趣的读者可以自行找其他资料查看

map封装

这里我们就可以分装map了

template<class K,class V>class Map{private:struct KOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};RBTree<K, pair<const K, V>, KOfT> map;public:typedef typename RBTree<K, pair<const K, V>, KOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, KOfT>::constIterator c_iterator;pair<iterator, bool> insert(const pair<K, V>& kv){return map.insert(kv);}iterator begin(){return map.begin();}iterator end(){return map.end();}c_iterator begin() const{return map.begin();}c_iterator end() const{return map.end();}};

我们在实现一个重载[]的方法

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

set封装

template<class K>class Set{private:struct KOfT{const K& operator()(const K& kv){return kv;}};RBTree<K, const K, KOfT> set;public:typedef typename RBTree<K, const K, KOfT>::Iterator iterator;typedef typename RBTree<K, const K, KOfT>::constIterator c_iterator;pair<iterator,bool> insert(const K& kv){return set.insert(kv);}iterator begin(){return set.begin();}iterator end(){return set.end();}c_iterator begin() const{return set.begin();}c_iterator end() const{return set.end;}};

结语

这里实现的代码还是非常简陋的，只是搭好了一个框架，后续还可以进行升级和加入新的逻辑，本文只是抛砖引玉，更复杂的代码和逻辑我们就不再展开了

以上便是今天的全部内容。如果有帮助到你，请给我一个免费的赞。

因为这对我很重要。

编程世界的小比特，希望与大家一起无限进步。

感谢阅读！


http://www.ppmy.cn/embedded/155671.html

相关文章

UnderTow服务器

UnderTow服务器

1.Undertow架构概述 Undertow是一个灵活的、高性能的Web服务器&#xff0c;它的设计理念是通过组合不同的组件来满足不同的应用需求。以下是对Undertow架构的详细分析&#xff1a; 1. 整体架构 Undertow服务器由三个主要部分组成&#xff1a; XNIO工作者实例&#xff1a;负责…
阅读更多...
速通Docker === 介绍与安装

速通Docker === 介绍与安装

目录 Docker介绍 Docker优势 Docker组件 Docker CLI (命令行接口) Docker Host (Docker 守护进程) 容器 (Container) 镜像 (Image) 仓库 (Registry) 关系总结 应用程序部署方式 传统部署 (Traditional Deployment) 虚拟化部署 (Virtualization Deployment) 容器部署…
阅读更多...
WPF实现动态四宫格布局

WPF实现动态四宫格布局

需求描述 我们要设计一个界面&#xff0c;用户可以通过 CheckBox 控制哪些图表显示。图表的数量是动态的&#xff0c;最多可以选择显示四个图表。如果显示一个图表&#xff0c;它会占满整个区域&#xff1b;如果显示两个图表&#xff0c;它们会水平排列&#xff1b;显示三个图…
阅读更多...
【C++】面试题整理（未完待续）

【C++】面试题整理（未完待续）

【C】面试题整理 文章目录 一、概述二、C基础2.1 - 指针在 32 位和 64 位系统中的长度2.2 - 数组和指针2.3 - 结构体对齐补齐2.4 - 头文件包含2.5 - 堆和栈的区别2.6 - 宏函数比较两个数值的大小2.7 - 冒泡排序2.8 - 菱形继承的内存布局2.9 - 继承重写2.10 - 如何禁止类在栈上分…
阅读更多...
Redis 中 TTL 的基本知识与禁用缓存键的实现策略（Java）

Redis 中 TTL 的基本知识与禁用缓存键的实现策略（Java）

目录 前言1. 基本知识2. Java代码 前言 &#x1f91f; 找工作&#xff0c;来万码优才&#xff1a;&#x1f449; #小程序://万码优才/r6rqmzDaXpYkJZF 单纯学习Redis可以看我前言的Java基本知识路线&#xff01;&#xff01; 对于Java的基本知识推荐阅读&#xff1a; java框架…
阅读更多...
PiliPalaX （ 第三方安卓哔哩哔哩）

PiliPalaX （ 第三方安卓哔哩哔哩）

PiliPalaX 是一款哔哩哔哩第三方客户端。使用 Flutter 开发&#xff0c;基于PiliPala原版基础上创作出来的X升级版&#xff0c;目前支持Android、IOS客户端。 应用特色 目前着重移动端(Android、iOS)和Pad端&#xff0c;暂时没有适配桌面端、手表端等 https://pan.quark.cn/s/…
阅读更多...
第九章：演示文稿软件PPT

第九章：演示文稿软件PPT

文章目录&#xff1a; 一&#xff1a;界面 1.介绍 2.选项卡 2.1 开始 2.2 插入 2.3 设计 2.4 切换 2.5 动画 2.6 放映 2.7 审阅 2.8 视图 2.9 音频工具 2.10 视频工具 二&#xff1a;基础 三&#xff1a;设计 1.静态 2.动态 四&#xff1a;放映 一&#xff1…
阅读更多...
软考信安22~网站安全需求分析与安全保护工程

软考信安22~网站安全需求分析与安全保护工程

1、网站安全威胁与需求分析 1.1、网站安全概念 网站安全主要是有关网站的机密性、完整性、可用性及可控性。 网站的机密性是指网站信息及相关数据不被授权查看或泄露。 网站的完整性是指网站的信息及数据不能非授权修改，网站服务不被劫持。 网站的可用性是指网站可以待续…
阅读更多...
最新文章

Copyright @ 2022~2023