C++ Template Meta Programming: Different Behavior using Types Aliases vs Inheritance

Question

I was trying to reverse a c++14 std::index_sequence and ran into problems with my original implementation that used inheritance. I found a workaround using local type aliases, but I would like to understand why the original code does not work.

Broken Reverse Using Inheritance

This was my first attempt at reversing a std::index_sequence:

/// Helper class that appends an element onto an index_sequence.
/// Base case.
template<size_t, typename>
struct Append : std::index_sequence<> { };

template<size_t X, size_t... XS>
struct Append<X, std::index_sequence<XS...>> : std::index_sequence<XS..., X> { };

/// Reverse elements of a std::index_sequence
template<typename>
struct Reverse;

/// Base case
template<>
struct Reverse<std::index_sequence<>> : std::index_sequence<> { };

template<size_t X, size_t... XS>
struct Reverse<std::index_sequence<X, XS...>> : Append<X, Reverse<std::index_sequence<XS...>>> { };

This support function prints the contents of an std::index_sequence:

template <size_t... XS>
void print_seq(std::index_sequence<XS...>)
{
    std::cout << "size " << sizeof...(XS) << ": ";
    bool Do[] = { (std::cout << XS << " ", true)... };
    (void) Do;
    std::cout << std::endl;
}

This implementation unfortunately did not work as I expected:

print_seq(Reverse<std::make_index_sequence<10>>{});

The output shows a size of 0 with no elements:

size 0: 

Working Reverse Using Type Aliases

Then I slightly revised my original code to use type aliases instead of inherence. All the other logic should be exactly the same as the first example.

template<size_t, typename>
struct AppendUsingType {
    using type = std::index_sequence<>;
};

template<size_t X, size_t... XS>
struct AppendUsingType<X, std::index_sequence<XS...>> {
    using type = std::index_sequence<XS..., X> ;
};

template<typename>
struct ReverseUsingType;

template<>
struct ReverseUsingType<std::index_sequence<>> {
    using type = std::index_sequence<>;
};

template<size_t X, size_t... XS>
struct ReverseUsingType<std::index_sequence<X, XS...>> {
    using type = typename AppendUsingType<X, typename ReverseUsingType<std::index_sequence<XS...>>::type>::type;
};

Now when I inspect the type:

print_seq(typename ReverseUsingType<std::make_index_sequence<10>>::type{});

I see the correct output:

 size 10: 9 8 7 6 5 4 3 2 1 0 

Question

Even though I found a solution, I would really like to understand why the implementation using inheritance fails while the one using type aliases behaves as expected. I see this in both gcc and Clang, so I suspect there some reason in the language specification.

(Perhaps Related Question: typedef vs public inheritance in c++ meta-programming)

Answer 1

First, matching of partial specializations are done using template argument deduction. If the template parameters of the partial specialization can be deduced from the the arguments supplied, the partial specialization is considered a match and can be used.

For function calls, there is a special rule in the standard permitting deducing base class template parameters from a derived class if deduction would otherwise fail (§14.8.2.1 [temp.deduct.call]/p4); this rule does not apply in other situations, and in particular it doesn't apply to partial specialization matching.

Hence, the compiler cannot match Reverse<std::index_sequence<XS...>> against std::index_sequence<XS...>, the partial specialization of Append is not viable, and the primary template is used instead.

---

A possible implementation of reversal using no type aliases:

template<typename, typename=std::index_sequence<>>
struct Reverse;

template<size_t...ints>
struct Reverse<std::index_sequence<>,
               std::index_sequence<ints...>> : std::index_sequence<ints...>{};

template<size_t first, size_t...remaining, size_t...done>
struct Reverse<std::index_sequence<first, remaining...>, std::index_sequence<done...>>
    : Reverse<std::index_sequence<remaining...>, std::index_sequence<first, done...>> {};

Answer 2

Thanks T.C. for the great explanation and much more elegant reversal implementation.

Just in case anyone needs to generalize reversals to a std::integer_sequence of any type, here is a small update to the code T.C. posted that does that:

template<typename T, typename=std::integer_sequence<typename T::value_type>>
struct Reverse;

template<typename T, T... list>
struct Reverse<std::integer_sequence<T>, std::integer_sequence<T, list...>> :
    std::integer_sequence<T, list...>
{ };

template<typename T, T first, T... rest, T... done>
struct Reverse<std::integer_sequence<T, first, rest...>, std::integer_sequence<T, done...>> :
    Reverse<std::integer_sequence<T, rest...>, std::integer_sequence<T, first, done...>>
{ };