arg_min and arg_max

[aken...@gmail.com]

Hello all,

I'd like to suggest a small addition to the standard library in the form of arg min and arg max functions.  It's the kind of loop we've probably all written hundreds of times: scan through a container, transform each element through some function, and find the element that produces the highest or lowest result.  Among other things, I've written this for finding the closest point in a set, the closest color in palette, the best individual in a genetic algorithm, and the next edge to add to a minimum spanning tree.

I'm tired of writing this loop out each time.  Regular generic programming can capture the basic idiom, and anonymous functions make it easy to express the transformation step.  In short, I'd like to suggest adding a function like this:

template<class ForwardIterator, class UnaryOperation>
ForwardIterator arg_min(ForwardIterator first, ForwardIterator last,
                        UnaryOperation op)
{
    if (first == last)
        return last;
    auto arg = first;
    auto minima = op(*first++);
    for (; first != last; ++first) {
        auto value = op(*first);
        if (value < minima) {
            arg = first;
            minima = value;
        }
    }
    return arg;
}

to the algorithm section of the library standard, along with the anologous arg_max() function.  As an example of its use, mapping a color to the nearest palette entry could then be as simple as:

struct rgb { float r, g, b; };
rgb map_to_palette(rgb const from, vector<rgb> const &palette)
{
    assert(!palette.empty());
    return *arg_min(begin(palette), end(palette), [&](rgb to) {
        return ((to.r - from.r) * (to.r - from.r) +
                (to.g - from.g) * (to.g - from.g) +
                (to.b - from.b) * (to.b - from.b));
    });
}

I apologize if this has been proposed before; my searches failed to find anything.  Thanks for your thoughts and consideration.

Cheers,
- Andrew Kensler

[Erich Keane]

Perhaps I'm reading this wrong, but it seems that it does the same thing as std::min_element.

[David Krauss]

On 2015–07–30, at 1:07 AM, Erich Keane <erich...@verizon.net> wrote:

Perhaps I'm reading this wrong, but it seems that it does the same thing as std::min_element.

Sort-of. Doing it with min_element requires performing the transformation inside the comparator, which means running it twice as many times as necessary (or implementing memoization or caching).

[aken...@gmail.com]

[Dave: exactly!  Here was what I was about to reply to Erich]

There are some similarities to min_element(), but also some important differences -- namely that the elements are mapped or transformed through a function.  If I were to rewrite my example of the color matching function to use min_element(), I could go about it in a couple of ways though none of them are great:

1. Give min_element() a comparator that computes the color difference to the input for both the left and right parameters and returns the lesser.  E.g.,
   
   

1. rgb map_to_palette(rgb const from, vector<rgb> const &palette)
   {
       assert(!palette.empty());

1. 
       auto diff = [&](rgb to) {

1. 
           return ((to.r - from.r) * (to.r - from.r) +
                   (to.g - from.g) * (to.g - from.g) +
                   (to.b - from.b) * (to.b - from.b));

1. 
       };
       return *min_element(begin(palette), end(palette), [&](rgb left, rgb right) {
               return diff(left) < diff(right);
       });
   }
   
   
   This works, but now the mapping function is called 2N times instead of 1N.  That's not so bad in this case, but may be problematic if the function is stateful or particularly expensive to compute.  (For example, I've written palette mapping code using the perceptual CIEDE2000 color-difference formula.)
   
   
2. Use a min_element() with a comparator that memoizes the mappings of its last pair of inputs.  This gets it back down to 1N invocation of the mapping function but now the comparator has to carry around a two-element cache and check its inputs against that.  This is clumsy and verbose enough that one might as well write the usual for-loop instead.

On the other hand, arg_min() is sufficiently powerful that one can express min_element() in terms of it by passing in a simple identity function as the operation.

With that in mind, I did consider suggesting these as new overloads of min_element() and max_element().  However, I believe that disambiguating whether the function passed is a comparator or a unary op requires either either arbitrarily re-ordering the parameters or else using an empty tag struct (similar to piecewise_constructor for tuples).  Neither one strikes me as a particularly great option and arg_min() and arg_max() at least have the advantage of implying the mapping.

Cheers,
- Andrew

[S.B.]

在 2015年7月29日星期三 UTC+8下午3:49:26，aken...@gmail.com写道：

See discussion on reddit.

[Mark A. Gibbs]

I saw this discussion on Reddit a while back, and at the time it struck me that - that rather than another algorithm, or mucking around with max_element's interface - the smart way to solve this problem would be a "transforming iterator". Like boost::transform_iterator:

auto p = std::max_element(
  boost::make_transform_iterator(first, func),
  boost::make_transform_iterator(last, func)).base();


For ranges you'd use the boost::adaptors::transformed adaptor (which will surely have an analogue in C++17 ranges):

auto p = boost::max_element(data | boost::adaptors::transformed(func));

Would this solve the problem?

[Magnus Fromreide]

On Thu, Jul 30, 2015 at 03:03:21PM -0700, Mark A. Gibbs wrote:
> I saw this discussion on Reddit a while back, and at the time it struck me
> that - that rather than another algorithm, or mucking around with
> max_element's interface - the smart way to solve this problem would be a
> "transforming iterator".

While I agree in principle the transform_iterator version isn't enough.

A typical implementation of max_element is

template <class ForwardIterator>
ForwardIterator max_element ( ForwardIterator first, ForwardIterator last )
{
if (first==last) return last;
ForwardIterator largest = first;

while (++first!=last)
if (*largest<*first)
largest=first;
return largest;
}

and using a transforming iterator wouldn't reduce the number of times
func gets called. What is needed is two wrappers, first the transforming
iterator and secondly a caching iterator that stores the value from the
dereference of the wrapped iterator and returns the cached value on
subsequent dereferences.

So, a caching_iterator<transform_iterator<first, func>> should be
enough to call func no more than N times.

/MF

[Mark A. Gibbs]

On Friday, 31 July 2015 01:30:19 UTC-4, Magnus Fromreide wrote:

So, a caching_iterator<transform_iterator<first, func>> should be
enough to call func no more than N times.

Ah, I assumed that transform iterators already cached, like istream_iterator does, but in hindsight that wouldn't make sense in this context.

At any rate, it seems to me that it would probably be more useful to add transform iterators and caching iterators - along with other iterator or range adaptors - rather than trying to add a bunch more functions. Adaptors compose, unlike functions. Arguably we already have a bunch of algorithm functions that are probably unnecessary - like std::transform is just std::copy with transform iterators. And if you use transform iterators with std::copy_if, you get the missing "transform_if" algorithm.