Is there a way to iterate over an n-dimensional array (where n is variable) without using recursion?

Is there a way to iterate over an n-dimensional array (where n is variable) without us开发者_开发技巧ing recursion? I'm using C++ at the moment, but I guess an answer in almost any language would do.

EDIT: Actually my real question is a bit different: I actually want to enumerate the indices of the array. Simple 2D example, with a 2x2 array: 0,0; 0,1; 1,0; 1,1.

---

void iterate(const std::vector<int> &dims)
{
    std::vector<int> idxs(dims.size());

    while (1)
    {
        // Print
        for (int i = 0; i < dims.size(); i++)
        {
            std::cout << idxs[i] << " ";
        }
        std::cout << "\n";

        // Update
        int j;
        for (j = 0; j < dims.size(); j++)
        {
            idxs[j]++;
            if (idxs[j] < dims[j]) break;
            idxs[j] = 0;
        }
        if (j == dims.size()) break;
    }
}

---

Yes - just remember that any multi-dimentional array in C++ (or most languages) is simply a linear region of memory. The language just helps you out by automatically multiplying any outer dimension indexes by the size / offset of that dimension.

You can therefore 'manually' walk the multidimensional array by doing the same arithmetic the language would do when you write array[x][y][z] - but of course you can do it for an arbitrary number of dimensions.

---

yes. if the array is 'flat' in the memory, you can just iterate from array to array + n^n.
note that the same solution with recursion will work with a loop + stack. (any recursion can be translated as loop + stack).

EDIT: after you editted your question: there are exactly m^n (assuming each dimension has the same number of elements m), a simple enumeration will be 0,1,...,(m^n)-1. access is via array + ENUM_NUMBER.

---

I recently wrote this generic helper to hash an NxM array of T.

template <class T, size_t N, size_t M>
    size_t hash(const T (&aa)[N][M])
{
    size_t seed = 0;
    for (size_t i=0; i<N; i++)
        boost::hash_combine(seed, boost::hash_range(aa[i], aa[i]+M));
    return seed;
}

You could use the same gist to iterate over arbitrary arrays

template <class T, size_t N, size_t M, class F>
    void for_each(const T (&aa)[N][M], F func)
{
    size_t seed = 0;
    for (size_t i=0; i<N; i++)
    for (size_t j=0; j<M; j++)
        func(aa[i][j]);
}

template <class T, size_t N, size_t M, size_t L, class F>
    void for_each(const T (&aaa)[N][M][L], F func)
{
    size_t seed = 0;
    for (size_t i=0; i<N; i++)
    for (size_t j=0; j<M; j++)
    for (size_t k=0; k<L; k++)
        func(aa[i][j][k]);
}

Use it like this:

void display(float f) {   std::cout << f << std::endl; }
// ...
float fff[1][2][3];
for_each(fff, display);