送给大家一句话：

今日的事情，尽心、尽意、尽力去做了，无论成绩如何，都应该高高兴兴地上床恬睡。 – 三毛 《亲爱的三毛》

🌃🌃🌃🌃🌃🌃🌃🌃🌃

🌏🌏🌏🌏🌏🌏🌏🌏🌏

---

从零开始map与set的封装

1 前言2 红黑树的迭代器3 map与set的封装3.1 红黑树的改进3.2 map的封装3.3 set 的封装 4 总结Thanks♪(･ω･)ﾉ谢谢阅读！！！下一篇文章见！！！

1 前言

为了map与set 的封装，我们进行了非常充足的知识储备！！！

首先，为了了解map 与 set 的底层原理我们开始学习二叉搜索树,二叉搜索树在二叉树的基础上增添了：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值若它的右子树不为空，则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树注意通常二叉搜索树不会有相同的键值

这样可以在一定程度上满足高效搜索的需求，但是在极端的情况（单子树情况）其效率会下降到O(n)。因此就有了改进的二叉搜索树：AVL树和红黑树。他们都增加一些特性使其最大程度上近似平衡二叉树！

AVL 树 和 红黑树 都是在保持二叉搜索树基本性质的基础上，通过旋转和重新平衡等操作，确保树的高度保持在一个相对平衡的状态，从而保证了操作的时间复杂度始终为 O(logn)。它们的出现大大提高了二叉搜索树在实际应用中的性能和稳定性。

AVL树增加了以下特性：

它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1 / 0 / 1 )

在平衡因子超出要求就会进行旋转，旋转分为：右单旋 ，左单旋，左右双旋，右左双旋。

红黑树加入以下特性:

⚠️每个节点要么是红色，要么是黑色。⚠️根节点必须是黑色的。⚠️如果一个节点是红色的，则它的两个子节点必须是黑色的。⚠️对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。⚠️每个叶子节点都是黑色的。这里的叶子节点指的是为空的节点。

在不满足规则时也会进行旋转。但是旋转的频率比AVL树要少很多，红黑树是只是接近平衡，AVL树几乎就是平衡的！

map与set大多数情况是用来检索的工具，我们底层使用红黑树来完成map与set的封装。

进行封装之前，我们先来实现一个非常重要的东西：迭代器

2 红黑树的迭代器

迭代器的好处是可以方便遍历。如果想要给红黑树增加迭代器，需要考虑以前问题：

迭代器的框架如何实现，才能满足泛型编程的需求？？STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，这里为了方便就给nullptr。operator++()与operator–()要如何实现？这里的++和–要满足中序遍历的顺序，就不能简单的进行指针的移动了！

接下来我们来逐个实现。

首先我们来搭建一下迭代器的框架

// 迭代器//T 表示数据类型 Ref为引用 Ptr为指针template<class T , class Ref , class Ptr>struct _RBTreeIterator{ //为了方便调用，我们重命名一下typedef RBTreeNode<T> Node;typedef _RBTreeIterator<T, Ref, Ptr> Self;//内部是节点指针Node* _node;_RBTreeIterator(Node* node):_node(node){ }//两种指向方式Ref operator*(){ return _node->_data;}Ptr operator&(){ return &_node->_data;}bool operator!= (const Self& s){ return _node != s._node;}};

接下来我们来实现++和–的操作。

中序遍历的顺序是先遍历左边再遍历当前节点最后是右子树。所以在跌迭代器指向当前节点的时候，说明当前节点的左子树已经遍历完了，如果++，就要去找右边的最左节点。如果没有右子树，说明该节点以下的部分已经遍历完了，接下来要去向上进行，找到是祖先左边的节点：

//迭代器的++ 中序遍历的顺序Self& operator++(){ //首先，能访问到当前节点说明左子树的都已经访问过啦//所以就要分类讨论//如果右边有子树,就要去寻找右子树的最左节点if (_node->_right){ Node* cur = _node->_right;while (cur->_left){ cur = cur->_left;}_node = cur;}//如果右边没有子树了，说明该节点以下的子树都已遍历完，那么就要向上进行//找到祖先节点(注意祖先节点右边还没遍历)//此时也要进行分类讨论else{ Node* cur = _node;Node* parent = _node->_parent;//_node == parent->_right//说明parent的节点已经访问过了while (parent && cur == parent->_right){ cur = parent;parent = cur->_parent;}_node = parent;}return *this;}

–与++完全相反。

这样红黑树的迭代器就成功设置好了，我们的红黑树更加完美了！！！

实现了迭代器接下来我们就来实现map与set的封装

3 map与set的封装

3.1 红黑树的改进

我们先来看我们写的红黑树的节点代码：

// 节点结构体template<class K, class V>struct RBTreeNode{ RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;color _col;RBTreeNode(pair<K, V> kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(Red){ }};

可以发现，这个节点的设置是写死的，里面的数据就设置为了pair<K , V>。如果我们想实现set的封装还要在写一份红黑树代码，因为set的节点数据是K 。这样就太不优雅了！

为了更好实现map与set的封装，我们来看STL源码里是如何实现的吧！

可以看到STL源码中使用了非常巧妙的模版来支持我们上层的map与set:

首先最底层的节点结构体只使用一个模版参数value，用来表明储存什么数据类型，上层的红黑树通过什么value就使用使用什么红黑树这层主要使用Key Value KeyOfValue: KEY：表示键值的类型,在Findj函数里有大用处（利用Key值来寻找是否存在）！！！Value:表示储存的数据类型KeyOfValue：这是一个仿函数，用来从Value取出Key值。 map与set这层分别有K V 和 K分别要提供给红黑树Key Value KeyOfValue： map:就传给红黑树<K , pair<K,V> ...>set: 就传给红黑树<K , K ...>

这样实现了上层的map与set的模版参数并不一样，却可以使用同一个底层红黑树代码！！！十分巧妙！！！

我们按照源码改进我们的红黑树：

//-------------------------------------------//---------------- 红黑树实现 -----------------//-------------------------------------------//-------- 适配map 与 set 的进阶版本 -----------//-------------------------------------------#include<utility>enum color{ Black,Red};// 节点结构体// T在这里是 pair<key , value>template<class T>struct RBTreeNode{ RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;color _col;RBTreeNode(T data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(Red){ }};//适配map与set 的版本// 迭代器template<class T , class Ref , class Ptr>struct _RBTreeIterator{ typedef RBTreeNode<T> Node;typedef _RBTreeIterator<T, Ref, Ptr> Self;Node* _node;_RBTreeIterator(Node* node):_node(node){ }Ref operator*(){ return _node->_data;}Ptr operator&(){ return &_node->_data;}bool operator!= (const Self& s){ return _node != s._node;}//迭代器的++ 中序遍历的顺序Self& operator++(){ }Self& operator--(){ }};//K 为键值 T 为储存的结构（pair<K ,V>） KeyOfValue 是取出Key的方式template<class K, class T , class KeyOfValue>class RBTree{ public:typedef _RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeNode<T> Node;Iterator begin(){ Node* cur = _root;while (cur->_left){ cur = cur->_left;}return Iterator(cur);}Iterator end(){ return Iterator(nullptr);}//右单旋void RotateR(Node* parent){ }//左右双旋void RotateLR(Node* parent){ }//右左双旋void RotateRL(Node* parent){ }//------------------//返回需要比较的值KeyOfValue kot;//------------------//插入函数bool Insert(T data){ }private:void _IsBalance(Node* root , int num){ }bool Check(Node* root, int blackNum, const int refNum){ }void _InOrder(Node* cur){ }RBTreeNode<T>* _root = nullptr;};

注意插入函数等里面的比较方式统一改成类似kot(data) < kot(node.data)的样子哦！！！因为map与set的取出key的方式不同！！！

3.2 map的封装

实现了红黑树的改进，接下来就简单了！

在上层操作我们只需要调用对应的底层代码，给予对应的模版参数就好了！！！

map 要满足K V的模版参数的传入map 要实现一个仿函数用来取出Keymap 类里要有一个底层红黑树类,传入对应的模版参数<K , pair<const K , V> , MapOfValue> (注意键值不可更改哦，所以使用pair<const K , V>)map 类里要实例化一个迭代器。只需要提供基本的begin()与end()接口（直接调用红黑树的就可以），剩下++ -- ！+交给迭代器操作交给红黑树的迭代器。

//----------------------------------//---------- MAP 的实现 -----------//----------------------------------#include"RBTree.h"#include<utility>//层层递进,//map 上层要提供 key value 键值对//相应的要改造红黑树的代码 使其满足泛型编程template<class K , class V>class map { struct MapOfValue{ const K& operator()(const pair<const K, V>& kv){ return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapOfValue>::Iterator iterator;iterator begin(){ return _t.begin();}iterator end(){ return _t.end();}bool Insert(pair<const K, V> kv){ return _t.Insert(kv);}void InOrder(){ _t.InOrder();}private://底层是红黑树//需要提供对应的键值 储存结构 比较方式RBTree<K, pair<const K, V>, MapOfValue > _t;};

这样就实现了map 的封装！！！

3.3 set 的封装

在上层操作我们只需要调用对应的底层代码，给予对应的模版参数就好了！！！

set 要满足K 的模版参数的传入set 要实现一个仿函数用来取出Keyset 类里要有一个底层红黑树类,传入对应的模版参数<K , const K , MapOfValue> (注意键值不可更改哦，所以使用 const K )set 类里要实例化一个迭代器。只需要提供基本的begin()与end()接口（直接调用红黑树的就可以），剩下++ -- ！+交给迭代器操作交给红黑树的迭代器。

//----------------------------------//---------- SET 的实现 -----------//----------------------------------#include"RBTree.h"#include<utility>//层层递进,//set 上层要提供 key 键值//相应的要改造红黑树的代码 使其满足泛型编程template<class K>class set{ struct SetOfValue{ const K& operator()(const K& k){ return k;}};public:typedef typename RBTree<K, const K, SetOfValue>::Iterator iterator;iterator begin(){ return _t.begin();}iterator end(){ return _t.end();}bool Insert(K kv){ return _t.Insert(kv);}void InOrder(){ _t.InOrder();}private://底层是红黑树//需要提供对应的键值 储存结构 比较方式RBTree<K, K, SetOfValue > _t;};

这样就实现了set的封装！！！

4 总结

通过近一周的学习，我们终于将map和set从零建立起来了，这里不仅需要二叉搜索树的知识还需要AVL树和红黑树的使用！！！甚至还需要对于模版的更深理解！！！

我们写完了发现上层的map和set并没有使用多少代码，大部分是调用底层的代码，所以只有根基稳固才能走到更远！！！

map和set的封装是很值得回味的内容！！！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！