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
>

Reply via email to