diff --git a/libcxx/include/deque b/libcxx/include/deque --- a/libcxx/include/deque +++ b/libcxx/include/deque @@ -47,6 +47,8 @@ deque(InputIterator f, InputIterator l); template deque(InputIterator f, InputIterator l, const allocator_type& a); + template R> + deque(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 deque(const deque& c); deque(deque&& c) noexcept(is_nothrow_move_constructible::value); @@ -64,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); @@ -107,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); @@ -117,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(); @@ -131,6 +141,10 @@ deque(InputIterator, InputIterator, Allocator = Allocator()) -> deque::value_type, Allocator>; // C++17 +template>> + deque(from_range_t, R&&, Allocator = Allocator()) + -> deque, Allocator>; // C++23 + template bool operator==(const deque& x, const deque& y); template @@ -165,6 +179,7 @@ #include <__algorithm/copy.h> #include <__algorithm/copy_backward.h> +#include <__algorithm/copy_n.h> #include <__algorithm/equal.h> #include <__algorithm/fill_n.h> #include <__algorithm/lexicographical_compare.h> @@ -176,6 +191,7 @@ #include <__assert> // all public C++ headers provide the assertion handler #include <__config> #include <__format/enable_insertable.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> #include <__iterator/prev.h> @@ -187,6 +203,11 @@ #include <__memory/temp_value.h> #include <__memory/unique_ptr.h> #include <__memory_resource/polymorphic_allocator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> +#include <__ranges/size.h> #include <__split_buffer> #include <__type_traits/is_allocator.h> #include <__type_traits/is_convertible.h> @@ -194,6 +215,7 @@ #include <__type_traits/type_identity.h> #include <__utility/forward.h> #include <__utility/move.h> +#include <__utility/pair.h> #include <__utility/swap.h> #include #include @@ -590,6 +612,23 @@ template _LIBCPP_HIDE_FROM_ABI deque(_InputIter __f, _InputIter __l, const allocator_type& __a, typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI deque(from_range_t, _Range&& __range, + const allocator_type& __a = allocator_type()) + : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + __append_with_size(ranges::begin(__range), ranges::distance(__range)); + + } else { + for (auto&& __e : __range) { + emplace_back(std::forward(__e)); + } + } + } +#endif + _LIBCPP_HIDE_FROM_ABI deque(const deque& __c); _LIBCPP_HIDE_FROM_ABI deque(const deque& __c, const __type_identity_t& __a); @@ -622,6 +661,25 @@ 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::random_access_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + __assign_with_size_random_access(ranges::begin(__range), __n); + + } else if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast(ranges::distance(__range)); + __assign_with_size(ranges::begin(__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 @@ -731,6 +789,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 @@ -749,6 +822,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); @@ -881,12 +972,44 @@ return false; } + template + _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __f, _Sentinel __l); + + template + _LIBCPP_HIDE_FROM_ABI + void __assign_with_size_random_access(_RandomAccessIterator __f, difference_type __n); + template + _LIBCPP_HIDE_FROM_ABI + void __assign_with_size(_Iterator __f, 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 + iterator __insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, 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); template _LIBCPP_HIDE_FROM_ABI void __append(_ForIter __f, _ForIter __l, typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type* = 0); + + template + _LIBCPP_HIDE_FROM_ABI void __append_with_size(_InputIterator __from, size_type __n); + template + _LIBCPP_HIDE_FROM_ABI void __append_with_sentinel(_InputIterator __f, _Sentinel __l); + _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); @@ -951,6 +1074,15 @@ -> deque<__iter_value_type<_InputIterator>, _Alloc>; #endif +#if _LIBCPP_STD_VER >= 23 +template >, + class = enable_if_t<__is_allocator<_Alloc>::value> + > +deque(from_range_t, _Range&&, _Alloc = _Alloc()) + -> deque, _Alloc>; +#endif + template deque<_Tp, _Allocator>::deque(size_type __n) : __start_(0), __size_(0, __default_init_tag()) @@ -1115,12 +1247,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); } @@ -1131,14 +1270,41 @@ 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_random_access(__f, __l - __f); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +void deque<_Tp, _Allocator>::__assign_with_size_random_access(_RandomAccessIterator __f, difference_type __n) { + if (static_cast(__n) > size()) { - _RAIter __m = __f + size(); - _VSTD::copy(__f, __m, begin()); - __append(__m, __l); + auto __l = __f + size(); + std::copy(__f, __l, begin()); + __append_with_size(__l, __n - size()); } else - __erase_to_end(_VSTD::copy(__f, __l, begin())); + __erase_to_end(std::copy_n(__f, __n, begin())); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +void deque<_Tp, _Allocator>::__assign_with_size(_Iterator __f, difference_type __n) { + if (static_cast(__n) > size()) { + auto __added_size = __n - size(); + + auto __i = begin(); + while (__n != 0) { + *__i++ = *__f++; + --__n; + } + + __append_with_size(__f, __added_size); + + } else { + __erase_to_end(std::copy_n(__f, __n, begin())); + } } template @@ -1616,8 +1782,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())); } @@ -1628,9 +1802,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())); } @@ -1641,7 +1822,22 @@ 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, size_type __n) { + return __insert_bidirectional(__p, __f, std::next(__f, __n), __n); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +typename deque<_Tp, _Allocator>::iterator +deque<_Tp, _Allocator>::__insert_bidirectional(const_iterator __p, _BiIter __f, _BiIter __l, size_type __n) { size_type __pos = __p - begin(); size_type __to_end = size() - __pos; allocator_type& __a = __alloc(); @@ -1710,6 +1906,13 @@ deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, typename enable_if<__is_exactly_cpp17_input_iterator<_InpIter>::value>::type*) { + __append_with_sentinel(__f, __l); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +void deque<_Tp, _Allocator>::__append_with_sentinel(_InputIterator __f, _Sentinel __l) { for (; __f != __l; ++__f) #ifdef _LIBCPP_CXX03_LANG push_back(*__f); @@ -1724,11 +1927,18 @@ deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l, typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type*) { - size_type __n = _VSTD::distance(__f, __l); + __append_with_size(__f, std::distance(__f, __l)); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +void deque<_Tp, _Allocator>::__append_with_size(_InputIterator __f, size_type __n) { allocator_type& __a = __alloc(); size_type __back_capacity = __back_spare(); if (__n > __back_capacity) __add_back_capacity(__n - __back_capacity); + // __n <= __back_capacity for (__deque_block_range __br : __deque_range(end(), end() + __n)) { _ConstructTransaction __tx(this, __br); diff --git a/libcxx/include/queue b/libcxx/include/queue --- a/libcxx/include/queue +++ b/libcxx/include/queue @@ -43,6 +43,7 @@ explicit queue(container_type&& c) template queue(InputIterator first, InputIterator last); // since C++23 + template R> queue(from_range_t, R&& rg); // since C++23 template explicit queue(const Alloc& a); template @@ -55,6 +56,8 @@ queue(queue&& q, const Alloc& a); template queue(InputIterator first, InputIterator last, const Alloc&); // since C++23 + template R, class Alloc> + queue(from_range_t, R&& rg, const Alloc&); // since C++23 bool empty() const; size_type size() const; @@ -66,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(); @@ -78,6 +83,9 @@ template queue(InputIterator, InputIterator) -> queue>; // since C++23 +template + queue(from_range_t, R&&) -> queue>; // since C++23 + template queue(Container, Allocator) -> queue; // C++17 @@ -86,6 +94,10 @@ -> queue, deque, Allocator>>; // since C++23 +template + queue(from_range_t, R&&, Allocator) + -> queue, deque, Allocator>>; // since C++23 + template bool operator==(const queue& x,const queue& y); @@ -138,6 +150,8 @@ template priority_queue(InputIterator first, InputIterator last, const Compare& comp, Container&& c); + template R> + priority_queue(from_range_t, R&& rg, const Compare& x = Compare()); // since C++23 template explicit priority_queue(const Alloc& a); template @@ -160,6 +174,10 @@ template priority_queue(InputIterator first, InputIterator last, const Compare& comp, Container&& c, const Alloc& a); + template R, class Alloc> + priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&); // since C++23 + template R, class Alloc> + priority_queue(from_range_t, R&& rg, const Alloc&); // since C++23 template priority_queue(const priority_queue& q, const Alloc& a); template @@ -171,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(); @@ -189,6 +209,10 @@ priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container()) -> priority_queue, Container, Compare>; // C++17 +template>> + priority_queue(from_range_t, R&&, Compare = Compare()) + -> priority_queue, vector>, Compare>; // C++23 + template priority_queue(Compare, Container, Allocator) -> priority_queue; // C++17 @@ -208,6 +232,15 @@ priority_queue(InputIterator, InputIterator, Compare, Container, Allocator) -> priority_queue; // C++17 +template + priority_queue(from_range_t, R&&, Compare, Allocator) + -> priority_queue, vector, Allocator>, + Compare>; // C++23 + +template + priority_queue(from_range_t, R&&, Allocator) + -> priority_queue, vector, Allocator>>; // C++23 + template void swap(priority_queue& x, priority_queue& y) @@ -220,11 +253,17 @@ #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> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> #include <__utility/forward.h> #include #include @@ -283,12 +322,24 @@ _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {} + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {} + template ::value>, class = __enable_if_t::value>> _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc) : c(__first, __second, __alloc) {} + + template <_ContainerCompatibleRange<_Tp> _Range, + class _Alloc, + class = __enable_if_t::value>> + _LIBCPP_HIDE_FROM_ABI + queue(from_range_t, _Range&& __range, const _Alloc& __alloc) + : c(from_range, std::forward<_Range>(__range), __alloc) {} + #endif _LIBCPP_INLINE_VISIBILITY @@ -360,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 @@ -418,12 +484,22 @@ queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>; +template +queue(from_range_t, _Range&&) + -> queue>; + template ::value>, class = __enable_if_t<__is_allocator<_Alloc>::value>> queue(_InputIterator, _InputIterator, _Alloc) -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>; + +template ::value>> +queue(from_range_t, _Range&&, _Alloc) + -> queue, deque, _Alloc>>; #endif template @@ -557,6 +633,17 @@ priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c); #endif // _LIBCPP_CXX03_LANG + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare()) + : c(from_range, std::forward<_Range>(__range)), + comp(__comp) { + std::make_heap(c.begin(), c.end(), comp); + } +#endif + template _LIBCPP_INLINE_VISIBILITY explicit priority_queue(const _Alloc& __a, @@ -611,6 +698,30 @@ __enable_if_t::value>* = 0); #endif // _LIBCPP_CXX03_LANG +#if _LIBCPP_STD_VER >= 23 + + template <_ContainerCompatibleRange<_Tp> _Range, + class _Alloc, + class = enable_if_t::value>> + _LIBCPP_HIDE_FROM_ABI + priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a) + : c(from_range, std::forward<_Range>(__range), __a), + comp(__comp) { + std::make_heap(c.begin(), c.end(), comp); + } + + template <_ContainerCompatibleRange<_Tp> _Range, + class _Alloc, + class = enable_if_t::value>> + _LIBCPP_HIDE_FROM_ABI + priority_queue(from_range_t, _Range&& __range, const _Alloc& __a) + : c(from_range, std::forward<_Range>(__range), __a), + comp() { + std::make_heap(c.begin(), c.end(), comp); + } + +#endif + _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY bool empty() const {return c.empty();} _LIBCPP_INLINE_VISIBILITY @@ -623,6 +734,23 @@ #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)); + } + + std::make_heap(c.begin(), c.end(), comp); + } +#endif + template _LIBCPP_INLINE_VISIBILITY void emplace(_Args&&... __args); @@ -695,6 +823,31 @@ -> priority_queue; #endif +#if _LIBCPP_STD_VER >= 23 + +template >, + class = enable_if_t::value>> +priority_queue(from_range_t, _Range&&, _Compare = _Compare()) + -> priority_queue, vector>, _Compare>; + +template ::value>, + class = enable_if_t<__is_allocator<_Alloc>::value>> +priority_queue(from_range_t, _Range&&, _Compare, _Alloc) + -> priority_queue, vector, _Alloc>, + _Compare>; + +template ::value>> +priority_queue(from_range_t, _Range&&, _Alloc) + -> priority_queue, vector, _Alloc>>; + +#endif + template inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, diff --git a/libcxx/include/stack b/libcxx/include/stack --- a/libcxx/include/stack +++ b/libcxx/include/stack @@ -42,6 +42,7 @@ explicit stack(const container_type& c); explicit stack(container_type&& c); template stack(InputIterator first, InputIterator last); // since C++23 + template R> stack(from_range_t, R&& rg); // since C++23 template explicit stack(const Alloc& a); template stack(const container_type& c, const Alloc& a); template stack(container_type&& c, const Alloc& a); @@ -49,6 +50,8 @@ template stack(stack&& c, const Alloc& a); template stack(InputIterator first, InputIterator last, const Alloc&); // since C++23 + template R, class Alloc> + stack(from_range_t, R&& rg, const Alloc&); // since C++23 bool empty() const; size_type size() const; @@ -57,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(); @@ -69,6 +74,9 @@ template stack(InputIterator, InputIterator) -> stack>; // since C++23 +template + stack(from_range_t, R&&) -> stack>; // since C++23 + template stack(Container, Allocator) -> stack; // C++17 @@ -77,6 +85,10 @@ -> stack, deque, Allocator>>; // since C++23 +template + stack(from_range_t, R&&, Allocator) + -> stack, deque, Allocator>>; // since C++23 + template bool operator==(const stack& x, const stack& y); template @@ -98,10 +110,16 @@ */ +#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> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> #include <__type_traits/is_same.h> #include <__utility/forward.h> #include @@ -210,12 +228,24 @@ _LIBCPP_HIDE_FROM_ABI stack(_InputIterator __first, _InputIterator __last) : c(__first, __last) {} + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + stack(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {} + template ::value>, class = __enable_if_t::value>> _LIBCPP_HIDE_FROM_ABI stack(_InputIterator __first, _InputIterator __last, const _Alloc& __alloc) : c(__first, __last, __alloc) {} + + template <_ContainerCompatibleRange<_Tp> _Range, + class _Alloc, + class = __enable_if_t::value>> + _LIBCPP_HIDE_FROM_ABI + stack(from_range_t, _Range&& __range, const _Alloc& __alloc) + : c(from_range, std::forward<_Range>(__range), __alloc) {} + #endif _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY @@ -233,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 @@ -290,12 +334,22 @@ stack(_InputIterator, _InputIterator) -> stack<__iter_value_type<_InputIterator>>; +template +stack(from_range_t, _Range&&) -> stack>; + template::value>, class = __enable_if_t<__is_allocator<_Alloc>::value>> stack(_InputIterator, _InputIterator, _Alloc) -> stack<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>; + +template ::value>> +stack(from_range_t, _Range&&, _Alloc) + -> stack, deque, _Alloc>>; + #endif template diff --git a/libcxx/test/std/containers/container.adaptors/from_range_container_adaptors.h b/libcxx/test/std/containers/container.adaptors/from_range_container_adaptors.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/container.adaptors/from_range_container_adaptors.h @@ -0,0 +1,229 @@ +//===----------------------------------------------------------------------===// +// +// 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_FROM_RANGE_CONTAINER_ADAPTORS_H +#define SUPPORT_FROM_RANGE_CONTAINER_ADAPTORS_H + +#include +#include +#include +#include +#include +#include +#include + +#include "../from_range_helpers.h" +#include "MoveOnly.h" +#include "almost_satisfies_types.h" +#include "count_new.h" +#include "test_macros.h" +#include "unwrap_container_adaptor.h" + +template +concept HasFromRangeCtr = requires (Range&& range) { + Container(std::from_range, std::forward(range)); + Container(std::from_range, std::forward(range), std::allocator()); +}; + +template