C++(初阶)(二十)——封装实现set和map
二十,封装实现set和map
- 二十,封装实现set和map
- 1,参数类型
- 2,比较方式
- 3,迭代器
- 3.1,普通迭代器
- 3.2,const迭代器
- 3.3,set_map的迭代器实现
- 4,插入和查找
- 5,特别的:map支持[]
- 6,完整代码
1,参数类型
本篇介绍模拟实现set和map的方法,由于set和map的底层是红黑树,所以需要先实现红黑树,此处的重点是封装上层的set和map。
感兴趣的可以看一下红黑树的实现:
链接: https://blog.csdn.net/2401_88328558/article/details/148177722?fromshare=blogdetail&sharetype=blogdetail&sharerId=148177722&sharerefer=PC&sharesource=2401_88328558&sharefrom=from_link
在之前实现的红黑树中,我们默认参数类型是pair<K, V>
也就是k_value结构,而要实现泛型,就不知道参数到底是K还是pair<K, V>,所以我们将数据类型写作T。
template<class T>
struct RBTreeNode
{// 这⾥更新控制平衡也要加⼊parent指针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), _col(BLACK){}
};
2,比较方式
此时就出现了一个很明显的问题:在insert操作时,对数据的大小比较就失去了原本的意义。我们并不知道参数T到底是K还是pair<K, V>,因为pair<K, V>在比较大小时,默认⽀持的是key和value⼀起参与⽐较。
例如:
//我们之前比较大小的方式如下:
if (cur->_kv.first < kv.first)
{parent = cur;cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{parent = cur;cur = cur->_left;
}
显然此时的比较方式在参数T是K时,并不正确。那么如何改造?
在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT,然后RBTree中通过KeyOfT仿函数取出T类型对象中的key,再进行比较。
部分参考代码:
//set
template<class K>
class set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
private:// 第一个模板参数带const,保证key不能被修改RBTree<K, const K, SetKeyOfT> _t;
};//map
template<class K, class V>
class map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
private://pair<>可以修改,其中的K不能修改,使用const修饰RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};//红黑树
//实例化出对象kot
KeyOfT kot;//比较
if (kot(cur->_data) < kot(data))
{parent = cur;cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{parent = cur;cur = cur->_left;
}
3,迭代器
3.1,普通迭代器
其中实现的难点就是:operator++和operator–
3.1.1,首先要知道++的本质是移动到下一个顺序位置。举一个简单的例子:
此时有一棵如图所示的红黑树,当前结点为4这个结点,那经过++后,所得到的就是13结点的位置,再次++得到17,再次++就走到null。
经过扩展分析得到结论:++的核心是不看全局只看局部。如果右子树不为空,找到右子树中序遍历的第一个结点。
3.1.2,如果右子树为空,那么可以分析到父亲结点也已经访问完成,原因是:我们访问的顺序是中序遍历(左根右)。此时需要找到祖先结点,先向上更新结点,结束特征是孩子结点是父亲结点左子树的那个位置,此时的父亲结点就是我们需要找到的祖先结点。但是如果parent为空,当前树遍历结束,将空作为end()。
3.1.3,控制end()位置的方式:找到孩子结点是父亲结点左子树的那个位置,如果不是,那么更新结点位置,最后如果更新到root(根)结点,那么就走到了空结点,将空结点作为end()结点
3.1.4,关于–是和++非常类似的,核心是访问顺序是右根左。
那是否是可以it=end(),对迭代器–遍历呢?
1),是可以的,但是实现时end()结点为空了,可以改为哨兵位(红色),也就是需要进行++操作,但是如果进行旋转,会增加维护哨兵位的成本。
2),不改变end(),依旧为空,其实只需要找到最右结点即可,因为我们的目标就是找到整棵树的末尾结点,但是我们此时是没有根结点进行遍历的,所以需要先定义根结点之后传过来即可。
普通迭代器参考代码:
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}Node* _node;//--end()需要Node* _root;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){//++就是走到下一个位置if (_node == nullptr){//如果是空树,直接返回即可;}else if (_node->_right){//2,如果右子树不为空//那么需要的就是右子树中序遍历的第一个结点(最左结点)Node* minleft = _node->_right;while (minleft->_left){minleft = minleft->_left;}_node = minleft;}else{//3,右子树为空//那么下一个结点就是当前结点的祖先,是孩子结点是父亲左结点的那个祖先//比如:18->25->28->30,如果cur=28,那么我们要找到的祖先结点就是30// 18// 30// 25// 28Node* cur = _node;Node* parent = cur->_parent;//但是注意特殊情况:cur就是根结点,并且没有右子树while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}//此时parent就是我们要找的祖先_node = parent;}return *this;}Self& operator--(){//++就是走到上一个位置,逻辑和++相反if (_node == nullptr){//1,如果_node为空//等价于--end(),也就是返回最右结点Node* maxright = _root;while (maxright && maxright->_right){maxright = maxright->_right;}_node = maxright;}else if (_node->_left){//2,左子树不为空//中序左子树最右结点Node* left_maxright = _node->_left;while (left_maxright->_right){left_maxright = left_maxright->_right;}_node = left_maxright;}else{//3,左子树为空//找到孩子是父亲右孩子的那个祖先(父亲),如果_node是25,需要找到18// 18// 30// 25Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}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 RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> Iterator;Iterator Begin(){//begin()就是最左结点Node* minleft = _root;while (minleft->_left){minleft = minleft->_left;}return Iterator(minleft, _root);}Iterator End(){//end()就是最右结点的下一个结点,即空结点return Iterator(nullptr, _root);}
};
3.2,const迭代器
逻辑与普通迭代器没有区别,主要限制K不能修改,加const修饰即可。
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, const T&, const T*> ConstIterator;ConstIterator Begin() const{//begin()就是最左结点Node* minleft = _root;while (minleft->_left){minleft = minleft->_left;}return ConstIterator(minleft, _root);}ConstIterator End() const{//end()就是最右结点的下一个结点,即空结点return ConstIterator(nullptr, _root);}
};
3.3,set_map的迭代器实现
//set
template<class K>
class set
{
public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const 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();}
};//map
template<class K, class V>
class map
{
public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<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();}
};
4,插入和查找
依旧是对底层红黑树修改后,在set和map套一层壳。
//set
pair<iterator, bool> insert(const K& key)
{return _t.Insert(key);
}iterator find(const K& key)
{return _t.Find(key);
}//map
pair<iterator, bool> insert(const pair<K, V>& kv)
{return _t.Insert(kv);
}iterator find(const K& key)
{return _t.Find(key);
}
5,特别的:map支持[]
map要⽀持[]主要需要修改insert返回值⽀持,修改RBtree中的insert返回值为
pair<Iterator, bool> Insert(const T& data)
实例:
//return { Iterator(cur, _root), false };
//return { Iterator(newnode, _root), true };
//对于map需要重载[]
V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert({ key, V() });iterator it = ret.first;return it->second;
}
6,完整代码
my_set_my_map