CRTP para evitar polimorfismo dinâmico

89

Como posso usar CRTP em C ++ para evitar a sobrecarga de funções de membro virtual?

Lightness Races in Orbit
fonte

Respostas:

139

Existem duas maneiras.

A primeira é especificando a interface estaticamente para a estrutura 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.
};

A segunda é evitar o uso do idioma referência à base ou ponteiro para base e fazer a fiação em tempo de compilação. Usando a definição acima, você pode ter funções de modelo semelhantes 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

Portanto, combinar a definição de estrutura / interface e a dedução de tipo de tempo de compilação em suas funções permite que você faça despacho estático em vez de despacho dinâmico. Esta é a essência do polimorfismo estático.

Dean Michael
fonte
15
Excelente resposta
Eli Bendersky
5
Eu gostaria de enfatizar que not_derived_from_basenão é derivado de base, nem é derivado de base...
menos em
3
Na verdade, a declaração de foo () dentro de my_type / your_type não é necessária. codepad.org/ylpEm1up (Causa estouro de pilha) - Existe uma maneira de forçar uma definição de foo em tempo de compilação? - Ok, encontrei uma solução: ideone.com/C6Oz9 - Talvez você queira corrigir isso em sua resposta.
cooky451
3
Você poderia me explicar qual é a motivação para usar CRTP neste exemplo? Se bar seria definido como modelo <class T> void bar (T & obj) {obj.foo (); }, então qualquer classe que forneça foo seria adequada. Portanto, com base em seu exemplo, parece que o único uso do CRTP é especificar a interface em tempo de compilação. É para isso que serve?
Anton Daneyko,
1
@Dean Michael De fato, o código no exemplo compila mesmo se foo não estiver definido em my_type e your_type. Sem essas substituições, o base :: foo é recursivamente chamado (e stackoverflows). Então, talvez você queira corrigir sua resposta como o cooky451 mostrou?
Anton Daneyko,
18

Tenho procurado discussões decentes sobre o CRTP. O Techniques for Scientific C ++ de Todd Veldhuizen é um grande recurso para este (1.3) e muitas outras técnicas avançadas, como modelos de expressão.

Além disso, descobri que você pode ler a maior parte do artigo C ++ Gems original de Coplien nos livros do Google. Talvez ainda seja o caso.

fizzer
fonte
@fizzer Eu li a parte que você sugere, mas ainda não entendo o que o template <class T_leaftype> double sum (Matrix <T_leaftype> & A); compra você em comparação com o template <class Whatever> double sum (Whatever & A);
Anton Daneyko,
@AntonDaneyko Quando chamado em uma instância base, a soma da classe base é chamada, por exemplo, "área de uma forma" com implementação padrão como se fosse um quadrado. O objetivo do CRTP, neste caso, é resolver a implementação mais derivada, "área de um trapézio", etc., enquanto ainda é capaz de se referir ao trapézio como uma forma até que o comportamento derivado seja necessário. Basicamente, sempre que você normalmente precisa dynamic_castde métodos virtuais.
John P
1

Eu tive que procurar CRTP . Tendo feito isso, no entanto, descobri algumas coisas sobre polimorfismo estático . Suspeito que esta seja a resposta à sua pergunta.

Acontece que o ATL usa esse padrão amplamente.

Roger Lipscombe
fonte
-5

Esta resposta da Wikipedia tem tudo que você precisa. Nomeadamente:

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

Embora eu não saiba quanto isso realmente te compra. A sobrecarga de uma chamada de função virtual é (dependente do compilador, é claro):

  • Memória: Um ponteiro de função por função virtual
  • Tempo de execução: uma chamada de ponteiro de função

Embora a sobrecarga do polimorfismo estático CRTP seja:

  • Memória: Duplicação de Base por instanciação de modelo
  • Tempo de execução: uma chamada de ponteiro de função + o que quer que static_cast esteja fazendo
user23167
fonte
4
Na verdade, a duplicação de Base por instanciação de modelo é uma ilusão porque (a menos que você ainda tenha uma vtable) o compilador irá mesclar o armazenamento da base e o derivado em uma única estrutura para você. A chamada do ponteiro de função também é otimizada pelo compilador (a parte static_cast).
Dean Michael
19
A propósito, sua análise do CRTP está incorreta. Deveria ser: Memória: Nada, como disse Dean Michael. Runtime: Uma chamada de função estática (mais rápida), não virtual, que é o objetivo do exercício. static_cast não faz nada, apenas permite que o código seja compilado.
Frederik Slijkerman
2
Meu ponto é que o código base será duplicado em todas as instâncias de modelo (a própria fusão de que você fala). Semelhante a ter um modelo com apenas um método que depende do parâmetro do modelo; todo o resto é melhor em uma classe base, caso contrário, ele é puxado ('mesclado') várias vezes.
user23167
1
Cada método na base será compilado novamente para cada derivado. No caso (esperado) em que cada método instanciado é diferente (por causa das propriedades de Derivado serem diferentes), isso não pode necessariamente ser contado como sobrecarga. Mas pode levar a um tamanho geral de código maior, em comparação com a situação em que um método complexo na classe base (normal) chama métodos virtuais de subclasses. Além disso, se você colocar métodos utilitários em Base <Derived>, que na verdade não dependem de <Derived>, eles ainda serão instanciados. Talvez a otimização global conserte isso de alguma forma.
Greggo 01 de
Uma chamada que passa por várias camadas de CRTP se expande na memória durante a compilação, mas pode se contrair facilmente por meio do TCO e do inlining. O CRTP em si não é realmente o culpado, certo?
John P