秒懂C++之set、map的封装

红黑树的泛型编程

改变比较方式：仿函数

迭代器模拟实现

++运算符重载

begin/end

!=/==运算符重载

测试

const

Find

[ ] 运算符重载

全部代码

RBTree.h

Mymap.h

Myset.h

test.cpp

红黑树的泛型编程

既然我们要实现set,map的封装那肯定要用到我们前面所学的红黑树为底层~

不过set是k模型，map是kv模型，难道我们要专门写两份不同模型的红黑树供它们使用吗？

让我们来看看在源码中它们是如何解决这一问题的~

在set源码中底层红黑树也设置了两个参数~不过这两个参数其实都是Key没啥区别

而map源码中底层红黑树第一个参数为key，第二个参数为pair，这就有点奇怪了，红黑树设置kv模型第一个参数为pair就行了，为什么这里有两个参数？

这其实是一种泛型编程的写法，目的就是减少重复冗余代码。首先红黑树第一个参数统一为key，第二个参数是根据set与map传递的参数而变化~

如果set使用红黑树，那红黑树就是<k,k>模型，value值就是key~

如果是map使用红黑树，那么红黑树就是<k,pair<k,v>>模型，value值就是pair<k,v>~
enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};// set<k>->RBTree<K, K>
// map<k,pair<k,v>>->RBTree<K, pair<K, V>>
template<class K, class T>
class RBTree
{typedef RBTreeNode<T> Node;
public:private:Node* _root = nullptr;
};
#pragma once
//Myset.h
#include"RBTree.h"namespace lj
{template<class K>class set{private:RBTree<K, K> _t;};
}
#pragma once
//Mymap.h
#include"RBTree.h"namespace lj
{template<class K,class V>class map{private:RBTree<K,  pair<k,v>> _t;};
}

改变比较方式：仿函数

以下是源代码中pair的比较方式~但我们不想实现value的比较，我们只想实现key的比较~

其实我们也不用特意去修改运算符>,<,我们修改获取_data数据的方式就行了~

pair小于如果是比较key与value的话，那么我们在获取data的时候只让它拿到key就好了~

定义一个内部类，作用为set参数的data只能获取key，map参数的data只能获取key~

迭代器模拟实现

++运算符重载

当右子树为空时，it++有指向其父节点的，也有指向其爷爷节点的，只能说最终会指向其祖先节点的某一个~那我们要如何表示这个呢？

当右子树为空作为条件时，我们先看向节点15，作为其父节点的左子树访问完后就应该访问父节点了~应该二叉搜索树为中序遍历——左子树，根，右子树

我们再来看向节点6，作为其父节点1的右子树，当把节点6访问完也就意味着包括节点1在内的其所有子树都访问完了，即节点8的左子树访问完了，下一步就该访问节点8~

所以当其右子树为空时，我们就去找哪个祖先节点的孩子节点为左节点，就比如节点15，它是祖先节点的左节点吗？——是的，那么我们的下一个节点就是其父亲。

再看节点6，它是目前父节点的左孩子吗？——不是，那么继续向上遍历，节点1是其父节点8的左孩子吗？——是的，那么我们的下一个节点就是节点1的父亲~
template<class T>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T> Self;Node* _node;RBTreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){//如果其右子树不为空if (_node->_right){// 右子树的最左节点Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 一直找该节点恰好是父亲左节点的关系Node* cur = _node;Node* parent = cur->_parent;//只要孩子还是父亲右节点的关系，就一直循环继续找//特殊判断，当最后一个节点++时应该指向空while (parent&&cur == parent->_right){//向上寻找cur = parent;parent = cur->_parent;}//找到了，把父亲节点作为下一个节点_node = parent;}return *this;}
}；
关于封装迭代器（使得指针++自定义）不熟悉的友友可以去看这篇文章：秒懂C++之List-CSDN博客

begin/end

iterator begin(){// 求最左节点Node* subLeft = _root;//若为空树则返回空节点while (subLeft&&subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}iterator end(){return iterator(nullptr);}

!=/==运算符重载

	bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}

测试

当我们部署好迭代器后，开始来检验一下成果~

const

对const迭代器不了解的友友可以参考这篇文章：秒懂C++之List-CSDN博客

当前我们还面临一个问题，key是不支持修改的~而我们现在只能通过降低传参权限去限制~

其实我们也可以封装一个const类型的迭代器~

不过const迭代器了解即可，毕竟正常迭代器就够用了~

ps:map一般不需要const迭代器，因为它需要修改pair里面的value，而set只有key，所以不能被修改~

Find

iterator Find(const K& key){whok kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return iterator(cur);}}return end();}
这就是为什么我们红黑树第一个参数统一设置成key的意义，我们用Find函数单纯就是寻找key，如果用第二个参数的话从data里面还得挑出key反而麻烦~

当然啦，如果你就是想在第二个参数的data找也可以~

不影响~

[ ] 运算符重载

    pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}

要实现[ ] 运算符重载就必须得对insert的返回值进行修改~

全部代码

RBTree.h

//RBTree.h
#pragma once
#include<vector>
enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T, class Ptr, class Ref>
struct RBTreeIterator
{typedef RBTreeNode<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;}Self& operator++(){//如果其右子树不为空if (_node->_right){// 右子树的最左节点Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else{// 一直找该节点恰好是父亲左节点的关系Node* cur = _node;Node* parent = cur->_parent;//只要孩子还是父亲右节点的关系，就一直循环继续找//特殊判断，当最后一个节点++时应该指向空while (parent&&cur == parent->_right){//向上寻找cur = parent;parent = cur->_parent;}//找到了，把父亲节点作为下一个节点_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};// set->RBTree<K, K>
// map->RBTree<K, pair<K, V>>
template<class K, class T, class whok>
class RBTree
{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T, T*, T&> iterator;typedef RBTreeIterator<T, const T*, const T&> const_iterator;const_iterator begin() const{// 求最左节点Node* subLeft = _root;//若为空树则返回空节点while (subLeft && subLeft->_left){subLeft = subLeft->_left;}return const_iterator(subLeft);}iterator begin(){// 求最左节点Node* subLeft = _root;//若为空树则返回空节点while (subLeft&&subLeft->_left){subLeft = subLeft->_left;}return iterator(subLeft);}const_iterator end() const{return const_iterator(nullptr);}iterator end(){return iterator(nullptr);}iterator Find(const T& data){whok kot;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){cur = cur->_right;}else if (kot(cur->_data) > kot(data)){cur = cur->_left;}else{return iterator(cur);}}return end();}pair<iterator, bool>  Insert(const T& data){if (_root == nullptr){_root = new Node(data);//根节点为黑色_root->_col = BLACK;//return true;return make_pair(iterator(_root), true);}whok kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{//return false;return make_pair(iterator(cur), false);}}// 准备插入，节点为红色cur = new Node(data);//标记最开始准备插入的cur，避免cur在向上遍历时变色移动，这时候的迭代器虽然还是叫cur，但已经不是原来的节点了Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//若插入成功后其父节点为黑，那么并不会触发连续红色，不需要修改//若插入成功后其父节点为红，触发连续红色，需要修改while (parent && parent->_col == RED){//记录g节点Node* grandfather = parent->_parent;//记录u节点if (grandfather->_left == parent){Node* uncle = grandfather->_right;//开始分类情况//情况一:u节点存在且为红if (uncle && uncle->_col == RED){//p/g/u变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//把g当作cur继续处理cur = grandfather;parent = cur->_parent;}//情况二:u节点不存在或u节点存在且为黑else{//情况二需要按照旋转情况进行分类//右旋情况，以g为旋转点if (cur == parent->_left){//       g//    p     u// c //右旋RotateR(grandfather);//p/g节点变色parent->_col = BLACK;grandfather->_col = RED;}//左右旋，p为旋转点后以g为旋转点else if (cur == parent->_right){//       g//    p     u//		 c //左旋RotateL(parent);//右旋RotateR(grandfather);//cur/g节点变色cur->_col = BLACK;grandfather->_col = RED;}//旋转处理完毕，不用再向上处理，直接退出break;}}else{Node* uncle = grandfather->_left;//开始分类情况//情况一:u节点存在且为红if (uncle && uncle->_col == RED){//p/g/u变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//把g当作cur继续处理cur = grandfather;parent = cur->_parent;}//情况二:u节点不存在或u节点存在且为黑else{//情况二需要按照旋转情况进行分类//左旋情况，以g为旋转点if (cur == parent->_right){//       g//    u     p//			   c//左旋RotateL(grandfather);//p/g节点变色parent->_col = BLACK;grandfather->_col = RED;}//右左旋，p为旋转点后以g为旋转点else if (cur == parent->_left){//       g//    u     p//		 c //右旋RotateR(parent);//左旋RotateL(grandfather);//cur/g节点变色cur->_col = BLACK;grandfather->_col = RED;}//旋转处理完毕，不用再向上处理，直接退出break;}}}//插入调整结束后我们统一让根节点变为黑色_root->_col = BLACK;//插入成功~//return true;//把最开始指向插入节点的迭代器返回return make_pair(iterator(newnode), true);}void RotateL(Node* parent){//先完成左单旋基本规则//移动三个主要节点Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;//再更新_parentif (subRL){//为空就不用给了subRL->_parent = parent;}Node* ppnode = parent->_parent;parent->_parent = subR;//若subR左旋后成为根节点if (parent == _root){_root = subR;subR->_parent = nullptr;}//若subR左旋后不会成为根节点else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}void RotateR(Node* parent){//先完成右单旋基本规则//移动三个主要节点Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;//再更新_parentif (subLR){//为空就不用给了subLR->_parent = parent;}Node* ppnode = parent->_parent;parent->_parent = subL;//若subL右旋后成为根节点if (parent == _root){_root = subL;subL->_parent = nullptr;}//若subL右旋后不会成为根节点else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}bool Check(Node* cur,int RedBlackNum,int BlackNum){if (cur == nullptr){if (RedBlackNum != BlackNum){cout << "黑色节点不足" << endl;return false;}cout << BlackNum << endl;return true;}//检查是否存在连续的红色节点if (cur->_col == RED && cur->_parent->_col == RED){cout << cur->_kv.first << "存在连续的红色节点" << endl;return false;}if (cur->_col == BLACK){BlackNum++;}return Check(cur->_left,RedBlackNum, BlackNum)&& Check(cur->_right, RedBlackNum, BlackNum);}bool IsBalance(){	//检查根节点是否为黑色if (_root && _root->_col == RED)return false;//检查路径黑节点int RedBlackNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){RedBlackNum++;}cur = cur->_left;}return Check(_root, RedBlackNum, 0);}private:Node* _root = nullptr;
};

Mymap.h

#pragma once
//Mymap.h
#include"RBTree.h"namespace lj
{template<class K,class V>class map{struct mapk{const K& operator()(const pair<K, V>& kv){//封装一个只获取pair中key值的内部类return kv.first;}};public:typedef typename RBTree< K, pair<const K, V>, mapk>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, mapk>::const_iterator const_iterator;const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}iterator begin(){return _t.begin();}iterator end(){return _t.end();}iterator find(const K& key){return _t.Find(key);}/*bool insert(const pair<K, V>& kv){return _t.Insert(kv);}*/pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private://使用底层红黑树封装时：RBTree<K,  pair<const K,V>, mapk> _t;};void maptest1(){map<int, int> m;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){m.insert(make_pair(e, e));}map<int, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << " "<< it->second<<endl;++it;}cout << endl;}void maptest2(){set< int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}set<int>::iterator it = s.begin();while (it != s.end()){//*it += 100;if (it == s.find(1)){cout << "找到了" << endl;cout << *it << endl;break;}else{cout << "找不到" << endl;break;}//cout << *it << endl;++it;}cout << endl;}void maptest3(){string arr[] = { "哈哈", "嘻嘻", "嘿嘿", "呃呃", "呃呃", "嘻嘻","嘿嘿", "嘿嘿", "哈哈", "嘿嘿", "呃呃", "哈哈" };map<string, int> countMap;for (auto& e : arr){/*if (e == "ݮ"){int i = 0;}*/countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}

Myset.h

#pragma once
//Myset.h
#include"RBTree.h"namespace lj
{template<class K>class set{struct setk{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K,const K, setk>::iterator iterator;typedef typename RBTree<K, const K, setk>::const_iterator const_iterator;iterator begin(){return _t.begin();}const_iterator begin() const{return _t.begin();}iterator end(){return _t.end();}const_iterator end() const{return _t.end();}iterator find(const K& key){return _t.Find(key);}/*bool insert(const K& key){return _t.Insert(key);}*/pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private://使用底层红黑树封装时：RBTree<K, const K, setk> _t;};void settest1(){set< int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}set<int>::iterator it = s.begin();while (it != s.end()){//*it += 100;if (it == s.find(11)){cout << "找到了"<<endl;cout << *it << endl;break;}else{cout << "找不到" << endl;break;}//cout << *it << endl;++it;}cout << endl;}
}

test.cpp

//test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include <map>
#include <set>#include "MySet.h"
#include "Mymap.h "int main()
{//lj::maptest1();//lj::maptest2();lj::maptest3();//lj::settest1();return 0;
}