Confusion about CRTP static polymorphism

Question

I'm trying to wrap my head around the CRTP. There are some good sources around, including this forum, but I think I have some confusion about the basics of static polymorphism. Looking at the following Wikipedia entry:

template <class T> 
struct Base
{
    void implementation()
    {
        // ...
        static_cast<T*>(this)->implementation();
        // ...
    }

    static void static_func()
    {
        // ...
        T::static_sub_func();
        // ...
    }
};

struct Derived : public Base<Derived>
{
    void implementation();
    static void static_sub_func();
};

I understand that this helps me to have different implementation() variants in derived classes, kinda like a compile-time virtual function. However, my confusion is that I think I cannot have functions like

void func(Base x){
    x.implementation();
}

as I would with normal inheritance and virtual functions, due to Base being templated, but I would have to either specify

func(Derived x)

or use

template<class T> 
func(T x)

So what does CRTP actually buy me in this context, as opposed to simply shadowing/implementing the method straightforward in Derived::Base?

struct Base
{
    void implementation();
};

struct Derived : public Base
{
    void implementation();
    static void static_sub_func();
};

Answer 1

The thing is that the description of CRTP as "static polymorphism" is not really helpful or accurate, with regards to what CRPT is actually used for. Polymorphism is really just about having different types that fulfill the same interface or contract; how those different types implement that interface is orthogonal to polymorphism. Dynamic polymorphism looks like this:

void foo(Animal& a) { a.make_sound();  } //  could bark, meow, etc

Where Animal is a base class providing a virtual make_sound method, that Dog, Cat, etc, override. Here is static polymorphism:

template <class T>
void foo(T& a) { a.make_sound(); }

And that's it. You can call the static version of foo on any type that happens to define a make_sound method, without inheriting from a base class. And the call will be resolved at compile time (i.e. you won't pay for a vtable call).

So where does CRTP fit in? CRTP is really not about interface at all, so it's not about polymorphism. CRTP is about letting you implement things more easily. What makes CRTP magical is that it can inject things directly into the interface of a type, with full knowledge of everything the derived type provides. A simple example might be:

template <class T>
struct MakeDouble {
    T double() {
        auto& me = static_cast<T&>(*this);
        return me + me;
};

Now any class that defines an addition operator, can also be given a double method:

class Matrix : MakeDouble<Matrix> ...

Matrix m;
auto m2 = m.double();

CRTP is all about aiding in implementation, not interface. So don't get too hung up about the fact that it's often referred to as "static polymorphism". If you want the real canonical example on what CRTP can be used for, consider Chapter 1 of Andrei Alexandrescu's Modern C++ design. Though, take it slow :-).

Answer 2

The advantages of CRTP only become obvious when more than one function is involved. Consider this code (with no CRTP):

struct Base
{
  int algorithm(int x)
  {
    prologue();
    if (x > 42)
      x = downsize(x);
    x = crunch(x);
    epilogue();
    return x;
  }

  void prologue()
  {}

  int downsize(int x)
  { return x % 42; }

  int crunch(int x)
  { return -x; }

  void epilogue()
  {}
};

struct Derived : Base
{
  int downsize(int x)
  {
    while (x > 42) x /= 2;
    return x;
  }

  void epilogue()
  { std::cout << "We're done!\n"; }
};

int main()
{
  Derived d;
  std::cout << d.algorithm(420);
}

This outputs:

0

[Live example]

Due to the static nature of C++'s type system, the call to d.algorithm calls all functions from Base. The attempted overrides in Derived are not called.

This changes when CRTP is used:

template <class Self>
struct Base
{
  Self& self() { return static_cast<Self&>(*this); }

  int algorithm(int x)
  {
    self().prologue();
    if (x > 42)
      x = self().downsize(x);
    x = self().crunch(x);
    self().epilogue();
    return x;
  }

  void prologue()
  {}

  int downsize(int x)
  { return x % 42; }

  int crunch(int x)
  { return -x; }

  void epilogue()
  {}
};

struct Derived : Base<Derived>
{
  int downsize(int x)
  {
    while (x > 42) x /= 2;
    return x;
  }

  void epilogue()
  { std::cout << "We're done!\n"; }
};

int main()
{
  Derived d;
  std::cout << d.algorithm(420);
}

Output:

We're done!
-26

[Live example]

This way, the implementation in Base will actually call into Derived whenever Derived provides an "override."

This would even be visible in your original code: if Base wasn't a CRTP class, its call to static_sub_func would never resolve to Derived::static_sub_func.

---

As to what the advantages of CRTP over other approaches are:

• CRTP versus virtual functions:

  CRTP is a compile-time construct, meaning there's no runtime overhead associated. Calling a virtual function through a base class reference (usually) requires a call through a pointer to function and thus incurs indirection costs and prevents inlining.

• CRTP versus simply implementing everything in Derived:

  Base class code reuse.

Of course, CRTP is a purely compile-time construct. To achieve the compile-time polymorphism it allows, you have to use a compile-time polymorphic construct: templates. There are two ways you can do this:

template <class T>
int foo(Base<T> &actor)
{
  return actor.algorithm(314);
}

template <class T>
int bar(T &actor)
{
  return actor.algorithm(314);
}

The former corresponds more closely to runtime polymorphism and offers better type safety, the latter is more duck-typing based.

Answer 3

You are correct that neither

void func(Base x);

or

void func(Derived x);

gives you static polymorphism. The first doesn’t compile, because Base isn’t a type, and the second isn’t polymorphic.

However, suppose you have two derived classes, Derived1 and Derived2. Then, what you could do is make func itself a template.

template <typename T>
void func(Base<T>& x);

This can then be called with any type which derives from Base, and it will use the static type of whatever parameter is passed to decide which function to call.

---

This is just one of the uses of CRTP, and if I were to guess I would say the less-common one. You can also use it as Nir Friedman suggests in another answer, which does not have anything to do with static polymorphism.

Both uses are discussed very well here