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

【C++】map和set的模拟实现

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

👉红黑树的改造👈


节点和模板参数的改造


我们知道，map 和 set 的底层数据结构都是红黑树，那库里是写了两份红黑树的代码来分别实例化出 map 和 set 吗？其实不是，而给一颗泛型结构的红黑树传不同的实例化参数，从而实现 map 和 set。

fafed1ea7db1428990756c8b42dae9ef.png

194b8e952afc4f40b01026d1b8255fe4.png

通过上图可以看到，map 传给红黑树的key_type是Key，value_type是pair<Key, T>；而 set 传给红黑树的key_type和value_type都是Key。红黑树的节点中存储数据就是value_type类型的数据，并不是像我们写的那样：直接存储键值对pair<K, V>。如果传给value_type的是pair<Key, T>，那么就会实例化出 map；而传给value_type的是Key，就会实例化出 set。那么现在我们也将自己实现的红黑树改造一下。


#pragma once
// 用枚举常量来代表颜色
enum Colour
{
  RED,
  BLACK
};
template<class T>
struct RBTreeNode
{
  RBTreeNode<T>* _parent;
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  T _data;
  Colour _col;
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
  {}
};
template<class K, class T>
struct RBTree
{
  typedef RBTreeNode<K, T> Node;
private:
  Node* _root = nullptr;
}

0fad1de89a4c48a88c3e63326124d1e3.png

改造红黑树的模板参数和节点后，就会带了一个问题：我们该如何比较_data的大小？因为 map 的数据类型是pair<K, T>，而 set 的数据类型是Key。那怎么才能用一份泛型代码同时实现键值对的比较和Key的比较呢？第一种方式就是重载键值对的比较。库里也实现了键值对的比较，但是并不是我们想要的。

e07cdb37d23c4d7cb610b95b3333839c.png

库里实现的键值对的大小比较是如果first没有比较出结果，还会比较second。这不是我们想要的，因为 map 键值对的比较只会比较first，并不会比较second。如果我们想要这样比较的话，那么就只能自己再实现一个pair了。这样会过于麻烦，那么我们可以采取第二种方式：通过一个仿函数来拿到节点数据的类型。

0108000d1c0849f5bbcfddbc0a2253a3.png

那么现在就能比较大小了，我们将 map 和 set 简单地封装一下，调试看看写得对不对。


调试样例4c46f48b03554d938a1c2341dcc79362.png

722f7b45a2d24df59d07cc641989b586.png792512a6bc674ad5a35e0c34c5361413.png

b337be1280d54602a010b43fdda71bb5.png

c798c99d1bad4839b0379730e89612cb.png


通过上面的调试可以看到，确实可以拿到Key去比较。那么，这样我们就通过红黑树实例化出 map 和 set。


红黑树的迭代器


STL 明确规定，begin() 与 end() 代表的是一段前闭后开的区间，而对红黑树进行中序遍历可以得到一个有序的序列。因此，begin() 可以放在红黑树中最小节点（即最左侧节点）的位置，end() 放在最大节点（最右侧节点）的下一个位置。注：最大节点的下一个位置可以认为是nullptr。 而库里的红黑多加了一个哨兵位的头节点header，header的左指针指向最小节点，右指针指向最大节点，父指针指向根节点，根节点的父指针指向header。如下图所示：

ae92e7c02d454e04879404183615e663.png

cdf015a16ade480080792f6942913ff0.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& it) const
  {
    return _node != it._node;
  }
  bool operator==(const Self& it) const
  {
    return _node == it._node;
  }
  Self& operator++()
  {
    if (_node->_right)
    {
      // 下一个就是右子树的最左节点
      Node* left = _node->_right;
      while (left->_left)
      {
        left = left->_left;
      }
      _node = left;
    }
    else
    {
      // 下一个是孩子不是在父亲的右边的第一个祖先
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = cur->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  Self& operator--()
  {
    if (_node->_left)
    {
      // 下一个就是左子树的最右节点
      Node* right = _node->_left;
      while (right->_right)
      {
        right = right->_right;
      }
      _node = right;
    }
    else
    {
      // 下一个是孩子不是父亲的左边的第一个祖先
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && cur == parent->_left)
      {
        cur = cur->_parent;
        parent = cur->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  Self operator++(int)
  {
    Self tmp(*this);
    ++(*this);
    return tmp;
  }
  Self operator--(int)
  {
    Self tmp(*this);
    --(*this);
    return tmp;
  }
};
template<class K, class T, class KeyOfT>
struct RBTree
{
  typedef RBTreeNode<T> Node;
  typedef __RBTreeIterator<T, T&, T*> iterator;
public:
  // begin()为树的最左节点
  iterator begin()
  {
    // 注：需要避免_root为nullptr
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
    return iterator(left);
  }
  // end()可以设置为nullptr
  iterator end()
  {
    return iterator(nullptr);
  }
private:
  Node* _root = nullptr;
}

33ff7359a8be4138ad96790cbf16eea7.png

ae3429d91b354aec9964859bc44c0cb6.png


注：map 和 set 的迭代器也是封装了红黑树的迭代器的。红黑树的反向迭代器可以自己尝试实现，reverse_begin()是最右节点，reverse_end()是 nullptr。因为我们没有添加哨兵位的头节点了，所以就可能比较难用封装正向迭代器的方式来实现方向迭代器。


测试迭代器


void MapTest1()
{
  map<int, int> m;
  m.insert(make_pair(1, 1));
  m.insert(make_pair(3, 3));
  m.insert(make_pair(5, 5));
  m.insert(make_pair(2, 2));
  map<int, int>::iterator it = m.begin();
  while (it != m.end())
  {
    cout << it->first << ":" << it->second << endl;
    ++it;
  }
}
void SetTest1()
{
  set<int> s;
  s.insert(1);
  s.insert(3);
  s.insert(5);
  s.insert(2);
  set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}


84be918acf534a418cb3dbe4f8d45e9a.png


红黑树的完整代码


现在红黑树的迭代器也实现完了，那么我们再来改造一下红黑树的 insert 函数，让它返回pair<iterator, bool>。insert 函数改造完成后，那么红黑树的代码就实现完了。（注：除了红黑树的删除节点没有实现，还有树的销毁和拷贝构造等内容可以参考二叉树搜索树的实现）


38b5480fd5ea4021935fdca8d83461e7.png

32b719ac89cc4779be4e107e4d19290c.png

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
// 用枚举常量来代表颜色
enum Colour
{
  RED,
  BLACK
};
template<class T>
struct RBTreeNode
{
  RBTreeNode<T>* _parent;
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  T _data;
  Colour _col;
  RBTreeNode(const T& data)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
  {}
};
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& it) const
  {
    return _node != it._node;
  }
  bool operator==(const Self& it) const
  {
    return _node == it._node;
  }
  Self& operator++()
  {
    if (_node->_right)
    {
      // 下一个就是右子树的最左节点
      Node* left = _node->_right;
      while (left->_left)
      {
        left = left->_left;
      }
      _node = left;
    }
    else
    {
      // 下一个是孩子不是在父亲的右边的第一个祖先
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = cur->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  Self& operator--()
  {
    if (_node->_left)
    {
      // 下一个就是左子树的最右节点
      Node* right = _node->_left;
      while (right->_right)
      {
        right = right->_right;
      }
      _node = right;
    }
    else
    {
      // 下一个是孩子不是父亲的左边的第一个祖先
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && cur == parent->_left)
      {
        cur = cur->_parent;
        parent = cur->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  Self operator++(int)
  {
    Self tmp(*this);
    ++(*this);
    return tmp;
  }
  Self operator--(int)
  {
    Self tmp(*this);
    --(*this);
    return tmp;
  }
};
template<class K, class T, class KeyOfT>
struct RBTree
{
  typedef RBTreeNode<T> Node;
  typedef __RBTreeIterator<T, T&, T*> iterator;
public:
  iterator begin()
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
    return iterator(left);
  }
  iterator end()
  {
    return iterator(nullptr);
  }
  pair<iterator, bool> Insert(const T& data)
  {
    KeyOfT kot; // 通过T来获取Key的一个仿函数类
    // 根节点的颜色为黑色
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_col = BLACK;
      return make_pair(iterator(_root), true);
    }
    Node* parent = nullptr;
    Node* cur = _root;
    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 make_pair(iterator(cur), false);
      }
    }
    // 插入节点
    cur = new Node(data);
    // 因为变色和旋转要修改cur,所以将新增节点的指针保存
    // 在newnode中方便后续构造迭代器
    Node* newnode = cur;  
    cur->_col = RED;  // 新插入节点默认为红色
    // 判断在哪一边插入
    if (kot(parent->_data) < kot(data))
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
    // 当parent存在且为红色,则需要继续往上处理
    // 当parent为空或为黑色时,则不需要往上处理
    while (parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;
      assert(grandfather);
      assert(grandfather->_col == BLACK);
      // 关键看叔叔
      if (parent == grandfather->_left)
      {
        Node* uncle = grandfather->_right;
        // 情况一：uncle存在且为红
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          // 继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else    //情况二和三：uncle不存在或uncle存在且为黑
        {
          // 情况二：右单旋+变色
          //     g              p
          //   p   u   ==>    c   g
          // c                      u
          if (cur == parent->_left)
          {
            RotateR(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            // 情况三：parent先做左单旋,grandfather再做右单旋,最后变色
            //     g          g            c
            //   p   u ==>  c   u  ==>   p   g
            //     c      p                    u
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
        // 情况一：uncle存在且为红
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          // 继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else    //情况二和三：uncle不存在或uncle存在且为黑
        {
          // 情况二：左单旋+变色
          //     g                  p
          //   u   p       ==>    g   c
          //         c          u 
          if (cur == parent->_right)
          {
            RotateL(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            // 情况三：parent先做右单旋,grandfather再做左单旋,最后变色
            //     g          g            c
            //   u   p ==>  u   c  ==>   g   p
            //     c             p     u
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    // 根节点永远是黑色
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);
  }
  void InOrder()
  {
    _InOrder(_root);
  }
  bool IsBalance()
  {
    if (_root == nullptr)
      return true;
    if (_root->_col != BLACK)
    {
      cout << "根节点不是黑色" << endl;
      return false;
    }
    // 黑色节点数量的基准值
    int mark = 0;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_col == BLACK)
        ++mark;
      cur = cur->_left;
    }
    return PrevCheck(_root, 0, mark);
  }
private:
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
  bool PrevCheck(Node* root, int blackNum, int mark)
  {
    if (root == nullptr)
    {
      if (blackNum != mark)
      {
        cout << "某条路径上的黑色节点的数量不相等" << endl;
        return false;
      }
      else
        return true;
    }
    if (root->_col == BLACK)
      ++blackNum;
    // 检查父亲
    if (root->_col == RED && root->_parent->_col == RED)
    {
      cout << "存在连续的红色节点" << endl;
    }
    return PrevCheck(root->_left, blackNum, mark)
      && PrevCheck(root->_right, blackNum, mark);
  }
  // 左单旋
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    Node* ppNode = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (_root == parent)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subR;
      }
      else
      {
        ppNode->_right = subR;
      }
      subR->_parent = ppNode;
    }
  }
  // 右单旋
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
    {
      subLR->_parent = parent;
    }
    Node* ppNode = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (_root == parent)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
      subL->_parent = ppNode;
    }
  }
private:
  Node* _root = nullptr;
};


map 和 set 的完整代码


红黑树的代码已经实现完了，那么现在就用红黑树实现出 map 和 set。


map 的完整代码


#pragma once 
#include "RBTree.h"
namespace Joy
{
  template <class K, class V>
  class map
  {
    struct MapKeyOfT
    {
      const K& operator()(const pair<K, V>&kv)
      {
        return kv.first;
      }
    };
  public:
    // typename的作用是告诉编译器这是类型的重命名,并不是静态变量
    typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
      return _t.Insert(kv);
    }
    V& operator[](const K& key)
    {
      // 有就插入失败,没有就插入成功,但是都能够得到该节点的迭代器
      pair<iterator, bool> ret = insert(make_pair(key, V()));
      return ret.first->second;
    }
  private:
    RBTree<K, pair<K, V>, MapKeyOfT> _t;
  };
}


统计出现次数


  void MapTest2()
  {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    map<string, int> countMap;
    for (auto& str : arr)
    {
      // 1、str不在countMap中，插入pair(str, int()),然后在对返回次数++
      // 2、str在countMap中，返回value(次数)的引用，次数++;
      countMap[str]++;
    }
    map<string, int>::iterator it = countMap.begin();
    while (it != countMap.end())
    {
      cout << it->first << ":" << it->second << endl;
      ++it;
    }
    cout << "-------" << endl;
    for (auto& kv : countMap)
    {
      cout << kv.first << ":" << kv.second << endl;
    }
  }

c162d139387c4c8bbf3e1f804e6d88b2.png


set 的完整代码


#pragma once 
#include "RBTree.h"
namespace Joy
{
  template <class K>
  class set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K & key)
      {
        return key;
      }
    };
  public:
    // typename的作用是告诉编译器这是类型的重命名,并不是静态变量
    typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    pair<iterator, bool> insert(const K& key)
    {
      return _t.Insert(key);
    }
  private:
    RBTree<K, K, SetKeyOfT> _t;
  };
}


👉总结👈


本篇博客主要改造了之前模拟实现的红黑树以及将改造后的红黑树模拟实现出 map 和 set等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️

文章标签：
C++
存储
关键词：
map Set
C++ map set
C++ set
C++ map
游客mpbbpgnnu5sxe
目录
相关文章
龙大吉
|
6天前
|
存储 JavaScript 索引
js开发：请解释什么是ES6的Map和Set，以及它们与普通对象和数组的区别。
ES6引入了Map和Set数据结构。Map的键可以是任意类型且有序，与对象的字符串或符号键不同；Set存储唯一值，无重复。两者皆可迭代，支持for...of循环。Map有get、set、has、delete等方法，Set有add、delete、has方法。示例展示了Map和Set的基本操作。
龙大吉
25 3
老板这功能得加钱
|
5天前
|
JavaScript 前端开发 Java
ES6 逐点突破系列 -- Set Map，工作感悟，完美收官
ES6 逐点突破系列 -- Set Map，工作感悟，完美收官
老板这功能得加钱
6 0
阿珊和她的猫
|
5天前
|
存储 缓存 JavaScript
JavaScript中的Set和Map：理解与使用
JavaScript中的Set和Map：理解与使用
阿珊和她的猫
8 0
游客g7kiuqrvkhn3g
|
6天前
|
存储 JavaScript
ES6+新特性-Symbol与Set/Map数据结构
ES6 引入了三种新的数据结构：Symbol、Set和Map。Symbol是唯一且不可变的值，常用于定义对象的独特属性；Set存储不重复值，适合数组去重；Map则是键值对集合，键可为任意类型，提供了更灵活的存储方式。这些新数据结构提供了更高效的操作手段，分别解决了属性命名冲突、数据去重和复杂键值对存储的问题。示例展示了如何使用Symbol、Set和Map进行基本操作。
游客g7kiuqrvkhn3g
16 6
盒马盒马
|
6天前
|
存储 编译器 C++
C++：map&set 对红黑树的封装
C++：map&set 对红黑树的封装
盒马盒马
11 1
toKeep
|
6天前
|
存储
Map与Set的经典OJ题
Map与Set的经典OJ题
toKeep
13 3
toKeep
|
6天前
|
存储 自然语言处理 容器
Map与Set
Map与Set
toKeep
13 3
盒马盒马
|
6天前
|
存储 C++ 容器
C++：STL - set & map
C++：STL - set & map
盒马盒马
16 4
Yawesh
|
6天前
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
Yawesh
11 1
小蜗牛~向前冲
|
6天前
|
存储 C++ 容器
[数据结构]-map和set
[数据结构]-map和set
小蜗牛~向前冲
21 2