More C++ Idioms/Metafunction
From Wikibooks, the open-content textbooks collection
Contents |
[edit]
Metafunction
[edit] Intent
- To encapsulate a complex type computation algorithm
- To generate a type using compile-time type selection techniques
[edit] Also Known As
[edit] Motivation
Templates is a powerful feature of C++, which can be used to perform arbitrary computations at compile-time, which is known as template metaprogramming. Some of the basic examples of the computations performed at compile-time are: (1) selection of a type based on compile-time constants or (2) computing factorial of a number. As a matter of fact, C++ templates is a turing complete sub-language of C++. Metafunction idiom is the principle way of writing compile-time algorithms in C++.
Algorithms -- compile-time or run-time -- should be encapsulated so that they are easier to use and reuse. Conventionally, run-time algorithms are encapsulated in functions that are invoked, obviously, at run-time. Metafunctions, on the other hand, are compile-time analogs of run-time functions. Traditional functions accept values/objects as parameters and return values/objects. However, metafunctions accept types and compile-time constants as parameters and return types/constants.
[edit] Solution and Sample Code
A metafunction, contrary to its name, is a class template. Implementation of metafunctions is often based on template specializations. For example, consider the following IF metafunction, which is compile-time equivalent of run-time if statement. Depending upon the value of the first parameter, IF metafunction yields either an int or a long in the example below.
template <bool, class L, class R> struct IF { typedef R type; }; template <class L, class R> struct IF<true, L, R> { typedef L type; }; IF<false, int, long>::type i; // is equivalent to long i; IF<true, int, long>::type i; // is equivalent to int i;
Factorial metafunction below is another example showing how a recursive factorial computation algorithm can be encapsulated using C++ templates. This metafunction yields an integral value rather than a type.
template <int N> struct Factorial { enum { value = N * Factorial<N - 1>::value }; }; template <> struct Factorial<0> { enum { value = 1 }; }; // Factorial<4>::value == 24 // Factorial<0>::value == 1 void foo() { int x = Factorial<4>::value; // == 24 int y = Factorial<0>::value; // == 1 }
Metafunction and Type Generator
Metafunction is a more general idiom than the type generator idiom. The intent of metafunction idiom is to encapsulate compile-time computation where as, type generator simplifies specification of a type. Metafunctions that produce type(s) as a result of a compile-time computation are all type generators, albeit more complex. However, not every metafunction is a type generator. For example, the Factorial metafunction shown before produces an integral value, not a type, at the end of the computation. Generally, metafunctions are implemented using compile-time control structures or other metafunctions unlike type generators.
Libraries such as Boost.MPL provide a large collection of metafunctions and compile-time data structures to simplify C++ template metaprogramming.
Higher order metafunctions
These are metafunctions that accept other metafunctions as parameters and use them during computation. This is conceptually is similar a function accepting a pointer to another function or a function object as a parameter at run-time. Only difference is that metafunctions exist only at compile-time. boost::mpl::transform is an example of such a higher order metafunction.
[edit] Known Uses
[edit] Related Idioms
[edit] References
A Deeper Look at Metafunctions -- David Abrahams and Aleksey Gurtovoy
