Tableau dynamique et contrôle de la croissance – Quelques options

Implémenter un tableau dynamique est un exercice intéressant (bien qu'arriver à la hauteur de std::vector soit plus subtil qu'il n'y paraisse à première vue). L'un des aspects intéressants est le contrôle du taux de croissance de la capacité du tableau lorsque l'on tente d'insérer un élément dans un tableau déjà plein; il est bien sûr possible de le placer sous le contrôle du code client en exposant un mécanisme tel que reserve(), le comportement par défaut lors d'un push_back() ou d'un emplace_back() demeure typiquement sous le contrôle de l'implémentation.

Comment pourrions-nous donner au code client le contrôle de ce comportement?

Il existe plusieurs approches pour y arriver, certaines fort discutables, d'autres intéressantes, et certaines un peu trop exotiques pour être véritablement utiles mais suffisamment différentes des usages pour stimuler l'imagination.

Cas de base – Un tableau dynamique « vanille »

Nous supposerons un cas de base « vanille » implémentant une seule stratégie de croissance. Ce cas sera notre cas « par défaut » (notre Baseline, comme disent les anglophones), et servira de comparatif pour les autres.

Notez que dans les autres exemples, nous ne répéterons pas le code entier, nous limitant à ce qui diffère du cas « vanille », ceci dans une optique d'économie.

Voir TabDyn--Vanille.html pour une implémentation détaillée.

Approche simple : le copier / coller

Je ne l'ai pas exprimé explicitement, mais une solution à ce problème est de copier / coller le code de la classe modélisant un tableau dynamique, et de changer d'une version à l'autre les mécanismes implémentant la stratégie de croissance.

Cette approche fonctionne; elle n'est toutefois recommandable que dans les cas les plus simples, car elle complique l'entretien de manière importante. En effet, le risque de trouver un bogue (qu'il faut alors corriger dans plusieurs classes distinctes), ou encore de souhaiter ajouter ou modifier une fonctionnalité (ce qu'il faut refaire dans chaque classe) est grand, et propager des modifications dans une vaste gamme de fichiers accroît les risques d'erreurs, et de divergence de comportement.

Exprimé autrement : vous ne voulez probablement pas faire cela.

Implémentations hiérarchiques « classiques »

Sur la base de la littérature « classique » de la POO, on serait tentés de se dire que pour spécialiser un comportement, la voie royale serait de passer par une combinaison héritage + polymorphisme. Il est en effet possible d'y arriver.

Voir TabDyn--Hierarchique-A.html et TabDyn--Hierarchique-B.html pour une implémentation détaillée de deux approches :

• L'une (TabDyn--Hierarchique-A.html) donne aux classes dérivées un accès direct aux états du parent, par exposition d'attributs protégés, et fait implémenter grow() par chacun des enfants. Cela fonctionne, mais les états protégés tendent à compliquer sérieusement l'entretien du code, et il est préférable de n'avoir recours à ce stratagème qu'en situation contrôlée
• L'autre (TabDyn--Hierarchique-B.html) spécialise le calcul de la nouvelle capacité chez les enfants, et implémente la stratégie de croissance dans le parent de manière générale (autrement dit, grow() est implémentée par le parent, mais utilise une fonction de l'enfant pour déterminer la capacité à utiliser)

Notez que pour profiter de ces solutions dans le code client, les deux principales options sont :

#include "Tableau.h"
#include <iostream>
int main() {
   using namespace std;
   enum { N = 1'000 };
   TableauCool<int> tab;
   for (int i = 0; i < N; ++i)
      tab.push_back(i);
   for(auto n : tab) cout << n << ' ';
   cout << endl;
}

#include "Tableau.h"
#include <iostream>

void Afficher(const Tableau<T> &tab) {//
   for(auto n : tab) cout << n << ' ';
   cout << endl;
}
int main() {
   using namespace std;
   enum { N = 1'000 };
   TableauCool<int> tab;
   for (int i = 0; i < N; ++i)
      tab.push_back(i);
   Afficher(tab);
}

Ceci diverge un peu des usages, du moins en C++, où un tableau sera habituellement une classe concrète, utilisée en tant qu'elle-même. Notez aussi qu'il y a sans doute un questionnement qui demande à être fait, à savoir si créer une classe enfant pour spécialiser un comportement sur une trentaine ou à peu près est une approche adéquate.

Implémentations collaboratives

Si nous en arrivons au constat que dériver d'une classe parent pour ne spécialiser qu'un seul de ses comportements semble boiteux, alors il devient intéressant de réfléchir à d'autres stratégies. Une famille de stratégies envisageables est celle mettant en place une relation de collaboration entre deux entités, soit le tableau dynamique et un tiers responsable de gérer sa stratégie de croissance. Autrement dit, passer de l'héritage à la composition.

Il y a plusieurs avantages à ce virage : réduire le couplage (l'héritage – public, si on parle de polymorphisme dynamique – est une relation à plus fort couplage que la composition), ne garder qu'un seul type de tableau (quoiqu'il y ait des subtilités en ce sens dans l'approche collaborative générique), une architecture moins complexe à entretenir, etc. Il y a aussi des inconvénients, évidemment.

Voir TabDyn--Collaboratif-Polymorphique.html, TabDyn--Collaboratif-Generique.html et TabDyn--Collaboratif-function.html pour trois variantes distinctes de cette pratique.

Approche collaborative polymorphique

Dans TabDyn--Collaboratif-Polymorphique.html, le tableau dynamique entrepose un pointeur sur une abstraction capable de gérer une partie de sa croissance. J'ai utilisé une fonction prenant en paramètre un pointeur avant croissance et une capacité avant croissance, et retournant une paire contenant un pointeur après croissance et une capacité après croissance; c'est une signature de fonction discutable, mais qui nous suffira.

Plus : cette approche est très souple, permettant par exemple de changer dynamiquement de stratégie de croissance pendant la vie d'une instance de tableau dynamique

Moins : cette approche comporte quelques inconvénients. Elle complique la gestion des ressources du tableau (du moins s'il est responsable de la durée de vie de son gestionnaire de croissance). Elle impacte la signature de plusieurs fonctions, en particulier celle des les constructeurs, et pose la question de la duplication du gestionnaire de croissance lors de la duplication du tableau (dupliquer un objet polymorphique requiert du clonage). Il faut gérer le cas où le pointeur sur le gestionnaire de croissance est nul. Enfin, entreposer un pointeur sur le gestionnaire de croissance dans le tableau en accroît la taille

Approche collaborative générique

Dans TabDyn--Collaboratif-Generique.html, le type du tableau dynamique comprend le type d'un tiers capable de gérer une partie de sa croissance (autrement dit, on passe de Tableau<T> à Tableau<T,G> où G est une stratégie de croissance); un type convenable par défaut est suppléé à même la signature du tableau, mais ce type peut être remplacé par le code client en fonction de ses besoins. J'ai ici encore utilisé une fonction prenant en paramètre un pointeur avant croissance et une capacité avant croissance, et retournant une paire contenant un pointeur après croissance et une capacité après croissance; c'est une signature de fonction discutable, mais qui nous suffira.

Plus : cette approche simplifie beaucoup la gestion des ressources par le tableau, la stratégie de croissance faisant partie de celui-ci.

Moins : la stratégie de croissance d'un tableau est fixée à même son type, et ne peut pas être modifiée au cours de sa vie.

Approche collaborative par délégué

Dans TabDyn--Collaboratif-function.html, nous avons un hybride à faible couplage. Le tableau accepte en paramètre un objet pouvant être utilisé comme une fonction prenant en paramètre un pointeur avant croissance et une capacité avant croissance, et retournant une paire contenant un pointeur après croissance et une capacité après croissance (c'est une signature de fonction discutable, mais qui nous suffira), et entrepose cet objet dans un std::function de signature appropriée.

Plus : cette approche simplifie beaucoup la gestion des ressources par le tableau, la durée de vie de la stratégie de croissance étant sous la gouverne du délégué. Le couplage est très faible. Il est possible de changer dynamiquement de stratégie de croissance.

Moins : la stratégie de croissance est insérée par agrégation dans le tableau et occupe un peu d'espace. Chaque appel implique une (possible) indirection supplémentaire.

Implémentations plus exotiques

Examinons maintenant deux approches plus... exotiques.

Approche par injection de parent

Variante de l'approche collaborative générique, l'approche par injection de parent fait de la stratégie de croissance non pas un attribut du tableau dynamique, mais bien son parent. Ceci donne accès aux états protégés du parent (la stratégie de croissance) à l'enfant (le tableau dynamique), et permet d'appliquer l'optimisation EBCO (Empty Base Class Optimization) ce qui peut épargner de l'espace dans chaque instance.

Voir TabDyn--Injection-Parent.html pour plus de détails.

Les avantages et les inconvénients de cette approche sont semblables à ceux de l'approche collaborative générique : la stratégie de croissance s'inscrit dans le type du tableau, la gestion de la vie de la stratégie de croissance est implicite, etc.

Approche par Mixin

Une autre option est de combiner une interface et une implémentation en fonction des besoins du code client. Cette approche, nommée Mixin, peut être réalisée de plusieurs manières. L'une d'entre elles apparaît dans TabDyn--Mixin.html si vous souhaitez en examiner les détails.