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. Une autre approche reposant sur l'héritage est l'implémentation hiérarchique (B).

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. C'est un signe que quelque chose cloche...

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. Voir https://wandbox.org/permlink/Cl2G1sLDKMILWMyi :

#ifndef TABLEAU_H
#define TABLEAU_H
 
#include <algorithm>
#include <iterator>
#include <utility>
#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 ...
   protected:
      pointer elems {};
      size_type nelems {},
                cap {};
   public:
      // empty(), size(), capacity(), full()
      // begin(), cbegin(), end(), cend()
      // constructeur par défaut
      // constructeur paramétrique
      // constructeur de copie
      // constructeur par liste d'initialisation
      // constructeur de séquence
      // constructeur de conversion
      // constructeur de mouvement
      virtual ~Tableau() {
         delete [] elems;
      }
      // swap(), affectation, affectation covariante
      // affectation par mouvement
   protected:
      virtual void grow() = 0;
   public:
      // push_back(), at(), operator[]
      // operator==, operator!=
   };

template <class T>
   struct TableauCool : Tableau<T> { // polymorphisme : héritage public
      using Tableau<T>::Tableau; // exposer les constructeurs du parent
      // le parent est générique, alors le compilateur ne sait pas ce que les
      // mots begin, end, elems, cap, etc. veulent dire avant que le code client
      // ne soit rencontré
      using typename Tableau<T>::value_type;
      using typename Tableau<T>::size_type;
      using Tableau<T>::begin;
      using Tableau<T>::end;
      using Tableau<T>::capacity;
      void grow() override {
         //
         // 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;
         }
      }
   private:
      using Tableau<T>::cap;
      using Tableau<T>::elems;
   };

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