Ordenar y buscar en C++: sort, ranges, lower_bound y find_if

Ordenar y buscar en C++ con la biblioteca estándar: std::sort y std::ranges::sort para números y estructuras, por varios campos y con proyecciones, stable_sort cuando importa el orden previo, el error de la comparación que no es un orden, y las búsquedas con binary_search, lower_bound y find_if.

También te puede interesar

Ordenar un vector con std::sort y std::ranges::sort

std::sort, de <algorithm>, ordena de menor a mayor cualquier rango con acceso aleatorio, como un std::vector, un std::array o un array normal. Desde C++20 existe además std::ranges::sort, que recibe el contenedor entero en lugar de dos iteradores:

#include <algorithm>
#include <functional>
#include <print>
#include <vector>

int main()
{
    std::vector<int> v{42, 7, 19, 3, 25, 7, 11};

    std::sort(v.begin(), v.end());                 // de menor a mayor
    std::println("ascendente:  {}", v);

    std::sort(v.begin(), v.end(), std::greater{}); // de mayor a menor
    std::println("descendente: {}", v);

    std::ranges::sort(v);                          // C++20: el contenedor entero
    std::println("con ranges:  {}", v);

    std::vector<int> w{5, 1, 4};
    std::println("¿está ordenado? {} y {}", std::ranges::is_sorted(v), std::ranges::is_sorted(w));
}
salidaascendente:  [3, 7, 7, 11, 19, 25, 42]
descendente: [42, 25, 19, 11, 7, 7, 3]
con ranges:  [3, 7, 7, 11, 19, 25, 42]
¿está ordenado? true y false

std::println sabe imprimir un vector entero desde C++23, con corchetes y comas. El tercer argumento de std::sort es la comparación: una función o un objeto que recibe dos elementos y devuelve true si el primero debe ir antes que el segundo. std::greater{} invierte el orden. std::sort tarda del orden de n log n comparaciones, así que ordenar un millón de números es cuestión de milisegundos.

Ordenar estructuras: lambdas y proyecciones

Para ordenar objetos hay que decir por qué campo. La forma clásica es una lambda que compara; la de C++20, una proyección: se le dice a std::ranges::sort qué campo mirar y él compara ese campo con <.

#include <algorithm>
#include <print>
#include <string>
#include <tuple>
#include <vector>

struct Persona {
    std::string nombre;
    int edad;
};

void mostrar(const char* titulo, const std::vector<Persona>& gente)
{
    std::print("{:<22}", titulo);
    for (const auto& p : gente) std::print(" {}({})", p.nombre, p.edad);
    std::println("");
}

int main()
{
    std::vector<Persona> gente{{"Lucía", 34}, {"Mario", 28}, {"Ana", 34}, {"Bruno", 28}, {"Eva", 41}};

    // 1. Lambda: por edad
    std::ranges::sort(gente, [](const Persona& a, const Persona& b) { return a.edad < b.edad; });
    mostrar("por edad (lambda):", gente);

    // 2. Proyección: por nombre
    std::ranges::sort(gente, {}, &Persona::nombre);
    mostrar("por nombre:", gente);

    // 3. Varios campos: edad descendente y, a igual edad, nombre
    std::ranges::sort(gente, [](const Persona& a, const Persona& b) {
        return std::tie(b.edad, a.nombre) < std::tie(a.edad, b.nombre);
    });
    mostrar("edad desc. y nombre:", gente);
}
salidapor edad (lambda):     Mario(28) Bruno(28) Lucía(34) Ana(34) Eva(41)
por nombre:            Ana(34) Bruno(28) Eva(41) Lucía(34) Mario(28)
edad desc. y nombre:   Eva(41) Ana(34) Lucía(34) Bruno(28) Mario(28)

En la proyección, el {} del segundo argumento es la comparación por omisión (std::ranges::less). Para ordenar por varios campos, std::tie crea tuplas de referencias que se comparan campo a campo, como un diccionario: primero la edad y, si empata, el nombre. Cambiar a por b en un campo invierte el orden solo de ese campo.

Ordenar sin perder el orden previo: stable_sort

std::sort no promete nada sobre los elementos que son iguales según la comparación: pueden quedar en cualquier orden. Cuando ese orden importa, por ejemplo al ordenar por un segundo criterio una lista que ya estaba ordenada por el primero, se usa std::stable_sort:

#include <algorithm>
#include <print>
#include <string>
#include <vector>

struct Pedido {
    int numero;
    std::string estado;
};

int main()
{
    // Ya están ordenados por número de pedido
    std::vector<Pedido> pedidos{{101, "enviado"}, {102, "pendiente"}, {103, "enviado"},
                                {104, "pendiente"}, {105, "enviado"}, {106, "pendiente"}};

    std::ranges::stable_sort(pedidos, {}, &Pedido::estado);

    for (const auto& p : pedidos) std::println("{:<10} {}", p.estado, p.numero);
}
salidaenviado    101
enviado    103
enviado    105
pendiente  102
pendiente  104
pendiente  106

Dentro de cada estado, los pedidos siguen en orden de número: 101, 103 y 105, y luego 102, 104 y 106. Con std::sort ese orden interno no está garantizado. A cambio, std::stable_sort puede necesitar memoria extra y ser algo más lento.

El error típico: una comparación que no es un orden

La comparación tiene que ser un orden estricto débil. En la práctica: comp(a, a) debe ser false, y si comp(a, b) es true, comp(b, a) debe ser false. El fallo más común es usar <= en lugar de <. Con eso, el programa tiene comportamiento indefinido: puede funcionar en las pruebas, ordenar mal o, con muchos elementos iguales, leer fuera del vector. El modo de depuración de libstdc++, que se activa con -D_GLIBCXX_DEBUG, lo comprueba:

#include <algorithm>
#include <print>
#include <vector>

int main()
{
    std::vector<int> v{3, 1, 2, 3, 1, 2, 3, 1, 2};

    // MAL: <= no es un orden estricto (dice que 3 va antes que 3)
    std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });

    std::println("{}", v);
}
salida con error/usr/local/include/c++/15.3.0/bits/stl_algo.h:4872:
In function:
…
Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

El programa se detiene en lugar de seguir con datos corruptos. La solución es cambiar a <= b por a < b. -D_GLIBCXX_DEBUG hace el programa bastante más lento, así que es para las pruebas; en producción, una opción más ligera es -D_GLIBCXX_ASSERTIONS, que comprueba los accesos fuera de rango pero no esto.

Buscar en un vector ordenado: binary_search, lower_bound y equal_range

Si el vector está ordenado, buscar es mucho más rápido: la búsqueda binaria mira el elemento del medio y descarta la mitad en cada paso, así que en un millón de elementos tarda unas 20 comparaciones. La biblioteca tiene cuatro funciones para eso:

Un vector ordenado 1, 3, 5, 5, 5, 8, 9. lower_bound del 5 señala la posición 2, el primer 5; upper_bound señala la posición 5, el primer elemento mayor que 5. Entre ambas están los tres cincoslower_bound y upper_bound buscando el 5 en un vector ordenado1[0]3[1]5[2]5[3]5[4]8[5]9[6]lower_bound: primer 5upper_bound: el primero > 5equal_range devuelve las dos cotas: entre ellas están todos los 5

lower_bound señala el primer elemento que no es menor que el buscado y upper_bound el primero que es mayor; entre las dos quedan todos los iguales. Esquema: decodigo.com.
#include <algorithm>
#include <print>
#include <vector>

int main()
{
    std::vector<int> v{1, 3, 5, 5, 5, 8, 9};     // tiene que estar ordenado

    std::println("¿hay un 5? {}   ¿hay un 4? {}", std::ranges::binary_search(v, 5),
                 std::ranges::binary_search(v, 4));

    auto primero = std::ranges::lower_bound(v, 5);  // primer elemento >= 5
    auto despues = std::ranges::upper_bound(v, 5);  // primer elemento > 5
    std::println("los 5 van de la posición {} a la {}: hay {}", primero - v.begin(),
                 despues - v.begin(), despues - primero);

    auto [ini, fin] = std::ranges::equal_range(v, 5);
    std::println("equal_range dice lo mismo: {} elementos", fin - ini);

    // Dónde insertar el 6 para que siga ordenado
    auto sitio = std::ranges::lower_bound(v, 6);
    v.insert(sitio, 6);
    std::println("con el 6: {}", v);

    // Un valor que no está: lower_bound señala dónde iría
    auto it = std::ranges::lower_bound(v, 4);
    std::println("el 4 iría en la posición {}, delante del {}", it - v.begin(), *it);
}
salida¿hay un 5? true   ¿hay un 4? false
los 5 van de la posición 2 a la 5: hay 3
equal_range dice lo mismo: 3 elementos
con el 6: [1, 3, 5, 5, 5, 6, 8, 9]
el 4 iría en la posición 2, delante del 5

binary_search solo dice si está; para saber dónde hay que usar lower_bound. Ojo: si el vector no está ordenado con la misma comparación, todas estas funciones dan resultados sin sentido, y no avisan.

Buscar en un vector sin ordenar: find y find_if

Si los datos no están ordenados, o se busca por una condición en lugar de un valor exacto, se recorre el vector con std::ranges::find o find_if, que devuelven un iterador al primer elemento que encaja, o end() si no hay ninguno:

#include <algorithm>
#include <print>
#include <string>
#include <vector>

struct Producto {
    std::string nombre;
    double precio;
    int stock;
};

int main()
{
    std::vector<Producto> tienda{{"teclado", 24.90, 12}, {"ratón", 15.50, 0},
                                 {"monitor", 189.00, 3}, {"cable", 4.99, 0}};

    // Por un campo exacto, con proyección
    auto it = std::ranges::find(tienda, "monitor", &Producto::nombre);
    if (it != tienda.end())
        std::println("{} cuesta ${:.2f}", it->nombre, it->precio);

    // Por una condición
    auto agotado = std::ranges::find_if(tienda, [](const Producto& p) { return p.stock == 0; });
    if (agotado != tienda.end())
        std::println("primer producto agotado: {}", agotado->nombre);

    // Cuántos cumplen la condición, y si alguno o todos la cumplen
    auto n = std::ranges::count_if(tienda, [](const Producto& p) { return p.stock == 0; });
    bool caro = std::ranges::any_of(tienda, [](const Producto& p) { return p.precio > 100; });
    std::println("agotados: {}  ¿alguno de más de $100? {}", n, caro);

    // Un valor que no está
    if (std::ranges::find(tienda, "altavoz", &Producto::nombre) == tienda.end())
        std::println("no hay altavoces");
}
salidamonitor cuesta $189.00
primer producto agotado: ratón
agotados: 2  ¿alguno de más de $100? true
no hay altavoces

Comprobar siempre el resultado contra end() antes de usarlo es obligatorio: *tienda.end() es comportamiento indefinido, el mismo tipo de error que leer fuera de un array.

Qué usar en cada caso

  • NecesitasUsaCoste
  • Ordenar sin importar el orden de los igualesstd::ranges::sortn log n
  • Ordenar respetando el orden previo de los igualesstd::ranges::stable_sortn log n (más memoria)
  • Solo los k primeros, ordenadosstd::ranges::partial_sortn log k
  • El elemento que iría en la posición k (la mediana, por ejemplo)std::ranges::nth_elementn de media
  • Saber si un valor está, en datos ordenadosstd::ranges::binary_searchlog n
  • Dónde está o dónde iría, en datos ordenadoslower_bound, upper_bound, equal_rangelog n
  • Buscar en datos sin ordenar o por una condiciónstd::ranges::find, find_ifn
  • Muchas búsquedas por clave, sin ordenstd::unordered_map o std::unordered_set1 de media

Si vas a buscar muchas veces en los mismos datos, compensa ordenarlos una vez y usar búsqueda binaria, o guardarlos directamente en un std::set, un std::map o sus versiones unordered. Un ejemplo completo con mapas está en Contar palabras en C++.

Todo el código de esta página se compiló con GCC 15.3 (C++23, -std=c++23 -Wall -Wextra, sin avisos) y se ejecutó en Linux, en un contenedor limpio sin acceso a la red, antes de publicarla; las salidas están copiadas de esa ejecución.

decodigo.com

Código listo para usar: ejemplos en Java, Python, Go, Rust y JavaScript, cursos, guías, herramientas en línea y noticias de tecnología.