C++：用红黑树封装map与set-2

在这里插入图片描述

文章目录

前言
一、红黑树封装map与set中const迭代器
- 1. 框架的搭建
- 2. set实现const迭代器
- 3. map实现const迭代器
二、operator[ ]
- 1. operator[ ]要达成的样子
- 2. insert的改变
三. 解决insert里set中的问题
四. 解决map中的operator[ ]
总结用红黑树封装map与set代码

前言

前面我们map与set封装的已经差不多了，接下来还有一些细节需要处理，本片博客主要解决const迭代器以及引发的一些其他问题~😘😘

总后的总结完整的源码封装的源码附上~🥰🥰

想看前面的封装是怎么实现的戳这里哦宝宝~❤️❤️
<(￣︶￣)↗[GO!]

一、红黑树封装map与set中const迭代器

1. 框架的搭建

首先，和以前一样，要写出const迭代器，和以前一样通过控制三个模板参数，从而控制operator*以及operator->的返回值，从而控制普通迭代器与const迭代器。

在这里插入图片描述

改变模板参数，控制返回值：
在这里插入图片描述

2. set实现const迭代器

set的data中储存的是key，而且set是key的模型，我们说key是不可以被改变的，无论你是普通迭代器还是const迭代器，key都不可以被改变。

因此，这里set普通迭代器与set const迭代器都是RBTree::const迭代器，就达到了这样的效果：
在这里插入图片描述

tips：注意这里要加typename，模板类内的东西要在外部使用要告诉编译器哦

因此，我们在封装的时候要这样写：
在这里插入图片描述
这里的iterator是什么呢？是普通的迭代器吗？

答：不是的，这里我们typedef了，这里其实是红黑树中的const_iterator。

3. map实现const迭代器

map与set不同，对于set来说，data中存储的是key，因此直接让它的普通迭代器与const迭代器都是const迭代器。

但是！对于map来说就不一样了，map的data中存储的是
pair<key, calue>，对于pair.first是不可以修改的，对于pair.second是需要修改的，如果直接将普通迭代器与const迭代器都是const迭代器，那么pair.first与pair.second都不能修改了。

因此我们需要想出其他的方法！

这里的解决方法是，将map的pair<key, calue>变为pair<const key, calue>，从一开始就限制key是不能够修改的，因此迭代器正常走就可以了~

在这里插入图片描述

二、operator[ ]

1. operator[ ]要达成的样子

对于map来说，因为map是key-value，因此我们要存在operator[ ]，

通过[ ]进行插入
通过[ ]通过key改变value

因此我们实现operator[ ]是一定要借助insert的。
这里我们前面详细分析过，具体的分析过程戳这里哦_宝

○( ＾皿＾)っHiahiahia…

2. insert的改变

通过前面的分析我们知道了，为了实现上述的目的，insert的返回值需要变成一个pair，

在这里插入图片描述

因此：
在这里插入图片描述
当然，RBTree.h中的insert改了，对应的map与set也要相应的更改：

以下是我们的测试代码：

jyf::map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));//bit::map<int, int>::iterator mit = m.begin();
auto mit = m.begin();
while (mit != m.end())
{// 不能修改key，可以修改value//mit->first = 1;mit->second = 2;cout << mit->first << ":" << mit->second << endl;++mit;
}
cout << endl;//func(m);for (const auto& kv : m)
{cout << kv.first << ":" << kv.second << endl;
}
cout << endl;jyf::set<int> s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);
jyf::set<int>::iterator it = s.begin();
while (it != s.end())
{// 不应该允许修改key
/*	if (*it % 2 == 0){*it += 10;}*/cout << *it << " ";++it;
}
cout << endl;

但是，但是中的但是，就算我们改完了之后还是编译不通过：
在这里插入图片描述

我们看到这里，map好像没问题了，唯一出问题的就是set，因此我们要解决这个问题。

三. 解决insert里set中的问题

那么set为什么会出问题呢？
问题出在set中普通迭代器与const迭代器都是const迭代器！

如下图：
在这里插入图片描述

那这里怎么解决呢？

首先我们来套一层：

用pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret来接收Insert的返回值，因此在ret中，pair的iterator是普通的iterator。

然后又用ret.first 与 ret.second来构造pair返回，也就是说pair是不能直接构造的时候这里first用const迭代器来构造，因此需要套一层，最后用普通迭代器构造cosnt迭代器。

pair<iterator, bool> insert(const K& key)
{pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);
}

但是只是这样还是编译不通过，还是老问题~

这是因为我们没有提供用普通迭代器构造const迭代器的构造函数：
解决方案如下：

在这里插入图片描述
这样我们的编译就可以通过了：

四. 解决map中的operator[ ]

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

以下是测试代码：

jyf::map<string, string> dict;
dict.insert(make_pair("sort", "xxx"));
dict["left"]; // 插入for (const auto& kv : dict)
{cout << kv.first << ":" << kv.second << endl;
}
cout << endl;dict["left"] = "左边"; // 修改
dict["sort"] = "排序"; // 修改
dict["right"] = "右边"; // 插入+修改for (const auto& kv : dict)
{cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

运行结果为：
在这里插入图片描述

总结用红黑树封装map与set代码

RBTree.h

#pragma once#include<iostream>using namespace std;enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;T _data;RBTreeNode(const T& data): _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _data(data){}
};template<class T, class Ptr, class Ref>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;// 解决insert中set的问题typedef __TreeIterator<T, T*, T&> iterator;__TreeIterator(const iterator& it): _node(it._node){};Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator* (){return _node->_data;}Ptr operator-> (){return &(_node->_data);}bool operator!= (const Self& s){return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}Self& operator++ (){if (_node->_right != nullptr){Node* curleft = _node->_right;while (curleft->_left){curleft = curleft->_left;}_node = curleft;}else{// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点Node* cur = _node;Node* parent = _node->_parent;while (parent){if (parent->_left == cur){break;}else{cur = parent;parent = parent->_parent;}}_node = parent;}return *this;}Self& operator--(){if (_node->_left){Node* subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}_node = subRight;}else{// 孩子是父亲的右的那个节点Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:// 同一个类模板，传的不同的参数实例化出的不同类型typedef __TreeIterator<T, T*, T&> iterator;typedef __TreeIterator<T, const T*, const T&> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return const_iterator(leftMin);}const_iterator end() const{return const_iterator(nullptr);}Node* Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;}pair<iterator, bool> Insert(const T& data){// 树为空，直接插入然后返回if (_root == nullptr){_root = new Node(data);// 根节点必须是黑色_root->_col = BLACK;return make_pair(iterator(_root), true);}Node* cur = _root;Node* parent = nullptr;KeyOfT kot;while (cur){// 小于往左走if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(data) > kot(cur->_data))   // 大于往右走{parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);// 其他结点初始颜色为红色cur->_col = RED;// 记录cur用于改变颜色后还能找到cur来返回Node* newnode = cur;// 链接if (kot(cur->_data) < kot(parent->_data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while (parent && parent->_col == RED){// 首先我们要找到grandfatherNode* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif (parent == grandfather->_left){// 说明uncle在右边Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if (cur == parent->_left){//     g//   p// cRotateR(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 左右双旋{//     g//   p//		cRotateL(parent);RotateR(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出break;}}else //(parent == grandfather->_right)  // 如果parent是grandfather->_right{// 说明uncle在左边Node* uncle = grandfather->_left;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 右左双旋{// g//	  p// cRotateR(parent);RotateL(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 这里保证根为黑色_root->_col = BLACK;return make_pair(iterator(newnode), true);}// 左单旋void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 右单旋void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 检查是否构建正确bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << kot(root->data) << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}private:Node* _root = nullptr;
};

myset.h

#pragma once
#include"RBTree.h"namespace jyf
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};
}

mymap.h

#pragma once#include"RBTree.h"namespace jyf
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<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<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}

test.cpp

#include<iostream>
#include<string>
using namespace std;#include"mymap.h"
#include"myset.h"//void func(const jyf::map<int, int>& m)
//{
//	//auto mit = m.begin();
//	jyf::map<int, int>::const_iterator mit = m.begin();
//	while (mit != m.end())
//	{
//		// 不能修改key，不能修改value
//		//mit->first = 1;
//		//mit->second = 2;
//
//		cout << mit->first << ":" << mit->second << endl;
//		++mit;
//	}
//	cout << endl;
//}int main()
{jyf::map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));//bit::map<int, int>::iterator mit = m.begin();auto mit = m.begin();while (mit != m.end()){// 不能修改key，可以修改value//mit->first = 1;mit->second = 2;cout << mit->first << ":" << mit->second << endl;++mit;}cout << endl;//func(m);for (const auto& kv : m){cout << kv.first << ":" << kv.second << endl;}cout << endl;jyf::set<int> s;s.insert(5);s.insert(2);s.insert(2);s.insert(12);s.insert(22);s.insert(332);s.insert(7);jyf::set<int>::iterator it = s.begin();while (it != s.end()){// 不应该允许修改key/*	if (*it % 2 == 0){*it += 10;}*/cout << *it << " ";++it;}cout << endl;//for (const auto& e : s)//{//	cout << e << " ";//}//cout << endl;jyf::map<string, string> dict;dict.insert(make_pair("sort", "xxx"));dict["left"]; // 插入for (const auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;dict["left"] = "左边"; // 修改dict["sort"] = "排序"; // 修改dict["right"] = "右边"; // 插入+修改for (const auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;return 0;
}