La bibliothèque standard C++ (STL) offre un ensemble étendu d'algorithmes génériques pour manipuler des plages d'éléments. Ces algorithmes travaillent avec des itérateurs, ce qui les rend compatibles avec une multitude de conteneurs (comme std::vector, std::list, std::array) ainsi qu'avec les tableaux de style C. Cet article explore ces outils puissants, classés par leur fonction principale, et fournit des exemples d'utilisation en C++.
Algorithmes de Séquence Non Modificateurs
Ces algorithmes parcourent les éléments d'une plage donnée sans en modifier les valeurs ni la structure du conteneur sous-jacent.
Recherche d'éléments : std::find, std::find_if, std::find_end
std::find(début, fin, valeur): Localise la première occurrence d'unevaleurspécifique dans une plage. Il renvoie un itérateur vers l'élément trouvé, ou l'itérateur definsi la valeur n'est pas présente.std::find_if(début, fin, prédicat): Identifie le premier élément qui satisfait unprédicat(une fonction unaire qui retourne un booléen).std::find_end(début1, fin1, début2, fin2): Recherche la dernière occurrence d'une sous-séquence[début2, fin2)au sein de la séquence principale[début1, fin1).
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::find, std::find_if, std::find_end
#include <iterator> // Pour std::distance
int main() {
std::vector<int> nombres = {10, 20, 30, 40, 50, 20, 60};
// Trouver la valeur 30
auto iterateur_trente = std::find(nombres.begin(), nombres.end(), 30);
if (iterateur_trente != nombres.end()) {
std::cout << "La valeur 30 est trouvée à l'indice : " << std::distance(nombres.begin(), iterateur_trente) << std::endl; // Affiche : 2
}
// Trouver le premier élément supérieur à 45
auto iterateur_gt45 = std::find_if(nombres.begin(), nombres.end(), [](int n) {
return n > 45;
});
if (iterateur_gt45 != nombres.end()) {
std::cout << "Le premier élément > 45 est : " << *iterateur_gt45 << std::endl; // Affiche : 50
}
// Rechercher la dernière occurrence de la sous-séquence {20, 60}
std::vector<int> sous_sequence = {20, 60};
auto iterateur_dernier_match = std::find_end(nombres.begin(), nombres.end(), sous_sequence.begin(), sous_sequence.end());
if (iterateur_dernier_match != nombres.end()) {
std::cout << "La sous-séquence {20, 60} débute à l'indice : " << std::distance(nombres.begin(), iterateur_dernier_match) << std::endl; // Affiche : 5
}
return 0;
}
Comptage d'éléments : std::count, std::count_if
std::count(début, fin, valeur): Compte le nombre d'occurrences d'unevaleurspécifique dans une plage.std::count_if(début, fin, prédicat): Détermine combien d'éléments dans une plage satisfont unprédicatdonné.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::count, std::count_if
int main() {
std::vector<int> donnees = {1, 5, 2, 5, 3, 5, 4};
// Compter les occurrences de la valeur 5
int occurrences_cinq = std::count(donnees.begin(), donnees.end(), 5);
std::cout << "Nombre d'occurrences de 5 : " << occurrences_cinq << std::endl; // Affiche : 3
// Compter les nombres pairs
int nb_pairs = std::count_if(donnees.begin(), donnees.end(), [](int x) {
return x % 2 == 0;
});
std::cout << "Nombre de nombres pairs : " << nb_pairs << std::endl; // Affiche : 2 (pour 2 et 4)
return 0;
}
Application de fonction à chaque élément : std::for_each
std::for_each(début, fin, fonction) : Applique une fonction (un objet callable) à chaque élément de la plage spécifiée. La fonction peut modifier les éléments si elle prend une référence modifiable.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::for_each
#include <string>
void afficher_vec_foreach(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> nombres_modifiables = {1, 2, 3, 4, 5};
afficher_vec_foreach("Avant for_each", nombres_modifiables); // Affiche : {1, 2, 3, 4, 5}
// Multiplier chaque élément par 2
std::for_each(nombres_modifiables.begin(), nombres_modifiables.end(), [](int& x) {
x *= 2;
});
afficher_vec_foreach("Après for_each (x *= 2)", nombres_modifiables); // Affiche : {2, 4, 6, 8, 10}
return 0;
}
Comparaison de séquences : std::equal, std::mismatch
std::equal(début1, fin1, début2): Vérifie si deux plages sont identiques élément par élément. Retournetruesi toutes les paires d'éléments correspondantes sont égales.std::mismatch(début1, fin1, début2): Trouve la première paire d'éléments non correspondants entre deux plages. Retourne unestd::paird'itérateurs pointant vers les premiers éléments différents de chaque séquence.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::equal, std::mismatch
#include <utility> // Pour std::pair
int main() {
std::vector<int> serie_un = {10, 20, 30};
std::vector<int> serie_deux = {10, 20, 40};
std::vector<int> serie_trois = {10, 20, 30, 50};
// Comparaison de serie_un et serie_deux
bool sont_strictement_egales = std::equal(serie_un.begin(), serie_un.end(), serie_deux.begin());
std::cout << "Serie UN et Serie DEUX sont égales ? " << std::boolalpha << sont_strictement_egales << std::endl; // Affiche : false
// Trouver le premier désaccord entre serie_un et serie_trois
auto paires_differentes = std::mismatch(serie_un.begin(), serie_un.end(), serie_trois.begin());
if (paires_differentes.first == serie_un.end()) {
std::cout << "Serie UN et les premiers éléments de Serie TROIS sont identiques." << std::endl;
} else {
std::cout << "Première différence : " << *paires_differentes.first << " (dans Serie UN) vs " << *paires_differentes.second << " (dans Serie TROIS)" << std::endl;
}
return 0;
}
Vérification de prédicats de plage : std::all_of, std::any_of, std::none_of (C++11)
std::all_of(début, fin, prédicat): Retournetruesi tous les éléments de la plage satisfont leprédicat.std::any_of(début, fin, prédicat): Retournetruesi au moins un élément de la plage satisfait leprédicat.std::none_of(début, fin, prédicat): Retournetruesi aucun élément de la plage ne satisfait leprédicat.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::all_of, std::any_of, std::none_of
int main() {
std::vector<int> ensemble_chiffres = {2, 4, 6, 8};
bool tous_pairs = std::all_of(ensemble_chiffres.begin(), ensemble_chiffres.end(), [](int val) {
return val % 2 == 0;
});
std::cout << "Tous les chiffres sont pairs : " << std::boolalpha << tous_pairs << std::endl; // Affiche : true
bool un_impair = std::any_of(ensemble_chiffres.begin(), ensemble_chiffres.end(), [](int val) {
return val % 2 != 0;
});
std::cout << "Il existe un chiffre impair : " << std::boolalpha << un_impair << std::endl; // Affiche : false
bool aucun_negatif = std::none_of(ensemble_chiffres.begin(), ensemble_chiffres.end(), [](int val) {
return val < 0;
});
std::cout << "Aucun chiffre n'est négatif : " << std::boolalpha << aucun_negatif << std::endl; // Affiche : true
return 0;
}
Algorithmes de Séquence Modificateurs
Ces algorithmes ont pour effet de modifier les éléments des plages sur lesquelles ils opèrent.
Copie d'éléments : std::copy, std::copy_if
std::copy(début_src, fin_src, début_dest): Copie les éléments de la plage source vers la plage de destination, à partir dedébut_dest. Il est essentiel que la destination ait une capacité suffisante.std::copy_if(début_src, fin_src, début_dest, prédicat): Copie sélectivement les éléments qui satisfont leprédicatvers la destination.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::copy, std::copy_if
#include <iterator> // Pour std::back_inserter
void afficher_vecteur(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> source_valeurs = {10, 15, 20, 25, 30};
std::vector<int> destination_complete(source_valeurs.size()); // Nécessite une pré-allocation
// Copier tous les éléments
std::copy(source_valeurs.begin(), source_valeurs.end(), destination_complete.begin());
afficher_vecteur("Copie complète", destination_complete); // Affiche : {10, 15, 20, 25, 30}
// Copier uniquement les nombres pairs dans un nouveau vecteur
std::vector<int> destination_nombres_pairs;
std::copy_if(source_valeurs.begin(), source_valeurs.end(),
std::back_inserter(destination_nombres_pairs), // std::back_inserter gère l'allocation automatique
[](int val) { return val % 2 == 0; });
afficher_vecteur("Copie des nombres pairs", destination_nombres_pairs); // Affiche : {10, 20, 30}
return 0;
}
Remarque : L'itérateur std::back_inserter est particulièrement utile car il appelle automatiquement la méthode push_back du conteneur cible, évitant ainsi le besoin de pré-allouer manuellement de l'espace.
Transformation d'éléments : std::transform
std::transform(début_src, fin_src, début_dest, opération) : Applique une opération unaire à chaque élément de la plage source et stocke le résultat à partir de début_dest. Une surcharge permet d'effectuer des opérations binaires avec deux plages d'entrée.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::transform
#include <iterator> // Pour std::back_inserter
void afficher_vec_transform(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> nombres_origine = {1, 2, 3, 4};
std::vector<int> carres; // La destination sera remplie par back_inserter
// Calculer les carrés des nombres (opération unaire)
std::transform(nombres_origine.begin(), nombres_origine.end(),
std::back_inserter(carres),
[](int x) { return x * x; });
afficher_vec_transform("Carrés", carres); // Affiche : {1, 4, 9, 16}
std::vector<int> liste_a = {10, 20, 30};
std::vector<int> liste_b = {1, 2, 3};
std::vector<int> resultats_somme;
// Additionner les éléments correspondants de deux listes (opération binaire)
std::transform(liste_a.begin(), liste_a.end(),
liste_b.begin(), // Début de la deuxième plage d'entrée
std::back_inserter(resultats_somme),
[](int x, int y) { return x + y; });
afficher_vec_transform("Sommes", resultats_somme); // Affiche : {11, 22, 33}
return 0;
}
Remplacement d'éléments : std::replace, std::replace_if, std::replace_copy
std::replace(début, fin, ancienne_valeur, nouvelle_valeur): Remplace toutes les occurrences d'ancienne_valeurparnouvelle_valeurdans la plage.std::replace_if(début, fin, prédicat, nouvelle_valeur): Remplace les éléments qui satisfont leprédicatparnouvelle_valeur.std::replace_copy(début_src, fin_src, début_dest, ancienne_valeur, nouvelle_valeur): Copie les éléments de la source vers la destination, en remplaçant lesancienne_valeurparnouvelle_valeurpendant le processus. La plage source n'est pas modifiée.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::replace, std::replace_if, std::replace_copy
#include <iterator> // Pour std::back_inserter
void afficher_vec_replace(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> valeurs_base = {1, 5, 2, 5, 3, 5};
afficher_vec_replace("Original", valeurs_base); // Affiche : {1, 5, 2, 5, 3, 5}
// Remplacer toutes les occurrences de 5 par 99
std::replace(valeurs_base.begin(), valeurs_base.end(), 5, 99);
afficher_vec_replace("Après replace(5 -> 99)", valeurs_base); // Affiche : {1, 99, 2, 99, 3, 99}
// Remplacer les nombres pairs par 0
std::replace_if(valeurs_base.begin(), valeurs_base.end(), [](int x) {
return x % 2 == 0;
}, 0);
afficher_vec_replace("Après replace_if(pairs -> 0)", valeurs_base); // Affiche : {1, 99, 0, 99, 3, 99}
std::vector<int> resultat_copie_remplacee;
std::vector<int> source_pour_copy_replace = {10, 20, 10, 30, 10};
// Copier en remplaçant 10 par 100
std::replace_copy(source_pour_copy_replace.begin(), source_pour_copy_replace.end(),
std::back_inserter(resultat_copie_remplacee), 10, 100);
afficher_vec_replace("Source pour replace_copy", source_pour_copy_replace); // Affiche : {10, 20, 10, 30, 10} (non modifiée)
afficher_vec_replace("Résultat de replace_copy", resultat_copie_remplacee); // Affiche : {100, 20, 100, 30, 100}
return 0;
}
Suppression logique et physique : std::remove, std::remove_if et erase
std::remove(début, fin, valeur): Réarrange les éléments pour que ceux qui ne sont **pas égaux** àvaleursoient déplacés au début de la plage. Il retourne un itérateur vers la nouvelle "fin logique". **Cet algorithme ne modifie pas la taille réelle du conteneur.**std::remove_if(début, fin, prédicat): Agit de manière similaire, mais déplace les éléments qui **ne satisfont pas** leprédicatvers le début.- Pour une suppression physique (réduire la taille du conteneur et libérer la mémoire),
removeouremove_ifdoit être combiné avec la méthodeerasedu conteneur :conteneur.erase(std::remove(...), conteneur.end());. C'est l'idiome "erase-remove".
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::remove, std::remove_if
void afficher_vec_remove(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> nombres_pour_suppression = {10, 20, 30, 20, 40, 50, 20};
afficher_vec_remove("Avant remove", nombres_pour_suppression); // Affiche : {10, 20, 30, 20, 40, 50, 20}
// Supprimer logiquement toutes les occurrences de 20
auto nouvelle_fin_logique = std::remove(nombres_pour_suppression.begin(), nombres_pour_suppression.end(), 20);
// Le vecteur contient maintenant les éléments non supprimés suivis des éléments "supprimés" à la fin
afficher_vec_remove("Après remove (logique)", nombres_pour_suppression); // Exemple : {10, 30, 40, 50, 40, 50, 20}
// Supprimer physiquement les éléments après la nouvelle fin logique
nombres_pour_suppression.erase(nouvelle_fin_logique, nombres_pour_suppression.end());
afficher_vec_remove("Après erase (physique)", nombres_pour_suppression); // Affiche : {10, 30, 40, 50}
std::vector<int> nombres_pour_suppression_if = {1, 2, 3, 4, 5, 6};
// Supprimer physiquement tous les nombres pairs
nombres_pour_suppression_if.erase(std::remove_if(nombres_pour_suppression_if.begin(), nombres_pour_suppression_if.end(), [](int x) {
return x % 2 == 0;
}), nombres_pour_suppression_if.end());
afficher_vec_remove("Après remove_if (nombres pairs)", nombres_pour_suppression_if); // Affiche : {1, 3, 5}
return 0;
}
Suppression de doublons consécutifs : std::unique
std::unique(début, fin) : Réarrange les éléments pour que les doublons consécutifs soient déplacés à la fin de la plage et retourne un itérateur vers la nouvelle fin logique. Comme std::remove, il ne modifie pas la taille du conteneur et est généralement utilisé avec erase.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::unique
void afficher_vec_unique(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> chiffres_avec_doublons = {1, 1, 2, 2, 2, 3, 4, 4, 5};
afficher_vec_unique("Initial", chiffres_avec_doublons); // Affiche : {1, 1, 2, 2, 2, 3, 4, 4, 5}
auto nouvelle_fin_unique = std::unique(chiffres_avec_doublons.begin(), chiffres_avec_doublons.end());
// Le vecteur contient maintenant les éléments uniques suivis des doublons
afficher_vec_unique("Après unique (logique)", chiffres_avec_doublons); // Exemple : {1, 2, 3, 4, 5, 2, 4, 4, 5}
chiffres_avec_doublons.erase(nouvelle_fin_unique, chiffres_avec_doublons.end());
afficher_vec_unique("Après erase (physique)", chiffres_avec_doublons); // Affiche : {1, 2, 3, 4, 5}
return 0;
}
Inversion de séquence : std::reverse
std::reverse(début, fin) : Inverse l'ordre des éléments dans la plage spécifiée.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::reverse
int main() {
std::vector<char> caracteres = {'A', 'B', 'C', 'D', 'E'};
std::cout << "Avant inversion : ";
for (char c : caracteres) { std::cout << c << " "; }
std::cout << std::endl; // Affiche : A B C D E
std::reverse(caracteres.begin(), caracteres.end());
std::cout << "Après inversion : ";
for (char c : caracteres) { std::cout << c << " "; }
std::cout << std::endl; // Affiche : E D C B A
return 0;
}
Rotation de séquence : std::rotate
std::rotate(début, milieu, fin) : Effectue une rotation circulaire des éléments dans la plage. L'élément pointé par milieu devient le nouveau premier élément de la plage.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::rotate
int main() {
std::vector<int> sequence_originale = {10, 20, 30, 40, 50, 60};
std::cout << "Séquence originale : ";
for (int n : sequence_originale) { std::cout << n << " "; }
std::cout << std::endl; // Affiche : 10 20 30 40 50 60
// Rotation de la séquence pour que 40 (situé à l'indice 3) devienne le premier élément
std::rotate(sequence_originale.begin(), sequence_originale.begin() + 3, sequence_originale.end());
std::cout << "Après rotation (point de départ à l'indice 3) : ";
for (int n : sequence_originale) { std::cout << n << " "; }
std::cout << std::endl; // Affiche : 40 50 60 10 20 30
return 0;
}
Mélange aléatoire : std::shuffle (C++11)
std::shuffle(début, fin, générateur_aléatoire) : Réorganise aléatoirement les éléments de la plage en utilisant un générateur de nombres aléatoires fourni.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::shuffle
#include <random> // Pour std::random_device, std::mt19937
#include <chrono> // Pour std::chrono::system_clock::now().time_since_epoch().count()
int main() {
std::vector<int> cartes_jeu = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::cout << "Ordre initial des cartes : ";
for (int c : cartes_jeu) { std::cout << c << " "; }
std::cout << std::endl;
// Utilisation d'un générateur de nombres aléatoires basé sur le temps système
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 generateur_aleatoire(seed); // Moteur Mersenne Twister
std::shuffle(cartes_jeu.begin(), cartes_jeu.end(), generateur_aleatoire);
std::cout << "Après mélange aléatoire : ";
for (int c : cartes_jeu) { std::cout << c << " "; }
std::cout << std::endl; // Affiche un ordre aléatoire, ex: 7 4 9 1 3 6 8 2 5 10
return 0;
}
Algorithmes de Tri et Associés
Ces algorithmes permettent d'organiser les éléments d'une plage selon un certain ordre.
Tri de plages : std::sort, std::stable_sort, std::partial_sort
std::sort(début, fin, [comparateur]): Trie les éléments dans la plage[début, fin)en utilisant l'opérateur<par défaut ou uncomparateurpersonnalisé. Généralement non stable (l'ordre relatif des éléments égaux peut changer).std::stable_sort(début, fin, [comparateur]): Trie les éléments tout en garantissant que l'ordre relatif des éléments égaux est maintenu.std::partial_sort(début, milieu, fin, [comparateur]): Trie une partie de la plage, plaçant les plus petits éléments (selon le critère de tri) dans la sous-plage[début, milieu). Cette sous-plage est triée, mais les éléments aprèsmilieune le sont pas.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::sort, std::stable_sort, std::partial_sort
#include <functional> // Pour std::greater
#include <utility> // Pour std::pair
void afficher_vec_sort(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> nombres_a_trier = {50, 10, 40, 20, 30};
std::cout << "Initial : ";
for (int n : nombres_a_trier) { std::cout << n << " "; }
std::cout << std::endl;
// Tri par défaut (ascendant)
std::sort(nombres_a_trier.begin(), nombres_a_trier.end());
afficher_vec_sort("Après sort (ascendant)", nombres_a_trier); // Affiche : {10, 20, 30, 40, 50}
// Tri descendant avec un comparateur
std::vector<int> nombres_desc = {5, 1, 4, 2, 3};
std::sort(nombres_desc.begin(), nombres_desc.end(), std::greater<int>());
afficher_vec_sort("Après sort (descendant)", nombres_desc); // Affiche : {5, 4, 3, 2, 1}
// std::stable_sort pour maintenir l'ordre des éléments égaux
std::vector<std::pair<int, int>> paires = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(paires.begin(), paires.end(), [](const auto& a, const auto& b) {
return a.first < b.first; // Tri par le premier élément
});
std::cout << "Après stable_sort (par premier élément) : ";
for (const auto& p : paires) { std::cout << "{" << p.first << "," << p.second << "} "; }
std::cout << std::endl; // Affiche : {1,2} {1,1} {2,1} {2,2} (l'ordre de {1,2} et {1,1} est conservé)
// std::partial_sort: trier seulement les 3 plus petits éléments au début
std::vector<int> nombres_partial_sort = {9, 2, 7, 1, 8, 3, 6, 4, 5};
std::partial_sort(nombres_partial_sort.begin(), nombres_partial_sort.begin() + 3, nombres_partial_sort.end());
afficher_vec_sort("Après partial_sort (3 premiers)", nombres_partial_sort); // Exemple : {1, 2, 3, 9, 8, 7, 6, 4, 5}
return 0;
}
Éléments n-ièmes : std::nth_element
std::nth_element(début, n_ieme_element, fin, [comparateur]) : Réorganise la plage de sorte que l'élément à la position n_ieme_element soit l'élément qui se trouverait à cette position si la plage était entièrement triée. Tous les éléments avant n_ieme_element sont inférieurs ou égaux à celui-ci, et tous les éléments après sont supérieurs ou égaux. Les sous-plages de gauche et de droite ne sont pas triées.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::nth_element
int main() {
std::vector<int> valeurs_pour_n_element = {5, 1, 8, 2, 9, 4, 7, 3, 6};
std::cout << "Initial : ";
for (int n : valeurs_pour_n_element) { std::cout << n << " "; }
std::cout << std::endl; // Affiche : 5 1 8 2 9 4 7 3 6
// Trouver le 4ème plus petit élément (à l'indice 3)
std::nth_element(valeurs_pour_n_element.begin(), valeurs_pour_n_element.begin() + 3, valeurs_pour_n_element.end());
std::cout << "Après nth_element (indice 3) : ";
for (int n : valeurs_pour_n_element) { std::cout << n << " "; }
std::cout << std::endl; // Exemple : 3 1 2 4 9 5 7 8 6 (valeurs_pour_n_element[3] est 4, et tous les éléments à gauche sont <=4, à droite sont >=4)
std::cout << "Le 4ème plus petit élément est : " << valeurs_pour_n_element[3] << std::endl; // Affiche : 4
return 0;
}
Recherche binaire sur plages triées : std::binary_search, std::lower_bound, std::upper_bound
Ces algorithmes nécessitent impérativement que la plage soit préalablement **triée**.
std::binary_search(début, fin, valeur, [comparateur]): Vérifei si unevaleurest présente dans la plage. Retourne un booléen.std::lower_bound(début, fin, valeur, [comparateur]): Retourne un itérateur vers le premier élément qui n'est **pas inférieur** àvaleur.std::upper_bound(début, fin, valeur, [comparateur]): Retourne un itérateur vers le premier élément qui est **strictement supérieur** àvaleur.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::binary_search, std::lower_bound, std::upper_bound
#include <iterator> // Pour std::distance
int main() {
std::vector<int> nombres_ordonnes = {10, 20, 20, 30, 40, 40, 40, 50}; // Doit être trié
// Vérifier si 30 est présent
bool trente_trouve = std::binary_search(nombres_ordonnes.begin(), nombres_ordonnes.end(), 30);
std::cout << "30 est présent : " << std::boolalpha << trente_trouve << std::endl; // Affiche : true
// Trouver le premier élément >= 20
auto it_borne_inf = std::lower_bound(nombres_ordonnes.begin(), nombres_ordonnes.end(), 20);
std::cout << "lower_bound(20) est à l'indice : " << std::distance(nombres_ordonnes.begin(), it_borne_inf)
<< ", valeur : " << *it_borne_inf << std::endl; // Affiche : 1, valeur : 20
// Trouver le premier élément > 20
auto it_borne_sup = std::upper_bound(nombres_ordonnes.begin(), nombres_ordonnes.end(), 20);
std::cout << "upper_bound(20) est à l'indice : " << std::distance(nombres_ordonnes.begin(), it_borne_sup)
<< ", valeur : " << *it_borne_sup << std::endl; // Affiche : 3, valeur : 30
// Utilisation de lower_bound et upper_bound pour trouver toutes les occurrences de 40
auto debut_plage_40 = std::lower_bound(nombres_ordonnes.begin(), nombres_ordonnes.end(), 40);
auto fin_plage_40 = std::upper_bound(nombres_ordonnes.begin(), nombres_ordonnes.end(), 40);
std::cout << "Occurrences de 40 trouvées à partir de l'indice " << std::distance(nombres_ordonnes.begin(), debut_plage_40)
<< " sur " << std::distance(debut_plage_40, fin_plage_40) << " éléments." << std::endl; // Affiche : 4 sur 3 éléments.
return 0;
}
Fusion de plages : std::merge
std::merge(début1, fin1, début2, fin2, début_dest, [comparateur]) : Fusionne deux plages triées [début1, fin1) et [début2, fin2) en une seule plage triée, stockée à partir de début_dest. Les plages sources doivent être triées pour que le résultat soit correct.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::merge
#include <iterator> // Pour std::back_inserter
void afficher_vec_merge(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> liste_pairs = {2, 4, 6, 8};
std::vector<int> liste_impairs = {1, 3, 5, 7, 9};
std::vector<int> liste_fusionnee; // Destination
// Les deux listes doivent être triées avant la fusion
std::merge(liste_pairs.begin(), liste_pairs.end(),
liste_impairs.begin(), liste_impairs.end(),
std::back_inserter(liste_fusionnee));
afficher_vec_merge("Liste fusionnée", liste_fusionnee); // Affiche : {1, 2, 3, 4, 5, 6, 7, 8, 9}
return 0;
}
Algorithmes de Tas (Heap)
La STL C++ fournit des algorithmes pour manipuler une plage d'éléments comme un tas (une structure de données arborescente partiellement triée, par défaut un tas max).
std::make_heap(début, fin, [comparateur]): Transforme une plage en un tas max.std::push_heap(début, fin, [comparateur]): Ajoute un élément au tas. L'élément doit être inséré à la fin de la plage (\*(fin-1)) avant d'appelerpush_heap.std::pop_heap(début, fin, [comparateur]): Déplace l'élément le plus grand (racine du tas) à la positionfin - 1et réorganise le reste pour maintenir la propriété de tas. L'élément doit ensuite être retiré du conteneur (ex: avecpop_back).std::sort_heap(début, fin, [comparateur]): Trie un tas, le transformant en une séquence triée. Aprèssort_heap, la plage n'est plus un tas.
#include <iostream>
#include <vector>
#include <algorithm> // Pour les algorithmes de tas
void afficher_vec_heap(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> donnees_pour_tas = {30, 10, 50, 20, 40};
afficher_vec_heap("Initial", donnees_pour_tas); // Affiche : {30, 10, 50, 20, 40}
// 1. Transformer le vecteur en un tas max
std::make_heap(donnees_pour_tas.begin(), donnees_pour_tas.end());
afficher_vec_heap("Après make_heap", donnees_pour_tas); // Exemple : {50, 40, 30, 20, 10}
// 2. Ajouter un nouvel élément au tas
donnees_pour_tas.push_back(60); // Ajout physique à la fin
std::push_heap(donnees_pour_tas.begin(), donnees_pour_tas.end()); // Restaure la propriété de tas
afficher_vec_heap("Après push_back(60) et push_heap", donnees_pour_tas); // Exemple : {60, 40, 50, 20, 10, 30}
// 3. Retirer l'élément le plus grand (racine)
std::pop_heap(donnees_pour_tas.begin(), donnees_pour_tas.end()); // Déplace le max à la fin
int valeur_max = donnees_pour_tas.back(); // Récupère le max
donnees_pour_tas.pop_back(); // Retire physiquement le max
std::cout << "Valeur max retirée : " << valeur_max << std::endl; // Affiche : 60
afficher_vec_heap("Après pop_heap et pop_back", donnees_pour_tas); // Exemple : {50, 40, 30, 20, 10}
// 4. Trier le tas
std::sort_heap(donnees_pour_tas.begin(), donnees_pour_tas.end());
afficher_vec_heap("Après sort_heap", donnees_pour_tas); // Affiche : {10, 20, 30, 40, 50}
return 0;
}
Algorithmes de Minimum/Maximum
Ces algorithmes facilitent la recherche des éléments les plus petits ou les plus grands dans une collection.
Valeur min/max entre deux ou plusieurs éléments : std::min, std::max
std::min(a, b, [comparateur]): Retourne la plus petite de deux valeurs.std::max(a, b, [comparateur]): Retourne la plus grande de deux valeurs.- Ces fonctions peuvent également accepter une
std::initializer_listpour comparer plusieurs éléments (C++11).
#include <iostream>
#include <algorithm> // Pour std::min, std::max
#include <vector> // Pour std::initializer_list
int main() {
int val1 = 15, val2 = 25;
std::cout << "Minimum de " << val1 << " et " << val2 << " : " << std::min(val1, val2) << std::endl; // Affiche : 15
std::cout << "Maximum de " << val1 << " et " << val2 << " : " << std::max(val1, val2) << std::endl; // Affiche : 25
// Avec une liste d'initialisation (C++11)
std::cout << "Minimum d'une liste : " << std::min({100, 50, 200, 75}) << std::endl; // Affiche : 50
std::cout << "Maximum d'une liste : " << std::max({100, 50, 200, 75}) << std::endl; // Affiche : 200
return 0;
}
Itérateur vers min/max élément : std::min_element, std::max_element
std::min_element(début, fin, [comparateur]): Retourne un itérateur vers le plus petit élément de la plage.std::max_element(début, fin, [comparateur]): Retourne un itérateur vers le plus grand élément de la plage.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::min_element, std::max_element
int main() {
std::vector<double> temperatures = {22.5, 18.0, 25.3, 19.1, 20.7};
auto it_temp_min = std::min_element(temperatures.begin(), temperatures.end());
std::cout << "Température minimale : " << *it_temp_min << std::endl; // Affiche : 18.0
auto it_temp_max = std::max_element(temperatures.begin(), temperatures.end());
std::cout << "Température maximale : " << *it_temp_max << std::endl; // Affiche : 25.3
return 0;
}
Itérateur vers min et max élément : std::minmax_element (C++11)
std::minmax_element(début, fin, [comparateur]) : Retourne une std::pair d'itérateurs, le premier pointant vers le plus petit élément et le second vers le plus grand élément de la plage.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::minmax_element
#include <utility> // Pour std::pair
int main() {
std::vector<int> scores = {85, 92, 78, 95, 88};
auto paires_min_max_it = std::minmax_element(scores.begin(), scores.end());
std::cout << "Score le plus bas : " << *paires_min_max_it.first << std::endl; // Affiche : 78
std::cout << "Score le plus élevé : " << *paires_min_max_it.second << std::endl; // Affiche : 95
return 0;
}
Algorithmes Numériques (<numeric>)
Les algorithmes suivants, situés dans l'en-tête <numeric>, sont principalement conçus pour des opérations mathématiques sur des plages d'éléments.
Accumulation / Somme : std::accumulate
std::accumulate(début, fin, valeur_initiale, [opération]) : Calcule la somme (ou applique une autre opération binaire cumulative) de tous les éléments de la plage, en commençant par une valeur_initiale.
#include <iostream>
#include <vector>
#include <numeric> // Pour std::accumulate
#include <functional> // Pour std::multiplies
int main() {
std::vector<int> nombres_pour_somme = {1, 2, 3, 4, 5};
// Calculer la somme totale
int somme_finale = std::accumulate(nombres_pour_somme.begin(), nombres_pour_somme.end(), 0);
std::cout << "Somme totale : " << somme_finale << std::endl; // Affiche : 15
// Calculer le produit total (avec une opération personnalisée)
int produit_final = std::accumulate(nombres_pour_somme.begin(), nombres_pour_somme.end(), 1, std::multiplies<int>());
std::cout << "Produit total : " << produit_final << std::endl; // Affiche : 120 (1*2*3*4*5)
// Concaténer des chaînes de caractères
std::vector<std::string> mots_a_concatener = {"Ceci", "est", "un", "test"};
std::string phrase_resultat = std::accumulate(mots_a_concatener.begin(), mots_a_concatener.end(), std::string(""),
[](const std::string& a, const std::string& b) {
return a + (a.empty() ? "" : " ") + b;
});
std::cout << "Phrase concaténée : '" << phrase_resultat << "'" << std::endl; // Affiche : 'Ceci est un test'
return 0;
}
Produit scalaire : std::inner_product
std::inner_product(début1, fin1, début2, valeur_initiale, [op_somme, op_produit]) : Calcule le produit scalaire (somme des produits des éléments correspondants) de deux plages.
#include <iostream>
#include <vector>
#include <numeric> // Pour std::inner_product
int main() {
std::vector<int> vecteur_x = {1, 2, 3};
std::vector<int> vecteur_y = {4, 5, 6};
// Calcul du produit scalaire : (1*4) + (2*5) + (3*6) = 4 + 10 + 18 = 32
int resultat_produit_scalaire = std::inner_product(vecteur_x.begin(), vecteur_x.end(),
vecteur_y.begin(), 0); // 0 est la valeur initiale pour la somme
std::cout << "Produit scalaire : " << resultat_produit_scalaire << std::endl; // Affiche : 32
return 0;
}
Remplissage séquentiel : std::iota (C++11)
std::iota(début, fin, valeur) : Remplit une plage avec des valeurs séquentiellement croissantes, en commençant par valeur.
#include <iostream>
#include <vector>
#include <numeric> // Pour std::iota
void afficher_vec_iota(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> sequence_remplie(7); // Créer un vecteur de 7 éléments
// Remplir avec des nombres à partir de 100
std::iota(sequence_remplie.begin(), sequence_remplie.end(), 100);
afficher_vec_iota("Séquence iota", sequence_remplie); // Affiche : {100, 101, 102, 103, 104, 105, 106}
return 0;
}
Sommes partielles : std::partial_sum
std::partial_sum(début_src, fin_src, début_dest, [opération]) : Calcule les sommes partielles (ou applique une autre opération binaire cumulative) des éléments de la plage source et stocke les résultats dans la plage de destination.
#include <iostream>
#include <vector>
#include <numeric> // Pour std::partial_sum
#include <functional> // Pour std::plus (par défaut)
void afficher_vec_psum(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> donnees_source_psum = {1, 2, 3, 4, 5};
std::vector<int> sommes_cumulees(donnees_source_psum.size());
// Calculer les sommes cumulées : 1, 1+2, 1+2+3, ...
std::partial_sum(donnees_source_psum.begin(), donnees_source_psum.end(), sommes_cumulees.begin());
afficher_vec_psum("Sommes partielles", sommes_cumulees); // Affiche : {1, 3, 6, 10, 15}
// Avec une opération personnalisée (par exemple, produits cumulés)
std::vector<int> produits_cumules(donnees_source_psum.size());
std::partial_sum(donnees_source_psum.begin(), donnees_source_psum.end(), produits_cumules.begin(), std::multiplies<int>());
afficher_vec_psum("Produits partiels", produits_cumules); // Affiche : {1, 2, 6, 24, 120}
return 0;
}
Différences adjacentes : std::adjacent_difference
std::adjacent_difference(début_src, fin_src, début_dest, [opération]) : Calcule la différence (ou applique une autre opération binaire) entre les éléments adjacents de la plage source et stocke les résultats dans la plage de destination. Le premier élément est copié tel quel.
#include <iostream>
#include <vector>
#include <numeric> // Pour std::adjacent_difference
#include <functional> // Pour std::minus (par défaut)
void afficher_vec_adjdiff(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> serie_valeurs_adj = {10, 12, 15, 11, 13};
std::vector<int> differences_resultat(serie_valeurs_adj.size());
// Calculer les différences : 10, 12-10, 15-12, 11-15, 13-11
std::adjacent_difference(serie_valeurs_adj.begin(), serie_valeurs_adj.end(), differences_resultat.begin());
afficher_vec_adjdiff("Différences adjacentes", differences_resultat); // Affiche : {10, 2, 3, -4, 2}
return 0;
}
Algorithmes Divers
Génération de valeurs : std::generate, std::generate_n
std::generate(début, fin, générateur): Remplit toute la plage avec des valeurs produites par ungénérateur(une fonctoin callable sans arguments).std::generate_n(début, n, générateur): Remplit lesnpremiers éléments à partir dedébutavec les valeurs dugénérateur.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::generate, std::generate_n
#include <numeric> // Utile pour visualiser l'état des éléments non générés
void afficher_vec_gen(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> nombres_gen_full(5);
int compteur_gen = 0;
// Générer des nombres séquentiels à partir de 0
std::generate(nombres_gen_full.begin(), nombres_gen_full.end(), [&compteur_gen]() {
return compteur_gen++;
});
afficher_vec_gen("Après generate", nombres_gen_full); // Affiche : {0, 1, 2, 3, 4}
std::vector<int> nombres_gen_partiel(5, 99); // Initialisé avec 99
int debut_serie = 10;
// Générer les 3 premiers éléments à partir de 10
std::generate_n(nombres_gen_partiel.begin(), 3, [&debut_serie]() {
return debut_serie++;
});
afficher_vec_gen("Après generate_n (3 éléments)", nombres_gen_partiel); // Affiche : {10, 11, 12, 99, 99}
return 0;
}
Vérification d'inclusion : std::includes
std::includes(début1, fin1, début2, fin2, [comparateur]) : Vérifie si tous les éléments de la seconde plage [début2, fin2) sont présents dans la première plage [début1, fin1). Les deux plages doivent être **triées** pour un fonctionnement correct.
#include <iostream>
#include <vector>
#include <algorithm> // Pour std::includes
int main() {
std::vector<int> ensemble_principal = {10, 20, 30, 40, 50}; // Trié
std::vector<int> sous_ensemble_valide = {20, 40}; // Trié
std::vector<int> sous_ensemble_invalide = {20, 60}; // Trié
bool contient_valide = std::includes(ensemble_principal.begin(), ensemble_principal.end(),
sous_ensemble_valide.begin(), sous_ensemble_valide.end());
std::cout << "L'ensemble principal contient {20, 40} : " << std::boolalpha << contient_valide << std::endl; // Affiche : true
bool contient_invalide = std::includes(ensemble_principal.begin(), ensemble_principal.end(),
sous_ensemble_invalide.begin(), sous_ensemble_invalide.end());
std::cout << "L'ensemble principal contient {20, 60} : " << std::boolalpha << contient_invalide << std::endl; // Affiche : false
return 0;
}
Opérations ensemblistes : std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference
Ces algorithmes effectuent des opérations ensemblistes sur deux plages triées et stockent le résultat dans une plage de destination. Les plages d'entrée doivent être triées.
std::set_union: Calcule l'union des deux ensembles.std::set_intersection: Calcule l'intersection des deux ensembles.std::set_difference: Calcule la différence des deux ensembles (éléments présents dans le premier mais pas dans le second).std::set_symmetric_difference: Calcule la différence symétrique (éléments présents dans l'un ou l'autre, mais pas dans les deux).
#include <iostream>
#include <vector>
#include <algorithm> // Pour les opérations ensemblistes
#include <iterator> // Pour std::back_inserter
void afficher_vec_set_op(const std::string& prefixe, const std::vector<int>& v) {
std::cout << prefixe << ": {";
for (size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << (i == v.size() - 1 ? "" : ", ");
}
std::cout << "}" << std::endl;
}
int main() {
std::vector<int> ensemble_a = {1, 2, 3, 4, 5}; // Trié
std::vector<int> ensemble_b = {3, 4, 5, 6, 7}; // Trié
std::vector<int> resultat_operation_set;
// Union
resultat_operation_set.clear();
std::set_union(ensemble_a.begin(), ensemble_a.end(),
ensemble_b.begin(), ensemble_b.end(),
std::back_inserter(resultat_operation_set));
afficher_vec_set_op("Union (A U B)", resultat_operation_set); // Affiche : {1, 2, 3, 4, 5, 6, 7}
// Intersection
resultat_operation_set.clear();
std::set_intersection(ensemble_a.begin(), ensemble_a.end(),
ensemble_b.begin(), ensemble_b.end(),
std::back_inserter(resultat_operation_set));
afficher_vec_set_op("Intersection (A ∩ B)", resultat_operation_set); // Affiche : {3, 4, 5}
// Différence (A - B)
resultat_operation_set.clear();
std::set_difference(ensemble_a.begin(), ensemble_a.end(),
ensemble_b.begin(), ensemble_b.end(),
std::back_inserter(resultat_operation_set));
afficher_vec_set_op("Différence (A \\ B)", resultat_operation_set); // Affiche : {1, 2}
// Différence symétrique ((A U B) - (A ∩ B))
resultat_operation_set.clear();
std::set_symmetric_difference(ensemble_a.begin(), ensemble_a.end(),
ensemble_b.begin(), ensemble_b.end(),
std::back_inserter(resultat_operation_set));
afficher_vec_set_op("Différence symétrique (A ⊖ B)", resultat_operation_set); // Affiche : {1, 2, 6, 7}
return 0;
}
Questions Fréquemment Posées
-
Quelle est la différence fondamentale entre
std::sortetstd::stable_sort?std::sort: Généralement implémenté via Introsort (une combinaison de quicksort, heapsort et insertionsort), il offre une complexité temporelle moyenne de O(N log N) mais n'est **pas stable**. Cela signifie que l'ordre relatif des éléments ayant des valeurs égales n'est pas garanti après le tri.std::stable_sort: Typiquement implémenté avec un tri fusion, il garantit la complexité temporelle de O(N log N) et est **stable**, ce qui veut dire que l'ordre relatif des éléments égaux est préservé. Il peut cependant occasionner une surcharge spatiale plus importante questd::sort.
-
**Pourquoi les algorithmes
std::removeetstd::remove_ifnécessitent-ils d'être couplés à la méthodeerased'un conteneur ?**Les algorithmesstd::removeetstd::remove_ifne modifient pas la taille physique du conteneur. Ils réorganisent simplement les éléments en déplaçant ceux à conserver vers le début de la plage et retournent un itérateur vers la nouvelle "fin logique" de la séquence valide. Les éléments après cet itérateur sont considérés comme "supprimés" logiquement, mais ils occupent toujours de la mémoire dans le conteneur. Pour réduire réellement la taille du conteneur et libérer la mémoire, il est nécessaire d'appeler ensuite la méthodeerasedu conteneur avec la plage[nouvelle_fin_logique, conteneur.end()). Cette séquence d'opérations est un idiome bien connu appelé le "erase-remove idiom". -
**Quels algorithmes requièrent que les plages soient triées au préalable pour fonctionner correctement ?**De nombreux algorithmes tirent parti des propriétés des plages triées pour des performances optimisées (souvent en O(log N) au lieu de O(N) ou O(N log N)) ou pour des garanties de correction. Parmi ceux-ci, on trouve :
- Les algorithmes de recherche binaire :
std::binary_search,std::lower_bound,std::upper_bound. - Les algorithmes de fusion :
std::merge. - Les algorithmes ensemblistes :
std::set_union,std::set_intersection,std::set_difference,std::set_symmetric_difference,std::includes.
Il est crucial de trier la plage avant d'utiliser ces algorithmes, faute de quoi les résultats produits seront incorrects ou imprévisibles.
- Les algorithmes de recherche binaire :