diff --git a/libcxx/include/__algorithm/equal_range.h b/libcxx/include/__algorithm/equal_range.h --- a/libcxx/include/__algorithm/equal_range.h +++ b/libcxx/include/__algorithm/equal_range.h @@ -55,7 +55,7 @@ _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( - _VSTD::__lower_bound_impl<_StdIterOps>(__first, __m, __value, __comp, __proj), + _VSTD::__lower_bound_impl<_ClassicAlgPolicy>(__first, __m, __value, __comp, __proj), _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value, __comp) ); } 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 @@ -6,14 +6,20 @@ // //===----------------------------------------------------------------------===// -#ifndef _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H -#define _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H +#ifndef _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H +#define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H +#include <__algorithm/iter_swap.h> #include <__config> #include <__iterator/advance.h> #include <__iterator/distance.h> +#include <__iterator/iter_move.h> +#include <__iterator/iter_swap.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> +#include <__utility/forward.h> +#include <__utility/move.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,35 +27,63 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template struct _IterOps; + #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -struct _RangesIterOps { +struct _RangeAlgPolicy {}; + +template <> +struct _IterOps<_RangeAlgPolicy> { static constexpr auto advance = ranges::advance; static constexpr auto distance = ranges::distance; + static constexpr auto __iter_move = ranges::iter_move; + static constexpr auto iter_swap = ranges::iter_swap; static constexpr auto next = ranges::next; }; #endif -struct _StdIterOps { +struct _ClassicAlgPolicy {}; + +template <> +struct _IterOps<_ClassicAlgPolicy> { - template - _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void advance(_Iterator& __iter, _Distance __count) { - return std::advance(__iter, __count); + // advance + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + static void advance(_Iter& __iter, _Distance __count) { + std::advance(__iter, __count); } - template - _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 - typename iterator_traits<_Iterator>::difference_type distance(_Iterator __first, _Iterator __last) { + // distance + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + static typename iterator_traits<_Iter>::difference_type distance(_Iter __first, _Iter __last) { return std::distance(__first, __last); } + // iter_move + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + // Declaring the return type is necessary for the C++03 mode (which doesn't support placeholder return types). + static typename iterator_traits<__uncvref_t<_Iter> >::value_type&& __iter_move(_Iter&& __i) { + return std::move(*std::forward<_Iter>(__i)); + } + + // iter_swap + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + static void iter_swap(_Iter1&& __a, _Iter2&& __b) { + std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b)); + } + + // next template _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 _Iterator next(_Iterator, _Iterator __last) { return __last; } - }; _LIBCPP_END_NAMESPACE_STD -#endif // _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H +#endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H diff --git a/libcxx/include/__algorithm/lower_bound.h b/libcxx/include/__algorithm/lower_bound.h --- a/libcxx/include/__algorithm/lower_bound.h +++ b/libcxx/include/__algorithm/lower_bound.h @@ -19,6 +19,7 @@ #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__type_traits/is_callable.h> +#include <__type_traits/remove_reference.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -27,15 +28,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter __lower_bound_impl(_Iter __first, _Sent __last, const _Type& __value, _Comp& __comp, _Proj& __proj) { - auto __len = _IterOps::distance(__first, __last); + auto __len = _IterOps<_AlgPolicy>::distance(__first, __last); while (__len != 0) { auto __l2 = std::__half_positive(__len); _Iter __m = __first; - _IterOps::advance(__m, __l2); + _IterOps<_AlgPolicy>::advance(__m, __l2); if (std::__invoke(__comp, std::__invoke(__proj, *__m), __value)) { __first = ++__m; __len -= __l2 + 1; @@ -52,7 +53,7 @@ static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value, "The comparator has to be callable"); auto __proj = std::__identity(); - return std::__lower_bound_impl<_StdIterOps>(__first, __last, __value, __comp, __proj); + return std::__lower_bound_impl<_ClassicAlgPolicy>(__first, __last, __value, __comp, __proj); } template diff --git a/libcxx/include/__algorithm/ranges_binary_search.h b/libcxx/include/__algorithm/ranges_binary_search.h --- a/libcxx/include/__algorithm/ranges_binary_search.h +++ b/libcxx/include/__algorithm/ranges_binary_search.h @@ -35,7 +35,7 @@ indirect_strict_weak_order> _Comp = ranges::less> _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { - auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); + auto __ret = std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj); return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); } @@ -45,7 +45,7 @@ bool operator()(_Range&& __r, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { auto __first = ranges::begin(__r); auto __last = ranges::end(__r); - auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); + auto __ret = std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj); return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); } }; diff --git a/libcxx/include/__algorithm/ranges_lower_bound.h b/libcxx/include/__algorithm/ranges_lower_bound.h --- a/libcxx/include/__algorithm/ranges_lower_bound.h +++ b/libcxx/include/__algorithm/ranges_lower_bound.h @@ -39,7 +39,7 @@ indirect_strict_weak_order> _Comp = ranges::less> _LIBCPP_HIDE_FROM_ABI constexpr _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { - return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); + return std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj); } template (ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); + return std::__lower_bound_impl<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); } }; } // namespace __lower_bound diff --git a/libcxx/include/__algorithm/ranges_set_intersection.h b/libcxx/include/__algorithm/ranges_set_intersection.h --- a/libcxx/include/__algorithm/ranges_set_intersection.h +++ b/libcxx/include/__algorithm/ranges_set_intersection.h @@ -59,7 +59,7 @@ _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { - auto __ret = std::__set_intersection<_RangesIterOps>( + auto __ret = std::__set_intersection<_RangeAlgPolicy>( std::move(__first1), std::move(__last1), std::move(__first2), @@ -93,7 +93,7 @@ _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { - auto __ret = std::__set_intersection<_RangesIterOps>( + auto __ret = std::__set_intersection<_RangeAlgPolicy>( ranges::begin(__range1), ranges::end(__range1), ranges::begin(__range2), diff --git a/libcxx/include/__algorithm/ranges_upper_bound.h b/libcxx/include/__algorithm/ranges_upper_bound.h --- a/libcxx/include/__algorithm/ranges_upper_bound.h +++ b/libcxx/include/__algorithm/ranges_upper_bound.h @@ -40,7 +40,7 @@ return !std::invoke(__comp, __rhs, __lhs); }; - return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); + return std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); } template (ranges::begin(__r), + return std::__lower_bound_impl<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), __value, __comp_lhs_rhs_swapped, diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -34,7 +34,7 @@ : in1(std::move(__in_iter1)), in2(std::move(__in_iter2)), out(std::move(__out_iter)) {} }; -template < class _IterOper, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> +template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 __set_intersection_result<_InIter1, _InIter2, _OutIter> __set_intersection( _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { @@ -52,8 +52,8 @@ } return __set_intersection_result<_InIter1, _InIter2, _OutIter>( - _IterOper::next(std::move(__first1), std::move(__last1)), - _IterOper::next(std::move(__first2), std::move(__last2)), + _IterOps<_AlgPolicy>::next(std::move(__first1), std::move(__last1)), + _IterOps<_AlgPolicy>::next(std::move(__first2), std::move(__last2)), std::move(__result)); } @@ -66,7 +66,7 @@ _OutputIterator __result, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return std::__set_intersection<_StdIterOps, _Comp_ref>( + return std::__set_intersection<_ClassicAlgPolicy, _Comp_ref>( std::move(__first1), std::move(__last1), std::move(__first2), @@ -83,7 +83,7 @@ _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { - return std::__set_intersection<_StdIterOps>( + return std::__set_intersection<_ClassicAlgPolicy>( std::move(__first1), std::move(__last1), std::move(__first2),