C++: CRTP to avoid dynamic polymorphism

Question

How can I use CRTP in C++ to avoid the overhead of virtual member functions?

Answer 1

I had to look up CRTP. Having done that, however, I found some stuff about Static Polymorphism. I suspect that this is the answer to your question.

It turns out that ATL uses this pattern quite extensively.

Answer 2

This Wikipedia answer has all you need. Namely:

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

Although I don't know how much this actually buys you. The overhead of a virtual function call is (compiler dependent, of course):

• Memory: One function pointer per virtual function
• Runtime: One function pointer call

While the overhead of CRTP static polymorphism is:

• Memory: Duplication of Base per template instantiation
• Runtime: One function pointer call + whatever static_cast is doing

Answer 3

By means of curiously recurring template pattern you can implement the static polymorphism. You can find an example on wikipedia.

Answer 4

I've been looking for decent discussions of CRTP myself. Todd Veldhuizen's Techniques for Scientific C++ is a great resource for this (1.3) and many other advanced techniques like expression templates.

Also, I found that you could read most of Coplien's original C++ Gems article at Google books. Maybe that's still the case.

Answer 5

There are two ways.

The first one is by specifying the interface statically for the structure of types:

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

The second one is by avoiding the use of the reference-to-base or pointer-to-base idiom and do the wiring at compile-time. Using the above definition, you can have template functions that look like these:

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

So combining the structure/interface definition and the compile-time type deduction in your functions allows you to do static dispatch instead of dynamic dispatch. This is the essence of static polymorphism.

Answer 6

Hi,

With the snippet of ppinsider, I don' t get how do you do a pointer to the base without specifying the template argument?

Base *poly = new Derived;
poly->interface();

Didn' t found sample on net, most of snippets just post the crtp trick, but no instantiation of a Derived contained in a Base*.

Thanks in advance.