Exercice – classe GenerateurId

Les explications pour cet exercice ont été données en classe. Deux versions suivent : une exposant l'interface au code client, et une autre sous forme pImpl.

Version avec interface exposée au code client

Programme principal (exemple) :

#include "Generateur.h"
#include <iostream>
using namespace std;
int main() {
   GenerateurNombres gen{ sorte_generateur::seq };
   cout << gen.prendre() << endl;
   cout << gen.prendre() << endl;
   cout << gen.prendre() << endl;
   cout << gen.prendre() << endl;
   auto nb = gen.prendre();
   gen.rendre(nb);
   cout << gen.prendre() << endl;
}

Interface (fichier Generateur.h) :

#ifndef GENERATEUR_H
#define GENERATEUR_H

#include <memory>

class banque_epuisee {};

struct IGenerateurNombres {
   using value_type = unsigned short;
   virtual value_type prendre() = 0;
   virtual void rendre(value_type) = 0;
   virtual ~IGenerateurNombres() = default;
};

enum class sorte_generateur : short {
   seq, recycl, alea
};

class sorte_inconnue{};

std::unique_ptr<IGenerateurNombres> creer_generateur(sorte_generateur);

class GenerateurNombres {
   std::unique_ptr<IGenerateurNombres> p;
public:
   using value_type = IGenerateurNombres::value_type;
   GenerateurNombres(sorte_generateur ze_sorte) : p{ creer_generateur(ze_sorte) } {
   }
   value_type prendre() {
      return p->prendre();
   }
   void rendre(value_type nb) {
      p->rendre(nb);
   }
};
#endif

Implémentation (fichier Generateurs.cpp) :

#include "Generateur.h"
#include <vector>
#include <random>
#include <algorithm>
#include <numeric>
#include <limits>
#include <memory>
using namespace std;

class GenSequentiel : public IGenerateurNombres {
   value_type cur{};
   value_type prendre() override {
      if (cur == numeric_limits<value_type>::max()) throw banque_epuisee{};
      return cur++;
   }
   void rendre(value_type) override {
   }
};

class GenRecycleur : public IGenerateurNombres {
   value_type cur{};
   vector<value_type> banque;
   value_type prendre() override {
      if (!banque.empty()) {
         auto nb = banque.back();
         banque.pop_back();
         return nb;
      }
      if (cur == numeric_limits<value_type>::max()) throw banque_epuisee{};
      return cur++;
   }
   void rendre(value_type nb) override {
      banque.push_back(nb);
   }
};

// implémentation naïve :)
class GenAleatoire : public IGenerateurNombres {
   vector<value_type> disponibles;
   mt19937 prng{ random_device{}() };
public:
   GenAleatoire() : disponibles(numeric_limits<value_type>::max()) {
      iota(begin(disponibles), end(disponibles), 0);
      shuffle(begin(disponibles), end(disponibles), prng);
   }
   value_type prendre() override {
      if (disponibles.empty()) throw banque_epuisee{};
      auto nb = disponibles.back();
      disponibles.pop_back();
      return nb;
   }
   void rendre(value_type nb) override {
      disponibles.push_back(nb);
      shuffle(begin(disponibles), end(disponibles), prng);
   }
};

unique_ptr<IGenerateurNombres> creer_generateur(sorte_generateur ze_sorte) {
   switch (ze_sorte) {
   case sorte_generateur::seq:
      return make_unique<GenSequentiel>();
   case sorte_generateur::recycl:
      return make_unique<GenRecycleur>();
   case sorte_generateur::alea:
      return make_unique<GenAleatoire>();
   }
   throw sorte_inconnue{};
}

auto GenerateurNombres::prendre() -> value_type {
   return p->prendre();
}

void GenerateurNombres::rendre(value_type nb) {
   p->rendre(nb);
}

Version avec pImpl

Programme principal (Exemple) :

#include "Generateur.h"
#include <iostream>
using namespace std;
int main() {
   GenerateurNombres gen{ sorte_generateur::seq };
   cout << gen.prendre() << endl;
   cout << gen.prendre() << endl;
   cout << gen.prendre() << endl;
   cout << gen.prendre() << endl;
   auto nb = gen.prendre();
   gen.rendre(nb);
   cout << gen.prendre() << endl;
}

Interface (fichier Generateur.h) :

#ifndef GENERATEUR_H
#define GENERATEUR_H

#include <memory>

class banque_epuisee {};

enum class sorte_generateur : short {
   seq, recycl, alea
};

class sorte_inconnue{};

class GenerateurNombres {
public:
   struct Impl;
private:
   std::unique_ptr<Impl> p;
public:
   using value_type = unsigned short;
   GenerateurNombres(sorte_generateur);
   ~GenerateurNombres();
   value_type prendre();
   void rendre(value_type);
};
#endif

Implémentation (fichier Generateurs.cpp) :

#include "Generateur.h"
#include <vector>
#include <random>
#include <algorithm>
#include <numeric>
#include <limits>
#include <memory>
using namespace std;


struct GenerateurNombres::Impl {
   using value_type = GenerateurNombres::value_type;
   virtual value_type prendre() = 0;
   virtual void rendre(value_type) = 0;
   virtual ~Impl() = default;
};

unique_ptr<GenerateurNombres::Impl> creer_generateur(sorte_generateur);


class GenSequentiel : public GenerateurNombres::Impl {
   value_type cur{};
   value_type prendre() override {
      if (cur == numeric_limits<value_type>::max()) throw banque_epuisee{};
      return cur++;
   }
   void rendre(value_type) override {
   }
};

class GenRecycleur : public GenerateurNombres::Impl {
   value_type cur{};
   vector<value_type> banque;
   value_type prendre() override {
      if (!banque.empty()) {
         auto nb = banque.back();
         banque.pop_back();
         return nb;
      }
      if (cur == numeric_limits<value_type>::max()) throw banque_epuisee{};
      return cur++;
   }
   void rendre(value_type nb) override {
      banque.push_back(nb);
   }
};

// implémentation naïve :)
class GenAleatoire : public GenerateurNombres::Impl {
   vector<value_type> disponibles;
   mt19937 prng{ random_device{}() };
public:
   GenAleatoire() : disponibles(numeric_limits<value_type>::max()) {
      iota(begin(disponibles), end(disponibles), 0);
      shuffle(begin(disponibles), end(disponibles), prng);
   }
   value_type prendre() override {
      if (disponibles.empty()) throw banque_epuisee{};
      auto nb = disponibles.back();
      disponibles.pop_back();
      return nb;
   }
   void rendre(value_type nb) override {
      disponibles.push_back(nb);
      shuffle(begin(disponibles), end(disponibles), prng);
   }
};

unique_ptr<GenerateurNombres::Impl> creer_generateur(sorte_generateur ze_sorte) {
   switch (ze_sorte) {
   case sorte_generateur::seq:
      return make_unique<GenSequentiel>();
   case sorte_generateur::recycl:
      return make_unique<GenRecycleur>();
   case sorte_generateur::alea:
      return make_unique<GenAleatoire>();
   }
   throw sorte_inconnue{};
}

GenerateurNombres::GenerateurNombres(sorte_generateur ze_sorte)
   : p{ creer_generateur(ze_sorte) }{
}

GenerateurNombres::~GenerateurNombres() = default;

auto GenerateurNombres::prendre() -> value_type {
   return p->prendre();
}

void GenerateurNombres::rendre(value_type nb) {
   p->rendre(nb);
}

Écrivez-moi si vous avez des questions!

Variations sur un thème – GenerateurAleatoire

On pourrait envisager des variantes sur le thème du type GenerateurAleatoire. Par exemple, ne brasser les nombres que lors d'une pige, et seulement s'il n'y a pas eu de brassage depuis la dernière remise :

// ...
class GenAleatoire : public GenerateurNombres::Impl {
   vector<value_type> disponibles;
   mt19937 prng{ random_device{}() };
   bool melange = false;
   void melanger() {
      shuffle(begin(disponibles), end(disponibles), prng);
      melange = true;
   }
   void melanger_si_requis() {
      if(!melange) melanger();
   }
public:
   GenAleatoire() : disponibles(numeric_limits<value_type>::max()) {
      iota(begin(disponibles), end(disponibles), 0);
      melanger();
   }
   value_type prendre() override {
      if (disponibles.empty()) throw banque_epuisee{};
      melanger_si_requis();
      auto nb = disponibles.back();
      disponibles.pop_back();
      return nb;
   }
   void rendre(value_type nb) override {
      disponibles.push_back(nb);
      melange = false;
   }
};
// ...

Ceci introduit des tests supplémentaires, et accroit la taille de GenAleatoire, mais peut être plus rapide selon les cas d'utilisation.

Une autre option serait de ne pas brasser du tout, et de piger un indice au hasard :

// ...
class GenAleatoire : public GenerateurNombres::Impl {
   vector<value_type> disponibles;
   mt19937 prng{ random_device{}() };
public:
   GenAleatoire() : disponibles(numeric_limits<value_type>::max()) {
      iota(begin(disponibles), end(disponibles), 0);
   }
   value_type prendre() override {
      if (disponibles.empty()) throw banque_epuisee{};
      auto n = uniform_int_distribution<int>(0,disponibles.size())(prng);
      auto pos = next(begin(), n);
      auto nb = *pos;
      disponibles.erase(pos);
      return nb;
   }
   void rendre(value_type nb) override {
      disponibles.push_back(nb);
   }
};
// ...

Ceci est un peu naïf cela dit, car la pige d'un nombre à une position aléatoire dans le vecteur a un coût linéaire.

Cependant, on peut prendre un truc dans la boîte à outils des gens du monde du jeu. Au lieu de supprimer à un point arbitraire dans le vecteur, on peut permuter l'élément avec le dernier du vecteur puis suivre d'un pop_back(), ce qui mène à un algorithme de complexité constante,  :

// ...
template <class T, class It>
   void erase_with_last_swap(vector<T> &v, It pos) {
      if(v.empty() || pos == end(v)) return;
      swap(*pos, *(prev(end(v))));
      v.pop_back();
   }
class GenAleatoire : public GenerateurNombres::Impl {
   vector<value_type> disponibles;
   mt19937 prng{ random_device{}() };
public:
   GenAleatoire() : disponibles(numeric_limits<value_type>::max()) {
      iota(begin(disponibles), end(disponibles), 0);
   }
   value_type prendre() override {
      if (disponibles.empty()) throw banque_epuisee{};
      auto n = uniform_int_distribution<int>(0,disponibles.size()-1)(prng);
      auto pos = next(begin(), n);
      auto nb = *pos;
      erase_with_last_swap(disponibles, pos);
      return nb;
   }
   void rendre(value_type nb) override {
      disponibles.push_back(nb);
   }
};
// ...

Ceci fonctionne dans notre cas car l'ordre relatif des éléments dans le vecteur nous importe peu.

Valid XHTML 1.0 Transitional

CSS Valide !