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

Tout comme l'implémentation hiérarchique (A) d'une stratégie de croissance pour un tableau dynamique, la présente implémentation met en place une infrastructure polymorphique (ici : abstraite) dans une classe parent représentant le concept de tableau et ses données, puis exprime 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. Pour éviter le bris d'encapsulation résultant d'attributs protégés, nous utiliserons ici une interface de croissance différente de celle proposée à l'implémentation hiérarchique (A) au sens où le rôle de l'enfant est de déterminer la nouvelle capacité du parent, pas de gérer la croissance à proprement dit. Ceci permet d'isoler les attributs complètement en les gardant privés. J'ai préféré ne pas modifier l'interface de grow() mais enrichir la classe Tableau<T> d'un contrat (méthode abstraite) impliquant de calculer la nouvelle capacité (méthode compute_newcap()).

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 implémentée dans Tableau, mais dépend
//   d'un calcul abstrait de la nouvelle capacité
//
// Modifs:
// - compute_newcap() est abstraite et protégée
// - le destructeur est polymorphique
//

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;
   private: // <-- ICI
      pointer elems;
      size_type nelems,
                cap;
   public:
      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) } {
         tab.elems = {};
         tab.nelems = {};
         tab.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;
      }
   private: // <-- ICI
      //
      //
      //
      void grow() {
         const auto nouv_cap = compute_newcap();
         using std::copy;
         auto p = new value_type[nouv_cap];
         try {
            copy(begin(), end(), p);
            delete [] elems;
            elems = p;
            cap = nouv_cap;
         } catch (...) {
            delete [] p;
            throw;
         }
      }
   protected: // <-- ICI
      //
      //
      //
      virtual size_type compute_newcap() const = 0;
   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);
      }
   };

template <class T>
   struct TableauCool : Tableau<T> {
      using Tableau<T>::Tableau;
      size_type compute_newcap() const override {
         const size_type TAILLE_DEFAUT = 128;
         const float FACTEUR_CROISSANCE = 1.5f;
         return capacity()? static_cast<size_type>(capacity() * FACTEUR_CROISSANCE) : TAILLE_DEFAUT;
      }
   };

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