stl upper_bound函数实现

写了一个upper_bound的实现。其中递归使用二分法求解最上界，虽然写的完全不像STL的风格，但是练手还是可以的。

view plaincopy to clipboardprint?
01.#include<iostream>  
02.#include<iterator>  
03.#include<cstring>  
04.#include<cassert>  
05.using namespace std;  
06.int UpperBound(int* a, int start, int end , const int& value){  
07.    int mid = 0;  
08.    int index = 0;  
09.    int up_index = 0;  
10.    if(a[end]<value)  
11. // 特判比最后一个数大时，end+1  
12.        return end+1;  
13.        //这里是经典的二分  
14.    while(start<= end){  
15.        mid = start + (end - start)/2;  
16.        if(a[mid] == value){  
17.            index = mid + 1;  
18.                        // 去递归的找一下上界  
19.            up_index = UpperBound(a,mid+1,end,value);  
20.                        // 如果找到的上界比现在的还小，那么就用现在的  
21.            return up_index > index? up_index : index;  
22.        }  
23.        else if(a[mid]<value){  
24.            start = mid+1;  
25.        }  
26.        else{  
27.            end = mid-1;  
28.                        // 记录上界  
29.            index = mid;  
30.        }  
31.    }  
32.    return index;  
33.} 
#include<iostream>
#include<iterator>
#include<cstring>
#include<cassert>
using namespace std;
int UpperBound(int* a, int start, int end , const int& value){
 int mid = 0;
 int index = 0;
 int up_index = 0;
 if(a[end]<value)
 // 特判比最后一个数大时，end+1
  return end+1;
        //这里是经典的二分
 while(start<= end){
  mid = start + (end - start)/2;
  if(a[mid] == value){
   index = mid + 1;
                        // 去递归的找一下上界
   up_index = UpperBound(a,mid+1,end,value);
                        // 如果找到的上界比现在的还小，那么就用现在的
   return up_index > index? up_index : index;
  }
  else if(a[mid]<value){
   start = mid+1;
  }
  else{
   end = mid-1;
                        // 记录上界
   index = mid;
  }
 }
 return index;
}

如果原数组中没有存在那个元素，就根本没有调用那个递归程序，递归只有在出现多个此元素时才会调用。另外中间递归调用段地方还可以改写为：

view plaincopy to clipboardprint?
01.if(a[mid] == value){  
02.   index = mid + 1;  
03.   /* 
04.    up_index = UpperBound(a,mid+1,end,value); 
05.    return up_index > index? up_index : index; 
06.   */ 
07.   // 因为只有在递归调用中start>end时，才会返回一个index = 0  
08.   return (mid+1>end) ? index : UpperBound(a,mid+1,end,value);  
09.} 
if(a[mid] == value){
   index = mid + 1;
   /*
    up_index = UpperBound(a,mid+1,end,value);
    return up_index > index? up_index : index;
   */
   // 因为只有在递归调用中start>end时，才会返回一个index = 0
   return (mid+1>end) ? index : UpperBound(a,mid+1,end,value);
}

这样写完后写一下测试代码,顺便wrap一层upper_bound：

view plaincopy to clipboardprint?
01.int upper_bound(int * a,int n, const int& value){  
02.    // 使用宏可以在编译时去除  
03.    #ifdef TEST  
04.    // pre-condition  
05.    assert(NULL != a && n>0);  
06.    // check the array a is sorted by elements      
07.    for(int i = 1; i < n; i++){  
08.         assert(a[i-1]<=a[i]);  
09.    }  
10.    int * tmp_a = new int[n];  
11.    memcpy(tmp_a,a,sizeof(int)*n);  
12.    #endif  
13.    int index = UpperBound(a,0,n-1,value);  
14.      
15.    #ifdef TEST  
16.    // post-condition  
17.    //check whether the array is changed or not  
18.    for(int i = 0; i < n; i++)  
19.        assert(a[i] == tmp_a[i]);  
20.    if(index == 0){  
21.        // min  
22.        assert(a[index]>value);  
23.    }  
24.    else if(index == n){  
25.        // max  
26.        assert(a[index-1]<=value);  
27.    }  
28.    else{  
29.        assert(a[index]>value && a[index-1]<=value);  
30.    }  
31.    delete [] tmp_a;  
32.    #endif  
33.    return index;  
34.} 
int upper_bound(int * a,int n, const int& value){
    // 使用宏可以在编译时去除
    #ifdef TEST
    // pre-condition
    assert(NULL != a && n>0);
    // check the array a is sorted by elements   
    for(int i = 1; i < n; i++){
         assert(a[i-1]<=a[i]);
    }
    int * tmp_a = new int[n];
    memcpy(tmp_a,a,sizeof(int)*n);
    #endif
    int index = UpperBound(a,0,n-1,value);
   
    #ifdef TEST
    // post-condition
    //check whether the array is changed or not
    for(int i = 0; i < n; i++)
        assert(a[i] == tmp_a[i]);
    if(index == 0){
        // min
        assert(a[index]>value);
    }
    else if(index == n){
        // max
        assert(a[index-1]<=value);
    }
    else{
        assert(a[index]>value && a[index-1]<=value);
    }
    delete [] tmp_a;
    #endif
    return index;
}

如果希望别人不调用UpperBound而只调用upper_bound,可以使用static 关键字， 将UpperBound限制在只在本文件中使用。别人调用就只能调用upper_bound()函数。不过STL的教学源码比我这精简的多，根本无须使用递归。真正的STL源码变量名称会使用下划线__作为起始。

view plaincopy to clipboardprint?
01.template <class ForwardIterator, class T>  
02.  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value )  
03.{  
04.  ForwardIterator it;  
05.  iterator_traits<ForwardIterator>::distance_type count, step;  
06.  count = distance(first,last);  
07.  while (count>0)  
08.  {  
09.    it = first; step=count/2; advance (it,step);  
10.    if (!(value<*it))                 // or: if (!comp(value,*it)), for the comp version  
11.      { first=++it; count-=step+1;  }  
12.    else count=step;  
13.  }  
14.  return first;  
15.} 
template <class ForwardIterator, class T>
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value )
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::distance_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (!(value<*it))                 // or: if (!comp(value,*it)), for the comp version
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}
 

这里的advance()函数定义类似:

view plaincopy to clipboardprint?
01.template<class Iterator, class Distance>  
02.void advance(Iterator& i, Distance n);  
03.类似于  i = x.begin()+n; i is an iterator of x 
template<class Iterator, class Distance>
void advance(Iterator& i, Distance n);
类似于  i = x.begin()+n; i is an iterator of x

最后把主函数贴上做结：

view plaincopy to clipboardprint?
01.int main(int argc, char* argv[])  
02.{  
03. 
04.   // 这里你可以使用random的方法进行测试。  
05. 
06.    int x[] = {1,2,3,4,5,5,5,5,9};  
07.    vector<int> v(x,x+9);  
08.    sort(v.begin(),v.end());  
09.    cout << (int)(upper_bound(v.begin(),v.end(),9)-v.begin());  
10.    cout << upper_bound(x,9,9);  
11.    return 0;  
12.}