diff --git a/libcxx/include/__algorithm/ranges_remove_copy.h b/libcxx/include/__algorithm/ranges_remove_copy.h --- a/libcxx/include/__algorithm/ranges_remove_copy.h +++ b/libcxx/include/__algorithm/ranges_remove_copy.h @@ -10,19 +10,16 @@ #define _LIBCPP___ALGORITHM_RANGES_REMOVE_COPY_H #include <__algorithm/in_out_result.h> -#include <__algorithm/make_projected.h> -#include <__algorithm/remove_copy.h> +#include <__algorithm/ranges_remove_copy_if.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> #include <__functional/ranges_operations.h> #include <__iterator/concepts.h> -#include <__iterator/iterator_traits.h> #include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> -#include <__utility/forward.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -40,32 +37,30 @@ namespace __remove_copy { -struct __fn { - - template _Sent, weakly_incrementable _OutIter, class _Type, - class _Proj = identity> - requires indirectly_copyable<_InIter, _OutIter> && - indirect_binary_predicate, const _Type*> - _LIBCPP_HIDE_FROM_ABI constexpr - remove_copy_result<_InIter, _OutIter> - operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result; (void)__value; (void)__proj; - return {}; - } - - template - requires indirectly_copyable, _OutIter> && - indirect_binary_predicate, _Proj>, const _Type*> - _LIBCPP_HIDE_FROM_ABI constexpr - remove_copy_result, _OutIter> - operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__value; (void)__proj; - return {}; - } - -}; + struct __fn { + template _Sent, + weakly_incrementable _OutIter, + class _Type, + class _Proj = identity> + requires indirectly_copyable<_InIter, _OutIter> && + indirect_binary_predicate, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __val) { return __value != __val; }; + return ranges::__remove_copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj); + } + + template + requires indirectly_copyable, _OutIter> && + indirect_binary_predicate, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_result, _OutIter> + operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __val) { return __value != __val; }; + return ranges::__remove_copy_if_impl( + ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __proj); + } + }; } // namespace __remove_copy diff --git a/libcxx/include/__algorithm/ranges_remove_copy_if.h b/libcxx/include/__algorithm/ranges_remove_copy_if.h --- a/libcxx/include/__algorithm/ranges_remove_copy_if.h +++ b/libcxx/include/__algorithm/ranges_remove_copy_if.h @@ -38,33 +38,43 @@ template using remove_copy_if_result = in_out_result<_InIter, _OutIter>; -namespace __remove_copy_if { - -struct __fn { - - template _Sent, weakly_incrementable _OutIter, - class _Proj = identity, indirect_unary_predicate> _Pred> - requires indirectly_copyable<_InIter, _OutIter> - _LIBCPP_HIDE_FROM_ABI constexpr - remove_copy_if_result<_InIter, _OutIter> - operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result; (void)__pred; (void)__proj; - return {}; +template +_LIBCPP_HIDE_FROM_ABI constexpr in_out_result<_InIter, _OutIter> +__remove_copy_if_impl(_InIter __first, _Sent __last, _OutIter __result, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) { + *__result = *__first; + ++__result; + } } + return {std::move(__first), std::move(__result)}; +} - template , _Proj>> _Pred> - requires indirectly_copyable, _OutIter> - _LIBCPP_HIDE_FROM_ABI constexpr - remove_copy_if_result, _OutIter> - operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__pred; (void)__proj; - return {}; - } +namespace __remove_copy_if { -}; + struct __fn { + template _Sent, + weakly_incrementable _OutIter, + class _Proj = identity, + indirect_unary_predicate> _Pred> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_if_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj); + } + + template , _Proj>> _Pred> + requires indirectly_copyable, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_if_result, _OutIter> + operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_copy_if_impl( + ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __proj); + } + }; } // namespace __remove_copy_if diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -774,7 +774,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> @@ -787,13 +787,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 @@ -818,13 +818,27 @@ 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, weakly_incrementable O, class T, + class Proj = identity> + indirect_binary_predicate, const T*> + constexpr remove_copy_result + remove_copy(I first, S last, O result, const T& value, Proj proj = {}); // Since C++20 + + template + requires indirectly_copyable, O> && + indirect_binary_predicate, Proj>, const T*> + constexpr remove_copy_result, O> + remove_copy(R&& r, O result, const T& value, Proj proj = {}); // Since C++20 + } constexpr bool // constexpr in C++20 @@ -1601,6 +1615,8 @@ #include <__algorithm/ranges_pop_heap.h> #include <__algorithm/ranges_push_heap.h> #include <__algorithm/ranges_remove.h> +#include <__algorithm/ranges_remove_copy.h> +#include <__algorithm/ranges_remove_copy_if.h> #include <__algorithm/ranges_remove_if.h> #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp @@ -34,12 +34,143 @@ #include "almost_satisfies_types.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template , class OutIter = int*> +concept HasRemoveCopyIt = + requires(Iter first, Sent last, OutIter result) { std::ranges::remove_copy(first, last, result, 0); }; + +static_assert(HasRemoveCopyIt); +static_assert(!HasRemoveCopyIt); +static_assert(!HasRemoveCopyIt); +static_assert(!HasRemoveCopyIt); +static_assert(!HasRemoveCopyIt); +static_assert(!HasRemoveCopyIt); +static_assert(!HasRemoveCopyIt); +static_assert(!HasRemoveCopyIt); + +template +concept HasRemoveCopyR = requires(Range range, OutIter result) { std::ranges::remove_copy(range, result, 0); }; + +static_assert(HasRemoveCopyR>); +static_assert(!HasRemoveCopyR); +static_assert(!HasRemoveCopyR); +static_assert(!HasRemoveCopyR); +static_assert(!HasRemoveCopyR); +static_assert(!HasRemoveCopyR); +static_assert(!HasRemoveCopyR, OutputIteratorNotIndirectlyWritable>); +static_assert(!HasRemoveCopyR, OutputIteratorNotInputOrOutputIterator>); + +template +struct Data { + std::array input; + std::array expected; + int val; +}; + +template +constexpr void test(Data d) { + { // iterator overload + std::array output; + + std::same_as> decltype(auto) ret = std::ranges::remove_copy( + InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())), OutIter(output.data()), d.val); + + assert(base(ret.in) == d.input.data() + N); + assert(base(ret.out) == output.data() + M); + assert(d.expected == output); + } + + { // range overload + std::array output; + auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size()))); + + std::same_as> decltype(auto) ret = + std::ranges::remove_copy(range, OutIter(output.data()), d.val); + + assert(base(ret.in) == d.input.data() + N); + assert(base(ret.out) == output.data() + M); + assert(d.expected == output); + } +} + +template +constexpr void tests() { + // simple test + test({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5}); + // empty range + test({}); + // single element range - match + test({.input = {1}, .expected = {}, .val = 1}); + // single element range - no match + test({.input = {1}, .expected = {1}, .val = 2}); + // two element range - same order + test({.input = {1, 2}, .expected = {1}, .val = 2}); + // two element range - reversed order + test({.input = {1, 2}, .expected = {2}, .val = 1}); + // all elements match + test({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1}); + // the relative order of elements isn't changed + test({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2}); +} + +template +constexpr void test_output_iterators() { + tests>(); + tests>(); + tests>(); + tests>(); + tests>(); + tests(); +} + +template +constexpr void test_sentinels() { + test_output_iterators(); + test_output_iterators>(); + test_output_iterators>(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_output_iterators, sentinel_wrapper>>(); + test_output_iterators, sized_sentinel>>(); + test_output_iterators, sentinel_wrapper>>(); + test_output_iterators, sized_sentinel>>(); + test_sentinels>(); + test_sentinels>(); + test_sentinels>(); + test_sentinels>(); + test_sentinels(); + + { // check that passing a different type works + struct S { + constexpr operator int() const { return 3; } + }; + { // iterator overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{}); + } + { // range overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(a, std::begin(b), S{}); + } + } + + { // check that a custom projection works + struct S { + constexpr operator int() const { return 3; } + }; + { // iterator overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{}); + } + { // range overload + int a[] = {1, 2, 3, 4}; + int b[3]; + std::ranges::remove_copy(a, std::begin(b), S{}); + } + } return true; }