max over c++ array with function call

Question

I have a list of obj objects which each have an eval() method, returning a double. I'd like to get the maximum value of all of these. So far, I've always done

double maxval = std::numeric_limits<double>::lowest();
for (const auto &obj: objs) {
  maxval = std::max(maxval, obj->eval());
}

I was wondering if there's a more elegant solution where you don't have to set the initial value -inf, something like Python's

max_value = max(obj.eval() for obj in objs)

perhaps. Note than eval() may be expensive, so I only want to eval() once per obj.

Any hints? Bonus points for readability.

So the usual practice to use the value of the first one you visit is not an option for you? Why? — Yunnosch
– Yunnosch, Commented Jun 4, 2021 at 13:47

lubgr · Accepted Answer · 2021-06-04 15:52:52Z

4

Some <ranges> nice things (C++20 only):

#include <ranges>

const auto maxval = std::ranges::max_element(objs, std::less<>{}, &ObjType::eval);

if (maxval != objs.cend())
    doStuffWith(*maxval);

where ObjType is the type of the sequence elements. The last check could also be on the size of the container as maxval would certainly be a dereferencable iterator when the sequence isn't empty, e.g.

if (!objs.empty()) ; // ...

Note however that as @NathanOliver has pointed out, this invokes eval() 2N-2 times. Here is a custom template that would call eval() exactly N times:

#include <optional>
#include <functional>
#include <type_traits>

template <class Range, class Cmp = std::less<>, class Proj = std::identity>
auto maxValue(const Range& rng, Cmp pred = Cmp{}, Proj p = Proj{})
{
    using std::begin;
    using std::end;
    using ValueType = std::remove_cvref_t<std::invoke_result_t<Proj,
        decltype(*begin(rng))>>;

    auto first = begin(rng);
    const auto last = end(rng);

    if (first == last)
        return std::optional<ValueType>{};

    auto result = std::invoke(p, *first);

    for (++first; first != last; ++first)
        result = std::max(std::invoke(p, *first), result, pred);

    return std::optional{result};
}

It doesn't return an iterator, but the resulting value - wrapped into a std::optional in case the range is empty (then the result is std::nullopt). Usage for a type Test with member function Test::eval() would be like this:

const auto max = maxValue(myContainer, std::less<>{}, &Test::eval);

Second and third argument have sensible defaults, so for primitive types and the like they could be left out.

edited Jun 4, 2021 at 15:52

answered Jun 4, 2021 at 13:53

lubgr

38.6k3 gold badges71 silver badges119 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Nico Schlömer Over a year ago

How often is eval called per obj?

lubgr Over a year ago

It's a linear algorithm, so once per object.

Nico Schlömer Over a year ago

Linear complexity could also mean k times per object, e.g., twice.

NathanOliver Over a year ago

Wouldn't this still have two calls to eval per element? ie, e1 cmp e2 is called and then e2 cmp e3 ... so only the first and last element get cmp called once on them.

NathanOliver Over a year ago

Looks like it is called 2N-2 times: wandbox.org/permlink/e260qaoY4RnqjuGB

0x5453 · Accepted Answer · 2021-06-04 13:53:17Z

2

The C++ equivalent to Python's max is std::max_element.

auto itr = std::max_element(
    objs.begin(), objs.end(),
    [](const auto& lhs, const auto& rhs){ return lhs.eval() < rhs.eval(); }
);
if (itr != objs.end()) {
    double maxval = *itr;
}

edited Jun 4, 2021 at 13:53

answered Jun 4, 2021 at 13:49

0x5453

13.8k2 gold badges36 silver badges70 bronze badges

4 Comments

Nico Schlömer Over a year ago

Does this cache the results of eval()?

0x5453 Over a year ago

@NicoSchlömer I don't think caching is required by the standard, so it probably depends on the standard library implementation.

lubgr Over a year ago

How should it cache the result?! There is no state involved here. It can't write the result into a global variable to return it upon the next invocation.

Nico Schlömer Over a year ago

I see. It's an interesting solution then, but not too useful for me. eval() can be expensive, so I really only want to eval() once per object.

Collectives™ on Stack Overflow

max over c++ array with function call

2 Answers 2

5 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related