Time Travel in C++: Implementing Static Polymorphism with CRTP

Hey, friends! Hui Mei is back! 😄 Today we are going to talk about a topic that seems a bit ‘sci-fi’: CRTP (Curiously Recurring Template Pattern), which literally translates to ‘Curiously Recurring Template Pattern’. Don’t be scared by this name; it is actually a very practical C++ technique often used to achieve efficient static polymorphism.

If you already have some understanding of polymorphism (like virtual functions and inheritance), then this article will help you ‘level up’ and learn how to use templates to implement compile-time polymorphism while avoiding the performance overhead of traditional dynamic polymorphism.

Are you ready? Let’s start today’s ‘time travel’! 🚀✨

1. What is CRTP?

CRTP is a template design pattern in C++, and its core idea is: to let a class inherit from a base class that uses itself as a template parameter. Sounds a bit convoluted? Don’t worry, take a look at the code example below:

template <typename Derived>
class Base {
public:
    void interface() {
        // Call the derived class's 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!

The Core Structure of CRTP:

1. The base class Base is a template class that takes the derived class Derived as a template parameter.
2. The derived class Derived inherits from Base<Derived>.
3. In the base class, the current object is cast to the derived class type using static_cast<Derived*>(this), allowing it to call methods of the derived class.

Hui Mei’s Tip: The name of this design pattern comes from its ‘recursive’ structure—the base class needs to define itself using the type of the derived class. Doesn’t it feel a bit like ‘time travel’? 😉

2. CRTP and Static Polymorphism

Performance Issues of Dynamic Polymorphism

In traditional object-oriented programming, we usually achieve polymorphism through inheritance and virtual functions:

class Base {
public:
    virtual void implementation() {
        std::cout << "Base::implementation()" << std::endl;
    }
    virtual ~Base() = default;
};

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

void callImplementation(Base* obj) {
    obj->implementation();
}

int main() {
    Derived d;
    callImplementation(&d);
    return 0;
}

Output:

Derived::implementation()

Although dynamic polymorphism (using virtual functions) is very flexible, it has two issues:

1. Performance Overhead: Each call to a virtual function requires access through the virtual table (vtable), which incurs some runtime overhead.
2. Inability to Inline: The specific implementation of a virtual function cannot be determined at compile time, preventing the compiler from performing inline optimization.

CRTP Achieving Static Polymorphism

CRTP achieves static polymorphism through templates, moving the function selection process to compile time, thus avoiding the runtime overhead of virtual functions.

Let’s look at the same functionality implemented with CRTP:

#include <iostream>

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

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

int main() {
    Derived d;
    d.callImplementation(); // Static call to derived class method
    return 0;
}

Output:

Derived::implementation()

Compared to dynamic polymorphism, the advantages of CRTP are:

1. No Runtime Overhead: All function calls are determined at compile time.
2. Supports Inline Optimization: Since the specific function implementation is called, the compiler can inline it, thus improving performance.

3. Practical Applications of CRTP

CRTP is not just a ‘show-off’ tool; it has many classic applications in actual development. Next, Hui Mei will list a few common examples.

Scenario 1: Enforcing Interface Implementation

CRTP can be used to force derived classes to implement certain interfaces while avoiding the overhead of dynamic polymorphism.

#include <iostream>

// Base class template, requiring derived classes to implement implementation()
template <typename Derived>
class Interface {
public:
    void call() {
        static_cast<Derived*>(this)->implementation();
    }
};

// Derived class
class MyClass : public Interface<MyClass> {
public:
    void implementation() {
        std::cout << "MyClass::implementation()" << std::endl;
    }
};

int main() {
    MyClass obj;
    obj.call(); // Calls MyClass's implementation
    return 0;
}

If the derived class does not implement implementation(), the compiler will throw an error, enforcing constraints on the derived class at compile time.

Scenario 2: Expression Templates

CRTP is a core technique for implementing expression templates, which are widely used in high-performance numerical computation libraries (like Eigen, Boost uBLAS).

Here’s a simple example showing how to implement vector addition using expression templates with CRTP:

#include <iostream>

// Vector base class template
template <typename Derived>
class VectorBase {
public:
    double operator[](size_t i) const {
        return static_cast<const Derived*>(this)->operator[](i);
    }
    size_t size() const {
        return static_cast<const Derived*>(this)->size();
    }
};

// Vector class
class Vector : public VectorBase<Vector> {
private:
    double data[3];
public:
    Vector(double x, double y, double z) {
        data[0] = x; data[1] = y; data[2] = z;
    }
    double operator[](size_t i) const {
        return data[i];
    }
    size_t size() const {
        return 3;
    }
};

// Vector addition class
template <typename LHS, typename RHS>
class VectorAdd : public VectorBase<VectorAdd<LHS, RHS>> {
private:
    const LHS& lhs;
    const RHS& rhs;
public:
    VectorAdd(const LHS& l, const RHS& r) : lhs(l), rhs(r) {}
    double operator[](size_t i) const {
        return lhs[i] + rhs[i];
    }
    size_t size() const {
        return lhs.size();
    }
};

// Overloading the + operator
template <typename LHS, typename RHS>
VectorAdd<LHS, RHS> operator+(const VectorBase<LHS>& lhs, const VectorBase<RHS>& rhs) {
    return VectorAdd<LHS, RHS>(*static_cast<const LHS*>(&lhs), *static_cast<const RHS*>(&rhs));
}

int main() {
    Vector v1(1.0, 2.0, 3.0);
    Vector v2(4.0, 5.0, 6.0);

    auto v3 = v1 + v2; // Lazy evaluation
    for (size_t i = 0; i < v3.size(); ++i) {
        std::cout << v3[i] << " "; // Outputs 5.0 7.0 9.0
    }
    return 0;
}

Output:

5 7 9

Scenario 3: Strategy Pattern

CRTP can also be used to implement functionality similar to the strategy pattern, allowing flexible switching between different implementations through template parameters.

4. Considerations When Using CRTP

1. Code Complexity: While CRTP can improve performance, the complexity of reading and debugging template code may increase.
2. Applicable Scenarios: CRTP is more suitable for scenarios with high performance requirements. If the performance loss of dynamic polymorphism is acceptable, prefer using traditional virtual functions.
3. Inheritance Chain Issues: CRTP is only suitable for single-level inheritance; complex inheritance chains may lead to maintainability issues.

5. Summary and Exercises

Today, Hui Mei introduced the core concepts and application scenarios of CRTP. We learned:

• The basic structure and usage of CRTP.
• How CRTP achieves static polymorphism and avoids the runtime overhead of dynamic polymorphism.
• Practical applications of CRTP in enforcing interface implementation and expression templates.

Exercises:

1. Implement a base class template using CRTP to enforce derived classes to implement a print() method.
2. Modify the vector addition example to support more operations (like vector subtraction).
3. Research high-performance libraries like Eigen to learn more about the applications of CRTP.

Friends, that’s all for today’s C++ learning journey! Remember to practice more, and feel free to ask Hui Mei any questions in the comments! Wishing everyone a joyful learning experience and continuous improvement in C++! 🎉