Similaire à la stratégie collaborative et polymorphique, l'approche collaborative et générique pour mettre en place une politique de croissance pour un tableau dynamique comporte une intéressante combinaison de particularités.
Imaginons un type de « Croisseur » ici (nom discutable, mais il s'agit d'un nom trouvé tard en fin de soirée et les suggestions pour mieux le nommer sont les bienvenues) capable d'exprimer certaines caractéristiques propres à un outil susceptible de prendre en charge une stratégie de croissance. On voudra qu'un « Croisseur » ne soit pas polymorphique, mais définisse certains types autour des concepts de valeur (T) et de capacité (SzT), dans le but d'alléger la syntaxe de sa méthode grow().
Chaque type « Croisseur » (par exemple CroisseurTypique) pourra déterminer une stratégie de croissance qui lui est propre. Aucun polymorphisme ne sera requis; on exigera en retour une certaine conformité sur le plan de la signature de la méthode grow() des divers types de « Croisseurs ».
Un tableau dynamique possèdera (par composition) un « Croisseur », quel qu'il soit, et lui déléguera la responsabilité de prendre en charge sa propre croissance au besoin. Le « Croisseur » en question sera d'un type déterminé par les paramètres d'instanciation du template Tableau, ce qui fait que chaque instance de Tableau sera susceptible d'avoir sa propre stratégie de croissance. Chaque Tableau reposera sur un type de valeur (le type T) et sur un type de « Croisseur », et cette combinaison entraînera à la fois la génération de l'instance elle-même et, au besoin, de son type.
Cette stratégie est très souple, mais moins que la stratégie collaborative polymorphique : 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 changer d'une instance de Tableau à l'autre, mais ne pourra pas changer pour un Tableau donné au cours de son existence. Puisque aucun pointeur vers un « Croisseur » n'est impliqué, le nombre d'indirections est fortement réduit et le code sera en général beaucoup plus rapide du fait qu'il sera sujet à une plus grande quantité d'optimisations de la part du compilateur. Voir https://wandbox.org/permlink/L2GOX7wArMSMPteb :
#ifndef TABLEAU_H
#define TABLEAU_H
#include <algorithm>
#include <utility>
#include <initializer_list>
class HorsBornes {};
template <class T, class SzT = std::size_t>
struct CroisseurTypique {
using value_type = T;
using size_type = SzT;
using pointer = T*;
std::pair<pointer, size_type> grow(pointer old_p, size_type old_cap) const { // <-- ICI
using std::copy;
using std::pair;
const size_type TAILLE_DEFAUT = 128;
const float FACTEUR_CROISSANCE = 1.5f;
const auto nouv_cap = static_cast<size_type>(old_cap? old_cap * FACTEUR_CROISSANCE : TAILLE_DEFAUT);
pointer p = new value_type[nouv_cap];
try {
copy(old_p, old_p+old_cap, p);
} catch(...) {
delete [] p;
throw;
}
return pair{ p, nouv_cap };
}
};
template <class T, class GrowthPol = CroisseurTypique<T, int>>
class Tableau {
public:
// using ...
using growth_pol_t = GrowthPol;
private:
growth_pol_t croisseur;
pointer elems {};
size_type nelems {},
cap {};
public:
// empty(), size(), capacity(), full()
// begin(), cbegin(), end(), cend()
// constructeur par défaut
//
// constructeur paramétrique
//
Tableau(size_type n, const value_type &val, growth_pol_t strategie = {})
: nelems{ n }, elems{ new value_type[n] }, cap{ n }, croisseur{ 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{ autre.croisseur } {
try {
std::copy(autre.begin(), autre.end(), begin());
} catch(...) {
delete [] elems;
throw;
}
}
//
// constructeur par liste d'initialisation
//
Tableau(std::initializer_list<value_type> src, growth_pol_t strategie = {})
: nelems{ src.size() }, cap{ src.size() }, elems{ new value_type[src.size()] }, croisseur{ 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, growth_pol_t strategie = {})
: nelems{ std::distance(debut, fin) }, croisseur{ strategie } {
cap = size();
elems = new value_type[capacity()];
try {
std::copy(debut, fin, begin());
} catch(...) {
delete [] elems;
throw;
}
}
//
// constructeur de conversion (signature à réfléchir)
//
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)
: 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() {
auto [p,nouv_cap] = croisseur.grow(elems, capacity());
delete [] elems;
elems = p;
cap = nouv_cap;
}
public:
// push_back(), at(), operator[]
// operator==, operator!=
};
#endifDans cet exemple, si CroisseurTypique::CroisseurTypique() lève une exception, nous avons une fuite. Pourquoi? Et comment peut-on (simplement) résoudre ce problème?
Que fera-t-on si un programme utilise deux types Tableau<T,P> et Tableau<T,Q>, donc avec les mêmes types de valeurs mais des politiques de croissance différentes? Pourra-t-on les comparer entre eux? Copier l'un dans l'autre? Réfléchissez-y, ça vaut la peine...
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.
#include "Tableau.h"
#include <iostream>
int main() {
using namespace std;
enum { N = 1'000 };
Tableau<int> tab;
for (int i = 0; i < N; ++i)
tab.push_back(i);
for(auto n : tab) cout << n << ' ';
cout << endl;
}Que pensez-vous cette solution?
Remarquez que le « Croisseur » utilisé ici est sans états (Stateless). Il peut donc être instancié et détruit au besoin, sans devoir retenir des états intermédiaires d'une utilisation à l'autre. Si tel est le contrat d'un« Croisseur », alors il est possible d'adapter le design ci-dessus d'au moins deux manières :
En remplaçant l'attribut de type growth_pol_t par une variable locale de ce type, à même la méthode Tableau<T>::grow(). Cette technique a été suggérée par Maxime Turmel, de la cohorte 10 du DDJV. Ce faisant, le growth_pol_t n'occupera plus d'espace dans l'instance de Tableau<T>. Du fait que le « Croisseur » n'est utilisé que pour une seule expression, il est évidemment possible de ne l'instancier que pour ce court moment : |
|
En remplaçant la méthode d'instance du growth_pol_t par une méthode de classe. On aurait donc désormais une méthode qui serait static, mais qui ne serait (conséquemment) plus const. On ferait ensuite disparaître l'attribut de type growth_pol_t, et on utiliserait le service grow() du growth_pol_t dans Tableau<T>::grow() à travers sa classe plutôt qu'à travers une instance. |
|
Dans les deux cas, on aurait une économie d'espace, ce qui est une bonne chose, mais on changerait du même coup une contrainte sur le design du croisseur. C'est toutefois une piste par laquelle nous pouvons explorer des approches plus fécondes...
