移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——13.mapset（模拟实现）

1.对红黑树进行改造

1.1treenode模板参数改变

之前构建treenode模板参数传的是class k,class v(set为k，k；map是k，v），现在直接用T代替

template<class T>  //这里直接传了T作为模板参数，T可能是pair<k,t>,也可能是k
struct RBTtreenode
{RBTtreenode<T>* _left;RBTtreenode<T>* _right;RBTtreenode<T>* _parent;//pair<K, V> kv;T data;color col;RBTtreenode(const T& _data):_left(nullptr), _right(nullptr), _parent(nullptr), data(_data), col(RED){}
};

 

2.构建红黑树的迭代器 

因为要构建const_iterator（不可修改内容） 和iterator（可修改内容）所以需要三个模板参数

//<T,T&,T*> iterator;//普通迭代器
//<T, const T&, const T*> const_iterator;//指向的东西不能改变

template<class T,class Ref,class Ptr>

 iterator内存的是node*类型的数据！！！！

2.1 重载operator*()   (set)

因为set传模板参数只传K，没有V，data类型是K，

所以用*直接取得data即可

Ref operator*()
{return _node->data;
}

 2.2 重载operator->()   (map)

因为map模板参数传的是K，pair<const K，T>,data类型是pair<const K，T>，

想取到K，则需要传回&data,再用->first取得K

Ptr operator->()
{return &_node->data;
}

 2.3operator++()与operator--()

 这里以operator++（）做解释：

分三种情况：

1.如果右子树不为空，则找到右子树的最左节点

2.//如果右子树为空，且cur是parent的右子树，则先parent回溯至parent->_parent,再_node变为parent
3.//如果右子树为空，且cur是parent的左子树，则_node变为parent

 

iterator& operator++()
{if (_node->_right){//如果右子树不为空，则找到右子树的最左节点node* cur = _node->_right;while (cur && cur->_left){cur = cur->_left;}_node = cur;}else{//如果右子树为空，且cur是parent的右子树，则先parent回溯至parent->_parent,再_node变为parent//如果右子树为空，且cur是parent的左子树，则_node变为parentnode* cur = _node;node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;
}

2.4.begin()&&end() 

iterator begin()
{node* flag = root;while (flag&&flag->_left)//flag可能为nullptr{flag = flag->_left;}return iterator(flag);
}iterator end()
{return iterator(nullptr); //end用nullptr去构造！！！！！！！！
}const_iterator begin() const
{node* flag = root;while (flag && flag->_left)//flag可能为nullptr{flag = flag->_left;}return const_iterator(flag);
}const_iterator end() const
{return const_iterator(nullptr); //end用nullptr去构造！！！！！！！！
}

3.set.h封装

https://cplusplus.com/reference/set/set/?kw=set

#include"rbt.h"
namespace zone
{template<class K>class set{public:struct setkeyoft //仿函数，用来取出红黑树节点data中的key{const K& operator()(const K& key){return key;}};//set这里的迭代器本质都是const_iterator，因为k要求无法修改typedef typename RBTtree<K, K, setkeyoft>::const_iterator iterator;//记得要使用typename告诉编译器RBTtree<K, K, setkeyoft>::iterator这个是类型，不是函数typedef typename RBTtree<K, K, setkeyoft>::const_iterator const_iterator;iterator begin()const{return it.begin();}iterator end()const{return it.end();}pair<iterator,bool> insert(const K& key){return it.insert(key);}void inorder(){it.inorder();}private:RBTtree<K,K,setkeyoft> it;};
}

3.1 仿函数setkeyoft

仿函数，用来取出红黑树节点data中的key，用于insert函数！！！！

3.2 iterator和const_iterator

//set这里的迭代器本质都是const_iterator，因为k要求无法修改
        typedef typename RBTtree<K, K, setkeyoft>::const_iterator iterator;
        typedef typename RBTtree<K, K, setkeyoft>::const_iterator const_iterator;

4.map.h封装 

https://cplusplus.com/reference/map/map/?kw=map

#include"rbt.h"
namespace zone
{template<class K,class T>class map{public:struct setkeyoft{const K& operator()(const pair<K, T>& key){return key.first;}};//map这里的迭代器则使用的是iterator，因为k要求无法修改，但v可以修改，所以可以直接初始化时用pair<const K, T>typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::iterator iterator;typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::const_iterator const_iterator;pair<iterator, bool> insert(const pair<K, T>& key){return it.insert(key);}T& operator[](const K& key){pair<iterator, bool>ret = insert(make_pair(key,T()));//insert返回一个pair，first是iterator，second是bool类型return ret.first->second;}iterator begin(){return it.begin();}iterator end(){return it.end();}void inorder(){it.inorder();}private:RBTtree<K,pair<const K,T>, setkeyoft> it;};
}

5.insert函数 ！！！！！！！

RBT.h里insert函数的返回值是 pair<node*, bool>

但封装过后的map.h,set.h里

pair<iterator,bool> insert(const K& key)
{return it.insert(key);
}

 返回值是pair<iterator,bool>

可见 pair<node*, bool>和pair<iterator(这里的iterator已经重命名了，本质是const_iteratir),bool>并不是同一类型，该如何解决呢？

 

 

1.如果T1和U类型一致，T2和V类型一致，那么就是拷贝构造！！！

2.如果不一致，也可以进行普通构造，前提是有可以用first来构建T1的函数！！！！！

回到刚才的问题：

可见 pair<node*, bool>和pair<iterator(这里的iterator已经重命名了，本质是const_iteratir),bool>并不是同一类型，该如何解决呢？

bool类型肯定可以用bool类型初始化，

iterator可以用node*进行初始化吗？

答案是可以的

treeiterator(node* it):_node(it)
{}

相当于使用了隐式类型转换

 6.杂谈

 

类比指针：

1.iterator 可修改指向的数据，也可改变自身

2.const iterator  可修改指向的数据，但不可改变自身

3.const_iterator 不可修改指向的数据，但能改变自身

 7.代码全览

RBT.h

#include<iostream>using namespace std;enum color
{RED,BLACK
};  //列举color的各种可能情况template<class T>  //这里直接传了T作为模板参数，T可能是pair<k,t>,也可能是k
struct RBTtreenode
{RBTtreenode<T>* _left;RBTtreenode<T>* _right;RBTtreenode<T>* _parent;//pair<K, V> kv;T data;color col;RBTtreenode(const T& _data):_left(nullptr), _right(nullptr), _parent(nullptr), data(_data), col(RED){}
};//<T,T&,T*> iterator;//普通迭代器
//<T, const T&, const T*> const_iterator;//指向的东西不能改变：const_iterator,本身不能改变：const iterator
template<class T,class Ref,class Ptr>
struct treeiterator
{typedef RBTtreenode<T> node;typedef treeiterator<T,Ref,Ptr> iterator;node* _node;treeiterator(node* it):_node(it){}Ref operator*(){return _node->data;}Ptr operator->(){return &_node->data;}iterator& operator++(){if (_node->_right){//如果右子树不为空，则找到右子树的最左节点node* cur = _node->_right;while (cur && cur->_left){cur = cur->_left;}_node = cur;}else{//如果右子树为空，且cur是parent的右子树，则先parent回溯至parent->_parent,再_node变为parent//如果右子树为空，且cur是parent的左子树，则_node变为parentnode* cur = _node;node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}iterator& operator--()   //和++反着来即可{if (_node->_left){node* cur = _node->_left;while (cur && cur->_right){cur = cur->_right;}_node = cur;}else{node* cur = _node;node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const iterator&s){return _node != s._node;}
};template<class K, class T,class keyoft>
class RBTtree
{
public:typedef treeiterator<T,T&,T*> iterator;typedef treeiterator<T, const T&, const T*> const_iterator;//指向的东西不能改变typedef RBTtreenode<T> node;iterator begin(){node* flag = root;while (flag&&flag->_left)//flag可能为nullptr{flag = flag->_left;}return iterator(flag);}iterator end(){return iterator(nullptr); //end用nullptr去构造！！！！！！！！}const_iterator begin() const{node* flag = root;while (flag && flag->_left)//flag可能为nullptr{flag = flag->_left;}return const_iterator(flag);}const_iterator end() const{return const_iterator(nullptr); //end用nullptr去构造！！！！！！！！}pair<node*, bool> insert(const T& _data)//！！！！！！！！！{if (root == nullptr){root = new node(_data);root->col = BLACK;//规定根必须是黑的return make_pair(root, true);}node* parent = nullptr; //比bst多了一个parentnode* cur = root;keyoft type;//取出data的K类型的数据while (cur){parent = cur;if (type(cur->data) < type(_data)) //这里取出key再进行比较{cur = cur->_right;}else if (type(cur->data) > type(_data)){cur = cur->_left;}else{return make_pair(cur,false);}}cur = new node(_data);cur->col = RED;//因为如果插入黑色的会使很多节点的一条路径上的黑色节点增多（相当于得罪了所有人），而插入红色则有可能只得罪父亲（如果父亲是红色的话）if (type(parent->data) < type(_data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;node* newnode = cur;//开始调整while (parent && parent->col == RED)//parent为黑不需要调整,如果cur变成root，parent就不存在退出循环{node* grandparent = parent->_parent;//祖父一定存在，因为只有根节点是没有祖父的，而根节点一定是黑色的if (parent == grandparent->_left){//      g//    p   unode* uncle = grandparent->_right;  //父亲在左则叔叔在右if (uncle && uncle->col == RED)     //情况一.如果叔叔存在且为红色{//变色parent->col = uncle->col = BLACK;grandparent->col = RED;//重置cur，parent，继续向上处理cur = grandparent;//变为祖父parent = cur->_parent;}else //叔叔不存在或为黑色，旋转加变色{//   g//  p// cif (cur == parent->_left)  //情况二.单旋{rotateR(grandparent);parent->col = BLACK;grandparent->col = RED;}//   g//  p//   celse      //情况三.cur==parent->_right,双旋{rotateL(parent);//经历一次左旋后变成情况二!!!!!!!!!!!(cur和parent换位置）rotateR(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent}}else{//      g//    u   p//node* uncle = grandparent->_left;  //父亲在右则叔叔在左if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;grandparent->col = RED;//cur = grandparent;parent = cur->_parent;}else{//    g//  u   p//        cif (cur == parent->_right){rotateL(grandparent);parent->col = BLACK;grandparent->col = RED;}else{//   g// u   p//    crotateR(parent);rotateL(grandparent);cur->col = BLACK;grandparent->col = RED;}break;//调整一次就结束了，所以经历过旋转后不需要重置cur，parent，grandparent}}}//1.如果parent和uncle都为RED，则可以一起变黑// 2.parent为黑不处理// 3.uncle为黑或不存在，parent为红，旋转+变色root->col = BLACK;//最后以防万一让根变为黑return make_pair(newnode, true);}void rotateL(node* parent)//左旋，（新节点插入到较高右子树的右侧）//   1.右右{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;subr->_left = parent;node* ppnode = parent->_parent;parent->_parent = subr;if (subrl) //subrl可能为空！！！！！！！{subrl->_parent = parent;}if (parent == root) //即如果parent->_parent==nullptr{root = subr;subr->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subr;}else if (ppnode->_right == parent){ppnode->_right = subr;}subr->_parent = ppnode;}}void rotateR(node* parent)//右旋，（新节点插入到较高左子树的左侧）//   2.左左{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr)               //sublr可能为空！！！！！！！sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent = subl;if (root == parent){root = subl;subl->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subl;}else if (ppnode->_right == parent){ppnode->_right = subl;}subl->_parent = ppnode;}}void inorder(){_inorder(root);}void _inorder(node* root){keyoft type;if (root == nullptr)return;_inorder(root->_left);cout << type(root->data)<< " ";_inorder(root->_right);}bool check(node* it, int blacknum, int flag){if (it == nullptr){if (blacknum == flag)return true;elsereturn false;}else if (it->col == RED && it->_parent->col == RED)//十分巧妙，因为孩子的情况有很多，但父亲不是红就是黑，所以判断父亲更合适return false;else if (it->col == BLACK)blacknum++;return check(it->_left, blacknum, flag) && check(it->_right, blacknum, flag);}bool isbalance(){return _isbalance(root);}bool _isbalance(node* root){if (root == nullptr)return true;else if (root->col == RED)return false;int blacknum = 0;int flag = 0;node* k = root;while (k){if (k->col == BLACK)flag++;k = k->_left;//这里十分巧妙，因为如果为红黑树，从某一节点到空的所有路径上的黑节点数量是一致的，所以可以先随便选一条路径，算出这一条路径上的黑节点数作为基准值，在由递归去和其他路径比较}return check(root, blacknum, flag);}private:node* root = nullptr;
};

myset.h

#include"rbt.h"
namespace zone
{template<class K>class set{public:struct setkeyoft //仿函数，用来取出红黑树节点data中的key{const K& operator()(const K& key){return key;}};//set这里的迭代器本质都是const_iterator，因为k要求无法修改typedef typename RBTtree<K, K, setkeyoft>::const_iterator iterator;//记得要使用typename告诉编译器RBTtree<K, K, setkeyoft>::iterator这个是类型，不是函数typedef typename RBTtree<K, K, setkeyoft>::const_iterator const_iterator;iterator begin()const{return it.begin();}iterator end()const{return it.end();}pair<iterator,bool> insert(const K& key){return it.insert(key);}void inorder(){it.inorder();}private:RBTtree<K,K,setkeyoft> it;};
}

mymap.h

#include"rbt.h"
namespace zone
{template<class K,class T>class map{public:struct setkeyoft{const K& operator()(const pair<K, T>& key){return key.first;}};//map这里的迭代器则使用的是iterator，因为k要求无法修改，但v可以修改，所以可以直接初始化时用pair<const K, T>typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::iterator iterator;typedef typename RBTtree<K, pair<const K, T>, setkeyoft>::const_iterator const_iterator;pair<iterator, bool> insert(const pair<K, T>& key){return it.insert(key);}T& operator[](const K& key){pair<iterator, bool>ret = insert(make_pair(key,T()));//insert返回一个pair，first是iterator，second是bool类型return ret.first->second;}iterator begin(){return it.begin();}iterator end(){return it.end();}void inorder(){it.inorder();}private:RBTtree<K,pair<const K,T>, setkeyoft> it;};
}

test.cpp

#include<iostream>
#include<vector>
#include<string>using namespace std;#include"myset.h"
#include"mymap.h"void test1()
{zone::set<int> it;it.insert(1);it.insert(3);it.insert(5);it.insert(2);it.insert(4);zone::set<int>::iterator arr = it.begin();while (arr!=it.end() ){cout << *arr << " ";++arr;}//it.inorder();}void test2()
{zone::map<string,string> it;it.insert(make_pair("sort","排序"));it.insert(make_pair("right", "右"));it.insert(make_pair("left", "左"));it.insert(make_pair("middle", "中"));zone::map<string,string>::iterator arr = it.begin();while (arr != it.end()){arr->second += 'x';//map的v可修改cout << arr->first << " ";++arr;}//it.inorder();}void test3()
{string arr[] = { "香蕉","苹果","西瓜","苹果","苹果","西瓜","苹果"};zone::map<string, int> it;for (auto e : arr){it[e]++;}for (auto k : it){++k.second;cout << k.first << ":" << k.second << endl;}
}
int main()
{test3();return 0;
}