Curiously recurring template pattern: Difference between revisions

Revision as of 13:59, 14 September 2021

Revision as of 08:55, 22 December 2021

Line 1:

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

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 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://staff.ustc.edu.cn/~xyfeng/teaching/FOPL/lectureNotes/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 | date=February 1995 | pages=24–27 | url=http://sites.google.com/a/gertrudandcope.com/info/Publications/InheritedTemplate.pdf}}</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=Timothy Budd | 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 |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 Jan's code and initially thought it couldn'tcould not possibly compile in the Microsoft compiler available at the time. Following the revelation that it did indeed work, Christian based the entire ATL and [[Windows Template Library]] (WTL) design on this mistake.{{Citation needed|date=August 2018}}

== General form ==

Line 57 ⟶ 58:

In the above example, note in particular that the function Base<Derived>::implementation(), though ''declared'' before the existence of the struct Derived is known by the compiler (i.e., before Derived is declared), is not actually ''instantiated'' by the compiler until it is actually ''called'' by some later code which occurs ''after'' the declaration of Derived (not shown in the above example), so that at the time the function "implementation" is instantiated, the declaration of Derived::implementation() 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't overridden (no constructors or destructors). If the derived class calls an inherited function which then calls another member function, that function will never call any derived or overridden member functions in the derived class.

Line 156 ⟶ 157:

</syntaxhighlight>

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>

Line 240 ⟶ 241:

===Pitfalls===

One issue with static polymorphism is that without using a general base class like <code>AbstractShape</code> from the above example, derived classes cannot be stored homogeneously &mdash;– 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. A common solution to this problem is 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>.

==See also==

Line 248 ⟶ 249:

==References==

{{reflist}}

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

[[Category:Software design patterns]]