通过源码分析STL中set和map对底层红黑树的使用


STL中,set、map、multiset、multimap的底层数据结构,都是红黑树。所以,在查看源码的时候,会发现,对set或者map的插入、删除等操作,其实底层都是对红黑树的插入和删除。所以,我们先来看下STL中的红黑树类的定义。

stl_tree.h    

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;

struct _Rb_tree_node_base
{
  typedef _Rb_tree_Color_type _Color_type;
  typedef _Rb_tree_node_base* _Base_ptr;

  _Color_type _M_color; 
  _Base_ptr _M_parent;
  _Base_ptr _M_left;
  _Base_ptr _M_right;
};

template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
  typedef _Rb_tree_node<_Value>* _Link_type;
  _Value _M_value_field;
};

template <class _Tp, class _Alloc>
struct _Rb_tree_base
{
  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

  _Rb_tree_base(const allocator_type&) 
    : _M_header(0) { _M_header = _M_get_node(); }
  ~_Rb_tree_base() { _M_put_node(_M_header); }

protected:
  _Rb_tree_node<_Tp>* _M_header;

  typedef simple_alloc<_Rb_tree_node<_Tp>, _Alloc> _Alloc_type;

  _Rb_tree_node<_Tp>* _M_get_node()
    { return _Alloc_type::allocate(1); }
  void _M_put_node(_Rb_tree_node<_Tp>* __p)
    { _Alloc_type::deallocate(__p, 1); }
};

template <class _Key, class _Value, class _KeyOfValue, class _Compare,
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> {
public:
  typedef _Key key_type;
  typedef _Value value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef _Rb_tree_node* _Link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
protected:
   _Compare _M_key_compare;
     _Link_type& _M_root() const 
    { return (_Link_type&) _M_header->_M_parent; }
     static _Link_type& _S_left(_Link_type __x)
    { return (_Link_type&)(__x->_M_left); }
  static _Link_type& _S_right(_Link_type __x)
    { return (_Link_type&)(__x->_M_right); }
  static _Link_type& _S_parent(_Link_type __x)
    { return (_Link_type&)(__x->_M_parent); }
  static reference _S_value(_Link_type __x)
    { return __x->_M_value_field; }
  static const _Key& _S_key(_Link_type __x)
    { return _KeyOfValue()(_S_value(__x)); }
};
     可以看到,红黑树的模板类,包含模板类型有,_Key,_Value,_KeyOfValue,_Compare,_Alloc 这五类。_Key是指key类型;_Value指值类型;_KeyOfValue是仿函数对象,用于从传来的Value中得到key;_Compare用于比较;_Alloc用于分配对象。

    现在,我们可以看下set和map分别对红黑树的定义做了什么样的自定义。

使用到的仿函数

stl_function.h

template <class _Tp>
struct less : public binary_function<_Tp,_Tp,bool> 
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }
};

// identity is an extensions: it is not part of the standard.
template <class _Tp>
struct _Identity : public unary_function<_Tp,_Tp> {
  const _Tp& operator()(const _Tp& __x) const { return __x; }
};

template <class _Tp> struct identity : public _Identity<_Tp> {};

// select1st and select2nd are extensions: they are not part of the standard.
template <class _Pair>
struct _Select1st : public unary_function<_Pair, typename _Pair::first_type> {
  const typename _Pair::first_type& operator()(const _Pair& __x) const {
    return __x.first;
  }
};

template <class _Pair>
struct _Select2nd : public unary_function<_Pair, typename _Pair::second_type>
{
  const typename _Pair::second_type& operator()(const _Pair& __x) const {
    return __x.second;
  }
};

set类的定义

stl_set.h

template <class _Key, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) >
class set;   //set的前置声明,包含了_Compare 和_Alloc的默认类型。

template <class _Key, class _Compare, class _Alloc>
class set {
   public:
  // typedefs:

  typedef _Key     key_type;
  typedef _Key     value_type;
  typedef _Compare key_compare;
  typedef _Compare value_compare;

private:
  typedef _Rb_tree<key_type, value_type, 
                  _Identity<value_type>, key_compare, _Alloc> _Rep_type;
   //set对于_Rb_tree的自定义部分。指定了_KeyOfValue的具体类型
   _Rep_type _M_t;  // red-black tree representing set
};  

map类的定义

stl_map.h

// Forward declarations of operators == and <, needed for friend declarations.
template <class _Key, class _Tp, 
          class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class map;  //map模板类的前置声明。指定了默认的_Compare和_Alloc类型

template <class _Key, class _Tp, class _Compare, class _Alloc>
class map {
public:
     typedef _Key                  key_type;   
  typedef _Tp                   data_type;
  typedef _Tp                   mapped_type;
  typedef pair<const _Key, _Tp> value_type;
  typedef _Compare              key_compare;

    class value_compare
    : public binary_function<value_type, value_type, bool> {
         friend class map<_Key,_Tp,_Compare,_Alloc>;
     protected :
          _Compare comp;
         value_compare(_Compare __c) : comp(__c) {}
     public:
         bool operator()(const value_type& __x, const value_type& __y) const {
               return comp(__x.first, __y.first);
         }
    };
   
private:
  typedef _Rb_tree<key_type, value_type, 
                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;   
   //map对于_Rb_tree的自定义部分。指定了_KeyOfValue的类型 
   _Rep_type _M_t // red-black tree representing map
};

对比分析set和map的源码.

项目 set map 分析
模板类的类型形参

template <class _Key, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(

less<_Key>),

          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) >
class set; 

template <class _Key, class _Tp,    

          class _Compare _STL_DEPENDENT_DEFAULT_TMPL(

less<_Key>),  class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >

class map; 

不同点:

1.map有_Tp类型

相同点:

1.默认的_Compare类型都是less<_Key>

2.默认的_Alloc类型都是alloc

公有成员   typedef _Key     key_type;
  typedef _Key     value_type;
  typedef _Compare key_compare;
  typedef _Compare value_compare;
  typedef _Key   key_type;
  typedef _Tp    data_type;
  typedef _Tp    mapped_type;
  typedef pair<const _Key, _Tp> value_type;
  typedef _Compare              key_compare;
    class value_compare {};

不同点:

1.map根据__TP类形参,定义了data_type和mmaped_type类型。

2.set的value_type类型就是_Key形参类型,而map的value_type类型是pair

3.set的value_compare类型是形参_Compare ,

而map的value_compare是map的内部类,也是仿函数,看代码实现,

实质上是对value_type即pair的first间的比较

类中红黑树成员的类型   typedef _Rb_tree<key_type, value_type, 
  _Identity<value_type>, key_compare, _Alloc> _Rep_type;

  _Rep_type _M_t;  

// red-black tree representing set


  typedef _Rb_tree<key_type, value_type, 
                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;

  _Rep_type _M_t;  

// red-black tree representing map


不同点:

1.set中,_KeyOfValue的类型是

对比分析set与multiset、map与multimap的源码

项目 不同点
set/multiset

1.set底层对红黑树的插入,调用insert_unique方法;multiset调用底层红黑树的insert_equal方法

2.类中的count方法实现不同。set调用红黑树的find方法判断是否有键值的节点;multiset则调用底层红黑树的count方法


map/multimap

1.map底层对红黑树的插入,调用insert_unique方法;multimap调用底层红黑树的insert_equal方法


2.类中的count方法实现不同。map调用红黑树的find方法判断是否有键值的节点;multimap则调用底层红黑树的count方法


2.map类支持[]运算符;multimap不支持,没有重载该运算符。


_KeyOfValue和_Compare在红黑树中的应用

我们以红黑树的插入为例。先看下插入的代码

stl_tree.h

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc>
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator, 
     bool>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::insert_unique(const _Value& __v)
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();
  bool __comp = true;
  while (__x != 0) {
    __y = __x;
    __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
    __x = __comp ? _S_left(__x) : _S_right(__x);
  }
  iterator __j = iterator(__y);   
  if (__comp)
    if (__j == begin())     
      return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
    else
      --__j;
  if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
    return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
  return pair<iterator,bool>(__j, false);
}

在insert_unique方法中,我们通过_KeyOfValue()获得仿函数实例, _KeyOfValue()(__v),获得__v的key值。_S_key(__x)获得__x的key值,然后通过仿函数对象_M_key_compare进行键值比较。默认的set或者map,调用的是less<_Key>,当小于时,返回true,大于或等于时,返回false.

        iterator __j = iterator(__y);  

        if (__comp)  

Q:为何要分析comp的真假??

A

  • 当__comp为真时,__v的键值肯定小于__j的键值,所以要判断插入的节点是否已存在,我们必须判断__j 的前一个值,即--__j,得到比__j键值小的下一个节点,然后用修改后的__j对应的节点与__v进行键值比较,此时得到的存在三种情况:小于,等于,大于。然而从代码上,我们看出,不存在大于的可能。为何??为何当__comp为真的时候,__j 会是大于__v的节点中最小的一个?? 证明:反证法:因为,当comp为真时,表示__j > __v.当__j 大于__v时,会将__j 的左节点赋值给__x,此时,如果__x存在,循环不会停。而这里的条件是循环停了。所以,__j 的左节点不存在,所以,__j 是大于__v的节点中最小的一个,当comp为true时。
  • 当comp为false时,此时,有 __v >= __j ,所以要判断插入的节点是否已存在,我们只需要判断__j 与__v的键值是否相等就可以了,而不需要对__j 再进行减1运算。

    我们现在对比查看insert_equal方法,就会看出,insert_equal没有检查是否已经存在同插入的节点相同键值的节点。

 stl_tree.h

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::insert_equal(const _Value& __v)
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();
  while (__x != 0) {
    __y = __x;
    __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? 
            _S_left(__x) : _S_right(__x);
  }
  return _M_insert(__x, __y, __v);
}

set、map、multiset、multimap的插入操作

    既然知道,set和map的底层是rb_tree,那么,当遇到需要插入时,是如何调用rb_tree的呢??我们来各自看下代码。

 stl_set.h

  pair<iterator,bool> insert(const value_type& __x) { 
    pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x); 
    return pair<iterator, bool>(__p.first, __p.second);
  }

    因为set是不允许存在重复的键的,所以调用的是红黑树的insert_unique。现在,我们来看看map的插入方法。

stl_map.h

  pair<iterator,bool> insert(const value_type& __x) 
    { return _M_t.insert_unique(__x); }
    看的出来。因为map也是不允许存在重复key的,所以调用的是红黑树的insert_unique。

    我们前面分析过,multiset/set之间的主要区别就是调用的插入方法不同。所以我们就不再贴代码了。分析到这里就告一段落。


评论

发表评论