自己做网站做淘宝联盟,手机端的网站首页该怎么做,短剧cps分销平台官网,网站开发开源架构目录 一、框架思考
三个问题
问题1的解决
问题2的解决#xff1a;
问题3的解决#xff1a;
二、泛型编程
1、仿函数的泛型编程
2、迭代器的泛型编程
3、typename#xff1a;
4、/--重载
三、原码
红黑树
map
set 一、框架思考
map和set都是使用红黑树底层
问题3的解决
二、泛型编程
1、仿函数的泛型编程
2、迭代器的泛型编程
3、typename
4、/--重载
三、原码
红黑树
map
set 一、框架思考
map和set都是使用红黑树底层要怎么实现同一个底层但是实现不同的功能呢
三个问题
1、map是pair模型而set是key模型 2、map和set的迭代器用法是一样的如何实现
3、插入时set和map插入的类型不同如何实现
我们是一个简单的实现而不是全部所以抓重点化繁为简 只关注和当前我么要实现功能有关系的部分其他的统统不关注
问题1的解决 RBTree的节点传的是一个模板
templateclass T
struct BRTreeNode
{BRTreeNodeT* _parent;BRTreeNodeT* _right;BRTreeNodeT* _left;T _data;Colour _col;BRTreeNode(const T data):_parent(nullptr), _right(nullptr), _left(nullptr), _data(data), _col(RED){}};
map传K,pairK,V set传K,K
我set要用的是key模型的BRTree所以传的是KK 我map要的是key-value模型的BRTree所以传的是KpairK,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 pairK, V kv){return kv.first;}};
红黑树部分的仿函数 KeyOfT kot;kot(data) 2、迭代器的泛型编程
set和map有各自的数据类型 但是器迭代器的形式是一样的 如何做到 迭代器实现实在红黑树部分实现的 将之设置为模板 传set就是se对应的迭代器 传map就是map对应的迭代器
set的迭代器 typedef typename BRTreeconst K, K, SetKeyOfT::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}
map的迭代器 typedef typename BRTreeK, pair K, V, MapKeyOfT::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}
红黑树的迭代器
//迭代器
//referrence :引用
templateclass T, class Ptr, class Ref//迭代器模板数据类型、指针类型、解引用
struct __RBTreeiterator
{typedef BRTreeNodeT Node;typedef __RBTreeiteratorT, 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
#includevector
#includeiostream
using namespace std;enum Colour
{BLACK,RED
};//node实例化只给一个T
templateclass T
struct BRTreeNode
{BRTreeNodeT* _parent;BRTreeNodeT* _right;BRTreeNodeT* _left;T _data;Colour _col;BRTreeNode(const T data):_parent(nullptr), _right(nullptr), _left(nullptr), _data(data), _col(RED){}};//迭代器
//referrence :引用
templateclass T, class Ptr, class Ref//迭代器模板数据类型、指针类型、解引用
struct __RBTreeiterator
{typedef BRTreeNodeT Node;typedef __RBTreeiteratorT, 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为这个对象指针}};templateclass K, class T, class KeyOfT
class BRTree
{typedef BRTreeNodeT Node;
public:typedef __RBTreeiteratorT, T*, TIterator;//提供迭代器接口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
#includeBRTree.h//对map的封装namespace myNameSpace
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public://插入bool insert(const pair K, V kv){return _t.Insert(kv);}//封装红黑树的迭代器typedef typename BRTreeK, 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(){/*mapint, int m;m.insert({1,1});m.insert({2,2});m.insert({3,1});m.insert({7,1});mapint,int::iterator it m.begin();while (it ! m.end()){cout it-first : it-second endl;it;}cout endl;*/mapstring, int m1;m1.insert({ hello,1});m1.insert({ world,2});m1.insert({ find,1});m1.insert({ peace,1});mapstring, int::iterator it1 m1.begin();while (it1 ! m1.end()){cout it1-first : it1-second endl;it1;}cout endl;}}
set
#pragma once
#includeBRTree.hnamespace myNameSpace {templateclass Kclass set {struct SetKeyOfT{const K operator()(const K key){return key;}};public:bool insert(const K key){return _t.Insert(key);}//对于红黑树的迭代器,需要实例化红黑树的迭代器//所以需要在红黑树的基础上封装迭代器typedef typename BRTreeconst K, K, SetKeyOfT::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}private:BRTreeconst K,K, SetKeyOfT _t;};void test_set(){setint s;s.insert(1);s.insert(2);s.insert(4);s.insert(7);s.insert(8);s.insert(9);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;}}
