La Biblioteca de Plantillas Estándar (STL) de C++ ofrece un conjunto robusto de algoritmos genéricos que operan sobre rangos de elementos definidos por iteradores. Estos algoritmos son herramientas fundamentales para manipular colecciones de datos de manera eficiente y expresiva. Se categorizan principalmente en algoritmos que no modifican la secuencia, aquellos que sí lo hacen, y otros para ordenación, operaciones numéricas, y más.

1. Algoritmos de Secuencia No Modificadores

Estos algoritmos examinan los elementos en un rango sin alterar su contenido.

1.1. Búsqueda: find, find_if, find_end

• std::find(inicio, fin, valor): Busca la primera aparición de valor. Retorna un iterador al elemento encontrado o fin si no se encuentra.
• std::find_if(inicio, fin, predicado): Busca el primer elemento que satisface el predicado (una función o lambda).
• std::find_end(inicio, fin, sub_inicio, sub_fin): Encuentra la última ocurrencia de una sub-secuencia dentro de un rango.

#include <iostream>
#include <vector>
#include <algorithm> // Para find, find_if, find_end

int main() {
    std::vector<int> numeros = {10, 25, 40, 55, 70, 85};

    // Buscar el valor 40
    auto it_cuarenta = std::find(numeros.begin(), numeros.end(), 40);
    if (it_cuarenta != numeros.end()) {
        std::cout << "Valor encontrado: " << *it_cuarenta << std::endl; // Salida: 40
    }

    // Buscar el primer número mayor que 60
    auto it_mayor_sesenta = std::find_if(numeros.begin(), numeros.end(), [](int n) {
        return n > 60;
    });
    if (it_mayor_sesenta != numeros.end()) {
        std::cout << "Primer valor > 60: " << *it_mayor_sesenta << std::endl; // Salida: 70
    }

    // Buscar una sub-secuencia {55, 70}
    std::vector<int> sub_sec = {55, 70};
    auto it_sub = std::find_end(numeros.begin(), numeros.end(), sub_sec.begin(), sub_sec.end());
    if (it_sub != numeros.end()) {
        std::cout << "Sub-secuencia comienza en el índice: " << (it_sub - numeros.begin()) << std::endl; // Salida: 3
    }
    return 0;
}

1.2. Conteo: count, count_if

• std::count(inicio, fin, valor): Cuenta las veces que valor aparece en el rango.
• std::count_if(inicio, fin, predicado): Cuenta los elementos que satisfacen el predicado.

#include <iostream>
#include <vector>
#include <algorithm> // Para count, count_if

int main() {
    std::vector<int> datos = {1, 2, 5, 2, 8, 2, 5};
    
    // Contar cuántas veces aparece el número 2
    int conteo_dos = std::count(datos.begin(), datos.end(), 2); 
    std::cout << "Cantidad de '2': " << conteo_dos << std::endl; // Salida: 3

    // Contar cuántos números son mayores que 4
    int conteo_mayor_cuatro = std::count_if(datos.begin(), datos.end(), [](int x) { 
        return x > 4; 
    }); 
    std::cout << "Cantidad de números > 4: " << conteo_mayor_cuatro << std::endl; // Salida: 3 (5, 8, 5)
    return 0;
}

1.3. for_each

Aplica una función o un objeto función a cada elemento en un rango.

#include <iostream>
#include <vector>
#include <algorithm> // Para for_each

int main() {
    std::vector<std::string> palabras = {"hola", "mundo", "c++"};
    std::cout << "Elementos: ";
    std::for_each(palabras.begin(), palabras.end(), [](const std::string& s) { 
        std::cout << s << " "; // Imprime cada palabra
    });
    std::cout << std::endl; // Salida: Elementos: hola mundo c++ 
    return 0;
}

1.4. Comparación de Rangos: equal y mismatch

• std::equal(b1, e1, b2): Comprueba si dos rangos son idénticos elemento a elemento.
• std::mismatch(b1, e1, b2): Retorna un std::pair de iteradores al primer par de elementos desiguales.

#include <iostream>
#include <vector>
#include <algorithm> // Para equal, mismatch

int main() {
    std::vector<int> seq1 = {10, 20, 30, 40};
    std::vector<int> seq2 = {10, 20, 30, 50};
    std::vector<int> seq3 = {10, 20, 30};

    // ¿seq1 y seq2 son iguales en sus primeros 3 elementos?
    bool son_iguales_parcial = std::equal(seq1.begin(), seq1.begin() + 3, seq2.begin());
    std::cout << "seq1 y seq2 son parcialmente iguales? " << std::boolalpha << son_iguales_parcial << std::endl; // Salida: true

    // ¿seq1 y seq3 son completamente iguales?
    bool son_iguales_completos = std::equal(seq1.begin(), seq1.begin() + seq3.size(), seq3.begin());
    std::cout << "seq1 y seq3 son completamente iguales? " << std::boolalpha << son_iguales_completos << std::endl; // Salida: true

    // Encontrar la primera diferencia entre seq1 y seq2
    auto diferen_par = std::mismatch(seq1.begin(), seq1.end(), seq2.begin());
    if (diferen_par.first != seq1.end()) {
        std::cout << "Primera diferencia: " << *diferen_par.first << " vs " << *diferen_par.second << std::endl; // Salida: 40 vs 50
    }
    return 0;
}

1.5. Predicados de Rango: all_of, any_of, none_of (C++11)

Verifican si todos, alguno o ninguno de los elementos en un rango cumplen una condición.

#include <iostream>
#include <vector>
#include <algorithm> // Para all_of, any_of, none_of

int main() {
    std::vector<int> valores = {10, 20, 30, 40};
    
    // ¿Todos los valores son múltiplos de 10?
    bool todos_mult_diez = std::all_of(valores.begin(), valores.end(), [](int x) { 
        return x % 10 == 0; 
    }); 
    std::cout << "Todos múltiplos de 10? " << std::boolalpha << todos_mult_diez << std::endl; // Salida: true

    // ¿Alguno de los valores es impar?
    bool alguno_impar = std::any_of(valores.begin(), valores.end(), [](int x) { 
        return x % 2 != 0; 
    }); 
    std::cout << "Alguno impar? " << std::boolalpha << alguno_impar << std::endl; // Salida: false

    // ¿Ninguno de los valores es menor que 5?
    bool ninguno_menor_cinco = std::none_of(valores.begin(), valores.end(), [](int x) { 
        return x < 5; 
    }); 
    std::cout << "Ninguno < 5? " << std::boolalpha << ninguno_menor_cinco << std::endl; // Salida: true
    return 0;
}

2. Algoritmos de Secuencia Modificadores

Estos algoritmos alteran el contenido de los elementos o su orden dentro del rango.

2.1. Copia: copy y copy_if

• std::copy(inicio, fin, destino): Copia elementos de un rango a otro. El rango de destino debe tener espacio suficiente.
• std::copy_if(inicio, fin, destino, predicado): Copia solo los elementos que satisfacen el predicado.

#include <iostream>
#include <vector>
#include <algorithm> // Para copy, copy_if
#include <iterator>  // Para back_inserter

int main() {
    std::vector<int> fuente = {100, 200, 300, 400, 500};
    std::vector<int> destino_todos(fuente.size()); // El destino debe tener tamaño adecuado

    // Copiar todos los elementos
    std::copy(fuente.begin(), fuente.end(), destino_todos.begin());
    std::cout << "Destino todos: ";
    for (int x : destino_todos) std::cout << x << " "; // Salida: 100 200 300 400 500

    // Copiar solo elementos mayores a 250 a un nuevo vector
    std::vector<int> destino_filtrado;
    std::copy_if(fuente.begin(), fuente.end(), std::back_inserter(destino_filtrado), [](int val) {
        return val > 250;
    });
    std::cout << "\nDestino filtrado (>250): ";
    for (int x : destino_filtrado) std::cout << x << " "; // Salida: 300 400 500
    std::cout << std::endl;
    return 0;
}

2.2. Transformación: transform

Aplica una función a cada elemento en un rango y guarda el resultado en otro rango.

#include <iostream>
#include <vector>
#include <algorithm> // Para transform
#include <numeric>   // Para std::plus

int main() {
    std::vector<int> valores_originales = {1, 2, 3, 4};
    std::vector<int> valores_duplicados(valores_originales.size());

    // Multiplicar cada elemento por 2
    std::transform(valores_originales.begin(), valores_originales.end(), valores_duplicados.begin(), [](int x) {
        return x * 2;
    });
    std::cout << "Valores duplicados: ";
    for (int x : valores_duplicados) std::cout << x << " "; // Salida: 2 4 6 8

    // Sumar elementos de dos vectores
    std::vector<int> v_a = {10, 20, 30};
    std::vector<int> v_b = {1, 2, 3};
    std::vector<int> v_suma(v_a.size());
    std::transform(v_a.begin(), v_a.end(), v_b.begin(), v_suma.begin(), std::plus<int>());
    std::cout << "\nSuma de vectores: ";
    for (int x : v_suma) std::cout << x << " "; // Salida: 11 22 33
    std::cout << std::endl;
    return 0;
}

2.3. Reemplazo: replace, replace_if, replace_copy

• std::replace(inicio, fin, valor_antiguo, valor_nuevo): Reemplaza todas las ocurrencias de valor_antiguo por valor_nuevo.
• std::replace_if(inicio, fin, predicado, valor_nuevo): Reemplaza elementos que cumplen el predicado.
• std::replace_copy(inicio, fin, destino, valor_antiguo, valor_nuevo): Copia el rango a destino reemplazando elementos, sin modificar el original.

#include <iostream>
#include <vector>
#include <algorithm> // Para replace, replace_if, replace_copy
#include <iterator>  // Para back_inserter

int main() {
    std::vector<char> letras = {'a', 'b', 'c', 'b', 'd', 'e'};

    // Reemplazar todas las 'b' por 'X'
    std::replace(letras.begin(), letras.end(), 'b', 'X');
    std::cout << "Después de replace('b', 'X'): ";
    for (char c : letras) std::cout << c << " "; // Salida: a X c X d e

    // Reemplazar vocales (minúsculas) por '*'
    std::replace_if(letras.begin(), letras.end(), [](char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }, '*');
    std::cout << "\nDespués de replace_if(vocal, '*'): ";
    for (char c : letras) std::cout << c << " "; // Salida: * X c X d *

    // Copiar y reemplazar 'X' por 'Y' sin modificar el original
    std::vector<char> copia_reemplazada;
    std::replace_copy(letras.begin(), letras.end(), std::back_inserter(copia_reemplazada), 'X', 'Y');
    std::cout << "\nCopia con 'X' reemplazadas por 'Y': ";
    for (char c : copia_reemplazada) std::cout << c << " "; // Salida: * Y c Y d *
    std::cout << std::endl;
    return 0;
}

2.4. Eliminación Lógica y Física: remove, remove_if y erase

• std::remove(inicio, fin, valor): "Mueve" los elementos iguales a valor al final del rango, retornando un iterador al nuevo final lógico. No cambia el tamaño del contenedor.
• std::remove_if(inicio, fin, predicado): Similar a remove, pero para elementos que satisfacen un predicado.

Para la eliminación física (cambiar el tamaño del contenedor), estos algoritmos se usan junto con el método erase del contenedor.

#include <iostream>
#include <vector>
#include <algorithm> // Para remove, remove_if

int main() {
    std::vector<int> mi_vector = {1, 7, 2, 7, 3, 7, 4};

    // Eliminar lógicamente todos los '7'
    auto nuevo_fin = std::remove(mi_vector.begin(), mi_vector.end(), 7);
    // En este punto, mi_vector podría ser {1, 2, 3, 4, 7, 7, 7} pero los últimos '7' no son accesibles
    std::cout << "Después de remove (lógico): ";
    for (int x : mi_vector) std::cout << x << " "; // Salida: 1 2 3 4 7 7 7 (elementos basura o antiguos)

    // Eliminar físicamente los elementos extra
    mi_vector.erase(nuevo_fin, mi_vector.end());
    std::cout << "\nDespués de erase (físico): ";
    for (int x : mi_vector) std::cout << x << " "; // Salida: 1 2 3 4

    // Eliminar lógicamente y físicamente los números pares
    mi_vector = {10, 11, 12, 13, 14, 15};
    mi_vector.erase(std::remove_if(mi_vector.begin(), mi_vector.end(), [](int n) {
        return n % 2 == 0; // Es par
    }), mi_vector.end());
    std::cout << "\nDespués de eliminar pares: ";
    for (int x : mi_vector) std::cout << x << " "; // Salida: 11 13 15
    std::cout << std::endl;
    return 0;
}

2.5. Elementos Únicos: unique

Elimina elementos consecutivos duplicados de un rango, moviendo los elementos únicos al principio. Retorna un iterador al nuevo final lógico. Requiere el uso de erase para la eliminación física.

#include <iostream>
#include <vector>
#include <algorithm> // Para unique

int main() {
    std::vector<int> datos_duplicados = {1, 1, 1, 2, 2, 3, 4, 4, 5, 5, 5};
    std::cout << "Original: ";
    for (int x : datos_duplicados) std::cout << x << " "; // Salida: 1 1 1 2 2 3 4 4 5 5 5

    auto ultimo_elemento_unico = std::unique(datos_duplicados.begin(), datos_duplicados.end());
    // datos_duplicados podría ser {1, 2, 3, 4, 5, 4, 4, 5, 5, 5}
    // donde los elementos a partir de ultimo_elemento_unico no son relevantes

    datos_duplicados.erase(ultimo_elemento_unico, datos_duplicados.end());
    std::cout << "\nDespués de unique + erase: ";
    for (int x : datos_duplicados) std::cout << x << " "; // Salida: 1 2 3 4 5
    std::cout << std::endl;
    return 0;
}

2.6. Inversión: reverse

Invierte el orden de los elementos en un rango.

#include <iostream>
#include <vector>
#include <algorithm> // Para reverse

int main() {
    std::vector<char> palabra = {'S', 'T', 'L', ' ', 'C', '+'};
    std::cout << "Original: ";
    for (char c : palabra) std::cout << c; // Salida: STL C+

    std::reverse(palabra.begin(), palabra.end());
    std::cout << "\nInvertida: ";
    for (char c : palabra) std::cout << c; // Salida: +C LTS
    std::cout << std::endl;
    return 0;
}

2.7. Rotación: rotate

Rota los elementos en un rango, moviendo el elemento en la posición especificada al inicio.

#include <iostream>
#include <vector>
#include <algorithm> // Para rotate

int main() {
    std::vector<int> elementos = {10, 20, 30, 40, 50};
    std::cout << "Original: ";
    for (int x : elementos) std::cout << x << " "; // Salida: 10 20 30 40 50

    // Rotar para que '30' (índice 2) sea el nuevo primer elemento
    std::rotate(elementos.begin(), elementos.begin() + 2, elementos.end());
    std::cout << "\nRotado (pivot 30): ";
    for (int x : elementos) std::cout << x << " "; // Salida: 30 40 50 10 20
    std::cout << std::endl;
    return 0;
}

2.8. Aleatorización: shuffle (C++11)

Reordena aleatoriamente los elementos en un rango utilizando un generador de números aleatorios.

#include <iostream>
#include <vector>
#include <algorithm> // Para shuffle
#include <random>    // Para random_device, mt19937
#include <chrono>    // Para system_clock

int main() {
    std::vector<int> baraja = {1, 2, 3, 4, 5, 6, 7};
    std::cout << "Baraja original: ";
    for (int x : baraja) std::cout << x << " ";

    // Usar un generador de números aleatorios para mezclar
    unsigned semilla = std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 g(semilla);
    
    std::shuffle(baraja.begin(), baraja.end(), g);
    std::cout << "\nBaraja mezclada: ";
    for (int x : baraja) std::cout << x << " "; // Salida: Orden aleatorio, e.g., 5 2 7 1 4 3 6
    std::cout << std::endl;
    return 0;
}

3. Algoritmos de Ordenación y Relacionados

Estos algoritmos organizan los elementos en un orden específico.

3.1. Ordenación: sort, stable_sort, partial_sort

• std::sort(inicio, fin, comparador_opcional): Ordena los elementos. Es generalmente inestable y de complejidad O(N log N).
• std::stable_sort(inicio, fin, comparador_opcional): Ordena los elementos manteniendo el orden relativo de elementos equivalentes. Es estable y de complejidad O(N log N).
• std::partial_sort(inicio, medio, fin, comparador_opcional): Ordena los primeros medio - inicio elementos del rango, que serán los más pequeños (o más grandes si se usa un comparador) del rango completo.

#include <iostream>
#include <vector>
#include <algorithm> // Para sort, stable_sort, partial_sort
#include <functional> // Para std::greater

int main() {
    std::vector<int> desordenados = {8, 1, 4, 2, 7, 3};
    std::cout << "Original: ";
    for (int x : desordenados) std::cout << x << " "; // Salida: 8 1 4 2 7 3

    std::sort(desordenados.begin(), desordenados.end()); // Orden ascendente por defecto
    std::cout << "\nOrdenado (ascendente): ";
    for (int x : desordenados) std::cout << x << " "; // Salida: 1 2 3 4 7 8

    std::sort(desordenados.begin(), desordenados.end(), std::greater<int>()); // Orden descendente
    std::cout << "\nOrdenado (descendente): ";
    for (int x : desordenados) std::cout << x << " "; // Salida: 8 7 4 3 2 1

    // Demostración de stable_sort con pares
    std::vector<std::pair<int, char>> items = {{1, 'c'}, {2, 'a'}, {1, 'b'}, {3, 'd'}, {2, 'e'}};
    std::stable_sort(items.begin(), items.end(), [](const auto& p1, const auto& p2) {
        return p1.first < p2.first; // Ordenar por el primer elemento
    });
    std::cout << "\nStable sort: ";
    for (const auto& p : items) std::cout << "(" << p.first << "," << p.second << ") "; 
    // Salida: (1,c) (1,b) (2,a) (2,e) (3,d) - Notar que 'c' sigue a 'b' para el valor 1, y 'a' a 'e' para el valor 2. (Originalmente 'a' venia antes de 'e')

    std::vector<int> datos_parciales = {9, 2, 5, 1, 8, 3, 7};
    // Queremos los 3 elementos más pequeños ordenados al principio
    std::partial_sort(datos_parciales.begin(), datos_parciales.begin() + 3, datos_parciales.end());
    std::cout << "\nPartial sort (primeros 3): ";
    for (int x : datos_parciales) std::cout << x << " "; // Salida: 1 2 3 9 8 5 7 (los primeros 3 están ordenados, el resto no)
    std::cout << std::endl;
    return 0;
}

3.2. Búsqueda de n-ésimo Elemento: nth_element

Reorganiza el rango de manera que el elemento en la posición n (especificada por un iterador) sea el mismo que estaría allí si el rango estuviera completamente ordenado. Todos los elementos a su izquierda serán menores o iguales, y todos a su derecha serán mayores o iguales.

#include <iostream>
#include <vector>
#include <algorithm> // Para nth_element

int main() {
    std::vector<int> numeros_random = {50, 10, 80, 20, 60, 30, 70, 40};
    
    // Encontrar el elemento que estaría en la posición del 4º (índice 3) si estuviera ordenado
    std::nth_element(numeros_random.begin(), numeros_random.begin() + 3, numeros_random.end());
    
    std::cout << "Después de nth_element (índice 3): ";
    for (int x : numeros_random) std::cout << x << " "; 
    // Salida (ejemplo, el orden de los demás varía): 30 10 20 40 60 50 70 80. El elemento en índice 3 es 40.
    std::cout << "\nEl elemento en la posición del 4º (índice 3) es: " << numeros_random[3] << std::endl; // Salida: 40
    return 0;
}

3.3. Búsqueda Binaria: binary_search, lower_bound, upper_bound

Requieren que el rango esté ordenado.

• std::binary_search(inicio, fin, valor): Comprueba si valor existe en el rango (retorna bool).
• std::lower_bound(inicio, fin, valor): Retorna un iterador al primer elemento que no es menor que valor.
• std::upper_bound(inicio, fin, valor): Retorna un iterador al primer elemento que es mayor que valor.

#include <iostream>
#include <vector>
#include <algorithm> // Para binary_search, lower_bound, upper_bound

int main() {
    std::vector<int> datos_ordenados = {10, 20, 30, 30, 40, 50}; // Debe estar ordenado

    // ¿Existe el 30?
    bool existe_treinta = std::binary_search(datos_ordenados.begin(), datos_ordenados.end(), 30);
    std::cout << "El 30 existe? " << std::boolalpha << existe_treinta << std::endl; // Salida: true

    // Encontrar el primer elemento >= 30
    auto it_lb = std::lower_bound(datos_ordenados.begin(), datos_ordenados.end(), 30);
    std::cout << "lower_bound para 30 en índice: " << (it_lb - datos_ordenados.begin()) << std::endl; // Salida: 2

    // Encontrar el primer elemento > 30
    auto it_ub = std::upper_bound(datos_ordenados.begin(), datos_ordenados.end(), 30);
    std::cout << "upper_bound para 30 en índice: " << (it_ub - datos_ordenados.begin()) << std::endl; // Salida: 4
    return 0;
}

3.4. Fusión: merge

Combina dos rangos ordenados en un tercer rango también ordenado. Los rangos de entrada deben estar ordenados.

#include <iostream>
#include <vector>
#include <algorithm> // Para merge

int main() {
    std::vector<int> lista1 = {1, 5, 9};
    std::vector<int> lista2 = {2, 4, 8};
    std::vector<int> lista_fusionada(lista1.size() + lista2.size());

    std::merge(lista1.begin(), lista1.end(), lista2.begin(), lista2.end(), lista_fusionada.begin());
    std::cout << "Lista fusionada: ";
    for (int x : lista_fusionada) std::cout << x << " "; // Salida: 1 2 4 5 8 9
    std::cout << std::endl;
    return 0;
}

4. Algoritmos de Montón (Heap Algorithms)

Estos algoritmos tratan un rango como una estructura de datos de montón (heap), típicamente un max-heap.

#include <iostream>
#include <vector>
#include <algorithm> // Para make_heap, push_heap, pop_heap, sort_heap

int main() {
    std::vector<int> datos_monticulo = {7, 1, 9, 3, 5, 2};
    std::cout << "Original: ";
    for (int x : datos_monticulo) std::cout << x << " ";

    std::make_heap(datos_monticulo.begin(), datos_monticulo.end()); // Crea un max-heap
    std::cout << "\nDespués de make_heap: ";
    for (int x : datos_monticulo) std::cout << x << " "; // Salida (ejemplo): 9 7 5 3 1 2

    datos_monticulo.push_back(10); // Agrega un elemento al final
    std::push_heap(datos_monticulo.begin(), datos_monticulo.end()); // Restaura la propiedad de heap
    std::cout << "\nDespués de push_back(10) y push_heap: ";
    for (int x : datos_monticulo) std::cout << x << " "; // Salida (ejemplo): 10 7 9 3 1 2 5

    std::pop_heap(datos_monticulo.begin(), datos_monticulo.end()); // Mueve el elemento más grande al final
    int elemento_maximo = datos_monticulo.back(); // El elemento más grande ahora está al final
    datos_monticulo.pop_back(); // Elimina el elemento más grande
    std::cout << "\nDespués de pop_heap y pop_back (maximo=" << elemento_maximo << "): ";
    for (int x : datos_monticulo) std::cout << x << " "; // Salida (ejemplo): 9 7 5 3 1 2

    std::sort_heap(datos_monticulo.begin(), datos_monticulo.end()); // Ordena el heap en orden ascendente
    std::cout << "\nDespués de sort_heap: ";
    for (int x : datos_monticulo) std::cout << x << " "; // Salida: 1 2 3 5 7 9
    std::cout << std::endl;
    return 0;
}

5. Algoritmos de Mínimo/Máximo

Encuentran los valores o elementos extremos en un rango.

5.1. min y max

Retornan el menor/mayor de dos valores o de una lista de inicializadores.

#include <iostream>
#include <algorithm> // Para min, max
#include <vector>    // Necesario para initializer_list

int main() {
    int val_a = 15, val_b = 8;
    int menor_entre_dos = std::min(val_a, val_b); // 8
    int mayor_entre_dos = std::max(val_a, val_b); // 15
    std::cout << "Menor entre " << val_a << " y " << val_b << ": " << menor_entre_dos << std::endl;
    std::cout << "Mayor entre " << val_a << " y " << val_b << ": " << mayor_entre_dos << std::endl;

    auto min_lista = std::min({5, 9, 2, 7, 3}); // 2
    auto max_lista = std::max({5, 9, 2, 7, 3}); // 9
    std::cout << "Menor de la lista: " << min_lista << std::endl;
    std::cout << "Mayor de la lista: " << max_lista << std::endl;
    return 0;
}

5.2. min_element y max_element

Retornan un iterador al elemento mínimo/máximo en un rango.

#include <iostream>
#include <vector>
#include <algorithm> // Para min_element, max_element

int main() {
    std::vector<double> medidas = {3.14, 1.618, 2.718, 0.577};
    auto it_min = std::min_element(medidas.begin(), medidas.end());
    auto it_max = std::max_element(medidas.begin(), medidas.end());
    std::cout << "Mínimo elemento: " << *it_min << std::endl; // Salida: 0.577
    std::cout << "Máximo elemento: " << *it_max << std::endl; // Salida: 3.14
    return 0;
}

5.3. minmax_element (C++11)

Retorna un std::pair de iteradores al elemento mínimo y máximo en un rango.

#include <iostream>
#include <vector>
#include <algorithm> // Para minmax_element

int main() {
    std::vector<int> calificaciones = {85, 92, 78, 95, 88};
    auto par_min_max = std::minmax_element(calificaciones.begin(), calificaciones.end());
    std::cout << "Calificación mínima: " << *par_min_max.first << std::endl;  // Salida: 78
    std::cout << "Calificación máxima: " << *par_min_max.second << std;<< "std::endl; // Salida: 95
    return 0;
}

6. Algoritmos Numéricos (en <numeric>)

Proporcionan operaciones matemáticas comunes sobre rangos.

6.1. accumulate

Calcula la suma (o cualquier operación binaria) de los elementos en un rango, empezando por un valor inicial.

#include <iostream>
#include <vector>
#include <numeric>   // Para accumulate
#include <functional> // Para std::multiplies

int main() {
    std::vector<int> serie = {1, 2, 3, 4};
    int suma_total = std::accumulate(serie.begin(), serie.end(), 0); // 0 es el valor inicial
    std::cout << "Suma de los elementos: " << suma_total << std::endl; // Salida: 10

    int producto_total = std::accumulate(serie.begin(), serie.end(), 1, std::multiplies<int>()); // 1 es el valor inicial
    std::cout << "Producto de los elementos: " << producto_total << std::endl; // Salida: 24

    std::string frase = std::accumulate(std::next(serie.begin()), serie.end(),
                                        std::to_string(serie[0]),
                                        [](std::string a, int b){ return std::move(a) + "-" + std::to_string(b); });
    std::cout << "Concatenación de cadena: " << frase << std::endl; // Salida: 1-2-3-4
    return 0;
}

6.2. inner_product

Calcula el producto escalar de dos rangos (o una operación generalizada).

#include <iostream>
#include <vector>
#include <numeric> // Para inner_product

int main() {
    std::vector<int> v_x = {1, 2, 3};
    std::vector<int> v_y = {5, 6, 7};
    // Producto escalar: (1*5) + (2*6) + (3*7) = 5 + 12 + 21 = 38
    int prod_escalar = std::inner_product(v_x.begin(), v_x.end(), v_y.begin(), 0);
    std::cout << "Producto escalar: " << prod_escalar << std::endl; // Salida: 38
    return 0;
}

6.3. iota (C++11)

Rellena un rango con valores incrementales, comenzando desde un valor dado.

#include <iostream>
#include <vector>
#include <numeric> // Para iota

int main() {
    std::vector<int> secuencia(7);
    std::iota(secuencia.begin(), secuencia.end(), 100); // Rellena con 100, 101, ...
    std::cout << "Secuencia generada con iota: ";
    for (int x : secuencia) std::cout << x << " "; // Salida: 100 101 102 103 104 105 106
    std::cout << std::endl;
    return 0;
}

6.4. partial_sum

Calcula la suma parcial de los elementos de un rango y almacena los resultados en otro rango.

#include <iostream>
#include <vector>
#include <numeric> // Para partial_sum

int main() {
    std::vector<int> entrada = {1, 2, 3, 4, 5};
    std::vector<int> sumas_parciales(entrada.size());
    std::partial_sum(entrada.begin(), entrada.end(), sumas_parciales.begin());
    std::cout << "Sumas parciales: ";
    for (int x : sumas_parciales) std::cout << x << " "; // Salida: 1 3 6 10 15
    std::cout << std::endl;
    return 0;
}

6.5. adjacent_difference

Calcula la diferencia entre elementos adyacentes en un rango y los almacena en otro rango. El primer elemento se copia sin cambios.

#include <iostream>
#include <vector>
#include <numeric> // Para adjacent_difference

int main() {
    std::vector<int> serie_numerica = {10, 12, 15, 19, 24};
    std::vector<int> diferencias(serie_numerica.size());
    std::adjacent_difference(serie_numerica.begin(), serie_numerica.end(), diferencias.begin());
    std::cout << "Diferencias adyacentes: ";
    for (int x : diferencias) std::cout << x << " "; // Salida: 10 2 3 4 5
    std::cout << std::endl;
    return 0;
}

7. Otros Algoritmos Útiles

7.1. Generación: generate

Rellena un rango con valores producidos por una función generadora (típicamente una lambda).

#include <iostream>
#include <vector>
#include <algorithm> // Para generate

int main() {
    std::vector<int> vector_generado(6);
    int contador = 100;
    std::generate(vector_generado.begin(), vector_generado.end(), [&contador]() { 
        return contador++; 
    }); 
    std::cout << "Vector generado: ";
    for (int x : vector_generado) std::cout << x << " "; // Salida: 100 101 102 103 104 105
    std::cout << std::endl;
    return 0;
}

7.2. Generación Parcial: generate_n

Rellena los primeros N elementos de un rango con valores producidos por una función generadora.

#include <iostream>
#include <vector>
#include <algorithm> // Para generate_n

int main() {
    std::vector<int> vector_parcial(5, 99); // Inicializa con 99
    int inicio_val = 1;
    // Generar los primeros 3 elementos con valores incrementales
    std::generate_n(vector_parcial.begin(), 3, [&inicio_val]() { 
        return inicio_val++; 
    }); 
    std::cout << "Vector generado parcialmente: ";
    for (int x : vector_parcial) std::cout << x << " "; // Salida: 1 2 3 99 99
    std::cout << std::endl;
    return 0;
}

7.3. Inclusión de Conjuntos: includes

Comprueba si un rango ordenado contiene todos los elementos de otro rango ordenado.

#include <iostream>
#include <vector>
#include <algorithm> // Para includes

int main() {
    std::vector<int> conjunto_mayor = {10, 20, 30, 40, 50};
    std::vector<int> subconjunto_valido = {20, 40};
    std::vector<int> subconjunto_invalido = {15, 20};

    bool incluye_valido = std::includes(conjunto_mayor.begin(), conjunto_mayor.end(),
                                        subconjunto_valido.begin(), subconjunto_valido.end());
    std::cout << "El conjunto_mayor incluye {20, 40}? " << std::boolalpha << incluye_valido << std::endl; // Salida: true

    bool incluye_invalido = std::includes(conjunto_mayor.begin(), conjunto_mayor.end(),
                                         subconjunto_invalido.begin(), subconjunto_invalido.end());
    std::cout << "El conjunto_mayor incluye {15, 20}? " << std::boolalpha << incluye_invalido << std::endl; // Salida: false
    return 0;
}

7.4. Operaciones de Conjuntos: set_union, set_intersection, set_difference, set_symmetric_difference

Realizan operaciones estándar de teoría de conjuntos en rangos ordenados.

#include <iostream>
#include <vector>
#include <algorithm> // Para set_union, set_intersection, set_difference, set_symmetric_difference
#include <iterator>  // Para back_inserter

int main() {
    std::vector<int> s1 = {1, 2, 3, 4, 5};
    std::vector<int> s2 = {4, 5, 6, 7, 8};
    std::vector<int> resultado;

    std::cout << "Conjunto 1: {1 2 3 4 5}" << std::endl;
    std::cout << "Conjunto 2: {4 5 6 7 8}" << std::endl;

    // Unión (s1 U s2)
    std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(resultado));
    std::cout << "Unión: ";
    for (int x : resultado) std::cout << x << " "; // Salida: 1 2 3 4 5 6 7 8
    std::cout << std::endl;

    // Intersección (s1 ∩ s2)
    resultado.clear();
    std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(resultado));
    std::cout << "Intersección: ";
    for (int x : resultado) std::cout << x << " "; // Salida: 4 5
    std::cout << std::endl;

    // Diferencia (s1 - s2)
    resultado.clear();
    std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(resultado));
    std::cout << "Diferencia (s1 - s2): ";
    for (int x : resultado) std::cout << x << " "; // Salida: 1 2 3
    std::cout << std::endl;

    // Diferencia simétrica ((s1 U s2) - (s1 ∩ s2))
    resultado.clear();
    std::set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(resultado));
    std::cout << "Diferencia simétrica: ";
    for (int x : resultado) std::cout << x << " "; // Salida: 1 2 3 6 7 8
    std::cout << std::endl;
    return 0;
}

8. Preguntas Comunes sobre Algoritmos STL

8.1. ¿Cuál es la diferencia entre std::sort y std::stable_sort?

• std::sort es típicamente más rápido (implementación usualmente Introsort, una combinación de Quicksort, Heapsort y Insertion Sort). No garantiza la estabilidad, lo que significa que el orden relativo de los elementos que se comparan como "iguales" puede cambiar. Su complejidad temporal promedio es O(N log N) y espacial O(log N) o O(N) para casos patológicos.
• std::stable_sort garantiza que el orden relativo de los elementos equivalentes se mantendrá. Generalmente utiliza una implementación basada en Merge Sort. Es un poco más lento que std::sort y su complejidad espacial puede ser O(N) en el peor de los casos, pero su complejidad temporal es O(N log N) garantizada.

8.2. ¿Por qué los algoritmos remove (y remove_if) requieren combinarse con erase?

Los algoritmos std::remove y std::remove_if son genéricos y no pueden modificar el tamaño subyacente del contenedor (como std::vector::size() o std::list::size()). Su función es reordenar los elementos de manera que aquellos que no deben ser "eliminados" se muevan al principio del rango. Retornan un iterador al nuevo "final lógico". Los elementos entre este nuevo final lógico y el final original del contenedor son los que deberían ser eliminados. Para una eliminación física que reduzca el tamaño del contenedor y libere memoria, es necesario llamar al método erase() del contenedor con el rango definido por el iterador retornado por remove y el final original del contenedor. Esta combinación se conoce como el "patrón erase-remove": contenedor.erase(std::remove(contenedor.begin(), contenedor.end(), valor), contenedor.end());

8.3. ¿Qué algoritmos requieren que el rango de entrada esté previamente ordenado?

Varios algoritmos dependen de que los rangos estén ordenados para funcionar correctamente o de manera eficiente. Entre ellos se encuentran:

• Algoritmos de búsqueda binaria: std::binary_search, std::lower_bound, std::upper_bound, std::equal_range.
• Algoritmos de fusión: std::merge.
• Algoritmos de operaciones de conjuntos: std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference, std::includes.
• Algunas sobrecargas de std::unique pueden beneficiarse de un rango ordenado si se quieren eliminar todos los duplicados, no solo los consecutivos. De hecho, std::unique solo elimina duplicados *consecutivos*, por lo que para eliminar todos los duplicados en un rango, se suele aplicar std::sort primero y luego std::unique.