[libc++][ranges] Implement `ranges::{,stable_}partition`.

[var-const]

Forgotten file

[var-const]

Patch link.

[var-const]

Uncomment omitted test.

[var-const]

Fix the CI.

[var-const]

Rebase and fix the CI.

[var-const]

Rebase on main and make the new algorithms support proxy iterators.

[var-const]

Version forgotten file.

[var-const]

Fix the CI.

[huixie90]

The algorithm LGTM. Regarding testing, I still prefer to have extra tests to verify iter_move and/or iter_swap is correctly used

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp

236

as these algorithms involves iter_move, I suggests to add tests to verify the outputs before we can figure out an automated way to catch in via a compile-time tests. so here , we could have

std::array<MoveOnly, N> a{...];
ProxyRange r{a};
std::ranges::partition(r);
// verify that the original `a` is partitioned as the expected result

(actually even without verifying the result, the compiler would catch std::move(*it) because std::move(*it) would copy the MoveOnly for Proxy<MoveOnly&>&& and MoveOnly is not copyable

[var-const]

libcxx/include/__algorithm/iterator_operations.h

92

This is copied from https://reviews.llvm.org/D129796.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp

236

I'd prefer to do these checks en masse: https://reviews.llvm.org/D130057

[var-const]

@philnik I'm going to merge this, but happy to address any comments you might have in a follow-up.

libcxx/docs/Status/RangesAlgorithms.csv

 Category,Algorithm,Assignee,CL,Complete
 Search,any_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,all_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,none_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,find,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_if,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_if_not,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_first_of,Nikolas Klauser,`D126529 <https://llvm.org/D126529>`_,✅
 Search,adjacent_find,Nikolas Klauser,`D126610 <https://llvm.org/D126610>`_,✅
 Search,mismatch,Nikolas Klauser,`D117817 <https://llvm.org/D117817>`_,✅
 Search,equal,Nikolas Klauser,`D123681 <https://llvm.org/D123681>`_,✅
 Search,lexicographical_compare,Nikolas Klauser,`D127130 <https://llvm.org/D127130>`_,✅
-Search,partition_point,Christopher Di Bella,`D105794 <https://llvm.org/D105794>`_,Under review
+Search,partition_point,Konstantin Varlamov,n/a,In progress
 Search,lower_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,upper_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,equal_range,Christopher Di Bella,n/a,Not started
 Search,binary_search,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,min,Nikolas Klauser,`D119589 <https://llvm.org/D119589>`_,✅
 Search,max,Nikolas Klauser,`D122002 <https://llvm.org/D122002>`_,✅
 Search,minmax,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,min_element,Nikolas Klauser,`D117025 <https://llvm.org/D117025>`_,✅

 Write,replace_if,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
 Write,replace_copy,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review
 Write,replace_copy_if,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,sample,Not assigned,n/a,Not started
 Write,unique_copy,Not assigned,n/a,Not started
-Write,partition_copy,Not assigned,n/a,Not started
+Write,partition_copy,Konstantin Varlamov,n/a,In progress
 Write,partial_sort_copy,Not assigned,n/a,Not started
 Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅
 Merge,set_difference,Hui Xie,`D128983 <https://llvm.org/D128983>`_,✅
 Merge,set_intersection,Hui Xie,`D129233 <https://llvm.org/D129233>`_,✅
 Merge,set_symmetric_difference,Hui Xie,`D129520 <https://llvm.org/D129520>`_,✅
 Merge,set_union,Hui Xie,`D129657 <https://llvm.org/D129657>`_,✅
 Permutation,remove,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
 Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review
 Permutation,shuffle,Not assigned,n/a,Not started
 Permutation,unique,Not assigned,n/a,Not started
-Permutation,partition,Not assigned,n/a,Not started
-Permutation,stable_partition,Not assigned,n/a,Not started
+Permutation,partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
+Permutation,stable_partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
 Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅
 Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅
 Permutation,partial_sort,Konstantin Varlamov,n/a,In progress
 Permutation,nth_element,Konstantin Varlamov,`D128149 <https://llvm.org/D128149>`_,✅
 Permutation,inplace_merge,Not assigned,n/a,Not started
 Permutation,make_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,push_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,pop_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_generate_n.h
   __algorithm/ranges_includes.h
   __algorithm/ranges_inplace_merge.h
   __algorithm/ranges_is_heap.h
   __algorithm/ranges_is_heap_until.h
   __algorithm/ranges_is_partitioned.h
   __algorithm/ranges_is_sorted.h
   __algorithm/ranges_is_sorted_until.h
+  __algorithm/ranges_iterator_concept.h
   __algorithm/ranges_lexicographical_compare.h
   __algorithm/ranges_lower_bound.h
   __algorithm/ranges_make_heap.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_merge.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h

libcxx/include/__algorithm/iterator_operations.h

struct _IterOps<_ClassicAlgPolicy> {
   template <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   _Iterator next(_Iterator, _Iterator __last) {
     return __last;
   }
 
   template <class _Iter>
   _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;
   }
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H

libcxx/include/__algorithm/make_projected.h

 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _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) {
   if constexpr (same_as<decay_t<_Proj>, identity> && !is_member_pointer_v<decay_t<_Comp>>) {
     // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable
     // optimizations that rely on the type of the comparator.
     return __comp;
 

libcxx/include/__algorithm/partition.h

 //===----------------------------------------------------------------------===//
 //
 // 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_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
 #endif
 
 _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;
         }
         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
 
 #endif // _LIBCPP___ALGORITHM_PARTITION_H

libcxx/include/__algorithm/ranges_find_end.h

 //===----------------------------------------------------------------------===//
 //
 // 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_FIND_END_H
 #define _LIBCPP___ALGORITHM_RANGES_FIND_END_H
 
 #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>
 #include <__iterator/concepts.h>
 #include <__iterator/indirectly_comparable.h>
 #include <__iterator/iterator_traits.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/subrange.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
 
-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 {
   template <forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
             forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
             class _Pred = ranges::equal_to,
             class _Proj1 = identity,
             class _Proj2 = identity>

libcxx/include/__algorithm/ranges_partition.h

 //===----------------------------------------------------------------------===//
 //
 // 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_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>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/permutable.h>
 #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
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 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,
             indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
   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);
   }
 
 };
 
 } // namespace __partition
 
 inline namespace __cpo {
   inline constexpr auto partition = __partition::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_PARTITION_H

libcxx/include/__algorithm/ranges_stable_partition.h

 //===----------------------------------------------------------------------===//
 //
 // 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_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>
 #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 <__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
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 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,
             indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
   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);
   }
 
 };
 
 } // namespace __stable_partition
 
 inline namespace __cpo {
   inline constexpr auto stable_partition = __stable_partition::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_STABLE_PARTITION_H

libcxx/include/__algorithm/rotate.h

 //===----------------------------------------------------------------------===//
 //
 // 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_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>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__utility/move.h>
 #include <__utility/swap.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _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;
         if (__first == __middle)
             __middle = __i;
     }
     _ForwardIterator __r = __first;
     if (__first != __middle)
     {
         __i = __middle;
         while (true)
         {
-            swap(*__first, *__i);
+            _IterOps<_AlgPolicy>::iter_swap(__first, __i);
             ++__first;
             if (++__i == __last)
             {
                 if (__first == __middle)
                     break;
                 __i = __middle;
             }
             else if (__first == __middle)
__algo_gcd(_Integral __x, _Integral __y)
     {
         _Integral __t = __x % __y;
         __x = __y;
         __y = __t;
     } while (__y);
     return __x;
 }
 
-template<typename _RandomAccessIterator>
+template <class _AlgPolicy, typename _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX14 _RandomAccessIterator
 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
 
     const difference_type __m1 = __middle - __first;
     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)
                 __p2 += __m1;
             else
                 __p2 = __first + (__m1 - __d);
         } while (__p2 != __p);
         *__p1 = _VSTD::move(__t);
     }
     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);
-    }
-    return _VSTD::__rotate_forward(__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 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>
 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,
+  return std::__rotate<_ClassicAlgPolicy>(__first, __middle, __last,
                                           typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_ROTATE_H

libcxx/include/__algorithm/stable_partition.h

 //===----------------------------------------------------------------------===//
 //
 // 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_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
 #endif
 
 _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)
         return __first;
     if (__len == 2)
     {
         _ForwardIterator __m = __first;
         if (__pred(*++__m))
         {
-            swap(*__first, *__m);
+            _Ops::iter_swap(__first, __m);
             return __m;
         }
         return __first;
     }
     if (__len <= __p.second)
     {   // The buffer is big enough to use
         typedef typename iterator_traits<_ForwardIterator>::value_type value_type;
         __destruct_n __d(0);
         unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
         // 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;
         while (++__i != __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;
             }
         }
         // 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
         __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;
     }
     // Else not enough buffer, do in place
     // __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
     _ForwardIterator __m1 = __m;
     _ForwardIterator __second_false = __last;
     _Distance __len_half = __len - __len2;
     while (__pred(*__m1))
     {
         if (++__m1 == __last)
             goto __second_half_done;
         --__len_half;
     }
     // 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
     // Either prove all true and return __first or point to first false
     while (true)
     {
         if (__first == __last)
             return __first;
         if (!__pred(*__first))
             break;
         ++__first;
     }
     // We now have a reduced range [__first, __last)
     // *__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)
     {
 // TODO: Remove the use of std::get_temporary_buffer
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
         __p = _VSTD::get_temporary_buffer<value_type>(__len);
 _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)
     {
         _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)
     {   // The buffer is big enough to use
         typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
         __destruct_n __d(0);
         unique_ptr<value_type, __destruct_n&> __h(__p.first, __d);
         // 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;
         while (++__i != __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;
     }
     // Else not enough buffer, do in place
     // __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
     _BidirectionalIterator __m1 = __m;
     _BidirectionalIterator __first_false = __first;
     _Distance __len_half = __len2;
     while (!__pred(*--__m1))
     {
         if (__m1 == __first)
             goto __first_half_done;
         --__len_half;
     }
     // 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
     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
     __m1 = __m;
     _BidirectionalIterator __second_false = __last;
     ++__second_false;
     __len_half = __len - __len2;
     while (__pred(*__m1))
     {
         if (++__m1 == __last)
             goto __second_half_done;
         --__len_half;
     }
     // 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;
     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
     const difference_type __alloc_limit = 4;  // might want to make this a function of trivial assignment
     // Either prove all true and return __first or point to first false
     while (true)
     {
__stable_partition_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
     {
         if (__first == --__last)
             return __first;
     } while (!__pred(*__last));
     // We now have a reduced range [__first, __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)
     {
 // TODO: Remove the use of std::get_temporary_buffer
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
         __p = _VSTD::get_temporary_buffer<value_type>(__len);
 _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>
 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
 
 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H

libcxx/include/algorithm

template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
     constexpr bool binary_search(I first, S last, const T& value, Comp comp = {},
                                          Proj proj = {});                                     // since C++20
 
   template<forward_range R, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
              ranges::less>
     constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
                                          Proj proj = {});                                     // since C++20
+
+  template<permutable I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    constexpr subrange<I>
+      partition(I first, S last, Pred pred, Proj proj = {});                                  // Since C++20
+
+  template<forward_range R, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires permutable<iterator_t<R>>
+    constexpr borrowed_subrange_t<R>
+      partition(R&& r, Pred pred, Proj proj = {});                                            // Since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    requires permutable<I>
+    subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {});                 // Since C++20
+
+  template<bidirectional_range R, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires permutable<iterator_t<R>>
+    borrowed_subrange_t<R> stable_partition(R&& r, Pred pred, Proj proj = {});                // Since C++20
+
   template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
            class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
     requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
     constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
                                        Pred pred = {},
                                        Proj1 proj1 = {}, Proj2 proj2 = {});                 // since C++20
 
   template<input_range R1, forward_range R2,

 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_nth_element.h>
+#include <__algorithm/ranges_partition.h>
 #include <__algorithm/ranges_pop_heap.h>
 #include <__algorithm/ranges_push_heap.h>
 #include <__algorithm/ranges_remove.h>
 #include <__algorithm/ranges_remove_if.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_reverse_copy.h>
 #include <__algorithm/ranges_rotate_copy.h>
 #include <__algorithm/ranges_search.h>
 #include <__algorithm/ranges_search_n.h>
 #include <__algorithm/ranges_set_difference.h>
 #include <__algorithm/ranges_set_intersection.h>
 #include <__algorithm/ranges_set_symmetric_difference.h>
 #include <__algorithm/ranges_set_union.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_sort_heap.h>
+#include <__algorithm/ranges_stable_partition.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_generate_n               { private header "__algorithm/ranges_generate_n.h" }
       module ranges_includes                 { private header "__algorithm/ranges_includes.h" }
       module ranges_inplace_merge            { private header "__algorithm/ranges_inplace_merge.h" }
       module ranges_is_heap                  { private header "__algorithm/ranges_is_heap.h" }
       module ranges_is_heap_until            { private header "__algorithm/ranges_is_heap_until.h" }
       module ranges_is_partitioned           { private header "__algorithm/ranges_is_partitioned.h" }
       module ranges_is_sorted                { private header "__algorithm/ranges_is_sorted.h" }
       module ranges_is_sorted_until          { private header "__algorithm/ranges_is_sorted_until.h" }
+      module ranges_iterator_concept         { private header "__algorithm/ranges_iterator_concept.h" }
       module ranges_lexicographical_compare  { private header "__algorithm/ranges_lexicographical_compare.h" }
       module ranges_lower_bound              { private header "__algorithm/ranges_lower_bound.h" }
       module ranges_make_heap                { private header "__algorithm/ranges_make_heap.h" }
       module ranges_max                      { private header "__algorithm/ranges_max.h" }
       module ranges_max_element              { private header "__algorithm/ranges_max_element.h" }
       module ranges_merge                    { private header "__algorithm/ranges_merge.h" }
       module ranges_min                      { private header "__algorithm/ranges_min.h" }
       module ranges_min_element              { private header "__algorithm/ranges_min_element.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     (void)std::ranges::none_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition(first, last, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition(a, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::partition(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::partition(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
#endif
     (void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::set_symmetric_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0);
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); }
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); }
     if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); }
     if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); }
 #if TEST_STD_VER > 20
     //(void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::transform(first, last, first2, UnaryTransform(&copies)); assert(copies == 0);
     (void)std::ranges::transform(a, first2, UnaryTransform(&copies)); assert(copies == 0);
     (void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     (void)std::ranges::none_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
#endif
     (void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::set_symmetric_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0);
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
-    //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
+    if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
     if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); }
     if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); }
 #if TEST_STD_VER > 20
     //(void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::transform(first, last, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::transform(a, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0);

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition.pass.cpp

 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+struct UnaryPred { bool operator()(int) const; };
+
+// Test constraints of the (iterator, sentinel) overload.
+// ======================================================
+
+template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
+concept HasPartitionIter =
+    requires(Iter&& iter, Sent&& sent, Pred&& pred) {
+      std::ranges::partition(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
+    };
+
+static_assert(HasPartitionIter<int*, int*, UnaryPred>);
+
+// !permutable<I>
+static_assert(!HasPartitionIter<PermutableNotForwardIterator>);
+static_assert(!HasPartitionIter<PermutableNotSwappable>);
+
+// !sentinel_for<S, I>
+static_assert(!HasPartitionIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasPartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !indirect_unary_predicate<projected<I, Proj>>
+static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
+
+// Test constraints of the (range) overload.
+// =========================================
+
+template <class Range, class Pred>
+concept HasPartitionRange =
+    requires(Range&& range, Pred&& pred) {
+      std::ranges::partition(std::forward<Range>(range), std::forward<Pred>(pred));
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasPartitionRange<R<int*>, UnaryPred>);
+
+// !forward_range<R>
+static_assert(!HasPartitionRange<ForwardRangeNotDerivedFrom, UnaryPred>);
+static_assert(!HasPartitionRange<ForwardIteratorNotIncrementable, UnaryPred>);
+
+// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
+
+// !permutable<iterator_t<R>>
+static_assert(!HasPartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
+static_assert(!HasPartitionRange<R<PermutableNotSwappable>, UnaryPred>);
+
+// `partition` isn't a stable algorithm so this function cannot test the exact output.
+template <class Iter, class Sent, size_t N, class Pred>
+constexpr void test_one(std::array<int, N> input, Pred pred, size_t partition_point) {
+  auto neg_pred = [&](int x) { return !pred(x); };
+
+  { // (iterator, sentinel) overload.
+    auto partitioned = input;
+    auto b = Iter(partitioned.data());
+    auto e = Sent(Iter(partitioned.data() + partitioned.size()));
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::partition(b, e, pred);
+
+    assert(base(result.begin()) == partitioned.data() + partition_point);
+    assert(base(result.end()) == partitioned.data() + partitioned.size());
+
+    assert(std::ranges::all_of(b, result.begin(), pred));
+    assert(std::ranges::all_of(result.begin(), e, neg_pred));
+  }
+
+  { // (range) overload.
+    auto partitioned = input;
+    auto b = Iter(partitioned.data());
+    auto e = Sent(Iter(partitioned.data() + partitioned.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::partition(range, pred);
+
+    assert(base(result.begin()) == partitioned.data() + partition_point);
+    assert(base(result.end()) == partitioned.data() + partitioned.size());
+
+    assert(std::ranges::all_of(b, result.begin(), pred));
+    assert(std::ranges::all_of(result.begin(), e, neg_pred));
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterators_2() {
+  auto is_odd = [](int x) { return x % 2 != 0; };
+
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, is_odd, 0);
+  // 1-element sequence, the element satisfies the predicate.
+  test_one<Iter, Sent, 1>({1}, is_odd, 1);
+  // 1-element sequence, the element doesn't satisfy the predicate.
+  test_one<Iter, Sent, 1>({2}, is_odd, 0);
+  // 2-element sequence, not in order.
+  test_one<Iter, Sent, 2>({2, 1}, is_odd, 1);
+  // 2-element sequence, already in order.
+  test_one<Iter, Sent, 2>({1, 2}, is_odd, 1);
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({2, 1, 3}, is_odd, 2);
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, 4);
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, 3);
+  // All elements are the same and satisfy the predicate.
+  test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3);
+  // All elements are the same and don't satisfy the predicate.
+  test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0);
+  // Already partitioned.
+  test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3);
+  // Reverse-partitioned.
+  test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3);
+  // Repeating pattern.
+  test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3);
+}
+
+template <class Iter>
+constexpr void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_1<forward_iterator<int*>>();
+  test_iterators_1<bidirectional_iterator<int*>>();
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
 
 constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+  test_iterators();
+
+  { // A custom projection works.
+    const std::array input = {1, -1};
+    auto is_negative = [](int x) { return x < 0; };
+    auto negate = [](int x) { return -x; };
+    const std::array expected_no_proj = {-1, 1};
+    const std::array expected_with_proj = {1, -1};
+
+    { // (iterator, sentinel) overload.
+      {
+        auto in = input;
+        std::ranges::partition(in.begin(), in.end(), is_negative);
+        assert(in == expected_no_proj);
+      }
+      {
+        auto in = input;
+        std::ranges::partition(in.begin(), in.end(), is_negative, negate);
+        assert(in == expected_with_proj);
+      }
+    }
+
+    { // (range) overload.
+      {
+        auto in = input;
+        std::ranges::partition(in, is_negative);
+        assert(in == expected_no_proj);
+      }
+      {
+        auto in = input;
+        std::ranges::partition(in, is_negative, negate);
+        assert(in == expected_with_proj);
+      }
+    }
+  }
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp

 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+struct UnaryPred { bool operator()(int) const; };
 
-constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+// Test constraints of the (iterator, sentinel) overload.
+// ======================================================
 
-  return true;
+template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
+concept HasStablePartitionIter =
+    requires(Iter&& iter, Sent&& sent, Pred&& pred) {
+      std::ranges::stable_partition(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
+    };
+
+static_assert(HasStablePartitionIter<int*, int*, UnaryPred>);
+
+// !bidirectional_iterator<I>
+static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasStablePartitionIter<BidirectionalIteratorNotDecrementable>);
+
+// !sentinel_for<S, I>
+static_assert(!HasStablePartitionIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasStablePartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !indirect_unary_predicate<projected<I, Proj>>
+static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasStablePartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
+
+// !permutable<I>
+static_assert(!HasStablePartitionIter<PermutableNotForwardIterator>);
+static_assert(!HasStablePartitionIter<PermutableNotSwappable>);
+
+// Test constraints of the (range) overload.
+// =========================================
+
+template <class Range, class Pred>
+concept HasStablePartitionRange =
+    requires(Range&& range, Pred&& pred) {
+      std::ranges::stable_partition(std::forward<Range>(range), std::forward<Pred>(pred));
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasStablePartitionRange<R<int*>, UnaryPred>);
+
+// !bidirectional_range<R>
+static_assert(!HasStablePartitionRange<BidirectionalRangeNotDerivedFrom, UnaryPred>);
+static_assert(!HasStablePartitionRange<BidirectionalRangeNotDecrementable, UnaryPred>);
+
+// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasStablePartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
+
+// !permutable<iterator_t<R>>
+static_assert(!HasStablePartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
+static_assert(!HasStablePartitionRange<R<PermutableNotSwappable>, UnaryPred>);
+
+template <class Iter, class Sent, size_t N, class Pred>
+void test_one(std::array<int, N> input, Pred pred, size_t partition_point, std::array<int, N> expected) {
+  auto neg_pred = [&](int x) { return !pred(x); };
+
+  { // (iterator, sentinel) overload.
+    auto partitioned = input;
+    auto b = Iter(partitioned.data());
+    auto e = Sent(Iter(partitioned.data() + partitioned.size()));
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::stable_partition(b, e, pred);
+
+    assert(partitioned == expected);
+    assert(base(result.begin()) == partitioned.data() + partition_point);
+    assert(base(result.end()) == partitioned.data() + partitioned.size());
+
+    assert(std::ranges::all_of(b, result.begin(), pred));
+    assert(std::ranges::all_of(result.begin(), e, neg_pred));
+  }
+
+  { // (range) overload.
+    auto partitioned = input;
+    auto b = Iter(partitioned.data());
+    auto e = Sent(Iter(partitioned.data() + partitioned.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::stable_partition(range, pred);
+
+    assert(partitioned == expected);
+    assert(base(result.begin()) == partitioned.data() + partition_point);
+    assert(base(result.end()) == partitioned.data() + partitioned.size());
+
+    assert(std::ranges::all_of(b, result.begin(), pred));
+    assert(std::ranges::all_of(result.begin(), e, neg_pred));
+  }
+}
+
+template <class Iter, class Sent>
+void test_iterators_2() {
+  auto is_odd = [](int x) { return x % 2 != 0; };
+
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, is_odd, 0, {});
+  // 1-element sequence, the element satisfies the predicate.
+  test_one<Iter, Sent, 1>({1}, is_odd, 1, {1});
+  // 1-element sequence, the element doesn't satisfy the predicate.
+  test_one<Iter, Sent, 1>({2}, is_odd, 0, {2});
+  // 2-element sequence, not in order.
+  test_one<Iter, Sent, 2>({2, 1}, is_odd, 1, {1, 2});
+  // 2-element sequence, already in order.
+  test_one<Iter, Sent, 2>({1, 2}, is_odd, 1, {1, 2});
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({2, 1, 3}, is_odd, 2, {1, 3, 2});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, 4, {1, 3, 11, 5, 2, 6, 8, 4});
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, 3, {1, 3, 1, 2, 6, 2, 8, 6});
+  // All elements are the same and satisfy the predicate.
+  test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3, {1, 1, 1});
+  // All elements are the same and don't satisfy the predicate.
+  test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0, {2, 2, 2});
+  // Already partitioned.
+  test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3, {1, 3, 5, 4, 6, 8});
+  // Reverse-partitioned.
+  test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3, {1, 3, 5, 4, 6, 8});
+  // Repeating pattern.
+  test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3, {1, 1, 1, 2, 2, 2});
+}
+
+template <class Iter>
+void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+void test_iterators() {
+  test_iterators_1<bidirectional_iterator<int*>>();
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
+
+void test() {
+  test_iterators();
+
+  { // The algorithm is stable (equivalent elements remain in the same order).
+    struct OrderedValue {
+      int value;
+      double original_order;
+      bool operator==(const OrderedValue&) const = default;
+    };
+
+    auto is_odd = [](OrderedValue x) { return x.value % 2 != 0; };
+
+    using V = OrderedValue;
+    using Array = std::array<V, 20>;
+    Array orig_in = {
+      V{10, 2.1}, {12, 2.2}, {3, 1.1}, {5, 1.2}, {3, 1.3}, {3, 1.4}, {11, 1.5}, {12, 2.3}, {4, 2.4}, {4, 2.5},
+      {4, 2.6}, {1, 1.6}, {6, 2.7}, {3, 1.7}, {10, 2.8}, {8, 2.9}, {12, 2.10}, {1, 1.8}, {1, 1.9}, {5, 1.10}
+    };
+    Array expected = {
+      V{3, 1.1}, {5, 1.2}, {3, 1.3}, {3, 1.4}, {11, 1.5}, {1, 1.6}, {3, 1.7}, {1, 1.8}, {1, 1.9}, {5, 1.10},
+      {10, 2.1}, {12, 2.2}, {12, 2.3}, {4, 2.4}, {4, 2.5}, {4, 2.6}, {6, 2.7}, {10, 2.8}, {8, 2.9}, {12, 2.10}
+    };
+
+    {
+      auto in = orig_in;
+      std::ranges::stable_partition(in.begin(), in.end(), is_odd);
+      assert(in == expected);
+    }
+
+    {
+      auto in = orig_in;
+      std::ranges::stable_partition(in, is_odd);
+      assert(in == expected);
+    }
+  }
+
+  { // A custom projection works.
+    const std::array input = {1, -1};
+    auto is_negative = [](int x) { return x < 0; };
+    auto negate = [](int x) { return -x; };
+    const std::array expected_no_proj = {-1, 1};
+    const std::array expected_with_proj = {1, -1};
+
+    { // (iterator, sentinel) overload.
+      {
+        auto in = input;
+        std::ranges::partition(in.begin(), in.end(), is_negative);
+        assert(in == expected_no_proj);
+      }
+      {
+        auto in = input;
+        std::ranges::partition(in.begin(), in.end(), is_negative, negate);
+        assert(in == expected_with_proj);
+      }
+    }
+
+    { // (range) overload.
+      {
+        auto in = input;
+        std::ranges::partition(in, is_negative);
+        assert(in == expected_no_proj);
+      }
+      {
+        auto in = input;
+        std::ranges::partition(in, is_negative, negate);
+        assert(in == expected_with_proj);
+      }
+    }
+  }
 }
 
 int main(int, char**) {
   test();
-  static_assert(test());
+  // Note: `stable_partition` is not `constexpr`.
 
   return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp

void test_all() {
   //in2_pred(std::ranges::partial_sort_copy, in, in2, binary_pred);
   in2_out_pred(std::ranges::merge, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_difference, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_intersection, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_symmetric_difference, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_union, in, in2, out, binary_pred);
   in_pred(std::ranges::remove_if, in, unary_pred);
   //in_pred(std::ranges::unique, in, binary_pred);
-  //in_pred(std::ranges::partition, in, binary_pred);
-  //in_pred(std::ranges::stable_partition, in, binary_pred);
+  in_pred(std::ranges::partition, in, unary_pred);
+  in_pred(std::ranges::stable_partition, in, unary_pred);
   in_pred(std::ranges::sort, in, binary_pred);
   in_pred(std::ranges::stable_sort, in, binary_pred);
   //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
   in_mid_pred(std::ranges::nth_element, in, mid, binary_pred);
   //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
   in_pred(std::ranges::make_heap, in, binary_pred);
   in_pred(std::ranges::push_heap, in, binary_pred);
   in_pred(std::ranges::pop_heap, in, binary_pred);
   in_pred(std::ranges::sort_heap, in, binary_pred);
   //in_pred(std::ranges::prev_permutation, in, binary_pred);
   //in_pred(std::ranges::next_permutation, in, binary_pred);
 }

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp

void test_all() {
   in2_out_pred(std::ranges::set_symmetric_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   in2_out_pred(std::ranges::set_union, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   in_val(std::ranges::remove, in, x, &Bar::val);
   in_pred(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val);
   // `reverse` has neither a projection nor a predicate.
   // `rotate` has neither a projection nor a predicate.
   // `shuffle` has neither a projection nor a predicate.
   //in_pred(std::ranges::unique, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::partition, in, &Foo::binary_pred, &Bar::val);
-  //in_pred(std::ranges::stable_partition, in, &Foo::binary_pred, &Bar::val);
+  in_pred(std::ranges::partition, in, &Foo::unary_pred, &Bar::val);
+  in_pred(std::ranges::stable_partition, in, &Foo::unary_pred, &Bar::val);
   in_pred(std::ranges::sort, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val);
   //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
   in_mid_pred(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val);
   //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
   in_pred(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
   //in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
   //in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
 }

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

constexpr bool test_all() {
   test(std::ranges::set_symmetric_difference, in, in2, out);
   test(std::ranges::set_union, in, in2, out);
   test(std::ranges::remove, in, x);
   test(std::ranges::remove_if, in, unary_pred);
   test(std::ranges::reverse, in);
   //test_mid(std::ranges::rotate, in, mid);
   //test(std::ranges::shuffle, in, rand_gen);
   //test(std::ranges::unique, in);
-  //test(std::ranges::partition, in, binary_pred);
-  //if (!std::is_constant_evaluated())
-  //  test(std::ranges::stable_partition, in, binary_pred);
+  test(std::ranges::partition, in, unary_pred);
+  if (!std::is_constant_evaluated())
+    test(std::ranges::stable_partition, in, unary_pred);
   test(std::ranges::sort, in);
   // TODO: `stable_sort` requires `ranges::rotate` to be implemented.
   //if (!std::is_constant_evaluated())
   //  test(std::ranges::stable_sort, in);
   //test_mid(std::ranges::partial_sort, in, mid);
   test_mid(std::ranges::nth_element, in, mid);
   //if (!std::is_constant_evaluated())
   //  test_mid(std::ranges::inplace_merge, in, mid);

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 static_assert(test(std::ranges::mismatch, a, a));
 static_assert(test(std::ranges::move, a, a));
 static_assert(test(std::ranges::move_backward, a, a));
 //static_assert(test(std::ranges::next_permutation, a));
 static_assert(test(std::ranges::none_of, a, odd));
 static_assert(test(std::ranges::nth_element, a, a+5));
 //static_assert(test(std::ranges::partial_sort, a, a+5));
 //static_assert(test(std::ranges::partial_sort_copy, a, a));
-//static_assert(test(std::ranges::partition, a, odd));
+static_assert(test(std::ranges::partition, a, odd));
 //static_assert(test(std::ranges::partition_copy, a, a, a, odd));
 //static_assert(test(std::ranges::partition_point, a, odd));
 static_assert(test(std::ranges::pop_heap, a));
 //static_assert(test(std::ranges::prev_permutation, a));
 static_assert(test(std::ranges::push_heap, a));
 static_assert(test(std::ranges::remove, a, 42));
 //static_assert(test(std::ranges::remove_copy, a, a, 42));
 //static_assert(test(std::ranges::remove_copy_if, a, a, odd));

 static_assert(test(std::ranges::search_n, a, 10, 42));
 static_assert(test(std::ranges::set_difference, a, a, a));
 static_assert(test(std::ranges::set_intersection, a, a, a));
 static_assert(test(std::ranges::set_symmetric_difference, a, a, a));
 static_assert(test(std::ranges::set_union, a, a, a));
 //static_assert(test(std::ranges::shuffle, a, g));
 static_assert(test(std::ranges::sort, a));
 static_assert(test(std::ranges::sort_heap, a));
-//static_assert(test(std::ranges::stable_partition, a, odd));
+static_assert(test(std::ranges::stable_partition, a, odd));
 static_assert(test(std::ranges::stable_sort, a));
 //static_assert(test(std::ranges::starts_with, a, a));
 static_assert(test(std::ranges::swap_ranges, a, a));
 static_assert(test(std::ranges::transform, a, a, triple));
 //static_assert(test(std::ranges::unique, a));
 //static_assert(test(std::ranges::unique_copy, a, a));
 static_assert(test(std::ranges::upper_bound, a, 42));