Generic Functions
Code to do things like search a list, copy values, and so forth will often look exactly the same, no matter what types are being used. The standard algorithms, which you first met in Chapter 3, “Arrays and Algorithms,” are examples of what is sometimes called generic programming. Rather than write out the same loops, you can reuse the generic code. In this section you will see exactly how such functions are generated, using function templates.
sqr() Revisited
The first example of overloading that we examined in Chapter 6, “Overloading Functions and Operators,” involved a pair of functions that were both called sqr() but dealt with int and double arguments. Any type that can be multiplied—not only ordinary types, but mathematical objects such as matrices and complex numbers—can be squared. For each type of object, the sqr() function looks exactly the same; thanks to compile-time polymorphism, x*x always represents the squaring operation.
The traditional way of efficiently doing this is by using macros. Macros do simple text replacement; for example, SQR(2.3) is replaced by (2.3)*(2.3) and SQR(1+2) is replaced by (1+2)*(1+2). (Note that if you did not include the parentheses, the last expression would be wrong. Appendix C, “The C++ Preprocessor,” discusses macros in more detail.) The following code shows how a macro SQR() can be defined and used to square both double and int values:
;> #define SQR(x) ((x)*(x)) ;> SQR(2.3); (double) 5.29 ;> SQR(2); (int) 4 ;> SQR(1+2); (int) 9 ;> int f(int i) { ;1} cout << "called " << i << endl; ;1} return i; ;1} } ;> SQR(f(2)); called 2 called 2 (int) 4
However, if the argument to this macro causes a function call or any side effects, these calls or side effects happen twice. Macros are simply too naive for general use. In such cases, a function template can be defined, which is parameterized by a type T. When the compiler finds the template used as a function, it looks at the type of the arguments. The type parameter T is bound to the type of the actual argument (think of the type parameter as a kind of type variable.) Then a new instance of the template will be generated, as in the following example:
;> template <class T> ;> T sqr(T x) ;> { return x*x; } ;> sqr(1.2); (double) 1.44 ;> sqr(2); (int) 4 ;> sqr(3.0); (double) 9.0 ;> #v sqr VAR <void> sqr size 4 offset 9432832 int sqr(int) double sqr(double)
sqr(1.2) causes T to be bound to double, and a function double sqr(double) is generated. Likewise, sqr(2) causes T to be bound to int, and int sqr(int) is generated. If you then use the UnderC #v command on sqr, you will see that two functions called sqr() have been generated by the template.
It is useful to think of templates as intelligent macros; the compiler looks at sqr(1.2), notes that the argument is double, and can then deduce that T must be double. It then effectively compiles double sqr(double x){ return x*x; }. If you again call sqr(), with a double argument, the compiler recognizes that this function has already been generated, or instantiated.
Function templates are not themselves functions; they are function generators. In engineering, the word template refers to a stencil or pattern for cutting metal shapes. Thus, a function template is like a cookie cutter, not the cookie itself. The actual functions generated by the template are called template functions; the order of the words is important.
Function templates can be parameterized by more than one type parameter. Here is Min(), which returns the smallest of its two parameters:
template <class T, class S>
T Min(T a, S b)
{ return a > b ? b : a; }
;> Min(1,2);
(int) 1
;> Min(2.3,2.0);
(double) 2.
;> Min(2.3,1);
(double) 1.
;> #v Min
VAR <void> Min size 4 offset 9446992
int Min(int,int)
double Min(double,double)
double Min(double,int)
This is a rather simple definition, which has already generated three versions of Min(). It seems wasteful; why couldn't you just use one type parameter, T? The difficulty is that template argument matching is not too intelligent; if T is first bound to double by looking at the first argument, the compiler complains if the next argument is an int. That is, all arguments declared as T must have consistently the same types, and no standard conversions are applied.
A template can be instantiated only if all the operations needed are available. For example, this simple template is intended to save a little typing:
template <class T>
void dump(T t) {
cout << t << endl;
}
;> int x = 2;
;> dump(x);
2
;> struct S { int a; };
;> S
s; s.a = 1;
;> dump(s);
;> CON 4:Could not match void operator<<(ostream,S);
1 parm
CON 4:Could not match void operator<<(void,_Endl_);
0 parm
Simple templates like this do not make any assumptions about the type parameters. They trust that they will be called in situations when it makes sense. The plain struct S does not overload operator<<, so cout << s is an error, and the instantiation therefore fails. This also illustrates a general point about templates; they are only fully compiled when needed. Thus, a function template may work fine with some types and give compilation errors with other types.
Programmers also tended to use macros for speed. Small template functions can be inlined and so are just as fast as macros.
Specializations
It is possible to specialize a function template to use different code for certain types. It is rather like function overloading. If the function template takes an argument that still contains a type parameter (for instance, list<T>) it is called a partial specialization; if it has no type parameters, then it is a full specialization. Full specializations of a function template are effectively ordinary functions.
Specialization is very useful when working with the standard containers, which themselves are parametrized types.
The formal arguments of a function template do not have to be simple types. It is useful to use type expressions that involve the type parameters (or “dummy types”). In the following example, there are two function templates called dump(). The first would be more efficient than the preceding definition when working with class types; the second dump() template handles simple arrays of objects and has an extra size argument:
template <class T>
void dump(const T& t) {
cout << t << endl;
}
template <class T>
void dump(T t[], int n) {
for(int i = 0; i < n; i++) cout << t[i] << ' ';
cout << endl;
}
These two templates can easily be distinguished from each other because they have different numbers of arguments, so a kind of overloading is possible. In the case of templates, this is called specialization.
If you now call dump() with a std::string argument, C++ will use the first template and can deduce that T is std::string but will then pass that argument as const std::string&. Likewise, dump(arr,4) (where arr is an array of integers) matches the second template and leads to T becoming int.
Note that the arguments of a function template can sometimes be ordinary types, which are converted in the usual fashion; the second version of dump() has an argument int n. However, each dummy parameter (in this case, T) must be mentioned at least once. If not, C++ cannot deduce what T must be from the arguments alone.
Working with the Standard Containers
As you may have guessed, the standard containers such as std::list are parameterized types that are defined as templates. A powerful use of function templates is to generate functions that can operate on any list. Here is a function template for dumping a list:
template <class T>
void dump(const list<T>& ls) {
list<T>::const_iterator li;
for(li = ls.begin(); li != ls.end(); ++li)
cout << *li << ' ';
cout << endl;
}
;> list<int> ls;
;> ls.push_back(1); ls.push_back(2);
;> dump(ls);
1 2
Please note that the list iterator type used here is list<T>::const_iterator. The difference is that a const_iterator cannot be used to modify the list. Since the list argument is const, C++ will not allow you to use a plain iterator here, because it cannot guarantee that it won't be used to change any list values. This can be tricky, because it's easy to forget this requirement (I did it for the first version of this template!). The error messages from C++ compilers can sometimes be a little obscure. If you used iterator instead of const_iterator earlier, BCC32 would give the following error message:
Error E2034 memtemp.cpp 36: Cannot convert 'list<int,allocator<int> >::const_iterator' to 'list<int,allocator<int> >::iterator' in function dump<int>(const list<int,allocator<int> > &)
The first thing is to concentrate on the first error (subsequent errors are often for the same reason or simply because the compiler is confused). Mentally remove the allocator<int> and you get list<int>; this is a default argument that you may never need to change. However, it does make reading error messages a bit tiresome. So the compiler is telling us that it cannot convert list<int>'s const_iterator to iterator; this error refers to the assignment li = ls.begin(). Since ls is a const reference, ls.begin() is a const type; hence the problem. The GCC error message got from running the C++ command is rather strange:
memtemp.cpp: In function `void dump<int>(const list<int,allocator<int> > &)':
memtemp.cpp:49: instantiated from here
memtemp.cpp:36: no match for `_List_iterator<int,int &,int *>& =
_List_iterator<int,const int &,const int *>'
GCC first tells us where the function template was originally called, and then gives the actual error inside the template. The problem is with an assignment; and the clue is that on the right-hand side the type parameters are const. Not obvious, but you start to recognize a pattern.
I don't want to scare you with nasty C++ error messages, but you are going to meet them in real life, and you have to learn to interpret what the compiler is trying to say. Error messages to do with templates and especially with the standard library can be hairy. The main thing is not to be intimidated. This is one good reason, incidently, why the standard algorithms are often easier than loops. Here is another version of the same template, this time using for_each:
template <class T>
void dump_item(const T& v) { cout << v << endl; }
template <class T>
void dump(const list<T>& ls) {
for_each(ls.begin(),ls.end(),dump_item);
}
It is perfectly fine to pass function templates like dump_item() to standard algorithms like for_each(), although I could not use dump() itself because it would not be clear which template was meant.
The convenience of the dump() template is that it can operate on any list, provided that its element type can be written out (that is, operator<< has been overloaded for that type.) This works well for list<string>, list<double>, and so on.
It also coexists happily with the simple dump() templates defined in the preceding section. Consider the call dump(ls) where ls is some list type. The system finds three templates called dump(), two of which can match list<int> because they each take one argument. The third template matches list<int> even more closely, so it is chosen; this template is said to be more specialized than the others. That is, although list<int> can match the const T& pattern, the const list<T>& pattern is a closer fit. By comparing the actual type parameter (list<int>) with the formal type parameter (const list<T>&), the compiler can deduce that T must be int.
In general, specialized templates give you less trouble than general templates. All the assumptions required by the dump() template specialized for list (the nested type iterator, the methods begin() and end()) are guaranteed by the fact that the function argument must be a list type.