东莞做网站网络公司,网站系统怎么做的,网站制作 火星科技,盘州电子商务网站建设目录 红黑树的源代码
正向迭代器的代码
反向迭代器的代码
set的模拟实现
map的模拟实现 红黑树的源代码
#pragma once
#include iostreamusing namespace std;
// set -key
// map -key/value// set -key
// map -key/valueenum Colour
{RED,BLAC…目录 红黑树的源代码
正向迭代器的代码
反向迭代器的代码
set的模拟实现
map的模拟实现 红黑树的源代码
#pragma once
#include iostreamusing namespace std;
// set -key
// map -key/value// set -key
// map -key/valueenum Colour
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};// 红黑树正向迭代器模板
// 模板参数:
// T - 结点数据类型
// Ref - 数据的引用类型
// Ptr - 数据的指针类型
templateclass T, class Ref, class Ptr
struct __TreeIterator
{typedef RBTreeNodeT Node; // 红黑树结点类型typedef __TreeIteratorT, 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;}
};//反向迭代器---迭代器适配器
templateclass Iterator
struct ReverseIterator
{typedef ReverseIteratorIterator 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-RBTreeK, K, SetKeyOfT _t;
// map-RBTreeK, pairconst K, T, MapKeyOfT _t;
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef __TreeIteratorT, T, T* iterator; //正向迭代器typedef __TreeIteratorT, const T, const T* const_iterator;typedef ReverseIteratoriterator reverse_iterator; //反向迭代器typedef ReverseIteratorconst_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 RBTreeK, T, KeyOfT t){_root _Copy(t._root, nullptr);}//赋值运算符重载现代写法RBTreeK, T, KeyOfT operator(RBTreeK, 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);}//pairiterator, bool Insert(const T data)pairNode*, 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 - 数据的指针类型
templateclass T, class Ref, class Ptr
struct __TreeIterator
{typedef Ref reference; // 数据引用类型定义typedef Ptr pointer; // 数据指针类型定义typedef RBTreeNodeT Node; // 红黑树结点类型typedef __TreeIteratorT, 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;}
};
反向迭代器的代码
//反向迭代器---迭代器适配器
templateclass Iterator
struct ReverseIterator
{typedef ReverseIteratorIterator 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
#includeRBTree.hnamespace wh
{templateclass Kclass set{public:struct SetKeyOfT{const K operator()(const K key){return key;}};typedef typename RBTreeK, K, SetKeyOfT::iterator iterator; //正向迭代器typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;typedef typename RBTreeK, K, SetKeyOfT::reverse_iterator reverse_iterator; //反向迭代器typedef typename RBTreeK, 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();}pairiterator, 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:RBTreeK, K, SetKeyOfT _t;};
}
map的模拟实现
接口分类接口名称作用插入操作insert插入键值对返回插入结果迭代器 是否成功。emplace原地构造键值对避免临时对象拷贝。operator[]通过键访问值若键不存在插入默认值并返回引用。删除操作erase删除指定键或迭代器范围内的键值对。clear清空所有键值对。查找与访问find查找键返回迭代器未找到返回 end()。count返回键的数量0 或 1。contains (C20)检查键是否存在返回布尔值。at安全访问值键不存在时抛出异常。容量查询empty检查容器是否为空。size返回键值对数量。迭代器begin / end获取正向迭代器按键升序。rbegin / rend获取反向迭代器按键降序。
#pragma once
#includeRBTree.hnamespace wh
{templateclass K, class Vclass map{public:struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};// 对类模板取内嵌类型加typename告诉编译器这里是类型typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::const_iterator const_iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::reverse_iterator reverse_iterator;typedef typename RBTreeK, pairconst 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 - 要插入的键值对// 返回值: 包含迭代器和插入结果的 pairpairiterator, bool insert(const pairconst K, V kv){return _t.Insert(kv);}// 下标访问运算符重载// 参数: key - 要访问的键// 返回值: 对应值的引用若键不存在则自动插入默认值V operator[](const K key){// 尝试插入键值对若存在则获取已存在的元素pairiterator, 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:RBTreeK, pairconst K, V, MapKeyOfT _t;};
}
