Export (0) Print
Expand All
This topic has not yet been rated - Rate this topic

lower_bound

Finds the position of the first element in an ordered range that has a value greater than or equivalent to a specified value, where the ordering criterion may be specified by a binary predicate.

template<class ForwardIterator, class Type>
   ForwardIterator lower_bound(
      ForwardIterator _First, 
      ForwardIterator _Last,
      const Type& _Val
   );
template<class ForwardIterator, class Type, class BinaryPredicate>
   ForwardIterator lower_bound(
      ForwardIterator _First, 
      ForwardIterator _Last,
      const Type& _Val,
      BinaryPredicate _Comp
   );

Parameters

_First
A forward iterator addressing the position of the first element in the range to be searched.
_Last
A forward iterator addressing the position one past the final element in the range to be searched.
_Val
The value whose first position or possible first position is being searched for in the ordered range.
_Comp
User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

Return Value

A forward iterator at the position of the first element in an ordered range with a value that is greater than or equivalent to a specified value, where the equivalence is specified with a binary predicate.

Remarks

The sorted source range referenced must be valid; all iteratora must be dereferenceable and within the sequence the last position must be reachable from the first by incrementation.

A sorted range is a precondition of using lower_bound and where the ordering is the same as specified by with binary predicate.

The range is not modified by the algorithm merge.

The value types of the forward iterators need be less-than comparable to be ordered, so that, given two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements

The complexity of the algorithm is logarithmic for random-access iterators and linear otherwise, with the number of steps proportional to (_Last1 – _First1).

Example

// alg_lower_bound.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // For greater<int>( )
#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser ( int elem1, int elem2 )
{
   if ( elem1 < 0 )
      elem1 = - elem1;
   if ( elem2 < 0 )
      elem2 = - elem2;
   return elem1 < elem2;
}

int main( )
{
   using namespace std;
   vector <int> v1;
   vector <int>::iterator Iter1, Result1;

   // Constructing vectors v1a & v1b with default less than ordering
   int i;
   for ( i = -1 ; i <= 4 ; i++ )
   {
      v1.push_back(  i );
   }

   int ii;
   for ( ii =-3 ; ii <= 0 ; ii++ )
   {
      v1.push_back(  ii  );
   }

   sort ( v1.begin ( ) , v1.end ( ) );
   cout << "Original vector v1 with range sorted by the\n "
        << "binary predicate less than is  v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   // Constructing vectors v2 with range sorted by greater
   vector <int> v2 ( v1 );
   vector <int>::iterator Iter2, Result2;
   sort ( v2.begin ( ) , v2.end ( ) , greater<int> ( ) );

   cout << "Original vector v2 with range sorted by the\n "
        << "binary predicate greater is    v2 = ( " ;
   for ( Iter2 = v2.begin ( ) ; Iter2 != v2.end ( ) ; Iter2++ )
      cout << *Iter2 << " ";
   cout << ")." << endl;

   // Constructing vectors v3 with range sorted by mod_lesser
   vector <int> v3 ( v1 );
   vector <int>::iterator Iter3, Result3;
   sort ( v3.begin ( ) , v3.end ( ) , mod_lesser );

   cout << "Original vector v3 with range sorted by the\n "
        <<  "binary predicate mod_lesser is v3 = ( " ;
   for ( Iter3 = v3.begin ( ) ; Iter3 != v3.end ( ) ; Iter3++ )
      cout << *Iter3 << " ";
   cout << ")." << endl;

   // lower_bound of 3 in v1 with default binary predicate less <int> ( )
   Result1 = lower_bound ( v1.begin ( ) , v1.end ( ) , 3 );
   cout << "The lower_bound in v2 for the element with a value of 3 is: "
        << *Result1 << "." << endl;

   // lower_bound of 3 in v2 with the binary predicate greater <int> ( )
   Result2 = lower_bound ( v2.begin ( ) , v2.end ( ) , 3, greater <int> ( ) );
   cout << "The lower_bound in v2 for the element with a value of 3 is: "
        << *Result2 << "." << endl;

   // lower_bound of 3 in v3 with the binary predicate  mod_lesser
   Result3 = lower_bound ( v3.begin ( ) , v3.end ( ) , 3,  mod_lesser  );
   cout << "The lower_bound in v3 for the element with a value of 3 is: "
        << *Result3 << "." << endl;
}

Output

Original vector v1 with range sorted by the
 binary predicate less than is  v1 = ( -3 -2 -1 -1 0 0 1 2 3 4 ).
Original vector v2 with range sorted by the
 binary predicate greater is    v2 = ( 4 3 2 1 0 0 -1 -1 -2 -3 ).
Original vector v3 with range sorted by the
 binary predicate mod_lesser is v3 = ( 0 0 -1 -1 1 -2 2 -3 3 4 ).
The lower_bound in v2 for the element with a value of 3 is: 3.
The lower_bound in v2 for the element with a value of 3 is: 3.
The lower_bound in v3 for the element with a value of 3 is: -3.

See Also

<algorithm> Members | lower_bound Sample | Predicate Version of lower_bound Sample

Show:
© 2014 Microsoft. All rights reserved.