Introduction
Templates form the basis for generic programming. So, templates are usually used to define generic containers or algorithms that operates on different types. But apart from it, templates can be used in various contexts to solve certain problems. This article tries to cover some of the template programming techniques and idioms, most of them falls in to the metaprogramming category.
Curiously Recurring Template Pattern (CRTP)
Imagine a situation, where you have to create a base class which has several static members; many derived classes inherit the base class, but you want the static members to be unique for each derived class. Curiously Recurring Template Pattern (CRTP) is the solution.
template <class>
class Base {
public:
static int a;
};
class Derived1 : public Base <Derived1>
{
public:
Derived1()
{
a = 1; }
};
int Base<Derived1>::a;
class Derived2 : public Base <Derived2>
{
public:
Derived2()
{
a = 2; }
};
int Base<Derived2>::a;
int main()
{
Derived1 d1;
Derived2 d2;
cout << "Base<Derived1>::a = " << Base<Derived1>::a << endl; cout << "Base<Derived2>::a = " << Base<Derived2>::a << endl; return 0;
}
We know that template instantiation is class creation. In this example, each derived class is derived from each instantiation of the class template "Base".
Template Instantiation for Use Without Any Instance
You can also instantiate classes with static members to operate on different classes. For example, consider a class which maps enum items to strings. Here is a without-template version:
enum Animals
{
Dog, Cat, Lion, Tiger
};
enum Directions
{
North, South, East, West
};
class EnumMap
{
private:
EnumMap() {}
public:
static map <int, string> m_Map;
};
map <int, string> EnumMap::m_Map;
int main()
{
EnumMap::m_Map[Dog] = "Dog is a pet animal";
EnumMap::m_Map[North] = "North is a direction";
cout << EnumMap::m_Map[Dog] << endl; return 0;
}
The above program doesn't produce the desired output. Templates can solve this problem.
enum Animals
{
Dog, Cat, Lion, Tiger
};
enum Directions
{
North, South, East, West
};
template <typename>
class EnumMap
{
private:
EnumMap() {}
public:
static map <int, string> m_Map;
};
map <int, string> EnumMap<Animals>::m_Map;
map <int, string> EnumMap<Directions>::m_Map;
typedef EnumMap<Animals> AnimalsMap;
typedef EnumMap<Directions> DirectionsMap;
int main()
{
AnimalsMap::m_Map[Dog] = "Dog is a pet animal";
DirectionsMap::m_Map[North] = "North is a direction";
cout << AnimalsMap::m_Map[Dog] << endl; return 0;
}
In this code, the class template EnumMap is instantiated for each enum type. Though enums are integral, according to the compiler they are actually different types.
Traits
Traits are classes which encapsulate properties of different types. The following is a simple traits type:
template <typename>
struct is_int
{
enum { value = false };
};
template <>
struct is_int <int> {
enum { value = true };
};
int main()
{
int i = 2;
char j = '2';
cout << is_int <decltype(i)>::value << endl; cout << is_int <decltype(j)>::value << endl; cout << is_int <int>::value << endl; cout << is_int <char>::value << endl; return 0;
}
As you can see, traits are based on the concept of specialization of templates.
Note: You don't have to create type traits for primitive data types. They are already implemented in the STL. Include the standard header "type_traits" to use them.
Nested Class Template Specialization Depending on Template Parameter of the Containing Class
It is possible, that you can specialize a nested class template based on the template parameter of the class which contains it. See the following example which implements a complex way just to compare two integers:
template <int val1, int val2>
struct EqualityChecker
{
template <int>
struct Local
{
enum { value = false };
};
template <>
struct Local <val1> {
enum { value = true };
};
enum { value = Local<val2>::value }; };
int main()
{
cout << EqualityChecker<3, 3>::value << endl; cout << EqualityChecker<5, 3>::value << endl; return 0;
}
Visualize the instantiation of the template EqualityChecker<int, int=""> when the parameters are 3 and 3.
struct EqualityChecker_3_3 {
template <int>
struct Local
{
enum { value = false };
};
template <>
struct Local <3> {
enum { value = true };
};
enum { value = Local<3>::value }; };
This is how the compiler instantiates EqualityChecker when we pass 3 and 3. You can see the how Local is specialized.
Substitution Failure Is Not An Error (SFINAE)
This occurs during overload resolution (when it resolves overloads) of function templates. When substituting the deduced type for the template parameter fails, the compiler won't stop with a compilation error. Instead, that specific specialization is discarded and the compiler skips to the next.
struct Example
{
typedef int type;
};
template <typename T>
void Func(typename T::type t) {
cout << "Function 1 is called" << endl;
}
template <typename T>
void Func(T y)
{
cout << "Function 2 is called" << endl;
}
int main()
{
Func<int>(10); return 0;
}
There are two potential overloads that take a single typename parameter. But, the first overload of "Func" is discarded as there is no int::type.
The Enable If Idiom
Using enable if you can let the compiler select a overload based on a compile-time boolean expression. This powerful technique is made possible by the feature of SFINAE. The following is a Enable_if class(we use capital "E" to avoid name clash with std::enable_if):
template <bool, class T = void>
struct Enable_if { };
template <class T>
struct Enable_if<true, T>
{
typedef T type;
};
Enable If, like other techniques, is also based on specialization. The specialized version of enable_if with the parameter "true" defines the type; otherwise, no type is defined. See the following example:
template <int v>
typename Enable_if<( v > 0 && v < 1000)>::type PrintNumber()
{
cout << "(( v > 0 && v < 1000) == true) and v = " << v << endl;
}
template <int v>
typename Enable_if<( v > 1000 && v < 2000)>::type PrintNumber()
{
cout << "(( v > 1000 && v < 2000) == true) and v = " << v << endl;
}
int main()
{
PrintNumber<500>(); PrintNumber<1020>(); return 0;
}
Here, there are two matching overloads. So the compiler goes to the first one and sees the Enable_if. We already know that the Enable_if won't contain "type" unless the boolean expression evaluates to true. So, if the expression evaluates to false, the compiler discards the overload and goes to the next (SFINAE). When the expression evaluates to true, it is already known that Enable_if's specialization for true has "type", so the function will get successfully compiled.
Note: If "v" doesn't obey both the conditions, a compilation error will occurs. Also, you can use std::enable_if instead of this implementation. The usage method is exactly the same, the above implementation is just to show how enable if works.
Parameterized Base Class Idiom - Inheriting from T
This is a technique in which the instantiation created out of a template is inherited from the parameter itself.
class Base
{
public:
int a;
};
template <typename T>
class DerivedClass : public T
{
};
int main()
{
DerivedClass<Base> test;
test.a = 3;
return 0;
}
The above code is self-explanatory. Here, DerivedClass<Base> is derived from Base.
Combining Parameterized Base Class and Enable if idioms
What if you want to make sure that your class is only inherited from a certain set of classes. The solution is simple - use Enable if. Example:
template <typename>
struct isSupportedClass
{
enum { value = false };
};
#define ADD_SUPP_CLASS(x) template <> struct isSupportedClass<x> { enum { value = true }; };
class SupportedClass1 {};
class SupportedClass2 {};
class SupportedClass3 {};
ADD_SUPP_CLASS(SupportedClass1);
ADD_SUPP_CLASS(SupportedClass2);
ADD_SUPP_CLASS(SupportedClass3);
template <typename T>
class DerivedClass : public Enable_if<isSupportedClass<T>::value, T>::type
{};
class UnsupportedClass {};
int main()
{
DerivedClass<SupportedClass1> test; DerivedClass<UnsupportedClass> test2; return 0;
}
As you can see, we have passed a boolean expression which checks whether "T" is a supported class using those specializations. Only if the condition is true, the compile will be successful.
Template Metaprogramming
What is it?
Template metaprogramming is a powerful technique used to write metaprograms using templates. C++ templates are a Turing complete language that means, everything that is computable is computable using C++ templates. While processing templates, the C++ compiler acts as an interpreter, or more like a calculator.
Template metaprogramming actually owes its origin to 1994. Surprisingly, no one knew about the feature until it was discovered.
How it Works
Template metaprogramming is made possible because of the following:
- Non-type template parameters. Example:
template <int i>
struct Example {
enum { sqr = i * i };
};
What can be a non-type parameter?
The C++ Standard Says[14.1 - Template parameters]:
"A non-type template-parameter shall have one of the following (optionally cv-qualified) types:
— integral or enumeration type,
— pointer to object or pointer to function
— reference to object or reference to function,
— pointer to member."
- Expression parsing done by the compiler while creating a template instantiation. Example:
cout << Example <(2 + 2) * 3>::sqr;
As you can see, in the above code, the expression is actually calculated not in the runtime but compile time.
What actually happens here? Firstly, the compiler creates instantiates the Example template and creates a new class named Example <12> after parsing "(2 + 2) * 3". Imagine how Example <12> looks like :
struct Example_12
{
enum { sqr = 144 };
};
- Allowing recursion in static members and enum initialization.
template <int i>
class Example
{
enum { value = Example<i+1>::value };
};
By default, the MSVC compiler allows up to 500 recursion, whereas the GCC goes up to the depth of 900 recursion.
An Example
template <int n>
struct factorial
{
enum { value = n * factorial<n-1>::value };
};
template <>
struct factorial<0>
{
enum { value = 1 };
};
int main()
{
cout << factorial<5>::value; return 0;
}
In the above program, the result is calculated during compile-time by the compiler.
In the assembly file generated out of this code you can find,
; Note : this is actually a very small part of the file. The total file is around 150 KB.
mov esi, esp
push 120
mov ecx, DWORD PTR __imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A
call DWORD PTR __imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QAEAAV01@H@Z
Surprisingly, the code just pushes 120 and calls "cout" - no recursive functions, not even the word "factorial" is in the assembly file. This is because, the factorial is calculated by the compiler.
Why Template Metaprogramming?
Always, run-time computations make your program slower than compile-time computations. But at most places, if not all, compile-time computations is not of that use. Take for instance, you can't do anything with the above factorial sample during runtime. But there are also places where compile-time computations improves readability,
template <unsigned long N>
struct binary
{
enum { value = binary<N/10>::value << 1 | N%10 };
};
template <>
struct binary<0>
{
enum { value = 0 };
};
int main()
{
cout << binary<1101>::value << endl; cout << 13 << endl; return 0;
}
Using "binary<1101>::value" is more readable than using magic numbers. Also no loss is in performance. But if you implement this algorithm without metaprogramming, your program WILL lose performance.
Regarding other than compile-time computations, bear in mind that, the compiler's knowledge about your program in compile-time is much more than your program's knowledge about itself during run-time. This makes metaprogramming much safer.
Test of Convertibility
How can you check whether a type can be implicitly converted to another? The following trick can do it:
template<class T, class U>
class TestConversion
{
typedef char Small; class Big { char dummy[2]; };
static Small Test(U); static Big Test(...);
static T MakeT(); public:
enum
{
value = sizeof(Test(MakeT())) == sizeof(Small)
};
};
class Base {};
class Derived : public Base {};
int main()
{
cout << TestConversion<int, char *>::value << endl; cout << TestConversion<Derived, Base>::value << endl; cout << TestConversion<Base, Derived>::value << endl; return 0;
}
In the class template "TestConversion", "value" is determined based on the template parameters. As you can see, the class compares the size of the "return types" of the two overloads. The class defines two typedefs Small and Big - both are intentionally of different sizes.
See here,
sizeof(Test(MakeT())) == sizeof(Small)
In the left hand side, the "sizeof" operator is used. There MakeT() which returns a "T" is called. Compiler knows it - MakeT() is not executed.
If T implicitly converts to U, the first overload is selected and the size of "Test" will become the size of "Small" which is the value of RHS, so "value" evaluates to true.
See the following visualization of TestConversion<Derived, Base>:
class TestConversion_Derived_Base {
typedef char Small;
class Big { char dummy[2]; };
static Small Test(Base); static Big Test(...);
static Derived MakeT();
public:
enum
{
value = sizeof(Test(MakeT())) == sizeof(Small) };
};
This is the way it is instantiated.
Typelists
Typelists are a way to create compile-time lists of type names. The following is a typelist:
struct NullType {};
template <typename val, typename next>
struct TypeList
{
typedef val Val; typedef next Next; };
#define TYPELIST_1(T1) TypeList<T1, NullType>
#define TYPELIST_2(T1, T2) TypeList<T1, TYPELIST_1(T2)>
#define TYPELIST_3(T1, T2, T3) TypeList<T1, TYPELIST_2(T2, T3)>
#define TYPELIST_4(T1, T2, T3, T4) TypeList<T1, TYPELIST_3(T2, T3, T4)>
#define TYPELIST_5(T1, T2, T3, T4, T5) TypeList<T1, TYPELIST_4(T2, T3, T4, T5)>
template <typename TLIST, int pos> struct GetAt {};
template <typename HEAD, typename TAIL, int pos>
struct GetAt<TypeList<HEAD, TAIL>, pos>
{
typedef typename GetAt<TAIL, pos-1>::type type;
};
template <typename T, typename TAIL>
struct GetAt<TypeList<T, TAIL>, 0>
{
typedef T type;
};
template <int pos>
struct GetAt<NullType, pos> {};
template <typename list, typename item>
struct HasItem { enum { value = false }; };
template <typename h, typename t, typename item>
struct HasItem<TypeList<h, t>, item>
{
enum { value = HasItem<t, item>::value };
};
template <typename h, typename t>
struct HasItem<TypeList<h, t>, h>
{
enum { value = true };
};
class Class1 {};
class Class2 {};
typedef TYPELIST_4(int, float, char, Class1) MyList;
int main()
{
cout << (GetAt<MyList, 0>::type)(97.03) << endl; cout << (GetAt<MyList, 1>::type)(97.03) << endl; cout << (GetAt<MyList, 2>::type)(97.03) << endl << endl; cout << HasItem<MyList, Class1>::value << endl; cout << HasItem<MyList, Class2>::value << endl; return 0;
}
Typelists works like linked lists, but typelists are compile-time.
GetAt gets the item at the specified index.
HasItem checks whether an item exists.
Combining Parameterized Base Class idiom, Typelists and Test of Convertibility
We have seen a class which restricts the template parameter to certain set of classes. Here is a equivalent of the same program using Typelists and TestConversion. Sometimes you may want to enable the user create classes that are supported.
class SupportedClass1 {};
class SupportedClass2 {};
class SupportedClass3 {};
class SupportedBase {};
typedef TYPELIST_3(SupportedClass1, SupportedClass2, SupportedClass3) SupportedClasses;
template <typename T>
class DerivedClass : public Enable_if< (HasItem<SupportedClasses, T>::value || TestConversion<T, SupportedBase>::value),
T
>::type
{};
class SupportedClass4 : public SupportedBase {};
class UnsupportedClass {};
int main()
{
DerivedClass<SupportedClass1> a;
DerivedClass<SupportedClass2> b;
DerivedClass<SupportedClass3> c;
DerivedClass<SupportedClass4> d;
DerivedClass<UnsupportedClass> e; return 0;
}
In this example, the "DerivedClass" accepts a class as a parameter if:
- It is one of the classes in the typelist (or)
- It derives from SupportedBase.
This example removes all those specializations and macros from the previous example and replaces them with typelists.
A Problem in the Above Program
The DerivedClass in the above program accepts a class if it can implicitly convert to SupportedBase. But what will happen if the class didn't derive from SupportedBase and it implements a "operator SupportedBase()"? DerivedClass will get cheated. Detecting whether a class derives from SupportedBase precisely may fix the problem.
The following class tests whether T is derived from X:
template<class T, class R>
T base_of(R T::*);
template <typename T, typename X>
struct IsDerivedFromX {
typedef char Small;
class Big { char dummy[2]; };
static Small test(X);
static Big test(T);
static decltype(base_of(&T::testFunction)) MakeBase();
enum { value = (sizeof(test(MakeBase())) == sizeof(Small)) };
};
Use it in the previous code:
class SupportedBase {
public:
void testFunction(); };
template <typename T>
class DerivedClass : public Enable_if< IsDerivedFromX<T, SupportedBase>::value,
T
>::type
{};
class SupportedClass4 : public SupportedBase {};
class UnsupportedClass {
public:
operator SupportedBase()
{
return SupportedBase();
}
};
int main()
{
DerivedClass<SupportedClass4> a;
DerivedClass<UnsupportedClass> e; return 0;
}
Here, the typelists and the TestConversion are removed. Instead the checking is done using IsDerivedFromX class.
Disadvantages of Templates
"Be careful about the complexity of the templates you write or use; it is easy to get overenthusiastic and write template code that is too clever to be useful as maintainable production code." - Bjarne Stroustrup
Be cautious about when and why to use templates. I also like to mention some disadvantages of using templates.
Code Bloat. This is one of the most frequently regarded disadvantages of templates. It is already said that, generic programming is a technique of writing algorithms that can be used with any type. That being said, We know what is instantiation. But what happens when any template, let it be class of function, is instantiated? Simple, a new function or class is created. Consider the following code:
template <typename> class MyClass {};
int main()
{
MyClass<int> a; vector<MyClass<char>> b; vector<MyClass<MyClass<float>>> c; vector<MyClass<MyClass<MyClass<char *>>>> d; return 0;
}
In this very small program, 10 new classes are created.
Slow Compilation Speeds. Templates, especially metaprogramming can easily contribute to slow compile speeds, as it is obvious that the calculations are done in the compile-time. Given the strength of today's CPUs and RAM, this may not be a real issue. But what if your project has about 1000000 lines of codes.
Incomprehensible Error Messages. Some C++ compilers fail to define template errors precisely. This makes finding the error difficult. A very simple error may produce some 100 lines of error messages. The following image shows a typical error message from the GCC compiler:
Member function templates can't be virtual(!). You can't make any function templates that are members of classes virtual. For example,
class Class
{
public:
template <typename>
virtual void Function1()
{
}
};
This code will produce a compilation error stating that,
error C2898: 'void Class::Function1(void)' : member function templates cannot be virtual
Conclusion
This article has explained some template techniques and idioms. These techniques show the uses of templates other than in generics algorithms and container classes. Though, what I have presented here is very few; there are always more than these. You can also have a look at the Boost C++ libraries.
Bibliography
Modern C++ Design: Generic Programming and Design Patterns Applied - by Andrei Alexandrescu
C++ Templates: The Complete Guide - by David Vandevoorde and Nicolai M. Josuttis
C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond - By David Abrahams and Aleksey Gurtovoy
Online
Boost Website
A gentle introduction to Template Metaprogramming with C++
TMPP: Template Metaprogramming Programming
History
30/6/2013 - Initial Post
4/7/2013 - Corrected some typos
