Upd libc++ to 12 July 2022 81c48436bbd29736f77a111fc207e28854939907

1 files changed, 179 insertions, 2 deletions

diff --git a/contrib/libs/cxxsupp/libcxx/include/algorithm b/contrib/libs/cxxsupp/libcxx/include/algorithm
index adf7e6a417..67741e30d8 100644
--- a/contrib/libs/cxxsupp/libcxx/include/algorithm
+++ b/contrib/libs/cxxsupp/libcxx/include/algorithm
@@ -287,6 +287,49 @@ namespace ranges {
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});                // since C++20
 
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {});                    // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {});                              // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
 
   template<bidirectional_iterator I, sentinel_for<I> S>
     requires permutable<I>
@@ -300,12 +343,22 @@ namespace ranges {
             class Proj = identity>
     requires sortable<I, Comp, Proj>
     constexpr I
-      sort(I first, S last, Comp comp = {}, Proj proj = {});                                // since C++20
+      ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});                        // since C++20
 
   template<random_access_range R, class Comp = ranges::less, class Proj = identity>
     requires sortable<iterator_t<R>, Comp, Proj>
     constexpr borrowed_iterator_t<R>
-      sort(R&& r, Comp comp = {}, Proj proj = {});                                          // since C++20
+      ranges::sort(R&& r, Comp comp = {}, Proj proj = {});                                  // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});                 // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    borrowed_iterator_t<R>
+      ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});                           // since C++20
 
   template<class T, output_iterator<const T&> O, sentinel_for<O> S>
     constexpr O ranges::fill(O first, S last, const T& value);                              // since C++20
@@ -370,6 +423,17 @@ namespace ranges {
     constexpr borrowed_iterator_t<R>
       ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});                       // since C++20
 
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});            // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});          // since C++20
+
   template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
     constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
@@ -484,6 +548,106 @@ namespace ranges {
     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
+
+  template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+    constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});          // since C++20
+
+  template<forward_range R, class T, class Proj = identity>
+    requires permutable<iterator_t<R>> &&
+             indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+    constexpr borrowed_subrange_t<R>
+      ranges::remove(R&& r, const T& value, 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> ranges::remove_if(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>
+      ranges::remove_if(R&& r, Pred pred, Proj proj = {});                                          // 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
+
+  template<class I1, class I2, class O>
+    using set_intersection_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_intersection_result<I1, I2, O>
+      set_intersection(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+                       Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                         // 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_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+      set_intersection(R1&& r1, R2&& r2, O result,
+                       Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                         // since C++20
+
+  template <class _InIter, class _OutIter>
+  using reverse_copy_result = in_out_result<_InIter, _OutIter>;                                     // since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, weakly_incrementable O>
+    requires indirectly_copyable<I, O>
+    constexpr ranges::reverse_copy_result<I, O>
+      ranges::reverse_copy(I first, S last, O result);                                              // since C++20
+
+  template<bidirectional_range R, weakly_incrementable O>
+    requires indirectly_copyable<iterator_t<R>, O>
+    constexpr ranges::reverse_copy_result<borrowed_iterator_t<R>, O>
+      ranges::reverse_copy(R&& r, O result);                                                        // since C++20
+
+  template <class _InIter, class _OutIter>
+  using rotate_copy_result = in_out_result<_InIter, _OutIter>;                                      // since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, weakly_incrementable O>
+    requires indirectly_copyable<I, O>
+    constexpr ranges::rotate_copy_result<I, O>
+      ranges::rotate_copy(I first, I middle, S last, O result);                                     // since C++20
+
+  template<forward_range R, weakly_incrementable O>
+    requires indirectly_copyable<iterator_t<R>, O>
+    constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
+      ranges::rotate_copy(R&& r, iterator_t<R> middle, O result);                                   // since C++20
 
 }
 
@@ -1238,8 +1402,10 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
+#include <__algorithm/ranges_make_heap.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>
@@ -1248,10 +1414,21 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
+#include <__algorithm/ranges_nth_element.h>
+#include <__algorithm/ranges_pop_heap.h>
+#include <__algorithm/ranges_push_heap.h>
+#include <__algorithm/ranges_remove.h>
+#include <__algorithm/ranges_remove_if.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
+#include <__algorithm/ranges_reverse_copy.h>
+#include <__algorithm/ranges_rotate_copy.h>
+#include <__algorithm/ranges_set_difference.h>
+#include <__algorithm/ranges_set_intersection.h>
 #include <__algorithm/ranges_sort.h>
+#include <__algorithm/ranges_sort_heap.h>
+#include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>