Library import 16 (#2433)

Co-authored-by: robot-piglet <robot-piglet@yandex-team.com>
Co-authored-by: deshevoy <deshevoy@yandex-team.com>
Co-authored-by: robot-contrib <robot-contrib@yandex-team.com>
Co-authored-by: thegeorg <thegeorg@yandex-team.com>
Co-authored-by: robot-ya-builder <robot-ya-builder@yandex-team.com>
Co-authored-by: svidyuk <svidyuk@yandex-team.com>
Co-authored-by: shadchin <shadchin@yandex-team.com>
Co-authored-by: robot-ratatosk <robot-ratatosk@yandex-team.com>
Co-authored-by: innokentii <innokentii@yandex-team.com>
Co-authored-by: arkady-e1ppa <arkady-e1ppa@yandex-team.com>
Co-authored-by: snermolaev <snermolaev@yandex-team.com>
Co-authored-by: dimdim11 <dimdim11@yandex-team.com>
Co-authored-by: kickbutt <kickbutt@yandex-team.com>
Co-authored-by: abdullinsaid <abdullinsaid@yandex-team.com>
Co-authored-by: korsunandrei <korsunandrei@yandex-team.com>
Co-authored-by: petrk <petrk@yandex-team.com>
Co-authored-by: miroslav2 <miroslav2@yandex-team.com>
Co-authored-by: serjflint <serjflint@yandex-team.com>
Co-authored-by: akhropov <akhropov@yandex-team.com>
Co-authored-by: prettyboy <prettyboy@yandex-team.com>
Co-authored-by: ilikepugs <ilikepugs@yandex-team.com>
Co-authored-by: hiddenpath <hiddenpath@yandex-team.com>
Co-authored-by: mikhnenko <mikhnenko@yandex-team.com>
Co-authored-by: spreis <spreis@yandex-team.com>
Co-authored-by: andreyshspb <andreyshspb@yandex-team.com>
Co-authored-by: dimaandreev <dimaandreev@yandex-team.com>
Co-authored-by: rashid <rashid@yandex-team.com>
Co-authored-by: robot-ydb-importer <robot-ydb-importer@yandex-team.com>
Co-authored-by: r-vetrov <r-vetrov@yandex-team.com>
Co-authored-by: ypodlesov <ypodlesov@yandex-team.com>
Co-authored-by: zaverden <zaverden@yandex-team.com>
Co-authored-by: vpozdyayev <vpozdyayev@yandex-team.com>
Co-authored-by: robot-cozmo <robot-cozmo@yandex-team.com>
Co-authored-by: v-korovin <v-korovin@yandex-team.com>
Co-authored-by: arikon <arikon@yandex-team.com>
Co-authored-by: khoden <khoden@yandex-team.com>
Co-authored-by: psydmm <psydmm@yandex-team.com>
Co-authored-by: robot-javacom <robot-javacom@yandex-team.com>
Co-authored-by: dtorilov <dtorilov@yandex-team.com>
Co-authored-by: sennikovmv <sennikovmv@yandex-team.com>
Co-authored-by: hcpp <hcpp@ydb.tech>

3 files changed, 67 insertions, 176 deletions

diff --git a/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/algorithm.h b/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/algorithm.h
index 8cbd179072..077093aaef 100644
--- a/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/algorithm.h
+++ b/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/algorithm.h
@@ -31,92 +31,17 @@
 namespace y_absl {
 Y_ABSL_NAMESPACE_BEGIN
 
-namespace algorithm_internal {
-
-// Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.
-struct EqualTo {
-  template <typename T, typename U>
-  bool operator()(const T& a, const U& b) const {
-    return a == b;
-  }
-};
-
-template <typename InputIter1, typename InputIter2, typename Pred>
-bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-               InputIter2 last2, Pred pred, std::input_iterator_tag,
-               std::input_iterator_tag) {
-  while (true) {
-    if (first1 == last1) return first2 == last2;
-    if (first2 == last2) return false;
-    if (!pred(*first1, *first2)) return false;
-    ++first1;
-    ++first2;
-  }
-}
-
-template <typename InputIter1, typename InputIter2, typename Pred>
-bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-               InputIter2 last2, Pred&& pred, std::random_access_iterator_tag,
-               std::random_access_iterator_tag) {
-  return (last1 - first1 == last2 - first2) &&
-         std::equal(first1, last1, first2, std::forward<Pred>(pred));
-}
-
-// When we are using our own internal predicate that just applies operator==, we
-// forward to the non-predicate form of std::equal. This enables an optimization
-// in libstdc++ that can result in std::memcmp being used for integer types.
-template <typename InputIter1, typename InputIter2>
-bool EqualImpl(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-               InputIter2 last2, algorithm_internal::EqualTo /* unused */,
-               std::random_access_iterator_tag,
-               std::random_access_iterator_tag) {
-  return (last1 - first1 == last2 - first2) &&
-         std::equal(first1, last1, first2);
-}
-
-template <typename It>
-It RotateImpl(It first, It middle, It last, std::true_type) {
-  return std::rotate(first, middle, last);
-}
-
-template <typename It>
-It RotateImpl(It first, It middle, It last, std::false_type) {
-  std::rotate(first, middle, last);
-  return std::next(first, std::distance(middle, last));
-}
-
-}  // namespace algorithm_internal
-
 // equal()
+// rotate()
 //
-// Compares the equality of two ranges specified by pairs of iterators, using
-// the given predicate, returning true iff for each corresponding iterator i1
-// and i2 in the first and second range respectively, pred(*i1, *i2) == true
-//
-// This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)
-// invocations of the predicate. Additionally, if InputIter1 and InputIter2 are
-// both random-access iterators, and `last1` - `first1` != `last2` - `first2`,
-// then the predicate is never invoked and the function returns false.
+// Historical note: Abseil once provided implementations of these algorithms
+// prior to their adoption in C++14. New code should prefer to use the std
+// variants.
 //
-// This is a C++11-compatible implementation of C++14 `std::equal`.  See
-// https://en.cppreference.com/w/cpp/algorithm/equal for more information.
-template <typename InputIter1, typename InputIter2, typename Pred>
-bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-           InputIter2 last2, Pred&& pred) {
-  return algorithm_internal::EqualImpl(
-      first1, last1, first2, last2, std::forward<Pred>(pred),
-      typename std::iterator_traits<InputIter1>::iterator_category{},
-      typename std::iterator_traits<InputIter2>::iterator_category{});
-}
-
-// Overload of equal() that performs comparison of two ranges specified by pairs
-// of iterators using operator==.
-template <typename InputIter1, typename InputIter2>
-bool equal(InputIter1 first1, InputIter1 last1, InputIter2 first2,
-           InputIter2 last2) {
-  return y_absl::equal(first1, last1, first2, last2,
-                     algorithm_internal::EqualTo{});
-}
+// See the documentation for the STL <algorithm> header for more information:
+// https://en.cppreference.com/w/cpp/header/algorithm
+using std::equal;
+using std::rotate;
 
 // linear_search()
 //
@@ -133,26 +58,6 @@ bool linear_search(InputIterator first, InputIterator last,
   return std::find(first, last, value) != last;
 }
 
-// rotate()
-//
-// Performs a left rotation on a range of elements (`first`, `last`) such that
-// `middle` is now the first element. `rotate()` returns an iterator pointing to
-// the first element before rotation. This function is exactly the same as
-// `std::rotate`, but fixes a bug in gcc
-// <= 4.9 where `std::rotate` returns `void` instead of an iterator.
-//
-// The complexity of this algorithm is the same as that of `std::rotate`, but if
-// `ForwardIterator` is not a random-access iterator, then `y_absl::rotate`
-// performs an additional pass over the range to construct the return value.
-template <typename ForwardIterator>
-ForwardIterator rotate(ForwardIterator first, ForwardIterator middle,
-                       ForwardIterator last) {
-  return algorithm_internal::RotateImpl(
-      first, middle, last,
-      std::is_same<decltype(std::rotate(first, middle, last)),
-                   ForwardIterator>());
-}
-
 Y_ABSL_NAMESPACE_END
 }  // namespace y_absl
 
diff --git a/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/container.h b/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/container.h
index b97a3fefb0..09864bb868 100644
--- a/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/container.h
+++ b/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/container.h
@@ -52,6 +52,7 @@
 
 #include "y_absl/algorithm/algorithm.h"
 #include "y_absl/base/macros.h"
+#include "y_absl/base/nullability.h"
 #include "y_absl/meta/type_traits.h"
 
 namespace y_absl {
@@ -116,18 +117,6 @@ template <class Key, class Hash, class KeyEqual, class Allocator>
 struct IsUnorderedContainer<std::unordered_set<Key, Hash, KeyEqual, Allocator>>
     : std::true_type {};
 
-// container_algorithm_internal::c_size. It is meant for internal use only.
-
-template <class C>
-auto c_size(C& c) -> decltype(c.size()) {
-  return c.size();
-}
-
-template <class T, std::size_t N>
-constexpr std::size_t c_size(T (&)[N]) {
-  return N;
-}
-
 }  // namespace container_algorithm_internal
 
 // PUBLIC API
@@ -348,20 +337,10 @@ container_algorithm_internal::ContainerDifferenceType<const C> c_count_if(
 template <typename C1, typename C2>
 container_algorithm_internal::ContainerIterPairType<C1, C2> c_mismatch(C1& c1,
                                                                        C2& c2) {
-  auto first1 = container_algorithm_internal::c_begin(c1);
-  auto last1 = container_algorithm_internal::c_end(c1);
-  auto first2 = container_algorithm_internal::c_begin(c2);
-  auto last2 = container_algorithm_internal::c_end(c2);
-
-  for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) {
-    // Negates equality because Cpp17EqualityComparable doesn't require clients
-    // to overload both `operator==` and `operator!=`.
-    if (!(*first1 == *first2)) {
-      break;
-    }
-  }
-
-  return std::make_pair(first1, first2);
+  return std::mismatch(container_algorithm_internal::c_begin(c1),
+                       container_algorithm_internal::c_end(c1),
+                       container_algorithm_internal::c_begin(c2),
+                       container_algorithm_internal::c_end(c2));
 }
 
 // Overload of c_mismatch() for using a predicate evaluation other than `==` as
@@ -370,56 +349,33 @@ container_algorithm_internal::ContainerIterPairType<C1, C2> c_mismatch(C1& c1,
 template <typename C1, typename C2, typename BinaryPredicate>
 container_algorithm_internal::ContainerIterPairType<C1, C2> c_mismatch(
     C1& c1, C2& c2, BinaryPredicate pred) {
-  auto first1 = container_algorithm_internal::c_begin(c1);
-  auto last1 = container_algorithm_internal::c_end(c1);
-  auto first2 = container_algorithm_internal::c_begin(c2);
-  auto last2 = container_algorithm_internal::c_end(c2);
-
-  for (; first1 != last1 && first2 != last2; ++first1, (void)++first2) {
-    if (!pred(*first1, *first2)) {
-      break;
-    }
-  }
-
-  return std::make_pair(first1, first2);
+  return std::mismatch(container_algorithm_internal::c_begin(c1),
+                       container_algorithm_internal::c_end(c1),
+                       container_algorithm_internal::c_begin(c2),
+                       container_algorithm_internal::c_end(c2), pred);
 }
 
 // c_equal()
 //
 // Container-based version of the <algorithm> `std::equal()` function to
 // test whether two containers are equal.
-//
-// NOTE: the semantics of c_equal() are slightly different than those of
-// equal(): while the latter iterates over the second container only up to the
-// size of the first container, c_equal() also checks whether the container
-// sizes are equal.  This better matches expectations about c_equal() based on
-// its signature.
-//
-// Example:
-//   vector v1 = <1, 2, 3>;
-//   vector v2 = <1, 2, 3, 4>;
-//   equal(std::begin(v1), std::end(v1), std::begin(v2)) returns true
-//   c_equal(v1, v2) returns false
-
 template <typename C1, typename C2>
 bool c_equal(const C1& c1, const C2& c2) {
-  return ((container_algorithm_internal::c_size(c1) ==
-           container_algorithm_internal::c_size(c2)) &&
-          std::equal(container_algorithm_internal::c_begin(c1),
-                     container_algorithm_internal::c_end(c1),
-                     container_algorithm_internal::c_begin(c2)));
+  return std::equal(container_algorithm_internal::c_begin(c1),
+                    container_algorithm_internal::c_end(c1),
+                    container_algorithm_internal::c_begin(c2),
+                    container_algorithm_internal::c_end(c2));
 }
 
 // Overload of c_equal() for using a predicate evaluation other than `==` as
 // the function's test condition.
 template <typename C1, typename C2, typename BinaryPredicate>
 bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
-  return ((container_algorithm_internal::c_size(c1) ==
-           container_algorithm_internal::c_size(c2)) &&
-          std::equal(container_algorithm_internal::c_begin(c1),
-                     container_algorithm_internal::c_end(c1),
-                     container_algorithm_internal::c_begin(c2),
-                     std::forward<BinaryPredicate>(pred)));
+  return std::equal(container_algorithm_internal::c_begin(c1),
+                    container_algorithm_internal::c_end(c1),
+                    container_algorithm_internal::c_begin(c2),
+                    container_algorithm_internal::c_end(c2),
+                    std::forward<BinaryPredicate>(pred));
 }
 
 // c_is_permutation()
@@ -428,20 +384,20 @@ bool c_equal(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
 // to test whether a container is a permutation of another.
 template <typename C1, typename C2>
 bool c_is_permutation(const C1& c1, const C2& c2) {
-  using std::begin;
-  using std::end;
-  return c1.size() == c2.size() &&
-         std::is_permutation(begin(c1), end(c1), begin(c2));
+  return std::is_permutation(container_algorithm_internal::c_begin(c1),
+                             container_algorithm_internal::c_end(c1),
+                             container_algorithm_internal::c_begin(c2),
+                             container_algorithm_internal::c_end(c2));
 }
 
 // Overload of c_is_permutation() for using a predicate evaluation other than
 // `==` as the function's test condition.
 template <typename C1, typename C2, typename BinaryPredicate>
 bool c_is_permutation(const C1& c1, const C2& c2, BinaryPredicate&& pred) {
-  using std::begin;
-  using std::end;
-  return c1.size() == c2.size() &&
-         std::is_permutation(begin(c1), end(c1), begin(c2),
+  return std::is_permutation(container_algorithm_internal::c_begin(c1),
+                             container_algorithm_internal::c_end(c1),
+                             container_algorithm_internal::c_begin(c2),
+                             container_algorithm_internal::c_end(c2),
                              std::forward<BinaryPredicate>(pred));
 }
 
@@ -818,6 +774,36 @@ void c_shuffle(RandomAccessContainer& c, UniformRandomBitGenerator&& gen) {
                std::forward<UniformRandomBitGenerator>(gen));
 }
 
+// c_sample()
+//
+// Container-based version of the <algorithm> `std::sample()` function to
+// randomly sample elements from the container without replacement using a
+// `gen()` uniform random number generator and write them to an iterator range.
+template <typename C, typename OutputIterator, typename Distance,
+          typename UniformRandomBitGenerator>
+OutputIterator c_sample(const C& c, OutputIterator result, Distance n,
+                        UniformRandomBitGenerator&& gen) {
+#if defined(__cpp_lib_sample) && __cpp_lib_sample >= 201603L
+  return std::sample(container_algorithm_internal::c_begin(c),
+                     container_algorithm_internal::c_end(c), result, n,
+                     std::forward<UniformRandomBitGenerator>(gen));
+#else
+  // Fall back to a stable selection-sampling implementation.
+  auto first = container_algorithm_internal::c_begin(c);
+  Distance unsampled_elements = c_distance(c);
+  n = (std::min)(n, unsampled_elements);
+  for (; n != 0; ++first) {
+    Distance r =
+        std::uniform_int_distribution<Distance>(0, --unsampled_elements)(gen);
+    if (r < n) {
+      *result++ = *first;
+      --n;
+    }
+  }
+  return result;
+#endif
+}
+
 //------------------------------------------------------------------------------
 // <algorithm> Partition functions
 //------------------------------------------------------------------------------
@@ -1657,7 +1643,7 @@ bool c_prev_permutation(C& c, LessThan&& comp) {
 //
 // Container-based version of the <numeric> `std::iota()` function
 // to compute successive values of `value`, as if incremented with `++value`
-// after each element is written. and write them to the container.
+// after each element is written, and write them to the container.
 template <typename Sequence, typename T>
 void c_iota(Sequence& sequence, const T& value) {
   std::iota(container_algorithm_internal::c_begin(sequence),
diff --git a/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/ya.make b/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/ya.make
index 3b66e3e400..939d073731 100644
--- a/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/ya.make
+++ b/contrib/restricted/abseil-cpp-tstring/y_absl/algorithm/ya.make
@@ -6,9 +6,9 @@ LICENSE(Apache-2.0)
 
 LICENSE_TEXTS(.yandex_meta/licenses.list.txt)
 
-VERSION(20230802.1)
+VERSION(20240116.1)
 
-ORIGINAL_SOURCE(https://github.com/abseil/abseil-cpp/archive/20230802.1.tar.gz)
+ORIGINAL_SOURCE(https://github.com/abseil/abseil-cpp/archive/20240116.1.tar.gz)
 
 NO_RUNTIME()