diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv
--- a/libcxx/docs/Status/RangesAlgorithms.csv
+++ b/libcxx/docs/Status/RangesAlgorithms.csv
@@ -60,11 +60,11 @@
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,Not assigned,n/a,Not started
-Merge,set_difference,Not assigned,n/a,Not started
-Merge,set_intersection,Not assigned,n/a,Not started
-Merge,set_symmetric_difference,Not assigned,n/a,Not started
-Merge,set_union,Not assigned,n/a,Not started
+Merge,merge,Hui Xie,n/a,✅
+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,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -94,6 +94,7 @@
__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
diff --git a/libcxx/include/__algorithm/ranges_merge.h b/libcxx/include/__algorithm/ranges_merge.h
new file mode 100644
--- /dev/null
+++ b/libcxx/include/__algorithm/ranges_merge.h
@@ -0,0 +1,142 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_MERGE_H
+#define _LIBCPP___ALGORITHM_RANGES_MERGE_H
+
+#include <__algorithm/in_in_out_result.h>
+#include <__algorithm/ranges_copy.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 _InIter1, class _InIter2, class _OutIter>
+using merge_result = in_in_out_result<_InIter1, _InIter2, _OutIter>;
+
+template <
+ class _InIter1,
+ class _Sent1,
+ class _InIter2,
+ class _Sent2,
+ class _OutIter,
+ class _Comp,
+ class _Proj1,
+ class _Proj2>
+_LIBCPP_HIDE_FROM_ABI constexpr ranges::merge_result<decay_t<_InIter1>, decay_t<_InIter2>, decay_t<_OutIter>>
+__merge_impl(
+ _InIter1&& __first1,
+ _Sent1&& __last1,
+ _InIter2&& __first2,
+ _Sent2&& __last2,
+ _OutIter&& __result,
+ _Comp&& __comp,
+ _Proj1&& __proj1,
+ _Proj2&& __proj2) {
+ for (; __first1 != __last1 && __first2 != __last2; ++__result) {
+ if (std::invoke(__comp, std::invoke(__proj2, *__first2), std::invoke(__proj1, *__first1))) {
+ *__result = *__first2;
+ ++__first2;
+ } else {
+ *__result = *__first1;
+ ++__first1;
+ }
+ }
+ auto __ret1 = ranges::copy(std::move(__first1), std::move(__last1), std::move(__result));
+ auto __ret2 = ranges::copy(std::move(__first2), std::move(__last2), std::move(__ret1.out));
+ return {std::move(__ret1.in), std::move(__ret2.in), std::move(__ret2.out)};
+}
+
+namespace __merge {
+
+ 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 std::mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2>
+ _LIBCPP_HIDE_FROM_ABI constexpr ranges::merge_result<_InIter1, _InIter2, _OutIter> operator()(
+ _InIter1 __first1,
+ _Sent1 __last1,
+ _InIter2 __first2,
+ _Sent2 __last2,
+ _OutIter __result,
+ _Comp __comp = {},
+ _Proj1 __proj1 = {},
+ _Proj2 __proj2 = {}) const {
+ return ranges::__merge_impl(__first1, __last1, __first2, __last2, __result, __comp, __proj1, __proj2);
+ }
+
+ template <
+ ranges::input_range _Range1,
+ ranges::input_range _Range2,
+ std::weakly_incrementable _OutIter,
+ class _Comp = ranges::less,
+ class _Proj1 = identity,
+ class _Proj2 = identity >
+ requires std::mergeable<
+ ranges::iterator_t<_Range1>,
+ ranges::iterator_t<_Range2>,
+ _OutIter,
+ _Comp,
+ _Proj1,
+ _Proj2> _LIBCPP_HIDE_FROM_ABI constexpr ranges::
+ merge_result<ranges::borrowed_iterator_t<_Range1>, ranges::borrowed_iterator_t<_Range2>, _OutIter>
+ operator()(
+ _Range1&& __range1,
+ _Range2&& __range2,
+ _OutIter __result,
+ _Comp __comp = {},
+ _Proj1 __proj1 = {},
+ _Proj2 __proj2 = {}) const {
+ return ranges::__merge_impl(
+ ranges::begin(__range1),
+ ranges::end(__range1),
+ ranges::begin(__range2),
+ ranges::end(__range2),
+ std::move(__result),
+ std::move(__comp),
+ std::move(__proj1),
+ std::move(__proj2));
+ }
+ };
+
+} // namespace __merge
+
+inline namespace __cpo {
+ inline constexpr auto merge = __merge::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MERGE_H
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -470,6 +470,23 @@
constexpr ranges::move_result<borrowed_iterator_t<R>, O>
ranges::move(R&& r, O result); // since C++20
+ template<class I1, class I2, class O>
+ using merge_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 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,
+ 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
}
@@ -1211,6 +1228,7 @@
#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>
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -333,6 +333,7 @@
module ranges_lower_bound { private header "__algorithm/ranges_lower_bound.h" }
module ranges_max { private header "__algorithm/ranges_max.h" }
module ranges_max_element { private header "__algorithm/ranges_max_element.h" }
+ module ranges_merge { private header "__algorithm/ranges_merge.h" }
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" }
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp
@@ -79,7 +79,7 @@
{
void *a[10] = {};
void *b[10] = {};
- //void *half[5] = {};
+ void *half[5] = {};
void **first = a;
void **mid = a+5;
void **last = a+10;
@@ -151,8 +151,8 @@
(void)std::ranges::max(a, Less(&copies)); assert(copies == 0);
(void)std::ranges::max_element(first, last, Less(&copies)); assert(copies == 0);
(void)std::ranges::max_element(a, Less(&copies)); assert(copies == 0);
- //(void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
- //(void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0);
+ (void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
+ (void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0);
(void)std::ranges::min(value, value, Less(&copies)); assert(copies == 0);
(void)std::ranges::min({ value, value }, Less(&copies)); assert(copies == 0);
(void)std::ranges::min(a, Less(&copies)); assert(copies == 0);
diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
--- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp
@@ -61,7 +61,7 @@
{
T a[10] = {};
T b[10] = {};
- //T half[5] = {};
+ T half[5] = {};
T *first = a;
T *mid = a+5;
T *last = a+10;
@@ -134,8 +134,8 @@
(void)std::ranges::max(a, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::max_element(first, last, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::max_element(a, Less(), Proj(&copies)); assert(copies == 0);
- //(void)std::ranges::merge(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
- //(void)std::ranges::merge(half, half, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+ (void)std::ranges::merge(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+ (void)std::ranges::merge(half, half, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
(void)std::ranges::min(T(), T(), Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::min({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0);
(void)std::ranges::min(a, Less(), Proj(&copies)); assert(copies == 0);
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -131,6 +131,7 @@
#include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}}
#include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
#include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
+#include <__algorithm/ranges_merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_merge.h'}}
#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'}}
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp
@@ -0,0 +1,573 @@
+//===----------------------------------------------------------------------===//
+//
+// 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 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,
+// 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 "almost_satisfies_types.h"
+#include "MoveOnly.h"
+#include "test_iterators.h"
+
+template <class... Args>
+concept HasMerge = requires(Args&&... args) { std::ranges::merge(std::forward<Args>(args)...); };
+
+// clang-format off
+
+using NotInputIter = InputIteratorNotDerivedFrom;
+using NotSentinel = SentinelForNotSemiregular;
+
+template <class It>
+using Sent = sentinel_wrapper<It>;
+
+// Test iterator overload's constraints:
+// =====================================
+
+// | InIter1 | Sent1 | InIter2 | Sent2 | OutIter |
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+static_assert( HasMerge<
+ int*, int*, int*, int*, int* >);
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+// !std::input_iterator<I1>
+static_assert(!HasMerge<
+ NotInputIter, Sent<NotInputIter>, int*, int*, int* >);
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+// !std::sentinel_for<S1, I1>
+static_assert(!HasMerge<
+ int*, NotSentinel, int*, int*, int* >);
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+// !std::input_iterator<I2>
+static_assert(!HasMerge<
+ int*, int*, NotInputIter, Sent<NotInputIter>, int* >);
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+// !std::sentinel_for<S2, I2>
+static_assert(!HasMerge<
+ int*, int*, int*, NotSentinel, int* >);
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+// !std::weakly_incrementable<O>
+static_assert(!HasMerge<
+ int*, int*, int*, int*, WeaklyIncrementableNotMovable>);
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+// !std::mergeable<I1, I2, O, Comp, Proj1, Proj2>
+static_assert(!HasMerge<
+ MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly*, MoveOnly* >);
+// |-----------------|-------------------|----------------|-----------------|-----------------|
+
+// Test range overload's constraints:
+// =====================================
+
+template <class It, class St = sentinel_wrapper<It>>
+using Range = UncheckedRange<It, St>;
+
+
+// | R1 | R2 | OutIter |
+// |------------------------|--------------------------|--------------------------|
+static_assert(HasMerge<
+ Range<int*, int*>, Range<int*, int*>, int* >);
+// |------------------------|--------------------------|--------------------------|
+// !std::input_range<R1>
+static_assert(!HasMerge<
+ Range<NotInputIter>, Range<int*>, int* >);
+// |------------------------|--------------------------|--------------------------|
+// !std::input_range<R2>
+static_assert(!HasMerge<
+ Range<int*>, Range<NotInputIter>, int* >);
+// |------------------------|--------------------------|--------------------------|
+// !std::weakly_incrementable<O>
+static_assert(!HasMerge<
+ Range<int*>, Range<int*>, WeaklyIncrementableNotMovable >);
+// |------------------------|--------------------------|--------------------------|
+// !mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+static_assert(!HasMerge<
+ Range<MoveOnly*>, Range<MoveOnly*>, MoveOnly* >);
+// |------------------------|--------------------------|--------------------------|
+
+// clang-format on
+
+template <class In1, class In2, class Out, std::size_t N1, std::size_t N2>
+constexpr void testMergeImpl(std::array<int, N1>& in1, std::array<int, N2>& in2, const auto& expected) {
+ // TODO: std::ranges::merge 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, N1 + N2> out;
+ std::same_as<std::ranges::merge_result<In1, In2, Out>> decltype(auto) result = std::ranges::merge(
+ 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.in1) == in1.data() + in1.size());
+ assert(base(result.in2) == in2.data() + in2.size());
+ assert(base(result.out) == out.data() + out.size());
+ }
+
+ // range overload
+ {
+ std::array<int, N1 + N2> 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<std::ranges::merge_result<In1, In2, Out>> decltype(auto) result =
+ std::ranges::merge(r1, r2, Out{out.data()});
+ assert(std::ranges::equal(out, expected));
+
+ assert(base(result.in1) == in1.data() + in1.size());
+ assert(base(result.in2) == in2.data() + in2.size());
+ assert(base(result.out) == out.data() + out.size());
+ }
+}
+
+template <class In1, class In2, class Out>
+constexpr void testImpl() {
+ // Test merge produces correct result for different kinds of iterators
+ {
+ std::array in1{0, 1, 5, 6, 9, 10};
+ std::array in2{3, 6, 7, 9, 13, 15, 100};
+ std::array expected{0, 1, 3, 5, 6, 6, 7, 9, 9, 10, 13, 15, 100};
+ testMergeImpl<In1, In2, Out>(in1, in2, expected);
+ }
+ {
+ std::array in1{0, 1, 2};
+ std::array in2{0, 1, 2};
+ std::array expected{0, 0, 1, 1, 2, 2};
+ testMergeImpl<In1, In2, Out>(in1, in2, expected);
+ }
+ {
+ std::array in1{0};
+ std::array in2{0, 0, 0, 1};
+ std::array expected{0, 0, 0, 0, 1};
+ testMergeImpl<In1, In2, Out>(in1, in2, expected);
+ }
+
+ // check that ranges::dangling is returned for non-borrowed_range and iterator_t is returned for borrowed_range
+ {
+ struct NonBorrowRange {
+ int* data_;
+ size_t size_;
+
+ // TODO: std::ranges::merge 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 Sent = std::conditional_t<std::contiguous_iterator<In2>, In2, sentinel_wrapper<In2>>;
+
+ constexpr NonBorrowRange(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};
+ std::array<int, 7> out;
+ std::same_as<std::ranges::merge_result<std::array<int, 4>::iterator, std::ranges::dangling, int*>> decltype(auto)
+ result = std::ranges::merge(r1, NonBorrowRange{r2.data(), r2.size()}, out.data());
+ assert(base(result.in1) == r1.end());
+ assert(base(result.out) == out.data() + out.size());
+ assert(std::ranges::equal(out, std::array{2, 3, 3, 4, 6, 7, 9}));
+ }
+}
+
+template <class InIter2, class OutIter>
+constexpr void withAllIn1Iterators() {
+ 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 void withAllIn1In2Iterators() {
+ withAllIn1Iterators<cpp20_input_iterator<int*>, OutIter>();
+ withAllIn1Iterators<forward_iterator<int*>, OutIter>();
+ withAllIn1Iterators<bidirectional_iterator<int*>, OutIter>();
+ withAllIn1Iterators<random_access_iterator<int*>, OutIter>();
+ withAllIn1Iterators<contiguous_iterator<int*>, OutIter>();
+}
+
+constexpr void withAllIteartorPermutations() {
+ withAllIn1In2Iterators<cpp17_output_iterator<int*>>();
+ withAllIn1In2Iterators<cpp20_output_iterator<int*>>();
+ withAllIn1In2Iterators<cpp17_input_iterator<int*>>();
+ withAllIn1In2Iterators<cpp20_input_iterator<int*>>();
+ withAllIn1In2Iterators<forward_iterator<int*>>();
+ withAllIn1In2Iterators<bidirectional_iterator<int*>>();
+ withAllIn1In2Iterators<random_access_iterator<int*>>();
+ withAllIn1In2Iterators<contiguous_iterator<int*>>();
+}
+
+constexpr bool test() {
+ withAllIteartorPermutations();
+
+ // 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};
+ using Iter = std::array<TracedCopy, 3>::iterator;
+
+ // iterator overload
+ {
+ std::array<TracedCopy, 6> out;
+ std::same_as<std::ranges::merge_result<Iter, Iter, TracedCopy*>> decltype(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}));
+
+ std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; });
+ }
+
+ // range overload
+ {
+ std::array<TracedCopy, 6> out;
+ std::same_as<std::ranges::merge_result<Iter, Iter, TracedCopy*>> decltype(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}));
+
+ std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; });
+ }
+ }
+
+ struct IntAndID {
+ int data;
+ int id;
+
+ constexpr auto operator==(const IntAndID& o) const { return data == o.data; }
+ constexpr auto operator<=>(const IntAndID& o) const { return data <=> o.data; }
+ };
+
+ // Algorithm is stable: equal elements should merged in the original order
+ {
+ std::array<IntAndID, 3> r1{{{0, 0}, {0, 1}, {0, 2}}};
+ std::array<IntAndID, 3> r2{{{1, 0}, {1, 1}, {1, 2}}};
+
+ // iterator overload
+ {
+ std::array<IntAndID, 6> out;
+ std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+ assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, std::ranges::equal_to{}, &IntAndID::data));
+ // ID should be in their original order
+ assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, std::ranges::equal_to{}, &IntAndID::id));
+ }
+
+ // range overload
+ {
+ std::array<IntAndID, 6> out;
+ std::ranges::merge(r1, r2, out.data());
+
+ assert(std::ranges::equal(out, std::array{0, 0, 0, 1, 1, 1}, std::ranges::equal_to{}, &IntAndID::data));
+ // ID should be in their original order
+ assert(std::ranges::equal(out, std::array{0, 1, 2, 0, 1, 2}, std::ranges::equal_to{}, &IntAndID::id));
+ }
+ }
+
+ // Equal elements in R1 should be merged before equal elements in R2
+ {
+ std::array<IntAndID, 3> r1{{{0, 1}, {1, 1}, {2, 1}}};
+ std::array<IntAndID, 3> r2{{{0, 2}, {1, 2}, {2, 2}}};
+
+ // iterator overload
+ {
+ std::array<IntAndID, 6> out;
+ std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+ assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, std::ranges::equal_to{}, &IntAndID::data));
+ // ID 1 (from R1) should be in front of ID 2 (from R2)
+ assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, std::ranges::equal_to{}, &IntAndID::id));
+ }
+
+ // range overload
+ {
+ std::array<IntAndID, 6> out;
+ std::ranges::merge(r1, r2, out.data());
+
+ assert(std::ranges::equal(out, std::array{0, 0, 1, 1, 2, 2}, std::ranges::equal_to{}, &IntAndID::data));
+ // ID 1 (from R1) should be in front of ID 2 (from R2)
+ assert(std::ranges::equal(out, std::array{1, 2, 1, 2, 1, 2}, std::ranges::equal_to{}, &IntAndID::id));
+ }
+ }
+
+ 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{5}, Data{9}};
+ using Iter1 = std::array<Data, 3>::iterator;
+ using Iter2 = std::array<Data, 2>::iterator;
+
+ // iterator overload
+ {
+ std::array<Data, 5> out;
+ std::same_as<std::ranges::merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+ std::ranges::merge(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, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+
+ // range overload
+ {
+ std::array<Data, 5> out;
+ std::same_as<std::ranges::merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+ std::ranges::merge(r1, r2, out.data(), [](const Data& x, const Data& y) { return x.data < y.data; });
+
+ assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+ }
+
+ // Test Projection
+ {
+ std::array r1{Data{4}, Data{8}, Data{12}};
+ std::array r2{Data{5}, Data{9}};
+ using Iter1 = std::array<Data, 3>::iterator;
+ using Iter2 = std::array<Data, 2>::iterator;
+
+ const auto proj = [](const Data& d) { return d.data; };
+
+ // iterator overload
+ {
+ std::array<Data, 5> out;
+ std::same_as<std::ranges::merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+ std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), std::ranges::less{}, proj, proj);
+
+ assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+
+ // range overload
+ {
+ std::array<Data, 5> out;
+ std::same_as<std::ranges::merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+ std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, proj, proj);
+
+ assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+
+ // member pointer Comparator
+ {
+ std::array<Data, 5> out;
+ std::same_as<std::ranges::merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+ std::ranges::merge(r1, r2, out.data(), &Data::smallerThan);
+
+ assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+
+ // member pointer Projection
+ {
+ std::array<Data, 5> out;
+ std::same_as<std::ranges::merge_result<Iter1, Iter2, Data*>> decltype(auto) result =
+ std::ranges::merge(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data);
+
+ assert(std::ranges::equal(out, std::array{4, 5, 8, 9, 12}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+ }
+
+ // Complexity: at most N - 1 comparisons and applications of each projection.
+ {
+ Data r1[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
+ Data r2[] = {{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}};
+ std::array<Data, 20> 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::merge(r1, r2, out.data(), comp, proj1, proj2);
+ assert(std::ranges::equal(
+ out,
+ std::array{0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9},
+ std::ranges::equal_to{},
+ &Data::data));
+ assert(numberOfComp < out.size());
+ assert(numberOfProj1 < out.size());
+ assert(numberOfProj2 < out.size());
+ }
+
+ // Comparator convertible to bool
+ {
+ struct ConvertibleToBool {
+ bool b;
+ constexpr operator bool() const { return b; }
+ };
+ Data r1[] = {{2}, {4}};
+ Data r2[] = {{3}, {4}, {5}};
+ std::array<Data, 5> out;
+
+ const auto comp = [](const Data& x, const Data& y) { return ConvertibleToBool{x.data < y.data}; };
+
+ std::ranges::merge(r1, r2, out.data(), comp);
+ assert(std::ranges::equal(out, std::array{2, 3, 4, 4, 5}, std::ranges::equal_to{}, &Data::data));
+ }
+
+ // One range is empty
+ {
+ auto r1 = std::views::empty<Data>;
+ std::array<Data, 3> r2 = {{{3}, {4}, {5}}};
+
+ // iterator overload
+ {
+ std::array<Data, 3> out;
+ std::same_as<std::ranges::merge_result<Data*, Data*, Data*>> decltype(auto) result =
+ std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.begin() + r2.size(), out.data(), &Data::smallerThan);
+
+ assert(std::ranges::equal(out, std::array{3, 4, 5}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+
+ // range overload
+ {
+ std::array<Data, 3> out;
+ std::same_as<std::ranges::merge_result<Data*, std::array<Data, 3>::iterator, Data*>> decltype(auto) result =
+ std::ranges::merge(r1, r2, out.data(), &Data::smallerThan);
+
+ assert(std::ranges::equal(out, std::array{3, 4, 5}, std::ranges::equal_to{}, &Data::data));
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.end());
+ }
+ }
+
+ // Both ranges are empty
+ {
+ auto r1 = std::views::empty<TracedCopy>;
+ auto r2 = std::views::empty<TracedCopy>;
+
+ // iterator overload
+ {
+ std::array<TracedCopy, 1> out{};
+ std::same_as<std::ranges::merge_result<TracedCopy*, TracedCopy*, TracedCopy*>> decltype(auto) result =
+ std::ranges::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data());
+
+ assert(out[0].copy_assign == 0);
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.begin());
+ }
+
+ // range overload
+ {
+ std::array<TracedCopy, 1> out{};
+ std::same_as<std::ranges::merge_result<TracedCopy*, TracedCopy*, TracedCopy*>> decltype(auto) result =
+ std::ranges::merge(r1, r2, out.data());
+
+ assert(out[0].copy_assign == 0);
+
+ assert(result.in1 == r1.end());
+ assert(result.in2 == r2.end());
+ assert(result.out == out.begin());
+ }
+ }
+
+ return true;
+}
+
+int main(int, char**) {
+ test();
+ static_assert(test());
+
+ return 0;
+}
diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
--- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
+++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp
@@ -98,7 +98,7 @@
//static_assert(test(std::ranges::make_heap, a));
static_assert(test(std::ranges::max, a));
static_assert(test(std::ranges::max_element, a));
-//static_assert(test(std::ranges::merge, a, a, a));
+static_assert(test(std::ranges::merge, a, a, a));
static_assert(test(std::ranges::min, a));
static_assert(test(std::ranges::min_element, a));
static_assert(test(std::ranges::minmax, a));