【C++】set和map的封装
本文详细解析了STL中set和map的底层实现原理。通过分析发现，set和map底层都是基于红黑树实现的，但存储结构不同：set存储Key类型，实际实现为rb_tree<Key,Key>；map存储Key-Value对，实现为rb_tree<Key,pair<Key,Value>>;。文章重点阐述了红黑树的改造过程，包括节点定义、插入操作的修改、迭代器实现等关键技术点。特别说明了如何通过模板参数和
·
目录
前言
之前我们认识到了，set和map的使用，AVL树，红黑树，其实set和map底层使用的都是红黑树。而本章我们将要来理解stl中set和map的封装原理
一、认识stl中的set和map
我们通过查询一些资料可以得到下图所示：
可以看到，我们看到的set只用传递一个类型就可以了，我们之前常说的Key类型，而map则需要传递两个类型，即我们之前说的Key_Value类型。但是实际上并不是这样，其实在库中实现的set和map的底层其实都是Key_Vaule类型的，底层都是通过一颗Key_Vaule类型的红黑树实现的，如下所示，库中的一些关键代码;
通过这个图，我们可以知道：库中的set和map都是通过库中Key_Vaule类型的红黑树实现的：
- 其中set虽然在外面是一个Key型（即set<Key>），但实际实现的时候，是通过一个红黑树的 rb_tree<Key，Key> 结构封装实现的；
- 而map则是在外面接收两个类型（即map<Key, Value>），但实际上是通过红黑树的rb_tree<Key，pair<Key, Vaule>> 结构封装实现的。
简化一下就是这样的：
二、修改红黑树
通过上面我们知道，set和map使用的都是同一种树，只是传递的第二个模板参数不同而已，set是<Key,Key>，而map是<Key, pair<Key, Value>>。
- 其中第一个模板参数Key的主要作用是用于确定查找类型。
- 而第二个模板参数是用于确定我们的存储类型，我们在树中插入数据的时候比较的就是第二个参数。
1. 节点定义
由于set存储的是Key类型，而map存储的是pair<Key, Value> 类型，所以我们在定义红黑树时，需要将它修改为都可以存储，这我们可以将红黑树节点的模板实现一个泛型存储，代码如下：
enum Colour { RED,BLACK };
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data; // 不论是Key还是pair类型都可以存储
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED) //新节点的默认颜色是红色
{ }
};在树中，定义也要改变，如下所示：
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node; //结点中存储类型与第二个模板参数有关
public:
//插入
bool Insert(const T& date)
{
// ......
}
private:
Node* _root = nullptr;
};注意：这里红黑树的类的模板参数虽然为两个，当时后面还会增加的。
2. 插入操作
由于我们节点中的存储类型是一个泛型的 T 类型，所以在树的插入操作中，当我们需要比较的时候，比较的应该是Key值，在set传递的第二个模板参数就是key，而map传递的第二个模板参数传递的应该是pair<key, value>，这时就需要取出pair中first的key来进行比较，要解决这个问题，我们可以通过在set和map这一层传递第三个模板参数给红黑树：
- 对于set，取出的就是key本身；
- 而对于map，取出的则是pair中的第一个参数key。
这第三个模板参数传递的是一个仿函数的类：重载了（）的类。
在 set 中实现一个内部类，用来获取 key 的本身：
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K>
class set
{
struct SetKeyOfT
{
// 获取key中的key本身
const K& operator()(const K& key)
{
return key;
}
};
private:
RBTree<K, K, SetKeyOfT> _t;
};
}在 map 中，树中的 T 是 pair ，这样我们需要取出 pair 中的 fist 作为 key ，代码如下：
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
// 获取pair<K,V>中的key
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
private:
RBTree<K, pair<K,V>, MapKeyOfT> _t;
};
}最后，我们需要修改红黑树的插入操作：每当需要比较插入的值时，都需要定义第三个模板参数的类型，通过这个类型来获取 T 的 key 值进行比较，这样不论是set还是map，都可以成功插入数据了。如下所示：
template<class K, class T, class KetOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
//插入
bool Insert(const T& date)
{
//1.树为空，直接插入
if (_root == nullptr)
{
_root = new Node(date);
_root->_col = BLACK;
return true;
}
KetOfT kot; // 定义取出T中的Key
//2.树不为空，则寻找要插入的位置
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 false; //已经存在，插入失败
}
}
cur = new Node(data);
if (kot(parent->_data) < kot(parent->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent; //但这里就,结点就在树中了
//插入红结点，需要判断和调整
while (parent && parent->_col == RED) // 如果父亲存在且为红，说明有两个连续的红结点，需要继续调整
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left) // parent在grandparent的左边
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新
{
//变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上更新
cur = grandparent;
parent = grandparent->_parent;
}
else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色
{
if(cur == parent->_left)
{
// g(黑)
// p(红) --> p(黑)
// c(红) c(红) g(红)
// 右单旋
RotateR(grandparent);
//变色
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
// g(黑) g(黑)
// p(红) --> c(红) --> c(黑)
// c(红) p(红) p(红) g(红)
// 先左单旋，再右单旋
RotateL(parent);
RotateR(grandparent);
// 变色
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
else // parent在grandparent的右边
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新
{
//变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上更新
cur = grandparent;
parent = grandparent->_parent;
}
else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色
{
if (cur == parent->_right)
{
// g(黑)
// p(红) --> p(黑)
// c(红) g(红) c(红)
// 左单旋
RotateL(grandparent);
//变色
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
// g(黑) g(黑)
// p(红) --> c(红) --> c(黑)
// c(红) p(红) g(红) p(红)
// 先右单旋，再左单旋
RotateR(parent);
RotateL(grandparent);
// 变色
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
private:
Node* _root = nullptr;
};这样我们红黑树的插入操作修改就大致完成了。但这里并不是最终的结构。因为返回值我们来没有修改。
注意：后续再实现重载 [ ] 的时候还需要修改一下它的返回值，因为这需要使用到我们实现的迭代器，所以就在实现重载 [ ] 的时候再说。
三、红黑树迭代器的实现
上一张我们没有实现红黑树的迭代器，这里我们就可以来实现一下。
1. 迭代器的定义
红黑树的迭代器，我们需要实现普通迭代器和const迭代器，所以首先我们就需要三个模板参数（用于方便实现const迭代器）。红黑树是树，所以其迭代器也就是节点指针，所以迭代器的基本定义如下所示：
//实现红黑树的迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node; // 树的节点指针
typedef __TreeIterator<T, Ref, Ptr> Self; // 将该类型重定义一下,方便书写
__TreeIterator(Node* node)
:_node(node)
{ }
};2. * 重载和 -> 重载
实现 * 重载的函数需要使用到第二个模板参数Ref ，这样可以保证：
- 当定义迭代器是传递的第二个模板参数是 T& 时，是普通迭代器；
- 如果第二个模板参数是 const T& 时，是const迭代器
所以 * 重载的代码如下所示：
Ref operator*()
{
return _node->_data;
}实现 -> 重载的函数需要使用到第三个模板参数Ref ，这样可以保证：
- 当定义迭代器是传递的第三个模板参数是 T* 时，是普通迭代器；
- 如果第三个模板参数是const T*时，是const迭代器
-> 重载的代码如下所示：
Ptr operator->()
{
return &_node->_data;
}3. 重载 != 和 ==
关于!=和==的重载很简单，只需要比较两个指针是否相等即可，实现代码如下所示：
// 迭代器与迭代器比较
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}4. 重载 ++ 和 --
红黑树的自增就是：红黑树的中序遍历的顺序。而--则是反着中序遍历的顺序。
对于 ++ 的操作：
- 如果右孩子不为空，则访问右子树的最左节点；
- 如果右孩子为空，则需要向上找到：第一个孩子是父亲左孩子的节点，此时它的父亲就是下一个访问的节点。如果遇到其父亲为空时，此时parent就是根节点的父亲，则这就说明都访问完了。
所以前置++的函数重载实现代码如下所示：
Self& operator++() // 前置++
{
if (_node->_right)
{
// 如果右孩子不为空，则访问右孩子最左节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
// 如果右孩子为空，则需要向上找到：
// 第一个孩子是父亲左孩子的节点，其父亲就是下一个访问的节点
Node* cur = _node;
Node* parent = cur-> _parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}如果是后置++，则需要添加一个int参数，实现的时候需要先保存在处理，最后返回的就是先保存的数据。
对于前置--，同理：
- 如果左孩子不为空，则访问左子树的最右节点；
- 如果左孩子为空，则需要向上找到：第一个孩子是父亲右孩子的节点，此时它的父亲就是下一个访问的节点。
则前置 -- 的代码实现如下所示：
Self& operator--() // 前置--
{
if (_node->_left)
{
// 如果左孩子不为空，则访问左子树的最右节点
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
// 如果左孩子为空，则需要向上找到：
// 第一个孩子是父亲右孩子的节点，此时它的父亲就是下一个访问的节点
Node* cur = _node;
Node* parent = cur-> _parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}5. 普通迭代器和const迭代器
我们实现了如实所示的迭代器操作之后，那么在红黑树中，我们就可以分别实现普通迭代器和const迭代器了，通过传递对应的模板参数，就可以实现对应的类型迭代器。如下所示：
template<class K, class T, class KetOfT>
class RBTree
{
typedef __TreeIterator<T, T&, T*> iterator; // 普通迭代器
typedef __TreeIterator<T, const T&, const T*> const_iterator; // const迭代器
// ......
}；然后实现红黑树迭代器的begin和end函数，代码如下所示：
// 普通迭代器
iterator begin()
{
// 红黑树的第一个节点是左子树的最左节点
Node* cur = _root;
while (cur->_right)
{
cur = cur->_right;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
// const迭代器
const_iterator begin()
{
// 红黑树的第一个节点是左子树的最左节点
Node* cur = _root;
while (cur->_right)
{
cur = cur->_right;
}
return const_iterator(cur);
}
const_iterator end()
{
return const_iterator(nullptr);
}四、set和map的封装
1. 迭代器的封装
（1）set迭代器
对于set 而言，只有key，并且key是不能被修改的，所以，set的当前本质上还是const迭代器。我们先来看看库中是怎么实现的，如下图所示：
在stl库中，是将const迭代器也作为了普通迭代器来解决这个问题的：不管是普通还是const，使用的都是红黑树中的const迭代器。所以我们实现set的迭代器就可以如下所示（注意：这里的错误的代码）：
// MySet.h
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K>
class set
{
struct SetKeyOfT
{
// 获取key中的key本身
const K& operator()(const K& key)
{
return key;
}
};
public:
//定义迭代器类型
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}但是如果真的这样写，就会出现一些问题，运行后，会报错，即：
原因如下：
要解决这个问题，我们可以在begin和end的后面都加上const修饰，这样就只会调用树里的const迭代器了（库里面也是这样实现的）。所以正确的代码实现如下所示：
// MySet.h
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K>
class set
{
struct SetKeyOfT
{
// 获取key中的key本身
const K& operator()(const K& key)
{
return key;
}
};
public:
//定义迭代器类型
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
bool insert(const K& key)
{
return _t.Insert(key); //对于set插入的就是key
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}（2）map迭代器
map调用的时候是要传递两个参数，即<Key, Value> ，在我们使用的时候，map中的Key是不可以改变的，但Value是可以改变的。在实现map的这一层，我们是通过Key_Value型的红黑树实现的，而map中传递给红黑树的模板参数是<Key, pair<Key, Value>>型的。也就是说，我们要控制最外层的map的Key不能改变，但Value可以改变，就需要修改实现红黑树的时候，红黑树的第二个模板参数是pair型，要保证此时的pair型中的first不可以修改，但second可以改变。总结一下：
那么我们要如何实现这样呢？
实现这个，也很简单，要修改的有一些两点：
map的迭代器就和常规实现迭代器一样，普通迭代器（map层）就是普通迭代器（红黑树层），const迭代器（map层）就是const迭代器（红黑树层）。如下所示：
// MyMap.h
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
// 获取pair<K,V>中的key
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
//普通迭代器
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
//const迭代器
const_iterator begin() const { return _t.begin(); }
const_iterator end() const{ return _t.end(); }
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv); //对于map插入的就是pair<k,v>
}
private:
RBTree<K, pair<K,V>, MapKeyOfT> _t;
};
}只是这样当然不行，还需要修改一下其中的pair的K，将K改为const K，就可以了，即：pair<K, V>修改为pair<const K, V>即可。正确的代码实现如下所示：
// MyMap.h
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
// 获取pair<K,V>中的key
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
//普通迭代器
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
//const迭代器
const_iterator begin() const { return _t.begin(); }
const_iterator end() const{ return _t.end(); }
private:
RBTree<K, pair<const K,V>, MapKeyOfT> _t;
};
}这样，那我们实现map后，如果是普通迭代器，则key不能修改，value可以修改，如果是const迭代器，则key和value都不能修改。
2. map的[ ] 重载实现
通过查看map文档，我们知道，map的[ ]重载需要先进行插入k的操作：
- 如果k已经在树里面了，这时插入的返回值ret就是pair<树里面的k所在节点的迭代器iterator, false>；
- 如果k不在树里面，这时插入的返回值ret就是pair<新插入k所在节点的迭代器iterator, false>；
然后再返回ret中的first迭代器对应的second的引用。
如下图所示：
分开就是：
所以，在实现 [ ] 重载函数之前，我们还需要实现返回值为pair<iterator，bool>类型的插入函数，只用修改上述红黑树的插入函数的返回值即可，实现代码如下所示：
//插入
pair<iterator, bool> Insert(const T& data)
{
//1.树为空，直接插入
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
KetOfT kot;
//2.树不为空，则寻找要插入的位置
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); //已经存在，插入失败
}
}
cur = new Node(data);
if (kot(parent->_data) < kot(cur->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
Node* newnode = cur; //保存一下插入节点的位置
cur->_parent = parent; //但这里就,结点就在树中了
//插入红结点，需要判断和调整
while (parent && parent->_col == RED) // 如果父亲存在且为红，说明有两个连续的红结点，需要继续调整
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left) // parent在grandparent的左边
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新
{
//变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上更新
cur = grandparent;
parent = grandparent->_parent;
}
else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色
{
if(cur == parent->_left)
{
// g(黑)
// p(红) --> p(黑)
// c(红) c(红) g(红)
// 右单旋
RotateR(grandparent);
//变色
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
// g(黑) g(黑)
// p(红) --> c(红) --> c(黑)
// c(红) p(红) p(红) g(红)
// 先左单旋，再右单旋
RotateL(parent);
RotateR(grandparent);
// 变色
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
else // parent在grandparent的右边
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新
{
//变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上更新
cur = grandparent;
parent = grandparent->_parent;
}
else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色
{
if (cur == parent->_right)
{
// g(黑)
// p(红) --> p(黑)
// c(红) g(红) c(红)
// 左单旋
RotateL(grandparent);
//变色
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
// g(黑) g(黑)
// p(红) --> c(红) --> c(黑)
// c(红) p(红) g(红) p(红)
// 先右单旋，再左单旋
RotateR(parent);
RotateL(grandparent);
// 变色
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}最后，在MyMap.h中实现我们自己map的 [ ] 重载函数，实现代码如下所示：
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
// 获取pair<K,V>中的key
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
// [ ] 重载函数
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K,V>, MapKeyOfT> _t;
};
}3. 插入操作的封装
set和map的插入操作，都是只需要调用红黑树的插入成员函数就可以了。
但是由于我们之前实现 [ ] 重载函数时，将insert插入函数的返回值改成了pair<iterator, bool>，所以我们实现的set中的插入函数，就有一些细节需要考虑了，如下所示：如果我们调用红黑树的插入函数：
出现这种错误的原因是因为：在set实现层，所有的迭代器都是const迭代器，，所以这里的iterator也是const迭代器，而我们调用的红黑树中插入函数返回的pair第一个迭代器返回的是红黑树中的普通迭代器，所以，这里就会出现普通迭代器转换成const迭代器的情况，由于它们类型不同不可以转换，所以才会出错，因此我们的解决办法就是：先试用一个pair<普通迭代器，bool>类型的变量来接收返回值，再使用这个这个pair的普通迭代器fist和布尔值second来构造，实现代码如下所示：
// MySet.h
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K>
class set
{
struct SetKeyOfT
{
// 获取key中的key本身
const K& operator()(const K& key)
{
return key;
}
};
public:
//定义迭代器类型
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
pair<iterator, bool> insert(const K& key)
{
//对于set插入的就是key
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); // 使用普通迭代器的pair来接收
// 使用普通pair中的迭代器first来构造当前的const迭代器
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}要注意：如果我们这样使用，那么我们就需要对在红黑树中熟悉的迭代器添加一个构造函数，即：
五、最终代码
RBTree.h
#pragma once
enum Colour { RED,BLACK };
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data; // 不论是Key还是pair类型都可以存储
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED) //新节点的默认颜色是红色
{ }
};
//实现红黑树的迭代器
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
Node* _node; // 树的节点指针
typedef __TreeIterator<T, Ref, Ptr> Self; // 将该类型重定义一下,方便书写
typedef __TreeIterator<T, T&, T*> Iterator; //表示当前的普通迭代器
__TreeIterator(const Iterator& it)
:_node(it._node)
{ }
__TreeIterator(Node* node)
:_node(node)
{ }
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;
}
Self& operator++() // 前置++
{
if (_node->_right)
{
// 如果右孩子不为空，则访问右子树的最左节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
// 如果右孩子为空，则需要向上找到：
// 第一个孩子是父亲左孩子的节点，此时它的父亲就是下一个访问的节点
Node* cur = _node;
Node* parent = cur-> _parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--() // 前置--
{
if (_node->_left)
{
// 如果左孩子不为空，则访问左子树的最右节点
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
// 如果左孩子为空，则需要向上找到：
// 第一个孩子是父亲右孩子的节点，此时它的父亲就是下一个访问的节点
Node* cur = _node;
Node* parent = cur-> _parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KetOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T&, T*> iterator; // 普通迭代器
typedef __TreeIterator<T, const T&, const T*> const_iterator; // const迭代器
// 普通迭代器
iterator begin()
{
// 红黑树的第一个节点是左子树的最左节点
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
// const迭代器
const_iterator begin() const
{
// 红黑树的第一个节点是左子树的最左节点
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
//插入
pair<iterator, bool> Insert(const T& data)
{
//1.树为空，直接插入
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
KetOfT kot;
//2.树不为空，则寻找要插入的位置
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); //已经存在，插入失败
}
}
cur = new Node(data);
if (kot(parent->_data) < kot(cur->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
Node* newnode = cur; //保存一下插入节点的位置
cur->_parent = parent; //但这里就,结点就在树中了
//插入红结点，需要判断和调整
while (parent && parent->_col == RED) // 如果父亲存在且为红，说明有两个连续的红结点，需要继续调整
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left) // parent在grandparent的左边
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新
{
//变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上更新
cur = grandparent;
parent = grandparent->_parent;
}
else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色
{
if(cur == parent->_left)
{
// g(黑)
// p(红) --> p(黑)
// c(红) c(红) g(红)
// 右单旋
RotateR(grandparent);
//变色
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
// g(黑) g(黑)
// p(红) --> c(红) --> c(黑)
// c(红) p(红) p(红) g(红)
// 先左单旋，再右单旋
RotateL(parent);
RotateR(grandparent);
// 变色
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
else // parent在grandparent的右边
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED) // 如果uncle存在且为红，则要变色，继续向上更新
{
//变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上更新
cur = grandparent;
parent = grandparent->_parent;
}
else // 如果uncle不存在 或 uncle存在且为黑，则需要旋转调整+变色
{
if (cur == parent->_right)
{
// g(黑)
// p(红) --> p(黑)
// c(红) g(红) c(红)
// 左单旋
RotateL(grandparent);
//变色
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
// g(黑) g(黑)
// p(红) --> c(红) --> c(黑)
// c(红) p(红) g(红) p(红)
// 先右单旋，再左单旋
RotateR(parent);
RotateL(grandparent);
// 变色
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
void RotateL(Node* parent) //左单旋
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
Node* ppnode = parent->_parent; // 判断parent是根结点的情况
parent->_right = curleft;
if (curleft != nullptr)
{
curleft->_parent = parent;
}
cur->_left = parent;
parent->_parent = cur;
if (ppnode == nullptr)
{
//说明parent是根结点
_root = cur;
cur->_parent = nullptr;
}
else
{
//parent是子树的情况
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;
Node* ppnode = parent->_parent;
parent->_left = curright;
if (curright != nullptr)
{
curright->_parent = parent;
}
cur->_right = parent;
parent->_parent = cur;
//判断是否parent为根结点
if (ppnode == nullptr)
{
//改变根结点
_root = cur;
cur->_parent = nullptr;
}
else
{
//parent为子树
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
}
private:
Node* _root = nullptr;
};MySet.h
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K>
class set
{
struct SetKeyOfT
{
// 获取key中的key本身
const K& operator()(const K& key)
{
return key;
}
};
public:
//定义迭代器类型
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
//对于set插入的就是key
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); // 使用普通迭代器的pair来接收
// 使用普通pair中的迭代器first来构造当前的const迭代器
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}MyMap.h
#pragma once
#include"RBTree.h"
namespace MyCreate
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
// 获取pair<K,V>中的key
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
//普通迭代器
iterator begin() { return _t.begin(); }
iterator end() { return _t.end(); }
//const迭代器
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); //对于map插入的就是pair<k,v>
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K,V>, MapKeyOfT> _t;
};
}
感谢各位观看！希望能多多支持
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
35
0- 0
已为社区贡献2条内容
所有评论(0)