C++ 基于自主实现的红黑树封装Map和Set （上）

C++ 红黑树-CSDN博客

1.观察代码

2. 修改代码

使用仿函数解决比较的问题

3.迭代器接口封装

4. 总结

1.观察代码

在实现了红黑树之后，我们将红黑树封装进Map和Set中。Map和Set最大的区别就是：前者使用的是pair<k,v> ，后者只有一个v

那我们需要各自封装一份接口吗？

显然这种做法正确但是效率不高，借此机会学习一下C++库中对红黑树的封装。

首先打开库中的代码，进行观察（需要源代码的读者可以在评论区私信我）

两者都先给一颗rb_tree(红黑树)传了一个key和一个value_type

因此可以推出，红黑树将接口实现为泛型编程

再来看红黑树：

把红黑树实现成模版，Value可以是pair也可以是key。

正如下图，map传的是pair; set传的就是一个key

2. 修改代码

我们对自己的代码开始修改：

将数据类型都改为T，至于T是一个pair还是一个值，我们不知道，也不需要知道，这是上层封装的事情。

template<typename T>
struct RBTreeNode {typedef RBTreeNode<T> Node;RBTreeNode(const T& data):_parent(nullptr), _left(nullptr), _right(nullptr), _kv(data), _color(RED){}Node* _parent;Node* _left;Node* _right;T _data;Color _color;
};

tree里也要修改：

T可以是pair也可以是单独一个key , 这不再是我们需要考虑的问题。

然后就可以创建map和set对应的文件了。传的模版参数是一个key和一个T , T表示的是对应的value 。至于为什么要传key,会在后文解释。

可以先实现基本结构：

那第一个相同的模版参数的k的目的是什么呢？

比如处理Find或者erase这类函数的形参。

此处用T就不行。比如在map的find函数中，我传入key的目的是查找key对应的value，结果我现在需要知道一整个pair的信息才能查找，不是逻辑矛盾吗？

但是insert和构造一个Node的时候就得使用T，插入一个数据或者构造一个节点的前提是整个键值对的信息我都清楚。

所以value主要是给Node或者给insert用的、

key主要是给Find或者erase用的。

使用仿函数解决比较的问题

现在的新麻烦出在对data的比较上

对于set，直接使用data进行大小比较当然没有问题；

对于map，data是一个对，不方便直接比较。我们可以采用重写pair的运算符的方法，但是此处官方采用的是使用执行回调功能的仿函数。仿函数还可以直接传进类模版，更为方便。

这个仿函数的功能是能把_data中用于比较大小的部分返回。

虽然对于set来说看起来多此一举，但是为了实现在上层将map和set封装到一起都更简单的实现，

逻辑如图：

3.迭代器接口封装

在MyMap中封装一层insert就可以直接使用了。

观察库中，最重要的就是还有迭代器以及相关的接口还没处理。

由于树的中序遍历与线性容器不同，除了++与--不一样，其他接口的实现大逻辑都是一致的。

来封装迭代器：

（鉴于++的逻辑较为复杂，我们暂且放置一下）

template<typename T>
struct RBTreeIterator {typedef RBTreeIterator<T> Self;typedef RBTreeNode<T> Node;Node* _node;RBTreeIterator(node* node):_node(node){}Self& operator++() {//inorderreturn *this;}T& oepartor* () {return _node->_data;}bool operator!=(const Self& it) {return this->_node != it._node;}};

然后把RBTreeIterator给包进RBTree里，这里注意中序的begin是从最左边的树开始的。

然后再包进set和map中去。

还有以前需要加typename的老问题

set和map这一层是在红黑树的类中去取一个变量变成自己的。因为是模版，所以编译器不能识别到底是静态成员变量还是类，所以要加个typename告诉编译器。

注意，如果想用const修饰begin和end会报错。因为End和Begin不是常函数，此处涉及一个权限的放大。但如果用const修饰End 和 Begin而不修饰begin和end , 就不会报错（权限的缩小）

现在，就只差一个++的实现了：

不论是算法题还是实现数据结构，这种类似的情况我们都需要从情况的最中间开始考虑。

也就是先不考虑特殊情况，假设已经走到了中间，从中间开始考虑如何走下一步。

中序：左中右

每当我们的cur遍历到一个节点时，说明该节点的左边已经被访问完了，我们暂时只需要考虑其右树。如果右树为空，则表示该节点的左子树和右子树都访问完了，已经可以退出这一层栈帧了。

比如我已经访问到6时，发现左右都为空，就往回退到1,1的左右也被访问完了，就往回退到8,8只是被访问了左子树，所以6访问完的下一个就是8。比如我已经访问到了27，就向上退到25，再退到17，再退到13，完成了整棵树的访问。

“我是父亲的右，我被访问完了、父亲也被访问完了，我们需要沿着_parent这条路径向上走”

“我是父亲的左，我被访问完了、下一个该访问的是父亲”

代码实现：

Self& operator++()
{if (_node->_right){// 右不为空，右子树最左节点就是中序下一个Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

现在代码就能跑起来了。