[libc++][ranges] implement `std::ranges::set_symmetric_difference`
[libc++][ranges] implement `std::ranges::set_symmetric_difference`
Differential Revision: https://reviews.llvm.org/D129520
NOKEYCHECK=True
GitOrigin-RevId: a5c0638dec838fe4c8189d3c72c251c9030f9605
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index 05c7c7b..4951d03 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -134,6 +134,7 @@
__algorithm/ranges_search_n.h
__algorithm/ranges_set_difference.h
__algorithm/ranges_set_intersection.h
+ __algorithm/ranges_set_symmetric_difference.h
__algorithm/ranges_set_union.h
__algorithm/ranges_shuffle.h
__algorithm/ranges_sort.h
diff --git a/include/__algorithm/ranges_set_intersection.h b/include/__algorithm/ranges_set_intersection.h
index dac35cf..05af91a 100644
--- a/include/__algorithm/ranges_set_intersection.h
+++ b/include/__algorithm/ranges_set_intersection.h
@@ -66,7 +66,7 @@
std::move(__last2),
std::move(__result),
ranges::__make_projected_comp(__comp, __proj1, __proj2));
- return {std::move(__ret.in1), std::move(__ret.in2), std::move(__ret.out)};
+ return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
}
template <
@@ -100,7 +100,7 @@
ranges::end(__range2),
std::move(__result),
ranges::__make_projected_comp(__comp, __proj1, __proj2));
- return {std::move(__ret.in1), std::move(__ret.in2), std::move(__ret.out)};
+ return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
}
};
diff --git a/include/__algorithm/ranges_set_symmetric_difference.h b/include/__algorithm/ranges_set_symmetric_difference.h
new file mode 100644
index 0000000..c54cf3a
--- /dev/null
+++ b/include/__algorithm/ranges_set_symmetric_difference.h
@@ -0,0 +1,116 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_SYMMETRIC_DIFFERENCE_H
+#define _LIBCPP___ALGORITHM_RANGES_SET_SYMMETRIC_DIFFERENCE_H
+
+#include <__algorithm/in_in_out_result.h>
+#include <__algorithm/make_projected.h>
+#include <__algorithm/set_symmetric_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 <__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 _InIter1, class _InIter2, class _OutIter>
+using set_symmetric_difference_result = in_in_out_result<_InIter1, _InIter2, _OutIter>;
+
+namespace __set_symmetric_difference {
+
+struct __fn {
+ template <
+ input_iterator _InIter1,
+ sentinel_for<_InIter1> _Sent1,
+ input_iterator _InIter2,
+ sentinel_for<_InIter2> _Sent2,
+ weakly_incrementable _OutIter,
+ class _Comp = ranges::less,
+ class _Proj1 = identity,
+ class _Proj2 = identity>
+ requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2>
+ _LIBCPP_HIDE_FROM_ABI constexpr set_symmetric_difference_result<_InIter1, _InIter2, _OutIter> operator()(
+ _InIter1 __first1,
+ _Sent1 __last1,
+ _InIter2 __first2,
+ _Sent2 __last2,
+ _OutIter __result,
+ _Comp __comp = {},
+ _Proj1 __proj1 = {},
+ _Proj2 __proj2 = {}) const {
+ auto __ret = std::__set_symmetric_difference(
+ std::move(__first1),
+ std::move(__last1),
+ std::move(__first2),
+ std::move(__last2),
+ std::move(__result),
+ ranges::__make_projected_comp(__comp, __proj1, __proj2));
+ return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
+ }
+
+ template <
+ input_range _Range1,
+ input_range _Range2,
+ weakly_incrementable _OutIter,
+ class _Comp = ranges::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_symmetric_difference_result<borrowed_iterator_t<_Range1>,
+ borrowed_iterator_t<_Range2>,
+ _OutIter>
+ operator()(
+ _Range1&& __range1,
+ _Range2&& __range2,
+ _OutIter __result,
+ _Comp __comp = {},
+ _Proj1 __proj1 = {},
+ _Proj2 __proj2 = {}) const {
+ auto __ret = std::__set_symmetric_difference(
+ ranges::begin(__range1),
+ ranges::end(__range1),
+ ranges::begin(__range2),
+ ranges::end(__range2),
+ std::move(__result),
+ ranges::__make_projected_comp(__comp, __proj1, __proj2));
+ return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)};
+ }
+};
+
+} // namespace __set_symmetric_difference
+
+inline namespace __cpo {
+ inline constexpr auto set_symmetric_difference = __set_symmetric_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_SYMMETRIC_DIFFERENCE_H
diff --git a/include/__algorithm/set_intersection.h b/include/__algorithm/set_intersection.h
index e0f5bd1..77cc837 100644
--- a/include/__algorithm/set_intersection.h
+++ b/include/__algorithm/set_intersection.h
@@ -25,14 +25,14 @@
template <class _InIter1, class _InIter2, class _OutIter>
struct __set_intersection_result {
- _InIter1 in1;
- _InIter2 in2;
- _OutIter out;
+ _InIter1 __in1_;
+ _InIter2 __in2_;
+ _OutIter __out_;
// need a constructor as C++03 aggregate init is hard
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
__set_intersection_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)
- : in1(std::move(__in_iter1)), in2(std::move(__in_iter2)), out(std::move(__out_iter)) {}
+ : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {}
};
template <class _AlgPolicy, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
@@ -74,7 +74,7 @@
std::move(__last2),
std::move(__result),
__comp)
- .out;
+ .__out_;
}
template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
@@ -92,7 +92,7 @@
std::move(__result),
__less<typename iterator_traits<_InputIterator1>::value_type,
typename iterator_traits<_InputIterator2>::value_type>())
- .out;
+ .__out_;
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/include/__algorithm/set_symmetric_difference.h b/include/__algorithm/set_symmetric_difference.h
index 2dbfb35..cd532ab 100644
--- a/include/__algorithm/set_symmetric_difference.h
+++ b/include/__algorithm/set_symmetric_difference.h
@@ -14,6 +14,7 @@
#include <__algorithm/copy.h>
#include <__config>
#include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
@@ -21,55 +22,81 @@
_LIBCPP_BEGIN_NAMESPACE_STD
-template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator
-__set_symmetric_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))
- {
- *__result = *__first2;
- ++__result;
- }
- else
- ++__first1;
- ++__first2;
- }
+template <class _InIter1, class _InIter2, class _OutIter>
+struct __set_symmetric_difference_result {
+ _InIter1 __in1_;
+ _InIter2 __in2_;
+ _OutIter __out_;
+
+ // need a constructor as C++03 aggregate init is hard
+ _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+ __set_symmetric_difference_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter)
+ : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {}
+};
+
+template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>
+__set_symmetric_difference(
+ _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) {
+ while (__first1 != __last1) {
+ if (__first2 == __last2) {
+ auto __ret1 = std::__copy_impl(std::move(__first1), std::move(__last1), std::move(__result));
+ return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>(
+ std::move(__ret1.first), std::move(__first2), std::move((__ret1.second)));
}
- return _VSTD::copy(__first2, __last2, __result);
+ if (__comp(*__first1, *__first2)) {
+ *__result = *__first1;
+ ++__result;
+ ++__first1;
+ } else {
+ if (__comp(*__first2, *__first1)) {
+ *__result = *__first2;
+ ++__result;
+ } else {
+ ++__first1;
+ }
+ ++__first2;
+ }
+ }
+ auto __ret2 = std::__copy_impl(std::move(__first2), std::move(__last2), std::move(__result));
+ return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>(
+ std::move(__first1), std::move(__ret2.first), std::move((__ret2.second)));
}
template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-set_symmetric_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_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_symmetric_difference(
+ _InputIterator1 __first1,
+ _InputIterator1 __last1,
+ _InputIterator2 __first2,
+ _InputIterator2 __last2,
+ _OutputIterator __result,
+ _Compare __comp) {
+ typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+ return std::__set_symmetric_difference<_Comp_ref>(
+ std::move(__first1),
+ std::move(__last1),
+ std::move(__first2),
+ std::move(__last2),
+ std::move(__result),
+ __comp)
+ .__out_;
}
template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_OutputIterator
-set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
-{
- return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
- __less<typename iterator_traits<_InputIterator1>::value_type,
- typename iterator_traits<_InputIterator2>::value_type>());
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_symmetric_difference(
+ _InputIterator1 __first1,
+ _InputIterator1 __last1,
+ _InputIterator2 __first2,
+ _InputIterator2 __last2,
+ _OutputIterator __result) {
+ return std::set_symmetric_difference(
+ std::move(__first1),
+ std::move(__last1),
+ std::move(__first2),
+ std::move(__last2),
+ std::move(__result),
+ __less<typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>());
}
_LIBCPP_END_NAMESPACE_STD
diff --git a/include/algorithm b/include/algorithm
index 18d8ef3..f616a03 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -692,6 +692,26 @@
ranges::find_end(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
+ template<class I1, class I2, class O>
+ using set_symmetric_difference_result = in_in_out_result<I1, I2, O>; // since C++20
+
+ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+ weakly_incrementable O, class Comp = ranges::less,
+ class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+ constexpr set_symmetric_difference_result<I1, I2, O>
+ set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+ Comp comp = {}, Proj1 proj1 = {},
+ Proj2 proj2 = {}); // since C++20
+
+ template<input_range R1, input_range R2, weakly_incrementable O,
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+ constexpr set_symmetric_difference_result<borrowed_iterator_t<R1>,
+ borrowed_iterator_t<R2>, O>
+ set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
+ Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20
+
}
constexpr bool // constexpr in C++20
@@ -1472,6 +1492,7 @@
#include <__algorithm/ranges_search_n.h>
#include <__algorithm/ranges_set_difference.h>
#include <__algorithm/ranges_set_intersection.h>
+#include <__algorithm/ranges_set_symmetric_difference.h>
#include <__algorithm/ranges_sort.h>
#include <__algorithm/ranges_sort_heap.h>
#include <__algorithm/ranges_stable_sort.h>
diff --git a/include/module.modulemap.in b/include/module.modulemap.in
index c0ecfac..25e1c6e 100644
--- a/include/module.modulemap.in
+++ b/include/module.modulemap.in
@@ -373,6 +373,7 @@
module ranges_search_n { private header "__algorithm/ranges_search_n.h" }
module ranges_set_difference { private header "__algorithm/ranges_set_difference.h" }
module ranges_set_intersection { private header "__algorithm/ranges_set_intersection.h" }
+ module ranges_set_symmetric_difference { private header "__algorithm/ranges_set_symmetric_difference.h" }
module ranges_set_union { private header "__algorithm/ranges_set_union.h" }
module ranges_shuffle { private header "__algorithm/ranges_shuffle.h" }
module ranges_sort { private header "__algorithm/ranges_sort.h" }