Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
577 views
in Technique[技术] by (71.8m points)

templates - Very generic argmax function in C++ wanted

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...