[PATCH] libstdc++: Add P1206R7 range operations to std::deque [PR111055]
Tomasz Kamiński
tkaminsk@redhat.com
Fri Mar 21 10:10:40 GMT 2025
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
+{
+ 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
More information about the Libstdc++
mailing list