【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;};
}