Tableau dynamique – Implémentation collaborative et polymorphique

Une approche possible pour mettre en place une politique de croissance pour un tableau dynamique est de procéder de manière collaborative.

Imaginons une abstraction (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 des règles de croissance pour un tiers et de se cloner (sujet intéressant en soi).

Un Croisseur définit certains types autour des concepts de valeur (T), de capacité (SzR) et de pointeur (PtrT), dans le but d'alléger la syntaxe de la méthode abstraite grow(). Chaque type de Croisseur (par exemple CroisseurTypique) pourra déterminer une stratégie de croissance qui lui est propre à partir de la même signature pour grow().

Un tableau dynamique possèdera (par agrégation) un lien indirect (un pointeur) vers un Croisseur, quel qu'il soit, et lui déléguera la responsabilité de prendre en charge sa propre croissance au besoin. Comme l'a fait remarquer Nicolas Lawson, de la cohorte 10 du DDJV, l'implémentation qui suit rend chaque Tableau<T> responsable de son Croisseur; si les instances de Tableau<T> peuvent partager un même Croisseur, alors le design de Tableau<T> sera différent (plus léger, mais dépendant d'un tiers pour gérer la vie des instances de Croisseur pour lui).

Cette stratégie est très souple : 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 même changer pour un tableau donné au cours de son existence. En retour, le pointeur sur un Croisseur peut être nul, ce qui implique une forme de validation, et toute invocation d'une service de croissance requiert une indirection supplémentaire.

#ifndef TABLEAU_H
#define TABLEAU_H

#include <algorithm>
#include <memory>
#include <initializer_list>

class HorsBornes {};
class IncapableDeCroitre{}; // <-- ICI

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&;
      // in: old capacity;
      // out: new capacity
      virtual size_type grow(ptrref_t, size_type) const = 0;
      virtual Croisseur* cloner() const = 0;
      virtual ~Croisseur() = default;
      Croisseur() = default;
   protected:
      Croisseur(const Croisseur&) = default;
   };

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 override {
         using std::copy;
         const size_type TAILLE_DEFAUT = 16;
         const float FACTEUR_CROISSANCE = 1.5f;
         const size_type nouv_cap = static_cast<size_type>(old_cap? old_cap * FACTEUR_CROISSANCE : TAILLE_DEFAUT);
         auto p = new value_type[nouv_cap];
         try {
            copy(tab, tab+old_cap, p);
            delete [] tab;
            tab = p;
         } catch(...) {
            delete [] p;
            throw;
         }
         return nouv_cap;
      }
      CroisseurTypique* cloner() const override {
         return new CroisseurTypique{ *this };
      }
      CroisseurTypique() = default;
   protected:
      CroisseurTypique(const CroisseurTypique&) = default;
   };

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;
      using growth_pol_t = Croisseur<value_type,size_type,pointer>; // <-- ICI
   private: // <-- ICI
      //
      //
      //
      std::unique_ptr<growth_pol_t> croisseur;
      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:
      std::unique_ptr<growth_pol_t> clone_growth_strategy() const { // <-- ICI
         return croisseur ? std::unique_ptr<growth_pol_t>{ croisseur->cloner() } : std::unique_ptr<growth_pol_t>{};
      }
      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(std::unique_ptr<growth_pol_t> strategie = {}) : nelems{}, elems{}, cap{}, croisseur{ std::move(strategie) } { // <-- ICI
      }
      //
      // constructeur paramétrique
      //
      Tableau(size_type n, const value_type &val, std::unique_ptr<growth_pol_t> strategie = {}) // <-- ICI
         : nelems{ n }, elems{ new value_type[n] }, cap{ n }, croisseur{ std::move(strategie) }
      {
         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() }, croisseur{} { // <-- ICI
         try {
            croisseur = autre.clone_growth_strategy();
            std::copy(autre.begin(), autre.end(), begin());
         } catch(...) {
            delete [] elems;
            throw;
         }
      }
      //
      // constructeur par liste d'initialisation
      //
      Tableau(std::initializer_list<value_type> src, std::unique_ptr<growth_pol_t> strategie = {}) // <-- ICI
         : nelems{ src.size() }, cap{ src.size() }, elems{ new value_type[src.size()] }, croisseur{ std::move(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, std::unique_ptr<growth_pol_t> strategie = {}) // <-- ICI
            : nelems{ std::distance(debut, fin) }, croisseur{ std::move(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{}
         {
            try {
               croisseur = autre.clone_growth_strategy();
               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 = {};
      }
      ~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); // <-- ICI
      }
      //
      // 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 = {};
         return *this;
      }
   private: // <-- ICI
      //
      //
      //
      void grow() {
         if (!croisseur) throw IncapableDeCroitre{};
         cap = croisseur->grow(elems, capacity());
      }
   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);
      }
   };
 
#endif

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.

Remarquez la création d'un tableau dynamique, fortement alourdie par le recours à l'instanciation d'un Croisseur approprié au besoin. Des outils pour assister les programmeurs et alléger la syntaxe sont possibles et devraient être envisagés dans ce cas-ci.

#include "Tableau.h"
#include <iostream>
#include <algorithm>
#include <iterator>
int main() {
   using namespace std;
   using size_type = Tableau<int>::size_type;
   using value_type = Tableau<int>::value_type;
   enum { N = 30 };
   Tableau<int> tab{ new CroisseurTypique<int, size_type> };
   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?


Valid XHTML 1.0 Transitional

CSS Valide !