Algoritmos de Búsqueda y Consulta

En lugar de alterar los elementos, estas funciones inspeccionan los contenedores sin modificar su contenido.

Búsqueda de Elementos

Para localizar elementos específicos o subsecuencias:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> data = {10, 30, 50, 70, 90};

    // Localizar un valor exacto
    auto pos = std::find(data.begin(), data.end(), 50);
    if (pos != data.end()) {
        std::cout << "Valor hallado: " << *pos << "\n";
    }

    // Localizar basado en una condición
    auto cond_pos = std::find_if(data.begin(), data.end(), [](int val) {
        return val > 60;
    });
    std::cout << "Primer valor mayor a 60: " << *cond_pos << "\n";

    // Búsqueda de subsecuencias
    std::vector<int> pattern = {30, 50};
    auto seq_pos = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
    if (seq_pos != data.end()) {
        std::cout << "Subsecuencia inicia en el índice: " << std::distance(data.begin(), seq_pos) << "\n";
    }
    return 0;
}

Conteo de Elementos

std::vector<int> items = {4, 8, 15, 16, 23, 42, 8, 8};
int target_count = std::count(items.begin(), items.end(), 8); // Resultado: 3
int odd_count = std::count_if(items.begin(), items.end(), [](int v) { return v % 2 != 0; }); // Resultado: 2

Iteración con for_each

Aplica una operación sobre cada elemento del rango.

std::vector<double> prices = {1.5, 2.0, 3.5};
std::for_each(prices.begin(), prices.end(), [](double& p) {
    p *= 1.10; // Incrementa en un 10%
});

Comparación de Rangos

Funciones como equal y mismatch permiten evaluar diferencias o similitudes entre secuencias.

std::vector<char> word1 = {'c', 'o', 'd', 'e'};
std::vector<char> word2 = {'c', 'o', 'd', 'e', 'r'};

bool are_same = std::equal(word1.begin(), word1.end(), word2.begin()); 
// true (compara los primeros 4 caracteres)

auto diff = std::mismatch(word1.begin(), word1.end(), word2.begin());
// diff.first apunta al final de word1, diff.second a 'r'

Evlauación de Condiciones

Validar si los elementos cumplen con un predicado específico.

std::vector<int> scores = {85, 90, 92, 88};
bool all_passing = std::all_of(scores.begin(), scores.end(), [](int s){ return s >= 70; }); // true
bool has_perfect = std::any_of(scores.begin(), scores.end(), [](int s){ return s == 100; }); // false
bool no_failing = std::none_of(scores.begin(), scores.end(), [](int s){ return s < 60; }); // true

Algoritmos de Mutación de Secuencias

Estas herramientas alteran directamente el contenido de los contenedores.

Copiado Condicional

std::vector<int> source = {11, 22, 33, 44, 55};
std::vector<int> destination(source.size());

std::copy(source.begin(), source.end(), destination.begin());

std::vector<int> filtered;
std::copy_if(source.begin(), source.end(), std::back_inserter(filtered), [](int n) {
    return n > 30;
}); // filtered contiene {33, 44, 55}

Transformación de Datos

std::vector<int> base = {2, 4, 6};
std::vector<int> doubled(base.size());
std::transform(base.begin(), base.end(), doubled.begin(), [](int x) { return x * 2; });

std::vector<int> offset = {1, 1, 1};
std::vector<int> result(base.size());
std::transform(base.begin(), base.end(), offset.begin(), result.begin(), [](int a, int b) { return a + b; });
// result: {3, 5, 7}

Reemplazo de Valores

Funciones como replace, replace_if y replace_copy permiten sustituir elementos.

std::vector<int> metrics = {10, 20, 30, 20, 50};
std::replace(metrics.begin(), metrics.end(), 20, 99); // {10, 99, 30, 99, 50}

std::vector<int> safe_metrics;
std::replace_copy(metrics.begin(), metrics.end(), std::back_inserter(safe_metrics), 99, 0); 
// safe_metrics: {10, 0, 30, 0, 50}, metrics sin cambios

Eliminación Lógica y Física

Es crucial recordar que std::remove solo reordena los elementos, devolviendo un nuevo iterador final lógico.

std::vector<std::string> names = {"Alice", "Bob", "Charlie", "Bob"};
auto new_logical_end = std::remove(names.begin(), names.end(), "Bob");
names.erase(new_logical_end, names.end()); // names ahora es {"Alice", "Charlie"}

// Eliminar por condición
names = {"A", "B", "C", "D"};
names.erase(std::remove_if(names.begin(), names.end(), [](const std::string& s) {
    return s.length() == 1 && s[0] > 'B';
}), names.end());

Reorganización de Elementos

• std::unique: Elimina duplicados consecutivos. Requiere contenedor ordenado para ser completamente efectivo.
• std::reverse: Invierte el orden.
• std::rotate: Desplaza elementos cíclicamente.

std::vector<int> cycle = {10, 20, 30, 40, 50};
std::rotate(cycle.begin(), cycle.begin() + 3, cycle.end()); 
// cycle se transforma en {40, 50, 10, 20, 30}

Aleatorización

#include <random>
std::vector<int> deck = {1, 2, 3, 4, 5};
std::mt19937 rng(std::random_device{}());
std::shuffle(deck.begin(), deck.end(), rng);

Ordenamiento y Búsqueda Binaria

Algoritmos de Ordenamiento

• std::sort: Ordenamiento rápido (Introsort), inestable.
• std::stable_sort: Mantiene el orden relativo de elementos equivalentes.
• std::partial_sort: Ordena solo un subconjunto inicial.

std::vector<int> unordered = {9, 7, 5, 3, 1, 8, 6, 4, 2};
std::partial_sort(unordered.begin(), unordered.begin() + 4, unordered.end());
// Los primeros 4 elementos son {1, 2, 3, 4}, el resto queda sin orden garantizado

Selección Rápida

std::vector<int> data = {45, 12, 89, 33, 21, 9};
std::nth_element(data.begin(), data.begin() + 2, data.end());
// data[2] es ahora el tercer elemento más pequeño (21), los anteriores son menores o iguales, los posteriores mayores.

Búsqueda en Rangos Ordenados

Requiere contenedores pre-ordenados.

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

bool found = std::binary_search(sorted_data.begin(), sorted_data.end(), 20);
auto first_20 = std::lower_bound(sorted_data.begin(), sorted_data.end(), 20); // Primer 20
auto past_20 = std::upper_bound(sorted_data.begin(), sorted_data.end(), 20); // Primer elemento > 20 (el 30)

Fusión

Combina dos secuencias ordenadas en una tercera.

std::vector<int> left = {2, 4, 6};
std::vector<int> right = {1, 3, 5};
std::vector<int> combined(left.size() + right.size());
std::merge(left.begin(), left.end(), right.begin(), right.end(), combined.begin());
// combined: {1, 2, 3, 4, 5, 6}

Operaciones con Heaps (Montículos)

Permiten gestionar colas de prioridad eficientemente sobre secuencias.

std::vector<int> pq = {15, 5, 20, 10};
std::make_heap(pq.begin(), pq.end()); // pq: {20, 10, 15, 5}

pq.push_back(25);
std::push_heap(pq.begin(), pq.end()); // 25 se convierte en la raíz

std::pop_heap(pq.begin(), pq.end()); // Mueve 25 al final
int top = pq.back();
pq.pop_back(); // Remueve 25

Extremos y Valores Mínimos/Máximos

Encontrar límites en rangos o conjuntos de datos.

std::vector<int> temps = {-5, 12, 28, 3, 19};
auto extremes = std::minmax_element(temps.begin(), temps.end());
// extremes.first apunta a -5, extremes.second apunta a 28

Algoritmos Numéricos (Biblioteca <numeric>)

Cálculos matemáticos sobre rangos.

#include <numeric>

std::vector<int> series = {1, 2, 3, 4, 5};
int total_sum = std::accumulate(series.begin(), series.end(), 0); // 15

std::vector<int> weights = {1, 2, 3};
std::vector<int> values = {10, 20, 30};
int dot_product = std::inner_product(weights.begin(), weights.end(), values.begin(), 0); // 140

std::vector<int> seq(5);
std::iota(seq.begin(), seq.end(), 100); // {100, 101, 102, 103, 104}

std::vector<int> diffs(5);
std::adjacent_difference(series.begin(), series.end(), diffs.begin()); // {1, 1, 1, 1, 1}

Generación y Operaciones de Conjuntos

Llenado Dinámico

std::vector<int> ids(5);
int current_id = 1000;
std::generate(ids.begin(), ids.end(), [&current_id]() { return current_id++; });

Validación de Subconjuntos

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

Álgebra de Conjuntos

Todos requieren rangos ordenados.

std::vector<int> set_a = {1, 3, 5, 7};
std::vector<int> set_b = {2, 3, 6, 7};
std::vector<int> intersection;

std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(intersection));
// intersection: {3, 7}

Dudas Comunes sobre la STL

¿Cuándo usar stable_sort en lugar de sort?

Cuando la estabilidad es un requisito, es decir, cuando elementos con el mismo valor deben conservar su orden original relativo. stable_sort garantiza esto, aunque generalmente requiere memoria adicional O(N), mientras que sort opera en O(log N) de memoria extra.

El idiom Erase-Remove

Los algoritmos como std::remove no pueden alterar el tamaño del contenedor subyacente. Por ello, solo compactan los elementos a conservar al inicio y devuelven un iterador al nuevo final lógico. Es obligatorio invocar al método erase del contenedor pasando este iterador y el end() original para ajustar el tamaño físico de la estructura de datos.

Requisito de Ordenamiento Previo

Cualquier función que aplique búsqueda binaria (como binary_search, lower_bound, equal_range) o álgebra de conjuntos (set_union, set_difference) asume que el rango de entrada está ordenado según el criterio de comparación proporcionado (o std::less por defecto). Proveer datos no ordenados resultará en un comportamiento indefinido o resultados incorrectos.