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<_STLClassicAlgorithms>(__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,13 +6,19 @@ // //===----------------------------------------------------------------------===// -#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> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,28 +26,63 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template struct _IterOps; + #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -struct _RangesIterOps { +struct _RangesAlgorithms {}; + +template <> +struct _IterOps<_RangesAlgorithms> { 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 _STLClassicAlgorithms {}; - template - _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void advance(_Iterator& __iter, _Distance __count) { - return std::advance(__iter, __count); +template <> +struct _IterOps<_STLClassicAlgorithms> { + + // 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::type>::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 _LIBCPP_CONSTEXPR_AFTER_CXX11 + static _Iter next(const _Iter&, const _Iter& __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 @@ -27,15 +27,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<_AlgFamily>::distance(__first, __last); while (__len != 0) { auto __l2 = std::__half_positive(__len); _Iter __m = __first; - _IterOps::advance(__m, __l2); + _IterOps<_AlgFamily>::advance(__m, __l2); if (std::__invoke(__comp, std::__invoke(__proj, *__m), __value)) { __first = ++__m; __len -= __l2 + 1; @@ -48,17 +48,17 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { +_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value, "The comparator has to be callable"); auto __proj = std::__identity(); - return std::__lower_bound_impl<_StdIterOps>(__first, __last, __value, __comp, __proj); + return std::__lower_bound_impl<_STLClassicAlgorithms>(__first, __last, __value_, __comp, __proj); } template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::lower_bound(__first, __last, __value, +_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) { + return std::lower_bound(__first, __last, __value_, __less::value_type, _Tp>()); } 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<_RangesAlgorithms>(__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<_RangesAlgorithms>(__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<_RangesAlgorithms>(__first, __last, __value, __comp, __proj); } template (ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); + return std::__lower_bound_impl<_RangesAlgorithms>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); } }; } // namespace __lower_bound 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<_RangesAlgorithms>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); } template (ranges::begin(__r), + return std::__lower_bound_impl<_RangesAlgorithms>(ranges::begin(__r), ranges::end(__r), __value, __comp_lhs_rhs_swapped,