1. Algorithmes non modificateurs de séquence

Ces algorithmes ne modifient pas les éléments des conteneurs sur lesquels ils opèrent.

1.1 find et find_if

• find(debut, fin, valeur) : recherche le premier élément égal à valeur, retourne un itérateur (retourne fin si non trouvé).
• find_if(debut, fin, prédicat) : recherche le premier élément satisfaisant le prédicat.
• find_end(debut, fin, debut_sous, fin_sous) : recherche la dernière occurrence d'une sous-séquence.

std::vector<int> donnees = {10, 30, 50, 70, 90};

// Recherche de l'élément 50
auto iterateur = std::find(donnees.begin(), donnees.end(), 50);
if (iterateur != donnees.end()) {
    std::cout << "trouvé: " << *iterateur << std::endl;  // Affiche : 50
}

// Recherche du premier élément supérieur à 60
auto iterateur2 = std::find_if(donnees.begin(), donnees.end(), [](int x) {
    return x > 60;
});
std::cout << "premier >60: " << *iterateur2 << std::endl;  // Affiche : 70

// Recherche d'une sous-séquence
std::vector<int> sous_seq = {30, 50};
auto iterateur3 = std::find_end(donnees.begin(), donnees.end(), sous_seq.begin(), sous_seq.end());
if (iterateur3 != donnees.end()) {
    std::cout << "sous-séquence commence à l'indice: " << iterateur3 - donnees.begin() << std::endl;  // Affiche : 1
}

1.2 count et count_if

• count(debut, fin, valeur) : compte le nombre d'éléments égaux à valeur.
• count_if(debut, fin, prédicat) : compte le nombre d'éléments satisfaisant le prédicat.

std::vector<int> tableau = {1, 2, 3, 2, 4, 2};
int nombre = std::count(tableau.begin(), tableau.end(), 2); // Compte les 2, résultat = 3
int pair_cnt = std::count_if(tableau.begin(), tableau.end(), [](int x) { 
    return x % 2 == 0; 
}); // Nombre d'éléments pairs, résultat = 3

1.3 for_each

Applique une fonction à chaque élément de la plage

std::vector<int> donnees = {1, 2, 3, 4, 5};
std::for_each(donnees.begin(), donnees.end(), [](int& x) { 
    x += 1; // Incrémente chaque élément de 1
});
// Maintenant donnees est {2, 3, 4, 5, 6}

1.4 equal et mismatch

• equal(b1, e1, b2) : vérifie si les plages [b1,e1) et [b2, b2+(e1-b1)) sont égales.
• mismatch(b1, e1, b2) : retourne une paire d'itérateurs pointant vers le premier élément différent dans les deux plages.

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {1, 2, 4};
std::vector<int> c = {1, 2, 3, 4};

// Comparaison des 3 premiers éléments de a et b
bool egal = std::equal(a.begin(), a.end(), b.begin());
std::cout << "a == b? " << std::boolalpha << egal << std::endl;  // Affiche : false

// Recherche du premier élément différent entre a et c
auto diff = std::mismatch(a.begin(), a.end(), c.begin());
if (diff.first != a.end()) {
    std::cout << "différence: " << *diff.first << " vs " << *diff.second << std::endl;  // Pas d'affichage (les 3 premiers éléments de a et c sont identiques)
}

1.5 all_of, any_of, none_of

Vérifie si tous, au moins un ou aucun élément satisfait une condition

std::vector<int> donnees = {2, 4, 6, 8};
bool tous_pairs = std::all_of(donnees.begin(), donnees.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool au_moins_impair = std::any_of(donnees.begin(), donnees.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool aucun_negatif = std::none_of(donnees.begin(), donnees.end(), [](int x) { 
    return x < 0; 
}); // true

2. Algorithmes modificateurs de séquence

Ces algorithmes modifient les éléments des conteneurs sur lesquels ils opèrent.

2.1 copy et copy_if

• copy(debut, fin, destination) : copie les éléments de [debut, fin) à partir de destination.
• copy_if(debut, fin, destination, prédicat) : copie les éléments satisfaisant le prédicat vers destination.

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);  // Espace pré-alloué suffisant

// Copie de tous les éléments
std::copy(source.begin(), source.end(), destination.begin());  // destination: [1,2,3,4,5]

// Copie des éléments pairs vers un nouveau conteneur
std::vector<int> pairs;
std::copy_if(source.begin(), source.end(), std::back_inserter(pairs), [](int x) {
    return x % 2 == 0;
});  // pairs: [2,4]

Note : std::back_inserter(destination) appelle automatiquement push_back, pas besoin d'allouer de l'espace à l'avance.

2.2 transform

Applqiue une fonction à chaque élément d'une plage et stocke le résultat dans une autre plage

std::vector<int> valeurs = {1, 2, 3};
std::vector<int> carres(3);

// Calcul des carrés (transformation à un paramètre)
std::transform(valeurs.begin(), valeurs.end(), carres.begin(), [](int x) {
    return x * x;
});  // carres: [1,4,9]

// Somme des éléments de deux conteneurs (transformation à deux paramètres)
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::vector<int> somme(3);
std::transform(a.begin(), a.end(), b.begin(), somme.begin(), [](int x, int y) {
    return x + y;
});  // somme: [5,7,9]

2.3 replace, replace_if et replace_copy

• replace(debut, fin, ancienne_valeur, nouvelle_valeur) : remplace toutes les occurrences de ancienne_valeur par nouvelle_valeur.
• replace_if(debut, fin, prédicat, nouvelle_valeur) : remplace les éléments satisfaisant le prédicat.
• replace_copy(debut, fin, destination, ancienne_valeur, nouvelle_valeur) : copie en remplaçant les éléments (ne modifie pas le conteneur source).

std::vector<int> donnees = {1, 2, 3, 2, 5};

// Remplacement de tous les 2 par 20
std::replace(donnees.begin(), donnees.end(), 2, 20);  // donnees: [1,20,3,20,5]

// Remplacement des éléments >10 par 0
std::replace_if(donnees.begin(), donnees.end(), [](int x) {
    return x > 10;
}, 0);  // donnees: [1,0,3,0,5]

// Copie avec remplacement des 3 par 300 (conteneur source inchangé)
std::vector<int> resultat;
std::replace_copy(donnees.begin(), donnees.end(), std::back_inserter(resultat), 3, 300);  // resultat: [1,0,300,0,5]

2.4 remove, remove_if et erase

• remove(debut, fin, valeur) : "déplace" les éléments égaux à valeur vers la fin du conteneur, retourne un nouvel itérateur logique de fin (ne supprime pas réellement les éléments, doit être combiné avec erase).
• remove_if(debut, fin, prédicat) : déplace les éléments satisfaisant le prédicat vers la fin.

std::vector<int> donnees = {1, 2, 3, 2, 4};

// Suppression logique de tous les 2 (déplacement vers la fin)
auto nouvelle_fin = std::remove(donnees.begin(), donnees.end(), 2);  // donnees: [1,3,4,2,2]

// Suppression physique (vraiment supprimer les éléments)
donnees.erase(nouvelle_fin, donnees.end());  // donnees: [1,3,4]

// Suppression des nombres pairs avec lambda
donnees = {1, 2, 3, 4, 5};
donnees.erase(std::remove_if(donnees.begin(), donnees.end(), [](int x) {
    return x % 2 == 0;
}), donnees.end());  // donnees: [1,3,5]

2.5 unique

Supprime les éléments consécutifs en double dans une plage, retourne un nouvel itérateur logique de fin. Généralemetn utilisé avec erase.

std::vector<int> tableau = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto dernier = std::unique(tableau.begin(), tableau.end());
tableau.erase(dernier, tableau.end()); // tableau devient {1, 2, 3, 4, 5}

2.6 reverse

Inverse l'ordre des éléments dans une plage

std::vector<int> donnees = {1, 2, 3, 4, 5};
std::reverse(donnees.begin(), donnees.end()); // donnees devient {5, 4, 3, 2, 1}

2.7 rotate

Effectue une rotation des éléments dans une plage, de manière à ce que l'élément du milieu devienne le premier élément

std::vector<int> donnees = {1, 2, 3, 4, 5};
std::rotate(donnees.begin(), donnees.begin() + 2, donnees.end()); // Rotation avec 3 comme point de départ, donnees devient {3, 4, 5, 1, 2}

2.8 shuffle

Réorganise aléatoirement les éléments d'une plage (nécessite C++11 ou version supérieure)

#include <random>
#include <algorithm>

std::vector<int> donnees = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(donnees.begin(), donnees.end(), g); // Mélange aléatoire des éléments de donnees

3. Algorithmes de tri et associés

3.1 sort, stable_sort et partial_sort

• sort(debut, fin) : trie les éléments avec un tri rapide (instable, complexité temporelle moyenne O(n log n)).
• stable_sort(debut, fin) : tri stable (les éléments égaux conservent leur relative position).
• partial_sort(debut, milieu, fin) : tri partiel, rend [debut, milieu) les plus petits éléments de la plage triés.

std::vector<int> donnees = {5, 3, 1, 4, 2};
std::sort(donnees.begin(), donnees.end()); // Tri ascendant par défaut, donnees devient {1, 2, 3, 4, 5}
std::sort(donnees.begin(), donnees.end(), std::greater<int>()); // Tri descendant, donnees devient {5, 4, 3, 2, 1}
std::sort(donnees.begin(), donnees.end(), [](int a, int b) { 
    return a < b; 
}); // Tri ascendant, comparateur personnalisé

std::vector<std::pair<int, int>> donnees = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(donnees.begin(), donnees.end(), [](const auto& a, const auto& b) {
    return a.first < b.first; // Tri selon first, préservation de l'ordre relatif des éléments égaux
});

std::vector<int> donnees = {5, 3, 1, 4, 2, 6};
// Trie les 3 plus petits éléments et les place au début
std::partial_sort(donnees.begin(), donnees.begin() + 3, donnees.end());
// Maintenant les 3 premiers éléments de donnees sont 1, 2, 3, suivis des non triés 4, 5, 6

3.2 nth_element

Réorganise la plage de manière à ce que l'élément à la position spécifiée soit celui qu'on aurait après un tri complet, avec les éléments à gauche qui ne sont pas plus grands et ceux à droite qui ne sont pas plus petits.

std::vector<int> donnees = {5, 3, 1, 4, 2, 6};
// Trouve le 3ème plus petit élément (indice 2)
std::nth_element(donnees.begin(), donnees.begin() + 2, donnees.end());
// Maintenant donnees[2] est 3, les éléments à gauche sont <=3, ceux à droite >=3

3.3 binary_search, lower_bound, upper_bound

Doit être utilisé sur des conteneurs triés

• binary_search(debut, fin, valeur) : vérifie si valeur existe (retourne bool).
• lower_bound(debut, fin, valeur) : retourne un itérateur vers le premier élément non inférieur à valeur.
• upper_bound(debut, fin, valeur) : retourne un itérateur vers le premier élément supérieur à valeur.

std::vector<int> trie = {1, 3, 3, 5, 7};  // Doit être trié

// Vérifie si 3 existe
bool existe = std::binary_search(trie.begin(), trie.end(), 3);  // true

// Trouve le premier élément >=3
auto lb = std::lower_bound(trie.begin(), trie.end(), 3);
std::cout << "indice lower_bound: " << lb - trie.begin() << std::endl;  // Affiche : 1

// Trouve le premier élément >3
auto ub = std::upper_bound(trie.begin(), trie.end(), 3);
std::cout << "indice upper_bound: " << ub - trie.begin() << std::endl;  // Affiche : 3

3.4 merge

Fusionne deux plages triées dans un nouveau conteneur (en conservant le tri)

std::vector<int> a = {1, 3, 5};
std::vector<int> b = {2, 4, 6};
std::vector<int> fusionne(a.size() + b.size());

// Fusionne a et b (doivent être triés)
std::merge(a.begin(), a.end(), b.begin(), b.end(), fusionne.begin());  // fusionne: [1,2,3,4,5,6]

4. Algorithmes de tas

La STL fournit des algorithmes pour opérer sur des plages comme des tas, incluant make_heap, push_heap, pop_heap, sort_heap, etc.

std::vector<int> donnees = {4, 1, 3, 2, 5};
std::make_heap(donnees.begin(), donnees.end()); // Construit un tas max, donnees devient {5, 4, 3, 2, 1}

donnees.push_back(6);
std::push_heap(donnees.begin(), donnees.end()); // Ajoute le nouvel élément au tas, donnees devient {6, 4, 5, 2, 1, 3}

std::pop_heap(donnees.begin(), donnees.end()); // Déplace le plus grand élément à la fin, donnees devient {5, 4, 3, 2, 1, 6}
int max_val = donnees.back(); // Récupère le plus grand élément 6
donnees.pop_back(); // Supprime le plus grand élément

std::sort_heap(donnees.begin(), donnees.end()); // Trie le tas en séquence ascendante, donnees devient {1, 2, 3, 4, 5}

5. Algorithmes minimum/maximum

5.1 min et max

Retourne la plus petite/grande valeur de deux valeurs ou d'une liste d'initialisation

int x = 5, y = 3;
int min_val = std::min(x, y); // 3
int max_val = std::max(x, y); // 5

auto min_liste = std::min({4, 2, 8, 5, 1}); // 1
auto max_liste = std::max({4, 2, 8, 5, 1}); // 8

5.2 min_element et max_element

Retourne un itérateur vers le plus petit/grand élément d'une plage

std::vector<int> donnees = {3, 1, 4, 2, 5};
auto min_it = std::min_element(donnees.begin(), donnees.end()); // Pointe vers 1
auto max_it = std::max_element(donnees.begin(), donnees.end()); // Pointe vers 5

5.3 minmax_element (C++11)

Retourne simultanément les itérateurs vers le plus petit et le plus grand élément d'une plage

std::vector<int> donnees = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(donnees.begin(), donnees.end());
// minmax.first pointe vers 1, minmax.second pointe vers 5

6. Algorithmes numériques (dans )

6.1 accumulate

Calcule la somme cumulative des éléments d'une plage (ou une opération personnalisée)

#include <numeric>

std::vector<int> donnees = {1, 2, 3, 4, 5};
int somme = std::accumulate(donnees.begin(), donnees.end(), 0); // Somme, valeur initiale 0, résultat 15
int produit = std::accumulate(donnees.begin(), donnees.end(), 1, std::multiplies<int>()); // Produit, valeur initiale 1, résultat 120

6.2 inner_product

Calcule le produit scalaire de deux plages (ou une opération personnalisée)

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

6.3 iota

Remplit une plage avec des valeurs consécutives croissantes

std::vector<int> donnees(5);
std::iota(donnees.begin(), donnees.end(), 10); // Remplit avec 10, 11, 12, 13, 14

6.4 partial_sum

Calcule les sommes partielles et stocke les résultats dans une plage cible

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());
std::partial_sum(source.begin(), source.end(), destination.begin()); // destination devient {1, 3, 6, 10, 15}

6.5 adjacent_difference

Calcule la différence entre les éléments adjacents et stocke les résultats dans une plage cible

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());
std::adjacent_difference(source.begin(), source.end(), destination.begin()); // destination devient {1, 1, 1, 1, 1}

7. Autres

7.1 generate

Remplit une plage avec une fonction génératrice

std::vector<int> donnees(5);
int n = 0;
std::generate(donnees.begin(), donnees.end(), [&n]() { 
    return n++; 
}); // Remplit avec 0, 1, 2, 3, 4

7.2 generate_n

Remplit les n premiers éléments d'une plage avec une fonction génératrice

std::vector<int> donnees(5);
int n = 10;
std::generate_n(donnees.begin(), 3, [&n]() { 
    return n++; 
}); // Les 3 premiers éléments sont 10, 11, 12, les 2 derniers inchangés

7.3 includes

Vérifie si une plage triée contient tous les éléments d'une autre plage triée

std::vector<int> donnees1 = {1, 2, 3, 4, 5};
std::vector<int> donnees2 = {2, 4};
bool contient = std::includes(donnees1.begin(), donnees1.end(), donnees2.begin(), donnees2.end()); // true

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

Effectue des opérations ensemblistes : union, intersection, différence et différence symétrique

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> resultat;

// Union
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultat));
// resultat est {1, 2, 3, 4, 5, 6, 7}

// Intersection
resultat.clear();
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultat));
// resultat est {3, 4, 5}

// Différence (v1 - v2)
resultat.clear();
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultat));
// resultat est {1, 2}

// Différence symétrique (v1 ∪ v2 - v1 ∩ v2)
resultat.clear();
std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(resultat));
// resultat est {1, 2, 6, 7}

8. Problèmes courants

1. Quelle est la différence entre sort et stable_sort ?

• sort utilise un tri rapide (en réalité l'algorithme introsort), instable (la position relative des éléments égaux peut changer), complexité temporelle moyenne O(n log n).
• stable_sort utilise un tri par fusion, stable (la position relative des éléments égaux est préservée), complexité temporelle O(n log n), mais avec une légère surcharge d'espace.

2. Pourquoi l'algorithme remove doit-il être utilisé avec erase ? L'algorithme remove fonctionne par "remplacement" des éléments à supprimer, déplaçant les éléments à conserver vers l'avant et retournant un nouvel itérateur logique de fin, mais il ne modifie pas la taille réelle du conteneur. erase supprime réellement les éléments en utilisant la plage d'itérateurs et modifie la taille du conteneur. Par conséquent, ils doivent être combinés : conteneur.erase(remove(...), conteneur.end()).
3. Quels algorithmes nécessitent que le conteneur soit trié ? Les algorithmes de recherche binaire (binary_search, lower_bound, upper_bound), les algorithmes ensemblistes (set_intersection, set_union, etc.), et merge dépendent de l'ordre pour des opérations efficaces (comme la recherche binaire en O(log n)).