[C++进阶] 21. 红黑树封装mapset

源码下载https://gitee.com/Lengggsiyu/cpp_code/tree/master/stl30一. STL源码中的封装逻辑1map2set根据我们对map和set的了解map是key_value结构这和我们看到的底层一样。但是怎么set底层也是key_value不应该只有key么这就要看看封装set的红黑树的结构了。3rb_tree1. 红黑树的第二个模板参数value传什么红黑树的节点中存的就是什么类型的数据。这样通过模板参数写成泛型就可以让map、set复用同一棵红黑树。set实例化rb_tree时第二个模板参数给的是keymap实例化rb_tree时第二个模板参数给的是pairconst key,T这样一棵红黑树既可以实现key搜索场景的set也可以实现key_value搜索场景的map。2.rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型为什么还要传第一个模板参数Key呢尤其是set两个模板参数是一样的。① 对于map和setfind/erase时的函数参数都是Key所以第一个模板参数是传给find/erase等函数做形参的类型的。② 对于set而言两个参数key_type和value_type是一样的都是key但是对于map而言就完全不一样了第一个是key第二个是pairconst key,Tmap insert的是pair对象但是find和erase的是Key对象。4实例化mapset的传参过程二. 模拟实现mapset1实现泛型红黑树结构封装map和set框架KeyOfT之前我们实现的是key_value的红黑树现在把之前的代码改造一下变成泛型的能同时被map和set复用。// 结点里存什么类型的数据由传过来的模板参数T决定 template class T struct RBtreeNode { T _data; RBtreeNodeT* _left; RBtreeNodeT* _right; RBtreeNodeT* _parent; Color _color; RBtreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _color(RED) {} };21. 结点数据的类型变成泛型我们的各种比较逻辑也要变了。之前我们是取出pair的first也就是key来比较但是现在_data不一定是pair不能随便取first。2. pair对象本身也是可以比较的但是他比较的逻辑是先拿first比first比完还会再拿second比。这不符合我们期望的比较逻辑对于map我们只希望他的first参与比较。3.那么如何处理能让比较的逻辑同时适合key和key_value① 说到控制比较逻辑很容易想到仿函数。给rbtree加一个模板参数将map和set各自的仿函数map和set各自知道自己的数据是key还是key_value也就可以控制比较逻辑该不该取first通过模板参数传给rbtree在仿函数里控制比较逻辑但是这种方法是行不通的。因为下图中的两种场景一个是插入时的比较逻辑一个是查找时的比较逻辑_data要比较的类型不是只有Tkey或pair还有可能直接是K。连仿函数的参数都确定不了。② 实际库里面的做法还是用到了仿函数并通过增加一个模板参数接受map和set各自的仿函数。只不过这个仿函数的作用不是直接控制比较逻辑而是从rbtree的第二个模板参数中取出key。我们不就是希望只有key参与比较么不管是什么类型确保仿函数能取出其中的key部分就好。2迭代器普通迭代器1. 因为结点的物理空间也是不连续的不能用原生指针直接充当迭代器所以红黑树迭代器的实现思路和框架和list很相似用一个类封装节点的指针再通过重载运算符实现像指针一样访问的行为。2. 迭代器实现的难点是operator和operator--的实现map和set迭代器走的是中序遍历的顺序。的逻辑规则① 迭代器时如果it指向的结点的右子树不为空代表当前结点已经访问完了要访问下一个结点是右子树的中序第一个一棵树中序第一个是最左结点所以直接找右子树的最左结点即可。② 迭代器时如果it指向的结点的右子树为空代表当前结点已经访问完了且当前结点所在的子树也访问完了要访问的下一个结点在当前结点的祖先里面所以要沿着当前结点到根的祖先路径向上找。那么是哪个祖先呢cur parent-_left 时的parent结点因为孩子如果是父亲的右孩子完了父亲也就完了。只有孩子是父亲的左根据中序遍历的左根右左完了才能轮到根。不过也有可能一路找到了根节点也没有符合cur parent-_left情况的祖先此时parent为空代表整棵树都已经遍历完了。3.begin()返回中序的第一个节点也就是上图中的10。那么end()返回最后一个节点的下一个位置应该如何表示呢如上图当it指向50it 时50是40的右40是30的右30是18的右18到根了没有父亲没有找到孩子是父亲左的那个祖先这时父亲为空那我们就把it中的结点指针置为nullptr用nullptr去充当end。sgi_stl源码中红黑树增加了一个哨兵位头结点做为end(这哨兵位头结点和根互为父亲左指向最左结点右指向最右结点在插入删除的过程中要实时维护。相比我们用nullptr作为end()各有利弊直接用空做end()需要在重载operator--时特殊处理一下让迭代器结点指向最右结点。4.迭代器--的实现跟的思路完全类似只是逻辑正好反过来因为他访问顺序是右子树-根结点-左子树。对end()位置--一定要注意要特殊处理。self operator--() { // 期望--end()能跳到最右节点 if (_node nullptr) { Node* maxright _root; while (maxright maxright-_right) { maxright maxright-_right; } _node maxright; return *this; } // 左子树不为空找左子树最右结点 else if (_node-_left) { _node _node-_left; while (_node-_right) _node _node-_right; return *this; } // 左子树为空 else { Node* parent _node-_parent; if (parent _node ! parent-_right) { _node parent; parent parent-_parent; } _node parent; return *this; } }const迭代器和链表部分思路一致是普通还是const我们通过模板参数传从而让编译器自己实例化避免我么写两份几乎一样的冗余代码。整体结构比较复杂一层套一层其实我感觉只有自己真正从头到尾写一遍才能真正捋清不然真的很混乱。map和set封装rbtreerbtree结构中实例化普通迭代器和const迭代器再下层普通迭代器和const迭代器都写在一个类模板中通过传递模板参数区分。3key不支持修改对应的结构中的其他位置不要忘记修改加上const。4operator[] -- 依靠insert1. 回顾一下 operator[] 和 insert 的行为V operator[](const K key) { std::pairiterator, bool ret _tree.Insert({ key, V() }); // 不管是否插入成功此时我们想插入的数据一定已经保存在iterator中 // 先取出iterator iterator it ret.first; // 再取出value并返回 return it-second; }三. 具体完整代码1rbtree.h#pragma once #include iostream // 实现一个Key-value结构的红黑树 enum Color { RED, BLACK }; // 结点里存什么类型的数据由传过来的模板参数T决定 template class T struct RBtreeNode { T _data; RBtreeNodeT* _left; RBtreeNodeT* _right; RBtreeNodeT* _parent; Color _color; RBtreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _color(RED) {} }; // 迭代器结构(普通 const版) template class T, class Ref, class Ptr class RBtreeIterator { typedef RBtreeNodeT Node; typedef RBtreeIteratorT, Ref, Ptr self; private: Node* _node; Node* _root; // 为了end()--能拿到根 public: RBtreeIterator(Node* node, Node* root) :_node(node) ,_root(root) {} Ref operator*() // T const T { return _node-_data; } // -有连续解引用的特性编译器自动处理要返回一个支持再次接引用的类型 Ptr operator-() // T* const T* { return (_node-_data); } bool operator(const self s) { return _node s._node; } bool operator!(const self s) { return _node ! s._node; } self operator() { // 右子树不为空找右子树最左结点 if (_node-_right) { _node _node-_right; while (_node-_left) _node _node-_left; return *this; // 不能直接返回_node产生临时对象不能给引用 } // 右子树为空 else { Node* parent _node-_parent; while (parent _node ! parent-_left) { _node parent; parent parent-_parent; } _node parent; // 不能直接返回parent产生临时对象不能给引用 return *this; } } //self operator(int) //{ // //} self operator--() { // 期望--end()能跳到最右节点 if (_node nullptr) { Node* maxright _root; while (maxright maxright-_right) { maxright maxright-_right; } _node maxright; return *this; } // 左子树不为空找左子树最右结点 else if (_node-_left) { _node _node-_left; while (_node-_right) _node _node-_right; return *this; } // 左子树为空 else { Node* parent _node-_parent; if (parent _node ! parent-_right) { _node parent; parent parent-_parent; } _node parent; return *this; } } //self operator--(int) //{ // //} }; template class K, class T, class KeyOfT class RBtree { typedef RBtreeNodeT Node; public: typedef RBtreeIteratorT, T, T* Iterator; typedef RBtreeIteratorT, const T, const T* ConstIterator; private: Node* _root nullptr; private: void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; Node* pparent parent-_parent; // 一定要记住每一个节点中都有一个_parent不要忘记更新 parent-_left subLR; if (subLR) // h为0的情况 subLR-_parent parent; subL-_right parent; parent-_parent subL; // 旋转完这个局部子树要看看pparent是否为空 // 也就是原本的parent是不是整棵树的根他还有没有父亲 if (pparent nullptr) { // 直接把新根给_root _root subL; subL-_parent nullptr; } else { if (parent pparent-_left) pparent-_left subL; else pparent-_right subL; subL-_parent pparent; } } void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; Node* pparent parent-_parent; // 一定要记住每一个节点中都有一个_parent不要忘记更新 parent-_right subRL; if (subRL) // h为0的情况 subRL-_parent parent; subR-_left parent; parent-_parent subR; // 旋转完这个局部子树要看看pparent是否为空 // 也就是原本的parent是不是整棵树的根他还有没有父亲 if (pparent nullptr) { // 直接把新根给_root _root subR; subR-_parent nullptr; } else { if (parent pparent-_left) pparent-_left subR; else pparent-_right subR; subR-_parent pparent; } } void _InOrder(Node* root) { if (root nullptr) return; KeyOfT kot; _InOrder(root-_left); std::cout kot(root-_data) ; _InOrder(root-_right); } // 统计节点个数 int _Size(Node* root) { return root nullptr ? 0 : _Size(root-_left) _Size(root-_right) 1; } public: Iterator Begin() { // 中序第一个--最左节点 Node* cur _root; while (cur cur-_left) { cur cur-_left; } return Iterator(cur, _root); } Iterator End() { return Iterator(nullptr,_root); } ConstIterator Begin() const { // 中序第一个--最左节点 Node* cur _root; while (cur cur-_left) { cur cur-_left; } return ConstIterator(cur, _root); } ConstIterator End() const { return ConstIterator(nullptr,_root); } std::pairIterator, bool Insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_color BLACK; return { Iterator(_root, _root), true}; } KeyOfT kot; Node* cur _root; Node* parent nullptr; // 找空位 while (cur) { if (kot(cur-_data) kot(data)) { parent cur; cur cur-_left; } else if (kot(cur-_data) kot(data)) { parent cur; cur cur-_right; } else return { Iterator(cur, _root), false }; } cur new Node(data); Node* newnode cur; // 记录插入位置留着返回 cur-_color RED; // 先直接插入 if (kot(parent-_data) kot(data)) { parent-_left cur; cur-_parent parent; } else if (kot(parent-_data) kot(data)) { parent-_right cur; cur-_parent parent; } // parent第一次确实是一定存在的但是我们这是一个循环向上处理的逻辑 // 当处理到根节点时根节点没有父亲 // 如果父亲存在且为红根据叔叔决定处理方式并向上处理 while (parent parent-_color RED) { // 通过爷爷找叔叔 Node* grandfather parent-_parent; // 叔叔在右 if (parent grandfather-_left) { Node* uncle grandfather-_right; // 如果叔叔存在且为红直接变色并向上处理 if (uncle uncle-_color RED) { // 变色 uncle-_color parent-_color BLACK; grandfather-_color RED; // 向上移动更新 cur grandfather; // !!颜色改变可能影响上级的是爷爷成为新的cur parent cur-_parent; } // 叔叔不存在 或者 存在且为黑变色旋转(单旋双旋) else { // 变色右旋 //if (parent grandfather-_left cur parent-_left) // uncle在右parent一定在左 if (cur parent-_left) { RotateR(grandfather); parent-_color BLACK; grandfather-_color RED; } // 变色左右双旋 if (cur parent-_right) { RotateL(parent); RotateR(grandfather); cur-_color BLACK; grandfather-_color RED; } break; // 不再继续向上更新 } } // 叔叔在左 else { Node* uncle grandfather-_left; // 叔叔存在且为红 if (uncle uncle-_color RED) { // 变色 uncle-_color parent-_color BLACK; grandfather-_color RED; // 向上移动更新 cur grandfather; // !!颜色改变可能影响上级的是爷爷成为新的cur parent cur-_parent; } // 叔叔不存在 或者 存在且为黑变色旋转(单旋双旋) else { // 变色左旋 if (cur parent-_right) { RotateL(grandfather); parent-_color BLACK; grandfather-_color RED; } // 变色左右双旋 if (cur parent-_left) { RotateR(parent); RotateL(grandfather); cur-_color BLACK; grandfather-_color RED; } break; } } } // 如果没处理到根根还是黑的但是可能处理根时将根变为红需要变回来 // 简单处理无论是否处理到根最后都将根置黑一次 _root-_color BLACK; // 如果父亲存在且为黑直接插入结束return true;(不止这一种情况return true;) return {Iterator(newnode, _root), true}; } Iterator Find(const K key) { KeyOfT kot; Node* cur _root; while (cur) { if (kot(cur-_data) key) cur cur-_right; else if (kot(cur-_data) key) cur cur-_left; else return Iterator(cur, _root); } return End(); } void InOrder() { _InOrder(_root); std::cout std::endl; } int Size() { return _Size(_root); } };2mymap.h#pragma once #include rb_tree.h namespace laosi { template class K, class V class map { struct mapKeyOfT { K operator()(const std::pairK, V kv) { return kv.first; } }; private: RBtreeK, std::pairconst K, V, mapKeyOfT _tree; public: typedef typename RBtreeK, std::pairconst K, V, mapKeyOfT::Iterator iterator; typedef typename RBtreeK, std::pairconst K, V, mapKeyOfT::ConstIterator const_iterator; iterator begin() { return _tree.Begin(); } iterator end() { return _tree.End(); } const_iterator begin() const { return _tree.Begin(); } const_iterator end() const { return _tree.End(); } std::pairiterator, bool insert(const std::pairconst K, V kv) { return _tree.Insert(kv); } iterator find(const K key) { return _tree.Find(key); } V operator[](const K key) { std::pairiterator, bool ret _tree.Insert({ key, V() }); // 不管是否插入成功此时我们想插入的数据一定已经保存在iterator中 // 先取出iterator iterator it ret.first; // 再取出value并返回 return it-second; } }; void Print(const mapstd::string, std::string m) { for (const auto e : m) { std::cout e.first : e.second std::endl; } } void testmap01() { mapstd::string, std::string m; m.insert({ sort, 排序}); m.insert({ left, 左边 }); m.insert({ right, 右边 }); m.insert({ string, 字符串 }); // 需要迭代器支持 for (auto e : m) { // key值不支持修改 //e.first m; e.second m; std::cout e.first : e.second std::endl; } Print(m); // find mapstd::string, std::string::iterator it m.find(string); std::cout it-first : it-second std::endl; } void testmap02() // 统计次数 -- operator[] { std::string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 }; mapstd::string, int countmap; for (const auto str : arr) { countmap[str]; // 这种写法更简洁 } for (const auto e : countmap) std::cout e.first : e.second std::endl; std::cout std::endl; } }3myset.h#pragma once #include rb_tree.h namespace laosi { template class K class set { struct setKeyOfT { K operator()(const K k) { return k; } }; private: RBtreeK, const K, setKeyOfT _tree; public: typedef typename RBtreeK, const K, setKeyOfT::Iterator iterator; typedef typename RBtreeK, const K, setKeyOfT::ConstIterator const_iterator; iterator begin() { return _tree.Begin(); } iterator end() { return _tree.End(); } const_iterator begin() const { return _tree.Begin(); } const_iterator end() const { return _tree.End(); } std::pairiterator, bool insert(const K k) { return _tree.Insert(k); } iterator find(const K key) { return _tree.Find(key); } }; void Print(const setint s) { setint::const_iterator it s.end(); while (it ! s.begin()) { //*it 1; --it; std::cout *it ; } std::cout std::endl; } void testset01() { setint s; s.insert(5); s.insert(1); s.insert(14); s.insert(77); s.insert(2); s.insert(1); s.insert(30); setint::iterator it s.begin(); while (it ! s.end()) { //std::cout (*it) ; // key值不可修改 it; } std::cout std::endl; Print(s); // find std::cout *(s.find(77)) std::endl; //std::cout *(s.find(100)) std::endl; // 不能对空指针解引用 } }4test.cpp#include iostream #include mymap.h #include myset.h int main() { //laosi::setint s; //laosi::mapint, int m; laosi::testset01(); laosi::testmap01(); laosi::testmap02(); return 0; }