STL容器——使用红黑树模拟实现map和set（由浅入深逐步完善3w字详解）
前言
【c++】红黑树的概念讲解与模拟实现、红黑树与AVL树的比对（2万字详解）——书接上文 详情请点击<——
本文由小编为大家介绍——【c++】STL容器——使用红黑树模拟实现map和set
在阅读本文前，由于本文map和set是基于红黑树的基础上封装出来的，所以请读者友友务必了解清楚红黑树的模拟实现，关于红黑树的模拟实现如果不熟悉的读者友友，请读者友友务必点击后方蓝字链接进行学习， 详情请点击<——
一、了解STL库中的map/set的底层
map和set是通过红黑树封装实现的，我们首先学习一下STL库中是如何通过封装红黑树实现的map/set，下面的代码为了便于讲解，小编只截取部分进行讲解
观察下面代码，STL库中的set中封装了一个类模板红黑树rb_tree的对象rep_type，传入了key_type, value_type，这两个的类型都是Key类型的，奇怪，在小编前面文章的讲解中，set是key结构，只用存储一个key就可以，为什么这里传入了两个key，继续向下阅读，小编会在后文进行解读
template <cla.ybdm.pro/ss Key, class Co.ybdm.pro/mpare = less<Key>, class Alloc = alloc>
class set {
public:
// typ.ybdm.pro/edefs:
typedef Key key_type;
typedef Key value_type;
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 Compare = less<Key>, class Alloc = alloc>
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
}
观察下面代码，STL库中的map中封装了一个类模板红黑树rb_tree的对象rep_type，传入了key_type, value_type，而key_type是key类型，value_type却是一个pair<const Key, T>类型的，按我们的预想value_type不应该是value(T)类型的吗？在小编之前文章的讲解中，讲解map是key_value结构的，map只需要存储key，value即可，为什么这里却传入了一个key和一个pair<const Key, T>进行实例化呢？继续向下阅读，小编会在后文进行解读
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
typedef Key key_type;
typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_ty.ybdm.pro/pe, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
}
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
typedef Key key_type;
type.ybdm.pro/def pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, All.ybdm.pro/oc> rep_type;
rep_type t; // red-bla.ybdm.pro/ck tree representing map
}
观察下面代码，STL库中关于红黑树rb_tree的实现，我们可以看到在struct类模板__rb_tree_node中是对于节点的定义，其中使用了模板参数Value去定义了节点中实际存储的内容，而没有使用key去定义，其实这是由于在STL库中设计的时候，在红黑树rb_tree的实现中使用第二个模板参数作为节点中实际存储的值
例如map传入<Key,pair<Key,Value>>，那么map中的红黑树类模板实例化出的红黑树中就使用传入红黑树的第二个模板参数pair<Key,Value>去定义节点中实际存储的内容，同样的set传入<Key,Key>，那么set中的红黑树类模板实例化出的红黑树中就使用传入红黑树的第二个模板参数Key去定义节点中实际存储的内容，那么这样的好处是什么呢？为什么map/set中还要多传入第一个模板参数Key呢？
其实STL库中是考虑了泛型模板，因为map和set在使用以及底层实现上都高度相似，如果不这样进行设计，那么我们就要写一份key_value结构的红黑树实现map，再写一份key结构的红黑树实现set，其中这两份红黑树的代码又高度吻合，在STL库中是不会这样设计的，它会考虑使用泛型模板，即让map和set使用同一份类模板，可以传入不同的模板参数，实例化出不同的类型
那么既然有了存储类型，为什么map/set中还要多传入第一个模板参数Key呢，其实这是为了例如find，erase这样的函数进行设计，find和erase是要使用key值进行查找或删除的，因为如果你仅仅有存储的类型那么对于set是可以使用存储的类型key去定义find和erase的函数参数，因为set的存储类型和key值都是key，但是对于map则不行，因为map中实际存储的是pair<key,value>，如果不显示传入Key，那么map的find和erase将会无法定义对应的函数参数，也就无法进行设计了，所以可以说第一个模板参数key是必须存在的，可以说是特定的为map进行设计，由于set也要和map共用一个类模板rb_tree，所以也要传入key
template <class Key, class Valu.ybdm.pro/e, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protected:
typedef __rb_tree_node<Valu.ybdm.pro/e> rb_tree_node;
typede.ybdm.pro/f rb_tree_node* link_type;
protected:
link_type head.ybdm.pro/er;//定义的节点指针
}
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_no.ybdm.pro/de<Value>* link_type;
Value value_field;//节点中实际存储的值
};
template <class Key, class Valu.ybdm.pro/e, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protected:
typedef __rb_tree_node<Value> rb_tree_node;
type.ybdm.pro/def rb_tree_node* lin.ybdm.pro/k_type;
protected:
link_type header;//定义的节点指针
}
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;//节点中实际存储的值
};
二、红黑树的迭代器
由于本文是基于红黑树的模拟实现进行讲解的，所以小编模拟实现的红黑树的源代码小编会直接拿来进行使用，关于红黑树的源代码小编已经放在后方蓝字的文章中的第五点 详情请点击<——
我们知道map/set中支持了迭代器进行遍历，那么我们实现一下红黑树的迭代器，让map/set封装一下红黑树的迭代器就可以进行使用
原红黑树小编是设计的key_value结构，由于小编要将红黑树改进成可以让map/set都进行使用，所以就将红黑树的原模板参数template<typename K, typename V>其中的K表示key，V表示value，那么小编将原模板参数改进成template<typename K, typename T>，其中表示第一个模板参数是Key，为了和V进行区分，小编将第二个模板参数设计为T，表示类型type，即红黑树节点中存储的类型T，如果是map，那么第二个模板参数就对应为pair<key,value>，表示红黑树节点中实际存储pair<key,value>，如果是key，那么第二个模板参数就对应key，表示红黑树节点中实际存储key
同时由于红黑树的模板参数更改那么红黑树的节点的类型就要修改了，由于修改后红黑树的节点中存储的是T类型，那么节点的模板参数以及对应的一些节点类型就要更改，为了区分，在红黑树的节点中，那么我们存储的内容就使用T类型定义一个成员变量_data，对应更改如下，同时由于节点的类型已经被我们修改，所以在红黑树中对节点类型的typedef要更改为typedef RBTreeNode<T> Node;
template<typename T>
struct RBTreeNode
{
T _data;
RBTree.zpia.pro/Node<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _pare.zpia.pro/nt;
Colour _col;
RBTreeNod.zpia.pro/e(const T& data)
:_data(data)
,_left(nullptr)
,_right(nu.zpia.pro/llptr)
,_par.zpia.pro/ent(nullptr)
,_col(RE.zpia.pro/D)
{}
};
template<typename K, typename T>
class RBTree
{
typedef RBTree.zpia.pro/Node<T> Node;
public:
RBTree()
:_root(nul.zpia.pro/lptr)
{}
private:
Node* _root;
};
template<typena.zpia.pro/me T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _par.zpia.pro/ent;
Colour _col;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_pa.zpia.pro/rent(nullptr)
,_col(RED)
{}
};
template<typename K, typename T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
RBTree()
:_root(nullptr)
{}
priva.yaii.pro/te:
Node* _root;
};
那么我们要模拟实现红黑树的普通迭代器__RBTree_itarator，由于迭代器的成员要经常被访问，所以我们就使用struct定义类模板__RBTree_itarator，类似的红黑树的迭代器和链表中的迭代器类似都是封装了一个节点的指针，使用迭代器去模拟指针的行为，关于链表的迭代器的讲解请点击后方蓝字链接 详情请点击<——
红黑树同样也是封装节点的指针，那么节点的使用需要使用到模板参数T，那么我们就给迭代器一个模板参数T，为了便于对节点进行使用，使用typedef将节点的类型RBTreeNode|重命名为Node，同时为了便于对迭代器类型的使用，使用typedef将迭代器的类型__RBTree_itarator重命名为Self，使用节点的指针Node*定义节点节点的指针_node
迭代器的构造函数，由于红黑树的迭代器中存储的是一个节点的指针_node，那么我们就在构造函数的参数中接收一个节点的指针node在初始化列表中完成对红黑树迭代器中节点的指针_node的初始化即可
运算符重载函数operator*，那么直接使用节点的指针访问节点中存储的内容_data，返回即可，返回值是T&，由于节点中存储的内容_data在出了这个函数仍然存在，所以我们可以直接返回类型的引用
运算符重载函数operator->，那么先使用节点的指针取出节点中存储的内容_data，接下来我们使用取地址操作符&即可取出节点中存储内容_data的地址了，即存储内容的指针，返回即可，返回值是存储内容的指针T*
运算符重载函数operator!=，那么接收迭代器即可，由于我们不修改，所以使用const修饰迭代器，由于迭代器出了函数仍然存在，所以我们可以使用引用接收，那么比较迭代器是否不想等，那么比较迭代器中节点的指针使用不想等即可完成比较
运算符重载函数operator++，原理如下，当++完成之后，由于迭代器++之后还是一个迭代器，所以运算符重载函数++的返回值应该还是迭代器，并且由于迭代器出了函数仍然存在，所以返回值的类型设定为迭代器的引用，此时this指针指向的就是当前++之后的迭代器，返回this指针的解引用即可
11. 运算符重载函数operator- -，原理如下
template<typename T>
struct __RBTree_itarator
{
typed.yaii.pro/ef RBTr.yaii.pro/eeNode<T> Node;
typedef __RBT.yaii.pro/ree_itarator<T> Self;
Node* _node;
__RBTree_itarator(Node* node)
:_node(node)
{}
T& opera.yaii.pro/tor*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool opera.yaii.pro/tor!=(const Self& it)
{
return _node != it._node;
}
Self& operator--()
{
Node* cur = _node;
Node* par.yaii.pro/ent = cur->_parent;
if (cur->_left)
{
Node* LeftM.yaii.pro/ax = cur->_left;
while (LeftMax->_right)
{
LeftMax = LeftMax->_right;
}
_node = LeftMax;
}
else
{
while (paren.yaii.pro/t && cur == parent->_left)
{
cur = parent;
parent = parent->_pa.yaii.pro/rent;
}
_node = parent;
}
return *this;
}
Self& oper.yaii.pro/ator++()
{
Node* cur = _node;
Node* parent = cur->_parent;
if(cur->_right)
{
Node* RightMin = cur->_right;
while (RightMin->_left)
{
RightMin = Right.zodl.pro/Min->_left;
}
_node = Rig.zodl.pro/htMin;
}
else
{
while (pare.zodl.pro/nt && cur == parent->_right)
{
cur = parent;
parent = parent->_pare.zodl.pro/nt;
}
_node = parent;
}
return *this;
}
};
template<typena.zodl.pro/me T>
struct __RBTree_itarator
{
typedef RBTre.zodl.pro/eNode<T> Node;
typed.zodl.pro/ef __RBTree_itarator<T> Self;
Node* _node;
__RBTree_itarator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool ope.llqn.pro/rator!=(const Self& it)
{
return _node != it._node;
}
Self& opera.llqn.pro/tor--()
{
Node* cur = _node;
Node* par.llqn.pro/ent = cur->_parent;
if (cur->_left)
{
Node* LeftMax = cur->_left;
while (LeftMax->_right)
{
LeftMax = LeftMax->_right;
}
_node = Left.llqn.pro/Max;
}
else
{
while (parent && cur == parent->_left)
{
cur = pare.llqn.pro/nt;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
Node* cur = _node;
Node* pare.llqn.pro/nt = cur->_parent;
if(cur->_right)
{
Node* RightMin = cur->_right;
while (RightMin->_left)
{
RightMin = RightMin->_left;
}
_node = RightMin;
}
else
{
while (pare.llqn.pro/nt && cur == parent->_right)
{
cu.llqn.pro/r = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
那么此时我们在红黑树中，我们对迭代器的类型__RBTree_itarator重命名一下便于书写，并且编写出begin，end即可，关于begin和end的逻辑在运算符重载函数operator++的原理中已经进行讲解了，这里小编不再过多赘述
typedef __RBTree_itarator<T> iterator;
iterator begin()
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return itera.llqn.pro/tor(cur);
}
iterator end()
{
return iterator(null.llqn.pro/ptr);
}
typedef __RB.llqn.pro/Tree_itarator<T> iterator;
iterator begin()
{
Node* cur = _root;
whil.llqn.pro/e (cur->_left)
{
cur = cur->_left;
}
return itera.llqn.pro/tor(cur);
}
iterat.llqn.pro/or end()
{
return itera.llqn.pro/tor(nullptr);
}
三、红黑树的插入
红黑树的未改造之前插入进行查找位置的时候，由于我们之前模拟实现的红黑树是key_value结构，那么查找的时候是采用的kv.first和cur->_kv.first找出key值进行比较的找出应该插入的位置cur和其对应的parent，但是这里我们不能这样进行比较了因为这里存储的内容我们采用了_data，我们并不能知道_data中的内容是一个key还是一个pair<key,value>，此时的插入我们就没有办法进行找到key值进行比较找到应该插入的位置cur和其对应的parent，此时我们应该如何办呢？
我们在红黑树内部不知道，但是上层封装红黑树的map和set知道啊，map知道红黑树节点存储的内容是pair<key,value>，set知道红黑树节点存储的内容是key，因为map/set给红黑树类模板传入不同的类型，红黑树类模板会实例化出节点中存储内容不同的红黑树，并且此时我们观察下面STL库里的红黑树的实现，第三个模板参数是KeyOfValue，即对应就是取出节点中存储内容的key值
template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protected:
typedef __rb_tree_node<Value> rb_tree_node;
typedef rb_tree_node* link_type;
protected:
link_type hea.llqn.pro/der;//定义的节点指针
}
temp.llqn.pro/late <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;//节点中实际存储的值
};
templ.llqn.pro/ate <class Key, class Value, class Key.llqn.pro/OfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protecte.llqn.pro/d:
typedef __rb_tree_node<Value> rb_tree_node;
typedef rb_tree_node* link_type;
protected:
link_type header;//定义的节点指针
}
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Val.llqn.pro/ue>* link_type;
Value value_field;//节点中实际存储的值
};
注意由于小编认为STL库里的这个Value容易混淆，这个库里的Value是红黑树节点中实际存储内容的类型，这里小编使用T进行替代，那么第三个模板参数使用KeyOfT进行替代，这个KeyOfT其实是一个仿函数即类模板，我们使用这个类模板定义出一个对象，即仿函数对象，仿函数KeyOfT中有重载的operator()，可以让仿函数对象像函数一样使用，关于map/set如何实现这个仿函数的后文小编会进行讲解，这里我们只需要知道如何使用即可，那么使用仿函数我们就可以取出节点中存储的内容_data中的key值，那么此时进行比较，就可以实现适配map/set的红黑树的插入接口，左单旋和右单旋保持不变即可，关于左单旋和右单旋，小编已经放到后面蓝色链接中了 详情请点击<——
template<typename K, typename T, typename KeyOfT>
class RBTree
{
public:
bool Inse.llqn.pro/rt(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
else
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(data);
cur->_col = RED;
cur->_parent = parent;
if (kot(cur->_data) > kot(parent->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
_root->_col = BLACK;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //cur = parent->_right
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
_root->_col = BLACK;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //cur = parent->_left
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
bre.vsfk.pro/ak;
}
}
}
return true;
}
}
private:
Node* _root;
};
template<typena.vsfk.pro/me K, typename T, typename KeyOfT>
class RBTree
{
public:
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
else
{
Node* pare.vsfk.pro/nt = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(da.vsfk.pro/ta) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(data);
cur->_col = RED;
cur->_parent = parent;
if (kot(cur->_data) > kot(pa.vsfk.pro/rent->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
while (par.vsfk.pro/ent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandf.vsfk.pro/3258sdqather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
_root->_col = BLACK;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandf.vsfk.pro/3236ather->_col = RED;
}
else //cur = parent->_right
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //parent == grandf.vsfk.pro/sdawqather->_right
{
Node* uncle = grandfath.vsfk.pro/er->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfa.vsfk.pro/ther->_col = RED;
cur = grandfather;
pare.vsfk.pro/589nt = cur->_parent;
_root->_col = BLACK;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //cur = parent->_left
{
RotateR(parent);
RotateL(gra.vsfk.pro/ndfather);
cur->_co.vsfk.pro/589l = BLACK;
grandfat.vsfk.pro/her->_col = RED;
}
break;
}
}
}
return true;
}
}
private:
Node* _root;
};
四、map/set的封装
set的封装
由于我们的set会跟STL库里的set命名冲突，所以将我们模拟实现的set放到一个命名空间中，那么set只需要一个K（key）作为模板参数即可
那么我们首先写出set中的仿函数SetKeyOfT，那么接下来写operator()，我们知道set中的红黑树类模板实例化出的红黑树中存储的内容_data就是key，所以这里我们的仿函数接收到data后直接返回data即可，并且由于data已经存在所以我们返回K引用即可，由于我们set中的key值不能修改所以我们返回值的类型要加const进行修改
那么接下来我们就给红黑树类模板传入参数实例化出一个存储key的红黑树_t即可
迭代器，我们取出红黑树中的普通迭代器iterator，这里有一点细节需要注意，由于红黑树是一个类，那么我们使用::取出的iterator有可能是内嵌类型，即内部类，被typedef的类型，也有可能是静态成员变量，那么此时编译器在编译检查语法错误的时候就会报错，因为它无法确定我们取出的iterator究竟是类型还是变量，如果是如果是被typedef的类型，那么没有问题，但是如果是静态成员变量的话会这里我们使用typedef会有语法错误，即使用变量重命名了一个类型，此时我们应该添加一个typename告诉编译器这里是一个类型，进行语法检查的时候先不要报错，等到模板实例化了之后再去类中找这个iterator，那么我们使用typedef将红黑树中的普通迭代器iterator重命名为iterator即可，那么此时我们就可以在set中使用iterator了
接下来编写begin，end即可，那么就是在该函数中调用底层红黑树的begin和end进行返回即可实现
插入，set的插入同样是调用红黑树的插入实现
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/2301_80751958/article/details/148581110
码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)