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