【C++筆記】紅黑樹封裝map和set深度剖析

在這里插入圖片描述

🔥個人主頁：大白的編程日記

🔥專欄：C++筆記

文章目錄

【C++筆記】紅黑樹封裝map和set深度剖析
- 前言
- 一. 源碼及框架分析
- - 1.1 源碼框架分析
- 二. 模擬實現map和set
- - 2.1封裝map和set
- 三.迭代器
- - 3.1思路分析
  - 3.2 代碼實現
- 四.operator[]
- - 4.1思路分析
- 五.源碼
- 后言

前言

哈嘍，各位小伙伴大家好!上期我們講了紅黑樹。今天我們來講一下用紅黑樹封裝map和set。話不多說，我們進入正題！向大廠沖鋒

一. 源碼及框架分析

我們看一下源碼是如何實現紅黑樹封裝map和set。

參考SGI-STL30版本源代碼，map和set的源代碼在map/set/stl_map.h/stl_set.h/stl_tree.h等幾個頭文件中。

// 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:// 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; // 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;
};

1.1 源碼框架分析

通過下圖對框架的分析，我們可以看到源碼中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 insert的是pair對象，但是find和ease的是Key對象。

所以我們可以通過模版參數來控制紅黑樹底層的結構。
所以不用實現兩顆紅黑樹，但是本質還是編譯器根據模版參數生成兩顆不同的紅黑樹。

二. 模擬實現map和set

這里借鑒源碼的底層實現。
我們也自己模擬實現出我們的mymap和myset.

2.1封裝map和set

參考源碼框架，map和set復用之前我們實現的紅黑樹。
我們這里相比源碼調整?下，key參數就用K，value參數就用V，紅黑樹中的數據類型，我們使用T。
其次因為RBTree實現了泛型不知道T參數導致是K，還是pair<K, V>，那么insert內部進行插入邏輯比較時，就沒辦法進行比較，因為pair的默認支持的是key和value?起參與比較，我們需要時的任何時候只比較key，所以我們在map和set層分別實現?個MapKeyOfT和SetKeyOfT的仿函數傳給RBTree的KeyOfT，然后RBTree中通過KeyOfT仿函數取出T類型對象中的key，再進行比較，具體細節參考如下代碼實現。

set.h:

template<class k>
class set
{
public:struct SetKeyofT{const k& operator()(const k& key){return key;}};bool insert(const k& kv){return _t.Insert(kv);}
private:qcj::RBTree<k,  const k, SetKeyofT> _t;
};

map.h:

template<class k,class v>
class map
{
public:struct MapKeyofT{const k& operator()(const pair<k, v>& key){return key.first;}};bool insert(const pair<k, v>& kv) {return _t.Insert(kv);}
private:qcj::RBTree<k, pair< const k, v>, MapKeyofT> _t;
};

insert:

bool Insert(const T& x) 
{if (_root == nullptr)//插入根節點{_root = new node(x);_root->col = BLACK;return true;};node* cur = _root;node* parent = nullptr;//保留父親節點KeyofT kot;while (cur){/*介質不冗余*/if (kot(x) < kot(cur->_date)){parent = cur;cur = cur->left;}else if (kot(x) > kot(cur->_date)){parent = cur;cur = cur->right;}else{return false;}}cur = new node(x);cur->col = RED;if (kot(x) > kot(parent->_date)){parent->right = cur;}else//相等插入左子樹{parent->left = cur;}cur->parent = parent;while (parent&&parent->parent&&parent->col == RED){node* grandfather = parent->parent;if (parent == grandfather->left){node* uncle = grandfather->right;//         g//       p    u//     c  c//u存在且為紅if (uncle&&uncle->col==RED){parent->col = uncle->col=BLACK;grandfather->col = RED;cur = grandfather;parent = cur->parent;}//u不存在或存在為黑else{//         g//       p    //     cif (cur == parent->left){RoRateR(grandfather);parent->col = BLACK;grandfather->col = RED;}//         g//       p    //         celse{RoRateL(parent);RoRateR(grandfather);cur->col = BLACK;grandfather->col = RED;}break;}}else{node* uncle = grandfather->left;//         g//       u   p    //          c  c//u存在且為紅if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;grandfather->col = RED;cur = grandfather;parent = cur->parent;}//u不存在或存在為黑else{//         g//            p    //              cif (cur == parent->right){RoRateL(grandfather);parent->col = BLACK;grandfather->col = RED;}//         g//            p    //          celse{RoRateR(parent);RoRateL(grandfather);cur->col = BLACK;grandfather->col = RED;}break;}}}_root->col = BLACK;//循環結束把根變黑return true;
}

find：

node* Find(const k& x)
{node* ret = nullptr;node* cur = _root;while (cur){if (x < kot(cur)){cur = cur->left;}else if (x > kot(cur)){cur = cur->right;}else{ret = cur;//保留當前節點cur = cur->left;//繼續向左子樹查找中序的第一個}}return ret;
}

這里通過仿函數就取出key控制了比較邏輯。

三.迭代器

3.1思路分析

operator++
operator- -
迭代器的key修改問題

如果我們這樣實現的迭代器是可以修改的key的。
但是紅黑樹的key是不能被修改的。那怎么辦呢？
我們只需要把紅黑樹的第二個模版參數的key改為
const key即可這樣迭代器的模版參數T的key也是const的了
set的iterator也不支持修改，我們把set的第?個模板參數改成const K即可，

qcj::RBTree<k, pair< const k, v>, MapKeyofT> _t;
qcj::RBTree<k,  const k, SetKeyofT> _t;

對比庫里的迭代器
為了實現反向迭代器我們可以在operator- -多加一個判斷。
同時還需要在迭代器里面加一個_root節點
運算符重載
運算符重載比較簡單具體參考下面的代碼

3.2 代碼實現

template<class T,class Ref,class Ptr>
struct RBTreeIteraor
{using node= RBNode<T>;using self= RBTreeIteraor< T, Ref, Ptr >;node* _node;node* _root;RBTreeIteraor(node* Node,node* root):_node(Node),_root(root){}self& operator++(){if (_node == nullptr){node* cur = _root;while (cur->right){cur = cur->right;}}else if (_node->right!=nullptr){node* cur = _node->right;while (cur->left){cur = cur->left;}_node = cur;}else{node* parent = _node->parent;while (parent&&_node != parent->left){_node = parent;parent = _node->parent;}_node = parent;}return *this;}self& operator--(){if (_node == nullptr){node* cur = _root;while (cur->right){cur = cur->right;}_node = cur;}else if (_node->left != nullptr){node* cur = _node->left;while (cur->right){cur = cur->right;}_node = cur;}else{node* parent = _node->parent;while (parent && _node != parent->right){_node = parent;parent = _node->parent;}_node = parent;}return *this;}Ref operator*(){return _node->_date;}Ptr operator->(){return &_node->_date;}bool operator==(const self& tmp) const{return _node==tmp._node;}bool operator!=(const self& tmp) const{return _node != tmp._node;}
};

四.operator[]

4.1思路分析

對于map我們還需要支持operator[]。
對于operator[]我們前面已經講過底層實現了。
參考博文：map的operator[]底層剖析
主要就是insert來支持的。改一下返回值即可。
讓insert返回迭代器和bool的pair即可。
返回insert迭代器的second也就是value即可。

v& operator[](const k& key)
{pair<iterator, bool> ret = _t.Insert(make_pair(key, v()));return ret.first->second;
}

五.源碼

set.h

#pragma once
#include"RBTree.h"
namespace qcj
{template<class k>class set{public:struct SetKeyofT{const k& operator()(const k& key){return key;}};public:typedef typename RBTree<k,  const k, SetKeyofT>::Iteratoriterator;typedef typename RBTree<k, const k, SetKeyofT>::Const_Iteratorconst_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& kv){return _t.Insert(kv);}iterator find(const k& key){return _t.find(key);}private:qcj::RBTree<k,  const k, SetKeyofT> _t;};void Print(const set<int>& s){set<int>::iterator it = s.end();while (it != s.begin()){--it;// 不?持修改//*it += 2;cout << *it << " ";}cout << endl;}void test_set(){set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}for (auto e : s){e += 1;cout << e << " ";}cout << endl;}}

map.h

#pragma once
#include"RBTree.h"
namespace qcj 
{template<class k,class v>class map{public:struct MapKeyofT{const k& operator()(const pair<k, v>& key){return key.first;}};public:typedef typename RBTree<k, pair<const  k, v>, MapKeyofT>::Iteratoriterator;typedef typename RBTree<k, pair<const  k, v>, MapKeyofT>::Const_Iteratorconst_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);}iterator find(const k& key){return _t.find(key);}v& operator[](const k& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, v()));return ret.first->second;}private:qcj::RBTree<k, pair< const k, v>, MapKeyofT> _t;};void test_map(){map<int,int> dict;dict.insert({1,1});dict.insert({2,2 });dict.insert({3,3 });dict.insert({ 4,4 });dict.insert({ 5,5 });dict.insert({ 6,6 });map<int,int>::iterator it = dict.end();while (it != dict.begin()){--it;// 不能修改first，可以修改second//it->first += 'x';it->second += 1;cout << it->first << ":" << it->second << endl;}cout << endl;}
}

RBTree.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace qcj
{enum coloros{RED,BLACK};template<class T>struct RBNode{using node= RBNode<T>;T _date;node* left;//左節點node* right;//右節點node* parent;//父親節點coloros col;//顏色RBNode(const T& date):_date(date), left(nullptr), right(nullptr), parent(nullptr){}};template<class T,class Ref,class Ptr>struct RBTreeIteraor{using node= RBNode<T>;using self= RBTreeIteraor< T, Ref, Ptr >;node* _node;node* _root;RBTreeIteraor(node* Node,node* root):_node(Node),_root(root){}self& operator++(){if (_node == nullptr){node* cur = _root;while (cur->right){cur = cur->right;}}else if (_node->right!=nullptr){node* cur = _node->right;while (cur->left){cur = cur->left;}_node = cur;}else{node* parent = _node->parent;while (parent&&_node != parent->left){_node = parent;parent = _node->parent;}_node = parent;}return *this;}self& operator--(){if (_node == nullptr){node* cur = _root;while (cur->right){cur = cur->right;}_node = cur;}else if (_node->left != nullptr){node* cur = _node->left;while (cur->right){cur = cur->right;}_node = cur;}else{node* parent = _node->parent;while (parent && _node != parent->right){_node = parent;parent = _node->parent;}_node = parent;}return *this;}Ref operator*(){return _node->_date;}Ptr operator->(){return &_node->_date;}bool operator==(const self& tmp) const{return _node==tmp._node;}bool operator!=(const self& tmp) const{return _node != tmp._node;}};template<class k, class T, class KeyofT>class RBTree{using node = RBNode<T>;public:RBTree() = default;using Iterator = RBTreeIteraor<T, T&, T*>;using Const_Iterator = RBTreeIteraor<T, const T&, const T*>;Iterator Begin(){node* cur = _root;while (cur&&cur->left){cur = cur->left;}return Iterator(cur,_root );}Iterator End(){return Iterator(nullptr,_root);}Const_Iterator Begin() const{node* cur = _root;while (cur&&cur->left){cur = cur->left;}return { cur,_root };}Const_Iterator End() const{return { nullptr,_root };}void Destory(const node* root){if (root == nullptr){return;}Destory(root->left);Destory(root->right);delete root;}~RBTree(){Destory(_root);_root = nullptr;}RBTree<k,T,KeyofT>& operator = (RBTree<k, T, KeyofT> tmp){swap(_root, tmp._root);return *this;}RBTree(const RBTree<k, T, KeyofT>& x){_root = Copy(x._root,nullptr);}node* Copy(node* x,node* parent){if (x == nullptr){return x;}node* root = new node(x->_date);root->parent = parent;root->left = Copy(x->left,root);root->right = Copy(x->right,root);return root;}void RoRateR(node* parent)//右單旋{node* subL = parent->left;node* subLR = subL->right;node* pparnet = parent->parent;parent->left = subLR;if (subLR){subLR->parent = parent;//修改父節點}subL->right = parent;parent->parent = subL;if (pparnet == nullptr)//parent就是根節點{_root = subL;subL->parent = nullptr;}else{if (pparnet->left == parent)//確定parent節點是左還是右{pparnet->left = subL;}else{pparnet->right = subL;}subL->parent = pparnet;//修改父節點}}void RoRateL(node* parent)//左單旋{node* subR = parent->right;node* subRL = subR->left;node* pparnet = parent->parent;parent->right = subRL;if (subRL)//防止subRL為空{subRL->parent = parent;//修改父節點}subR->left = parent;parent->parent = subR;if (pparnet == nullptr)//parent就是根節點{_root = subR;subR->parent = nullptr;}else{if (pparnet->left == parent)//確定parent節點是左還是右{pparnet->left = subR;}else{pparnet->right = subR;}subR->parent = pparnet;//修改父節點}}pair<Iterator,bool> Insert(const T& x) {if (_root == nullptr)//插入根節點{_root = new node(x);_root->col = BLACK;return make_pair(Iterator(_root, _root), true);};node* cur = _root;node* parent = nullptr;//保留父親節點KeyofT kot;while (cur){/*介質不冗余*/if (kot(x) < kot(cur->_date)){parent = cur;cur = cur->left;}else if (kot(x) > kot(cur->_date)){parent = cur;cur = cur->right;}else{return make_pair(Iterator(cur, _root), true);}}cur = new node(x);cur->col = RED;if (kot(x) > kot(parent->_date)){parent->right = cur;}else//相等插入左子樹{parent->left = cur;}cur->parent = parent;while (parent&&parent->parent&&parent->col == RED){node* grandfather = parent->parent;if (parent == grandfather->left){node* uncle = grandfather->right;//         g//       p    u//     c  c//u存在且為紅if (uncle&&uncle->col==RED){parent->col = uncle->col=BLACK;grandfather->col = RED;cur = grandfather;parent = cur->parent;}//u不存在或存在為黑else{//         g//       p    //     cif (cur == parent->left){RoRateR(grandfather);parent->col = BLACK;grandfather->col = RED;}//         g//       p    //         celse{RoRateL(parent);RoRateR(grandfather);cur->col = BLACK;grandfather->col = RED;}break;}}else{node* uncle = grandfather->left;//         g//       u   p    //          c  c//u存在且為紅if (uncle && uncle->col == RED){parent->col = uncle->col = BLACK;grandfather->col = RED;cur = grandfather;parent = cur->parent;}//u不存在或存在為黑else{//         g//            p    //              cif (cur == parent->right){RoRateL(grandfather);parent->col = BLACK;grandfather->col = RED;}//         g//            p    //          celse{RoRateR(parent);RoRateL(grandfather);cur->col = BLACK;grandfather->col = RED;}break;}}}_root->col = BLACK;//循環結束把根變黑return make_pair(Iterator(cur, _root), true);}bool check(node* cur,size_t tmp,size_t sum){if (cur == nullptr){if (tmp != sum){cout << "存在黑色結點的數量不相等的路徑" << endl;return false;}return true;}if (cur->col == RED){if (cur->parent->col == RED){cout << cur->_key << ":" << "存在連續紅節點" << endl;return false;}}else{sum++;}return check(cur->left, tmp, sum) && check(cur->right, tmp, sum);}bool ISRBTree(){return _ISRBTree(_root);}bool _ISRBTree(node* cur){if (cur == nullptr){return true;}if (cur->col == RED){return false;}size_t t = 0;while (cur){if (cur->col == BLACK){t++;}cur = cur->left;}return check(_root,t,0);}node* Find(const k& x){node* ret = nullptr;node* cur = _root;while (cur){if (x < kot(cur)){cur = cur->left;}else if (x > kot(cur)){cur = cur->right;}else{ret = cur;//保留當前節點cur = cur->left;//繼續向左子樹查找中序的第一個}}return ret;}void Inorder(){_Inorder(_root);cout << endl;}bool IsBalanceTree(){return _IsBalanceTree(_root);}void _Inorder(const node* root){if (root == nullptr){return;}_Inorder(root->left);cout << root->_key << ":" << root->_value << endl;_Inorder(root->right);}size_t Size(){return _Size(_root);}size_t _Size(const node* parent){if (parent){return 1 + _Size(parent->left) + _Size(parent->right);}else{return 0;}}size_t Height(){return _Height(_root);}size_t _Height(const node* parent){if (parent){return 1 + max(_Height(parent->left), _Height(parent->right));}else{return 0;}}bool Empty(){return _root == nullptr;}private:node* _root = nullptr;};
}