Les algorithmes de la bibliothèque standard C++ offrent une large gamme de fonctionnalités pour manipuler des conteneurs et des plages d'éléments. Ce guide explore les différentes catégories d'algorithmes et leur utilisation pratique.

1. Algorithmes sans modification

Ces algorithmes n'altèrent pas les éléments des conteneurs qu'ils parcourent.

1.1 Recherche d'éléments

• rechercher localise la première occurrence d'une valeur donnée dans une plage.
• rechercher_si identifie le premier élément satisfaisant un prédicat.
• rechercher_fin trouve la dernière position d'une sous-séquence.

vector<int> donnees = {2, 5, 8, 11, 14};

// Trouver l'élément égal à 8
auto it = find(donnees.begin(), donnees.end(), 8);
if (it != donnees.end()) {
    cout << "Valeur trouvée : " << *it << endl;  // Affiche 8
}

// Rechercher le premier élément supérieur à 10
auto it2 = find_if(donnees.begin(), donnees.end(), [](int val) {
    return val > 10;
});
cout << "Premier >10 : " << *it2 << endl;  // Affiche 11

// Détecter une sous-séquence
vector<int> sous_seq = {5, 8};
auto it3 = find_end(donnees.begin(), donnees.end(), sous_seq.begin(), sous_seq.end());
if (it3 != donnees.end()) {
    cout << "Position de la sous-séquence : " << it3 - donnees.begin() << endl;  // Affiche 1
}

1.2 Comptage conditionnel

Les fonctions compter et compter_si permettent de dénombrer les occurrences ou les éléments vérifiant une condition.

vector<int> ensemble = {3, 7, 3, 9, 3, 4};
int nb_trois = count(ensemble.begin(), ensemble.end(), 3); // Résultat : 3
int nb_pairs = count_if(ensemble.begin(), ensemble.end(), [](int x) {
    return x % 2 == 0;
}); // Résultat : 1 (seul 4 est pair)

1.3 Application d'opération

pour_chaque applique une fonction à tous les éléments d'une plage, potentiellement en les modifiant par référence.

vector<int> serie = {10, 20, 30, 40};
for_each(serie.begin(), serie.end(), [](int& elem) {
    elem /= 10; // Divise chaque élément par 10
});
// serie devient {1, 2, 3, 4}

1.4 Comparaison de plages

• egal vérifie si deux plages sont identiques élément par élément.
• incompatibilite retourne la première position où les plages diffèrent.

vector<int> seq_a = {5, 10, 15};
vector<int> seq_b = {5, 10, 20};
vector<int> seq_c = {5, 10, 15, 25};

bool identiques = equal(seq_a.begin(), seq_a.end(), seq_b.begin());
cout << "seq_a et seq_b identiques ? " << boolalpha << identiques << endl;  // false

auto divergence = mismatch(seq_a.begin(), seq_a.end(), seq_c.begin());
if (divergence.first != seq_a.end()) {
    cout << "Première différence : " << *divergence.first << " vs " << *divergence.second << endl;
}

1.5 Vérifications globales

tout_si, au_moins_un_si et aucun_si évaluent des conditions sur l'ensemble d'une plage.

vector<int> valeurs = {4, 6, 8, 10};
bool tous_positifs = all_of(valeurs.begin(), valeurs.end(), [](int v) {
    return v > 0;
}); // true
bool contient_impair = any_of(valeurs.begin(), valeurs.end(), [](int v) {
    return v % 2 != 0;
}); // false
bool aucun_negatif = none_of(valeurs.begin(), valeurs.end(), [](int v) {
    return v < 0;
}); // true

2. Algorithmes modificateurs

Ces algorithmes modifient les éléments des conteneurs ou produisent de nouvelles séquences.

2.1 Copie sélective

• copier duplique les éléments d'une plage vers une destination.
• copier_si ne copie que les éléments vérifiant un prédicat.

vector<int> source = {3, 8, 12, 5, 9};
vector<int> destination;

// Copie complète
copy(source.begin(), source.end(), back_inserter(destination)); // destination = {3,8,12,5,9}

// Copie des éléments impairs uniquement
vector<int> impairs;
copy_if(source.begin(), source.end(), back_inserter(impairs), [](int val) {
    return val % 2 != 0;
}); // impairs = {3,5,9}

2.2 Transformation

transformer applique une fonction à chaque élément, stockant le résultat dans une autre plage.

vector<int> nombres = {2, 3, 4};
vector<int> carres(nombres.size());

// Calcul des carrés
transform(nombres.begin(), nombres.end(), carres.begin(), [](int n) {
    return n * n;
}); // carres = {4,9,16}

// Combinaison de deux plages
vector<int> x = {1, 2, 3};
vector<int> y = {4, 5, 6};
vector<int> somme(x.size());
transform(x.begin(), x.end(), y.begin(), somme.begin(), [](int a, int b) {
    return a + b;
}); // somme = {5,7,9}

2.3 Remplacement

Les variantes remplacer, remplacer_si et remplacer_copie modifient ou dupliquent des éléments selon des critères.

vector<int> data = {5, 12, 5, 18, 5};
replace(data.begin(), data.end(), 5, 50); // data = {50,12,50,18,50}
replace_if(data.begin(), data.end(), [](int v) { return v > 15; }, 0); // data = {50,12,50,0,50}

vector<int> copie;
replace_copy(data.begin(), data.end(), back_inserter(copie), 12, 120); // copie = {50,120,50,0,50}, data inchangé

2.4 Suppression logique et physique

supprimer et supprimer_si déplacent les éléments à éliminer vers la fin, retournant un nouvel itérateur de fin logique. Il faut ensuite appeler effacer pour modifier la taille du conteneur.

vector<int> liste = {7, 2, 7, 9, 7, 4};
auto nouvelle_fin = remove(liste.begin(), liste.end(), 7); // liste = {2,9,4,7,7,?}, nouvelle_fin pointe avant les 7
liste.erase(nouvelle_fin, liste.end()); // liste = {2,9,4}

// Combinaison avec erase et remove_if
liste = {1, 6, 3, 8, 5};
liste.erase(remove_if(liste.begin(), liste.end(), [](int n) {
    return n % 2 == 0;
}), liste.end()); // liste = {1,3,5}

2.5 Déduplication et réordonnancement

• unique élimine les doublons consécutifs.
• inverser inverse l'ordre des éléments.
• tourner effectue une rotation des éléments.
• melanger réordonne aléatoirement (nécessite C++11).

vector<int> seq = {1, 1, 2, 3, 3, 4};
auto fin_unique = unique(seq.begin(), seq.end());
seq.erase(fin_unique, seq.end()); // seq = {1,2,3,4}

vector<int> tab = {10, 20, 30, 40, 50};
reverse(tab.begin(), tab.end()); // tab = {50,40,30,20,10}

rotate(tab.begin(), tab.begin() + 2, tab.end()); // Rotation autour du 3ème élément, tab = {30,20,10,50,40}

#include <random>
vector<int> aleatoire = {1, 2, 3, 4, 5};
random_device rd;
mt19937 gen(rd());
shuffle(aleatoire.begin(), aleatoire.end(), gen); // Ordre aléatoire

3. Algorithmes de tri et recherche

3.1 Tri

• trier effectue un tri instable (introsort).
• trier_stable préserve l'ordre relatif des éléments égaux (merge sort).
• trier_partiel trie seulement une portion spécifiée.

vector<int> chiffres = {9, 3, 7, 1, 5};
sort(chiffres.begin(), chiffres.end()); // Tri ascendant, chiffres = {1,3,5,7,9}
sort(chiffres.begin(), chiffres.end(), greater<int>()); // Tri descendant

vector<pair<int,string>> paires = {{2,"b"}, {1,"a"}, {2,"c"}, {1,"b"}};
stable_sort(paires.begin(), paires.end(), [](const auto& p1, const auto& p2) {
    return p1.first < p2.first;
}); // Trie par première valeur, conserve l'ordre original pour les valeurs égales

vector<int> mixte = {8, 3, 6, 1, 9, 4};
partial_sort(mixte.begin(), mixte.begin() + 3, mixte.end()); // Les 3 plus petits en tête triés : {1,3,4,8,9,6}

3.2 Sélection de position

nieme_element réorganise la plage de sorte que l'élément à la position donnée soit à sa place finale dans une séquence triée.

vector<int> valeurs = {7, 2, 9, 4, 6};
nth_element(valeurs.begin(), valeurs.begin() + 2, valeurs.end()); // valeurs[2] est la 3ème plus petite valeur (6), avec 2,4 à gauche et 7,9 à droite

3.3 Recherche dans des plages triées

Ces algorithmes nécessitnet une plage préalablement triée.

• recherche_binaire teste l'existence d'une valeur.
• borne_inf et borne_sup retournent des itérateurs pour des valeurs limites.

vector<int> trie = {2, 5, 5, 8, 11};
bool present = binary_search(trie.begin(), trie.end(), 5); // true
auto inf = lower_bound(trie.begin(), trie.end(), 5); // Pointe vers le premier 5 (index 1)
auto sup = upper_bound(trie.begin(), trie.end(), 5); // Pointe vers l'élément après le dernier 5 (index 3, valeur 8)

3.4 Fusion

fusionner combine deux plages triées en une nouvelle plage triée.

vector<int> gauche = {1, 4, 7};
vector<int> droite = {2, 5, 8};
vector<int> resultat(gauche.size() + droite.size());
merge(gauche.begin(), gauche.end(), droite.begin(), droite.end(), resultat.begin()); // resultat = {1,2,4,5,7,8}

4. Algorithmes sur les tas

Les fonctions faire_tas, pousser_dans_tas, extraire_du_tas et trier_tas manipulent des plages comme des tas binaires.

vector<int> tas = {3, 1, 4, 1, 5};
make_heap(tas.begin(), tas.end()); // Transforme en tas max, tas = {5,4,3,1,1}

tas.push_back(9);
push_heap(tas.begin(), tas.end()); // Ajoute l'élément au tas, tas = {9,4,5,1,1,3}

pop_heap(tas.begin(), tas.end()); // Déplace le maximum (9) à la fin, tas = {5,4,3,1,1,9}
int max_val = tas.back(); // Récupère 9
tas.pop_back(); // Supprime le maximum

sort_heap(tas.begin(), tas.end()); // Trie le tas en ordre croissant, tas = {1,1,3,4,5}

5. Algorithmes numériques

Fournis dans l'en-tête <numeric>.

• accumuler calcule une somme ou applique une opération binaire récursive.
• produit_interne calcule le produit scalaire de deux plages.
• remplir_croissant initialise une plage avec des valeurs consécutives.
• somme_partielle et difference_adjacente génèrent des séquences dérivées.

#include <numeric>
vector<int> serie = {2, 3, 4, 5};
int total = accumulate(serie.begin(), serie.end(), 0); // Somme, total = 14
int produit = accumulate(serie.begin(), serie.end(), 1, multiplies<int>()); // Produit, produit = 120

vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
int scalaire = inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32

vector<int> plage(5);
iota(plage.begin(), plage.end(), 10); // plage = {10,11,12,13,14}

vector<int> src = {3, 1, 4, 1, 5};
vector<int> cumul(src.size());
partial_sum(src.begin(), src.end(), cumul.begin()); // cumul = {3,4,8,9,14}

vector<int> diffs(src.size());
adjacent_difference(src.begin(), src.end(), diffs.begin()); // diffs = {3,-2,3,-3,4}

6. Opérations ensemblistes et génération

Divers algorithmes pour les ensembles et la génération de données.

• est_inclus vérifie si une plage triée contient toutes les éléments d'une autre.
• union_set, intersection_set, difference_set, difference_symetrique_set effectuent des opérations ensemblistes sur des plages triées.
• generer et generer_n remplissent des plages à l'aide d'une fonction de génération.

vector<int> grand = {1, 2, 3, 4, 5, 6};
vector<int> petit = {2, 4, 6};
bool inclus = includes(grand.begin(), grand.end(), petit.begin(), petit.end()); // true

vector<int> ensemble_a = {1, 3, 5, 7};
vector<int> ensemble_b = {3, 4, 5, 6};
vector<int> uni;

// Union
set_union(ensemble_a.begin(), ensemble_a.end(), ensemble_b.begin(), ensemble_b.end(), back_inserter(uni));
// uni = {1,3,4,5,6,7}

vector<int> inter;
set_intersection(ensemble_a.begin(), ensemble_a.end(), ensemble_b.begin(), ensemble_b.end(), back_inserter(inter));
// inter = {3,5}

vector<int> diff;
set_difference(ensemble_a.begin(), ensemble_a.end(), ensemble_b.begin(), ensemble_b.end(), back_inserter(diff));
// diff = {1,7}

vector<int> sym_diff;
set_symmetric_difference(ensemble_a.begin(), ensemble_a.end(), ensemble_b.begin(), ensemble_b.end(), back_inserter(sym_diff));
// sym_diff = {1,4,6,7}

vector<int> rempli(4);
int compteur = 100;
generate(rempli.begin(), rempli.end(), [&compteur]() {
    return compteur += 5;
}); // rempli = {105,110,115,120}

vector<int> debut(5);
generate_n(debut.begin(), 2, [&compteur]() {
    return compteur--;
}); // Les deux premiers éléments sont modifiés