1. 项目概述从使用者到造轮子如果你用过C的STL那对std::set肯定不陌生。它就像一个自动帮你排好序、还不允许重复的智能数组无论是做去重、快速查找还是维护一个有序集合都离不开它。但用久了尤其是面试被问到“set底层是怎么实现的”时心里难免会有点虚。光知道它是红黑树和背八股文没什么区别。真正能让你把这块知识焊死在脑子里的方法就是自己动手从零开始模拟实现一个set。这个项目就是带你走一遍这个“造轮子”的过程。它不仅仅是把红黑树的代码抄一遍更重要的是理解STL设计者是如何将复杂的底层数据结构红黑树封装成一个简洁、易用、类型安全的容器接口的。你会遇到迭代器封装、模板适配、const正确性处理等一系列经典问题每一个都是C中高级编程的试金石。通过这个项目你能彻底搞明白为什么set的迭代器是const的为什么insert返回一个pair以及红黑树是如何通过旋转和变色来维持平衡的。这远比死记硬背面试题来得扎实。2. 核心设计理解set与红黑树的适配关系在动手写代码之前我们必须先理清最核心的设计思路set本身并不直接管理数据它只是一个“外壳”内部真正干活的是一个红黑树RBTree类。这种设计模式在STL中非常常见map、unordered_set等容器也是如此。2.1 为什么是红黑树你可能知道set底层是红黑树但为什么是它而不是AVL树或者普通的二叉搜索树BST平衡性与效率的折衷AVL树是严格平衡的查找效率极致O(logN)但插入/删除时为了维持平衡旋转操作更频繁。红黑树是一种“近似平衡”的二叉搜索树它确保从根到叶子的最长路径不会超过最短路径的两倍。这种宽松的平衡条件使得它在插入和删除节点时需要旋转的情况比AVL树少整体性能更均衡。对于综合性的容器红黑树是更优的选择。稳定迭代器红黑树的插入和删除操作大部分情况下不会改变整个树的结构性连接指非根节点路径的大规模改变这使得迭代器在操作后不容易失效除了指向被删除元素的迭代器这是一个非常重要的容器特性。所以我们的首要任务是先实现一个通用的、模板化的红黑树。这个红黑树要足够“通用”以便set和map都能复用。set存储单个键值K而map存储键值对pairK, V。这就要求我们的红黑树节点能存储不同类型的数据T同时又能从中提取出用于比较的“键”。2.2 关键设计仿函数Functor提取键值这是实现通用红黑树的核心技巧。我们给红黑树类增加第三个模板参数KeyOfT从数据T中提取Key的仿函数。templateclass K, class T, class KeyOfT class RBTree { // ... 内部使用 KeyOfT 来比较节点 };对于set它存储的数据T就是键K。所以它的提取仿函数非常简单直接返回自身templateclass K class set { struct SetKeyOfT { const K operator()(const K key) { return key; // 数据就是键直接返回 } }; private: RBTreeK, K, SetKeyOfT _t; // 红黑树存储K并用SetKeyOfT提取K };对于map虽然本项目不实现但有助于理解存储的数据T是pairconst K, V提取仿函数就需要返回pair.firsttemplateclass K, class V class map { struct MapKeyOfT { const K operator()(const std::pairconst K, V kv) { return kv.first; // 从pair中提取出key } }; private: RBTreeK, std::pairconst K, V, MapKeyOfT _t; };通过这个设计红黑树内部的比较逻辑查找插入位置、判断是否重复等就可以统一使用KeyOfT()(data)来获取键值从而与具体的数据类型T解耦。这是STL设计中非常精妙的一个点。2.3 set的迭代器全是const迭代器这是set模拟实现中最容易踩坑的地方之一。set的元素键值是不允许被修改的因为修改键值可能会破坏红黑树的有序性。因此STL中setT::iterator和setT::const_iterator本质上是同一个类型——都是常量迭代器。在我们的实现中这意味着set的begin()和end()返回的应该是const_iterator。即使我们通过iterator类型去接收这个iterator也应该是const_iterator的别名。红黑树需要同时提供普通迭代器和常量迭代器但set只暴露常量迭代器的接口。如何实现呢我们会在迭代器部分详细展开核心是利用模板和类型别名让set的iterator直接指向红黑树的const_iterator。3. 红黑树基础实现在封装set之前我们必须先搭建好红黑树这个底层引擎。这里会涵盖节点结构、插入操作以及旋转调整这是整个项目的基石。3.1 节点与树结构定义红黑树节点需要存储数据、颜色标记以及三个指针。颜色我们用一个枚举类型来定义比用布尔值更清晰。// 颜色枚举 enum Colour { RED, BLACK }; // 红黑树节点模板类 templateclass T struct RBTreeNode { RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; // 父指针用于回溯调整 T _data; // 存储的数据可能是Kset或pairK,Vmap Colour _col; // 节点颜色 RBTreeNode(const T data) : _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _data(data) {} };注意新节点默认颜色为红色。这是红黑树规则决定的将新节点设为红色可能违反“不能有连续红节点”的规则但可以通过局部调整解决如果设为黑色则必然违反“每条路径黑色节点数相同”的规则调整起来更麻烦。红黑树类的框架如下包含了后续实现所需的成员和方法声明templateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: // 迭代器相关声明后续实现 typedef __RBTreeIteratorT, T*, T iterator; typedef __RBTreeIteratorT, const T*, const T const_iterator; // 构造函数、析构函数等 RBTree() : _root(nullptr) {} // 核心接口 pairiterator, bool insert(const T data); iterator find(const K key); // ... 其他接口如 erase, size 等 private: void RotateL(Node* parent); // 左旋 void RotateR(Node* parent); // 右旋 // ... 其他辅助函数 private: Node* _root nullptr; };3.2 插入操作与平衡调整红黑树的插入分为两步1) 按照二叉搜索树规则找到插入位置并插入新节点2) 检查并调整颜色和结构以满足红黑树的五条性质。调整是插入的难点。第一步二叉搜索树插入这部分和普通BST插入类似但需要使用KeyOfT仿函数来比较。pairiterator, bool insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; // 根节点必须为黑 return make_pair(iterator(_root), true); } KeyOfT kot; // 仿函数对象 Node* parent nullptr; Node* cur _root; // 寻找插入位置 while (cur) { parent cur; if (kot(data) kot(cur-_data)) cur cur-_right; else if (kot(data) kot(cur-_data)) cur cur-_left; else // 键值已存在插入失败 return make_pair(iterator(cur), false); } // 创建新节点并链接 cur new Node(data); // 新节点为红色 Node* newnode cur; // 保存新节点指针用于返回 if (kot(data) kot(parent-_data)) parent-_left cur; else parent-_right cur; cur-_parent parent; // ... 第二步颜色调整 }第二步颜色调整核心新节点cur为红色其父节点parent也是红色时违反“红节点不能连续”的规则需要调整。调整情况主要取决于叔叔节点uncle的颜色。情况一叔叔存在且为红处理方式将父节点和叔叔节点变黑祖父节点变红然后将cur指向祖父节点继续向上检查。while (parent parent-_col RED) { Node* grandparent parent-_parent; if (parent grandparent-_left) { Node* uncle grandparent-_right; if (uncle uncle-_col RED) { // 情况一叔叔为红 parent-_col uncle-_col BLACK; grandparent-_col RED; // 继续向上调整 cur grandparent; parent cur-_parent; } else { // 情况二/三叔叔为黑或不存在 // ... 见下文 } } else { // parent是grandparent的右孩子对称情况 // ... 对称处理 } } _root-_col BLACK; // 最后确保根节点为黑情况二与三叔叔为黑或不存在这种情况需要通过旋转来解决。旋转分为左旋和右旋是平衡二叉树的基本操作。左旋 (RotateL): 以某个节点为支点将其右子节点提升为新的子树根。右旋 (RotateR): 以某个节点为支点将其左子节点提升为新的子树根。当parent是grandparent的左孩子时情况二cur是parent的左孩子直线型处理对grandparent进行右旋然后将parent变黑grandparent变红。情况三cur是parent的右孩子折线型处理先对parent进行左旋转换成情况二再对grandparent进行右旋然后将cur变黑grandparent变红。// 接上面 else 部分 // 情况二/三叔叔为黑或不存在 if (cur parent-_left) { // 情况二直线型 // g(B) p(B) // / \ / \ // p(R) u(B) c(R) g(R) // / \ // c(R) u(B) RotateR(grandparent); grandparent-_col RED; parent-_col BLACK; } else { // 情况三折线型 // g(B) g(B) c(B) // / \ / \ / \ // p(R) u(B) c(R) u(B) p(R) g(R) // \ / \ // c(R) p(R) u(B) RotateL(parent); RotateR(grandparent); grandparent-_col RED; cur-_col BLACK; } break; // 调整完成后树已平衡退出循环parent是grandparent右孩子的对称情况逻辑镜像处理即可。旋转的具体实现我们稍后给出。3.3 旋转操作实现旋转操作需要仔细处理节点间六个指针的指向关系并更新父指针。// 右单旋 (以parent为旋转中心) void RotateR(Node* parent) { Node* cur parent-_left; Node* curright cur-_right; // 1. cur的右子树 成为 parent的左子树 parent-_left curright; if (curright) { curright-_parent parent; } // 2. parent 成为 cur的右孩子 cur-_right parent; // 3. 更新原parent的父节点对cur的指向 Node* ppnode parent-_parent; parent-_parent cur; if (parent _root) { // parent是根节点 _root cur; cur-_parent nullptr; } else { // parent不是根 if (ppnode-_left parent) { ppnode-_left cur; } else { ppnode-_right cur; } cur-_parent ppnode; } } // 左单旋 (以parent为旋转中心) void RotateL(Node* parent) { Node* cur parent-_right; Node* curleft cur-_left; // 1. cur的左子树 成为 parent的右子树 parent-_right curleft; if (curleft) { curleft-_parent parent; } // 2. parent 成为 cur的左孩子 cur-_left parent; // 3. 更新原parent的父节点对cur的指向 Node* ppnode parent-_parent; parent-_parent cur; if (parent _root) { _root cur; cur-_parent nullptr; } else { if (ppnode-_left parent) { ppnode-_left cur; } else { ppnode-_right cur; } cur-_parent ppnode; } }实操心得写旋转代码时最容易出错的就是父指针_parent的更新。一定要画图按照“断开旧链接 - 建立新链接 - 更新父指针”三步走每一步都对应图上箭头的改变。写完代码后用简单的三个节点例如左旋父节点、右子节点、右子节点的左孩子模拟一遍确保所有指针都指向正确。4. 迭代器封装让树可遍历红黑树自己不会遍历我们需要实现迭代器让set的用户能用for(auto e : set)这样的方式访问元素。红黑树的迭代器是双向迭代器需要支持和--操作。4.1 迭代器类框架迭代器本质上是一个包装了节点指针的类通过重载运算符来模拟指针的行为。templateclass T, class Ptr, class Ref // Ptr: 指针类型 Ref: 引用类型 struct __RBTreeIterator { typedef RBTreeNodeT Node; typedef __RBTreeIteratorT, Ptr, Ref Self; // 自身类型别名 Node* _node; // 迭代器内部持有的节点指针 __RBTreeIterator(Node* node) : _node(node) {} // 解引用获取节点数据的引用 Ref operator*() { return _node-_data; } // 成员访问操作符用于访问数据成员的指针例如迭代器指向pair时可用-first Ptr operator-() { return (_node-_data); } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } // 前置 Self operator(); // 前置-- Self operator--(); };这里使用了三个模板参数T,Ptr,Ref是为了能同时定义出普通迭代器和常量迭代器普通迭代器__RBTreeIteratorT, T*, T常量迭代器__RBTreeIteratorT, const T*, const T4.2 核心operator中序遍历后继红黑树迭代器遍历的顺序是中序遍历左-根-右这恰好能输出有序序列。operator的目的就是找到当前节点在中序序列中的后继节点。寻找后继的规则如果当前节点_node的右子树不为空则后继节点是右子树中的最左节点。如果当前节点_node的右子树为空则需要向上回溯。沿着父指针向上走直到找到某个节点是其父节点的左孩子那么这个父节点就是后继节点。如果回溯到根节点也没找到说明当前节点已是最后一个元素后继为nullptr即end()。Self operator() { if (_node-_right) { // 情况1右子树存在找右子树的最左节点 Node* cur _node-_right; while (cur-_left) { cur cur-_left; } _node cur; } else { // 情况2右子树为空向上回溯 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_right) { // 如果cur是parent的右孩子说明parent这颗子树已遍历完继续向上 cur parent; parent parent-_parent; } // 当cur变成parent的左孩子时parent就是后继 // 或者parent为空cur是整棵树最右节点则_node置为nullptr _node parent; } return *this; }4.3 核心operator--中序遍历前驱operator--是operator的逆过程寻找中序序列中的前驱节点。寻找前驱的规则如果当前节点_node的左子树不为空则前驱节点是左子树中的最右节点。如果当前节点_node的左子树为空则向上回溯。沿着父指针向上走直到找到某个节点是其父节点的右孩子那么这个父节点就是前驱节点。Self operator--() { if (_node-_left) { // 情况1左子树存在找左子树的最右节点 Node* cur _node-_left; while (cur-_right) { cur cur-_right; } _node cur; } else { // 情况2左子树为空向上回溯 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_left) { cur parent; parent parent-_parent; } _node parent; } return *this; }注意事项begin()返回的是树中最左节点的迭代器end()通常返回一个用nullptr构造的迭代器。operator走到最后一个节点后再就会得到end()。operator--从end()即nullptr开始应该得到最后一个节点的迭代器但我们的简单实现可能不支持更健壮的实现需要在迭代器或树中维护一个哨兵节点这属于更高级的话题。4.4 在红黑树中提供迭代器接口红黑树类需要提供begin()和end()方法以及迭代器类型定义。templateclass K, class T, class KeyOfT class RBTree { public: typedef __RBTreeIteratorT, T*, T iterator; typedef __RBTreeIteratorT, const T*, const T const_iterator; iterator begin() { Node* leftMin _root; while (leftMin leftMin-_left) { leftMin leftMin-_left; } return iterator(leftMin); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* leftMin _root; while (leftMin leftMin-_left) { leftMin leftMin-_left; } return const_iterator(leftMin); } const_iterator end() const { return const_iterator(nullptr); } // ... 其他成员 };5. set的封装与const迭代器难题有了强大的红黑树引擎set的封装就相对简单了。但正如前面提到的set的迭代器必须是const的这带来了一个关键问题。5.1 set类的基本框架namespace MySTL { // 建议放在自己的命名空间里 templateclass K class set { // 仿函数从数据K中提取键对于set就是K本身 struct SetKeyOfT { const K operator()(const K key) const { return key; } }; public: // 关键点迭代器类型定义 typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator; typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator; iterator begin() const { return _t.begin(); } iterator end() const { return _t.end(); } // 插入接口 std::pairiterator, bool insert(const K key) { // 调用红黑树的insert它返回 pairRBTree::iterator, bool std::pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key); // 需要将 RBTree::iterator 转换成 set::iterator (即 const_iterator) return std::pairiterator, bool(ret.first, ret.second); } // 查找等其他接口... private: RBTreeK, K, SetKeyOfT _t; // 底层红黑树 }; }注意看typedef那两行我们把set的iterator和const_iterator都定义为红黑树的const_iterator。这意味着通过set::iterator也无法修改元素值。5.2 插入返回值类型转换的坑问题出现在insert函数。红黑树的insert返回的是pairRBTree::iterator, bool。而set的insert需要返回pairset::iterator, bool即pairconst_iterator, bool。这里存在一个类型转换我们需要将RBTree::iterator普通迭代器转换为RBTree::const_iterator。如果直接构造pairconst_iterator, bool(ret.first, ret.second)编译器会报错因为ret.first是普通迭代器类型无法直接用于初始化const_iterator对象。解决方案在迭代器类中添加一个构造函数允许从普通迭代器构造出常量迭代器。templateclass T, class Ptr, class Ref struct __RBTreeIterator { // ... 其他成员 typedef __RBTreeIteratorT, T*, T Iterator; // 普通迭代器类型 // 从普通迭代器构造常量迭代器的构造函数 __RBTreeIterator(const Iterator it) : _node(it._node) // 直接拷贝节点指针 {} };这个构造函数使得const_iterator可以从iterator隐式转换而来。这样在set::insert中pairiterator, bool(ret.first, ret.second)这行代码就能顺利编译了因为ret.firstRBTree::iterator可以用于构造一个临时的const_iterator对象。5.3 完善set接口除了insert和迭代器set还应提供一些常用接口实现起来基本就是调用红黑树的对应接口。// 在set类中添加 iterator find(const K key) const { return _t.Find(key); // 红黑树的Find返回iterator这里自动转换为const_iterator } bool erase(const K key) { return _t.Erase(key); } size_t size() const { // 需要在红黑树中维护一个_size成员插入删除时更新 return _t.Size(); } bool empty() const { return _t.Empty(); } void clear() { _t.Clear(); }实操心得set的find返回的也应该是const_iterator。由于我们之前将set::iterator定义为const_iterator所以直接返回红黑树Find的结果即可类型转换是安全的。这体现了设计的一致性。6. 测试与调试验证你的模拟实现写代码不测试等于没写。我们需要编写测试用例验证set的基本功能是否正确。6.1 基础功能测试创建一个测试文件test_set.cpp#include Set.h // 你的set头文件 #include iostream #include vector using namespace MySTL; // 你的命名空间 void TestSet1() { std::cout 测试1: 插入与去重 std::endl; setint s; int arr[] {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; for (auto e : arr) { auto ret s.insert(e); std::cout 插入 e : (ret.second ? 成功 : 失败(重复)) std::endl; } // 尝试插入重复元素 auto ret s.insert(4); std::cout 再次插入 4 : (ret.second ? 成功 : 失败(重复)) std::endl; std::cout 中序遍历结果应有序: ; for (auto e : s) { std::cout e ; } std::cout std::endl; } void TestSet2() { std::cout \n 测试2: 迭代器与查找 std::endl; setstd::string s; s.insert(apple); s.insert(banana); s.insert(cherry); s.insert(date); std::cout set内容: ; for (auto it s.begin(); it ! s.end(); it) { std::cout *it ; } std::cout std::endl; auto it s.find(banana); if (it ! s.end()) { std::cout 找到 banana std::endl; // *it berry; // 这行代码应该编译报错验证iterator是const } else { std::cout 未找到 banana std::endl; } it s.find(elderberry); if (it s.end()) { std::cout 未找到 elderberry (符合预期) std::endl; } } void TestSet3() { std::cout \n 测试3: 范围for与拷贝 std::endl; setint s; for (int i 10; i 0; --i) { s.insert(i * 2); } std::cout 使用范围for循环: ; for (int x : s) { std::cout x ; } std::cout std::endl; // 测试拷贝构造和赋值需要实现拷贝控制成员函数 // setint s2(s); // std::cout 拷贝构造s2: ; // for (int x : s2) std::cout x ; // std::cout std::endl; } int main() { TestSet1(); TestSet2(); TestSet3(); return 0; }6.2 常见问题与调试技巧在实现过程中你几乎一定会遇到程序崩溃或逻辑错误。以下是一些常见问题和排查思路插入时程序崩溃访问空指针检查点在红黑树插入的while (parent parent-_col RED)循环中访问grandparent即parent-_parent前是否确保parent不为空在向上调整时cur和parent更新后新的parent可能为空当cur调整到根节点时。调试方法在旋转和颜色调整的代码中插入大量断言assert例如assert(parent ! nullptr);assert(grandparent ! nullptr);。使用调试器单步跟踪插入过程观察指针状态。迭代器或--时死循环或越界检查点operator中当_node-_right为空时向上回溯的循环条件while (parent cur parent-_right)是否正确确保cur和parent能正确向上移动。operator--同理。调试方法构造一棵简单的小树如3个节点手动计算其中序遍历序列然后用调试器一步步跟踪迭代器的操作看指针移动路径是否符合预期。内存泄漏检查点目前我们只实现了插入没有实现析构函数和erase操作。new的节点没有delete。临时解决在红黑树类的析构函数中实现一个后序遍历删除所有节点。这是一个很好的练习。~RBTree() { _Destroy(_root); _root nullptr; } void _Destroy(Node* root) { if (root nullptr) return; _Destroy(root-_left); _Destroy(root-_right); delete root; }set的iterator无法修改元素编译错误检查这是正确行为说明你的const迭代器设计成功了。尝试写测试代码*it 10;应该编译不通过。红黑树性质被破坏检查点实现一个辅助函数递归检查红黑树的五个性质每个节点非红即黑。根节点是黑色。所有叶子节点NIL节点我们实现中用空指针表示都是黑色。红色节点的两个子节点都是黑色。不能有连续红节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。调试方法在每次插入操作后调用这个检查函数。如果检查失败打印出树的结构可以层序遍历打印节点值和颜色与手动推导的结果对比。7. 进阶思考与扩展一个基本的set模拟实现已经完成了。但如果你想更深入地理解STL或者让这个项目成为你简历上的亮点可以考虑以下扩展实现map这是最直接的扩展。基于现有的红黑树实现map类。关键区别在于节点存储的数据类型是pairconst K, V。定义MapKeyOfT仿函数从pair中提取first作为键。map的迭代器解引用得到的是pairconst K, V其first是const的但second可以修改。map的operator[]是一个重头戏它需要实现“如果key不存在则插入一个默认值的pair并返回其引用”的语义。实现erase删除操作红黑树的删除是比插入更复杂的操作需要考虑更多种情况下的颜色调整。这是检验你对红黑树理解深度的绝佳挑战。实现拷贝控制完整的容器需要支持拷贝构造、拷贝赋值、移动构造、移动赋值和析构深拷贝。这涉及到树的复制需要递归地复制整个树结构。添加更多STL风格接口如lower_bound、upper_bound、equal_range、count等。这些接口在有序容器中非常有用。性能分析与优化对比你的set和std::set在大量数据插入、查找时的性能。思考红黑树节点中的父指针_parent是否必须能否实现无父指针的红黑树这会对迭代器/--操作带来什么挑战了解“内存池”概念尝试为节点分配设计一个简单的内存池减少频繁new/delete的开销。通过这个从零模拟实现set的项目你收获的不仅仅是一个能运行的容器类。你深入了红黑树这一经典数据结构的内部理解了迭代器如何将底层复杂遍历封装成简单的指针抽象解决了C模板编程和const正确性中的典型问题。下次面试官再问你set的底层你完全可以自信地从红黑树节点结构讲到迭代器封装甚至和他讨论删除操作的实现细节。这才是真正的“理解”而非“背诵”。
1. 项目概述从使用者到造轮子如果你用过C的STL那对std::set肯定不陌生。它就像一个自动帮你排好序、还不允许重复的智能数组无论是做去重、快速查找还是维护一个有序集合都离不开它。但用久了尤其是面试被问到“set底层是怎么实现的”时心里难免会有点虚。光知道它是红黑树和背八股文没什么区别。真正能让你把这块知识焊死在脑子里的方法就是自己动手从零开始模拟实现一个set。这个项目就是带你走一遍这个“造轮子”的过程。它不仅仅是把红黑树的代码抄一遍更重要的是理解STL设计者是如何将复杂的底层数据结构红黑树封装成一个简洁、易用、类型安全的容器接口的。你会遇到迭代器封装、模板适配、const正确性处理等一系列经典问题每一个都是C中高级编程的试金石。通过这个项目你能彻底搞明白为什么set的迭代器是const的为什么insert返回一个pair以及红黑树是如何通过旋转和变色来维持平衡的。这远比死记硬背面试题来得扎实。2. 核心设计理解set与红黑树的适配关系在动手写代码之前我们必须先理清最核心的设计思路set本身并不直接管理数据它只是一个“外壳”内部真正干活的是一个红黑树RBTree类。这种设计模式在STL中非常常见map、unordered_set等容器也是如此。2.1 为什么是红黑树你可能知道set底层是红黑树但为什么是它而不是AVL树或者普通的二叉搜索树BST平衡性与效率的折衷AVL树是严格平衡的查找效率极致O(logN)但插入/删除时为了维持平衡旋转操作更频繁。红黑树是一种“近似平衡”的二叉搜索树它确保从根到叶子的最长路径不会超过最短路径的两倍。这种宽松的平衡条件使得它在插入和删除节点时需要旋转的情况比AVL树少整体性能更均衡。对于综合性的容器红黑树是更优的选择。稳定迭代器红黑树的插入和删除操作大部分情况下不会改变整个树的结构性连接指非根节点路径的大规模改变这使得迭代器在操作后不容易失效除了指向被删除元素的迭代器这是一个非常重要的容器特性。所以我们的首要任务是先实现一个通用的、模板化的红黑树。这个红黑树要足够“通用”以便set和map都能复用。set存储单个键值K而map存储键值对pairK, V。这就要求我们的红黑树节点能存储不同类型的数据T同时又能从中提取出用于比较的“键”。2.2 关键设计仿函数Functor提取键值这是实现通用红黑树的核心技巧。我们给红黑树类增加第三个模板参数KeyOfT从数据T中提取Key的仿函数。templateclass K, class T, class KeyOfT class RBTree { // ... 内部使用 KeyOfT 来比较节点 };对于set它存储的数据T就是键K。所以它的提取仿函数非常简单直接返回自身templateclass K class set { struct SetKeyOfT { const K operator()(const K key) { return key; // 数据就是键直接返回 } }; private: RBTreeK, K, SetKeyOfT _t; // 红黑树存储K并用SetKeyOfT提取K };对于map虽然本项目不实现但有助于理解存储的数据T是pairconst K, V提取仿函数就需要返回pair.firsttemplateclass K, class V class map { struct MapKeyOfT { const K operator()(const std::pairconst K, V kv) { return kv.first; // 从pair中提取出key } }; private: RBTreeK, std::pairconst K, V, MapKeyOfT _t; };通过这个设计红黑树内部的比较逻辑查找插入位置、判断是否重复等就可以统一使用KeyOfT()(data)来获取键值从而与具体的数据类型T解耦。这是STL设计中非常精妙的一个点。2.3 set的迭代器全是const迭代器这是set模拟实现中最容易踩坑的地方之一。set的元素键值是不允许被修改的因为修改键值可能会破坏红黑树的有序性。因此STL中setT::iterator和setT::const_iterator本质上是同一个类型——都是常量迭代器。在我们的实现中这意味着set的begin()和end()返回的应该是const_iterator。即使我们通过iterator类型去接收这个iterator也应该是const_iterator的别名。红黑树需要同时提供普通迭代器和常量迭代器但set只暴露常量迭代器的接口。如何实现呢我们会在迭代器部分详细展开核心是利用模板和类型别名让set的iterator直接指向红黑树的const_iterator。3. 红黑树基础实现在封装set之前我们必须先搭建好红黑树这个底层引擎。这里会涵盖节点结构、插入操作以及旋转调整这是整个项目的基石。3.1 节点与树结构定义红黑树节点需要存储数据、颜色标记以及三个指针。颜色我们用一个枚举类型来定义比用布尔值更清晰。// 颜色枚举 enum Colour { RED, BLACK }; // 红黑树节点模板类 templateclass T struct RBTreeNode { RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; // 父指针用于回溯调整 T _data; // 存储的数据可能是Kset或pairK,Vmap Colour _col; // 节点颜色 RBTreeNode(const T data) : _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _data(data) {} };注意新节点默认颜色为红色。这是红黑树规则决定的将新节点设为红色可能违反“不能有连续红节点”的规则但可以通过局部调整解决如果设为黑色则必然违反“每条路径黑色节点数相同”的规则调整起来更麻烦。红黑树类的框架如下包含了后续实现所需的成员和方法声明templateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: // 迭代器相关声明后续实现 typedef __RBTreeIteratorT, T*, T iterator; typedef __RBTreeIteratorT, const T*, const T const_iterator; // 构造函数、析构函数等 RBTree() : _root(nullptr) {} // 核心接口 pairiterator, bool insert(const T data); iterator find(const K key); // ... 其他接口如 erase, size 等 private: void RotateL(Node* parent); // 左旋 void RotateR(Node* parent); // 右旋 // ... 其他辅助函数 private: Node* _root nullptr; };3.2 插入操作与平衡调整红黑树的插入分为两步1) 按照二叉搜索树规则找到插入位置并插入新节点2) 检查并调整颜色和结构以满足红黑树的五条性质。调整是插入的难点。第一步二叉搜索树插入这部分和普通BST插入类似但需要使用KeyOfT仿函数来比较。pairiterator, bool insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; // 根节点必须为黑 return make_pair(iterator(_root), true); } KeyOfT kot; // 仿函数对象 Node* parent nullptr; Node* cur _root; // 寻找插入位置 while (cur) { parent cur; if (kot(data) kot(cur-_data)) cur cur-_right; else if (kot(data) kot(cur-_data)) cur cur-_left; else // 键值已存在插入失败 return make_pair(iterator(cur), false); } // 创建新节点并链接 cur new Node(data); // 新节点为红色 Node* newnode cur; // 保存新节点指针用于返回 if (kot(data) kot(parent-_data)) parent-_left cur; else parent-_right cur; cur-_parent parent; // ... 第二步颜色调整 }第二步颜色调整核心新节点cur为红色其父节点parent也是红色时违反“红节点不能连续”的规则需要调整。调整情况主要取决于叔叔节点uncle的颜色。情况一叔叔存在且为红处理方式将父节点和叔叔节点变黑祖父节点变红然后将cur指向祖父节点继续向上检查。while (parent parent-_col RED) { Node* grandparent parent-_parent; if (parent grandparent-_left) { Node* uncle grandparent-_right; if (uncle uncle-_col RED) { // 情况一叔叔为红 parent-_col uncle-_col BLACK; grandparent-_col RED; // 继续向上调整 cur grandparent; parent cur-_parent; } else { // 情况二/三叔叔为黑或不存在 // ... 见下文 } } else { // parent是grandparent的右孩子对称情况 // ... 对称处理 } } _root-_col BLACK; // 最后确保根节点为黑情况二与三叔叔为黑或不存在这种情况需要通过旋转来解决。旋转分为左旋和右旋是平衡二叉树的基本操作。左旋 (RotateL): 以某个节点为支点将其右子节点提升为新的子树根。右旋 (RotateR): 以某个节点为支点将其左子节点提升为新的子树根。当parent是grandparent的左孩子时情况二cur是parent的左孩子直线型处理对grandparent进行右旋然后将parent变黑grandparent变红。情况三cur是parent的右孩子折线型处理先对parent进行左旋转换成情况二再对grandparent进行右旋然后将cur变黑grandparent变红。// 接上面 else 部分 // 情况二/三叔叔为黑或不存在 if (cur parent-_left) { // 情况二直线型 // g(B) p(B) // / \ / \ // p(R) u(B) c(R) g(R) // / \ // c(R) u(B) RotateR(grandparent); grandparent-_col RED; parent-_col BLACK; } else { // 情况三折线型 // g(B) g(B) c(B) // / \ / \ / \ // p(R) u(B) c(R) u(B) p(R) g(R) // \ / \ // c(R) p(R) u(B) RotateL(parent); RotateR(grandparent); grandparent-_col RED; cur-_col BLACK; } break; // 调整完成后树已平衡退出循环parent是grandparent右孩子的对称情况逻辑镜像处理即可。旋转的具体实现我们稍后给出。3.3 旋转操作实现旋转操作需要仔细处理节点间六个指针的指向关系并更新父指针。// 右单旋 (以parent为旋转中心) void RotateR(Node* parent) { Node* cur parent-_left; Node* curright cur-_right; // 1. cur的右子树 成为 parent的左子树 parent-_left curright; if (curright) { curright-_parent parent; } // 2. parent 成为 cur的右孩子 cur-_right parent; // 3. 更新原parent的父节点对cur的指向 Node* ppnode parent-_parent; parent-_parent cur; if (parent _root) { // parent是根节点 _root cur; cur-_parent nullptr; } else { // parent不是根 if (ppnode-_left parent) { ppnode-_left cur; } else { ppnode-_right cur; } cur-_parent ppnode; } } // 左单旋 (以parent为旋转中心) void RotateL(Node* parent) { Node* cur parent-_right; Node* curleft cur-_left; // 1. cur的左子树 成为 parent的右子树 parent-_right curleft; if (curleft) { curleft-_parent parent; } // 2. parent 成为 cur的左孩子 cur-_left parent; // 3. 更新原parent的父节点对cur的指向 Node* ppnode parent-_parent; parent-_parent cur; if (parent _root) { _root cur; cur-_parent nullptr; } else { if (ppnode-_left parent) { ppnode-_left cur; } else { ppnode-_right cur; } cur-_parent ppnode; } }实操心得写旋转代码时最容易出错的就是父指针_parent的更新。一定要画图按照“断开旧链接 - 建立新链接 - 更新父指针”三步走每一步都对应图上箭头的改变。写完代码后用简单的三个节点例如左旋父节点、右子节点、右子节点的左孩子模拟一遍确保所有指针都指向正确。4. 迭代器封装让树可遍历红黑树自己不会遍历我们需要实现迭代器让set的用户能用for(auto e : set)这样的方式访问元素。红黑树的迭代器是双向迭代器需要支持和--操作。4.1 迭代器类框架迭代器本质上是一个包装了节点指针的类通过重载运算符来模拟指针的行为。templateclass T, class Ptr, class Ref // Ptr: 指针类型 Ref: 引用类型 struct __RBTreeIterator { typedef RBTreeNodeT Node; typedef __RBTreeIteratorT, Ptr, Ref Self; // 自身类型别名 Node* _node; // 迭代器内部持有的节点指针 __RBTreeIterator(Node* node) : _node(node) {} // 解引用获取节点数据的引用 Ref operator*() { return _node-_data; } // 成员访问操作符用于访问数据成员的指针例如迭代器指向pair时可用-first Ptr operator-() { return (_node-_data); } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } // 前置 Self operator(); // 前置-- Self operator--(); };这里使用了三个模板参数T,Ptr,Ref是为了能同时定义出普通迭代器和常量迭代器普通迭代器__RBTreeIteratorT, T*, T常量迭代器__RBTreeIteratorT, const T*, const T4.2 核心operator中序遍历后继红黑树迭代器遍历的顺序是中序遍历左-根-右这恰好能输出有序序列。operator的目的就是找到当前节点在中序序列中的后继节点。寻找后继的规则如果当前节点_node的右子树不为空则后继节点是右子树中的最左节点。如果当前节点_node的右子树为空则需要向上回溯。沿着父指针向上走直到找到某个节点是其父节点的左孩子那么这个父节点就是后继节点。如果回溯到根节点也没找到说明当前节点已是最后一个元素后继为nullptr即end()。Self operator() { if (_node-_right) { // 情况1右子树存在找右子树的最左节点 Node* cur _node-_right; while (cur-_left) { cur cur-_left; } _node cur; } else { // 情况2右子树为空向上回溯 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_right) { // 如果cur是parent的右孩子说明parent这颗子树已遍历完继续向上 cur parent; parent parent-_parent; } // 当cur变成parent的左孩子时parent就是后继 // 或者parent为空cur是整棵树最右节点则_node置为nullptr _node parent; } return *this; }4.3 核心operator--中序遍历前驱operator--是operator的逆过程寻找中序序列中的前驱节点。寻找前驱的规则如果当前节点_node的左子树不为空则前驱节点是左子树中的最右节点。如果当前节点_node的左子树为空则向上回溯。沿着父指针向上走直到找到某个节点是其父节点的右孩子那么这个父节点就是前驱节点。Self operator--() { if (_node-_left) { // 情况1左子树存在找左子树的最右节点 Node* cur _node-_left; while (cur-_right) { cur cur-_right; } _node cur; } else { // 情况2左子树为空向上回溯 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_left) { cur parent; parent parent-_parent; } _node parent; } return *this; }注意事项begin()返回的是树中最左节点的迭代器end()通常返回一个用nullptr构造的迭代器。operator走到最后一个节点后再就会得到end()。operator--从end()即nullptr开始应该得到最后一个节点的迭代器但我们的简单实现可能不支持更健壮的实现需要在迭代器或树中维护一个哨兵节点这属于更高级的话题。4.4 在红黑树中提供迭代器接口红黑树类需要提供begin()和end()方法以及迭代器类型定义。templateclass K, class T, class KeyOfT class RBTree { public: typedef __RBTreeIteratorT, T*, T iterator; typedef __RBTreeIteratorT, const T*, const T const_iterator; iterator begin() { Node* leftMin _root; while (leftMin leftMin-_left) { leftMin leftMin-_left; } return iterator(leftMin); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* leftMin _root; while (leftMin leftMin-_left) { leftMin leftMin-_left; } return const_iterator(leftMin); } const_iterator end() const { return const_iterator(nullptr); } // ... 其他成员 };5. set的封装与const迭代器难题有了强大的红黑树引擎set的封装就相对简单了。但正如前面提到的set的迭代器必须是const的这带来了一个关键问题。5.1 set类的基本框架namespace MySTL { // 建议放在自己的命名空间里 templateclass K class set { // 仿函数从数据K中提取键对于set就是K本身 struct SetKeyOfT { const K operator()(const K key) const { return key; } }; public: // 关键点迭代器类型定义 typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator; typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator; iterator begin() const { return _t.begin(); } iterator end() const { return _t.end(); } // 插入接口 std::pairiterator, bool insert(const K key) { // 调用红黑树的insert它返回 pairRBTree::iterator, bool std::pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key); // 需要将 RBTree::iterator 转换成 set::iterator (即 const_iterator) return std::pairiterator, bool(ret.first, ret.second); } // 查找等其他接口... private: RBTreeK, K, SetKeyOfT _t; // 底层红黑树 }; }注意看typedef那两行我们把set的iterator和const_iterator都定义为红黑树的const_iterator。这意味着通过set::iterator也无法修改元素值。5.2 插入返回值类型转换的坑问题出现在insert函数。红黑树的insert返回的是pairRBTree::iterator, bool。而set的insert需要返回pairset::iterator, bool即pairconst_iterator, bool。这里存在一个类型转换我们需要将RBTree::iterator普通迭代器转换为RBTree::const_iterator。如果直接构造pairconst_iterator, bool(ret.first, ret.second)编译器会报错因为ret.first是普通迭代器类型无法直接用于初始化const_iterator对象。解决方案在迭代器类中添加一个构造函数允许从普通迭代器构造出常量迭代器。templateclass T, class Ptr, class Ref struct __RBTreeIterator { // ... 其他成员 typedef __RBTreeIteratorT, T*, T Iterator; // 普通迭代器类型 // 从普通迭代器构造常量迭代器的构造函数 __RBTreeIterator(const Iterator it) : _node(it._node) // 直接拷贝节点指针 {} };这个构造函数使得const_iterator可以从iterator隐式转换而来。这样在set::insert中pairiterator, bool(ret.first, ret.second)这行代码就能顺利编译了因为ret.firstRBTree::iterator可以用于构造一个临时的const_iterator对象。5.3 完善set接口除了insert和迭代器set还应提供一些常用接口实现起来基本就是调用红黑树的对应接口。// 在set类中添加 iterator find(const K key) const { return _t.Find(key); // 红黑树的Find返回iterator这里自动转换为const_iterator } bool erase(const K key) { return _t.Erase(key); } size_t size() const { // 需要在红黑树中维护一个_size成员插入删除时更新 return _t.Size(); } bool empty() const { return _t.Empty(); } void clear() { _t.Clear(); }实操心得set的find返回的也应该是const_iterator。由于我们之前将set::iterator定义为const_iterator所以直接返回红黑树Find的结果即可类型转换是安全的。这体现了设计的一致性。6. 测试与调试验证你的模拟实现写代码不测试等于没写。我们需要编写测试用例验证set的基本功能是否正确。6.1 基础功能测试创建一个测试文件test_set.cpp#include Set.h // 你的set头文件 #include iostream #include vector using namespace MySTL; // 你的命名空间 void TestSet1() { std::cout 测试1: 插入与去重 std::endl; setint s; int arr[] {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; for (auto e : arr) { auto ret s.insert(e); std::cout 插入 e : (ret.second ? 成功 : 失败(重复)) std::endl; } // 尝试插入重复元素 auto ret s.insert(4); std::cout 再次插入 4 : (ret.second ? 成功 : 失败(重复)) std::endl; std::cout 中序遍历结果应有序: ; for (auto e : s) { std::cout e ; } std::cout std::endl; } void TestSet2() { std::cout \n 测试2: 迭代器与查找 std::endl; setstd::string s; s.insert(apple); s.insert(banana); s.insert(cherry); s.insert(date); std::cout set内容: ; for (auto it s.begin(); it ! s.end(); it) { std::cout *it ; } std::cout std::endl; auto it s.find(banana); if (it ! s.end()) { std::cout 找到 banana std::endl; // *it berry; // 这行代码应该编译报错验证iterator是const } else { std::cout 未找到 banana std::endl; } it s.find(elderberry); if (it s.end()) { std::cout 未找到 elderberry (符合预期) std::endl; } } void TestSet3() { std::cout \n 测试3: 范围for与拷贝 std::endl; setint s; for (int i 10; i 0; --i) { s.insert(i * 2); } std::cout 使用范围for循环: ; for (int x : s) { std::cout x ; } std::cout std::endl; // 测试拷贝构造和赋值需要实现拷贝控制成员函数 // setint s2(s); // std::cout 拷贝构造s2: ; // for (int x : s2) std::cout x ; // std::cout std::endl; } int main() { TestSet1(); TestSet2(); TestSet3(); return 0; }6.2 常见问题与调试技巧在实现过程中你几乎一定会遇到程序崩溃或逻辑错误。以下是一些常见问题和排查思路插入时程序崩溃访问空指针检查点在红黑树插入的while (parent parent-_col RED)循环中访问grandparent即parent-_parent前是否确保parent不为空在向上调整时cur和parent更新后新的parent可能为空当cur调整到根节点时。调试方法在旋转和颜色调整的代码中插入大量断言assert例如assert(parent ! nullptr);assert(grandparent ! nullptr);。使用调试器单步跟踪插入过程观察指针状态。迭代器或--时死循环或越界检查点operator中当_node-_right为空时向上回溯的循环条件while (parent cur parent-_right)是否正确确保cur和parent能正确向上移动。operator--同理。调试方法构造一棵简单的小树如3个节点手动计算其中序遍历序列然后用调试器一步步跟踪迭代器的操作看指针移动路径是否符合预期。内存泄漏检查点目前我们只实现了插入没有实现析构函数和erase操作。new的节点没有delete。临时解决在红黑树类的析构函数中实现一个后序遍历删除所有节点。这是一个很好的练习。~RBTree() { _Destroy(_root); _root nullptr; } void _Destroy(Node* root) { if (root nullptr) return; _Destroy(root-_left); _Destroy(root-_right); delete root; }set的iterator无法修改元素编译错误检查这是正确行为说明你的const迭代器设计成功了。尝试写测试代码*it 10;应该编译不通过。红黑树性质被破坏检查点实现一个辅助函数递归检查红黑树的五个性质每个节点非红即黑。根节点是黑色。所有叶子节点NIL节点我们实现中用空指针表示都是黑色。红色节点的两个子节点都是黑色。不能有连续红节点从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。调试方法在每次插入操作后调用这个检查函数。如果检查失败打印出树的结构可以层序遍历打印节点值和颜色与手动推导的结果对比。7. 进阶思考与扩展一个基本的set模拟实现已经完成了。但如果你想更深入地理解STL或者让这个项目成为你简历上的亮点可以考虑以下扩展实现map这是最直接的扩展。基于现有的红黑树实现map类。关键区别在于节点存储的数据类型是pairconst K, V。定义MapKeyOfT仿函数从pair中提取first作为键。map的迭代器解引用得到的是pairconst K, V其first是const的但second可以修改。map的operator[]是一个重头戏它需要实现“如果key不存在则插入一个默认值的pair并返回其引用”的语义。实现erase删除操作红黑树的删除是比插入更复杂的操作需要考虑更多种情况下的颜色调整。这是检验你对红黑树理解深度的绝佳挑战。实现拷贝控制完整的容器需要支持拷贝构造、拷贝赋值、移动构造、移动赋值和析构深拷贝。这涉及到树的复制需要递归地复制整个树结构。添加更多STL风格接口如lower_bound、upper_bound、equal_range、count等。这些接口在有序容器中非常有用。性能分析与优化对比你的set和std::set在大量数据插入、查找时的性能。思考红黑树节点中的父指针_parent是否必须能否实现无父指针的红黑树这会对迭代器/--操作带来什么挑战了解“内存池”概念尝试为节点分配设计一个简单的内存池减少频繁new/delete的开销。通过这个从零模拟实现set的项目你收获的不仅仅是一个能运行的容器类。你深入了红黑树这一经典数据结构的内部理解了迭代器如何将底层复杂遍历封装成简单的指针抽象解决了C模板编程和const正确性中的典型问题。下次面试官再问你set的底层你完全可以自信地从红黑树节点结构讲到迭代器封装甚至和他讨论删除操作的实现细节。这才是真正的“理解”而非“背诵”。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
