您现在的位置是:首页 >技术交流 >【C++】用红黑树迭代器封装map和set网站首页技术交流
【C++】用红黑树迭代器封装map和set
封装有点难 - . -
前言
因为我们要将红黑树封装让map和set使用,所以我们要在原来的基础上将红黑树代码进行修改,最主要的是修改模板参数,下面我们直接进入正题:
一、红黑树原先代码的修改
首先我们拿出STL中的源代码,看看大佬是如何进行封装的:
我们可以看到在STL中map的模板参数是Key和T,这没毛病很显然是KV结构,那么底层红黑树key_type和value_type是什么?其中Key是KeyType的别名,value是pair的别名,也就是说map有两个模板参数一个是key,一个是为pair的value,这个pair大家要记住也是一个键值对。那么这到底是怎么回事呢?别急,我们再看看set的实现然后给出答案:
我们可以看到,set整体的模板参数还是Key,但是在底层红黑树的参数变成了key_type和value_type,而这两个参数都是同一个Key重命名而来的,也就是说set的底层用红黑树是两个Key做模板参数,到这其实我们应该是明白了,真正在红黑树中存储的是key还是kv结构是由第二个模板参数Value_type来决定的,因为map中的value_type是pair,set中的value_type是key.那么第一个参数key有什么用呢?为什么要多传这一个参数呢?因为在我们用find查找以及erase删除接口的时候,我们都是用的key值啊,举个例子,map中的find接口要查找不能用pair直接查找吧,我们是用的pair中的first来进行查找,但是由于set是key可以直接使用,pair要拿到first才能查找,所以干脆就多传一个参数,这个参数就是我们查找呀什么的那些接口所需要的类型,下面是红黑树的源码:
我们可以看到红黑树的节点确实通过一个模板参数来控制,然后红黑树中两个模板参数,源码中实现了一个头结点和记录节点的多少,我们没有实现所以不用管这个,了解了以上知识我们就可以将之前的红黑树代码先修改一下:
template <class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{
}
};
首先将红黑树节点修改完毕,我们将原来的pair变成一个data类型,这个类型在set中是key,在map中是pair。
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);
if (parent->_data < data)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//开始红黑树
//...........省略
}
上面是我们将红黑树进行了修改,因为我们将红黑树的节点模板参数设为T,所以我们在红黑树中需要修改一下将第二个参数设置为T,然后insert函数也需要改变,因为我们直接插入的是一个pair值,但是很明显这样是解决不了set的问题的,所以我们插入的是一个T类型的data,这个T类型的data就是红黑树节点中存储的值,将这些修改完毕后我们就可以实现map和set了,下面我们先实现set:
namespace sxy
{
template <class K>
class set
{
public:
bool insert(const K& key)
{
return _t.insert(key);
}
private:
RBTree<K, K> _t;
};
void test_set()
{
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
/*set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}*/
}
}
如我们之前所讲,set只需要一个参数key,但是在底层红黑树中是需要传两个K的,然后用红黑树的插入接口等即可,下面我们先演示一下:
展开后2的左边是1右边是3,下面我们在简单实现一下map的:
namespace sxy
{
template<class K, class V>
class map
{
public:
bool insert(const pair<const K, V>& kv)
{
return _t.insert(kv);
}
private:
RBTree<K, pair<const K, V>> _t;
};
void test_map()
{
map<int, int> mp;
mp.insert(make_pair(1, 1));
mp.insert(make_pair(2, 2));
mp.insert(make_pair(3, 3));
}
}
在map中我们需要的是KV结构,然后再调用底层红黑树的时候第一个参数为K,第二个参数为pair类型,pair的first加上const是因为map中的first不允许修改,但是second可以修改。同样我们跑起来演示一下:
可以看到2的左边是1,1,右边是3,3.下面我们总结一下,map和set在用底层红黑树的时候set会多用一个模板参数,理由是:
1.第一个参数拿到单独K的类型,因为find,erase这些接口函数的参数是K。
2.第二个模板参数决定了树的节点里面存什么。。 K or KV
测试完毕后我们讲解源码中红黑树的第三个模板参数KeyOfT,这个参数实际上就是一个仿函数,通过一个仿函数将pair中的first拿到或者直接拿到set中的key。
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> _t;
};
可以看到set中的仿函数就是直接返回key。
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>> _t;
};
map中的仿函数需要返回pair中的first,下面我们将红黑树的模板参数加入KeyOfT:
template <class K, class T, class KeyOfT>
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;
KeyOfT kot;
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(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
可以看到我们在insert函数中加入了kot这个仿函数,这个仿函数重载了()符号,所以我们用kot(cur->data)就拿到了set中的key或者map中的pair.first,对了,前面我们没加仿函数但是程序可以运行的原因是:pair是有自己的比较方法的,也是通过仿函数实现的,当first不相等就用first比较,当first相等就用second比较,但是这不是我们想要的,我们想要的只是通过first比较,所以我们用仿函数来控制确定只拿出first。因为加入了一个模板参数所以map和set肯定是需要修改的:
将这里的仿函数加入后我们就正式将红黑树部分搞定了,下面画张图让大家理解一下set和map如何调用红黑树的:
下面就开始实现迭代器了。
二、红黑树迭代器的实现
迭代器的实现同样我们参考源码:
我们可以看到源码中对于普通迭代器和const迭代器都用了const迭代器,这也就证明了为什么我们在使用map和set的时候不可以用迭代器修改其Key值,rep_type是红黑树的迭代器,也就是说map和set都用的红黑树内部的迭代器,当我们要使用模板类的使用要用typename否则编译器会报错以为没有实现迭代器,加了typename就会等模板实例化后。
我们可以看到,红黑树的迭代器在源码中typedef了很多,下面我们就实现一下:
因为红黑树每一个都是节点,所以我们的迭代器实现和list的迭代器一样,底层用一个节点就解决了:
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++()
{
//....
}
};
这里的Ref就是T&,Ptr就是T*,这里的玩法我们在list的迭代器就玩过了,这样可以让模板生成普通迭代器和const迭代器,如果调用者传的const T&,const T*那么就是const迭代器。然后迭代器的构造就是通过一个节点来构造,*(解引用)就是返回节点的data值的引用,->如果是pair类型本来需要两次->才能访问到pair的first但是我们重载后一个->就能访问到节点中的data,并且我们返回的是T*,引用的本质也是指针所以直接返回引用。下面我们就实现迭代器中的++:
首先我们要知道,红黑树的迭代器的begin位置是在中序遍历的第一个位置(因为中序才能排序),所以我们直接看下图:
对于下面这张图我们的it就是迭代器,在中序的第一个位置,++后我们要访问6这个位置,这个位置有什么要求呢?首先如果1这个节点有右子树并且6有左子树还需要依次往6这个节点的左子树走(因为中序遍历:左子树,根,右子树),如果1这个节点没有右子树那么++后的节点是8所以我们要判断的就是是否有右子树,如果有就访问右子树的最左节点,如果没有就要回溯,回溯也并不简单我们用代码来演示:
Self& operator++()
{
if (_node->_right)
{
Node* cur = _node->_right;
while (cur && cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
我们直接说else语句中的代码,当发现右边为空时那就说明该向上回溯了,而我们通过图可以看到:当迭代器在6这个位置,正好6的右子树为空,++只能向上走,向上的时候1是parent是存在的并且1的右子树是cur,所以向上继续找parent变成8cur变成1,这个时候不满足8的右边是cur,所以这个时候parent的节点就是++后的节点,找到后返回*this(*this就是++后的迭代器).下面我们将迭代器放到红黑树中:
template <class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, T&, T*> iterator;
public:
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
begin我们已经说过是中序的第一个节点,拿到中序第一个节点后直接返回用这个节点构造的迭代器即可。end我们直接返回由空指针构造的迭代器即可,因为end必须是最后一个节点的后一个位置,而最后一个节点的后一个位置本来也是空。(这里源代码中是增加一个高于根节点的头结点,让end最后指向头结点,但是我们的nullptr也可以完成任务只不过不能从end--回到上一个节点(因为end为空)),而源代码是可以让end--在返回上一个节点的)接下来我们将迭代器放到set中看一下:
template <class K>
class set
{
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
这里我们先用的普通迭代器,因为const迭代器还有一个很难理解的问题需要我们详细讲解。因为这里用了红黑树的迭代器,所以红黑树中我们对于迭代器的typedef都放在public中,否则会有权限的问题:
可以看到我们的迭代器没毛病,下面我们再用一下map:
template<class K, class V>
class map
{
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
void test_map()
{
map<int, int> mp;
mp.insert(make_pair(1, 1));
mp.insert(make_pair(2, 2));
mp.insert(make_pair(3, 3));
for (auto& e : mp)
{
cout << e.first << ":" << e.second << endl;
}
cout << "-------------------------------- -" << endl;
map<int, int>::iterator it = mp.begin();
while (it != mp.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
}
可以看到我们的迭代器用于set和map都没问题,然后刚刚我们没有实现迭代器--现在实现一下:
--直接就是++的相反,比如++是左中右遍历,那么--就是右中左遍历:
Self& operator--()
{
if (_node->_left)
{
Node* cur = _node->_left;
while (cur && cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
对于--大家让迭代器等于8或者等于6让其随着代码走一遍就知道正确与否。
有了迭代器后,我们就可以将map的[]运算符实现出来了,下面我们先修改insert函数:
pair<iterator,bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
//根节点必须为黑色
_root->_col = BLACK;
//只有一个根节点,插入成功后返回根节点所在的迭代器
return make_pair(iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot;
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
{
//cur找到与要插入节点相等的节点,但由于相等没有插入,返回cur这个位置的迭代器
return make_pair(iterator(cur), false);
}
}
cur = new Node(data);
Node* newnode = cur;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//开始红黑树
//省略没有修改的地方......
_root->_col = BLACK;
//本来应该返回新插入节点的迭代器,但是由于cur在进入红黑树位置会发生调整,所以提前保存cur
return make_pair(iterator(newnode), true);
}
我们详细的介绍过map中的[]运算符,这个运算符可以实现:如果key不在就插入,如果在就返回second的引用(map中的second可以修改我们反复说过),唯一需要注意的地方是最后要返回新插入节点的迭代器,但是新节点在红黑树调整的过程中cur发生了变化,所以提前记录cur,最后返回之前记录的cur的这个节点即可。
将map和set中insert的返回值修改完后我们实现[]:
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
return ret.first->second;
}
首先[]要返回pair中second的引用,而second的模板参数是V所以返回值是V&,然后【】的插入是根据key来确定的,如果key存在bool为false,如果不存在就插入,但是不管怎么样我们都返回second,再插入的时候我们刚开始不知道K,V中的V具体是多少,所以我们给一个匿名对象去初始化即可,返回值这里就用到我们以前的知识了,首先ret是一个pair,先拿到pair中的迭代器,因为map迭代器里面存放的是pair,所以代码应该是:ret.first->_node->_data->second,但是由于我们重载了->符号所以可以直接访问到_data,然后返回_data->second即可下面我们测试一下是否成功:(如果对于->还有问题可以看一下下面第一张图:)
it是一个迭代器,一旦通过->符号就拿到了红黑树节点中的_data,map中data存放的是KV模型,所以直接访问first,second。
void test_map2()
{
string arr[] = { "苹果","西瓜","西瓜","梨","葡萄" };
map<string, int> mp;
for (auto& e : arr)
{
mp[e]++;
}
for (auto& m : mp)
{
cout << m.first << ":" << m.second << endl;
}
}
通过运行结果我们也发现是没问题的,接下来我们就要实现const迭代器了,首先先加入const迭代器:
const_iterator begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
然后我们先用set做一下测试:
运行起来报错了:
错误原因在这里:
我们已经将set的普通迭代器修改为红黑树中的const迭代器,但是红黑树中的begin()是一个普通迭代器,iterator经过typedef已经变成const迭代器,所以发生了报错,当然有人发现:
将set的第二个参数加个const就可以,确实是这样,但是map该怎么办呢?map能在pair前面加上const吗?很明显是不能的,因为map中只有key也就是first不能修改,second是可以修改的,这该怎么办呢?下面我们参考一下源代码:
首先set里面普通迭代器用const迭代器实现,const迭代器也用const迭代器来实现,并且begin和end()也没做任何修改,所以这里应该也面临着和我们一样的问题,那就是如何解决普通迭代器转化为const迭代器,我们继续看:
我们可以看到源码中的迭代器比我们的迭代器多了一个构造函数,首先我们区分一下,iterator里面的参数都是不加const的所一iterator是普通迭代器,而self里面的参数是ref和ptr,当传参为const类型时self就变成了const迭代器,当传参为不带const就是普通迭代器,而最后的这个构造函数的参数是一个普通迭代器,那有什么作用呢?其实是这样:
1.当我本身的迭代器是普通迭代器时,参数也是一个普通迭代器这个时候就是一个拷贝构造函数。
2.当我本身是一个const迭代器时,参数是一个普通迭代器,这个时候就变成了用普通迭代器构造const迭代器,也就是说让普通迭代器和const迭代器之间进行转化了,再想想我们刚刚的报错,无法从普通迭代器转化为const迭代器,用上这个构造函数不就可以将红黑树中的普通迭代器转化为const迭代器了吗。 (现在搞懂这个构造函数为什么不用self来做参数了吧,因为self的参数如果是const那么self就变成const迭代器,那还如何转化呢)
了解了以上知识我们直接加一个构造函数就可以了,一定要注意这个构造函数的参数是普通迭代器:
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)
{
}
RBTreeIterator(const RBTreeIterator<T, T&, T*>& it)
:_node(it._node)
{
}
有了这个构造函数运行起来就不会报错了,下面我们看看map的迭代器:
我们可以看到map中普通迭代器还是普通迭代器,const迭代器是const迭代器。
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_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
这样我们就搞定了set和map的底层,以上就是本文的所有内容了。
总结
对于这里的难点我认为迭代器确实是有难度的,并且有些方法也不是我们普通人可以想到的,所以要多看优秀的代码才能提升自己。