On Fri, 21 Mar 2025 at 14:31, Tomasz Kaminski <tkami...@redhat.com> wrote:
>
>
>
> 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.
In debug mode this is std::_GLIBCXX_STD_C::__detail and so it hides
std::__detail where the __container_compatible_range concept is
defined.
You should be able to fix it by using
std::_detail::__container_compatible_range later in this file, or you
could rename this __detail namespace to __deque, or just remove it.
>>
>> +{
>> + 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
>>
