【C++】封装红黑树实现mymap和myset(源码及框架分析、实现复用红黑树的框架，并支持insert、支持iterator迭代器的实现、map支持[]下标运算符、map和set代码实现)

小编主页详情-请点击小编gitee代码仓库-请点击本文主要介绍了封装红黑树实现mymap和myset(源码及框架分析、实现复用红黑树的框架并支持insert、支持iterator迭代器的实现、map支持[]下标运算符、map和set代码实现内容全由作者原创无AI并带有配图帮助博友们更好的理解点个关注不迷路下面进入正文~~目录1. 源码及框架分析2. 模拟实现map和set2.1 实现复用红黑树的框架并支持insert2.2 支持iterator迭代器的实现2.3 map支持[]下标运算符2.4 map和set代码实现结语1.源码及框架分析SGI-STL30版本源代码map和set的源代码存放在map、set、stl_map.h、stl_set.h、stl_tree.h等几个头文件中。map和set的实现结构框架核心部分截取如下// set #ifndef __SGI_STL_INTERNAL_TREE_H #include stl_tree.h #endif #include stl_set.h #include stl_multiset.h // map #ifndef __SGI_STL_INTERNAL_TREE_H #include stl_tree.h #endif #include stl_map.h #include stl_multimap.h // stl_set.h template class Key, class Compare lessKey, class Alloc alloc class set { public: // 类型重定义 typedef Key key_type; typedef Key value_type; private: typedef rb_treekey_type, value_type, identityvalue_type, key_compare, Alloc rep_type; rep_type t; // 代表set的红黑树 }; // stl_map.h template class Key, class T, class Compare lessKey, class Alloc alloc class map { public: // 类型重定义 typedef Key key_type; typedef T mapped_type; typedef pairconst Key, T value_type; private: typedef rb_treekey_type, value_type, select1stvalue_type, key_compare, Alloc rep_type; rep_type t; // 代表map的红黑树 }; // 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; }; // stl_tree.h template class Key, class Value, class KeyOfValue, class Compare, class Alloc alloc class rb_tree { protected: typedef void* void_pointer; typedef __rb_tree_node_base* base_ptr; typedef __rb_tree_nodeValue rb_tree_node; typedef rb_tree_node* link_type; typedef Key key_type; typedef Value value_type; public: // insert使用第二个模板参数作为形参 pairiterator, bool insert_unique(const value_type x); // erase和find使用第一个模板参数作为形参 size_type erase(const key_type x); iterator find(const key_type x); protected: size_type node_count; // 记录树的节点数量 link_type header; }; template class Value struct __rb_tree_node : public __rb_tree_node_base { typedef __rb_tree_nodeValue* link_type; Value value_field; };通过图示对框架进行分析我们可以看到源码中的rb_tree使用了一个巧妙的泛型思想实现rb_tree是实现key的搜索场景还是key/value的搜索场景并非直接写死而是由第二个模板参数Value决定_rb_tree_node中存储的数据类型。set实例化rb_tree时第二个模板参数传入keymap实例化rb_tree时第二个模板参数传入pairconst key, T。这样一棵红黑树既可以实现仅key检索场景的set也可以实现key/value检索场景的map。需要注意源码里模板参数使用T代表value而内部定义的value_type并非我们日常key/value场景所说的value源码中的value_type实际是红黑树节点里真实存储的数据类型。rb_tree第二个模板参数Value已经控制节点存储的数据类型为什么还要传入第一个模板参数Key尤其是set两个模板参数完全相同。要注意map和set的find、erase函数参数均为Key第一个模板参数是传给find、erase等函数用作形参的类型。对于set两个参数一致但对于map二者完全不同map插入的是pair对象find和erase传入的是Key对象。2.模拟实现map和set2.1实现复用红黑树的框架并支持insert参考源码框架map和set复用我们之前实现的红黑树。这里相比源码做一点调整key参数使用Kvalue参数使用V红黑树内部存储的数据类型使用T。由于RBTree自身泛型无法区分T是单纯K还是pairK, V插入时进行大小比较会出现问题pair默认重载的小于运算符会同时对比key和value。我们需要保证任何场景下只对比key因此分别在map、set层实现MapKeyOfT、SetKeyOfT仿函数传给RBTree的KeyOfT。RBTree内部通过KeyOfT仿函数取出T对象里的key再执行比较。2.2支持iterator迭代器的实现迭代器核心源码struct __rb_tree_base_iterator { typedef __rb_tree_node_base::base_ptr base_ptr; base_ptr node; void increment() { if (node-right ! 0) { node node-right; while (node-left ! 0) node node-left; } else { base_ptr y node-parent; while (node y-right) { node y; y y-parent; } if (node-right ! y) node y; } } void decrement() { if (node-color __rb_tree_red node-parent-parent node) node node-right; else if (node-left ! 0) { base_ptr y node-left; while (y-right ! 0) y y-right; node y; } else { base_ptr y node-parent; while (node y-left) { node y; y y-parent; } node y; } }; template class Value, class Ref, class Ptr struct __rb_tree_iterator : public __rb_tree_base_iterator { typedef Value value_type; typedef Ref reference; typedef Ptr pointer; typedef __rb_tree_iteratorValue, Value, Value* iterator; __rb_tree_iterator() {} __rb_tree_iterator(link_type x) { node x; } __rb_tree_iterator(const iterator it) { node it.node; } reference operator*() const { return link_type(node)-value_field; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator-() const { return (operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self operator() { increment(); return *this; } self operator--() { decrement(); return *this; } inline bool operator(const __rb_tree_base_iterator x, const __rb_tree_base_iterator y) { return x.node y.node; } inline bool operator!(const __rb_tree_base_iterator x, const __rb_tree_base_iterator y) { return x.node ! y.node; } }迭代器实现思路分析迭代器整体实现框架和list的迭代器思路一致用一个类型封装节点指针再通过重载运算符让迭代器拥有类似指针的访问行为。此处难点是operator与operator--的实现。之前使用阶段我们分析过map和set的迭代器遍历遵循中序遍历顺序为左子树→根节点→右子树begin()会返回中序第一个节点对应的迭代器。迭代器的核心逻辑无需关注整棵树仅分析局部找到当前节点中序遍历的下一个节点1. 迭代器时若当前节点的右子树不为空代表当前节点遍历完成下一个节点是右子树中序第一个节点一棵树中序第一个节点是最左节点直接取右子树的最左节点即可。2. 迭代器时若当前节点右子树为空代表当前节点及所在子树全部遍历完毕下一个节点在当前节点的祖先链中需要沿着节点向上遍历祖先。若当前节点是父节点的左孩子按照中序左→根→右的规则下一个访问节点就是父节点。若当前节点是父节点的右孩子当前节点、父节点所在子树均遍历完成需要继续向上寻找祖先直到找到“自身是父节点左孩子”的那个祖先该祖先就是下一个访问节点。end()如何表示当 it 找不到满足条件的祖先此时将迭代器内部节点指针置为nullptr我们用nullptr充当end()。需要注意STL源码中红黑树会增加一个哨兵头节点作为end()哨兵头节点与根互为父子左指针指向整树最左节点右指针指向整树最右节点。相比我们用nullptr作为end()二者功能差别不大STL能实现的逻辑我们都可以实现仅在--end()时需要特殊处理让迭代器指向整树最右节点具体参考迭代器--的实现代码。迭代器--的实现思路和完全对称逻辑反向即可遍历顺序变为右子树→根节点→左子树具体参考下方完整代码。set的迭代器不允许修改存储的值我们将set传入RBTree的第二个模板参数改为const K即RBTreeK, const K, SetKeyOfT _t;。map的迭代器不允许修改key但允许修改value我们将map传入RBTree的pair第一个参数改为const K即RBTreeK, pairconst K, V, MapKeyOfT _t;。完整迭代器还存在大量细节需要调整完整代码参考下文。2.3map支持[]下标运算符map要支持[]运算符核心是修改insert的返回值类型让RBTree的Insert函数返回pairIterator, bool。拥有该返回值后实现[]运算符会非常简单具体参考下方代码实现。2.4map和set代码实现Myset.h#pragma once #include RBTree.h namespace cyh { templateclass K class set { struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator; typedef typename RBTreeK, const K, SetKeyOfT::ConstIterator 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(); } pairiterator, bool insert(const K key) { return _t.Insert(key); } private: RBTreeK, const K, SetKeyOfT _t; }; }Mymap.h#pragma once namespace cyh { templateclass K, class V class map { struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator; typedef typename RBTreeK, pairconst K, V, MapKeyOfT::ConstIterator 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(); } pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); } V operator[](const K key) { pairiterator, bool ret insert({ key, V() }); return ret.first-second; } private: RBTreeK, pairconst K, V, MapKeyOfT _t; }; }RBTree.h#pragma once #includeiostream #includeassert.h using namespace std; enum Colour { RED, BLACK }; templateclass T struct RBTreeNode { T _data; RBTreeNodeT* _parent; RBTreeNodeT* _left; RBTreeNodeT* _right; Colour _col; RBTreeNode(const T data) :_data(data) , _parent(nullptr) , _left(nullptr) , _right(nullptr) {} }; templateclass T, class Ref, class Ptr struct RBTreeIterator { typedef RBTreeNodeT Node; typedef RBTreeIteratorT, Ref, Ptr Self; Node* _node; Node* _root; RBTreeIterator(Node* node, Node* root) :_node(node) ,_root(root) {} Self operator() { if (_node-_right) { Node* cur _node-_right; while (cur-_left) { cur cur-_left; } _node cur; } else { Node* cur _node; Node* parent cur-_parent; while (parent parent-_right cur) { cur parent; parent cur-_parent; } _node parent; } return *this; } Self operator--() { if (_node nullptr) // --end() { // --end()特殊处理走到中序最后一个结点整棵树的最右结点 Node* rightMost _root; while (rightMost rightMost-_right) { rightMost rightMost-_right; } _node rightMost; } else if (_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); } bool operator(const Self s) const { return s._node _node; } bool operator!(const Self s) const { return s._node ! _node; } }; templateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: typedef RBTreeIteratorT, T, T* Iterator; typedef RBTreeIteratorT, const T, const T* ConstIterator; Iterator Begin() { Node* cur _root; while (cur cur-_left) { cur cur-_left; } return Iterator{ cur,_root }; } ConstIterator End() const { return ConstIterator{ nullptr,_root }; } ConstIterator Begin() const { Node* cur _root; while (cur cur-_left) { cur cur-_left; } return ConstIterator{ cur,_root }; } Iterator End() { return Iterator{ nullptr,_root }; } pairIterator,bool Insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; return { 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; } else if (kot(cur-_data) kot(data)) { parent cur; cur cur-_left; } else { return { Iterator(cur,_root), false }; } } cur new Node(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) { 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; return { Iterator(newnode, _root), false }; } void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) { subLR-_parent parent; } Node* pParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _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; 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; } } Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_right; } else if (cur-_kv.first key) { cur cur-_left; } else { return cur; } } return nullptr; } void InOrder() { _InOrder(_root); cout endl; } int Height() { return _Height(_root); } int Size() { return _Size(_root); } bool IsBalance() { if (_root nullptr) return true; if (_root-_col RED) return false; // 参考值 int refNum 0; Node* cur _root; while (cur) { if (cur-_col BLACK) { refNum; } cur cur-_left; } return Check(_root, 0, refNum); } private: bool Check(Node* root, int blackNum, const int refNum) { if (root nullptr) { // 前序遍历走到空时意味着一条路径走完了 //cout blackNum endl; if (refNum ! blackNum) { cout 存在黑色结点的数量不相等的路径 endl; return false; } return true; } // 检查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲就方便多了 if (root-_col RED root-_parent-_col RED) { cout root-_kv.first 存在连续的红色结点 endl; return false; } if (root-_col BLACK) { blackNum; } return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum); } void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_kv.first : root-_kv.second endl; _InOrder(root-_right); } int _Height(Node* root) { if (root nullptr) return 0; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; } int _Size(Node* root) { if (root nullptr) return 0; return _Size(root-_left) _Size(root-_right) 1; } private: Node* _root nullptr; };结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~