Does template (meta)programming has always only one way of implementation?

Question

Studying few of the template programs and especially meta programs which deduce result at compile time into a constant, I learned that generally there is only one way to implement something. e.g.: as easy as factorial example or as complex as is_base_of

I am never able to think about perfect alternate implementation of such code which has completely different logic. Is this a true assumption ?

If this assumption is true that means, whenever we implement something using template tricks, we are always assured that, it's the best code and we don't have to worry about optimizing compilation time anymore.

[Note: I am not mentioning about general template usage which we do with class and functions. But the usage for deducing a compile time constant.]

Answer 1

The reason you tend to only see one way of doing something is because the things that people actually use template meta-programming for are usually algorithmically trivial -- they just look complicated because they get mixed up with a load of type hackery and the oddities of C++ template syntax.

But sometimes (as Steve Jessop's answer shows) there really are multiple algorithms to calculate something, and you can implement any of them with templates.

As another example, here are two ways to evaluate pow(a,b) (for small integer arguments):

Obvious:

// ----- Simple Way -----

template <int A, int B>
struct PowA {
    typedef PowA<A,B-1> next;
    enum {
       value = A * next::value,
       recursion_count = 1 + next::recursion_count
    };
};
template <int A> struct PowA<A, 1> { enum { value = A, recursion_count = 0 }; };
template <int A> struct PowA<A, 0> { enum { value = 1, recursion_count = 0 }; };

Slightly less obvious:

// ----- Less Simple Way -----

template <int A, int B, int IsOdd> struct PowHelper;

template <int A> struct PowHelper<A, 0, 0> { enum { value = 1, recursion_count = 0 }; };
template <int A> struct PowHelper<A, 1, 1> { enum { value = A, recursion_count = 0 }; };

template <int A, int B>
struct PowHelper<A, B, 1> {
    typedef PowHelper<A, B-1, 1> next;
    enum {
        value = A * next::value,
        recursion_count = 1 + next::recursion_count
    };
};
template <int A, int B>
struct PowHelper<A, B, 0> {
    typedef PowHelper<A, B/2, ((B/2)&1)> next;
    enum {
        x = next::value,
        value = x*x,
        recursion_count = 1 + next::recursion_count
    };
};

template <int A, int B>
struct PowB {
    typedef PowHelper<A,B,(B & 1)> helper;
    enum {
        value = helper::value,
        recursion_count = helper::recursion_count
    };
};

And some code to let you check it:

// ----- Test -----

#include <iostream>

int main(int argc, char* argv[]) {
#define CHECK(X,Y) \
    std::cout << ("PowA: " #X "**" #Y " = ") << \
        PowA<(X),(Y)>::value << " (recurses " << \
        PowA<(X),(Y)>::recursion_count << " times)" << std::endl; \
    std::cout << ("PowB: " #X "**" #Y " = ") << \
        PowB<(X),(Y)>::value << " (recurses " << \
        PowB<(X),(Y)>::recursion_count << " times)" << std::endl;

    CHECK(3,3)
    CHECK(2,8)
    CHECK(7,3)
    CHECK(3,18)

#undef CHECK

   return 0;
}

Answer 2

Sort of depends what you mean by "doing it differently". Here are two TMP implementations to compute a triangle number:

template<int N>
struct RecursiveTriangle {
    static const int value = RecursiveTriangle<N-1>::value + N;
};

template<>
struct RecursiveTriangle<0> {
    static const int value = 0;
};

template<int N>
struct Triangle {
    static const int value = (N*(N+1))/2;
};

These are precisely analagous to two "different" ways of computing triangle numbers imperatively - with a loop or with the same formula as Triangle. Their domain of definition differs, though - Triangle handles negative numbers, and RecursiveTriangle doesn't. Not that the result of Triangle for negative numbers makes much sense.

So, what do you mean by "different ways to do it"?

Answer 3

No, there's not only one implementation. Here's an example of two ways of doing factorial:

#include <iostream>
using namespace std;

template <int N>
struct Factorial
{
  enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0>
{
  enum { value = 1 };
};

template <int N>
class FactorialC {
public:
  static const long value = N * Factorial<N - 1>::value;
};

template <>
class FactorialC<10> {
public:
  static const long value = 3628800;
};

template <>
class FactorialC<0> {
public:
  static const long value = 0;
};

int main() {
  cout << Factorial<4>::value << endl;
  cout << Factorial<12>::value << endl;
  cout << FactorialC<4>::value << endl;
  cout << FactorialC<12>::value << endl;
}

Output:

24
479001600
24
479001600

Answer 4

Let's take the code for factorial from Wikipedia:

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

You could implement this alternatively as:

template <int N>
struct Factorial 
{
    enum { value = Factorial<N - 1>::value * N };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

Or alternatively as:

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<1> 
{
    enum { value = 1 };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

Answer 5

Generally speaking, the lack of features available in TMP and the relative simplicity of the functionality- if not the way it has to be expressed- means that there's very rarely more than one implementation that differs significantly.