How to Turn a Hierarchy of Virtual Methods into a CRTP
After reading the series of posts on the CRTP, Fluent C++ reader Miguel Raggi reached out to me with the following email (reproduced with his permission):
Dear Jonathan Boccara,
[…] After reading the posts on the curiously recurring template pattern, I’m wondering how to (expressively) implement this with 3 or more classes.
Say, you have 3 classes, A, B, C, and that C is derived from B which is derived from A, and, say, both B and A used to be pure virtual classes.
How would I convert this to CRTP? I have something similar to this that is currently suffering from some performance problems that go away if I copy and paste the code.
struct A
{
virtual ~A() = default;
void bigAndSlow() const
{
// ...
helperfunction1(); //in very inner loop, so performance matters
helperfunction2(); // same
// ...
}
virtual void helperfunction1() const = 0;
virtual void helperfunction2() const = 0;
};
struct B : public A
{
void helperfunction1() const override;
};
struct C : public B
{
void helperfunction2() const override;
};
int main()
{
C c;
c.bigAndSlow();
}
I’ve done some tests with CRTP and it does speed things up considerably not having to do the virtual redirections, but I’m having trouble when you have 3 or more in a chain 🙂
I want to thank Miguel for this great question.
It’s a great question, as it aims at reducing the overload caused by something we don’t need: here Miguel doesn’t need the runtime polymorphism provided by virtual methods, and he doesn’t want to pay for its cost.
This is part of the Programmer’s Rights, protected by the Constitution of C++: no one shall pay for what they don’t use.
So let’s see how to implement static polymorphism in the above code. This question can be split into two parts:
- How to replace virtual methods by a CRTP,
- How to make a CRTP inherit from another CRTP
From virtual methods to CRTP
Let’s simplify the case of Miguel for the moment to keep only two levels in the hierarchy, struct A and struct B (we’ll get back to the deeper hierarchy in a moment):
struct A
{
virtual ~A() = default;
void bigAndSlow() const
{
helperfunction1();
}
virtual void helperfunction1() const = 0;
};
struct B : public A
{
void helperfunction1() const override{}
};
And the client code looks like this:
int main()
{
B b;
b.bigAndSlow();
}
The interface that the client code is invoking is the interface of A. And to be implemented, A needs some code behind the method helperFunction1, which is implemented in B here.
We can also have some polymorphic calling code, independent from B:
void f(A const& a)
{
a.bigAndSlow(); // ends up in the code of B::helperFunction1 even though B doesn't appear here
}
The parallel with the CRTP goes like this: B has the functionality helperFunction1, and this functionality can be extended. This is what the CRTP is made for: adding functionality to a class.
The extension of functionality consists in a method that uses helperFunction1. In our starting example, that method was the one called bigAndSlow.
Now here is the resulting code using CRTP:
template<typename Derived>
struct A
{
void bigAndSlow() const
{
return static_cast<Derived const&>(*this).helperfunction1();
}
};
struct B : public A<B>
{
void helperfunction1() const;
};
And to hide the ugly static_cast and to make the word “CRTP” appear in the interface, we can use the crtp helper:
template<typename Derived>
struct A : crtp<Derived, A>
{
void bigAndSlow() const
{
return this->underlying().helperfunction1();
}
};
Our calling code stays the same:
int main()
{
B b;
b.bigAndSlow();
}
And this code also ends up calling helperFunction1 in B. But the virtual function mechanism, that incurs a certain cost (the size of a virtual pointer and the indirection of a virtual table) is gone.
We could also have some polymorphic code independent from B:
template<typename T>
void f(A<T> const& a)
{
a.bigAndSlow(); // ends up in the code of B::helperFunction1 even though B doesn't appear here
}
And, just like with virtual functions, we can reuse A with other classes offering a helperFunction1 methods, to augment their functionalities.
Inheritance without a virtual destructor?
As you may have noticed, the virtual destructor is gone after this transformation. But is it OK? Is it safe to inherit from a class that does not have a virtual destructor?
Let’s see. Writing this:
class A
{
};
class B : public A
{
};
is totally valid and legal C++.
The problems come when you delete a pointer to a base class that points to an object of a derived class:
B* b = new B; A* pa = b; delete pa; // undefinded behaviour
Indeed, the third line calls the destructor on A, which is not virtual so it does not redirect to the code of the destructor of B. The destructor of B never gets called. This is undefined behaviour.
Whereas with a virtual destructor, the call to the destructor on A is resolved by calling the destructor of B (just like when calling any other virtual method on A that is overriden in B). The destructor of B does its stuff and then calls the destructor of A (similarly to constructors of derived classes that call the constructor of their base class).
In our case, the class is not designed to be used with dynamic polymorphism (see below) and pointers to base class. So I haven’t left the virtual destructor.
You could add it though, the price will only be an increased size of the object (so that the compiler can fit in a virtual pointer to redirect calls to the destructor), and arguably it would be less clear that this class is not meant to be used with dynamic polymorphism.
Why pay for virtual functions at all?
It seems that the code using CRTP does just the same thing as the code using virtual methods, but it does not incur the cost of virtual methods. Is this to say that virtual methods are useless?
In this case, yes.
But in general, no.
Virtual methods are just more powerful than the CRTP, and therefore they cost more.
They’re more powerful in the sense that, unlike the CRTP, they are able to discover the implementation of an interface at each runtime call. This is dynamic polymorphism.
For example, if you hold a pointer to an interface A that has virtual methods:
std::unique_ptr<A> pa;
You can use the polymorphic function f:
void f(A const& a)
{
a.bigAndSlow();
}
on pa, even if the implementation of the interface changes at runtime.
To illustrate, let’s assume that we have another class B2 that inherits from A:
struct B2 : public A
{
void helperfunction1() const override;
};
With dynamic polymorphism we can write the following code:
std::unique_ptr<A> pa = std::make_unique<B>(); // pa is a B f(*pa); // calls B::helperFunction1 pa = std::make_unique<B2>(); // pa is now a B2 f(*pa); // calls B2::helperFunction1
The first call to f ends up calling the code of the class B, and the second one calls the code of the class B2.
This is an incredible flexibility. But it comes at a cost.
But if you don’t need it, you don’t have to pay for it. If you don’t need the power of this dynamic polymorphism with virtual methods you can use static polymorphism with templates and (for example) CRTP.
A deeper hierarchy of CRTPs
Now that we have our CRTP with one layer of inheritance, we can tackle Miguel’s case and replace by a CRTP the following virtual methods:
struct A
{
virtual ~A() = default;
void bigAndSlow() const
{
helperfunction1();
helperfunction2();
}
virtual void helperfunction1() const = 0;
virtual void helperfunction2() const = 0;
};
struct B : public A
{
void helperfunction1() const override;
};
struct C : public B
{
void helperfunction2() const override;
};
Note that B overrides only one virtual method, helperFunction1, and leaves helperFunction2 to be implemented by another class deeper down the hierarchy. Here, that class is C.
So to implement the CRTP in this hierarchy, we also need B to be a CRTP base class:
template<typename Derived>
struct A
{
void bigAndSlow() const
{
static_cast<Derived const&>(*this).helperfunction1();
static_cast<Derived const&>(*this).helperfunction2();
}
};
template<typename Derived>
struct B : public A<B<Derived>>
{
void helperfunction1() const;
void helperfunction2() const
{
return static_cast<Derived const&>(*this).helperfunction2();
};
};
struct C : public B<C>
{
void helperfunction2() const;
};
(Note that we could use the crtp helper in only one of A or B. Indeed, if both inherit from crtp that defines the method underlying then this method becomes ambiguous for B)
EDIT: As pointed out by Simon Nivault in the comments sections, we can simplify this code. Indeed, no need for B to inherit from A<B<Derived>>: inheriting from A<Derived> is enough, because it makes A manipulate C, which also exposes the methods of B since it is is base class. This has the advantage of not needing any implementation of helperFunction2 in B:
template<typename Derived>
struct A
{
void bigAndSlow() const
{
static_cast<Derived const&>(*this).helperfunction1();
static_cast<Derived const&>(*this).helperfunction2();
}
};
template<typename Derived>
struct B : public A<Derived>
{
void helperfunction1() const;
};
struct C : public B<C>
{
void helperfunction2() const;
};
So this is a hierarchy of virtual methods turned into a hierarchy of CRTP!
Let me know how I can help
If, like Miguel, you have a question about a topic we tackled on Fluent C++, or if you have a question related to expressive code in C++, you can write me at jonathan@fluentcpp.com. I’m always happy to hear from you.
I don’t promise to have the answers, but I’ll do my best to answer your question, and that could be by writing an article out of it!
Related articles:
- The Curiously Recurring Template Pattern (CRTP)
- What the Curiously Recurring Template Pattern can bring to your code
- An Implementation Helper For The Curiously Recurring Template Pattern
Share this post!
