Bibliothèque d'algorithmes C++<algorithm>

Dans la bibliothèque standard C++,<algorithm>le fichier d'en-tête fournit un ensemble d'algorithmes pour manipuler des conteneurs (tels que des tableaux, des vecteurs, des listes, etc.). Ces algorithmes incluent le tri, la recherche, la copie, la comparaison, etc., et sont des outils importants pour écrire du code efficace et réutilisable.

<algorithm>Le fichier d'en-tête définit un ensemble de fonctions modèles qui peuvent être appliquées à des conteneurs de tout type, tant que le conteneur prend en charge les itérateurs. Ces algorithmes acceptent généralement deux itérateurs ou plus comme paramètres, indiquant les positions de début et de fin de l'opération.

Syntaxe

La plupart<algorithm>Les fonctions qu'il contient suivent toutes la syntaxe de base suivante :

algorithm_name(container.begin(), container.end(), ...);

icicontainerest un objet conteneur,begin()etend()Sont des fonctions membres du conteneur, renvoyant des itérateurs qui pointent vers le début et la fin du conteneur.

Exemple

1. Algorithmes de tri

Fonctions : sort

Définition : Trie les éléments du conteneur.

Syntaxe :

sort(container.begin(), container.end(), compare_function);

où compare_function est une fonction de comparaison facultative utilisée pour personnaliser la méthode de tri.

Résultat de sortie :

1 2 5 5 6 9 

std::partial_sort: Trie une plage partielle, avec les n premiers éléments dans l'ordre trié.

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

std::stable_sort: Tri stable, préservant l'ordre relatif des éléments égaux.

std::stable_sort(vec.begin(), vec.end());

2. Algorithmes de recherche

Fonctions : find

Définition : Trouve le premier élément du conteneur qui correspond à une valeur donnée.

Syntaxe :

auto it = find(container.begin(), container.end(), value);

S'il est trouvé, il pointera vers l'élément correspondant ; s'il n'est pas trouvé, il sera égal à container.end().

Résultat de sortie :

Found: 3

std::binary_search: Effectue une recherche binaire sur un intervalle trié.

std::sort(vec.begin(), vec.end());  // 先排序
bool found = std::binary_search(vec.begin(), vec.end(), 4);

std::find_if: Trouve le premier élément qui satisfait une condition spécifique.

auto it = std::find_if(vec.begin(), vec.end(), [](int x) { return x > 3; });

3. Algorithmes de copie

Fonctions : copy

Définition : Copie des éléments d'une plage vers un autre conteneur ou tableau.

Syntaxe :

copy(source_begin, source_end, destination_begin);

Exemple :

Résultat de sortie :

1 2 3 4 5 

4. Algorithmes de comparaison

Fonctions : equal

Définition : Compare si les éléments de deux conteneurs ou de deux plages sont égaux.

Syntaxe :

bool result = equal(first1, last1, first2);

ou 

bool result = equal(first1, last1, first2, compare_function);

Résultat de sortie :

Vectors are equal.

5. Algorithmes de modification

std::reverse: Inverse l'ordre des éléments dans l'intervalle.

std::reverse(vec.begin(), vec.end());

std::: Affecte une certaine valeur à tous les éléments dans la plage spécifiée.

std::fill(vec.begin(), vec.end(), 0);  // 所有元素设为 0

std::replace: Remplace une certaine valeur dans la plage par une autre valeur.

std::replace(vec.begin(), vec.end(), 1, 99);  // 将所有 1 替换为 99

std::copy: Copie les éléments de l'intervalle vers un autre intervalle.

std::vector<int> vec2(6);
std::copy(vec.begin(), vec.end(), vec2.begin());

6. Algorithmes de permutation

std::next_permutation: Génère la permutation suivante dans l'ordre lexicographique, et renvoie false s'il n'y a pas de permutation suivante.

std::vector<int> vec = {1, 2, 3};
do {
    for (int n : vec) std::cout << n << " ";
    std::cout << std::endl;
} while (std::next_permutation(vec.begin(), vec.end()));

std::prev_permutation: Génère la permutation lexicographique précédente.

std::prev_permutation(vec.begin(), vec.end());

7. Algorithmes de fusion

std::merge: Fusionne deux plages triées en une seule plage triée.

std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};
std::vector<int> result(6);
std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

std::inplace_merge: Fusionne deux sous-plages triées au sein d'une même plage.

std::inplace_merge(vec.begin(), middle, vec.end());

8. Algorithmes sur les ensembles

std::set_union: Calcule l'union de deux ensembles triés.

std::vector<int> result(10);
auto it = std::set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_intersection: Calcule l'intersection de deux ensembles triés.

auto it = std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

std::set_difference: Calcule la différence de deux ensembles.

auto it = std::set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
result.resize(it - result.begin());

9. Autres algorithmes utiles

std::accumulate(nécessite la bibliothèque <numeric>): Calcule la somme cumulée des éléments de la plage.

#include <numeric>
int sum = std::accumulate(vec.begin(), vec.end(), 0);

std::for_each: Effectue une opération sur chaque élément de la plage.

std::for_each(vec.begin(), vec.end(), [](int& x) { x += 1; });

std::min_elementetstd::max_element: Trouve les valeurs minimale et maximale dans la plage.

auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());

<algorithm>Est un outil très puissant de la bibliothèque standard C++. Il fournit un grand nombre d'algorithmes génériques, ce qui peut grandement simplifier la programmation.