1. Algorithmes non modificaterus

---

Ces algorithmes n'altèrent pas les éléments des séquences qu'ils traitent.

1.1 Recherche avec find et find_if

L'algorithme find localise la première occurrence d'une valeur donnée. find_if cherche le premier élément satisfaisant un prédicat. find_end repère la dernière occurrence d'une sous-séquence.

vector<int> data = {1, 3, 5, 7, 9};

// Recherche de la valeur 5
auto pos = find(begin(data), end(data), 5);
if (pos != end(data)) {
    cout << "Trouvé: " << *pos << endl;  // Affiche: 5
}

// Premier élément supérieur à 6
auto pos_sup = find_if(begin(data), end(data), [](int val) {
    return val > 6;
});
cout << "Premier >6: " << *pos_sup << endl;  // Affiche: 7

// Recherche de la sous-séquence {3, 5}
vector<int> sequence = {3, 5};
auto pos_seq = find_end(begin(data), end(data), begin(sequence), end(sequence));
if (pos_seq != end(data)) {
    cout << "Sous-séquence à l'index: " << pos_seq - begin(data) << endl;  // Affiche: 1
}

1.2 Comptage avec count et count_if

count retourne le nombre d'éléments égaux à une valeur. count_if compte ceux satisfaisant une condition.

std::vector<int> collection = {1, 2, 3, 2, 4, 2};
int nombre = std::count(begin(collection), end(collection), 2); // 3 occurrences de 2
int nb_pairs = std::count_if(begin(collection), end(collection), [](int val) { 
    return val % 2 == 0; 
}); // 4 éléments pairs

1.3 Application d'une fonction avec for_each

Cet algorithme applique une opération à chaque élément de l'intervalle spécifié.

std::vector<int> valeurs = {1, 2, 3, 4, 5};
std::for_each(begin(valeurs), end(valeurs), [](int& val) { 
    val *= 2; // Double chaque valeur
});
// valeurs vaut maintenant {2, 4, 6, 8, 10}

1.4 Comparaison avec equal et mismatch

equal teste l'égalité de deux plages. ismatch renvoie la paire d'itérateurs au premier écart.

vector<int> seq1 = {1, 2, 3};
vector<int> seq2 = {1, 2, 4};
vector<int> seq3 = {1, 2, 3, 4};

// Comparaison des trois premiers éléments
bool identique = equal(begin(seq1), end(seq1), begin(seq2));
cout << "seq1 == seq2 ? " << boolalpha << identique << endl;  // false

// Premier élément divergent entre seq1 et seq3
auto ecart = mismatch(begin(seq1), end(seq1), begin(seq3));
if (ecart.first != end(seq1)) {
    cout << "Écart: " << *ecart.first << " vs " << *ecart.second << endl;
}

1.5 Vérifications avec all_of, any_of, none_of

Ces fonctions vérifient si tous, certains ou aucun élément répondent à un critère.

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

2. Algorithmes modificateurs

---

Ces opérations modifient les éléments des conteneurs.

2.1 Copie avec copy et copy_if

copy transfère tous les éléments. copy_if ne copie que ceux vérifiant une condition.

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

// Copie conditionnelle (uniquement les pairs)
copy_if(begin(source), end(source), back_inserter(destination), [](int x) {
    return x % 2 == 0;
}); // destination: [2,4]

2.2 Transformation avec transform

Applique une fonction de transformation sur une ou deux séquences et stocke le résultat.

vector<int> nombres = {1, 2, 3};
vector<int> carres(3);

// Calcul des carrés
transform(begin(nombres), end(nombres), begin(carres), [](int x) {
    return x * x;
}); // carres: [1,4,9]

// Addition de deux vecteurs
vector<int> vec1 = {1, 2, 3};
vector<int> vec2 = {4, 5, 6};
vector<int> somme(3);
transform(begin(vec1), end(vec1), begin(vec2), begin(somme), [](int a, int b) {
    return a + b;
}); // somme: [5,7,9]

2.3 Remplacement avec replace, replace_if et replace_copy

Ces fonctions substituent des valeurs, soit sur place, soit lors de la copie.

vector<int> serie = {1, 2, 3, 2, 5};

// Remplacement de toutes les occurrences de 2 par 20
replace(begin(serie), end(serie), 2, 20);  // serie: [1,20,3,20,5]

// Remplacement conditionnel (valeurs > 10 par 0)
replace_if(begin(serie), end(serie), [](int x) {
    return x > 10;
}, 0);  // serie: [1,0,3,0,5]

// Copie avec remplacement (3 devient 300)
vector<int> copie;
replace_copy(begin(serie), end(serie), back_inserter(copie), 3, 300);  // copie: [1,0,300,0,5]

2.4 Suppression logique avec remove et erase

remove déplace les éléments non désirés vers la fin et renvoie le nouveau point de fin. erase élimine physiquement ces éléments.

vector<int> tableau = {1, 2, 3, 2, 4};

// Déplacement des 2 à la fin
auto nouvelle_fin = remove(begin(tableau), end(tableau), 2);  // tableau: [1,3,4,2,2]

// Suppression effective des éléments en fin
tableau.erase(nouvelle_fin, end(tableau));  // tableau: [1,3,4]

// Combinaison pour supprimer les pairs
tableau = {1, 2, 3, 4, 5};
tableau.erase(remove_if(begin(tableau), end(tableau), [](int x) {
    return x % 2 == 0;
}), end(tableau));  // tableau: [1,3,5]

2.5 Élimination des doublons consécutifs avec unique

unique supprime les répétitions adjacentes et renvoie un itérateur de fin logique.

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

2.6 Inversion de séquence avec reverse

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

2.7 Rotation avec rotate

Fait pivoter les éléments autour d'un point spécifié.

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

2.8 Mélange aléatoire avec shuffle

#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); // Réordonne aléatoirement les éléments

3. Algorithmes de tri

---

3.1 Tri général avec sort, stable_sort et partial_sort

sort utilise un tri rapide (introsort). stable_sort préserve l'ordre relatif des éléments égaux. partial_sort trie seulement une partie de la séquence.

std::vector<int> donnees = {5, 3, 1, 4, 2};
std::sort(begin(donnees), end(donnees)); // Tri ascendant

// Tri avec critère personnalisé
std::sort(begin(donnees), end(donnees), [](int a, int b) { 
    return a > b; 
}); // Tri descendant

// Tri stable de paires
std::vector<std::pair<int, int>> paires = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(begin(paires), end(paires), [](const auto& p1, const auto& p2) {
    return p1.first < p2.first;
});

// Tri partiel (les 3 plus petits éléments)
std::vector<int> valeurs = {5, 3, 1, 4, 2, 6};
std::partial_sort(begin(valeurs), begin(valeurs) + 3, end(valeurs));
// Les trois premières valeurs sont maintenant {1, 2, 3}

3.2 Sélection de l'élément n-ième avec nth_element

Réorganise les éléments de sorte que la position spécifiée contienne l'élément qui y serait si la séquence était triée.

std::vector<int> donnees = {5, 3, 1, 4, 2, 6};
std::nth_element(begin(donnees), begin(donnees) + 2, end(donnees));
// donnees[2] est maintenant 3 (le 3ème plus petit élément)

3.3 Recherche binaire dans une séquence triée

Ces algorithmes nécessitent une séquence préalablement triée.

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

// Test d'existence
bool present = binary_search(begin(sorted), end(sorted), 3); // true

// Première position >= 3
auto borne_inf = lower_bound(begin(sorted), end(sorted), 3);
cout << "Index borne inf: " << borne_inf - begin(sorted) << endl; // 1

// Première position > 3
auto borne_sup = upper_bound(begin(sorted), end(sorted), 3);
cout << "Index borne sup: " << borne_sup - begin(sorted) << endl; // 3

3.4 Fusion de séquences triées avec merge

vector<int> premier = {1, 3, 5};
vector<int> second = {2, 4, 6};
vector<int> fusionne(premier.size() + second.size());

merge(begin(premier), end(premier), begin(second), end(second), begin(fusionne));
// fusionne: [1,2,3,4,5,6]

4. Manipulation de tas (heap)

---

Ces algorithmes permettent de gérer une séquence comme un tas (priorité max ou min).

std::vector<int> tas = {4, 1, 3, 2, 5};
std::make_heap(begin(tas), end(tas)); // Crée un tas max, tas: {5, 4, 3, 2, 1}

tas.push_back(6);
std::push_heap(begin(tas), end(tas)); // Ajout dans le tas, tas: {6, 4, 5, 2, 1, 3}

std::pop_heap(begin(tas), end(tas)); // Déplace le max à la fin, tas: {5, 4, 3, 2, 1, 6}
int valeur_max = tas.back(); // Récupère le max (6)
tas.pop_back(); // Supprime le max

std::sort_heap(begin(tas), end(tas)); // Trie la séquence, tas: {1, 2, 3, 4, 5}

5. Algorithmes de valeurs extrêmes

---

5.1 min et max

Retuornent le minimum ou le maximum entre deux valeurs ou dans 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

Localisent l'élément minimum ou maximum dans une plage.

std::vector<int> seq = {3, 1, 4, 2, 5};
auto iter_min = std::min_element(begin(seq), end(seq)); // Pointe vers 1
auto iter_max = std::max_element(begin(seq), end(seq)); // Pointe vers 5

5.3 minmax_element

Retourne simultanément les itérateurs vers les éléments minimum et maximum.

std::vector<int> seq = {3, 1, 4, 2, 5};
auto extremas = std::minmax_element(begin(seq), end(seq));
// extremas.first -> 1, extremas.second -> 5

6. Algorithmes numériques (header <numeric>)

---

6.1 Accumulation avec accumulate

#include <numeric>

std::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<int>()); // 120

6.2 Produit scalaire avec inner_product

std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};
int scalaire = std::inner_product(begin(vec1), end(vec1), begin(vec2), 0); // 32

6.3 Remplissage séquentiel avec iota

std::vector<int> sequence(5);
std::iota(begin(sequence), end(sequence), 10); // {10, 11, 12, 13, 14}

6.4 Sommes partielles avec partial_sum

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

6.5 Différences adjacentes avec adjacent_difference

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

7. Algorithmes divers

---

7.1 Génération avec generate

Remplit une plage avec les valeurs produites par une fonction.

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

7.2 Génération partielle avec generate_n

std::vector<int> sortie(5);
int valeur = 10;
std::generate_n(begin(sortie), 3, [&valeur]() { 
    return valeur++; 
}); // Les trois premiers éléments: 10, 11, 12

7.3 Vérification d'inclusion avec includes

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

7.4 Opérations ensemblistes

Ces algorithmes effectuent des opérations sur des ensembles triés.

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

// Union
std::set_union(begin(set1), end(set1), begin(set2), end(set2), back_inserter(resultat));
// resultat: {1, 2, 3, 4, 5, 6, 7}

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

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

// Différence symétrique
resultat.clear();
std::set_symmetric_difference(begin(set1), end(set1), begin(set2), end(set2), back_inserter(resultat));
// resultat: {1, 2, 6, 7}

8. Questions fréquentes

---

1. Quelle différence entre sort et stable_sort ?
   sort utilise un tri rapide (introsort), non stable, complexité moyenne O(n log n). stable_sort est basé sur le tri fusion, stable, même complexité mais plus gourmand en mémoire.
2. Pourquoi faut-il combiner remove et erase ?
   remove déplace les éléments à conserver vers le début, mais ne modifie pas la taille du conteneur. erase supprime physiquement les éléments restants en fin. D'où l'usage combiné : conteneur.erase(remove(...), conteneur.end()).
3. Quels algorithmes nécessitent une séquence triée ?
   La recherche binaire (binary_search, lower_bound, upper_bound), les opérations ensemblistes (set_intersection, etc.), et merge requièrent une séquence ordonnée pour fonctionner efficacement.