I am struggling to understand templates definition. My basic understanding is that templates definitions allows to make data type either for return or arguments as generic. That is a template argument is a datatype for which compiler instantiates and link at compile time,

But I am not able to understand complex definitions as like below:

#include <iostream>
#include <type_traits>

template <unsigned n>
struct factorial : std::integral_constant<int,n * factorial<n-1>::value> {};

template <>
struct factorial<0> : std::integral_constant<int,1> {};

int main() {
  std::cout << factorial<5>::value;  // constexpr (no calculations on runtime)
  return 0;
}

where

template <class T, T v>
struct integral_constant {
  static constexpr T value = v;
  typedef T value_type;
  typedef integral_constant<T,v> type;
  constexpr operator T() { return v; }
};

Output:

120

Its really difficult to visualize how templates gets instatntiated:

template <int,5 * factorial<5-1>::value>
struct integral_constant {
  static constexpr int value = 5 * factorial<5-1>::value;
  typedef int value_type;
  typedef integral_constant<5 * factorial<5-1>::value> type;
  constexpr operator int() { return 5 * factorial<5-1>::value; }
};

I am struggling to understand templates definition. My basic understanding is that templates definitions allows to make data type either for return or arguments as generic. That is a template argument is a datatype for which compiler instantiates and link at compile time,

But I am not able to understand complex definitions as like below:

#include <iostream>
#include <type_traits>

template <unsigned n>
struct factorial : std::integral_constant<int,n * factorial<n-1>::value> {};

template <>
struct factorial<0> : std::integral_constant<int,1> {};

int main() {
  std::cout << factorial<5>::value;  // constexpr (no calculations on runtime)
  return 0;
}

where

template <class T, T v>
struct integral_constant {
  static constexpr T value = v;
  typedef T value_type;
  typedef integral_constant<T,v> type;
  constexpr operator T() { return v; }
};

Output:

120

Its really difficult to visualize how templates gets instatntiated:

template <int,5 * factorial<5-1>::value>
struct integral_constant {
  static constexpr int value = 5 * factorial<5-1>::value;
  typedef int value_type;
  typedef integral_constant<5 * factorial<5-1>::value> type;
  constexpr operator int() { return 5 * factorial<5-1>::value; }
};

• c++

• Well the first thing to understand here is that there are no data types involved. The template parameter unsigned n is an integer value, not a data type. – john Commented Mar 30 at 5:22
• factorial<n-1>::value is just like a function call (e.g. factorial(n-1)), except that the 'function call' is being done by the compiler when your code is being compiled, not at runtime as with normal functions. – john Commented Mar 30 at 5:24

1 Answer 1

The one use of templates you have not mentioned but are probably familiar with is storing generic data, like std::vector<int>. Here, we are using integral_constant which kinda stores data as a constant static member.

We then define a factorial struct recursively, where a base case of 0 is "equal" to 1, while any other is the number N multiplied by factorial<N - 1>. This means factorial<5> expands to:

struct factorial<5> : factorial<5 * factorial<4>::value> {};
struct factorial<4> : factorial<4 * factorial<3>::value> {};
struct factorial<3> : factorial<3 * factorial<2>::value> {};
struct factorial<2> : factorial<2 * factorial<1>::value> {};
struct factorial<1> : factorial<1 * factorial<0>::value> {};
struct factorial<0> : std::integral_constant<int, 1>;

So following the inheritance and multiplication, means that factorial<5> : std::integral_constant<int, 5 * 4 * 3 * 2 * 1 * 1> and factorial<5>::value = 5 * 4 * 3 * 2 * 1 * 1 = 120.

Despite weird syntax, this is not unlike the "normal" definition of factorial as a recursive function:

int factorial(int n) {
    if (n == 0) {
        return 1;
    else {
        return n * factorial(n - 1);
    }
}

Though in both cases, I would advise using an unsigned type or adding a negative check to avoid the recursive calls exploding for n < 0.

As to why you might want to compute values that way, it is because it is guaranteed to happen at compile time, allowing for stuff like std::array<int, factorial<5>::value>. It is less the case in modern C++, where constexpr functions are allowed to do more, so marking int factorial(int n) as constexpr should allow std::array<int, factorial(5)> to compile in C++17 and newer.