有没有一种方法可以在n维数组(n是变量)上迭代而不使用递归?

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

有没有一种方法可以在n维数组(n是变量)上迭代而不使用递归?我现在用的是c++，但我想几乎任何语言都能回答这个问题。

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.

编辑:实际上，我的实际问题有点不同:我实际上想枚举数组的索引。简单的2D示例，使用2x2数组:0,0;0,1;1,0;1、1。

4 个解决方案

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

#2

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.

是的——请记住，c++(或大多数语言)中的任何多维数组都是一个线性的内存区域。该语言通过自动地将任何外部维度索引乘以该维度的大小/偏移量来帮助您。

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.

因此，您可以“手工”遍历多维数组，方法与编写数组[x][y][z]时使用的算法相同——但当然，您可以对任意数量的维数进行遍历。

#3

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

我最近编写了这个通用帮助程序来散列NxM 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);

#4

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).

是的。如果数组为“平”的记忆,你可以从数组迭代数组+ n ^ n。注意，同样的递归解决方案也适用于循环+堆栈。(任何递归都可以翻译为循环+堆栈)。

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.

编辑:在你编辑你的问题:究竟m ^ n(假设每个维度有相同数量的元素),一个简单的枚举将是0,1,…,(m ^ n)1。访问是通过数组+ ENUM_NUMBER进行的。

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

#2