Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I previously posted a question on finding the maximum value of an InputIterator range. For completeness, I thought it would be useful to post an implementation that finds the minimum & maximum values, in a similar way to std::minmax_element.

#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>

namespace detail
{
    template <typename InputIt, typename Compare>
    auto minmax_input(InputIt first, InputIt last, Compare comp, std::input_iterator_tag)
    {
        using ValueType = typename std::iterator_traits<InputIt>::value_type;

        std::pair<ValueType, ValueType> result {*first, *first};

        if (++first == last) return result;

        if (comp(*first, result.first)) {
            result.first = *first;
        } else {
            result.second = *first;
        }

        while (++first != last) {
            auto prev = *first;
            if (++first == last) {
                if (comp(prev, result.first))
                    result.first = std::move(prev);
                else if (!comp(prev, result.second))
                    result.second = std::move(prev);
                break;
            } else {
                if (comp(*first, prev)) {
                    if (comp(*first, result.first))
                        result.first = *first;
                    if (!comp(prev, result.second))
                        result.second = std::move(prev);
                } else {
                    if (comp(prev, result.first))
                        result.first = std::move(prev);
                    if (!comp(*first, result.second))
                        result.second = *first;
                }
            }
        }

        return result;
    }

    template <typename ForwardIt, typename Compare>
    auto minmax_input(ForwardIt first, ForwardIt last, Compare comp, std::forward_iterator_tag)
    {
        const auto itr_result = std::minmax_element(first, last, comp);
        return std::make_pair(*itr_result.first, *itr_result.second);
    }
} // namespace detail

template <typename InputIt, typename Compare = std::less<void>>
auto minmax_input(InputIt first, InputIt last, Compare comp = Compare {})
{
    return detail::minmax_input(first, last, comp, typename std::iterator_traits<InputIt>::iterator_category {});
}

As this will presumably be used mostly on input streams, I also thought to provide this helper method:

#include <istream>

template <typename T>
auto minmax_stream(std::istream& in)
{
    return minmax_input(std::istream_iterator<T> {in}, std::istream_iterator<T> {});
}

Used like:

#include <iostream>
#include <sstream>

int main()
{
    std::istringstream ss {"0.1 0.2 0.3 0.4 0.2 0.05 0.1"};

    const auto minmax = minmax_stream<double>(ss);

    std::cout << "minmax is (" << minmax.first << ", " << minmax.second << ")" << std::endl;
}
share|improve this question
    
@greybeard You're right, there was an error - corrected now. I don't believe this is "reinventing-the-wheel"; this is a problem not solved by any algorithm in the standard library. – Daniel Feb 10 at 9:22
    
A pity Zeta withdrew his whole answer: one of numerous points I agree with has been use of more telling names for the extrema and construction of the pair at return. Not really easy with move semantics, I guess I'd choose (non-rvalue-)references instead of the real thing (just auto) or (as your reference shows) try and keep the iterator before it was advanced - comment your choice? Nagging me in both renditions is the repetition of the non-pair comparisons at the beginning and end of the sequence - beware a non-answer. – greybeard Feb 10 at 11:46
    
@greybeard I agree; Zita's answer was still useful. But it's not possible to keep the iterator (or a reference) to the previous iterator - that's the whole point of implementing this algorithm for InputIterator (single pass). I don't really understand the repetition in the algorithm either, but it's the way it's implemented in libcpp... – Daniel Feb 10 at 11:50

(This is an extended (and formatted…) comment (don't like the repetition of the non-pair comparisons at the beginning and end of the sequence). Not having used C++ in a dozen years, I'm hopeless with move semantics, for one. (And not quite destined to review C++ postings…))

Let me try something about the non-pair comparisons:

template <typename InputIt, typename Compare>
auto minmax_input(InputIt first, InputIt last, Compare comp, std::input_iterator_tag)
{
    using ValueType = typename std::iterator_traits<InputIt>::value_type;

    auto const
        &minimum = *first,
        &maximum = minimum;

    while (++first != last) {
        auto &prev = *first;
        if (++first == last) { // left with half a pair: prev
            if (comp(prev, minimum))
                minimum = prev;
            else if (!comp(prev, maximum))
                maximum = prev;
            break;
        }
        if (comp(*first, prev)) {
            if (comp(*first, minimum))
                minimum = *first;
            if (!comp(prev, maximum))
                maximum = prev;
        } else {
            if (comp(prev, minimum))
                minimum = prev;
            if (!comp(*first, maximum))
                maximum = *first;
        }
    }

    return std::pair<ValueType, ValueType> {minimum, maximum};
}

(Come to think of it, I don't like the symmetrical pairs of comparisons in the loop…)

        auto min_max = std::minmax(one, *first);
        if (comp(min_max.first, minimum))
            minimum = min_max.first;
        if (!comp(min_max.second, maximum))
            maximum = min_max.second;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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