Loop nidificati Variadic

Question

Sto lavorando su una griglia N dimensionale.
Vorrei generare cicli annidati in base a qualsiasi dimensione (2D, 3D, 4D, ecc.).
Come posso farlo in modo elegante e veloce? Di seguito una semplice illustrazione del mio problema. Sto scrivendo in C++ ma penso che questo tipo di domanda possa essere utile per altre lingue.
Ho bisogno di conoscere gli indici (i, j, k ...) nella parte do do stuff. Modifica: lower_bound e upper_bound rappresentano gli indici nella griglia in modo che siano sempre positivi.

#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

segue può aiutare:

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

e usarlo in questo modo:

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

Una funzione ricorsiva può aiutarti a ottenere ciò che desideri.

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

Alcune aggiunte possono essere necessarie nella firma funzione se è necessario conoscere gli indici correnti (i, j, k, ...) nella vostra sezione "Do Stuff".

Questo è un modo pulito per avere accesso a questi indici

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

Questo non è tuttavia utilizzabile insieme più thread, grazie al vettore statica condivisa.

Answer 3

Probabilmente alcuni errori di battitura e altro, ma appiattirei l'intera gamma.

questo si basa sull'idea che il campo può essere descritto come

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

Così possiamo rotolare la nostra in questo modo

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: per essere più generico:

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

Un approccio iterativo potrebbe essere il seguente:

#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's 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"; 
    } 
} 

... anche se questo o un approccio ricorsivo è più elegante, piuttosto dipende dal caso d'uso.

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