C++进阶--使用红黑树封装map和set

很高兴和大家见面，给生活加点impetus！！开启今天的编程之路！！

前面我们实现了红黑树，今天我们使用红黑树来封装mymap和myset
作者：٩( ‘ω’ )و260
我的专栏：C++进阶，C++初阶，数据结构初阶，题海探骊，c语言
欢迎点赞，关注！！

这篇文章最后的总代码我会以文件形式上传，请我的资源中寻找

使用红黑树封装map和set

我们使用红黑树封装map和set，我们将从这几个步骤来实现：

1：实现红黑树
2：封装map和set的框架，解决KeyOfT
3：iterator
4：const_iterator
5：Key不支持修改的问题
6：operator[]

红黑树在上一个章节我们已经实现过了，一定要先学会如何实现红黑树，随后再来封装map和set
红黑树的实现

实现出复用红黑树框架，并支持insert

首先，map和set的底层是红黑树，map的key，value型，set是key型，要通过一个红黑树实现两种不同的数据结构，我们必须将已经实现好的红黑树实现为一个模版
那我们模版参数应该怎样给出呢？
我们总共需要给出三个模版参数，第一个是key，第二个是T，但三个是KeyOfT。

第一个参数的作用：目的是为了find/erase接口的使用
第二个参数的作用：表示结点里面存储的数据类型
第三个参数的作用：目的是获取一个数据

首先，这三个参数其实是套了一层壳，其实是陪map演的演的一出戏。
虽然set只有一个key，但是map的成员是pair，我们传递了一个模版参数T，上层传的是什么，下层结点里面存储的数据就是什么。而且，我find和erase都是直接传递的key，所以我们需要传递第一个模版参数，而且，红黑树其实也是二叉搜索树，遍历寻找位置也是需要按照二叉搜索树的规则来进行的，二叉搜索树我们是通过比较key，所以我们需要传递一个参数KeyOfT来获取key，set就比较直接，因为存储的数据是key，但是pair就不行了，必须比较key，库中pair的比较是first和second有一个小就是小。

接下来我们来实现整体的架构：
myset:

template<class K>
class set{struct SetOfT{const K& operator()(const K& key){return key}}
private:RBTree<k,k,SetOfT> _t;	
};

mymap:

template<class K,class V>
{struct MapOfT{const K&operator()(const pair<K,V>& kv){return kv.first;}}
private:RBTree<K,pair<K,V>,MapOfT> _t; 
}

我把这个仿函数给传递过去，目的是为了获取Key。
随后，我们RBTree的所有有关数据的比较都要实用这个仿函数来获取Key
RBTree:
这里我们重点写insert需要改变的，主要是伪代码。

enum Colour{RED,BLACK
}
template<class T>
struct RBTreeNode{T _data;BRTreeNode<T> _left = nullptr;BRTreeNode<T> _right = nullptr;BRTreeNode<T> _parent = nullptr;Colour _col;RBTreeNode(const T&data):_col(RED),_data(data){}
};template<class K,class T,class KeyOfT>
class RBTree{typedef RBTreeNode<T> Node;
public:bool Insert(const T&data){//_root为空时的处理KeyOfT kot;Node*cur =_root;Node* parent=nullptr;while(cur){if(kot(data)<kot(cur->_data)){parent=cur;cur=cur->left;}else if(kot(data)>kot(cur->_data)){parent=cur;cur=cur->_right;}] }//......//下列所有涉及T比较的代码，都要这样改，使用kot来获取key
};

这里我们通过仿函数实例化对象，通过对象调用operator来获取其中的数据。

为什么将仿函数写在上层而不写在红黑树中？
因为上层知道节点中应该存储的类型是什么，然后再加一个配套的仿函数即可
为什么需要两边都是用kot调用
因为必须始终保持key进行比较，pair中大小比较不满足需求，只能实现重载，而且map中是data和data比，find中是data和key比（所以有了第一个模版参数）
RBTree中第二个模版参数决定了底层是存key，还是pair。

支持iterator的实现

完成了基本的建构，我们对迭代器进行实现，RBTree和list中迭代器的实现也是高度相似的。
问题：迭代器应该如何实现++，–，迭代器基本的接口（==，！=，operator*，operator->，）
先来实现基本结构：

template<class T>
struct Iterator
{typedef RBTreeNode<T> Node;typedef template<T> Self;T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator==(Self& s){return _node==s._node;}bool operator!=(Self& s){return _node!=s._node;}
}

随后我们来实现++和- -的操作：
首先，我们需要只关注局部，不能关注全局。
我们要寻找a结点++之后的下一个结点，其实就是中序遍历之后a结点的下一个结点：（中序遍历：左根右）
核心：判断右子树是否为空
迭代器++时，如果it指向的结点的右子树不为空，代表当前结点已经访问完了，要访问下一个结点是右子树的中序第一个，一棵树中序第一个是最左结点，所以直接找右子树的最左结点即可

那么如果说我的右子树为空呢？右子树为空，说明此时这棵树我已经遍历完了，下一个结点肯定是这个结点的祖先

我们发现，如果cur是父亲的右孩子，说明cur结点遍历完了，我的父亲也遍历完了，需要parent和cur继续向上更新，那么什么时候结束呢？当我的孩子结点是父亲的左孩子的时候，应该停止循环。那么如果一直向上更新，cur肯定会到达根结点，此时parent为nullptr，也应该停止循环，说明此时cur为最右结点，整棵树都遍历完了。

我们来看代码实现：

Self& operator++()
{Node*cur=_node;if(cur->_right)//找最左结点{Node*minLeft=cur->_right;while(minLeft->_left){minLeft = minLeft->_left;}_node=minLeft;}else{//去祖先中继续寻找Node*parent=cur->_parent;while(parent&&cur==parent->_right){cur=parent;parent=parent->_parent;}_node=parent;}return *this;
}

接下来我们来实现operator- -，在实现operator- -之间，先来解决一个问题，begin（）和end（）迭代器应该表示什么位置呢？begin（）肯定表示中序遍历的位置的第一个位置，end（）表示中序遍历最后一个位置的下一个位置，那这个位置时哪里呢？
我们不妨想一想，当我们遍历到中序的最后一个位置的时候，迭代器再++，此时一直向上找祖先，由于整棵树都已经遍历完了，最后肯定cur到根节点，parent到nullptr，所以我们不妨设置end（）位置的迭代器的成员就是nullptr。

来看代码：
这个位置的代码肯定是红黑树部分的迭代器代码。

Iterator Begin()
{Node*cur=_root;while(cur&&cur->_left)//小心根原本就是空的情况{cur=cur->_left;}return Iterator(cur);//此时到达了最左结点
}
Iterator End()
{return Iterator(nullptr);
}

接下来我们来看operator- -，- -其实和++无本质区别，++的顺序是左根右，孩子是父亲的右，继续向上遍历找祖先，- -的顺序是右根左，孩子是父亲的左，则继续向上遍历找祖先
但是有一个特殊情况需要处理：就是如果一开始就是end()位置的话，我- -需要到达最后结点（即最后一个结点，此时我们需要先特殊处理一下）
因为特殊处理，我们需要一个红黑树的根结点，所以需要再传一个根结点，迭代器中除了封装一个_node,还需要封装一个_root，这个root是专门为了operator- -而设置的。
来看代码：

Self& operator--()
{if(_node==nullptr){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&&parent->_left==cur){cur=parent;parent=parent->_parent;}_node=parent;}return *this;
}

const迭代器

这个思路其实与list实现迭代器的一样，因为有const，所以需要添加：

	Const_Iterator Begin()const{Node* minLeft = _root;while (minLeft && minLeft->_left){minLeft = minLeft->_left;}return Const_Iterator(minLeft, _root);//这个位置一定要传递一个根结点，为operator--所用}Const_Iterator End()const{return Const_Iterator(nullptr, _root);//这个位置一定要传递一个根结点，为operator--所用}

为什么这里有两个参数了呢？因为前面operator- -的时候设置了一个根结点参数，所以上面非const版本也是需要跟着一起修改的。

Key不能被修改

const迭代器中，肯定是不能修改的，但是普通迭代器中，Key是可以修改的，但是我的需求是Key无法被修改，因为Key被修改的话，可能会改变红黑树的结构。所以我们在传递数据的时候，就需要对Key加上const修饰，这样就能够保证Key不被修改了。
来看代码：

class map{//成员函数+typedef
private:RBTree<K,pair<const,K>,MapOfT> _t;
}class set{//成员函数+typedef
private:RBTree<K,const K,MapOfT> _t;
}

这样就能够完成目的。

map支持[ ]

[]的作用：1：查找 2：修改 3：查找+修改 4：验证Key是否已经存在
[]的本质依靠Find，而是依靠Insert函数，而且返回值是pair<Inerator,bool>
所以这里我们需要对Insert函数进行修改，将返回值修改为pair<Iterator,bool>类型。
来看map中的代码：

V& operator[](const K&key)
{pair<iterator,bool> ret=_t.Insert({key,V()});//匿名对象调用默认构造函数初始化iterator it=ret.first;return it->second;//迭代器先调用operator->返回一个地址，随后->等价于*和点操作取出里面的second
}

结语

感谢大家阅读我的博客，不足之处欢迎指正，感谢大家的支持
逆水行舟，楫摧而志愈坚；破茧成蝶，翼湿而心更炽！！加油！！