C++红黑树封装set和map代码详解
·
目录
我们都知道set和map的底层都是通过红黑树来实现的，前面讲解了红黑树的原理和代码，那么如何通过红黑树的代码封装实现set和map呢。
1.如何通过红黑树封装出set和map
set模型是key模型，只存关键字key，而map是key-value模型，存的的pair<K,V>，那如何通过模板参数来控制红黑树是哪种模型，实例化不同的模板。我们学习一下库里面是如何实现的。
这里面通过了多层的封装来实现了如果是set，红黑树的节点就存Key，如果是map，红黑树节点就存pair<K,V>。符合了set和map的模型。
红黑树的第一个模板参数就是关键字K的类型，第二个模板参数就是所要存储数据的类型，set底层就存储K，而map底层就存储pair<K,V>。
但是这里面还有一个问题，向set和map中插入节点时，set插入的是key，可以根据二叉搜索树的规则进行比较，而map插入的是pair<K,V>，是无法进行比较的，这个问题是如何来解决的呢？
这个就需要看红黑树的第三个模板参数了。
set中实现了一个内部类：
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};map中也实现了一个内部类：
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};这两个类都实现了operator(),其实就是一个仿函数，返回了关键字K的值，这样无论是map和set都可以根据二叉搜索树的规则进行比较找到要插入的位置了。
2.set和map迭代器的实现
下面的代码是迭代器实现的关键代码，其中最重要的就是operator++和operator--。通过三个模板参数可以控制该迭代器是const迭代器还是普通迭代器，其实就是通过传不同的参数类型来实现的，注意迭代器是像指针那样使用，用来方便遍历，但并不是指针，他的实质就是operator*，operator++，operator!=等函数重载实现的，函数重载的返回值是我们想要的结果。
//用来适配普通迭代器和const迭代器
template<class T,class Ptr,class Ref>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T,Ptr,Ref> self;
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_date;
}
Ptr operator->()
{
return &(_node->_date);
}
bool operator ==(const self& s) const
{
return _node == s._node;
}
bool operator !=(const self& s) const
{
return _node != s._node;
}
//这里走的是中序遍历 左 根 右
self& operator++()
{
//1.右不为空
if (_node->_right)
{
//右子树的最左节点
Node* rightMin = _node->_right;
while (rightMin->_left)
{
rightMin = rightMin->_left;
}
_node = rightMin;
}
//2.右为空 说明该子树已经遍历完了 向上找孩子是父亲左的那个祖宗节点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
parent = parent->_parent;
cur = cur->_parent;
}
_node = parent;
}
return *this;
}
//注意 这里是 右 根 左
self& operator--()
{
//1.左不为空
if (_node->_left)
{
//左子树的最右节点
Node* leftMax = _node->_right;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
_node = leftMax;
}
//2.左为空 说明这颗子树也已经遍历完了 找孩子是父亲右的那个祖宗节点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left == cur)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Node* _node;
};
operator++：
operator--：
3.如何确保map和set中K不能被修改的问题
set是如何保证key是不能被修改的呢？
我们看到set的普通迭代器就是const迭代器，但是我们不能只写const迭代器，因为我们用的时候还是set<K>::iterator it=s.begin()，s是一个set容器等之类的用法。我们这样写只是为了保证set中K的值不被修改。
map是如何保证key是不能被修改的呢？
我们能不能借用set的思路呢，显然是不可以的，如果和set一样，那么map中不仅key不能被修改，value也不能被修改，那不就不符合要求了。
map是这样实现的：
map中存的红黑树对应的红黑树节点所存的pair中的K是不允许被修改的是const的，对iterator解引用返回的是pair<const K,V>确保了Key不被修改。
4.map operator[]的实现
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
return ret.first->second;
}主要是修改insert函数的返回，通过调用insert函数来实现operator[]。
5.代码汇总
MyMap.h
#pragma once
#include"RBTree.h"
namespace my
{
template<class K,class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const 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();
}
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K,V>, MapKeyOfT> _t;
};
}MySet.h
#pragma once
#include"RBTree.h"
namespace my
{
template<class K>
class set
{
struct SetKeyOfT
{
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;
//加const才能编译通过
// 因为这里的iterator其实就是const_iterator，如果不加const普通对象调用返回普通对象的迭代器是无法赋值给const对象的迭代器的
//加const后，普通对象调用的也是const修饰的函数，返回的就是const迭代器 符合set key不能修改
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
//注意这里pair中的iterator实际为const_iterator 普通对象调用insert返回的是普通迭代器而不是const迭代器
//所以不能直接把普通迭代器直接返回给const迭代器
//我们需要在iterator中写一个构造函数，用普通迭代器构造const迭代器
pair<iterator, bool> insert(const K& key)
{
pair<typename RBTree<K, K, SetKeyOfT>::iterator,bool>ret=_t.insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}RBTree.h
#pragma once
#include<iostream>
using namespace std;
enum Col
{
BLACK,
RED
};
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& date)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _date(date)
, _col(RED)
{}
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
T _date;
Col _col;
};
//用来适配普通迭代器和const迭代器
template<class T,class Ptr,class Ref>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T,Ptr,Ref> self;
typedef __RBTreeIterator<T, T*, T&> Iterator; //注意Iterator和self是有区别的
/*场景 1：类被实例化为const迭代器时
此时 iterator 是 “普通迭代器类型”（非const），而当前类是const迭代器类。
这个构造函数就会成为转换构造函数—— 允许用 “普通迭代器” 构造 “const迭代器”，
从而支持const迭代器从普通迭代器那里获取节点信息（但const迭代器不会修改节点值）。
场景 2：类被实例化为普通迭代器时
此时 iterator 就是 “普通迭代器类型” 本身，
这个构造函数就是普通的拷贝构造函数—— 用于同一类型迭代器之间的拷贝（比如普通迭代器的复制）。*/
__RBTreeIterator(const Iterator& it)
:_node(it._node)
{}
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_date;
}
Ptr operator->()
{
return &(_node->_date);
}
bool operator ==(const self& s) const
{
return _node == s._node;
}
bool operator !=(const self& s) const
{
return _node != s._node;
}
//这里走的是中序遍历 左 根 右
self& operator++()
{
//1.右不为空
if (_node->_right)
{
//右子树的最左节点
Node* rightMin = _node->_right;
while (rightMin->_left)
{
rightMin = rightMin->_left;
}
_node = rightMin;
}
//2.右为空 说明该子树已经遍历完了 向上找孩子是父亲左的那个祖宗节点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
parent = parent->_parent;
cur = cur->_parent;
}
_node = parent;
}
return *this;
}
//注意 这里是 右 根 左
self& operator--()
{
//1.左不为空
if (_node->_left)
{
//左子树的最右节点
Node* leftMax = _node->_right;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
_node = leftMax;
}
//2.左为空 说明这颗子树也已经遍历完了 找孩子是父亲右的那个祖宗节点
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left == cur)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Node* _node;
};
//这里的T模板参数代表的是红黑树节点要存在的数据类型 如果是set就存K，如果是map则存pair<K,V>
//K模板参数就是map和set中的键
template<class K, class T,class KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T,T*,T&> iterator;
typedef __RBTreeIterator<T, const T*,const T&> const_iterator;
public:
iterator begin()
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return iterator(leftMost);
}
iterator end()
{
return iterator(nullptr);
}
iterator begin() const
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return iterator(leftMost);
}
iterator end()const
{
return iterator(nullptr);
}
Node* find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_date) > key)
{
cur = cur->_left;
}
else if (kot(cur->_date) < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
pair<iterator,bool> insert(const T& date)
{
if (_root == nullptr)
{
_root = new Node(date);
_root->_col = BLACK;
return make_pair(iterator(_root),true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
while (cur)
{
if (kot(cur->_date) > kot(date))
{
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_date) < kot(date))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur), true);
}
}
//找到要插入的位置 进行链接
cur = new Node(date);
Node* newNode = cur;
if (kot(parent->_date) > kot(date))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//进行调整 父亲节点存在且为红 才需要调整 默认插入的节点是红色的
while (parent && parent->_col == RED)
{
Node* gradeparent = parent->_parent; //gradeparent节点一定存在 否则不会进入这里 直接就插入成功了
if (parent == gradeparent->_left)
{
Node* uncle = gradeparent->_right;
//叔叔节点存在且为红
if (uncle && uncle->_col == RED)
{
//变色+继续向上调整
uncle->_col = parent->_col = BLACK;
gradeparent->_col = RED;
//向上调整 此时parent相当于cur
cur = gradeparent;
parent = cur->_parent;
}
//叔叔节点不存在 or 叔叔节点存在为黑
else
{
//旋转加变色
if (cur == parent->_left)
{
// g
// p
//c
RotateR(gradeparent);
parent->_col = BLACK;
gradeparent->_col = RED;
}
else
{
// g
// p
// c
RotateL(parent);
RotateR(gradeparent);
cur->_col = BLACK;
gradeparent->_col = RED;
}
break;
}
}
else
{
Node* uncle = gradeparent->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//变色+向上调整
uncle->_col = parent->_col = BLACK;
gradeparent->_col = RED;
cur = gradeparent;
parent = cur->_parent;
}
//叔叔不存在 or 叔叔存在且为黑
else
{
//旋转+变色
if (cur == parent->_right)
{
//g
// p
// c
RotateL(gradeparent);
parent->_col = BLACK;
gradeparent->_col = RED;
}
else
{
//g
// p
//c
RotateR(parent);
RotateL(gradeparent);
cur->_col = BLACK;
gradeparent->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newNode), true);
}
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curRight = cur->_right;
Node* ppNode = parent->_parent;
//进行链接
parent->_left = curRight;
if (curRight)
curRight->_parent = parent;
cur->_right = parent;
parent->_parent = cur;
if (ppNode == NULL)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = cur;
}
else
{
ppNode->_right = cur;
}
cur->_parent = ppNode;
}
}
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curLeft = cur->_left;
Node* ppNode = parent->_parent;
parent->_right = curLeft;
if (curLeft)
{
curLeft->_parent = parent;
}
cur->_left = 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;
}
}
private:
Node* _root = nullptr;
};
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
6
0- 0
已为社区贡献3条内容
所有评论(0)