Integer sequences implementation C++

Question

I have been reading up on compile time sequences and I have a hard time understanding how the program below works. Can anyone out there explain the program below in detail? Thanks!

#include<iostream>
template<int...>
struct ints
{

};

template<int N, int...args>
struct rev_seq : rev_seq<N - 1, 2 * args..., 1> {};

template<int...args>
struct rev_seq<0, args...>
{
    using type = ints<args...>;

};

template<int N>
using RS = typename rev_seq<N + 1>::type;

template<int... args>
void fU(ints<args...>&& s)
{
    for (const auto& i : { args... }) std::cout << i << " ";
    std::cout << std::endl;
}
int main()
{
    fU(RS<5>());
}

Answer 1

RS<2>() instantiates rev_seq<2, 2>::type

rev_seq<2, 2>::type is the primary template (not the specialized one) for rev_seq:

template<int C, int N, int... Is>
struct rev_seq : rev_seq<C - 1, N, N - C, Is...>{}

This is a recursive declaration, so it derives from a version of itself like so:

rev_seq<2, 2, (empty int... Is pack)>

derives from

rev_seq<2-1, 2, 2 - 2>

which is rev_seq<1, 2, 0>

That 0 on the end is part of the int... Is pack on the base class

This again recurses

rev_seq<1, 2, 0>

derives from

rev_seq<1-1, 2, 2-1, 0>

which is rev_seq<0, 2, (1, 0)>

See how the last parameter argument gets appended to the pack?

rev_seq<0, 2, (1, 0)> matches the following template specialization for rev_seq:

template<int N, int... Is>
struct rev_seq<0, N, Is...>
{
    using type = ints<N, Is...>;
};

Note that this struct doesn't derive from anything

At this point, the type type in the class becomes

ints<2, 1, 0>

See how the specialization causes us to append N to the front of the sequence?

Finally, we pass the constructed ints to a function:

template<int... Is>
void fU(ints<Is...>&& s)
{
    for (auto i : { Is... }) std::cout << i << " ";
    std::cout << std::endl;
}

The loop iterates over the integers

for (auto i : { Is... })

Here { Is...} is a pack expansion, creating an initializer list for us to iterate over. It's fun to note that this is one of the very few places you can just create and use an initializer list, almost all other cases are relegated to matching a std::initializer_list constructor overload for some class (e.g., std::vector)

Answer 2

Assuming you already know the theory behind variadic template, the best approach I may suggest is to "manually unroll" template definitions.

Most of the cases variadic templates exploit a recursive approaches.

---

Let's try to do this exercise.

The core part is: RS<5>(). That's just an instance of rev_seq<5, 5>::type. Well, let's go deep into rev_seq.

Its declaration:

template<int C, int N, int... Is> 
struct rev_seq // ...

So that instance will be "mapped":

template<5, 5, $> 
struct rev_seq // ...

where $ is just a placeholder symbol to indicate an empty variadic list.

rev_seq inherits recursively:

template<5, 5, $> 
struct rev_seq : rev_seq <4, 5, 0, $> {}

Of course rev_seq <4, 5, 0, $> (i.e., rev_seq<4, 5, {0}>) inherits and so on.

<5, 5, $>                -> 
<4, 5, {0}>              -> 
<3, 5, {1, 0}>           -> 
<2, 5, {2, 1, 0}>        ->
<1, 5, {3, 2, 1, 0}>     ->
<0, 5, {4, 3, 2, 1, 0}>

When the first template parameter is 0 we stop. Because in that case we have a partial template specialization. Here you can see the analogy with the "base case" in the recursion strategy.

Therefore, we finally get this inheritance:

struct rev_seq<0, N, Is...>
{
    using type = ints<N, Is...>;
};

In your case:

struct rev_seq<0, 5, {4, 3, 2, 1, 0}>
{
    using type = ints<5, {4, 3, 2, 1, 0}>;
};

Note that ints is just a variadic list. That is: ints<5, {4, 3, 2, 1, 0}> actually is ints<{5, 4, 3, 2, 1, 0}>.

So, in the end, you are just calling the "print function" with this particular instance of ints:

template<{5, 4, 3, 2, 1, 0}>
void fU(ints<{5, 4, 3, 2, 1, 0}>&& s)
{
    for (auto i : { 5, 4, 3, 2, 1, 0 }) std::cout << i << " ";
    std::cout << std::endl;
}

Please note that is not a valid C++ syntax, but more just a "graphical representation" aimed to show the recursive process.