17.1 Templates for Algorithm Abstraction

Many of our previous C++ function definitions have an underlying algorithm that is much more general than the algorithm we gave in the function definition. For example, consider the function swapValues, which we first discussed in Chapter 5. For reference, we now repeat the function definition:

void swapValues(int& variable1, int& variable2)
{
    int temp;
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
}

Notice that the function swapValues applies only to variables of type int. Yet the algorithm given in the function body could just as well be used to swap the values in two variables of type char. If we want to also use the function swapValues with variables of type char, we can overload the function name by adding the following definition:

void swapValues(char& variable1, char& variable2)
{
    char temp;
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
}

But there is something inefficient and unsatisfying about these two definitions of the swapValues function: They are almost identical. The only difference is that one definition uses the type int in three places and the other uses the type char in the same three places. Proceeding in this way, if we wanted to have the function swapValues apply to pairs of variables of type double, we would have to write a third almost identical function definition. If we wanted to apply swapValues to still more types, the number of almost identical function definitions would be even larger. This would require a good deal of typing and would clutter up our code with lots of definitions that look identical. We should be able to say that the following function definition applies to variables of any type:

void swapValues(Type_Of_The_Variables& variable1,
                Type_Of_The_Variables& variable2)
{
    Type_Of_The_Variables temp;
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
}

As we will see, something like this is possible. We can define one function that applies to all types of variables, although the syntax is a bit different from what we have shown above. That syntax is described in the next subsection.

Templates for Functions

Display 17.1 shows a C++ template for the function swapValues. This function template allows you to swap the values of any two variables, of any type, as long as the two variables have the same type. The definition and the function declaration begin with the line

template<class T>

This is often called the template prefix, and it tells the compiler that the definition or function declaration that follows is a template and that T is a type parameter. In this context, the word class actually means type.1 As we will see, the type parameter T can be replaced by any type, whether the type is a class or not. Within the body of the function definition, the type parameter T is used just like any other type.

¹ In fact, the ANSI standard provides that you may use the keyword typename instead of class in the template prefix. Although we agree that using typename makes more sense than using class, the use of class is a firmly established tradition, and so we use class for the sake of consistency with most other programmers and authors.

Display17.1 A Function Template

 1    //Program to demonstrate a function template.  2    #include <iostream>
 3    using namespace std;
 4    //Interchanges the values of variable1 and variable2.
 5    template<class T>
 6    void swapValues(T& variable1, T& variable2)
 7    {
 8          T temp;
 9           
10          temp = variable1;
11          variable1 = variable2;
12          variable2 = temp;
13    }
14    int main( )
15    {
16        int integer1 = 1, integer2 = 2;
17        cout << "Original integer values are "
18             << integer1 << " " << integer2 <<endl;
19        swapValues(integer1, integer2);
20        cout << "Swapped integer values are "
21             << integer1 << " " << integer2 <<endl;
22        char symbol1 = 'A', symbol2 = 'B';
23        cout << "Original character values are "
24             << symbol1 << " " << symbol2 <<endl;
25        swapValues(symbol1, symbol2);
26        cout << "Swapped character values are "
27             << symbol1 << " " << symbol2 <<endl;
28        return 0;
29    }

Output

Original integer values are 1 2
Swapped integer values are 2 1
Original character values are A B
Swapped character values are B A

The function template definition is, in effect, a large collection of function definitions. For the function template for swapValues shown in Display 17.1, there is, in effect, one function definition for each possible type name. Each of these definitions is obtained by replacing the type parameter T with a type name. For example, the function definition that follows is obtained by replacing T with the type name double:

void swapValues(double& variable1, double& variable2)
{
    double temp;
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
}

A template overloads the function name

Another definition for swapValues is obtained by replacing the type parameter T in the function template with the type name int. Yet another definition is obtained by replacing the type parameter T with char. The one function template shown in Display 17.1 overloads the function name swapValues so that there is a slightly different function definition for every possible type.

The compiler will not literally produce definitions for every possible type for the function name swapValues, but it will behave exactly as if it had produced all those function definitions. A separate definition will be produced for each different type for which you use the template, but not for any types you do not use. Only one definition is generated for a single type regardless of the number of times you use the template for that type. Notice that the function swapValues is called twice in Display 17.1: One time the arguments are of type int and the other time the arguments are of type char.

Consider the following function call from Display 17.1:

swapValues(integer1, integer2);

When the C++ compiler gets to this function call, it notices the types of the arguments—in this case int—and then it uses the template to produce a function definition with the type parameter T replaced with the type name int. Similarly, when the compiler sees the function call

swapValues(symbol1, symbol2);

it notices the types of the arguments—in this case char—and then it uses the template to produce a function definition with the type parameter T replaced with the type name char.

Calling a function template

Notice that you need not do anything special when you call a function that is defined with a function template; you call it just as you would any other function. The compiler does all the work of producing the function definition from the function template.

Notice that in Display 17.1 we placed the function template definition before the main part of the program, and we used no template function declaration. A function template may have a function declaration, just like an ordinary function. You may (or may not) be able to place the function declaration and definition for a function template in the same locations that you place function declarations and definitions for ordinary functions. However, some compilers do not support template function declarations and do not support separate compilation of template functions. When these are supported, the details can be messy and can vary from one compiler to another. Your safest strategy is to not use template function declarations and to be sure the function template definition appears in the same file in which it is used and appears before the function template is used.

We said that a function template definition should appear in the same file as the file that uses the template function (that is, the same file as the file that has an invocation of the template function). However, the function template definition can appear via a #include directive. You can give the function template definition in one file and then #include that file in a file that uses the template function. That is the cleanest and safest general strategy. However, even that may not work on some compilers. If it does not work, consult a local expert.

Although we will not be using template function declarations in our code, we will describe them and give examples of them for the benefit of readers whose compilers support the use of these function declarations.

In the function template in Display 17.1, we used the letter T as the parameter for the type. This is traditional but is not required by the C++ language. The type parameter can be any identifier (other than a keyword). T is a good name for the type parameter, but sometimes other names may work better. For example, the function template for swapValues given in Display 17.1 is equivalent to the following:

template<class VariableType>
void swapValues(VariableType& variable1,
                VariableType& variable2)
{
    VariableType temp;
    temp = variable1;
    variable1 = variable2;
    variable2 = temp;
}

More than one type parameter

It is possible to have function templates that have more than one type parameter. For example, a function template with two type parameters named T1 and T2 would begin as follows:

template<class T1, class T2>

However, most function templates require only one type parameter. You cannot have unused template parameters; that is, each template parameter must be used in your template function.

Pitfall Compiler Complications

Issues Compiling Programs with Templates

C++ does not allow you to separate interface (header) and implementation files for template definitions in the usual way, so you need to include your template definition with your code that uses it. As usual, at least the function declaration must precede any use of the template function. This is because the header can’t correctly match the implementation when the type is unknown.

Your safest strategy is not to use template function declarations and to be sure the function template definition appears in the same file in which it is used and appears before the function template is called. However, the function template definition can appear via a #include directive. You can give the function template definition in one file and then #include that file in a file that uses the template function.

Another common technique is to put your definition and implementation, all in the header file. If you use this technique, then you would only have a header (.h) file and no implementation (.cpp) file. Sometimes the .hpp file extension is used when all of the code is in the header file. Finally, an alternate approach is to include the implementation (.cpp) file for your template class instead of the header file (.h).

Some C++ compilers have additional special requirements for using templates. If you have trouble compiling your templates, check your manuals or check with a local expert. You may need to set special options or rearrange the way you order the template definitions and the other items in your files.

Function Template

The function definition and the function declaration for a function template are each prefaced with the following:

template<class Type_Parameter>

The function declaration (if used) and definition are the same as any ordinary function declaration and definition, except that the Type_Parameter can be used in place of a type.

For example, the following is a function declaration for a function template:

template<class T>
void showStuff(int stuff1, T stuff2, T stuff3);

The definition for this function template might be as follows:

template<class T> void showStuff(int stuff1, T stuff2, T stuff3)
{
    cout << stuff1 << endl
         << stuff2 << endl
         << stuff3 << endl;
}

The function template given in this example is equivalent to having one function declaration and one function definition for each possible type name. The type name is substituted for the type parameter (which is T in the example above). For instance, consider the following function call:

showStuff(2, 3.3, 4.4);

When this function call is executed, the compiler uses the function definition obtained by replacing T with the type name double. A separate definition will be produced for each different type for which you use the template but not for any types you do not use. Only one definition is generated for a specific type regardless of the number of times you use the template.

Self-Test Exercises

1. Write a function template named maximum. The function takes two values of the same type as its arguments and returns the larger of the two arguments (or either value if they are equal). Give both the function declaration and the function definition for the template. You will use the operator < in your definition. Therefore, this function template will apply only to types for which < is defined. Write a comment for the function declaration that explains this restriction.

2. We have used three kinds of absolute value function: abs, labs, and fabs. These functions differ only in the type of their argument. It might be better to have a function template for the absolute value function. Give a function template for an absolute value function called absolute. The template will apply only to types for which < is defined, for which the unary negation operator is defined, and for which the constant 0 can be used in a comparison with a value of that type. Thus, the function absolute can be called with any of the number types, such as int, long, and double. Give both the function declaration and the function definition for the template.

3. Define or characterize the template facility for C++.

4. In the template prefix

   template<class T>

   what kind of variable is the parameter T?

   1. T must be a class.

   2. T must not be a class.

   3. T can be only types built into the C++ language.

   4. T can be any type, whether built into C++ or defined by the programmer.

Algorithm Abstraction

As we saw in our discussion of the swapValues function, there is a very general algorithm for interchanging the value of two variables, and this more general algorithm applies to variables of any type. Using a function template, we were able to express this more general algorithm in C++. This is a very simple example of algorithm abstraction. When we say we are using algorithm abstraction, we mean that we are expressing our algorithms in a very general way so that we can ignore incidental detail and concentrate on the substantive part of the algorithm. Function templates are one feature of C++ that supports algorithm abstraction.

Programming Example A Generic Sorting Function

In Chapter 7 we gave a simple sorting algorithm to sort an array of values of type int. The algorithm was realized in C++ code as the function sort, which we gave in Display 7.12. Here we repeat the definition of this function sort:

void sort(int a[], int numberUsed)
{     int indexOfNextSmallest;
    for (int index = 0; index < numberUsed − 1; index++)
    {//Place the correct value in a[index]:         indexOfNextSmallest =
               indexOfSmallest(a, index, numberUsed);
        swapValues(a[index], a[indexOfNextSmallest]);
        //a[0] <= a[1] <=…<= a[index] are the smallest of         //the original array elements. The rest of the         //elements are in the remaining positions.     }
}

If you study this definition of the function sort, you will see that the base type of the array is never used in any significant way. If we replace the base type of the array in the function header with the type double, then we would obtain a sorting function that applies to arrays of values of type double. Of course, we also must adjust the helping functions so they apply to arrays of elements of type double. So let’s consider the helping functions that are called inside the body of the function sort. The two helping functions are swapValues and indexOfSmallest.

Helping functions

We already saw that swapValues can apply to variables of any type, provided we define it as a function template (as in Display 17.1). Let’s see if indexOfSmallest depends in any significant way on the base type of the array being sorted. The definition of indexOfSmallest is repeated next so you can study its details.

int indexOfSmallest(const int a[], int startIndex,
                    int numberUsed)
{     int min = a[startIndex];     int indexOfMin = startIndex;     for (int index = startIndex + 1;
         index < numberUsed; index++)
    {
        if (a[index] < min)
        {
            min = a[index];
            indexOfMin = index;
            //min is the smallest of a[startIndex] through             //a[index]
        }
    }
    return indexOfMin;
}

The function indexOfSmallest also does not depend in any significant way on the base type of the array. If we replaced the two highlighted instances of the type int with the type double, then we will have changed the function indexOfSmallest so that it applies to arrays whose base type is double.

To change the function sort so that it can be used to sort arrays with the base type double, we only needed to replace a few instances of the type name int with the type name double. Moreover, there is nothing special about the type double. We can do a similar replacement for many other types. The only thing we need to know about the type is that the operator < is defined for that type. This is the perfect situation for function templates. If we replace a few instances of the type name int (in the functions sort and indexOfSmallest) with a type parameter, then the function sort can sort an array of values of any type provided that the values of that type can be compared using the < operator. In Display 17.2 we have written just such a function template.

Display 17.2 A Generic Sorting Function

 1    //This is file sortfunc.cpp
 2    template<class T>
 3    void swapValues(T& variable1, T& variable2)
           <The rest of the definition of swapValues is given in  Display 17.1.>
 4     
 5    template<class BaseType>
 6    int indexOfSmallest(const BaseType a[], int startIndex, int numberUsed)
 7    {
 8        BaseType min = a[startIndex];
 9        int indexOfMin = startIndex;
10     
11        for (int index = startIndex + 1; index < numberUsed; index++)
12            if (a[index] < min)
13            {
14                min = a[index];
15                indexOfMin = index;
16                //min is the smallest of a[startIndex] through a[index]
17            }
18      
19        return indexOfMin;
20    }
21     
22    template<class BaseType>
23    void sort(BaseType a[], int numberUsed)
24    {
25    int indexOfNextSmallest;
26    for (int index = 0; index < numberUsed – 1; index++)
27       {//Place the correct value in a[index]:
28              indexOfNextSmallest =
29                    indexOfSmallest(a, index, numberUsed);
30              swapValues(a[index], a[indexOfNextSmallest]);
31           //a[0] <= a[1] <=…<= a[index] are the smallest of the original array 32           //elements. The rest of the elements are in the remaining positions.
33       }
34    }

Notice that the function template sort shown in Display 17.2 can be used with arrays of values that are not numbers. In the demonstration program in Display 17.3, the function template sort is called to sort an array of characters. Characters can be compared using the < operator. Although the exact meaning of the < operator applied to character values may vary somewhat from one implementation to another, some things are always true about how < orders the letters of the alphabet. When applied to two uppercase letters, the operator < tests to see if the first comes before the second in alphabetic order. Also, when applied to two lowercase letters, the operator < tests to see if the first comes before the second in alphabetic order. When you mix uppercase and lowercase letters, the situation is not so well behaved, but the program shown in Display 17.3 deals only with uppercase letters. In that program, an array of uppercase letters is sorted into alphabetical order with a call to the function template sort. (The function template sort will even sort an array of objects of a class that you define, provided you overload the < operator to apply to objects of that class.)

Display 17.3 Using a Generic Sorting Function

Output

Unsorted integers:
9 8 7 6 5 1 2 3 0 4
In sorted order the integers are:
0 1 2 3 4 5 6 7 8 9
Unsorted doubles:
5.5 4.4 1.1 3.3 2.2
In sorted order the doubles are:
1.1 2.2 3.3 4.4 5.5
Unsorted characters:
G E N E R I C
In sorted order the characters are:
C E E G I N R

Figure 17.3 Full Alternative Text

Programming Tip How to Define Templates

When we defined the function template in Display 17.2, we started with a function that sorts an array of elements of type int. We then created a template by replacing the base type of the array with the type parameter T. This is a good general strategy for writing templates. If you want to write a function template, first write a version that is not a template at all but is just an ordinary function. Completely debug the ordinary function and then convert the ordinary function to a template by replacing some type names with a type parameter. There are two advantages to this method. First, when you are defining the ordinary function you are dealing with a much more concrete case, which makes the problem easier to visualize. Second, you have fewer details to check at each stage; when worrying about the algorithm itself, you need not concern yourself with template syntax rules.

Pitfall Using a Template with an Inappropriate Type2

² The example in this Pitfall section uses arrays. If you have not yet covered arrays (Chapter 7), you should skip this Pitfall section and return after covering arrays.

You can use a template function with any type for which the code in the function definition makes sense. However, all the code in the template function must make sense and must behave in an appropriate way. For example, you cannot use the swapValues template (Display 17.1) with the type parameter replaced by a type for which the assignment operator does not work at all or does not work “correctly.”

As a more concrete example, suppose that your program defines the template function swapValues as in Display 17.1. You cannot add the following to your program:

int a[10], b[10];
<some code to fill arrays>
swapValues(a, b);

This code will not work, because assignment does not work with array types.

Self-Test Exercises

5. Display 7.10 shows a function called search, which searches an array for a specified integer. Give a function template version of search that can be used to search an array of elements of any type. Give both the function declaration and the function definition for the template. (Hint: It is almost identical to the function given in Display 7.10.)

6. In Practice Program 8 of Chapter 4 you were asked to overload the abs function so that the name abs would work with several of the built-in types that had been studied at the time. Compare and contrast function overloading of the abs function with the use of templates for this purpose in Self-Test Exercise 2.