 # Boost :

From: Robert Minsk (egbert_at_[hidden])
Date: 2004-10-13 18:37:03

I would like to propose to specialize algorithm/minmax_element for
random access iterators. The inner loop for a random access iterator
would have one less compare and does not have the "potential_min"
special case. I have included a sample implementation without all the
support functions.

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

RandomAccessIter min(first), max(first), second(first + 1);

// Even or odd number of elements
if (std::distance(first, last) & 0x01) {
// Odd - swap the first and second so first will equal last
somewhere down
// the line
std::swap(first, second);
} else {
// Even - so treat first pair separately (only one comparison for
first two
// elements)
if (comp(first, second))
max = second;
else
min = second;
first += 2;
}

// Each element by pairs, with at most 3 comparison per pair
while (first != last) {
second += 2;
if (comp(first, second)) {
if (comp(first, min))
min = first;
if (comp(max, second))
max = second;
} else {
if (comp(second, min))
min = second;
if (comp(max, first))
max = first;
}
first += 2;
}

return std::make_pair(min, max);
}

template <typename Iter>
std::pair<Iter, Iter>
minmax_element(Iter first, Iter last)
{
typedef typename std::iterator_traits<Iter>::iterator_category
IterType;
return detail::basic_minmax_element(first, last,
detail::less_over_iter<Iter>(), IterType());
}

template <typename Iter, class _BinaryPred>
std::pair<Iter, Iter>
minmax_element(Iter first, Iter last, _BinaryPred comp)
{
typedef typename std::iterator_traits<Iter>::iterator_category
IterType;
return detail::basic_minmax_element(first, last,
detail::binary_pred_over_iter<Iter, _BinaryPred>(comp), IterType());
}