N-dimensionally nested metaloops with templates

Question

I am trying to do N-dimensionally nested metaloops with template metaprogramming. The nesting part is trivial, however passing all the arbitrary number of iteration indices as template parameters to the most-inner loop seems problematic.

A simple unnested metaloop looks like:

template <size_t I, size_t N>
struct meta_for
{
    template <typename Lambda>
    inline meta_for(Lambda &&iteration)
    {
        iteration(I);
        meta_for<I+1, N> next(static_cast<Lambda&&>(iteration));
    }
};

template <size_t N>
struct meta_for<N, N>
{
    template <typename Lambda>
    inline meta_for(Lambda &&iteration)
    {
        return;
    }
};

#include <iostream>

int main()
{
    meta_for<0, 10>([&](size_t i) // perform 10 iterations
    {
        std::cout << i << '\n';
    });

    return 0;
}

Now, I want to make a metaloop, which accepts an N parameter denoting the dimensionality (the level of nesting), using like:

#include <iostream>

int main()
{
    // perform 3 dimensionally nested iterations
    // each index goes from 0 to 10
    // so 10x10x10 iterations performed
    meta_for<3, 0, 10>([&](size_t i, size_t j, size_t k)
    {
        std::cout << i << ' ' << j << ' ' << k << '\n';
    });

    return 0;
}

Answer 1

Since this question appears to still be getting traffic, I thought it would be a good idea to show how much easier this is to do in C++17. First, the full code

Demo

template<size_t Dimensions, class Callable>
constexpr void meta_for_loop(size_t begin, size_t end, Callable&& c)
{
    static_assert(Dimensions > 0);
    for(size_t i = begin; i != end; ++i)
    {
        if constexpr(Dimensions == 1)
        {
            c(i);
        }
        else
        {
            auto bind_an_argument = [i, &c](auto... args)
            {
                c(i, args...);
            };
            meta_for_loop<Dimensions-1>(begin, end, bind_an_argument);
        }
    }
}

---

Explanation:

1. If the Dimensions is 1, we simply call the provided-lambda with the next index in a loop
2. Else, we create a new callable from the provided one, except that we bind the loop index to one of the callable arguments. Then we recurse on our meta for loop with 1 fewer dimension.

If you're familiar at all with functional programming, this is a bit easier to understand, as it's an application of currying.

How it works in more concrete terms:

You want a binary counter that goes

0 0
0 1
1 0
1 1

So you create a callable that can print two integers like so:

auto callable = [](size_t i, size_t j)
{
   std::cout << i << " " << j << std::endl;
};

And since we have two columns, we have two dimensions, so D = 2.

We call our meta for loop defined above like so:

meta_for_loop<2>(0, 2, callable);

The end argument to meta_for_loop is 2 instead of 1 because we are modeling a half-closed interval [start, end), which is common in programming because people often want the first index to be included in their loop, and then they want to iterate (end - start) times.

Let's step through the algorithm:

1. Dimensions == 2, so we don't fail our static assert
2. We begin to iterate, i = 0
3. Dimensions == 2, so we enter the "else" branch of our constexpr if statement
   • We create a new callable that captures the passed in callable and name it bind_an_argument to reflect that we're binding one argument of the provided callable c.

So, bind_an_argument effectively looks like this:

void bind_an_argument(size_t j)
{
    c(i, j);
}

Note that i stays the same, but j is variable. This is useful in our meta for loop because we want to model the fact that an outer loop stays at the same index while an inner loop iterates over its whole range. For example

for(int i = 0; i < N; ++i)
{
    for (int j = 0; j < M; ++j)
    {
       /*...*/
    }
}

when i == 0 we iterate over all values of j from 0 to M, and then we repeat for i == 1, i == 2, etc.

4. We call meta_for_loop again, except that Dimensions is now 1 instead of 2, and our Callable is now bind_an_argument instead of c
5. Dimensions == 1 so our static_assert passes
6. We begin to loop for(size_t i = 0; i < 2; ++i)
7. Dimensions == 1 so we enter the if branch of our constexpr if
8. We call bind_an_argument with i = 1, which calls our callable from above with arguments (0, 0), the first of which was bound from the previous call to meta_for_loop. This produces output

   0 0

9. We call bind_an_argument with i == 1, which calls our callable from above with arguments (0, 1), the first argument of which was bound during our previous call to meta_for_loop. This produces output

   0 1

10. We finish iterating, so the stack unwinds to the parent calling function
11. We're back in our call to meta_for_loop with Dimensions == 2 and Callable == callable. We finish our first loop iteration and then increment i to 1
12. Since Dimensions == 2, we enter the else branch again
13. Repeat steps 4 through 10, except that the first argument to callable is bound to 1 instead of 0. This produces output

    1 0
    1 1