首页/资讯中心/详情

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

【C++】封装红黑树实现mymap和myset(源码及框架分析、实现复用红黑树的框架，并支持insert、支持iterator迭代器的实现、map支持[]下标运算符、map和set代码实现)
📅 发布时间：2026/7/26 23:40:11

小编主页详情<-请点击
小编gitee代码仓库<-请点击

本文主要介绍了封装红黑树实现mymap和myset(源码及框架分析、实现复用红黑树的框架，并支持insert、支持iterator迭代器的实现、map支持[]下标运算符、map和set代码实现，内容全由作者原创（无AI），并带有配图帮助博友们更好的理解，点个关注不迷路，下面进入正文~~

目录

1. 源码及框架分析

2. 模拟实现map和set

2.1 实现复用红黑树的框架，并支持insert

2.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 = less<Key>, class Alloc = alloc> class set { public: // 类型重定义： typedef Key key_type; typedef Key value_type; private: typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t; // 代表set的红黑树 }; // stl_map.h template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> class map { public: // 类型重定义： typedef Key key_type; typedef T mapped_type; typedef pair<const Key, T> value_type; private: typedef rb_tree<key_type, value_type, select1st<value_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_node<Value> rb_tree_node; typedef rb_tree_node* link_type; typedef Key key_type; typedef Value value_type; public: // insert使用第二个模板参数作为形参 pair<iterator, 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_node<Value>* link_type; Value value_field; };

通过图示对框架进行分析，我们可以看到源码中的rb_tree使用了一个巧妙的泛型思想实现，rb_tree是实现key的搜索场景，还是key/value的搜索场景，并非直接写死，而是由第二个模板参数Value决定_rb_tree_node中存储的数据类型。

set实例化rb_tree时，第二个模板参数传入key；map实例化rb_tree时，第二个模板参数传入pair<const 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和set

2.1实现复用红黑树的框架，并支持insert

参考源码框架，map和set复用我们之前实现的红黑树。
这里相比源码做一点调整，key参数使用K，value参数使用V，红黑树内部存储的数据类型使用T。
由于RBTree自身泛型无法区分T是单纯K，还是pair<K, 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_iterator<Value, 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，即RBTree<K, const K, SetKeyOfT> _t;。
map的迭代器不允许修改key，但允许修改value，我们将map传入RBTree的pair第一个参数改为const K，即RBTree<K, pair<const K, V>, MapKeyOfT> _t;。

完整迭代器还存在大量细节需要调整，完整代码参考下文。

2.3map支持[]下标运算符

map要支持[]运算符，核心是修改insert的返回值类型，让RBTree的Insert函数返回pair<Iterator, bool>。
拥有该返回值后，实现[]运算符会非常简单，具体参考下方代码实现。

2.4map和set代码实现

Myset.h

#pragma once #include "RBTree.h" namespace cyh { template<class K> class set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator; typedef typename RBTree<K, 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(); } pair<iterator, bool> insert(const K& key) { return _t.Insert(key); } private: RBTree<K, const K, SetKeyOfT> _t; }; }

Mymap.h

#pragma once namespace cyh { template<class K, class V> class map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator; typedef typename RBTree<K, pair<const 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(); } pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = insert({ key, V() }); return ret.first->second; } private: RBTree<K, pair<const K, V>, MapKeyOfT> _t; }; }

RBTree.h

#pragma once #include<iostream> #include<assert.h> using namespace std; enum Colour { RED, BLACK }; template<class T> struct RBTreeNode { T _data; RBTreeNode<T>* _parent; RBTreeNode<T>* _left; RBTreeNode<T>* _right; Colour _col; RBTreeNode(const T& data) :_data(data) , _parent(nullptr) , _left(nullptr) , _right(nullptr) {} }; template<class T, class Ref, class Ptr> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T, 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; } }; template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef RBTreeIterator<T, T&, T*> Iterator; typedef RBTreeIterator<T, 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 }; } pair<Iterator,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制作，希望各位博友能有所收获
欢迎各位博友的讨论，觉得不错的小伙伴，别忘了点赞关注哦~