Templates in C++: Passing Types¶
C++ provides a powerful technique called templates (or generics) that let you pass a type to a function or class in a way that allows the compiler to still do static type checking.
As an example, consider these two functions:
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
void swap(string& a, string& b) {
string temp = a;
a = b;
b = temp;
}
The only difference is that one uses the type int, and the other uses the
type string. Templates let you pass the type to the function so you need
write only one function to handle both cases:
template<class T>
void swap(T& a, T& b) {
T temp = a;
a = b;
b = temp;
}
// ...
int x = 3;
int y = 4;
swap(x, y); // T is int
string s = "cat";
string t = "dog";
swap(s, y); // T is string
The C++ compiler infers at compile-time what the value of the template
variable T` ought to be by examining the types of the variables passed to
``swap. This generic swap function works with any type of value that has
assignment defined for it.
Generic Algorithms¶
C++’s standard template library (STL) implements numerous fundamental data
structures and algorithms in this way. For example, here is how the find
function in the STL is often implemented:
template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)
{
for (; first != last; ++first) {
if (*first == value) {
return first;
}
}
return last;
}
The template here has two input types: one called InputIt (an input
iterator type), and T (the type of the objects being searched). In C++,
iterator types are essentially objects that act like pointers, i.e. iterators
are objects that refer to other objects, and can be compared, incremented, and
de-referenced like regular pointers.
The parameters to find are two iterators, first and last, that
specify a range of objects. Many programmers find this to be an unusual way of
calling at algorithm, but with practice it soon becomes natural. Plus, this
approach turns out to be extremely flexible, allow you to, for instance,
easily search sub-sequence of an array or vector or any other container where
that makes sense.
For example, here is how you can use the STL sort function to sort the
“middle” part of an array and a vector:
int arr[] = {7, 9, 1, -4, 0, 2, 2};
vector<int> vec = {8, 1, 1, 2, 8, 9, 0, 1};
sort(arr + 1, arr + 6);
for(int x : arr) cout << x << ' ';
cout << '\n';
sort(vec.begin() + 1, vec.end() - 1);
for(int x : vec) cout << x << ' ';
Generic Containers¶
Another important application of templates in C++ is to create type-safe
collections of objects. For example, vector<T> is the type of a vector
containing just objects of type T. Type-safe means that you will get a
compiler-time error if you try to put an object that is not of type T in
it.
Comments on Templates¶
An example of the power (and complexity!) of templates, a technique known as template meta-programming can be used to make C++ templates perform any calculation at compile-time. This actually has practical uses, such as for fix-sized vectors, or doing small matrix computations.
While many basic examples of using templates are easy to understand and use, C++ templates have many subtle rules that make them one of the most complex features in C++.
A significant problem with C++ templates in practice is that the error messages they generate, sometimes even for simple errors, can be hundreds thousands of characters long (see the The Grand C++ Error Explosion Competition for some pathological examples of C++ errors — the winner resulted in an error message almost six billion times the size of the program that produced it). This makes it quite hard to debug template errors.
Other languages, such as Java, C#, and Ada, implement variations of templates, but with various different rules, restrictions, and performance characteristics.
Generics (not) in Go¶
Go has a reputation for being a simple language, but some programmers think it is too simple. In particular, many programmers criticize Go for its lack of generics.
Go doesn’t have a any feature quite like C++ templates, and so this means you can end up re-writing Go functions that are identical except for the type of a variable, e.g.:
func maxFloat64(a, b float64) float64 {
if a > b {
return a
} else {
return b
}
}
func maxString(a, b string) string {
if a > b {
return a
} else {
return b
}
}
Go does have a trick for dealing with unknown types: interface{}.
Basically, you can use interface{} to declare variables that can refer to
any type, e.g.:
var a interface{} // the value a refers to can be any type
a = 5
fmt.Println(a) // 5
a = "cat"
fmt.Println(a) // cat
However, you cannot write a function like this:
func max(a, b interface{}) interface{} {
if a > b {
return a
} else {
return b
}
}
There are a couple of problems with this:
- It’s not necessarily the case that
aandbwork with the>operator. - For a sensible
maxfunction,a,b, and the function’s return type should all be the same type. But nothing inmaxensures that they are.
If you write a Haskell type signature for a max function, you can see
what Go_ is missing:
maxGood :: Ord t => t -> t -> t
This says that the two inputs to maxGood, and its output, must all have
the same type t. Furthermore, t must implement the Ord type class,
meaning that the inputs to maxGood must be comparable using >.
The Go function using interface{} would be the same as this Haskell
function:
maxWrong :: t -> u -> v
The types for this function need not be the same, and there is no requirement
that > works for any of them.
The issue of generics in Go has been around since Go was first released, and many programmers have strong opinions. Some feel that Go desperately needs generics, while others feel that the benefits of generics don’t outweigh the extra burden they will put on the compiler and the programmer. A number of proposals have been put forward for adding generics to Go, but so far the developers of Go haven’t committed to adding them.