Module 9 - cours du 3 novembre (quiz 8) - matière du final

STL : algorithmes, foncteurs et fonctions lambda

Leçon Moodle « STL » (algorithmes) | Simulateur de hockey : exercice « Algorithmes STL et foncteurs » (éliminer toutes les boucles de Match) | Déjà utilisé au TP3 (sommer avec une lambda) ; central au TP4

<algorithm>, <numeric>find_if, count_if, for_eachsort avec comparateurtransform, accumulateerase-removeFoncteur : operator()Lambda et captures

1. Les algorithmes : des boucles toutes faites

Un algorithme de la STL est une fonction générique qui travaille sur un intervalle d'itérateurs [debut, fin[, donc sur n'importe quel conteneur (et même sur un tableau C). Beaucoup prennent en plus une fonction (prédicat, opération, comparateur) qui décide quoi faire de chaque élément. Remplacer une boucle par un algorithme rend l'intention lisible (« compter », « chercher », « transformer ») et évite les erreurs d'indices.

Catégorie	Algorithmes	Retour
Recherche et comptage (sans modification)	`find(b, e, val)`, `find_if(b, e, pred)`, `count(b, e, val)`, `count_if(b, e, pred)`, `any_of` / `all_of` / `none_of(b, e, pred)`, `min_element` / `max_element(b, e[, comp])`, `equal(b, e, b2)`	itérateur (`e` si absent), entier, booléen
Parcours	`for_each(b, e, f)`	la fonction (utile pour un foncteur avec état)
Modification	`copy(b, e, dest)`, `copy_if(b, e, dest, pred)`, `transform(b, e, dest, f)`, `fill(b, e, val)`, `replace(b, e, old, nouveau)`, `replace_if`, `reverse(b, e)`, `swap_ranges`, `generate(b, e, f)`	itérateur de fin de destination
Suppression	`remove(b, e, val)`, `remove_if(b, e, pred)`, `unique(b, e)`	nouvelle fin logique (la taille ne change pas !)
Tri et recherche binaire	`sort(b, e[, comp])`, `stable_sort`, `partial_sort`, `binary_search(b, e, val)`, `lower_bound`, `upper_bound`, `equal_range`, `merge`, `partition(b, e, pred)`	bool ou itérateur
Numérique (`<numeric>`)	`accumulate(b, e, init[, op])`, `inner_product`, `iota(b, e, debut)`, `partial_sum`	valeur

L'idiome erase-remove

remove et remove_if ne peuvent pas changer la taille d'un conteneur (ils ne connaissent que des itérateurs) : ils compactent les éléments à garder au début et retournent un itérateur sur la nouvelle fin logique. Les éléments après sont indéterminés. Il faut donc enchaîner avec erase :

2. Foncteurs : des objets qui s'appellent comme des fonctions

Un foncteur (objet-fonction) est un objet d'une classe qui surcharge operator(). On l'utilise comme une fonction, mais il peut avoir des attributs : un seuil, un compteur, un flux de sortie. C'est la façon classique de paramétrer un algorithme avec un état.

Foncteurs standard de <functional> : less<T>, greater<T>, plus<T>, minus<T>, multiplies<T>, equal_to<T>, logical_not<T>. Exemple : accumulate(b, e, 1, multiplies<int>()) pour un produit.
Un comparateur doit définir un ordre strict : a < b, jamais <= (sinon comportement indéfini de sort et des set).
operator() est const pour un prédicat ou un comparateur (l'algorithme peut recevoir une copie constante) ; non const si le foncteur accumule.

Le simulateur de hockey sans boucles

3. Fonctions lambda

Une lambda est un foncteur anonyme écrit sur place : le compilateur génère la classe (avec operator() et des attributs pour les captures) à votre place. Syntaxe : [captures](paramètres) -> type_de_retour { corps }. Le type de retour est déduit s'il est omis.

Capture	Effet
`[]`	aucune variable extérieure (seules les variables globales et les paramètres sont accessibles)
`[x]`	`x` copiée au moment de la création ; non modifiable dans la lambda sauf `mutable`
`[&x]`	`x` par référence : modifications visibles à l'extérieur ; `x` doit survivre à la lambda
`[=]` / `[&]`	toutes les variables utilisées, par valeur / par référence
`[this]`	accès aux membres de l'objet courant (dans une méthode)
`[=, &total]`	mixte : tout par valeur sauf `total` par référence

Chaque lambda a un type unique et anonyme : on la reçoit dans un paramètre générique (template <typename Fonction>, comme sommer au TP3) ou dans un std::function<bool(int)> (<functional>), qui peut aussi contenir une fonction ou un foncteur.
Lambda générique (C++14) : [](const auto& c) { ... } : le paramètre est déduit, pratique pour les shared_ptr.
Quand choisir ? Lambda : court, local, à usage unique. Foncteur : réutilisable, nommé, avec état ou plusieurs méthodes. Pointeur de fonction : fonctions existantes sans état.

4. À retenir

Algorithmes sur [begin, end[ ; retour : itérateur (end si absent), nombre, booléen. back_inserter pour remplir un conteneur vide, ostream_iterator pour afficher.
remove / remove_if / unique ne suppriment pas : c.erase(remove..., c.end()).
Foncteur = classe avec operator() ; peut avoir un état ; for_each le retourne. Comparateur : ordre strict, const, type passé en paramètre de template pour set / map / priority_queue.
Lambda [captures](params) { corps } ; par valeur (copie figée) ou par référence ; [this] dans une méthode ; mutable pour modifier une capture par valeur ; type unique → auto, template ou std::function.

Quiz rapide - Module 9

Que retourne find(v.begin(), v.end(), 42) si 42 est absent ?

nullptr
v.end()
-1
Une exception

Toujours tester if (it != v.end()) avant de déréférencer.

Après remove_if(v.begin(), v.end(), pred) seul, la taille de v :

Diminue du nombre d'éléments retirés
Devient 0
Ne change pas : les éléments à garder sont compactés au début, il faut appeler erase avec l'itérateur retourné
Double

C'est l'idiome erase-remove.

Qu'est-ce qu'un foncteur ?

Un objet d'une classe qui surcharge operator(), utilisable comme une fonction et pouvant avoir un état
Un pointeur de fonction
Une fonction générique
Une méthode statique

Exemples standard : greater<int>, less<T>, plus<T>.

Pourquoi Compteur c; for_each(v.begin(), v.end(), c); c.get(); retourne-t-il 0 même si des éléments ont été comptés ?

for_each ne fonctionne pas avec des foncteurs
get() est const
operator() n'a pas été appelé
Le foncteur est passé par valeur : for_each travaille sur une copie, qu'il retourne ; il faut récupérer cette copie

Compteur r = for_each(...); r.get();

Quelle lambda capture total de façon à le modifier ?

[total](int n) { total += n; }
[&total](int n) { total += n; }
[=](int n) { total += n; }
[](int n) { total += n; }

Par valeur, total est une copie constante (erreur de compilation sans mutable, et même avec mutable l'original ne change pas). Sans capture, total n'est pas accessible.

Que vaut x à la fin ? int a = 1; auto f = [a]() { return a; }; a = 7; int x = f();

7
Erreur de compilation
1 : la capture par valeur copie a au moment de la création de la lambda
0

Avec [&a], x vaudrait 7.

Quel comparateur est correct pour trier des robots par masse croissante ?

[](const Robot& a, const Robot& b) { return a.getMasse() < b.getMasse(); }
[](const Robot& a, const Robot& b) { return a.getMasse() <= b.getMasse(); }
[](Robot a, Robot b) { return a < b; }
[](const Robot& a) { return a.getMasse(); }

Deux paramètres, ordre strict (jamais <=), par référence constante pour ne pas copier.

Que calcule accumulate(v.begin(), v.end(), 0) pour vector<double> v = {0.5, 0.5} ?

1.0
Erreur de compilation
2
0 : la valeur initiale 0 est un int, les additions se font en int (troncature)

Écrire accumulate(v.begin(), v.end(), 0.0).

À quoi sert back_inserter(w) ?

À insérer au début de w
À fournir un itérateur de sortie qui fait push_back dans w à chaque écriture (w peut être vide)
À trier w
À retirer le dernier élément de w

Sans lui, copy(b, e, w.begin()) sur un w vide écrirait hors du conteneur.

Comment stocker une lambda dans un attribut de classe ?

lambda f_;
auto f_;
std::function<bool(int)> f_;
Impossible

auto n'est pas permis pour un attribut non statique ; std::function accepte lambdas, foncteurs et fonctions de signature compatible.

Que fait transform(v.begin(), v.end(), v.begin(), f) ?

Remplace chaque élément par f(élément), sur place
Trie v selon f
Retire les éléments pour lesquels f est faux
Copie v dans f

Le troisième argument est la destination ; ici le conteneur lui-même.

Dans une méthode de Robot, une lambda a besoin de l'attribut facteur_. Quelle capture ?

[facteur_]
[&facteur_]
Aucune : les attributs sont toujours visibles
[this] (ou [=] / [&], qui capturent this implicitement)

Un attribut n'est pas une variable locale : on capture l'objet courant.

Quel algorithme remplace cette boucle ? bool ok = true; for (const auto& m : membres) if (m->getSalaire() > cap) ok = false;

count(...)
bool ok = none_of(membres.begin(), membres.end(), [cap](const auto& m) { return m->getSalaire() > cap; });
find(...)
sort(...)

Ou all_of avec le prédicat inverse (<= cap).

Exercices à développement

Simulateur de hockeyAlgorithmes

Match sans aucune boucle

Match possède list<Joueur*> joueurs_ et list<Arbitre*> arbitres_. Réécrivez sans boucle explicite : simuler() (fait jouer tous les patineurs), int getButs(bool equipe) const, bool valider() const (chaque équipe a exactement 3 joueurs), void afficherEquipe(bool equipe) const et Joueur* meilleurButeur() const.

Solution

L'exercice original demande des foncteurs nommés (FoncteurJouer, FoncteurGetButs, FoncteurValider, AfficherElement) : chaque lambda ci-dessus se transpose en une classe avec operator() et les captures en attributs.

Foncteurs

Trois foncteurs

Écrivez : (1) DansIntervalle, prédicat vrai si une valeur est dans [min, max] ; (2) Multiplier, qui multiplie par un facteur (pour transform) ; (3) Statistiques, un foncteur avec état qui accumule somme, minimum et maximum (pour for_each), et montrez l'utilisation de chacun.

Solution

LambdasTP3 / TP4

Robot et algorithmes

Avec vector<shared_ptr<Composante>> composantes_, écrivez avec des algorithmes et des lambdas : (1) double getMasse() const ; (2) shared_ptr<Composante> plusGourmande() const (consommation maximale, nullptr si vide) ; (3) vector<string> nomsLourds(double seuil) const (noms des composantes dont la masse dépasse le seuil) ; (4) void retirerInactifs() qui retire les capteurs inactifs (utiliser dynamic_pointer_cast) ; (5) bool contient(const string& nom) const.

Solution

Algorithmesmap

Inventaire

Avec map<string, int> stock (article → quantité) : (1) affichez les articles en rupture (quantité 0) avec for_each ; (2) calculez le total des quantités avec accumulate ; (3) trouvez l'article le plus stocké avec max_element ; (4) construisez un vector<string> des articles dont la quantité est inférieure à un seuil, trié par quantité croissante.

Solution

Détail : vector<Entree> avec une clé const ne se trie pas (les éléments ne sont pas affectables) : en pratique utiliser pair<string, int> pour le vecteur intermédiaire.

AffichageCaptures