C++进阶--＞封装map和set
1、map和set的底层源码分析
首先如下图所示，这里就可以解掉一个我们可能会有的疑惑，就是只包一个map或者set的头文件为什么就可以使用multiset和multimap，因为他包含在里面了。而下面这张图我们需要关注的重点在于stl_tree.h这个头文件，因为我们前面一篇实现红黑树还有AVL树的实现，我们实现了两棵树，一个key结构的树，还有一个是key_value的树，但是我们看下面图的底层源码，发现他只包了一个头文件#include<stl_tree.h>，接下来我们就来看一下他究竟是怎么实现的，然后我们再自己实现一个。
stl_set和stl_map的底层源码：
这里我们注意，首先我们来分析stl_set的源码，我们发现Key被typedef成key_type和value_type，然后我们再看stl_map的源码，在我们前面实现key_value结构的时候我们模版是template<class K, class V>，但是他这里用的是T， 其实也大差不多差，我们只要知道Key和T就是Key和value就行。
但是重点在于 下面那句我们用红色框框出来的
首先是stl_set，typedef 树结构传过去的是key_type和value_type，实质上这两个都是Key
然后是stl_map，typedef树结构传过去的key_type和value_type，实质上一个是Key，一个是被typedef的pair<const Key, T> 。
由此我们可以分析得出， 是Key结构还是Key_value结构是通过tree的第二个模板参数控制的，那么接下来我们再来看一下树的底层源码。
stl_tree.h的源码：
这里我们再来看__rb_tree_node<Value> rb_tree_node；通过这个名字我们就大概能知道他就是树的结点，那么我们前面AVL树和红黑树的实现上最大的差别就是在于此，AVL树的结点存的是Key，而红黑树结点存的是Key_value，那么我们又可以证实我们上面的观点，那就是C++的map和set的实现是通过树的第二个模板参数Value来控制是map还是set结构，也就是Key结构或者是Key_value结构。
然后有一点需要注意的是，可能有的人觉得实现Key_value结构只需要第二个模板参数就可以了，为什么还需要第一个模板参数class Key，这是因为在实现find和erase的实现上，是通过查找Key值找到对应的位置然后进行删除的。
补充一下：这种就是代码的泛型思想。
最后来补充一下整个的思路图：
2、map和set的模拟实现
map和set其实就是一个外壳来的，主要还是树的结构的实现，这里我们要去前面的红黑树实现拿一份BRTree的代码过来（BRTree我给拼错了，红黑树应该是RBTree，这里我们就将就一下把哈哈哈哈）。这里我们就直接放一份红黑树的树结构的实现的代码，如果有需要直接跳转到后面去Copy，然后再回到这里对着文章一段一段修改，因为我们是要实现一个泛型的树。
2.1 修改红黑树结构实现泛型
结点的修改：
前面的一些无关紧要的代码我就不放进来了，例如那些enum类型定义红黑结点的
首先是对树的结点结构进行改变，由上面的分析看出，树的结点只有一个模板参数来构成，那就是value_type， 那么我们这里用T来表示，然后我们还要把kv改成_data，这个_data改不改都没事，因为这是个泛型结构，不仅是key_value结构可以使用，key结构也可以使用。
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
};这样子就可以实现泛型了，如果T接收的是Key，那就是key结构，如果T模板接收的是pair<Key, Value>，那就是Key_value结构的树。
树结构的修改：
对于树结构的修改我们又有一些别的东西需要注意，就是我们结点改成泛型了之后，在下面一些接口的实现，例如Insert的实现，插入数据，我们需要找到对应的位置进行插入，而这个找位置这个过程是按照平衡二叉树的查找规则进行找位置，平衡二叉的查找规则是比当前结点的值大就走右边，比当前结点的值小就走左边，问题就在于，如果我们要实现泛型，我们该怎么比较大小，如果我们是key结构还好，直接调用cur->_data可以，但要是key_value结构呢？cur->_data.first可以找到，但是这么改的话key结构就用不了了。
所以这时候就用得上仿函数了，我们通过重载仿函数的括号，进行实现即可，那这样我们就需要添加多一个KeyOfT的模板参数。
//定义红黑树的树结构
template<class K, class T, class KeyOfT>
class BRTree
{
typedef RBTreeNode<T> Node;
public:
BRTree() = default;
BRTree(const BRTree& t)
{
_root = Copy(t._root, nullptr);
}
~BRTree()
{
Destory(_root);
_root = nullptr;
}
private:
Node* _root = nullptr;
};这里面的BRTree() = default，是C++11新增的一个用法，后面的篇章会讲到，我们这里就当是一个默认构造即可，然后BRTree(const BRTree& t)和析构在下面会讲，这里就直接放上代码，因为重点是在于Copy和Destory函数。
set.h和map.h的修改：
在set的仿函数重载括号处直接返回传入的值就行，而map的就不同了，需要返回当前值的first值，因为传入的pair，我们需要Key的值。
set.h
#pragma once
#include"RBTree.h"
namespace lwt
{
template<class K>
class set
{
//定义一个仿函数，不然data不知道取的是什么值
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
private:
BRTree < K, K, SetKeyOfT> _t;
};
}
map.h
#pragma once
#include"RBTree.h"
//map是有key和value的
namespace lwt
{
template<class K, class V>
class map
{
//定义一个仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
private:
BRTree < K, pair<const K, V>,MapKeyOfT > _t;
};
}2.2 迭代器的实现
一般我们在实现stl的容器的时候都会需要我们实现泛型的迭代器，因为里面不仅有普通迭代器，还有const迭代器，但是我们不可能写两份相同的代码，这样的话相似性太高了，可能我们人受得了，但实现底层的大佬们可不能容许，所以迭代器的实现也是用到泛型思维进行实现。
如下代码所示：
//定义迭代器类型
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
,_root(root)
{}
};迭代器里面肯定需要结点结构，因为在我们实现--或者++的时候会用到，所以我们typedef一个RBTreeNode<T> Node，然后定义两个成员变量一个_node, 一个_root，然后又思考，在++或者--的时候我们肯定需要返回新的迭代器把，那就需要typedef一个RBTreeIterator<T, Ref, Ptr, Self>，因为我们不可能每次需要返回迭代器的时候这么写，太长了，所以我们typedef成Self。
2.2.1 迭代器operator*的实现
我们思考我们在前面对一个迭代器进行解引用（*）的时候我们是不是得到他们的数据，就类似一个指针，我们对指针解引用，然后得到指针指向的内容，这个也一样，我们只需要对迭代器进行重载即可。如下代码所示：
Ref operator*()
{
return _node->_data;
}ps：Ref是reference的意思，也就是引用 ，因为我们通过迭代器取到这个值的时候是可以对其修改的。
2.2.2 迭代器operator->的实现
使用->的时候左边必须是一个指针，那么我们就返回当前元素的指针即可。
Ptr operator->()
{
return &_node->_data;
}
2.2.3 迭代器重载!=和重载==的实现
判断等于或者不等于我们只需要判断他们是不是同一个结点就行。
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}2.3 --和++的实现（重点）
++和--其实也应该放在迭代器的类里的作为成员函数的，因为++和--是对迭代器进行++和--，但是因为这节比较重点，所以我们把他另外分一个点进行讲解。
首先是++的实现，我们知道数据的分布规则是平衡二叉树，而平衡二叉树是通过中序遍历实现，然后打印出来的数据是有序的，那么我们的++的实现也需要循序中序遍历的规则即“左根右”，左根右顾名思义就是需要遍历完左子树再遍历根然后再遍历右子树，知道这个后我们这里就来一步一步实现一下，可能会有点绕，但是会通过画图进行讲解。
1、首先我们对第一个值进行++，就是树内的最小值，也就是我们后面要实现的begin()，而树内的最小值就是左子树的最左结点。
到达最左结点之后，我们就按上图来进行解析；
2、在我们对it进行++操作的时候我们需要判断右子树是否为空，如果不为空则访问右子树的最左结点，这时候it就走到了15的结点处如下图：
3、接下来这步比较难理解，就是当右子树为空的时候就代表当前it处于的这课子树已经遍历完了，根据中序遍历的“左根右”可以知道，对子树的最后一次遍历是右子树，那么我们就需要跳出当前的子树，我们就需要找到孩子位于父亲左子树的那个父亲结点，这句话可能有点难理解，我们来一点一点的捋清楚。首先我们看下面这张图：cur是孩子结点，而cur位于parent结点的右子树，那就说明这个父亲结点不是我们想要的，所以我们要继续往上找，因为要符合孩子位于父亲左子树的那个父亲结点
然后我们就得到下图，当走到下面这张图的时候就发现，cur孩子结点走到parent父亲结点的左子树处，也就符合了孩子位于父亲左子树的那个父亲结点这个规则，那么我们就让it走到当前符合条件的父亲结点处即可，但是可能有有人疑问为什么这样子找，下面我就会来解释一下。
选择孩子位于父亲左子树的那个父亲结点是因为，当前子树已经完全走完了，符合了中序遍历的左根右顺序，但是当前子树可能又是另一棵树的右子树，那就意味着另一棵树的右子树遍历完了，就需要找到一棵是左子树的结点。
右下图可见，当9的右子树为空的时候我们就需要去找孩子结点为父亲结点的左子树的父亲结点，也就是10结点，然后按照中序遍历的顺序“左根右”，此时左和根走完了，就需要走到右子树处，也就是15，然后发现左为空，就走15的右子树，然后到20,走到20发现左子树为空，就需要找到右子树21结点处，走完之后就代表当前整棵以10为根结点的树已经找完了，那此时，10作为18的左子树，这意味着左子树已经找完了，那就需要走到18根结点处，也就是符合孩子结点位于父亲结点的左子树处的父亲结点。
这个刚接触可能感觉有点绕，我们自己画图看几遍就懂了，可能我讲的也不适合清楚，我们对着图走两遍再走两遍然后对着我说的那些条件可能就更好理解。
总结一下走的条件：
1、如果右子树不为空，找到右子树的最左结点，然后让it走到那即可。
2、如果右子树为空，则说明当前子树已经遍历完毕，需要找到孩子是父亲左结点的那个父亲结点，然后让it走到当前父亲结点处。
实现代码如下：
Self operator++()
{
//首先判断右节点是否为空，如果不为空
//然后让node走到右子树的最左节点
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
//右节点为空,找孩子为父亲左结点的那个父亲结点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}重载operator--的思路和上面的相反，遍历从“左中右”改成“右中左”即可，这里我们就不细致讲了，我们直接上代码，因为很相似的，只是改变一些条件。
这里面因为++可能会加越界，也就是走到50的右节点处，那么当_node==nullptr也就是越界的时候，就让_node走到最大结点处，也就是50处即可。
Self operator--()
{
//如果++ 让_node==nullptr的时候，那就让--_node = 最右的结点
if (_node == nullptr)
{
Node* rightMost = _root;
while (rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
//这个和++相反，因为要逆着走
//++是中序遍历左中右，那么我们--就需要走右中左
else if (_node->_left)
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
//左子树为空，找孩子节点为父亲结点右结点的父亲结点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}2.4 树结构的修改
这里我们会挑一些重点的来讲，其他简单的粗略过一下
2.4.1 树的数据插入
树的插入就和前面红黑树和AVL树讲的一样，返回的值是pair<iterator, bool>类型，如果插入失败，说明里面有需要插入的数据，则插入数据的结点的迭代器和false，如果插入成功则返回插入数据的迭代器和true等等，这些都是前面红黑树那一篇讲的，那边讲的更加具体，我们这里就大概讲一下就然后直接放代码，因为这篇文章的重点就在于--和++的实现。
pair<Iterator, bool> Insert(const T& data)
{
//如果树为空插入结点就需要让该结点为黑色
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return { Iterator(_root, _root), true };
}
KeyOfT kot;
//不是空树，开始找合适的插入位置
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 { Iterator(cur, _root), false };
}
}
//这里出来之后就说明找到了可以插入值的位置
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//链接上父亲
cur->_parent = parent;
//判断parent是否存在，因为这是遍历完整个树的
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (grandparent->_left == parent)
{
Node* uncle = grandparent->_right;
//uncle存在且为红色
if (uncle && uncle->_col == RED)
{
//开始变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//往上走
cur = grandparent;
parent = cur->_parent;
}
//uncle不存在或者为黑色就需要进行旋转
else
{
//进行单旋操作
if (cur == parent->_left)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//就说明插入或存在且从黑变成红的C在parent的右边，就需要进行双旋操作
else
{
// g
// p u
// c
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
//parent在grandparent的右边
else
{
// g
// u p
Node* uncle = grandparent->_left;
//如果uncle存在且uncle的col为红色
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
//uncle不存在或uncle为黑需要进行旋转操作
else
{
if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//进行双旋操作
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return { Iterator(newnode, _root), true };
}2.4.2 赋值运算符的重载operator=
实现operator=，我们使用现代写法，因为赋值运算符的重载是需要释放原空间，然后申请新空间，再把新数据拷贝到新的空间来，但是我们这里可以通过创建一个树的类的变量接受传入的树，然后再调用swap函数对两块空间进行交换，然后返回*this当前空间即可；
BRTree& operator=(BRTree t)
{
swap(_root, t._root);
return *this;
}2.4.3 Begin、End的实现
Begin就是要返回最小的值，也就是root结点的左子树的最左边的值，而这里的返回值我们通过一个匿名函数进行返回；
Iterator Begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
ConstIterator Begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return ConstIterator(cur, _root);
}End的实现就是返回一个nullptr即可；
Iterator End()
{
return Iterator(nullptr, _root);
}
ConstIterator End() const
{
return ConstIterator(nullptr, _root);
}2.4.4 Copy和Destroy的实现
Copy的实现：
Copy函数我们是用来实现拷贝构造的，那么Copy函数就可以使用递归进行一个一个结点复制，但是我们需要注意的是我们要让每一个结点的parent指针指向上一个结点，那么我们就需要传多一个参数进行接收上一个结点的指针。如下代码所示：
Node* Copy(Node* root, Node* parent)
{
if (root == nullptr)
{
return nullptr;
}
Node* newnode = new Node(root->_data);
newnode->_col = root->_col;
newnode->_parent = parent;
newnode->_left = Copy(root->_left, newnode);
newnode->_right = Copy(root->_right, newnode);
return newnode;
}Destory函数的实现：
递归对每一个结点进行销毁即可；如下代码所示：
void Destory(Node* root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
}拷贝构造：
BRTree(const BRTree& t)
{
_root = Copy(t._root, nullptr);
//_root = _Copy(t._root, nullptr);
}析构函数：
~BRTree()
{
Destory(_root);
_root = nullptr;
}2.5 最后再对map.h和set.h进行完善
首先是map.h，map和set其实就是一个壳来的，我们只需要调用红黑树的成员函数对map和set的各个功能进行实现即可，map和set内有两个迭代器，一个是iterator还有一个是const_iterator，那么我们就把map的pair结构传过去，还有仿函数等等进行传过去即可；
template<class K, class V>
class map
{
//定义一个仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename BRTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename BRTree< K, pair<const K, V>,MapKeyOfT>::ConstIterator const_iterator;set的也是一样，只不过set的第二个模版参数传的是K，然后仿函数传的是SetKeyOfT，但是注意前面需要加一个typename，是因为编译器不知道你typedef的不是一个成员变量而是一个嵌套类型。其他的实现我们就直接看后面的代码，end和begin都是调用红黑树的成员函数进行实现的。
3、前面红黑树的实现代码：
#pragma once
#include<iostream>
using namespace std;
//设置红黑结点的定义
enum Colour
{
RED,
BLACK
};
//使用key_value的结构来实现红黑树
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
};
//定义红黑树的树结构
template<class K, class V>
class BRTree
{
typedef RBTreeNode<K, V> Node;
public:
typedef RBTreeIterator<K, V> iterator;
~BRTree()
{
Destroy(_root);
_root = nullptr;
}
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
bool Insert(const pair<K, V>& kv)
{
//如果树为空插入结点就需要让该结点为黑色
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
//不是空树，开始找合适的插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//这里出来之后就说明找到了可以插入值的位置
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//链接上父亲
cur->_parent = parent;
//判断parent是否存在，因为这是遍历完整个树的
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (grandparent->_left == parent)
{
Node* uncle = grandparent->_right;
//uncle存在且为红色
if (uncle && uncle->_col == RED)
{
//开始变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//往上走
cur = grandparent;
parent = cur->_parent;
}
//uncle不存在或者为黑色就需要进行旋转
else
{
//进行单旋操作
if (cur == parent->_left)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//就说明插入或存在且从黑变成红的C在parent的右边，就需要进行双旋操作
else
{
// g
// p u
// c
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
//parent在grandparent的右边
else
{
// g
// u p
Node* uncle = grandparent->_left;
//如果uncle存在且uncle的col为红色
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
//uncle不存在或uncle为黑需要进行旋转操作
else
{
if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//进行双旋操作
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
subL->_parent = pParent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
// 前序遍历走到空时，意味着一条路径走完了
//cout << blackNum << endl;
if (refNum != blackNum)
{
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, refNum)
&& Check(root->_right, blackNum, refNum);
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
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;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
};4、完整的map和set封装代码
RBTree.h
#pragma once
#include<iostream>
using namespace std;
//设置红黑结点的定义
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
{}
};
//定义迭代器类型
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
,_root(root)
{}
Self operator++()
{
//首先判断右节点是否为空，如果不为空
//然后让node走到右子树的最左节点
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
//右节点为空,找孩子为父亲左结点的那个父亲结点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator--()
{
//如果++ 让_node==nullptr的时候，那就让--_node = 最右的结点
if (_node == nullptr)
{
Node* rightMost = _root;
while (rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
//这个和++相反，因为要逆着走
//++是中序遍历左中右，那么我们--就需要走右中左
else if (_node->_left)
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
//左子树为空，找孩子节点为父亲结点右结点的父亲结点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
//定义红黑树的树结构
template<class K, class T, class KeyOfT>
class BRTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*>ConstIterator;
BRTree() = default;
BRTree(const BRTree& t)
{
_root = Copy(t._root, nullptr);
//_root = _Copy(t._root, nullptr);
}
BRTree& operator=(BRTree t)
{
swap(_root, t._root);
return *this;
}
~BRTree()
{
Destory(_root);
_root = nullptr;
}
Iterator Begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
ConstIterator Begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return ConstIterator(cur, _root);
}
ConstIterator End() const
{
return ConstIterator(nullptr, _root);
}
pair<Iterator, bool> Insert(const T& data)
{
//如果树为空插入结点就需要让该结点为黑色
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return { Iterator(_root, _root), true };
}
KeyOfT kot;
//不是空树，开始找合适的插入位置
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 { Iterator(cur, _root), false };
}
}
//这里出来之后就说明找到了可以插入值的位置
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//链接上父亲
cur->_parent = parent;
//判断parent是否存在，因为这是遍历完整个树的
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (grandparent->_left == parent)
{
Node* uncle = grandparent->_right;
//uncle存在且为红色
if (uncle && uncle->_col == RED)
{
//开始变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//往上走
cur = grandparent;
parent = cur->_parent;
}
//uncle不存在或者为黑色就需要进行旋转
else
{
//进行单旋操作
if (cur == parent->_left)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//就说明插入或存在且从黑变成红的C在parent的右边，就需要进行双旋操作
else
{
// g
// p u
// c
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
//parent在grandparent的右边
else
{
// g
// u p
Node* uncle = grandparent->_left;
//如果uncle存在且uncle的col为红色
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
//uncle不存在或uncle为黑需要进行旋转操作
else
{
if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
//进行双旋操作
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return { Iterator(newnode, _root), true };
}
//pair<Iterator, bool> Insert(const T& data)
//{
// if (_root == nullptr)
// {
// _root = new Node(data);
// _root->_col = BLACK;
//
// //return pair<Iterator, bool>(Iterator(_root, _root), true);
// return { Iterator(_root, _root), true };
// }
//
// KeyOfT kot;
// Node* parent = nullptr;
// Node* cur = _root;
// while (cur)
// {
// if (kot(cur->_data) < kot(data))
// {
// parent = cur;
// cur = cur->_right;
// }
// else if ( kot(data)< kot(cur->_data))
// {
// parent = cur;
// cur = cur->_left;
// }
// else
// {
// return { Iterator(cur, _root), false };
// }
// }
//
// cur = new Node(data);
// Node* newnode = cur;
// cur->_col = RED;
// if (kot(parent->_data) < kot(data))
// {
// parent->_right = cur;
// }
// else
// {
// parent->_left = cur;
// }
// // 链接父亲
// cur->_parent = parent;
//
// // 父亲是红色，出现连续的红色节点，需要处理
// while (parent && parent->_col == RED)
// {
// Node* grandfather = parent->_parent;
// if (parent == grandfather->_left)
// {
// // g
// // p u
// Node* 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 u
// // c
// RotateR(grandfather);
// parent->_col = BLACK;
// grandfather->_col = RED;
// }
// else
// {
// // g
// // p u
// // c
// RotateL(parent);
// RotateR(grandfather);
// cur->_col = BLACK;
// grandfather->_col = RED;
// }
//
// break;
// }
// }
// else
// {
// // g
// // u p
// Node* uncle = grandfather->_left;
// // 叔叔存在且为红，-》变色即可
// if (uncle && uncle->_col == RED)
// {
// parent->_col = uncle->_col = BLACK;
// grandfather->_col = RED;
//
// // 继续往上处理
// cur = grandfather;
// parent = cur->_parent;
// }
// else // 叔叔不存在，或者存在且为黑
// {
// // 情况二：叔叔不存在或者存在且为黑
// // 旋转+变色
// // g
// // u p
// // c
// if (cur == parent->_right)
// {
// RotateL(grandfather);
// parent->_col = BLACK;
// grandfather->_col = RED;
// }
// else
// {
// RotateR(parent);
// RotateL(grandfather);
// cur->_col = BLACK;
// grandfather->_col = RED;
// }
//
// break;
// }
// }
// }
//
// _root->_col = BLACK;
//
// return { Iterator(newnode, _root), true };
//}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
subL->_parent = pParent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
// 前序遍历走到空时，意味着一条路径走完了
//cout << blackNum << endl;
if (refNum != blackNum)
{
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, refNum)
&& Check(root->_right, blackNum, refNum);
}
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void Destory(Node* root)
{
if (root == nullptr)
{
return;
}
Destory(root->_left);
Destory(root->_right);
delete root;
}
Node* Copy(Node* root, Node* parent)
{
if (root == nullptr)
{
return nullptr;
}
Node* newnode = new Node(root->_data);
newnode->_col = root->_col;
newnode->_parent = parent;
newnode->_left = Copy(root->_left, newnode);
newnode->_right = Copy(root->_right, newnode);
return newnode;
}
private:
Node* _root = nullptr;
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;
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
};
Mymap.h
#pragma once
#include"RBTree.h"
//map是有key和value的
namespace lwt
{
template<class K, class V>
class map
{
//定义一个仿函数
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename BRTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename BRTree< K, pair<const K, V>,MapKeyOfT>::ConstIterator const_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();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
private:
BRTree < K, pair<const K, V>,MapKeyOfT > _t;
};
}Myset.h
#pragma once
#include"RBTree.h"
namespace lwt
{
template<class K>
class set
{
//定义一个仿函数，不然data不知道取的是什么值
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename BRTree<K, K, SetKeyOfT>::Iterator iterator;
typedef typename BRTree<K, K, SetKeyOfT>::ConstIterator const_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();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
BRTree < K, K, SetKeyOfT> _t;
};
}
END!