CKTIS / C++
Ordenación, comparaciones y rangos de búsqueda
Una ordenación correcta requiere un comparador que defina un orden débil estricto. La búsqueda binaria requiere un rango particionado según la condición pertinente; ordenar todo el rango es suficiente, pero no siempre necesario.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort de <algorithm> ordena el rango semiabierto [first, last) según comp: ningún elemento posterior precede a uno anterior. Requiere iteradores de acceso aleatorio y elementos que cumplan los requisitos de movimiento e intercambio. Realiza O(N log N) comparaciones. No garantiza conservar el orden de los elementos equivalentes; para ello se usa std::stable_sort.
El comparador debe definir un orden débil estricto. comp(a, b) significa que a precede a b, y comp(a, a) debe ser falso. La relación debe ser transitiva. La equivalencia definida por !comp(a, b) && !comp(b, a) también debe ser transitiva y no tiene por qué coincidir con operator==. No uses <=: incumple el requisito para argumentos idénticos. Si no se cumplen los requisitos del comparador, dejan de aplicarse las garantías del algoritmo.
El orden débil estricto y la partición de los rangos de búsqueda son requisitos relacionados, pero distintos. En un rango particionado según un predicado, primero aparecen todos los elementos cuyo resultado es true y después los que dan false; cualquiera de las partes puede estar vacía. Para std::lower_bound(first, last, value, comp), el predicado es comp(e, value). La función devuelve la frontera: el primer elemento cuyo resultado es false, o last. Esto no demuestra que el valor buscado esté presente; no desreferencies last.
Ordenar con el mismo orden garantiza esta partición para cualquier clave. Para una sola clave basta con particionar: [2, 1, 4, 3] cumple la precondición de std::lower_bound para value = 3 y la comparación <, aunque no está ordenado. Otras funciones de búsqueda binaria tienen sus propios requisitos de partición. std::lower_bound realiza O(log N) comparaciones, pero sin iteradores de acceso aleatorio puede necesitar un número lineal de pasos de iterador.
El ejemplo ordena enteros y luego reutiliza el mismo comp para obtener el índice 3. El contenido tiene como objetivo C++23; la referencia proporcionada apunta a un borrador de trabajo en evolución, no a una publicación definitiva de C++23. No está acreditada la compatibilidad del compilador ni del entorno de ejecución de producción.
Ejemplos
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 3, 1, 2};
const auto comp = [](int a, int b) { return a < b; };
std::sort(values.begin(), values.end(), comp);
for (std::size_t i = 0; i < values.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
std::cout << "index=" << (it - values.begin()) << '\n';
}
Resultado
1 1 2 3 4 index=3
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.