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

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

2023-02-08 132
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【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++
存储
关键词：
C++ map
map Set
C++ set
C++ map set
游客mpbbpgnnu5sxe
目录
相关文章
刘大猫.
|
17天前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
52 18
你对Collection中Set、List、Map理解？
软件求生
|
11天前
|
存储 缓存 安全
只会“有序无序”？面试官嫌弃的List、Set、Map回答！
小米，一位热衷于技术分享的程序员，通过与朋友小林的对话，详细解析了Java面试中常见的List、Set、Map三者之间的区别，不仅涵盖了它们的基本特性，还深入探讨了各自的实现原理及应用场景，帮助面试者更好地准备相关问题。
软件求生
49 20
chian-ocean
|
28天前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对，每个键唯一；而`set`存储唯一元素，不包含值。两者均基于红黑树实现，支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口，并简要对比了`map`与`set`的主要差异。此外，还介绍了允许重复元素的`multiset`和`multimap`。
chian-ocean
30 3
【C++】map、set基本用法
chian-ocean
|
28天前
|
存储 算法 C++
【C++】unordered_map（set）
C++中的`unordered`容器（如`std::unordered_set`、`std::unordered_map`）基于哈希表实现，提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中，每个桶可存储一个或多个元素，以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列，以及迭代器。哈希函数用于计算元素的哈希值，冲突通过开链法解决，负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1)，但在冲突较多时可能退化为O(n)。
chian-ocean
22 5
chian-ocean
|
28天前
|
存储 C++ 容器
【C++】map的模拟实现
C++中的`map`是STL中的一种关联容器，存储键值对且键唯一。`map`基于红黑树实现，自动按键排序，支持动态调整、复杂数据类型、丰富的成员函数及双向迭代器。插入、查找等操作保证了对数时间复杂度，适用于需要快速查找和有序存储的场景。
chian-ocean
22 3
chian-ocean
|
28天前
|
存储 C++ 容器
【C++】set模拟实现
C++中的`set`是STL提供的一种关联容器，用于存储唯一元素并自动按特定顺序（默认升序）排序。其内部通过红黑树实现，保证了高效的插入、删除和查找操作，时间复杂度均为O(log n)。`set`支持迭代器遍历，提供了良好的数据访问接口。
chian-ocean
31 3
html的七十二变
|
2月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中，Set 和 Map 用于存储唯一值和键值对，支持多种操作方法，如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象，有助于防止内存泄漏，适合特定场景使用。
html的七十二变
40 2
2的n次方_
|
3月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet（哈希表实现，无序且元素唯一）、LinkedHashSet（保持插入顺序的HashSet）、TreeSet（红黑树实现，自动排序）。Map系列为双列集合，键值一一对应，键不可重复，值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景，并提供了面试题示例，如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
2的n次方_
47 6
【数据结构】map&set详解
GuGuStudy
|
2月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
GuGuStudy
43 1
刘大猫.
|
3月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
42 5