diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -59,7 +59,7 @@ Write,sample,Not assigned,n/a,Not started Write,unique_copy,Not assigned,n/a,Not started Write,partition_copy,Konstantin Varlamov,`D130070 `_,✅ -Write,partial_sort_copy,Konstantin Varlamov,n/a,In progress +Write,partial_sort_copy,Konstantin Varlamov,`D130532 `_,✅ Merge,merge,Hui Xie,`D128611 `_,✅ Merge,set_difference,Hui Xie,`D128983 `_,✅ Merge,set_intersection,Hui Xie,`D129233 `_,✅ diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h --- a/libcxx/include/__algorithm/make_heap.h +++ b/libcxx/include/__algorithm/make_heap.h @@ -25,7 +25,7 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { +void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp) { using _CompRef = typename __comp_ref_type<_Compare>::type; _CompRef __comp_ref = __comp; @@ -34,7 +34,7 @@ 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<_AlgPolicy, _CompRef>(__first, __comp_ref, __n, __first + __start); + std::__sift_down<_AlgPolicy>(__first, __comp_ref, __n, __first + __start); } } } diff --git a/libcxx/include/__algorithm/make_projected.h b/libcxx/include/__algorithm/make_projected.h --- a/libcxx/include/__algorithm/make_projected.h +++ b/libcxx/include/__algorithm/make_projected.h @@ -14,51 +14,91 @@ #include <__functional/identity.h> #include <__functional/invoke.h> #include <__type_traits/decay.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/integral_constant.h> #include <__type_traits/is_member_pointer.h> +#include <__type_traits/is_same.h> +#include <__utility/declval.h> #include <__utility/forward.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 { - template -_LIBCPP_HIDE_FROM_ABI constexpr static -decltype(auto) __make_projected_pred(_Pred& __pred, _Proj& __proj) { - if constexpr (same_as, identity> && !is_member_pointer_v>) { - // 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; +struct _ProjectedPred { + _Pred& __pred; // Can be a unary or a binary predicate. + _Proj& __proj; + + _LIBCPP_CONSTEXPR _ProjectedPred(_Pred& __pred_arg, _Proj& __proj_arg) : __pred(__pred_arg), __proj(__proj_arg) {} + + template + typename __invoke_of<_Pred&, + decltype(std::__invoke(std::declval<_Proj&>(), std::declval<_Tp>())) + >::type + _LIBCPP_CONSTEXPR operator()(_Tp&& __v) const { + return std::__invoke(__pred, std::__invoke(__proj, std::forward<_Tp>(__v))); + } - } else { - return [&](auto&& __x) { - return std::invoke(__pred, std::invoke(__proj, std::forward(__x))); - }; + template + typename __invoke_of<_Pred&, + decltype(std::__invoke(std::declval<_Proj&>(), std::declval<_T1>())), + decltype(std::__invoke(std::declval<_Proj&>(), std::declval<_T2>())) + >::type + _LIBCPP_CONSTEXPR operator()(_T1&& __lhs, _T2&& __rhs) const { + return std::__invoke(__pred, + std::__invoke(__proj, std::forward<_T1>(__lhs)), + std::__invoke(__proj, std::forward<_T2>(__rhs))); } -} -template -_LIBCPP_HIDE_FROM_ABI constexpr static -decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) { - if constexpr (same_as, identity> && !is_member_pointer_v>) { - // 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; +}; - } else { - return [&](auto&& __lhs, auto&& __rhs) { - return std::invoke(__comp, - std::invoke(__proj, std::forward(__lhs)), - std::invoke(__proj, std::forward(__rhs))); - }; - } +template +struct __can_use_pristine_comp : false_type {}; + +template +struct __can_use_pristine_comp<_Pred, _Proj, __enable_if_t< + !is_member_pointer::type>::value && ( +#if _LIBCPP_STD_VER > 17 + is_same::type, identity>::value || +#endif + is_same::type, __identity>::value + ) +> > : true_type {}; + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static +__enable_if_t< + !__can_use_pristine_comp<_Pred, _Proj>::value, + _ProjectedPred<_Pred, _Proj> +> +__make_projected(_Pred& __pred, _Proj& __proj) { + return _ProjectedPred<_Pred, _Proj>(__pred, __proj); +} + +// Avoid creating the functor and just use the pristine comparator -- for certain algorithms, this would enable +// optimizations that rely on the type of the comparator. Additionally, this results in less layers of indirection in +// the call stack when the comparator is invoked, even in an unoptimized build. +template ::value> > +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static +__enable_if_t< + __can_use_pristine_comp<_Pred, _Proj>::value, + _Pred& +> +__make_projected(_Pred& __pred, _Proj&) { + return __pred; } +_LIBCPP_END_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + template _LIBCPP_HIDE_FROM_ABI constexpr static decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) { diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h --- a/libcxx/include/__algorithm/partial_sort.h +++ b/libcxx/include/__algorithm/partial_sort.h @@ -31,12 +31,12 @@ template _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __partial_sort_impl( - _RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, _Compare __comp) { + _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); + std::__make_heap<_AlgPolicy>(__first, __middle, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; _RandomAccessIterator __i = __middle; @@ -45,11 +45,11 @@ if (__comp(*__i, *__first)) { _IterOps<_AlgPolicy>::iter_swap(__i, __first); - std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first); + std::__sift_down<_AlgPolicy>(__first, __comp, __len, __first); } } - std::__sort_heap<_AlgPolicy, _Compare>(std::move(__first), std::move(__middle), __comp); + std::__sort_heap<_AlgPolicy>(std::move(__first), std::move(__middle), __comp); return __i; } @@ -64,7 +64,7 @@ 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); + auto __last_iter = std::__partial_sort_impl<_AlgPolicy>(__first, __middle, __last, static_cast<_Comp_ref>(__comp)); std::__debug_randomize_range<_AlgPolicy>(__middle, __last); diff --git a/libcxx/include/__algorithm/partial_sort_copy.h b/libcxx/include/__algorithm/partial_sort_copy.h --- a/libcxx/include/__algorithm/partial_sort_copy.h +++ b/libcxx/include/__algorithm/partial_sort_copy.h @@ -13,10 +13,16 @@ #include <__algorithm/comp_ref_type.h> #include <__algorithm/iterator_operations.h> #include <__algorithm/make_heap.h> +#include <__algorithm/make_projected.h> #include <__algorithm/sift_down.h> #include <__algorithm/sort_heap.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> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -24,27 +30,33 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator -__partial_sort_copy(_InputIterator __first, _InputIterator __last, - _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_InputIterator, _RandomAccessIterator> +__partial_sort_copy(_InputIterator __first, _Sentinel1 __last, + _RandomAccessIterator __result_first, _Sentinel2 __result_last, + _Compare&& __comp, _Proj1&& __proj1, _Proj2&& __proj2) { _RandomAccessIterator __r = __result_first; + auto&& __projected_comp = std::__make_projected(__comp, __proj2); + if (__r != __result_last) { for (; __first != __last && __r != __result_last; ++__first, (void) ++__r) *__r = *__first; - std::__make_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp); + std::__make_heap<_AlgPolicy>(__result_first, __r, __projected_comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; for (; __first != __last; ++__first) - if (__comp(*__first, *__result_first)) - { + if (std::__invoke(__comp, std::__invoke(__proj1, *__first), std::__invoke(__proj2, *__result_first))) { *__result_first = *__first; - std::__sift_down<_AlgPolicy, _Compare>(__result_first, __comp, __len, __result_first); + std::__sift_down<_AlgPolicy>(__result_first, __projected_comp, __len, __result_first); } - std::__sort_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp); + std::__sort_heap<_AlgPolicy>(__result_first, __r, __projected_comp); } - return __r; + + return pair<_InputIterator, _RandomAccessIterator>( + _IterOps<_AlgPolicy>::next(std::move(__first), std::move(__last)), std::move(__r)); } template @@ -53,9 +65,13 @@ 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 std::__partial_sort_copy<_ClassicAlgPolicy, _Comp_ref>( - __first, __last, __result_first, __result_last, __comp); + static_assert(__is_callable<_Compare, decltype(*__first), decltype(*__result_first)>::value, + "Comparator has to be callable"); + + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + auto __result = std::__partial_sort_copy<_ClassicAlgPolicy>(__first, __last, __result_first, __result_last, + static_cast<_Comp_ref>(__comp), __identity(), __identity()); + return __result.second; } template diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h --- a/libcxx/include/__algorithm/pop_heap.h +++ b/libcxx/include/__algorithm/pop_heap.h @@ -38,7 +38,7 @@ using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; if (__len > 1) { 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); + _RandomAccessIterator __hole = std::__floyd_sift_down<_AlgPolicy>(__first, __comp_ref, __len); --__last; if (__hole == __last) { @@ -47,7 +47,7 @@ *__hole = _IterOps<_AlgPolicy>::__iter_move(__last); ++__hole; *__last = std::move(__top); - std::__sift_up<_AlgPolicy, _CompRef>(__first, __hole, __comp_ref, __hole - __first); + std::__sift_up<_AlgPolicy>(__first, __hole, __comp_ref, __hole - __first); } } } diff --git a/libcxx/include/__algorithm/push_heap.h b/libcxx/include/__algorithm/push_heap.h --- a/libcxx/include/__algorithm/push_heap.h +++ b/libcxx/include/__algorithm/push_heap.h @@ -25,7 +25,7 @@ template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, +void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len) { using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; diff --git a/libcxx/include/__algorithm/ranges_is_heap.h b/libcxx/include/__algorithm/ranges_is_heap.h --- a/libcxx/include/__algorithm/ranges_is_heap.h +++ b/libcxx/include/__algorithm/ranges_is_heap.h @@ -39,7 +39,7 @@ _LIBCPP_HIDE_FROM_ABI constexpr static bool __is_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); auto __result = std::__is_heap_until(std::move(__first), std::move(__last_iter), __projected_comp); return __result == __last; diff --git a/libcxx/include/__algorithm/ranges_is_heap_until.h b/libcxx/include/__algorithm/ranges_is_heap_until.h --- a/libcxx/include/__algorithm/ranges_is_heap_until.h +++ b/libcxx/include/__algorithm/ranges_is_heap_until.h @@ -40,7 +40,7 @@ _LIBCPP_HIDE_FROM_ABI constexpr static _Iter __is_heap_until_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); return std::__is_heap_until(std::move(__first), std::move(__last_iter), __projected_comp); } diff --git a/libcxx/include/__algorithm/ranges_make_heap.h b/libcxx/include/__algorithm/ranges_make_heap.h --- a/libcxx/include/__algorithm/ranges_make_heap.h +++ b/libcxx/include/__algorithm/ranges_make_heap.h @@ -45,7 +45,7 @@ _Iter __make_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); std::__make_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; diff --git a/libcxx/include/__algorithm/ranges_nth_element.h b/libcxx/include/__algorithm/ranges_nth_element.h --- a/libcxx/include/__algorithm/ranges_nth_element.h +++ b/libcxx/include/__algorithm/ranges_nth_element.h @@ -44,7 +44,7 @@ _Iter __nth_element_fn_impl(_Iter __first, _Iter __nth, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); 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 --- a/libcxx/include/__algorithm/ranges_partial_sort.h +++ b/libcxx/include/__algorithm/ranges_partial_sort.h @@ -43,7 +43,7 @@ template _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); + auto&& __projected_comp = std::__make_projected(__comp, __proj); return std::__partial_sort<_RangeAlgPolicy>(std::move(__first), std::move(__middle), __last, __projected_comp); } diff --git a/libcxx/include/__algorithm/ranges_partial_sort_copy.h b/libcxx/include/__algorithm/ranges_partial_sort_copy.h --- a/libcxx/include/__algorithm/ranges_partial_sort_copy.h +++ b/libcxx/include/__algorithm/ranges_partial_sort_copy.h @@ -10,11 +10,11 @@ #define _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_COPY_H #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/partial_sort_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> @@ -23,7 +23,6 @@ #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) @@ -52,9 +51,11 @@ partial_sort_copy_result<_Iter1, _Iter2> operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result_first, _Sent2 __result_last, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result_first; (void)__result_last; (void)__comp; (void)__proj1; (void)__proj2; - return {}; + auto __result = std::__partial_sort_copy<_RangeAlgPolicy>( + std::move(__first), std::move(__last), std::move(__result_first), std::move(__result_last), + __comp, __proj1, __proj2 + ); + return {std::move(__result.first), std::move(__result.second)}; } template , borrowed_iterator_t<_Range2>> operator()(_Range1&& __range, _Range2&& __result_range, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { - // TODO: implement - (void)__range; (void)__result_range; (void)__comp; (void)__proj1; (void)__proj2; - return {}; + auto __result = std::__partial_sort_copy<_RangeAlgPolicy>( + ranges::begin(__range), ranges::end(__range), ranges::begin(__result_range), ranges::end(__result_range), + __comp, __proj1, __proj2 + ); + return {std::move(__result.first), std::move(__result.second)}; } }; diff --git a/libcxx/include/__algorithm/ranges_partition.h b/libcxx/include/__algorithm/ranges_partition.h --- a/libcxx/include/__algorithm/ranges_partition.h +++ b/libcxx/include/__algorithm/ranges_partition.h @@ -44,7 +44,7 @@ template _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&& __projected_pred = std::__make_projected(__pred, __proj); auto __result = std::__partition<_RangeAlgPolicy>( std::move(__first), std::move(__last), __projected_pred, __iterator_concept<_Iter>()); diff --git a/libcxx/include/__algorithm/ranges_pop_heap.h b/libcxx/include/__algorithm/ranges_pop_heap.h --- a/libcxx/include/__algorithm/ranges_pop_heap.h +++ b/libcxx/include/__algorithm/ranges_pop_heap.h @@ -46,7 +46,7 @@ auto __last_iter = ranges::next(__first, __last); auto __len = __last_iter - __first; - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); 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 --- a/libcxx/include/__algorithm/ranges_push_heap.h +++ b/libcxx/include/__algorithm/ranges_push_heap.h @@ -45,7 +45,7 @@ _Iter __push_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); std::__push_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; diff --git a/libcxx/include/__algorithm/ranges_sort.h b/libcxx/include/__algorithm/ranges_sort.h --- a/libcxx/include/__algorithm/ranges_sort.h +++ b/libcxx/include/__algorithm/ranges_sort.h @@ -44,7 +44,7 @@ _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); 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 --- a/libcxx/include/__algorithm/ranges_sort_heap.h +++ b/libcxx/include/__algorithm/ranges_sort_heap.h @@ -45,7 +45,7 @@ _Iter __sort_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); 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 --- a/libcxx/include/__algorithm/ranges_stable_partition.h +++ b/libcxx/include/__algorithm/ranges_stable_partition.h @@ -49,7 +49,7 @@ _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&& __projected_pred = std::__make_projected(__pred, __proj); auto __result = std::__stable_partition<_RangeAlgPolicy>( std::move(__first), __last_iter, __projected_pred, __iterator_concept<_Iter>()); diff --git a/libcxx/include/__algorithm/ranges_stable_sort.h b/libcxx/include/__algorithm/ranges_stable_sort.h --- a/libcxx/include/__algorithm/ranges_stable_sort.h +++ b/libcxx/include/__algorithm/ranges_stable_sort.h @@ -44,7 +44,7 @@ static _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { auto __last_iter = ranges::next(__first, __last); - auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + auto&& __projected_comp = std::__make_projected(__comp, __proj); std::__stable_sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h --- a/libcxx/include/__algorithm/sift_down.h +++ b/libcxx/include/__algorithm/sift_down.h @@ -23,7 +23,7 @@ template _LIBCPP_CONSTEXPR_AFTER_CXX11 void -__sift_down(_RandomAccessIterator __first, _Compare __comp, +__sift_down(_RandomAccessIterator __first, _Compare&& __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, _RandomAccessIterator __start) { @@ -79,7 +79,7 @@ template _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator -__floyd_sift_down(_RandomAccessIterator __first, _Compare __comp, +__floyd_sift_down(_RandomAccessIterator __first, _Compare&& __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len) { using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; diff --git a/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h --- a/libcxx/include/__algorithm/sort_heap.h +++ b/libcxx/include/__algorithm/sort_heap.h @@ -26,13 +26,13 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { +void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp) { using _CompRef = typename __comp_ref_type<_Compare>::type; _CompRef __comp_ref = __comp; using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) - std::__pop_heap<_AlgPolicy, _CompRef>(__first, __last, __comp_ref, __n); + std::__pop_heap<_AlgPolicy>(__first, __last, __comp_ref, __n); } template diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -446,6 +446,25 @@ indirect_unary_predicate, Proj>> Pred> constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {}); // since C++20 + template S1, + random_access_iterator I2, sentinel_for S2, + class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> + requires indirectly_copyable && sortable && + indirect_strict_weak_order, projected> + constexpr partial_sort_copy_result + partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last, + Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + + template + requires indirectly_copyable, iterator_t> && + sortable, Comp, Proj2> && + indirect_strict_weak_order, Proj1>, + projected, Proj2>> + constexpr partial_sort_copy_result, borrowed_iterator_t> + partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + template S, class Proj = identity, indirect_strict_weak_order> Comp = ranges::less> constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 @@ -1628,6 +1647,7 @@ #include <__algorithm/ranges_none_of.h> #include <__algorithm/ranges_nth_element.h> #include <__algorithm/ranges_partial_sort.h> +#include <__algorithm/ranges_partial_sort_copy.h> #include <__algorithm/ranges_partition.h> #include <__algorithm/ranges_partition_copy.h> #include <__algorithm/ranges_partition_point.h> diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -173,8 +173,8 @@ (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::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_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -156,8 +156,8 @@ (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::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_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/ranges_partial_sort_copy.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/ranges_partial_sort_copy.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/ranges_partial_sort_copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/ranges_partial_sort_copy.pass.cpp @@ -12,39 +12,286 @@ // // template S1, -// random_access_iterator I2, sentinel_for S2, -// class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> -// requires indirectly_copyable && sortable && -// indirect_strict_weak_order, projected> -// constexpr partial_sort_copy_result -// partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last, -// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 +// random_access_iterator I2, sentinel_for S2, +// class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> +// requires indirectly_copyable && sortable && +// indirect_strict_weak_order, projected> +// constexpr partial_sort_copy_result +// partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last, +// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 // -// template -// requires indirectly_copyable, iterator_t> && -// sortable, Comp, Proj2> && -// indirect_strict_weak_order, Proj1>, -// projected, Proj2>> -// constexpr partial_sort_copy_result, borrowed_iterator_t> -// partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {}, -// Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 +// template +// requires indirectly_copyable, iterator_t> && +// sortable, Comp, Proj2> && +// indirect_strict_weak_order, Proj1>, +// projected, Proj2>> +// constexpr partial_sort_copy_result, borrowed_iterator_t> +// partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 #include #include #include #include #include +#include +#include "MoveOnly.h" #include "almost_satisfies_types.h" #include "test_iterators.h" -// TODO: SFINAE tests. +// Test constraints of the (iterator, sentinel) overload. +// ====================================================== + +template +concept HasPartialSortCopyIter = + requires(Iter1&& first1, Sent1&& last1, Iter2&& first2, Sent2&& last2, Comp&& comp) { + std::ranges::partial_sort_copy(std::forward(first1), std::forward(last1), + std::forward(first2), std::forward(last2), std::forward(comp)); + }; + +static_assert(HasPartialSortCopyIter); + +// !input_iterator +static_assert(!HasPartialSortCopyIter); +static_assert(!HasPartialSortCopyIter); +static_assert(!HasPartialSortCopyIter); + +// !sentinel_for +static_assert(!HasPartialSortCopyIter); +static_assert(!HasPartialSortCopyIter); + +// !random_access_iterator +static_assert(!HasPartialSortCopyIter); +static_assert(!HasPartialSortCopyIter); + +// !sentinel_for +static_assert(!HasPartialSortCopyIter); +static_assert(!HasPartialSortCopyIter); + +// !indirect_unary_predicate> +static_assert(!HasPartialSortCopyIter); +static_assert(!HasPartialSortCopyIter); + +// !indirectly_copyable +static_assert(!HasPartialSortCopyIter); + +// !sortable +static_assert(!HasPartialSortCopyIter); + +struct NoComparator {}; +// !indirect_strict_weak_order, projected> +static_assert(!HasPartialSortCopyIter); + +// Test constraints of the (range) overload. +// ====================================================== + +template +using R = UncheckedRange; + +template , class Range2 = R, class Comp = std::ranges::less> +concept HasPartialSortCopyRange = + requires(Range1&& range1, Range2&& range2, Comp&& comp) { + std::ranges::partial_sort_copy(std::forward(range1), std::forward(range2), + std::forward(comp)); + }; + +static_assert(HasPartialSortCopyRange, R, std::ranges::less>); + +// !input_range +static_assert(!HasPartialSortCopyRange); +static_assert(!HasPartialSortCopyRange); +static_assert(!HasPartialSortCopyRange); + +// !random_access_range +static_assert(!HasPartialSortCopyRange, RandomAccessRangeNotDerivedFrom>); +static_assert(!HasPartialSortCopyRange, RandomAccessRangeBadIndex>); + +// !indirectly_copyable, iterator_t> +static_assert(!HasPartialSortCopyRange, R>); + +// !sortable, Comp, Proj2> +static_assert(!HasPartialSortCopyRange, R>); + +// !indirect_strict_weak_order, Proj1>, projected, Proj2>> +static_assert(!HasPartialSortCopyRange, R>); + +static_assert(std::is_same_v, std::ranges::in_out_result>); + +template +constexpr void test_one( + std::array input, size_t input_size, size_t output_size, std::array sorted) { + assert(input_size <= N); + assert(output_size <= N + 1); // To support testing the case where output size exceeds input size. + + using ResultT = std::ranges::partial_sort_copy_result; + // To support testing the case where output size exceeds input size; also makes sure calling `out.data() + int()` is + // valid. + constexpr size_t OutputSize = N + 1; + size_t result_size = std::ranges::min(input_size, output_size); + + auto begin = input.data(); + auto end = input.data() + input_size; + + { // (iterator, sentinel) overload. + std::array out; + auto out_begin = out.data(); + auto out_end = out.data() + output_size; + + std::same_as decltype(auto) result = std::ranges::partial_sort_copy( + Iter(begin), Sent(Iter(end)), OutIter(out_begin), OutSent(OutIter(out_end))); + + assert(base(result.in) == input.data() + input_size); + assert(base(result.out) == out.data() + result_size); + + assert(std::ranges::equal(std::ranges::subrange(out.begin(), out.begin() + result_size), + std::ranges::subrange(sorted.begin(), sorted.begin() + result_size))); + } + + { // (range) overload. + std::array out; + auto out_begin = out.data(); + auto out_end = out.data() + output_size; + auto in_range = std::ranges::subrange(Iter(begin), Sent(Iter(end))); + auto out_range = std::ranges::subrange(OutIter(out_begin), OutSent(OutIter(out_end))); + + std::same_as decltype(auto) result = std::ranges::partial_sort_copy(in_range, out_range); + + assert(base(result.in) == input.data() + input_size); + assert(base(result.out) == out.data() + result_size); + + assert(std::ranges::equal(std::ranges::subrange(out.begin(), out.begin() + result_size), + std::ranges::subrange(sorted.begin(), sorted.begin() + result_size))); + } + +} + +template +constexpr void test_all_subsequences(const std::array input) { + auto sorted = input; + std::sort(sorted.begin(), sorted.end()); + + // Whole input, increasing output size. Also check the case when `output_size` exceeds input size. + for (size_t out_size = 0; out_size <= N + 1; ++out_size) { + test_one(input, N, out_size, sorted); + } +} + +template +constexpr void test_iterators_in_sent1_out_sent2() { + // Empty sequence. + test_all_subsequences({}); + + // 1-element sequence. + test_all_subsequences(std::array{1}); + + // 2-element sequence. + test_all_subsequences(std::array{2, 1}); + + // 3-element sequence. + test_all_subsequences(std::array{2, 1, 3}); + + // Longer sequence. + test_all_subsequences(std::array{2, 1, 3, 6, 8, 4, 11, 5}); + + // Longer sequence with duplicates. + test_all_subsequences(std::array{2, 1, 3, 6, 2, 8, 6}); + + // All elements are the same. + test_all_subsequences(std::array{1, 1, 1}); + + // Already sorted. + test_all_subsequences(std::array{1, 2, 3, 4, 5}); + + // Descending. + test_all_subsequences(std::array{5, 4, 3, 2, 1}); +} + +template +constexpr void test_iterators_in_sent1_out() { + test_iterators_in_sent1_out_sent2(); + test_iterators_in_sent1_out_sent2>(); +} + +template +constexpr void test_iterators_in_sent1() { + test_iterators_in_sent1_out>(); +} + +template +constexpr void test_iterators_in() { + if constexpr (std::sentinel_for) { + test_iterators_in_sent1(); + } + test_iterators_in_sent1>(); +} + +constexpr void test_iterators() { + test_iterators_in>(); + // Omitting other iterator types to reduce the combinatorial explosion. + test_iterators_in>(); + test_iterators_in(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_iterators(); + + { // A custom comparator works. + const std::array in = {1, 2, 3, 4, 5}; + std::ranges::greater comp; + + { + std::array out; + + auto result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), comp); + assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{5, 4})); + } + + { + std::array out; + + auto result = std::ranges::partial_sort_copy(in, out, comp); + assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{5, 4})); + } + } + + { // A custom projection works. + struct A { + int a; + + constexpr A() = default; + constexpr A(int value) : a(value) {} + constexpr auto operator<=>(const A&) const = default; + }; + + const std::array in = {2, 1, 3}; + auto proj1 = [](int value) { return value * -1; }; + auto proj2 = [](A value) { return value.a * -1; }; + // The projections negate the argument, so the array will appear to be sorted in descending order: [3, 2, 1] + // (the projections make it appear to the algorithm as [-3, -2, -1]). + + { + std::array out; + + // No projections: ascending order. + auto result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), {}); + assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{1, 2})); + // Using projections: descending order. + result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), {}, proj1, proj2); + assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{3, 2})); + } + + { + std::array out; + + auto result = std::ranges::partial_sort_copy(in, out, {}); + assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{1, 2})); + result = std::ranges::partial_sort_copy(in, out, {}, proj1, proj2); + assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{3, 2})); + } + } return true; } diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp @@ -30,7 +30,7 @@ static_assert(std::is_same_v, copy_backward_result>); static_assert(std::is_same_v, move_result>); static_assert(std::is_same_v, move_backward_result>); -// static_assert(std::is_same_v, partial_sort_copy_result>); +static_assert(std::is_same_v, partial_sort_copy_result>); // static_assert(std::is_same_v, remove_copy_result>); // static_assert(std::is_same_v, remove_copy_if_result>); // static_assert(std::is_same_v, replace_copy_result>); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -76,7 +76,7 @@ using std::ranges::mismatch_result; using std::ranges::move_result; //using std::ranges::move_backward_result; - //using std::ranges::partial_sort_copy_result; + using std::ranges::partial_sort_copy_result; using std::ranges::partition_copy_result; //using std::ranges::remove_copy_result; //using std::ranges::remove_copy_if_result; @@ -159,9 +159,9 @@ dangling_1st>(std::ranges::rotate_copy, in, mid, out); //dangling_1st>(std::ranges::unique_copy, in, out); dangling_1st>(std::ranges::partition_copy, in, out, out2, unary_pred); - //dangling_1st>(std::ranges::partial_sort_copy, in, in2); - //dangling_2nd>(std::ranges::partial_sort_copy, in, in2); - //dangling_both>(std::ranges::partial_sort_copy, in, in2); + dangling_1st>(std::ranges::partial_sort_copy, in, in2); + dangling_2nd>(std::ranges::partial_sort_copy, in, in2); + dangling_both>(std::ranges::partial_sort_copy, in, in2); dangling_1st>(std::ranges::merge, in, in2, out); dangling_2nd>(std::ranges::merge, in, in2, out); dangling_both>(std::ranges::merge, in, in2, out); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp @@ -64,7 +64,7 @@ test(std::ranges::find_end, in, in2, eq, proj1, proj2); test(std::ranges::transform, in, in2, out, sum, proj1, proj2); test(std::ranges::transform, in, in2, out2, sum, proj1, proj2); - //test(std::ranges::partial_sort_copy, in, in2, output2.begin(), output2.end(), less, proj1, proj2); + test(std::ranges::partial_sort_copy, in, in2, less, proj1, proj2); test(std::ranges::merge, in, in2, out, less, proj1, proj2); test(std::ranges::merge, in, in2, out2, less, proj1, proj2); test(std::ranges::set_intersection, in, in2, out, less, proj1, proj2); @@ -75,6 +75,8 @@ test(std::ranges::set_symmetric_difference, in, in2, out2, less, proj1, proj2); test(std::ranges::set_union, in, in2, out, less, proj1, proj2); test(std::ranges::set_union, in, in2, out2, less, proj1, proj2); + //test(std::ranges::starts_with, in, in2, eq, proj1, proj2); + //test(std::ranges::ends_with, in, in2, eq, proj1, proj2); return true; } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp @@ -117,7 +117,7 @@ //test(std::ranges::replace_copy_if, in, out, unary_pred, x); //test(std::ranges::unique_copy, in, out, binary_pred); test(std::ranges::partition_copy, in, out, out2, unary_pred); - //test(std::ranges::partial_sort_copy, in, in2, binary_pred); + test(std::ranges::partial_sort_copy, in, in2, binary_pred); test(std::ranges::merge, in, in2, out, binary_pred); test(std::ranges::set_difference, in, in2, out, binary_pred); test(std::ranges::set_intersection, in, in2, out, binary_pred); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -142,7 +142,7 @@ // `sample` has no requirement that the given generator be invoked via `std::invoke`. //test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val); test(std::ranges::partition_copy, in, out, out2, &Foo::unary_pred, &Bar::val); - //test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val); + test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); test(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); test(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); test(std::ranges::set_intersection, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -138,7 +138,7 @@ test_mid(std::ranges::rotate_copy, in, mid, out); //test(std::ranges::unique_copy, in, out); test(std::ranges::partition_copy, in, out, out2, unary_pred); - //test_mid(std::ranges::partial_sort_copy, in, in2); + test(std::ranges::partial_sort_copy, in, in2); test(std::ranges::merge, in, in2, out); test(std::ranges::set_difference, in, in2, out); test(std::ranges::set_intersection, in, in2, out); diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -111,7 +111,7 @@ 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::partial_sort_copy, a, a)); 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));