如何在需要两个参数的函数的向量上使用 std::ranges ？

Question

我一直在尝试了解新的范围库，并尝试将一些更传统的 for 循环转换为函数代码。cppreference给出的示例代码非常简单易读。但是，我不确定如何将范围应用于点向量，该点向量需要查看、计算并比较每个 x 和 y 值，并在最后比较最大距离。

struct Point
{
  double x;
  double y;
}

double ComputeDistance(const Point& p1, const Point& p2)
{
  return std::hypot(p1.x - p2.x, p1.y - p2.y);
}

double GetMaxDistance(const std::vector<Point>& points)
{
  double maxDistance = 0.0;

  for (int i = 0; i < points.size(); ++i)
  {
    for(int j = i; j < points.size(); ++j)
    {
      maxDistance = std::max(maxDistance, ComputeDistance(points.at(i),points.at(j)));
    }
  }
  return maxDistance;
}

GetMaxDistance是我想尝试清理并应用范围的代码。我认为这就像做类似的事情一样简单：

double GetMaxDistance(const std::vector<Point>& points)
{
  auto result = points | std::views::tranform(ComputeDistance);
  return static_cast<double>(result);
}

然后我意识到这是不正确的，因为我没有将任何值传递给函数。所以我认为：

double GetMaxDistance(const std::vector<Point>& points)
{
  for(auto point : points | std::views::transform(ComputeDistance)) 
    // get the max distance somehow and return it?
    // Do I add another for(auto nextPoint : points) here and drop the first item?
}

但后来我意识到我将该函数应用于每一点，但不是它旁边的点，而且这也不起作用，因为我仍然只将一个参数传递给函数ComputeDistance。由于我需要计算向量中所有点的距离，因此我必须将每个点相互比较并进行计算。将其保留为n^2算法。我并不是想打败它n^2，我只是想知道是否有一种方法可以使这种传统的 for 循环采用现代的函数式方法。

这让我们回到了标题。std::ranges这种情况我该如何申请？是否有可能利用标准目前给我们的东西来做？我知道 C++23 中还需要添加更多内容。所以我不知道在发布之前这是否无法实现，或者是否根本不可能做到。

谢谢！

Answer 1

您正在寻找的算法是组合 - 但没有范围适配器（C++20 和 range-v3 中都没有，C++23 中也没有）。

但是，在这种情况下，我们可以使用通常称为平面地图的算法手动构造它：

inline constexpr auto flat_map = [](auto f){
    return std::views::transform(f) | std::views::join;
};

我们可以使用如下：

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    return std::ranges::max(
        rv::iota(0u, points.size())
        | flat_map([&](size_t i){
            return rv::iota(i+1, points.size())
                 | rv::transform([&](size_t j){
                     return ComputeDistance(points[i], points[j]);
                 });
          }));
}

外层iota是我们的第一个循环。然后对于每个i，我们从开始得到一个序列i+1来获得我们的j. 然后对于每个(i,j)我们计算ComputeDistance。

或者，如果您想要transform顶层（可以说更干净）：

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    return std::ranges::max(
        rv::iota(0u, points.size())
        | flat_map([&](size_t i){
            return rv::iota(i+1, points.size())
                 | rv::transform([&](size_t j){
                     return std::pair(i, j);
                 });
          })
        | rv::transform([&](auto p){
            return ComputeDistance(points[p.first], points[p.second]);
          }));
}

甚至（此版本生成一系列对 的引用Point，以允许更直接的transform）：

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    namespace hof = boost::hof;

    return std::ranges::max(
        rv::iota(0u, points.size())
        | flat_map([&](size_t i){
            return rv::iota(i+1, points.size())
                 | rv::transform([&](size_t j){
                     return std::make_pair(
                         std::ref(points[i]),
                         std::ref(points[j]));
                 });
          })
        | rv::transform(hof::unpack(ComputeDistance)));
}

这些基本上都做同样的事情，只是ComputeDistance函数在哪里以及如何调用的问题。

C++23 将添加cartesian_productand chunk（range-v3 现在有它们），以及最近添加的zip_transform，这也将允许：

double GetMaxDistance(const std::vector<Point>& points)
{
    namespace rv = std::views;
    namespace hof = boost::hof;

    return std::ranges::max(
        rv::zip_transform(
           rv::drop,
           rv::cartesian_product(points, points)
           | rv::chunk(points.size()),
           rv::iota(1))
        | rv::join
        | rv::transform(hof::unpack(ComputeDistance))
    );
}

cartesian_product其本身会给你所有对 - 其中都包括(x, x)for allx以及两者(x, y)和(y, x)，这两个都是你想要的。当我们将其分块points.size()（产生Nlength 的范围N）时，我们会重复删除不断增加的 ( iota(1)) 个元素...因此，仅从第一个块中删除一个（包含第一个元素两次的对），然后从第二个块中删除两个块（(points[1], points[0])和(points[1], points[1])元素）等。

该zip_transform部分仍然会产生一系列 的对的块Point，然后join将其减少到一系列的 的对Point，然后我们需要将其unpack放入 中ComputeDistance。

这一切都存在于 range-v3 中（除了zip_transformname zip_with）。但在 range-v3 中，你会得到common_tupleBoost.HOF 不支持的 ，但你可以让它工作。