Variadic templates - incomplete type

Question

Having this code:

template<class ...Args>
struct Are_Same
{
    enum {value = Are_Same<Args...>::value};
};

template<class A,class... C>
struct Are_Same<A,C...>
{
    enum {value = Are_Same<A,C...>::value};//HERE is THE ERROREOUS LINE
};

template<class A,class B>
struct Are_Same<A,B>
{
    enum {value = std::is_same<A,B>::value};
};  

I'm getting error from gcc 4.6.1:

error: incomplete type 'Are_Same' used in nested name specifier.

I thought that by doing Are_Same<A,C...>::value I will invoke recursive call which at the end will simply expand to Are_Same<A,B>. Obviously it's not the case. Anyone knows where am I making mistake?

Answer 1

I think that the definitions of the templates are wrong, in both cases you are triggering exact recursion. I would have expected the compiler to die with some stackoverflow inside the compiler but a different error is produced...

An implementation of the are_same variadic template could be:

template <class... Args>                    // base (optional to declare the template)
struct are_same;

template <class A, class B, class... Args>  // recursion
struct are_same<A,B,Args...> {
    static const bool value = is_same<A,B>::value && are_same<A,Args...>::value;
};

template <class A, class B>                 // stop condition
struct are_same<A,B> {
    static const bool value = is_same<A,B>::value;
};

Note that in the recursion step, one argument is dropped from the list of arguments, so that the new problem to resolve is a reduced version of the original. This type of template metaprogramming is quite related to recursion, and the same rules apply, to be able to use recursion you need to ensure that each recursive step gets you closer to a solution. In this particular case, given a list of N potentially same types, each step reduces the problem to finding whether N-1 types are the same.

You can use alternatively, as stop condition (replacing the former one) a degenerate version of the are_same problem:

template <class A> 
struct are_same<A> {
   static const bool value = true;
};

Which is degenerate in the sense that it does not really make sense asking whether a single type *are_same*, but for different metaprogramming tasks it could be appropriate.

A different potentially more efficient algorithm (I am not sure whether the compiler will avoid the instantiation of the template in the recursion step above) that does not depend on is_same could be:

template <class... Args>
struct are_same;

template <class A, class... Args>
struct are_same<A,A,Args...> {              // recursion
    static const bool value = are_same<A,Args...>::value;
};

template <class A, class B, class... Args>
struct are_same<A,B,Args...> {              // cut, A and B are not the same
    static const bool value = false;
};

template <class A>
struct are_same<A> {                        // end of recursion
    static const bool value = true;
};

In this case, the compiler will prefer the recursion to the cut steps whenever the two types are the same, so we need not check is_same internally. At the same time, if the compiler goes into the cut step, we don't need to process the rest of the type list, as we already know the answer.