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::assing_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), (assing_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. --- Changes from last patch: * provide no-effects guarantee for append_range and prepend_range * implement reversing inline to avoid dependency on stl_algo * default prepend_range/insert_range to append_range if container is empty * remove gratuitous constexpr specifier on new operations * test with large enough value type to trigger allocations libstdc++-v3/include/bits/deque.tcc | 229 +++++++++++++++--- libstdc++-v3/include/bits/stl_deque.h | 103 ++++++++ libstdc++-v3/include/debug/deque | 51 ++++ .../23_containers/deque/cons/from_range.cc | 117 +++++++++ .../deque/modifiers/append_range.cc | 108 +++++++++ .../deque/modifiers/assign/assign_range.cc | 109 +++++++++ .../deque/modifiers/insert/insert_range.cc | 122 ++++++++++ .../deque/modifiers/prepend_range.cc | 116 +++++++++ 8 files changed, 924 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(); + if constexpr (ranges::forward_range<_Rg>) + { + auto [__last, __n] = __advance_dist(__rg); + if (__builtin_expect(__n != 0, 1)) + _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 (__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); + + __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..add345965ef 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,17 @@ _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> + 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 +1149,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 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 +1821,33 @@ _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> + 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> + void + prepend_range(_Rg&& __rg); + + /** + * @brief Append a range at the end of the deque. + * @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 +2122,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 +2377,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..6259f662dac --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/append_range.cc @@ -0,0 +1,108 @@ +// { 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; + }; + + + 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}) ); + d.append_range(Range(a+4, a+8)); + VERIFY( eq(d, {a, 8}) ); + d.append_range(Range(a+8, a+14)); + VERIFY( eq(d, a) ); + + d.clear(); + d.append_range(Range(a, a+4)); + VERIFY( eq(d, {a, 4}) ); + d.append_range(Range(a+4, a+14)); + VERIFY( eq(d, a) ); + + d.clear(); + 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..a5a46c190a5 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/insert_range.cc @@ -0,0 +1,122 @@ +// { 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; + }; + + 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}) ); + d.insert_range(d.begin(), Range(a+8,a+12)); + VERIFY( eq(d, {a+8, 6}) ); + d.insert_range(d.begin(), Range(a, a+8)); + VERIFY( eq(d, a) ); + + d.clear(); + 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.insert_range(d.end(), Range(a+4, a+14)); + VERIFY( eq(d, a) ); + + 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..ceecc7115c3 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/prepend_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,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> d; + d.prepend_range(Range(a, a)); + VERIFY( d.empty() ); + d.prepend_range(Range(a+8, a+14)); + VERIFY( eq(d, {a+8, 6}) ); + d.prepend_range(Range(a+4, a+8)); + VERIFY( eq(d, {a+4, 10}) ); + d.prepend_range(Range(a, a+4)); + VERIFY( eq(d, a) ); + + d.clear(); + d.prepend_range(Range(a+12, a+14)); + VERIFY( eq(d, {a+12, 2}) ); + d.prepend_range(Range(a+8,a+12)); + VERIFY( eq(d, {a+8, 6}) ); + d.prepend_range(Range(a, a+8)); + VERIFY( eq(d, a) ); + + d.clear(); + d.prepend_range(Range(a+12, a+14)); + VERIFY( eq(d, {a+12, 2}) ); + d.prepend_range(Range(a,a+12)); + VERIFY( eq(d, a) ); + + 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