Des boucles que vous n'avez pas à écrire
À la page précédente, vous avez vu que chaque conteneur fournit des itérateurs - des curseurs légers avec begin() et end(). Cette abstraction est la raison d'être des algorithmes standard. Au lieu d'écrire une boucle for brute chaque fois que vous voulez chercher, compter ou transformer des données, vous appelez une fonction nommée de <algorithm> et vous lui passez une plage.
Une plage, ce ne sont que deux itérateurs : où commencer et juste après où s'arrêter. Comme chaque algorithme parle ce même langage d'itérateurs, le même find fonctionne sur un vector, une string ou un tableau brut.
Le schéma à intégrer : un algorithme de recherche renvoie l'itérateur end() pour signifier « rien trouvé ». Comparez toujours avec end() avant de déréférencer le résultat - déréférencer end() est un comportement indéfini.
Compter et tester avec des prédicats
De nombreux algorithmes prennent un prédicat - une fonction (souvent une lambda) qui renvoie un bool pour chaque élément. count_if compte les correspondances ; all_of, any_of et none_of répondent à des questions oui/non sur toute la plage.
std::count (sans _if) est le cousin plus simple qui compte une valeur exacte au lieu d'une condition. Tournez-vous vers les versions à prédicat dès que votre test devient « tout ce qui satisfait une règle » plutôt que « cette valeur précise ».
Transformer et réduire une plage
Deux chevaux de bataille couvrent l'essentiel du traitement de données : std::transform applique une fonction à chaque élément, et std::accumulate (de <numeric>, pas de <algorithm>) réduit une plage à une seule valeur.
transform écrit ses résultats via un itérateur de sortie. Une erreur courante et dangereuse consiste à diriger la sortie vers un vector vide - l'algorithme suppose que la place existe déjà et écrit au-delà de la fin. Dimensionnez d'abord la destination, ou utilisez un back_inserter pour que chaque résultat soit ajouté par push_back.
accumulate part d'une valeur initiale et combine les éléments de gauche à droite. Le type de la valeur initiale compte : passez 0 (un int) et la somme est calculée en int, ce qui peut déborder ou tronquer.
Si vous aviez écrit accumulate(prices.begin(), prices.end(), 0) avec une graine int, chaque addition se ferait en int et les centimes disparaîtraient. Le type de la graine détermine silencieusement le type du résultat.
L'idiome erase-remove
Voici le piège qui surprend tout le monde. std::remove ne supprime rien du conteneur. Les algorithmes n'ont que des itérateurs, ils ne peuvent donc pas changer la taille d'un conteneur - ils ignorent même qu'un conteneur existe. Ce que remove fait réellement, c'est déplacer tous les éléments conservés vers le début, laissant la queue dans un état non spécifié, et renvoyer un itérateur sur la nouvelle fin logique.
// remove seul laisse la taille inchangée - voilà le bug :
remove(v.begin(), v.end(), 0); // renvoie un itérateur que vous avez ignoré
// v conserve sa taille d'origine ; la queue est du déchet
Pour réellement supprimer les éléments, vous associez remove au erase du conteneur, d'où le nom d'idiome erase-remove :
Utilisez remove_if pour un prédicat plutôt qu'une valeur exacte. En C++20, vous pouvez vous passer entièrement de cette danse avec les fonctions libres std::erase / std::erase_if, qui font les deux étapes pour vous : erase(v, 0);.
Les itérateurs survivent à leur validité à vos risques et périls
Comme les algorithmes renvoient des itérateurs, ceux-ci sont soumis aux mêmes règles d'invalidation que vous avez rencontrées à la page précédente. Stocker un itérateur puis modifier le conteneur - un push_back qui déclenche une réallocation, ou un erase - peut laisser l'itérateur stocké pendouillant, et l'utiliser est un comportement indéfini.
auto it = find(v.begin(), v.end(), 16);
v.push_back(99); // peut réallouer le stockage de v
cout << *it; // BUG : `it` peut désormais pointer sur de la mémoire libérée
La bonne habitude : utilisez l'itérateur renvoyé par un algorithme immédiatement, avant toute opération susceptible de redimensionner ou réallouer le conteneur. Si vous devez modifier le conteneur en fonction d'un résultat, capturez plutôt un indice (it - v.begin()), car les indices survivent à la réallocation.
Suite : le tri
Vous avez maintenant vu la recherche, le comptage, la transformation et la réduction - mais un algorithme est assez important pour mériter sa propre page. std::sort réordonne une plage sur place, et une fois les données triées, toute une famille d'algorithmes plus rapides et réservés aux données triées (binary_search, lower_bound, equal_range) s'ouvre à vous. Ensuite, nous creuserons le tri : comment fournir un comparateur personnalisé, la différence entre sort et stable_sort, et les règles que votre fonction de comparaison doit respecter pour éviter le comportement indéfini.
Questions fréquentes
Qu'est-ce que l'en-tête <algorithm> en C++ ?
<algorithm> est l'en-tête de la bibliothèque standard contenant des fonctions génériques comme std::find, std::sort, std::count_if et std::transform. Elles opèrent sur des plages décrites par une paire d'itérateurs (généralement begin() et end()), si bien que le même algorithme fonctionne sur un vector, un array, une string ou tout conteneur qui expose des itérateurs.
Comment vérifier qu'une valeur existe dans un vector en C++ ?
Utilisez std::find : auto it = find(v.begin(), v.end(), target);. Si it == v.end(), la valeur est absente ; sinon it pointe sur la première correspondance. Pour tester une condition plutôt qu'une valeur exacte, utilisez std::any_of avec un prédicat.
Pourquoi std::remove ne supprime-t-il pas réellement les éléments de mon conteneur ?
Les algorithmes ne voient que des itérateurs, pas le conteneur, donc std::remove ne peut pas le rétrécir - il décale les éléments conservés vers le début et renvoie un itérateur sur la nouvelle fin logique. Vous devez le faire suivre de v.erase(...) (l'idiome erase-remove) pour supprimer physiquement les restes.
