CKTIS / C++
std::upper_bound — el límite después de los elementos equivalentes
`std::upper_bound` encuentra el límite de la partición para el valor buscado: devuelve un iterador al primer elemento para el que `value` es menor que dicho elemento según la comparación utilizada, o `last` si no hay ninguno. Con la comparación predeterminada y números ordenados de forma ascendente, ese elemento es el primer número mayor que `value`.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)std::upper_bound, declarado en <algorithm>, busca en el rango semiabierto [first, last). Con la comparación predeterminada y un rango ascendente, devuelve el primer elemento mayor que value, omitiendo todos los duplicados de ese valor. El resultado es un iterador, no un índice ni un indicador de pertenencia. Si no hay ningún elemento que cumpla la condición, incluso en un rango vacío, el resultado es last. Comprueba que el resultado no sea last antes de desreferenciarlo.
La sobrecarga que recibe comp busca el primer elemento e para el que comp(value, e) es verdadero. Como precondición, el rango debe estar particionado: primero deben ir todos los elementos que cumplen !comp(value, e) y, después, los restantes. Ordenar por completo según un orden compatible es suficiente, pero no hace falta para una sola consulta. No busques en datos arbitrariamente desordenados: incumplir la precondición provoca comportamiento indefinido. «Mayor» depende del comparador y no necesariamente del operador numérico >.
En un rango ascendente, std::lower_bound encuentra el primer elemento que no es menor que value, mientras que std::upper_bound encuentra el primer elemento mayor. En un rango ordenado, ambos límites delimitan los elementos equivalentes según la comparación. Fíjate en el orden de los argumentos: std::upper_bound usa comp(value, element), no comp(element, value).
Se requieren al menos iteradores forward. El número de comparaciones es O(log N), pero sin acceso aleatorio el número de pasos de iterador puede ser O(N); con iteradores de std::vector, es logarítmico. El ejemplo usa sintaxis compatible con C++23. El borrador de trabajo enlazado evoluciona y puede incluir declaraciones más recientes.
Ejemplos
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 2, 2, 2, 4, 7};
const auto it = std::upper_bound(values.begin(), values.end(), 2);
std::cout << "index=" << (it - values.begin()) << '\n';
if (it != values.end()) {
std::cout << "value=" << *it << '\n';
}
const auto end = std::upper_bound(values.begin(), values.end(), 7);
std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}
Resultado
index=4 value=4 at_end=true
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.