diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -37,6 +37,7 @@ Implemented Papers ------------------ +- P1206R7 - ``ranges::to``: A function to convert any range to a container - P2520R0 - ``move_iterator`` should be a random access iterator - P1328R1 - ``constexpr type_info::operator==()`` - P1413R3 - Formatting ``thread::id`` (the ``stacktrace`` is not done yet) diff --git a/libcxx/docs/Status/Cxx2bPapers.csv b/libcxx/docs/Status/Cxx2bPapers.csv --- a/libcxx/docs/Status/Cxx2bPapers.csv +++ b/libcxx/docs/Status/Cxx2bPapers.csv @@ -41,7 +41,7 @@ "`P0323R12 `__","LWG","``std::expected``","February 2022","|Complete|","16.0" "`P0533R9 `__","LWG","``constexpr`` for ```` and ````","February 2022","|In progress| [#note-P0533R9]_","" "`P0627R6 `__","LWG","Function to mark unreachable code","February 2022","|Complete|","15.0" -"`P1206R7 `__","LWG","``ranges::to``: A function to convert any range to a container","February 2022","|Partial|","17.0","|ranges|" +"`P1206R7 `__","LWG","``ranges::to``: A function to convert any range to a container","February 2022","|Complete|","17.0","|ranges|" "`P1413R3 `__","LWG","Deprecate ``std::aligned_storage`` and ``std::aligned_union``","February 2022","|Complete| [#note-P1413R3]_","" "`P2255R2 `__","LWG","A type trait to detect reference binding to temporary","February 2022","","" "`P2273R3 `__","LWG","Making ``std::unique_ptr`` constexpr","February 2022","|Complete|","16.0" diff --git a/libcxx/docs/Status/RangesMajorFeatures.csv b/libcxx/docs/Status/RangesMajorFeatures.csv --- a/libcxx/docs/Status/RangesMajorFeatures.csv +++ b/libcxx/docs/Status/RangesMajorFeatures.csv @@ -1,4 +1,4 @@ Standard,Name,Assignee,CL,Status -C++23,`ranges::to `_,Konstantin Varlamov,`D142335 `_,Partial +C++23,`ranges::to `_,Konstantin Varlamov,`D142335 `_,Complete C++23,`Pipe support for user-defined range adaptors `_,Unassigned,No patch yet,Not started C++23,`Formatting Ranges `_,Mark de Wever,Various,Complete diff --git a/libcxx/include/__split_buffer b/libcxx/include/__split_buffer --- a/libcxx/include/__split_buffer +++ b/libcxx/include/__split_buffer @@ -170,6 +170,14 @@ __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value> __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __construct_at_end_with_size(_Iterator __first, size_type __n); + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin) { __destruct_at_begin(__new_begin, is_trivially_destructible()); } @@ -279,6 +287,13 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 __enable_if_t<__is_exactly_cpp17_input_iterator<_InputIter>::value> __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) { + __construct_at_end_with_sentinel(__first, __last); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 +void __split_buffer<_Tp, _Allocator>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) { __alloc_rr& __a = this->__alloc(); for (; __first != __last; ++__first) { @@ -296,13 +311,19 @@ ++this->__end_; } } - template template _LIBCPP_CONSTEXPR_SINCE_CXX20 __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value> __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) { - _ConstructTransaction __tx(&this->__end_, _VSTD::distance(__first, __last)); + __construct_at_end_with_size(__first, std::distance(__first, __last)); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 +void __split_buffer<_Tp, _Allocator>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) { + _ConstructTransaction __tx(&this->__end_, __n); for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void) ++__first) { __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_), *__first); diff --git a/libcxx/include/deque b/libcxx/include/deque --- a/libcxx/include/deque +++ b/libcxx/include/deque @@ -66,6 +66,8 @@ template void assign(InputIterator f, InputIterator l); + template R> + void assign_range(R&& rg); // C++23 void assign(size_type n, const value_type& v); void assign(initializer_list il); @@ -109,8 +111,12 @@ // modifiers: void push_front(const value_type& v); void push_front(value_type&& v); + template R> + void prepend_range(R&& rg); // C++23 void push_back(const value_type& v); void push_back(value_type&& v); + template R> + void append_range(R&& rg); // C++23 template reference emplace_front(Args&&... args); // reference in C++17 template reference emplace_back(Args&&... args); // reference in C++17 template iterator emplace(const_iterator p, Args&&... args); @@ -119,6 +125,8 @@ iterator insert(const_iterator p, size_type n, const value_type& v); template iterator insert(const_iterator p, InputIterator f, InputIterator l); + template R> + iterator insert_range(const_iterator position, R&& rg); // C++23 iterator insert(const_iterator p, initializer_list il); void pop_front(); void pop_back(); @@ -173,6 +181,7 @@ #include <__algorithm/copy_backward.h> #include <__algorithm/equal.h> #include <__algorithm/fill_n.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/lexicographical_compare.h> #include <__algorithm/lexicographical_compare_three_way.h> #include <__algorithm/min.h> @@ -651,6 +660,21 @@ template _LIBCPP_HIDE_FROM_ABI void assign(_RAIter __f, _RAIter __l, typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void assign_range(_Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + __assign_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +#endif + _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v); _LIBCPP_HIDE_FROM_ABI @@ -760,6 +784,21 @@ _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __v); _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __v); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void prepend_range(_Range&& __range) { + insert_range(begin(), std::forward<_Range>(__range)); + } + + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void append_range(_Range&& __range) { + insert_range(end(), std::forward<_Range>(__range)); + } +#endif + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v); _LIBCPP_HIDE_FROM_ABI @@ -778,6 +817,24 @@ _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _BiIter __f, _BiIter __l, typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + iterator insert_range(const_iterator __position, _Range&& __range) { + if constexpr (ranges::bidirectional_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + return __insert_bidirectional(__position, ranges::begin(__range), ranges::end(__range), __n); + + } else if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + return __insert_with_size(__position, ranges::begin(__range), __n); + + } else { + return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } + } +#endif + _LIBCPP_HIDE_FROM_ABI void pop_front(); _LIBCPP_HIDE_FROM_ABI void pop_back(); _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p); @@ -910,6 +967,26 @@ return false; } + template + _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __f, _Sentinel __l); + + template + _LIBCPP_HIDE_FROM_ABI + void __assign_with_size(_Iterator __f, _Sentinel __l, difference_type __n); + + template + _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l); + + template + _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_size(const_iterator __p, _Iterator __f, size_type __n); + + template + _LIBCPP_HIDE_FROM_ABI + iterator __insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel __sent, size_type __n); + template _LIBCPP_HIDE_FROM_ABI void __append(_InpIter __f, _InpIter __l, typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type* = 0); @@ -933,6 +1010,16 @@ } } + template + _LIBCPP_HIDE_FROM_ABI void __append_with_sentinel(_InputIterator __f, _Sentinel __l) { + for (; __f != __l; ++__f) +#ifdef _LIBCPP_CXX03_LANG + push_back(*__f); +#else + emplace_back(*__f); +#endif + } + _LIBCPP_HIDE_FROM_ABI void __append(size_type __n); _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const value_type& __v); _LIBCPP_HIDE_FROM_ABI void __erase_to_end(const_iterator __f); @@ -1170,12 +1257,19 @@ typename enable_if<__is_cpp17_input_iterator<_InputIter>::value && !__is_cpp17_random_access_iterator<_InputIter>::value>::type*) { + __assign_with_sentinel(__f, __l); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +void deque<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) { iterator __i = begin(); iterator __e = end(); for (; __f != __l && __i != __e; ++__f, (void) ++__i) *__i = *__f; if (__f != __l) - __append(__f, __l); + __append_with_sentinel(std::move(__f), std::move(__l)); else __erase_to_end(__i); } @@ -1186,14 +1280,21 @@ deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l, typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*) { - if (static_cast(__l - __f) > size()) + __assign_with_size(__f, __l, __l - __f); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +void deque<_Tp, _Allocator>::__assign_with_size(_Iterator __f, _Sentinel __l, difference_type __n) { + if (static_cast(__n) > size()) { - _RAIter __m = __f + size(); - _VSTD::copy(__f, __m, begin()); - __append(__m, __l); + _Iterator __m = std::next(__f, size()); // TODO(varconst): NEEDS DISCUSSION + std::__copy<_ClassicAlgPolicy>(__f, __m, begin()); + __append_with_size(__m, __n - size()); } else - __erase_to_end(_VSTD::copy(__f, __l, begin())); + __erase_to_end(std::__copy<_ClassicAlgPolicy>(__f, __l, begin()).second); } template @@ -1671,8 +1772,16 @@ deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l, typename enable_if<__is_exactly_cpp17_input_iterator<_InputIter>::value>::type*) { + return __insert_with_sentinel(__p, __f, __l); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) { __split_buffer __buf(__alloc()); - __buf.__construct_at_end(__f, __l); + __buf.__construct_at_end_with_sentinel(std::move(__f), std::move(__l)); typedef typename __split_buffer::iterator __bi; return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); } @@ -1683,9 +1792,16 @@ deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, typename enable_if<__is_exactly_cpp17_forward_iterator<_ForwardIterator>::value>::type*) { - size_type __n = _VSTD::distance(__f, __l); + return __insert_with_size(__p, __f, std::distance(__f, __l)); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_with_size(const_iterator __p, _Iterator __f, size_type __n) { __split_buffer __buf(__n, 0, __alloc()); - __buf.__construct_at_end(__f, __l); + __buf.__construct_at_end_with_size(__f, __n); typedef typename __split_buffer::iterator __fwd; return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end())); } @@ -1696,7 +1812,15 @@ deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l, typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type*) { - size_type __n = _VSTD::distance(__f, __l); + return __insert_bidirectional(__p, __f, __l, std::distance(__f, __l)); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _Sentinel __sent, size_type __n) { + auto __l = std::ranges::next(__f, __sent); size_type __pos = __p - begin(); size_type __to_end = size() - __pos; allocator_type& __a = __alloc(); @@ -1765,12 +1889,7 @@ deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type*) { - for (; __f != __l; ++__f) -#ifdef _LIBCPP_CXX03_LANG - push_back(*__f); -#else - emplace_back(*__f); -#endif + __append_with_sentinel(__f, __l); } template diff --git a/libcxx/include/forward_list b/libcxx/include/forward_list --- a/libcxx/include/forward_list +++ b/libcxx/include/forward_list @@ -65,6 +65,8 @@ template void assign(InputIterator first, InputIterator last); + template R> + void assign_range(R&& rg); // C++23 void assign(size_type n, const value_type& v); void assign(initializer_list il); @@ -91,6 +93,8 @@ template reference emplace_front(Args&&... args); // reference in C++17 void push_front(const value_type& v); void push_front(value_type&& v); + template R> + void prepend_range(R&& rg); // C++23 void pop_front(); @@ -102,6 +106,8 @@ template iterator insert_after(const_iterator p, InputIterator first, InputIterator last); + template R> + iterator insert_range_after(const_iterator position, R&& rg); // C++23 iterator insert_after(const_iterator p, initializer_list il); iterator erase_after(const_iterator p); @@ -729,7 +735,7 @@ template <_ContainerCompatibleRange<_Tp> _Range> _LIBCPP_HIDE_FROM_ABI forward_list(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) : base(__a) { - __insert_range_after(cbefore_begin(), std::forward<_Range>(__range)); + insert_range_after(cbefore_begin(), std::forward<_Range>(__range)); } #endif @@ -766,6 +772,15 @@ template __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void> assign(_InputIterator __f, _InputIterator __l); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void assign_range(_Range&& __range) { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } +#endif + void assign(size_type __n, const value_type& __v); _LIBCPP_INLINE_VISIBILITY @@ -827,6 +842,14 @@ #endif // _LIBCPP_CXX03_LANG void push_front(const value_type& __v); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void prepend_range(_Range&& __range) { + insert_range_after(cbefore_begin(), std::forward<_Range>(__range)); + } +#endif + void pop_front(); #ifndef _LIBCPP_CXX03_LANG @@ -844,9 +867,17 @@ __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, iterator> insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + iterator insert_range_after(const_iterator __position, _Range&& __range) { + return __insert_after_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } +#endif + template _LIBCPP_HIDE_FROM_ABI - iterator __insert_after(const_iterator __p, _InputIterator __f, _Sentinel __l) { + iterator __insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) { __begin_node_pointer __r = __p.__get_begin(); if (__f != __l) { @@ -885,14 +916,6 @@ return iterator(__r); } -#if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. - template <_ContainerCompatibleRange<_Tp> _Range> - iterator __insert_range_after(const_iterator __position, _Range&& __range) { - return __insert_after(__position, ranges::begin(__range), ranges::end(__range)); - } -#endif - iterator erase_after(const_iterator __p); iterator erase_after(const_iterator __f, const_iterator __l); @@ -951,6 +974,10 @@ void __move_assign(forward_list& __x, false_type); #endif // _LIBCPP_CXX03_LANG + template + _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iter __f, _Sent __l); + template static __node_pointer @@ -1170,13 +1197,20 @@ __enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void> forward_list<_Tp, _Alloc>::assign(_InputIterator __f, _InputIterator __l) { + __assign_with_sentinel(__f, __l); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +void forward_list<_Tp, _Alloc>::__assign_with_sentinel(_Iter __f, _Sent __l) { iterator __i = before_begin(); iterator __j = _VSTD::next(__i); iterator __e = end(); for (; __j != __e && __f != __l; ++__i, (void) ++__j, ++__f) *__j = *__f; if (__j == __e) - insert_after(__i, __f, __l); + __insert_after_with_sentinel(__i, std::move(__f), std::move(__l)); else erase_after(__i, __e); } @@ -1363,7 +1397,7 @@ forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) { - return __insert_after(__p, std::move(__f), std::move(__l)); + return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l)); } template diff --git a/libcxx/include/list b/libcxx/include/list --- a/libcxx/include/list +++ b/libcxx/include/list @@ -66,6 +66,8 @@ list& operator=(initializer_list); template void assign(Iter first, Iter last); + template R> + void assign_range(R&& rg); // C++23 void assign(size_type n, const value_type& t); void assign(initializer_list); @@ -101,8 +103,12 @@ void pop_back(); void push_front(const value_type& x); void push_front(value_type&& x); + template R> + void prepend_range(R&& rg); // C++23 void push_back(const value_type& x); void push_back(value_type&& x); + template R> + void append_range(R&& rg); // C++23 template iterator emplace(const_iterator position, Args&&... args); iterator insert(const_iterator position, const value_type& x); @@ -110,6 +116,8 @@ iterator insert(const_iterator position, size_type n, const value_type& x); template iterator insert(const_iterator position, Iter first, Iter last); + template R> + iterator insert_range(const_iterator position, R&& rg); // C++23 iterator insert(const_iterator position, initializer_list il); iterator erase(const_iterator position); @@ -937,6 +945,15 @@ template void assign(_InpIter __f, _InpIter __l, __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void assign_range(_Range&& __range) { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } +#endif + void assign(size_type __n, const value_type& __x); _LIBCPP_INLINE_VISIBILITY @@ -1015,6 +1032,20 @@ void push_front(value_type&& __x); void push_back(value_type&& __x); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void prepend_range(_Range&& __range) { + insert_range(begin(), std::forward<_Range>(__range)); + } + + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void append_range(_Range&& __range) { + insert_range(end(), std::forward<_Range>(__range)); + } +#endif + template #if _LIBCPP_STD_VER >= 17 reference emplace_front(_Args&&... __args); @@ -1055,6 +1086,14 @@ iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>* = 0); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + iterator insert_range(const_iterator __position, _Range&& __range) { + return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } +#endif + _LIBCPP_INLINE_VISIBILITY void swap(list& __c) #if _LIBCPP_STD_VER >= 14 @@ -1139,6 +1178,12 @@ #endif // _LIBCPP_ENABLE_DEBUG_MODE private: + template + void __assign_with_sentinel(_Iterator __f, _Sentinel __l); + + template + iterator __insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l); + _LIBCPP_INLINE_VISIBILITY static void __link_nodes (__link_pointer __p, __link_pointer __f, __link_pointer __l); _LIBCPP_INLINE_VISIBILITY @@ -1397,12 +1442,18 @@ list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, __enable_if_t<__is_cpp17_input_iterator<_InpIter>::value>*) { + __assign_with_sentinel(__f, __l); +} + +template +template +void list<_Tp, _Alloc>::__assign_with_sentinel(_Iterator __f, _Sentinel __l) { iterator __i = begin(); iterator __e = end(); for (; __f != __l && __i != __e; ++__f, (void) ++__i) *__i = *__f; if (__i == __e) - insert(__e, __f, __l); + __insert_with_sentinel(__e, std::move(__f), std::move(__l)); else erase(__i, __e); std::__debug_db_invalidate_all(this); @@ -1504,6 +1555,14 @@ { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, "list::insert(iterator, range) called with an iterator not referring to this list"); + + return __insert_with_sentinel(__p, __f, __l); +} + +template +template +typename list<_Tp, _Alloc>::iterator +list<_Tp, _Alloc>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) { iterator __r(__p.__ptr_, this); if (__f != __l) { diff --git a/libcxx/include/map b/libcxx/include/map --- a/libcxx/include/map +++ b/libcxx/include/map @@ -143,6 +143,8 @@ iterator insert(const_iterator position, P&& p); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list il); node_type extract(const_iterator position); // C++17 @@ -420,6 +422,8 @@ iterator insert(const_iterator position, P&& p); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list il); node_type extract(const_iterator position); // C++17 @@ -1335,10 +1339,9 @@ } #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { const_iterator __end = cend(); for (auto&& __element : __range) { insert(__end.__i_, std::forward(__element)); @@ -2170,10 +2173,9 @@ } #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { const_iterator __end = cend(); for (auto&& __element : __range) { __tree_.__insert_multi(__end.__i_, std::forward(__element)); diff --git a/libcxx/include/queue b/libcxx/include/queue --- a/libcxx/include/queue +++ b/libcxx/include/queue @@ -69,6 +69,8 @@ void push(const value_type& v); void push(value_type&& v); + template R> + void push_range(R&& rg); // C++23 template reference emplace(Args&&... args); // reference in C++17 void pop(); @@ -187,6 +189,8 @@ void push(const value_type& v); void push(value_type&& v); + template R> + void push_range(R&& rg); // C++23 template void emplace(Args&&... args); void pop(); @@ -249,9 +253,11 @@ #include <__algorithm/make_heap.h> #include <__algorithm/pop_heap.h> #include <__algorithm/push_heap.h> +#include <__algorithm/ranges_copy.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__config> #include <__functional/operations.h> +#include <__iterator/back_insert_iterator.h> #include <__iterator/iterator_traits.h> #include <__memory/uses_allocator.h> #include <__ranges/access.h> @@ -405,6 +411,21 @@ #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void push_range(_Range&& __range) { + if constexpr (requires (container_type& __c) { + __c.append_range(std::forward<_Range>(__range)); + }) { + c.append_range(std::forward<_Range>(__range)); + } else { + ranges::copy(std::forward<_Range>(__range), std::back_inserter(c)); + } + } +#endif + template _LIBCPP_INLINE_VISIBILITY #if _LIBCPP_STD_VER >= 17 @@ -713,6 +734,21 @@ #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY void push(value_type&& __v); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void push_range(_Range&& __range) { + if constexpr (requires (container_type& __c) { + __c.append_range(std::forward<_Range>(__range)); + }) { + c.append_range(std::forward<_Range>(__range)); + } else { + ranges::copy(std::forward<_Range>(__range), std::back_inserter(c)); + } + } +#endif + template _LIBCPP_INLINE_VISIBILITY void emplace(_Args&&... __args); diff --git a/libcxx/include/set b/libcxx/include/set --- a/libcxx/include/set +++ b/libcxx/include/set @@ -119,6 +119,8 @@ iterator insert(const_iterator position, value_type&& v); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list il); node_type extract(const_iterator position); // C++17 @@ -358,6 +360,8 @@ iterator insert(const_iterator position, value_type&& v); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list il); node_type extract(const_iterator position); // C++17 @@ -793,10 +797,9 @@ } #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { const_iterator __end = cend(); for (auto&& __element : __range) { __tree_.__insert_unique(__end, std::forward(__element)); @@ -1372,10 +1375,9 @@ } #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { const_iterator __end = cend(); for (auto&& __element : __range) { __tree_.__insert_multi(__end, std::forward(__element)); diff --git a/libcxx/include/stack b/libcxx/include/stack --- a/libcxx/include/stack +++ b/libcxx/include/stack @@ -60,6 +60,8 @@ void push(const value_type& x); void push(value_type&& x); + template R> + void push_range(R&& rg); // C++23 template reference emplace(Args&&... args); // reference in C++17 void pop(); @@ -108,8 +110,10 @@ */ +#include <__algorithm/ranges_copy.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__config> +#include <__iterator/back_insert_iterator.h> #include <__iterator/iterator_traits.h> #include <__memory/uses_allocator.h> #include <__ranges/access.h> @@ -259,6 +263,20 @@ _LIBCPP_INLINE_VISIBILITY void push(value_type&& __v) {c.push_back(_VSTD::move(__v));} +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + void push_range(_Range&& __range) { + if constexpr (requires (container_type& __c) { + __c.append_range(std::forward<_Range>(__range)); + }) { + c.append_range(std::forward<_Range>(__range)); + } else { + ranges::copy(std::forward<_Range>(__range), std::back_inserter(c)); + } + } +#endif + template _LIBCPP_INLINE_VISIBILITY #if _LIBCPP_STD_VER >= 17 diff --git a/libcxx/include/string b/libcxx/include/string --- a/libcxx/include/string +++ b/libcxx/include/string @@ -202,6 +202,8 @@ basic_string& append(size_type n, value_type c); // constexpr since C++20 template basic_string& append(InputIterator first, InputIterator last); // constexpr since C++20 + template R> + constexpr basic_string& append_range(R&& rg); // C++23 basic_string& append(initializer_list); // constexpr since C++20 void push_back(value_type c); // constexpr since C++20 @@ -223,6 +225,8 @@ basic_string& assign(size_type n, value_type c); // constexpr since C++20 template basic_string& assign(InputIterator first, InputIterator last); // constexpr since C++20 + template R> + constexpr basic_string& assign_range(R&& rg); // C++23 basic_string& assign(initializer_list); // constexpr since C++20 basic_string& insert(size_type pos1, const basic_string& str); // constexpr since C++20 @@ -239,6 +243,8 @@ iterator insert(const_iterator p, size_type n, value_type c); // constexpr since C++20 template iterator insert(const_iterator p, InputIterator first, InputIterator last); // constexpr since C++20 + template R> + constexpr iterator insert_range(const_iterator p, R&& rg); // C++23 iterator insert(const_iterator p, initializer_list); // constexpr since C++20 basic_string& erase(size_type pos = 0, size_type n = npos); // constexpr since C++20 @@ -264,6 +270,8 @@ basic_string& replace(const_iterator i1, const_iterator i2, size_type n, value_type c); // constexpr since C++20 template basic_string& replace(const_iterator i1, const_iterator i2, InputIterator j1, InputIterator j2); // constexpr since C++20 + template R> + constexpr basic_string& replace_with_range(const_iterator i1, const_iterator i2, R&& rg); // C++23 basic_string& replace(const_iterator i1, const_iterator i2, initializer_list); // constexpr since C++20 size_type copy(value_type* s, size_type n, size_type pos = 0) const; // constexpr since C++20 @@ -687,6 +695,8 @@ struct __uninitialized_size_tag {}; +struct __init_with_sentinel_tag {}; + template class basic_string { @@ -847,6 +857,14 @@ std::__debug_db_insert_c(this); } + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 + basic_string(__init_with_sentinel_tag, _Iter __first, _Sent __last, const allocator_type& __a) + : __r_(__default_init_tag(), __a) { + __init_with_sentinel(__first, __last); + std::__debug_db_insert_c(this); + } + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __make_iterator(pointer __p) { return iterator(this, __p); } @@ -1301,6 +1319,14 @@ _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& append(_ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_CharT> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr basic_string& append_range(_Range&& __range) { + return append(basic_string(from_range, std::forward<_Range>(__range), get_allocator())); + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& append(initializer_list __il) {return append(__il.begin(), __il.size());} @@ -1364,6 +1390,24 @@ _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& assign(_ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_CharT> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr basic_string& assign_range(_Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + size_type __n = __string_is_trivial_iterator>::value ? + static_cast(ranges::distance(__range)) : 0; + __assign_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + basic_string __temp(from_range, std::forward<_Range>(__range), __alloc()); + assign(__temp.data(), __temp.size()); + } + + return *this; + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& assign(initializer_list __il) {return assign(__il.begin(), __il.size());} @@ -1395,6 +1439,21 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& insert(size_type __pos, size_type __n, value_type __c); _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __pos, value_type __c); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_CharT> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr iterator insert_range(const_iterator __position, _Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n); + + } else { + basic_string __temp(from_range, std::forward<_Range>(__range), __alloc()); + return insert(__position, __temp.data(), __temp.data() + __temp.size()); + } + } +#endif + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __pos, size_type __n, value_type __c) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this, @@ -1483,6 +1542,15 @@ _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& replace(const_iterator __i1, const_iterator __i2, _InputIterator __j1, _InputIterator __j2); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_CharT> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr basic_string& replace_with_range(const_iterator __i1, const_iterator __i2, _Range&& __range) { + basic_string __temp(from_range, std::forward<_Range>(__range), __alloc()); + return replace(__i1, __i2, __temp); + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string& replace(const_iterator __i1, const_iterator __i2, initializer_list __il) @@ -1741,9 +1809,17 @@ return !__libcpp_is_constant_evaluated() && (__sz < __min_cap); } - template + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_size(_Iterator __first, _Sentinel __last, size_type __n); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __first, _Sentinel __last); + + template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 - iterator __insert_from_safe_copy(size_type __n, size_type __ip, _ForwardIterator __first, _ForwardIterator __last) { + iterator __insert_from_safe_copy(size_type __n, size_type __ip, _ForwardIterator __first, _Sentinel __last) { size_type __sz = size(); size_type __cap = capacity(); value_type* __p; @@ -1768,6 +1844,10 @@ return begin() + __ip; } + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 + iterator __insert_with_size(const_iterator __pos, _Iterator __first, _Sentinel __last, size_type __n); + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 allocator_type& __alloc() _NOEXCEPT { return __r_.second(); } _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR const allocator_type& __alloc() const _NOEXCEPT { return __r_.second(); } @@ -2505,9 +2585,17 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>& basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last) { - const basic_string __temp(__first, __last, __alloc()); - assign(__temp.data(), __temp.size()); - return *this; + __assign_with_sentinel(__first, __last); + return *this; +} + +template +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 +void +basic_string<_CharT, _Traits, _Allocator>::__assign_with_sentinel(_InputIterator __first, _Sentinel __last) { + const basic_string __temp(__init_with_sentinel_tag{}, __first, __last, __alloc()); + assign(__temp.data(), __temp.size()); } template @@ -2515,11 +2603,24 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 basic_string<_CharT, _Traits, _Allocator>& basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) { + if (__string_is_trivial_iterator<_ForwardIterator>::value) { + size_type __n = static_cast(std::distance(__first, __last)); + __assign_with_size(__first, __last, __n); + } else { + __assign_with_sentinel(__first, __last); + } + + return *this; +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void +basic_string<_CharT, _Traits, _Allocator>::__assign_with_size(_Iterator __first, _Sentinel __last, size_type __n) { size_type __cap = capacity(); - size_type __n = __string_is_trivial_iterator<_ForwardIterator>::value ? - static_cast(std::distance(__first, __last)) : 0; - if (__string_is_trivial_iterator<_ForwardIterator>::value && + if (__string_is_trivial_iterator<_Iterator>::value && (__cap >= __n || !__addr_in_range(*__first))) { if (__cap < __n) @@ -2536,10 +2637,8 @@ } else { - const basic_string __temp(__first, __last, __alloc()); - assign(__temp.data(), __temp.size()); + __assign_with_sentinel(__first, __last); } - return *this; } template @@ -2845,19 +2944,27 @@ { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(&__pos) == this, "string::insert(iterator, range) called with an iterator not referring to this string"); + auto __n = static_cast(std::distance(__first, __last)); + return __insert_with_size(__pos, __first, __last, __n); +} +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 +typename basic_string<_CharT, _Traits, _Allocator>::iterator +basic_string<_CharT, _Traits, _Allocator>::__insert_with_size( + const_iterator __pos, _Iterator __first, _Sentinel __last, size_type __n) { size_type __ip = static_cast(__pos - begin()); - size_type __n = static_cast(std::distance(__first, __last)); if (__n == 0) return begin() + __ip; - if (__string_is_trivial_iterator<_ForwardIterator>::value && !__addr_in_range(*__first)) + if (__string_is_trivial_iterator<_Iterator>::value && !__addr_in_range(*__first)) { return __insert_from_safe_copy(__n, __ip, __first, __last); } else { - const basic_string __temp(__first, __last, __alloc()); + const basic_string __temp(__init_with_sentinel_tag{}, __first, __last, __alloc()); return __insert_from_safe_copy(__n, __ip, __temp.begin(), __temp.end()); } } diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map --- a/libcxx/include/unordered_map +++ b/libcxx/include/unordered_map @@ -133,6 +133,8 @@ iterator insert(const_iterator hint, P&& obj); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list); node_type extract(const_iterator position); // C++17 @@ -417,6 +419,8 @@ iterator insert(const_iterator hint, P&& obj); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list); node_type extract(const_iterator position); // C++17 @@ -1317,10 +1321,9 @@ void insert(_InputIterator __first, _InputIterator __last); #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { for (auto&& __element : __range) { __table_.__insert_unique(std::forward(__element)); } @@ -2282,10 +2285,9 @@ void insert(_InputIterator __first, _InputIterator __last); #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { for (auto&& __element : __range) { __table_.__insert_multi(std::forward(__element)); } diff --git a/libcxx/include/unordered_set b/libcxx/include/unordered_set --- a/libcxx/include/unordered_set +++ b/libcxx/include/unordered_set @@ -123,6 +123,8 @@ iterator insert(const_iterator hint, value_type&& obj); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list); node_type extract(const_iterator position); // C++17 @@ -369,6 +371,8 @@ iterator insert(const_iterator hint, value_type&& obj); template void insert(InputIterator first, InputIterator last); + template R> + void insert_range(R&& rg); // C++23 void insert(initializer_list); node_type extract(const_iterator position); // C++17 @@ -800,10 +804,9 @@ void insert(_InputIterator __first, _InputIterator __last); #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { for (auto&& __element : __range) { __table_.__insert_unique(std::forward(__element)); } @@ -1514,10 +1517,9 @@ void insert(_InputIterator __first, _InputIterator __last); #if _LIBCPP_STD_VER >= 23 - // TODO(varconst): make this a public function. template <_ContainerCompatibleRange _Range> _LIBCPP_HIDE_FROM_ABI - void __insert_range(_Range&& __range) { + void insert_range(_Range&& __range) { for (auto&& __element : __range) { __table_.__insert_multi(std::forward(__element)); } diff --git a/libcxx/include/vector b/libcxx/include/vector --- a/libcxx/include/vector +++ b/libcxx/include/vector @@ -57,6 +57,8 @@ vector& operator=(initializer_list il); template void assign(InputIterator first, InputIterator last); + template R> + constexpr void assign_range(R&& rg); // C++23 void assign(size_type n, const value_type& u); void assign(initializer_list il); @@ -101,6 +103,8 @@ void push_back(value_type&& x); template reference emplace_back(Args&&... args); // reference in C++17 + template R> + constexpr void append_range(R&& rg); // C++23 void pop_back(); template iterator emplace(const_iterator position, Args&&... args); @@ -109,6 +113,8 @@ iterator insert(const_iterator position, size_type n, const value_type& x); template iterator insert(const_iterator position, InputIterator first, InputIterator last); + template R> + constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 iterator insert(const_iterator position, initializer_list il); iterator erase(const_iterator position); @@ -183,6 +189,8 @@ vector& operator=(initializer_list il); template void assign(InputIterator first, InputIterator last); + template R> + constexpr void assign_range(R&& rg); // C++23 void assign(size_type n, const value_type& u); void assign(initializer_list il); @@ -222,6 +230,8 @@ void push_back(const value_type& x); template reference emplace_back(Args&&... args); // C++14; reference in C++17 + template R> + constexpr void append_range(R&& rg); // C++23 void pop_back(); template iterator emplace(const_iterator position, Args&&... args); // C++14 @@ -229,6 +239,8 @@ iterator insert(const_iterator position, size_type n, const value_type& x); template iterator insert(const_iterator position, InputIterator first, InputIterator last); + template R> + constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 iterator insert(const_iterator position, initializer_list il); iterator erase(const_iterator position); @@ -529,6 +541,20 @@ int> = 0> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void assign_range(_Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + __assign_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +#endif + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const_reference __u); #ifndef _LIBCPP_CXX03_LANG @@ -631,6 +657,14 @@ void emplace_back(_Args&&... __args); #endif +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void append_range(_Range&& __range) { + insert_range(end(), std::forward<_Range>(__range)); + } +#endif + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back(); @@ -650,6 +684,20 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr iterator insert_range(const_iterator __position, _Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n); + + } else { + return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } + } +#endif + template < class _ForwardIterator, __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value && @@ -755,6 +803,22 @@ __guard.__complete(); } + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __first, _Sentinel __last); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_size(_Iterator __first, _Sentinel __last, difference_type __n); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n); + template _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n); @@ -1380,6 +1444,13 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) { + __assign_with_sentinel(__first, __last); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) { clear(); for (; __first != __last; ++__first) emplace_back(*__first); @@ -1392,22 +1463,25 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) { - size_type __new_size = static_cast(std::distance(__first, __last)); + __assign_with_size(__first, __last, std::distance(__first, __last)); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector<_Tp, _Allocator>::__assign_with_size(_Iterator __first, _Sentinel __last, difference_type __n) { + size_type __new_size = static_cast(__n); if (__new_size <= capacity()) { - _ForwardIterator __mid = __last; - bool __growing = false; if (__new_size > size()) { - __growing = true; - __mid = __first; - std::advance(__mid, size()); + std::advance(__first, size()); + __construct_at_end(__first, __last, __new_size - size()); + + } else { + pointer __m = std::__copy<_ClassicAlgPolicy>(__first, __last, this->__begin_).second; + this->__destruct_at_end(__m); } - pointer __m = std::copy(__first, __mid, this->__begin_); - if (__growing) - __construct_at_end(__mid, __last, __new_size - size()); - else - this->__destruct_at_end(__m); } else { @@ -1837,7 +1911,6 @@ } return __make_iter(__p); } - template template ::value && is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value, @@ -1845,8 +1918,17 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(std::addressof(__position)) == this, - "vector::insert(iterator, range) called with an iterator not referring to this vector"); + _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(std::addressof(__position)) == this, + "vector::insert(iterator, range) called with an iterator not referring to this vector"); + + return __insert_with_sentinel(__position, __first, __last); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector<_Tp, _Allocator>::iterator +vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { difference_type __off = __position - begin(); pointer __p = this->__begin_ + __off; allocator_type& __a = this->__alloc(); @@ -1862,7 +1944,7 @@ try { #endif // _LIBCPP_HAS_NO_EXCEPTIONS - __v.__construct_at_end(__first, __last); + __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last)); difference_type __old_size = __old_last - this->__begin_; difference_type __old_p = __p - this->__begin_; reserve(__recommend(size() + __v.size())); @@ -1890,17 +1972,27 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(std::addressof(__position)) == this, - "vector::insert(iterator, range) called with an iterator not referring to this vector"); + _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(std::addressof(__position)) == this, + "vector::insert(iterator, range) called with an iterator not referring to this vector"); + + return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector<_Tp, _Allocator>::iterator +vector<_Tp, _Allocator>::__insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, + difference_type __n) { + auto __insertion_size = __n; pointer __p = this->__begin_ + (__position - begin()); - difference_type __n = std::distance(__first, __last); if (__n > 0) { if (__n <= this->__end_cap() - this->__end_) { size_type __old_n = __n; pointer __old_last = this->__end_; - _ForwardIterator __m = __last; + _Iterator __m = std::next(__first, __n); difference_type __dx = this->__end_ - __p; if (__n > __dx) { @@ -1920,7 +2012,7 @@ { allocator_type& __a = this->__alloc(); __split_buffer __v(__recommend(size() + __n), __p - this->__begin_, __a); - __v.__construct_at_end(__first, __last); + __v.__construct_at_end_with_size(__first, __insertion_size); __p = __swap_out_circular_buffer(__v, __p); } } @@ -2224,6 +2316,20 @@ >::type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void assign_range(_Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + __assign_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +#endif + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x); #ifndef _LIBCPP_CXX03_LANG @@ -2313,6 +2419,14 @@ } #endif +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void append_range(_Range&& __range) { + insert_range(end(), std::forward<_Range>(__range)); + } +#endif + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() {--__size_;} #if _LIBCPP_STD_VER >= 14 @@ -2336,6 +2450,20 @@ >::type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr iterator insert_range(const_iterator __position, _Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n); + + } else { + return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, initializer_list __il) @@ -2404,6 +2532,22 @@ #endif // _LIBCPP_HAS_NO_EXCEPTIONS } + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __first, _Sentinel __last); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_size(_Iterator __first, _Sentinel __last, difference_type __ns); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last); + + template + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n); + // Allocate space for __n objects // throws length_error if __n > max_size() // throws (probably bad_alloc) if memory run out @@ -2894,6 +3038,13 @@ >::type vector::assign(_InputIterator __first, _InputIterator __last) { + __assign_with_sentinel(__first, __last); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector::__assign_with_sentinel(_Iterator __first, _Sentinel __last) { clear(); for (; __first != __last; ++__first) push_back(*__first); @@ -2909,9 +3060,17 @@ >::type vector::assign(_ForwardIterator __first, _ForwardIterator __last) { - clear(); - difference_type __ns = std::distance(__first, __last); + __assign_with_size(__first, __last, std::distance(__first, __last)); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector::__assign_with_size(_Iterator __first, _Sentinel __last, difference_type __ns) { _LIBCPP_ASSERT(__ns >= 0, "invalid range specified"); + + clear(); + const size_t __n = static_cast(__ns); if (__n) { @@ -3046,6 +3205,14 @@ >::type vector::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { + return __insert_with_sentinel(__position, __first, __last); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector::iterator +vector::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { difference_type __off = __position - begin(); iterator __p = __const_iterator_cast(__position); iterator __old_end = end(); @@ -3061,7 +3228,7 @@ try { #endif // _LIBCPP_HAS_NO_EXCEPTIONS - __v.assign(__first, __last); + __v.__assign_with_sentinel(std::move(__first), std::move(__last)); difference_type __old_size = static_cast(__old_end - begin()); difference_type __old_p = __p - begin(); reserve(__recommend(size() + __v.size())); @@ -3091,7 +3258,15 @@ >::type vector::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { - const difference_type __n_signed = std::distance(__first, __last); + return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); +} + +template +template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector::iterator +vector::__insert_with_size(const_iterator __position, _ForwardIterator __first, _Sentinel __last, + difference_type __n_signed) { _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified"); const size_type __n = static_cast(__n_signed); iterator __r; @@ -3112,7 +3287,7 @@ std::copy_backward(__position, cend(), __v.end()); swap(__v); } - std::copy(__first, __last, __r); + std::__copy<_ClassicAlgPolicy>(__first, __last, __r); return __r; } diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/insert_range.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/insert_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/associative/map/map.modifiers/insert_range.pass.cpp @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template R> +// void insert_range(R&& rg); // C++23 + +#include + +#include "../../../insert_range_helpers.h" +#include "../../../test_compare.h" +#include "test_macros.h" + +int main(int, char**) { + for_all_iterators_and_allocators>([]() { + test_map_insert_range, Alloc>, Iter, Sent>(); + }); + + return 0; +} diff --git a/libcxx/test/std/containers/associative/multiset/insert_range.pass.cpp b/libcxx/test/std/containers/associative/multiset/insert_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/associative/multiset/insert_range.pass.cpp @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template R> +// void insert_range(R&& rg); // C++23 + +#include + +#include "../../insert_range_helpers.h" +#include "../../test_compare.h" +#include "test_macros.h" + +int main(int, char**) { + for_all_iterators_and_allocators([]() { + test_set_insert_range, Alloc>, Iter, Sent>(/*allow_duplicates=*/true); + }); + + return 0; +} diff --git a/libcxx/test/std/containers/associative/set/insert_range.pass.cpp b/libcxx/test/std/containers/associative/set/insert_range.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/associative/set/insert_range.pass.cpp @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// template R> +// void insert_range(R&& rg); // C++23 + +#include + +#include "../../insert_range_helpers.h" +#include "../../test_compare.h" +#include "test_macros.h" + +int main(int, char**) { + for_all_iterators_and_allocators([]() { + test_set_insert_range, Alloc>, Iter, Sent>(); + }); + + return 0; +} diff --git a/libcxx/test/std/containers/insert_range_helpers.h b/libcxx/test/std/containers/insert_range_helpers.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/insert_range_helpers.h @@ -0,0 +1,415 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SUPPORT_INSERT_RANGE_HELPERS_H +#define SUPPORT_INSERT_RANGE_HELPERS_H + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "min_allocator.h" +#include "test_allocator.h" +#include "test_iterators.h" +#include "test_macros.h" +#include "type_algorithms.h" + +template +constexpr auto wrap_input(Range&& input) { + auto b = Iter(std::ranges::begin(input)); + auto e = Sent(Iter(std::ranges::end(input))); + return std::ranges::subrange(std::move(b), std::move(e)); +} + +template +constexpr auto wrap_input(std::vector& input) { + auto b = Iter(input.data()); + auto e = Sent(Iter(input.data() + input.size())); + return std::ranges::subrange(std::move(b), std::move(e)); +} + +template +void test_set_insert_range(bool allow_duplicates = false) { + using T = typename Container::value_type; + + { // Empty set. + { // Empty range. + Container c; + std::array input; + auto in = wrap_input(input); + + c.insert_range(in); + assert(c.empty()); + } + + { // Single-element range. + T input[] = {1}; + auto in = wrap_input(input); + + Container c; + c.insert_range(in); + assert(std::ranges::is_permutation(c, input)); + } + + { // Range with no duplicates. + T input[] = {5, 1, 3, 8, 6}; + auto in = wrap_input(input); + + Container c; + c.insert_range(in); + assert(std::ranges::is_permutation(c, input)); + } + + { // Range with duplicates. + T input[] = {5, 1, 1, 3, 5, 8, 5, 6}; + auto in = wrap_input(input); + + Container c; + c.insert_range(in); + if (allow_duplicates) { + assert(std::ranges::is_permutation(c, input)); + } else { + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6})); + } + } + } + + { // Single-element set. + Container initial = {10}; + + { // Empty range. + Container c = initial; + std::array input; + auto in = wrap_input(input); + + c.insert_range(in); + assert(std::ranges::is_permutation(c, initial)); + } + + { // Single-element range. + T input[] = {1}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{1, 10})); + } + + { // Range with no duplicates. + T input[] = {5, 1, 3, 8, 6}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6, 10})); + } + + { // Range with duplicates. + T input[] = {5, 1, 1, 3, 5, 8, 5, 6, 10}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + if (allow_duplicates) { + assert(std::ranges::is_permutation(c, std::array{5, 1, 1, 3, 5, 8, 5, 6, 10, 10})); + } else { + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6, 10})); + } + } + } + + { // Set with several elements. + Container initial = {10, 15, 19, 16}; + + { // Empty range. + Container c = initial; + std::array input; + auto in = wrap_input(input); + + c.insert_range(in); + assert(std::ranges::is_permutation(c, initial)); + } + + { // Single-element range. + T input[] = {1}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{1, 10, 15, 19, 16})); + } + + { // Range with no duplicates. + T input[] = {5, 1, 3, 8, 6}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6, 10, 15, 19, 16})); + } + + { // Range with duplicates. + T input[] = {5, 1, 1, 3, 5, 8, 19, 5, 6, 10}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + if (allow_duplicates) { + assert(std::ranges::is_permutation(c, std::array{5, 1, 1, 3, 5, 8, 19, 5, 6, 10, 10, 15, 19, 16})); + } else { + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6, 10, 15, 19, 16})); + } + } + } +} + +/* +template +void test_map_insert_range(bool allow_duplicates = false) { + using T = typename Container::value_type; + + { // Empty map. + { // Empty range. + Container c; + std::array input; + auto in = wrap_input(input); + + c.insert_range(in); + assert(c.empty()); + } + + { // Single-element range. + T input[] = {{1, -1}}; + auto in = wrap_input(input); + + Container c; + c.insert_range(in); + assert(std::ranges::is_permutation(c, input)); + } + + { // Range with no duplicates. + T input[] = {{5, -5}, {1, -1}, {3, -3}, {8, -8}, {6, -6}}; + auto in = wrap_input(input); + + Container c; + c.insert_range(in); + assert(std::ranges::is_permutation(c, input)); + } + + { // Range with duplicates. + T input[] = {{5, -15}, {1, -11}, {1, -21}, {3, -3}, {5, -25}, {8, -8}, {5, -35}, {6, -6}}; + auto in = wrap_input(input); + + Container c; + c.insert_range(in); + if (allow_duplicates) { + assert(std::ranges::is_permutation(c, input)); + } else { + assert(std::ranges::is_permutation(c, std::array{ + T{5, -15}, T{1, -11}, T{3, -3}, T{8, -8}, T{6, -6} + })); + } + } + } + + { // Single-element map. + Container initial = {{10, -100}}; + + { // Empty range. + Container c = initial; + std::array input; + auto in = wrap_input(input); + + c.insert_range(in); + assert(std::ranges::is_permutation(c, initial)); + } + + { // Single-element range. + T input[] = {{1, -1}}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{T{1, -1}, T{10, -100}}); + } + + { // Range with no duplicates. + T input[] = {{5, -5}, {1, -1}, {3, -3}, {8, -8}, {6, -6}}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6, 10})); + } + + { // Range with duplicates. + T input[] = {{5, -15}, {1, -11}, {1, -21}, {3, -3}, {5, -25}, {8, -8}, {5, -35}, {6, -6}, {10, -200}}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + if (allow_duplicates) { + assert(std::ranges::is_permutation(c, std::array{ + T{5, -15}, T{1, -11}, T{1, -21}, T{3, -3}, T{5, -25}, T{8, -8}, T{5, -35}, T{6, -6}, T{10, -100}, + T{10, -200} + })); + } else { + assert(std::ranges::is_permutation(c, std::array{ + T{5, -15}, T{1, -11}, T{3, -3}, T{8, -8}, T{6, -6}, T{10, -100} + })); + } + } + } + + { // Map with several elements. + Container initial = {10, 15, 19, 16}; + + { // Empty range. + Container c = initial; + std::array input; + auto in = wrap_input(input); + + c.insert_range(in); + assert(std::ranges::is_permutation(c, initial)); + } + + { // Single-element range. + T input[] = {1}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{1, 10, 15, 19, 16})); + } + + { // Range with no duplicates. + T input[] = {5, 1, 3, 8, 6}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6, 10, 15, 19, 16})); + } + + { // Range with duplicates. + T input[] = {5, 1, 1, 3, 5, 8, 19, 5, 6, 10}; + auto in = wrap_input(input); + + Container c = initial; + c.insert_range(in); + if (allow_duplicates) { + assert(std::ranges::is_permutation(c, std::array{5, 1, 1, 3, 5, 8, 19, 5, 6, 10, 10, 15, 19, 16})); + } else { + assert(std::ranges::is_permutation(c, std::array{5, 1, 3, 8, 6, 10, 15, 19, 16})); + } + } + } +} +*/ + +template +constexpr void for_all_iterators_and_allocators(Func f) { + using Iterators = types::type_list< + cpp20_input_iterator, + forward_iterator, + bidirectional_iterator, + random_access_iterator, + contiguous_iterator, + PtrT + >; + + types::for_each(Iterators{}, [=]() { + f.template operator(), std::allocator>(); + f.template operator(), test_allocator>(); + f.template operator(), min_allocator>(); + f.template operator(), safe_allocator>(); + + if constexpr (std::sentinel_for) { + f.template operator()>(); + f.template operator()>(); + f.template operator()>(); + f.template operator()>(); + } + }); +} + +/* +#if !defined(TEST_HAS_NO_EXCEPTIONS) +template +struct ThrowingCopy { + static bool throwing_enabled; + static int created_by_copying; + static int destroyed; + int x = 0; // Allows distinguishing between different instances. + + ThrowingCopy() = default; + ThrowingCopy(int value) : x(value) {} + ~ThrowingCopy() { + ++destroyed; + } + + ThrowingCopy(const ThrowingCopy& other) : x(other.x) { + ++created_by_copying; + if (throwing_enabled && created_by_copying == N) { + throw -1; + } + } + + friend auto operator<=>(const ThrowingCopy&, const ThrowingCopy&) = default; + + static void reset() { + created_by_copying = destroyed = 0; + } +}; + +template +struct std::hash> { + std::size_t operator()(const ThrowingCopy& value) const { + return value.x; + } +}; + +template +bool ThrowingCopy::throwing_enabled = true; +template +int ThrowingCopy::created_by_copying = 0; +template +int ThrowingCopy::destroyed = 0; + +template +struct ThrowingAllocator { + using value_type = T; + using char_type = T; + using is_always_equal = std::false_type; + + ThrowingAllocator() = default; + + template + ThrowingAllocator(const ThrowingAllocator&) {} + + T* allocate(std::size_t) { throw 1; } + void deallocate(T*, std::size_t) {} + + template + friend bool operator==(const ThrowingAllocator&, const ThrowingAllocator&) { + return true; + } +}; +#endif + +*/ + +#endif // SUPPORT_INSERT_RANGE_HELPERS_H diff --git a/libcxx/test/std/containers/insert_range_sequence_containers.h b/libcxx/test/std/containers/insert_range_sequence_containers.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/insert_range_sequence_containers.h @@ -0,0 +1,1263 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H +#define SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "MoveOnly.h" +#include "count_new.h" +#include "from_range_helpers.h" +#include "insert_range_helpers.h" +#include "min_allocator.h" +#include "test_allocator.h" +#include "test_iterators.h" +#include "test_macros.h" +#include "type_algorithms.h" + +// A simple literal-type container. It can be used as a `constexpr` global variable (which isn't supported by +// `std::vector`). +template +class Buffer { + public: + constexpr Buffer() = default; + template + constexpr Buffer(std::initializer_list input) { + assert(input.size() <= N); + std::ranges::copy(input, data_); + size_ = input.size(); + } + + constexpr const T* begin() const { return data_; } + constexpr const T* end() const { return data_ + size_; } + constexpr std::size_t size() const { return size_; } + + private: + std::size_t size_ = 0; + T data_[N] = {}; +}; + +template +struct TestCase { + Buffer initial; + std::size_t index = 0; + Buffer input; + Buffer expected; +}; + +// Empty container. + +template +TestCase constexpr EmptyContainer_EmptyRange { + .initial = {}, .index = 0, .input = {}, .expected = {} +}; +// Note: specializations for `bool` still use `vector` for inputs. This is to avoid dealing with `vector` and +// its iterators over proxy types. +template <> constexpr TestCase EmptyContainer_EmptyRange { + .initial = {}, .index = 0, .input = {}, .expected = {} +}; + +template constexpr TestCase EmptyContainer_OneElementRange; +template <> constexpr TestCase EmptyContainer_OneElementRange { + .initial = {}, .index = 0, .input = {5}, .expected = {5} +}; +template <> constexpr TestCase EmptyContainer_OneElementRange { + .initial = {}, .index = 0, .input = {'a'}, .expected = {'a'} +}; +template <> constexpr TestCase EmptyContainer_OneElementRange { + .initial = {}, .index = 0, .input = {true}, .expected = {true} +}; + +template constexpr TestCase EmptyContainer_MidRange; +template <> constexpr TestCase EmptyContainer_MidRange { + .initial = {}, .index = 0, .input = {5, 3, 1, 7, 9}, .expected = {5, 3, 1, 7, 9} +}; +template <> constexpr TestCase EmptyContainer_MidRange { + .initial = {}, .index = 0, .input = {'a', 'e', 'i', 'o', 'u'}, .expected = {'a', 'e', 'i', 'o', 'u'} +}; +template <> constexpr TestCase EmptyContainer_MidRange { + .initial = {}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1} +}; + +// One-element container. + +template constexpr TestCase OneElementContainer_Begin_EmptyRange; +template <> constexpr TestCase OneElementContainer_Begin_EmptyRange { + .initial = {3}, .index = 0, .input = {}, .expected = {3} +}; +template <> constexpr TestCase OneElementContainer_Begin_EmptyRange { + .initial = {'B'}, .index = 0, .input = {}, .expected = {'B'} +}; +template <> constexpr TestCase OneElementContainer_Begin_EmptyRange { + .initial = {0}, .index = 0, .input = {}, .expected = {0} +}; + +template constexpr TestCase OneElementContainer_End_EmptyRange; +template <> constexpr TestCase OneElementContainer_End_EmptyRange { + .initial = {3}, .index = 1, .input = {}, .expected = {3} +}; +template <> constexpr TestCase OneElementContainer_End_EmptyRange { + .initial = {'B'}, .index = 1, .input = {}, .expected = {'B'} +}; +template <> constexpr TestCase OneElementContainer_End_EmptyRange { + .initial = {0}, .index = 1, .input = {}, .expected = {0} +}; + +template constexpr TestCase OneElementContainer_Begin_OneElementRange; +template <> constexpr TestCase OneElementContainer_Begin_OneElementRange { + .initial = {3}, .index = 0, .input = {-5}, .expected = {-5, 3} +}; +template <> constexpr TestCase OneElementContainer_Begin_OneElementRange { + .initial = {'B'}, .index = 0, .input = {'a'}, .expected = {'a', 'B'} +}; +template <> constexpr TestCase OneElementContainer_Begin_OneElementRange { + .initial = {0}, .index = 0, .input = {1}, .expected = {1, 0} +}; + +template constexpr TestCase OneElementContainer_End_OneElementRange; +template <> constexpr TestCase OneElementContainer_End_OneElementRange { + .initial = {3}, .index = 1, .input = {-5}, .expected = {3, -5} +}; +template <> constexpr TestCase OneElementContainer_End_OneElementRange { + .initial = {'B'}, .index = 1, .input = {'a'}, .expected = {'B', 'a'} +}; +template <> constexpr TestCase OneElementContainer_End_OneElementRange { + .initial = {0}, .index = 1, .input = {1}, .expected = {0, 1} +}; + +template constexpr TestCase OneElementContainer_Begin_MidRange; +template <> constexpr TestCase OneElementContainer_Begin_MidRange { + .initial = {3}, .index = 0, .input = {-5, -3, -1, -7, -9}, .expected = {-5, -3, -1, -7, -9, 3} +}; +template <> constexpr TestCase OneElementContainer_Begin_MidRange { + .initial = {'B'}, .index = 0, .input = {'a', 'e', 'i', 'o', 'u'}, .expected = {'a', 'e', 'i', 'o', 'u', 'B'} +}; +template <> constexpr TestCase OneElementContainer_Begin_MidRange { + .initial = {0}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1, 0} +}; + +template constexpr TestCase OneElementContainer_End_MidRange; +template <> constexpr TestCase OneElementContainer_End_MidRange { + .initial = {3}, .index = 1, .input = {-5, -3, -1, -7, -9}, .expected = {3, -5, -3, -1, -7, -9} +}; +template <> constexpr TestCase OneElementContainer_End_MidRange { + .initial = {'B'}, .index = 1, .input = {'a', 'e', 'i', 'o', 'u'}, .expected = {'B', 'a', 'e', 'i', 'o', 'u'} +}; +template <> constexpr TestCase OneElementContainer_End_MidRange { + .initial = {0}, .index = 1, .input = {1, 1, 0, 1, 1}, .expected = {0, 1, 1, 0, 1, 1} +}; + +// Full container / empty range. + +template constexpr TestCase FullContainer_Begin_EmptyRange; +template <> constexpr TestCase FullContainer_Begin_EmptyRange { + .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {}, .expected = {11, 29, 35, 14, 84} +}; +template <> constexpr TestCase FullContainer_Begin_EmptyRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, .index = 0, .input = {}, .expected = {'B', 'F', 'H', 'G', 'D'} +}; +template <> constexpr TestCase FullContainer_Begin_EmptyRange { + .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {}, .expected = {0, 0, 1, 0, 0} +}; + +template constexpr TestCase FullContainer_Mid_EmptyRange; +template <> constexpr TestCase FullContainer_Mid_EmptyRange { + .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {}, .expected = {11, 29, 35, 14, 84} +}; +template <> constexpr TestCase FullContainer_Mid_EmptyRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, .index = 2, .input = {}, .expected = {'B', 'F', 'H', 'G', 'D'} +}; +template <> constexpr TestCase FullContainer_Mid_EmptyRange { + .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {}, .expected = {0, 0, 1, 0, 0} +}; + +template constexpr TestCase FullContainer_End_EmptyRange; +template <> constexpr TestCase FullContainer_End_EmptyRange { + .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {}, .expected = {11, 29, 35, 14, 84} +}; +template <> constexpr TestCase FullContainer_End_EmptyRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, .index = 5, .input = {}, .expected = {'B', 'F', 'H', 'G', 'D'} +}; +template <> constexpr TestCase FullContainer_End_EmptyRange { + .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {}, .expected = {0, 0, 1, 0, 0} +}; + +// Full container / one-element range. + +template constexpr TestCase FullContainer_Begin_OneElementRange; +template <> constexpr TestCase FullContainer_Begin_OneElementRange { + .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {-5}, .expected = {-5, 11, 29, 35, 14, 84} +}; +template <> constexpr TestCase FullContainer_Begin_OneElementRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, .index = 0, .input = {'a'}, .expected = {'a', 'B', 'F', 'H', 'G', 'D'} +}; +template <> constexpr TestCase FullContainer_Begin_OneElementRange { + .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {1}, .expected = {1, 0, 0, 1, 0, 0} +}; + +template constexpr TestCase FullContainer_Mid_OneElementRange; +template <> constexpr TestCase FullContainer_Mid_OneElementRange { + .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {-5}, .expected = {11, 29, -5, 35, 14, 84} +}; +template <> constexpr TestCase FullContainer_Mid_OneElementRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, .index = 2, .input = {'a'}, .expected = {'B', 'F', 'a', 'H', 'G', 'D'} +}; +template <> constexpr TestCase FullContainer_Mid_OneElementRange { + .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {1}, .expected = {0, 0, 1, 1, 0, 0} +}; + +template constexpr TestCase FullContainer_End_OneElementRange; +template <> constexpr TestCase FullContainer_End_OneElementRange { + .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {-5}, .expected = {11, 29, 35, 14, 84, -5} +}; +template <> constexpr TestCase FullContainer_End_OneElementRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, .index = 5, .input = {'a'}, .expected = {'B', 'F', 'H', 'G', 'D', 'a'} +}; +template <> constexpr TestCase FullContainer_End_OneElementRange { + .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {1}, .expected = {0, 0, 1, 0, 0, 1} +}; + +// Full container / mid-sized range. + +template constexpr TestCase FullContainer_Begin_MidRange; +template <> constexpr TestCase FullContainer_Begin_MidRange { + .initial = {11, 29, 35, 14, 84}, + .index = 0, + .input = {-5, -3, -1, -7, -9}, + .expected = {-5, -3, -1, -7, -9, 11, 29, 35, 14, 84} +}; +template <> constexpr TestCase FullContainer_Begin_MidRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, + .index = 0, + .input = {'a', 'e', 'i', 'o', 'u'}, + .expected = {'a', 'e', 'i', 'o', 'u', 'B', 'F', 'H', 'G', 'D'} +}; +template <> constexpr TestCase FullContainer_Begin_MidRange { + .initial = {0, 0, 1, 0, 1}, + .index = 0, + .input = {1, 1, 0, 1, 1}, + .expected = {1, 1, 0, 1, 1, 0, 0, 1, 0, 1} +}; + +template constexpr TestCase FullContainer_Mid_MidRange; +template <> constexpr TestCase FullContainer_Mid_MidRange { + .initial = {11, 29, 35, 14, 84}, + .index = 2, + .input = {-5, -3, -1, -7, -9}, + .expected = {11, 29, -5, -3, -1, -7, -9, 35, 14, 84} +}; +template <> constexpr TestCase FullContainer_Mid_MidRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, + .index = 2, + .input = {'a', 'e', 'i', 'o', 'u'}, + .expected = {'B', 'F', 'a', 'e', 'i', 'o', 'u', 'H', 'G', 'D'} +}; +template <> constexpr TestCase FullContainer_Mid_MidRange { + .initial = {0, 0, 1, 0, 1}, + .index = 2, + .input = {1, 1, 0, 1, 1}, + .expected = {0, 0, 1, 1, 0, 1, 1, 1, 0, 1} +}; + +template constexpr TestCase FullContainer_End_MidRange; +template <> constexpr TestCase FullContainer_End_MidRange { + .initial = {11, 29, 35, 14, 84}, + .index = 5, + .input = {-5, -3, -1, -7, -9}, + .expected = {11, 29, 35, 14, 84, -5, -3, -1, -7, -9} +}; +template <> constexpr TestCase FullContainer_End_MidRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, + .index = 5, + .input = {'a', 'e', 'i', 'o', 'u'}, + .expected = {'B', 'F', 'H', 'G', 'D', 'a', 'e', 'i', 'o', 'u'} +}; +template <> constexpr TestCase FullContainer_End_MidRange { + .initial = {0, 0, 1, 0, 1}, + .index = 5, + .input = {1, 1, 0, 1, 1}, + .expected = {0, 0, 1, 0, 1, 1, 1, 0, 1, 1} +}; + +// Full container / long range. + +template constexpr TestCase FullContainer_Begin_LongRange; +template <> constexpr TestCase FullContainer_Begin_LongRange { + .initial = {11, 29, 35, 14, 84}, + .index = 0, + .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48}, + .expected = { + -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48, 11, 29, 35, 14, 84 + } +}; +template <> constexpr TestCase FullContainer_Begin_LongRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, + .index = 0, + .input = {'a', 'e', 'i', 'o', 'u', 'q', 'w', 'x', 'y', 'z', '5', '7', '8', '1', '9', '6', '4', '2', '0', '3'}, + .expected = { + 'a', 'e', 'i', 'o', 'u', 'q', 'w', 'x', 'y', 'z', '5', '7', '8', '1', '9', '6', '4', '2', '0', '3', + 'B', 'F', 'H', 'G', 'D' + } +}; +template <> constexpr TestCase FullContainer_Begin_LongRange { + .initial = {0, 0, 1, 0, 0}, + .index = 0, + .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, + .expected = { + 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 + } +}; + +template constexpr TestCase FullContainer_Mid_LongRange; +template <> constexpr TestCase FullContainer_Mid_LongRange { + .initial = {11, 29, 35, 14, 84}, + .index = 2, + .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48}, + .expected = { + 11, 29, -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48, 35, 14, 84 + } +}; +template <> constexpr TestCase FullContainer_Mid_LongRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, + .index = 2, + .input = {'a', 'e', 'i', 'o', 'u', 'q', 'w', 'x', 'y', 'z', '5', '7', '8', '1', '9', '6', '4', '2', '0', '3'}, + .expected = { + 'B', 'F', + 'a', 'e', 'i', 'o', 'u', 'q', 'w', 'x', 'y', 'z', '5', '7', '8', '1', '9', '6', '4', '2', '0', '3', + 'H', 'G', 'D' + } +}; +template <> constexpr TestCase FullContainer_Mid_LongRange { + .initial = {0, 0, 1, 0, 0}, + .index = 2, + .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, + .expected = { + 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0 + } +}; + +template constexpr TestCase FullContainer_End_LongRange; +template <> constexpr TestCase FullContainer_End_LongRange { + .initial = {11, 29, 35, 14, 84}, + .index = 5, + .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48}, + .expected = { + 11, 29, 35, 14, 84, -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48 + } +}; +template <> constexpr TestCase FullContainer_End_LongRange { + .initial = {'B', 'F', 'H', 'G', 'D'}, + .index = 5, + .input = {'a', 'e', 'i', 'o', 'u', 'q', 'w', 'x', 'y', 'z', '5', '7', '8', '1', '9', '6', '4', '2', '0', '3'}, + .expected = { + 'B', 'F', 'H', 'G', 'D', + 'a', 'e', 'i', 'o', 'u', 'q', 'w', 'x', 'y', 'z', '5', '7', '8', '1', '9', '6', '4', '2', '0', '3' + } +}; +template <> constexpr TestCase FullContainer_End_LongRange { + .initial = {0, 0, 1, 0, 1}, + .index = 5, + .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, + .expected = { + 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 + } +}; + +// Sequence containers tests. + +template +constexpr void test_sequence_insert_range(Validate validate) { + using T = typename Container::value_type; + auto get_pos = [](auto& c, auto& test_case) { return std::ranges::next(c.begin(), test_case.index); }; + + { // Empty container. + { // empty_c.insert_range(end, empty_range) + auto& test_case = EmptyContainer_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // empty_c.insert_range(end, one_element_range) + auto& test_case = EmptyContainer_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // empty_c.insert_range(end, mid_range) + auto& test_case = EmptyContainer_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + } + + { // One-element container. + { // one_element_c.insert_range(begin, empty_range) + auto& test_case = OneElementContainer_Begin_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // one_element_c.insert_range(end, empty_range) + auto& test_case = OneElementContainer_End_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // one_element_c.insert_range(begin, one_element_range) + auto& test_case = OneElementContainer_Begin_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // one_element_c.insert_range(end, one_element_range) + auto& test_case = OneElementContainer_End_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // one_element_c.insert_range(begin, mid_range) + auto& test_case = OneElementContainer_Begin_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // one_element_c.insert_range(end, mid_range) + auto& test_case = OneElementContainer_End_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + } + + { // Full container. + { // full_container.insert_range(begin, empty_range) + auto& test_case = FullContainer_Begin_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(mid, empty_range) + auto& test_case = FullContainer_Mid_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(end, empty_range) + auto& test_case = FullContainer_End_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(begin, one_element_range) + auto& test_case = FullContainer_Begin_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(end, one_element_range) + auto& test_case = FullContainer_Mid_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(end, one_element_range) + auto& test_case = FullContainer_End_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(begin, mid_range) + auto& test_case = FullContainer_Begin_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(mid, mid_range) + auto& test_case = FullContainer_Mid_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(end, mid_range) + auto& test_case = FullContainer_End_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(begin, long_range) + auto& test_case = FullContainer_Begin_LongRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(mid, long_range) + auto& test_case = FullContainer_Mid_LongRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + + { // full_container.insert_range(end, long_range) + auto& test_case = FullContainer_End_LongRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(std::ranges::equal(c, test_case.expected)); + assert(result == get_pos(c, test_case)); + validate(c); + } + } +} + +template +constexpr void test_sequence_prepend_range(Validate validate) { + using T = typename Container::value_type; + + { // Empty container. + { // empty_c.prepend_range(empty_range) + auto& test_case = EmptyContainer_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // empty_c.prepend_range(one_element_range) + auto& test_case = EmptyContainer_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // empty_c.prepend_range(mid_range) + auto& test_case = EmptyContainer_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + } + + { // One-element container. + { // one_element_c.prepend_range(empty_range) + auto& test_case = OneElementContainer_Begin_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // one_element_c.prepend_range(one_element_range) + auto& test_case = OneElementContainer_Begin_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // one_element_c.prepend_range(mid_range) + auto& test_case = OneElementContainer_Begin_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + } + + { // Full container. + { // full_container.prepend_range(empty_range) + auto& test_case = FullContainer_Begin_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // full_container.prepend_range(one_element_range) + auto& test_case = FullContainer_Begin_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // full_container.prepend_range(mid_range) + auto& test_case = FullContainer_Begin_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // full_container.prepend_range(long_range) + auto& test_case = FullContainer_Begin_LongRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.prepend_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + } +} + +template +constexpr void test_sequence_append_range(Validate validate) { + using T = typename Container::value_type; + + { // Empty container. + { // empty_c.append_range(empty_range) + auto& test_case = EmptyContainer_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // empty_c.append_range(one_element_range) + auto& test_case = EmptyContainer_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // empty_c.append_range(mid_range) + auto& test_case = EmptyContainer_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + } + + { // One-element container. + { // one_element_c.append_range(empty_range) + auto& test_case = OneElementContainer_End_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // one_element_c.append_range(one_element_range) + auto& test_case = OneElementContainer_End_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // one_element_c.append_range(mid_range) + auto& test_case = OneElementContainer_End_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + } + + { // Full container. + { // full_container.append_range(empty_range) + auto& test_case = FullContainer_End_EmptyRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // full_container.append_range(one_element_range) + auto& test_case = FullContainer_End_OneElementRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // full_container.append_range(mid_range) + auto& test_case = FullContainer_End_MidRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + + { // full_container.append_range(long_range) + auto& test_case = FullContainer_End_LongRange; + + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input(test_case.input); + + c.append_range(in); + assert(std::ranges::equal(c, test_case.expected)); + validate(c); + } + } +} + +template +constexpr void test_sequence_assign_range(Validate validate) { + using T = typename Container::value_type; + + auto& initial_empty = EmptyContainer_EmptyRange.initial; + auto& initial_one_element = OneElementContainer_Begin_EmptyRange.initial; + auto& initial_full = FullContainer_Begin_EmptyRange.initial; + auto& input_empty = FullContainer_Begin_EmptyRange.input; + auto& input_one_element = FullContainer_Begin_OneElementRange.input; + auto& input_mid_range = FullContainer_Begin_MidRange.input; + auto& input_long_range = FullContainer_Begin_LongRange.input; + + { // Empty container. + { // empty_container.assign_range(empty_range) + auto& initial = initial_empty; + auto& input = input_empty; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // empty_container.assign_range(one_element_range) + auto& initial = initial_empty; + auto& input = input_one_element; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // empty_container.assign_range(mid_range) + auto& initial = initial_empty; + auto& input = input_mid_range; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // empty_container.assign_range(long_range) + auto& initial = initial_empty; + auto& input = input_long_range; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + } + + { // One-element container. + { // one_element_container.assign_range(empty_range) + auto& initial = initial_one_element; + auto& input = input_empty; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // one_element_container.assign_range(one_element_range) + auto& initial = initial_one_element; + auto& input = input_one_element; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // one_element_container.assign_range(mid_range) + auto& initial = initial_one_element; + auto& input = input_mid_range; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // one_element_container.assign_range(long_range) + auto& initial = initial_one_element; + auto& input = input_long_range; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + } + + { // Full container. + { // full_container.assign_range(empty_range) + auto& initial = initial_full; + auto& input = input_empty; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // full_container.assign_range(one_element_range) + auto& initial = initial_full; + auto& input = input_one_element; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // full_container.assign_range(mid_range) + auto& initial = initial_full; + auto& input = input_mid_range; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + + { // full_container.assign_range(long_range) + auto& initial = initial_full; + auto& input = input_long_range; + + Container c(initial.begin(), initial.end()); + auto in = wrap_input(input); + + c.assign_range(in); + assert(std::ranges::equal(c, input)); + validate(c); + } + } +} + +// Move-only types. + +template