1. Algorithmes non modifiants
Ces algorithmes inspectent les éléments sans les modifier.
1.1 find, find_if et find_end
find(b, e, val): retourne un itérateur vers la première occurrence deval.find_if(b, e, pred): trouve le premier élément satisfaisant le prédicatpred.find_end(b, e, sb, se): localise la dernière occurrence d’une sous-séquence.
std::vector<int> data = {10, 20, 30, 40, 50};
auto pos = std::find(data.begin(), data.end(), 30);
if (pos != data.end()) {
std::cout << "Valeur trouvée : " << *pos << '\n';
}
auto gt40 = std::find_if(data.begin(), data.end(),
[](int x) { return x > 40; });
std::cout << "Premier >40 : " << *gt40 << '\n';
std::vector<int> pattern = {20, 30};
auto last_match = std::find_end(data.begin(), data.end(),
pattern.begin(), pattern.end());
if (last_match != data.end()) {
std::cout << "Début à l’indice : " << (last_match - data.begin()) << '\n';
}
1.2 count et count_if
Comptent les occurrences d’une valeur ou d’un critère.
std::vector<int> vals = {2, 4, 2, 6, 2, 8};
int twos = std::count(vals.begin(), vals.end(), 2); // 3
int evens = std::count_if(vals.begin(), vals.end(),
[](int x) { return x % 2 == 0; }); // 6
1.3 for_each
Applique une fonction à chaque élément.
std::vector<int> numbers = {1, 2, 3};
std::for_each(numbers.begin(), numbers.end(),
[](int& n) { n *= 10; });
// numbers = {10, 20, 30}
1.4 equal et mismatch
Compares two ranges for equality or first difference.
std::vector<int> x = {1, 2, 3}, y = {1, 2, 4};
bool same = std::equal(x.begin(), x.end(), y.begin()); // false
auto diff = std::mismatch(x.begin(), x.end(), y.begin());
if (diff.first != x.end())
std::cout << "Différence : " << *diff.first << " vs " << *diff.second << '\n';
1.5 all_of, any_of, none_of
Vérifient des conditions globales sur une plage.
std::vector<int> seq = {4, 6, 8};
bool all_even = std::all_of(seq.begin(), seq.end(),
[](int n) { return n % 2 == 0; }); // true
bool has_odd = std::any_of(seq.begin(), seq.end(),
[](int n) { return n % 2 == 1; }); // false
bool no_neg = std::none_of(seq.begin(), seq.end(),
[](int n) { return n < 0; }); // true
2. Algorithmes modifiants
2.1 copy et copy_if
Copient des éléments, conditionnellement ou non.
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> dest(5);
std::copy(source.begin(), source.end(), dest.begin());
std::vector<int> odds;
std::copy_if(source.begin(), source.end(), std::back_inserter(odds),
[](int n) { return n % 2 == 1; });
// odds = {1, 3, 5}
2.2 transform
Applique une transformation unaire ou binaire.
std::vector<int> input = {2, 3, 4};
std::vector<int> squares(input.size());
std::transform(input.begin(), input.end(), squares.begin(),
[](int x) { return x * x; });
std::vector<int> a = {1, 2}, b = {10, 20}, sum(2);
std::transform(a.begin(), a.end(), b.begin(), sum.begin(),
std::plus<int>());
// sum = {11, 22}
2.3 replace, replace_if, replace_copy
std::vector<int> items = {0, 1, 0, 2, 0};
std::replace(items.begin(), items.end(), 0, -1); // remplace 0 par -1
std::replace_if(items.begin(), items.end(),
[](int x) { return x < 0; }, 99);
std::vector<int> clean;
std::replace_copy(items.begin(), items.end(), std::back_inserter(clean),
99, 0);
2.4 remove, remove_if et erase
« Déplacent » les éléments à supprimer vers la fin (idiome erase-remove).
std::vector<int> list = {1, 2, 3, 2, 4, 2};
list.erase(
std::remove(list.begin(), list.end(), 2),
list.end()
); // list = {1, 3, 4}
// Suppression conditionnelle
list = {1, 2, 3, 4, 5};
list.erase(
std::remove_if(list.begin(), list.end(),
[](int x) { return x % 2 == 0; }),
list.end()
); // list = {1, 3, 5}
2.5 unique
Élimine les doublons consécutifs.
std::vector<int> dup = {1, 1, 2, 2, 2, 3};
dup.erase(std::unique(dup.begin(), dup.end()), dup.end());
// dup = {1, 2, 3}
2.6 reverse
Inverse l’ordre des éléments.
std::vector<int> rev = {1, 2, 3};
std::reverse(rev.begin(), rev.end()); // {3, 2, 1}
2.7 rotate
Fait pivoter autour d’un point donné.
std::vector<int> rot = {1, 2, 3, 4, 5};
std::rotate(rot.begin(), rot.begin() + 2, rot.end());
// rot = {3, 4, 5, 1, 2}
2.8 shuffle
Mélange aléatoirement les éléments.
#include <random>
std::vector<int> deck = {1, 2, 3, 4, 5};
std::shuffle(deck.begin(), deck.end(),
std::mt19937{std::random_device{}()});
3. Tri et algorithmes associés
3.1 sort, stable_sort, partial_sort
std::vector<int> arr = {5, 1, 4, 2, 3};
std::sort(arr.begin(), arr.end()); // {1,2,3,4,5}
std::sort(arr.begin(), arr.end(), std::greater<>()); // décroissant
std::vector<std::pair<int, char>> pairs = {{2,'b'}, {1,'a'}, {2,'c'}};
std::stable_sort(pairs.begin(), pairs.end(),
[](auto& a, auto& b) { return a.first < b.first; });
// ordre relatif conservé pour les clés égales
std::vector<int> part = {9, 1, 8, 2, 7, 3};
std::partial_sort(part.begin(), part.begin() + 3, part.end());
// les 3 plus petits sont triés au début
3.2 nth_element
Place l’élément médian à sa position finale dans un tri.
std::vector<int> v = {5, 6, 4, 3, 2, 1, 7};
std::nth_element(v.begin(), v.begin() + 3, v.end());
// v[3] est le 4e plus petit ; éléments à gauche ≤ v[3], à droite ≥ v[3]
3.3 Recherche dichotomique
Nécessite un conteneur trié.
std::vector<int> sorted = {1, 2, 2, 3, 4, 4, 4, 5};
bool found = std::binary_search(sorted.begin(), sorted.end(), 3); // true
auto low = std::lower_bound(sorted.begin(), sorted.end(), 4); // premier ≥4 → index 4
auto up = std::upper_bound(sorted.begin(), sorted.end(), 4); // premier >4 → index 7
3.4 merge
Fusionne deux plages triées.
std::vector<int> left = {1, 3, 5}, right = {2, 4, 6};
std::vector<int> merged(left.size() + right.size());
std::merge(left.begin(), left.end(), right.begin(), right.end(), merged.begin());
// merged = {1,2,3,4,5,6}
4. Algorithmes de tas
std::vector<int> heap = {1, 2, 3, 4, 5};
std::make_heap(heap.begin(), heap.end()); // max-heap : {5,4,3,1,2}
heap.push_back(6);
std::push_heap(heap.begin(), heap.end()); // réorganise
std::pop_heap(heap.begin(), heap.end()); // déplace max à la fin
int max_val = heap.back();
heap.pop_back();
std::sort_heap(heap.begin(), heap.end()); // trie en place
5. Min/Max
int a = 7, b = 3;
int m = std::min(a, b); // 3
int M = std::max({1, 5, 2, 9, 3}); // 9
std::vector<int> data = {5, 1, 9, 3};
auto min_it = std::min_element(data.begin(), data.end()); // → 1
auto max_it = std::max_element(data.begin(), data.end()); // → 9
auto mm = std::minmax_element(data.begin(), data.end());
// mm.first → 1, mm.second → 9
6. Algorithmes numériques (<numeric>)
#include <numeric>
std::vector<int> nums = {1, 2, 3, 4};
int total = std::accumulate(nums.begin(), nums.end(), 0); // 10
int prod = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>()); // 24
std::vector<int> u = {1, 2, 3}, v = {4, 5, 6};
int dot = std::inner_product(u.begin(), u.end(), v.begin(), 0); // 32
std::vector<int> seq(5);
std::iota(seq.begin(), seq.end(), 10); // {10,11,12,13,14}
std::vector<int> partial(5);
std::partial_sum(nums.begin(), nums.end(), partial.begin()); // {1,3,6,10}
std::vector<int> diffs(5);
std::adjacent_difference(nums.begin(), nums.end(), diffs.begin()); // {1,1,1,1}
7. Autres algorithmes
// Génération
std::vector<int> gen(4);
int counter = 0;
std::generate(gen.begin(), gen.end(), [&]() { return counter++; }); // {0,1,2,3}
std::vector<int> init(5);
std::generate_n(init.begin(), 3, [&counter]() { return counter++; }); // {3,4,5,?,?}
// Inclusion et opérations ensemblistes
std::vector<int> A = {1,2,3,4,5}, B = {2,4};
bool contains = std::includes(A.begin(), A.end(), B.begin(), B.end()); // true
std::vector<int> out;
std::set_union(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(out));
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(out));
std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(out));
std::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(out));
8. Points clés
sortest rapide mais instable ;stable_sortpréserve l’ordre des équivalents.- L’idiome
erase(remove(...), end())est nécessaire carremovene redimensionne pas le conteneur. - Les algorithmes de recherche dichotomique et ensemblistes exigent des entrées triées.