CKTIS / C++
Rango de búsqueda particionado
`std::lower_bound` no exige ordenar todo el rango: para la clave dada, los elementos que cumplen la condición deben aparecer antes que los que no la cumplen.
Versión: ISO C++23; implementation support may vary
Sintaxis
#include <algorithm>
std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);
// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges: bool(std::invoke(comp, std::invoke(proj, element), key))Un rango [first, last) está particionado respecto de la clave si bool(comp(element, key)) da primero solo true y después solo false. Cualquiera de los dos tramos puede estar vacío y ninguno tiene que estar ordenado internamente. El std::lower_bound clásico de <algorithm> devuelve el primer iterador en el que la condición es falsa, o last si no existe. El resultado no tiene por qué coincidir con la clave. Incumplir la precondición de partición provoca comportamiento indefinido.
La sobrecarga clásica con comparador solo compara en el sentido elemento–clave. Por tanto, admite una lambda [](const Sale& row, int key) que evalúa row.sales > key; [] no captura nada. std::ranges::lower_bound (desde C++20) acepta un par iterador–centinela o un rango. Su comparador debe satisfacer indirect_strict_weak_order para los elementos proyectados y la clave; &Sale::sales permite comparar enteros. Ambas versiones necesitan al menos iteradores de avance y hacen un número logarítmico de comparaciones, pero el número de pasos del iterador puede ser lineal sin acceso aleatorio. La sobrecarga de rango devuelve std::ranges::dangling para un rango temporal que no sea un borrowed_range. No desreferencies un iterador de fin ni uno invalidado.
std::nth_element y std::partial_sort requieren iteradores de acceso aleatorio y un orden débil estricto: comp(x, x) debe ser falso, y tanto la comparación como la equivalencia definida por dos comparaciones falsas deben ser transitivas. Para ventas representadas por enteros, a.sales > b.sales cumple esas condiciones; >= no. nth_element coloca el elemento del rango ordinal elegido en su posición de ordenación y separa ambos tramos sin garantizar que queden ordenados. partial_sort ordena el prefijo solicitado y deja el resto en un orden no especificado. Ninguno garantiza que todo el rango quede particionado para cualquier clave. Si vas a hacer búsquedas repetidas con claves distintas, ordena todo el rango con el mismo criterio.
Ejemplos
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
struct Sale {
int sales;
};
int main() {
const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
const int key = 90;
const auto before_key = [](const Sale& row, int key) {
return row.sales > key;
};
const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);
if (classic != rows.end() && ranged != rows.end()) {
std::cout << classic->sales << '\n' << ranged->sales << '\n';
}
}Resultado
70 70
Para `90`, ambas llamadas imprimen `70`, el primer valor que no supera el umbral, aunque el rango no está ordenado de mayor a menor. Para `100`, `95` da `false` antes de que `120` dé `true`, así que ninguna llamada es válida con `100` en este rango.
Lecciones relacionadas
- C++ · Lección 23 · Avanzado · Versión: 3