From 1f04759316204e677b7bc8c049ea259253a2795d Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Wed, 13 Jul 2022 13:41:25 +0200 Subject: Revert "[libc++] Implement ranges::find_end, ranges::search{, _n}" This reverts commit 76a76518507ccc59ccdad5b83f44dc8c3d9593c7. --- libcxx/include/CMakeLists.txt | 3 - libcxx/include/__algorithm/find_end.h | 181 +++++++---------------- libcxx/include/__algorithm/iterator_operations.h | 1 - libcxx/include/__algorithm/ranges_find_end.h | 113 -------------- libcxx/include/__algorithm/ranges_search.h | 134 ----------------- libcxx/include/__algorithm/ranges_search_n.h | 120 --------------- libcxx/include/__algorithm/search.h | 176 ++++++---------------- libcxx/include/__algorithm/search_n.h | 159 ++++++-------------- libcxx/include/__algorithm/set_intersection.h | 1 - libcxx/include/__functional/default_searcher.h | 8 +- libcxx/include/__iterator/iterator_traits.h | 6 - libcxx/include/__string/char_traits.h | 4 +- libcxx/include/algorithm | 46 ------ libcxx/include/experimental/functional | 6 +- libcxx/include/module.modulemap.in | 3 - 15 files changed, 155 insertions(+), 806 deletions(-) delete mode 100644 libcxx/include/__algorithm/ranges_find_end.h delete mode 100644 libcxx/include/__algorithm/ranges_search.h delete mode 100644 libcxx/include/__algorithm/ranges_search_n.h (limited to 'libcxx/include') diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index 05c7c7b6bbcc..5af1f9439301 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -83,7 +83,6 @@ set(files __algorithm/ranges_fill.h __algorithm/ranges_fill_n.h __algorithm/ranges_find.h - __algorithm/ranges_find_end.h __algorithm/ranges_find_first_of.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h @@ -130,8 +129,6 @@ set(files __algorithm/ranges_reverse.h __algorithm/ranges_reverse_copy.h __algorithm/ranges_rotate_copy.h - __algorithm/ranges_search.h - __algorithm/ranges_search_n.h __algorithm/ranges_set_difference.h __algorithm/ranges_set_intersection.h __algorithm/ranges_set_union.h diff --git a/libcxx/include/__algorithm/find_end.h b/libcxx/include/__algorithm/find_end.h index 755b643c1180..0220c0939711 100644 --- a/libcxx/include/__algorithm/find_end.h +++ b/libcxx/include/__algorithm/find_end.h @@ -11,16 +11,8 @@ #define _LIBCPP___ALGORITHM_FIND_END_OF_H #include <__algorithm/comp.h> -#include <__algorithm/iterator_operations.h> -#include <__algorithm/search.h> #include <__config> -#include <__functional/identity.h> -#include <__iterator/advance.h> #include <__iterator/iterator_traits.h> -#include <__iterator/next.h> -#include <__iterator/reverse_iterator.h> -#include <__utility/pair.h> -#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -28,52 +20,35 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template < - class _IterOps, - class _Iter1, - class _Sent1, - class _Iter2, - class _Sent2, - class _Pred, - class _Proj1, - class _Proj2> -_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> __find_end_impl( - _Iter1 __first1, - _Sent1 __last1, - _Iter2 __first2, - _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - forward_iterator_tag, - forward_iterator_tag) { +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred, forward_iterator_tag, + forward_iterator_tag) { // modeled after search algorithm - _Iter1 __match_first = _IterOps::next(__first1, __last1); // __last1 is the "default" answer - _Iter1 __match_last = __match_first; + _ForwardIterator1 __r = __last1; // __last1 is the "default" answer if (__first2 == __last2) - return pair<_Iter1, _Iter1>(__match_last, __match_last); + return __r; while (true) { while (true) { - if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) - return pair<_Iter1, _Iter1>(__match_first, __match_last); - if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) + if (__first1 == __last1) // if source exhausted return last correct answer + return __r; // (or __last1 if never found) + if (__pred(*__first1, *__first2)) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _Iter1 __m1 = __first1; - _Iter2 __m2 = __first2; + _ForwardIterator1 __m1 = __first1; + _ForwardIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one - __match_first = __first1; - __match_last = ++__m1; + __r = __first1; ++__first1; break; } if (++__m1 == __last1) // Source exhausted, return last answer - return pair<_Iter1, _Iter1>(__match_first, __match_last); - // mismatch, restart with a new __first - if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) + return __r; + if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first { ++__first1; break; @@ -82,52 +57,33 @@ _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> } } -template < - class _IterOps, - class _Pred, - class _Iter1, - class _Sent1, - class _Iter2, - class _Sent2, - class _Proj1, - class _Proj2> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end( - _Iter1 __first1, - _Sent1 __sent1, - _Iter2 __first2, - _Sent2 __sent2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - bidirectional_iterator_tag, - bidirectional_iterator_tag) { - auto __last1 = _IterOps::next(__first1, __sent1); - auto __last2 = _IterOps::next(__first2, __sent2); +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( + _BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, + _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag) { // modeled after search algorithm (in reverse) if (__first2 == __last2) return __last1; // Everything matches an empty sequence - _Iter1 __l1 = __last1; - _Iter2 __l2 = __last2; + _BidirectionalIterator1 __l1 = __last1; + _BidirectionalIterator2 __l2 = __last2; --__l2; while (true) { // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks while (true) { if (__first1 == __l1) // return __last1 if no element matches *__first2 return __last1; - if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) + if (__pred(*--__l1, *__l2)) break; } // *__l1 matches *__l2, now match elements before here - _Iter1 __m1 = __l1; - _Iter2 __m2 = __l2; + _BidirectionalIterator1 __m1 = __l1; + _BidirectionalIterator2 __m2 = __l2; while (true) { if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) return __m1; if (__m1 == __first1) // Otherwise if source exhaused, pattern not found return __last1; - - // if there is a mismatch, restart with a new __l1 - if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) + if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 { break; } // else there is a match, check next elements @@ -135,53 +91,37 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end( } } -template < - class _IterOps, - class _Pred, - class _Iter1, - class _Sent1, - class _Iter2, - class _Sent2, - class _Proj1, - class _Proj2> -_LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end( - _Iter1 __first1, - _Sent1 __sent1, - _Iter2 __first2, - _Sent2 __sent2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - random_access_iterator_tag, - random_access_iterator_tag) { - typedef typename iterator_traits<_Iter1>::difference_type _D1; - auto __last1 = _IterOps::next(__first1, __sent1); - auto __last2 = _IterOps::next(__first2, __sent2); +template +_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( + _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { + typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; + typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - auto __len2 = __last2 - __first2; + _D2 __len2 = __last2 - __first2; if (__len2 == 0) return __last1; - auto __len1 = __last1 - __first1; + _D1 __len1 = __last1 - __first1; if (__len1 < __len2) return __last1; - const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here - _Iter1 __l1 = __last1; - _Iter2 __l2 = __last2; + const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here + _RandomAccessIterator1 __l1 = __last1; + _RandomAccessIterator2 __l2 = __last2; --__l2; while (true) { while (true) { if (__s == __l1) return __last1; - if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) + if (__pred(*--__l1, *__l2)) break; } - _Iter1 __m1 = __l1; - _Iter2 __m2 = __l2; + _RandomAccessIterator1 __m1 = __l1; + _RandomAccessIterator2 __m2 = __l2; while (true) { if (__m2 == __first2) return __m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) { + if (!__pred(*--__m1, *--__m2)) { break; } } @@ -189,39 +129,20 @@ _LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end( } template -_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -_ForwardIterator1 __find_end_classic(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate& __pred) { - auto __proj = __identity(); - return std::__find_end_impl<_StdIterOps>( - __first1, - __last1, - __first2, - __last2, - __pred, - __proj, - __proj, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()) - .first; -} - -template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + return _VSTD::__find_end<_BinaryPredicate&>( + __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; - using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; - return std::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h index 4c4f406efe81..bccac368f302 100644 --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -39,7 +39,6 @@ struct _IterOps<_RangeAlgPolicy> { static constexpr auto __iter_move = ranges::iter_move; static constexpr auto iter_swap = ranges::iter_swap; static constexpr auto next = ranges::next; - static constexpr auto __advance_to = ranges::advance; }; #endif diff --git a/libcxx/include/__algorithm/ranges_find_end.h b/libcxx/include/__algorithm/ranges_find_end.h deleted file mode 100644 index 5c301b35abbd..000000000000 --- a/libcxx/include/__algorithm/ranges_find_end.h +++ /dev/null @@ -1,113 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_END_H -#define _LIBCPP___ALGORITHM_RANGES_FIND_END_H - -#include <__algorithm/find_end.h> -#include <__algorithm/iterator_operations.h> -#include <__config> -#include <__functional/identity.h> -#include <__functional/ranges_operations.h> -#include <__iterator/concepts.h> -#include <__iterator/indirectly_comparable.h> -#include <__iterator/iterator_traits.h> -#include <__ranges/access.h> -#include <__ranges/concepts.h> -#include <__ranges/subrange.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - -_LIBCPP_BEGIN_NAMESPACE_STD - -template -consteval auto __get_iterator_concept() { - if constexpr (contiguous_iterator<_Iter>) - return contiguous_iterator_tag(); - else if constexpr (random_access_iterator<_Iter>) - return random_access_iterator_tag(); - else if constexpr (bidirectional_iterator<_Iter>) - return bidirectional_iterator_tag(); - else if constexpr (forward_iterator<_Iter>) - return forward_iterator_tag(); - else if constexpr (input_iterator<_Iter>) - return input_iterator_tag(); -} - -template -using __iterator_concept = decltype(__get_iterator_concept<_Iter>()); - -namespace ranges { -namespace __find_end { -struct __fn { - template _Sent1, - forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - class _Pred = ranges::equal_to, - class _Proj1 = identity, - class _Proj2 = identity> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - _LIBCPP_HIDE_FROM_ABI constexpr - subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred __pred = {}, - _Proj1 __proj1 = {}, - _Proj2 __proj2 = {}) const { - auto __ret = std::__find_end_impl<_RangesIterOps>( - __first1, - __last1, - __first2, - __last2, - __pred, - __proj1, - __proj2, - __iterator_concept<_Iter1>(), - __iterator_concept<_Iter2>()); - return {__ret.first, __ret.second}; - } - - template - requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> - _LIBCPP_HIDE_FROM_ABI constexpr - borrowed_subrange_t<_Range1> operator()(_Range1&& __range1, - _Range2&& __range2, - _Pred __pred = {}, - _Proj1 __proj1 = {}, - _Proj2 __proj2 = {}) const { - auto __ret = std::__find_end_impl<_RangesIterOps>( - ranges::begin(__range1), - ranges::end(__range1), - ranges::begin(__range2), - ranges::end(__range2), - __pred, - __proj1, - __proj2, - __iterator_concept>(), - __iterator_concept>()); - return {__ret.first, __ret.second}; - } -}; -} // namespace __find_end - -inline namespace __cpo { - inline constexpr auto find_end = __find_end::__fn{}; -} // namespace __cpo -} // namespace ranges - -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - -#endif // _LIBCPP___ALGORITHM_RANGES_FIND_END_H diff --git a/libcxx/include/__algorithm/ranges_search.h b/libcxx/include/__algorithm/ranges_search.h deleted file mode 100644 index a7b7695d280f..000000000000 --- a/libcxx/include/__algorithm/ranges_search.h +++ /dev/null @@ -1,134 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___ALGORITHM_RANGES_SEARCH_H -#define _LIBCPP___ALGORITHM_RANGES_SEARCH_H - -#include <__algorithm/iterator_operations.h> -#include <__algorithm/search.h> -#include <__config> -#include <__functional/identity.h> -#include <__functional/ranges_operations.h> -#include <__iterator/advance.h> -#include <__iterator/concepts.h> -#include <__iterator/distance.h> -#include <__iterator/indirectly_comparable.h> -#include <__ranges/access.h> -#include <__ranges/concepts.h> -#include <__ranges/size.h> -#include <__ranges/subrange.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - -_LIBCPP_BEGIN_NAMESPACE_STD - -namespace ranges { -namespace __search { -struct __fn { - template - _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_impl( - _Iter1 __first1, - _Sent1 __last1, - _Iter2 __first2, - _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2) { - if constexpr (sized_sentinel_for<_Sent2, _Iter2>) { - auto __size2 = ranges::distance(__first2, __last2); - if (__size2 == 0) - return {__first1, __first1}; - - if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { - auto __size1 = ranges::distance(__first1, __last1); - if (__size1 < __size2) { - ranges::advance(__first1, __last1); - return {__first1, __first1}; - } - - if constexpr (random_access_iterator<_Iter1> && random_access_iterator<_Iter2>) { - auto __ret = std::__search_random_access_impl<_RangesIterOps>( - __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2); - return {__ret.first, __ret.second}; - } - } - } - - auto __ret = - std::__search_forward_impl<_RangesIterOps>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); - return {__ret.first, __ret.second}; - } - - template _Sent1, - forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - class _Pred = ranges::equal_to, - class _Proj1 = identity, - class _Proj2 = identity> - requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> - _LIBCPP_HIDE_FROM_ABI constexpr - subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred __pred = {}, - _Proj1 __proj1 = {}, - _Proj2 __proj2 = {}) const { - return __ranges_search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); - } - - template - requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> - _LIBCPP_HIDE_FROM_ABI constexpr - borrowed_subrange_t<_Range1> operator()(_Range1&& __range1, - _Range2&& __range2, - _Pred __pred = {}, - _Proj1 __proj1 = {}, - _Proj2 __proj2 = {}) const { - auto __first1 = ranges::begin(__range1); - if constexpr (sized_range<_Range2>) { - auto __size2 = ranges::size(__range2); - if (__size2 == 0) - return {__first1, __first1}; - if constexpr (sized_range<_Range1>) { - auto __size1 = ranges::size(__range1); - if (__size1 < __size2) { - ranges::advance(__first1, ranges::end(__range1)); - return {__first1, __first1}; - } - } - } - - return __ranges_search_impl( - ranges::begin(__range1), - ranges::end(__range1), - ranges::begin(__range2), - ranges::end(__range2), - __pred, - __proj1, - __proj2); - } - -}; -} // namespace __search - -inline namespace __cpo { - inline constexpr auto search = __search::__fn{}; -} // namespace __cpo -} // namespace ranges - -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - -#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H diff --git a/libcxx/include/__algorithm/ranges_search_n.h b/libcxx/include/__algorithm/ranges_search_n.h deleted file mode 100644 index d7178ca415b1..000000000000 --- a/libcxx/include/__algorithm/ranges_search_n.h +++ /dev/null @@ -1,120 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H -#define _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H - -#include <__algorithm/iterator_operations.h> -#include <__algorithm/search_n.h> -#include <__config> -#include <__functional/identity.h> -#include <__functional/ranges_operations.h> -#include <__iterator/advance.h> -#include <__iterator/concepts.h> -#include <__iterator/distance.h> -#include <__iterator/incrementable_traits.h> -#include <__iterator/indirectly_comparable.h> -#include <__iterator/iterator_traits.h> -#include <__ranges/access.h> -#include <__ranges/concepts.h> -#include <__ranges/size.h> -#include <__ranges/subrange.h> -#include <__utility/move.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - -_LIBCPP_BEGIN_NAMESPACE_STD - -namespace ranges { -namespace __search_n { -struct __fn { - - template - _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_n_impl( - _Iter1 __first, _Sent1 __last, _SizeT __count, const _Type& __value, _Pred& __pred, _Proj& __proj) { - if (__count == 0) - return {__first, __first}; - - if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { - auto __size = ranges::distance(__first, __last); - if (__size < __count) { - ranges::advance(__first, __last); - return {__first, __first}; - } - - if constexpr (random_access_iterator<_Iter1>) { - auto __ret = __search_n_random_access_impl<_RangesIterOps>(__first, __last, - __count, - __value, - __pred, - __proj, - __size); - return {std::move(__ret.first), std::move(__ret.second)}; - } - } - - auto __ret = std::__search_n_forward_impl<_RangesIterOps>(__first, __last, - __count, - __value, - __pred, - __proj); - return {std::move(__ret.first), std::move(__ret.second)}; - } - - template _Sent, - class _Type, - class _Pred = ranges::equal_to, - class _Proj = identity> - requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj> - _LIBCPP_HIDE_FROM_ABI constexpr - subrange<_Iter> operator()(_Iter __first, _Sent __last, - iter_difference_t<_Iter> __count, - const _Type& __value, - _Pred __pred = {}, - _Proj __proj = _Proj{}) const { - return __ranges_search_n_impl(__first, __last, __count, __value, __pred, __proj); - } - - template - requires indirectly_comparable, const _Type*, _Pred, _Proj> - _LIBCPP_HIDE_FROM_ABI constexpr - borrowed_subrange_t<_Range> operator()(_Range&& __range, - range_difference_t<_Range> __count, - const _Type& __value, - _Pred __pred = {}, - _Proj __proj = {}) const { - auto __first = ranges::begin(__range); - if (__count <= 0) - return {__first, __first}; - if constexpr (sized_range<_Range>) { - auto __size1 = ranges::size(__range); - if (__size1 < static_cast>(__count)) { - ranges::advance(__first, ranges::end(__range)); - return {__first, __first}; - } - } - - return __ranges_search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj); - } -}; -} // namespace __search_n - -inline namespace __cpo { - inline constexpr auto search_n = __search_n::__fn{}; -} // namespace __cpo -} // namespace ranges - -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - -#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H diff --git a/libcxx/include/__algorithm/search.h b/libcxx/include/__algorithm/search.h index b5c4820e5daa..d89ec2b1c5bc 100644 --- a/libcxx/include/__algorithm/search.h +++ b/libcxx/include/__algorithm/search.h @@ -11,15 +11,9 @@ #define _LIBCPP___ALGORITHM_SEARCH_H #include <__algorithm/comp.h> -#include <__algorithm/iterator_operations.h> #include <__config> -#include <__functional/identity.h> -#include <__iterator/advance.h> -#include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> -#include <__type_traits/is_callable.h> #include <__utility/pair.h> -#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -27,43 +21,31 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2) { +template +pair<_ForwardIterator1, _ForwardIterator1> + _LIBCPP_CONSTEXPR_AFTER_CXX11 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { if (__first2 == __last2) - return std::make_pair(__first1, __first1); // Everything matches an empty sequence + return _VSTD::make_pair(__first1, __first1); // Everything matches an empty sequence while (true) { // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks while (true) { - if (__first1 == __last1) { // return __last1 if no element matches *__first2 - _IterOps::__advance_to(__first1, __last1); - return std::make_pair(__first1, __first1); - } - if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) + if (__first1 == __last1) // return __last1 if no element matches *__first2 + return _VSTD::make_pair(__last1, __last1); + if (__pred(*__first1, *__first2)) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _Iter1 __m1 = __first1; - _Iter2 __m2 = __first2; + _ForwardIterator1 __m1 = __first1; + _ForwardIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) - return std::make_pair(__first1, ++__m1); - if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found - return std::make_pair(__m1, __m1); - } - - // if there is a mismatch, restart with a new __first1 - if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) + return _VSTD::make_pair(__first1, __m1); + if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found + return _VSTD::make_pair(__last1, __last1); + if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 { ++__first1; break; @@ -72,42 +54,38 @@ pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1, } } -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - _DiffT1 __size1, - _DiffT2 __size2) { - const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here +template +_LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_RandomAccessIterator1, _RandomAccessIterator1> +__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, + _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, + random_access_iterator_tag) { + typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; + typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; + // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern + const _D2 __len2 = __last2 - __first2; + if (__len2 == 0) + return _VSTD::make_pair(__first1, __first1); + const _D1 __len1 = __last1 - __first1; + if (__len1 < __len2) + return _VSTD::make_pair(__last1, __last1); + const _RandomAccessIterator1 __s = __last1 - _D1(__len2 - 1); // Start of pattern match can't go beyond here while (true) { while (true) { - if (__first1 == __s) { - _IterOps::__advance_to(__first1, __last1); - return std::make_pair(__first1, __first1); - } - if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) + if (__first1 == __s) + return _VSTD::make_pair(__last1, __last1); + if (__pred(*__first1, *__first2)) break; ++__first1; } - _Iter1 __m1 = __first1; - _Iter2 __m2 = __first2; + _RandomAccessIterator1 __m1 = __first1; + _RandomAccessIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) - return std::make_pair(__first1, __first1 + _DiffT1(__size2)); + return _VSTD::make_pair(__first1, __first1 + _D1(__len2)); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { + if (!__pred(*__m1, *__m2)) { ++__first1; break; } @@ -115,78 +93,22 @@ pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1 } } -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - __enable_if_t<__is_cpp17_random_access_iterator<_Iter1>::value - && __is_cpp17_random_access_iterator<_Iter2>::value>* = nullptr) { - - auto __size2 = __last2 - __first2; - if (__size2 == 0) - return std::make_pair(__first1, __first1); - - auto __size1 = __last1 - __first1; - if (__size1 < __size2) { - return std::make_pair(__last1, __last1); - } - - return std::__search_random_access_impl<_StdIterOps>(__first1, __last1, - __first2, __last2, - __pred, - __proj1, - __proj2, - __size1, - __size2); -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, - _Iter2 __first2, _Sent2 __last2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value - && __is_cpp17_forward_iterator<_Iter2>::value - && !(__is_cpp17_random_access_iterator<_Iter1>::value - && __is_cpp17_random_access_iterator<_Iter2>::value)>* = nullptr) { - return std::__search_forward_impl<_StdIterOps>(__first1, __last1, - __first2, __last2, - __pred, - __proj1, - __proj2); -} - template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, - "BinaryPredicate has to be callable"); - auto __proj = __identity(); - return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first; +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + return _VSTD::__search<_BinaryPredicate&>( + __first1, __last1, __first2, __last2, __pred, + typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()).first; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; - using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; - return std::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 +search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; + typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; + return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } #if _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h index 2a9285f4efe5..c51701415bdc 100644 --- a/libcxx/include/__algorithm/search_n.h +++ b/libcxx/include/__algorithm/search_n.h @@ -11,15 +11,8 @@ #define _LIBCPP___ALGORITHM_SEARCH_N_H #include <__algorithm/comp.h> -#include <__algorithm/iterator_operations.h> #include <__config> -#include <__functional/identity.h> -#include <__iterator/advance.h> -#include <__iterator/concepts.h> -#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> -#include <__ranges/concepts.h> -#include <__utility/pair.h> #include // __convert_to_integral #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -28,39 +21,30 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last, - _SizeT __count, - const _Type& __value, - _Pred& __pred, - _Proj& __proj) { +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, + _Size __count, const _Tp& __value, _BinaryPredicate __pred, + forward_iterator_tag) { if (__count <= 0) - return std::make_pair(__first, __first); + return __first; while (true) { - // Find first element in sequence that matchs __value, with a mininum of loop checks + // Find first element in sequence that matchs __value_, with a mininum of loop checks while (true) { - if (__first == __last) { // return __last if no element matches __value - _IterOps::__advance_to(__first, __last); - return std::make_pair(__first, __first); - } - if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) + if (__first == __last) // return __last if no element matches __value_ + return __last; + if (__pred(*__first, __value)) break; ++__first; } - // *__first matches __value, now match elements after here - _Iter __m = __first; - _SizeT __c(0); + // *__first matches __value_, now match elements after here + _ForwardIterator __m = __first; + _Size __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return std::make_pair(__first, ++__m); - if (++__m == __last) { // Otherwise if source exhaused, pattern not found - _IterOps::__advance_to(__first, __last); - return std::make_pair(__first, __first); - } - - // if there is a mismatch, restart with a new __first - if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) + return __first; + if (++__m == __last) // Otherwise if source exhaused, pattern not found + return __last; + if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first { __first = __m; ++__first; @@ -70,44 +54,35 @@ pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last, } } -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __last, - _SizeT __count, - const _Type& __value, - _Pred& __pred, - _Proj& __proj, - _DiffT __size1) { - using difference_type = typename iterator_traits<_Iter>::difference_type; - if (__count == 0) - return std::make_pair(__first, __first); - if (__size1 < static_cast<_DiffT>(__count)) { - _IterOps::__advance_to(__first, __last); - return std::make_pair(__first, __first); - } - - const auto __s = __first + __size1 - difference_type(__count - 1); // Start of pattern match can't go beyond here +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first, + _RandomAccessIterator __last, _Size __count, + const _Tp& __value, _BinaryPredicate __pred, + random_access_iterator_tag) { + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + if (__count <= 0) + return __first; + _Size __len = static_cast<_Size>(__last - __first); + if (__len < __count) + return __last; + const _RandomAccessIterator __s = __last - difference_type(__count - 1); // Start of pattern match can't go beyond here while (true) { - // Find first element in sequence that matchs __value, with a mininum of loop checks + // Find first element in sequence that matchs __value_, with a mininum of loop checks while (true) { - if (__first >= __s) { // return __last if no element matches __value - _IterOps::__advance_to(__first, __last); - return std::make_pair(__first, __first); - } - if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) + if (__first >= __s) // return __last if no element matches __value_ + return __last; + if (__pred(*__first, __value)) break; ++__first; } // *__first matches __value_, now match elements after here - auto __m = __first; - _SizeT __c(0); + _RandomAccessIterator __m = __first; + _Size __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return std::make_pair(__first, __first + _DiffT(__count)); - ++__m; // no need to check range on __m because __s guarantees we have enough source - - // if there is a mismatch, restart with a new __first - if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) + return __first; + ++__m; // no need to check range on __m because __s guarantees we have enough source + if (!__pred(*__m, __value)) // if there is a mismatch, restart with a new __first { __first = __m; ++__first; @@ -117,63 +92,19 @@ std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __las } } -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter, _Iter> __search_n_impl(_Iter __first, _Sent __last, - _DiffT __count, - const _Type& __value, - _Pred& __pred, - _Proj& __proj, - __enable_if_t<__is_cpp17_random_access_iterator<_Iter>::value>* = nullptr) { - return std::__search_n_random_access_impl<_StdIterOps>(__first, __last, - __count, - __value, - __pred, - __proj, - __last - __first); -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Iter1, _Iter1> __search_n_impl(_Iter1 __first, _Sent1 __last, - _DiffT __count, - const _Type& __value, - _Pred& __pred, - _Proj& __proj, - __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value - && !__is_cpp17_random_access_iterator<_Iter1>::value>* = nullptr) { - return std::__search_n_forward_impl<_StdIterOps>(__first, __last, - __count, - __value, - __pred, - __proj); -} - template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, - _Size __count, - const _Tp& __value, - _BinaryPredicate __pred) { - static_assert(__is_callable<_BinaryPredicate, decltype(*__first), decltype(*__last)>::value, - "BinaryPredicate has to be callable"); - auto __proj = __identity(); - return std::__search_n_impl(__first, __last, std::__convert_to_integral(__count), __value, __pred, __proj).first; +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n( + _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value, _BinaryPredicate __pred) { + return _VSTD::__search_n<_BinaryPredicate&>( + __first, __last, _VSTD::__convert_to_integral(__count), __value, __pred, + typename iterator_traits<_ForwardIterator>::iterator_category()); } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value) { +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value) { typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return std::search_n(__first, __last, std::__convert_to_integral(__count), __value, __equal_to<__v, _Tp>()); + return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value, __equal_to<__v, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h index e0f5bd140be7..650705703219 100644 --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -14,7 +14,6 @@ #include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <__iterator/next.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) diff --git a/libcxx/include/__functional/default_searcher.h b/libcxx/include/__functional/default_searcher.h index 8e37082b6bed..05fb23d7c3c4 100644 --- a/libcxx/include/__functional/default_searcher.h +++ b/libcxx/include/__functional/default_searcher.h @@ -12,7 +12,6 @@ #include <__algorithm/search.h> #include <__config> -#include <__functional/identity.h> #include <__functional/operations.h> #include <__iterator/iterator_traits.h> #include <__utility/pair.h> @@ -39,15 +38,16 @@ public: pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - auto __proj = __identity(); - return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); + return _VSTD::__search(__f, __l, __first_, __last_, __pred_, + typename iterator_traits<_ForwardIterator>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); } private: _ForwardIterator __first_; _ForwardIterator __last_; _BinaryPredicate __pred_; -}; + }; #endif // _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h index 63525e230add..1fbdc955d148 100644 --- a/libcxx/include/__iterator/iterator_traits.h +++ b/libcxx/include/__iterator/iterator_traits.h @@ -481,12 +481,6 @@ struct __is_exactly_cpp17_forward_iterator __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value && !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value> {}; -template -struct __is_exactly_cpp17_bidirectional_iterator - : public integral_constant::value && - !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value> {}; - template using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; diff --git a/libcxx/include/__string/char_traits.h b/libcxx/include/__string/char_traits.h index 18ad67b28e16..457a771b94cf 100644 --- a/libcxx/include/__string/char_traits.h +++ b/libcxx/include/__string/char_traits.h @@ -802,7 +802,9 @@ __str_rfind(const _CharT *__p, _SizeT __sz, __pos += __n; else __pos = __sz; - const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq); + const _CharT* __r = _VSTD::__find_end( + __p, __p + __pos, __s, __s + __n, _Traits::eq, + random_access_iterator_tag(), random_access_iterator_tag()); if (__n > 0 && __r == __p + __pos) return __npos; return static_cast<_SizeT>(__r - __p); diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 18d8ef3805e5..387aebe78e6c 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -649,49 +649,6 @@ namespace ranges { constexpr ranges::rotate_copy_result, O> ranges::rotate_copy(R&& r, iterator_t middle, O result); // since C++20 - template S1, forward_iterator I2, - sentinel_for S2, class Pred = ranges::equal_to, - class Proj1 = identity, class Proj2 = identity> - requires indirectly_comparable - constexpr subrange - ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - - template - requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> - constexpr borrowed_subrange_t - ranges::search(R1&& r1, R2&& r2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - - template S, class T, - class Pred = ranges::equal_to, class Proj = identity> - requires indirectly_comparable - constexpr subrange - ranges::search_n(I first, S last, iter_difference_t count, - const T& value, Pred pred = {}, Proj proj = {}); // since C++20 - - template - requires indirectly_comparable, const T*, Pred, Proj> - constexpr borrowed_subrange_t - ranges::search_n(R&& r, range_difference_t count, - const T& value, Pred pred = {}, Proj proj = {}); // since C++20 - - template S1, forward_iterator I2, sentinel_for S2, - class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> - requires indirectly_comparable - constexpr subrange - ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - - template - requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> - constexpr borrowed_subrange_t - ranges::find_end(R1&& r1, R2&& r2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - } constexpr bool // constexpr in C++20 @@ -1435,7 +1392,6 @@ template #include <__algorithm/ranges_fill.h> #include <__algorithm/ranges_fill_n.h> #include <__algorithm/ranges_find.h> -#include <__algorithm/ranges_find_end.h> #include <__algorithm/ranges_find_first_of.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> @@ -1468,8 +1424,6 @@ template #include <__algorithm/ranges_reverse.h> #include <__algorithm/ranges_reverse_copy.h> #include <__algorithm/ranges_rotate_copy.h> -#include <__algorithm/ranges_search.h> -#include <__algorithm/ranges_search_n.h> #include <__algorithm/ranges_set_difference.h> #include <__algorithm/ranges_set_intersection.h> #include <__algorithm/ranges_sort.h> diff --git a/libcxx/include/experimental/functional b/libcxx/include/experimental/functional index 12440744ca50..04f195d3cf24 100644 --- a/libcxx/include/experimental/functional +++ b/libcxx/include/experimental/functional @@ -62,7 +62,6 @@ inline namespace fundamentals_v1 { #include <__assert> // all public C++ headers provide the assertion handler #include <__debug> -#include <__functional/identity.h> #include <__memory/uses_allocator.h> #include #include @@ -105,8 +104,9 @@ public: pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - auto __proj = __identity(); - return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); + return _VSTD::__search(__f, __l, __first_, __last_, __pred_, + typename iterator_traits<_ForwardIterator>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); } private: diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index c0ecfac991fd..8efeb1fc4926 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -322,7 +322,6 @@ module std [system] { module ranges_fill { private header "__algorithm/ranges_fill.h" } module ranges_fill_n { private header "__algorithm/ranges_fill_n.h" } module ranges_find { private header "__algorithm/ranges_find.h" } - module ranges_find_end { private header "__algorithm/ranges_find_end.h" } module ranges_find_first_of { private header "__algorithm/ranges_find_first_of.h" } module ranges_find_if { private header "__algorithm/ranges_find_if.h" } module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" } @@ -369,8 +368,6 @@ module std [system] { module ranges_reverse { private header "__algorithm/ranges_reverse.h" } module ranges_reverse_copy { private header "__algorithm/ranges_reverse_copy.h" } module ranges_rotate_copy { private header "__algorithm/ranges_rotate_copy.h" } - module ranges_search { private header "__algorithm/ranges_search.h" } - module ranges_search_n { private header "__algorithm/ranges_search_n.h" } module ranges_set_difference { private header "__algorithm/ranges_set_difference.h" } module ranges_set_intersection { private header "__algorithm/ranges_set_intersection.h" } module ranges_set_union { private header "__algorithm/ranges_set_union.h" } -- cgit v1.2.3