如何使用 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)创建和额外容器的费用。

问题：

1. 我是否可以重写generate_all_combinations_of()它使用的此类yield或新的std::ranges，以便我可以将其与 STL 算法（例如find_if、any_of、min_element甚至 ）结合使用adjacent_pair？
   这个“生成器”函数的伟大之处在于它易于阅读，所以我希望尽可能保持它的可读性。
   注意：其中一些算法需要break循环。

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

Answer 1

我会关注http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2168r0.pdf谁的发展

如果您正在使用 MSVC，并且可以使用他们的实验/生成器（不确定其他人是否支持它），您可以使用

std::experimental::generator<std::size_t> Generate(std::size_t const end){
   for(std::size_t i = 0; i < end; ++i)
      co_yield i;
}

int main(){
   auto vals = Generate(22);
   auto const result = *std::min_element(std::begin(vals),std::end(vals));
   std::cout <<'\n' << " " << result;
}

在这里，您需要修改生成函数以产生一对/或产生成本

（我的建议是保持事情简单并降低成本）

然后使用 vals 找到 min_cost

范围

根据我能找到的有关范围提案的内容，它基于 std::begin 和 std::end 工作，两者都experimental::generator提供

所以它应该可以工作