On Tue, 25 Mar 2025 at 15:53, 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 append_front of input non-sized range, we are emplacing element at the > front and > then reverse inserted elements. This does not existing elements, and properly > handle > aliasing ranges. > > 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, but reduces > number of instantiations. > > This patch extract _M_range_prepend, _M_range_append helper functions that > accepts > (iterator, sentinel) pair. This all used in all standard modes. > > PR libstdc++/111055 > > libstdc++-v3/ChangeLog: > > * include/bits/deque.tcc (deque::prepend_range, deque::append_range) > (deque::insert_range, __advance_dist): Define. > (deque::_M_range_prepend, deque::_M_range_append): > Extract from _M_range_insert_aux for _ForwardIterator(s). > * include/bits/stl_deque.h (deque::assign_range): Define. > (deque::prepend_range, deque::append_range, deque::insert_range): > Declare. > (deque(from_range_t, _Rg&&, const allocator_type&)): Define > constructor > and deduction guide. > * include/debug/deque (deque::prepend_range, deque::append_range) > (deque::assign_range): Define. > (deque(from_range_t, _Rg&&, const allocator_type&)): Define > constructor > and deduction guide. > * 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. > --- > Addressed all the comments. > Testing on x86_64-linux, container tests passed. > OK for trunk if tests pass?
OK, thanks. > > libstdc++-v3/include/bits/deque.tcc | 229 +++++++++++++++--- > libstdc++-v3/include/bits/stl_deque.h | 111 +++++++++ > libstdc++-v3/include/debug/deque | 51 ++++ > .../23_containers/deque/cons/from_range.cc | 117 +++++++++ > .../deque/modifiers/append_range.cc | 128 ++++++++++ > .../deque/modifiers/assign/assign_range.cc | 109 +++++++++ > .../deque/modifiers/insert/insert_range.cc | 142 +++++++++++ > .../deque/modifiers/prepend_range.cc | 140 +++++++++++ > 8 files changed, 996 insertions(+), 31 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..87ea1cebdaa 100644 > --- a/libstdc++-v3/include/bits/deque.tcc > +++ b/libstdc++-v3/include/bits/deque.tcc > @@ -583,6 +583,51 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; > } > > + template <typename _Tp, typename _Alloc> > + template <typename _InputIterator, typename _Sentinel> > + void > + deque<_Tp, _Alloc>:: > + _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> > void > @@ -605,38 +650,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); > } > @@ -857,6 +873,157 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > } > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + 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> > + auto > + deque<_Tp, _Alloc>:: > + insert_range(const_iterator __pos, _Rg&& __rg) > + -> iterator > + { > + if (__pos == cend()) > + { > + const auto __ins_idx = size(); > + append_range(std::forward<_Rg>(__rg)); > + return begin() + __ins_idx; > + } > + > + if (__pos == cbegin()) > + { > + prepend_range(std::forward<_Rg>(__rg)); > + return begin(); > + } > + > + const auto __ins_idx = __pos - cbegin(); > + if constexpr (ranges::forward_range<_Rg>) > + { > + auto [__last, __n] = __advance_dist(__rg); > + if (__n != 0) [[likely]] > + _M_insert_aux(__pos._M_const_cast(), > + ranges::begin(__rg), __last, > + __n); > + } > + else > + { > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + for (auto __it = __pos._M_const_cast(); __first != __last; > + (void)++__first, ++__it) > + __it = _M_emplace_aux(__it, *__first); > + } > + return begin() + __ins_idx; > + } > + > + template<typename _Tp, typename _Alloc> > + template<__detail::__container_compatible_range<_Tp> _Rg> > + void > + deque<_Tp, _Alloc>:: > + prepend_range(_Rg&& __rg) > + { > + if (empty()) > + append_range(std::forward<_Rg>(__rg)); > + else if constexpr (ranges::forward_range<_Rg> || > ranges::sized_range<_Rg>) > + { > + const size_type __n(ranges::distance(__rg)); > + if (__n != 0) [[likely]] > + _M_range_prepend(ranges::begin(__rg), ranges::end(__rg), __n); > + } > + else > + { > + struct _Guard_elts_front > + { > + deque& __self; > + size_type __n = 0; > + > + ~_Guard_elts_front() > + { > + if (__n > 0) > + __self._M_erase_at_begin(__self.begin() + __n); > + } > + }; > + > + _Guard_elts_front __guard{*this}; > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + for (; __first != __last; (void)++__first, ++__guard.__n) > + emplace_front(*__first); > + > + for (auto __fins = begin(), __lins = begin() + __guard.__n; > + __fins != __lins && __fins != --__lins; ++__fins) > + std::iter_swap(__fins, __lins); > + > + __guard.__n = 0; > + } > + } > + > + template<typename _Tp, typename _Alloc> > + template<__detail::__container_compatible_range<_Tp> _Rg> > + void > + deque<_Tp, _Alloc>:: > + append_range(_Rg&& __rg) > + { > + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) > + { > + const size_type __n(ranges::distance(__rg)); > + if (__n != 0) [[likely]] > + _M_range_append(ranges::begin(__rg), ranges::end(__rg), __n); > + } > + else > + { > + struct _Guard_elts_back > + { > + deque& __self; > + size_type __n = __self.size(); > + > + ~_Guard_elts_back() > + { > + if (__n < __self.size()) > + __self._M_erase_at_end(__self.begin() + __n); > + } > + }; > + > + _Guard_elts_back __guard{*this}; > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + for (; __first != __last; (void)++__first) > + emplace_back(*__first); > + > + __guard.__n = size(); > + } > + } > +#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..94e08861010 100644 > --- a/libstdc++-v3/include/bits/stl_deque.h > +++ b/libstdc++-v3/include/bits/stl_deque.h > @@ -66,6 +66,9 @@ > #if __cplusplus > 201703L > # include <compare> > #endif > +#if __cplusplus > 202002L > +# include <bits/ranges_algobase.h> // ranges::copy > +#endif > > #include <debug/assertions.h> > > @@ -1019,6 +1022,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Construct a deque from a range. > + * @param __rg A range of values that are convertible to `value_type`. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + 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 +1150,53 @@ _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. > + * @param __rg A range of values that are convertible to `value_type`. > + * @pre `__rg` and `*this` do not overlap. > + * @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 size_type __n(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 +1824,38 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Insert a range into the deque. > + * @param __rg A range of values that are convertible to `value_type`. > + * @pre `__rg` and `*this` do not overlap. > + * @return An iterator that points to the first new element inserted, > + * or to `__pos` if `__rg` is an empty range. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + iterator > + insert_range(const_iterator __pos, _Rg&& __rg); > + > + /** > + * @brief Prepend a range at the begining of the deque. > + * @param __rg A range of values that are convertible to `value_type`. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + void > + prepend_range(_Rg&& __rg); > + > + /** > + * @brief Append a range at the end of the deque. > + * @param __rg A range of values that are convertible to `value_type`. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + void > + append_range(_Rg&& __rg); > +#endif // ranges_to_container > + > /** > * @brief Remove element at given position. > * @param __position Iterator pointing to element to be erased. > @@ -2036,6 +2130,16 @@ _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); > + > // called by the second insert_dispatch above > template<typename _InputIterator> > void > @@ -2281,6 +2385,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..9715721ca52 100644 > --- a/libstdc++-v3/include/debug/deque > +++ b/libstdc++-v3/include/debug/deque > @@ -155,6 +155,13 @@ namespace __debug > __gnu_debug::__base(__last), __a) > { } > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<__detail::__container_compatible_range<_Tp> _Rg> > + 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 +217,16 @@ namespace __debug > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + void > + assign_range(_Rg&& __rg) > + { > + _Base::assign_range(std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + } > +#endif > + > using _Base::get_allocator; > > // iterators: > @@ -544,6 +561,33 @@ namespace __debug > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<__detail::__container_compatible_range<_Tp> _Rg> > + iterator > + insert_range(const_iterator __pos, _Rg&& __rg) > + { > + auto __res = _Base::insert_range(__pos.base(), > std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + return iterator(__res, this); > + } > + > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + void > + prepend_range(_Rg&& __rg) > + { > + _Base::prepend_range(std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + } > + > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + void > + append_range(_Rg&& __rg) > + { > + _Base::append_range(std::forward<_Rg>(__rg)); > + this->_M_invalidate_all(); > + } > +#endif > + > void > pop_front() _GLIBCXX_NOEXCEPT > { > @@ -667,6 +711,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..96e994d649c > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/deque/cons/from_range.cc > @@ -0,0 +1,117 @@ > +// { 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,10,11,12,13,14}; > + > + 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> d8(std::from_range, Range(a, a+8)); > + VERIFY( eq(d8, {a, 8}) ); > + VERIFY( d8.get_allocator() == Alloc() ); > + > + std::deque<V, Alloc> d9(std::from_range, Range(a, a+14), alloc); > + VERIFY( eq(d9, {a, 14}) ); > + VERIFY( d9.get_allocator() == alloc ); > +} > + > +struct EightInBuf > +{ > + EightInBuf(int x) : elems{x} > + { } > + > +private: > + int elems[512 / (sizeof(int) * 8)]; > + > + friend constexpr bool operator==(EightInBuf const& lhs, int rhs) > + { return lhs.elems[0] == rhs; } > +}; > + > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range>(std::allocator<int>()); > + do_test<Range>(__gnu_test::uneq_allocator<int>(42)); > + do_test<Range>(std::allocator<EightInBuf>()); > +} > + > +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..e46711cfcd6 > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/append_range.cc > @@ -0,0 +1,128 @@ > +// { 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,10,11,12,13,14}; > + > + 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; > + }; > + > + V const* p[std::size(a)]{}; > + auto stable = [](const std::deque<V, Alloc>& l, std::span<V const*> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + { > + if (r[i] == nullptr) > + r[i] = &l[i]; > + else if (&l[i] != r[i]) > + return false; > + } > + return true; > + }; > + > + std::deque<V, Alloc> d; > + d.append_range(Range(a, a)); > + VERIFY( d.empty() ); > + d.append_range(Range(a, a+4)); > + VERIFY( eq(d, {a, 4}) ); > + VERIFY( stable(d, {p, 4} ) ); > + d.append_range(Range(a+4, a+8)); > + VERIFY( eq(d, {a, 8}) ); > + VERIFY( stable(d, {p, 8}) ); > + d.append_range(Range(a+8, a+14)); > + VERIFY( eq(d, a) ); > + VERIFY( stable(d, p) ); > + > + d.clear(); > + std::ranges::fill(p, nullptr); > + d.append_range(Range(a, a+4)); > + VERIFY( eq(d, {a, 4}) ); > + VERIFY( stable(d, {p, 4} ) ); > + d.append_range(Range(a+4, a+14)); > + VERIFY( eq(d, a) ); > + VERIFY( stable(d, p) ); > + > + d.clear(); > + std::ranges::fill(p, nullptr); > + d.append_range(Range(a, a+14)); > + VERIFY( eq(d, a) ); > +} > + > +struct EightInBuf > +{ > + EightInBuf(int x) : elems{x} > + { } > + > +private: > + int elems[512 / (sizeof(int) * 8)]; > + > + friend constexpr bool operator==(EightInBuf const& lhs, int rhs) > + { return lhs.elems[0] == rhs; } > +}; > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<int>>(); > + do_test<Range, __gnu_test::SimpleAllocator<int>>(); > + do_test<Range, std::allocator<EightInBuf>>(); > +} > + > +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..75cd430f14f > --- /dev/null > +++ > b/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/insert_range.cc > @@ -0,0 +1,142 @@ > +// { 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,10,11,12,13,14}; > + > + 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; > + }; > + > + V const* p[std::size(a)]{}; > + auto stable = [](const std::deque<V, Alloc>& l, std::span<V const*> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + { > + if (r[i] == nullptr) > + r[i] = &l[i]; > + else 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+12, a+14)); > + VERIFY( eq(d, {a+12, 2}) ); > + VERIFY( stable(d, {p+12, 2}) ); > + d.insert_range(d.begin(), Range(a+8,a+12)); > + VERIFY( eq(d, {a+8, 6}) ); > + VERIFY( stable(d, {p+8, 6}) ); > + d.insert_range(d.begin(), Range(a, a+8)); > + VERIFY( eq(d, a) ); > + VERIFY( stable(d, p) ); > + > + d.clear(); > + std::ranges::fill(p, nullptr); > + 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}) ); > + VERIFY( stable(d, {p, 4} ) ); > + d.insert_range(d.end(), Range(a+4, a+14)); > + VERIFY( eq(d, a) ); > + VERIFY( stable(d, p) ); > + > + d.clear(); > + auto it = d.insert_range(d.begin(), Range(a, a+4)); > + VERIFY( it == d.begin() ); > + it = d.insert_range(d.end(), Range(a+8, a+14)); > + VERIFY( it == d.begin() + 4 ); > + it = d.insert_range(d.begin() + 4, Range(a+4, a+8)); > + VERIFY( it == d.begin() + 4 ); > + VERIFY( eq(d, a) ); > + > + d.clear(); > + it = d.insert_range(d.end(), Range(a+10, a+14)); > + VERIFY( it == d.begin() ); > + it = d.insert_range(d.begin(), Range(a, a+6)); > + VERIFY( it == d.begin() ); > + it = d.insert_range(d.begin() + 6, Range(a+6, a+10)); > + VERIFY( it == d.begin() + 6 ); > + VERIFY( eq(d, a) ); > +} > + > +struct EightInBuf > +{ > + EightInBuf(int x) : elems{x} > + { } > + > +private: > + int elems[512 / (sizeof(int) * 8)]; > + > + friend constexpr bool operator==(EightInBuf const& lhs, int rhs) > + { return lhs.elems[0] == rhs; } > +}; > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<int>>(); > + do_test<Range, __gnu_test::SimpleAllocator<int>>(); > + do_test<Range, std::allocator<EightInBuf>>(); > +} > + > +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..4258beec86e > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/prepend_range.cc > @@ -0,0 +1,140 @@ > +// { 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,10,11,12,13,14}; > + > + 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; > + }; > + > + V const* p[std::size(a)]{}; > + auto stable = [](const std::deque<V, Alloc>& l, std::span<V const*> r) { > + if (l.size() != r.size()) > + return false; > + for (auto i = 0u; i < l.size(); ++i) > + { > + if (r[i] == nullptr) > + r[i] = &l[i]; > + else if (&l[i] != r[i]) > + return false; > + } > + return true; > + }; > + > + std::deque<V, Alloc> d; > + d.prepend_range(Range(a, a)); > + VERIFY( d.empty() ); > + d.prepend_range(Range(a+8, a+14)); > + VERIFY( eq(d, {a+8, 6}) ); > + VERIFY( stable(d, {p+8, 6}) ); > + d.prepend_range(Range(a+4, a+8)); > + VERIFY( eq(d, {a+4, 10}) ); > + VERIFY( stable(d, {p+4, 10}) ); > + d.prepend_range(Range(a, a+4)); > + VERIFY( eq(d, a) ); > + VERIFY( stable(d, p) ); > + > + d.clear(); > + std::ranges::fill(p, nullptr); > + d.prepend_range(Range(a+12, a+14)); > + VERIFY( eq(d, {a+12, 2}) ); > + VERIFY( stable(d, {p+12, 2}) ); > + d.prepend_range(Range(a+8,a+12)); > + VERIFY( eq(d, {a+8, 6}) ); > + VERIFY( stable(d, {p+8, 6}) ); > + d.prepend_range(Range(a, a+8)); > + VERIFY( eq(d, a) ); > + VERIFY( stable(d, p) ); > + > + d.clear(); > + std::ranges::fill(p, nullptr); > + d.prepend_range(Range(a+12, a+14)); > + VERIFY( eq(d, {a+12, 2}) ); > + VERIFY( stable(d, {p+12, 2}) ); > + d.prepend_range(Range(a, a+12)); > + VERIFY( eq(d, a) ); > + VERIFY( stable(d, p) ); > + > + d.clear(); > + d.prepend_range(Range(a, a+14)); > + VERIFY( eq(d, a) ); > +} > + > +struct EightInBuf > +{ > + EightInBuf(int x) : elems{x} > + { } > + > +private: > + int elems[512 / (sizeof(int) * 8)]; > + > + friend constexpr bool operator==(EightInBuf const& lhs, int rhs) > + { return lhs.elems[0] == rhs; } > +}; > + > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<int>>(); > + do_test<Range, __gnu_test::SimpleAllocator<int>>(); > + do_test<Range, std::allocator<EightInBuf>>(); > +} > + > +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 >