lower_bound

Artículo
03/27/2013

Encuentra la posición del primer elemento de un intervalo pedido que tiene un valor mayor o igual a un valor especificado, donde el criterio de ordenación se puede especificar por un predicado binario.

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
   );

Parámetros

_First
Un iterador hacia delante que dirige la posición del primer elemento del intervalo que se buscará.
_Last
Un iterador hacia delante que dirige la posición una más allá del último elemento en el intervalo que se buscará.
_Val
El valor cuya primera posición o primera posición posible se busca en el intervalo petición.
_Comp
Objeto definido por el usuario de la función de predicado en el que define sentido que un elemento es menor que otro.Un predicado binario toma dos argumentos y devuelve TRUE cuando se cumple y Falso cuando no se cumple.

Valor devuelto

Un iterador hacia delante en la posición del primer elemento de un intervalo petición con un valor que es mayor que o igual a un valor especificado, donde la equivalencia se especifica con un predicado binario.

Comentarios

El intervalo de origen ordenada hace referencia debe ser válido; todos los iteradores deben ser dereferenceable y dentro de la secuencia la posición última debe ser accesible de primera por el aumento.

Un intervalo ordenado es una condición previa de utilizar lower_bound y donde es igual el orden según lo especificado por con predicado binario.

El intervalo no se ha modificado el algoritmo lower_bound.

Los tipos de valor de iteradores hacia delante es necesario que comparable ser secuenciado, para, dadas dos elementos, poder determinar las que son equivalentes (en el sentido de que ninguno es menor que otro) o que uno es menor que otro.Esto produce el orden entre los elementos desiguales

La complejidad del algoritmo es logarítmica para iteradores de acceso aleatorio y lineal de otra manera, con el número de pasos proporcional a (_Last1 – _First1).

Ejemplo

// 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;
}