一、封裝思路
在 STL 中 map set 的底層就是封裝了一棵紅黑樹。
其中連接紅黑樹和容器的是迭代器，map set 暴露出的接口都不是自己寫的，而是紅黑樹寫的，外部接口封裝紅黑樹接口。
所以寫出紅黑樹為 map set 寫的接口，再在上層的 map set 類中包裝一下即可。
之前的紅黑樹就是單純的在樹上插入節點，為了實現 map set 就需要紅黑樹再實現迭代器。
二、紅黑樹細節實現
1、迭代器
本質就是封裝了一個節點，用于遍歷紅黑樹找到目標值。
（1）整體設計
與鏈表迭代器一樣，需要迭代器重載解引用和箭頭，所以模板依舊設計成：
template<class T, class Ref, class Ptr>
來適應 const 迭代器的復用。
（2）重載解引用
// 解引用迭代器是取數據
Ref operator*()
{return _node->_data;
}（3）重載箭頭
// 取數據的地址
Ptr operator->()
{return &(_node->_data);
}（4）重載不等于
bool operator!=(const Self& it)
{return _node != it._node;
}（5）后置++
// 1.如果右子樹存在，訪問右子樹的最左節點
// 2.如果右子樹不存在，如果我是父親的左，那就訪問父親
// 如果我是父親的右，表示父親也完了，向上判斷，直到是左孩子
Self& operator++()
{if (_node->_right){Node* cur = _node->_right;while (cur->_left)cur = cur->_left;_node = cur;}else{Node* cur = _node;while (cur->_parent && cur == cur->_parent->_right)cur = cur->_parent;_node = cur->_parent;}return *this;
}（6）后置--
// 1.如果左子樹存在，返回左子樹的最右節點
// 2.如果左子樹不存在，如果是父親的右孩子，返回根
// 如果是父親的左孩子，向上找直到是右孩子
Self& operator--()
{Node* cur = _node;if (_node->_left){while (cur->_right)cur = cur->_right;_node = cur;}else{while (cur && cur == cur->_parent->_left)cur = cur->_parent;_node = cur->_parent;}return *this;
}2、紅黑樹
到這里迭代器已經實現完畢，要把裸的迭代器實現出不同的形式花樣就是在紅黑樹這一層實現的。
（1）整體設計
從這里開始就要考慮如何把容器與紅黑樹相關聯。
難點一
?map 是 kv 模型，set 是 key 模型，類型都不一樣，怎么防止在一份紅黑樹代碼中參數的沖突？
庫里面的解決辦法是：template<class K, class T>
這里的 T 是存放的數據類型，即 map 是 pair<K, V>，set 是 K，這樣至少能傳入正確的參數了。
但是紅黑樹主要功能插入刪除的比較參數是 key，所以直接傳入的參數 T 用于比較（map 的 pair<K, V> 比較邏輯是 K 大的就返回，K 不大就 V 大的返回，顯然不符合比較邏輯）是不行的，我們需要都是比較 K，所以還需要一個內部類提取 map set 的 key 值。
所以最終的紅黑樹模板參數如下：
template<class K, class T, class KeyOfT>
K 是?key 的類型，T 是容器存儲的數據類型，KeyOfT 是分別在 map 和 set 中實現的內部類分別提取其中的 key 用于插入刪除函數的比較。
難點二
迭代器分為 const 迭代器和非 const 迭代器，所以在紅黑樹中也要封裝。
不用寫兩份迭代器代碼，之前迭代器的模板參數就起作用了：其實 const 和非 const 的區別就是指向的內容不能修改，就是解引用和箭頭的重載返回值不能被修改，利用模板實例化就能解決問題：
// 紅黑樹中定義兩個迭代器，模板參數不同即可
typedef __RBTreeIterator<T, T&, T*> Iterator;
typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;（2）構造析構
由于已經要和容器接軌了，所以要考慮深淺拷貝問題，這里封裝了常見的默認成員函數
RBTree() = default; // 由于已經寫了拷貝構造，強制生成默認構造// 私有的概念只針對于類外，類內可以訪問其他對象的私有成員
RBTree(const RBTree<K, T, KeyOfT>& tree)
{_root = Copy(tree._root);
}RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> tree)
{swap(_root, tree._root);
}~RBTree()
{Destroy(_root);_root = nullptr;
}（3）迭代器封裝
在迭代器類中已經處理了迭代器的使用邏輯，在紅黑樹這一層就是封裝容器的迭代器常用功能
Iterator begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return leftMin;
}Iterator end()
{return Iterator(nullptr);
}ConstIterator begin() const
{Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return leftMin;
}ConstIterator end() const
{return ConstIterator(nullptr);
}注意 const 迭代器函數后面需要加 const 構成函數重載。
（4）insert 改造
和庫里面保持一致，插入函數返回插入元素的迭代器和是否插入成功的 pair
為了比較的正確性要利用內部類 KeyOfT 來取出數據的 key 進行比較
pair<Iterator, bool> insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return {_root, true};}Node* cur = _root;Node* parent = cur;KeyOfT kot;// 1.像搜索二叉樹一樣插入節點curwhile (cur){if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}elsereturn {cur, false};}cur = new Node(data);Node* newnode = cur;if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;// 新插入是紅色，如果父親是黑色就沒事while (parent && parent->_col == RED){Node* g = parent->_parent;Node* uncle = parent == g->_left ? g->_right : g->_left;// 情況一：叔叔存在且為紅，u p 變黑，g變紅，向上if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;g->_col = RED;cur = g;parent = cur->_parent;}// 情況二：叔叔存在且為黑或叔叔不存在else{// u parent cur 的位置決定的是左右單旋雙旋// gB pB// pR u -> cR gR// cR uif (cur == parent->_left && parent == g->_left){RotateR(g);parent->_col = BLACK;g->_col = RED;}// gB gB cB// pR u -> cR u -> pR gR// cR pR uelse if (cur == parent->_right && parent == g->_left){RotateL(parent);RotateR(g);cur->_col = BLACK;g->_col = RED;}// gB pB// u pR -> gR cR// cR u else if (cur == parent->_right && parent == g->_right){RotateL(g);g->_col = RED;parent->_col = BLACK;}// gB gB cB// u pR -> u cR -> gR pR// cR pR u else if (cur == parent->_left && parent == g->_right){RotateR(parent);RotateL(g);cur->_col = BLACK;g->_col = RED;}elseassert(false);break;}}_root->_col = BLACK;return {newnode, true};
}三、容器細節實現
首先容器的實現共性是 map set 上層確確實實只傳入 <K, V> 和 <K>，是底層紅黑樹為了適應容器，底層紅黑樹的實例化是 <K, pair<K, V>, KeyOfT> 和?<K, K, KeyOfT>
其次兩者都要實現各自的 KeyOfT 內部類來告訴底層紅黑樹要怎么取到 key 值。
最后容器封裝底層紅黑樹寫好的迭代器代碼交給外部使用。
1、set 實現
template<class K>
class set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}iterator find(const K& key){return _t.find(key);}pair<iterator, bool> insert(const K& key){return _t.insert(key);}
private:RBTree<K, const K, SetKeyOfT> _t;
};2、map 實現
template<class K, class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}iterator find(const K& key){return _t.find(key);}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;}
private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};值得一提的是 map 還要重載 []，其實現邏輯已經在博客map和set-CSDN博客解釋過。
搜索引擎Agent)
