Replace multidimensional measurement for cycle based range for cycle

Question

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

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); 

at no cost to the runtime?

Answer 1

This is the simplest implementation that I could do:

 #include <iostream> #include <tuple> using namespace std; using tuple_3d = tuple<int, int, int>; struct range_3d; struct range_3d_iterator { const range_3d& c; tuple_3d i; bool operator!=(const range_3d_iterator& other) { return get<0>(i) != get<0>(other.i) && get<1>(i) != get<1>(other.i) && get<2>(i) != get<2>(other.i); } tuple_3d operator*() const { return make_tuple(get<0>(i), get<1>(i), get<2>(i)); } const range_3d_iterator& operator++(); }; struct range_3d { tuple_3d s; tuple_3d e; range_3d_iterator begin() const { return { *this, s }; } range_3d_iterator end() const { return { *this, e }; } }; const range_3d_iterator& range_3d_iterator::operator++() { ++get<2>(i); if (get<2>(i) == get<2>(ce)) { get<2>(i) = get<2>(cs); ++get<1>(i); if (get<1>(i) == get<1>(ce)) { get<1>(i) = get<1>(cs); ++get<0>(i); } } return *this; } int main(void) { for (auto&& v : range_3d{ make_tuple(20, 40, 2), make_tuple(25, 45, 4) }) cout << get<0>(v) << ' ' << get<1>(v) << ' ' << get<2>(v) << endl; } 

Naming is a little shit, but aside, the concept is simple. range_3d is a simple class that supports begin() , end() to get the range for the loop to work, then the "smartness" is in range_3d_iterator , which will iterate the tuple. Given how I used the tuple here, it is trivial to extend to arbitrary sizes ...

TBH, the original for the cycle is pretty clear ... IMO!

Answer 2

To do this, I wrote an iterative and combining adapter in the fn functional library :

 #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 that iterates through the values ​​of [a, b) (i.e., the first is inclusive, the second is exclusive). (The third parameter may indicate the step, and more complex alternatives exist for more control over the iteration.)

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

This tuple is then bound to the body of the loop to some variables. (Unfortunately, there is no "auto-binding" for a loop-based range, like for(tie(auto x, auto y, auto z) : ...) .)

---

Implementation:

seq()

This is pretty simple: it is a function that returns an adapter object that has begin() and end() functions. They return a custom iterator that increments the current value in operator++ and returns it in operator* .

combine()

This is more interesting: it returns an adapter object that contains the ranges provided as combine arguments in the tuple member. The iterator of this adapter contains iterators for the wrapped ranges in the tuple member, but three times: the current position, the beginning and the end, you will soon see why.

The operator++ iterator is most likely the most interesting one: it is implemented recursively using variational patterns in variadic_ops.h , va_next_combination() and it is set with iterator triplets (for each range, current, start 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 with the right iterator itself in the set, it increments the iterator. If it has just reached the end of the range, it reports that the return value of the recursive function. The next iterator checks this value, if it is true, you need to promote it yourself (otherwise), as well as "reset" the iterator next to the right (ie, "Wrap" its overflow) and, finally, it passes the same information to the next left .

Basically, how mechanical counters work if you start with an "if" -condition at the deepest level of recursion.

Answer 3

 template<size_t N> using indexes=std::array<size_t,N>; template<size_t N> void advance( indexes<N>& in, indexes<N-1> const& limit, size_t amt=1 ); 

which finds the amt index further along, wrapping around at the limit.

Then write a range object. It retains a limit and two iterators, b and e. begin returns b and end e .

Iterators have a pointer to the range from which they come and an array of values. They are ++ via next above. Write a regular iterator pattern interpreter.

Your function should probably be:

 template<size_t N> multi_range_t<N> multi_range( indexes<N> start, indexes<N> finish ); 

for which you want to pass N

Finally, write a copy of ctor for Vec3 from std::array<3,T> .

Perhaps you can make it easier by making it 3 instead of N , but only by touching.