Max element of input iterator range

Question

I came across this SO question on why std::max_element requires a ForwardIterator (as apposed to an InputIterator). Having a max_element-like algorithm for InputIterator would be useful, as it could then be used with objects like std::istream_iterator or boost::transform_iterator.

I came up with the following algorithm for this:

#include <iterator>   // std::iterator_traits, std::advance
#include <stdexcept>  // std::logic_error
#include <algorithm>  // std::for_each
#include <functional> // std::less
#include <utility>    // std::move

template <typename InputIterator, typename Compare>
typename std::iterator_traits<InputIterator>::value_type
max_input(InputIterator first, InputIterator last, Compare comp)
{
    if (first == last) throw std::logic_error {"max_input given empty range"};

    using ValueType = typename std::iterator_traits<InputIterator>::value_type;

    ValueType result {*first};

    std::advance(first, 1);

    std::for_each(first, last, [&result, comp] (ValueType curr) {
        if (comp(result, curr)) result = std::move(curr);
    });

    return result;
}

Example:

#include <sstream>
#include <iostream>

int main()
{
    std::istringstream str("0.1 0.2 0.3 0.4 0.2 0.0 0.1");

    const auto max = max_input(std::istream_iterator<double>(str), std::istream_iterator<double>());

    std::cout << "max is " << max << std::endl;

    return 0;
}

I'm looking for general feedback/improvements, especially on the decision to throw for an empty range. I was also deliberating whether the algorithm should also return the index of the maximum (e.g. in a std::pair).

Answer 1

Don't use a lambda

This code:

std::for_each(first, last, [&result, comp] (ValueType curr) {
    if (comp(result, curr)) result = std::move(curr);
});

is just a lot messier than the non-lambda equivalent:

for (; first != last; ++first) {
    ValueType cur = *first;
    if (comp(result, cur)) {
        result = std::move(cur);
    }
}

I don't see the advantage in the lambda.

Avoid the copy

Once you advance an input iterator, all earlier iterators are invalidated. But you can dereference the same one multiple times. In this case, you're incurring an unnecessary copy of ValueType, you can just write:

for (; first != last; ++first) {
    if (comp(result, *first)) {
        result = std::move(*first);
    }
}

Move iterators

Dereference likely returns a const T& - so you probably want to wrap the iterators in std::make_move_iterator first. That will actually let you move-from the iterator, instead of looking like you're moving from and actually copying from.

advance is excessive

You can just write:

ValueType result{*first++};

Or:

ValueType result{*first};
++first;

There's no need for advance() - you know operator++ is supported.

Throwing on empty range

Honestly, I'd prefer it just be undefined behavior and avoid the first check. Let the user deal with it. That's just a personal preference though.

Additionally, you could return an optional<ValueType>, returning none if the range is empty.

Defer to std::max_element?

Since std::max_element is more efficient than yours for forward iterators, it'd be nice to defer to it if you're given a forward iterator:

template <class It, class Cmp>
typename std::iterator_traits<It>::value_type
max_input(It first, It last, Cmp mp) {
    // possibly check empty range and throw here, if that's what you want
    return max_input(first, last, cmp, typename std::iterator_traits<It>::iterator_category{});
}

template <class It, class Cmp>
typename std::iterator_traits<It>::value_type
max_input(It first, It last, Cmp cmp, std::input_iterator_tag) {
    /* your implementation */
}

template <class It, class Cmp>
typename std::iterator_traits<It>::value_type
max_input(It first, It last, Cmp cmp, std::forward_iterator_tag) {
    return *std::max_element(it, last, cmp);
}

Excessive commenting

Avoid this sort of commenting style:

#include <iterator>   // std::iterator_traits, std::advance
#include <stdexcept>  // std::logic_error
#include <algorithm>  // std::for_each
#include <functional> // std::less
#include <utility>    // std::move

It's just verbose and provides no value.