1. Algoritmos de no modificación

Estos algoritmos no alteran los elementos del contenedor sobre el que operan.

1.1 find y find_if

• find(inicio, fin, valor): Localiza el primer elemento igual a valor, devolviendo un iterador (fin si no se encuentra).
• find_if(inicio, fin, predicado): Localiza el primer elemento que satisface el predicado.
• find_end(inicio, fin, sub_inicio, sub_fin): Busca la última aparición de una subsecuenica.

std::vector<int> datos = {1, 3, 5, 7, 9};

// Buscar elemento con valor 5
auto iter = std::find(datos.begin(), datos.end(), 5);
if (iter != datos.end()) {
    std::cout << "encontrado: " << *iter << std::endl;  // Imprime: 5
}

// Buscar primer elemento mayor a 6
auto iter2 = std::find_if(datos.begin(), datos.end(), [](int x) {
    return x > 6;
});
std::cout << "primero >6: " << *iter2 << std::endl;  // Imprime: 7

// Buscar subsecuencia
std::vector<int> sub = {3, 5};
auto iter3 = std::find_end(datos.begin(), datos.end(), sub.begin(), sub.end());
if (iter3 != datos.end()) {
    std::cout << "subsecuencia inicia en índice: " << iter3 - datos.begin() << std::endl;  // Imprime: 1
}

1.2 count y count_if

• count(inicio, fin, valor): Cuenta las ocurrencias de valor.
• count_if(inicio, fin, predicado): Cuenta los elementos que cumplen el predicado.

std::vector<int> numeros = {1, 2, 3, 2, 4, 2};
int cantidad = std::count(numeros.begin(), numeros.end(), 2); // Cantidad de 2's, resultado: 3
int pares = std::count_if(numeros.begin(), numeros.end(), [](int x) { 
    return x % 2 == 0; 
}); // Cantidad de pares, resultado: 4

1.3 for_each

Aplica una función a cada elemento del rango.

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

1.4 equal y mismatch

• equal(ini1, fin1, ini2): Determina si dos rangos [ini1,fin1) y [ini2, ini2+(fin1-ini1)) son iguales.
• mismatch(ini1, fin1, ini2): Devuelve un par de iteradores al primer elemento diferente.

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {1, 2, 4};
std::vector<int> v3 = {1, 2, 3, 4};

// Comparar v1 y v2 (primeros 3 elementos)
bool iguales = std::equal(v1.begin(), v1.end(), v2.begin());
std::cout << "v1 == v2? " << std::boolalpha << iguales << std::endl;  // Imprime: false

// Buscar primer desajuste entre v1 y v3
auto desajuste = std::mismatch(v1.begin(), v1.end(), v3.begin());
if (desajuste.first != v1.end()) {
    std::cout << "desajuste: " << *desajuste.first << " vs " << *desajuste.second << std::endl;  // Sin salida (v1 y v3 primeros 3 iguales)
}

1.5 all_of, any_of, none_of

Verifican si todos, algún o ningún elemento cumple una condición.

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

2. Algoritmos de modificación

Estos algoritmos modifican los elementos del contenedor.

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 solo los elementos que cumplen el predicado.

std::vector<int> origen = {1, 2, 3, 4, 5};
std::vector<int> destino(5);  // Debe tener espacio suficiente

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

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

Nota: back_inserter(destino) invoca automáticamente push_back, sin necesidad de preasignar espacio.

2.2 transform

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

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

// Calcular cuadrados (transformación unaria)
std::transform(numeros.begin(), numeros.end(), cuadrados.begin(), [](int x) {
    return x * x;
});  // cuadrados: [1,4,9]

// Sumar elementos de dos contenedores (transformación binaria)
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::vector<int> suma(3);
std::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, viejo, nuevo): Reemplaza todas las ocurrencias de viejo por nuevo.
• replace_if(inicio, fin, predicado, nuevo): Reemplaza los elementos que cumplen el predicado.
• replace_copy(inicio, fin, destino, viejo, nuevo): Copia reemplazando durante la copia.

std::vector<int> valores = {1, 2, 3, 2, 5};

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

// Reemplazar mayores a 10 por 0
std::replace_if(valores.begin(), valores.end(), [](int x) {
    return x > 10;
}, 0);  // valores: [1,0,3,0,5]

// Copiar reemplazando 3 por 300 (original intacto)
std::vector<int> resultado;
std::replace_copy(valores.begin(), valores.end(), std::back_inserter(resultado), 3, 300);  // resultado: [1,0,300,0,5]

2.4 remove, remove_if y erase

• remove(inicio, fin, valor): Mueve los elementos igual a valor al final, devuelve nuevo iterador lógico (no elimina realmente).
• remove_if(inicio, fin, predicado): Mueve los elementos que cumplen el predicado al final.

std::vector<int> datos = {1, 2, 3, 2, 4};

// Eliminación lógica de todos los 2
auto nuevo_fin = std::remove(datos.begin(), datos.end(), 2);  // datos: [1,3,4,2,2]

// Eliminación física (real)
datos.erase(nuevo_fin, datos.end());  // datos: [1,3,4]

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

2.5 unique

Elimina duplicados consecutivos, devuelve nuevo final lógico. Normalmente se combina con erase.

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

2.6 reverse

Invierte el orden de los elementos en el rango.

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

2.7 rotate

Rota los elementos para que el indicado sea el primero.

std::vector<int> items = {1, 2, 3, 4, 5};
std::rotate(items.begin(), items.begin() + 2, items.end()); // items: {3, 4, 5, 1, 2}

2.8 shuffle

Reordena aleatoriamente los elementos (C++11 en adelante).

#include <random>
#include <algorithm>

std::vector<int> elementos = {1, 2, 3, 4, 5};
std::random_device dispositivo;
std::mt19937 generador(dispositivo());
std::shuffle(elementos.begin(), elementos.end(), generador); // Orden aleatorio

3. Algoritmos de ordenamiento

3.1 sort, stable_sort y partial_sort

• sort(inicio, fin): Ordena con QuickSort (inestable, O(n log n) promedio).
• stable_sort(inicio, fin): Ordenamiento estable (MergeSort).
• partial_sort(inicio, medio, fin): Ordena parcialmente los primeros elementos.

std::vector<int> datos = {5, 3, 1, 4, 2};
std::sort(datos.begin(), datos.end()); // Ascendente: {1, 2, 3, 4, 5}
std::sort(datos.begin(), datos.end(), std::greater<int>()); // Descendente: {5, 4, 3, 2, 1}
std::sort(datos.begin(), datos.end(), [](int a, int b) { 
    return a < b; 
}); // Ascendente con lambda

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; // Ordena por first, manteniendo orden relativo de iguales
});

std::vector<int> nums = {5, 3, 1, 4, 2, 6};
std::partial_sort(nums.begin(), nums.begin() + 3, nums.end());
// Primeros 3: 1, 2, 3; resto desordenado

3.2 nth_element

Reordena para que el elemento en la posición n sea el que le correspondería tras ordenar.

std::vector<int> valores = {5, 3, 1, 4, 2, 6};
std::nth_element(valores.begin(), valores.begin() + 2, valores.end());
// valores[2] = 3, elementos a izquierda <=3, derecha >=3

3.3 binary_search, lower_bound, upper_bound

Requieren contenedor ordenado.

• binary_search(inicio, fin, valor): Verifica existencia (booleano).
• lower_bound(inicio, fin, valor): Primer elemento no menor a valor.
• upper_bound(inicio, fin, valor): Primer elemento mayor a valor.

std::vector<int> ordenado = {1, 3, 3, 5, 7};

bool existe = std::binary_search(ordenado.begin(), ordenado.end(), 3);  // true

auto lb = std::lower_bound(ordenado.begin(), ordenado.end(), 3);
std::cout << "lower_bound índice: " << lb - ordenado.begin() << std::endl;  // 1

auto ub = std::upper_bound(ordenado.begin(), ordenado.end(), 3);
std::cout << "upper_bound índice: " << ub - ordenado.begin() << std::endl;  // 3

3.4 merge

Combina dos rangos ordenados en uno nuevo (también ordenado).

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

std::merge(a.begin(), a.end(), b.begin(), b.end(), fusionado.begin());  // [1,2,3,4,5,6]

4. Algoritmos de heap

STL provee operaciones de heap: make_heap, push_heap, pop_heap, sort_heap.

std::vector<int> monticulo = {4, 1, 3, 2, 5};
std::make_heap(monticulo.begin(), monticulo.end()); // Max-heap: {5, 4, 3, 2, 1}

monticulo.push_back(6);
std::push_heap(monticulo.begin(), monticulo.end()); // Inserta 6: {6, 4, 5, 2, 1, 3}

std::pop_heap(monticulo.begin(), monticulo.end()); // Máximo al final: {5, 4, 3, 2, 1, 6}
int maximo = monticulo.back(); // 6
monticulo.pop_back();

std::sort_heap(monticulo.begin(), monticulo.end()); // Ascendente: {1, 2, 3, 4, 5}

5. Algoritmos de mínimo/máximo

5.1 min y max

int a = 5, b = 3;
int min_val = std::min(a, b); // 3
int max_val = std::max(a, b); // 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

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)

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 (<numeric>)

6.1 accumulate

#include <numeric>

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

6.2 inner_product

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

6.3 iota

std::vector<int> rango(5);
std::iota(rango.begin(), rango.end(), 10); // {10, 11, 12, 13, 14}

6.4 partial_sum

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

6.5 adjacent_difference

std::vector<int> entrada = {1, 2, 3, 4, 5};
std::vector<int> salida(entrada.size());
std::adjacent_difference(entrada.begin(), entrada.end(), salida.begin()); // {1, 1, 1, 1, 1}

7. Otros algoritmos

7.1 generate

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

7.2 generate_n

std::vector<int> contenedor(5);
int inicio = 10;
std::generate_n(contenedor.begin(), 3, [&inicio]() { 
    return inicio++; 
}); // Primeros 3: {10, 11, 12}, resto sin cambios

7.3 includes

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

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

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: {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: {3, 4, 5}

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

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

8. Preguntas frecuentes

1. ¿Diferencia entre sort y stable_sort?
   sort usa introsort (inestable, O(n log n) pormedio). stable_sort usa mergesort (estable, O(n log n), mayor uso de memoria).
2. ¿Por qué remove necesita erase?
   remove solo "cubre" los elementos a eliminar moviendo los restantes hacia adelante y devolviendo un nuevo final lógico, pero no modifica el tamaño del contenedor. erase elimina realmente usando el iterador devuelto.
3. ¿Qué algoritmos requieren contenedores ordenados?
   Búsqueda binaria (binary_search, lower_bound, upper_bound), algoritmos de conjuntos (set_intersection, set_union, etc.), merge, entre otros. Dependen del orden para eficiencia (búsqueda O(log n)).