上一章節我們實現了紅黑樹，這一章節我們就用紅黑樹封裝來實現一個我們自己的map和set

1. 源碼及框架分析

// 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 容器共性

• 底層數據結構：
  set?和?map?均通過?rb_tree（紅黑樹）實現，確保操作（插入、刪除、查找）的時間復雜度為?O(log n)。

• 成員變量：
  二者內部均包含一個?rep_type t（即?rb_tree?實例），所有操作委托給紅黑樹完成。

1.2?關鍵差異：元素類型與鍵提取方式

set?的實現

template <class Key, class Compare, class Alloc>
class set {
private:typedef rb_tree<Key, Key, identity<Key>, Compare, Alloc> rep_type;rep_type t; // 紅黑樹存儲 Key 本身
};

• 元素類型：value_type = Key（鍵與值相同）。

• 鍵提取器：identity<value_type>
  直接返回元素自身作為鍵（value?→?key）。

map?的實現

template <class Key, class T, class Compare, class Alloc>
class map {
private:typedef rb_tree<Key, pair<const Key, T>, select1st<pair<const Key, T>>, Compare, Alloc> rep_type;rep_type t; // 紅黑樹存儲 pair<const Key, T>
};

• 元素類型：value_type = pair<const Key, T>（鍵值對，鍵不可修改）。

• 鍵提取器：select1st<value_type>
  從?pair?中提取第一個元素作為鍵（pair.first?→?key）。

1.3?紅黑樹（rb_tree）核心設計

節點結構

// 基類：管理樹結構指針和顏色
struct __rb_tree_node_base {color_type color;      // 節點顏色（紅/黑）base_ptr parent;       // 父節點base_ptr left;         // 左子節點base_ptr right;        // 右子節點
};// 派生類：存儲實際數據
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base {Value value_field;     // 節點存儲的值（set: Key, map: pair<const Key, T>）
};

樹類模板

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>
class rb_tree {
protected:link_type header;      // 哨兵節點（父節點指向根，左/右指向最小/最大節點）size_type node_count;  // 節點數量（O(1) 獲取 size）public:// 核心操作pair<iterator, bool> insert_unique(const Value& x); // 插入唯一鍵size_type erase(const Key& x);                      // 按鍵刪除iterator find(const Key& x);                        // 按鍵查找
};

• 模板參數：

  • Key：鍵類型（用于查找/刪除）。

  • Value：節點實際存儲類型（set?為?Key，map?為?pair<const Key, T>）。

  • KeyOfValue：從?Value?提取鍵的函數對象（set?用?identity，map?用?select1st）。

  • Compare：鍵比較函數（默認?less<Key>）。

1.4?操作邏輯

• 插入：
  insert_unique(const value_type& x)
  使用?KeyOfValue?提取鍵，通過?Compare?比較鍵值，在樹中查找合適位置插入。若鍵已存在，返回失敗。

• 刪除：
  erase(const key_type& x)
  直接使用傳入的鍵?x?在樹中查找并刪除節點。

• 查找：
  find(const key_type& x)
  按鍵值在樹中進行二分查找。

1.5?設計優勢

1. 復用性：
   通過模板參數?KeyOfValue?和?Value?的差異，rb_tree?同時支持?set、map、multiset、multimap。

2. 效率：

   • 紅黑樹的自平衡特性保證操作復雜度為?O(log n)。

   • header?哨兵節點優化了?begin()/end()?操作（直接訪問最小/最大節點）。

   • node_count?成員使?size()?操作時間復雜度為?O(1)。

3. 類型安全：
   map?的鍵被設計為?const Key，防止用戶修改鍵導致樹結構破壞。

紅黑樹模板參數設計分析

紅黑樹的泛型實現機制

通過源碼分析可以看到，rb_tree采用了一個巧妙的泛型設計思想。其核心在于：

• 通過第二個模板參數Value來控制紅黑樹節點_rb_tree_node中存儲的數據類型
• 這使得同一套紅黑樹實現可以同時支持兩種不同的使用場景：
  • 純鍵值搜索場景（如set）
  • 鍵值對搜索場景（如map）

set和map的不同實例化方式

具體實現上有以下關鍵區別：

1. set的實現：

   • 實例化rb_tree時第二個模板參數直接傳入key
   • 例如：rb_tree<Key, Key>
   • 節點中存儲的就是鍵值本身

2. map的實現：

   • 實例化rb_tree時第二個模板參數傳入std::pair<const key, T>
   • 例如：rb_tree<Key, std::pair<const Key, Value>>
   • 節點中存儲的是鍵值對

模板參數命名解析

源碼中存在以下命名慣例需要注意：

• T代表的是節點存儲的實際數據類型（即Value）
• value_type在源碼中表示紅黑樹節點存儲的真實數據類型
  • 這與日常使用中的key/value概念不同
  • 在set中，value_type就是Key
  • 在map中，value_type是std::pair<const Key, T>

雙模板參數的必要性

關于為何需要兩個模板參數（Key和Value）：

1. Value參數的作用：

   • 控制節點實際存儲的數據類型
   • 決定紅黑樹是作為key容器還是key/value容器

2. Key參數的作用：

   • 作為find()、erase()等操作的參數類型
   • 對于set：
     • Key和Value相同
     • 如：find(const Key&)
   • 對于map：
     • Key和Value不同
     • 如：find(const Key&)（雖然存儲的是pair，但查找時只用Key）

源碼命名風格問題

值得注意的命名不一致問題：

• set模板參數使用Key命名
• map模板參數使用Key和T命名
• rb_tree模板參數又使用Key和Value命名
• 這種不一致的命名風格反映了即使是經驗豐富的開發者也可能存在編碼規范不統一的問題

2. 模擬實現map和set

2.1 實現出復用紅黑樹的框架，并支持insert

框架設計思路

參考STL源碼框架結構，我們將map和set的實現復用了之前已完成實現的紅黑樹（RBTree）數據結構。這種復用設計遵循了STL的設計理念，通過模板和仿函數實現代碼復用，避免了重復造輪子。

模板參數調整

相比原始實現，我們對模板參數進行了以下優化調整：

• 使用K表示鍵類型參數
• 使用V表示值類型參數
• 紅黑樹內部數據類型統一使用T表示模板參數

關鍵問題與解決方案

類型比較問題： 當RBTree實現為泛型模板后，編譯器無法確定模板參數T具體是簡單的鍵類型K（set的情況），還是鍵值對pair<K, V>（map的情況）。這導致在insert操作內部進行節點比較時產生歧義：

// 問題示例
if (cur->_data < new_node->_data)  // 當T是pair時，這會比較key和value

解決方案： 我們引入了提取鍵值的仿函數機制：

1. 在map和set層分別實現：
   • MapKeyOfT：從pair<K,V>中提取key
   • SetKeyOfT：從K中直接返回key（保持原樣）
2. 將這些仿函數作為模板參數KeyOfT傳給RBTree
3. RBTree內部通過KeyOfT仿函數統一獲取比較鍵值

具體實現示例

// map層的鍵提取仿函數
struct MapKeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;}
};// set層的鍵提取仿函數
struct SetKeyOfT {const K& operator()(const K& key) {return key;}
};// RBTree中的比較邏輯調整
template<class T, class KeyOfT>
bool RBTree<T, KeyOfT>::Insert(const T& data) {KeyOfT kot;  // 實例化鍵提取仿函數// ...if (kot(cur->_data) < kot(data)) {  // 統一使用kot提取鍵值進行比較// 右子樹處理}else if (kot(data) < kot(cur->_data)) {// 左子樹處理}else {// 鍵值相等處理}// ...
}

應用場景說明

這種設計使得我們的RBTree可以：

1. 作為set的底層容器時，直接比較鍵值
2. 作為map的底層容器時，僅比較pair中的鍵部分
3. 保持統一的插入接口，同時正確處理兩種場景的鍵比較邏輯

通過這種仿函數和模板的組合設計，我們實現了map和set對紅黑樹代碼的高度復用，同時保證了類型安全和比較邏輯的正確性。

具體代碼如下：

// Mymap.h
#pragma once#include "RBTree.h"namespace Ro
{template<class K, class V>class Mymap{struct MapKeyOfT{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, V, MapKeyOfT> _t;};
}// Myset.h
#pragma once#include "RBTree.h"namespace Ro
{template<class K>class Myset{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};
}// RBTree.h
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)          // 新節點默認紅色（符合紅黑樹插入規則）{}T _data;          RBTreeNode<T>* _left; // 左子節點RBTreeNode<T>* _right;// 右子節點RBTreeNode<T>* _parent; // 父節點Colour _col;             // 節點顏色
};template<class K, class T, class KeyOfT>
class RBTree
{using Node = RBTreeNode<T>;
public:bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}KeyOfT kt;Node* parent = nullptr;Node* cur = _root;while (cur){if (kt(cur->_data) < kt(data)){parent = cur;cur = cur->_right;}else if (kt(cur->_data) > kt(data)){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);if (kt(parent->_data) < kt(data)){parent->_right = cur;}else{parent->_left = cur;}//鏈接父親節點cur->_parent = parent;// 父節點為紅色，需要顏色修正while (parent && parent->_col == RED){Node* grandfather = parent->_parent; // 祖父節點必存在（因父為紅，不可能是根）// 分父節點是祖父的左/右孩子兩種情況處理if (grandfather->_left == parent){//		g(B)//	p(R)	   u(分情況)Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) // 情況1：變色處理{//		g(B)//	p(R)	   u（存在且為紅色）//c(R)// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // 情況2，3：旋轉 + 變色{if (parent->_left == cur) // 右單旋 + 變色{//		g(B)//	p(R)	   u（不存在或為黑色）//c(R)RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else // 左右雙旋 + 變色{//		g(B)//	p(R)	   u（不存在或為黑色）//    c(R)RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//此時旋轉之后的子樹根節點為parent或cur，但都變為黑色，更新到黑結束break;}}else{//		      g(B)//	u(分情況)		 p(R)Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED) // 情況1：變色處理{//			  g(B)//	u(存在且為紅色)		p(R)//							c(R)// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // 情況2，3：旋轉 + 變色{if (parent->_right == cur) // 左單旋 + 變色{//			  g(B)//	u(不存在或為黑色)		p(R)//							c(R)RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else // 右左雙旋 + 變色{//			  g(R)//	u(不存在或為黑色)		p(R)//					c(R)RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//此時旋轉之后的子樹根節點為parent或cur，但都變為黑色，更新到黑結束break;}}}// 暴力處理：無論是否處理到根節點，都直接把根節點變為黑色（符合根節點為黑色規則）_root->_col = BLACK;return true;}// 右單旋void RotateR(Node* parent){Node* subL = parent->_left;// parent的左子節點（旋轉后的新根）Node* subLR = subL->_right;// subL的右子節點（可能為空）// 旋轉節點subL->_right = parent;parent->_left = subLR;// 維護父指針Node* pParent = parent->_parent;parent->_parent = subL;if (subLR) //若subLR存在,更新其父指針,避免堆空指針解引用{subLR->_parent = parent;}subL->_parent = pParent;// 維護parent的父節點if (parent == _root) // parent為根節點的情況{_root = subL;}else // parent是一棵局部子樹的情況{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}}}// 左單旋void RotateL(Node* parent){Node* subR = parent->_right;// parent的右子節點（旋轉后的新根）Node* subRL = subR->_left;// subR的左子節點（可能為空）// 旋轉節點subR->_left = parent;parent->_right = subRL;// 維護父指針Node* pParent = parent->_parent;parent->_parent = subR;if (subRL) //若subRL存在,更新其父指針,避免堆空指針解引用{subRL->_parent = parent;}subR->_parent = pParent;// 維護parent的父節點if (parent == _root) // parent為根節點的情況{_root = subR;}else // parent是一棵局部子樹的情況{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}}}Node* Find(const K& key){KeyOfT kt;Node* cur = _root;while (cur){if (kt(cur->_data) < key){cur = cur->_right;}else if (kt(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
private:int _Size(Node* root){if (root == nullptr) return 0;int leftSize = _Size(root->_left);int rightSize = _Size(root->_right);return leftSize + rightSize + 1;}int _Height(Node* root){if (root == nullptr) return 0;int leftHigh = _Height(root->_left);int rightHigh = _Height(root->_right);return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;}private:Node* _root = nullptr;
};

2.2 支持iterator的實現

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

紅黑樹迭代器源碼分析（SGI STL v3.0）

1.?迭代器繼承結構

struct __rb_tree_base_iterator { /* 基礎迭代器 */ };
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator { /* 具體迭代器 */ };

• 基礎迭代器：處理樹節點指針移動的核心邏輯

• 具體迭代器：添加類型定義和運算符重載

2.?關鍵成員變量

// 基礎迭代器中
base_ptr node;  // __rb_tree_node_base* 類型

• 核心指針：指向當前紅黑樹節點

• 節點類型：__rb_tree_node_base?僅包含樹結構指針（父/左/右）和顏色信息

3.?核心移動操作：increment()（++操作）

void increment() {if (node->right != 0) {         // 情況1：存在右子樹node = node->right;         // 先移動到右子節點while (node->left != 0)     // 再向左走到盡頭node = node->left;} else {                        // 情況2：無右子樹base_ptr y = node->parent;while (node == y->right) {  // 回溯直到不再是右子節點node = y;y = y->parent;}if (node->right != y)       // 特殊邊界檢測（防止回環）node = y;}
}

移動邏輯：

1. 有右子樹：右子樹的最左節點（中序后繼）

2. 無右子樹：回溯到第一個左祖先節點

3. 邊界處理：node->right != y?防止指向 header 節點時形成環

4.?核心移動操作：decrement()（--操作）

void decrement() {if (node->color == __rb_tree_red &&  // 情況1：header節點特殊處理node->parent->parent == node) {  // header特征：自環結構node = node->right;              // 指向最大值節點} else if (node->left != 0) {        // 情況2：存在左子樹base_ptr y = node->left;while (y->right != 0)            // 左子樹的最右節點y = y->right;node = y;} else {                             // 情況3：無左子樹base_ptr y = node->parent;while (node == y->left) {        // 回溯直到不再是左子節點node = y;y = y->parent;}node = y;}
}

移動邏輯：

1. header 節點：直接跳轉到最大值節點（通過?node->right）

2. 有左子樹：左子樹的最右節點（中序前驅）

3. 無左子樹：回溯到第一個右祖先節點

5.?具體迭代器關鍵實現

reference operator*() const { return link_type(node)->value_field;  // 實際值訪問
}pointer operator->() const { return &(operator*());               // 指針訪問
}self& operator++() { increment();  // 調用基礎迭代器的移動邏輯return *this;
}

類型轉換技巧：

return link_type(node)->value_field;

• link_type?=?__rb_tree_node<Value>*

• 安全轉換：將?__rb_tree_node_base*?轉為具體節點類型

• 值訪問：通過?value_field?獲取實際存儲數據

6.?迭代器特征設計

typedef Value value_type;
typedef Ref reference;   // 如 Value&
typedef Ptr pointer;     // 如 Value*

模板參數化：

• 三參數設計：<Value, Ref, Ptr>?支持常量/非常量迭代器

  • 普通迭代器：__rb_tree_iterator<Value, Value&, Value*>

  • 常量迭代器：__rb_tree_iterator<Value, const Value&, const Value*>

7.?邊界檢測關鍵細節

header 節點識別：

node->color == __rb_tree_red && 
node->parent->parent == node

• 顏色特征：header 節點固定為紅色

• 結構特征：形成?header->parent->parent == header?的自環

遞增邊界保護：

if (node->right != y)  // 防止指向自身node = y;

• 確保從最大值節點遞增時正確跳轉到 header（end迭代器）

iterator實現思路分析

基本實現框架

iterator的實現采用與list類似的思路，通過一個類封裝結點的指針，并重載運算符模擬指針行為。核心實現包括：

1. 封裝一個指向樹結點的指針成員變量
2. 重載operator*和operator->用于訪問數據
3. 重載operator++和operator--實現遍歷
4. 重載比較運算符實現迭代器比較

中序遍歷實現關鍵點

map和set的迭代器遵循中序遍歷順序(左子樹->根結點->右子樹)，begin()返回樹的最左結點(中序第一個結點)。

operator++實現邏輯

1. 右子樹非空情況：

   • 當前結點訪問完畢后，下一個要訪問的是右子樹的中序第一個結點
   • 實現方式：找到右子樹的最左結點

   if(node->right) {node = node->right;while(node->left) node = node->left;
   }
   

2. 右子樹為空情況：

   • 需要向上查找祖先結點
   • 如果當前結點是父結點的左孩子，則下一個訪問父結點
   • 如果當前結點是父結點的右孩子，繼續向上查找直到找到某結點是其父結點的左孩子

   else {Node* parent = node->parent;while(parent && node == parent->right) {node = parent;parent = parent->parent;}node = parent;
   }
   

operator--實現邏輯

operator--與operator++邏輯相反，按照右子樹->根結點->左子樹的順序：

1. 若左子樹非空，則找到左子樹的最右結點
2. 若左子樹為空，則向上查找直到找到某結點是其父結點的右孩子

end()處理方案

1. 簡單方案：使用nullptr作為end()標志

   • 當遍歷到最后結點時(如圖中50)，繼續++會返回nullptr
   • --begin()同樣返回nullptr
   • 需要特殊處理--end()使其指向樹的最右結點

2. STL方案：使用哨兵頭結點

   • 增加一個專用頭結點，其parent指向根結點
   • 左指針指向樹的最小結點，右指針指向樹的最大結點
   • 根結點的parent也指向該頭結點
   • 這種設計使--end()可以直接指向最大結點

類型約束實現

1. set迭代器：

   template<class K>
   class set {RBTree<K, const K, SetKeyOfT> _t;// const K - 保證set元素的不可修改性
   };
   

2. map迭代器：

   template<class K, class V> 
   class map {RBTree<K, pair<const K, V>, MapKeyOfT> _t;// pair<const K, V> - 鍵值對，鍵為const保證不可修改
   };
   

• set存儲單個元素(const K)，保證元素不可修改
• map存儲鍵值對(pair<const K, V>)，保證鍵不可修改

完整實現注意事項

1. 邊界條件處理：begin()/end()/++/--的邊界情況
2. const迭代器支持
3. 迭代器失效問題處理
4. 與容器其他操作的兼容性

我們實現Mymap和Myset迭代器時，使用nullptr作為end()，如果仿照STL中使用頭節點的話，我們自己封裝的紅黑樹就需要改動，旋轉之后還需要維護，對于我們來說改動比較多，成本比較高，所以這里我們不去仿照STL搞一個頭節點

關于這兩種方法實現的優缺點：

1. 我的實現：nullptr?作為?end()?標志

// 查找示例
Node* Find(const K& key) {Node* cur = _root;while (cur) { // 依賴 nullptr 判斷邊界if (key < cur->_data) cur = cur->_left;else if (key > cur->_data) cur = cur->_right;else return cur;}return nullptr; // end() 等價于 nullptr
}

??優點

1. 內存精簡：

   • 無額外內存開銷（節省一個頭節點）

   • 空樹時僅需?_root = nullptr

2. 實現簡單：

   • 插入/刪除邏輯無需維護額外指針

   • 迭代器只需存儲當前節點指針

3. 遍歷效率：

   • 普通遍歷操作與哨兵方案性能相當

??缺點

1. 邊界處理復雜：

   // 迭代器遞減操作需特殊處理根節點
   void decrement() {if (node == _root) { // 需要特殊處理根節點邊界}// ...其他邏輯
   }

2. 無法直接訪問極值：

   • 獲取?begin()（最小節點）需 O(log n) 遍歷

   • 沒有緩存最大/最小節點，每次需重新查找

3. 迭代器失效風險：

   • end()?迭代器 (nullptr) 無法進行?--?操作

   • 無法實現標準要求的?--end()?獲取最大值

2.?STL 哨兵頭結點方案

// STL 頭結點結構示例
struct __rb_tree_node_base {__rb_tree_node_base* parent;__rb_tree_node_base* left;   // 指向最小節點__rb_tree_node_base* right;  // 指向最大節點
};class rb_tree {
protected:link_type header; // 哨兵頭結點// ...
};

??優點

1. 極值訪問 O(1)：

   • begin() = header->left

   • end() = header

   • rbegin() = header->right

2. 邊界處理統一：

   // 迭代器遞增無需特殊判斷
   void increment() {if (node->right) {// 正常右子樹處理} else {// 統一回溯邏輯（含header處理）}
   }

3. 符合STL標準：

   • 支持?--end()?獲取最大值

   • 滿足雙向迭代器所有要求

4. 空樹處理優雅：

   // 空樹時形成自環
   header->parent = nullptr;
   header->left = header;
   header->right = header;

??缺點

1. 內存開銷：

   • 額外 3 個指針 + 顏色字段的內存占用

   • 小型容器相對開銷較大

2. 實現復雜度：

   • 插入/刪除需維護header指針：

   // 插入新節點后需更新極值
   if (new_node < header->left) header->left = new_node;
   if (new_node > header->right)header->right = new_node;

3. 指針維護成本：

   • 旋轉操作需額外更新header關聯

由于nullptr為end()時，在end()--時會有風險，所以我們在實現時需要考慮這種特殊情況。

代碼實現和梳理：

代碼基礎架構：

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;RBTreeIterator(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;}
};

關鍵點分析

1. 模板參數設計：

   • T：節點數據類型（如?pair<K, V>?或直接?K）

   • Ref：引用類型（T&?或?const T&）

   • Ptr：指針類型（T*?或?const T*）

   • 作用：通過模板參數實現常量/非常量迭代器的統一實現

2. 節點訪問操作：

   Ref operator*() { return _node->_data; }  // 返回數據引用
   Ptr operator->() { return &_node->_data; } // 返回數據指針

   • 提供標準迭代器訪問接口

   • 支持?*iter?和?iter->member?語法

3. 迭代器比較：

   bool operator!=(const Self& s) const { return _node != s._node; }
   bool operator==(const Self& s) const { return _node == s._node; }

   • 直接比較節點指針地址

   • 簡單高效，符合迭代器等價性要求

operator++ 實現

執行過程分析

情況1：當前節點有右子樹（直接后繼存在）

if (_node->_right) 
{// 步驟1：進入右子樹Node* minright = _node->_right;// 步驟2：找到右子樹的最左節點while (minright->_left){minright = minright->_left;}// 步驟3：更新當前節點_node = minright;
}

1. 進入右子樹：從當前節點移動到其右子節點

2. 向左遍歷到底：在右子樹中持續向左遍歷，直到最左葉子節點

3. 更新迭代器：將迭代器指向找到的最左節點

圖示過程：

      [A]         // 當前節點\[B]      // 進入右子樹/ \[C]   [D]   // 在右子樹中/ \         // 向左遍歷[E]  [F]       // 找到最左節點 [E]

情況2：當前節點無右子樹（回溯尋找祖先）

else 
{Node* cur = _node;Node* parent = cur->_parent;// 向上回溯直到找到左祖先while (parent && parent->_left != cur){cur = parent;parent = cur->_parent;}_node = parent; // 更新為左祖先或nullptr
}

1. 初始化指針：

   • cur?= 當前節點

   • parent?= 當前節點的父節點

2. 回溯循環：

   • 當?cur?是?parent?的右子節點時繼續回溯

   • 移動：cur?→?parent,?parent?→ 祖父節點

3. 終止條件：

   • 找到?cur?是?parent?左子節點的位置

   • 或回溯到根節點后（parent == nullptr）

4. 更新迭代器：

   • 指向找到的左祖先節點

   • 若無滿足條件的祖先，設為?nullptr?(表示?end())

圖示過程：

      [G]        // 最終目標祖先/[P]         // cur是G的左子節點\[C]        // 當前節點為右子節點\[A]      // 需要回溯的節點路徑\[B]    // 當前節點

1. 從?[B]?開始回溯

2. [B]?是?[A]?的右子 → 繼續

3. [A]?是?[C]?的右子 → 繼續

4. [C]?是?[P]?的右子 → 繼續

5. [P]?是?[G]?的左子 → 停止，返回?[G]

具體代碼：

Self& operator++()
{if (_node->_right) // 右子樹不為空，找右子樹中序第一個節點，也就是右子樹最小節點{Node* minright = _node->_right;while (minright->_left){minright = minright->_left;}_node = minright;}else // 右子樹為空，找孩子是父親左的那個祖先節點{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left != cur){cur = parent;parent = cur->_parent;}_node = parent; // 更新為左祖先或nullptr}return *this;
}

operator-- 的實現

執行過程分析

情況1：end() 迭代器 (_node == nullptr)

if (_node == nullptr)
{Node* maxright = _root;// 使用 _root 開始遍歷while (maxright->_right) // 向右遍歷到底{maxright = maxright->_right;}_node = maxright; // 指向最大節點
}

1. 特殊處理：當迭代器處于?end()?(nullptr) 時

2. 查找最大值：從根節點開始持續向右遍歷

3. 更新節點：指向找到的最右節點（樹的最大值）

情況2：左子樹存在

else if (_node->_left)
{Node* maxright = _node->_left;while (maxright->_right) // 在左子樹中向右遍歷{maxright = maxright->_right;}_node = maxright; // 指向左子樹的最右節點
}

1. 進入左子樹：移動到當前節點的左子節點

2. 向右遍歷：在左子樹中持續向右，直到最右節點

3. 更新節點：指向找到的最右節點

示例：

  [5]        // 當前節點/
[3]        // 進入左子樹\[4]     // 向右遍歷至最右節點

情況3：左子樹不存在（回溯尋找右祖先）

else
{Node* cur = _node;Node* parent = cur->_parent;// 回溯直到找到右祖先while (parent && parent->_right != cur){cur = parent;parent = cur->_parent;}_node = parent; // 更新為右祖先或nullptr
}

1. 初始化指針：

   • cur?= 當前節點

   • parent?= 當前節點的父節點

2. 回溯循環：

   • 當?cur?是?parent?的左子節點時繼續回溯

   • 移動：cur?→?parent,?parent?→ 祖父節點

3. 終止條件：

   • 找到?cur?是?parent?右子節點的位置

   • 或回溯到根節點后（parent == nullptr）

4. 更新迭代器：

   • 指向找到的右祖先節點

   • 若無滿足條件的祖先，設為?nullptr?(表示?rend())

示例：

    [P]        // 目標祖先（右祖先）\[C]       // cur是P的右子節點/[A]         // 當前節點起點/[B]           // 需要回溯的節點

1. 從?[B]?開始回溯

2. [B]?是?[A]?的左子 → 繼續

3. [A]?是?[C]?的左子 → 繼續

4. [C]?是?[P]?的右子 → 停止

5. 返回?[P]

具體代碼：

Node* _node;
Node* _root;// 處理end()--情況，需要從根節點開始遍歷最右節點RBTreeIterator(Node* node, Node* root):_node(node),_root(root)
{}
Self& operator--()
{if (_node == nullptr) // end()--，特殊情況處理{// 找到樹的最右節點，也就是最大節點Node* maxright = _root;// 使用 _root 開始遍歷while (maxright->_right){maxright = maxright->_right;}_node = maxright;}else if (_node->_left) // 左子樹不為空，找左子樹最右節點，也就是最大節點{Node* maxright = _node->_left;while (maxright->_right){maxright = maxright->_right;}_node = maxright;}else // 左子樹不為空，找孩子是父親右的那個祖先{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right != cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

復用紅黑樹迭代器實現Mymap和Myset的迭代器功能

template<class K, class T, class KeyOfT>
class RBTree
{using Node = RBTreeNode<T>;public:using Iterator = RBTreeIterator<T, T&, T*>;using ConstIterator = RBTreeIterator<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);}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return ConstIterator(cur, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}private:Node* _root = nullptr;
};

在上文中還有一點我們需要注意，也就是在類型約束實現中，在STL源碼中為了不讓外界修改我們key，使用了const來保證鍵的不可修改，那么這里我們也可以這么做

Mymap.h

namespace Ro
{template<class K, class V>class Mymap{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();}bool insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}

Myset.h

namespace Ro
{template<class K>class Myset{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();}bool insert(const K& key){return _t.Insert(key);}private:RBTree<K, const K, SetKeyOfT> _t;};
}

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

RBtree.h

pair<Iterator, bool> Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(_root, _root), true);return { Iterator(_root, _root), true }; // 隱式類型轉換}KeyOfT kt;Node* parent = nullptr;Node* cur = _root;while (cur){if (kt(cur->_data) < kt(data)){parent = cur;cur = cur->_right;}else if (kt(cur->_data) > kt(data)){parent = cur;cur = cur->_left;}else{return { Iterator(cur, _root), false }; //插入失敗返回當前已存在節點的迭代器}}cur = new Node(data);Node* newnode = cur; // 用于返回新插入的節點迭代器if (kt(parent->_data) < kt(data)){parent->_right = cur;}else{parent->_left = cur;}//鏈接父親節點cur->_parent = parent;// 父節點為紅色，需要顏色修正while (parent && parent->_col == RED){Node* grandfather = parent->_parent; // 祖父節點必存在（因父為紅，不可能是根）// 分父節點是祖父的左/右孩子兩種情況處理if (grandfather->_left == parent){//		g(B)//	p(R)	   u(分情況)Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) // 情況1：變色處理{//		g(B)//	p(R)	   u（存在且為紅色）//c(R)// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // 情況2，3：旋轉 + 變色{if (parent->_left == cur) // 右單旋 + 變色{//		g(B)//	p(R)	   u（不存在或為黑色）//c(R)RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else // 左右雙旋 + 變色{//		g(B)//	p(R)	   u（不存在或為黑色）//    c(R)RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//此時旋轉之后的子樹根節點為parent或cur，但都變為黑色，更新到黑結束break;}}else{//		      g(B)//	u(分情況)		 p(R)Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED) // 情況1：變色處理{//			  g(B)//	u(存在且為紅色)		p(R)//							c(R)// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // 情況2，3：旋轉 + 變色{if (parent->_right == cur) // 左單旋 + 變色{//			  g(B)//	u(不存在或為黑色)		p(R)//							c(R)RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else // 右左雙旋 + 變色{//			  g(R)//	u(不存在或為黑色)		p(R)//					c(R)RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//此時旋轉之后的子樹根節點為parent或cur，但都變為黑色，更新到黑結束break;}}}// 暴力處理：無論是否處理到根節點，都直接把根節點變為黑色（符合根節點為黑色規則）_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(newnode, _root), true);return { Iterator(newnode, _root), true }; // 隱式類型轉換
}

Mymap.h

pair<iterator, bool> insert(const pair<K, V>& kv)
{return _t.Insert(kv);
}

Myset.h

pair<iterator, bool> insert(const K& key)
{return _t.Insert(key);
}

map 下標運算符?operator[]?實現解析

通過鍵值?key?訪問對應的值?V，如果鍵不存在則自動插入新元素。

V& operator[](const K& key)
{// 嘗試插入鍵值對 (key, 默認值)pair<iterator, bool> ret = insert({ key, V() });  // 返回鍵對應值的引用return ret.first->second;
}

執行流程詳解：

1. 插入操作：

   pair<iterator, bool> ret = insert(key, V());

   • 嘗試插入鍵值對?(key, V())

   • V()?創建值類型的默認構造對象（如?int()?返回?0，string()?返回空串）

   • 返回值?ret?包含：

     • ret.first：指向元素的迭代器

     • ret.second：插入是否成功（true=新插入，false=已存在）

2. 返回值引用：

   return ret.first->second;

   • 通過迭代器獲取值的引用

   • 無論是否新插入，都返回鍵對應的值引用

關鍵特性：

1. 自動插入機制：

   • 當鍵不存在時：自動創建?(key, V())?并返回新值的引用

   • 當鍵存在時：直接返回已有值的引用

2. 返回值可修改：

   map<string, int> ages;
   ages["Alice"] = 25;  // 自動創建并賦值
   ages["Bob"]++;       // 自動創建0然后自增

3. 等價寫法：

   iterator it = ret.first;
   return it->second;

   • 等價于直接?ret.first->second

測試

測試Myset

void test_set()
{Ro::Myset<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){cout << e << " ";}cout << endl;
}

運行結果：

測試Mymap

void test_map()
{Ro::Mymap<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左邊" });dict.insert({ "right", "右邊" });dict["left"] = "左邊，剩余";dict["insert"] = "插入";dict["string"];for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;Ro::Mymap<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}

運行結果：

我們這里封裝紅黑樹實現的Mymap和Myset并不是很完善，這里只是簡單實現了一下，讓Mymap和Myset能夠實現一些正常的插入遍歷的操作，可以跑起來。例如刪除，拷貝，賦值等一些操作沒有實現，感興趣的可以自己去實現一下。

代碼：

RBTree.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)          // 新節點默認紅色（符合紅黑樹插入規則）{}T _data;          RBTreeNode<T>* _left; // 左子節點RBTreeNode<T>* _right;// 右子節點RBTreeNode<T>* _parent; // 父節點Colour _col;             // 節點顏色
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;// 處理end()--情況，需要從根節點開始遍歷最右節點RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Self& operator++(){if (_node->_right) // 右子樹不為空，找右子樹中序第一個節點，也就是右子樹最小節點{Node* minright = _node->_right;while (minright->_left){minright = minright->_left;}_node = minright;}else // 右子樹為空，找孩子是父親左的那個祖先節點{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left != cur){cur = parent;parent = cur->_parent;}_node = parent; // 更新為左祖先或nullptr}return *this;}Self& operator--(){if (_node == nullptr) // end()--，特殊情況處理{// 找到樹的最右節點，也就是最大節點Node* maxright = _root;// 使用 _root 開始遍歷while (maxright->_right){maxright = maxright->_right;}_node = maxright;}else if (_node->_left) // 左子樹不為空，找左子樹最右節點，也就是最大節點{Node* maxright = _node->_left;while (maxright->_right){maxright = maxright->_right;}_node = maxright;}else // 左子樹不為空，找孩子是父親右的那個祖先{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right != cur){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 KeyOfT>
class RBTree
{using Node = RBTreeNode<T>;
public:using Iterator = RBTreeIterator<T, T&, T*>;using ConstIterator = RBTreeIterator<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);}ConstIterator Begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return ConstIterator(cur, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}pair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(_root, _root), true);return { Iterator(_root, _root), true }; // 隱式類型轉換}KeyOfT kt;Node* parent = nullptr;Node* cur = _root;while (cur){if (kt(cur->_data) < kt(data)){parent = cur;cur = cur->_right;}else if (kt(cur->_data) > kt(data)){parent = cur;cur = cur->_left;}else{return { Iterator(cur, _root), false }; //插入失敗返回當前已存在節點的迭代器}}cur = new Node(data);Node* newnode = cur; // 用于返回新插入的節點迭代器if (kt(parent->_data) < kt(data)){parent->_right = cur;}else{parent->_left = cur;}//鏈接父親節點cur->_parent = parent;// 父節點為紅色，需要顏色修正while (parent && parent->_col == RED){Node* grandfather = parent->_parent; // 祖父節點必存在（因父為紅，不可能是根）// 分父節點是祖父的左/右孩子兩種情況處理if (grandfather->_left == parent){//		g(B)//	p(R)	   u(分情況)Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED) // 情況1：變色處理{//		g(B)//	p(R)	   u（存在且為紅色）//c(R)// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // 情況2，3：旋轉 + 變色{if (parent->_left == cur) // 右單旋 + 變色{//		g(B)//	p(R)	   u（不存在或為黑色）//c(R)RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else // 左右雙旋 + 變色{//		g(B)//	p(R)	   u（不存在或為黑色）//    c(R)RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//此時旋轉之后的子樹根節點為parent或cur，但都變為黑色，更新到黑結束break;}}else{//		      g(B)//	u(分情況)		 p(R)Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED) // 情況1：變色處理{//			  g(B)//	u(存在且為紅色)		p(R)//							c(R)// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // 情況2，3：旋轉 + 變色{if (parent->_right == cur) // 左單旋 + 變色{//			  g(B)//	u(不存在或為黑色)		p(R)//							c(R)RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else // 右左雙旋 + 變色{//			  g(R)//	u(不存在或為黑色)		p(R)//					c(R)RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//此時旋轉之后的子樹根節點為parent或cur，但都變為黑色，更新到黑結束break;}}}// 暴力處理：無論是否處理到根節點，都直接把根節點變為黑色（符合根節點為黑色規則）_root->_col = BLACK;//return pair<Iterator, bool>(Iterator(newnode, _root), true);return { Iterator(newnode, _root), true }; // 隱式類型轉換}// 右單旋void RotateR(Node* parent){Node* subL = parent->_left;// parent的左子節點（旋轉后的新根）Node* subLR = subL->_right;// subL的右子節點（可能為空）// 旋轉節點subL->_right = parent;parent->_left = subLR;// 維護父指針Node* pParent = parent->_parent;parent->_parent = subL;if (subLR) //若subLR存在,更新其父指針,避免堆空指針解引用{subLR->_parent = parent;}subL->_parent = pParent;// 維護parent的父節點if (parent == _root) // parent為根節點的情況{_root = subL;}else // parent是一棵局部子樹的情況{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}}}// 左單旋void RotateL(Node* parent){Node* subR = parent->_right;// parent的右子節點（旋轉后的新根）Node* subRL = subR->_left;// subR的左子節點（可能為空）// 旋轉節點subR->_left = parent;parent->_right = subRL;// 維護父指針Node* pParent = parent->_parent;parent->_parent = subR;if (subRL) //若subRL存在,更新其父指針,避免堆空指針解引用{subRL->_parent = parent;}subR->_parent = pParent;// 維護parent的父節點if (parent == _root) // parent為根節點的情況{_root = subR;}else // parent是一棵局部子樹的情況{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}}}Iterator Find(const K& key){KeyOfT kt;Node* cur = _root;while (cur){if (kt(cur->_data) < key){cur = cur->_right;}else if (kt(cur->_data) > key){cur = cur->_left;}else{return Iterator(cur, _root);}}return End();}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
private:int _Size(Node* root){if (root == nullptr) return 0;int leftSize = _Size(root->_left);int rightSize = _Size(root->_right);return leftSize + rightSize + 1;}int _Height(Node* root){if (root == nullptr) return 0;int leftHigh = _Height(root->_left);int rightHigh = _Height(root->_right);return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;}private:Node* _root = nullptr;
};

Mymap.h

#pragma once#include "RBTree.h"namespace Ro
{template<class K, class V>class Mymap{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){// 嘗試插入鍵值對 (key, 默認值)pair<iterator, bool> ret = insert({ key, V() });//iterator it = ret.first;//return it->second; //返回_data中鍵對應的值 // 等價寫法return ret.first->second; // 返回鍵對應值的引用}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}

Myset.h

#pragma once#include "RBTree.h"namespace Ro
{template<class K>class Myset{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);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};
}