Algoritmos de la STL

Parte de la sección Programación Orientada a Objetos del Journey de C++ de Coddy — lección 73 de 104.

Los algoritmos de la STL son funciones de plantilla que operan sobre rangos definidos por iteradores. Se encuentran en las cabeceras <algorithm> y <numeric> y funcionan con cualquier contenedor que proporcione iteradores compatibles.

std::sort ordena los elementos en orden ascendente por defecto:

#include <algorithm>
#include <vector>

std::vector<int> nums = {5, 2, 8, 1};
std::sort(nums.begin(), nums.end());
// nums: {1, 2, 5, 8}

std::find busca un valor y devuelve un iterador a la primera coincidencia, o end() si no se encuentra:

auto it = std::find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    std::cout << "Found at index: " << (it - nums.begin());
}

std::transform aplica una operación a cada elemento y almacena los resultados en un rango de destino:

std::vector<int> doubled(nums.size());
std::transform(nums.begin(), nums.end(), doubled.begin(),
               [](int x) { return x * 2; });
// doubled: {2, 4, 10, 16}

std::accumulate de <numeric> combina todos los elementos en un solo valor:

#include <numeric>

int sum = std::accumulate(nums.begin(), nums.end(), 0);
// sum: 16 (1 + 2 + 5 + 8)

Estos algoritmos aceptan rangos de iteradores en lugar de contenedores directamente, lo que los hace lo suficientemente flexibles como para trabajar con rangos parciales o diferentes tipos de contenedores con el mismo código.

Desafío

Fácil

Vamos a construir un analizador de puntajes que procesa una colección de números utilizando algoritmos de la STL. Crearás funciones de utilidad que demuestran cómo sort, find, transform y accumulate trabajan juntos para analizar datos.

Organizarás tu código en dos archivos:

ScoreAnalyzer.h: Define funciones de utilidad que utilizan algoritmos de la STL para procesar vectores de enteros.
Crea una función llamada sortScores que reciba un std::vector<int>& y lo ordene de forma ascendente utilizando std::sort.

Crea una función llamada findScore que reciba un const std::vector<int>& y un valor objetivo int. Usa std::find para buscar el objetivo. Si se encuentra, devuelve el índice (distancia desde el inicio). Si no se encuentra, devuelve -1.

Crea una función llamada applyBonus que reciba un const std::vector<int>& y una cantidad de bono int. Usa std::transform para crear y devolver un nuevo vector donde a cada puntaje se le haya sumado el bono.

Crea una función llamada calculateAverage que reciba un const std::vector<int>& y devuelva el promedio como un double. Usa std::accumulate para calcular la suma y luego divídela por el tamaño.

Crea una función llamada printVector que reciba un const std::vector<int>& e imprima todos los elementos separados por espacios, seguidos de un salto de línea.
main.cpp: Lee seis entradas (cada una en una línea separada):
1. Primer puntaje (entero)
2. Segundo puntaje (entero)
3. Tercer puntaje (entero)
4. Cuarto puntaje (entero)
5. Un puntaje para buscar (entero)
6. Una cantidad de bono a aplicar (entero)
Crea un vector con los cuatro puntajes y demuestra los algoritmos:
1. Imprime Original: seguido del contenido del vector
2. Ordena los puntajes e imprime Sorted: seguido del vector ordenado
3. Busca el puntaje objetivo en el vector ordenado. Si se encuentra, imprime Found <value> at index <index>. Si no se encuentra, imprime <value> not found
4. Aplica el bono a los puntajes ordenados e imprime With bonus: seguido del nuevo vector
5. Calcula e imprime el promedio de los puntajes ordenados originales (antes del bono) como Average: <value> con un decimal

Por ejemplo, con las entradas 75, 90, 60, 85, 85 y 5:

Original: 75 90 60 85 
Sorted: 60 75 85 90 
Found 85 at index 2
With bonus: 65 80 90 95 
Average: 77.5

Con las entradas 100, 80, 95, 70, 50 y 10:

Original: 100 80 95 70 
Sorted: 70 80 95 100 
50 not found
With bonus: 80 90 105 110 
Average: 86.2

Recuerda incluir <algorithm> para sort, find y transform, y <numeric> para accumulate. Usa std::fixed y std::setprecision(1) de <iomanip> para dar formato al promedio.

Hoja de referencia

Los algoritmos de la STL son funciones de plantilla de <algorithm> y <numeric> que operan en rangos definidos por iteradores.

std::sort organiza los elementos en orden ascendente:

#include <algorithm>
#include <vector>

std::vector<int> nums = {5, 2, 8, 1};
std::sort(nums.begin(), nums.end());
// nums: {1, 2, 5, 8}

std::find busca un valor y devuelve un iterador a la primera coincidencia, o end() si no se encuentra:

auto it = std::find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    std::cout << "Found at index: " << (it - nums.begin());
}

std::transform aplica una operación a cada elemento y almacena los resultados en un rango de destino:

std::vector<int> doubled(nums.size());
std::transform(nums.begin(), nums.end(), doubled.begin(),
               [](int x) { return x * 2; });
// doubled: {2, 4, 10, 16}

std::accumulate de <numeric> combina todos los elementos en un solo valor:

#include <numeric>

int sum = std::accumulate(nums.begin(), nums.end(), 0);
// sum: 16 (1 + 2 + 5 + 8)

Estos algoritmos funcionan con rangos de iteradores, lo que los hace flexibles para rangos parciales o diferentes tipos de contenedores.

Pruébalo tú mismo

#include <iostream>
#include <vector>
#include <iomanip>
#include "ScoreAnalyzer.h"

using namespace std;

int main() {
    // Lee seis entradas
    int score1, score2, score3, score4;
    int searchTarget, bonusAmount;
    
    cin >> score1;
    cin >> score2;
    cin >> score3;
    cin >> score4;
    cin >> searchTarget;
    cin >> bonusAmount;
    
    // TODO: Crea un vector con las cuatro puntuaciones
    
    // TODO: Imprime "Original:" seguido del contenido del vector
    
    // TODO: Ordena las puntuaciones e imprime "Sorted:" seguido del vector ordenado
    
    // TODO: Busca la puntuación objetivo en el vector ordenado
    // Si se encuentra, imprime "Found <value> at index <index>"
    // Si no se encuentra, imprime "<value> not found"
    
    // TODO: Aplica el bono a las puntuaciones ordenadas e imprime "With bonus:" seguido del nuevo vector
    
    // TODO: Calcula e imprime el promedio de las puntuaciones ordenadas (antes del bono)
    // Usa fixed y setprecision(1) para el formato
    // Imprime como "Average: <value>"
    
    return 0;
}