目录前言Part1. map、set与红黑树Part2. 红黑树的改造Part2.1. map和set在传给红黑树模板参数的区别Part2.2. 传给红黑树模板中第一个K的意义Part2.3. 访问红黑树内数值与函数传参之间的矛盾Part3. 迭代器的实现Part3.1. 的重载Part3.2. --的重载Part4. 代码实现Part4.1. setPart4.1. mapPart4.2. 红黑树Part5. 结语前言了解STL容器最好的方法就是亲自去实现它接下来跟随小编的视角来看看在实现map和set容器中会遇到的问题与困难吧。lets go!!!!!!!!!Part1. map、set与红黑树map和set的底层都是红黑树都用红黑树来管理数据。因此了解红黑树的实现是必要的至于怎么实现红黑树可以看这两篇博客【知识讲解】 红黑树的基本接口讲解插入、判断等等-CSDN博客【知识讲解】 红黑树的删除讲解-CSDN博客Part2. 红黑树的改造我们知道set只存一个数据就是单单的key而map存两个即key和value两个构成映射关系。关键这两个底层都是红黑树要想实现不是得实现两种红黑树实则不用这里用的的方法就是C中的模板我们来看。同iterator和const_iterator的实现相似都是利用模板不定参数依靠编译器自己实现来简化代码。逻辑 1 map、set模板templateclass k,class v,··· 2 给红黑树的模板 rb_treek,k,····//set rb_treek,pairk,v,····//map 3 节点rb_tree_nodeclass v 4 rb_tree_nodev//set rb_tree_nodepairk,v//mapPart2.1. map和set在传给红黑树模板参数的区别在红黑树模板中我们给出的第一个参数是键值第二个给出的是数据由于在set中数据和键值都是一起的所以两个写相同的但是在map中就是给value了。在给红黑树的模板中为什么map的第二个参数是pair这个呢因为这里模板第二个参数指代的意思是指红黑树每个结点的类型在map的红黑树每个节点类型自然是pair了因为有两个参数。Part2.2. 传给红黑树模板中第一个K的意义那为什么还要多一个参数就是第一个k这个参数代表的是键值为什么要把这个独立出来呢因为在红黑树的接口中删除等需要这个类型所以必须把这个独立出来。而没有单独的需要value类型的接口只会需要键值和value结合的整体类型。故不用把value独立出来。Part2.3. 访问红黑树内数值与函数传参之间的矛盾由于map传给红黑树类型为pair他访问的方式是.first/.second与set的不同它传的就可以直接用。他们的访问方式有区别我们怎么解决呢我们可以利用一个萃取器就是仿函数我们用这个函数取出来需要的数据在map和set里面分别按照需求实现这样就解决了。Part3. 迭代器的实现迭代器的大体实现主要还是和list一样关键的难点在于的重载我们来看Part3.1. 的重载为什么实现比较难因为按照我们的逻辑红黑树的遍历是中序遍历也就是说在当前迭代器后应该到它在中序遍历中的下一个节点对应的迭代器关键我们怎么搞呢我们来看图我们要求A处迭代器后的结果也就是要到下一个中序遍历的迭代器。中序遍历的顺序是左-根-右。A为这个局部树的根我们现在能到这个位置说明左边b已经遍历完了现在该到A的右子树了到A的右子树d按照左-根-右应该遍历他的左如此循环直到结点的左边为nullptr为止这个节点就是下一个中序遍历的节点。结束。我们现在能到这个位置说明左右已经遍历完了说明其中序遍历结束了该回到上一个根节点了到B。由于A为B右子说明B右也遍历完了说明B的中序遍历也结束了回到C直到D由于C为D的左边象征这左边遍历完该到根也就是D本身。这个节点就是下一个中序遍历的节点。结束。总结就是1当当前节点的右边为不为空找其右子树的最左节点。2若为空则向上索引直到找到节点x的父亲节点的左边为x返回父亲节点当然要是父亲节点为空说明此时x为根节点说明此时整个树遍历完了返回nullptr结束。Part3.2. --的重载我们上面重载的实现其实埋下了一个隐祸就是当end()--时候我们按照上面的逻辑end()为nullptr对这个--肯定会有问题因此我们就要判断当当前节点为nullptr时我们返回_root的最右节点中序遍历的最后一个关键是我们的迭代器没有_root因此我们要加一个_root成员来解决。p.s. STL库解决这个问题是用一个哨兵位它的_left指向整个树的最左_right指向最右它的_parent指向_root_root的_parent指向它这样确实会比较方便但是我们还要注意eraseinsert对于这个的维护。Part4. 代码实现Part4.1. set#include头.h namespace all { templateclass k class set { struct SetKeyOrT//萃取器 { const k operator()(const k key) { return key; } }; public: typedef typename RBTreek,const k, SetKeyOrT::iterator iterator; typedef typename RBTreek, const k, SetKeyOrT::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(); } bool insert(const k key) { return _t.insert(key); } private: RBTreek, const k, SetKeyOrT _t; }; }Part4.1. map#include头.h namespace all { templateclass k,class v class map { struct MapKeyOrT { const k operator()(const pairk, v p) { return p.first; } }; public: typedef typename RBTreeconst k, pairconst k, v, MapKeyOrT::iterator iterator; typedef typename RBTreeconst k, pairconst k, v, MapKeyOrT::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(); } bool insert(const pairk,v value) { return _t.insert(value); } private: RBTreeconst k, pairconst k, v, MapKeyOrT _t; }; }Part4.2. 红黑树#pragma once #includeiostream #includevector #includemap using namespace std; enum colour { RED , BLACK }; templateclass T//红黑树节点 struct RBTreeNode { T _data; RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; colour _col; RBTreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { } }; templateclass T,class Ref,class Ptr class RBTreeIterator; templateclass k , class T ,class KeyOrT class RBTree { typedef RBTreeNodeT Node; public: typedef RBTreeIteratorT, T, T* iterator; typedef RBTreeIteratorT, const T, const T* const_iterator; iterator begin() { Node* cur _root; while (cur!nullptrcur-_left ! nullptr) { cur cur-_left; } return iterator(cur,_root); } iterator end() { return iterator(nullptr,_root); } const_iterator begin()const { Node* cur _root; while (cur ! nullptr cur-_left ! nullptr) { cur cur-_left; } return iterator(cur,_root); } const_iterator end()const { return iterator(nullptr,_root); } bool insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; return true; } Node* cur _root; Node* parent nullptr; while (cur ! nullptr) { if (KeyOrT()(cur-_data) KeyOrT()(data)) { parent cur; cur cur-_left; } else if (KeyOrT()(cur-_data) KeyOrT()(data)) { parent cur; cur cur-_right; } else { return false; } } cur new Node(data); cur-_parent parent; if (KeyOrT()(parent-_data) KeyOrT()(data)) { parent-_left cur; } else { parent-_right cur; } cur-_col RED; while (parent ! nullptr parent-_col RED) { Node* grandfather parent-_parent; if (grandfather-_left parent) { Node* uncle grandfather-_right; if (uncle ! nullptr uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else { if (cur parent-_left) { RotateR(grandfather); grandfather-_col RED; cur-_col RED; parent-_col BLACK; } else { RotateLR(grandfather); grandfather-_col RED; cur-_col BLACK; parent-_col RED; } break; } } else { Node* uncle grandfather-_left; if (uncle ! nullptr uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else { if (cur parent-_right) { RotateL(grandfather); grandfather-_col RED; cur-_col RED; parent-_col BLACK; } else { RotateRL(grandfather); grandfather-_col RED; cur-_col BLACK; parent-_col RED; } break; } } } _root-_col BLACK; return true; } bool erase(const k key) { Node* z find(key); Node* x nullptr; if (z nullptr) { return false; } colour col z-_col; Node* parent z-_parent; int lor 0; if (z-_left nullptrz-_right!nullptr) { if (z-_parent nullptr) { _root z-_right; z-_right-_parent nullptr; z-_right-_col BLACK; delete z; return true; } if (z-_parent-_left z) { z-_parent-_left z-_right; lor -1; } else { z-_parent-_right z-_right; lor 1; } x z-_right; z-_right-_parent z-_parent; delete z; } else if (z-_left ! nullptr z-_right nullptr) { if (z-_parent nullptr) { _root z-_left; z-_left-_parent nullptr; z-_left-_col BLACK; delete z; return true; } if (z-_parent-_left z) { z-_parent-_left z-_left; lor -1; } else { z-_parent-_right z-_left; lor 1; } x z-_left; z-_left-_parent z-_parent; delete z; } else if (z-_left nullptr z-_right nullptr) { if (z-_parent nullptr) { delete z; _root nullptr; return true; } if (z-_parent-_left z) { z-_parent-_left nullptr; lor -1; } else { z-_parent-_right nullptr; lor 1; } x nullptr; delete z; } else { Node* y z-_right; while (y-_left ! nullptr) { y y-_left; } z-_kv y-_kv; col y-_col; parent y-_parent; if (y-_parent-_left y) { y-_parent-_left y-_right; lor -1; } else { y-_parent-_right y-_right; lor 1; } x y-_right; if (y-_right ! nullptr) { y-_right-_parent y-_parent; } delete y; } if (col RED) { return true; } Node* w nullptr; if (lor 1) { w parent-_left; } else { w parent-_right; } while (x ! _root (xnullptr||x-_colBLACK)) { if (lor -1) { if (w-_col RED) { w-_col BLACK; parent-_col RED; Node* tem w-_left; RotateL(parent); w tem; } else if (w-_col BLACK(w-_leftnullptr||w-_left-_colBLACK)(w-_rightnullptr||w-_right-_colBLACK)) { w-_col RED; x parent; if (x _root) { break; } else { if (x-_parent-_left x) { w x-_parent-_right; lor -1; } else { w x-_parent-_left; lor 1; } parent x-_parent; } } else if (w-_col BLACK w-_left ! nullptr w-_left-_col RED (w-_right nullptr || w-_right-_col BLACK)) { w-_left-_col BLACK; w-_col RED; Node* tem w-_left; RotateR(w); w tem; } else if (w-_col BLACK w-_right ! nullptr w-_right-_col RED) { w-_col parent-_col; parent-_col BLACK; w-_right-_col BLACK; RotateL(parent); x _root; } } else { if (w-_col RED) { w-_col BLACK; parent-_col RED; Node* tem w-_right; RotateR(parent); w tem; } else if (w-_col BLACK (w-_left nullptr || w-_left-_col BLACK) (w-_right nullptr || w-_right-_col BLACK)) { w-_col RED; x parent; if (x _root) { break; } else { if (x-_parent-_left x) { w x-_parent-_right; lor -1; } else { w x-_parent-_left; lor 1; } parent x-_parent; } } else if (w-_col BLACK w-_right ! nullptr w-_right-_col RED (w-_left nullptr || w-_left-_col BLACK)) { w-_right-_col BLACK; w-_col RED; Node* tem w-_right; RotateL(w); w tem; } else if (w-_col BLACK w-_left ! nullptr w-_left-_col RED) { w-_col parent-_col; parent-_col BLACK; w-_left-_col BLACK; RotateR(parent); x _root; } } } if (x ! nullptr) { x-_col BLACK; } _root-_col BLACK; return true; } void InOrder()const { _InOrder(_root); } void Is_RBTree() { if (_Is_RBTree(_root) ! -1) { cout YES endl; } else { cout NO endl; } } Node* find(const k key) { Node* cur _root; while (cur ! nullptr) { if (KeyOrT()(cur-_data) KeyOrT()(data)) { cur cur-_left; } else if (KeyOrT()(cur-_data) KeyOrT()(data)) { cur cur-_right; } else { return cur; } } return nullptr; } private: void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; subL-_right parent; if (parent-_parent ! nullptr) { if (parent-_parent-_left parent) { parent-_parent-_left subL; } else { parent-_parent-_right subL; } } else { _root subL; } if (subLR ! nullptr) { subLR-_parent parent; } subL-_parent parent-_parent; parent-_parent subL; } void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; subR-_left parent; if (parent-_parent ! nullptr) { if (parent-_parent-_left parent) { parent-_parent-_left subR; } else { parent-_parent-_right subR; } } else { _root subR; } if (subRL ! nullptr) { subRL-_parent parent; } subR-_parent parent-_parent; parent-_parent subR; } void RotateLR(Node* parent) { Node* subL parent-_left; RotateL(subL); RotateR(parent); } void RotateRL(Node* parent) { Node* subR parent-_right; RotateR(subR); RotateL(parent); } void _InOrder(Node* root)const { if (root nullptr) return; _InOrder(root-_left); cout root-_kv.second : root-_kv.second endl; _InOrder(root-_right); } int _Is_RBTree(Node* root) { if (root nullptr) return 0; int left _Is_RBTree(root-_left); int right _Is_RBTree(root-_right); if (left -1 || right -1) { return -1; } if (left ! right) { return -1; } if (root-_col RED) { if (root-_left ! nullptr) { if (root-_left-_col ! BLACK) { return -1; } } if (root-_right ! nullptr) { if (root-_right-_col ! BLACK) { return -1; } } return left 0; } else { return left 1; } } Node* _root nullptr; }; templateclass T, class Ref, class Ptr class RBTreeIterator { typedef RBTreeIteratorT, Ref, Ptr self; typedef RBTreeNodeT Node; public: RBTreeIterator(Node* node,Node* root) :_node(node) ,_root(root) { } self operator() { if (_node-_right ! nullptr) { Node* cur _node-_right; while(cur-_left ! nullptr) { cur cur-_left; } _node cur; } else { Node* parent _node-_parent; while (parent!nullptr _node ! parent-_left) { _node parent; parent parent-_parent; } _node parent; } return *this; } self operator--() { if (_node nullptr) { Node* cur _root; while (cur-_right ! nullptr) { cur cur-_right; } _node cur; return *this; } else { if (_node-_left ! nullptr) { Node* cur _node-_left; while (cur-_right ! nullptr) { cur cur-_right; } _node cur; } else { Node* parent _node-_parent; while (parent ! nullptr _node ! parent-_right) { _node parent; parent parent-_parent; } _node parent; } } return *this; } Ref operator*() { return _node-_data; } Ptr operator-() { return (_node-_data); } bool operator!(const self s)const { return s._node ! _node; } private: Node* _node; Node* _root;//多一个_root };Part5. 结语这篇文章我们认识到了map和set的实现接下来小编会带来哈希表的相关知识敬请期待~最后祝大家可以春风得意马蹄疾一日看尽长安花最后的最后要是觉得本文还可以的话可以点点赞关注小编一波谢谢大家~
)
