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

Dupleix

When you take a Base instance by value, you suffer from object slicing. Pass it by reference or by pointer if you want polymorphic behavior (whether you use static or dynamic polymorphism). – Ronironica

Doesn't work for me, I get variable or field ‘func’ declared void void func( Base& x)... – Dupleix

@Dupleix Base is a template. You cannot use just Base &, you have to provide a template argument: Base<Something> &. Which means func will have to be a template too. – Aminaamine

That's exactly my point... if I have to use templates for my functions or define them explicitly for Derived, why bother with CRTP...? – Dupleix

@Dupleix To re-use the implementation in Base. – Aminaamine

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 :-).

Humpage

There are multiple uses of CRTP. This is one of them, but the one the asker is talking about is also a valid one. – Unasked

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.

Aminaamine

This is obviously a great use of CRTP, but my problem with it and generally the description of CRTP as "static polymorphism" is that CRTP has nothing directly to do with polymorphism. It's a tool to help with implementation. – Humpage

@NirFriedman It does have to do with polymorphism, but compile-time polymorphism. Which can only be realised through templates. I'll add a point about this to the answer. – Aminaamine

I understand what compile time polymorphism is. And yes, there is a templated class in your code. But CRTP is not about a function using a type purely according to its interface, which is what polymorphism is. Base is simply a tool to help implement Derived or similar classes. If it's about helping with implementation, it's not really about polymorphism, which is only about interface. – Humpage

@NirFriedman I meant "realised through templates on the caller side." Answer updated. – Aminaamine

Of course there is no point in doing this if you have only one derived class. Polymorphism (note: Poly = many) comes into play when you have several implementations, hidden behind one common interface. Imagine you have serveral implementations, e.g. class Derived1 : Base<Derived1> and class Derived2 : Base<Derived2>. You then add them to a vector<Base *> and iterate over all elements, calling Base::algorithm(). This is polymorphism! – Henna

This is a great answer, and it actually clarifies a misconception I had: I used to think that classes are derived by "copying" methods from their base, unless there's an overwrite, so that methods in derived classes would be called if they exist and higher-up methods would only be used as a "fallback" if Derived does not provide its own version. If I understand you correctly, CRTP achieves this rather intuitive behavior? – Dupleix

@Dupleix Member functions are never "copied" to derived classes in C++ (they are a normal part of them). Unless virtual is involved, only the static type of this determines which function will be called on the object. Which is why in the non-CRTP case, the call epilogue() in Base calls Base::epilogue(). Note that if, in the CRTP case, you don't include the self() call, it will behave just like the regular case and base on the static type of this, which is Base<Derived> and not Derived. – Aminaamine

@Henna This vector<Base *> thing doesn't work for me at all, at least not with the implementation above. – Dupleix

@Henna That cannot work. Don't forget that Base is still a template. There's no such thing as Base*, Base is not a class! – Aminaamine

@Angew: True :) I was thinking to fast. Base may need to implement an interface IBase that can then be added to a vector<IBase*>. But then you have dynamic polymorphism again. Sorry for the confusion. – Henna

@Henna It is not polymorphism. It is code reuse promoted by Base aiding in the implementation of both Derived1 and Derived2. And your example is totally incorrect for two separate reasons (edit: I've see you've already figured that out with help from Angew). – Humpage

When you look at Base and Derived, the question is: who is the client? If Derived is a client of Base, Derived uses Base to aid in its implementation. This is CRTP as a static mixin. This is, in my experience, by far more common. The other way to look at it is that Base is a static polymorphic client of Derived. But if that's the case, Base is almost always better off having derived as a member! CRTP only makes sense when Derived has a lot of interface, including stuff that Base does not care about. In which case, we are clearly in the first scenario. So: not polymoprhism! – Humpage

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

Unasked