• 1 How CRTP works
• 2 CRTP is not “template programming magic”
• 3 We already have static polymorphism
• 4 We already have static implementation inheritance…Except
• 5 Appendix-Dynamic Dispatch

On my first encounter, the Curiously Recurring Template Pattern seemed like magic to me. Apparently, by writing static_cast<T*>(this)->func(), we now have “static polymorphism/inheritance”. It wasn’t until a few months and some c++ learning resources later, that I was finally able to understand CRTP. In this blogpost, I will talk about CRTP from more of a code generation point of view, and hopefully by then end convince you that “static polymorphism/inheritance” is a misleading description of this pattern.

1 How CRTP works

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

template <typename T>
class BaseT{
public:
    void func(){
        // Note: the use of pointers instead of references is for pedagogy reasons
        T* derived = static_cast<T*>(this);
        // pre function call code
        derived->do_func1();
        derived->do_func2();
        // post function call code
    }
private:
    void do_func1();
    void do_func2();
};

class Derived: public BaseT<Derived>{
private:
    void do_func1(){};
    void do_func2(){};
};

Here is the general form of the pattern, with some modifications that will come to light by the end of this article. Let us now walk through what foo translates to for this Derived class. When the compiler processes¹ this function, whose func1 does it insert, BaseT<Derived> or Derived?

1
2
3
4
5
6
7
8
9

// rough translation
void func(BaseT<Derived>* this){
    // From now on, generate code as if we have a pointer to Derived(whichc we do)
    Derived* derived = static_cast<Derived*>(this);
    // pre function call code
    Derived::do_func1(derived);
    Derived::do_func2(derived);
    // post function call code
}

The way the C++ object model works is that when there are no virtual functions, the compiler inserts the function corresponding with the whatever the compile time type CURRENTLY is of the object who calls that method ²

Now, that was a bit of a mouthful. Let us walk through another example of using static_cast to help the compiler with name resolution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

struct Parent1{
    void f(){cout << "1" << endl;}
};
struct Parent2{
    void f(){cout << "2" << endl;}
};
struct Child:public Parent1,public Parent2{
    void g(){
        Parent2* casted = static_cast<Parent2*>(this);
        casted->f();
        // Parent2::f(); // can also be done with explicit scoping
    }
};

Without the static_cast, the compiler will throw an error, saying f is found in multiple base classes. But by using it, the compiler will no longer look in Child or Parent1 during name resolution. One can also use explicit scoping to achieve this, but the difference is that static_cast will walk the class hierarchy until it finds a f . Furthermore explicit scoping requires retyping Parent1 on every subsequent member function call.

I find this explanation in terms of “manipulating the name resolution path” to be much clearer than saying “the base class can now access the derived class” or “we inject the derived class into the base” as I have found in other blogs. For all intensive purposes, the compiler thinks it has a Derived object now. And in fact, it is the other way around, that the derived class has access to the base. Which isn’t that suprising, as that’s basically the definition of how classes work.

So to repeat, after the static_cast, there is no Base anymore. With the fundamental understanding of CRTP down, let us now dispel some myths/confusion around its usage.

2 CRTP is not “template programming magic”

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

struct Widget{
    void update(){cout << "hi" << endl;};
};
template<typename T>
void generic_function(void* x){
    static_cast<T*>(this)->update();
}
// vs
template<typename T>
void generic_function2(T* x){
    x->update();
}
int main(void){
    Widget* x = new Widget;
    generic_function<Widget>((void*)x);
    generic_function2(x);
}

Consider the above example. They both will print “hi”. The difference is just that we gave the first one a bad input argument, and so we had to “compensate” via the static_cast. So if you understand static_cast and basic generic programming³ there is no reason you shouldn’t understand CRTP.

3 We already have static polymorphism

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

struct Object1{
public:
    void interface(){
        // pre function call code
        impl();
        // post function call code
    }
private:
   void impl(){cout << "a" << endl;}
};

struct Object2{
public:
    void interface(){
        // Notice we call whatever functions we want here, unlike CRTP
        impl_a();
        impl_b();
    }
private:
    void impl_a(){cout << "b1" << endl;}
    void impl_b(){cout << "b2" << endl;}
};
template<typename T>
struct BaseT{
    void interface(){
        // pre function call code
        static_cast<T*>(this)->impl();
        // post function call code
    }
};
struct Derived: public BaseT<Derived>{
    void impl(){cout << "c" << endl;}
};

template<typename T>
void call_a_function(T& x){
    x.interface();
}
int main(void){
    Object1 a;
    Object2 b;
    Derived c;
    call_a_function(a);// They all work!
    call_a_function(b);
    call_a_function(c);
}

As we can see, CRTP is not necessary here(and actually is not even a “true” interface in some sense, as it has already predetermined the implementation). What is really giving us polymorphism is generic programming. Furthermore, inheriting from a CRTP doesn’t actually guarantee the Derived class will satisfy the interface. Consider this example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

template<typename T>
struct BaseT{
    void f(){
        static_cast<T*>(this)->not_implemented();
    }
};

struct Derived:public BaseT<Derived>{
};

struct B{
    virtual void f() = 0;
};
struct D:public B{
};
int main(void){
    Derived a;
    D b;
}

Comment out the D b; initialization in main, and the code compiles. With it, we get an error. Why? Because abstract base classes force their inheritors to implement the interface, even if the function never gets called. There are no such guarantees, however, with CRTP.(If we do call Derived’s f function, we will get an error…but we basically get the same error had f been a templated free function)⁴

4 We already have static implementation inheritance…Except

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

struct EngineMixin{
    void do_work();
};
struct SpecificEngine:public EngineMixin{
};

template<typename T>
struct BaseT{
    void do_work();
};
struct Derived:public BaseT<Derived>{
};
int main(void){
    SpecificEngine e;
    Derived d;
    e.work(); //They both static dispatch to the same thing!
    d.work();
}

Let us now consider the other aspect of inheritance, inheritance of functionality. In the above example, SpecificEngine and Derived will both resolve the function call at compile time, as there are no virtual functions + pointers here. I would like to emphasis this, as I feel some people may think that just because there is a “static_cast” in CRTP, it is somehow related to the function call being static too. As I have explained above, static_cast controls what name we dispatch to, and not the type of the dispatch

So given all of this, when exactly should we use CRTP? Let us reconsider the initial example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class BaseT{
public:
    void func(){
        // pre function call code
        derived->do_func1();
        derived->do_func2();
        // post function call code
    }
private:
    virtual void do_func1();
    virtual void do_func2();
};

class Derived: public BaseT<Derived>{
private:
    void do_func1(){};
    void do_func2(){};
};

Now, if you look closely, I haven’t actually reproduced the initial example! Instead, by removing the static_cast and adding virtual to do_func1/do_func2, I have actually introduced another pattern, known as the “NVI idiom” or Facade Design Pattern. The purpose of this pattern is the Base class provides most of the code scaffolding/wiring/or public interface, and the Derived class simply needs to “fill in the blanks”. So if you have been wondering why I have been writing “pre function call” comments throughout this post, it is because I want to encourage you to think of CRTP as a “static NVI idiom”, and not “static inheritance”. If all the Base class does is forward to the implementation, one has to wonder “What was the point?”

As long as you keep this in mind, CRTP should be hard to abuse and then subsequently “shoot yourself in the foot” with it.

5 Appendix-Dynamic Dispatch

(Note: This section may or may not be helpful in understanding how CRTP works. )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Animal{
    virtual void walk();
    virtual void eat()  ;
    int data;
};
// is roughly
struct Animal{
    void* _vtable;
    int data;
};
void update(Animal*){};

When you declare a virtual function inside the `Animal` class in C++, the compile will add a pointer inside every created object that points to the same location: the start of `Animal` vtable. In this region of memory, every 8 byte interval(the size of a pointer) will correspond with the address of a virtual function for this object. When virtual functions get called, the following translation happens

1
2
3
4
5

// Note: the use of raw pointers is for pedagogy reasons
Animal* animal = new Animal;
animal->eat();
// is roughly
(*(*animal._vtable+1byte))(animal); // 1byte offset to get to 2nd virtual function

Note the w is a pointer. Had we declare it as variable, static dispatch would have to happen, even if the function was declared virtual. I won’t go completely into detail as to why here, but let’s just say that given animal is declared on the stack, there is no way to “lie” and say it is anything but an Animal

Finally, the way that this indirection allows for polymorphism is that the dynamic dispatch translation is the same regardless of what the Animal pointer actually points to

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

struct Dog:public Animal{
    virtual eat(){
        //something different
    }
}

Animal* dog = new Dog;
dog->eat();
// is roughly
(*(*dog._vtable+1byte))(dog);

// so basically the same as
// (*(*animal._vtable+1byte))(animal);

The difference is that the vtable now holds different information. Namely *dog._vtable+1byte now stores the location of Dog::eat() rather than Animal::eat()