【C++】map和set的模拟实现
2023-12-18 11:03:38
喜欢的点赞，收藏，关注一下把！
在前面几篇C++的博客，讲过了二叉搜索树，AVL树，红黑树。
今天我们就用红黑树模拟实现map和set。
那现在就有一个问题了。给你一颗红黑树你该如果用它模拟实现map和set呢？但是map是KV模型的，set是K模型的。难道分别给一颗红黑树照着改吗？
如果没有思路，我们不妨看一看库里是怎么实现的。
上图分别是我们的map和set，主要看它们传给红黑树第二个模板参数都是value_type，但是map的value_type是pair<const Key，T>，而set的value_type是Key。
我们都知道同一份模板，因为给的参数不同可以示例化不同的类。
所以第二个模板参数传的参数不同，那关于KV模型与K模型的问题就可以解决了，因此map和set底层也可以使用同一份红黑树类模板。
我们再看一个红黑树的库就知道它为什么这样给参数了。
红黑树第二个模板参数决定到底是map(KV模型)，set(K模型)。
那为什么还要传第一个参数Key呢？
这里主要因为find的存在，站在红黑树的角度，它不知道你给它传的到底是什么，就比如insert，上层传什么我就插入什么样值的节点，同样find上层传什么就按什么类型的值去查找。但是不管是K模型，还是KV模型，即使KV模型可以改变值，但是它改的是V而不是K。因此都可以用K去查找。
下面我们就用红黑树模拟实现map和set
enum Coloer
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Coloer _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_data < data)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_data > data)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(data);
cur->_col = RED;
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//调整
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;
}
else
{
if (cur == parent->_left)//情况二
{
RotaleR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三
{
RotaleL(parent);
RotaleR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotaleL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotaleR(parent);
RotaleL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void RotaleL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppNode == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void RotaleR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (ppNode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == ppNode->_left)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
private:
Node* _root = nullptr;
};
为了方便，传参的时候没有像库那样给。
//Map.h
namespace bit
{
template<class K,class V>
class map
{
private:
RBTree<K, pair<const K, V>> _t;
};
}
//Set.h
namespace bit
{
template<class K>
class set
{
private:
RBTree<K, K> _t;
};
}
下面我们来实现插入。
插入模拟实现
但是实现之前，有一个问题，插入是有比较的。
map给的是pair，set给的是key，而pair的比较规则是first不小于，就比较second（first是pair第一个参数的值,second是第二个参数的值），但是我们只想比较key。那该怎么办呢？
那我们就想办法改变一下，让map和set只比较key。这里当然不是重写一个pair的比较，而是给map和set分别写一个仿函数，也就是给红黑树传第三个模板参数。
//map.h
template<class K,class V>
class map
{
struct MapKeyofT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
private:
RBTree<K, pair<const K, V>,MapKeyofT> _t;
};
//set.h
template<class K>
class set
{
struct SetKeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
private:
RBTree<K, K,SetKeyofT> _t;
};
//RBTree.h
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return 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(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(data);
cur->_col = RED;
if (kot(cur->_data) < kot(parent->_data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//调整
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;
}
else
{
if (cur == parent->_left)//情况二
{
RotaleR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三
{
RotaleL(parent);
RotaleR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotaleL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotaleR(parent);
RotaleL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
红黑树的插入实现好了，map和set调用一下就可以了
//map.h
template<class K,class V>
class map
{
struct MapKeyofT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
bool Insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>,MapKeyofT> _t;
};
//set.h
template<class K>
class set
{
struct SetKeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool Insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K,SetKeyofT> _t;
};
插入暂时先讲到这里，这里还有一些问题，接下来学完迭代器在回来解决。
正向迭代器模拟实现+插入完整实现
先把红黑树迭代器实现好，然后map和set再去调用。
红黑树的迭代器和list迭代器实现方法是一样的，原生指针并不能解决问题，因此我们把它封装+运算符重载实现需要的迭代器。
这里补充说明一点，我们红黑树的结构与库里给的不一样。
库里红黑树有一个头结点，它的左指针指向最左边，右指针指向最右边。
这是因为，迭代器是一个中序，库中这样的设计很容易找到迭代器开始的位置和结束的位置。
而我们的红黑树没有头结点。就是正常的一颗红黑树。接下来迭代器的实现都是按照下图结构实现的。
鉴于有list迭代器模拟实现的底子，我们先实现一个简易的迭代器，然后再一步步加。
template<class T>
class _RBTreeIterator
{
public:
typedef RBTreeNode<T> Node;
Node* _node;
_RBTreeIterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &(_node->_data);
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T,class KeyofT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef _RBTreeIterator<T> iterator;
/。。。。。
}
目前我们迭代器还差一个++运算符重载，就可以使用了。
那红黑树应该如何实现这个++呢？
迭代器走的是中序，按照下图也就是说第一个位置应该是5。
按照中序左子树，根，右子树的走法，当我们第一个位置是5的时候。左子树和根都已经走过了。接下来就该右子树了。所以我们现在面临的就是右子树存在和空的两种情况。
右子树不为空， it在8的位置。
下一个位置就是10的位置。也就是下一个右子树最左节点。
右为空 it在7的位置
也就是说5，6都访问完了，下一个位置该访问8了。能直接写访问祖先吗？
那如果7下面还有一个位置，那不就是访问祖先的祖先了。所以不能就访问祖先。
可以这样想。左子树访问完了，该访问根了，而左子树根节点是这个树根的左孩子。只要满足这个条件，我们就找到下一个要访问的位置了。
1.右不为空，找下一个右子树最左节点
2.右为空，去找祖先（孩子是父亲左的那个祖先）
template<class T>
class _RBTreeIterator
{
public:
typedef RBTreeNode<T> Node;
Node* _node;
typedef _RBTreeIterator<T> Self;
_RBTreeIterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &(_node->_data);
}
Self& operator++()
{
//1.右不为空，找下一个右子树最左节点
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;//_node指向它
}
else//2.右为空，去找祖先（孩子是父亲左的那个祖先）
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)//走到最后parent为空
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
我们再把begin和end实现一下。
迭代器是一个中序，第一个有效数据位置就是5了，最后一个有效位置的下一个位置那就是nullptr。
template<class K, class T,class KeyofT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef _RBTreeIterator<T> iterator;
public:
iterator begin()
{
Node* left = _root->_left;
while (left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
/
}
接下来给map和set加上迭代器
//map.h
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;
bool Insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>,MapKeyofT> _t;
};
这里可能有些疑问加typename干什么，因为分不清
RBTree<K, pair<const K, V>, MapKeyofT>::iterator 是静态变量还是里面定义的类型。所以在前面加typename告诉编译器这是一个类型，等实例化之后再去取。
凡是没有实例化的类模板，编译器区分不清楚RBTree<K, pair<const K, V>, MapKeyofT>::iterator中iterator到底是静态变量还是类型，因为静态变量可以这样用，类型也可以这样用，加个typename告诉编译器这个类模板虽然没有实例化，这个是一个类型，你先让我过，等到类模板实例化了再去取。
//map.h
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;
bool Insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, pair<const K, V>,MapKeyofT> _t;
};
//set.h
template<class K>
class set
{
struct SetKeyofT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyofT>::iterator iterator;
bool Insert(const K& key)
{
return _t.Insert(key);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, K,SetKeyofT> _t;
};
迭代器目前没有问题，但真的就没有问题吗？
看看我们的set迭代器
普通迭代器当然可以修改值，但在set和map这里还能随意修改Key值吗，随意改之后还能保证是底层红黑树吗？
我们先看看库里是set迭代器怎么实现的。
库里set普通迭代器和const迭代器用的都是红黑树的const迭代器。
所以我们把红黑树的迭代器补充完整。
template<class T,class Ref,class Ptr>
class _RBTreeIterator
{
public:
typedef RBTreeNode<T> Node;
Node* _node;
typedef _RBTreeIterator<T,Ref,Ptr> Self;
_RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
Self& operator++()
{
//1.右不为空，找下一个右子树最左节点
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;//_node指向它
}
else//2.右为空，去找祖先（孩子是父亲左的那个祖先）
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)//走到最后parent为空
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
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;
public:
iterator begin()
{
Node* left = _root->_left;
while (left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* left = _root->_left;
while (left->_left)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
再把set的迭代器改一下
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;
bool Insert(const K& key)
{
return _t.Insert(key);
}
//那这里该如何调用红黑树的const_iterator
//因为_t.begin();调用的红黑树的iterator
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, K,SetKeyofT> _t;
};
我们还是参考库，发现它加个const，为什么这样就行了呢？
因为权限可以缩小。所以不管是普通对象和const对象都可以调用。
所以set的正向迭代器，普通的或者的const都用着两个函数就可以了，不用单独在为const迭代器重写一个了。
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;
bool Insert(const K& key)
{
return _t.Insert(key);
}
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
private:
RBTree<K, K,SetKeyofT> _t;
};
这样不管set是普通还是cosnt迭代器，都不能修改Key值。
那map呢，也需要这样写迭代器吗？其实不用，map迭代器还和以往一样的写。
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;
bool Insert(const pair<const 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;
};
那map就不担心修改Key吗，请看上面pair<const K, V>，第一个参数我们就给了const ，所以你根本无法修改。 并且你只能修改V。同样这也符合我们的想法。
迭代器先讲到这里，还有一个反向迭代器最下面在实现。
我们接着把插入完善一下。
库里insert返回类型是pair，而我们自己写的只有bool。
insert返回类型的意思是。当成功插入时iterator指向最新插入的节点，bool设为true。插入失败时也就是插入相同的key，iterator指向已经插入过的节点。bool设为false。
//RBTree.h
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->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur),false);
}
}
//这里要重写申请一个指针，记录当前插入节点
//否则下面调整情况uncle是红色节点,cur会变
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(cur->_data) < kot(parent->_data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//调整
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;
}
else
{
if (cur == parent->_left)//情况二
{
RotaleR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三
{
RotaleL(parent);
RotaleR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotaleL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotaleR(parent);
RotaleL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode),true);
}
map和set也改一下
//map.h
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;
pair<iterator,bool> Insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
//set.h
typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;
pair<iterator,bool> Insert(const K& key)
{
return _t.Insert(key);
}
但是改完就出事了。
set的插入出现了问题，返回时类型不匹配。而map没问题。
这是因为，set的iterator用的是红黑树的const_iterator，而_t.Insert(key)，调用底层的红黑树插入还用的是iterator所导致类型不匹配的问题。
至于map的insert没问题，那是红黑树的迭代器怎么用，它就怎么样的。
对于map和set出现这样的问题。这是因为它们底层用的是同一个黑红树模板，我们遇到这个问题，库肯定也遇到这个问题。
参考库怎么解决的
库里并不是还像刚才遇到迭代器问题那样，在后面加个const。
而是用同类型的iterator接收insert返回的值，然后在返回时，匿名构造一个pair。而这个pair里所用的就是const_iterator。这样就解决了返回时类型不匹配的问题。
那它是如何将iterator构造成const_iterator
看看库里怎么做到的。
乍看这是一个拷贝构造。它真的是吗？我们也写一个拷贝构造看看。
但还是有问题。那它到底是什么？如何将普通迭代器转换成const迭代器。
好了不卖关子，这个关键还是在typedef出一个iterator
我们传第一个参数是T给的Value，这里就相当于是<T,T&,T*>，
而下面这个函数，当你用的是同一类型的迭代器这是拷贝构造。当你用的是不同类型的迭代器，这里相对于构造。
这里就是调用那个构造函数把iterator构造成const_iterator。
把set的插入修改一下。再把刚才的那个函数填上，就解决返回时类型不匹配的问题
//set.h
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);
}
接下来我们把map中的 [ ]接口实现一下。
map的[ ]接口模拟实现
我们在使用map的[ ]接口方便的很，既可以插入，修改，也可以查找(存在才能查否则就是插入)。那实现一下把。这一部分在【C++】map和set的使用及注意事项的map接口使用有详细结束。这里就只把它实现出来。
V& operator[](const K& key)
{
//插入key，返回V，然后就可以修改V了
pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
return ret.first->second;
}
正向迭代器完整代码+反向迭代器模拟实现
反向迭代器是一个容器适配器，正因为有了正向迭代器我们可以适配出一个反向迭代器。
更为详细内容情况看这里【C++】priority_queue模拟实现+仿函数+反向迭代器
反向迭代器里面的运算符重装调用正向迭代器的就行了。
template<class iterator, class Ref, class Ptr>
class _RBTreeReverseIterator
{
public:
typedef _RBTreeReverseIterator<iterator, Ref, Ptr> Self;
public:
_RBTreeReverseIterator(iterator it)
:_it(it)
{}
private:
iterator _it;
};
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;
//反向迭代器
typedef _RBTreeReverseIterator<iterator, T&, T*> reverse_iterator;
typedef _RBTreeReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
///
}
我们先把正向迭代器还差的一些东西补上。
主要补充的就是- -
其实 - -完全就是 ++反过来了
it在15的位置，说明这颗以15为根的子树，根和右子树已经访问过了，该访问左子树了，左子树分为两个情况，左子树存在，不存在
1.左不为空，下一个左子树最右节点
2.左为空，去找祖先（孩子是父亲右的那个祖先）
正向迭代器完整代码
template<class T,class Ref,class Ptr>
class _RBTreeIterator
{
public:
typedef RBTreeNode<T> Node;
Node* _node;
typedef _RBTreeIterator<T,Ref,Ptr> Self;
typedef _RBTreeIterator<T, T&, T*> iterator;
_RBTreeIterator(Node* node)
:_node(node)
{}
_RBTreeIterator(const iterator& s)
:_node(s._node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
//++it
Self& operator++()
{
//1.右不为空，找下一个右子树最左节点
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;//_node指向它
}
else//2.右为空，去找祖先（孩子是父亲左的那个祖先）
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)//走到最后parent为空
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//it++
Self operator(int)
{
Self tmp(*this);
operator++();
return tmp;
}
//--it
Self& operator--()//1.左不为空，下一个左子树最右节点
{
if (_node->_left)
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else//2.左为空，去找祖先（孩子是父亲右的那个祖先）
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//it--
Self operator--(int)
{
Self tmp(*this);
operator--();
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& t)
{
return _node == t._node;
}
};
下面开始写反向迭代器，其实很简单直接复用就行了。
++，rit最开始指向15的位置，它++，就相当于正向迭代器的- -
反向迭代器完整代码
template<class iterator, class Ref, class Ptr>
class _RBTreeReverseIterator
{
public:
typedef _RBTreeReverseIterator<iterator, Ref, Ptr> Self;
public:
_RBTreeReverseIterator(iterator it)
:_it(it)
{}
Ref operator*()
{
return *_it;
}
Ptr operator->()
{
return &(operator*());
}
//++it
Self& operator++()
{
--_it;
return *this;
}
//it++
Self operator++(int)
{
Self tmp(*this);
++_it;
return tmp;
}
//--it
Self& operator--()
{
++_it;
return *this;
}
//it--
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const Self& s)
{
return _it != s._it;
}
bool operator==(const Self& s)
{
return _it == s._it;
}
private:
iterator _it;
};
我们再把红黑树，map，set反向迭代器补充一下
//RBTree.h
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;
//反向迭代器
typedef _RBTreeReverseIterator<iterator, T&, T*> reverse_iterator;
typedef _RBTreeReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
public:
iterator begin()
{
Node* left = _root->_left;
while (left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* left = _root->_left;
while (left->_left)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
reverse_iterator rbegin()
{
Node* right = _root;
while (right && right->_right)
{
right = right->_right;
}
return reverse_iterator(right);
}
reverse_iterator rend()
{
return reverse_iterator(nullptr);
}
const_reverse_iterator rbegin() const
{
Node* right = _root;
while (right && right->_right)
{
right = right->_right;
}
return const_reverse_iterator(right);
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(nullptr);
}
/
}
//map.h
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;
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::reverse_iterator reverse_iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::const_reverse_iterator const_reverse_iterator;
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;
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
const_reverse_iterator rbegin() const
{
return _t.rbegin();
}
const_reverse_iterator rend() const
{
return _t.rend();
}
private:
RBTree<K, pair<const K, V>,MapKeyofT> _t;
};
//set.h
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;
typedef typename RBTree<K, K, SetKeyofT>::const_reverse_iterator reverse_iterator;
typedef typename RBTree<K, K, SetKeyofT>::const_reverse_iterator const_reverse_iterator;
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);
}
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
reverse_iterator rbegin() const
{
return _t.rbegin();
}
reverse_iterator rend() const
{
return _t.rend();
}
private:
RBTree<K, K,SetKeyofT> _t;
};
关于map和set的模拟实现就到这里，还有一些接口没有实现，感兴趣的小伙伴可以自己动手实现。
文章来源:https://blog.csdn.net/fight_p/article/details/135034124
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！