CRTP pour éviter le polymorphisme dynamique

89

Comment puis-je utiliser CRTP en C ++ pour éviter la surcharge des fonctions membres virtuelles?

Courses de légèreté en orbite
la source

Réponses:

139

Il y a deux manières.

Le premier consiste à spécifier l'interface de manière statique pour la structure des types:

template <class Derived>
struct base {
  void foo() {
    static_cast<Derived *>(this)->foo();
  };
};

struct my_type : base<my_type> {
  void foo(); // required to compile.
};

struct your_type : base<your_type> {
  void foo(); // required to compile.
};

La seconde consiste à éviter l'utilisation de l'idiome de référence à la base ou de pointeur à la base et à effectuer le câblage au moment de la compilation. En utilisant la définition ci-dessus, vous pouvez avoir des fonctions de modèle qui ressemblent à celles-ci:

template <class T> // T is deduced at compile-time
void bar(base<T> & obj) {
  obj.foo(); // will do static dispatch
}

struct not_derived_from_base { }; // notice, not derived from base

// ...
my_type my_instance;
your_type your_instance;
not_derived_from_base invalid_instance;
bar(my_instance); // will call my_instance.foo()
bar(your_instance); // will call your_instance.foo()
bar(invalid_instance); // compile error, cannot deduce correct overload

Ainsi, la combinaison de la définition de structure / interface et de la déduction de type au moment de la compilation dans vos fonctions vous permet de faire une distribution statique au lieu d'une distribution dynamique. C'est l'essence du polymorphisme statique.

Dean Michael
la source
15
Excellente réponse
Eli Bendersky
5
Je tiens à souligner que ce not_derived_from_basen'est pas dérivé de base, ni dérivé de base...
gauche autour du
3
En fait, la déclaration de foo () dans my_type / your_type n'est pas requise. codepad.org/ylpEm1up (Provoque un débordement de pile) - Existe-t-il un moyen d'appliquer une définition de foo au moment de la compilation? - Ok, j'ai trouvé une solution: ideone.com/C6Oz9 - Peut-être voulez-vous corriger cela dans votre réponse.
cooky451
3
Pourriez-vous m'expliquer quelle est la motivation d'utiliser le CRTP dans cet exemple? Si bar serait défini comme modèle <class T> void bar (T & obj) {obj.foo (); }, alors n'importe quelle classe qui fournit foo conviendrait. Donc, sur la base de votre exemple, il semble que la seule utilisation de CRTP est de spécifier l'interface au moment de la compilation. Est-ce à quoi ça sert?
Anton Daneyko
1
@Dean Michael En effet, le code de l'exemple se compile même si foo n'est pas défini dans my_type et your_type. Sans ces remplacements, base :: foo est appelé récursivement (et stackoverflows). Alors peut-être voulez-vous corriger votre réponse comme l'a montré cooky451?
Anton Daneyko
18

J'ai moi-même recherché des discussions décentes sur le CRTP. Techniques for Scientific C ++ de Todd Veldhuizen est une excellente ressource pour cela (1.3) et de nombreuses autres techniques avancées comme les modèles d'expression.

De plus, j'ai trouvé que vous pouviez lire la plupart des articles originaux de Coplien sur C ++ Gems dans Google Books. C'est peut-être toujours le cas.

pétillant
la source
@fizzer J'ai lu la partie que vous suggérez, mais je ne comprends toujours pas ce que fait la double somme du modèle <class T_leaftype> (Matrix <T_leaftype> & A); vous achète par rapport au modèle <class Whatever> double somme (Whatever & A);
Anton Daneyko
@AntonDaneyko Lorsqu'elle est appelée sur une instance de base, la somme de la classe de base est appelée, par exemple "aire d'une forme" avec l'implémentation par défaut comme s'il s'agissait d'un carré. Le but du CRTP dans ce cas est de résoudre l'implémentation la plus dérivée, "l'aire d'un trapèze", etc. tout en étant capable de se référer au trapèze comme une forme jusqu'à ce qu'un comportement dérivé soit requis. Fondamentalement, chaque fois que vous auriez normalement besoin dynamic_castde méthodes virtuelles.
John P
1

J'ai dû chercher CRTP . Après avoir fait cela, cependant, j'ai trouvé des trucs sur le polymorphisme statique . Je soupçonne que c'est la réponse à votre question.

Il s'avère qu'ATL utilise ce modèle assez largement.

Roger Lipscombe
la source
-5

Cette réponse Wikipedia a tout ce dont vous avez besoin. À savoir:

template <class Derived> struct Base
{
    void interface()
    {
        // ...
        static_cast<Derived*>(this)->implementation();
        // ...
    }

    static void static_func()
    {
        // ...
        Derived::static_sub_func();
        // ...
    }
};

struct Derived : Base<Derived>
{
    void implementation();
    static void static_sub_func();
};

Bien que je ne sache pas combien cela vous achète réellement. La surcharge d'un appel de fonction virtuelle est (dépendante du compilateur, bien sûr):

  • Mémoire: un pointeur de fonction par fonction virtuelle
  • Runtime: un appel de pointeur de fonction

Alors que la surcharge du polymorphisme statique CRTP est:

  • Mémoire: Duplication de base par instanciation de modèle
  • Exécution: un appel de pointeur de fonction + tout ce que fait static_cast
utilisateur23167
la source
4
En fait, la duplication de Base par instanciation de modèle est une illusion car (à moins que vous n'ayez toujours une vtable) le compilateur fusionnera le stockage de la base et du dérivé en une structure unique pour vous. L'appel du pointeur de fonction est également optimisé par le compilateur (la partie static_cast).
Dean Michael
19
Au fait, votre analyse du CRTP est incorrecte. Cela devrait être: Mémoire: Rien, comme l'a dit Dean Michael. Runtime: Un appel de fonction statique (plus rapide), pas virtuel, qui est le but de l'exercice. static_cast ne fait rien, il permet simplement au code de se compiler.
Frederik Slijkerman
2
Mon point est que le code de base sera dupliqué dans toutes les instances de modèle (la fusion même dont vous parlez). Semblable à avoir un modèle avec une seule méthode qui repose sur le paramètre de modèle; tout le reste est meilleur dans une classe de base, sinon il est tiré plusieurs fois («fusionné»).
user23167
1
Chaque méthode de la base sera à nouveau compilée pour chaque dérivée. Dans le cas (attendu) où chaque méthode instanciée est différente (car les propriétés de Derived sont différentes), cela ne peut pas nécessairement être compté comme une surcharge. Mais cela peut conduire à une taille de code globale plus grande, par rapport à la situation où une méthode complexe de la classe de base (normale) appelle des méthodes virtuelles de sous-classes. De plus, si vous placez des méthodes utilitaires dans Base <Derived>, qui ne dépendent pas du tout de <Derived>, elles seront toujours instanciées. Peut-être que l'optimisation globale résoudra quelque peu ce problème.
greggo
Un appel qui passe par plusieurs couches de CRTP se développera en mémoire pendant la compilation mais peut facilement se contracter via le TCO et l'inlining. Le CRTP lui-même n'est donc pas vraiment le coupable, non?
John P