- Algorithmes de séquence non modifiante
Ces algorithmes ne modifient pas les éléments des conteneurs sur lesquels ils opèrent.
1.1 Recherche avec find et find_if
find(premier, dernier, valeur) localise le premier élément égal à la valeur et retourne un itérateur. Si aucun élément n'est trouvé, l'itérateur dernier est retourné.
find_if(premier, dernier, predicat) cherche le premier élément satisfaisant le predicat.
find_end(premier, dernier, sous_premier, sous_dernier) localise la dernière occurrence de la sous-séquence spécifiée.
vector<int> donnees = {10, 30, 50, 70, 90};
// Recherche de l'élément 50
auto position = find(begin(donnees), end(donnees), 50);
if (position != end(donnees)) {
cout << "Élément trouvé: " << *position << endl; // Affiche: 50
}
// Recherche du premier élément supérieur à 65
auto it_sup = find_if(begin(donnees), end(donnees), [](int elem) {
return elem > 65;
});
cout << "Premier >65: " << *it_sup << endl; // Affiche: 70
// Recherche d'une sous-séquence
vector<int> motif = {30, 50};
auto debut_seq = find_end(begin(donnees), end(donnees), begin(motif), end(motif));
if (debut_seq != end(donnees)) {
cout << "Sous-séquence à l'index: " << distance(begin(donnees), debut_seq) << endl; // Affiche: 1
}
1.2 Comptage avec count et count_if
count(premier, dernier, valeur) dénombre les occurrences d'une valeur.
count_if(premier, dernier, predicat) dénombre les éléments répondant au predicat.
std::vector<int> elements = {1, 2, 3, 2, 4, 2};
int nb_deux = std::count(begin(elements), end(elements), 2); // Résultat: 3
int nb_pairs = std::count_if(begin(elements), end(elements), [](int elem) {
return elem % 2 == 0;
}); // Résultat: 4
1.3 Application avec for_each
Cet algorithme applique une fonction à chaque élément d'une plage.
std::vector<int> valeurs = {1, 2, 3, 4, 5};
std::for_each(begin(valeurs), end(valeurs), [](int& elem) {
elem *= 3; // Multiplie chaque élément par 3
});
// valeurs contient maintenant {3, 6, 9, 12, 15}
1.4 Comparaison avec equal et mismatch
equal(premier1, dernier1, premier2) vérifie si deux plages sont identiques.
mismatch(premier1, dernier1, premier2) retourne un pair d'itérateurs pointant vers le premier élément différent.
vector<int> seq_a = {5, 10, 15};
vector<int> seq_b = {5, 10, 20};
vector<int> seq_c = {5, 10, 15, 20};
bool identiques = equal(begin(seq_a), end(seq_a), begin(seq_b)); // Faux
auto divergence = mismatch(begin(seq_a), end(seq_a), begin(seq_c));
if (divergence.first != end(seq_a)) {
cout << "Différence: " << *divergence.first << " vs " << *divergence.second << endl;
// Affiche: 15 vs 15 (car les 3 premiers sont égaux)
}
1.5 Tests logiques: all_of, any_of, none_of
Ces fonctions vérifient si tous, certains ou aucun élément satisfont une condition.
std::vector<int> collection = {2, 4, 6, 8};
bool tous_positifs = std::all_of(begin(collection), end(collection), [](int x) {
return x > 0;
}); // Vrai
bool contient_pair = std::any_of(begin(collection), end(collection), [](int x) {
return x % 2 == 0;
}); // Vrai
bool aucun_negatif = std::none_of(begin(collection), end(collection), [](int x) {
return x < 0;
}); // Vrai
- Algorithmes de séquence modifiante
Ces algorithmes altèrent les éléments des conteneurs.
2.1 Copie avec copy et copy_if
copy(premier, dernier, dest) dulpique tous les éléments vers la destination dest.
copy_if(premier, dernier, dest, predicat) ne copie que les éléments validant le predicat.
vector<int> source = {10, 20, 30, 40, 50};
vector<int> recepteur;
// Copie conditionnelle avec itérateur d'insertion
copy_if(begin(source), end(source), back_inserter(recepteur), [](int x) {
return x % 20 == 0;
}); // recepteur: {20, 40}
2.2 Transformation avec transform
transform applique une fonction et stocke les résultats dans une autre plage.
vector<int> nombres = {2, 3, 4};
vector<int> cubes(nombres.size());
// Transformation unaire: calcul des cubes
transform(begin(nombres), end(nombres), begin(cubes), [](int n) {
return n * n * n;
}); // cubes: {8, 27, 64}
// Transformation binaire: somme de deux plages
vector<int> partie1 = {1, 2, 3};
vector<int> partie2 = {10, 20, 30};
vector<int> total(3);
transform(begin(partie1), end(partie1), begin(partie2), begin(total), [](int a, int b) {
return a + b;
}); // total: {11, 22, 33}
2.3 Remplacement: replace, replace_if et replace_copy
replace(premier, dernier, ancien, nouveau) substitue toutes les occurrences de ancien par nouveau.
replace_if effectue un remplacement conditionnel.
replace_copy effectue la substitution lors d'une copie, préservant l'original.
vector<int> liste = {1, 2, 3, 2, 5};
// Remplacement in-place
replace(begin(liste), end(liste), 2, 20); // Liste: {1, 20, 3, 20, 5}
// Remplacement conditionnel
replace_if(begin(liste), end(liste), [](int x) { return x > 15; }, 0); // Liste: {1, 0, 3, 0, 5}
// Copie avec remplacement
vector<int> copie_modifiee;
replace_copy(begin(liste), end(liste), back_inserter(copie_modifiee), 3, 300); // copie_modifiee: {1, 0, 300, 0, 5}
2.4 Suppression logique et physique: remove, remove_if et erase
remove et remove_if ne suppriment pas physiquement les éléments. Ils les déplacent à la fin et retournent un itérateur vers la nouvelle fin logique. L'effacement réel nécessite erase.
vector<int> donnees = {5, 1, 5, 2, 5};
// Étape 1: Suppression logique (les 5 sont déplacés à la fin)
auto fin_logique = remove(begin(donnees), end(donnees), 5); // donnees: {1, 2, 5, 5, 5}
// Étape 2: Suppression physique
donnees.erase(fin_logique, end(donnees)); // donnees: {1, 2}
// Combinaison en une seule instruction pour les impairs
donnees = {1, 2, 3, 4, 5, 6};
donnees.erase(remove_if(begin(donnees), end(donnees), [](int n) { return n % 2 != 0; }), end(donnees));
// donnees: {2, 4, 6}
2.5 Élimination des doublons consécutifs: unique
std::vector<int> seq = {1, 1, 3, 3, 3, 5, 5, 7};
auto nouveau_fin = std::unique(begin(seq), end(seq));
seq.erase(nouveau_fin, end(seq)); // seq: {1, 3, 5, 7}
2.6 Inversion: reverse
std::vector<int> tableau = {10, 20, 30, 40};
std::reverse(begin(tableau), end(tableau)); // tableau: {40, 30, 20, 10}
2.7 Rotation: rotate
Effectue une rotation des éléments autour d'un point pivot.
std::vector<int> cyclique = {1, 2, 3, 4, 5, 6};
// Rotation pour que l'élément à l'index 3 (valeur 4) devienne le premier
std::rotate(begin(cyclique), begin(cyclique) + 3, end(cyclique));
// cyclique: {4, 5, 6, 1, 2, 3}
2.8 Mélange aléatoire: shuffle (C++11)
#include <random>
#include <algorithm>
std::vector<int> paquet = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 generateur(rd());
std::shuffle(begin(paquet), end(paquet), generateur); // Mélange aléatoire
- Algorithmes de tri et associés
3.1 Tri: sort, stable_sort et partial_sort
sort(premier, dernier) trie les éléments (complexité moyenne O(n log n), algorithme instable).
stable_sort maintient l'ordre relatif des éléments égaux.
partial_sort(premier, milieu, dernier) trie seulement les n premiers éléments.
vector<int> chiffres = {5, 3, 1, 4, 2};
sort(begin(chiffres), end(chiffres)); // {1, 2, 3, 4, 5}
// Tri descendant avec un foncteur prédéfini
sort(begin(chiffres), end(chiffres), std::greater<int>()); // {5, 4, 3, 2, 1}
// Tri partiel: garder les 3 plus petits en tête
chiffres = {5, 3, 1, 4, 2, 6};
partial_sort(begin(chiffres), begin(chiffres) + 3, end(chiffres));
// chiffres: {1, 2, 3, 4, 5, 6} (les 3 premiers sont triés)
3.2 Partitionnement: nth_element
Réorganise les éléments de sorte que le n-ième élément soit à sa position finale.
vector<int> serie = {5, 2, 8, 1, 9, 3};
// Placer le 3ème élément (index 2) à sa position finale
nth_element(begin(serie), begin(serie) + 2, end(serie));
// Maintenant, serie[2] est 3. Tous les éléments avant sont <= 3, tous après sont >= 3.
3.3 Recherche binaire sur données triées: binary_search, lower_bound, upper_bound
vector<int> trie = {10, 20, 20, 30, 40}; // Doit être trié
bool present = binary_search(begin(trie), end(trie), 20); // Vrai
// Itérateur vers le premier élément >= 25
auto lb = lower_bound(begin(trie), end(trie), 25);
cout << "Index lower_bound: " << distance(begin(trie), lb) << endl; // 3
// Itérateur vers le premier élément > 20
auto ub = upper_bound(begin(trie), end(trie), 20);
cout << "Index upper_bound: " << distance(begin(trie), ub) << endl; // 3
3.4 Fusion de séquences triées: merge
vector<int> gauche = {1, 4, 7};
vector<int> droite = {2, 5, 8};
vector<int> fusion(gauche.size() + droite.size());
merge(begin(gauche), end(gauche), begin(droite), end(droite), begin(fusion));
// fusion: {1, 2, 4, 5, 7, 8}
- Algorithmes de tas (heap)
Ces algorithmes manipulent une plage comme un tas binaire.
vector<int> tas = {30, 10, 50, 20, 40};
make_heap(begin(tas), end(tas)); // Crée un max-heap
tas.push_back(60);
push_heap(begin(tas), end(tas)); // Ajoute 60 au tas
pop_heap(begin(tas), end(tas)); // Déplace le max (60) à la fin
int maximum = tas.back(); // 60
tas.pop_back(); // Supprime le dernier élément
sort_heap(begin(tas), end(tas)); // Trie le tas en ordre croissant
- Recherche de minimum et maximum
5.1 min, max et minmax
int x = 7, y = 3;
auto paire = std::minmax(x, y); // paire.first=3, paire.second=7
auto extrema = std::minmax({9, 2, 7, 5, 1}); // {1, 9}
5.2 Itérateurs min/max: min_element, max_element, minmax_element
vector<int> points = {5, 2, 8, 1, 9};
auto it_min = std::min_element(begin(points), end(points)); // Pointe vers 1
auto it_max = std::max_element(begin(points), end(points)); // Pointe vers 9
auto paire_it = std::minmax_element(begin(points), end(points));
// paire_it.first pointe vers 1, paire_it.second pointe vers 9
- Algorithmes numériques (en-tête <numeric>)
6.1 Accumulation: accumulate
#include <numeric>
vector<int> valeurs = {1, 2, 3, 4, 5};
int somme = std::accumulate(begin(valeurs), end(valeurs), 0); // 15
int produit = std::accumulate(begin(valeurs), end(valeurs), 1, std::multiplies<>()); // 120
6.2 Produit scalaire: inner_product
vector<int> u = {1, 2, 3};
vector<int> v = {4, 5, 6};
int scalaire = std::inner_product(begin(u), end(u), begin(v), 0); // 1*4 + 2*5 + 3*6 = 32
6.3 Remplissage séquentiel: iota
vector<int> sequence(5);
std::iota(begin(sequence), end(sequence), 100); // {100, 101, 102, 103, 104}
6.4 Sommes partielles: partial_sum
vector<int> entrees = {1, 3, 5, 7};
vector<int> sommes(entrees.size());
std::partial_sum(begin(entrees), end(entrees), begin(sommes)); // {1, 4, 9, 16}
6.5 Différences adjacentes: adjacent_difference
vector<int> valeurs = {10, 15, 12, 20};
vector<int> differences(valeurs.size());
std::adjacent_difference(begin(valeurs), end(valeurs), begin(differences)); // {10, 5, -3, 8}
- Autres alogrithmes utiles
7.1 Génération: generate et generate_n
vector<int> cible(5);
int compteur = 0;
std::generate(begin(cible), end(cible), [&compteur]() { return compteur += 2; });
// cible: {2, 4, 6, 8, 10}
vector<int> autre(5, 0);
std::generate_n(begin(autre), 3, []() { return rand() % 100; }); // 3 éléments aléatoires
7.2 Test d'inclusion: includes
vector<int> ensemble = {1, 2, 3, 4, 5, 6};
vector<int> sous_ensemble = {2, 4, 6};
bool est_inclus = std::includes(begin(ensemble), end(ensemble), begin(sous_ensemble), end(sous_ensemble)); // Vrai
7.3 Opérations ensemblistes
set_union, set_intersection, set_difference, set_symmetric_difference opèrent sur des plages triées.
vector<int> a = {1, 3, 5, 7};
vector<int> b = {3, 4, 5, 6};
vector<int> resultat;
// Union
set_union(begin(a), end(a), begin(b), end(b), back_inserter(resultat)); // {1, 3, 4, 5, 6, 7}
// Intersection
resultat.clear();
set_intersection(begin(a), end(a), begin(b), end(b), back_inserter(resultat)); // {3, 5}
// Différence (a - b)
resultat.clear();
set_difference(begin(a), end(a), begin(b), end(b), back_inserter(resultat)); // {1, 7}
// Différence symétrique
resultat.clear();
set_symmetric_difference(begin(a), end(a), begin(b), end(b), back_inserter(resultat)); // {1, 4, 6, 7}