[libc++][ranges] implement `std::ranges::inplace_merge`
Differential Revision: https://reviews.llvm.org/D130627
NOKEYCHECK=True
GitOrigin-RevId: 8a61749f767e9af773051fc4f6dc99276fe189e3
diff --git a/include/algorithm b/include/algorithm
index 197b3b1..4fc353a 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -803,7 +803,7 @@
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>
@@ -816,13 +816,13 @@
indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
constexpr subrange<I>
equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
-
+
template<forward_range R, class T, class Proj = identity,
indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
ranges::less>
constexpr borrowed_subrange_t<R>
equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
-
+
template<class I1, class I2, class O>
using set_union_result = in_in_out_result<I1, I2, O>; // since C++20
@@ -847,13 +847,24 @@
ranges::less>
constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20
-
+
template<input_range R1, input_range R2, class Proj1 = identity,
class Proj2 = identity,
indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20
+
+ template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+ class Proj = identity>
+ requires sortable<I, Comp, Proj>
+ I inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {}); // Since C++20
+
+ template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
+ requires sortable<iterator_t<R>, Comp, Proj>
+ borrowed_iterator_t<R>
+ inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {},
+ Proj proj = {}); // Since C++20
}
constexpr bool // constexpr in C++20
@@ -1607,6 +1618,7 @@
#include <__algorithm/ranges_generate.h>
#include <__algorithm/ranges_generate_n.h>
#include <__algorithm/ranges_includes.h>
+#include <__algorithm/ranges_inplace_merge.h>
#include <__algorithm/ranges_is_heap.h>
#include <__algorithm/ranges_is_heap_until.h>
#include <__algorithm/ranges_is_partitioned.h>