【红黑树进阶】手撕STL源码：从零封装RB-tree实现map和set

Ne0inhk

25 Mar 2026 — 19 min read

👇点击进入作者专栏：

《算法画解》 ✅

《linux系统编程》✅

《C++》 ✅

文章目录

一. 源码及框架分析
- 1.1 STL源码中的设计思想
- 1.2 STL源码框架分析
二. 模拟实现map和set（实现复用红黑树的框架）
三. 迭代器的实现
四. map和set对迭代器的封装
六. const迭代器和const正确性
七. 完整代码实现
- 7.1 RBTree.h（完整版）
- 7.2 Myset.h（完整版）
  - 7.3 Mymap.h（完整版）
八. 总结与思考

一. 源码及框架分析

1.1 STL源码中的设计思想

在SGI-STL30版本中，map和set的实现基于一棵红黑树（rb_tree）。这种设计体现了C++泛型编程的强大之处：通过同一棵红黑树，既可以实现key-only的set，也可以实现key/value的map。

核心设计思想：

rb_tree的节点中存储什么类型，由模板参数决定
set传给rb_tree的是Key类型
map传给rb_tree的是pair<const Key, T>类型

1.2 STL源码框架分析

// stl_set.htemplate<classKey,classCompare= less<Key>,classAlloc= alloc>classset{public:typedef Key key_type;typedef Key value_type;// set的value_type就是Keyprivate:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t;// 红黑树，存储的是Key类型};// stl_map.htemplate<classKey,classT,classCompare= less<Key>,classAlloc= alloc>classmap{public:typedef Key key_type;typedef T mapped_type;typedef pair<const Key, T> value_type;// map的value_type是pairprivate:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t;// 红黑树，存储的是pair<const Key, T>类型};// stl_tree.h - 红黑树节点定义struct__rb_tree_node_base{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr; color_type color;// 节点颜色 base_ptr parent;// 父节点 base_ptr left;// 左孩子 base_ptr right;// 右孩子};template<classValue>struct__rb_tree_node:public__rb_tree_node_base{typedef __rb_tree_node<Value>* link_type; Value value_field;// 节点存储的数据，Value类型由使用者决定};

关键问题：为什么rb_tree需要两个模板参数Key和Value？

Value：决定了节点中存储的数据类型（set是Key，map是pair）
Key：用于查找和删除操作的参数类型（find/erase的参数类型）

对于set而言，Key和Value是相同的；对于map而言，Key是键的类型，Value是pair类型。这种设计使得一棵红黑树既能处理set场景，也能处理map场景。

二. 模拟实现map和set（实现复用红黑树的框架）

2.1 红黑树节点的定义

// RBTree.h#pragmaonceenumColour{ RED, BLACK };template<classT>structRBTreeNode{ T _data;// 节点存储的数据（泛型T） RBTreeNode<T>* _left;// 左孩子 RBTreeNode<T>* _right;// 右孩子 RBTreeNode<T>* _parent;// 父节点 Colour _col;// 颜色// 构造函数RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)// 新节点默认红色{}};

2.2 红黑树的基本框架

template<classK,classT,classKeyOfT>classRBTree{typedef RBTreeNode<T> Node;public:// 类型重命名（迭代器类型，后续实现）typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T,const T&,const T*> ConstIterator;// 构造函数RBTree()=default;// 析构函数~RBTree(){Destroy(_root); _root =nullptr;}// 插入接口 pair<Iterator,bool>Insert(const T& data);// 查找接口 Iterator Find(const K& key);// 迭代器相关 Iterator Begin(); Iterator End(); ConstIterator Begin()const; ConstIterator End()const;private:// 旋转操作voidRotateL(Node* parent);// 左单旋voidRotateR(Node* parent);// 右单旋// 销毁树voidDestroy(Node* root); Node* _root =nullptr;// 根节点};

2.3 解决Key的比较问题：KeyOfT仿函数

问题：红黑树在插入时需要比较键的大小，但T可能是Key类型，也可能是pair类型。pair的比较规则是first和second一起比较，不符合我们的需求（我们只想比较key）。

解决方案：使用仿函数KeyOfT，从T对象中取出Key进行比较。

// Mymap.h - map中定义的KeyOfT仿函数namespace bit {template<classK,classV>classmap{// 仿函数：从pair中取出keystructMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;// 返回pair的first（键）}};// ... 其他代码};}

// Myset.h - set中定义的KeyOfT仿函数namespace bit {template<classK>classset{// 仿函数：直接返回key本身structSetKeyOfT{const K&operator()(const K& key){return key;// 直接返回key}};// ... 其他代码};}

2.4 支持insert插入

RBTree中的Insert实现（关键部分是使用KeyOfT进行比较）

template<classK,classT,classKeyOfT> pair<typenameRBTree<K, T, KeyOfT>::Iterator,bool>RBTree<K, T, KeyOfT>::Insert(const T& data){// 1. 空树情况if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;// 根节点必须是黑色returnmake_pair(Iterator(_root, _root),true);}// 2. 查找插入位置 KeyOfT kot;// 创建仿函数对象 Node* parent =nullptr; Node* cur = _root;while(cur){// 使用kot取出key进行比较if(kot(cur->_data)<kot(data)){ parent = cur; cur = cur->_right;}elseif(kot(cur->_data)>kot(data)){ parent = cur; cur = cur->_left;}else{// 键值已存在，插入失败returnmake_pair(Iterator(cur, _root),false);}}// 3. 创建新节点并链接 cur =newNode(data); Node* newnode = cur; cur->_col = RED;// 新节点默认红色if(kot(parent->_data)<kot(data)) parent->_right = cur;else parent->_left = cur; cur->_parent = parent;// 4. 红黑树性质修复（与之前实现的插入逻辑相同）while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;// 情况1：叔叔存在且为红if(uncle && uncle->_col == RED){// 变色处理 parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续向上处理 cur = grandfather; parent = cur->_parent;}else{// 情况2/3：叔叔不存在或为黑if(cur == parent->_left){// 左左：右单旋RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// 左右：左右双旋RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else{// 对称情况：parent是grandfather的右孩子 Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{if(cur == parent->_right){// 右右：左单旋RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// 右左：右左双旋RotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}}// 确保根节点为黑色 _root->_col = BLACK;returnmake_pair(Iterator(newnode, _root),true);}

2.5 map和set的insert封装

// Mymap.h - map的insertnamespace bit {template<classK,classV>classmap{// ... 前面的代码public: pair<iterator,bool>insert(const pair<K, V>& kv){return _t.Insert(kv);// 直接调用RBTree的Insert}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};}

// Myset.h - set的insertnamespace bit {template<classK>classset{// ... 前面的代码public: pair<iterator,bool>insert(const K& key){return _t.Insert(key);// 直接调用RBTree的Insert}private: RBTree<K,const K, SetKeyOfT> _t;};}

三. 迭代器的实现

3.1 迭代器结构设计

迭代器需要支持：

operator++：前往中序下一个节点
operator--：前往中序上一个节点
operator*：解引用，获取节点数据
operator->：通过指针访问成员
operator==/!=：比较两个迭代器是否相等

// RBTree.htemplate<classT,classRef,classPtr>structRBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self; Node* _node;// 当前迭代器指向的节点 Node* _root;// 根节点（用于--end()特殊处理）// 构造函数RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}// 前置++ Self&operator++();// 前置-- Self&operator--();// 解引用 Ref operator*(){return _node->_data;}// 箭头操作 Ptr operator->(){return&_node->_data;}// 比较操作booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};

3.2 迭代器的++操作

中序遍历的顺序是：左子树 → 根 → 右子树

template<classT,classRef,classPtr>typenameRBTreeIterator<T, Ref, Ptr>::Self& RBTreeIterator<T, Ref, Ptr>::operator++(){if(_node ==nullptr)return*this;// end()不能++if(_node->_right){// 情况1：右子树不为空// 中序下一个是右子树的最左节点 Node* leftMost = _node->_right;while(leftMost->_left){ leftMost = leftMost->_left;} _node = leftMost;}else{// 情况2：右子树为空// 向上找：孩子是父亲左的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_right){ cur = parent; parent = cur->_parent;} _node = parent;// 可能是nullptr（到达end）}return*this;}

3.3 迭代器的–操作

template<classT,classRef,classPtr>typenameRBTreeIterator<T, Ref, Ptr>::Self& RBTreeIterator<T, Ref, Ptr>::operator--(){if(_node ==nullptr)// --end()特殊处理{// end()应该走到中序最后一个节点（整棵树的最右节点） Node* rightMost = _root;while(rightMost && rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}elseif(_node->_left){// 情况1：左子树不为空// 中序上一个节点是左子树的最右节点 Node* rightMost = _node->_left;while(rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}else{// 情况2：左子树为空// 向上找：孩子是父亲右的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = parent; parent = cur->_parent;} _node = parent;// 可能是nullptr（到达rend？）}return*this;}

–end()的特殊处理：

end()迭代器指向nullptr
当对end()执行–操作时，应该得到最后一个有效节点（最右节点）
所以需要记录_root来找到最右节点

3.4 RBTree中的迭代器接口

template<classK,classT,classKeyOfT>classRBTree{// ... 前面的代码public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T,const T&,const T*> ConstIterator;// begin() -> 最左节点 Iterator Begin(){ Node* leftMost = _root;while(leftMost && leftMost->_left){ leftMost = leftMost->_left;}returnIterator(leftMost, _root);}// end() -> nullptr Iterator End(){returnIterator(nullptr, _root);}// const版本 ConstIterator Begin()const{ Node* leftMost = _root;while(leftMost && leftMost->_left){ leftMost = leftMost->_left;}returnConstIterator(leftMost, _root);} ConstIterator End()const{returnConstIterator(nullptr, _root);}};

四. map和set对迭代器的封装

4.1 set的迭代器封装

// Myset.hnamespace bit {template<classK>classset{// ... 前面的代码public:// 类型重命名：从RBTree中取出迭代器类型typedeftypenameRBTree<K,const K, SetKeyOfT>::Iterator iterator;typedeftypenameRBTree<K,const K, SetKeyOfT>::ConstIterator const_iterator;// begin/end接口 iterator begin(){return _t.Begin();} iterator end(){return _t.End();} const_iterator begin()const{return _t.Begin();} const_iterator end()const{return _t.End();}private: RBTree<K,const K, SetKeyOfT> _t;};}

4.2 map的迭代器封装

// Mymap.hnamespace bit {template<classK,classV>classmap{// ... 前面的代码public:// 类型重命名typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;// begin/end接口 iterator begin(){return _t.Begin();} iterator end(){return _t.End();} const_iterator begin()const{return _t.Begin();} const_iterator end()const{return _t.End();}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};}

4.3 测试迭代器

// 测试setvoidtest_set(){ bit::set<int> s;int a[]={4,2,6,1,3,5,15,7,16,14};for(auto e : a){ s.insert(e);}// 范围for测试（依赖begin/end）for(auto e : s){ cout << e <<" ";// 输出：1 2 3 4 5 6 7 14 15 16} cout << endl;}

五. map的operator[]实现

5.1 operator[]的原理

map的operator[]是一个非常方便的特性：

如果key存在，返回对应的value引用
如果key不存在，插入一个默认value并返回其引用

5.2 实现步骤

修改RBTree的Insert，返回pair<Iterator, bool>
在map的operator[]中调用insert
根据返回的迭代器访问second

5.3 代码实现

// Mymap.hnamespace bit {template<classK,classV>classmap{// ... 前面的代码public: V&operator[](const K& key){// 尝试插入：如果key不存在，插入{key, V()}// V()会调用V类型的默认构造函数（内置类型为0） pair<iterator,bool> ret =insert(make_pair(key,V()));// ret.first是插入位置（新节点或已存在节点）的迭代器// 返回该节点的second（value）的引用return ret.first->second;}};}

5.4 测试operator[]

voidtest_map(){ bit::map<string, string> dict;// 插入操作 dict.insert({"sort","排序"}); dict.insert({"left","左边"}); dict.insert({"right","右边"});// operator[]的三种用法 dict["left"]="左边，剩余";// 修改已存在key的value dict["insert"]="插入";// 插入新key-value dict["string"];// 插入新key，value为默认值（空字符串）// 遍历输出for(auto& kv : dict){// 不能修改first，可以修改second// kv.first += 'x'; // 错误！ kv.second +='x';// 正确：value可以修改 cout << kv.first <<":"<< kv.second << endl;}}

输出结果：

insert:插入x left:左边，剩余x right:右边x sort:排序x string:x

六. const迭代器和const正确性

6.1 const迭代器的使用场景

// 接收const引用的函数voidPrint(const bit::set<int>& s){// 这里只能用const_iterator，因为s是const的 bit::set<int>::const_iterator it = s.begin();while(it != s.end()){// *it += 10; // 错误！const迭代器不允许修改 cout <<*it <<" ";++it;} cout << endl;}

6.2 为什么要支持const迭代器？

const对象只能用const迭代器：保证const对象的内容不会被修改
语义清晰：表明这段代码只读不写
编译器检查：帮助捕获意外的修改

6.3 set中key不可修改的保证

在set中，key是不可修改的。实现方式：

// Myset.htemplate<classK>classset{private:// RBTree第二个模板参数传入 const K RBTree<K,const K, SetKeyOfT> _t;};

这样，迭代器解引用得到的是const K&，无法修改。

6.4 map中key不可修改，value可修改

// Mymap.htemplate<classK,classV>classmap{private:// RBTree第二个模板参数传入 pair<const K, V>// key是const的，value是可修改的 RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

迭代器解引用得到pair<const K, V>&
first是const，不能修改
second不是const，可以修改

七. 完整代码实现

7.1 RBTree.h（完整版）

#pragmaonce#include<utility>usingnamespace std;enumColour{ RED, BLACK };// 红黑树节点template<classT>structRBTreeNode{ T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}};// 迭代器template<classT,classRef,classPtr>structRBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self; Node* _node; Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){} Self&operator++(){if(_node ==nullptr)return*this;if(_node->_right){// 右子树的最左节点 Node* leftMost = _node->_right;while(leftMost->_left){ leftMost = leftMost->_left;} _node = leftMost;}else{// 向上找：孩子是父亲左的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_right){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;} Self&operator--(){if(_node ==nullptr)// --end(){// 走到最右节点 Node* rightMost = _root;while(rightMost && rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}elseif(_node->_left){// 左子树的最右节点 Node* rightMost = _node->_left;while(rightMost->_right){ rightMost = rightMost->_right;} _node = rightMost;}else{// 向上找：孩子是父亲右的那个祖先 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = parent; parent = cur->_parent;} _node = parent;}return*this;} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};// 红黑树template<classK,classT,classKeyOfT>classRBTree{typedef RBTreeNode<T> Node;public:typedef RBTreeIterator<T, T&, T*> Iterator;typedef RBTreeIterator<T,const T&,const T*> ConstIterator;RBTree()=default;~RBTree(){Destroy(_root); _root =nullptr;} Iterator Begin(){ Node* leftMost = _root;while(leftMost && leftMost->_left){ leftMost = leftMost->_left;}returnIterator(leftMost, _root);} Iterator End(){returnIterator(nullptr, _root);} ConstIterator Begin()const{ Node* leftMost = _root;while(leftMost && leftMost->_left){ leftMost = leftMost->_left;}returnConstIterator(leftMost, _root);} ConstIterator End()const{returnConstIterator(nullptr, _root);}// 插入 pair<Iterator,bool>Insert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returnmake_pair(Iterator(_root, _root),true);} KeyOfT kot; Node* parent =nullptr; Node* cur = _root;while(cur){if(kot(cur->_data)<kot(data)){ parent = cur; cur = cur->_right;}elseif(kot(cur->_data)>kot(data)){ parent = cur; cur = cur->_left;}else{returnmake_pair(Iterator(cur, _root),false);}} cur =newNode(data); Node* newnode = cur; cur->_col = RED;if(kot(parent->_data)<kot(data)) parent->_right = cur;else parent->_left = cur; cur->_parent = parent;// 修复红黑树性质while(parent && parent->_col == RED){ Node* grandfather = parent->_parent;if(parent == grandfather->_left){ Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){// 情况1：变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{if(cur == parent->_left){// 左左：右单旋RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// 左右：左右双旋RotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else{ Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){ parent->_col = uncle->_col = BLACK; grandfather->_col = RED; cur = grandfather; parent = cur->_parent;}else{if(cur == parent->_right){// 右右：左单旋RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// 右左：右左双旋RotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}} _root->_col = BLACK;returnmake_pair(Iterator(newnode, _root),true);}// 查找 Iterator Find(const K& key){ KeyOfT kot; Node* cur = _root;while(cur){if(kot(cur->_data)< key) cur = cur->_right;elseif(kot(cur->_data)> key) cur = cur->_left;elsereturnIterator(cur, _root);}returnEnd();}private:// 左单旋voidRotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;if(subRL) subRL->_parent = parent; Node* parentParent = parent->_parent; subR->_left = parent; parent->_parent = subR;if(parentParent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(parent == parentParent->_left) parentParent->_left = subR;else parentParent->_right = subR; subR->_parent = parentParent;}}// 右单旋voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* parentParent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(parentParent ==nullptr){ _root = subL; subL->_parent =nullptr;}else{if(parent == parentParent->_left) parentParent->_left = subL;else parentParent->_right = subL; subL->_parent = parentParent;}}// 销毁树voidDestroy(Node* root){if(root ==nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;} Node* _root =nullptr;};

7.2 Myset.h（完整版）

#pragmaonce#include"RBTree.h"namespace bit {template<classK>classset{// 仿函数：从数据中取出keystructSetKeyOfT{const K&operator()(const K& key){return key;}};public:// 迭代器类型（从RBTree中取出）typedeftypenameRBTree<K,const K, SetKeyOfT>::Iterator iterator;typedeftypenameRBTree<K,const K, SetKeyOfT>::ConstIterator const_iterator;// begin/end iterator begin(){return _t.Begin();} iterator end(){return _t.End();} const_iterator begin()const{return _t.Begin();} const_iterator end()const{return _t.End();}// 插入 pair<iterator,bool>insert(const K& key){return _t.Insert(key);}// 查找 iterator find(const K& key){return _t.Find(key);}private: RBTree<K,const K, SetKeyOfT> _t;};// 测试函数voidPrint(const set<int>& s){ set<int>::const_iterator it = s.begin();while(it != s.end()){// *it += 2; // 错误！不能修改 cout <<*it <<" ";++it;} cout << endl;}voidtest_set(){ set<int> s;int a[]={4,2,6,1,3,5,15,7,16,14};for(auto e : a){ s.insert(e);}// 范围forfor(auto e : s){ cout << e <<" ";} cout << endl;Print(s);}}

7.3 Mymap.h（完整版）

#pragmaonce#include"RBTree.h"namespace bit {template<classK,classV>classmap{// 仿函数：从pair中取出keystructMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:// 迭代器类型typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;// begin/end iterator begin(){return _t.Begin();} iterator end(){return _t.End();} const_iterator begin()const{return _t.Begin();} const_iterator end()const{return _t.End();}// 插入 pair<iterator,bool>insert(const pair<K, V>& kv){return _t.Insert(kv);}// 查找 iterator find(const K& key){return _t.Find(key);}// operator[] V&operator[](const K& key){ pair<iterator,bool> ret =insert(make_pair(key,V()));return ret.first->second;}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};voidtest_map(){ map<string, string> dict; dict.insert({"sort","排序"}); dict.insert({"left","左边"}); dict.insert({"right","右边"}); dict["left"]="左边，剩余"; dict["insert"]="插入"; dict["string"]; map<string, string>::iterator it = dict.begin();while(it != dict.end()){// it->first += 'x'; // 错误！不能修改key it->second +='x';// 可以修改value cout << it->first <<":"<< it->second << endl;++it;} cout << endl;}}

八. 总结与思考

8.1 设计亮点

泛型设计：一棵红黑树通过模板参数适配set和map
仿函数KeyOfT：解决了不同类型中取key的问题
迭代器抽象：封装了中序遍历的逻辑
const正确性：通过模板参数Ref和Ptr支持const迭代器

8.2 与STL源码的对比

特性	我们的实现	SGI-STL
节点结构	RBTreeNode	__rb_tree_node
迭代器	RBTreeIterator	__rb_tree_iterator
KeyOfT	模板参数	identity/select1st
迭代器–	支持	支持
哨兵节点	无	header节点

8.3 常见问题

Q1：为什么set的迭代器不能修改key？

set中的元素本身就是key，修改key会破坏BST的有序性
实现中通过RBTree<K, const K, SetKeyOfT>保证存储的是const K

Q2：为什么map的迭代器能修改value但不能修改key？

map存储的是pair<const K, V>，key是const的，value不是const
修改key会破坏有序性，修改value不会影响树的组织结构

Q3：为什么要实现const_iterator？

const对象只能用const_iterator遍历
明确表达只读语义，帮助编译器检查

Q4：迭代器–操作中为什么要保存_root？

为了处理--end()的情况，需要找到最右节点
没有_root无法从nullptr找到最右节点

加油！志同道合的人会看到同一片风景。
看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。创作不易，还请多多支持！