Algorithmes de la STL

Fait partie de la section Programmation Orientée Objet du Journey C++ de Coddy — leçon 73 sur 104.

Les algorithmes de la STL sont des fonctions templates qui opèrent sur des plages définies par des itérateurs. On les trouve dans les en-têtes <algorithm> et <numeric> et ils fonctionnent avec n'importe quel conteneur fournissant des itérateurs compatibles.

std::sort organise les éléments par ordre croissant par défaut :

#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 recherche une valeur et renvoie un itérateur vers la première occurrence, ou end() si elle n'est pas trouvée :

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

std::transform applique une opération à chaque élément et stocke les résultats dans une plage de destination :

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> combine tous les éléments en une seule valeur :

#include <numeric>

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

Ces algorithmes acceptent des plages d'itérateurs plutôt que des conteneurs directement, ce qui les rend suffisamment flexibles pour fonctionner sur des plages partielles ou différents types de conteneurs avec le même code.

Défi

Facile

Construisons un analyseur de scores qui traite une collection de nombres en utilisant les algorithmes de la STL. Vous allez créer des fonctions utilitaires qui démontrent comment sort, find, transform, et accumulate travaillent ensemble pour analyser des données.

Vous organiserez votre code sur deux fichiers :

ScoreAnalyzer.h : Définissez des fonctions utilitaires qui utilisent les algorithmes de la STL pour traiter des vecteurs d'entiers.
Créez une fonction appelée sortScores qui prend un std::vector<int>& et le trie par ordre croissant en utilisant std::sort.

Créez une fonction appelée findScore qui prend un const std::vector<int>& et une valeur cible int. Utilisez std::find pour rechercher la cible. Si elle est trouvée, retournez l'index (distance depuis le début). Si elle n'est pas trouvée, retournez -1.

Créez une fonction appelée applyBonus qui prend un const std::vector<int>& et un montant de bonus int. Utilisez std::transform pour créer et retourner un nouveau vecteur où chaque score se voit ajouter le bonus.

Créez une fonction appelée calculateAverage qui prend un const std::vector<int>& et retourne la moyenne sous forme de double. Utilisez std::accumulate pour calculer la somme, puis divisez par la taille.

Créez une fonction appelée printVector qui prend un const std::vector<int>& et affiche tous les éléments séparés par des espaces, suivis d'un saut de ligne.
main.cpp : Lisez six entrées (chacune sur une ligne séparée) :
1. Premier score (entier)
2. Deuxième score (entier)
3. Troisième score (entier)
4. Quatrième score (entier)
5. Un score à rechercher (entier)
6. Un montant de bonus à appliquer (entier)
Créez un vecteur avec les quatre scores et démontrez les algorithmes :
1. Affichez Original: suivi du contenu du vecteur
2. Triez les scores et affichez Sorted: suivi du vecteur trié
3. Recherchez le score cible dans le vecteur trié. S'il est trouvé, affichez Found <value> at index <index>. S'il n'est pas trouvé, affichez <value> not found
4. Appliquez le bonus aux scores triés et affichez With bonus: suivi du nouveau vecteur
5. Calculez et affichez la moyenne des scores triés originaux (avant bonus) sous la forme Average: <value> avec une décimale

Par exemple, avec les entrées 75, 90, 60, 85, 85, et 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

Avec les entrées 100, 80, 95, 70, 50, et 10 :

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

N'oubliez pas d'inclure <algorithm> pour sort, find, et transform, et <numeric> pour accumulate. Utilisez std::fixed et std::setprecision(1) de <iomanip> pour formater la moyenne.

Aide-mémoire

Les algorithmes de la STL sont des fonctions templates provenant de <algorithm> et <numeric> qui opèrent sur des plages définies par des itérateurs.

std::sort organise les éléments par ordre croissant :

#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 recherche une valeur et renvoie un itérateur vers la première correspondance, ou end() si elle n'est pas trouvée :

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

std::transform applique une opération à chaque élément et stocke les résultats dans une plage de destination :

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> combine tous les éléments en une seule valeur :

#include <numeric>

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

Ces algorithmes fonctionnent avec des plages d'itérateurs, ce qui les rend flexibles pour des plages partielles ou différents types de conteneurs.

Essayez vous-même

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

using namespace std;

int main() {
    // Lire six entrées
    int score1, score2, score3, score4;
    int searchTarget, bonusAmount;
    
    cin >> score1;
    cin >> score2;
    cin >> score3;
    cin >> score4;
    cin >> searchTarget;
    cin >> bonusAmount;
    
    // TODO: Créer un vector avec les quatre scores
    
    // TODO: Afficher "Original:" suivi du contenu du vector
    
    // TODO: Trier les scores et afficher "Sorted:" suivi du vector trié
    
    // TODO: Rechercher le score cible dans le vector trié
    // Si trouvé, afficher "Found <value> at index <index>"
    // Si non trouvé, afficher "<value> not found"
    
    // TODO: Appliquer le bonus aux scores triés et afficher "With bonus:" suivi du nouveau vector
    
    // TODO: Calculer et afficher la moyenne des scores triés (avant bonus)
    // Utiliser fixed et setprecision(1) pour le formatage
    // Afficher sous la forme "Average: <value>"
    
    return 0;
}