[libc++][ranges] Implement `ranges::remove_copy{, _if}`.

[huixie90]

• finalise ranges::remove_copy{_if}
• fixed a bug where ranges::remove_copy_if got the predicate inverted
• enabled all the "robust" tests
• added tests for ranges::remove_copy_if

[var-const]

libcxx/include/algorithm

832

Missing the definition of remove_copy_result.

libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp

48

Needs tests for indirectly_copyable and indirect_binary_predicate.

175

Need to count invocations of the predicate as well.

libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy_if.pass.cpp

61 ↗

(On Diff #448352)

This should be made consistent with the other test file.

223 ↗

(On Diff #448352)

These two files should ideally be almost mirror versions of each other.

[var-const]

Address the existing feedback and rebase on main.

libcxx/include/__algorithm/ranges_remove_copy.h

 //===----------------------------------------------------------------------===//
 //
 // 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_REMOVE_COPY_H
 #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)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
 template <class _InIter, class _OutIter>
 using remove_copy_result = in_out_result<_InIter, _OutIter>;
 
 namespace __remove_copy {
 
   struct __fn {
-
-  template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, class _Type,
+    template <input_iterator _InIter,
+              sentinel_for<_InIter> _Sent,
+              weakly_incrementable _OutIter,
+              class _Type,
               class _Proj = identity>
       requires indirectly_copyable<_InIter, _OutIter> &&
                indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type*>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  remove_copy_result<_InIter, _OutIter>
+    _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 {};
+      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 <input_range _Range, weakly_incrementable _OutIter, class _Type, class _Proj = identity>
       requires indirectly_copyable<iterator_t<_Range>, _OutIter> &&
                indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  remove_copy_result<borrowed_iterator_t<_Range>, _OutIter>
+    _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_result<borrowed_iterator_t<_Range>, _OutIter>
     operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__result; (void)__value; (void)__proj;
-    return {};
+      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
 
 inline namespace __cpo {
   inline constexpr auto remove_copy = __remove_copy::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_REMOVE_COPY_H

libcxx/include/__algorithm/ranges_remove_copy_if.h

 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
 template <class _InIter, class _OutIter>
 using remove_copy_if_result = in_out_result<_InIter, _OutIter>;
 
+template <class _InIter, class _Sent, class _OutIter, class _Proj, class _Pred>
+_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)};
+}
+
 namespace __remove_copy_if {
 
   struct __fn {
-
-  template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter,
-            class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred>
+    template <input_iterator _InIter,
+              sentinel_for<_InIter> _Sent,
+              weakly_incrementable _OutIter,
+              class _Proj = identity,
+              indirect_unary_predicate<projected<_InIter, _Proj>> _Pred>
       requires indirectly_copyable<_InIter, _OutIter>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  remove_copy_if_result<_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 {};
+      return ranges::__remove_copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj);
     }
 
-  template <input_range _Range, weakly_incrementable _OutIter, class _Proj = identity,
+    template <input_range _Range,
+              weakly_incrementable _OutIter,
+              class _Proj = identity,
               indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
       requires indirectly_copyable<iterator_t<_Range>, _OutIter>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  remove_copy_if_result<borrowed_iterator_t<_Range>, _OutIter>
+    _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _OutIter>
     operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__result; (void)__pred; (void)__proj;
-    return {};
+      return ranges::__remove_copy_if_impl(
+          ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __proj);
     }
-
   };
 
 } // namespace __remove_copy_if
 
 inline namespace __cpo {
   inline constexpr auto remove_copy_if = __remove_copy_if::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_REMOVE_COPY_IF_H

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_symmetric_difference_result<I1, I2, O>
       set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                                Comp comp = {}, Proj1 proj1 = {},
                                Proj2 proj2 = {});                                                   // since C++20
-  
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_symmetric_difference_result<borrowed_iterator_t<R1>,
                                                       borrowed_iterator_t<R2>, O>
       set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
                                Proj1 proj1 = {}, Proj2 proj2 = {});                                 // since C++20
 
   template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
     constexpr subrange<I>
       equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});                 // since C++20
-  
   template<forward_range R, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
              ranges::less>
     constexpr borrowed_subrange_t<R>
       equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});                           // since C++20
-  
   template<class I1, class I2, class O>
     using set_union_result = in_in_out_result<I1, I2, O>;                                           // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_union_result<I1, I2, O>
       set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
 
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            class Proj1 = identity, class Proj2 = identity,
            indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
              ranges::less>
     constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
-  
   template<input_range R1, input_range R2, class Proj1 = identity,
            class Proj2 = identity,
            indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
                                       projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
     constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
+
+  template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T,
+           class Proj = identity>
+             indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+    constexpr remove_copy_result<I, O>
+      remove_copy(I first, S last, O result, const T& value, Proj proj = {});                      // Since C++20
+
+  template<input_range R, weakly_incrementable O, class T, class Proj = identity>
+    requires indirectly_copyable<iterator_t<R>, O> &&
+             indirect_binary_predicate<ranges::equal_to,
+                                       projected<iterator_t<R>, Proj>, const T*>
+    constexpr remove_copy_result<borrowed_iterator_t<R>, O>
+      remove_copy(R&& r, O result, const T& value, Proj proj = {});                                // Since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_nth_element.h>
 #include <__algorithm/ranges_partial_sort.h>
 #include <__algorithm/ranges_partition.h>
 #include <__algorithm/ranges_partition_copy.h>
 #include <__algorithm/ranges_partition_point.h>
 #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>
 #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>

libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp

 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+template <class Iter, class Sent = sentinel_wrapper<Iter>, class OutIter = int*>
+concept HasRemoveCopyIt =
+    requires(Iter first, Sent last, OutIter result) { std::ranges::remove_copy(first, last, result, 0); };
+
+static_assert(HasRemoveCopyIt<int*>);
+static_assert(!HasRemoveCopyIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasRemoveCopyIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasRemoveCopyIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasRemoveCopyIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasRemoveCopyIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasRemoveCopyIt<int*, int*, OutputIteratorNotIndirectlyWritable>);
+static_assert(!HasRemoveCopyIt<int*, int*, OutputIteratorNotInputOrOutputIterator>);
+
+template <class Range, class OutIter = int*>
+concept HasRemoveCopyR = requires(Range range, OutIter result) { std::ranges::remove_copy(range, result, 0); };
+
+static_assert(HasRemoveCopyR<UncheckedRange<int*>>);
+static_assert(!HasRemoveCopyR<InputRangeNotDerivedFrom>);
+static_assert(!HasRemoveCopyR<InputRangeNotIndirectlyReadable>);
+static_assert(!HasRemoveCopyR<InputRangeNotInputOrOutputIterator>);
+static_assert(!HasRemoveCopyR<InputRangeNotSentinelSemiregular>);
+static_assert(!HasRemoveCopyR<InputRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasRemoveCopyR<UncheckedRange<int*>, OutputIteratorNotIndirectlyWritable>);
+static_assert(!HasRemoveCopyR<UncheckedRange<int*>, OutputIteratorNotInputOrOutputIterator>);
+
+template <int N, int M>
+struct Data {
+  std::array<int, N> input;
+  std::array<int, M> expected;
+  int val;
+};
+
+template <class InIter, class Sent, class OutIter, int N, int M>
+constexpr void test(Data<N, M> d) {
+  { // iterator overload
+    std::array<int, M> output;
+
+    std::same_as<std::ranges::in_out_result<InIter, OutIter>> 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<int, M> output;
+    auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())));
+
+    std::same_as<std::ranges::in_out_result<InIter, OutIter>> 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 <class Iter, class Sent, class OutIter>
+constexpr void tests() {
+  // simple test
+  test<Iter, Sent, OutIter, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5});
+  // empty range
+  test<Iter, Sent, OutIter, 0, 0>({});
+  // single element range - match
+  test<Iter, Sent, OutIter, 1, 0>({.input = {1}, .expected = {}, .val = 1});
+  // single element range - no match
+  test<Iter, Sent, OutIter, 1, 1>({.input = {1}, .expected = {1}, .val = 2});
+  // two element range - same order
+  test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2});
+  // two element range - reversed order
+  test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1});
+  // all elements match
+  test<Iter, Sent, OutIter, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1});
+  // the relative order of elements isn't changed
+  test<Iter, Sent, OutIter, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2});
+}
+
+template <class InIter, class Sent>
+constexpr void test_output_iterators() {
+  tests<InIter, Sent, cpp17_output_iterator<int*>>();
+  tests<InIter, Sent, forward_iterator<int*>>();
+  tests<InIter, Sent, bidirectional_iterator<int*>>();
+  tests<InIter, Sent, random_access_iterator<int*>>();
+  tests<InIter, Sent, contiguous_iterator<int*>>();
+  tests<InIter, Sent, int*>();
+}
+
+template <class Iter>
+constexpr void test_sentinels() {
+  test_output_iterators<Iter, Iter>();
+  test_output_iterators<Iter, sentinel_wrapper<Iter>>();
+  test_output_iterators<Iter, sized_sentinel<Iter>>();
+}
 
 constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+  test_output_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_output_iterators<cpp17_input_iterator<int*>, sized_sentinel<cpp17_input_iterator<int*>>>();
+  test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_output_iterators<cpp20_input_iterator<int*>, sized_sentinel<cpp20_input_iterator<int*>>>();
+  test_sentinels<forward_iterator<int*>>();
+  test_sentinels<bidirectional_iterator<int*>>();
+  test_sentinels<random_access_iterator<int*>>();
+  test_sentinels<contiguous_iterator<int*>>();
+  test_sentinels<int*>();
+
+  { // 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;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }