STL源码剖析之RB_tree之insert_unique()与find()函数

发表于 | 更新于 | 分类于

这篇文章主要讲解STL源码剖析 P.224 P.229 中的find()和insert_unique()函数 . 这两个函数写的很巧妙 , 理解有点绕 . 网上都找不到讲解 , 都TM一堆抄书的.

注意事项

  1. 所使用的代码非书上代码 , 使用gcc代码/usr/include/c++/7/bits/stl_tree.h来说明(基本原理没变)

  2. 说明时我会把变量的前两个下划线去掉 , 打起来太烦了

  3. 在比较结点大小时 , 会使用_M_key_compare函数 , 这是一个仿函数 , 这里做一个约定 , 当这个函数返回 1 时 , 定义为前者比后者”小” , 这个”小”是抽象的小 , 下文表示>或<时都表示抽象的大或小 , 具体实现取决于_Key_compare . 如果将 1 定义为大的话 , - - 和 ++ 会是反向的.

源代码

_M_get_insert_unique_pos()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 template<typename _Key, typename _Val, typename _KeyOfValue,
          typename _Compare, typename _Alloc>
   pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
		   _Compare, _Alloc>::_Base_ptr,
 typename _Rb_tree<_Key, _Val, _KeyOfValue,
		   _Compare, _Alloc>::_Base_ptr>
   _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
   _M_get_insert_unique_pos(const key_type& __k)
   {
     typedef pair<_Base_ptr, _Base_ptr> _Res;
     _Link_type __x = _M_begin();
     _Base_ptr __y = _M_end();
     bool __comp = true;
     while (__x != 0)
{
  __y = __x;
  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
  __x = __comp ? _S_left(__x) : _S_right(__x);
}
     iterator __j = iterator(__y);
     if (__comp)
{
  if (__j == begin())
    return _Res(__x, __y);
  else
    --__j;
}
     if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
return _Res(__x, __y);
     return _Res(__j._M_node, 0);
   }

find()

1
2
3
4
5
6
7
8
9
10
11
12
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
      _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  find(const _Key& __k)
  {
    iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
    return (__j == end()
     || _M_impl._M_key_compare(__k,
			_S_key(__j._M_node))) ? end() : __j;
  }

_M_lower_bound()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 //这个函数在find()的第8行调用
 template<typename _Key, typename _Val, typename _KeyOfValue,
          typename _Compare, typename _Alloc>
   typename _Rb_tree<_Key, _Val, _KeyOfValue,
	      _Compare, _Alloc>::iterator
   _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
   _M_lower_bound(_Link_type __x, _Base_ptr __y,
	   const _Key& __k)
   {
     while (__x != 0)
if (!_M_impl._M_key_compare(_S_key(__x), __k))
  __y = __x, __x = _S_left(__x);
else
  __x = _S_right(__x);
     return iterator(__y);
   }

_M_insert_node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//放这个代码是为了说明我们定义的"大"会在左边
template<typename _Key, typename _Val, typename _KeyOfValue,
         typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
  {
    bool __insert_left = (__x != 0 || __p == _M_end()
	    || _M_impl._M_key_compare(_S_key(__z),
				      _S_key(__p)));

    _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
		    this->_M_impl._M_header);
    ++_M_impl._M_node_count;
    return iterator(__z);
  }

find()函数

find()函数第8行直接调用_M_lower_bound()函数 , 即找出要插入的变量 k 的下界.

进入_M_lower_bound()函数 , x 是 root 结点(_M_begin()) , y 是 end(header) , 只要 x 不为 0 , 就将 x 与 k 进行比较 , 如果 k ≤ x , 将 x 保存到 y 当中 , 同时向左找(小的在左边 , 可以在_M_insert_node函数中找到) . 当 x == 0 时 , 这个时候 y 不是保存的 x 的父结点 , 而是比 k 大的最小值 . 返回那个结点的迭代器.

find()函数第9行 , 第一个判断 j == end() , 我们可以知道只有当不存在 x 使 k ≤ x 时 , j 才为 end() , 即要寻找的值大于整个树的最大值 , 那当然不存在这样的值 , 返回 end().

第10和第11行第二个判断 , 此时 j 不为 end() . 下面就是精彩的地方了.

分为两种情况.

当 _M_key_compare(__k,_S_key(__j._M_node)) 返回 1 时 , 可知 j > k , 从_M_lower_bound()函数中 k ≤ j , 那么一定不存在 k (有些人可能考虑 j 的父结点是否可能等于 k , 见特殊说明1).

当 _M_key_compare(__k,_S_key(__j._M_node)) 返回 0 时 , 可知 j ≤ k , 从_M_lower_bound()函数中 k ≤ j , k 既大于等于 j , 又小于等于 j , 那么唯一的可能就是 k == j . 返回 j 所在的结点的迭代器.

insert_unique()

这个函数在GCC版本里改名为_M_get_insert_unique_pos() , 不过逻辑没改 , 返回值有所变动.

这个函数逻辑上和find()很相似 , 上面懂了的话这个应该也能看懂.

在第14到19行中一直在比较大小 , 我们可以看到 y 是插入点的父结点 , comp 存储了 k 与 x 的大小关系.

这里同样也要分为两种情况.

当 comp 为 1 时 , 如果 j == begin() , 即 k 比整个树最小值还小 , 那么可以插入 . 如果不等于begin() , 将 j 变为 j- - , 即比 j 小的那个数(j- - 与 j 整体大小上相邻) . 此时再比较 j- - 与 k 的大小 , 如果 k > j- - , 又根据 comp 为 1 可以看出 j > k , 也就是说 k 位于 j- - 与 j 之间 , 那么必然是唯一的 . 如果 j- - ≥ k , 见特殊说明3.

当 comp 为 0 时 . 即 k ≥ j , 此时再比较 j 与 k 大小 , 如果 k > j , 那么唯一(有些人可能会考虑 j 的父结点等于 k , 见特殊说明2). 否则的话即 j ≥ k , 此时 j == k , 不唯一.

特殊说明

  1. 如果 j 的某个父结点等于 k , 那么那个时候会向左 , 而左边的所有结点都比 k 小 , 最后比较时不可能出现 j > k 的情况 . 即一路上不重复且正确方向到底.

  2. 如果 j 的某个父结点等于 k , 那么那个时候会向右 , 而右边的所有结点都比 k 大 , 最后比较时不可能出现 k > j 的情况 . 即一路上不重复且正确方向到底.

  3. j ≥ k  and  j- - ≥ k , 比 j 小的 j- - 只能出现在 j 的左子树和不为左结点的父结点的父结点(设为 M ) , 因为 x == 0 , 所以左子树为空 , 而 j 是在 M 的右结点的左结点下 , 即 k ≥ j- - , 此时可得 k 不唯一.