Introduction aux algorithmes génériques

En C++, les conteneurs de la bibliothèque standard (STL) ne possèdent que peu de méthodes de manipulation directe. Au lieu d'intégrer des fonctions complexes comme le tri ou la recherche dans chaque type de conteneur, le langage utilise des algorithmes génériques. Le terme "générique" signifie que ces algorithmes sont indépendants du type de conteneur et travaillent sur une grande variété d'éléments.

Les algorithmes n'agissent jamais directement sur le conteneur lui-même, mais passent par des itérateurs. Cette abstraction permet d'appliquer la même logique de recherche à un std::vector, une std::list ou même un tableau brut.

Fonctionnement via les itérateurs

La plupart des algorithmes sont déclarés dans l'en-tête <algorithm>, tandis que les algorithmes numériques résident dans <numeric>. Voici un exemple simple avec std::find :

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

int main() {
    std::vector<std::string> mots = {"C++", "Python", "Rust", "Java"};
    std::string cible = "Rust";
    
    // find retourne un itérateur vers l'élément ou vers la fin si non trouvé
    auto it = std::find(mots.cbegin(), mots.cend(), cible);
    
    if (it != mots.cend()) {
        std::cout << cible << " a été trouvé dans la liste." << std::endl;
    } else {
        std::cout << cible << " est absent." << std::endl;
    }
    return 0;
}

Il est crucial de comprendre que les algorithmes ne modifient jamais la taile du conteneur. Ils peuvent modifier les valeurs ou déplacer les éléments, mais l'ajout ou la suppression de cellules mémoire nécessite l'appel explicite à des méthodes membres du conteneur (comme erase).

Algorithmes en lecture seule

Certains algorithmes se contentent de parcourir la séquence sans modifier les données. C'est le cas de std::accumulate et std::equal.

Sommation avec accumulate

L'algorithme accumulate (dans <numeric>) calcule la somme d'une plage d'éléments à partir d'une valeur initiale. Le type de cette valeur initiale détermine le type de retour.

#include <numeric>
#include <vector>

std::vector<double> mesures = {1.5, 2.5, 3.0};
// Le 0.0 indique un calcul en double
double total = std::accumulate(mesures.begin(), mesures.end(), 0.0);

Comparaison avec equal

L'algorithme equal compare deux séquences. Il suppose par défaut que la seconde séquence est au moins aussi longue que la plage définie pour la première.

bool sont_identiques = std::equal(v1.begin(), v1.end(), v2.begin());

Modification des éléments et itérateurs d'insertion

Pour écrire des données, on utilise des fonctions comme fill ou copy. Cependant, si le conteneur est vide, une écriture directe provoquera une erreur. C'est ici qu'intervient std::back_inserter.

#include <iterator>
#include <vector>
#include <algorithm>

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination; // Vide

// back_inserter appelle push_back à chaque itération
std::copy(source.begin(), source.end(), std::back_inserter(destination));

Personnalisation via les prédicats et expressions Lambda

De nombreux algorithmes acceptent un prédicat, c'est-à-dire une fonction ou un objet appelable qui retourne un booléen pour guider l'algorithme.

Les expressions Lambda

Une lambda est une fonction anonyme définie localement. Sa structure est : [capture](paramètres) -> type_retour { corps }.

• Capture par valeur [=] : Une copie des variables locales est créée.
• Capture par référence [&] : La lambda travaille sur les variables originales.

#include <vector>
#include <algorithm>

int seuil = 10;
std::vector<int> nombres = {5, 12, 8, 15, 3};

// Compter les nombres supérieurs au seuil
auto nb = std::count_if(nombres.begin(), nombres.end(), [seuil](int n) {
    return n > seuil;
});

L'adaptateur std::bind

Pour transformer une fonction prenant plusieurs arguments en un objet appelable compatible avec un algorithme (ex: transformer une fonction binaire en unaire), on utilise std::bind :

using namespace std::placeholders;
auto superieur_a_10 = std::bind(std::greater<int>(), _1, 10);
bool resultat = superieur_a_10(15); // Retourne vrai

Itérateurs de flux (Stream Iterators)

Les itérateurs peuvent lier les algorithmes directement aux entrées/sorties (IO).

• std::istream_iterator : Lit les données depuis un flux (ex: cin).
• std::ostream_iterator : Écrit les données vers un flux (ex: cout).

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

int main() {
    std::vector<int> v = {1, 2, 3, 4};
    std::ostream_iterator<int> out_it(std::cout, " | ");
    std::copy(v.begin(), v.end(), out_it); // Affiche: 1 | 2 | 3 | 4 | 
    return 0;
}

Classification des itérateurs

Les algorithmes exigent des capacités spécifiques de la part des itérateurs. On distingue 5 catégories :

Algorithmes spécifiques aux listes

Pour les types std::list et std::forward_list, il est préférable d'utiliser leurs méthodes membres (sort, merge, remove, reverse, unique) plutôt que les algorithmes génériques. Les versions génériques de sort nécessitent des itérateurs à accès aléatoire, ce que les listes ne fournissent pas.

La méthode splice est également unique aux listes, permettant de transférer des nœuds d'une liste à une autre de manière très performante, sans copie des données réelles.