map和set基于红黑树的实现

从这里可以看出来set和map都是在红黑树的基础上对传入参数做出改变实现的一个时key一个是pairkey valueset传第二个参数是为了兼容map的pair同时传入第三个是为了在插入时从map中取出key进行排序把红黑树通用的拓扑结构颜色、三个指针抽到基类把和业务相关的数据 Value 放在派生类树平衡旋转等底层操作使用基类指针实现做到平衡逻辑与存储的数据类型解耦一套红黑树可以支持 set、map 不同 Value把不变的逻辑封装成父类减少代码在生成时的冗余。通过下图对框架的分析我们可以看到源码中rb_tree⽤了⼀个巧妙的泛型思想实现rb_tree是实现key的搜索场景还是key/value的搜索场景不是直接写死的⽽是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型。• set实例化rb_tree时第⼆个模板参数给的是keymap实例化rb_tree时第⼆个模板参数给的是pairconst key, T这样⼀颗红⿊树既可以实现key搜索场景的set也可以实现key/value搜索场景的map。• 要注意⼀下源码⾥⾯模板参数是⽤T代表value⽽内部写的value_type不是我们我们⽇常key/value场景中说的value源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。• rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型为什么还要传第⼀个模板参数Key呢尤其是set两个模板参数是⼀样的这是很多同学这时的⼀个疑问。要注意的是对于map和setfind/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和set2.1 实现出复⽤红⿊树的框架并⽀持insert参考源码框架map和set复⽤之前我们实现的红⿊树。• 我们这⾥相⽐源码调整⼀下key参数就⽤Kvalue参数就⽤V红⿊树中的数据类型我们使⽤T。• 其次因为RBTree实现了泛型不知道T参数导致是K还是pairK, V那么insert内部进⾏插⼊逻辑⽐较时就没办法进⾏⽐较因为pair的默认⽀持的是key和value⼀起参与⽐较我们需要时的任何时候只⽐较key所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT然后RBTree中通过KeyOfT仿函数取出T类型对象中的key再进⾏⽐较具体细节参考如下代码实现。b_tree 作为通用泛型容器无法预知存储的元素 T 是 K 还是 pairK,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指向2525右为空25是30的左所以下⼀个访问的结点就是30。• 如果当前结点是⽗亲的右根据中序左⼦树-根结点-右⼦树当前当前结点所在的⼦树访问完了当前结点所在⽗亲的⼦树也访问完了那么下⼀个访问的需要继续往根的祖先中去找直到找到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。如下图it指向1515右为空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即可 RBTreeK,const K, SetKeyOfT _t;• map的iterator不⽀持修改key但是可以修改value我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可 RBTreeK, pairconst K, V, MapKeyOfT _t;• ⽀持完整的迭代器还有很多细节需要修改具体参考下⾯题的代码。2.3 map⽀持[]首先iterator还是复用PBtree的迭代器这里的迭代器和我之前写的list的迭代器类似通过传入的模板参数不同生成不同的类核心迭代器的实现的思路就是返回当前节点的右节点的最左节点如果没有右节点就向上找当前节点是父亲左节点的节点并返回该父亲节点--的时候多了一层特殊处理就是 根节点--的时候返回的是最右边的节点这样也就支持了逆序引入root最大用处就是处理空的情况