vendor/llvm-project/llvmorg-15-init-17485-ga3e38b4a206b

47 files changed, 1180 insertions, 653 deletions

diff --git a/libcxx/include/__algorithm/equal_range.h b/libcxx/include/__algorithm/equal_range.h
index f30f55be64fc..42d009ebbc0f 100644
--- a/libcxx/include/__algorithm/equal_range.h
+++ b/libcxx/include/__algorithm/equal_range.h
@@ -17,9 +17,13 @@
 #include <__algorithm/upper_bound.h>
 #include <__config>
 #include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_callable.h>
+#include <__type_traits/is_copy_constructible.h>
+#include <__utility/move.h>
 #include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -28,59 +32,50 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _ForwardIterator, class _Tp>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
-__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
-{
-    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
-    while (__len != 0)
-    {
-        difference_type __l2 = _VSTD::__half_positive(__len);
-        _ForwardIterator __m = __first;
-        _VSTD::advance(__m, __l2);
-        if (__comp(*__m, __value))
-        {
-            __first = ++__m;
-            __len -= __l2 + 1;
-        }
-        else if (__comp(__value, *__m))
-        {
-            __last = __m;
-            __len = __l2;
-        }
-        else
-        {
-            auto __proj = std::__identity();
-            _ForwardIterator __mp1 = __m;
-            return pair<_ForwardIterator, _ForwardIterator>
-                   (
-                      _VSTD::__lower_bound_impl<_ClassicAlgPolicy>(__first, __m, __value, __comp, __proj),
-                      _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value, __comp)
-                   );
-        }
+template <class _AlgPolicy, class _Compare, class _Iter, class _Sent, class _Tp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_Iter, _Iter>
+__equal_range(_Iter __first, _Sent __last, const _Tp& __value, _Compare&& __comp, _Proj&& __proj) {
+  auto __len  = _IterOps<_AlgPolicy>::distance(__first, __last);
+  _Iter __end = _IterOps<_AlgPolicy>::next(__first, __last);
+  while (__len != 0) {
+    auto __half_len = std::__half_positive(__len);
+    _Iter __mid     = _IterOps<_AlgPolicy>::next(__first, __half_len);
+    if (std::__invoke(__comp, std::__invoke(__proj, *__mid), __value)) {
+      __first = ++__mid;
+      __len -= __half_len + 1;
+    } else if (std::__invoke(__comp, __value, std::__invoke(__proj, *__mid))) {
+      __end = __mid;
+      __len = __half_len;
+    } else {
+      _Iter __mp1 = __mid;
+      return pair<_Iter, _Iter>(
+          std::__lower_bound_impl<_AlgPolicy>(__first, __mid, __value, __comp, __proj),
+          std::__upper_bound<_AlgPolicy>(++__mp1, __end, __value, __comp, __proj));
     }
-    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
+  }
+  return pair<_Iter, _Iter>(__first, __first);
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-pair<_ForwardIterator, _ForwardIterator>
-equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value, __comp);
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
+equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) {
+  static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value,
+                "The comparator has to be callable");
+  static_assert(is_copy_constructible<_ForwardIterator>::value,
+                "Iterator has to be copy constructible");
+  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+  return std::__equal_range<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), __value, static_cast<_Comp_ref>(__comp), std::__identity());
 }
 
 template <class _ForwardIterator, class _Tp>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-pair<_ForwardIterator, _ForwardIterator>
-equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
-{
-    return _VSTD::equal_range(__first, __last, __value,
-                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
+equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  return std::equal_range(
+      std::move(__first),
+      std::move(__last),
+      __value,
+      __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/includes.h b/libcxx/include/__algorithm/includes.h
index 4c87e8d22116..102d3db39a2d 100644
--- a/libcxx/include/__algorithm/includes.h
+++ b/libcxx/include/__algorithm/includes.h
@@ -13,6 +13,7 @@
 #include <__algorithm/comp_ref_type.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -20,41 +21,40 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator1, class _InputIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
-           _Compare __comp)
-{
-    for (; __first2 != __last2; ++__first1)
-    {
-        if (__first1 == __last1 || __comp(*__first2, *__first1))
-            return false;
-        if (!__comp(*__first1, *__first2))
-            ++__first2;
-    }
-    return true;
+template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Comp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__includes(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Comp&& __comp) {
+  for (; __first2 != __last2; ++__first1) {
+    if (__first1 == __last1 || __comp(*__first2, *__first1))
+      return false;
+    if (!__comp(*__first1, *__first2))
+      ++__first2;
+  }
+  return true;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _Compare>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-bool
-includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
-         _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool includes(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _Compare __comp) {
+  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+  return std::__includes(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), static_cast<_Comp_ref>(__comp));
 }
 
 template <class _InputIterator1, class _InputIterator2>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-bool
-includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
-{
-    return _VSTD::includes(__first1, __last1, __first2, __last2,
-                          __less<typename iterator_traits<_InputIterator1>::value_type,
-                                 typename iterator_traits<_InputIterator2>::value_type>());
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
+  return std::includes(
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__last2),
+      __less<typename iterator_traits<_InputIterator1>::value_type,
+             typename iterator_traits<_InputIterator2>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h
index 58919ddbae76..f4364969b8f9 100644
--- a/libcxx/include/__algorithm/inplace_merge.h
+++ b/libcxx/include/__algorithm/inplace_merge.h
@@ -11,17 +11,18 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/upper_bound.h>
 #include <__config>
+#include <__functional/identity.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
-#include <__utility/swap.h>
 #include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -53,7 +54,7 @@ public:
     bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
 };
 
-template <class _Compare, class _InputIterator1, class _InputIterator2,
+template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2,
           class _OutputIterator>
 void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
                           _InputIterator2 __first2, _InputIterator2 __last2,
@@ -63,25 +64,26 @@ void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
     {
         if (__first2 == __last2)
         {
+            // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `move`.
             _VSTD::move(__first1, __last1, __result);
             return;
         }
 
         if (__comp(*__first2, *__first1))
         {
-            *__result = _VSTD::move(*__first2);
+            *__result = _IterOps<_AlgPolicy>::__iter_move(__first2);
             ++__first2;
         }
         else
         {
-            *__result = _VSTD::move(*__first1);
+            *__result = _IterOps<_AlgPolicy>::__iter_move(__first1);
             ++__first1;
         }
     }
     // __first2 through __last2 are already in the right spot.
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void
 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
@@ -95,30 +97,32 @@ __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_VSTD::move(*__i));
-        _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp);
+            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
+        std::__half_inplace_merge<_AlgPolicy, _Compare>(__buff, __p, __middle, __last, __first, __comp);
     }
     else
     {
         value_type* __p = __buff;
         for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_VSTD::move(*__i));
+            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
         typedef reverse_iterator<_BidirectionalIterator> _RBi;
         typedef reverse_iterator<value_type*> _Rv;
         typedef __invert<_Compare> _Inverted;
-        _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff),
+        std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff),
                                     _RBi(__middle), _RBi(__first),
                                     _RBi(__last), _Inverted(__comp));
     }
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void
 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
                 _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
                                  typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
                 typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
     while (true)
     {
@@ -126,7 +130,7 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
         if (__len2 == 0)
             return;
         if (__len1 <= __buff_size || __len2 <= __buff_size)
-            return _VSTD::__buffered_inplace_merge<_Compare>
+            return std::__buffered_inplace_merge<_AlgPolicy, _Compare>
                    (__first, __middle, __last, __comp, __len1, __len2, __buff);
         // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
         for (; true; ++__first, (void) --__len1)
@@ -153,35 +157,38 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
         {   // __len >= 1, __len2 >= 2
             __len21 = __len2 / 2;
             __m2 = __middle;
-            _VSTD::advance(__m2, __len21);
-            __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp);
-            __len11 = _VSTD::distance(__first, __m1);
+            _Ops::advance(__m2, __len21);
+            // TODO: replace _ClassicAlgPolicy and __identity with _AlgPolicy and projection
+            __m1 = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity());
+            __len11 = _Ops::distance(__first, __m1);
         }
         else
         {
             if (__len1 == 1)
             {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
                 // It is known *__first > *__middle
-                swap(*__first, *__middle);
+              _Ops::iter_swap(__first, __middle);
                 return;
             }
             // __len1 >= 2, __len2 >= 1
             __len11 = __len1 / 2;
             __m1 = __first;
-            _VSTD::advance(__m1, __len11);
+            _Ops::advance(__m1, __len11);
             __m2 = std::lower_bound(__middle, __last, *__m1, __comp);
-            __len21 = _VSTD::distance(__middle, __m2);
+            __len21 = _Ops::distance(__middle, __m2);
         }
         difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
         difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
         // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
         // swap middle two partitions
+        // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`.
         __middle = _VSTD::rotate(__m1, __middle, __m2);
         // __len12 and __len21 now have swapped meanings
         // merge smaller range with recursive call and larger with tail recursion elimination
         if (__len11 + __len21 < __len12 + __len22)
         {
-            _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
+            std::__inplace_merge<_AlgPolicy, _Compare>(
+                __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
 //          _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
             __first = __middle;
             __middle = __m2;
@@ -190,7 +197,8 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle,
         }
         else
         {
-            _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
+            std::__inplace_merge<_AlgPolicy, _Compare>(
+                __middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
 //          _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
             __last = __middle;
             __middle = __m1;
@@ -217,7 +225,7 @@ _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 _LIBCPP_SUPPRESS_DEPRECATED_POP
     unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
+    return _VSTD::__inplace_merge<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
                                             __buf.first, __buf.second);
 }
 
diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h
index eb627e1ace7a..8307d71214e5 100644
--- a/libcxx/include/__algorithm/iterator_operations.h
+++ b/libcxx/include/__algorithm/iterator_operations.h
@@ -41,6 +41,7 @@ struct _IterOps<_RangeAlgPolicy> {
   static constexpr auto next = ranges::next;
   static constexpr auto __advance_to = ranges::advance;
 };
+
 #endif
 
 struct _ClassicAlgPolicy {};
@@ -65,11 +66,24 @@ struct _IterOps<_ClassicAlgPolicy> {
   // iter_move
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-  // Declaring the return type is necessary for the C++03 mode (which doesn't support placeholder return types).
-  static typename iterator_traits<__uncvref_t<_Iter> >::value_type&& __iter_move(_Iter&& __i) {
+      // Declaring the return type is necessary for C++03, so we basically mirror what `decltype(auto)` would deduce.
+      static __enable_if_t<
+          is_reference<typename iterator_traits<__uncvref_t<_Iter> >::reference>::value,
+          typename remove_reference< typename iterator_traits<__uncvref_t<_Iter> >::reference >::type&&>
+      __iter_move(_Iter&& __i) {
     return std::move(*std::forward<_Iter>(__i));
   }
 
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+      // Declaring the return type is necessary for C++03, so we basically mirror what `decltype(auto)` would deduce.
+      static __enable_if_t<
+          !is_reference<typename iterator_traits<__uncvref_t<_Iter> >::reference>::value,
+          typename iterator_traits<__uncvref_t<_Iter> >::reference>
+      __iter_move(_Iter&& __i) {
+    return *std::forward<_Iter>(__i);
+  }
+
   // iter_swap
   template <class _Iter1, class _Iter2>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
@@ -85,7 +99,15 @@ struct _IterOps<_ClassicAlgPolicy> {
   }
 
   template <class _Iter>
-  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void __advance_to(_Iter& __first, _Iter __last) {
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  __uncvref_t<_Iter> next(_Iter&& __it, 
+                          typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1){
+    return std::next(std::forward<_Iter>(__it), __n);
+  }
+
+  template <class _Iter>
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
+  void __advance_to(_Iter& __first, _Iter __last) {
     __first = __last;
   }
 };
diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h
index bc39d82bf916..bf9dd96756af 100644
--- a/libcxx/include/__algorithm/make_heap.h
+++ b/libcxx/include/__algorithm/make_heap.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/sift_down.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
@@ -22,7 +23,7 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
@@ -33,7 +34,7 @@ void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
   if (__n > 1) {
     // start from the first parent, there is no need to consider children
     for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) {
-        std::__sift_down<_CompRef>(__first, __comp_ref, __n, __first + __start);
+        std::__sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __n, __first + __start);
     }
   }
 }
@@ -41,7 +42,7 @@ void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__make_heap(std::move(__first), std::move(__last), __comp);
+  std::__make_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/make_projected.h b/libcxx/include/__algorithm/make_projected.h
index 6d8ebfd3d90e..64fc3dfb6a12 100644
--- a/libcxx/include/__algorithm/make_projected.h
+++ b/libcxx/include/__algorithm/make_projected.h
@@ -27,6 +27,21 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
+template <class _Pred, class _Proj>
+_LIBCPP_HIDE_FROM_ABI constexpr static
+decltype(auto) __make_projected_pred(_Pred& __pred, _Proj& __proj) {
+  if constexpr (same_as<decay_t<_Proj>, identity> && !is_member_pointer_v<decay_t<_Pred>>) {
+    // Avoid creating the lambda and just use the pristine predicate -- for certain algorithms, this would enable
+    // optimizations that rely on the type of the predicate.
+    return __pred;
+
+  } else {
+    return [&](auto&& __x) {
+      return std::invoke(__pred, std::invoke(__proj, std::forward<decltype(__x)>(__x)));
+    };
+  }
+}
+
 template <class _Comp, class _Proj>
 _LIBCPP_HIDE_FROM_ABI constexpr static
 decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) {
diff --git a/libcxx/include/__algorithm/min_element.h b/libcxx/include/__algorithm/min_element.h
index 129833d42bda..17b242c341e6 100644
--- a/libcxx/include/__algorithm/min_element.h
+++ b/libcxx/include/__algorithm/min_element.h
@@ -12,7 +12,11 @@
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_callable.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -20,28 +24,38 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _ForwardIterator>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
-__min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
-{
-    static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
-        "std::min_element requires a ForwardIterator");
-    if (__first != __last)
-    {
-        _ForwardIterator __i = __first;
-        while (++__i != __last)
-            if (__comp(*__i, *__first))
-                __first = __i;
-    }
+template <class _Comp, class _Iter, class _Sent, class _Proj>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+_Iter __min_element(_Iter __first, _Sent __last, _Comp __comp, _Proj& __proj) {
+  if (__first == __last)
     return __first;
+
+  _Iter __i = __first;
+  while (++__i != __last)
+    if (std::__invoke(__comp, std::__invoke(__proj, *__i), std::__invoke(__proj, *__first)))
+      __first = __i;
+
+  return __first;
+}
+
+template <class _Comp, class _Iter, class _Sent>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+_Iter __min_element(_Iter __first, _Sent __last, _Comp __comp) {
+  auto __proj = __identity();
+  return std::__min_element<_Comp>(std::move(__first), std::move(__last), __comp, __proj);
 }
 
 template <class _ForwardIterator, class _Compare>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__min_element<_Comp_ref>(__first, __last, __comp);
+  static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
+      "std::min_element requires a ForwardIterator");
+  static_assert(__is_callable<_Compare, decltype(*__first), decltype(*__first)>::value,
+              "The comparator has to be callable");
+
+  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+  return std::__min_element<_Comp_ref>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _ForwardIterator>
diff --git a/libcxx/include/__algorithm/nth_element.h b/libcxx/include/__algorithm/nth_element.h
index c7cdef5be817..688398dee814 100644
--- a/libcxx/include/__algorithm/nth_element.h
+++ b/libcxx/include/__algorithm/nth_element.h
@@ -11,13 +11,13 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
-#include <__utility/swap.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -41,10 +41,12 @@ __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j,
     }
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     // _Compare is known to be a reference type
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     const difference_type __limit = 7;
@@ -60,24 +62,24 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando
             return;
         case 2:
             if (__comp(*--__last, *__first))
-                swap(*__first, *__last);
+                _Ops::iter_swap(__first, __last);
             return;
         case 3:
             {
             _RandomAccessIterator __m = __first;
-            _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
+            std::__sort3<_AlgPolicy, _Compare>(__first, ++__m, --__last, __comp);
             return;
             }
         }
         if (__len <= __limit)
         {
-            _VSTD::__selection_sort<_Compare>(__first, __last, __comp);
+            std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
             return;
         }
         // __len > __limit >= 3
         _RandomAccessIterator __m = __first + __len/2;
         _RandomAccessIterator __lm1 = __last;
-        unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
+        unsigned __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, --__lm1, __comp);
         // *__m is median
         // partition [__first, __m) < *__m and *__m <= [__m, __last)
         // (this inhibits tossing elements equivalent to __m around unnecessarily)
@@ -90,7 +92,7 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando
         {
             // *__first == *__m, *__first doesn't go in first part
             if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
-                swap(*__i, *__j);
+                _Ops::iter_swap(__i, __j);
                 ++__n_swaps;
             } else {
                 // *__first == *__m, *__m <= all other elements
@@ -102,7 +104,7 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando
                         if (__i == __j) {
                             return;  // [__first, __last) all equivalent elements
                         } else if (__comp(*__first, *__i)) {
-                            swap(*__i, *__j);
+                            _Ops::iter_swap(__i, __j);
                             ++__n_swaps;
                             ++__i;
                             break;
@@ -121,7 +123,7 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando
                         ;
                     if (__i >= __j)
                         break;
-                    swap(*__i, *__j);
+                    _Ops::iter_swap(__i, __j);
                     ++__n_swaps;
                     ++__i;
                 }
@@ -152,7 +154,7 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando
                     ;
                 if (__i >= __j)
                     break;
-                swap(*__i, *__j);
+                _Ops::iter_swap(__i, __j);
                 ++__n_swaps;
                 // It is known that __m != __j
                 // If __m just moved, follow it
@@ -164,7 +166,7 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando
         // [__first, __i) < *__m and *__m <= [__i, __last)
         if (__i != __m && __comp(*__m, *__i))
         {
-            swap(*__i, *__m);
+            _Ops::iter_swap(__i, __m);
             ++__n_swaps;
         }
         // [__first, __i) < *__i and *__i <= [__i+1, __last)
@@ -220,21 +222,21 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando
     }
 }
 
-template <class _RandomAccessIterator, class _Compare>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
                         _Compare& __comp) {
   if (__nth == __last)
     return;
 
-  std::__debug_randomize_range(__first, __last);
+  std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 
   using _Comp_ref = typename __comp_ref_type<_Compare>::type;
-  std::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
+  std::__nth_element<_AlgPolicy, _Comp_ref>(__first, __nth, __last, __comp);
 
-  std::__debug_randomize_range(__first, __nth);
+  std::__debug_randomize_range<_AlgPolicy>(__first, __nth);
   if (__nth != __last) {
-    std::__debug_randomize_range(++__nth, __last);
+    std::__debug_randomize_range<_AlgPolicy>(++__nth, __last);
   }
 }
 
@@ -242,7 +244,7 @@ template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
                  _Compare __comp) {
-  std::__nth_element_impl(std::move(__first), std::move(__nth), std::move(__last), __comp);
+  std::__nth_element_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__nth), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h
index e008c0c99679..24016e5cf5a5 100644
--- a/libcxx/include/__algorithm/partial_sort.h
+++ b/libcxx/include/__algorithm/partial_sort.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__algorithm/sort_heap.h>
@@ -18,7 +19,8 @@
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
+#include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -26,24 +28,47 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 void
-__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
-               _Compare __comp)
-{
-    if (__first == __middle)
-        return;
-    _VSTD::__make_heap<_Compare>(__first, __middle, __comp);
-    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
-    for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
-    {
-        if (__comp(*__i, *__first))
-        {
-            swap(*__i, *__first);
-            _VSTD::__sift_down<_Compare>(__first, __comp, __len, __first);
-        }
-    }
-    _VSTD::__sort_heap<_Compare>(__first, __middle, __comp);
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17
+_RandomAccessIterator __partial_sort_impl(
+    _RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, _Compare __comp) {
+  if (__first == __middle) {
+    return _IterOps<_AlgPolicy>::next(__middle, __last);
+  }
+
+  std::__make_heap<_AlgPolicy, _Compare>(__first, __middle, __comp);
+
+  typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
+  _RandomAccessIterator __i = __middle;
+  for (; __i != __last; ++__i)
+  {
+      if (__comp(*__i, *__first))
+      {
+          _IterOps<_AlgPolicy>::iter_swap(__i, __first);
+          std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first);
+      }
+
+  }
+  std::__sort_heap<_AlgPolicy, _Compare>(std::move(__first), std::move(__middle), __comp);
+
+  return __i;
+}
+
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17
+_RandomAccessIterator __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last,
+                                     _Compare& __comp) {
+  if (__first == __middle)
+      return _IterOps<_AlgPolicy>::next(__middle, __last);
+
+  std::__debug_randomize_range<_AlgPolicy>(__first, __last);
+
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  auto __last_iter = std::__partial_sort_impl<_AlgPolicy, _Comp_ref>(__first, __middle, __last, __comp);
+
+  std::__debug_randomize_range<_AlgPolicy>(__middle, __last);
+
+  return __last_iter;
 }
 
 template <class _RandomAccessIterator, class _Compare>
@@ -52,10 +77,10 @@ void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
-  std::__debug_randomize_range(__first, __last);
-  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
-  std::__debug_randomize_range(__middle, __last);
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
+  (void)std::__partial_sort<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/partial_sort_copy.h b/libcxx/include/__algorithm/partial_sort_copy.h
index 7ed1e538e9b8..3556764e652d 100644
--- a/libcxx/include/__algorithm/partial_sort_copy.h
+++ b/libcxx/include/__algorithm/partial_sort_copy.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__algorithm/sort_heap.h>
@@ -23,7 +24,7 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _InputIterator, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
                     _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
@@ -33,15 +34,15 @@ __partial_sort_copy(_InputIterator __first, _InputIterator __last,
     {
         for (; __first != __last && __r != __result_last; ++__first, (void) ++__r)
             *__r = *__first;
-        _VSTD::__make_heap<_Compare>(__result_first, __r, __comp);
+        std::__make_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp);
         typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
         for (; __first != __last; ++__first)
             if (__comp(*__first, *__result_first))
             {
                 *__result_first = *__first;
-                _VSTD::__sift_down<_Compare>(__result_first, __comp, __len, __result_first);
+                std::__sift_down<_AlgPolicy, _Compare>(__result_first, __comp, __len, __result_first);
             }
-        _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp);
+        std::__sort_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp);
     }
     return __r;
 }
@@ -53,7 +54,8 @@ partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
+    return std::__partial_sort_copy<_ClassicAlgPolicy, _Comp_ref>(
+        __first, __last, __result_first, __result_last, __comp);
 }
 
 template <class _InputIterator, class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/partition.h b/libcxx/include/__algorithm/partition.h
index 73d94831ed87..60b4e290ebeb 100644
--- a/libcxx/include/__algorithm/partition.h
+++ b/libcxx/include/__algorithm/partition.h
@@ -9,9 +9,12 @@
 #ifndef _LIBCPP___ALGORITHM_PARTITION_H
 #define _LIBCPP___ALGORITHM_PARTITION_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -19,40 +22,45 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Predicate, class _ForwardIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
-__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
+template <class _Predicate, class _AlgPolicy, class _ForwardIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
+__partition_impl(_ForwardIterator __first, _Sentinel __last, _Predicate __pred, forward_iterator_tag)
 {
     while (true)
     {
         if (__first == __last)
-            return __first;
+            return std::make_pair(std::move(__first), std::move(__first));
         if (!__pred(*__first))
             break;
         ++__first;
     }
-    for (_ForwardIterator __p = __first; ++__p != __last;)
+
+    _ForwardIterator __p = __first;
+    while (++__p != __last)
     {
         if (__pred(*__p))
         {
-            swap(*__first, *__p);
+            _IterOps<_AlgPolicy>::iter_swap(__first, __p);
             ++__first;
         }
     }
-    return __first;
+    return std::make_pair(std::move(__first), std::move(__p));
 }
 
-template <class _Predicate, class _BidirectionalIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator
-__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
+template <class _Predicate, class _AlgPolicy, class _BidirectionalIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_BidirectionalIterator, _BidirectionalIterator>
+__partition_impl(_BidirectionalIterator __first, _Sentinel __sentinel, _Predicate __pred,
             bidirectional_iterator_tag)
 {
+    _BidirectionalIterator __original_last = _IterOps<_AlgPolicy>::next(__first, __sentinel);
+    _BidirectionalIterator __last = __original_last;
+
     while (true)
     {
         while (true)
         {
             if (__first == __last)
-                return __first;
+                return std::make_pair(std::move(__first), std::move(__original_last));
             if (!__pred(*__first))
                 break;
             ++__first;
@@ -60,20 +68,29 @@ __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Pred
         do
         {
             if (__first == --__last)
-                return __first;
+                return std::make_pair(std::move(__first), std::move(__original_last));
         } while (!__pred(*__last));
-        swap(*__first, *__last);
+        _IterOps<_AlgPolicy>::iter_swap(__first, __last);
         ++__first;
     }
 }
 
+template <class _AlgPolicy, class _ForwardIterator, class _Sentinel, class _Predicate, class _IterCategory>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+pair<_ForwardIterator, _ForwardIterator> __partition(
+    _ForwardIterator __first, _Sentinel __last, _Predicate&& __pred, _IterCategory __iter_category) {
+  return std::__partition_impl<__uncvref_t<_Predicate>&, _AlgPolicy>(
+      std::move(__first), std::move(__last), __pred, __iter_category);
+}
+
 template <class _ForwardIterator, class _Predicate>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
 {
-    return _VSTD::__partition<_Predicate&>(
-        __first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
+  using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
+  auto __result = std::__partition<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __pred, _IterCategory());
+  return __result.first;
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h
index cadda81f6c88..870af50c133e 100644
--- a/libcxx/include/__algorithm/pop_heap.h
+++ b/libcxx/include/__algorithm/pop_heap.h
@@ -11,12 +11,14 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -24,7 +26,7 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp,
     typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
@@ -35,17 +37,17 @@ void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Co
 
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   if (__len > 1) {
-    value_type __top = std::move(*__first);  // create a hole at __first
-    _RandomAccessIterator __hole = std::__floyd_sift_down<_CompRef>(__first, __comp_ref, __len);
+    value_type __top = _IterOps<_AlgPolicy>::__iter_move(__first);  // create a hole at __first
+    _RandomAccessIterator __hole = std::__floyd_sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __len);
     --__last;
 
     if (__hole == __last) {
       *__hole = std::move(__top);
     } else {
-      *__hole = std::move(*__last);
+      *__hole = _IterOps<_AlgPolicy>::__iter_move(__last);
       ++__hole;
       *__last = std::move(__top);
-      std::__sift_up<_CompRef>(__first, __hole, __comp_ref, __hole - __first);
+      std::__sift_up<_AlgPolicy, _CompRef>(__first, __hole, __comp_ref, __hole - __first);
     }
   }
 }
@@ -53,8 +55,11 @@ void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Co
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
-  std::__pop_heap(std::move(__first), std::move(__last), __comp, __len);
+  std::__pop_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __len);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/push_heap.h b/libcxx/include/__algorithm/push_heap.h
index 1e3eec373d4f..716670b76788 100644
--- a/libcxx/include/__algorithm/push_heap.h
+++ b/libcxx/include/__algorithm/push_heap.h
@@ -11,9 +11,11 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -21,7 +23,7 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
         typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
@@ -32,9 +34,9 @@ void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Com
     _RandomAccessIterator __ptr = __first + __len;
 
     if (__comp(*__ptr, *--__last)) {
-      value_type __t(std::move(*__last));
+      value_type __t(_IterOps<_AlgPolicy>::__iter_move(__last));
       do {
-        *__last = std::move(*__ptr);
+        *__last = _IterOps<_AlgPolicy>::__iter_move(__ptr);
         __last = __ptr;
         if (__len == 0)
           break;
@@ -47,18 +49,21 @@ void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Com
   }
 }
 
-template <class _RandomAccessIterator, class _Compare>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
-  std::__sift_up<_CompRef>(std::move(__first), std::move(__last), __comp, __len);
+  std::__sift_up<_AlgPolicy, _CompRef>(std::move(__first), std::move(__last), __comp, __len);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__push_heap(std::move(__first), std::move(__last), __comp);
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
+  std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/ranges_equal_range.h b/libcxx/include/__algorithm/ranges_equal_range.h
index 28d721530bda..dd4b377df1a1 100644
--- a/libcxx/include/__algorithm/ranges_equal_range.h
+++ b/libcxx/include/__algorithm/ranges_equal_range.h
@@ -10,7 +10,7 @@
 #define _LIBCPP___ALGORITHM_RANGES_EQUAL_RANGE_H
 
 #include <__algorithm/equal_range.h>
-#include <__algorithm/make_projected.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
@@ -37,27 +37,30 @@ namespace ranges {
 namespace __equal_range {
 
 struct __fn {
-
-  template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Tp, class _Proj = identity,
-            indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  subrange<_Iter> operator()(_Iter __first, _Sent __last, const _Tp& __value, _Comp __comp = {},
-                             _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__value; (void)__comp; (void)__proj;
-    return {};
+  template <
+      forward_iterator _Iter,
+      sentinel_for<_Iter> _Sent,
+      class _Tp,
+      class _Proj                                                           = identity,
+      indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter>
+  operator()(_Iter __first, _Sent __last, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __ret = std::__equal_range<_RangeAlgPolicy>(
+        std::move(__first), std::move(__last), __value, __comp, __proj);
+    return {std::move(__ret.first), std::move(__ret.second)};
   }
 
-  template <forward_range _Range, class _Tp, class _Proj = identity,
-            indirect_strict_weak_order<const _Tp*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  borrowed_subrange_t<_Range> operator()(_Range&& __range, const _Tp& __value, _Comp __comp = {},
-                                         _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__value; (void)__comp; (void)__proj;
-    return {};
+  template <
+      forward_range _Range,
+      class _Tp,
+      class _Proj                                                                        = identity,
+      indirect_strict_weak_order<const _Tp*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range>
+  operator()(_Range&& __range, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __ret = std::__equal_range<_RangeAlgPolicy>(
+        ranges::begin(__range), ranges::end(__range), __value, __comp, __proj);
+    return {std::move(__ret.first), std::move(__ret.second)};
   }
-
 };
 
 } // namespace __equal_range
diff --git a/libcxx/include/__algorithm/ranges_fill.h b/libcxx/include/__algorithm/ranges_fill.h
index 846e31885141..7ce4a76ba9e9 100644
--- a/libcxx/include/__algorithm/ranges_fill.h
+++ b/libcxx/include/__algorithm/ranges_fill.h
@@ -30,7 +30,7 @@ struct __fn {
   template <class _Type, output_iterator<const _Type&> _Iter, sentinel_for<_Iter> _Sent>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const {
-    if constexpr(random_access_iterator<_Iter>) {
+    if constexpr(random_access_iterator<_Iter> && sized_sentinel_for<_Sent, _Iter>) {
       return ranges::fill_n(__first, __last - __first, __value);
     } else {
       for (; __first != __last; ++__first)
diff --git a/libcxx/include/__algorithm/ranges_find_end.h b/libcxx/include/__algorithm/ranges_find_end.h
index fec709e79f5a..270b00649848 100644
--- a/libcxx/include/__algorithm/ranges_find_end.h
+++ b/libcxx/include/__algorithm/ranges_find_end.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/find_end.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/ranges_iterator_concept.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/ranges_operations.h>
@@ -29,23 +30,6 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Iter>
-consteval auto __get_iterator_concept() {
-  if constexpr (contiguous_iterator<_Iter>)
-    return contiguous_iterator_tag();
-  else if constexpr (random_access_iterator<_Iter>)
-    return random_access_iterator_tag();
-  else if constexpr (bidirectional_iterator<_Iter>)
-    return bidirectional_iterator_tag();
-  else if constexpr (forward_iterator<_Iter>)
-    return forward_iterator_tag();
-  else if constexpr (input_iterator<_Iter>)
-    return input_iterator_tag();
-}
-
-template <class _Iter>
-using __iterator_concept = decltype(__get_iterator_concept<_Iter>());
-
 namespace ranges {
 namespace __find_end {
 struct __fn {
diff --git a/libcxx/include/__algorithm/ranges_for_each_n.h b/libcxx/include/__algorithm/ranges_for_each_n.h
index ddf8b047cdb2..013afbd19389 100644
--- a/libcxx/include/__algorithm/ranges_for_each_n.h
+++ b/libcxx/include/__algorithm/ranges_for_each_n.h
@@ -18,7 +18,6 @@
 #include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
diff --git a/libcxx/include/__algorithm/ranges_generate_n.h b/libcxx/include/__algorithm/ranges_generate_n.h
index bcf50e025ecc..7bde5fb4e579 100644
--- a/libcxx/include/__algorithm/ranges_generate_n.h
+++ b/libcxx/include/__algorithm/ranges_generate_n.h
@@ -23,7 +23,6 @@
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
diff --git a/libcxx/include/__algorithm/ranges_includes.h b/libcxx/include/__algorithm/ranges_includes.h
index 19c17870ed6f..ba054e6fd89d 100644
--- a/libcxx/include/__algorithm/ranges_includes.h
+++ b/libcxx/include/__algorithm/ranges_includes.h
@@ -9,8 +9,8 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_INCLUDES_H
 #define _LIBCPP___ALGORITHM_RANGES_INCLUDES_H
 
-#include <__algorithm/make_projected.h>
 #include <__algorithm/includes.h>
+#include <__algorithm/make_projected.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
@@ -20,7 +20,6 @@
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
@@ -36,29 +35,46 @@ namespace ranges {
 namespace __includes {
 
 struct __fn {
-
-  template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
-            class _Proj1 = identity, class _Proj2 = identity,
-            indirect_strict_weak_order<projected<_Iter1, _Proj1>, projected<_Iter2, _Proj2>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  bool operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Comp __comp = {},
-                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__first1; (void)__last1; (void)__first2; (void)__last2; (void)__comp; (void)__proj1; (void)__proj2;
-    return {};
+  template <
+      input_iterator _Iter1,
+      sentinel_for<_Iter1> _Sent1,
+      input_iterator _Iter2,
+      sentinel_for<_Iter2> _Sent2,
+      class _Proj1                                                                           = identity,
+      class _Proj2                                                                           = identity,
+      indirect_strict_weak_order<projected<_Iter1, _Proj1>, projected<_Iter2, _Proj2>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(
+      _Iter1 __first1,
+      _Sent1 __last1,
+      _Iter2 __first2,
+      _Sent2 __last2,
+      _Comp __comp   = {},
+      _Proj1 __proj1 = {},
+      _Proj2 __proj2 = {}) const {
+    return std::__includes(
+        std::move(__first1),
+        std::move(__last1),
+        std::move(__first2),
+        std::move(__last2),
+        ranges::__make_projected_comp(__comp, __proj1, __proj2));
   }
 
-  template <input_range _Range1, input_range _Range2, class _Proj1 = identity, class _Proj2 = identity,
-            indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
-                                       projected<iterator_t<_Range2>, _Proj2>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  bool operator()(_Range1&& __range1, _Range2&& __range2, _Comp __comp = {},
-                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__range1; (void)__range2; (void)__comp; (void)__proj1; (void)__proj2;
-    return {};
+  template <
+      input_range _Range1,
+      input_range _Range2,
+      class _Proj1 = identity,
+      class _Proj2 = identity,
+      indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, projected<iterator_t<_Range2>, _Proj2>>
+          _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(
+      _Range1&& __range1, _Range2&& __range2, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
+    return std::__includes(
+        ranges::begin(__range1),
+        ranges::end(__range1),
+        ranges::begin(__range2),
+        ranges::end(__range2),
+        ranges::__make_projected_comp(__comp, __proj1, __proj2));
   }
-
 };
 
 } // namespace __includes
diff --git a/libcxx/include/__algorithm/ranges_is_heap.h b/libcxx/include/__algorithm/ranges_is_heap.h
index 0f10fa4dcec9..00105189fed7 100644
--- a/libcxx/include/__algorithm/ranges_is_heap.h
+++ b/libcxx/include/__algorithm/ranges_is_heap.h
@@ -20,7 +20,6 @@
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
diff --git a/libcxx/include/__algorithm/ranges_iterator_concept.h b/libcxx/include/__algorithm/ranges_iterator_concept.h
new file mode 100644
index 000000000000..3323119317ae
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_iterator_concept.h
@@ -0,0 +1,51 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_ITERATOR_CONCEPT_H
+#define _LIBCPP___ALGORITHM_RANGES_ITERATOR_CONCEPT_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _IterMaybeQualified>
+consteval auto __get_iterator_concept() {
+  using _Iter = __uncvref_t<_IterMaybeQualified>;
+
+  if constexpr (contiguous_iterator<_Iter>)
+    return contiguous_iterator_tag();
+  else if constexpr (random_access_iterator<_Iter>)
+    return random_access_iterator_tag();
+  else if constexpr (bidirectional_iterator<_Iter>)
+    return bidirectional_iterator_tag();
+  else if constexpr (forward_iterator<_Iter>)
+    return forward_iterator_tag();
+  else if constexpr (input_iterator<_Iter>)
+    return input_iterator_tag();
+}
+
+template <class _Iter>
+using __iterator_concept = decltype(__get_iterator_concept<_Iter>());
+
+} // namespace ranges
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_ITERATOR_CONCEPT_H
diff --git a/libcxx/include/__algorithm/ranges_make_heap.h b/libcxx/include/__algorithm/ranges_make_heap.h
index fd488dc11a4b..8eabdd12cd2f 100644
--- a/libcxx/include/__algorithm/ranges_make_heap.h
+++ b/libcxx/include/__algorithm/ranges_make_heap.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/make_projected.h>
 #include <__concepts/same_as.h>
@@ -45,7 +46,7 @@ struct __fn {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__make_heap(std::move(__first), __last_iter, __projected_comp);
+    std::__make_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
diff --git a/libcxx/include/__algorithm/ranges_min_element.h b/libcxx/include/__algorithm/ranges_min_element.h
index ae82dceb9ad8..26f95fe3a6d2 100644
--- a/libcxx/include/__algorithm/ranges_min_element.h
+++ b/libcxx/include/__algorithm/ranges_min_element.h
@@ -30,6 +30,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
+// TODO(ranges): `ranges::min_element` can now simply delegate to `std::__min_element`.
 template <class _Ip, class _Sp, class _Proj, class _Comp>
 _LIBCPP_HIDE_FROM_ABI static constexpr
 _Ip __min_element_impl(_Ip __first, _Sp __last, _Comp& __comp, _Proj& __proj) {
diff --git a/libcxx/include/__algorithm/ranges_nth_element.h b/libcxx/include/__algorithm/ranges_nth_element.h
index 2a929eacb89d..b15eb816b918 100644
--- a/libcxx/include/__algorithm/ranges_nth_element.h
+++ b/libcxx/include/__algorithm/ranges_nth_element.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H
 #define _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/nth_element.h>
 #include <__config>
@@ -44,7 +45,7 @@ struct __fn {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__nth_element_impl(std::move(__first), std::move(__nth), __last_iter, __projected_comp);
+    std::__nth_element_impl<_RangeAlgPolicy>(std::move(__first), std::move(__nth), __last_iter, __projected_comp);
 
     return __last_iter;
   }
diff --git a/libcxx/include/__algorithm/ranges_partial_sort.h b/libcxx/include/__algorithm/ranges_partial_sort.h
new file mode 100644
index 000000000000..5e82bc6fcc32
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_partial_sort.h
@@ -0,0 +1,77 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_H
+#define _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/make_projected.h>
+#include <__algorithm/partial_sort.h>
+#include <__concepts/same_as.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/projected.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __partial_sort {
+
+struct __fn {
+  template <class _Iter, class _Sent, class _Comp, class _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  _Iter __partial_sort_fn_impl(_Iter __first, _Iter __middle, _Sent __last, _Comp& __comp, _Proj& __proj) {
+    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    return std::__partial_sort<_RangeAlgPolicy>(std::move(__first), std::move(__middle), __last, __projected_comp);
+  }
+
+  template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<_Iter, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __partial_sort_fn_impl(std::move(__first), std::move(__middle), std::move(__last), __comp, __proj);
+  }
+
+  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, iterator_t<_Range> __middle, _Comp __comp = {},
+                                         _Proj __proj = {}) const {
+    return __partial_sort_fn_impl(ranges::begin(__r), std::move(__middle), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __partial_sort
+
+inline namespace __cpo {
+  inline constexpr auto partial_sort = __partial_sort::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_H
diff --git a/libcxx/include/__algorithm/ranges_partition.h b/libcxx/include/__algorithm/ranges_partition.h
index c145e7bdb4a2..60bee699d90e 100644
--- a/libcxx/include/__algorithm/ranges_partition.h
+++ b/libcxx/include/__algorithm/ranges_partition.h
@@ -9,8 +9,10 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_PARTITION_H
 #define _LIBCPP___ALGORITHM_RANGES_PARTITION_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/partition.h>
+#include <__algorithm/ranges_iterator_concept.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
@@ -21,10 +23,10 @@
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
-#include <__ranges/dangling.h>
 #include <__ranges/subrange.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -39,13 +41,21 @@ namespace __partition {
 
 struct __fn {
 
+  template <class _Iter, class _Sent, class _Proj, class _Pred>
+  _LIBCPP_HIDE_FROM_ABI static constexpr
+  subrange<__uncvref_t<_Iter>> __partition_fn_impl(_Iter&& __first, _Sent&& __last, _Pred&& __pred, _Proj&& __proj) {
+    auto&& __projected_pred = ranges::__make_projected_pred(__pred, __proj);
+    auto __result = std::__partition<_RangeAlgPolicy>(
+        std::move(__first), std::move(__last), __projected_pred, __iterator_concept<_Iter>());
+
+    return {std::move(__result.first), std::move(__result.second)};
+  }
+
   template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   _LIBCPP_HIDE_FROM_ABI constexpr
   subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__pred; (void)__proj;
-    return {};
+    return __partition_fn_impl(__first, __last, __pred, __proj);
   }
 
   template <forward_range _Range, class _Proj = identity,
@@ -53,9 +63,7 @@ struct __fn {
   requires permutable<iterator_t<_Range>>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__pred; (void)__proj;
-    return {};
+    return __partition_fn_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
   }
 
 };
diff --git a/libcxx/include/__algorithm/ranges_partition_copy.h b/libcxx/include/__algorithm/ranges_partition_copy.h
index f55089b94ea5..7201a8cbfe45 100644
--- a/libcxx/include/__algorithm/ranges_partition_copy.h
+++ b/libcxx/include/__algorithm/ranges_partition_copy.h
@@ -10,20 +10,17 @@
 #define _LIBCPP___ALGORITHM_RANGES_PARTITION_COPY_H
 
 #include <__algorithm/in_out_out_result.h>
-#include <__algorithm/make_projected.h>
-#include <__algorithm/partition_copy.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
-#include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
-#include <__utility/forward.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -42,6 +39,27 @@ namespace __partition_copy {
 
 struct __fn {
 
+  // TODO(ranges): delegate to the classic algorithm.
+  template <class _InIter, class _Sent, class _OutIter1, class _OutIter2, class _Proj, class _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  static partition_copy_result<
+      __uncvref_t<_InIter>, __uncvref_t<_OutIter1>, __uncvref_t<_OutIter2>
+  > __partition_copy_fn_impl( _InIter&& __first, _Sent&& __last, _OutIter1&& __out_true, _OutIter2&& __out_false,
+      _Pred& __pred, _Proj& __proj) {
+    for (; __first != __last; ++__first) {
+      if (std::invoke(__pred, std::invoke(__proj, *__first))) {
+        *__out_true = *__first;
+        ++__out_true;
+
+      } else {
+        *__out_false = *__first;
+        ++__out_false;
+      }
+    }
+
+    return {std::move(__first), std::move(__out_true), std::move(__out_false)};
+  }
+
   template <input_iterator _InIter, sentinel_for<_InIter> _Sent,
             weakly_incrementable _OutIter1, weakly_incrementable _OutIter2,
             class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred>
@@ -50,9 +68,8 @@ struct __fn {
   partition_copy_result<_InIter, _OutIter1, _OutIter2>
   operator()(_InIter __first, _Sent __last, _OutIter1 __out_true, _OutIter2 __out_false,
              _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__out_true; (void)__out_false; (void)__pred; (void)__proj;
-    return {};
+    return __partition_copy_fn_impl(
+        std::move(__first), std::move(__last), std::move(__out_true), std::move(__out_false), __pred, __proj);
   }
 
   template <input_range _Range, weakly_incrementable _OutIter1, weakly_incrementable _OutIter2,
@@ -61,9 +78,8 @@ struct __fn {
   _LIBCPP_HIDE_FROM_ABI constexpr
   partition_copy_result<borrowed_iterator_t<_Range>, _OutIter1, _OutIter2>
   operator()(_Range&& __range, _OutIter1 __out_true, _OutIter2 __out_false, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__out_true; (void)__out_false; (void)__pred; (void)__proj;
-    return {};
+    return __partition_copy_fn_impl(
+        ranges::begin(__range), ranges::end(__range), std::move(__out_true), std::move(__out_false), __pred, __proj);
   }
 
 };
diff --git a/libcxx/include/__algorithm/ranges_partition_point.h b/libcxx/include/__algorithm/ranges_partition_point.h
index 336b29f63284..6614a0bb50fd 100644
--- a/libcxx/include/__algorithm/ranges_partition_point.h
+++ b/libcxx/include/__algorithm/ranges_partition_point.h
@@ -9,19 +9,18 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_PARTITION_POINT_H
 #define _LIBCPP___ALGORITHM_RANGES_PARTITION_POINT_H
 
-#include <__algorithm/make_projected.h>
-#include <__algorithm/partition_point.h>
+#include <__algorithm/half_positive.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
-#include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
-#include <__utility/forward.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -37,22 +36,40 @@ namespace __partition_point {
 
 struct __fn {
 
+  // TODO(ranges): delegate to the classic algorithm.
+  template <class _Iter, class _Sent, class _Proj, class _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  static _Iter __partition_point_fn_impl(_Iter&& __first, _Sent&& __last, _Pred& __pred, _Proj& __proj) {
+    auto __len = ranges::distance(__first, __last);
+
+    while (__len != 0) {
+      auto __half_len = std::__half_positive(__len);
+      auto __mid = ranges::next(__first, __half_len);
+
+      if (std::invoke(__pred, std::invoke(__proj, *__mid))) {
+        __first = ++__mid;
+        __len -= __half_len + 1;
+
+      } else {
+        __len = __half_len;
+      }
+    }
+
+    return __first;
+  }
+
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__pred; (void)__proj;
-    return {};
+    return __partition_point_fn_impl(std::move(__first), std::move(__last), __pred, __proj);
   }
 
   template <forward_range _Range, class _Proj = identity,
             indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_iterator_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__pred; (void)__proj;
-    return {};
+    return __partition_point_fn_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
   }
 
 };
diff --git a/libcxx/include/__algorithm/ranges_pop_heap.h b/libcxx/include/__algorithm/ranges_pop_heap.h
index d0b8314e5b0a..92df6119d34a 100644
--- a/libcxx/include/__algorithm/ranges_pop_heap.h
+++ b/libcxx/include/__algorithm/ranges_pop_heap.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/pop_heap.h>
 #include <__concepts/same_as.h>
@@ -46,7 +47,7 @@ struct __fn {
     auto __len = __last_iter - __first;
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__pop_heap(std::move(__first), __last_iter, __projected_comp, __len);
+    std::__pop_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp, __len);
 
     return __last_iter;
   }
diff --git a/libcxx/include/__algorithm/ranges_push_heap.h b/libcxx/include/__algorithm/ranges_push_heap.h
index e46ad19cfed7..4c41b00128de 100644
--- a/libcxx/include/__algorithm/ranges_push_heap.h
+++ b/libcxx/include/__algorithm/ranges_push_heap.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/push_heap.h>
 #include <__concepts/same_as.h>
@@ -45,7 +46,7 @@ struct __fn {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__push_heap(std::move(__first), __last_iter, __projected_comp);
+    std::__push_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
diff --git a/libcxx/include/__algorithm/ranges_set_union.h b/libcxx/include/__algorithm/ranges_set_union.h
index 39537503b98f..3826e55688f7 100644
--- a/libcxx/include/__algorithm/ranges_set_union.h
+++ b/libcxx/include/__algorithm/ranges_set_union.h
@@ -42,34 +42,68 @@ using set_union_result = in_in_out_result<_InIter1, _InIter2, _OutIter>;
 namespace __set_union {
 
 struct __fn {
-
-  template <input_iterator _InIter1, sentinel_for<_InIter1> _Sent1,
-            input_iterator _InIter2, sentinel_for<_InIter2> _Sent2,
-            weakly_incrementable _OutIter, class _Comp = ranges::less,
-            class _Proj1 = identity, class _Proj2 = identity>
-  requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  set_union_result<_InIter1, _InIter2, _OutIter>
-  operator()(_InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Comp __comp = {},
-            _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__first1; (void)__last1; (void)__first2; (void)__last2; (void)__result; (void)__comp; (void)__proj1;
-    (void)__proj2;
-    return {};
+  template <
+      input_iterator _InIter1,
+      sentinel_for<_InIter1> _Sent1,
+      input_iterator _InIter2,
+      sentinel_for<_InIter2> _Sent2,
+      weakly_incrementable _OutIter,
+      class _Comp  = ranges::less,
+      class _Proj1 = identity,
+      class _Proj2 = identity>
+    requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2>
+  _LIBCPP_HIDE_FROM_ABI constexpr set_union_result<_InIter1, _InIter2, _OutIter> operator()(
+      _InIter1 __first1,
+      _Sent1 __last1,
+      _InIter2 __first2,
+      _Sent2 __last2,
+      _OutIter __result,
+      _Comp __comp   = {},
+      _Proj1 __proj1 = {},
+      _Proj2 __proj2 = {}) const {
+    auto __ret = std::__set_union(
+        std::move(__first1),
+        std::move(__last1),
+        std::move(__first2),
+        std::move(__last2),
+        std::move(__result),
+        ranges::__make_projected_comp(__comp, __proj1, __proj2));
+    return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
   }
 
-  template <input_range _Range1, input_range _Range2, weakly_incrementable _OutIter,
-            class _Comp = ranges::less, class _Proj1 = identity, class _Proj2 = identity>
-  requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _OutIter, _Comp, _Proj1, _Proj2>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  set_union_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>, _OutIter>
-  operator()(_Range1&& __range1, _Range2&& __range2, _OutIter __result, _Comp __comp = {},
-            _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__range1; (void)__range2; (void)__result; (void)__comp; (void)__proj1; (void)__proj2;
-    return {};
+  template <
+      input_range _Range1,
+      input_range _Range2,
+      weakly_incrementable _OutIter,
+      class _Comp  = ranges::less,
+      class _Proj1 = identity,
+      class _Proj2 = identity>
+    requires mergeable<
+        iterator_t<_Range1>,
+        iterator_t<_Range2>,
+        _OutIter,
+        _Comp,
+        _Proj1,
+        _Proj2> 
+  _LIBCPP_HIDE_FROM_ABI constexpr set_union_result<borrowed_iterator_t<_Range1>,
+                                                   borrowed_iterator_t<_Range2>,
+                                                   _OutIter>
+    operator()(
+        _Range1&& __range1,
+        _Range2&& __range2,
+        _OutIter __result,
+        _Comp __comp   = {},
+        _Proj1 __proj1 = {},
+        _Proj2 __proj2 = {}) const {
+    auto __ret = std::__set_union(
+        ranges::begin(__range1),
+        ranges::end(__range1),
+        ranges::begin(__range2),
+        ranges::end(__range2),
+        std::move(__result),
+        ranges::__make_projected_comp(__comp, __proj1, __proj2));
+    return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
   }
-
 };
 
 } // namespace __set_union
diff --git a/libcxx/include/__algorithm/ranges_shuffle.h b/libcxx/include/__algorithm/ranges_shuffle.h
index bf9c28b4ce26..b101a8582eac 100644
--- a/libcxx/include/__algorithm/ranges_shuffle.h
+++ b/libcxx/include/__algorithm/ranges_shuffle.h
@@ -9,23 +9,22 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
 #define _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
 
-#include <__algorithm/make_projected.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/shuffle.h>
 #include <__config>
-#include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 #include <__iterator/permutable.h>
-#include <__iterator/projected.h>
 #include <__random/uniform_random_bit_generator.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
-#include <__type_traits/remove_reference.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -33,29 +32,57 @@
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 namespace __shuffle {
 
 struct __fn {
+  // `std::shuffle` is more constrained than `std::ranges::shuffle`. `std::ranges::shuffle` only requires the given
+  // generator to satisfy the `std::uniform_random_bit_generator` concept. `std::shuffle` requires the given
+  // generator to meet the uniform random bit generator requirements; these requirements include satisfying
+  // `std::uniform_random_bit_generator` and add a requirement for the generator to provide a nested `result_type`
+  // typedef (see `[rand.req.urng]`).
+  //
+  // To reuse the implementation from `std::shuffle`, make the given generator meet the classic requirements by wrapping
+  // it into an adaptor type that forwards all of its interface and adds the required typedef.
+  template <class _Gen>
+  class _ClassicGenAdaptor {
+  private:
+    // The generator is not required to be copyable or movable, so it has to be stored as a reference.
+    _Gen& __gen;
+
+  public:
+    using result_type = invoke_result_t<_Gen&>;
+
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto min() { return __uncvref_t<_Gen>::min(); }
+    _LIBCPP_HIDE_FROM_ABI
+    static constexpr auto max() { return __uncvref_t<_Gen>::max(); }
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr explicit _ClassicGenAdaptor(_Gen& __g) : __gen(__g) {}
+
+    _LIBCPP_HIDE_FROM_ABI
+    constexpr auto operator()() const { return __gen(); }
+  };
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Gen>
   requires permutable<_Iter> && uniform_random_bit_generator<remove_reference_t<_Gen>>
   _LIBCPP_HIDE_FROM_ABI
   _Iter operator()(_Iter __first, _Sent __last, _Gen&& __gen) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__gen;
-    return {};
+    _ClassicGenAdaptor<_Gen> __adapted_gen(__gen);
+    return std::__shuffle<_RangeAlgPolicy>(std::move(__first), std::move(__last), __adapted_gen);
   }
 
   template<random_access_range _Range, class _Gen>
   requires permutable<iterator_t<_Range>> && uniform_random_bit_generator<remove_reference_t<_Gen>>
   _LIBCPP_HIDE_FROM_ABI
   borrowed_iterator_t<_Range> operator()(_Range&& __range, _Gen&& __gen) const {
-    // TODO: implement
-    (void)__range; (void)__gen;
-    return {};
+    return (*this)(ranges::begin(__range), ranges::end(__range), std::forward<_Gen>(__gen));
   }
 
 };
@@ -69,6 +96,8 @@ inline namespace __cpo {
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H
diff --git a/libcxx/include/__algorithm/ranges_sort.h b/libcxx/include/__algorithm/ranges_sort.h
index 8297940df237..ef14db64295d 100644
--- a/libcxx/include/__algorithm/ranges_sort.h
+++ b/libcxx/include/__algorithm/ranges_sort.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H
 #define _LIBCPP___ALGORITHM_RANGES_SORT_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/sort.h>
 #include <__config>
@@ -44,7 +45,7 @@ struct __fn {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__sort_impl(std::move(__first), __last_iter, __projected_comp);
+    std::__sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
diff --git a/libcxx/include/__algorithm/ranges_sort_heap.h b/libcxx/include/__algorithm/ranges_sort_heap.h
index c753e20c44a6..eb6a30dcd3d0 100644
--- a/libcxx/include/__algorithm/ranges_sort_heap.h
+++ b/libcxx/include/__algorithm/ranges_sort_heap.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/sort_heap.h>
 #include <__concepts/same_as.h>
@@ -45,7 +46,7 @@ struct __fn {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__sort_heap(std::move(__first), __last_iter, __projected_comp);
+    std::__sort_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
diff --git a/libcxx/include/__algorithm/ranges_stable_partition.h b/libcxx/include/__algorithm/ranges_stable_partition.h
index 178c953ebdae..27957db8829f 100644
--- a/libcxx/include/__algorithm/ranges_stable_partition.h
+++ b/libcxx/include/__algorithm/ranges_stable_partition.h
@@ -9,7 +9,9 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_STABLE_PARTITION_H
 #define _LIBCPP___ALGORITHM_RANGES_STABLE_PARTITION_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
+#include <__algorithm/ranges_iterator_concept.h>
 #include <__algorithm/stable_partition.h>
 #include <__config>
 #include <__functional/identity.h>
@@ -17,6 +19,7 @@
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 #include <__iterator/permutable.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
@@ -25,6 +28,7 @@
 #include <__ranges/subrange.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -39,14 +43,25 @@ namespace __stable_partition {
 
 struct __fn {
 
+  template <class _Iter, class _Sent, class _Proj, class _Pred>
+  _LIBCPP_HIDE_FROM_ABI static
+  subrange<__uncvref_t<_Iter>> __stable_partition_fn_impl(
+      _Iter&& __first, _Sent&& __last, _Pred&& __pred, _Proj&& __proj) {
+    auto __last_iter = ranges::next(__first, __last);
+
+    auto&& __projected_pred = ranges::__make_projected_pred(__pred, __proj);
+    auto __result = std::__stable_partition<_RangeAlgPolicy>(
+        std::move(__first), __last_iter, __projected_pred, __iterator_concept<_Iter>());
+
+    return {std::move(__result), std::move(__last_iter)};
+  }
+
   template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   requires permutable<_Iter>
   _LIBCPP_HIDE_FROM_ABI
   subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__pred; (void)__proj;
-    return {};
+    return __stable_partition_fn_impl(__first, __last, __pred, __proj);
   }
 
   template <bidirectional_range _Range, class _Proj = identity,
@@ -54,9 +69,7 @@ struct __fn {
   requires permutable<iterator_t<_Range>>
   _LIBCPP_HIDE_FROM_ABI
   borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__pred; (void)__proj;
-    return {};
+    return __stable_partition_fn_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
   }
 
 };
diff --git a/libcxx/include/__algorithm/ranges_stable_sort.h b/libcxx/include/__algorithm/ranges_stable_sort.h
index 20e840426434..de48416a41be 100644
--- a/libcxx/include/__algorithm/ranges_stable_sort.h
+++ b/libcxx/include/__algorithm/ranges_stable_sort.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H
 #define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/stable_sort.h>
 #include <__config>
@@ -44,7 +45,7 @@ struct __fn {
     auto __last_iter = ranges::next(__first, __last);
 
     auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
-    std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp);
+    std::__stable_sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
 
     return __last_iter;
   }
diff --git a/libcxx/include/__algorithm/rotate.h b/libcxx/include/__algorithm/rotate.h
index c9ea5bad4c5a..fcf8444a65a0 100644
--- a/libcxx/include/__algorithm/rotate.h
+++ b/libcxx/include/__algorithm/rotate.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_ROTATE_H
 #define _LIBCPP___ALGORITHM_ROTATE_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/move.h>
 #include <__algorithm/move_backward.h>
 #include <__algorithm/swap_ranges.h>
@@ -26,37 +27,40 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _ForwardIterator>
+template <class _AlgPolicy, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
-    value_type __tmp = _VSTD::move(*__first);
+    value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__first);
+    // TODO(ranges): pass `_AlgPolicy` to `move`.
     _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
     *__lm1 = _VSTD::move(__tmp);
     return __lm1;
 }
 
-template <class _BidirectionalIterator>
+template <class _AlgPolicy, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+    // TODO(ranges): pass `_AlgPolicy` to `prev`.
     _BidirectionalIterator __lm1 = _VSTD::prev(__last);
-    value_type __tmp = _VSTD::move(*__lm1);
+    value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__lm1);
+    // TODO(ranges): pass `_AlgPolicy` to `move_backward`.
     _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
     *__first = _VSTD::move(__tmp);
     return __fp1;
 }
 
-template <class _ForwardIterator>
+template <class _AlgPolicy, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX14 _ForwardIterator
 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
     _ForwardIterator __i = __middle;
     while (true)
     {
-        swap(*__first, *__i);
+        _IterOps<_AlgPolicy>::iter_swap(__first, __i);
         ++__first;
         if (++__i == __last)
             break;
@@ -69,7 +73,7 @@ __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIt
         __i = __middle;
         while (true)
         {
-            swap(*__first, *__i);
+            _IterOps<_AlgPolicy>::iter_swap(__first, __i);
             ++__first;
             if (++__i == __last)
             {
@@ -98,7 +102,7 @@ __algo_gcd(_Integral __x, _Integral __y)
     return __x;
 }
 
-template<typename _RandomAccessIterator>
+template <class _AlgPolicy, typename _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
@@ -109,18 +113,19 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran
     const difference_type __m2 = __last - __middle;
     if (__m1 == __m2)
     {
+        // TODO(ranges): pass `_AlgPolicy` to `swap_ranges`.
         _VSTD::swap_ranges(__first, __middle, __middle);
         return __middle;
     }
     const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
     {
-        value_type __t(_VSTD::move(*--__p));
+        value_type __t(_IterOps<_AlgPolicy>::__iter_move(--__p));
         _RandomAccessIterator __p1 = __p;
         _RandomAccessIterator __p2 = __p1 + __m1;
         do
         {
-            *__p1 = _VSTD::move(*__p2);
+            *__p1 = _IterOps<_AlgPolicy>::__iter_move(__p2);
             __p1 = __p2;
             const difference_type __d = __last - __p2;
             if (__m1 < __d)
@@ -133,54 +138,66 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran
     return __first + __m2;
 }
 
-template <class _ForwardIterator>
+template <class _AlgPolicy, class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator
-__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
+__rotate_impl(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
          _VSTD::forward_iterator_tag)
 {
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
     if (is_trivially_move_assignable<value_type>::value)
     {
-        if (_VSTD::next(__first) == __middle)
-            return _VSTD::__rotate_left(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+            return std::__rotate_left<_AlgPolicy>(__first, __last);
     }
-    return _VSTD::__rotate_forward(__first, __middle, __last);
+    return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
 }
 
-template <class _BidirectionalIterator>
+template <class _AlgPolicy, class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _BidirectionalIterator
-__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
+__rotate_impl(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
          bidirectional_iterator_tag)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     if (is_trivially_move_assignable<value_type>::value)
     {
-        if (_VSTD::next(__first) == __middle)
-            return _VSTD::__rotate_left(__first, __last);
-        if (_VSTD::next(__middle) == __last)
-            return _VSTD::__rotate_right(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+            return std::__rotate_left<_AlgPolicy>(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__middle) == __last)
+            return std::__rotate_right<_AlgPolicy>(__first, __last);
     }
-    return _VSTD::__rotate_forward(__first, __middle, __last);
+    return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
 }
 
-template <class _RandomAccessIterator>
+template <class _AlgPolicy, class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
-__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
+__rotate_impl(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
          random_access_iterator_tag)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     if (is_trivially_move_assignable<value_type>::value)
     {
-        if (_VSTD::next(__first) == __middle)
-            return _VSTD::__rotate_left(__first, __last);
-        if (_VSTD::next(__middle) == __last)
-            return _VSTD::__rotate_right(__first, __last);
-        return _VSTD::__rotate_gcd(__first, __middle, __last);
+        if (_IterOps<_AlgPolicy>::next(__first) == __middle)
+            return std::__rotate_left<_AlgPolicy>(__first, __last);
+        if (_IterOps<_AlgPolicy>::next(__middle) == __last)
+            return std::__rotate_right<_AlgPolicy>(__first, __last);
+        return std::__rotate_gcd<_AlgPolicy>(__first, __middle, __last);
     }
-    return _VSTD::__rotate_forward(__first, __middle, __last);
+    return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last);
+}
+
+template <class _AlgPolicy, class _RandomAccessIterator, class _IterCategory>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+_RandomAccessIterator __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle,
+    _RandomAccessIterator __last, _IterCategory __iter_category) {
+  if (__first == __middle)
+      return __last;
+  if (__middle == __last)
+      return __first;
+
+  return std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __iter_category);
 }
 
 template <class _ForwardIterator>
@@ -188,12 +205,8 @@ inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
 {
-    if (__first == __middle)
-        return __last;
-    if (__middle == __last)
-        return __first;
-    return _VSTD::__rotate(__first, __middle, __last,
-                           typename iterator_traits<_ForwardIterator>::iterator_category());
+  return std::__rotate<_ClassicAlgPolicy>(__first, __middle, __last,
+                                          typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h
index 2a0547565ee9..ccb8e845f5b1 100644
--- a/libcxx/include/__algorithm/search_n.h
+++ b/libcxx/include/__algorithm/search_n.h
@@ -163,7 +163,7 @@ _ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last,
                           _Size __count,
                           const _Tp& __value,
                           _BinaryPredicate __pred) {
-  static_assert(__is_callable<_BinaryPredicate, decltype(*__first), decltype(*__last)>::value,
+  static_assert(__is_callable<_BinaryPredicate, decltype(*__first), const _Tp&>::value,
                 "BinaryPredicate has to be callable");
   auto __proj = __identity();
   return std::__search_n_impl(__first, __last, std::__convert_to_integral(__count), __value, __pred, __proj).first;
diff --git a/libcxx/include/__algorithm/set_union.h b/libcxx/include/__algorithm/set_union.h
index 0ec6b09380ed..3bd437980161 100644
--- a/libcxx/include/__algorithm/set_union.h
+++ b/libcxx/include/__algorithm/set_union.h
@@ -14,6 +14,7 @@
 #include <__algorithm/copy.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -21,50 +22,77 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
-__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
-            _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
-{
-    for (; __first1 != __last1; ++__result)
-    {
-        if (__first2 == __last2)
-            return _VSTD::copy(__first1, __last1, __result);
-        if (__comp(*__first2, *__first1))
-        {
-            *__result = *__first2;
-            ++__first2;
-        }
-        else
-        {
-            if (!__comp(*__first1, *__first2))
-                ++__first2;
-            *__result = *__first1;
-            ++__first1;
-        }
+template <class _InIter1, class _InIter2, class _OutIter>
+struct __set_union_result {
+  _InIter1 __in1_;
+  _InIter2 __in2_;
+  _OutIter __out_;
+
+  // need a constructor as C++03 aggregate init is hard
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+  __set_union_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)
+      : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {}
+};
+
+template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 __set_union_result<_InIter1, _InIter2, _OutIter> __set_union(
+    _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) {
+  for (; __first1 != __last1; ++__result) {
+    if (__first2 == __last2) {
+      auto __ret1 = std::__copy_impl(std::move(__first1), std::move(__last1), std::move(__result));
+      return __set_union_result<_InIter1, _InIter2, _OutIter>(
+          std::move(__ret1.first), std::move(__first2), std::move((__ret1.second)));
+    }
+    if (__comp(*__first2, *__first1)) {
+      *__result = *__first2;
+      ++__first2;
+    } else {
+      if (!__comp(*__first1, *__first2)) {
+        ++__first2;
+      }
+      *__result = *__first1;
+      ++__first1;
     }
-    return _VSTD::copy(__first2, __last2, __result);
+  }
+  auto __ret2 = std::__copy_impl(std::move(__first2), std::move(__last2), std::move(__result));
+  return __set_union_result<_InIter1, _InIter2, _OutIter>(
+      std::move(__first1), std::move(__ret2.first), std::move((__ret2.second)));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-set_union(_InputIterator1 __first1, _InputIterator1 __last1,
-          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_union(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _OutputIterator __result,
+    _Compare __comp) {
+  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+  return std::__set_union<_Comp_ref>(
+             std::move(__first1),
+             std::move(__last1),
+             std::move(__first2),
+             std::move(__last2),
+             std::move(__result),
+             __comp)
+      .__out_;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-set_union(_InputIterator1 __first1, _InputIterator1 __last1,
-          _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
-{
-    return _VSTD::set_union(__first1, __last1, __first2, __last2, __result,
-                          __less<typename iterator_traits<_InputIterator1>::value_type,
-                                 typename iterator_traits<_InputIterator2>::value_type>());
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_union(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _OutputIterator __result) {
+  return std::set_union(
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__last2),
+      std::move(__result),
+      __less<typename iterator_traits<_InputIterator1>::value_type,
+             typename iterator_traits<_InputIterator2>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/shuffle.h b/libcxx/include/__algorithm/shuffle.h
index 6c6ff5675dad..e32c6a7608ba 100644
--- a/libcxx/include/__algorithm/shuffle.h
+++ b/libcxx/include/__algorithm/shuffle.h
@@ -9,11 +9,13 @@
 #ifndef _LIBCPP___ALGORITHM_SHUFFLE_H
 #define _LIBCPP___ALGORITHM_SHUFFLE_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__debug>
 #include <__iterator/iterator_traits.h>
 #include <__random/uniform_int_distribution.h>
-#include <__utility/swap.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
 #include <cstddef>
 #include <cstdint>
 
@@ -134,13 +136,15 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
 }
 #endif
 
-template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
-    void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
-                 _UniformRandomNumberGenerator&& __g)
-{
+template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel, class _UniformRandomNumberGenerator>
+_RandomAccessIterator __shuffle(
+    _RandomAccessIterator __first, _Sentinel __last_sentinel, _UniformRandomNumberGenerator&& __g) {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef uniform_int_distribution<ptrdiff_t> _Dp;
     typedef typename _Dp::param_type _Pp;
+
+    auto __original_last = _IterOps<_AlgPolicy>::next(__first, __last_sentinel);
+    auto __last = __original_last;
     difference_type __d = __last - __first;
     if (__d > 1)
     {
@@ -149,9 +153,18 @@ template<class _RandomAccessIterator, class _UniformRandomNumberGenerator>
         {
             difference_type __i = __uid(__g, _Pp(0, __d));
             if (__i != difference_type(0))
-                swap(*__first, *(__first + __i));
+                _IterOps<_AlgPolicy>::iter_swap(__first, __first + __i);
         }
     }
+
+    return __original_last;
+}
+
+template <class _RandomAccessIterator, class _UniformRandomNumberGenerator>
+void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
+             _UniformRandomNumberGenerator&& __g) {
+  (void)std::__shuffle<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), std::forward<_UniformRandomNumberGenerator>(__g));
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h
index 0351a1c578b0..be2eb29dd53a 100644
--- a/libcxx/include/__algorithm/sift_down.h
+++ b/libcxx/include/__algorithm/sift_down.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H
 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
@@ -20,12 +21,14 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __sift_down(_RandomAccessIterator __first, _Compare __comp,
             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
             _RandomAccessIterator __start)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     // left-child of __start is at 2 * __start + 1
@@ -49,11 +52,11 @@ __sift_down(_RandomAccessIterator __first, _Compare __comp,
         // we are, __start is larger than its largest child
         return;
 
-    value_type __top(_VSTD::move(*__start));
+    value_type __top(_Ops::__iter_move(__start));
     do
     {
         // we are not in heap-order, swap the parent with its largest child
-        *__start = _VSTD::move(*__child_i);
+        *__start = _Ops::__iter_move(__child_i);
         __start = __child_i;
 
         if ((__len - 2) / 2 < __child)
@@ -74,7 +77,7 @@ __sift_down(_RandomAccessIterator __first, _Compare __comp,
     *__start = _VSTD::move(__top);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
 __floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
                   typename iterator_traits<_RandomAccessIterator>::difference_type __len)
@@ -97,7 +100,7 @@ __floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
         }
 
         // swap __hole with its largest child
-        *__hole = std::move(*__child_i);
+        *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i);
         __hole = __child_i;
 
         // if __hole is now a leaf, we're done
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
index 76a18215731b..1ca2f1b81712 100644
--- a/libcxx/include/__algorithm/sort.h
+++ b/libcxx/include/__algorithm/sort.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
@@ -21,7 +22,6 @@
 #include <__functional/operations.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
 #include <climits>
 #include <memory>
 
@@ -31,37 +31,85 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+// Wraps an algorithm policy tag and a comparator in a single struct, used to pass the policy tag around without
+// changing the number of template arguments (to keep the ABI stable). This is only used for the "range" policy tag.
+//
+// To create an object of this type, use `_WrapAlgPolicy<T, C>::type` -- see the specialization below for the rationale.
+template <class _PolicyT, class _CompT, class = void>
+struct _WrapAlgPolicy {
+  using type = _WrapAlgPolicy;
+
+  using _AlgPolicy = _PolicyT;
+  using _Comp = _CompT;
+  _Comp& __comp;
+
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+  _WrapAlgPolicy(_Comp& __c) : __comp(__c) {}
+};
+
+// Specialization for the "classic" policy tag that avoids creating a struct and simply defines an alias for the
+// comparator. When unwrapping, a pristine comparator is always considered to have the "classic" tag attached. Passing
+// the pristine comparator where possible allows using template instantiations from the dylib.
+template <class _PolicyT, class _CompT>
+struct _WrapAlgPolicy<_PolicyT, _CompT, __enable_if_t<std::is_same<_PolicyT, _ClassicAlgPolicy>::value> > {
+  using type = _CompT;
+};
+
+// Unwraps a pristine functor (e.g. `std::less`) as if it were wrapped using `_WrapAlgPolicy`. The policy tag is always
+// set to "classic".
+template <class _CompT>
+struct _UnwrapAlgPolicy {
+  using _AlgPolicy = _ClassicAlgPolicy;
+  using _Comp = _CompT;
+
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 static
+  _Comp __get_comp(_Comp __comp) { return __comp; }
+};
+
+// Unwraps a `_WrapAlgPolicy` struct.
+template <class... _Ts>
+struct _UnwrapAlgPolicy<_WrapAlgPolicy<_Ts...> > {
+  using _Wrapped = _WrapAlgPolicy<_Ts...>;
+  using _AlgPolicy = typename _Wrapped::_AlgPolicy;
+  using _Comp = typename _Wrapped::_Comp;
+
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 static
+  _Comp __get_comp(_Wrapped& __w) { return __w.__comp; }
+};
+
 // stable, 2-3 compares, 0-2 swaps
 
-template <class _Compare, class _ForwardIterator>
+template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z,
                                                _Compare __c) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   unsigned __r = 0;
   if (!__c(*__y, *__x))   // if x <= y
   {
     if (!__c(*__z, *__y)) // if y <= z
       return __r;         // x <= y && y <= z
                           // x <= y && y > z
-    swap(*__y, *__z);     // x <= z && y < z
+    _Ops::iter_swap(__y, __z);     // x <= z && y < z
     __r = 1;
     if (__c(*__y, *__x))  // if x > y
     {
-      swap(*__x, *__y);   // x < y && y <= z
+      _Ops::iter_swap(__x, __y);   // x < y && y <= z
       __r = 2;
     }
     return __r;           // x <= y && y < z
   }
   if (__c(*__z, *__y))    // x > y, if y > z
   {
-    swap(*__x, *__z);     // x < y && y < z
+    _Ops::iter_swap(__x, __z);     // x < y && y < z
     __r = 1;
     return __r;
   }
-  swap(*__x, *__y);       // x > y && y <= z
+  _Ops::iter_swap(__x, __y);       // x > y && y <= z
   __r = 1;                // x < y && x <= z
   if (__c(*__z, *__y))    // if y > z
   {
-    swap(*__y, *__z);     // x <= y && y < z
+    _Ops::iter_swap(__y, __z);     // x <= y && y < z
     __r = 2;
   }
   return __r;
@@ -69,18 +117,20 @@ _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned __sort3(_ForwardIterator __x, _ForwardIte
 
 // stable, 3-6 compares, 0-5 swaps
 
-template <class _Compare, class _ForwardIterator>
+template <class _AlgPolicy, class _Compare, class _ForwardIterator>
 unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
                  _Compare __c) {
-  unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
+  using _Ops = _IterOps<_AlgPolicy>;
+
+  unsigned __r = std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
   if (__c(*__x4, *__x3)) {
-    swap(*__x3, *__x4);
+    _Ops::iter_swap(__x3, __x4);
     ++__r;
     if (__c(*__x3, *__x2)) {
-      swap(*__x2, *__x3);
+      _Ops::iter_swap(__x2, __x3);
       ++__r;
       if (__c(*__x2, *__x1)) {
-        swap(*__x1, *__x2);
+        _Ops::iter_swap(__x1, __x2);
         ++__r;
       }
     }
@@ -90,21 +140,28 @@ unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator
 
 // stable, 4-10 compares, 0-9 swaps
 
-template <class _Compare, class _ForwardIterator>
+template <class _WrappedComp, class _ForwardIterator>
 _LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
-                                _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) {
-  unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
+                                _ForwardIterator __x4, _ForwardIterator __x5, _WrappedComp __wrapped_comp) {
+  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
+  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
+  using _Ops = _IterOps<_AlgPolicy>;
+
+  using _Compare = typename _Unwrap::_Comp;
+  _Compare __c = _Unwrap::__get_comp(__wrapped_comp);
+
+  unsigned __r = std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
   if (__c(*__x5, *__x4)) {
-    swap(*__x4, *__x5);
+    _Ops::iter_swap(__x4, __x5);
     ++__r;
     if (__c(*__x4, *__x3)) {
-      swap(*__x3, *__x4);
+      _Ops::iter_swap(__x3, __x4);
       ++__r;
       if (__c(*__x3, *__x2)) {
-        swap(*__x2, *__x3);
+        _Ops::iter_swap(__x2, __x3);
         ++__r;
         if (__c(*__x2, *__x1)) {
-          swap(*__x1, *__x2);
+          _Ops::iter_swap(__x1, __x2);
           ++__r;
         }
       }
@@ -113,6 +170,16 @@ _LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _F
   return __r;
 }
 
+template <class _AlgPolicy, class _Compare, class _ForwardIterator>
+_LIBCPP_HIDDEN unsigned __sort5_wrap_policy(
+    _ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5,
+    _Compare __c) {
+  using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
+  _WrappedComp __wrapped_comp(__c);
+  return std::__sort5<_WrappedComp>(
+      std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __wrapped_comp);
+}
+
 // The comparator being simple is a prerequisite for using the branchless optimization.
 template <class _Tp>
 struct __is_simple_comparator : false_type {};
@@ -137,6 +204,7 @@ using __use_branchless_sort =
 // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary.
 template <class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) {
+  // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`).
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   bool __r = __c(*__x, *__y);
   value_type __tmp = __r ? *__x : *__y;
@@ -149,6 +217,7 @@ inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _Random
 template <class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y,
                                                           _RandomAccessIterator __z, _Compare __c) {
+  // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`).
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   bool __r = __c(*__z, *__x);
   value_type __tmp = __r ? *__z : *__x;
@@ -158,7 +227,7 @@ inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator
   *__y = __r ? *__y : __tmp;
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _Compare __c) {
@@ -166,14 +235,14 @@ __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2,
   _VSTD::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _Compare __c) {
-  _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
+  std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _Compare __c) {
@@ -184,14 +253,14 @@ __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2,
   _VSTD::__cond_swap<_Compare>(__x2, __x3, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _Compare __c) {
-  _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
+  std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
@@ -203,53 +272,57 @@ __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2,
   _VSTD::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
                          _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
-  _VSTD::__sort5<_Compare>(__x1, __x2, __x3, __x4, __x5, __c);
+  std::__sort5_wrap_policy<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c);
 }
 
 // Assumes size > 0
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last,
                                                     _Compare __comp) {
   _BidirectionalIterator __lm1 = __last;
   for (--__lm1; __first != __lm1; ++__first) {
-    _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp);
+    _BidirectionalIterator __i = std::__min_element<_Compare>(__first, __last, __comp);
     if (__i != __first)
-      swap(*__first, *__i);
+      _IterOps<_AlgPolicy>::iter_swap(__first, __i);
   }
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
   if (__first != __last) {
     _BidirectionalIterator __i = __first;
     for (++__i; __i != __last; ++__i) {
       _BidirectionalIterator __j = __i;
-      value_type __t(_VSTD::move(*__j));
+      value_type __t(_Ops::__iter_move(__j));
       for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
-        *__j = _VSTD::move(*__k);
+        *__j = _Ops::__iter_move(__k);
       *__j = _VSTD::move(__t);
     }
   }
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   _RandomAccessIterator __j = __first + difference_type(2);
-  _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp);
+  std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp);
   for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
     if (__comp(*__i, *__j)) {
-      value_type __t(_VSTD::move(*__i));
+      value_type __t(_Ops::__iter_move(__i));
       _RandomAccessIterator __k = __j;
       __j = __i;
       do {
-        *__j = _VSTD::move(*__k);
+        *__j = _Ops::__iter_move(__k);
         __j = __k;
       } while (__j != __first && __comp(__t, *--__k));
       *__j = _VSTD::move(__t);
@@ -258,8 +331,16 @@ void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __l
   }
 }
 
-template <class _Compare, class _RandomAccessIterator>
-bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+template <class _WrappedComp, class _RandomAccessIterator>
+bool __insertion_sort_incomplete(
+    _RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) {
+  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
+  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
+  using _Ops = _IterOps<_AlgPolicy>;
+
+  using _Compare = typename _Unwrap::_Comp;
+  _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
+
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   switch (__last - __first) {
   case 0:
@@ -267,32 +348,33 @@ bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIte
     return true;
   case 2:
     if (__comp(*--__last, *__first))
-      swap(*__first, *__last);
+      _IterOps<_AlgPolicy>::iter_swap(__first, __last);
     return true;
   case 3:
-    _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+    std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
     return true;
   case 4:
-    _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                              --__last, __comp);
+    std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
+        __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
     return true;
   case 5:
-    _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                              __first + difference_type(3), --__last, __comp);
+    std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
+        __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3),
+        --__last, __comp);
     return true;
   }
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   _RandomAccessIterator __j = __first + difference_type(2);
-  _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp);
+  std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp);
   const unsigned __limit = 8;
   unsigned __count = 0;
   for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
     if (__comp(*__i, *__j)) {
-      value_type __t(_VSTD::move(*__i));
+      value_type __t(_Ops::__iter_move(__i));
       _RandomAccessIterator __k = __j;
       __j = __i;
       do {
-        *__j = _VSTD::move(*__k);
+        *__j = _Ops::__iter_move(__k);
         __j = __k;
       } while (__j != __first && __comp(__t, *--__k));
       *__j = _VSTD::move(__t);
@@ -304,27 +386,29 @@ bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIte
   return true;
 }
 
-template <class _Compare, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1,
                            typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
   if (__first1 != __last1) {
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
     value_type* __last2 = __first2;
-    ::new ((void*)__last2) value_type(_VSTD::move(*__first1));
+    ::new ((void*)__last2) value_type(_Ops::__iter_move(__first1));
     __d.template __incr<value_type>();
     for (++__last2; ++__first1 != __last1; ++__last2) {
       value_type* __j2 = __last2;
       value_type* __i2 = __j2;
       if (__comp(*__first1, *--__i2)) {
-        ::new ((void*)__j2) value_type(_VSTD::move(*__i2));
+        ::new ((void*)__j2) value_type(std::move(*__i2));
         __d.template __incr<value_type>();
         for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
-          *__j2 = _VSTD::move(*__i2);
-        *__j2 = _VSTD::move(*__first1);
+          *__j2 = std::move(*__i2);
+        *__j2 = _Ops::__iter_move(__first1);
       } else {
-        ::new ((void*)__j2) value_type(_VSTD::move(*__first1));
+        ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1));
         __d.template __incr<value_type>();
       }
     }
@@ -332,9 +416,11 @@ void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterat
   }
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
                  typename iterator_traits<_RandomAccessIterator>::difference_type __depth) {
+  using _Ops = _IterOps<_AlgPolicy>;
+
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   const difference_type __limit =
@@ -348,28 +434,29 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
       return;
     case 2:
       if (__comp(*--__last, *__first))
-        swap(*__first, *__last);
+        _IterOps<_AlgPolicy>::iter_swap(__first, __last);
       return;
     case 3:
-      _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+      std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
       return;
     case 4:
-      _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                                --__last, __comp);
+      std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
+          __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
       return;
     case 5:
-      _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
-                                                __first + difference_type(3), --__last, __comp);
+      std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
+          __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3),
+          --__last, __comp);
       return;
     }
     if (__len <= __limit) {
-      _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
+      std::__insertion_sort_3<_AlgPolicy, _Compare>(__first, __last, __comp);
       return;
     }
     // __len > 5
     if (__depth == 0) {
       // Fallback to heap sort as Introsort suggests.
-      _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
+      std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp);
       return;
     }
     --__depth;
@@ -383,11 +470,12 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
         __delta = __len / 2;
         __m += __delta;
         __delta /= 2;
-        __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp);
+        __n_swaps = std::__sort5_wrap_policy<_AlgPolicy, _Compare>(
+            __first, __first + __delta, __m, __m + __delta, __lm1, __comp);
       } else {
         __delta = __len / 2;
         __m += __delta;
-        __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
+        __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, __lm1, __comp);
       }
     }
     // *__m is median
@@ -414,7 +502,7 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
               if (__i == __j)
                 return; // [__first, __last) all equivalent elements
               if (__comp(*__first, *__i)) {
-                swap(*__i, *__j);
+                _Ops::iter_swap(__i, __j);
                 ++__n_swaps;
                 ++__i;
                 break;
@@ -432,7 +520,7 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
               ;
             if (__i >= __j)
               break;
-            swap(*__i, *__j);
+            _Ops::iter_swap(__i, __j);
             ++__n_swaps;
             ++__i;
           }
@@ -443,7 +531,7 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
           goto __restart;
         }
         if (__comp(*__j, *__m)) {
-          swap(*__i, *__j);
+          _Ops::iter_swap(__i, __j);
           ++__n_swaps;
           break; // found guard for downward moving __j, now use unguarded partition
         }
@@ -465,7 +553,7 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
           ;
         if (__i > __j)
           break;
-        swap(*__i, *__j);
+        _Ops::iter_swap(__i, __j);
         ++__n_swaps;
         // It is known that __m != __j
         // If __m just moved, follow it
@@ -476,14 +564,16 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
     }
     // [__first, __i) < *__m and *__m <= [__i, __last)
     if (__i != __m && __comp(*__m, *__i)) {
-      swap(*__i, *__m);
+      _Ops::iter_swap(__i, __m);
       ++__n_swaps;
     }
     // [__first, __i) < *__i and *__i <= [__i+1, __last)
     // If we were given a perfect partition, see if insertion sort is quick...
     if (__n_swaps == 0) {
-      bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
-      if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + difference_type(1), __last, __comp)) {
+      using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Compare>::type;
+      _WrappedComp __wrapped_comp(__comp);
+      bool __fs = std::__insertion_sort_incomplete<_WrappedComp>(__first, __i, __wrapped_comp);
+      if (std::__insertion_sort_incomplete<_WrappedComp>(__i + difference_type(1), __last, __wrapped_comp)) {
         if (__fs)
           return;
         __last = __i;
@@ -497,10 +587,10 @@ void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
     }
     // sort smaller range with recursive call and larger with tail recursion elimination
     if (__i - __first < __last - __i) {
-      _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
+      std::__introsort<_AlgPolicy, _Compare>(__first, __i, __comp, __depth);
       __first = ++__i;
     } else {
-      _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth);
+      std::__introsort<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp, __depth);
       __last = __i;
     }
   }
@@ -525,17 +615,22 @@ inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
   return __log2;
 }
 
-template <class _Compare, class _RandomAccessIterator>
-void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+template <class _WrappedComp, class _RandomAccessIterator>
+void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   difference_type __depth_limit = 2 * __log2i(__last - __first);
-  _VSTD::__introsort<_Compare>(__first, __last, __comp, __depth_limit);
+
+  using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>;
+  using _AlgPolicy = typename _Unwrap::_AlgPolicy;
+  using _Compare = typename _Unwrap::_Comp;
+  _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
+  std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit);
 }
 
 template <class _Compare, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) {
   __less<uintptr_t> __comp;
-  _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
+  std::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
 }
 
 extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
@@ -576,22 +671,27 @@ extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long do
 
 extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&);
 
-template <class _RandomAccessIterator, class _Comp>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
-  std::__debug_randomize_range(__first, __last);
+  std::__debug_randomize_range<_AlgPolicy>(__first, __last);
+
   using _Comp_ref = typename __comp_ref_type<_Comp>::type;
   if (__libcpp_is_constant_evaluated()) {
-    std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+    std::__partial_sort<_AlgPolicy>(__first, __last, __last, __comp);
+
   } else {
-    std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp));
+    using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Comp_ref>::type;
+    _Comp_ref __comp_ref(__comp);
+    _WrappedComp __wrapped_comp(__comp_ref);
+    std::__sort<_WrappedComp>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp);
   }
 }
 
 template <class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
-  std::__sort_impl(std::move(__first), std::move(__last), __comp);
+  std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h
index 261adedd0eaf..b9f0b2c9690d 100644
--- a/libcxx/include/__algorithm/sort_heap.h
+++ b/libcxx/include/__algorithm/sort_heap.h
@@ -11,11 +11,12 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/pop_heap.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
-#include <type_traits> // swap
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -23,7 +24,7 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
@@ -31,13 +32,16 @@ void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _C
 
   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
   for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
-    std::__pop_heap<_CompRef>(__first, __last, __comp_ref, __n);
+    std::__pop_heap<_AlgPolicy, _CompRef>(__first, __last, __comp_ref, __n);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__sort_heap(std::move(__first), std::move(__last), __comp);
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
+  std::__sort_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/stable_partition.h b/libcxx/include/__algorithm/stable_partition.h
index 969ac7a6173e..e5ad48b2ed51 100644
--- a/libcxx/include/__algorithm/stable_partition.h
+++ b/libcxx/include/__algorithm/stable_partition.h
@@ -9,13 +9,14 @@
 #ifndef _LIBCPP___ALGORITHM_STABLE_PARTITION_H
 #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H
 
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/rotate.h>
 #include <__config>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
 #include <memory>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -23,11 +24,13 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
+template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _Distance, class _Pair>
 _ForwardIterator
-__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
+__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
                    _Distance __len, _Pair __p, forward_iterator_tag __fit)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     // *__first is known to be false
     // __len >= 1
     if (__len == 1)
@@ -37,7 +40,7 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate
         _ForwardIterator __m = __first;
         if (__pred(*++__m))
         {
-            swap(*__first, *__m);
+            _Ops::iter_swap(__first, __m);
             return __m;
         }
         return __first;
@@ -50,7 +53,7 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate
         // Move the falses into the temporary buffer, and the trues to the front of the line
         // Update __first to always point to the end of the trues
         value_type* __t = __p.first;
-        ::new ((void*)__t) value_type(_VSTD::move(*__first));
+        ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
         __d.template __incr<value_type>();
         ++__t;
         _ForwardIterator __i = __first;
@@ -58,12 +61,12 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate
         {
             if (__pred(*__i))
             {
-                *__first = _VSTD::move(*__i);
+                *__first = _Ops::__iter_move(__i);
                 ++__first;
             }
             else
             {
-                ::new ((void*)__t) value_type(_VSTD::move(*__i));
+                ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
                 __d.template __incr<value_type>();
                 ++__t;
             }
@@ -72,7 +75,7 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate
         // Move falses back into range, but don't mess up __first which points to first false
         __i = __first;
         for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
-            *__i = _VSTD::move(*__t2);
+            *__i = _Ops::__iter_move(__t2);
         // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
         return __first;
     }
@@ -80,11 +83,12 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate
     // __len >= 3
     _ForwardIterator __m = __first;
     _Distance __len2 = __len / 2;  // __len2 >= 2
-    _VSTD::advance(__m, __len2);
+    _Ops::advance(__m, __len2);
     // recurse on [__first, __m), *__first know to be false
     // F?????????????????
     // f       m         l
-    _ForwardIterator __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m, __pred, __len2, __p, __fit);
+    _ForwardIterator __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+        __first, __m, __pred, __len2, __p, __fit);
     // TTTFFFFF??????????
     // f  ff   m         l
     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
@@ -99,18 +103,19 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate
     }
     // TTTFFFFFTTTF??????
     // f  ff   m  m1     l
-    __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
+    __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+        __m1, __last, __pred, __len_half, __p, __fit);
 __second_half_done:
     // TTTFFFFFTTTTTFFFFF
     // f  ff   m    sf   l
-    return _VSTD::rotate(__first_false, __m, __second_false);
+    return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false, __fit);
     // TTTTTTTTFFFFFFFFFF
     //         |
 }
 
-template <class _Predicate, class _ForwardIterator>
+template <class _AlgPolicy, class _Predicate, class _ForwardIterator>
 _ForwardIterator
-__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
+__stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
                    forward_iterator_tag)
 {
     const unsigned __alloc_limit = 3;  // might want to make this a function of trivial assignment
@@ -127,7 +132,7 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate
     // *__first is known to be false
     typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
     typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
-    difference_type __len = _VSTD::distance(__first, __last);
+    difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last);
     pair<value_type*, ptrdiff_t> __p(0, 0);
     unique_ptr<value_type, __return_temporary_buffer> __h;
     if (__len >= __alloc_limit)
@@ -138,20 +143,23 @@ _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 _LIBCPP_SUPPRESS_DEPRECATED_POP
         __h.reset(__p.first);
     }
-    return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, forward_iterator_tag());
+    return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+        std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag());
 }
 
-template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
+template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
 _BidirectionalIterator
-__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
+__stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
                    _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     // *__first is known to be false
     // *__last is known to be true
     // __len >= 2
     if (__len == 2)
     {
-        swap(*__first, *__last);
+        _Ops::iter_swap(__first, __last);
         return __last;
     }
     if (__len == 3)
@@ -159,12 +167,12 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last
         _BidirectionalIterator __m = __first;
         if (__pred(*++__m))
         {
-            swap(*__first, *__m);
-            swap(*__m, *__last);
+            _Ops::iter_swap(__first, __m);
+            _Ops::iter_swap(__m, __last);
             return __last;
         }
-        swap(*__m, *__last);
-        swap(*__first, *__m);
+        _Ops::iter_swap(__m, __last);
+        _Ops::iter_swap(__first, __m);
         return __m;
     }
     if (__len <= __p.second)
@@ -175,7 +183,7 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last
         // Move the falses into the temporary buffer, and the trues to the front of the line
         // Update __first to always point to the end of the trues
         value_type* __t = __p.first;
-        ::new ((void*)__t) value_type(_VSTD::move(*__first));
+        ::new ((void*)__t) value_type(_Ops::__iter_move(__first));
         __d.template __incr<value_type>();
         ++__t;
         _BidirectionalIterator __i = __first;
@@ -183,23 +191,23 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last
         {
             if (__pred(*__i))
             {
-                *__first = _VSTD::move(*__i);
+                *__first = _Ops::__iter_move(__i);
                 ++__first;
             }
             else
             {
-                ::new ((void*)__t) value_type(_VSTD::move(*__i));
+                ::new ((void*)__t) value_type(_Ops::__iter_move(__i));
                 __d.template __incr<value_type>();
                 ++__t;
             }
         }
         // move *__last, known to be true
-        *__first = _VSTD::move(*__i);
+        *__first = _Ops::__iter_move(__i);
         __i = ++__first;
         // All trues now at start of range, all falses in buffer
         // Move falses back into range, but don't mess up __first which points to first false
         for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, (void) ++__i)
-            *__i = _VSTD::move(*__t2);
+            *__i = _Ops::__iter_move(__t2);
         // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer
         return __first;
     }
@@ -207,7 +215,7 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last
     // __len >= 4
     _BidirectionalIterator __m = __first;
     _Distance __len2 = __len / 2;  // __len2 >= 2
-    _VSTD::advance(__m, __len2);
+    _Ops::advance(__m, __len2);
     // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false
     // F????????????????T
     // f       m        l
@@ -222,7 +230,8 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last
     }
     // F???TFFF?????????T
     // f   m1  m        l
-    __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);
+    __first_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+        __first, __m1, __pred, __len_half, __p, __bit);
 __first_half_done:
     // TTTFFFFF?????????T
     // f  ff   m        l
@@ -239,18 +248,19 @@ __first_half_done:
     }
     // TTTFFFFFTTTF?????T
     // f  ff   m  m1    l
-    __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);
+    __second_false = std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+        __m1, __last, __pred, __len_half, __p, __bit);
 __second_half_done:
     // TTTFFFFFTTTTTFFFFF
     // f  ff   m    sf  l
-    return _VSTD::rotate(__first_false, __m, __second_false);
+    return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false, __bit);
     // TTTTTTTTFFFFFFFFFF
     //         |
 }
 
-template <class _Predicate, class _BidirectionalIterator>
+template <class _AlgPolicy, class _Predicate, class _BidirectionalIterator>
 _BidirectionalIterator
-__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
+__stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
                    bidirectional_iterator_tag)
 {
     typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
@@ -276,7 +286,7 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last
     // *__first is known to be false
     // *__last is known to be true
     // __len >= 2
-    difference_type __len = _VSTD::distance(__first, __last) + 1;
+    difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1;
     pair<value_type*, ptrdiff_t> __p(0, 0);
     unique_ptr<value_type, __return_temporary_buffer> __h;
     if (__len >= __alloc_limit)
@@ -287,7 +297,16 @@ _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 _LIBCPP_SUPPRESS_DEPRECATED_POP
         __h.reset(__p.first);
     }
-    return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
+    return std::__stable_partition_impl<_AlgPolicy, _Predicate&>(
+        std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag());
+}
+
+template <class _AlgPolicy, class _Predicate, class _ForwardIterator, class _IterCategory>
+_LIBCPP_HIDE_FROM_ABI
+_ForwardIterator __stable_partition(
+    _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred, _IterCategory __iter_category) {
+  return std::__stable_partition_impl<_AlgPolicy, __uncvref_t<_Predicate>&>(
+      std::move(__first), std::move(__last), __pred, __iter_category);
 }
 
 template <class _ForwardIterator, class _Predicate>
@@ -295,7 +314,9 @@ inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator
 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
 {
-    return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
+  using _IterCategory = typename iterator_traits<_ForwardIterator>::iterator_category;
+  return std::__stable_partition<_ClassicAlgPolicy, _Predicate&>(
+      std::move(__first), std::move(__last), __pred, _IterCategory());
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h
index e3479aad62e6..6122758bdefe 100644
--- a/libcxx/include/__algorithm/stable_sort.h
+++ b/libcxx/include/__algorithm/stable_sort.h
@@ -12,11 +12,11 @@
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/inplace_merge.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
-#include <__utility/swap.h>
 #include <memory>
 #include <type_traits>
 
@@ -26,12 +26,14 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator1, class _InputIterator2>
+template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2>
 void
 __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
         _InputIterator2 __first2, _InputIterator2 __last2,
         typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_InputIterator1>::value_type value_type;
     __destruct_n __d(0);
     unique_ptr<value_type, __destruct_n&> __h(__result, __d);
@@ -40,111 +42,115 @@ __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1,
         if (__first1 == __last1)
         {
             for (; __first2 != __last2; ++__first2, (void) ++__result, __d.template __incr<value_type>())
-                ::new ((void*)__result) value_type(_VSTD::move(*__first2));
+                ::new ((void*)__result) value_type(_Ops::__iter_move(__first2));
             __h.release();
             return;
         }
         if (__first2 == __last2)
         {
             for (; __first1 != __last1; ++__first1, (void) ++__result, __d.template __incr<value_type>())
-                ::new ((void*)__result) value_type(_VSTD::move(*__first1));
+                ::new ((void*)__result) value_type(_Ops::__iter_move(__first1));
             __h.release();
             return;
         }
         if (__comp(*__first2, *__first1))
         {
-            ::new ((void*)__result) value_type(_VSTD::move(*__first2));
+            ::new ((void*)__result) value_type(_Ops::__iter_move(__first2));
             __d.template __incr<value_type>();
             ++__first2;
         }
         else
         {
-            ::new ((void*)__result) value_type(_VSTD::move(*__first1));
+            ::new ((void*)__result) value_type(_Ops::__iter_move(__first1));
             __d.template __incr<value_type>();
             ++__first1;
         }
     }
 }
 
-template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
+template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
 void
 __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1,
         _InputIterator2 __first2, _InputIterator2 __last2,
         _OutputIterator __result, _Compare __comp)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     for (; __first1 != __last1; ++__result)
     {
         if (__first2 == __last2)
         {
             for (; __first1 != __last1; ++__first1, (void) ++__result)
-                *__result = _VSTD::move(*__first1);
+                *__result = _Ops::__iter_move(__first1);
             return;
         }
         if (__comp(*__first2, *__first1))
         {
-            *__result = _VSTD::move(*__first2);
+            *__result = _Ops::__iter_move(__first2);
             ++__first2;
         }
         else
         {
-            *__result = _VSTD::move(*__first1);
+            *__result = _Ops::__iter_move(__first1);
             ++__first1;
         }
     }
     for (; __first2 != __last2; ++__first2, (void) ++__result)
-        *__result = _VSTD::move(*__first2);
+        *__result = _Ops::__iter_move(__first2);
 }
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void
 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
               typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void
 __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
                    typename iterator_traits<_RandomAccessIterator>::difference_type __len,
                    typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
 {
+    using _Ops = _IterOps<_AlgPolicy>;
+
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     switch (__len)
     {
     case 0:
         return;
     case 1:
-        ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
+        ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
         return;
     case 2:
         __destruct_n __d(0);
         unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
         if (__comp(*--__last1, *__first1))
         {
-            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1));
             __d.template __incr<value_type>();
             ++__first2;
-            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
         }
         else
         {
-            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1));
             __d.template __incr<value_type>();
             ++__first2;
-            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
+            ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1));
         }
         __h2.release();
         return;
     }
     if (__len <= 8)
     {
-        _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
+        std::__insertion_sort_move<_AlgPolicy, _Compare>(__first1, __last1, __first2, __comp);
         return;
     }
     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
     _RandomAccessIterator __m = __first1 + __l2;
-    _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
-    _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
-    _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
+    std::__stable_sort<_AlgPolicy, _Compare>(__first1, __m, __comp, __l2, __first2, __l2);
+    std::__stable_sort<_AlgPolicy, _Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
+    std::__merge_move_construct<_AlgPolicy, _Compare>(__first1, __m, __m, __last1, __first2, __comp);
 }
 
 template <class _Tp>
@@ -153,7 +159,7 @@ struct __stable_sort_switch
     static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
 };
 
-template <class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 void
 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
               typename iterator_traits<_RandomAccessIterator>::difference_type __len,
@@ -168,12 +174,12 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp
         return;
     case 2:
         if (__comp(*--__last, *__first))
-            swap(*__first, *__last);
+            _IterOps<_AlgPolicy>::iter_swap(__first, __last);
         return;
     }
     if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
     {
-        _VSTD::__insertion_sort<_Compare>(__first, __last, __comp);
+        std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
         return;
     }
     typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
@@ -182,11 +188,12 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp
     {
         __destruct_n __d(0);
         unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
-        _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
+        std::__stable_sort_move<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff);
         __d.__set(__l2, (value_type*)nullptr);
-        _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
+        std::__stable_sort_move<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
         __d.__set(__len, (value_type*)nullptr);
-        _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
+        std::__merge_move_assign<_AlgPolicy, _Compare>(
+            __buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
 //         _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff),
 //                                  move_iterator<value_type*>(__buff + __l2),
 //                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
@@ -194,12 +201,12 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp
 //                                  __first, __comp);
         return;
     }
-    _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
-    _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
-    _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
+    std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
+    std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
+    std::__inplace_merge<_AlgPolicy, _Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
 }
 
-template <class _RandomAccessIterator, class _Compare>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI
 void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
@@ -217,13 +224,13 @@ _LIBCPP_SUPPRESS_DEPRECATED_POP
   }
 
   using _Comp_ref = typename __comp_ref_type<_Compare>::type;
-  std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
+  std::__stable_sort<_AlgPolicy, _Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI
 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
-  std::__stable_sort_impl(std::move(__first), std::move(__last), __comp);
+  std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/unwrap_iter.h b/libcxx/include/__algorithm/unwrap_iter.h
index 7d1807b7bbf9..fa9a8fbf2dde 100644
--- a/libcxx/include/__algorithm/unwrap_iter.h
+++ b/libcxx/include/__algorithm/unwrap_iter.h
@@ -12,6 +12,7 @@
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__memory/pointer_traits.h>
+#include <__utility/move.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -20,77 +21,50 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-// The job of __unwrap_iter is to lower contiguous iterators (such as
-// vector<T>::iterator) into pointers, to reduce the number of template
-// instantiations and to enable pointer-based optimizations e.g. in std::copy.
-// For iterators that are not contiguous, it must be a no-op.
+// TODO: Change the name of __unwrap_iter_impl to something more appropriate
+// The job of __unwrap_iter is to remove iterator wrappers (like reverse_iterator or __wrap_iter),
+// to reduce the number of template instantiations and to enable pointer-based optimizations e.g. in std::copy.
 // In debug mode, we don't do this.
 //
-// __unwrap_iter is non-constexpr for user-defined iterators whose
-// `to_address` and/or `operator->` is non-constexpr. This is okay; but we
-// try to avoid doing __unwrap_iter in constant-evaluated contexts anyway.
-//
 // Some algorithms (e.g. std::copy, but not std::sort) need to convert an
-// "unwrapped" result back into a contiguous iterator. Since contiguous iterators
-// are random-access, we can do this portably using iterator arithmetic; this
-// is the job of __rewrap_iter.
+// "unwrapped" result back into the original iterator type. Doing that is the job of __rewrap_iter.
 
+// Default case - we can't unwrap anything
 template <class _Iter, bool = __is_cpp17_contiguous_iterator<_Iter>::value>
 struct __unwrap_iter_impl {
-    static _LIBCPP_CONSTEXPR _Iter
-    __apply(_Iter __i) _NOEXCEPT {
-        return __i;
-    }
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __rewrap(_Iter, _Iter __iter) { return __iter; }
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __unwrap(_Iter __i) _NOEXCEPT { return __i; }
 };
 
 #ifndef _LIBCPP_ENABLE_DEBUG_MODE
 
+// It's a contiguous iterator, so we can use a raw pointer instead
 template <class _Iter>
 struct __unwrap_iter_impl<_Iter, true> {
-    static _LIBCPP_CONSTEXPR decltype(_VSTD::__to_address(declval<_Iter>()))
-    __apply(_Iter __i) _NOEXCEPT {
-        return _VSTD::__to_address(__i);
-    }
-};
+  using _ToAddressT = decltype(std::__to_address(std::declval<_Iter>()));
 
-#endif // !_LIBCPP_ENABLE_DEBUG_MODE
-
-template<class _Iter, class _Impl = __unwrap_iter_impl<_Iter> >
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-decltype(_Impl::__apply(declval<_Iter>()))
-__unwrap_iter(_Iter __i) _NOEXCEPT
-{
-    return _Impl::__apply(__i);
-}
-
-template <class _OrigIter, class _UnwrappedIter>
-struct __rewrap_iter_impl {
-  static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter __first, _UnwrappedIter __result) {
-    // Precondition: __result is reachable from __first
-    // Precondition: _OrigIter is a contiguous iterator
-    return __first + (__result - std::__unwrap_iter(__first));
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Iter __rewrap(_Iter __orig_iter, _ToAddressT __unwrapped_iter) {
+    return __orig_iter + (__unwrapped_iter - std::__to_address(__orig_iter));
   }
-};
 
-template <class _OrigIter>
-struct __rewrap_iter_impl<_OrigIter, _OrigIter> {
-  static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) {
-    return __result;
+  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _ToAddressT __unwrap(_Iter __i) _NOEXCEPT {
+    return std::__to_address(__i);
   }
 };
 
-template<class _OrigIter>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
-_OrigIter __rewrap_iter(_OrigIter, _OrigIter __result)
-{
-    return __result;
+#endif // !_LIBCPP_ENABLE_DEBUG_MODE
+
+template<class _Iter,
+         class _Impl = __unwrap_iter_impl<_Iter>,
+         __enable_if_t<is_copy_constructible<_Iter>::value, int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+decltype(_Impl::__unwrap(std::declval<_Iter>())) __unwrap_iter(_Iter __i) _NOEXCEPT {
+  return _Impl::__unwrap(__i);
 }
 
-template<class _OrigIter, class _UnwrappedIter, class _Impl = __rewrap_iter_impl<_OrigIter, _UnwrappedIter> >
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR
-_OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result)
-{
-  return _Impl::__apply(__first, __result);
+template <class _OrigIter, class _Iter, class _Impl = __unwrap_iter_impl<_OrigIter> >
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter __orig_iter, _Iter __iter) _NOEXCEPT {
+  return _Impl::__rewrap(std::move(__orig_iter), std::move(__iter));
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/upper_bound.h b/libcxx/include/__algorithm/upper_bound.h
index 3fc254873532..1045380bc84e 100644
--- a/libcxx/include/__algorithm/upper_bound.h
+++ b/libcxx/include/__algorithm/upper_bound.h
@@ -11,10 +11,15 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_copy_constructible.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -22,45 +27,40 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _ForwardIterator, class _Tp>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
-__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
-{
-    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
-    while (__len != 0)
-    {
-        difference_type __l2 = _VSTD::__half_positive(__len);
-        _ForwardIterator __m = __first;
-        _VSTD::advance(__m, __l2);
-        if (__comp(__value, *__m))
-            __len = __l2;
-        else
-        {
-            __first = ++__m;
-            __len -= __l2 + 1;
-        }
+template <class _AlgPolicy, class _Compare, class _Iter, class _Sent, class _Tp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter
+__upper_bound(_Iter __first, _Sent __last, const _Tp& __value, _Compare&& __comp, _Proj&& __proj) {
+  auto __len = _IterOps<_AlgPolicy>::distance(__first, __last);
+  while (__len != 0) {
+    auto __half_len = std::__half_positive(__len);
+    auto __mid      = _IterOps<_AlgPolicy>::next(__first, __half_len);
+    if (std::__invoke(__comp, __value, std::__invoke(__proj, *__mid)))
+      __len = __half_len;
+    else {
+      __first = ++__mid;
+      __len -= __half_len + 1;
     }
-    return __first;
+  }
+  return __first;
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_ForwardIterator
-upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
-{
-    return _VSTD::__upper_bound<_Compare&>(__first, __last, __value, __comp);
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) {
+  static_assert(is_copy_constructible<_ForwardIterator>::value,
+                "Iterator has to be copy constructible");
+  return std::__upper_bound<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), __value, std::move(__comp), std::__identity());
 }
 
 template <class _ForwardIterator, class _Tp>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_ForwardIterator
-upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
-{
-    return _VSTD::upper_bound(__first, __last, __value,
-                             __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  return std::upper_bound(
+      std::move(__first),
+      std::move(__last),
+      __value,
+      __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD