1. Algoritmos de Secuencia No Modificadores

Estos algoritmos no alteran los elementos en los contenedores que operan.

1.1 Búsqueda con find y find_if

La función find(inicio, fin, valor) localiza el primer elemento que coincide con el valor dado, devolviendo un iterador (o el iterador fin si no se encuentra). La variante find_if(inicio, fin, predicado) busca el primer elemento que cumple con una condición específica. Para localizar la última aparición de una subsecuencia, se utiliza find_end(inicio, fin, sub_inicio, sub_fin).

vector<int> datos = {1, 3, 5, 7, 9};
auto pos = find(datos.begin(), datos.end(), 5);
if (pos != datos.end()) {
    cout << "Hallado: " << *pos << endl; // Muestra 5
}

auto mayor = find_if(datos.begin(), datos.end(), [](int n) {
    return n > 6;
});
cout << "Primer mayor a 6: " << *mayor << endl; // Muestra 7

vector<int> patron = {3, 5};
auto inicio_sub = find_end(datos.begin(), datos.end(), patron.begin(), patron.end());
if (inicio_sub != datos.end()) {
    cout << "La subsecuencia comienza en índice: " << inicio_sub - datos.begin() << endl; // Muestra 1
}</int></int>

1.2 Conteo con count y count_if

count(inicio, fin, valor) devuelve el número de elementos iguales al valor proporcionado. count_if(inicio, fin, predicado) cuenta los elementos que satisfacen el predicado.

vector<int> coleccion = {1, 2, 3, 2, 4, 2};
int total_dos = count(coleccion.begin(), coleccion.end(), 2); // Resultado: 3
int pares = count_if(coleccion.begin(), coleccion.end(), [](int x) {
    return x % 2 == 0;
}); // Resultado: 4</int>

1.3 Aplicación con for_each

Este algoritmo aplica una función a cada elemento en un rango dado.

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

1.4 Comparación con equal y mismatch

equal(inicio1, fin1, inicio2) determina si dos rangos son idénticos. mismatch(inicio1, fin1, inicio2) retorna un par de iteradores apuntando al primer desacuerdo.

vector<int> conjunto_a = {1, 2, 3};
vector<int> conjunto_b = {1, 2, 4};
vector<int> conjunto_c = {1, 2, 3, 4};

bool iguales = equal(conjunto_a.begin(), conjunto_a.end(), conjunto_b.begin());
cout << "¿conjunto_a == conjunto_b? " << boolalpha << iguales << endl; // false

auto discrepancia = mismatch(conjunto_a.begin(), conjunto_a.end(), conjunto_c.begin());
if (discrepancia.first != conjunto_a.end()) {
    cout << "Diferencia: " << *discrepancia.first << " vs " << *discrepancia.second << endl;
}</int></int></int>

1.5 Verificaciones con all_of, any_of, none_of

Estas funciones comprueban si todos, alguno o ningún elemento de un rango cumplen una condición.

vector<int> valores = {2, 4, 6, 8};
bool todos_pares = all_of(valores.begin(), valores.end(), [](int v) {
    return v % 2 == 0;
}); // true
bool hay_impares = any_of(valores.begin(), valores.end(), [](int v) {
    return v % 2 != 0;
}); // false
bool sin_negativos = none_of(valores.begin(), valores.end(), [](int v) {
    return v < 0;
}); // true</int>

2. Algoritmos de Secuencia Modificadores

Estos algoritmos modifican los elementos de los contenedores.

2.1 Copia con copy y copy_if

copy(inicio, fin, destino) copia los elementos al destino. copy_if(inicio, fin, destino, predicado) solo copia los que cumplen la condición. Es común usar back_inserter para evitar preasignar espacio.

vector<int> original = {1, 2, 3, 4, 5};
vector<int> copia(5);
copy(original.begin(), original.end(), copia.begin());

vector<int> solo_pares;
copy_if(original.begin(), original.end(), back_inserter(solo_pares), [](int num) {
    return num % 2 == 0;
}); // solo_pares: [2, 4]</int></int></int>

2.2 Transformación con transform

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

vector<int> entradas = {1, 2, 3};
vector<int> cuadrados(3);
transform(entradas.begin(), entradas.end(), cuadrados.begin(), [](int x) {
    return x * x;
}); // cuadrados: [1, 4, 9]

vector<int> primer_termino = {1, 2, 3};
vector<int> segundo_termino = {4, 5, 6};
vector<int> suma(3);
transform(primer_termino.begin(), primer_termino.end(), segundo_termino.begin(), suma.begin(), [](int a, int b) {
    return a + b;
}); // suma: [5, 7, 9]</int></int></int></int></int>

2.3 Reemplazo con replace, replace_if y replace_copy

replace cambia todas las ocurrencias de un valor. replace_if reemplaza según una condición. replace_copy crea una copia con los reemplazos sin modificar el original.

vector<int> secuencia = {1, 2, 3, 2, 5};
replace(secuencia.begin(), secuencia.end(), 2, 20); // [1, 20, 3, 20, 5]

replace_if(secuencia.begin(), secuencia.end(), [](int x) {
    return x > 10;
}, 0); // [1, 0, 3, 0, 5]

vector<int> copia_reemplazada;
replace_copy(secuencia.begin(), secuencia.end(), back_inserter(copia_reemplazada), 3, 300); // [1, 0, 300, 0, 5]</int></int>

2.4 Eliminación con remove, remove_if y erase

remove y remove_if no eliminan físicamente los elementos, sino que los mueven al final y devuelven un iterador al nuevo final lógico. Para eliminar realmente, se debe combinar con erase.

vector<int> elementos = {1, 2, 3, 2, 4};
auto nuevo_fin = remove(elementos.begin(), elementos.end(), 2); // [1, 3, 4, 2, 2]
elementos.erase(nuevo_fin, elementos.end()); // [1, 3, 4]

elementos = {1, 2, 3, 4, 5};
elementos.erase(remove_if(elementos.begin(), elementos.end(), [](int e) {
    return e % 2 == 0;
}), elementos.end()); // [1, 3, 5]</int>

2.5 Eliminación de duplicados con unique

Elimina elementos duplicados consecutivos. Se suele usar en contenedores ordenados y junto con erase.

vector<int> con_duplicados = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto final_unico = unique(con_duplicados.begin(), con_duplicados.end());
con_duplicados.erase(final_unico, con_duplicados.end()); // {1, 2, 3, 4, 5}</int>

2.6 Inversión con reverse

Invierte el orden de los elementos en un rango.

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

2.7 Rotación con rotate

Rota los elementos de modo que un elemento intermedio se convierte en el primero.

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

2.8 Aleatorización con shuffle (C++11)

Reordena los elementos aleatoriamente. Requiere un generador de números aleatorios.

#include <random>
#include <algorithm>

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

3. Algoritmos de Ordenación y Relacionados

3.1 Ordenación con sort, stable_sort y partial_sort

sort ordena generalmente con una complejidad O(n log n) pero es inestable. stable_sort mantiene el orden relativo de elementos iguales. partial_sort ordena solo los primeros m elementos más pequeños.

vector<int> desordenado = {5, 3, 1, 4, 2};
sort(desordenado.begin(), desordenado.end()); // {1, 2, 3, 4, 5}
sort(desordenado.begin(), desordenado.end(), greater<int>()); // {5, 4, 3, 2, 1}

vector<pair<int, string>> registros = {{2, "beta"}, {1, "alfa"}, {2, "gama"}, {1, "delta"}};
stable_sort(registros.begin(), registros.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // Mantiene el orden de inserción para llaves iguales
});

vector<int> para_parcial = {5, 3, 1, 4, 2, 6};
partial_sort(para_parcial.begin(), para_parcial.begin() + 3, para_parcial.end()); // Los 3 menores: 1, 2, 3</int>

3.2 Partición con nth_element

Reorganiza los elementos de modo que el elemento en la posición n-ésima es el que estaría allí en una secuencia totalmente ordenada.

vector<int> muestra = {5, 3, 1, 4, 2, 6};
nth_element(muestra.begin(), muestra.begin() + 2, muestra.end()); // El tercer elemento más pequeño (índice 2) es 3</int>

3.3 Búsqueda binaria (requiere contenedor ordenado)

binary_search verifica la existencia de un valor. lower_bound y upper_bound devuelven iteradores a posiciones clave.

vector<int> ordenado = {1, 3, 3, 5, 7};
bool existe = binary_search(ordenado.begin(), ordenado.end(), 3); // true

auto primer_mayor_igual = lower_bound(ordenado.begin(), ordenado.end(), 3); // Apunta al primer 3
auto primer_mayor = upper_bound(ordenado.begin(), ordenado.end(), 3); // Apunta al 5</int>

3.4 Fusión con merge

Combina dos rangos ordenados en un tercero, manteniendo el orden.

vector<int> lista_a = {1, 3, 5};
vector<int> lista_b = {2, 4, 6};
vector<int> fusionada(lista_a.size() + lista_b.size());
merge(lista_a.begin(), lista_a.end(), lista_b.begin(), lista_b.end(), fusionada.begin()); // {1, 2, 3, 4, 5, 6}</int></int></int>

4. Algoritmos de Montículo (Heap)

Estos algoritmos tratan un rango como un montículo (heap) y permiten su manipulación.

vector<int> heap_datos = {4, 1, 3, 2, 5};
make_heap(heap_datos.begin(), heap_datos.end()); // Crea un montículo máximo: {5, 4, 3, 2, 1}

heap_datos.push_back(6);
push_heap(heap_datos.begin(), heap_datos.end()); // Incorpora el 6: {6, 4, 5, 2, 1, 3}

pop_heap(heap_datos.begin(), heap_datos.end()); // Mueve el máximo al final: {5, 4, 3, 2, 1, 6}
int maximo = heap_datos.back();
heap_datos.pop_back();

sort_heap(heap_datos.begin(), heap_datos.end()); // Ordena el montículo: {1, 2, 3, 4, 5}</int>

5. Algoritmos de Mínimo y Máximo

5.1 min y max

Retornan el mínimo o máximo entre dos valores o de una lista de inicialización.

int valor_a = 5, valor_b = 3;
int menor = min(valor_a, valor_b); // 3
int mayor = max(valor_a, valor_b); // 5

auto menor_de_lista = min({4, 2, 8, 5, 1}); // 1

5.2 min_element y max_element

Retornan iteradores al menor y mayor elemento de un rango.

vector<int> conjunto = {3, 1, 4, 2, 5};
auto it_min = min_element(conjunto.begin(), conjunto.end()); // Apunta al 1
auto it_max = max_element(conjunto.begin(), conjunto.end()); // Apunta al 5</int>

5.3 minmax_element (C++11)

Retorna un par con los iteradores al mínimo y al máximo.

vector<int> datos_mixtos = {3, 1, 4, 2, 5};
auto par_minmax = minmax_element(datos_mixtos.begin(), datos_mixtos.end());
// par_minmax.first -> 1, par_minmax.second -> 5</int>

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

6.1 accumulate

Calcula la suma acumulada o aplica una operación binaria sucesiva.

#include <numeric>

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

6.2 inner_product

Calcula el producto interior (dot product) de dos rangos.

vector<int> v1 = {1, 2, 3};
vector<int> v2 = {4, 5, 6};
int producto_escalar = inner_product(v1.begin(), v1.end(), v2.begin(), 0); // 1*4 + 2*5 + 3*6 = 32</int></int>

6.3 iota

Rellena un rango con valores consecutivos incrementados.

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

6.4 partial_sum

Calcula la suma parcial de los elementos.

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

6.5 adjacent_difference

Calcula la diferencia entre elementos adyacentes.

vector<int> serie_original = {1, 2, 3, 4, 5};
vector<int> diferencias(serie_original.size());
adjacent_difference(serie_original.begin(), serie_original.end(), diferencias.begin()); // {1, 1, 1, 1, 1}</int></int>

7. Otros Algoritmos Útiles

7.1 generate y generate_n

generate rellena un rango usando una función. generate_n rellena los primeros n elementos.

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

vector<int> otro_contenedor(5);
int inicio = 10;
generate_n(otro_contenedor.begin(), 3, [&inicio]() {
    return inicio++;
}); // Los primeros 3: 10, 11, 12</int></int>

7.2 includes

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

vector<int> universo = {1, 2, 3, 4, 5};
vector<int> subconjunto = {2, 4};
bool contenido = includes(universo.begin(), universo.end(), subconjunto.begin(), subconjunto.end()); // true</int>

7.3 Algoritmos de Conjuntos

Realizan operaciones teóricas de conjuntos en rangos ordenados: unión, intersección, diferencia y diferencia simétrica.

vector<int> conjunto_a = {1, 2, 3, 4, 5};
vector<int> conjunto_b = {3, 4, 5, 6, 7};
vector<int> resultado;

set_union(conjunto_a.begin(), conjunto_a.end(), conjunto_b.begin(), conjunto_b.end(), back_inserter(resultado));
// resultado: {1, 2, 3, 4, 5, 6, 7}

resultado.clear();
set_intersection(conjunto_a.begin(), conjunto_a.end(), conjunto_b.begin(), conjunto_b.end(), back_inserter(resultado));
// resultado: {3, 4, 5}

resultado.clear();
set_difference(conjunto_a.begin(), conjunto_a.end(), conjunto_b.begin(), conjunto_b.end(), back_inserter(resultado));
// resultado: {1, 2}

resultado.clear();
set_symmetric_difference(conjunto_a.begin(), conjunto_a.end(), conjunto_b.begin(), conjunto_b.end(), back_inserter(resultado));
// resultado: {1, 2, 6, 7}</int></int></int>

8. Preguntas Comunes

1. ¿Cuál es la diferencia entre sort y stable_sort?
   sort utiliza generalmente una variación de quicksort (introsort) y es inestable. stable_sort (típicamente mergesort) es estable y preserva el orden relativo de elementos iguales, a costa de mayor uso de memoria.
2. ¿Por qué remove debe combinarse con erase?
   remove no cambia el tamaño del contenedor; solo desplaza los elementos no eliminados al inicio y devuelve un iterador al nuevo final lógico. erase es quien realmente reduce el tamaño del contanedor al descartar el rango final.
3. ¿Qué algoritmos requieren un contenedor ordenado?
   Los algoritmos de búsqueda binaria (binary_search, lower_bound, upper_bound), los algoritmos de conjuntos (set_union, etc.) y merge dependen de la propiedad de orden para funcionar correctamente y eficientemente.