Ces algorithmes analysent ou recherchent des éléments sans altérer le contenu du conteneur.

Recherche d’éléments : find, find_if, find_end

• find(first, last, val) : retourne l’itérateur du premier élément égal à val, ou last s’il n’est pas trouvé.
• find_if(first, last, pred) : localsie le premier élément satisfaisant un prédicat.
• find_end(first1, last1, first2, last2) : trouve la dernière occurrence d’une sous-séquence.

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

auto pos = std::find(data.begin(), data.end(), 5);
if (pos != data.end()) {
    std::cout << "Trouvé : " << *pos << '\n'; // Affiche : 5
}

auto gt6 = std::find_if(data.begin(), data.end(), [](int n) { return n > 6; });
std::cout << "Premier >6 : " << *gt6 << '\n'; // Affiche : 7

std::vector<int> pattern = {3, 5};
auto subpos = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (subpos != data.end()) {
    std::cout << "Sous-séquence débutant à l’indice : " << (subpos - data.begin()) << '\n'; // Affiche : 1
}

Comptage : count, count_if

• count(first, last, val) : compte les occurrences de val.
• count_if(first, last, pred) : compte les éléments répondant à un prédicat.

std::vector<int> sample = {1, 2, 3, 2, 4, 2};
int twos = std::count(sample.begin(), sample.end(), 2);           // Résultat : 3
int evens = std::count_if(sample.begin(), sample.end(), [](int x) { 
    return (x & 1) == 0; 
}); // Résultat : 4

Application de fonction : for_each

Applique une fonction à chaque élément du domaine.

std::vector<int> values = {1, 2, 3, 4, 5};
std::for_each(values.begin(), values.end(), [](int& x) {
    x += 10; // Ajoute 10 à chaque élément
});
// values devient {11, 12, 13, 14, 15}

Comparaison : equal, mismatch

• equal(range1, range2) : vérifie si deux séquences sont identiques.
• mismatch(range1, range2) : retourne un pair des premiers itérateurs divergents.

std::vector<int> A = {1, 2, 3};
std::vector<int> B = {1, 2, 4};
std::vector<int> C = {1, 2, 3, 4};

bool match = std::equal(A.begin(), A.end(), B.begin()); // false

auto diff = std::mismatch(A.begin(), A.end(), C.begin());
if (diff.first != A.end()) {
    std::cout << "Divergence : " << *diff.first << " vs " << *diff.second << '\n';
} // Aucune sortie : les trois premiers éléments sont identiques

Quantification universelle : all_of, any_of, none_of

• all_of : tous les éléments satisfont le prédicat.
• any_of : au moins un élément satisfait le prédicat.
• none_of : aucun élément ne satisfait le prédicat.

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

Algorithmes modificateurs de séquence

Ces algorithmes modifient directement ou indirectement les éléments du conteneur.

Copie conditionnelle : copy, copy_if

• copy(src_first, src_last, dest) : copie tous les éléments.
• copy_if(src_first, src_last, dest, pred) : copie uniquement les éléments validés par un prédicat.

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> target(5);

std::copy(source.begin(), source.end(), target.begin()); // target = {1,2,3,4,5}

std::vector<int> filtered;
std::copy_if(source.begin(), source.end(), std::back_inserter(filtered), [](int x) {
    return x % 2 == 0;
}); // filtered = {2, 4}

Transformation : transform

Applique une fonction à chaque élément et stocke le résultat dans une autre séquence.

std::vector<int> input = {1, 2, 3};
std::vector<int> output(input.size());

std::transform(input.begin(), input.end(), output.begin(), [](int x) {
    return x * x;
}); // output = {1, 4, 9}

std::vector<int> x = {1, 2, 3};
std::vector<int> y = {4, 5, 6};
std::vector<int> sum(x.size());

std::transform(x.begin(), x.end(), y.begin(), sum.begin(), std::plus<>{});
// sum = {5, 7, 9}

Remplacement : replace, replace_if, replace_copy

• replace : remplace toutes les occurrences d’une valeur.
• replace_if : remplace les éléments répondant à un prédicat.
• replace_copy : copie avec remplacement, sans modifier l’origine.

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

std::replace(data.begin(), data.end(), 2, 20); // {1, 20, 3, 20, 5}

std::replace_if(data.begin(), data.end(), [](int x) { return x > 10; }, 0); // {1, 0, 3, 0, 5}

std::vector<int> copy;
std::replace_copy(data.begin(), data.end(), std::back_inserter(copy), 3, 300); // {1, 0, 300, 0, 5}

Suppression logique : remove, remove_if, erase

Les algorithmes remove et remove_if déplacent les éléments à conserver vers le début, et retournent un itérateur pointant après la dernière valeur conservée. La suppression physique nécessite erase.

std::vector<int> data = {1, 2, 3, 2, 4};
auto new_end = std::remove(data.begin(), data.end(), 2); // {1, 3, 4, 2, 2}
data.erase(new_end, data.end()); // {1, 3, 4}

// Suppression des pairs en une ligne :
data = {1, 2, 3, 4, 5};
data.erase(std::remove_if(data.begin(), data.end(), [](int x) { return x % 2 == 0; }), data.end());
// Résultat : {1, 3, 5}

Élimination des doublons consécutifs : unique

Supprime les éléments identiques adjacents. Doit être combiné avec erase.

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

Renversement et rotation : reverse, rotate

• reverse : inverse l’ordre des éléments.
• rotate : fait tourner les éléments autour d’un point central.

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

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

Mélange aléatoire : shuffle

Nécessite un moteur de génération aléatoire (C++11+).

#include <random>

std::vector<int> deck = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 rng(rd());
std::shuffle(deck.begin(), deck.end(), rng); // Ordre aléatoire

Algorithmes de tri

Triage : sort, stable_sort, partial_sort

• sort : tri rapide (non stable).
• stable_sort : tri fusion (stable, conservant l’ordre des égaux).
• partial_sort : trie les n premiers éléments comme les plus petits.

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

std::vector<std::pair<int, int>> pairs = {{1,2}, {2,1}, {1,1}, {2,2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
}); // Trie par clé, conserve l’ordre des paires ayant la même clé

std::vector<int> top3 = {5, 3, 1, 4, 2, 6};
std::partial_sort(top3.begin(), top3.begin() + 3, top3.end());
// top3[0..2] = {1, 2, 3} ; les autres restent non triés

Partitionnement par quantile : nth_element

Place l’élément à la position n comme s’il était trié, avec les éléments plus petits à gauche et plus grands à droite.

std::vector<int> data = {5, 3, 1, 4, 2, 6};
std::nth_element(data.begin(), data.begin() + 2, data.end());
// data[2] contient la troisième plus petite valeur (3)
// Tous les éléments avant sont ≤ 3, tous après ≥ 3

Recherche binaire : binary_search, lower_bound, upper_bound

Exigent que le conteneur soit trié.

std::vector<int> sorted = {1, 3, 3, 5, 7};

bool found = std::binary_search(sorted.begin(), sorted.end(), 3); // true

auto low = std::lower_bound(sorted.begin(), sorted.end(), 3); // premier ≥ 3 → index 1
auto up = std::upper_bound(sorted.begin(), sorted.end(), 3);  // premier > 3 → index 3

Fusion : merge

Combine deux séquences triées en une seule triée.

std::vector<int> left = {1, 3, 5};
std::vector<int> right = {2, 4, 6};
std::vector<int> result(left.size() + right.size());

std::merge(left.begin(), left.end(), right.begin(), right.end(), result.begin());
// result = {1, 2, 3, 4, 5, 6}

Algorithmes de tas

Permettent de gérer un tas max via des itérateurs.

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

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

std::pop_heap(heap.begin(), heap.end()); // {5, 4, 3, 2, 1, 6}
int max = heap.back(); heap.pop_back(); // max = 6, heap = {5, 4, 3, 2, 1}

std::sort_heap(heap.begin(), heap.end()); // {1, 2, 3, 4, 5}

Recherche de min/max

min, max, minmax_element

• min(a, b) et max(a, b) : comparaison de deux valeurs.
• min_element et max_element : itérateurs vers les extrêmes.
• minmax_element : retourne un pair des deux en une seule passe.

std::vector<int> nums = {3, 1, 4, 2, 5};
auto extremes = std::minmax_element(nums.begin(), nums.end());
int min_val = *extremes.first;  // 1
int max_val = *extremes.second; // 5

Algorithmes numériques

Accumulation : accumulate

Effectue une opération binaire cumulative sur une séquence.

#include <numeric>

std::vector<int> data = {1, 2, 3, 4, 5};
int total = std::accumulate(data.begin(), data.end(), 0); // 15

int product = std::accumulate(data.begin(), data.end(), 1, std::multiplies<>{}); // 120

Produit scalaire : inner_product

Calcule la somme des produits élément par élément.

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

Remplissage incrémental : iota

Remplit une séquence avec une suite arithmétique.

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

Sommes partielles : partial_sum

Calcule les sommes cumulées.

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

Différences adjacentes : adjacant_difference

Calcule les différences entre éléments consécutifs.

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

Autres algorithmes utiles

Remplissage dynamique : generate, generate_n

Utilise une fonction pour produire les valeurs.

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

std::vector<int> other(5);
int start = 10;
std::generate_n(other.begin(), 3, [&start]() { return start++; }); // {10,11,12,0,0}

Tests d’inclusion et opérations ensemblistes

• includes : vérifie si un ensemble trié contient un autre.
• set_union, set_intersection, set_difference, set_symmetric_difference : opérations sur ensembles triés.

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

std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result));
// result = {3, 4, 5}

std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result));
// result = {1, 2, 6, 7}