文章目录
-
- ?? map与set介绍
- ?? map与set的基础结构
- ?? 红黑树的再修改
-
- ??节点及树的定义
- ??KeyOfValue的使用
- ??插入函数
- ??析构函数
- ??红黑树完整代码(供参考)
- ?? 迭代器的实现
-
- ??迭代器的定义
- ??迭代器中成员函数的实现
- ??迭代器完整代码[不含迭代器] (供参考)
- ?? set的封装及代码(供参考)
- ?? map的封装及代码(供参考)
?? map与set介绍
它们是一种树形数据结构的容器,且其的底层构造为一棵红黑树;
而在上一篇文章中提到,其实红黑树本身就是一棵二叉搜索树,是基于二叉搜索树的性质对其增加了平衡的属性来提高其综合性能(包括增删查改);
当然也提到了红黑树与AVL树的区别:
-
AVL树
AVL树是一棵高度平衡搜索二叉树,其特点即为在搜索二叉树的基础上根据控制结构达到了最终的属性;
即为,每一个节点的左右子树的高度差不超过1;
-
红黑树
红黑树是一棵近似平衡的二叉树,其特点为根据树的颜色 (红色或是黑色),以制定了一系列的规则使得树能够达到最终的效果;
即为每条最长路径的长度不超过最短路径的2倍;
-
当然为什么
map 与set 容器所使用的数据结构为红黑树而不是AVL树?最简单的原因其实是因为对于AVL树来说,既然要维持高度平衡,那么必定会在少次插入过后以特定的操作(旋转操作)来使得树在不符合规则时对其进行调整从而恢复平衡状态,虽然在查找方面有着绝对的优势,但是在大量的旋转操作后必定会使整体的效率变慢;
而对于红黑树来说,红黑树虽然也是一棵平衡搜索二叉树,但是它允许树中的节点不为高度平衡而是为近似平衡
最长路径的长度不超过最短路径的二倍 ,这使得红黑树允许多次进行插入而少量的进行旋转操作;-
那么既然相对AVL树在结构上的平衡高于红黑树,那么在整体效率当中谁更胜一筹?
当然,以单单的查找为例;
AVL树的最终深度保持在了
logN ,其中N 为数中节点的个数;对于红黑树而言,红黑树允许了最长节点长度不超过最短节点的二倍的原因,其最终的深度控制在了
2logN 以内,其时间复杂度也相当(可以看作是logN );举个例子,假设两棵都存在
10亿 个节点,分别为AVL树与红黑树,当查找同一个节点时,AVL树只需要查找30次 ,而红黑树最多需要查找60次 ;然而由于当前CPU的性能而言,查找30次的速度可以与查找60次的速度相当;
又因为红黑树在插入过程中需要处理的次数大大少于AVL树,故以综合性能而言,红黑树大于AVL树;
-
故在多数场景的使用中红黑树的使用频率要大于AVL树;
当然既然他们的底层都是平衡搜索二叉树,当然他们所对应的容器也必定有着对应的功能,即排序(搜索二叉树又被称为排序二叉树)与去重;
?? map与set的基础结构
在
而对于
所以可能会联想到在
而实际在
-
map
//... private: typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; // red-black tree representing map -
set
//... private: typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;///模板参数传参 rep_type t; // red-black tree representing set /*template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>//*/
以上的两段代码是来自
其中两个容器都使用了同一棵红黑树;
- 那么既然是同一棵红黑树,应该如何对这棵树进行修改使得该树能够满足对于
map 容器而言可以进行对应的key ,value 数据的存储与管理,而set 容器可以进行单纯的key 数据的存储与管理?
?? 红黑树的再修改
在上文之中提到,若是以上一篇文章为例子来实现红黑树的话,则对于
而实际上在
-
那么如何对红黑树进行修改来使得其能够通过泛型来同时作用于(封装)两个容器?
struct __rb_tree_node_base { //红黑树节点的定义 typedef __rb_tree_color_type color_type; typedef __rb_tree_node_base* base_ptr; color_type color; base_ptr parent; base_ptr left; base_ptr right; /*...*/ } template <class Value> struct __rb_tree_node : public __rb_tree_node_base { //定义一个新的类为__rb_tree_node_base,并且继承原先节点的定义__rb_tree_node typedef __rb_tree_node<Value>* link_type; Value value_field; /*...*/ }; template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>// class rb_tree { typedef rb_tree_node* link_type; protected: //... link_type header; //整棵树的定义 /*...*/ };该段代码为在
STL 中的红黑树与其的定义,其中可以看出对于红黑树节点的定义来说使用的是一种继承的方法,主要是定义一个基类__rb_tree_node_base 并用派生类__rb_tree_node 继承该基类;同时再继承过后通过
tytpedef 重命名了派生类__rb_tree_node* 的节点指针为link_type ,并设置头节点为header ;从整棵树的定义中可以看到,一共有五个模板参数,分别为
Key ,Value ,KeyOfValue ,Compare ,Alloc = alloc ;这五个模板参数分别对应的是:
-
Key 该模板参数参数用于传递
key 数据的类型; -
Value 该模板参数用于传递
value 数据的类型; -
KeyOfValue 该模板参数为一个仿函数,通过该仿函数可以达到使得
map 与set 间虽然所存的数据不同但是能在一些场景下(例如比较)使其能够进行相同的操作;这个模板参数也是该问题中的核心部分;
-
Alloc 该模板参数用来传入一个内存分配器,在此不做过多说明;
-
那么可以根据这个模板参数来从两个容器的源码当中来追溯参数的传递:
-
map #ifndef __STL_LIMITED_DEFAULT_TEMPLATES template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> #else template <class Key, class T, class Compare, class Alloc = alloc> #endif class map { public: // typedefs: typedef Key key_type; typedef T data_type; typedef T mapped_type; typedef pair<const Key, T> value_type; typedef Compare key_compare; //... }; private: typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; // red-black tree representing map从该段代码当中可以看到对于
map 而言其对于key ,value 模型中传递了对应的参数分别为key_type ,value_type ;且从中可以看出对于其中的
value_type 而言,map 容器所传递给红黑树的参数为一个pair<const Key, T> ;而其中的
Key 与T 即为所传递的参数;map 将所传递的参数用于两个用途,其中一个是封装为一个pair<const Key ,T> 传递给红黑树用于数据的管理;另一个直接将
Key 作为单独的参数(key_type )传递给红黑树当中的Key 用于其他部分中可能出现的其他操作(例如查找); -
set #ifndef __STL_LIMITED_DEFAULT_TEMPLATES template <class Key, class Compare = less<Key>, class Alloc = alloc> #else template <class Key, class Compare, class Alloc = alloc> #endif class set { public: // typedefs: typedef Key key_type; typedef Key value_type; typedef Compare key_compare; typedef Compare value_compare; private: typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;///模板参数传参 rep_type t; // red-black tree representing set /*template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>//*/而对于
set 而言,传递给红黑树当中的Key ,Value 时传递的参数同样为key_type 与value_type ;但唯一有一点不同的是,对于
set 而言,其中的key_type 与value_type 都是由Key 进行typedef 重命名而来,以此可以得知,实际上为了实现两个容器共用同一棵红黑树,对于set 而言其传递一个冗余的参数; -
那么当需要进行比较操作时,红黑树如何以泛型的属性来达到既可以比较
map 中的key ,value ,又能够比较set 中的key ?在上文中提到了一个仿函数为
KeyOfValue ,该仿函数是从map 与set 容器中传递给红黑树当中的;当然其定义也在对应的容器定义当中;
-
set typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;///模板参数传参对于
set 而言它的仿函数为identity<value_type> ,它的底层实现类似于:template <class T> struct identity { const T& operator()(const T& x) const { return x; } };即返回对应的
key 值即可; -
map typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;而对于
map 容器来说它的仿函数为select1st<value_type> ;其底层的实现类似于:
template <class Pair> struct select1st { const typename Pair::first_type& operator()(const Pair& x) const { return x.first; } };由于其传值对应的
Value 中传递的是一个pair 类型,所以可以使map 容器通过仿函数来获取pair 数据结构中的key 值;这也使得两个容器可以适用于同一棵红黑树;
-
当然在实际过程中
??节点及树的定义
在上文中提到,若是需要实现两个容器同时使用同一棵红黑树就得对先前的红黑树进行对应的修改;
首先是节点以及树的定义;
对于节点与树的定义来说可修改的内容不是特别的多,需要修改的为:
-
KeyOfValue 在
STL 的红黑树当中新增了一个模板参数为KeyOfValue 使得两个容器都能获取到其对应的key 值; -
节点的模板参数
在原先的红黑树的模板参数当中所传递的是一个
Key ,Value 的模型,而在该处需要修改为对应的T ,根据T 来传递对应的参数,若是set 对应所传递的即为其中的Key ;若是map ,所传递的即为对应的pair<key,value> ;
enum COLOR{
RED,
BLACK
};
template<class T>
struct RBTreeNode{
RBTreeNode<T> *_left;
RBTreeNode<T> *_right;
RBTreeNode<T> *_parent;
T _data;
COLOR _col;
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)
{}
};
template<class K,class T,class KeyOfT>
class RBTree{
public:
KeyOfT kot; // KeyOfT
typedef RBTreeNode<T> Node;
//....
private:
Node* _root = nullptr;
};
而对于其
??KeyOfValue的使用
只需要对其进行实例化并且在需要的地方进行使用即可;
KeyOfT kot; // KeyOfT
??插入函数
在
若是插入成功则返回新插入节点的迭代器(迭代器的实现将在下文中提到)位置与
若是插入失败则返回需要插入的数据相同的节点位置与
当然其对于插入时需要进行的旋转逻辑以及变色逻辑都不变;
pair<iterator,bool> Insert(const T &data) {
if(_root == nullptr){
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
Node *cur = _root;
Node *parent = nullptr;
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(iterator(cur), false);
}
}
Node* newnode = new Node(data);
cur = newnode;
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(grandfather->_left == parent){
Node *uncle = grandfather->_right;
if(uncle && uncle->_col == RED){
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else{
// if(uncle == nullptr || uncle->_col == BLACK)
if(cur == parent->_left){
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else{ // cur == parent->_left
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else{
// if(grandfather->_right == parent){
Node *uncle = grandfather->_left;
if (uncle && uncle->_col == RED){
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else{
// if(uncle == nullptr || uncle->_col == BLACK)
if(cur == parent->_right){
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
??析构函数
红黑树的析构函数与普通二叉树的析构函数相同,只需要创建一个
void _Destory(Node* &root){
if(root == nullptr){
return ;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
root = nullptr;
}
~RBTree() {
_Destory(_root);
}
??红黑树完整代码(供参考)
#include<iostream>
#include<vector>
enum COLOR{
RED,
BLACK
};
template<class T>
struct RBTreeNode{
RBTreeNode<T> *_left;
RBTreeNode<T> *_right;
RBTreeNode<T> *_parent;
T _data;
COLOR _col;
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)
{}
};
protected:
private:
Node *_node;
};
template<class K,class T,class KeyOfT>
class RBTree{
public:
KeyOfT kot; // KeyOfT
typedef RBTreeNode<T> Node;
typedef __RBTree_Iterator<T, T &, T *> iterator;
typedef __RBTree_Iterator<T, const T &, const T *> const_iterator;
iterator begin(){
Node* cur = _root;
while(cur && cur->_left){
cur = cur->_left;
}
return iterator(cur);
}
iterator end(){
return iterator(nullptr);
}
~RBTree() {
_Destory(_root);
}
Node *Find(const K &key){
Node* cur = _root;
while(cur){
if(key>kot(cur->_data)){
cur = cur->_right;
}
else if (key < kot(cur->_data))
{
cur = cur->_left;
}
else{
return cur;
}
}
return nullptr;
}
pair<iterator,bool> Insert(const T &data) {
if(_root == nullptr){
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
Node *cur = _root;
Node *parent = nullptr;
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(iterator(cur), false);
}
}
Node* newnode = new Node(data);
cur = newnode;
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(grandfather->_left == parent){
Node *uncle = grandfather->_right;
if(uncle && uncle->_col == RED){
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else{
// if(uncle == nullptr || uncle->_col == BLACK)
if(cur == parent->_left){
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else{ // cur == parent->_left
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else{
// if(grandfather->_right == parent){
Node *uncle = grandfather->_left;
if (uncle && uncle->_col == RED){
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else{
// if(uncle == nullptr || uncle->_col == BLACK)
if(cur == parent->_right){
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
bool IsBalance(){
if(_root == nullptr){
return true;
}
if(_root && _root->_col == RED){
return false;
}
std::pair<bool,std::vector<int>> ret ;
ret.first = true;
_Check(ret,_root,0);
if(!ret.first){
std::cout << "某一路径出现连续红色节点" << std::endl;
}
bool to_comp = true;
size_t _comp = ret.second[0];
for(auto &it : ret.second){
if(it != _comp){
to_comp = false;
break;
}
std::cout << it << std::endl;
}
return to_comp && ret.first;
}
int getHeight()
{
return getHeight(_root);
}
protected:
void RotateL(Node *parent){
Node *cur = parent->_right;
Node *curleft = cur->_left;
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
cur->_left = parent;
Node *ppnode = parent->_parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
void RotateR(Node *parent){
Node *cur = parent->_left;
Node *curright = cur->_right;
parent->_left = curright;
if (curright)
curright->_parent = parent;
Node *ppnode = parent->_parent;
cur->_right = parent;
parent->_parent = cur;
if (ppnode == nullptr)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
void _Check(std::pair<bool,std::vector<int>> &ret,Node *root,size_t blackNum = 0){
if(root == nullptr){
ret.first = ret.first && true;
ret.second.push_back(blackNum);
return;
}
if(root->_col == RED && root->_parent->_col == RED){
ret.first = ret.first && false;
return ;
}
if(root->_col == BLACK){
blackNum++;
}
_Check(ret, root->_left, blackNum);
_Check(ret, root->_right, blackNum);
}
int getHeight(Node *root)
{
if (root == nullptr)
{
return 0;
}
int left = getHeight(root->_left);
int right = getHeight(root->_right);
return left > right ? left + 1 : right + 1;
}
void _Destory(Node* &root){
if(root == nullptr){
return ;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
root = nullptr;
}
private:
Node* _root = nullptr;
};
?? 迭代器的实现
而红黑树的迭代器是单独进行封装的;
主要的接口即为:
- 需要对迭代器进行对应的遍历所需要的
operator++() 与operator--() ; - 用于比较(可以用来终止遍历)的
operator!=() ; - 用于将节点的指针来构造出迭代器的构造函数;
- 将迭代器进行解引用的
operator->() 与operator*() ;
在该篇博客中的迭代器实现将着重以上述的几个接口作为主要接口进行实现;
??迭代器的定义
template <class T, class Ref /*数据的引用*/, class Ptr /*数据的地址*/> // 迭代器的实现
class __RBTree_Iterator
{
typedef __RBTree_Iterator<T, Ref, Ptr> Self;
typedef RBTreeNode<T> Node;
public:
__RBTree_Iterator(Node *node)//构造函数
: _node(node)
{}
Ref operator*();
Ptr operator->();
Self& operator++();
Self operator++(int);
Self& operator--();
Self operator--(int);
bool operator!=(const Self &s);
protected:
private:
Node *_node;
};
红黑树的迭代器主要为封装其中红黑树的节点作为迭代器,并再封装之后对其设置其他的功能;
其构造函数只需要对其中的红黑树的节点进行初始化即可;
在该迭代器当中传入了几个模板参数分别为
其中:
-
Ref 为引用主要的功能是通过引用能够实现
operator*() 中能通过* 来获取节点中的数据(可能为key 也可能为pair ); -
Ptr 为指针由于迭代器中具有
-> 的功能,即为通过指针来指向节点中的值,能够实现通过迭代器的-> 来指向迭代器中的数据;
??迭代器中成员函数的实现
-
Ref operator*() 对于该函数而言,由于返回的是引用,所以只需要根据节点指针来返回其中对应的值即可;
若是
key 则返回key ,若是pair 则返回对应的pair ,当然这已经依靠泛型从而得到解决;Ref operator*() { return _node->_data; } -
Ptr operator->() 对于该函数而言,其返回的是指针指向的数据,但是在C++中,若是重载其中的
-> 符号时所得的依旧是个指针,则将会得到编译器的优化;编译器将会通过这个指针再去指向下一层的数据;
Ptr operator->() { return &_node->_data; }以该函数而言,其取到的是节点中数据的地址;
若是
set 时,该函数将返回的是其中key 数据的地址,而经过编译器优化-> 将能够直接取到其中的值;对于
map 而言也是如此,将会取到其中pair 的值; -
Self& operator++() 与Self operator++(int) 对该函数而言也是较为复杂的函数;
该函数的思路即为手撕出红黑树的遍历方式;
以中序遍历的思路而言,对于中序遍历来说,一棵树的最左侧节点即为一棵树中迭代器的
begin 位置;
以该图为例,该图中的节点
1 即为该红黑树迭代器begin 的位置;而对于
++ 而言,需要思考如何通过该节点而去遍历下一个节点;最简单的思路即为:
-
设置一个
cur 节点与parent 节点,其中cur 节点为当前节点,parent 节点即为当前节点的父亲节点;以这两个节点进行遍历
-
cur 节点的右子树存在当该节点的右子树存在时,下一个节点即为该节点右子树的最左侧节点;
同时在遍历的过程中应该更新其节点;
-
cur 节点的右子树不存在当
cur 节点的右子树不存在时则说明原先的右子树已经被遍历完毕;那么下一个节点即为
cur 节点不为parent 节点右侧节点的情况中的parent 节点,以此类推; -
代码片段:
Self& operator++()//前置++ { Node* cur = _node; if(cur->_right){ cur = cur->_right; while (cur->_left){ cur = cur->_left; } _node = cur; } else{ Node *parent = cur->_parent; while(parent && cur==parent->_right){ cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; }
对于
Self operator++(int) 函数而言只需要调用operator++() 即可;-
代码段
Self operator++(int){//后置++ Node* cur = _node; ++*this; return Self(cur); }
-
-
Self& operator--() 与Self operator--(int) 该函数的思路即为
operator++() 思路相反即可;在此不作过多赘述;
-
代码段
Self& operator--() { Node* cur = _node; if(cur->_left){ cur = cur->_left; while(cur->_right){ cur = cur->_right; } _node = cur; } else{ Node *parent = cur->_parent; while(parent && cur == parent->_left){ cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; } Self operator--(int) { Node *cur = _node; --*this; return Self(cur); }
-
-
bool operator!=(const Self &s) 该函数只需要判断其中的数据是否相同即可;
-
代码段
bool operator!=(const Self &s) { return _node != s._node; }
-
??迭代器完整代码[不含迭代器] (供参考)
template <class T, class Ref /*数据的引用*/, class Ptr /*数据的地址*/> // 迭代器的实现
class __RBTree_Iterator
{
typedef __RBTree_Iterator<T, Ref, Ptr> Self;
typedef RBTreeNode<T> Node;
public:
__RBTree_Iterator(Node *node)
: _node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()//前置++
{
Node* cur = _node;
if(cur->_right){
cur = cur->_right;
while (cur->_left){
cur = cur->_left;
}
_node = cur;
}
else{
Node *parent = cur->_parent;
while(parent && cur==parent->_right){
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self operator++(int){//后置++
Node* cur = _node;
++*this;
return Self(cur);
}
Self& operator--()
{
Node* cur = _node;
if(cur->_left){
cur = cur->_left;
while(cur->_right){
cur = cur->_right;
}
_node = cur;
}
else{
Node *parent = cur->_parent;
while(parent && cur == parent->_left){
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self operator--(int)
{
Node *cur = _node;
--*this;
return Self(cur);
}
bool operator!=(const Self &s)
{
return _node != s._node;
}
protected:
private:
Node *_node;
};
?? set的封装及代码(供参考)
对于
#include "RBTree.hpp"
enum COLOR;
namespace MYSTL
{
template<class K>
class Set
{
struct setKeyOfT
{
const K &operator()(const K &key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, setKeyOfT>::iterator iterator;
//typedef类模板的时候需要加上typename ,否则编译器不知道typedef的是类型还是成员变量
std::pair<iterator,bool> Insert(const K& key){
pair<iterator,bool> ret = _rbt.Insert(key);
return ret;
}
iterator begin(){
return _rbt.begin();
}
iterator end(){
return _rbt.end();
}
protected:
private:
RBTree<K , K , setKeyOfT> _rbt;
// 模板参数传入两个参数都为K
};
?? map的封装及代码(供参考)
对于
唯独不同的是,在
-
插入功能
若是该数据对应的
key 不存在,则将该数据进行插入,并返回其value ; -
读取功能
若是该数据对应的
key 存在,则不对该数据进行插入,直接返回存在数据的value 值;
要实现上述功能只需要在
-
代码段
V& operator[](const K& key){ std::pair<iterator,bool> ret = _rbt.Insert(std::make_pair(key,V())); return ret.first->second; } -
完整代码:
#include "RBTree.hpp" enum COLOR; namespace MYSTL{ template<class K,class V> class Map{ struct mapKeyOfT{ const K &operator()(const std::pair<const K, V> &kv) { return kv.first; } }; public: typedef typename RBTree<K, std::pair<const K, V>, mapKeyOfT>::iterator iterator; // typedef类模板的时候需要加上typename ,否则编译器不知道typedef的是类型还是成员变量 pair<iterator, bool> Insert(const std::pair<const K, V> &kv) { pair<iterator,bool> ret = _rbt.Insert(kv); return ret; } iterator begin(){ return _rbt.begin(); } iterator end(){ return _rbt.end(); } V& operator[](const K& key){ std::pair<iterator,bool> ret = _rbt.Insert(std::make_pair(key,V())); return ret.first->second; } protected: private: RBTree<K , std::pair<const K,V> , mapKeyOfT> _rbt; //模板参数传入两个参数分别为K类型的数据与pair };