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.

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

4 4 20

#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.

#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 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.

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.

#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

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.

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.

#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 :

• Les méthodes polymorphiques sont implémentées par des indirections. Une table de pointeurs de méthodes sera définie dans toute instance possédant au moins une méthode polymorphique et l'adresse de la bonne méthode à invoquer pour un objet donné y sera déposée
• Si une méthode est générique sur un type T quelconque, cela implique qu'une version distincte de cette méthode sera générée pour chaque type T en fonction de laquelle elle sera utilisée en pratique
• Ne sachant pas d'avance pour combien de types distincts cette méthode sera invoquée dans un programme donné, ni si plusieurs fichiers sources utiliseront des types distincts pour la même méthode, le compilateur ne peut tout simplement pas créer la table de pointeurs de méthodes requise pour permettre le polymorphisme sur des méthodes génériques

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.

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 :

• De contenir des éléments d'un certain type
• De se faire ajouter un élément à la fin
• D'agir comme un véritable type valeur, supportant la Sainte-Trinité
• D'être comparé à l'aide des opérateurs == et !=
• D'offrir un accès direct en consultation ou en modification à l'un de ses éléments
• De croître en taille au besoin
• De révéler sa propre taille, calculée en nombre d'éléments
• De nous révéler s'il est vide, et
• De se comporter, pour l'essentiel, comme un tableau

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.

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.

Invariants à respecter

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 :

• La valeur de l'attribut nelems est précisément le nombre d'éléments entreposés dans l'objet. Cet attribut peut avoir la valeur zéro si l'objet est considéré vide, mais n'aura jamais de valeur négative
• La valeur de l'attribut cap est précisément la capacité d'entreposage (exprimée en nombre d'éléments) du substrat interne de l'objet. Cet attribut peut avoir la valeur zéro si l'objet est considéré vide, mais n'aura jamais de valeur négative
• L'attribut elems ne sera nul que si le Tableau est vide (l'inverse n'est pas vrai!). S'il n'est pas nul, alors il contient l'adresse du 1^er élément d'un tableau brut, alloué dynamiquement, de type T

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.

#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;
      }

private:
   pointer elems;
   size_type cap,
             nelems;
public:
   Tableau() noexcept : cap{}, nelems{}, elems{} {
   }

private:
   pointer elems{};
   size_type cap{},
             nelems{};
public:
   Tableau() = default;

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 à nullptr rend le destructeur banal car, en C++, delete 0; et delete [] 0; sont deux opérations inoffensives.

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

      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

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.

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;).

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

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 :

• Le recours à l'algorithme std::copy(), chose sage dans les circonstances, et
• L'initialisation d'elems à zéro, pour que le pointeur soit déjà dans un état vérifiable au moment où débute l'exécution du constructeur

À 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.

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.

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.

short tabA[] { 2, 4, 6, 8, 10, 1, 3, 5, 7, 9 };
// j'utiliser std::begin() et std::end() de <iterator> ici
Tableau<int> tabB{ begin(tabA), end(tabA) }; // constructeur de séquence

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

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

Permutation 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.

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.

Affectation et affectation covariante

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

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, mais s'implémente encore mieux à l'aide d'un algorithme standard tel que std::equal() :

bool operator==(const Tableau &tab) const {
   return size() == tab.size() && std::equal(begin(), end(), autre.begin());
}
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.

Ajout d'éléments

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

• L'opérateur += pour accommoder les algorithmes de cumul sous une forme plus mathématique, et
• Une méthode push_back() qui harmonisera notre conteneur avec les conteneurs standards

    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(), p);
         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? Parce 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.

Sémantique de mouvement

   public:
      Tableau(Tableau &&tab)
         : elems{ std::exchange(tab.elems, nullptr) },
           cap { std::exchange(autre.cap, 0) },
           nelems { std::exchange(tab.nelems, 0) } {
      }
      Tableau& operator=(Tableau &&tab) {
         if (this == &tab) return *this;
         delete [] elems;
         elems = std::exchange(tab.elems, nullptr);
         cap = std::exchange(autre.cap, 0);
         nelems = std::exchange(tab.nelems, 0);
         return *this;
      }
};

Opérations connexes

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.

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) :

#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.

#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...) :

#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) :

#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 :

• Tirées d'une entrevue avec Al Stevens en 1995 : http://stepanovpapers.com/drdobbs-interview.html
• Tirées d'une introduction pour un livre, en 2001 : http://www.stepanovpapers.com/MusserForeward.pdf

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

Chic truc de Zhihao Yuan en 2020 pour choisir plus aisément un constructeur générique : https://simpleroseinc.github.io/2020/04/05/passing-type-param-to-ctor.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.