C++红黑树封装map/set核心揭秘

是思成呀：个人主页

个人专栏《C++知识总结》《MySQL 零基础入门到实战》

前言：

C++ STL 中的map和set是典型的关联式容器，二者均基于红黑树实现，核心差异仅在于存储的数据类型（set存储单个键值、map存储键值对）。本文聚焦于如何通过泛型编程和仿函数技术，基于红黑树底层结构封装出符合 STL 风格的map和set，重点体现代码复用和类型适配的设计思想。

目录

一、先理清核心关联：map/set 与红黑树的绑定逻辑

1.1 红黑树的泛型设计（核心适配层）

1.2 set 与红黑树的关联：极简适配

1.3 map 与红黑树的关联：键值对适配

1.4 核心关联总结

二、迭代器的核心实现：基于红黑树的中序遍历

2.1 迭代器的基础结构（封装红黑树节点）

2.2 迭代器 ++ 实现：找中序后继节点（核心难点）

场景 1：当前节点有右子树

场景 2：当前节点无右子树

示例理解

2.3 迭代器 -- 实现：找中序前驱节点（对称逻辑）

2.4 红黑树的 begin/end 接口：迭代器的边界

三、迭代器的使用：map/set 遍历的底层逻辑

3.1 set 遍历：迭代器返回键值

3.2 map 遍历：迭代器返回键值对

四、核心总结

4.1 map/set 共用红黑树的核心

4.2 迭代器的核心逻辑

五、拓展：const 迭代器（补充）

结尾

一、先理清核心关联：map/set 与红黑树的绑定逻辑

map 和 set 并非重新实现红黑树，而是通过模板参数 + 仿函数，复用同一套红黑树代码，仅在 “存储数据类型” 和 “键值提取方式” 上做差异化适配。

1.1 红黑树的泛型设计（核心适配层）

红黑树通过三个模板参数实现对 map/set 的通用支持，这是关联的基础：

template<class K, class T, class KOfT>

1. K：键类型（如 map<int,V> 的 int，set<string> 的 string）
2. T：节点存储的实际数据类型（map 存 pair<K,V>，set 存 K）
3. KOfT：仿函数，用于从 T 中提取键 K（解决比较逻辑统一问题）
   

// 红黑树模板定义：适配 map/set 的核心 template<class K, class T, class KOfT> class RBTree { // 迭代器类型：对外暴露，供 map/set 复用 typedef __TreeIterator<T> iterator; private: RBTreeNode<T>* _root = nullptr; // 红黑树根节点 };

1.2 set 与红黑树的关联：极简适配

set 仅存储键值（无值关联），因此：

• 存储类型T = K（节点直接存键）；
• 仿函数SetKeyOfT直接返回键本身（无需提取）；
• 迭代器直接复用红黑树的iterator，解引用返回键值。

核心代码：

template<class K> class set { // 仿函数：从 T=K 中提取键（直接返回自身） struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: // 复用红黑树的迭代器：typename 声明嵌套类型（模板解析必须） typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; // 容器迭代器接口：直接调用红黑树的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } private: // set 持有的红黑树对象：T=K，用 SetKeyOfT 提取键 RBTree<K, K, SetKeyOfT> _t; };

1.3 map 与红黑树的关联：键值对适配

map 存储键值对pair<K,V>，因此：

• 存储类型T = pair<K,V>（节点存键值对）；
• 仿函数MapKeyOfT从pair中提取first（键）用于比较；
• 迭代器复用红黑树的iterator，解引用返回pair<K,V>，支持->first/second访问。

核心代码：

template<class K, class V> class map { // 仿函数：从 T=pair<K,V> 中提取键（pair.first） struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: // 复用红黑树的迭代器 typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; // 容器迭代器接口：调用红黑树的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } private: // map 持有的红黑树对象：T=pair<K,V>，用 MapKeyOfT 提取键 RBTree<K, pair<K, V>, MapKeyOfT> _t; };

1.4 核心关联总结

二、迭代器的核心实现：基于红黑树的中序遍历

map/set 的迭代器本质是红黑树节点指针的封装，其核心能力是通过重载++/--实现 “中序遍历”（红黑树中序遍历结果为有序序列，这是 map/set 有序性的根源）。

2.1 迭代器的基础结构（封装红黑树节点）

迭代器类的核心是持有红黑树节点指针，并重载基础运算符（解引用、箭头、比较），为遍历提供基础能力：

// 红黑树节点结构（迭代器的操作对象） template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data; // 存储的数据（set: K；map: pair<K,V>） Colour _col; RBTreeNode(const T& data) : _data(data), _col(RED), _left(nullptr), _right(nullptr), _parent(nullptr) {} }; // 迭代器核心类：封装节点指针，实现遍历逻辑 template<class T> struct __TreeIterator { typedef RBTreeNode<T> Node; typedef __TreeIterator<T> Self; Node* _node; // 核心：指向红黑树的节点 // 构造函数：接收节点指针初始化 __TreeIterator(Node* node) : _node(node) {} // 1. 解引用运算符：返回节点存储的数据 // set：返回 K&；map：返回 pair<K,V>& T& operator*() { return _node->_data; } // 2. 箭头运算符：支持 map 迭代器 it->first/it->second // 编译器优化：it-> 等价于 (*it). ，实际返回 &(_node->_data) T* operator->() { return &(_node->_data); } // 3. 比较运算符：判断迭代器是否指向同一节点（end() 是 nullptr） bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } // 4. ++/-- 运算符：核心逻辑，下文重点讲解 Self& operator++(); Self& operator--(); };

2.2 迭代器 ++ 实现：找中序后继节点（核心难点）

map/set 迭代器的++对应红黑树的中序遍历后继节点（保证遍历结果有序），分两种场景处理：

场景 1：当前节点有右子树

后继节点是 “右子树的最左节点”（右子树中最小的节点）：

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 = _node->_parent; // 循环条件：当前节点是父节点的右孩子（说明还没找到后继） while (parent && cur == parent->_right) { cur = parent; // 向上移动 parent = parent->_parent; } // 退出循环：parent 是后继（或 parent=nullptr，即 end()） _node = parent; } return *this; }

场景 2：当前节点无右子树

需沿父节点向上查找，直到找到第一个 “当前节点是其左孩子” 的祖先节点（该祖先节点即为后继）；若一直找到根节点仍未满足，则到达end()（_node = nullptr）。

示例理解

红黑树结构：5(root) <- 3 <- 1，5 -> 7 -> 9

迭代器指向1: 无右子树, 向上找, 3是1的父节点且1是3的左孩子 → 后继是3;
迭代器指向3: 有右子树 (空? 假设3右子树为空), 向上找, 5是3的父节点且3是5的左孩子 → 后继是5;
迭代器指向5: 有右子树，找右子树（7）的最左节点 → 7的左子树为空，因此后继是7;
迭代器指向9: 无右子树, 向上找, 7是9的父节点且9是7的右孩子 → 继续向上, 5是7的父节点且7是5的右孩子 → 继续向上, parent=nullptr → 后继是end()。

2.3 迭代器 -- 实现：找中序前驱节点（对称逻辑）

--对应红黑树的中序遍历前驱节点，逻辑与++对称：

Self& operator--() { if (_node->_left) { // 场景1：有左子树，找左子树最右节点 Node* subRight = _node->_left; while (subRight->_right) { // 一直向右找，直到无右孩子 subRight = subRight->_right; } _node = subRight; } else { // 场景2：无左子树，向上找祖先节点 Node* cur = _node; Node* parent = _node->_parent; // 循环条件：当前节点是父节点的左孩子（未找到前驱） while (parent && cur == parent->_left) { cur = parent; parent = parent->_parent; } // 退出循环：parent 是前驱（或 parent=nullptr，即 begin() 之前） _node = parent; } return *this; }

2.4 红黑树的 begin/end 接口：迭代器的边界

红黑树为 map/set 提供统一的迭代器边界，与T类型无关：

template<class K, class T, class KOfT> class RBTree { public: typedef __TreeIterator<T> iterator; // begin()：红黑树中序遍历的第一个节点（最左节点） iterator begin() { Node* cur = _root; while (cur && cur->_left) { // 一直向左找，直到无左孩子 cur = cur->_left; } return iterator(cur); } // end()：遍历的终止位置（空指针，不指向任何有效节点） iterator end() { return iterator(nullptr); } };

map/set 直接复用这两个接口：

// set 的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } // map 的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); }

三、迭代器的使用：map/set 遍历的底层逻辑

3.1 set 遍历：迭代器返回键值

void test_set() { sicheng::set<int> s; s.Insert(5); s.Insert(3); s.Insert(7); s.Insert(1); // 迭代器遍历：底层是红黑树的中序遍历 sicheng::set<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; // 输出：1 3 5 7（有序） ++it; // 调用 __TreeIterator::operator++() } }

• *it：调用operator*()，返回红黑树节点的_data（即 int 键值）；
• ++it：找到下一个中序节点，保证遍历有序。

3.2 map 遍历：迭代器返回键值对

void test_map() { sicheng::map<int, string> m; m.Insert({1, "one"}); m.Insert({3, "three"}); m.Insert({2, "two"}); // 迭代器遍历 sicheng::map<int, string>::iterator it = m.begin(); while (it != m.end()) { // it->first：等价于 (*it).first，返回 pair 的键 // it->second：返回 pair 的值 cout << it->first << ":" << it->second << " "; // 输出：1:one 2:two 3:three ++it; } }

• it->first：底层是operator->()返回pair<K,V>*，编译器优化为(*it).first；
• 遍历有序性：依赖红黑树的中序遍历，按键升序排列。

四、核心总结

4.1 map/set 共用红黑树的核心

1. 共性封装：红黑树封装 “基于键的有序存储、平衡调整、中序遍历” 等共性逻辑，与存储的具体数据类型解耦；
2. 差异抽象：通过模板参数T适配存储类型（键 / 键值对），通过仿函数KOfT统一键提取规则；
3. 无冗余复用：无需为 map/set 分别实现红黑树，仅需适配模板参数，极大减少代码冗余。

4.2 迭代器的核心逻辑

1. 本质：封装红黑树节点指针，遍历逻辑与存储类型T无关，仅通过解引用 / 箭头运算符适配不同返回值；
2. ++/-- 核心：找中序后继 / 前驱节点，分 “有子树” 和 “无自树” 两种场景，依赖红黑树的三叉链结构；
3. 边界：begin()是红黑树最左节点，end()是空指针（遍历终止）；
4. 差异化：set 迭代器解引用返回键，map 迭代器解引用返回键值对，底层仅因红黑树节点的T类型不同。

五、拓展：const 迭代器（补充）

实际开发中，map/set 还需提供const_iterator（只读迭代器），核心是修改operator*()和operator->()的返回值为 const：

template<class T> struct __TreeConstIterator { typedef RBTreeNode<T> Node; typedef __TreeConstIterator<T> Self; Node* _node; __TreeConstIterator(Node* node) : _node(node) {} // const 迭代器：解引用返回 const T& const T& operator*() { return _node->_data; } // const 迭代器：箭头返回 const T* const T* operator->() { return &(_node->_data); } // ++/-- 逻辑与非 const 版本完全一致 Self& operator++() { /* 同前 */ } Self& operator--() { /* 同前 */ } };

map/set 中新增const_iterator类型即可复用：

// set 的 const 迭代器 typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator; const_iterator cbegin() const { return _t.cbegin(); } const_iterator cend() const { return _t.cend(); } // map 的 const 迭代器同理

结尾

🍍 我是思成！若这篇内容帮你理清了 map/set 与红黑树的关联逻辑：

👀 【关注】跟我一起拆解 C++ 底层原理，从容器到数据结构，吃透每一个核心知识点

❤️ 【点赞】让技术干货被更多人看见，让抽象的底层逻辑变得易懂

⭐ 【收藏】把迭代器实现、泛型复用的思路存好，面试 / 实战时随时查阅

💬 【评论】分享你学习红黑树时踩过的坑，或想深挖的技术点，一起交流进步

🗳️ 【投票】告诉我你最想拆解的下一个知识点（比如红黑树删除？哈希表？）

技术学习没有捷径，但找对思路能少走弯路～愿我们都能把复杂的底层逻辑，拆解成可落地的知识碎片，一步步构建自己的技术体系！

结语：红黑树以 “颜色规则 + 旋转操作” 实现自平衡，既保留了二叉搜索树中序遍历的有序性，又解决了单支树退化的性能问题。而 map/set 基于泛型和仿函数的复用设计，更是 C++ 抽象思维的经典体现 —— 将共性逻辑封装，差异点参数化，让一套底层结构适配多种上层场景。理解这一设计思路，不仅能吃透 map/set，更能掌握泛型编程的核心精髓。