【map和set的封装】

news/2024/10/31 1:33:07/

文章目录

  • 前言
  • 1 大致框架
  • 2 迭代器
  • 3 map和set的封装


前言

上篇博客已经讲解了红黑树插入的模拟实现,这篇文章的目的是利用上节课讲解的底层实现来封装map和set.参考代码借鉴的是STL SGI版本3.0


1 大致框架

首先我们来看看源码里面怎么定义的:

在这里插入图片描述

在这里插入图片描述从源码中我们不难发现map和set底层是用了一颗红黑树来封装的,并且模板参数与我们自己想的不太一样。set中传入的是<K,K>,map中传入的是<K,Pair<K,V>> (其他参数可以暂时不用考虑)
大家想想,为什么要这么设计❓这样设计的好处是什么❓
我们传入两个参数的目的就是为了用一颗红黑树封装map和set,也就是第二个参数我们可以理解为给的是一个T,T可以接受上层的传入来的参数。

那可能大家又有了疑问?那为啥要传入第一个参数呀?直接用第二个参数不行吗?
大家别忘了,我们使用find接口和erase接口是用的参数是啥?是不是无论是map还是set都是用的是K,所以这个参数我们必须的传。

但是这样做问题又来了,上层是如何知道我们比较结点大小的时候比较的是K,还是Pair<K,V>?
所以我们还得再传入一个模板参数,不妨给一个仿函数,通过仿函数来取得数据。


2 迭代器

同样,迭代器往往就是容器中最精华的部分,所以迭代器的设计也是有着举足轻重的地位,这里迭代器的设计思路类似于链表的迭代器,不过具体实现却是比链表更加复杂,接下来我们便来看看。

* -> == !=这些运算符重载好说,实现起来不难,关键是如何实现++重载?–重载?
给了一颗红黑树,如下图,我们如何走到下个结点呢?
在这里插入图片描述我们不妨采用这种思路:如果右子树存在,就找右子树的最左结点;右子树不存在,需要判断是否孩子是父亲的右节点,是的话还要往祖宗向上找,直到找到孩子是父亲的左节点为止。

我们不妨来举一个例子:假如当前在1这个结点,由于1的右子树存在,且6这个结点恰好是1右子树的最左节点,所以++后应该走到了6;假如现在当前结点为11,由于11的右子树为空,所以要往上找,直到找到孩子是父亲左节点为止:11往上找父亲为8,8的右孩子是11,所以没有找到孩子是父亲右孩子的情况继续往上走,孩子为8,父亲为13,13的左孩子为8,随意此时找到了孩子是父亲左的那一个,所以++后就走到了13这个位置。

同理- -运算符的重载可以与++运算符重载反着来,思路类似:如果左子树存在,就找左子树的最右结点;左子树不存在,需要判断是否孩子是父亲的右节点,是的话还要往祖宗向上找,直到找到孩子是父亲的右节点为止。
这个我就不再分析了,大家可以自行分析。

为了方便,我们将用nullptr来构造找到了末尾,不用继续找了,但是STL中并不是这样设计的,是用了一个头结点来连接:
在这里插入图片描述走到了头结点就表示找到了末尾。
用这种方式会稍微麻烦些,不过总体也是不难的。

然后我们自己便可以实现一份迭代器了:

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& self)const{return _node == self._node;}bool operator!=(const Self& self)const{return _node != self._node;}Self& operator++(){if (_node->_right)//右子树存在,就找右子树的最左结点{Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else{//右子树不存在,需要判断是否孩子是父亲的右节点,是的话还要往祖宗向上找,直到找到//孩子是父亲的左节点为止Node* child = _node;Node* parent = _node->_parent;while (parent && parent->_right == child){child = parent;parent = parent->_parent;}//走到这里说明找到了孩子是父亲的左节点或者//孩子已经是根节点了(表明在根节点也没有找到,说明已经遍历完成了)_node = parent;}return *this;}Self& operator--(){if (_node->_right)//左子树存在,就找左子树的最右结点{Node* right = _node->_left;while (left->_right){left = left->_right;}_node = right;}else{//左子树不存在,需要判断是否孩子是父亲的左节点,是的话还要往祖宗向上找,直到找到//孩子是父亲的右节点为止Node* child = _node;Node* parent = _node->_parent;while (parent && parent->_left == child){child = parent;parent = parent->_parent;}//走到这里说明找到了孩子是父亲的右节点或者//孩子已经是根节点了(表明在根节点也没有找到,说明已经遍历完成了)_node = parent;}return *this;}
};

3 map和set的封装

其他的都好说,关键是如何实现set不能够修改,而map中可以修改Val;
我们可以采取这种方式:set的普通迭代器我们用上层的const迭代器实现,set的const迭代器我们也用上层的const迭代器实现。map的话我们只需要将==第二个模板参数给pair<const K,V>==就可以了。

set.hpp:

namespace grm
{template<class K>class set{struct SetOfKey{const K& operator()(const K& k){return k;}};private:RBTree<K, K, SetOfKey> _rbTree;//typedef typename RBTree<K, const K, SetOfKey>::Iterator iterator;//不能够像上面这样传入参数typedef typename RBTree<K, K, SetOfKey>::ConstIterator iterator;typedef typename RBTree<K, K, SetOfKey>::ConstIterator const_terator;public:iterator begin(){return _rbTree.begin();}iterator end(){return _rbTree.end();}const_terator begin()const{return _rbTree.begin();}const_terator end()const{return _rbTree.end();}pair<iterator, bool> insert(const K& k){return _rbTree.insert(k);}};

map.hpp:

namespace grm
{template<class K, class V>class map{struct MapOfKey{const K& operator()(const pair<const K, V>& kv){return kv.first;}};private:RBTree<K, pair<const K,V>, MapOfKey> _rbTree;public:typedef typename RBTree<K, pair<const K, V>, MapOfKey>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapOfKey>::ConstIterator const_iterator;iterator begin(){return _rbTree.begin();}iterator end(){return _rbTree.end();}const_iterator begin()const{return _rbTree.begin();}const_iterator end()const{return _rbTree.end();}pair<iterator, bool> insert(const pair<K,V>& kv){return _rbTree.insert(kv);}V& operator[](const K& k){pair<iterator, bool> tmp = insert(make_pair(k,V()));return tmp.first->second;}};

但是这样实现set时也还是会遇到问题:那就是我们用了普通迭代器来构造const迭代器,这样势必是会报错的,有什么处理方式吗?
我们可以在迭代器中多给出一个构造:

//模板参数是普通迭代器就是拷贝构造//模板参数是const迭代器就是用普通迭代器构造const迭代器__RBTreeIterator(const __RBTreeIterator<T,T&,T*>& it):_node(it._node){}

这样就能够解决问题了。

如果大家还有哪里不懂的地方可以私信博主,有需要的可以参考博主的码云:
【码云地址】



http://www.ppmy.cn/news/170763.html

相关文章

知识图谱涉及技术点分析

文章目录 数据从哪里来为什么通常将知识图谱划分到NLP领域&#xff1f;常用NLP技术点分析只是NLP任务吗&#xff1f;graph embedding知识融合业务还是算法&#xff1f;知识图谱组成 数据从哪里来 是手动提取关系吗&#xff1f;数据很多&#xff0c;关系确难涉及大量NLP技术关系…

【Docker】什么是Docker,它用来干什么

作者简介&#xff1a; 辭七七&#xff0c;目前大一&#xff0c;正在学习C/C&#xff0c;Java&#xff0c;Python等 作者主页&#xff1a; 七七的个人主页 文章收录专栏&#xff1a; 七七的闲谈 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01;&#x1f496;&#x1f…

飞利浦linux手机,LINUX超长待机 百万像素飞利浦968评测

前言 进入2005年后&#xff0c;飞利浦一方面在努力维护着自己“超长时间待机神话”的形象&#xff0c;另一方面也逐渐开始向多元化发展。而在这其中&#xff0c;飞利浦968无疑是最引人注目的一款。它不仅是“飞机”中第一款采用了LINUX开放式操作系统的智能手机&#xff0c;同时…

太阳能手机可创超长待机时间 能成为未来主流?

差异化竞争促使另类手机层出不穷&#xff0c;比如商务通手机、信息安全手机、隐形手机。近日&#xff0c;恒基伟业推出全球首款光能 手机 &#xff0c;一时间震动业界&#xff0c;赚足眼球。将太阳能技术移植到手机上是否有着巨大的应用价值&#xff1f;其技术难点在哪里&#…

挂脖式运动蓝牙耳机什么牌子的好、运动蓝牙挂脖耳机推荐

我们都知道运动耳机的出现是为了人们在运动中更好的使用,减少掉落、进水等问题而出现的,所以一般的运动耳机也都具备无线、防水以及防汗功能。常见的款式大多是挂耳式的,较为适合经常运动跑步和热爱健身的人群使用。那么,市面上琳琅满目的运动耳机那么多,究竟哪个好呢?今天小编…

超长待机支持高清播放 Viliv新款MID

Viliv新款MID将在今年年初发售&#xff0c;该款MID最大亮点是可以播放1080P格式的高清视频&#xff0c;内置GPS导航。外观上采用全黑金属设计&#xff0c;附带基本功能按键&#xff0c;是一款配置高端的MID产品。 该款MID采用1.33GHz的Atom处理器&#xff0c;1GB内存&#xff0…

续航时间长的蓝牙耳机有哪些?续航时间超长的蓝牙耳机测评

在选择蓝牙耳机时&#xff0c;我们肯定需要考虑很多因素。比如说蓝牙耳机的连接速度&#xff0c;连接稳定性和音质、降噪等等。在综合比较了这些因素之后&#xff0c;小编选择了几款较好的耳机&#xff0c;在这里给大家介绍一下。 NO1&#xff1a;南卡A2降噪蓝牙耳机&#xff…

手机声音同步到另一部手机_手机冻冰箱总共分几步?AGM推出金嗓子手机H2,超大声音超长待机...

前言 前两天母亲大人的小米手机再一次落地而碎&#xff0c;是时候给换一个新手机了&#xff0c;因为传统智能手机声音比较小&#xff0c;又不禁摔。这回打算入手一个三防手机&#xff0c;对游戏和拍照性能要求不高&#xff0c;主要是声音要大&#xff0c;户外打电话、语音聊天也…