Programmer avec des algorithmes

Ce texte est court, ayant été écrit à un moment où je n'avais pas vraiment pas le temps de l'écrire. Cela dit, je me suis aperçu accidentellement que je n'avais aucun texte sur mon site (mais plusieurs dans mes notes de cours!) sur la programmation à l'aide d'algorithmes. Je voulais donc « boucher un trou » rapidement...

Il est présumé au préalable que vous êtes familière ou familier avec les conteneurs et les itérateurs de C++. Idéalement, les λ-expressions ne vous sont pas étrangères non plus.

La pratique de la programmation est une chose complexe, mais dans laquelle on voit régulièrement apparaître à la fois des designs récurrents. Certains de ces designs sont de haut niveau : des schémas de conception, façons de faire qui tendent à s'appliquer à plusieurs langages de programmation, ou des idiomes de programmation propres à certains langages.

 D'autres sont plus simples mais tout aussi récurrents...

Appliquer une même opération à plusieurs éléments d'une séquence (p. ex. : écrire chaque élément sur un flux).

 
// ...
vector<string> v;
// ... remplir v ...
ofstream out{ "sortie.txt" };
for(auto it = begin(v); it != end(v); ++it)
   out << *it << ' ';
out << flush;
// ...

Remplacer chaque élément d'une séquence par le fruit d'une opération sur lui (p. ex. :remplacer chaque valeur par son carré).

 
// ...
auto carre = [](float f) { return f * f; };
vector<float> v;
// ... remplir v ...
for(auto it = begin(v); it != end(v); ++it)
   *it = carre(*it);
// ...

Calculer la somme d'une séquence de valeurs (ou le produit, ou trouver le minimum, ou...).

 
// ...
vector<int> v;
// ... remplir v ...
long long cumul {};
for(auto it = begin(v); it != end(v); ++it)
   cumul += *it;
// ...

Trouver le premier élément d'une séquence pour lequel un prédicat s'avère; etc.

 
// ...
vector<string> v;
using size_type = string::size_type;
size_type n {};
if (cin >> n) {
   // ... remplir v ...
   auto plus_long = [n](const string &s) {
      return s.size() > n;
   };
   auto it = begin(v);
   for(; it != end(v); ++it)
      if (plus_long(*it))
         break; // beurk
   if (it != end(v))
      cout << "Premier element plus long que "
           << n << " : " << *it << endl;
   else
      cout << "Aucun element plus long que "
           << n << endl;
}
// ...

Bien qu'il soit possible d'écrire des solutions manuelles à ces problèmes de la vie courante, il s'agit d'une pratique malsaine :

Il existe dans la bibliothèque standard de C++ un en-tête merveilleux nommé <algorithm> (et d'autres, en particulier <numeric>, pour des usages plus spécialisés) qui colligent des algorithmes parfois banals (pensons à   for_each(), à   iota() ou à  transform()), parfois très complexes (shuffle(), pour prendre un cas parmi plusieurs).

Recommandations simples :

Reprenons les exemples plus haut, à titre d'illustrations.

Opération souhaitée Version avec algorithme standard Version manuelle (rappel)

Dans le cas « appliquer une même opération à plusieurs éléments d'une séquence », bien que les deux solutions se ressemblent en termes de complexité d'écriture, celle avec algorithme standard a plusieurs avantages :

  • Elle sera légèrement plus rapide en général, dû aux opportunités supplémentaires d'optimisation qu'a le compilateur quand il connaît l'intention derrière l'écriture
  • Elle n'aura pas d'erreurs de gestion de compteur ou de condition d'arrêt, et fera nécessairement les meilleurs choix possibles (p. ex. : utiliser la préincrémentation pour le compteur, qui est plus rapide que la post-incrémentation), et
  • Elle cache au code client les détails syntaxiques des itérateurs, en particulier le recours à l'opérateur de déréférencement pour accéder à la valeur

Dans ce cas bien précis, l'algorithme est si commun que, depuis C++ 11, on trouve une forme spécialisée de la boucle for pour l'exprimer de manière encore plus concise :

for(const auto & s : v)
   out << s << ' ';

Vous trouverez plus de détails à son sujet sur ../../Liens/Caracteristiques-Cplusplus--Liens.html#range_based_for. Notez toutefois que, depuis C++ 17, il est possible d'exécuter la plupart plusieurs des algorithmes standards en parallèle, et il suffit pour cela d'ajouter un paramètre. Ceci assure une pertinence certaine à std::for_each() malgré tout.

 
// ...
vector<string> v;
// ... remplir v ...
ofstream out{"sortie.txt"};
for_each(begin(v), end(v), [&](const string &s) {
   out << s << ' ';
});
out << flush;
// ...
 
// ...
vector<string> v;
// ... remplir v ...
ofstream out{"sortie.txt"};
for(auto it = begin(v); it != end(v); ++it)
   out << *it << ' ';
out << flush;
// ...

Dans le cas « remplacer chaque élément d'une séquence par le fruit d'une opération sur lui », l'écriture avec algorithme standard est plus concise. Notez que le troisième paramètre à  transform() est le début de la séquence de destination, ce qui permet d'écrire les résultats des calculs ailleurs que dans la séquence source comme nous le faisons ici.

Nous aurions bien sûr pu imbriquer l'opération dans l'appel à  transform() pour obtenir l'écriture suivante, encore plus concise :

transform(begin(v), end(v), begin(v), [](float f) { return f * f; });
 
// ...
auto carre = [](float f) { return f * f; };
vector<float> v;
// ... remplir v ...
transform(begin(v), end(v), begin(v), carre);
// ...
 
// ...
auto carre = [](float f) { return f * f; };
vector<float> v;
// ... remplir v ...
for(auto it = begin(v); it != end(v); ++it)
   *it = carre(*it);
// ...

Dans le cas « calculer la somme d'une séquence de valeurs (ou le produit, ou trouver le minimum, ou...) », l'algorithme accumulate() de <numeric> fait un excellent travail. Pour en savoir plus à son sujet, voir ../Maths/Notation-et-code.html

Notez que le type du troisième opérande (la valeur initiale du cumul) sera aussi le type du calcul réalisé par accumulate(), ce qui explique le choix du littéral 0LL ici (nous voulons une somme cumulée sur un long long).

 
// ...vector<int> v;
// ... remplir v ...
auto cumul = accumulate(begin(v), end(v), 0LL);
// ...
 
// ...
vector<int> v;
// ... remplir v ...
long long cumul {};
for(auto it = begin(v); it != end(v); ++it)
   cumul += *it;
//// ...

Dans le cas « trouver le premier élément d'une séquence pour lequel un prédicat s'avère », l'algorithme find_if() est tout désigné. Remarquez que les manoeuvres discutables réalisées pour fins d'optimisation dans la version manuelle (en particulier, la sortie inconditionnelle de la répétitive) sont complètement disparues du code reposant sur un algorithme standard.

Le résultat est plus rapide, plus concis, et plus élégant; de plus, il est moins obscurci par des détails techniques et va directement à l'essentiel.

 
// ...vector<string> v;
using size_type = string::size_type;
size_type n {};
if (cin >> n) {
   // ... remplir v ...
   auto itt = find_if(begin(v), end(v), [n](const string &s) {
      return s.size() > n;
   });
   if (itt != end(v))
      cout << "Premier element plus long que "
           << n << " : " << *itt << endl;
   else
      cout << "Aucun element plus long que "
           << n << endl;
}
// ...
 
// ...
vector<string> v;
using size_type = string::size_type;
size_type n {};
if (cin >> n) {
   // ... remplir v ...
   auto plus_long = [n](const string &s) {
      return s.size() > n;
   };
   auto it = begin(v);
   for(; it != end(v); ++it)
      if (plus_long(*it))
         break; // beurk
   if (it != end(v))
      cout << "Premier element plus long que "
           << n << " : " << *it << endl;
   else
      cout << "Aucun element plus long que "
           << n << endl;
}
// ...

Ne vous privez pas : étudiez vos algorithmes, utilisez-les, améliorez votre code (et votre productivité!), déboguez moins et simplifiez votre existence.

Créer son propre algorithme

Supposons que vous ayez rédigé une répétitive accomplissant une tà¢che pour laquelle vous ne trouvez pas d'algorithme standard. Par exemple, ce qui suit :

// ...
vector<int> v;
auto est_pair = [](int n) { return n % 2 == 0; };
// ...remplir v ...
for(auto it = begin(v); it != end(v); ++it)
   if (est_pair(*it))
      *it = -(*it);
// ...

Cet algorithme ne vous semble pas vraiment être un cas de transform(), puisqu'il ne modifie que certains éléments de la séquence, soit ceux qui sont pairs. Ce serait plus une sorte de « transform_if() », mais un tel algorithme n'existe pas.

Bien que la répétitive manuelle fonctionne, évidemment, mais fait montre des inconvénients (documentaires et techniques) mentionnés plus haut. La solution la plus élégante est sans doute d'écrire un algorithme de notre cru! En étudiant le code existant, on remarque un certain nombre d'éléments clés, en commentaires ci-dessous :

// ...
vector<int> v;
auto est_pair = [](int n) { return n % 2 == 0; };
// ...remplir v ...
for(auto it = begin(v); it != end(v); ++it) // structure générale d'un transform()
   if (est_pair(*it)) // nécessite un prédicat, par exemple est_pair
      *it = -(*it); // nécessite une fonction à   appliquer, par exemple « negation_arithmetique »
// ...

Ainsi, une écriture correcte serait :

// ...
template <class InIt, class OutIt, class Pred, class F>
   void transform_if(InIt debut, InIt fin, OutIt dest, Pred pred, F fct) {
      for(; debut != fin; ++debut, ++dest)
         if (pred(debut))
            *dest = fct(*debut);
   }
// ...

On aurait pu aussi profiter de l'existence (et des qualités techniques!) de transform() et de la flexibilité des λ pour exprime le même algorithme comme suit (remarquez le recours à des traits dans cet exemple) :

// ...
template <class InIt, class OutIt, class Pred, class F>
   void transform_if(InIt debut, InIt fin, OutIt dest, Pred pred, F fct) {
      using namespact std;
      using value_type = typename
         iterator_traits<InIt>::value_type;
      transform(debut, fin, dest, [=](value_type val) {
         return pred(val)? fct(val) : val;
      });
   }
// ...

Enfin, le code client deviendrait :

// ...
vector<int> v;
auto est_pair = [](int n) { return n % 2 == 0; };
// ...remplir v ...
transform_if(begin(v), end(v), begin(v), est_pair, [](int n) { return -n });
// ...

... ou encore, de manière plus compacte :

// ...
vector<int> v;
// ...remplir v ...
transform_if(
   begin(v), end(v), begin(v),
   [](int n) { return n % 2 == 0; },
   [](int n) { return -n }
);
// ...

Exercice

Soit l'ébauche de code suivant. Complétez le tout en respectant les consignes données dans les commentaires.

//
// Incluez ce dont vous avec besoin
//

int main() {
   cout << "Combien d'elements? ";
   int n;
   if (!(cin >> n) || n < 0) return -1;
   //
   // Créez un conteneur capable de contenir n éléments
   //

   //
   // Générez n entiers pseudoaléatoires entre 1 et 100 dans ce conteneur
   //
   // <random>, <algorithm>
   // Utilisez uniform_int_distribution, random_device, mt19937 et generate_n()
   //

   //
   // Partitionnez le conteneur pour que les pairs soient d'un côté et les impairs de l'autre
   //
   // <algorithm>
   // Utilisez partition()
   //

   //
   // Triez les pairs en ordre croissant
   //
   // <algorithm>
   // Utilisez sort()
   //

   //
   // Triez les impairs en ordre décroissant
   //
   // <algorithm>
   // Utilisez sort()
   //

   //
   // Affichez les éléments du conteneur, avec " | " entre chacun
   //
   // <algorithm>
   // Utilisez for_each() et next()
   //

   //
   // Transformez chaque nombre en son négatif
   //
   // <algorithm>
   // Utilisez transform()
   //

   //
   // Affichez les éléments du conteneur, avec " | " entre chacun
   //
   // <algorithm>
   // Utilisez for_each() et next()
   //

   //
   // Transformez chaque nombre en son négatif
   //
   // Utilisez une boucle for simplifiée
   //

   //
   // Affichez les éléments du conteneur, avec " | " entre chacun
   //
   // <algorithm>
   // Utilisez for_each() et next()
   //

   //
   // Mélangez les
   //
   // <algorithm>, <random>
   // Utilisez shuffle(), random_device et mt19937
   //

   //
   // Affichez les éléments du conteneur, avec " | " entre chacun
   //
   // <algorithm>
   // Utilisez for_each() et next()
   //

   //
   // Indiquez la position et la valeur du plus petit et du plus gros élément
   //
   // <algorithm>
   // Utilisez minmax_element()
   //

   //
   // Y a-t-il un élément qui soit divisible par trois? Si oui, lequel est-ce et à quel indice est-il?
   //
}

Quand vous aurez complété le tout, je vous invite à comparer vos réponses avec ce qui suit (cliquez ici pour révéler une solution possible (ou pour la cacher!)).

Lectures complémentaires

Quelques liens pour enrichir le propos.

Valid XHTML 1.0 Transitional

CSS Valide !