c++：封装红黑树实现map与set

模拟实现map与set

1.支持insert

（1）复用红黑树头文件并更改相应模板参数

对于节点：

我们需要将存的数据类型修改为泛型T，这样它既可以是key结构实现set，也可以是key_value结构实现map

对于红黑树：

我们需要单独有一个K模板参数，再来一个T模板参数（T表示容器中存储的数据的类型），而要多存一次Key,是为了保证map的erase和find正常进行，这两个方法都要用到key作为参数

（2）源码中的find函数与insert函数的修改方式

insert中是_data和data进行比较，都是容器存储的数据的类型，可以用仿函数实现pair的正确比较

insert的比较

但是find是key和_data进行比较，这个用仿函数就不行了，因为我们在红黑树的层面不知道_data到底是key还是pair。

find的比较

那么我们在哪里可以知道_data到底是pair还是key呢？
答案就是map和set的头文件中。

我们在map和set中创建一个仿函数，该仿函数的作用是将key返回出来

map：

set：

然后我们再将红黑树中的data和key之间，data与data之间的比较都改为仿函数的比较即可，这样子就全都转换成了key的比较

以find为例，我们先将仿函数实例化，然后再使用仿函数提取出key进行比较

2.支持iterator

（1）框架搭建

由于我们的map和set是红黑树为底层实现的，所以指针无法直接充当迭代器，我们还需要将迭代器单独封装进一个类，然后重载运算符实现迭代器除了访问外的功能。

接下来我们主要实现迭代器的++

思路讲解：

迭代器++就是找一个大于且紧邻当前节点的节点

情况1：当前迭代器指向的节点右子树不为空

直接找右子树的最左节点，该节点的大小就是仅次于当前节点的

iterator下一个指向的数据应该是25，此时18的右树不为空，所以可以指向右树最左节点

情况2：右子树为空

25的下一个应该是30，也就是它的父节点。

那么我们右子树为空就是找父节点？

并不是！

这里我们如果找父节点10就错了，因为我们是中序遍历，所以若右树为空，说明当前节点为根节点的子树遍历完了。也就是15的树遍历完了，而对于10来说，10的树也遍历完了，此时我们就往上找到18，而18就是我们要找的下一个节点。

所以我们发现要找的节点是祖先节点中，子节点在父节点左边的那个父节点

（2）++代码实现：

首先考虑右树不为空的情况，先让node指向其右节点，然后不断向左节点移动，直到左节点为空就返回_node

然后考虑右树为空的情况，在父节点存在的情况下寻找到子节点为父节点的左节点的那个父节点，并让迭代器中的_node指向该父节点。然后返回_node。

（3）begin与end实现

begin：是整棵树的最左节点

不过有可能整棵树为空，所以我们先让minleft指向整棵树的根部。然后进入while循环，

若树为空就不会进循环，直接构造一个指针为空的空迭代器返回

若树不为空，就会搜索到最左节点并构造一个指向最左节点的迭代器返回

end：根节点的父节点，也就是nullptr

注意：
1.不能返回迭代器的引用，其一是迭代器设计的初衷就是用于访问数据，迭代器不被允许修改。其二是迭代器可能是局部创建的，若返回引用会导致返回的迭代器在出函数后就被销毁了，导致迭代器悬空。

2.这里我们的Begin和End都用了大写，这是为了防止和map，set的begin/end名字发生冲突，因为我们是接口命名优先保证一样。Iterator这里大写也是同理

（4）封装进map与set

set

注意要将RBtree<K, pair<K, V>, MapKeyOfT>::Iterator前面加一个typename告诉编译器这是一个类型，那么类型重命名为类型是可以的。

map同理

补充：

operator--：

左不为空，找左树最右节点。

左为空，找祖先节点中子节点在父节点右侧的父节点

需要注意的是：当我们迭代器为end时，指向的为nullptr，所以还需要传一个根节点给operator--，再进行中序遍历找到最右节点。

3.支持const_iterator

 我们前面实现的迭代器只能支持普通引用和普通地址返回，而不能控制他为const属性，且如果我们迭代器返回的指针或引用不再是普通的指针/引用，而是智能指针、右值引用时，也无法兼容。

（1）所以为了将迭代器变得兼容性更强，我们将operator*和operator->的返回值变成模板参数类型，Ref和Ptr。

那么我们就可以在rbtree中将TreeIterator进行typedef，把迭代器分成普通迭代器和const迭代器。

我们只要控制TreeIterator的模板参数传参就可以控制迭代器类型了

（2）const的begin和end

（3）封装进map与set

set

map

4.将key的修改权限更正

 由于此时我们的key在set和map中都可以修改，而我们的set和map的key都是不允许修改的，所以我们就需要限制一下key

set中：我们需要将存储数据类型的key限制为const，而用于find和erase的则不用去限制，因为方法参数中已经加了const。

map中：将pair中的key限制为const。

5.支持[  ]

 [  ]运算符的实现依赖于返回pair<iterator,bool>的insert方法，所以我们先将insert的返回值进行修改

修改insert：

（1）对于树为空情况

插入位置为_root，所以用_root构造迭代器

（2）对于查找到已有节点

树中已有节点cur，返回cur

（3）对于插入成功的最终返回

这里的oldcur是在cur节点新建完成后立刻记录的cur地址，因为后面红黑树的变色操作会改变cur的指向，不能直接返回最后的cur。

顺便修改find：

将返回值改为迭代器，若已有key值的节点，返回指向树中该key值节点的迭代器。

若没有找到，返回End（）。

修改map与set的insert

map：

set：

在map中实现operator[ ]：

注意：

1.c++支持所有类型的匿名对象构造，所以可以直接用V（）充当value

2.p.first->second的解读：p.first取出了iterator，然后iterator->second相当于访问iterator指向的value，然后返回的就是value的引用。之所以用->是因为iterator要当成指针来用