Solutions – exercices du laboratoire L00

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

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 :

#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 :

• Initialement, la fin est le premier élément juste après le dernier élément valide de la séquence. Il ne faut donc pas utiliser *fin avant d'avoir fait --fin au moins une fois
• L'algorithme doit fonctionner avec des séquences vides, donc dans le cas où initialement, debut == fin. Ici, l'algorithme quitterait sans faire la moindre permutation
• Nous avons limité les déplacements d'itérateurs aux opérations ++ et --. Cet algorithme est donc applicable à des itérateurs au moins bidirectionnels (il n'est pas utilisable sur une liste simplement chaînée, par exemple, mais il peut être utilisé sur une liste doublement chaînée ou sur un pointeur dans un tableau)
• À ce sujet, notez que ++debut (aller au prochain élément) n'est pas la même chose que debut += 1 (avancer de n positions, où n vaut 1)
• La raison des deux tests par itération est qu'il y a deux itérateurs à déplacer, une fois chacun, donc deux moments par itération où il est utile de vérifier l'état des itérateurs (si vous en négligez un, il est probable que l'algorithme ne se termine pas normalement)
• Le test debut!=fin est préférable à un test debut<fin puisque < suppose une relation d'ordre, une condition plus difficile à rencontrer que !=
• Le nombre de permutations (d'appels à std::swap()) est proportionnel à la moitié du nombre d'éléments dans la séquence. C'est donc un algorithme de complexité linéaire (complexité $O(\frac{1}{2}n)$)

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 :

• L'algorithme doit fonctionner avec des séquences vides, donc dans le cas où initialement, debut == fin. Ici, l'algorithme retournerait 0
• Nous avons limité les déplacements d'itérateurs aux opérations ++. Cet algorithme est donc applicable à des itérateurs au moins unidirectionnels (il est utilisable sur une liste simplement chaînée, par exemple)
• À ce sujet, notez que ++debut (aller au prochain élément) n'est pas la même chose que debut += 1 (avancer de n positions, où n vaut 1)
• Le test debut != fin est préférable à un test debut < fin puisque < suppose une relation d'ordre, une condition plus difficile à rencontrer que !=
• Le type int pour le compteur n et la valeur retournée par la fonction est inapproprié, mais choisir le bon type demande des connaissances qui ne sont pas supposées chez vous pour le moment
• Le nombre d'appels à operator== sur un élément pointé par It et un T est proportionnel au nombre d'éléments dans la séquence. C'est donc un algorithme de complexité linéaire (complexité $O(n)$)

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 :

• L'algorithme doit fonctionner avec des séquences vides, donc dans le cas où initialement, debut == fin. Ici, l'algorithme retournerait 0
• Nous avons limité les déplacements d'itérateurs aux opérations ++. Cet algorithme est donc applicable à des itérateurs au moins unidirectionnels (il est utilisable sur une liste simplement chaînée, par exemple)
• À ce sujet, notez que ++debut (aller au prochain élément) n'est pas la même chose que debut += 1 (avancer de n positions, où n vaut 1)
• Le test debut != fin est préférable à un test debut < fin puisque < suppose une relation d'ordre, une condition plus difficile à rencontrer que !=
• Le type int pour le compteur n et la valeur retournée par la fonction est inapproprié, mais choisir le bon type demande des connaissances qui ne sont pas supposées chez vous pour le moment
• Le nombre d'appels à pred() sur un élément pointé par It et un T est proportionnel au nombre d'éléments dans la séquence. C'est donc un algorithme de complexité linéaire (complexité $O(n)$ )

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; };

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; });
   }