diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -185,6 +185,7 @@ formatter_float.bench.cpp formatter_int.bench.cpp function.bench.cpp + join_view.bench.cpp map.bench.cpp monotonic_buffer.bench.cpp ordered_set.bench.cpp diff --git a/libcxx/benchmarks/join_view.bench.cpp b/libcxx/benchmarks/join_view.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/join_view.bench.cpp @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include + +#include "benchmark/benchmark.h" + +namespace { +void run_sizes(auto benchmark) { + benchmark->Arg(0) + ->Arg(1) + ->Arg(2) + ->Arg(64) + ->Arg(512) + ->Arg(1024) + ->Arg(4000) + ->Arg(4096) + ->Arg(5500) + ->Arg(64000) + ->Arg(65536) + ->Arg(70000); +} + +void BM_join_view_in_vectors(benchmark::State& state) { + auto size = state.range(0); + std::vector> input(size, std::vector(32)); + std::ranges::fill(input | std::views::join, 10); + std::vector output; + output.resize(size * 32); + + for (auto _ : state) { + benchmark::DoNotOptimize(input); + benchmark::DoNotOptimize(output); + std::ranges::copy(input | std::views::join, output.begin()); + } +} +BENCHMARK(BM_join_view_in_vectors)->Apply(run_sizes); + +void BM_join_view_out_vectors(benchmark::State& state) { + auto size = state.range(0); + std::vector> output(size, std::vector(32)); + std::vector input; + input.resize(size * 32); + std::ranges::fill(input, 10); + + for (auto _ : state) { + benchmark::DoNotOptimize(output); + benchmark::DoNotOptimize(input); + std::ranges::copy(input, (output | std::views::join).begin()); + } +} +BENCHMARK(BM_join_view_out_vectors)->Apply(run_sizes); + +void BM_join_view_deques(benchmark::State& state) { + auto size = state.range(0); + std::deque> deque(size, std::deque(32)); + std::ranges::fill(deque | std::views::join, 10); + std::vector output; + output.resize(size * 32); + + for (auto _ : state) { + benchmark::DoNotOptimize(deque); + benchmark::DoNotOptimize(output); + std::ranges::copy(deque | std::views::join, output.begin()); + } +} +BENCHMARK(BM_join_view_deques)->Apply(run_sizes); +} // namespace + +BENCHMARK_MAIN(); diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -79,6 +79,9 @@ - `D122780 `_ Improved the performance of std::sort - The ``ranges`` versions of ``copy``, ``move``, ``copy_backward`` and ``move_backward`` are now also optimized for ``std::deque<>::iterator``, which can lead to up to 20x performance improvements on certain algorithms. +- The ``std`` and ``ranges`` versions of ``copy``, ``move``, ``copy_backward`` and ``move_backward`` are now also + optimized for ``join_view::iterator``, which can lead to up to 20x performance improvements on certain combinations of + iterators and algorithms. Deprecations and Removals ------------------------- diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -392,6 +392,7 @@ __iterator/iter_swap.h __iterator/iterator.h __iterator/iterator_traits.h + __iterator/iterator_with_data.h __iterator/mergeable.h __iterator/move_iterator.h __iterator/move_sentinel.h diff --git a/libcxx/include/__iterator/iterator_with_data.h b/libcxx/include/__iterator/iterator_with_data.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/iterator_with_data.h @@ -0,0 +1,100 @@ +//===----------------------------------------------------------------------===// +// +// 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___ITERATOR_ITERATOR_WITH_DATA_H +#define _LIBCPP___ITERATOR_ITERATOR_WITH_DATA_H + +#include <__compare/compare_three_way_result.h> +#include <__compare/three_way_comparable.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/iter_move.h> +#include <__iterator/iter_swap.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/readable_traits.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER >= 20 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +class __iterator_with_data { + _Iterator __iter_{}; + _Data __data_{}; + +public: + using value_type = iter_value_t<_Iterator>; + using difference_type = iter_difference_t<_Iterator>; + + _LIBCPP_HIDE_FROM_ABI __iterator_with_data() = default; + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data(_Iterator __iter, _Data __data) + : __iter_(std::move(__iter)), __data_(std::move(__data)) {} + + constexpr _LIBCPP_HIDE_FROM_ABI _Iterator __get_iter() const { return __iter_; } + + constexpr _LIBCPP_HIDE_FROM_ABI _Data __get_data() && { return std::move(__data_); } + + friend constexpr _LIBCPP_HIDE_FROM_ABI bool + operator==(const __iterator_with_data& __lhs, const __iterator_with_data& __rhs) { + return __lhs.__iter_ == __rhs.__iter_; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data& operator++() { + ++__iter_; + return *this; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data operator++(int) { + auto __tmp = *this; + __iter_++; + return __tmp; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data& operator--() + requires bidirectional_iterator<_Iterator> + { + --__iter_; + return *this; + } + + constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data operator--(int) + requires bidirectional_iterator<_Iterator> + { + auto __tmp = *this; + --__iter_; + return __tmp; + } + + constexpr _LIBCPP_HIDE_FROM_ABI iter_reference_t<_Iterator> operator*() const { return *__iter_; } + + _LIBCPP_HIDE_FROM_ABI friend constexpr iter_rvalue_reference_t<_Iterator> + iter_move(const __iterator_with_data& __iter) noexcept(noexcept(ranges::iter_move(__iter.__iter_))) { + return ranges::iter_move(__iter.__iter_); + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr void + iter_swap(const __iterator_with_data& __lhs, + const __iterator_with_data& __rhs) noexcept(noexcept(ranges::iter_swap(__lhs.__iter_, __rhs.__iter_))) + requires indirectly_swappable<_Iterator> + { + return ranges::iter_swap(__lhs.__data_, __rhs.__iter_); + } +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 20 + +#endif // _LIBCPP___ITERATOR_ITERATOR_WITH_DATA_H diff --git a/libcxx/include/__ranges/join_view.h b/libcxx/include/__ranges/join_view.h --- a/libcxx/include/__ranges/join_view.h +++ b/libcxx/include/__ranges/join_view.h @@ -20,9 +20,12 @@ #include <__iterator/iter_move.h> #include <__iterator/iter_swap.h> #include <__iterator/iterator_traits.h> +#include <__iterator/iterator_with_data.h> +#include <__iterator/segmented_iterator.h> #include <__ranges/access.h> #include <__ranges/all.h> #include <__ranges/concepts.h> +#include <__ranges/empty.h> #include <__ranges/non_propagating_cache.h> #include <__ranges/range_adaptor.h> #include <__ranges/view_interface.h> @@ -63,6 +66,14 @@ >; }; + template + requires view<_View> && input_range> + struct __join_view_iterator; + + template + requires view<_View> && input_range> + struct __join_view_sentinel; + template requires view<_View> && input_range> class join_view @@ -70,8 +81,22 @@ private: using _InnerRange = range_reference_t<_View>; - template struct __iterator; - template struct __sentinel; + template + using __iterator = __join_view_iterator<_View, _Const>; + + template + using __sentinel = __join_view_sentinel<_View, _Const>; + + template + requires view<_View2> && input_range> + friend struct __join_view_iterator; + + template + requires view<_View2> && input_range> + friend struct __join_view_sentinel; + + template + friend struct std::__segmented_iterator_traits; static constexpr bool _UseCache = !is_reference_v<_InnerRange>; using _Cache = _If<_UseCache, __non_propagating_cache>, __empty_cache>; @@ -139,49 +164,57 @@ } }; - template + template requires view<_View> && input_range> - template struct join_view<_View>::__sentinel { - template friend struct __sentinel; + struct __join_view_sentinel { + template + requires view<_View2> && input_range> + friend struct __join_view_sentinel; private: - using _Parent = __maybe_const<_Const, join_view>; + using _Parent = __maybe_const<_Const, join_view<_View>>; using _Base = __maybe_const<_Const, _View>; sentinel_t<_Base> __end_ = sentinel_t<_Base>(); public: _LIBCPP_HIDE_FROM_ABI - __sentinel() = default; + __join_view_sentinel() = default; _LIBCPP_HIDE_FROM_ABI - constexpr explicit __sentinel(_Parent& __parent) + constexpr explicit __join_view_sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {} _LIBCPP_HIDE_FROM_ABI - constexpr __sentinel(__sentinel __s) + constexpr __join_view_sentinel(__join_view_sentinel<_View, !_Const> __s) requires _Const && convertible_to, sentinel_t<_Base>> : __end_(std::move(__s.__end_)) {} template requires sentinel_for, iterator_t<__maybe_const<_OtherConst, _View>>> _LIBCPP_HIDE_FROM_ABI - friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) { + friend constexpr bool operator==(const __join_view_iterator<_View, _OtherConst>& __x, const __join_view_sentinel& __y) { return __x.__outer_ == __y.__end_; } }; - template + template requires view<_View> && input_range> - template struct join_view<_View>::__iterator + struct __join_view_iterator : public __join_view_iterator_category<__maybe_const<_Const, _View>> { - template friend struct __iterator; + template + requires view<_View2> && input_range> + friend struct __join_view_iterator; + + template + friend struct std::__segmented_iterator_traits; private: - using _Parent = __maybe_const<_Const, join_view>; + using _Parent = __maybe_const<_Const, join_view<_View>>; using _Base = __maybe_const<_Const, _View>; using _Outer = iterator_t<_Base>; using _Inner = iterator_t>; + using _InnerRange = range_reference_t<_View>; static constexpr bool __ref_is_glvalue = is_reference_v>; @@ -210,6 +243,9 @@ __inner_.reset(); } + _LIBCPP_HIDE_FROM_ABI constexpr __join_view_iterator(_Parent* __parent, _Outer __outer, _Inner __inner) + : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {} + public: using iterator_concept = _If< __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range> && @@ -228,17 +264,17 @@ range_difference_t<_Base>, range_difference_t>>; _LIBCPP_HIDE_FROM_ABI - __iterator() requires default_initializable<_Outer> = default; + __join_view_iterator() requires default_initializable<_Outer> = default; _LIBCPP_HIDE_FROM_ABI - constexpr __iterator(_Parent& __parent, _Outer __outer) + constexpr __join_view_iterator(_Parent& __parent, _Outer __outer) : __outer_(std::move(__outer)) , __parent_(std::addressof(__parent)) { __satisfy(); } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator(__iterator __i) + constexpr __join_view_iterator(__join_view_iterator<_View, !_Const> __i) requires _Const && convertible_to, _Outer> && convertible_to, _Inner> @@ -259,7 +295,7 @@ } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator& operator++() { + constexpr __join_view_iterator& operator++() { auto&& __inner = [&]() -> auto&& { if constexpr (__ref_is_glvalue) return *__outer_; @@ -279,7 +315,7 @@ } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator operator++(int) + constexpr __join_view_iterator operator++(int) requires __ref_is_glvalue && forward_range<_Base> && forward_range> @@ -290,7 +326,7 @@ } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator& operator--() + constexpr __join_view_iterator& operator--() requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range> && @@ -309,7 +345,7 @@ } _LIBCPP_HIDE_FROM_ABI - constexpr __iterator operator--(int) + constexpr __join_view_iterator operator--(int) requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range> && @@ -321,7 +357,7 @@ } _LIBCPP_HIDE_FROM_ABI - friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) + friend constexpr bool operator==(const __join_view_iterator& __x, const __join_view_iterator& __y) requires __ref_is_glvalue && equality_comparable> && equality_comparable>> @@ -330,14 +366,14 @@ } _LIBCPP_HIDE_FROM_ABI - friend constexpr decltype(auto) iter_move(const __iterator& __i) + friend constexpr decltype(auto) iter_move(const __join_view_iterator& __i) noexcept(noexcept(ranges::iter_move(*__i.__inner_))) { return ranges::iter_move(*__i.__inner_); } _LIBCPP_HIDE_FROM_ABI - friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y) + friend constexpr void iter_swap(const __join_view_iterator& __x, const __join_view_iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_))) requires indirectly_swappable<_Inner> { @@ -365,6 +401,50 @@ } // namespace views } // namespace ranges +template + requires(ranges::common_range::_Parent> && + __is_cpp17_random_access_iterator::_Outer>::value && + __is_cpp17_random_access_iterator::_Inner>::value) +struct __segmented_iterator_traits> { + using _JoinViewIterator = ranges::__join_view_iterator<_View, _Const>; + + using __segment_iterator = + _LIBCPP_NODEBUG __iterator_with_data; + using __local_iterator = typename _JoinViewIterator::_Inner; + + // TODO: Would it make sense to enable the optimization for other iterator types? + + static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) { + if (ranges::empty(__iter.__parent_->__base_)) + return {}; + if (!__iter.__inner_.has_value()) + return __segment_iterator(--__iter.__outer_, __iter.__parent_); + return __segment_iterator(__iter.__outer_, __iter.__parent_); + } + + static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) { + if (ranges::empty(__iter.__parent_->__base_)) + return {}; + if (!__iter.__inner_.has_value()) + return ranges::end(*--__iter.__outer_); + return *__iter.__inner_; + } + + static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) { + return ranges::begin(*__iter.__get_iter()); + } + + static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) { + return ranges::end(*__iter.__get_iter()); + } + + static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator + __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) { + return _JoinViewIterator( + std::move(__seg_iter).__get_data(), std::move(__seg_iter).__get_iter(), std::move(__local_iter)); + } +}; + #endif // _LIBCPP_STD_VER > 17 _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -996,6 +996,7 @@ module iter_swap { private header "__iterator/iter_swap.h" } module iterator { private header "__iterator/iterator.h" } module iterator_traits { private header "__iterator/iterator_traits.h" } + module iterator_with_data { private header "__iterator/iterator_with_data.h" } module mergeable { private header "__iterator/mergeable.h" export functional.__functional.ranges_operations diff --git a/libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp b/libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp @@ -0,0 +1,39 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 + +#include "test_macros.h" + +TEST_DIAGNOSTIC_PUSH +TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header") +#include <__iterator/iterator_with_data.h> +TEST_DIAGNOSTIC_POP + +#include "test_iterators.h" + +static_assert(std::forward_iterator, int>>); +static_assert(std::bidirectional_iterator, int>>); +static_assert(std::bidirectional_iterator, int>>); +static_assert(std::bidirectional_iterator, int>>); + +constexpr bool test() { + { + std::__iterator_with_data, int> iter(forward_iterator(nullptr), 3); + assert(iter == iter); + assert(iter.__get_iter() == forward_iterator(nullptr)); + assert(std::move(iter).__get_data() == 3); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); +} diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -423,6 +423,7 @@ #include <__iterator/iter_swap.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iter_swap.h'}} #include <__iterator/iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator.h'}} #include <__iterator/iterator_traits.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator_traits.h'}} +#include <__iterator/iterator_with_data.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator_with_data.h'}} #include <__iterator/mergeable.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/mergeable.h'}} #include <__iterator/move_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/move_iterator.h'}} #include <__iterator/move_sentinel.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/move_sentinel.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp @@ -9,11 +9,16 @@ // UNSUPPORTED: c++03, c++11, c++14, c++17 #include +#include #include #include #include +#include #include +#include "test_iterators.h" +#include "type_algorithms.h" + template constexpr void test_containers() { using InIter = typename InContainer::iterator; @@ -39,6 +44,52 @@ } } +template +constexpr void test_join_view() { + auto to_subranges = std::views::transform([](auto& vec) { + return std::ranges::subrange(Iter(vec.data()), Sent(Iter(vec.data() + vec.size()))); + }); + + { // segmented -> contiguous + std::vector> vectors = {}; + auto range = vectors | to_subranges; + std::vector> subrange_vector(range.begin(), range.end()); + std::array arr; + + std::ranges::copy(subrange_vector | std::views::join, arr.begin()); + assert(std::ranges::equal(arr, std::array{})); + } + { // segmented -> contiguous + std::vector> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range = vectors | to_subranges; + std::vector> subrange_vector(range.begin(), range.end()); + std::array arr; + + std::ranges::copy(subrange_vector | std::views::join, arr.begin()); + assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // contiguous -> segmented + std::vector> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}}; + auto range = vectors | to_subranges; + std::vector> subrange_vector(range.begin(), range.end()); + std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + + std::ranges::copy(arr, (subrange_vector | std::views::join).begin()); + assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // segmented -> segmented + std::vector> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range1 = vectors | to_subranges; + std::vector> subrange_vector(range1.begin(), range1.end()); + std::vector> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}}; + auto range2 = to_vectors | to_subranges; + std::vector> to_subrange_vector(range2.begin(), range2.end()); + + std::ranges::copy(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).begin()); + assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } +} + int main(int, char**) { if (!std::is_constant_evaluated()) { test_containers, std::deque>(); @@ -47,5 +98,11 @@ test_containers, std::vector>(); } + meta::for_each(meta::forward_iterator_list{}, [] { + test_join_view(); + test_join_view>(); + test_join_view>(); + }); + return 0; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp @@ -123,17 +123,69 @@ } } +template +constexpr void test_join_view() { + auto to_subranges = std::views::transform([](auto& vec) { + return std::ranges::subrange(Iter(vec.begin()), Sent(Iter(vec.end()))); + }); + + { // segmented -> contiguous + std::vector> vectors = {}; + auto range = vectors | to_subranges; + std::vector> subrange_vector(range.begin(), range.end()); + std::array arr; + + std::ranges::copy_backward(subrange_vector | std::views::join, arr.end()); + assert(std::ranges::equal(arr, std::array{})); + } + { // segmented -> contiguous + std::vector> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range = vectors | to_subranges; + std::vector> subrange_vector(range.begin(), range.end()); + std::array arr; + + std::ranges::copy_backward(subrange_vector | std::views::join, arr.end()); + assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // contiguous -> segmented + std::vector> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}}; + auto range = vectors | to_subranges; + std::vector> subrange_vector(range.begin(), range.end()); + std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + + std::ranges::copy_backward(arr, (subrange_vector | std::views::join).end()); + assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } + { // segmented -> segmented + std::vector> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}}; + auto range1 = vectors | to_subranges; + std::vector> subrange_vector(range1.begin(), range1.end()); + std::vector> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}}; + auto range2 = to_vectors | to_subranges; + std::vector> to_subrange_vector(range2.begin(), range2.end()); + + std::ranges::copy_backward(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).end()); + assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); + } +} + +template +constexpr bool is_proxy_iterator = false; + +template +constexpr bool is_proxy_iterator> = true; + template