[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

33

sentinel is always copyable.
this applies for other places

74

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

86

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

33

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

86

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

33

sounds good to me

86

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

73

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

33

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

86

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 ↗

(On Diff #460406)

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

1 ↗

(On Diff #460406)

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

39

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.

81

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.

83

93–105

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

78

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

1 ↗

(On Diff #460406)

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

74

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

50–51 ↗

(On Diff #461835)

libcxx/include/__algorithm/copy_backward.h

73

libcxx/include/__algorithm/move_backward.h

82

[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

1 ↗

(On Diff #460406)

Have you verified the assembly for these benchmarks?

124 ↗

(On Diff #464550)

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

138 ↗

(On Diff #464550)

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

[philnik]

libcxx/benchmarks/deque_iterator.bench.cpp

1 ↗

(On Diff #460406)

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.

124 ↗

(On Diff #464550)

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

407

[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/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/allocate_at_least.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/unwrap_iter.h>
 #include <__algorithm/unwrap_range.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
+#include <__iterator/segmented_iterator.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <cstring>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // copy
 
+template <class _InIter, class _Sent, class _OutIter,
+          __enable_if_t<!(is_copy_constructible<_InIter>::value
+                       && is_copy_constructible<_Sent>::value
+                       && is_copy_constructible<_OutIter>::value), int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
+pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result);
+
+template <class _InIter, class _Sent, class _OutIter,
+          __enable_if_t<is_copy_constructible<_InIter>::value
+                     && is_copy_constructible<_Sent>::value
+                     && is_copy_constructible<_OutIter>::value, int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
+pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result);
+
 template <class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<_InIter, _OutIter> __copy_impl(_InIter __first, _Sent __last, _OutIter __result) {
   while (__first != __last) {
     *__result = *__first;
     ++__first;
     ++__result;
   }
   return pair<_InIter, _OutIter>(std::move(__first), std::move(__result));
 }
 
+template <class _InIter,
+          class _OutIter,
+          __enable_if_t<__is_cpp17_random_access_iterator<_InIter>::value &&
+                            !__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value &&
+                            __segmented_iterator_traits<_OutIter>::__is_segmented_iterator::value,
+                        int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+__copy_impl(_InIter __first, _InIter __last, _OutIter __result) {
+  if (__first == __last)
+    return std::make_pair(__last, __result);
+
+  while (true) {
+    auto __segment = __segmented_iterator_traits<_OutIter>::__get_range_to_segment_end(__result);
+    auto __segment_size = __segment.__end_ - __segment.__begin_;
+    auto __range_size = __last - __first;
+
+    if (__range_size < __segment_size) {
+      auto __iters = std::__copy(__first, __last, __segment.__begin_);
+      __result += __range_size;
+      return std::make_pair(__iters.first, __result);
+    }
+
+    std::__copy(__first, __first + __segment_size, __segment.__begin_);
+    __first += __segment_size;
+    __result += __segment_size;
+  }
+}
+
+template <class _InIter,
+          class _OutIter,
+          __enable_if_t<__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value, int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+__copy_impl(_InIter __first, _InIter __last, _OutIter __result) {
+  for (auto&& __segment : __segmented_iterator_traits<_InIter>::__get_forward_range(__first, __last)) {
+    auto __iters = std::__copy(__segment.__begin_, __segment.__end_, std::move(__result));
+    __result     = std::move(__iters.second);
+  }
+  return std::make_pair(__last, std::move(__result));
+}
+
 template <class _InValueT,
           class _OutValueT,
           class = __enable_if_t<is_same<typename remove_const<_InValueT>::type, _OutValueT>::value
                              && is_trivially_copy_assignable<_OutValueT>::value> >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<_InValueT*, _OutValueT*> __copy_impl(_InValueT* __first, _InValueT* __last, _OutValueT* __result) {
   if (__libcpp_is_constant_evaluated()
 // TODO: Remove this once GCC supports __builtin_memmove during constant evaluation
__copy_impl(_InIter __first, _InIter __last, _OutIter __result) {
   auto __result_first = __result_base - (__first_base - __last_base);
   std::__copy_impl(__last_base, __first_base, __result_first);
   return std::make_pair(__last, _OutIter(std::__rewrap_iter(__result.base(), __result_first)));
 }
 
 template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<!(is_copy_constructible<_InIter>::value
                        && is_copy_constructible<_Sent>::value
-                       && is_copy_constructible<_OutIter>::value), int> = 0 >
+                       && is_copy_constructible<_OutIter>::value), int> >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
   return std::__copy_impl(std::move(__first), std::move(__last), std::move(__result));
 }
 
 template <class _InIter, class _Sent, class _OutIter,
           __enable_if_t<is_copy_constructible<_InIter>::value
                      && is_copy_constructible<_Sent>::value
-                     && is_copy_constructible<_OutIter>::value, int> = 0>
+                     && is_copy_constructible<_OutIter>::value, int> >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) {
   auto __range = std::__unwrap_range(__first, __last);
   auto __ret   = std::__copy_impl(std::move(__range.first), std::move(__range.second), std::__unwrap_iter(__result));
   return std::make_pair(
       std::__rewrap_range<_Sent>(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 

libcxx/include/__algorithm/copy_backward.h

 
 #include <__algorithm/copy.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/ranges_copy.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/prev.h>
 #include <__iterator/reverse_iterator.h>
+#include <__iterator/segmented_iterator.h>
 #include <__ranges/subrange.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <cstring>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _InputIterator, class _OutputIterator,
-          __enable_if_t<is_same<_AlgPolicy, _ClassicAlgPolicy>::value, int> = 0>
+template <class _AlgPolicy,
+          class _InputIterator,
+          class _OutputIterator,
+          __enable_if_t<is_same<_AlgPolicy, _ClassicAlgPolicy>::value &&
+                            !__segmented_iterator_traits<_InputIterator>::__is_segmented_iterator::value &&
+                            !__segmented_iterator_traits<_OutputIterator>::__is_segmented_iterator::value,
+                        int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InputIterator, _OutputIterator>
 __copy_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
   auto __ret = std::__copy(
       __unconstrained_reverse_iterator<_InputIterator>(__last),
       __unconstrained_reverse_iterator<_InputIterator>(__first),
       __unconstrained_reverse_iterator<_OutputIterator>(__result));
   return pair<_InputIterator, _OutputIterator>(__ret.first.base(), __ret.second.base());
 }
 
 #if _LIBCPP_STD_VER > 17
-template <class _AlgPolicy, class _Iter1, class _Sent1, class _Iter2,
+template <class _AlgPolicy,
+          class _Iter1,
+          class _Sent1,
+          class _Iter2,
           __enable_if_t<is_same<_AlgPolicy, _RangeAlgPolicy>::value, int> = 0>
 _LIBCPP_HIDE_FROM_ABI constexpr pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) {
   auto __last_iter     = _IterOps<_AlgPolicy>::next(__first, std::move(__last));
   auto __reverse_range = std::__reverse_range(std::ranges::subrange(std::move(__first), __last_iter));
   auto __ret           = ranges::copy(std::move(__reverse_range), std::make_reverse_iterator(__result));
   return std::make_pair(__last_iter, __ret.out.base());
 }
 #endif // _LIBCPP_STD_VER > 17
 
+template <class _AlgPolicy,
+          class _InIter,
+          class _OutIter,
+          __enable_if_t<__is_cpp17_random_access_iterator<_InIter>::value &&
+                            !__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value &&
+                            __segmented_iterator_traits<_OutIter>::__is_segmented_iterator::value,
+                        int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+__copy_backward(_InIter __first, _InIter __last, _OutIter __result) {
+  if (__first == __last)
+    return std::make_pair(__last, __result);
+
+  auto __end = __last;
+  while (true) {
+    auto __segment      = __segmented_iterator_traits<_OutIter>::__get_range_to_segment_begin(__result);
+    auto __segment_size = __segment.__end_ - __segment.__begin_;
+    auto __range_size   = __last - __first;
+
+    if (__range_size < __segment_size) {
+      std::__copy_backward<_AlgPolicy>(__first, __last, __segment.__end_);
+      __result -= __range_size;
+      return std::make_pair(__end, __result);
+    }
+
+    std::__copy_backward<_AlgPolicy>(__last - __segment_size, __last, __segment.__end_);
+    __last -= __segment_size;
+    __result -= __segment_size;
+  }
+}
+
+template <class _AlgPolicy,
+          class _InIter,
+          class _OutIter,
+          __enable_if_t<__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+__copy_backward(_InIter __first, _InIter __last, _OutIter __result) {
+  for (auto&& __segment : __segmented_iterator_traits<_InIter>::__get_backward_range(__first, __last)) {
+    auto __iters = std::__copy_backward<_AlgPolicy>(__segment.__begin_, __segment.__end_, std::move(__result));
+    __result     = std::move(__iters.second);
+  }
+  return std::make_pair(__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) {
   return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result).second;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #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/iterator_operations.h>
 #include <__algorithm/unwrap_iter.h>
+#include <__algorithm/unwrap_range.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
+#include <__iterator/segmented_iterator.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <cstring>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // move
 
 template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
+__enable_if_t<is_copy_constructible<_InIter>::value
+           && is_copy_constructible<_Sent>::value
+           && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
+__move(_InIter __first, _Sent __last, _OutIter __result);
+
+template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
+__enable_if_t<!is_copy_constructible<_InIter>::value
+           || !is_copy_constructible<_Sent>::value
+           || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
+__move(_InIter __first, _Sent __last, _OutIter __result);
+
+template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX17
 pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) {
   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_cpp17_random_access_iterator<_InIter>::value &&
+                            !__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value &&
+                            __segmented_iterator_traits<_OutIter>::__is_segmented_iterator::value,
+                        int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+__move_impl(_InIter __first, _InIter __last, _OutIter __result) {
+  if (__first == __last)
+    return std::make_pair(__last, __result);
+
+  while (true) {
+    auto __segment = __segmented_iterator_traits<_OutIter>::__get_range_to_segment_end(__result);
+    auto __segment_size = __segment.__end_ - __segment.__begin_;
+    auto __range_size = __last - __first;
+
+    if (__range_size < __segment_size) {
+      auto __iters = std::__move(__first, __last, __segment.__begin_);
+      __result += __range_size;
+      return std::make_pair(__iters.first, __result);
+    }
+
+    std::__move(__first, __first + __segment_size, __segment.__begin_);
+    __first += __segment_size;
+    __result += __segment_size;
+  }
+}
+
+template <class _InIter,
+          class _OutIter,
+          __enable_if_t<__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value, int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_InIter, _OutIter>
+__move_impl(_InIter __first, _InIter __last, _OutIter __result) {
+  for (auto&& __segment : __segmented_iterator_traits<_InIter>::__get_forward_range(__first, __last)) {
+    auto __iters = std::__move(__segment.__begin_, __segment.__end_, std::move(__result));
+    __result     = std::move(__iters.second);
+  }
+  return std::make_pair(__last, std::move(__result));
+}
+
 template <class _AlgPolicy,
           class _InType,
           class _OutType,
           class = __enable_if_t<is_same<typename remove_const<_InType>::type, _OutType>::value
                              && is_trivially_move_assignable<_OutType>::value> >
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<_InType*, _OutType*> __move_impl(_InType* __first, _InType* __last, _OutType* __result) {
   if (__libcpp_is_constant_evaluated()

 }
 
 template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 __enable_if_t<is_copy_constructible<_InIter>::value
            && is_copy_constructible<_Sent>::value
            && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
 __move(_InIter __first, _Sent __last, _OutIter __result) {
+  auto __range = std::__unwrap_range(__first, __last);
   auto __ret = std::__move_impl<_AlgPolicy>(
-      std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result));
-  return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
+    std::move(__range.first), std::move(__range.second), std::__unwrap_iter(__result));
+  return std::make_pair(std::__rewrap_range<_Sent>(__first, __ret.first), std::__rewrap_iter(__result, __ret.second));
 }
 
 template <class _AlgPolicy, class _InIter, class _Sent, class _OutIter>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 __enable_if_t<!is_copy_constructible<_InIter>::value
            || !is_copy_constructible<_Sent>::value
            || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> >
 __move(_InIter __first, _Sent __last, _OutIter __result) {

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/iterator_operations.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__config>
+#include <__iterator/segmented_iterator.h>
 #include <__utility/move.h>
 #include <cstring>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
__move_backward_impl(_Tp* __first, _Tp* __last, _Up* __result)
     if (__n > 0)
     {
         __result -= __n;
         _VSTD::memmove(__result, __first, __n * sizeof(_Up));
     }
     return __result;
 }
 
-template <class _AlgPolicy, class _BidirectionalIterator1, class _BidirectionalIterator2>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
-_BidirectionalIterator2
-__move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
-                _BidirectionalIterator2 __result)
-{
+template <class _AlgPolicy,
+          class _BidirectionalIterator1,
+          class _BidirectionalIterator2,
+          __enable_if_t<!__segmented_iterator_traits<_BidirectionalIterator1>::__is_segmented_iterator::value &&
+                            !__segmented_iterator_traits<_BidirectionalIterator2>::__is_segmented_iterator::value,
+                        int> = 0>
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _BidirectionalIterator2
+__move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) {
     if (__libcpp_is_constant_evaluated()) {
         return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result);
     } else {
         return _VSTD::__rewrap_iter(__result,
             _VSTD::__move_backward_impl<_AlgPolicy>(_VSTD::__unwrap_iter(__first),
                                                     _VSTD::__unwrap_iter(__last),
                                                     _VSTD::__unwrap_iter(__result)));
     }
 }
 
+template <class _AlgPolicy,
+          class _InIter,
+          class _OutIter,
+          __enable_if_t<__is_cpp17_random_access_iterator<_InIter>::value &&
+                            !__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value &&
+                            __segmented_iterator_traits<_OutIter>::__is_segmented_iterator::value,
+                        int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _OutIter
+__move_backward(_InIter __first, _InIter __last, _OutIter __result) {
+  if (__first == __last)
+    return __result;
+
+  auto __end = __last;
+  while (true) {
+    auto __segment      = __segmented_iterator_traits<_OutIter>::__get_range_to_segment_begin(__result);
+    auto __segment_size = __segment.__end_ - __segment.__begin_;
+    auto __range_size   = __last - __first;
+
+    if (__range_size < __segment_size) {
+      std::__move_backward<_AlgPolicy>(__first, __last, __segment.__end_);
+      __result -= __range_size;
+      return __result;
+    }
+
+    std::__move_backward<_AlgPolicy>(__last - __segment_size, __last, __segment.__end_);
+    __last -= __segment_size;
+    __result -= __segment_size;
+  }
+}
+
+template <class _AlgPolicy,
+          class _InIter,
+          class _OutIter,
+          __enable_if_t<__segmented_iterator_traits<_InIter>::__is_segmented_iterator::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _OutIter
+__move_backward(_InIter __first, _InIter __last, _OutIter __result) {
+  for (auto&& __segment : __segmented_iterator_traits<_InIter>::__get_backward_range(__first, __last)) {
+    __result = std::__move_backward<_AlgPolicy>(__segment.__begin_, __segment.__end_, std::move(__result));
+  }
+  return 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));
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MOVE_BACKWARD_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 which are made up of multiple other iterators.
+// For example, std::deque uses segments to store a few elements in a contiguous block and then have a new block
+// after that. To allow algorithms to optimize on this an iterator can specialize __segmented_iterator_traits.
+// If __segmented_iterator_traits::__is_segmented_iterator::value is true, the following functions have to be
+// implemented:
+// - `static <undefined> __get_forward_range(_Iterator __first, _Iterator __last);`
+//   where <undefined> is a range which contains the segments to iterate over. The segments are iterated front to back.
+// - `static <undefined> __get_backward_range(_Iterator __first, _Iterator __last);`
+//   where <undefined> is a range which contains the segments to iterate over. The segments are iterated back to front.
+// - `static <undefined> __get_range_to_segment_begin(_Iterator __end)`
+//   where <undefined> is a struct where [__begin_, __end_) is a range from begin of the segment to
+//   the passed-in iterator
+// - `static <undefined> __get_range_to_segment_end(_Iterator __begin)`
+//   where <undefined> is a struct where [__begin_, __end_) is a range from the passed-in iterator to
+//   the end of the segment
+
+#include <__config>
+#include <__type_traits/integral_constant.h>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Iterator>
+struct __segmented_iterator_traits {
+  using __is_segmented_iterator = false_type;
+};
+
+_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 <__split_buffer>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <__utility/swap.h>
 #include <limits>
 #include <stdexcept>
 #include <type_traits>
 #include <version>

 
 template <class _Tp, class _Allocator> class __deque_base;
 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
public:
     typedef _Pointer  pointer;
     typedef _DiffType difference_type;
 private:
     __map_iterator __m_iter_;
     pointer        __ptr_;
 
     static const difference_type __block_size;
 public:
-    typedef _ValueType                  value_type;
-    typedef random_access_iterator_tag  iterator_category;
-    typedef _Reference                  reference;
+  using value_type        = _ValueType;
+  using iterator_category = random_access_iterator_tag;
+  using reference         = _Reference;
 
     _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
      : __m_iter_(nullptr), __ptr_(nullptr)
 #endif
      {}
 
     template <class _Pp, class _Rp, class _MP>
private:
     _LIBCPP_INLINE_VISIBILITY explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT
         : __m_iter_(__m), __ptr_(__p) {}
 
     template <class _Tp, class _Ap> friend class __deque_base;
     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 class __deque_range;
+
+    template <class>
+    friend class __deque_backward_range;
+
+    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;
+template <class _Pointer>
+struct __deque_block_range {
+  explicit __deque_block_range(_Pointer __b, _Pointer __e) _NOEXCEPT : __begin_(__b), __end_(__e) {}
+  const _Pointer __begin_;
+  const _Pointer __end_;
+};
 
-// copy
+template <class _Iterator>
+struct __deque_range {
+  using iterator = _Iterator;
+  using __deque_block_range = std::__deque_block_range<typename _Iterator::pointer>;
 
-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;
-}
+  iterator __pos_;
+  const iterator __end_;
 
-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;
-}
+  __deque_range(iterator __pos, iterator __e) _NOEXCEPT
+    : __pos_(__pos), __end_(__e) {}
 
-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;
+  explicit operator bool() const _NOEXCEPT {
+    return __pos_ != __end_;
   }
 
-// copy_backward
+  __deque_range begin() const {
+    return *this;
+  }
 
-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;
+  __deque_range end() const {
+    return __deque_range(__end_, __end_);
+
+  __deque_block_range operator*() const _NOEXCEPT {
+    if (__pos_.__m_iter_ == __end_.__m_iter_) {
+      return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);
+    } else {
+      return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + _Iterator::__block_size);
     }
-    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;
+  __deque_range& operator++() _NOEXCEPT {
+    if (__pos_.__m_iter_ == __end_.__m_iter_) {
+      __pos_ = __end_;
+    } else {
+      ++__pos_.__m_iter_;
+      __pos_.__ptr_ = *__pos_.__m_iter_;
     }
-    return __r;
+    return *this;
   }
 
-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;
+  _LIBCPP_HIDE_FROM_ABI friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {
+    return __lhs.__pos_ == __rhs.__pos_;
+  _LIBCPP_HIDE_FROM_ABI friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {
+    return !(__lhs == __rhs);
   }
+};
 
-// move
+template <class _Iterator>
+class __deque_backward_range {
+  using __deque_block_range = std::__deque_block_range<typename _Iterator::pointer>;
 
-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;
-}
+  const _Iterator __begin_;
+  _Iterator __pos_;
+public:
+  _LIBCPP_HIDE_FROM_ABI __deque_backward_range(_Iterator __begin, _Iterator __pos) _NOEXCEPT
+    : __begin_(__begin), __pos_(__pos) {}
 
-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;
+  _LIBCPP_HIDE_FROM_ABI __deque_backward_range begin() const {
+    return *this;
   }
 
-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;
+  _LIBCPP_HIDE_FROM_ABI __deque_backward_range end() const {
+    return __deque_backward_range(__begin_, __begin_);
+
+  _LIBCPP_HIDE_FROM_ABI __deque_block_range operator*() const _NOEXCEPT {
+    auto __last = std::prev(__pos_);
+    if (__begin_.__m_iter_ == __last.__m_iter_) {
+      return __deque_block_range(__begin_.__ptr_, __last.__ptr_ + 1);
+    } else {
+      return __deque_block_range(*__last.__m_iter_, __last.__ptr_ + 1);
     }
-    return __r;
   }
 
-// move_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>
-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;
+  _LIBCPP_HIDE_FROM_ABI __deque_backward_range& operator++() _NOEXCEPT {
+    --__pos_;
+    if (__begin_.__m_iter_ == __pos_.__m_iter_) {
+      __pos_ = __begin_;
+    } else {
+      __pos_ -= __pos_.__ptr_ - *__pos_.__m_iter_;
     }
-    return __r;
+    return *this;
   }
 
-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;
-    }
-    return __r;
+  _LIBCPP_HIDE_FROM_ABI friend bool
+  operator==(const __deque_backward_range& __lhs, const __deque_backward_range& __rhs) {
+    return __lhs.__pos_ == __rhs.__pos_;
+
+  _LIBCPP_HIDE_FROM_ABI friend bool
+  operator!=(const __deque_backward_range& __lhs, const __deque_backward_range& __rhs) {
+    return !(__lhs == __rhs);
+};
+
+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 _V1, class _P1, class _R1, class _M1, class _DiffT, _DiffT _BlockSize>
+struct __segmented_iterator_traits<__deque_iterator<_V1, _P1, _R1, _M1, _DiffT, _BlockSize> > {
+  using __is_segmented_iterator = true_type;
+  using _Iterator               = _LIBCPP_NODEBUG __deque_iterator<_V1, _P1, _R1, _M1, _DiffT, _BlockSize>;
+  using __deque_range           = _LIBCPP_NODEBUG std::__deque_range<_Iterator>;
+  using __deque_backward_range  = _LIBCPP_NODEBUG std::__deque_backward_range<_Iterator>;
+  using __deque_block_range     = _LIBCPP_NODEBUG typename __deque_range::__deque_block_range;
+
+  static _LIBCPP_HIDE_FROM_ABI __deque_range __get_forward_range(_Iterator __first, _Iterator __last) {
+    return __deque_range(__first, __last);
   }
 
-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;
+  static _LIBCPP_HIDE_FROM_ABI __deque_backward_range __get_backward_range(_Iterator __first, _Iterator __last) {
+    return __deque_backward_range(__first, __last);
+
+  static _LIBCPP_HIDE_FROM_ABI __deque_block_range __get_range_to_segment_begin(_Iterator __end) {
+    --__end;
+    return __deque_block_range(*__end.__m_iter_, __end.__ptr_ + 1);
+
+  static _LIBCPP_HIDE_FROM_ABI __deque_block_range __get_range_to_segment_end(_Iterator __begin) {
+    return __deque_block_range(__begin.__ptr_, *__begin.__m_iter_ + _BlockSize);
   }
+};
 
 template <class _Tp, class _Allocator>
 class __deque_base
 {
     __deque_base(const __deque_base& __c);
     __deque_base& operator=(const __deque_base& __c);
 public:
     typedef _Allocator                                allocator_type;
public:
     typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;
     typedef __split_buffer<pointer, __pointer_allocator> __map;
 
     typedef __deque_iterator<value_type, pointer, reference, __map_pointer,
                              difference_type>    iterator;
     typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,
                              difference_type>    const_iterator;
 
-    struct __deque_block_range {
-      explicit __deque_block_range(pointer __b, pointer __e) _NOEXCEPT : __begin_(__b), __end_(__e) {}
-      const pointer __begin_;
-      const pointer __end_;
-    };
-
-    struct __deque_range {
-      iterator __pos_;
-      const iterator __end_;
-
-      __deque_range(iterator __pos, iterator __e) _NOEXCEPT
-        : __pos_(__pos), __end_(__e) {}
-
-      explicit operator bool() const _NOEXCEPT {
-        return __pos_ != __end_;
-      }
-
-      __deque_range begin() const {
-        return *this;
-      }
-
-      __deque_range end() const {
-        return __deque_range(__end_, __end_);
-      }
-      __deque_block_range operator*() const _NOEXCEPT {
-         if (__pos_.__m_iter_ == __end_.__m_iter_) {
-          return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);
-        }
-        return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size);
-      }
-
-      __deque_range& operator++() _NOEXCEPT {
-        if (__pos_.__m_iter_ == __end_.__m_iter_) {
-          __pos_ = __end_;
-        } else {
-          ++__pos_.__m_iter_;
-          __pos_.__ptr_ = *__pos_.__m_iter_;
-        }
-        return *this;
-      }
-
-
-      _LIBCPP_HIDE_FROM_ABI friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {
-        return __lhs.__pos_ == __rhs.__pos_;
-      }
-      _LIBCPP_HIDE_FROM_ABI friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {
-        return !(__lhs == __rhs);
-      }
-    };
-
-
+    using __deque_range = std::__deque_range<iterator>;
+    using __deque_block_range = typename __deque_range::__deque_block_range;
 
     struct _ConstructTransaction {
       _ConstructTransaction(__deque_base* __db, __deque_block_range& __r)
         : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {}
 
 
       ~_ConstructTransaction() {
         __base_->size() += (__pos_ - __begin_);

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" }
       module unreachable_sentinel  { private header "__iterator/unreachable_sentinel.h" }
       module wrap_iter             { private header "__iterator/wrap_iter.h" }
     }
   }
   module latch {
     @requires_LIBCXX_ENABLE_THREADS@

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/allocate_at_least.h> // expected-error@*:* {{use of private header from outside its module: '__memory/allocate_at_least.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"
 
 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(HasCopyIt<int*>);
constexpr void test_iterators() {
       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()));
       assert(base(ret.in) == in.data());
       assert(base(ret.out) == out.data());
     }
   }
 }
 
-template <class In, class Out>
+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(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::copy(range, Out(out.begin()));
+    assert(std::ranges::equal(in, out));
+    assert(base(ret.in) == in.end());
+    assert(base(ret.out) == out.end());
+  }
+}
+
+template <template <class> class In, template <class> class Out>
 constexpr void test_sentinels() {
-  test_iterators<In, Out>();
-  test_iterators<In, Out, sized_sentinel<In>>();
-  test_iterators<In, Out, sentinel_wrapper<In>>();
+  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*>>) {
+      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 <class Out>
+template <template <class> class Out>
 constexpr void test_in_iterators() {
-  test_iterators<cpp20_input_iterator<int*>, Out, sentinel_wrapper<cpp20_input_iterator<int*>>>();
-  test_sentinels<forward_iterator<int*>, Out>();
-  test_sentinels<bidirectional_iterator<int*>, Out>();
-  test_sentinels<random_access_iterator<int*>, Out>();
-  test_sentinels<contiguous_iterator<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>();
 }
 
 template <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>();
 }
 
 constexpr bool test() {
-  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<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_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*>>>();
 
   { // check that ranges::dangling is returned

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<bidirectional_iterator, Out>();
+  test_sentinels<random_access_iterator, Out>();
+  test_sentinels<contiguous_iterator, 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>();
 }
 
 constexpr bool test() {
-  test_in_iterators<bidirectional_iterator<int*>>();
-  test_in_iterators<random_access_iterator<int*>>();
-  test_in_iterators<contiguous_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<bidirectional_iterator>();
+  test_in_iterators<random_access_iterator>();
+  test_in_iterators<contiguous_iterator>();
+
+  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<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>();
 }
 
-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>();
 }
 
 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_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_proxy_in_iterators<Cpp20InputProxyIterator>();
+  test_proxy_in_iterators<ForwardProxyIterator>();
+  test_proxy_in_iterators<BidirectionalProxyIterator>();
+  test_proxy_in_iterators<RandomAccessProxyIterator>();
+  test_proxy_in_iterators<ContiguousProxyIterator>();
 
   { // 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 Out>
+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 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<bidirectional_iterator<int*>, Out, sentinel_wrapper<bidirectional_iterator<int*>>>();
-  test_iterators<bidirectional_iterator<int*>, Out>();
-  test_iterators<random_access_iterator<int*>, Out>();
-  test_iterators<contiguous_iterator<int*>, Out>();
+  test_sentinels<bidirectional_iterator, Out>();
+  test_sentinels<random_access_iterator, Out>();
+  test_sentinels<contiguous_iterator, 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>();
 }
 
 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_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_proxy_in_iterators<BidirectionalProxyIterator>();
+  test_proxy_in_iterators<RandomAccessProxyIterator>();
+  test_proxy_in_iterators<ContiguousProxyIterator>();
 
   { // 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

friend constexpr difference_type operator-(const ProxyIterator& x, const ProxyIterator& y)
     return x.base_ - y.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>