C++使用一棵紅黑樹同時封裝出map和set實(shí)例代碼
一、封裝第一層：仿函數(shù)取結(jié)點(diǎn)中的key關(guān)鍵碼
1.在源碼里面，對于map和set的實(shí)現(xiàn)，底層是用同一棵紅黑樹封裝出來的，并不是用了兩棵紅黑樹，一個紅黑樹結(jié)點(diǎn)存key，一個紅黑樹結(jié)點(diǎn)存<key,value>的鍵值對，這樣的方式太不符合大佬的水準(zhǔn)了，實(shí)際上在紅黑樹底層中用了一個模板參數(shù)Value來代表紅黑樹結(jié)點(diǎn)存儲對象的類型，這個類型可能是pair鍵值對，也有可能是key類型。
所以在紅黑樹這一層中是不知道他自己的結(jié)點(diǎn)要存儲什么類型的對象的，故而需要模板參數(shù)來接收存儲對象的類型。
2.第一個問題，既然通過模板參數(shù)Value就能夠確定紅黑樹實(shí)現(xiàn)的是map還是set了，那我還需要模板參數(shù)Key干什么??？如果Value是鍵值對，那紅黑樹此時封裝的就是map，如果Value是key，那紅黑樹此時封裝的就是set。
對于紅黑樹的find()函數(shù)來講，我們在傳參的時候，find形參類型肯定得是key，此時就發(fā)揮出Key模板參數(shù)的作用了，因?yàn)樵诩t黑樹搜索的時候，依靠的還是關(guān)鍵碼進(jìn)行搜索，通過所傳關(guān)鍵碼和紅黑樹結(jié)點(diǎn)中的關(guān)鍵碼的大小關(guān)系，確定到紅黑樹中要搜索的某個結(jié)點(diǎn)。
template <class T>
struct RBTreeNode
{
T _data;// 我們不清楚紅黑樹結(jié)點(diǎn)里面存的是什么,可能是string，內(nèi)置類型，又或是鍵值對，取決于map和set里面存的是什么
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
enum color _col;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};
3.第二個問題，紅黑樹在插入結(jié)點(diǎn)的時候，不知道結(jié)點(diǎn)的類型，怎么拿出結(jié)點(diǎn)中的關(guān)鍵碼進(jìn)行比較插入??？如果是pair，我們應(yīng)該拿pair的first進(jìn)行比較，如果是key，我們直接比較即可，但在紅黑樹中該如何實(shí)現(xiàn)具體代碼呢？
此時仿函數(shù)就登場了，我們在map和set中都增加一個仿函數(shù)類，在給紅黑樹模板傳參的時候，除Key和T類型外（由于庫里面的Key和Value容易誤導(dǎo)大家，庫里的Value類型不是鍵值對中的value，而是紅黑樹結(jié)點(diǎn)存儲對象的類型，所以我們自己寫的紅黑樹第二個模板參數(shù)采用的命名是T），再增加一個用于獲取結(jié)點(diǎn)的關(guān)鍵碼的仿函數(shù)類型，也就是KeyOfT仿函數(shù)，這個仿函數(shù)實(shí)例化出的對象的作用就是幫助紅黑樹完成結(jié)點(diǎn)的插入，方便在插入內(nèi)部實(shí)現(xiàn)時進(jìn)行結(jié)點(diǎn)之間關(guān)鍵碼的比較。
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;//pair鍵值對的關(guān)鍵嗎是常量
};
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
private:
RBTree<K, K, SetKeyOfT> _t;
};
template <class K, class T, class KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;// T代表紅黑樹結(jié)點(diǎn)的存儲內(nèi)容的類型在擁有仿函數(shù)類型后，我們實(shí)例化一個仿函數(shù)對象，這個對象的功能就是幫助我們?nèi)〉媒Y(jié)點(diǎn)中的key關(guān)鍵碼，方便我們在紅黑樹Insert的實(shí)現(xiàn)里面進(jìn)行結(jié)點(diǎn)中關(guān)鍵碼的比較
二、封裝第二層：紅黑樹的普通迭代器
1.map和set的表層迭代器實(shí)現(xiàn)
1.下面是表層的map和set的迭代器實(shí)現(xiàn)，注意我們沒有實(shí)現(xiàn)map和set的const迭代器，在封裝第二層這里，僅僅只實(shí)現(xiàn)普通迭代器，第三層封裝的時候都會加上。
其實(shí)map和set的表層迭代器實(shí)現(xiàn)都很簡單，他們都是直接調(diào)用了底層紅黑樹的普通迭代器，所以難點(diǎn)其實(shí)是在紅黑樹的迭代器實(shí)現(xiàn)上。
2.對紅黑樹類型中的迭代器類型進(jìn)行typedef時，可以看到我們在typedef后面加了typename，typename的作用就是告訴編譯器后面的東西是一個類型，你先不要編譯他，等到模板實(shí)例化為真正類型后，你再去取他里面的內(nèi)嵌類型iterator。因?yàn)槲覀冎谰幾g器是不編譯模板的，編譯的是模板實(shí)例化之后的代碼，只有模板實(shí)例化之后，它里面的內(nèi)嵌類型我們才可以取到，所以如果你不加typename，有可能取的不是類型，因?yàn)殪o態(tài)變量或函數(shù)都是可以通過類+域訪問符進(jìn)行訪問的，所以如果你要取模板里面的類型，那就必須在模板前面加typename，告訴編譯器你取的是類型。
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
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();
}
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
2.底層紅黑樹中迭代器的實(shí)現(xiàn)
1.紅黑樹的迭代器和list的迭代器實(shí)際是一個道理，兩個容器的原生指針均無法滿足迭代器的要求，所以道理還是相同，我們進(jìn)行類封裝+運(yùn)算符重載，讓類實(shí)例化后的對象能夠滿足迭代器的要求，使其行為像指針一樣。
2.稍有難度的就是++和- -的運(yùn)算符重載的實(shí)現(xiàn)，但紅黑樹的三叉鏈結(jié)構(gòu)能幫助我們省不少事，迭代器移動的本質(zhì)就是讓__RBTreeIterator類里面的原生指針_node指向紅黑樹的中序位置的下一個結(jié)點(diǎn)。
其實(shí)大體就分兩種情況，對于1位置的it而言，由于他是begin，所以他的左邊一定為空，那就需要先判斷他的右邊是否為空，如果不為空，那就需要先訪問他的右子樹的最左結(jié)點(diǎn)，但在圖里面這個最左結(jié)點(diǎn)恰好就是6，我們將it對象里的_node指向更新到結(jié)點(diǎn)6處，然后等到it的右邊為空時，我們需要判斷當(dāng)前結(jié)點(diǎn)和他的父親結(jié)點(diǎn)的位置關(guān)系，如果此時結(jié)點(diǎn)是父親的左，那就說明父親結(jié)點(diǎn)還沒有訪問，因?yàn)槭亲笞訕?根 右子樹的訪問順序，那就得先訪問父親，然后再去訪問父親的右，如果此時結(jié)點(diǎn)是父親的右，那就說明父親結(jié)點(diǎn)已經(jīng)被訪問過了，所以需要回溯找祖先，就比如6訪問完了，6是1的右，那就回溯找1的父親，此時如果1是8的左，那就訪問8就好了，但如果1是8的右，那就還需要迭代向上找祖先，這就是++重載的大體思路，- -與其類似，這里不過多贅述。
3.紅黑樹結(jié)點(diǎn)里面存儲的是一個個自定義類型或者是內(nèi)置類型定義出來的變量，由這些變量混和組成了RBTreeNode結(jié)構(gòu)體，所以* 重載返回的是_data變量，→重載返回的是變量的地址，而++和- -返回的是* this，this指針其實(shí)就是結(jié)構(gòu)體指針，只不過this現(xiàn)在指向的是一個迭代器對象，那么* this實(shí)際返回的就是迭代器對象本身。
其實(shí)這些難度都不大，對我們的要求也不高，只要list迭代器理解的透徹，那紅黑樹的迭代器也很好理解，唯一不同的是紅黑樹迭代器內(nèi)部多加了一點(diǎn)算法而已。
template<class T>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
//右子樹 根 左子樹
if (_node->_left)
{
//找左子樹的最右結(jié)點(diǎn)，其實(shí)就是次大的結(jié)點(diǎn)
_node = _node->_left;
while (_node->_right)
{
_node = _node->_right;
}
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
//如果cur是parent的右，則直接讓_node指向到parent即可
_node = parent;
}
return *this;//返回迭代器對象
}
bool operator!=(const Self& it)const//const修飾表示在該成員函數(shù)內(nèi)部，不能修改對象的任何成員變量
{
return this->_node != it._node;
}
bool operator==(const Self& it)const//const對象和非const對象都可以調(diào)用
{
return this->_node == it._node;
}
};
三、封裝第三層：
1.set的迭代器（底層均為const_iterator）
1.從源碼的實(shí)現(xiàn)我們可以看到，set表層的兩個迭代器其實(shí)都是由紅黑樹的const迭代器typedef出來的，至于原因也很好理解，由于set的紅黑樹結(jié)點(diǎn)只存儲key關(guān)鍵碼，所以他是不允許被修改的，那其實(shí)就是迭代器指向的內(nèi)容不可被修改，所以我們用set迭代器時，嚴(yán)格來說應(yīng)該使用const_iterator，但就算你使用iterator，set也不會允許你修改iterator指向的內(nèi)容，因?yàn)榈讓佑玫氖羌t黑樹的const_iterator，所以第三步封裝這里，我們也給set的迭代器搞成像庫里面一樣。
2.結(jié)構(gòu)體SetKeyOfT放在哪無所謂，僅僅只是形式變了一下而已，當(dāng)你修改set表層的迭代器之后，你一編譯就會報錯，編譯器會產(chǎn)生一大堆的模板錯誤，其實(shí)是由于類型不兼容導(dǎo)致的。普通set對象調(diào)用begin()時，此時調(diào)用的是普通版本，那么底層調(diào)用的紅黑樹的begin()也調(diào)用的是普通版本，所以最終會返回一個普通迭代器，但表層set的Iterator實(shí)際又是紅黑樹的const迭代器類型，此時就會發(fā)生返回值和返回類型不兼容的問題，那應(yīng)該怎么辦呢？答案就是看源碼。
3.從源碼中可以看到set的begin和end都用了const版本，且僅僅只有const版本的begin和end，我們知道，普通對象會優(yōu)先調(diào)用普通版本的函數(shù)，但如果只有const版本的函數(shù)，那普通對象也會調(diào)用const版本的函數(shù)。由于const版本函數(shù)中只能讀，不能寫，所以普通對象會被const版本函數(shù)認(rèn)為是const對象，那在調(diào)用底層紅黑樹的begin和end時，就會自動調(diào)用紅黑樹中的const版本的begin和end，此時返回值和返回類型就兼容了，不會產(chǎn)生編譯錯誤。
4.這里在補(bǔ)充一點(diǎn)知識，一個函數(shù)是否需要實(shí)現(xiàn)const版本取決于這個函數(shù)的功能是什么，如果這個函數(shù)對于容器來說僅僅是只讀的功能，那就實(shí)現(xiàn)const版本，如果可以寫可以讀那就實(shí)現(xiàn)兩個版本，如果僅僅是只寫，那就實(shí)現(xiàn)非const版本。
template <class K>
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
template <class K>
class set
{
public:
//set表層的普通迭代器底層用的依舊是const_iterator，就是不允許對set的迭代器指向內(nèi)容進(jìn)行修改
typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator const_iterator;
iterator begin()//const
{
return _t.begin();
//普通對象調(diào)用的begin()返回的是普通迭代器，而set上層要求返回的都是const迭代器，發(fā)生類型不兼容問題
//庫是怎么解決的呢？
//
//set的begin和end沒有提供兩個版本，僅僅只提供了const版本，強(qiáng)制性要求set的普通對象和const對象底層都去調(diào)用
//紅黑樹const版本的begin()和end()
//注意：如果是普通對象發(fā)生調(diào)用const函數(shù)，那么在const函數(shù)內(nèi)部，普通對象也會被當(dāng)作const對象進(jìn)行處理。
// 所以底層調(diào)用的紅黑樹的begin，自動就是const版本的begin()
}
iterator end()//const
{
return _t.end();
}
5.從下面紅黑樹和紅黑樹結(jié)點(diǎn)兩個類的模板參數(shù)其實(shí)就可以看到list的const迭代器的影子，我們用Ref和Ptr作為紅黑樹迭代器的模板參數(shù)，和list迭代器非常相似，這樣在迭代器內(nèi)部就可以直接用參數(shù)Ref和Ptr作為→和*重載的返回值，完成const迭代器的要求，返回常引用和const修飾的指針內(nèi)容。
template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;// node里面存的是鍵值對或key類型變量
typedef __RBTreeIterator<T, Ref, Ptr> Self;//迭代器
Ref operator*()
{
return _node->_data;// 如果是set就是key，如果是map就是鍵值對,這里返回引用
}
Ptr operator->()
{
return &_node->_data;
}
}
template <class K, class T, class KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;// T代表紅黑樹結(jié)點(diǎn)的存儲內(nèi)容的類型
typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()//給普通對象調(diào)用
{
Node* left = _root;
while (left && left->_left)// 這棵樹有可能是空樹，若不為空樹找到左樹最小結(jié)點(diǎn)
{
left = left->_left;
}
return iterator(left);// 不能瞎用引用啊，這里的迭代器對象出了begin()作用域就銷毀了，引用就出大事了！
}
const_iterator begin()const//給const對象調(diào)用
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return const_iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
2.map的const_iterator（鍵值對中的Key類型寫死為const修飾的類型，則定義出來的都是常量，不能被修改）
1.map的迭代器是需要實(shí)現(xiàn)兩個版本的，因?yàn)閙ap容器中的數(shù)據(jù)是可以被修改的，如果你想修改map中的數(shù)據(jù)那就用iterator，如果你想修改map中的數(shù)據(jù)那就用const_iterator。
如果是const_iterator，那解引用或者→返回的就是鍵值對的常引用或const修飾的指向鍵值對的結(jié)構(gòu)體指針，那么此時鍵值對的key和value都是不可以修改的。
如果是iterator，解引用或者→返回的就是鍵值對的普通引用或無const修飾的指向鍵值對的結(jié)構(gòu)體指針，但此時鍵值對的key依舊不可以被修改，只能對鍵值對中的value進(jìn)行修改，因?yàn)樵诮o紅黑樹模板傳參的時候，鍵值對中的K我們寫死了，用的就是const修飾的K，那么在鍵值對結(jié)構(gòu)體中K類型定義出來的變量或?qū)ο缶褪浅Ａ?，因?yàn)閏onst修飾的任何變量都可以稱為常量，所以即使你用的是iterator，他所指向的鍵值對的key依舊是不能修改的，我們只能修改他的value。
2.對于const關(guān)鍵字，const修飾的變量我們稱之為常量，const修飾的對象我們稱之為常對象，常量不能被修改，常對象的成員變量也不能被修改。
template <class K, class V>
class map
{
public:
// 1.取未實(shí)例化類模板里面的類型時，無論是內(nèi)部類還是內(nèi)嵌類型，都需要加typename，告訴編譯器類模板后面的東西是類型
// 因?yàn)轭惸０謇锩孢€有可能是靜態(tài)成員，靜態(tài)成員也是可以通過類名+域訪問符進(jìn)行訪問的，編譯器無法確定是類型還是靜態(tài)成員
// 2.圖紙里面怎么能直接取東西呢？肯定是需要對這樣的情況進(jìn)行特殊處理的
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K,V>>::iterator iterator;
// 編譯器不會編譯模板，編譯的都是模板實(shí)例化之后的代碼，所以iterator是靜態(tài)成員還是內(nèi)嵌類型，編譯器都確定不了。
//typename就是先告訴一下編譯器，這里是類型，先不要取這個類型，等到模板實(shí)例化好之后你再去取這個類型。
//圖紙里面有水果，你先不要去拿這個水果，等到按照圖紙實(shí)例化為蘋果樹之后，你再取這個蘋果
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;
//map的迭代器需要提供兩個版本
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<K,V>> _t;
};
3.map的[ ]運(yùn)算符重載
1.如果我們自己封裝的map也想像庫里面的[ ]重載函數(shù)一樣，能夠同時具有增查改的功能，我們該怎么實(shí)現(xiàn)呢？那就需要從紅黑樹的insert來入手，此時的insert返回的就不再是ture或false了，返回的應(yīng)該是一個鍵值對，這個鍵值對的first是指向結(jié)點(diǎn)的迭代器，second是bool值。
2.[ ]在進(jìn)行鍵值對的insert時，value使用的是其類型的無參構(gòu)造，如果是內(nèi)置類型則值為0或nullptr這些，如果是自定義類型則調(diào)用其默認(rèn)的構(gòu)造函數(shù)。
pair<iterator, bool> Insert(const T& data)
//紅黑樹必須通過結(jié)點(diǎn)里面存儲的key來進(jìn)行比較才可以插入結(jié)點(diǎn)，所以出現(xiàn)了kot仿函數(shù)對象
{
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
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);
Node* curit = cur;//保存一下cur的位置否則下面旋轉(zhuǎn)調(diào)色過程中，cur有可能被改了
if (kot(parent->_data) > kot(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else if (cur == parent->_left)
{
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
break;
}
else if (cur == parent->_right)
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
else
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
uncle->_col = parent->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
else if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
break;
}
else if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
}
_root->_col = BLACK;
return make_pair(iterator(curit), true);
}
3.下面是紅黑樹這一層Insert的實(shí)現(xiàn)，我們對其內(nèi)部實(shí)現(xiàn)稍作改動，更改其返回值為鍵值對，如果出現(xiàn)插入key值相等的情況，則將bool改為false即可。最后調(diào)色后返回鍵值對時，我們不能直接返回cur構(gòu)造的迭代器，因?yàn)槿绻l(fā)生調(diào)色，則cur位置會更改，所以在插入結(jié)點(diǎn)后，用一個curit的結(jié)點(diǎn)指針記錄一下插入結(jié)點(diǎn)的位置，最后返回由curit結(jié)點(diǎn)指針構(gòu)造出來的迭代器。
pair<iterator, bool> Insert(const T& data)
//紅黑樹必須通過結(jié)點(diǎn)里面存儲的key來進(jìn)行比較才可以插入結(jié)點(diǎn)，所以出現(xiàn)了kot仿函數(shù)對象
{
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
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);
Node* curit = cur;//保存一下cur的位置否則下面旋轉(zhuǎn)調(diào)色過程中，cur有可能被改了
if (kot(parent->_data) > kot(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else if (cur == parent->_left)
{
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
break;
}
else if (cur == parent->_right)
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
else
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
uncle->_col = parent->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
else if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
break;
}
else if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
}
_root->_col = BLACK;
return make_pair(iterator(curit), true);
}
4.Insert返回的iterator和set表層的const_iterator返回類型不兼容（重寫迭代器的拷貝構(gòu)造函數(shù)）
1.我們知道一般情況下，迭代器的拷貝構(gòu)造是不需要我們自己寫的，因?yàn)榫幾g器默認(rèn)生成的值拷貝就夠用了，兩個迭代器之間進(jìn)行結(jié)點(diǎn)指針的賦值即可，這兩個迭代器我們一般都默認(rèn)為相同類型，比如普通迭代器和普通迭代器進(jìn)行賦值，const迭代器和const迭代器進(jìn)行賦值。
但其實(shí)庫里面的容器都支持用普通迭代器去拷貝構(gòu)造const迭代器，下面的list和vector都支持這樣的操作，那這樣的操作是怎么實(shí)現(xiàn)的呢？
int main()
{
list<int> lt;
vector<int> v;
list<int>::const_iterator clit = lt.begin();
vector<int>::const_iterator cvit = v.begin();
return 0;
}2.其實(shí)實(shí)現(xiàn)這樣的操作并不復(fù)雜，不過我們需要重寫迭代器的拷貝構(gòu)造，當(dāng)const迭代器調(diào)用自身拷貝構(gòu)造時，我們想讓拷貝對象是普通迭代器，那就不能用Self作為拷貝構(gòu)造函數(shù)的形參類型，所以此時就重新在迭代器內(nèi)部定義一個固定不變的類型iterator，用這個類型作為拷貝構(gòu)造的形參類型。
所以當(dāng)const迭代器之間進(jìn)行拷貝的時候，const迭代器類里面是沒有寫const迭代器之間的拷貝構(gòu)造的，所以編譯器會默認(rèn)生成拷貝構(gòu)造。
當(dāng)普通迭代器之間進(jìn)行拷貝的時候，普通迭代器類里面寫了普通迭代器之間的拷貝構(gòu)造，那么編譯器就不會默認(rèn)生成拷貝構(gòu)造。
當(dāng)const迭代器被普通迭代器拷貝的時候，const迭代器類里面的構(gòu)造函數(shù)會被調(diào)用，即用普通迭代器構(gòu)造出const迭代器。。
template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;// node里面存的是鍵值對或key類型變量
typedef __RBTreeIterator<T, Ref, Ptr> Self;//迭代器
typedef __RBTreeIterator<T, T&, T*> iterator;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
//如果是const迭代器調(diào)用，這里是構(gòu)造。如果是普通迭代器調(diào)用，這里是拷貝構(gòu)造。
__RBTreeIterator(const iterator& it)
:_node(it._node)
{}
3.既然set不是要返回const迭代器么，我們只需要先接收一下insert的鍵值對，然后再重寫拷貝構(gòu)造一個鍵值對即可，鍵值對的first拷貝會調(diào)用iterator類型的拷貝構(gòu)造函數(shù)（我們重寫的拷貝構(gòu)造就派上用場了），bool值則直接進(jìn)行值拷貝即可。
template <class K>
class set
{
public:
pair<iterator, bool> insert(const K& key)//這里的迭代器被替換為const_iterator
{
//return _t.Insert(key);
//Insert返回的是普通迭代器，普通迭代器不能直接拷貝構(gòu)造給const迭代器，類型不同，但我們可以自己寫拷貝構(gòu)造。
//這里肯定不能再使用const修飾來進(jìn)行解決了，因?yàn)閕nsert功能就是要寫嘛，又不具有讀的功能，實(shí)現(xiàn)const版本干嘛？？？
pair<typename RBTree<K, K, SetKeyOfT<K>>::iterator, bool> ret = _t.Insert(key);
//必須用紅黑樹底層的普通迭代器類型接收Insert返回的鍵值對，因?yàn)閟et的所有迭代器都是底層const迭代器typedef出來的
return pair<iterator, bool>(ret.first, ret.second);
//這里在利用Insert的返回值重新拷貝構(gòu)造一個鍵值對，用普通迭代器構(gòu)造const迭代器，然后返回具有const迭代器的鍵值對
//********set這個地方即使自己寫了拷貝構(gòu)造，在返回的時候也依舊不能直接強(qiáng)轉(zhuǎn)，這誰能想到??？？？？？？？？？？？？
}
private:
RBTree<K, K, SetKeyOfT<K>> _t;
};
四、對于紅黑樹設(shè)計(jì)產(chǎn)生的問題
1.map底層的紅黑樹存的是<key,value>的鍵值對，set底層的紅黑樹存的是key關(guān)鍵碼，我當(dāng)時覺得為什么一定要設(shè)計(jì)成這樣呢？我們讓map的紅黑樹結(jié)點(diǎn)只存儲value不可以嗎？修改value不就行了嗎？搞個鍵值對干嘛啊，其實(shí)這個問題很好解決，我當(dāng)時也是蒙了產(chǎn)生這樣的問題。
紅黑樹插入結(jié)點(diǎn)的原理是什么呢？原理不就是和搜索樹一樣么，只有結(jié)點(diǎn)之間能夠進(jìn)行比較我們才能將結(jié)點(diǎn)按照搜索樹的規(guī)則進(jìn)行插入啊，那如果紅黑樹結(jié)點(diǎn)想要進(jìn)行比較，那只能通過結(jié)點(diǎn)的key來進(jìn)行比較，所以map就不能只存value，必須存儲鍵值對，只有這樣才能進(jìn)行結(jié)點(diǎn)之間的比較。
總結(jié)
到此這篇關(guān)于C++使用一棵紅黑樹同時封裝出map和set的文章就介紹到這了,更多相關(guān)C++紅黑樹封裝map和set內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- C++用一棵紅黑樹同時封裝出set與map的實(shí)現(xiàn)代碼
- C++ map與set封裝實(shí)現(xiàn)過程講解
- C++中map和set封裝實(shí)現(xiàn)示例
- C++深入探究哈希表如何封裝出unordered_set和unordered_map
- c++容器list、vector、map、set區(qū)別與用法詳解
- C++ STL入門教程(7) multimap、multiset的使用
- C++中map和set的簡介及使用詳解
- C++中set/multiset與map/multimap的使用詳解
- C++中map和set的使用詳細(xì)攻略
- C++中常見容器類的使用方法詳解(vector/deque/map/set)
- C++實(shí)現(xiàn)map和set封裝詳解
相關(guān)文章
首先簡單說一下什么是行壓縮圖，其實(shí)嚴(yán)格意義上應(yīng)該是行壓縮矩陣2013-05-05
使用C/C++調(diào)用libcurl調(diào)試消息的方式
在使用 C/C++ 調(diào)用 libcurl 進(jìn)行 HTTP 請求時,有時我們需要查看請求的/應(yīng)答消息的內(nèi)容（包括請求頭和請求體）以方便調(diào)試,libcurl 提供了多種方法來捕獲和輸出這些信息,本文介紹具體的使用方式,需要的朋友可以參考下2025-02-02
一般情況下，由鍵盤輸入的字符并沒有直接送入程序，而是被存儲在一個緩沖區(qū)當(dāng)中。下面這篇文章主要給大家介紹了關(guān)于C語言中輸入輸出流與緩沖區(qū)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-09-09
C++編程之CString、string與、char數(shù)組的轉(zhuǎn)換
這篇文章主要介紹了C++編程之CString、string與、char數(shù)組的轉(zhuǎn)換的相關(guān)資料,希望通過本文能幫助到大家，讓大家學(xué)習(xí)理解這部分內(nèi)容，需要的朋友可以參考下2017-10-10
訪問說明符是 C++ 中控制類成員（屬性和方法）可訪問性的關(guān)鍵字,它們用于封裝類數(shù)據(jù)并保護(hù)其免受意外修改或?yàn)E用,本文將給大家詳細(xì)的介紹一下C++的訪問說明符,感興趣的朋友可以參考下2024-04-04
這篇文章主要介紹了淺析C++中的函數(shù)重載,在C++中，可以為兩個或兩個以上的函數(shù)提供相同的函數(shù)名稱，只要參數(shù)類型不同，或者參數(shù)類型相同而參數(shù)個數(shù)不同，又或者參數(shù)類型參數(shù)個數(shù)相同，參數(shù)次序不同，稱為函數(shù)重載,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了C語言SQLite3事務(wù)和鎖的操作,結(jié)合完整實(shí)例形式分析了C語言針對SQLite3數(shù)據(jù)庫的事務(wù)與鎖相關(guān)操作技巧,需要的朋友可以參考下2017-07-07
這篇文章主要介紹了在C語言編程中使用變量的基礎(chǔ)教程,特別需要注意C語言中的指針變量,需要的朋友可以參考下2016-02-02
C++多線程實(shí)現(xiàn)TCP服務(wù)器端同時和多個客戶端通信
通訊建立后首先由服務(wù)器端發(fā)送消息，客戶端接收消息；接著客戶端發(fā)送消息，服務(wù)器端接收消息，實(shí)現(xiàn)交互發(fā)送消息。本文主要介紹了C++多線程實(shí)現(xiàn)TCP服務(wù)器端同時和多個客戶端通信，感興趣的可以了解一下2021-05-05
opencv實(shí)現(xiàn)視場轉(zhuǎn)換
這篇文章主要為大家詳細(xì)介紹了opencv實(shí)現(xiàn)視場轉(zhuǎn)換，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04