Efficient Argmin in C++11

Question

I have a vector of elements, and I can calculate a single number from each of the elements using a very expensive function. I would like the element which maps to the lowest of these numbers. I know how to do this in C++03: *

Foo get_lowest(const std::vector<Foo> &foos) {
  double lowest_so_far = std::numeric_limits<double>::max();
  std::vector<Foo>::iterator best;
  for(std::vector<Foo>::iterator i = foos.begin(); i != foos.end(); i++) {
    const double curr_val = i->bar();
     if( curr_val < lowest_so_far ) { 
       best = i;
       lowest_so_far = curr_val
     }
  }

  return *i;
}

I could also do this using std::min_element, except the naive way of doing things (calling Foo::bar and returning a boolean from <) calls Foo::bar more times than the code I posted above. I could pre-calculate each of these values and then use std::min_element, except that this code is more complicated than the above code.

In Going Native, someone (Sean Parent, thanks SChepurin!) said that a good style guide for modern C++ is to avoid "raw loops". Is there a more C++11 idiomatic way of doing what I want?

* I just typed this into the window, I didn't even try to compile it.

Answer 1

This is an interesting one: determining a property based on an expensive operation at a position is not immediately supported. Using a version of std::min_element() which would do the computations in each call to the binary predicate isn't quite the way to go: you don't want to recompute the value of the current known minimum. It may be warranted to write a custom loop.

In general, the STL algorithms assume that getting the value at a position is fairly cheap. Likewise, the iterator operations (advance, test, dereference) should be fast. The somewhat costly operation is assumed to be the comparison in this example. When uses match these use caes, STL algorithms are probably indeed a better option, e.g., because they can do all kinds of crazy things (loop unrolling, memory operations, etc.). I certainly agree with Herb's statement to use what to do rather than how to do it but for your case I don't think the STL algorithms can do it efficiently.

Answer 2

If calling Foo::bar is really such a big deal in terms of performance (see juancho's note to profiling), I'd first calculate a vector of the bar values and then search for the min_index there:

Foo const& get_lowest(const std::vector<Foo> &foos) {
  typedef decltype(foos[0].bar()) BarVal;

  std::vector<BarVal> barValues;
  barValues.reserve(foos.size());

  std::transform(begin(foos), end(foos), std::back_inserter(barValues), [](Foo const& f) {
    return f.bar(); 
  });

  auto barPos = std::min_element(begin(barValues), end(barValues));
  auto fooPos = begin(foos) + std::distance(begin(barValues), barPos);
  return *fooPos;
}

Update: another approach would be using std::accumulate with a lambda to do exactly what you handcoded, but that would involve housekeeping and rely on side effecets of the lambda, making the code less comprehensible.