N-dimensionally nested metaloops with templates

Someone better versed in this stuff can improve my answer.

Live Demo

The gist of my solution is that you declare N dimensions, with a start and an end.

It recurses on N-1 dimensions with the same start and end.

When it reaches the 1st dimension, it will actually begin incrementing the start, calling the passed function.

It will always attempt to pass a number of arguments identical to the number of dimensions (their indices).

So a call like this:

meta_for<2, 0, 2>::loop(
    [](size_t i, size_t j)
    {
        std::cout << i << " " << j << std::endl;
    });

Will result in output like this:

0 0

0 1

1 0

1 1

Here's the meta_for structure, which uses a helper, iterate:

template<size_t D, size_t B, size_t E>
struct meta_for
{
    template<typename Func>
    static void loop(Func&& func)
    {
        iterate<D, B, B, E>::apply(std::forward<Func>(func));
    }
};

And the helpers:

// a helper macro to avoid repeating myself too much
#define FN template<typename Func, typename... Args> \
             static void apply(Func&& func, Args&&... a)


// Outer loop. S="Self" or "Start". Indicating current index of outer loop. Intent is to iterate until S == E
template<int Dim, size_t S, size_t B, size_t E>
struct iterate
{
    static_assert(S < E && B < E, "Indices are wrong");
    FN
    {
        // outer loop recursive case. Recurse on lower Dimension (Dim-1), and then increment outer loop (S+1)
        iterate<Dim-1, B, B, E>::apply (func, a..., S);
        iterate<Dim, S+1, B, E>::apply (func, a...);
    }
};

// Outer loop base case
template<int Dim, size_t B, size_t E> 
struct iterate<Dim, E, B, E>
{
    FN
    {
        // outer loop base case, End == End. Terminate loop
    }
};

// innter loop. "S" is outer loop's current index, which we need to pass on to function
// "B" is inner loop's (this loop) current index, which needs to iterate until B == E
template<size_t S, size_t B, size_t E>
struct iterate<1, S, B, E>
{
    static_assert(S < E && B < E, "Indices are wrong");
    FN
    {
        // inner loop recursive case. Perform work, and then recurse on next index (B+1)
        func(a..., B);
        iterate<1, S, B+1, E>::apply(func, a...);
    }
};

// inner loop base case
template<size_t S, size_t E>
struct iterate<1, S, E, E>
{
    FN
    {
        // inner loop base case, End == End. Terminate loop
    }
};

// case where zero dimensions (no loop)
template<size_t S, size_t B, size_t E>
struct iterate<0, S, B, E>
{
    static_assert(sizeof(S) == 0, "Need more than 0 dimensions!");
};

---

More explanation

This solution, like any other involving variadic templates, relies on recursion.

I wanted to express recursion on an outer loop, so I started with a base case; the end of the loop. This is the case where the start is the same as the end :

template<int Dim, size_t B, size_t E> 
struct iterate<Dim, E, B, E>
{ /*..*/};

Notice here that this is a specialization for <Dim, E, B, E>. The second position indicates the outer loop's current index, and the last position indicates the index to iterate up to (but not including). So in this case, the current index is the same as the last, indicating we are finished looping (and hence a "do nothing" function).

The recursive case for the outer loop involves the scenario where the loop index is less than the index to iterate to. In template terms, the second position is less than the fourth position:

template<int Dim, size_t S, size_t B, size_t E>
struct iterate
{/*...*/}

Notice this is NOT a specialization.

The logic of this function is that an outer loop should signal an inner loop to begin executing from its start, and then the outer loop continues and starts the process all over again for inner loops:

iterate<Dim-1, B, B, E>::apply (func, a..., S);
iterate<Dim, S+1, B, E>::apply (func, a...);

Notice in the first line that the second template argument is again B, indicating to start at the beginning again. This is necessary because the other recursive case on the second line increments S (incrementing outer loop index).

The entire time, we are also accumulating arguments to pass to the function:

::apply(func, a..., S)

is passing the function on, along with indices of higher dimension loops, and then appending the current loop's index (S). a here is a variadic template.

The inner loop

When I say "inner loop", I mean the innermost loop. This loop needs to simply increment until the start index reaches the end index, and not attempt to recurse on any lower dimension. In our case, this is when our Dim (Dimension) parameter is 1:

template<size_t S, size_t B, size_t E>
struct iterate<1, S, B, E>
{/*...*/};

At this point, we finally want to call our passed function, along with all arguments we've accumulated thus far (the indices of the outer loops) PLUS, the index of the innermost loop:

func(a..., B);

And then recurse (increment index)

iterate<1, S, B+1, E>::apply(func, a...);

The base case here is when the innermost loop's index is the same as the end index (AND the dimension is 1):

template<size_t S, size_t E>
struct iterate<1, S, E, E>
{/*...*/};

Hence the "do nothing" function here; there shouldn't be any work performed because the loop is terminating.

Finally, I included one last specialization to catch a user error where they didn't specify any dimensions:

template<size_t S, size_t B, size_t E>
struct iterate<0, S, B, E>

Which uses static_assert to always fail because sizeof(size_t) is not zero:

static_assert(sizeof(S) == 0, "Need more than 0 dimensions!");

Conclusion

This is a specific use case template meta-program. Where we essentially generate N nested for loops that all have the same start and end indices AND we want to pass those indices to a function. We could do a little more work to make it such that the iterate structure could stand on its own without making the assumption that the outer loop's start and end indices are the same as an inner loop's.

My favorite application of this code is that we can use it to make an N-dimensional counter. For example, a binary counter for N-bits (found in the live demo).

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