Tableau dynamique – Implémentation hiérarchique (A)

Une implémentation possible et souvent proposée d'une stratégie de croissance pour un tableau dynamique est de mettre en place une infrastructure polymorphique (même abstraite, comme dans ce cas-ci) dans une classe parent représentant le concept de tableau et ses données, puis d'exprimer les stratégies possibles dans des classes dérivées en spécialisant la méthode de croissance.

La version proposée ici est épurée. L'encapsulation y est brisée par l'introduction d'attributs protégés, un cauchemar d'entretien, pour permettre aux enfants de l'abstraction parent d'implémenter la méthode grow() par accès direct à ces attributs (une alternative moins dommageable du point de vue de l'encapsulation est présentée ici).

La possibilité d'introduire autant d'enfants de Tableau que désiré accroît fortement la flexibilité en comparaison avec la stratégie implémentant grow() de manière locale. Il devient par contre moins agréable de manipuler un tableau dynamique, étant forcés de passer par une indirection (un pointeur) pour obtenir les précieux bénéfices du polymorphisme. Il est possible, en faisant fi de la généralité, de se passer ici de polymorphisme à l'externe et d'utiliser directement un enfant – l'invocation de grow() dans push_back() passera par this, un pointeur, et sera polymorphique de toute manière.

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

//
// - l'implémentation de grow() est abstraite dans Tableau, mais on pourrait en
//   avoir une qui soit là par défaut; ça ne change rien à notre exemple
//
// Modifs:
// - grow() est abstraite et protégée
// - le destructeur est polymorphique
//
// Problèmes pas gentils:
// - faut exposer elems de manière protégée ou repenser l'interface de
//   croissance sinon l'enfant ne pourra pas le modifier
// - faut exposer cap de manière protégée ou repenser l'interface
//   de croissance sinon l'enfant ne pourra pas le modifier
//
// Ici, je suis allé avec une version à attributs protégés
//

class HorsBornes {};
 
template <class T>
   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;
   protected: // <-- 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() noexcept : nelems{}, elems{}, cap{} {
      }
      //
      // constructeur paramétrique
      //
      Tableau(size_type n, const value_type &val) : nelems{ n }, elems{ new value_type[n] }, cap{ n } {
         try {
            std::fill(begin(), end(), val);
         } catch(...) {
            delete [] elems;
            throw;
         }
      }
      //
      // constructeur de copie
      //
      Tableau(const Tableau &autre) : nelems{ autre.size() }, elems{ new value_type[autre.size()] }, cap{ autre.size() } {
         try {
            std::copy(autre.begin(), autre.end(), begin());
         } catch(...) {
            delete [] elems;
            throw;
         }
      }
      //
      // constructeur par liste d'initialisation
      //
      Tableau(std::initializer_list<value_type> src) : nelems{ src.size() }, cap{ src.size() }, elems{ new value_type[src.size()] } {
         try {
            std::copy(src.begin(), src.end(), begin());
         } catch(...) {
            delete [] elems;
            throw;
         }
      }
      //
      // constructeur de séquence
      //
      template <class It>
         Tableau(It debut, It fin) : nelems{ std::distance(debut, fin) } {
            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) : nelems{ autre.size() }, elems{ new value_type[autre.size()] }, cap{ autre.size() } {
            try {
               std::copy(autre.begin(), autre.end(), begin());
            } catch(...) {
               delete [] elems;
               throw;
            }
         }
      //
      // constructeur de mouvement
      //
      Tableau(Tableau &&autre) : nelems{ std::move(autre.nelems) }, elems{ std::move(autre.elems) }, cap{ std::move(autre.cap) } {
         autre.elems = {};
         autre.nelems = {};
         autre.cap = {};
      }
      virtual ~Tableau() { // <-- ICI
         delete [] elems;
      }
      void swap(Tableau &autre) {
         using std::swap;
         swap(elems, autre.elems);
         swap(nelems, autre.nelems);
         swap(cap, autre.cap);
      }
      //
      // 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);
         autre.elems = {};
         autre.nelems = {};
         autre.cap = {};
         return *this;
      }
   protected: // <-- ICI
      //
      //
      //
      virtual void grow() = 0; // <-- ICI
   public:
      void push_back(const_reference val) {
         if (full())
            grow();
         elems[size()] = val;
         ++nelems;
      }
      const_reference 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];
      }
      const_reference 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);
      }
   };

template <class T>
   struct TableauCool : Tableau<T> {
      using Tableau<T>::Tableau;
      void grow() {
         //
         // Politique: facteur de croissance 1.5 de la capacité
         //
         const size_type TAILLE_DEFAUT = 128;
         const float FACTEUR_CROISSANCE = 1.5f;
         const auto nouv_cap = capacity()? static_cast<size_type>(capacity() * FACTEUR_CROISSANCE) : TAILLE_DEFAUT;
         auto p = new value_type[nouv_cap];
         try {
            std::copy(begin(), end(), p);
            delete [] elems;
            elems = p;
            cap = nouv_cap;
         } catch (...) {
            delete[] p;
            throw;
         }
      }
   };

#endif

Un programme de test suit. Ce programme ajoute N éléments au tableau (notez qu'on utilise l'enfant, à la fois pour obtenir les bénéfices de son algorithme de croissance et parce que son parent est abstrait), 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>

//
// Modifs: on utilise TableauCool<T> plutôt que Tableau<T>
//
int main() {
   using namespace std;
   enum { N = 30 };
   TableauCool<int> tab;
   using value_type = TableauCool<int>::value_type;
   for (int i = 0; i < N; ++i)
      tab.push_back(i);
   copy(begin(tab), end(tab), ostream_iterator<value_type>{cout, " "});
}

Que pensez-vous cette solution?


Valid XHTML 1.0 Transitional

CSS Valide !