扒透 STL 底层！map/set 如何封装红黑树？迭代器逻辑 + 键值限制全手撕----《Hello C++ Wrold!》(23)--(C/C++)
文章目录
前言
你是不是也有过这种 “知其然不知其所以然” 的困惑：
用 map 存键值对、用 set 去重排序时很顺手，但一被问 “map 的 [] 怎么既插入又访问”“set 为啥不能改元素”“它们底层的红黑树到底存的啥”，就瞬间卡壳？甚至看 STL 源码时，被 “KeyOfT”“迭代器 ++ 逻辑” 绕得晕头转向？
其实 map 和 set 的本质，就是对红黑树的 “定制化封装” —— 红黑树是 “通用骨架”，map 和 set 通过 “提取键的规则（KeyOfT）”“迭代器权限控制”“键值修改限制”，分别适配了 “键值对存储” 和 “单一元素去重” 的需求。
这篇内容不搞虚的，直接从 “红黑树如何适配 map/set” 切入：拆透 map 的 KeyOfT 怎么提取 pair 的 first，set 为啥要用 const 迭代器锁死修改；讲清迭代器 +±- 的底层逻辑（右子树找最左 vs 回溯父节点）；还附上手撕的红黑树封装、迭代器实现代码 —— 不管你是想搞懂 STL 底层，还是面试被问 “map/set 原理” 时想答到点子上，这篇都能让你把 “封装逻辑” 嚼得明明白白。
map和set的封装
这俩在封装的时候对红黑树里面的K,T的处理:map的话K是存Key,T是搞的pair<Key,Value>--这两个Key是一样的哈set的话K是存Key,T也是存Key–这两个Key是一样的哈(第二个T存东西单纯为了陪跑)
对于set的话KT都不能被修改–因为都是Key
对于map的话K不能被修改，T里面的value可以被修改
对于键和值的理解:
对于map:键用来排序查找啥的，值用来存信息
对于set:键承担了所有
map:namespace renshen {template<classK,classV>classmap{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}//一般不在里面直接封装比较，而是把要比较的值给出去--这样灵活一些};public:typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;//这里必须加typename，不然编译器不指定RBTree<K, pair<K, V>, MapKeyOfT>::iterator是个类型//因为,类模板只有在被实例化的时候，编译器才会真正知道其中各种类型和表达式的含义//之后在源文件的话就可以eg:renshen::map<int,int>::iterator mit = ......//如果iterator被typedef过的话，RBTree<K, pair<const K, V>, MapKeyOfT>::iterator还是RBTree里面的iteratortypedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} V&operator[](const K& key){ pair<iterator,bool> ret =insert(make_pair(key,V()));return ret.first->second;}//V()就是为了没有这个key的话就插入，有的话就返回已有的那个值 pair<iterator,bool>insert(const pair<K, V>& kv){return _t.Insert(kv);}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;//这个const用的好,让普通迭代器的value可以修改，const迭代器啥也不能修改};}map的[]可以插入和修改和访问–string的[]不能用来插入
set:namespace renshen {template<classK>classset{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator iterator;//注意这里typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator const_iterator; const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} pair<iterator,bool>insert(const K& key){ pair<typenameRBTree<K, K, SetKeyOfT>::iterator,bool> ret = _t.Insert(key);return pair<iterator,bool>(ret.first, ret.second);}private: RBTree<K, K, SetKeyOfT> _t;};}底层红黑树的模拟实现
enumColour{ RED, BLACK };template<classT>structRBTreeNode{ RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data; Colour _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}};template<classK,classT,classKeyOfT>structRBTree{typedef RBTreeNode<T> Node;public:typedef __TreeIterator<T, T*, T&> iterator;typedef __TreeIterator<T,const T*,const T&> const_iterator; iterator begin(){ Node* leftMin = _root;while(leftMin && leftMin->_left)//这里前面那个leftMin是防止这个树是空树{ leftMin = leftMin->_left;}//最左边的那个节点returniterator(leftMin);//调用了iterator的构造函数} iterator end(){returniterator(nullptr);} const_iterator begin()const{ Node* leftMin = _root;while(leftMin && leftMin->_left){ leftMin = leftMin->_left;}returnconst_iterator(leftMin);} const_iterator end()const{returnconst_iterator(nullptr);} Node*Find(const K& key){ Node* cur = _root; KeyOfT kot;while(cur){if(kot(cur->_data)< key){ cur = cur->_right;}elseif(kot(cur->_data)> key){ cur = cur->_left;}else{return cur;}}returnnullptr;} pair<iterator,bool>Insert(const T& data){if(_root ==nullptr){ _root =newNode(data); _root->_col = BLACK;returntrue;} Node* parent =nullptr; Node* cur = _root; KeyOfT kot;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),false);//返回已经存在的那个节点的迭代器}} cur =newNode(data); 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;// u存在且为红if(uncle && uncle->_col == RED){// 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续向上处理 cur = grandfather; parent = cur->_parent;}else// u不存在 或 存在且为黑{if(cur == parent->_left){// g// p// cRotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED;}else{// g// p// cRotateL(parent);RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}else// parent == grandfather->_right{ Node* uncle = grandfather->_left;// u存在且为红if(uncle && uncle->_col == RED){// 变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED;// 继续向上处理 cur = grandfather; parent = cur->_parent;}else{if(cur == parent->_right){// g// p// cRotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED;}break;}}} _root->_col = BLACK;returnmake_pair(iterator(newnode),true);}//旋转相关的代码就参考AVL树的就行了private: Node* _root =nullptr;};库里面的红黑树和这里的模拟实现的区别:
库里面其实还有个头节点,头节点的父亲是红黑树的根节点，头节点的left是红黑树里面最小的数，头节点的right是红黑树里面最大的数,然后根节点的父亲也是头节点
注意:区分头节点和根节点!
迭代器的模拟实现
这里的迭代器的begin和end的位置要注意:begin是最左边的那个节点end是根节点的父亲–nullptr–这个begin和end是在底层红黑树那里定义的
这里的迭代器的++:
1.当前节点的右子树不为空，则访问右树的最左节点
2.当前节点的右子树为空，如果当前节点的父亲是其父亲的左孩子，就访问当前节点的父亲，不然就把当前节点的父亲变成当前节点，直到遇到那种情况或者当前节点成根节点的父亲了
这里迭代器的--:
1.当前节点的左子树不为空，则访问左树的最右节点
2.当前节点的右子树为空，如果当前节点的父亲是其父亲的右孩子，就访问当前节点的父亲，不然就把当前节点的父亲变成当前节点，直到遇到那种情况或者当前节点变成根节点的父亲了
引申:普通迭代器可以隐式转换为const迭代器
template<classT,classPtr,classRef>struct__TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;typedef __TreeIterator<T, T*, T&> Iterator;__TreeIterator(const Iterator& it):_node(it._node){} Node* _node;__TreeIterator(Node* node):_node(node){} 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;} Self&operator--(){if(_node->_left){ Node* subRight = _node->_left;while(subRight->_right){ subRight = subRight->_right;} _node = subRight;}else{ Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = cur->_parent; parent = parent->_parent;} _node = parent;}return*this;} Self&operator++(){if(_node->_right){// 右树的最左节点(最小节点) Node* subLeft = _node->_right;while(subLeft->_left){ subLeft = subLeft->_left;} _node = subLeft;}else{ Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_right){ cur = cur->_parent; parent = parent->_parent;} _node = parent;}return*this;}};
