Unrolling loops using templates in C++ with partial specialization

Question

I'm trying to use templates to unroll a loop in C++ as follows.

#include <iostream>

template< class T, T i >
struct printDown {
    static void run(void) {
        std::cout << i << "\n";
        printDown< T, i - 1 >::run();
    }
};

template< class T >
struct printDown< T, 0 > {
    static void run(void) {
        std::cout << 0 << "\n";
    }
};

int main(void) {
    printDown< int, 10 >::run();
    return 0;
}

When I compile w/ g++ 3.4.4 in Cygwin, I get the following error.

tmp.cpp:12: error: type T' of template argument0' depends on template parameter(s)

What am I doing wrong? Do I need to somehow annotate the 0 to say that it's of type T?

Thanks in advance.

Answer 1

Have you tried int i instead of T i?

Answer 2

Why this happens? From 14.5.5/8,

— The type of a template parameter corresponding to a specialized non-type argument shall not be dependent on a parameter of the specialization. [ Example:

template <class T, T t> struct C {};
template <class T> struct C<T, 1>; // error
template< int X, int (*array_ptr)[X] > class A {};
int array[5];
template< int X > class A<X,&array> { }; // error

—end example ]

Therefore when you apply partial specialization, the type of 0 is T (dependent on a parameter of the specialization). There are two choices, one is to make it none dependent, e.g., change T i to int i, and second is to apply explicit specialization rather than partial specialization.

Both solutions have been given out by others, so I'm not gonna to repost them here. At least you know the reason. It's defined by standard.

Answer 3

As pointed out by phooji your implementation suffers from a small issue: it quickly generates a long list of calls, which will make compilers choke quickly.

You could work around this by implementing a slightly more complicated version, using binary decomposition. I'll make it generic on a functor too, cause I am lazy.

// Signature
template <Functor F, unsigned N>
struct UnrolledLoop;

We need a helper template, which keeps an offset of the parameter to pass

template <Functor F, unsigned N, unsigned OffSet>
struct UnrolledImpl;

template <Functor F, unsigned OffSet>
struct UnrolledImpl<F, 0, OffSet>
{
  static F run(F f) { return f; }
};

template <Functor F, unsigned OffSet>
struct UnrolledImpl<F, 1, OffSet>
{
  static F run(F f) { f(OffSet); return f; }
};

template <Functor F, unsigned N, unsigned OffSet>
struct UnrolledImpl
{
  static F run(F f) {
    F f2 = UnrolledImpl<F, N/2, OffSet>::run(f);
    return UnrolledImpl<F, N - N/2, OffSet + N/2>::run(f2);
  }
};

And you can implement UnrolledLoop simply:

template <Functor F, unsigned N>
struct UnrolledLoop
{
  static F run(F f) { return UnrolledImpl<F, N, 0>::run(f); }
}

Note that you could provide specialization for more values of N (3, 4 for example) to be nicer on the compiler.