Range randomization

randomize_ranges.cpp

// _LIBCPP_DEBUG_RANDOMIZE_RANGE is std::shuffle

template <class _RandomAccessIterator, class _Compare>
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Compare __comp) {
  // Randomize range.
  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
  // Call internal sort.
  _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first),
                           _VSTD::__unwrap_iter(__last), _Comp_ref(__comp));
}

template <class _RandomAccessIterator, class _Compare>
void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
                 _RandomAccessIterator __last, _Compare __comp) {
  // Randomize range.
  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
  // Call internal nth_element.
  _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
  // Both sides of the partition do not have ordering requirements. 
  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth);
  if (__nth != __last) {
    _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last);
  }
}

template <class _RandomAccessIterator, class _Compare>
void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle,
                  _RandomAccessIterator __last, _Compare __comp) {
  // Randomize range.
  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
  _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
  // Trailing part does not have any ordering requirement.
  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last);
}