【C++】：STL詳解 —— 紅黑樹封裝map和set

紅黑樹的源代碼

正向迭代器的代碼

反向迭代器的代碼

set的模擬實現

map的模擬實現

紅黑樹的源代碼

#pragma once
#include <iostream>using namespace std;
// set ->key
// map ->key/value// set ->key
// map ->key/valueenum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};// 紅黑樹正向迭代器模板
// 模板參數:
//   T    - 結點數據類型
//   Ref  - 數據的引用類型
//   Ptr  - 數據的指針類型
template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;					// 紅黑樹結點類型typedef __TreeIterator<T, Ref, Ptr> Self;	// 迭代器自身類型Node* _node;								// 當前迭代器持有的結點指針// 構造函數// 參數://   node - 需要包裝的結點指針__TreeIterator(Node* node): _node(node)  // 初始化持有的結點指針{}// 解引用操作符（獲取數據引用）Ref operator*(){return _node->_data;  // 返回結點存儲數據的引用}// 箭頭操作符（獲取數據指針）Ptr operator->(){return &_node->_data;  // 返回指向結點數據的指針}// 不等比較操作符// 參數://   s - 要比較的迭代器// 返回值: 兩個迭代器是否指向不同結點bool operator!=(const Self& s) const{return _node != s._node;  // 直接比較結點指針}// 相等比較操作符// 參數://   s - 要比較的迭代器// 返回值: 兩個迭代器是否指向相同結點bool operator==(const Self& s) const{return _node == s._node;  // 直接比較結點指針}// 前置自增操作符（中序遍歷順序的下一個結點）Self operator++(){if (_node->_right)  // 當前結點存在右子樹{// 尋找右子樹的最左結點（右子樹中的最小結點）Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else  // 當前結點沒有右子樹{// 向上尋找第一個不是右孩子的祖先結點Node* cur = _node;Node* parent = cur->_parent;// 沿著父指針向上查找，直到當前結點是父結點的左孩子while (parent && cur == parent->_right){cur = parent;parent = parent->_parent;}_node = parent;  // 最終定位到的父結點即為后繼}return *this;}// 前置自減操作符（中序遍歷順序的前一個結點）Self operator--(){if (_node->_left)  // 當前結點存在左子樹{// 尋找左子樹的最右結點（左子樹中的最大結點）Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else  // 當前結點沒有左子樹{// 向上尋找第一個不是左孩子的祖先結點Node* cur = _node;Node* parent = cur->_parent;// 沿著父指針向上查找，直到當前結點是父結點的右孩子while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;  // 最終定位到的父結點即為前驅}return *this;}
};//反向迭代器---迭代器適配器
template<class Iterator>
struct ReverseIterator
{typedef ReverseIterator<Iterator> Self; //反向迭代器的類型typedef typename Iterator::reference Ref; //結點指針的引用typedef typename Iterator::pointer Ptr; //結點指針Iterator _it; //反向迭代器所封裝的正向迭代器//構造函數ReverseIterator(Iterator it):_it(it) //根據所給正向迭代器構造一個反向迭代器{}Ref operator*(){return *_it; //通過調用正向迭代器的operator*返回結點數據的引用}Ptr operator->(){return _it.operator->(); //通過調用正向迭代器的operator->返回結點數據的指針}//前置++Self& operator++(){--_it; //調用正向迭代器的前置--return *this;}//前置--Self& operator--(){++_it; //調用正向迭代器的前置++return *this;}bool operator!=(const Self& s) const{return _it != s._it; //調用正向迭代器的operator!=}bool operator==(const Self& s) const{return _it == s._it; //調用正向迭代器的operator==}
};// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<const K, T>, MapKeyOfT> _t;
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator<T, T&, T*> iterator;			//正向迭代器typedef __TreeIterator<T, const T&, const T*> const_iterator;typedef ReverseIterator<iterator> reverse_iterator; //反向迭代器typedef ReverseIterator<const_iterator> const_reverse_iterator; iterator begin(){Node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}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);}reverse_iterator rbegin(){//尋找最右結點Node* right = _root;while (right && right->_right){right = right->_right;}//返回最右結點的反向迭代器return reverse_iterator(iterator(right));}reverse_iterator rend(){//返回由nullptr構造得到的反向迭代器（不嚴謹）return reverse_iterator(iterator(nullptr));}const_reverse_iterator rbegin() const{//尋找最右結點Node* right = _root;while (right && right->_right){right = right->_right;}//返回最右結點的反向迭代器return const_reverse_iterator(const_iterator(right));}const_reverse_iterator rend() const{//返回由nullptr構造得到的反向迭代器（不嚴謹）return const_reverse_iterator(const_iterator(nullptr));}//構造函數RBTree():_root(nullptr){}//拷貝構造RBTree(const RBTree<K, T, KeyOfT>& t){_root = _Copy(t._root, nullptr);}//賦值運算符重載（現代寫法）RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this; //支持連續賦值}//析構函數~RBTree(){_Destroy(_root);_root = nullptr;}size_t Size(){return _Size(_root);}bool Empty() const {return _root == nullptr;}void Clear() {_Destroy(_root);_root = nullptr;}void Swap(Node& other) {std::swap(_root, other._root);}//pair<iterator, bool> Insert(const T& data)pair<Node*, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;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(cur, false);}}// 新增節點給紅色cur = new Node(data);Node* newnode = cur;cur->_col = RED;if (kot(parent->_data) < kot(data)){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){//     g//   p   u// cNode* uncle = grandfather->_right;if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上更新處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){// 單旋//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// 雙旋//     g//   p//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else  // parent == grandfather->_right{//     g//   u   p //          c//Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   u   p //     c//RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(newnode, true);}//刪除函數bool Erase(const K& key){KeyOfT kot;//用于遍歷二叉樹Node* parent = nullptr;Node* cur = _root;//用于標記實際的待刪除結點及其父結點Node* delParentPos = nullptr;Node* delPos = nullptr;while (cur){if (key < kot(cur->_data)) //所給key值小于當前結點的key值{//往該結點的左子樹走parent = cur;cur = cur->_left;}else if (key > kot(cur->_data)) //所給key值大于當前結點的key值{//往該結點的右子樹走parent = cur;cur = cur->_right;}else //找到了待刪除結點{if (cur->_left == nullptr) //待刪除結點的左子樹為空{if (cur == _root) //待刪除結點是根結點{_root = _root->_right; //讓根結點的右子樹作為新的根結點if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根結點為黑色}delete cur; //刪除原根結點return true;}else{delParentPos = parent; //標記實際刪除結點的父結點delPos = cur; //標記實際刪除的結點}break; //進行紅黑樹的調整以及結點的實際刪除}else if (cur->_right == nullptr) //待刪除結點的右子樹為空{if (cur == _root) //待刪除結點是根結點{_root = _root->_left; //讓根結點的左子樹作為新的根結點if (_root){_root->_parent = nullptr;_root->_col = BLACK; //根結點為黑色}delete cur; //刪除原根結點return true;}else{delParentPos = parent; //標記實際刪除結點的父結點delPos = cur; //標記實際刪除的結點}break; //進行紅黑樹的調整以及結點的實際刪除}else //待刪除結點的左右子樹均不為空{//替換法刪除//尋找待刪除結點右子樹當中key值最小的結點作為實際刪除結點Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_data = minRight->_data; //將待刪除結點的_data改為minRight的_datadelParentPos = minParent; //標記實際刪除結點的父結點delPos = minRight; //標記實際刪除的結點break; //進行紅黑樹的調整以及結點的實際刪除}}}if (delPos == nullptr) //delPos沒有被修改過，說明沒有找到待刪除結點{return false;}//記錄待刪除結點及其父結點（用于后續實際刪除）Node* del = delPos;Node* delP = delParentPos;//調整紅黑樹if (delPos->_col == BLACK) //刪除的是黑色結點{if (delPos->_left) //待刪除結點有一個紅色的左孩子（不可能是黑色）{delPos->_left->_col = BLACK; //將這個紅色的左孩子變黑即可}else if (delPos->_right) //待刪除結點有一個紅色的右孩子（不可能是黑色）{delPos->_right->_col = BLACK; //將這個紅色的右孩子變黑即可}else //待刪除結點的左右均為空{while (delPos != _root) //可能一直調整到根結點{if (delPos == delParentPos->_left) //待刪除結點是其父結點的左孩子{Node* brother = delParentPos->_right; //兄弟結點是其父結點的右孩子//情況一：brother為紅色if (brother->_col == RED){delParentPos->_col = RED;brother->_col = BLACK;RotateL(delParentPos);//需要繼續處理brother = delParentPos->_right; //更新brother（否則在本循環中執行其他情況的代碼會出錯）}//情況二：brother為黑色，且其左右孩子都是黑色結點或為空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParentPos->_col == RED){delParentPos->_col = BLACK;break;}//需要繼續處理delPos = delParentPos;delParentPos = delPos->_parent;}else{//情況三：brother為黑色，且其左孩子是紅色結點，右孩子是黑色結點或為空if ((brother->_right == nullptr) || (brother->_right->_col == BLACK)){brother->_left->_col = BLACK;brother->_col = RED;RotateR(brother);//需要繼續處理brother = delParentPos->_right; //更新brother（否則執行下面情況四的代碼會出錯）}//情況四：brother為黑色，且其右孩子是紅色結點brother->_col = delParentPos->_col;delParentPos->_col = BLACK;brother->_right->_col = BLACK;RotateL(delParentPos);break; //情況四執行完畢后調整一定結束}}else //delPos == delParentPos->_right //待刪除結點是其父結點的左孩子{Node* brother = delParentPos->_left; //兄弟結點是其父結點的左孩子//情況一：brother為紅色if (brother->_col == RED) //brother為紅色{delParentPos->_col = RED;brother->_col = BLACK;RotateR(delParentPos);//需要繼續處理brother = delParentPos->_left; //更新brother（否則在本循環中執行其他情況的代碼會出錯）}//情況二：brother為黑色，且其左右孩子都是黑色結點或為空if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK))){brother->_col = RED;if (delParentPos->_col == RED){delParentPos->_col = BLACK;break;}//需要繼續處理delPos = delParentPos;delParentPos = delPos->_parent;}else{//情況三：brother為黑色，且其右孩子是紅色結點，左孩子是黑色結點或為空if ((brother->_left == nullptr) || (brother->_left->_col == BLACK)){brother->_right->_col = BLACK;brother->_col = RED;RotateL(brother);//需要繼續處理brother = delParentPos->_left; //更新brother（否則執行下面情況四的代碼會出錯）}//情況四：brother為黑色，且其左孩子是紅色結點brother->_col = delParentPos->_col;delParentPos->_col = BLACK;brother->_left->_col = BLACK;RotateR(delParentPos);break; //情況四執行完畢后調整一定結束}}}}}//進行實際刪除if (del->_left == nullptr) //實際刪除結點的左子樹為空{if (del == delP->_left) //實際刪除結點是其父結點的左孩子{delP->_left = del->_right;if (del->_right)del->_right->_parent = delP;}else //實際刪除結點是其父結點的右孩子{delP->_right = del->_right;if (del->_right)del->_right->_parent = delP;}}else //實際刪除結點的右子樹為空{if (del == delP->_left) //實際刪除結點是其父結點的左孩子{delP->_left = del->_left;if (del->_left)del->_left->_parent = delP;}else //實際刪除結點是其父結點的右孩子{delP->_right = del->_left;if (del->_left)del->_left->_parent = delP;}}delete del; //實際刪除結點return true;}//查找函數const_iterator Find(const K& key) const{KeyOfT kot;Node* cur = _root;while (cur){if (key < kot(cur->_data))	//key值小于該結點的值{cur = cur->_left;		//在該結點的左子樹當中查找}else if (key > kot(cur->_data)) //key值大于該結點的值{cur = cur->_right;			//在該結點的右子樹當中查找}else //找到了目標結點{return const_iterator(cur); //返回該結點}}return end(); //查找失敗}void InOrder(){_InOrder(_root);cout << endl;}// 根節點->當前節點這條路徑的黑色節點的數量bool Check(Node* root, int blacknum, const int refVal){if (root == nullptr){//cout << balcknum << endl;if (blacknum != refVal){cout << "存在黑色節點數量不相等的路徑" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "有連續的紅色節點" << endl;return false;}if (root->_col == BLACK){++blacknum;}return Check(root->_left, blacknum, refVal)&& Check(root->_right, blacknum, refVal);}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;//參考值int refVal = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refVal;}cur = cur->_left;}int blacknum = 0;return Check(_root, blacknum, refVal);}int Height(){return _Height(_root);}private:size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}//拷貝樹Node* _Copy(Node* root, Node* parent){if (root == nullptr){return nullptr;}Node* copyNode = new Node(root->_data);copyNode->_parent = parent;copyNode->_left = _Copy(root->_left, copyNode);copyNode->_right = _Copy(root->_right, copyNode);return copyNode;}//析構函數子函數void _Destroy(Node* root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}//左單旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;//建立subRL與parent之間的聯系parent->_right = subRL;if (subRL)subRL->_parent = parent;//建立parent與subR之間的聯系subR->_left = parent;parent->_parent = subR;//建立subR與parentParent之間的聯系if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}}//右單旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;//建立subLR與parent之間的聯系parent->_left = subLR;if (subLR)subLR->_parent = parent;//建立parent與subL之間的聯系subL->_right = parent;parent->_parent = subL;//建立subL與parentParent之間的聯系if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}}//左右雙旋void RotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}//右左雙旋void RotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}Node* _root; //紅黑樹的根結點	
};

正向迭代器的代碼

// 紅黑樹正向迭代器模板
// 模板參數:
//   T    - 結點數據類型
//   Ref  - 數據的引用類型
//   Ptr  - 數據的指針類型
template<class T, class Ref, class Ptr>
struct __TreeIterator 
{typedef Ref reference;    // 數據引用類型定義typedef Ptr pointer;      // 數據指針類型定義typedef RBTreeNode<T> Node;          // 紅黑樹結點類型typedef __TreeIterator<T, Ref, Ptr> Self;  // 迭代器自身類型Node* _node;  // 當前迭代器持有的結點指針// 構造函數// 參數://   node - 需要包裝的結點指針__TreeIterator(Node* node): _node(node)  // 初始化持有的結點指針{}// 解引用操作符（獲取數據引用）Ref operator*() {return _node->_data;  // 返回結點存儲數據的引用}// 箭頭操作符（獲取數據指針）Ptr operator->() {return &_node->_data;  // 返回指向結點數據的指針}// 不等比較操作符// 參數://   s - 要比較的迭代器// 返回值: 兩個迭代器是否指向不同結點bool operator!=(const Self& s) const {return _node != s._node;  // 直接比較結點指針}// 相等比較操作符// 參數://   s - 要比較的迭代器// 返回值: 兩個迭代器是否指向相同結點bool operator==(const Self& s) const {return _node == s._node;  // 直接比較結點指針}// 前置自增操作符（中序遍歷順序的下一個結點）Self operator++() {if (_node->_right)  // 當前結點存在右子樹{// 尋找右子樹的最左結點（右子樹中的最小結點）Node* left = _node->_right;while (left->_left) {left = left->_left;}_node = left;}else  // 當前結點沒有右子樹{// 向上尋找第一個不是右孩子的祖先結點Node* cur = _node;Node* parent = cur->_parent;// 沿著父指針向上查找，直到當前結點是父結點的左孩子while (parent && cur == parent->_right) {cur = parent;parent = parent->_parent;}_node = parent;  // 最終定位到的父結點即為后繼}return *this;}// 前置自減操作符（中序遍歷順序的前一個結點）Self operator--() {if (_node->_left)  // 當前結點存在左子樹{// 尋找左子樹的最右結點（左子樹中的最大結點）Node* right = _node->_left;while (right->_right) {right = right->_right;}_node = right;}else  // 當前結點沒有左子樹{// 向上尋找第一個不是左孩子的祖先結點Node* cur = _node;Node* parent = cur->_parent;// 沿著父指針向上查找，直到當前結點是父結點的右孩子while (parent && cur == parent->_left) {cur = parent;parent = parent->_parent;}_node = parent;  // 最終定位到的父結點即為前驅}return *this;}
};

反向迭代器的代碼

//反向迭代器---迭代器適配器
template<class Iterator>
struct ReverseIterator
{typedef ReverseIterator<Iterator> Self; //反向迭代器的類型typedef typename Iterator::reference Ref; //結點指針的引用typedef typename Iterator::pointer Ptr; //結點指針Iterator _it; //反向迭代器所封裝的正向迭代器//構造函數ReverseIterator(Iterator it):_it(it) //根據所給正向迭代器構造一個反向迭代器{}Ref operator*(){return *_it; //通過調用正向迭代器的operator*返回結點數據的引用}Ptr operator->(){return _it.operator->(); //通過調用正向迭代器的operator->返回結點數據的指針}//前置++Self& operator++(){--_it; //調用正向迭代器的前置--return *this;}//前置--Self& operator--(){++_it; //調用正向迭代器的前置++return *this;}bool operator!=(const Self& s) const{return _it != s._it; //調用正向迭代器的operator!=}bool operator==(const Self& s) const{return _it == s._it; //調用正向迭代器的operator==}
};

set的模擬實現

成員函數	功能
insert	插入指定元素
erase	刪除指定元素
find	查找指定元素
size	獲取容器中元素的個數
empty	判斷容器是否為空
clear	清空容器
swap	交換兩個容器中的數據
count	獲取容器中指定元素值的元素個數

#pragma once
#include"RBTree.h"namespace wh
{template<class K>class set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;			//正向迭代器typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器typedef typename RBTree<K, K, SetKeyOfT>::const_reverse_iterator const_reverse_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();}// 獲取反向起始迭代器（指向最后一個元素）reverse_iterator rbegin(){return _t.rbegin();}// 獲取反向結束迭代器（指向起始哨兵節點）reverse_iterator rend(){return _t.rend();}// 獲取反向起始迭代器（指向最后一個元素）const_reverse_iterator rbegin() const{return _t.rbegin();}// 獲取反向結束迭代器（指向起始哨兵節點）const_reverse_iterator rend() const{return _t.rend();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}// 刪除函數void erase(const K& key){_t.Erase(key);}// 查找函數const_iterator find(const K& key) const{return _t.Find(key);}// 獲取容器中元素的個數size_t size(){return _t.Size();}// 獲取容器中指定元素值的元素個數size_t count(const K& key) const{return _t.Find(key) != _t.end() ? 1 : 0;}// 判斷容器是否為空bool empty() const{return _t.Empty();}// 清空容器void clear(){_t.Clear();}void swap(set& other){_t.Swap(other._t);}private:RBTree<K, K, SetKeyOfT> _t;};
}

map的模擬實現

接口分類	接口名稱	作用
插入操作	`insert`	插入鍵值對，返回插入結果（迭代器 + 是否成功）。
	`emplace`	原地構造鍵值對，避免臨時對象拷貝。
	`operator[]`	通過鍵訪問值（若鍵不存在，插入默認值并返回引用）。
刪除操作	`erase`	刪除指定鍵或迭代器范圍內的鍵值對。
	`clear`	清空所有鍵值對。
查找與訪問	`find`	查找鍵，返回迭代器（未找到返回?`end()`）。
	`count`	返回鍵的數量（0 或 1）。
	`contains`?(C++20)	檢查鍵是否存在，返回布爾值。
	`at`	安全訪問值（鍵不存在時拋出異常）。
容量查詢	`empty`	檢查容器是否為空。
	`size`	返回鍵值對數量。
迭代器	`begin`?/?`end`	獲取正向迭代器（按鍵升序）。
	`rbegin`?/?`rend`	獲取反向迭代器（按鍵降序）。

#pragma once
#include"RBTree.h"namespace wh
{template<class K, class V>class map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};// 對類模板取內嵌類型，加typename告訴編譯器這里是類型typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_reverse_iterator const_reverse_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();}// 獲取反向起始迭代器（指向最后一個元素）reverse_iterator rbegin(){return _t.rbegin();}// 獲取反向結束迭代器（指向起始哨兵節點）reverse_iterator rend(){return _t.rend();}// 獲取反向起始迭代器（指向最后一個元素）const_reverse_iterator rbegin() const{return _t.rbegin();}// 獲取反向結束迭代器（指向起始哨兵節點）const_reverse_iterator rend() const{return _t.rend();}// 插入鍵值對// 參數: kv - 要插入的鍵值對// 返回值: 包含迭代器和插入結果的 pairpair<iterator, bool> insert(const pair<const K, V>& kv){return _t.Insert(kv);}// 下標訪問運算符重載// 參數: key - 要訪問的鍵// 返回值: 對應值的引用（若鍵不存在則自動插入默認值）V& operator[](const K& key){// 嘗試插入鍵值對（若存在則獲取已存在的元素）pair<iterator, bool> ret = insert(make_pair(key, V()));iterator it = ret.first;     // 獲取迭代器return it->second;            // 返回值的引用}// 刪除指定鍵的元素// 參數: key - 要刪除的鍵void erase(const K& key){_t.Erase(key);}// 查找指定鍵的元素// 參數: key - 要查找的鍵// 返回值: 指向元素的迭代器（若未找到則返回 end()）iterator find(const K& key){return _t.Find(key);}// 獲取容器中元素的個數size_t size(){return _t.Size();}// 獲取容器中指定元素值的元素個數size_t count(const K& key) const{return _t.Find(key) != _t.end() ? 1 : 0;}// 判斷容器是否為空bool empty() const{return _t.Empty();}// 清空容器void clear(){_t.Clear();}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}