Requisitos previos: iteradores de acceso aleatorio , iteradores bidireccionales
Los conjuntos son un tipo de contenedor asociativo en el que cada elemento tiene que ser único porque el valor del elemento lo identifica. El valor del elemento no se puede modificar una vez que se agrega al conjunto, aunque es posible eliminar y agregar el valor modificado de ese elemento.
Funciones asociadas a Set:
- begin() : Devuelve un iterador al primer elemento del conjunto.
- end() : Devuelve un iterador al elemento teórico que sigue al último elemento del conjunto.
- size() : Devuelve el número de elementos del conjunto.
- max_size() : Devuelve el número máximo de elementos que puede contener el conjunto.
- vacío() : devuelve si el conjunto está vacío.
Este artículo se centra en la diferencia entre std::set::upper_bound y std::upper_bound en C++.
std::upper_bound() en C++
El método upper_bound() en C++ se usa para devolver un iterador que apunta al primer elemento en el rango [primero, último] que tiene un valor mayor que el valor dado.
std::set::upper_bound() en C++
set::upper_bound() es una función incorporada en C++ STL que devuelve un iterador que apunta al elemento en el contenedor que es mayor que el valor ‘x’ pasado como parámetro. 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.
std::upper_bound() frente a std::set::upper_bound()
A continuación se muestran algunas de las diferencias entre std::upper_bound() y std::set::upper_bound().
| No Señor. | std::superior_enlace() | std::set::superior_enlace() |
| 1 | Sintaxis- std::upper_bound(ForwardIterator primero, ForwardIterator último, const T& val). |
Sintaxis- std::upper_bound(const value_type& val). |
| 2 | El std::upper_bound tiene iteradores de acceso aleatorio e iteradores de acceso no aleatorio. | El std::set::upperoptimizes_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 mediante iteradores bidireccionales. |
| 4 | La complejidad del tiempo de ejecución es O(log2N) 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(log2N) debido a su implementación del árbol de búsqueda binaria. |
En los siguientes ejemplos, hemos ilustrado el tiempo de ejecución de la CPU tomado por ambas funciones. En general, se prefiere el método std::set::upper_bound() sobre el método std::upper_bound().
Ejemplo: std::upper_bound()
A continuación se muestra el programa C++ para ilustrar la función std::upper_bound().
C++
// C++ program to illustrate
// std::set::upper_bound
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
// Function whose time is to
// be measured
void myFunction()
{
// Initialise the set
set<int> s;
// Insert element in the set
for (int i = 0; i < 10; i++) {
s.insert(i);
}
// Use upper_bound() function
// to find 5
set<int>::iterator it;
it = upper_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
myFunction();
// Stop timer
gettimeofday(&end, NULL);
// Calculating total time taken
// by the program.
double totalTime;
totalTime = (end.tv_sec - start.tv_sec) * 1e6;
totalTime
= (totalTime + (end.tv_usec - start.tv_usec))
* 1e-6;
cout << "Time taken by the program is : " << fixed
<< totalTime << setprecision(6);
cout << " sec" << endl;
return 0;
}
Time taken by the program is : 0.000056 sec
Ejemplo: std::set::upper_bound()
A continuación se muestra el programa C++ para ilustrar la función std::set::upper_bound().
C++
// C++ program to illustrate
// std::upper_bound
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
// Function whose time is to
// be measured
void myFunction()
{
// Initialise the set
set<int> s;
// Insert element in the set
for (int i = 0; i < 10; i++) {
s.insert(i);
}
// Use set::upper_bound() function
// to find 5
set<int>::iterator it;
it = s.upper_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);
myFunction();
// Stop timer
gettimeofday(&end, NULL);
// Calculating total time taken
// by the program.
double totalTime;
totalTime = (end.tv_sec - start.tv_sec) * 1e6;
totalTime
= (totalTime + (end.tv_usec - start.tv_usec))
* 1e-6;
cout << "Time taken by program is : " << fixed
<< totalTime << setprecision(6);
cout << " sec" << endl;
return 0;
}
Time taken by program is : 0.000043 sec