红黑树底层封装map、set C++

一、框架思考

三个问题

问题1的解决

问题2的解决：

问题3的解决：

二、泛型编程

1、仿函数的泛型编程

2、迭代器的泛型编程

3、typename：

4、++/--重载

三、原码

红黑树

map

set

一、框架思考

map和set都是使用红黑树底层，要怎么实现同一个底层，但是实现不同的功能呢？

三个问题

1、map是pair模型，而set是key模型

2、map和set的迭代器用法是一样的，如何实现？

3、插入时，set和map插入的类型不同，如何实现？

我们是一个简单的实现，而不是全部，所以抓重点，化繁为简
只关注和当前我么要实现功能有关系的部分，其他的统统不关注

问题1的解决

RBTree的节点传的是一个模板

template<class T>
struct BRTreeNode
{BRTreeNode<T>* _parent;BRTreeNode<T>* _right;BRTreeNode<T>* _left;T _data;Colour _col;BRTreeNode(const T& data):_parent(nullptr), _right(nullptr), _left(nullptr), _data(data), _col(RED){}};

map传<K,pair<K,V>>
set传<K,K>

我set要用的是key模型的BRTree，所以传的是<K，K>
我map要的是key-value模型的BRTree，所以传的是<K，pair<K,V>>
对应的BRTree传对应的模板到Node，实现不同类型的Node节点

问题2的解决：

map和set底层都是红黑树，其行为都是一致的，问题在于节点数据类型的不同，所以，红黑树的底层迭代器实现都是一样的，设置为模板，因此和问题1的解决思路是一致的。

问题3的解决：

set和map的比较不一样
set的比较是直接key，而map的比较是用kv.first
不确定是map还是set，不能写死，怎么办？
可以写一个内部类的仿函数
这个仿函数，对于set返回的是其key值
对于map返回的是其kv.first值
仿函数是一个强大的功能，你想怎么实现就怎么实现

模板写成一样的，功能是一样的，但是不同的对象类具体实现不同的功能

具体解决请看以下的泛型编程过程：

二、泛型编程

1、仿函数的泛型编程

set和map的key值不一样
如何使用同一份红黑树实现不同的比较逻辑？
当对红黑树实例化时，多传一个参数，即仿函数
在红黑树底层使用一个模板仿函数
在各自的map和set写好各自的类，用于模板仿函数的实例化
这样，虽然在底层，仿函数的行为都是一致的
但是，因为模板参数不同，其返回值也就不同

set的仿函数：

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

map的仿函数：

		struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};

红黑树部分的仿函数

		KeyOfT kot;kot(data)

2、迭代器的泛型编程

set和map有各自的数据类型
但是器迭代器的形式是一样的
如何做到？
迭代器实现，实在红黑树部分实现的
将之设置为模板
传set，就是se对应的迭代器
传map，就是map对应的迭代器

set的迭代器：

	typedef typename BRTree<const K,  K, SetKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}

map的迭代器：

	typedef typename BRTree<K, pair< K, V>, MapKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return  _t.End();}

红黑树的迭代器：

//迭代器
//referrence :引用
template<class T, class Ptr, class Ref>//迭代器模板：数据类型、指针类型、解引用
struct __RBTreeiterator
{typedef BRTreeNode<T> Node;typedef __RBTreeiterator<T, Ptr, Ref> 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* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else//右孩子为空{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right)//当孩子作为父亲的左，这个父亲就是要访问的节点{cur = parent;parent = parent->_parent;}_node = parent;}return *this;//this为这个对象指针}};

一般的迭代器的功能：
解引用*
指针访问->
比较相等
++
--

3、typename：

在没有实例化的对象，访问其内嵌类型
会出现分不清楚的问题：
因为静态成员、内部类、内部成员的访问都可以使用类域的方式去访问
没有实例化，就不知道访问哪一个

在没有实例化模板的类对象去取器内嵌类型时，加一个typename
意义就是告诉编译器，等到实例化的时候再去找对应的内嵌类型

4、++/--重载

红黑树采用的是中序遍历
中序遍历，++返回的是当前节点中序遍历的下一个节点
顺序是：左，根、右
因此，需要分情况
如果当前节点有右孩子，那就是右孩子的最左节点

如果当前节点没有右孩子，那么说明自己这棵子树已经访问完毕
需要访问该子树的父亲，因为该子树是作为父亲的左孩子
按照中序遍历的思想，左子树访问完毕，接下来要访问的就是根

红黑树

#pragma once
#pragma once
#include<vector>
#include<iostream>
using namespace std;enum Colour
{BLACK,RED
};//node实例化，只给一个T
template<class T>
struct BRTreeNode
{BRTreeNode<T>* _parent;BRTreeNode<T>* _right;BRTreeNode<T>* _left;T _data;Colour _col;BRTreeNode(const T& data):_parent(nullptr), _right(nullptr), _left(nullptr), _data(data), _col(RED){}};//迭代器
//referrence :引用
template<class T, class Ptr, class Ref>//迭代器模板：数据类型、指针类型、解引用
struct __RBTreeiterator
{typedef BRTreeNode<T> Node;typedef __RBTreeiterator<T, Ptr, Ref> 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* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else//右孩子为空{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right)//当孩子作为父亲的左，这个父亲就是要访问的节点{cur = parent;parent = parent->_parent;}_node = parent;}return *this;//this为这个对象指针}};template<class K, class T, class KeyOfT>
class BRTree
{typedef BRTreeNode<T> Node;
public:typedef  __RBTreeiterator<T, T*, T&>Iterator;//提供迭代器接口Iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left)//如果为空，直接返回{leftMin = leftMin->_left;}//返回一个迭代器//return leftMin;单参数的构造函数支持隐式类型转换return Iterator(leftMin);}Iterator End(){//遍历，要访问到最大的值为止//一般end位置为空return Iterator(nullptr);}bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT kot;Node* cur = _root;Node* parent = nullptr;while (cur){//现在，不知道是k还是k-v模型//set访问的直接是key，而map访问的.first//所以，对应不同的返回值，仿函数解决if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else//找到相等key{return false;}}cur = new Node(data);cur->_col = RED;if (kot(data) < kot(parent->_data))//插入左{parent->_left = cur;}else //插入右{parent->_right = cur;}cur->_parent = parent;//插入之后，要进行颜色调整while (parent && parent->_col == RED)//如果为空/黑色节点，直接结束{//Node* grandfather = parent->_parent;if (parent == grandfather->_left)//p为左，u为右{Node* uncle = grandfather->_right;//如果叔叔存在，且为红色if (uncle && uncle->_col == RED){//修改颜色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//向上更新cur = grandfather;parent = cur->_parent;}else//叔叔不存在/叔叔存在且为黑色{if (cur == parent->_left){//		   g//	   p      u//  c//RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		   g//	   p      u//      c//RotateL(parent);//		   g//	   c      u//  p//RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//p为右，u为左{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){//		   g//	   u      p//					c//RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//		   g//	   u      p//          c//RotateR(parent);//		   g//	   u      c//  				p//RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}//右旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)//subLR可能为空{subLR->_parent = parent;}subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//注意修改顺序if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}//检查平衡bool isBalance(){if (_root->_col == RED){return false;}//找到任意一条路黑色节点个数Node* cur = _root;int refNum = 0;while (cur){if (cur->_col == BLACK){refNum++;}cur = cur->_left;}return Check(_root, 0, refNum);return 1;}void Inoder(){_Inoder(_root);cout << endl;}private:bool Check(Node* root, int blackNum, const int refNum){//到路径结束位置检查黑色节点if (root == nullptr){if (blackNum != refNum){cout << "黑色节点不相等" << endl;return false;}// << blackNum << endl;return true;}//检查红色节点if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "连续红节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}void _Inoder(const Node* root){if (root == nullptr){return;}_Inoder(root->_left);cout << root->_kv.first << ":" << _root->_kv.second << endl;_Inoder(root->_right);}private:Node* _root = nullptr;};

map

#pragma once
#include"BRTree.h"//对map的封装namespace myNameSpace
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://插入bool insert(const  pair <K, V>& kv){return _t.Insert(kv);}//封装红黑树的迭代器typedef typename BRTree<K, pair< K, V>, MapKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return  _t.End();}BRTree< K, pair <K, V>, MapKeyOfT> _t;};void test_map(){/*map<int, int> m;m.insert({1,1});m.insert({2,2});m.insert({3,1});m.insert({7,1});map<int,int>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;*/map<string, int> m1;m1.insert({ "hello",1});m1.insert({ "world",2});m1.insert({ "find",1});m1.insert({ "peace",1});map<string, int>::iterator it1 = m1.begin();while (it1 != m1.end()){cout << it1->first << ":" << it1->second << endl;++it1;}cout << endl;}}

set

#pragma once
#include"BRTree.h"namespace myNameSpace {template<class K>class set {struct  SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}//对于红黑树的迭代器,需要实例化红黑树的迭代器//所以需要在红黑树的基础上封装迭代器typedef typename BRTree<const K,  K, SetKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}private:BRTree<const K,K, SetKeyOfT> _t;};void test_set(){set<int> s;s.insert(1);s.insert(2);s.insert(4);s.insert(7);s.insert(8);s.insert(9);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}}