对于需要两个参数的函数，如何在向量上使用 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_product 和 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) 对所有 x 和 (x, y) 和 (y, x)，两者都不你要。当我们按 points.size() 对它进行分块时（产生 N 长度范围 N），然后我们重复删除一个稳定增加（iota(1)）的元素数量......所以只有一个来自第一个块（包含第一个元素两次的对），然后来自第二个块的两个（(points[1], points[0]) 和 (points[1], points[1]) 元素），等等

zip_transform 部分仍然产生一系列 Point 对，join 将其减少到 Point 对的范围，然后我们需要 unpack 变成 ComputeDistance.

这一切都存在于 range-v3 中（除了 zip_transform 那里被命名为 zip_with）。但是在 range-v3 中，你得到 common_tuple，Boost.HOF 不支持，但是 you can make it work.

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

How to use std::ranges on a vector for a function that needs two arguments?

c++

functional-programming

c++20

std-ranges