5
\$\begingroup\$

I made a function to find the element that yields the largest value when put into a custom functor.

I think this is missing from the STL. I can think of three ways to do this in STL:

  • Transform the container by the functor. Find the maximum in the transformed version. Take the corresponding element from the original container.
  • Transform the container to an iterable of std::pairs containing the iterators to the original values and the corresponding functor result value. Write a custom comparison function which compares the .second of the pairs. Find max among the pairs with std::max_element. Take .first of the resulting iterator.
  • Use a custom comparator functor in std::max_element (return f(lhs) < f(rhs)).

The first two are really cumbersome and the third calls the functor twice as many times as necessary. Hence this:

template<typename Iterable, typename UnaryFun>
auto maxElementBy(Iterable const& iterable, UnaryFun criterion)
    -> decltype(std::begin(iterable))
{
    typedef decltype(criterion(*std::begin(iterable))) CriterionResult;

    auto itCurrent = std::begin(iterable);
    auto itEnd = std::end(iterable);

    if (itCurrent == itEnd)
    {
        return itEnd;
    }

    CriterionResult bestValue = criterion(*itCurrent);
    auto itBest = itCurrent;
    ++itCurrent;

    for (; itCurrent != itEnd; ++itCurrent)
    {
        CriterionResult currentValue = criterion(*itCurrent);
        if (bestValue < currentValue)
        {
            itBest = itCurrent;
            bestValue = std::move(currentValue);
        }
    }
    return itBest;
}

Any suggestions?

\$\endgroup\$
  • \$\begingroup\$ While the standard does not offer applying functors before comparing it allows to specify a custom comparator. This makes it easy to implement a custom comparator that takes a functor and applies it before comparing objects. \$\endgroup\$ – Nobody May 23 '14 at 16:18
  • \$\begingroup\$ @Nobody In that way the functor will be called twice as many times as necessary. \$\endgroup\$ – isarandi May 23 '14 at 16:20
  • \$\begingroup\$ If the operation is too costly you could offer a caching comparator that caches the last two results and reuses them if appropriate. The "beauty" of the comparator approach is, that you could also use it with other functions (like std::sort) \$\endgroup\$ – Nobody May 23 '14 at 16:36
  • \$\begingroup\$ std::accumulate with a simple custom function achieves the same result. \$\endgroup\$ – vnp May 23 '14 at 17:06
  • 1
    \$\begingroup\$ I'm not very comfortable with the decltype. This might yield a reference, and you need something local assignable for bestValue. I'd use auto bestValue = criterion(*itCurrent); instead. For currentValue, you can use auto&& currentValue = ..; because that doesn't need to be assignable. However, if it returns a reference, you might have an unintended side-effect via the move. \$\endgroup\$ – dyp May 23 '14 at 19:59
2
\$\begingroup\$

Setting aside the std::accumulate discussion, I have one recommendation. The signature

template<typename Iterator, typename UnaryFun>
auto maxElementBy(Iterator first, Iterator last, UnaryFun criterion)
    -> Iterator

seems to be more flexible. It allows partial ranges, and seems more in line with the std design approach.

\$\endgroup\$
  • \$\begingroup\$ You are right, that is the STL style. I don't really like it, though. It's really cumbersome to write (and read) maxElementBy(std::begin(someNamedVector), std::end(someNamedVector), fun) compared to maxElementBy(someNamedVector, fun). Hopefully ranges will be introduced to C++ sometime. \$\endgroup\$ – isarandi May 23 '14 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.