[PATCH v3] libstdc++: Add P1206R7 range operations to std::deque [PR111055]
Jonathan Wakely
jwakely@redhat.com
Tue Mar 25 14:58:32 GMT 2025
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
More information about the Libstdc++
mailing list