How to compose generators with STL algorithms

Question

I have an algorithm which generates combinations from entries of a container and I want to find the combination which minimizes a cost function:

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 );

Unfortunately, get_pair_with_minimum_cost() does 2 jobs:

• generates the combinations
• gets the minimum element

I could break them in two functions, like:

• the generator:

  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]));
          }
      }
  }
  

• and then use std::min_element on the output of the generator, i.e.

  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);
  

but I do not want the pay the cost of creating and extra container with temporary data (all_combinations).

Questions:

1. Can I rewrite the generate_all_combinations_of() such that it uses yield or the new std::ranges in such a way that I can combine it with STL algorithms such as find_if, any_of, min_element or even adjacent_pair ?
   The great thing about this 'generator' function is that it is easy to read, so I would like to keep it as readable as possible.
   NB: some of these algorithms need to break the loop.

2. What is the official name of combining entries this way? It this the combinations used in 'bubble-sort'.

Answer 1

Here's how I would write the function in c++20, using range views and algorithms so that there isn't a separate container that stores the intermediate results:

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);
}

Here's a demo.

Note that the solution doesn't compare the cost between same elements, since the cost function example you showed would have a trivial result of 0. For a cost function that doesn't return 0, you can adapt the solution to generate a range from i instead of i + 1. Also, if the cost function is not symmetric, make that range start from 0 instead of i.

Also, this function has UB if you call it with an empty range, so you should check for that as well.