One of my coworkers recently asked me to help him solve a problem he was having in code. He had a base class with several derived classes, and he wanted to add a static method to the base class, but have the derived classes determine the implementation. Basically, he wanted virtual method dispatch semantics, while still using static method dispatching. Obviously he couldn’t just declare a static virtual function!
While there’s certainly more than one way too skin a cat in C++, I felt that a good answer would be to use CRTP — the Curiously Recurring Template Pattern. Essentially, it’s a design pattern where the base class is a templated class, and the derived class is a template specialization, containing the derived class itself as the template parameter. For instance:
template< class Derived >
class Base {
};
class Derived1: public Base< Derived1 > {
};
class Derived2 : public Base< Derived2 > {
};
As you can see, each of the derived classes are a specialization of the Base class, but the template parameter is the derived class itself.
The problem that my coworker wanted to solve was: he wanted to call a method on the base class to determine whether an action was possible or not. However, the derived classes were ultimately responsible for determining whether the action was possible. Also, at the call site, there were no instances of the class available. Ultimately, he wanted the Base class to have a method like:
static bool CanPerformAction();
But he wanted the base classes to determine the outcome. When using the CRTP, the Base class has access to the derived type through the template parameter. Due to the way templates work in C++, you can use one to call a static method. So the trick here is to use the template parameter to call a static method on the base classes.
template< class Derived >
class Base {
public:
static bool CanPerformAction() {
return Derived::canPerformActionImpl();
}
};
class Derived1: public Base< Derived1 > {
friend class Base< Derived1 >;
private:
static bool canPerformActionImpl() {
return true;
}
};
class Derived2: public Base< Derived2 > {
friend class Base< Derived2 >;
private:
static bool canPerformActionImpl() {
return false;
}
};
You can then use the base class to perform static polymorphic function calls by using the template argument at the call site:
if (Base< Derived1 >::CanPerformAction()) {
}
What happens is that Base::CanPerformAction has a template parameter of Derived1. So the canPerformActionImpl call will resolve to Derived1::canPerformActionImpl, which is exactly what’s wanted, without requiring a class instance.
Of course, you don’t have to use CRTP with static methods. You can do the same thing with instances as well. For instance, let’s say Base had the following method (Note that SomeFunction is not a virtual method!):
void SomeFunction() {
// What goes here if I want to call someFunctionImpl on a derived class?
}
You can use CRTP in this case as well by using static_cast to cast the Base type to the derived type specified by the template parameter. Like this:
static_cast< Derived * >( this )->someFunctionImpl();
So even though there’s not a virtual function involved, you still get polymorphic dispatching, just without the overhead of vtables. This works because all of the dispatching can be determined at compile time instead of at runtime.
This isn’t a design pattern you’re likely to need very often, but you should be aware that it exists and is perfectly legal just so you don’t get surprised when you see it in the wild.
I still couldn’t understand the last section :
“Of course, you don’t have to use CRTP with static methods. You can do the same thing with instances as well……
might be you could post some working example with client code?
P.S : There is a typo 3rd last para , case -> cast.
@Beamon — thanks for letting me know about the typo, I’ve fixed it in the text.
As for example code, here’s a contrived example:
#include <stdio.h> template< class Derived > class Base { public: bool CanPerformAction() { return static_cast< Derived * >( this )->canPerformActionImpl(); } }; class Derived1: public Base< Derived1 > { friend class Base< Derived1 >; private: bool canPerformActionImpl() { return true; } }; class Derived2: public Base< Derived2 > { friend class Base< Derived2 >; private: bool canPerformActionImpl() { return false; } }; int main( void ) { Base< Derived1 > *b1 = new Derived1(); Base< Derived2 > *b2 = new Derived2(); ::printf( "b1 %s perform the action.\nb2 %s perform the action\n", b1->CanPerformAction() ? "can" : "cannot", b2->CanPerformAction() ? "can" : "cannot" ); return 0; }The difference is that you use static_cast to cast to the derived type to call the function. You won’t be able to use dynamic_cast because the compiler won’t be able to verify the relationship for all template instances, but static_cast gets the job done as well.
Thanks for reply, now understood it. Great article :)
Please delete my above post, it has so much typos
I was wondering if this code also solves the problem:
template
class Base {
public:
static bool CanPerformAction() {
return Derived::canPerformActionImpl();
}
};
class Derived1 {
public:
static bool canPerformActionImpl() {
return true;
}
};
class Derived2: public Base {
public:
static bool canPerformActionImpl() {
return false;
}
};
user code :
if (Base::CanPerformAction());
I understand that in your article we had to determine whether the derived has some interface and it’s implementation . But doesn’t this is also solves the problem if inheritance is not there ?
Also how do I define some beginner that what is static polymorphism in realm of c++? with some good example or analogy?
Thanks :)
@Beamon — I deleted your previous post for you. :-)
I think WP mangled your code because if the < and > in there, but I catch what you were after. Yes, that code does solve the problem but isn’t really static polymorphism. It’s more just relying on SFINAE (not that static polymorphism doesn’t do the same thing!).
There’s not a really good way to phrase this for beginners because it’s not really a beginner topic. The number of times you need to use static polymorphism should be fairly low. But a good example of when you’d want to use this is when the cost of true polymorphism is really high. Calling through a vtable isn’t expensive, but doing it millions of times can certainly add up. So you can use static polymorphism to achieve polymorphic behavior without the expense of virtual method calls.
Thank you for the clear explanation. I am currently facing the very same problem Beamon talked about. I used to have an interface with a pure virtual method which is of course resolved at runtime. I need to call this method very often so I thaught CRTP could be a benefit for me. The problem I ran into is that I lost my interface. In fact, the above example does not have an interface either. When you say
if (Base<Derived1>::CanPerformAction()) {
…
}
you do know the type in advance (yes, of course, because it’s about static polymorphism), but I wonder why I should use CRTP at all then. I could just leave it alone and call Derived1::canPerformActionImpl() directly. Could you provide a real-world example showing advantages from the client code side?
Best Regards
Daniel
@Daniel — but you can’t call Derived1::canPerformActionImpl from Base directly without CRTP. Because the function isn’t static, you have no way to call the instance method from Base. Because Base could be a Derived1 or a Derived2 (via inheritance), the only other way to resolve it would be via virtual method dispatch. By using CRTP, you remove the vtable access and indirect method call. Does that make sense?
As for a real-world examples, those are pretty varied. I most recently used CRTP as a way for a base class to clone a derived class without polymorphism. eg)
template
class base {
public:
_Derived *clone() const {
return new _Derived( *static_cast< const _Derived * >( this ) );
}
};
The design decision to use this over polymorphism is pretty weak, but I had other needs that I knew would crop up in the future where CRTP would help this class out so I didn’t feel too bad using it.
I know we use CRTP in clang for the recursive AST visitor set of classes. I would point you to that as a good usage of it, but that code is incredibly dense and difficult to read (not because of CRTP though).
Your desired usage seems like it could be perfectly valid as well — if there’s a performance concern with turning a class into a virtual one (or perhaps layout concerns, too). Though I would suggest you profile with polymorphism and then profile again with CRTP to see if the speed gains truly materialize or not.
Does that help?
Thank you for your reply. I have seen the example with a clone method before. But that one I saw used dynamic polymorphism together with CRTP. It was a non-templated base class with a pure virtual clone method, which was implemented by the CRTP base:
class Shape {
public:
virtual Shape* clone() const = 0;
};
template<typename Derived>
class TShape : public Shape {
public:
virtual Shape* clone() const { return new Derived(); }
};
class Sphere : public TShape {
// no need to implement clone here
};
It is nice to see that each derived class does not need to reimplement the clone method.
However, coming back to my problem, I guess I still “think” in dynamic polymorphism and expect things to work with CRTP as well – which is of course not true but limited with respect to compile time resolution.
I am curious about measuring time differences with a templated function like this:
template<typename T>
void myFunctionMakingALotOfObjectCalls(const CRTPBase<T> &myObject) {
for (…) {
myObject.myMethod(…); // compile time selected
}
}
compared to
void myOtherFunctionMakingALotOfObjectCalls(const Base &myObject) {
for (…) {
myObject.myMethod(…); // runtime selected
}
}
If I have very many different types, I guess the binary could be blown up with all these template instances, don’t you think?
Best regards
Daniel
@Daniel — There’s a part of me that thinks the different template instances won’t wind up being an issue. If you think about it, all of the instances would have to exist anyways because you’re using CRTP. It’s not like list, where you can have a list of ints, doubles, foos, etc. In this case, the only instantiations you would have are of derived classes, so the number of instantiations is fixed. What’s more, if you’re not storing the template type (simply using it as a type at compile time, not as runtime storage), then everything happens at compile time. The runtime layout of the objects should not be affected, so the only hit you should take (if any) would be at compile time, not binary size.
Hello Aaron,
I am extending functionality of a large code base application. Implementing CRTP pattern helped to some extend but I need something like this:
Derived1 s_pDerived; //<– My legacy pointer to my legacy Derived1 class (with mostly static members) that i converted to class Derived1: public Base with the implementation of CRTP. So:
int main( void ) {
Base *b1 = new Derived1();
Base *b2 = new Derived2();
//IS THERE A WAY TO DO THIS
if( condition )
s_pDerived = b1;
else
pDerived = b2;
pDerived->doTherest();
return 0;
}
correction – chars got cut off’.
Derived1 s_pDerived;
int main( void ) {
Base *b1 = new Derived1();
Base *b2 = new Derived2();
if( condition )
s_pDerived = b1;
else
s_pDerived = b2;
s_pDerived->CanPerformAction();
//or :
s_pDerived->canPerformActionImpl();
return 0;
}
@Sam — I don’t have a firm grasp on your situation, so my advice may be a bit off-base. ;-) But s_pDerived expects a Derived1, so there’s no way for you to assign b1 to it without casting, and no way for you to assign b2 to it at all. So I’m a bit confused. I think what you want is to be able to use either b1 or b2, and then call CanPerformAction generically off a Base *. But with CRTP, you’d have to specify what type goes to Base in order for the dispatch to work (either Base<Derived1> or Base<Derived2>). I think you may be forced into using polymorphism for your use case.
Thank you for the response – I was trying to get the best of both worlds.
Hi Aaron! Cool post. Very useful.
I might have misunderstood this part so feel free to just ignore me but:
When you said:
Ultimately, he wanted the Base class to have a method like:
static bool CanPerformAction();
But he wanted the base classes to determine the outcome.
Do you mean:
But he wanted the DERIVED classes to determine the outcome.
?
Regards,
piotr
A bit of both. He wanted the derived class methods to be called, but from the base class object pointer. I probably could have been a bit more clear. ;-)
Hello, thanks for your article it helped me understand this pattern, especially your sample that does not use statics :)
But I have one remark:
In all the code samples you “new” your objects but never “delete”, ok it’s a sample but I think it’s very important because when you will call delete on your object without a virtual destructor OR a cast to the derived class it will not delete the base class.
// note: calling delete on "b1" will not call the Derived1 destructor
Base *b1 = new Derived1();
So this remark bring me to a question:
If we want the derived class destructor to be called when deleting we have to make the base class destructor virtual, it then create a vtable, but will it slow down the others calls that are not virtual ? (noob in vtable here)
After this I see another thing that can be told on this pattern, there is a HUGE advantage of using it that I saw nowhere (I may be bad at searching on the web): you can have an interface with template methods:
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////////////////////////
// macros
//////////////////////////////////////////////////////////////////////////////////////////////////////////
#define crtp_cast(TIMPL) static_cast<TIMPL*>(this)
#define crtp_const_cast(TIMPL) static_cast<const TIMPL*>(this)
//////////////////////////////////////////////////////////////////////////////////////////////////////////
// TCrtp - keep the interface clean with definitions outside the class
//////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename TImpl> class TCrtp {
protected:
TCrtp() { std::cout << __FUNCTION__ << std::endl; }
public:
virtual ~TCrtp() { std::cout << __FUNCTION__ << std::endl; }
void Hello() const;
template<typename T> void HelloTemplate();
};
//--------------------------------------------------------------------------------------------------------
template<typename TImpl>
inline void TCrtp<TImpl>::Hello() const {
crtp_const_cast(TImpl)->HelloImpl();
}
template<typename TImpl>
template<typename T> inline void TCrtp<TImpl>::HelloTemplate() {
crtp_cast(TImpl)->template HelloTemplateImpl<T>();
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////
// TCrtpImpl
//////////////////////////////////////////////////////////////////////////////////////////////////////////
class TCrtpImpl : public TCrtp<TCrtpImpl> {
friend class TCrtp<TCrtpImpl>;
public:
TCrtpImpl() { std::cout << __FUNCTION__ << std::endl; }
~TCrtpImpl() { std::cout << __FUNCTION__ << std::endl; }
private:
void HelloImpl() const { std::cout << "Hello !" << std::endl; }
template<typename T> void HelloTemplateImpl() { std::cout << "HelloTemplate !" << std::endl; }
};
//////////////////////////////////////////////////////////////////////////////////////////////////////////
// main
//////////////////////////////////////////////////////////////////////////////////////////////////////////
int main(int, char **)
{
std::cout << "sizeof(TCrtp<TCrtpImpl>) = " << sizeof(TCrtp<TCrtpImpl>) << std::endl;
TCrtp<TCrtpImpl>* pCrtp = new TCrtpImpl;
pCrtp->Hello();
pCrtp->HelloTemplate<int>();
delete pCrtp;
return 0;
}
@Remi – Excellent point about the destructors not being called. One possible solution would be to use CRTP. ;-) Make the destructors protected so that you cannot call delete on the object from outside of the class. Then provide a Destroy function which uses CRTP to dispatch to the most-derived class, which then calls delete on *this.
One thing that should be a red flag though is assuming vtable dispatch is slow. It really isn’t that slow in practice, so if you are using CRTP for speed, you should be sure to measure first with virtual function dispatch. If you find that the dispatch itself is part of the hot path, then consider CRTP.
The advantage of dynamic polymorphism is allocating the memory space for the method at run time. Dynamic polymorphism is effective utilization of the resources, So Java always use dynamic polymorphism.
Hi,
The post was good. Got a good idea.
However, I am wondering why we need to say derived is a friend of the base;
more precisely this
friend class Base;
friend class Base;
why derived need to know about the base or simply what is the use case?
This allows the base class to access the private methods from the derived class. For instance, if you wanted to have a private virtual method, you could instead use CRTP and friendship to accomplish the same thing.
> the only hit you should take (if any) would be at compile time, not binary size.
Of course you’re duplicating code. The compiler has to duplicate the code of all the methods that are calling the overridden function, _directly or indirectly_. Think about it: how can you have a single version of `CanPerformAction()` doing two different things? You don’t, you have two versions of it. Same with every function calling `CanPerformAction()` and so on. Now imagine modelling a Widget hierarchy with CRTP, your exe would explode.
Coming *extremely* late to the party, like, several years, late, but…
What’s the point of having Base::CanPerformAction()?
If we have code dealing with just one type, Derived1, can’t we call Derived1::CanPerformAction() directly?
If we have code where the type is a template argument, we can call T::CanPerformAction(). We can even have a traits class that defined CanPerformAction() for those types that don’t have built-in method.
There’s lot of ways to implement this; I think when I was writing this code, the goal was to not expose public APIs on all of the derived classes, but instead only allow access through the base class. But this could be done in other ways (traits class and friendship comes to mind).