c++ - 如何使用 STL 算法组合生成器

Question

我有一个从容器条目生成组合的算法，我想找到最小化成本函数的组合:

struct Vec { double x; double y; };

double cost( Vec a, Vec b ) {
    double dx = a.x - b.x; 
    double dy = a.y - b.y; 
    return dx*dx + dy*dy;
}


pair<Vec,Vec> get_pair_with_minimum_cost ( vector<Vec> inp, double (*cost_fun)(Vec,Vec) )
{
    pair<Vec,Vec> result;
    double min_cost = FLT_MAX;

    size_t sz = inp.size();
    for(size_t i=0; i<sz; i++) {
        for (size_t j=i; j<sz; j++) {
            double cost = cost_fun(inp[i], inp[j]);
            if (cost < min_cost) {
                min_cost = cost;
                result = make_pair(inp[i], inp[j]);
            }
        }
    }

    return result;
}

vector <Vec> inp = {....};

auto best_pair = get_pair_with_minimum_cost ( inp, cost );

不幸的是， get_pair_with_minimum_cost()做 2 个工作:

生成组合

获取最小元素

我可以将它们分解为两个函数，例如:

发电机:

template <class Func>
void generate_all_combinations_of( vector<Vec> inp, Func fun )
{
    size_t sz = inp.size();
    for(size_t i=0; i<sz; i++) {
        for (size_t j=i; j<sz; j++) {
            fun(make_pair(inp[i], inp[j]));
        }
    }
}

然后使用 std::min_element在生成器的输出上，即

vector<Vec> inp = {....};
vector<pair<Vec,Vec>> all_combinations;
generate_all_combinations_of(inp, [&](vector<pair<Vec,Vec>> o){all_combinations.push_back(o); } );
auto best_pair = *min_element(all_combinations.begin(), all_combinations.end(), cost);

但我不想支付使用临时数据( all_combinations )创建和额外容器的费用。
问题:

我可以重写generate_all_combinations_of()这样它使用 yield或新的 std::ranges这样我就可以将它与 STL 算法(例如 find_if)结合起来。 , any_of , min_element甚至 adjacent_pair ?
这个“生成器”函数的伟大之处在于它易于阅读，所以我想尽可能保持它的可读性。
注意:其中一些算法需要break循环。

以这种方式组合条目的正式名称是什么？
这就是“冒泡排序”中使用的组合。

Answer 1

下面是我将如何在 c++20 中编写函数，使用范围 View 和算法，以便没有单独的容器来存储中间结果:

double get_minimum_cost(auto const & inp)
{
  namespace rs = std::ranges;
  namespace rv = std::ranges::views;

  // for each i compute the minimum cost for all j's  
  auto min_cost_from_i = [&](auto i) 
  {

    auto costs_from_i = rv::iota(i + 1, inp.size())
                      | rv::transform([&](auto j) 
                        { 
                          return cost(inp[i], inp[j]); 
                        });

    return *rs::min_element(costs_from_i);
  };

  // compute min costs for all i's
  auto all_costs = rv::iota(0u, inp.size())
                 | rv::transform(min_cost_from_i);

  return *rs::min_element(all_costs);
}

这是一个 demo .
请注意，该解决方案不会比较相同元素之间的成本，因为 cost您展示的函数示例的结果是 0。对于不返回 0 的成本函数，您可以调整解决方案以生成范围从 i而不是 i + 1 .另外，如果 cost函数不对称，使该范围从 0 开始而不是 i .
此外，如果您使用空范围调用此函数，则该函数具有 UB，因此您也应该检查它。