关注我，学习c++不迷路:
个人主页：爱装代码的小瓶子
专栏如下：
- c++学习
- Linux学习
后续会更新更多有趣的小知识，关注我带你遨游知识世界
期待你的关注。
文章目录
- 1. 改造红黑树：适应泛型
- 1.1 模板参数的变化
- 1.2 核心魔法：KeyOfT
- 2. 完善后的红黑树代码 (RBTree.h)
- 3. 封装实现 MySet
- 4. 封装实现 MyMap
- 5. 测试代码
- 总结
这篇博客将带你像 STL 源码一样，用同一棵红黑树底座，同时衍生出MyMap和MySet。
前言：
在上一篇文章中，我们已经手搓了一棵高性能的红黑树（RBTree）。但是，如果我们看 STL 的源码会发现，std::map和std::set底层竟然用的是同一个红黑树模板！既然 Set 存的是
Key，而 Map 存的是pair<K, V>，它们是如何共用同一套代码的呢？今天哆啦A梦就带大家钻进源码的“任意门”，揭秘其中的泛型编程技巧——KeyOfT仿函数。
1. 改造红黑树：适应泛型
要让红黑树既能存int(Set)，又能存pair(Map)，我们需要对红黑树的模板参数进行改造。
1.1 模板参数的变化
原来的定义：
// 只能针对特定类型，不够灵活template<classK,classV>classRBTree{...};改造后的定义：
// K: 键值类型（用于查找、比较）// T: 节点中实际存储的数据类型（Set是K，Map是pair<K,V>）// KeyOfT: 仿函数，用于从 T 中提取出 Ktemplate<classK,classT,classKeyOfT>classRBTree{...};1.2 核心魔法：KeyOfT
这是封装的精髓。因为节点里存的是T，红黑树在比较大小时需要用K。
- 如果是Set，
T就是K，直接返回。 - 如果是Map，
T是pair，我们需要取出first。
我们在红黑树内部不再直接比较data，而是这样写：
KeyOfT kot;// 实例化仿函数if(kot(data)>kot(cur->_data)){...}2. 完善后的红黑树代码 (RBTree.h)
这是基于我们之前修复过 Bug（修复了迭代器和 Find 逻辑）的最终版本。为了节省篇幅，只展示核心修改部分。
#pragmaonce#include<iostream>#include<vector>#include<assert.h>usingnamespacestd;enumColor{RED,BLACK};template<classT>structRBTreeNode{RBTreeNode<T>*_left;RBTreeNode<T>*_right;RBTreeNode<T>*_parent;T _data;// T 可能是 Key，也可能是 pair<K,V>Color _col;RBTreeNode(constT&data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}};// 迭代器实现（复用之前的修复版）template<classT,classRef,classPtr>struct__RBTreeIterator{typedefRBTreeNode<T>Node;typedef__RBTreeIterator<T,Ref,Ptr>Self;Node*_node;Node*_root;__RBTreeIterator(Node*node,Node*root):_node(node),_root(root){}Refoperator*(){return_node->_data;}Ptroperator->(){return&_node->_data;}// ... operator++ 和 operator-- 的代码与之前修复版一致 ...// 重点：Map 的 Value 允许修改，Key 不允许；Set 都不允许。// 这通过传递 const T& 或 T& 来控制。};// 红黑树主体template<classK,classT,classKeyOfT>classRBTree{typedefRBTreeNode<T>Node;public:typedef__RBTreeIterator<T,T&,T*>iterator;typedef__RBTreeIterator<T,constT&,constT*>const_iterator;// 插入逻辑改造pair<iterator,bool>Insert(constT&data){if(_root==nullptr){_root=newNode(data);_root->_col=BLACK;returnmake_pair(iterator(_root,_root),true);}KeyOfT kot;// 核心：提取 Key 的工具人Node*parent=nullptr;Node*cur=_root;while(cur){// 所有的比较都通过 kot 提取 key 后进行if(kot(data)<kot(cur->_data)){parent=cur;cur=cur->_left;}elseif(kot(data)>kot(cur->_data)){parent=cur;cur=cur->_right;}else{returnmake_pair(iterator(cur,_root),false);}}// ... 剩下的插入节点、变色、旋转逻辑保持不变 ...// ... 注意 new Node(data) ...returnmake_pair(iterator(newnode,_root),true);}// 查找逻辑改造iteratorFind(constK&key){KeyOfT kot;Node*cur=_root;while(cur){if(key<kot(cur->_data))cur=cur->_left;elseif(key>kot(cur->_data))cur=cur->_right;elsereturniterator(cur,_root);}returnend();}iteratorbegin(){Node*cur=_root;while(cur&&cur->_left)cur=cur->_left;returniterator(cur,_root);}iteratorend(){returniterator(nullptr,_root);}private:Node*_root=nullptr;};3. 封装实现 MySet
Set 的特点是：
- 存储的是 Key。
- 迭代器不可修改（底层是
const_iterator）。
#include"RBTree.h"namespacebit{template<classK>classset{// 1. 定义仿函数：怎么从 K 中取 K？直接返回自己即可！structSetKeyOfT{constK&operator()(constK&key){returnkey;}};public:// 2. 实例化红黑树// K: 查找类型// K: 存储类型// SetKeyOfT: 提取方式typedeftypenameRBTree<K,K,SetKeyOfT>::const_iterator iterator;typedeftypenameRBTree<K,K,SetKeyOfT>::const_iterator const_iterator;pair<iterator,bool>insert(constK&key){// Set 的普通迭代器本质也是 const 迭代器，防止修改 Key 破坏树结构autoret=_t.Insert(key);returnpair<iterator,bool>(ret.first,ret.second);}iteratorbegin()const{return_t.begin();}iteratorend()const{return_t.end();}private:RBTree<K,K,SetKeyOfT>_t;};}4. 封装实现 MyMap
Map 的特点是：
- 存储的是
pair<const K, V>。 - 支持
operator[]。 - 迭代器可以修改 Value，但不能修改 Key。
#include"RBTree.h"namespacebit{template<classK,classV>classmap{// 1. 定义仿函数：怎么从 pair 中取 K？返回 first！structMapKeyOfT{constK&operator()(constpair<K,V>&kv){returnkv.first;}};public:// 2. 实例化红黑树// 存储类型 T 是 pair<const K, V>，const K 保证了 Key 不会被迭代器修改typedeftypenameRBTree<K,pair<constK,V>,MapKeyOfT>::iterator iterator;pair<iterator,bool>insert(constpair<K,V>&kv){return_t.Insert(kv);}// 3. 实现核心功能：方括号访问// 逻辑：插入 key。如果存在，返回对应 iterator；如果不存在，插入默认值并返回 iterator。V&operator[](constK&key){pair<iterator,bool>ret=insert(make_pair(key,V()));// ret.first 是迭代器，-> 解引用拿到 pair，.second 拿到 Valuereturnret.first->second;}iteratorbegin(){return_t.begin();}iteratorend(){return_t.end();}private:RBTree<K,pair<constK,V>,MapKeyOfT>_t;};}5. 测试代码
让我们来验证一下大雄（我们）的代码是否健壮：
voidTestMap(){bit::map<string,string>dict;dict.insert(make_pair("sort","排序"));dict.insert(make_pair("string","字符串"));// 测试 operator[]dict["apple"]="苹果";// 插入 + 修改dict["sort"]="排序(新)";// 修改for(auto&kv:dict){cout<<kv.first<<":"<<kv.second<<endl;}}voidTestSet(){bit::set<int>s;s.insert(3);s.insert(1);s.insert(2);// *s.begin() = 10; // 报错！Set 迭代器不可修改，符合预期for(autoe:s){cout<<e<<" ";}cout<<endl;}总结
通过引入KeyOfT仿函数，我们成功地将红黑树从“专用于某一种类型”变成了“通用的容器底座”。
- Set告诉红黑树：“我存的是
int，比较的时候直接用它。” - Map告诉红黑树：“我存的是
pair，比较的时候请用first。”
这就是 C++ STL 极致复用的智慧！希望这篇博客能帮你像哆啦A梦一样，从百宝袋里掏出完美的红黑树！
觉得写得不错的话，记得一键三连哦！
