如何用红黑树实现既封装map又封装set的长尾功能？

本文共计5853个文字，预计阅读时间需要24分钟。

目录

一、封装第一层：函数取结点中的key关键字

二、封装第二层：红黑树的普通遍代器

1.map和set的表层遍代器实现

2.底层红黑树遍代器的实现

三、封装第三层：set的遍代器（底层）

目录

• 一、封装第一层：仿函数取结点中的key关键码
• 二、封装第二层：红黑树的普通迭代器
• 1.map和set的表层迭代器实现
• 2.底层红黑树中迭代器的实现
• 三、封装第三层：
• 1.set的迭代器（底层均为const_iterator）
• 3.map的[ ]运算符重载
• 四、对于红黑树设计产生的问题
• 总结

一、封装第一层：仿函数取结点中的key关键码

1.在源码里面，对于map和set的实现，底层是用同一棵红黑树封装出来的，并不是用了两棵红黑树，一个红黑树结点存key，一个红黑树结点存<key,value>的键值对，这样的方式太不符合大佬的水准了，实际上在红黑树底层中用了一个模板参数Value来代表红黑树结点存储对象的类型，这个类型可能是pair键值对，也有可能是key类型。

所以在红黑树这一层中是不知道他自己的结点要存储什么类型的对象的，故而需要模板参数来接收存储对象的类型。