STL源码剖析 lower

lower_bound

• 二分查找的一种版本，试图在已经排序的区间内查找元素value，如果区间内存在和value数值相等的元素，便返回一个迭代器，指向其中的第一个元素。
• 如果没有数值相等的元素，会返回假设这个元素存在的前提下应该出现的位置，也就是返回一个指向第一个不小于value的元素的迭代器
• 如果查询的数值value大于区间内任何一个元素则返回last
• 综上所述：lower_bound返回的是不破坏排序状态的前提下，可插入value的第一个位置

• 版本一使用operator<
• 版本二使用仿函数 comp(*j,value)为true

template 
ForwardIterator lower_bound(ForwardIterator first,ForwardIterator last,const T& value){
    ForwardIterator it;
    typename std::iterator_traits::difference_type count,step;
    count = std::distance(first,last);
    while (count > 0){
        it = first;
        step = count / 2;
        std::advance(it,step);
        if(*it < value){
            first = ++it;
            count = count - step+1;
        } else{
            count = step;
        }
    }
    return first;
}

// lower_bound/upper_bound example
#include      // std::cout
#include     // std::lower_bound, std::upper_bound, std::sort
#include        // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << 'n';
  std::cout << "upper_bound at position " << (up - v.begin()) << 'n';

  return 0;
}

• 不破坏插入顺序的情况下返回可以插入的最后一个合适的位置
• 即如果元素存在，返回的迭代器指向的是value的下一个数值，而不是指向value本身，类似于last

template 
ForwardIterator upper_bound(ForwardIterator first,ForwardIterator last,const T& value){
    ForwardIterator it;
    typename std::iterator_traits::difference_type count,step;
    count = std::distance(first,last);
    while (count > 0){
        it = first;
        step = count / 2;
        std::advance(it,step);
        if(!(*it < value)){
            first = ++it;
            count = count - step+1;
        } else{
            count = step;
        }
    }
    return first;
}

• 二分查找
• 利用lower_bound 如果value存在返回其应该出现的位置 ，对指定位置的迭代器进行解引用和value比较，确定元素是否存在

template 
ForwardIterator binary_search(ForwardIterator first,ForwardIterator last,const T& value){
    first = std::lower_bound(first,last,value);
    return (first!=last && !(*first > value));
}

// binary_search example
#include      // std::cout
#include     // std::binary_search, std::sort
#include        // std::vector

bool myfunction (int i,int j) { return (i v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

  // using default comparison:
  std::sort (v.begin(), v.end());

  std::cout << "looking for a 3... ";
  if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!n"; else std::cout << "not found.n";

  // using myfunction as comp:
  std::sort (v.begin(), v.end(), myfunction);

  std::cout << "looking for a 6... ";
  if (std::binary_search (v.begin(), v.end(), 6, myfunction))
    std::cout << "found!n"; else std::cout << "not found.n";

  return 0;
}

• 函数会取得first，last区间范围内所标示的序列的下一个组合，则返回true，否则false 

• 随机重排，N!可能性 N = last - first
• 均匀分布 每种序列被选中的可能性均为1/N!
• 版本一使用 内部随机数
• 版本二使用 使用随机数仿函数，需要仿函数传递的方式是引用传递，因为这个考虑到随机数产生器拥有局部状态，每次调用都会被改变，从而保障数据的随机性

template 
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomNumberGenerator& gen)
{
  iterator_traits::difference_type i, n;
  n = (last-first);
  for (i=n-1; i>0; --i) {
    swap (first[i],first[gen(i+1)]);
  }
}

// random_shuffle example
#include      // std::cout
#include     // std::random_shuffle
#include        // std::vector
#include         // std::time
#include       // std::rand, std::srand

// random generator function:
int myrandom (int i) { return std::rand()%i;}

int main () {
  std::srand ( unsigned ( std::time(0) ) );
  std::vector myvector;

  // set some values:
  for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

  // using built-in random generator:
  std::random_shuffle ( myvector.begin(), myvector.end() );

  // using myrandom:
  std::random_shuffle ( myvector.begin(), myvector.end(), myrandom);

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << 'n';

  return 0;
}

• 函数接受一个middle迭代器，位于起始first和终止last迭代器内部，但是只对first到middle区间内的元素进行从小到大的排序，middle到last区间内的元素乱序
• 这个函数的含义是 保证middle到first内的元素是按照从小到大排序的，但是middle到last是相较于middle之前的元素要大，但是没人有何特定的顺序
• 第一版本使用 less-than操作符
• 第二版本使用 仿函数comp，算法内部采用heap sort来完成任务 ，max_heap大根堆，将每一个元素和最大的数值进行比较，也就是第一个元素。

// partial_sort example
#include      // std::cout
#include     // std::partial_sort
#include        // std::vector

bool myfunction (int i,int j) { return (i myvector (myints, myints+9);

  // using default comparison (operator <):
  std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());

  // using function as comp
  std::partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << 'n';

  return 0;
}

•  RandomAccessIterators(随机迭代器)，将区间内的元素按照从小到大进行排序
• 第二版本：仿函数作为排序的准则
• STL关系型数据库内部使用红黑树，已经经过了排序，不需要sort
• 序列式容器：stack queue  priority_queue元素按照特定的方式进行出入，不允许排序
• vector 和 deque 迭代器属于RandomAccessIterators 可以使用迭代器 sort
• list的迭代器的类型是Bidirectioinallterators 不适用，使用数据成员自带的sort排序算法
• slist的迭代器的类型是ForwardIterators 不适用，使用数据成员自带的sort排序算法
• 数据量很大 使用快速排序，一旦数据量少于某个阈值就改用 插入排序，避免快速排序带来的额外负载；如果递归层次过深，就改用 堆排序

插入排序

• 使用lower_bound和upper_bound两个函数返回的迭代器组成pair元祖的形式，first指向等于元素的区间起始点，second指向等于元素的下一个位置处
• 如果不存在，那么first和second都指向的同一个位置

template 
  pair
    equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it = std::lower_bound (first,last,val);
  return std::make_pair ( it, std::upper_bound(it,last,val) );
}

// equal_range example
// equal_range example
#include      // std::cout
#include     // std::equal_range, std::sort
#include        // std::vector

bool mygreater (int i,int j) { return (i>j); }

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  std::pair::iterator,std::vector::iterator> bounds;

  // using default comparison:
  std::sort (v.begin(), v.end());                              // 10 10 10 20 20 20 30 30
  bounds=std::equal_range (v.begin(), v.end(), 20);            //          ^        ^

  // using "mygreater" as comp:
  std::sort (v.begin(), v.end(), mygreater);                   // 30 30 20 20 20 10 10 10
  bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); //       ^        ^

  std::cout << "bounds at positions " << (bounds.first - v.begin());
  std::cout << " and " << (bounds.second - v.begin()) << 'n';

  return 0;
}

•  将两个排好顺序的子序列 合并形成一个单调递增的序列
• 稳定排序
• 如果使用额外的内存空间速度会很快，没有多余的内存空间也是可以进行元素的合并的

// inplace_merge example
#include      // std::cout
#include     // std::inplace_merge, std::sort, std::copy
#include        // std::vector

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector v(10);
  std::vector::iterator it;

  std::sort (first,first+5);
  std::sort (second,second+5);

  it=std::copy (first, first+5, v.begin());
     std::copy (second,second+5,it);

  std::inplace_merge (v.begin(),v.begin()+5,v.end());

  std::cout << "The resulting vector contains:";
  for (it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << 'n';

  return 0;
}

• 算法会重新排列[first ，last)区间 ,使得迭代器nth指向的元素于经过排序之后同一位置的元素数值相等，这个其实就是快速排序的思路一样，确定一个元素的位置，他的左边都是比他小的元素，他的右边都是比他大的元素

• nth_element 比 partial_sort保证的更少，不保证左边和右边序列有序
• 只支持随机访问迭代器

• 合并排序
• 分而治之 
• 需要额外内存