1. 项目概述从复用红黑树到理解STL设计哲学如果你写过C肯定用过std::map和std::set。它们一个存键值对一个只存键用起来很方便底层都是红黑树保证有序性。但不知道你有没有想过标准库的实现者是怎么设计这两个容器的难道要为map和set分别写两棵几乎一模一样的红黑树吗这显然太笨了。今天要聊的就是如何用一棵红黑树同时支撑起map和set这两个容器。这不仅仅是实现一个数据结构那么简单它更像是一次对STLStandard Template Library核心设计思想的深度剖析。STL的精髓在于“泛型”和“复用”通过巧妙的模板技术将算法与数据结构解耦实现最大程度的代码复用。map和set共用红黑树就是这个思想最经典的体现之一。理解了这个过程你不仅能自己动手封装出功能完整的map和set更能深刻理解迭代器、仿函数、类型萃取这些高级C特性是如何协同工作的这对于突破C学习的瓶颈至关重要。我当年第一次看STL源码时就被这种设计震撼到了。看似复杂的容器其底层骨架竟如此简洁优雅。自己动手实现一遍比看十遍书都管用。接下来我们就一步步拆解看看这棵“万能”的红黑树是怎么搭建起来的。2. 核心设计思路模板、仿函数与迭代器的三位一体要实现一棵同时服务于map和set的红黑树我们不能像写普通数据结构那样把数据类型写死。核心思路是抽象与分层。2.1 红黑树节点的通用设计首先红黑树节点里存什么对于setT节点直接存一个T类型的值。对于mapK, V节点需要存一个pairconst K, V类型的键值对。这里第一个关键点就来了我们的节点数据不能是固定类型必须是一个模板参数。我们称之为ValueType。对于setValueType就是T。 对于mapValueType就是pairconst K, V。注意map的键K是const的这是为了保证键的不可变性防止用户修改键值破坏红黑树的有序结构。// 红黑树节点颜色 enum Colour { RED, BLACK }; // 红黑树节点 templateclass T // T 就是 ValueType struct RBTreeNode { RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; T _data; // 关键这里存储的数据类型是泛型的T Colour _col; RBTreeNode(const T data) : _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) // 新节点默认为红色 {} };这样通过模板参数T我们就统一了map和set的节点存储格式。2.2 数据提取的关键仿函数KeyOfValue节点里存的是ValueType但红黑树在插入、查找、删除时比较的依据是什么对于set直接比较ValueType即T本身。对于map我们需要从pairconst K, V中提取出K键来进行比较。如何让同一套比较逻辑适应两种不同的数据提取方式这里就要引入STL中非常重要的一个组件仿函数Functor也叫函数对象。我们将定义一个名为KeyOfValue的仿函数它的唯一任务就是从ValueType中取出用于比较的“关键值”Key。// 针对set的仿函数值本身就是关键值 templateclass K struct SetKeyOfValue { const K operator()(const K key) { return key; // 对于setValueType就是K直接返回 } }; // 针对map的仿函数从pair中提取first即key templateclass K, class V struct MapKeyOfValue { const K operator()(const std::pairconst K, V kv) { return kv.first; // 对于map从pair中返回key } };这个仿函数会在红黑树类中作为一个模板参数传入。在树内部任何需要比较的地方都通过调用这个仿函数对象来获取当前节点的“关键值”。2.3 红黑树类的模板设计有了节点和提取关键值的方法我们可以定义红黑树的核心类了。它的模板参数会比较多但每一个都有其明确的作用。templateclass K, class ValueType, class KeyOfValue class RBTree { typedef RBTreeNodeValueType Node; private: Node* _root nullptr; KeyOfValue _kot; // 关键值提取仿函数对象 public: // 插入、查找、删除等接口... bool Insert(const ValueType data) { // 在比较时使用 _kot(node-_data) 来获取关键值进行比较 // _kot(data) 获取待插入数据的关键值 } };K关键值的类型。对于set是T对于map是K。这个参数主要用于某些需要明确键类型的接口虽然内部比较通过KeyOfValue进行但对外声明时需要。ValueType节点存储的数据类型。KeyOfValue从ValueType提取关键值的仿函数类型。这样的设计将“数据存储”ValueType和“数据比较的依据”通过KeyOfValue提取K完全解耦。红黑树只关心如何组织节点和维护平衡完全不关心节点里具体存的是单一值还是键值对。2.4 迭代器设计让树可遍历容器必须提供迭代器。红黑树的迭代器本质上是一个对节点的指针进行封装的对象重载了、--、*、-等操作符。对于set解引用迭代器*it应该得到一个const T因为set的元素是不可修改的修改可能破坏有序性。 对于map解引用迭代器应该得到一个pairconst K, V其中key是const不可修改value可以修改。我们的红黑树迭代器内部持有一个Node*。operator*()返回的是节点中_data的引用。那么如何控制返回的引用类型呢这又需要借助模板。// 红黑树迭代器 templateclass T, class Ref, class Ptr // T是ValueType, Ref是引用类型Ptr是指针类型 struct __RBTreeIterator { typedef RBTreeNodeT Node; typedef __RBTreeIteratorT, Ref, Ptr Self; Node* _node; // 解引用操作符返回节点数据的引用 Ref operator*() { return _node-_data; } // 成员访问操作符返回节点数据的指针 Ptr operator-() { return (_node-_data); } // ... 其他操作符重载如 --等 };在set和map中它们会定义自己所需的迭代器类型并传递给红黑树。// 在set类内部 typedef typename RBTreeK, K, SetKeyOfValueK::iterator iterator; // 实际上set的iterator和const_iterator通常都是const版本的防止修改 // 很多实现中set的iterator直接被定义为RBTree的const_iterator // 在map类内部 typedef typename RBTreeK, pairconst K, V, MapKeyOfValueK, V::iterator iterator;这样通过迭代器模板参数的精妙控制map的迭代器解引用后我们可以修改value但无法修改key完全符合语义。注意事项迭代器中和--操作的实现本质上是中序遍历左-根-右找前驱和后继节点。对于it如果当前节点有右子树则后继节点是右子树中的最左节点如果没有则需向上回溯找到第一个“孩子是父亲左孩子”的祖先节点。这部分逻辑需要仔细处理是迭代器实现中的难点务必画图理解。3. 封装set与map薄薄的适配层有了强大的、泛型的红黑树之后set和map类的实现就变得异常简单了。它们本质上只是一个“适配器”Adapter对外提供标准的容器接口内部将所有操作委托给红黑树对象。3.1 set类的封装set的模板参数通常只需要一个K键类型。在它内部定义出所需的仿函数类型和红黑树类型。templateclass K class my_set { private: // 核心红黑树类型定义 // 参数1: K 是关键值类型 // 参数2: K 也是节点存储的数据类型(ValueType) // 参数3: SetKeyOfValueK 是提取关键值的仿函数 RBTreeK, K, SetKeyOfValueK _t; public: // 类型定义暴露给用户 typedef typename RBTreeK, K, SetKeyOfValueK::const_iterator iterator; // 注意set的iterator通常是const的 typedef typename RBTreeK, K, SetKeyOfValueK::const_iterator const_iterator; // 接口实现直接调用红黑树的对应接口 pairiterator, bool insert(const K key) { // 调用_t.Insert返回的可能是普通迭代器需要转换成const迭代器 // 这里涉及一个pair的类型转换是另一个小难点 auto ret _t.Insert(key); return pairiterator, bool(iterator(ret.first._node), ret.second); } iterator find(const K key) { return _t.Find(key); } iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } // ... 其他接口如erase, size, empty等 };可以看到my_set的代码量非常少它的主要工作就是“转调”。一个需要特别注意的细节是set的迭代器应该是const_iterator因为set的元素不允许修改。这要求在红黑树的Insert接口中当插入成功时返回的迭代器可能需要被隐式或显式地转换为const版本或者在set::insert内部进行转换。3.2 map类的封装map的模板参数有两个K键类型和V值类型。它的适配逻辑与set类似但ValueType变成了pairconst K, V。templateclass K, class V class my_map { private: // 核心红黑树类型定义 // 参数1: K 是关键值类型 // 参数2: pairconst K, V 是节点存储的数据类型(ValueType) // 参数3: MapKeyOfValueK, V 是从pair中提取key的仿函数 RBTreeK, pairconst K, V, MapKeyOfValueK, V _t; public: // 类型定义 typedef typename RBTreeK, pairconst K, V, MapKeyOfValueK, V::iterator iterator; typedef typename RBTreeK, pairconst K, V, MapKeyOfValueK, V::const_iterator const_iterator; // map特有的operator[]这是map方便使用的关键 V operator[](const K key) { pairiterator, bool ret insert(make_pair(key, V())); // 尝试插入值用默认构造函数构造 return ret.first-second; // 返回插入成功或已存在节点的value的引用 } pairiterator, bool insert(const pairconst K, V kv) { return _t.Insert(kv); } iterator find(const K key) { return _t.Find(key); } iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } // ... 其他接口 };map的封装有两个亮点operator[]的实现这是map最常用的接口之一。它的实现非常巧妙先用给定的key和V的默认值构造一个pair尝试插入。insert方法会返回一个pairiterator, bool。无论插入成功新节点还是失败key已存在这个迭代器都指向了key对应的节点。最后直接返回这个节点数据pair的second成员即value的引用。这样map[key]既可以用于访问也可以用于赋值写法非常直观。键的const属性注意insert方法的参数类型是const pairconst K, V键K被两层const修饰。这确保了用户无法在插入时修改键也与我们节点存储pairconst K, V的设计保持一致。实操心得在封装set和map时最容易出错的地方是迭代器类型的匹配和转换。因为红黑树内部可能实现了一个通用的、可修改的迭代器但set需要的是const迭代器。处理好这里的类型转换需要理解C的const_cast、或者通过在红黑树内部同时定义iterator和const_iterator并让set直接使用const_iterator来解决。建议先实现红黑树的基础迭代器再仔细设计set/map对迭代器类型的别名定义。4. 红黑树核心操作实现详解前面讲了宏观设计现在深入到红黑树内部看看支撑map和set的这棵通用红黑树其关键操作——插入——是如何实现的。删除操作更为复杂但原理相通本文重点讲解插入以阐明思想。4.1 泛化插入逻辑红黑树的插入分为两步1. 按照二叉搜索树规则找到插入位置并创建新节点红色2. 检查并修复因插入红色节点而可能破坏的红黑树性质。我们的插入函数接收一个const ValueType data参数。在内部我们通过_kot仿函数来获取用于比较的关键值。pairiterator, bool Insert(const ValueType data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; // 根节点必须为黑 return make_pair(iterator(_root), true); } Node* parent nullptr; Node* cur _root; KeyOfValue kot; // 提取关键值的仿函数对象 // 1. 搜索插入位置 while (cur) { parent cur; // 使用kot仿函数提取关键值进行比较 if (kot(data) kot(cur-_data)) cur cur-_left; else if (kot(data) kot(cur-_data)) cur cur-_right; else // 关键值已存在插入失败 return make_pair(iterator(cur), false); } // 2. 创建新节点并链接 cur new Node(data); Node* newnode cur; // 保存新节点指针用于返回 if (kot(data) kot(parent-_data)) { parent-_left cur; } else { parent-_right cur; } cur-_parent parent; // 3. 调整颜色与结构核心 while (parent parent-_col RED) { Node* grandparent parent-_parent; // 情况分类父节点是祖父节点的左孩子还是右孩子 if (parent grandparent-_left) { Node* uncle grandparent-_right; // 情况一叔叔存在且为红 if (uncle uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandparent-_col RED; // 继续向上调整 cur grandparent; parent cur-_parent; } else { // 叔叔不存在或为黑 // 情况二cur是parent的右孩子LR双旋 if (cur parent-_right) { RotateL(parent); // 左单旋 swap(parent, cur); // 旋转后parent和cur关系互换 } // 情况三cur是parent的左孩子R单旋 RotateR(grandparent); // 右单旋 parent-_col BLACK; grandparent-_col RED; break; } } else { // parent grandparent-_right对称情况 Node* uncle grandparent-_left; if (uncle uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandparent-_col RED; cur grandparent; parent cur-_parent; } else { if (cur parent-_left) { // RL双旋 RotateR(parent); swap(parent, cur); } RotateL(grandparent); // L单旋 parent-_col BLACK; grandparent-_col RED; break; } } } _root-_col BLACK; // 确保根节点为黑 return make_pair(iterator(newnode), true); }这段代码是红黑树插入的核心。它完全独立于ValueType的具体形式所有比较都通过kot仿函数完成。旋转操作RotateL,RotateR也只涉及节点指针的调整与节点数据无关。这就是泛型设计的威力。4.2 旋转操作的实现旋转是AVL树、红黑树等平衡二叉搜索树维持平衡的基础操作。它只改变节点的拓扑结构不改变中序遍历的顺序。// 左单旋 (以parent为旋转中心) void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; subR-_left parent; Node* ppnode parent-_parent; parent-_parent subR; // 处理parent原父节点的指向 if (parent _root) { _root subR; _root-_parent nullptr; } else { if (ppnode-_left parent) { ppnode-_left subR; } else { ppnode-_right subR; } subR-_parent ppnode; } } // 右单旋 (与左单旋对称) void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; subL-_right parent; Node* ppnode parent-_parent; parent-_parent subL; if (parent _root) { _root subL; _root-_parent nullptr; } else { if (ppnode-_left parent) { ppnode-_left subL; } else { ppnode-_right subL; } subL-_parent ppnode; } }注意事项旋转代码虽然逻辑固定但指针操作非常繁琐极易出错。两个关键点一是不要忘记处理每个节点的_parent指针这是实现迭代器/--操作的基础二是注意判断旋转节点parent是否是根节点如果是需要更新_root。建议在写代码时每一步都画图对照确保每个指针的指向都正确无误。4.3 查找与删除的泛化查找Find操作相对简单同样使用_kot仿函数进行比较即可。删除Erase是红黑树中最复杂的操作其情况分类比插入更多。但其核心逻辑依然是先执行二叉搜索树的删除然后根据被删除节点和其替代节点的颜色进行复杂的颜色调整和旋转。在实现删除时同样要完全使用_kot进行比较保证代码的通用性。由于删除代码较长此处不展开但其设计原则与插入一致所有对节点数据的访问和比较都通过KeyOfValue仿函数间接进行。5. 迭代器、const与反向迭代器要让我们的map和set用起来和STL一样顺手迭代器必须完善。5.1 正向迭代器的完整实现我们之前给出了迭代器的框架。这里补充中序后继和--中序前驱的实现这是迭代器的灵魂。templateclass T, class Ref, class Ptr struct __RBTreeIterator { // ... 类型定义、构造函数、operator*、operator- Self operator() { // 找中序遍历的后继节点 if (_node-_right) { // 情况1: 有右子树后继是右子树的最左节点 Node* subLeft _node-_right; while (subLeft-_left) { subLeft subLeft-_left; } _node subLeft; } else { // 情况2: 无右子树向上找直到当前节点是其父节点的左孩子 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_right) { cur parent; parent parent-_parent; } _node parent; // parent可能为nullptr即end() } return *this; } Self operator(int) { Self tmp(*this); (*this); return tmp; } Self operator--() { // 找中序遍历的前驱节点与对称 if (_node-_left) { Node* subRight _node-_left; while (subRight-_right) { subRight subRight-_right; } _node subRight; } else { Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_left) { cur parent; parent parent-_parent; } _node parent; } return *this; } // ... 其他操作符如, ! };5.2 const迭代器的巧妙复用我们不想为const迭代器再写一份几乎相同的代码。C模板允许我们复用代码。通常在红黑树类内部我们会这样定义// 红黑树类内部 public: typedef __RBTreeIteratorValueType, ValueType, ValueType* iterator; typedef __RBTreeIteratorValueType, const ValueType, const ValueType* const_iterator;注意iterator和const_iterator是同一个模板__RBTreeIterator的不同实例化。它们的区别仅在于Ref和Ptr模板参数一个是普通引用/指针一个是const引用/指针。这里有一个关键技巧为了让const_iterator能接受普通iterator的构造例如在find函数返回const_iterator时我们需要在迭代器模板中添加一个构造函数允许从“非const版本”的迭代器构造“const版本”的迭代器。这通常通过一个额外的模板参数和模板构造函数实现。templateclass T, class Ref, class Ptr struct __RBTreeIterator { typedef __RBTreeIteratorT, T, T* Iterator; // 普通迭代器类型 // 模板构造函数允许用普通迭代器构造const迭代器 templateclass URef, class UPtr __RBTreeIterator(const __RBTreeIteratorT, URef, UPtr it) : _node(it._node) {} // ... 其他成员 };这个模板构造函数只有在URef和UPtr能匹配或转换为Ref和Ptr时才会被实例化从而安全地实现了从iterator到const_iterator的转换。5.3 反向迭代器reverse_iteratorSTL容器通常也提供rbegin()和rend()。反向迭代器可以用一个适配器模式轻松实现它内部包装一个正向迭代器将操作重载为正向迭代器的--操作将--重载为。在C中std::reverse_iterator就是这样一个适配器。我们可以自己实现一个简易版或者直接使用标准库的std::reverse_iterator来定义我们的reverse_iterator类型。// 在红黑树或set/map类中 typedef std::reverse_iteratoriterator reverse_iterator; typedef std::reverse_iteratorconst_iterator const_reverse_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); }std::reverse_iterator的构造需要传入一个正向迭代器rbegin()对应正向的end()rend()对应正向的begin()逻辑上正好反转。6. 常见问题与调试技巧实录自己实现红黑树并封装容器调试是最大的挑战。以下是我在实现过程中踩过的坑和总结的技巧。6.1 迭代器失效问题与vector不同红黑树以及map/set的插入操作通常不会导致迭代器失效除了指向被删除元素的迭代器。这是因为红黑树是节点式存储插入新节点不会导致原有节点的内存地址发生变化。这是我们的一大优势。但是删除操作会导致指向被删除节点的迭代器失效这是所有节点式容器的通病。使用时需要注意。6.2 内存泄漏与节点删除红黑树的析构函数需要后序遍历整棵树删除所有节点。忘记实现析构函数会导致严重的内存泄漏。~RBTree() { _Destroy(_root); _root nullptr; } void _Destroy(Node* root) { if (root nullptr) return; _Destroy(root-_left); _Destroy(root-_right); delete root; }删除节点Erase的逻辑非常复杂在调整颜色和旋转时一定要理清各个节点的关系。强烈建议为红黑树实现一个中序遍历打印函数按顺序打印关键值并在每次插入/删除后调用检查是否仍然满足二叉搜索树的性质和红黑树的五条性质。6.3 红黑树性质验证编写一个IsBalance()函数来验证红黑树对于调试至关重要。它主要检查根节点是否为黑色。是否存在连续的红色节点红色节点的孩子必须是黑色。从任一节点到其所有后代叶节点的简单路径上黑色节点的数量是否相同这条最难查。bool _CheckColour(Node* root, int blackNum, int benchmark) { if (root nullptr) { // 走到空节点计算这条路径的黑色节点数 if (blackNum ! benchmark) { cout 黑色节点数量不一致 endl; return false; } return true; } if (root-_col RED root-_parent root-_parent-_col RED) { cout 存在连续的红色节点 endl; return false; } if (root-_col BLACK) { blackNum; } return _CheckColour(root-_left, blackNum, benchmark) _CheckColour(root-_right, blackNum, benchmark); } bool IsBalance() { if (_root nullptr) return true; if (_root-_col RED) return false; // 性质2 // 计算最左路径的黑色节点数作为基准 int benchmark 0; Node* cur _root; while (cur) { if (cur-_col BLACK) benchmark; cur cur-_left; } return _CheckColour(_root, 0, benchmark); }6.4 模板编译错误排查由于大量使用模板编译器报错信息往往又长又晦涩。一个核心技巧是先让代码在一种特定类型下能编译通过。例如可以先typedef RBTreeint, int, SetKeyOfValueint IntSetTree用int实例化你的红黑树把所有逻辑调通。然后再换成模板这样能快速定位是算法逻辑错误还是模板语法错误。另外当出现“未找到匹配的成员函数”或“类型不匹配”时仔细检查迭代器相关的typedef是否正确const和非const版本是否混淆。6.5 与STL行为对齐的细节插入返回值std::map::insert返回pairiterator, bool其中iterator指向已存在或新插入的元素。我们的实现也要保持一致。map的operator[]如果key不存在它会插入一个用默认值初始化的value并返回其引用。我们的实现依赖V类型有默认构造函数。对于没有默认构造函数的类型operator[]可能无法使用。set的迭代器是const的这是一个容易忽略的细节。在STL中setT::iterator实际上是setT::const_iterator的别名解引用后得到的是const T。我们的实现也最好遵循这一约定防止用户修改set的元素。7. 性能考量与扩展思考7.1 时间复杂度分析红黑树保证了最坏情况下插入、删除、查找的时间复杂度都是O(log n)其中n是元素个数。这是它作为map和set底层容器的底气。虽然不如哈希表的平均O(1)快但红黑树能维持元素有序性这是哈希表做不到的。map和set的迭代器遍历是中序有序的。7.2 与unordered_map/set的对比C11引入了基于哈希表的unordered_map和unordered_set。它们提供平均O(1)的查找效率但不保证元素顺序。选择哪个需要元素有序或者需要按顺序遍历 - 选择map/set红黑树。追求极致的查找、插入速度且不关心顺序 - 选择unordered_map/unordered_set哈希表。注意哈希表在最坏情况下大量哈希冲突会退化到O(n)而红黑树始终稳定在O(log n)。7.3 可能的优化方向内存池频繁的new和delete节点会影响性能。可以实现一个简单的内存池一次性申请一大块内存自己管理节点的分配与回收。缓存友好性红黑树节点在内存中是不连续的对CPU缓存不友好。在某些特定场景下可以考虑使用B树变体但实现复杂度更高。支持透明比较C14C14为关联容器引入了“透明比较”特性允许查找时使用与键类型不同的类型进行比较例如用string查找mapstring, int时可以直接传递string_view避免不必要的临时对象构造。这需要让我们的KeyOfValue仿函数和比较逻辑支持多类型。自己动手实现一遍这个项目你会对C模板、数据结构、STL设计有脱胎换骨的理解。它就像打通任督二脉之前很多模糊的概念比如“迭代器为什么这么设计”、“模板如何实现泛型”都会变得无比清晰。下次当你再使用std::map时你看到的将不再是一个黑盒容器而是一棵在内存中优雅旋转的红黑树以及背后精妙绝伦的抽象艺术。
C++ STL map/set底层实现：一棵红黑树如何支撑两种容器
1. 项目概述从复用红黑树到理解STL设计哲学如果你写过C肯定用过std::map和std::set。它们一个存键值对一个只存键用起来很方便底层都是红黑树保证有序性。但不知道你有没有想过标准库的实现者是怎么设计这两个容器的难道要为map和set分别写两棵几乎一模一样的红黑树吗这显然太笨了。今天要聊的就是如何用一棵红黑树同时支撑起map和set这两个容器。这不仅仅是实现一个数据结构那么简单它更像是一次对STLStandard Template Library核心设计思想的深度剖析。STL的精髓在于“泛型”和“复用”通过巧妙的模板技术将算法与数据结构解耦实现最大程度的代码复用。map和set共用红黑树就是这个思想最经典的体现之一。理解了这个过程你不仅能自己动手封装出功能完整的map和set更能深刻理解迭代器、仿函数、类型萃取这些高级C特性是如何协同工作的这对于突破C学习的瓶颈至关重要。我当年第一次看STL源码时就被这种设计震撼到了。看似复杂的容器其底层骨架竟如此简洁优雅。自己动手实现一遍比看十遍书都管用。接下来我们就一步步拆解看看这棵“万能”的红黑树是怎么搭建起来的。2. 核心设计思路模板、仿函数与迭代器的三位一体要实现一棵同时服务于map和set的红黑树我们不能像写普通数据结构那样把数据类型写死。核心思路是抽象与分层。2.1 红黑树节点的通用设计首先红黑树节点里存什么对于setT节点直接存一个T类型的值。对于mapK, V节点需要存一个pairconst K, V类型的键值对。这里第一个关键点就来了我们的节点数据不能是固定类型必须是一个模板参数。我们称之为ValueType。对于setValueType就是T。 对于mapValueType就是pairconst K, V。注意map的键K是const的这是为了保证键的不可变性防止用户修改键值破坏红黑树的有序结构。// 红黑树节点颜色 enum Colour { RED, BLACK }; // 红黑树节点 templateclass T // T 就是 ValueType struct RBTreeNode { RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; T _data; // 关键这里存储的数据类型是泛型的T Colour _col; RBTreeNode(const T data) : _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) // 新节点默认为红色 {} };这样通过模板参数T我们就统一了map和set的节点存储格式。2.2 数据提取的关键仿函数KeyOfValue节点里存的是ValueType但红黑树在插入、查找、删除时比较的依据是什么对于set直接比较ValueType即T本身。对于map我们需要从pairconst K, V中提取出K键来进行比较。如何让同一套比较逻辑适应两种不同的数据提取方式这里就要引入STL中非常重要的一个组件仿函数Functor也叫函数对象。我们将定义一个名为KeyOfValue的仿函数它的唯一任务就是从ValueType中取出用于比较的“关键值”Key。// 针对set的仿函数值本身就是关键值 templateclass K struct SetKeyOfValue { const K operator()(const K key) { return key; // 对于setValueType就是K直接返回 } }; // 针对map的仿函数从pair中提取first即key templateclass K, class V struct MapKeyOfValue { const K operator()(const std::pairconst K, V kv) { return kv.first; // 对于map从pair中返回key } };这个仿函数会在红黑树类中作为一个模板参数传入。在树内部任何需要比较的地方都通过调用这个仿函数对象来获取当前节点的“关键值”。2.3 红黑树类的模板设计有了节点和提取关键值的方法我们可以定义红黑树的核心类了。它的模板参数会比较多但每一个都有其明确的作用。templateclass K, class ValueType, class KeyOfValue class RBTree { typedef RBTreeNodeValueType Node; private: Node* _root nullptr; KeyOfValue _kot; // 关键值提取仿函数对象 public: // 插入、查找、删除等接口... bool Insert(const ValueType data) { // 在比较时使用 _kot(node-_data) 来获取关键值进行比较 // _kot(data) 获取待插入数据的关键值 } };K关键值的类型。对于set是T对于map是K。这个参数主要用于某些需要明确键类型的接口虽然内部比较通过KeyOfValue进行但对外声明时需要。ValueType节点存储的数据类型。KeyOfValue从ValueType提取关键值的仿函数类型。这样的设计将“数据存储”ValueType和“数据比较的依据”通过KeyOfValue提取K完全解耦。红黑树只关心如何组织节点和维护平衡完全不关心节点里具体存的是单一值还是键值对。2.4 迭代器设计让树可遍历容器必须提供迭代器。红黑树的迭代器本质上是一个对节点的指针进行封装的对象重载了、--、*、-等操作符。对于set解引用迭代器*it应该得到一个const T因为set的元素是不可修改的修改可能破坏有序性。 对于map解引用迭代器应该得到一个pairconst K, V其中key是const不可修改value可以修改。我们的红黑树迭代器内部持有一个Node*。operator*()返回的是节点中_data的引用。那么如何控制返回的引用类型呢这又需要借助模板。// 红黑树迭代器 templateclass T, class Ref, class Ptr // T是ValueType, Ref是引用类型Ptr是指针类型 struct __RBTreeIterator { typedef RBTreeNodeT Node; typedef __RBTreeIteratorT, Ref, Ptr Self; Node* _node; // 解引用操作符返回节点数据的引用 Ref operator*() { return _node-_data; } // 成员访问操作符返回节点数据的指针 Ptr operator-() { return (_node-_data); } // ... 其他操作符重载如 --等 };在set和map中它们会定义自己所需的迭代器类型并传递给红黑树。// 在set类内部 typedef typename RBTreeK, K, SetKeyOfValueK::iterator iterator; // 实际上set的iterator和const_iterator通常都是const版本的防止修改 // 很多实现中set的iterator直接被定义为RBTree的const_iterator // 在map类内部 typedef typename RBTreeK, pairconst K, V, MapKeyOfValueK, V::iterator iterator;这样通过迭代器模板参数的精妙控制map的迭代器解引用后我们可以修改value但无法修改key完全符合语义。注意事项迭代器中和--操作的实现本质上是中序遍历左-根-右找前驱和后继节点。对于it如果当前节点有右子树则后继节点是右子树中的最左节点如果没有则需向上回溯找到第一个“孩子是父亲左孩子”的祖先节点。这部分逻辑需要仔细处理是迭代器实现中的难点务必画图理解。3. 封装set与map薄薄的适配层有了强大的、泛型的红黑树之后set和map类的实现就变得异常简单了。它们本质上只是一个“适配器”Adapter对外提供标准的容器接口内部将所有操作委托给红黑树对象。3.1 set类的封装set的模板参数通常只需要一个K键类型。在它内部定义出所需的仿函数类型和红黑树类型。templateclass K class my_set { private: // 核心红黑树类型定义 // 参数1: K 是关键值类型 // 参数2: K 也是节点存储的数据类型(ValueType) // 参数3: SetKeyOfValueK 是提取关键值的仿函数 RBTreeK, K, SetKeyOfValueK _t; public: // 类型定义暴露给用户 typedef typename RBTreeK, K, SetKeyOfValueK::const_iterator iterator; // 注意set的iterator通常是const的 typedef typename RBTreeK, K, SetKeyOfValueK::const_iterator const_iterator; // 接口实现直接调用红黑树的对应接口 pairiterator, bool insert(const K key) { // 调用_t.Insert返回的可能是普通迭代器需要转换成const迭代器 // 这里涉及一个pair的类型转换是另一个小难点 auto ret _t.Insert(key); return pairiterator, bool(iterator(ret.first._node), ret.second); } iterator find(const K key) { return _t.Find(key); } iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } // ... 其他接口如erase, size, empty等 };可以看到my_set的代码量非常少它的主要工作就是“转调”。一个需要特别注意的细节是set的迭代器应该是const_iterator因为set的元素不允许修改。这要求在红黑树的Insert接口中当插入成功时返回的迭代器可能需要被隐式或显式地转换为const版本或者在set::insert内部进行转换。3.2 map类的封装map的模板参数有两个K键类型和V值类型。它的适配逻辑与set类似但ValueType变成了pairconst K, V。templateclass K, class V class my_map { private: // 核心红黑树类型定义 // 参数1: K 是关键值类型 // 参数2: pairconst K, V 是节点存储的数据类型(ValueType) // 参数3: MapKeyOfValueK, V 是从pair中提取key的仿函数 RBTreeK, pairconst K, V, MapKeyOfValueK, V _t; public: // 类型定义 typedef typename RBTreeK, pairconst K, V, MapKeyOfValueK, V::iterator iterator; typedef typename RBTreeK, pairconst K, V, MapKeyOfValueK, V::const_iterator const_iterator; // map特有的operator[]这是map方便使用的关键 V operator[](const K key) { pairiterator, bool ret insert(make_pair(key, V())); // 尝试插入值用默认构造函数构造 return ret.first-second; // 返回插入成功或已存在节点的value的引用 } pairiterator, bool insert(const pairconst K, V kv) { return _t.Insert(kv); } iterator find(const K key) { return _t.Find(key); } iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } // ... 其他接口 };map的封装有两个亮点operator[]的实现这是map最常用的接口之一。它的实现非常巧妙先用给定的key和V的默认值构造一个pair尝试插入。insert方法会返回一个pairiterator, bool。无论插入成功新节点还是失败key已存在这个迭代器都指向了key对应的节点。最后直接返回这个节点数据pair的second成员即value的引用。这样map[key]既可以用于访问也可以用于赋值写法非常直观。键的const属性注意insert方法的参数类型是const pairconst K, V键K被两层const修饰。这确保了用户无法在插入时修改键也与我们节点存储pairconst K, V的设计保持一致。实操心得在封装set和map时最容易出错的地方是迭代器类型的匹配和转换。因为红黑树内部可能实现了一个通用的、可修改的迭代器但set需要的是const迭代器。处理好这里的类型转换需要理解C的const_cast、或者通过在红黑树内部同时定义iterator和const_iterator并让set直接使用const_iterator来解决。建议先实现红黑树的基础迭代器再仔细设计set/map对迭代器类型的别名定义。4. 红黑树核心操作实现详解前面讲了宏观设计现在深入到红黑树内部看看支撑map和set的这棵通用红黑树其关键操作——插入——是如何实现的。删除操作更为复杂但原理相通本文重点讲解插入以阐明思想。4.1 泛化插入逻辑红黑树的插入分为两步1. 按照二叉搜索树规则找到插入位置并创建新节点红色2. 检查并修复因插入红色节点而可能破坏的红黑树性质。我们的插入函数接收一个const ValueType data参数。在内部我们通过_kot仿函数来获取用于比较的关键值。pairiterator, bool Insert(const ValueType data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; // 根节点必须为黑 return make_pair(iterator(_root), true); } Node* parent nullptr; Node* cur _root; KeyOfValue kot; // 提取关键值的仿函数对象 // 1. 搜索插入位置 while (cur) { parent cur; // 使用kot仿函数提取关键值进行比较 if (kot(data) kot(cur-_data)) cur cur-_left; else if (kot(data) kot(cur-_data)) cur cur-_right; else // 关键值已存在插入失败 return make_pair(iterator(cur), false); } // 2. 创建新节点并链接 cur new Node(data); Node* newnode cur; // 保存新节点指针用于返回 if (kot(data) kot(parent-_data)) { parent-_left cur; } else { parent-_right cur; } cur-_parent parent; // 3. 调整颜色与结构核心 while (parent parent-_col RED) { Node* grandparent parent-_parent; // 情况分类父节点是祖父节点的左孩子还是右孩子 if (parent grandparent-_left) { Node* uncle grandparent-_right; // 情况一叔叔存在且为红 if (uncle uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandparent-_col RED; // 继续向上调整 cur grandparent; parent cur-_parent; } else { // 叔叔不存在或为黑 // 情况二cur是parent的右孩子LR双旋 if (cur parent-_right) { RotateL(parent); // 左单旋 swap(parent, cur); // 旋转后parent和cur关系互换 } // 情况三cur是parent的左孩子R单旋 RotateR(grandparent); // 右单旋 parent-_col BLACK; grandparent-_col RED; break; } } else { // parent grandparent-_right对称情况 Node* uncle grandparent-_left; if (uncle uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandparent-_col RED; cur grandparent; parent cur-_parent; } else { if (cur parent-_left) { // RL双旋 RotateR(parent); swap(parent, cur); } RotateL(grandparent); // L单旋 parent-_col BLACK; grandparent-_col RED; break; } } } _root-_col BLACK; // 确保根节点为黑 return make_pair(iterator(newnode), true); }这段代码是红黑树插入的核心。它完全独立于ValueType的具体形式所有比较都通过kot仿函数完成。旋转操作RotateL,RotateR也只涉及节点指针的调整与节点数据无关。这就是泛型设计的威力。4.2 旋转操作的实现旋转是AVL树、红黑树等平衡二叉搜索树维持平衡的基础操作。它只改变节点的拓扑结构不改变中序遍历的顺序。// 左单旋 (以parent为旋转中心) void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; subR-_left parent; Node* ppnode parent-_parent; parent-_parent subR; // 处理parent原父节点的指向 if (parent _root) { _root subR; _root-_parent nullptr; } else { if (ppnode-_left parent) { ppnode-_left subR; } else { ppnode-_right subR; } subR-_parent ppnode; } } // 右单旋 (与左单旋对称) void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; subL-_right parent; Node* ppnode parent-_parent; parent-_parent subL; if (parent _root) { _root subL; _root-_parent nullptr; } else { if (ppnode-_left parent) { ppnode-_left subL; } else { ppnode-_right subL; } subL-_parent ppnode; } }注意事项旋转代码虽然逻辑固定但指针操作非常繁琐极易出错。两个关键点一是不要忘记处理每个节点的_parent指针这是实现迭代器/--操作的基础二是注意判断旋转节点parent是否是根节点如果是需要更新_root。建议在写代码时每一步都画图对照确保每个指针的指向都正确无误。4.3 查找与删除的泛化查找Find操作相对简单同样使用_kot仿函数进行比较即可。删除Erase是红黑树中最复杂的操作其情况分类比插入更多。但其核心逻辑依然是先执行二叉搜索树的删除然后根据被删除节点和其替代节点的颜色进行复杂的颜色调整和旋转。在实现删除时同样要完全使用_kot进行比较保证代码的通用性。由于删除代码较长此处不展开但其设计原则与插入一致所有对节点数据的访问和比较都通过KeyOfValue仿函数间接进行。5. 迭代器、const与反向迭代器要让我们的map和set用起来和STL一样顺手迭代器必须完善。5.1 正向迭代器的完整实现我们之前给出了迭代器的框架。这里补充中序后继和--中序前驱的实现这是迭代器的灵魂。templateclass T, class Ref, class Ptr struct __RBTreeIterator { // ... 类型定义、构造函数、operator*、operator- Self operator() { // 找中序遍历的后继节点 if (_node-_right) { // 情况1: 有右子树后继是右子树的最左节点 Node* subLeft _node-_right; while (subLeft-_left) { subLeft subLeft-_left; } _node subLeft; } else { // 情况2: 无右子树向上找直到当前节点是其父节点的左孩子 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_right) { cur parent; parent parent-_parent; } _node parent; // parent可能为nullptr即end() } return *this; } Self operator(int) { Self tmp(*this); (*this); return tmp; } Self operator--() { // 找中序遍历的前驱节点与对称 if (_node-_left) { Node* subRight _node-_left; while (subRight-_right) { subRight subRight-_right; } _node subRight; } else { Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_left) { cur parent; parent parent-_parent; } _node parent; } return *this; } // ... 其他操作符如, ! };5.2 const迭代器的巧妙复用我们不想为const迭代器再写一份几乎相同的代码。C模板允许我们复用代码。通常在红黑树类内部我们会这样定义// 红黑树类内部 public: typedef __RBTreeIteratorValueType, ValueType, ValueType* iterator; typedef __RBTreeIteratorValueType, const ValueType, const ValueType* const_iterator;注意iterator和const_iterator是同一个模板__RBTreeIterator的不同实例化。它们的区别仅在于Ref和Ptr模板参数一个是普通引用/指针一个是const引用/指针。这里有一个关键技巧为了让const_iterator能接受普通iterator的构造例如在find函数返回const_iterator时我们需要在迭代器模板中添加一个构造函数允许从“非const版本”的迭代器构造“const版本”的迭代器。这通常通过一个额外的模板参数和模板构造函数实现。templateclass T, class Ref, class Ptr struct __RBTreeIterator { typedef __RBTreeIteratorT, T, T* Iterator; // 普通迭代器类型 // 模板构造函数允许用普通迭代器构造const迭代器 templateclass URef, class UPtr __RBTreeIterator(const __RBTreeIteratorT, URef, UPtr it) : _node(it._node) {} // ... 其他成员 };这个模板构造函数只有在URef和UPtr能匹配或转换为Ref和Ptr时才会被实例化从而安全地实现了从iterator到const_iterator的转换。5.3 反向迭代器reverse_iteratorSTL容器通常也提供rbegin()和rend()。反向迭代器可以用一个适配器模式轻松实现它内部包装一个正向迭代器将操作重载为正向迭代器的--操作将--重载为。在C中std::reverse_iterator就是这样一个适配器。我们可以自己实现一个简易版或者直接使用标准库的std::reverse_iterator来定义我们的reverse_iterator类型。// 在红黑树或set/map类中 typedef std::reverse_iteratoriterator reverse_iterator; typedef std::reverse_iteratorconst_iterator const_reverse_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); }std::reverse_iterator的构造需要传入一个正向迭代器rbegin()对应正向的end()rend()对应正向的begin()逻辑上正好反转。6. 常见问题与调试技巧实录自己实现红黑树并封装容器调试是最大的挑战。以下是我在实现过程中踩过的坑和总结的技巧。6.1 迭代器失效问题与vector不同红黑树以及map/set的插入操作通常不会导致迭代器失效除了指向被删除元素的迭代器。这是因为红黑树是节点式存储插入新节点不会导致原有节点的内存地址发生变化。这是我们的一大优势。但是删除操作会导致指向被删除节点的迭代器失效这是所有节点式容器的通病。使用时需要注意。6.2 内存泄漏与节点删除红黑树的析构函数需要后序遍历整棵树删除所有节点。忘记实现析构函数会导致严重的内存泄漏。~RBTree() { _Destroy(_root); _root nullptr; } void _Destroy(Node* root) { if (root nullptr) return; _Destroy(root-_left); _Destroy(root-_right); delete root; }删除节点Erase的逻辑非常复杂在调整颜色和旋转时一定要理清各个节点的关系。强烈建议为红黑树实现一个中序遍历打印函数按顺序打印关键值并在每次插入/删除后调用检查是否仍然满足二叉搜索树的性质和红黑树的五条性质。6.3 红黑树性质验证编写一个IsBalance()函数来验证红黑树对于调试至关重要。它主要检查根节点是否为黑色。是否存在连续的红色节点红色节点的孩子必须是黑色。从任一节点到其所有后代叶节点的简单路径上黑色节点的数量是否相同这条最难查。bool _CheckColour(Node* root, int blackNum, int benchmark) { if (root nullptr) { // 走到空节点计算这条路径的黑色节点数 if (blackNum ! benchmark) { cout 黑色节点数量不一致 endl; return false; } return true; } if (root-_col RED root-_parent root-_parent-_col RED) { cout 存在连续的红色节点 endl; return false; } if (root-_col BLACK) { blackNum; } return _CheckColour(root-_left, blackNum, benchmark) _CheckColour(root-_right, blackNum, benchmark); } bool IsBalance() { if (_root nullptr) return true; if (_root-_col RED) return false; // 性质2 // 计算最左路径的黑色节点数作为基准 int benchmark 0; Node* cur _root; while (cur) { if (cur-_col BLACK) benchmark; cur cur-_left; } return _CheckColour(_root, 0, benchmark); }6.4 模板编译错误排查由于大量使用模板编译器报错信息往往又长又晦涩。一个核心技巧是先让代码在一种特定类型下能编译通过。例如可以先typedef RBTreeint, int, SetKeyOfValueint IntSetTree用int实例化你的红黑树把所有逻辑调通。然后再换成模板这样能快速定位是算法逻辑错误还是模板语法错误。另外当出现“未找到匹配的成员函数”或“类型不匹配”时仔细检查迭代器相关的typedef是否正确const和非const版本是否混淆。6.5 与STL行为对齐的细节插入返回值std::map::insert返回pairiterator, bool其中iterator指向已存在或新插入的元素。我们的实现也要保持一致。map的operator[]如果key不存在它会插入一个用默认值初始化的value并返回其引用。我们的实现依赖V类型有默认构造函数。对于没有默认构造函数的类型operator[]可能无法使用。set的迭代器是const的这是一个容易忽略的细节。在STL中setT::iterator实际上是setT::const_iterator的别名解引用后得到的是const T。我们的实现也最好遵循这一约定防止用户修改set的元素。7. 性能考量与扩展思考7.1 时间复杂度分析红黑树保证了最坏情况下插入、删除、查找的时间复杂度都是O(log n)其中n是元素个数。这是它作为map和set底层容器的底气。虽然不如哈希表的平均O(1)快但红黑树能维持元素有序性这是哈希表做不到的。map和set的迭代器遍历是中序有序的。7.2 与unordered_map/set的对比C11引入了基于哈希表的unordered_map和unordered_set。它们提供平均O(1)的查找效率但不保证元素顺序。选择哪个需要元素有序或者需要按顺序遍历 - 选择map/set红黑树。追求极致的查找、插入速度且不关心顺序 - 选择unordered_map/unordered_set哈希表。注意哈希表在最坏情况下大量哈希冲突会退化到O(n)而红黑树始终稳定在O(log n)。7.3 可能的优化方向内存池频繁的new和delete节点会影响性能。可以实现一个简单的内存池一次性申请一大块内存自己管理节点的分配与回收。缓存友好性红黑树节点在内存中是不连续的对CPU缓存不友好。在某些特定场景下可以考虑使用B树变体但实现复杂度更高。支持透明比较C14C14为关联容器引入了“透明比较”特性允许查找时使用与键类型不同的类型进行比较例如用string查找mapstring, int时可以直接传递string_view避免不必要的临时对象构造。这需要让我们的KeyOfValue仿函数和比较逻辑支持多类型。自己动手实现一遍这个项目你会对C模板、数据结构、STL设计有脱胎换骨的理解。它就像打通任督二脉之前很多模糊的概念比如“迭代器为什么这么设计”、“模板如何实现泛型”都会变得无比清晰。下次当你再使用std::map时你看到的将不再是一个黑盒容器而是一棵在内存中优雅旋转的红黑树以及背后精妙绝伦的抽象艺术。
