C++ 基于自主实现的红黑树封装Map和Set （上）-CSDN博客
本文针对上文中没有完成的迭代器接口进行一个补充。
1. 箭头访问
在map的测试中使用箭头访问测试，我们可以复习到:
测试刚才重载的-> , 出现了经典双箭头问题
按理来说应该是像下图一样调用，第一个我们自己重载的箭头返回一个指针，第二个箭头才能去访问first或者second，但是编译器为了规范语法，只需要写一个->即可。
2. operator--()
operator-- 应该从左子树的最右节点开始
思路和上一篇中的++几乎都是一样的。
遍历顺序从左 根 右变成了 右 根 左，从正序变成逆序。
Self& operator--() {
if (_node == nullptr) {
//此时在end的位置，需要特殊处理
Node* MostRight = _root;//但是_root是在RBTree里定义的，此处拿不到。
while (MostRight->_right) {
MostRight = MostRight->_right;
}
_node = MostRight;
}
else if (_node->_left) {
Node* MostRight = _node->_left;
while (MostRight->_right) {
MostRight = MostRight->_right;
}
_node = MostRight;
}
else {
//left不存在，表示当前节点已经完成遍历
Node* cur = _node;
Node* parent = _node->_parent;
if (parent->_right == cur) {
_node = parent;
}
else {
while (parent && cur == parent->_left) {
cur = cur->_parent;
parent = cur->_parent;
}
_node = parent;
}
}
return *this;
}但是要特殊处理iterator指向的是end的问题：
_root要在根节点的位置才能拿到，而operator--是封装在iterator中的。
解决办法：
因为库中的tree是一个带头的树：
此处我们只能进行一个奇怪的改动，构造iterator的时候传入一个_root
在Iterator中加入一个_root , 每次构造iterator都把这个值传过去。
再进行测试：
请注意，因为end对应的是红色，需要先--再解引用。
3.const_iterator
正如在学习list时我们封装的那样，进行一个const_iterator的封装。
是否是const修饰的迭代器，只和返回的引用以及指针有没有权限更改有关。
在set和map里也要写出对应的改动：
假如这是在set中的更改。
此处的const修饰的this对应的是一个set , 但是this被const修饰之后里面的RBTree（成员变量）也是const修饰的，所以End和Begin都会去调那个被const修饰的版本。
再在set中去测试实现的const_iterator
4. 改变树中的元素的数值
改变数值就不满足搜索树。在库中采取的是一律使用const迭代器，我们采取在set和map中实现的时候直接传const
map的处理：
set的处理：
5. map中的operator[]
map对于方括号的重载很特别，是通过key访问value，但是如果该key不存在就会调用value的默认构造，将该不存在的key和value()一起赛进一个新的pair作为新的元素。
并且insert的返回值也是一个pair
因此我们需要先稍加修改之前的insert。
其他所有return的地方都需要修改：
若插入成功：
因为在整个调整过程中cur的值发生变化。所以记录一下初始值。
最后再封装operator[]
v& operator[](const k& key) {
pair<iterator, bool> ret = Insert(make_pair(key, v()));
return ret.first->second;
}以上就是将简易红黑树封装到简易版本的map和set的大致思路。
