AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++】map和set的封装（上）

2023-05-25 80
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++】map和set的封装

1. 在STL中的map与set

在STL中，map和set都是使用的红黑树

48253e52bb1d4e87bd71ab1604ff472f.png

32c58d11b26145fe91a2b70e33ce1588.png

map与set在STL中实现是一样的

对于value_type，map的第二个模板参数是pair，而set的第二个模板参数是key

这样写是为了map和set使用同一颗红黑树去复用map和set


set < K > -> rb_tree<K,K>

map<K,V> - > rb_tree<K,pair<const K,V>>


第一个模板参数拿到单独K的类型，使用Find erase接口函数的参数是K

第二个模板参数决定了树的节点是 K 类型 or K V类型


2. 修改自己实现的红黑树

在上一篇文章中 ，实现了红黑树的插入等接口功能，

但是只能对于K V使用，修改模板参数使K或者 K V 都能调用

点击查看: 自己实现的红黑树

修改结构定义

90af8b7487e94109b2ed01b5e49052ac.png

原本自己实现的红黑树 模板为 template<class K,class V>

第一个参数代表 key ，第二个参数 代表 value


把第二个参数 改为 T 即 template<class K,class T>

按照STL的写法，使用第二个模板参数决定树的节点


原本的kv包含K V ，但是由于要调用map 和set，所以不知道到底传过来的是什么

所以使用 模板类型的 data 代替

13d0af8698b348248e72205dfbc6b562.png

在结构定义时，为了让map与set都能调用同一颗红黑树，所以把模板参数改为T

当set要调用时，T变为<K,K>

当map要调用时，T变为<K,pair<const K,V>>

红黑树的insert中如何取到key

34c50b5534544d3b8923bb7ae560f9f2.png

在insert中由于不知道data代表的是 pair还是K ，所以不能够取first

pair 虽然能够比较，但是不符合预期，所以要自己实现一个仿函数


我们要把key取出来，但是在红黑树中并不知道调用的是 set 还是map，无法知道T代表什么

但是在使用set或者map内部是知道的,所以 分别在map和set内部各自创建一个内部类，其中都写一个operator()


590f52d35eb34fb4a647aac989760288.png

在函数模板中添加一个参数，即可找到对应map/set的key值

8a3b7028ed5248acb58f684fbb446c70.png

在红黑树内部，使用类实例化一个对象kot，通过kot去调用map/set 中相同的operator() ，取出对应的key值

迭代器

set/map的迭代器是红黑树内部的迭代器


3b964d2f704748a3b5ab5b583a3a09f0.png

170269d921b543d29e380e152921cc3c.png

72f286f734414ef68c3b05224ac088a9.png

第二个模板参数Ref 第三个模板参数Ptr都是为了迭代器与const迭代器传参时有不同的参数存在，

从而区分普通迭代器与const迭代器


在list的模拟实现中有详细解释 关于 参数Ref 与Ptr 以及operator != -> * 的基本相似的使用


点击查看: 迭代器详细解释


operator++

9d9667652a364dcf89f1f1fe9ad59783.png

若当前右子树不为空，则下一个节点为右树的最左节点即蓝色节点


af85492ee2574b93ac7a49a08e60e1bd.png


b6908e5fd2ba4b47b2118fe89d6b28c2.png

6的右子树为空，并且6作为1的右子树，需要继续往上寻找

将parent作为新的cur节点，把爷爷节点作为parent节点

6作为1的右子树，说明1已经遍历完了，所以把1及1的左右子树看作一个整体，1整体是8的左子树，

所以下一个节点返回8


9fb16326a027418c8b12240d4da6658b.png

若右子树为空，并且孩子作为父节点的左子树，则直接把父节点返回即可

514bd1173b98407184a88816602e3a1c.png

operator - -

73ffae3eeeb94ef1a685f6c338cf41a1.png

左子树若不为空，则寻找左子树的最右节点

3bca0c84bf664381bb54570a3e512555.png

8bce004175c640ba8a6149bfc64a0c68.png

cur为当前节点，若cur的左子树为空，并且作为parent的右子树，则直接返回

parent节点

ae9506c9c8ad43089c961477b01ebe69.png

begin

d25cd899875f417bb4210f7050fe12e1.png

begin返回 的是开头的数据 即中序遍历的第一个 即最左节点

end

cbe6032db22a48caaa8f5c23cbc0fd7d.png

end返回最后一个数据的下一个 即nullptr

typename 问题

aac6d67b2d4c4451811a15c758f2430f.png

加入typename 是因为编译器无法识别RBTree<K, K,setkeyOfT>是静态变量还是类型

在set.h中，寻找到红黑树的迭代器，通过该迭代器调用对应的begin和end ，来实现set的begin和end

map 中 operator[]的实现

e0436d169ab74556ab3c22208591c9c0.png

将insert的返回值设置成迭代器加布尔值

若插入成功，返回新插入节点的迭代器

若插入失败，返回已经有的节点的迭代器

f762e32470574804bfbfc4ae2f5b5df1.png

在map中，通过设置好的insert返回值来达到[]的作用

operwator [] 详细的解析 ，点击查看迭代器部分 : map和set的使用

解决自己实现的迭代器的key值可以被修改问题


8c6af701141c40f29bdc79acf1398697.png

自己实现的迭代器的key值可以被修改，但是在STL实际上是不能被修改的

e1849f5f36c84000a51e0d550be2f2d0.png

在STL中，普通迭代器和const迭代器都是const迭代器


d9e2331c441b4da8b606b36c7642a835.png

在set中同样做出相同的修改，即可解决问题

d8e17d31072345609ff71cf5da53418b.png


begin调用的是红黑树的普通迭代器，但是return返回的const迭代器

，所以正常运行时会报错


d5547ba497324baaaf1692739a14ed7c.png


自己去实现一个普通迭代器类型，当类模板实例化为iterator时，则红框为拷贝构造

当类模板实例化为const_iterator时，通过发生隐式类型转换，使用普通迭代器构造const迭代器


3. 完整代码

RBTree.h

#pragma once
#include<iostream>
#include<cassert> 
using namespace std;
enum colour
{
  RED,//红色 默认为0
  BLACK,//黑色 默认为1
};
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)
  {
  }
};
//迭代器
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<T,T&,T*> 为普通迭代器
  //这样就可使普通迭代器构造const迭代器 完成隐式类型转换
  _RBTreeIterator(const _RBTreeIterator<T,T&,T*> &it)
    :_node(it._node)
  {
  }
  Ref operator*()
  {
    return _node->_data;
  }
  Ptr operator->()
  {
    return  &_node->_data;
  }
  bool operator!=(const self& s)
  {
    return _node != s._node;
  }
  self& operator++()
  {
    //右子树不为空，则寻找右子树的最左节点
    if (_node->_right)
    {
      Node* subleft = _node->_right;
      while (subleft->_left)
      {
        subleft = subleft->_left; 
      }
      _node = subleft;
    }
    else
    {
      //右子树为空,沿着根路径寻找，找到孩子是父亲的左的那个祖先节点
      Node* cur = _node;
      Node* parent = cur->_parent;
      //若右子树为空，且孩子作为父节点的右子树，就往上处理
      while (parent && cur==parent->_right)
      {
        cur = parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  self& operator--()
  {
    //左子树不为空，则寻找左子树的最右节点
    if (_node->_left) 
    {
      Node* subright = _node->_left;
      while (subright->_right)
      {
        subright = subright->_right;
      }
      _node = subright;
    }
    else
    {
      //左子树为空,沿着根路径寻找，找到孩子是父亲的右的那个祖先节点
      Node* cur = _node;
      Node* parent = cur->_parent;
      //若左子树为空，且孩子作为父节点的左子树，就往上处理
      while (parent && cur == parent->_left)
      {
        cur = parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
};
//仿函数
template<class K, class T, class keyOfT>
class RBTree
{
  typedef RBTreeNode<T>  Node;
public:
  ~RBTree()//析构
  {
    _Destroy(_root);
    _root = nullptr;
  }
public:
  typedef _RBTreeIterator<T, T&, T*> iterator;
  typedef _RBTreeIterator<T, const T&, const T*> const_iterator;
  iterator begin()//开头的数据
  {
    Node* cur = _root;
    //寻找最左节点
    while(cur&&cur->_left)
    {
      cur = cur->_left;
    }
    return iterator(cur);
  }
  iterator end()//最后一个数据的下一个
  {
    return iterator(nullptr);
  }
  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);
  }
  Node* Find(const K & key)//查找
  {
    Node* cur = _root;
    keyOfT kot;
    while (cur)
    {
      //kot(cur->_data) 取出当前的key值 
      //_data 有可能为 K 或者 pair类型
      if (kot(cur->_data) > key)
      {
        cur = cur->_left;
      }
      else if (kot(cur->_data) < key)
      {
        cur = cur->_right;
      }
      else
      {
        return cur;
      }
    }
    return nullptr;
  }
  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;//用于记录cur的前一个节点
    Node* cur = _root;
    while (cur)
    {
      //若插入的值比当前树的值小 插入左边
      //kot(cur->_data) 找到对应的key值
      if (kot(cur->_data) >kot(data))
      {
        parent = cur;
        cur = cur->_left;
      }
      //若插入的值比当前树的值大 插入右边
      else if (kot(cur->_data)< kot(data))
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        //若插入的值，在树中有相同的值 ，则插入失败
        return make_pair(iterator(cur), true);
      }
    }
    cur = new Node(data);
    Node* newnode = cur;
    //再次判断parent当前节点值与插入值大小
    if (kot(parent->_data) > kot(data))
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    //cur的上一个节点即为 刚才的记录cur前一个节点的parent
    cur->_parent = parent;
    //当父节点不为NULL并且父节点为红色
    while (parent != nullptr && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;//爷爷节点
      //若父节点为爷爷节点的左子树，则unlce为爷爷节点的右子树
      if (grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
        //       g
        //    p     u
        // c
        //情况1:u存在并且为红，直接变色即可，并继续往上处理
        if (uncle && uncle->_col == RED)
          //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上调整
          cur = grandfather;
          parent = cur->_parent;
        }
        //情况2+3:u不存在或者u存在且为黑，旋转+变色
        else
        {
          //情况2
          //g p c 作为一条直线 所以为单旋
          //    g
          //  p   u
          //c 
          if (cur == parent->_left)
          {
            //右旋转
            RotateR(grandfather);
            //最终p作为最终的根 为黑  g为红 
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          //情况3
          //g p c 作为一条折线 所以为双旋
          //    g
           //   p   u
           //     c 
          else
          {
            //左单旋
            RotateL(parent);
            //右单旋
            RotateR(grandfather);
            //最终cur作为最终的根 为黑  g为红 
            cur->_col = BLACK;
            grandfather->_col = RED;
            //父节点继续保持红色
            parent->_col = RED;
          }
          break;
        }
      }
      else//grandfather->_right == parent
        若父节点为爷爷节点的右子树，则unlce为爷爷节点的左子树
      {
        //   g
        // u   p
        //       c
        Node* uncle = grandfather->_left;
        //情况1:u存在并且为红，直接变色即可，并继续往上处理
        if (uncle && uncle->_col == RED)
          //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上调整
          cur = grandfather;
          parent = cur->_parent;
        }
        //情况2+3:u不存在或者u存在且为黑，旋转+变色
        else
        {
          //情况2
          //g p c 作为一条直线 所以为单旋
          //    g
          //  u   p
          //        c  
          if (cur == parent->_right)
          {
            //左旋转 
            RotateL(grandfather);
            //最终p作为最终的根 为黑  g为红 
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          //情况3
          //g p c 作为一条折线 所以为双旋
          //   g
           //  u   p
           //    c 
          else
          {
            //右单旋
            RotateR(parent);
            //左单旋
            RotateL(grandfather);
            //最终cur作为最终的根 为黑  g为红 
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    //为了避免grandfather节点正好为根时，会被更新成红色的情况
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);
  }
  void inorder()//中序遍历
  {
    _inorder(_root);
    cout << endl;
  }
  //判断一颗二叉树是否为红黑树
  bool isbalance()
  {
    //检查根是否为黑
    if (_root && _root->_col == RED)
    {
      cout << "根节点颜色是红色" << endl;
      return false;
    }
    //连续的红色节点
    return _check(_root, 0);
  }
private:
  void _Destroy(Node*root)//销毁
  {
    if (root == nullptr)
    {
      return;
    }
     //后序遍历
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
  }
  bool _check(Node* root, int blacknum)
  {
    if (root == nullptr)
    {
      //为空时，blacknum代表一条路径的黑色节点个数
      cout << blacknum << " ";
      return true;
    }
    //blacknum代表黑色节点的个数
    if (root->_col == BLACK)
    {
      blacknum++;
    }
    //若当前节点为红 父节点也为红
    if (root->_col == RED
      && root->_parent
      && root->_parent->_col == RED)
    {
      cout << "存在连续的红色节点" << endl;
      return false;
    }
    //遍历整棵树
    return  _check(root->_left, blacknum) && _check(root->_right, blacknum);
  }
  void _inorder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _inorder(root->_left);
    cout << root->_kv.first << " ";
    _inorder(root->_right);
  }
  void RotateL(Node* parent)//左单旋
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL != nullptr)
    {
      subRL->_parent = parent;
    }
    Node* ppnode = parent->_parent;//记录parent的前一个节点
    subR->_left = parent;
    parent->_parent = subR;
    if (ppnode == nullptr)//说明parent是根即代表整棵树
    {
      _root = subR;//subR作为新的根
      _root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
    }
    else//说明旋转的是一部分，所以要跟ppnode相连接
    {
      if (ppnode->_left == parent)//若连接在左子树上
      {
        ppnode->_left = subR;
      }
      else//若连接在右子树上
      {
        ppnode->_right = subR;
      }
      subR->_parent = ppnode;//将subR父节点置为ppnode
    }
  }
  void RotateR(Node* parent)//右单旋
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR != nullptr)
    {
      subLR->_parent = parent;
    }
    Node* ppnode = parent->_parent;//记录parent的父节点
    subL->_right = parent;
    parent->_parent = subL;
    if (ppnode == nullptr)//若旋转整棵树
    {
      _root = subL;
      _root->_parent = nullptr;
    }
    else//若旋转整棵树的部分子树
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subL;
      }
      else
      {
        ppnode->_right = subL;
      }
      subL->_parent = ppnode;//使subL的父节点为ppnode
    }
  }
private:
  Node* _root = nullptr;
};

map.h

#pragma once
#include"RBTree.h"
namespace yzq
{
  template<class K, class V>
  class map
  {
    struct mapkeyOfT
    {
      const K& operator()(const pair<const K,V> & kv)
      {
        return kv.first;
      }
    };
  public:
    //加入typename 是因为编译器无法识别RBTree<K, K,setkeyOfT>是静态变量还是类型
    typedef typename RBTree<K, pair<const K,V>, mapkeyOfT>::iterator  iterator;
    iterator begin()//复用红黑树的begin
    {
      return _t.begin();
    }
    iterator end()//复用红黑树的end
    {
      return _t.end();
    }
  public:
    pair<iterator,bool> insert(const pair<const K, V>& kv)
    {
      //调用红黑树中的insert
      return _t.insert(kv);
    }
    V& operator[](const K&key)
    {
      pair<iterator,bool>ret=_t.insert(make_pair(key, V()));
      return ret.first->second;
    }
  private:
    RBTree<K, pair<const K, V>,mapkeyOfT> _t;
  };
  void test_map()
  {
    map<int, int> v;
    v.insert(make_pair(1, 1));
    v.insert(make_pair(2, 2));
    v.insert(make_pair(3, 3));
    map<int, int>::iterator it = v.begin();
    while (it != v.end())
    {
       cout << it->first << ":"<<it->second<<endl;
        ++it;
    }
  }
}

set.h

#pragma once
#pragma once
#include"RBTree.h"
namespace yzq
{
  template<class K>
  class set
  {
    struct setkeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    //加入typename 是因为编译器无法识别RBTree<K, K,setkeyOfT>是静态变量还是类型
    typedef typename RBTree<K, K,setkeyOfT>::const_iterator  iterator;
    typedef typename RBTree<K, K, setkeyOfT>::const_iterator  const_iterator;
    iterator begin()//复用红黑树的begin
    {
      return _t.begin();
    }
    iterator end()//复用红黑树的end
    {
      return _t.end();
    }
  public:
    pair<iterator,bool> insert(const K& key)
    {
      return _t.insert(key);
    }
  private:
    RBTree<K, K, setkeyOfT> _t;
  };
  void test_set()
  {
    set<int> v;
    v.insert(1);
    v.insert(5);
    v.insert(2);
    v.insert(8);
    set<int>::iterator it = v.begin();
    while (it != v.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
  }
}
文章标签：
C++
编译器
关键词：
map Set
C++封装
C++ map
Set封装
map Set封装
6rjmqfdboo6zq
目录
相关文章
html的七十二变
|
1月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中，Set 和 Map 用于存储唯一值和键值对，支持多种操作方法，如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象，有助于防止内存泄漏，适合特定场景使用。
html的七十二变
34 2
2的n次方_
|
2月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet（哈希表实现，无序且元素唯一）、LinkedHashSet（保持插入顺序的HashSet）、TreeSet（红黑树实现，自动排序）。Map系列为双列集合，键值一一对应，键不可重复，值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景，并提供了面试题示例，如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
2的n次方_
37 6
【数据结构】map&set详解
GuGuStudy
|
1月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
GuGuStudy
35 1
刘大猫.
|
2月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
36 5
游客j4mujezz7vm7y
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
游客j4mujezz7vm7y
38 5
周一同学Zelina
|
2月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法，并探讨了它们在前端开发中的具体应用，包括如何利用这些数据结构来解决常见的编程问题。
周一同学Zelina
28 0
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
热爱技术的小郑
|
3月前
|
存储 安全 Java
java集合框架复习----（4）Map、List、set
这篇文章是Java集合框架的复习总结，重点介绍了Map集合的特点和HashMap的使用，以及Collections工具类的使用示例，同时回顾了List、Set和Map集合的概念和特点，以及Collection工具类的作用。
热爱技术的小郑
46 1
java集合框架复习----（4）Map、List、set
可能只会写BUG
|
2月前
|
数据安全/隐私保护 C语言 C++
C++(七)封装
本文档详细介绍了C++封装的概念及其应用。封装通过权限控制对外提供接口并隐藏内部数据，增强代码的安全性和可维护性。文档首先解释了`class`中的权限修饰符（`public`、`private`、`protected`）的作用，并通过示例展示了如何使用封装实现栈结构。接着介绍了构造器和析构器的使用方法，包括初始化列表的引入以及它们在内存管理和对象生命周期中的重要性。最后，通过分文件编程的方式展示了如何将类定义和实现分离，提高代码的模块化和复用性。
可能只会写BUG
51 1
热爱技术的小郑
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别？
该CSDN博客文章讨论了Map和Set的区别，但提供的内容摘要并未直接解释这两种集合类型的差异。通常，Map是一种键值对集合，提供通过键快速检索值的能力，而Set是一个不允许重复元素的集合。
热爱技术的小郑
47 3
wljslmz
|
3月前
|
存储 Java 索引
Java 中 List、Set、Map 和 Queue 之间的区别
【8月更文挑战第22天】
wljslmz
31 0