【map和set的封装】

简介: 【map和set的封装】

前言

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

1 大致框架

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

网络异常,图片无法展示
|
4dac299aa1944b40a51aec0945d0b1f6.png



a26a0b26c62e4c45809385a476b14101.png

从源码中我们不难发现map和set底层是用了一颗红黑树来封装的,并且模板参数与我们自己想的不太一样。set中传入的是<K,K>,map中传入的是<K,Pair<K,V>> (其他参数可以暂时不用考虑)

大家想想,为什么要这么设计❓这样设计的好处是什么❓

我们传入两个参数的目的就是为了用一颗红黑树封装map和set,也就是第二个参数我们可以理解为给的是一个T,T可以接受上层的传入来的参数。

那可能大家又有了疑问?那为啥要传入第一个参数呀?直接用第二个参数不行吗?

大家别忘了,我们使用find接口和erase接口是用的参数是啥?是不是无论是map还是set都是用的是K,所以这个参数我们必须的传。

但是这样做问题又来了,上层是如何知道我们比较结点大小的时候比较的是K,还是Pair<K,V>?

所以我们还得再传入一个模板参数,不妨给一个仿函数,通过仿函数来取得数据。

2 迭代器

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

像* -> == !=这些运算符重载好说,实现起来不难,关键是如何实现++重载?–重载?

给了一颗红黑树,如下图,我们如何走到下个结点呢?


d042ba62013c44dda07b2faf4671437f.png


我们不妨采用这种思路:如果右子树存在,就找右子树的最左结点;右子树不存在,需要判断是否孩子是父亲的右节点,是的话还要往祖宗向上找,直到找到孩子是父亲的左节点为止。

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

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

这个我就不再分析了,大家可以自行分析。

为了方便,我们将用nullptr来构造找到了末尾,不用继续找了,但是STL中并不是这样设计的,是用了一个头结点来连接:



dc1beea829f049789222a9714bb998cb.png

走到了头结点就表示找到了末尾。

用这种方式会稍微麻烦些,不过总体也是不难的。

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

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)
  {}

这样就能够解决问题了。

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

【码云地址】

Fox!
+关注
目录
打赏
0
0
0
0
2
分享
相关文章
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
只会“有序无序”?面试官嫌弃的List、Set、Map回答!
小米,一位热衷于技术分享的程序员,通过与朋友小林的对话,详细解析了Java面试中常见的List、Set、Map三者之间的区别,不仅涵盖了它们的基本特性,还深入探讨了各自的实现原理及应用场景,帮助面试者更好地准备相关问题。
73 20
|
2月前
|
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
79 18
你对Collection中Set、List、Map理解?
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
37 5
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对,每个键唯一;而`set`存储唯一元素,不包含值。两者均基于红黑树实现,支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口,并简要对比了`map`与`set`的主要差异。此外,还介绍了允许重复元素的`multiset`和`multimap`。
62 3
【C++】map、set基本用法
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
4月前
|
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
57 1
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等