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++进阶--mep和set的模拟实现

底层容器

红黑树的改造

红黑树的迭代器

map和set的模拟实现

测试

operator[]

完善

验证

热门文章

最新文章

相关课程

相关电子书