Algorithmes de séquence non modifiante

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

find et find_if

find(begin, end, value) localise le premier élément égal à value et retourne un itérateur. find_if(begin, end, predicate) recherche le premier élément satisfaisant un prédicat. find_end(begin, end, sub_begin, sub_end) identifie la dernière occurence d'une sous-séquence.

vector<int> data = {1, 3, 5, 7, 9};
auto it = find(begin(data), end(data), 5);
if (it != end(data)) {
    cout << "found: " << *it << endl;
}

auto it2 = find_if(begin(data), end(data), [](int x) { return x > 6; });
cout << "first >6: " << *it2 << endl;

vector<int> subseq = {3, 5};
auto it3 = find_end(begin(data), end(data), begin(subseq), end(subseq));
if (it3 != end(data)) {
    cout << "subsequence index: " << it3 - begin(data) << endl;
}

count et count_if

count(begin, end, value) dénombre les éléments égaux à value. count_if(begin, end, predicate) compte les éléments vérifiant une condition.

vector<int> seq = {1, 2, 3, 2, 4, 2};
int two_count = count(begin(seq), end(seq), 2);
int even_count = count_if(begin(seq), end(seq), [](int x) { return x % 2 == 0; });

for_each

Applique une fonction à chaque élément de l'intervalle.

vector<int> values = {1, 2, 3, 4, 5};
for_each(begin(values), end(values), [](int& v) { v *= 2; });

equal et mismatch

equal(b1, e1, b2) compare deux intervalles pour l'égalité. mismatch(b1, e1, b2) retourne la première paire d'itérateurs où les éléments diffèrent.

vector<int> first = {1, 2, 3};
vector<int> second = {1, 2, 4};
vector<int> third = {1, 2, 3, 4};

bool eq = equal(begin(first), end(first), begin(second));
auto mismatch_pair = mismatch(begin(first), end(first), begin(third));

all_of, any_of, none_of

Vérifient si tous, certains ou aucun des éléments satisfont une condition.

vector<int> collection = {2, 4, 6, 8};
bool all_even = all_of(begin(collection), end(collection), [](int x) { return x % 2 == 0; });
bool any_negative = any_of(begin(collection), end(collection), [](int x) { return x < 0; });
bool none_positive = none_of(begin(collection), end(collection), [](int x) { return x > 0; });

Algorithmes de séquence modifiante

Ces algorithmes altèrent les éléments du conteneur.

copy et copy_if

copy(begin, end, dest) copie les éléments. copy_if(begin, end, dest, predicate) ne copie que ceux saitsfaisant un prédicat.

vector<int> source = {1, 2, 3, 4, 5};
vector<int> destination(source.size());
copy(begin(source), end(source), begin(destination));

vector<int> even_numbers;
copy_if(begin(source), end(source), back_inserter(even_numbers), [](int x) { return x % 2 == 0; });

transform

Applique une fonction à chaque élément et stocke les résultats dans un autre intervalle.

vector<int> base = {1, 2, 3};
vector<int> squares(base.size());
transform(begin(base), end(base), begin(squares), [](int x) { return x * x; });

vector<int> vec1 = {1, 2, 3};
vector<int> vec2 = {4, 5, 6};
vector<int> sums(vec1.size());
transform(begin(vec1), end(vec1), begin(vec2), begin(sums), [](int a, int b) { return a + b; });

replace, replace_if et replace_copy

replace remplace toutes les occurrences d'une valeur. replace_if remplace les éléments vérifiant un prédicat. replace_copy effectue une copie modifiée.

vector<int> arr = {1, 2, 3, 2, 5};
replace(begin(arr), end(arr), 2, 20);
replace_if(begin(arr), end(arr), [](int x) { return x > 10; }, 0);

vector<int> new_arr;
replace_copy(begin(arr), end(arr), back_inserter(new_arr), 3, 300);

remove, remove_if et erase

remove déplace les éléments à supprimer vers la fin et retourne le nouvel itérateur de fin. Nécessite erase pour la suppression effective.

vector<int> numbers = {1, 2, 3, 2, 4};
auto logical_end = remove(begin(numbers), end(numbers), 2);
numbers.erase(logical_end, end(numbers));

numbers = {1, 2, 3, 4, 5};
numbers.erase(remove_if(begin(numbers), end(numbers), [](int x) { return x % 2 == 0; }), end(numbers));

unique

Élimine les éléments consécutifs en doublon.

vector<int> with_dupes = {1, 1, 2, 2, 3, 3, 4, 5};
auto new_end_unique = unique(begin(with_dupes), end(with_dupes));
with_dupes.erase(new_end_unique, end(with_dupes));

reverse

Inverse l'ordre des éléments.

vector<int> to_reverse = {1, 2, 3, 4, 5};
reverse(begin(to_reverse), end(to_reverse));

rotate

Fait pivoter les éléments d'un intervalle.

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

shuffle

Réarrange aléatoirement les éléments (nécessite C++11).

#include <random>
vector<int> deck = {1, 2, 3, 4, 5};
random_device rd;
mt19937 rng(rd());
shuffle(begin(deck), end(deck), rng);

Algorithmes de tri et associés

sort, stable_sort et partial_sort

sort trie (non stable). stable_sort conserve l'ordre relatif des éléments égaux. partial_sort trie partiellement.

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

vector<int> partial_data = {5, 3, 1, 4, 2, 6};
partial_sort(begin(partial_data), begin(partial_data) + 3, end(partial_data));

nth_element

Positionne le n-ième élément de l'intervalle trié, avec les éléments plus petits avant et les plus grands après.

vector<int> elements = {5, 3, 1, 4, 2, 6};
nth_element(begin(elements), begin(elements) + 2, end(elements));

binary_search, lower_bound, upper_bound

Doivent être utilisés sur un intervalle trié. binary_search vérifie l'existence. lower_bound reoturne le premier élément non inférieur. upper_bound retourne le premier élément supérieur.

vector<int> sorted_seq = {1, 3, 3, 5, 7};
bool exists = binary_search(begin(sorted_seq), end(sorted_seq), 3);
auto lb = lower_bound(begin(sorted_seq), end(sorted_seq), 3);
auto ub = upper_bound(begin(sorted_seq), end(sorted_seq), 3);

merge

Fusionne deux intervalles triés dans un conteneur de destination.

vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6};
vector<int> merged(a.size() + b.size());
merge(begin(a), end(a), begin(b), end(b), begin(merged));

Algorithmes de tas

Manipulent un intervalle sous forme de tas (heap).

vector<int> heap_vec = {4, 1, 3, 2, 5};
make_heap(begin(heap_vec), end(heap_vec));

heap_vec.push_back(6);
push_heap(begin(heap_vec), end(heap_vec));

pop_heap(begin(heap_vec), end(heap_vec));
int max_val = heap_vec.back();
heap_vec.pop_back();

sort_heap(begin(heap_vec), end(heap_vec));

Algorithmes de minimum/maximum

min et max

Retournent le minimum ou le maximum de deux valeurs ou d'une liste d'initialisation.

int min_val = min(5, 3);
int max_val = max(5, 3);
auto min_list = min({4, 2, 8, 5, 1});
auto max_list = max({4, 2, 8, 5, 1});

min_element et max_element

Retournent un itérateur vers l'élément minimum ou maximum dans un intervalle.

vector<int> minmax_vec = {3, 1, 4, 2, 5};
auto min_it = min_element(begin(minmax_vec), end(minmax_vec));
auto max_it = max_element(begin(minmax_vec), end(minmax_vec));

minmax_element (C++11)

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

vector<int> mm_vec = {3, 1, 4, 2, 5};
auto minmax_pair = minmax_element(begin(mm_vec), end(mm_vec));

Algorithmes numériques (dans <numeric>)

accumulate

Calcule la somme cumulative (ou une opération personnalisée).

#include <numeric>
vector<int> nums = {1, 2, 3, 4, 5};
int sum = accumulate(begin(nums), end(nums), 0);
int product = accumulate(begin(nums), end(nums), 1, multiplies<int>());

inner_product

Calcule le produit scalaire de deux intervalles.

vector<int> v1 = {1, 2, 3};
vector<int> v2 = {4, 5, 6};
int dot_product = inner_product(begin(v1), end(v1), begin(v2), 0);

iota

Remplit un intervalle avec des valeurs séquentielles croissantes.

vector<int> iota_vec(5);
iota(begin(iota_vec), end(iota_vec), 10);

partial_sum

Calcule les sommes partielles.

vector<int> src = {1, 2, 3, 4, 5};
vector<int> dst(src.size());
partial_sum(begin(src), end(src), begin(dst));

adjacent_difference

Calcule les différences entre éléments adjacents.

vector<int> input = {1, 2, 3, 4, 5};
vector<int> output(input.size());
adjacent_difference(begin(input), end(input), begin(output));

Autres algorithmes

generate et generate_n

generate remplit un intervalle avec les résultats d'une fonction. generate_n remplit les n premiers éléments.

vector<int> gen_vec(5);
int counter = 0;
generate(begin(gen_vec), end(gen_vec), [&counter]() { return counter++; });

vector<int> gen_n_vec(5);
int n_counter = 10;
generate_n(begin(gen_n_vec), 3, [&n_counter]() { return n_counter++; });

includes

Vérifie si un intervalle trié contient tous les éléments d'un autre intervalle trié.

vector<int> super = {1, 2, 3, 4, 5};
vector<int> sub = {2, 4};
bool is_included = includes(begin(super), end(super), begin(sub), end(sub));

Opérations ensemblistes

set_union, set_intersection, set_difference, set_symmetric_difference effectuent les opérations correspondantes sur des intervalles triés.

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

set_union(begin(set1), end(set1), begin(set2), end(set2), back_inserter(result));
set_intersection(begin(set1), end(set1), begin(set2), end(set2), back_inserter(result));
set_difference(begin(set1), end(set1), begin(set2), end(set2), back_inserter(result));
set_symmetric_difference(begin(set1), end(set1), begin(set2), end(set2), back_inserter(result));

Points fréquents

Différence entre sort et stable_sort ? sort utilise un algorithme instable (introsort). stable_sort préserve l'ordre relatif des éléments égaux, souvent via un tri fusion.

Pourquoi combiner remove et erase ? remove déplace les éléments à conserver vers l'avant et retourne un itérateur vers la nouvelle fin logique, mais ne modifie pas la taille du conteneur. erase supprime physiquement les éléments indésirables de la fin.

Quels algorithmes nécessitent un conteneur trié ? Les algorithmes de recherche binaire (binary_search, lower_bound, upper_bound), les algorithmes ensemblistes, merge et includes requièrent des intervalles triés.