改造红黑树实现封装 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的析构函数会调用红黑树的析构，所以不用写他们的。注意后序遍历析构。
