在C ++中迭代具有可变维大小的N维矩阵

Question

我正在尝试遍历n维矩阵，其中矩阵的每个维也具有可变大小。

我特别想让每个元素具有多维坐标，就像a for loop允许您i访问数组中的元素。

我想从根本上重新创建嵌套的for循环，例如以下代码，在其中可以将任何其他类型的数字放入dimensionSize。

std::vector<int> dimensionSize = {1, 4, 4};

for (int i = 0; i < dimensionSize [0]; i++)
{
    for (int j = 0; j < dimensionSize [1]; j++)
    {
        for (int k = 0; k < dimensionSize [2]; k++)
        {
            std::cout << i << " " << j << " " << k << std::endl;
        }
    }
}

这个嵌套循环的结果是...

0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 1 1
0 1 2
0 1 3
0 2 0
0 2 1
0 2 2
0 2 3
0 3 0
0 3 1
0 3 2
0 3 3

到目前为止，我在C ++中遍历n维矩阵时发现的所有示例/解决方案实际上都是凌乱的代码，并且对于固定尺寸的尺寸（例如9x9x9或3x3x3）也是如此。

但是我的矩阵可以是1x256x513x3或各种尺寸。

我目前有以下功能，它接近我想要的功能，但是它有一个问题。

void iterate_over_n_dimensions (std::vector<int>& counters,
                                std::vector<int> dimensionSizes, 
                                int currentDimension)
{
    for (long i = 0; i < dimensionSizes [currentDimension]; i++)
    {
        print_counter (counters);

        if (currentDimension + 1 != dimensionSizes.size())
        {
            iterate_over_n_dimensions (counters, 
                                       dimensionSizes, 
                                       currentDimension + 1);
        }

        counters [currentDimension] ++;
        counters [currentDimension] %= dimensionSizes [currentDimension];
    }
}

运行以下内容...

int main(int argc, const char * argv[])
{
    std::vector<int> dimensionSizes = {1, 4, 4};
    std::vector<int> counters(dimensionSizes.size(), 0);

    iterate_over_n_dimensions (counters, dimensionSizes, 0);

    return 0;
}

该递归函数的结果是...

0 0 0 
0 0 0 
0 0 0 
0 0 1 
0 0 2 
0 0 3 
0 1 0 
0 1 0 
0 1 1 
0 1 2 
0 1 3 
0 2 0 
0 2 0 
0 2 1 
0 2 2 
0 2 3 
0 3 0 
0 3 0 
0 3 1 
0 3 2 
0 3 3 

您会看到，每次嵌套的for循环完成时，输出都会重复一次！在...的重复

0 1 0 
0 2 0 
0 3 0 

我添加的尺寸越大，这个问题就越严重。例如，每次完成4维循环时，都会重复1x4x4x2矩阵，并在其他位置重复多次。

如果有人可以提出一个与我当前函数一样简洁的解决方案，我将不胜感激！

现在，我将不得不实现带有大量for循环的大规模switch语句，并将维数的上限限制为5个左右。

Answer 1

If I understand correctly you want to iterate all elements of the "n-dimensional matrix" (actually not called "matrix") and need a way to get all indices. I would start with something like this:

#include <iostream>
#include <vector>

struct multi_index {
    std::vector<size_t> dimensions;
    std::vector<size_t> current;
    multi_index(std::vector<size_t> dim) : dimensions(dim), current(dim.size()) {}
    void print() {
        for (const auto& e : current) std::cout << e << " ";
        std::cout << "\n";
    }
    bool increment() {        
        for (size_t i=0;i<dimensions.size();++i) {
            current[i] += 1;
            if (current[i] >= dimensions[i]) {
                current[i] = 0;
            } else {
                return true;
            }
        }
        return false;
    }
};


int main() {
    multi_index x{{1,2,3}};
    do {
        x.print();
    } while (x.increment());    
}

And then adpapt it to the specific needs. Eg the vectors could probably be std::arrays and depening on the actual container you probably want an easy way to access the element in the container without having to write data[ x[0] ][ x[1] ][ x[2] ].

Note that often it is better to flatten the data into a one dimensional data structure and then just map the indices. Especially when the dimensions are fixed you can benefit from data locality. While the above lets you write a single loop to iterate through all dimensions you then need the reverse mapping, ie many indices to a flat index. The following is not thoroughly tested, but just to outline the idea:

#include <vector>
#include <utility>
template <typename T>
struct multi_dim_array {
    std::vector<T> data;
    std::vector<size_t> dimensions;
    multi_dim_array(std::vector<size_t> dim) {
        size_t total = 1;
        for (const auto& d : dim) total *= d;
        data.resize(total);
    }
    T& get(std::initializer_list<int> index) {
        return data[flatten_index(index)];
    }
    size_t flatten_index(std::initializer_list<int> index) {
        size_t flat = 0;
        size_t sub_size = 1;
        for (auto x = std::make_pair(0u,index.begin());
             x.first < dimensions.size() && x.second != index.end();
             ++x.first, ++x.second) {
            flat += (*x.second) * sub_size;
            sub_size *= dimensions[x.first];
        }
        return flat;
    }
};
int main(){
    multi_dim_array<int> x{{2,2,3}};
    x.get({1,1,1}) = 5;
}

Once you store the multidimensional data in a flat array/vector writing a simple loop to iterate all elements should be straightforward.

PS: to be honest I didn't bother to find the problem in your code, recursion makes me dizzy :P