Dominio de algoritmos de transformación y modificación

Tabla de contenido

Los algoritmos de la biblioteca <algorithm> son implementaciones altamente optimizadas para operar sobre rangos definidos por iteradores. Cuando utilizas std::sort, no estás ejecutando un simple Quicksort; la mayoría de las implementaciones modernas utilizan Introsort [C++98], un algoritmo híbrido que comienza con Quicksort pero cambia a Heapsort si la profundidad de la recursión excede un límite, evitando así el caso degenerado de $O(N^2)$. Si necesitas mantener el orden relativo de elementos que tu comparador considera “iguales”, debes usar std::stable_sort, el cual garantiza estabilidad a cambio de utilizar memoria adicional para permitir una variante de Merge Sort optimizada.

Para transformar datos, std::transform actúa como una función de mapeo que aplica un operador a cada elemento de un rango de entrada y deposita el resultado en un rango de salida. Si solo buscas iterar para aplicar efectos secundarios (como imprimir o modificar elementos in-place), std::for_each es la opción semántica correcta. Para la gestión de subconjuntos, std::copy_if filtra elementos basados en un predicado, mientras que std::move permite transferir la propiedad de los objetos (usando semántica de movimiento [C++11]) hacia un nuevo contenedor, evitando copias profundas costosas.

Debes usar estos algoritmos siempre que trabajes con contenedores estándar; reimplementar bucles for para estas tareas no solo es redundante, sino que suele ser menos eficiente que las implementaciones de la STL, que a menudo utilizan técnicas de vectorización (SIMD) o des-rolleo de bucles. Si los usas mal, especialmente al proporcionar comparadores que violan la Strict Weak Ordering, podrías provocar comportamientos indefinidos (UB) que el compilador no detectará, pero que causarán un crash o corrupción de memoria en producción.

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <iterator>
#include <vector>

struct Tick {
    std::string symbol;
    double price;

    // Para que std::replace funcione con el valor exacto
    bool operator==(const Tick&) const = default; 
};

int main() {
    // 1. Generación y llenado inicial
    std::vector<Tick> market_data;
    market_data.reserve(6);
    std::vector<std::string> symbols = {"AAPL", "MSFT", "GOOG", "AAPL", "TSLA", "MSFT"};
    
    // std::generate para llenar con datos iniciales (simulado)
    std::generate(symbols.begin(), symbols.end(), []() { return "SYM"; }); 
    // Usaremos un enfoque más manual para el ejemplo para tener datos reales
    market_data = {{"AAPL", 150.0}, {"MSFT", 300.0}, {"GOOG", 2800.0}, {"AAPL", 150.0}, {"TSLA", 700.0}, {"MSFT", 300.0}};

    // 2. std::sort (no estable): Ordenar por precio descendente
    // Introsort garantiza O(N log N) incluso en el peor caso.
    std::sort(market_data.begin(), market_data.end(), [](const Tick& a, const Tick& b) {
        return a.price > b.price;
    });

    // 3. std::stable_sort: Ordenar por símbolo manteniendo el orden de precio actual
    // Útil para jerarquías de ordenación múltiples.
    std::stable_sort(market_data.begin(), market_data.end(), [](const Tick& a, const Tick& b) {
        return a.symbol < b.symbol;
    });

    // 4. std::transform: Aplicar un impuesto del 2% a los precios
    std::vector<double> taxed_prices(market_data.size());
    std::transform(market_data.begin(), market_data.end(), taxed_prices.begin(), 
                   [](const Tick& t) { return t.price * 1.02; });

    // 5. std::copy_if: Filtrar solo activos con precio > 500.0
    std::vector<Tick> expensive_assets;
    std::copy_if(market_data.begin(), market_data.end(), std::back_inserter(expensive_assets),
                 [](const Tick& t) { return t.price > 500.0; });

    // 6. std::replace: Corregir un símbolo erróneo
    // (Requiere C++20 para operator== default)
    std::replace(market_data.begin(), market_data.end(), Tick{"AAPL", 150.0}, Tick{"APPLE", 150.0});

    // 7. std::reverse y std::rotate: Manipulación de la ventana de tiempo
    std::reverse(market_data.begin(), market_data.end()); // Invertir todo
    std::rotate(market_data.begin(), market_data.begin() + 1, market_data.end()); // Mover el primero al final

    // 8. std::move: Transferir datos a un contenedor de procesamiento final
    std::vector<Tick> final_buffer;
    std::move(market_data.begin(), market_data.end(), std::back_inserter(final_buffer));

    // 9. std::fill y std::generate para limpieza/inicialización
    std::vector<int> status_flags(5);
    std::fill(status_flags.begin(), status_flags.end(), 0); // Llenar con ceros
    std::generate(status_flags.begin(), status_flags.end(), []() { return rand() % 100; });

    // 10. std::for_each para salida
    std::cout << "Datos procesados:\n";
    std::for_each(final_buffer.begin(), final_buffer.end(), [](const Tick& t) {
        std::cout << " - " << t.symbol << ": " << t.price << "\n";
    });

    return 0;
}

Desglose del ejemplo

std::sort y std::stable_sort: En market_data, primero usamos std::sort para organizar los Tick por precio. Como std::sort no es estable, si dos AAPL tienen el mismo precio, su orden relativo puede cambiar. Al aplicar std::stable_sort posteriormente por symbol, nos aseguramos de que los elementos con el mismo símbolo mantengan su ordenación previa de precio, permitiendo crear índices jerárquicos.
std::transform: Esta función toma el rango de market_data y extrae únicamente el double del precio, aplicándole un factor de 1.02. El resultado se escribe en taxed_prices. A diferencia de un bucle for manual, std::transform deja claro la intención de “mapear” un conjunto a otro.
std::copy_if y std::back_inserter: std::copy_if no puede redimensionar un contenedor automáticamente. Usamos std::back_inserter para llamar a push_back en cada elemento que cumpla el predicado (precio > 500.0), permitiendo que expensive_assets crezca dinámicamente.
std::rotate: La operación std::rotate(market_data.begin(), market_data.begin() + 1, market_data.end()) toma el segundo elemento y lo convierte en el primero, desplazando el resto hacia la derecha y enviando el antiguo primero al final del rango. Es una operación lineal $O(N)$.
std::move: Al usar std::move con std::back_inserter, estamos transfiriendo los recursos de los std::string dentro de los Tick desde market_data hacia final_buffer. Esto es crucial para el rendimiento cuando los objetos contienen punteros a memoria heap, ya que evitamos copiar las cadenas de texto.

El error frecuente

Un error clásico al usar std::sort es proporcionar un comparador que no cumple con la Strict Weak Ordering (Orden Débil Estricto).

// ERROR: Esto causará Comportamiento Indefinido (UB)
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b; // ERROR: Debe ser estrictamente '<'
});

Si utilizas <= en lugar de <, el algoritmo puede entrar en un bucle infinito o acceder a memoria fuera de los límites del contenedor. Esto ocurre porque std::sort busca un punto de corte donde !(a < b) y !(b < a) sea cierto para identificar elementos equivalentes. Si defines que a <= b es cierto, la condición de “equivalencia” se vuelve inconsistente para el algoritmo, rompiendo la lógica de partición de Quicksort/Introsort. El compilador podría no avisarte, pero AddressSanitizer detectará el acceso ilegal a la memoria durante la ejecución.

N° 72

Desglose del ejemplo

El error frecuente

Entradas relacionadas

Dejar un comentario Cancelar respuesta