Replacing Multi-Dimension for-loop with range-based for-loop

Question

I have a Vec3 class. What is the best way to replace a loop like

for (int x = 20; x < 25; x++)
    for (int y = 40; y < 45; y++)
        for (int z = 2; z < 4; z++) doStuff({x,y,z});

with something like this:

for(Vec3 v: Vec3range({20,40,2}, {25,45,4}))
    doStuff(v);

without any runtime costs?

Answer 1

For this, I wrote an iterating and a combining adaptor in my functional library fn:

#include <fn.h>
#include <iostream>

int main() {
    using std; using fn;

    for (auto &&values : combine(seq(20,25), seq(40,45), seq(2,4))) {
        int x, y, z; 
        tie(x, y, z) = values;
        cout << x << ", " << y << ", " << z << "\n";
        // or in your case: doStuff({x, y, z});
    }
}

Output:

20, 40, 2
20, 40, 3
20, 41, 2
20, 41, 3
...
24, 43, 2
24, 43, 3
24, 44, 2
24, 44, 3

Here, seq(a, b) returns an implicit range which iterates through the values [a, b) (i.e. the first is inclusive, the second exclusive). (A third parameter can specify the step and more complex alternatives exist for more control over the iteration.)

The function combine(ranges...) returns an implicit range which iterates over all combinations of the given ranges (where the first is considered the "most significant" one, similar to your "outer-most" loop). Its iterator dereferences to a std::tuple holding the current combination.

This tuple is then tied in the loop body to some variables. (Sadly, there is no "auto-tie" for the range-based for loop like for(tie(auto x, auto y, auto z) : ...).)

---

Implementation:

seq()

That's quite easy: it is a function returning an adaptor object which has begin() and end() functions. They return a custom iterator which increments the current value in operator++ and returns it in operator*.

combine()

This is more interesting: it returns an adaptor object which holds the ranges being provided as the arguments to combine in a tuple member. The iterator of this adaptor holds iterators to the wrapped ranges in a tuple member, but three times: the current position, the begin and the end, you soon see why.

The operator++ of the iterator is most likely the most interesting one: it's implemented recursively using variadic templates in variadic_ops.h, va_next_combination() and it is given triplets of iterators (for each range the current, begin, and end):

// base case
inline bool va_next_combination() {
    return true;
}

// recursive case
template<typename Head, typename ...Tail>
inline bool va_next_combination(std::tuple<Head&,Head&,Head&> && curr_and_begin_and_end, std::tuple<Tail&,Tail&,Tail&> &&...t) {
    // advance the "tail" to its next combination and check if it had an overflow
    if (va_next_combination(std::forward<std::tuple<Tail&,Tail&,Tail&>>(t)...)) {
        // advance the "head" iterator
        ++std::get<0>(curr_and_begin_and_end);
        // check if the "head" just overflow
        bool at_end = (std::get<0>(curr_and_begin_and_end) == std::get<2>(curr_and_begin_and_end));
        // if it did, put it back to the beginning and report the overflow
        if (at_end) std::get<0>(curr_and_begin_and_end) = std::get<1>(curr_and_begin_and_end);
        return at_end;
    } else {
        // "tail" didn't overflow, so we do nothing and no overflow should be reported
        return false;
    }
}

Starting from the right most iterator in the set, it increments the iterator. If it just reached the end of the range, it reports that as the return value of the recursive function. The next iterator checks that value, if it is true itself needs to advance (otherwise not) as well as "reset" the iterator next to the right (i.e. "wrap around" its overflow), and finally it reports the same information to the next to the left.

That's basically how mechanical counters work, if you start at the "if"-condition in the deepest recursion level.