Templates: Generic Functions

Templates: Generic Functions

 

Learning Objectives After completing this module, students should be able to: •      Explain why templates are needed and how the compiler instantiates a function template. •      Write generic functions with one or more type parameters. •      Apply generic functions using implicit deduction and explicit template arguments, and explain why deduction can fail. •      Distinguish function templates from function overloading and use an explicit specialization. •      Write practical generic functions (swap, sort, search) and recognise common mistakes.

 

1. Introduction to Templates

A function normally works with specific data types. A function that finds the larger of two int values cannot be used for two double values, so the same logic would have to be written again for each type:

int maximum(int a, int b)          { return (a > b) ? a : b; }

double maximum(double a, double b) { return (a > b) ? a : b; }

 

Both functions perform exactly the same operation; only the data type is different. C++ solves this duplication with templates.

Definition: A template is a mechanism that lets a programmer write a function or a class once, with the data type left as a parameter. The compiler uses the template, together with the types actually supplied, to generate the type-specific code during compilation.

 

Writing code that is independent of any particular data type is called generic programming. The C++ Standard Library (vector, list, map, sort, …) is built almost entirely from templates.

1.1 Advantages

1.      Reusability: one definition serves many types.

2.      Less duplication and easier maintenance: a correction is made in one place.

3.      Type safety: the generated functions are checked by the compiler, unlike macros or void *.

4.      Efficiency: templates are resolved at compile time, so there is no run-time type test.

 

Important: A template does not mean that every operation works with every type. The type supplied must support the operations used in the template body; for example, a > b needs a suitable operator>.

 

2. Generic Functions

A generic function is a function that can operate on different data types without a separate definition for each. In C++ it is written as a function template.

2.1 Syntax

template <typename T>

return_type function_name(T parameter1, T parameter2)

{

    // function body

}

 

Component	Meaning
template	Keyword that starts a template declaration
<typename T>	Template parameter list: T is a type parameter (a placeholder for a type)
return_type	Return type; it may be T, another type, or auto (see Section 5.3)
T parameter1	A function parameter whose type is the type argument

 

T is not a built-in type; it is a name for a type that is chosen when the function is used. Any valid identifier may be used instead of T. For a type parameter the keywords class and typename mean the same:

template <class T>

T square(T value) { return value * value; }

 

Version Note: Function templates have been part of C++ since the first standard (C++98). The keyword typename was added so that it can also be used in other contexts (Module 2, Section 8); in a template parameter list class and typename are interchangeable in every standard.

 

3. How a Function Template Works

A function template is not a function; it is a pattern from which functions are generated. When a call such as maximum(10, 20) is compiled, the compiler deduces T = int and generates (instantiates) the function int maximum(int, int). A call with double arguments generates a second function, and so on. A function is generated only for the types that are actually used.

Figure 1.1: Instantiation of a function template: one definition, one generated function per type used.

•      Instantiation happens at compile time; the program contains the generated functions.

•      The body is checked for each type: if the type does not support an operation, a compile-time error is reported for that instantiation.

•      Many different types lead to many generated functions, which can increase the size of the executable (code bloat).

 

4. Example: A Generic Maximum Function

Program 1.1: Finding the maximum of two values of any comparable type.

#include <iostream>

#include <string>

using namespace std;

 

template <typename T>

T maximum(T a, T b)

{

    return (a > b) ? a : b;

}

 

int main()

{

    cout << "Maximum integer  : " << maximum(10, 20) << endl;

    cout << "Maximum double   : " << maximum(5.5, 2.3) << endl;

    cout << "Maximum character: " << maximum('A', 'Z') << endl;

    cout << "Maximum string   : " << maximum(string("apple"), string("banana"))

        << endl;

    return 0;

}

 

Output:

Maximum integer  : 20

Maximum double   : 5.5

Maximum character: Z

Maximum string   : banana

 

Explanation

1.      template <typename T> declares T as a type parameter.

2.      T maximum(T a, T b) takes two values of the same type T and returns the larger one using the conditional operator.

3.      In maximum(10, 20) both arguments are int, so T = int. With 5.5 and 2.3, T = double; with 'A' and 'Z', T = char.

4.      For char the comparison uses the character codes; in ASCII-compatible encodings 'Z' (90) is greater than 'A' (65).

5.      A string works too, because std::string defines operator>.

 

5. Applying Generic Functions

To apply a generic function means to call it so that the compiler can select or generate the right type-specific function. There are two ways.

5.1 Implicit deduction and explicit template arguments

•      Implicit (template argument deduction): the compiler deduces T from the types of the call arguments: square(5) gives T = int.

•      Explicit: the programmer writes the type in angle brackets: square<double>(5) forces T = double; the argument 5 is converted to double.

 

Explicit arguments are needed when the type cannot be deduced (for example, when it appears only in the return type) or when a particular type is wanted.

Program 1.2: Implicit and explicit template arguments, and the effect of mixed types.

#include <iostream>

using namespace std;

 

template <typename T>

T square(T value)

{

    return value * value;

}

 

template <typename T>

T add(T a, T b)

{

    return a + b;

}

 

int main()

{

    /* implicit deduction */

    cout << square(5) << endl;           // T = int

    cout << square(2.5) << endl;         // T = double

 

    /* explicit template arguments */

    cout << square<int>(5) << endl;

    cout << square<double>(2.5) << endl;

 

    /* add(10, 2.5) would fail: T cannot be both int and double */

    cout << add<double>(10, 2.5) << endl;    // explicit: 10 is converted to double

    cout << add(10, 20) << endl;             // T = int

    return 0;

}

 

Output:

25

6.25

25

6.25

12.5

30

 

The first two lines use deduction, the next two use explicit arguments, and the last two use add: add<double>(10, 2.5) gives 12.5, and add(10, 20) gives 30.

5.2 Why deduction can fail

Template argument deduction examines each argument and must arrive at one type for each template parameter. It does not apply the usual conversions to pick a common type.

Call	Deduced from	Result
add(10, 20)	T = int from both arguments	Valid
add(1.5, 2.5)	T = double from both	Valid
add(10, 2.5)	T = int from the first, T = double from the second	Error: conflicting deduction
add<double>(10, 2.5)	T given explicitly; 10 is converted	Valid: 12.5

 

There are three ways to correct a failing call such as add(10, 2.5): (1) give the type explicitly, add<double>(10, 2.5); (2) cast an argument, add(10.0, 2.5); or (3) use two template parameters, as in the next section.

5.3 Generic functions with multiple template parameters

template <typename T1, typename T2>

return_type function_name(T1 a, T2 b);

 

Now the arguments can have different types. The return type of such a function often depends on both types, so it is written with auto.

Program 1.3: Two type parameters, and a deduced return type.

#include <iostream>

using namespace std;

 

template <typename T1, typename T2>

void display(T1 a, T2 b)

{

    cout << "First value : " << a << endl;

    cout << "Second value: " << b << endl;

}

 

/* C++11: trailing return type */

template <typename T1, typename T2>

auto addOld(T1 a, T2 b) -> decltype(a + b)

{

    return a + b;

}

 

/* C++14: the return type is deduced from the return statement */

template <typename T1, typename T2>

auto add(T1 a, T2 b)

{

    return a + b;

}

 

int main()

{

    display(10, 3.14);

    display('A', 100);

    cout << add(10, 2.5) << endl;

    cout << add(5, 7) << endl;

    cout << addOld(1.5, 2) << endl;

    return 0;

}

 

Output:

First value : 10

Second value: 3.14

First value : A

Second value: 100

12.5

12

3.5

 

Version Note: C++11: the return type must be written explicitly with a trailing return type, as in auto addOld(T1 a, T2 b) -> decltype(a + b). C++14 and later: plain auto is enough; the compiler deduces the return type from the return statement (function add in Program 1.3). Compiled with -std=c++11, Program 1.3 is rejected:

 

p1_multi.cpp:20:1: error: ‘add’ function uses ‘auto’ type specifier without trailing return type

 

6. Function Templates and Function Overloading

Function overloading means several functions with the same name and different parameter lists, each written separately. A function template is one definition from which such functions are generated. The two can be mixed.

Basis	Function overloading	Function template
Definition	Several separate functions with one name	One generic definition
Parameter types	Written separately in every overload	Represented by template parameters
Code duplication	Higher: the body is repeated	Lower: written once
Behaviour for different types	May be completely different	Same algorithm for every type
Type support	Only the declared overloads	Any type that supports the operations used

 

6.1 How the compiler chooses between them

When an ordinary function and a template could both be called, overload resolution prefers the better match, and if the matches are equally good it prefers the ordinary (non-template) function.

Figure 1.2: Order in which candidates are considered when a call is resolved.

6.2 Explicit specialization

Sometimes the generic algorithm is wrong for one particular type. A specialization provides a special version of the template for that type. For example, maximum compares addresses, not text, when applied to C-style strings; a specialization for const char * compares the characters.

Program 1.4: Template, ordinary function with the same name, and an explicit specialization.

#include <iostream>

#include <cstring>

using namespace std;

 

/* Ordinary function */

int display(int x)

{

    return x + 100;

}

 

/* Function template with the same name */

template <typename T>

T display(T x)

{

    return x * 2;

}

 

/* Primary template */

template <typename T>

T maximum(T a, T b)

{

    return (a > b) ? a : b;

}

 

/* Explicit specialization for C-strings: compares the text, not the addresses */

template <>

const char *maximum<const char *>(const char *a, const char *b)

{

    return (strcmp(a, b) > 0) ? a : b;

}

 

int main()

{

    cout << display(10) << endl;        // ordinary function is preferred

    cout << display(2.5) << endl;       // template with T = double

    cout << display<int>(10) << endl;   // explicit <int> forces the template

    cout << maximum("apple", "banana") << endl;

    cout << maximum(3, 9) << endl;

    return 0;

}

 

Output:

110

5

20

banana

9

 

•      display(10) calls the ordinary function (110), because an exact non-template match is preferred.

•      display(2.5) calls the template with T = double (5).

•      display<int>(10) uses the explicit <int> to force the template (20).

•      template <> introduces the explicit specialization; for const char * it uses strcmp(), so maximum("apple", "banana") prints banana.

 

7. Practical Applications of Function Templates

Typical uses are: finding the maximum or minimum, swapping two values, sorting, searching, printing arrays, and writing reusable utility functions. Program 1.5 contains several of them.

Program 1.5: Generic swap, bubble sort, linear search, array printing and array size.

#include <iostream>

using namespace std;

 

template <typename T>

void swapValues(T &a, T &b)

{

    T temp = a;

    a = b;

    b = temp;

}

 

/* Generic bubble sort */

template <typename T>

void bubbleSort(T arr[], int n)

{

    for (int i = 0; i < n - 1; i++)

        for (int j = 0; j < n - 1 - i; j++)

            if (arr[j] > arr[j + 1])

                swapValues(arr[j], arr[j + 1]);

}

 

/* Generic linear search: returns the index or -1 */

template <typename T>

int linearSearch(const T arr[], int n, T key)

{

    for (int i = 0; i < n; i++)

        if (arr[i] == key)

            return i;

    return -1;

}

 

template <typename T>

void printArray(const T arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

    cout << endl;

}

 

/* The array size is deduced from the array type itself */

template <typename T, int N>

int arraySize(T (&)[N])

{

    return N;

}

 

int main()

{

    int a[] = {40, 10, 30, 20};

    double d[] = {2.5, 1.5, 3.5};

    char c[] = {'q', 'a', 'z', 'm'};

 

    bubbleSort(a, arraySize(a));

    bubbleSort(d, arraySize(d));

    bubbleSort(c, arraySize(c));

 

    printArray(a, arraySize(a));

    printArray(d, arraySize(d));

    printArray(c, arraySize(c));

 

    cout << "Index of 30: " << linearSearch(a, arraySize(a), 30) << endl;

    cout << "Index of 9 : " << linearSearch(a, arraySize(a), 9) << endl;

 

    int x = 10, y = 20;

    swapValues(x, y);

    cout << x << " " << y << endl;

    return 0;

}

 

Output:

10 20 30 40

1.5 2.5 3.5

a m q z

Index of 30: 2

Index of 9 : -1

20 10

 

•      swapValues(T &a, T &b) uses references, so the original variables are changed, not copies. Both parameters have the same type T.

•      bubbleSort(T arr[], int n) sorts an array of any type that supports > and assignment; the same code sorted int, double and char arrays.

•      arraySize(T (&)[N]) shows a non-type template parameter N: the compiler deduces the number of elements from the array type, so no size has to be passed.

 

Note: The Standard Library already provides std::swap, std::max, std::min and std::sort. In real programs these should be used. The programs here use different names (swapValues, maximum) on purpose: with using namespace std;, a user-defined template named swap can make the call ambiguous with std::swap and cause the error call of overloaded ‘swap(int&, int&)’ is ambiguous.

 

8. Rules, Limitations and Common Mistakes

1.      Required operations: every operation in the body must be valid for the supplied type.

2.      Deduction must succeed: with f(T, T) a call with an int and a double fails unless the type is given explicitly.

3.      Place the definition in a header file. The compiler needs the whole template body at the point where it instantiates it, so templates are normally defined in headers rather than in a separately compiled .cpp file (see the note about export in Module 2).

4.      Templates do not guarantee speed. They allow efficient type-specific code, but performance depends on the compiler and the algorithm.

5.      Error messages can be long because the error is reported where the template is instantiated.

 

Mistake	Why it is a problem	Correction
Using template but forgetting the parameter list	T is not declared	Write template <typename T> before the function
Calling f(10, 2.5) when both parameters are T	Conflicting deduction	Use explicit arguments, a cast, or two type parameters
Using an operator the type does not provide	Compile error at instantiation	Use a suitable type or overload the operator
Treating T as a real type name	T is only a placeholder	T stands for whichever type is chosen at instantiation
Defining a template only in a .cpp file	Other files cannot instantiate it (linker error)	Put the full definition in a header
Comparing C-strings with a generic >	Compares addresses, not text	Use a specialization or std::string

 

Version Note: C++20 concepts. The informal rule “the type must support the operations” can be written in the code itself as a constraint. If the type does not satisfy it, the compiler reports that the constraint is not satisfied, which is much clearer than a long instantiation error. This works only in C++20 (g++ -std=c++20).

 

#include <iostream>

#include <concepts>

using namespace std;

 

template <typename T>

requires totally_ordered<T>

T maximum(T a, T b) { return (a > b) ? a : b; }

 

 

int main()

{

    cout << maximum(3, 9) << endl;

    return 0;

}

 

9

 

9. Quick Revision

Concept	Key point
Template	Mechanism for generic programming; the compiler generates type-specific code
Generic function	A function template; one definition for many types
typename T / class T	Declare a type parameter (equivalent in a template parameter list)
Instantiation	Generation of a concrete function when a call needs it (at compile time)
Deduction	The compiler finds T from the call arguments; it must find one consistent type
Explicit argument	square<double>(2) specifies T directly
Several parameters	template <typename T1, typename T2> allows different argument types
Specialization	template <> gives a special version for one type
Overload preference	An exact ordinary function beats a template with the same match

 

10. Important Examination Questions

Short-answer questions

1.      Define a template. What is generic programming?

2.      What is a generic function? Write its general syntax.

3.      Differentiate between typename and class in a template parameter list.

4.      What is template argument deduction? When does it fail?

5.      What is an explicit template argument? Give an example.

6.      Can a function template take arguments of different types? Explain.

7.      What is an explicit specialization? Why is it needed?

8.      State four advantages and two limitations of templates.

 

Long-answer and programming questions

1.      Explain function templates with syntax and a complete C++ program.

2.      Write a generic function to find the maximum of two values and show how it is applied to int, double and char.

3.      Explain template argument deduction with examples of success and failure.

4.      Write a program using a function template with two type parameters.

5.      Differentiate between function overloading and function templates.

6.      Write a generic function to swap two variables of the same type. (A single template with T &a, T &b cannot swap an int with a double; this needs two parameters or a conversion.)

7.      Write a generic bubble sort and a generic linear search.

8.      Explain the limitations and common errors of function templates.