On Fri, Mar 21, 2025 at 11:14 AM Tomasz Kamiński <tkami...@redhat.com> wrote:
> This is another piece of P1206R7, adding from_range constructor, > append_range, > prepend_range, insert_range, and assign_range members to std::deque. > > For insert_range, the handling of insertion in the middle of input-only > ranges > that are sized could be optimized, we still insert nodes one-by-one in > such case. > For forward and stronger ranges, we reduce them to common_range case, > by computing the iterator when computing the distance. > This is slightly suboptimal, as it require range to be iterated for > non-common > forward ranges that are sized. > > This patch extract a set of helper functions that accepts (iterator, > sentinel) pair: > _M_range_prepend, _M_range_append, _M_range_empl. > To make them usable in all standard modes, _M_emplace_aux is defined for > c++98 > as accepting const value_type&, and _M_insert_aux forwards to it. > > PR libstdc++/111055 > > libstdc++-v3/ChangeLog: > > * include/bits/deque.tcc (deque::insert_range, > __detail::__advance_dist): > Define. > (deque::_M_range_prepend, deque::_M_range_append): > Extract from _M_range_insert_aux for _ForwardIterator(s). > (deque::_M_range_empl): Define. > (deque::_M_emplace_aux(iterator, const value_type&)): Renamed > _M_insert_aux > in c++98. > * include/bits/stl_deque.h (deque::prepend_range, > deque::append_range), > (deque::assing_range):Define. > deque(from_range_t, _Rg&&, const allocator_type&): Define > constructor > and deduction guide. > * include/debug/deque (prepend_range, append_range, assing_range): > Define. > deque(from_range_t, _Rg&&, const allocator_type&): Define > constructor > and deduction guide. > (deque::_M_insert_qux): Define using _M_emplace_aux also for c++98. > (deque::_M_range_insert(iterator, _InputIterator, _InputIterator, > std::input_iterator_tag)): Forward to _M_range_empl. > * testsuite/23_containers/deque/cons/from_range.cc: New test. > * testsuite/23_containers/deque/modifiers/append_range.cc: New > test. > * testsuite/23_containers/deque/modifiers/assign/assign_range.cc: > New test. > * testsuite/23_containers/deque/modifiers/prepend_range.cc: New > test. > --- > Testing on x86_64-linux. Tests in 23_containers passed with each of: > -std=c++98, GLIBCXX_DEBUG and no-PCH. > OK for trunk? > > In the __advance_dist I branch between __it += __n and > ranges::advance(__it, ranges::end(__rg)), > instead of just calling ranges::advance(__it, __n), as the former will > handle nearly > common ranges, like `int const*` and `int*`. > > libstdc++-v3/include/bits/deque.tcc | 170 ++++++++++++++---- > libstdc++-v3/include/bits/stl_deque.h | 148 ++++++++++++++- > libstdc++-v3/include/debug/deque | 52 ++++++ > .../23_containers/deque/cons/from_range.cc | 99 ++++++++++ > .../deque/modifiers/append_range.cc | 88 +++++++++ > .../deque/modifiers/assign/assign_range.cc | 109 +++++++++++ > .../deque/modifiers/insert/insert_range.cc | 116 ++++++++++++ > .../deque/modifiers/prepend_range.cc | 90 ++++++++++ > 8 files changed, 829 insertions(+), 43 deletions(-) > create mode 100644 > libstdc++-v3/testsuite/23_containers/deque/cons/from_range.cc > create mode 100644 > libstdc++-v3/testsuite/23_containers/deque/modifiers/append_range.cc > create mode 100644 > libstdc++-v3/testsuite/23_containers/deque/modifiers/assign/assign_range.cc > create mode 100644 > libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/insert_range.cc > create mode 100644 > libstdc++-v3/testsuite/23_containers/deque/modifiers/prepend_range.cc > > diff --git a/libstdc++-v3/include/bits/deque.tcc > b/libstdc++-v3/include/bits/deque.tcc > index fcbecca55b4..8444d810e03 100644 > --- a/libstdc++-v3/include/bits/deque.tcc > +++ b/libstdc++-v3/include/bits/deque.tcc > @@ -584,13 +584,72 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > > template <typename _Tp, typename _Alloc> > - template <typename _InputIterator> > + template <typename _InputIterator, typename _Sentinel> > void > deque<_Tp, _Alloc>:: > - _M_range_insert_aux(iterator __pos, > - _InputIterator __first, _InputIterator __last, > - std::input_iterator_tag) > - { std::copy(__first, __last, std::inserter(*this, __pos)); } > + _M_range_prepend(_InputIterator __first, _Sentinel __last, > + size_type __n) > + { > + iterator __new_start = _M_reserve_elements_at_front(__n); > + __try > + { > + std::__uninitialized_copy_a(_GLIBCXX_MOVE(__first), __last, > + __new_start, > _M_get_Tp_allocator()); > + this->_M_impl._M_start = __new_start; > + } > + __catch(...) > + { > + _M_destroy_nodes(__new_start._M_node, > + this->_M_impl._M_start._M_node); > + __throw_exception_again; > + } > + } > + > + template <typename _Tp, typename _Alloc> > + template <typename _InputIterator, typename _Sentinel> > + void > + deque<_Tp, _Alloc>:: > + _M_range_append(_InputIterator __first, _Sentinel __last, > + size_type __n) > + { > + iterator __new_finish = _M_reserve_elements_at_back(__n); > + __try > + { > + std::__uninitialized_copy_a(_GLIBCXX_MOVE(__first), __last, > + this->_M_impl._M_finish, > + _M_get_Tp_allocator()); > + this->_M_impl._M_finish = __new_finish; > + } > + __catch(...) > + { > + _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, > + __new_finish._M_node + 1); > + __throw_exception_again; > + } > + } > + > + template <typename _Tp, typename _Alloc> > + template <typename _InputIterator, typename _Sentinel> > + void > + deque<_Tp, _Alloc>:: > + _M_range_empl(iterator __pos, _InputIterator __first, _Sentinel > __last) > + { > + if (__pos._M_cur != this->_M_impl._M_finish._M_cur) > + for (; __first != __last; (void)++__first, ++__pos) > + __pos = _M_emplace_aux(__pos, *__first); > + else > + for (; __first != __last; ++__first) > + if (this->_M_impl._M_finish._M_cur > + != this->_M_impl._M_finish._M_last - 1) > + { > + _Alloc_traits::construct(this->_M_impl, > + this->_M_impl._M_finish._M_cur, > + *__first); > + ++this->_M_impl._M_finish._M_cur; > + } > + else > + _M_push_back_aux(*__first); > + } > > template <typename _Tp, typename _Alloc> > template <typename _ForwardIterator> > @@ -605,38 +664,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > return; > > if (__pos._M_cur == this->_M_impl._M_start._M_cur) > - { > - iterator __new_start = _M_reserve_elements_at_front(__n); > - __try > - { > - std::__uninitialized_copy_a(__first, __last, __new_start, > - _M_get_Tp_allocator()); > - this->_M_impl._M_start = __new_start; > - } > - __catch(...) > - { > - _M_destroy_nodes(__new_start._M_node, > - this->_M_impl._M_start._M_node); > - __throw_exception_again; > - } > - } > + _M_range_prepend(__first, __last, __n); > else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) > - { > - iterator __new_finish = _M_reserve_elements_at_back(__n); > - __try > - { > - std::__uninitialized_copy_a(__first, __last, > - this->_M_impl._M_finish, > - _M_get_Tp_allocator()); > - this->_M_impl._M_finish = __new_finish; > - } > - __catch(...) > - { > - _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, > - __new_finish._M_node + 1); > - __throw_exception_again; > - } > - } > + _M_range_append(__first, __last, __n); > else > _M_insert_aux(__pos, __first, __last, __n); > } > @@ -652,7 +682,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > #else > typename deque<_Tp, _Alloc>::iterator > deque<_Tp, _Alloc>:: > - _M_insert_aux(iterator __pos, const value_type& __x) > + _M_emplace_aux(iterator __pos, const value_type& __x) > { > value_type __x_copy = __x; // XXX copy > #endif > @@ -857,6 +887,72 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > } > > +#if __glibcxx_ranges_to_container // C++ >= 23 > +namespace __detail > I get compilation errors about missing __detail::__container_compatible_range being not defined when compiling in GLIBCXX_DEBUG mode, I plan to remove the namespace. > +{ > + template<ranges::forward_range _Rg> > + auto __advance_dist(_Rg& __rg) > + { > + struct _Res > + { > + ranges::iterator_t<_Rg> __last; > + ranges::range_difference_t<_Rg> __size; > + }; > + if constexpr (ranges::common_range<_Rg>) > + return _Res{ranges::end(__rg), ranges::distance(__rg)}; > + else if constexpr (ranges::sized_range<_Rg>) > + { > + auto const __n = ranges::distance(__rg); > + auto __it = ranges::begin(__rg); > + if constexpr (ranges::random_access_range<_Rg>) > + __it += __n; > + else > + ranges::advance(__it, ranges::end(__rg)); > + return _Res{__it, __n}; > + } > + else > + { > + auto __it = ranges::begin(__rg); > + auto const __last = ranges::end(__rg); > + ranges::range_difference_t<_Rg> __n(0); > + for (; __it != __last; ++__it) > + ++__n; > + return _Res{__it, __n}; > + } > + } > +} > + > + template<typename _Tp, typename _Alloc> > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr auto > + deque<_Tp, _Alloc>:: > + insert_range(const_iterator __pos, _Rg&& __rg) > + -> iterator > + { > + if (__pos == begin()) > + { > + prepend_range(std::forward<_Rg>(__rg)); > + return begin(); > + } > + > + const auto __ins_idx = __pos - begin(); > + if (__pos == cend()) > + append_range(std::forward<_Rg>(__rg)); > + else if constexpr (ranges::forward_range<_Rg>) > + { > + auto [__last, __n] = __detail::__advance_dist(__rg); > + if (__builtin_expect(__n != 0, 1)) > + _M_insert_aux(__pos._M_const_cast(), > + ranges::begin(__rg), __last, > + __n); > + } > + else > + // TODO Optimize sized input ranges: space could be reserved. > + _M_range_empl(__pos._M_const_cast(), ranges::begin(__rg), > ranges::end(__rg)); > + return begin() + __ins_idx; > + } > +#endif // ranges_to_container > + > template<typename _Tp, typename _Alloc> > void > deque<_Tp, _Alloc>:: > diff --git a/libstdc++-v3/include/bits/stl_deque.h > b/libstdc++-v3/include/bits/stl_deque.h > index 69367140c8e..d9153788f29 100644 > --- a/libstdc++-v3/include/bits/stl_deque.h > +++ b/libstdc++-v3/include/bits/stl_deque.h > @@ -66,6 +66,10 @@ > #if __cplusplus > 201703L > # include <compare> > #endif > +#if __cplusplus > 202002L > +# include <bits/ranges_algobase.h> // ranges::copy > +# include <bits/ranges_util.h> // ranges::subrange > +#endif > > #include <debug/assertions.h> > > @@ -1019,6 +1023,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Construct a deque from a range. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr > + deque(from_range_t, _Rg&& __rg, const allocator_type& __a = > _Alloc()) > + : deque(__a) > + { append_range(std::forward<_Rg>(__rg)); } > +#endif > + > /** > * The dtor only erases the elements, and note that if the elements > * themselves are pointers, the pointed-to memory is not touched > in any > @@ -1135,6 +1151,51 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > { _M_assign_aux(__l.begin(), __l.end(), > random_access_iterator_tag()); } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Assign a range to the deque. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + assign_range(_Rg&& __rg) > + { > + static_assert(assignable_from<_Tp&, > ranges::range_reference_t<_Rg>>); > + > + if constexpr (ranges::forward_range<_Rg> || > ranges::sized_range<_Rg>) > + { > + const auto __n = size_type(ranges::distance(__rg)); > + if (__n <= size()) > + { > + auto __res = ranges::copy(__rg, begin()); > + return _M_erase_at_end(__res.out); > + } > + > + auto __rest = ranges::copy_n(ranges::begin(__rg), size(), > + begin()).in; > + _M_range_append(std::move(__rest), ranges::end(__rg), > + __n - size()); > + } > + else > + { > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + for (iterator __it = begin(), __end = end(); > + __it != __end; (void)++__first, ++__it) > + { > + if (__first == __last) > + return _M_erase_at_end(__it); > + > + *__it = *__first; > + } > + > + for (; __first != __last; ++__first) > + emplace_back(*__first); > + } > + } > +#endif // ranges_to_container > + > + > /// Get a copy of the memory allocation object. > _GLIBCXX_NODISCARD > allocator_type > @@ -1762,6 +1823,58 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Insert a range into the deque. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr iterator > + insert_range(const_iterator __pos, _Rg&& __rg); > + > + /** > + * @brief Prepend a range at the begining of the deque. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + prepend_range(_Rg&& __rg) > + { > + if constexpr (ranges::forward_range<_Rg> || > ranges::sized_range<_Rg>) > + { > + const size_type __n(ranges::distance(__rg)); > + if (__builtin_expect(__n != 0, 1)) > + _M_range_prepend(ranges::begin(__rg), ranges::end(__rg), > __n); > + } > + else > + _M_range_empl(begin(), ranges::begin(__rg), ranges::end(__rg)); > + } > + > + /** > + * @brief Append a range at the end of the deque. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + append_range(_Rg&& __rg) > + { > + if constexpr (ranges::forward_range<_Rg> || > ranges::sized_range<_Rg>) > + { > + const size_type __n(ranges::distance(__rg)); > + if (__builtin_expect(__n != 0, 1)) > + _M_range_append(ranges::begin(__rg), ranges::end(__rg), > __n); > + } > + else > + { > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + for (; __first != __last; ++__first) > + emplace_back(*__first); > + } > + } > +#endif // ranges_to_container > + > + > /** > * @brief Remove element at given position. > * @param __position Iterator pointing to element to be erased. > @@ -2036,11 +2149,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > + // insert [__first, __last) at the front, assumes distance(__first, > __last) is n > + template<typename _InputIterator, typename _Sentinel> > + void _M_range_prepend(_InputIterator __first, _Sentinel __last, > + size_type __n); > + > + // insert [__first, __last) at the back, assumes distance(__first, > __last) is n > + template<typename _InputIterator, typename _Sentinel> > + void _M_range_append(_InputIterator __first, _Sentinel __last, > + size_type __n); > + > + // insert [__first, __last) at the _pos, be inserting each element > separately > + template<typename _InputIterator, typename _Sentinel> > + void _M_range_empl(iterator __pos, > + _InputIterator __first, _Sentinel __last); > + > // called by the second insert_dispatch above > template<typename _InputIterator> > void > _M_range_insert_aux(iterator __pos, _InputIterator __first, > - _InputIterator __last, > std::input_iterator_tag); > + _InputIterator __last, std::input_iterator_tag) > + { _M_range_empl(__pos, __first, __last); } > > // called by the second insert_dispatch above > template<typename _ForwardIterator> > @@ -2057,17 +2186,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > // called by insert(p,x) > #if __cplusplus < 201103L > iterator > - _M_insert_aux(iterator __pos, const value_type& __x); > + _M_emplace_aux(iterator __pos, const value_type& __x); > #else > - iterator > - _M_insert_aux(iterator __pos, const value_type& __x) > - { return _M_emplace_aux(__pos, __x); } > - > template<typename... _Args> > iterator > _M_emplace_aux(iterator __pos, _Args&&... __args); > #endif > > + iterator > + _M_insert_aux(iterator __pos, const value_type& __x) > + { return _M_emplace_aux(__pos, __x); } > + > // called by insert(p,n,x) via fill_insert > void > _M_insert_aux(iterator __pos, size_type __n, const value_type& __x); > @@ -2281,6 +2410,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > typename = _RequireAllocator<_Allocator>> > deque(_InputIterator, _InputIterator, _Allocator = _Allocator()) > -> deque<_ValT, _Allocator>; > + > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<ranges::input_range _Rg, > + typename _Alloc = allocator<ranges::range_value_t<_Rg>>> > + deque(from_range_t, _Rg&&, _Alloc = _Alloc()) > + -> deque<ranges::range_value_t<_Rg>, _Alloc>; > +#endif > #endif > > /** > diff --git a/libstdc++-v3/include/debug/deque > b/libstdc++-v3/include/debug/deque > index 0422acf3496..eb66f8a9590 100644 > --- a/libstdc++-v3/include/debug/deque > +++ b/libstdc++-v3/include/debug/deque > @@ -155,6 +155,14 @@ namespace __debug > __gnu_debug::__base(__last), __a) > { } > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr > + deque(from_range_t, _Rg&& __rg, const _Allocator& __a = > _Allocator()) > + : _Base(from_range, std::forward<_Rg>(__rg), __a) > + { } > +#endif > + > deque(_Base_ref __x) > : _Base(__x._M_ref) { } > > @@ -210,6 +218,16 @@ namespace __debug > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + assign_range(_Rg&& __rg) > + { > + _Base::assign_range(std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + } > +#endif > + > using _Base::get_allocator; > > // iterators: > @@ -544,6 +562,33 @@ namespace __debug > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr iterator > + insert_range(const_iterator __pos, _Rg&& __rg) > + { > + auto __res = _Base::insert(__pos.base(), > std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + return iterator(__res, this); > + } > + > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + prepend_range(_Rg&& __rg) > + { > + _Base::prepend_range(std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + } > + > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + append_range(_Rg&& __rg) > + { > + _Base::append_range(std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + } > +#endif > + > void > pop_front() _GLIBCXX_NOEXCEPT > { > @@ -667,6 +712,13 @@ namespace __debug > typename = _RequireAllocator<_Allocator>> > deque(size_t, _Tp, _Allocator = _Allocator()) > -> deque<_Tp, _Allocator>; > + > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<ranges::input_range _Rg, > + typename _Alloc = allocator<ranges::range_value_t<_Rg>>> > + deque(from_range_t, _Rg&&, _Alloc = _Alloc()) > + -> deque<ranges::range_value_t<_Rg>, _Alloc>; > +#endif > #endif > > template<typename _Tp, typename _Alloc> > diff --git a/libstdc++-v3/testsuite/23_containers/deque/cons/from_range.cc > b/libstdc++-v3/testsuite/23_containers/deque/cons/from_range.cc > new file mode 100644 > index 00000000000..73e7e724065 > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/deque/cons/from_range.cc > @@ -0,0 +1,99 @@ > +// { dg-do run { target c++23 } } > + > +#include <deque> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +void > +test_deduction_guide(long* p) > +{ > + __gnu_test::test_input_range<long> r(p, p); > + std::deque d(std::from_range, r); > + static_assert(std::is_same_v<decltype(d), std::deque<long>>); > + > + using Alloc = __gnu_test::SimpleAllocator<long>; > + Alloc alloc; > + std::deque d2(std::from_range, r, alloc); > + static_assert(std::is_same_v<decltype(d2), std::deque<long, Alloc>>); > +} > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test(Alloc alloc) > +{ > + // The deque's value_type. > + using V = typename std::allocator_traits<Alloc>::value_type; > + > + // The range's value_type. > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::deque<V, Alloc>& l, std::span<T> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + if (l[i] != r[i]) > + return false; > + return true; > + }; > + > + std::deque<V, Alloc> d0(std::from_range, Range(a, a+0)); > + VERIFY( d0.empty() ); > + VERIFY( d0.get_allocator() == Alloc() ); > + > + std::deque<V, Alloc> d4(std::from_range, Range(a, a+4)); > + VERIFY( eq(d4, {a, 4}) ); > + VERIFY( d4.get_allocator() == Alloc() ); > + > + std::deque<V, Alloc> d9(std::from_range, Range(a, a+9), alloc); > + VERIFY( eq(d9, {a, 9}) ); > + VERIFY( d9.get_allocator() == alloc ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range>(std::allocator<int>()); > + do_test<Range>(__gnu_test::uneq_allocator<int>(42)); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<int>>(); > + do_test_a<test_forward_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<int>>(); > + do_test_a<test_input_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, input_iterator_wrapper>>(); > + > + do_test_a<test_range_nocopy<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<int, > input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + // Not lvalue-convertible to int > + struct C { > + C(int v) : val(v) { } > + operator int() && { return val; } > + bool operator==(int b) const { return b == val; } > + int val; > + }; > + using rvalue_input_range = test_range<C, input_iterator_wrapper_rval>; > + do_test<rvalue_input_range>(std::allocator<int>()); > + > + return true; > +} > + > +int main() > +{ > + test_ranges(); > +} > diff --git > a/libstdc++-v3/testsuite/23_containers/deque/modifiers/append_range.cc > b/libstdc++-v3/testsuite/23_containers/deque/modifiers/append_range.cc > new file mode 100644 > index 00000000000..a4eebcbc96d > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/append_range.cc > @@ -0,0 +1,88 @@ > +// { dg-do run { target c++23 } } > + > +#include <deque> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + // The deque's value_type. > + using V = typename std::allocator_traits<Alloc>::value_type; > + > + // The range's value_type. > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::deque<V, Alloc>& l, std::span<T> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + if (l[i] != r[i]) > + return false; > + return true; > + }; > + > + Range r4(a, a+4); > + Range r5(a+4, a+9); > + > + std::deque<V, Alloc> d; > + d.append_range(r4); > + VERIFY( eq(d, {a, 4}) ); > + d.append_range(r5); > + VERIFY( eq(d, a) ); > + d.append_range(Range(a, a)); > + VERIFY( eq(d, a) ); > + d.clear(); > + d.append_range(Range(a, a)); > + VERIFY( d.empty() ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<int>>(); > + do_test<Range, __gnu_test::SimpleAllocator<int>>(); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<int>>(); > + do_test_a<test_forward_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<int>>(); > + do_test_a<test_input_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, input_iterator_wrapper>>(); > + > + do_test_a<test_range_nocopy<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<int, > input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + // Not lvalue-convertible to int > + struct C { > + C(int v) : val(v) { } > + operator int() && { return val; } > + bool operator==(int b) const { return b == val; } > + int val; > + }; > + using rvalue_input_range = test_range<C, input_iterator_wrapper_rval>; > + do_test<rvalue_input_range, std::allocator<int>>(); > + > + return true; > +} > + > +int main() > +{ > + test_ranges(); > +} > diff --git > a/libstdc++-v3/testsuite/23_containers/deque/modifiers/assign/assign_range.cc > b/libstdc++-v3/testsuite/23_containers/deque/modifiers/assign/assign_range.cc > new file mode 100644 > index 00000000000..0cfdd3b2c0f > --- /dev/null > +++ > b/libstdc++-v3/testsuite/23_containers/deque/modifiers/assign/assign_range.cc > @@ -0,0 +1,109 @@ > +// { dg-do run { target c++23 } } > + > +#include <deque> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + // The deque's value_type. > + using V = typename std::allocator_traits<Alloc>::value_type; > + > + // The range's value_type. > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::deque<V, Alloc>& l, std::span<T> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + if (l[i] != r[i]) > + return false; > + return true; > + }; > + > + // assign to empty deque > + std::deque<V, Alloc> d; > + d.assign_range(Range(a, a)); > + VERIFY( d.empty() ); > + d.assign_range(Range(a, a+4)); > + VERIFY( eq(d, {a, 4}) ); > + d.clear(); > + d.assign_range(Range(a, a+9)); > + VERIFY( eq(d, a) ); > + d.clear(); > + d.assign_range(Range(a, a+4)); > + VERIFY( eq(d, {a, 4}) ); > + d.clear(); > + d.assign_range(Range(a, a+9)); > + VERIFY( eq(d, a) ); > + > + > + // assign to non-empty deque > + d.assign_range(Range(a, a+4)); // smaller than size() > + VERIFY( eq(d, {a, 4}) ); > + d.assign_range(Range(a, a+9)); // larger than size() > + VERIFY( eq(d, a) ); > + d.resize(1); > + d.assign_range(Range(a, a+4)); // larger than size() > + VERIFY( eq(d, {a, 4}) ); > + d.clear(); > + d.resize(4); > + d.assign_range(Range(a, a+4)); // equal to size() > + VERIFY( eq(d, {a, 4}) ); > + d.shrink_to_fit(); > + d.assign_range(Range(a, a+9)); > + VERIFY( eq(d, a) ); > + d.assign_range(Range(a, a)); > + VERIFY( d.empty() ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<int>>(); > + do_test<Range, __gnu_test::SimpleAllocator<int>>(); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<int>>(); > + do_test_a<test_forward_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<int>>(); > + do_test_a<test_input_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, input_iterator_wrapper>>(); > + > + do_test_a<test_range_nocopy<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<int, > input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + // Not lvalue-convertible to int > + struct C { > + C(int v) : val(v) { } > + operator int() && { return val; } > + bool operator==(int b) const { return b == val; } > + int val; > + }; > + using rvalue_input_range = test_range<C, input_iterator_wrapper_rval>; > + do_test<rvalue_input_range, std::allocator<int>>(); > + > + return true; > +} > + > +int main() > +{ > + test_ranges(); > +} > diff --git > a/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/insert_range.cc > b/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/insert_range.cc > new file mode 100644 > index 00000000000..c5a8b3fc7c3 > --- /dev/null > +++ > b/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/insert_range.cc > @@ -0,0 +1,116 @@ > +// { dg-do run { target c++23 } } > + > +#include <deque> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + // The deque's value_type. > + using V = typename std::allocator_traits<Alloc>::value_type; > + > + // The range's value_type. > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::deque<V, Alloc>& l, std::span<T> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + if (l[i] != r[i]) > + return false; > + return true; > + }; > + > + std::deque<V, Alloc> d; > + d.insert_range(d.begin(), Range(a, a)); > + VERIFY( d.empty() ); > + d.insert_range(d.begin(), Range(a, a+4)); > + VERIFY( eq(d, {a, a+4}) ); > + d.clear(); > + d.insert_range(d.begin(), Range(a+4, a+9)); > + VERIFY( eq(d, {a+4, a+9}) ); > + d.insert_range(d.begin(), Range(a, a+4)); > + VERIFY( eq(d, a) ); > + d.clear(); > + d.shrink_to_fit(); > + > + d.insert_range(d.end(), Range(a, a)); > + VERIFY( d.empty() ); > + d.insert_range(d.end(), Range(a, a+4)); > + VERIFY( eq(d, {a, a+4}) ); > + d.clear(); > + d.insert_range(d.end(), Range(a, a+4)); > + VERIFY( eq(d, {a, a+4}) ); > + d.insert_range(d.end(), Range(a+4, a+9)); > + VERIFY( eq(d, a) ); > + d.clear(); > + d.shrink_to_fit(); > + > + auto it = d.insert_range(d.begin(), Range(a, a+3)); > + VERIFY( it == d.begin() ); > + it = d.insert_range(d.end(), Range(a+6, a+9)); > + VERIFY( it == d.begin()+3 ); > + it = d.insert_range(d.begin()+3, Range(a+3, a+6)); > + VERIFY( it == d.begin()+3 ); > + VERIFY( eq(d, a) ); > + d.resize(3); > + it = d.insert_range(d.begin()+1, Range(a+4, a+9)); > + VERIFY( it == d.begin()+1 ); > + it = d.insert_range(d.begin()+1, Range(a+1, a+4)); > + VERIFY( it == d.begin()+1 ); > + d.resize(9); > + VERIFY( eq(d, a) ); > + it = d.insert_range(d.begin() + 6, Range(a, a)); > + VERIFY( it == d.begin() + 6 ); > + VERIFY( eq(d, a) ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<int>>(); > + do_test<Range, __gnu_test::SimpleAllocator<int>>(); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<int>>(); > + do_test_a<test_forward_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<int>>(); > + do_test_a<test_input_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, input_iterator_wrapper>>(); > + > + do_test_a<test_range_nocopy<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<int, > input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + // Not lvalue-convertible to int > + struct C { > + C(int v) : val(v) { } > + operator int() && { return val; } > + bool operator==(int b) const { return b == val; } > + int val; > + }; > + using rvalue_input_range = test_range<C, input_iterator_wrapper_rval>; > + do_test<rvalue_input_range, std::allocator<int>>(); > + > + return true; > +} > +int main() > +{ > + test_ranges(); > +} > diff --git > a/libstdc++-v3/testsuite/23_containers/deque/modifiers/prepend_range.cc > b/libstdc++-v3/testsuite/23_containers/deque/modifiers/prepend_range.cc > new file mode 100644 > index 00000000000..7cb57df7826 > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/prepend_range.cc > @@ -0,0 +1,90 @@ > +// { dg-do run { target c++23 } } > + > +#include <deque> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + // The deque's value_type. > + using V = typename std::allocator_traits<Alloc>::value_type; > + > + // The range's value_type. > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::deque<V, Alloc>& l, std::span<T> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + if (l[i] != r[i]) > + return false; > + return true; > + }; > + > + Range r4(a+5, a+9); > + Range r5(a+0, a+5); > + > + std::deque<V, Alloc> d; > + d.prepend_range(r4); > + VERIFY( d.size() == 4 ); > + VERIFY( d[0] == 6 ); > + VERIFY( eq(d, {a+5, 4}) ); > + d.prepend_range(r5); > + VERIFY( eq(d, a) ); > + d.prepend_range(Range(a, a)); > + VERIFY( eq(d, a) ); > + d.clear(); > + d.prepend_range(Range(a, a)); > + VERIFY( d.empty() ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<int>>(); > + do_test<Range, __gnu_test::SimpleAllocator<int>>(); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<int>>(); > + do_test_a<test_forward_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<int>>(); > + do_test_a<test_input_sized_range<int>>(); > + do_test_a<test_sized_range_sized_sent<int, input_iterator_wrapper>>(); > + > + do_test_a<test_range_nocopy<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<int, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<int, > input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + // Not lvalue-convertible to int > + struct C { > + C(int v) : val(v) { } > + operator int() && { return val; } > + bool operator==(int b) const { return b == val; } > + int val; > + }; > + using rvalue_input_range = test_range<C, input_iterator_wrapper_rval>; > + do_test<rvalue_input_range, std::allocator<int>>(); > + > + return true; > +} > + > +int main() > +{ > + test_ranges(); > +} > -- > 2.48.1 > >