(CRTP) Curiously Recurring Template Pattern

The Curiously Recurring Template Pattern (CRTP) is an advanced C++ idiom where a class template is used to inherit from a specialization of itself. It may sound odd, but this pattern enables compile-time polymorphism, allows certain optimizations, and helps implement various design patterns.

Definition

In CRTP, a class Derived inherits from a class template Base that takes the Derived class as a template parameter. The structure looks something like this:

template <typename Derived>
class Base {
    // Base class functionality that can use Derived
};

class Derived : public Base<Derived> {
    // Derived-specific functionality
};

The “curious” part comes from the fact that Derived is passing itself (the derived class) as a template parameter to Base, hence the name Curiously Recurring Template Pattern.

CRTP Structure

Here is the general structure of CRTP:

template <typename Derived>
class Base {
public:
    void interface() {
        // This function calls a function from the derived class
        static_cast<Derived*>(this)->implementation();
    }
    
    // Base class might provide common functionality
};

class Derived : public Base<Derived> {
public:
    void implementation() {
        std::cout << "Derived implementation called!" << std::endl;
    }
};

• The Base class provides the common functionality for derived classes and defines a function (interface) that calls a function from the derived class (implementation) using static_cast<Derived*>(this).
• The Derived class inherits from Base<Derived> and provides its own implementation of the implementation function.

Example of Usage:

#include <iostream>

template <typename Derived>
class Base {
public:
    void interface() {
        // This calls Derived::implementation()
        static_cast<Derived*>(this)->implementation();
    }
};

class Derived : public Base<Derived> {
public:
    void implementation() {
        std::cout << "Derived::implementation called!" << std::endl;
    }
};

int main() {
    Derived d;
    d.interface();  // Calls Derived::implementation()
    
    return 0;
}

Output:

Derived::implementation called!

Key Features of CRTP

1. Compile-Time Polymorphism: CRTP provides an alternative to traditional runtime polymorphism using virtual functions. Instead of using dynamic dispatch (i.e., through vtables), CRTP enables compile-time polymorphism. The function calls are resolved at compile time, which can result in better performance since there is no runtime overhead of virtual function dispatch.
2. Code Reuse: The Base class can define functionality that applies to a wide range of derived classes. The derived classes just need to specialize certain behaviors. This allows for significant code reuse.
3. No Virtual Functions: CRTP doesn’t require virtual functions, which means no vtables or virtual dispatch, avoiding the associated overhead.
4. Type-Specific Optimizations: Since the Base class knows the exact type of the Derived class at compile time, it can perform optimizations that are not possible in runtime polymorphism where types are only known at runtime.

Applications of CRTP

CRTP is widely used in many scenarios, especially where compile-time optimizations or specialized behavior are desired. Below are some common uses of CRTP:

1. Static Polymorphism

As an alternative to traditional polymorphism, CRTP allows for static (compile-time) polymorphism. With traditional polymorphism, virtual functions are used, which introduces runtime overhead due to dynamic dispatch. CRTP, however, resolves everything at compile time.

Example:

#include <iostream>

template <typename Derived>
class Animal {
public:
    void makeSound() {
        static_cast<Derived*>(this)->makeSoundImpl();
    }
};

class Dog : public Animal<Dog> {
public:
    void makeSoundImpl() {
        std::cout << "Woof!" << std::endl;
    }
};

class Cat : public Animal<Cat> {
public:
    void makeSoundImpl() {
        std::cout << "Meow!" << std::endl;
    }
};

int main() {
    Dog dog;
    dog.makeSound();  // Outputs: Woof!
    
    Cat cat;
    cat.makeSound();  // Outputs: Meow!
    
    return 0;
}

In this example, the Animal class provides a generic interface for animals, while the specific animals like Dog and Cat implement their own behavior. This is an example of static polymorphism: the behavior is determined at compile time, without any virtual functions or runtime overhead.

2. Curiously Recurring Pattern for Mixins

CRTP can be used to implement mixin classes, which allow you to extend functionality of multiple classes without traditional inheritance.

Example:

#include <iostream>

template <typename Derived>
class Printable {
public:
    void print() const {
        static_cast<const Derived*>(this)->printImpl();
    }
};

class MyClass : public Printable<MyClass> {
public:
    void printImpl() const {
        std::cout << "MyClass implementation" << std::endl;
    }
};

int main() {
    MyClass obj;
    obj.print();  // Outputs: MyClass implementation
    
    return 0;
}

Here, Printable is a mixin class that provides a print() function to any class that inherits from it. The derived class MyClass defines the actual implementation in printImpl().

3. Code Factorization and Method Specialization

CRTP allows you to share common functionality in the base class while letting the derived class specialize some behaviors. You can write generic code in the base class and specific code in the derived class.

Example:

#include <iostream>

template <typename Derived>
class Algorithm {
public:
    void run() {
        // Common steps
        static_cast<Derived*>(this)->step1();
        static_cast<Derived*>(this)->step2();
    }
};

class MyAlgorithm : public Algorithm<MyAlgorithm> {
public:
    void step1() {
        std::cout << "Step 1" << std::endl;
    }

    void step2() {
        std::cout << "Step 2" << std::endl;
    }
};

int main() {
    MyAlgorithm algo;
    algo.run();  // Outputs: Step 1 and Step 2
    
    return 0;
}

In this example, the Algorithm class defines the structure of an algorithm, while the derived class MyAlgorithm provides specific implementations of the steps.

4. Implementation of EBO (Empty Base Optimization)

CRTP is used to implement the Empty Base Optimization (EBO) in C++. When a class inherits from an empty class, CRTP allows the compiler to optimize the memory layout by not allocating any space for the empty base class.

Advantages of CRTP

1. No Overhead of Virtual Functions: CRTP avoids the overhead of virtual functions and dynamic dispatch since everything is resolved at compile time.
2. Type-Safe Behavior at Compile Time: By using static_cast to cast this to the Derived type, CRTP ensures that the compiler can check at compile time whether the derived class provides the necessary functions.
3. Flexible and Extensible: CRTP provides a flexible design pattern that can be used for static polymorphism, code reuse, and type-safe mixins.
4. Better Performance: Since there is no runtime dispatch, CRTP can lead to better performance compared to traditional runtime polymorphism.

Disadvantages of CRTP

1. Complexity: The CRTP idiom can be complex and difficult to understand for newcomers. It also leads to intricate compiler errors if used incorrectly.
2. No Runtime Polymorphism: While CRTP provides compile-time polymorphism, it does not provide runtime polymorphism like traditional inheritance with virtual functions. If you need polymorphic behavior at runtime, CRTP may not be suitable.
3. Code Duplication: Since CRTP relies on template instantiation, it can result in code bloat (duplication of code) when the pattern is used extensively in large codebases with many instantiations.

Comparison of CRTP vs. Virtual Inheritance

Conclusion

The Curiously Recurring Template Pattern (CRTP) is a powerful and flexible C++ design pattern that leverages templates for compile-time polymorphism, enabling optimized and type-safe behavior without the runtime overhead of virtual functions. While it can be more complex to understand than traditional inheritance, it provides significant benefits in terms of performance, code reuse, and compile-time type checking.

CRTP is often used in performance-critical code, template metaprogramming, mixins, and in scenarios where type-specific optimizations are required. However, it may not be suitable if runtime polymorphism is needed.