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

[philnik]

Summary

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>

[philnik]

• Generate files

[philnik]

• Try to fix CI

[huixie90]

I found this approach "having a boolean + some operations" less clearer than defining a concept (or pseudo concept with constexpr bool + sfinae) with several customization points.

libcxx/include/__algorithm/copy.h

46

sentinel is always copyable.
this applies for other places

117

+= isn't required as part of your "concept" of segmented iterator

129

As we get more and more optimisations for different types, it is harder to make sure all of these overloads are mutually exclusive. Do you think this is (or will be) a problem?

libcxx/include/__iterator/segmented_iterator.h

18–26

It might be a good idea to put these functions in the primary template __segmented_iterator_traits and =delete them. This way it is more self documentary. What do you think?

[philnik]

libcxx/include/__algorithm/copy.h

46

Since this is pre-existing I'd rather fix it in a follow-up. This patch is already quite large.

129

I think this is a problem. But I don't really have a good idea how to fix it. Using if constexpr would probably do the job, but we don't have that option.

libcxx/include/__iterator/segmented_iterator.h

18–26

I didn't define the return type more specifically here on purpose, so what should I return from the deleted functions?

[huixie90]

libcxx/include/__algorithm/copy.h

46

sounds good to me

129

I feel that someone is going to promote his priority_tag thing

libcxx/include/__iterator/segmented_iterator.h

18–26

perhaps just return auto?

[ldionne]

I really like this patch in spirit! It should be rebased onto main, though.

libcxx/include/__algorithm/copy.h

116

It seems to me that what you really need here is some kind of __copy_up_to primitive, where we would copy [__first, as-far-as-we-can-go) to [__segment.__begin_, segment-end). Then you would not need to know the size of the input segment, and this optimization would apply to non-random-access iterators as well.

It might not be worth trying to optimize for non random-access input iterators anyway though, since we will end up having to loop over each element regardless inside __copy_up_to, which is not much better than what we'd do without applying any segmented optimization at all.

libcxx/include/__iterator/segmented_iterator.h

13–27

I think your definition of segmented iterators is an excellent starting point, however we could make the following changes based on prior art (http://lafstern.org/matt/segmented.pdf):

// 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.
//
// Given Traits = __segmented_iterator_traits<It>, if Traits::__is_segmented_iterator::value
// is true, 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.

Then, you can use it as:

void f(__deque_iterator<T> __first, __deque_iterator<T> __last) {
    using _Traits = __segmented_iterator_traits<__deque_iterator<T> >;

    Traits::__segment_iterator __sfirst = _Traits::__segment(__first);
    Traits::__segment_iterator __slast = _Traits::__segment(__last);
    use(Traits::__local(__first), Traits::__end(__sfirst)); // special case the first block
    for (++__sfirst; __sfirst != __slast; ++__sfirst) {
      use(Traits::__begin(__sfirst), Traits::__end(__sfirst));
    }
    use(Traits::__begin(__slast), Traits::__local(__last));
}

At a glance, I think we would implement the traits for deque something like:

template <class T>
struct __segmented_iterator_traits<__deque_iterator<T> > {
  struct __segment_iterator {
    // fun stuff
  };

  using __local_iterator = T*;

  static __segment_iterator __segment(__deque_iterator<T> __it) {
    return __segment_iterator(__it.__m_iter_);
  }

  static __local_iterator __local(__deque_iterator<T> __it) {
    return __it.__ptr_;
  }

  static __local_iterator __begin(__segment_iterator __it) {
    return *__it.__m_iter_;
  }

  static __local_iterator __end(__segment_iterator __it) {
    return *__it.__m_iter_ + BLOCK_SIZE;
  }
};

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp

82

Also fix ranges::move with contiguous iterators and non-iterator sentinels as a drive-by.

I would really prefer doing this separately. If @var-const 's patch does that already, can you simply double-check that your added tests pass now? Basically I want to make sure that you don't lose test coverage when you rebase on top of his change.

[EricWF]

My understanding of these algorithms is that they were hand-tuned to produce optimizer friendly (at the time) codegen.

How are we verifying the performance impact of this change? Or is that not a concern?

[ldionne]

In D132505#3778038, @EricWF wrote:

My understanding of these algorithms is that they were hand-tuned to produce optimizer friendly (at the time) codegen.

How are we verifying the performance impact of this change? Or is that not a concern?

Performance is clearly a concern, and in fact it's the whole purpose of this part of the codebase. I think we should take a look at the codegen before and after. We can also add a simple benchmark in our benchmark infrastructure.

That being said, this is a fairly macro optimization, not a micro optimization, so I'm less concerned about the exact codegen (not that we should ignore it). The real micro optimization happens inside the non-segmented version of std::__copy, where we use memmove if we can.

[philnik]

Address comments

[philnik]

Here are the benchmarks for the current patch:

-----------------------------------------------------------------------
Benchmark                                             old           new
-----------------------------------------------------------------------
BM_deque_vector_copy/0                           0.272 ns       1.58 ns
BM_deque_vector_copy/1                            3.40 ns       1.85 ns
BM_deque_vector_copy/2                            3.30 ns       1.72 ns
BM_deque_vector_copy/64                           4.24 ns       2.90 ns
BM_deque_vector_copy/512                          18.6 ns       17.2 ns
BM_deque_vector_copy/1024                         41.3 ns       40.1 ns
BM_deque_vector_copy/4000                          145 ns        127 ns
BM_deque_vector_copy/4096                          148 ns        132 ns
BM_deque_vector_copy/5500                          196 ns        169 ns
BM_deque_vector_copy/64000                        5518 ns       5554 ns
BM_deque_vector_copy/65536                        5665 ns       5680 ns
BM_deque_vector_copy/70000                        5852 ns       5772 ns
BM_deque_vector_ranges_copy/0                    0.265 ns       1.58 ns
BM_deque_vector_ranges_copy/1                     1.30 ns       1.87 ns
BM_deque_vector_ranges_copy/2                     1.60 ns       1.72 ns
BM_deque_vector_ranges_copy/64                    23.5 ns       2.90 ns
BM_deque_vector_ranges_copy/512                    188 ns       16.9 ns
BM_deque_vector_ranges_copy/1024                   370 ns       39.5 ns
BM_deque_vector_ranges_copy/4000                  1437 ns        128 ns
BM_deque_vector_ranges_copy/4096                  1474 ns        128 ns
BM_deque_vector_ranges_copy/5500                  1990 ns        170 ns
BM_deque_vector_ranges_copy/64000                23213 ns       5503 ns
BM_deque_vector_ranges_copy/65536                23703 ns       5436 ns
BM_deque_vector_ranges_copy/70000                25287 ns       5897 ns
BM_deque_deque_copy/0                             1.06 ns       7.18 ns
BM_deque_deque_copy/1                             5.77 ns       12.8 ns
BM_deque_deque_copy/2                             5.63 ns       13.1 ns
BM_deque_deque_copy/64                            6.42 ns       15.2 ns
BM_deque_deque_copy/512                           21.4 ns       29.1 ns
BM_deque_deque_copy/1024                          43.0 ns       56.9 ns
BM_deque_deque_copy/4000                           114 ns        116 ns
BM_deque_deque_copy/4096                           171 ns        177 ns
BM_deque_deque_copy/5500                           236 ns        225 ns
BM_deque_deque_copy/64000                         5387 ns       5431 ns
BM_deque_deque_copy/65536                         5552 ns       5560 ns
BM_deque_deque_copy/70000                         5882 ns       5941 ns
BM_deque_deque_ranges_copy/0                     0.793 ns       7.12 ns
BM_deque_deque_ranges_copy/1                      1.85 ns       12.8 ns
BM_deque_deque_ranges_copy/2                      2.38 ns       13.0 ns
BM_deque_deque_ranges_copy/64                     44.4 ns       15.2 ns
BM_deque_deque_ranges_copy/512                     281 ns       29.1 ns
BM_deque_deque_ranges_copy/1024                    555 ns       56.9 ns
BM_deque_deque_ranges_copy/4000                   2155 ns        115 ns
BM_deque_deque_ranges_copy/4096                   2217 ns        177 ns
BM_deque_deque_ranges_copy/5500                   2977 ns        226 ns
BM_deque_deque_ranges_copy/64000                 34584 ns       5432 ns
BM_deque_deque_ranges_copy/65536                 35419 ns       5572 ns
BM_deque_deque_ranges_copy/70000                 37847 ns       5972 ns
BM_vector_deque_copy/0                           0.585 ns      0.529 ns
BM_vector_deque_copy/1                            2.98 ns       2.73 ns
BM_vector_deque_copy/2                            2.79 ns       2.62 ns
BM_vector_deque_copy/64                           3.70 ns       3.44 ns
BM_vector_deque_copy/512                          13.5 ns       13.6 ns
BM_vector_deque_copy/1024                         40.0 ns       40.1 ns
BM_vector_deque_copy/4000                          145 ns        144 ns
BM_vector_deque_copy/4096                          147 ns        147 ns
BM_vector_deque_copy/5500                          199 ns        201 ns
BM_vector_deque_copy/64000                        5452 ns       5462 ns
BM_vector_deque_copy/65536                        5718 ns       5691 ns
BM_vector_deque_copy/70000                        5985 ns       5988 ns
BM_vector_deque_ranges_copy/0                    0.529 ns      0.528 ns
BM_vector_deque_ranges_copy/1                     1.06 ns       2.69 ns
BM_vector_deque_ranges_copy/2                     1.46 ns       2.65 ns
BM_vector_deque_ranges_copy/64                    23.2 ns       3.51 ns
BM_vector_deque_ranges_copy/512                    187 ns       14.0 ns
BM_vector_deque_ranges_copy/1024                   369 ns       40.2 ns
BM_vector_deque_ranges_copy/4000                  1440 ns        145 ns
BM_vector_deque_ranges_copy/4096                  1474 ns        146 ns
BM_vector_deque_ranges_copy/5500                  1979 ns        202 ns
BM_vector_deque_ranges_copy/64000                22995 ns       5512 ns
BM_vector_deque_ranges_copy/65536                23549 ns       5695 ns
BM_vector_deque_ranges_copy/70000                25182 ns       6064 ns
BM_deque_vector_move/0                           0.266 ns       1.61 ns
BM_deque_vector_move/1                            3.26 ns       1.91 ns
BM_deque_vector_move/2                            3.23 ns       1.73 ns
BM_deque_vector_move/64                           4.24 ns       2.90 ns
BM_deque_vector_move/512                          14.1 ns       13.5 ns
BM_deque_vector_move/1024                         40.4 ns       39.5 ns
BM_deque_vector_move/4000                          144 ns        128 ns
BM_deque_vector_move/4096                          144 ns        128 ns
BM_deque_vector_move/5500                          200 ns        170 ns
BM_deque_vector_move/64000                        5482 ns       5481 ns
BM_deque_vector_move/65536                        5436 ns       5397 ns
BM_deque_vector_move/70000                        5846 ns       5795 ns
BM_deque_vector_ranges_move/0                    0.264 ns       1.58 ns
BM_deque_vector_ranges_move/1                     1.32 ns       1.85 ns
BM_deque_vector_ranges_move/2                     1.59 ns       1.72 ns
BM_deque_vector_ranges_move/64                    35.3 ns       2.90 ns
BM_deque_vector_ranges_move/512                    202 ns       13.5 ns
BM_deque_vector_ranges_move/1024                   395 ns       39.5 ns
BM_deque_vector_ranges_move/4000                  1548 ns        128 ns
BM_deque_vector_ranges_move/4096                  1559 ns        128 ns
BM_deque_vector_ranges_move/5500                  2133 ns        170 ns
BM_deque_vector_ranges_move/64000                24609 ns       5478 ns
BM_deque_vector_ranges_move/65536                25182 ns       5396 ns
BM_deque_vector_ranges_move/70000                27414 ns       5783 ns
BM_deque_deque_move/0                             1.06 ns       7.12 ns
BM_deque_deque_move/1                             5.67 ns       12.7 ns
BM_deque_deque_move/2                             5.54 ns       12.9 ns
BM_deque_deque_move/64                            6.37 ns       15.1 ns
BM_deque_deque_move/512                           21.3 ns       28.8 ns
BM_deque_deque_move/1024                          43.0 ns       56.8 ns
BM_deque_deque_move/4000                           112 ns        116 ns
BM_deque_deque_move/4096                           171 ns        177 ns
BM_deque_deque_move/5500                           233 ns        228 ns
BM_deque_deque_move/64000                         5378 ns       5442 ns
BM_deque_deque_move/65536                         5546 ns       5578 ns
BM_deque_deque_move/70000                         5877 ns       5932 ns
BM_deque_deque_ranges_move/0                     0.792 ns       7.12 ns
BM_deque_deque_ranges_move/1                      1.85 ns       12.7 ns
BM_deque_deque_ranges_move/2                      2.38 ns       13.0 ns
BM_deque_deque_ranges_move/64                     43.9 ns       15.1 ns
BM_deque_deque_ranges_move/512                     281 ns       28.8 ns
BM_deque_deque_ranges_move/1024                    560 ns       56.8 ns
BM_deque_deque_ranges_move/4000                   2171 ns        115 ns
BM_deque_deque_ranges_move/4096                   2245 ns        177 ns
BM_deque_deque_ranges_move/5500                   3013 ns        225 ns
BM_deque_deque_ranges_move/64000                 35085 ns       5429 ns
BM_deque_deque_ranges_move/65536                 35939 ns       5560 ns
BM_deque_deque_ranges_move/70000                 38388 ns       5935 ns
BM_vector_deque_move/0                           0.597 ns      0.534 ns
BM_vector_deque_move/1                            2.83 ns       2.71 ns
BM_vector_deque_move/2                            2.70 ns       2.60 ns
BM_vector_deque_move/64                           3.68 ns       3.44 ns
BM_vector_deque_move/512                          13.5 ns       13.6 ns
BM_vector_deque_move/1024                         39.9 ns       40.1 ns
BM_vector_deque_move/4000                          145 ns        144 ns
BM_vector_deque_move/4096                          146 ns        146 ns
BM_vector_deque_move/5500                          200 ns        200 ns
BM_vector_deque_move/64000                        5454 ns       5460 ns
BM_vector_deque_move/65536                        5722 ns       5686 ns
BM_vector_deque_move/70000                        5986 ns       5984 ns
BM_vector_deque_ranges_move/0                    0.539 ns      0.528 ns
BM_vector_deque_ranges_move/1                     1.06 ns       2.71 ns
BM_vector_deque_ranges_move/2                     1.47 ns       2.58 ns
BM_vector_deque_ranges_move/64                    24.0 ns       3.44 ns
BM_vector_deque_ranges_move/512                    189 ns       13.6 ns
BM_vector_deque_ranges_move/1024                   375 ns       40.1 ns
BM_vector_deque_ranges_move/4000                  1436 ns        144 ns
BM_vector_deque_ranges_move/4096                  1472 ns        146 ns
BM_vector_deque_ranges_move/5500                  1977 ns        200 ns
BM_vector_deque_ranges_move/64000                22981 ns       5466 ns
BM_vector_deque_ranges_move/65536                23577 ns       5688 ns
BM_vector_deque_ranges_move/70000                25131 ns       5985 ns
BM_deque_vector_copy_backward/0                  0.264 ns       1.58 ns
BM_deque_vector_copy_backward/1                   2.96 ns       1.86 ns
BM_deque_vector_copy_backward/2                   3.55 ns       1.72 ns
BM_deque_vector_copy_backward/64                  4.49 ns       2.93 ns
BM_deque_vector_copy_backward/512                 16.1 ns       13.2 ns
BM_deque_vector_copy_backward/1024                41.1 ns       40.0 ns
BM_deque_vector_copy_backward/4000                 151 ns        126 ns
BM_deque_vector_copy_backward/4096                 145 ns        127 ns
BM_deque_vector_copy_backward/5500                 211 ns        170 ns
BM_deque_vector_copy_backward/64000               5471 ns       5506 ns
BM_deque_vector_copy_backward/65536               5439 ns       5415 ns
BM_deque_vector_copy_backward/70000               5838 ns       5786 ns
BM_deque_vector_ranges_copy_backward/0           0.264 ns       1.58 ns
BM_deque_vector_ranges_copy_backward/1            1.17 ns       1.85 ns
BM_deque_vector_ranges_copy_backward/2            1.45 ns       1.73 ns
BM_deque_vector_ranges_copy_backward/64           26.0 ns       3.11 ns
BM_deque_vector_ranges_copy_backward/512           147 ns       13.3 ns
BM_deque_vector_ranges_copy_backward/1024          282 ns       40.1 ns
BM_deque_vector_ranges_copy_backward/4000         1103 ns        127 ns
BM_deque_vector_ranges_copy_backward/4096         1131 ns        127 ns
BM_deque_vector_ranges_copy_backward/5500         1514 ns        170 ns
BM_deque_vector_ranges_copy_backward/6400        17553 ns       5515 ns
BM_deque_vector_ranges_copy_backward/6553        17944 ns       5415 ns
BM_deque_vector_ranges_copy_backward/7000        19183 ns       5784 ns
BM_deque_deque_copy_backward/0                    1.16 ns       1.32 ns
BM_deque_deque_copy_backward/1                    6.58 ns       3.17 ns
BM_deque_deque_copy_backward/2                    6.87 ns       3.17 ns
BM_deque_deque_copy_backward/64                   7.77 ns       4.19 ns
BM_deque_deque_copy_backward/512                  24.3 ns       19.2 ns
BM_deque_deque_copy_backward/1024                 46.2 ns       43.5 ns
BM_deque_deque_copy_backward/4000                  121 ns        101 ns
BM_deque_deque_copy_backward/4096                  179 ns        163 ns
BM_deque_deque_copy_backward/5500                  247 ns        216 ns
BM_deque_deque_copy_backward/64000                5362 ns       5408 ns
BM_deque_deque_copy_backward/65536                5474 ns       5647 ns
BM_deque_deque_copy_backward/70000                5856 ns       5948 ns
BM_deque_deque_ranges_copy_backward/0            0.792 ns       1.33 ns
BM_deque_deque_ranges_copy_backward/1             2.04 ns       3.17 ns
BM_deque_deque_ranges_copy_backward/2             2.93 ns       3.17 ns
BM_deque_deque_ranges_copy_backward/64            56.0 ns       4.19 ns
BM_deque_deque_ranges_copy_backward/512            372 ns       19.2 ns
BM_deque_deque_ranges_copy_backward/1024           715 ns       43.5 ns
BM_deque_deque_ranges_copy_backward/4000          2839 ns        101 ns
BM_deque_deque_ranges_copy_backward/4096          2861 ns        163 ns
BM_deque_deque_ranges_copy_backward/5500          3850 ns        217 ns
BM_deque_deque_ranges_copy_backward/64000        42909 ns       5404 ns
BM_deque_deque_ranges_copy_backward/65536        44236 ns       5572 ns
BM_deque_deque_ranges_copy_backward/70000        47484 ns       5997 ns
BM_vector_deque_copy_backward/0                  0.597 ns      0.532 ns
BM_vector_deque_copy_backward/1                   4.17 ns       2.15 ns
BM_vector_deque_copy_backward/2                   3.83 ns       2.03 ns
BM_vector_deque_copy_backward/64                  4.99 ns       3.49 ns
BM_vector_deque_copy_backward/512                 18.1 ns       14.0 ns
BM_vector_deque_copy_backward/1024                43.6 ns       41.1 ns
BM_vector_deque_copy_backward/4000                 160 ns        135 ns
BM_vector_deque_copy_backward/4096                 160 ns        138 ns
BM_vector_deque_copy_backward/5500                 225 ns        180 ns
BM_vector_deque_copy_backward/64000               5458 ns       5435 ns
BM_vector_deque_copy_backward/65536               5648 ns       5652 ns
BM_vector_deque_copy_backward/70000               6021 ns       6026 ns
BM_vector_deque_ranges_copy_backward/0           0.529 ns      0.529 ns
BM_vector_deque_ranges_copy_backward/1            1.06 ns       2.11 ns
BM_vector_deque_ranges_copy_backward/2            1.35 ns       1.98 ns
BM_vector_deque_ranges_copy_backward/64           25.4 ns       3.43 ns
BM_vector_deque_ranges_copy_backward/512           166 ns       13.8 ns
BM_vector_deque_ranges_copy_backward/1024          286 ns       41.0 ns
BM_vector_deque_ranges_copy_backward/4000         1149 ns        134 ns
BM_vector_deque_ranges_copy_backward/4096         1138 ns        138 ns
BM_vector_deque_ranges_copy_backward/5500         1536 ns        180 ns
BM_vector_deque_ranges_copy_backward/6400        17771 ns       5435 ns
BM_vector_deque_ranges_copy_backward/6553        18343 ns       5653 ns
BM_vector_deque_ranges_copy_backward/7000        19422 ns       6024 ns
BM_deque_vector_move_backward/0                  0.271 ns       1.58 ns
BM_deque_vector_move_backward/1                   2.91 ns       1.85 ns
BM_deque_vector_move_backward/2                   3.51 ns       1.72 ns
BM_deque_vector_move_backward/64                  4.49 ns       2.94 ns
BM_deque_vector_move_backward/512                 15.8 ns       13.3 ns
BM_deque_vector_move_backward/1024                41.2 ns       40.0 ns
BM_deque_vector_move_backward/4000                 147 ns        126 ns
BM_deque_vector_move_backward/4096                 145 ns        127 ns
BM_deque_vector_move_backward/5500                 207 ns        170 ns
BM_deque_vector_move_backward/64000               5465 ns       5512 ns
BM_deque_vector_move_backward/65536               5435 ns       5414 ns
BM_deque_vector_move_backward/70000               5835 ns       5788 ns
BM_deque_vector_ranges_move_backward/0           0.264 ns       1.58 ns
BM_deque_vector_ranges_move_backward/1            1.17 ns       1.85 ns
BM_deque_vector_ranges_move_backward/2            1.45 ns       1.72 ns
BM_deque_vector_ranges_move_backward/64           23.2 ns       3.11 ns
BM_deque_vector_ranges_move_backward/512           147 ns       13.3 ns
BM_deque_vector_ranges_move_backward/1024          281 ns       39.9 ns
BM_deque_vector_ranges_move_backward/4000         1097 ns        126 ns
BM_deque_vector_ranges_move_backward/4096         1122 ns        127 ns
BM_deque_vector_ranges_move_backward/5500         1514 ns        170 ns
BM_deque_vector_ranges_move_backward/6400        17551 ns       5502 ns
BM_deque_vector_ranges_move_backward/6553        17944 ns       5415 ns
BM_deque_vector_ranges_move_backward/7000        19183 ns       5787 ns
BM_deque_deque_move_backward/0                    1.17 ns       1.32 ns
BM_deque_deque_move_backward/1                    6.60 ns       3.17 ns
BM_deque_deque_move_backward/2                    6.87 ns       3.17 ns
BM_deque_deque_move_backward/64                   7.78 ns       4.19 ns
BM_deque_deque_move_backward/512                  24.2 ns       19.2 ns
BM_deque_deque_move_backward/1024                 46.2 ns       43.5 ns
BM_deque_deque_move_backward/4000                  121 ns        101 ns
BM_deque_deque_move_backward/4096                  179 ns        163 ns
BM_deque_deque_move_backward/5500                  247 ns        216 ns
BM_deque_deque_move_backward/64000                5361 ns       5401 ns
BM_deque_deque_move_backward/65536                5465 ns       5531 ns
BM_deque_deque_move_backward/70000                5845 ns       5942 ns
BM_deque_deque_ranges_move_backward/0            0.791 ns       1.32 ns
BM_deque_deque_ranges_move_backward/1             2.04 ns       3.17 ns
BM_deque_deque_ranges_move_backward/2             2.93 ns       3.17 ns
BM_deque_deque_ranges_move_backward/64            55.7 ns       4.19 ns
BM_deque_deque_ranges_move_backward/512            351 ns       19.2 ns
BM_deque_deque_ranges_move_backward/1024           689 ns       43.5 ns
BM_deque_deque_ranges_move_backward/4000          2685 ns        102 ns
BM_deque_deque_ranges_move_backward/4096          2743 ns        163 ns
BM_deque_deque_ranges_move_backward/5500          3698 ns        215 ns
BM_deque_deque_ranges_move_backward/64000        42808 ns       5394 ns
BM_deque_deque_ranges_move_backward/65536        43858 ns       5531 ns
BM_deque_deque_ranges_move_backward/70000        46853 ns       5941 ns
BM_vector_deque_move_backward/0                  0.621 ns      0.528 ns
BM_vector_deque_move_backward/1                   4.17 ns       2.11 ns
BM_vector_deque_move_backward/2                   3.84 ns       1.98 ns
BM_vector_deque_move_backward/64                  4.99 ns       3.43 ns
BM_vector_deque_move_backward/512                 18.1 ns       13.8 ns
BM_vector_deque_move_backward/1024                43.6 ns       41.0 ns
BM_vector_deque_move_backward/4000                 160 ns        134 ns
BM_vector_deque_move_backward/4096                 160 ns        138 ns
BM_vector_deque_move_backward/5500                 225 ns        180 ns
BM_vector_deque_move_backward/64000               5457 ns       5433 ns
BM_vector_deque_move_backward/65536               5646 ns       5650 ns
BM_vector_deque_move_backward/70000               6020 ns       6027 ns
BM_vector_deque_ranges_move_backward/0           0.536 ns      0.529 ns
BM_vector_deque_ranges_move_backward/1            1.06 ns       2.11 ns
BM_vector_deque_ranges_move_backward/2            1.33 ns       1.98 ns
BM_vector_deque_ranges_move_backward/64           28.9 ns       3.43 ns
BM_vector_deque_ranges_move_backward/512           160 ns       13.8 ns
BM_vector_deque_ranges_move_backward/1024          286 ns       41.0 ns
BM_vector_deque_ranges_move_backward/4000         1197 ns        134 ns
BM_vector_deque_ranges_move_backward/4096         1138 ns        138 ns
BM_vector_deque_ranges_move_backward/5500         1552 ns        180 ns
BM_vector_deque_ranges_move_backward/6400        17834 ns       5432 ns
BM_vector_deque_ranges_move_backward/6553        18351 ns       5654 ns
BM_vector_deque_ranges_move_backward/7000        19473 ns       6028 ns

libcxx/include/__algorithm/copy.h

46

Doesn't apply anymore, since @var-const refactored it.

129

Also doesn't apply anymore.

[ldionne]

I think this is a really really nice generalization. It's super elegant how the segmented iterator traits bridge perfectly with our existing deque iterator.

The speedup this provides for ranges is extremely valuable too, and it opens the door to doing the same for other segmented iterators (maybe join_view)?

libcxx/benchmarks/CMakeLists.txt

171

Not tied to this file: Let's add a release note. This is an interesting optimization and it will yield large performance benefits for all segmented iterators, so it's worth advertising.

libcxx/benchmarks/deque_iterator.bench.cpp

2

I would be curious to try adding _LIBCPP_ALWAYS_INLINE to __unwrap_and_dispatch (and possibly other implementation details in that code path) to see what impact it has on the benchmarks. Could you try that out and report? I would assume that for raw pointers, that should all end up being inlined away.

libcxx/include/__algorithm/copy_backward.h

54

Just a matter of personal preference, but I find these names quite long (__first_segment, __last_segment). IMO it would be a bit easier to read with shorter names because of how the lines would be wrapped. I'd suggest __sfirst and __slast, which I think is idiomatic to segmented iterators based on the paper we looked at.

96

Here and in a few other places, a using _DiffT = typename common_type<__iter_diff_t<_InIter>, __iter_diff_t<_OutIter> >::type; would increase readability.

98

108–120

I think you can pretty easily remove the special casing for the last segment by doing something like this. I'm not saying it's the best way to write it, but it should be possible to remove the special case.

Also, let's use {} on the if since it spans multiple lines.

libcxx/include/__iterator/segmented_iterator.h

31

Indentation here and below doesn't match above.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp

80

The indentation is crazy here.

[philnik]

• Address comments

[philnik]

For completeness, here are the updated numbers:

--------------------------------------------------------------------
Benchmark                                         old            new
--------------------------------------------------------------------
BM_deque_vector_copy/0                       0.272 ns        1.58 ns
BM_deque_vector_copy/1                        3.40 ns        1.85 ns
BM_deque_vector_copy/2                        3.30 ns        1.72 ns
BM_deque_vector_copy/64                       4.24 ns        2.90 ns
BM_deque_vector_copy/512                      18.6 ns        26.1 ns
BM_deque_vector_copy/1024                     41.3 ns        40.1 ns
BM_deque_vector_copy/4000                      145 ns         127 ns
BM_deque_vector_copy/4096                      148 ns         131 ns
BM_deque_vector_copy/5500                      196 ns         167 ns
BM_deque_vector_copy/64000                    5518 ns        5647 ns
BM_deque_vector_copy/65536                    5665 ns        5674 ns
BM_deque_vector_copy/70000                    5852 ns        5852 ns
BM_deque_vector_ranges_copy/0                0.265 ns        1.58 ns
BM_deque_vector_ranges_copy/1                 1.30 ns        1.85 ns
BM_deque_vector_ranges_copy/2                 1.60 ns        1.73 ns
BM_deque_vector_ranges_copy/64                23.5 ns        2.90 ns
BM_deque_vector_ranges_copy/512                188 ns        16.9 ns
BM_deque_vector_ranges_copy/1024               370 ns        39.5 ns
BM_deque_vector_ranges_copy/4000              1437 ns         128 ns
BM_deque_vector_ranges_copy/4096              1474 ns         128 ns
BM_deque_vector_ranges_copy/5500              1990 ns         171 ns
BM_deque_vector_ranges_copy/64000            23213 ns        5533 ns
BM_deque_vector_ranges_copy/65536            23703 ns        5469 ns
BM_deque_vector_ranges_copy/70000            25287 ns        5884 ns
BM_deque_deque_copy/0                         1.06 ns        1.24 ns
BM_deque_deque_copy/1                         5.77 ns        3.11 ns
BM_deque_deque_copy/2                         5.63 ns        2.91 ns
BM_deque_deque_copy/64                        6.42 ns        4.03 ns
BM_deque_deque_copy/512                       21.4 ns        18.8 ns
BM_deque_deque_copy/1024                      43.0 ns        41.7 ns
BM_deque_deque_copy/4000                       114 ns        97.6 ns
BM_deque_deque_copy/4096                       171 ns         156 ns
BM_deque_deque_copy/5500                       236 ns         204 ns
BM_deque_deque_copy/64000                     5387 ns        5406 ns
BM_deque_deque_copy/65536                     5552 ns        5566 ns
BM_deque_deque_copy/70000                     5882 ns        5907 ns
BM_deque_deque_ranges_copy/0                 0.793 ns        1.21 ns
BM_deque_deque_ranges_copy/1                  1.85 ns        3.12 ns
BM_deque_deque_ranges_copy/2                  2.38 ns        2.90 ns
BM_deque_deque_ranges_copy/64                 44.4 ns        4.03 ns
BM_deque_deque_ranges_copy/512                 281 ns        18.7 ns
BM_deque_deque_ranges_copy/1024                555 ns        41.8 ns
BM_deque_deque_ranges_copy/4000               2155 ns        97.8 ns
BM_deque_deque_ranges_copy/4096               2217 ns         156 ns
BM_deque_deque_ranges_copy/5500               2977 ns         206 ns
BM_deque_deque_ranges_copy/64000             34584 ns        5412 ns
BM_deque_deque_ranges_copy/65536             35419 ns        5582 ns
BM_deque_deque_ranges_copy/70000             37847 ns        5912 ns
BM_vector_deque_copy/0                       0.585 ns       0.528 ns
BM_vector_deque_copy/1                        2.98 ns        2.11 ns
BM_vector_deque_copy/2                        2.79 ns        1.98 ns
BM_vector_deque_copy/64                       3.70 ns        3.44 ns
BM_vector_deque_copy/512                      13.5 ns        13.4 ns
BM_vector_deque_copy/1024                     40.0 ns        39.2 ns
BM_vector_deque_copy/4000                      145 ns         130 ns
BM_vector_deque_copy/4096                      147 ns         135 ns
BM_vector_deque_copy/5500                      199 ns         182 ns
BM_vector_deque_copy/64000                    5452 ns        5424 ns
BM_vector_deque_copy/65536                    5718 ns        5698 ns
BM_vector_deque_copy/70000                    5985 ns        5992 ns
BM_vector_deque_ranges_copy/0                0.529 ns       0.531 ns
BM_vector_deque_ranges_copy/1                 1.06 ns        2.11 ns
BM_vector_deque_ranges_copy/2                 1.46 ns        1.98 ns
BM_vector_deque_ranges_copy/64                23.2 ns        3.44 ns
BM_vector_deque_ranges_copy/512                187 ns        13.5 ns
BM_vector_deque_ranges_copy/1024               369 ns        39.2 ns
BM_vector_deque_ranges_copy/4000              1440 ns         130 ns
BM_vector_deque_ranges_copy/4096              1474 ns         135 ns
BM_vector_deque_ranges_copy/5500              1979 ns         182 ns
BM_vector_deque_ranges_copy/64000            22995 ns        5421 ns
BM_vector_deque_ranges_copy/65536            23549 ns        5705 ns
BM_vector_deque_ranges_copy/70000            25182 ns        5994 ns
BM_deque_vector_move/0                       0.266 ns        1.59 ns
BM_deque_vector_move/1                        3.26 ns        1.85 ns
BM_deque_vector_move/2                        3.23 ns        1.72 ns
BM_deque_vector_move/64                       4.24 ns        2.90 ns
BM_deque_vector_move/512                      14.1 ns        13.5 ns
BM_deque_vector_move/1024                     40.4 ns        39.5 ns
BM_deque_vector_move/4000                      144 ns         128 ns
BM_deque_vector_move/4096                      144 ns         128 ns
BM_deque_vector_move/5500                      200 ns         171 ns
BM_deque_vector_move/64000                    5482 ns        5458 ns
BM_deque_vector_move/65536                    5436 ns        5469 ns
BM_deque_vector_move/70000                    5846 ns        5781 ns
BM_deque_vector_ranges_move/0                0.264 ns        1.58 ns
BM_deque_vector_ranges_move/1                 1.32 ns        1.85 ns
BM_deque_vector_ranges_move/2                 1.59 ns        1.72 ns
BM_deque_vector_ranges_move/64                35.3 ns        2.91 ns
BM_deque_vector_ranges_move/512                202 ns        13.4 ns
BM_deque_vector_ranges_move/1024               395 ns        39.5 ns
BM_deque_vector_ranges_move/4000              1548 ns         128 ns
BM_deque_vector_ranges_move/4096              1559 ns         128 ns
BM_deque_vector_ranges_move/5500              2133 ns         170 ns
BM_deque_vector_ranges_move/64000            24609 ns        5460 ns
BM_deque_vector_ranges_move/65536            25182 ns        5470 ns
BM_deque_vector_ranges_move/70000            27414 ns        5774 ns
BM_deque_deque_move/0                         1.06 ns        1.22 ns
BM_deque_deque_move/1                         5.67 ns        3.10 ns
BM_deque_deque_move/2                         5.54 ns        2.90 ns
BM_deque_deque_move/64                        6.37 ns        4.00 ns
BM_deque_deque_move/512                       21.3 ns        18.8 ns
BM_deque_deque_move/1024                      43.0 ns        41.7 ns
BM_deque_deque_move/4000                       112 ns        97.6 ns
BM_deque_deque_move/4096                       171 ns         156 ns
BM_deque_deque_move/5500                       233 ns         206 ns
BM_deque_deque_move/64000                     5378 ns        5401 ns
BM_deque_deque_move/65536                     5546 ns        5562 ns
BM_deque_deque_move/70000                     5877 ns        5911 ns
BM_deque_deque_ranges_move/0                 0.792 ns        1.21 ns
BM_deque_deque_ranges_move/1                  1.85 ns        3.10 ns
BM_deque_deque_ranges_move/2                  2.38 ns        2.90 ns
BM_deque_deque_ranges_move/64                 43.9 ns        4.02 ns
BM_deque_deque_ranges_move/512                 281 ns        18.8 ns
BM_deque_deque_ranges_move/1024                560 ns        41.7 ns
BM_deque_deque_ranges_move/4000               2171 ns        97.6 ns
BM_deque_deque_ranges_move/4096               2245 ns         156 ns
BM_deque_deque_ranges_move/5500               3013 ns         204 ns
BM_deque_deque_ranges_move/64000             35085 ns        5399 ns
BM_deque_deque_ranges_move/65536             35939 ns        5560 ns
BM_deque_deque_ranges_move/70000             38388 ns        5903 ns
BM_vector_deque_move/0                       0.597 ns       0.579 ns
BM_vector_deque_move/1                        2.83 ns        2.11 ns
BM_vector_deque_move/2                        2.70 ns        1.98 ns
BM_vector_deque_move/64                       3.68 ns        3.43 ns
BM_vector_deque_move/512                      13.5 ns        13.5 ns
BM_vector_deque_move/1024                     39.9 ns        39.1 ns
BM_vector_deque_move/4000                      145 ns         130 ns
BM_vector_deque_move/4096                      146 ns         135 ns
BM_vector_deque_move/5500                      200 ns         182 ns
BM_vector_deque_move/64000                    5454 ns        5422 ns
BM_vector_deque_move/65536                    5722 ns        5693 ns
BM_vector_deque_move/70000                    5986 ns        5992 ns
BM_vector_deque_ranges_move/0                0.539 ns       0.528 ns
BM_vector_deque_ranges_move/1                 1.06 ns        2.13 ns
BM_vector_deque_ranges_move/2                 1.47 ns        1.99 ns
BM_vector_deque_ranges_move/64                24.0 ns        3.44 ns
BM_vector_deque_ranges_move/512                189 ns        13.8 ns
BM_vector_deque_ranges_move/1024               375 ns        39.5 ns
BM_vector_deque_ranges_move/4000              1436 ns         130 ns
BM_vector_deque_ranges_move/4096              1472 ns         135 ns
BM_vector_deque_ranges_move/5500              1977 ns         183 ns
BM_vector_deque_ranges_move/64000            22981 ns        5660 ns
BM_vector_deque_ranges_move/65536            23577 ns        5888 ns
BM_vector_deque_ranges_move/70000            25131 ns        6174 ns
BM_deque_vector_copy_backward/0              0.264 ns        1.61 ns
BM_deque_vector_copy_backward/1               2.96 ns        1.87 ns
BM_deque_vector_copy_backward/2               3.55 ns        1.75 ns
BM_deque_vector_copy_backward/64              4.49 ns        3.02 ns
BM_deque_vector_copy_backward/512             16.1 ns        13.4 ns
BM_deque_vector_copy_backward/1024            41.1 ns        40.3 ns
BM_deque_vector_copy_backward/4000             151 ns         128 ns
BM_deque_vector_copy_backward/4096             145 ns         129 ns
BM_deque_vector_copy_backward/5500             211 ns         171 ns
BM_deque_vector_copy_backward/64000           5471 ns        5517 ns
BM_deque_vector_copy_backward/65536           5439 ns        5440 ns
BM_deque_vector_copy_backward/70000           5838 ns        5775 ns
BM_deque_vector_ranges_copy_backward/0       0.264 ns        1.58 ns
BM_deque_vector_ranges_copy_backward/1        1.17 ns        1.85 ns
BM_deque_vector_ranges_copy_backward/2        1.45 ns        1.72 ns
BM_deque_vector_ranges_copy_backward/64       26.0 ns        3.12 ns
BM_deque_vector_ranges_copy_backward/512       147 ns        13.2 ns
BM_deque_vector_ranges_copy_backward/1024      282 ns        39.9 ns
BM_deque_vector_ranges_copy_backward/4000     1103 ns         126 ns
BM_deque_vector_ranges_copy_backward/4096     1131 ns         127 ns
BM_deque_vector_ranges_copy_backward/5500     1514 ns         171 ns
BM_deque_vector_ranges_copy_backward/64000   17553 ns        5512 ns
BM_deque_vector_ranges_copy_backward/65536   17944 ns        5441 ns
BM_deque_vector_ranges_copy_backward/70000   19183 ns        5772 ns
BM_deque_deque_copy_backward/0                1.16 ns        1.33 ns
BM_deque_deque_copy_backward/1                6.58 ns        3.17 ns
BM_deque_deque_copy_backward/2                6.87 ns        3.17 ns
BM_deque_deque_copy_backward/64               7.77 ns        4.18 ns
BM_deque_deque_copy_backward/512              24.3 ns        19.2 ns
BM_deque_deque_copy_backward/1024             46.2 ns        43.2 ns
BM_deque_deque_copy_backward/4000              121 ns         101 ns
BM_deque_deque_copy_backward/4096              179 ns         162 ns
BM_deque_deque_copy_backward/5500              247 ns         216 ns
BM_deque_deque_copy_backward/64000            5362 ns        5429 ns
BM_deque_deque_copy_backward/65536            5474 ns        5551 ns
BM_deque_deque_copy_backward/70000            5856 ns        5942 ns
BM_deque_deque_ranges_copy_backward/0        0.792 ns        1.34 ns
BM_deque_deque_ranges_copy_backward/1         2.04 ns        3.17 ns
BM_deque_deque_ranges_copy_backward/2         2.93 ns        3.17 ns
BM_deque_deque_ranges_copy_backward/64        56.0 ns        4.20 ns
BM_deque_deque_ranges_copy_backward/512        372 ns        19.2 ns
BM_deque_deque_ranges_copy_backward/1024       715 ns        43.2 ns
BM_deque_deque_ranges_copy_backward/4000      2839 ns         101 ns
BM_deque_deque_ranges_copy_backward/4096      2861 ns         163 ns
BM_deque_deque_ranges_copy_backward/5500      3850 ns         216 ns
BM_deque_deque_ranges_copy_backward/64000    42909 ns        5425 ns
BM_deque_deque_ranges_copy_backward/65536    44236 ns        5547 ns
BM_deque_deque_ranges_copy_backward/70000    47484 ns        5939 ns
BM_vector_deque_copy_backward/0              0.597 ns       0.566 ns
BM_vector_deque_copy_backward/1               4.17 ns        2.11 ns
BM_vector_deque_copy_backward/2               3.83 ns        1.98 ns
BM_vector_deque_copy_backward/64              4.99 ns        3.43 ns
BM_vector_deque_copy_backward/512             18.1 ns        13.8 ns
BM_vector_deque_copy_backward/1024            43.6 ns        41.0 ns
BM_vector_deque_copy_backward/4000             160 ns         134 ns
BM_vector_deque_copy_backward/4096             160 ns         138 ns
BM_vector_deque_copy_backward/5500             225 ns         180 ns
BM_vector_deque_copy_backward/64000           5458 ns        5440 ns
BM_vector_deque_copy_backward/65536           5648 ns        5657 ns
BM_vector_deque_copy_backward/70000           6021 ns        6018 ns
BM_vector_deque_ranges_copy_backward/0       0.529 ns       0.538 ns
BM_vector_deque_ranges_copy_backward/1        1.06 ns        2.11 ns
BM_vector_deque_ranges_copy_backward/2        1.35 ns        1.98 ns
BM_vector_deque_ranges_copy_backward/64       25.4 ns        3.43 ns
BM_vector_deque_ranges_copy_backward/512       166 ns        13.8 ns
BM_vector_deque_ranges_copy_backward/1024      286 ns        41.0 ns
BM_vector_deque_ranges_copy_backward/4000     1149 ns         134 ns
BM_vector_deque_ranges_copy_backward/4096     1138 ns         139 ns
BM_vector_deque_ranges_copy_backward/5500     1536 ns         182 ns
BM_vector_deque_ranges_copy_backward/64000   17771 ns        5467 ns
BM_vector_deque_ranges_copy_backward/65536   18343 ns        5658 ns
BM_vector_deque_ranges_copy_backward/70000   19422 ns        6062 ns
BM_deque_vector_move_backward/0              0.271 ns        1.60 ns
BM_deque_vector_move_backward/1               2.91 ns        1.87 ns
BM_deque_vector_move_backward/2               3.51 ns        1.74 ns
BM_deque_vector_move_backward/64              4.49 ns        3.13 ns
BM_deque_vector_move_backward/512             15.8 ns        13.4 ns
BM_deque_vector_move_backward/1024            41.2 ns        40.0 ns
BM_deque_vector_move_backward/4000             147 ns         126 ns
BM_deque_vector_move_backward/4096             145 ns         127 ns
BM_deque_vector_move_backward/5500             207 ns         171 ns
BM_deque_vector_move_backward/64000           5465 ns        5515 ns
BM_deque_vector_move_backward/65536           5435 ns        5441 ns
BM_deque_vector_move_backward/70000           5835 ns        5787 ns
BM_deque_vector_ranges_move_backward/0       0.264 ns        1.58 ns
BM_deque_vector_ranges_move_backward/1        1.17 ns        1.85 ns
BM_deque_vector_ranges_move_backward/2        1.45 ns        1.72 ns
BM_deque_vector_ranges_move_backward/64       23.2 ns        3.12 ns
BM_deque_vector_ranges_move_backward/512       147 ns        13.3 ns
BM_deque_vector_ranges_move_backward/1024      281 ns        39.9 ns
BM_deque_vector_ranges_move_backward/4000     1097 ns         126 ns
BM_deque_vector_ranges_move_backward/4096     1122 ns         127 ns
BM_deque_vector_ranges_move_backward/5500     1514 ns         170 ns
BM_deque_vector_ranges_move_backward/64000   17551 ns        5507 ns
BM_deque_vector_ranges_move_backward/65536   17944 ns        5436 ns
BM_deque_vector_ranges_move_backward/70000   19183 ns        5781 ns
BM_deque_deque_move_backward/0                1.17 ns        1.34 ns
BM_deque_deque_move_backward/1                6.60 ns        3.17 ns
BM_deque_deque_move_backward/2                6.87 ns        3.17 ns
BM_deque_deque_move_backward/64               7.78 ns        4.20 ns
BM_deque_deque_move_backward/512              24.2 ns        19.2 ns
BM_deque_deque_move_backward/1024             46.2 ns        43.2 ns
BM_deque_deque_move_backward/4000              121 ns         101 ns
BM_deque_deque_move_backward/4096              179 ns         163 ns
BM_deque_deque_move_backward/5500              247 ns         217 ns
BM_deque_deque_move_backward/64000            5361 ns        5431 ns
BM_deque_deque_move_backward/65536            5465 ns        5547 ns
BM_deque_deque_move_backward/70000            5845 ns        5939 ns
BM_deque_deque_ranges_move_backward/0        0.791 ns        1.33 ns
BM_deque_deque_ranges_move_backward/1         2.04 ns        3.17 ns
BM_deque_deque_ranges_move_backward/2         2.93 ns        3.17 ns
BM_deque_deque_ranges_move_backward/64        55.7 ns        4.18 ns
BM_deque_deque_ranges_move_backward/512        351 ns        19.2 ns
BM_deque_deque_ranges_move_backward/1024       689 ns        43.2 ns
BM_deque_deque_ranges_move_backward/4000      2685 ns         101 ns
BM_deque_deque_ranges_move_backward/4096      2743 ns         162 ns
BM_deque_deque_ranges_move_backward/5500      3698 ns         215 ns
BM_deque_deque_ranges_move_backward/64000    42808 ns        5426 ns
BM_deque_deque_ranges_move_backward/65536    43858 ns        5551 ns
BM_deque_deque_ranges_move_backward/70000    46853 ns        5947 ns
BM_vector_deque_move_backward/0              0.621 ns       0.532 ns
BM_vector_deque_move_backward/1               4.17 ns        2.11 ns
BM_vector_deque_move_backward/2               3.84 ns        1.98 ns
BM_vector_deque_move_backward/64              4.99 ns        3.43 ns
BM_vector_deque_move_backward/512             18.1 ns        13.8 ns
BM_vector_deque_move_backward/1024            43.6 ns        41.0 ns
BM_vector_deque_move_backward/4000             160 ns         134 ns
BM_vector_deque_move_backward/4096             160 ns         138 ns
BM_vector_deque_move_backward/5500             225 ns         181 ns
BM_vector_deque_move_backward/64000           5457 ns        5436 ns
BM_vector_deque_move_backward/65536           5646 ns        5658 ns
BM_vector_deque_move_backward/70000           6020 ns        6022 ns
BM_vector_deque_ranges_move_backward/0       0.536 ns       0.528 ns
BM_vector_deque_ranges_move_backward/1        1.06 ns        2.11 ns
BM_vector_deque_ranges_move_backward/2        1.33 ns        1.98 ns
BM_vector_deque_ranges_move_backward/64       28.9 ns        3.43 ns
BM_vector_deque_ranges_move_backward/512       160 ns        13.8 ns
BM_vector_deque_ranges_move_backward/1024      286 ns        41.0 ns
BM_vector_deque_ranges_move_backward/4000     1197 ns         134 ns
BM_vector_deque_ranges_move_backward/4096     1138 ns         138 ns
BM_vector_deque_ranges_move_backward/5500     1552 ns         181 ns
BM_vector_deque_ranges_move_backward/64000   17834 ns        5436 ns
BM_vector_deque_ranges_move_backward/65536   18351 ns        5660 ns
BM_vector_deque_ranges_move_backward/70000   19473 ns        6022 ns

libcxx/benchmarks/deque_iterator.bench.cpp

2

I've changed the implementation of copy and move to use the segment iterators and that fixed the performance issues, so I didn't test with _LIBCPP_ALWAYS_INLINE.

libcxx/include/__algorithm/copy.h

117

I'd like to investigate that when adding a non-random-access iterator to the segmented iterators, since then it will actually matter. I don't know yet whether local iterators should always be random-access or copying to output segmented iterators should be constrained on the local iterator being random-access.

[philnik]

Fix diff

[philnik]

• Rebased
• Generate files

[philnik]

Fix diff

[ldionne]

LGTM but let's wait for the CI to be back online for a green run and then submit.

libcxx/docs/ReleaseNotes.rst

77–78

libcxx/include/__algorithm/copy_backward.h

88

libcxx/include/__algorithm/move_backward.h

87

[huixie90]

Thanks for the update. LGTM!

[philnik]

• Try to fix CI

[philnik]

• Rebased

[mstorsjo]

If this change builds on top of D130695, then I would request to hold off of proceeding with and landing this - I have bisected downstream breakage down to D130695.

[EricWF]

libcxx/benchmarks/deque_iterator.bench.cpp

2

Have you verified the assembly for these benchmarks?

125

Can you meaningfully do this more than once on the same container?

139

Can you meaningfully do this more than once on the same container?

[philnik]

libcxx/benchmarks/deque_iterator.bench.cpp

2

No, but why should I? The assembly is obviously different, since the benchmarks show differences. The differences aren't very significant though, i.e. a pessimization for the 0-case, but an optimization for small N for some algorithms and an optimization across the board for others.

125

When the types are trivial they are just copied, so it should be fine.

[philnik]

• Try to fix CI

[philnik]

Fix C++03

[ldionne]

libcxx/include/__iterator/segmented_iterator.h

54

template <class _Iterator, class = void>
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>
constexpr bool __has_specialization_v = false;

template <class _Tp>
constexpr bool __has_specialization_v<_Tp, sizeof(_Tp)> = true;

template <class _Iterator>
using __is_segmented_iterator = bool_constant<__has_specialization_v<segmented_iterator_traits<_Iterator> >;

That way, we avoid forming __segmented_iterator_traits specializations for types that are not segmented iterators. That's more in-line with what we do for other traits classes, e.g. char_traits, allocator_traits, etc.

libcxx/include/deque

401

[philnik]

Address comments

[philnik]

Rebased

[philnik]

Try to fix CI

[philnik]

Fix modulemap

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[ldionne]

libcxx/include/__iterator/segmented_iterator.h

54

I don't think you addressed this feedback, have you?

[philnik]

Address comments

[philnik]

Try to fix CI

[ldionne]

Thanks!

libcxx/benchmarks/CMakeLists.txt

set(BENCHMARK_TESTS
     algorithms/make_heap_then_sort_heap.bench.cpp
     algorithms/min_max_element.bench.cpp
     algorithms/pop_heap.bench.cpp
     algorithms/push_heap.bench.cpp
     algorithms/ranges_make_heap.bench.cpp
     algorithms/ranges_make_heap_then_sort_heap.bench.cpp
     algorithms/ranges_pop_heap.bench.cpp
     algorithms/ranges_push_heap.bench.cpp
     algorithms/ranges_sort.bench.cpp
     algorithms/ranges_sort_heap.bench.cpp
     algorithms/ranges_stable_sort.bench.cpp
     algorithms/sort.bench.cpp
     algorithms/sort_heap.bench.cpp
     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
     format.bench.cpp
     formatted_size.bench.cpp
     formatter_float.bench.cpp
     formatter_int.bench.cpp
     function.bench.cpp

libcxx/benchmarks/deque_iterator.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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();

libcxx/docs/ReleaseNotes.rst

 - P1035R7 - Input Range Adaptors
 - P2325R3 - Views should not be required to be default constructible
 
 Improvements and New Features
 -----------------------------
 - Declarations of ``std::c8rtomb()`` and ``std::mbrtoc8()`` from P0482R6 are
   now provided when implementations in the global namespace are provided by
   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
 -------------------------
 - ``unary_function`` and ``binary_function`` are no longer provided in C++17 and newer Standard modes.
   They can be re-enabled with ``_LIBCPP_ENABLE_CXX17_REMOVED_UNARY_BINARY_FUNCTION``.
 
 - Several incidental transitive includes have been removed from libc++. Those
   includes are removed based on the language version used. Incidental transitive

libcxx/include/CMakeLists.txt

set(files
   __iterator/ostream_iterator.h
   __iterator/ostreambuf_iterator.h
   __iterator/permutable.h
   __iterator/prev.h
   __iterator/projected.h
   __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
   __iterator/wrap_iter.h
   __locale
   __mbstate_t.h
   __memory/addressof.h
   __memory/align.h

libcxx/include/__algorithm/copy.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_COPY_H
 #define _LIBCPP___ALGORITHM_COPY_H
 
 #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>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  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>
   operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     while (__first != __last) {
       *__result = *__first;
       ++__first;
       ++__result;
     }
 
     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 {
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out,
             __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
   operator()(_In* __first, _In* __last, _Out* __result) const {
     return std::__copy_trivial_impl(__first, __last, __result);
   }
 };
 
 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

libcxx/include/__algorithm/copy_backward.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_COPY_BACKWARD_H
 #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H
 
 #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>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  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>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
   operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     auto __last_iter          = _IterOps<_AlgPolicy>::next(__first, __last);
     auto __original_last_iter = __last_iter;
 
     while (__first != __last_iter) {
       *--__result = *--__last_iter;
     }
 
     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 {
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out,
             __enable_if_t<__can_lower_copy_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
   operator()(_In* __first, _In* __last, _Out* __result) const {
     return std::__copy_backward_trivial_impl(__first, __last, __result);
   }
 };
 
 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));
 }
 
 template <class _BidirectionalIterator1, class _BidirectionalIterator2>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 _BidirectionalIterator2
 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
               _BidirectionalIterator2 __result)
 {
   static_assert(std::is_copy_constructible<_BidirectionalIterator1>::value &&
                 std::is_copy_constructible<_BidirectionalIterator1>::value, "Iterators must be copy constructible.");
 
   return std::__copy_backward<_ClassicAlgPolicy>(
       std::move(__first), std::move(__last), std::move(__result)).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
+_LIBCPP_POP_MACROS
+
 #endif // _LIBCPP___ALGORITHM_COPY_BACKWARD_H

libcxx/include/__algorithm/move.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_MOVE_H
 #define _LIBCPP___ALGORITHM_MOVE_H
 
 #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>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  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>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
   operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     while (__first != __last) {
       *__result = _IterOps<_AlgPolicy>::__iter_move(__first);
       ++__first;
       ++__result;
     }
     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 {
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out,
             __enable_if_t<__can_lower_move_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
   operator()(_In* __first, _In* __last, _Out* __result) const {
     return std::__copy_trivial_impl(__first, __last, __result);
   }
 };
 
 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

libcxx/include/__algorithm/move_backward.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H
 #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H
 
 #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>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  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>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
   operator()(_InIter __first, _Sent __last, _OutIter __result) const {
     auto __last_iter          = _IterOps<_AlgPolicy>::next(__first, __last);
     auto __original_last_iter = __last_iter;
 
     while (__first != __last_iter) {
       *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last_iter);
     }
 
     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 {
   // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer.
   template <class _In, class _Out,
             __enable_if_t<__can_lower_move_assignment_to_memmove<_In, _Out>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*>
   operator()(_In* __first, _In* __last, _Out* __result) const {
     return std::__copy_backward_trivial_impl(__first, __last, __result);
   }
 };
 
 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.");
 
   return std::__dispatch_copy_or_move<_AlgPolicy, __move_backward_loop<_AlgPolicy>, __move_backward_trivial>(
       std::move(__first), std::move(__last), std::move(__result));
 }
 
 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

libcxx/include/__iterator/reverse_iterator.h

 #include <__iterator/incrementable_traits.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator.h>
 #include <__iterator/iterator_traits.h>
 #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>
 #include <__ranges/subrange.h>
 #include <__type_traits/conditional.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_assignable.h>
 #include <__type_traits/is_convertible.h>

libcxx/include/__iterator/segmented_iterator.h

+//===----------------------------------------------------------------------===//
+//
+// 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

libcxx/include/deque

 #include <__algorithm/unwrap_iter.h>
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__config>
 #include <__format/enable_insertable.h>
 #include <__iterator/iterator_traits.h>
 #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>
 #include <__memory/unique_ptr.h>
 #include <__memory_resource/polymorphic_allocator.h>
 #include <__split_buffer>
 #include <__type_traits/is_allocator.h>
 #include <__utility/forward.h>

 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
 _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;
 };
 
 template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,
           class _DiffType, _DiffType _BS =
 #ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE

 private:
     _LIBCPP_HIDE_FROM_ABI explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
         : __m_iter_(__m), __ptr_(__p) {}
 
     template <class _Tp, class _Ap> friend class _LIBCPP_TEMPLATE_VIS deque;
     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;
-        }
-        __r = _VSTD::move_backward(__lb, __le, __r);
-        __n -= __bs;
-        __l -= __bs - 1;
+  static _LIBCPP_HIDE_FROM_ABI _Iterator __compose(__segment_iterator __segment, __local_iterator __local) {
+        if (__local == __end(__segment)) {
+            ++__segment;
+            return _Iterator(__segment, *__segment);
         }
-    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
 {
 public:
     // types:
 
   using value_type = _Tp;

libcxx/include/module.modulemap.in

module __iterator {
         export iosfwd
       }
       module permutable            { private header "__iterator/permutable.h" }
       module prev                  { private header "__iterator/prev.h" }
       module projected             { private header "__iterator/projected.h" }
       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"
         export functional.__functional.ranges_operations
       }
       module unreachable_sentinel  { private header "__iterator/unreachable_sentinel.h" }
       module wrap_iter             { private header "__iterator/wrap_iter.h" }
     }

libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_iterator.compile.pass.cpp

 
 // template<class I>
 // concept __nothrow_forward_iterator;
 
 #include <memory>
 
 #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;
 }
 constexpr bool forward_subsumes_input(std::ranges::__nothrow_input_iterator auto);
 
 static_assert(forward_subsumes_input("foo"));

libcxx/test/libcxx/algorithms/specialized.algorithms/special.mem.concepts/nothrow_forward_range.compile.pass.cpp

 // template<class R>
 // concept __nothrow_forward_range;
 
 #include <memory>
 
 #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>>);
 static_assert(!std::ranges::__nothrow_forward_range<test_range<ForwardProxyIterator>>);
 
 constexpr bool forward_subsumes_input(std::ranges::__nothrow_forward_range auto&&) {
   return true;
 }
 constexpr bool forward_subsumes_input(std::ranges::__nothrow_input_range auto&&);
 
 static_assert(forward_subsumes_input("foo"));

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__iterator/ostream_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/ostream_iterator.h'}}
 #include <__iterator/ostreambuf_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/ostreambuf_iterator.h'}}
 #include <__iterator/permutable.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/permutable.h'}}
 #include <__iterator/prev.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/prev.h'}}
 #include <__iterator/projected.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/projected.h'}}
 #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'}}
 #include <__iterator/wrap_iter.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/wrap_iter.h'}}
 #include <__locale> // expected-error@*:* {{use of private header from outside its module: '__locale'}}
 #include <__mbstate_t.h> // expected-error@*:* {{use of private header from outside its module: '__mbstate_t.h'}}
 #include <__memory/addressof.h> // expected-error@*:* {{use of private header from outside its module: '__memory/addressof.h'}}
 #include <__memory/align.h> // expected-error@*:* {{use of private header from outside its module: '__memory/align.h'}}

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp

 //   constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result);
 // template<input_range R, weakly_incrementable O>
 //   requires indirectly_copyable<iterator_t<R>, O>
 //   constexpr ranges::copy_result<borrowed_iterator_t<R>, O> ranges::copy(R&& r, O result);
 
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 #include "type_algorithms.h"
 
 template <class In, class Out = In, class Sent = sentinel_wrapper<In>>
 concept HasCopyIt = requires(In in, Sent sent, Out out) { std::ranges::copy(in, sent, out); };
 

 static_assert(!HasCopyR<InputRangeNotInputOrOutputIterator, int*>);
 static_assert(!HasCopyR<WeaklyIncrementableNotMovable, int*>);
 static_assert(!HasCopyR<UncheckedRange<NotIndirectlyCopyable*>, int*>);
 static_assert(!HasCopyR<InputRangeNotSentinelSemiregular, int*>);
 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()));
       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()));
       assert(in == out);
       assert(base(ret.in) == in.data() + in.size());
       assert(base(ret.out) == out.data() + out.size());
     }
   }
 
   { // check that an empty range works
     {
       std::array<int, 0> in;
       std::array<int, 0> out;
       auto ret = std::ranges::copy(In(in.data()), Sent(In(in.data() + in.size())), Out(out.data()));
       assert(base(ret.in) == in.data());
       assert(base(ret.out) == out.data());
     }
     {
       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>() {
     test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();
     test_iterators<ProxyIterator<cpp20_input_iterator<int*>>,
                    ProxyIterator<Out>,
                    sentinel_wrapper<ProxyIterator<cpp20_input_iterator<int*>>>>();
 
meta::for_each(meta::forward_iterator_list<int*>{}, []<class Out>() {
     std::array<int, 4> out;
     std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret =
         std::ranges::copy(std::array{1, 2, 3, 4}, out.data());
     assert(ret.out == out.data() + 4);
     assert((out == std::array{1, 2, 3, 4}));
   }
 
   { // 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);
     assert(ret.out == out.data() + 4);
     assert(in == out);
   }
 
   { // 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);
         copied = true;
         return *this;
       }
     };
     {
-      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());
       assert(std::all_of(out.begin(), out.end(), [](const auto& e) { return e.copied; }));
     }
   }
 
   { // 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)
           next->canCopy = true;
         return *this;
       }
     };
     {
-      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);
       assert(out[1].canCopy);
       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);
       assert(out[1].canCopy);
       assert(out[2].canCopy);
     }
   }
 

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp

 // template<bidirectional_range R, bidirectional_iterator I>
 //   requires indirectly_copyable<iterator_t<R>, I>
 //   constexpr ranges::copy_backward_result<borrowed_iterator_t<R>, I>
 //     ranges::copy_backward(R&& r, I result);
 
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
 template <class In, class Out = In, class Sent = sentinel_wrapper<In>>
 concept HasCopyBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::copy_backward(in, sent, out); };
 
 static_assert(HasCopyBackwardIt<int*>);
constexpr void test_iterators() {
       auto range = std::ranges::subrange(In(in.data()), Sent(In(in.data() + in.size())));
       auto ret = std::ranges::copy_backward(range, Out(out.data()));
       assert(base(ret.in) == in.data() + in.size());
       assert(base(ret.out) == out.data());
     }
   }
 }
 
-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;
     std::same_as<std::ranges::in_out_result<std::ranges::dangling, int*>> auto ret =
       std::ranges::copy_backward(std::array {1, 2, 3, 4}, out.data() + out.size());
     assert(ret.out == out.data());
     assert((out == std::array{1, 2, 3, 4}));
   }

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp

 // template<input_range R, weakly_incrementable O>
 //   requires indirectly_movable<iterator_t<R>, O>
 //   constexpr ranges::move_result<borrowed_iterator_t<R>, O>
 //     ranges::move(R&& r, O result);
 
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "MoveOnly.h"
 #include "test_iterators.h"
 
 template <class In, class Out = In, class Sent = sentinel_wrapper<In>>
 concept HasMoveIt = requires(In in, Sent sent, Out out) { std::ranges::move(in, sent, out); };
 
constexpr void test(std::array<int, N> in) {
     std::same_as<std::ranges::in_out_result<In, Out>> decltype(auto) ret =
         std::ranges::move(range, Out(out.data()));
     assert(in == out);
     assert(base(ret.in) == in.data() + in.size());
     assert(base(ret.out) == out.data() + out.size());
   }
 }
 
+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
   test<In, Out, Sent, 4>({1, 2, 3, 4});
   // check that an empty range works
   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 {
   using value_type = int;
   using difference_type = int;
   explicit IteratorWithMoveIter() = default;
   int* ptr;
   constexpr IteratorWithMoveIter(int* ptr_) : ptr(ptr_) {}
 
   constexpr int& operator*() const; // iterator with iter_move should not be dereferenced
 
   constexpr IteratorWithMoveIter& operator++() { ++ptr; return *this; }
   constexpr IteratorWithMoveIter operator++(int) { auto ret = *this; ++*this; return ret; }
 
   friend constexpr int iter_move(const IteratorWithMoveIter&) { return 42; }
 
   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
     {
       MoveOnly a[] = {1, 2, 3};
       MoveOnly b[3];
       std::ranges::move(a, std::begin(b));
       assert(b[0].get() == 1);
       assert(b[1].get() == 2);

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp

 // template<bidirectional_range R, bidirectional_iterator I>
 //   requires indirectly_movable<iterator_t<R>, I>
 //   constexpr ranges::move_backward_result<borrowed_iterator_t<R>, I>
 //     ranges::move_backward(R&& r, I result);
 
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
+#include <vector>
 
 #include "almost_satisfies_types.h"
 #include "MoveOnly.h"
 #include "test_iterators.h"
 
 template <class In, class Out = In, class Sent = sentinel_wrapper<In>>
 concept HasMoveBackwardIt = requires(In in, Sent sent, Out out) { std::ranges::move_backward(in, sent, out); };
 

 template <class In, class Out, class Sent = In>
 constexpr void test_iterators() {
   // simple test
   test<In, Out, Sent, 4>({1, 2, 3, 4});
   // check that an empty range works
   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 {
   using value_type = int;
   using difference_type = int;
   explicit IteratorWithMoveIter() = default;
   int* ptr;
   constexpr IteratorWithMoveIter(int* ptr_) : ptr(ptr_) {}
 
   constexpr int& operator*() const; // iterator with iter_move should not be dereferenced
 
   constexpr IteratorWithMoveIter& operator++() { ++ptr; return *this; }
   constexpr IteratorWithMoveIter operator++(int) { auto ret = *this; ++*this; return ret; }
 
   constexpr IteratorWithMoveIter& operator--() { --ptr; return *this; }
   constexpr IteratorWithMoveIter operator--(int) { auto ret = *this; --*this; return ret; }
 
   friend constexpr int iter_move(const IteratorWithMoveIter&) { return 42; }
 
   constexpr bool operator==(const IteratorWithMoveIter& other) const = default;
 };
 
 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
     {
       MoveOnly a[] = {1, 2, 3};
       MoveOnly b[3];
       std::ranges::move_backward(a, std::end(b));
       assert(b[0].get() == 1);
       assert(b[1].get() == 2);

libcxx/test/support/test_iterators.h

 };
 template <class Base>
 ProxyIterator(Base) -> ProxyIterator<Base>;
 
 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_;
 
   ProxySentinel() = default;
   constexpr ProxySentinel(BaseSent base) : base_{std::move(base)} {}
 
   template <class Base>