1. Algoritmos de No Modificación

Estas funciones examinan los elementos de un contenedor sin alterar su contenido.

1.1 find, find_if y find_end

• find(inicio, fin, valor): Localiza el primer elemento equivalente a valor, retornnado un iterador hacia él (o fin si no existe).
• find_if(inicio, fin, predicado): Obtiene el primer elemento que satisface la condición dada.
• find_end(inicio1, fin1, inicio2, fin2): Busca la última ocurrencia de una subsecuencia dentro del rango.

std::vector<int> datos = {10, 20, 30, 40, 50};

// Localizar el elemento 30
auto pos1 = std::find(datos.begin(), datos.end(), 30);
if (pos1 != datos.end()) {
    std::cout << "Encontrado: " << *pos1 << '\n';
}

// Localizar el primer elemento mayor a 25
auto pos2 = std::find_if(datos.begin(), datos.end(), [](int val) {
    return val > 25;
});
std::cout << "Primer >25: " << *pos2 << '\n';

// Buscar subsecuencia
std::vector<int> sub = {20, 30};
auto pos3 = std::find_end(datos.begin(), datos.end(), sub.begin(), sub.end());
if (pos3 != datos.end()) {
    std::cout << "Subsecuencia en índice: " << pos3 - datos.begin() << '\n';
}

1.2 count y count_if

• count(inicio, fin, valor): Cuenta cuántos elementos son iguales a valor.
• count_if(inicio, fin, predicado): Cuenta los elementos que cumplen el predicado.

std::vector<int> lista = {5, 10, 5, 15, 5};
int c5 = std::count(lista.begin(), lista.end(), 5); // Cuenta 5s, resultado: 3
int multiplos = std::count_if(lista.begin(), lista.end(), [](int v) { 
    return v % 5 == 0; 
}); // Resultado: 5

1.3 for_each

Ejecuta una función sobre cada elemento del rango especificado.

std::vector<int> lista = {1, 2, 3, 4, 5};
std::for_each(lista.begin(), lista.end(), [](int& v) { 
    v += 10; // Incrementar cada elemento
});
// lista ahora es {11, 12, 13, 14, 15}

1.4 equal y mismatch

• equal(i1, f1, i2): Comprueba si los rangos [i1, f1) y [i2, i2+(f1-i1)) son idénticos.
• mismatch(i1, f1, i2): Retorna un par de iteradores al primer par de elementos que difieren.

std::vector<int> x = {2, 4, 6};
std::vector<int> y = {2, 4, 8};
std::vector<int> z = {2, 4, 6, 10};

bool iguales = std::equal(x.begin(), x.end(), y.begin());
std::cout << "x == y? " << std::boolalpha << iguales << '\n'; // false

auto diff = std::mismatch(x.begin(), x.end(), z.begin());
if (diff.first != x.end()) {
    std::cout << "Diferencia: " << *diff.first << " vs " << *diff.second << '\n';
}

1.5 all_of, any_of, none_of

Evalúan si todos, alguno o ningún elemento del rango cumplen una condición.

std::vector<int> vals = {10, 20, 30};
bool todos_positivos = std::all_of(vals.begin(), vals.end(), [](int v) { 
    return v > 0; 
}); // true
bool alguno_negativo = std::any_of(vals.begin(), vals.end(), [](int v) { 
    return v < 0; 
}); // false
bool ninguno_cero = std::none_of(vals.begin(), vals.end(), [](int v) { 
    return v == 0; 
}); // true

2. Algoritmos de Modificación

Estas operaciones alteran los valores o el orden de los elementos en el contenedor.

2.1 copy y copy_if

• copy(inicio, fin, destino): Copia los elementos de [inicio, fin) comenzando desde destino.
• copy_if(inicio, fin, destino, predicado): Copia solo los elementos que satisfacen el predicado.

std::vector<int> origen = {10, 20, 30, 40, 50};
std::vector<int> destino(5);

std::copy(origen.begin(), origen.end(), destino.begin());

std::vector<int> mayores30;
std::copy_if(origen.begin(), origen.end(), std::back_inserter(mayores30), [](int v) {
    return v > 30;
}); // mayores30: {40, 50}

Nota: std::back_inserter invoca push_back automáticamente, evitando la necesidad de reservar espacio previamente.

2.2 transform

Aplica una operación a cada elemento, guardando el resultado en otro rango.

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

// Transformación unaria
std::transform(base.begin(), base.end(), dobles.begin(), [](int v) {
    return v * 2;
}); // dobles: {2, 4, 6}

// Transformación binaria
std::vector<int> arr1 = {10, 20, 30};
std::vector<int> arr2 = {1, 2, 3};
std::vector<int> suma(3);
std::transform(arr1.begin(), arr1.end(), arr2.begin(), suma.begin(), [](int a, int b) {
    return a + b;
}); // suma: {11, 22, 33}

2.3 replace, replace_if y replace_copy

• replace(inicio, fin, antiguo, nuevo): Sustituye todas las ocurrencias de antiguo por nuevo.
• replace_if(inicio, fin, predicado, nuevo): Sustituye los elementos que cumplen la condición.
• replace_copy(inicio, fin, destino, antiguo, nuevo): Copia los elementos reemplazando los valores indicados (el original permanece intacto).

std::vector<int> datos = {5, 10, 15, 10, 20};

std::replace(datos.begin(), datos.end(), 10, 100); // datos: {5, 100, 15, 100, 20}

std::replace_if(datos.begin(), datos.end(), [](int v) {
    return v > 50;
}, 0); // datos: {5, 0, 15, 0, 20}

std::vector<int> copia;
std::replace_copy(datos.begin(), datos.end(), std::back_inserter(copia), 15, 150); 
// copia: {5, 0, 150, 0, 20}

2.4 remove, remove_if y erase

• remove(inicio, fin, valor): Desplaza los elementos distintos a valor al frente y devuelve un iterador al nuevo final lógico (no reduce el tamaño del contenedor).
• remove_if(inicio, fin, predicado): Igual que remove, pero basado en un predicado.

std::vector<int> datos = {8, 2, 8, 5, 8};

auto nuevo_fin = std::remove(datos.begin(), datos.end(), 8); // datos: {2, 5, 8, 5, 8}
datos.erase(nuevo_fin, datos.end()); // datos: {2, 5}

datos = {8, 2, 8, 5, 8};
datos.erase(std::remove_if(datos.begin(), datos.end(), [](int v) {
    return v < 5;
}), datos.end()); // datos: {8, 8, 8}

2.5 unique

Elimina los elementos duplicados consecutivos, retornando un iterador al nuevo final lógico. Se combina frecuentemente con erase.

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

2.6 reverse

Invierte el orden de los elementos en el rango.

std::vector<int> sec = {10, 20, 30, 40};
std::reverse(sec.begin(), sec.end()); // sec: {40, 30, 20, 10}

2.7 rotate

Rota los elementos de modo que el elemento apuntado por el iterador medio se convierte en el primero.

std::vector<int> sec = {10, 20, 30, 40, 50};
std::rotate(sec.begin(), sec.begin() + 2, sec.end()); // sec: {30, 40, 50, 10, 20}

2.8 shuffle

Reordena los elementos de forma aleatoria (C++11 o superior).

#include <random>
#include <algorithm>

std::vector<int> sec = {5, 10, 15, 20};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(sec.begin(), sec.end(), gen); // Orden aleatorio

3. Algoritmos de Ordenación y Búsqueda

3.1 sort, stable_sort y partial_sort

• sort(inicio, fin): Ordenamiento rápido (introsort), inestable, O(n log n).
• stable_sort(inicio, fin): Ordenamiento estable (mergesort), O(n log n).
• partial_sort(inicio, medio, fin): Ordena los medio-inicio elementos más pequeños en el rango [inicio, medio).

std::vector<int> v = {40, 10, 30, 20};
std::sort(v.begin(), v.end()); // Ascendente: {10, 20, 30, 40}
std::sort(v.begin(), v.end(), std::greater<int>()); // Descendente: {40, 30, 20, 10}

std::vector<std::pair<int, int>> pares = {{2,1}, {1,2}};
std::stable_sort(pares.begin(), pares.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
});

std::vector<int> p = {50, 10, 40, 20, 30};
std::partial_sort(p.begin(), p.begin() + 2, p.end()); 
// Los 2 primeros son {10, 20}, el resto no está ordenado

3.2 nth_element

Reorganiza los elementos para que el elemento en la posición n sea el que estaría ahí si el contenedor estuviera ordenado. Los elementos anteriores son menores o iguales, y los posteriores son mayores o iguales.

std::vector<int> v = {50, 10, 40, 20, 30};
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] es 30; los anteriores <=30, los posteriores >=30

3.3 binary_search, lower_bound, upper_bound

Requieren contenedores ordenados.

• binary_search(inicio, fin, valor): Retorna true si valor está presente.
• lower_bound(inicio, fin, valor): Iterador al primer elemento no menor que valor.
• upper_bound(inicio, fin, valor): Iterador al primer elemento mayor que valor.

std::vector<int> ord = {10, 20, 20, 30, 40};

bool existe = std::binary_search(ord.begin(), ord.end(), 20); // true

auto lb = std::lower_bound(ord.begin(), ord.end(), 20);
std::cout << "lower_bound índice: " << lb - ord.begin() << '\n'; // 1

auto ub = std::upper_bound(ord.begin(), ord.end(), 20);
std::cout << "upper_bound índice: " << ub - ord.begin() << '\n'; // 3

3.4 merge

Combina dos rangos ordenados en un nuevo rango manteniendo el orden.

std::vector<int> a = {10, 30, 50};
std::vector<int> b = {20, 40, 60};
std::vector<int> resultado(a.size() + b.size());

std::merge(a.begin(), a.end(), b.begin(), b.end(), resultado.begin()); 
// resultado: {10, 20, 30, 40, 50, 60}

4. Algoritmos de Montículos (Heaps)

La STL permite tratar un rango como un heap máximo usando make_heap, push_heap, pop_heap, y sort_heap.

std::vector<int> h = {20, 10, 30, 5};
std::make_heap(h.begin(), h.end()); // Max-heap

h.push_back(40);
std::push_heap(h.begin(), h.end()); // Inserta 40

std::pop_heap(h.begin(), h.end()); // Mueve el máximo al final
int max_val = h.back();
h.pop_back(); // Elimina el máximo

std::sort_heap(h.begin(), h.end()); // Convierte el heap en rango ordenado ascendentemente

5. Algoritmos de Mínimos y Máximos

5.1 min y max

Retornan el menor o mayor de dos valores, o de una lista de inicialización.

int menor = std::min(100, 200); // 100
int mayor = std::max(100, 200); // 200

auto m_lista = std::min({8, 3, 9, 1}); // 1

5.2 min_element y max_element

Rteornan iteradores al elemento más pequeño o más grande del rango.

std::vector<int> v = {7, 2, 9, 4};
auto it_min = std::min_element(v.begin(), v.end()); // Apunta a 2
auto it_max = std::max_element(v.begin(), v.end()); // Apunta a 9

5.3 minmax_element

Retorna un par de iteradores al mínimo y máximo del rango simultáneamente.

std::vector<int> v = {7, 2, 9, 4};
auto res = std::minmax_element(v.begin(), v.end());
// res.first apunta a 2, res.second apunta a 9

6. Algoritmos Numéricos (<numeric>)

6.1 accumulate

Calcula la suma (u otra operación binaria) de los elementos en un rango.

#include <numeric>

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

6.2 inner_product

Calcula el producto punto de dos rangos.

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

6.3 iota

Llena el rango con valores consecutivos crecientes.

std::vector<int> v(5);
std::iota(v.begin(), v.end(), 5); // v: {5, 6, 7, 8, 9}

6.4 partial_sum

Calcula las sumas parciales y las almacena en otro rango.

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

6.5 adjacent_difference

Calcula las diferencias entre elementos adyacentes.

std::vector<int> origen = {10, 11, 13, 16};
std::vector<int> destino(4);
std::adjacent_difference(origen.begin(), origen.end(), destino.begin()); // destino: {10, 1, 2, 3}

7. Otros Algoritmos

7.1 generate y generate_n

Llenan un rango usando una función generadora.

std::vector<int> v1(4);
int base = 1;
std::generate(v1.begin(), v1.end(), [&base]() { return base *= 2; }); // v1: {2, 4, 8, 16}

std::vector<int> v2(5, 0);
int idx = 100;
std::generate_n(v2.begin(), 3, [&idx]() { return idx--; }); // v2: {100, 99, 98, 0, 0}

7.2 includes

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

std::vector<int> conjuntoA = {10, 20, 30, 40, 50};
std::vector<int> conjuntoB = {20, 40};
bool contiene = std::includes(conjuntoA.begin(), conjuntoA.end(), conjuntoB.begin(), conjuntoB.end()); // true

7.3 Operaciones de Conjuntos

Permiten realizar uniones, intersecciones, diferencias y diferencias simétricas sobre rangos ordenados.

std::vector<int> A = {10, 20, 30};
std::vector<int> B = {30, 40, 50};
std::vector<int> res;

// Unión
std::set_union(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res)); // res: {10, 20, 30, 40, 50}

// Intersección
res.clear();
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res)); // res: {30}

// Diferencia (A - B)
res.clear();
std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res)); // res: {10, 20}

// Diferencia Simétrica
res.clear();
std::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(res)); // res: {10, 20, 40, 50}

8. Preguntas Frecuentes

1. ¿Cuál es la diferencia entre sort y stable_sort?
sort utiliza introsort, el cual es inestable (puede alterar el orden relativo de elementos equivalentes) y tiene complejidad O(n log n). stable_sort emplea mergesort, siendo estable pero consumiendo más memoria.

2. ¿Por qué remove debe usarse con erase?
El algoritmo remove sobrescribe los elementos a conservar desplazándolos hacia el inicio, y devuelve un iterador al nuevo límite lógico, pero no altera el tamaño real del contenedor. erase se encarga de eliminar físicamente los elementos sobrantes desde ese iterador hasta el final, ajustando el tamaño.

3. ¿Qué algoritmos requieren rangos ordenados?
Los algoritmos de búsqueda binaria (binary_search, lower_bound, upper_bound), las operaciones de conjuntos (set_union, set_intersection, etc.) y merge. Requieren orden para lograr complejidades logarítmicas o lineales.