【c++】STL容器——使用红黑树模拟实现map和set（由浅入深逐步完善3w字详解）
小编个人主页详情<—请点击
小编个人gitee代码仓库<—请点击
c++系列专栏<—请点击
倘若命中无此运，孤身亦可登昆仑，送给屏幕面前的读者朋友们和小编自己!
目录
前言
【c++】红黑树的概念讲解与模拟实现、红黑树与AVL树的比对（2万字详解）——书接上文 详情请点击<——
本文由小编为大家介绍——【c++】STL容器——使用红黑树模拟实现map和set
在阅读本文前，由于本文map和set是基于红黑树的基础上封装出来的，所以请读者友友务必了解清楚红黑树的模拟实现，关于红黑树的模拟实现如果不熟悉的读者友友，请读者友友务必点击后方蓝字链接进行学习， 详情请点击<——
一、了解STL库中的map/set的底层
- map和set是通过红黑树封装实现的，我们首先学习一下STL库中是如何通过封装红黑树实现的map/set，下面的代码为了便于讲解，小编只截取部分进行讲解
- 观察下面代码，STL库中的set中封装了一个类模板红黑树rb_tree的对象rep_type，传入了key_type, value_type，这两个的类型都是Key类型的，奇怪，在小编前面文章的讲解中，set是key结构，只用存储一个key就可以，为什么这里传入了两个key，继续向下阅读，小编会在后文进行解读
template<classKey,classCompare= less<Key>,classAlloc= alloc>classset{public:// typedefs:typedef Key key_type;typedef Key value_type;private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing set}- 观察下面代码，STL库中的map中封装了一个类模板红黑树rb_tree的对象rep_type，传入了key_type, value_type，而key_type是key类型，value_type却是一个pair<const Key, T>类型的，按我们的预想value_type不应该是value(T)类型的吗？在小编之前文章的讲解中，讲解map是key_value结构的，map只需要存储key，value即可，为什么这里却传入了一个key和一个pair<const Key, T>进行实例化呢？继续向下阅读，小编会在后文进行解读
template<classKey,classT,classCompare= less<Key>,classAlloc= alloc>classmap{public:// typedefs:typedef Key key_type;typedef pair<const Key, T> value_type;private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing map}- 观察下面代码，STL库中关于红黑树rb_tree的实现，我们可以看到在struct类模板__rb_tree_node中是对于节点的定义，其中使用了模板参数Value去定义了节点中实际存储的内容，而没有使用key去定义，其实这是由于在STL库中设计的时候，在红黑树rb_tree的实现中使用第二个模板参数作为节点中实际存储的值
- 例如map传入<Key,pair<Key,Value>>，那么map中的红黑树类模板实例化出的红黑树中就使用传入红黑树的第二个模板参数pair<Key,Value>去定义节点中实际存储的内容，同样的set传入<Key,Key>，那么set中的红黑树类模板实例化出的红黑树中就使用传入红黑树的第二个模板参数Key去定义节点中实际存储的内容，那么这样的好处是什么呢？为什么map/set中还要多传入第一个模板参数Key呢？
- 其实STL库中是考虑了泛型模板，因为map和set在使用以及底层实现上都高度相似，如果不这样进行设计，那么我们就要写一份key_value结构的红黑树实现map，再写一份key结构的红黑树实现set，其中这两份红黑树的代码又高度吻合，在STL库中是不会这样设计的，它会考虑使用泛型模板，即让map和set使用同一份类模板，可以传入不同的模板参数，实例化出不同的类型
- 那么既然有了存储类型，为什么map/set中还要多传入第一个模板参数Key呢，其实这是为了例如find，erase这样的函数进行设计，find和erase是要使用key值进行查找或删除的，因为如果你仅仅有存储的类型那么对于set是可以使用存储的类型key去定义find和erase的函数参数，因为set的存储类型和key值都是key，但是对于map则不行，因为map中实际存储的是pair<key,value>，如果不显示传入Key，那么map的find和erase将会无法定义对应的函数参数，也就无法进行设计了，所以可以说第一个模板参数key是必须存在的，可以说是特定的为map进行设计，由于set也要和map共用一个类模板rb_tree，所以也要传入key
template<classKey,classValue,classKeyOfValue,classCompare,classAlloc= alloc>classrb_tree{protected:typedef __rb_tree_node<Value> rb_tree_node;typedef rb_tree_node* link_type;protected: link_type header;//定义的节点指针}template<classValue>struct__rb_tree_node:public__rb_tree_node_base{typedef __rb_tree_node<Value>* link_type; Value value_field;//节点中实际存储的值};二、红黑树的迭代器
由于本文是基于红黑树的模拟实现进行讲解的，所以小编模拟实现的红黑树的源代码小编会直接拿来进行使用，关于红黑树的源代码小编已经放在后方蓝字的文章中的第五点 详情请点击<——
- 我们知道map/set中支持了迭代器进行遍历，那么我们实现一下红黑树的迭代器，让map/set封装一下红黑树的迭代器就可以进行使用
- 原红黑树小编是设计的key_value结构，由于小编要将红黑树改进成可以让map/set都进行使用，所以就将红黑树的原模板参数template<typename K, typename V>其中的K表示key，V表示value，那么小编将原模板参数改进成template<typename K, typename T>，其中表示第一个模板参数是Key，为了和V进行区分，小编将第二个模板参数设计为T，表示类型type，即红黑树节点中存储的类型T，如果是map，那么第二个模板参数就对应为pair<key,value>，表示红黑树节点中实际存储pair<key,value>，如果是key，那么第二个模板参数就对应key，表示红黑树节点中实际存储key
- 同时由于红黑树的模板参数更改那么红黑树的节点的类型就要修改了，由于修改后红黑树的节点中存储的是T类型，那么节点的模板参数以及对应的一些节点类型就要更改，为了区分，在红黑树的节点中，那么我们存储的内容就使用T类型定义一个成员变量_data，对应更改如下，同时由于节点的类型已经被我们修改，所以在红黑树中对节点类型的typedef要更改为typedef RBTreeNode<T> Node;
template<typenameT>structRBTreeNode{ T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};template<typenameK,typenameT>classRBTree{typedef RBTreeNode<T> Node;public:RBTree():_root(nullptr){}private: Node* _root;};- 那么我们要模拟实现红黑树的普通迭代器__RBTree_itarator，由于迭代器的成员要经常被访问，所以我们就使用struct定义类模板__RBTree_itarator，类似的红黑树的迭代器和链表中的迭代器类似都是封装了一个节点的指针，使用迭代器去模拟指针的行为，关于链表的迭代器的讲解请点击后方蓝字链接 详情请点击<——
- 红黑树同样也是封装节点的指针，那么节点的使用需要使用到模板参数T，那么我们就给迭代器一个模板参数T，为了便于对节点进行使用，使用typedef将节点的类型RBTreeNode|重命名为Node，同时为了便于对迭代器类型的使用，使用typedef将迭代器的类型__RBTree_itarator重命名为Self，使用节点的指针Node*定义节点节点的指针_node
- 迭代器的构造函数，由于红黑树的迭代器中存储的是一个节点的指针_node，那么我们就在构造函数的参数中接收一个节点的指针node在初始化列表中完成对红黑树迭代器中节点的指针_node的初始化即可
- 运算符重载函数operator*，那么直接使用节点的指针访问节点中存储的内容_data，返回即可，返回值是T&，由于节点中存储的内容_data在出了这个函数仍然存在，所以我们可以直接返回类型的引用
- 运算符重载函数operator->，那么先使用节点的指针取出节点中存储的内容_data，接下来我们使用取地址操作符&即可取出节点中存储内容_data的地址了，即存储内容的指针，返回即可，返回值是存储内容的指针T*
- 运算符重载函数operator!=，那么接收迭代器即可，由于我们不修改，所以使用const修饰迭代器，由于迭代器出了函数仍然存在，所以我们可以使用引用接收，那么比较迭代器是否不想等，那么比较迭代器中节点的指针使用不想等即可完成比较
- 运算符重载函数operator++，原理如下，当++完成之后，由于迭代器++之后还是一个迭代器，所以运算符重载函数++的返回值应该还是迭代器，并且由于迭代器出了函数仍然存在，所以返回值的类型设定为迭代器的引用，此时this指针指向的就是当前++之后的迭代器，返回this指针的解引用即可
11. 运算符重载函数operator- -，原理如下
template<typenameT>struct__RBTree_itarator{typedef RBTreeNode<T> Node;typedef __RBTree_itarator<T> Self; Node* _node;__RBTree_itarator(Node* node):_node(node){} T&operator*(){return _node->_data;} T*operator->(){return&_node->_data;}booloperator!=(const Self& it){return _node != it._node;} Self&operator--(){ Node* cur = _node; Node* parent = cur->_parent;if(cur->_left){ Node* LeftMax = cur->_left;while(LeftMax->_right){ LeftMax = LeftMax->_right;} _node = LeftMax;}else{while(parent && cur == parent->_left){ cur = parent; parent = parent->_parent;} _node = parent;}return*this;} Self&operator++(){ Node* cur = _node; Node* parent = cur->_parent;if(cur->_right){ Node* RightMin = cur->_right;while(RightMin->_left){ RightMin = RightMin->_left;} _node = RightMin;}else{while(parent && cur == parent->_right){ cur = parent; parent = parent->_parent;} _node = parent;}return*this;}};- 那么此时我们在红黑树中，我们对迭代器的类型__RBTree_itarator重命名一下便于书写，并且编写出begin，end即可，关于begin和end的逻辑在运算符重载函数operator++的原理中已经进行讲解了，这里小编不再过多赘述
typedef __RBTree_itarator<T> iterator; iterator begin(){ Node* cur = _root;while(cur->_left){ cur = cur->_left;}returniterator(cur);} iterator end(){returniterator(nullptr);}三、红黑树的插入
- 红黑树的未改造之前插入进行查找位置的时候，由于我们之前模拟实现的红黑树是key_value结构，那么查找的时候是采用的kv.first和cur->_kv.first找出key值进行比较的找出应该插入的位置cur和其对应的parent，但是这里我们不能这样进行比较了因为这里存储的内容我们采用了_data，我们并不能知道_data中的内容是一个key还是一个pair<key,value>，此时的插入我们就没有办法进行找到key值进行比较找到应该插入的位置cur和其对应的parent，此时我们应该如何办呢？
- 我们在红黑树内部不知道，但是上层封装红黑树的map和set知道啊，map知道红黑树节点存储的内容是pair<key,value>，set知道红黑树节点存储的内容是key，因为map/set给红黑树类模板传入不同的类型，红黑树类模板会实例化出节点中存储内容不同的红黑树，并且此时我们观察下面STL库里的红黑树的实现，第三个模板参数是KeyOfValue，即对应就是取出节点中存储内容的key值
template<classKey,classValue,classKeyOfValue,classCompare,classAlloc= alloc>classrb_tree{protected:typedef __rb_tree_node<Value> rb_tree_node;typedef rb_tree_node* link_type;protected: link_type header;//定义的节点指针}template<classValue>struct__rb_tree_node:public__rb_tree_node_base{typedef __rb_tree_node<Value>* link_type; Value value_field;//节点中实际存储的值};- 注意由于小编认为STL库里的这个Value容易混淆，这个库里的Value是红黑树节点中实际存储内容的类型，这里小编使用T进行替代，那么第三个模板参数使用KeyOfT进行替代，这个KeyOfT其实是一个仿函数即类模板，我们使用这个类模板定义出一个对象，即仿函数对象，仿函数KeyOfT中有重载的operator()，可以让仿函数对象像函数一样使用，关于map/set如何实现这个仿函数的后文小编会进行讲解，这里我们只需要知道如何使用即可，那么使用仿函数我们就可以取出节点中存储的内容_data中的key值，那么此时进行比较，就可以实现适配map/set的红黑树的插入接口，左单旋和右单旋保持不变即可，关于左单旋和右单旋，小编已经放到后面蓝色链接中了 详情请点击<——
template<typenameK,typenameT,typenameKeyOfT>classRBTree{public:boolInsert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returntrue;}else{ Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(data)>kot(cur->_data)){ parent = cur; cur = cur->_right;}elseif(kot(data)<kot(cur->_data)){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(data); cur->_col = RED; cur->_parent = parent;if(kot(cur->_data)>kot(parent->_data)){ parent->_right = cur;}else{ parent->_left = cur;}while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; _root->_col = BLACK;}else{if(cur == parent->_left){RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else//cur = parent->_right{RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else//parent == grandfather->_right{ Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; _root->_col = BLACK;}else{if(cur == parent->_right){RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else//cur = parent->_left{RotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}}returntrue;}}private: Node* _root;};四、map/set的封装
set的封装
- 由于我们的set会跟STL库里的set命名冲突，所以将我们模拟实现的set放到一个命名空间中，那么set只需要一个K（key）作为模板参数即可
- 那么我们首先写出set中的仿函数SetKeyOfT，那么接下来写operator()，我们知道set中的红黑树类模板实例化出的红黑树中存储的内容_data就是key，所以这里我们的仿函数接收到data后直接返回data即可，并且由于data已经存在所以我们返回K引用即可，由于我们set中的key值不能修改所以我们返回值的类型要加const进行修改
- 那么接下来我们就给红黑树类模板传入参数实例化出一个存储key的红黑树_t即可
- 迭代器，我们取出红黑树中的普通迭代器iterator，这里有一点细节需要注意，由于红黑树是一个类，那么我们使用::取出的iterator有可能是内嵌类型，即内部类，被typedef的类型，也有可能是静态成员变量，那么此时编译器在编译检查语法错误的时候就会报错，因为它无法确定我们取出的iterator究竟是类型还是变量，如果是如果是被typedef的类型，那么没有问题，但是如果是静态成员变量的话会这里我们使用typedef会有语法错误，即使用变量重命名了一个类型，此时我们应该添加一个typename告诉编译器这里是一个类型，进行语法检查的时候先不要报错，等到模板实例化了之后再去类中找这个iterator，那么我们使用typedef将红黑树中的普通迭代器iterator重命名为iterator即可，那么此时我们就可以在set中使用iterator了
- 接下来编写begin，end即可，那么就是在该函数中调用底层红黑树的begin和end进行返回即可实现
- 插入，set的插入同样是调用红黑树的插入实现
#pragmaonce#include"RBTree.h"namespace wzx {template<typenameK>classset{private:structSetKeyOfT{const K&operator()(const K& data){return data;}};public:typedeftypenameRBTree<K, K, SetKeyOfT>::iterator iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();}boolInsert(const K& key){return _t.Insert(key);}private: RBTree<K, K, SetKeyOfT> _t;};}map的封装
- map是key_value结构，那么就需要对应的模板参数K，V，同样的我们模拟实现的map由于会和STL库中的map命名冲突，所以需要放到我们自己的命名空间中
- 那么接下来就需要实现仿函数MapKeyOfT，我们知道接收的参数是一个pair<K,V>类型的，那么使用pair<K,V>类型的kv接收后，我们取出kv中的第一个first，first对应就为key，由于key不能修改，所以我们的返回值要加const修饰，由于key出了函数仍然存在，所以我们取出kv的first返回const引用即可
- 那么接下来我们就给红黑树类模板传入参数实例化出一个存储key的红黑树_t即可
- 封装红黑树的迭代器，插入，以及迭代器的重命名和set都类似，这里小编就不过多赘述了
#pragmaonce#include"RBTree.h"namespace wzx {template<typenameK,typenameV>classmap{private:structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:typedeftypenameRBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();}boolInsert(const pair<K, V> kv){return _t.Insert(kv);}private: RBTree<K, pair<K, V>, MapKeyOfT> _t;};五、测试
测试一
- 我们使用如下代码进行测试我们编写的初步的红黑树和map和set
#include<iostream>#include"MyMap.h"#include"MySet.h"usingnamespace std;intmain(){ wzx::set<int> s; s.Insert(5); s.Insert(2); s.Insert(9); s.Insert(1); wzx::set<int>::iterator it = s.begin();while(it != s.end()){ cout <<*it <<' ';++it;} cout << endl << endl; wzx::map<int,int> m; m.Insert(make_pair(3,3)); m.Insert(make_pair(1,1)); m.Insert(make_pair(8,8)); m.Insert(make_pair(6,6)); wzx::map<int,int>::iterator mit = m.begin();while(mit != m.end()){ cout << mit->first <<':'<< mit->second << endl;++mit;} cout << endl;return0;}运行结果如下，可以运行出来
测试二
- 我们知道map中的key值（对应pair中的first）不可以修改，value值（对应pair中的second）可以修改，同时set中的key不能修改
- 我们使用如下代码测试
#include<iostream>#include"MyMap.h"#include"MySet.h"usingnamespace std;intmain(){ wzx::set<int> s; s.Insert(5); s.Insert(2); s.Insert(9); s.Insert(1); wzx::set<int>::iterator it = s.begin();while(it != s.end()){(*it)++; cout <<*it <<' ';++it;} cout << endl << endl; wzx::map<int,int> m; m.Insert(make_pair(6,6)); m.Insert(make_pair(1,1)); m.Insert(make_pair(8,8)); m.Insert(make_pair(3,3)); wzx::map<int,int>::iterator mit = m.begin();while(mit != m.end()){ mit->first++; mit->second++; cout << mit->first <<':'<< mit->second << endl;++mit;} cout << endl;return0;}运行结果如下
小编实现的map/set不符合STL库中的要求，STL库中要求map中的key值（对应pair中的first）不可以修改，value值（对应pair中的second）可以修改，同时set中的key不能修改小编实现的map可以对key进行修改，set中的key可以进行修改，这两点不符合STL库中的要求，那么我们应该如何做才能限制map中的key不被修改，同时又能让map中的value可以被修改，让set中的key不能被修改呢？
六、学习STL库中的实现
set如何保证key不被修改
- 上图是小编截取的库里实现的set的迭代器，普通迭代器是由const迭代器重命名来的，这里由于普通迭代器是类模板，那么在使用typedef对ret_type::const_iterator进行重命名的时候要使用typename声明ret_type::const_iterator是类型而不是变量
- multiset对key不进行修改的限制方式同set
set中遍历访问key需要使用到迭代器，set的const迭代器不能修改ser中存储的内容key，而set的普通迭代器是由const迭代器转换而来的，所以普通迭代器也不能修改key
map如何保证key不被修改
- map中是通过给键值对pair的成员变量key的类型加const进行修饰，修饰后不能对key进行修改，同时保证了value的类型不加const修饰，不加const修饰后value可以修改
- 在map中不可以采取上述类似于set中让普通迭代器由const迭代器封装转换的形式保证key不被修改，因为虽然这样真的保证了key不被修改，但是同时value也被限制不能修改了，但是map中的性质要求value可以修改，所以不能采取类似于set的方式进行限制key
- multimap不对key进行修改的限制方式同map
八、set的改进
在set中采取的措施是使用红黑树的const迭代器转换为普通迭代器，那么我们就需要给红黑树中添加const迭代器
红黑树的const迭代器
- 红黑树const迭代器的实现就是通过控制红黑树迭代器的模板参数即可，通过模板参数控制operator*返回引用的类型，如果是const迭代器，那么引用返回的是const T&，如果是普通迭代器那么引用返回是T&，operaotr->返回的指针的类型，如果是const迭代器，那么引用返回的是const T*，如果是普通迭代器那么引用返回是T*
- 同时在红黑树内通过传入的参数对const迭代器和普通迭代器分别进行typedef即可
template<typenameT,typenamePtr,typenameRef>struct__RBTree_iterator{typedef RBTreeNode<T> Node;typedef __RBTree_iterator<T, Ptr, Ref> Self; Node* _node;__RBTree_iterator(Node* root):_node(root){} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}};template<typenameK,typenameT,typenameKeyOfT>classRBTree{typedef RBTreeNode<T> Node;public:RBTree():_root(nullptr){}typedef __RBTree_iterator<T, T*, T&> iterator;typedef __RBTree_iterator<T,const T*,const T&> const_iterator;private: Node* _root;};改进set
- 那么我们就可以在set中使用红黑树中的const迭代器转换我们的普通的迭代器了，并且对应的我们也使用红黑树的const迭代器转换set的const迭代器，这里也只需要写出对应的const修饰的begin和end即可，因为普通迭代器和const迭代器的begin和end实际上返回的类型是const类型的迭代器，使用const修饰的begin和end，那么begin和end需要调用的指针指向的对象是const的，即const的指针，那么进行调用底层红黑树就只能去调用红黑树的const修饰的begin和end，这样红黑树返回的迭代器的类型是const迭代器类型和这里上层set的普通迭代器和const迭代器的begin和end实际上返回的类型是const类型的迭代器普配
#pragmaonce#include"RBTree.h"namespace wzx {template<typenameK>classset{private:structSetKeyOfT{const K&operator()(const K& data){return data;}};public:typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator const_iterator; const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();}boolInsert(const K& key){return _t.Insert(key);}private: RBTree<K, K, SetKeyOfT> _t;};}测试一
- 我们使用如下代码测试经过修改后的set是否可以解决key值不能被修改的问题
#include<iostream>#include"MyMap.h"#include"MySet.h"usingnamespace std;intmain(){ wzx::set<int> s; s.Insert(5); s.Insert(2); s.Insert(9); s.Insert(1); wzx::set<int>::iterator it = s.begin();while(it != s.end()){(*it)++; cout <<*it <<' ';++it;} cout << endl;return0;}运行结果如下
可以了，set的key值不能被修改了
测试二
- 那么我们接下来测试我们的代码是否可以正常访问key值
#include<iostream>#include"MyMap.h"#include"MySet.h"usingnamespace std;intmain(){ wzx::set<int> s; s.Insert(5); s.Insert(2); s.Insert(9); s.Insert(1); wzx::set<int>::iterator it = s.begin();while(it != s.end()){//(*it)++; cout <<*it <<' ';++it;} cout << endl;return0;}运行结果如下，正确
九、map的改进
- 这里我们仿造STL库中的map通过给pair<key,value>中的key使用const进行修饰，这样的话，key就不会被修改了，同时value没有加const进行修饰，那么就可以进行修改了，符合STL库中的需求
- 同时这里我们也顺带添加map的const迭代器，并且map的const迭代器是由红黑树的const迭代器转换来的，map的普通迭代器是由红黑树的普通迭代器转换来的
#pragmaonce#include"RBTree.h"namespace wzx {template<typenameK,typenameV>classmap{private:structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();}boolInsert(const pair<const K, V> kv){return _t.Insert(kv);}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};}测试一
- 我们使用如下代码测试map的普通迭代器的key是否是不可以修改，value是否是可以修改的，map的const迭代器的key和value是否是不能修改的
voidfun(const wzx::map<int,int> m){ wzx::map<int,int>::const_iterator cmit = m.begin();while(cmit != m.end()){ cmit->first++; cmit->second++; cout << cmit->first <<':'<< cmit->second << endl;++cmit;} cout << endl;}intmain(){ wzx::map<int,int> m; m.Insert(make_pair(1,1)); m.Insert(make_pair(3,3)); m.Insert(make_pair(6,6)); m.Insert(make_pair(8,8)); wzx::map<int,int>::iterator mit = m.begin();while(mit != m.end()){ mit->first++; mit->second++; cout << mit->first <<':'<< mit->second << endl;++mit;} cout << endl;fun(m);return0;}运行结果如下
map的普通迭代器的key不可以修改，value是可以修改，map的const迭代器的key和value是不能修改的
测试二
- 使用如下代码测试是否const迭代器和普通迭代器都可以正常读取key和value，并且测试普通迭代器的value是否可以进行修改
voidfun(const wzx::map<int,int> m){ wzx::map<int,int>::const_iterator cmit = m.begin();while(cmit != m.end()){//cmit->first++;//cmit->second++; cout << cmit->first <<':'<< cmit->second << endl;++cmit;} cout << endl;}intmain(){ wzx::map<int,int> m; m.Insert(make_pair(1,1)); m.Insert(make_pair(3,3)); m.Insert(make_pair(6,6)); m.Insert(make_pair(8,8)); wzx::map<int,int>::iterator mit = m.begin();while(mit != m.end()){//mit->first++; mit->second++; cout << mit->first <<':'<< mit->second << endl;++mit;} cout << endl;fun(m);return0;}运行结果如下，正确
operator[]
- 我们知道在map中还有一个重要的接口我们没有实现那就是operator[]，关于operator[]的使用小编已经整理在了后方蓝字链接部分【c++】STL容器-map和set、multimap和multiset的使用和介绍（2.3w字详情解析）
- 在STL库中，operator[]的实现是使用insert实现的，在STL库中insert的返回值不同于我们实现的Insert，我们实现的Insert的返回值只是一个bool值，在STL库中的insert的返回值是一个pair<iterator,bool>，即返回插入位置的迭代器和是否插入成功，并且将这两个返回值放在一个pair结构中一并返回
Insert
- 那么接下来我们改造一下我们的insert的返回值即可，那么将我们Insert的返回值改造成和STL库中的insert一样的返回值pair<iterator,bool>
- 接下来就是有三处改进，第一处是当红黑树的根节点为空的时候返回新增节点_root构造出来的迭代器和true放在make_pair函数模板中返回即可
- 第二处是当Insert发现这个值已经存在，那么返回cur指针构造出来的迭代器和false放在make_pair函数模板中返回即可
- 第三处是当红黑树的根节点不为空，Insert发现这个值不存在的时候，在cur位置就是对应的新增节点，但是由于进行插入后红黑树可能还会进行对应的变色向上调整加旋转，所以当进行变色向上旋转的时候cur位置就会被向上更新迭代，所以我们要在cur申请了一个新节点后，进行变色前使用一个节点的指针newnode提起保存一下cur即可，那么当进行完对应的变色加旋转后，返回newnode节点指针构造的迭代器和true放在make_pair函数模板中返回即可
pair<iterator,bool>Insert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returnmake_pair(iterator(_root),true);}else{ Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(data)>kot(cur->_data)){ parent = cur; cur = cur->_right;}elseif(kot(data)<kot(cur->_data)){ parent = cur; cur = cur->_left;}else{returnmake_pair(iterator(cur),false);}} cur =newNode(data); cur->_col = RED; Node* newnode = cur; cur->_parent = parent;if(kot(cur->_data)>kot(parent->_data)){ parent->_right = cur;}else{ parent->_left = cur;}while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; _root->_col = BLACK;}else{if(cur == parent->_left){RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else//cur = parent->_right{RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else//parent == grandfather->_right{ Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; _root->_col = BLACK;}else{if(cur == parent->_right){RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else//cur = parent->_left{RotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}}returnmake_pair(iterator(newnode),true);}}继续完善operaotr[]
- operator[]的返回值是value的引用，函数的参数是key，那么我们在operator[]中调用Insert，传入key和V()即value的默认构造函数即可，同样的我们使用一个pair<iterator,bool>类型的变量kv接收Inset的返回值
- 那么kv是一个pair对象，取出kv的first是迭代器，那么迭代器中封装的是节点的指针，由于在map中这个节点中存储的类型是一个pair<key,value>结构，我们想要取出这个节点的value那么就要使用->取出second即可，返回取出的value即可
V&operator[](const K& key){ pair<RBTree<K, pair<const K, V>, MapKeyOfT>::iterator,bool> kv =Insert(make_pair(key,V()));return kv.first->second;} pair<iterator,bool>Insert(const pair<const K, V> kv){return _t.Insert(kv);}测试一
- 我们使用如下代码测试operator[]的使用
intmain(){ wzx::map<string, string> m; m.Insert(make_pair("insert","xxx")); m["string"];for(constauto& e : m){ cout << e.first <<':'<< e.second << endl;} cout << endl; m["string"]="字符串"; m["insert"]="插入"; m["hello"]="你好";for(constauto& e : m){ cout << e.first <<':'<< e.second << endl;} cout << endl;return0;}运行结果如下，正确
十、完善set的Insert
- 由于我们对红黑树的Insert的返回值进行了修改，set中的Insert的返回值仍然为bool我们还没有进行修改，所以我们要对其进行修改返回值，思考一下，为什么小编要这样去写，先进行接收红黑树的返回值，在使用pair的构造函数构造一个pair的匿名对象进行返回
pair<iterator,bool>Insert(const K& key){ pair<typenameRBTree<K, K, SetKeyOfT>::iterator,bool> kv = _t.Insert(key);return pair<iterator,bool>(kv.first, kv.second);}- 原因是红黑树Insert的返回值的类型是pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool>，即返回的pair中的first，即迭代器是普通迭代器，而小编编写的set中的普通迭代器的底层是const迭代器，所以这里必然会出现类型不匹配，那我们该如何做呢？
那么我们应该如何做呢？我们了解，普通迭代器作为构造函数的参数是可以构造转换出const迭代器的，因为它们中只是封装了一个节点指针，我们将普通迭代器的节点的指针取出来浅拷贝给const迭代器节点的指针即可完成使用普通迭代器构造const迭代器，那么我们就需要继续对红黑树的迭代器的构造函数进行改造，那么就是将红黑树的迭代器的构造函数添加一个函数重载，函数参数是普通迭代器类型，完成节点指针的浅拷贝即可，同样的，我们如何在红黑树的迭代器的内部获取普通迭代器的类型呢？在红黑树的模板参数中有T，节点中存储的类型即可typedef出来普通迭代器的类型typedef __RBTree_iterator<T, T*, T&> Iterator;那么我们使用这个普通迭代器作为参数完成const迭代器的构造函数即可
template<typenameT,typenamePtr,typenameRef>struct__RBTree_iterator{typedef RBTreeNode<T> Node;typedef __RBTree_iterator<T, Ptr, Ref> Self;typedef __RBTree_iterator<T, T*, T&> Iterator; Node* _node;__RBTree_iterator(Node* root):_node(root){}__RBTree_iterator(const Iterator& it):_node(it._node){} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& it){return _node != it._node;} Self&operator--(){ Node* cur = _node; Node* parent = cur->_parent;if(cur->_left){ Node* LeftMax = cur->_left;while(LeftMax->_right){ LeftMax = LeftMax->_right;} _node = LeftMax;}else{while(parent && cur == parent->_left){ cur = parent; parent = parent->_parent;} _node = parent;}return*this;} Self&operator++(){ Node* cur = _node; Node* parent = cur->_parent;if(cur->_right){ Node* RightMin = cur->_right;while(RightMin->_left){ RightMin = RightMin->_left;} _node = RightMin;}else{while(parent && cur == parent->_right){ cur = parent; parent = parent->_parent;} _node = parent;}return*this;}};测试
- 那么当我们完成红黑树的const迭代器构造之后，当调用set的Insert的时候，去set的Insert进行调用底层红黑树的Insert，底层红黑树Insert返回的pair中的first是普通迭代器，set的Insert的返回值类型的pair的first是const迭代器，出现类型不匹配，那么此时普通迭代器就可以通过构造函数构造出const迭代器了
- 同样的我们那刚才的代码进行测试，是否set可以正常读取key值
#include<iostream>#include"MyMap.h"#include"MySet.h"usingnamespace std;intmain(){ wzx::set<int> s; s.Insert(5); s.Insert(2); s.Insert(9); s.Insert(1); wzx::set<int>::iterator it = s.begin();while(it != s.end()){//(*it)++; cout <<*it <<' ';++it;} cout << endl;return0;}运行结果如下，可以set进行正常的插入值了
- 那么我们思考一点，当红黑树的迭代器实例化为const迭代器的时候，那么此时的const迭代器，下面代码就是const迭代器的构造函数，那么红黑树的迭代器实例化为普通迭代器的时候，下面代码是什么呢？其实下面代码此时就成为了普通迭代器的拷贝构造函数了，因为此时下面函数的参数类型和普通迭代器的类型一致，所以是普通迭代器的拷贝构造函数
- 那么当红黑树的const迭代器被调用的时候，那么此时的const迭代器的拷贝构造函数去哪了呢？不要忘记当我们不显示写，由于拷贝构造函数是编译器默认生成的，所以编译器会默认帮我们生成一个拷贝构造函数进行调用
__RBTree_iterator(const Iterator& it):_node(it._node){}十一、源代码
MyMap.h
#pragmaonce#include"RBTree.h"namespace wzx {template<typenameK,typenameV>classmap{private:structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} V&operator[](const K& key){ pair<RBTree<K, pair<const K, V>, MapKeyOfT>::iterator,bool> kv =Insert(make_pair(key,V()));return kv.first->second;} pair<iterator,bool>Insert(const pair<const K, V> kv){return _t.Insert(kv);}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};}Myset.h
#pragmaonce#include"RBTree.h"namespace wzx {template<typenameK>classset{private:structSetKeyOfT{const K&operator()(const K& data){return data;}};public:typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} pair<iterator,bool>Insert(const K& key){return _t.Insert(key);}private: RBTree<K, K, SetKeyOfT> _t;};}RBTree.h
#pragmaonce#include<iostream>usingnamespace std;enumColour{ RED, BLACK };template<typenameT>structRBTreeNode{ T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};template<typenameT,typenamePtr,typenameRef>struct__RBTree_iterator{typedef RBTreeNode<T> Node;typedef __RBTree_iterator<T, Ptr, Ref> Self;typedef __RBTree_iterator<T, T*, T&> Iterator; Node* _node;__RBTree_iterator(Node* root):_node(root){}__RBTree_iterator(const Iterator& it):_node(it._node){} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& it){return _node != it._node;} Self&operator--(){ Node* cur = _node; Node* parent = cur->_parent;if(cur->_left){ Node* LeftMax = cur->_left;while(LeftMax->_right){ LeftMax = LeftMax->_right;} _node = LeftMax;}else{while(parent && cur == parent->_left){ cur = parent; parent = parent->_parent;} _node = parent;}return*this;} Self&operator++(){ Node* cur = _node; Node* parent = cur->_parent;if(cur->_right){ Node* RightMin = cur->_right;while(RightMin->_left){ RightMin = RightMin->_left;} _node = RightMin;}else{while(parent && cur == parent->_right){ cur = parent; parent = parent->_parent;} _node = parent;}return*this;}};template<typenameK,typenameT,typenameKeyOfT>classRBTree{typedef RBTreeNode<T> Node;public:RBTree():_root(nullptr){}typedef __RBTree_iterator<T, T*, T&> iterator;typedef __RBTree_iterator<T,const T*,const T&> const_iterator; iterator begin(){ Node* cur = _root;while(cur->_left){ cur = cur->_left;}returniterator(cur);} iterator end(){returniterator(nullptr);} const_iterator begin()const{ Node* cur = _root;while(cur->_left){ cur = cur->_left;}returnconst_iterator(cur);} const_iterator end()const{returnconst_iterator(nullptr);} KeyOfT kot; Node*Find(const K& key){ Node* cur = _root;while(cur){if(key >kot(cur->_data)){ cur = cur->_right;}elseif(key <kot(cur->_data)){ cur = cur->_left;}else{return cur;}}returnnullptr;} pair<iterator,bool>Insert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returnmake_pair(iterator(_root),true);}else{ Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(data)>kot(cur->_data)){ parent = cur; cur = cur->_right;}elseif(kot(data)<kot(cur->_data)){ parent = cur; cur = cur->_left;}else{returnmake_pair(iterator(cur),false);}} cur =newNode(data); cur->_col = RED; Node* newnode = cur; cur->_parent = parent;if(kot(cur->_data)>kot(parent->_data)){ parent->_right = cur;}else{ parent->_left = cur;}while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; _root->_col = BLACK;}else{if(cur == parent->_left){RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else//cur = parent->_right{RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else//parent == grandfather->_right{ Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent; _root->_col = BLACK;}else{if(cur == parent->_right){RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else//cur = parent->_left{RotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}}returnmake_pair(iterator(newnode),true);}}boolCheckColour(Node* root,int blacksum,int leftpathblack){if(root ==nullptr){if(blacksum != leftpathblack){ cout <<"每条路径上的黑色节点的数目不同"<< endl;returnfalse;}returntrue;} Node* parent = root->_parent;if(parent && parent->_col == RED && root->_col == RED){ cout << root->_kv.first <<':'<<"出现两个连续的红节点"<< endl;returnfalse;}if(root->_col == BLACK) blacksum++;returnCheckColour(root->_left, blacksum, leftpathblack)&&CheckColour(root->_right, blacksum, leftpathblack);}boolIsBalance(){returnIsBalance(_root);}boolIsBalance(Node* root){if(root ==nullptr)returntrue;if(root->_col != BLACK){ cout <<"根节点颜色错误不为黑色"<< endl;returnfalse;}int leftpathbalck =0; Node* cur = root;while(cur){if(cur->_col == BLACK) leftpathbalck++; cur = cur->_left;}returnCheckColour(root,0, leftpathbalck);}intHeight(){returnHeight(_root);}intHeight(Node* root){if(root ==nullptr){return0;}int heightL =Height(root->_left);int heightR =Height(root->_right);return heightL > heightR ? heightL +1: heightR +1;}private:voidRotateL(Node* parent){ Node* ppnode = parent->_parent; Node* cur = parent->_right; Node* curleft = cur->_left; parent->_right = curleft;if(curleft){ curleft->_parent = parent;} cur->_left = parent; parent->_parent = cur;if(ppnode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{ cur->_parent = ppnode;if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;}}}voidRotateR(Node* parent){ Node* ppnode = parent->_parent; Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright;if(curright){ curright->_parent = parent;} cur->_right = parent; parent->_parent = cur;if(ppnode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur; cur->_parent = ppnode;}else{ ppnode->_right = cur; cur->_parent = ppnode;}}}private: Node* _root;};test.cpp
#include<iostream>#include"MyMap.h"#include"MySet.h"usingnamespace std;//int main()//{// wzx::set<int> s;// s.Insert(5);// s.Insert(2);// s.Insert(9);// s.Insert(1);//// wzx::set<int>::iterator it = s.begin();//// while (it != s.end())// {// (*it)++;// cout << *it << ' ';// ++it;// }// cout << endl << endl;//// wzx::map<int, int> m;// m.Insert(make_pair(6, 6));// m.Insert(make_pair(1, 1));// m.Insert(make_pair(8, 8));// m.Insert(make_pair(3, 3));//// wzx::map<int, int>::iterator mit = m.begin();// while (mit != m.end())// {// mit->first++;// mit->second++;// cout << mit->first << ':' << mit->second << endl;// ++mit;// }// cout << endl;//// return 0;//}//int main()//{// wzx::set<int> s;// s.Insert(5);// s.Insert(2);// s.Insert(9);// s.Insert(1);//// wzx::set<int>::iterator it = s.begin();//// while (it != s.end())// {// //(*it)++;// cout << *it << ' ';// ++it;// }// cout << endl;//// return 0;//}//void fun(const wzx::map<int, int> m)//{// wzx::map<int, int>::const_iterator cmit = m.begin();// while (cmit != m.end())// {// //cmit->first++;// //cmit->second++;// cout << cmit->first << ':' << cmit->second << endl;// ++cmit;// }// cout << endl;//}////int main()//{// wzx::map<int, int> m;// m.Insert(make_pair(1, 1));// m.Insert(make_pair(3, 3));// m.Insert(make_pair(6, 6));// m.Insert(make_pair(8, 8));//// wzx::map<int, int>::iterator mit = m.begin();// while (mit != m.end())// {// //mit->first++;// mit->second++;// cout << mit->first << ':' << mit->second << endl;// ++mit;// }// cout << endl;//// fun(m);//// return 0;//}intmain(){ wzx::map<string, string> m; m.Insert(make_pair("insert","xxx")); m["string"];for(constauto& e : m){ cout << e.first <<':'<< e.second << endl;} cout << endl; m["string"]="字符串"; m["insert"]="插入"; m["hello"]="你好";for(constauto& e : m){ cout << e.first <<':'<< e.second << endl;} cout << endl;return0;}总结
以上就是今天的博客内容啦,希望对读者朋友们有帮助
水滴石穿，坚持就是胜利，读者朋友们可以点个关注
点赞收藏加关注，找到小编不迷路！
