[libc++] Refactor deque::iterator algorithm optimizations

This has multiple benefits:
- The optimizations are also performed for the `ranges::` versions of the algorithms
- Code duplication is reduced
- it is simpler to add this optimization for other segmented iterators,
  like `ranges::join_view::iterator`
- Algorithm code is removed from `<deque>`

Reviewed By: ldionne, huixie90, #libc

Spies: mstorsjo, sstefan1, EricWF, libcxx-commits, mgorny

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

21 files changed, 953 insertions, 682 deletions

diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt
index a792230..fbc5144 100644
--- a/libcxx/benchmarks/CMakeLists.txt
+++ b/libcxx/benchmarks/CMakeLists.txt
@@ -176,6 +176,7 @@ set(BENCHMARK_TESTS
     algorithms/stable_sort.bench.cpp
     allocation.bench.cpp
     deque.bench.cpp
+    deque_iterator.bench.cpp
     filesystem.bench.cpp
     format_to_n.bench.cpp
     format_to.bench.cpp
diff --git a/libcxx/benchmarks/deque_iterator.bench.cpp b/libcxx/benchmarks/deque_iterator.bench.cpp
new file mode 100644
index 0000000..0eb23f2
--- /dev/null
+++ b/libcxx/benchmarks/deque_iterator.bench.cpp
@@ -0,0 +1,232 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <deque>
+
+#include "benchmark/benchmark.h"
+
+namespace {
+void run_sizes(auto benchmark) {
+  benchmark->Arg(0)
+      ->Arg(1)
+      ->Arg(2)
+      ->Arg(64)
+      ->Arg(512)
+      ->Arg(1024)
+      ->Arg(4000)
+      ->Arg(4096)
+      ->Arg(5500)
+      ->Arg(64000)
+      ->Arg(65536)
+      ->Arg(70000);
+}
+
+template <class FromContainer, class ToContainer, class Func>
+void benchmark_containers(benchmark::State& state, FromContainer& d, ToContainer& v, Func&& func) {
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(v);
+    benchmark::DoNotOptimize(d);
+    func(d.begin(), d.end(), v.begin());
+  }
+}
+
+template <class Func>
+void benchmark_deque_vector(benchmark::State& state, Func&& func) {
+  auto size = state.range(0);
+  std::deque<int> d;
+  d.resize(size);
+  std::ranges::fill(d, 10);
+  std::vector<int> v;
+  v.resize(size);
+  benchmark_containers(state, d, v, func);
+}
+
+template <class Func>
+void benchmark_deque_deque(benchmark::State& state, Func&& func) {
+  auto size = state.range(0);
+  std::deque<int> d;
+  d.resize(size);
+  std::ranges::fill(d, 10);
+  std::deque<int> v;
+  v.resize(size);
+  benchmark_containers(state, d, v, func);
+}
+
+template <class Func>
+void benchmark_vector_deque(benchmark::State& state, Func&& func) {
+  auto size = state.range(0);
+  std::vector<int> d;
+  d.resize(size);
+  std::ranges::fill(d, 10);
+  std::deque<int> v;
+  v.resize(size);
+  benchmark_containers(state, d, v, func);
+}
+
+template <class FromContainer, class ToContainer, class Func>
+void benchmark_containers_backward(benchmark::State& state, FromContainer& d, ToContainer& v, Func&& func) {
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(v);
+    benchmark::DoNotOptimize(d);
+    func(d.begin(), d.end(), v.end());
+  }
+}
+
+template <class Func>
+void benchmark_deque_vector_backward(benchmark::State& state, Func&& func) {
+  auto size = state.range(0);
+  std::deque<int> d;
+  d.resize(size);
+  std::ranges::fill(d, 10);
+  std::vector<int> v;
+  v.resize(size);
+  benchmark_containers_backward(state, d, v, func);
+}
+
+template <class Func>
+void benchmark_deque_deque_backward(benchmark::State& state, Func&& func) {
+  auto size = state.range(0);
+  std::deque<int> d;
+  d.resize(size);
+  std::ranges::fill(d, 10);
+  std::deque<int> v;
+  v.resize(size);
+  benchmark_containers_backward(state, d, v, func);
+}
+
+template <class Func>
+void benchmark_vector_deque_backward(benchmark::State& state, Func&& func) {
+  auto size = state.range(0);
+  std::vector<int> d;
+  d.resize(size);
+  std::ranges::fill(d, 10);
+  std::deque<int> v;
+  v.resize(size);
+  benchmark_containers_backward(state, d, v, func);
+}
+
+struct CopyFunctor {
+  template <class... Args>
+  auto operator()(Args... args) const {
+    std::copy(std::forward<Args>(args)...);
+  }
+} copy;
+
+struct MoveFunctor {
+  template <class... Args>
+  auto operator()(Args... args) const {
+    std::move(std::forward<Args>(args)...);
+  }
+} move;
+
+struct CopyBackwardFunctor {
+  template <class... Args>
+  auto operator()(Args... args) const {
+    std::copy_backward(std::forward<Args>(args)...);
+  }
+} copy_backward;
+
+struct MoveBackwardFunctor {
+  template <class... Args>
+  auto operator()(Args... args) const {
+    std::move_backward(std::forward<Args>(args)...);
+  }
+} move_backward;
+
+// copy
+void BM_deque_vector_copy(benchmark::State& state) { benchmark_deque_vector(state, copy); }
+BENCHMARK(BM_deque_vector_copy)->Apply(run_sizes);
+
+void BM_deque_vector_ranges_copy(benchmark::State& state) { benchmark_deque_vector(state, std::ranges::copy); }
+BENCHMARK(BM_deque_vector_ranges_copy)->Apply(run_sizes);
+
+void BM_deque_deque_copy(benchmark::State& state) { benchmark_deque_deque(state, copy); }
+BENCHMARK(BM_deque_deque_copy)->Apply(run_sizes);
+
+void BM_deque_deque_ranges_copy(benchmark::State& state) { benchmark_deque_deque(state, std::ranges::copy); }
+BENCHMARK(BM_deque_deque_ranges_copy)->Apply(run_sizes);
+
+void BM_vector_deque_copy(benchmark::State& state) { benchmark_vector_deque(state, copy); }
+BENCHMARK(BM_vector_deque_copy)->Apply(run_sizes);
+
+void BM_vector_deque_ranges_copy(benchmark::State& state) { benchmark_vector_deque(state, std::ranges::copy); }
+BENCHMARK(BM_vector_deque_ranges_copy)->Apply(run_sizes);
+
+// move
+void BM_deque_vector_move(benchmark::State& state) { benchmark_deque_vector(state, move); }
+BENCHMARK(BM_deque_vector_move)->Apply(run_sizes);
+
+void BM_deque_vector_ranges_move(benchmark::State& state) { benchmark_deque_vector(state, std::ranges::move); }
+BENCHMARK(BM_deque_vector_ranges_move)->Apply(run_sizes);
+
+void BM_deque_deque_move(benchmark::State& state) { benchmark_deque_deque(state, move); }
+BENCHMARK(BM_deque_deque_move)->Apply(run_sizes);
+
+void BM_deque_deque_ranges_move(benchmark::State& state) { benchmark_deque_deque(state, std::ranges::move); }
+BENCHMARK(BM_deque_deque_ranges_move)->Apply(run_sizes);
+
+void BM_vector_deque_move(benchmark::State& state) { benchmark_vector_deque(state, move); }
+BENCHMARK(BM_vector_deque_move)->Apply(run_sizes);
+
+void BM_vector_deque_ranges_move(benchmark::State& state) { benchmark_vector_deque(state, std::ranges::move); }
+BENCHMARK(BM_vector_deque_ranges_move)->Apply(run_sizes);
+
+// copy_backward
+void BM_deque_vector_copy_backward(benchmark::State& state) { benchmark_deque_vector_backward(state, copy_backward); }
+BENCHMARK(BM_deque_vector_copy_backward)->Apply(run_sizes);
+
+void BM_deque_vector_ranges_copy_backward(benchmark::State& state) {
+  benchmark_deque_vector_backward(state, std::ranges::copy_backward);
+}
+BENCHMARK(BM_deque_vector_ranges_copy_backward)->Apply(run_sizes);
+
+void BM_deque_deque_copy_backward(benchmark::State& state) { benchmark_deque_deque_backward(state, copy_backward); }
+BENCHMARK(BM_deque_deque_copy_backward)->Apply(run_sizes);
+
+void BM_deque_deque_ranges_copy_backward(benchmark::State& state) {
+  benchmark_deque_deque_backward(state, std::ranges::copy_backward);
+}
+BENCHMARK(BM_deque_deque_ranges_copy_backward)->Apply(run_sizes);
+
+void BM_vector_deque_copy_backward(benchmark::State& state) { benchmark_vector_deque_backward(state, copy_backward); }
+BENCHMARK(BM_vector_deque_copy_backward)->Apply(run_sizes);
+
+void BM_vector_deque_ranges_copy_backward(benchmark::State& state) {
+  benchmark_vector_deque_backward(state, std::ranges::copy_backward);
+}
+BENCHMARK(BM_vector_deque_ranges_copy_backward)->Apply(run_sizes);
+
+// move_backward
+void BM_deque_vector_move_backward(benchmark::State& state) { benchmark_deque_vector_backward(state, move_backward); }
+BENCHMARK(BM_deque_vector_move_backward)->Apply(run_sizes);
+
+void BM_deque_vector_ranges_move_backward(benchmark::State& state) {
+  benchmark_deque_vector_backward(state, std::ranges::move_backward);
+}
+BENCHMARK(BM_deque_vector_ranges_move_backward)->Apply(run_sizes);
+
+void BM_deque_deque_move_backward(benchmark::State& state) { benchmark_deque_deque_backward(state, move_backward); }
+BENCHMARK(BM_deque_deque_move_backward)->Apply(run_sizes);
+
+void BM_deque_deque_ranges_move_backward(benchmark::State& state) {
+  benchmark_deque_deque_backward(state, std::ranges::move_backward);
+}
+BENCHMARK(BM_deque_deque_ranges_move_backward)->Apply(run_sizes);
+
+void BM_vector_deque_move_backward(benchmark::State& state) { benchmark_vector_deque_backward(state, move_backward); }
+BENCHMARK(BM_vector_deque_move_backward)->Apply(run_sizes);
+
+void BM_vector_deque_ranges_move_backward(benchmark::State& state) {
+  benchmark_vector_deque_backward(state, std::ranges::move_backward);
+}
+BENCHMARK(BM_vector_deque_ranges_move_backward)->Apply(run_sizes);
+
+} // namespace
+
+BENCHMARK_MAIN();
diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst
index e467959..eeacec1 100644
--- a/libcxx/docs/ReleaseNotes.rst
+++ b/libcxx/docs/ReleaseNotes.rst
@@ -76,6 +76,8 @@ Improvements and New Features
   the C library.
 - Implemented ``<memory_resource>`` header from C++17
 - `D122780 <https://reviews.llvm.org/D122780>`_ Improved the performance of std::sort
+- The ``ranges`` versions of ``copy``, ``move``, ``copy_backward`` and ``move_backward`` are now also optimized for
+  ``std::deque<>::iterator``, which can lead to up to 20x performance improvements on certain algorithms.
 
 Deprecations and Removals
 -------------------------
diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 2d20244..8c372a3b 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -404,6 +404,7 @@ set(files
   __iterator/readable_traits.h
   __iterator/reverse_access.h
   __iterator/reverse_iterator.h
+  __iterator/segmented_iterator.h
   __iterator/size.h
   __iterator/sortable.h
   __iterator/unreachable_sentinel.h
diff --git a/libcxx/include/__algorithm/copy.h b/libcxx/include/__algorithm/copy.h
index f33d7fe..193a6df 100644
--- a/libcxx/include/__algorithm/copy.h
+++ b/libcxx/include/__algorithm/copy.h
@@ -11,7 +11,10 @@
 
 #include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/min.h>
 #include <__config>
+#include <__iterator/segmented_iterator.h>
+#include <__type_traits/common_type.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 
@@ -19,8 +22,15 @@
 #  pragma GCC system_header
 #endif
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class, class _InIter, class _Sent, class _OutIter>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter> __copy(_InIter, _Sent, _OutIter);
+
+template <class _AlgPolicy>
 struct __copy_loop {
   template <class _InIter, class _Sent, class _OutIter>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
@@ -33,6 +43,57 @@ struct __copy_loop {
 
     return std::make_pair(std::move(__first), std::move(__result));
   }
+
+  template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) const {
+    using _Traits = __segmented_iterator_traits<_InIter>;
+    auto __sfirst = _Traits::__segment(__first);
+    auto __slast  = _Traits::__segment(__last);
+    if (__sfirst == __slast) {
+      auto __iters = std::__copy<_AlgPolicy>(_Traits::__local(__first), _Traits::__local(__last), std::move(__result));
+      return std::make_pair(__last, std::move(__iters.second));
+    }
+
+    __result = std::__copy<_AlgPolicy>(_Traits::__local(__first), _Traits::__end(__sfirst), std::move(__result)).second;
+    ++__sfirst;
+    while (__sfirst != __slast) {
+      __result =
+          std::__copy<_AlgPolicy>(_Traits::__begin(__sfirst), _Traits::__end(__sfirst), std::move(__result)).second;
+      ++__sfirst;
+    }
+    __result =
+        std::__copy<_AlgPolicy>(_Traits::__begin(__sfirst), _Traits::__local(__last), std::move(__result)).second;
+    return std::make_pair(__last, std::move(__result));
+  }
+
+  template <class _InIter,
+            class _OutIter,
+            __enable_if_t<__is_cpp17_random_access_iterator<_InIter>::value &&
+                              !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value,
+                          int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) {
+    using _Traits = __segmented_iterator_traits<_OutIter>;
+    using _DiffT  = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type;
+
+    if (__first == __last)
+      return std::make_pair(std::move(__first), std::move(__result));
+
+    auto __local_first      = _Traits::__local(__result);
+    auto __segment_iterator = _Traits::__segment(__result);
+    while (true) {
+      auto __local_last = _Traits::__end(__segment_iterator);
+      auto __size       = std::min<_DiffT>(__local_last - __local_first, __last - __first);
+      auto __iters      = std::__copy<_AlgPolicy>(__first, __first + __size, __local_first);
+      __first           = std::move(__iters.first);
+
+      if (__first == __last)
+        return std::make_pair(std::move(__first), _Traits::__compose(__segment_iterator, std::move(__iters.second)));
+
+      __local_first = _Traits::__begin(++__segment_iterator);
+    }
+  }
 };
 
 struct __copy_trivial {
@@ -46,20 +107,20 @@ struct __copy_trivial {
 };
 
 template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
-pair<_InIter, _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
+pair<_InIter, _OutIter> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 __copy(_InIter __first, _Sent __last, _OutIter __result) {
-  return std::__dispatch_copy_or_move<_AlgPolicy, __copy_loop, __copy_trivial>(
+  return std::__dispatch_copy_or_move<_AlgPolicy, __copy_loop<_AlgPolicy>, __copy_trivial>(
       std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
-_OutputIterator
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   return std::__copy<_ClassicAlgPolicy>(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___ALGORITHM_COPY_H
diff --git a/libcxx/include/__algorithm/copy_backward.h b/libcxx/include/__algorithm/copy_backward.h
index be8c1ae9..bb2a432 100644
--- a/libcxx/include/__algorithm/copy_backward.h
+++ b/libcxx/include/__algorithm/copy_backward.h
@@ -11,7 +11,10 @@
 
 #include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/min.h>
 #include <__config>
+#include <__iterator/segmented_iterator.h>
+#include <__type_traits/common_type.h>
 #include <__type_traits/is_copy_constructible.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
@@ -20,8 +23,15 @@
 #  pragma GCC system_header
 #endif
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+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 _AlgPolicy>
 struct __copy_backward_loop {
   template <class _InIter, class _Sent, class _OutIter>
@@ -36,6 +46,64 @@ struct __copy_backward_loop {
 
     return std::make_pair(std::move(__original_last_iter), std::move(__result));
   }
+
+  template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) const {
+    using _Traits = __segmented_iterator_traits<_InIter>;
+    auto __sfirst = _Traits::__segment(__first);
+    auto __slast  = _Traits::__segment(__last);
+    if (__sfirst == __slast) {
+      auto __iters =
+          std::__copy_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__local(__last), std::move(__result));
+      return std::make_pair(__last, __iters.second);
+    }
+
+    __result =
+        std::__copy_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__local(__last), std::move(__result))
+            .second;
+    --__slast;
+    while (__sfirst != __slast) {
+      __result =
+          std::__copy_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__end(__slast), std::move(__result))
+              .second;
+      --__slast;
+    }
+    __result = std::__copy_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__end(__slast), std::move(__result))
+                   .second;
+    return std::make_pair(__last, std::move(__result));
+  }
+
+  template <class _InIter,
+            class _OutIter,
+            __enable_if_t<__is_cpp17_random_access_iterator<_InIter>::value &&
+                              !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value,
+                          int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) {
+    using _Traits           = __segmented_iterator_traits<_OutIter>;
+    auto __orig_last        = __last;
+    auto __segment_iterator = _Traits::__segment(__result);
+
+    // When the range contains no elements, __result might not be a valid iterator
+    if (__first == __last)
+      return std::make_pair(__first, __result);
+
+    auto __local_last = _Traits::__local(__result);
+    while (true) {
+      using _DiffT = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type;
+
+      auto __local_first = _Traits::__begin(__segment_iterator);
+      auto __size        = std::min<_DiffT>(__local_last - __local_first, __last - __first);
+      auto __iter        = std::__copy_backward<_AlgPolicy>(__last - __size, __last, __local_last).second;
+      __last -= __size;
+
+      if (__first == __last)
+        return std::make_pair(std::move(__orig_last), _Traits::__compose(__segment_iterator, std::move(__iter)));
+      --__segment_iterator;
+      __local_last = _Traits::__end(__segment_iterator);
+    }
+  }
 };
 
 struct __copy_backward_trivial {
@@ -49,8 +117,7 @@ struct __copy_backward_trivial {
 };
 
 template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
-pair<_BidirectionalIterator1, _BidirectionalIterator2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_BidirectionalIterator1, _BidirectionalIterator2>
 __copy_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) {
   return std::__dispatch_copy_or_move<_AlgPolicy, __copy_backward_loop<_AlgPolicy>, __copy_backward_trivial>(
       std::move(__first), std::move(__last), std::move(__result));
@@ -71,4 +138,6 @@ copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H
diff --git a/libcxx/include/__algorithm/move.h b/libcxx/include/__algorithm/move.h
index 2581a41..ac95bda 100644
--- a/libcxx/include/__algorithm/move.h
+++ b/libcxx/include/__algorithm/move.h
@@ -11,7 +11,10 @@
 
 #include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/min.h>
 #include <__config>
+#include <__iterator/segmented_iterator.h>
+#include <__type_traits/common_type.h>
 #include <__type_traits/is_copy_constructible.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
@@ -20,8 +23,15 @@
 #  pragma GCC system_header
 #endif
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+__move(_InIter __first, _Sent __last, _OutIter __result);
+
 template <class _AlgPolicy>
 struct __move_loop {
   template <class _InIter, class _Sent, class _OutIter>
@@ -34,6 +44,57 @@ struct __move_loop {
     }
     return std::make_pair(std::move(__first), std::move(__result));
   }
+
+  template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) const {
+    using _Traits = __segmented_iterator_traits<_InIter>;
+    auto __sfirst = _Traits::__segment(__first);
+    auto __slast  = _Traits::__segment(__last);
+    if (__sfirst == __slast) {
+      auto __iters = std::__move<_AlgPolicy>(_Traits::__local(__first), _Traits::__local(__last), std::move(__result));
+      return std::make_pair(__last, std::move(__iters.second));
+    }
+
+    __result = std::__move<_AlgPolicy>(_Traits::__local(__first), _Traits::__end(__sfirst), std::move(__result)).second;
+    ++__sfirst;
+    while (__sfirst != __slast) {
+      __result =
+          std::__move<_AlgPolicy>(_Traits::__begin(__sfirst), _Traits::__end(__sfirst), std::move(__result)).second;
+      ++__sfirst;
+    }
+    __result =
+        std::__move<_AlgPolicy>(_Traits::__begin(__sfirst), _Traits::__local(__last), std::move(__result)).second;
+    return std::make_pair(__last, std::move(__result));
+  }
+
+  template <class _InIter,
+            class _OutIter,
+            __enable_if_t<__is_cpp17_random_access_iterator<_InIter>::value &&
+                              !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value,
+                          int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) {
+    using _Traits = __segmented_iterator_traits<_OutIter>;
+    using _DiffT  = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type;
+
+    if (__first == __last)
+      return std::make_pair(std::move(__first), std::move(__result));
+
+    auto __local_first      = _Traits::__local(__result);
+    auto __segment_iterator = _Traits::__segment(__result);
+    while (true) {
+      auto __local_last = _Traits::__end(__segment_iterator);
+      auto __size       = std::min<_DiffT>(__local_last - __local_first, __last - __first);
+      auto __iters      = std::__move<_AlgPolicy>(__first, __first + __size, __local_first);
+      __first           = std::move(__iters.first);
+
+      if (__first == __last)
+        return std::make_pair(std::move(__first), _Traits::__compose(__segment_iterator, std::move(__iters.second)));
+
+      __local_first = _Traits::__begin(++__segment_iterator);
+    }
+  }
 };
 
 struct __move_trivial {
@@ -47,23 +108,23 @@ struct __move_trivial {
 };
 
 template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
-pair<_InIter, _OutIter>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
 __move(_InIter __first, _Sent __last, _OutIter __result) {
   return std::__dispatch_copy_or_move<_AlgPolicy, __move_loop<_AlgPolicy>, __move_trivial>(
       std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InputIterator, class _OutputIterator>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
-_OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
+move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   static_assert(is_copy_constructible<_InputIterator>::value, "Iterators has to be copy constructible.");
   static_assert(is_copy_constructible<_OutputIterator>::value, "The output iterator has to be copy constructible.");
 
-  return std::__move<_ClassicAlgPolicy>(
-      std::move(__first), std::move(__last), std::move(__result)).second;
+  return std::__move<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___ALGORITHM_MOVE_H
diff --git a/libcxx/include/__algorithm/move_backward.h b/libcxx/include/__algorithm/move_backward.h
index 6636ca6..d4f013b 100644
--- a/libcxx/include/__algorithm/move_backward.h
+++ b/libcxx/include/__algorithm/move_backward.h
@@ -11,7 +11,10 @@
 
 #include <__algorithm/copy_move_common.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/min.h>
 #include <__config>
+#include <__iterator/segmented_iterator.h>
+#include <__type_traits/common_type.h>
 #include <__type_traits/is_copy_constructible.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
@@ -20,8 +23,15 @@
 #  pragma GCC system_header
 #endif
 
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_BidirectionalIterator1, _BidirectionalIterator2>
+__move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result);
+
 template <class _AlgPolicy>
 struct __move_backward_loop {
   template <class _InIter, class _Sent, class _OutIter>
@@ -36,6 +46,64 @@ struct __move_backward_loop {
 
     return std::make_pair(std::move(__original_last_iter), std::move(__result));
   }
+
+  template <class _InIter, class _OutIter, __enable_if_t<__is_segmented_iterator<_InIter>::value, int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) const {
+    using _Traits = __segmented_iterator_traits<_InIter>;
+    auto __sfirst = _Traits::__segment(__first);
+    auto __slast  = _Traits::__segment(__last);
+    if (__sfirst == __slast) {
+      auto __iters =
+          std::__move_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__local(__last), std::move(__result));
+      return std::make_pair(__last, __iters.second);
+    }
+
+    __result =
+        std::__move_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__local(__last), std::move(__result))
+            .second;
+    --__slast;
+    while (__sfirst != __slast) {
+      __result =
+          std::__move_backward<_AlgPolicy>(_Traits::__begin(__slast), _Traits::__end(__slast), std::move(__result))
+              .second;
+      --__slast;
+    }
+    __result = std::__move_backward<_AlgPolicy>(_Traits::__local(__first), _Traits::__end(__slast), std::move(__result))
+                   .second;
+    return std::make_pair(__last, std::move(__result));
+  }
+
+  template <class _InIter,
+            class _OutIter,
+            __enable_if_t<__is_cpp17_random_access_iterator<_InIter>::value &&
+                              !__is_segmented_iterator<_InIter>::value && __is_segmented_iterator<_OutIter>::value,
+                          int> = 0>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+  operator()(_InIter __first, _InIter __last, _OutIter __result) {
+    using _Traits = __segmented_iterator_traits<_OutIter>;
+    using _DiffT  = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type;
+
+    // When the range contains no elements, __result might not be a valid iterator
+    if (__first == __last)
+      return std::make_pair(__first, __result);
+
+    auto __orig_last = __last;
+
+    auto __local_last       = _Traits::__local(__result);
+    auto __segment_iterator = _Traits::__segment(__result);
+    while (true) {
+      auto __local_first = _Traits::__begin(__segment_iterator);
+      auto __size        = std::min<_DiffT>(__local_last - __local_first, __last - __first);
+      auto __iter        = std::__move_backward<_AlgPolicy>(__last - __size, __last, __local_last).second;
+      __last -= __size;
+
+      if (__first == __last)
+        return std::make_pair(std::move(__orig_last), _Traits::__compose(__segment_iterator, std::move(__iter)));
+
+      __local_last = _Traits::__end(--__segment_iterator);
+    }
+  }
 };
 
 struct __move_backward_trivial {
@@ -49,8 +117,7 @@ struct __move_backward_trivial {
 };
 
 template <class _AlgPolicy, class _BidirectionalIterator1, class _Sentinel, class _BidirectionalIterator2>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
-pair<_BidirectionalIterator1, _BidirectionalIterator2>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_BidirectionalIterator1, _BidirectionalIterator2>
 __move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _BidirectionalIterator2 __result) {
   static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value &&
                 std::is_copy_constructible<_BidirectionalIterator1>::value, "Iterators must be copy constructible.");
@@ -60,15 +127,13 @@ __move_backward(_BidirectionalIterator1 __first, _Sentinel __last, _Bidirectiona
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
-_BidirectionalIterator2
-move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
-              _BidirectionalIterator2 __result)
-{
-  return std::__move_backward<_ClassicAlgPolicy>(
-      std::move(__first), std::move(__last), std::move(__result)).second;
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _BidirectionalIterator2
+move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {
+  return std::__move_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___ALGORITHM_MOVE_BACKWARD_H
diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h
index 942235a..f272e03 100644
--- a/libcxx/include/__iterator/reverse_iterator.h
+++ b/libcxx/include/__iterator/reverse_iterator.h
@@ -25,6 +25,7 @@
 #include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__iterator/readable_traits.h>
+#include <__iterator/segmented_iterator.h>
 #include <__memory/addressof.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
diff --git a/libcxx/include/__iterator/segmented_iterator.h b/libcxx/include/__iterator/segmented_iterator.h
new file mode 100644
index 0000000..f3cd1e5
--- /dev/null
+++ b/libcxx/include/__iterator/segmented_iterator.h
@@ -0,0 +1,79 @@
+//===----------------------------------------------------------------------===//
+//
+// 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___SEGMENTED_ITERATOR_H
+#define _LIBCPP___SEGMENTED_ITERATOR_H
+
+// Segmented iterators are iterators over (not necessarily contiguous) sub-ranges.
+//
+// For example, std::deque stores its data into multiple blocks of contiguous memory,
+// which are not stored contiguously themselves. The concept of segmented iterators
+// allows algorithms to operate over these multi-level iterators natively, opening the
+// door to various optimizations. See http://lafstern.org/matt/segmented.pdf for details.
+//
+// If __segmented_iterator_traits can be instantiated, the following functions and associated types must be provided:
+// - Traits::__local_iterator
+//   The type of iterators used to iterate inside a segment.
+//
+// - Traits::__segment_iterator
+//   The type of iterators used to iterate over segments.
+//   Segment iterators can be forward iterators or bidirectional iterators, depending on the
+//   underlying data structure.
+//
+// - static __segment_iterator Traits::__segment(It __it)
+//   Returns an iterator to the segment that the provided iterator is in.
+//
+// - static __local_iterator Traits::__local(It __it)
+//   Returns the local iterator pointing to the element that the provided iterator points to.
+//
+// - static __local_iterator Traits::__begin(__segment_iterator __it)
+//   Returns the local iterator to the beginning of the segment that the provided iterator is pointing into.
+//
+// - static __local_iterator Traits::__end(__segment_iterator __it)
+//   Returns the one-past-the-end local iterator to the segment that the provided iterator is pointing into.
+//
+// - static It Traits::__compose(__segment_iterator, __local_iterator)
+//   Returns the iterator composed of the segment iterator and local iterator.
+
+#include <__config>
+#include <__type_traits/integral_constant.h>
+#include <cstddef>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Iterator>
+struct __segmented_iterator_traits;
+/* exposition-only:
+{
+  using __segment_iterator = ...;
+  using __local_iterator   = ...;
+
+  static __segment_iterator __segment(_Iterator);
+  static __local_iterator __local(_Iterator);
+  static __local_iterator __begin(__segment_iterator);
+  static __local_iterator __end(__segment_iterator);
+  static _Iterator __compose(__segment_iterator, __local_iterator);
+};
+*/
+
+template <class _Tp, size_t = 0>
+struct __has_specialization : false_type {};
+
+template <class _Tp>
+struct __has_specialization<_Tp, sizeof(_Tp) * 0> : true_type {};
+
+template <class _Iterator>
+using __is_segmented_iterator = __has_specialization<__segmented_iterator_traits<_Iterator> >;
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___SEGMENTED_ITERATOR_H
diff --git a/libcxx/include/deque b/libcxx/include/deque
index 844588339..f2b8076 100644
--- a/libcxx/include/deque
+++ b/libcxx/include/deque
@@ -176,6 +176,7 @@ template <class T, class Allocator, class Predicate>
 #include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__iterator/reverse_iterator.h>
+#include <__iterator/segmented_iterator.h>
 #include <__memory/allocator_destructor.h>
 #include <__memory/pointer_traits.h>
 #include <__memory/temp_value.h>
@@ -216,98 +217,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS deque;
 
-template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
-          class _DiffType, _DiffType _BlockSize>
-class _LIBCPP_TEMPLATE_VIS __deque_iterator;
-
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy(_RAIter __f,
-     _RAIter __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     _OutputIterator __r);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
-
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy_backward(_RAIter __f,
-              _RAIter __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              _OutputIterator __r);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
-
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move(_RAIter __f,
-     _RAIter __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     _OutputIterator __r);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
-
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move_backward(_RAIter __f,
-              _RAIter __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              _OutputIterator __r);
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
-
 template <class _ValueType, class _DiffType>
 struct __deque_block_size {
   static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;
@@ -478,464 +387,43 @@ private:
     template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>
         friend class _LIBCPP_TEMPLATE_VIS __deque_iterator;
 
-    template <class _RAIter,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    copy(_RAIter __f,
-         _RAIter __l,
-         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-         typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _OutputIterator>
-    friend
-    _OutputIterator
-    copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-         _OutputIterator __r);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
-
-    template <class _RAIter,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    copy_backward(_RAIter __f,
-                  _RAIter __l,
-                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-                  typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _OutputIterator>
-    friend
-    _OutputIterator
-    copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-                  _OutputIterator __r);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
-
-    template <class _RAIter,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    move(_RAIter __f,
-         _RAIter __l,
-         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-         typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _OutputIterator>
-    friend
-    _OutputIterator
-    move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-         _OutputIterator __r);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-         __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-         __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
-
-    template <class _RAIter,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    move_backward(_RAIter __f,
-                  _RAIter __l,
-                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-                  typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _OutputIterator>
-    friend
-    _OutputIterator
-    move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-                  _OutputIterator __r);
-
-    template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-              class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-    friend
-    __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-    move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-                  __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-                  __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r);
+    template <class>
+    friend struct __segmented_iterator_traits;
 };
 
-template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
-          class _DiffType, _DiffType _BlockSize>
-const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
-                                 _DiffType, _BlockSize>::__block_size =
-    __deque_block_size<_ValueType, _DiffType>::value;
-
-// copy
-
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy(_RAIter __f,
-     _RAIter __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
-{
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
-    const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
-    while (__f != __l)
-    {
-        pointer __rb = __r.__ptr_;
-        pointer __re = *__r.__m_iter_ + __block_size;
-        difference_type __bs = __re - __rb;
-        difference_type __n = __l - __f;
-        _RAIter __m = __l;
-        if (__n > __bs)
-        {
-            __n = __bs;
-            __m = __f + __n;
-        }
-        _VSTD::copy(__f, __m, __rb);
-        __f = __m;
-        __r += __n;
-    }
-    return __r;
-}
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     _OutputIterator __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + __block_size;
-        difference_type __bs = __fe - __fb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __fe = __fb + __bs;
-        }
-        __r = _VSTD::copy(__fb, __fe, __r);
-        __n -= __bs;
-        __f += __bs;
-    }
-    return __r;
-}
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + __block_size;
-        difference_type __bs = __fe - __fb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __fe = __fb + __bs;
-        }
-        __r = _VSTD::copy(__fb, __fe, __r);
-        __n -= __bs;
-        __f += __bs;
-    }
-    return __r;
-}
-
-// copy_backward
-
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy_backward(_RAIter __f,
-              _RAIter __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
-{
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
-    while (__f != __l)
-    {
-        __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
-        pointer __rb = *__rp.__m_iter_;
-        pointer __re = __rp.__ptr_ + 1;
-        difference_type __bs = __re - __rb;
-        difference_type __n = __l - __f;
-        _RAIter __m = __f;
-        if (__n > __bs)
-        {
-            __n = __bs;
-            __m = __l - __n;
-        }
-        _VSTD::copy_backward(__m, __l, __re);
-        __l = __m;
-        __r -= __n;
-    }
-    return __r;
-}
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              _OutputIterator __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        --__l;
-        pointer __lb = *__l.__m_iter_;
-        pointer __le = __l.__ptr_ + 1;
-        difference_type __bs = __le - __lb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __lb = __le - __bs;
-        }
-        __r = _VSTD::copy_backward(__lb, __le, __r);
-        __n -= __bs;
-        __l -= __bs - 1;
-    }
-    return __r;
-}
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        --__l;
-        pointer __lb = *__l.__m_iter_;
-        pointer __le = __l.__ptr_ + 1;
-        difference_type __bs = __le - __lb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __lb = __le - __bs;
-        }
-        __r = _VSTD::copy_backward(__lb, __le, __r);
-        __n -= __bs;
-        __l -= __bs - 1;
-    }
-    return __r;
-}
-
-// move
-
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move(_RAIter __f,
-     _RAIter __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-     typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
-{
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
-    const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size;
-    while (__f != __l)
-    {
-        pointer __rb = __r.__ptr_;
-        pointer __re = *__r.__m_iter_ + __block_size;
-        difference_type __bs = __re - __rb;
-        difference_type __n = __l - __f;
-        _RAIter __m = __l;
-        if (__n > __bs)
-        {
-            __n = __bs;
-            __m = __f + __n;
-        }
-        _VSTD::move(__f, __m, __rb);
-        __f = __m;
-        __r += __n;
-    }
-    return __r;
-}
-
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     _OutputIterator __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + __block_size;
-        difference_type __bs = __fe - __fb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __fe = __fb + __bs;
-        }
-        __r = _VSTD::move(__fb, __fe, __r);
-        __n -= __bs;
-        __f += __bs;
-    }
-    return __r;
-}
+template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, class _DiffType, _DiffType _BlockSize>
+struct __segmented_iterator_traits<
+    __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize> > {
+private:
+  using _Iterator = __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, _DiffType, _BlockSize>;
 
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-     __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-     __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        pointer __fb = __f.__ptr_;
-        pointer __fe = *__f.__m_iter_ + __block_size;
-        difference_type __bs = __fe - __fb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __fe = __fb + __bs;
-        }
-        __r = _VSTD::move(__fb, __fe, __r);
-        __n -= __bs;
-        __f += __bs;
-    }
-    return __r;
-}
+public:
+  using __is_segmented_iterator = true_type;
+  using __segment_iterator = _MapPointer;
+  using __local_iterator = _Pointer;
 
-// move_backward
+  static _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_Iterator __iter) { return __iter.__m_iter_; }
+  static _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_Iterator __iter) { return __iter.__ptr_; }
+  static _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) { return *__iter; }
 
-template <class _RAIter,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move_backward(_RAIter __f,
-              _RAIter __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r,
-              typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)
-{
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type;
-    typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer;
-    while (__f != __l)
-    {
-        __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r);
-        pointer __rb = *__rp.__m_iter_;
-        pointer __re = __rp.__ptr_ + 1;
-        difference_type __bs = __re - __rb;
-        difference_type __n = __l - __f;
-        _RAIter __m = __f;
-        if (__n > __bs)
-        {
-            __n = __bs;
-            __m = __l - __n;
-        }
-        _VSTD::move_backward(__m, __l, __re);
-        __l = __m;
-        __r -= __n;
-    }
-    return __r;
-}
+  static _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {
+        return *__iter + _Iterator::__block_size;
+  }
 
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _OutputIterator>
-_LIBCPP_HIDE_FROM_ABI _OutputIterator
-move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              _OutputIterator __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        --__l;
-        pointer __lb = *__l.__m_iter_;
-        pointer __le = __l.__ptr_ + 1;
-        difference_type __bs = __le - __lb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __lb = __le - __bs;
+  static _LIBCPP_HIDE_FROM_ABI _Iterator __compose(__segment_iterator __segment, __local_iterator __local) {
+        if (__local == __end(__segment)) {
+            ++__segment;
+            return _Iterator(__segment, *__segment);
         }
-        __r = _VSTD::move_backward(__lb, __le, __r);
-        __n -= __bs;
-        __l -= __bs - 1;
-    }
-    return __r;
-}
+        return _Iterator(__segment, __local);
+  }
+};
 
-template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1,
-          class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2>
-_LIBCPP_HIDE_FROM_ABI __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>
-move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f,
-              __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l,
-              __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r)
-{
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type;
-    typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer;
-    difference_type __n = __l - __f;
-    while (__n > 0)
-    {
-        --__l;
-        pointer __lb = *__l.__m_iter_;
-        pointer __le = __l.__ptr_ + 1;
-        difference_type __bs = __le - __lb;
-        if (__bs > __n)
-        {
-            __bs = __n;
-            __lb = __le - __bs;
-        }
-        __r = _VSTD::move_backward(__lb, __le, __r);
-        __n -= __bs;
-        __l -= __bs - 1;
-    }
-    return __r;
-}
+template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
+          class _DiffType, _DiffType _BlockSize>
+const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,
+                                 _DiffType, _BlockSize>::__block_size =
+    __deque_block_size<_ValueType, _DiffType>::value;
 
 template <class _Tp, class _Allocator /*= allocator<_Tp>*/>
 class _LIBCPP_TEMPLATE_VIS deque
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index aa4da4d..a6521a9 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -1014,6 +1014,7 @@ module std [system] {
       module readable_traits       { private header "__iterator/readable_traits.h" }
       module reverse_access        { private header "__iterator/reverse_access.h" }
       module reverse_iterator      { private header "__iterator/reverse_iterator.h" }
+      module segmented_iterator    { private header "__iterator/segmented_iterator.h" }
       module size                  { private header "__iterator/size.h" }
       module sortable {
         private header "__iterator/sortable.h"
diff --git a/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_iterator.compile.pass.cpp b/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_iterator.compile.pass.cpp
index c3da6f0..9c488c2 100644
--- a/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_iterator.compile.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_iterator.compile.pass.cpp
@@ -15,19 +15,9 @@
 
 #include "test_iterators.h"
 
-struct ForwardProxyIterator {
-  using value_type = int;
-  using difference_type = int;
-  ForwardProxyIterator& operator++();
-  ForwardProxyIterator operator++(int);
-  bool operator==(const ForwardProxyIterator&) const;
-
-  int operator*() const;
-};
-
 static_assert(std::ranges::__nothrow_forward_iterator<forward_iterator<int*>>);
-static_assert(std::forward_iterator<ForwardProxyIterator>);
-static_assert(!std::ranges::__nothrow_forward_iterator<ForwardProxyIterator>);
+static_assert(std::forward_iterator<ForwardProxyIterator<int*>>);
+static_assert(!std::ranges::__nothrow_forward_iterator<ForwardProxyIterator<int*>>);
 
 constexpr bool forward_subsumes_input(std::ranges::__nothrow_forward_iterator auto) {
   return true;
diff --git a/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_range.compile.pass.cpp b/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_range.compile.pass.cpp
index 06af5370..2ddfdf6 100644
--- a/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_range.compile.pass.cpp
+++ b/libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_range.compile.pass.cpp
@@ -16,18 +16,6 @@
 #include "test_iterators.h"
 #include "test_range.h"
 
-// Has to be a template to work with `test_range`.
-template <typename>
-struct ForwardProxyIterator {
-  using value_type = int;
-  using difference_type = int;
-  ForwardProxyIterator& operator++();
-  ForwardProxyIterator operator++(int);
-  bool operator==(const ForwardProxyIterator&) const;
-
-  int operator*() const;
-};
-
 static_assert(std::ranges::__nothrow_forward_range<test_range<forward_iterator>>);
 static_assert(!std::ranges::__nothrow_forward_range<test_range<cpp20_input_iterator>>);
 static_assert(std::ranges::forward_range<test_range<ForwardProxyIterator>>);
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
index e61eedd..339324c 100644
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -435,6 +435,7 @@ END-SCRIPT
 #include <__iterator/readable_traits.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/readable_traits.h'}}
 #include <__iterator/reverse_access.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/reverse_access.h'}}
 #include <__iterator/reverse_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/reverse_iterator.h'}}
+#include <__iterator/segmented_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/segmented_iterator.h'}}
 #include <__iterator/size.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/size.h'}}
 #include <__iterator/sortable.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/sortable.h'}}
 #include <__iterator/unreachable_sentinel.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/unreachable_sentinel.h'}}
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp
index c241056..7a5c0a7 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp
@@ -20,7 +20,9 @@
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
@@ -53,20 +55,21 @@ static_assert(!HasCopyR<InputRangeNotSentinelEqualityComparableWith, int*>);
 
 static_assert(std::is_same_v<std::ranges::copy_result<int, long>, std::ranges::in_out_result<int, long>>);
 
+// clang-format off
 template <class In, class Out, class Sent = In>
 constexpr void test_iterators() {
   { // simple test
     {
-      std::array in {1, 2, 3, 4};
+      std::array in{1, 2, 3, 4};
       std::array<int, 4> out;
       std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
-        std::ranges::copy(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data()));
+          std::ranges::copy(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data()));
       assert(in == out);
       assert(base(ret.in) == in.data() + in.size());
       assert(base(ret.out) == out.data() + out.size());
     }
     {
-      std::array in {1, 2, 3, 4};
+      std::array in{1, 2, 3, 4};
       std::array<int, 4> out;
       auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
       std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::copy(range, Out(out.data()));
@@ -88,12 +91,13 @@ constexpr void test_iterators() {
       std::array<int, 0> in;
       std::array<int, 0> out;
       auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
-      auto ret = std::ranges::copy(range, Out(out.data()));
+      auto ret   = std::ranges::copy(range, Out(out.data()));
       assert(base(ret.in) == in.data());
       assert(base(ret.out) == out.data());
     }
   }
 }
+// clang-format on
 
 constexpr bool test() {
   meta::for_each(meta::forward_iterator_list<int*>{}, []<class Out>() {
@@ -122,7 +126,7 @@ constexpr bool test() {
   }
 
   { // check that an iterator is returned with a borrowing range
-    std::array in {1, 2, 3, 4};
+    std::array in{1, 2, 3, 4};
     std::array<int, 4> out;
     std::same_as<std::ranges::in_out_result<int*, int*>> auto ret = std::ranges::copy(std::views::all(in), out.data());
     assert(ret.in == in.data() + 4);
@@ -132,8 +136,8 @@ constexpr bool test() {
 
   { // check that every element is copied exactly once
     struct CopyOnce {
-      bool copied = false;
-      constexpr CopyOnce() = default;
+      bool copied                               = false;
+      constexpr CopyOnce()                      = default;
       constexpr CopyOnce(const CopyOnce& other) = delete;
       constexpr CopyOnce& operator=(const CopyOnce& other) {
         assert(!other.copied);
@@ -142,16 +146,16 @@ constexpr bool test() {
       }
     };
     {
-      std::array<CopyOnce, 4> in {};
-      std::array<CopyOnce, 4> out {};
+      std::array<CopyOnce, 4> in{};
+      std::array<CopyOnce, 4> out{};
       auto ret = std::ranges::copy(in.begin(), in.end(), out.begin());
       assert(ret.in == in.end());
       assert(ret.out == out.end());
       assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));
     }
     {
-      std::array<CopyOnce, 4> in {};
-      std::array<CopyOnce, 4> out {};
+      std::array<CopyOnce, 4> in{};
+      std::array<CopyOnce, 4> out{};
       auto ret = std::ranges::copy(in, out.begin());
       assert(ret.in == in.end());
       assert(ret.out == out.end());
@@ -162,8 +166,8 @@ constexpr bool test() {
   { // check that the range is copied forwards
     struct OnlyForwardsCopyable {
       OnlyForwardsCopyable* next = nullptr;
-      bool canCopy = false;
-      OnlyForwardsCopyable() = default;
+      bool canCopy               = false;
+      OnlyForwardsCopyable()     = default;
       constexpr OnlyForwardsCopyable& operator=(const OnlyForwardsCopyable&) {
         assert(canCopy);
         if (next != nullptr)
@@ -172,12 +176,12 @@ constexpr bool test() {
       }
     };
     {
-      std::array<OnlyForwardsCopyable, 3> in {};
-      std::array<OnlyForwardsCopyable, 3> out {};
-      out[0].next = &out[1];
-      out[1].next = &out[2];
+      std::array<OnlyForwardsCopyable, 3> in{};
+      std::array<OnlyForwardsCopyable, 3> out{};
+      out[0].next    = &out[1];
+      out[1].next    = &out[2];
       out[0].canCopy = true;
-      auto ret = std::ranges::copy(in.begin(), in.end(), out.begin());
+      auto ret       = std::ranges::copy(in.begin(), in.end(), out.begin());
       assert(ret.in == in.end());
       assert(ret.out == out.end());
       assert(out[0].canCopy);
@@ -185,12 +189,12 @@ constexpr bool test() {
       assert(out[2].canCopy);
     }
     {
-      std::array<OnlyForwardsCopyable, 3> in {};
-      std::array<OnlyForwardsCopyable, 3> out {};
-      out[0].next = &out[1];
-      out[1].next = &out[2];
+      std::array<OnlyForwardsCopyable, 3> in{};
+      std::array<OnlyForwardsCopyable, 3> out{};
+      out[0].next    = &out[1];
+      out[1].next    = &out[2];
       out[0].canCopy = true;
-      auto ret = std::ranges::copy(in, out.begin());
+      auto ret       = std::ranges::copy(in, out.begin());
       assert(ret.in == in.end());
       assert(ret.out == out.end());
       assert(out[0].canCopy);
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp
new file mode 100644
index 0000000..e8f8301
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp
@@ -0,0 +1,51 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+#include <algorithm>
+#include <cassert>
+#include <concepts>
+#include <deque>
+#include <vector>
+
+template <class InContainer, class OutContainer>
+constexpr void test_containers() {
+  using InIter  = typename InContainer::iterator;
+  using OutIter = typename OutContainer::iterator;
+
+  {
+    InContainer in{1, 2, 3, 4};
+    OutContainer out(4);
+
+    std::same_as<std::ranges::in_out_result<InIter, OutIter>> auto ret =
+        std::ranges::copy(in.begin(), in.end(), out.begin());
+    assert(std::ranges::equal(in, out));
+    assert(ret.in == in.end());
+    assert(ret.out == out.end());
+  }
+  {
+    InContainer in{1, 2, 3, 4};
+    OutContainer out(4);
+    std::same_as<std::ranges::in_out_result<InIter, OutIter>> auto ret = std::ranges::copy(in, out.begin());
+    assert(std::ranges::equal(in, out));
+    assert(ret.in == in.end());
+    assert(ret.out == out.end());
+  }
+}
+
+int main(int, char**) {
+  if (!std::is_constant_evaluated()) {
+    test_containers<std::deque<int>, std::deque<int>>();
+    test_containers<std::deque<int>, std::vector<int>>();
+    test_containers<std::vector<int>, std::deque<int>>();
+    test_containers<std::vector<int>, std::vector<int>>();
+  }
+
+  return 0;
+}
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
index a18ba9d..3762948 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp
@@ -23,7 +23,9 @@
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
@@ -99,37 +101,84 @@ constexpr void test_iterators() {
   }
 }
 
-template <class InIter, class OutIter>
+template <class InContainer, class OutContainer, class In, class Out, class Sent = In>
+constexpr void test_containers() {
+  {
+    InContainer in {1, 2, 3, 4};
+    OutContainer out(4);
+    std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
+      std::ranges::copy_backward(In(in.begin()), Sent(In(in.end())), Out(out.end()));
+    assert(std::ranges::equal(in, out));
+    assert(base(ret.in) == in.end());
+    assert(base(ret.out) == out.begin());
+  }
+  {
+    InContainer in {1, 2, 3, 4};
+    OutContainer out(4);
+    auto range = std::ranges::subrange(In(in.begin()), Sent(In(in.end())));
+    std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::copy_backward(range, Out(out.end()));
+    assert(std::ranges::equal(in, out));
+    assert(base(ret.in) == in.end());
+    assert(base(ret.out) == out.begin());
+  }
+}
+
+template <template <class> class InIter, template <class> class OutIter>
 constexpr void test_sentinels() {
-  test_iterators<InIter, OutIter, InIter>();
-  test_iterators<InIter, OutIter, sentinel_wrapper<InIter>>();
-  test_iterators<InIter, OutIter, sized_sentinel<InIter>>();
+  test_iterators<InIter<int*>, OutIter<int*>, InIter<int*>>();
+  test_iterators<InIter<int*>, OutIter<int*>, sentinel_wrapper<InIter<int*>>>();
+  test_iterators<InIter<int*>, OutIter<int*>, sized_sentinel<InIter<int*>>>();
+
+  if (!std::is_constant_evaluated()) {
+    if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> &&
+                  !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> &&
+                  !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> &&
+                  !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) {
+      test_containers<std::deque<int>,
+                      std::deque<int>,
+                      InIter<std::deque<int>::iterator>,
+                      OutIter<std::deque<int>::iterator>>();
+      test_containers<std::deque<int>,
+                      std::vector<int>,
+                      InIter<std::deque<int>::iterator>,
+                      OutIter<std::vector<int>::iterator>>();
+      test_containers<std::vector<int>,
+                      std::deque<int>,
+                      InIter<std::vector<int>::iterator>,
+                      OutIter<std::deque<int>::iterator>>();
+      test_containers<std::vector<int>,
+                      std::vector<int>,
+                      InIter<std::vector<int>::iterator>,
+                      OutIter<std::vector<int>::iterator>>();
+    }
+  }
 }
 
-template <class Out>
+template <template <class> class Out>
 constexpr void test_in_iterators() {
-  test_sentinels<bidirectional_iterator<int*>, Out>();
-  test_sentinels<random_access_iterator<int*>, Out>();
-  test_sentinels<contiguous_iterator<int*>, Out>();
-  test_sentinels<int*, Out>();
+  test_sentinels<bidirectional_iterator, Out>();
+  test_sentinels<random_access_iterator, Out>();
+  test_sentinels<contiguous_iterator, Out>();
+  test_sentinels<std::type_identity_t, Out>();
 }
 
-template <class Out>
+template <template <class> class Out>
 constexpr void test_proxy_in_iterators() {
-  test_sentinels<ProxyIterator<bidirectional_iterator<int*>>, Out>();
-  test_sentinels<ProxyIterator<random_access_iterator<int*>>, Out>();
-  test_sentinels<ProxyIterator<contiguous_iterator<int*>>, Out>();
+  test_sentinels<BidirectionalProxyIterator, Out>();
+  test_sentinels<RandomAccessProxyIterator, Out>();
+  test_sentinels<ContiguousProxyIterator, Out>();
+  test_sentinels<ProxyIterator, Out>();
 }
 
 constexpr bool test() {
-  test_in_iterators<bidirectional_iterator<int*>>();
-  test_in_iterators<random_access_iterator<int*>>();
-  test_in_iterators<contiguous_iterator<int*>>();
-  test_in_iterators<int*>();
-
-  test_proxy_in_iterators<ProxyIterator<bidirectional_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<random_access_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
+  test_in_iterators<bidirectional_iterator>();
+  test_in_iterators<random_access_iterator>();
+  test_in_iterators<contiguous_iterator>();
+  test_in_iterators<std::type_identity_t>();
+
+  test_proxy_in_iterators<BidirectionalProxyIterator>();
+  test_proxy_in_iterators<RandomAccessProxyIterator>();
+  test_proxy_in_iterators<ContiguousProxyIterator>();
 
   { // check that ranges::dangling is returned
     std::array<int, 4> out;
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp
index 2963096..18ac692 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp
@@ -22,7 +22,9 @@
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "MoveOnly.h"
@@ -77,6 +79,28 @@ constexpr void test(std::array<int, N> in) {
   }
 }
 
+template <class InContainer, class OutContainer, class In, class Out, class Sent = In>
+constexpr void test_containers() {
+  {
+    InContainer in {1, 2, 3, 4};
+    OutContainer out(4);
+    std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
+      std::ranges::move(In(in.begin()), Sent(In(in.end())), Out(out.begin()));
+    assert(std::ranges::equal(in, out));
+    assert(base(ret.in) == in.end());
+    assert(base(ret.out) == out.end());
+  }
+  {
+    InContainer in {1, 2, 3, 4};
+    OutContainer out(4);
+    auto range = std::ranges::subrange(In(in.begin()), Sent(In(in.end())));
+    std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::move(range, Out(out.begin()));
+    assert(std::ranges::equal(in, out));
+    assert(base(ret.in) == in.end());
+    assert(base(ret.out) == out.end());
+  }
+}
+
 template <class In, class Out, class Sent = In>
 constexpr void test_iterators() {
   // simple test
@@ -85,23 +109,57 @@ constexpr void test_iterators() {
   test<In, Out, Sent, 0>({});
 }
 
-template <class Out>
+template <template <class> class In, template <class> class Out>
+constexpr void test_sentinels() {
+  test_iterators<In<int*>, Out<int*>>();
+  test_iterators<In<int*>, Out<int*>, sized_sentinel<In<int*>>>();
+  test_iterators<In<int*>, Out<int*>, sentinel_wrapper<In<int*>>>();
+
+  if (!std::is_constant_evaluated()) {
+    if constexpr (!std::is_same_v<In<int*>, contiguous_iterator<int*>> &&
+                  !std::is_same_v<Out<int*>, contiguous_iterator<int*>> &&
+                  !std::is_same_v<In<int*>, ContiguousProxyIterator<int*>> &&
+                  !std::is_same_v<Out<int*>, ContiguousProxyIterator<int*>>) {
+      test_containers<std::deque<int>,
+                      std::deque<int>,
+                      In<std::deque<int>::iterator>,
+                      Out<std::deque<int>::iterator>>();
+      test_containers<std::deque<int>,
+                      std::vector<int>,
+                      In<std::deque<int>::iterator>,
+                      Out<std::vector<int>::iterator>>();
+      test_containers<std::vector<int>,
+                      std::deque<int>,
+                      In<std::vector<int>::iterator>,
+                      Out<std::deque<int>::iterator>>();
+      test_containers<std::vector<int>,
+                      std::vector<int>,
+                      In<std::vector<int>::iterator>,
+                      Out<std::vector<int>::iterator>>();
+    }
+  }
+}
+
+template <template <class> class Out>
 constexpr void test_in_iterators() {
-  test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();
-  test_iterators<forward_iterator<int*>, Out>();
-  test_iterators<bidirectional_iterator<int*>, Out>();
-  test_iterators<random_access_iterator<int*>, Out>();
-  test_iterators<contiguous_iterator<int*>, Out>();
-  test_iterators<int*, Out>();
+  test_iterators<cpp20_input_iterator<int*>, Out<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_sentinels<forward_iterator, Out>();
+  test_sentinels<bidirectional_iterator, Out>();
+  test_sentinels<random_access_iterator, Out>();
+  test_sentinels<contiguous_iterator, Out>();
+  test_sentinels<std::type_identity_t, Out>();
 }
 
-template <class Out>
+template <template <class> class Out>
 constexpr void test_proxy_in_iterators() {
-  test_iterators<ProxyIterator<cpp20_input_iterator<int*>>, Out, sentinel_wrapper<ProxyIterator<cpp20_input_iterator<int*>>>>();
-  test_iterators<ProxyIterator<forward_iterator<int*>>, Out>();
-  test_iterators<ProxyIterator<bidirectional_iterator<int*>>, Out>();
-  test_iterators<ProxyIterator<random_access_iterator<int*>>, Out>();
-  test_iterators<ProxyIterator<contiguous_iterator<int*>>, Out>();
+  test_iterators<ProxyIterator<cpp20_input_iterator<int*>>,
+                 Out<int*>,
+                 sentinel_wrapper<ProxyIterator<cpp20_input_iterator<int*>>>>();
+  test_sentinels<ForwardProxyIterator, Out>();
+  test_sentinels<BidirectionalProxyIterator, Out>();
+  test_sentinels<RandomAccessProxyIterator, Out>();
+  test_sentinels<ContiguousProxyIterator, Out>();
+  test_sentinels<ProxyIterator, Out>();
 }
 
 struct IteratorWithMoveIter {
@@ -121,22 +179,27 @@ struct IteratorWithMoveIter {
   constexpr bool operator==(const IteratorWithMoveIter& other) const = default;
 };
 
+// cpp17_intput_iterator has a defaulted template argument
+template <class Iter>
+using Cpp17InIter = cpp17_input_iterator<Iter>;
+
 constexpr bool test() {
-  test_in_iterators<cpp17_output_iterator<int*>>();
-  test_in_iterators<cpp20_output_iterator<int*>>();
-  test_in_iterators<cpp17_input_iterator<int*>>();
-  test_in_iterators<cpp20_input_iterator<int*>>();
-  test_in_iterators<forward_iterator<int*>>();
-  test_in_iterators<bidirectional_iterator<int*>>();
-  test_in_iterators<random_access_iterator<int*>>();
-  test_in_iterators<contiguous_iterator<int*>>();
-  test_in_iterators<int*>();
-
-  test_proxy_in_iterators<ProxyIterator<cpp20_input_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<forward_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<bidirectional_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<random_access_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
+  test_in_iterators<cpp17_output_iterator>();
+  test_in_iterators<cpp20_output_iterator>();
+  test_in_iterators<Cpp17InIter>();
+  test_in_iterators<cpp20_input_iterator>();
+  test_in_iterators<forward_iterator>();
+  test_in_iterators<bidirectional_iterator>();
+  test_in_iterators<random_access_iterator>();
+  test_in_iterators<contiguous_iterator>();
+  test_in_iterators<std::type_identity_t>();
+
+  test_proxy_in_iterators<Cpp20InputProxyIterator>();
+  test_proxy_in_iterators<ForwardProxyIterator>();
+  test_proxy_in_iterators<BidirectionalProxyIterator>();
+  test_proxy_in_iterators<RandomAccessProxyIterator>();
+  test_proxy_in_iterators<ContiguousProxyIterator>();
+  test_proxy_in_iterators<ProxyIterator>();
 
   { // check that a move-only type works
     {
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp
index b77c1ed..1a281c6 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp
@@ -22,7 +22,9 @@
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "MoveOnly.h"
@@ -85,27 +87,73 @@ constexpr void test_iterators() {
   test<In, Out, Sent, 0>({});
 }
 
-template <class InIter, class OutIter>
+template <class InContainer, class OutContainer, class In, class Out, class Sent = In>
+constexpr void test_containers() {
+  {
+    InContainer in {1, 2, 3, 4};
+    OutContainer out(4);
+    std::same_as<std::ranges::in_out_result<In, Out>> auto ret =
+      std::ranges::move_backward(In(in.begin()), Sent(In(in.end())), Out(out.end()));
+    assert(std::ranges::equal(in, out));
+    assert(base(ret.in) == in.end());
+    assert(base(ret.out) == out.begin());
+  }
+  {
+    InContainer in {1, 2, 3, 4};
+    OutContainer out(4);
+    auto range = std::ranges::subrange(In(in.begin()), Sent(In(in.end())));
+    std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::move_backward(range, Out(out.end()));
+    assert(std::ranges::equal(in, out));
+    assert(base(ret.in) == in.end());
+    assert(base(ret.out) == out.begin());
+  }
+}
+
+template <template <class> class InIter, template <class> class OutIter>
 constexpr void test_sentinels() {
-  test_iterators<InIter, OutIter, InIter>();
-  test_iterators<InIter, OutIter, sentinel_wrapper<InIter>>();
-  test_iterators<InIter, OutIter, sized_sentinel<InIter>>();
+  test_iterators<InIter<int*>, OutIter<int*>, InIter<int*>>();
+  test_iterators<InIter<int*>, OutIter<int*>, sentinel_wrapper<InIter<int*>>>();
+  test_iterators<InIter<int*>, OutIter<int*>, sized_sentinel<InIter<int*>>>();
+
+  if (!std::is_constant_evaluated()) {
+    if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> &&
+                  !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> &&
+                  !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> &&
+                  !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) {
+      test_containers<std::deque<int>,
+                      std::deque<int>,
+                      InIter<std::deque<int>::iterator>,
+                      OutIter<std::deque<int>::iterator>>();
+      test_containers<std::deque<int>,
+                      std::vector<int>,
+                      InIter<std::deque<int>::iterator>,
+                      OutIter<std::vector<int>::iterator>>();
+      test_containers<std::vector<int>,
+                      std::deque<int>,
+                      InIter<std::vector<int>::iterator>,
+                      OutIter<std::deque<int>::iterator>>();
+      test_containers<std::vector<int>,
+                      std::vector<int>,
+                      InIter<std::vector<int>::iterator>,
+                      OutIter<std::vector<int>::iterator>>();
+    }
+  }
 }
 
-template <class Out>
+template <template <class> class Out>
 constexpr void test_in_iterators() {
-  test_sentinels<bidirectional_iterator<int*>, Out>();
-  test_sentinels<random_access_iterator<int*>, Out>();
-  test_sentinels<contiguous_iterator<int*>, Out>();
-  test_sentinels<int*, Out>();
+  test_sentinels<bidirectional_iterator, Out>();
+  test_sentinels<random_access_iterator, Out>();
+  test_sentinels<contiguous_iterator, Out>();
+  test_sentinels<std::type_identity_t, Out>();
 }
 
-template <class Out>
+template <template <class> class Out>
 constexpr void test_proxy_in_iterators() {
-  test_iterators<ProxyIterator<bidirectional_iterator<int*>>, Out, sentinel_wrapper<ProxyIterator<bidirectional_iterator<int*>>>>();
-  test_iterators<ProxyIterator<bidirectional_iterator<int*>>, Out>();
-  test_iterators<ProxyIterator<random_access_iterator<int*>>, Out>();
-  test_iterators<ProxyIterator<contiguous_iterator<int*>>, Out>();
+  test_sentinels<BidirectionalProxyIterator, Out>();
+  test_sentinels<RandomAccessProxyIterator, Out>();
+  test_sentinels<ContiguousProxyIterator, Out>();
+  test_sentinels<ProxyIterator, Out>();
 }
 
 struct IteratorWithMoveIter {
@@ -129,14 +177,15 @@ struct IteratorWithMoveIter {
 };
 
 constexpr bool test() {
-  test_in_iterators<bidirectional_iterator<int*>>();
-  test_in_iterators<random_access_iterator<int*>>();
-  test_in_iterators<contiguous_iterator<int*>>();
-  test_in_iterators<int*>();
-
-  test_proxy_in_iterators<ProxyIterator<bidirectional_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<random_access_iterator<int*>>>();
-  test_proxy_in_iterators<ProxyIterator<contiguous_iterator<int*>>>();
+  test_in_iterators<bidirectional_iterator>();
+  test_in_iterators<random_access_iterator>();
+  test_in_iterators<contiguous_iterator>();
+  test_in_iterators<std::type_identity_t>();
+
+  test_proxy_in_iterators<BidirectionalProxyIterator>();
+  test_proxy_in_iterators<RandomAccessProxyIterator>();
+  test_proxy_in_iterators<ContiguousProxyIterator>();
+  test_proxy_in_iterators<ProxyIterator>();
 
   { // check that a move-only type works
     {
diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h
index bc197e6..b8ed6b9 100644
--- a/libcxx/test/support/test_iterators.h
+++ b/libcxx/test/support/test_iterators.h
@@ -1285,6 +1285,21 @@ static_assert(std::indirectly_readable<ProxyIterator<int*>>);
 static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int>>);
 static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int&>>);
 
+template <class Iter>
+using Cpp20InputProxyIterator = ProxyIterator<cpp20_input_iterator<Iter>>;
+
+template <class Iter>
+using ForwardProxyIterator = ProxyIterator<forward_iterator<Iter>>;
+
+template <class Iter>
+using BidirectionalProxyIterator = ProxyIterator<bidirectional_iterator<Iter>>;
+
+template <class Iter>
+using RandomAccessProxyIterator = ProxyIterator<random_access_iterator<Iter>>;
+
+template <class Iter>
+using ContiguousProxyIterator = ProxyIterator<contiguous_iterator<Iter>>;
+
 template <class BaseSent>
 struct ProxySentinel {
   BaseSent base_;