La norme C++ et donc le langage ne précisent absolument pas comment doit être mis en oeuvre la résolution dynamique des appels de fonctions virtuelles. Le langage se contente de définir le comportement attendu. A charge des compilateurs de trouver des mécanismes appropriés pour atteindre cet objectif. Ce qui suit précise les solutions habituellement utilisées par les compilateurs. Il existe peut être des compilateurs ayant opté pour d'autres solutions (je n'en connais pas) ou dans l'avenir d'autres techniques émergeront. En ce sens, tout ce qui suit concerne plus des détails d'implémentation que des comportements imposés par la norme.

La compilation traduit le code source en code exécutable, c'est à dire en une suite d'instructions machines directement exécutées par le processeur. Une fonction est donc compilée en une suite continue d'instructions à une adresse donnée, fixe et connue à la compilation. Cette adresse est l'adresse de la fonction. Lorsqu'un appel vers une fonction est résolue à la compilation, le compilateur génère une instruction spéciale (un saut) qui demande au processeur de continuer son exécution à l'adresse indiquée. Cette adresse est connue à la compilation, et c'est l'éditeur de lien qui a la charge de mettre en dur l'adresse du saut :

aller à 0x12345678  (0x12345678 est l'adresse de la fonction)

Les nouvelles instructions, celle de la fonction, sont alors lues à partir de cette adresse et exécutées par la machine.
Pour une résolution dynamique d'une fonction virtuelle, le compilateur ne sait pas vers quelle adresse le saut doit être fait car cela dépend du type dynamique connu uniquement à l'exécution. Pour résoudre ce problème, les compilateurs - sans que ce soit une obligation mais je ne connais pas d'autres méthodes - utilisent une indirection : la table des fonctions virtuelles. Les mots vtable, v-table, dispatch table sont aussi souvent employés pour désigner la table des fonctions virtuelles. Cette table contient autant d'entrées que de fonctions virtuelles, chaque entrée contenant l'adresse d'une fonction. A chaque classe est associée une telle table avec les adresses des fonctions virtuelles lui correspondant : celle de la classe de base si la fonction n'est pas spécialisée, sinon celle de sa spécialisation.
Pour le code suivant :

struct base
{
   virtual void function_1();
   virtual void function_2();
   virtual ~base();
};

struct derived : public base
{
   virtual void function_1();
   virtual ~derived();

};

Les tables virtuelles sont :

Le compilateur est chargé de construire ces tables. Une fonction virtuelle donnée est toujours au même emplacement dans la table des fonctions virtuelles dans tout l'arbre d'héritage. Dans notre exemple, function_1 est à l'emplacement 0 pour la classe de base et pour la classe dérivée. Si une classe dérivée ajoute de nouvelles fonctions virtuelles alors celles-ci sont mises à la suite des fonctions précédentes :
Pour le code suivant :

struct base
{
   virtual void function_1();
   virtual void function_2();
   virtual ~base();
};

struct derived : public base
{
   virtual void function_1();
   virtual void function_3();
   virtual ~derived();

};

Les tables virtuelles sont :

L'appel d'une fonction virtuelle consiste alors à aller chercher dans cette table l'adresse de la fonction vers laquelle faire le saut. En pseudo code, les appels ressemblent à ça :

L'appel d'une fonction virtuelle a par conséquent un coût à l'exécution puisqu'il faut d'abord récupérer l'adresse de la fonction vers laquelle faire le saut. L'appel d'une fonction virtuelle est donc légèrement plus lent que l'appel d'une fonction non virtuelle. Ce coût n'est pas prohibitif en regard des avantages du mécanisme de résolution dynamique des fonctions virtuelles. Généralement le coût est relativement faible face à la durée d'exécution de la fonction. Enfin, avec ces tables virtuelles, ce coût est constant quelque soit la profondeur de l'héritage ou le nombre de fonctions virtuelles car l'index dans le tableau est connu à la compilation.

Les tables des fonctions virtuelles sont associées aux classes. Dès lors, comment retrouver la table virtuelle d'un objet ? Chaque objet instance d'une classe polymorphe contient un pointeur caché, vpointer, vers la table des fonctions virtuelles de son type dynamique. Pour s'en convaincre, le test suivant montre que la taille d'une classe change selon qu'elle est polymorphe ou non. Cette différence est due au pointeur vers la table des fonctions virtuelles :

#include <iostream>

struct non_polymorphic_type
{
};

struct polymorphic_type
{
   virtual ~polymorphic_type();
};


int main()
{
   std::cout<<"sizeof(non_polymorphic_type) = "<<sizeof(non_polymorphic_type)<<"\n";
   std::cout<<"sizeof(polymorphic_type) = "<<sizeof(polymorphic_type)<<"\n";

   return 0;
}

Ce code produit comme sortie :

sizeof(non_polymorphic_type) = 1
sizeof(polymorphic_type) = 4

La classe sans membre virtuel n'a pas une taille de zéro car le C++ impose que tous les types aient une taille non nulle.
Les 4 octets de la classe polymorphe correspondent avec mon Windows 32 bits à la taille d'un pointeur : 4 octets (et non pas 5, car de par la table virtuelle la classe n'a plus une taille de 0 nécessitant un octet fictif).

Lorsqu'il y a héritage multiple, pour maintenir la contrainte d'utilisation du même index dans la table des fonctions virtuelles, plusieurs tables sont associées à la classe dérivée :

#include <iostream>

struct base_1
{
   virtual ~base_1(){}
};

struct base_2
{
   virtual ~base_2(){}
};

struct derived : public base_1, public base_2
{
   virtual ~derived(){}

};


int main()
{
   std::cout<<"sizeof(base_1) = "<<sizeof(base_1)<<"\n";
   std::cout<<"sizeof(base_2) = "<<sizeof(base_2)<<"\n";
   std::cout<<"sizeof(derived) = "<<sizeof(derived)<<"\n";

   return 0;
}

La sortie produite est :

sizeof(base_1) = 4
sizeof(base_2) = 4
sizeof(derived) = 8

• sizeof(base_1) = 4 : 4 octets pour l'adresse de la table des fonctions virtuelles de base_1.
• sizeof(base_2) = 4 : 4 octets pour l'adresse de la table des fonctions virtuelles de base_2.
• sizeof(derived) = 8 : 4 octets pour l'adresse de la table des fonctions virtuelles base_1, et 4 octets pour l'adresse de la table des fonctions virtuelles base_2.

Nous avons vu que le type dynamique d'une variable ne peut jamais correspondre à une classe abstraite. Autrement dit, l'entrée de la vtable de la classe abstraite pour une fonction virtuelle pure n'est jamais lue pour trouver l'appel correspondant... Les compilateurs utilisent généralement 3 stratégies :

• laisser l'entrée initialisée : tenter de la déréférencer provoque une erreur ;
• positionner l'entrée à un pointeur nul : tenter de la déréférencer provoque une erreur ;
• positionner l'entrée vers une fonction spéciale proposée par le compilateur : en général, cette fonction affiche un message d'erreur et provoque la terminaison du programme.

Les tables de fonctions virtuelles sont de simples tableaux statiques générés par le compilateur pour chaque classe contenant des fonctions virtuelles. Il existe donc un tableau par classe indépendamment des objets instanciés. Les tables de fonctions virtuelles peuvent être vues comme des membres statiques d'une classe : elles sont partagées par toutes les instances de la classe. Le compilateur possède toutes les informations nécessaires à l'initialisation de ces tables. Le compilateur ajoute donc ces tables correctement initialisées dans le code du programme. En revanche, pour un objet instance d'une classe polymorphe, le compilateur doit ajouter le code nécessaire pour initialiser correctement le pointeur caché (vpointer) vers la bonne table. Pour cela, le compilateur ajoute dans le constructeur d'une classe un morceau de code après l'appel des constructeurs des classes de bases et avant d'entrer dans le constructeur en cours pour faire pointer le vpointer vers le tableau des fonctions virtuelles de la classe dont le constructeur va être déroulé. Ainsi, dans le constructeur, le vpointer pointe sur la table de la classe en cours. Si un appel vers une fonction virtuelle est demandé, la résolution prend l'entrée dans la table de la classe en cours et c'est bien l'appel de la fonction dont le constructeur est en train d'être exécutée qui est appelée. Cela est conforme au comportement décrit par la norme tel que nous l'avons présenté plus tôt.
Avec l'exemple suivant :

#include <iostream>
struct base_1
{
   base_1()
   {
      function_1();
      function_2();
   }
   virtual void function_1()
   {
      std::cout<<"base_1::function_1\n";
   }
   virtual void function_2()
   {
      std::cout<<"base_1::function_2\n";
   }
   virtual void function_3()=0;

   virtual ~base_1(){}
};

struct base_2 : public base_1
{
   base_2()   {
      function_1();
      function_2();
   }
   virtual void function_1()
   {
      std::cout<<"base_2::function_1\n";
   }

   virtual ~base_2(){}
};
struct base_3 : public base_2
{
   base_3()   {
      function_1();
      function_2();
      function_3();
   }
   virtual void function_1()
   {
      std::cout<<"base_3::function_1\n";
   }

   virtual void function_2()
   {
      std::cout<<"base_3::function_2\n";
   }

   virtual void function_3()
   {
      std::cout<<"base_3::function_3\n";
   }

   virtual ~base_3(){}
};

struct derived : public base_3
{
   derived()   {
      function_1();
      function_2();
      function_3();
   }
   virtual void function_1()
   {
      std::cout<<"derived::function_1\n";
   }

};

int main()
{
   derived d;
   return 0;
}

4 tables de fonctions virtuelles sont générées. Appelons-les :

Regardons maintenant la valeur du vpointeur lors de la construction :

1. Juste avant d'entrée dans base_1::base_1 : vpointer = vtable_1
2. Juste avant d'entrée dans base_2::base_2 : vpointer = vtable_2
3. Juste avant d'entrée dans base_3::base_3 : vpointer = vtable_3
4. Juste avant d'entrée dans derived::derived : vpointer = vtable_derived

Avec cette liste et le tableau précédent, vous avez tous les éléments pour prévoir la séquence de trace provoquée par l'instanciation de la variable d de la classe derived dans le main.

Si in-fine l'appel d'une fonction virtuelle pure dans le constructeur est indéterminée, au regarde de ce que nous venons de voir, on comprend mieux les différents comportements :

• Appel direct d'une fonction virtuelle pure sans définition : nous avons vu que les compilateurs choisissent une résolution statique de l'appel. Donc, la fonction n'existant pas, une erreur de lien est obtenue.
• Appel indirect d'une fonction virtuelle pure sans définition : avec un appel indirect, le compilateur doit utiliser la vtable pour résoudre l'appel. Or, l'entrée pour la fonction virtuelle est renseignée avec l'adresse d'une fonction spéciale. A l'exécution, le message d'erreur est affiché et le programme est terminé.
• Appel direct d'une fonction virtuelle pure avec définition : comme pour le premier cas, l'appel direct est optimisé par le compilateur et un saut vers la définition de la fonction est ajouté. Cela se passe donc sans problème.
• Appel indirect d'une fonction virtuelle pure avec définition : comme dans le second cas, la table virtuelle est utilisée et la fonction spéciale d'affichage d'erreur et de terminaison est appelée.

La destruction d'une variable suit le processus inverse de la construction : à l'entrée du destructeur, le vpointer est redirigé vers la classe dont le destructeur va être exécuté. Le comportement est donc identique que pour le constructeur : les fonctions virtuelles (non pures) appelées sont celles de la classe dont le destructeur est en train de s'exécuter et les fonctions virtuelles pures dans les classes abstraites provoquent l'appel de la fonction spéciale de trace et de terminaison.

Les adresses des fonctions virtuelles peuvent être récupérées tout comme celles des adresses des fonctions non virtuelles :

#include <iostream>

struct base
{
   void non_virtual_function()
   {
      std::cout<<"base::non_virtual_function\n";
   }

   virtual void virtual_function()
   {
      std::cout<<"base::virtual_function\n";
   }
};
int main()
{
   base b;
   void (base::*p_function)(void);

   p_function = &base::non_virtual_function;
   (b.*p_function)();
   p_function =  &base::virtual_function;
   (b.*p_function)();

   return 0;
}

Pour une fonction non virtuelle, l'affaire est simple : l'adresse positionnée dans p_function est donnée en dur à la compilation avec la fonction générée. En revanche, rien de tel ne peut être fait avec une fonction virtuelle car l'adresse est résolue dynamiquement à l'exécution.
Visual C++ créé ce qu'on appelle un thunk. Il s'agit d'une fonction qui prend en paramètre un objet de la classe et appelle la fonction virtuelle à l'aide de la vtable. Dans notre exemple, il créé une fonction non virtuelle vcall_0 et donne son adresse à p_function. vcall_0 ressemble à ça :

void vcall_0(base &rb_)
{
   rb_.virtual_function();
}

A chaque fonction virtuelle est associée un thunk avec la même signature (respectant les paramètres, le type retour, la constance) pour permettre cet appel.
De ce que j'ai compris, GCC utilise une méthode un peu plus subtile. Elle se base sur le fait que les adresses de fonctions sont alignées sur 4 octets. Donc elles sont toujours paires. Pour une fonction virtuelle, p_function reçoit le décalage en octet de l'entrée dans la vtable incrémenté de 1. Par exemple, pour la fonction virtuelle de la première entrée, la variable reçoit 1. Pour la fonction virtuelle de la troisième entrée, la variable reçoit (3-1)*4 + 1 = 9. 3, pour la troisième entrée, -1 car les tableaux commencent avec l'index 0, *4 car les pointeurs sont sur 32 bits.
Donc un pointeur de fonction désignant une fonction virtuelle a une valeur impaire. Lors de l'appel effectif de la fonction sur un objet, GCC commence par tester la parité du pointeur de fonction. Si la valeur du pointeur est paire, c'est une fonction non virtuelle, l'adresse utilisée correspond à cette valeur. Si la valeur du pointeur est impaire, GCC récupère la table des fonctions virtuelles de l'objet, décrémente la valeur du pointeur de 1, se décale pour atteindre l'entrée correspondante et récupère l'adresse effective à exécuter.
Visual C++ introduit un coût supplémentaire pour l'appel de fonctions virtuelles par pointeur de fonction car un saut supplémentaire est utilisé vers le thunk. GCC ne génère pas de fonctions thunk spécifiques, en revanche il introduit une pénalité pour chaque appel de fonction non virtuelle via un pointeur de fonction puisque la parité est systématiquement testée pour savoir quelle action entreprendre. L'appel de fonctions non virtuelles avec un pointeur de fonction n'a pas de surcoût avec Visual C++. 2 compilateurs, 2 choix différents. Probablement que d'autres compilateurs ont fait des choix encore différents de ceux-là.