Practical Uses for the "Curiously Recurring Template Pattern"

Practical Uses for the Curiously Recurring Template Pattern

Simulated dynamic binding.
Avoiding the cost of virtual function calls while retaining some of the hierarchical benefits is an enormous win for the subsystems where it can be done in the project I am currently working on.

Benefits of CRTP over an abstract class?

The are several advantages of using CRTP:

• Generic Code - Codebases such as container classes, lists, arrays, etc. Programs that are evaluated at compile time.
• Reusability - Being able to easily use existing code to create new code.
• Efficiency - At the core of a Generic Codebase: objects, function calls, their types, and even their values are determined at compile time instead of runtime, unlike virtual methods that require the runtime overhead from the compiler's and operating system's generated virtual function tables.
• Maintainability - Easier to maintain as there is generally less code to manage, unlike multiple inheritances within complex class hierarchies.
• Reliability - Knowing the code will work for different types not having to worry about the internal implementation.
• Readability - The intent of code is obvious without needing to worry about its internal structure.

---

Some of the disadvantages are found within their complexities:

• Syntax - The syntax is more difficult and a challenge to have it written correctly without any code smells.
• Compiler - Depending on the compiler some messages can be more cryptic or if you don't truly understand the compiler, generated assembly and what happens behind the scenes it can point you to the wrong line of code that is actually producing or invoking the error.
• Linker - There shouldn't be any concerns with the linker as long as the code compiles and objects are linked correctly.
• Debugger - Similar to the compiler the messages can be more cryptic looking and may point to the wrong location in code that is actually causing or triggering the error or exception.
• Readability - It can be a little tougher to read due to the complexity of the required syntax

---

A suggestion to determine which idiom is best to use is to weigh the differences based on what is needed for a particular codebase.

• If you need fast and efficient code that can easily be reused with minimal overhead then CRTP would be the better fit.
• If you need a stronger OOP codebase that utilizes class hierarchies with inheritance, polymorphism, and dynamic and heap memory usages then the later would be a proper fit.

Yet a single codebase can use both idioms and utilize their strengths into an integrated application. It's more about knowing where and when you need each type.

Here's a prime example of a proper way to look at code design practices: I'll use the idea of a simple 3D Graphics Engine to illustrate this method of thinking, planning and developing.

• Use CRTP to create custom containers, iterators, and algorithms that are generic, reusable, efficient and are generated at compile time that will store and do work on your custom objects.
• Use Class Hierarchies to create your custom objects, classes, structures, etc. that you will use throughout your codebase.

---

In a 3D Game Engine; you might have several container classes that will store all of the game's assets such as image files known as textures, fonts, sprites, models, shaders, audio and more. These types of classes that manage the functionality to open, read and parse these files and convert their information into your supported custom data structures would be CRTP at their core yet they can still share concepts of inheritance.

For example, the individual manager classes themselves would be designed in a CRTP manner to handle all of the file loading, creating, storing and cleanup of the memory of your custom objects yet the bulk of them could in themselves inherit from a Singleton Base class object that may or may not require the subclasses to have virtual functions. A class hierarchy might look like this:

• Singleton - An abstract base class the must be inherited from, each of it's derived types can be constructed once per application run. All of the following classes are derived from Singleton.
  
  
  • AssetManager - Manages the storing and clean up of internally stored objects either being a texture, font, gui, model, shader, or audio file...
  • AudioManager - Manages all of the functionality of audio playback.
  • TextureManager - Manages the instance count of different loaded textures, prevents unnecessary duplicate opening, reading, and loading a single file multiple types and prevents generating and storing multiple copies of the same object.
  • FontManager - Manages all of the fonts properties, similar to the TextureManager but designed specifically for handling fonts.
  • SpriteManager - Depending on engine and game type sprites may or may not be used or could, in general, be considered a texture but of a specific type...
  • ShaderManager - Handles all of the shaders for performing lighting and shading operations within the generated frame or scene.
  • GuiManager - Handles all of the Graphical User Interface types of objects your Engine would support such as buttons, radio buttons, sliders, lists boxes, checkboxes, text fields, macro boxes, etc...
  • AnimationManager - Would handle and store all object animations your engine would support.
  • TerrainManager - Responsible for all of the games Terrain information from vertices and normal data to height maps, bump maps, etc, to colored or patterned textures, to various shaders that are associated with the terrain that can also include the skybox or skydome, clouds, sun or moon, and background information. May also include objects such as foilage - grass, trees, bushes, etc...
  • ModelManager - Handles all of the 3D model information generating the necessary 3D meshes for your objects and also handles other internal data such as texture coordinates, index coordinates, and normal coordinates.

As you can see from above each of these manager classes would be designed with CRTP since it provides a way of creating generic structures that can process many different types of objects. Yet the entire class Hierarchy still uses inheritance and may or may not require virtual methods. The later depends on your needs or intent. If you are expecting someone else to reuse your Singleton class to implement their own personal type of manager or some other class that would be a Singleton such as a Logger and or an ExceptionHandler then you might want to require them to have to implement Initialization and Cleanup functions.

Now as for your in-game objects such as the models that would be used in your class or even abstract ideas such as a player and enemies where they would inherit from a general Character class these would generate a class hierarchy that may or may not require the use of virtual methods depending on the particular needs and these classes would not require the CRTP idiom.

This was to give a demonstration on when, where and how to use these idioms properly.

---

If you want to see how the performance differs between the two, what you could end up doing is write two codebases that will perform the same exact task, create one specifically with CRTP and the other without it only using Inheritance and Virtual functions. Then enter those codebases into one of the various online compilers that will generate the different types of assembly instructions for the various types of available compilers that can be used and compare the generated assembly. I like Compiler Explorer that is used by Jason Turner.

why Curiously Recurring Template Pattern (CRTP) works

Recursively-defined types aren't unusual: a linked list is recursive, too. It works because at one point in the cycle you don't need the type to be complete, you only need to know its name.

struct LinkedNode {
    int data;
    LinkedNode *next; // Look ma, no problem
};

In the case of CRTP, that point is here:

Base<Derived>

Instantiating Base for Derived does not require Derived to be complete, only to know that it is a class type. I.e., the following works fine:

template <class>
struct Foo { };

struct Undefined;

Foo<Undefined> myFoo;

Thus, as long as the definition of Base does not require Derived to be complete, everything just works.

C++ Curiously Recurring Template Pattern uses undefined struct compile error

When using the recurring template pattern, the child is an incomplete type in the scope of the parent.

template<class CHILD>
struct Parent
{
    CHILD _child; // <- there, incomplete
};

You cannot instantiate an incomplete type as its definition is not there yet.

So... why is that?

A type become complete when the compiler encounter the closing bracket:

struct Hello {
    // Technically not complete yet
};
// Complete here, we encountered the closing bracket.

Also, parent classes are required to be complete type themselves:

struct Incomplete;

struct NiceTry : Incomplete {}; // ERROR! `Incomplete` is an incomplete type.

---

So we have two rules here: the parent of a class must be complete, and a type is not complete until the closing bracket. Inside the parent of a CRTP, we fail both condition: The parent is evaluated before the class scope (they are also positionned before the class scope in the code) and since the parent of a class must be complete, it must be complete before the child class is. You cannot have mutually complete types in class scope, no matter how hard you try:

struct class2;

struct class1 {
    // Class 2 is incomplete here
};

struct class2 {
    // class1 complete
};

You cannot have both complete at the same time in both scopes.

The same thing happens with CRTP, there is no exceptions there.

---

Also, your code is roughly equivalent to this:

struct class1 {
    class2 instance;
};

struct class2 {
    class1 instance;
};

If you try to compute the size of the types, you run into an infinite recursion. You cannot have a type that contain itself.

---

To fix your problem, don't try to contain the child. Instead, since you know 100% which class is the child, simply cast this:

template<typename Child>
struct parent {

    void common_behavior() {
        child().function1();
        std::cout << child().member1 + child().member2;
    }
    
private:
    auto child() noexcept -> Child& { return *static_cast<Child*>(this); }
    auto child() const noexcept -> Child const& { return *static_cast<Child const*>(this); }
};

And implement the child like that:

struct child1 : parent<child1> {
    void function1() { std::cout << "This is child 1"; }
    int member1, member2;
};

struct child2 : parent<child2> {
    void function1() { std::cout << "This is child 2"; }
    float member1, member2;
};

Live example

Can I use the Curiously Recurring Template Pattern here (C++)?

CRTP or compile-time polymorphism is for when you know all of your types at compile time. As long as you're using addWidget to collect a list of widgets at runtime and as long as fooAll and barAll then have to handle members of that homogenous list of widgets at runtime, you have to be able to handle different types at runtime. So for the problem you've presented, I think you're stuck using runtime polymorphism.

A standard answer, of course, is to verify that the performance of runtime polymorphism is a problem before you try to avoid it...

If you really need to avoid runtime polymorpism, then one of the following solutions may work.

Option 1: Use a compile-time collection of widgets

If your WidgetCollection's members are known at compile time, then you can very easily use templates.

template<typename F>
void WidgetCollection(F functor)
{
  functor(widgetA);
  functor(widgetB);
  functor(widgetC);
}

// Make Foo a functor that's specialized as needed, then...

void FooAll()
{
  WidgetCollection(Foo);
}

Option 2: Replace runtime polymorphism with free functions

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
  // (other virtual methods)
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> defaultFooableWidgets;
  vector<AbstractWidget*> customFooableWidgets1;
  vector<AbstractWidget*> customFooableWidgets2;      

 public:
  void addWidget(AbstractWidget* widget) {
    // decide which FooableWidgets list to push widget onto
  }

  void fooAll() {
    for (unsigned int i = 0; i < defaultFooableWidgets.size(); i++) {
      defaultFoo(defaultFooableWidgets[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets1.size(); i++) {
      customFoo1(customFooableWidgets1[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets2.size(); i++) {
      customFoo2(customFooableWidgets2[i]);
    }
  }
};

Ugly, and really not OO. Templates could help with this by reducing the need to list every special case; try something like the following (completely untested), but you're back to no inlining in this case.

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
};

class WidgetCollection {
 private:
  map<void(AbstractWidget*), vector<AbstractWidget*> > fooWidgets;

 public:
  template<typename T>
  void addWidget(T* widget) {
    fooWidgets[TemplateSpecializationFunctionGivingWhichFooToUse<widget>()].push_back(widget);
  }

  void fooAll() {
    for (map<void(AbstractWidget*), vector<AbstractWidget*> >::const_iterator i = fooWidgets.begin(); i != fooWidgets.end(); i++) {
      for (unsigned int j = 0; j < i->second.size(); j++) {
        (*i->first)(i->second[j]);
      }
    }
  }
};

Option 3: Eliminate OO

OO is useful because it helps manage complexity and because it helps maintain stability in the face of change. For the circumstances you seem to be describing - thousands of widgets, whose behavior generally doesn't change, and whose member methods are very simple - you may not have much complexity or change to manage. If that's the case, then you may not need OO.

This solution is the same as runtime polymorphism, except that it requires that you maintain a static list of "virtual" methods and known subclasses (which is not OO) and it lets you replace virtual function calls with a jump table to inlined functions.

class AbstractWidget {
 public:
  enum WidgetType { CONCRETE_1, CONCRETE_2 };
  WidgetType type;
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> mWidgets;

 public:
  void addWidget(AbstractWidget* widget) {
    widgets.push_back(widget);
  }

  void fooAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      switch(widgets[i]->type) {
        // insert handling (such as calls to inline free functions) here
      }
    }
  }
};

How to use the Curiously recurring template pattern

You forgot public :

class Foo : public LListNode<Foo> {
private:
  Foo* m_next;
public:
  ...

How to instantiate the base class when using the Curiously Recurring Template Pattern?

There is something unsymmetric about using Array as the DerivedType in some cases while using the actual derived type in other cases, as you have presented in your answer.

I would like to suggest a solution that uses a different approach. It uses an "empty derived type" for cases where a "derived type" does not exist.

#include <iostream>
#include <array>

template <unsigned int array_width, typename DataType>
struct empty_derived_type;

template 
  <
    unsigned int array_width, 
    typename DataType, 
    typename DerivedType = empty_derived_type<array_width, DataType>
  >
struct Array {
  std::array<DataType, array_width> _data;

  Array() {
    for(unsigned int index = 0; index < array_width; ++index) _data[index] = 1;
  }

  DerivedType operator/(const double& data) {
    unsigned int column;
    DerivedType new_array;

    for(column = 0; column < array_width; column++) {
      new_array._data[column] = _data[column] / data;
    }
    return new_array;
  }

  friend std::ostream& operator<<( std::ostream &output, const Array &array ) {
    unsigned int column; output << "(";
    for( column=0; column < array_width; column++ ) {
      output << array._data[column];
      if( column != array_width-1 ) {
        output << ", ";
      }
    }
    output << ")"; return output;
  }
};

template <unsigned int array_width, typename DataType>
struct empty_derived_type : public Array
    <
      array_width, 
      DataType, 
      empty_derived_type<array_width, DataType>
    >
{
};

struct Coordinate : public Array<3, double, Coordinate> {
  typedef Array< 3, double, Coordinate > SuperClass;
  double& x;
  double& y;
  double& z;

  Coordinate() : SuperClass{}, x{this->_data[0]}, y{this->_data[1]}, z{this->_data[2]} {}
};

int main() {
  Coordinate coordinate;
  std::cout << "coordinate: " << coordinate << std::endl;

  Coordinate new_coordinate = coordinate / 10.0;
  std::cout << "new_coordinate: " << new_coordinate << std::endl;

  Array<5, int> int_array;
  std::cout << "int_array: " << int_array << std::endl;

  Array<5, int> new_int_array = int_array / 10;
  std::cout << "new_int_array: " << new_int_array << std::endl;
}

The output:

coordinate: (1, 1, 1)
new_coordinate: (0.1, 0.1, 0.1)
int_array: (1, 1, 1, 1, 1)
new_int_array: (0, 0, 0, 0, 0)

Curiously Recurring Template Pattern, Multiple Layers of Inheritance

There were a number of problems with your code, and I lost track of all the things I had to change, but here's a working snippet:

void Main()
{
    Console.WriteLine(Dog.Fido.ToString());
}

public abstract class Enumeration<T> where T : Enumeration<T>
{
    private static IEnumerable<T> enumerateAllValues()
    {
        // Obviously use some caching here
        var fields = typeof(T).GetFields(BindingFlags.Public | BindingFlags.Static | BindingFlags.DeclaredOnly);
        return fields.Select(f => f.GetValue(null)).OfType<T>();
    }

    internal static IEnumerable<T> AllValues { get { return enumerateAllValues();}}

    protected Enumeration(int value, string displayName)
    {
        if (!typeof(T).IsSealed)
            throw new NotSupportedException($"Value objects must be sealed, {typeof(T).Name} is not.");
        this.Value = value;
        this.DisplayName = displayName;
    }

    protected int Value { get; }

    protected string DisplayName { get; }

    public override string ToString() { return DisplayName; }       
        // IEquatable implementation based solely on this.Value
}

public static class Enumeration
{
    public static IEnumerable<T> GetAllValues<T>() where T : Enumeration<T>
    {
        return Enumeration<T>.AllValues;
    }
    // Other helper methods, e.g. T Parse(int), bool TryParse(int, out T), etc.
}

public abstract class AnimalTrait<T> : Enumeration<T>
    where T : AnimalTrait<T>
{
    protected AnimalTrait(int value, string displayName) : base(value, displayName) {; }
}

public struct AnimalTraitValuePair<TAnimalTrait> where TAnimalTrait : AnimalTrait<TAnimalTrait>
{

    public TAnimalTrait AnimalTrait { get; }

    public string Value { get; } // Analogy breaks down here, but lets assume we know that the values of animal traits are always strings.

    public AnimalTraitValuePair(TAnimalTrait animalTrait, string value)
    {
        this.AnimalTrait = animalTrait;
        this.Value = value;
    }

    public override string ToString()
    {
        return $"[{AnimalTrait}, {Value}]";
}
}

public abstract class Animal<TAnimal, TAnimalTrait> : Enumeration<TAnimal>
    where TAnimal : Animal<TAnimal, TAnimalTrait>
    where TAnimalTrait : AnimalTrait<TAnimalTrait>
{
    private readonly IList<AnimalTraitValuePair<TAnimalTrait>> animalTraitValuePairList;

    // All animals have a name
    public string Name { get; }

    protected Animal(int i, string name, IEnumerable<AnimalTraitValuePair<TAnimalTrait>> animalTraitValuePairs)
        : base(i, name)
    {
        animalTraitValuePairList = animalTraitValuePairs.ToList();
        this.Name = name;
    }

    public string this[TAnimalTrait animalTrait]
    {
        get
        {
            return animalTraitValuePairList.First(atvp => atvp.AnimalTrait == animalTrait).Value;
        }
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        sb.AppendLine($"{this.Name}'s traits:");
        foreach (var animalTrait in Enumeration.GetAllValues<TAnimalTrait>())
        {
            sb.AppendLine($"[{animalTrait}, {this[animalTrait]}]");
        }
        return sb.ToString();
    }
}

public sealed class DogTrait : AnimalTrait<DogTrait>
{
    public DogTrait(int i, string name) 
        : base(i, name)
    { }
    public static DogTrait Color = new DogTrait(1, "Color");
    public static DogTrait Size = new DogTrait(2, "Size");
}

public sealed class Dog : Animal<Dog, DogTrait>
{
    public Dog(int i, string name, IEnumerable<AnimalTraitValuePair<DogTrait>> animalTraitValuePairs)
        : base(i, name, animalTraitValuePairs)
    {
    }
    public static Dog Fido = new Dog(1, "Fido", new[] {
        new AnimalTraitValuePair<DogTrait>(DogTrait.Color, "Black"),
        new AnimalTraitValuePair<DogTrait>(DogTrait.Size, "Medium"),
    });
}

Output:

Fido's traits:

[Color, Black]

[Size, Medium]

---

Related Topics