The Curiously Recurring Template Pattern in C++

May 17th, 2011 at 5:38 am

C++ provides pretty good support for polymorphism by means of virtual functions. This is dynamic polymorphism (or runtime polymorphism), since the actual function to be called is resolved at runtime. It’s usually implemented by adding a hidden pointer in every object of a class with virtual functions. The pointer will point for any given object at the actual functions to call for it, so even when the compiler only knows this object through a pointer to a base class, it can generate correct code.

The problem with dynamic polymorphism is its runtime cost. This usually consists of the following components [1]:

  • Extra indirection (pointer dereference) for each call to a virtual method.
  • Virtual methods usually can’t be inlined, which may be a significant cost hit for some small methods.
  • Additional pointer per object. On 64-bit systems which are prevalent these days, this is 8 bytes per object. For small objects that carry little data this may be a serious overhead.

Although in general dynamic polymorphism is a great tool, due to the aforementioned costs some applications prefer not to use it, at least for some performance-critical classes. So what is the alterantive?

It turns out that using templates, C++ provides an alternative way to implement polymorphism without the extra costs. There’s a catch, of course – the types of objects have to be resolvable by the compiler at compile-time. This is called static polymorphism (or "simulated dynamic binding").

Here’s the simplest code sample I could come up with that demonstrates the technique:

#include <iostream>
using namespace std;

template <typename Child>
struct Base
{
    void interface()
    {
        static_cast<Child*>(this)->implementation();
    }
};

struct Derived : Base<Derived>
{
    void implementation()
    {
        cerr << "Derived implementation\n";
    }
};

int main()
{
    Derived d;
    d.interface();  // Prints "Derived implementation"
}

The key to the technique is the strange template trickery that’s being used: note that Derived inherits from Base<Derived>. What gives? The idea is to "inject" the real type of the derived class into the base, at compile time, allowing the static_cast of this in the interface to produce the desired result. This technique has a name – it’s called Curiously Recurring Template Pattern (CRTP from now on).

Synthetic examples are prone to not being exciting, and this one is no exception. Why not just implement interface in Derived, if its type is known at compile-time anyway, you may ask. This is a good question, which is why I plan to provide more examples to show how CRTP is useful.

The following example is much longer – although it is also a simplification. It presents a generic base class for visiting binary trees in various orders. This base class can be inherited to specify special handling of some types of nodes. Here is the tree node definition and the base class:

struct TreeNode
{
    enum Kind {RED, BLUE};

    TreeNode(Kind kind_, TreeNode* left_ = NULL, TreeNode* right_ = NULL)
        : kind(kind_), left(left_), right(right_)
    {}

    Kind kind;
    TreeNode *left, *right;
};

template <typename Derived>
class GenericVisitor
{
public:
    void visit_preorder(TreeNode* node)
    {
        if (node) {
            dispatch_node(node);
            visit_preorder(node->left);
            visit_preorder(node->right);
        }
    }

    void visit_inorder(TreeNode* node)
    {
        if (node) {
            visit_inorder(node->left);
            dispatch_node(node);
            visit_inorder(node->right);
        }
    }

    void visit_postorder(TreeNode* node)
    {
        if (node) {
            visit_postorder(node->left);
            visit_postorder(node->right);
            dispatch_node(node);
        }
    }

    void handle_RED(TreeNode* node)
    {
        cerr << "Generic handle RED\n";
    }

    void handle_BLUE(TreeNode* node)
    {
        cerr << "Generic handle BLUE\n";
    }

private:
    // Convenience method for CRTP
    //
    Derived& derived()
    {
        return *static_cast<Derived*>(this);
    }

    void dispatch_node(TreeNode* node)
    {
        switch (node->kind) {
            case TreeNode::RED:
                derived().handle_RED(node);
                break;
            case TreeNode::BLUE:
                derived().handle_BLUE(node);
                break;
            default:
                assert(0);
        }
    }
};

And a simple derived class:

class SpecialVisitor : public GenericVisitor<SpecialVisitor>
{
public:
    void handle_RED(TreeNode* node)
    {
        cerr << "RED is special\n";
    }
};

Now you can easily implement special handling of various kinds of nodes in subclasses, and use visiting services provided by the base class.

To reiterate – this is a simplified example, as there are only two kinds of nodes, but in reality there can be many more. Such code would be quite useful inside compilers, where the source is usually parsed into a tree with many different kinds of nodes. Multiple passes in the compiler then process the trees by implementing their own visitors. As a matter of fact, the Clang compiler frontend has such a class, named RecursiveASTVisitor, which implements a much more complete version of the visitor displayed above.

Without CRTP, there’s no way to implement such functionality except resorting to dynamic polymorphism and virtual functions [2].

Another interesting example is the following:

template <typename Derived>
struct Comparisons
{
};


template <typename Derived>
bool operator==(const Comparisons<Derived>& o1, const Comparisons<Derived>& o2)
{
    const Derived& d1 = static_cast<const Derived&>(o1);
    const Derived& d2 = static_cast<const Derived&>(o2);

    return !(d1 < d2) && !(d2 < d1);
}


template <typename Derived>
bool operator!=(const Comparisons<Derived>& o1, const Comparisons<Derived>& o2)
{
    return !(o1 == o2);
}

This is a generic base class with some external comparison functions that act on it. What this makes possible is to create a derived class that only defines the < operator, making other comparison operators (== and != here, but others are trivial to add) possible. Here’s a sample derived class:

class Person : public Comparisons<Person>
{
public:
    Person(string name_, unsigned age_)
        : name(name_), age(age_)
    {}

    friend bool operator<(const Person& p1, const Person& p2);
private:
    string name;
    unsigned age;
};


bool operator<(const Person& p1, const Person& p2)
{
    return p1.age < p2.age;
}

Again, this is using CRTP to implement something that could only be possible with virtual functions had we wanted dynamic polymorphism. Sometimes a class like Comparisons above is called a mixin class:

In object-oriented programming languages, a mixin is a class that provides a certain functionality to be inherited or just reused by a subclass, while not meant for instantiation (the generation of objects of that class). Inheriting from a mixin is not a form of specialization but is rather a means of collecting functionality. A class may inherit most or all of its functionality from one or more mixins through multiple inheritance.

[Wikipedia quote]

So how often is CRTP used in "real life"? I don’t have any actual usage statistics, but it appears that this is a useful tool in a C++ programmer’s toolbox. The RecursiveASTVisitor class from Clang I mentioned above is a very real use case. Clang’s parent project LLVM uses CRTP in at least another place (the HeuristicBase class in the code generator module).

Boost also uses CRTP for its Iterator Facade:

iterator_facade is a base class template that implements the interface of standard iterators in terms of a few core functions and associated types, to be supplied by a derived iterator class.

And finally, Microsoft’s Active Template Library (ATL) uses CRTP comprehensively. See, for example, the CWindowImpl template.

http://eli.thegreenplace.net/wp-content/uploads/hline.jpg
[1] I have no intention of providing a comprehensive analysis of the cost here. This is a well-defined topic and a lot of information can be learned by googling "c++ virtual call cost".
[2] You may wonder why this is so. Can’t GenericVisitor be a simple class, without the Derived templating? Absolutely not. Had dispatch_node just called handle_RED for red nodes, this would always call GenericVisitor::handle_RED, and never the handle_RED of the derived class. Keep in mind that the code of dispatch_node is generated statically at compile-time, and the only handle_RED the compiler is familiar with at that point is GenericVisitor‘s, unless of course it’s virtual, or CRTP is used.

Related posts:

  1. C++ template syntax patterns
  2. Pure virtual destructors in C++
  3. Dependent name lookup for C++ templates
  4. The many faces of operator new in C++
  5. How I stopped worrying and switched to C++ for my Bob Scheme VM

9 Responses to “The Curiously Recurring Template Pattern in C++”

  1. Roger PateNo Gravatar Says:

    I notice your convenience function GenericVisitor::derived and your static_cast to a const type in op==. You can use crtp_cast to simplify that:

    template<class D, class B>
    D& crtp_cast(B& p) {
      return static_cast<D&>(p);
    }
    template<class D, class B>
    D const& crtp_cast(B const& p) {
      return static_cast<D const&>(p);
    }
    template<class D, class B>
    D volatile& crtp_cast(B volatile& p) {
      return static_cast<D volatile&>(p);
    }
    template<class D, class B>
    D const volatile& crtp_cast(B const volatile& p) {
      return static_cast<D const volatile&>(p);
    }

    I prefer using it with a local, helper macro:

    template<class Derived>
    struct Base {
    #define self crtp_cast<Derived>(*this)
      void f() { self.g(); }  // Uses non-const g().
      void foo() const { self.g(); }  // Uses const g().
    #undef self
    };
  2. Nicola BonelliNo Gravatar Says:

    While the example of CRTP as used in the mixin class is really effective, I wonder how CRTP impacts on the performance of the first example that by design requires dynamic polymorphism (the tree layout is indeed unknown at compile time).
    The cost of virtual functions is in reality buried in the dispatch_node method. It would be really interesting to have a performance comparison of the two implementations…

  3. DavidNo Gravatar Says:

    Eli,

    Nice & enlightening post.

    I’ve read about the CRTP in at least 2 books, and I’ve read the Wikipedia article a couple times, but it never came together until I read this blog post. For me at least, *the key was the basic example* introduced at the beginning – “artificial” or not, it helped me understand the basic pattern before using it in a more complicated, real-world situation.

    Keep up the good work, I’ve bookmarked & forwarded on many of your posts.

  4. elibenNo Gravatar Says:

    Roger
    Interesting, thanks.

    Nicola
    I agree this levels the “indirection” cost. But the space cost and inlining cost still stay. The inlining, in particular, is IMHO the most significant runtime cost. With inlining, the CRTP method can have one function call less, which is significant. That said, I agree that it’s better to measure.

    David
    Thanks for the feedback.

  5. Arseny KapoulkineNo Gravatar Says:

    Almost every singleton implementation in C++ uses CRTP, and almost every significant C++ project uses at least a dozen singleton classes – this, I believe, is the most common usage of CRTP.

  6. VincentLNo Gravatar Says:

    In reply to your point [2] it seems to me that it actually is possible not to use CRTP in that case.
    You definitely have to use a template class, but you can use aggregation instead of inheritance
    to form an equally viable solution:

    template <typename NodeActor>
    class Visitor
    {
    public:
    
        void visit_preorder(TreeNode* node);
    
        void visit_inorder(TreeNode* node);
    
        void visit_postorder(TreeNode* node)
    
    private:
    
        NodeActor      mNodeActor;
    
        void dispatch_node(TreeNode* node)
        {
            switch (node->kind) {
                case TreeNode::RED:
                    mNodeActor.handle_RED(node);
                    break;
                case TreeNode::BLUE:
                    mNodeActor.handle_BLUE(node);
                    break;
                default:
                    assert(0);
            }
        }
    };

    and :

    struct GenericNodeActor
    {
        void handle_RED(TreeNode* node)
        {
            cerr << "Generic handle RED\n";
        }
    
        void handle_BLUE(TreeNode* node)
        {
            cerr << "Generic handle BLUE\n";
        }
    }
    
    struct SpecialNodeActor : public GenericNodeActor
    {
        void handle_RED(TreeNode* node)
        {
            cerr << "RED is special\n";
        }
    };

    Then obviously you can instantiate the Visitor class templated on the desired NodeActor class,
    thus achieving the same behaviour as the CRTP solution.

  7. elibenNo Gravatar Says:

    VincentL,

    Yep, I’m aware of this alternative. It’s a “kind-of” CRTP just replacing inheritance by composition, exactly as you say. It does have some disadvantages opposed to CRTP – for example, what if the specialized visitors need to access other methods of the base class? This is natural with CRTP but not so with this composition-based approach (the base class should inject a reference to itself into the visitors).

    Pragmatically you’re right – this is a solution, and it’s not strictly CRTP.

  8. rayneboyNo Gravatar Says:

    this is a great explanation and helped me understand design patterns in C++. I originally came across your tutorial through a similar question in Stack Overflow, the users mentioned the templated Visitor pattern as a form of CRTP:
    http://stackoverflow.com/questions/2886193/visitor-and-templated-virtual-methods

  9. GregNo Gravatar Says:

    How can I use CRTP for multi-level inheritance? I something like this possible?

    struct AlsoDerived : Derived
    {
        void implementation()
        {
            // Call Parent first.
            static_cast<Derived*>(this)->implementation();
            cerr << "AlsoDerived implementation\n";
        }
    };

Leave a Reply

To post code with preserved formatting, enclose it in `backticks` (even multiple lines)