Curiously recurring template pattern: Difference between revisions

Revision as of 08:46, 22 January 2020

Latest revision as of 01:27, 10 June 2025

(33 intermediate revisions by 32 users not shown)

Line 1:

{{Short description|Software design pattern}}

The '''curiously recurring template pattern''' ('''CRTP''') is an idiom in [[C++]] in which a class <code>X</code> derives from a class [[Template (C++)|template]] instantiation using <code>X</code> itself as template argument.<ref>{{cite book | first1=David | last1=Abrahams | authorlink1=David Abrahams (computer programmer) | first2=Aleksey | last2=Gurtovoy | title=C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond |publisher=Addison-Wesley | isbn=0-321-22725-5}}</ref> More generally it is known as '''F-bound polymorphism''', and it is a form of [[F-bounded quantification|''F''-bounded quantification]].

{{useUse dmy dates|date=JanuaryDecember 20122021}}

The '''curiously recurring template pattern''' ('''CRTP''') is an idiom, originally in [[C++]], in which a class <code>X</code> derives from a class [[Template (C++)|template]] instantiation using <code>X</code> itself as a template argument.<ref>{{cite book | first1=David | last1=Abrahams | authorlink1=David Abrahams (computer programmer) | first2=Aleksey | last2=Gurtovoy | title=C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond |publisher=Addison-Wesley | isbn=0-321-22725-5| date=January 2005 }}</ref> More generally it is known as '''F-bound polymorphism''', and it is a form of [[F-bounded quantification|''F''-bounded quantification]].

==History==

The technique was formalized in 1989 as "''F''-bounded quantification."<ref>{{cite web|url=http://staffcs.ustcutexas.edu.cn/~xyfeng/teachingwcook/FOPLpapers/lectureNotesFBound89/CookFBound89.pdf|title=F-Bounded Polymorphism for Object-Oriented Programming|author=William Cook|date=1989|display-authors=etal}}</ref> The name "CRTP" was independently coined by [[Jim Coplien]] in 1995,<ref>{{cite journal | author=Coplien, James O. | title=Curiously Recurring Template Patterns | journal=C++ Report | yeardate=February 1995 | pages=24–27 | url=httphttps://sitesdrive.google.com/afile/gertrudandcope.comd/info1yJPlJ2d_79gxEzicliT_M2Qn2dwOfCOP/Publications/InheritedTemplate.pdfview}}</ref> who had observed it in some of the earliest [[C++]] template code as well as in code examples that Timothy Budd created in his multiparadigm language Leda.<ref>{{cite book | first=Timothy | last=Budd | authorlink=| title=Multiparadigm programming in Leda | publisher=Addison-Wesley | isbn=0-201-82080-3 | year=1994| title-link=Multiparadigm programming in Leda }}</ref> It is sometimes called "Upside-Down Inheritance"<ref>{{Cite web|url=http://www.apostate.com/programming/atlupsidedown.html |title=Apostate Café: ATL and Upside-Down Inheritance |date=2006-03-15 |access-date=2016-10-09 |url-status=bot: unknown |archiveurl=https://web.archive.org/web/20060315072824/http://www.apostate.com/programming/atlupsidedown.html |archivedate=15 March 2006 }}</ref><ref>{{Cite web|url=http://archive.devx.com/free/mgznarch/vcdj/1999/julmag99/atlinherit1.asp |title=ATL and Upside-Down Inheritance |date=2003-06-04 |access-date=2016-10-09 |url-status=bot: unknown |archiveurl=https://web.archive.org/web/20030604104137/http://archive.devx.com/free/mgznarch/vcdj/1999/julmag99/atlinherit1.asp |archivedate=4 June 2003 }}</ref> due to the way it allows class hierarchies to be extended by substituting different base classes.

as well as in code examples that [[Timothy Budd]] created in his multiparadigm language Leda.<ref>{{cite book | first=Timothy | last=Budd | authorlink=Timothy Budd | title=[[Multiparadigm programming in Leda]] | publisher=Addison-Wesley | isbn=0-201-82080-3 | year=1994}}</ref> It is sometimes called "Upside-Down Inheritance"<ref>{{Cite web|url=http://www.apostate.com/programming/atlupsidedown.html |title=Apostate Café: ATL and Upside-Down Inheritance |date=2006-03-15 |access-date=2016-10-09 |url-status=bot: unknown |archiveurl=https://web.archive.org/web/20060315072824/http://www.apostate.com/programming/atlupsidedown.html |archivedate=15 March 2006 |df=dmy }}</ref><ref>{{Cite web|url=http://archive.devx.com/free/mgznarch/vcdj/1999/julmag99/atlinherit1.asp |title=ATL and Upside-Down Inheritance |date=2003-06-04 |access-date=2016-10-09 |url-status=bot: unknown |archiveurl=https://web.archive.org/web/20030604104137/http://archive.devx.com/free/mgznarch/vcdj/1999/julmag99/atlinherit1.asp |archivedate=4 June 2003 |df=dmy }}</ref> due to the way it allows class hierarchies to be extended by substituting different base classes.

The Microsoft Implementation of CRTP in [[Active Template Library]] (ATL) was independently discovered, also in 1995, by Jan Falkin, who accidentally derived a base class from a derived class. Christian Beaumont first saw JanFalkin's code and initially thought it couldn'tcould possiblynot compile in the Microsoft compiler available at the time. Following thisthe revelation that it did indeed work, ChristianBeaumont based the entire ATL and [[Windows Template Library]] (WTL) design on this mistake.{{Citation needed|date=August 2018}}

== General form ==

<sourcesyntaxhighlight lang="cpp">

// The Curiously Recurring Template Pattern (CRTP)

template <class T>

Line 20 ⟶ 21:

// ...

};

</syntaxhighlight>{{clarify|reason=members within Base<T> can use what template and what would that look like?|date=June 2025}}

</source>

Some use cases for this pattern are [[Template metaprogramming#Static polymorphism|static polymorphism]] and other metaprogramming techniques such as those described by [[Andrei Alexandrescu]] in ''[[Modern C++ Design]]''.<ref>{{cite book | first=Andrei | last=Alexandrescu | authorlink=Andrei Alexandrescu | title=[[Modern C++ Design]]: Generic Programming and Design Patterns Applied | publisher=Addison-Wesley | isbn=0-201-70431-5 | year=2001}}</ref>

It also figures prominently in the C++ implementation of the [[Data, Context, and Interaction]] paradigm.<ref>{{cite book | first1=James | last1=Coplien | authorlink1=James Coplien | first2=Gertrud | last2=Bjørnvig | title=[[Lean Architecture]]: for agile software development | publisher=Wiley | isbn=978-0-470-68420-87 | year=2010}}</ref>

In addition, CRTP is used by the C++ standard library to implement the <code>std::enable_shared_from_this</code> functionality.<ref>{{cite web |title=std::enable_shared_from_this |url=https://en.cppreference.com/w/cpp/memory/enable_shared_from_this |access-date=22 November 2022}}</ref>

== Static polymorphism ==

Line 29 ⟶ 31:

Typically, the base class template will take advantage of the fact that member function bodies (definitions) are not instantiated until long after their declarations, and will use members of the derived class within its own member functions, via the use of a [[Type conversion|cast]]; e.g.:

<sourcesyntaxhighlight lang="cpp">

template <class T>

struct Base

Line 48 ⟶ 50:

};

struct Derived : public Base<Derived>

{

void implementation();

static void static_sub_func();

};

</syntaxhighlight>

</source>

In the above example, note in particular that the function <code>Base<Derived>::interface()</code>, though ''declared'' before the existence of the <code>struct Derived</code> is known by the compiler (i.e., before <code>Derived</code> is declared), is not actually ''instantiated'' by the compiler until it is actually ''called'' by some later code which occurs ''after'' the declaration of <code>Derived</code> (not shown in the above example), so that at the time the function "implementationinterface" is instantiated, the declaration of <code>Derived::implementation()</code> is known.

This technique achieves a similar effect to the use of [[virtual function]]s, without the costs (and some flexibility) of [[dynamic polymorphism]]. This particular use of the CRTP has been called "simulated dynamic binding" by some.<ref>{{cite web | url=http://www.pnotepad.org/devlog/archives/000083.html | title=Simulated Dynamic Binding | date=7 May 2003 | accessdate=13 January 2012 | url-status=dead | archiveurl=https://web.archive.org/web/20120209045146/http://www.pnotepad.org/devlog/archives/000083.html | archivedate=9 February 2012 | df=dmy-all }}</ref> This pattern is used extensively in the Windows [[Active Template Library|ATL]] and [[Windows Template Library|WTL]] libraries.

To elaborate on the above example, consider a base class with '''no virtual functions'''. Whenever the base class calls another member function, it will always call its own base class functions. When we derive a class from this base class, we inherit all the member variables and member functions that weren'twere not overridden (no constructors or destructors). If the derived class calls an inherited function which then calls another member function, then that function will never call any derived or overridden member functions in the derived class.

However, if base class member functions use CRTP for all member function calls, the overridden functions in the derived class will be selected at compile time. This effectively emulates the virtual function call system at compile time without the costs in size or function call overhead ([[Virtual method table|VTBL]] structures, and method lookups, multiple-inheritance VTBL machinery) at the disadvantage of not being able to make this choice at runtime.

== Object counter ==

The main purpose of an object counter is retrieving statistics of object creation and destruction for a given class.<ref>{{cite journal | author=Meyers, Scott | title=Counting Objects in C++ | journal=C/C++ Users Journal | yeardate=April 1998 | url=http://www.drdobbs.com/cpp/counting-objects-in-c/184403484}}</ref> This can be easily solved using CRTP:

<sourcesyntaxhighlight lang="cpp">

template <typename T>

struct counter

{

static inline int objects_created = 0;

static inline int objects_alive = 0;

counter()

Line 91 ⟶ 93:

}

};

template <typename T> int counter<T>::objects_created( 0 );

template <typename T> int counter<T>::objects_alive( 0 );

class X : counter<X>

Line 103:

// ...

};

</syntaxhighlight>

</source>

Each time an object of class <code>X</code> is created, the constructor of <code>counter<X></code> is called, incrementing both the created and alive count. Each time an object of class <code>X</code> is destroyed, the alive count is decremented. It is important to note that <code>counter<X></code> and <code>counter<Y></code> are two separate classes and this is why they will keep separate counts of <code>X</code>'s and <code>Y</code>'s. In this example of CRTP, this distinction of classes is the only use of the template parameter (<code>T</code> in <code>counter<T></code>) and the reason why we cannot use a simple un-templated base class.

== Polymorphic chaining ==

Line 113:

When the named parameter object pattern is applied to an object hierarchy, things can go wrong. Suppose we have such a base class:

<sourcesyntaxhighlight lang="cpp">

class Printer

{

Line 127:

ostream& m_stream;

};

</syntaxhighlight>

</source>

Prints can be easily chained:

<sourcesyntaxhighlight lang="cpp">

Printer{(myStream}).println("hello").println(500);

</syntaxhighlight>

</source>

However, if we define the following derived class:

<sourcesyntaxhighlight lang="cpp">

class CoutPrinter : public Printer

{

Line 149:

}

};

</syntaxhighlight>

</source>

we "lose" the concrete class as soon as we invoke a function of the base:

<sourcesyntaxhighlight lang="cpp">

// v----- we have a 'Printer' here, not a 'CoutPrinter'

CoutPrinter().print("Hello ").SetConsoleColor(Color.red).println("Printer!"); // compile error

</syntaxhighlight>

</source>

This happens because 'print' is a function of the base -– 'Printer' -– and then it returns a 'Printer' instance.

The CRTP can be used to avoid such problem and to implement "Polymorphic chaining":<ref>{{cite web|last1=Arena|first1=Marco|title=Use CRTP for polymorphic chaining|url=https://marcoarena.wordpress.com/2012/04/29/use-crtp-for-polymorphic-chaining/|accessdate=15 March 2017|date=29 April 2012}}</ref>

<sourcesyntaxhighlight lang="cpp>

// Base class

template <typename ConcretePrinter>

Line 202:

// usage

CoutPrinter().print("Hello ").SetConsoleColor(Color.red).println("Printer!");

</syntaxhighlight>

</source>

==Polymorphic copy construction==

Line 208:

When using polymorphism, one sometimes needs to create copies of objects by the base class pointer. A commonly used idiom for this is adding a virtual clone function that is defined in every derived class. The CRTP can be used to avoid having to duplicate that function or other similar functions in every derived class.

<sourcesyntaxhighlight lang="cpp">

// Base class has a pure virtual function for cloning

class AbstractShape {

Line 215:

virtual std::unique_ptr<AbstractShape> clone() const = 0;

};

// This CRTP class implements clone() for Derived

template <typename Derived>

Line 220 ⟶ 221:

public:

std::unique_ptr<AbstractShape> clone() const override {

return std::unique_ptrmake_unique<AbstractShape>{new Derived{>(static_cast<Derived const&>(*this)}});

}

Line 227 ⟶ 228:

Shape() = default;

Shape(const Shape&) = default;

Shape(Shape&&) = default;

};

Line 235 ⟶ 237:

class Circle : public Shape<Circle>{};

</syntaxhighlight>

</source>

This allows obtaining copies of squares, circles or any other shapes by <code>shapePtr->clone()</code>.

===Pitfalls===

One issue with static polymorphism is that without using a general base class like "Shape"<code>AbstractShape</code> from the above example, derived classes cannot be stored homogeneously – that is, putting different types derived from the same base class in the same container. For example, a container defined as <code>std::vector<Shape*></code> does not work because <code>Shape</code> is not a class, but a template needing specialization. A container defined as <code>std::vector<Shape<Circle>*></code> can only store <code>Circle</code>s, not <code>Square</code>s. This is because each of the classes derived from the CRTP base class <code>Shape</code> is a unique type. ForA thiscommon reason,solution itto isthis moreproblem commonis to inherit from a shared base class with a virtual destructor, like the <code>AbstractShape</code> example above, allowing for the creation of a <code>std::vector<AbstractShape*></code>.

==Deducing this==

The use of CRTP can be simplified using the [[C++23]] feature ''deducing this''.<ref>{{Cite web|url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0847r7.html|title=Deducing this|date=2021-07-12|author1=Gašper Ažman|author2=Sy Brand|author3=Ben Deane|author4=Barry Revzin

}}</ref><ref>{{Cite web|title=Explicit object parameter|url=https://en.cppreference.com/w/cpp/language/member_functions#Explicit_object_parameter|access-date=27 December 2023}}</ref> For the function <code>signature_dish</code> to call a derived member function <code>cook_signature_dish</code>, <code>ChefBase</code> needs to be a templated type and <code>CafeChef</code> needs to inherit from <code>ChefBase</code>, passing its type as the template parameter.

<syntaxhighlight lang="cpp">

template <typename T>

struct ChefBase

{

void signature_dish()

{

static_cast<T*>(this)->cook_signature_dish();

}

};

struct CafeChef : ChefBase<CafeChef>

{

void cook_signature_dish() {}

};

</syntaxhighlight>

If explicit object parameter is used, <code>ChefBase</code> does not need to be templated and <code>CafeChef</code> can derive from <code>ChefBase</code> plainly. Since the <code>self</code> parameter is automatically deduced as the correct derived type, no casting is required.

<syntaxhighlight lang="cpp">

struct ChefBase

{

template <typename Self>

void signature_dish(this Self&& self)

{

self.cook_signature_dish();

}

};

struct CafeChef : ChefBase

{

void cook_signature_dish() {}

};

</syntaxhighlight>

==See also==

Line 249 ⟶ 295:

{{reflist}}

{{C++ programming language}}

{{use dmy dates|date=January 2012}}

[[Category:Software design patterns]]