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 j'accueille volontiers les suggestions plus inspirées) 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, 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. Voir https://wandbox.org/permlink/j8BoVwkENrQDo25b :
#ifndef TABLEAU_H
#define TABLEAU_H
#include <algorithm>
#include <iterator>
#include <utility>
#include <initializer_list>
#include <memory>
class HorsBornes {};
class IncapableDeCroitre{};
template <class T, class SzT>
struct Croisseur { // hum...
using value_type = T;
using size_type = SzT;
using pointer = T*;
virtual std::pair<pointer, size_type> grow(pointer, 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>
struct CroisseurTypique : Croisseur<T, SzT> {
using value_type = typename Croisseur<T, SzT>::value_type;
using size_type = typename Croisseur<T, SzT>::size_type;
using pointer = typename Croisseur<T, SzT>::pointer;
std::pair<pointer, size_type> grow(pointer old_p, size_type old_cap) const override {
using std::copy;
using std::pair;
const size_type TAILLE_DEFAUT = 16;
const float FACTEUR_CROISSANCE = 1.5f;
const auto nouv_cap = static_cast<size_type>(old_cap? old_cap * FACTEUR_CROISSANCE : TAILLE_DEFAUT);
auto p = new value_type[nouv_cap];
try {
copy(old_p, old_p+old_cap, p);
} catch(...) {
delete [] p;
throw;
}
return pair{ p, nouv_cap };
}
CroisseurTypique* cloner() const override {
return new CroisseurTypique{ *this };
}
CroisseurTypique() = default;
protected:
CroisseurTypique(const CroisseurTypique&) = default;
};
template <class T>
class Tableau {
public:
// using ...
using growth_pol_t = Croisseur<value_type,size_type>;
private:
std::unique_ptr<growth_pol_t> croisseur;
pointer elems {};
size_type nelems {},
cap {};
public:
// empty(), size(), capacity()
private:
// full()
auto clone_growth_strategy() const {
using std::unique_ptr;
return croisseur ? unique_ptr<growth_pol_t>{ croisseur->cloner() } : unique_ptr<growth_pol_t>{};
}
public:
// begin(), cbegin(), end(), cend()
// constructeur par défaut
Tableau(std::unique_ptr<growth_pol_t> strategie) : 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() } {
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 (pourrait bénificier de enable_if ou
// des concepts de C++ 20)
//
template <class It>
Tableau(It debut, It fin, std::unique_ptr<growth_pol_t> strategie = {})
: 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)
: nelems{ autre.size() }, elems{ new value_type[autre.size()] }, cap{ autre.size() } {
try {
croisseur = autre.clone_growth_strategy();
std::copy(autre.begin(), autre.end(), begin());
} catch(...) {
delete [] elems;
throw;
}
}
//
// constructeur de mouvement
//
Tableau(Tableau &&autre) noexcept
: elems { std::exchange(autre.elems, nullptr) },
nelems { std::exchange(autre.nelems, 0) },
cap { std::exchange(autre.cap, 0) },
croisseur { std::move(autre.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);
}
// swap(), affectation, affectation covariante
//
// affectation par mouvement
//
private:
void grow() {
if (!croisseur) throw IncapableDeCroitre{};
auto [nouv_p,nouv_cap] = croisseur->grow(elems, capacity());
delete [] elems;
elems = nouv_p;
cap = nouv_cap;
}
public:
// push_back(), at(), operator[]
// operator==, operator!=
};
#endifUn 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 pourraient être envisagés dans ce cas-ci.
#include "Tableau.h"
#include <iostream>
int main() {
using namespace std;
enum { N = 1'000 };
Tableau<int> tab{ make_unique<CroisseurTypique<int>>() };
for (int i = 0; i < N; ++i)
tab.push_back(i);
for(auto n : tab) cout << n << ' ';
cout << endl;
}Que pensez-vous cette solution?
