A simple example to understand CRTP

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.

Problem

• Say, we have a class hierarchy with 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 {};

• Species like 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.
• Suppose we want to write equality (==) 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

Solutions

Let us see different ways this can be solved elegantly:

• Solution 1: Create pure-virtual == 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.
• Solution 2: Create non-virtual == 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.
• Solution 3: Create non-virtual == 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!
• Solution 4: Use CRTP as shown in the code below. Both equality and inequality tests are fully type dependent. However, note that the inequality test is only written once in the base class. So, we end up writing 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;

    b1.eye_num  = 2;
    b2.eye_num  = 2;
    b3.eye_num  = 2;

    b1.wing_num = 2;
    b2.wing_num = 2;
    b3.wing_num = 3;

    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.