C++进阶——封装红黑树实现map和set

目录

1、源码及框架分析

2、模拟实现map和set

2.1 复用的红黑树框架及Insert

2.2 iterator的实现

2.2.1 iterator的核心源码

2.2.2 iterator的实现思路

2.3 map支持[ ]

2.4 map和set的代码实现

2.4.1 MyMap.h

2.4.2 MySet.h

2.4.3 RBTree.h

2.4.4 Test.cpp

---

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:// typedefs: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;  // red-black tree representing set
};// stl_map.h
template <class Key, class T, class Compare = less<Key>,class Alloc = alloc>
class map {
public:// typedefs: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;  // red-black tree representing 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:// insertpair<iterator, bool> insert_unique(const value_type& x);// erase and findsize_type erase(const key_type& x);iterator find(const key_type& x);protected:size_type node_count; // keeps track of size of treelink_type header;
};template <class Value>
struct __rb_tree_node : public __rb_tree_node_base {typedef __rb_tree_node<Value>* link_type;Value value_field;
};

template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>

删除查找用Key，插入用Value，KeyOfValue如果是一个仿函数，取Value中的Key。

2、模拟实现map和set

2.1 复用的红黑树框架及Insert

1. 这里相比源码调整一下，key参数就用K，value参数就用V，红黑树中的数据类型，我们使用T。

2. 源码中的pair的<比较，比较了key和value，但是红黑树只需要比较key，所以MyMap和MySet各自实现了一个只比较key的仿函数。MySet是为了兼容MyMap，所以也要实现。

3. const保证了不能修改key。

RBTree<K, pair<const K, V>, MapKfromT> _t;

RBTree<K, const K, SetKfromT> _t;

template<class K, class T, class KfromT>

class RBTree{}；

// 源码中 pair 支持的 < 重载
//template <class T1, class T2>
//bool operator<(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
//    return lhs.first < rhs.first || (!(rhs.first < lhs.first) && lhs.second < rhs.second);
//}// Mymap.h
namespace Lzc
{template<class K, class V>class MyMap{struct MapKfromT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:bool insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKfromT> _t;};
}// Myset.h
namespace Lzc
{template<class K>class MySet{struct SetKfromT{const K& operator()(const K& k){return k;}};public:bool insert(const K& k){return _t.Insert(k);}private:RBTree<K, const K, SetKfromT> _t;};
}// RBTree.h
namespace Lzc
{enum Color{RED,BLACK};template<class T>struct RBTreeNode{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){ }};template<class K, class T, class KfromT>class RBTree{typedef RBTreeNode<T> Node;public:KfromT KfT;bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (KfT(data) > KfT(cur->_data)){parent = cur;cur = cur->_right;}else if (KfT(data) < KfT(cur->_data)){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);if (KfT(data) > KfT(parent->_data))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;Node* uncle;if (parent == grandfather->_left){//    g//  p   uuncle = 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{//    g//  u   puncle = 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;}}}if (parent == nullptr)_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* pParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;subL->_parent = pParent;if (pParent == nullptr) // 当pParent == nullptr时,_root == parent{_root = subL;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}}void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;subR->_parent = pParent;if (pParent == nullptr)_root = subR;else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > KfT(cur->_data))cur = cur->_right;else if (key < KfT(cur->_data))cur = cur->_left;elsereturn cur;}return nullptr;}~RBTree(){Destroy(_root);_root = nullptr;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}private:Node* _root = nullptr;};
}

2.2 iterator的实现

2.2.1 iterator的核心源码

typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false;
const __rb_tree_color_type __rb_tree_black = true;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_OPERATORpointer 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;}
};

2.2.2 iterator的实现思路

1. 整体思路与list的iterator一致，封装节点的指针，迭代器类模板多传Ref和Ptr两个参数，一份模板实现iterator和const_iterator。

2. 重点是operator++和operator--的实现。operator++走中序遍历，左中右，

当左为空，表示左访问完了，访问中(其实只能访问中，给的节点就是访问完的中节点)，

如果右不为空，在右子树中进行，左中右，访问右子树的最左节点，

如果右为空(整个子树已经访问完了，如果这个子树是外面的右子树，那么外面一层的子树也访问完了，直到子树是外面子树的左子树，左子树访问完了，访问中)，就访问，当孩子是父亲左的那个父亲(祖先)，相当于外层左边的子树访问完了，然后访问中。

然后更新迭代器中的节点指针，返回*this。

operator--就是走右中左，基本相同。

3. begin和end。begin就给最左节点，end给nullptr，但是，--end()呢？ 

所以给迭代器类模板的增加一个成员变量_root(红黑树的根节点)，--end()就可以是最右节点。

2.3 map支持[ ]

map要支持[ ]主要需要修改insert返回值，

修改RBtree中的insert返回值为pair<Iterator,bool> Insert(const T& data)，

插入失败，就返回相同的key的value的引用。

插入成功，就返回key的value(默认值)的引用。

2.4 map和set的代码实现

2.4.1 MyMap.h

#pragma once
#include "RBTree.h"namespace Lzc
{template<class K, class V>class MyMap{struct MapKfromT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKfromT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKfromT>::ConstIterator const_iterator;pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}V& operator[](const K& k){iterator ret = _t.Insert({ k, V() }).first;return ret->second;}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}private:RBTree<K, pair<const K, V>, MapKfromT> _t;};
}

2.4.2 MySet.h

#pragma once#include "RBTree.h"namespace Lzc
{template<class K>class MySet{struct SetKfromT{const K& operator()(const K& k){return k;}};public:typedef typename RBTree<K, const K, SetKfromT>::Iterator iterator;typedef typename RBTree<K, const K, SetKfromT>::ConstIterator const_iterator;pair<iterator, bool> insert(const K& k){return _t.Insert(k);}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}private:RBTree<K, const K, SetKfromT> _t;};
}

2.4.3 RBTree.h

#pragma once#include <iostream>
#include <assert.h>using namespace std;namespace Lzc
{enum Color{RED,BLACK};template<class T>struct RBTreeNode{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){ }};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 && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){// --end，因为end == nullptr，所以最右节点需要_rootif (_node == nullptr){Node* MostRight = _root;while (MostRight->_right){MostRight = MostRight->_right;}_node = MostRight;}else if (_node->_left){Node* cur = _node->_left;while (cur->_right){cur = cur->_right;}_node = cur;}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 _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};template<class K, class T, class KfromT>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 { cur,_root };}Iterator End(){return { nullptr,_root };}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return { cur,_root };}ConstIterator End() const{return { nullptr,_root };}KfromT KfT;pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return { Iterator(_root,_root),true };}Node* parent = nullptr;Node* cur = _root;while (cur){if (KfT(data) > KfT(cur->_data)){parent = cur;cur = cur->_right;}else if (KfT(data) < KfT(cur->_data)){parent = cur;cur = cur->_left;}else{return { Iterator(cur,_root),false };}}cur = new Node(data);Node* newnode = cur; // cur可能后面会更新if (KfT(data) > KfT(parent->_data))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;Node* uncle;if (parent == grandfather->_left){//    g//  p   uuncle = 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{//    g//  u   puncle = 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;}}}if (parent == nullptr)_root->_col = BLACK;return { Iterator(newnode,_root),true };}void RotateR(Node* parent){Node* pParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;subL->_parent = pParent;if (pParent == nullptr) // 当pParent == nullptr时,_root == parent{_root = subL;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}}void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;subR->_parent = pParent;if (pParent == nullptr)_root = subR;else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}}Node* Find(const K& key){Node* cur = _root;while (cur){if (key > KfT(cur->_data))cur = cur->_right;else if (key < KfT(cur->_data))cur = cur->_left;elsereturn cur;}return nullptr;}~RBTree(){Destroy(_root);_root = nullptr;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}private:Node* _root = nullptr;};
}

2.4.4 Test.cpp

#include "MySet.h"
#include "MyMap.h"// 遍历 MyMap
void TestMapIterator()
{Lzc::MyMap<int, string> map;map.insert({ 1, "one" });map.insert({ 2, "two" });map.insert({ 3, "three" });cout << "Testing MyMap iterator:" << endl;for (auto it = map.begin(); it != map.end(); ++it){cout << "Key: " << it->first << ", Value: " << it->second << endl;}cout << "-----------------------------" << endl;
}// 反向遍历 MyMap
void TestMapReverseIterator()
{Lzc::MyMap<int, string> map;map.insert({ 5, "five" });map.insert({ 3, "three" });map.insert({ 7, "seven" });auto it = map.end();--it; // 移动到最后一个元素cout << "Testing MyMap reverse iterator:" << endl;while (it != map.begin()){cout << "Key: " << it->first << ", Value: " << it->second << endl;--it;}cout << "Key: " << it->first << ", Value: " << it->second << endl; // 打印第一个元素cout << "-----------------------------" << endl;
}// 测试 operator[] 和迭代器
void TestMapOperatorBracket()
{Lzc::MyMap<int, string> map;map[1] = "one";map[2] = "two";map[3] = "three";cout << "Testing MyMap operator[] and iterator:" << endl;for (auto it = map.begin(); it != map.end(); ++it){cout << "Key: " << it->first << ", Value: " << it->second << endl;}cout << "-----------------------------" << endl;
}// 遍历 MySet
void TestSetIterator()
{Lzc::MySet<int> set;set.insert(10);set.insert(20);set.insert(30);cout << "Testing MySet iterator:" << endl;for (auto it = set.begin(); it != set.end(); ++it){cout << "Key: " << *it << endl;}cout << "-----------------------------" << endl;
}// 反向遍历 MySet
void TestSetReverseIterator()
{Lzc::MySet<int> set;set.insert(50);set.insert(30);set.insert(70);auto it = set.end();--it; // 移动到最后一个元素cout << "Testing MySet reverse iterator:" << endl;while (it != set.begin()){cout << "Key: " << *it << endl;--it;}cout << "Key: " << *it << endl; // 打印第一个元素cout << "-----------------------------" << endl;
}// 测试空 MySet 的迭代器
void TestEmptySetIterator()
{Lzc::MySet<int> set;auto it = set.begin();auto end = set.end();cout << "Testing empty MySet iterator:" << endl;if (it == end){cout << "Set is empty, begin() == end()" << endl;}else{cout << "Set is not empty" << endl;}cout << "-----------------------------" << endl;
}void RunIteratorTests()
{TestMapIterator();TestMapReverseIterator();TestMapOperatorBracket();TestSetIterator();TestSetReverseIterator();TestEmptySetIterator();
}int main()
{RunIteratorTests();return 0;
}