On 25/03/25 13:30 +0100, Tomasz Kamiński 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.

There should be two underscores at the start of _advance_dist.

        (deque::_M_range_prepend, deque::_M_range_append):
        Extract from _M_range_insert_aux for _ForwardIterator(s).
        * include/bits/stl_deque.h (deque::assing_range): Define.

Spelling "assign"

        (deque::prepend_range, deque::append_range, deque::insert_range):
        Declare.
        deque(from_range_t, _Rg&&, const allocator_type&): Define constructor

Missing parentheses around the function name:

        (deque(from_range_t, _Rg&&, const allocator_type&)): Define
        constructor and deduction guide.

        and deduction guide.
        * include/debug/deque (deque::prepend_range, deque::append_range),

No comma at the end of the line here.

        (assing_range): Define.

Spelling "assign" again.

        deque(from_range_t, _Rg&&, const allocator_type&): Define constructor

Missing parens again.

        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.
---
Expanded the documentetion comments. Tests for the stability of 
pointers/references
to existing elements, when inserting at front/end.

libstdc++-v3/include/bits/deque.tcc           | 229 +++++++++++++++---
libstdc++-v3/include/bits/stl_deque.h         | 110 +++++++++
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, 995 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..6de76ebc116 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 - begin();

Using cbegin() would be a tiny bit faster for unoptimized builds,
avoiding a conversion from iterator to const_iterator.

+       if constexpr (ranges::forward_range<_Rg>)
+         {
+           auto [__last, __n] = __advance_dist(__rg);
+           if (__builtin_expect(__n != 0, 1))

Since this is C++23 code, you can use the (IMHO more readable) likely
attribute:

            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));

Nice shortcut.

+        else 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
+          {
+            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);

Aha, so that's how to do prepend_range for input iterators!

+
+            __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 (__builtin_expect(__n != 0, 1))
+              _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..51faf6e7f89 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,52 @@ _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`.

We can add "@pre `__rg` and `*this` do not overlap." here.

+       * @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

Reply via email to