Tableau dynamique – Implémentation collaborative et générique

Similaire à la stratégie collaborative et polymorphique, l'approche collaborative et générique pour mettre en place une politique de croissance pour un tableau dynamique comporte une intéressante combinaison de particularités.

Imaginons un type (que j'ai nommé Croisseur ici, mais entendons-nous qu'il s'agit d'un nom trouvé tard en fin de soirée et que vous êtes les bienvenu(e)s de me proposer mieux) capable d'exprimer certaines caractéristiques propres à un outil susceptible de prendre en charge une stratégie de croissance. Ici, Croisseur ne sera pas polymorphique et définira surtout certains types autour des concepts de valeur (T), de capacité (SzT) et de pointeur (PtrT), dans le but d'alléger la syntaxe de la méthode grow() de ses enfants.

Chaque type de Croisseur (par exemple CroisseurTypique) pourra déterminer une stratégie de croissance qui lui est propre. Toutefois, aucun polymorphisme ne sera requis; on exigera en retour une certaine conformité sur le plan de la signature de la méthode grow() des divers types de Croisseur.

Un tableau dynamique possèdera (par composition) un Croisseur, quel qu'il soit, et lui déléguera la responsabilité de prendre en charge sa propre croissance au besoin. Le Croisseur en question sera d'un type déterminé par les paramètres d'instanciation du template Tableau, ce qui fait que chaque instance de Tableau sera susceptible d'avoir sa propre stratégie de croissance. Chaque Tableau reposera sur un type de valeur (le type T) et sur un type de Croisseur, et cette combinaison entraînera à la fois la génération de l'instance elle-même et, au besoin, de son type.

Cette stratégie est très souple, mais moins que la stratégie collaborative polymorphique : les concepts de tableau et de politique de croissance sont découplés, réduits à leur plus simple expression (celle de service de croissance sans état), et la politique de croissance peut changer d'une instance de Tableau à l'autre, mais ne pourra pas changer pour un Tableau donné au cours de son existence. Puisque aucun pointeur vers un Croisseur n'est impliqué, le nombre d'indirections est fortement réduit et le code sera en général beaucoup plus rapide du fait qu'il sera sujet à une plus grande quantité d'optimisations de la part du compilateur.

#ifndef TABLEAU_H
#define TABLEAU_H
 
#include <algorithm>
#include <initializer_list>

class HorsBornes {};

template <class T, class SzT, class PtrT>
   struct Croisseur { // hum...
      using value_type = T;
      using size_type = SzT;
      using pointer = PtrT;
      using ptrref_t = pointer&;
   };

template <class T, class SzT = std::size_t, class PtrT = T*>
   struct CroisseurTypique : Croisseur<T, SzT, PtrT> {
      size_type grow(ptrref_t tab, size_type old_cap) const { // <-- ICI
         using std::copy;
         const size_type TAILLE_DEFAUT = 128;
         const float FACTEUR_CROISSANCE = 1.5f;
         const auto nouv_cap = static_cast<size_type>(old_cap? old_cap * FACTEUR_CROISSANCE : TAILLE_DEFAUT);
         pointer p = new value_type[nouv_cap];
         try {
            copy(tab, tab+old_cap, p);
            delete [] tab;
            tab = p;
         } catch(...) {
            delete [] p;
            throw;
         }
         return nouv_cap;
      }
   };

template <class T, class GrowthPol = CroisseurTypique<T, int>>
   class Tableau {
   public:
      using value_type = T;
      using size_type = int;
      using reference = value_type&;
      using const_reference = const value_type&;
      using pointer = value_type*;
      using const_pointer = const value_type*;
      using iterator = pointer;
      using const_iterator = const_pointer;
      using growth_pol_t = GrowthPol; // <-- ICI
   private:
      //
      //
      //
      growth_pol_t croisseur; // <-- ICI
      pointer elems;
      size_type nelems,
                cap;
   public:
      bool empty() const noexcept {
         return !size();
      }
      size_type size() const noexcept {
         return nelems;
      }
      size_type capacity() const noexcept {
         return cap;
      }
   private:
      bool full() const noexcept {
         return size() == capacity();
      }
   public:
      iterator begin() noexcept {
         return elems;
      }
      const_iterator begin() const noexcept {
         return elems;
      }
      const_iterator cbegin() const noexcept {
         return begin();
      }
      iterator end() noexcept {
         return begin() + size();
      }
      const_iterator end() const noexcept {
         return begin() + size();
      }
      const_iterator cend() const noexcept {
         return end();
      }
      //
      // constructeur par défaut
      //
      Tableau(growth_pol_t strategie = {}) : nelems{}, elems{}, cap{}, croisseur{strategie} { // <-- ICI  
      }
      //
      // constructeur paramétrique
      //
      Tableau(size_type n, const value_type &val, growth_pol_t strategie = {}) // <-- ICI
         : nelems{ n }, elems{ new value_type[n] }, cap{ n }, croisseur{ strategie }
      {
         try {
            std::fill(begin(), end(), val);
         } catch(...) {
            delete [] elems;
            throw;
         }
      }
      //
      // constructeur de copie
      //
      Tableau(const Tableau &autre) // <-- ICI
         : nelems{ autre.size() }, elems{ new value_type[autre.size()] }, cap{ autre.size() }, croisseur{ autre.croisseur }
      {
         try {
            std::copy(autre.begin(), autre.end(), begin());
         } catch(...) {
            delete [] elems;
            throw;
         }
      }
      //
      // constructeur par liste d'initialisation
      //
      Tableau(std::initializer_list<value_type> src, growth_pol_t strategie = {}) // <-- ICI
         : nelems{ src.size() }, cap{ src.size() }, elems{ new value_type[src.size()] }, croisseur{ strategie }
      {
         try {
            std::copy(src.begin(), src.end(), begin());
         } catch(...) {
            delete [] elems;
            throw;
         }
      }
      //
      // constructeur de séquence
      //
      template <class It>
         Tableau(It debut, It fin, growth_pol_t strategie = {}) // <-- ICI
            : nelems{ std::distance(debut, fin) }, croisseur{ strategie }
         {
            cap = size();
            elems = new value_type[capacity()];
            try {
               std::copy(debut, fin, begin());
            } catch(...) {
               delete [] elems;
               throw;
            }
         }
      //
      // constructeur de conversion
      //
      template <class U>
         Tableau(const Tableau<U> &autre) // <-- ICI
            : nelems{ autre.size() }, elems{ new value_type[autre.size()] }, cap{ autre.size() }, croisseur{} // hum... Votre avis?
         {
            try {
               std::copy(autre.begin(), autre.end(), begin());
            } catch(...) {
               delete [] elems;
               throw;
            }
         }
      //
      // constructeur de mouvement
      //
      Tableau(Tableau &&autre) { // <-- ICI
         elems = std::move(autre.elems);
         nelems = std::move(autre.nelems);
         cap = std::move(autre.cap);
         croisseur = std::move(autre.croisseur);
         tab.elems = {};
         tab.nelems = {};
         tab.cap = {};
         tab.croisseur = {};
      }
      ~Tableau() {
         delete [] elems;
      }
      void swap(Tableau &autre) {
         using std::swap;
         swap(elems, autre.elems);
         swap(nelems, autre.nelems);
         swap(cap, autre.cap);
         swap(croisseur, autre.croisseur);
      }
      //
      // affectation
      //
      Tableau& operator=(const Tableau &autre) {
         Tableau{ autre }.swap(*this);
         return *this;
      }
      //
      // affectation covariante
      //
      template <class U>
         Tableau& operator=(const Tableau<U> &autre) {
            Tableau{ autre }.swap(*this);
            return *this;
         }
      //
      // affectation par mouvement
      //
      Tableau& operator=(Tableau &&autre) {
         delete [] elems;
         elems = std::move(autre.elems);
         nelems = std::move(autre.nelems);
         cap = std::move(autre.cap);
         croisseur = std::move(autre.croisseur);
         autre.elems = {};
         autre.nelems = {};
         autre.cap = {};
         autre.croisseur = {};
         return *this;
      }
   private: // <-- ICI
      //
      //
      //
      void grow() {
         cap = croisseur.grow(elems, capacity());
      }
   public:
      void push_back(const_reference val) {
         if (full())
            grow();
         elems[size()] = val;
         ++nelems;
      }
      value_type at(size_type n) const {
         if (size() < n) throw HorsBornes{};
         return elems[n];
      }
      reference at(size_type n) {
         if (size() < n) throw HorsBornes{};
         return elems[n];
      }
      value_type operator[](size_type n) const {
         return elems[n];
      }
      reference operator[](size_type n) noexcept {
         return elems[n];
      }
      bool operator==(const Tableau &autre) const {
         return size() == autre.size() &&
                std::equal(begin(), end(), autre.begin());
      }
      bool operator!=(const Tableau &autre) const {
         return !(*this == autre);
      }
   };
 
#endif

Dans cet exemple, si CroisseurTypique::CroisseurTypique() lève une exception, nous avons une fuite. Pourquoi? Et comment peut-on (simplement) résoudre ce problème?

Que fera-t-on si un programme utilise deux types Tableau<T,P> et Tableau<T,Q>, donc avec les mêmes types de valeurs mais des politiques de croissance différentes? Pourra-t-on les comparer entre eux? Copier l'un dans l'autre? Réfléchissez-y, ça vaut la peine...

Un programme de test suit. Ce programme ajoute N éléments au tableau, provoquant au passsage à plus d'une reprise l'activation de la stratégie de croissance, puis affiche les éléments sur la sortie standard.

#include "Tableau.h"
#include <iostream>
#include <algorithm>
#include <iterator>
int main() {
   using namespace std;
   using value_type = Tableau<int>::value_type;
   enum { N = 30 };
   Tableau<int> tab;
   for (int i = 0; i < N; ++i)
      tab.push_back(i);
   copy(begin(tab), end(tab), ostream_iterator<value_type>{cout, " "});
   cout << endl;
}

Que pensez-vous cette solution?

Approches alternatives

Remarquez que le Croisseur utilisé ici est sans états (Stateless). Il peut donc être instancié et détruit au besoin, sans devoir retenir des états intermédiaires d'une utilisation à l'autre. Si tel est le contrat d'un Croisseur, alors il est possible d'adapter le design ci-dessus d'au moins deux manières :

En remplaçant l'attribut de type growth_pol_t par une variable locale de ce type, à même la méthode Tableau<T>::grow(). Cette technique a été suggérée par Maxime Turmel, de la cohorte 10 du DDJV.

Ce faisant, le growth_pol_t n'occupera plus d'espace dans l'instance de Tableau<T>.

//
// growth_pol_t croisseur; // <-- supprimer ceci
//
// ... puis exprimer grow() comme ceci:
//
void grow() {
   growth_pol_t croisseur;
   cap = croisseur.grow(elems, capacity());
}

En remplaçant la méthode d'instance du growth_pol_t par une méthode de classe. On aurait donc désormais une méthode qui serait static mais qui ne serait plus const.

On ferait ensuite disparaître l'attribut de type growth_pol_t, et on utiliserait le service grow() du growth_pol_t dans Tableau<T>::grow() à travers sa classe plutôt qu'à travers une instance.

//
// modifier la signature de la méthode grow() du Croisseur pour un faire
// une méthode de classe plutôt qu'une méthode d'instance...
//
template <class T, class SzT = std::size_t, class PtrT = T*>
   struct CroisseurTypique : Croisseur<T, SzT, PtrT> {
      static size_type grow(ptrref_t tab, size_type old_cap) { // <-- ICI
         // ...
      }
   };
//
// growth_pol_t croisseur; // <-- supprimer ceci
//
// ... puis exprimer grow() comme ceci:
//
void grow() {
   cap = growth_pol_t::croisseur.grow(elems, capacity());
}

Dans les deux cas, on aurait une économie d'espace, ce qui est une bonne chose, mais on imposerait du même coup une contrainte sur le design du croisseur.


Valid XHTML 1.0 Transitional

CSS Valide !