随笔-16  评论-7  文章-0  trackbacks-0

 

   lower_bound&upper_bound是二分查找的一种版本,在已排序的区间中寻找可插入value的第一个位置和第一个不小于value的位置。
   lower_bound的实现(forward_iteratror版本,其random_access_iterator版本不需要用distance函数,直接用+):

template<class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first,
                              ForwardIterator last,
                              
const T& value,
                              Distance
*,
                              forward_iterator_tag)
{
    Distance len
=0;
    distance(first, last, len);    
//求整个区间的长度
    Distance half;
    ForwardIterator middle;

    
while(len>0)
    
{
        half
=len>>1;            //除以二
        middle=first;
        advance(middle, half);    
//middle指向中间位置
        if(*middle<value)
        
{
            first 
= middle;
            
++first;
            len
=len-half-1;        //修正len
        }

        
else
            len
=half;
    }

    
return first;
}

upper_bound的实现(forward_iterator版本):

template<class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first,
                              ForwardIterator last,
                              
const T& value,
                              Distance
*,
                              forward_iterator_tag)
{
    Distance len
=0;
    distance(first, last, len);    
//求整个区间的长度
    Distance half;
    ForwardIterator middle;

    
while(len>0)
    
{
        half
=len>>1;            //除以二
        middle=first;
        advance(middle, half);    
//middle指向中间位置
        if(value<*middle)
        
{
            len
=half;
        }

        
else
        
{
            first 
= middle;
            
++first;
            len
=len-half-1;        //修正len
        }

    }

    
return first;
}


   upper_bound和lower_bound的区别在于取等号时的做法。upper_bound将等号放在大于号一起处理,lower_bound则相反,因此两者最终得到的结果也不同。binary_search()可以通过lower_bound得到。

排序算法(重点):
   partial_sort:将一个区间内的前N个元素进行排序。
   方法:堆排序:(从小到大排序)先将前N个元素make_heap,生成一个max_heap,然后对N+1~size的元素与max_heap的顶依次比较,如果比堆顶元素小,则交换两元素位置,再对堆进行重排。循环过后再对堆进行sort_heap。
make_heap(first, middle);
for(RandomAccessIterator i = middle; i<last; ++i)    //只能是随机迭代器
    if(*i<*first)
        __pop_heap(first, middle, i ,T(
*i), dfistance_type(first));
    sort_heap(first, middle);

   sort:对所给区间进行排序。
   方法:快速排序(改进版),改进方法:结合插入排序、采用三点中值法选区pivot,使用内省式排序(在结合插入排序、三点中值法的同时,检测如果递归次数达到限定次数时,改为使用堆排序,防止出现二次的时间效率。)
   sort接受两个随机迭代器作为参数(只有随机迭代器能够使用sort)
inline void sort(RandomAccessIterator first, RandomAccessIterator last)
{
    
if(first != last)
    
{
        __introsort_loop(first, last, value_type(first)        
//内省式排序
                         __lg(last-first)*2);
        __final_insertion_sort(first, last);                
//最终进行一次插入排序
    }

}

   __lg()用来控制最多的递归次数,找出2^k<n的最大K。当个数为40时,得到5。5*2=10为最多允许分割层数。
template<class Size>
inline Size __lg(size n)
{
    Size k;
    
for(k=0; n>1; n>>=1++k;
    
return k;
}

    
void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last.
                      T
*, Size depth_limit)
{
    
while(last-first>__stl_threshold)    //__stl_threshold=const int 16
    {
        
if(depth_limit==0)
        
{
            partial_sort(first, last, last);    
//改用heapsort
            return;
        }


        
--depth_limit;
        RandomAccessIterator cut 
= __unguarded_partition(first, last, T(__median(*first,
            
*(first+(last-first)/2,
            
*(last-1)))));
        
//cur为三点中值法求出来的pivot
        
//右半段递归
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last
=cut;//定位到左半段再递归处理(左右共用一个depth_limit)
    }

}


   分割方法:
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
                                           RandomAccessIterator last,
                                           T pivot)
{
    
while(true)
    
{
        
while(*first < pivot) ++first;
        
--last;
        
while(pivot < *last) --last;
        
if(!(first<last)) return first;
        iter_swap(first, last);
        
++first;
    }

}


   在上述步骤做完以后,变将区间内元素分成了多个元素个数少于16的子序列,这个时候就进入到母函数,然后进行最后的插入排序。
   SGI STL的最后插入排序是将其分成两部分:前一部分直接调用插入排序。后一部分再重写的一段插入排序(为什么这样做?)。
posted on 2011-06-08 01:06 dead_horse 阅读(983) 评论(0)  编辑 收藏 引用 所属分类: STL读书笔记

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理