1. Algoritmos de Secuencias No Modificadores

Estos algoritmos no modifican los elementos de los contenedores en los que operan.

1.1 find y find_if

• find(inicio, fin, valor): Busca el primer elemento igual a valor, devuelve un iterador (si no lo encuentra devuelve fin).
• find_if(inicio, fin, predicado): Busca el primer elemento que cumple con el predicado.
• find_end(inicio, fin, sub_inicio, sub_fin): Busca la última posición donde aparece la subsecuencia.

vector<int> numeros = {1, 3, 5, 7, 9};

// Buscar elemento con valor 5
auto iterador = find(numeros.begin(), numeros.end(), 5);
if (iterador != numeros.end()) {
    cout << "encontrado: " << *iterador << endl;  // Salida: 5
}

// Buscar el primer elemento mayor que 6
auto iterador2 = find_if(numeros.begin(), numeros.end(), [](int x) {
    return x > 6;
});
cout << "primer >6: " << *iterador2 << endl;  // Salida: 7

// Buscar subsecuencia
vector<int> sub = {3, 5};
auto iterador3 = find_end(numeros.begin(), numeros.end(), sub.begin(), sub.end());
if (iterador3 != numeros.end()) {
    cout << "subsecuencia comienza en índice: " << iterador3 - numeros.begin() << endl;  // Salida: 1
}

1.2 count y count_if

• count(inicio, fin, valor): Cuenta el número de elementos iguales a valor.
• count_if(inicio, fin, predicado): Cuenta los elementos que cumplen con el predicado.

std::vector<int> datos = {1, 2, 3, 2, 4, 2};
int contador = std::count(datos.begin(), datos.end(), 2); // Cuenta las ocurrencias de 2, resultado 3
int pares = std::count_if(datos.begin(), datos.end(), [](int x) { 
    return x % 2 == 0; 
}); // Cuenta números pares, resultado 3

1.3 for_each

Aplica una función a cada elemento en un rango

std::vector<int> datos = {1, 2, 3, 4, 5};
std::for_each(datos.begin(), datos.end(), [](int& x) { 
    x *= 2; // Multiplica cada elemento por 2
});
// Ahora datos es {2, 4, 6, 8, 10}

1.4 equal y mismatch

• equal(b1, e1, b2): Compara si los rangos [b1,e1) y [b2, b2+(e1-b1)) son iguales.
• mismatch(b1, e1, b2): Devuelve un par de iteradores a los primeros elementos diferentes en ambos rangos.

vector<int> a = {1, 2, 3};
vector<int> b = {1, 2, 4};
vector<int> c = {1, 2, 3, 4};

// Comparar primeros 3 elementos de a y b
bool son_iguales = equal(a.begin(), a.end(), b.begin());
cout << "a == b? " << boolalpha << son_iguales << endl;  // Salida: false

// Encontrar primer elemento diferente entre a y c
auto desajuste = mismatch(a.begin(), a.end(), c.begin());
if (desajuste.first != a.end()) {
    cout << "desajuste: " << *desajuste.first << " vs " << *desajuste.second << endl;  // Sin salida (primeros 3 elementos de a y c son iguales)
}

1.5 all_of, any_of, none_of

Comprueba si todos, algunos o ninguno de los elementos cumplen una condición

std::vector<int> datos = {2, 4, 6, 8};
bool todos_pares = std::all_of(datos.begin(), datos.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool hay_impar = std::any_of(datos.begin(), datos.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool ninguno_negativo = std::none_of(datos.begin(), datos.end(), [](int x) { 
    return x < 0; 
}); // true

2. Algoritmos de Secuencias Modificadores

Estos algoritmos modifican los elementos de los contenedores en los que operan.

2.1 copy y copy_if

• copy(inicio, fin, destino): Copia elementos de [inicio, fin) a partir de destino.
• copy_if(inicio, fin, destino, predicado): Copia elementos que cumplen el predicado a destino.

vector<int> origen = {1, 2, 3, 4, 5};
vector<int> destino(5);  // Se debe asignar espacio suficiente previamente

// Copiar todos los elementos
copy(origen.begin(), origen.end(), destino.begin());  // destino: [1,2,3,4,5]

// Copiar elementos pares a un nuevo contenedor
vector<int> pares;
copy_if(origen.begin(), origen.end(), back_inserter(pares), [](int x) {
    return x % 2 == 0;
});  // pares: [2,4]

Nota: back_inserter(destino) llama automáticamente a push_back, no es necesario asignar espacio previamente.

2.2 transform

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

vector<int> numeros = {1, 2, 3};
vector<int> cuadrados(3);

// Calcular cuadrados (transformación de un parámetro)
transform(numeros.begin(), numeros.end(), cuadrados.begin(), [](int x) {
    return x * x;
});  // cuadrados: [1,4,9]

// Sumar elementos de dos contenedores (transformación de dos parámetros)
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> suma(3);
transform(a.begin(), a.end(), b.begin(), suma.begin(), [](int x, int y) {
    return x + y;
});  // suma: [5,7,9]

2.3 replace, replace_if y replace_copy

• replace(inicio, fin, valor_antiguo, valor_nuevo): Reemplaza todos los valor_antiguo con valor_nuevo.
• replace_if(inicio, fin, predicado, valor_nuevo): Reemplaza elementos que cumplen el predicado.
• replace_copy(inicio, fin, destino, valor_antiguo, valor_nuevo): Copia reemmplazando elementos (no modifica el contenedor original).

vector<int> numeros = {1, 2, 3, 2, 5};

// Reemplazar todos los 2 con 20
replace(numeros.begin(), numeros.end(), 2, 20);  // numeros: [1,20,3,20,5]

// Reemplazar elementos mayores que 10 con 0
replace_if(numeros.begin(), numeros.end(), [](int x) {
    return x > 10;
}, 0);  // numeros: [1,0,3,0,5]

// Copiar reemplazando 3 con 300 (contenedor original sin cambios)
vector<int> resultado;
replace_copy(numeros.begin(), numeros.end(), back_inserter(resultado), 3, 300);  // resultado: [1,0,300,0,5]

2.4 remove, remove_if y erase

• remove(inicio, fin, valor): "Mueve" elementos iguales a valor al final del contenedor, devuelve un nuevo iterador lógico al final (no elimina realmente los elementos, debe usarse con erase).
• remove_if(inicio, fin, predicado): Mueve elementos que cumplen el predicado al final.

vector<int> numeros = {1, 2, 3, 2, 4};

// Eliminación lógica de todos los 2 (se mueven al final)
auto nuevo_final = remove(numeros.begin(), numeros.end(), 2);  // numeros: [1,3,4,2,2]

// Eliminación física (realmente se eliminan los elementos)
numeros.erase(nuevo_final, numeros.end());  // numeros: [1,3,4]

// Combinar con lambda para eliminar pares
numeros = {1, 2, 3, 4, 5};
numeros.erase(remove_if(numeros.begin(), numeros.end(), [](int x) {
    return x % 2 == 0;
}), numeros.end());  // numeros: [1,3,5]

2.5 unique

Elimina elementos duplicados consecutivos en un rango, devuelve un nuevo iterador lógico al final. Normalmente se usa con erase.

std::vector<int> datos = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto ultimo = std::unique(datos.begin(), datos.end());
datos.erase(ultimo, datos.end()); // datos se convierte en {1, 2, 3, 4, 5}

2.6 reverse

Invierte el orden de los elementos en un rango

std::vector<int> datos = {1, 2, 3, 4, 5};
std::reverse(datos.begin(), datos.end()); // datos se convierte en {5, 4, 3, 2, 1}

2.7 rotate

Rota los elementos de un rango, haciendo que un elemento intermedio se convierta en el primero

std::vector<int> datos = {1, 2, 3, 4, 5};
std::rotate(datos.begin(), datos.begin() + 2, datos.end()); // Rota con 3起点, datos se convierte en {3, 4, 5, 1, 2}

2.8 shuffle

Reorganiza aleatoriamente los elementos de un rango (requiere C++11 o superior)

#include <random>
#include <algorithm>

std::vector<int> datos = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(datos.begin(), datos.end(), g); // Reorganiza aleatoriamente los elementos de datos

3. Algoritmos de Ordenación y Relacionados

3.1 sort, stable_sort y partial_sort

• sort(inicio, fin): Ordena elementos usando quicksort (inestable, complejidad temporal promedio O(n log n)).
• stable_sort(inicio, fin): Ordenación estable (la posición relativa de elementos iguales no cambia).
• partial_sort(inicio, medio, fin): Ordenación parcial, haciendo que [inicio, medio) sean los elementos más pequeños del rango completo y ordenados.

std::vector<int> datos = {5, 3, 1, 4, 2};
std::sort(datos.begin(), datos.end()); // Orden ascendente por defecto, datos se convierte en {1, 2, 3, 4, 5}
std::sort(datos.begin(), datos.end(), std::greater<int>()); // Orden descendente, datos se convierte en {5, 4, 3, 2, 1}
std::sort(datos.begin(), datos.end(), [](int a, int b) { 
    return a < b; 
}); // Orden ascendente, comparador personalizado

std::vector<std::pair<int, int>> pares = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(pares.begin(), pares.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // Ordenar por first, mantener orden relativo de elementos iguales
});

std::vector<int> datos = {5, 3, 1, 4, 2, 6};
// Ordenar los 3 elementos más pequeños y ponerlos al frente
std::partial_sort(datos.begin(), datos.begin() + 3, datos.end());
// Ahora los primeros 3 elementos de datos son 1, 2, 3, los restantes son 4, 5, 6 sin ordenar

3.2 nth_element

Reorganiza el rango para que el elemento en la posición especificada esté en su posición final si el rango estuviera ordenado, y los elementos a su izquierda no sean mayores que él, y los de la derecha no menores que él

std::vector<int> datos = {5, 3, 1, 4, 2, 6};
// Encontrar el tercer elemento más pequeño (índice 2)
std::nth_element(datos.begin(), datos.begin() + 2, datos.end());
// Ahora datos[2] es 3, los elementos a su izquierda son <=3, los de la derecha son >=3

3.3 binary_search, lower_bound, upper_bound

Deben usarse en contenedores ordenados

• binary_search(inicio, fin, valor): Comprueba si valor existe (devuelve bool).
• lower_bound(inicio, fin, valor): Devuelve un iterador al primer elemento no menor que valor.
• upper_bound(inicio, fin, valor): Devuelve un iterador al primer elemento mayor que valor.

vector<int> ordenado = {1, 3, 3, 5, 7};  // Debe estar ordenado

// Comprobar si 3 existe
bool existe = binary_search(ordenado.begin(), ordenado.end(), 3);  // true

// Buscar primer elemento >=3
auto lb = lower_bound(ordenado.begin(), ordenado.end(), 3);
cout << "lower_bound índice: " << lb - ordenado.begin() << endl;  // Salida: 1

// Buscar primer elemento >3
auto ub = upper_bound(ordenado.begin(), ordenado.end(), 3);
cout << "upper_bound índice: " << ub - ordenado.begin() << endl;  // Salida: 3

3.4 merge

Fusiona dos rangos ordenados en un nuevo contenedor (manteniendo el orden)

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> fusionado(a.size() + b.size());

// Fusionar a y b (ambos deben estar ordenados)
merge(a.begin(), a.end(), b.begin(), b.end(), fusionado.begin());  // fusionado: [1,2,3,4,5,6]

4. Algoritmos de Montículo (Heap)

La STL proporciona algoritmos para operar con rangos como montículos, incluyendo make_heap, push_heap, pop_heap, sort_heap, etc.

std::vector<int> datos = {4, 1, 3, 2, 5};
std::make_heap(datos.begin(), datos.end()); // Construye un montículo máximo, datos se convierte en {5, 4, 3, 2, 1}

datos.push_back(6);
std::push_heap(datos.begin(), datos.end()); // Agrega el nuevo elemento al montículo, datos se convierte en {6, 4, 5, 2, 1, 3}

std::pop_heap(datos.begin(), datos.end()); // Mueve el elemento máximo al final, datos se convierte en {5, 4, 3, 2, 1, 6}
int max_val = datos.back(); // Obtiene el elemento máximo 6
datos.pop_back(); // Elimina el elemento máximo

std::sort_heap(datos.begin(), datos.end()); // Ordena el montículo en secuencia ascendente, datos se convierte en {1, 2, 3, 4, 5}

5. Algoritmos de Mínimo/Máximo

5.1 min y max

Devuelven el valor mínimo/máximo entre dos valores o una lista inicializada

int x = 5, y = 3;
int min_val = std::min(x, y); // 3
int max_val = std::max(x, y); // 5

auto min_lista = std::min({4, 2, 8, 5, 1}); // 1
auto max_lista = std::max({4, 2, 8, 5, 1}); // 8

5.2 min_element y max_element

Devuelven iteradores al elemento mínimo/máximo en un rango

std::vector<int> datos = {3, 1, 4, 2, 5};
auto min_it = std::min_element(datos.begin(), datos.end()); // Apunta a 1
auto max_it = std::max_element(datos.begin(), datos.end()); // Apunta a 5

5.3 minmax_element (C++11)

Devuelve simultáneamente iteradores al elemento mínimo y máximo en un rango

std::vector<int> datos = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(datos.begin(), datos.end());
// minmax.first apunta a 1, minmax.second apunta a 5

6. Algoritmos Numéricos (en )

6.1 accumulate

Calcula la suma acumulada de elementos en un rango (o una operación personalizada)

#include <numeric>

std::vector<int> datos = {1, 2, 3, 4, 5};
int suma = std::accumulate(datos.begin(), datos.end(), 0); // Suma, valor inicial 0, resultado 15
int producto = std::accumulate(datos.begin(), datos.end(), 1, std::multiplies<int>()); // Producto, valor inicial 1, resultado 120

6.2 inner_product

Calcula el producto interno de dos rangos (o una operación personalizada)

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
int producto_punto = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32

6.3 iota

Llena un rango con valores incrementales consecutivos

std::vector<int> datos(5);
std::iota(datos.begin(), datos.end(), 10); // Llena con 10, 11, 12, 13, 14

6.4 partial_sum

Calcula las sumas parciales, almacenando los resultados en un rango de destino

std::vector<int> origen = {1, 2, 3, 4, 5};
std::vector<int> destino(origen.size());
std::partial_sum(origen.begin(), origen.end(), destino.begin()); // destino se convierte en {1, 3, 6, 10, 15}

6.5 adjacent_difference

Calcula las diferencias entre elementos adyacentes, almacenando los resultados en un rango de destino

std::vector<int> origen = {1, 2, 3, 4, 5};
std::vector<int> destino(origen.size());
std::adjacent_difference(origen.begin(), origen.end(), destino.begin()); // destino se convierte en {1, 1, 1, 1, 1}

7. Otros Algoritmos

7.1 generate

Llena un rango usando una función generadora

std::vector<int> datos(5);
int n = 0;
std::generate(datos.begin(), datos.end(), [&n]() { 
    return n++; 
}); // Llena con 0, 1, 2, 3, 4

7.2 generate_n

Llena los primeros n elementos de un rango usando una función generadora

std::vector<int> datos(5);
int n = 10;
std::generate_n(datos.begin(), 3, [&n]() { 
    return n++; 
}); // Los primeros 3 elementos son 10, 11, 12, los otros 2 permanecen sin cambios

7.3 includes

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

std::vector<int> datos1 = {1, 2, 3, 4, 5};
std::vector<int> datos2 = {2, 4};
bool incluido = std::includes(datos1.begin(), datos1.end(), datos2.begin(), datos2.end()); // true

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

Realizan operaciones de conjuntos: unión, intersección, diferencia y diferencia simétrica

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> resultado;

// Unión
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultado));
// resultado es {1, 2, 3, 4, 5, 6, 7}

// Intersección
resultado.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultado));
// resultado es {3, 4, 5}

// Diferencia (v1 - v2)
resultado.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultado));
// resultado es {1, 2}

// Diferencia simétrica (v1 ∪ v2 - v1 ∩ v2)
resultado.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultado));
// resultado es {1, 2, 6, 7}

8. Preguntas Frecuentes

1. ¿Cuál es la diferencia entre sort y stable_sort?

• sort utiliza quicksort (en realidad es introsort), es inestable (la posición relativa de elementos iguales puede cambiar), complejidad temporal promedio O(n log n).
• stable_sort utiliza ordenación por mezcla (merge sort), es estable (la posición relativa de elementos iguales no cambia), complejidad temporal O(n log n), pero tiene un consumo de memoria ligeramente mayor.

2. ¿Por qué el algoritmo remove debe usarse junto con erase?

El principio del algoritmo remove es "cubrir" los elementos que se eliminarán, moviendo los elementos que se conservan al frente y devolviendo un nuevo iterador lógico al final, pero no modifica el tamaño real del contenedor. erase elimina realmente los elementos a través del rango de iteradores, modificando el tamaño del contenedor. Por lo tanto, deben usarse juntos: contenedor.erase(remove(...), contenedor.end()).

3. ¿Qué algoritmos requieren que el contenedor esté ordenado?

Los algoritmos de búsqueda binaria (binary_search, lower_bound, upper_bound), los algoritmos de conjunto (set_intersection, set_union, etc.), y merge, dependen del ordenamiento para lograr una operación eficiente (como la búsqueda binaria con O(log n)).