This lab session is entirely dedicated to the subject of C++ function templates. It's no exaggeration to say that templates are a very advanced topic. However, the introduction of templates to C++ in 1989 was a huge step towards the development of generic containers and algorithms in C++. A couple of examples and exercises should get you started.
Using templates allows you to reuse source code: one piece of code can be reused in multiple formats. More specifically, the C++ template mechanism allows you to use a type as a parameter for a definition of a function or a class; these are the so-called templates arguments. This results in so-called class templates and function templates. Keep in mind: the template mechanism of C++ happens at compile time in contradiction to the run-time based polymorphism OOP with late binding. In this session, we'll start with function templates.
Function templates are a key feature in C++ for writing generic functions that can be called with arguments of different types to perform functionality that's analogous for these different types. A good example is sorting a sequence; it's not important what's being sorted exactly. The only thing that's necessary is an operation to compare two objects of the same type; for instance
bool T::operator<(const T &) const;
where T denotes a generic type.
In this sense, a function template acts as a pattern used by the compiler to generate (instantiate) a family of functions depending on the type of the arguments they're called with. For function templates this instantiation can happen in two ways:
Remember: A template function is an instantiation of a function template.
The basic syntax of defining a function template is:
template<typename T>
void sort(std::vector<T> & v) {
// use:
// bool T::operator<(const T &) const;
// if available, to compare and sort
// objects of type T
}
If the argument list uniquely identifies the set of template arguments the type of function arguments can be deduced from the call:
std::vector<int> v;
...
sort(v);
In other cases explicit instantiation is necesary:
sort<int>(v);
Please note that since the compiler does not know what type will be used as
T no code is generated for a function template. The code for a template
function is generated at the moment of its instantiation with a concrete type.
Template arguments can be built-in types or a user-defined types. Of course, statements and expressions in the function template body should be valid and defined on the type. For example:
template<typename T>
T min(const T & a, const T & b) {
if (a < b)
return a;
else
return b;
}
Call it with int and Foo:
min(4,5); // OK
Foo foo1; // Foo is an user-defined empty class, with no member variables nor functions
Foo foo2; // Foo is an user-defined empty class, with no member variables nor functions
min(foo1, foo2); // COMPILE ERROR
Trying to instantiate min with Foo min with foo1 and foo2 returns this error:
main.cpp: In instantiation of 'T min(const T&, const T&) [with T = Foo]':
main.cpp:35:51: required from here
main.cpp:25:11: error: no match for 'operator<' (operand types are 'const Foo' and 'const Foo')
if (a < b)
Foo does not have an overload definition of < which prohibits the compiler from instantiating the min for the Foo template argument.
Sometimes you see the keyword class being used instead of typename.
When naming template parameters, there are equivalent.
typename is however also possible in another context related to templates.
Read about it here.
You can see that no code gets generated for a template unless it's instantiated for a specific type with the following little experiment:
print.h:
#ifndef PRINT_H
#define PRINT_H
template<typename T>
void print(const T & x);
#endif /* PRINT_H */
print.cpp:
#include <iostream>
#include "print.h"
template<typename T>
void print(const T & x) {
std::cout << x << std::endl;
}
Now create a main.cpp file that includes the print.h file but does not use the print function:
#include "print.h"
int main() {
int i = 3;
return 0;
}
Compile & link the above code: g++ -o p main.cpp print.cpp and look at the symbols defined in the generated executable: nm p | c++filt:
0000000100000ee3 unsigned short __GLOBAL__sub_I_print.cpp
0000000100000e9b unsigned short __static_initialization_and_destruction_0(int, int)
U std::ios_base::Init::Init()
U std::ios_base::Init::~Init()
0000000100001030 short std::__ioinit
U ___cxa_atexit
0000000100000000 T __mh_execute_header
0000000100000e89 T _main
U dyld_stub_binder
There's no mention of print whatsoever!
You can try to call the print function in main.cpp:
#include "print.h"
int main() {
int i = 3;
print(i);
return 0;
}
Unfortunately you'll get a linker error:
Undefined symbols for architecture x86_64:
"void print<int>(int const&)", referenced from:
_main in cc1bl7rY.o
ld: symbol(s) not found for architecture x86_64
collect2: error: ld returned 1 exit status
Since print.cpp and main.cpp are compiled as two separate translation units the compiler can not generate code for the print function.
While compiling print.cpp it does not know that some other code is using print<int> and can not generate code for print with an unknown type T.
On the other hand, when compiling main.cpp the compiler supposes that a print<int> is defined somewhere else and that's why linking fails.
There are several possibilities to make things work here:
Header files should normally only contain function declarations, but function (or class) templates are an exception to this. The actual template function definition is generated when the template is instantiated, which should be done in a source file, thereby not violating the one-definition-rule. But be careful not to define anything else besides templates in the header file! By including the recipe in the header file, every translation unit that uses your template knows how instantiate it for the types they require.
Instantiate the template for the specific type that you need within the same translation unit as the template definition, i.e., in print.cpp:
#include <iostream>
#include "print.h"
// Template definition
template<typename T>
void print(const T & x) {
std::cout << x << std::endl;
}
// Explicit instantiation of print<T> for T = int
template void print<int>(const int & x);
Now print is generated:
0000000100001e8b unsigned short __GLOBAL__sub_I_print.cpp
0000000100001e42 unsigned short __static_initialization_and_destruction_0(int, int)
0000000100001e07 T void print<int>(int const&)
U std::ostream::operator<<(std::ostream& (*)(std::ostream&))
U std::ostream::operator<<(int)
U std::ios_base::Init::Init()
U std::ios_base::Init::~Init()
U std::cout
U std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)
0000000100002050 short std::__ioinit
U ___cxa_atexit
0000000100000000 T __mh_execute_header
0000000100001de5 T _main
U dyld_stub_binder
However, this is not very convenient because you need to alter the template's .cpp file to specify which template instantiations you'll need beforehand.
Note that if you explicitly instantiate the template in a translation unit where the template definition is not known, main.cpp for instance, does not work. Thus, doing this:
#include "print.h"
template void print<int>(const int & x);
int main() {
int i = 3;
print(i);
return 0;
}
results in this:
main.cpp: In instantiation of 'void print(const T&) [with T = int]':
main.cpp:3:39: required from here
main.cpp:3:39: error: explicit instantiation of 'void print(const T&) [with T = int]' but no definition available [-fpermissive]
template void print<int>(const int & x);
^
extern keywordThis feature allows you to reduce the work done by the compiler by using the already constructed instantiations of the templates. Have a look at:
Let's go back to template argument deduction.
When the template mechanism needs argument conversion to map the call to the template signature, the compiler will generate a fatal error because of the possible ambiguity.
For example, following print function with two parameters:
template<typename T>
void print(const T & x, const T & y) {
std::cout << x << " " << y << std::endl;
}
Calling the print like this:
print(3, 5.0);
results in:
main.cpp: In function 'int main()':
main.cpp:11:17: error: no matching function for call to 'print(int, double)'
print(3, 5.0);
^
main.cpp:5:27: note: candidate: template<class T> void print(const T&, const T&)
template<typename T> void print(const T & x, const T & y) {
^~~~~
main.cpp:5:27: note: template argument deduction/substitution failed:
main.cpp:11:17: note: deduced conflicting types for parameter 'const T' ('int' and 'double')
print(3, 5.0);
The compiler does not want to decide on the conversion and fails. This problem can be resolved by explicitly stating the template argument. This way the compilers knows which conversion to apply.
print<int>(3, 5.0);
When using multiple template parameters, one can also apply partial argument deduction.
Here, the arguments that should be deduced should be placed at the end of the argument list.
Having a print with two different template parameters:
template<typename U, typename T>
void print(const U & x, const T & y) {
std::cout << x << " " << y << std::endl;
}
One can call this print as follows:
print<double>(5.0, 4);
Here, U is determined by the explicit (double) initialization, while T is deduced to being an int.
If your function template needs a specific implementation for a specific type, such as for instance a std::vector<bool> uses a special implementation (read more), you can specialize the template:
print.h:
#ifndef PRINT_H
#define PRINT_H
template<typename T>
void print(const T & x);
#endif /* PRINT_H */
print.cpp:
#include <iostream>
#include "print.h"
// Generic implementation
template<typename T>
void print(const T & x) {
std::cout << x << std::endl;
}
// Specific implementation for T = char
template<>
void print<char>(const char & x) {
std::cout << x << " is a char!" << std::endl;
}
// Instantiations of print for T = int and T = char
template void print<int>(const int & x);
template void print<char>(const char & x);
This generic implementation is also called the primary template (in the case there are also specializations, otherwise it is just called a template). The specific implementation is also called an explicit specialization.
main.cpp:
#include "print.h"
// Specific implementation for T = bool
template<>
void print<bool>(const bool & x) {
std::cout << x << " is a bool!" << std::endl;
}
int main() {
int i = 3;
print(i);
char p = 'P';
print(p);
print(true);
return 0;
}
We added two explicit specializations: T = char in print.cpp, T = bool in main.cpp.
As you can see from the specialization T = bool in main.cpp, explicit specializations do not need the primary template definition: its declaration is enough (which is available in print.h).
You might wonder now: what is the practical difference between function overloading and function template specialization?
When should I define print(int) instead of specializing the print<T> template for T = int?
You're not the only one confusing the two:
Just like a function's argument list can specify default values for the arguments making them optional, a function template can specify default values for its template arguments.
This is used a lot in the context of custom comparator objects. In this example, a default comparator CustomComparatorLess is set.
If we do want to sort the vector in ascending order, we specify the CustomComparatorGreater type as template argument:
class CustomComparatorLess {
public:
bool operator() (const int& i, const int& j) { return (i < j); };
};
class CustomComparatorGreater {
public:
bool operator() (const int& i, const int& j) { return (i > j); };
};
template<typename C = CustomComparatorLess>
void customSort(std::vector<int>& v) {
C cmp;
std::sort(v.begin(), v.end(), cmp);
for (int val: v)
std::cout << val << std::endl;
};
int main() {
std::vector<int> v = {3, 6, 4, 5, 1, 6};
customSort(v);
customSort<CustomComparatorGreater>(v);
return 0;
}
Of course, it would be much nicer if we can not only apply this to vector<int>, but to all kind of vector types.
With the help of class templates (which are discussed in next session) we can make this possible.
This handy C++11 feature allows you to define something you could call "typedef templates". Suppose you'd like to define a matrix-like class as a vector of vectors, you could write
std::vector<std::vector<double>> m;
However, writing this every time you need such a type is extremely inconvenient.
To ease the pain you could create and use a typedef like this:
typedef std::vector<std::vector<double>> vv_d_t;
// Now this is much cleaner:
vv_d_t m;
Although you'd need to define such a typedef for each type of variables you want to store in the vectors (hence the d in vv_d_t, a vector of vectors of doubles).
What you'd really want is a typedef that can be instantiated for a generic type T.
Prior to C++11 that was not possible.
Now you can do:
template<typename T> using vv_t = std::vector<std::vector<T>>;
// Now you can do:
vv_t<double> a;
// and
vv_t<int> b;
Pretty neat, right? This is the reason we previously advised you to always use alias declarations instead of typedef.
The idea of implementing this pretty obvious feature has been around for quite some time already. You can skim through the original proposal if you want. For other uses of alias templates have a look here.
Go to the assignment: https://classroom.github.com/a/KZqJBIDE
Go to the assignment: https://classroom.github.com/a/WThYXrz5