diff --git a/libcxx/include/__algorithm/pstl_any_all_none_of.h b/libcxx/include/__algorithm/pstl_any_all_none_of.h
--- a/libcxx/include/__algorithm/pstl_any_all_none_of.h
+++ b/libcxx/include/__algorithm/pstl_any_all_none_of.h
@@ -13,7 +13,6 @@
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h
--- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h
@@ -16,7 +16,7 @@
 #include <__atomic/memory_order.h>
 #include <__config>
 #include <__functional/operations.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/pair.h>
 #include <__utility/terminate_on_exception.h>
@@ -67,7 +67,7 @@
 _LIBCPP_HIDE_FROM_ABI bool
 __pstl_any_of(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return std::__parallel_or(
           __first, __last, [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
@@ -76,7 +76,7 @@
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_or(__first, __last - __first, __pred);
   } else {
     return std::any_of(__first, __last, __pred);
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h
--- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.h
@@ -12,7 +12,7 @@
 #include <__algorithm/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/terminate_on_exception.h>
 
@@ -37,7 +37,7 @@
 _LIBCPP_HIDE_FROM_ABI void
 __pstl_fill(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__terminate_on_exception([&] {
       __par_backend::__parallel_for(
           __first, __last, [&__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
@@ -46,7 +46,7 @@
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_fill_n(__first, __last - __first, __value);
   } else {
     std::fill(__first, __last, __value);
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h
--- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h
@@ -14,6 +14,7 @@
 #include <__atomic/atomic.h>
 #include <__config>
 #include <__functional/operations.h>
+#include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/pair.h>
@@ -93,7 +94,7 @@
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 __pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return std::__parallel_find(
           __first,
@@ -106,7 +107,7 @@
           true);
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     using __diff_t = __iter_diff_t<_ForwardIterator>;
     return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
       return __pred(__iter[__i]);
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h
--- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h
@@ -12,7 +12,7 @@
 #include <__algorithm/for_each.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/terminate_on_exception.h>
 
@@ -37,7 +37,7 @@
 _LIBCPP_HIDE_FROM_ABI void
 __pstl_for_each(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Functor __func) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__terminate_on_exception([&] {
       std::__par_backend::__parallel_for(
           __first, __last, [__func](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
@@ -46,7 +46,7 @@
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_walk_1(__first, __last - __first, __func);
   } else {
     std::for_each(__first, __last, __func);
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h
--- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h
@@ -12,7 +12,7 @@
 #include <__algorithm/merge.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/move.h>
 #include <__utility/terminate_on_exception.h>
@@ -39,9 +39,9 @@
     _ForwardOutIterator __result,
     _Comp __comp) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__terminate_on_exception([&] {
       __par_backend::__parallel_merge(
           __first1,
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.h
--- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.h
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.h
@@ -12,6 +12,7 @@
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__algorithm/transform.h>
 #include <__config>
+#include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
@@ -43,8 +44,8 @@
     _ForwardOutIterator __result,
     _UnaryOperation __op) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     std::__terminate_on_exception([&] {
       std::__par_backend::__parallel_for(
           __first, __last, [__op, __first, __result](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
@@ -54,8 +55,8 @@
     });
     return __result + (__last - __first);
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value &&
-                       __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__simd_walk_2(
         __first,
         __last - __first,
@@ -90,9 +91,9 @@
     _ForwardOutIterator __result,
     _BinaryOperation __op) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     std::__terminate_on_exception([&] {
       std::__par_backend::__parallel_for(
           __first1,
@@ -109,9 +110,9 @@
     });
     return __result + (__last1 - __first1);
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                       __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                       __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__simd_walk_3(
         __first1,
         __last1 - __first1,
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h
--- a/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h
@@ -11,6 +11,7 @@
 
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
+#include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__numeric/transform_reduce.h>
 #include <__type_traits/is_arithmetic.h>
@@ -106,8 +107,8 @@
     _BinaryOperation1 __reduce,
     _BinaryOperation2 __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
     return std::__terminate_on_exception([&] {
       return __par_backend::__parallel_transform_reduce(
           __first1,
@@ -130,8 +131,8 @@
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                       __has_random_access_iterator_category<_ForwardIterator2>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
     return std::__simd_transform_reduce(
         __last1 - __first1, std::move(__init), std::move(__reduce), [&](__iter_diff_t<_ForwardIterator1> __i) {
           return __transform(__first1[__i], __first2[__i]);
@@ -156,7 +157,7 @@
     _BinaryOperation __reduce,
     _UnaryOperation __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return __par_backend::__parallel_transform_reduce(
           std::move(__first),
@@ -175,7 +176,7 @@
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_transform_reduce(
         __last - __first,
         std::move(__init),
diff --git a/libcxx/include/__algorithm/pstl_copy.h b/libcxx/include/__algorithm/pstl_copy.h
--- a/libcxx/include/__algorithm/pstl_copy.h
+++ b/libcxx/include/__algorithm/pstl_copy.h
@@ -15,7 +15,7 @@
 #include <__algorithm/pstl_transform.h>
 #include <__config>
 #include <__functional/identity.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_constant_evaluated.h>
 #include <__type_traits/is_execution_policy.h>
@@ -67,7 +67,7 @@
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_copy_n),
       [&__policy](_ForwardIterator __g_first, _Size __g_n, _ForwardOutIterator __g_result) {
-        if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value)
+        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
           return std::copy(__policy, __g_first, __g_first + __g_n, __g_result);
         else
           return std::copy_n(__g_first, __g_n, __g_result);
diff --git a/libcxx/include/__algorithm/pstl_fill.h b/libcxx/include/__algorithm/pstl_fill.h
--- a/libcxx/include/__algorithm/pstl_fill.h
+++ b/libcxx/include/__algorithm/pstl_fill.h
@@ -13,6 +13,7 @@
 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
+#include <__iterator/concepts.h>
 #include <__iterator/cpp17_iterator_concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
@@ -67,7 +68,7 @@
   std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill_n),
       [&](_ForwardIterator __g_first, _SizeT __g_n, const _Tp& __g_value) {
-        if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value)
+        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
           std::fill(__policy, __g_first, __g_first + __g_n, __g_value);
         else
           std::fill_n(__g_first, __g_n, __g_value);
diff --git a/libcxx/include/__algorithm/pstl_find.h b/libcxx/include/__algorithm/pstl_find.h
--- a/libcxx/include/__algorithm/pstl_find.h
+++ b/libcxx/include/__algorithm/pstl_find.h
@@ -15,7 +15,6 @@
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
diff --git a/libcxx/include/__algorithm/pstl_for_each.h b/libcxx/include/__algorithm/pstl_for_each.h
--- a/libcxx/include/__algorithm/pstl_for_each.h
+++ b/libcxx/include/__algorithm/pstl_for_each.h
@@ -14,8 +14,8 @@
 #include <__algorithm/pstl_backend.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
+#include <__iterator/concepts.h>
 #include <__iterator/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
@@ -58,7 +58,7 @@
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n),
       [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) {
-        if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value) {
+        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
           std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
         } else {
           std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));
diff --git a/libcxx/include/__algorithm/pstl_generate.h b/libcxx/include/__algorithm/pstl_generate.h
--- a/libcxx/include/__algorithm/pstl_generate.h
+++ b/libcxx/include/__algorithm/pstl_generate.h
@@ -14,6 +14,7 @@
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
+#include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
diff --git a/libcxx/include/__algorithm/pstl_transform.h b/libcxx/include/__algorithm/pstl_transform.h
--- a/libcxx/include/__algorithm/pstl_transform.h
+++ b/libcxx/include/__algorithm/pstl_transform.h
@@ -12,7 +12,6 @@
 #include <__algorithm/pstl_backend.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
diff --git a/libcxx/include/__iterator/concepts.h b/libcxx/include/__iterator/concepts.h
--- a/libcxx/include/__iterator/concepts.h
+++ b/libcxx/include/__iterator/concepts.h
@@ -295,6 +295,14 @@
 
 #endif // _LIBCPP_STD_VER >= 20
 
+template <class _Tp>
+using __has_random_access_iterator_category_or_concept
+#if _LIBCPP_STD_VER >= 20
+  = integral_constant<bool, random_access_iterator<_Tp>>;
+#else   // _LIBCPP_STD_VER < 20
+  = __has_random_access_iterator_category<_Tp>;
+#endif  // _LIBCPP_STD_VER
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_CONCEPTS_H