commit 4fdeeb171043c780851cb8596d69144f514b13c9
author Konstantin Varlamov <varconst@apple.com> Mon Jul 18 21:05:51 2022 -0700
committer Copybara-Service <copybara-worker@google.com> Mon Jul 18 21:11:15 2022 -0700
tree 15db15b57cba2fc269f95e1e05d6efa4b015895e
parent 5dba0a9451783a0ad32f8dcaf3c4212df4616321

[libc++][ranges] Implement `ranges::{,stable_}partition`.

Differential Revision: https://reviews.llvm.org/D129624

NOKEYCHECK=True
GitOrigin-RevId: 8ed702b83f20d0ec117264a8e7776098ae956250

include/algorithm

diff --git a/include/algorithm b/include/algorithm
index ff700cf..cc2c468 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -464,6 +464,28 @@
              ranges::less>
     constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
                                          Proj proj = {});                                     // since C++20
+
+  template<permutable I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    constexpr subrange<I>
+      partition(I first, S last, Pred pred, Proj proj = {});                                  // Since C++20
+
+  template<forward_range R, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires permutable<iterator_t<R>>
+    constexpr borrowed_subrange_t<R>
+      partition(R&& r, Pred pred, Proj proj = {});                                            // Since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    requires permutable<I>
+    subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {});                 // Since C++20
+
+  template<bidirectional_range R, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires permutable<iterator_t<R>>
+    borrowed_subrange_t<R> stable_partition(R&& r, Pred pred, Proj proj = {});                // Since C++20
+
   template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
            class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
     requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
@@ -1496,6 +1518,7 @@
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_nth_element.h>
+#include <__algorithm/ranges_partition.h>
 #include <__algorithm/ranges_pop_heap.h>
 #include <__algorithm/ranges_push_heap.h>
 #include <__algorithm/ranges_remove.h>
@@ -1513,6 +1536,7 @@
 #include <__algorithm/ranges_set_union.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_sort_heap.h>
+#include <__algorithm/ranges_stable_partition.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>