Minimum return value for range

Question

I was wondering if there was a standard function that returns the minimum/maximum of the return values for a given range of elements. Something like this:

std::vector<int> list = { -2, -1, 6, 8, 10 };
auto it = 
    std::find_min_return_value(list.begin(), list.end(), std::abs, std::less<int>);
// it should be the iterator for -1

If there is no such, what is the best approach for a problem like this? My list is long, I really don't want to copy it, and also don't want to call the function whose minimum return value I look for more than once per element. Thanks!

UPDATE:

Based on ForEveR's suggestion to use std::min_element, I made the following benchmarking tests:

std::vector<double> list = { -2, -1, 6, 8, 10 };
auto semi_expensive_test_function = [] (const double& a) { return asin(sin(a)); };
for(int i = 0; i < 10000000; ++i)
{
    auto it = std::min_element(list.begin(), list.end(), 
        [&] (const double& a, const double& b) mutable 
    {
        return(semi_expensive_test_function(a) < semi_expensive_test_function(b));
    });
}

This worked just fine:

./a.out  11.52s user 0.00s system 99% cpu 11.521 total

After modifying the code to use a stateful lambda instead:

for(int i = 0; i < 10000000; ++i)
{
    auto it = std::min_element(list.begin() + 1, list.end(), 
        [&, current_min_value = semi_expensive_test_function(*(list.begin()))] (const double& a, const double& b) mutable 
    {
        double current_value = semi_expensive_test_function(b);
        if(current_value < current_min_value)
        {
            current_min_value = std::move(current_value);
            return true;
        } 
        return false; 
    });
}

This resulted:

./a.out  6.34s user 0.00s system 99% cpu 6.337 total

Using stateful lambdas seems to be the way to go. The question is: is there a more code-compact way to achieve this?

depends, if there is no time complexity constraint, you can std::sort(list.begin(), list.end()) first element is the min and max is the last using the default comparator i.e. Thats nlogn. — Samer Tufail, Feb 16 '17 at 12:46
@Piotr Skotnicki I wanted to type lograthimic that came out wrong. nlogn indeed — Samer Tufail, Feb 16 '17 at 12:49
@nwp How do you use std::min_element and std::max_element to find the minimum and maximum return values of a function performed on a range? — Adam Hunyadi, Feb 16 '17 at 12:50
That's a very specific use case. I doubt that any language's standard library has that function. — molbdnilo, Feb 16 '17 at 12:51
@AdamHunyadi: Without empty vector check: `auto p = std::minmax_element(v.begin(), v.end(), less_abs); auto min = *p.first; auto max = *p.second;` — Jarod42, Feb 16 '17 at 12:52
@PiotrSkotnicki I'm not really concerned about the algorithm complexity, but I have many elements, so I think even creating a sorted list of pointers requires too much memory... (I'm not too sure though) — Adam Hunyadi, Feb 16 '17 at 12:52
@AdamHunyadi `std::minmax_element(list.begin(), list.end(), [] (int a, int b) { return std::abs(a) < std::abs(b); })` — Piotr Skotnicki, Feb 16 '17 at 12:52
std::min_element and std::max_element returns an iterator to that element. derefence them to get the element — Samer Tufail, Feb 16 '17 at 12:52
@PiotrSkotnicki, well... that does the job, but it will perform my calculations twice for each of the elements, not just once... Can you change it to use a stateful lamda? — Adam Hunyadi, Feb 16 '17 at 12:54
@AdamHunyadi that really not a point to rewrite this lambda, until profiler tell you, that it's bottleneck. — ForEveR, Feb 16 '17 at 12:56
@ForEveR it just feels wrong not to be effective when it is simple... — Adam Hunyadi, Feb 16 '17 at 12:59
@AdamHunyadi premature optimization is evil.) Actually, to be statefull it should store array of `abs` values and it will be more unefficient I think. — ForEveR, Feb 16 '17 at 13:00
@ForEveR I thought something like this: `auto it = std::minmax_element(list.begin() + 1, list.end(), [int current_min_value = std::abs(list.begin()) ] (const int& a, const int& b) mutable { if(std::abs(b) < current_min_value) {current_min_value = std::abs(b); return true; } return false; });` — Adam Hunyadi, Feb 16 '17 at 13:16
@AdamHunyadi you sound a bit lost, I suggest you rewrite your question — Piotr Skotnicki, Feb 16 '17 at 13:27
@PiotrSkotnicki I added some possible implementations to the question, is it more clear now? — Adam Hunyadi, Feb 16 '17 at 13:53
Any requirement on memory usage and performance? I only ask because you ask for a compact solution but it seems you also care about performance a lot — greedy52, Feb 16 '17 at 13:55
@XinHuang the list is very long, so I don't want to copy it. Also, I want to call the function of whose minimum return value I look for exactly once for each element. — Adam Hunyadi, Feb 16 '17 at 13:58
@XinHuang It's not sorted, and i can't afford a sorted copy list. That way the problem would be easy. Also I don't really care about algorithmic complexity, but my return value calculation is expensive and so is copying the list. — Adam Hunyadi, Feb 16 '17 at 14:04

score 2 · Answer 1 · answered Feb 16 '17 at 13:06

2

With range-v3, it would be something like:

ranges::min(list, std::less<>{}, [](auto e) { return std::abs(e); });

answered Feb 16 '17 at 13:06

Jarod42

203,559
14
181
302

score 1 · Answer 2 · edited Mar 04 '17 at 05:54

1

Well, assuming Boost is like the standard library nowadays, you might use this:

#include <boost/range/adaptor/transformed.hpp>
#include <algorithm>

int main()
{
    std::vector<int> list = { -2, -1, 6, 8, 10 };
    auto abs_list = list | boost::adaptors::transformed(+[](int v) { return std::abs(v); });
    //                                                  ^ - read http://stackoverflow.com/questions/11872558/using-boost-adaptors-with-c11-lambdas
    auto it =  std::min_element(abs_list.begin(), abs_list.end(), std::less<int>{});
    std::cout << *it;
}

edited Mar 04 '17 at 05:54

Peter Mortensen

30,738
21
105
131

answered Feb 16 '17 at 13:02

PiotrNycz

23,099
7
66
112

Well, this would be good, but my list takes up a lot of memory, so I don't want to copy it :S – Adam Hunyadi Feb 16 '17 at 13:59
No copy at all with my solution. `boost::adaptors::transformed` creates only view. – PiotrNycz Feb 16 '17 at 15:21

score 0 · Accepted Answer · answered Feb 16 '17 at 14:41

If it'll get reused, and to give you another option, you could write your own generic algorithm following std conventions.

template <typename T, typename ForwardIt, typename UnaryFunction, typename Comparator>
ForwardIt find_min_return_value(ForwardIt first, ForwardIt last, UnaryFunction op, Comparator compare)
{
    if (first == last)
        return last;

    ForwardIt smallestItr = first;
    T smallestValue = op(*first);

    for (auto itr = first + 1; itr != last; ++itr)
        {
        T current = op(*itr);
        if (compare(current, smallestValue))
            {
            smallestValue = current;
            smallestItr = itr;
            }
        }

    return smallestItr;
}

Usage is then quite code-compact, and the operation will only be performed once per element:

int main()
{
    std::vector<int> list = { -2, -1, 6, 8, 10 };
    auto it1 = find_min_return_value<int>(list.begin(), list.end(), [](int i){ return std::abs(i); }, std::less<int>());

    std::vector<std::string> strings = { "Lorem", "ipsum", "dolor", "sit", "amet", "consectetur", "adipiscing", "elit" };
    auto it3 = find_min_return_value<size_t>(strings.begin(), strings.end(), [](std::string s){ return s.length(); }, std::less<size_t>());

    std::cout << *it1 << "\n"; // outputs -1
    std::cout << *it3 << "\n"; // outputs sit
}

If you only suspect it may get reused one day it probably won't, and it's then overly complicated, and should then be just a simple function.

`smallestValue = current;` could be `smallestValue = std::move(current);`, `op` can be renamed `project` as you do a projection. (that naming is used in the range library). — Jarod42, Feb 16 '17 at 18:45

Minimum return value for range

3 Answers3