Templates were originally meant to help us with making generic algorithms and containers. But soon people realized that the language feature is much more powerful. It's actually a separate programming language inside C++.
As a demonstration, let us consider this very simple factorial function.
int fact(int n) {
if (n == 0)
return 1;
else
return n * fact(n - 1);
}It can be rewritten to calculate the factorial at compile time, with using class template instantiations. We use the following substitutions:
- Functions will become classes.
- Function arguments will become template arguments.
- The return value will be stored in the static variable named
valueby convention, eg. fact(6) will be Fact<6>::value. - We can do loops and recursion by instantiating another class.
- We can do conditionals with specializations.
The template version, the so-called metafunction will be:
template <int N>
class Fact {
public:
static constexpr int value = N * Fact<N - 1>::value;
};
template <>
class Fact<0> {
public:
static constexpr int value = 1;
};
int main() {
std::cout << Fact<6>::value;
}constexpr means "constant expression": constant in a sense that it is calculated
at compile time.
Nowadays noone ever writes template metaprograms like this, maybe only as
an exercise. Since C++11, we also have constexpr functions, which are even more
powerful since C++14. A constexpr function's value is calculated at compile time,
given that the arguments are known at compile time. So you can write something
like this:
constexpr int fact(int n) {
if (n == 0)
return 1;
else
return n * fact(n - 1);
}
int myarr[fact(6)]; // ok, since it can be calculated at compile time
int main() {
std::cout << fact(6) << std::endl; // calculated at compile time
int i;
std::cin >> i;
std::cout << fact(i) << std::endl; // calculated at run time
}Still these exercises help you with understanding the advanced topics of C++ templates.
We'll discuss a metafunction which can tell whether a type is a class or it is a built-in type, eg.
int main() {
std::cout << IsClass<std::ostream>::value << std::endl; // true, is a class
std::cout << IsClass<double>::value << std::endl; // false, not a class
}This will also explain some details and tricks about C++ templates which are frequently used with template metaprograms. The implementation of the metafunction is this:
template <typename T>
class IsClass {
private:
template <typename U>
static constexpr bool check(int U::* ptr) {
return true;
}
template <typename U>
static constexpr bool check(...) {
return false;
}
public:
static constexpr bool value = check<T>(0);
};By following the specializations generated by the compiler we can figure out
how it works. Let's try IsClass<std::ostream> first! With T = std::ostream,
the static variable value is defined as:
static constexpr bool value = check<std::ostream>(0);To get its value, the check function template is to be called. However,
check is actually an overload, there are two functions with the same name.
So firstly, the compiler will check the header of the functions (the body
is not important yet). The template argument is explicitly specified, so
U = std::ostream is substituted in both headers:
template <>
static constexpr bool check<std::ostream>(int std::ostream::* ptr);
template <>
static constexpr bool check<std::ostream>(...);Now the compiler has to select one of the two via the usual function
overload resolution mechanism. The argument is 0. The value zero
can be treated as a null pointer, so the first version could be called
(an attribute member pointer can be null as well). The second version
could also be called: ... here is the "variadic function of unknown types"
language feature inherited from C (like in printf).
Which one is better? In this case, the compiler will prefer the better
overload, with less conversions, which is in this case the first one.
A member pointer is more concretized than an unknown type. It will return
true, and yes: std::ostream is a class.
What about IsClass<double>? The static variable will be like this:
static constexpr bool value = check<double>(0);So we'll have to follow the overload resolutions for the check function again.
Firstly, the headers:
template <>
static constexpr bool check<std::ostream>(int double::* ptr);
template <>
static constexpr bool check<std::ostream>(...);A strange thing happens: we have a syntax error in the first function's header.
There is no such thing as an int double::*, doubles do not have attributes,
so they can't have member pointers. However, the compilation is not stopped;
the compiler will throw away the first function, in the hope that some other
overload will work. In this is actually the case, as the other overload can
be called. And it will return false, which is fine, because double is not
a class.
The most important takeaway here is that C++ has this rule regarding templates: whenever a template argument substitution creates a syntax error, just ignore that function or class specialization, and continue the compilation. The above example shows why this is so: other overloads or specializations might still work. This rule is called SFINAE, Substitution Failure Is Not An Error, and we can exploit it to control how the compiler uses our template functions and classes.
With the use (actually the abuse) of the SFINAE rule, we can actually control how the compiler instantiates templates. Imagine that we have a function with an integer argument of some size. It can be an int, a short, maybe a long long. It is important for that function that the argument is actually signed; unsigned int or unsigned short won't do.
This is not a usual specialization of the function or the set of overloads. We'd like to allow instantiation of the function based on some property of the type, and not simply for a list of types or a single type. So we'll have to do the following:
- Create a metafunction, which takes the type as an argument, and tells whether the type satisfies some criterion. (Is it a signed integer or not?)
- Use SFINAE to disable instantiation of the function, if the function will not work.
The metafunction for checking signedness looks like this:
template <typename T>
class IsSigned {
public:
static constexpr bool value = T(~0) < T(0);
};
int main() {
std::cout << IsSigned<int>::value << std::endl;
std::cout << IsSigned<short>::value << std::endl;
std::cout << IsSigned<unsigned int>::value << std::endl;
std::cout << IsSigned<unsigned short>::value << std::endl;
}It is based on the fact that in two's complement notation, a number with all bits as 1's (like 111111111) is the representation of –1. Which is actually smaller than zero. For unsigned values, 11111111... is a very large number, eg. for short it is 65535, definitely greater than zero. We could have used std::is_signed<T> from #include <type_traits> as well.
SFINAE is usually based on a class like this:
// empty class, will be instantiated for EnableIf<false>
template <bool ENABLE>
class EnableIf {
};
// instantiated for EnableIf<true>
template <>
class EnableIf<true> {
public:
using type = void;
};So EnableIf<false>::type is a nonexistent member (syntax error), and EnableIf<true>::type is equivalent to void. The bool template argument tells if the class should generate a syntax error or not. This is the same as std::enable_if.
The solution is:
template <typename T, typename ENABLE = typename EnableIf<IsSigned<T>::value>::type>
void func(T number) {
// ...
}
int main() {
int a = 0;
func(a); // ok
short b = 0;
func(b); // ok
// unsigned c;
// func(c); // would be compile error
}The idea is that we deliberately put the piece of code into the header of the function (in this case: the template argument list), which creates the compile error. If T is a signed number, typename ENABLE = void will be applied, the compiler can use this default template argument after deducing T. However if it is unsigned, the EnableIf part is a syntax error, therefore the function cannot be compiled.
The next example shows a more real life example.
This section will introduce void_t, that is also part of the standard since C++17. the definition is this:
template <typename ... T>
using void_t = void;This looks like the most unusable thing every. You can instantiate the template with any type,
like void_t<int> or void_t<double, char>, but every time you will get an alias for void.
They one implements a metafunction with void_t is something like this:
template <typename ... T>
using void_t = void;
template <typename T, typename SFINAE = void>
class IsRandomAccessIterator {
public:
static constexpr bool value = false;
};
template <typename T>
class IsRandomAccessIterator<T, void_t<decltype(T() + 0)>> {
public:
static constexpr bool value = true;
};
int main() {
std::cout << IsRandomAccessIterator<std::list<int>::iterator>::value << std::endl;
std::cout << IsRandomAccessIterator<std::vector<int>::iterator>::value << std::endl;
}The SFINAE argument name gives a hint on what is happening. To understand the internals, it's
nice to follow the instantiations. Firstly for std::list<int>::iterator, the following
class declarations and arguments are checked by the compiler:
template <>
class IsRandomAccessIterator<std::list<int>::iterator, void> { /* ... */ };
template <>
class IsRandomAccessIterator<std::list<int>::iterator, void_t<decltype(std::list<int>::iterator() + 0)>> { /* ... */ };The base template can have the arguments T = std::list<int>::iterator (as specified)
and SFINAE = void (as default). The specialization will have T = std::list<int>::iterator (as specified),
and the void_t<...> part is yet to be evaluated. However, the evaluation will fail, as the list
iterator has no iterator + int operation. Therefore the specialization is discarded, and the base
template is used: the value is false, which is the right answer.
Secondly, for std::vector<int>::iterator:
template <>
class IsRandomAccessIterator<std::vector<int>::iterator, void> { /* ... */ };
template <>
class IsRandomAccessIterator<std::vector<int>::iterator, void_t<decltype(std::vector<int>::iterator() + 0)>> { /* ... */ };The base version is the same, and evaluation is also required for the specialization. The compiler
will look up if it can find the operator that could be used for the std::vector<int>::iterator() + 0
expression. This will be successful, as this iterator has the desired iterator + int operation.
The decltype keyword will cause the compiler to figure out what the type of this expression is.
The type is std::vector<int>::iterator (iterator + integer is an iterator itself), so the actual
meaning of this part is void_t<std::vector<int>::iterator>, which is equivalent to void. So the
final form of the base template and the specialization is:
template <>
class IsRandomAccessIterator<std::vector<int>::iterator, void> { /* ... */ };
template <>
class IsRandomAccessIterator<std::vector<int>::iterator, void> { /* ... */ };A strange thing has happened: the template arguments of the base template and its user-defined specialization are the same. So the compiler cannot make a choice based on just the arguments. However, specializations are always preferred to base templates, and that means that in this case the specialization will be selected by the compiler, and the base template will be discarded. And the specialization is
template <>
class IsRandomAccessIterator<std::vector<int>::iterator, void> {
public:
static constexpr bool value = true;
};Which is actually the correct answer: the vector iterator is definitely a random access iterator.
Remark 1. The sole purpose of using the decltype keyword here is to have a context in which
the desired expressions can be specified. The expression ITER() + 0 won't be evaluated (the function
won't be called), but the compiler will do the overload resolution to figure out the resulting type.
The result of that overload resolution is not important either; it is used as a template argument
for void_t, but whatever the argument is, void_t is always an alias for void. But to figure
this out, the compiler had to do the overload resolution, so it had to check whether the expression
can be evaluated.
Remark 2. Any number of expressions can be checked by a void_t<>, that's why it is defined as a
variadic template. Just use void_t<decltype(expr1), decltype(expr2), ...>.
Remark 3. The operator+= of the iterator in advance(), but the metafunction checks for
operator+. The code assumes that whenever operator+ exists, operator+= will be implemented
as well - which is expected. One could also write something like decltype(*(T*)nullptr += 0)
to check for the availability of operator+=. This looks like a null pointer dereference, but it
is not: remember that the expression in decltype is not evaluated.
The IsRandomAccessIterator function is then used with std::enable_if as usual. That will
be another SFINAE. For any iterator, one of the functions will be called, because either
IsRandomAccessIterator or !IsRandomAccessIterator will be true.
#include <iostream>
#include <vector>
#include <list>
template <typename T, typename SFINAE = void>
class IsRandomAccessIterator {
public:
static constexpr bool value = false;
};
template <typename T>
class IsRandomAccessIterator<T, void_t<decltype(T() + 0)>> {
public:
static constexpr bool value = true;
};
template <typename ITER>
void advance(ITER & it, int n, typename std::enable_if<IsRandomAccessIterator<ITER>::value>::type * = nullptr) {
std::cout << "O(1) advance with +=" << std::endl;
it += n;
}
template <typename ITER>
void advance(ITER & it, int n, typename std::enable_if<!IsRandomAccessIterator<ITER>::value>::type * = nullptr) {
std::cout << "O(n) advance with for(...) ++" << std::endl;
for (int i = 0; i < n; ++i)
it++;
}
int main() {
std::vector<int> v = { 1, 2, 3, 4, 5 };
auto v_it = v.begin();
advance(v_it, 3);
std::list<int> l = { 1, 2, 3, 4, 5 };
auto l_it = l.begin();
advance(l_it, 3);
}