📅 2015-Jul-09 ⬩ ✍️ Ashwin Nanjappa ⬩ 🏷️ cpp, crtp, dynamic polymorphism, static polymorphism, template ⬩ 📚 Archive
Dynamic polymorphism (or runtime polymorphism) using virtual functions in C++ is a great savior. However, a tiny fraction of applications might be affected by its disadvantages: an extra function call overhead and space occupied by a vtable pointer in every object.
For most of these applications, there might be no better choice than virtual functions, they will need to grin and bear it. But among these applications, there might be a further tiny fraction whose problem just might be elegantly solved using a static polymorphism technique called Curiously Recurring Template Pattern (CRTP). It is also called the Barton-Nackman trick, since this duo introduced it for the first time in their 1997 book Scientific and Engineering C++ (Section 12.6: Restricted Template Expansion).
The web is full of articles (like this) and code explaining CRTP. While I could understand how the code worked, none of them explained what problem this trick was solving. In other words, I did not see the motivation for using this trick.
It is only when I went back to the source, i.e., the Barton-Nackman book that I hit pay dirt. They actually describe a contrived problem which this trick solves. However, their code examples were still quite obscure, so to understand them I created a simpler example, which I describe below.
Creature
base class and thousands of species classes derived from it. As an example, Bird
and Fish
are both derived from it.struct Creature {};
struct Bird: Creature {};
struct Fish: Creature {};
Bird
and Fish
have some common features (say eye_num
) and some specialized features (say wing_num
for Bird
and fin_num
for Fish
). If this were not the case, there would be no need to arrange them in a hierarchy.==
) and inequality (!=
) comparison methods to compare any two objects of same species. That is to compare two Bird
objects or two Fish
objects. Also assume that inequality in this case is nothing but the negation of equality, but we want this inequality method anyway to write elegant code. We want to have the most maintainable and least amount of code that can achieve this:
Bird b1, b2, b3;// ...
if (b1 == b2) // Do something
if (b2 != b3) // Do something
Let us see different ways this can be solved elegantly:
==
method in Creature
and override it in all the derived classes. Create !=
method only in Creature
that calls the equality method. For N
derived classes, this would entail writing N
equality methods and 1
inequality method. This is the ideal solution. However, we started this article with the assumption that its performance is not optimal for our application.==
and !=
operator methods in Creature
. This means we write just 1
equality and 1
inequality method. Problem: This will take Creature
as input, so features specific to Bird
or Fish
cannot be compared. This is useless because any reasonable equality test should be type dependent.==
operator methods in both Bird
and Fish
. Problem is that you will now need to create the non-virtual !=
method also in all the derived classes. This means writing N
equality and N
inequality methods. Too much work!N + 1
equality and 1
inequality methods. This is optimal. The peculiar feature you can use to identify a CRTP is a type passing itself as template type to the base type it is deriving from, as seen in Bird
and Fish
below.#include <iostream>
using namespace std;
template <typename Derived>
struct Creature
{int eye_num;
friend bool operator == (const Derived& lhs, const Derived& rhs)
{return lhs.IsEqual(rhs);
}
friend bool operator != (const Derived& lhs, const Derived& rhs)
{return !(lhs.IsEqual(rhs));
}
};
struct Bird: Creature<Bird>
{int wing_num;
bool IsEqual(const Bird& b) const
{return eye_num == b.eye_num && wing_num == b.wing_num;
}
};
struct Fish: Creature<Fish>
{int fin_num;
bool IsEqual(const Fish& f) const
{return eye_num == f.eye_num && fin_num == f.fin_num;
}
};
int main()
{
Bird b1, b2, b3;
2;
b1.eye_num = 2;
b2.eye_num = 2;
b3.eye_num =
2;
b1.wing_num = 2;
b2.wing_num = 3;
b3.wing_num =
if (b1 != b2) cout << "Bird equal\n";
else cout << "Bird not equal\n";
if (b1 == b3) cout << "Bird equal\n";
else cout << "Bird not equal\n";
// You can do the same with Fish:
// Fish f1, f2, f3;
// f1.fin_num = 5;
// and so on ...
}
I hope this example helped you understand this trick.