使用基于范围的for循环替换多维for循环

Question

我有一个Vec3类。 如何替换像这样的循环是最好的方法：

for (int x = 20; x < 25; x++)
    for (int y = 40; y < 45; y++)
        for (int z = 2; z < 4; z++) doStuff({x,y,z});

使用类似以下的方式：

for(Vec3 v: Vec3range({20,40,2}, {25,45,4}))
    doStuff(v);

没有任何运行时成本吗？

- phiresky

---

请查看以下问题及其答案：TMP：如何将向量的笛卡尔积泛化？，循环遍历模板参数/类型和在搜索参数空间时避免嵌套for循环。 - Constructor

Vec3range需要是一个自定义容器类型（具有begin、end等），并且需要有一个自定义迭代器。但是，由于这需要中间类具有可变的内部变量，因此这将阻止编译器能够展开循环，因此在长期运行中可能会变得更慢。而且，老实说，在我看来它也不那么易读。 - IdeaHat

我支持@MadScienceDreams的观点——向量通常不以这种方式操作，因此在没有解释的情况下，这种方法（虽然更为简洁）并没有太多意义。在我看来，最好的选择是调整代码格式，如果您不喜欢循环的读取方式和/或经常需要这种循环并且不喜欢打很多字，可以创建一个宏来实现。 - Conduit

我刚刚写了一个可行的解决方案，但是它真的很丑。而且根据@MadScienceDreams的说法，它肯定会更慢。慢+丑？听起来像个赢家！ - Barry

@Conduit 这是用于在3D地图中创建元素的，有很多类似这样的循环来创建地板等。 （[github]（https://github.com/phiresky/noeuclid/）） - phiresky

Answer 1

为此，我在我的函数库fn中编写了一个迭代和组合适配器：

#include <fn.h>
#include <iostream>

int main() {
    using std; using fn;

    for (auto &&values : combine(seq(20,25), seq(40,45), seq(2,4))) {
        int x, y, z; 
        tie(x, y, z) = values;
        cout << x << ", " << y << ", " << z << "\n";
        // or in your case: doStuff({x, y, z});
    }
}

输出：

20, 40, 2
20, 40, 3
20, 41, 2
20, 41, 3
...
24, 43, 2
24, 43, 3
24, 44, 2
24, 44, 3

在这里，seq(a, b) 返回一个隐式范围，它通过值 [a, b)（即第一个是包含的，第二个是不包含的）进行迭代。（第三个参数可以指定步长，并且更复杂的替代方案存在以便更好地控制迭代。）

函数 combine(ranges...) 返回一个隐式范围，它遍历给定范围的所有组合（其中第一个被认为是“最重要”的，类似于你的“最外层”循环）。它的迭代器解引用为一个持有当前组合的 std::tuple。

然后，在循环体中将此元组绑定到某些变量上。（不幸的是，对于基于范围的 for 循环，没有像 for(tie(auto x, auto y, auto z) : ...) 这样的“自动绑定”语法。）

---

实现：

seq()

那很简单：它是一个返回适配器对象的函数，该对象具有 begin() 和 end() 函数。它们返回一个自定义迭代器，该迭代器在 operator++ 中增加当前值并在 operator* 中返回它。

combine()

这更有趣：它返回一个适配器对象，该对象在元组成员中保存作为参数提供给 combine 的范围。此适配器的迭代器在元组成员中保持对包装范围的迭代器三次引用：当前位置、开始和结束，您很快就会明白原因。

迭代器的 operator++ 很可能是最有趣的：它使用可变参数模板递归实现，在 variadic_ops.h，va_next_combination() 中给出迭代器三元组（对于每个范围，当前、开始和结束）。

// base case
inline bool va_next_combination() {
    return true;
}

// recursive case
template<typename Head, typename ...Tail>
inline bool va_next_combination(std::tuple<Head&,Head&,Head&> && curr_and_begin_and_end, std::tuple<Tail&,Tail&,Tail&> &&...t) {
    // advance the "tail" to its next combination and check if it had an overflow
    if (va_next_combination(std::forward<std::tuple<Tail&,Tail&,Tail&>>(t)...)) {
        // advance the "head" iterator
        ++std::get<0>(curr_and_begin_and_end);
        // check if the "head" just overflow
        bool at_end = (std::get<0>(curr_and_begin_and_end) == std::get<2>(curr_and_begin_and_end));
        // if it did, put it back to the beginning and report the overflow
        if (at_end) std::get<0>(curr_and_begin_and_end) = std::get<1>(curr_and_begin_and_end);
        return at_end;
    } else {
        // "tail" didn't overflow, so we do nothing and no overflow should be reported
        return false;
    }
}

从集合中最右边的迭代器开始，它会递增迭代器。如果它刚到达范围的末尾，它将把它作为递归函数的返回值报告。下一个迭代器检查该值，如果它本身需要前进（否则不需要），以及“重置”右侧的迭代器（即“环绕”其溢出），最后将相同的信息报告给左侧的迭代器。

这基本上就是机械计数器的工作原理，如果您从最深的递归级别中的“if”条件开始。

- leemes

Answer 2

template<size_t N>
using indexes=std::array<size_t,N>;

template<size_t N>
void advance( indexes<N>& in, indexes<N-1> const& limit, size_t amt=1 );

该函数查找距离当前位置amt个索引的元素，当到达限制时会循环。

然后编写一个范围对象。它存储了限制和两个迭代器b和e。begin 函数返回 b，end 函数返回 e。

这些迭代器有指向它们所来自的范围的指针和值数组。它们通过上面的next方法实现自增运算符++。编写通常的前向迭代器样板代码。

您的函数可能应该是：

template<size_t N>
multi_range_t<N> multi_range( indexes<N> start, indexes<N> finish );

这需要您通过N。

最后为Vec3从std::array<3,T>编写一个拷贝构造函数。

您可能可以通过将其变成3而不是N使它变得更加容易，但只是一点点。

- Yakk - Adam Nevraumont

Answer 3

这是我能做到的最简单实现方式：

#include <iostream>
#include <tuple>

using namespace std;

using tuple_3d = tuple<int, int, int>;

struct range_3d;

struct range_3d_iterator
{
  const range_3d& c;
  tuple_3d i;

  bool operator!=(const range_3d_iterator& other)
  { return get<0>(i) != get<0>(other.i) && get<1>(i) != get<1>(other.i) && get<2>(i) != get<2>(other.i); }

  tuple_3d operator*() const
  { return make_tuple(get<0>(i), get<1>(i), get<2>(i)); }

  const range_3d_iterator& operator++();
};

struct range_3d
{
  tuple_3d s;
  tuple_3d e;

  range_3d_iterator begin() const
  { return { *this, s }; }

  range_3d_iterator end() const
  { return { *this, e }; }
};

const range_3d_iterator& range_3d_iterator::operator++()
{
  ++get<2>(i);
  if (get<2>(i) == get<2>(c.e))
  {
    get<2>(i) = get<2>(c.s);
    ++get<1>(i);
    if (get<1>(i) == get<1>(c.e))
    {
      get<1>(i) = get<1>(c.s);
      ++get<0>(i);
    }
  }
  return *this;
}

int main(void)
{
  for (auto&& v : range_3d{ make_tuple(20, 40, 2), make_tuple(25, 45, 4) })
    cout << get<0>(v) << ' ' << get<1>(v) << ' ' << get<2>(v) << endl;  
}

命名有点糟糕，但是概念很简单。 range_3d 是一个简单的类，支持begin()，end()获取循环范围，然后“智能”的部分在于range_3d_iterator，它将迭代元组。鉴于我在这里使用元组的方式，将其扩展到任意维度是微不足道的...

老实说，原始的for循环非常清晰... 在我看来！

- Nim

---

谢谢！这个很好用。不确定是使用这个还是保持原来的循环，或者写一个宏。 - phiresky