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 阅读(1033)
评论(0) 编辑 收藏 引用 所属分类:
STL读书笔记