STL之rb_tree的find函数

本文主要是介绍STL之rb_tree的find函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 通用的search方法

STL在实现对特定key值的查找时,并没有采用通用的方法:

BRTreeNode *  rb_tree_search(RBTreeNode * x, int key){while(x ! = NULL && x->key != key){if( x->key > key){x = x ->left;}else{x = x->right;}}return x;
}

如果rb_tree树中允许多个相同的key同时存在.上述方法查找到的是中序顺序中的位置最后的那个,

如果要求要求查找的是中序顺序中的第一个出现的位置呢?

看看STL是怎么实现的.

2 find源码

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;}

STL采用的lower_bound函数实现.若干j指向end()或k 比j的值还小则不存在.

3 lower_bound源码

template<typename _Key, typename _Val, typename _KeyOfValue,typename _Compare, typename _Alloc>typename _Rb_tree<_Key, _Val, _KeyOfValue,_Compare, _Alloc>::const_iterator_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,const _Key& __k) const{while (__x != 0)if (!_M_impl._M_key_compare(_S_key(__x), __k))//__x >= k__y = __x, __x = _S_left(__x);else__x = _S_right(__x);return const_iterator(__y);}

引入一个y变量,记录中序顺序中第一个比k大或相等的位置.
如果要找最大的位置呢.自然的想到upper_bound函数.怎么实现?

4 upper_bound源码

  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_upper_bound(_Link_type __x, _Link_type __y,const _Key& __k){while (__x != 0)if (_M_impl._M_key_compare(__k, _S_key(__x)))//__x > k__y = __x, __x = _S_left(__x);else__x = _S_right(__x);return iterator(__y);}

这篇关于STL之rb_tree的find函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---