diff --git a/libcxx/include/__algorithm/copy_backward.h b/libcxx/include/__algorithm/copy_backward.h --- a/libcxx/include/__algorithm/copy_backward.h +++ b/libcxx/include/__algorithm/copy_backward.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H #include <__algorithm/copy.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/unwrap_iter.h> #include <__config> #include <__iterator/iterator_traits.h> @@ -23,21 +24,22 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter2> __copy_backward_impl(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __ret = std::__copy(reverse_iterator<_Iter1>(__last), - reverse_iterator<_Sent1>(__first), + auto __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); + auto __ret = std::__copy(reverse_iterator<_Iter1>(__last_iter), + reverse_iterator<_Iter1>(__first), reverse_iterator<_Iter2>(__result)); return pair<_Iter1, _Iter2>(__ret.first.base(), __ret.second.base()); } -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) { - auto __ret = std::__copy_backward_impl(std::__unwrap_iter(__first), - std::__unwrap_iter(__last), - std::__unwrap_iter(__result)); + auto __ret = std::__copy_backward_impl<_AlgPolicy>(std::__unwrap_iter(__first), + std::__unwrap_iter(__last), + std::__unwrap_iter(__result)); return pair<_Iter1, _Iter2>(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); } @@ -45,7 +47,7 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator2 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { - return std::__copy_backward(__first, __last, __result).second; + return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/lower_bound.h> #include <__algorithm/min.h> #include <__algorithm/move.h> @@ -21,7 +22,6 @@ #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/reverse_iterator.h> -#include <__utility/swap.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -53,12 +53,14 @@ bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);} }; -template void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + for (; __first1 != __last1; ++__result) { if (__first2 == __last2) @@ -69,25 +71,27 @@ if (__comp(*__first2, *__first1)) { - *__result = _VSTD::move(*__first2); + *__result = _Ops::__iter_move(__first2); ++__first2; } else { - *__result = _VSTD::move(*__first1); + *__result = _Ops::__iter_move(__first1); ++__first1; } } // __first2 through __last2 are already in the right spot. } -template +template void __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, typename iterator_traits<_BidirectionalIterator>::difference_type __len2, typename iterator_traits<_BidirectionalIterator>::value_type* __buff) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; __destruct_n __d(0); unique_ptr __h2(__buff, __d); @@ -95,30 +99,32 @@ { value_type* __p = __buff; for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr(), (void) ++__i, (void) ++__p) - ::new ((void*)__p) value_type(_VSTD::move(*__i)); - _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp); + ::new ((void*)__p) value_type(_Ops::__iter_move(__i)); + std::__half_inplace_merge<_AlgPolicy, _Compare>(__buff, __p, __middle, __last, __first, __comp); } else { value_type* __p = __buff; for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr(), (void) ++__i, (void) ++__p) - ::new ((void*)__p) value_type(_VSTD::move(*__i)); + ::new ((void*)__p) value_type(_Ops::__iter_move(__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator _Rv; typedef __invert<_Compare> _Inverted; - _VSTD::__half_inplace_merge<_Inverted>(_Rv(__p), _Rv(__buff), + std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), _Inverted(__comp)); } } -template +template void __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, typename iterator_traits<_BidirectionalIterator>::difference_type __len2, typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; while (true) { @@ -126,7 +132,7 @@ if (__len2 == 0) return; if (__len1 <= __buff_size || __len2 <= __buff_size) - return _VSTD::__buffered_inplace_merge<_Compare> + return std::__buffered_inplace_merge<_AlgPolicy, _Compare> (__first, __middle, __last, __comp, __len1, __len2, __buff); // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 for (; true; ++__first, (void) --__len1) @@ -153,24 +159,24 @@ { // __len >= 1, __len2 >= 2 __len21 = __len2 / 2; __m2 = __middle; - _VSTD::advance(__m2, __len21); + _Ops::advance(__m2, __len21); __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp); - __len11 = _VSTD::distance(__first, __m1); + __len11 = _Ops::distance(__first, __m1); } else { if (__len1 == 1) { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 // It is known *__first > *__middle - swap(*__first, *__middle); + _Ops::iter_swap(__first, __middle); return; } // __len1 >= 2, __len2 >= 1 __len11 = __len1 / 2; __m1 = __first; - _VSTD::advance(__m1, __len11); + _Ops::advance(__m1, __len11); __m2 = std::lower_bound(__middle, __last, *__m1, __comp); - __len21 = _VSTD::distance(__middle, __m2); + __len21 = _Ops::distance(__middle, __m2); } difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) difference_type __len22 = __len2 - __len21; // distance(__m2, __last) @@ -181,7 +187,8 @@ // merge smaller range with recursive call and larger with tail recursion elimination if (__len11 + __len21 < __len12 + __len22) { - _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); + std::__inplace_merge<_AlgPolicy, _Compare>( + __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); // _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); __first = __middle; __middle = __m2; @@ -190,7 +197,8 @@ } else { - _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); + std::__inplace_merge<_AlgPolicy, _Compare>( + __middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); // _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); __last = __middle; __middle = __m1; @@ -217,7 +225,7 @@ _LIBCPP_SUPPRESS_DEPRECATED_POP unique_ptr __h(__buf.first); typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, + return _VSTD::__inplace_merge<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, __buf.first, __buf.second); } diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -10,6 +10,8 @@ #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H #include <__algorithm/iter_swap.h> +#include <__algorithm/min_element.h> +#include <__algorithm/ranges_min_element.h> #include <__config> #include <__iterator/advance.h> #include <__iterator/distance.h> @@ -29,6 +31,8 @@ template struct _IterOps; +template struct _Algs; + #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) struct _RangeAlgPolicy {}; @@ -41,6 +45,12 @@ static constexpr auto next = ranges::next; static constexpr auto __advance_to = ranges::advance; }; + +template <> +struct _Algs<_RangeAlgPolicy> { + static constexpr auto min_element = ranges::min_element; +}; + #endif struct _ClassicAlgPolicy {}; @@ -85,11 +95,25 @@ } template - _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void __advance_to(_Iter& __first, _Iter __last) { + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + void __advance_to(_Iter& __first, _Iter __last) { __first = __last; } }; + +template <> +struct _Algs<_ClassicAlgPolicy> { + + // min_element + template + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + _Iter min_element(_Iter __first, _Iter __last) { + return std::min_element(__first, __last); + } + +}; + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H 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 @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/sift_down.h> #include <__config> #include <__iterator/iterator_traits.h> @@ -22,7 +23,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { using _CompRef = typename __comp_ref_type<_Compare>::type; @@ -33,7 +34,7 @@ if (__n > 1) { // start from the first parent, there is no need to consider children for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { - std::__sift_down<_CompRef>(__first, __comp_ref, __n, __first + __start); + std::__sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __n, __first + __start); } } } @@ -41,7 +42,7 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - std::__make_heap(std::move(__first), std::move(__last), __comp); + std::__make_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); } template diff --git a/libcxx/include/__algorithm/nth_element.h b/libcxx/include/__algorithm/nth_element.h --- a/libcxx/include/__algorithm/nth_element.h +++ b/libcxx/include/__algorithm/nth_element.h @@ -11,13 +11,13 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/sort.h> #include <__config> #include <__debug> #include <__debug_utils/randomize_range.h> #include <__iterator/iterator_traits.h> #include <__utility/move.h> -#include <__utility/swap.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -41,10 +41,12 @@ } } -template +template _LIBCPP_CONSTEXPR_AFTER_CXX11 void __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + // _Compare is known to be a reference type typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; const difference_type __limit = 7; @@ -60,24 +62,24 @@ return; case 2: if (__comp(*--__last, *__first)) - swap(*__first, *__last); + _Ops::iter_swap(__first, __last); return; case 3: { _RandomAccessIterator __m = __first; - _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); + std::__sort3<_AlgPolicy, _Compare>(__first, ++__m, --__last, __comp); return; } } if (__len <= __limit) { - _VSTD::__selection_sort<_Compare>(__first, __last, __comp); + std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp); return; } // __len > __limit >= 3 _RandomAccessIterator __m = __first + __len/2; _RandomAccessIterator __lm1 = __last; - unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); + unsigned __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, --__lm1, __comp); // *__m is median // partition [__first, __m) < *__m and *__m <= [__m, __last) // (this inhibits tossing elements equivalent to __m around unnecessarily) @@ -90,7 +92,7 @@ { // *__first == *__m, *__first doesn't go in first part if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) { - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; } else { // *__first == *__m, *__m <= all other elements @@ -102,7 +104,7 @@ if (__i == __j) { return; // [__first, __last) all equivalent elements } else if (__comp(*__first, *__i)) { - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; ++__i; break; @@ -121,7 +123,7 @@ ; if (__i >= __j) break; - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; ++__i; } @@ -152,7 +154,7 @@ ; if (__i >= __j) break; - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it @@ -164,7 +166,7 @@ // [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { - swap(*__i, *__m); + _Ops::iter_swap(__i, __m); ++__n_swaps; } // [__first, __i) < *__i and *__i <= [__i+1, __last) @@ -220,7 +222,7 @@ } } -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare& __comp) { @@ -230,7 +232,7 @@ std::__debug_randomize_range(__first, __last); using _Comp_ref = typename __comp_ref_type<_Compare>::type; - std::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + std::__nth_element<_AlgPolicy, _Comp_ref>(__first, __nth, __last, __comp); std::__debug_randomize_range(__first, __nth); if (__nth != __last) { @@ -242,7 +244,7 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) { - std::__nth_element_impl(std::move(__first), std::move(__nth), std::move(__last), __comp); + std::__nth_element_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__nth), std::move(__last), __comp); } template 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 @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_heap.h> #include <__algorithm/sift_down.h> #include <__algorithm/sort_heap.h> @@ -18,7 +19,6 @@ #include <__debug> #include <__debug_utils/randomize_range.h> #include <__iterator/iterator_traits.h> -#include <__utility/swap.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -26,24 +26,24 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template _LIBCPP_CONSTEXPR_AFTER_CXX17 void __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) { if (__first == __middle) return; - _VSTD::__make_heap<_Compare>(__first, __middle, __comp); + std::__make_heap<_AlgPolicy, _Compare>(__first, __middle, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) { if (__comp(*__i, *__first)) { - swap(*__i, *__first); - _VSTD::__sift_down<_Compare>(__first, __comp, __len, __first); + _IterOps<_AlgPolicy>::iter_swap(__i, __first); + std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first); } } - _VSTD::__sort_heap<_Compare>(__first, __middle, __comp); + std::__sort_heap<_AlgPolicy, _Compare>(__first, __middle, __comp); } template @@ -54,7 +54,7 @@ { std::__debug_randomize_range(__first, __last); typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); + std::__partial_sort<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp); std::__debug_randomize_range(__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 @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_heap.h> #include <__algorithm/sift_down.h> #include <__algorithm/sort_heap.h> @@ -23,7 +24,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) @@ -33,15 +34,15 @@ { for (; __first != __last && __r != __result_last; ++__first, (void) ++__r) *__r = *__first; - _VSTD::__make_heap<_Compare>(__result_first, __r, __comp); + std::__make_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; for (; __first != __last; ++__first) if (__comp(*__first, *__result_first)) { *__result_first = *__first; - _VSTD::__sift_down<_Compare>(__result_first, __comp, __len, __result_first); + std::__sift_down<_AlgPolicy, _Compare>(__result_first, __comp, __len, __result_first); } - _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp); + std::__sort_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp); } return __r; } @@ -53,7 +54,8 @@ _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp); + return std::__partial_sort_copy<_ClassicAlgPolicy, _Comp_ref>( + __first, __last, __result_first, __result_last, __comp); } template 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 @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/push_heap.h> #include <__algorithm/sift_down.h> #include <__assert> @@ -24,7 +25,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len) { @@ -36,16 +37,16 @@ using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; if (__len > 1) { value_type __top = std::move(*__first); // create a hole at __first - _RandomAccessIterator __hole = std::__floyd_sift_down<_CompRef>(__first, __comp_ref, __len); + _RandomAccessIterator __hole = std::__floyd_sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __len); --__last; if (__hole == __last) { *__hole = std::move(__top); } else { - *__hole = std::move(*__last); + *__hole = _IterOps<_AlgPolicy>::__iter_move(__last); ++__hole; *__last = std::move(__top); - std::__sift_up<_CompRef>(__first, __hole, __comp_ref, __hole - __first); + std::__sift_up<_AlgPolicy, _CompRef>(__first, __hole, __comp_ref, __hole - __first); } } } @@ -54,7 +55,7 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first; - std::__pop_heap(std::move(__first), std::move(__last), __comp, __len); + std::__pop_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __len); } template 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 @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> @@ -21,7 +22,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len) { @@ -32,9 +33,9 @@ _RandomAccessIterator __ptr = __first + __len; if (__comp(*__ptr, *--__last)) { - value_type __t(std::move(*__last)); + value_type __t(_IterOps<_AlgPolicy>::__iter_move(__last)); do { - *__last = std::move(*__ptr); + *__last = _IterOps<_AlgPolicy>::__iter_move(__ptr); __last = __ptr; if (__len == 0) break; @@ -47,18 +48,18 @@ } } -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { using _CompRef = typename __comp_ref_type<_Compare>::type; typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first; - std::__sift_up<_CompRef>(std::move(__first), std::move(__last), __comp, __len); + std::__sift_up<_AlgPolicy, _CompRef>(std::move(__first), std::move(__last), __comp, __len); } template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - std::__push_heap(std::move(__first), std::move(__last), __comp); + std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); } template diff --git a/libcxx/include/__algorithm/ranges_copy_backward.h b/libcxx/include/__algorithm/ranges_copy_backward.h --- a/libcxx/include/__algorithm/ranges_copy_backward.h +++ b/libcxx/include/__algorithm/ranges_copy_backward.h @@ -11,6 +11,7 @@ #include <__algorithm/copy_backward.h> #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/concepts.h> #include <__iterator/reverse_iterator.h> @@ -39,7 +40,7 @@ requires indirectly_copyable<_InIter1, _InIter2> _LIBCPP_HIDE_FROM_ABI constexpr copy_backward_result<_InIter1, _InIter2> operator()(_InIter1 __first, _Sent1 __last, _InIter2 __result) const { - auto __ret = std::__copy_backward(std::move(__first), std::move(__last), std::move(__result)); + auto __ret = std::__copy_backward<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } @@ -47,9 +48,9 @@ requires indirectly_copyable, _Iter> _LIBCPP_HIDE_FROM_ABI constexpr copy_backward_result, _Iter> operator()(_Range&& __r, _Iter __result) const { - auto __ret = std::__copy_backward(ranges::begin(__r), - ranges::end(__r), - std::move(__result)); + auto __ret = std::__copy_backward<_RangeAlgPolicy>(ranges::begin(__r), + ranges::end(__r), + std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } }; diff --git a/libcxx/include/__algorithm/ranges_fill.h b/libcxx/include/__algorithm/ranges_fill.h --- a/libcxx/include/__algorithm/ranges_fill.h +++ b/libcxx/include/__algorithm/ranges_fill.h @@ -30,7 +30,7 @@ template _Iter, sentinel_for<_Iter> _Sent> _LIBCPP_HIDE_FROM_ABI constexpr _Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const { - if constexpr(random_access_iterator<_Iter>) { + if constexpr(random_access_iterator<_Iter> && sized_sentinel_for<_Sent, _Iter>) { return ranges::fill_n(__first, __last - __first, __value); } else { for (; __first != __last; ++__first) diff --git a/libcxx/include/__algorithm/ranges_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 @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H #define _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_heap.h> #include <__algorithm/make_projected.h> #include <__concepts/same_as.h> @@ -45,7 +46,7 @@ auto __last_iter = ranges::next(__first, __last); auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); - std::__make_heap(std::move(__first), __last_iter, __projected_comp); + std::__make_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; } diff --git a/libcxx/include/__algorithm/ranges_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 @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H #define _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/nth_element.h> #include <__config> @@ -44,7 +45,7 @@ auto __last_iter = ranges::next(__first, __last); auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); - std::__nth_element_impl(std::move(__first), std::move(__nth), __last_iter, __projected_comp); + std::__nth_element_impl<_RangeAlgPolicy>(std::move(__first), std::move(__nth), __last_iter, __projected_comp); return __last_iter; } diff --git a/libcxx/include/__algorithm/ranges_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 @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H #define _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/pop_heap.h> #include <__concepts/same_as.h> @@ -46,7 +47,7 @@ auto __len = __last_iter - __first; auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); - std::__pop_heap(std::move(__first), __last_iter, __projected_comp, __len); + std::__pop_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp, __len); return __last_iter; } diff --git a/libcxx/include/__algorithm/ranges_push_heap.h b/libcxx/include/__algorithm/ranges_push_heap.h --- a/libcxx/include/__algorithm/ranges_push_heap.h +++ b/libcxx/include/__algorithm/ranges_push_heap.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H #define _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/push_heap.h> #include <__concepts/same_as.h> @@ -45,7 +46,7 @@ auto __last_iter = ranges::next(__first, __last); auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); - std::__push_heap(std::move(__first), __last_iter, __projected_comp); + std::__push_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; } diff --git a/libcxx/include/__algorithm/ranges_sort.h b/libcxx/include/__algorithm/ranges_sort.h --- a/libcxx/include/__algorithm/ranges_sort.h +++ b/libcxx/include/__algorithm/ranges_sort.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H #define _LIBCPP___ALGORITHM_RANGES_SORT_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/sort.h> #include <__config> @@ -44,7 +45,7 @@ auto __last_iter = ranges::next(__first, __last); auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); - std::__sort_impl(std::move(__first), __last_iter, __projected_comp); + std::__sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; } diff --git a/libcxx/include/__algorithm/ranges_sort_heap.h b/libcxx/include/__algorithm/ranges_sort_heap.h --- a/libcxx/include/__algorithm/ranges_sort_heap.h +++ b/libcxx/include/__algorithm/ranges_sort_heap.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H #define _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/sort_heap.h> #include <__concepts/same_as.h> @@ -45,7 +46,7 @@ auto __last_iter = ranges::next(__first, __last); auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); - std::__sort_heap(std::move(__first), __last_iter, __projected_comp); + std::__sort_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; } diff --git a/libcxx/include/__algorithm/ranges_stable_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 @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H #define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/stable_sort.h> #include <__config> @@ -44,7 +45,7 @@ auto __last_iter = ranges::next(__first, __last); auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); - std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp); + std::__stable_sort_impl<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp); return __last_iter; } diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h --- a/libcxx/include/__algorithm/sift_down.h +++ b/libcxx/include/__algorithm/sift_down.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H #define _LIBCPP___ALGORITHM_SIFT_DOWN_H +#include <__algorithm/iterator_operations.h> #include <__assert> #include <__config> #include <__iterator/iterator_traits.h> @@ -20,12 +21,14 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template _LIBCPP_CONSTEXPR_AFTER_CXX11 void __sift_down(_RandomAccessIterator __first, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, _RandomAccessIterator __start) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // left-child of __start is at 2 * __start + 1 @@ -49,11 +52,11 @@ // we are, __start is larger than its largest child return; - value_type __top(_VSTD::move(*__start)); + value_type __top(_Ops::__iter_move(__start)); do { // we are not in heap-order, swap the parent with its largest child - *__start = _VSTD::move(*__child_i); + *__start = _Ops::__iter_move(__child_i); __start = __child_i; if ((__len - 2) / 2 < __child) @@ -74,7 +77,7 @@ *__start = _VSTD::move(__top); } -template +template _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator __floyd_sift_down(_RandomAccessIterator __first, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len) @@ -97,7 +100,7 @@ } // swap __hole with its largest child - *__hole = std::move(*__child_i); + *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i); __hole = __child_i; // if __hole is now a leaf, we're done diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/min_element.h> #include <__algorithm/partial_sort.h> #include <__algorithm/unwrap_iter.h> @@ -21,7 +22,6 @@ #include <__functional/operations.h> #include <__functional/ranges_operations.h> #include <__iterator/iterator_traits.h> -#include <__utility/swap.h> #include #include @@ -33,35 +33,37 @@ // stable, 2-3 compares, 0-2 swaps -template +template _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) { + using _Ops = _IterOps<_AlgPolicy>; + unsigned __r = 0; if (!__c(*__y, *__x)) // if x <= y { if (!__c(*__z, *__y)) // if y <= z return __r; // x <= y && y <= z // x <= y && y > z - swap(*__y, *__z); // x <= z && y < z + _Ops::iter_swap(__y, __z); // x <= z && y < z __r = 1; if (__c(*__y, *__x)) // if x > y { - swap(*__x, *__y); // x < y && y <= z + _Ops::iter_swap(__x, __y); // x < y && y <= z __r = 2; } return __r; // x <= y && y < z } if (__c(*__z, *__y)) // x > y, if y > z { - swap(*__x, *__z); // x < y && y < z + _Ops::iter_swap(__x, __z); // x < y && y < z __r = 1; return __r; } - swap(*__x, *__y); // x > y && y <= z + _Ops::iter_swap(__x, __y); // x > y && y <= z __r = 1; // x < y && x <= z if (__c(*__z, *__y)) // if y > z { - swap(*__y, *__z); // x <= y && y < z + _Ops::iter_swap(__y, __z); // x <= y && y < z __r = 2; } return __r; @@ -69,18 +71,20 @@ // stable, 3-6 compares, 0-5 swaps -template +template unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c) { - unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); + using _Ops = _IterOps<_AlgPolicy>; + + unsigned __r = std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); if (__c(*__x4, *__x3)) { - swap(*__x3, *__x4); + _Ops::iter_swap(__x3, __x4); ++__r; if (__c(*__x3, *__x2)) { - swap(*__x2, *__x3); + _Ops::iter_swap(__x2, __x3); ++__r; if (__c(*__x2, *__x1)) { - swap(*__x1, *__x2); + _Ops::iter_swap(__x1, __x2); ++__r; } } @@ -90,21 +94,23 @@ // stable, 4-10 compares, 0-9 swaps -template +template _LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { - unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); + using _Ops = _IterOps<_AlgPolicy>; + + unsigned __r = std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c); if (__c(*__x5, *__x4)) { - swap(*__x4, *__x5); + _Ops::iter_swap(__x4, __x5); ++__r; if (__c(*__x4, *__x3)) { - swap(*__x3, *__x4); + _Ops::iter_swap(__x3, __x4); ++__r; if (__c(*__x3, *__x2)) { - swap(*__x2, *__x3); + _Ops::iter_swap(__x2, __x3); ++__r; if (__c(*__x2, *__x1)) { - swap(*__x1, *__x2); + _Ops::iter_swap(__x1, __x2); ++__r; } } @@ -132,7 +138,8 @@ template ::value_type> using __use_branchless_sort = integral_constant::value && sizeof(_Tp) <= sizeof(void*) && - is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>; + is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value && + is_same()), _Tp>::value>; // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. template @@ -158,7 +165,7 @@ *__y = __r ? *__y : __tmp; } -template +template inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) { @@ -166,14 +173,14 @@ _VSTD::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c); } -template +template inline _LIBCPP_HIDE_FROM_ABI __enable_if_t::value, void> __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) { - _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); + std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c); } -template +template inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _Compare __c) { @@ -184,14 +191,14 @@ _VSTD::__cond_swap<_Compare>(__x2, __x3, __c); } -template +template inline _LIBCPP_HIDE_FROM_ABI __enable_if_t::value, void> __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _Compare __c) { - _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); + std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c); } -template +template inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { @@ -203,53 +210,57 @@ _VSTD::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c); } -template +template inline _LIBCPP_HIDE_FROM_ABI __enable_if_t::value, void> __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { - _VSTD::__sort5<_Compare>(__x1, __x2, __x3, __x4, __x5, __c); + std::__sort5<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __x5, __c); } // Assumes size > 0 -template +template _LIBCPP_CONSTEXPR_AFTER_CXX11 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { _BidirectionalIterator __lm1 = __last; for (--__lm1; __first != __lm1; ++__first) { - _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp); + _BidirectionalIterator __i = _Algs<_AlgPolicy>::min_element(__first, __last, __comp); if (__i != __first) - swap(*__first, *__i); + _IterOps<_AlgPolicy>::iter_swap(__first, __i); } } -template +template void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; if (__first != __last) { _BidirectionalIterator __i = __first; for (++__i; __i != __last; ++__i) { _BidirectionalIterator __j = __i; - value_type __t(_VSTD::move(*__j)); + value_type __t(_Ops::__iter_move(__j)); for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) - *__j = _VSTD::move(*__k); + *__j = _Ops::__iter_move(__k); *__j = _VSTD::move(__t); } } } -template +template void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first + difference_type(2); - _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); + std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp); for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { if (__comp(*__i, *__j)) { - value_type __t(_VSTD::move(*__i)); + value_type __t(_Ops::__iter_move(__i)); _RandomAccessIterator __k = __j; __j = __i; do { - *__j = _VSTD::move(*__k); + *__j = _Ops::__iter_move(__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); @@ -258,8 +269,10 @@ } } -template +template bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; switch (__last - __first) { case 0: @@ -267,32 +280,33 @@ return true; case 2: if (__comp(*--__last, *__first)) - swap(*__first, *__last); + _IterOps<_AlgPolicy>::iter_swap(__first, __last); return true; case 3: - _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); + std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp); return true; case 4: - _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), - --__last, __comp); + std::__sort4_maybe_branchless<_AlgPolicy, _Compare>( + __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp); return true; case 5: - _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), - __first + difference_type(3), --__last, __comp); + std::__sort5_maybe_branchless<_AlgPolicy, _Compare>( + __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3), + --__last, __comp); return true; } typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first + difference_type(2); - _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); + std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), __j, __comp); const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { if (__comp(*__i, *__j)) { - value_type __t(_VSTD::move(*__i)); + value_type __t(_Ops::__iter_move(__i)); _RandomAccessIterator __k = __j; __j = __i; do { - *__j = _VSTD::move(*__k); + *__j = _Ops::__iter_move(__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); @@ -304,27 +318,29 @@ return true; } -template +template void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; if (__first1 != __last1) { __destruct_n __d(0); unique_ptr __h(__first2, __d); value_type* __last2 = __first2; - ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__last2) value_type(_Ops::__iter_move(__first1)); __d.template __incr(); for (++__last2; ++__first1 != __last1; ++__last2) { value_type* __j2 = __last2; value_type* __i2 = __j2; if (__comp(*__first1, *--__i2)) { - ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); + ::new ((void*)__j2) value_type(_Ops::__iter_move(__i2)); __d.template __incr(); for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) - *__j2 = _VSTD::move(*__i2); - *__j2 = _VSTD::move(*__first1); + *__j2 = _Ops::__iter_move(__i2); + *__j2 = _Ops::__iter_move(__first1); } else { - ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__j2) value_type(_Ops::__iter_move(__first1)); __d.template __incr(); } } @@ -332,9 +348,11 @@ } } -template +template void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __depth) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; const difference_type __limit = @@ -348,28 +366,29 @@ return; case 2: if (__comp(*--__last, *__first)) - swap(*__first, *__last); + _IterOps<_AlgPolicy>::iter_swap(__first, __last); return; case 3: - _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); + std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp); return; case 4: - _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), - --__last, __comp); + std::__sort4_maybe_branchless<_AlgPolicy, _Compare>( + __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp); return; case 5: - _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), - __first + difference_type(3), --__last, __comp); + std::__sort5_maybe_branchless<_AlgPolicy, _Compare>( + __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3), + --__last, __comp); return; } if (__len <= __limit) { - _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); + std::__insertion_sort_3<_AlgPolicy, _Compare>(__first, __last, __comp); return; } // __len > 5 if (__depth == 0) { // Fallback to heap sort as Introsort suggests. - _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp); + std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp); return; } --__depth; @@ -383,11 +402,11 @@ __delta = __len / 2; __m += __delta; __delta /= 2; - __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp); + __n_swaps = std::__sort5<_AlgPolicy, _Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp); } else { __delta = __len / 2; __m += __delta; - __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); + __n_swaps = std::__sort3<_AlgPolicy, _Compare>(__first, __m, __lm1, __comp); } } // *__m is median @@ -414,7 +433,7 @@ if (__i == __j) return; // [__first, __last) all equivalent elements if (__comp(*__first, *__i)) { - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; ++__i; break; @@ -432,7 +451,7 @@ ; if (__i >= __j) break; - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; ++__i; } @@ -443,7 +462,7 @@ goto __restart; } if (__comp(*__j, *__m)) { - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; break; // found guard for downward moving __j, now use unguarded partition } @@ -465,7 +484,7 @@ ; if (__i > __j) break; - swap(*__i, *__j); + _Ops::iter_swap(__i, __j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it @@ -476,14 +495,14 @@ } // [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { - swap(*__i, *__m); + _Ops::iter_swap(__i, __m); ++__n_swaps; } // [__first, __i) < *__i and *__i <= [__i+1, __last) // If we were given a perfect partition, see if insertion sort is quick... if (__n_swaps == 0) { - bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); - if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + difference_type(1), __last, __comp)) { + bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp); + if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) { if (__fs) return; __last = __i; @@ -497,10 +516,10 @@ } // sort smaller range with recursive call and larger with tail recursion elimination if (__i - __first < __last - __i) { - _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth); + std::__introsort<_AlgPolicy, _Compare>(__first, __i, __comp, __depth); __first = ++__i; } else { - _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth); + std::__introsort<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp, __depth); __last = __i; } } @@ -525,73 +544,73 @@ return __log2; } -template +template void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __depth_limit = 2 * __log2i(__last - __first); - _VSTD::__introsort<_Compare>(__first, __last, __comp, __depth_limit); + std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit); } -template +template inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) { __less __comp; - _VSTD::__sort<__less&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); + std::__sort<_AlgPolicy, __less&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); } -extern template _LIBCPP_FUNC_VIS void __sort<__less&, char*>(char*, char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -extern template _LIBCPP_FUNC_VIS void __sort<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -extern template _LIBCPP_FUNC_VIS void __sort<__less&, signed char*>(signed char*, signed char*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, short*>(short*, short*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, int*>(int*, int*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned*>(unsigned*, unsigned*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, long*>(long*, long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, long long*>(long long*, long long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, float*>(float*, float*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, double*>(double*, double*, __less&); -extern template _LIBCPP_FUNC_VIS void __sort<__less&, long double*>(long double*, long double*, __less&); - -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, char*>(char*, char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); +extern template _LIBCPP_FUNC_VIS void __sort<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); + +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, signed char*>(signed char*, signed char*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, short*>(short*, short*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, int*>(int*, int*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned*>(unsigned*, unsigned*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, long*>(long*, long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, long long*>(long long*, long long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, float*>(float*, float*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, double*>(double*, double*, __less&); -extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less&, long double*>(long double*, long double*, __less&); - -extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); - -template +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); + +extern template _LIBCPP_FUNC_VIS unsigned __sort5<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); + +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { std::__debug_randomize_range(__first, __last); using _Comp_ref = typename __comp_ref_type<_Comp>::type; if (__libcpp_is_constant_evaluated()) { - std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); + std::__partial_sort<_AlgPolicy, _Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); } else { - std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp)); + std::__sort<_AlgPolicy, _Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp)); } } template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { - std::__sort_impl(std::move(__first), std::move(__last), __comp); + std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); } template 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 @@ -11,6 +11,7 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/pop_heap.h> #include <__config> #include <__iterator/iterator_traits.h> @@ -23,7 +24,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { using _CompRef = typename __comp_ref_type<_Compare>::type; @@ -31,13 +32,13 @@ using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) - std::__pop_heap<_CompRef>(__first, __last, __comp_ref, __n); + std::__pop_heap<_AlgPolicy, _CompRef>(__first, __last, __comp_ref, __n); } template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - std::__sort_heap(std::move(__first), std::move(__last), __comp); + std::__sort_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); } template diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -12,11 +12,11 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/inplace_merge.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/sort.h> #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> -#include <__utility/swap.h> #include #include @@ -26,12 +26,14 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template void __merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_InputIterator1>::value_type value_type; __destruct_n __d(0); unique_ptr __h(__result, __d); @@ -40,111 +42,115 @@ if (__first1 == __last1) { for (; __first2 != __last2; ++__first2, (void) ++__result, __d.template __incr()) - ::new ((void*)__result) value_type(_VSTD::move(*__first2)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first2)); __h.release(); return; } if (__first2 == __last2) { for (; __first1 != __last1; ++__first1, (void) ++__result, __d.template __incr()) - ::new ((void*)__result) value_type(_VSTD::move(*__first1)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first1)); __h.release(); return; } if (__comp(*__first2, *__first1)) { - ::new ((void*)__result) value_type(_VSTD::move(*__first2)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first2)); __d.template __incr(); ++__first2; } else { - ::new ((void*)__result) value_type(_VSTD::move(*__first1)); + ::new ((void*)__result) value_type(_Ops::__iter_move(__first1)); __d.template __incr(); ++__first1; } } } -template +template void __merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { + using _Ops = _IterOps<_AlgPolicy>; + for (; __first1 != __last1; ++__result) { if (__first2 == __last2) { for (; __first1 != __last1; ++__first1, (void) ++__result) - *__result = _VSTD::move(*__first1); + *__result = _Ops::__iter_move(__first1); return; } if (__comp(*__first2, *__first1)) { - *__result = _VSTD::move(*__first2); + *__result = _Ops::__iter_move(__first2); ++__first2; } else { - *__result = _VSTD::move(*__first1); + *__result = _Ops::__iter_move(__first1); ++__first1; } } for (; __first2 != __last2; ++__first2, (void) ++__result) - *__result = _VSTD::move(*__first2); + *__result = _Ops::__iter_move(__first2); } -template +template void __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size); -template +template void __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, typename iterator_traits<_RandomAccessIterator>::value_type* __first2) { + using _Ops = _IterOps<_AlgPolicy>; + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; switch (__len) { case 0: return; case 1: - ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); return; case 2: __destruct_n __d(0); unique_ptr __h2(__first2, __d); if (__comp(*--__last1, *__first1)) { - ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1)); __d.template __incr(); ++__first2; - ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); } else { - ::new ((void*)__first2) value_type(_VSTD::move(*__first1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__first1)); __d.template __incr(); ++__first2; - ::new ((void*)__first2) value_type(_VSTD::move(*__last1)); + ::new ((void*)__first2) value_type(_Ops::__iter_move(__last1)); } __h2.release(); return; } if (__len <= 8) { - _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); + std::__insertion_sort_move<_AlgPolicy, _Compare>(__first1, __last1, __first2, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; _RandomAccessIterator __m = __first1 + __l2; - _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); - _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); - _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp); + std::__stable_sort<_AlgPolicy, _Compare>(__first1, __m, __comp, __l2, __first2, __l2); + std::__stable_sort<_AlgPolicy, _Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); + std::__merge_move_construct<_AlgPolicy, _Compare>(__first1, __m, __m, __last1, __first2, __comp); } template @@ -153,7 +159,7 @@ static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value; }; -template +template void __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, @@ -168,12 +174,12 @@ return; case 2: if (__comp(*--__last, *__first)) - swap(*__first, *__last); + _IterOps<_AlgPolicy>::iter_swap(__first, __last); return; } if (__len <= static_cast(__stable_sort_switch::value)) { - _VSTD::__insertion_sort<_Compare>(__first, __last, __comp); + std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; @@ -182,11 +188,12 @@ { __destruct_n __d(0); unique_ptr __h2(__buff, __d); - _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); + std::__stable_sort_move<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff); __d.__set(__l2, (value_type*)nullptr); - _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); + std::__stable_sort_move<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); __d.__set(__len, (value_type*)nullptr); - _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); + std::__merge_move_assign<_AlgPolicy, _Compare>( + __buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp); // _VSTD::__merge<_Compare>(move_iterator(__buff), // move_iterator(__buff + __l2), // move_iterator<_RandomAccessIterator>(__buff + __l2), @@ -194,12 +201,12 @@ // __first, __comp); return; } - _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); - _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); - _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); + std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size); + std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); + std::__inplace_merge<_AlgPolicy, _Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); } -template +template inline _LIBCPP_HIDE_FROM_ABI void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; @@ -217,13 +224,13 @@ } using _Comp_ref = typename __comp_ref_type<_Compare>::type; - std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); + std::__stable_sort<_AlgPolicy, _Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); } template inline _LIBCPP_HIDE_FROM_ABI void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - std::__stable_sort_impl(std::move(__first), std::move(__last), __comp); + std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp); } template diff --git a/libcxx/src/algorithm.cpp b/libcxx/src/algorithm.cpp --- a/libcxx/src/algorithm.cpp +++ b/libcxx/src/algorithm.cpp @@ -6,48 +6,49 @@ // //===----------------------------------------------------------------------===// +#include <__algorithm/iterator_operations.h> #include _LIBCPP_BEGIN_NAMESPACE_STD // TODO(varconst): this currently doesn't benefit `ranges::sort` because it uses `ranges::less` instead of `__less`. -template void __sort<__less&, char*>(char*, char*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -template void __sort<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -template void __sort<__less&, signed char*>(signed char*, signed char*, __less&); -template void __sort<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -template void __sort<__less&, short*>(short*, short*, __less&); -template void __sort<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -template void __sort<__less&, int*>(int*, int*, __less&); -template void __sort<__less&, unsigned*>(unsigned*, unsigned*, __less&); -template void __sort<__less&, long*>(long*, long*, __less&); -template void __sort<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -template void __sort<__less&, long long*>(long long*, long long*, __less&); -template void __sort<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -template void __sort<__less&, float*>(float*, float*, __less&); -template void __sort<__less&, double*>(double*, double*, __less&); -template void __sort<__less&, long double*>(long double*, long double*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); +template void __sort<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); -template bool __insertion_sort_incomplete<__less&, char*>(char*, char*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, char*>(char*, char*, __less&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -template bool __insertion_sort_incomplete<__less&, wchar_t*>(wchar_t*, wchar_t*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, wchar_t*>(wchar_t*, wchar_t*, __less&); #endif -template bool __insertion_sort_incomplete<__less&, signed char*>(signed char*, signed char*, __less&); -template bool __insertion_sort_incomplete<__less&, unsigned char*>(unsigned char*, unsigned char*, __less&); -template bool __insertion_sort_incomplete<__less&, short*>(short*, short*, __less&); -template bool __insertion_sort_incomplete<__less&, unsigned short*>(unsigned short*, unsigned short*, __less&); -template bool __insertion_sort_incomplete<__less&, int*>(int*, int*, __less&); -template bool __insertion_sort_incomplete<__less&, unsigned*>(unsigned*, unsigned*, __less&); -template bool __insertion_sort_incomplete<__less&, long*>(long*, long*, __less&); -template bool __insertion_sort_incomplete<__less&, unsigned long*>(unsigned long*, unsigned long*, __less&); -template bool __insertion_sort_incomplete<__less&, long long*>(long long*, long long*, __less&); -template bool __insertion_sort_incomplete<__less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); -template bool __insertion_sort_incomplete<__less&, float*>(float*, float*, __less&); -template bool __insertion_sort_incomplete<__less&, double*>(double*, double*, __less&); -template bool __insertion_sort_incomplete<__less&, long double*>(long double*, long double*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, signed char*>(signed char*, signed char*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned char*>(unsigned char*, unsigned char*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, short*>(short*, short*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned short*>(unsigned short*, unsigned short*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, int*>(int*, int*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned*>(unsigned*, unsigned*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long*>(long*, long*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long*>(unsigned long*, unsigned long*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long long*>(long long*, long long*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, unsigned long long*>(unsigned long long*, unsigned long long*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, float*>(float*, float*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, double*>(double*, double*, __less&); +template bool __insertion_sort_incomplete<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, __less&); -template unsigned __sort5<__less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); +template unsigned __sort5<_ClassicAlgPolicy, __less&, long double*>(long double*, long double*, long double*, long double*, long double*, __less&); _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.compile.pass.cpp @@ -0,0 +1,177 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// +// +// Range algorithms should return `std::ranges::dangling` when given a dangling range. + +#include + +#include +#include +#include +#include +#include + +#include "test_iterators.h" + +struct NonBorrowedRange { + using Iter = int*; + using Sent = sentinel_wrapper; + + int* data_; + size_t size_; + + template + constexpr explicit NonBorrowedRange(std::array arr) : NonBorrowedRange{arr.data(), arr.size()} {} + constexpr NonBorrowedRange(int* d, size_t s) : data_{d}, size_{s} {} + + constexpr Iter begin() const { return data_; }; + constexpr Sent end() const { return Sent{data_ + size_}; }; +}; + +using R = NonBorrowedRange; + +// (dangling_in, ...) +template +void dangling_1st(Func&& func, Input& in, Args&& ...args) { + using ResultT = decltype(func(R(in), std::forward(args)...)); + static_assert(std::same_as); +} + +// (in, dangling_in, ...) +template +void dangling_2nd(Func&& func, Input& in1, Input& in2, Args&& ...args) { + using ResultT = decltype(func(in1, R(in2), std::forward(args)...)); + static_assert(std::same_as); +} + +void test_all() { + using std::ranges::dangling; + + using std::ranges::binary_transform_result; + using std::ranges::copy_result; + using std::ranges::copy_backward_result; + using std::ranges::copy_if_result; + using std::ranges::for_each_result; + using std::ranges::merge_result; + using std::ranges::minmax_result; + 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::partition_copy_result; + //using std::ranges::remove_copy_result; + //using std::ranges::remove_copy_if_result; + using std::ranges::reverse_copy_result; + using std::ranges::rotate_copy_result; + using std::ranges::set_difference_result; + using std::ranges::set_intersection_result; + //using std::ranges::set_symmetric_difference_result; + //using std::ranges::set_union_result; + using std::ranges::swap_ranges_result; + using std::ranges::unary_transform_result; + //using std::ranges::unique_copy_result; + + auto unary_pred = [](int i) { return i > 0; }; + auto binary_pred = [](int i, int j) { return i < j; }; + //auto gen = [] { return 42; }; + //std::mt19937 rand_gen; + + std::array in = {1, 2, 3}; + std::array in2 = {4, 5, 6}; + + auto mid = in.begin() + 1; + + std::array output = {7, 8, 9}; + auto out = output.begin(); + //auto out2 = output.begin() + 1; + + int x = 2; + size_t count = 1; + + dangling_1st(std::ranges::find, in, x); + dangling_1st(std::ranges::find_if, in, unary_pred); + dangling_1st(std::ranges::find_if_not, in, unary_pred); + dangling_1st(std::ranges::find_first_of, in, in2); + dangling_1st(std::ranges::adjacent_find, in); + dangling_1st>(std::ranges::mismatch, in, in2); + dangling_2nd>(std::ranges::mismatch, in, in2); + //dangling_1st(std::ranges::partition_point, in, unary_pred); + dangling_1st(std::ranges::lower_bound, in, x); + dangling_1st(std::ranges::upper_bound, in, x); + //dangling_1st(std::ranges::equal_range, in, x); + dangling_1st(std::ranges::min_element, in); + dangling_1st(std::ranges::max_element, in); + dangling_1st>(std::ranges::minmax_element, in); + dangling_1st(std::ranges::search, in, in2); + dangling_1st(std::ranges::search_n, in, count, x); + dangling_1st(std::ranges::find_end, in, in2); + dangling_1st(std::ranges::is_sorted_until, in); + //dangling_1st(std::ranges::is_heap_until, in); + dangling_1st>(std::ranges::for_each, in, unary_pred); + dangling_1st>(std::ranges::copy, in, out); + dangling_1st>(std::ranges::copy_backward, in, out); + dangling_1st>(std::ranges::copy_if, in, out, unary_pred); + dangling_1st>(std::ranges::move, in, out); + dangling_1st>(std::ranges::move_backward, in, out); + dangling_1st(std::ranges::fill, in, x); + { // transform + std::array out_transform = {false, true, true}; + dangling_1st>(std::ranges::transform, in, out_transform.begin(), unary_pred); + dangling_1st>( + std::ranges::transform, in, in2, out_transform.begin(), binary_pred); + dangling_2nd>( + std::ranges::transform, in, in2, out_transform.begin(), binary_pred); + } + //dangling_1st(std::ranges::generate, in, gen); + //dangling_1st>(std::ranges::remove_copy, in, out, x); + //dangling_1st>(std::ranges::remove_copy_if, in, out, unary_pred); + dangling_1st(std::ranges::replace, in, x, x); + dangling_1st(std::ranges::replace_if, in, std::identity{}, x); + //dangling_1st(std::ranges::replace_copy, in, out, x, x); + //dangling_1st(std::ranges::replace_copy_if, in, out, x, x); + dangling_1st>(std::ranges::swap_ranges, in, in2); + dangling_2nd>(std::ranges::swap_ranges, in, in2); + dangling_1st>(std::ranges::reverse_copy, in, out); + 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_1st>(std::ranges::merge, in, in2, out); + dangling_2nd>(std::ranges::merge, in, in2, out); + dangling_1st>(std::ranges::set_difference, in, in2, out); + dangling_1st>(std::ranges::set_intersection, in, in2, out); + dangling_2nd>(std::ranges::set_intersection, in, in2, out); + //dangling_1st>(std::ranges::set_symmetric_difference, in, in2, out); + //dangling_1st>(std::ranges::set_union, in, in2, out); + //dangling_2nd>(std::ranges::set_union, in, in2, out); + dangling_1st(std::ranges::remove, in, x); + dangling_1st(std::ranges::remove_if, in, unary_pred); + //dangling_1st(std::ranges::reverse, in); + //dangling_1st(std::ranges::rotate, in, mid); + //dangling_1st(std::ranges::shuffle, in, rand_gen); + //dangling_1st(std::ranges::unique, in); + //dangling_1st(std::ranges::partition, in, binary_pred); + //dangling_1st(std::ranges::stable_partition, in, binary_pred); + dangling_1st(std::ranges::sort, in); + dangling_1st(std::ranges::stable_sort, in); + //dangling_1st(std::ranges::partial_sort, in, mid); + dangling_1st(std::ranges::nth_element, in, mid); + //dangling_1st(std::ranges::inplace_merge, in, mid); + dangling_1st(std::ranges::make_heap, in); + dangling_1st(std::ranges::push_heap, in); + dangling_1st(std::ranges::pop_heap, in); + dangling_1st(std::ranges::sort_heap, in); + //dangling_1st(std::ranges::prev_permutation, in); + //dangling_1st(std::ranges::next_permutation, in); +} diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp @@ -32,49 +32,20 @@ static_assert(!std::same_as); static_assert(std::convertible_to); -// There are only a few typical signatures shared by most algorithms -- this set of helpers invokes both the -// (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid. - -// (in, pred) -template -void in_pred(Func&& func, Input& in, Pred& pred) { - func(in.begin(), in.end(), pred); - func(in, pred); -} - -// (in, val, pred) -template -void in_val_pred(Func&& func, Input& in, T& value, Pred& pred) { - func(in.begin(), in.end(), value, pred); - func(in, value, pred); -} - -// (in, out, pred) -template -void in_out_pred(Func&& func, Input& in, Output& out, Pred& pred) { - func(in.begin(), in.end(), out, pred); - func(in, out, pred); -} - -// (in1, in2, pred) -template -void in2_pred(Func&& func, Input& in1, Input& in2, Pred& pred) { - func(in1.begin(), in1.end(), in2.begin(), in2.end(), pred); - func(in1, in2, pred); -} +// Invokes both the (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid. -// (in1, in2, out, pred) -template -void in2_out_pred(Func&& func, Input& in1, Input& in2, Output& out, Pred& pred) { - func(in1.begin(), in1.end(), in2.begin(), in2.end(), out, pred); - func(in1, in2, out, pred); +// (in, ...) +template +void test(Func&& func, Input& in, Args&& ...args) { + func(in.begin(), in.end(), std::forward(args)...); + func(in, std::forward(args)...); } -// (in, mid, pred) -template -void in_mid_pred(Func&& func, Input& in, std::ranges::iterator_t& mid, Pred& pred) { - func(in.begin(), mid, in.end(), pred); - func(in, mid, pred); +// (in1, in2, ...) +template +void test(Func&& func, Input& in1, Input& in2, Args&& ...args) { + func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward(args)...); + func(in1, in2, std::forward(args)...); } void test_all() { @@ -87,23 +58,23 @@ //auto out2 = output.begin() + 1; int x = 2; - //int count = 1; - - in_pred(std::ranges::any_of, in, unary_pred); - in_pred(std::ranges::all_of, in, unary_pred); - in_pred(std::ranges::none_of, in, unary_pred); - in_pred(std::ranges::find_if, in, unary_pred); - in_pred(std::ranges::find_if_not, in, unary_pred); - in2_pred(std::ranges::find_first_of, in, in2, binary_pred); - in_pred(std::ranges::adjacent_find, in, binary_pred); - in2_pred(std::ranges::mismatch, in, in2, binary_pred); - in2_pred(std::ranges::equal, in, in2, binary_pred); - in2_pred(std::ranges::lexicographical_compare, in, in2, binary_pred); - //in_pred(std::ranges::partition_point, unary_pred); - in_val_pred(std::ranges::lower_bound, in, x, binary_pred); - in_val_pred(std::ranges::upper_bound, in, x, binary_pred); - //in_val_pred(std::ranges::equal_range, in, x, binary_pred); - in_val_pred(std::ranges::binary_search, in, x, binary_pred); + int count = 1; + + test(std::ranges::any_of, in, unary_pred); + test(std::ranges::all_of, in, unary_pred); + test(std::ranges::none_of, in, unary_pred); + test(std::ranges::find_if, in, unary_pred); + test(std::ranges::find_if_not, in, unary_pred); + test(std::ranges::find_first_of, in, in2, binary_pred); + test(std::ranges::adjacent_find, in, binary_pred); + test(std::ranges::mismatch, in, in2, binary_pred); + test(std::ranges::equal, in, in2, binary_pred); + test(std::ranges::lexicographical_compare, in, in2, binary_pred); + //test(std::ranges::partition_point, unary_pred); + test(std::ranges::lower_bound, in, x, binary_pred); + test(std::ranges::upper_bound, in, x, binary_pred); + //test(std::ranges::equal_range, in, x, binary_pred); + test(std::ranges::binary_search, in, x, binary_pred); // min std::ranges::min(1, 2, binary_pred); @@ -118,55 +89,48 @@ std::ranges::minmax(std::initializer_list{1, 2}, binary_pred); std::ranges::minmax(in, binary_pred); - in_pred(std::ranges::min_element, in, binary_pred); - in_pred(std::ranges::max_element, in, binary_pred); - in_pred(std::ranges::minmax_element, in, binary_pred); - in_pred(std::ranges::count_if, in, unary_pred); - //in2_pred(std::ranges::search, in, in2, binary_pred); - //std::ranges::search_n(in.begin(), in.end(), count, x, binary_pred); - //std::ranges::search_n(in, count, x, binary_pred); - //in2_pred(std::ranges::find_end, in, in2, binary_pred); - in_pred(std::ranges::is_partitioned, in, unary_pred); - in_pred(std::ranges::is_sorted, in, binary_pred); - in_pred(std::ranges::is_sorted_until, in, binary_pred); - //in2_pred(std::ranges::includes, in, in2, binary_pred); - //in_pred(std::ranges::is_heap, in, binary_pred); - //in_pred(std::ranges::is_heap_until, in, binary_pred); + test(std::ranges::min_element, in, binary_pred); + test(std::ranges::max_element, in, binary_pred); + test(std::ranges::minmax_element, in, binary_pred); + test(std::ranges::count_if, in, unary_pred); + test(std::ranges::search, in, in2, binary_pred); + test(std::ranges::search_n, in, count, x, binary_pred); + test(std::ranges::find_end, in, in2, binary_pred); + test(std::ranges::is_partitioned, in, unary_pred); + test(std::ranges::is_sorted, in, binary_pred); + test(std::ranges::is_sorted_until, in, binary_pred); + //test(std::ranges::includes, in, in2, binary_pred); + //test(std::ranges::is_heap, in, binary_pred); + //test(std::ranges::is_heap_until, in, binary_pred); //std::ranges::clamp(2, 1, 3, binary_pred); - //in2_pred(std::ranges::is_permutation, in, in2, binary_pred); - in_out_pred(std::ranges::copy_if, in, out, unary_pred); - //in_out_pred(std::ranges::remove_copy_if, in, out, unary_pred); - - // replace_if - //std::ranges::replace_if(in.begin(), in.end(), unary_pred, x); - //std::ranges::replace_if(in, unary_pred, x); - // replace_copy_if - //std::ranges::replace_copy_if(in.begin(), in.end(), out, unary_pred, x); - //std::ranges::replace_copy_if(in, out, unary_pred, x); - - //in_out_pred(std::ranges::unique_copy, in, out, binary_pred); - // partition_copy - //std::ranges::partition_copy(in.begin(), in.end(), out, out2, unary_pred); - //std::ranges::partition_copy(in, out, out2, unary_pred); - //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::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); + //test(std::ranges::is_permutation, in, in2, binary_pred); + test(std::ranges::copy_if, in, out, unary_pred); + //test(std::ranges::remove_copy_if, in, out, unary_pred); + + //test(std::ranges::replace_if, in, unary_pred, x); + //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::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); + //test(std::ranges::set_symmetric_difference, in, in2, out, binary_pred); + //test(std::ranges::set_union, in, in2, out, binary_pred); + test(std::ranges::remove_if, in, unary_pred); + //test(std::ranges::unique, in, binary_pred); + //test(std::ranges::partition, in, binary_pred); + //test(std::ranges::stable_partition, in, binary_pred); + test(std::ranges::sort, in, binary_pred); + test(std::ranges::stable_sort, in, binary_pred); + //test(std::ranges::partial_sort, in, mid, binary_pred); + test(std::ranges::nth_element, in, mid, binary_pred); + //test(std::ranges::inplace_merge, in, mid, binary_pred); + test(std::ranges::make_heap, in, binary_pred); + test(std::ranges::push_heap, in, binary_pred); + test(std::ranges::pop_heap, in, binary_pred); + test(std::ranges::sort_heap, in, binary_pred); + //test(std::ranges::prev_permutation, in, binary_pred); + //test(std::ranges::next_permutation, in, binary_pred); } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp @@ -33,56 +33,20 @@ Bar create() const { return Bar(); } }; -// There are only a few typical signatures shared by most algorithms -- this set of helpers invokes both the -// (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid. - -// (in, val) -template -void in_val(Func&& func, Input& in, const T& val, Proj&& proj) { - func(in.begin(), in.end(), val, proj); - func(in, val, proj); -} - -// (in, pred) -template -void in_pred(Func&& func, Input& in, Pred&& pred, Proj&& proj) { - func(in.begin(), in.end(), pred, proj); - func(in, pred, proj); -} - -// (in, val, pred) -template -void in_val_pred(Func&& func, Input& in, const T& val, Pred&& pred, Proj&& proj) { - func(in.begin(), in.end(), val, pred, proj); - func(in, val, pred, proj); -} - -// (in1, in2, pred) -- two projections. -template -void in2_pred(Func&& func, Input& in1, Input& in2, Pred&& pred, Proj1&& proj1, Proj2&& proj2) { - func(in1.begin(), in1.end(), in2.begin(), in2.end(), pred, proj1, proj2); - func(in1, in2, pred, proj1, proj2); -} - -// (in, out, pred) -template -void in_out_pred(Func&& func, Input& in, Output out, Pred&& pred, Proj&& proj) { - func(in.begin(), in.end(), out, pred, proj); - func(in, out, pred, proj); -} +// Invokes both the (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid. -// (in, mid, pred) -template -void in_mid_pred(Func&& func, Input& in, Iter mid, Pred&& pred, Proj&& proj) { - func(in.begin(), mid, in.end(), pred, proj); - func(in, mid, pred, proj); +// (in, ...) +template +void test(Func&& func, Input& in, Args&& ...args) { + func(in.begin(), in.end(), std::forward(args)...); + func(in, std::forward(args)...); } -// (in1, in2, out, pred) -- two projections. -template -void in2_out_pred(Func&& func, Input& in1, Input& in2, Output out, Pred&& pred, Proj1&& proj1, Proj2&& proj2) { - func(in1.begin(), in1.end(), in2.begin(), in2.end(), out, pred, proj1, proj2); - func(in1, in2, out, pred, proj1, proj2); +// (in1, in2, ...) +template +void test(Func&& func, Input& in1, Input& in2, Args&& ...args) { + func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward(args)...); + func(in1, in2, std::forward(args)...); } void test_all() { @@ -101,22 +65,22 @@ Foo x{2}; size_t count = 1; - in_pred(std::ranges::any_of, in, &Foo::unary_pred, &Bar::val); - in_pred(std::ranges::all_of, in, &Foo::unary_pred, &Bar::val); - in_pred(std::ranges::none_of, in, &Foo::unary_pred, &Bar::val); - in_val(std::ranges::find, in, x, &Bar::val); - in_pred(std::ranges::find_if, in, &Foo::unary_pred, &Bar::val); - in_pred(std::ranges::find_if_not, in, &Foo::unary_pred, &Bar::val); - in2_pred(std::ranges::find_first_of, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - in_pred(std::ranges::adjacent_find, in, &Foo::binary_pred, &Bar::val); - in2_pred(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - in2_pred(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - in2_pred(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - //in_pred(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val); - in_val_pred(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val); - in_val_pred(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val); - //in_val_pred(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val); - in_val_pred(std::ranges::binary_search, in, x, &Foo::binary_pred, &Bar::val); + test(std::ranges::any_of, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::all_of, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::none_of, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::find, in, x, &Bar::val); + test(std::ranges::find_if, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::find_if_not, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::find_first_of, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::adjacent_find, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + //test(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val); + test(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val); + //test(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val); + test(std::ranges::binary_search, in, x, &Foo::binary_pred, &Bar::val); // min std::ranges::min(a, b, &Foo::binary_pred, &Bar::val); @@ -131,87 +95,70 @@ std::ranges::minmax(std::initializer_list{a, b}, &Foo::binary_pred, &Bar::val); std::ranges::minmax(in, &Foo::binary_pred, &Bar::val); - in_pred(std::ranges::min_element, in, &Foo::binary_pred, &Bar::val); - in_pred(std::ranges::max_element, in, &Foo::binary_pred, &Bar::val); - in_pred(std::ranges::minmax_element, in, &Foo::binary_pred, &Bar::val); - in_val(std::ranges::count, in, x, &Bar::val); - in_pred(std::ranges::count_if, in, &Foo::unary_pred, &Bar::val); - //in2_pred(std::ranges::search, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - // search_n - //std::ranges::search_n(in.begin(), in.end(), count, x, &Foo::binary_pred, &Bar::val); - //std::ranges::search_n(in, count, x, &Foo::binary_pred, &Bar::val); - //in2_pred(std::ranges::find_end, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - in_pred(std::ranges::is_partitioned, in, &Foo::unary_pred, &Bar::val); - in_pred(std::ranges::is_sorted, in, &Foo::binary_pred, &Bar::val); - in_pred(std::ranges::is_sorted_until, in, &Foo::binary_pred, &Bar::val); - //in2_pred(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - //in_pred(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val); - //in_pred(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::min_element, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::max_element, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::minmax_element, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::count, in, x, &Bar::val); + test(std::ranges::count_if, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::search, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::search_n, in, count, x, &Foo::binary_pred, &Bar::val); + test(std::ranges::find_end, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::is_partitioned, in, &Foo::unary_pred, &Bar::val); + test(std::ranges::is_sorted, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::is_sorted_until, in, &Foo::binary_pred, &Bar::val); + //test(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + //test(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val); + //test(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val); //std::ranges::clamp(b, a, c, &Foo::binary_pred); - //in2_pred(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - in_pred(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val); + //test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val); std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val); // `copy`, `copy_n` and `copy_backward` have neither a projection nor a predicate. - in_out_pred(std::ranges::copy_if, in, out, &Foo::unary_pred, &Bar::val); + test(std::ranges::copy_if, in, out, &Foo::unary_pred, &Bar::val); // `move` and `move_backward` have neither a projection nor a predicate. // `fill` and `fill_n` have neither a projection nor a predicate. { std::array out_transform = {false, true, true}; - in_out_pred(std::ranges::transform, in, out_transform.begin(), &Foo::unary_pred, &Bar::val); + test(std::ranges::transform, in, out_transform.begin(), &Foo::unary_pred, &Bar::val); } - // generate - //std::ranges::generate(in.begin(), in.end(), &Bar::create); - //std::ranges::generate(in, &Bar::create); - // generate_n - //std::ranges::generate(in.begin(), count, &Bar::create); - // remove_copy - //std::ranges::remove_copy(in.begin(), in.end(), out, x, &Bar::val); - //std::ranges::remove_copy(in, out, x, &Bar::val); - //in_out_pred(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val); + //test(std::ranges::generate, in, &Bar::create); + //std::ranges::generate_n(in.begin(), count, &Bar::create); + //test(std::ranges::remove_copy, in, out, x, &Bar::val); + //test(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val); // `replace*` algorithms only use the projection to compare the elements, not to write them. - // replace - std::ranges::replace(in.begin(), in.end(), x, a, &Bar::val); - std::ranges::replace(in, x, a, &Bar::val); - // replace_if - std::ranges::replace_if(in.begin(), in.end(), &Foo::unary_pred, a, &Bar::val); - std::ranges::replace_if(in, &Foo::unary_pred, a, &Bar::val); - // replace_copy - //std::ranges::replace_copy(in.begin(), in.end(), out, x, a, &Bar::val); - //std::ranges::replace_copy(in, out, x, a, &Bar::val); - // replace_copy_if - //std::ranges::replace_copy_if(in.begin(), in.end(), out, pred, a, &Bar::val); - //std::ranges::replace_copy_if(in, out, pred, a, &Bar::val); + test(std::ranges::replace, in, x, a, &Bar::val); + test(std::ranges::replace_if, in, &Foo::unary_pred, a, &Bar::val); + //test(std::ranges::replace_copy, in, out, x, a, &Bar::val); + //test(std::ranges::replace_copy_if, in, out, pred, a, &Bar::val); // `swap_ranges` has neither a projection nor a predicate. // `reverse_copy` has neither a projection nor a predicate. // `rotate_copy` has neither a projection nor a predicate. // `sample` has no requirement that the given generator be invoked via `std::invoke`. - //in_out_pred(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val); - // partition_copy - //std::ranges::partition_copy(in.begin(), in.end(), out, out2, &Foo::unary_pred, &Bar::val); - //std::ranges::partition_copy(in, out, out2, &Foo::unary_pred, &Bar::val); - //in2_pred(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val); - in2_out_pred(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); - in2_out_pred(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); - in2_out_pred(std::ranges::set_intersection, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); - 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); + //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::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); + //test(std::ranges::set_symmetric_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); + //test(std::ranges::set_union, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); + test(std::ranges::remove, in, x, &Bar::val); + test(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::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); + //test(std::ranges::unique, in, &Foo::binary_pred, &Bar::val); + //test(std::ranges::partition, in, &Foo::binary_pred, &Bar::val); + //test(std::ranges::stable_partition, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::sort, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val); + //test(std::ranges::partial_sort, in, mid, binary_pred); + test(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val); + //test(std::ranges::inplace_merge, in, mid, binary_pred); + test(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val); + //test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val); + //test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val); } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.compile.pass.cpp @@ -0,0 +1,155 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// +// +// Range algorithms should work with proxy iterators. For example, the implementations should use `iter_swap` (which is +// a customization point) rather than plain `swap` (which might not work with certain valid iterators). + +#include + +#include +#include +#include +#include +#include +#include +#include + +#include "test_iterators.h" + +template +void test(Func&& func, Input& in, Args&& ...args) { + func(in.begin(), in.end(), std::forward(args)...); + func(in, std::forward(args)...); +} + +template +void test(Func&& func, Input& in1, Input& in2, Args&& ...args) { + func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward(args)...); + func(in1, in2, std::forward(args)...); +} + +template +void test_mid(Func&& func, Input& in, std::ranges::iterator_t mid, Args&& ...args) { + func(in.begin(), mid, in.end(), std::forward(args)...); + func(in, mid, std::forward(args)...); +} + +void test_all() { + std::array input = {1, 2, 3}; + ProxyRange in{input}; + std::array input2 = {4, 5, 6}; + ProxyRange in2{input2}; + + auto mid = in.begin() + 1; + + std::array output = {4, 5, 6}; + ProxyIterator out{output.begin()}; + std::array output_bool = {true, false, true}; + ProxyIterator out_bool{output_bool.begin()}; + //auto out2 = output.begin() + 1; + + int num = 2; + Proxy x{num}; + int count = 1; + + auto unary_pred = [](const Proxy& x) { return x.getData() > 0; }; + auto binary_pred = [](const Proxy& lhs, const Proxy& rhs) { return lhs.getData() == rhs.getData(); }; + auto binary_func = [](const Proxy& lhs, const Proxy&) -> Proxy { return lhs.getData(); }; + //auto gen = [] { return Proxy(42); }; + //std::mt19937 rand_gen; + + test(std::ranges::any_of, in, unary_pred); + test(std::ranges::all_of, in, unary_pred); + test(std::ranges::none_of, in, unary_pred); + test(std::ranges::find, in, x); + test(std::ranges::find_if, in, unary_pred); + test(std::ranges::find_if_not, in, unary_pred); + test(std::ranges::find_first_of, in, in2); + test(std::ranges::adjacent_find, in); + test(std::ranges::mismatch, in, in2); + test(std::ranges::equal, in, in2); + test(std::ranges::lexicographical_compare, in, in2); + //test(std::ranges::partition_point, unary_pred); + test(std::ranges::lower_bound, in, x); + test(std::ranges::upper_bound, in, x); + //test(std::ranges::equal_range, in, x); + test(std::ranges::binary_search, in, x); + + test(std::ranges::min_element, in); + test(std::ranges::max_element, in); + test(std::ranges::minmax_element, in); + test(std::ranges::count, in, x); + test(std::ranges::count_if, in, unary_pred); + test(std::ranges::search, in, in2); + test(std::ranges::search_n, in, count, x); + test(std::ranges::find_end, in, in2); + test(std::ranges::is_partitioned, in, unary_pred); + test(std::ranges::is_sorted, in); + test(std::ranges::is_sorted_until, in); + //test(std::ranges::includes, in, in2); + //test(std::ranges::is_heap, in); + //test(std::ranges::is_heap_until, in); + //test(std::ranges::is_permutation, in, in2); + test(std::ranges::for_each, in, std::identity{}); + std::ranges::for_each_n(in.begin(), count, std::identity{}); + test(std::ranges::copy, in, out); + std::ranges::copy_n(in.begin(), count, out); + test(std::ranges::copy_if, in, out, unary_pred); + test(std::ranges::copy_backward, in, out); + test(std::ranges::move, in, out); + test(std::ranges::move_backward, in, out); + test(std::ranges::fill, in, x); + std::ranges::fill_n(in.begin(), count, x); + test(std::ranges::transform, in, out, std::identity{}); + test(std::ranges::transform, in, in2, out, binary_func); + //test(std::ranges::generate, in, gen); + //std::ranges::generate_n(in.begin(), count, gen); + //test(std::ranges::remove_copy, in, out, x); + //test(std::ranges::remove_copy_if, in, out, unary_pred); + test(std::ranges::replace, in, x, x); + test(std::ranges::replace_if, in, unary_pred, x); + //test(std::ranges::replace_copy, in, out, x, x); + //test(std::ranges::replace_copy_if, in, out, unary_pred, x); + //test(std::ranges::swap_ranges, in, in2); + test(std::ranges::reverse_copy, in, out); + test_mid(std::ranges::rotate_copy, in, mid, out); + //test(std::ranges::sample, in, out, count, rand_gen); + //test(std::ranges::unique_copy, in, out, binary_pred); + //test(std::ranges::partition_copy, in, out, out2, unary_pred); + //test_mid(std::ranges::partial_sort_copy, in, in2, binary_pred); + test(std::ranges::merge, in, in2, out); + test(std::ranges::set_difference, in, in2, out); + test(std::ranges::set_intersection, in, in2, out); + 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); + //test(std::ranges::stable_partition, in, binary_pred); + test(std::ranges::sort, in); + // TODO: `stable_sort` requires `ranges::rotate` to be implemented. + //test(std::ranges::stable_sort, in); + //test_mid(std::ranges::partial_sort, in, mid); + test_mid(std::ranges::nth_element, in, mid); + //test_mid(std::ranges::inplace_merge, in, mid); + test(std::ranges::make_heap, in); + test(std::ranges::push_heap, in, binary_pred); + test(std::ranges::pop_heap, in, binary_pred); + test(std::ranges::sort_heap, in, binary_pred); + //test(std::ranges::prev_permutation, in, binary_pred); + //test(std::ranges::next_permutation, in, binary_pred); +} diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -878,17 +878,39 @@ return *this; } + // If `T` is a reference type, the default assignment operator will be deleted. + constexpr Proxy& operator=(const Proxy& rhs) { + data = rhs.data; + return *this; + } + // no specialised swap function that takes const Proxy& and no specialised const member swap // Calling swap(Proxy{}, Proxy{}) would fail (pass prvalues) // Compare operators are defined for the convenience of the tests friend constexpr bool operator==(const Proxy&, const Proxy&) - requires std::equality_comparable + requires (std::equality_comparable && !std::is_reference_v) = default; + // Helps compare e.g. `Proxy` and `Proxy`. Note that the default equality comparison operator is deleted + // when `T` is a reference type. + template + friend constexpr bool operator==(const Proxy& lhs, const Proxy& rhs) + requires std::equality_comparable_with, std::decay_t> { + return lhs.data == rhs.data; + } + friend constexpr auto operator<=>(const Proxy&, const Proxy&) - requires std::three_way_comparable + requires (std::three_way_comparable && !std::is_reference_v) = default; + + // Helps compare e.g. `Proxy` and `Proxy`. Note that the default 3-way comparison operator is deleted when + // `T` is a reference type. + template + friend constexpr auto operator<=>(const Proxy& lhs, const Proxy& rhs) + requires std::three_way_comparable_with, std::decay_t> { + return lhs.data <=> rhs.data; + } }; // This is to make ProxyIterator model `std::indirectly_readable` @@ -920,7 +942,7 @@ template requires std::derived_from< typename std::iterator_traits::iterator_category, - std::input_iterator_tag> + std::input_iterator_tag> struct ProxyIteratorBase { using iterator_category = std::input_iterator_tag; }; @@ -951,8 +973,8 @@ = default; constexpr ProxyIterator(Base base) : base_{std::move(base)} {} - - template + + template requires std::constructible_from constexpr ProxyIterator(T&& t) : base_{std::forward(t)} {} @@ -1076,6 +1098,7 @@ static_assert(std::indirectly_readable>); static_assert(std::indirectly_writable, Proxy>); +static_assert(std::indirectly_writable, Proxy>); template struct ProxySentinel {