Bases – Solutions

Ce qui suit liste des solutions pour les problèmes proposés dans les séries d'exercices Bases.

Exercice EX00

Pour cet exercice, une solution possible serait :

EX00 (avant) EX00 (après)
#include <string>
#include <locale>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
string transformer_majuscules(string originale) {
   string resultat;
   for (string::size_type i = 0; i < originale.size(); i++) {
      char c;
      c = toupper(originale[i], locale::classic());
      resultat = resultat + c;
   }
   return resultat;
}
int main() {
   const int TAILLE = 5'000'000;
   string texte(TAILLE, 'a');
   string resultat;
   auto avant = system_clock::now();
   resultat = transformer_majuscules(texte);
   auto apres = system_clock::now();
   cout << "Transformer en majuscules v1 " << TAILLE << " caractères: "
        << duration_cast<milliseconds>(apres- avant).count() << " ms." << endl;
}
#include <string>
#include <locale>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
string transformer_majuscules(string s) {
   using namespace std;
   auto loc = locale::classic();
   for (string::size_type i = 0; i < s.size(); i++)
      s[i] = toupper(s[i], loc);
   return resultat;
}
int main() {
   const int TAILLE = 5'000'000;
   string texte(TAILLE, 'a');
   string resultat;
   auto avant = system_clock::now();
   resultat = transformer_majuscules(texte);
   auto apres = system_clock::now();
   cout << "Transformer en majuscules v2 " << TAILLE << " caractères: "
        << duration_cast<milliseconds>(apres- avant).count() << " ms." << endl;
}

La solution proposée ici peut ne pas être optimale, mais montre comment on peut, de manière portable et à peu de frais, améliorer la version originale de la fonction transformant un mot en majuscules...

Le plus gros gain de vitesse ici (de très loin!) est le remplacement du recours à l'opérateur +, qui provoque la création d'objets temporaires, par une alternative plus saine. Utiliser l'opérateur +=, qui insère à la fin d'une séquence existante (ou, pour du code plus général, la méthode push_back()) aurait en soi amélioré drastiquement la vitesse d'exécution de cette fonction.

Un autre gain, plus petit (mais appréciable), tient à l'utilisation de la constante locale loc. Voyez-vous pourquoi? Si vous lisez la documentation de std::toupper() et de std::locale, vous aurez peut-être la puce à l'oreille...

Notez qu'avec un compilateur récent, il est possible de remplacer ceci :

for(string::size_type i = 0; i < original.size(); ++i)
   original[i] = toupper(original[i], loc);

... par cela :

for(auto & c : original)
   c = toupper(c, loc);

... qui est plus concis, plus simple et tout aussi rapide. Vous auriez aussi pu envisager utiliser std::for_each ou std::transform.

Exercice EX01

Ici encore, quelques menus changements peuvent faire une grosse différence. Cependant, l'impact des changements que vous aurez apportés ici dépendront beaucoup des choix d'implémentation derrière la classe std::string pour votre compilateur, alors il se peut que vous ayez des améliorations importantes avec certains compilateurs et des améliorations limitées avec d'autres.

Dans l'exemple de solution proposé ici, quelques constats peuvent être faits :

Sous C++ 11, les gains seront très petits dû à l'ajout de la sémantique de mouvement et des références sur des rvalue.

Les exemples avant et après suivent (ci-dessous). Pour obtenir un meilleur comparatif, vous pouvez placer des deux versions de la fonction dans un même programme (quitte à les placer dans des espaces nommés distincts, par exemple avant::trier_texte et apres::trier_texte) et les tester successivement sur les mêmes données (c'est très important pour obtenir un test valable), puis afficher leurs performances respectives.

EX01 (avant) EX01 (après) 
#include <string>
#include <random>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
string trier_texte(string originale) {
   string resultat, avant_milieu, apres_milieu;
   string::size_type milieu;
   switch (originale.size()) {
   case 2:
      if (originale[0] < originale[1]) {
         resultat += originale[0];
         resultat += originale[1];
      } else {
         resultat += originale[1];
         resultat += originale[0];
      }
      break;
   case 1:
   case 0:
      resultat = originale;
      break;
   default:
   {
      milieu = originale.size() / 2;
      avant_milieu = trier_texte(originale.substr(0, milieu));
      apres_milieu = trier_texte(originale.substr(milieu));
      string::size_type av = 0, ap = 0;
      while (av < avant_milieu.size() && ap < apres_milieu.size())
      {
         if (avant_milieu[av] < apres_milieu[ap]) {
            resultat += avant_milieu[av];
            av++;
         } else {
            resultat += apres_milieu[ap];
            ap++;
         }
      }
      if (av < avant_milieu.size()) {
         resultat += avant_milieu.substr(av);
      } else if (ap < apres_milieu.size()) {
         resultat += apres_milieu.substr(ap);
      }
   }
   return resultat;
}
string generer_texte(int taille) {
   random_device rd;
   mt19937 prng { rd() };
   uniform_int_distribution<int> de{0, static_cast<int>('z'-'a')};
   string temp;
   for (int i = 0; i < taille; i++)
      temp += de(prng) + 'a';
   return temp;
}
int main() {
   const int TAILLE = 100'000;
   string texte = generer_texte(TAILLE);
   auto avant = system_clock::now();
   auto texteTrie = trier_texte(texte);
   auto apres = system_clock::now();
   cout << "Avant: " << texte << endl
        << "Après: " << texteTrie << endl
        << "Tri de " << TAILLE << " caractères: "
        << duration_cast<milliseconds>(apres- avant).count() << " ms." << endl;
}
 
#include <string>
#include <random>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
string trier_texte(const string &originale) {
   string resultat;
   switch (originale.size()) {
   case 2:
      if (originale[0] < originale[1]) {
         resultat += originale[0];
         resultat += originale[1];
      } else {
         resultat += originale[1];
         resultat += originale[0];
      }
      break;
   case 1:
   case 0:
      resultat = originale;
      break;
   default:
   {
      const string::size_type milieu = originale.size() / 2;
      auto avant_milieu = trier_texte(originale.substr(0, milieu));
      auto apres_milieu = trier_texte(originale.substr(milieu));
      string::size_type av = 0, ap = 0;
      while (av < avant_milieu.size() && ap < apres_milieu.size()) {
         if (avant_milieu[av] < apres_milieu[ap]) {
            resultat += avant_milieu[av];
            av++;
         } else {
            resultat += apres_milieu[ap];
            ap++;
         }
      }
      if (av < avant_milieu.size())
         resultat += avant_milieu.substr(av);
      else if (ap < apres_milieu.size())
         resultat += apres_milieu.substr(ap);
   }
   return resultat;
}
string generer_texte(int taille) {
   random_device rd;
   mt19937 prng { rd() };
   uniform_int_distribution<int> de{0, static_cast<int>('z'-'a')};
   string temp;
   for (int i = 0; i < taille; i++)
      temp += de(prng) + 'a';
   return temp;
}
int main() {
   const int TAILLE = 100'000;
   string texte = generer_texte(TAILLE);
   auto avant = system_clock::now();
   auto texteTrie = trier_texte(texte);
   auto apres = system_clock::now();
   cout << "Avant: " << texte << endl
        << "Après: " << texteTrie << endl
        << "Tri de " << TAILLE << " caractères: "
        << duration_cast<milliseconds>(apres- avant).count() << " ms." << endl;
}

Petite remarque à propos de generer_texte() : en pratique, personnellement, je l'écrirais comme ceci :

string generer_texte(int n) {
   random_device rd;
   mt19937 prng { rd() };
   uniform_int_distribution<> de{ 0, static_cast<int>('z'-'a') };
   string temp;
   temp.reserve(n); // pour n'avoir qu'une seule réallocation
   generate_n(back_inserter(temp), n, [&]() {
      return de(prng) + 'a';
   });
   return temp;
}

En appelant reserve(), on assure une allocation unique d'espace pour temp (ici, selon la valeur de n, cela peut éviter plusieurs new[], plusieurs delete[] et plusieurs copies de contenu). L'algorithme generate_n() générera n valeurs en se basant sur la λ utilisée comme troisième paramètre. L'adaptateur back_inserter transforme les écritures sur « son » itérateur en appels à push_back() et y ajoute des éléments à la fin.

Si mon compilateur ne supportait pas C++ 11, alors je remplacerais ma λ par un foncteur.

Exercice EX02

Pour cet exercice, une solution possible serait :

EX02 (avant) EX02 (après) EX02 (plus moderne)
struct Noeud {
   Noeud *succ;
   int val;
   // AJOUTEZ ICI
};
class ListeEntiers {
   Noeud *tete;
public:
   class ListeVide { };
   // AJOUTEZ ICI
   bool est_vide() const noexcept {
      return tete == nullptr;
   }
   void ajouter(int val) {
      if (est_vide())
         tete = new Noeud{val};
      else {
         auto p = tete;
         while (p->succ) p = p->succ;
         p->succ = new Noeud{val};
      }
   }
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      const int val = p->val;
      delete p;
      return val;
   }
   int taille() const noexcept {
      int n = 0;
      for(auto p = tete; p; p = p->succ)
         ++n;
      return n;
   }
   void inverser() {
      Noeud *nouvelle_tete = {};
      while (tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelle_tete;
         nouvelle_tete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelle_tete;
   }
};
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter(i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
}
#include <utility>
struct Noeud {
   Noeud *succ;
   int val;
   //
   // AJOUT: constructeur paramétrique
   //
   Noeud (int val)
      : succ{}, val{val}
   {
   }
   //
   // AJOUT: constructeur de copie
   //
   Noeud(const Noeud &n)
      : succ{}, val{n.val}
   {
   }
};
class ListeEntiers {
   Noeud *tete;
public:
   class ListeVide { };
   //
   // AJOUT: constructeur par défaut de ListeEntiers
   //
   ListeEntiers() noexcept : tete{} {
   }
   //
   // AJOUT: constructeur de copie de ListeEntiers
   //
   ListeEntiers(const ListeEntiers &lst) : tete{} {
      for (auto p = lst.tete; p; p = p->succ)
         ajouter(p->val);
   }
   //
   // AJOUT: méthode swap(ListeEntiers&)
   //
   void swap(ListeEntiers &lst) {
      using std::swap;
      swap(tete,lst.tete);
   }
   //
   // AJOUT: opérateur d'affectation
   //
   ListeEntiers& operator=(const ListeEntiers &lst) {
      ListeEntiers{ lst }.swap(*this);
      return *this;
   }
   //
   // AJOUT: destructeur
   //
   ~ListeEntiers() {
      while(!est_vide())
         extraire();
   }
   bool est_vide() const noexcept {
      return tete == nullptr;
   }
   void ajouter(int val) {
      if (est_vide())
         tete = new Noeud{val};
      else {
         auto p = tete;
         while (p->succ) p = p->succ;
         p->succ = new Noeud{val};
      }
   }
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      const int val = p->val;
      delete p;
      return val;
   }
   int taille() const noexcept {
      int n = 0;
      for(auto p = tete; p; p = p->succ)
         ++n;
      return n;
   }
   void inverser() {
      Noeud *nouvelle_tete = nullptr;
      while (tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelle_tete;
         nouvelle_tete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelle_tete;
   }
};
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter(i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
}
#include <utility>
struct Noeud {
   Noeud *succ = nullptr;
   int val;
   //
   // AJOUT: constructeur paramétrique
   //
   Noeud (int val) : val{ val } {
   }
   //
   // AJOUT: constructeur de copie
   //
   Noeud(const Noeud &n) : val{ n.val } {
   }
};
class ListeEntiers {
   Noeud *tete = nullptr;
public:
   class ListeVide { };
   //
   // AJOUT: constructeur par défaut de ListeEntiers
   //
   ListeEntiers() = default;
   //
   // AJOUT: constructeur de copie de ListeEntiers
   //
   ListeEntiers(const ListeEntiers &lst) {
      for (auto p = lst.tete; p; p = p->succ)
         ajouter(p->val);
   }
   //
   // AJOUT: méthode swap(ListeEntiers&)
   //
   void swap(ListeEntiers &lst) {
      using std::swap;
      swap(tete,lst.tete);
   }
   //
   // AJOUT: opérateur d'affectation
   //
   ListeEntiers& operator=(const ListeEntiers &lst) {
      ListeEntiers{ lst }.swap(*this);
      return *this;
   }
   //
   // AJOUT: destructeur
   //
   ~ListeEntiers() {
      while(!est_vide())
         extraire();
   }
   bool est_vide() const noexcept {
      return tete == nullptr;
   }
   void ajouter(int val) {
      if (est_vide())
         tete = new Noeud{val};
      else {
         auto p = tete;
         while (p->succ) p = p->succ;
         p->succ = new Noeud{val};
      }
   }
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      const int val = p->val;
      delete p;
      return val;
   }
   int taille() const noexcept {
      int n = 0;
      for(auto p = tete; p; p = p->succ)
         ++n;
      return n;
   }
   void inverser() {
      Noeud *nouvelle_tete = nullptr;
      while (tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelle_tete;
         nouvelle_tete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelle_tete;
   }
};
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter(i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
}

L'important ici était :

Autres trucs intéressants :

Exercice EX03

Dans ce cas, on voulait voir comment utiliser un traitement d'exception pour réagir à l'occurrence de la fin de la liste... Évidemment, si vous deviez remettre cet exercice, ne négligez pas de remettre le code des classes Noeud et ListeEntiers aussi!

Notez que les boucles infinies à la while(true) (ici, j'ai utilisé un for ever, ou for(;;)) me donnent des boutons mais que dans ce cas-ci, l'idée était de démontrer une possibilité, pas une pratique recommandable.

//
// ...
//
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter(i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   try {
      for(;;)
         cout << lstInv.extraire() << " ";
   } catch (ListeEntiers::ListeVide&) {
   }
   cout << endl;
}

Exercice EX04

Les ajustements requis à la classe ListeEntiers pourraient être les suivants :

EX04 (avant) EX04 (après)
#include <utility>
struct Noeud {
   Noeud *succ = nullptr;
   int val;
   Noeud (int val) : val{ val } {
   }
   Noeud(const Noeud &n) : val{ n.val } {
   }
};
class ListeEntiers {
   Noeud *tete = nullptr;
public:
   class ListeVide { };
   ListeEntiers() = default;
   ListeEntiers(const ListeEntiers &lst) {
      for (auto p = lst.tete; p; p = p->succ)
         ajouter(p->val);
   }
   void swap(ListeEntiers &lst) {
      using std::swap;
      swap(tete,lst.tete);
   }
   ListeEntiers& operator=(const ListeEntiers &lst) {
      ListeEntiers{ lst }.swap(*this);
      return *this;
   }
   ~ListeEntiers() {
      while(!est_vide())
         extraire();
   }
   bool est_vide() const noexcept {
      return tete == nullptr;
   }
   void ajouter(int val) {
      if (est_vide())
         tete = new Noeud{val};
      else {
         auto p = tete;
         while (p->succ) p = p->succ;
         p->succ = new Noeud{val};
      }
   }
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      const int val = p->val;
      delete p;
      return val;
   }
   int taille() const noexcept {
      int n = 0;
      for(auto p = tete; p; p = p->succ)
         ++n;
      return n;
   }
   void inverser() {
      Noeud *nouvelle_tete = nullptr;
      while (tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelle_tete;
         nouvelle_tete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelle_tete;
   }
};
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter(i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
}
#include <utility>
struct Noeud {
   Noeud *succ = nullptr;
   int val;
   Noeud(int val) noexcept : val{val} {
   }
   Noeud(const Noeud &n) noexcept : val{n.val} {
   }
};
class ListeEntiers {
   Noeud *tete = nullptr;
   //
   // AJOUT: deux attributs
   //
   Noeud *fin = nullptr;
   int nelems = 0;
public:
   class ListeVide { };
   //
   // AJUSTEMENT: initialisations
   //
   ListeEntiers() = default;
   //
   // AJUSTEMENT: initialisations
   //
   ListeEntiers(const ListeEntiers &lst) {
      for (auto p = lst.tete; p; p = p->succ)
         ajouter(p->val);
   }
   //
   // AJUSTEMENT: permutation des nouveaux états
   //
   void swap(ListeEntiers &lst) {
      using std::swap;
      swap(tete,lst.tete);
      swap(fin,lst.fin);
      swap(nelems,lst.nelems);
   }
   ListeEntiers& operator=(const ListeEntiers &lst) {
      ListeEntiers{ lst }.swap(*this);
      return *this;
   }
   //
   // RAFFINEMENT : méthode pour vider efficacement la liste
   // (plus rapide que while(!est_vide()) extraire();)
   //
   void vider() {
      for(auto p = tete; p;) {
         auto q = p->succ;
         delete p;
         p = q;
      }
      tete = fin = nullptr;
      nelems = 0;
   }
   ~ListeEntiers() {
      vider();
   }
   //
   // AJUSTEMENT : ajout du mouvement
   //
   ListeEntiers(ListeEntiers &&autre)
      : tete{ autre.tete }, fin{ autre.fin }, nelems{ autre.nelems } {
      autre.tete = {};
      autre.fin = {};
      autre.nelems = {};
   }
   ListeEntiers& operator=(ListeEntiers &&autre) {
      if (this != &autre) {
         vider();
         tete = autre.tete;
         fin = autre.fin;
         nelems = autre.nelems;
         autre.tete = {};
         autre.fin = {};
         autre.nelems = {};
      }
      return *this;
   }
   bool est_vide() const noexcept {
      return tete == nullptr;
   }
   //
   // AJUSTEMENT: mise à jour des nouveaux états,
   // et passe de complexité O(n) à O(1)
   //
   void ajouter(int val) {
      auto p = new Noeud{val};
      if (est_vide())
         tete = fin = p;
      else {
         fin->succ = p;
         fin = p;
      }
      ++nelems;
   }
   //
   // AJUSTEMENT: mise à jour des nouveaux états
   //
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      const int val = p->val;
      if (p == fin) fin = nullptr;
      delete p;
      --nelems;
      return val;
   }
   //
   // AJUSTEMENT: passe de complexité O(n) à O(1)
   //
   int taille() const noexcept {
      return nelems;
   }
   //
   // AJUSTEMENT: mise à jour de fin (et pourrait être
   // bien plus rapide encore)
   //
   void inverser() {
      Noeud *nouvelle_tete = {},
            *nouvelle_fin = {};
      if (tete) {// cas particulier pour se charger de nouvelle_fin
         auto p = new Noeud{*tete};
         p->succ = nouvelle_tete;
         nouvelle_fin = nouvelle_tete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      while (tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelle_tete;
         nouvelle_tete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelle_tete;
      fin = nouvelle_fin;
   }
};
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter (i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
}

Quelques améliorations à la classe ListeEntiers :

Une amélioration sur laquelle j'aimerais que vous réfléchissiez reste à apporter : il est déraisonnable que la méthode inverser() ait recours à de l'allocation dynamique de mémoire. Pouvez-vous la modifier pour éliminer cet irritant? Une fois la modification réalisée, la méthode pourra-t-elle être qualifiée noexcept?

Exercice EX05

Oubliez cet exercice. Mon erreur.

Solutionner EX00 avec algorithmes standards, foncteurs et λ

Si vous êtes curieuse ou curieux, voici deux exemples de solutions à EX00 reposant sur un algorithme standard et un foncteur (ou encore une λ).

L'une des versions utilise std::for_each() et l'autre utilise sa cousine std::transform(), deux algorithmes que vous trouverez dans <algorithm>.

En gros, for_each() applique une opération à chaque élément d'une séquence et considère cette opération comme ne retournant rien, alors que transform() applique une opération à chaque élément d'une séquence et dépose le résultat de cette opérations dans une séquence (qui peut être la même ou être une séquence différente).

Les foncteurs utilisés dans chaque cas reflètent ces rôles : celui utilisé par for_each() prend un paramètre par référence et le modifie, alors que celui utilisé par transform() a le comportement d'une fonction au sens plus mathématique du terme.

 
template <class It, class Op>
   Op for_each(It debut, It fin, Op oper) {
      for (; debut != fin; ++debut)
         oper(*debut);
      return oper;
   }
template <class II, class OI, class Op>
   void transform(II ds, II fs, OI dd, Op oper) {
      for (; ds != fs; ++ds, ++dd)
         *dd = oper(*ds);
   }

Dans les deux cas, les modifications sont faites directement sur la chaîne reçue en paramètre, qui est une copie de la chaîne fournie à l'appel, ce qui évite d'avoir recours à une variable temporaire supplémentaire.

Avec std::for_each() Avec std::transform() 
#include <string>
#include <locale>
#include <algorithm>
using namespace std;
class Majuscules {
   const locale &loc;
public:
   Majuscules(const locale &loc = locale::classic()) : loc{ loc } {
   }
   void operator()(char &c) const {
      c = toupper(c, loc);
   }
};
string transformer_majuscules(string s) {
   for_each(begin(s), end(s), Majuscules{});
   return s;
}
 
#include <string>
#include <locale>
#include <algorithm>
using namespace std;
class Majuscules {
   const locale &loc;
public:
   Majuscules(const locale &loc = locale::classic()) : loc{ loc } {
   }
   char operator()(char c) const {
      return toupper(c, loc); }
   }
};
string transformer_majuscules(string s) {
   transform(begin(s), end(s), begin(s), Majuscules{});
   return s;
}

Avec des λ, le tout devient :

Avec std::for_each() Avec std::transform() 
#include <string>
#include <locale>
#include <algorithm>
using namespace std;
string transformer_majuscules(string s) {
   auto loc = locale::classic();
   for_each(begin(s), end(s), [&loc](char &c) {
      c = toupper(c, loc);
   });
   return s;
}
 
#include <string>
#include <locale>
#include <algorithm>
using namespace std;
string transformer_majuscules(string s) {
   auto loc = locale::classic();
   transform(begin(s), end(s), begin(s), [&loc](char c) {
      return toupper(c,loc);
   });
   return s;
}

C++ 14 enrichit les λ, en particulier du point de vue des captures, et permet d'écrire :

Avec std::for_each() Avec std::transform() 
#include <string>
#include <locale>
#include <algorithm>
using namespace std;
string transformer_majuscules(string s) {
   for_each(begin(s), end(s), [loc = locale::classic()](char &c) {
      c = toupper(c, loc);
   });
   return s;
}
 
#include <string>
#include <locale>
#include <algorithm>
using namespace std;
string transformer_majuscules(string s) {
   transform(begin(s), end(s), begin(s), [loc = locale::classic()](char c) {
      return toupper(c,loc);
   });
   return s;
}

Quelques comparatifs

Vous trouverez, à droite, quelques exemples d'implémentations de solutions à l'exercice EX00, de même qu'un programme de test invoquant une fonction générique capable de mesurer chacune des versions de la fonction de transformation de texte en majuscules.

Les fonctions vont comme suit :

Le code suit :

#include <algorithm>
#include <iostream>
#include <chrono>
#include <string>
#include <locale>
using namespace std;
using namespace std::chrono;

string transformer_majusculesA(string originale) {
   string resultat;
   for (string::size_type i = 0; i < originale.size(); i++) {
      char c;
      c = toupper(originale[i], locale::classic());
      resultat = resultat + c;
   }
   return resultat;
}
string transformer_majusculesB(const string &originale) {
   string resultat;
   auto loc = locale::classic();
   for (string::size_type i = 0; i < originale.size(); ++i)
      resultat += toupper(originale[i], loc);
   return resultat;
}
string transformer_majusculesC(const string & originale) {
   string resultat(originale.size(), ' ');
   auto loc = locale::classic();
   for (string::size_type i = 0; i < originale.size(); ++i)
      resultat[i] = toupper(originale[i], loc);
   return resultat;
}
string transformer_majusculesD(string s) {
   auto loc = locale::classic();
   for (string::size_type i = 0; i < s.size(); ++i)
      s[i] = toupper(s[i], loc);
   return s;
}
string transformer_majusculesE(string s) {
   struct Majuscules {
      const locale &loc;
      Majuscules(const locale &loc = locale::classic())
         : loc{loc}
      {
      }
      void operator()(char &c) const {
         c = toupper(c, loc);
      }
   };
   for_each(begin(s), end(s), Majuscules{});
   return s;
}
string transformer_majusculesF(string s) {
   auto loc = locale::classic();
   for_each(begin(s), end(s), [&](char &c) {
      c = toupper(c, loc);
   });
   return s;
}
string transformer_majusculesG(string s) {
   struct Majuscules {
      const locale &loc;
      Majuscules(const locale &loc = locale::classic())
         : loc{loc}
      {
      }
      char operator()(char c) const {
         return toupper(c, loc);
      }
   };
   transform(begin(s), end(s), begin(s), Majuscules{});
   return s;
}
string transformer_majusculesH(string s) {
   auto loc = locale::classic();
   transform(begin(s), end(s), begin(s), [&](char c) {
      return toupper(c, loc);
   });
   return s;
}
string transformer_majusculesI(string s) {
   auto loc = locale::classic();
   for(auto & c : s)
      c = toupper(c, loc);
   return s;
}
template <class F>
   void tester(F oper, const string &nom) {
      const int TAILLE = 50'000'000;
      string texte(TAILLE, 'a');
      string resultat;
      auto avant = system_clock::now();
      resultat = oper(texte);
      auto apres = system_clock::now();
      cout << nom << ", " << TAILLE << " caracteres : "
           << duration_cast<milliseconds>(apres - avant).count()
           << " ms." << endl;
   }
int main() {
   // tester(transformer_majusculesA, "Version originale et follement lente");
   tester(transformer_majusculesB, "Version du solutionnaire");
   tester(transformer_majusculesC, "Version du solutionnaire (preallocation)");
   tester(transformer_majusculesD, "Version du solutionnaire (copie)");
   tester(transformer_majusculesE, "Version avec std::for_each() et foncteur");
   tester(transformer_majusculesF, "Version avec std::for_each() et lambda");
   tester(transformer_majusculesG, "Version avec std::transform() et foncteur");
   tester(transformer_majusculesH, "Version avec std::transform() et lambda");
   tester(transformer_majusculesI, "Version avec for sur intervalle");
}

Les résultats de l'exécution de ce programme sur ce compilateur en ligne vont comme suit :

Version du solutionnaire, 50000000 caracteres : 2498 ms.
Version du solutionnaire (preallocation), 50000000 caracteres : 1979 ms.
Version du solutionnaire (copie), 50000000 caracteres : 1787 ms.
Version avec std::for_each() et foncteur, 50000000 caracteres : 1789 ms.
Version avec std::for_each() et lambda, 50000000 caracteres : 1826 ms.
Version avec std::transform() et foncteur, 50000000 caracteres : 1495 ms.
Version avec std::transform() et lambda, 50000000 caracteres : 1777 ms.
Version avec for sur intervalle, 50000000 caracteres : 1753 ms.

Voilà pour les comparatifs.

Complément – Forcer l'allocation dynamique d'un Noeud

Examinez les deux extraits de programme proposés à droite. Comment faire en sorte que celui créant un Noeud par voie d'allocation dynamique soit légal, tout en s'assurant que celui alloué de manière automatique soit illégal?

On veut que ceci soit légalOn veut que ceci soit illégal
auto p = new Noeud{3};
Noeud n{3};

Le truc pour éviter qu'un objet puisse être alloué automatiquement, quel que soit son type, est somme toute simple, mais quelque peu contre-intuitif. En effet, il suffit de faire en sorte que son destructeur (oui, son destructeur!) soit privé. Bien que ceci semble suspect à première vue, il s'agit d'une démarche tout à fait raisonnable.

Tout d'abord, sur le plan des modifications de base à la classe Noeud, nous n'avons que peu de choses à faire, soit expliciter un destructeur et le qualifier « privé ».

class Noeud {
   Noeud *succ = nullptr;
   int val;
public:
   Noeud(int val) : val{ val } {
   }
   Noeud(const Noeud &n) : val{ n.val } {
   }
private: // <--
   ~Noeud() = default; // <--
};

La question qui vient naturellement à l'esprit à ce stade est de savoir pourquoi ceci bloquerait la déclaration de variables automatiques de type Noeud. Pour connaître la réponse, examinez le code à droite; la définition de la variable n est en soi correcte, mais l'appel du destructeur de n est alors fait implicitement à la fin de sa portée... Or cet appel ne peut être réalisé, la méthode étant privée!

On constatera ensuite que ce vers quoi pointe p est alloué dynamiquement, ce qui se fait sans problème; à la fin de main(), le pointeur est détruit, ce qui est tout à fait légal. Évidemment, appeler delete p ne compilerait pas, donc notre programme fuit. Clairement, nous ne pouvons nous arrêter là.

int main() {
   auto p = new Noeud{3};
   // Noeud n{3}; // ne compilerait pas, car...
} // ...appel implicite à n.~Noeud(), qui est inacessible!

Détruire un objet dont le destructeur est privé

Examinons trois manières connexes de détruire un objet dont le destructeur est privé.

Approche « méthode »

Une stratégie toute simple pour pallier le fait que le destructeur soit privé est d'implémenter une méthode d'instance qui y ait accès et s'en serve. À droite, nous avons un exemple d'une telle méthode, nommée Noeud::meurs(). Puisque meurs() est une méthode de Noeud, elle a accès à Noeud::~Noeud() même si celui-ci est privé.

L'expression delete this peut faire sursauter mais elle est tout à fait légale. Une méthode d'instance est en fait une fonction globale à laquelle est passée implicitement un paramètre supplémentaire, this. Après l'expression delete this, il n'est plus possible d'accéder aux membres d'instance de this, mais tout le reste (méthodes de classe, objets globaux, variables locales) demeure pleinement accessible et sans danger.

class Noeud {
   Noeud *succ = nullptr;
   int val;
public:
   Noeud(int val) : val{ val } {
   }
   Noeud(const Noeud &n) : val{ n.val } {
   }
   void meurs() const { // <--
      delete this;      // <--
   }
private:
   ~Noeud() = default;
};

Le programme principal serait alors tel que proposé à droite. La clé est de remplacer delete p; par p->meurs() et le tour est joué.

int main() {
   auto p = new Noeud{3};
   // ...
   p->meurs(); // urg!
}

Approche « fonction amie »

Si écrire delete this vous stresse (et je comprendrai si c'est le cas, même si c'est complètement irrationnel ), une alternative serait de demander à un ami de Noeud de détruire les instances de Noeud.

Ici, Noeud détermine que la fonction globale meurs(const Noeud*) est son amie. L'amitié donne à cette fonction un droit d'accès sur les membres protégés et privés d'un Noeud, ce qui inclut Noeud::~Noeud() bien entendu.

class Noeud {
   Noeud *succ = nullptr;
   int val;
   Noeud(int val) : val{ val } {
   }
   Noeud(const Noeud &n) : val{ n.val } {
   }
   friend void meurs(const Noeud *p) { // <--
      delete p;
   }
private:
   ~Noeud() = default;
};

Le programme principal serait alors tel que proposé à droite. Nous sommes passés de p->meurs(), une forme de Hara Kiri, à meurs(p), une forme de trucidation.

int main() {
   auto p = new Noeud{3};
   // ...
   meurs(p); // urg!
}

Approche « pointeur intelligent »

Le problème des deux approches précédentes est que la finalisation est chaque fois manuelle. On voudrait pouvoir automatiser la finalisation d'un Noeud si tel est notre souhait.

Heureusement, unique_ptr accepte des stratégies de libération alternatives et n'est pas limité à delete ou à delete[].

class Noeud {
   Noeud *succ = nullptr;
   int val;
public:
   Noeud(int val) : val{ val } {
   }
   Noeud(const Noeud &n) : val{ n.val } {
   }
   friend void meurs(const Noeud *p) { // <--
      delete p;
   }
private:
   ~Noeud() = default;
};

Le programme principal proposé à droite montre comment combiner une fonction de nettoyage d'un Noeud et un unique_ptr pour en arriver à une finalisation déterministe et sécuritaire, tout en forçant le recours à l'instanciation dynamique.

#include <memory>
using std::unique_ptr;
int main() {
   unique_ptr<Noeud, void(*)(const Noeud*)> p(new Noeud{ 3 }, meurs);
   // ...
}

Valid XHTML 1.0 Transitional

CSS Valide !