Programmation générique appliquée

Comment utiliser sagement les surprenantes avenues ouvertes qui s'offrent à nous de par l'avènement de la programmation générique? La question intéresse beaucoup de gens (dont votre humble serviteur) et mène à des techniques poussées comme la métaprogrammation, la programmation par politique et les traits.

Ce que nous explorerons brièvement ici sont quelques subtilités techniques et philosophiques de la pratique de la programmation générique et de son application. Nous examinerons entre autres comment construire un type générique Tableau, représentant un tableau dynamique de valeurs d'un type générique.

Nous n'aurons pas l'ambition de faire compétition avec le type std::vector de la bibliothèque standard, mais bien celle d'explorer les ramifications de la pensée générique dans un contexte pédagogique mais crédible.

Considérations préalables

Un élément philosophique à la base de la démarche générique (et de l'informatique en général) peut s'exprimer ainsi : lorsque le code est en partie complexe, il est préférable que la complexité soit du côté du serveur plutôt que du côté du client. Tout serveur, tout objet, sera utilisé beaucoup plus souvent qu'il ne sera conçu, après tout.

Les types génériques sont parfois déclarés à travers deux fichiers d'en-tête distincts, soit un très léger qui n'expose que des déclarations a priori et l'autre exposant les classes et outils dans toute leur splendeur. Pensez par exemple à <iostream> et à sa compagne <iosfwd>. Ceci permet au code client de savoir qu'un type existe et de l'utiliser indirectement, sans avoir à inclure toute la mécanique qui lui est associée.

En POO, cette philosophie se reflète entre autres à travers l'encapsulation. En effet, un objet correctement encapsulé cache de ce fait les détails de sa mécanique interne et de son évolution.

Dans les systèmes répartis, le serveur est un spécialiste et cherche à exposer pour ses clients des services à la fois efficaces et simples à utiliser.

En programmation générique, la généricité élève le seuil d'abstraction chez les conceptrices et les concepteurs des types et des algorithmes génériques, mais le code client devrait naturellement profiter du fait que les outils génériques s'appliquent entre autres à lui, à ses besoins.

Généricité, tableaux et pointeurs bruts

En C++, passer des pointeurs en paramètre à une fonction ou à un template provoque un phénomène de décrépitude de ce pointeur (ce qu'on nomme en anglais le Pointer Decay).

Ainsi, présumant que sizeof(short)==2 et présumant que sizeof(short*)==4, l'exemple proposé à droite affichera à la console

4 4 20

...même si le paramètre passé à g() est clairement un tableau de dix short. Le type des paramètres perd en teneur sémantique, passant de tableau avant l'appel à simple pointeur dans le sous-programme appelé.

Cela peut entraîner certaines surprises pour qui souhaite définir des templates à partir de types qui sont, au fond, des pointeurs. Pensez par exemple, à des chaînes de caractères brutes.

#include <iostream>
using namespace std;
void f(short *p) {
   cout << sizeof(p) << ' ';
}
void g(short (&p)[10]) {
   cout << sizeof(p) << ' ';
}
int main() {
   short tab[10];
   f(tab);
   g(tab);
   cout << sizeof(tab) << endl;
}

Une illustration maintenant classique du phénomène est celle proposée par David Vandevoorde et Nicolai M. Josuttis dans leur volume C++ Templates, The Complete Guide. L'exemple en question ressemble fortement à celui proposé ci-dessous.

Dans cet exemple, toutes les invocations de min_ok() compilent parce que cette fonction manipule des const char*. Les paramètres effectifs sont des tableaux de caractères de taille connue alors que les paramètres formels sont de simples pointeurs grâce à la décrépitude.

La seconde invocation de min_ow(), toutefois, ne compile pas. En effet, min_ow() reçoit en paramètre des références vers une version constante du type original, or dans ce cas les littéraux d'origine que sont "allo" et "yo" ne sont pas du même type avant décrépitude, les séquences constantes pointées n'étant pas de même taille. Il se trouve que la fonction générique min_ow() s'attend, elle, à recevoir deux const T& avec le même T dans chaque cas.

#include <iostream>
using namespace std;
template <class T>
   const T& min_ow(const T &a, const T &b) {
      return a < b ? a : b;
   }
template <class T>
   T min_ok(T a, T b) {
      return a < b ? a : b;
   }
int main() {
   cout << min_ow("allo", "hola") << endl
        << min_ow("allo", "yo")   << endl
        << min_ok("allo", "hola") << endl
        << min_ok("allo", "yo")   << endl;
}

Le littéral "allo" est de type pointeur sur une séquence constante de cinq char (ou char const[5]) et le littéral "yo" est de type pointeur sur une séquence constante de trois char (ou char const[3]). Dans les deux cas, le délimiteur de fin est comptabilisé dans la taille de la séquence

Le problème ne serait évidemment pas survenu avec des std::string. Il faut faire preuve de prudence en mêlant généricité et pointeurs bruts.

Généricité par classe ou par méthode

Avec les classes et les struct, la généricité peut s'exprimer par type ou par méthode. Les deux approches sont valables et ont leurs applications, mais il y a une nuance entre ce que chacune représente et permet de faire.

Le struct nommé X, présenté à droite, est générique sur la base de son type. Le mot X en soi n'est pas une classe mais bien un modèle permettant au compilateur de générer des classes, alors que X<int> est une classe à part entière, distincte de X<string>.

Une instance de X<T> expose une méthode d'instance nommée val_defaut(), retournant un T par défaut, et un type interne et public value_type, correspondant au type T de ce X<T>.

Le programme en exemple à droite montre comment il est possible d'instancier un X<int> et un X<string> puis d'invoquer la méthode val_defaut() de chacune de ces instances.

template <class T>
   struct X {
      using value_type = T;
      static value_type val_defaut() {
         return {};
      }
   };
#include <string>
int main() {
   using std::string;
   X<int> x0;
   auto i = x0.val_defaut(); // i est int
   X<string> x1;
   auto s = x1.val_defaut(); // s est string
}

Évidemment, dans cet exemple, les types int et X<int>::value_type sont identiques, et il en va de même pour string et X<string>::value_type.

Le struct nommé Y à droite n'est pas générique mais expose une méthode générique. Ainsi, dans un programme donné, il existera une classe Y mais le nombre de méthodes d'instances afficher() de cette classe variera selon l'utilisation qui en sera faite : le compilateur générera autant de méthodes que nécessaire, une par type auquel elle sera appliquée.

Le programme à droite donne un exemple d'utilisation de ce struct. Dans ce programme, Y aura deux méthodes afficher() distinctes, l'une ayant comme premier paramètre un int et l'autre prenant plutôt une std::string, ceci parce que c'est l'utilisation que le programme en fait.

Selon les besoins, les deux approches auront leurs moments. Dans l'approche par type, il y aura plusieurs types mais un nombre fixe de méthodes; dans l'approche par méthode, il y aura un seul type mais plusieurs méthodes. Évidemment, il est possible de combiner les deux (nous y reviendrons).

#include <iostream>
#include <string>
using namespace std;
struct Y {
   template <class T>
      void afficher(T val, ostream &os) {
         os << val << ' '
      }
};
int main() {
   Y y;
   int i = 3;
   string s = "Coucou";
   y.afficher(i,cout);
   y.afficher(-3,cout);
   y.afficher(s, cout);
}

Généricité et méthodes polymorphiques

Dans ce qui suit, les termes struct et class sont équivalents au sens de notre discours, et les méthodes polymorphiques peuvent être abstraites ou non; cela ne change rien au propos.

On pourrait être tenté d'intégrer à un objet des méthodes à la fois polymorphiques (donc sujettes à être spécialisées chez les enfants) et génériques. Concrètement, ce n'est pas possible. En retour, il est possible pour un type générique d'exposer des méthodes polymorphiques. Quelle phrase, n'est-ce pas?

Examinons le tout avec un exemple pour nous y retrouver un peu.

La classe générique Indirecteur proposée à droite est un exemple légal impliquant une méthode virtuelle et une méthode abstraite. Bien qu'Indirecteur soit un type générique, la classe Indirecteur<T> pour un T donné est une classe comme les autres et peut exposer des méthodes virtuelles.

template <class T>
   struct Indirecteur {
      virtual void operer(T *) = 0;
      virtual ~Indirecteur() = default;
   };

Tout enfant d'Indirecteur<T> devra implémenter la méthode operer(T*) et pourra spécialiser sa mécanique de destruction. Le nombre de méthodes polymorphiques d'un cas particulier d'Indirecteur<T> est connu au préalable et ne dépend que du type T appliqué à la concrétisation cette classe.

En retour, on ne peut avoir de méthodes qui soient à la fois génériques et polymorphiques. Voyons un exemple pour mieux comprendre.

La classe Utilisateur proposée à droite expose un destructeur virtuel et une méthode virtuelle nommée operer(), tous deux légaux. Elle offre aussi un nombre arbitrairement grand de méthodes afficher(T) pour divers types T, ce qui est absolument correct.

Toutefois, sa méthode générique agir(), elle, est illégale car elle cherche à être à la fois générique et polymorphique.

#include <iostream>
using std::ostream;
struct Utilisateur {
   // légal
   virtual void operer(Utilisateur *);
   // légal si un T peut être
   // projeté sur un flux
   template <class T>
      void afficher(T obj, ostream &os) {
         os << obj << ' '
      }
   // illégal... pourquoi?
   template <class T>
      virtual void agir(T *) = 0;
   virtual ~Utilisateur() = default;
};

Pour comprendre le problème, mettons-nous dans la peau de ce pauvre compilateur :

Le problème est donc que la liste des méthodes polymorphiques d'une classe doit être connue à la compilation de cette classe, mais la généricité dépend de l'utilisation qu'en fait le code client, dérivés de la classe inclus. Il est impossible de générer la table de méthodes virtuelles du parent lors de sa compilation si les éléments de cette table dépendent d'éventuels enfants encore inconnus (en POO, les parents ne connaissent pas leurs enfants).

Le polymorphisme et la généricité peuvent être combinés de plusieurs manières différentes et constituent deux atouts puissants dans la boîte d'outils des informaticiennes et des informaticiens aujourd'hui, mais une méthode ne peut être à la fois générique et polymorphique.

Si vous souhaitez des clarifications sur les nuances entre généricité et polymorphisme, allez au bas du présent document où vous trouverez quelques textes en ce sens.

Une classe générique, pas à pas

Entreprenons maintenant en détail le design d'un petit type générique Tableau, annoncé d'entrée de jeu.

Définir le type visé

Pour être efficaces, nous devrons définir clairement notre objectif. Ici, nous voulons un conteneur nommé Tableau qui sera capable :

Nous devrons, au fur et à mesure de notre développement, définir clairement quel sera le contrat applicable au type T. Nous devrons aussi baliser sans ambiguïté ce que doit et ce que ne doit pas faire le type Tableau. Ces deux éléments sont aussi importants l'un que l'autre.

Certaines considérations techniques devront être examinées plus en détail au passage.

Les idées de nombre d'éléments et de capacité sont des idées distinctes. L'une représente l'espace alloué pour entreposer des éléments (capacité) alors que l'autre représente le nombre d'éléments entreposés à partir du début.

Nous aurons besoin des deux pour être en mesure de savoir quand il deviendra nécessaire de réserver de l'espace[1].

Par exemple, que signifie être vide pour une instance du type Tableau? Cela peut impliquer économiser de l'espace mémoire et faire en sorte que le pointeur qui servira de représentation interne soit nul, ou faire en sorte que le pointeur soit nécessairement valide (pointe sur un espace où il est possible d'écrire) tout en travaillant à partir du compteur du nombre d'éléments valides à l'intérieur. Les deux approches ont du bon.

Un autre détail auquel nous porterons attention est la possibilité (ou non) d'offrir des garanties de sécurité face à la levée d'exceptions. En programmation générique, dù au peu d'information connue sur les types auxquels nous appliquons nos propres types ou nos propres algorithmes, cette question n'est pas banale.

Voir ../Developpement/Exceptions.html#exception_safe pour en savoir plus à ce sujet.

Invariants à respecter

Par « en tout temps », on signifie ici de la fin de sa construction au début de sa destruction. Les moments charnières que sont la construction et la destruction d'un objet sont, bien entendu, des périodes de mutation.

Les invariants sont ces caractéristiques d'un objet qui doivent en tout temps s'avérer pour que l'objet soit considéré valide. L'encapsulation est l'outil privilégié par lequel un objet assure le respect de ses invariants. Nos invariants pour Tableau sont :

Construction par défaut et destruction

Revenon à notre démarche de rédaction d'une classe Tableau. Une fois définies les abstractions de base pour les types utilisés à titre de valeur contenue et pour les questions de taille et de capacité (types internes et publics value_type et size_type), nous définirons le sens à donner aux idées de Tableau par défaut et de destruction d'un Tableau.

Respectant les usages (et l'intuition), nous choisirons ici d'établir un invariant : un Tableau par défaut sera vide. Cet invariant influencera l'écriture du code client, qui comptera dessus pour ses propres opérations.

À l'interne, nous devront par contre déterminer ce que signifie être vide pour un Tableau. Visiblement, le nombre d'éléments (nelems) sera nul, mais pour le reste, deux grandes options s'offrent à nous :

  • Faire en sorte que le pointeur d'éléments (elems) soit nul, donc que la capacité (cap) initiale soit zéro, et
  • Allouer à l'interne un tableau d'une taille par défaut (indiquée par cap), même si cette taille est nulle (car oui, il est légal d'allouer dynamiquement un tableau de taille nulle en C++)

Les deux se valent : la première est plus économique en espace et permet d'avoir un constructeur par défaut ne levant pas d'exceptions, alors que la seconde peut être économique en temps si la capacité par défaut convient à la majorité des tâches courantes.

#include <algorithm>
#include <iterator>
template <class T>
   class Tableau {
   public:
      using value_type = T;
      using size_type = std::size_t;
      using pointer = value_type*;
      using const_pointer = const value_type*;
      using reference = value_type&;
      using const_reference = const value_type&;
   private:
      pointer elems;
      size_type cap,
                nelems;
   public:
      Tableau() noexcept : cap{}, nelems{}, elems{} {
      }
      ~Tableau() {
         delete [] elems;
      }

N'oublions pas que, si construire un T est une opération pour laquelle nous ne pouvons a priori rien affirmer quant aux risques de levée d'exceptions, le type T* demeure un type primitif : sa construction est sans risque. Initialiser elems à 0 ne lèvera donc jamais d'exception, peu importe le type T.

Il faut faire un choix, alors je choisirai la première option ici, mais chaque choix a ses vertus et influence l'ensemble du code subséquent pour notre classe : déterminer que elems puisse être nul nous impose de tenir compte de cette réalité dans les méthodes subséquentes, alors qu'allouer un tableau initial à travers elems ferait en sorte que le cas du pointeur nul soit une impossibilité.

Il est important, que le type développé soit générique ou non, d'assurer que la construction laisse l'objet dans un état stable et connu, respectueux de ses invariants. Ici, initialiser elems à 0 rend le destructeur banal car, en C++, delete 0; et delete [] 0; sont deux opérations inoffensives.

Un destructeur ne devrait jamais lever d'exceptions. Dans notre implémentation, cette contrainte est effectivement respectée... sauf si T::~T() lève lui-même une exception et contrevient à cette règle d'or!

Nous exposerons quelques accesseurs de premier ordre, pour consulter la capacité d'un Tableau et pour en connaître le nombre d'éléments.

Les noms choisis seront conformes à ceux que l'on retrouve dans les conteneurs standards.

Toujours par souci de conformité avec les conteneurs standards, et pour simplifier grandement le code client, nous définirons les types iterator et const_iterator dans notre classe, tout comme nous définirons aussi les accesseurs usuels menant vers les extrémités de la séquence contenue, soit begin() et end(), qui peuvent être const ou non, de même que leur contrepartie toujours const faite des méthodes cbegin() et cend().

   private:
      size_type capacity() const noexcept {
         return cap;
      }
   public:
      size_type size() const noexcept {
         return nelems;
      }
      bool empty() const noexcept {
         return !size();
      }

Pour notre type, ces méthodes sont simples, pour ne pas dire évidentes. Elles ne coùtent rien en taille ou en temps d'exécution et facilitent énormément la programmation dans son ensemble. Par ces petits gestes, ces petits services à coùt nul, nous parviendrons à définir une interface homogène et conforme aux attentes du code client.

En effet, exposer un itérateur et des extrémités de séquence permet d'appliquer sur notre conteneur toute la gamme des algorithmes standards et de convertir aisément d'un conteneur standard à notre conteneur et inversement (en partie grâce aux constructeurs de séquences, plus loin).

      using iterator = pointer;
      using const_iterator = const_pointer;
      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();
      }

Construction de copie et de conversion

J'utilise le terme constructeur de conversion pour un constructeur d'un type T prenant en paramètre un type U distinct de T, au sens large. Notez que les implémentations proposées ici sont perfectibles (elles sont fragiles lorsqu'une exception survient).

Tel que noté plus haut, notre choix d'avoir un tableau par défaut dont le pointeur elems est nul nous forcera à tenir compte, en tout temps, de cette possibilité dans l'implémentation des méthodes de Tableau. Heureusement, elems est un attribut pleinement encapsulé et nous sommes en mesure de cacher les ramifications de ce choix d'implémentation à l'intérieur de la classe.

Le constructeur de copie est presque évident. Par encapsulation, le paramètre tab est présumé dans un état correct.

Des exceptions peuvent être levées par l'invocation de new[] et par la copie des éléments, opération qui repose sur l'affectation d'un T à un autre T.

// ...
      Tableau(const Tableau &tab)
         : cap{tab.size()},
           nelems{tab.size()},
           elems{new value_type[tab.size()]}
      {
         try {
            std::copy(tab.begin(), tab.end(), begin());
         } catch(...) {
            delete [] elems;
            throw;
         }
      }

Dans cette classe, nous ne sommes pas en mesure de garantir sur l'affectation d'un T à un T ne lèvera pas d'exception; puisque std::copy() applique une affectation élément par élément, il est possible que cet algorithme échoue.

Dans un tel cas, nos constructeurs sont responsables de récupérer l'exception, au moins le temps de nettoyer (d'appliquer delete[] à elems qui a préalablement été alloué avec new[]) et de laisser filtrer l'exception au code client (throw;).

Le constructeur de conversion est plus subtil : il construit un Tableau<T> à partir d'un Tableau<U> (T et U sont nécessairement des types distincts ici)[2].

// ...
      template <class U>
         Tableau(const Tableau<U> &tab)
            : cap{tab.size()},
              nelems{tab.size()},
              elems{new value_type[tab.size()]}
         {
            try {
               std::copy(tab.begin(), tab.end(), begin());
            } catch(...) {
               delete [] elems;
               throw;
            }
         }

Remarquez, dans chaque cas :

À ce stade, le contrat de T implique l'exposition d'un constructeur par défaut (création dynamique d'un tableau de T) et d'un opérateur d'affectation (dont se sert std::copy()).

Bonnes pratiques

Le constructeur de conversion est une des clés de la bonne programmation générique. C'est là que doivent converger toutes les opérations de conversion.

À l'intérieur d'un type générique tel que Tableau, nous ferons en sorte de faire converger vers cette méthode toute conversion de Tableau<U> vers un Tableau<T>. L'implémentation de ce constructeur nous indique que les types T et U doivent être apparentés, au sens de un U doit pouvoir être affecté à un T, pour que le constructeur soit applicable. Chercher à construire un Tableau<float> à partir d'un Tableau<string> provoquerait des erreurs (justifiées) à la compilation par l'affectation d'une string à un float n'est pas définie.

Pour tout conteneur générique, incluant les décorateurs et les autres classes génériques qui ne contiennent qu'un seul élément, le constructeur de type apparenté vaut la peine d'être implémenté. Il allège énormément la logique d'ensemble de la classe

La conversion par construction prend son sens avec les classes génériques, résultant en une covariance de types lors de l'initialisation des conteneurs. Constation d'ailleurs qu'une double généricité s'applique ici, en ce sens que ce constructeur est une méthode générique sur un type U dans une classe générique sur un type T.

De manière générale, le constructeur de copie doit être le seul véritable lieu de duplication d'un objet, que ce constructeur soit protégé dans un type polymorphique ou qu'il soit public dans un type valeur, alors que le constructeur de conversion doit être le seul véritable lieu de conversion pour un type générique.

Retenez que le constructeur de conversion ne remplace pas le constructeur de copie. Il ne s'applique que pour un type U différent du type T.

Notez que j'ai fait de la capacité du nouvel objet une copie du nombre d'éléments de l'objet original. Ce choix n'est pas anodin. Selon vous, pourquoi ai-je privilégié cette approche?

Construction de séquence

Permettre de construire un conteneur à partir d'une séquence arbitraire signifie offrir un service extrêmement utile. Ceci permet, par exemple, de construire un vecteur à partir d'un tableau ou une liste à partir d'un vecteur.

Plutôt que de chercher à mettre au point un large éventail de cas particuliers, nous définirons un seul constructeur,m opérant à partir d'une séquence générique.[5].

La fonction std::distance(), appliquée à une séquence standard, trouve (de manière optimale pour les itérateurs impliqués) le nombre d'éléments de cette séquence.

// ...
      template <class It>
         Tableau(It debut, It fin)
            : cap{std::distance(debut, fin)},
              nelems{},
              elems{}
         {
            nelems = capacity();
            elems = new value_type[capacity()];
            try {
               std::copy(debut, fin, begin());
            } catch(...) {
               delete [] elems;
               throw;
            }
         }

En 2017, Jesse Emond m'a fait remarquer que le constructeur de conversion pourrait s’exprimer sans perte de généralité, et sans perte de vitesse, par une délégation vers le constructeur de séquence, comme suit :

template <class U>
   Tableau(const Tableau<U> &tab) : Tableau{ tab.begin(), tab.end() } {
   }

Échange d'états

L'opération swap(), par laquelle les états de deux entités peuvent être échangés, est une opération fondamentale, en particulier lors de l'implémentation d'opérations sur un conteneur. Dans la mesure où des choix d'implémentation adéquats ont été faits pour un conteneur donné, il est toujours possible d'y implémenter une méthode swap() qui s'exécutera en temps constant et de manière à ne pas lever d'exceptions.

L'algorithme standard std::swap() ne lèvera pas d'exceptions si l'affectation définie sur ses paramètres n'en lève pas – et encore : il est parfois possible de l'implémenter à partir d'une sémantique de mouvement,ce qui ne lève à peu près jamais d'exceptions. Elle peut toujours être implémentée en temps constant, [6] et peut toujours être implémentée de manière à ne pas lever d'exception.

// ...
      void swap(Tableau &tab) noexcept {
         using std::swap;
         swap(nelems, tab.nelems);
         swap(cap, tab.cap);
         swap(elems, tab.elems);
      }

La méthode swap() sert dans plusieurs manoeuvres en programmation générique car elle est généralement optimale en temps et s'avère être l'une des rares opérations qui peut toujours être écrite de manière à ne lever aucune exception, sans égard aux types impliqués.

La plupart des opérations d'un type T quelconque ne peuvent être garanties pleinement libres d'exceptions du fait que le code générique ne sait à peu près rien des détails internes au type T qu'il manipule. Il se trouve que std::swap() appliqué au type T ne manipule pas des T mais bien des T& ce qui fait toute la différence du monde[8].

Affectation et affectation covariante

Notre objectif ici sera de localiser tout effort de conversion dans les constructeurs de conversion, pour réduire la complexité du code sans entraîner de coùts inutiles. Nous appliquerons pour ce faire l'idiome sécuritaire d'affectation :

  • Affecter un Tableau<T> à un autre Tableau<T> s'implémente sans peine par la paire construction par copie/ swap() et n'implique pas de conversion, et
  • Affecter un Tableau<U> à un Tableau<T> (T différent de U) s'implémente de la même manière et localise la conversion de U à T dans la construction par copie

Nous ne pouvons pas offrir de garanties quant aux exceptions dans ces méthodes du fait que nous ne pouvons pas en offrir dans les constructeurs sur lesquels elles reposent.

// ...
      Tableau& operator=(const Tableau &tab) {
         Tableau{tab}.swap(*this);
         return *this;
      }
      template <class U>
         Tableau& operator=(const Tableau<U> &tab) {
            Tableau{tab}.swap(*this);
            return *this;
         }

Respectant les saines pratiques annoncées plus haut, nous faisons converger la copie vers le constructeur de copie. Ainsi, dans l'affectation, la véritable duplication de contenu est réalisée dans le constructeur de copie qui mène à une temporaire anonyme. De même, la conversion requise par l'opérateur daffectation covariante est réalisée à l'intérieur du constructeur de conversion. Procédant ainsi, nous évitons la duplication de fonctionnalité.

Notez au passage que nous venons, en définissant l'affectation pour Tableau, de compléter la Sainte-Trinité. La copie, l'affectation et la destruction sont toutes implémentées convenablement, ce qui signifie (informellement) que le type Tableau<T> est un type valeur, peu importe la nature de T.

Accès à un élément

L'accès à un élément en lecture seule (version const) ou en écriture (version non const) s'écrit de la même manière, aux garanties de constance près. Nous avons choisi ici d'exposer une méthode at() validant les bornes à chaque accès, mais notez que cela entraîne une perte de « performance » – en pratique, préférez les crochets []. Après tout, si votre code tente d'accéder un tableau hors des bornes valides, alors votre programme doit être réparé, tout simplement.

Remarquez que même avec at(), nous ne validons ici que la borne supérieure du tableau. Ceci tient à notre choix de std::size_t en tant que size_type, et relève donc d'un choix d'implémentation.

// ...
      class HorsBornes {};
      reference at(size_type n) {
         if (size() < n) throw HorsBornes{};
         return elems[n];
      }
      const_reference at(size_type n) const {
         if (size() < n) throw HorsBornes{};
         return elems[n];
      }
      reference operator[](size_type n) {
         return elems[n];
      }
      const_reference operator[](size_type n) const {
         return elems[n];
      }

Comparaison

La comparaison de deux instances de Tableau<T> s'implémente bien à l'aide d'une répétitive et de l'opérateur != applicable à un T.

// ...
      bool operator==(const Tableau &tab) const {
         if (size() != tab.size())
            return false;
         for (const_iterator itA = begin(), itB = tab.begin(); itA != end(); ++itA, ++itB)
            if (*itA != *itB) return false;
         return true;
      }
      bool operator!=(const Tableau &tab) const {
         return !(*this == tab);
       }

L'existence d'un constructeur implicite de conversion permet d'éviter d'écrire une déclinaison pour types apparentés des opérateurs == et !=. Si un besoin (de « performance ») se faisait sentir, implémenter des versions spécialisées de ces opérateurs serait simple.

Une écriture plus simple – et nettement préférable – de l'opérateur == serait :

bool operator==(const Tableau &tab) const {
   return size() == tab.size() && std::equal(begin(), end(), tab.begin());
}

Ajout d'éléments

Deux méthodes publiques permettront d'ajouter un élément à la fin d'un Tableau, soit :

// ...
      Tableau& operator+=(const_reference val) {
         push_back(val);
         return *this;
      }
      void push_back(const_reference val) {
         if (full()) grow();
         elems[nelems] = val;
         ++nelems;
      }
   private:
      bool full() const noexcept {
         return size() == capacity();
      }
      void grow() { // coùteux
         static const size_type TAILLE_BASE = 128; // arbitraire
         const auto n = capacity()?
            static_cast<size_type>(capacity() * 1.5) :
            TAILLE_BASE;
         auto p = new value_type[n];
         try {
            std::copy(begin(), end(), temp);
            delete[] elems;
            cap = n;
            elems = p;
         } catch(...) {
            delete[] p;
            throw;
         }
      }

La méthode privée grow() sera invoquée lorsque la capacité d'un Tableau sera sur le point d'être dépassée. Son coùt sera amorti si elle n'est pas sollicitée souvent.

Subtilité : notre implémentation du constructeur par défaut fait qu'il soit possible que capacity() retourne 0. Nous devons tenir compte de ce cas pour calculer correctement la nouvelle capacité lors d'une invocation de grow().

Notez que grow() ne pourrait pas raisonnablement indiquer de spécifications d'exceptions, throw(std::bad_alloc) ou autre, même dans le respect du standard C++ ISO de 1998. Pourquoi donc?[9]

Sémantique de mouvement

Une optimisation importante possible sous C++ 11 est celle qui permet de tenir compte des objets jetables, aussi nommés références sur des rvalue. En gros, lorsqu'une opération (souvent un constructeur ou un opérateur d'affectation) est sollicitée avec pour opérande de droite (le r de rvalue) un objet sur le point d'être détruit, il est possible d'en profiter pour remplacer l'habituelle copie des états de l'objet source dans l'objet de destination par un déplacement de contenu de l'objet source vers l'objet de destination – ceci dans la mesure où l'objet source demeure respectueux de ses invariants a posteriori.

Les implémentations proposées à droite sont simples et efficaces :

  • Le constructeur de mouvement arrache à l'objet source ses états et les dépose dans l'objet nouvellement construit, laissant l'original dans une sorte d'état par défaut. Les deux seront donc dans un état convenable par la suite
  • L'affectation de mouvement détruit la destination puis y transfère les états de l'objet source
// ...
   public:
      Tableau(Tableau &&tab) : elems{ tab.elems }, cap { autre.cap }, nelems { tab.nelems }{
         tab.elems = {};
         tab.cap = {};
         tab.nelems = {};
      }
      Tableau& operator=(Tableau &&tab) {
         delete [] elems;
         elems = tab.elems;
         cap = autre.cap;
         nelems = tab.nelems;
         return *this;
         tab.elems = {};
         tab.cap = {};
         tab.nelems = {};
      }
};

Opérations connexes

Nous ajouterons au moins deux opérations externes à l'interface de Tableau<T> :

  • Un opérateur de projection sur un flux, qui n'aura de sens que si un T lui-même peut être projeté sur un flux, et
  • Une fonction globale std::swap() qui déléguera le travail aux instances de Tableau impliquées et fera en sorte d'appliquer le meilleur algorithme possible pour ce type

Ceci complétera le portrait (bien que l'on puisse souhaiter encore ajouter une infinité d'opérations supplémentaires).

Deux remarques importantes sur le plan technique doivent être faites à ce stade.

template <class T>
   std::ostream& operator <<(std::ostream &os, const Tableau<T> &tab) {
      using namespace std;
      if (tab.empty()) return os;
      os << tab[0];
      for_each(next(begin(tab)), end(tab), [&os](auto && elem) {
         os << ' ' << elem;
      });
      return os;
   }
namespace std {
   template <class T>
      void swap(Tableau<T> &a, Tableau<T> &b) {
         a.swap(b);
      }
}

Fonctions génériques globales et ODR

Nous le savons, la définition de fonctions globales dans un fichier d'en-tête est une pratique peu recommandable en raison d'ODR (le One Definition Rule). En effet, si une définition de fonction globale est placée dans un fichier d'en-tête, alors tous les fichiers sources qui incluront cet en-tête auront leur propre définition de la fonction, en violation d'ODR.

Les fonctions globales génériques (comme l'opérateur << et la spécialisation de la fonction swap() ci-dessus) échappent à cette contrainte car elles ne seront générées qu'au moment de leur utilisation. Le compilateur doit voir les définitions pendant qu'il examine le code client pour être en mesure de générer le code attendu; conséquemment, les classes génériques et les fonctions globales génériques sont définies dans des en-têtes, visibles au code client.

Spécialiser un template défini dans l'espace nommé std

Il est interdit, en C++, d'ajouter des éléments dans l'espace nommé std. Cet espace est le terrain de jeu privé des gens qui entretiennent le standard du langage; si le commun des mortels pouvait y ajouter des éléments, cet espace serait pollué et le problème qu'il vise à résoudre reviendrait en force.

Notre swap() demeure générique puisque T y est un paramètre, et peut donc être défini dans un fichier d'en-tête.

Si nous avions une spécialisation pointue pour Tableau<int>, il s'agirait alors d'une fonction globale normale et il faudrait placer sa définition dans un fichier source.

Il est permis, par contre, de spécialiser des classes et des fonctions génériques définies dans std pour couvrir avec plus de précision des types qui nous intéressent. Ici, nous indiquons que, bien qu'il existe un std::swap() général pour deux instances de T, notre version est préférable pour deux instances de Tableau<T>.

Quelques clarifications

J'ai reçu des demandes de clarification quant à ce qui précède, en particulier de la part de Jérôme Rampon, que je remercie au passage. Permettez-moi une tentative d'illustration technique du problème.

Notons tout d'abord que C++, comme C, procède par compilation séparée. Chaque fichier source est compilé isolément, et l'édition des liens (qui constitue une étape distincte de celle de la compilation) résout les appels de fonctions en les connectant au code appelé lorsque les deux sont dans des fichiers objets distincts (.o, .obj, .lib, .a, etc.)

Imaginons maintenant ceci (ce n'est pas un grand exemple, mais c'est simple et de bon coeur) :

Fichier Acteur.h
#ifndef ACTEUR_H
#define ACTEUR_H
struct Acteur {
   virtual void agir() = 0;
   virtual ~Acteur() = default;
};
#endif

Exprimé autrement : tout Acteur sait agir, mais chaque type d'Acteur agit à sa manière.

Fichier test.cpp
#include "acteur.h"
#include <memory>
using std::unique_ptr;
unique_ptr<Acteur> creer();
int main() {
   auto p = creer();
   p->agir();
}

Nous avons ici un seul .cpp, où est appellée une hypothétique fonction creer() qui retournera un pointeur intelligent vers quelque chose qui sera au moins un Acteur. Nous appellons ensuite agir() à travers l'indirection ainsi retournée.

Il faut que le compilateur puisse savoir ce que signifie cet appel avec la seule information propre à Acteur, faute de savoir quoi que ce soit d'autre. Ici, le compilateur ne sait pas ce que retourne creer(), à une chose près : c'est au moins un Acteur.

Notez ici que du code plus gentil aurait privilégié un std::unique_ptr<Acteur> au pointeur brut, mais bon, c'est un exemple.

Le fichier test.cpp peut être compilé car il est complet (présumant le fichier Acteur.h donné plus haut) : l'appel à creer() respecte le prototype de cette fonction, les types correspondent du début à la fin, tout est propre.

Si nous procédons à l'édition des liens, toutefois, il y aura un Unresolved External Symbol sur creer(), qui a été déclarée mais pas n'a pas été définie jusqu'ici. Ceci n'est pas un problème de compilation, il faut le rappeler.

Ajoutons maintenant un fichier source à notre projet (ou à notre Makefile, ou...) :

Fichier X.cpp
#include "Acteur.h"
#include <iostream>
#include <memory>
using namespace std;
struct X : Acteur {
   void agir() {
      cout << "Coucou!" << endl;
   }
};
// définition de creer()
unique_ptr<Acteur> creer() {
   return make_unique<X>();
}

Avec l'ajout de ce fichier, grâce à l'ajout de la définition de creer(), l'édition des liens pourra se faire. Le code généré à partir de test.cpp fonctionnera et tout ira bien.

Il faut comprendre ici que X est apparue bien après Acteur, alors que main() appelle agir() à travers p à partir de la déclaration seule d'Acteur. Il faut donc qu'à partir de ce type, toutes les entrées possibles de la vtbl de X, donc de la table de méthodes virtuelles (entre autres choses) soient connues pour tous les services polymorphiques d'Acteur.

Maintenant, si on enrichit Acteur de cette manière (c'est ici que le choix de méthode perd un peu de sa pertinence, mais bon, je le répète, c'est un exemple qui se veut simple, par pertinent) :

Fichier Acteur.h (un peu galvaudé)
#ifndef ACTEUR_H
#define ACTEUR_H
struct Acteur {
   template <class T>
      T doubler(const T &val) { // bof
         return val + val;
      }
   virtual void agir() = 0;
   virtual ~Acteur() = default;
};
#endif

...alors combien de méthodes doubler() vient-on d'ajouter à notre classe? La réponse est : on ne le sait pas. En effet, il peut n'y en avoir aucune s'il s'avère que rien ni personne dans le programme n'appelle doubler() sur un Acteur; il peut n'y en avoir qu'une seule si on appelle doubler(int) et rien d'autre; il peut y avoir n cas distincts si on appelle doubler() pour n types T distincts. On ne sait pas au préalable dans quels fichiers seront faits ces appels, car chaque fichier source ignore tout des choix faits par les autres.

Sachant cela, si nous tentions de définir une version virtuelle de Acteur::doubler(), alors (a) de combien d'entrées la vtbl de la classe Acteur aurait-elle besoin? et (b) quels seraient les types T de chacune de ces entrées? On ne le saura qu'au moment de l'édition des liens, quand tous les cas possibles pour tous les fichiers d'un projet donné auront été générés – et en présumant qu'on n'utilisera aucun module à liens dynamiques, que ce soit des .so, des .dll ou peu importe, qui pourraient « cacher » des cas qui auraient échappé au compilateur.

Il demeure que la vtbl doit être générée à la compilation à partir de la seule classe Acteur car tout code client utilisant cette interface y est contraint. Exprimé autrement : dans test.cpp, l'appel p->agir() doit être indépendant des divers fichiers binaires avec lesquels l'édition sera peut-être faite un jour, et doit être compilé sur la base de son propre mérite.

Bref technique sur le polymorphisme

Il est possible que ce qui précède vous semble encore quelque peu abstrait, surtout si la mécanique du polymorphisme vous est peu connue.

Voici donc un bref aperçu de l'implémentation du polymorphisme en C++, comme dans bien des langages. Voici ce dont il en retourne.

Supposons tout d'abord une classe qui n'aurait aucun service polymorphique (rien de virtuel); alors, dans ses instances, on ne trouvera pas de vtbl du tout. Ainsi :

class X {
   int val;
public:
   X(int val) : val{val} {
   }
   int f() const {
      return val;
   }
};

Ici, il est très probable que sizeof(X)==sizeof(int). Utiliser un X n'entraînera aucun impact sur la vitesse à l'exécution ou sur l'espace occupé en comparaison avec utiliser un int, du moins pour les services que X supporte.

Si une classe offre au moins un service polymorphique, alors la vtbl de ses instances contiendra au moins une entrée par méthode virtuelle.

Ainsi :

class Y {
   // ...
public:
   virtual int f() = 0; // abstrait
   virtual int g() {
      return f() + 3; // polymorphique sans être abstrait
   }
   virtual ~Y() = default; // idem
   int h() {  // pas polymorphique du tout
      return 4;
   }
};

Ici, une instance de Y possèdera une vtbl d'au moins trois entrées, soit l'adresse de Y::f(), l'adresse de Y::g() et l'adresse de Y::~Y(). Pas d'entrée pour Y::h() par contre, puisque cette méthode ne peut être spécialisée.

Dans la vtbl de Y, l'entrée pour Y::f() contient un pointeur nul. Ceci signifie que Y ne peut être instanciée en tant que telle (un de ses services n'est pas encore implémenté), mais on peut instancier ses enfants s'ils implémentent f() eux-mêmes (et s'ils n'introduisent pas eux-mêmes de nouveaux services abstraits).

Maintenant, faut comprendre que les méthodes d'instance dans une classe se voient passer un paramètre silencieux, this, ce qui permet au compilateur de retrouver les états de l'objet et la vtbl à l'intérieur même des méthodes. Ainsi, dans Y::g(), l'appel à f() peut être fait parce qu'on connaît implicitement this, ce qui mènera à un appel de la version la plus appropriée de f() pour this.

Imaginons maintenant ces quelques classes dérivées :

class Z0 : public Y {
   // ...
public:
   int f() { // spécialise Y::f()
      return -1;
   }
};
class Z1 : public Y {
   // ...
public:
   int f() { // spécialise Y::f()
      return -3;
   }
};
class Z2 : public Y {
   // ...
public:
   int f() { // spécialise Y::f()
      return -2;
   } 
   int g() { // spécialise Y::g()
      return 10;
   }
};

Les classes Z0, Z1 et Z2 ont une vtbl identique à celle de Y car elles ont les mêmes services polymorphiques. Cependant, à titre d'exemple, pour un Z0, l'entrée de f() mène vers Z0::f alors que pour un Y, elle mène vers Y::f.

Dans le cas de Z0 et Z1, on ne spécialise que f(). Dans le cas de Z2, on spécialise aussi g(). Tout ce qui change, c'est l'adresse de la fonction dans la vtbl, ce qui est indépendant de la taille et de la structure de cette table.

Ceci illustre la différence entre le polymorphisme et la généricité sur le plan structurel. Avec la généricité, le nombre de services dans une classe variera en fonction du nombre d'appels sur la base de types distincts, mais les appels seront directs (et souvent « inlinés »). Avec le polymorphisme, en contrepartie, le nombre de services est fixé par le type au point d'appel, mais les adresses des services changent dans la vtbl en fonction des types réellement instanciés. C'est lors de la construction des instances que les entrées de la table sont remplies.

#include <iostream>
void f(Y &y) {
   using namespace std;
   cout << y.f() << ' ' << y.g() << ' ' << y.h() << endl;
}
int main() {
   // Y y; // illégal
   Z0 z0;
   Z1 z1;
   Z2 z2;
   f(z0);
   f(z1);
   f(z2);
}

Ici, le programme affichera "-1 2 4" puis "-3 0 4" puis "-2 10 4".

Lectures complémentaires

Wiki sur le sujet, qui ne se limite pas à C++ : http://en.wikipedia.org/wiki/Generic_programming

Résumé de ce qu'est la programmation générique, avec un penchant pour l'acception qu'on en fait en C++ : http://www.generic-programming.org/

Réflexions d'Alexander Stepanov sur la programmation générique :

Quelques-unes des techniques de programmation générique mises en application dans la bibliothèque Boost : http://www.boost.org/community/generic_programming.html

Exercices

EX00 – Examinez la méthode empty() qui retourne true si et seulement si le conteneur est vide. Est-ce la meilleure implémentation possible. Pouvez-vous améliorer le reste de votre conteneur en utilisant cette méthode aux endroits opportuns?

EX01 – Pouvez-vous implémenter (au moins en partie) l'opérateur de comparaison == à l'aide d'un algorithme standard? Si oui, faites-le.

EX02 – Implémentez un opérateur de comparaison == de types apparentés. Quel est l'avantage de mettre en place cette méthode?

EX03 – Serait-il avantageux d'implémenter aussi un opérateur de comparaison != de types apparentés? Expliquez votre position.

EX04 – Modifiez le design des constructeurs pour que cap ne soit jamais nulle. Modifiez la classe de manière à ce que toutes ses méthodes en tiennent compte. À votre avis, cette nouvelle implémentation est-elle meilleure que la précédente?

EX05 – Plusieurs conteneurs standards offrent (comme nous) une méthode capacity() pour connaître la capacité du conteneur et une méthode resize() pour redimensionner le conteneur. Implémentez les deux et documentez clairement le comportement de resize() à la fois lorsque cette méthode accroît la taille du conteneur et lorsqu'elle décroit cette taille.

EX06 – Plusieurs conteneurs standards sont tels que resize() ne permet pas de rapetisser un conteneur. Pouvez-vous établir les avantages et les inconvénients de cette approche?

EX07 – La méthode clear() des conteneurs standards permet de vider un conteneur de ses valeurs. Donnez au moins deux approches différentes pour implémenter cette méthode, puis implémentez-les et comparez les résultats obtenus.


[1]Si nous voulons ne garder que le nombre d'éléments et lui donner le rôle supplémentaire de capacité, alors nous devrons réallouer de l'espace à chaque ajout d'élément, stratégie très coùteuse en temps d'exécution.

[2]Pensez à un tableau de int construit à partir d'un tableau de short :

Tableau<short> tabA;
// remplir tabA
Tableau<int> tabB = tabA; // conversion covariante

[3]Ceci présume que <algorithm> a été inclus au préalable.

[4]Il se peut que certains compilateurs (dont celui de Microsoft) signalent un avertissement à l'utilisation de std::copy() car cet algorithme présume que la capacité de la destination suffit à recevoir la source. On peut comprendre les compilateurs craintifs mais ceci présume des pratiques de programmation malsaines. Ici, nous agissons en adultes responsables et cet avertissement est ridicule (pour l'éliminer, allez dans les propriétés du projet, C/ C++, Préprocesseur, et ajoutez l'option que vous recommande le compilateur dans son message d'avertissement – que vous avez lu, n'est-ce pas? – aux définitions déjà présentes).

[5]Un exemple d'utilisation d'un constructeur de séquence serait :

short tabA[10] = { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 };
Tableau<int> tabB(tabA + 5, tabA + 10); // constructeur de séquence

[6]Évidemment, il est possible de réaliser des implémentations déficientes, mais on parle ici de code bien écrit.

[7]À moins d'être extrêmement pervers.

[8]Corollaire : utiliser std::swap() sur un type n'exige rien de ce type (son contrat demeure inchangé).

[9]Il faut comprendre que nous ne savons pas si le constructeur par défaut de T ou si l'opérateur d'affectation d'un T lèvera quoi que ce soit. Nous ne sommes pas en mesure d'offrir des garanties ici.


Valid XHTML 1.0 Transitional

CSS Valide !