網(wǎng)站關鍵詞優(yōu)化方法西安優(yōu)化外
好了，上次我們了解完了AVL平衡樹和紅黑樹之后，我們就可以去了解關于map與set的底層實現(xiàn)原理了。
全局觀STL的操作：
我們先來看看STL中是如何利用紅黑樹進行對map與set的實現(xiàn)的？
從上面我們可以看到：
為了實現(xiàn)一顆紅黑樹，即可map又可set，即即可key結構，也可K,V結構，這取決于 第二個模板參數(shù)你傳什么？能不能只傳Value，不傳Key（傳第二個模板參數(shù)，不傳第一個模板參數(shù)？）
不能，因為當find接口時，對于set沒問題，set的value就是Key，但對于map不能。
所以為了統(tǒng)一適配，要傳兩個模板參數(shù)。但實際上，set是一個模板參數(shù)，map是兩個模板參數(shù)。
（ps：Key與pair中的Key是同一類型）
set的模擬實現(xiàn)（set是一個模板參數(shù)）
typedef Key key_type;
typedef Key value_type;?
那么有人又會想：它會不會存在樹被修改的問題？
答案：不存在的，因為你并不會動這棵樹，你只是動map與set而已，接觸不了樹的那層。
看上面的圖：K是為了讓find接口更加好搞，T是為了決定樹的結點里面存什么。
好了，上面了解庫的大概實現(xiàn)的方式后，現(xiàn)在我們來實現(xiàn)一下：
自己模擬：
ps：這里我們會采用set與map兩者之間的對比差異結合來實現(xiàn)（即同一部分的放在一起，并不會像之前那樣set與map分開來實現(xiàn)。）
紅黑樹創(chuàng)建結點和顏色管理
紅黑樹部分跟上一篇的差不多，只不過這里改了_kv類型改了一下：
我們上一篇的是以pair<K,V> _kv,而現(xiàn)在改成了T _data
這里可以認為在紅黑樹這一層它走了一個泛型，以前實現(xiàn)紅黑樹都是確定的是pair<K,V>類型，而現(xiàn)在是不確定的，而是通過一個模板來接受它的類型。
這里的本意就是想要通過模板來使紅黑樹實例化出來兩份：一份是<K,K>,一份是<K,pair<K,V>>
enum Color
{BLACK,RED
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Color _col;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){ }};構建其成員變量：
ps：有些模板參數(shù)后面會講，可暫時先不用管。
紅黑樹部分：
template<class K,class T,class KeyOFT>
class RBTree
{typedef RBTreeNode<T> Node;public:
private:Node* _root = nullptr;
};?set部分
namespace bai
{template<class K>class My_set{private:RBTree<K, K, SetKeyOFT> _t;};
}map部分
namespace bai
{template<class K, class V>class My_map{private:RBTree<K, pair<const K, V>, MapKeyOFT> _t;};
}插入部分
1.這里如果按照上一篇的方式之間比較的話，它就會行不通，為什么呢？
因為insert部分的比較：通過上面我們知道對于set，可以直接比較，它的結構本質上<K,K>第二個模板是K，而map的話，它的結構是<K,pair<K,V>>,第二個模板參數(shù)是pair類型，它并不可以像我們之前那樣直接比較?？赡苡腥藭?#xff1a;那為什么不可以直接用K模板比較？注意：我們這里比較的是值，這個K是個類型，而這比較需要拿的是對象，對象不確定，是K還是pair？所以不可以。
那么，我們該怎么去解決這個問題呢？這里就使用到了仿函數(shù)了。
之前我們說過，仿函數(shù)是可以做到像函數(shù)一樣的。
這里我們可以直接在各自那里：實現(xiàn)一個仿函數(shù)。通過模板還傳進去樹的結構那里。
使用仿函數(shù)比較
set部分
struct SetKeyOFT{const K& operator()(const K& key){return key;}};bool insert(const K& key){return _t.Insert(key);}map部分
struct MapKeyOFT{const K& operator()(const pair<K, V>& kv){return kv.first;}};//后面我們再實現(xiàn)V& operator[](const K& key);bool insert(const pair<K, V>& kv){return _t.Insert(kv);}
完了之后，就可以直接利用仿函數(shù)的使用方法，通過仿函數(shù)比較insert部分里面的比較內容了。
由于代碼太多了，這里只展現(xiàn)出部分的：（展示如何利用上仿函數(shù)就行）其余的代碼跟上一篇的紅黑樹插入部分已經(jīng)有了。
bool Insert(const T& data)
{……………………………………………………KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){……………………}else if (kot(cur->_data) > kot(data)){……………………}
………………
………………
}說明：為什么在紅黑樹中不通過KeyOfT實現(xiàn)比較？
這樣設計是為了保持KeyOfT的純粹性。如果讓KeyOfT負責比較，就會失去其核心價值。我們要思考的是：KeyOfT存在的真正意義是什么？是為了讓樹結構本身更清晰。
我們的做法是：使用者只需關注比較邏輯，無需理會KeyOfT的具體實現(xiàn)。因此將兩者分離，只需傳入比較接口即可實現(xiàn)功能。
迭代器部分：
紅黑樹部分：
迭代器的構造（加上構造+拷貝構造）
template<class T,class Ptr,class Ref>
struct TreeIterator
{typedef RBTreeNode<T> Node;typedef TreeIterator<T,Ptr,Ref> Self;typedef TreeIterator<T, T*, T&> Iterator;Node* _node;TreeIterator(Node*node):_node(node){ }TreeIterator(const Iterator&it):_node(it._node){ }};operator*
Ref operator*()
{return _node->_data;
}
operator->?
Ptr operator->(){return &_node->_data;}operator!=
bool operator!=(const Self&s){return _node != s._node;}operator==
bool operator==(const Self& s) const{return _node == s._node;}operator++
講解：
1.首先，我們來看一下上面的圖來使我們更加清楚了解它是如何進行++的？
2.我們先來看一下它的總思路：（結合著上圖一起看）
1）右不為空，訪問右樹的最左結點（即最小結點）。
2）右為空，下一個要訪問的孩子是父親左的那個祖先。
Self& operator++(){//右樹不為空，找右樹的最左結點（即最小結點）if (_node->_right){Node* subleft = _node->_right;while (subleft->_left){subleft = subleft->_left;}_node = subleft;}//右樹為空，else{Node* cur = _node;Node* parent = cur->_parent;//找孩子是父親左的那個祖先節(jié)點，就是下一個要訪問的節(jié)點while (parent && cur==parent->_right){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}?operator--
1.減減的思路和加加的思路相反：
1）左不為空，訪問左樹的最右結點（即最大結點）。
2）左為空，下一個要訪問的孩子是父親右的那個祖先。
Self& operator--(){if (_node->_left){Node* subright = _node->_right;while (subright->_right){subright = subright->_right;}_node = subright;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur==parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}好了，迭代器接口的類已經(jīng)寫完了，現(xiàn)在我們利用上寫的迭代器函數(shù)，進行對begin(),end()等實現(xiàn)上去。
begin()和end（）函數(shù)
首先，我們先來看一下庫里面是如何進行實現(xiàn)的；
庫那利用了一個哨兵節(jié)點。
除了它的開銷：在旋轉操作中，為了維護父節(jié)點而付出了一定的代價。而且，當在最左邊或最右邊插入或刪除節(jié)點時，也需要進行相應的維護和修改
在這里，我們就不像它那樣實現(xiàn)了，復雜，難！
1.我們先對迭代器進行封裝，還是用上我們的模板：
2.begin()函數(shù)的解釋：因為底層實現(xiàn)是紅黑樹，即平衡二叉搜索樹，所以，我們開始的結點（中序遍歷）是左子樹最左的那個值，所以，要進行查找遍歷到左數(shù)最小的值，最后返回。
3.end（）函數(shù)的解釋：直接返回迭代器為nullptr時。為什么呢？返回nullptr構造的迭代器，當遍歷完紅黑樹時，迭代器到達這個位置就說明遍歷完了有效的元素，和STL容器的迭代器使用習慣一致，方便搭配基于范圍for循環(huán)等遍歷方式：for(auto it=rbtree.begin();it!=end();it++).
4.下面還有就是實現(xiàn)了const迭代器。
template<class K,class T,class KeyOFT>
class RBTree
{typedef RBTreeNode<T> Node;public:typedef TreeIterator<T,T*,T&> iterator;iterator begin(){Node* LeftMin = _root;while (LeftMin && LeftMin->_left){LeftMin = LeftMin->_left;}return iterator(LeftMin);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* LeftMin = _root;while (LeftMin && LeftMin->_left){LeftMin = LeftMin->_left;}return const_iterator(LeftMin);}const_iterator end()const {return const_iterator(nullptr);}
private:Node* _root = nullptr;
};好了，紅黑樹里的迭代器封裝我們就基本實現(xiàn)完成了，那么現(xiàn)在，就開始對set與map進行對迭代器模板的使用。
set迭代器
同樣，我們來進行實現(xiàn)兩個迭代器，分別是普通迭代器和const迭代器。
但是，由上面一開始的分析我們也知道，set中是不可被修改的，否則就不是搜索樹了。
所以普通迭代器底層對紅黑樹的迭代器封裝時，也是使用了const迭代器進行封裝的，從而做到不可修改。
1.注意：為什么iterator begin()后面不加const不會通過編譯，會報錯？
因為：不加const的話，那么_t就是普通迭代器的_t，普通迭代器的t就只能調用普通的begin,普通的begin()，end(),返回的就是普通的iterator,普通的iterator能不能跟這個匹配？不能。
那么，我們只提供const版本的迭代器，有沒有價值呢？
答案是有點：反正它是不能被修改的，const對象可以調用const（平移），普通對象也是可以調用const的（縮小）。因為我們說過，對象可以平移或者縮小，但是不可以擴大。
比如：我們使用時：bai::set<int>::iterator it=_t.begin();
iterator可以轉化為const_itrerator，那要單獨寫一個構造進行轉化，但是typedef里的iterator還是要寫的，因為像我們平常的話，更多習慣用的還是iterator而不是const_iterator，對吧。
2.注意補充一點：類模板沒有實例化，編譯器不會去找。
內嵌類型：內部類，typedef
要加typename，相當于給編譯器吃一顆定心丸，告知編譯器它是合法的。（具體的可以去看一下關于進階模板的文章）
//有些代碼已經(jīng)省略
namespace bai
{template<class K>class My_set{public:typedef typename RBTree<K,K,SetKeyOFT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOFT>::const_iterator const_iterator;iterator begin()const{return _t.begin();}iterator end()const{return _t.end();}private:RBTree<K, K, SetKeyOFT> _t;};
}map迭代器
1.我們的map可以修改：即不可以修改K，可以修改Value，那么我們能不能繼續(xù)像剛才set那樣，，底層都是const_iterator？來保證K不變。
答：不可以，因為set只有一個，讓K不可被修改，若map也用的話，它不僅僅K不可改，連V也不可修改了。
那么，我們該怎么去做到不改變K，但是改變V呢？
我們可以在pair內部進行操作，即在pair<const K,V>,這樣的話pair可以被修改，但是K不可以修改了，達成我們的目的！
其他的做法，跟我們set的差不多！
namespace bai
{template<class K, class V>class My_map{public:typedef typename RBTree<K, pair<const K,V>, MapKeyOFT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOFT>::const_iterator 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();}private:RBTree<K, pair<const K, V>, MapKeyOFT> _t;};
}隨之我們的迭代器部分的完善，我們的insert部分也要進一步改善的！
完善insert部分
insert部分返回值要改成pair<iterator,bool>
紅黑樹部分
講解
1.為什么要用newnode保存一下cur呢？不能直接用cur？
答：因為紅黑樹插入的過程中會有變色，cur的grandfather，cur可能往上走，不一定是新插入的結點，所以要保存一下新節(jié)點
pair<iterator, bool> insert(const T& data){KeyOFT kot;if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root),true);}Node* cur = _root;Node* parent = nullptr;//Node* newnode = cur;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);//寫錯1Node* newnode = cur;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;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//繼續(xù)向上更新cur = grandfather;parent = cur->_parent;}else//不存在 或者uncle為黑 旋轉+變色{if (cur == parent->_left){// g// p//cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED; }else //cur==parnet->right{// g// p// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = BLACK;grandfather->_col = RED;}break;} }else //(parent == grandfather->_right){Node* uncle = grandfather->_left;//Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續(xù)向上更新cur = grandfather;parent = cur->_parent;}else //(uncle不存在時)旋轉+變色{// g // p// c if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}// g // p// celse{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;//parent->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode),true);}你把樹里的改了，那么set與map的也要跟著改。但是這時候就會set的insert出現(xiàn)問題：
現(xiàn)在我們來看一下改變的代碼：
set部分
pair<iterator, bool> insert(const K& key)
{return _t.insert(key);
}set沒有pair，而pair又是全局的。
會出現(xiàn)迭代器問題：
返回值的pair<iterator,bool>是RBTree::const_iterator
而你return的 _t.Insert(key)是pair<RBTree::iterator,bool>
那么，我們在insert() const? 行不行？
不能，_t是const，Insert也是const,那么必須去調用const insert,那就不能夠修改樹的結構了，所以不能！
再來回顧，make_pair會根據(jù)它的類型自己去推，在類里面直接用iterator,本質也是const_iterator.
這里的做法是：
拿一個普通迭代器去構造const迭代器！
按理說，迭代器不需要寫拷貝構造，因為編譯器默認寫：淺拷貝。
template<class T,class Ptr,class Ref>
struct TreeIterator
{typedef RBTreeNode<T> Node;typedef TreeIterator<T,Ptr,Ref> Self;typedef TreeIterator<T, T*, T&> Iterator;Node* _node;TreeIterator(Node*node):_node(node){ }TreeIterator(const Iterator&it):_node(it._node){ }
}但這個函數(shù)也不完全是拷貝構造，因為它的返回值不是Self 。
Self與Iterator的區(qū)別：Self就是這個迭代器，但Iterator就不一定了。
可能聽到這里有點疑惑，別急，讓我們再來捋捋思路：
_t.insert是一個普通樹的對象，
pair<typename RBTree<K,K,SetkeyofT>::iterator,bool> ret=t.insert()返回的是一個普通的迭代器，而set這層的iterator是const迭代器，傳不過去，所以我們的做法是：
單獨用一個pair對象普通樹的迭代器的對象去接受，接受了以后，再用這個東西去構造，傳參，first傳的是普通迭代器，
那么，普通迭代器為什么可以初始化const迭代器？
因為const迭代器中支持了一個構造，這兩個pair是同一個類模板，并不是同類型的。
當這個類被實例化成const迭代器時，這個函數(shù)是一個構造，支持普通迭代器構造const迭代器，為什么？
1.因為我實例化出const迭代器，我自己就是const迭代器，但是這個參數(shù)是iterator，特點是不管你是普通迭代器還是const迭代器，都是普通迭代器，因為這參數(shù)傳的是?
typedef TreeIterator<T, T*, T&> Iterator;并不受Ref，Ptr影響。
2.當這個類被實例化成普通迭代器，這個函數(shù)就是一個拷貝構造（普通構造普通）。
map部分
pair<iterator,bool> insert(const pair<K, V>& kv){return _t.insert(kv);}也是跟上面的一樣理解。
map的operator[]部分
V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}1.這是一個關聯(lián)式容器：
- ?make_pair(key, V())??：創(chuàng)建一個 ?pair??對象，?first??是傳入的 ?key??，?second??是默認構造的 ?V??類型對象（如果 ?V??是自定義類型，需有默認構造函數(shù) ）。
- ?insert(make_pair(key, V()))??：調用下方自定義的 ?insert??函數(shù)，嘗試插入pair??。
?insert??函數(shù)返回一個 ?pair??，其中 ?first??是指向插入位置（或已存在元素位置 ）的迭代器，?second??是 ?bool??類型，?true??表示插入成功（之前無該 ?key??），?false??表示已存在（未插入新元素 ）。
- ?return ret.first->second??：不管插入是否成功，通過迭代器 ?ret.first??訪問 ?pair??的 ?second??（即對應 ?key??的 ?value??）并返回其引用，
大整體部分就這樣了。
好的，本次分享就到處結束了，希望我們一起進步！
最后，到了本次雞湯環(huán)節(jié)：
?下面圖片與大家共勉！
