TEMPLATES
Templates
are a way to make code more reusable. Trivial examples include creating generic
data structures which can store arbitrary data types. Templates are of great
utility to programmers, especially when combined with multiple inheritance and
operator overloading. The Standard Template Library (STL) provides many useful
functions within a framework of connected templates.
As
templates are very expressive they may be used for things other than generic
programming. One such use is called template metaprogramming, which is a way of
pre-evaluating some of the code at compile-time rather than run-time. Further
discussion here only relates to templates as a method of generic programming.
By now
you should have noticed that functions that perform the same tasks tend to look
similar. For example, if you wrote a function that prints an int, you would
have to have the int declared first. This way, the possibility of error in your
code is reduced, however, it gets somewhat annoying to have to create different
versions of functions just to handle all the different data types you use. For
example, you may want the function to simply print the input variable,
regardless of what type that variable is. Writing a different function for
every possible input type (double, char *, etc. ...) would be extremely
cumbersome. That is where templates come in.
Templates
solve some of the same problems as macros, generate "optimized" code
at compile time, but are subject to C++'s strict type checking.
Parameterized
types, better known as templates, allow the programmer to create one function
that can handle many different types. Instead of having to take into account
every data type, you have one arbitrary parameter name that the compiler then
replaces with the different data types that you wish the function to use,
manipulate, etc.
Templates
are instantiated at compile-time with the source code.
Templates are type safe.
Templates
allow user-defined specialization. Templates allow non-type parameters.
Templates
use “lazy structural constraints”.
Templates support mix-ins.
Syntax for Templates
Templates are pretty easy to use, just look at the
syntax: template <class TYPEPARAMETER>
(or,
equivalently, and preferred by some) template <typename TYPEPARAMETER>
Function template
There are
two kinds of templates. A function template behaves like a function that can
accept arguments of many different types. For example, the Standard Template
Library contains the function template max(x, y) which returns either x or y,
whichever is larger. max() could be defined like this:
template
<typename TYPEPARAMETER>
TYPEPARAMETER
max(TYPEPARAMETER x, TYPEPARAMETER y)
{
if (x < y) return y;
else
return x;
}
This template can be called just like a function:
std::cout << max(3, 7); // outputs 7
The compiler determines by examining the arguments
that this is a call to max(int, int) and instantiates a version of the function
where the type TYPEPARAMETER is int.
This works whether the arguments x and y are
integers, strings, or any other type for which it makes sense to say "x
< y". If you have defined your own data type, you can use operator
overloading to define the meaning of < for your type, thus allowing you to
use the max() function. While this may seem a minor benefit in this isolated
example, in the context of a comprehensive library like the STL it allows the
programmer to get extensive functionality for a new data type, just by defining
a few operators for it. Merely defining < allows a type to be used with the
standard sort(), stable_sort(), and binary_search() algorithms; data structures
such as sets, heaps, and associative arrays; and more.
As a counterexample, the standard type complex does
not define the < operator, because there is no strict order on complex
numbers. Therefore max(x, y) will fail with a compile error if x and y are
complex values. Likewise, other templates that rely on < cannot be applied
to complex data. Unfortunately, compilers historically generate somewhat
esoteric and unhelpful error messages for this sort of error. Ensuring that a
certain object adheres to a method protocol can alleviate this issue.
{TYPEPARAMETER} is just the arbitrary TYPEPARAMETER
name that you want to use in your function. Some programmers prefer using just
T in place of TYPEPARAMETER. Let us say you want to create a swap function that
can handle more than one data type...
something that looks like this:
template <class SOMETYPE>
void swap
(SOMETYPE &x, SOMETYPE &y)
{
SOMETYPE
temp = x; x = y;
y = temp;
}
The
function you see above looks really similar to any other swap function, with
the differences being the template <class SOMETYPE> line before the
function definition and the instances of SOMETYPE in the code. Everywhere you
would normally need to have the name or class of the datatype that you're using,
you now replace with the arbitrary name that you used in the template <class
SOMETYPE>. For example, if you had SUPERDUPERTYPE instead of SOMETYPE, the
code would look something like this:
template
<class SUPERDUPERTYPE>
void swap
(SUPERDUPERTYPE &x, SUPERDUPERTYPE &y)
{
SUPERDUPERTYPE
temp = x; x = y;
y = temp;
}
As you
can see, you can use whatever label you wish for the template TYPEPARAMETER, as
long as it is not a reserved word.
Class
template
A class
template extends the same concept to classes. Class templates are often used to
make generic containers. For example, the STL has a linked list container. To
make a linked list of integers, one writes list<int>. A list of strings
is denoted list<string>. A list has a set of standard functions
associated with it, which work no matter what you put between the brackets.
If you
want to have more than one template TYPEPARAMETER, then the syntax would be:
template <class SOMETYPE1, class SOMETYPE2, ...>
1. Templates and Classes
Let us
say that rather than create a simple templated function, you would like to use
templates for a class, so that the class may handle more than one datatype. You
may have noticed that some classes are able to accept a type as a parameter and
create variations of an object based on that type (for example the classes of
the STL container class hierarchy). This is because they are declared as
templates using syntax not unlike the one presented below:
template
<class T> class Foo
{
public:
Foo();
void
some_function();
T
some_other_function();
private:
int
member_variable;
T parametrized_variable; };
Defining
member functions of a template class is somewhat like defining a function
template, except for the fact, that you use the scope resolution operator to
indicate that this is the template classes' member function. The one important
and non-obvious detail is the requirement of using the template operator
containing the parametrized type name after the class name.
The
following example describes the required syntax by defining functions from the
example class above.
template
<class T> Foo<T>::Foo()
{
member_variable
= 0;
}
template
<class T> void Foo<T>::some_function()
{
cout
<< "member_variable = " << member_variable << endl;
}
template
<class T> T Foo<T>::some_other_function()
{
return
parametrized_variable;
}
As you
may have noticed, if you want to declare a function that will return an object
of the parametrized type, you just have to use the name of that parameter as
the function's return type.
Advantages and disadvantages
Some uses
of templates, such as the max() function, were previously filled by
function-like preprocessor macros.
// a
max() macro
#define
max(a,b) ((a) < (b) ? (b) : (a))
Both
macros and templates are expanded at compile time. Macros are always expanded
inline; templates can also be expanded as inline functions when the compiler
deems it appropriate. Thus both function-like macros and function templates
have no run-time overhead.
However,
templates are generally considered an improvement over macros for these
purposes. Templates are type-safe. Templates avoid some of the common errors
found in code that makes heavy use of function-like macros. Perhaps most
importantly, templates were designed to be applicable to much larger problems
than macros. The definition of a function-like macro must fit on a single
logical line of code.
There are
three primary drawbacks to the use of templates. First, many compilers
historically have very poor support for templates, so the use of templates can
make code somewhat less portable. Second, almost all compilers produce
confusing, unhelpful error messages when errors are detected in template code.
This can make templates difficult to develop. Third, each use of a template may
cause the compiler to generate extra code (an instantiation of the template),
so the indiscriminate use of templates can lead to code bloat, resulting in
excessively large executables.
The other
big disadvantage of templates is that to replace a #define like max which acts
identically with dissimilar types or function calls is impossible. Templates
have replaced using #defines for complex functions but not for simple stuff
like max(a,b). For a full discussion on trying to create a template for the
#define max, see the paper "Min, Max and More" that Scott Meyer wrote
for C++ Report in January 1995.
The
biggest advantage of using templates, is that a complex algorithm can have a
simple interface that the compiler then uses to choose the correct
implementation based on the type of the arguments. For instance, a searching
algorithm can take advantage of the properties of the container being searched.
This technique is used throughout the C++ standard library.
Linkage
problems
While
linking a template-based program consisting over several modules spread over a
couple files, it is a frequent and mystifying situation to find that the object
code of the modules won't link due to 'unresolved reference to (insert template
member function name here) in (...)'.
The
offending function's implementation is there, so why is it missing from the
object code? Let us stop a moment and consider how can this be possible.
Assume
you have created a template based class called Foo and put its declaration in
the file Util.hpp along with some other regular class called Bar:
template
<class T> Foo
{
public:
Foo();
T
some_function();
T
some_other_function();
T
some_yet_other_function(); T member;
};
class Bar
{
Bar();
void do_something(); };
Now, to
adhere to all the rules of the art, you create a file called Util.cc, where you
put all the function definitions, template or otherwise:
#include
"Util.hpp"
template
<class T> T Foo<T>::some_function()
{
...
}
template
<class T> T Foo<T>::some_other_function()
{
...
}
template
<class T> T Foo<T>::some_yet_other_function()
{
...
}
and,
finally:
void
Bar::do_something()
{
Foo<int>
my_foo;
int x =
my_foo.some_function();
int y =
my_foo.some_other_function();
}
Next, you
compile the module, there are no errors, you are happy. But suppose there is an
another (main) module in the program, which resides in MyProg.cc:
#include "Util.hpp" // imports our utility classes'
declarations, including the template
int
main()
{
Foo<int>
main_foo;
int z =
main_foo.some_yet_other_function(); return 0;
}
This also
compiles clean to the object code. Yet when you try to link the two modules
together, you get an error saying there is an undefined reference to
Foo<int>::some_yet_other function() in MyProg.cc. You defined the
template member function correctly, so what is the problem?
As you remember,
templates are instantiated at compile-time. This helps avoid code bloat, which
would be the result of generating all the template class and function variants
for all possible types as its parameters. So, when the compiler processed the
Util.cc code, it saw that the only variant of the Foo class was Foo<int>,
and the only needed functions were:
int
Foo<int>::some_function();
int
Foo<int>::some_other_function();
No code
in Util.cc required any other variants of Foo or its methods to exist, so the
compiler generated no code other than that. There is no implementation of
some_yet_other_function() in the object code, just as there is no
implementation for
double
Foo<double>::some_function(); or
string
Foo<string>::some_function();
The
MyProg.cc code compiled without errors, because the member function of Foo it
uses is correctly declared in the Util.hpp header, and it is expected that it
will be available upon linking. But it is not and hence the error, and a lot of
nuisance if you are new to templates and start looking for errors in your code,
which ironically is perfectly correct.
The
solution is somewhat compiler dependent. For the GNU compiler, try
experimenting with the -frepo flag, and also reading the template-related
section of 'info gcc' (node "Template Instantiation": "Where is
the Template?") may prove enlightening. In Borland, supposedly, there is a
selection in the linker options, which activates 'smart' templates just for
this kind of problem.
The other
thing you may try is called explicit instantiation. What you do is create some
dummy code in the module with the templates, which creates all variants of the
template class and calls all variants of its member functions, which you know
are needed elsewhere. Obviously, this requires you to know a lot about what
variants you need throughout your code. In our simple example this would go
like this:
1. Add the
following class declaration to Util.hpp: class Instantiations
{
private:
void Instantiate(); };
2. Add the
following member function definition to Util.cc: void
Instantiations::Instantiate()
{
Foo<int>
my_foo; my_foo.some_yet_other_function();
// other
explicit instantiations may follow
}
we never
need to actually instantiate the Instantiations class, or call any of its
methods. The fact that they just exist in the code makes the compiler generate
all the template variations which are required. Now the object code will link
without problems.
There is
still one, if not elegant, solution. Just move all the template functions'
definition code to the Util.hpp header file. This is not pretty, because header
files are for declarations, and the implementation is supposed to be defined
elsewhere, but it does the trick in this situation. While compiling the
MyProg.cc (and any other modules which include Util.hpp) code, the compiler
will generate all the template variants which are needed, because the
definitions are readily available.
2. Template Meta-programming
overview
Template
meta-programming (TMP) refers to uses of the C++ template system to perform
computation at compile-time within the code. It can, for the most part, be
considered to be "programming with types" — in that, largely, the
"values" that TMP works with are specific C++ types. Using types as
the basic objects of calculation allows the full power of the type-inference
rules to be used for general-purpose computing.
3. Compile-time programming
The
preprocessor allows certain calculations to be carried out at compile time,
meaning that by the time the code has finished compiling the decision has
already been taken, and can be left out of the compiled executable. The
following is a very contrived example:
#define myvar 17 #if myvar % 2
cout
<< "Constant is odd" << endl; #else
cout
<< "Constant is even" << endl; #endif
This kind
of construction does not have much application beyond conditional inclusion of
platform-specific code. In particular there's no way to iterate, so it can not
be used for general computing. Compile-time programming with templates works in
a similar way but is much more powerful, indeed it is actually Turing complete.
Traits
classes are a familiar example of a simple form of template meta-programming:
given input of a type, they compute as output properties associated with that
type (for example, std::iterator_traits<> takes an iterator type as
input, and computes properties such as the iterator's difference_type,
value_type and so on).
4. The nature of template
meta-programming
Template
meta-programming is much closer to functional programming than ordinary
idiomatic C++ is. This is because 'variables' are all immutable, and hence it
is necessary to use recursion rather than iteration to process elements of a
set. This adds another layer of challenge for C++ programmers learning TMP: as
well as learning the mechanics of it, they must learn to think in a different
way.
Limitations of Template Meta-programming
Because
template meta-programming evolved from an unintended use of the template
system, it is frequently cumbersome. Often it is very hard to make the intent
of the code clear to a maintainer, since the natural meaning of the code being
used is very different from the purpose to which it is being put. The most
effective way to deal with this is through reliance on idiom; if you want to be
a productive template meta-programmer you will have to learn to recognize the
common idioms.
It also
challenges the capabilities of older compilers; generally speaking, compilers
from around the year 2000 and later are able to deal with much practical TMP code.
Even when the compiler supports it, the compile times can be extremely large
and in the case of a compile failure the error messages are frequently
impenetrable.
Some
coding standards may even forbid template meta-programming, at least outside of
third-party libraries like Boost.
History
of TMP
Historically
TMP is something of an accident; it was discovered during the process of
standardizing the C++ language that its template system happens to be
Turing-complete, i.e., capable in principle of computing anything that is
computable. The first concrete demonstration of this was a program written by
Erwin Unruh which computed prime numbers although it did not actually finish
compiling: the list of prime numbers was part of an error message generated by
the compiler on attempting to compile the code.[1] TMP has since advanced
considerably, and is now a practical tool for library builders in C++, though
its complexities mean that it is not generally appropriate for the majority of
applications or systems programming contexts.
#include
<iostream>
template
<int p, int i>
class
is_prime { public:
enum {
prim = ( (p % i) && is_prime<p, i - 1>::prim ) };
};
template
<int p>
class
is_prime<p, 1>
{
public:
enum {
prim = 1 };
};
template
<int i>
class Prime_print
{ // primary template for loop to print prime numbers public:
Prime_print<i
- 1> a;
enum {
prim = is_prime<i, i - 1>::prim }; void f() {
a.f();
if (prim)
{
std::cout
<< "prime number:" << i << std::endl;
}
}
};
template<>
class
Prime_print<1> { // full specialization to end the loop public:
enum {
prim = 0 }; void f() {}
};
#ifndef
LAST
#define
LAST 18
#endif
int
main()
{
Prime_print<LAST>
a; a.f();
}
5. Building blocks
Values
The
'variables' in TMP are not really variables since their values cannot be
altered, but you can have named values that you use rather like you would
variables in ordinary programming. When programming with types, named values
are typedefs:
struct
ValueHolder
{
typedef
int value; };
You can
think of this as 'storing' the int type so that it can be accessed under the
value name. Integer values are usually stored as members in an enum:
struct
ValueHolder
{
enum {
value = 2 }; };
This
again stores the value so that it can be accessed under the name value. Neither
of these examples is any use on its own, but they form the basis of most other
TMP, so they are vital patterns to be aware of.
Functions
A
function maps one or more input parameters into an output value. The TMP
analogue to this is a template class:
template<int
X, int Y> struct Adder
{
enum {
result = X + Y }; };
This is a
function that adds its two parameters and stores the result in the result enum
member. You can call this at compile time with something like Adder<1,
2>::result, which will be expanded at compile time and act exactly like a
literal 3 in your program.
Branching
A
conditional branch can be constructed by writing two alternative
specialisations of a template class. The compiler will choose the one that fits
the types provided, and a value defined in the instantiated class can then be
accessed. For example, consider the following partial specialisation:
template<typename
X, typename Y>
struct
SameType
{
enum {
result = 0 }; };
template<typename
T>
struct
SameType<T, T>
{
enum {
result = 1 }; };
This
tells us if the two types it is instantiated with are the same. This might not
seem very useful, but it can see through typedefs that might otherwise obscure
whether types are the same, and it can be used on template arguments in
template code. You can use it like this:
if
(SameType<SomeThirdPartyType, int>::result)
{
// ...
Use some optimised code that can assume the type is an int
}
else
{
// ...
Use defensive code that doesn't make any assumptions about the type
}
The above
code isn't very idiomatic: since the types can be identified at compile-time,
the if() block will always have a trivial condition (it'll always resolve to
either if (1) { ... } or if (0) {
... }).
However, this does illustrate the kind of thing that can be achieved. Recursion
Since you
don't have mutable variables available when you're programming with templates,
it's impossible to iterate over a sequence of values. Tasks that might be
achieved with iteration in standard C++ have to be redefined in terms of
recursion, i.e. a function that calls itself. This usually takes the shape of a
template class whose output value recursively refers to itself, and one or more
specialisations that give fixed values to prevent infinite recursion. You can
think of this as a combination of the function and conditional branch ideas
described above.
Calculating
factorials is naturally done recursively: 0!=1, and for n>0, n!=n∗(n−1)!. In TMP, this corresponds
to a class template "factorial" whose general form uses the
recurrence relation, and a specialization of which terminates the recursion.
First,
the general (unspecialized) template says that factorial<n>::value is
given by n*factorial<n-1>::value:
template
<unsigned n>
struct
factorial
{
enum {
value = n * factorial<n-1>::value }; };
Next, the
specialization for zero says that factorial<0>::value evaluates to 1:
template <>
struct
factorial<0>
{
enum {
value = 1 }; };
And now
some code that "calls" the factorial template at compile-time:
int
main() {
// Because
calculations are done at compile-time, they can be
// used for
things such as array sizes.
int
array[ factorial<7>::value ];
}
Observe
that the factorial<N>::value member is expressed in terms of the
factorial<N> template, but this can't continue infinitely: each time it
is evaluated, it calls itself with a progressively smaller (but non-negative)
number. This must eventually hit zero, at which point the specialisation kicks
in and evaluation doesn't recurse any further.
Example:
Compile-time "If"
The
following code defines a meta-function called "if_"; this is a class
template that can be used to choose between two types based on a compile-time
constant, as demonstrated in main below:
template
<bool Condition, typename TrueResult, typename FalseResult> class if_;
template <typename TrueResult, typename
FalseResult> struct if_<true, TrueResult, FalseResult>
{
typedef TrueResult result; };
template
<typename TrueResult, typename FalseResult> struct if_<false,
TrueResult, FalseResult>
{
typedef FalseResult result; };
int
main()
{
typename
if_<true, int, void*>::result number(3); typename if_<false, int,
void*>::result pointer(&number);
typedef typename if_<(sizeof(void *) >
sizeof(uint32_t)), uint64_t, uint32_t>::result integral_ptr_t;
integral_ptr_t
converted_pointer = reinterpret_cast<integral_ptr_t>(pointer);
}
On line
18, we evaluate the if_ template with a true value, so the type used is the
first of the provided values. Thus the entire expression if_<true, int,
void*>::result evaluates to int.
Similarly,
on line 19 the template code evaluates to void *. These expressions act exactly
the same as if the types had been written as literal values in the source code.
Line 21
is where it starts to get clever: we define a type that depends on the value of
a platform-dependent sizeof expression. On platforms where pointers are either
32 or 64 bits, this will choose the correct type at compile time without any
modification, and without preprocessor macros. Once the type has been chosen,
it can then be used like any other type.
For
comparison, this problem is best attacked in C90 as follows
# include
<stddef.h> typedef size_t integral_ptr_t;
typedef
int the_correct_size_was_chosen [sizeof (integral_ptr_t) >= sizeof (void *)?
1: -1]; 1.
As it
happens, the library-defined type size_t should be the correct choice for this
particular problem on any platform. To ensure this, line 3 is used as a compile
time check to see if the selected type is actually large enough; if not, the
array type the_correct_size_was_chosen will be defined with a negative length,
causing a compile-time error. In C99, <stdint.h> may define the types
intptr_h and uintptr_h.
Conventions
for "Structured" TMP
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.