Algoritmos da STL

Parte da seção Programação Orientada a Objetos do Journey de C++ da Coddy — lição 73 de 104.

Os algoritmos da STL são funções template que operam em intervalos definidos por iteradores. Eles são encontrados nos cabeçalhos <algorithm> e <numeric> e funcionam com qualquer contêiner que forneça iteradores compatíveis.

std::sort organiza os elementos em ordem crescente por padrão:

#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 procura por um valor e retorna um iterador para a primeira correspondência, ou end() se não for encontrado:

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

std::transform aplica uma operação a cada elemento e armazena os resultados em um intervalo 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 os elementos em um único valor:

#include <numeric>

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

Estes algoritmos aceitam intervalos de iteradores em vez de contêineres diretamente, tornando-os flexíveis o suficiente para trabalhar em intervalos parciais ou diferentes tipos de contêineres com o mesmo código.

Desafio

Fácil

Vamos construir um analisador de pontuações que processa uma coleção de números usando algoritmos da STL. Você criará funções utilitárias que demonstram como sort, find, transform e accumulate trabalham juntos para analisar dados.

Você organizará seu código em dois arquivos:

ScoreAnalyzer.h: Defina funções utilitárias que usam algoritmos da STL para processar vetores de inteiros.
Crie uma função chamada sortScores que recebe um std::vector<int>& e o ordena em ordem crescente usando std::sort.

Crie uma função chamada findScore que recebe um const std::vector<int>& e um valor alvo int. Use std::find para procurar o alvo. Se encontrado, retorne o índice (distância do início). Se não for encontrado, retorne -1.

Crie uma função chamada applyBonus que recebe um const std::vector<int>& e um valor de bônus int. Use std::transform para criar e retornar um novo vetor onde cada pontuação tem o bônus adicionado a ela.

Crie uma função chamada calculateAverage que recebe um const std::vector<int>& e retorna a média como um double. Use std::accumulate para calcular a soma e, em seguida, divida pelo tamanho.

Crie uma função chamada printVector que recebe um const std::vector<int>& e imprime todos os elementos separados por espaços, seguidos por uma nova linha.
main.cpp: Leia seis entradas (cada uma em uma linha separada):
1. Primeira pontuação (inteiro)
2. Segunda pontuação (inteiro)
3. Terceira pontuação (inteiro)
4. Quarta pontuação (inteiro)
5. Uma pontuação para pesquisar (inteiro)
6. Um valor de bônus para aplicar (inteiro)
Crie um vetor com as quatro pontuações e demonstre os algoritmos:
1. Imprima Original: seguido pelo conteúdo do vetor
2. Ordene as pontuações e imprima Sorted: seguido pelo vetor ordenado
3. Procure pela pontuação alvo no vetor ordenado. Se encontrada, imprima Found <value> at index <index>. Se não for encontrada, imprima <value> not found
4. Aplique o bônus às pontuações ordenadas e imprima With bonus: seguido pelo novo vetor
5. Calcule e imprima a média das pontuações ordenadas originais (antes do bônus) como Average: <value> com uma casa decimal

Por exemplo, com as entradas 75, 90, 60, 85, 85 e 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

Com as entradas 100, 80, 95, 70, 50 e 10:

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

Lembre-se de incluir <algorithm> para sort, find e transform, e <numeric> para accumulate. Use std::fixed e std::setprecision(1) de <iomanip> para formatar a média.

Folha de consulta

Algoritmos STL são funções de template de <algorithm> e <numeric> que operam em intervalos definidos por iteradores.

std::sort organiza os elementos em ordem crescente:

#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 procura por um valor e retorna um iterador para a primeira correspondência, ou end() se não for encontrado:

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

std::transform aplica uma operação a cada elemento e armazena os resultados em um intervalo 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 os elementos em um único valor:

#include <numeric>

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

Esses algoritmos funcionam com intervalos de iteradores, tornando-os flexíveis para intervalos parciais ou diferentes tipos de contêineres.

Experimente você mesmo

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

using namespace std;

int main() {
    // Lê seis entradas
    int score1, score2, score3, score4;
    int searchTarget, bonusAmount;
    
    cin >> score1;
    cin >> score2;
    cin >> score3;
    cin >> score4;
    cin >> searchTarget;
    cin >> bonusAmount;
    
    // TODO: Cria um vector com as quatro pontuações
    
    // TODO: Imprime "Original:" seguido pelo conteúdo do vector
    
    // TODO: Ordena as pontuações e imprime "Sorted:" seguido pelo vector ordenado
    
    // TODO: Procura pela pontuação alvo no vector ordenado
    // Se encontrada, imprime "Found <value> at index <index>"
    // Se não encontrada, imprime "<value> not found"
    
    // TODO: Aplica o bônus às pontuações ordenadas e imprime "With bonus:" seguido pelo novo vector
    
    // TODO: Calcula e imprime a média das pontuações ordenadas (antes do bônus)
    // Usa fixed e setprecision(1) para formatação
    // Imprime como "Average: <value>"
    
    return 0;
}