[boost] Proposed specialization of algorithm/minmax_element

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());
}