Solutions – exercices du laboratoire L00

Ce qui suit propose des solutions possibles aux exercices du laboratoire L00, énoncé comme suit :

Pour pratiquer un peu, vous êtes invité(e)s à faire les exercices suivants. N'utilisez pas les algorithmes de <algorithm> pour arriver à vos fins (nous voulons nous pratiquer, après tout) :

Par la suite (ne trichez pas!), essayez de voir si ces algorithmes sont codés dans <algorithm> (respectivement sous les noms reverse(), count() et count_if(), tous dans l'espace nommé std), et comparez vos implémentations avec celles que vous y trouverez.

Pour réaliser les exercices proposés ici, il vous faudra utiliser entre autres les types std::vector et std::list, que vous trouverez dans les en-têtes standards <vector> et <list> respectivement.

Le type vector représente une sorte de tableau dynamique, très efficace pour accéder à un élément particulier ou pour ajouter ou enlever un élément à la fin, mais moins efficace pour insérer ou retirer des éléments à d'autres positions.

Le type list représente une liste doublement chaînée; les opérations sur elle sont en général plus lentes que sur vector, mais les opérations d'insertion et de suppression à un endroit autre qu'à la toute fin y sont beaucoup plus rapides.

Pour en savoir plus sur les conteneurs standards et sur les algorithmes standards, jetez un coup d'oeil à cet article.

Notez que les solutions ne sont pas uniques (d'autres solutions peuvent être correctes).

Solution possible pour inverser_elements()

Une implémentation correcte pour l'algorithme inverser_elements() décrit plus haut serait celui-ci :

Implémentation possible Variante équivalente Autre variante équivalente
#include <utility> // std::swap()
template <class It>
   void inverser_elements(It debut, It fin) {
      using std::swap;
      while(debut != fin) {
         --fin;
         if (debut != fin) {
            swap(*debut, *fin);
            ++debut;
         }
      }
   }
#include <utility> // std::swap()
template <class It>
   void inverser_elements(It debut, It fin) {
      using std::swap;
      for(; debut != fin; ++debut) {
         --fin;
         if (debut != fin)
            swap(*debut, *fin);
      }
   }
#include <utility> // std::swap()
template <class It>
   void inverser_elements(It debut, It fin) {
      using std::swap;
      for (; debut != fin; ++debut) {
         --fin;
         if (debut == fin) return;
         swap(*debut, *fin);
      }
   }

À noter :

Un programme de test simple pour cette fonction serait :

// inclusions et using...
int main() {
   int tab[] { 2,3,5,7,11 };
   vector<string> v { "bon!", "prof", "mon", "J'aime" };
   list<double> lst;
   //
   // test sur une séquence vide (ne doit pas planter)
   //
   cout << "Avant : ";
   for(double d : lst)
      cout << d << ' ';
   cout << endl;
   inverser_elements(begin(lst), end(lst));
   cout << "Apres : ";
   for(double d : lst)
      cout << d << ' ';
   cout << endl;
   //
   // insertion d'éléments dans la liste
   //
   for(auto n : tab)
      lst.push_back(n + 0.5);
   //
   // inverser les éléments d'un tableau de int (séquence de taille impaire)
   //
   cout << "Avant : ";
   for(int n : tab)
      cout << n << ' ';
   cout << endl;
   inverser_elements(tab + 0, tab + N);
   cout << "Apres : ";
   for(int n : tab)
      cout << n << ' ';
   cout << endl;
   //
   // inverser les éléments d'un vector<string> (séquence de taille paire)
   //
   cout << "Avant : ";
   for(const auto &s : v)
      cout << s << ' ';
   cout << endl;
   inverser_elements(begin(v), end(v));
   cout << "Apres : ";
   for(const auto &s : v)
      cout << s << ' ';
   cout << endl;
   //
   // inverser les éléments d'une list<double> (séquence de taille impaire)
   //
   cout << "Avant : ";
   for(double d : lst)
      cout << d << ' ';
   cout << endl;
   inverser_elements(begin(lst), end(lst));
   cout << "Apres : ";
   for(double d : lst)
      cout << d << ' ';
   cout << endl;
}

Solution possible pour compter_occurrences()

Une implémentation correcte pour l'algorithme compter_occurrences() décrit plus haut serait celui-ci :

template <class It, class T>
   int compter_occurrences(It debut, It fin, const T &val) {
      int n = 0;
      for (; debut != fin; ++debut)
         if (*debut == val)
            ++n;
      return n;
   }

À noter :

Un programme de test simple pour cette fonction serait :

// inclusions et using...
int main() {
   int tab[]= { 2,3,5,7,3,11 };
   enum { N = sizeof(tab) / sizeof(tab[0]) }; // la comprenez-vous? :)
   vector<int> v;
   //
   // test sur une séquence vide (ne doit pas planter)
   //
   cout << "Entier a rechercher? ";
   int n;
   if (!(cin >> n)) {
      cerr << "Ceci n'est pas un entier. Au revoir!" << endl;
      return -1;
   }
   cout << "Il y a " << compter_occurrences(begin(v), end(v), n)
        << " de la valeur " << n
        << " dans la sequence suivante : { ";
   for(int nb : v)
      cout << nb << ' ';
   cout << " }" << endl;
   //
   // insertion d'éléments dans le vecteur
   //
   for(int nb : tab)
      v.push_back(nb);
   cout << "Il y a " << compter_occurrences(begin(v), end(v), n)
        << " de la valeur " << n
        << " dans la sequence suivante : { ";
   for(int nb : v)
      cout << nb << ' ';
   cout << " }" << endl;
   //
   // tests sur un vector<string>
   //
   vector<string> w { "yo", "la", "genre", "style", "yo", "comme" };
   cout << "Mot a rechercher? ";
   string s;
   if (!(cin >> s)) {
      cerr << "Ceci n'est pas un mot valide. Au revoir!" << endl;
      return -1;
   }
   cout << "Il y a " << compter_occurrences(begin(w), end(w), s)
        << " de la valeur " << s
        << " dans la sequence suivante : { ";
   for(const auto &mot : w)
      cout << mot << ' ';
   cout << " }" << endl;
}

Solution possible pour compter_si()

Une implémentation correcte pour l'algorithme compter_si() décrit plus haut serait celui-ci :

template <class It, class Pred>
   int compter_si(It debut, It fin, Pred pred) {
      int n = 0;
      for (; debut != fin; ++debut)
         if (pred(*debut))
            ++n;
      return n;
   }

À noter :

Pour tester cette fonction, inspirez-vous du programme de test simple proposé pour compter_si() ci-dessus mais remplacez la valeur (n ou s, par exemple) par un prédicat tel que :

bool est_pair(int n) {
   return n % 2 == 0;
}
// ou encore (foncteur)
struct est_court {
   bool operator()(const string &s) const {
      return s.size() < 10;
   }
};
// ou encore (λ)
auto entre_1_incl_et_10_excl = [](int n) { return 1 <= n && n < 10; };

Avez-vous remarqué qu'il est possible d'exprimer compter() sous la forme d'un appel à compter_si()? En effet :

template <class It, class T>
   auto compter(It debut, It fin, const T &val) {
      return compter_si(debut, fin, [val](const T &autre) { return val == autre; });
   }

C'est un signe que quelque chose de profond et de fécond se cache ici...


Valid XHTML 1.0 Transitional

CSS Valide !