Generic Programming

3.5. Technical overview

There are two kinds of templates: function templates and class templates. A function template is a pattern for creating ordinary functions based upon the parameterizing types supplied when instantiated. For example, the C++ Standard Template Library contains the function template max(x, y) that creates functions that return either x or y, whichever is larger. max() could be defined like this:

template <typename T>   
T max(T x, T y) {
  return x < y ? y : x;
}

Specializations of this function template, instantiations with specific types, can be called just like an ordinary function:

std::cout << max(3, 7);  // Outputs 7.

The compiler examines the arguments used to call max and determines that this is a call to max(int, int). It then instantiates a version of the function where the parameterizing type T is int, making the equivalent of the following function:

int max(int x, int y) {
  return x < y ? y : x;
}

This works whether the arguments x and y are integers, strings, or any other type for which the expression x < y is sensible, or more specifically, for any type for which operator< is defined. Common inheritance is not needed for the set of types that can be used, and so it is very similar to duck typing. A program defining a custom data type can use operator overloading to define the meaning of < for that type, thus allowing its use with the max() function template. 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 or to be put inside data structures such as sets, heaps, and associative arrays.

C++ templates are completely type safe at compile time. As a demonstration, 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 unless a comparison (in the form of a functor or function) is provided. E.g.: A complex cannot be used as key for a map unless a comparison is provided. Unfortunately, compilers historically generate somewhat esoteric, long, and unhelpful error messages for this sort of error. Ensuring that a certain object adheres to a method protocol can alleviate this issue. Languages which use compare instead of < can also use complex values as keys.

The second kind of template, a class template, extends the same concept to classes. A class template specialization is a class. 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, that work for any compatible parameterizing types.