[libc++] Implement ranges::remove{, _if}

[huixie90]

libcxx/include/__algorithm/ranges_remove_if.h

37

By having an impl function, you can save 2 moves of pred and proj of the range overload, at the cost of having 2 extra moves of iterator/sentinel for iterator overload. is it worth it? sometimes moving iterators can be expensive, especially for iterators in the range adaptor (e.g. zip iterator)

[var-const]

libcxx/include/CMakeLists.txt

98

Please update the status page, the module map, and the private headers test file.

libcxx/include/__algorithm/ranges_remove.h

38

Nit: please move the iterators.

libcxx/include/__algorithm/ranges_remove_if.h

38

I found the name __end a little confusing -- it's not obvious how it is different from __last. How about new_end or similar?

libcxx/include/algorithm

1290

Please add synopsis.

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

17

Nit: wrong synopsis.

48

remove_if.

54

Please also check permutable.

66

Please add brief comments to explain what is being tested.

70

Optional: consider using some intermediate variables to make this expression a little easier to parse.

92

Can you please add a more complicated test case that contains the following?

• two or more matching elements in a row;
• a matching element followed by a non-matching element;
• a matching element followed by several non-matching elements?

Also might be worthwhile to check both the case where the last element in the range matches and the case when it doesn't match.

93

It's not obvious from the name val that the predicate is < val -- perhaps name it max, cutoff{,_point} or similar?

102

Nit: s/matche/match/.

102

How about also No elements match? (for a non-trivial case with several elements)

132

Nit: weird formatting.

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_remove_if.h

37

I'd keep it for now as-is, but I think we want to review the stance on moving the iterators. I don't think anybody had zip_view and friends in mind when we decided to take the iterators by value.

38

I think __new_end could also be a bit confusing, but definitely better than __end.

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

54

That's done in lines 50 and 51, or am I missing something?

66

What exactly are you asking for? Something like check that the expected outcome is the actual outcome isn't exactly useful, but I don't think there is anything more specific I could say.

[var-const]

libcxx/include/module.modulemap.in

345

Do you also need to add remove_if?

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

66

Basically I meant something like // Iterator overload, // Range overload.

144

Nit: can you add a little bit more context in addition to the link?

[philnik]

• Address comments

[philnik]

• Fix CI

libcxx/docs/Status/RangesAlgorithms.csv

 Write,unique_copy,Not assigned,n/a,Not started
 Write,partition_copy,Not assigned,n/a,Not started
 Write,partial_sort_copy,Not assigned,n/a,Not started
 Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅
 Merge,set_difference,Hui Xie,n/a,Not started
 Merge,set_intersection,Hui Xie,n/a,Not started
 Merge,set_symmetric_difference,Hui Xie,n/a,Not started
 Merge,set_union,Not assigned,Hui Xie,Not started
-Permutation,remove,Not assigned,n/a,Not started
-Permutation,remove_if,Not assigned,n/a,Not started
+Permutation,remove,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`,✅
+Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`,✅
 Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
 Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review
 Permutation,shuffle,Not assigned,n/a,Not started
 Permutation,unique,Not assigned,n/a,Not started
 Permutation,partition,Not assigned,n/a,Not started
 Permutation,stable_partition,Not assigned,n/a,Not started
 Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅
 Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_is_partitioned.h
   __algorithm/ranges_is_sorted.h
   __algorithm/ranges_is_sorted_until.h
   __algorithm/ranges_lexicographical_compare.h
   __algorithm/ranges_lower_bound.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_merge.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_move.h
   __algorithm/ranges_move_backward.h
   __algorithm/ranges_none_of.h
+  __algorithm/ranges_remove.h
+  __algorithm/ranges_remove_if.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_sort.h
   __algorithm/ranges_stable_sort.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h

libcxx/include/__algorithm/ranges_remove.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_H
+#define _LIBCPP___ALGORITHM_RANGES_REMOVE_H
+#include <__config>
+
+#include <__algorithm/ranges_remove_if.h>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/permutable.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.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 __remove {
+struct __fn {
+
+  template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  subrange<_Iter> operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const {
+    auto __pred = [&](auto&& __other) { return __value == __other; };
+    return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+  }
+
+  template <forward_range _Range, class _Type, class _Proj = identity>
+    requires permutable<iterator_t<_Range>>
+          && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_subrange_t<_Range> operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) const {
+    auto __pred = [&](auto&& __other) { return __value == __other; };
+    return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
+  }
+};
+} // namespace __remove
+
+inline namespace __cpo {
+  inline constexpr auto remove = __remove::__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_H

libcxx/include/__algorithm/ranges_remove_if.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_IF_H
+#define _LIBCPP___ALGORITHM_RANGES_REMOVE_IF_H
+#include <__config>
+
+#include <__algorithm/ranges_find_if.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iter_move.h>
+#include <__iterator/permutable.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.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 {
+
+template <class _Iter, class _Sent, class _Proj, class _Pred>
+_LIBCPP_HIDE_FROM_ABI constexpr
+subrange<_Iter> __remove_if_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) {
+  auto __new_end = ranges::__find_if_impl(__first, __last, __pred, __proj);
+  if (__new_end == __last)
+    return {__new_end, __new_end};
+
+  _Iter __i = __new_end;
+  while (++__i != __last) {
+    if (!std::invoke(__pred, std::invoke(__proj, *__i))) {
+      *__new_end = ranges::iter_move(__i);
+      ++__new_end;
+    }
+  }
+  return {__new_end, __i};
+}
+
+namespace __remove_if {
+struct __fn {
+
+  template <permutable _Iter, sentinel_for<_Iter> _Sent,
+            class _Proj = identity,
+            indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const {
+    return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+  }
+
+  template <forward_range _Range,
+            class _Proj = identity,
+            indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
+    requires permutable<iterator_t<_Range>>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const {
+    return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
+  }
+
+};
+} // namespace __remove_if
+
+inline namespace __cpo {
+  inline constexpr auto remove_if = __remove_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_IF_H

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
 
   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 merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       merge(R1&& r1, R2&& r2, O result,
             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                                    // since C++20
 
+  template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+    constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});          // since C++20
+
+  template<forward_range R, class T, class Proj = identity>
+    requires permutable<iterator_t<R>> &&
+             indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+    constexpr borrowed_subrange_t<R>
+      ranges::remove(R&& r, const T& value, Proj proj = {});                                        // since C++20
+
+  template<permutable I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});            // since C++20
+
+  template<forward_range R, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires permutable<iterator_t<R>>
+    constexpr borrowed_subrange_t<R>
+      ranges::remove_if(R&& r, Pred pred, 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_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_merge.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
+#include <__algorithm/ranges_remove.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_sort.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_min                      { private header "__algorithm/ranges_min.h" }
       module ranges_min_element              { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax                   { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element           { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch                 { private header "__algorithm/ranges_mismatch.h" }
       module ranges_move                     { private header "__algorithm/ranges_move.h" }
       module ranges_move_backward            { private header "__algorithm/ranges_move_backward.h" }
       module ranges_none_of                  { private header "__algorithm/ranges_none_of.h" }
+      module ranges_remove                   { private header "__algorithm/ranges_remove.h" }
+      module ranges_remove_if                { private header "__algorithm/ranges_remove_if.h" }
       module ranges_replace                  { private header "__algorithm/ranges_replace.h" }
       module ranges_replace_if               { private header "__algorithm/ranges_replace_if.h" }
       module ranges_reverse                  { private header "__algorithm/ranges_reverse.h" }
       module ranges_sort                     { private header "__algorithm/ranges_sort.h" }
       module ranges_stable_sort              { private header "__algorithm/ranges_stable_sort.h" }
       module ranges_swap_ranges              { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform                { private header "__algorithm/ranges_transform.h" }
       module ranges_upper_bound              { private header "__algorithm/ranges_upper_bound.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     //(void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::remove_if(a, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::remove_if(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0);
     (void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0);
     (void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(a, first2, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::remove(first, last, value, Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::remove(a, value, Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::remove_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::remove_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::remove(first, last, value, Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::remove(a, value, Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::remove_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::remove_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy(first, last, first2, value, T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy(a, first2, value, T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::replace(first, last, value, T(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::replace(a, value, T(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::replace_if(first, last, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::replace_if(a, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
 #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
+#include <__algorithm/ranges_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.h'}}
+#include <__algorithm/ranges_remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_if.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
 #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}

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

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
+//   requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+//   constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});
+// template<forward_range R, class T, class Proj = identity>
+//   requires permutable<iterator_t<R>> &&
+//            indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+//   constexpr borrowed_subrange_t<R>
+//     ranges::remove(R&& r, const T& value, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasRemoveIt = requires(Iter first, Sent last) { std::ranges::remove(first, last, 0); };
+
+static_assert(HasRemoveIt<int*>);
+static_assert(!HasRemoveIt<PermutableNotForwardIterator>);
+static_assert(!HasRemoveIt<PermutableNotSwappable>);
+static_assert(!HasRemoveIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasRemoveIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasRemoveIt<int**>); // not indirect_binary_prediacte
+
+template <class Range>
+concept HasRemoveR = requires(Range range) { std::ranges::remove(range, 0); };
+
+static_assert(HasRemoveR<UncheckedRange<int*>>);
+static_assert(!HasRemoveR<PermutableRangeNotForwardIterator>);
+static_assert(!HasRemoveR<PermutableRangeNotSwappable>);
+static_assert(!HasRemoveR<SentinelForNotSemiregular>);
+static_assert(!HasRemoveR<SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasRemoveR<UncheckedRange<int**>>); // not indirect_binary_prediacte
+
+template <int N, int M>
+struct Data {
+  std::array<int, N> input;
+  std::array<int, M> expected;
+  int val;
+};
+
+template <class Iter, class Sent, int N, int M>
+constexpr void test(Data<N, M> d) {
+  { // iterator overload
+    auto input = d.input;
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret =
+        std::ranges::remove(Iter(input.data()), Sent(Iter(input.data() + input.size())), d.val);
+
+    assert(base(ret.begin()) == input.data() + M);
+    assert(base(ret.end()) == input.data() + N);
+    assert(std::ranges::equal(input.begin(), base(ret.begin()), d.expected.begin(), d.expected.end()));
+  }
+
+  { // range overload
+    auto input = d.input;
+    auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size())));
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove(range, d.val);
+
+    assert(base(ret.begin()) == input.data() + M);
+    assert(base(ret.end()) == input.data() + N);
+    assert(std::ranges::equal(base(input.begin()), base(ret.begin()), d.expected.begin(), d.expected.end()));
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void tests() {
+  // simple test
+  test<Iter, Sent, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5});
+  // empty range
+  test<Iter, Sent, 0, 0>({});
+  // single element range - match
+  test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .val = 1});
+  // single element range - no match
+  test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .val = 2});
+  // two element range - same order
+  test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2});
+  // two element range - reversed order
+  test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1});
+  // all elements match
+  test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1});
+  // the relative order of elements isn't changed
+  test<Iter, Sent, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2});
+}
+
+template <class Iter>
+constexpr void test_sentinels() {
+  tests<Iter, Iter>();
+  tests<Iter, sentinel_wrapper<Iter>>();
+  tests<Iter, sized_sentinel<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_sentinels<forward_iterator<int*>>();
+  test_sentinels<bidirectional_iterator<int*>>();
+  test_sentinels<random_access_iterator<int*>>();
+  test_sentinels<contiguous_iterator<int*>>();
+  test_sentinels<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // check that ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::remove(std::array{1, 2, 3, 4}, 1);
+  }
+
+  { // check complexity requirements
+    struct CompCounter {
+      int* comp_count;
+
+      constexpr bool operator==(const CompCounter&) const {
+        ++*comp_count;
+        return false;
+      }
+    };
+    {
+      int proj_count = 0;
+      auto proj      = [&](CompCounter i) {
+        ++proj_count;
+        return i;
+      };
+      int comp_count = 0;
+
+      CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}};
+      auto ret        = std::ranges::remove(std::begin(a), std::end(a), CompCounter{&comp_count}, proj);
+      assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
+      assert(comp_count == 4);
+      assert(proj_count == 4);
+    }
+    {
+      int proj_count = 0;
+      auto proj      = [&](CompCounter i) {
+        ++proj_count;
+        return i;
+      };
+      int comp_count = 0;
+
+      CompCounter a[] = {{&comp_count}, {&comp_count}, {&comp_count}, {&comp_count}};
+      auto ret        = std::ranges::remove(a, CompCounter{&comp_count}, proj);
+      assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
+      assert(comp_count == 4);
+      assert(proj_count == 4);
+    }
+  }
+
+  { // check that std::invoke is used
+    struct S {
+      constexpr S& identity() { return *this; }
+      bool operator==(const S&) const = default;
+    };
+    {
+      S a[4]   = {};
+      auto ret = std::ranges::remove(std::begin(a), std::end(a), S{}, &S::identity);
+      assert(ret.begin() == std::begin(a));
+      assert(ret.end() == std::end(a));
+    }
+    {
+      S a[4]   = {};
+      auto ret = std::ranges::remove(a, S{}, &S::identity);
+      assert(ret.begin() == std::begin(a));
+      assert(ret.end() == std::end(a));
+    }
+  }
+
+  {
+    // check that the implicit conversion to bool works
+    {
+      StrictComparable<int> a[] = {1, 2, 3, 4};
+      auto ret                  = std::ranges::remove(a, a + 4, StrictComparable<int>{2});
+      assert(ret.begin() == a + 3);
+    }
+    {
+      StrictComparable<int> a[] = {1, 2, 3, 4};
+      auto ret                  = std::ranges::remove(a, StrictComparable<int>{2});
+      assert(ret.begin() == a + 3);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

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

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<permutable I, sentinel_for<I> S, class Proj = identity,
+//          indirect_unary_predicate<projected<I, Proj>> Pred>
+//   constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});
+// template<forward_range R, class Proj = identity,
+//          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+//   requires permutable<iterator_t<R>>
+//   constexpr borrowed_subrange_t<R>
+//     ranges::remove_if(R&& r, Pred pred, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+struct FalsePredicate {
+  bool operator()(int) { return false; }
+};
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasRemoveIfIt = requires(Iter first, Sent last) { std::ranges::remove_if(first, last, FalsePredicate{}); };
+
+static_assert(HasRemoveIfIt<int*>);
+static_assert(!HasRemoveIfIt<PermutableNotForwardIterator>);
+static_assert(!HasRemoveIfIt<PermutableNotSwappable>);
+static_assert(!HasRemoveIfIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasRemoveIfIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasRemoveIfIt<int**>); // not indirect_unary_predicate
+
+template <class Range>
+concept HasRemoveIfR = requires(Range range) { std::ranges::remove_if(range, FalsePredicate{}); };
+
+static_assert(HasRemoveIfR<UncheckedRange<int*>>);
+static_assert(!HasRemoveIfR<PermutableRangeNotForwardIterator>);
+static_assert(!HasRemoveIfR<PermutableRangeNotSwappable>);
+static_assert(!HasRemoveIfR<SentinelForNotSemiregular>);
+static_assert(!HasRemoveIfR<SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasRemoveIfR<UncheckedRange<int**>>); // not indirect_unary_predicate
+
+template <int N, int M>
+struct Data {
+  std::array<int, N> input;
+  std::array<int, M> expected;
+  int cutoff;
+};
+
+template <class Iter, class Sent, int N, int M>
+constexpr void test(Data<N, M> d) {
+  { // iterator overload
+    auto input = d.input;
+
+    auto first = Iter(input.data());
+    auto last  = Sent(Iter(input.data() + input.size()));
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret =
+        std::ranges::remove_if(std::move(first), std::move(last), [&](int i) { return i < d.cutoff; });
+
+    assert(base(ret.begin()) == input.data() + M);
+    assert(base(ret.end()) == input.data() + N);
+    assert(std::ranges::equal(input.data(), base(ret.begin()), d.expected.begin(), d.expected.end()));
+  }
+
+  { // range overload
+    auto input = d.input;
+    auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size())));
+
+    std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove_if(range, [&](int i) {
+      return i < d.cutoff;
+    });
+
+    assert(base(ret.begin()) == input.data() + M);
+    assert(base(ret.end()) == input.data() + N);
+    assert(std::ranges::equal(base(input.begin()), base(ret.begin()), d.expected.begin(), d.expected.end()));
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void tests() {
+  // simple test
+  test<Iter, Sent, 6, 2>({.input = {1, 2, 3, 4, 5, 6}, .expected = {5, 6}, .cutoff = 5});
+  // empty range
+  test<Iter, Sent, 0, 0>({});
+  // single element range - no match
+  test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .cutoff = 1});
+  // single element range - match
+  test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .cutoff = 2});
+  // two element range
+  test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .cutoff = 2});
+  // all elements match
+  test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .cutoff = 2});
+  // no elements match
+  test<Iter, Sent, 5, 5>({.input = {1, 1, 1, 1, 1}, .expected = {1, 1, 1, 1, 1}, .cutoff = 0});
+  // the relative order of elements isn't changed
+  test<Iter, Sent, 8, 7>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {2, 3, 2, 3, 4, 2, 5}, .cutoff = 2});
+  // multiple matches in a row
+  test<Iter, Sent, 5, 3>({.input = {1, 2, 2, 2, 1}, .expected = {2, 2, 2}, .cutoff = 2});
+  // only the last element matches
+  test<Iter, Sent, 3, 2>({.input = {2, 2, 1}, .expected = {2, 2}, .cutoff = 2});
+  // only the last element doesn't match
+  test<Iter, Sent, 3, 1>({.input = {1, 1, 2}, .expected = {2}, .cutoff = 2});
+}
+
+template <class Iter>
+constexpr void test_sentinels() {
+  tests<Iter, Iter>();
+  tests<Iter, sentinel_wrapper<Iter>>();
+  tests<Iter, sized_sentinel<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_sentinels<forward_iterator<int*>>();
+  test_sentinels<bidirectional_iterator<int*>>();
+  test_sentinels<random_access_iterator<int*>>();
+  test_sentinels<contiguous_iterator<int*>>();
+  test_sentinels<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // check that ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::remove_if(std::array{1, 2, 3, 4}, [](int i) { return i < 0; });
+  }
+
+  {// check complexity requirements
+
+   // This is https://llvm.org/PR56382 - clang-format behaves weird if function-local structs are used
+   // clang-format off
+    {
+      int comp_count = 0;
+      auto comp = [&](int i) {
+        ++comp_count;
+        return i == 0;
+      };
+      int proj_count = 0;
+      auto proj      = [&](int i) {
+        ++proj_count;
+        return i;
+      };
+      int a[]  = {1, 2, 3, 4};
+      auto ret = std::ranges::remove_if(std::begin(a), std::end(a), comp, proj);
+      assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
+      assert(comp_count == 4);
+      assert(proj_count == 4);
+    }
+    {
+      int comp_count = 0;
+      auto comp      = [&](int i) {
+        ++comp_count;
+        return i == 0;
+      };
+      int proj_count = 0;
+      auto proj      = [&](int i) {
+        ++proj_count;
+        return i;
+      };
+      int a[]  = {1, 2, 3, 4};
+      auto ret = std::ranges::remove_if(a, comp, proj);
+      assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
+      assert(comp_count == 4);
+      assert(proj_count == 4);
+    }
+  }
+
+  { // check that std::invoke is used
+    struct S {
+      constexpr S& identity() { return *this; }
+      constexpr bool predicate() const { return true; }
+    };
+    {
+      S a[4]   = {};
+      auto ret = std::ranges::remove_if(std::begin(a), std::end(a), &S::predicate, &S::identity);
+      assert(ret.begin() == std::begin(a));
+      assert(ret.end() == std::end(a));
+    }
+    {
+      S a[4]   = {};
+      auto ret = std::ranges::remove_if(a, &S::predicate, &S::identity);
+      assert(ret.begin() == std::begin(a));
+      assert(ret.end() == std::end(a));
+    }
+  }
+
+  {
+    // check that the implicit conversion to bool works
+    {
+      int a[]  = {1, 2, 3, 4};
+      auto ret = std::ranges::remove_if(a, a + 4, [](const int& i) { return BooleanTestable{i == 3}; });
+      assert(ret.begin() == a + 3);
+    }
+    {
+      int a[]  = {1, 2, 3, 4};
+      auto ret = std::ranges::remove_if(a, [](const int& b) { return BooleanTestable{b == 3}; });
+      assert(ret.begin() == a + 3);
+    }
+  }
+
+  return true;
+}
+// clang-format on
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //static_assert(test(std::ranges::partial_sort, a, a+5));
 //static_assert(test(std::ranges::partial_sort_copy, a, a));
 //static_assert(test(std::ranges::partition, a, odd));
 //static_assert(test(std::ranges::partition_copy, a, a, a, odd));
 //static_assert(test(std::ranges::partition_point, a, odd));
 //static_assert(test(std::ranges::pop_heap, a));
 //static_assert(test(std::ranges::prev_permutation, a));
 //static_assert(test(std::ranges::push_heap, a));
-//static_assert(test(std::ranges::remove, a, 42));
+static_assert(test(std::ranges::remove, a, 42));
 //static_assert(test(std::ranges::remove_copy, a, a, 42));
 //static_assert(test(std::ranges::remove_copy_if, a, a, odd));
-//static_assert(test(std::ranges::remove_if, a, odd));
+static_assert(test(std::ranges::remove_if, a, odd));
 static_assert(test(std::ranges::replace, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy, a, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43));
 static_assert(test(std::ranges::replace_if, a, odd, 43));
 static_assert(test(std::ranges::reverse, a));
 //static_assert(test(std::ranges::reverse_copy, a, a));
 //static_assert(test(std::ranges::rotate, a, a+5));
 //static_assert(test(std::ranges::rotate_copy, a, a+5, a));