C++學習：map/set源碼剖析+利用紅黑樹封裝map/set

? ? ? ? 前面我們已經學習了紅黑樹這個高級數據結構的實現。我們知道STL的map/set的底層數據結構為紅黑樹，本期就查看STL源碼的map/set，并結合著這之前的紅黑樹的實現，模擬實現map和set的一部分功能

? ? ? ? STL源碼：樓田莉子/CPP代碼學習

? ? ? ? 作者的個人gitee：樓田莉子/CPP代碼學習喜歡請支持一下，謝謝

STL——map/set源碼剖析

? ? ? ? 解析

模擬實現set/map

? ? ? ? 復用之前紅黑樹的代碼實現my_set/my_map，并實現Insert功能

? ? ? ? 紅黑樹的迭代器

? ? ? ? 迭代器的核心源碼

? ? ? ? 迭代器實現思路

? ? ? ? 迭代器++/--

? ? ? ? map的[]插入

源代碼

????????my_set.h

? ? ? ? my_map.h

? ? ? ? 測試代碼：

軟件推薦：source insight

1. 強大的代碼導航與分析（核心優勢）

2. 高效的源代碼編輯

3. 項目范圍的理解

4. 語言支持

5. 其他特點

拓展：條件編譯

? ? ? ? 基本語法為：

? ? ? ?

? ? ? ? 實際應用

? ? ? ? 跨平臺開發

? ? ? ? 調試與版本發布

? ? ? ? 功能定制

? ? ? ? 防止重復編譯頭文件

STL——map/set源碼剖析

? ? ? ? 源碼核心部分：

//set.h
#ifndef __SGI_STL_SET_H
#define __SGI_STL_SET_H#include <tree.h>
#include <stl_set.h>#ifdef __STL_USE_NAMESPACES
using __STD::set;
#endif /* __STL_USE_NAMESPACES */#endif /* __SGI_STL_SET_H *///map.h
#ifndef __SGI_STL_MAP_H
#define __SGI_STL_MAP_H#include <tree.h>
#include <stl_map.h>#ifdef __STL_USE_NAMESPACES
using __STD::map;
#endif /* __STL_USE_NAMESPACES */#endif /* __SGI_STL_MAP_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;typedef Compare key_compare;typedef Compare value_compare;
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 data_type;typedef T mapped_type;typedef pair<const Key, T> value_type;typedef Compare key_compare;   
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;static base_ptr minimum(base_ptr x){while (x->left != 0) x = x->left;return x;}static base_ptr maximum(base_ptr x){while (x->right != 0) x = x->right;return x;}
};
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>
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;typedef __rb_tree_color_type color_type;
protected:size_type node_count; // keeps track of size of treelink_type header;  
};

? ? ? ? 解析

? ? ? ? 它們之間的關系為：

? ? ? ? 我們發現了紅紅黑樹并不是像我們那樣直接寫死的，而是通過通過泛型決定紅黑樹存儲什么

? ? ? ? 通過下面兩張圖，我們發現set實例化rb_tree時第?個模板參數給的是key，map實例化rb_tree時第?個模板參數給的是pair<const key, T>，這樣?顆紅?樹既可以實現key搜索場景的set，也可以實現key/value搜索場景的map。

? ? ? ? stl_set.h

? ? ? ? stl-map.h??

????????注意：源碼??模板參數是?T代表value，?內部寫的value_type不是我們我們?常

key/value場景中說的value，源碼中的value_type反?是紅?樹結點中存儲的真實的數據的類型。

????????

????????rb_tree第?個模板參數Value已經控制了紅?樹結點中存儲的數據類型，為什么還要傳第?個模板參數Key呢？

????????對于map和set，find/erase時的函數參數都是Key，所以第?個模板參數是傳給find/erase等函數做形參的類型的。對于set??兩個參數是?樣的，但是對于map??就完全不?樣了，map insert的是pair對象，但是find和ease的是Key對象。

模擬實現set/map

? ? ? ? 復用之前紅黑樹的代碼實現my_set/my_map，并實現Insert功能

? ? ? ? 仿照源碼的形式，我們來模仿一下

????????我們這?相?源碼調整?下，key參數就?K，value參數就?V，紅?樹中的數據類型，我們使?T。

????????因為RBTree實現了泛型不知道T參數導致是K，還是pair<K, V>，那么insert內部進?插?邏輯

?較時，就沒辦法進??較（因為pair的默認?持的是key和value?起參與?較，我們需要時的任

何時候只?較key）

//作者自己為了可讀性對格式稍做修改
// 源碼中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); 
}

????????因此我們在map和set層分別實現?個MapKeyOfT和SetKeyOfT的仿函數傳給RBTree的KeyOfT，然后RBTree中通過KeyOfT仿函數取出T類型對象中的key，再進??較

? ? ? ? 源代碼：

//my_set.h
#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{template<class K>class Set{//取出set中所有的key值的仿函數//照顧map而設計的泛型struct SetKeyOf{const K& operator()(const K& k){return k;}};public:bool Insert(const K& k){return _t.Insert(k);}private:RBTree<K,K,SetKeyOf> _t;};
}
//my_map.h
#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{template<class K,class V>class Map{//取出set中所有的key值的仿函數//照顧map而設計的泛型struct MapKeyOf{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool Insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<K, V>,MapKeyOf> _t;};
}
//RBTree - 副本.h
#pragma once
#include<iostream>
using namespace std;
// 枚舉值表示顏色
enum Colour
{RED,BLACK
};
// 節點結構
//set
template<class T>
struct RBTreeNode
{// 這里更新控制平衡也需要parent指針T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;		//顏色 紅黑樹的關鍵RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};
template<class K, class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public://紅黑樹插入//旋轉代碼的實現跟AVL樹是一樣的，只是不需要更新平衡因子bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return 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 false;}} cur = new Node(data);// 新增節點。顏色紅色給紅色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;// g// p uif (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){// g// p u//c//單旋RotateR(grandfather);//變色parent->_col = BLACK;grandfather->_col = RED;} else{// g// p u// c//雙旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;} break;}} else{// g// u pNode * uncle = grandfather->_left;// 叔叔存在且為紅色-》變色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;} else // 情況?：叔叔不存在或者存在為黑{// 情況?：叔叔不存在或者存在為黑// 旋轉+變色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;} else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;} break;}}} _root->_col = BLACK;return true;}//紅黑樹的查找Node* Find(const K& key){Node* cur = _root;while(cur){if (kot(cur->_data) < key){cur = cur->_right;} else if (cur->_kv.first > key){cur = cur->_left;} else{return cur;}} return nullptr;}private://右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}//左單旋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 (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}Node* _root = nullptr;
};

? ? ? ? 使用案例：

#include <iostream>
using namespace std;// 示例1：平臺特定代碼
#ifdef _WIN32#define PLATFORM "Windows"
#elif __linux__#define PLATFORM "Linux"
#elif __APPLE__#define PLATFORM "macOS"
#else#define PLATFORM "Unknown"
#endif// 示例2：調試模式
#define DEBUG_MODE 1// 示例3：功能開關
#define FEATURE_A_ENABLED
#define FEATURE_B_LEVEL 3int main() {// 平臺檢測cout << "Running on: " << PLATFORM << endl;// 調試代碼#if DEBUG_MODEcout << "Debug information: Program started" << endl;#endif// 功能開關#ifdef FEATURE_A_ENABLEDcout << "Feature A is enabled" << endl;#endif// 帶值的條件編譯#if FEATURE_B_LEVEL > 2cout << "Feature B at high level (" << FEATURE_B_LEVEL << ")" << endl;#elif FEATURE_B_LEVEL > 0cout << "Feature B at basic level (" << FEATURE_B_LEVEL << ")" << endl;#elsecout << "Feature B is disabled" << endl;#endif// 頭文件保護模擬#ifndef MY_HEADER_GUARD#define MY_HEADER_GUARDcout << "This would be included only once" << endl;#endif// 嘗試再次包含相同內容（不會執行）#ifndef MY_HEADER_GUARDcout << "This won't be printed" << endl;#endifreturn 0;
}

? ? ? ? 紅黑樹的迭代器

? ? ? ? 迭代器的核心源碼

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

? ? ? ? 迭代器實現思路

????????iterator實現的?框架跟list的iterator思路是?致的，??個類型封裝結點的指針，再通過重載運算符實現，迭代器像指針?樣訪問的?為。

? ? ? ? 源代碼的迭代器：

? ? ? ? set

//set
class set {
public:// typedefs:typedef Key key_type;typedef Key value_type;typedef Compare key_compare;typedef Compare value_compare;
private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing set
//迭代器
public:typedef typename rep_type::const_pointer pointer;typedef typename rep_type::const_pointer const_pointer;typedef typename rep_type::const_reference reference;typedef typename rep_type::const_reference const_reference;typedef typename rep_type::const_iterator iterator;typedef typename rep_type::const_iterator const_iterator;typedef typename rep_type::const_reverse_iterator reverse_iterator;typedef typename rep_type::const_reverse_iterator const_reverse_iterator;typedef typename rep_type::size_type size_type;typedef typename rep_type::difference_type difference_type;
};

? ? ? ? map

//map
class map {
public:// typedefs:typedef Key key_type;typedef T data_type;typedef T mapped_type;typedef pair<const Key, T> value_type;typedef Compare key_compare;private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing map
//迭代器
public:typedef typename rep_type::pointer pointer;typedef typename rep_type::const_pointer const_pointer;typedef typename rep_type::reference reference;typedef typename rep_type::const_reference const_reference;typedef typename rep_type::iterator iterator;typedef typename rep_type::const_iterator const_iterator;typedef typename rep_type::reverse_iterator reverse_iterator;typedef typename rep_type::const_reverse_iterator const_reverse_iterator;typedef typename rep_type::size_type size_type;typedef typename rep_type::difference_type difference_type;
};

? ? ? ? 紅黑樹

//紅黑樹
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;typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;typedef __rb_tree_iterator<Value, Ref, Ptr>                   self;typedef __rb_tree_node<Value>* link_type;
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 simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;typedef __rb_tree_color_type color_type;
public:typedef Key key_type;typedef Value value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef rb_tree_node* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;
//迭代器typedef __rb_tree_iterator<value_type, reference, pointer> iterator;typedef __rb_tree_iterator<value_type, const_reference, const_pointer> const_iterator;
};

? ? ? ? 迭代器++/--

? ? ? ? 迭代器實現的難點是operator++和operator--的實現。之前我們知道map和set的迭代器?

的是中序遍歷，左?樹->根結點->右?樹，那么begin()會返回中序第?個結點的iterator也就是10

所在結點的迭代器。

???????????????????迭代器++的核?邏輯就是不看全局，只看局部，只考慮當前中序局部要訪問的下?個結點。

????????迭代器++時，如果it指向的結點的右?樹不為空，代表當前結點已經訪問完了，要訪問下?個結點是右?樹的中序第?個，?棵樹中序第?個是最左結點，所以直接找右?樹的最左結點即可。

????????迭代器++時，如果it指向的結點的右?樹空，代表當前結點已經訪問完了且當前結點所在的?樹也訪問完了，要訪問的下?個結點在當前結點的祖先??，所以要沿著當前結點到根的祖先路徑向上找。

????????如果當前結點是?親的左，根據中序左?樹->根結點->右?樹，那么下?個訪問的結點就是當前結點的?親；如下圖：it指向25，25右為空，25是30的左，所以下?個訪問的結點就是30。

????????end()如何表?呢？如下圖：當it指向50時，++it時，50是40的右，40是30的右，30是18的右，18到根沒有?親，沒有找到孩?是?親左的那個祖先，這是?親為空了，那我們就把it中的結點指針置為nullptr，我們?nullptr去充當end。需要注意的是stl源碼空，紅?樹增加了?個哨兵位頭結點做為end()，這哨兵位頭結點和根互為?親，左指向最左結點，右指向最右結點。相?我們?nullptr作為end()，差別不?。只是--end()判斷到結點時空，特殊處理?下，讓迭代器結點指向最右結點。

????????迭代器--的實現跟++的思路完全類似，邏輯正好反過來即可，因為他訪問順序是右?樹->根結點->左?樹

????????set的iterator也不?持修改，我們把set的第?個模板參數改成const K即可

RBTree<K,const K, SetKeyOfT> _t;

????????map的iterator不?持修改key但是可以修改value，我們把map的第?個模板參數pair的第?個參數改成const K即可

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

????????

//迭代器
template<class T,class Ref,class Ptr>
struct TreeIterator
{typedef RBTreeNode<T> Node;typedef TreeIterator<T,Ref,Ptr> Self;Node* _node;TreeIterator(Node* node):_node(node){}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;}//前置--Self& operator--(){// ...return *this;}//前置++Self& operator++(){//當前右不為空，下一個就是右子樹有序第一個（最左結點）if (_node->_right){Node*min=_node->_right;while (min->_left){min=min->_left;}_node=min;}//當前右為空，下一個就是孩子是父親左的那個祖先結點else{Node* cur = _node;Node* parent = _node->_parent;while (parent&& cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};

? ? ? ? map的[]插入

????????map要?持[]主要需要修改insert返回值?持，修改RBtree中的insert返回值為

pair<Iterator, bool> Insert(const T& data)

? ? ? ? 通過insert實現[]插入

//RBTree.hpair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_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 make_pair(Iterator(cur), false);}}cur = new Node(data);// 新增節點。顏色紅色給紅色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;// g// p uif (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){// g// p u//c//單旋RotateR(grandfather);//變色parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c//雙旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// g// u pNode* uncle = grandfather->_left;// 叔叔存在且為紅色-》變色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else // 情況?：叔叔不存在或者存在為黑{// 情況?：叔叔不存在或者存在為黑// 旋轉+變色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(Iterator(cur), true);}
//my_set.h
pair<iterator, bool> Insert(const K& k)
{return _t.Insert(k);
}
//my_map.h
pair<iterator, bool> Insert(const pair<K, V>& kv)
{return _t.Insert(kv);
}
V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert({key,V()});return ret.first->second;//用迭代器訪問value
}

源代碼
?

? ? ? ? RBTree.h

#pragma once
#include <iostream>
using namespace std;// 枚舉值表示顏色
enum Colour
{RED,BLACK
};// 節點結構
template<class T>
struct RBTreeNode
{// 這里更新控制平衡也需要parent指針T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;        //顏色 紅黑樹的關鍵RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr){}
};// 迭代器
template<class T, class Ref, class Ptr>
struct TreeIterator
{typedef RBTreeNode<T> Node;typedef TreeIterator<T, Ref, Ptr> Self;typedef TreeIterator<T, T&, T*> Iterator;Node* _node;TreeIterator(Node* node):_node(node){}// 允許從普通迭代器構造const迭代器TreeIterator(const Iterator& it):_node(it._node){}Ref operator* () const{return _node->_data;}Ptr operator->() const{return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}// 前置--Self& operator--(){if (_node->_left){// 左子樹存在，找左子樹的最右節點Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else{// 左子樹不存在，向上找第一個是父節點右孩子的節點Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}// 后置--Self operator--(int){Self tmp = *this;--(*this);return tmp;}// 前置++Self& operator++(){// 當前右不為空，下一個就是右子樹有序第一個（最左結點）if (_node->_right){Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}// 當前右為空，下一個就是孩子是父親左的那個祖先結點else{Node* cur = _node;Node* parent = _node->_parent;while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}// 后置++Self operator++(int){Self tmp = *this;++(*this);return tmp;}
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef TreeIterator<T, T&, T*> Iterator;typedef TreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* min = _root;while (min && min->_left){min = min->_left;}return Iterator(min);}Iterator End(){return Iterator(nullptr);}ConstIterator Begin() const{Node* min = _root;while (min && min->_left){min = min->_left;}return ConstIterator(min);}ConstIterator End() const{return ConstIterator(nullptr);}// 查找節點并返回const迭代器ConstIterator Find(const K& key) const{KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return ConstIterator(cur);}}return End();}// 紅黑樹插入// 旋轉代碼的實現跟AVL樹是一樣的，只是不需要更新平衡因子pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_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 make_pair(Iterator(cur), false);}}cur = new Node(data);// 新增節點。顏色紅色給紅色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;// g// p uif (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){// g// p u//c//單旋RotateR(grandfather);//變色parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// c//雙旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{// g// u pNode* uncle = grandfather->_left;// 叔叔存在且為紅色-》變色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else // 情況?：叔叔不存在或者存在為黑{// 情況?：叔叔不存在或者存在為黑// 旋轉+變色// g// u p// cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(Iterator(cur), true);}private:// 右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}// 左單旋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 (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}Node* _root = nullptr;
};

????????my_set.h

#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{template<class K>class Set{//取出set中所有的key值的仿函數//照顧map而設計的泛型struct SetKeyOf{const K& operator()(const K& k){return k;}};public://通過typename關鍵字來聲明迭代器類型typedef typename RBTree<K, K, SetKeyOf>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}pair<iterator, bool> Insert(const K& k){return _t.Insert(k);}private:RBTree<K,K,SetKeyOf> _t;};
}

? ? ? ? my_map.h

#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{template<class K,class V>class Map{//取出set中所有的key值的仿函數//照顧map而設計的泛型struct MapKeyOf{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOf>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){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 = _t.Insert({key,V()});return ret.first->second;//用迭代器訪問value}private:RBTree<K, pair<const K, V>,MapKeyOf> _t;};
}

? ? ? ? 測試代碼：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include "my_map.h"
#include "my_set.h"
#include <string>
using namespace std;
//迭代器源碼：
//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;
//	}
//};				
void test_set()
{The_Song_of_the_end_of_the_world::Set<int> s;s.Insert(4);s.Insert(2);s.Insert(1);s.Insert(6);The_Song_of_the_end_of_the_world::Set<int>::iterator it = s.begin();while (it != s.end()){cout<<*it<<" ";++it;}
}
void test_map()
{The_Song_of_the_end_of_the_world::Map<string, string> map;map.Insert({ "hello", "world" });map.Insert({ "apple", "banana" });map.Insert({ "dog", "cat" });The_Song_of_the_end_of_the_world::Map<string, string>::iterator it = map.begin();map["left"] = "左邊，剩余";map["insert"] = "插入";map["string"];while (it != map.end()){cout << it->first << " " << it->second << endl;++it;}
}
int main()
{//test_set();test_map();return 0;
}

軟件推薦：source insight

????????Source Insight 是一款為編寫和閱讀大型代碼項目而設計的源代碼編輯器和瀏覽器。它以其卓越的代碼導航和分析能力而聞名，尤其在 C/C++ 開發領域擁有大量忠實用戶。? ? ??

1. 強大的代碼導航與分析（核心優勢）

這是 Source Insight 的立身之本。它能快速解析整個代碼庫，構建一個詳細的符號數據庫（函數、變量、類、宏等），從而實現：

關系瀏覽：輕松查看函數調用關系（誰調用這個函數、這個函數又調用了誰）、類繼承關系、符號定義和引用。
快速跳轉：Ctrl+Click?點擊任何函數或變量，即可立即跳轉到它的定義處。
上下文窗口：一個懸浮窗，顯示當前函數或變量的定義，無需離開當前位置。
符號窗口：列出所有文件中的函數、變量、類等符號，方便快速導航。

2. 高效的源代碼編輯

語法高亮：支持多種語言，并可高度自定義。
智能自動完成：基于其強大的符號數據庫，提供的自動補全建議非常準確和智能。
代碼片段：支持創建和使用代碼片段模板，提高編碼效率。
代碼格式重排：可以按照自定義風格格式化代碼。

3. 項目范圍的理解

快速構建整個項目（而非單個文件）的符號數據庫。
提供項目范圍的搜索、查找引用、重構等功能，讓你輕松理清大型項目中海量文件之間的復雜關系。

4. 語言支持

主要專注于C和C++，并對它們提供了最深層次的支持。同時也支持?Java、C#、Python、PHP、HTML?等多種語言，但其核心優勢仍在 C/C++。

5. 其他特點

運行速度快：相較于許多重型 IDE，它非常輕快敏捷。
Windows 原生應用：界面符合 Windows 操作習慣。
高度可定制：快捷鍵、配色方案、命令等都可以自定義。

拓展：條件編譯

? ? ? ? 條件編譯的內容在作者之前的博客：https://blog.csdn.net/2401_89119815/article/details/147345616?fromshare=blogdetail&sharetype=blogdetail&sharerId=147345616&sharerefer=PC&sharesource=2401_89119815&sharefrom=from_link

? ? ? ? 已經闡述過了。因為條件編譯實際上再項目中應用十分廣泛因此作者在這里再說一遍

? ? ? ? 在之前的源碼中stl_tree.h中有這么一段，實際含義是這樣的

#ifndef __SGI_STL_SET_H       // 如果沒有定義 __SGI_STL_SET_H 宏
#define __SGI_STL_SET_H       // 定義 __SGI_STL_SET_H 宏#include <tree.h>             // 包含樹結構相關的頭文件
#include <stl_set.h>          // 包含STL集合實現#ifdef __STL_USE_NAMESPACES   // 如果定義了 __STL_USE_NAMESPACES 宏
using __STD::set;             // 使用命名空間 __STD 中的 set 類
#endif /* __STL_USE_NAMESPACES */ // 結束條件編譯#endif /* __SGI_STL_SET_H */  // 結束頭文件保護

? ? ? ? 基本語法為：

#ifdef 宏名// 如果宏已定義，編譯此部分代碼
#else// 如果宏未定義，編譯此部分代碼
#endif#ifndef 宏名// 如果宏未定義，編譯此部分代碼
#else// 如果宏已定義，編譯此部分代碼
#endif#if 表達式// 如果表達式為真，編譯此部分代碼
#elif 另一個表達式// 如果前一個表達式為假且此表達式為真，編譯此部分
#else// 如果所有表達式都為假，編譯此部分
#endif

? ? ? ? 再舉一個實際案例：

#include <iostream>
using namespace std;// 示例1：平臺特定代碼
#ifdef _WIN32#define PLATFORM "Windows"
#elif __linux__#define PLATFORM "Linux"
#elif __APPLE__#define PLATFORM "macOS"
#else#define PLATFORM "Unknown"
#endif// 示例2：調試模式
#define DEBUG_MODE 1// 示例3：功能開關
#define FEATURE_A_ENABLED
#define FEATURE_B_LEVEL 3int main() {// 平臺檢測cout << "Running on: " << PLATFORM << endl;// 調試代碼#if DEBUG_MODEcout << "Debug information: Program started" << endl;#endif// 功能開關#ifdef FEATURE_A_ENABLEDcout << "Feature A is enabled" << endl;#endif// 帶值的條件編譯#if FEATURE_B_LEVEL > 2cout << "Feature B at high level (" << FEATURE_B_LEVEL << ")" << endl;#elif FEATURE_B_LEVEL > 0cout << "Feature B at basic level (" << FEATURE_B_LEVEL << ")" << endl;#elsecout << "Feature B is disabled" << endl;#endif// 頭文件保護模擬#ifndef MY_HEADER_GUARD#define MY_HEADER_GUARDcout << "This would be included only once" << endl;#endif// 嘗試再次包含相同內容（不會執行）#ifndef MY_HEADER_GUARDcout << "This won't be printed" << endl;#endifreturn 0;
}

? ? ? ?

? ? ? ? 實際應用

? ? ? ? 跨平臺開發

#ifdef _WIN32#include <windows.h>
#else#include <unistd.h>
#endif

? ? ? ? 調試與版本發布

#ifdef DEBUG#define LOG(msg) std::cout << "DEBUG: " << msg << std::endl
#else#define LOG(msg)
#endif

? ? ? ? 功能定制

#if VERSION == 2// 版本2特有功能#include "new_features.h"
#elif VERSION == 1// 版本1功能#include "basic_features.h"
#endif

? ? ? ? 防止重復編譯頭文件

// myheader.h
#ifndef MYHEADER_H
#define MYHEADER_H// 頭文件內容#endif

????????

? ? ? ? 本期關于map/set的源碼剖析和模擬實現功能到這里就結束了，喜歡請點個贊謝謝。

封面圖自取：