Iterating over an N-dimensional matrix with variable dimension sizes in C++

Question

I am trying to iterate over an n-dimensional matrix where each dimension of the matrix also has a variable size.

I specifically want to have each elements multi-dimensional coordinate, like a for loop gives you i to access an element in an array.

I want to basically re-create a nested for loop like the following code with recursion where I could put any different kind of numbers into 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;
        }
    }
}

The results of this nested loop are...

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

So far all of the examples/solutions I've found on traversing n-dimensional matrices in C++ have been really messy code and also for fixed dimension sizes e.g. 9x9x9 or 3x3x3.

However my matrix could be 1x256x513x3 or all kinds of sizes.

I currently have the following function which is close to getting what I want however it's got one problem.

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

Run with the following...

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

The results of this recursive function are...

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 

You can see, the output repeats itself every time a nested for loop is completed! The repetitions at...

0 1 0 
0 2 0 
0 3 0 

This problem gets worse the more dimensions I add. For examples a matrix of 1x4x4x2 repeats every time it completes it's 4th dimensional loop and more in other places.

If anyone could suggest a solution that is as cleanly written as my current function I would really appreciate it!

Right now I'm going to have to implement a massive switch statement with lots of for loops and capping the number of dimensions at 5 or so.

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

Answer 2

I'm not sure I understood the question. If you want to visit each element of the multidimensional array once, the following code should do the job (counters in my case count the times each element has been visited so, at the end count, should be equal to dimensionSizes):

void print_counter(std::vector<int>& counters)
{
    for (unsigned int i = 0; i < counters.size(); ++i)
        std::cout << counters[i] << " ";
    std::cout << std::endl;
}

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



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

The output is:

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