Applying Curiously Recurring Template Pattern in C++

There is various material effectively accessible for "How" and "What" on CRTP. So, I will address the "Where" part that CRTP Applicability.

Vishal Chovatiya

Updated Aug. 03, 20 · Tutorial

Likes (2)

Comment

Save

10.2K Views

Curiously Recurring Template Pattern(CRTP) in C++ is definitely a powerful technique and a static alternative to virtual functions. But at the same time, learning it may seem a bit weird at first. If you are like me who struggled to grasp anything in one go. Then this article might help you to provide a thought process on where CRTP fits in day-to-day coding. And, if you are an Embedded Programmer, you may run into CRTP more often. Although, std::variant + std::visit will also help but 90% of the compilers for embedded processors are either not up to date with standard or dumb.

There is various material effectively accessible for "How" and "What" on CRTP. So, I will address the "Where" part that CRTP Applicability.

CRTP and Static Polymorphism In C++

     C++
    
x

template<typename specific_animal>
struct animal {
    void who() { static_cast<specific_animal*>(this)->who(); }
};
struct dog : animal<dog> {
    void who() { cout << "dog" << endl; }
};
struct cat : animal<cat> {
    void who() { cout << "cat" << endl; }
};
template<typename specific_animal>
void who_am_i(animal<specific_animal> andanimal) {
    animal.who();
}
cat c;
who_am_i(c); // prints `cat`
dog d;
who_am_i(d); // prints `dog`

Curiously Recurring Template Pattern widely employed for static polymorphism without bearing the cost of a virtual dispatch mechanism. Consider the above code, we haven't used virtual keyword and still achieved the functionality of polymorphism.
How it works is not the topic of this article. So, I am leaving it to you to figure out.

Limiting Object Count With CRTP

There are times when you have to manage the critical resource with single or predefined object count. And we have Singleton and Monotone Design Patterns for this. But this works as long as your object counts are smaller in number.
When you want to limit the arbitrary type to be limited with an arbitrary number of instances. CRTP will come to rescue:

     C++
    
xxxxxxxxxx

template <class ToBeLimited, uint32_t maxInstance>
struct LimitNoOfInstances {
    static atomic<uint32_t> cnt;
    LimitNoOfInstances() {
        if (cnt >= maxInstance)
            throw logic_error{"Too Many Instances"};
        ++cnt;
    }
    ~LimitNoOfInstances() { --cnt; }
}; // Copy, move & other sanity checks to be complete
struct One : LimitNoOfInstances<One, 1> {};
struct Two : LimitNoOfInstances<Two, 2> {};
template <class T, uint32_t maxNoOfInstace>
atomic<uint32_t> LimitNoOfInstances<T, maxNoOfInstace>::cnt(0);
void use_case() {
    Two _2_0, _2_1;
    try {
        One _1_0, _1_1;
    } catch (exception &e) {
        cout << e.what() << endl;
    }
}

You might be wondering that what is the point of the template parameter ToBeLimited, if it isn't used. In that case, you should have brush up your C++ Template fundamentals or use cppinsights.io. As it isn't useless.

CRTP to Avoid Code Duplication

Let say you have a set of containers that support the functions begin() and end(). But, the standard library's requirements for containers require more functionalities like front(), back(), size(), etc.
We can design such functionalities with a CRTP base class that provides common utilities solely based on derived class member function i.e. begin() and end() in our cases:

     C++
    
xxxxxxxxxx

template <typename T>
class Container {
    T &actual() { return *static_cast<T *>(this); }
    T const &actual() const { return *static_cast<T const *>(this); }
public:
    decltype(auto) front() { return *actual().begin(); }
    decltype(auto) back() { return *std::prev(actual().end()); }
    decltype(auto) size() const { return std::distance(actual().begin(), actual().end()); }
    decltype(auto) operator[](size_t i) { return *std::next(actual().begin(), i); }
};

The above class provides the functions front(), back(), size() and operator[ ] for any subclass that has begin() and end().
For example, subclass could be a simple dynamically allocated array as:

     C++
    
xxxxxxxxxx

template <typename T>
class DynArray : public Container<DynArray<T>> {
    size_t m_size;
    unique_ptr<T[]> m_data;
  public:
    DynArray(size_t s) : m_size{s}, m_data{make_unique<T[]>(s)} {}
    T *begin() { return m_data.get(); }
    const T *begin() const { return m_data.get(); }
    T *end() { return m_data.get() + m_size; }
    const T *end() const { return m_data.get() + m_size; }
};
DynArray<int> arr(10);
arr.front() = 2;
arr[2]        = 5;
asssert(arr.size() == 10);

Modern C++ Composite Design Pattern Leveraging CRTP

Composite Design Pattern states that we should treat the group of objects in the same manner as a single object. And to implement such a pattern we can leverage the CRTP.
For example, as a part of machine learning, we have to deal with Neuron which for simplicity defined as:

     C++
    
xxxxxxxxxx

struct Neuron {
    vector<Neuron*>     in, out;    // Stores the input-output connnections to other Neurons
    uint32_t            id;
    Neuron() {
        static int id = 1;
        this->id = id++;
    }
    void connect_to(Neuron &other) {
        out.push_back(&other);
        other.in.push_back(this);
    }
    friend ostream &operator<<(ostream &os, const Neuron &obj) {
        for (Neuron *n : obj.in)
            os << n->id << "\t-->\t[" << obj.id << "]" << endl;
        for (Neuron *n : obj.out)
            os << "[" << obj.id << "]\t-->\t" << n->id << endl;
        return os;
    }
};
Neuron n1, n2;
n1.connect_to(n2);
cout << n1 << n2 << endl;
/* Output
[1]    -->    2
1    -->    [2]
*/

And there is also a 
   NeuronLayer i.e. collection of 
   Neuron which for simplicity defined as:

     C++
    
xxxxxxxxxx

struct NeuronLayer : vector<Neuron> {
    NeuronLayer(int count) {
        while (count --> 0)
            emplace_back(Neuron{});
    }
    friend ostream &operator<<(ostream &os, NeuronLayer &obj) {
        for (auto &n : obj)
            os << n;
        return os;
    }
};

Now, if you want to connect the Neuron with NeuronLayer and vice-versa. You're going to have a total of four different functions as follows:

     C++
    
xxxxxxxxxx

Neuron::connect_to(Neuron&)
Neuron::connect_to(NeuronLayer&)
NeuronLayer::connect_to(NeuronLayer&)
NeuronLayer::connect_to(Neuron&)

You see this is state-space explosion(permutation in layman terms) problem and it's not good. Because we want a single function that enumerable both the layer as well as individual neurons. CRTP comes handy here as:

     C++
    
 

      
     

       

      

       

      

      

     
xxxxxxxxxx

           

          

           

          

             
           
template <typename Self>
struct SomeNeurons {
    template <typename T>
    void connect_to(T &other);
};
struct Neuron : SomeNeurons<Neuron> {
    vector<Neuron*>     in, out;
    uint32_t            id;
    Neuron() {
        static int id = 1;
        this->id = id++;
    }
    Neuron* begin() { return this; }
    Neuron* end() { return this + 1; }
};
struct NeuronLayer : vector<Neuron>, SomeNeurons<NeuronLayer> {
    NeuronLayer(int count) {
        while (count-- > 0)
            emplace_back(Neuron{});
    }
};
/* ----------------------------------------------------------------------- */
template <typename Self>
template <typename T>
void SomeNeurons<Self>::connect_to(T &other) {
    for (Neuron &from : *static_cast<Self *>(this)) {
        for (Neuron &to : other) {
            from.out.push_back(&to);
            to.in.push_back(&from);
        }
    }
}
/* ----------------------------------------------------------------------- */
template <typename Self>
ostream &operator<<(ostream &os, SomeNeurons<Self> &object) {
    for (Neuron &obj : *static_cast<Self *>(&object)) {
        for (Neuron *n : obj.in)
            os << n->id << "\t-->\t[" << obj.id << "]" << endl;
        for (Neuron *n : obj.out)
            os << "[" << obj.id << "]\t-->\t" << n->id << endl;
    }
    return os;
}
int main() {
    Neuron n1, n2;
    NeuronLayer l1{1}, l2{2};
    n1.connect_to(l1); // Scenario 1: Neuron connects to Layer
    l2.connect_to(n2); // Scenario 2: Layer connects to Neuron
    l1.connect_to(l2); // Scenario 3: Layer connects to Layer
    n1.connect_to(n2); // Scenario 4: Neuron connects to Neuron
    cout << "Neuron " << n1.id << endl << n1 << endl;
    cout << "Neuron " << n2.id << endl << n2 << endl;
    cout << "Layer " << endl << l1 << endl;
    cout << "Layer " << endl << l2 << endl;
    return EXIT_SUCCESS;
}
/* Output
Neuron 1
[1]    -->    3
[1]    -->    2
Neuron 2
4    -->    [2]
5    -->    [2]
1    -->    [2]
Layer 
1    -->    [3]
[3]    -->    4
[3]    -->    5
Layer 
3    -->    [4]
[4]    -->    2
3    -->    [5]
[5]    -->    2
*/

       

      

As you can see we have covered all four different permutation scenarios using a single SomeNeurons::connect_to method. And both Neuron and NeuronLayer conforms to this interface via self templatization.

C++20 Spaceship Operator With the Help of CRTP

Problem

     C++
    
xxxxxxxxxx

struct obj_type_1 {
    bool operator<(const value &rhs) const { return m_x < rhs.m_x; }
    // bool operator==(const value &rhs) const;
    // bool operator!=(const value &rhs) const;    
    // List goes on. . . . . . . . . . . . . . . . . . . .
private:
    // data members to compare
};
struct obj_type_2 {
    bool operator<(const value &rhs) const { return m_x < rhs.m_x; }
    // bool operator==(const value &rhs) const;
    // bool operator!=(const value &rhs) const;    
    // List goes on. . . . . . . . . . . . . . . . . . . .
private:
    // data members to compare
};
struct obj_type_3 { ...
struct obj_type_4 { ...
// List goes on. . . . . . . . . . . . . . . . . . . .

For each comparable objects, you need to define respective comparison operators. This is redundant because if we have an 
   operator < , we can overload other operators based on it.

Thus, operator < is the only one operator having type information, other operators can be made type independent for reusability purposes.

Solution Till C++17 With CRTP

     C++
    
xxxxxxxxxx

template <class derived>
struct compare {};
struct value : compare<value> {
    int m_x;
    value(int x) : m_x(x) {}
    bool operator < (const value &rhs) const { return m_x < rhs.m_x; }
};
template <class derived>
bool operator > (const compare<derived> &lhs, const compare<derived> &rhs) {
    // static_assert(std::is_base_of_v<compare<derived>, derived>); // Compile time safety measures
    return (static_cast<const derived&>(rhs) < static_cast<const derived&>(lhs));
}
/*  Same goes with other operators
    == :: returns !(lhs < rhs) and !(rhs < lhs)
    != :: returns !(lhs == rhs)
    >= :: returns (rhs < lhs) or (rhs == lhs)
    <= :: returns (lhs < rhs) or (rhs == lhs) 
*/
int main() {   
    value v1{5}, v2{10};
    cout << boolalpha << "v1 > v2: " << (v1 > v2) << '\n';
    return EXIT_SUCCESS;
}
// Now no need to write comparator operators for all the classes, 
// Write only type dependent `operator <` & inherit with `compare<T>`

C++20 Solution : Spaceship Operator

     C++
    
xxxxxxxxxx

struct value{
    int m_x;
    value(int x) : m_x(x) {}
    auto operator<=>(const value &rhs) const = default;
};
// Defaulted equality comparisons
// More Info: https://en.cppreference.com/w/cpp/language/default_comparisons

Enabling Polymorphic Method Chaining

Method Chaining is a common syntax for invoking multiple methods on a single object back to back. That too, in a single statement without requiring variables to store the intermediate results. For example:

     C++
    
xxxxxxxxxx

class Printer {
    ostream &m_stream;
public:
    Printer(ostream &s) : m_stream(s) { }
    Printer &print(auto &&t) {
        m_stream << t;
        return *this;
    }
    Printer &println(auto &&t) {
        m_stream << t << endl;
        return *this;
    }
};
Printer{cout}.println("hello").println(500);     // Method Chaining

But, when method chaining applied to an object hierarchy, things can go wrong. For example:

     C++
    
xxxxxxxxxx

struct ColorPrinter : Printer {
    enum Color{red, blue, green};
    ColorPrinter(ostream &s) : Printer(s) {}
    ColorPrinter &SetConsoleColor(Color c) {
        // ...
        return *this;
    }
};
ColorPrinter(cout).print("Hello").SetConsoleColor(ColorPrinter::Color::red).println("Printer!"); // Not OK

Compiling above code prompt you with the following error:

     C++
    
xxxxxxxxxx

error: 'class Printer' has no member named 'SetConsoleColor'
ColorPrinter(cout).print("Hello").SetConsoleColor(ColorPrinter::Color::red).println("Printer!");
                                  ^
                                  |____________ We have a 'Printer' here, not a 'ColorPrinter'

This happens because we "lose" the concrete class as soon as we invoke a function of the base class.
The CRTP can be useful to avoid such a problem and to enable Polymorphic Method Chaining.

     C++
    
xxxxxxxxxx

template <typename ConcretePrinter>
class Printer {
    ostream &m_stream;
public:
    Printer(ostream &s) : m_stream(s) { }
    ConcretePrinter &print(auto &&t) {
        m_stream << t;
        return static_cast<ConcretePrinter &>(*this);
    }
    ConcretePrinter &println(auto &&t) {
        m_stream << t << endl;
        return static_cast<ConcretePrinter &>(*this);
    }
};
struct ColorPrinter : Printer<ColorPrinter> {
    enum Color { red, blue, green };
    ColorPrinter(ostream &s) : Printer(s) {}
    ColorPrinter &SetConsoleColor(Color c) {
        // ...
        return *this;
    }
};
int main() {
    ColorPrinter(cout).print("Hello ").SetConsoleColor(ColorPrinter::Color::red).println("Printer!");
    return EXIT_SUCCESS;
}

Enabling Polymorphic Copy Construction in C++ with CRTP

Problem

C++ has the support of polymorphic object destruction using it's base class's virtual destructor. But, equivalent support for creation and copying of objects is missing as С++ doesn't support virtual constructor/copy-constructors.
Moreover, you can't create an object unless you know its static type, because the compiler must know the amount of space it needs to allocate. For the same reason, a copy of an object also requires its type to known at compile-time.

     C++
    
xxxxxxxxxx

struct animal {  virtual ~animal(){ cout << "~animal\n"; } };
struct dog : animal  { ~dog(){ cout << "~dog\n"; } };
struct cat : animal  { ~cat(){ cout << "~cat\n"; } };
void who_am_i(animal *who) { // not sure whether `dog` would be passed here or `cat`
    // How to `copy` object of the same type i.e. pointed by who?
    delete who; // you can delete object pointed by who
}

Solution 1: Dynamic Polymorphism

As the name suggests, we will use virtual methods to delegate the act of copying(and/or creation) of the object as below:

     C++
    
xxxxxxxxxx

struct animal {
    virtual unique_ptr<animal> clone() = 0;
};
struct dog : animal {
    unique_ptr<animal> clone() override { return make_unique<dog>(*this); }
};
struct cat : animal {
    unique_ptr<animal> clone() override { return make_unique<cat>(*this); }
};
void who_am_i(animal *who) {
    auto duplicate_who = who->clone(); // `copy` object of same type i.e. pointed by who ?    
}

Solution 2: Static Polymorphism

The same thing can be accomplished with CRTP as below:

     C++
    
xxxxxxxxxx

template <class specific>
struct animal {
    unique_ptr<animal> clone() {
        return make_unique<specific>(static_cast<specific &>(*this));
    }
protected: // Forcing animal class to be inherited
    animal(const animal &) = default;
};
struct dog : animal<dog> {
    dog(const dog &) { cout << "copied dog" << endl; }
};
struct cat : animal<cat> {
    cat(const cat &) { cout << "copied cat" << endl; }
};
template <class specific>
void who_am_i(animal<specific> *who) {
    auto duplicate_who = who->clone(); // `copy` object of same type i.e. pointed by who ?
}

Closing Words

Everything comes with its price. And CRTP is no exception. For example, if you are using CRTP with run time object creation, your code may behave weird. Moreover,

As the base class is templated, you can not point the derived class object with the base class pointer.
Also, you can not create generic container like std::vector<animal*> because animal is not a class, but a template needing specialization. A container defined as std::vector<animal<dog>*> can only store dogs, not cats. This is because each of the classes derived from the CRTP base class animal is a unique type. A common solution to this problem is to add one more layer of indirection i.e. abstract class with a virtual destructor, like the abstract_animal and inherit animal class, allowing for the creation of a std::vector<abstract_animal*>.

There is another useful application of CRTP as well. If you think I am missing any major one and have any suggestions you can always reach me here.

References

Template Object (computer science)

Published at DZone with permission of Vishal Chovatiya. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

Trending

Applying Curiously Recurring Template Pattern in C++

There is various material effectively accessible for "How" and "What" on CRTP. So, I will address the "Where" part that CRTP Applicability.

CRTP and Static Polymorphism In C++

Limiting Object Count With CRTP

CRTP to Avoid Code Duplication

Modern C++ Composite Design Pattern Leveraging CRTP

C++20 Spaceship Operator With the Help of CRTP

Problem

Solution Till C++17 With CRTP

C++20 Solution : Spaceship Operator

Enabling Polymorphic Method Chaining

Enabling Polymorphic Copy Construction in C++ with CRTP

Problem

Solution 1: Dynamic Polymorphism

Solution 2: Static Polymorphism

Closing Words

References

Related

Partner Resources