【C++】如何仅仅使用一颗红黑树来封装map和set？(超详细！)-171主机测评

在这里插入图片描述

🎬 个人主页：MSTcheng · CSDN 🌱 代码仓库：MSTcheng · Gitee

🔥 精选专栏: 《C语言》《数据结构》《算法学习》《C++由浅入深》

💬座右铭：
路虽远行则将至，事虽难做则必成！

前言：在前面的文章中我们向大家介绍并模拟实现了红黑树，那么本篇文章就带着大家使用一棵红黑树来封装map和set。

文章目录

一、标准库中map和set的源码与框架分析
二、封装map和set
- 2.1封装map和set的框架，解决KeyOfT的问题
- 2.2实现普通迭代器(iterator)和const迭代器(const_iterator)
- 2.3实现map和set中Key不支持修改
- 2.4实现map的operator[]
三、完整代码&测试代码
四、总结

一、标准库中map和set的源码与框架分析

在这里插入图片描述通过上面的源码我们能够得出两个信息：

顺着库里面定义的map和set的类型，最终发现库里面的红黑树的第二个模板参数Value才是每个结点的数据类型，因为在后面定义结点的类型使用的就是第二个模板参数Value类型，所以这里的Value可以是set中的Key类型，也可以是map中的pair类型！！！

通过set中的select1st<value_type>和map中的select1st<value_type>可以发现这其实对应着红黑树的第二个模板参数KeyOfValue，而Value是结点实际的数据可能是set中的Key也可能是map中的pair，所以KeyOfValue顾名思义就是Value里面的Key；如果Value本来就是Key那么就直接提取Key；如果Value是pair那么就要提取pair里的first（类似一个仿函数）。(为什么要提取后面揭晓)

要注意一下：源码里面模板参数是用T代表value，而内部写的value_type不是我们我们日常key/value场景中说的value，源码中的value_type反而是红黑树结点中存储的真实的数据的类型。（但是我们自己封装就是用泛型参数T，而不使用value避免与key/value中的value弄混淆）

到这里可能还有人有疑问，rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型为什么库里面的红黑树还要传第一个模板参数Key呢？

在map和set中，find和erase时参数使用的都是key，因为无论查找还是删除我们都只找键(key)或删除键，而不会去查找或删除值(value)，所以第一个模板参数是传给find/erase等函数做形参的类型的。对于set而言两个参数都一样因为set内部存的就是key类型，而map就不一样了，map内部存的是pair对象，而find和ease的是Key对象！

那么我们现在就知道了库里面的红黑树，第一个模板参数Key是给find/erase等函数做形参类型的；第二个模板参数Value是底层结点的真实数据类型(Key/pair)；第三个模板参数KeyOfValue是从真实数据类型中提取Key的仿函数。封装一棵红黑树我们仅需要了解这些模板参数即可。

了解完了库里面红黑树的模板参数，下面我们就来自己封装一个红黑树使其既能做map的底层又能做set的底层！

二、封装map和set

封装一棵红黑树有6个步骤：

实现一棵红黑树

封装map和set的框架，解决KeyOfT (注意我们自己实现第二个模板参数就使用的是T而不是Value避免与key/value的value弄混淆)

实现普通迭代器(iterator)以及const迭代器 (const_iterator)

实现Key不支持修改

实现map的operator[]

第一步实现红黑树我们在前面的文章就已经实现过了，如果想看红黑树实现的请点击：【C++】为什么说红黑树更适合做map和set的底层？这篇文章能找到答案！所以下面我们按照步骤逐一来实现！

2.1封装map和set的框架，解决KeyOfT的问题

首先先来看看我们自己实现的框架：

1、结点的结构：

//使用一颗红黑树来封装map和set那么就不能写死成pair了要修改成泛型T
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};

下面贴一张图能让大家更好的区分二者的区别：

这里是引用

2、红黑树的结构：

//这里的模板参数Value改成了泛型T 因为一棵红黑树提供map和set的底层那么对于set存的就是k
//但对于map存的就是一个pair 另外还要增加一个仿函数，来提取pair中的key进行插入逻辑的比较
template<class k, class T,class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:

private:
Node* _root = nullptr;
};

第二个模板参数我们使用T类型，第三个模板参数我们也仿造库里面使用一个仿函数KeyOfT。

从插入函数中发现问题：为什么要实现一个KeyOfT的仿函数？

//注意我们插入的类型就是T类型了，因为T可能只是Key也可能是pair
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;

return true;
}

Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//============================
//看到这里其实问题就显而易见了
//cur是红黑树的一个结点，这里的cur如果是pair类型那么自然可以访问first
//如果cur是set中的Key类型，那么去访问first必然崩
//============================
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}

cur = new Node(data);
cur->_col = RED;

//===============================
//这里出现的问题与上面一样，parent也是红黑树的一个结点
//如果该课树是set，那么底层结点存的就是Key结构
//那么Key结构你去访问first必然崩溃
//===============================
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}

cur->_parent = parent;

while (parent && parent->_col == RED)
{
//……
}
_root->_col = BLACK;
return true;
}

针对上面的问题，我们就有必要实现一个仿函数，当红黑树存的是set就直接返回Key；当红黑树存的是map就返回pair中的Key。这样既能支持set的比较也能支持map的比较，这便是KeyOfT的核心功能所在！

下面我们就来解决这一问题：

首先要在Map.h和Set.h中定义仿函数：

1、在Set.h中

#include"RBTree.h"
//防止与库中定义的set有冲突，使用一个命名空间封装
namespace my_set
{
//set的类型就是Key类型
template<class k>
class set
{
//仿函数在红黑树的插入时set直接比较key即可
//所以重载一个operator()
struct SetKeyOfT
{
const k& operator()(const k& key)
{
return key;
}
};
public:
bool insert(const k& key)
{
//底层直接调用红黑树的插入即可
return _t.Insert(key);
}
private:
//注意第二个模板参数才是key-value结构的k
//第一个模板参数是查找时返回的结点类型，以及做find/erase等函数的形参
RBTree<k, k,SetKeyOfT> _t;
};

2、在Map.h中

#include"RBTree.h"
//避免与库里面冲突
namespace my_map
{
//map类型就是key-value结构了因为map存储的是pair对象
template<class k, class v>
class map
{
//仿函数在插入比较时用于提取map中pair里的key进行比较
//所以重载一个operator()
struct MapKeyOfT
{
const v& operator()(const pair<k, v>& kv)
{
//返回的是pair中的first也就是key
return kv.first;
}
};
public:
bool insert(const pair<k,v>&kv)
{
//直接调用底层红黑树的插入
return _t.Insert(kv);
}
private:
//第二个参数是pair类型，就是红黑树底层结点存的实际类型
RBTree<k, pair<k, v>, MapKeyOfT> _t;
};

其实通过Set.h和Map.h的传参不难发现，底层红黑树为什么第二个参数我们要选择T？因为在set.h和map.h中观察_t的类型我们不难发现：如果T是key那么整棵树就是set结构，如果T是pair那么整棵树就是map结构。

解决问题：改造底层红黑树的比较逻辑，凡是涉及用key比较的地方都要跟着改！

bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;

return true;
}
KeyOfT kot;//用仿函数定义一个kot对象
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{

//if (cur->_kv.first < kv.first)
if(kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
//else if (cur->_kv.first > kv.first)
else if(kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}

cur = new Node(data);
cur->_col = RED;

//if (parent->_kv.first < kv.first)
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}

cur->_parent = parent;

while (parent && parent->_col == RED)
{
//……
}
_root->_col = BLACK;
return true;
}

几个细节：

使用cur->data或parent->data取到的是key对象或pair对象，对于key对象经过kot之后得到的还是key，pair对象经过kot之后，得到的就是pair中的key！！！

new新结点的时候，传入的是data，红黑树结点中表示存储数据的变量。

find中也含有key的比较逻辑，这里不展示在后面完整的代码中展示！

2.2实现普通迭代器(iterator)和const迭代器(const_iterator)

iterator实现的大框架跟list的iterator思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的行为。
这里的难点是operator++和operator–的实现。之前使用部分，我们分析了，map和set的迭代器走的是中序遍历，左子树->根结点->右子树，那么begin()会返回中序第⼀个结点的迭代器。其他的重载*、->、！=、==均与链表部分的类似很好实现。所以我们现在就针对难点进行分析：

如何实现迭代器的++和–？

迭代器++的核心：就是不看全局，只看局部，只考虑当前中序局部要访问的下一个结点。这里又分两种情况：

迭代器++时，如果it指向的结点的右子树不为空，代表当前结点的左子树已经访问完了，要访问下一个结点是右子树的中序第一个，一棵树中序第一个是最左结点，所以直接找右子树的最左结点即可。

迭代器++时，如果it指向的结点的右子树为空，代表当前结点已经访问完了且当前结点所在的子树也访问完了，要访问的下⼀个结点在当前结点的祖先里面，所以要沿着当前结点到根的祖先路径向上找。在这里插入图片描述

上面说的是it节点的左右子树的情况，下面来看it节点是父亲parent的左子树还是右子树的情况：

如果当前结点是父亲的左，根据中序左子树->根结点->右子树，那么下⼀个访问的结点就是当前结点的父亲；如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。在这里插入图片描述

如果当前结点是父亲的右，根据中序左子树->根结点->右⼦树，当前当前结点所在的子树访问完了，当前结点所在父亲的子树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找到孩子是父亲左的那个祖先就是中序要问题的下⼀个结点。如下图：it指向15，15右为空，15是10的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个访问的结点就是18。在这里插入图片描述

那么end()如何来表示呢？

当it遍历到50这个结点的时候，如下图当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有父亲，没有找到孩⼦是父亲左的那个祖先，这时父亲为空了，那我们就把it中的结点指针置为nullptr，我们用nullptr去充当end()。

需要注意的是：stl源码中，红黑树增加了一个哨兵位头结点做为end()，这哨兵位头结点和根互为父亲，左指向最左结点，右指向最右结点。相比我们用nullptr作为end()，差别不⼤，他能实现的，我们也能实现。只是–end()判断到结点为空时，特殊处理⼀下，让迭代器结点指向最右结点。在这里插入图片描述

下面我们就给出所有实现的代码： 1、在RBTree.h中

//封装第二步，封装一个红黑树的迭代器
//为了方便修改模板参数将T& T* 改成两个模板参数Ref和Ptr
template <class T,class Ref,class Ptr>
struct TreeIterator
{
typedef RBTreeNode<T> Node;
typedef TreeIterator<T, Ref, Ptr> Self;
Node* _node;

//迭代器的默认构造加上一个根节点的构造operator–的时候会用到
TreeIterator(Node* node,Node* root)
:_node(node)
,_root(root)
{}

//T& operator*()
Ref operator*()
{
return _node->_data;
}

//T* operator->()
Ptr operator->()
{
//注意operator箭头拿到的是变量_data的地址
//_node->_data->再使用一个箭头访问才能拿到key或者pair中的key/value
return &_node->_data;
}

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

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

//封装迭代器最重要的一步就是封装operator++ 返回值返回的是一个迭代器
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 = parent;
parent = parent->_parent;
}
//情况三：跳出循环此时的右子节点不等于父亲节点或此时父亲节点为空，直接将父亲节点给给当前的_node 即跳到了祖先节点
_node = parent;
}
return *this;
}
Self& operator—()
{
if (_node == nullptr) // end()
{
// –end()，特殊处理，走到中序最后⼀个结点，整棵树的最右结点
Node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_node->_left)
{
// 左子树不为空，中序左子树最后⼀个
Node* rightMost = _node->_left;
while (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;
}

template<class k, class T,class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef TreeIterator<T, T&, T*> Iterator;
typedef TreeIterator<T, const T&,const T*> ConstIterator;

Iterator Begin()
{
//中序第一个左根右最左结点
Node* cur = _root;
while (cur && cur->_left)//当前结点不为空并且当前结点的左孩子不为空
{
cur = cur->_left;
}
//跳出循环当前cur结点的左孩子为空那么它就是最左结点即中序第一个

return Iterator(cur,_root);//
}

Iterator End()
{
return Iterator(nullptr,_root);;
}

ConstIterator Begin() const
{
//中序第一个左根右最左结点
Node* cur = _root;
while (cur && cur->_left)//当前结点不为空并且当前结点的左孩子不为空
{
cur = cur->_left;
}
//跳出循环当前cur结点的左孩子为空那么它就是最左结点即中序第一个

return ConstIterator(cur,_root);//
}

ConstIterator End() const
{
return ConstIterator(nullptr,_root);
}
//下面的插入函数略……
};

注意：迭代器–的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->左子树。

有几个细节需要注意：

细节一：在RBTree.h中迭代器类为什么要设计第二个模板参数Ref和第三个Ptr？实际上Ref和Ptr是由下面红黑树那个类来确定的，第二个第三个模板参数分别传的是T&，和T*，因为迭代器类中operator*返回的是红黑树节点数据的引用，而operator->返回的是红黑树节点数据的地址！

细节二：对于const迭代器，我们一定不是去让迭代器本身不能修改，而是让迭代器所指向的节点数据不能修改，所以const是加在模板参数里面修饰T&、T* ！！！

在Set.h中：

namespace my_set
{
template<class k>
class set
{

struct SetKeyOfT
{
const k& operator()(const k& key)
{
return key;
}
};

public:
//使用 typename 明确告诉编译器iterator是个类型
typedef typename RBTree<k, k, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<k, k, SetKeyOfT>::ConstIterator const_iterator;

//普通迭代器
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}

//非const对象可以调用普通版本和const版本
//const对象必须调用const版本的迭代器
//const迭代器
const_iterator cbegin() const
{
return _t.Begin();
}
const_iterator cend() const
{
return _t.End();
}
bool insert(const k& key)
{
return _t.Insert(key);
}
private:

RBTree<k, k,SetKeyOfT> _t;
};
};

3、在Map.h中

#include"RBTree.h"
namespace my_map
{
template<class k, class v>
class map
{
//仿函数在插入比较时用于提取map中pair里的key进行比较
//所以重载一个operator()
struct MapKeyOfT
{
const v& operator()(const pair<k, v>& kv)
{
return kv.first;
}
};
public:

typedef typename RBTree< k, pair< k, v>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree< k, pair< k, v>, MapKeyOfT>::ConstIterator const_iterator;

//普通迭代器
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}

//非const对象可以调用普通版本和const版本
//const对象必须调用const版本的迭代器
//const迭代器
const_iterator cbegin() const
{
return _t.Begin();
}

const_iterator cend() const
{
return _t.End();
}

bool insert(const pair<k,v>&kv)
{
return _t.Insert(kv);
}

private:
RBTree<k, pair<k, v>, MapKeyOfT> _t;
};
};

在Set.h和Map.h中也有一些细节需要注意：

细节一：Set.h和Map.h中的迭代器，typedef时需要加上typename声明在RBTree这个类域里面的Iterator是一个类型，如果声明那么编译器可能会以为是静态成员变量从而报错。

细节二：Set.h和Map.h中，我们所有定义的函数包括begin()，cbegin()，insert()函数底层都是通过_t对象(红黑树对象内部通过传参实例化成了一个set或map)来调用红黑树的Begin(),Insert()函数。

以上就完成了，普通迭代器iterator和const迭代器const_iterator的实现。

2.3实现map和set中Key不支持修改

想要实现map中Key不能被修改，那么我们在将红黑树实例化成map传参的时候就因该限制，pair里的key不能被修改，所以我们直接加上const即可，下面看代码：

#include"RBTree.h"
namespace my_map
{
template<class k, class v>
class map
{
//……
};
public:

//这里也需要加这样才能保证迭代器指向的节点中pair的key不能被修改但value可以被修改
typedef typename RBTree< k, pair< const k, v>, MapKeyOfT>::Iterator iterator;
//const迭代器无论是key还是value都不能被修改！
typedef typename RBTree< k, pair< const k, v>, MapKeyOfT>::ConstIterator

private:
//注意这里加了const 上面typedef处也要加
RBTree<k, pair<const k, v>, MapKeyOfT> _t;
};
};

注意：map是支持修改value，不要把value也给加上const了。

同样的set中的key也不支持修改，那我们也一样直接加上const

#include"RBTree.h"
namespace my_set
{
template<class k>
class set
{
//……
};

public:
//使用 typename 明确告诉编译器iterator是个类型
typedef typename RBTree<k, const k, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<k, const k, SetKeyOfT>::ConstIterator const_iterator;

private:
RBTree<k, const k,SetKeyOfT> _t;
};
};

2.4实现map的operator[]

还记得在前面介绍map和set的使用时，我们就说过map的方括号底层实际上是调用插入来实现的，因为插入的返回值是一个pair<iterator,bool>刚好有查找和修改的功能，所以我们只需要修改一下插入函数，然后底层调用插入函数即可。

在RBTree.h中

pair<Iterator,bool> Insert(const T& data)
{

if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;

//使用迭代器构造根节点，然后使用花括号隐式类型转化为一个pair类型
//因为返回值是一个pair类型所以我们的返回值也要构造出一个pair类型
return { Iterator(_root,_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 { Iterator(cur,_root),false };
}
}

cur = new Node(data);
//=============================
//提前保存一下cur避免后面旋转该节点发生变化
//因为后面要使用cur节点去构造迭代器
//=============================
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;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;

if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;

cur = grandfather;
parent = cur->_parent;
}
else
{

if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(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
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}

break;
}
}
}

_root->_col = BLACK;

//使用新节点去构造迭代器，然后再使用花括号走隐式类型转化成一个pair
return { Iterator(newnode,_root),true };
}

修改完成后接下来我们就可以在Map.h中去调用这个插入函数：

//===============================================
//实现map的方括号[]访问实际上内部直接调用插入即可
//在调用插入之前要改装insert的返回值将bool类型修改成一个pair类型
//pair<iterator,bool>
//===============================================
v& operator[](const k& key)//operato[]返回的是value类型
{
pair<iterator, bool> ret = insert({ key,v() });//调用v的默认构造是因为默认情况下插入为空
//ret.first拿到的是迭代器再使用->才能拿到value
return ret.first->second;
}

三、完整代码&测试代码

1、由于篇幅问题，想要获得完整代码的友友们请到我的代码仓库获取：获取完整代码请点击

2、测试代码：

#include<iostream>
using namespace std;
#include"Map.h"
#include"Set.h"

void test_set()
{
my_set::set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(2223);
s.insert(–2);
s.insert(0);
my_set::set<int>::const_iterator it = s.cbegin();
while (it != s.cend())
{
//*it = 1;
cout << *it << " ";
++it;
}
//cout << endl;
//cout << endl;
}
void test_map()
{
my_map::map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });

dict["left"] = "左边，剩余"; // 修改
dict["insert"] = "插入"; // 插入+修改
dict["string"]; // 插入

my_map::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;
}

int main()
{
test_set();
test_map();
return 0;
}

在这里插入图片描述

四、总结

以上就是所有的封装内容啦，如果在封装的过程中出些了一些问题，不要慌张，就看看每一步的细节上要注意的点。如果还是不行那么就参考我的代码，博客的代码也有可能笔误还请多多包含，！相信只要按照上面的步骤你也能封装出一个属于你自己的map和set！

MSTcheng 始终坚持用直观图解 + 实战代码，把复杂技术拆解得明明白白！
👁️ 【关注】看普通程序员如何用实用派思路搞定复杂需求
👍 【点赞】给 “不搞虚的” 技术分享多份认可
🔖 【收藏】把这些 “好用又好懂” 的干货技巧存进你的知识库
💬 【评论】来唠唠 —— 你踩过最 “离谱” 的技术坑是啥？
🔄 【转发】把实用技术干货分享给身边有需要的程序员伙伴
技术从无唯一解，让我们一起用最接地气的方式，写出最扎实的代码！ 🚀💻

能够看到这里的小伙伴已经打败95%的人了超棒的，为你点赞，休息一下吧！

在这里插入图片描述

【C++】如何仅仅使用一颗红黑树来封装map和set？(超详细！)

文章目录

一、标准库中map和set的源码与框架分析