目录
前言：
下面为了简单模拟实现set map所出现的代码是以C++中STL源码库中的代码逻辑基础进行的简化代码，本片博客目的是带你简单深入底层，了解set map底层的实现逻辑，对泛型编程有更加深刻的认识。
一、学前铺垫（泛型编程）
本篇博客我们通过对一个红黑树进行改造，使其可以让set和map的模拟实现都使用这一个红黑树结构，因为set map所存储的数据类型不一样,set底层存储的是pair<key,key>,map底层存储的是pair<key,value>,所以这里就一定会用上多个模板对红黑树进行改造，形成泛型编程，之后再对set map使用改造后的红黑树进行封装，达到模拟STL库中set map的效果。（有能力的可以直接去看STL中set map所实现的源码，逻辑与我所讲述的相同）
二、改造红黑树
1.红黑树节点的改造
这里节点的构造基本与二叉搜索树的节点构造相同，但是因为要同时兼顾set map两中类型，所以存储数据的类型不可以写死，要用到模板，节点代码如下：
template <class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
T _data;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};2.insert的改造
需要改造的地方：
1) 根据STL库中的set和map的insert的功能，插入成功返回插入位置所在的迭代器以及true，插入失败说明树中已存在改值，返回该值所在的位置的迭代器以及false，所以返回类型应为pair<iterator,bool>，所以返回类型需要进行改造。
2) 在insert中大小值的比较，因为要兼容set和map，而在set中的模板类型只需要一个就可以进行初始化，因为set中底层数据类型是一样的，而map不同，map底层类型其实是pair<key,pair<key,value>>实现，因为在实现find函数时需要用到key的值并且与set保持一致，所以将value类型定义为pair<key,value>，那么在后续的比较大小中就不能那么随意了，因为set直接拿其节点指向的_data进行比较即可，而map中的_data为pair<key,pair<key,value>>,不可以直接拿来进行比较,所以我们将代码进行改造。
下面是模拟实现set，map的简单封装。SetKeyOFT，MapKeyOFT就是解决大小比较所定义的内部类。
Mymap.h:
template <class K,class V>
class map
{
public:
struct MapKeyOFT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
private:
RBTree<K, pair<K,V>, MapKeyOFT> _t;
};Myset.h:
template <class K>
class set
{
public:
struct SetKeyOFT
{
const K& operator()(const K& key)
{
return key;
}
};
private:
RBTree<K,K, SetKeyOFT> _t;
};insert函数改造实现：
pair<iterator,bool> Insert(const T& data)
{
//二叉树为空，插入第一个值
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
KeyOfT kot;
//后续插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else
{
//不允许冗余
return make_pair(iterator(cur),false);
}
}
//找到对应位置
cur = new Node(data);
cur->_parent = parent;
Node* newcur = cur;
if (kot(parent->_data) > kot(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//父亲的颜色是黑色也就结束
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;
/*if (grandfather == _root)
{
grandfather->_col = BLACK;
}
else
{
grandfather->_col = RED;
}*/
grandfather->_col = RED;
cur = grandfather;
parent = grandfather->_parent;
}
else
{
//舅子树不存在或颜色为黑
if (parent->_left == cur)
{
//单旋
parent->_col = BLACK;
grandfather->_col = RED;
RNode(grandfather);
}
else
{
//双旋 先左再右
LNode(parent);
cur->_col = BLACK;
grandfather->_col = RED;
RNode(grandfather);
}
break;
}
}
else
{
//舅子树在左边
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = grandfather->_parent;
}
else
{
if (parent->_right == cur)
{
//单旋
parent->_col = BLACK;
grandfather->_col = RED;
LNode(grandfather);
}
else
{
//双旋
RNode(parent);
LNode(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newcur),true);
}因为只在红黑树insert函数里面使用的都是模板，所以是不知道所传数据的具体类型，但是在模拟实现的set，map中知道其对应的类型，所以我们可以在set，map类里面定义一个类，在这个类里面定义一个仿函数用于提取所对应比较大小的值，再将这个类用模板参数传递给红黑树中，在需要比较大小时提前用这个类定义一个变量，在通过仿函数进行大小的比较，这样就可以实现set，map的兼容。
3.迭代器的实现
迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代
器，需要考虑以前问题：
● begin() 与 end()
STL 明确规定， begin() 与 end() 代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此： begin() 可以放在红黑树中最小节点 ( 即最左侧节点 ) 的位置 ， end() 放在最大节点 ( 最右侧节点 ) 的下一个位置 ，关键是最大节点的下一个位置在哪块？能否给成 nullptr 呢？答案是行不通的，因为 对 end() 位置的迭代器进行 -- 操作，必须要能找最后一个元素 ，此处就不行，因此最好的方式是 将 end() 放在头结点的位置 ：
● operator++()与operator--()
// 找迭代器的下一个节点，下一个节点肯定比其大
void Increasement()
{
//分两种情况讨论:_pNode的右子树存在和不存在
// 右子树存在
if (_pNode->_pRight)
{
// 右子树中最小的节点，即右子树中最左侧节点
_pNode = _pNode->_pRight;
while (_pNode->_pLeft)
_pNode = _pNode->_pLeft;
}
else
{
// 右子树不存在，向上查找，直到_pNode != pParent->right
PNode pParent = _pNode->_pParent;
while (pParent->_pRight == _pNode)
{
_pNode = pParent;
pParent = _pNode->_pParent;
}
// 特殊情况：根节点没有右子树
if (_pNode->_pRight != pParent)
_pNode = pParent;
}
}
// 获取迭代器指向节点的前一个节点
void Decreasement()
{
//分三种情况讨论：_pNode 在head的位置，_pNode 左子树存在，_pNode 左子树不
存在
// 1. _pNode 在head的位置，--应该将_pNode放在红黑树中最大节点的位置
if (_pNode->_pParent->_pParent == _pNode && _pNode->_color == RED)
_pNode = _pNode->_pRight;
else if (_pNode->_pLeft)
{
// 2. _pNode的左子树存在,在左子树中找最大的节点，即左子树中最右侧节点
_pNode = _pNode->_pLeft;
while (_pNode->_pRight)
_pNode = _pNode->_pRight;
}
else
{
// _pNode的左子树不存在，只能向上找
PNode pParent = _pNode->_pParent;
while (_pNode == pParent->_pLeft)
{
_pNode = pParent;
pParent = _pNode->_pParent;
}
_pNode = pParent;
}
}4.完整改造代码
#pragma once
#include <iostream>
using namespace::std;
enum Color
{
RED,//(0)
BLACK//(1)
};
template <class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
T _data;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
template <class T,class Ref,class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator--()
{
if (_node->_left)
{
//存在左子树
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
//不存在左子树
Node* parent = _node->_parent;
if (parent && parent->_left == _node)
{
//为父亲的左孩子
while (parent && parent->_left == _node)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
else
{
//为父亲的右孩子
_node = parent;
}
}
return *this;
}
Self& operator++()
{
if (_node->_right)
{
//存在右子树
_node = _node->_right;
while (_node && _node->_left)
{
_node = _node->_left;
}
}
else
{
//不存在右子树
Node* parent = _node->_parent;
while (parent && _node == parent->_right)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template <class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T,const T&,const T*> const_iterator;
RBTree() = default;//强制编译器生成构造函数
//拷贝构造
RBTree(RBTree<K, const T, KeyOfT>& t)
{
_root = copy(t._root);
}
iterator begin()
{
Node* LeftMin = _root;
while (LeftMin && LeftMin->_left)
{
LeftMin = LeftMin->_left;
}
return iterator(LeftMin);
}
iterator end()
{
return iterator(_root->_parent);
}
const_iterator begin() const
{
Node* LeftMin = _root;
while (LeftMin && LeftMin->_left)
{
LeftMin = LeftMin->_left;
}
return const_iterator(LeftMin);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
//右单旋，满足二叉树引发右单旋之后平衡因子一定为0
void RNode(Node* parent)
{
Node* pparent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (pparent)
{
subL->_parent = pparent;
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
}
else
{
_root = subL;
subL->_parent = nullptr;
}
}
//左单旋
void LNode(Node* parent)
{
Node* pparent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (pparent)
{
subR->_parent = pparent;
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
}
else
{
_root = subR;
subR->_parent = nullptr;
}
}
pair<iterator,bool> Insert(const T& data)
{
//二叉树为空，插入第一个值
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
KeyOfT kot;
//后续插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else
{
//不允许冗余
return make_pair(iterator(cur),false);
}
}
//找到对应位置
cur = new Node(data);
cur->_parent = parent;
Node* newcur = cur;
if (kot(parent->_data) > kot(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//父亲的颜色是黑色也就结束
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 = grandfather->_parent;
}
else
{
//舅子树不存在或颜色为黑
if (parent->_left == cur)
{
//单旋
parent->_col = BLACK;
grandfather->_col = RED;
RNode(grandfather);
}
else
{
//双旋 先左再右
LNode(parent);
cur->_col = BLACK;
grandfather->_col = RED;
RNode(grandfather);
}
break;
}
}
else
{
//舅子树在左边
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = grandfather->_parent;
}
else
{
if (parent->_right == cur)
{
//单旋
parent->_col = BLACK;
grandfather->_col = RED;
LNode(grandfather);
}
else
{
//双旋
RNode(parent);
LNode(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newcur),true);
}
bool IsRBTree()
{
if (_root->_col == RED)
{
cout << "根节点为红节点" << endl;
return false;
}
int DefNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
DefNum++;
}
cur = cur->_left;
}
return _Check(_root, 0, DefNum);
}
~RBTree()
{
Destory(_root);
_root = nullptr;
}
private:
Node* copy(const Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* newnode = new Node(root->_data);
newnode->_col = root->_col;
newnode->_left = copy(root->_left);
if(newnode->_left)
newnode->_left->_parent = newnode;
newnode->_right = copy(root->_right);
if (newnode->_left)
newnode->_left->_parent = newnode;
return newnode;
}
void Destory(Node* root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
root = nullptr;
}
bool _Check(Node* root, int BlackNum, int DefNum)
{
if (root == nullptr)
{
if (BlackNum != DefNum)
{
cout << BlackNum << "|" << DefNum << endl;
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "->存在连续的两个红节点" << endl;
return false;
}
if (root->_col == BLACK)
{
BlackNum++;
}
return _Check(root->_left, BlackNum, DefNum)
&& _Check(root->_right, BlackNum, DefNum);
}
Node* _root = nullptr;
};
三、set的模拟实现封装
set 的底层为红黑树，因此只需在 set 内部封装一棵红黑树，即可将该容器实现出来 ( 具体实现可参
考 map) 。
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, const K, SetKeyOFT>::iterator const_iterator;
pair<iterator,bool> insert(const K& key)
{
return _t.Insert(key);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
private:
RBTree<K, const K, SetKeyOFT> _t;
};四、map的模拟实现封装
template <class K,class V>
class map
{
public:
struct MapKeyOFT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename RBTree<K, pair<const K, V>, MapKeyOFT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOFT>::iterator const_iterator;
V& operator[](const K& key)
{
pair<iterator,bool> ret = _t.Insert(make_pair(key,V()));
return ret.first->second;
}
pair<iterator,bool> insert(const pair<K,V>& kv)
{
return _t.Insert(kv);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
private:
RBTree<K, pair<const K,V>, MapKeyOFT> _t;
};五、完结撒❀
如果以上内容对你有帮助不妨点赞支持一下，以后还会分享更多编程知识，我们一起进步。
最后我想讲的是，据说点赞的都能找到漂亮女朋友❤
![[C++][数据<span style='color:red;'>结构</span>]<span style='color:red;'>红</span><span style='color:red;'>黑</span><span style='color:red;'>树</span><span style='color:red;'>的</span>介绍和<span style='color:red;'>模拟</span><span style='color:red;'>实现</span>](https://img-blog.csdnimg.cn/direct/97d66224e23f4d9b97bbf9d542e57ed8.png)
