Lesson 17 - Templates

Example Program

// If you are not sure what some lines of code do, try looking back at
// previous example programs, notes, or ask a question.

#include <iostream>

using namespace std;

// See last example for comments on the list data structure
// Comments here are only for template features


// Our forward declaration has to be template
template <typename T> class LinkedList;

// Here our node is templated so nodes can hold an arbitrary data type
template <typename T> 
class node {
	// Our value parameter is of our template parameter "T"
	// This is also implemented here, in the class definition
	node(T v, node* n = NULL) {
		value = v;
		next = n;
	}
	// Don't need this to do anything
 	~node() {}

	// The value this node holds should, of course, be of generic type "T"
	T value;
	node* next;

	// Note that we must specify that LinkedList is templated
	friend class LinkedList<T>;

	// We can't implement a friend here, as it's not a member
	// We also have to specify what kind of list we're outputting, so we do LinkedList<type>.
	// Hence, the friend must also be templated. Note that the template declaration goes before
	// "friend," and that we must use U as our argument, as T is already defined.
	template <typename U> 
	friend ostream& operator<<(ostream& out, const LinkedList<U>& src);
};

// Here our actual list is templated to accommodate the templated nodes and arbitrary data input/output
template <typename T> 
class LinkedList {
public:
	LinkedList() {
		head = NULL;
	}
	// We need a copy constructor for later
	LinkedList(const LinkedList& src) {
		head = NULL;
		node<T>* temp = src.head;
		while(temp) {
			addValue(temp->value);
			temp = temp->next;
		}
	}
	// We need an assignment operator for later
	LinkedList& operator=(const LinkedList& src) {
		while(head) {
			node<T>* temp = head->next;
			delete head;
			head = temp;
		}
		node<T>* temp = src.head;
		while(temp) {
			addValue(temp->value);
			temp = temp->next;
		}
	}
	~LinkedList() {
		while(head) {
			node<T>* temp = head->next;
			delete head;
			head = temp;
		}
	}

	// Here we add a value of generic type T
	void addValue(T value) {
		head = new node<T>(value,head);
	}
	// Here we remove a value, returning generic type T
	T removeValue() {
		T result;
		if(head) {
			result = head->value;
			node<T>* temp = head->next;
			delete head;
			head = temp;
		}
		return result;
	}

	// Again, we can't implement a friend here, and we must specify that the LinkedList uses type U
	template <typename U> 
	friend ostream& operator<<(ostream& out, const LinkedList<U>& src);

private:
	// Our node must use generic type T
	node<T>* head;
};

// Here we actually implement our friend, note the use of another template
template <typename T>
ostream& operator<<(ostream& out, const LinkedList<T>& src) {
	node<T>* temp = src.head;
	while(temp) {
		// Output brackets for list-of-list clarity
		// Later, we create a list of lists, so in that case "out << temp->value"
		// will actually recursively call this function 
		out << "[" << temp->value << "]";
		if(temp->next) {
			out << " -> ";
		}

		temp = temp->next;
	}

	return out;
}

int main() {
	// Declare list using integers
	LinkedList<int> intList;
	// Declare list using floats
	LinkedList<float> floatList;
	
	// Prior to c++11, you have to leave a space between two '>' brackets in a
	// nested template, otherwise the compiler thinks you're using the ">>" operator 
	
	// Declare list using lists that use integers
	LinkedList<LinkedList<int> > listList;

	// Output lists
	cout << "Int list: " << intList << endl;
	cout << "Float list: " << floatList << endl;
	cout << "List list: " << listList << endl;

	// Add values to the int list
	for(int index = 0; index < 10; index++) {
		intList.addValue(index);
	}

	// Add values to the float list
	for(float index = 0.5; index < 10; index++) {
		floatList.addValue(index);
	}

	// Add values to list list
	for(int index = 0; index < 10; index++) {
		LinkedList<int> value;
		for(int index = 0; index < 10; index++) {
			value.addValue(index);
		}
		listList.addValue(value);
	}

	// Output lists
	cout << "Int list: " << intList << endl;
	cout << "Float list: " << floatList << endl;
	cout << "List list: " << listList << endl;

	system("pause");
	return 0;	
}

Generic Programming

Generic programming allows one to specify logic without knowing or caring about the type of data to be used. Generic programming is particularly useful for abstracting data structures, in which case all you have to think about is the logic behind the structure's organization. For example, you could can create a type-agnostic "list" data, and it will work whether it holds integers, strings, or even more lists.

C++ Templates

This topic will be the first (and only) lesson in the basic C++ section that is really specific to C++. Many languages support generic programming, but C++'s implementation—templates—is relatively unique.

Templates give you the ability to make functions and data structures type-agnostic. However, they sometimes cause more problems than they solve. They are hard to validate for all cases, they can significantly slow compilation time, old C++ compilers don’t support them, and related error messages are practically incomprehensible. (Seriously—template errors can be hundreds of lines and only directly give you the line number of the error.)

Most of these problems arise from the fact that templates are not compiled into code in C++. This is because to compile truly type-agnostic functions and objects would incur significant performance overhead, and the main strength of C++ is its low overhead and high execution speed. Instead, the C++ compiler generates specific versions of templates whenever they are instantiated.

In basic terms, the compiler automatically writes an "int" version of your object if you instantiate the template with an "int," a "float" version if you instantiate it with a "float," etc. This code, using concrete data types, is actually compiled. You might see how this can cause problems. Of course, the compiler can't generate code for every possible combination of your template parameters, so it only does so when they are specified. Consequently, buggy, even uncompilable code may lie dormant until one day, you instantiate a template with a new type and all hell breaks loose.

Additionally, you can do some pretty crazy metaprogramming with templates. There's nested templates, template recursion, template functors, and much more. But that's not to say that you should. You shouldn't. It's needlessly overcomplicated.

If there is one piece of advice for using templates, it would simply be to seriously consider if using templates is actually making your code more straightforward and your life easier. If you're using templates for more than type plasticity, the answer is likely no.

So, why would you want to use templates? Most of the time, you won’t. However, when used intelligently, they can be effective in allowing you to easily reuse data structures and methods. Finally, the C++ Standard Template Library (STL) is, as the name implies, built around templates. Even if you never create your own, you should be at least familiar with using templates.

Template Functions

When declaring any template, begin with the word “template," then add template parameters. Template parameters, specified in pointy brackets, can be normal parameter data—or type names. The type of a type name parameter can be either "typename" or "class." (Bit of a mouthful.)

template <typename T, int x>
// templated thing

Within your templated object or function, template parameters can be used as constants or actual data types. This is what makes it generic: the arbitrary type parameter can be used specify variables, pointers, the function return type, parameters—anything.

For example, a templated function that creates an array of any type of any length...

template <typename T, int n>
T* createArray() {
	return new T[n];
}

Here, “n” could be passed as a normal parameter, but for the sake of the example it’s a template parameter.

Since templates abstract data types, when actually using a templated function or object, you must specify what types you’re working with. Passing template parameters parallels passing normal parameters, except that values can now include type names. Template parameters are passed inside pointy brackets, before your actual parameters. For example, to tell the previous example to allocate an array of 10 integers...

int* array = createArray<int,10>();

Here, we pass “int” as the type name “T,” and “10” as the integer template parameter “n.” The function will allocate an array of 10 integers.

Template Parameters

Another useful feature of templates is that if possible, the compiler will automatically detect what types you’re using, allowing you to omit the template parameters. For example...

template <typename T>
T abs_value(T value) {
	if(value < 0) return –value;
	return value;
}

int main() {
	float f = abs_value(5.45f);	   // This call will automatically use “float” as “T”
	int i = abs_value(-10);	   // This call will automatically use “int” as “T”
}

Just like functions, templates can have default parameters. They work in exactly the same way as function default parameters. They are also declared in the same way: in the template definition, simply set a parameter equal to its default value.

template <typename T = float>
T divide(float x, float y) {
	return x / y;
}

int main() {
	float f = divide(5,7);
	int i = divide<int>(5,7);
}

This example is a little contrived, as this isn't really how you would use default template parameters. However, it illustrates how if you leave out the template parameter, the function will automatically return a float. Default template parameters will be more useful when creating data structures.

Templates can be used to create many useful utility functions, but the main use is creating reusable data structures.

Template Structures & Classes

Declaring a templated structure or class is much the same as templating a function: you begin with the keyword “template” and the template parameters, then declare the class/struct as usual. In the declaration, you can use your template parameters as constants or types.

For example, to create a “vector” structure that contains N elements of type T....

template <typename T, int N>
class Vector {
public:
	Vector& operator=(const Vector& src);
	T operator*(const Vector& other);
private:
	T elements[N];
};

In this case, N would not work as a normal parameter, as you cannot create a static array of non-constant size. However, as a template parameter, N is considered a constant at compile time. Note that the “Vector” type is still used normally, and “T” can be used as the return type for the * operator.

The syntax to implement external member functions of a templated struct/class is very obtuse, as you have to declare the member as a template, and each time you were to write the class type, you have to write the type with all template parameters.

template <typename T, int N>
Vector<T,N>& Vector<T,N>::operator=(const Vector<T,N>& src) {
	// …
}

However, it is conventional to implement members functions of templated classes directly within the class definition. Because the compiler does not directly compile templates, a templated class cannot be compiled on its own. This creates a bit of a paradox. The compiler wants to compile each class individually, but if some code references a templated class, the compiler must go find the template implementation, generate code, and finally compile that. And the compiler's job is not to look at the code holistically—that's the linker's job. Consequently, if you implement your template members within the class definition, this code is automatically included (in your .h) in each necessary compilation unit.

If this part mostly went over your head, that's OK—we haven't talked about the compilation and linkage process. However, know that you should implement members for a template class in the definition. This has the added benefit of allowing you to drop the clunky template parameters from each reference to your class type.

template <typename T, int N>
class Vector {
public:
	Vector& operator=(const Vector& src) {
		// …
	}

	T operator*(const Vector& other) {
		// …
	}
private:
	T elements[N];
}

Instead of implementing each member like previous example, you can simply implement at the prototype.

Using Template Structures & Classes

Creating a templated type is very similar to calling a templated function: simply specify your template parameters in pointy brackets.

Vector<int,3> vec1;

This creates a vector holding 3 integers named “vec1.”

Using your newly created instance is no different than using any other object: member functions, data members, operators, and everything else works the same way.

Template Specialization

Template specialization allows you to specify entirely different logic for special template parameters. For example, you can specialize a templated function to perform different operations for integers, floats, and everything else. Specialization is only really useful in (obviously) special cases that require different handling. However, specialization is also a not insignificant part of the STL and functional programming in C++, so it's useful to know.

A template can be fully or partially specialized. A fully specialized template is the most specific case: all parameters are accounted for. A partially specialized template, on the other hand, only has one or more parameter specified.

The syntax for template specialization is a little complicated: as always, begin the declaration with the keyword "template." However, if you are fully specializing your template, leave the pointy brackets empty. If you are partially specializing, only include the arbitrary parameters. Then, declare the function/class the same as the generalized version, and add another set of pointy brackets. These brackets contain the specialized parameters. For example, if you are fully specializing a data structure for integers, you would have template<> class name<int> { ... };

Next, implement the specialized function or class. This implementation technically does not have to share any similarities with the more general type—it's its own fully fledged type. However, be aware that when using the template later in your program, you (or another programmer) may not know if they are using the specialized or generalized version. This is another dangerous property of templates. Hence, it is conventional for any specialized templates to have the same interface, or API, as the generalized version. The user should not have to know if they are using the specialized or generalized version.

Finally, as I just alluded to, using the specialized template is automatic—the specialized version will automatically be used when needed. Just remember that the specialized version is an entirely different type than the generalized.

A fully specialized function for integers:

template<typename T>
int floor(T val) {
	return std::floor(val);
};

template<>
int floor<int>(int val) {
	return val;
};

A partially specialized vector for zero elements:

template<typename T, int N>
class Vector {
public:
	// ...
private:
	T elements[N];
};

template<typename T>
class Vector<T,0> {
public:
	// ...
private:
	T element;
};

int main() {
	Vector<int,3> v1;
	Vector<int,0> v2;

	// Assume these are public
	cout << v1.elements[0] << endl;
	// This line is totally valid—Vector<int,0> is an entirely different type and has a different data member
	cout << v2.element << endl;
};

Templated Nodes

As I’ve mentioned several times, templates are often used to create generic data structures. A quick note here: simply templating a class is often enough to make it generic. However, suppose you want to template a linked list-based structure. In this case, you would need to not only template the node type to hold arbitrary data, but also the list type to accommodate the template nodes. See the example program for an example.

Programming Exercises

Template last week’s exercise, the linked-list based list data structure. Make sure it will work with any data type, including itself.
Create your own full-featured, templated, arbitrarily sized vector class (the mathematical vector, not the STL vector). Try implementing the following members:

Default constructor
Parametrized constructor
Copy constructor
Destructor
operator=
operator+
operator-
operator+=
operator-=

length()
normal() – same direction, length = 1
round() – round to integer vector
rotate()
angle()
operator==
operator!=
templated operator* - multiply by constant
operator * - dot product

Example Program

Download Run this Code

// If you are not sure what some lines of code do, try looking back at
// previous example programs, notes, or ask a question.

#include <iostream>

using namespace std;

// See last example for comments on the list data structure
// Comments here are only for template features


// Our forward declaration has to be template
template <typename T> class LinkedList;

// Here our node is templated so nodes can hold an arbitrary data type
template <typename T> 
class node {
	// Our value parameter is of our template parameter "T"
	// This is also implemented here, in the class definition
	node(T v, node* n = NULL) {
		value = v;
		next = n;
	}
	// Don't need this to do anything
 	~node() {}

	// The value this node holds should, of course, be of generic type "T"
	T value;
	node* next;

	// Note that we must specify that LinkedList is templated
	friend class LinkedList<T>;

	// We can't implement a friend here, as it's not a member
	// We also have to specify what kind of list we're outputting, so we do LinkedList<type>.
	// Hence, the friend must also be templated. Note that the template declaration goes before
	// "friend," and that we must use U as our argument, as T is already defined.
	template <typename U> 
	friend ostream& operator<<(ostream& out, const LinkedList<U>& src);
};

// Here our actual list is templated to accommodate the templated nodes and arbitrary data input/output
template <typename T> 
class LinkedList {
public:
	LinkedList() {
		head = NULL;
	}
	// We need a copy constructor for later
	LinkedList(const LinkedList& src) {
		head = NULL;
		node<T>* temp = src.head;
		while(temp) {
			addValue(temp->value);
			temp = temp->next;
		}
	}
	// We need an assignment operator for later
	LinkedList& operator=(const LinkedList& src) {
		while(head) {
			node<T>* temp = head->next;
			delete head;
			head = temp;
		}
		node<T>* temp = src.head;
		while(temp) {
			addValue(temp->value);
			temp = temp->next;
		}
	}
	~LinkedList() {
		while(head) {
			node<T>* temp = head->next;
			delete head;
			head = temp;
		}
	}

	// Here we add a value of generic type T
	void addValue(T value) {
		head = new node<T>(value,head);
	}
	// Here we remove a value, returning generic type T
	T removeValue() {
		T result;
		if(head) {
			result = head->value;
			node<T>* temp = head->next;
			delete head;
			head = temp;
		}
		return result;
	}

	// Again, we can't implement a friend here, and we must specify that the LinkedList uses type U
	template <typename U> 
	friend ostream& operator<<(ostream& out, const LinkedList<U>& src);

private:
	// Our node must use generic type T
	node<T>* head;
};

// Here we actually implement our friend, note the use of another template
template <typename T>
ostream& operator<<(ostream& out, const LinkedList<T>& src) {
	node<T>* temp = src.head;
	while(temp) {
		// Output brackets for list-of-list clarity
		// Later, we create a list of lists, so in that case "out << temp->value"
		// will actually recursively call this function 
		out << "[" << temp->value << "]";
		if(temp->next) {
			out << " -> ";
		}

		temp = temp->next;
	}

	return out;
}

int main() {
	// Declare list using integers
	LinkedList<int> intList;
	// Declare list using floats
	LinkedList<float> floatList;
	
	// Prior to c++11, you have to leave a space between two '>' brackets in a
	// nested template, otherwise the compiler thinks you're using the ">>" operator 
	
	// Declare list using lists that use integers
	LinkedList<LinkedList<int> > listList;

	// Output lists
	cout << "Int list: " << intList << endl;
	cout << "Float list: " << floatList << endl;
	cout << "List list: " << listList << endl;

	// Add values to the int list
	for(int index = 0; index < 10; index++) {
		intList.addValue(index);
	}

	// Add values to the float list
	for(float index = 0.5; index < 10; index++) {
		floatList.addValue(index);
	}

	// Add values to list list
	for(int index = 0; index < 10; index++) {
		LinkedList<int> value;
		for(int index = 0; index < 10; index++) {
			value.addValue(index);
		}
		listList.addValue(value);
	}

	// Output lists
	cout << "Int list: " << intList << endl;
	cout << "Float list: " << floatList << endl;
	cout << "List list: " << listList << endl;

	system("pause");
	return 0;	
}