C++STLアルゴリズムlower_bound、upper_bound、equal_range

3905 ワード

参考『C++Primer』
//全ての容器適用(O(log(n))))シーケンシャル区間検索アルゴリズム
lower_bound()/最初に一致する要素を探して、位置反復器を返して、valが現れた最初の位置を返します
upper_bound()/最後の一致する要素を探して、位置反復器を返して、Valが現れた最後の位置の次の位置を返します
equal_range()/一対の反復器pair(<>,<>)を探し、lower_に等しいbound()とupper_bound(). 関連コンテナには等価なメンバー関数があり、パフォーマンスが向上します.
#include  
#include  
#include  
#include  
#include  
using namespace std;  
  
/************************************************************************************* 
std::lower_bound                                                    algorithm 
-------------------------------------------------------------------------------------- 
template  
  ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, 
                                const T& value ); 
 
template  
  ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, 
                                const T& value, Compare comp ); 
 
//eg: 
template  
  ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value ) 
{ 
  ForwardIterator it; 
  iterator_traits::difference_type count, step; 
  count = distance(first,last); 
  while (count>0) 
  { 
    it = first; step=count/2; advance (it,step); 
    if (*it 
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, 
                                const T& value ); 
 
template  
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, 
                                const T& value, Compare comp ); 
 
//eg: 
template  
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value ) 
{ 
  ForwardIterator it; 
  iterator_traits::difference_type count, step; 
  count = distance(first,last); 
  while (count>0) 
  { 
    it = first; step=count/2; advance (it,step); 
    if (!(value 
  pair 
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value ); 
 
template  
  pair 
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value, 
                  Compare comp ); 
 
//eg: 
template  
  pair 
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value ) 
{ 
  ForwardIterator it = lower_bound (first,last,value); 
  return make_pair ( it, upper_bound(it,last,value) ); 
} 
*************************************************************************************/  
bool mygreater (int i,int j){ return (i>j); }  
  
int main()  
{  
    int myints[] = {10,20,30,30,20,10,10,20};  
    vector v(myints,myints+8);           // 10 20 30 30 20 10 10 20  
    vector::iterator low,up;  
  
    sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30  
  
    cout<::iterator,vector::iterator> bounds;  
  
    // using default comparison:  
//  sort (v.begin(), v.end());                              // 10 10 10 20 20 20 30 30  
    bounds=equal_range (v.begin(), v.end(), 20);            //          ^        ^  
    cout<