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