map和set基于红黑树的实现

从这里可以看出来set和map都是在红黑树的基础上对传入参数做出改变实现的一个时key一个是pair<key value>

set传第二个参数是为了兼容map的pair同时传入第三个是为了在插入时从map中取出key进行排序

• 把红黑树通用的拓扑结构（颜色、三个指针）抽到基类，把和业务相关的数据 Value 放在派生类；树平衡旋转等底层操作使用基类指针实现，做到平衡逻辑与存储的数据类型解耦，一套红黑树可以支持 set、map 不同 Value，把不变的逻辑封装成父类，减少代码在生成时的冗余。
• 通过下图对框架的分析，我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现，rb_tree是实现key的搜索场景，还是key/value的搜索场景不是直接写死的，⽽是由第⼆个模板参数Value决定
  _rb_tree_node中存储的数据类型。
  • set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是
  pair<const key, T>，这样⼀颗红⿊树既可以实现key搜索场景的set，也可以实现key/value搜索场
  景的map。
  • 要注意⼀下，源码⾥⾯模板参数是⽤T代表value，⽽内部写的value_type不是我们我们⽇常
  key/value场景中说的value，源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。
  • rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型，为什么还要传第⼀个模板
  参数Key呢？尤其是set，两个模板参数是⼀样的，这是很多同学这时的⼀个疑问。要注意的是对于
  map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形
  参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，map insert的
  是pair对象，但是find和ease的是Key对象。
  • 吐槽⼀下，这⾥源码命名⻛格⽐较乱，set模板参数⽤的Key命名，map⽤的是Key和T命名，⽽
  rb_tree⽤的⼜是Key和Value，可⻅⼤佬有时写代码也不规范，乱弹琴。
  2. 模拟实现map和set
  
• 核心框架，通过第二个模板参数的不同，在__rb_tree_node的结构上让红黑树生成的类不同。

• 2. 模拟实现map和set

• 2.1 实现出复⽤红⿊树的框架，并⽀持insert

• 参考源码框架，map和set复⽤之前我们实现的红⿊树。
  • 我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，红⿊树中的数据类型，我们使⽤
  T。
  • 其次因为RBTree实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进⾏插⼊逻辑
  ⽐较时，就没办法进⾏⽐较，因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任
  何时候只⽐较key，所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给
  RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较，具体
  细节参考如下代码实现。
• b_tree 作为通用泛型容器，无法预知存储的元素 T 是 K 还是 pair<K,V>。
  如果直接使用 T 进行比较，pair 默认比较会同时比较 key 和 value，而 map 只允许 key 参与比较。
  所以我们提供 KeyOfT 萃取仿函数：set 用 identity 直接返回元素本身；map 用 select1st 提取 pair 的 first。rb_tree 内部依靠这个仿函数拿到 key，只使用 key 完成查找、比较、判重，实现一套 rb_tree 同时支撑 set 与 map。解决比较判断的问题
• pair内部的比较逻辑是first和second同时参与比较与map的比较逻辑不符合我们用仿函数来去出pair的key进行比较

• # 总结对比

  1. 运算符重载：**绑定在类型上，一个类型一套固定规则，不能随便换**
  2. 仿函数：独立的策略类型，**可插拔、可带成员状态、编译期确定逻辑、不止能比较，还能做萃取 / 转换**

  ## 📌 面试精简背诵（适配你的红黑树问题）

  仿函数不仅仅用来实现比较。

  1. **策略可插拔**：作为模板参数，同一套 rb_tree 可以传入不同仿函数，切换萃取规则、排序规则，不用重写容器代码；
  2. **可以保存状态**，普通函数和运算符重载无法携带成员变量；
  3. 它是类型，支持模板实例化，编译期内联，运行时开销很小；
  4. 仿函数不局限于返回 bool 做大小比较，像`select1st`萃取仿函数，可以用来提取数据，这也是我们 rb_tree 区分 map/set 的核心；
  5. STL 容器、算法的扩展机制都是基于仿函数设计。

• map和set分别传入自己的仿函数，用自己的比较逻辑

• 通过在RBtree生成不同的两个类，实现不同的比较逻辑

• iterator实现思路分析

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算
  符实现，迭代器像指针⼀样访问的⾏为。
  • 这⾥的难点是operator++和operator--的实现。之前使⽤部分，我们分析了，map和set的迭代器⾛
  的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10
  所在结点的迭代器。
  • 迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。
  • 迭代器++时，如果it指向的结点的右⼦树不为空，代表当前结点已经访问完了，要访问下⼀个结点
  是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。
  • 迭代器++时，如果it指向的结点的右⼦树空，代表当前结点已经访问完了且当前结点所在的⼦树也
  访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上
  找。
  • 如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结
  点的⽗亲；如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。
  • 如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完
  了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找
  到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。如下图：it指向15，15右为空，15是10
  的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个
  访问的结点就是18。
  • end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18
  到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这是⽗亲为空了，那我们就把it中的结点指针
  置为nullptr，我们⽤nullptr去充当end。需要注意的是stl源码空，红⿊树增加了⼀个哨兵位头结点
  做为end()，这哨兵位头结点和根互为⽗亲，左指向最左结点，右指向最右结点。相⽐我们⽤
  nullptr作为end()，差别不⼤，他能实现的，我们也能实现。只是--end()判断到结点时空，特殊处
  理⼀下，让迭代器结点指向最右结点。具体参考迭代器--实现。
  • 迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->
  左⼦树，具体参考下⾯代码实现。
  • set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可， RBTree<K,
  const K, SetKeyOfT> _t;
  • map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参
  数改成const K即可， RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  • ⽀持完整的迭代器还有很多细节需要修改，具体参考下⾯题的代码。

• 2.3 map⽀持[]

• 首先iterator还是复用PBtree的迭代器
• 这里的迭代器和我之前写的list的迭代器类似，通过传入的模板参数不同生成不同的类
• 核心迭代器的实现
• ++的思路就是返回当前节点的右节点的最左节点，如果没有右节点就向上找当前节点是父亲左节点的节点并返回该父亲节点
• --的时候多了一层特殊处理就是 根节点--的时候返回的是最右边的节点，这样也就支持了逆序，引入root最大用处就是处理空的情况