Requisito previo: iteradores de acceso aleatorio en C++ , iteradores bidireccionales en C++ .
std::lower_bound en C++:
El método lower_bound() en C++ se usa para devolver un iterador que apunta al primer elemento en el rango [primero, último] que tiene un valor no menor que el valor dado. Esto significa que la función devuelve el índice del siguiente número más pequeño justo mayor que ese número.
std::set::lower_bound en C++:
set ::lower_bound() es una función incorporada en C++ STL que devuelve un iterador que apunta al elemento en el contenedor que es equivalente a K pasado en el parámetro. En caso de que K no esté presente en el contenedor del conjunto , la función devuelve un iterador que apunta al siguiente elemento inmediato que es mayor que K. Si la clave pasada en el parámetro excede el valor máximo en el contenedor, entonces el iterador devolvió puntos al último elemento en el contenedor establecido.
A continuación se muestra la diferencia entre std::lower_bound y std::set::lower_bound:
| S. No. | estándar::límite_inferior() | std::set::lower_bound() |
|---|---|---|
| 1 | Sintaxis: std::lower_bound(ForwardIterator primero, ForwardIterator último, const T& val). | Sintaxis: std::lower_bound(const value_type& val). |
| 2 | El std::lower_bound tiene iteradores de acceso aleatorio e iteradores de acceso no aleatorio. | El std::set::lower_bound tiene iteradores bidireccionales. |
| 3 | Esta función optimiza el número de comparaciones, lo cual es eficiente para iteradores de acceso aleatorio. | Esta función optimiza el número de comparaciones usando iteradores bidireccionales |
| 4 | La complejidad del tiempo de ejecución es O(log 2 N) para los iteradores de acceso aleatorio, pero para los iteradores de acceso no aleatorio es O(N). | La complejidad del tiempo de ejecución siempre es O (log 2 N) debido a su implementación del árbol de búsqueda binaria. |
A continuación se muestra el programa con el tiempo de ejecución de la CPU que ilustrará el tiempo de ejecución de ambas funciones.
Programa para ilustrar de std::lower_bound() :
// C++ program to illustrate
// std::set::lower_bound
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
// Function whose time is to
// be measured
void fun()
{
// Initialise the set
set<int> s;
// Insert element in the set
for (int i = 0; i < 10; i++) {
s.insert(i);
}
// Use lower_bound() function
// to find 5
set<int>::iterator it;
it = lower_bound(s.begin(), s.end(), 5);
}
// Driver Code
int main()
{
// Use function gettimeofday()
// can get the time
struct timeval start, end;
// Start timer
gettimeofday(&start, NULL);
// unsync the I/O of C and C++.
ios_base::sync_with_stdio(false);
// Function Call
fun();
// Stop timer
gettimeofday(&end, NULL);
// Calculating total time taken
// by the program.
double time_taken;
time_taken = (end.tv_sec
- start.tv_sec)
* 1e6;
time_taken = (time_taken
+ (end.tv_usec
- start.tv_usec))
* 1e-6;
cout << "Time taken by program is : "
<< fixed
<< time_taken << setprecision(6);
cout << " sec" << endl;
return 0;
}
Time taken by program is : 0.000046 sec
Programa para ilustrar de std::set::lower_bound() :
// C++ program to illustrate
// std::lower_bound
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
// Function whose time is to
// be measured
void fun()
{
// Initialise the set
set<int> s;
// Insert element in the set
for (int i = 0; i < 10; i++) {
s.insert(i);
}
// Use set::lower_bound() function
// to find 5
set<int>::iterator it;
it = s.lower_bound(5);
}
// Driver Code
int main()
{
// Use function gettimeofday()
// can get the time
struct timeval start, end;
// Start timer
gettimeofday(&start, NULL);
// unsync the I/O of C and C++.
ios_base::sync_with_stdio(false);
fun();
// Stop timer
gettimeofday(&end, NULL);
// Calculating total time taken
// by the program.
double time_taken;
time_taken = (end.tv_sec
- start.tv_sec)
* 1e6;
time_taken = (time_taken
+ (end.tv_usec
- start.tv_usec))
* 1e-6;
cout << "Time taken by program is : "
<< fixed
<< time_taken << setprecision(6);
cout << " sec" << endl;
return 0;
}
Time taken by program is : 0.000039 sec