11
\$\begingroup\$

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).

\$\endgroup\$

1 Answer 1

8
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Is there a reason you made a copy of the ValueType in your non-lambda implementation? Wouldn't it be more efficient to skip making the copy of that element on each for loop iteration and just do: if (comp(result, *first)) { ValueType cur = *first; result = std::move(*first); } \$\endgroup\$
    – Bizkit
    Dec 23, 2015 at 16:01
  • \$\begingroup\$ @TamerCpp The original copied too - I just... copied... the code. But yeah, you're right, updated the answer. \$\endgroup\$
    – Barry
    Dec 23, 2015 at 16:12
  • \$\begingroup\$ The reason I chose to make an unconditional copy rather than multiple dereferences was that we cannot be sure of the complexity of the dereference. e.g. I believe boost::transform_iterator applies its functor at dereference rather than on increment. But I guess that could be the callers responsibility. \$\endgroup\$
    – Daniel
    Dec 23, 2015 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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