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?
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) : ...).)
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.
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 index amt further along, wrapping around at limit.
Then write a range object. It stores the limit and two iterators, b and e. begin returns b, and end e.
The iterators have a pointer to the range they come from and an array of values. They ++ via next above. Write the usual forward iterator boilerplate.
Your function probably should be:
template<size_t N>
multi_range_t<N> multi_range( indexes<N> start, indexes<N> finish );
which requires you to pass N.
Finally write a copy ctor for Vec3 from std::array<3,T>.
You can probably make it a touch easier by making it 3 instead of N, but only a touch.
This is about the simplest implementation I could manage:
#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>(c.e))
{
get<2>(i) = get<2>(c.s);
++get<1>(i);
if (get<1>(i) == get<1>(c.e))
{
get<1>(i) = get<1>(c.s);
++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;
}
The naming is a bit crap, but that aside, the concept is simple. The range_3d is a simple class which supports begin(), end() to get the range for loop to work, then the "smartness" is in the range_3d_iterator which will iterate the tuple. Given the way I've used the tuple here, it's trivial to extend to arbitary dimensions...
TBH, the original for loop is pretty clear... IMO!
