緒論?：
“我這個(gè)人走得很慢，但是我從不后退?！獊啿薄ち挚稀?#xff0c;本章是接上一章搜索二叉樹中紅黑樹的后續(xù)文章，若沒有看過強(qiáng)烈建議觀看，否則后面模擬實(shí)現(xiàn)部分很看懂其代碼原理。本章主要講了map、set是如何使用的，以及map、set如何底層實(shí)現(xiàn)相較于前面的章節(jié)本章更加考驗(yàn)?zāi)愕倪壿嬆芰磉M(jìn)行封裝，還能幫助對大體框架的有更加好的了解。下一章將進(jìn)入哈希表的學(xué)習(xí)，同樣也是STL中非常重要且難以學(xué)習(xí)的章節(jié)敬請期待（早關(guān)注不迷路！）。話不多說安全帶系好，發(fā)車?yán)?#xff08;建議電腦觀看）。

---

1.set

1.1set的概念

set其底層就是紅黑樹，所以其很多特性也和紅黑樹一樣也就表明了他就是一個(gè)二叉搜索樹。set看起來只是存著value，但是set是關(guān)聯(lián)式容器容器內(nèi)部的元素都是pair<key,value>構(gòu)成的鍵值對，所以set的value元素其實(shí)就是pair<value,value>它兩個(gè)元素是相同的且只存了一個(gè)值value，但我們在使用的時(shí)候并不用管底層只需要插入正常的value值即可，并且在set中所有元素值value都是唯一的不能重復(fù)出現(xiàn)，在set中不能修改元素的值，但可以正常增刪元素，同二叉搜索樹一樣他可以通過迭代器遍歷出有序?qū)Α?br /> set常用來：去重（去掉一個(gè)序列的相同值）、排序、查找。

1.2set常使用的方法

1. set的模板參數(shù)：
   

Compare默認(rèn)缺省為less也就表示其默認(rèn)是其底層是 x < y，這樣如果用迭代器遍歷出來就是一個(gè)升序。 x < y 返回真進(jìn)行交換，反之x>y的話返回假（和vector等若干容器中一樣）。

2. set的構(gòu)造：
   上圖123如何使用對應(yīng)下圖123的具體方法：
   源碼：

void test1()
{set<int> s1;//無參的構(gòu)造int a[] = { 1,2,3,4,5,6 };for (auto ch : a){s1.insert(ch);//調(diào)用插入函數(shù)直接放value值即可}set<int> s2(s1.begin(), s1.end());//迭代器的構(gòu)造 ， 構(gòu)造出來和s1一樣set<int> s3(s2);//拷貝構(gòu)造，拷貝s2for (auto k : s1){cout << k << " ";}cout << endl;for (auto k : s2){cout << k << " ";}cout << endl;for (auto k : s3){cout << k << " ";}cout << endl;
}

3. set的插入：
   
   下圖123對應(yīng)著上圖123的使用方法：
   
   1. 在方法1中的返回值一個(gè)pair<iterator,bool>類型，其中iterator指向插入的節(jié)點(diǎn)，bool表示true表示不存在該元素插入成功，false表示已經(jīng)存在該元素則插入失敗。
   2. 在方法2中返回的是新插入節(jié)點(diǎn)的迭代器。
      源碼：

void Print(const set<int>& s1)
{for (auto k : s1){cout << k << " ";}cout << endl;
}
void test2()
{set<int> s1;int a[] = { 1, 2, 3, 4, 5, 6 };for (auto ch : a){s1.insert(ch);//直接插入value值}Print(s1);s1.insert(s1.begin(), 0);//在指定迭代器位置插入Print(s1);set<int> s2 = { 7,8,9,10 }; //c++11知識暫時(shí)不管s1.insert(s2.begin(), s2.end());//迭代器區(qū)域插入Print(s1);
}

4. set的刪除：
   下圖123對應(yīng)著上圖123的使用方法：
   
   1. 在2方法中返回的是刪除元素的個(gè)數(shù)（size_type 就是 size_t 無符號整形）
      源碼：

void Print(const set<int>& s1)
{cout << "P：";for (auto k : s1){cout << k << " ";}cout << endl;
}
void test3()
{set<int>s1{ 1,2,3,4,5,6,7,8,9,10 };//c++11知識暫時(shí)不管Print(s1);s1.erase(s1.begin());//迭代器指定刪除Print(s1);s1.erase(10);//刪除指定元素Print(s1);s1.erase(s1.begin(), s1.end());//刪除一段迭代器區(qū)間Print(s1);
}

5. set的查找find、查看個(gè)數(shù)size、是否為空empty、是否存在count、清空元素clear：
   
   下面通過代碼解釋：
   1. find，返回迭代器，如找到則返回找到的元素的迭代器，反之返回nullptr的迭代器
   2. size，返回該容器的元素個(gè)數(shù)
   3. empty，返回0表示非空，返回1表示空
   4. count，返回1表示存在，返回0表示是不存在

源碼：

void test4()
{set<int>s1{ 1,2,3,4,5,6,7,8,9,10 };//c++11知識暫時(shí)不管set<int>::iterator it1 = s1.find(8);if (it1 != s1.end())cout << "find的返回值(指向該元素)：" << *it1 << endl;else cout << "返回Nullptr" << endl;cout << "8值是否存在(返回1表示存在0表示不存在)：" << s1.count(8) << endl;cout <<"s1的元素個(gè)數(shù)(返回元素個(gè)數(shù))：" << s1.size() << " | s1是否為空(0表示非空反之1為空)：" << s1.empty() << endl;cout << endl;s1.clear();//清空元素set<int>::iterator it2 = s1.find(8);if(it2 != s1.end())cout << "find的返回值(指向該元素)：" << *it2 << endl;else cout << "返回Nullptr" << endl;cout << "8值是否存在(返回1表示存在0表示不存在)：" << s1.count(8) << endl;cout << "s1的元素個(gè)數(shù)(返回元素個(gè)數(shù))：" << s1.size() << " | s1是否為空(0表示非空反之1為空)：" << s1.empty() << endl;
}

7. set的交換swap、指定區(qū)間的lower_bound、upper_bound：
   

lower_bound和upper_bound是通過指定數(shù)值來確定迭代器區(qū)間，常用來指定刪除數(shù)據(jù)的區(qū)間，如：1 2 3 4 5 6 ， lower_bound(2)，upper_bound(5)，這樣取出來的區(qū)間lower_bound指向的就是2（取>=value的值），而upper_bound指向的是6（取>value的值），但因?yàn)榈鲄^(qū)間是左閉右開的所以即使刪除也不會刪到6！

源碼：

void Print(const set<int>& s1)
{cout << "P：";for (auto k : s1){cout << k << " ";}c
void test5()
{set<int>s1{ 1,2,3,4,5,6 };set<int>s2{ 7,8,9,10,11,12 };Print(s1);Print(s2);s1.swap(s2);//s1 和 s2 交換Print(s1);Print(s2);cout << "upper_bound：" << *s1.upper_bound(11) << endl;s1.erase(s1.lower_bound(8), s1.upper_bound(11));Print(s1);cout << "upper_bound：" << *s2.upper_bound(5) << endl;s2.erase(s2.lower_bound(2), s2.upper_bound(5));Print(s2);
}

1.3 multiset的概念和使用

其原理和set幾乎一致，只是multiset能存多個(gè)相同的值了
注意點(diǎn)：是find查找時(shí)是返回第一個(gè)遇到的value，count將返回該值存在的個(gè)數(shù)
其中還要交代一個(gè)函數(shù)(set中也有不過不夠?qū)嵱?

他返回的是pair<iterator,iterator>，這兩個(gè)迭代器分別表示的就是value值的lower_bound和upper_bound，這樣就能一次性刪除所有相同的元素！

void Print(const multiset<int>& s1)
{cout << "P：";for (auto k : s1){cout << k << " ";}cout << endl;
}
void test6()
{multiset<int> s{ 1,1,2,2,2,3,3 };Print(s);cout << "lower_bound：" << *s.equal_range(2).first << endl;cout << "upper_bound：" << *s.equal_range(2).second << endl;s.erase(s.equal_range(2).first, s.equal_range(2).second);Print(s);
}

2.map

2.1map的概念

map底層也是紅黑樹，同理也就表明了他就是一個(gè)二叉搜索樹。map不同于set他的K,V兩個(gè)值都是有用的，map也是關(guān)聯(lián)式容器，
1. 容器內(nèi)部的元素都是pair<K,V>構(gòu)成的一個(gè)個(gè)鍵值對
2. 如果是比較大小的話通常是用key值來進(jìn)行
3. 在map中所有元素的值都是唯一的（指的是key值不能重復(fù)）
4. 在map中不能修改元素的值（即是不能修改K值的，只能修改value值）

2.2map常使用的方法

1. map的模板參數(shù)：
   

同樣Compare默認(rèn)缺省為less

2. map的構(gòu)造：
   
   對照著set幾乎一樣，直接通過代碼展示了
   
   注意點(diǎn)：
   1. 范圍for打印時(shí)給kv的是迭代器，迭代器的類型是pair<K,V>所以kv.first指向Key，kv.second指向value
   2. 插入的數(shù)據(jù)必須是鍵值對，用make_pair()函數(shù)直接構(gòu)造

源碼：

void Print(const map<int,int>& m1)
{cout << "P：";for (auto kv : m1){cout << kv.first << " " << kv.second << " | ";}cout << endl;
}
void test1()
{map<int, int> m1;//無參的構(gòu)造int a[] = { 1,2,3,4,5,6 };for (auto ch : a){m1.insert(make_pair(ch, ch));//調(diào)用插入函數(shù)注意插入的是構(gòu)造出來的pair，通過make_pair（n1,n2）,//給定兩個(gè)參數(shù)就能直接構(gòu)造出對應(yīng)參數(shù)類型的pair(n1,n2)}map<int, int> m2(m1.begin(), m1.end());//迭代器的構(gòu)造,構(gòu)造出來和m1一樣map<int, int> m3(m2);//拷貝構(gòu)造，拷貝m2Print(m1);Print(m2);Print(m3);
}

3. set的插入：
   其中插入函數(shù)參數(shù)的value_type的實(shí)際類型是pair<const K,V>
   注意點(diǎn)：
   1. 用make_pair(key,value)構(gòu)造出K,V類型的pair<K,V>當(dāng)參數(shù)傳遞進(jìn)去，或者寫成用pair的構(gòu)造pair<K,V>(key,value)（具體如下）
      
   2. 返回pair<iterator,bool>。
   3. 若返回的iterator，需要注意的是其類型是pair<K,V>型

map<int, int> m1;
m1.insert(make_pair(1,1));//構(gòu)造出pair(1,1) 或m1.insert(pair<int,int>(1,1));

4. map的刪除：
   
   同理使用迭代器部分是一樣的，此處刪除時(shí)就不用在使用pair了，直接通過確定key即可刪除。
   

void test2()
{map<int, int> m1;int a[] = { 1,2,3};for (auto ch : a){m1.insert(make_pair(ch, ch));}Print(m1);m1.erase(1);Print(m1);
}

5. map的查找find、查看個(gè)數(shù)size、是否為空empty、是否存在count、清空元素clear、交換swap：

此處find、count的參數(shù)同樣用key即可使用、其余函數(shù)和set完全一樣。

6. map的重載operator[]（極其重要）

通過代碼和底層來解釋：
其中我們operator[]的底層是：
(*((this->insert(make_pair(k,mapped_type()))).first)).second
其中能看到他是調(diào)用了插入函數(shù)，所以[]能實(shí)現(xiàn)插入功能
而我們map的插入返回的類型是：pair<iterator,bool>
所以就能簡化為：(*pair<iterator,bool>.first).second//此處.的優(yōu)先級高于*所以是先訪問，得到iterator后，再(*iterator).second得到其迭代器的value值，也就是插入時(shí)的第二個(gè)參數(shù)
所以分析上面代碼：m1[ch]++;第一次進(jìn)去的時(shí)候插入成功并且返回來他的second++，這樣就能不斷的插入，即使后面是插入失敗也能返回second進(jìn)行++，所以就能形成計(jì)數(shù)器。（其中注意點(diǎn)我們雖然沒有初始化int，但其實(shí)其內(nèi)部會默認(rèn)為0開始，也就是上面的mapped_type()他會自動構(gòu)造出該類型的初始值，int為0，string為""）

2.3 multimap的概念和使用

與multiset一樣，都是可以出現(xiàn)重復(fù)的值，只是其中沒有了map的operator[ ]，就不過訴了。

3.map、set的底層實(shí)現(xiàn)

3.1紅黑樹的修改

為了給set、map做底層，我們需要完善一下紅黑樹在里面主要是

1. 模板的改變：將原本第二個(gè)參數(shù)V改成T，T代表的是K，V組成成的鍵值對pair<K,V>
2. 添加迭代器以及begin、end函數(shù)，讓map、set也能用迭代器
3. 修改插入的返回值：將原本的iterator改成pair<iterator,bool>，（這是STL源碼內(nèi)的設(shè)計(jì)，也是為了map的[]做準(zhǔn)備）

修改后的源碼：

#pragma once
#include<iostream>
using namespace std;
enum Color
{BLACK,RED
};template<class T>
struct RBTreeNode {RBTreeNode<T>* _left = nullptr;RBTreeNode<T>* _right = nullptr;RBTreeNode<T>* _parent = nullptr;T _data;Color _col = RED;//默認(rèn)生成的節(jié)點(diǎn)顏色是紅色RBTreeNode(const T& data):_data(data){}
};//迭代器
template<class T, class Ptr, class Ref>
struct _TreeIterator
{typedef _TreeIterator<T, Ptr, Ref> Self;typedef RBTreeNode<T> Node;Node* _node;//迭代器的成員變量_TreeIterator(Node* node):_node(node){}Self& operator++(){Node* cur = _node;if (cur->_right)//若右邊不為空，則找到其左邊的右邊節(jié)點(diǎn){cur = cur->_right;while (cur->_left){cur = cur->_left;}_node = cur;}else{Node* parent = cur->_parent;while (parent && parent->_left != cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator==(const Self & it){return _node == it._node;}bool operator!=(const Self & it){return _node != it._node;}};template<class K, class T, class Compare>
class RBTree
{typedef RBTreeNode<T> Node;Compare kot;
public:typedef _TreeIterator<T,T*,T&> iterator;typedef _TreeIterator<T,const T*,const T&> const_iterator;//typedef typename RBTree<K, pair<K, V>, Mapofkey>::iterator iterator;// 在紅黑樹中插入值為data的節(jié)點(diǎn)，插入成功返回true，否則返回false// 注意：為了簡單起見，本次實(shí)現(xiàn)紅黑樹不存儲重復(fù)性元素iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);//end指向最后數(shù)據(jù)的后面故為空}const_iterator begin() const{Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);//end指向最后數(shù)據(jù)的后面故為空}//此處用Node* 的原因set處的iterator為了防止被修改所以set內(nèi)的iterator本質(zhì)還是const_iterator，//所以這里用了 Node* 來代替iterator 的返回pair<Node*, bool> Insert(const T& data){//此處和AVL平衡二叉樹的性質(zhì)一樣找到所要插入節(jié)點(diǎn)的位置 大的在右 、 小的在左Node* parent = nullptr;Node* cur = _root;if (cur == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}//找到插入的位置！while (cur)//當(dāng)為null時(shí)表示此處就是要插入的位置！{if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else{return make_pair(nullptr, false);}}//找到位置后，插入cur = new Node(data);//建立新節(jié)點(diǎn)Node* ret = cur;//建立鏈接if (kot(parent->_data) > kot(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//插入時(shí)要判斷插入后是否會導(dǎo)致不平衡！對于紅黑樹來說主要問題有//1. 不能出現(xiàn)連續(xù)的紅節(jié)點(diǎn)//2. 最長路徑不超過最短路徑的兩倍//判斷是否需要變色/旋轉(zhuǎn)// //1.當(dāng)父親節(jié)點(diǎn)為黑色時(shí)，當(dāng)新增了一個(gè)紅色節(jié)點(diǎn)時(shí)就結(jié)束插入了// //2.當(dāng)父為紅時(shí)：//	情況一(僅變色即可)：當(dāng)parent為紅 grandfather為黑 uncle存在且為黑 插入一個(gè)新節(jié)點(diǎn)while (parent && parent->_col == RED){Node* g = parent->_parent;//grandfatherif (g->_left == parent){Node* u = g->_right;//uncleif (u && u->_col == RED)//u存在且為紅{//變色即可u->_col = parent->_col = BLACK;g->_col = RED;//向上調(diào)整cur = g;parent = g->_parent;//當(dāng)g 的 父親為黑時(shí)或者為null時(shí)停止調(diào)整}else //u不存在或者為黑{if (cur == parent->_left)//此處u不存在和當(dāng)插入節(jié)點(diǎn)在左邊時(shí)的情況一樣直接右旋加變色即可{//旋轉(zhuǎn)加變色RotateR(g);parent->_col = BLACK;g->_col = RED;}else{//旋轉(zhuǎn)加變色RotateL(parent);RotateR(g);cur->_col = BLACK;g->_col = RED;}}}else{Node* u = g->_left;//uncleif (u && u->_col == RED)//u存在且為紅{//變色即可u->_col = parent->_col = BLACK;g->_col = RED;//向上調(diào)整cur = g;parent = g->_parent;//當(dāng)g 的 父親為黑時(shí)或者為null時(shí)停止調(diào)整}else //u不存在或者為黑{if (cur == parent->_right)//此處u不存在和當(dāng)插入節(jié)點(diǎn)在左邊時(shí)的情況一樣直接右旋加變色即可{RotateL(g);parent->_col = BLACK;g->_col = RED;}else{RotateR(parent);RotateL(g);cur->_col = BLACK;g->_col = RED;}}}}_root->_col = BLACK;return make_pair(ret, true);}void Inorder(){_Inorder(_root);cout << endl;}// 獲取紅黑樹最左側(cè)節(jié)點(diǎn)Node* LeftMost(){Node* cur = _root;while (cur){if (cur->_left == nullptr){return cur;}cur = cur->_left;}return nullptr;}// 獲取紅黑樹最右側(cè)節(jié)點(diǎn)Node* RightMost(){Node* cur = _root;while (cur){if (cur->_right == nullptr){return cur;}cur = cur->_right;}return nullptr;}//  檢測紅黑樹是否為有效的紅黑樹，注意：其內(nèi)部主要依靠_IsValidRBTRee函數(shù)檢測//	1.每條路徑中的黑色節(jié)點(diǎn)個(gè)數(shù)是否一樣//	2.最長路徑不超過最短路徑的兩倍//	3.不能出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)//	4.根節(jié)點(diǎn)為黑色bool IsValidRBTRee(){if (_root == nullptr) return true;if (_root->_col == RED) return false;Node* cur = _root;int blackCount = 0;while (cur){if (cur->_col == BLACK){blackCount++;}cur = cur->_left;}return _IsValidRBTRee(_root, blackCount, 0);}int Height(){if (_root == nullptr) return 0;return _Height(_root);}int Size(){if (_root == nullptr) return 0;return _Size(_root);}//檢測紅黑樹中是否存在值為data的節(jié)點(diǎn)，存在返回該節(jié)點(diǎn)的地址，否則返回nullptrNode* Find(const K& val){Node* cur = _root;while (cur){if (kot(cur->_data) == val){return cur;}else if (kot(cur->_data) > val){cur = cur->_left;}else {cur = cur->_right;}}return nullptr;}
private:int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) +_Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int lefthight = _Height(root->_left);int righthight = _Height(root->_right);return lefthight > righthight ? lefthight + 1 : righthight + 1;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_data.first << " ";_Inorder(root->_right);}bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack){if (root == nullptr){if (blackCount != pathBlack)//當(dāng)為null時(shí)表示該路徑已經(jīng)結(jié)束，那么判斷改路徑的黑色節(jié)點(diǎn)（pathblack） 和其他路徑的黑色節(jié)點(diǎn)（blacCount）是否相同{return false;}return true;}if (root->_col == RED){if (root->_left && root->_right && (root->_left->_col == RED || root->_right->_col == RED)){cout << "有連續(xù)的紅色節(jié)點(diǎn)" << endl;return false;}}if (root->_col == BLACK){pathBlack++;}return _IsValidRBTRee(root->_left, blackCount, pathBlack) &&_IsValidRBTRee(root->_right, blackCount, pathBlack);}//	// 為了操作樹簡單起見：獲取根節(jié)點(diǎn)//Node*& GetRoot();void RotateR(Node* parent){Node* SubL = parent->_left;//此處就為 curNode* SubLR = SubL->_right;//parent的左換成cur的右parent->_left = SubLR;//把cur的右孩子換成parentSubL->_right = parent;//注意還要修改其父指針Node* Ppnode = parent->_parent;parent->_parent = SubL;if (SubLR)//cur的右邊可能為空SubLR->_parent = parent;if (_root == parent)//如果parent為根節(jié)點(diǎn)，則需要把subR改變成根節(jié)點(diǎn)并且其父親為nullptr{_root = SubL;SubL->_parent = nullptr;}else{//同時(shí)還要考慮父親 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubL;}else{Ppnode->_right = SubL;}SubL->_parent = Ppnode;}}// 左單旋// 同理void RotateL(Node* parent){Node* SubR = parent->_right;//此處就為 curNode* SubRL = SubR->_left;//parent的右換成cur的左parent->_right = SubRL;//把cur的左孩子換成parentSubR->_left = parent;Node* Ppnode = parent->_parent;//注意 還要修改其父指針parent->_parent = SubR;if (SubRL)//右邊可能為空SubRL->_parent = parent;if (_root == parent)//如果parent為根節(jié)點(diǎn)，則需要把subR改變成根節(jié)點(diǎn)并且其父親為nullptr{_root = SubR;SubR->_parent = nullptr;}else{//同時(shí)還要考慮父親 是祖先的左或右if (Ppnode->_left == parent){Ppnode->_left = SubR;}else{Ppnode->_right = SubR;}SubR->_parent = Ppnode;}}private:Node* _root = nullptr;
};

為了讓set、map能實(shí)現(xiàn)迭代器所以還要寫好迭代器常用的重載operator*、operator++、operator!=、…

下面是實(shí)現(xiàn)過程也就是再將以及寫好的紅黑樹進(jìn)行再一次的封裝，實(shí)現(xiàn)set、map所需要的功能。

3.2set的實(shí)現(xiàn)

#pragma once
#include"RBTree.h"template<class K>
class MySet
{
public:struct Setofkey{//自己所寫的適配器用來從pair中調(diào)出key值const K& operator()(const K& key){return key;}};//通過紅黑樹的迭代器來重定義生成自己的
//typename的意思是聲明他是類型名typedef typename RBTree<K, K, Setofkey>::const_iterator iterator;typedef typename RBTree<K, K, Setofkey>::const_iterator const_iterator;pair<iterator, bool> Insert(const K& key){return _rb.Insert(key);// pair<Node*, bool> 給 pair<iterator, bool>// pair的構(gòu)造函數(shù)： template<class U, class V> pair (const pair<U,V>& pr);// 這樣就能通過一個(gè)pair去構(gòu)造另外一個(gè)pair// 所以返回來的pair<Node*,bool> 就會對應(yīng)給到要返回的pair<iterator,bool>的 iterator 和 bool 來進(jìn)行構(gòu)造// 這樣就能iterator避免內(nèi)外的不一樣，外部的是iterator其實(shí)是const_iterator}pair<iterator, bool> Insert(const K& key)const{return _rb.Insert(key);//pair<iterator, bool>  }//普通對象、const對象都能調(diào)用iterator begin() const{return _rb.begin();}iterator end() const{return _rb.end();}private:RBTree<K,K,Setofkey> _rb;
};

3.3map的實(shí)現(xiàn)

#pragma once
#include"RBTree.h"template<class K,class V>
class MyMap
{
public:
//自己所寫的適配器用來從pair中調(diào)出key值struct Mapofkey{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef typename RBTree<K, pair<const K, V>,Mapofkey>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, Mapofkey>::const_iterator const_iterator;pair<iterator, bool> Insert(const pair<K,V>& kv){return _rb.Insert(kv);}iterator begin(){return _rb.begin();}iterator end(){return _rb.end();}const_iterator begin() const{return _rb.begin();}const_iterator end() const{return _rb.end();}V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key,V()));return ret.first->second;}private:RBTree<K, pair<const K,V>,Mapofkey> _rb;
};

---

本章完。預(yù)知后事如何，暫聽下回分解。

如果有任何問題歡迎討論哈！

如果覺得這篇文章對你有所幫助的話點(diǎn)點(diǎn)贊吧！

持續(xù)更新大量C++細(xì)致內(nèi)容，早關(guān)注不迷路。

?