C++ Template Metaprogramming

Note: with C++14 & C++17 life gets much better with constexpr. Details: computing-exp-at-compile-time and constexpr2

factorial(number) = 1 * 2 * 3 * … * (n-1) * n

1
2
3
4
5
6
7
8
9
static int factorial_imperative(int value)
{
    int factorial = 1;
    for(auto idx = value; idx > 1; --idx )
    {
        factorial *= idx;
    }
    return factorial;
}
  1. Very compact code, which is good as well as bad for it can be difficult to understand at times
  2. Understanding when to stop, specifying termination condition correctly

So here is the recursive and immutable version for evaluating factorial:

1
2
3
4
5
6
static int factorial_recursive(int value)
{
    return
            value <= 1 ? 1 :
            (value * factorial_recursive(value-1));
}
  1. we are not mutating any variable, even though we generate new values due to recursion but we are not mutating
  2. well defined termination condition, at line 4: value <= 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//  in metaprogram every thing is a template-class/struct
template<int Num>
struct factorial_c
{
enum
    {
        value = Num * factorial_c<Num-1>::value
    };
};

//  terminating conditions
//
//  factorial of 1 is 1
//
template<>
struct factorial_c<1>
{
    enum
    {
        value = 1
    };
};


//  factorial of 0 is 1
//
template<>
struct factorial_c<0>
{
    enum
    {
        value = 1
    };
};


int main()
{
    auto factorial_5 = factorial_c<5>::value;
    std::cout << "factorial of 5 is "
              << factorial_5 << std::endl;
    return 0;
}

Here is how the compiler evaluates the template recusions:

1
2
3
4
5
6
7
factorial_5 = factorial_c<5>::value;
factorial_5 = 5 * factorial_c<4>::value;
factorial_5 = 5 * 4 * factorial_c<3>::value;
factorial_5 = 5 * 4 * 3 * factorial_c<2>::value;
factorial_5 = 5 * 4 * 3 * 2 * factorial_c<1>::value;
factorial_5 = 5 * 4 * 3 * 2 * 1;
factorial_5 = 120;

Recursive & Immutable runtime code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
static int gcd_recursive(int a, int b)
{
    if( a == b )
    {
        return a;
    }
    //
    auto max = a > b ? a : b;
    auto min = a < b ? a : b;
    //
    //
    if( min == 0 )
    {
        return max;
    }
    return gcd_recursive(min, max % min);
}

TMP:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//  equivalent to max function
//
template<int One, int Two>
struct  max_c
{
    enum
    {
        value = One > Two ? One : Two
    };
};
//
//
//  equivalent to min function
//
template<int One, int Two>
struct min_c
{
    enum
    {
        value = One < Two ? One : Two
    };
};
//
//
//  TMP version of gcd
//
template<int One, int Two>
struct gcd_c
{
    enum
    {
        //  equivalent to:
        //  value = gcd(min, max % min)
        //
        value = gcd_c<  min_c<One, Two>::value,
                        max_c<One, Two>::value %
                        min_c<One,Two>::value>::value
    };
};
//
//
//  template specialization for
//  Min being 0, this is our
//  termination condition for recursion
//
template<int Max>
struct gcd_c<Max, 0>
{
    enum
    {
        value = Max
    };
};

lcm (least common multiple)

Recursive & Immutable runtime code:

1
2
3
4
static int lcm_r(int one, int two)
{
    return one * two / gcd_recursive(one, two);
}

TMP:

1
2
3
4
5
6
7
8
template<int One, int Two>
struct lcm_c
{
    enum
    {
        value = One * Two / gcd_c<One, Two>::value
    };
};

Parting Thoughts

C++