Commit d9f0fbf983

@@ -13,8 +13,10 @@
 #include <__algorithm/for_each_segment.h>
 #include <__algorithm/min.h>
 #include <__config>
+#include <__fwd/bit_reference.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/segmented_iterator.h>
+#include <__memory/pointer_traits.h>
 #include <__type_traits/common_type.h>
 #include <__type_traits/enable_if.h>
 #include <__utility/move.h>
@@ -29,9 +31,129 @@ _LIBCPP_PUSH_MACROS
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _InputIterator, class _OutputIterator>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
+copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result);
+
 template <class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> __copy(_InIter, _Sent, _OutIter);
 
+template <class _Cp, bool _IsConst>
+_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_aligned(
+    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
+  using _In             = __bit_iterator<_Cp, _IsConst>;
+  using difference_type = typename _In::difference_type;
+  using __storage_type  = typename _In::__storage_type;
+
+  const int __bits_per_word = _In::__bits_per_word;
+  difference_type __n       = __last - __first;
+  if (__n > 0) {
+    // do first word
+    if (__first.__ctz_ != 0) {
+      unsigned __clz       = __bits_per_word - __first.__ctz_;
+      difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
+      __n -= __dn;
+      __storage_type __m = std::__middle_mask<__storage_type>(__clz - __dn, __first.__ctz_);
+      __storage_type __b = *__first.__seg_ & __m;
+      *__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b;
+      __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
+      __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
+      ++__first.__seg_;
+      // __first.__ctz_ = 0;
+    }
+    // __first.__ctz_ == 0;
+    // do middle words
+    __storage_type __nw = __n / __bits_per_word;
+    std::copy(std::__to_address(__first.__seg_),
+              std::__to_address(__first.__seg_ + __nw),
+              std::__to_address(__result.__seg_));
+    __n -= __nw * __bits_per_word;
+    __result.__seg_ += __nw;
+    // do last word
+    if (__n > 0) {
+      __first.__seg_ += __nw;
+      __storage_type __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+      __storage_type __b = *__first.__seg_ & __m;
+      *__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b;
+      __result.__ctz_ = static_cast<unsigned>(__n);
+    }
+  }
+  return __result;
+}
+
+template <class _Cp, bool _IsConst>
+_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_unaligned(
+    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
+  using _In             = __bit_iterator<_Cp, _IsConst>;
+  using difference_type = typename _In::difference_type;
+  using __storage_type  = typename _In::__storage_type;
+
+  const int __bits_per_word = _In::__bits_per_word;
+  difference_type __n       = __last - __first;
+  if (__n > 0) {
+    // do first word
+    if (__first.__ctz_ != 0) {
+      unsigned __clz_f     = __bits_per_word - __first.__ctz_;
+      difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
+      __n -= __dn;
+      __storage_type __m   = std::__middle_mask<__storage_type>(__clz_f - __dn, __first.__ctz_);
+      __storage_type __b   = *__first.__seg_ & __m;
+      unsigned __clz_r     = __bits_per_word - __result.__ctz_;
+      __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
+      __m                  = std::__middle_mask<__storage_type>(__clz_r - __ddn, __result.__ctz_);
+      *__result.__seg_ &= ~__m;
+      if (__result.__ctz_ > __first.__ctz_)
+        *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
+      else
+        *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
+      __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
+      __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
+      __dn -= __ddn;
+      if (__dn > 0) {
+        __m = std::__trailing_mask<__storage_type>(__bits_per_word - __dn);
+        *__result.__seg_ &= ~__m;
+        *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
+        __result.__ctz_ = static_cast<unsigned>(__dn);
+      }
+      ++__first.__seg_;
+      // __first.__ctz_ = 0;
+    }
+    // __first.__ctz_ == 0;
+    // do middle words
+    unsigned __clz_r   = __bits_per_word - __result.__ctz_;
+    __storage_type __m = std::__leading_mask<__storage_type>(__result.__ctz_);
+    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) {
+      __storage_type __b = *__first.__seg_;
+      *__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b << __result.__ctz_;
+      ++__result.__seg_;
+      *__result.__seg_ &= __m;
+      *__result.__seg_ |= __b >> __clz_r;
+    }
+    // do last word
+    if (__n > 0) {
+      __m                 = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+      __storage_type __b  = *__first.__seg_ & __m;
+      __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
+      __m                 = std::__middle_mask<__storage_type>(__clz_r - __dn, __result.__ctz_);
+      *__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b << __result.__ctz_;
+      __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
+      __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
+      __n -= __dn;
+      if (__n > 0) {
+        __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+        *__result.__seg_ &= ~__m;
+        *__result.__seg_ |= __b >> __dn;
+        __result.__ctz_ = static_cast<unsigned>(__n);
+      }
+    }
+  }
+  return __result;
+}
+
 struct __copy_impl {
   template <class _InIter, class _Sent, class _OutIter>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
@@ -95,6 +217,16 @@ struct __copy_impl {
     }
   }
 
+  template <class _Cp, bool _IsConst>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> >
+  operator()(__bit_iterator<_Cp, _IsConst> __first,
+             __bit_iterator<_Cp, _IsConst> __last,
+             __bit_iterator<_Cp, false> __result) const {
+    if (__first.__ctz_ == __result.__ctz_)
+      return std::make_pair(__last, std::__copy_aligned(__first, __last, __result));
+    return std::make_pair(__last, std::__copy_unaligned(__first, __last, __result));
+  }
+
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out, __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
@@ -110,7 +242,7 @@ __copy(_InIter __first, _Sent __last, _OutIter __result) {
 }
 
 template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   return std::__copy(__first, __last, __result).second;
 }

@@ -10,11 +10,14 @@
 #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H
 
 #include <__algorithm/copy_move_common.h>
+#include <__algorithm/copy_n.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/min.h>
 #include <__config>
+#include <__fwd/bit_reference.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/segmented_iterator.h>
+#include <__memory/pointer_traits.h>
 #include <__type_traits/common_type.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_constructible.h>
@@ -34,6 +37,124 @@ template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_InIter, _OutIter>
 __copy_backward(_InIter __first, _Sent __last, _OutIter __result);
 
+template <class _Cp, bool _IsConst>
+_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_aligned(
+    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
+  using _In             = __bit_iterator<_Cp, _IsConst>;
+  using difference_type = typename _In::difference_type;
+  using __storage_type  = typename _In::__storage_type;
+
+  const int __bits_per_word = _In::__bits_per_word;
+  difference_type __n       = __last - __first;
+  if (__n > 0) {
+    // do first word
+    if (__last.__ctz_ != 0) {
+      difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);
+      __n -= __dn;
+      unsigned __clz     = __bits_per_word - __last.__ctz_;
+      __storage_type __m = std::__middle_mask<__storage_type>(__clz, __last.__ctz_ - __dn);
+      __storage_type __b = *__last.__seg_ & __m;
+      *__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b;
+      __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
+      // __last.__ctz_ = 0
+    }
+    // __last.__ctz_ == 0 || __n == 0
+    // __result.__ctz_ == 0 || __n == 0
+    // do middle words
+    __storage_type __nw = __n / __bits_per_word;
+    __result.__seg_ -= __nw;
+    __last.__seg_ -= __nw;
+    std::copy_n(std::__to_address(__last.__seg_), __nw, std::__to_address(__result.__seg_));
+    __n -= __nw * __bits_per_word;
+    // do last word
+    if (__n > 0) {
+      __storage_type __m = std::__leading_mask<__storage_type>(__bits_per_word - __n);
+      __storage_type __b = *--__last.__seg_ & __m;
+      *--__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b;
+      __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
+    }
+  }
+  return __result;
+}
+
+template <class _Cp, bool _IsConst>
+_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, false> __copy_backward_unaligned(
+    __bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) {
+  using _In             = __bit_iterator<_Cp, _IsConst>;
+  using difference_type = typename _In::difference_type;
+  using __storage_type  = typename _In::__storage_type;
+
+  const int __bits_per_word = _In::__bits_per_word;
+  difference_type __n       = __last - __first;
+  if (__n > 0) {
+    // do first word
+    if (__last.__ctz_ != 0) {
+      difference_type __dn = std::min(static_cast<difference_type>(__last.__ctz_), __n);
+      __n -= __dn;
+      unsigned __clz_l     = __bits_per_word - __last.__ctz_;
+      __storage_type __m   = std::__middle_mask<__storage_type>(__clz_l, __last.__ctz_ - __dn);
+      __storage_type __b   = *__last.__seg_ & __m;
+      unsigned __clz_r     = __bits_per_word - __result.__ctz_;
+      __storage_type __ddn = std::min(__dn, static_cast<difference_type>(__result.__ctz_));
+      if (__ddn > 0) {
+        __m = std::__middle_mask<__storage_type>(__clz_r, __result.__ctz_ - __ddn);
+        *__result.__seg_ &= ~__m;
+        if (__result.__ctz_ > __last.__ctz_)
+          *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
+        else
+          *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
+        __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
+        __dn -= __ddn;
+      }
+      if (__dn > 0) {
+        // __result.__ctz_ == 0
+        --__result.__seg_;
+        __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
+        __m             = std::__leading_mask<__storage_type>(__result.__ctz_);
+        *__result.__seg_ &= ~__m;
+        __last.__ctz_ -= __dn + __ddn;
+        *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
+      }
+      // __last.__ctz_ = 0
+    }
+    // __last.__ctz_ == 0 || __n == 0
+    // __result.__ctz_ != 0 || __n == 0
+    // do middle words
+    unsigned __clz_r   = __bits_per_word - __result.__ctz_;
+    __storage_type __m = std::__trailing_mask<__storage_type>(__clz_r);
+    for (; __n >= __bits_per_word; __n -= __bits_per_word) {
+      __storage_type __b = *--__last.__seg_;
+      *__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b >> __clz_r;
+      *--__result.__seg_ &= __m;
+      *__result.__seg_ |= __b << __result.__ctz_;
+    }
+    // do last word
+    if (__n > 0) {
+      __m                 = std::__leading_mask<__storage_type>(__bits_per_word - __n);
+      __storage_type __b  = *--__last.__seg_ & __m;
+      __clz_r             = __bits_per_word - __result.__ctz_;
+      __storage_type __dn = std::min(__n, static_cast<difference_type>(__result.__ctz_));
+      __m                 = std::__middle_mask<__storage_type>(__clz_r, __result.__ctz_ - __dn);
+      *__result.__seg_ &= ~__m;
+      *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
+      __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + __result.__ctz_) % __bits_per_word);
+      __n -= __dn;
+      if (__n > 0) {
+        // __result.__ctz_ == 0
+        --__result.__seg_;
+        __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
+        __m             = std::__leading_mask<__storage_type>(__result.__ctz_);
+        *__result.__seg_ &= ~__m;
+        *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
+      }
+    }
+  }
+  return __result;
+}
+
 template <class _AlgPolicy>
 struct __copy_backward_impl {
   template <class _InIter, class _Sent, class _OutIter>
@@ -107,6 +228,16 @@ struct __copy_backward_impl {
     }
   }
 
+  template <class _Cp, bool _IsConst>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> >
+  operator()(__bit_iterator<_Cp, _IsConst> __first,
+             __bit_iterator<_Cp, _IsConst> __last,
+             __bit_iterator<_Cp, false> __result) {
+    if (__last.__ctz_ == __result.__ctz_)
+      return std::make_pair(__last, std::__copy_backward_aligned(__first, __last, __result));
+    return std::make_pair(__last, std::__copy_backward_unaligned(__first, __last, __result));
+  }
+
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out, __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>

@@ -55,18 +55,18 @@ __count_bool(__bit_iterator<_Cp, _IsConst> __first, typename __size_difference_t
   if (__first.__ctz_ != 0) {
     __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
     __storage_type __dn    = std::min(__clz_f, __n);
-    __storage_type __m     = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
-    __r                    = std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_) & __m);
+    __storage_type __m     = std::__middle_mask<__storage_type>(__clz_f - __dn, __first.__ctz_);
+    __r                    = std::__popcount(__storage_type(std::__invert_if<!_ToCount>(*__first.__seg_) & __m));
     __n -= __dn;
     ++__first.__seg_;
   }
   // do middle whole words
   for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
-    __r += std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_));
+    __r += std::__popcount(std::__invert_if<!_ToCount>(*__first.__seg_));
   // do last partial word
   if (__n > 0) {
-    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
-    __r += std::__libcpp_popcount(std::__invert_if<!_ToCount>(*__first.__seg_) & __m);
+    __storage_type __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+    __r += std::__popcount(__storage_type(std::__invert_if<!_ToCount>(*__first.__seg_) & __m));
   }
   return __r;
 }

@@ -11,16 +11,20 @@
 #define _LIBCPP___ALGORITHM_EQUAL_H
 
 #include <__algorithm/comp.h>
+#include <__algorithm/min.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__functional/identity.h>
+#include <__fwd/bit_reference.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__memory/pointer_traits.h>
 #include <__string/constexpr_c_functions.h>
 #include <__type_traits/desugars_to.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/invoke.h>
 #include <__type_traits/is_equality_comparable.h>
+#include <__type_traits/is_same.h>
 #include <__type_traits/is_volatile.h>
 #include <__utility/move.h>
 
@@ -33,6 +37,140 @@ _LIBCPP_PUSH_MACROS
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Cp, bool _IsConst1, bool _IsConst2>
+[[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool
+__equal_unaligned(__bit_iterator<_Cp, _IsConst1> __first1,
+                  __bit_iterator<_Cp, _IsConst1> __last1,
+                  __bit_iterator<_Cp, _IsConst2> __first2) {
+  using _It             = __bit_iterator<_Cp, _IsConst1>;
+  using difference_type = typename _It::difference_type;
+  using __storage_type  = typename _It::__storage_type;
+
+  const int __bits_per_word = _It::__bits_per_word;
+  difference_type __n       = __last1 - __first1;
+  if (__n > 0) {
+    // do first word
+    if (__first1.__ctz_ != 0) {
+      unsigned __clz_f     = __bits_per_word - __first1.__ctz_;
+      difference_type __dn = std::min(static_cast<difference_type>(__clz_f), __n);
+      __n -= __dn;
+      __storage_type __m   = std::__middle_mask<__storage_type>(__clz_f - __dn, __first1.__ctz_);
+      __storage_type __b   = *__first1.__seg_ & __m;
+      unsigned __clz_r     = __bits_per_word - __first2.__ctz_;
+      __storage_type __ddn = std::min<__storage_type>(__dn, __clz_r);
+      __m                  = std::__middle_mask<__storage_type>(__clz_r - __ddn, __first2.__ctz_);
+      if (__first2.__ctz_ > __first1.__ctz_) {
+        if (static_cast<__storage_type>(*__first2.__seg_ & __m) !=
+            static_cast<__storage_type>(__b << (__first2.__ctz_ - __first1.__ctz_)))
+          return false;
+      } else {
+        if (static_cast<__storage_type>(*__first2.__seg_ & __m) !=
+            static_cast<__storage_type>(__b >> (__first1.__ctz_ - __first2.__ctz_)))
+          return false;
+      }
+      __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
+      __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);
+      __dn -= __ddn;
+      if (__dn > 0) {
+        __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+        if (static_cast<__storage_type>(*__first2.__seg_ & __m) !=
+            static_cast<__storage_type>(__b >> (__first1.__ctz_ + __ddn)))
+          return false;
+        __first2.__ctz_ = static_cast<unsigned>(__dn);
+      }
+      ++__first1.__seg_;
+      // __first1.__ctz_ = 0;
+    }
+    // __first1.__ctz_ == 0;
+    // do middle words
+    unsigned __clz_r   = __bits_per_word - __first2.__ctz_;
+    __storage_type __m = std::__leading_mask<__storage_type>(__first2.__ctz_);
+    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) {
+      __storage_type __b = *__first1.__seg_;
+      if (static_cast<__storage_type>(*__first2.__seg_ & __m) != static_cast<__storage_type>(__b << __first2.__ctz_))
+        return false;
+      ++__first2.__seg_;
+      if (static_cast<__storage_type>(*__first2.__seg_ & static_cast<__storage_type>(~__m)) !=
+          static_cast<__storage_type>(__b >> __clz_r))
+        return false;
+    }
+    // do last word
+    if (__n > 0) {
+      __m                 = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+      __storage_type __b  = *__first1.__seg_ & __m;
+      __storage_type __dn = std::min(__n, static_cast<difference_type>(__clz_r));
+      __m                 = std::__middle_mask<__storage_type>(__clz_r - __dn, __first2.__ctz_);
+      if (static_cast<__storage_type>(*__first2.__seg_ & __m) != static_cast<__storage_type>(__b << __first2.__ctz_))
+        return false;
+      __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
+      __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word);
+      __n -= __dn;
+      if (__n > 0) {
+        __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+        if (static_cast<__storage_type>(*__first2.__seg_ & __m) != static_cast<__storage_type>(__b >> __dn))
+          return false;
+      }
+    }
+  }
+  return true;
+}
+
+template <class _Cp, bool _IsConst1, bool _IsConst2>
+[[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool
+__equal_aligned(__bit_iterator<_Cp, _IsConst1> __first1,
+                __bit_iterator<_Cp, _IsConst1> __last1,
+                __bit_iterator<_Cp, _IsConst2> __first2) {
+  using _It             = __bit_iterator<_Cp, _IsConst1>;
+  using difference_type = typename _It::difference_type;
+  using __storage_type  = typename _It::__storage_type;
+
+  const int __bits_per_word = _It::__bits_per_word;
+  difference_type __n       = __last1 - __first1;
+  if (__n > 0) {
+    // do first word
+    if (__first1.__ctz_ != 0) {
+      unsigned __clz       = __bits_per_word - __first1.__ctz_;
+      difference_type __dn = std::min(static_cast<difference_type>(__clz), __n);
+      __n -= __dn;
+      __storage_type __m = std::__middle_mask<__storage_type>(__clz - __dn, __first1.__ctz_);
+      if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
+        return false;
+      ++__first2.__seg_;
+      ++__first1.__seg_;
+      // __first1.__ctz_ = 0;
+      // __first2.__ctz_ = 0;
+    }
+    // __first1.__ctz_ == 0;
+    // __first2.__ctz_ == 0;
+    // do middle words
+    for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
+      if (*__first2.__seg_ != *__first1.__seg_)
+        return false;
+    // do last word
+    if (__n > 0) {
+      __storage_type __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
+      if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
+        return false;
+    }
+  }
+  return true;
+}
+
+template <class _Cp,
+          bool _IsConst1,
+          bool _IsConst2,
+          class _BinaryPredicate,
+          __enable_if_t<__desugars_to_v<__equal_tag, _BinaryPredicate, bool, bool>, int> = 0>
+[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_iter_impl(
+    __bit_iterator<_Cp, _IsConst1> __first1,
+    __bit_iterator<_Cp, _IsConst1> __last1,
+    __bit_iterator<_Cp, _IsConst2> __first2,
+    _BinaryPredicate) {
+  if (__first1.__ctz_ == __first2.__ctz_)
+    return std::__equal_aligned(__first1, __last1, __first2);
+  return std::__equal_unaligned(__first1, __last1, __first2);
+}
+
 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_iter_impl(
     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate& __pred) {
@@ -94,6 +232,28 @@ __equal_impl(_Tp* __first1, _Tp* __last1, _Up* __first2, _Up*, _Pred&, _Proj1&,
   return std::__constexpr_memcmp_equal(__first1, __first2, __element_count(__last1 - __first1));
 }
 
+template <class _Cp,
+          bool _IsConst1,
+          bool _IsConst2,
+          class _Pred,
+          class _Proj1,
+          class _Proj2,
+          __enable_if_t<__desugars_to_v<__equal_tag, _Pred, bool, bool> && __is_identity<_Proj1>::value &&
+                            __is_identity<_Proj2>::value,
+                        int> = 0>
+[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl(
+    __bit_iterator<_Cp, _IsConst1> __first1,
+    __bit_iterator<_Cp, _IsConst1> __last1,
+    __bit_iterator<_Cp, _IsConst2> __first2,
+    __bit_iterator<_Cp, _IsConst2>,
+    _Pred&,
+    _Proj1&,
+    _Proj2&) {
+  if (__first1.__ctz_ == __first2.__ctz_)
+    return std::__equal_aligned(__first1, __last1, __first2);
+  return std::__equal_unaligned(__first1, __last1, __first2);
+}
+
 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 equal(_InputIterator1 __first1,

@@ -41,11 +41,7 @@ __fill_n_bool(__bit_iterator<_Cp, false> __first, typename __size_difference_typ
   if (__first.__ctz_ != 0) {
     __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
     __storage_type __dn    = std::min(__clz_f, __n);
-    __storage_type __m     = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
-    if (_FillVal)
-      *__first.__seg_ |= __m;
-    else
-      *__first.__seg_ &= ~__m;
+    std::__fill_masked_range(std::__to_address(__first.__seg_), __clz_f - __dn, __first.__ctz_, _FillVal);
     __n -= __dn;
     ++__first.__seg_;
   }
@@ -56,11 +52,7 @@ __fill_n_bool(__bit_iterator<_Cp, false> __first, typename __size_difference_typ
   // do last partial word
   if (__n > 0) {
     __first.__seg_ += __nw;
-    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
-    if (_FillVal)
-      *__first.__seg_ |= __m;
-    else
-      *__first.__seg_ &= ~__m;
+    std::__fill_masked_range(std::__to_address(__first.__seg_), __bits_per_word - __n, 0u, _FillVal);
   }
 }
 

@@ -106,10 +106,10 @@ __find_bool(__bit_iterator<_Cp, _IsConst> __first, typename __size_difference_ty
   if (__first.__ctz_ != 0) {
     __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
     __storage_type __dn    = std::min(__clz_f, __n);
-    __storage_type __m     = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+    __storage_type __m     = std::__middle_mask<__storage_type>(__clz_f - __dn, __first.__ctz_);
     __storage_type __b     = std::__invert_if<!_ToFind>(*__first.__seg_) & __m;
     if (__b)
-      return _It(__first.__seg_, static_cast<unsigned>(std::__libcpp_ctz(__b)));
+      return _It(__first.__seg_, static_cast<unsigned>(std::__countr_zero(__b)));
     if (__n == __dn)
       return __first + __n;
     __n -= __dn;
@@ -119,14 +119,14 @@ __find_bool(__bit_iterator<_Cp, _IsConst> __first, typename __size_difference_ty
   for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) {
     __storage_type __b = std::__invert_if<!_ToFind>(*__first.__seg_);
     if (__b)
-      return _It(__first.__seg_, static_cast<unsigned>(std::__libcpp_ctz(__b)));
+      return _It(__first.__seg_, static_cast<unsigned>(std::__countr_zero(__b)));
   }
   // do last partial word
   if (__n > 0) {
-    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+    __storage_type __m = std::__trailing_mask<__storage_type>(__bits_per_word - __n);
     __storage_type __b = std::__invert_if<!_ToFind>(*__first.__seg_) & __m;
     if (__b)
-      return _It(__first.__seg_, static_cast<unsigned>(std::__libcpp_ctz(__b)));
+      return _It(__first.__seg_, static_cast<unsigned>(std::__countr_zero(__b)));
   }
   return _It(__first.__seg_, static_cast<unsigned>(__n));
 }

@@ -12,9 +12,10 @@
 
 #include <__algorithm/for_each_segment.h>
 #include <__config>
+#include <__functional/identity.h>
 #include <__iterator/segmented_iterator.h>
-#include <__ranges/movable_box.h>
-#include <__utility/in_place.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/invoke.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -26,28 +27,36 @@ _LIBCPP_PUSH_MACROS
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _InputIterator, class _Function>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Function
-for_each(_InputIterator __first, _InputIterator __last, _Function __f) {
+template <class _InputIterator, class _Sent, class _Func, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _InputIterator
+__for_each(_InputIterator __first, _Sent __last, _Func& __f, _Proj& __proj) {
   for (; __first != __last; ++__first)
-    __f(*__first);
-  return __f;
+    std::__invoke(__f, std::__invoke(__proj, *__first));
+  return __first;
 }
 
-// __movable_box is available in C++20, but is actually a copyable-box, so optimization is only correct in C++23
-#if _LIBCPP_STD_VER >= 23
-template <class _SegmentedIterator, class _Function>
-  requires __is_segmented_iterator<_SegmentedIterator>::value
-_LIBCPP_HIDE_FROM_ABI constexpr _Function
-for_each(_SegmentedIterator __first, _SegmentedIterator __last, _Function __func) {
-  ranges::__movable_box<_Function> __wrapped_func(in_place, std::move(__func));
-  std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) {
-    __wrapped_func =
-        ranges::__movable_box<_Function>(in_place, std::for_each(__lfirst, __llast, std::move(*__wrapped_func)));
+#ifndef _LIBCPP_CXX03_LANG
+template <class _SegmentedIterator,
+          class _Func,
+          class _Proj,
+          __enable_if_t<__is_segmented_iterator<_SegmentedIterator>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _SegmentedIterator
+__for_each(_SegmentedIterator __first, _SegmentedIterator __last, _Func& __func, _Proj& __proj) {
+  using __local_iterator_t = typename __segmented_iterator_traits<_SegmentedIterator>::__local_iterator;
+  std::__for_each_segment(__first, __last, [&](__local_iterator_t __lfirst, __local_iterator_t __llast) {
+    std::__for_each(__lfirst, __llast, __func, __proj);
   });
-  return std::move(*__wrapped_func);
+  return __last;
+}
+#endif // !_LIBCPP_CXX03_LANG
+
+template <class _InputIterator, class _Func>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Func
+for_each(_InputIterator __first, _InputIterator __last, _Func __f) {
+  __identity __proj;
+  std::__for_each(__first, __last, __f, __proj);
+  return __f;
 }
-#endif // _LIBCPP_STD_VER >= 23
 
 _LIBCPP_END_NAMESPACE_STD
 

@@ -10,32 +10,93 @@
 #ifndef _LIBCPP___ALGORITHM_FOR_EACH_N_H
 #define _LIBCPP___ALGORITHM_FOR_EACH_N_H
 
+#include <__algorithm/for_each.h>
+#include <__algorithm/for_each_n_segment.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/segmented_iterator.h>
+#include <__type_traits/disjunction.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/invoke.h>
+#include <__type_traits/negation.h>
 #include <__utility/convert_to_integral.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
-_LIBCPP_BEGIN_NAMESPACE_STD
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
 
-#if _LIBCPP_STD_VER >= 17
+_LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _InputIterator, class _Size, class _Function>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _InputIterator
-for_each_n(_InputIterator __first, _Size __orig_n, _Function __f) {
+template <class _InputIterator,
+          class _Size,
+          class _Func,
+          class _Proj,
+          __enable_if_t<!__has_random_access_iterator_category<_InputIterator>::value &&
+                            _Or< _Not<__is_segmented_iterator<_InputIterator> >,
+                                 _Not<__has_random_access_local_iterator<_InputIterator> > >::value,
+                        int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _InputIterator
+__for_each_n(_InputIterator __first, _Size __orig_n, _Func& __f, _Proj& __proj) {
   typedef decltype(std::__convert_to_integral(__orig_n)) _IntegralSize;
   _IntegralSize __n = __orig_n;
   while (__n > 0) {
-    __f(*__first);
+    std::__invoke(__f, std::__invoke(__proj, *__first));
     ++__first;
     --__n;
   }
-  return __first;
+  return std::move(__first);
 }
 
-#endif
+template <class _RandIter,
+          class _Size,
+          class _Func,
+          class _Proj,
+          __enable_if_t<__has_random_access_iterator_category<_RandIter>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandIter
+__for_each_n(_RandIter __first, _Size __orig_n, _Func& __f, _Proj& __proj) {
+  typename std::iterator_traits<_RandIter>::difference_type __n = __orig_n;
+  auto __last                                                   = __first + __n;
+  std::__for_each(__first, __last, __f, __proj);
+  return __last;
+}
+
+#ifndef _LIBCPP_CXX03_LANG
+template <class _SegmentedIterator,
+          class _Size,
+          class _Func,
+          class _Proj,
+          __enable_if_t<!__has_random_access_iterator_category<_SegmentedIterator>::value &&
+                            __is_segmented_iterator<_SegmentedIterator>::value &&
+                            __has_random_access_iterator_category<
+                                typename __segmented_iterator_traits<_SegmentedIterator>::__local_iterator>::value,
+                        int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _SegmentedIterator
+__for_each_n(_SegmentedIterator __first, _Size __orig_n, _Func& __f, _Proj& __proj) {
+  using __local_iterator_t = typename __segmented_iterator_traits<_SegmentedIterator>::__local_iterator;
+  return std::__for_each_n_segment(__first, __orig_n, [&](__local_iterator_t __lfirst, __local_iterator_t __llast) {
+    std::__for_each(__lfirst, __llast, __f, __proj);
+  });
+}
+#endif // !_LIBCPP_CXX03_LANG
+
+#if _LIBCPP_STD_VER >= 17
+
+template <class _InputIterator, class _Size, class _Func>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _InputIterator
+for_each_n(_InputIterator __first, _Size __orig_n, _Func __f) {
+  __identity __proj;
+  return std::__for_each_n(__first, __orig_n, __f, __proj);
+}
+
+#endif // _LIBCPP_STD_VER >= 17
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___ALGORITHM_FOR_EACH_N_H

@@ -0,0 +1,63 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_FOR_EACH_N_SEGMENT_H
+#define _LIBCPP___ALGORITHM_FOR_EACH_N_SEGMENT_H
+
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/segmented_iterator.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// __for_each_n_segment optimizes linear iteration over segmented iterators. It processes a segmented
+// input range [__first, __first + __n) by applying the functor __func to each element within the segment.
+// The return value of __func is ignored, and the function returns an iterator pointing to one past the
+// last processed element in the input range.
+
+template <class _SegmentedIterator, class _Size, class _Functor>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _SegmentedIterator
+__for_each_n_segment(_SegmentedIterator __first, _Size __orig_n, _Functor __func) {
+  static_assert(__is_segmented_iterator<_SegmentedIterator>::value &&
+                    __has_random_access_iterator_category<
+                        typename __segmented_iterator_traits<_SegmentedIterator>::__local_iterator>::value,
+                "__for_each_n_segment only works with segmented iterators with random-access local iterators");
+  if (__orig_n <= 0)
+    return __first;
+
+  using _Traits        = __segmented_iterator_traits<_SegmentedIterator>;
+  using __local_iter_t = typename _Traits::__local_iterator;
+  using __difference_t = typename std::iterator_traits<__local_iter_t>::difference_type;
+  __difference_t __n   = __orig_n;
+  auto __seg           = _Traits::__segment(__first);
+  auto __local_first   = _Traits::__local(__first);
+  __local_iter_t __local_last;
+
+  while (__n > 0) {
+    __local_last    = _Traits::__end(__seg);
+    auto __seg_size = __local_last - __local_first;
+    if (__n <= __seg_size) {
+      __local_last = __local_first + __n;
+      __func(__local_first, __local_last);
+      break;
+    }
+    __func(__local_first, __local_last);
+    __n -= __seg_size;
+    __local_first = _Traits::__begin(++__seg);
+  }
+
+  return _Traits::__compose(__seg, __local_last);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_FOR_EACH_N_SEGMENT_H

@@ -22,6 +22,7 @@
 #include <__functional/identity.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
+#include <__memory/construct_at.h>
 #include <__memory/destruct_n.h>
 #include <__memory/unique_ptr.h>
 #include <__memory/unique_temporary_buffer.h>
@@ -106,13 +107,13 @@ _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __buffered_inplace_merg
     value_type* __p = __buff;
     for (_BidirectionalIterator __i = __first; __i != __middle;
          __d.template __incr<value_type>(), (void)++__i, (void)++__p)
-      ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
+      std::__construct_at(__p, _IterOps<_AlgPolicy>::__iter_move(__i));
     std::__half_inplace_merge<_AlgPolicy>(__buff, __p, __middle, __last, __first, __comp);
   } else {
     value_type* __p = __buff;
     for (_BidirectionalIterator __i = __middle; __i != __last;
          __d.template __incr<value_type>(), (void)++__i, (void)++__p)
-      ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
+      std::__construct_at(__p, _IterOps<_AlgPolicy>::__iter_move(__i));
     typedef reverse_iterator<_BidirectionalIterator> _RBi;
     typedef reverse_iterator<value_type*> _Rv;
     typedef __invert<_Compare> _Inverted;
@@ -203,7 +204,7 @@ _LIBCPP_CONSTEXPR_SINCE_CXX26 void __inplace_merge(
 }
 
 template <class _AlgPolicy, class _BidirectionalIterator, class _Compare>
-_LIBCPP_HIDE_FROM_ABI void __inplace_merge(
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void __inplace_merge(
     _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare&& __comp) {
   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
   typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
@@ -223,14 +224,14 @@ _LIBCPP_HIDE_FROM_ABI void __inplace_merge(
 }
 
 template <class _BidirectionalIterator, class _Compare>
-inline _LIBCPP_HIDE_FROM_ABI void inplace_merge(
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void inplace_merge(
     _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) {
   std::__inplace_merge<_ClassicAlgPolicy>(
       std::move(__first), std::move(__middle), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp));
 }
 
 template <class _BidirectionalIterator>
-inline _LIBCPP_HIDE_FROM_ABI void
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) {
   std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), __less<>());
 }

@@ -29,7 +29,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Comp, class _Iter, class _Sent, class _Proj>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter
-__min_element(_Iter __first, _Sent __last, _Comp __comp, _Proj& __proj) {
+__min_element(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
   if (__first == __last)
     return __first;
 

@@ -9,11 +9,13 @@
 #ifndef _LIBCPP___ALGORITHM_MOVE_H
 #define _LIBCPP___ALGORITHM_MOVE_H
 
+#include <__algorithm/copy.h>
 #include <__algorithm/copy_move_common.h>
 #include <__algorithm/for_each_segment.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/min.h>
 #include <__config>
+#include <__fwd/bit_reference.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/segmented_iterator.h>
 #include <__type_traits/common_type.h>
@@ -98,6 +100,14 @@ struct __move_impl {
     }
   }
 
+  template <class _Cp, bool _IsConst>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> >
+  operator()(__bit_iterator<_Cp, _IsConst> __first,
+             __bit_iterator<_Cp, _IsConst> __last,
+             __bit_iterator<_Cp, false> __result) {
+    return std::__copy(__first, __last, __result);
+  }
+
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out, __enable_if_t<__can_lower_move_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>

@@ -9,10 +9,12 @@
 #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H
 #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H
 
+#include <__algorithm/copy_backward.h>
 #include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/min.h>
 #include <__config>
+#include <__fwd/bit_reference.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/segmented_iterator.h>
 #include <__type_traits/common_type.h>
@@ -107,6 +109,14 @@ struct __move_backward_impl {
     }
   }
 
+  template <class _Cp, bool _IsConst>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> >
+  operator()(__bit_iterator<_Cp, _IsConst> __first,
+             __bit_iterator<_Cp, _IsConst> __last,
+             __bit_iterator<_Cp, false> __result) {
+    return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result);
+  }
+
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out, __enable_if_t<__can_lower_move_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>

@@ -0,0 +1,56 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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_OUT_VALUE_RESULT_H
+#define _LIBCPP___ALGORITHM_OUT_VALUE_RESULT_H
+
+#include <__concepts/convertible_to.h>
+#include <__config>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER >= 23
+
+namespace ranges {
+
+template <class _OutIter1, class _ValType1>
+struct out_value_result {
+  _LIBCPP_NO_UNIQUE_ADDRESS _OutIter1 out;
+  _LIBCPP_NO_UNIQUE_ADDRESS _ValType1 value;
+
+  template <class _OutIter2, class _ValType2>
+    requires convertible_to<const _OutIter1&, _OutIter2> && convertible_to<const _ValType1&, _ValType2>
+  _LIBCPP_HIDE_FROM_ABI constexpr operator out_value_result<_OutIter2, _ValType2>() const& {
+    return {out, value};
+  }
+
+  template <class _OutIter2, class _ValType2>
+    requires convertible_to<_OutIter1, _OutIter2> && convertible_to<_ValType1, _ValType2>
+  _LIBCPP_HIDE_FROM_ABI constexpr operator out_value_result<_OutIter2, _ValType2>() && {
+    return {std::move(out), std::move(value)};
+  }
+};
+
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER >= 23
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_OUT_VALUE_RESULT_H

@@ -29,10 +29,12 @@
 
 #include <__algorithm/for_each.h>
 #include <__algorithm/move.h>
+#include <__bit/bit_cast.h>
 #include <__bit/bit_log2.h>
-#include <__bit/countl.h>
 #include <__config>
+#include <__cstddef/size_t.h>
 #include <__functional/identity.h>
+#include <__iterator/access.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/move_iterator.h>
@@ -43,9 +45,12 @@
 #include <__type_traits/enable_if.h>
 #include <__type_traits/invoke.h>
 #include <__type_traits/is_assignable.h>
+#include <__type_traits/is_enum.h>
 #include <__type_traits/is_integral.h>
 #include <__type_traits/is_unsigned.h>
 #include <__type_traits/make_unsigned.h>
+#include <__type_traits/void_t.h>
+#include <__utility/declval.h>
 #include <__utility/forward.h>
 #include <__utility/integer_sequence.h>
 #include <__utility/move.h>
@@ -67,7 +72,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 #if _LIBCPP_STD_VER >= 14
 
 template <class _InputIterator, class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI pair<_OutputIterator, __iter_value_type<_InputIterator>>
+_LIBCPP_HIDE_FROM_ABI constexpr pair<_OutputIterator, __iter_value_type<_InputIterator>>
 __partial_sum_max(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   if (__first == __last)
     return {__result, 0};
@@ -109,7 +114,7 @@ struct __counting_sort_traits {
 };
 
 template <class _Radix, class _Integer>
-_LIBCPP_HIDE_FROM_ABI auto __nth_radix(size_t __radix_number, _Radix __radix, _Integer __n) {
+_LIBCPP_HIDE_FROM_ABI constexpr auto __nth_radix(size_t __radix_number, _Radix __radix, _Integer __n) {
   static_assert(is_unsigned<_Integer>::value);
   using __traits = __counting_sort_traits<_Integer, _Radix>;
 
@@ -117,7 +122,7 @@ _LIBCPP_HIDE_FROM_ABI auto __nth_radix(size_t __radix_number, _Radix __radix, _I
 }
 
 template <class _ForwardIterator, class _Map, class _RandomAccessIterator>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI constexpr void
 __collect(_ForwardIterator __first, _ForwardIterator __last, _Map __map, _RandomAccessIterator __counters) {
   using __value_type = __iter_value_type<_ForwardIterator>;
   using __traits     = __counting_sort_traits<__value_type, _Map>;
@@ -129,7 +134,7 @@ __collect(_ForwardIterator __first, _ForwardIterator __last, _Map __map, _Random
 }
 
 template <class _ForwardIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI constexpr void
 __dispose(_ForwardIterator __first,
           _ForwardIterator __last,
           _RandomAccessIterator1 __result,
@@ -147,7 +152,7 @@ template <class _ForwardIterator,
           class _RandomAccessIterator1,
           class _RandomAccessIterator2,
           size_t... _Radices>
-_LIBCPP_HIDE_FROM_ABI bool __collect_impl(
+_LIBCPP_HIDE_FROM_ABI constexpr bool __collect_impl(
     _ForwardIterator __first,
     _ForwardIterator __last,
     _Map __map,
@@ -177,7 +182,7 @@ _LIBCPP_HIDE_FROM_ABI bool __collect_impl(
 }
 
 template <class _ForwardIterator, class _Map, class _Radix, class _RandomAccessIterator1, class _RandomAccessIterator2>
-_LIBCPP_HIDE_FROM_ABI bool
+_LIBCPP_HIDE_FROM_ABI constexpr bool
 __collect(_ForwardIterator __first,
           _ForwardIterator __last,
           _Map __map,
@@ -191,7 +196,7 @@ __collect(_ForwardIterator __first,
 }
 
 template <class _BidirectionalIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>
-_LIBCPP_HIDE_FROM_ABI void __dispose_backward(
+_LIBCPP_HIDE_FROM_ABI constexpr void __dispose_backward(
     _BidirectionalIterator __first,
     _BidirectionalIterator __last,
     _RandomAccessIterator1 __result,
@@ -206,7 +211,7 @@ _LIBCPP_HIDE_FROM_ABI void __dispose_backward(
 }
 
 template <class _ForwardIterator, class _RandomAccessIterator, class _Map>
-_LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
+_LIBCPP_HIDE_FROM_ABI constexpr _RandomAccessIterator
 __counting_sort_impl(_ForwardIterator __first, _ForwardIterator __last, _RandomAccessIterator __result, _Map __map) {
   using __value_type = __iter_value_type<_ForwardIterator>;
   using __traits     = __counting_sort_traits<__value_type, _Map>;
@@ -225,7 +230,7 @@ template <class _RandomAccessIterator1,
           class _Radix,
           enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count == 1,
                        int> = 0>
-_LIBCPP_HIDE_FROM_ABI void __radix_sort_impl(
+_LIBCPP_HIDE_FROM_ABI constexpr void __radix_sort_impl(
     _RandomAccessIterator1 __first,
     _RandomAccessIterator1 __last,
     _RandomAccessIterator2 __buffer,
@@ -245,7 +250,7 @@ template <
     class _Radix,
     enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count % 2 == 0,
                  int> = 0 >
-_LIBCPP_HIDE_FROM_ABI void __radix_sort_impl(
+_LIBCPP_HIDE_FROM_ABI constexpr void __radix_sort_impl(
     _RandomAccessIterator1 __first,
     _RandomAccessIterator1 __last,
     _RandomAccessIterator2 __buffer_begin,
@@ -297,6 +302,96 @@ _LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(_Ip __n) {
   return static_cast<make_unsigned_t<_Ip> >(__n ^ __min_value);
 }
 
+template <size_t _Size>
+struct __unsigned_integer_of_size;
+
+template <>
+struct __unsigned_integer_of_size<1> {
+  using type _LIBCPP_NODEBUG = uint8_t;
+};
+
+template <>
+struct __unsigned_integer_of_size<2> {
+  using type _LIBCPP_NODEBUG = uint16_t;
+};
+
+template <>
+struct __unsigned_integer_of_size<4> {
+  using type _LIBCPP_NODEBUG = uint32_t;
+};
+
+template <>
+struct __unsigned_integer_of_size<8> {
+  using type _LIBCPP_NODEBUG = uint64_t;
+};
+
+#  if _LIBCPP_HAS_INT128
+template <>
+struct __unsigned_integer_of_size<16> {
+  using type _LIBCPP_NODEBUG = unsigned __int128;
+};
+#  endif
+
+template <size_t _Size>
+using __unsigned_integer_of_size_t _LIBCPP_NODEBUG = typename __unsigned_integer_of_size<_Size>::type;
+
+template <class _Sc>
+using __unsigned_representation_for_t _LIBCPP_NODEBUG = __unsigned_integer_of_size_t<sizeof(_Sc)>;
+
+// The function `__to_ordered_integral` is defined for integers and IEEE 754 floating-point numbers.
+// Returns an integer representation such that for any `x` and `y` such that `x < y`, the expression
+// `__to_ordered_integral(x) < __to_ordered_integral(y)` is true, where `x`, `y` are integers or IEEE 754 floats.
+template <class _Integral, enable_if_t< is_integral<_Integral>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Integral __n) {
+  return __n;
+}
+
+// An overload for IEEE 754 floating-point numbers
+
+// For the floats conforming to IEEE 754 (IEC 559) standard, we know that:
+// 1. The bit representation of positive floats directly reflects their order:
+//    When comparing floats by magnitude, the number with the larger exponent is greater, and if the exponents are
+//    equal, the one with the larger mantissa is greater.
+// 2. The bit representation of negative floats reflects their reverse order (for the same reasons).
+// 3. The most significant bit (sign bit) is zero for positive floats and one for negative floats. Therefore, in the raw
+//    bit representation, any negative number will be greater than any positive number.
+
+// The only exception from this rule is `NaN`, which is unordered by definition.
+
+// Based on the above, to obtain correctly ordered integral representation of floating-point numbers, we need to:
+// 1. Invert the bit representation (including the sign bit) of negative floats to switch from reverse order to direct
+//    order;
+// 2. Invert the sign bit for positive floats.
+
+// Thus, in final integral representation, we have reversed the order for negative floats and made all negative floats
+// smaller than all positive numbers (by inverting the sign bit).
+template <class _Floating, enable_if_t< numeric_limits<_Floating>::is_iec559, int> = 0>
+_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Floating __f) {
+  using __integral_type          = __unsigned_representation_for_t<_Floating>;
+  constexpr auto __bit_count     = std::numeric_limits<__integral_type>::digits;
+  constexpr auto __sign_bit_mask = static_cast<__integral_type>(__integral_type{1} << (__bit_count - 1));
+
+  const auto __u = std::__bit_cast<__integral_type>(__f);
+
+  return static_cast<__integral_type>(__u & __sign_bit_mask ? ~__u : __u ^ __sign_bit_mask);
+}
+
+// There may exist user-defined comparison for enum, so we cannot compare enums just like integers.
+template <class _Enum, enable_if_t< is_enum<_Enum>::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Enum __e) = delete;
+
+// `long double` varies significantly across platforms and compilers, making it practically
+// impossible to determine its actual bit width for conversion to an ordered integer.
+inline _LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(long double) = delete;
+
+template <class _Tp, class = void>
+inline const bool __is_ordered_integer_representable_v = false;
+
+template <class _Tp>
+inline const bool
+    __is_ordered_integer_representable_v<_Tp, __void_t<decltype(std::__to_ordered_integral(std::declval<_Tp>()))>> =
+        true;
+
 struct __low_byte_fn {
   template <class _Ip>
   _LIBCPP_HIDE_FROM_ABI constexpr uint8_t operator()(_Ip __integer) const {
@@ -307,18 +402,20 @@ struct __low_byte_fn {
 };
 
 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Map, class _Radix>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI constexpr void
 __radix_sort(_RandomAccessIterator1 __first,
              _RandomAccessIterator1 __last,
              _RandomAccessIterator2 __buffer,
              _Map __map,
              _Radix __radix) {
-  auto __map_to_unsigned = [__map = std::move(__map)](const auto& __x) { return std::__shift_to_unsigned(__map(__x)); };
+  auto __map_to_unsigned = [__map = std::move(__map)](const auto& __x) {
+    return std::__shift_to_unsigned(__map(std::__to_ordered_integral(__x)));
+  };
   std::__radix_sort_impl(__first, __last, __buffer, __map_to_unsigned, __radix);
 }
 
 template <class _RandomAccessIterator1, class _RandomAccessIterator2>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI constexpr void
 __radix_sort(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __buffer) {
   std::__radix_sort(__first, __last, __buffer, __identity{}, __low_byte_fn{});
 }

@@ -9,10 +9,12 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_FOR_EACH_H
 #define _LIBCPP___ALGORITHM_RANGES_FOR_EACH_H
 
+#include <__algorithm/for_each.h>
+#include <__algorithm/for_each_n.h>
 #include <__algorithm/in_fun_result.h>
+#include <__concepts/assignable.h>
 #include <__config>
 #include <__functional/identity.h>
-#include <__functional/invoke.h>
 #include <__iterator/concepts.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>
@@ -41,9 +43,17 @@ private:
   template <class _Iter, class _Sent, class _Proj, class _Func>
   _LIBCPP_HIDE_FROM_ABI constexpr static for_each_result<_Iter, _Func>
   __for_each_impl(_Iter __first, _Sent __last, _Func& __func, _Proj& __proj) {
-    for (; __first != __last; ++__first)
-      std::invoke(__func, std::invoke(__proj, *__first));
-    return {std::move(__first), std::move(__func)};
+    // In the case where we have different iterator and sentinel types, the segmented iterator optimization
+    // in std::for_each will not kick in. Therefore, we prefer std::for_each_n in that case (whenever we can
+    // obtain the `n`).
+    if constexpr (!std::assignable_from<_Iter&, _Sent> && std::sized_sentinel_for<_Sent, _Iter>) {
+      auto __n   = __last - __first;
+      auto __end = std::__for_each_n(std::move(__first), __n, __func, __proj);
+      return {std::move(__end), std::move(__func)};
+    } else {
+      auto __end = std::__for_each(std::move(__first), std::move(__last), __func, __proj);
+      return {std::move(__end), std::move(__func)};
+    }
   }
 
 public:

@@ -9,10 +9,10 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_FOR_EACH_N_H
 #define _LIBCPP___ALGORITHM_RANGES_FOR_EACH_N_H
 
+#include <__algorithm/for_each_n.h>
 #include <__algorithm/in_fun_result.h>
 #include <__config>
 #include <__functional/identity.h>
-#include <__functional/invoke.h>
 #include <__iterator/concepts.h>
 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
@@ -40,11 +40,8 @@ struct __for_each_n {
   template <input_iterator _Iter, class _Proj = identity, indirectly_unary_invocable<projected<_Iter, _Proj>> _Func>
   _LIBCPP_HIDE_FROM_ABI constexpr for_each_n_result<_Iter, _Func>
   operator()(_Iter __first, iter_difference_t<_Iter> __count, _Func __func, _Proj __proj = {}) const {
-    while (__count-- > 0) {
-      std::invoke(__func, std::invoke(__proj, *__first));
-      ++__first;
-    }
-    return {std::move(__first), std::move(__func)};
+    auto __last = std::__for_each_n(std::move(__first), __count, __func, __proj);
+    return {std::move(__last), std::move(__func)};
   }
 };
 

@@ -41,7 +41,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 namespace ranges {
 struct __inplace_merge {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
-  _LIBCPP_HIDE_FROM_ABI static constexpr auto
+  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_SINCE_CXX26 auto
   __inplace_merge_impl(_Iter __first, _Iter __middle, _Sent __last, _Comp&& __comp, _Proj&& __proj) {
     auto __last_iter = ranges::next(__middle, __last);
     std::__inplace_merge<_RangeAlgPolicy>(
@@ -51,7 +51,7 @@ struct __inplace_merge {
 
   template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
-  _LIBCPP_HIDE_FROM_ABI _Iter
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _Iter
   operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
     return __inplace_merge_impl(
         std::move(__first), std::move(__middle), std::move(__last), std::move(__comp), std::move(__proj));
@@ -59,7 +59,7 @@ struct __inplace_merge {
 
   template <bidirectional_range _Range, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<iterator_t<_Range>, _Comp, _Proj>
-  _LIBCPP_HIDE_FROM_ABI borrowed_iterator_t<_Range>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 borrowed_iterator_t<_Range>
   operator()(_Range&& __range, iterator_t<_Range> __middle, _Comp __comp = {}, _Proj __proj = {}) const {
     return __inplace_merge_impl(
         ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__comp), std::move(__proj));

@@ -44,7 +44,7 @@ consteval auto __get_iterator_concept() {
 }
 
 template <class _Iter>
-using __iterator_concept _LIBCPP_NODEBUG = decltype(__get_iterator_concept<_Iter>());
+using __iterator_concept _LIBCPP_NODEBUG = decltype(ranges::__get_iterator_concept<_Iter>());
 
 } // namespace ranges
 _LIBCPP_END_NAMESPACE_STD

@@ -9,7 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_MAX_H
 #define _LIBCPP___ALGORITHM_RANGES_MAX_H
 
-#include <__algorithm/ranges_min_element.h>
+#include <__algorithm/min_element.h>
 #include <__assert>
 #include <__concepts/copyable.h>
 #include <__config>
@@ -57,7 +57,7 @@ struct __max {
         __il.begin() != __il.end(), "initializer_list must contain at least one element");
 
     auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) -> bool { return std::invoke(__comp, __rhs, __lhs); };
-    return *ranges::__min_element_impl(__il.begin(), __il.end(), __comp_lhs_rhs_swapped, __proj);
+    return *std::__min_element(__il.begin(), __il.end(), __comp_lhs_rhs_swapped, __proj);
   }
 
   template <input_range _Rp,
@@ -75,7 +75,7 @@ struct __max {
       auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) -> bool {
         return std::invoke(__comp, __rhs, __lhs);
       };
-      return *ranges::__min_element_impl(std::move(__first), std::move(__last), __comp_lhs_rhs_swapped, __proj);
+      return *std::__min_element(std::move(__first), std::move(__last), __comp_lhs_rhs_swapped, __proj);
     } else {
       range_value_t<_Rp> __result = *__first;
       while (++__first != __last) {