对于需要两个参数的函数,如何在向量上使用std::Range?

我一直在尝试理解新的范围库,并尝试将一些更传统的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中还会添加更多内容。因此,我不知道这是在发布之前无法实现,还是根本不可能实现。

谢谢!


解决方案

您要寻找的算法是组合,但没有相应的范围适配器(既不是在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_productchunk(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部分仍然生成一系列成对的Pointjoin将其减少到一系列成对的Point,然后我们需要unpackComputeDistance

这些都存在于Range-v3中(除了zip_transform有名为zip_with)。但在Range-v3中,您得到的是common_tuple,Boost.HOF不支持,但you can make it work。

相关文章