Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

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.

Fuentes