| Message ID | 20241024145949.1450378-1-jwakely@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | libstdc++: Add P1206R7 from_range members to std::vector [PR111055] | expand |
On Thu, 24 Oct 2024 at 16:00, Jonathan Wakely <jwakely@redhat.com> wrote: > > This is another piece of P1206R7, adding new members to std::vector and > std::vector<bool>. > > The __uninitialized_copy_a extension needs to be enhanced to support > passing non-common ranges (i.e. a sentinel that is a different type from > the iterator) and move-only input iterators. I forgot to say that this patch is also available at https://forge.sourceware.org/gcc/gcc-TEST/pulls/5 > > libstdc++-v3/ChangeLog: > > PR libstdc++/111055 > * include/bits/ranges_base.h (__container_compatible_range): New > concept. > * include/bits/stl_bvector.h (vector(from_range, R&&, const Alloc&)) > (assign_range, insert_range, append_range): Define. > * include/bits/stl_uninitialized.h (__do_uninit_copy): Support > non-common ranges. > (__uninitialized_copy_a): Likewise. > * include/bits/stl_vector.h (_Vector_base::_M_append_range_to): > New function. > (_Vector_base::_M_append_range): Likewise. > (vector(from_range, R&&, const Alloc&), assign_range): Define. > (append_range): Define. > (insert_range): Declare. > * include/debug/vector (vector(from_range, R&&, const Alloc&)) > (assign_range, insert_range, append_range): Define. > * include/bits/vector.tcc (insert_range): Define. > * testsuite/23_containers/vector/bool/cons/from_range.cc: New test. > * testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc: > New test. > * testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc: > New test. > * testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc: > New test. > * testsuite/23_containers/vector/cons/from_range.cc: New test. > * testsuite/23_containers/vector/modifiers/append_range.cc: New test. > * testsuite/23_containers/vector/modifiers/assign/assign_range.cc: > New test. > * testsuite/23_containers/vector/modifiers/insert/insert_range.cc: > New test. > --- > Tested x86_64-linux. > > libstdc++-v3/include/bits/ranges_base.h | 10 ++ > libstdc++-v3/include/bits/stl_bvector.h | 120 +++++++++++++ > libstdc++-v3/include/bits/stl_uninitialized.h | 38 +++- > libstdc++-v3/include/bits/stl_vector.h | 166 ++++++++++++++++++ > libstdc++-v3/include/bits/vector.tcc | 124 +++++++++++++ > libstdc++-v3/include/debug/vector | 70 ++++++++ > .../vector/bool/cons/from_range.cc | 81 +++++++++ > .../bool/modifiers/assign/assign_range.cc | 96 ++++++++++ > .../bool/modifiers/insert/append_range.cc | 83 +++++++++ > .../bool/modifiers/insert/insert_range.cc | 94 ++++++++++ > .../23_containers/vector/cons/from_range.cc | 94 ++++++++++ > .../vector/modifiers/append_range.cc | 83 +++++++++ > .../vector/modifiers/assign/assign_range.cc | 107 +++++++++++ > .../vector/modifiers/insert/insert_range.cc | 94 ++++++++++ > 14 files changed, 1252 insertions(+), 8 deletions(-) > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc > create mode 100644 libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc > > diff --git a/libstdc++-v3/include/bits/ranges_base.h b/libstdc++-v3/include/bits/ranges_base.h > index cb2eba1f841..a2c743ff56b 100644 > --- a/libstdc++-v3/include/bits/ranges_base.h > +++ b/libstdc++-v3/include/bits/ranges_base.h > @@ -1079,6 +1079,16 @@ namespace ranges > #if __glibcxx_ranges_to_container // C++ >= 23 > struct from_range_t { explicit from_range_t() = default; }; > inline constexpr from_range_t from_range{}; > + > +/// @cond undocumented > +namespace __detail > +{ > + template<typename _Rg, typename _Tp> > + concept __container_compatible_range > + = ranges::input_range<_Rg> > + && convertible_to<ranges::range_reference_t<_Rg>, _Tp>; > +} > +/// @endcond > #endif > > _GLIBCXX_END_NAMESPACE_VERSION > diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h > index 42261ac5915..ebb5ff2c594 100644 > --- a/libstdc++-v3/include/bits/stl_bvector.h > +++ b/libstdc++-v3/include/bits/stl_bvector.h > @@ -892,6 +892,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Construct a vector from a range. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<bool> _Rg> > + constexpr > + vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) > + : _Base(__a) > + { > + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) > + { > + _M_initialize(size_type(ranges::distance(__rg))); > + ranges::copy(__rg, begin()); > + } > + else > + { > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + for (; __first != __last; ++__first) > + emplace_back(*__first); > + } > + } > +#endif > + > _GLIBCXX20_CONSTEXPR > ~vector() _GLIBCXX_NOEXCEPT { } > > @@ -996,6 +1021,21 @@ _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 vector. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<bool> _Rg> > + constexpr void > + assign_range(_Rg&& __rg) > + { > + static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>); > + clear(); > + append_range(std::forward<_Rg>(__rg)); > + } > +#endif > + > _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR > iterator > begin() _GLIBCXX_NOEXCEPT > @@ -1279,6 +1319,86 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > { return this->insert(__p, __l.begin(), __l.end()); } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Insert a range into the vector. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<bool> _Rg> > + constexpr iterator > + insert_range(const_iterator __pos, _Rg&& __rg) > + { > + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) > + { > + if (auto __n = size_type(ranges::distance(__rg))) > + { > + if (capacity() - size() >= __n) > + { > + std::copy_backward(__pos._M_const_cast(), end(), > + this->_M_impl._M_finish > + + difference_type(__n)); > + auto __i = ranges::copy(__rg, __pos._M_const_cast()).out; > + this->_M_impl._M_finish += difference_type(__n); > + return __i; > + } > + else > + { > + const size_type __len = > + _M_check_len(__n, "vector<bool>::insert_range"); > + const iterator __begin = begin(), __end = end(); > + _Bit_pointer __q = this->_M_allocate(__len); > + iterator __start(std::__addressof(*__q), 0); > + iterator __i = _M_copy_aligned(__begin, > + __pos._M_const_cast(), > + __start); > + __i = ranges::copy(__rg, __i).out; > + iterator __finish = std::copy(__pos._M_const_cast(), > + __end, __i); > + this->_M_deallocate(); > + this->_M_impl._M_end_of_storage = __q + _S_nword(__len); > + this->_M_impl._M_start = __start; > + this->_M_impl._M_finish = __finish; > + return __i; > + } > + } > + else > + return __pos._M_const_cast(); > + } > + else > + return insert_range(__pos, > + vector(from_range, __rg, get_allocator())); > + } > + > + /** > + * @brief Append a range at the end of the vector. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<bool> _Rg> > + constexpr void > + append_range(_Rg&& __rg) > + { > + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) > + { > + reserve(size() + size_type(ranges::distance(__rg))); > + this->_M_impl._M_finish = ranges::copy(__rg, end()).out; > + } > + else > + { > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + size_type __n = size(); > + const size_type __cap = capacity(); > + for (; __first != __last && __n < __cap; ++__first, (void)++__n) > + emplace_back(*__first); > + if (__first != __last) > + { > + ranges::subrange __rest(std::move(__first), __last); > + append_range(vector(from_range, __rest, get_allocator())); > + } > + } > + } > +#endif // ranges_to_container > + > _GLIBCXX20_CONSTEXPR > void > pop_back() > diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h > index de3e8cbeaf5..d5674fa9881 100644 > --- a/libstdc++-v3/include/bits/stl_uninitialized.h > +++ b/libstdc++-v3/include/bits/stl_uninitialized.h > @@ -132,10 +132,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > }; > > // This is the default implementation of std::uninitialized_copy. > - template<typename _InputIterator, typename _ForwardIterator> > + // This can be used with C++20 iterators and non-common ranges. > + template<typename _InputIterator, typename _Sentinel, > + typename _ForwardIterator> > _GLIBCXX20_CONSTEXPR > _ForwardIterator > - __do_uninit_copy(_InputIterator __first, _InputIterator __last, > + __do_uninit_copy(_InputIterator __first, _Sentinel __last, > _ForwardIterator __result) > { > _UninitDestroyGuard<_ForwardIterator> __guard(__result); > @@ -568,11 +570,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > // default allocator. For nondefault allocators we do not use > // any of the POD optimizations. > > - template<typename _InputIterator, typename _ForwardIterator, > - typename _Allocator> > + template<typename _InputIterator, typename _Sentinel, > + typename _ForwardIterator, typename _Allocator> > _GLIBCXX20_CONSTEXPR > _ForwardIterator > - __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, > + __uninitialized_copy_a(_InputIterator __first, _Sentinel __last, > _ForwardIterator __result, _Allocator& __alloc) > { > _UninitDestroyGuard<_ForwardIterator, _Allocator> > @@ -586,17 +588,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > } > > #if _GLIBCXX_HOSTED > - template<typename _InputIterator, typename _ForwardIterator, typename _Tp> > + template<typename _InputIterator, typename _Sentinel, > + typename _ForwardIterator, typename _Tp> > _GLIBCXX20_CONSTEXPR > inline _ForwardIterator > - __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, > + __uninitialized_copy_a(_InputIterator __first, _Sentinel __last, > _ForwardIterator __result, allocator<_Tp>&) > { > #ifdef __cpp_lib_is_constant_evaluated > if (std::is_constant_evaluated()) > - return std::__do_uninit_copy(__first, __last, __result); > + return std::__do_uninit_copy(std::move(__first), __last, __result); > #endif > + > +#ifdef __glibcxx_ranges > + if constexpr (!is_same_v<_InputIterator, _Sentinel>) > + { > + // Convert to a common range if possible, to benefit from memcpy > + // optimizations that std::uninitialized_copy might use. > + if constexpr (sized_sentinel_for<_Sentinel, _InputIterator> > + && random_access_iterator<_InputIterator>) > + return std::uninitialized_copy(__first, > + __first + (__last - __first), > + __result); > + else // Just use default implementation. > + return std::__do_uninit_copy(std::move(__first), __last, __result); > + } > + else > + return std::uninitialized_copy(std::move(__first), std::move(__last), > + __result); > +#else > return std::uninitialized_copy(__first, __last, __result); > +#endif > } > #endif > > diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h > index 8982ca2b9ee..fb97810acf8 100644 > --- a/libstdc++-v3/include/bits/stl_vector.h > +++ b/libstdc++-v3/include/bits/stl_vector.h > @@ -65,6 +65,10 @@ > #if __cplusplus >= 202002L > # 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> > > @@ -399,6 +403,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > this->_M_impl._M_finish = this->_M_impl._M_start; > this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; > } > + > +#if __glibcxx_ranges_to_container // C++ >= 23 > + // Called by insert_range, and indirectly by assign_range, append_range. > + // Initializes new elements in storage at __ptr and updates __ptr to > + // point after the last new element. > + // Provides strong exception safety guarantee. > + // Requires [ptr, ptr+distance(rg)) is a valid range. > + template<ranges::input_range _Rg> > + constexpr void > + _M_append_range_to(_Rg&& __rg, pointer& __ptr) > + { > + __ptr = std::__uninitialized_copy_a(ranges::begin(__rg), > + ranges::end(__rg), > + __ptr, _M_get_Tp_allocator()); > + } > + > + // Called by assign_range, append_range, insert_range. > + // Requires capacity() >= size()+distance(rg). > + template<ranges::input_range _Rg> > + constexpr void > + _M_append_range(_Rg&& __rg) > + { _M_append_range_to(std::forward<_Rg>(__rg), _M_impl._M_finish); } > +#endif > }; > > /** > @@ -723,6 +750,47 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Construct a vector from a range. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr > + vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) > + : _Base(__a) > + { > + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) > + { > + const auto __n = size_type(ranges::distance(__rg)); > + pointer __start = > + this->_M_allocate(_S_check_init_len(__n, > + _M_get_Tp_allocator())); > + _Guard_alloc __guard(__start, __n, *this); > + this->_M_impl._M_finish = this->_M_impl._M_start = __start; > + this->_M_impl._M_end_of_storage = __start + __n; > + _Base::_M_append_range(__rg); > + (void) __guard._M_release(); > + } > + else > + { > + // If an exception is thrown ~_Base() will deallocate storage, > + // but will not destroy elements. This RAII type destroys them. > + struct _Clear > + { > + ~_Clear() { if (_M_this) _M_this->clear(); } > + vector* _M_this; > + } __guard{this}; > + > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + for (; __first != __last; ++__first) > + emplace_back(*__first); > + __guard._M_this = nullptr; > + } > + } > +#endif > + > /** > * The dtor only erases the elements, and note that if the > * elements themselves are pointers, the pointed-to memory is > @@ -859,6 +927,62 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Assign a range to the vector. > + * @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, this->_M_impl._M_start); > + _M_erase_at_end(__res.out); > + return; > + } > + > + reserve(__n); > + auto __first = ranges::copy_n(ranges::begin(__rg), size(), > + this->_M_impl._M_start).in; > + [[maybe_unused]] const auto __diff = __n - size(); > + _GLIBCXX_ASAN_ANNOTATE_GROW(__diff); > + _Base::_M_append_range(ranges::subrange(std::move(__first), > + ranges::end(__rg))); > + _GLIBCXX_ASAN_ANNOTATE_GREW(__diff); > + } > + else // input_range<_Rg> > + { > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + pointer __ptr = this->_M_impl._M_start; > + pointer const __end = this->_M_impl._M_finish; > + > + while (__ptr < __end && __first != __last) > + { > + *__ptr = *__first; > + ++__ptr; > + ++__first; > + } > + > + if (__first == __last) > + _M_erase_at_end(__ptr); > + else > + { > + do > + emplace_back(*__first); > + while (++__first != __last); > + } > + } > + } > +#endif // ranges_to_container > + > /// Get a copy of the memory allocation object. > using _Base::get_allocator; > > @@ -1515,6 +1639,41 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > #endif > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Insert a range into the vector. > + * @since C++23 > + */ > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr iterator > + insert_range(const_iterator __pos, _Rg&& __rg); > + > + /** > + * @brief Append a range at the end of the vector. > + * @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 auto __n = size_type(ranges::distance(__rg)); > + reserve(size() + __n); > + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); > + _Base::_M_append_range(__rg); > + _GLIBCXX_ASAN_ANNOTATE_GREW(__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. > @@ -2049,6 +2208,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > typename = _RequireAllocator<_Allocator>> > vector(_InputIterator, _InputIterator, _Allocator = _Allocator()) > -> vector<_ValT, _Allocator>; > + > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<ranges::input_range _Rg, > + typename _Alloc = allocator<ranges::range_value_t<_Rg>>> > + vector(from_range_t, _Rg&&, _Alloc = _Alloc()) > + -> vector<ranges::range_value_t<_Rg>, _Alloc>; > +#endif > #endif > > /** > diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc > index a99a5b56b77..f9c050726dd 100644 > --- a/libstdc++-v3/include/bits/vector.tcc > +++ b/libstdc++-v3/include/bits/vector.tcc > @@ -974,6 +974,130 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER > } > } > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<typename _Tp, typename _Alloc> > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr auto > + vector<_Tp, _Alloc>:: > + insert_range(const_iterator __pos, _Rg&& __rg) > + -> iterator > + { > + if (__pos == cend()) > + { > + append_range(std::forward<_Rg>(__rg)); > + return end(); > + } > + > + auto __first = ranges::begin(__rg); > + const auto __last = ranges::end(__rg); > + > + if constexpr (ranges::forward_range<_Rg>) > + { > + // Start of existing elements: > + pointer __old_start = this->_M_impl._M_start; > + // End of existing elements: > + pointer __old_finish = this->_M_impl._M_finish; > + // Insertion point: > + const auto __ins_idx = __pos - cbegin(); > + pointer __ins = __old_start + __ins_idx; > + // Number of new elements to insert: > + const auto __n = size_type(ranges::distance(__rg)); > + // Number of elements that can fit in unused capacity: > + const auto __cap = this->_M_impl._M_end_of_storage - __old_finish; > + if (__cap >= __n) > + { > + // Number of existing elements after insertion point: > + const size_type __elems_after = cend() - __pos; > + if (__elems_after > __n) > + { > + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); > + std::__uninitialized_move_a(__old_finish - __n, > + __old_finish, > + __old_finish, > + _M_get_Tp_allocator()); > + this->_M_impl._M_finish += __n; > + _GLIBCXX_ASAN_ANNOTATE_GREW(__n); > + std::move_backward(__ins, __old_finish - __n, __old_finish); > + ranges::copy(__rg, __ins); > + } > + else > + { > + auto __mid = ranges::next(__first, __elems_after); > + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); > + _Base::_M_append_range(ranges::subrange(__mid, __last)); > + _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); > + std::__uninitialized_move_a(__ins, __old_finish, > + this->_M_impl._M_finish, > + _M_get_Tp_allocator()); > + this->_M_impl._M_finish += __elems_after; > + _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); > + ranges::copy(__first, __mid, __ins); > + } > + } > + else // Reallocate > + { > + const size_type __len > + = _M_check_len(__n, "vector::insert_range"); > + > + struct _Guard : _Guard_alloc > + { > + // End of elements to destroy: > + pointer _M_finish = _Guard_alloc::_M_storage; > + > + using _Guard_alloc::_Guard_alloc; > + > + constexpr > + ~_Guard() > + { > + std::_Destroy(this->_M_storage, _M_finish, > + this->_M_vect._M_get_Tp_allocator()); > + } > + }; > + > + // Allocate new storage: > + pointer __new_start(this->_M_allocate(__len)); > + _Guard __guard(__new_start, __len, *this); > + > + auto& __alloc = _M_get_Tp_allocator(); > + > + // Populate the new storage in three steps. After each step, > + // __guard owns the new storage and any elements that have > + // been constructed there. > + > + // Move elements from before insertion point to new storage: > + __guard._M_finish > + = std::__uninitialized_move_if_noexcept_a( > + __old_start, __ins, __new_start, __alloc); > + > + // Append new elements to new storage: > + _Base::_M_append_range_to(__rg, __guard._M_finish); > + > + // Move elements from after insertion point to new storage: > + __guard._M_finish > + = std::__uninitialized_move_if_noexcept_a( > + __ins, __old_finish, __guard._M_finish, __alloc); > + > + _GLIBCXX_ASAN_ANNOTATE_REINIT; // Creates _Asan::_Reinit. > + > + // All elements are in the new storage, exchange ownership > + // with __guard so that it cleans up the old storage: > + this->_M_impl._M_start = __guard._M_storage; > + this->_M_impl._M_finish = __guard._M_finish; > + this->_M_impl._M_end_of_storage = __new_start + __len; > + __guard._M_storage = __old_start; > + __guard._M_finish = __old_finish; > + __guard._M_len = (__old_finish - __old_start) + __cap; > + // _Asan::_Reinit destructor marks unused capacity. > + // _Guard destructor destroys [old_start,old_finish). > + // _Guard_alloc destructor frees [old_start,old_start+len). > + } > + return begin() + __ins_idx; > + } > + else > + return insert_range(__pos, vector(from_range, std::move(__rg), > + _M_get_Tp_allocator())); > + } > +#endif // ranges_to_container > > // vector<bool> > template<typename _Alloc> > diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector > index fe43a372485..f2ab4f73764 100644 > --- a/libstdc++-v3/include/debug/vector > +++ b/libstdc++-v3/include/debug/vector > @@ -244,6 +244,19 @@ namespace __debug > const allocator_type& __a = allocator_type()) > : _Base(__l, __a) { } > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + /** > + * @brief Construct a vector from a range. > + * @since C++23 > + */ > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + constexpr > + vector(std::from_range_t __t, _Rg&& __rg, > + const allocator_type& __a = allocator_type()) > + : _Base(__t, std::forward<_Rg>(__rg), __a) > + { } > +#endif > + > ~vector() = default; > #endif > > @@ -858,6 +871,56 @@ namespace __debug > const _Base& > _M_base() const _GLIBCXX_NOEXCEPT { return *this; } > > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<std::__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + assign_range(_Rg&& __rg) > + { > + auto __old_begin = _Base::begin(); > + auto __old_size = _Base::size(); > + _Base::assign_range(__rg); > + if (!std::__is_constant_evaluated()) > + { > + if (_Base::begin() != __old_begin) > + this->_M_invalidate_all(); > + else if (_Base::size() < __old_size) > + this->_M_invalidate_after_nth(_Base::size()); > + this->_M_update_guaranteed_capacity(); > + } > + } > + > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr iterator > + insert_range(const_iterator __pos, _Rg&& __rg) > + { > + auto __old_begin = _Base::begin(); > + auto __old_size = _Base::size(); > + auto __res = _Base::insert_range(__pos.base(), __rg); > + if (!std::__is_constant_evaluated()) > + { > + if (_Base::begin() != __old_begin) > + this->_M_invalidate_all(); > + this->_M_update_guaranteed_capacity(); > + } > + return iterator(__res, this); > + } > + > + template<__detail::__container_compatible_range<_Tp> _Rg> > + constexpr void > + append_range(_Rg&& __rg) > + { > + auto __old_begin = _Base::begin(); > + auto __old_size = _Base::size(); > + _Base::append_range(__rg); > + if (!std::__is_constant_evaluated()) > + { > + if (_Base::begin() != __old_begin) > + this->_M_invalidate_all(); > + this->_M_update_guaranteed_capacity(); > + } > + } > +#endif > + > private: > void > _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT > @@ -937,6 +1000,13 @@ namespace __debug > typename = _RequireAllocator<_Allocator>> > vector(size_t, _Tp, _Allocator = _Allocator()) > -> vector<_Tp, _Allocator>; > + > +#if __glibcxx_ranges_to_container // C++ >= 23 > + template<ranges::input_range _Rg, > + typename _Alloc = allocator<ranges::range_value_t<_Rg>>> > + vector(from_range_t, _Rg&&, _Alloc = _Alloc()) > + -> vector<ranges::range_value_t<_Rg>, _Alloc>; > +#endif > #endif > > } // namespace __debug > diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc > new file mode 100644 > index 00000000000..5836c36d0f3 > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc > @@ -0,0 +1,81 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test(Alloc alloc) > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,1,0,1,0,0,1,0,0}; > + > + auto eq = [](const std::vector<bool, 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::vector<bool, Alloc> v0(std::from_range, Range(a, a+0)); > + VERIFY( v0.empty() ); > + VERIFY( v0.get_allocator() == Alloc() ); > + > + std::vector<bool, Alloc> v4(std::from_range, Range(a, a+4)); > + VERIFY( eq(v4, {a, 4}) ); > + VERIFY( v4.get_allocator() == Alloc() ); > + > + std::vector<bool, Alloc> v9(std::from_range, Range(a, a+9), alloc); > + VERIFY( eq(v9, {a, 9}) ); > + VERIFY( v9.get_allocator() == alloc ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range>(std::allocator<bool>()); > + do_test<Range>(__gnu_test::uneq_allocator<bool>(42)); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<bool>>(); > + do_test_a<test_forward_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<bool>>(); > + do_test_a<test_input_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); > + > + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<bool>, std::allocator<bool>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc > new file mode 100644 > index 00000000000..22c3ce31851 > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc > @@ -0,0 +1,96 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,1,0,1,0,0,1,0,0}; > + > + auto eq = [](const std::vector<bool, 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 r9(a); > + > + std::vector<bool, Alloc> v; > + v.assign_range(Range(a, a)); > + VERIFY( v.empty() ); > + VERIFY( v.capacity() == 0 ); > + v.assign_range(r4); > + VERIFY( eq(v, {a, 4}) ); > + v.clear(); > + v.assign_range(r9); // larger than v.capacity() > + VERIFY( eq(v, a) ); > + v.assign_range(r9); // equal to size() and equal to capacity() > + VERIFY( eq(v, a) ); > + v.resize(1); > + v.assign_range(r4); // larger than size(), smaller than capacity() > + VERIFY( eq(v, {a, 4}) ); > + v.clear(); > + v.resize(4); > + v.assign_range(r4); // equal to size(), smaller than capacity() > + VERIFY( eq(v, {a, 4}) ); > + v.shrink_to_fit(); > + v.assign_range(r9); // larger than capacity() > + VERIFY( eq(v, a) ); > + v.assign_range(Range(a, a)); > + VERIFY( v.empty() ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<bool>>(); > + do_test<Range, __gnu_test::SimpleAllocator<bool>>(); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<bool>>(); > + do_test_a<test_forward_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<bool>>(); > + do_test_a<test_input_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); > + > + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<short>, std::allocator<bool>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc > new file mode 100644 > index 00000000000..13cbddda9df > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc > @@ -0,0 +1,83 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,1,0,1,0,0,1,0,0}; > + > + auto eq = [](const std::vector<bool, 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::vector<bool, Alloc> v; > + v.append_range(r4); > + VERIFY( eq(v, {a, 4}) ); > + v.append_range(r5); // larger than v.capacity() > + VERIFY( eq(v, a) ); > + v.append_range(Range(a, a)); > + VERIFY( eq(v, a) ); > + v.clear(); > + v.append_range(Range(a, a)); > + VERIFY( v.empty() ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<bool>>(); > + do_test<Range, __gnu_test::SimpleAllocator<bool>>(); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<bool>>(); > + do_test_a<test_forward_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<bool>>(); > + do_test_a<test_input_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); > + > + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<short>, std::allocator<bool>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc > new file mode 100644 > index 00000000000..4f530466efe > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc > @@ -0,0 +1,94 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,1,0,1,0,0,1,0,0}; > + > + auto eq = [](const std::vector<bool, 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::vector<bool, Alloc> v; > + v.insert_range(v.begin(), Range(a, a+0)); > + VERIFY( v.empty() ); > + VERIFY( v.capacity() == 0 ); > + v.insert_range(v.begin(), Range(a, a+4)); > + VERIFY( eq(v, {a, a+4}) ); > + v.clear(); > + v.insert_range(v.begin(), Range(a, a+5)); > + VERIFY( eq(v, {a+4, a+9}) ); > + v.insert_range(v.begin(), Range(a, a+4)); > + VERIFY( eq(v, a) ); > + v.clear(); > + v.shrink_to_fit(); > + v.insert_range(v.begin(), Range(a, a+3)); > + v.insert_range(v.end(), Range(a+6, a+9)); > + v.insert_range(v.begin()+3, Range(a+3, a+6)); > + VERIFY( eq(v, a) ); > + v.resize(3); > + v.insert_range(v.begin()+1, Range(a+4, a+9)); > + v.insert_range(v.begin()+1, Range(a+1, a+3)); > + v.resize(9); > + VERIFY( eq(v, a) ); > + v.insert_range(v.begin(), Range(a, a)); > + VERIFY( eq(v, a) ); > +} > + > +template<typename Range> > +void > +do_test_a() > +{ > + do_test<Range, std::allocator<bool>>(); > + do_test<Range, __gnu_test::SimpleAllocator<bool>>(); > +} > + > +bool > +test_ranges() > +{ > + using namespace __gnu_test; > + > + do_test_a<test_forward_range<bool>>(); > + do_test_a<test_forward_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); > + > + do_test_a<test_input_range<bool>>(); > + do_test_a<test_input_sized_range<bool>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); > + > + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); > + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); > + > + do_test_a<test_forward_range<short>>(); > + do_test_a<test_input_range<short>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<bool>, std::allocator<bool>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > diff --git a/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc > new file mode 100644 > index 00000000000..9c06e185b3f > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc > @@ -0,0 +1,94 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#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::vector v(std::from_range, r); > + static_assert(std::is_same_v<decltype(v), std::vector<long>>); > + > + using Alloc = __gnu_test::SimpleAllocator<long>; > + Alloc alloc; > + std::vector v2(std::from_range, r, alloc); > + static_assert(std::is_same_v<decltype(v2), std::vector<long, Alloc>>); > +} > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test(Alloc alloc) > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::vector<int, 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::vector<int, Alloc> v0(std::from_range, Range(a, a+0)); > + VERIFY( v0.empty() ); > + VERIFY( v0.get_allocator() == Alloc() ); > + > + std::vector<int, Alloc> v4(std::from_range, Range(a, a+4)); > + VERIFY( eq(v4, {a, 4}) ); > + VERIFY( v4.get_allocator() == Alloc() ); > + > + std::vector<int, Alloc> v9(std::from_range, Range(a, a+9), alloc); > + VERIFY( eq(v9, {a, 9}) ); > + VERIFY( v9.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<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>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<short>, std::allocator<int>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc > new file mode 100644 > index 00000000000..6faa7a4d198 > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc > @@ -0,0 +1,83 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::vector<int, 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::vector<int, Alloc> v; > + v.append_range(r4); > + VERIFY( eq(v, {a, 4}) ); > + v.append_range(r5); // larger than v.capacity() > + VERIFY( eq(v, a) ); > + v.append_range(Range(a, a)); > + VERIFY( eq(v, a) ); > + v.clear(); > + v.append_range(Range(a, a)); > + VERIFY( v.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<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>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<short>, std::allocator<int>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc > new file mode 100644 > index 00000000000..e28c883a1fa > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc > @@ -0,0 +1,107 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::vector<int, 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 r9(a); > + > + // assign to empty vector > + std::vector<int, Alloc> v; > + v.assign_range(Range(a, a)); > + VERIFY( v.empty() ); > + VERIFY( v.capacity() == 0 ); > + v.assign_range(r4); > + VERIFY( eq(v, {a, 4}) ); > + v.clear(); > + v.assign_range(r9); // larger than v.capacity() > + VERIFY( eq(v, a) ); > + v.clear(); > + v.assign_range(r4); // smaller than v.capacity() > + VERIFY( eq(v, {a, 4}) ); > + v.clear(); > + v.assign_range(r9); // equal to v.capacity() > + VERIFY( eq(v, a) ); > + > + // assign to non-empty vector > + v.assign_range(r4); // smaller than size() > + VERIFY( eq(v, {a, 4}) ); > + v.assign_range(r9); // larger than size(), equal to capacity() > + VERIFY( eq(v, a) ); > + v.resize(1); > + v.assign_range(r4); // larger than size(), smaller than capacity() > + VERIFY( eq(v, {a, 4}) ); > + v.clear(); > + v.resize(4); > + v.assign_range(r4); // equal to size(), smaller than capacity() > + VERIFY( eq(v, {a, 4}) ); > + v.shrink_to_fit(); > + v.assign_range(r9); // larger than capacity() > + VERIFY( eq(v, a) ); > + v.assign_range(Range(a, a)); > + VERIFY( v.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<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>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<short>, std::allocator<int>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc > new file mode 100644 > index 00000000000..b81ce6971bb > --- /dev/null > +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc > @@ -0,0 +1,94 @@ > +// { dg-do compile { target c++23 } } > + > +#include <vector> > +#include <span> > +#include <testsuite_hooks.h> > +#include <testsuite_iterators.h> > +#include <testsuite_allocator.h> > + > +template<typename Range, typename Alloc> > +constexpr void > +do_test() > +{ > + using T = std::ranges::range_value_t<Range>; > + T a[]{1,2,3,4,5,6,7,8,9}; > + > + auto eq = [](const std::vector<int, 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::vector<int, Alloc> v; > + v.insert_range(v.begin(), Range(a, a)); > + VERIFY( v.empty() ); > + VERIFY( v.capacity() == 0 ); > + v.insert_range(v.begin(), Range(a, a+4)); > + VERIFY( eq(v, {a, a+4}) ); > + v.clear(); > + v.insert_range(v.begin(), Range(a, a+5)); > + VERIFY( eq(v, {a+4, a+9}) ); > + v.insert_range(v.begin(), Range(a, a+4)); > + VERIFY( eq(v, a) ); > + v.clear(); > + v.shrink_to_fit(); > + v.insert_range(v.begin(), Range(a, a+3)); > + v.insert_range(v.end(), Range(a+6, a+9)); > + v.insert_range(v.begin()+3, Range(a+3, a+6)); > + VERIFY( eq(v, a) ); > + v.resize(3); > + v.insert_range(v.begin()+1, Range(a+4, a+9)); > + v.insert_range(v.begin()+1, Range(a+1, a+3)); > + v.resize(9); > + VERIFY( eq(v, a) ); > + v.insert_range(v.begin() + 6, Range(a, a)); > + VERIFY( eq(v, 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<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>>(); > + > + return true; > +} > + > +constexpr bool > +test_constexpr() > +{ > + // XXX: this doesn't test the non-forward_range code paths are constexpr. > + do_test<std::span<short>, std::allocator<int>>; > + return true; > +} > + > +int main() > +{ > + test_ranges(); > + static_assert( test_constexpr() ); > +} > -- > 2.47.0 >
diff --git a/libstdc++-v3/include/bits/ranges_base.h b/libstdc++-v3/include/bits/ranges_base.h index cb2eba1f841..a2c743ff56b 100644 --- a/libstdc++-v3/include/bits/ranges_base.h +++ b/libstdc++-v3/include/bits/ranges_base.h @@ -1079,6 +1079,16 @@ namespace ranges #if __glibcxx_ranges_to_container // C++ >= 23 struct from_range_t { explicit from_range_t() = default; }; inline constexpr from_range_t from_range{}; + +/// @cond undocumented +namespace __detail +{ + template<typename _Rg, typename _Tp> + concept __container_compatible_range + = ranges::input_range<_Rg> + && convertible_to<ranges::range_reference_t<_Rg>, _Tp>; +} +/// @endcond #endif _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 42261ac5915..ebb5ff2c594 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -892,6 +892,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Construct a vector from a range. + * @since C++23 + */ + template<__detail::__container_compatible_range<bool> _Rg> + constexpr + vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) + : _Base(__a) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + _M_initialize(size_type(ranges::distance(__rg))); + ranges::copy(__rg, begin()); + } + else + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + for (; __first != __last; ++__first) + emplace_back(*__first); + } + } +#endif + _GLIBCXX20_CONSTEXPR ~vector() _GLIBCXX_NOEXCEPT { } @@ -996,6 +1021,21 @@ _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 vector. + * @since C++23 + */ + template<__detail::__container_compatible_range<bool> _Rg> + constexpr void + assign_range(_Rg&& __rg) + { + static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>); + clear(); + append_range(std::forward<_Rg>(__rg)); + } +#endif + _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR iterator begin() _GLIBCXX_NOEXCEPT @@ -1279,6 +1319,86 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { return this->insert(__p, __l.begin(), __l.end()); } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Insert a range into the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range<bool> _Rg> + constexpr iterator + insert_range(const_iterator __pos, _Rg&& __rg) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + if (auto __n = size_type(ranges::distance(__rg))) + { + if (capacity() - size() >= __n) + { + std::copy_backward(__pos._M_const_cast(), end(), + this->_M_impl._M_finish + + difference_type(__n)); + auto __i = ranges::copy(__rg, __pos._M_const_cast()).out; + this->_M_impl._M_finish += difference_type(__n); + return __i; + } + else + { + const size_type __len = + _M_check_len(__n, "vector<bool>::insert_range"); + const iterator __begin = begin(), __end = end(); + _Bit_pointer __q = this->_M_allocate(__len); + iterator __start(std::__addressof(*__q), 0); + iterator __i = _M_copy_aligned(__begin, + __pos._M_const_cast(), + __start); + __i = ranges::copy(__rg, __i).out; + iterator __finish = std::copy(__pos._M_const_cast(), + __end, __i); + this->_M_deallocate(); + this->_M_impl._M_end_of_storage = __q + _S_nword(__len); + this->_M_impl._M_start = __start; + this->_M_impl._M_finish = __finish; + return __i; + } + } + else + return __pos._M_const_cast(); + } + else + return insert_range(__pos, + vector(from_range, __rg, get_allocator())); + } + + /** + * @brief Append a range at the end of the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range<bool> _Rg> + constexpr void + append_range(_Rg&& __rg) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + reserve(size() + size_type(ranges::distance(__rg))); + this->_M_impl._M_finish = ranges::copy(__rg, end()).out; + } + else + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + size_type __n = size(); + const size_type __cap = capacity(); + for (; __first != __last && __n < __cap; ++__first, (void)++__n) + emplace_back(*__first); + if (__first != __last) + { + ranges::subrange __rest(std::move(__first), __last); + append_range(vector(from_range, __rest, get_allocator())); + } + } + } +#endif // ranges_to_container + _GLIBCXX20_CONSTEXPR void pop_back() diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h index de3e8cbeaf5..d5674fa9881 100644 --- a/libstdc++-v3/include/bits/stl_uninitialized.h +++ b/libstdc++-v3/include/bits/stl_uninitialized.h @@ -132,10 +132,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION }; // This is the default implementation of std::uninitialized_copy. - template<typename _InputIterator, typename _ForwardIterator> + // This can be used with C++20 iterators and non-common ranges. + template<typename _InputIterator, typename _Sentinel, + typename _ForwardIterator> _GLIBCXX20_CONSTEXPR _ForwardIterator - __do_uninit_copy(_InputIterator __first, _InputIterator __last, + __do_uninit_copy(_InputIterator __first, _Sentinel __last, _ForwardIterator __result) { _UninitDestroyGuard<_ForwardIterator> __guard(__result); @@ -568,11 +570,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // default allocator. For nondefault allocators we do not use // any of the POD optimizations. - template<typename _InputIterator, typename _ForwardIterator, - typename _Allocator> + template<typename _InputIterator, typename _Sentinel, + typename _ForwardIterator, typename _Allocator> _GLIBCXX20_CONSTEXPR _ForwardIterator - __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, + __uninitialized_copy_a(_InputIterator __first, _Sentinel __last, _ForwardIterator __result, _Allocator& __alloc) { _UninitDestroyGuard<_ForwardIterator, _Allocator> @@ -586,17 +588,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } #if _GLIBCXX_HOSTED - template<typename _InputIterator, typename _ForwardIterator, typename _Tp> + template<typename _InputIterator, typename _Sentinel, + typename _ForwardIterator, typename _Tp> _GLIBCXX20_CONSTEXPR inline _ForwardIterator - __uninitialized_copy_a(_InputIterator __first, _InputIterator __last, + __uninitialized_copy_a(_InputIterator __first, _Sentinel __last, _ForwardIterator __result, allocator<_Tp>&) { #ifdef __cpp_lib_is_constant_evaluated if (std::is_constant_evaluated()) - return std::__do_uninit_copy(__first, __last, __result); + return std::__do_uninit_copy(std::move(__first), __last, __result); #endif + +#ifdef __glibcxx_ranges + if constexpr (!is_same_v<_InputIterator, _Sentinel>) + { + // Convert to a common range if possible, to benefit from memcpy + // optimizations that std::uninitialized_copy might use. + if constexpr (sized_sentinel_for<_Sentinel, _InputIterator> + && random_access_iterator<_InputIterator>) + return std::uninitialized_copy(__first, + __first + (__last - __first), + __result); + else // Just use default implementation. + return std::__do_uninit_copy(std::move(__first), __last, __result); + } + else + return std::uninitialized_copy(std::move(__first), std::move(__last), + __result); +#else return std::uninitialized_copy(__first, __last, __result); +#endif } #endif diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index 8982ca2b9ee..fb97810acf8 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -65,6 +65,10 @@ #if __cplusplus >= 202002L # 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> @@ -399,6 +403,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER this->_M_impl._M_finish = this->_M_impl._M_start; this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; } + +#if __glibcxx_ranges_to_container // C++ >= 23 + // Called by insert_range, and indirectly by assign_range, append_range. + // Initializes new elements in storage at __ptr and updates __ptr to + // point after the last new element. + // Provides strong exception safety guarantee. + // Requires [ptr, ptr+distance(rg)) is a valid range. + template<ranges::input_range _Rg> + constexpr void + _M_append_range_to(_Rg&& __rg, pointer& __ptr) + { + __ptr = std::__uninitialized_copy_a(ranges::begin(__rg), + ranges::end(__rg), + __ptr, _M_get_Tp_allocator()); + } + + // Called by assign_range, append_range, insert_range. + // Requires capacity() >= size()+distance(rg). + template<ranges::input_range _Rg> + constexpr void + _M_append_range(_Rg&& __rg) + { _M_append_range_to(std::forward<_Rg>(__rg), _M_impl._M_finish); } +#endif }; /** @@ -723,6 +750,47 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Construct a vector from a range. + * @since C++23 + */ + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr + vector(from_range_t, _Rg&& __rg, const _Alloc& __a = _Alloc()) + : _Base(__a) + { + if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>) + { + const auto __n = size_type(ranges::distance(__rg)); + pointer __start = + this->_M_allocate(_S_check_init_len(__n, + _M_get_Tp_allocator())); + _Guard_alloc __guard(__start, __n, *this); + this->_M_impl._M_finish = this->_M_impl._M_start = __start; + this->_M_impl._M_end_of_storage = __start + __n; + _Base::_M_append_range(__rg); + (void) __guard._M_release(); + } + else + { + // If an exception is thrown ~_Base() will deallocate storage, + // but will not destroy elements. This RAII type destroys them. + struct _Clear + { + ~_Clear() { if (_M_this) _M_this->clear(); } + vector* _M_this; + } __guard{this}; + + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + for (; __first != __last; ++__first) + emplace_back(*__first); + __guard._M_this = nullptr; + } + } +#endif + /** * The dtor only erases the elements, and note that if the * elements themselves are pointers, the pointed-to memory is @@ -859,6 +927,62 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Assign a range to the vector. + * @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, this->_M_impl._M_start); + _M_erase_at_end(__res.out); + return; + } + + reserve(__n); + auto __first = ranges::copy_n(ranges::begin(__rg), size(), + this->_M_impl._M_start).in; + [[maybe_unused]] const auto __diff = __n - size(); + _GLIBCXX_ASAN_ANNOTATE_GROW(__diff); + _Base::_M_append_range(ranges::subrange(std::move(__first), + ranges::end(__rg))); + _GLIBCXX_ASAN_ANNOTATE_GREW(__diff); + } + else // input_range<_Rg> + { + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + pointer __ptr = this->_M_impl._M_start; + pointer const __end = this->_M_impl._M_finish; + + while (__ptr < __end && __first != __last) + { + *__ptr = *__first; + ++__ptr; + ++__first; + } + + if (__first == __last) + _M_erase_at_end(__ptr); + else + { + do + emplace_back(*__first); + while (++__first != __last); + } + } + } +#endif // ranges_to_container + /// Get a copy of the memory allocation object. using _Base::get_allocator; @@ -1515,6 +1639,41 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } #endif +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Insert a range into the vector. + * @since C++23 + */ + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr iterator + insert_range(const_iterator __pos, _Rg&& __rg); + + /** + * @brief Append a range at the end of the vector. + * @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 auto __n = size_type(ranges::distance(__rg)); + reserve(size() + __n); + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); + _Base::_M_append_range(__rg); + _GLIBCXX_ASAN_ANNOTATE_GREW(__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. @@ -2049,6 +2208,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typename = _RequireAllocator<_Allocator>> vector(_InputIterator, _InputIterator, _Allocator = _Allocator()) -> vector<_ValT, _Allocator>; + +#if __glibcxx_ranges_to_container // C++ >= 23 + template<ranges::input_range _Rg, + typename _Alloc = allocator<ranges::range_value_t<_Rg>>> + vector(from_range_t, _Rg&&, _Alloc = _Alloc()) + -> vector<ranges::range_value_t<_Rg>, _Alloc>; +#endif #endif /** diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc index a99a5b56b77..f9c050726dd 100644 --- a/libstdc++-v3/include/bits/vector.tcc +++ b/libstdc++-v3/include/bits/vector.tcc @@ -974,6 +974,130 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } } +#if __glibcxx_ranges_to_container // C++ >= 23 + template<typename _Tp, typename _Alloc> + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr auto + vector<_Tp, _Alloc>:: + insert_range(const_iterator __pos, _Rg&& __rg) + -> iterator + { + if (__pos == cend()) + { + append_range(std::forward<_Rg>(__rg)); + return end(); + } + + auto __first = ranges::begin(__rg); + const auto __last = ranges::end(__rg); + + if constexpr (ranges::forward_range<_Rg>) + { + // Start of existing elements: + pointer __old_start = this->_M_impl._M_start; + // End of existing elements: + pointer __old_finish = this->_M_impl._M_finish; + // Insertion point: + const auto __ins_idx = __pos - cbegin(); + pointer __ins = __old_start + __ins_idx; + // Number of new elements to insert: + const auto __n = size_type(ranges::distance(__rg)); + // Number of elements that can fit in unused capacity: + const auto __cap = this->_M_impl._M_end_of_storage - __old_finish; + if (__cap >= __n) + { + // Number of existing elements after insertion point: + const size_type __elems_after = cend() - __pos; + if (__elems_after > __n) + { + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); + std::__uninitialized_move_a(__old_finish - __n, + __old_finish, + __old_finish, + _M_get_Tp_allocator()); + this->_M_impl._M_finish += __n; + _GLIBCXX_ASAN_ANNOTATE_GREW(__n); + std::move_backward(__ins, __old_finish - __n, __old_finish); + ranges::copy(__rg, __ins); + } + else + { + auto __mid = ranges::next(__first, __elems_after); + _GLIBCXX_ASAN_ANNOTATE_GROW(__n); + _Base::_M_append_range(ranges::subrange(__mid, __last)); + _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); + std::__uninitialized_move_a(__ins, __old_finish, + this->_M_impl._M_finish, + _M_get_Tp_allocator()); + this->_M_impl._M_finish += __elems_after; + _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); + ranges::copy(__first, __mid, __ins); + } + } + else // Reallocate + { + const size_type __len + = _M_check_len(__n, "vector::insert_range"); + + struct _Guard : _Guard_alloc + { + // End of elements to destroy: + pointer _M_finish = _Guard_alloc::_M_storage; + + using _Guard_alloc::_Guard_alloc; + + constexpr + ~_Guard() + { + std::_Destroy(this->_M_storage, _M_finish, + this->_M_vect._M_get_Tp_allocator()); + } + }; + + // Allocate new storage: + pointer __new_start(this->_M_allocate(__len)); + _Guard __guard(__new_start, __len, *this); + + auto& __alloc = _M_get_Tp_allocator(); + + // Populate the new storage in three steps. After each step, + // __guard owns the new storage and any elements that have + // been constructed there. + + // Move elements from before insertion point to new storage: + __guard._M_finish + = std::__uninitialized_move_if_noexcept_a( + __old_start, __ins, __new_start, __alloc); + + // Append new elements to new storage: + _Base::_M_append_range_to(__rg, __guard._M_finish); + + // Move elements from after insertion point to new storage: + __guard._M_finish + = std::__uninitialized_move_if_noexcept_a( + __ins, __old_finish, __guard._M_finish, __alloc); + + _GLIBCXX_ASAN_ANNOTATE_REINIT; // Creates _Asan::_Reinit. + + // All elements are in the new storage, exchange ownership + // with __guard so that it cleans up the old storage: + this->_M_impl._M_start = __guard._M_storage; + this->_M_impl._M_finish = __guard._M_finish; + this->_M_impl._M_end_of_storage = __new_start + __len; + __guard._M_storage = __old_start; + __guard._M_finish = __old_finish; + __guard._M_len = (__old_finish - __old_start) + __cap; + // _Asan::_Reinit destructor marks unused capacity. + // _Guard destructor destroys [old_start,old_finish). + // _Guard_alloc destructor frees [old_start,old_start+len). + } + return begin() + __ins_idx; + } + else + return insert_range(__pos, vector(from_range, std::move(__rg), + _M_get_Tp_allocator())); + } +#endif // ranges_to_container // vector<bool> template<typename _Alloc> diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index fe43a372485..f2ab4f73764 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -244,6 +244,19 @@ namespace __debug const allocator_type& __a = allocator_type()) : _Base(__l, __a) { } +#if __glibcxx_ranges_to_container // C++ >= 23 + /** + * @brief Construct a vector from a range. + * @since C++23 + */ + template<std::__detail::__container_compatible_range<_Tp> _Rg> + constexpr + vector(std::from_range_t __t, _Rg&& __rg, + const allocator_type& __a = allocator_type()) + : _Base(__t, std::forward<_Rg>(__rg), __a) + { } +#endif + ~vector() = default; #endif @@ -858,6 +871,56 @@ namespace __debug const _Base& _M_base() const _GLIBCXX_NOEXCEPT { return *this; } +#if __glibcxx_ranges_to_container // C++ >= 23 + template<std::__detail::__container_compatible_range<_Tp> _Rg> + constexpr void + assign_range(_Rg&& __rg) + { + auto __old_begin = _Base::begin(); + auto __old_size = _Base::size(); + _Base::assign_range(__rg); + if (!std::__is_constant_evaluated()) + { + if (_Base::begin() != __old_begin) + this->_M_invalidate_all(); + else if (_Base::size() < __old_size) + this->_M_invalidate_after_nth(_Base::size()); + this->_M_update_guaranteed_capacity(); + } + } + + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr iterator + insert_range(const_iterator __pos, _Rg&& __rg) + { + auto __old_begin = _Base::begin(); + auto __old_size = _Base::size(); + auto __res = _Base::insert_range(__pos.base(), __rg); + if (!std::__is_constant_evaluated()) + { + if (_Base::begin() != __old_begin) + this->_M_invalidate_all(); + this->_M_update_guaranteed_capacity(); + } + return iterator(__res, this); + } + + template<__detail::__container_compatible_range<_Tp> _Rg> + constexpr void + append_range(_Rg&& __rg) + { + auto __old_begin = _Base::begin(); + auto __old_size = _Base::size(); + _Base::append_range(__rg); + if (!std::__is_constant_evaluated()) + { + if (_Base::begin() != __old_begin) + this->_M_invalidate_all(); + this->_M_update_guaranteed_capacity(); + } + } +#endif + private: void _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT @@ -937,6 +1000,13 @@ namespace __debug typename = _RequireAllocator<_Allocator>> vector(size_t, _Tp, _Allocator = _Allocator()) -> vector<_Tp, _Allocator>; + +#if __glibcxx_ranges_to_container // C++ >= 23 + template<ranges::input_range _Rg, + typename _Alloc = allocator<ranges::range_value_t<_Rg>>> + vector(from_range_t, _Rg&&, _Alloc = _Alloc()) + -> vector<ranges::range_value_t<_Rg>, _Alloc>; +#endif #endif } // namespace __debug diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc new file mode 100644 index 00000000000..5836c36d0f3 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/from_range.cc @@ -0,0 +1,81 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#include <span> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <testsuite_allocator.h> + +template<typename Range, typename Alloc> +constexpr void +do_test(Alloc alloc) +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector<bool, 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::vector<bool, Alloc> v0(std::from_range, Range(a, a+0)); + VERIFY( v0.empty() ); + VERIFY( v0.get_allocator() == Alloc() ); + + std::vector<bool, Alloc> v4(std::from_range, Range(a, a+4)); + VERIFY( eq(v4, {a, 4}) ); + VERIFY( v4.get_allocator() == Alloc() ); + + std::vector<bool, Alloc> v9(std::from_range, Range(a, a+9), alloc); + VERIFY( eq(v9, {a, 9}) ); + VERIFY( v9.get_allocator() == alloc ); +} + +template<typename Range> +void +do_test_a() +{ + do_test<Range>(std::allocator<bool>()); + do_test<Range>(__gnu_test::uneq_allocator<bool>(42)); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a<test_forward_range<bool>>(); + do_test_a<test_forward_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); + + do_test_a<test_input_range<bool>>(); + do_test_a<test_input_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); + + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); + + do_test_a<test_forward_range<short>>(); + do_test_a<test_input_range<short>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<bool>, std::allocator<bool>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc new file mode 100644 index 00000000000..22c3ce31851 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/assign/assign_range.cc @@ -0,0 +1,96 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#include <span> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <testsuite_allocator.h> + +template<typename Range, typename Alloc> +constexpr void +do_test() +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector<bool, 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 r9(a); + + std::vector<bool, Alloc> v; + v.assign_range(Range(a, a)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.assign_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.assign_range(r9); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.assign_range(r9); // equal to size() and equal to capacity() + VERIFY( eq(v, a) ); + v.resize(1); + v.assign_range(r4); // larger than size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.resize(4); + v.assign_range(r4); // equal to size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.shrink_to_fit(); + v.assign_range(r9); // larger than capacity() + VERIFY( eq(v, a) ); + v.assign_range(Range(a, a)); + VERIFY( v.empty() ); +} + +template<typename Range> +void +do_test_a() +{ + do_test<Range, std::allocator<bool>>(); + do_test<Range, __gnu_test::SimpleAllocator<bool>>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a<test_forward_range<bool>>(); + do_test_a<test_forward_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); + + do_test_a<test_input_range<bool>>(); + do_test_a<test_input_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); + + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); + + do_test_a<test_forward_range<short>>(); + do_test_a<test_input_range<short>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<short>, std::allocator<bool>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc new file mode 100644 index 00000000000..13cbddda9df --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc @@ -0,0 +1,83 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#include <span> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <testsuite_allocator.h> + +template<typename Range, typename Alloc> +constexpr void +do_test() +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector<bool, 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::vector<bool, Alloc> v; + v.append_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.append_range(r5); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.append_range(Range(a, a)); + VERIFY( eq(v, a) ); + v.clear(); + v.append_range(Range(a, a)); + VERIFY( v.empty() ); +} + +template<typename Range> +void +do_test_a() +{ + do_test<Range, std::allocator<bool>>(); + do_test<Range, __gnu_test::SimpleAllocator<bool>>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a<test_forward_range<bool>>(); + do_test_a<test_forward_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); + + do_test_a<test_input_range<bool>>(); + do_test_a<test_input_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); + + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); + + do_test_a<test_forward_range<short>>(); + do_test_a<test_input_range<short>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<short>, std::allocator<bool>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc new file mode 100644 index 00000000000..4f530466efe --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/insert_range.cc @@ -0,0 +1,94 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#include <span> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <testsuite_allocator.h> + +template<typename Range, typename Alloc> +constexpr void +do_test() +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,1,0,1,0,0,1,0,0}; + + auto eq = [](const std::vector<bool, 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::vector<bool, Alloc> v; + v.insert_range(v.begin(), Range(a, a+0)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, {a, a+4}) ); + v.clear(); + v.insert_range(v.begin(), Range(a, a+5)); + VERIFY( eq(v, {a+4, a+9}) ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, a) ); + v.clear(); + v.shrink_to_fit(); + v.insert_range(v.begin(), Range(a, a+3)); + v.insert_range(v.end(), Range(a+6, a+9)); + v.insert_range(v.begin()+3, Range(a+3, a+6)); + VERIFY( eq(v, a) ); + v.resize(3); + v.insert_range(v.begin()+1, Range(a+4, a+9)); + v.insert_range(v.begin()+1, Range(a+1, a+3)); + v.resize(9); + VERIFY( eq(v, a) ); + v.insert_range(v.begin(), Range(a, a)); + VERIFY( eq(v, a) ); +} + +template<typename Range> +void +do_test_a() +{ + do_test<Range, std::allocator<bool>>(); + do_test<Range, __gnu_test::SimpleAllocator<bool>>(); +} + +bool +test_ranges() +{ + using namespace __gnu_test; + + do_test_a<test_forward_range<bool>>(); + do_test_a<test_forward_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, forward_iterator_wrapper>>(); + + do_test_a<test_input_range<bool>>(); + do_test_a<test_input_sized_range<bool>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper>>(); + + do_test_a<test_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range<bool, input_iterator_wrapper_nocopy>>(); + do_test_a<test_sized_range_sized_sent<bool, input_iterator_wrapper_nocopy>>(); + + do_test_a<test_forward_range<short>>(); + do_test_a<test_input_range<short>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<bool>, std::allocator<bool>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc b/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc new file mode 100644 index 00000000000..9c06e185b3f --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/cons/from_range.cc @@ -0,0 +1,94 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#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::vector v(std::from_range, r); + static_assert(std::is_same_v<decltype(v), std::vector<long>>); + + using Alloc = __gnu_test::SimpleAllocator<long>; + Alloc alloc; + std::vector v2(std::from_range, r, alloc); + static_assert(std::is_same_v<decltype(v2), std::vector<long, Alloc>>); +} + +template<typename Range, typename Alloc> +constexpr void +do_test(Alloc alloc) +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector<int, 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::vector<int, Alloc> v0(std::from_range, Range(a, a+0)); + VERIFY( v0.empty() ); + VERIFY( v0.get_allocator() == Alloc() ); + + std::vector<int, Alloc> v4(std::from_range, Range(a, a+4)); + VERIFY( eq(v4, {a, 4}) ); + VERIFY( v4.get_allocator() == Alloc() ); + + std::vector<int, Alloc> v9(std::from_range, Range(a, a+9), alloc); + VERIFY( eq(v9, {a, 9}) ); + VERIFY( v9.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<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>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<short>, std::allocator<int>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc new file mode 100644 index 00000000000..6faa7a4d198 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc @@ -0,0 +1,83 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#include <span> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <testsuite_allocator.h> + +template<typename Range, typename Alloc> +constexpr void +do_test() +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector<int, 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::vector<int, Alloc> v; + v.append_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.append_range(r5); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.append_range(Range(a, a)); + VERIFY( eq(v, a) ); + v.clear(); + v.append_range(Range(a, a)); + VERIFY( v.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<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>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<short>, std::allocator<int>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc new file mode 100644 index 00000000000..e28c883a1fa --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/assign/assign_range.cc @@ -0,0 +1,107 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#include <span> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <testsuite_allocator.h> + +template<typename Range, typename Alloc> +constexpr void +do_test() +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector<int, 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 r9(a); + + // assign to empty vector + std::vector<int, Alloc> v; + v.assign_range(Range(a, a)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.assign_range(r4); + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.assign_range(r9); // larger than v.capacity() + VERIFY( eq(v, a) ); + v.clear(); + v.assign_range(r4); // smaller than v.capacity() + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.assign_range(r9); // equal to v.capacity() + VERIFY( eq(v, a) ); + + // assign to non-empty vector + v.assign_range(r4); // smaller than size() + VERIFY( eq(v, {a, 4}) ); + v.assign_range(r9); // larger than size(), equal to capacity() + VERIFY( eq(v, a) ); + v.resize(1); + v.assign_range(r4); // larger than size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.clear(); + v.resize(4); + v.assign_range(r4); // equal to size(), smaller than capacity() + VERIFY( eq(v, {a, 4}) ); + v.shrink_to_fit(); + v.assign_range(r9); // larger than capacity() + VERIFY( eq(v, a) ); + v.assign_range(Range(a, a)); + VERIFY( v.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<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>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<short>, std::allocator<int>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +} diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc new file mode 100644 index 00000000000..b81ce6971bb --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/insert_range.cc @@ -0,0 +1,94 @@ +// { dg-do compile { target c++23 } } + +#include <vector> +#include <span> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <testsuite_allocator.h> + +template<typename Range, typename Alloc> +constexpr void +do_test() +{ + using T = std::ranges::range_value_t<Range>; + T a[]{1,2,3,4,5,6,7,8,9}; + + auto eq = [](const std::vector<int, 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::vector<int, Alloc> v; + v.insert_range(v.begin(), Range(a, a)); + VERIFY( v.empty() ); + VERIFY( v.capacity() == 0 ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, {a, a+4}) ); + v.clear(); + v.insert_range(v.begin(), Range(a, a+5)); + VERIFY( eq(v, {a+4, a+9}) ); + v.insert_range(v.begin(), Range(a, a+4)); + VERIFY( eq(v, a) ); + v.clear(); + v.shrink_to_fit(); + v.insert_range(v.begin(), Range(a, a+3)); + v.insert_range(v.end(), Range(a+6, a+9)); + v.insert_range(v.begin()+3, Range(a+3, a+6)); + VERIFY( eq(v, a) ); + v.resize(3); + v.insert_range(v.begin()+1, Range(a+4, a+9)); + v.insert_range(v.begin()+1, Range(a+1, a+3)); + v.resize(9); + VERIFY( eq(v, a) ); + v.insert_range(v.begin() + 6, Range(a, a)); + VERIFY( eq(v, 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<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>>(); + + return true; +} + +constexpr bool +test_constexpr() +{ + // XXX: this doesn't test the non-forward_range code paths are constexpr. + do_test<std::span<short>, std::allocator<int>>; + return true; +} + +int main() +{ + test_ranges(); + static_assert( test_constexpr() ); +}