c++ - boost minmax_element()实现问题
黄舟
黄舟 2017-04-17 13:40:42
0
0
589
template<typename forwarditerator>
bool _islessequal(forwarditerator first, forwarditerator end)
{
    return *first <= *end;
}

template <typename ForwardIter, class Compare >
std::pair<ForwardIter, ForwardIter>
basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)
{
    if (first == last)
        return std::make_pair(last, last);

    ForwardIter min_result = first;
    ForwardIter max_result = first;

    // if only one element
    ForwardIter second = first; 
    ++second;
    if (second == last)
        return std::make_pair(min_result, max_result);

    // treat first pair separately (only one comparison for first two elements)
     ForwardIter potential_min_result = last;
    if (comp(first, second))
        max_result = second;
    else 
    {
        min_result = second;
        potential_min_result = first;
    }

    // then each element by pairs, with at most 3 comparisons per pair
    first = ++second; 
    if (first != last) 
        ++second;
    while (second != last) 
    {
        if (comp(first, second)) 
        {
            if (comp(first, min_result)) 
            {
                min_result = first;
                potential_min_result = last;
            }
            if (comp(max_result, second))
                max_result = second;
        }
        else 
        {
            if (comp(second, min_result)) 
            {
                min_result = second;
                potential_min_result = first;
            }
            if (comp(max_result, first))
                max_result = first;
        }
        first = ++second;
        if (first != last) 
            ++second;
    }

    // if odd number of elements, treat last element
    if (first != last) 
    { // odd number of elements
        if (comp(first, min_result))
            min_result = first, potential_min_result = last;
        else if (comp(max_result, first))
            max_result = first;
    }

    // resolve min_result being incorrect with one extra comparison
    // (in which case potential_min_result is necessarily the correct result)
    if (potential_min_result != last && !comp(min_result, potential_min_result))
        min_result = potential_min_result;

    return std::make_pair(min_result, max_result);
}

在源码中potential_min_result这个变量的作用是什么?

黄舟
黄舟

人生最曼妙的风景,竟是内心的淡定与从容!

reply all(0)
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template