The Curiously Recurring Template Pattern

The Curiously Recurring Template Pattern (CRTP) is a C++ design pattern that exhibits some interesting behavior related to inheritance and polymorphism. It is considered an idiomatic design pattern, meaning it incorporates semantic design principles for efficiently implementing a recurring construct. In this instance, CRTP is heavily tied to C++ given the language features that C++ exposes to the developer.

Motivation for Use

Before we get into the specifics of implementation, to what benefit is CRTP to the developer? For one, CRTP exposes a C++ language feature called static polymorphism. This is an object-oriented programming paradigm that works similarly to virtual functions, but instead of incurring a potential cost during runtime due to the overhead of dynamic dispatch, the resolution occurs at compile time (hence “static”).

Okay, so maybe you save a few clock cycles by allowing the compiler to resolve polymorphic calls. Sure, that is nothing to sneeze at, especially in applications where every nanosecond counts, but for the general developer, this isn’t necessarily a concern. If time is not of the essence, then perhaps code reusability is. CRTP enables the developer to have a base class that implements some generic functionality, but actual implementation details can be deferred to the derived class. Examples of this will be shown when the CRTP framework is discussed. The real benefit to this is having a neat, idiomatic way to handle derived classes that possess enough similarity to have a generalized interface, but enough complexity to require their own implementations. Again, this is very similar to the concept of virtual and abstract classes, but those do not get the benefit of the static polymorphism previously discussed.

CRTP also enables stronger type checking and optimization at compile time. Since everything to do with these classes and their objects, values, methods, etc. is resolved statically (at compile time), the compiler is able to perform optimization that it would be unable to do with virtual classes and functions.

Implementation

To properly demonstrate CRTP, we will first show a typical implementation of runtime polymorphism using abstract classes with virtual methods.

#include <iostream>
/**
 * @class Shape
 * @brief Shape interface
 */
class Shape {
 public:
  virtual void Draw() const = 0;
  virtual ~Shape() = default;
};
/**
 * @class Square
 * @brief Derived Shape class representing a square
 */
class Square : public Shape {
 public:
  void Draw() const override {
    std::cout << "Drawing a square\n";
  }
};
/**
 * @class Circle
 * @brief Derived Shape class representing a circle
 */
class Circle : public Shape {
 public:
  void Draw() const override {
    std::cout << "Drawing a circle\n";
  }
};
/**
 * @brief Demonstrate runtime polymorphism using abstract classes
 * @returns int Program exit code
 */
int main() {
  std::vector<std::unique_ptr<Shape>> shapes;
  shapes.push_back(std::make_unique<Circle>());
  shapes.push_back(std::make_unique<Square>());
  for (const auto& shape : shapes) {
    shape->Draw();
  }
  return 0;
}

The above code is a very generic implementation of runtime polymorphism in C++. The Shape class is the base, and Circle and Square are the derived classes. In the main function, a vector is constructed with the type specified as the base class, and then it is populated with an instance of both the Circle and Square classes. A for loop is then called that executes the Draw method in both derived objects. The shape variable is of type Shape, so dynamic dispatch occurs to determine which class’s method to call. The mechanism for this action is beyond the scope of this article; I will be discussing dynamic dispatch and virtual/abstract classes in a different post.

The primary takeaway is this: resolving which method to call occurs at runtime, which incurs cost due to overhead. In performance-critical code, any overhead could be detrimental. This is where static polymorphism comes into play.

#include <iostream>
/**
 * @class Shape
 * @brief Shape interface
 */
template <class Derived>
class Shape {
 public:
  void Draw() const {
    static_cast<const Derived*>(this)->Draw();
  }
};
/**
 * @class Square
 * @brief Derived Shape class representing a square
 */
class Square : public Shape<Square> {
 public:
  void Draw() const {
    std::cout << "Drawing a square\n";
  }
};
/**
 * @class Circle
 * @brief Derived Shape class representing a circle
 */
class Circle : public Shape<Circle> {
 public:
  void Draw() const {
    std::cout << "Drawing a circle\n";
  }
};
int main() {
  Circle circle;
  Square square;
  circle.Draw();
  square.Draw();
  return 0;
}

The structure of the code is very similar to the abstract class example, but notice that there are no virtual keywords. The base class also now has a template parameter Derived, and the derived classes all inherit from the base class. Strangely, the derived classes pass themselves as the template parameter to the base class… what is happening there? This very odd method of inheritance is exactly why this pattern is called “curious”.

It almost seems impossible: how can a derived class inherit from a base class and provide itself as a template parameter when it hasn’t been defined yet? It comes down to the compiler and the way things are ordered. Here’s what is happening: Shape<Circle>::Draw() is declared in the code before class Circle “exists” (i.e., is known to the compiler). However, that method is not actually instantiated until some other portion of the code calls it later on. The calling of the method will occur after Circle is declared. In the main function, when circle.Draw() is called, the declaration of the Circle::Draw() method is known by the compiler.

History

The concept of CRTP originated from type theory, a branch of mathematics and computer science that deals with type systems.¹ In type theory, there is a concept called quantification. Quantification refers to using type variables to make generic code. We see examples of this in C++ with templates.

template <typename T>
T interface(T value);

The above code reads as such in layman’s terms: “For any type T, the function interface takes a T and returns a T.” This is known as unbounded quantification, meaning that T can be any type.

An extension of this is bounded quantification which describes the manner in which a type variable can be restricted. This is used to construct functions or type variables which read as such in layman’s terms: “For all types T such that T is a subtype of U.”

CRTP as it is known today was formalized in 1989 when F-bounded quantification was introduced in type theory. This form of bounded quantification deals with the typing of functions which are applied to recursive types.² CRTP is a form of F-bounded quantification called F-bound polymorphism. The name “Curiously Recurring Template Pattern” was formalized by Jim Coplien in 1995.³

Conclusion

The Curiously Recurring Template Pattern is one of many powerful OOP idioms. It enables static polymorphism, and it transfers the runtime overhead of deducing type behavior to the compiler instead, saving precious time in performance-critical code. It appears complicated (and, depending on the intended use case, actually can be quite complex), but it enables the compiler to perform optimizations and to enforce stronger type checking. It allows the developer to reuse code and create interfaces to share type behavior across derived classes while allowing the derived implementation to be as complex as needed.

References

Kleene, S. C. & Rosser, J. B. (1935). “The inconsistency of certain formal logics”. Annals of Mathematics. 36 (3): 630–636. doi:10.2307/1968646. JSTOR 1968646. ↩︎
F-bounded polymorphism for object-oriented programming. Canning, Cook, Hill, Olthof and Mitchell. http://dl.acm.org/citation.cfm?id=99392 ↩︎
Coplien, James O. (February 1995). “Curiously Recurring Template Patterns”. C++ Report: 24–27. ↩︎

shared_ptr