In C++, compared to final or not virtual function, what is the advantage of CRTP?

Question

I'm new to learning modern C++ programming. I have read many blogs and questions but haven't found the answer of this question. In C++, compared to final or not virtual function, what is the advantage of CRTP?

When people talk about CRTP, some code like these are often shown as an example:

template<typename Derived>
class Base {
public:
    void interface() {
        static_cast<Derived*>(this)->implementation();
    }

    void foo() { ... }
};

class Derived : public Base<Derived> {
public:
    void implementation() { ... }
};

int main() {
    Derived d;
    d.interface();
    d.foo();
}

An object d of class Derived can use the function foo from Base, and Derived rewrites the function interface. They don't search vtable because these are not virtual function.

But I think that, when I use inherit, I can achieve the same effect.

class Base1 {
public:
    virtual void interface() = 0;

    void foo() { ... }
};

class Derived1 : public Base1 {
public:
    void interface() final { ... }
};

int main() {
    Derived1 *d1 = new Derived1();
    d1->interface();
    d1->foo();
}

In those code, when d1 call function interface(), although the function is a virtual function, compiler can recognize that it is actually the function of class Derived1 because I mark final. And d1 can also call function foo from Base1 without searching vtable because foo is not virtual function.

But in the case, I have not used polymorphism. But Base is a template class. It is Base<Derived>. We actually has the information that it is Derived and we can't use a common pointer Base* which point to Base<A> and Base<B> at same time. I think compare it and Base* in inheritance is not fair. It should be compared to Derived in inheritance. What I mean is, when we can get type Base<Derived>, we can also get type Derived*.

Then, in my opinion, the difference between these two ways to rewrite and share common code is only that inherit will add a vtable at the header of derived class. So these two ways may have some differences in memory usage and running speed due to the different memory sizes. These memory are used to help us point to the subclass through the parent class pointer and perform virtual function calls when we need it. If there are no such situation in code, we choose CRTP, otherwise inherit.

Is my idea correct? What other things can CRTP do that inheritance cannot do?

Answer 1

CRTP is more useful for code reuse than polymorphism. So it's comparing two qualitatively different goals.

For example, take from the sibling answer:

template <typename T>
void foo(Base<T>& b);

Whether we write Base<T> or T, we still have a concrete dependence on the derived class. There is not meaningful polymorphism here, aside from the static polymorphism to which CRTP isn't adding utility.

This is similarly misleading:

In those code, when d1 call function interface(), although the function is a virtual function, compiler can recognize that it is actually the function of class Derived1 because I mark final

We have the static type, so whether we call the function on Base<Derived> or Derived, it isn't meaningfully different. That said, the optimization mentioned is an optimization and is definitely not guaranteed.

But where CRTP does help is by re-using code. Let's say you have two related functions. foo() and bar(). foo() should always be 1 + bar(). CRTP lets you do this:

template <typename T>
class Base {
public:
    void foo() {
        return 1 + static_cast<T*>(this)->bar();
    }
};

There are many times a small implementation can be the backing for a larger interface. Consider iterators. Consider pointers (operator* and operator->).

It is worthwhile to consider the newer way to write CRTP:

class Base {
public:
    template <typename Self>
    void foo(this Self& self) {
        return 1 + self.bar();
    }
};

It becomes clear, CRTP is really just a way to write a parametrically polymorphic function involving the object. It provides a new interface based on an existing smaller interface.

Answer 2

As mentioned in comments, your comparison isn't quite fair, because you are not actually making use of polymorphism. Neither of compile time nor of runtime polymorphism. Once you do, the difference becomes apparent.

Virtual dispatch, runtime polymorphism:

void foo(Base1& b) { 
      b.interface();
}

Only at runtime it is decided what method is actually called. This prevents the optimizer to inline the call. That the method is final in Derived does not help here, because foo uses the interface not the concrete type.

Now compare that to CRTP, compile time polymorphism

 template <typename T>
 void foo(Base<T>& b) {
     b.interface();
 }

In any instantiation of foo, there is no doubt which function is called. This has certain positive implications. For example the call can be inlined.

Answer 3

Wikipedia lists a number of cases where CRTP allows for much cleaner implementations than virtual inheritance (see e.g. polymorphic chaining or polymorphic copy construction).

But even apart from such cases, with runtime polymorphism you are simply paying for features you (apparently) don't intend to use. The main benefit of runtime polymorphism is the ability to do something like this (as has been pointed out in other answers):

void foo(Base1& b) { 
  b.interface();
}

That is, you can call interface() on a base class reference, without knowing which class exactly it is referring to. Even if you never intend to do this, the compiler has to make sure it's possible.

One consequence of this is that every instance of Base1 and of every class derived from it needs to contain a vtable pointer, increasing its size. In many cases this is totally negligible, but imagine for example a family of iterators (which, in most cases, should have the size of a single pointer): You have several base classes implementing different functionalities and you now mix and match them to create iterators suited for different purposes. With virtual inheritance, each iterator will end up with one extra pointer per base class, making it several times the size it should have.

There is also the possibility of performance hits due to indirect calls to virtual functions, but, as you have pointed out, the compiler might, in many cases, be able to optimize that out.

Other reasons to use CRTP are more philosophical: One basic principle of strongly typed languages is to prevent misuse by making it impossible. If you don't intend for Base and Derived to ever be used polymorphically at runtime (for logical or other reasons), you can use CRTP to make sure no-one ever will.