【C++】：STL详解 —— 红黑树封装map和set

news/2025/3/10 23:51:50/

目录

红黑树的源代码

正向迭代器的代码

反向迭代器的代码

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


http://www.ppmy.cn/news/1578207.html

相关文章

【JAVA面试题】Spring、Spring MVC、Spring Boot、Spring Cloud的区别与联系

【JAVA面试题】Spring、Spring MVC、Spring Boot、Spring Cloud的区别与联系

在Java生态中&#xff0c;Spring框架及其衍生技术&#xff08;如Spring MVC、Spring Boot、Spring Cloud&#xff09;是开发企业级应用的核心工具。它们在功能、定位和使用场景上各有侧重&#xff0c;但又紧密联系。本文将详细解析它们的区别与联系&#xff0c;帮助你在面试中更…
阅读更多...
SpringCloud系列教程（十三）：Sentinel流量控制

SpringCloud系列教程（十三）：Sentinel流量控制

SpringCloud中的注册、发现、网关、服务调用都已经完成了&#xff0c;现在就剩下最后一部分&#xff0c;就是关于网络控制。SpringCloud Alibaba这一套中间件做的非常好&#xff0c;把平时常用的功能都集成进来了&#xff0c;而且非常简单高效。我们下一步就完成最后一块拼图Se…
阅读更多...
省市区数据最新json全国45380个省市区县乡镇街道

省市区数据最新json全国45380个省市区县乡镇街道

2025年01月10日更新&#xff0c;全国45380个省市区县乡镇街道&#xff0c;行政代码邮编代码json数据 包括北京市上海市天津市重庆市广东省广州市,韶关市,深圳市,珠海市,汕头市,佛山市,江门市,湛江市,茂名市,肇庆市,惠州市,梅州市,汕尾市,河源市,阳江市,清远市,东莞市,中山市,潮…
阅读更多...
Java 中数据脱敏的实现

Java 中数据脱敏的实现

数据脱敏 首先&#xff0c;要思考一个问题&#xff0c;SpringBoot 查询到的一条数据是一个 Java 对象&#xff0c;为什么返回给前端时候&#xff0c;前端拿到的却是 JSON 格式的数据呢&#xff1f; 是因为 SpringBoot 默认采用了 Jackson 作为序列化器&#xff0c;而 Jackson…
阅读更多...
第十五届蓝桥杯省赛电子类单片机学习过程记录（客观题）

第十五届蓝桥杯省赛电子类单片机学习过程记录（客观题）

客观试题： 01．典型的BUCK电源电路包含哪些关键器件（ABCD） A. 电容 B. 二极管 C. 电感 D. MOSFET 解析： 典型的 BUCK 电源电路是一种降压型的直流-直流转换电路，它包含以下关键器件： A.电容：电容在电路中起到滤波的作用。输入电容用于平滑输入电压的波动，减少电源噪声对…
阅读更多...
ArcGIS 工程文件到 ArcGIS Pro 的无缝迁移：详细步骤与技巧

ArcGIS 工程文件到 ArcGIS Pro 的无缝迁移：详细步骤与技巧

在地理信息系统&#xff08;GIS&#xff09;领域&#xff0c;ArcGIS 长期以来都是专业人士进行地图制作、空间分析和数据管理的重要工具。 随着技术的不断进步&#xff0c;Esri 公司推出了 ArcGIS Pro&#xff0c;这款新一代的 GIS 软件以其更强大的功能、更高效的性能和更直观…
阅读更多...
初识Bert

初识Bert

在学习Bert之前我们先了解“递归神经网络&#xff08;RNN Recurrent neural network)” 和 “长短期记忆&#xff08;LSTM Long short-term memory)” 我们如果仅仅识别每个字的含义&#xff0c;那么在一句话中没有相同的字还是可以的但是如果一句话中有相同的字&#xff0c;那…
阅读更多...
解释 HTTP 中的内容协商，如何根据客户端偏好返回合适的内容？

解释 HTTP 中的内容协商，如何根据客户端偏好返回合适的内容？

一、内容协商的本质与价值 内容协商&#xff08;Content Negotiation&#xff09;是HTTP协议中客户端与服务器就资源表现形式达成一致的协商机制。其核心价值在于&#xff1a;​用同一URI提供资源的不同表现形式&#xff0c;同时保证客户端获得最适合自身环境的内容版本。 典…
阅读更多...
最新文章

Copyright @ 2022~2023