CRTP para evitar el polimorfismo dinámico

89

¿Cómo puedo usar CRTP en C ++ para evitar la sobrecarga de las funciones de miembros virtuales?

Carreras de ligereza en órbita
fuente

Respuestas:

139

Hay dos maneras.

El primero es especificando la interfaz estáticamente para la estructura de tipos:

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 segunda es evitar el uso del lenguaje de referencia a base o puntero a base y hacer el cableado en tiempo de compilación. Usando la definición anterior, puede tener funciones de plantilla que se parecen a estas:

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

Por lo tanto, la combinación de la definición de estructura / interfaz y la deducción de tipo en tiempo de compilación en sus funciones le permite realizar un envío estático en lugar de un envío dinámico. Ésta es la esencia del polimorfismo estático.

Dean Michael
fuente
15
Excelente respuesta
Eli Bendersky
5
Me gustaría enfatizar que not_derived_from_baseno se deriva baseni se deriva de base...
izquierda rotonda sobre
3
En realidad, la declaración de foo () dentro de my_type / your_type no es necesaria. codepad.org/ylpEm1up (Causa el desbordamiento de la pila) - ¿Hay alguna manera de hacer cumplir una definición de foo en tiempo de compilación? - Ok, encontré una solución: ideone.com/C6Oz9 - Tal vez quieras corregir eso en tu respuesta.
cooky451
3
¿Podría explicarme cuál es la motivación para usar CRTP en este ejemplo? Si la barra se definiría como plantilla <clase T> void bar (T & obj) {obj.foo (); }, entonces cualquier clase que proporcione foo estaría bien. Entonces, según su ejemplo, parece que el único uso de CRTP es especificar la interfaz en tiempo de compilación. ¿Para eso es?
Anton Daneyko
1
@Dean Michael De hecho, el código del ejemplo se compila incluso si foo no está definido en my_type y your_type. Sin esas anulaciones, base :: foo se llama de forma recursiva (y stackoverflows). Entonces, ¿tal vez quieras corregir tu respuesta como mostró cooky451?
Anton Daneyko
18

Yo mismo he estado buscando discusiones decentes sobre CRTP. Las técnicas de Todd Veldhuizen para C ++ científico son un gran recurso para esto (1.3) y muchas otras técnicas avanzadas como las plantillas de expresión.

Además, descubrí que se podía leer la mayoría de los artículos de Gemas C ++ originales de Coplien en Google Books. Quizás ese todavía sea el caso.

fizzer
fuente
@fizzer He leído la parte que sugieres, pero aún no entiendo qué significa la plantilla <class T_leaftype> double sum (Matrix <T_leaftype> & A); le compra en comparación con la plantilla <class Whatever> doble suma (Whatever & A);
Anton Daneyko
@AntonDaneyko Cuando se llama en una instancia base, se llama a la suma de la clase base, por ejemplo, "área de una forma" con implementación predeterminada como si fuera un cuadrado. El objetivo de CRTP en este caso es resolver la implementación más derivada, el "área de un trapezoide", etc., sin dejar de poder referirse al trapezoide como una forma hasta que se requiera un comportamiento derivado. Básicamente, siempre que lo necesite normalmente dynamic_casto métodos virtuales.
John P
1

Tuve que buscar CRTP . Sin embargo, habiendo hecho eso, encontré algunas cosas sobre el polimorfismo estático . Sospecho que esta es la respuesta a tu pregunta.

Resulta que ATL usa este patrón de manera bastante extensa.

Roger Lipscombe
fuente
-5

Esta respuesta de Wikipedia tiene todo lo que necesita. A saber:

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();
};

Aunque no sé cuánto te compra esto realmente. La sobrecarga de una llamada de función virtual es (dependiente del compilador, por supuesto):

  • Memoria: un puntero de función por función virtual
  • Tiempo de ejecución: una llamada de puntero de función

Mientras que la sobrecarga del polimorfismo estático CRTP es:

  • Memoria: duplicación de base por instanciación de plantilla
  • Tiempo de ejecución: una llamada de puntero de función + lo que esté haciendo static_cast
usuario23167
fuente
4
En realidad, la duplicación de Base por instanciación de plantilla es una ilusión porque (a menos que todavía tenga una vtable) el compilador fusionará el almacenamiento de la base y el derivado en una sola estructura para usted. El compilador también optimiza la llamada a la función del puntero (la parte static_cast).
Dean Michael
19
Por cierto, su análisis de CRTP es incorrecto. Debería ser: Memoria: Nada, como dijo Dean Michael. Tiempo de ejecución: una llamada de función estática (más rápida), no virtual, que es el objetivo del ejercicio. static_cast no hace nada, solo permite que el código se compile.
Frederik Slijkerman
2
Mi punto es que el código base se duplicará en todas las instancias de la plantilla (la misma fusión de la que habla). Similar a tener una plantilla con un solo método que se basa en el parámetro de la plantilla; todo lo demás es mejor en una clase base, de lo contrario, se incorpora ('fusiona') varias veces.
user23167
1
Cada método de la base se volverá a compilar para cada derivado. En el caso (esperado) en el que cada método instanciado es diferente (debido a que las propiedades de Derived son diferentes), eso no necesariamente se puede contar como una sobrecarga. Pero puede conducir a un tamaño de código general más grande, en comparación con la situación en la que un método complejo en la clase base (normal) llama a métodos virtuales de subclases. Además, si coloca métodos de utilidad en Base <Derived>, que en realidad no dependen en absoluto de <Derived>, aún así se crearán instancias. Quizás la optimización global lo arregle de alguna manera.
Greggo
Una llamada que pasa por varias capas de CRTP se expandirá en la memoria durante la compilación, pero puede contraerse fácilmente a través del TCO y la inserción. El CRTP en sí mismo no es realmente el culpable, ¿verdad?
John P