Home > C++ > C++: Polymorphic cloning and the CRTP (Curiously Recurring Template Pattern)

C++: Polymorphic cloning and the CRTP (Curiously Recurring Template Pattern)


A common problem in C++ occurs when you have an object of an unknown derived type and want to make a copy of it. Consider the following code:

class Vehicle {}

class Car : public Vehicle {}
class Plane : public Vehicle {}
class Train : public Vehicle {}

...
function make_a_copy(Vehicle *v)
{
  Vehicle *copy_of_vehicle = new ????(*v);
}

You can’t just use new Vehicle in this situation because only the base class elements (those from the Vehicle base class) will be available in the copy. So what do we do?

Polymorphic cloning

The solution is to use the commonly-used polymorphic cloning pattern. In this pattern, we define a virtual function – which we’ll call clone() in this article – which when called via an object pointer returns a new object of the correct derived type. For this to work, each derived type must override clone() and return a copy of itself, like this:

class Vehicle
{
public:
    virtual ~Vehicle() {}

	virtual Vehicle *clone() const = 0;
};

class Car : public Vehicle
{
public:
	virtual Car *clone() const { return new Car(*this); }
};

class Plane : public Vehicle
{
public:
	virtual Plane *clone() const { return new Plane(*this); }
};

You can now clone an object which is a derived type of Vehicle like this:

Vehicle *copy_of_vehicle = vehicle_to_copy->clone();

Assuming your objects have appropriately defined copy constructors, this will allocate memory on the heap for a new object of the correct derived type and execute the copy constructor to copy the data into the new object. The following code is a full working example:

#include <iostream>

class Vehicle
{
public:
    virtual ~Vehicle() {}

	virtual Vehicle *clone() const = 0;

	virtual void describe() const = 0;
};

class Car : public Vehicle
{
public:
	virtual Car *clone() const { return new Car(*this); }

	virtual void describe() const
	{
		std::cout << "I am a car" << std::endl;
	}
};

class Plane : public Vehicle
{
public:
	virtual Plane *clone() const { return new Plane(*this); }

	virtual void describe() const
	{
		std::cout << "I am a plane" << std::endl;
	}
};

class FighterPlane : public Plane
{
public:
	virtual FighterPlane *clone() const { return new FighterPlane(*this); }

	virtual void describe() const
	{
		std::cout << "I am a fighter plane" << std::endl;
	}
};

int main()
{
	Vehicle *car = new Car();
	Vehicle *plane = new Plane();
	Vehicle *fighterplane = new FighterPlane();

	car->describe();
	plane->describe();
	fighterplane->describe();

	Vehicle *vehicleUnknown = plane->clone();

	vehicleUnknown->describe();
}

The output is as you would expect:

I am a car
I am a plane
I am a fighter plane
I am a plane

This pattern takes advantage of the fact that when a virtual function in a base class which returns an object of the class’s type is overridden by a derived class, the return type can be changed to that of the derived object’s class type. This is called co-variant return types. Eg. when you define the virtual clone() function in Vehicle as returning an object of type Vehicle, you can override the function in the derived class Plane to return an object of type Plane, and this is not a violation of C++’s strong typing rules. As you can see, the implementation of clone() is essentially the same in each derived class. This is slightly awkward, and – if you have many derived classes – makes the code messier and more error-prone if you forget to implement clone() or copy-paste without changing the object type. What if there was a way to provide the clone() function automatically in each derived type?

The Curiously Recurring Template Pattern (CRTP)

The CRTP is a pattern which has many applications, but its main feature is that you can define a class which derives from a template class where the class being defined is itself a template type parameter. For example, if you have a template class MyTemplateClass and you want to define a class called SomeClass, the following code is valid:

class SomeClass : public MyTemplateClass<SomeClass>

What does this do for us? Well, it means that any function we include in the template class which uses the template type parameter will be duplicated in all the derived classes which use it, with the type name replaced by the name of the class we are defining. Consider the following code:

class Vehicle
{
public:
    virtual ~Vehicle() {}

	virtual Vehicle *clone() const = 0;

	virtual void describe() const = 0;
};

template <typename Derived>
class VehicleCloneable : public Vehicle
{
public:
	virtual Vehicle *clone() const
	{
		return new Derived(static_cast<Derived const &>(*this));
	}
};

In Vehicle, we define the interface that each derived type must implement, namely clone() and describe() in this case, as in the original polymorphic cloning example. In VehicleCloneable, we drive from Vehicle and implement the clone() function using the template type parameter Derived to create an object of the type specified when we define each class which derives from VehicleCloneable. The static_cast is required because *this will reference an object of type VehicleCloneable by default, so we need to down-cast to the correct derived type. Now we can re-implement the other vehicles as follows:

class Car : public VehicleCloneable<Car>
{
public:
	virtual void describe() const
	{
		std::cout << "I am a car" << std::endl;
	}
};

class Plane : public VehicleCloneable<Plane>
{
public:
	virtual void describe() const
	{
		std::cout << "I am a plane" << std::endl;
	}
};

As you can see, each class definition derives from VehicleCloneable using its own type name as the template type parameter. This will cause VehicleCloneable<DerivedVehicleType>::clone() to be inherited by each new derived class. The code in main() remains the same, as does the output.

This works fine as long as we are only using one level of derivation, but what if we want to derive from an already-derived class like this:

class FighterPlane : public Plane

How do we convert this definition to use the CRTP?

class FighterPlane : public VehicleCloneable<????>

Now we have a problem. If we derive from VehicleCloneable<Plane>, the implementation of clone() will return the wrong type – Plane instead of FighterPlane. If we derive from VehicleCloneable<FighterPlane>, we won’t inherit the fields and methods from Plane.

CRTP with Multi-Level Inheritance

To work around this, we have to get creative. We need to supply two template parameters to VehicleCloneable: the type name of the class being defined as we currently use, but also the type name of the class we want to derive from. We re-write VehicleCloneable as follows:

template <typename Base, typename Derived>
class VehicleCloneable : public Base
{
public:
	virtual Base *clone() const
	{
		return new Derived(static_cast<Derived const &>(*this));
	}
};

The key here is that whereas VehicleCloneable used to derive from Vehicle, it now derives from the template type parameter Base, which ensures the proper inheritance of Base‘s fields and methods. We also change the return type of clone() from Vehicle * to Base *, to ensure that a pointer to the correct parent class is returned. We now re-write the definitions of Car and Plane as follows:

class Car : public VehicleCloneable<Vehicle, Car>
...
class Plane : public VehicleCloneable<Vehicle, Plane>
...

We can now also define our FighterPlane as a class derived from Plane as follows:

class FighterPlane : public VehicleCloneable<Plane, FighterPlane>
{
public:
	virtual void describe() const
	{
		std::cout << "I am a fighter plane" << std::endl;
	}
};

Notice that the Base template type parameter is now set to Plane rather than Vehicle, to indicate the desired parent class for FighterPlane. We can now write code such as:

Vehicle *fighterplane = new FighterPlane();

fighterplane->describe();

Vehicle *vehicleUnknown = fighterplane->clone();

vehicleUnknown->describe();

and we will get the expected result.

The constructor forwarding problem

The solution above is all very well if you have:

  • no constructors
  • only default constructors
  • all constructors in all derived classes use the same signature
  • the individual derived classes only use constructors which don’t call any base constructors

Most of the time though in a real world application, the derived classes will have multiple constructors with different signatures, and oftentimes you will want to call a base constructor too. In these cases, you will experience the constructor forwarding problem. Consider the following re-work of the above code:

#include <iostream>

class Vehicle
{
protected:
	int fuelCapacity;

public:
	Vehicle() {}
	Vehicle(int fuelCapacity) : fuelCapacity(fuelCapacity) {}
    virtual ~Vehicle() {}
    virtual Vehicle *clone() const = 0;

    virtual void describe() const = 0;
};

template <typename Base, typename Derived>
class VehicleCloneable : public Base
{
public:
 virtual Base *clone() const
 {
 return new Derived(static_cast<Derived const &>(*this));
 }
};

class Car : public VehicleCloneable<Vehicle, Car>
{
private:
 typedef VehicleCloneable<Vehicle, Car> BaseClass;

public:
 Car() {}
 Car(int fuelCapacity) : BaseClass(fuelCapacity) {}

 virtual void describe() const
 {
 std::cout << "I am a car" << std::endl;
 }
};

class Plane : public VehicleCloneable<Vehicle, Plane>
{
private:
 typedef VehicleCloneable<Vehicle, Plane> BaseClass;

protected:
 int wingSpan;

public:
 Plane() {}
 Plane(int fuelCapacity, int wingSpan) : BaseClass(fuelCapacity), wingSpan(wingSpan) {}

 virtual void describe() const
 {
 std::cout << "I am a plane" << std::endl;
 }
};

class FighterPlane : public VehicleCloneable<Plane, FighterPlane>
{
private:
 typedef VehicleCloneable<Plane, FighterPlane> BaseClass;

protected:
 int numberOfBombs;

public:
 FighterPlane() {}
 FighterPlane(int fuelCapacity, int wingSpan, int numberOfBombs)
 : BaseClass(fuelCapacity, wingSpan), numberOfBombs(numberOfBombs) {}

 virtual void describe() const
 {
 std::cout << "I am a fighter plane" << std::endl;
 }
};

We have given the Vehicle class a fuelCapacity, the Plane class a wingSpan (and the constructor also passes the fuel capacity back to Vehicle), and the FighterPlane class (which is itself derived indirectly from Plane via the CRTP middle-man class VehicleCloneable) a numberOfBombs, and again this classes passes back the fuel capacity and wing span to Plane.

To simplify calling of the base constructor, we define a private typedef in each derived class specifying the templated base class to refer to (called BaseClass).

You might at first glance think this should work nicely, but unfortunately it won’t compile. The problem comes with the fact that the base class constructors being called are all expected to be in VehicleCloneable<…>, not the ‘conceptual’ base classes we want. Adding in the middle-man class distorts the inheritance hierarchy such that the constructor calls can’t be forwarded to the conceptual base classes directly, only via VehicleCloneable.

What if we try to just reference the conceptual base classes directly in our base constructor calls, eg. Vehicle from Car and Plane from FighterPlane? Unfortunately, since we haven’t derived directly from these – rather from VehicleCloneable – the compiler will emit an error saying that the class being referenced in the base constructor call is not a base class.

A horrible workaround

NOTE: The following is just for illustration and should not be used in real applications.

What the compiler is expecting is a bunch of constructors in VehicleCloneable, using every possible set of signatures that all of the derived classes use. The following will compile:

template <typename Base, typename Derived>
class VehicleCloneable : public Base
{
public:
    // These forwarding constructors just pass all the supplied arguments to the base class
	// You have to provide constructors with all the same signatures as any derived class - dumb!
	VehicleCloneable() {}
	VehicleCloneable(int arg1) : Base(arg1) {}
	VehicleCloneable(int arg1, int arg2) : Base(arg1, arg2) {}

	virtual Base *clone() const
	{
		return new Derived(static_cast<Derived const &>(*this));
	}
};

While this works, it is obviously a terrible solution because every time we add a new derived class, or a new constructor to an existing derived class, we have to add a new forwarding constructor with the same signature to VehicleCloneable.

The C++11 solution

If you are using a C++11 compiler which supports constructor inheritance (that includes gcc and clang, but not Visual Studio 2012 or 2013), the solution is trivial and one line long:

template <typename Base, typename Derived>
class VehicleCloneable : public Base
{
public:
    using Base::Base;

	virtual Base *clone() const
	{
		return new Derived(static_cast<Derived const &>(*this));
	}
};

The using line causes all constructors to be automatically inherited from whichever base class is specified in the Base template type parameter, bringing them into whatever specialization of VehicleCloneable we are currently deriving from. To illustrate further, if you have the following base class:

class MyBase
{
public:
  MyBase(int something, float somethingelse) { /* ... */ }
  MyBase(char somechar) { /* ... */ }
};

then the following two code samples behave identically in C++11:

class MyDerived
{
public:
  MyDerived(int a, float b) : MyBase(a, b) {}
  MyDerived(char c) : MyBase(c) {}
};

and:

class MyDerived
{
public:
  using MyBase::MyBase;
};

The using declaration creates a series of new constructors in MyDerived with matching signatures to those in MyBase, simply passing all the arguments to the MyBase constructors and doing nothing else (empty function body). This is the essence of constructor forwarding.

Side Note: As noted by Tim in the comments, in C++11 it is generally preferred to return a std::unique_ptr rather than a naked (unwrapped) pointer from a function. The above code is purely for illustrative purposes.

The C++03 solution

No such luxuries exist in prior versions of C++, and even though solutions exist, they are not entirely transparent as they require syntactical changes to the way your constructors are defined. The most thorough solution is to create a series of templates with varying numbers of type parameters; these act as argument containers whose types can be anything, and can then be passed around in derived and base constructors which all have a unified signature: a single argument whose type is the same as the template used to hold the real arguments. Hence the required syntactical changes to the way you create your constructors.

Alf has written a couple of excellent articles about this, so rather than plagiarize his work, I refer you to his [cppx] C++98 constructor arguments forwarding (v2 posting) and [cppx] 3 ways to mix in a generic cloning implementation articles for further information.

Is it all worth it? Ah screw it, let’s just cheat with macros

We have taken a number of detours to solve the basic problem of allowing polymorphic cloning without having to type in the clone() function, and you have to ask yourself if all the hassle is really worth the effort. The answer depends on your application, but in most cases, probably not when you consider all the downsides. So let’s go back to basics.

C++ macros in the 21st century. Not my first choice for easy-to-maintain code, but in this case, it may be worth it.

Here is how to “solve” the cloning problem with macros:

#define BASE_CLONEABLE(Type) \
	virtual Type *clone() const = 0;

#define CLONEABLE(Type) \
	virtual Type *clone() const { return new Type(*this); }

class Vehicle
{
public:
	BASE_CLONEABLE(Vehicle)

    virtual ~Vehicle() {}
    virtual void describe() const = 0;
};

class Car : public Vehicle
{
public:
 CLONEABLE(Car)

 virtual void describe() const
 {
 std::cout << "I am a car" << std::endl;
 }
};

class Plane : public Vehicle
{
public:
 CLONEABLE(Plane)

 virtual void describe() const
 {
 std::cout << "I am a plane" << std::endl;
 }
};

class FighterPlane : public Plane
{
public:
 CLONEABLE(FighterPlane)

 virtual void describe() const
 {
 std::cout << "I am a fighter plane" << std::endl;
 }
};

Notice that you still have to use the macro in each class, however it is certainly easier to read and less error-prone, as long as you remember to include the macro in each class of course.

I’m a software developer with very limited work capacity due to having the debilitating illness M.E. – please read my article Dying with M.E. as a Software Developer and donate to the crowdfund to help me with my bucket list if you found this article useful. Thank you so much!

References

Here are some great links I found while researching this article:

Stack Overflow: Forwarding Constructor with CRTP

Stack Overflow: What is constructor inheritance?

[cppx] 3 ways to mix in a generic cloning implementation

[cppx] C++98 constructor arguments forwarding (v2 posting).

About these ads
  1. August 23, 2013 at 12:01

    Very interesting article, thanks a lot. Unfortunately without a happy end for c++03, but it’s ok :)

  2. August 23, 2013 at 15:58

    In the end, I find the macro-version much more maintainable than the template one. ;-)

  3. Barry
    August 23, 2013 at 17:23

    In C++11, even on Visual Studio and gcc 4.6 (before inherited constructors was implemented), you could just do perfect forwarding with variadic templates. Not nearly as simple as inherited constructors, but definitely beats macros…

    • August 23, 2013 at 17:27

      Yeah I did have that in mind actually, it was the one version I didn’t bother to the article. You caught me :) The main reason I didn’t is essentially because that’s a ‘fudge’ for partially C++11 compliant compilers, the true C++11 inheriting constructor solution is simple as you said, and those with no C+11 support can’t use variadic templates anyway, as you know.

  4. August 23, 2013 at 21:13

    This sort of CRTP use (the last examples before your macro cases) is perhaps one of the primary arguements for mixins in C++: the ability to inject virtual method override implementations into a class without introducing multiple inheritance or diamond inheritance. The CRTP pattern gets ugly when you want to mix in more than one template and the only remaining visable option in that case is macros, which in theory we’re trying to stop using as a community.

  5. Paul
    August 24, 2013 at 02:19

    For the speed fanatics out there, virtual functions are not required to achieve CRTP, the caveat being functions must be defined in the base:

    template
    struct Base
    {
    const char * getDescription() {return “Base”;}

    void printDescription() {std::cout << "Instance of " << static_cast(this)->getDescription();}
    };

    struct BaseWithSameDescription : public Base {};

    struct BaseWithDifferentDescription : public Base
    {
    const char * getDescription() {return “BaseWithDifferentDescription”;}
    };

    However, if the base inherits from a class with virtual functions (as your example does), it will not matter since instances will have a virtual table anyway.

    Also, the multi-level inheritance issue can be addressed without an extra template parameter if you do not need to create instances of Plane:

    class Vehicle
    {
    protected:
    int fuelCapacity;

    public:
    Vehicle() {}
    Vehicle(int fuelCapacity) : fuelCapacity(fuelCapacity) {}

    virtual Vehicle *clone() const = 0;

    virtual void describe() const = 0;
    };

    template
    class VehicleCloneable : public Base
    {
    public:
    const char * getDescription() const {return “vehicle”;}

    virtual Base *clone() const
    {
    return new Derived(static_cast(*this));
    }

    virtual void describe() const
    {
    std::cout << "I am a " << static_cast(*this)->getDescription();
    }
    };

    template
    class Plane : public VehicleCloneable
    {
    private:
    typedef VehicleCloneable BaseClass;

    protected:
    int wingSpan;

    public:
    Plane() {}
    Plane(int fuelCapacity, int wingSpan) : BaseClass(fuelCapacity), wingSpan(wingSpan) {}

    const char * getDescription() const {return “plane”;}
    };

    class FighterPlane : public Plane
    {
    private:
    typedef Plane BaseClass;

    protected:
    int numberOfBombs;

    public:
    FighterPlane() {}
    FighterPlane(int fuelCapacity, int wingSpan, int numberOfBombs)
    : BaseClass(fuelCapacity, wingSpan), numberOfBombs(numberOfBombs) {}

    const char * getDescription() const {return “fighter plane”;}
    };

    • August 24, 2013 at 02:33

      As you can see, WordPress is hideous when it comes to source code :( You need to enclose it in [ sourcecode lang="cpp" ] (without the spaces near the brackets) I think. Even when I am writing articles, it loves to remove anything inside chevrons randomly, I’m forever going back over pasted source code with templates or #includes in…

      nonetheless, I got the idea so hopefully others will too, thanks very much for taking the time to post! :)

  6. Tim
    August 25, 2013 at 08:52

    I like the idea and the C++11 version is a great solution.
    But I hate the bad examples … junior programmer will copy past these code fragments and then they will introduce bugs.
    Polymorphic base classes must always have a public virtual destructor or a protected destructor one.
    Don’t return naked pointers in C++11. The idiom here is to return a std::unique_ptr unless you want to have covariant returns types.

    • August 25, 2013 at 13:58

      I’m aware of these things, I tried to just make the examples bare bones without any distractions, and when it concerns returning a pointer, the patterns in the article don’t just apply to C++11. Maybe I should have added in a virtual destructor though.

      • Tim
        August 25, 2013 at 20:59

        The virtual destructor is not clutter is just plain correctness that many programmers still forget. I can follow you about the pointer but personally I would mention it in the C++11 section so people pick it up these new idioms.

        • August 25, 2013 at 22:22

          Ok, I concur. I’ve added in virtual destructors (hope I didn’t miss any out) and a note in the C++11 section about std::unique_ptr. Thanks for the feedback!

  7. August 27, 2013 at 12:51

    It would be nice that the clone methods returns C++11 smart pointers instances, don’t you think? :D

  8. August 28, 2013 at 16:08

    Posted on behalf of Nevin Liber:

    If you are going to do all that work, why not just implement type erasure and get inheritance out of the interface?

    Something along the lines of (note: uncomplied and untested):

    class Vehicle
    {
        struct Concept
        {
            virtual ~Concept() = default;
            virtual Concept* clone() const = 0;
            virtual void describe() const = 0;
        };
    
        template
        struct Model final : Concept
        {
            explicit Model(T t) : data(std::move(t)) {}
    
            virtual Model* clone() const override { return new Model(*this); }
            virtual void describe() const override { return data.describe(); }
    
        private:
            T data;
        }
    
        std::unique_ptr object;
    
    public:
        template
        explicit Vehicle(T t) : object(new Model(std::move(t))) {}
    
        Vehicle(Vehicle const& that) : object(that.object->clone()) {}
        Vehicle(Vehicle&&) = default;
        Vehicle& operator=(Vehicle&&) = default;
        Vehicle& operator=(Vehicle const& that) { object.reset(that.object->clone()); return *this; }
    
        void describe() const { return object->describe(); }
    };
    
  9. Rock
    June 24, 2014 at 13:39

    Hi,
    Sorry to reply bit late, just read this post when searching for CRTP.
    Very nicely written, it as easy to understand and could write code myself to see how it works.
    Just a question, for curiosity I thought of deleting all the memory allocated using new keyword and this is what i tried in main function at end.
    delete car;
    delete plane;
    delete fighterplane;
    delete vehicleUnknown;
    Surprisingly the binary crashed with segmentation fault. I am using gcc 4.7 .
    i checked the address for each pointer and saw plane and vehicleUnknown are pointing to same memory address. Why should it do so? Please help

  1. October 11, 2013 at 15:02
  2. October 29, 2013 at 22:39
  3. January 4, 2014 at 00:37

Share your thoughts! Note: to post source code, enclose it in [code lang=...] [/code] tags. Valid values for 'lang' are cpp, csharp, xml, javascript, php etc. To post compiler errors or other text that is best read monospaced, use 'text' as the value for lang.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 563 other followers

%d bloggers like this: