用红黑树封装实现map和set

简介: 用红黑树封装实现map和set

map和set的实现原理

为了方便实现我们的map和set,我们肯定是要养成看源码的习惯的,看了源码之后你才会感受到大佬的强大!

在源码里面,对于map和set的实现,底层是用同一棵红黑树封装出来的,并不是用了两棵红黑树

那么大家肯定会有疑问了,一棵红黑树这么能两用呢,况且map和set的底层存储的节点类型不一样啊,map是存储的键值对,set只是存储key

这时设计map和set的大佬就想到了一个极佳的办法,在红黑树底层中用了一个模板参数Value来代表红黑树结点存储对象的类型,这个类型可能是pair键值对,也有可能是key类型。

红黑树其实并不知道自己的节点是什么类型,只能用模板来接受存储对象的类型

enum Color {RED,BLACK};
template<class T>//节点存储对象类型,可能是键值对也有可能是key
class RBTreeNode
{
  T _data;
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  Color _col;
  RBTreeNode(const T& data)
    :_data(data)
    , _left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _col(RED)
  {}
};

这样,我们就可以实现一树多用了!

我们就可以根据value的类型来去确定是map还是set了,但是大家可能会有一点小疑问,既然有了value就可以实现红黑树了,那我们还要关键码key有什么用呢?

这里的关键码key是必不可少的!

因为在红黑树搜索的时候,依靠的还是关键码进行搜索,通过所传关键码和红黑树结点中的关键码的大小关系,确定到红黑树中要搜索的某个结点。

红黑树的find函数的参数类型必须是key!

在实现map和set之前,我们先想一想,上一篇博文的红黑树有哪些地方需要进行改进的?

细心的朋友就会发现,上篇博文的代码,插入时比较的就只是在整形情况下的key的比较,但是map和set就只是存储整形吗?显然不是,所以我们就要想办法提取其他类型下的key关键码来进行比较,并且map的节点的value类型是键值对的话,要提取的first,set只需要直接比较key,该如何结局这个问题呢?

我们这个时候就可以使用仿函数了!

我们可以在map和set中各自增加一个仿函数类,在模板传参时,再增加一个仿函数类来提取节点的关键码的参数,我们将他命名为KeyOfT

set

template<class K>
class set
{
  struct SetKeyOfT
  {
    const K& operator()(const K& key)
    {
      return key;
    }
  };
public:
private:
  RBTree<K, K, SetKeyOfT> _t;
};

map

template<class K, class V>
class map
{
  struct MapKeyOfT
  {
    const K& operator()(const pair<const K, V>& kv)
    {
      return kv.first;
    }
  };
public:
private:
  RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

rbtree

template<class K,class T,class KeyOfT>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
private:
  Node* _root = nullptr;
};

这样我们再插入的时候就可以直接提取关键码进行插入了

map和set的迭代器

关于map和set的迭代器的实现,设计库里面的源码的大佬很巧妙地运用了const

大家都知道,set是不可以修改的,map可以修改,但是修改的也只是pair键值对的value,pair里面的key可是不能修改的

对红黑树类型中的迭代器类型进行typedef时,可以看到我们在typedef后面加了typename,typename的作用就是告诉编译器后面的东西是一个类型,你先不要编译他,等到模板实例化为真正类型后,你再去取他里面的内嵌类型iterator。因为我们知道编译器是不编译模板的,编译的是模板实例化之后的代码,只有模板实例化之后,它里面的内嵌类型我们才可以取到,所以如果你不加typename,有可能取的不是类型,因为静态变量或函数都是可以通过类+域访问符进行访问的,所以如果你要取模板里面的类型,那就必须在模板前面加typename,告诉编译器你取的是类型。

rbtree迭代器实现

struct __RBTreeIterator
{
  typedef RBTreeNode<T> Node;
  typedef __RBTreeIterator<T> Self;
  Node* _node;
  __RBTreeIterator(Node* node)
    :_node(node)
  {}
  T& operator*()
  {
    return _node->_data;
  }
  T* operator->()
  {
    return &_node->_data;
  }
  Self& operator++()
  {
    if (_node->_right)
    {
      Node* min = _node->_right;
      while (min->_left)
      {
        min = min->_left;
      }
      _node = min;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }
  Self& operator--()
  {
    //右子树 根 左子树
    if (_node->_left)
    {
      //找左子树的最右结点,其实就是次大的结点
      _node = _node->_left;
      while (_node->_right)
      {
        _node = _node->_right;
      }
    }
    else
    {
      Node* cur = _node;
      Node* parent = _node->_parent;
      while (parent && cur == parent->_left)
      {
        cur = parent;
        parent = parent->_parent;
      }
      //如果cur是parent的右,则直接让_node指向到parent即可
      _node = parent;
    }
    return *this;//返回迭代器对象
  }
  bool operator!=(const Self& it)const//const修饰表示在该成员函数内部,不能修改对象的任何成员变量
  {
    return this->_node != it._node;
  }
  bool operator==(const Self& it)const//const对象和非const对象都可以调用
  {
    return this->_node == it._node;
  }
};

那么map和set的实现就很简单了:

template <class K>  
  class set
  {
  public:
    //set表层的普通迭代器底层用的依旧是const_iterator,就是不允许对set的迭代器指向内容进行修改
    typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator iterator;
    typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator const_iterator;
    iterator begin()  const   //为了防止权限的放大,我们直接使用const,如果对象是const,调用const的begin,不是const也调用const的begin和end
    {
      return _t.begin();
    }
    iterator end()  const
    {
      return _t.end();
    }

map的迭代器是需要实现两个版本的,因为map容器中的数据是可以被修改的,如果你想修改map中的数据那就用iterator,如果你想修改map中的数据那就用const_iterator。
如果是const_iterator,那解引用或者→返回的就是键值对的常引用或const修饰的指向键值对的结构体指针,那么此时键值对的key和value都是不可以修改的。
如果是iterator,解引用或者→返回的就是键值对的普通引用或无const修饰的指向键值对的结构体指针,但此时键值对的key依旧不可以被修改,只能对键值对中的value进行修改所以即使你用的是iterator,他所指向的键值对的key依旧是不能修改的,我们只能修改他的value。

template <class K, class V>
class map
{
public:
  typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;
  //map的迭代器需要提供两个版本
  iterator begin()
  {
    return _t.begin();
  }
  iterator end()
  {
    return _t.end();
  }
  const_iterator begin()const
  {
    return _t.begin();
  }
  const_iterator end()const
  {
    return _t.end();
  }
private:
  RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t;
};

红黑树插入的改造

我们使得插入后其返回值为键值对,如果出现插入key值相等的情况,则将bool改为false即可。最后调色后返回键值对时,我们不能直接返回cur构造的迭代器,因为如果发生调色,则cur位置会更改,所以在插入结点后,用一个curit的结点指针记录一下插入结点的位置,最后返回由curit结点指针构造出来的迭代器

pair<iterator, bool> Insert(const T& data)
//红黑树必须通过结点里面存储的key来进行比较才可以插入结点,所以出现了kot仿函数对象
{
  KeyOfT kot;
  Node* parent = nullptr;
  Node* cur = _root;
  if (_root == nullptr)
  {
    _root = new Node(data);
    _root->_col = BLACK;
    return make_pair(iterator(_root), true);
  }
  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);
  Node* curit = cur;//保存一下cur的位置否则下面旋转调色过程中,cur有可能被改了
  if (kot(parent->_data) > kot(data))
  {
    parent->_left = cur;
    cur->_parent = parent;
  }
  else
  {
    parent->_right = cur;
    cur->_parent = parent;
  }
  while (parent && parent->_col == RED)
  {
    Node* grandparent = parent->_parent;
    if (parent == grandparent->_left)
    {
      Node* uncle = grandparent->_right;
      if (uncle && uncle->_col == RED)
      {
        parent->_col = uncle->_col = BLACK;
        grandparent->_col = RED;
        cur = grandparent;
        parent = cur->_parent;
      }
      else if (cur == parent->_left)
      {
        RotateR(grandparent);
        grandparent->_col = RED;
        parent->_col = BLACK;
        break;
      }
      else if (cur == parent->_right)
      {
        RotateL(parent);
        RotateR(grandparent);
        cur->_col = BLACK;
        grandparent->_col = RED;
        break;
      }
      else
      {
        assert(false);
      }
    }
    else
    {
      Node* uncle = grandparent->_left;
      if (uncle && uncle->_col == RED)
      {
        grandparent->_col = RED;
        uncle->_col = parent->_col = BLACK;
        cur = grandparent;
        parent = cur->_parent;
      }
      else if (cur == parent->_right)
      {
        RotateL(grandparent);
        parent->_col = BLACK;
        grandparent->_col = RED;
        break;
      }
      else if (cur == parent->_left)
      {
        RotateR(parent);
        RotateL(grandparent);
        cur->_col = BLACK;
        grandparent->_col = RED;
        break;
      }
      else
      {
        assert(false);
      }
    }
  }
  _root->_col = BLACK;
  
  return make_pair(iterator(curit), true);
}

map的[]重载

[]直接返回插入节点的值,如果[]内的key值不在红黑树中,就直接插入,若在其中也有进行修改,最后返回iterator的first的second

template <class K, class V>
class map
{
public:
  pair<iterator, bool> insert(const pair<const 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<const K, V>, MapKeyOfT<K,V>> _t;
};

由于博主的能力有限,部分讲解不到位,等我巩固知识后再做修正!希望大家指正!本篇博文的分享到这里就结束了,感谢大家的支持!

相关文章
|
5天前
|
JavaScript 前端开发 Java
ES6 逐点突破系列 -- Set Map,工作感悟,完美收官
ES6 逐点突破系列 -- Set Map,工作感悟,完美收官
|
5天前
|
存储 缓存 JavaScript
JavaScript中的Set和Map:理解与使用
JavaScript中的Set和Map:理解与使用
|
6天前
|
存储 JavaScript
ES6+新特性-Symbol与Set/Map数据结构
ES6 引入了三种新的数据结构:Symbol、Set和Map。Symbol是唯一且不可变的值,常用于定义对象的独特属性;Set存储不重复值,适合数组去重;Map则是键值对集合,键可为任意类型,提供了更灵活的存储方式。这些新数据结构提供了更高效的操作手段,分别解决了属性命名冲突、数据去重和复杂键值对存储的问题。示例展示了如何使用Symbol、Set和Map进行基本操作。
|
6天前
|
存储 编译器 C++
C++:map&set 对红黑树的封装
C++:map&set 对红黑树的封装
11 1
|
6天前
|
存储
Map与Set的经典OJ题
Map与Set的经典OJ题
13 3
|
6天前
|
存储 JavaScript 索引
js开发:请解释什么是ES6的Map和Set,以及它们与普通对象和数组的区别。
ES6引入了Map和Set数据结构。Map的键可以是任意类型且有序,与对象的字符串或符号键不同;Set存储唯一值,无重复。两者皆可迭代,支持for...of循环。Map有get、set、has、delete等方法,Set有add、delete、has方法。示例展示了Map和Set的基本操作。
27 3
|
6天前
|
存储 数据格式
Set和Map的应用场景
Set和Map的应用场景
|
6天前
|
存储 自然语言处理 C++
map和set的简单介绍
map和set的简单介绍
27 1
|
6天前
|
存储 自然语言处理 容器
Map与Set
Map与Set
13 3
|
6天前
|
存储 C++ 容器
C++:STL - set & map
C++:STL - set & map
16 4