【C++】从零开始map与set的封装

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

🌃🌃🌃🌃🌃🌃🌃🌃🌃
🌏🌏🌏🌏🌏🌏🌏🌏🌏

---

1 前言

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

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

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

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

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

AVL树增加了以下特性：

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

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

红黑树加入以下特性:

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

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

map与set大多数情况是用来检索的工具，我们底层使用红黑树来完成map与set的封装。
进行封装之前，我们先来实现一个非常重要的东西：迭代器

2 红黑树的迭代器

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

1. 迭代器的框架如何实现，才能满足泛型编程的需求？？
2. STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，这里为了方便就给nullptr。
3. 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:

1. 首先最底层的节点结构体只使用一个模版参数value，用来表明储存什么数据类型，上层的红黑树通过什么value就使用使用什么
2. 红黑树这层主要使用Key Value KeyOfValue:
   • KEY：表示键值的类型,在Findj函数里有大用处（利用Key值来寻找是否存在）！！！
   • Value:表示储存的数据类型
   • KeyOfValue：这是一个仿函数，用来从Value取出Key值。
3. 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的封装

实现了红黑树的改进，接下来就简单了！
在上层操作我们只需要调用对应的底层代码，给予对应的模版参数就好了！！！

1. map 要满足K V的模版参数的传入
2. map 要实现一个仿函数用来取出Key
3. map 类里要有一个底层红黑树类,传入对应的模版参数<K , pair<const K , V> , MapOfValue> (注意键值不可更改哦，所以使用pair<const K , V>)
4. 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 的封装

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

1. set 要满足K 的模版参数的传入
2. set 要实现一个仿函数用来取出Key
3. set 类里要有一个底层红黑树类,传入对应的模版参数<K , const K , MapOfValue> (注意键值不可更改哦，所以使用 const K )
4. 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♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！