AI 助理
备案控制台
开发者社区 云原生 文章 正文

C++进阶--mep和set的模拟实现

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

红黑树链接入口

底层容器

模拟实现set和map时常用的底层容器是红黑树。

红黑树是一种自平衡的搜索二叉树，通过对节点进行颜色标记来保持平衡。

在模拟实现set和map时，可以使用红黑树来按照元素的大小自动排序，并且保持插入和删除操作的高效性。set的每个节点只存储一个键值，不需要额外的值；而map每个节点存储的是一个键值对，值与键保持关联。通过红黑树的特性，可以根据快速查找，插入和删除对应的节点元素；

红黑树的改造

#pragma once
#include<vector>
enum Colour
{
  RED,
  BLACK
};
template<class T>
struct RBTreeNode
{
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  Colour _col;
  T _data;
  RBTreeNode(const T& data)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
    , _col(RED)
  {
  }
};
//红黑树的迭代器
  template<class T,class Ptr,class Ref>
  struct RBTreeIterator
  {
    typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T,Ptr,Ref> Self;
    Node* _node;
    RBTreeIterator(Node* node)
      :_node(node)
    {}
    Ref operator*()
    {
      return _node->_data;
    }
    Ptr operator->()
    {
      return &_node->_data;
    }
    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;
    }
    bool operator!=(const Self& s)
    {
      return _node != s._node;
    }
    bool operator == (const Self & s)
    {
      return _node == s._node;
    }
  };
//set->RBTree<K,K,SetOfT>
//map->RBTree<K,pair<K,V>,MapKeyOfT>
template<class K,class T,class KeyOfT>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef RBTreeIterator<T,T*,T&> iterator;
  typedef RBTreeIterator<T, const T*, const T&> const_iterator;
  
  const_iterator begin() const
  {
    Node* subLeft = _root;
    while (subLeft && subLeft->_left)
    {
      subLeft = subLeft->_left;
    }
    return const_iterator(subLeft);
  }
  
  iterator begin()
  {
    Node* subLeft = _root;
    while (subLeft && subLeft->_left)
    {
      subLeft = subLeft->_left;
    }
    return iterator(subLeft);
  }
  const_iterator end() const
  {
    return const_iterator(nullptr);
  }
  iterator end()
  {
    return iterator(nullptr);
  }
  iterator Find(const K& key)
  {
    KeyOfT kot;
    Node* cur = _root;
    //通过比较确定key节点的位置
    while (cur)
    {
      if (kot(cur->_data) < key)
      {
        cur = cur->_right;
      }
      else if (kot(cur->_data) > key)
      {
        cur = cur->_left;
      }
      else
      {
        return iterator(cur);
      }
    }
    //找不到返回最后的end
    return end();
  }
  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;
    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节点和p节点的位置关系
    cur = new Node(data);
    //要记住当前节点的位置
    Node* newnode = cur;
    if (kot(parent->_data )< kot(data))
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;
      if (parent == grandfather->_left)
      {
        Node* uncle = grandfather->_right;
        //情况一
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          //向上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else//情况2
        {
          if (cur == parent->_left)
          {
            //      g
            //    p    u
            //  c
            RotateR(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            //      g
            //    p    u
            //      c
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;//旋转完的子树的根节点必为黑，这时就不用向上调整处理了
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
        // 情况一：叔叔存在且为红
        if (uncle && uncle->_col == RED)
        {
          // 变色
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          // 继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else//情况2
        {
          if (cur == parent->_right)
          {
            //      g
            //    u    p
            //           c
            RotateL(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            //      g
            //    u    p
            //        c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;//旋转完的子树的根节点必为黑，这时就不用向上调整处理了
        }
      }
    }
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);
  }
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    subR->_left = parent;
    Node* ppnode = parent->_parent;
    parent->_parent = subR;
    if (parent == _root)
    {
      _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;
    subL->_right = parent;
    Node* ppnode = parent->_parent;
    parent->_parent = subL;
    if (parent == _root)
    {
      _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的模拟实现

Mymap.h

namespace fnc
{
  template<class K,class V>
  class map
  {
    struct MapKeyOfT
    {
      const K& operator()(const pair<K, V>& kv)
      {
        return kv.first;
      }
    };
  public:
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
    iterator begin()
    {
      return _t.begin();
    }
    iterator end()
    {
      return _t.end();
    }
    const_iterator begin() const
    {
      return _t.begin();
    }
    const_iterator end() const 
    {
      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;
    }
    iterator find(const K& key)
    {
      return _t.Find(key);
    }
  private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  };
}

Myset.h

namespace fnc
{
  template<class K>
  class set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
    typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_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, const K, SetKeyOfT> _t;
  };
}

测试

void test_map1()
  {
    map<int, int> m;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a)
    {
      m.insert(make_pair(e,e));
    }
    map<int, int>::iterator it = m.begin();
    while (it != m.end())
    {
      it->second += 100;
      cout << it->first << "," << it->second << endl;
      ++it;
    }
    cout << endl;
  }

void test_set1()
  {
    set<int> s;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a)
    {
      s.insert(e);
    }
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
  }

operator[]

void test_map2()
  {
    string arr[] = { "西瓜","草莓","香蕉","苹果","西瓜","草莓","香蕉" ,"西瓜","草莓","西瓜" };
    map<string, int> countmap;
    for (auto& e : arr)
    {
      countmap[e]++;
    }
    for (auto& kv : countmap)
    {
      cout << kv.first << ":" << kv.second << " ";
    }
    cout << endl;
  }

完善

验证

void test_map3()
  {
     map<int, int> m;
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    for (auto e : a)
    {
      m.insert(make_pair(e, e));
    }
    const map<int, int> m1 = m;
    map<int, int>::const_iterator it = m1.begin();
    while (it != m1.end())
    {
      cout << it->first << "," << it->second << endl;
      ++it;
    }
    cout << endl;
    map<int, int>::iterator it2 = m.find(15);
    --it2;
    cout << it2->first << "," << it2->second << endl;
  }

文章标签：
C++
容器
存储
关键词：
C++ set
C++进阶
诡异森林。
目录
相关文章
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对，每个键唯一；而`set`存储唯一元素，不包含值。两者均基于红黑树实现，支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口，并简要对比了`map`与`set`的主要差异。此外，还介绍了允许重复元素的`multiset`和`multimap`。
chian-ocean
33 3
【C++】map、set基本用法
chian-ocean
|
1月前
|
存储 算法 C++
【C++】unordered_map（set）
C++中的`unordered`容器（如`std::unordered_set`、`std::unordered_map`）基于哈希表实现，提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中，每个桶可存储一个或多个元素，以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列，以及迭代器。哈希函数用于计算元素的哈希值，冲突通过开链法解决，负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1)，但在冲突较多时可能退化为O(n)。
chian-ocean
24 5
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】set模拟实现
C++中的`set`是STL提供的一种关联容器，用于存储唯一元素并自动按特定顺序（默认升序）排序。其内部通过红黑树实现，保证了高效的插入、删除和查找操作，时间复杂度均为O(log n)。`set`支持迭代器遍历，提供了良好的数据访问接口。
chian-ocean
38 3
დ旧言~
|
5月前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
დ旧言~
44 2
დ旧言~
|
5月前
|
存储 C++ 容器
【C++】map和set深度讲解（下）
【C++】map和set深度讲解（下）
დ旧言~
70 2
დ旧言~
|
5月前
|
存储 自然语言处理 Java
【C++】map和set深度讲解（上）
【C++】map和set深度讲解（上）
დ旧言~
54 2
百锦再@新空间代码工作室
|
5月前
|
存储 C++ 容器
C++ 学习之Set容器
C++ 学习之Set容器
百锦再@新空间代码工作室
86 1
好奇的菜鸟
|
6月前
|
C++ 容器
C++之set/multiset容器
C++之set/multiset容器
好奇的菜鸟
37 1
风掣长空
|
6月前
|
编译器 C++
C++模板进阶
C++模板进阶
风掣长空
28 1
枫叶丹4
|
6月前
|
存储 自然语言处理 C++
【C++航海王：追寻罗杰的编程之路】set|map|multiset|multimap简单介绍
【C++航海王：追寻罗杰的编程之路】set|map|multiset|multimap简单介绍
枫叶丹4
48 0
【C++航海王：追寻罗杰的编程之路】set|map|multiset|multimap简单介绍