从零实现C++ Set：AVL树原理、迭代器设计与工程实践 1. 项目概述为什么我们需要自己实现一个Set在C的日常开发中std::set几乎是每个开发者都会用到的标准库容器。它基于红黑树实现自动排序、元素唯一用起来非常顺手。但不知道你有没有想过当面试官问你“Set的底层原理是什么”或者“如果不允许使用STL你怎么实现一个集合”时你能否清晰地回答出来又或者当你遇到一些特殊场景比如需要极致的性能、特定的内存布局或者需要在嵌入式等受限环境中运行时标准库的std::set可能就不再是最优解了。这就是我们今天要动手做的从零开始用C完整地实现一个集合Set。这绝不是一个“重复造轮子”的练习。通过亲手实现你将彻底吃透集合数据结构背后的核心思想——无论是基于平衡二叉搜索树如AVL树、红黑树还是基于哈希表。你会对插入、删除、查找、遍历这些基本操作的时间复杂度有刻骨铭心的理解更能深刻体会到迭代器设计、内存管理、异常安全这些工程细节的微妙之处。对于中级开发者来说这是突破“API调用者”身份向“基础设施构建者”迈进的关键一步对于初学者这是一次将《数据结构》课本知识转化为可运行代码的绝佳实践。我们最终要实现的是一个功能完整、接口清晰、具有一定工业强度的MySet类。它将支持模板化以存储任意可比较类型提供完整的增删改查接口并实现一个前向迭代器用于范围遍历。我们将从最简单的二叉搜索树版本开始逐步探讨其性能瓶颈并引入AVL树来实现自平衡确保操作的效率。在这个过程中你会遇到并解决内存泄漏、迭代器失效、拷贝控制等C中的经典问题。2. 核心设计思路选择哪种数据结构作为基石实现一个集合首先要决定底层的数据结构。这直接决定了集合的性能特征和接口设计。我们主要对比两种主流方案树形结构和哈希结构。2.1 方案对比二叉搜索树 vs. 哈希表特性基于平衡二叉搜索树 (Tree-based Set)基于哈希表 (Hash-based Set)核心思想利用元素间的可比较性维护一棵有序树。利用哈希函数将元素映射到数组的特定位置。有序性天然有序。中序遍历即可得到升序序列。无序。元素存储顺序由哈希函数决定。平均时间复杂度插入、删除、查找O(log n)插入、删除、查找O(1)最坏时间复杂度退化为链表时O(n)哈希冲突严重时O(n)关键要求元素类型必须支持严格弱序比较定义或提供比较器。元素类型需要哈希函数和相等比较函数。内存开销每个节点需要存储左右子节点指针开销相对较大。需要维护一个桶数组可能存在空间浪费。实现复杂度中高尤其是实现自平衡逻辑如AVL、红黑树。中需要处理哈希冲突链地址法、开放寻址。设计决策对于通用的、教学性质的实现我们选择基于平衡二叉搜索树。理由如下1它保证了元素的有序性这是std::set的核心特性之一2其实现过程能更全面地覆盖数据结构树和算法旋转的知识点3模板和比较器的设计更具普适性不依赖哈希函数。我们将以实现一个AVL树为最终目标因为它比红黑树概念上更直观平衡因子适合学习。2.2 我们的MySet类蓝图基于以上选择我们的MySet类将围绕一棵AVL树展开。以下是核心设计要点模板化template typename Key, typename Compare std::lessKey。支持任何定义了操作符或指定了自定义比较器Compare的类型。内部节点结构struct Node包含键值Key key指向左右子节点的指针Node* left, *right节点高度int height用于AVL平衡以及可选的父节点指针简化迭代器实现但会增加开销。我们将先实现无父指针版本再讨论迭代器的挑战。核心数据成员一个Node* root_指针指向树的根节点一个Compare comp_比较器对象以及size_t size_记录元素个数。接口仿STL提供insert(),erase(),find(),count(),clear(),size(),empty()等成员函数。同时实现begin(),end()返回迭代器支持基于范围的for循环。迭代器设计迭代器需要能在树上进行中序遍历。我们将实现一个iterator和const_iterator类。为了在不存储父指针的情况下实现高效的操作我们可以在迭代器内部使用一个栈来模拟中序遍历过程但这会使迭代器的拷贝和移动成本变高。另一种更高效、更挑战性的方法是实现线索化二叉树或在节点中存储父指针。为了平衡复杂度和性能我们将在初始版本使用栈辅助并在进阶优化中讨论父指针方案。3. 从零构建基础二叉搜索树骨架在加入自平衡的魔法之前我们先搭建一个最朴素的二叉搜索树BST这是理解所有树形集合的起点。3.1 节点结构与类定义template typename Key, typename Compare std::lessKey class MySet { private: struct Node { Key key; Node* left; Node* right; // 为后续AVL树预留高度字段初始化为1 int height; Node(const Key k) : key(k), left(nullptr), right(nullptr), height(1) {} }; Node* root_; Compare comp_; size_t size_; public: // 构造函数、析构函数、拷贝控制函数后续实现 MySet() : root_(nullptr), size_(0) {} ~MySet() { clear(); } // 基础接口声明 bool insert(const Key key); bool erase(const Key key); bool find(const Key key) const; size_t size() const { return size_; } bool empty() const { return size_ 0; } void clear(); private: // 内部递归辅助函数 Node* insert(Node* node, const Key key); Node* erase(Node* node, const Key key); Node* find(Node* node, const Key key) const; void clear(Node* node); // 工具函数 Node* minValueNode(Node* node); // 找子树最小节点 };3.2 插入操作的实现与陷阱插入是BST的核心。递归实现逻辑清晰比较当前节点键值与待插入键值根据比较结果向左或向右子树递归直到到达空位置nullptr创建新节点。template typename Key, typename Compare bool MySetKey, Compare::insert(const Key key) { size_t oldSize size_; root_ insert(root_, key); return size_ oldSize; // 返回是否成功插入元素是否已存在 } template typename Key, typename Compare typename MySetKey, Compare::Node* MySetKey, Compare::insert(Node* node, const Key key) { // 递归基到达空位置创建新节点 if (node nullptr) { size_; return new Node(key); } // 递归步骤根据比较结果向左或向右 if (comp_(key, node-key)) { // key node-key node-left insert(node-left, key); } else if (comp_(node-key, key)) { // key node-key node-right insert(node-right, key); } else { // 键值相等集合不允许重复直接返回当前节点 return node; } // 注意这里暂时没有更新高度和平衡操作这是普通BST的实现。 // 对于AVL树此处需要更新节点高度并重新平衡。 return node; }实操心得这里有一个初学者极易忽略的内存所有权问题。insert辅助函数返回的是Node*这个指针必须被上层正确赋值。例如node-left insert(node-left, key);这确保了新创建的节点或未改变的子树能正确链接回树中。如果忘记赋值新节点就“丢失”了造成内存泄漏。3.3 查找与删除操作的细节查找操作相对直接。删除则复杂得多需要处理三种情况待删除节点是叶子节点直接删除父节点对应指针置空。待删除节点有一个子节点用其子节点替代自身。待删除节点有两个子节点这是最复杂的情况。需要找到其右子树中的最小节点或左子树中的最大节点用这个“后继”节点的值替换待删除节点的值然后递归地删除那个“后继”节点。因为后继节点至多只有一个子节点从而将问题简化为情况1或2。template typename Key, typename Compare bool MySetKey, Compare::erase(const Key key) { size_t oldSize size_; root_ erase(root_, key); return size_ oldSize; } template typename Key, typename Compare typename MySetKey, Compare::Node* MySetKey, Compare::erase(Node* node, const Key key) { if (node nullptr) return nullptr; // 未找到要删除的键 if (comp_(key, node-key)) { node-left erase(node-left, key); } else if (comp_(node-key, key)) { node-right erase(node-right, key); } else { // 找到要删除的节点 size_--; // 情况1 2: 有一个或零个子节点 if (node-left nullptr) { Node* temp node-right; delete node; return temp; } else if (node-right nullptr) { Node* temp node-left; delete node; return temp; } // 情况3: 有两个子节点 Node* successor minValueNode(node-right); // 找后继 node-key successor-key; // 用后继的值覆盖当前节点 // 递归删除后继节点现在它在右子树中 node-right erase(node-right, successor-key); } return node; // 同样对于AVL树这里需要更新高度和平衡 } template typename Key, typename Compare typename MySetKey, Compare::Node* MySetKey, Compare::minValueNode(Node* node) { Node* current node; while (current current-left ! nullptr) { current current-left; } return current; }注意事项在情况3中我们采用了“值拷贝”的策略。这要求Key类型是可拷贝构造/赋值的。如果Key是只移动类型或拷贝成本极高这种设计就有问题。std::set的处理方式更复杂它可能通过直接操作节点链接来避免拷贝但这需要非常小心地处理指针和内存。我们的实现以教学清晰为首要目标采用了值拷贝这种更安全的方式。4. 升级为AVL树赋予Set自平衡能力普通的BST在插入有序数据时会退化成链表操作复杂度降为O(n)。AVL树通过在每次插入和删除后检查并恢复树的平衡任意节点左右子树高度差不超过1来保证O(log n)的性能。4.1 AVL树的四大旋转平衡的维护通过四种旋转操作完成左旋 (Left Rotation)处理右子树过高的情况。右旋 (Right Rotation)处理左子树过高的情况。左右旋 (Left-Right Rotation)先左旋左子节点再右旋当前节点。处理左子树的右子树过高。右左旋 (Right-Left Rotation)先右旋右子节点再左旋当前节点。处理右子树的左子树过高。template typename Key, typename Compare typename MySetKey, Compare::Node* MySetKey, Compare::rightRotate(Node* y) { Node* x y-left; Node* T2 x-right; // 执行旋转 x-right y; y-left T2; // 更新高度 (必须先更新y的高度再更新x的因为y现在是x的子节点) y-height 1 std::max(getHeight(y-left), getHeight(y-right)); x-height 1 std::max(getHeight(x-left), getHeight(x-right)); // 返回新的根节点 return x; } template typename Key, typename Compare typename MySetKey, Compare::Node* MySetKey, Compare::leftRotate(Node* x) { Node* y x-right; Node* T2 y-left; // 执行旋转 y-left x; x-right T2; // 更新高度 x-height 1 std::max(getHeight(x-left), getHeight(x-right)); y-height 1 std::max(getHeight(y-left), getHeight(y-right)); return y; }getHeight是一个简单的辅助函数用于安全地获取节点高度处理nullptr。4.2 在插入和删除中集成平衡逻辑现在我们需要修改之前的insert和erase辅助函数在递归返回的路径上对每个节点更新其高度。计算平衡因子左子树高 - 右子树高。根据平衡因子和子树的不平衡情况执行相应的旋转。以insert为例修改后的平衡部分如下template typename Key, typename Compare typename MySetKey, Compare::Node* MySetKey, Compare::insert(Node* node, const Key key) { // ... (之前的递归插入逻辑不变) ... // 1. 更新当前节点的高度 node-height 1 std::max(getHeight(node-left), getHeight(node-right)); // 2. 获取当前节点的平衡因子 int balance getBalance(node); // getBalance height(left) - height(right) // 3. 根据平衡因子进行旋转调整 // 左左情况 (新节点插入在左子树的左子树) if (balance 1 comp_(key, node-left-key)) { return rightRotate(node); } // 右右情况 if (balance -1 comp_(node-right-key, key)) { return leftRotate(node); } // 左右情况 if (balance 1 comp_(node-left-key, key)) { node-left leftRotate(node-left); return rightRotate(node); } // 右左情况 if (balance -1 comp_(key, node-right-key)) { node-right rightRotate(node-right); return leftRotate(node); } // 平衡无需旋转 return node; }核心要点旋转操作不仅调整了指针还返回了新的子树根节点。这就是为什么我们必须用node-left insert(...)和return rightRotate(node)这样的形式确保旋转后新的局部根节点能正确链接回整棵树。erase操作中的平衡逻辑类似但判断条件稍有不同因为删除可能引起更复杂的不平衡传播。你需要检查删除后节点的平衡因子并进行相应的旋转。判断条件中的键值比较需要更谨慎因为被删除的节点可能已经不在那个位置了。一种通用的方法是像上面一样根据平衡因子和子树的平衡因子来决定旋转类型而不直接比较键值。5. 实现迭代器让MySet支持现代C循环没有迭代器的容器是不完整的。为树实现迭代器本质上是实现一个中序遍历的游标。5.1 迭代器类的设计我们采用栈辅助的方法。迭代器内部维护一个栈std::stackNode*用于存储待访问的节点路径。template typename Key, typename Compare class MySet { public: class iterator { private: std::stackNode* stk_; Node* current_; const MySet* set_; // 用于访问根节点实现end() // 私有构造函数仅供MySet的begin()/end()调用 iterator(Node* root, const MySet* set, bool isEnd false) : set_(set) { if (!isEnd) { // 初始化时沿着最左侧路径压栈 pushLeft(root); advance(); } else { current_ nullptr; } } void pushLeft(Node* node) { while (node) { stk_.push(node); node node-left; } } void advance() { if (stk_.empty()) { current_ nullptr; return; } current_ stk_.top(); stk_.pop(); // 当前节点的右子树的所有左节点是下一个访问序列 pushLeft(current_-right); } public: using iterator_category std::forward_iterator_tag; using value_type Key; using difference_type std::ptrdiff_t; using pointer const Key*; using reference const Key; iterator() : current_(nullptr), set_(nullptr) {} reference operator*() const { return current_-key; } pointer operator-() const { return (current_-key); } // 前缀 iterator operator() { advance(); return *this; } // 后缀 iterator operator(int) { iterator tmp *this; (*this); return tmp; } bool operator(const iterator other) const { // 注意比较current_指针即可。两个end()迭代器都是current_为nullptr。 return current_ other.current_; } bool operator!(const iterator other) const { return !(*this other); } friend class MySetKey, Compare; // 允许MySet访问私有构造函数 }; iterator begin() const { return iterator(root_, this); } iterator end() const { return iterator(nullptr, this, true); } // 还需要实现 const_iterator通常可以让iterator继承自一个基类或单独实现一个。 };5.2 迭代器实现的挑战与优化挑战1end()迭代器。我们通常将end()定义为最后一个元素之后的位置。对于树一个常见的做法是让end()迭代器内部current_为nullptr。begin()迭代器在走到最后一个元素后再次也会使current_变为nullptr从而与end()相等。挑战2修改操作导致迭代器失效。这是所有STL容器都面临的问题。对于我们的MySet任何插入或删除操作都可能通过旋转改变树的结构使得现有迭代器内部栈中存储的节点指针失效可能指向了被删除或移动的节点。因此我们必须声明插入和删除操作会使所有指向容器的迭代器失效。这与std::set的行为是一致的除了被删除元素的迭代器其他迭代器通常保持有效但实现起来极其复杂。优化方向父指针方案。栈辅助的迭代器每次拷贝成本较高需要拷贝整个栈。一个更高效的方案是在Node中增加Node* parent指针。这样迭代器只需要保存一个Node* current_。operator()的实现需要算法来找到中序遍历的后继节点如果当前节点有右子树后继是右子树中的最左节点。如果没有右子树则需要向上回溯直到找到一个节点它是其父节点的左子节点那么这个父节点就是后继。这种方案迭代器本身很小一个指针拷贝成本低但增加了每个节点的内存开销多一个指针并使得节点的插入、删除和旋转操作更复杂需要维护父指针的正确性。这是典型的空间换时间也是工业级实现如std::set通常基于红黑树节点包含父指针和颜色标记的常见选择。6. 完善与测试拷贝控制、内存管理与性能验证一个健壮的类必须妥善处理拷贝、赋值和移动。6.1 实现“三大件”或“五大件”template typename Key, typename Compare class MySet { public: // 1. 析构函数 ~MySet() { clear(); } // 2. 拷贝构造函数 (深拷贝) MySet(const MySet other) : root_(copyTree(other.root_)), comp_(other.comp_), size_(other.size_) {} // 3. 拷贝赋值运算符 (copy-and-swap 惯用法) MySet operator(MySet other) { // 注意参数按值传递自动调用拷贝构造 swap(*this, other); return *this; } // 4. 移动构造函数 MySet(MySet other) noexcept : root_(other.root_), comp_(std::move(other.comp_)), size_(other.size_) { other.root_ nullptr; other.size_ 0; } // 5. 移动赋值运算符 MySet operator(MySet other) noexcept { if (this ! other) { clear(); // 释放现有资源 root_ other.root_; comp_ std::move(other.comp_); size_ other.size_; other.root_ nullptr; other.size_ 0; } return *this; } friend void swap(MySet first, MySet second) noexcept { using std::swap; swap(first.root_, second.root_); swap(first.comp_, second.comp_); swap(first.size_, second.size_); } private: Node* copyTree(Node* node) { if (!node) return nullptr; Node* newNode new Node(node-key); newNode-height node-height; newNode-left copyTree(node-left); newNode-right copyTree(node-right); // 如果实现了父指针这里还需要设置父指针比较复杂。 return newNode; } };重要技巧copy-and-swap。拷贝赋值运算符的写法是C资源管理的经典技巧。通过按值传参我们让编译器自动完成了拷贝或移动构造。然后在函数体内交换*this和参数other的内容。函数返回时参数other被销毁自动释放了*this原来的资源。这种方法异常安全且代码简洁。6.2 编写测试验证功能与性能最后我们需要编写测试代码来验证MySet的正确性并和std::set进行简单性能对比。#include iostream #include vector #include algorithm #include cassert #include chrono #include set // 用于对比 void testBasicOperations() { MySetint s; assert(s.empty()); assert(s.size() 0); // 测试插入 auto [it1, inserted1] s.insert(5); // 需要修改insert返回pairiterator, bool assert(inserted1); assert(s.size() 1); assert(s.find(5)); auto [it2, inserted2] s.insert(5); assert(!inserted2); // 重复插入失败 assert(s.size() 1); s.insert(3); s.insert(7); s.insert(1); assert(s.size() 4); // 测试遍历有序性 std::vectorint vec; for (int x : s) { // 需要实现基于范围的for循环支持 vec.push_back(x); } assert(std::is_sorted(vec.begin(), vec.end())); // 测试查找 assert(s.find(3)); assert(!s.find(10)); // 测试删除 assert(s.erase(5)); assert(s.size() 3); assert(!s.find(5)); assert(!s.erase(5)); // 删除不存在的元素 s.clear(); assert(s.empty()); std::cout 所有基础测试通过 std::endl; } void performanceComparison() { const int N 100000; std::vectorint data(N); std::generate(data.begin(), data.end(), std::rand); // 测试 MySet auto start std::chrono::high_resolution_clock::now(); MySetint mySet; for (int x : data) mySet.insert(x); auto end std::chrono::high_resolution_clock::now(); auto mySetTime std::chrono::duration_caststd::chrono::milliseconds(end - start).count(); std::cout MySet 插入 N 个随机数耗时: mySetTime ms std::endl; // 测试 std::set start std::chrono::high_resolution_clock::now(); std::setint stdSet; for (int x : data) stdSet.insert(x); end std::chrono::high_resolution_clock::now(); auto stdSetTime std::chrono::duration_caststd::chrono::milliseconds(end - start).count(); std::cout std::set 插入 N 个随机数耗时: stdSetTime ms std::endl; // 注意我们的MySet是AVL树std::set通常是红黑树两者都是O(log n)。 // 性能差异可能来自内存分配、代码优化程度、编译器内联等。我们的实现通常会更慢这是正常的。 }7. 常见问题与进阶思考在实际实现和面试中你可能会遇到以下问题Q1我的迭代器在遍历过程中如果容器被修改了怎么办A1正如之前所述这会导致未定义行为。我们的实现以及std::set不提供这种稳定性保证。如果需要在遍历时修改一个常见的模式是先收集要删除的键遍历结束后再批量删除。Q2如何实现lower_bound和upper_bound函数A2这两个函数对于有序集合非常有用。lower_bound(k)返回第一个不小于k的元素的迭代器upper_bound(k)返回第一个大于k的元素的迭代器。实现它们需要在树中进行搜索记录“候选节点”。算法类似于查找但在找不到精确匹配时需要记录路径上最后一个可能符合条件的节点。Q3AVL树和红黑树在实际的STL实现中为什么多用红黑树A3虽然AVL树具有更严格的平衡条件查找更快但红黑树的平衡条件更宽松导致在插入和删除时需要进行的旋转操作更少。对于频繁插入删除的场景红黑树的综合性能更好。此外红黑树每个节点只需要1个bit存储颜色信息而AVL树需要存储高度通常是一个int。不过两者的操作都是O(log n)量级。Q4除了树和哈希表还有其他实现集合的方式吗A4对于小规模或特定类型的数据有序数组使用二分查找或位图Bitmap对于整数范围集合可能是更高效的选择。例如存储一个0-999的整数集合用一个1000位的位图查找和插入都是O(1)且极其节省空间。Q5如何让我的MySet支持透明比较器C14的std::lessA5透明比较器允许查找操作接受与Key类型不同的参数避免不必要的类型转换。这需要将比较器类型定义为Compare std::less并在find、count、lower_bound等函数中使用comp_(k, node-key)这种形式其中k可以是任何能与Key比较的类型。这要求比较器是“透明的”即定义了is_transparent类型。实现一个完整的集合容器是一次对C综合能力的深度锻炼。它迫使你思考数据结构的本质、算法的效率、类的设计、资源管理、迭代器抽象以及API的易用性。当你亲手调通第一个版本看着它通过所有测试并能与std::set在功能上媲美时你对C和数据结构理解会上一个坚实的台阶。这个过程中遇到的每一个编译错误和运行时bug都是最宝贵的经验。