AI 助理
备案控制台
开发者社区 云原生 文章 正文

【C++进阶】七、使用红黑树对set和map进行封装

2023-04-20 189
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 目录前言一、改造红黑树1.1 红黑树迭代器相关1.2 红黑树接口相关二、set代码三、map代码

目录

前言

一、改造红黑树

1.1 红黑树迭代器相关

1.2 红黑树接口相关

二、set代码

三、map代码

前言

       set 是 K模型的容器，map 是 KV模型的容器，但是它们的底层实现都是红黑树实现，即用红黑树可以封装出 set和 map，之前的篇章已经讲过红黑树了，这里就不解释了。

       接下来对红黑树进行改造，用改造后的红黑树封装出 set 和 map

一、改造红黑树

使用的代码是之前篇章红黑树实现的代码，改造后红黑树的框架如下：

#pragma onceenumColour{
RED,
BLACK,
};
template<classT>structRBTreeNode{
//构造函数RBTreeNode(constT&data)
        :_data(data)
        ,_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_col(RED)
    {}
//成员变量T_data;
RBTreeNode<T>*_left;
RBTreeNode<T>*_right;
RBTreeNode<T>*_parent;
Colour_col;
};
template<classT, classRef, classPtr>struct__RBTreeIterator{
typedefRBTreeNode<T>Node;
typedef__RBTreeIterator<T, Ref, Ptr>Self;
typedef__RBTreeIterator<T, T&, T*>iterator;
//构造__RBTreeIterator(Node*node)
        :_node(node)
    {}
// 普通迭代器的时候，他是拷贝构造// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器__RBTreeIterator(constiterator&s)
        :_node(s._node)
    {}
Refoperator*()
    {
return_node->_data;
    }
Ptroperator->()
    {
return&_node->_data;
    }
booloperator!=(constSelf&s)const    {
return_node!=s._node;
    }
booloperator==(constSelf&s)const    {
return_node==s._node;
    }
Self&operator++()
    {
if (_node->_right)
        {
Node*min=_node->_right;
while (min->_left)
            {
min=min->_left;
            }
_node=min;
        }
else        {
Node*cur=_node;
Node*parent=cur->_parent;
while (parent&&cur==parent->_right)
            {
cur=cur->_parent;
parent=parent->_parent;
            }
_node=parent;
        }
return*this;
    }
Self&operator--()
    {
if (_node->_left)
        {
Node*max=_node->_left;
while (max->_right)
            {
max=max->_right;
            }
_node=max;
        }
else        {
Node*cur=_node;
Node*parent=cur->_parent;
while (parent&&cur==parent->_left)
            {
cur=cur->_parent;
parent=parent->_parent;
            }
_node=parent;
        }
return*this;
    }
//成员变量Node*_node;
};
template<classK, classT, classKeyOfT>classRBTree{
typedefRBTreeNode<T>Node;
public:
typedef__RBTreeIterator<T, T&, T*>iterator;
typedef__RBTreeIterator<T, constT&, constT*>const_iterator;
iteratorbegin()
    {
Node*left=_root;
while (left->_left)
        {
left=left->_left;
        }
returniterator(left);// 使用匿名对象构造返回    }
const_iteratorbegin()const    {
Node*left=_root;
while (left->_left)
        {
left=left->_left;
        }
returnconst_iterator(left);
    }
iteratorend()
    {
returniterator(nullptr);
    }
const_iteratorend()const    {
returnconst_iterator(nullptr);
    }
//插入pair<iterator, bool>Insert(constT&data)
    {}
//中序遍历voidInOrder()
    {
_InOrder(_root);
    }
//检查红黑树特性boolIsBalance()
    {}
private:
//检查每条路径的黑色节点是否相等 && 是否出现连续红色节点boolCheck(Node*root, intblackNum, intref)
    {}
void_InOrder(Node*root)
    {}
//左单旋voidRotateL(Node*parent)
    {}
//右单旋voidRotateR(Node*parent)
    {}
private:
Node*_root=nullptr;//缺省值};

代码过多就不贴完了，完整代码链接：

https://gitee.com/Maple_fylqh/code/blob/master/code_c++/Set_and_Map/Set_and_Map/RBTree.h

改造红黑树就是给红黑树增加迭代器相关的，这棵泛型的红黑树可以同时封装出set 和 map

1.1 红黑树迭代器相关

迭代器模板参数在 list 模拟实现已经有过解释，这里不解释了，模板参数 T 是红黑树存放数据的类型，下面解释

template<class T, class Ref, class Ptr>

       上面迭代器类只需提供构造函数即可， 拷贝构造和赋值不需要自己实现，默认生成的即可，当前迭代器赋值给另一个迭代器是不需要深拷贝的，浅拷贝就可以，拷贝构造也是；析构释放空间的事情不归迭代器类管理，迭代器类只需构建迭代器对象即可

上面红黑树迭代器实现的接口有：

//构造__RBTreeIterator(Node*node)
        :_node(node)
    {}
// 普通迭代器的时候，他是拷贝构造// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器__RBTreeIterator(constiterator&s)
        :_node(s._node)
    {}
//解引用，获取数据Refoperator*(){}
//返回数据的地址Ptroperator->(){}
//比较两个迭代器是否不相等booloperator!=(constSelf&s)const{}
//比较两个迭代器是否相等booloperator==(constSelf&s)const{}
//前置++Self&operator++(){}
//前置--Self&operator--(){}

说明一下，迭代器都是支持普通迭代器构造const迭代器

image.png

实现如下，这里它利用了构造函数和拷贝构造函数的特性，当传入的迭代器是普通迭代器时：参数类型与拷贝构造参数要求一致，它就是拷贝构造；当传入的的迭代器是 const迭代器，参数类型与拷贝构造函数不匹配，类型有差异，它就变成了构造函数

typedef__RBTreeIterator<T, T&, T*>iterator;
// 普通迭代器的时候，他是拷贝构造// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器__RBTreeIterator(constiterator&s)
    :_node(s._node)
{}

前置++ 和前置-- 是红黑树迭代器实现的重点

前置++

一个结点的正向迭代器进行 ++ 操作后，应该根据红黑树中序遍历的序列找到当前结点的下一个结点

如下图，传入第一个节点是1，迭代器++ 下一个节点是6，再次++ 节点为8，迭代器要达到这种效果才可以满足需求

image.png

思路：

  1. 传入一个节点，如果节点右不为空就先往右边走，找到右边节点最小的节点，该节点就是 ++ 的下一个节点
  2. 传入一个节点，如果节点的右子树为空，去找祖先，迭代依次往上走，找到孩子是父亲左的那个祖先节点 
  3. image.png

代码如下： 

Self&operator++()
{
if (_node->_right)//传入节点右不为空，找右边最小节点    {
Node*min=_node->_right;
while (min->_left)
        {
min=min->_left;
        }
_node=min;
    }
else)//传入节点为空    {
Node*cur=_node;
Node*parent=cur->_parent;
while (parent&&cur==parent->_right)
        {
cur=cur->_parent;
parent=parent->_parent;
        }
_node=parent;
    }
return*this;
}

前置--

一个结点的迭代器进行 -- 操作后，就是红黑树中序遍历找到的结点的前一个结点

如下图，比如传入第一个节点是27，迭代器-- 下一个节点是25，再次 -- 节点为22，迭代器要达到这种效果才可以满足需求

image.png

--的思路和 ++ 的思路类似，只不过是反过来找

思路：

  1. 传入一个节点，如果节点左不为空就先往左边走，找到左边节点最大的节点，该节点就是 -- 的下一个节点
  2. 传入一个节点，如果节点的左子树为空，去找祖先，迭代依次往上走，找到孩子是父亲右的那个祖先节点
  3. image.png

代码如下：

Self&operator--()
{
if (_node->_left)//传入节点左不为空就先往左边走，    {
Node*max=_node->_left;
while (max->_right)
        {
max=max->_right;
        }
_node=max;
    }
else//传入节点左为空    {
Node*cur=_node;
Node*parent=cur->_parent;
while (parent&&cur==parent->_left)
        {
cur=cur->_parent;
parent=parent->_parent;
        }
_node=parent;
    }
return*this;
}

其他就不介绍了

1.2 红黑树接口相关

template<classK, classT, classKeyOfT>classRBTree{
typedefRBTreeNode<T>Node;
public:
typedef__RBTreeIterator<T, T&, T*>iterator;
typedef__RBTreeIterator<T, constT&, constT*>const_iterator;
private:
Node*_root=nullptr;//缺省值};

说明一下模板参数，为了实现泛型RBTree：

  1. 红黑树第一个参数是 K(Key)，主要用于查找数据；
  2. 红黑树第二个模板参数 T ，可以识别是 map 还是 set，因为 set和 map传给 T的参数不一样，set 传的是 Key，map 传的是键值对 pair；
  3. 红黑树第三个参数是 KeyOfT，这是一个仿函数，由于红黑树中 T 存的可能是K，也可能是pair。那我们插入的时候该怎么比较结点的大小呢,对于set是没有问题的，直接可以用T比较，但是map就不行了，我们要取出pair的 first来进行比较
  4. image.png

二、set代码

#include "RBTree.h"namespacefy{
template<classK>classset    {
structSetKeyOfT        {
constK&operator()(constK&key)
            {
returnkey;
            }
        };
public:
typedeftypenameRBTree<K, K, SetKeyOfT>::const_iteratoriterator;
typedeftypenameRBTree<K, K, SetKeyOfT>::const_iteratorconst_iterator;
iteratorbegin()const        {
return_t.begin();
        }
iteratorend()const        {
return_t.end();
        }
pair<iterator, bool>insert(constK&key)
        {
pair<typenameRBTree<K, K, SetKeyOfT>::iterator, bool>ret=_t.Insert(key);
returnpair<iterator, bool>(ret.first, ret.second);
        }
private:
RBTree<K, K, SetKeyOfT>_t;
    };
voidTestSet()
    {
intarr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
set<int>s;
for (auto&e : arr)
        {
s.insert(e);
        }
set<int>::iteratorit=s.begin();
while (it!=s.end())
        {
cout<<*it<<" ";
++it;
        }
cout<<endl;
for (auto&e : s)
        {
cout<<e<<" ";
        }
cout<<endl;
    }
}

三、map代码

#include "RBTree.h"namespacefy{
template<classK, classV>classmap    {
structMapKeyOfT        {
constK&operator()(constpair<constK, V>&kv)
            {
returnkv.first;
            }
        };
public:
typedeftypenameRBTree<constK, pair<constK, V>, MapKeyOfT>::iteratoriterator;
typedeftypenameRBTree<constK, pair<constK, V>, MapKeyOfT>::const_iteratorconst_iterator;
iteratorbegin()
        {
return_t.begin();
        }
iteratorend()
        {
return_t.end();
        }
const_iteratorbegin()const        {
return_t.begin();
        }
const_iteratorend()const        {
return_t.end();
        }
pair<iterator, bool>insert(constpair<constK, V>&kv)
        {
return_t.Insert(kv);
        }
V&operator[](constK&key)
        {
pair<iterator, bool>ret=insert(make_pair(key, V()));
returnret.first->second;
        }
private:
RBTree<K, pair<constK, V>, MapKeyOfT>_t;
    };
voidTestMap()
    {
intarr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
map<int, int>m;
for (auto&e : arr)
        {
m.insert(make_pair(e, e));
        }
map<int, int>::iteratorit=m.begin();
while(it!=m.end())
        {
it->second++;
cout<<it->first<<"->"<<it->second<<endl;
++it;
        }
map<string, int>countMap;
stringstr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
for (auto&e : str)
        {
countMap[e]++;
        }
for (auto&kv : countMap)
        {
cout<<kv.first<<":"<<kv.second<<endl;
        }
    }
}

这篇文章写起来逻辑有点不通（难写）dog，主要是用来复习的

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

文章标签：
C++
容器
关键词：
C++红黑树
红黑树Set
红黑树Map
C++ map
C++红黑树map
枫叶先生_
目录
相关文章
凉凉心.
|
11天前
|
存储 JavaScript Java
（Python基础）新时代语言！一起学习Python吧！（四）：dict字典和set类型；切片类型、列表生成式；map和reduce迭代器；filter过滤函数、sorted排序函数；lambda函数
dict字典 Python内置了字典：dict的支持，dict全称dictionary，在其他语言中也称为map，使用键-值（key-value）存储，具有极快的查找速度。 我们可以通过声明JS对象一样的方式声明dict
凉凉心.
58 1
john散漫
|
3月前
|
存储 缓存 JavaScript
Set和Map有什么区别？
Set和Map有什么区别？
john散漫
291 1
陌陌谣
|
27天前
|
存储 缓存 监控
用 C++ 红黑树给公司电脑监控软件的日志快速排序的方法
本文介绍基于C++红黑树算法实现公司监控电脑软件的日志高效管理，利用其自平衡特性提升日志排序、检索与动态更新效率，并结合实际场景提出优化方向，增强系统性能与稳定性。
陌陌谣
56 4
码字猴儿
|
4月前
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些？
for...of循环在遍历Set和Map时的注意事项有哪些？
码字猴儿
275 121
hahaha无
|
4月前
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素。在unordered_set中，元素的值同时也是唯一地标识它的key。在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
hahaha无
196 0
hahaha无
|
4月前
|
编译器 C++ 容器
用一棵红黑树同时封装出map和set
再完成上面的代码后，我们的底层代码已经完成了，这时候已经是一个底层STL的红黑树了，已经已符合库里面的要求了，这时候我们是需要给他穿上对应的“衣服”，比如穿上set的“衣服”，那么这个穿上set的“衣服”，那么他就符合库里面set的要求了，同样map一样，这时候我们就需要实现set与map了。因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
hahaha无
55 0
hahaha无
|
4月前
|
存储 C++
c++ 红黑树（带头结点）（k，k型）
想必在看到这篇文章的时候，你一定是带着问题去搜索的，一定是对红黑树已经有了初步大致的认识，已经知道了红黑树的性质与普通红黑树的功能与如何代码实现，但是莫一天突然看到了带头结点的红黑树，肯定是对此有一些疑惑的，或者来说在代码的实现上自己存在着某些疑惑。那么话不多说，就先给出红黑树（带头结点）的完整实现代码。然后再给出相应的详细解释。
hahaha无
90 0
平凡程序猿~
|
8月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
185 0
hahaha无
|
4月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
109 0

热门文章

最新文章

  • 1
    【Golang】（3）条件判断与循环？切片和数组的关系？映射表与Map？三组关系傻傻分不清？本文带你了解基本的复杂类型与执行判断语句
  • 2
    应用程序无法正常启动（0xc0000005）？C++报错0xC0000005如何解决？使命召唤17频频出现闪退，错误代码0xC0000005（0x0）
  • 3
    Microsoft Visual Basic/C++ Runtime，Visual C++ 运行库合集（VCRedistPack）
  • 4
    C++异常详细介绍
  • 5
    C++STL底层原理：探秘标准模板库的内部机制
  • 6
    Java、Python、C++支持jenkins和SonarQube(全集)
  • 7
    大数相加（c/c++）
  • 8
    基本二叉树与排序二叉树（C++源码）
  • 9
    Java、Python、C++支持jenkins和SonarQube（一）
  • 10
    C++零拷贝网络编程实战：从理论到生产环境的性能优化之路
  • 1
    redis-学习笔记(Jedis set 简单命令)
    140
  • 2
    redis-学习笔记(set)
    85
  • 3
    redis-学习笔记(string , hash , list , set , zset 前置知识)
    128
  • 4
    黑马c++ STL部分 笔记(8) set/ multiset 容器
    100
  • 5
    Redis -- set集合
    124
  • 6
    数据结构-Java Map 和 Set-2
    92
  • 7
    数据结构-Java Map 和 Set-1
    100
  • 8
    实时计算 Flink版操作报错之往GREENPLUM 6 写数据，用postgresql-42.2.9.jar 报 ON CONFLICT (uuid) DO UPDATE SET 语法有问题。怎么解决
    555
  • 9
    【JAVA学习之路 | 进阶篇】Set及其实现类与常用方法
    155
  • 10
    【C++】红黑树模拟实现STL中的map与set
    125

    • 相关课程

    更多
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    阿里云无影云电脑免费使用_免费申请教程