For the longest time, I felt shaky about using templates in my code. I don’t mean the Standard Template Library. I mean code with
instead of data types.
Additionally, C++11 introduced variadic templates, so I decided it was time to take the time and finally solidify my understanding of templates. This post is an effort to test whether I understand it well enough to explain it to others.
What?
Templates allow programmers to use a series of instructions to manipulate types. This is similar to how programming languages use a series of instructions to manipulate data. One of the most simple (and commonly used) instructions is to copy a type. For example, in the standard template library std::vector class, the type ‘int’ specified in, for example, std::vector, is copied into the implementation of the std::vector class. However, templates are much more powerful than this, and they can perform more complex operations on types as well. In fact, the set of operations allowed on types using C++11 templates is Turing complete. In this post, we will look at a more complex example that uses templates to build a list of types, and iterate over it at compile time. But before that, let’s talk about the basics of templates. Templates can be categorized as:
function templates
These use a placeholder type called template type parameter for some or all of it’s parameters. This is essentially a family of functions supporting various data types for these parameters. When this function is used with a specific type, the compiler uses this stencil function and replaces the placeholder type with the actual type that the function call specified and calls the function template instance for that type.
class templates
These are basically a family of classes. The compiler uses the appropriate class instance depending on the type it is instantiated with. The classic example is the containers in the Standard Template Library eg: std::vector vs. std::vector vs. std::vector
Why?
The intent of using templates is to decouple the concern of code from data. i.e algorithms can be developed independent of the datatypes they manipulate. Templates enable classes and functions to operate on different data types without having to replicate code for each type. A simple example is a function [getMax] that returns the maximum of two numbers. These numbers could have different precision, be integers, doubles or floats. Without templates, we’d have to replicate the code for getMax for each of these types.
When?
Templates are used whenever there is a piece of code that manipulates various kinds of datatypes. And the operations in this code do not depend on the datatypes.
How?
I’m going to try a different format to explain how. Let’s go over a code example to understand the how.
Here is the problem statement for the code example:
Create a list of type new_type_list that can hold a list of types. Provide the following functions
– append_type that adds a given data type to the list
– print_types that traverses this list and prints the data type of each entry in the list
Let’s assume that new_type_list is a linked list for simplicity.
Here is how the calling code looks:
typedef typename new_type_list::type empty_list;
typedef typename append_type<empty_list, int>::type temp1;
typedef typename append_type<temp1, float>::type temp2;
typedef typename append_type<temp2, float>::type temp3;
typedef typename append_type<temp3, float>::type temp4;
typedef typename append_type<temp4, char>::type complete_list;
print_types<complete_list>()();
return 0;
}
Let’s start by defining the new_type_list. From its usage in the calling function, we know that new_type_list contains information about the type and the next type (which can be Null when the current entry is the last entry in the list). So we define node as payload type and next node type:
class TypeList {
public:
typedef Payload payload_type;
typedef Next next_type;
};
Our new_type_list now contains a type made up of such a TypeList:
[cc lang="cpp" tab_size="4" lines="40"]
class new_type_list {
public:
typedef TypeList<NullType, NullType> type;
};
Now let’s look at the append_type function. This function can be called to append a node to
- a list of nodes or
- a node or
- nothing (first node of a linked list)
Looking at this more closely, it is obvious that each of these cases can be composed of the other (from simplest to the most complex).
The simplest case is for the first node appended to nothing (null). For this case, the TypeList we are attaching to, is nothing (referred to as NullType here onwards). The Value we start with (first node) is the first entry in our list.
[cc lang="cpp" tab_size="4" lines="40"]
template<typename Value>
class append_type<TypeList<NullType, NullType>, Value> {
public:
typedef TypeList<Value, NullType> type;
};
To append a node to a node, we use the target Node (we are attaching to) with PayLoad and next_type NullType (since it was the last node until now and hence pointed to NullType) and the Value of our new node.
class append_type<TypeList<Payload, NullType>, Value> {
public:
typedef TypeList<Payload, TypeList<Value, NullType>> type;
};
Next one is the most general call. When a call to append_type is made, the compiler matches it to the most specific function. The above two declarations of append_type are more specific. The following function declaration is the least specific. The compiler matches to this call when they don’t match to either of the above two declarations.
class append_type {
// value not NullType static_assert();
public:
typedef TypeList<typename List::payload_type, typename append_type<typename List::next_type, Value>::type> type;
};
Now let’s write the print_types function. It takes a new_type_list and prints the contents. For each entry in the list, it has to print the Payload type and the following Next type. We can write it as:
class print_types {
public:
void operator()() const {
typedef typename get_first_type<T>::type first;
typedef typename get_second_type<T>::type second;
print_types<first>()();
print_types<second>()();
}
};
We have helper functions to get the first (Payload) and second (Next) types:
class get_first_type {
public:
typedef typename T::payload_type type;
};
template<typename T>
class get_second_type {
public:
typedef typename T::next_type type;
};
Now we define what to do in the print_types functions for each of the following types int, float, char and NullType (more types can be easily added if required).
class print_types<int> {
public:
void operator()() const {
std::cout << "int ";
}
};
template<>
class print_types<float> {
public:
void operator()() const {
std::cout << "float ";
}
};
template<>
class print_types<char> {
public:
void operator()() const {
std::cout << "char\n";
}
};
template<>
class print_types<NullType> {
public:
void operator()() const {
//intentionally blank
}
};
To summarize, we talked about what templates are, why they’re useful. We saw a detailed example where we created a list that held types, appended new types to the list and printed all the types. One application of the example we saw could be to generate code for various types. Imagine a matrix operation that evaluates dot product of two matrices, each matrix could be of different precisions. We could generate this dot product for each combination by iterating over a list of type (from our example).
