C++ Logo


Advanced search

Re: arg_min and arg_max algorithms

From: Jason Beach <jason.m.beach_at_[hidden]>
Date: Tue, 15 Dec 2020 22:39:30 -0500
Ah--interesting. I wasn't aware of that. It looks like the projection
function argument is only available on std::ranges::min_element and not
std::min_element. Using this though actually results in 2N-1 unary op calls
(https://godbolt.org/z/YjPeoq), which I would be reluctant to leave on the
table, but that's probably more a reflection of my OCD tendencies than of
profiled data.

Thanks for your reply.

On Tue, Dec 15, 2020 at 9:24 PM Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>

> On Tue, Dec 15, 2020 at 8:00 PM Jason Beach via Std-Proposals <
> std-proposals_at_[hidden]> wrote:
>> Hi,
>> I recently wrote a simple particle filter for a robotics project and
>> needed an arg_min function. This function returns the argument that
>> results in a minimum value of a function (as opposed to the minimum
>> argument value itself https://en.wikipedia.org/wiki/Arg_max). In my
>> case, from a list of points I needed to find the point that was closest to
>> another given point.
>> I based my implementation on the examples given on cppreference for
>> std::transform and std::min_element. The major advantage of a combined
>> algorithm as opposed to using std::transform and std::min_element
>> individually is that it cuts the number of function evaluations in half by
>> caching the result.
> This smells a lot like std::ranges::min_element with a projection:
> https://godbolt.org/z/9fE7r8
> auto arg_min(auto first, auto last, auto unary_op) {
> auto it = std::ranges::min_element(first, last, std::less(), unary_op);
> return std::make_pair(it, it == last ? std::nullopt :
> std::make_optional(unary_op(*it)));
> }
> I admit that my version does one more evaluation of unary_op(*it) than
> yours does; but maybe that's acceptable?
> –Arthur

Received on 2020-12-15 21:40:13