15 Function Templates

Bhushan Trivedi

Introduction

The template is a unique feature of the C++ language. A template is an outline or a sketch of a class or a function, which can later be converted to a specific type of a class or function, based on user’s requirement. Whenever the function or a class with specific type is defined, this template is used to generate a copy of a function or a class for that specific type. The idea of template is derived from the need of two different camps. One camp wants to preserve the efficiency of the C language while the other camp demands generic solutions to problems, for example, designing classes which can work with any valid data types and design algorithms which can also work with objects of multiple classes. How templates are able to satisfy requirements of both communities is the theme of this and next module. Templates do everything at compile time and do not leave anything to be done at runtime.

Class and function templates

There are two different types of the templates, generic functions, which can work with any data types, are known as function templates and generic classes, which can work with multiple data types are known as class templates. Thus, we can have two types of templates, function templates as well as class templates. We will discuss with generic functions or function templates in this module. The class templates are covered in the next module. Reusability is one of the important advantages of using object based language. It is about a class or function designed for one case can also be used for other purposes. Templates allow reusability of both a class and a function. When we use templates and provide generic algorithms which can work with multiple types and write classes which can work with multiple types, the programming methodology is known as object based programming. The biggest advantage of such programming is that it provides reusability without any runtime overhead. Later on we will see object oriented methods which are more flexible but need additional runtime overhead to work. The object based programming is dealing with function and class templates.

A Function Template is a function sketch with clear algorithm for doing everything with a generic type. When an actual function is instantiated with a proper value of type, this function template is used to generate that function. Function template is also called template function or generic function. On the other hand, a Class template is a sketch of the class where members are designed with a generic type. When an actual class is instantiated with a specific type, a class is designed from that template and the object comes into an existence. The class template is also called template class or generic class. We will look at function templates in this module and class template in next module.

The reusability using templates

Same code-multiple types paradigm is the theme of template based code design. C++ provides reusability in many ways, templates is one important way. We have already seen how the functions are overloaded and we can use that feature to provide reusability in some cases. For example, if we want to write bubble sort for an int data type as well as a float data type, we may write two bubble sort functions, one with integer and another with float arguments and overload these two functions. That, however introduces another problem. An identical copy of the same code at two places. As and when there is a need to change the code, the programmer must change the code at BOTH the places or otherwise introduce inconsistency related bugs very difficult to identify and repair.

One may argue that one can write a bubble sort function only for float and if ever this function is called with int arguments, those arguments are promoted to float1. This approach actually works, but it is not a good solution. When an int value is promoted to float, it occupies more memory as well as takes much more time in computing. Thus whenever we are sorting int values, we are spending time and needing space as much as the float values would. If we generally sort only integer values, it is a much bigger price to pay as every time when the sorting process begins, this conversion is made, int values are sorted as if they are a float and eventually the result is copied back to int. In fact, overloading is better in such a case. Overloading in this case allows us to use a specific function for a specific type of argument. Int values use int version of the function while float values use float version of the function.

However, if you look closely, you will realize that when we overload a function like a bubble sort, it only differs in terms of the type being used, otherwise, the code is identical. You might wonder if there is a way to tell C++ this and have a generic function which is independent of type. In this case, when we actually put the function to use, we may specify the type on which the generic function is to be used. Fortunately, this is possible in C++ by means of a function template. Thus we eliminate both, the need to have multiple copies of the same code and headache of maintaining them, and performance overhead while allowing promotions of types.

A function template contains a body of the function with a generic type. The difference between a normal function and a function template is that the function template uses a

1 Like C, C++ also provides logical promotion of values while multiple types are used in an expression. A type which is of lower rank is promoted to higher rank, for example, an int and long, both are used in expression than an int value is promoted to long before that expression is evaluated.

generic type while the normal function does not. When the function call is made for a function template, a specific type is provided by the user. The compiler, when compiles the function call, replaces the call by the call to a specific function for that type which is generated from that generic function. If such a function with that specific type is not generated, it will generate one before processing the function call with that specific type. Let us try to understand the process by looking at the generic bubble sort algorithm, implemented using a function template.

Function Template Bubble sort

Before we start looking that this program, let us pay some attention to the way we code and represent the programs in our modules. First, the program is divided into a few blocks and each block bears the program number to indicate which program that block belongs to. For example, following two lines indicate the name and number of a program.

// Generic Bubble sort

// Program 16.1

The second line, i.e. Program 16.1 is written in the beginning of every block of that program. The second point, we have a typical naming convention followed through out. For example, anything starts with t indicates it is a temporary variable of some sort. A indicates array, so t_A indicates a temporary array. In the naming convention like t_i_A, the middle value indicates the type of the array, int in this case. When the array is not temporary, you may find convention like i_A indicating integer array. The word G or g is used to indicate the generic entity. That means tGArray is a temporary generic array.

The variables used have different names but can be replaced by any other names and the result would be the same. Another important difference is the indicator that the Type being a generic type. The indicator is written as follows.

template <typename Type>

The keyword typename defines a generic type or a placeholder for defining a generic type. When the function or class is defined, the generic type defined by the typename is used exactly like a normal type. Whenever the function or class is instantiated, this generic type is

// Program 16.1 Block 2	replaced by an actual type. The
indicator indicates that the Type is a
template <typename Type>
void GBubbleSrt(Type tGArray[])	generic type name that we are going
{

for (int i=0;i<9;i++)	to use in this function which will be
{	replaced when the function is called.
for (int j = i + 1; j<10;j++)
{	For example, when the function call
if (tGArray[i] < tGArray[j])	is made in the following statement,
{
Type tGeneric = tGArray[i];	the Type is replaced by int
tGArray[i] = tGArray[j];

tGArray[j] = tGeneric;
}	GBubbleSrt <int > (i_A_2);
}

}
}	You may try to compare this call with
a normal function call, like the one as follows.
BubbleSrt(i_A_1);

You will be able to notice the additional section starts with < sign and ends with a > sign and having int in between. It is known as a declaration section. A declaration section in the template definition covered inside angular brackets (<>), it defines all type placeholders using the typename or class keyword. This (the declaration section) is where we specify the type to be used when to call this generic function. At this particular point in time, a new function from generic GBubbleSrt is constructed and invoked.

Let us closely look at the template definition. The template keyword indicates that the definition of the function template has begun. The <> section defines the placeholders for dummy types. Type is one such placeholder used in program 16.1. Wherever we have used that Type, it will be replaced by the specific type mentioned at the time of a call, for example, int or char. The typename is a keyword too. It describes the placeholder coming next. In some older C++ programs, you may find word class instead of typename. The use of word class here is legal but not advised as it confuses the reader about what exactly it is. Unlike the class, typename clearly indicates what it describes and thus it is a very user-friendly method to indicate the type and thus, recommended.

Look at the function call yet again. Apart from the generic type indicator that appears before the list of arguments, there is no other difference. Now, pay some attention to the definition of the function template GBubbleSrt. You can see that Type is used in exactly the same as any other valid type could have been. For example, following statement.

Type tGeneric = tGArray[i];

The variable tGeneric (now you can understand that it is a temporary variable of generic nature) has no type defined now. Only when the call is encountered (at compile time) the compiler generates a function of the specific type and replaces this Type placeholder with the actual type.

One interesting replacement for Type is made when the template function is called without the declaration section (enclosed within <>). Look at the function call made when the following statement executes.

GBubbleSrt(f_A_1);

There is no declaration section for the compiler to learn about the type of the function to be generated. Compilers are generally smart enough to deduce the type in such cases. For example, the f_A_1 (which is a float value array number 1) with float values defined already. It is easy for the compiler, in this case, to determine the type of

the argument to be a float and it does so. If a float function is already called before, and thus the function exists, the compiler’s job is reduced to call that function and no longer need to generate it. Let us recap. When a generic function is instantiated without the declaration (<>) section, the type which replaces the generic type in the instantiated function is decided by the compiler looking at the arguments. This process is called automatic type deduction. This process is also known as argument deduction process.

Why template

The word Type is a placeholder or a template and hence the name. Figure 16.1 has three samples indicating the same definition, using different names for the same placeholder that we are supposed to use in the function template. There is no difference in any manner in these three

definitions. Carefully observe the calls made to the function in the main. There are two different calls.

The earlier example illustrated an int call and following indicates a char call. When the first call with int is made, a new function from GBubbleSort is generated for int data type while in the second case a new function from GBubbleSort is generated for char data type.

GBubbleSrt <char> (c_A_1);

Kindly also note the difference between GBubbleSrt and GBubbleSrt <char>. The first is a generic function definition, for which there is no memory occupied and no member is defined. While in the case of GBubbleSrt <char>, it is an actual function with char as the type, with all members defined and also needs memory to store function members. Similarly, GBubbleSrt <int> is another such function with Type as int and is altogether different function than GBubbleSrt <char>.

In a way, function template is a method for providing automatic overloading of a given function, for a given type. The problems with user defined overloading process, maintaining the same code at multiple places, is eliminated here.

Instantiation

Suppose we encounter two statements, one after another in the program where GBubbleSrt is defined, what is the difference in which these two statements are processed by the compiler? Assume another character array c_A_2 is already defined?

GBubbleSrt <char> (c_A_1);

GBubbleSrt <char> (c_A_2);

The difference is that the second call does not demand to generate the function GBubbleSrt <char> as it is already done by the previous statement. The second statement only demands to call that already generated function. The process of generating that function is known as instantiation. So the second call to GBubbleSrt does not require instantiation while the first call demands instantiation. In simple terms, the instantiation is a process by which a function of a specific type is generated from the template (template function).

The difference between a normal function call and a template function call is worth noticing. A normal function is instantiated instantly when defined. It does not need to be instantiated when the call is made. On the contrary, the function call to a generic function (for the first time) demands instantiation. This indicates one important point. Though the generic function can be used for many types, the C++ instantiates only those functions which are actually called. A consequence of this is, a normal function comes into existence when they are defined, a template function’s instantiation comes into existence when (and if) the function with that type is called ever. For example, if such a call is made in either if or else part and that part is not executed, the function does not come into existence.

Argument deduction

Revisit the call that we have encountered before.

GBubbleSrt(f_A_1);

The compiler decides the type of the function to instantiate on its own. This is a great service, especially when C++ strives to make sure the instantiated function’s call looks like a normal function call. That means, as long as a compiler can deduce, a user can call both, a normal as well as a template function, in a similar fashion. So when such a function is provided in the library, the user can use it without really knowing it to be a template.

Another advantage is also worth noticing. A program keeps on being modified, despite the attempts from administrators against such practice. If the type changes in the next update, the programmer does not need to go to those calls and change the declaration section. When the program is recompiled, the compiler can deduce type yet again and generate a specific instantiation of the function based on the type of the argument automatically. However, there are two things to notice before we start using it. The first is there are some cases where type deduction is either not possible or ambiguous Another point is, the type matching process is quite stringent. The process does not introduce any promotional upgrading to other types. For example, if we have a typical template defined in 16.2, it won’t compile!

Why? The compare function is called with two different arguments, an int and an unsigned. In the definition, both of them are defined to be of type Type so they will have to be the same. is, sometimes it is not possible for the compiler to deduce an argument from the user’s call. In that case, the programmer must provide some means of gracefully responding with a specific error or help the user to call with proper arguments.

Using template for user defined objects

The power of templates is more apparent when we use them for user defined objects. Let us take another example to understand. Let us write a generic function for searching through an array, for finding the search item that we are looking for. We will do a sequential search on an array of employee objects. We will define both, an Emp class describing an employee and an array which contains such employee objects. We will have three blocks in which we write this program. The first block contains the employee class definition with operators overloaded for the == operator. The need of == operator needs to be understood. When we search an item like an employee object, how one can compare an employee object to be a search item and return true or false? We can do that with an integer or char variable very easily because we can easily compare them. Doing something similar for an employee object is not straight forward. One can either compare them using a C like complete object match or database like index matching method. In databases the index value identifies a record and the index value like customer number or employee number is an identity. When the identity matches, irrespective of other contents, two records are said to belong to same entity and when multiple entity records are not allowed, such a set of records are not allowed. The designer must specify what is an identity of an employee object. In our example, it is the EmpNo variable (which contains employee id) which holds the identity of the employee. The designer decides that

complete object match or database like index matching method. In databases the index value identifies a record and the index value like customer number or employee number is an identity. When the identity matches, irrespective of other contents, two records are said to belong to same entity and when multiple entity records are not allowed, such a set of records are not allowed. The designer must specify what is an identity of an employee object. In our example, it is the EmpNo variable (which contains employee id) which holds the identity of the employee. The designer decides that when the id of the two objects matches, they are the same. The compiler cannot decide this thing on its own and the designers must provide the solution in terms of overloaded operator == which indicates that when two employee objects are equated, one should check their respective EmpNo values to decide whether they are the same or not. Searching an employee object from an array also is done in similar fashion.

Closely look at the program 16.2, the first block. The Emp Class defines four data members, employee number, employee name, department name and the designation. Parameterized constructor for the class is provided for the data entry. The overloaded operator == returns true or false based on the employee number of the other object matches with our employee number or not. This block also defines another operator << for displaying an employee object member by member.

The second block of the program describes the function template for a generic search. This function template is named as g_Search indicating the generic search, the Search_Item is of the generic type while t_g_A[] is the array of that generic type.The convention to use t_before any item defined inside the function is that such items are temporary and also are replaced by called arguments when the call is made. The function is quite straight forward,it assumes the array

length to be 10, iterates through the array and check if the search item equates with any

//Program 16.2 block 3

int main()

{

int i_A_1[]={121,425,243,859,635,364,132,442,615,221};

char c_A_1[]=”hi_bhushan”;

Emp EmpList[]=

{

Emp (1,”Mithali”,”Batsman”,”captain”),

Emp (2,”Smriti”,”Batsman”,”opener”),

Emp (3,”Ekta”,”spinner”,”LeftArm”),

Emp (4,”Zulan”,”pacer”,”RightArm”),

Emp (5,”Shikha”,”pacer”,”RightArm”),

Emp (6,”Harmanprit”,”Allrounder”,”Middle”),

Emp (7,”Veda”,”pinchhitter”,”Lower”),

Emp (8,”Gayakwad”,”spinner”,”LeftArm”),

Emp (9,”Dipti”,”Allrounder”,”opener”),

Emp (10,”Saha”,”WicketKeepr”,”Right”)

};

cout << “\nThe integer element is at position ” << g_Search(i_A_1, 635); cout << “\nThe char element is at position ” << g_Search(c_A_1, ‘b’); cout << “\n”;

int Who = g_Search(EmpList, Emp (3,””,””,””));

cout << EmpList [Who];

}

items of an array. If so, it returns the index. In case no item matches with the search item, the template is designed to return -1. The third block describes the main (). You can see that the main calls the g_Search function with built in datatypes like int as well as char. You can also see that there is an array EmpList which is populated with some employee values. The g_search function is called with a search item as well as this list later. There is no difference in each of these calls. Interestingly, the search item is constructed using an explicit call to the parameterized constructor of the Emp class.

int Who = g_Search(EmpList, Emp (3,””,””,””));

The Emp (3…) call constructs a temporary object with only EmpNo value as actual and rest as null. This temporary object is compared with elements of the array and only if there is a match, the index value of an array is returned in an integer variable Who.

The final important point is how the employee object is displayed using an overloaded operator << for an employee class. The syntax for this operator and why it is overloaded as a friend is described in detail in reference 1. You may refer to it if you need further understanding of that operator.

You can try extending the program with the same GBubbleSrt function with the EmpList of this program and try sorting it. A similar program is also found in reference 1.

Function template with multiple types

We have seen two examples so far, both of them used only one generic type but you can have a template with multiple types as well. For example, we can have a function Sum which sums the input values. Consider following the definition of the function Sum having following structure, can you guess what is the problem?

template <typename Type>

Type Sum (Type, Type)

Only if both T1 and T2 of the same type, the addition is possible and not otherwise. So if we have following definition, the call to Sum won’t compile2.

unsigned First;

int Second; long Third;

Third = Sum(First, Second); // this will not compile

The better solution is to provide the template definition as follows.

template <typename T1, typename T2, typename T3>

T3 Sum(T1, T2)

2 You may be surprised that if we have a normal Sum function, it would compile. The reason is that the template type matching is really stringent and seemingly common promotions a normal C++ function enjoys are unavailable to them. Thus the template Sum cannot promote an int to long while a normal function could..

This is an example of a function template with multiple types. However, it solves one problem but introduces another. What if the arguments are incompatible? For example, what if we call Sum in the following fashion?

int What = Sum (2,”Hi”);

int What = Sum (3,’a’);

string What = Sum (“Jay”,” Hind”);

……….

We will come back and answer these question shortly in the next section.

int What = Sum (2,”Hi”);

int What = Sum (3,’a’);

string What = Sum (“Jay”,” Hind”);

……….

We will come back and answer these question shortly in the next section.

Specialization

Function Specialization is a function which overloads a template. When we write a special function for a special type which overloads a generic function, it is known as a process of function specialization (verb). This process is different than defining a normal function in the sense that a function specialization precedes with template <> and it is very stringent in type promotion. Specialization is also used as a name; it is a function which overloads the template function for a specific set of types. As the meaning will be clear from the context we will not differentiate between the verb and the noun henceforth.

However absurd it looks like, there is a possible meaning associated with each of the calls mentioned in the previous section. The last one is about concatenating two strings, the second one is about adding an ASCII value of character ‘a’ to the int value 3, and the first adds 2 to the summation of ASCII values of H and i. This is one typical interpretation of these calls. A designer may seem similar or different meaning for his/her work based on the context and the problem.

If we want to associate such a meaning to typical combination of Type values, there are a few ways to do so. Let us discuss them.

First is to write a normal function (like we have done earlier for bubble sort int values). That function is to be designed specifically for that typical set of types. This function is also known as a non-generic function. We can use the same name as we have used with the generic function and thus actually overload the generic function with this specific function. As long as the compiler is able to deduce which call is associated with which of the function, generic or otherwise, there is no issue.

Another option is to provide a specialization. Specialization is a function which overloads the template function for a specific set of types. Defining the specialization is possible using a typical syntax. For example, we can write definitions of the Sum function which adds two strings.

template <>

If we want to associate such a meaning to typical combination of Type values, there are a few ways to do so. Let us discuss them.

template <>

Sum (string S1, string S2) { <logic for concatenation of the strings>3 }

to concatenate them, as follows. Kindly observe the first line in the declaration template <>. This is an indicator that the next function definition is a specialization of a template function. The difference between a non-generic and a specialization is that a specialization, like a template, is instantiated only when it is called and not otherwise. Also, the type matching for a specialization is much more stringent and no promotion is made.

It is possible to provide specialization for a set of types. For example, we can have a specialization of Sum as follows for pointers to types. In that case, we will sum the values which are pointed to and not the pointers themselves.

template <>

Type Sum (Type *p_g1, Type *p_g2) {return *p_g1 + *p_g2; }

Non-generic types

It is possible to have non-generic types in the definition of the templates, for example, look at the following definition.

template <typename Type>

GBubbleSrt(Type t_Array[], int size)

The second value, the int, is a non-generic type in the above case. The call must be made either using a constant, a pointer or reference to a global function or a non-local object reference or pointer. Why these three categories? We can only use things which are known at compile time and these three values actually are. One of the legal ways to call GBubbleSrt of the above case is as follows, using a constant value 10. The first argument, like the earlier case, is the list of employees. We are not specifying the type and let the compiler deduce the data type to be Emp.

GBubbleSrt (EmpList, 10);

Summary

In this module, we have looked at function templates. In two examples that we have seen in this module, we have provided a generic function to bubble sort as a well as a generic function to search in an array. We have seen how a generic function is put to use. The advantage of a generic function is when we need multiple functions with the same body but different type, a single template function can be defined to handle both cases.

you can view video on Function Templates

References

Programming with ANSI C++, Bhushan Trivedi, Oxford University Press
www.stroustrup.com, homepage of Bjarne Stroustrup, the creator of C++