[libcxx][ranges] implement `std::ranges::set_difference`

[huixie90]

Summary

implement std::ranges::set_difference
reused classic std::set_difference
added unit tests

[var-const]

Looks pretty good overall, the only substantial comment is about avoid observable changes in behavior in the classic set_difference algorithm. Thanks for working on this!

libcxx/docs/Status/RangesAlgorithms.csv

64

Please add a link to this patch.

libcxx/include/__algorithm/ranges_set_difference.h

47

Nit: unnecessary std::.

51

Nit: unnecessary (I think) space. Is this done by clang-format? If yes, it's not worth changing.

libcxx/include/__algorithm/set_difference.h

38

Does using decay here lead to any observable difference?

53

Wouldn't using invoke here create an observable change in behavior for the classic algorithm? It seems like it would cause e.g. passing a pointer to member to work with the classic algorithm which wasn't the case before.

Instead, I would strongly recommend the following trick: in the range algorithm, create a lambda that wraps the comparator and the projection functors and pass it as the comparator. It also avoids the need to pass the projections directly. See e.g. ranges_sort.h:

auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
std::__sort_impl(std::move(__first), __last_iter, __projected_comp);

62–76

Optional: you can also s/_LIBCPP_INLINE_VISIBILITY/_LIBCPP_HIDE_FROM_ABI/ since you're changing this line anyway. _LIBCPP_HIDE_FROM_ABI is the newer name for the same macro (we use it in new code and IMO it's good to update the old code to use the new name when opportunity arises).

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp

97

Ultranit: qualify std:: for consistency?

150

Can you also check the case when the lengths are the same (but the elements are different)?

206

Nit: the test case doesn't seem to check borrowed_range, so remove that part of the comment?

235

Nit: probably needs renaming for consistency with the merge test.

245

Question: does cpp17_input_iterator not work? If yes, can you add a short comment indicating why it doesn't work, to make it clear it wasn't forgotten but deliberately omitted?

262

Since this class is already used here and in merge test, and will likely be used more in further tests, it should probably be moved into a shared header with helpers.

[huixie90]

address comments

[huixie90]

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp

245

The algorithm requires the input to be std::input_iterator which is a c++ 20 concept. cpp_17_input_iterator might or might not work, depending on whether or not it models C++20 input_iterator concept.

IMO it doesn't add too much in the test, and at the same time it couples the test to the implementation of cpp_17_input_iterator. Whether or not model c++ 20's input_iterator might change for that particular class.

If we really want to test it must work, we should probably create another class cpp17_and_cpp20_input_iterator

What do you think?

[huixie90]

remove non ascii characters

[var-const]

Thanks for addressing the feedback!

libcxx/include/__algorithm/make_projected.h

50

Question: why is this check necessary (is_member_pointer)?

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp

245

If a type modeling the _bare minimum_ required to satisfy cpp17_input_iterator doesn't meet the requirements, then we can say that cpp17_input_iterator doesn't work. Consider a comment like "cpp17_input_iterator doesn't satisfy the std::input_iterator constraint".

[huixie90]

libcxx/include/__algorithm/make_projected.h

50

if the caller is passing a member function pointer as comparator and two identitys as projections, without this check, if would just return __comp, which is a member function pointer. And the returned member function pointer is used by the __impl function and the __impl function simply invoke operator() as __comp(*first, *second). This would fail because member function pointer don't support this syntax.

I suspect the overload above needs the same treatment. For the algorithms you've implemented, do you have any tests that pass a member function pointer as comparator and std::identity as projection?

[huixie90]

address feedback

[var-const]

libcxx/include/__algorithm/make_projected.h

50

Thanks a lot for fixing the existing overload!

[philnik]

LGTM % nits.

libcxx/include/__algorithm/ranges_set_difference.h

68–96

This formatting is really weird. Hopefully I'll have some time soon to fix clang-format a bit.

libcxx/include/__algorithm/set_difference.h

68–76

Why aren't you returning std::__set_difference(...).second here? IIUC explicitly doing the move is either redundant because of implicit move or detrimental because of copy elision.

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

127

Could you also uncomment the corresponding line in ranges_result_alias_declarations.compile.pass.cpp?

[var-const]

libcxx/include/__algorithm/set_difference.h

68–76

I think implicit move doesn't apply when returning a member of an object, even if the object itself is a local variable.

[philnik]

libcxx/include/__algorithm/set_difference.h

68–76

https://godbolt.org/z/q1rj39Tdf looks to me a lot like an implicit move.

[huixie90]

address feedback

libcxx/include/__algorithm/set_difference.h

68–76

Double checked with several compilers, it is always a move
https://godbolt.org/z/GPTnzhj38

not because it is implicit move, it is because the expression make_pair(x, y).second yields an rvalue reference to the second member,
so no need for explicit move here

libcxx/docs/Status/RangesAlgorithms.csv

 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
 Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,Under review
 Write,sample,Not assigned,n/a,Not started
 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_difference,Hui Xie,`D128983 <https://llvm.org/D128983>`,✅
 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,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

libcxx/include/CMakeLists.txt

set(files
   __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_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
+  __algorithm/ranges_set_difference.h
   __algorithm/ranges_sort.h
   __algorithm/ranges_stable_sort.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h

libcxx/include/__algorithm/make_projected.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_MAKE_PROJECTED_H
 #define _LIBCPP___ALGORITHM_MAKE_PROJECTED_H
 
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
+#include <__type_traits/decay.h>
+#include <__type_traits/is_member_pointer.h>
 #include <__utility/forward.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)
 
if constexpr (same_as<_Proj, identity>) {
     return [&](auto&& __lhs, auto&& __rhs) {
       return std::invoke(__comp,
                         std::invoke(__proj, std::forward<decltype(__lhs)>(__lhs)),
                         std::invoke(__proj, std::forward<decltype(__rhs)>(__rhs)));
     };
   }
 }
 
+template <class _Comp, class _Proj1, class _Proj2>
+_LIBCPP_HIDE_FROM_ABI constexpr static
+decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) {
+  if constexpr (same_as<_Proj1, identity> && same_as<_Proj2, identity> && !is_member_pointer_v<decay_t<_Comp>>) {
+    // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable
+    // optimizations that rely on the type of the comparator.
+    return __comp;
+
+  } else {
+    return [&](auto&& __lhs, auto&& __rhs) {
+      return std::invoke(__comp,
+                        std::invoke(__proj1, std::forward<decltype(__lhs)>(__lhs)),
+                        std::invoke(__proj2, std::forward<decltype(__rhs)>(__rhs)));
+    };
+  }
+}
+
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_MAKE_PROJECTED_H

libcxx/include/__algorithm/ranges_set_difference.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_SET_DIFFERENCE_H
+#define _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H
+
+#include <__algorithm/in_out_result.h>
+#include <__algorithm/make_projected.h>
+#include <__algorithm/set_difference.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/mergeable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__type_traits/decay.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 set_difference_result = in_out_result<_InIter, _OutIter>;
+
+namespace __set_difference {
+
+  struct __fn {
+    template <
+        input_iterator _InIter1,
+        sentinel_for<_InIter1> _Sent1,
+        input_iterator _InIter2,
+        sentinel_for<_InIter2> _Sent2,
+        weakly_incrementable _OutIter,
+        class _Comp  = less,
+        class _Proj1 = identity,
+        class _Proj2 = identity>
+      requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2>
+    _LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<_InIter1, _OutIter> operator()(
+        _InIter1 __first1,
+        _Sent1 __last1,
+        _InIter2 __first2,
+        _Sent2 __last2,
+        _OutIter __result,
+        _Comp __comp   = {},
+        _Proj1 __proj1 = {},
+        _Proj2 __proj2 = {}) const {
+      auto __ret = std::__set_difference(
+          __first1, __last1, __first2, __last2, __result, ranges::__make_projected_comp(__comp, __proj1, __proj2));
+      return {std::move(__ret.first), std::move(__ret.second)};
+    }
+
+    template <
+        input_range _Range1,
+        input_range _Range2,
+        weakly_incrementable _OutIter,
+        class _Comp  = less,
+        class _Proj1 = identity,
+        class _Proj2 = identity>
+      requires mergeable<
+          iterator_t<_Range1>,
+          iterator_t<_Range2>,
+          _OutIter,
+          _Comp,
+          _Proj1,
+          _Proj2> _LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<borrowed_iterator_t<_Range1>, _OutIter>
+      operator()(
+          _Range1&& __range1,
+          _Range2&& __range2,
+          _OutIter __result,
+          _Comp __comp   = {},
+          _Proj1 __proj1 = {},
+          _Proj2 __proj2 = {}) const {
+      auto __ret = std::__set_difference(
+          ranges::begin(__range1),
+          ranges::end(__range1),
+          ranges::begin(__range2),
+          ranges::end(__range2),
+          __result,
+          ranges::__make_projected_comp(__comp, __proj1, __proj2));
+      return {std::move(__ret.first), std::move(__ret.second)};
+    }
+  };
+
+} // namespace __set_difference
+
+inline namespace __cpo {
+  inline constexpr auto set_difference = __set_difference::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+#endif // _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H
 No newline at end of file

libcxx/include/__algorithm/set_difference.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_SET_DIFFERENCE_H
 #define _LIBCPP___ALGORITHM_SET_DIFFERENCE_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/copy.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
-__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
-                 _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
-{
-    while (__first1 != __last1)
-    {
-        if (__first2 == __last2)
-            return _VSTD::copy(__first1, __last1, __result);
-        if (__comp(*__first1, *__first2))
-        {
-            *__result = *__first1;
-            ++__result;
-            ++__first1;
-        }
-        else
-        {
-            if (!__comp(*__first2, *__first1))
-                ++__first1;
-            ++__first2;
-        }
-    }
-    return __result;
+template < class _Comp, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<__uncvref_t<_InIter1>, __uncvref_t<_OutIter> >
+__set_difference(
+    _InIter1&& __first1, _Sent1&& __last1, _InIter2&& __first2, _Sent2&& __last2, _OutIter&& __result, _Comp&& __comp) {
+  while (__first1 != __last1 && __first2 != __last2) {
+    if (__comp(*__first1, *__first2)) {
+      ++__result;
+    } else if (__comp(*__first2, *__first1)) {
+      ++__first2;
+    } else {
+  return std::__copy(std::move(__first1), std::move(__last1), std::move(__result));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
-               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_difference(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _OutputIterator __result,
+    _Compare __comp) {
+  auto __ret = std::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
+  return std::move(__ret.second);
 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
-               _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
-{
-    return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result,
-                                __less<typename iterator_traits<_InputIterator1>::value_type,
-                                       typename iterator_traits<_InputIterator2>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_difference(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _OutputIterator __result) {
+  auto __ret = std::__set_difference(
+      __first1,
+      __last1,
+      __first2,
+      __last2,
+      __result,
+  return std::move(__ret.second);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SET_DIFFERENCE_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<class I, class O>
+    using set_difference_result = in_out_result<I, 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_difference_result<I1, O>
+      set_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_difference_result<borrowed_iterator_t<R1>, O>
+      set_difference(R1&& r1, R2&& r2, O result,
+                     Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                           // 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_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_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
+#include <__algorithm/ranges_set_difference.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>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>

libcxx/include/module.modulemap.in

module __algorithm {
       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_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_set_difference           { private header "__algorithm/ranges_set_difference.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" }
       module remove                          { private header "__algorithm/remove.h" }
       module remove_copy                     { private header "__algorithm/remove_copy.h" }
       module remove_copy_if                  { private header "__algorithm/remove_copy_if.h" }

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

#endif
     //(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);
-    //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(&copies)); assert(copies == 0);

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

#endif
     (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);
     //(void)std::ranges::search(first, last, first2, mid2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(first, last, count, value, Equal(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(a, count, value, Equal(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::set_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::set_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::set_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #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_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_set_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.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'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.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<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2,
-//          weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity,
+// 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 merge_result<I1, I2, O>
 //     merge(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,
+// 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
 
 #include <algorithm>
 #include <array>
 #include <concepts>
 
 #include "almost_satisfies_types.h"
 #include "MoveOnly.h"
 #include "test_iterators.h"
+#include "../sortable_helpers.h"
 
 // Test iterator overload's constraints:
 // =====================================
 template <
     class InIter1,
     class InIter2,
     class OutIter,
     class Sent1 = sentinel_wrapper<InIter1>,
constexpr bool withAllPermutationsOfInIter1AndInIter2() {
   withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>();
   withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>();
   withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>();
   withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>();
   return true;
 }
 
 constexpr void runAllIteratorPermutationsTests() {
-  withAllPermutationsOfInIter1AndInIter2<cpp17_output_iterator<int*>>();
   withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>();
   withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>();
   withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>();
   withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>();
   withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>();
 
-  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp17_output_iterator<int*>>());
   static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>());
   static_assert(withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>());
   static_assert(withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>());
   static_assert(withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>());
   static_assert(withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>());
 }
 
 constexpr bool test() {
   // check that every element is copied exactly once
-  struct TracedCopy {
-    int copy_assign = 0;
-    int data        = 0;
-
-    constexpr TracedCopy() = default;
-    constexpr TracedCopy(int i) : data(i) {}
-    constexpr TracedCopy(const TracedCopy& other) : copy_assign(other.copy_assign), data(other.data) {}
-
-    constexpr TracedCopy(TracedCopy&& other)            = delete;
-    constexpr TracedCopy& operator=(TracedCopy&& other) = delete;
-
-    constexpr TracedCopy& operator=(const TracedCopy& other) {
-      copy_assign = other.copy_assign + 1;
-      data        = other.data;
-      return *this;
-    }
-
-    constexpr bool operator==(const TracedCopy& o) const { return data == o.data; }
-    constexpr auto operator<=>(const TracedCopy& o) const { return data <=> o.data; }
-  };
   {
     std::array<TracedCopy, 3> r1{3, 5, 8};
     std::array<TracedCopy, 3> r2{1, 3, 8};
 
     // iterator overload
     {
       std::array<TracedCopy, 6> out;
       auto result = std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
 
       assert(result.in1 == r1.end());
       assert(result.in2 == r2.end());
       assert(result.out == out.end());
       assert(std::ranges::equal(out, std::array<TracedCopy, 6>{1, 3, 3, 5, 8, 8}));
 
-      assert(std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; }));
+      assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
     }
 
     // range overload
     {
       std::array<TracedCopy, 6> out;
       auto result = std::ranges::merge(r1, r2, out.data());
 
       assert(result.in1 == r1.end());
       assert(result.in2 == r2.end());
       assert(result.out == out.end());
       assert(std::ranges::equal(out, std::array<TracedCopy, 6>{1, 3, 3, 5, 8, 8}));
 
-      assert(std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; }));
+      assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
     }
   }
 
   struct IntAndID {
     int data;
     int id;
 
     constexpr auto operator==(const IntAndID& o) const { return data == o.data; }

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.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<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_difference_result<I1, O>
+//     set_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_difference_result<borrowed_iterator_t<R1>, O>
+//     set_difference(R1&& r1, R2&& r2, O result,
+//                    Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                           // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+
+#include "almost_satisfies_types.h"
+#include "MoveOnly.h"
+#include "test_iterators.h"
+#include "../../sortable_helpers.h"
+
+// Test iterator overload's constraints:
+// =====================================
+template <
+    class InIter1,
+    class InIter2,
+    class OutIter,
+    class Sent1 = sentinel_wrapper<InIter1>,
+    class Sent2 = sentinel_wrapper<InIter2>>
+concept HasSetDifferenceIter =
+    requires(InIter1&& inIter1, InIter2&& inIter2, OutIter&& outIter, Sent1&& sent1, Sent2&& sent2) {
+      std::ranges::set_difference(
+          std::forward<InIter1>(inIter1),
+          std::forward<Sent1>(sent1),
+          std::forward<InIter2>(inIter2),
+          std::forward<Sent2>(sent2),
+          std::forward<OutIter>(outIter));
+    };
+
+static_assert(HasSetDifferenceIter<int*, int*, int*, int*, int*>);
+
+// !std::input_iterator<I1>
+static_assert(!HasSetDifferenceIter<InputIteratorNotDerivedFrom, int*, int*>);
+
+// !std::sentinel_for<S1, I1>
+static_assert(!HasSetDifferenceIter<int*, int*, int*, SentinelForNotSemiregular>);
+
+// !std::input_iterator<I2>
+static_assert(!HasSetDifferenceIter<int*, InputIteratorNotDerivedFrom, int*>);
+
+// !std::sentinel_for<S2, I2>
+static_assert(!HasSetDifferenceIter<int*, int*, int*, int*, SentinelForNotSemiregular>);
+
+// !std::weakly_incrementable<O>
+static_assert(!HasSetDifferenceIter<int*, int*, WeaklyIncrementableNotMovable>);
+
+// !std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
+static_assert(!HasSetDifferenceIter<MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*>);
+
+// Test range overload's constraints:
+// =====================================
+
+template <class Range1, class Range2, class OutIter>
+concept HasSetDifferenceRange =
+    requires(Range1&& range1, Range2&& range2, OutIter&& outIter) {
+      std::ranges::set_difference(
+          std::forward<Range1>(range1), std::forward<Range2>(range2), std::forward<OutIter>(outIter));
+    };
+
+static_assert(HasSetDifferenceRange<UncheckedRange<int*>, UncheckedRange<int*>, int*>);
+
+// !std::input_range<R2>
+static_assert(!HasSetDifferenceRange<UncheckedRange<InputIteratorNotDerivedFrom>, UncheckedRange<int*>, int*>);
+
+// !std::input_range<R2>
+static_assert(!HasSetDifferenceRange<UncheckedRange<int*>, UncheckedRange<InputIteratorNotDerivedFrom>, int*>);
+
+// !std::weakly_incrementable<O>
+static_assert(!HasSetDifferenceRange<UncheckedRange<int*>, UncheckedRange<int*>, WeaklyIncrementableNotMovable >);
+
+// !std::mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+static_assert(!HasSetDifferenceRange< UncheckedRange<MoveOnly*>, UncheckedRange<MoveOnly*>, MoveOnly*>);
+
+using std::ranges::set_difference_result;
+
+template <class In1, class In2, class Out, std::size_t N1, std::size_t N2, std::size_t N3>
+constexpr void testSetDifferenceImpl(std::array<int, N1> in1, std::array<int, N2> in2, std::array<int, N3> expected) {
+  // TODO: std::ranges::set_difference calls std::ranges::copy
+  // std::ranges::copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
+  // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator<int*> into int*,
+  // and then it failed because there is no == between int* and sentinel_wrapper<contiguous_iterator<int*>>
+  using Sent1 = std::conditional_t<std::contiguous_iterator<In1>, In1, sentinel_wrapper<In1>>;
+  using Sent2 = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
+
+  // iterator overload
+  {
+    std::array<int, N3> out;
+    std::same_as<set_difference_result<In1, Out>> decltype(auto) result = std::ranges::set_difference(
+        In1{in1.data()},
+        Sent1{In1{in1.data() + in1.size()}},
+        In2{in2.data()},
+        Sent2{In2{in2.data() + in2.size()}},
+        Out{out.data()});
+    assert(std::ranges::equal(out, expected));
+
+    assert(base(result.in) == in1.data() + in1.size());
+    assert(base(result.out) == out.data() + out.size());
+  }
+
+  // range overload
+  {
+    std::array<int, N3> out;
+    std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}};
+    std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}};
+    std::same_as<set_difference_result<In1, Out>> decltype(auto) result =
+        std::ranges::set_difference(r1, r2, Out{out.data()});
+    assert(std::ranges::equal(out, expected));
+
+    assert(base(result.in) == in1.data() + in1.size());
+    assert(base(result.out) == out.data() + out.size());
+  }
+}
+
+template <class In1, class In2, class Out>
+constexpr void testImpl() {
+  // range 1 shorter than range2
+  {
+    std::array in1{0, 1, 5, 6, 9, 10};
+    std::array in2{3, 6, 7, 9, 13, 15, 100};
+    std::array expected{0, 1, 5, 10};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 shorter than range 1
+  {
+    std::array in1{2, 6, 8, 12, 15, 16};
+    std::array in2{0, 2, 8};
+    std::array expected{6, 12, 15, 16};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 and range 2 has the same length but different elements
+  {
+    std::array in1{2, 6, 8, 12, 15, 16};
+    std::array in2{0, 2, 8, 15, 17, 19};
+    std::array expected{6, 12, 16};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 == range 2
+  {
+    std::array in1{0, 1, 2};
+    std::array in2{0, 1, 2};
+    std::array<int, 0> expected{};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 is super set of range 2
+  {
+    std::array in1{8, 8, 10, 12, 13};
+    std::array in2{8, 10};
+    std::array expected{8, 12, 13};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 is super set of range 1
+  {
+    std::array in1{0, 1, 1};
+    std::array in2{0, 1, 1, 2, 5};
+    std::array<int, 0> expected{};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 1 is empty
+  {
+    std::array<int, 0> in1{};
+    std::array in2{3, 4, 5};
+    std::array<int, 0> expected{};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // range 2 is empty
+  {
+    std::array in1{3, 4, 5};
+    std::array<int, 0> in2{};
+    std::array expected{3, 4, 5};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // both ranges are empty
+  {
+    std::array<int, 0> in1{};
+    std::array<int, 0> in2{};
+    std::array<int, 0> expected{};
+    testSetDifferenceImpl<In1, In2, Out>(in1, in2, expected);
+  }
+
+  // check that ranges::dangling is returned for non-borrowed_range
+  {
+    struct NonBorrowedRange {
+      int* data_;
+      size_t size_;
+
+      // TODO: std::ranges::set_difference calls std::__copy
+      // std::ranges::copy(contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>, contiguous_iterator<int*>) doesn't seem to work.
+      // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator<int*> into int*,
+      // and then it failed because there is no == between int* and sentinel_wrapper<contiguous_iterator<int*>>
+      using Sent = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
+
+      constexpr NonBorrowedRange(int* d, size_t s) : data_{d}, size_{s} {}
+
+      constexpr In2 begin() const { return In2{data_}; };
+      constexpr Sent end() const { return Sent{In2{data_ + size_}}; };
+    };
+
+    std::array r1{3, 6, 7, 9};
+    std::array r2{2, 3, 4, 5, 6};
+    std::array<int, 2> out;
+    std::same_as<set_difference_result<std::ranges::dangling, int*>> decltype(auto) result =
+        std::ranges::set_difference(NonBorrowedRange{r1.data(), r1.size()}, r2, out.data());
+    assert(base(result.out) == out.data() + out.size());
+    assert(std::ranges::equal(out, std::array{7, 9}));
+  }
+}
+
+template <class InIter2, class OutIter>
+constexpr void withAllPermutationsOfInIter1() {
+  testImpl<cpp20_input_iterator<int*>, InIter2, OutIter>();
+  testImpl<forward_iterator<int*>, InIter2, OutIter>();
+  testImpl<bidirectional_iterator<int*>, InIter2, OutIter>();
+  testImpl<random_access_iterator<int*>, InIter2, OutIter>();
+  testImpl<contiguous_iterator<int*>, InIter2, OutIter>();
+}
+
+template <class OutIter>
+constexpr bool withAllPermutationsOfInIter1AndInIter2() {
+  withAllPermutationsOfInIter1<cpp20_input_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<forward_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<bidirectional_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<random_access_iterator<int*>, OutIter>();
+  withAllPermutationsOfInIter1<contiguous_iterator<int*>, OutIter>();
+  return true;
+}
+
+constexpr void runAllIteratorPermutationsTests() {
+  withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>();
+  withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>();
+
+  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_output_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<cpp20_input_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<forward_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<bidirectional_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<random_access_iterator<int*>>());
+  static_assert(withAllPermutationsOfInIter1AndInIter2<contiguous_iterator<int*>>());
+}
+
+constexpr bool test() {
+  // check that every element is copied exactly once
+  {
+    std::array<TracedCopy, 5> r1{3, 5, 8, 15, 16};
+    std::array<TracedCopy, 3> r2{1, 3, 8};
+
+    // iterator overload
+    {
+      std::array<TracedCopy, 3> out;
+      auto result = std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+      assert(std::ranges::equal(out, std::array<TracedCopy, 3>{5, 15, 16}));
+
+      assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
+    }
+
+    // range overload
+    {
+      std::array<TracedCopy, 3> out;
+      auto result = std::ranges::set_difference(r1, r2, out.data());
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+      assert(std::ranges::equal(out, std::array<TracedCopy, 3>{5, 15, 16}));
+
+      assert(std::ranges::all_of(out, &TracedCopy::copiedOnce));
+    }
+  }
+
+  struct IntAndOrder {
+    int data;
+    int order;
+
+    constexpr auto operator==(const IntAndOrder& o) const { return data == o.data; }
+    constexpr auto operator<=>(const IntAndOrder& o) const { return data <=> o.data; }
+  };
+
+  // equal elements should be copied in the original order and only m-n elements are copied
+  {
+    std::array<IntAndOrder, 5> r1{{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}}};
+    std::array<IntAndOrder, 3> r2{{{0, 1}, {0, 2}, {0, 3}}};
+
+    // iterator overload
+    {
+      std::array<IntAndOrder, 2> out;
+      std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0}, {}, &IntAndOrder::data));
+      // m-n elements are copied in order
+      assert(std::ranges::equal(out, std::array{3, 4}, {}, &IntAndOrder::order));
+    }
+
+    // range overload
+    {
+      std::array<IntAndOrder, 2> out;
+      std::ranges::set_difference(r1, r2, out.data());
+
+      assert(std::ranges::equal(out, std::array{0, 0}, {}, &IntAndOrder::data));
+      // ID should be in their original order
+      assert(std::ranges::equal(out, std::array{3, 4}, {}, &IntAndOrder::order));
+    }
+  }
+
+  struct Data {
+    int data;
+
+    constexpr bool smallerThan(const Data& o) const { return data < o.data; }
+  };
+
+  // Test custom comparator
+  {
+    std::array r1{Data{4}, Data{8}, Data{12}};
+    std::array r2{Data{8}, Data{9}};
+    using Iter1 = std::array<Data, 3>::iterator;
+
+    // iterator overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result = std::ranges::set_difference(
+          r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), [](const Data& x, const Data& y) {
+            return x.data < y.data;
+          });
+
+      assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+
+    // range overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
+          std::ranges::set_difference(r1, r2, out.data(), [](const Data& x, const Data& y) { return x.data < y.data; });
+
+      assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Comparator iterator overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
+          std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), &Data::smallerThan);
+
+      assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Comparator range overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
+          std::ranges::set_difference(r1, r2, out.data(), &Data::smallerThan);
+
+      assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+  }
+
+  // Test Projection
+  {
+    std::array r1{Data{1}, Data{3}, Data{5}};
+    std::array r2{Data{2}, Data{3}, Data{4}};
+    using Iter1 = std::array<Data, 3>::iterator;
+
+    const auto proj = [](const Data& d) { return d.data; };
+
+    // iterator overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result = std::ranges::set_difference(
+          r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), std::ranges::less{}, proj, proj);
+
+      assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+
+    // range overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
+          std::ranges::set_difference(r1, r2, out.data(), std::ranges::less{}, proj, proj);
+
+      assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Projection iterator overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result = std::ranges::set_difference(
+          r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), {}, &Data::data, &Data::data);
+
+      assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+
+    // member pointer Projection range overload
+    {
+      std::array<Data, 2> out;
+      std::same_as<set_difference_result<Iter1, Data*>> decltype(auto) result =
+          std::ranges::set_difference(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data);
+
+      assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data));
+
+      assert(result.in == r1.end());
+      assert(result.out == out.end());
+    }
+  }
+
+  // Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection.
+  {
+    std::array<Data, 3> r1{{{4}, {8}, {12}}};
+    std::array<Data, 9> r2{{{1}, {2}, {3}, {5}, {6}, {7}, {9}, {10}, {11}}};
+    std::array expected{4, 8, 12};
+
+    const std::size_t maxOperation = 2 * (r1.size() + r2.size()) - 1;
+
+    // iterator overload
+    {
+      std::array<Data, 3> out;
+      std::size_t numberOfComp  = 0;
+      std::size_t numberOfProj1 = 0;
+      std::size_t numberOfProj2 = 0;
+
+      const auto comp = [&numberOfComp](int x, int y) {
+        ++numberOfComp;
+        return x < y;
+      };
+
+      const auto proj1 = [&numberOfProj1](const Data& d) {
+        ++numberOfProj1;
+        return d.data;
+      };
+
+      const auto proj2 = [&numberOfProj2](const Data& d) {
+        ++numberOfProj2;
+        return d.data;
+      };
+
+      std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), comp, proj1, proj2);
+
+      assert(std::ranges::equal(out, expected, {}, &Data::data));
+      assert(numberOfComp < maxOperation);
+      assert(numberOfProj1 < maxOperation);
+      assert(numberOfProj2 < maxOperation);
+    }
+
+    // range overload
+    {
+      std::array<Data, 3> out;
+      std::size_t numberOfComp  = 0;
+      std::size_t numberOfProj1 = 0;
+      std::size_t numberOfProj2 = 0;
+
+      const auto comp = [&numberOfComp](int x, int y) {
+        ++numberOfComp;
+        return x < y;
+      };
+
+      const auto proj1 = [&numberOfProj1](const Data& d) {
+        ++numberOfProj1;
+        return d.data;
+      };
+
+      const auto proj2 = [&numberOfProj2](const Data& d) {
+        ++numberOfProj2;
+        return d.data;
+      };
+
+      std::ranges::set_difference(r1, r2, out.data(), comp, proj1, proj2);
+
+      assert(std::ranges::equal(out, expected, {}, &Data::data));
+      assert(numberOfComp < maxOperation);
+      assert(numberOfProj1 < maxOperation);
+      assert(numberOfProj2 < maxOperation);
+    }
+  }
+
+  // Comparator convertible to bool
+  {
+    struct ConvertibleToBool {
+      bool b;
+      constexpr operator bool() const { return b; }
+    };
+    Data r1[] = {{2}, {4}};
+    Data r2[] = {{3}, {4}, {5}};
+
+    const auto comp = [](const Data& x, const Data& y) { return ConvertibleToBool{x.data < y.data}; };
+
+    // iterator overload
+    {
+      std::array<Data, 1> out;
+      std::ranges::set_difference(r1, r1 + 2, r2, r2 + 3, out.data(), comp);
+      assert(std::ranges::equal(out, std::array{2}, {}, &Data::data));
+    }
+
+    // range overload
+    {
+      std::array<Data, 1> out;
+      std::ranges::set_difference(r1, r2, out.data(), comp);
+      assert(std::ranges::equal(out, std::array{2}, {}, &Data::data));
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  runAllIteratorPermutationsTests();
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/sortable_helpers.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 SORTABLE_HELPERS_H
 #define SORTABLE_HELPERS_H
 
 #include <type_traits>
 
 #include "test_macros.h"
 
+#if TEST_STD_VER > 17
+#include <compare>
+#endif 
+
 struct TrivialSortable {
     int value;
     TEST_CONSTEXPR TrivialSortable() : value(0) {}
     TEST_CONSTEXPR TrivialSortable(int v) : value(v) {}
     friend TEST_CONSTEXPR bool operator<(const TrivialSortable& a, const TrivialSortable& b) {
         return a.value / 10 < b.value / 10;
     }
     static TEST_CONSTEXPR bool less(const TrivialSortable& a, const TrivialSortable& b) {
struct NonTrivialSortableWithComp {
     }
 };
 
 static_assert(std::is_trivially_copyable<TrivialSortable>::value, "");
 static_assert(std::is_trivially_copyable<TrivialSortableWithComp>::value, "");
 static_assert(!std::is_trivially_copyable<NonTrivialSortable>::value, "");
 static_assert(!std::is_trivially_copyable<NonTrivialSortableWithComp>::value, "");
 
+#if TEST_STD_VER > 17
+struct TracedCopy {
+  int copied = 0;
+  int data   = 0;
+
+  constexpr TracedCopy() = default;
+  constexpr TracedCopy(int i) : data(i) {}
+  constexpr TracedCopy(const TracedCopy& other) : copied(other.copied + 1), data(other.data) {}
+
+  constexpr TracedCopy(TracedCopy&& other)            = delete;
+  constexpr TracedCopy& operator=(TracedCopy&& other) = delete;
+
+  constexpr TracedCopy& operator=(const TracedCopy& other) {
+    copied = other.copied + 1;
+    data   = other.data;
+    return *this;
+  }
+
+  constexpr bool copiedOnce() const { return copied == 1; }
+
+  constexpr bool operator==(const TracedCopy& o) const { return data == o.data; }
+  constexpr auto operator<=>(const TracedCopy& o) const { return data <=> o.data; }
+};
+#endif // TEST_STD_VER > 17
+
 #endif // SORTABLE_HELPERS_H

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

 //static_assert(test(std::ranges::push_heap, a));
 //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::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));
 //static_assert(test(std::ranges::sample, a, a, 5));
 //static_assert(test(std::ranges::search, a, a));
 //static_assert(test(std::ranges::search_n, a, 10, 42));
-//static_assert(test(std::ranges::set_difference, a, a, a));
+static_assert(test(std::ranges::set_difference, a, a, a));
 //static_assert(test(std::ranges::set_intersection, a, a, a));
 //static_assert(test(std::ranges::set_symmetric_difference, a, a, a));
 //static_assert(test(std::ranges::set_union, a, a, a));
 //static_assert(test(std::ranges::shuffle, a, g));
 static_assert(test(std::ranges::sort, a));
 //static_assert(test(std::ranges::sort_heap, a));
 //static_assert(test(std::ranges::stable_partition, a, odd));
 static_assert(test(std::ranges::stable_sort, a));