CRTP, aby uniknąć dynamicznego polimorfizmu

89

Jak mogę używać CRTP w C ++, aby uniknąć narzutu wirtualnych funkcji członkowskich?

Lekkość wyścigów na orbicie
źródło

Odpowiedzi:

141

Istnieją dwa sposoby.

Pierwszym jest statyczne określenie interfejsu dla struktury typów:

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

Drugi polega na unikaniu stosowania idiomu odniesienia do bazy lub wskaźnika do podstawy i wykonywaniu okablowania w czasie kompilacji. Korzystając z powyższej definicji, możesz mieć funkcje szablonów, które wyglądają następująco:

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

Zatem połączenie definicji struktury / interfejsu i odliczenia typu czasu kompilacji w twoich funkcjach pozwala na wysyłanie statyczne zamiast dynamicznego. Na tym polega istota statycznego polimorfizmu.

Dean Michael
źródło
15
Doskonała odpowiedź
Eli Bendersky
5
Chciałbym podkreślić, że not_derived_from_basenie pochodzi z base, ani nie pochodzi z base...
leftaroundo około
3
W rzeczywistości deklaracja foo () wewnątrz my_type / your_type nie jest wymagana. codepad.org/ylpEm1up (powoduje przepełnienie stosu) - Czy istnieje sposób na wymuszenie definicji foo w czasie kompilacji? - Ok, znalazłem rozwiązanie: ideone.com/C6Oz9 - Może chcesz to poprawić w swojej odpowiedzi.
cooky451
3
Czy mógłbyś mi wyjaśnić, jaka jest motywacja do używania CRTP w tym przykładzie? Gdyby bar został zdefiniowany jako template <class T> void bar (T & obj) {obj.foo (); }, to każda klasa dostarczająca foo będzie w porządku. Na podstawie twojego przykładu wygląda na to, że jedynym zastosowaniem CRTP jest określenie interfejsu w czasie kompilacji. Czy do tego służy?
Anton Daneyko
1
@Dean Michael Rzeczywiście, kod w przykładzie kompiluje się, nawet jeśli foo nie jest zdefiniowane w my_type i your_type. Bez tych nadpisań metoda base :: foo jest wywoływana rekurencyjnie (i przepływy stosu). Więc może chcesz poprawić swoją odpowiedź, tak jak pokazał cooky451?
Anton Daneyko
18

Sam szukałem porządnych dyskusji na temat CRTP. Techniki Todda Veldhuizena dotyczące naukowego języka C ++ to świetne źródło informacji o tym (1.3) i wielu innych zaawansowanych technikach, takich jak szablony wyrażeń.

Odkryłem również, że większość oryginalnego artykułu Coplien o C ++ Gems można przeczytać w książkach Google. Może nadal tak jest.

fizzer
źródło
@fizzer Przeczytałem część, którą sugerujesz, ale nadal nie rozumiem, co oznacza podwójna suma szablonu <class T_leaftype> (Matrix <T_leaftype> & A); kupuje w porównaniu z szablonem <class Cokolwiek> podwójna suma (Cokolwiek & A);
Anton Daneyko
@AntonDaneyko W przypadku wywołania w instancji bazowej wywoływana jest suma klasy bazowej, np. „Obszar kształtu” z domyślną implementacją, tak jakby był kwadratem. Celem CRTP w tym przypadku jest rozwiązanie najbardziej pochodnej implementacji, „obszaru trapezu” itp., Przy jednoczesnym zachowaniu możliwości odniesienia się do trapezu jako kształtu, dopóki nie będzie wymagane wyprowadzone zachowanie. Zasadniczo zawsze, gdy normalnie potrzebujesz dynamic_castlub metod wirtualnych.
John P
1

Musiałem sprawdzić CRTP . Jednak gdy to zrobiłem, znalazłem trochę rzeczy na temat statycznego polimorfizmu . Podejrzewam, że to jest odpowiedź na Twoje pytanie.

Okazuje się, że ATL dość szeroko wykorzystuje ten wzorzec.

Roger Lipscombe
źródło
-5

Ta odpowiedź z Wikipedii zawiera wszystko, czego potrzebujesz. Mianowicie:

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

Chociaż nie wiem, ile to faktycznie kosztuje. Narzut wywołania funkcji wirtualnej jest (oczywiście zależny od kompilatora):

  • Pamięć: jeden wskaźnik funkcji na funkcję wirtualną
  • Środowisko wykonawcze: jedno wywołanie wskaźnika funkcji

Podczas gdy narzut statyczny polimorfizmu CRTP wynosi:

  • Pamięć: Duplikacja Base na wystąpienie szablonu
  • Środowisko uruchomieniowe: jedno wywołanie wskaźnika funkcji + cokolwiek robi static_cast
user23167
źródło
4
W rzeczywistości powielanie instancji Base na szablon jest iluzją, ponieważ (chyba że nadal masz vtable) kompilator połączy przechowywanie bazy i pochodnej w jedną strukturę dla Ciebie. Wywołanie wskaźnika funkcji jest również optymalizowane przez kompilator (część static_cast).
Dean Michael
19
Nawiasem mówiąc, twoja analiza CRTP jest nieprawidłowa. Powinno być: Pamięć: Nic, jak powiedział Dean Michael. Runtime: Jedno (szybsze) wywołanie funkcji statycznej, a nie wirtualnej, co jest celem ćwiczenia. static_cast nic nie robi, po prostu pozwala skompilować kod.
Frederik Slijkerman
2
Chodzi mi o to, że kod podstawowy zostanie zduplikowany we wszystkich wystąpieniach szablonu (samo scalanie, o którym mówisz). Podobne do posiadania szablonu z tylko jedną metodą, która opiera się na parametrze szablonu; wszystko inne jest lepsze w klasie bazowej, w przeciwnym razie jest wielokrotnie wciągane („scalane”).
user23167
1
Każda metoda w bazie zostanie ponownie skompilowana dla każdego wyprowadzonego. W (oczekiwanym) przypadku, w którym każda utworzona metoda jest inna (ze względu na różne właściwości Derived), nie musi to być liczone jako narzut. Ale może to prowadzić do większego całkowitego rozmiaru kodu w porównaniu z sytuacją, w której złożona metoda w (normalnej) klasie bazowej wywołuje wirtualne metody podklas. Ponadto, jeśli umieścisz metody narzędziowe w Base <Derived>, które w rzeczywistości wcale nie zależą od <Derived>, nadal zostaną utworzone instancje. Może globalna optymalizacja w jakiś sposób to naprawi.
greggo
Wywołanie, które przechodzi przez kilka warstw CRTP, rozszerzy się w pamięci podczas kompilacji, ale może łatwo skurczyć się przez TCO i inlining. Sam CRTP nie jest więc winowajcą, prawda?
John P