CRTP untuk menghindari polimorfisme dinamis

89

Bagaimana saya dapat menggunakan CRTP di C ++ untuk menghindari overhead fungsi anggota virtual?

Balapan Ringan dalam Orbit
sumber

Jawaban:

141

Ada dua cara.

Yang pertama adalah dengan menentukan antarmuka secara statis untuk struktur tipe:

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

Yang kedua adalah dengan menghindari penggunaan idiom reference-to-base atau pointer-to-base dan melakukan wiring pada waktu kompilasi. Menggunakan definisi di atas, Anda dapat memiliki fungsi template yang terlihat seperti ini:

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

Jadi, menggabungkan definisi struktur / antarmuka dan pengurangan jenis waktu kompilasi dalam fungsi Anda memungkinkan Anda untuk melakukan pengiriman statis, bukan pengiriman dinamis. Ini adalah inti dari polimorfisme statis.

Dean Michael
sumber
15
Jawaban luar biasa
Eli Bendersky
5
Saya ingin menekankan bahwa not_derived_from_basetidak berasal dari base, juga bukan berasal dari base...
kiri sekitar
3
Sebenarnya, deklarasi foo () di dalam my_type / your_type tidak diperlukan. codepad.org/ylpEm1up (Menyebabkan stack overflow) - Apakah ada cara untuk menerapkan definisi foo pada waktu kompilasi? - Oke, temukan solusinya: ideone.com/C6Oz9 - Mungkin Anda ingin memperbaikinya di jawaban Anda.
cooky451
3
Bisakah Anda menjelaskan kepada saya apa motivasi menggunakan CRTP dalam contoh ini? Jika bar akan didefinisikan sebagai template <class T> void bar (T & obj) {obj.foo (); }, maka semua kelas yang menyediakan foo akan baik-baik saja. Jadi berdasarkan contoh Anda, sepertinya satu-satunya penggunaan CRTP adalah untuk menentukan antarmuka pada waktu kompilasi. Untuk apa itu?
Anton Daneyko
1
@Dean Michael Memang kode dalam contoh ini dikompilasi meskipun foo tidak ditentukan dalam my_type dan your_type. Tanpa penggantian tersebut, base :: foo dipanggil secara rekursif (dan stackoverflows). Jadi mungkin Anda ingin mengoreksi jawaban Anda seperti yang ditunjukkan oleh cooky451?
Anton Daneyko
18

Saya sendiri sedang mencari diskusi yang layak tentang CRTP. Teknik Todd Veldhuizen untuk Scientific C ++ adalah sumber yang bagus untuk ini (1.3) dan banyak teknik lanjutan lainnya seperti template ekspresi.

Selain itu, saya menemukan bahwa Anda dapat membaca sebagian besar artikel C ++ Gems asli Coplien di buku Google. Mungkin masih begitu.

fizzer
sumber
@fizzer Saya telah membaca bagian yang Anda sarankan, tetapi masih tidak mengerti apa itu template <class T_leaftype> double sum (Matrix <T_leaftype> & A); membeli Anda dibandingkan dengan template <class What's> double sum (What's & A);
Anton Daneyko
@AntonDaneyko Ketika dipanggil pada instance dasar, jumlah kelas dasar dipanggil, misalnya "area dari suatu bentuk" dengan implementasi default seolah-olah itu adalah persegi. Tujuan CRTP dalam hal ini adalah untuk menyelesaikan implementasi yang paling banyak diturunkan, "area trapesium", dll. Sambil tetap dapat merujuk ke trapesium sebagai bentuk hingga perilaku turunan diperlukan. Pada dasarnya, kapan pun Anda biasanya membutuhkan dynamic_castatau metode virtual.
John P
1

Saya harus mencari CRTP . Namun, setelah melakukan itu, saya menemukan beberapa hal tentang Polimorfisme Statis . Saya curiga inilah jawaban atas pertanyaan Anda.

Ternyata ATL menggunakan pola ini cukup ekstensif.

Roger Lipscombe
sumber
-5

Jawaban Wikipedia ini memiliki semua yang Anda butuhkan. Yaitu:

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

Meskipun saya tidak tahu seberapa banyak ini benar-benar membeli Anda. Overhead dari panggilan fungsi virtual adalah (tergantung kompiler, tentu saja):

  • Memori: Satu penunjuk fungsi per fungsi virtual
  • Runtime: Satu panggilan penunjuk fungsi

Sedangkan overhead polimorfisme statis CRTP adalah:

  • Memori: Duplikasi Basis per contoh templat
  • Runtime: Satu panggilan penunjuk fungsi + apa pun yang dilakukan static_cast
pengguna23167
sumber
4
Sebenarnya, duplikasi Base per instantiation template adalah ilusi karena (kecuali jika Anda masih memiliki vtable) compiler akan menggabungkan penyimpanan basis dan turunannya menjadi satu struct untuk Anda. Panggilan penunjuk fungsi juga dioptimalkan oleh kompiler (bagian static_cast).
Dean Michael
19
Omong-omong, analisis CRTP Anda salah. Seharusnya: Memori: Tidak ada, seperti kata Dean Michael. Runtime: Satu panggilan fungsi statis (lebih cepat), bukan virtual, yang merupakan inti dari latihan. static_cast tidak melakukan apa-apa, ini hanya memungkinkan kode untuk dikompilasi.
Frederik Slijkerman
2
Maksud saya adalah bahwa kode dasar akan diduplikasi di semua contoh template (penggabungan yang Anda bicarakan). Mirip memiliki template dengan hanya satu metode yang bergantung pada parameter template; segala sesuatu yang lain lebih baik di kelas dasar jika tidak maka ditarik ('digabung') beberapa kali.
pengguna23167
1
Setiap metode dalam basis akan dikompilasi lagi untuk setiap turunannya. Dalam kasus (diharapkan) di mana setiap metode yang dipakai berbeda (karena properti Derived berbeda), itu tidak dapat dihitung sebagai overhead. Tetapi hal itu dapat menyebabkan ukuran kode keseluruhan yang lebih besar, vs situasi di mana metode kompleks dalam kelas dasar (normal) memanggil metode virtual subkelas. Selain itu, jika Anda meletakkan metode utilitas di Base <Derived>, yang sebenarnya tidak bergantung sama sekali pada <Derived>, metode tersebut akan tetap dibuat instance-nya. Mungkin pengoptimalan global akan sedikit memperbaikinya.
Greggo
Panggilan yang melewati beberapa lapisan CRTP akan berkembang dalam memori selama kompilasi tetapi dapat dengan mudah berkontraksi melalui TCO dan inlining. CRTP sendiri sebenarnya bukan pelakunya, kan?
John P