diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -77,7 +77,7 @@ Permutation,stable_sort,Konstantin Varlamov,`D127834 `_,✅ Permutation,nth_element,Konstantin Varlamov,`D128149 `_,✅ Permutation,partial_sort,Konstantin Varlamov,`D128744 `_,✅ -Permutation,inplace_merge,Not assigned,n/a,Not started +Permutation,inplace_merge,Hui Xie,`D130404 `_,✅ Permutation,make_heap,Konstantin Varlamov,`D128115 `_,✅ Permutation,push_heap,Konstantin Varlamov,`D128115 `_,✅ Permutation,pop_heap,Konstantin Varlamov,`D128115 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -1,5 +1,6 @@ set(files __algorithm/adjacent_find.h + __algorithm/algorithm_family.h __algorithm/all_of.h __algorithm/any_of.h __algorithm/binary_search.h diff --git a/libcxx/include/__algorithm/algorithm_family.h b/libcxx/include/__algorithm/algorithm_family.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/algorithm_family.h @@ -0,0 +1,52 @@ +//===----------------------------------------------------------------------===// +// +// 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_ALGORITHM_FAMILY_H +#define _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/move.h> +#include <__algorithm/ranges_move.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct _AlgoFamily; + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +template <> +struct _AlgoFamily<_RangeAlgPolicy> { + static constexpr auto __move = ranges::move; +}; + +#endif + +template <> +struct _AlgoFamily<_ClassicAlgPolicy> { + + // move + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 static _OutputIterator + __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + return std::move( + std::move(__first), + std::move(__last), + std::move(__result)); + } +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H 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 @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_INPLACE_MERGE_H #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H +#include <__algorithm/algorithm_family.h> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/iterator_operations.h> @@ -38,204 +39,199 @@ class __invert // invert the sense of a comparison { private: - _Predicate __p_; + _Predicate __p_; + public: - _LIBCPP_INLINE_VISIBILITY __invert() {} + _LIBCPP_HIDE_FROM_ABI __invert() {} - _LIBCPP_INLINE_VISIBILITY - explicit __invert(_Predicate __p) : __p_(__p) {} + _LIBCPP_HIDE_FROM_ABI explicit __invert(_Predicate __p) : __p_(__p) {} - template - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x) {return !__p_(__x);} + template + _LIBCPP_HIDE_FROM_ABI bool operator()(const _T1& __x) { + return !__p_(__x); + } - template - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);} + template + _LIBCPP_HIDE_FROM_ABI 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) -{ - for (; __first1 != __last1; ++__result) - { - if (__first2 == __last2) - { - // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `move`. - _VSTD::move(__first1, __last1, __result); - return; - } - - if (__comp(*__first2, *__first1)) - { - *__result = _IterOps<_AlgPolicy>::__iter_move(__first2); - ++__first2; - } - else - { - *__result = _IterOps<_AlgPolicy>::__iter_move(__first1); - ++__first1; - } +template < + class _AlgPolicy, + class _Compare, + class _InputIterator1, + class _Sent1, + class _InputIterator2, + class _Sent2, + class _OutputIterator> +_LIBCPP_HIDE_FROM_ABI void __half_inplace_merge( + _InputIterator1 __first1, + _Sent1 __last1, + _InputIterator2 __first2, + _Sent2 __last2, + _OutputIterator __result, + _Compare&& __comp) { + for (; __first1 != __last1; ++__result) { + if (__first2 == __last2) { + _AlgoFamily<_AlgPolicy>::__move(__first1, __last1, __result); + return; + } + + if (__comp(*__first2, *__first1)) { + *__result = _IterOps<_AlgPolicy>::__iter_move(__first2); + ++__first2; + } else { + *__result = _IterOps<_AlgPolicy>::__iter_move(__first1); + ++__first1; } - // __first2 through __last2 are already in the right spot. + } + // __first2 through __last2 are already in the right spot. } 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) -{ - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - __destruct_n __d(0); - unique_ptr __h2(__buff, __d); - if (__len1 <= __len2) - { - value_type* __p = __buff; - for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr(), (void) ++__i, (void) ++__p) - ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__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(_IterOps<_AlgPolicy>::__iter_move(__i)); - typedef __unconstrained_reverse_iterator<_BidirectionalIterator> _RBi; - typedef __unconstrained_reverse_iterator _Rv; - typedef __invert<_Compare> _Inverted; - std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff), - _RBi(__middle), _RBi(__first), - _RBi(__last), _Inverted(__comp)); - } +_LIBCPP_HIDE_FROM_ABI 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) { + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; + __destruct_n __d(0); + unique_ptr __h2(__buff, __d); + if (__len1 <= __len2) { + value_type* __p = __buff; + for (_BidirectionalIterator __i = __first; __i != __middle; + __d.template __incr(), (void)++__i, (void)++__p) + ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i)); + std::__half_inplace_merge<_AlgPolicy>(__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(_IterOps<_AlgPolicy>::__iter_move(__i)); + typedef __unconstrained_reverse_iterator<_BidirectionalIterator> _RBi; + typedef __unconstrained_reverse_iterator _Rv; + typedef __invert<_Compare> _Inverted; + std::__half_inplace_merge<_AlgPolicy>( + _Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), _Inverted(__comp)); + } } 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) - { - // if __middle == __last, we're done - if (__len2 == 0) - return; - if (__len1 <= __buff_size || __len2 <= __buff_size) - 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) - { - if (__len1 == 0) - return; - if (__comp(*__middle, *__first)) - break; - } - // __first < __middle < __last - // *__first > *__middle - // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that - // all elements in: - // [__first, __m1) <= [__middle, __m2) - // [__middle, __m2) < [__m1, __middle) - // [__m1, __middle) <= [__m2, __last) - // and __m1 or __m2 is in the middle of its range - _BidirectionalIterator __m1; // "median" of [__first, __middle) - _BidirectionalIterator __m2; // "median" of [__middle, __last) - difference_type __len11; // distance(__first, __m1) - difference_type __len21; // distance(__middle, __m2) - // binary search smaller range - if (__len1 < __len2) - { // __len >= 1, __len2 >= 2 - __len21 = __len2 / 2; - __m2 = __middle; - _Ops::advance(__m2, __len21); - // TODO: replace _ClassicAlgPolicy and __identity with _AlgPolicy and projection - __m1 = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity()); - __len11 = _Ops::distance(__first, __m1); - } - else - { - if (__len1 == 1) - { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 - // It is known *__first > *__middle - _Ops::iter_swap(__first, __middle); - return; - } - // __len1 >= 2, __len2 >= 1 - __len11 = __len1 / 2; - __m1 = __first; - _Ops::advance(__m1, __len11); - __m2 = std::lower_bound(__middle, __last, *__m1, __comp); - __len21 = _Ops::distance(__middle, __m2); - } - difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) - difference_type __len22 = __len2 - __len21; // distance(__m2, __last) - // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) - // swap middle two partitions - // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`. - __middle = _VSTD::rotate(__m1, __middle, __m2); - // __len12 and __len21 now have swapped meanings - // merge smaller range with recursive call and larger with tail recursion elimination - if (__len11 + __len21 < __len12 + __len22) - { - 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; - __len1 = __len12; - __len2 = __len22; - } - else - { - 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; - __len1 = __len11; - __len2 = __len21; - } + 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) { + // if __middle == __last, we're done + if (__len2 == 0) + return; + if (__len1 <= __buff_size || __len2 <= __buff_size) + return std::__buffered_inplace_merge<_AlgPolicy>(__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) { + if (__len1 == 0) + return; + if (__comp(*__middle, *__first)) + break; + } + // __first < __middle < __last + // *__first > *__middle + // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that + // all elements in: + // [__first, __m1) <= [__middle, __m2) + // [__middle, __m2) < [__m1, __middle) + // [__m1, __middle) <= [__m2, __last) + // and __m1 or __m2 is in the middle of its range + _BidirectionalIterator __m1; // "median" of [__first, __middle) + _BidirectionalIterator __m2; // "median" of [__middle, __last) + difference_type __len11; // distance(__first, __m1) + difference_type __len21; // distance(__middle, __m2) + // binary search smaller range + if (__len1 < __len2) { // __len >= 1, __len2 >= 2 + __len21 = __len2 / 2; + __m2 = __middle; + _Ops::advance(__m2, __len21); + // TODO: replace _ClassicAlgPolicy and __identity with _AlgPolicy and projection + __m1 = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity()); + __len11 = _Ops::distance(__first, __m1); + } else { + if (__len1 == 1) { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 + // It is known *__first > *__middle + _Ops::iter_swap(__first, __middle); + return; + } + // __len1 >= 2, __len2 >= 1 + __len11 = __len1 / 2; + __m1 = __first; + _Ops::advance(__m1, __len11); + __m2 = std::lower_bound(__middle, __last, *__m1, __comp); + __len21 = _Ops::distance(__middle, __m2); } + difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) + difference_type __len22 = __len2 - __len21; // distance(__m2, __last) + // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) + // swap middle two partitions + // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`. + __middle = _VSTD::rotate(__m1, __middle, __m2); + // __len12 and __len21 now have swapped meanings + // merge smaller range with recursive call and larger with tail recursion elimination + if (__len11 + __len21 < __len12 + __len22) { + std::__inplace_merge<_AlgPolicy>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); + __first = __middle; + __middle = __m2; + __len1 = __len12; + __len2 = __len22; + } else { + std::__inplace_merge<_AlgPolicy>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); + __last = __middle; + __middle = __m1; + __len1 = __len11; + __len2 = __len21; + } + } +} + +template +_LIBCPP_HIDE_FROM_ABI void __inplace_merge( + _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare&& __comp) { + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; + typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; + difference_type __len1 = _IterOps<_AlgPolicy>::distance(__first, __middle); + difference_type __len2 = _IterOps<_AlgPolicy>::distance(__middle, __last); + difference_type __buf_size = _VSTD::min(__len1, __len2); + // TODO: Remove the use of std::get_temporary_buffer + _LIBCPP_SUPPRESS_DEPRECATED_PUSH + pair __buf = _VSTD::get_temporary_buffer(__buf_size); + _LIBCPP_SUPPRESS_DEPRECATED_POP + unique_ptr __h(__buf.first); + std::__inplace_merge<_AlgPolicy>( + std::move(__first), std::move(__middle), std::move(__last), __comp, __len1, __len2, __buf.first, __buf.second); } template -inline _LIBCPP_INLINE_VISIBILITY -void -inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, - _Compare __comp) -{ - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; - difference_type __len1 = _VSTD::distance(__first, __middle); - difference_type __len2 = _VSTD::distance(__middle, __last); - difference_type __buf_size = _VSTD::min(__len1, __len2); -// TODO: Remove the use of std::get_temporary_buffer -_LIBCPP_SUPPRESS_DEPRECATED_PUSH - pair __buf = _VSTD::get_temporary_buffer(__buf_size); -_LIBCPP_SUPPRESS_DEPRECATED_POP - unique_ptr __h(__buf.first); - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__inplace_merge<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, - __buf.first, __buf.second); +inline _LIBCPP_HIDE_FROM_ABI void inplace_merge( + _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + std::__inplace_merge<_ClassicAlgPolicy>( + std::move(__first), std::move(__middle), std::move(__last), static_cast<_Comp_ref>(__comp)); } template -inline _LIBCPP_INLINE_VISIBILITY -void -inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) -{ - _VSTD::inplace_merge(__first, __middle, __last, - __less::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI void +inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) { + std::inplace_merge(__first, __middle, __last, __less::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_inplace_merge.h b/libcxx/include/__algorithm/ranges_inplace_merge.h --- a/libcxx/include/__algorithm/ranges_inplace_merge.h +++ b/libcxx/include/__algorithm/ranges_inplace_merge.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_RANGES_INPLACE_MERGE_H #include <__algorithm/inplace_merge.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__config> #include <__functional/identity.h> @@ -17,6 +18,7 @@ #include <__functional/ranges_operations.h> #include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> #include <__iterator/projected.h> #include <__iterator/sortable.h> #include <__ranges/access.h> @@ -36,28 +38,38 @@ namespace ranges { namespace __inplace_merge { -struct __fn { + struct __fn { + template + _LIBCPP_HIDE_FROM_ABI static constexpr auto + __inplace_merge_impl(_Iter __first, _Iter __middle, _Sent __last, _Comp&& __comp, _Proj&& __proj) { + auto __last_iter = ranges::next(__middle, __last); + std::__inplace_merge<_RangeAlgPolicy>( + std::move(__first), std::move(__middle), __last_iter, ranges::__make_projected_comp(__comp, __proj)); + return __last_iter; + } - template _Sent, class _Comp = ranges::less, class _Proj = identity> - requires sortable<_Iter, _Comp, _Proj> - _LIBCPP_HIDE_FROM_ABI - _Iter operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__middle; (void)__last; (void)__comp; (void)__proj; - return {}; - } + template < + bidirectional_iterator _Iter, + sentinel_for<_Iter> _Sent, + class _Comp = ranges::less, + class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI _Iter + operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __inplace_merge_impl( + std::move(__first), std::move(__middle), std::move(__last), std::move(__comp), std::move(__proj)); + } - template - requires sortable, _Comp, _Proj> - _LIBCPP_HIDE_FROM_ABI - borrowed_iterator_t<_Range> operator()(_Range&& __range, iterator_t<_Range> __middle, - _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__middle; (void)__comp; (void)__proj; - return {}; - } - -}; + template + requires sortable< + iterator_t<_Range>, + _Comp, + _Proj> _LIBCPP_HIDE_FROM_ABI borrowed_iterator_t<_Range> + operator()(_Range&& __range, iterator_t<_Range> __middle, _Comp __comp = {}, _Proj __proj = {}) const { + return __inplace_merge_impl( + ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__comp), std::move(__proj)); + } + }; } // namespace __inplace_merge 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 @@ -203,7 +203,7 @@ } 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); + std::__inplace_merge<_AlgPolicy>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size); } template diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -803,7 +803,7 @@ set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - + template requires mergeable, iterator_t, O, Comp, Proj1, Proj2> @@ -816,13 +816,13 @@ indirect_strict_weak_order> Comp = ranges::less> constexpr subrange equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 - + template, Proj>> Comp = ranges::less> constexpr borrowed_subrange_t equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20 - + template using set_union_result = in_in_out_result; // since C++20 @@ -847,13 +847,24 @@ ranges::less> constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 - + template, Proj1>, projected, Proj2>> Comp = ranges::less> constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + I inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {}); // Since C++20 + + template + requires sortable, Comp, Proj> + borrowed_iterator_t + inplace_merge(R&& r, iterator_t middle, Comp comp = {}, + Proj proj = {}); // Since C++20 } constexpr bool // constexpr in C++20 @@ -1607,6 +1618,7 @@ #include <__algorithm/ranges_generate.h> #include <__algorithm/ranges_generate_n.h> #include <__algorithm/ranges_includes.h> +#include <__algorithm/ranges_inplace_merge.h> #include <__algorithm/ranges_is_heap.h> #include <__algorithm/ranges_is_heap_until.h> #include <__algorithm/ranges_is_partitioned.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -239,6 +239,7 @@ module __algorithm { module adjacent_find { private header "__algorithm/adjacent_find.h" } + module algorithm_family { private header "__algorithm/algorithm_family.h" } module all_of { private header "__algorithm/all_of.h" } module any_of { private header "__algorithm/any_of.h" } module binary_search { private header "__algorithm/binary_search.h" } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -138,8 +138,8 @@ (void)std::ranges::is_sorted(a, Less(&copies)); assert(copies == 0); (void)std::ranges::is_sorted_until(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::is_sorted_until(a, Less(&copies)); assert(copies == 0); - //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(&copies)); assert(copies == 0); } - //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(&copies)); assert(copies == 0); } (void)std::ranges::lexicographical_compare(first, last, first2, last2, Less(&copies)); assert(copies == 0); (void)std::ranges::lexicographical_compare(a, b, Less(&copies)); assert(copies == 0); (void)std::ranges::lower_bound(first, last, value, Less(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -121,8 +121,8 @@ (void)std::ranges::is_sorted(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::is_sorted_until(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::is_sorted_until(a, Less(), Proj(&copies)); assert(copies == 0); - //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); } - //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(), Proj(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); } + if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(), Proj(&copies)); assert(copies == 0); } (void)std::ranges::lexicographical_compare(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::lexicographical_compare(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::lower_bound(first, last, value, Less(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -37,6 +37,7 @@ // DO NOT MANUALLY EDIT ANYTHING BETWEEN THE MARKERS BELOW // GENERATED-MARKER #include <__algorithm/adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/adjacent_find.h'}} +#include <__algorithm/algorithm_family.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/algorithm_family.h'}} #include <__algorithm/all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/all_of.h'}} #include <__algorithm/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/any_of.h'}} #include <__algorithm/binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/binary_search.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp @@ -27,23 +27,295 @@ #include #include #include +#include #include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template < + class Iter, + class Middle = Iter, + class Sent = sentinel_wrapper>, + class Comp = std::ranges::less, + class Proj = std::identity> +concept HasInplaceMergeIter = + requires(Iter&& iter, Middle&& mid, Sent&& sent, Comp&& comp, Proj&& proj) { + std::ranges::inplace_merge( + std::forward(iter), + std::forward(mid), + std::forward(sent), + std::forward(comp), + std::forward(proj)); + }; + +static_assert(HasInplaceMergeIter); + +// !bidirectional_­iterator +static_assert(!HasInplaceMergeIter); +static_assert(!HasInplaceMergeIter>); + +// !sentinel_for +static_assert(!HasInplaceMergeIter); +static_assert(!HasInplaceMergeIter); + +// !sortable +static_assert(!HasInplaceMergeIter>); +static_assert(!HasInplaceMergeIter); + +template < + class Range, + class Middle = std::ranges::iterator_t, + class Comp = std::ranges::less, + class Proj = std::identity> +concept HasInplaceMergeRange = + requires(Range&& r, Middle&& mid, Comp&& comp, Proj&& proj) { + std::ranges::inplace_merge( + std::forward(r), std::forward(mid), std::forward(comp), std::forward(proj)); + }; + +template +using R = UncheckedRange; + +static_assert(HasInplaceMergeRange, int*>); + +// !bidirectional_range +static_assert(!HasInplaceMergeRange>>); +static_assert(!HasInplaceMergeRange>); + +// !sortable, Comp, Proj> +static_assert(!HasInplaceMergeRange, int*, ComparatorNotCopyable>); +static_assert(!HasInplaceMergeIter, const int*>); + +template class SentWrapper, std::size_t N1, std::size_t N2> +constexpr void testInplaceMergeImpl(std::array input, int midIdx, std::array expected) { + using Sent = SentWrapper; + + // iterator overload + { + auto in = input; + std::same_as decltype(auto) result = + std::ranges::inplace_merge(In{in.data()}, In{in.data() + midIdx}, Sent{In{in.data() + in.size()}}); + assert(std::ranges::equal(in, expected)); + assert(base(result) == in.data() + in.size()); + } + + // range overload + { + auto in = input; + std::ranges::subrange r{In{in.data()}, Sent{In{in.data() + in.size()}}}; + std::same_as decltype(auto) result = std::ranges::inplace_merge(r, In{in.data() + midIdx}); + assert(std::ranges::equal(in, expected)); + assert(base(result) == in.data() + in.size()); + } +} + +template class SentWrapper> +constexpr void testImpl() { + // sorted range + { + std::array in{0, 1, 5, 6, 9, 10}; + std::array expected = in; + testInplaceMergeImpl(in, 3, expected); + } + + // is longer + { + std::array in{0, 5, 9, 15, 18, 22, 2, 4, 6, 10}; + std::array expected = {0, 2, 4, 5, 6, 9, 10, 15, 18, 22}; + testInplaceMergeImpl(in, 6, expected); + } + + // [first, mid) is shorter + { + std::array in{0, 5, 9, 2, 4, 6, 10}; + std::array expected = {0, 2, 4, 5, 6, 9, 10}; + testInplaceMergeImpl(in, 3, expected); + } + + // [first, mid) == [mid, last) + { + std::array in{0, 5, 9, 0, 5, 9}; + std::array expected = {0, 0, 5, 5, 9, 9}; + testInplaceMergeImpl(in, 3, expected); + } + + // duplictes within each range + { + std::array in{1, 5, 5, 2, 9, 9, 9}; + std::array expected = {1, 2, 5, 5, 9, 9, 9}; + testInplaceMergeImpl(in, 3, expected); + } + + // all the same + { + std::array in{5, 5, 5, 5, 5, 5, 5, 5}; + std::array expected = in; + testInplaceMergeImpl(in, 5, expected); + } + + // [first, mid) is empty (mid == begin) + { + std::array in{0, 1, 5, 6, 9, 10}; + std::array expected = in; + testInplaceMergeImpl(in, 0, expected); + } + + // [mid, last] is empty (mid == end) + { + std::array in{0, 1, 5, 6, 9, 10}; + std::array expected = in; + testInplaceMergeImpl(in, 6, expected); + } + + // both empty + { + std::array in{}; + std::array expected = in; + testInplaceMergeImpl(in, 0, expected); + } +} + +template < template class SentWrapper> +constexpr void withAllPermutationsOfIter() { + testImpl, SentWrapper>(); + testImpl, SentWrapper>(); + testImpl, SentWrapper>(); + testImpl(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + withAllPermutationsOfIter(); + withAllPermutationsOfIter(); + + struct Data { + int data; + }; + + const auto equal = [](const Data& x, const Data& y) { return x.data == y.data; }; + // Test custom comparator + { + std::array input{{{4}, {8}, {2}, {5}}}; + std::array expected{{{2}, {4}, {5}, {8}}}; + const auto comp = [](const Data& x, const Data& y) { return x.data < y.data; }; + + // iterator overload + { + auto in = input; + auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 2, in.end(), comp); + assert(std::ranges::equal(in, expected, equal)); + assert(result == in.end()); + } + + // range overload + { + auto in = input; + auto result = std::ranges::inplace_merge(in, in.begin() + 2, comp); + assert(std::ranges::equal(in, expected, equal)); + assert(result == in.end()); + } + } + + // Test custom projection + { + std::array input{{{4}, {8}, {2}, {5}}}; + std::array expected{{{2}, {4}, {5}, {8}}}; + + const auto proj = &Data::data; + + // iterator overload + { + auto in = input; + auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 2, in.end(), {}, proj); + assert(std::ranges::equal(in, expected, equal)); + assert(result == in.end()); + } + + // range overload + { + auto in = input; + auto result = std::ranges::inplace_merge(in, in.begin() + 2, {}, proj); + assert(std::ranges::equal(in, expected, equal)); + assert(result == in.end()); + } + } + + // Remarks: Stable. + { + struct IntAndID { + int data; + int id; + constexpr auto operator<=>(const IntAndID& rhs) const { return data <=> rhs.data; } + constexpr auto operator==(const IntAndID& rhs) const { return data == rhs.data; } + }; + std::array input{{{0, 0}, {1, 0}, {2, 0}, {0, 1}, {1, 1}, {2, 1}}}; + + // iterator overload + { + auto in = input; + auto result = std::ranges::inplace_merge(in.begin(), in.begin() + 3, in.end()); + assert(std::ranges::equal(in, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data)); + assert(std::ranges::equal(in, std::array{0, 1, 0, 1, 0, 1}, {}, &IntAndID::id)); + assert(result == in.end()); + } + + // range overload + { + auto in = input; + auto result = std::ranges::inplace_merge(in, in.begin() + 3); + assert(std::ranges::equal(in, std::array{0, 0, 1, 1, 2, 2}, {}, &IntAndID::data)); + assert(std::ranges::equal(in, std::array{0, 1, 0, 1, 0, 1}, {}, &IntAndID::id)); + assert(result == in.end()); + } + } + + // Complexity + { + std::array input{1, 2, 3, 3, 3, 7, 7, 2, 2, 5, 5, 6, 6}; + std::array expected{1, 2, 2, 2, 3, 3, 3, 5, 5, 6, 6, 7, 7}; + auto mid = 7; + // iterator overload + { + auto in = input; + int numberOfComp = 0; + int numberOfProj = 0; + auto result = std::ranges::inplace_merge( + in.begin(), + in.begin() + mid, + in.end(), + counting_predicate{std::ranges::less{}, numberOfComp}, + counting_projection{numberOfProj}); + assert(std::ranges::equal(in, expected)); + assert(result == in.end()); + // the spec specify exactly N-1 comparison but we actually + // does not invoke as many times as specified + assert(numberOfComp <= static_cast(in.size() - 1)); + assert(numberOfProj <= 2 * numberOfComp); + } + // range overload + { + auto in = input; + int numberOfComp = 0; + int numberOfProj = 0; + auto result = std::ranges::inplace_merge( + in, + in.begin() + mid, + counting_predicate{std::ranges::less{}, numberOfComp}, + counting_projection{numberOfProj}); + assert(std::ranges::equal(in, expected)); + assert(result == in.end()); + assert(numberOfComp <= static_cast(in.size() - 1)); + assert(numberOfProj <= 2 * numberOfComp); + } + } return true; } int main(int, char**) { test(); - static_assert(test()); + // inplace_merge is not constexpr (yet) return 0; } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -193,8 +193,8 @@ dangling_1st(std::ranges::stable_sort, in); dangling_1st(std::ranges::partial_sort, in, mid); dangling_1st(std::ranges::nth_element, in, mid); - //if (!std::is_constant_evaluated()) - // dangling_1st(std::ranges::inplace_merge, in, mid); + if (!std::is_constant_evaluated()) + 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); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp @@ -35,36 +35,36 @@ // Invokes both the (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid. // (in, ...) -template -constexpr void test(Func&& func, Input& in, Args&& ...args) { +template +constexpr void test(Func&& func, Input& in, Args&&... args) { func(in.begin(), in.end(), std::forward(args)...); func(in, std::forward(args)...); } // (in1, in2, ...) -template -constexpr void test(Func&& func, Input& in1, Input& in2, Args&& ...args) { +template +constexpr 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)...); } // (in, mid, ...) -template -constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t mid, Args&& ...args) { +template +constexpr 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)...); } constexpr bool test_all() { - std::array in = {1, 2, 3}; + std::array in = {1, 2, 3}; std::array in2 = {4, 5, 6}; - auto mid = in.begin() + 1; + auto mid = in.begin() + 1; std::array output = {7, 8, 9, 10, 11, 12}; - auto out = output.begin(); - auto out2 = output.begin() + 1; + auto out = output.begin(); + auto out2 = output.begin() + 1; - int x = 2; + int x = 2; int count = 1; test(std::ranges::any_of, in, unary_pred); @@ -133,7 +133,8 @@ test(std::ranges::stable_sort, in, binary_pred); test_mid(std::ranges::partial_sort, in, mid, binary_pred); test_mid(std::ranges::nth_element, in, mid, binary_pred); - //test_mid(std::ranges::inplace_merge, in, mid, binary_pred); + if (!std::is_constant_evaluated()) + test_mid(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); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -36,34 +36,34 @@ // Invokes both the (iterator, sentinel, ...) and the (range, ...) overloads of the given niebloid. // (in, ...) -template -constexpr void test(Func&& func, Input& in, Args&& ...args) { +template +constexpr void test(Func&& func, Input& in, Args&&... args) { func(in.begin(), in.end(), std::forward(args)...); func(in, std::forward(args)...); } // (in1, in2, ...) -template -constexpr void test(Func&& func, Input& in1, Input& in2, Args&& ...args) { +template +constexpr 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)...); } // (in, mid, ...) -template -constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t mid, Args&& ...args) { +template +constexpr 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)...); } constexpr bool test_all() { - std::array in = {Bar{Foo{1}}, Bar{Foo{2}}, Bar{Foo{3}}}; + std::array in = {Bar{Foo{1}}, Bar{Foo{2}}, Bar{Foo{3}}}; std::array in2 = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}}; - auto mid = in.begin() + 1; + auto mid = in.begin() + 1; std::array output = {Bar{Foo{7}}, Bar{Foo{8}}, Bar{Foo{9}}, Bar{Foo{10}}, Bar{Foo{11}}, Bar{Foo{12}}}; - auto out = output.begin(); - auto out2 = output.begin() + 1; + auto out = output.begin(); + auto out2 = output.begin() + 1; Bar a{Foo{1}}; Bar b{Foo{2}}; @@ -162,7 +162,8 @@ test(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val); test_mid(std::ranges::partial_sort, in, mid, &Foo::binary_pred, &Bar::val); test_mid(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val); - //test_mid(std::ranges::inplace_merge, in, mid, binary_pred); + if (!std::is_constant_evaluated()) + test_mid(std::ranges::inplace_merge, in, mid, &Foo::binary_pred, &Bar::val); 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); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -164,6 +164,7 @@ // test(std::ranges::stable_sort, in); test_mid(std::ranges::partial_sort, in, mid); test_mid(std::ranges::nth_element, in, mid); + // TODO(ranges): `inplace_merge` requires `ranges::rotate` to be implemented. //if (!std::is_constant_evaluated()) // test_mid(std::ranges::inplace_merge, in, mid); test(std::ranges::make_heap, in); diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -87,7 +87,7 @@ static_assert(test(std::ranges::generate, a, gen)); static_assert(test(std::ranges::generate_n, a, 10, gen)); static_assert(test(std::ranges::includes, a, a)); -//static_assert(test(std::ranges::inplace_merge, a, a+5)); +static_assert(test(std::ranges::inplace_merge, a, a+5)); static_assert(test(std::ranges::is_heap, a)); static_assert(test(std::ranges::is_heap_until, a)); static_assert(test(std::ranges::is_partitioned, a, odd)); diff --git a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn --- a/llvm/utils/gn/secondary/libcxx/include/BUILD.gn +++ b/llvm/utils/gn/secondary/libcxx/include/BUILD.gn @@ -69,6 +69,7 @@ copy("copy_headers") { sources = [ "__algorithm/adjacent_find.h", + "__algorithm/algorithm_family.h", "__algorithm/all_of.h", "__algorithm/any_of.h", "__algorithm/binary_search.h",