Curiously recurring template pattern

Last updated

The curiously recurring template pattern (CRTP) is an idiom, originally in C++, in which a class X derives from a class template instantiation using X itself as a template argument. [1] More generally it is known as F-bound polymorphism, and it is a form of F-bounded quantification.

Contents

History

The technique was formalized in 1989 as "F-bounded quantification." [2] The name "CRTP" was independently coined by Jim Coplien in 1995, [3] 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. [4] It is sometimes called "Upside-Down Inheritance" [5] [6] 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 could 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 ]

General form

// The Curiously Recurring Template Pattern (CRTP)template<classT>classBase{// methods within Base can use template to access members of Derived};classDerived:publicBase<Derived>{// ...};

Some use cases for this pattern are static polymorphism and other metaprogramming techniques such as those described by Andrei Alexandrescu in Modern C++ Design . [7] It also figures prominently in the C++ implementation of the Data, Context, and Interaction paradigm. [8] In addition, CRTP is used by the C++ standard library to implement the std::enable_shared_from_this functionality. [9]

Static polymorphism

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 cast; e.g.:

template<classT>structBase{voidinterface(){// ...static_cast<T*>(this)->implementation();// ...}staticvoidstatic_func(){// ...T::static_sub_func();// ...}};structDerived:publicBase<Derived>{voidimplementation();staticvoidstatic_sub_func();};

In the above example, the function Base<Derived>::interface(), 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 "interface" is instantiated, the declaration of Derived::implementation() is known.

This technique achieves a similar effect to the use of virtual functions, without the costs (and some flexibility) of dynamic polymorphism. This particular use of the CRTP has been called "simulated dynamic binding" by some. [10] This pattern is used extensively in the Windows ATL and 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 were 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 (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. [11] This can be easily solved using CRTP:

template<typenameT>structcounter{staticinlineintobjects_created=0;staticinlineintobjects_alive=0;counter(){++objects_created;++objects_alive;}counter(constcounter&){++objects_created;++objects_alive;}protected:~counter()// objects should never be removed through pointers of this type{--objects_alive;}};classX:counter<X>{// ...};classY:counter<Y>{// ...};

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

Polymorphic chaining

Method chaining, also known as named parameter idiom, is a common syntax for invoking multiple method calls in object-oriented programming languages. Each method returns an object, allowing the calls to be chained together in a single statement without requiring variables to store the intermediate results.

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

classPrinter{public:Printer(ostream&pstream):m_stream(pstream){}template<typenameT>Printer&print(T&&t){m_stream<<t;return*this;}template<typenameT>Printer&println(T&&t){m_stream<<t<<endl;return*this;}private:ostream&m_stream;};

Prints can be easily chained:

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

However, if we define the following derived class:

classCoutPrinter:publicPrinter{public:CoutPrinter():Printer(cout){}CoutPrinter&SetConsoleColor(Colorc){// ...return*this;}};

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

//                           v----- we have a 'Printer' here, not a 'CoutPrinter'CoutPrinter().print("Hello ").SetConsoleColor(Color.red).println("Printer!");// compile error

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": [12] 

// Base classtemplate<typenameConcretePrinter>classPrinter{public:Printer(ostream&pstream):m_stream(pstream){}template<typenameT>ConcretePrinter&print(T&&t){m_stream<<t;returnstatic_cast<ConcretePrinter&>(*this);}template<typenameT>ConcretePrinter&println(T&&t){m_stream<<t<<endl;returnstatic_cast<ConcretePrinter&>(*this);}private:ostream&m_stream;};// Derived classclassCoutPrinter:publicPrinter<CoutPrinter>{public:CoutPrinter():Printer(cout){}CoutPrinter&SetConsoleColor(Colorc){// ...return*this;}};// usageCoutPrinter().print("Hello ").SetConsoleColor(Color.red).println("Printer!");

Polymorphic copy construction

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.

// Base class has a pure virtual function for cloningclassAbstractShape{public:virtual~AbstractShape()=default;virtualstd::unique_ptr<AbstractShape>clone()const=0;};// This CRTP class implements clone() for Derivedtemplate<typenameDerived>classShape:publicAbstractShape{public:std::unique_ptr<AbstractShape>clone()constoverride{returnstd::make_unique<Derived>(static_cast<Derivedconst&>(*this));}protected:// We make clear Shape class needs to be inheritedShape()=default;Shape(constShape&)=default;Shape(Shape&&)=default;};// Every derived class inherits from CRTP class instead of abstract classclassSquare:publicShape<Square>{};classCircle:publicShape<Circle>{};

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

Pitfalls

One issue with static polymorphism is that without using a general base class like AbstractShape 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 std::vector<Shape*> does not work because Shape is not a class, but a template needing specialization. A container defined as std::vector<Shape<Circle>*> can only store Circles, not Squares. This is because each of the classes derived from the CRTP base class Shape is a unique type. A common solution to this problem is to inherit from a shared base class with a virtual destructor, like the AbstractShape example above, allowing for the creation of a std::vector<AbstractShape*>.

Deducing this

The use of CRTP can be simplified using the C++23 feature deducing this. [13] [14] For the function signature_dish to call a derived member function cook_signature_dish, ChefBase needs to be a templated type and CafeChef needs to inherit from ChefBase, passing its type as the template parameter.

template<typenameT>structChefBase{voidsignature_dish(){static_cast<T*>(this)->cook_signature_dish();}};structCafeChef:ChefBase<CafeChef>{voidcook_signature_dish(){}};

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

structChefBase{template<typenameSelf>voidsignature_dish(thisSelf&&self){self.cook_signature_dish();}};structCafeChef:ChefBase{voidcook_signature_dish(){}};

See also

Related Research Articles

Templates are a feature of the C++ programming language that allows functions and classes to operate with generic types. This allows a function or class declaration to reference via a generic variable another different class without creating full declaration for each of these different classes.

The bridge pattern is a design pattern used in software engineering that is meant to "decouple an abstraction from its implementation so that the two can vary independently", introduced by the Gang of Four. The bridge uses encapsulation, aggregation, and can use inheritance to separate responsibilities into different classes.

In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. It is a kind of lazy evaluation that refers specifically to the instantiation of objects or other resources.

In object-oriented programming, the decorator pattern is a design pattern that allows behavior to be added to an individual object, dynamically, without affecting the behavior of other instances of the same class. The decorator pattern is often useful for adhering to the Single Responsibility Principle, as it allows functionality to be divided between classes with unique areas of concern as well as to the Open-Closed Principle, by allowing the functionality of a class to be extended without being modified. Decorator use can be more efficient than subclassing, because an object's behavior can be augmented without defining an entirely new object.

Template metaprogramming (TMP) is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates can include compile-time constants, data structures, and complete functions. The use of templates can be thought of as compile-time polymorphism. The technique is used by a number of languages, the best-known being C++, but also Curl, D, Nim, and XL.

A method in object-oriented programming (OOP) is a procedure associated with an object, and generally also a message. An object consists of state data and behavior; these compose an interface, which specifies how the object may be used. A method is a behavior of an object parametrized by a user.

In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:

In programming language theory and type theory, polymorphism is the use of one symbol to represent multiple different types.

In object-oriented programming such as is often used in C++ and Object Pascal, a virtual function or virtual method is an inheritable and overridable function or method that is dispatched dynamically. Virtual functions are an important part of (runtime) polymorphism in object-oriented programming (OOP). They allow for the execution of target functions that were not precisely identified at compile time.

In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type, or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which type is in use. It can be thought of as a type that has several "cases", each of which should be handled correctly when that type is manipulated. This is critical in defining recursive datatypes, in which some component of a value may have the same type as that value, for example in defining a type for representing trees, where it is necessary to distinguish multi-node subtrees and leaves. Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.

In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.

In the C++ programming language, a reference is a simple reference datatype that is less powerful but safer than the pointer type inherited from C. The name C++ reference may cause confusion, as in computer science a reference is a general concept datatype, with pointers and C++ references being specific reference datatype implementations. The definition of a reference in C++ is such that it does not need to exist. It can be implemented as a new name for an existing object.

<span class="mw-page-title-main">Method overriding</span> Language feature in object-oriented programming

Method overriding, in object-oriented programming, is a language feature that allows a subclass or child class to provide a specific implementation of a method that is already provided by one of its superclasses or parent classes. In addition to providing data-driven algorithm-determined parameters across virtual network interfaces, it also allows for a specific type of polymorphism (subtyping). The implementation in the subclass overrides (replaces) the implementation in the superclass by providing a method that has same name, same parameters or signature, and same return type as the method in the parent class. The version of a method that is executed will be determined by the object that is used to invoke it. If an object of a parent class is used to invoke the method, then the version in the parent class will be executed, but if an object of the subclass is used to invoke the method, then the version in the child class will be executed. This helps in preventing problems associated with differential relay analytics which would otherwise rely on a framework in which method overriding might be obviated. Some languages allow a programmer to prevent a method from being overridden.

<i>Modern C++ Design</i> Book by Andrei Alexandrescu

Modern C++ Design: Generic Programming and Design Patterns Applied is a book written by Andrei Alexandrescu, published in 2001 by Addison-Wesley. It has been regarded as "one of the most important C++ books" by Scott Meyers.

A class in C++ is a user-defined type or data structure declared with any of the keywords class, struct or union that has data and functions as its members whose access is governed by the three access specifiers private, protected or public. By default access to members of a C++ class declared with the keyword class is private. The private members are not accessible outside the class; they can be accessed only through member functions of the class. The public members form an interface to the class and are accessible outside the class.

C++11 is a version of a joint technical standard, ISO/IEC 14882, by the International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC), for the C++ programming language. C++11 replaced the prior version of the C++ standard, named C++03, and was later replaced by C++14. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

Substitution failure is not an error (SFINAE) is a principle in C++ where an invalid substitution of template parameters is not in itself an error. David Vandevoorde first introduced the acronym SFINAE to describe related programming techniques.

Expression templates are a C++ template metaprogramming technique that builds structures representing a computation at compile time, where expressions are evaluated only as needed to produce efficient code for the entire computation. Expression templates thus allow programmers to bypass the normal order of evaluation of the C++ language and achieve optimizations such as loop fusion.

In computer programming, variadic templates are templates that take a variable number of arguments.

"typename" is a keyword in the C++ programming language used when writing templates. It is used for specifying that a dependent name in a template definition or declaration is a type. In the original C++ compilers before the first ISO standard was completed, the typename keyword was not part of the C++ language and Bjarne Stroustrup used the class keyword for template arguments instead. While typename is now the preferred keyword, older source code may still use the class keyword instead.

References

  1. ↑ Abrahams, David; Gurtovoy, Aleksey (January 2005). C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond. Addison-Wesley. ISBN   0-321-22725-5.
  2. ↑ William Cook; et al. (1989). "F-Bounded Polymorphism for Object-Oriented Programming" (PDF).
  3. ↑ Coplien, James O. (February 1995). "Curiously Recurring Template Patterns". C++ Report: 24–27.
  4. ↑ Budd, Timothy (1994). Multiparadigm programming in Leda. Addison-Wesley. ISBN   0-201-82080-3.
  5. ↑ "Apostate Café: ATL and Upside-Down Inheritance". 15 March 2006. Archived from the original on 15 March 2006. Retrieved 9 October 2016.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  6. ↑ "ATL and Upside-Down Inheritance". 4 June 2003. Archived from the original on 4 June 2003. Retrieved 9 October 2016.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  7. ↑ Alexandrescu, Andrei (2001). Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley. ISBN   0-201-70431-5.
  8. ↑ Coplien, James; Bjørnvig, Gertrud (2010). Lean Architecture: for agile software development. Wiley. ISBN   978-0-470-68420-7.
  9. ↑ "std::enable_shared_from_this" . Retrieved 22 November 2022.
  10. ↑ "Simulated Dynamic Binding". 7 May 2003. Archived from the original on 9 February 2012. Retrieved 13 January 2012.
  11. ↑ Meyers, Scott (April 1998). "Counting Objects in C++". C/C++ Users Journal.
  12. ↑ Arena, Marco (29 April 2012). "Use CRTP for polymorphic chaining" . Retrieved 15 March 2017.
  13. ↑ Gašper Ažman; Sy Brand; Ben Deane; Barry Revzin (12 July 2021). "Deducing this".
  14. ↑ "Explicit object parameter" . Retrieved 27 December 2023.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.