---

前言

我們知道map和set的底層都是用紅黑樹實現的，但是set和map的結構不一樣，set只有一個參數K，而map有兩個參數K/V，難道set和map是利用倆份紅黑樹來實現的嗎？從設計者的角度是不可能這樣復現的，這樣實現的話兩個容器有著大量的重復代碼，只是參數的個數不同就要使用兩份紅黑樹復現是完全不符合設計規則的，那么紅黑樹做了怎樣的處理使得傳入參數的不同來復現這兩個容器呢？下面我們就一起來進行學習！！

一、紅黑樹的設計

1.1 紅黑樹存儲節點的設計

既然map和set的參數不同，那么紅黑樹就要統一的對它們的參數進行處理，當為pair<K，V>類型時復現map，為K類型時復現set。我們先來看看stl庫中是如何來進行設計的：

通過上圖可以看到，map 傳給紅黑樹的key_type是Key，value_type是pair<Key, T>；而 set 傳給紅黑樹的key_type和value_type都是Key。紅黑樹節點中存儲的數據就是value_type類型的數據。如果傳給value_type的是pair<Key, T>，那么就會實例化出 map；而傳給value_type的是Key，就會實例化出 set。

那么我們下面的問題就轉化成了，如何去提取出value_type類型的數據？

在插入節點的時候我們是需要根據二叉搜索樹的規則來調整的，set的Value為K直接提取出來對比即可，而map中的Vaule為pair<K, V>，我們只需提取出K來對比即可，stl庫中對pair的排序規則不符合并我們的要求，所以我們得自己設計一個仿函數來返回對應的數據！！

紅黑樹節點存儲設計如下：

#pragma onceenum Colour
{RED,BLACK,
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};// 仿函數
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public: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;}}// ......return true;}private:Node* _root = nullptr;
};

1.2 紅黑樹的迭代器

我們知道紅黑樹本質上也是一顆二叉搜索樹，所以通過中序遍歷能得到一個升序的序列。

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){return _node != s._node;}Self& operator++(){ // 當節點的右子樹存在時, 一直往下沿左走 走到盡頭了 證明左子樹走完了 該走右子樹了 右子樹也重復該步驟if (_node->_right){Node* subL = _node->_right;while (subL->_left){subL = subL->_left;}_node = subL;}else{Node* cur = _node;Node* parent = cur->_parent;// 右子樹走完了  我們應該返回到該右子樹的父節點的祖先了while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node->_left){Node* subR = _node->_left;while (subR->_right){subR = subR->_right;}_node = subR;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}
};template<class K, class T, class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, T&, T*> iterator;
public:// begin()為樹的最左節點iterator begin(){// 注: 需要避免_root為nullptrNode* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}private:Node* _root = nullptr;
}

1.3 map的設計

#pragma once
#include "RBTree.h"namespace curry
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;   // 提取出kv的key值}};public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<K, V>, MapKeyOfT> _t;  // 底層調用RBTree進行插入操作};
};

1.4 set的設計

#pragma once
#include "RBTree.h"namespace curry
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};
};

通過上述map和set的設計我們可以發現，實際它們的迭代器與功能操作都是由紅黑樹提供的！！

1.5關于map與set的const_iterator設計

我們先來看看stl庫中對它的設計：

由上圖可知，實際上在stl庫中map/set的普通迭代器都設計成了const迭代器，那么const迭代器是如何實現的呢？

它是利用普通迭代器構造出來的。self與iterator是不一樣的，我們的普通迭代器是self設計出來的，而const迭代器需要普通迭代器的構造，那么我們就需要顯式定義出普通迭代器的類型進行構造。