Very generic argmax function in C++ wanted

Question

I'm a spoiled Python programmer who is used to calculating the argmax of a collection with respect to some function with

max(collection, key=function)

For example:

l = [1,43,10,17]
a = max(l, key=lambda x: -1 * abs(42 - x))

a then contains 43, the number closest to 42.

Is it possible to write a C++ function which takes any "iterable" and any function and returns the argmax like above? I guess this would involve template parameters, the auto keyword, and range-based iteration, but I was not able to piece it together.

Solution 1

Since @leemes solutions are too many. All are correct, except that none attempts to imitate the Python version in your example, Here is my attempt to imitate that:

Convenient generic argmax-function just like Python version:

template<typename Container, typename Fn>
auto max(Container const & c, Fn && key) -> decltype(*std::begin(c))
{  
    if ( std::begin(c) == std::end(c) ) 
       throw std::invalid_argument("empty container is not allowed.");

    typedef decltype(*std::begin(c)) V;
    auto cmp = [&](V a, V b){ return key(a) < key(b); };
    return *std::max_element(std::begin(c), std::end(c), cmp);
}

And use it as:

std::vector<int> l = {1,43,10,17};
auto a = max(l, [](int x) { return -1 * std::abs(42-x); };

int l[] = {1,43,10,17}; //works with array also!
auto a = max(l, [](int x) { return -1 * std::abs(42-x); };

Note: Unlike the other solution, this max() returns the element itself, not the iterator to the element!

Also note this solution would work for user-defined container also:

namespace test
{
     template<size_t N>
     struct intcollection
     {
         int _data[N];
         int const * begin() const { return _data; }
         int const * end() const { return _data + N; }
     };
}

test::intcollection<4> c{{1,43,10,17}};
auto r = max(c, [](int x) { return -1 * std::abs(42-x); });

See the live demo.

Solution 2

This is a two-step process. Define a function key which should get mapped to the elements, i.e. which is applied before the operation which finds the maximum. Wrap things together in a lambda expression defining the comparison for finding the maximum.

auto key = [](int x){
    return -abs(42 - x);
};

std::max_element(l.begin(), l.end(), [key](int a, int b){
    return key(a) < key(b);
});

Here, we have to capture key which was defined outside the second lambda function. (We could also have defined it inside). You can also put this in one single lambda function. When the 42 should be parameterized from outside the lambda, capture this as a variable:

int x = 42;
std::max_element(l.begin(), l.end(), [x](int a, int b){
    return -abs(x - a) < -abs(x - b);
});

Note that std::max_element returns an iterator. To access the value / a reference to it, prepend it with *:

int x = 42;
auto nearest = std::min_element(l.begin(), l.end(), [x](int a, int b){
    return abs(x - a) < abs(x - b);
});
std::cout << "Nearest to " << x << ": " << *nearest << std::endl;

You can nicely wrap this in a generic find_nearest function:

template<typename Iter>
Iter find_nearest(Iter begin, Iter end,
                  const typename std::iterator_traits<Iter>::value_type & value)
{
    typedef typename std::iterator_traits<Iter>::value_type T;
    return std::min_element(begin, end, [&value](const T& a, const T& b){
        return abs(value - a) < abs(value - b);
    });
}

auto a = find_nearest(l.begin(), l.end(), 42);
std::cout << *a << std::endl;

Live demo find_nearest: http://ideone.com/g7dMYI

---

A higher-order function similar to the argmax function in your question might look like this:

template<typename Iter, typename Function>
Iter argmax(Iter begin, Iter end, Function f)
{
    typedef typename std::iterator_traits<Iter>::value_type T;
    return std::min_element(begin, end, [&f](const T& a, const T& b){
        return f(a) < f(b);
    });
}

You can invoke this with the following code, having exactly the lambda function from your question:

auto a = argmax(l.begin(), l.end(), [](int x) { return -1 * abs(42 - x); });
std::cout << *a << std::endl;

Live demo argmax: http://ideone.com/HxLMap

---

The only remaining difference now is that this argmax function uses an iterator-based interface, which corresponds to the design of the C++ standard algorithms (<algorithm>). It's always a good idea to adapt your own coding style to the tools you're using.

If you want a container-based interface which returns the value directly, Nawaz provided a nice solution which requires the decltype-feature to correctly specify the return type. I decided to keep my version this way, so people can see the both alternative interface designs.

Comments

[clstaudt]

Nice answer, but the "find nearest" problem was just an example for the use of max(collection, key=function), not the actual problem to be solved.

[leemes]

@cls I'll add a generic higher-order function solving the argmax problem.

[clstaudt]

What is the -> operator here and decltype?

[Nawaz]

@cls: It is called trailing-return-type. It is C++11 feature. :-)

[leemes]

@cls Here you go. The .begin() and .end() thing are typical for C++ algorithms, so I adopted the C++ style.

[Nawaz]

@cls: See this Alternative function syntax which uses trailing-return-type.

[Nawaz]

@cls: And decltype deduces the type of the expression. So you can write decltype(0) age = 40; which is same as int age = 40;. In this case, it doesn't make much sense, but sometimes it is needed like in my solution.

[Nawaz]

@cls: Also note that this solution returns the iterator to the element rather than element itself.

[Yakk - Adam Nevraumont]

If you are gonna use std::begin, do it with ADL! So people can write custom containers. :) Second, note that your code executes undefined behavior on empty containers, which I doubt the python version did.

[GManNickG]

You should use typedef std::iterator_traits<Iter>::value_type T; to be correct, which is specialized for pointer iterators that don't have an inner-type value_type. Otherwise this answer's solution is the right way to go.

[leemes]

@GManNickG Ok I did't know this, thanks. No typename in this case?

[GManNickG]

@leemes: Yeah you need typename, my mistake. :)

[leemes]

@Yakk Hugh, why is this? (UB for empty containers)

[Yakk - Adam Nevraumont]

std::max_element returns end if passed an empty container, I think.

[Nawaz]

@Yakk: Fixed the UB. Also, std::begin(c) would call the custom container .begin() internally. So that is not a problem.

[Yakk - Adam Nevraumont]

On the contrary @Nawaz: namespace bar{struct foo{int data[10];};int*begin(foo&f){return &f.data[0];}int*end(foo&f){return begin(f)+10;}}int main(){bar::foo f;for(auto x:f){std::cout<<x<<"\n";}} -- no foo::begin, yet adl-based begin lookup works, while std::begin does not. Calling std::begin(c) directly is not quite the "right" thing to do, but it is close. Replace call to std::begin(c); with using std::begin; begin(c); and you get ADL-based begin lookup. It is a small problem, not a big one.

[Nawaz]

@Yakk: How would you write this -> decltype(*std::begin(c)) to enable ADL, without writing using std::begin outside the function? Adding an ADL solution to this post would pollute it, which I don't want to do, because it is not required. I want to keep it simple and to the point which works for most containers, as long as it has member functions begin() and end().

[Yakk - Adam Nevraumont]

namespace aux{using std::begin;template<typename C>auto adl_begin(C&&c)->decltype(begin(std::forward(c)));}, then ->decltype(*aux::adl_begin(c)) is a technique that works.