An introduction to C++ templates

Introduction

Templates are a very powerful – but often very confusing – mechanism within C++. However, approached in stages, templates can be readily understood (despite their heinous syntax).

The aim of this series of articles is to guide beginners through the syntax and semantics of the foundation concepts in C++ template programming.

Let’s start simple and familiar…

Generic programming

With a strongly-typed language we may find ourselves having to implement a different version of a common function for each type we have to deal with:

image

This can be tedious, error prone and time-consuming (especially if there is a common bug). It also can lead to code bloat for library code when you want to support as many types as possible (even though good compilers may optimise away unreferenced code).

An alternative, using a C approach, is to define a macro and let the C pre-processor expand it. This is generally OK for base types, but what if the macro arguments are more complex, or we can get unwanted side effects?

image

Since the macro is evaluated by the pre-processor (before compilation) it is working purely on the source code text, which means:

  • Parameters are not type-checked
  • Parameters are not evaluated

The subtle problem with the shown macro is that the value of one of its arguments will be evaluated twice, once during the test and once when calculating the return value. Consider:

image

Template functions

Template functions extend the capabilities of the function-like macro to allow the compiler (rather than the pre-processor) to create new functions based on some ‘scaffold’ code written by the programmer.

Variables and arguments in the template code can be parameterised for different types, allowing the compiler to generate different variants on the function, as required.

Candidate functions for templates are those whose implementation remains invariant over a set of instances. That is, the algorithmic behaviour of the code is the same, independent of the type of objects the algorithm is processing.

image

The keyword template always begins a definition and declaration of a function template. The <> brackets contain a list of template parameters. The replaceable elements in the code – the template parameters – must be identified as such in the template parameter list.

The keyword typename tells the compiler that what follows is the name of a type (occasionally, you may see the keyword class in its place, but this can be confusing so I have avoided it in this article)

To use the template function you call it with the required type in angle-brackets. The compiler will generate a new function for each new type parameter you supply.

In many cases the template type can be deduced from the invocation of the function. For example min has two arguments and a return type all of the same type. In the call min(10,20) both arguments are integers, therefore the compiler can deduce that typename T maps onto int.

image

If it cannot deduce the type from the argument – e.g. min (10, 20.9) (and note, there are no conversion rules) then a compiler error message is generated. This can be resolved by forcing the type using explicit instantiation.

Under the hood

New code is generated for each new type that the compiler encounters. The compiler uses the template code to generate a new function with the template parameter replaced by the supplied type.

A template instance is only created once. If multiple calls to min with int or double arguments are encountered (or any type for that matter) then still only one set of object code is created per translation unit.

image

Multiple template parameters

If differing types are required, then multiple type parameters can be specified.

image

Unfortunately, in this form a return type cannot be deduced, so you have to add it explicitly as a template parameter. By making it the first parameter, the other parameters can be deduced.

image

Note, the programmer is responsible for specifying the return type, and an incorrect choice could lead to truncation (for example supplying an integer return type for two floating point parameters)

This is somewhat clumsy – particularly for library code – so a new mechanism was introduction for C++11.

The decltype keyword deduces the type of an expression. C++ is an expression-based language. All expressions have both a value (the result) and a type. The decltype operator simply returns the type, rather than the value.

We can use decltype to deduce the return type from functions, too. Here’s a first attempt with our min function:

image

First thing to note: the expression inside the decltype isn’t evaluated, so we must still have the expression inside the body of the function.

Second (and far more important): This code will not compile! decltype is trying to evaluate an expression based on the types of a and b, but they have not been declared yet.

To fix this we need to use trailing return type syntax, instead.

image

Putting the return type after the parameter list allows the parameters to be used to specify the return type. The keyword auto is required to tell the compiler the return type is specified after the parameters

Problems with template functions

Whenever you use a template function then certain requirements will be placed on the argument type. If the type does not support the operation then the compiler will generate an error message (deciphering these message is a real art and very compiler-dependent). The error will normally be flagged in the template code not at the Point-of-Instantiation (PoI). This can make using templates sometime very frustrating.

image

In the above example, we are attempting to use our min template function with some abstract data type (class ADT). When we compile we get an error in the template function – type T must support operator<.

Remember, for a class type the expression (a < b) resolves to (a.operator<(b))

In this instance the compiler has no way of comparing two ADT objects, so get our code to work we must supply an overload for operator< on the class ADT that allows us to compare them (I’ll leave that as an exercise to the reader!)

Function overloading and templates

Sometimes template expansion may generate either incorrect or inefficient versions.

image

The output from this example is just as likely to be ‘world’ as ‘hello’. When comparing string literals the compiler deduces the template type as const char*; therefore the function is comparing pointer values, rather than strings. The answer you get depends on the order the compiler stores the string literals in the program.

Usefully, template functions (just like any other function) can be overloaded.

image

In the code above we have written a free function version of min that uses the C standard library function strcmp (which correctly identifies “hello” < “world”).

When you call min the compiler is required to deduce the template parameters (which are, of course, of type const char*). This causes a problem: The template instantiation will be const char* min(const char*, const char*), which matches the non-template overload of the function The compiler will always prefer the non-template versions in such cases.

In the second case we are explicitly instantiating (and calling) the template function with const char*; there is no type deduction, so no ambiguity.

Summary

Template functions are a useful mechanism for implementing ‘generic’ algorithms – that is, those algorithms where the only difference is the types of the parameters being operated on.

However, the real power of templates starts when we combine template functions with classes.

So that’s what we’ll look at next time.

Posted on May 29th, 2014
» Feed to this thread
» Trackback

2 Comments a “An introduction to C++ templates”

  1. GWO says:

    Actually, the macro you give is even worse than you originally thought. There’s no sequence point between your repeated modification of i or j, so you can’t even be sure that m=7. If you want to be technically correct (“the best sort of correct”) that’s undefined behaviour, and the compiler is free to do what ever it likes.

  2. glennan says:

    Excellent point!

    I think the best rule-of-thumb has to be: “Don’t try to use Generics in a language that doesn’t support them.”

    (Well, not unless you REALLY like spending long hours at the office fixing subtle bugs)

Leave a Reply