CODEWITHSUNDEEP
c++algorithmc++11c++14
Adam Hunyadi
Adam Hunyadi

Reputation: 1952

Minimum return value for range

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?

Upvotes: 3

Views: 430

Answers (3)

PiotrNycz
PiotrNycz

Reputation: 24412

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;
}

Upvotes: 1

acraig5075
acraig5075

Reputation: 10756

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.

Upvotes: 0

Jarod42
Jarod42

Reputation: 217468

With range-v3, it would be something like:

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

Upvotes: 2

Related Questions