Templates in depth

Templates are of great utility to programmers in C++, especially when combined with multiple inheritance and operator overloading. The C++ Standard Template Library (STL) provides many useful functions within a framework of connected templates.

As the templates in C++ are very expressive they may be used for things other than generic programming. One such use is called template metaprogramming, which is a way of pre-evaluating some of the code at compile-time rather than run-time. Further discussion here only relates to templates as a method of generic programming.

There are two kinds of templates. A function template behaves like a function that can accept arguments of many different types. For example, the C++ Standard Template Library contains the function template max(x, y) which returns either x or y, whichever is larger. max() could be defined like this:

template &lt;typename T&gt;
T max(T x, T y)
{
   if (x &lt; y)
   return y;
   else
   return x;
}

template <typename T>

T max(T x, T y)

{

if (x < y)

return y;

else

return x;

}

This template can be called just like a function:

cout &lt;&lt; max(3, 7); // outputs 7

1	cout << max(3, 7); // outputs 7

The compiler determines by examining the arguments that this is a call to max(int, int) and instantiates a version of the function where the type T is int.

There are three primary drawbacks to the use of templates.

First, many compilers historically have very poor support for templates, so the use of templates can make code somewhat less portable.
Second, almost all compilers produce confusing, unhelpful error messages when errors are detected in template code. This can make templates difficult to develop.
Third, each use of a template may cause the compiler to generate extra code (an instantiation of the template), so the indiscriminate use of templates can lead to code bloat, resulting in excessively large executables. The extra instantiations generated by templates can also cause debuggers to have difficulty working gracefully with templates. For example, setting a debug breakpoint within a template from a source file may either miss setting the breakpoint in the actual instantiation desired or may set a breakpoint in every place the template is instantiated.

Default template arguments

The typename keyword

Consider the following:

// Using 'typename' to say it's a type,
// and not something other than a type

template&lt;class T&gt; class X {
// Without typename, you should get an error:
typename T::id i;
public:
void f() { i.g(); }
};

class Y {
public:
class id {
public:
void g() {}
};
};

int main() {
Y y;
X&lt;Y&gt; xy;
xy.f();
} ///:~

// Using 'typename' to say it's a type,

// and not something other than a type

template<class T> class X {

// Without typename, you should get an error:

typename T::id i;

public:

void f() { i.g(); }

};

class Y {

public:

class id {

public:

void g() {}

};

int main() {

Y y;

X<Y> xy;

xy.f();

} ///:~

The template definition assumes that the C++ class T that you hand it must have a nested identifier of some kind called id. But id could be a member object of T, in which case you can perform operations on id directly, but you couldn’t create an object of the type id. However, that’s exactly what is happening here: the identifier id is being treated as if it were actually a nested type inside T. In the case of class Y, id is in fact a nested type, but (without the typename keyword) the compiler can’t know that when it’s compiling X.

If, when it sees an identifier in a template, the compiler has the option of treating that identifier as a type or as something other than a type, then it will assume that the identifier refers to something other than a type. That is, it will assume that the identifier refers to an object (including variables of primitive types), an enumeration or something similar. However, it will not just assume that it is a type. Thus, the compiler gets confused when we pretend it’s a type.

Because the default behavior of the compiler is to assume that a name that fits the above two points is not a type, you must use typename for nested names, even in places where you think that the compiler ought to be able to figure out the right way to interpret the name on its own. In the above example, when the compiler sees T::id, it knows (because of the typename keyword) that id refers to a nested type and thus it can create an object of that type.

The short version of the rule is: if your type is qualified by a template type parameter, you must use typename.

Typedefing a typename

The typename keyword does not automatically create a typedef. A line which reads:
typename Seq::iterator It;

causes a variable to be declared of type Seq::iterator. If you mean to make a typedef, you must say:
typedef typename Seq::iterator It;

Using typename instead of class
With the introduction of the typename keyword, you now have the option of using typename instead of class in the template argument list of a template definition. This may produce code which is clearer:

// Using 'typename' in the template argument list

template&lt;typename T&gt; class X { };

int main() {
X&lt;int&gt; x;
} ///:~

// Using 'typename' in the template argument list

template<typename T> class X { };

int main() {

X<int> x;

} ///:~

You’ll probably see a great deal of code which does not use typename in this fashion, since the keyword was added to the language a relatively long time after templates were introduced.

Function templates

A class template describes an infinite set of classes, and the most common place you’ll see templates is with classes. However, C++ also supports the concept of an infinite set of functions, which is sometimes useful. The syntax is virtually identical, except that you create a function instead of a class.
The clue that you should create a function template is, as you might suspect, if you find you’re creating a number of functions that look identical except that they are dealing with different types. The classic example of a function template is a sorting function. However, a function template is useful in all sorts of places, as demonstrated in the first example that follows. The second example shows a function template used with containers and iterators.

// A string conversion system
//
#ifndef STRINGCONV_H
#define STRINGCONV_H
#include &lt;string&gt;
#include &lt;sstream&gt;

template&lt;typename T&gt;
T fromString(const std::string&amp; s) {
std::istringstream is(s);
T t;
is &gt;&gt; t;
return t;
}

template&lt;typename T&gt;
std::string toString(const T&amp; t) {
std::ostringstream s;
s &lt;&lt; t;
return s.str();
}
#endif // STRINGCONV_H ///:~

// A string conversion system

#ifndef STRINGCONV_H

#define STRINGCONV_H

#include <string>

#include <sstream>

template<typename T>

T fromString(const std::string& s) {

std::istringstream is(s);

T t;

is >> t;

return t;

}

template<typename T>

std::string toString(const T& t) {

std::ostringstream s;

s << t;

return s.str();

}

#endif // STRINGCONV_H ///:~

Here’s a test program, that includes the use of the Standard Library complex number type:

#include "stringConv.h"
#include &lt;iostream&gt;
#include &lt;complex&gt;
using namespace std;

int main() {
int i = 1234;
cout &lt;&lt; "i == \"" &lt;&lt; toString(i) &lt;&lt; "\"\n";
float x = 567.89;
cout &lt;&lt; "x == \"" &lt;&lt; toString(x) &lt;&lt; "\"\n";
complex&lt;float&gt; c(1.0, 2.0);
cout &lt;&lt; "c == \"" &lt;&lt; toString(c) &lt;&lt; "\"\n";
cout &lt;&lt; endl;

i = fromString&lt;int&gt;(string("1234"));
cout &lt;&lt; "i == " &lt;&lt; i &lt;&lt; endl;
x = fromString&lt;float&gt;(string("567.89"));
cout &lt;&lt; "x == " &lt;&lt; x &lt;&lt; endl;
c = fromString&lt; complex&lt;float&gt; &gt;(string("(1.0,2.0)"));
cout &lt;&lt; "c == " &lt;&lt; c &lt;&lt; endl;
} ///:~

The output is what you'd expect:
i == "1234"
x == "567.89"
c == "(1,2)"

i == 1234
x == 567.89
c == (1,2)

#include "stringConv.h"

#include <iostream>

#include <complex>

using namespace std;

int main() {

int i = 1234;

cout << "i == \"" << toString(i) << "\"\n";

float x = 567.89;

cout << "x == \"" << toString(x) << "\"\n";

complex<float> c(1.0, 2.0);

cout << "c == \"" << toString(c) << "\"\n";

cout << endl;

i = fromString<int>(string("1234"));

cout << "i == " << i << endl;

x = fromString<float>(string("567.89"));

cout << "x == " << x << endl;

c = fromString< complex<float> >(string("(1.0,2.0)"));

cout << "c == " << c << endl;

} ///:~

The output is what you'd expect:

i == "1234"

x == "567.89"

c == "(1,2)"

i == 1234

x == 567.89

c == (1,2)

Type induction in function templates

As a simple but very useful example, consider the following:

// discover the size of an array
#ifndef ARRAYSIZE_H
#define ARRAYSIZE_H

template&lt;typename T, int size&gt;
int asz(T (&amp;)[size]) { return size; }

#endif // ARRAYSIZE_H ///:~

// discover the size of an array

#ifndef ARRAYSIZE_H

#define ARRAYSIZE_H

template<typename T, int size>

int asz(T (&)[size]) { return size; }

#endif // ARRAYSIZE_H ///:~

This actually figures out the size of an array as a compile-time constant value, without using any sizeof( ) operations! Thus you can have a much more succinct way to calculate the size of an array at compile time:

//{-msc}
//{-bor}
// The return value of the template function
// asz() is a compile-time constant
#include "../arraySize.h"

int main() {
int a[12], b[20];
const int sz1 = asz(a);
const int sz2 = asz(b);
int c[sz1], d[sz2];
} ///:~

//{-msc}

//{-bor}

// The return value of the template function

// asz() is a compile-time constant

#include "../arraySize.h"

int main() {

int a[12], b[20];

const int sz1 = asz(a);

const int sz2 = asz(b);

int c[sz1], d[sz2];

} ///:~

Of course, just making a variable of a built-in type a const does not guarantee it’s actually a compile-time constant, but if it’s used to define the size of an array (as it is in the last line of main( )), then it must be a compile-time constant.

Taking the address of a generated function template
There are a number of situations where you need to take the address of a function. For example, you may have a function that takes an argument of a pointer to another function. Of course it’s possible that this other function might be generated from a template function so you need some way to take that kind of address :

// Taking the address of a function generated
// from a template.
//{L} ../TestSuite/Test

template &lt;typename T&gt; void f(T*) {}

void h(void (*pf)(int*)) {}

template &lt;class T&gt;
void g(void (*pf)(T*)) {}

int main() {
// Full type exposition:
h(&amp;f&lt;int&gt;);
// Type induction:
h(&amp;f);
// Full type exposition:
g&lt;int&gt;(&amp;f&lt;int&gt;);
// Type inductions:
g(&amp;f&lt;int&gt;);
g&lt;int&gt;(&amp;f);
} ///:~

// Taking the address of a function generated

// from a template.

//{L} ../TestSuite/Test

template <typename T> void f(T*) {}

void h(void (*pf)(int*)) {}

template <class T>

void g(void (*pf)(T*)) {}

int main() {

// Full type exposition:

h(&f<int>);

// Type induction:

h(&f);

// Full type exposition:

g<int>(&f<int>);

// Type inductions:

g(&f<int>);

g<int>(&f);

} ///:~

This example demonstrates a number of different issues. First, even though you’re using templates, the signatures must match the function h( ) takes a pointer to a function that takes an int* and returns void, and that’s what the template f produces. Second, the function that wants the function pointer as an argument can itself be a template, as in the case of the template g.

In main( ) you can see that type induction works here, too. The first call to h( ) explicitly gives the template argument for f, but since h( ) says that it will only take the address of a function that takes an int*, that part can be induced by the compiler. With g( ) the situation is even more interesting because there are two templates involved. The compiler cannot induce the type with nothing to go on, but if either f or g is given int, then the rest can be induced.

Member function templates

It’s also possible to make apply( ) a member function template of the class. That is, a separate template definition from the class template, and yet a member of the class. This may produce a cleaner syntax:

dogs.apply(&amp;Gromit::sit);

1	dogs.apply(&Gromit::sit);

The definition of the apply( ) functions turn out to be cleaner, as well, because they are members of the container. To accomplish this, a new container is inherited from one of the existing STL sequence containers and the member function templates are added to the new type. However, for maximum flexibility we’d like to be able to use any of the STL sequence containers, and for this to work a template-template must be used, to tell the compiler that a template argument is actually a template, itself, and can thus take a type argument and be instantiated. Here is what it looks like after bringing the apply( ) functions into the new type as member functions:

// applySequence.h modified to use
// member function templates

template&lt;class T, template&lt;typename&gt; class Seq&gt;
class SequenceWithApply : public Seq&lt;T*&gt; {
public:
// 0 arguments, any type of return value:
template&lt;class R&gt;
void apply(R (T::*f)()) {
iterator it = begin();
while(it != end()) {
((*it)-&gt;*f)();
it++;
}
}
// 1 argument, any type of return value:
template&lt;class R, class A&gt;
void apply(R(T::*f)(A), A a) {
iterator it = begin();
while(it != end()) {
((*it)-&gt;*f)(a);
it++;
}
}
// 2 arguments, any type of return value:
template&lt;class R, class A1, class A2&gt;
void apply(R(T::*f)(A1, A2),
A1 a1, A2 a2) {
iterator it = begin();
while(it != end()) {
((*it)-&gt;*f)(a1, a2);
it++;
}
}
}; ///:~

// applySequence.h modified to use

// member function templates

template<class T, template<typename> class Seq>

class SequenceWithApply : public Seq<T*> {

public:

// 0 arguments, any type of return value:

template<class R>

void apply(R (T::*f)()) {

iterator it = begin();

while(it != end()) {

((*it)->*f)();

it++;

}

// 1 argument, any type of return value:

template<class R, class A>

void apply(R(T::*f)(A), A a) {

iterator it = begin();

while(it != end()) {

((*it)->*f)(a);

it++;

}

// 2 arguments, any type of return value:

template<class R, class A1, class A2>

void apply(R(T::*f)(A1, A2),

A1 a1, A2 a2) {

iterator it = begin();

while(it != end()) {

((*it)->*f)(a1, a2);

it++;

}

}; ///:~

Because they are members, the apply( ) functions don’t need as many arguments, and the iterator class doesn’t need to be qualified. Also, begin( ) and end( ) are now member functions of the new type and so look cleaner as well. However, the basic code is still the same.
You can see how the function calls are also simpler for the client programmer:

// Test applyMember.h
//{L} ../TestSuite/Test
//{-g++}
//{-msc}
#include "Gromit.h"
#include "applyMember.h"
#include &lt;vector&gt;
#include &lt;iostream&gt;
using namespace std;

int main() {
SequenceWithApply&lt;Gromit, vector&gt; dogs;
for(int i = 0; i &lt; 5; i++)
dogs.push_back(new Gromit(i));
dogs.apply(&amp;Gromit::speak, 1);
dogs.apply(&amp;Gromit::eat, 2.0f);
dogs.apply(&amp;Gromit::sleep, 'z', 3.0);
dogs.apply(&amp;Gromit::sit);
} ///:~

// Test applyMember.h

//{L} ../TestSuite/Test

//{-g++}

//{-msc}

#include "Gromit.h"

#include "applyMember.h"

#include <vector>

#include <iostream>

using namespace std;

int main() {

SequenceWithApply<Gromit, vector> dogs;

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

dogs.push_back(new Gromit(i));

dogs.apply(&Gromit::speak, 1);

dogs.apply(&Gromit::eat, 2.0f);

dogs.apply(&Gromit::sleep, 'z', 3.0);

dogs.apply(&Gromit::sit);

} ///:~

Conceptually, it reads more sensibly to say that you’re calling apply( ) for the dogs container.

Preventing template bloat

Each time you instantiate a template, the code in the template is generated anew (except for inline functions). If some of the functionality of a template does not depend on type, it can be put in a common base class to prevent needless reproduction of that code.

// Templatized InheritStack.cpp
#ifndef NOBLOAT_H
#define NOBLOAT_H
#include "../C0B/Stack4.h"

template&lt;class T&gt;
class NBStack : public Stack {
public:
void push(T* str) {
Stack::push(str);
}
T* peek() const {
return (T*)Stack::peek();
}
T* pop() {
return (T*)Stack::pop();
}
~NBStack();
};

// Defaults to heap objects &amp; ownership:
template&lt;class T&gt;
NBStack&lt;T&gt;::~NBStack() {
T* top = pop();
while(top) {
delete top;
top = pop();
}
}
#endif // NOBLOAT_H ///:~

// Templatized InheritStack.cpp

#ifndef NOBLOAT_H

#define NOBLOAT_H

#include "../C0B/Stack4.h"

template<class T>

class NBStack : public Stack {

public:

void push(T* str) {

Stack::push(str);

}

T* peek() const {

return (T*)Stack::peek();

}

T* pop() {

return (T*)Stack::pop();

}

~NBStack();

};

// Defaults to heap objects & ownership:

template<class T>

NBStack<T>::~NBStack() {

T* top = pop();

while(top) {

delete top;

top = pop();

}

#endif // NOBLOAT_H ///:~

As before, the inline functions generate no code and are thus “free.” The functionality is provided by creating the base-class code only once. However, the ownership problem has been solved here by adding a destructor (which is type-dependent, and thus must be created by the template). Here, it defaults to ownership. Notice that when the base-class destructor is called, the stack will be empty so no duplicate releases will occur.

//{L} ../TestSuite/Test
#include "Nobloat.h"
#include "../require.h"
#include &lt;fstream&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;
using namespace std;

int main() {
ifstream in("NobloatTest.cpp");
assure(in, "NobloatTest.cpp");
NBStack&lt;string&gt; textlines;
string line;
// Read file and store lines in the stack:
while(getline(in, line))
textlines.push(new string(line));
// Pop the lines from the stack and print them:
string* s;
while((s = (string*)textlines.pop()) != 0) {
cout &lt;&lt; *s &lt;&lt; endl;
delete s;
}
} ///:~

//{L} ../TestSuite/Test

#include "Nobloat.h"

#include "../require.h"

#include <fstream>

#include <iostream>

#include <string>

using namespace std;

int main() {

ifstream in("NobloatTest.cpp");

assure(in, "NobloatTest.cpp");

NBStack<string> textlines;

string line;

// Read file and store lines in the stack:

while(getline(in, line))

textlines.push(new string(line));

// Pop the lines from the stack and print them:

string* s;

while((s = (string*)textlines.pop()) != 0) {

cout << *s << endl;

delete s;

}

} ///:~

Explicit instantiation

At times it is useful to explicitly instantiate a template; that is, to tell the compiler to lay down the code for a specific version of that template even though you’re not creating an object at that point. To do this, you reuse the template keyword as follows:

template class Bobbin&lt;thread&gt;;
template void sort&lt;char&gt;(char*[]);

1 2	template class Bobbin<thread>; template void sort<char>(char*[]);

Here is a version of the Sorted.cpp example that explicitly instantiates a template before using it:

//{-msc}
#include "Urand.h"
#include "Sorted.h"
#include &lt;iostream&gt;
using namespace std;
// Explicit instantiation:
template class Sorted&lt;int&gt;;

int main() {
Sorted&lt;int&gt; is;
Urand&lt;47&gt; rand1;
for(int k = 0; k &lt; 15; k++)
is.push_back(rand1());
is.sort();
for(int l = 0; l &lt; is.size(); l++)
cout &lt;&lt; is[l] &lt;&lt; endl;
} ///:~

//{-msc}

#include "Urand.h"

#include "Sorted.h"

#include <iostream>

using namespace std;

// Explicit instantiation:

template class Sorted<int>;

int main() {

Sorted<int> is;

Urand<47> rand1;

for(int k = 0; k < 15; k++)

is.push_back(rand1());

is.sort();

for(int l = 0; l < is.size(); l++)

cout << is[l] << endl;

} ///:~

In this example, the explicit instantiation doesn’t really accomplish anything; the program would work the same without it. Explicit instantiation is only for special cases where extra control is needed. Here is a complete source code of templates in C++.