?
嘿，各位技術潮人！好久不見甚是想念。生活就像一場奇妙冒險，而編程就是那把超酷的萬能鑰匙。此刻，陽光灑在鍵盤上，靈感在指尖跳躍，讓我們拋開一切束縛，給平淡日子加點料，注入滿滿的
passion。準備好和我一起沖進代碼的奇幻宇宙了嗎？Let’s go！
我的博客：yuanManGan
我的專欄：C++入門小館 C言雅韻集 數據結構漫游記 閑言碎語小記坊
進階數據結構 走進Linux的世界 題山采玉 領略算法真諦
用紅黑樹實現封裝map和set
實現步驟：
- 實現紅黑樹
- 封裝 map 和 set 框架解決KeyOfT
- iterator
- const_iterator
- key不支持修改的問題
- operator[ ]
1.實現紅黑樹
上集我們已經實現了一個普通的紅黑樹 進階數據結構：紅黑樹，
2.封裝 map 和 set 框架解決KeyOfT
查看stl源碼借鑒了解
發現實現 set 和 map 都包含了一個 tree 頭文件，我們那篇博客實現的 key-value 的紅黑樹，那我們是不是要實現兩個紅黑樹一個是 key 的一個 key-value 的呢？
不急我們看看源碼：
template<typename _Key, typename _Val, typename _KeyOfValue,typename _Compare, typename _Alloc = allocator<_Val> >class _Rb_tree{}
我們湊湊這模板，這怎么又有key又有value那它怎么實現的set , set 不是不要value嗎？
我來解釋一下吧：
- 可能寫這個代碼的程序員寫的不太規范，這個地方的Val代表的不是我們之前寫代碼的value。
- 而是比如我們set傳入的key，map傳入的key_value,代表的是這一類，而不是單純的value
- 我們就這樣形成了模板，本質上編譯器還是寫了兩份代碼，但增加了復用，減少了我們自己寫。
那又有人問了，那我們不是只要一個模板參數就夠了嗎，為什么前面還得加個key呢？
- 我們實現 find 等功能的時候需要使用到 key，所以不能偷懶
更改我們的紅黑樹
我們寫就寫的規范一點，我們將 V 替換為 T
//原本
////////////////////////////////////////////////////////////////
template <class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _parent;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr) // 按聲明順序放在_col之前, _col(RED){}
};
template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public://...
private:Node* _root = nullptr;
};
////////////////////////////////////////////////////////////////
//修改后
template <class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _parent;RBTreeNode<V>* _left;RBTreeNode<V>* _right;Colour _col;RBTreeNode(T& data): _data(data), _parent(nullptr), _left(nullptr), _right(nullptr) // 按聲明順序放在_col之前, _col(RED){}
};
template <class K, class T>
class RBTree
{typedef RBTreeNode<K, T> Node;
public://...
private:Node* _root = nullptr;
};
我們在修改 Insert 這個函數的時候就遇到的問題，我們怎么比較插入節點與原節點的大小呢？
- 我們可以引入一個模板參數 KeyOfT 分別在 set和 map頭文件里面重載 ( ) 實現比較邏輯，如果是set就直接返回 key ，map就返回kv中的 first。
//set.h
template<class K>
class set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public://...
private:RBTree<K, K, SetKeyOfT> _t;
};
//map.h
template<class K, class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public://...
private:RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
insert
KeyOfT kot;
bool Insert(const T& data)
{//插入//空樹if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else {return false;}}cur = new Node(data);cur->_col = RED;if (kot(data) > kot(parent->_data)){//是p的右子樹parent->_right = cur;}else{//是p的左子樹parent->_left = cur;}cur->_parent = parent;//變色while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;//u存在且為紅if (uncle && uncle->_col == RED){//變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續往上處理cur = grandfather;parent = cur->_parent;}else{//u存在但為黑if (cur == parent->_left){//c在左// g p // p u ---> c g// c uRotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//c在右// g RotateL(p) g RotateR(g) c// p u -----------> c u --------> p g// c p u RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//u存在且為紅if (uncle && uncle->_col == RED){//變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續往上處理cur = grandfather;parent = cur->_parent;}else{//u存在但為黑if (cur == parent->_right){//c在右// g p // u p ---> g c// c uRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//c在z左// g RotateR(p) g RotateL(g) c// u p -----------> u c --------> g p// c p u RotateR(parent);RotateL)
)
