改造红黑树实现封装 map/set：感受C++ 标准容器的精妙设计与底层实现

容器map/set的底层是红黑树，这一篇详解红黑树如何封装实现map/set。

1.map/set设计的巧妙之处

map是key/value类型，set是key类型，两个冲突的参数类型，是如何由红黑树封装而成？



暴力思路：两个红黑树，一个kv，一个k。可是这样代码复用率极低，维护成本高。



源码思路：利用 键提取器——仿函数 提取kv、k的key，用一颗红黑树实现map，set



C语言一般用函数指针，但是它十分麻烦，C++有了仿函数就很方便

接下来在红黑树基础上封装map和set

2.map和set的实现

2.1map和set的基本框架 + 原红黑树结构变化

map是key、value结构，set是key结构：

 既然我们要用一个红黑树封装实现map和set，那传的参数就得通用：







原本是K，V结构，现在，要改成通用的，就用T吧







T根据需要，可选择传pair<K,V>，也可以是K：（原来是K，V，参数是kv）

然后根据上面，各自写一个仿函数，用于控制红黑树底层获取Key的行为

上层传仿函数，下层需要新增一个模板参数来接收：

2.2Insert

根据上面，原本是KV结构的红黑树，那Insert自然传的是pair

现在传data就行：data类型可能是pair<K,V>，也可能是Key，根据传的不同，创建仿函数对象，去获取它的Key：

Insert后面的部分，反正涉及到获取Key比较大小，就用仿函数

这样就形成一个回调。

2.3Find

Find是用Key比较，那_data类型可能是Key，也可能是pair<K,V>，那同样需要仿函数获取Key

map复用红黑树的Insert，Find



set复用红黑树的Insert，Find

2.4map和set的迭代器Iterator

map和set的迭代器都是由红黑树的迭代器封装而成，源码中有体现。源码写的迭代器十分复杂，包含了继承关系，我们就不写那么复杂。

了解到前面容器的迭代器实现，不难猜红黑树的迭代器也是用一个类封装，再通过重载运算符，使迭代器能像指针一样访问。

这里难点是++和--的实现。红黑树是一种二叉搜索树，走中序遍历输出结果有序。之前使用map和set也提到是这样，得出结论：红黑树迭代器也是走中序遍历：左根右。

那begin返回中序遍历第一个结点（最左结点），end返回空结点（最右结点的一个是空，下面）

迭代器实现++ 和 -- ，只需要注意局部。++返回中序下一个节点，--返回上一个，局部解决了，全局就解决了。但是++和--的情况很多，这也就是它的难点，不是逻辑难点，是代码难点。举例子：

根据中序：左根右，可以推断，begin的下一个就是15节点

因为走到10节点，说明当前子树 左，根都遍历完了，就剩右子树，中序访问右子树，就必须先访问其最左节点，15没有最左节点（本身就是右子树的最左节点），那++it的结果就是15节点

这里呢？ it遍历到18节点，说明 左与根 都遍历完了，++it就是遍历右子树的最左节点（中序第一个），也就是25节点

那如果右子树为空呢？中序遍历升序，可以知道15的下一个是18，怎么得来？

15的右子树为空，15也已经遍历过，说明当前15的子树遍历完，那15要往上找祖先。15作为10的右子树，说明10也已经遍历完（右子树最后遍历），那10也要往上找祖先。

若10还是祖先的右子树，就还得继续找，找到根的父亲还没找到,或者找到，右父亲，停止。

若10是祖先的左子树，说明才刚遍历完祖先的左子树，那下一个就是该祖先，根

这里同理，++若右子树为空，就得向上找右父亲，25的右父亲直接就是30，得出答案。

2.4.1实现迭代器（重点是++与--）

红黑树内部使用迭代器： 

上层（map和set）复用红黑树的迭代器

模板还未实例化，取其中成员类型时，需要typename：告诉是个类型，后面实例化再去找。

迭代器的 --  和 ++ 完全对称，找左父亲，end前一个为最右结点。

2.5 Key不能被修改的问题

对于set，它的key是不能被修改的，但是这里的迭代器还是能修改它。

可以修改后，这棵树就失去意义了， 所以我们要解决这个Key被修改的问题。

为了让它不被修改，最简单的就是这样：

上层传递的const Key给红黑树，因为被const修饰，所以K将不会被修改，从源头解决问题。

typedef这里的声明也需要加上const，不然会出现很多模板特有的意义不明确的报错。

对于map，pair里的Key也不容被修改，那就同理：

2.6修改Find返回值为Iterator，实现统计次数功能

2.7修改Insert返回值为pair<Iterator,bool>，实现operator[ ]

map和set那节，讲过这个[ ]的使用和底层

newnode保存新增结点cur（因为插入过程设计旋转加变色，向上更新，最后的cur不一定是新增）

解决完Insert，接下来就实现operator[ ]:

首先插入Key，如果插入失败，说明存在，flag为false，it是已存在节点，最后返回value

                        如果插入成功，说明不存在，flag为true，it是新增结点，最后返回value

外层对value（[ ]的返回值）++，即可统计次数，不用那么麻烦。

j

2.8红黑树的析构函数

map和set的析构函数会调用红黑树的析构，所以不用写他们的。注意后序遍历析构。