C++多维C数组的迭代器

Question

我有大量的3到6维C数组需要遍历。使用类似于boost::multi_array的更C++化的表示不是一个选项，因为这些数组通过C框架PETSc进行传递（使用Fortran顺序，因此索引是反向的）。直接的循环最终看起来像这样：

  for (int i=range.ibeg; i<=range.iend; ++i){
   for (int j=range.jbeg; j<=range.jend; ++j){
     for (int k=range.kbeg; k<=range.kend; ++k){
       (...)

甚至更糟糕的是：

  for (int i=range.ibeg-1; i<=range.iend+1; ++i){
    for (int j=range.jbeg-1; j<=range.jend+1; ++j){
      for (int k=range.kbeg-1; k<=range.kend+1; ++k){
       for (int ii=0; ii<Np1d; ++ii){
        for (int jj=0; jj<Np1d; ++jj){
         for (int kk=0; kk<Np1d; ++kk){
           data[k][j][i].member[kk][jj][ii] = 
            func(otherdata[k][j][i].member[kk][jj][ii],
                 otherdata[k][j][i].member[kk][jj][ii+1]);

有很多类似的情况，循环索引的范围不同，这使得代码变得非常丑陋，同时也更容易出错。如何为这样的多维数组构建迭代器呢？

- Aurelius

---

你和我一样，但这就是我生活的世界。 - Aurelius

递归？有些情况下递归是更好的选择。如果你将其与模板结合使用，甚至可以使所有内容都内联化。 - Sebastian Hoffmann

你可以举个代码示例吗？ - Aurelius

你能把一个Foo[X][Y][Z]看作是一个Foo[XYZ]吗？那么foo[i][j][k]就变成了[i+jX+kX*Y]。或者这只是偶然能够工作而不被标准保证的事情吗？ - KitsuneYMG

@KitsuneYMG 如果在计算过程中不需要单独的坐标，那么将其简化为一个单一的“for”循环，计数直到整个n维数组的大小是微不足道的。这也更有效率，因为您不需要计算“i+jX+kX*Y”。但通常您确实需要单独的坐标，例如给定示例中的“ii”与“ii+1”。这就是我在答案中建议使用n维计数器的原因。 - iavr

Answer 1

完全模板化的版本其实并不难，所以在这里另外提供一个答案，同样提供在线示例。如果我没弄错的话，这应该在自定义嵌套循环之上没有额外的开销。你可以测量一下并让我知道。我打算为了自己的目的来实现它，这就是我在这里付出努力的原因。

template<size_t N>
using size = std::integral_constant<size_t, N>;

template<typename T, size_t N>
class counter : std::array<T, N>
{
    using A = std::array<T, N>;
    A b, e;

    template<size_t I = 0>
    void inc(size<I> = size<I>())
    {
        if (++_<I>() != std::get<I>(e))
            return;

        _<I>() = std::get<I>(b);
        inc(size<I+1>());
    }

    void inc(size<N-1>) { ++_<N-1>(); }

public:
    counter(const A& b, const A& e) : A(b), b(b), e(e) { }

    counter& operator++() { return inc(), *this; }

    operator bool() const { return _<N-1>() != std::get<N-1>(e); }

    template<size_t I>
    T& _() { return std::get <I>(*this); }

    template<size_t I>
    constexpr const T& _() const { return std::get <I>(*this); }
};

现在我已经有了_方法（可以自由重命名），而不是operator[]，它只是std::get的一种快捷方式，因此使用起来与operator[]相比没有那么冗长：

    for (counter<int, N> c(begin, end); c; ++c)
        cout << c._<0>() << " " << c._<1>() << " " << c._<2>() << endl;

事实上，您可以尝试先前的版本。

    for (counter<int, N> c(begin, end); c; ++c)
        cout << c[0] << " " << c[1] << " " << c[2] << endl;

要进行测量，因为它可能是等效的。为了使其起作用，请将std::array继承更改为public或在counter的public部分中声明using A :: operator [];。

绝对不同的是operator ++，现在基于递归模板函数inc()和有问题的条件if (n < N - 1)被替换为一个没有额外开销的专门化（实际上是重载）。

如果最终出现了开销，则最终尝试将std::array替换为std::tuple。在这种情况下，std::get是唯一的方式；没有operator []可供选择。类型T重复N次也很奇怪。但是我希望这不是必需的。

进一步的概括是可能的，例如指定每个维度的（编译时）增量步长，甚至指定任意间接数组的维数，例如模拟

a([3 5 0 -2 7], -4:2:20)

使用类似Matlab的语法。

但是这需要更多的工作，如果你喜欢这种方法，我认为你可以接着完成它。

- iavr

---

太棒了，我会尝试并回来。这对于任意 n 维向量都适用，是吗？ - Aurelius

它适用于任何组合的一维数组、n维数组、自定义类、函数、表达式或几乎放在单个 for 循环块内的任何东西。它不保存任何数据，只是计数并提供您可以随意使用的坐标 c[0]、c[1]、...。 - iavr

@Aurelius 当然，一个要求是对底层数组的随机访问。否则，你需要让计数器/迭代器持有数据的引用，并递增底层迭代器而不是整数坐标。这又是另一种泛化。 - iavr

非常出色的答案。使用调试编译，这个解决方案比C循环慢约10％，与-O3编译相同。这大大简化了我的代码。如果您接受啤酒作为付款，请发送给我一个地址;) - Aurelius

Answer 2

在您简单的嵌套for循环情况下，不需要完整的n维迭代器。由于只需要进行一次遍历，因此一个简单的计数器就足够了，可以轻松地自定义如下：

template<typename T, size_t N>
class counter
{
    using A = std::array<T, N>;
    A b, i, e;

public:
    counter(const A& b, const A& e) : b(b), i(b), e(e) { }

    counter& operator++()
    {
        for (size_t n = 0; n < N; ++n)
        {
            if (++i[n] == e[n])
            {
                if (n < N - 1)
                    i[n] = b[n];
            }
            else
                break;
        }

        return *this;
    }

    operator bool() { return i[N - 1] != e[N - 1]; }

    T&       operator[](size_t n)       { return i[n]; }
    const T& operator[](size_t n) const { return i[n]; }
};

接下来，使用这个计数器非常简单：

int main()
{
    constexpr size_t N = 3;
    using A = std::array<int, N>;

    A begin = {{0, -1,  0}};
    A end   = {{3,  1,  4}};

    for (counter<int, N> c(begin, end); c; ++c)
        cout << c << endl;
        // or, cout << c[0] << " " << c[1] << " " << c[3] << endl;
}

假设存在一个操作符<<用于counter。请参见实时示例以获取完整代码。

内部条件if (n < N - 1)考虑到能够检查终止，并且不总是有效检查。对我来说，如何将其分解并不明显，但无论如何，它只发生在我们推进到计数器的下一个“数字”时，而不是在每个增量操作时都进行。

与其使用c[0]，c[1]，c[2]等，如果counter派生自std :: array而不是具有成员i（而b，e保持成员），则更有效地使用std :: get 。这个想法可以扩展到编译时递归实现operator ++（以及operator bool），从而消除其中的for循环，以及上述讨论中的问题检查。在这种情况下，operator [] 将被丢弃。但所有这些都会使counter代码更加晦涩，我只是想强调这个想法。这也会使counter的使用有点更冗长，但这是您为了效率而需要付出的代价。

当然，可以通过扩展counter以获取更多方法和特性来构建完整的n维迭代器。但要使其足够通用可能是一个巨大的任务。

- iavr

---

非常整洁的解决方案，我会在周一处理并回复。您能否编辑std::get的示例？这是性能关键代码；即使是最好的实现，在100多个核心上运行数天，因此任何比C风格循环慢得多的东西都是不可接受的。 - Aurelius

我最初误解了...它绝对需要是一个“完整的n维”（或3、5和6-D）迭代器，因为我们不是在循环遍历所有数组数据，而只是有限的部分。例如，数据可能在一个数组a[nk][nj][ni]中，一些函数将需要遍历所有数据，但大多数函数将在一些子集上操作，如a[1:nk-1][0:nj][0]。 - Aurelius

@Aurelius 这不是问题。 我所说的“全功能”迭代器是指双向或随机访问，类型特征等。 您在此处所说的可以通过适当初始化begin，end 数组进行自定义。 - iavr

@Aurelius 在Matlab和许多其他编程语言中，这也非常容易实现。这是我开发ivl的动力之一，但它已经开发了多年，这就是我说“巨大的任务”的原因。 - iavr

同意；在高性能计算和数值方法方面工作时，缺乏任何足够处理多维数组的方法是使用C++的一个主要缺点，这是一个重大问题。boost::multiarray、boost::ublas、eigen、blitz++、TNT、armadillo等都存在严重的问题。 - Aurelius