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

1.1 Recherche d'éléments

• find(begin, end, value) : Recherche le premier élément égal à value et renvoie un itérateur (ou end si non trouvé).
• find_if(begin, end, predicate) : Recherche le premier élément satisfaisant le prédicat.
• find_end(begin, end, sub_begin, sub_end) : Recherche la dernière occurrence d'une sous-séquence.

std::vector<double> donnees = {2.5, 4.1, 6.7, 8.3, 10.0};

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

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

// Recherche d'une sous-séquence
std::vector<double> sous = {4.1, 6.7};
auto it3 = std::find_end(donnees.begin(), donnees.end(), sous.begin(), sous.end());
if (it3 != donnees.end()) {
    std::cout << "Sous-séquence à l'index : " << it3 - donnees.begin() << std::endl;  // Affiche : 1
}

1.2 Comptage d'éléments

• count(begin, end, value) : Compte le nombre d'éléments égaux à value.
• count_if(begin, end, predicate) : Compte le nombre d'éléments satisfaisant le prédicat.

std::vector<int> chiffres = {5, 8, 2, 8, 3, 8};
int total = std::count(chiffres.begin(), chiffres.end(), 8); // Compte les 8, résultat 3
int paire = std::count_if(chiffres.begin(), chiffres.end(), [](int x) {
    return x % 2 == 0;
}); // Compte les nombres pairs, résultat 3

1.3 Application de fonction

for_each(begin, end, function) applique une fonction à chaque élément dans la plage.

std::vector<int> nombres = {10, 20, 30};
std::for_each(nombres.begin(), nombres.end(), [](int& x) {
    x += 5; // Ajoute 5 à chaque élément
});
// nombres devient {15, 25, 35}

1.4 Comparaison de plages

• equal(b1, e1, b2) : Vérifie si deux plages sont égales.
• mismatch(b1, e1, b2) : Retourne la paire d'itérateurs au premier désaccord.

std::vector<int> seq1 = {1, 3, 5};
std::vector<int> seq2 = {1, 3, 7};
std::vector<int> seq3 = {1, 3, 5, 9};

// Comparaison des plages seq1 et seq2
bool egal = std::equal(seq1.begin(), seq1.end(), seq2.begin());
std::cout << "seq1 == seq2 ? " << std::boolalpha << egal << std::endl;  // Affiche : false

// Recherche du premier désaccord entre seq1 et seq3
auto diff = std::mismatch(seq1.begin(), seq1.end(), seq3.begin());
if (diff.first != seq1.end()) {
    std::cout << "Désaccord : " << *diff.first << " vs " << *diff.second << std::endl;
}

1.5 Vérifications conditionnelles

all_of, any_of, none_of vérifient si tous, au moins un, ou aucun élément satisfont une condition.

std::vector<int> liste = {4, 8, 12, 16};
bool tous_positifs = std::all_of(liste.begin(), liste.end(), [](int x) {
    return x > 0;
}); // true
bool aucun_negatif = std::none_of(liste.begin(), liste.end(), [](int x) {
    return x < 0;
}); // true

2. Algorithmes modificateurs

---

Ces algorithmes modifient les éléments des conteneurs.

2.1 Copie d'éléments

• copy(begin, end, dest) : Copie les éléments dans une destination.
• copy_if(begin, end, dest, predicate) : Copie les éléments satisfaisant un prédicat.

std::vector<int> source = {10, 20, 30, 40, 50};
std::vector<int> copie;

// Copie conditionnelle des éléments supérieurs à 25
std::copy_if(source.begin(), source.end(), std::back_inserter(copie), [](int x) {
    return x > 25;
}); // copie contient {30, 40, 50}

2.2 Transformation

transform(begin, end, dest, function) applique une fonction et stocke les résultats.

std::vector<int> entrees = {2, 3, 4};
std::vector<int> resultats(entrees.size());

// Calcul des cubes
std::transform(entrees.begin(), entrees.end(), resultats.begin(), [](int x) {
    return x * x * x;
}); // resultats = {8, 27, 64}

// Combinaison de deux conteneurs
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {10, 20, 30};
std::vector<int> somme(3);
std::transform(a.begin(), a.end(), b.begin(), somme.begin(), [](int x, int y) {
    return x + y;
}); // somme = {11, 22, 33}

2.3 Remplacement

• replace(begin, end, old_val, new_val) : Remplace toutes les occurrences.
• replace_if(begin, end, predicate, new_val) : Remplace selon une condition.

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

// Remplacer tous les 2 par 200
std::replace(valeurs.begin(), valeurs.end(), 2, 200); // valeurs = {1, 200, 200, 3, 4}

// Remplacer les éléments pairs par 0
std::replace_if(valeurs.begin(), valeurs.end(), [](int x) {
    return x % 2 == 0;
}, 0); // valeurs = {1, 0, 0, 3, 0}

2.4 Suppression d'éléments

remove et remove_if déplacent les éléments à supprimer vers la fin, nécessitant erase pour une suppression physique.

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

// Suppression logique des 5
auto nouvelle_fin = std::remove(elements.begin(), elements.end(), 5); // elements = {1, 3, 2, 5, 5, 5}

// Suppression physique
elements.erase(nouvelle_fin, elements.end()); // elements = {1, 3, 2}

// Suppression conditionnelle des nombres impairs
std::vector<int> donnees = {1, 2, 3, 4, 5};
donnees.erase(std::remove_if(donnees.begin(), donnees.end(), [](int x) {
    return x % 2 != 0;
}), donnees.end()); // donnees = {2, 4}

2.5 Dédoublonnage

unique supprime les éléments consécutifs dupliqués, souvent utilisé avec erase.

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

2.6 Inversion et rotation

• reverse(begin, end) : Inverse l'ordre des éléments.
• rotate(begin, new_first, end) : Effectue une rotation des éléments.

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

std::rotate(seq.begin(), seq.begin() + 3, seq.end()); // Rotation, seq = {2, 1, 5, 4, 3}

3. Algorithmes de tri et de recherche

---

3.1 Tri

• sort(begin, end) : Tri non stable (introsort).
• stable_sort(begin, end) : Tri stable (merge sort).
• partial_sort(begin, mid, end) : Trie partiellement la plage.

std::vector<int> data = {30, 10, 50, 20, 40};
std::sort(data.begin(), data.end()); // Tri ascendant : {10, 20, 30, 40, 50}

// Tri avec comparateur personnalisé
std::sort(data.begin(), data.end(), [](int a, int b) {
    return a > b;
}); // Tri descendant : {50, 40, 30, 20, 10}

// Tri stable pour conserver l'ordre des éléments égaux
std::vector<std::pair<int, std::string>> paires = {{2, "b"}, {1, "a"}, {1, "c"}};
std::stable_sort(paires.begin(), paires.end(), [](const auto& x, const auto& y) {
    return x.first < y.first;
}); // L'ordre de "a" et "c" est préservé

3.2 Recherche binaire

Les algorithmes suivants nécessitent une plage triée.

• binary_search(begin, end, value) : Vérifie l'existence.
• lower_bound(begin, end, value) : Premier élément non inférieur.
• upper_bound(begin, end, value) : Premier élément supérieur.

std::vector<int> trie = {10, 20, 20, 30, 40}; // Déjà trié

// Vérifier si 20 existe
bool present = std::binary_search(trie.begin(), trie.end(), 20); // true

// Trouver la première occurrence >= 20
auto lb = std::lower_bound(trie.begin(), trie.end(), 20); // Pointe vers le premier 20

// Trouver le premier > 20
auto ub = std::upper_bound(trie.begin(), trie.end(), 20); // Pointe vers 30

3.3 Fusion de plages triées

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

std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> fusion(v1.size() + v2.size());
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), fusion.begin()); // fusion = {1, 2, 3, 4, 5, 6}

4. Algorithmes numériques

---

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

4.1 Accumulation

#include <numeric>
#include <vector>

std::vector<int> vals = {5, 10, 15};
int somme = std::accumulate(vals.begin(), vals.end(), 0); // 30
int produit = std::accumulate(vals.begin(), vals.end(), 1, std::multiplies<int>()); // 750

4.2 Produit scalaire

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

4.3 Remplissage séquentiel

std::vector<int> seq(5);
std::iota(seq.begin(), seq.end(), 100); // seq = {100, 101, 102, 103, 104}

4.4 Sommes partielles

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

5. Autres algorithmes

---

5.1 Génération

std::vector<int> vec(5);
int compteur = 10;
std::generate_n(vec.begin(), 3, [&compteur]() { return compteur--; }); // vec = {10, 9, 8, ?, ?}

5.2 Inclusion et opérations ensemblistes

std::vector<int> ensemble1 = {1, 2, 3, 4};
std::vector<int> ensemble2 = {3, 4, 5, 6};
std::vector<int> resultat;

// Union
std::set_union(ensemble1.begin(), ensemble1.end(), ensemble2.begin(), ensemble2.end(), std::back_inserter(resultat));
// resultat = {1, 2, 3, 4, 5, 6}

// Intersection
resultat.clear();
std::set_intersection(ensemble1.begin(), ensemble1.end(), ensemble2.begin(), ensemble2.end(), std::back_inserter(resultat));
// resultat = {3, 4}

6. Questions fréquentes

---

• Différence entre sort et stable_sort ? sort est rapide mais non stable ; stable_sort préserve l'ordre des éléments égaux.
• Pourquoi utiliser erase avec remove ? remove ne réduit pas la taille du conteneur ; erase supprime physiquement les éléments.
• Algorithmes nécessitant des données triées ? Les recherches binaires et les opérations ensemblistes.