diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -465,6 +465,7 @@ __iterator/permutable.h __iterator/prev.h __iterator/projected.h + __iterator/ranges_iterator_traits.h __iterator/readable_traits.h __iterator/reverse_access.h __iterator/reverse_iterator.h diff --git a/libcxx/include/__iterator/ranges_iterator_traits.h b/libcxx/include/__iterator/ranges_iterator_traits.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/ranges_iterator_traits.h @@ -0,0 +1,42 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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 _LIBCPP___ITERATOR_RANGES_ITERATOR_TRAITS_H +#define _LIBCPP___ITERATOR_RANGES_ITERATOR_TRAITS_H + +#include <__config> +#include <__fwd/pair.h> +#include <__ranges/concepts.h> +#include <__type_traits/add_const.h> +#include <__type_traits/remove_const.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 23 + +template +using __range_key_type = __remove_const_t::first_type>; + +template +using __range_mapped_type = typename ranges::range_value_t<_Range>::second_type; + +template +using __range_to_alloc_type = + pair::first_type>, + typename ranges::range_value_t<_Range>::second_type>; + +#endif + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ITERATOR_RANGES_ITERATOR_TRAITS_H diff --git a/libcxx/include/forward_list b/libcxx/include/forward_list --- a/libcxx/include/forward_list +++ b/libcxx/include/forward_list @@ -44,6 +44,8 @@ forward_list(InputIterator first, InputIterator last); template forward_list(InputIterator first, InputIterator last, const allocator_type& a); + template R> + forward_list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 forward_list(const forward_list& x); forward_list(const forward_list& x, const allocator_type& a); forward_list(forward_list&& x) @@ -63,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); @@ -89,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(); @@ -100,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); @@ -140,6 +148,10 @@ forward_list(InputIterator, InputIterator, Allocator = Allocator()) -> forward_list::value_type, Allocator>; // C++17 +template>> + forward_list(from_range_t, R&&, Allocator = Allocator()) + -> forward_list, Allocator>; // C++23 + template bool operator==(const forward_list& x, const forward_list& y); @@ -204,6 +216,10 @@ #include <__memory/swap_allocator.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 <__type_traits/conditional.h> #include <__type_traits/is_allocator.h> #include <__type_traits/is_const.h> @@ -722,6 +738,15 @@ _LIBCPP_HIDE_FROM_ABI forward_list(_InputIterator __f, _InputIterator __l, const allocator_type& __a, __enable_if_t<__has_input_iterator_category<_InputIterator>::value>* = nullptr); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI forward_list(from_range_t, _Range&& __range, + const allocator_type& __a = allocator_type()) : base(__a) { + prepend_range(std::forward<_Range>(__range)); + } +#endif + _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x); _LIBCPP_HIDE_FROM_ABI forward_list(const forward_list& __x, const __type_identity_t& __a); @@ -755,6 +780,15 @@ template __enable_if_t<__has_input_iterator_category<_InputIterator>::value, void> _LIBCPP_HIDE_FROM_ABI 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 + _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __v); _LIBCPP_INLINE_VISIBILITY @@ -818,6 +852,14 @@ #endif // _LIBCPP_CXX03_LANG _LIBCPP_HIDE_FROM_ABI 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 + _LIBCPP_HIDE_FROM_ABI void pop_front(); #ifndef _LIBCPP_CXX03_LANG @@ -835,6 +877,18 @@ __enable_if_t<__has_input_iterator_category<_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_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l); + _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __p); _LIBCPP_HIDE_FROM_ABI iterator erase_after(const_iterator __f, const_iterator __l); @@ -896,6 +950,10 @@ _LIBCPP_HIDE_FROM_ABI 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 _LIBCPP_HIDE_FROM_ABI __node_pointer @@ -927,6 +985,15 @@ -> forward_list<__iter_value_type<_InputIterator>, _Alloc>; #endif +#if _LIBCPP_STD_VER >= 23 +template >, + class = enable_if_t<__is_allocator<_Alloc>::value> + > +forward_list(from_range_t, _Range&&, _Alloc = _Alloc()) + -> forward_list, _Alloc>; +#endif + template inline forward_list<_Tp, _Alloc>::forward_list(const allocator_type& __a) @@ -1107,13 +1174,20 @@ __enable_if_t<__has_input_iterator_category<_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); } @@ -1307,9 +1381,17 @@ forward_list<_Tp, _Alloc>::insert_after(const_iterator __p, _InputIterator __f, _InputIterator __l) { - using _Guard = __allocation_guard<__node_allocator>; + return __insert_after_with_sentinel(__p, std::move(__f), std::move(__l)); +} +template +template +_LIBCPP_HIDE_FROM_ABI +typename forward_list<_Tp, _Alloc>::iterator +forward_list<_Tp, _Alloc>::__insert_after_with_sentinel(const_iterator __p, _InputIterator __f, _Sentinel __l) { + using _Guard = __allocation_guard<__node_allocator>; __begin_node_pointer __r = __p.__get_begin(); + if (__f != __l) { __node_allocator& __a = base::__alloc(); @@ -1321,6 +1403,7 @@ __first = __h.__release_ptr(); } __node_pointer __last = __first; + #ifndef _LIBCPP_HAS_NO_EXCEPTIONS try { @@ -1346,10 +1429,12 @@ throw; } #endif // _LIBCPP_HAS_NO_EXCEPTIONS + __last->__next_ = __r->__next_; __r->__next_ = __first; __r = static_cast<__begin_node_pointer>(__last); } + return iterator(__r); } diff --git a/libcxx/include/list b/libcxx/include/list --- a/libcxx/include/list +++ b/libcxx/include/list @@ -46,6 +46,8 @@ list(Iter first, Iter last); template list(Iter first, Iter last, const allocator_type& a); + template R> + list(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 list(const list& x); list(const list&, const allocator_type& a); list(list&& x) @@ -64,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); @@ -99,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); @@ -108,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); @@ -152,6 +162,10 @@ list(InputIterator, InputIterator, Allocator = Allocator()) -> list::value_type, Allocator>; // C++17 +template>> + list(from_range_t, R&&, Allocator = Allocator()) + -> list, Allocator>; // C++23 + template bool operator==(const list& x, const list& y); template @@ -207,6 +221,10 @@ #include <__memory/swap_allocator.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 <__type_traits/conditional.h> #include <__type_traits/is_allocator.h> #include <__type_traits/is_nothrow_default_constructible.h> @@ -761,6 +779,14 @@ _LIBCPP_HIDE_FROM_ABI list(_InpIter __f, _InpIter __l, const allocator_type& __a, __enable_if_t<__has_input_iterator_category<_InpIter>::value>* = 0); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI list(from_range_t, _Range&& __range, + const allocator_type& __a = allocator_type()) : base(__a) { + prepend_range(std::forward<_Range>(__range)); + } +#endif + _LIBCPP_HIDE_FROM_ABI list(const list& __c); _LIBCPP_HIDE_FROM_ABI list(const list& __c, const __type_identity_t& __a); _LIBCPP_INLINE_VISIBILITY @@ -792,6 +818,15 @@ template _LIBCPP_HIDE_FROM_ABI void assign(_InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_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 + _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x); _LIBCPP_INLINE_VISIBILITY @@ -870,6 +905,20 @@ _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x); _LIBCPP_HIDE_FROM_ABI 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 _LIBCPP_HIDE_FROM_ABI reference emplace_front(_Args&&... __args); @@ -910,6 +959,14 @@ _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_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 @@ -986,6 +1043,14 @@ } private: + template + _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __f, _Sentinel __l); + + template + _LIBCPP_HIDE_FROM_ABI + 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 @@ -1020,6 +1085,15 @@ -> list<__iter_value_type<_InputIterator>, _Alloc>; #endif +#if _LIBCPP_STD_VER >= 23 +template >, + class = enable_if_t<__is_allocator<_Alloc>::value> + > +list(from_range_t, _Range&&, _Alloc = _Alloc()) + -> list, _Alloc>; +#endif + // Link in nodes [__f, __l] just prior to __p template inline @@ -1225,12 +1299,19 @@ list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_InpIter>::value>*) { + __assign_with_sentinel(__f, __l); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +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); } @@ -1324,6 +1405,14 @@ list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, __enable_if_t<__has_input_iterator_category<_InpIter>::value>*) { + return __insert_with_sentinel(__p, __f, __l); +} + +template +template +_LIBCPP_HIDE_FROM_ABI +typename list<_Tp, _Alloc>::iterator +list<_Tp, _Alloc>::__insert_with_sentinel(const_iterator __p, _Iterator __f, _Sentinel __l) { iterator __r(__p.__ptr_); if (__f != __l) { diff --git a/libcxx/include/map b/libcxx/include/map --- a/libcxx/include/map +++ b/libcxx/include/map @@ -70,6 +70,8 @@ template map(InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a); + template R> + map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 map(const map& m); map(map&& m) noexcept( @@ -83,6 +85,9 @@ template map(InputIterator first, InputIterator last, const allocator_type& a) : map(first, last, Compare(), a) {} // C++14 + template R> + map(from_range_t, R&& rg, const Allocator& a)) + : map(from_range, std::forward(rg), Compare(), a) { } // C++23 map(initializer_list il, const allocator_type& a) : map(il, Compare(), a) {} // C++14 ~map(); @@ -138,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 @@ -229,6 +236,11 @@ map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator()) -> map, iter_val_t, Compare, Allocator>; // C++17 +template, + class Allocator = allocator>> + map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) + -> map, range-mapped-type, Compare, Allocator>; // C++23 + template, class Allocator = allocator>> map(initializer_list>, Compare = Compare(), Allocator = Allocator()) @@ -239,6 +251,10 @@ -> map, iter_val_t, less>, Allocator>; // C++17 +template + map(from_range_t, R&&, Allocator) + -> map, range-mapped-type, less>, Allocator>; // C++23 + template map(initializer_list>, Allocator) -> map, Allocator>; // C++17 @@ -338,6 +354,9 @@ template multimap(InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a); + template R> + multimap(from_range_t, R&& rg, + const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 multimap(const multimap& m); multimap(multimap&& m) noexcept( @@ -352,6 +371,9 @@ template multimap(InputIterator first, InputIterator last, const allocator_type& a) : multimap(first, last, Compare(), a) {} // C++14 + template R> + multimap(from_range_t, R&& rg, const Allocator& a)) + : multimap(from_range, std::forward(rg), Compare(), a) { } // C++23 multimap(initializer_list il, const allocator_type& a) : multimap(il, Compare(), a) {} // C++14 ~multimap(); @@ -400,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 @@ -474,6 +498,11 @@ multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator()) -> multimap, iter_val_t, Compare, Allocator>; // C++17 +template>, + class Allocator = allocator>> + multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) + -> multimap, range-mapped-type, Compare, Allocator>; // C++23 + template, class Allocator = allocator>> multimap(initializer_list>, Compare = Compare(), Allocator = Allocator()) @@ -484,6 +513,10 @@ -> multimap, iter_val_t, less>, Allocator>; // C++17 +template + multimap(from_range_t, R&&, Allocator) + -> multimap, range-mapped-type, less>, Allocator>; // C++23 + template multimap(initializer_list>, Allocator) -> multimap, Allocator>; // C++17 @@ -549,11 +582,15 @@ #include <__functional/operations.h> #include <__iterator/erase_if_container.h> #include <__iterator/iterator_traits.h> +#include <__iterator/ranges_iterator_traits.h> #include <__iterator/reverse_iterator.h> #include <__memory/addressof.h> #include <__memory/allocator.h> #include <__memory_resource/polymorphic_allocator.h> #include <__node_handle> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> #include <__tree> #include <__type_traits/is_allocator.h> #include <__utility/forward.h> @@ -1079,6 +1116,16 @@ insert(__f, __l); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + map(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(), + const allocator_type& __a = allocator_type()) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { + insert_range(std::forward<_Range>(__range)); + } +#endif + #if _LIBCPP_STD_VER >= 14 template _LIBCPP_INLINE_VISIBILITY @@ -1086,6 +1133,13 @@ : map(__f, __l, key_compare(), __a) {} #endif +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + map(from_range_t, _Range&& __range, const allocator_type& __a) + : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY map(const map& __m) : __tree_(__m.__tree_) @@ -1285,6 +1339,17 @@ insert(__e.__i_, *__f); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + const_iterator __end = cend(); + for (auto&& __element : __range) { + insert(__end.__i_, std::forward(__element)); + } + } +#endif + #if _LIBCPP_STD_VER >= 17 template @@ -1570,6 +1635,15 @@ map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Allocator = allocator<__range_to_alloc_type<_Range>>, + class = enable_if_t::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> +map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) + -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; +#endif + template>, class _Allocator = allocator>, class = enable_if_t::value, void>, @@ -1584,6 +1658,13 @@ -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, less<__iter_key_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template ::value, void>> +map(from_range_t, _Range&&, _Allocator) + -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; +#endif + template::value, void>> map(initializer_list>, _Allocator) @@ -1875,6 +1956,16 @@ insert(__f, __l); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + multimap(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(), + const allocator_type& __a = allocator_type()) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { + insert_range(std::forward<_Range>(__range)); + } +#endif + #if _LIBCPP_STD_VER >= 14 template _LIBCPP_INLINE_VISIBILITY @@ -1882,6 +1973,13 @@ : multimap(__f, __l, key_compare(), __a) {} #endif +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + multimap(from_range_t, _Range&& __range, const allocator_type& __a) + : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY multimap(const multimap& __m) : __tree_(__m.__tree_.value_comp(), @@ -2072,6 +2170,17 @@ __tree_.__insert_multi(__e.__i_, *__f); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + const_iterator __end = cend(); + for (auto&& __element : __range) { + __tree_.__insert_multi(__end.__i_, std::forward(__element)); + } + } +#endif + _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} _LIBCPP_INLINE_VISIBILITY @@ -2256,6 +2365,15 @@ multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Allocator = allocator<__range_to_alloc_type<_Range>>, + class = enable_if_t::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> +multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) + -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; +#endif + template>, class _Allocator = allocator>, class = enable_if_t::value, void>, @@ -2270,6 +2388,13 @@ -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, less<__iter_key_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template ::value, void>> +multimap(from_range_t, _Range&&, _Allocator) + -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; +#endif + template::value, void>> multimap(initializer_list>, _Allocator) diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1146,55 +1146,63 @@ export type_traits.is_reference export type_traits.remove_cvref } - module counted_iterator { private header "__iterator/counted_iterator.h" } - module data { private header "__iterator/data.h" } - module default_sentinel { private header "__iterator/default_sentinel.h" } - module distance { + module counted_iterator { private header "__iterator/counted_iterator.h" } + module data { private header "__iterator/data.h" } + module default_sentinel { private header "__iterator/default_sentinel.h" } + module distance { private header "__iterator/distance.h" export ranges.__ranges.size } - module empty { private header "__iterator/empty.h" } - module erase_if_container { private header "__iterator/erase_if_container.h" } - module front_insert_iterator { private header "__iterator/front_insert_iterator.h" } - module incrementable_traits { private header "__iterator/incrementable_traits.h" } - module indirectly_comparable { private header "__iterator/indirectly_comparable.h" } - module insert_iterator { private header "__iterator/insert_iterator.h" } - module istream_iterator { private header "__iterator/istream_iterator.h" } - module istreambuf_iterator { private header "__iterator/istreambuf_iterator.h" } - module iter_move { private header "__iterator/iter_move.h" } - module iter_swap { private header "__iterator/iter_swap.h" } - module iterator { private header "__iterator/iterator.h" } - module iterator_traits { + module empty { private header "__iterator/empty.h" } + module erase_if_container { private header "__iterator/erase_if_container.h" } + module front_insert_iterator { private header "__iterator/front_insert_iterator.h" } + module incrementable_traits { private header "__iterator/incrementable_traits.h" } + module indirectly_comparable { private header "__iterator/indirectly_comparable.h" } + module insert_iterator { private header "__iterator/insert_iterator.h" } + module istream_iterator { private header "__iterator/istream_iterator.h" } + module istreambuf_iterator { private header "__iterator/istreambuf_iterator.h" } + module iter_move { private header "__iterator/iter_move.h" } + module iter_swap { private header "__iterator/iter_swap.h" } + module iterator { private header "__iterator/iterator.h" } + module iterator_traits { private header "__iterator/iterator_traits.h" export type_traits.is_primary_template } - module iterator_with_data { private header "__iterator/iterator_with_data.h" } + module iterator_with_data { private header "__iterator/iterator_with_data.h" } module mergeable { private header "__iterator/mergeable.h" export functional.__functional.ranges_operations } - module move_iterator { private header "__iterator/move_iterator.h" } - module move_sentinel { private header "__iterator/move_sentinel.h" } - module next { private header "__iterator/next.h" } - module ostream_iterator { private header "__iterator/ostream_iterator.h" } - module ostreambuf_iterator { + module move_iterator { private header "__iterator/move_iterator.h" } + module move_sentinel { private header "__iterator/move_sentinel.h" } + module next { private header "__iterator/next.h" } + module ostream_iterator { private header "__iterator/ostream_iterator.h" } + module ostreambuf_iterator { private header "__iterator/ostreambuf_iterator.h" export iosfwd } - module permutable { private header "__iterator/permutable.h" } - module prev { private header "__iterator/prev.h" } - module projected { private header "__iterator/projected.h" } - module readable_traits { private header "__iterator/readable_traits.h" } - module reverse_access { private header "__iterator/reverse_access.h" } - module reverse_iterator { private header "__iterator/reverse_iterator.h" } - module segmented_iterator { private header "__iterator/segmented_iterator.h" } - module size { private header "__iterator/size.h" } + module permutable { private header "__iterator/permutable.h" } + module prev { private header "__iterator/prev.h" } + module projected { private header "__iterator/projected.h" } + module ranges_iterator_traits { private header "__iterator/ranges_iterator_traits.h" } + module reverse_access { private header "__iterator/reverse_access.h" } + module reverse_iterator { private header "__iterator/reverse_iterator.h" } + module segmented_iterator { private header "__iterator/segmented_iterator.h" } + module size { private header "__iterator/size.h" } + module permutable { private header "__iterator/permutable.h" } + module prev { private header "__iterator/prev.h" } + module projected { private header "__iterator/projected.h" } + module readable_traits { private header "__iterator/readable_traits.h" } + module reverse_access { private header "__iterator/reverse_access.h" } + module reverse_iterator { private header "__iterator/reverse_iterator.h" } + module segmented_iterator { private header "__iterator/segmented_iterator.h" } + module size { private header "__iterator/size.h" } module sortable { private header "__iterator/sortable.h" export functional.__functional.ranges_operations } - module unreachable_sentinel { private header "__iterator/unreachable_sentinel.h" } - module wrap_iter { private header "__iterator/wrap_iter.h" } + module unreachable_sentinel { private header "__iterator/unreachable_sentinel.h" } + module wrap_iter { private header "__iterator/wrap_iter.h" } } } module latch { diff --git a/libcxx/include/set b/libcxx/include/set --- a/libcxx/include/set +++ b/libcxx/include/set @@ -56,6 +56,8 @@ template set(InputIterator first, InputIterator last, const value_compare& comp, const allocator_type& a); + template R> + set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 set(const set& s); set(set&& s) noexcept( @@ -70,6 +72,9 @@ template set(InputIterator first, InputIterator last, const allocator_type& a) : set(first, last, Compare(), a) {} // C++14 + template R> + set(from_range_t, R&& rg, const Allocator& a)) + : set(from_range, std::forward(rg), Compare(), a) { } // C++23 set(initializer_list il, const allocator_type& a) : set(il, Compare(), a) {} // C++14 ~set(); @@ -114,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 @@ -190,6 +197,11 @@ Compare = Compare(), Allocator = Allocator()) -> set::value_type, Compare, Allocator>; // C++17 +template>, + class Allocator = allocator>> + set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) + -> set, Compare, Allocator>; // C++23 + template, class Allocator = allocator> set(initializer_list, Compare = Compare(), Allocator = Allocator()) -> set; // C++17 @@ -199,6 +211,10 @@ -> set::value_type, less::value_type>, Allocator>; // C++17 +template + set(from_range_t, R&&, Allocator) + -> set, less>, Allocator>; // C++23 + template set(initializer_list, Allocator) -> set, Allocator>; // C++17 @@ -284,6 +300,9 @@ template multiset(InputIterator first, InputIterator last, const value_compare& comp, const allocator_type& a); + template R> + multiset(from_range_t, R&& rg, + const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 multiset(const multiset& s); multiset(multiset&& s) noexcept( @@ -298,6 +317,9 @@ template multiset(InputIterator first, InputIterator last, const allocator_type& a) : set(first, last, Compare(), a) {} // C++14 + template R> + multiset(from_range_t, R&& rg, const Allocator& a)) + : multiset(from_range, std::forward(rg), Compare(), a) { } // C++23 multiset(initializer_list il, const allocator_type& a) : set(il, Compare(), a) {} // C++14 ~multiset(); @@ -342,6 +364,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 @@ -419,6 +443,11 @@ Compare = Compare(), Allocator = Allocator()) -> multiset::value_type, Compare, Allocator>; // C++17 +template>, + class Allocator = allocator>> + multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) + -> multiset, Compare, Allocator>; + template, class Allocator = allocator> multiset(initializer_list, Compare = Compare(), Allocator = Allocator()) -> multiset; // C++17 @@ -428,6 +457,10 @@ -> multiset::value_type, less::value_type>, Allocator>; // C++17 +template + multiset(from_range_t, R&&, Allocator) + -> multiset, less>, Allocator>; + template multiset(initializer_list, Allocator) -> multiset, Allocator>; // C++17 @@ -489,10 +522,14 @@ #include <__functional/operations.h> #include <__iterator/erase_if_container.h> #include <__iterator/iterator_traits.h> +#include <__iterator/ranges_iterator_traits.h> #include <__iterator/reverse_iterator.h> #include <__memory/allocator.h> #include <__memory_resource/polymorphic_allocator.h> #include <__node_handle> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> #include <__tree> #include <__type_traits/is_allocator.h> #include <__utility/forward.h> @@ -603,6 +640,16 @@ insert(__f, __l); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + set(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(), + const allocator_type& __a = allocator_type()) + : __tree_(__comp, __a) { + insert_range(std::forward<_Range>(__range)); + } +#endif + #if _LIBCPP_STD_VER >= 14 template _LIBCPP_INLINE_VISIBILITY @@ -610,6 +657,13 @@ : set(__f, __l, key_compare(), __a) {} #endif +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + set(from_range_t, _Range&& __range, const allocator_type& __a) + : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY set(const set& __s) : __tree_(__s.__tree_) @@ -752,6 +806,17 @@ __tree_.__insert_unique(__e, *__f); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + const_iterator __end = cend(); + for (auto&& __element : __range) { + __tree_.__insert_unique(__end, std::forward(__element)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY pair insert(value_type&& __v) @@ -947,6 +1012,15 @@ set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Allocator = allocator>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>, + class = enable_if_t::value, void>> +set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) + -> set, _Compare, _Allocator>; +#endif + template, class _Allocator = allocator<_Key>, class = enable_if_t::value, void>, @@ -961,6 +1035,13 @@ -> set<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template ::value, void>> +set(from_range_t, _Range&&, _Allocator) + -> set, less>, _Allocator>; +#endif + template::value, void>> set(initializer_list<_Key>, _Allocator) @@ -1160,6 +1241,21 @@ insert(__f, __l); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + multiset(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(), + const allocator_type& __a = allocator_type()) + : __tree_(__comp, __a) { + insert_range(std::forward<_Range>(__range)); + } + + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + multiset(from_range_t, _Range&& __range, const allocator_type& __a) + : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY multiset(const multiset& __s) : __tree_(__s.__tree_.value_comp(), @@ -1301,6 +1397,17 @@ __tree_.__insert_multi(__e, *__f); } +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + const_iterator __end = cend(); + for (auto&& __element : __range) { + __tree_.__insert_multi(__end, std::forward(__element)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator insert(value_type&& __v) @@ -1496,6 +1603,15 @@ multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Allocator = allocator>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>, + class = enable_if_t::value, void>> +multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) + -> multiset, _Compare, _Allocator>; +#endif + template, class _Allocator = allocator<_Key>, class = enable_if_t<__is_allocator<_Allocator>::value, void>, @@ -1510,6 +1626,13 @@ -> multiset<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template ::value, void>> +multiset(from_range_t, _Range&&, _Allocator) + -> multiset, less>, _Allocator>; +#endif + template::value, void>> multiset(initializer_list<_Key>, _Allocator) diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map --- a/libcxx/include/unordered_map +++ b/libcxx/include/unordered_map @@ -59,6 +59,11 @@ size_type n = 0, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); + template R> + unordered_map(from_range_t, R&& rg, size_type n = see below, + const hasher& hf = hasher(), const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); // C++23 + explicit unordered_map(const allocator_type&); unordered_map(const unordered_map&); unordered_map(const unordered_map&, const Allocator&); @@ -82,6 +87,12 @@ unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a) : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 + template R> + unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a) + : unordered_map(from_range, std::forward(rg), n, hasher(), key_equal(), a) { } // C++23 + template R> + unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) + : unordered_map(from_range, std::forward(rg), n, hf, key_equal(), a) { } // C++23 unordered_map(initializer_list il, size_type n, const allocator_type& a) : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 unordered_map(initializer_list il, size_type n, const hasher& hf, @@ -122,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 @@ -224,6 +237,13 @@ -> unordered_map, iter_value_t, Hash, Pred, Allocator>; // C++17 +template>, + class Pred = equal_to>, + class Allocator = allocator>> + unordered_map(from_range_t, R&&, typename see below::size_type = see below, + Hash = Hash(), Pred = Pred(), Allocator = Allocator()) + -> unordered_map, range-mapped-type, Hash, Pred, Allocator>; // C++23 + template, class Pred = equal_to, class Allocator = allocator>> unordered_map(initializer_list>, typename see below::size_type = see below, @@ -245,6 +265,21 @@ -> unordered_map, iter_val_t, Hash, equal_to>, Allocator>; // C++17 +template + unordered_map(from_range_t, R&&, typename see below::size_type, Allocator) + -> unordered_map, range-mapped-type, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_map(from_range_t, R&&, Allocator) + -> unordered_map, range-mapped-type, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator) + -> unordered_map, range-mapped-type, Hash, + equal_to>, Allocator>; // C++23 + template unordered_map(initializer_list>, typename see below::size_type, Allocator) -> unordered_map, equal_to, Allocator>; // C++17 @@ -311,6 +346,10 @@ size_type n = 0, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); + template R> + unordered_multimap(from_range_t, R&& rg, size_type n = see below, + const hasher& hf = hasher(), const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); // C++23 explicit unordered_multimap(const allocator_type&); unordered_multimap(const unordered_multimap&); unordered_multimap(const unordered_multimap&, const Allocator&); @@ -334,6 +373,12 @@ unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a) : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 + template R> + unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a) + : unordered_multimap(from_range, std::forward(rg), n, hasher(), key_equal(), a) { } // C++23 + template R> + unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) + : unordered_multimap(from_range, std::forward(rg), n, hf, key_equal(), a) { } // C++23 unordered_multimap(initializer_list il, size_type n, const allocator_type& a) : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 unordered_multimap(initializer_list il, size_type n, const hasher& hf, @@ -374,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 @@ -453,6 +500,13 @@ -> unordered_multimap, iter_value_t, Hash, Pred, Allocator>; // C++17 +template>, + class Pred = equal_to>, + class Allocator = allocator>> + unordered_multimap(from_range_t, R&&, typename see below::size_type = see below, + Hash = Hash(), Pred = Pred(), Allocator = Allocator()) + -> unordered_multimap, range-mapped-type, Hash, Pred, Allocator>; // C++23 + template, class Pred = equal_to, class Allocator = allocator>> unordered_multimap(initializer_list>, typename see below::size_type = see below, @@ -474,6 +528,21 @@ -> unordered_multimap, iter_val_t, Hash, equal_to>, Allocator>; // C++17 +template + unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator) + -> unordered_multimap, range-mapped-type, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_multimap(from_range_t, R&&, Allocator) + -> unordered_multimap, range-mapped-type, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator) + -> unordered_multimap, range-mapped-type, Hash, + equal_to>, Allocator>; // C++23 + template unordered_multimap(initializer_list>, typename see below::size_type, Allocator) -> unordered_multimap, equal_to, Allocator>; // C++17 @@ -524,10 +593,14 @@ #include <__iterator/distance.h> #include <__iterator/erase_if_container.h> #include <__iterator/iterator_traits.h> +#include <__iterator/ranges_iterator_traits.h> #include <__memory/addressof.h> #include <__memory/allocator.h> #include <__memory_resource/polymorphic_allocator.h> #include <__node_handle> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> #include <__type_traits/is_allocator.h> #include <__type_traits/type_identity.h> #include <__utility/forward.h> @@ -1111,6 +1184,21 @@ size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_map(from_range_t, _Range&& __range, size_type __n = /*implementation-defined*/0, + const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : __table_(__hf, __eql, typename __table::allocator_type(__a)) { + if (__n > 0) { + __table_.__rehash_unique(__n); + } + insert_range(std::forward<_Range>(__range)); + } +#endif + _LIBCPP_INLINE_VISIBILITY explicit unordered_map(const allocator_type& __a); _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u); @@ -1143,6 +1231,19 @@ unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) + : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} + + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) + : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY unordered_map(initializer_list __il, size_type __n, const allocator_type& __a) : unordered_map(__il, __n, hasher(), key_equal(), __a) {} @@ -1217,6 +1318,16 @@ _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + for (auto&& __element : __range) { + __table_.__insert_unique(std::forward(__element)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY void insert(initializer_list __il) @@ -1528,6 +1639,20 @@ _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Pred = equal_to<__range_key_type<_Range>>, + class _Allocator = allocator<__range_to_alloc_type<_Range>>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type = 0, + _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) + -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++23 +#endif + template>, class _Pred = equal_to>, class _Allocator = allocator>, @@ -1562,6 +1687,30 @@ -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 + +template ::value>> +unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) + -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, hash<__range_key_type<_Range>>, + equal_to<__range_key_type<_Range>>, _Allocator>; + +template ::value>> +unordered_map(from_range_t, _Range&&, _Allocator) + -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, hash<__range_key_type<_Range>>, + equal_to<__range_key_type<_Range>>, _Allocator>; + +template ::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) + -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, + equal_to<__range_key_type<_Range>>, _Allocator>; + +#endif + template::value>> unordered_map(initializer_list>, typename allocator_traits<_Allocator>::size_type, _Allocator) @@ -1950,6 +2099,21 @@ size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_multimap(from_range_t, _Range&& __range, size_type __n = /*implementation-defined*/0, + const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : __table_(__hf, __eql, typename __table::allocator_type(__a)) { + if (__n > 0) { + __table_.__rehash_multi(__n); + } + insert_range(std::forward<_Range>(__range)); + } +#endif + _LIBCPP_INLINE_VISIBILITY explicit unordered_multimap(const allocator_type& __a); _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u); @@ -1983,6 +2147,19 @@ unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) + : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} + + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) + : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY unordered_multimap(initializer_list __il, size_type __n, const allocator_type& __a) : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} @@ -2056,6 +2233,16 @@ _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + for (auto&& __element : __range) { + __table_.__insert_multi(std::forward(__element)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY void insert(initializer_list __il) @@ -2276,6 +2463,20 @@ _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Pred = equal_to<__range_key_type<_Range>>, + class _Allocator = allocator<__range_to_alloc_type<_Range>>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type = 0, + _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) + -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; +#endif + template>, class _Pred = equal_to>, class _Allocator = allocator>, @@ -2310,6 +2511,30 @@ -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 + +template ::value>> +unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) + -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, hash<__range_key_type<_Range>>, + equal_to<__range_key_type<_Range>>, _Allocator>; + +template ::value>> +unordered_multimap(from_range_t, _Range&&, _Allocator) + -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, hash<__range_key_type<_Range>>, + equal_to<__range_key_type<_Range>>, _Allocator>; + +template ::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) + -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, + equal_to<__range_key_type<_Range>>, _Allocator>; + +#endif + template::value>> unordered_multimap(initializer_list>, typename allocator_traits<_Allocator>::size_type, _Allocator) diff --git a/libcxx/include/unordered_set b/libcxx/include/unordered_set --- a/libcxx/include/unordered_set +++ b/libcxx/include/unordered_set @@ -58,6 +58,10 @@ size_type n = 0, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); + template R> + unordered_set(from_range_t, R&& rg, size_type n = see below, + const hasher& hf = hasher(), const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); // C++23 explicit unordered_set(const allocator_type&); unordered_set(const unordered_set&); unordered_set(const unordered_set&, const Allocator&); @@ -77,6 +81,12 @@ template unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); // C++14 + template R> + unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a) + : unordered_set(from_range, std::forward(rg), n, hasher(), key_equal(), a) { } // C++23 + template R> + unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) + : unordered_set(from_range, std::forward(rg), n, hf, key_equal(), a) { } // C++23 unordered_set(initializer_list il, size_type n, const allocator_type& a); // C++14 unordered_set(initializer_list il, size_type n, const hasher& hf, const allocator_type& a); // C++14 @@ -113,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 @@ -191,6 +203,13 @@ -> unordered_set::value_type, Hash, Pred, Allocator>; // C++17 +template>, + class Pred = equal_to>, + class Allocator = allocator>> + unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator()) + -> unordered_set, Hash, Pred, Allocator>; // C++23 + template, class Pred = equal_to, class Allocator = allocator> unordered_set(initializer_list, typename see below::size_type = see below, @@ -211,6 +230,21 @@ equal_to::value_type>, Allocator>; // C++17 +template + unordered_set(from_range_t, R&&, typename see below::size_type, Allocator) + -> unordered_set, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_set(from_range_t, R&&, Allocator) + -> unordered_set, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator) + -> unordered_set, Hash, + equal_to>, Allocator>; // C++23 + template unordered_set(initializer_list, typename see below::size_type, Allocator) -> unordered_set, equal_to, Allocator>; // C++17 @@ -272,6 +306,10 @@ size_type n = 0, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); + template R> + unordered_multiset(from_range_t, R&& rg, size_type n = see below, + const hasher& hf = hasher(), const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); // C++23 explicit unordered_multiset(const allocator_type&); unordered_multiset(const unordered_multiset&); unordered_multiset(const unordered_multiset&, const Allocator&); @@ -291,6 +329,12 @@ template unordered_multiset(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); // C++14 + template R> + unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a) + : unordered_multiset(from_range, std::forward(rg), n, hasher(), key_equal(), a) { } // C++23 + template R> + unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) + : unordered_multiset(from_range, std::forward(rg), n, hf, key_equal(), a) { } // C++23 unordered_multiset(initializer_list il, size_type n, const allocator_type& a); // C++14 unordered_multiset(initializer_list il, size_type n, const hasher& hf, const allocator_type& a); // C++14 @@ -327,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 @@ -405,6 +451,13 @@ -> unordered_multiset::value_type, Hash, Pred, Allocator>; // C++17 +template>, + class Pred = equal_to>, + class Allocator = allocator>> + unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator()) + -> unordered_multiset, Hash, Pred, Allocator>; // C++23 + template, class Pred = equal_to, class Allocator = allocator> unordered_multiset(initializer_list, typename see below::size_type = see below, @@ -424,6 +477,21 @@ -> unordered_multiset::value_type, Hash, equal_to::value_type>, Allocator>; // C++17 +template + unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator) + -> unordered_multiset, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_multiset(from_range_t, R&&, Allocator) + -> unordered_multiset, hash>, + equal_to>, Allocator>; // C++23 + +template + unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator) + -> unordered_multiset, Hash, + equal_to>, Allocator>; // C++23 + template unordered_multiset(initializer_list, typename see below::size_type, Allocator) -> unordered_multiset, equal_to, Allocator>; // C++17 @@ -469,10 +537,14 @@ #include <__iterator/distance.h> #include <__iterator/erase_if_container.h> #include <__iterator/iterator_traits.h> +#include <__iterator/ranges_iterator_traits.h> #include <__memory/addressof.h> #include <__memory/allocator.h> #include <__memory_resource/polymorphic_allocator.h> #include <__node_handle> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> #include <__type_traits/is_allocator.h> #include <__utility/forward.h> #include @@ -572,6 +644,21 @@ _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_set(from_range_t, _Range&& __range, size_type __n = /*implementation-defined*/0, + const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : __table_(__hf, __eql, __a) { + if (__n > 0) { + __table_.__rehash_unique(__n); + } + insert_range(std::forward<_Range>(__range)); + } +#endif + #if _LIBCPP_STD_VER >= 14 template inline _LIBCPP_INLINE_VISIBILITY @@ -583,6 +670,19 @@ size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} #endif + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) + : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} + + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) + : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY explicit unordered_set(const allocator_type& __a); _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u); @@ -688,6 +788,16 @@ _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + for (auto&& __element : __range) { + __table_.__insert_unique(std::forward(__element)); + } + } +#endif + _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __table_.erase(__p);} _LIBCPP_INLINE_VISIBILITY @@ -866,6 +976,20 @@ _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Pred = equal_to>, + class _Allocator = allocator>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type = 0, + _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) + -> unordered_set, _Hash, _Pred, _Allocator>; // C++23 +#endif + template, class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>, @@ -898,6 +1022,29 @@ equal_to<__iter_value_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 + +template ::value>> +unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) + -> unordered_set, hash>, + equal_to>, _Allocator>; + +template ::value>> +unordered_set(from_range_t, _Range&&, _Allocator) + -> unordered_set, hash>, + equal_to>, _Allocator>; + +template ::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) + -> unordered_set, _Hash, equal_to>, _Allocator>; + +#endif + template::value>> unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) @@ -1188,6 +1335,21 @@ _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n , const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_multiset(from_range_t, _Range&& __range, size_type __n = /*implementation-defined*/0, + const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : __table_(__hf, __eql, __a) { + if (__n > 0) { + __table_.__rehash_multi(__n); + } + insert_range(std::forward<_Range>(__range)); + } +#endif + #if _LIBCPP_STD_VER >= 14 template inline _LIBCPP_INLINE_VISIBILITY @@ -1200,6 +1362,19 @@ size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} #endif + +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) + : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} + + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) + : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} +#endif + _LIBCPP_INLINE_VISIBILITY explicit unordered_multiset(const allocator_type& __a); _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u); @@ -1298,6 +1473,16 @@ _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + for (auto&& __element : __range) { + __table_.__insert_multi(std::forward(__element)); + } + } +#endif + #if _LIBCPP_STD_VER >= 17 _LIBCPP_INLINE_VISIBILITY iterator insert(node_type&& __nh) @@ -1477,6 +1662,20 @@ _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; +#if _LIBCPP_STD_VER >= 23 +template >, + class _Pred = equal_to>, + class _Allocator = allocator>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type = 0, + _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) + -> unordered_multiset, _Hash, _Pred, _Allocator>; // C++23 +#endif + template, class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>, class = enable_if_t::value>, @@ -1507,6 +1706,29 @@ equal_to<__iter_value_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 + +template ::value>> +unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) + -> unordered_multiset, hash>, + equal_to>, _Allocator>; + +template ::value>> +unordered_multiset(from_range_t, _Range&&, _Allocator) + -> unordered_multiset, hash>, + equal_to>, _Allocator>; + +template ::value>, + class = enable_if_t::value>, + class = enable_if_t<__is_allocator<_Allocator>::value>> +unordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) + -> unordered_multiset, _Hash, equal_to>, _Allocator>; + +#endif + template::value>> unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) diff --git a/libcxx/test/std/containers/associative/from_range_associative_containers.h b/libcxx/test/std/containers/associative/from_range_associative_containers.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/associative/from_range_associative_containers.h @@ -0,0 +1,303 @@ +//===----------------------------------------------------------------------===// +// +// 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_ASSOCIATIVE_CONTAINERS_H +#define SUPPORT_FROM_RANGE_ASSOCIATIVE_CONTAINERS_H + +#include +#include +#include +#include +#include +#include + +#include "../from_range_helpers.h" +#include "../test_compare.h" +#include "MoveOnly.h" +#include "almost_satisfies_types.h" +#include "count_new.h" +#include "test_macros.h" + +template +concept HasFromRangeCtr = requires (Range&& range) { + Container(std::from_range, std::forward(range)); + Container(std::from_range, std::forward(range), std::less()); + Container(std::from_range, std::forward(range), std::less(), + std::allocator()); + Container(std::from_range, std::forward(range), std::allocator()); +}; + +template