Variadic nested loops

Question

I am working on an N-dimensional grid.
I would like to generate nested loops depending on any dimension (2D, 3D, 4D, etc.).
How can I do it elegantly and quickly? Below is a simple illustration of my problem. I am writing in C ++, but I think this question may be useful for other languages.
I need to know the indices (i, j, k ...) in my part. Edit: lower_bound and upper_bound represent indexes in the grid, so they are always positive.

#include <vector> int main() { // Dimension here is 3D std::vector<size_t> lower_bound({4,2,1}); std::vector<size_t> upper_bound({16,47,9}); for (size_t i = lower_bound[0]; i < upper_bound[0]; i ++) for (size_t j = lower_bound[1]; j < upper_bound[1]; j ++) for (size_t k = lower_bound[2]; k < upper_bound[2]; k ++) // for (size_t l = lower_bound[3]; l < upper_bound[3]; l ++) // ... { // Do stuff such as grid({i,j,k}) = 2 * i + 3 *j - 4 * k; // where grid size is the total number of vertices } } 

Answer 1

The following may help:

 bool increment( std::vector<int>& v, const std::vector<int>& lower, const std::vector<int>& upper) { assert(v.size() == lower.size()); assert(v.size() == upper.size()); for (auto i = v.size(); i-- != 0; ) { ++v[i]; if (v[i] != upper[i]) { return true; } v[i] = lower[i]; } return false; } 

And use it like this:

 int main() { const std::vector<int> lower_bound({4,2,1}); const std::vector<int> upper_bound({6,7,4}); std::vector<int> current = lower_bound; do { std::copy(current.begin(), current.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; } while (increment(current, lower_bound, upper_bound)); } 

Live demo

Answer 2

A recursive function can help you achieve what you want.

 void Recursive( int comp ) { if(comp == dimension) { // Do stuff } else { for (int e = lower_bound[comp]; e < upper_bound[comp]; e++) Recursive(comp+1); } } 

Some additions may be required in the function signature if you need to know the current indices (i, j, k, ...) in the "Do Stuff" section.

This is a clean way to access these indices.

 void Recursive( int comp, int dimension ) { static std::vector<int> indices; if( comp == 0 ) // initialize indices { indices.clear(); indices.resize(dimension, 0); } if(comp == dimension -1) { // Do stuff } else { int& e = indices[comp]; for (e = lower_bound[comp]; e < upper_bound[comp]; e++) Recursive(comp+1); } } 

This, however, cannot be used in multiple threads due to a common static vector.

Answer 3

Probably some typos are not everything, but I would smooth the whole range.

This is based on the idea that a range can be described as

 x_0 + d_0*(x_1+d_1*(x_2+d_2....) 

So we can collapse this way

 std::vector<int> lower_bound{-4,-5,6}; std::vector<int> upper_bound{6,7,4}; //ranges std::vector<int> ranges; for (size_t i = 0; i < lower_bound.size(); i++) { ranges.push_back(upper_bound[i]-lower_bound[i]); } for (int idx = 0; idx < numel; idx++) { //if you don't need the actual indicies, you're done //extract indexes int idx2 = idx; std::vector<int> indexes; for (int i = 0; i < ranges.size(); i++) { indexes.push_back(idx2%ranges[i]-lower_bound[i]); idx2 = idx2/ranges[i]; } //do stuff grid[idx] = 2 * indexes[0] + 3 *indexes[1] - 4 * indexes[2]; } 

Edit: be more general:

  template <typename D> void multi_for(const std::vector<int>& lower_bound, const std::vector<int> upper_bound, D d) { std::vector<int> ranges; for (size_t i = 0; i < lower_bound.size(); i++) { ranges.push_back(upper_bound[i]-lower_bound[i]); } size_t numel = std::accumulate(ranges.begin(), ranges.end(), std::multiplies<int,int>{}); for (int idx = 0; idx < numel; idx++) { //if you don't need the actual indicies, you're done //extract indexes int idx2 = idx; std::vector<int> indexes; for (int i = 0; i < ranges.size(); i++) { indexes.push_back(idx2%ranges[i]-lower_bound[i]); idx2 = idx2/ranges[i]; } //do stuff d(idx,indexes); } } //main size_t* grid;//initialize to whateer std::vector<int> lower_bound{-4,-5,6}; std::vector<int> upper_bound{6,7,4}; auto do_stuff = [grid](size_t idx, const std::vector<int> indexes) { grid[idx] = 2 * indexes[0] + 3 *indexes[1] - 4 * indexes[2]; }; multi_for(lower_bound,upper_bound,do_stuff); 

Answer 4

An iterative approach might look like this:

 #include <iostream> #include <vector> int main() { std::vector<int> lower_bound({-4, -5, -6}); std::vector<int> upper_bound({ 6, 7, 4}); auto increase_counters = [&](std::vector<int> &c) { for(std::size_t i = 0; i < c.size(); ++i) { // This bit could be made to look prettier if the indices are counted the // other way around. Not that it really matters. int &ctr = c .rbegin()[i]; int top = upper_bound.rbegin()[i]; int bottom = lower_bound.rbegin()[i]; // count up the innermost counter if(ctr + 1 < top) { ++ctr; return; } // if it flows over the upper bound, wrap around and continue with // the next. ctr = bottom; } // end condition. If we end up here, loop over. c = upper_bound; }; for(std::vector<int> counters = lower_bound; counters != upper_bound; increase_counters(counters)) { for(int i : counters) { std::cout << i << ", "; } std::cout << "\n"; } } 

... although this or a recursive approach is more elegant, it depends more on the use case.

Answer 5

 #include <iostream> #include <vector> template <typename Func> void process(const std::vector<int>& lower, const std::vector<int>& upper, Func f) { std::vector<int> temp; process(lower, upper, f, 0, temp); } template <typename Func> void process(const std::vector<int>& lower, const std::vector<int>& upper, Func f, int index, std::vector<int>& current) { if (index == lower.size()) { f(current); return; } for (int i = lower[index]; i < upper[index]; ++i) { current.push_back(i); process(lower, upper, f, index + 1, current); current.pop_back(); } } int main() { // Dimension here is 3D std::vector<int> lower_bound({-4, -5, 6}); std::vector<int> upper_bound({6, 7, 4}); // Replace the lambda below with whatever code you want to process // the resulting permutations. process(lower_bound, upper_bound, [](const std::vector<int>& values) { for (std::vector<int>::const_iterator it = values.begin(); it != values.end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; }); }