diff options
Diffstat (limited to 'contrib/libs/cxxsupp/libcxx/include/unordered_map')
| -rw-r--r-- | contrib/libs/cxxsupp/libcxx/include/unordered_map | 534 |
1 files changed, 343 insertions, 191 deletions
diff --git a/contrib/libs/cxxsupp/libcxx/include/unordered_map b/contrib/libs/cxxsupp/libcxx/include/unordered_map index 14f93bab36..8d83063bbe 100644 --- a/contrib/libs/cxxsupp/libcxx/include/unordered_map +++ b/contrib/libs/cxxsupp/libcxx/include/unordered_map @@ -59,6 +59,11 @@ public: size_type n = 0, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); + template<container-compatible-range<value_type> 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 @@ public: 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<container-compatible-range<value_type> R> + unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a) + : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 + template<container-compatible-range<value_type> R> + unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) + : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, @@ -122,6 +133,8 @@ public: iterator insert(const_iterator hint, P&& obj); template <class InputIterator> void insert(InputIterator first, InputIterator last); + template<container-compatible-range<value_type> R> + void insert_range(R&& rg); // C++23 void insert(initializer_list<value_type>); node_type extract(const_iterator position); // C++17 @@ -224,6 +237,13 @@ unordered_map(InputIterator, InputIterator, typename see below::size_type = see -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, Allocator>; // C++17 +template<ranges::input_range R, class Hash = hash<range-key-type<R>>, + class Pred = equal_to<range-key-type<R>>, + class Allocator = allocator<range-to-alloc-type<R>>> + unordered_map(from_range_t, R&&, typename see below::size_type = see below, + Hash = Hash(), Pred = Pred(), Allocator = Allocator()) + -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23 + template<class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, @@ -245,6 +265,21 @@ unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 +template<ranges::input_range R, class Allocator> + unordered_map(from_range_t, R&&, typename see below::size_type, Allocator) + -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, + equal_to<range-key-type<R>>, Allocator>; // C++23 + +template<ranges::input_range R, class Allocator> + unordered_map(from_range_t, R&&, Allocator) + -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, + equal_to<range-key-type<R>>, Allocator>; // C++23 + +template<ranges::input_range R, class Hash, class Allocator> + unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator) + -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, + equal_to<range-key-type<R>>, Allocator>; // C++23 + template<class Key, class T, typename Allocator> unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 @@ -270,7 +305,7 @@ template <class Key, class T, class Hash, class Pred, class Alloc> template <class Key, class T, class Hash, class Pred, class Alloc> bool operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, - const unordered_map<Key, T, Hash, Pred, Alloc>& y); + const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, class Alloc = allocator<pair<const Key, T>>> @@ -311,6 +346,10 @@ public: size_type n = 0, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()); + template<container-compatible-range<value_type> 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 @@ public: 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<container-compatible-range<value_type> R> + unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a) + : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 + template<container-compatible-range<value_type> R> + unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) + : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, @@ -374,6 +419,8 @@ public: iterator insert(const_iterator hint, P&& obj); template <class InputIterator> void insert(InputIterator first, InputIterator last); + template<container-compatible-range<value_type> R> + void insert_range(R&& rg); // C++23 void insert(initializer_list<value_type>); node_type extract(const_iterator position); // C++17 @@ -453,6 +500,13 @@ unordered_multimap(InputIterator, InputIterator, typename see below::size_type = -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, Allocator>; // C++17 +template<ranges::input_range R, class Hash = hash<range-key-type<R>>, + class Pred = equal_to<range-key-type<R>>, + class Allocator = allocator<range-to-alloc-type<R>>> + unordered_multimap(from_range_t, R&&, typename see below::size_type = see below, + Hash = Hash(), Pred = Pred(), Allocator = Allocator()) + -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23 + template<class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, @@ -474,6 +528,21 @@ unordered_multimap(InputIterator, InputIterator, typename see below::size_type, -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 +template<ranges::input_range R, class Allocator> + unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator) + -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, + equal_to<range-key-type<R>>, Allocator>; // C++23 + +template<ranges::input_range R, class Allocator> + unordered_multimap(from_range_t, R&&, Allocator) + -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, + equal_to<range-key-type<R>>, Allocator>; // C++23 + +template<ranges::input_range R, class Hash, class Allocator> + unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator) + -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, + equal_to<range-key-type<R>>, Allocator>; // C++23 + template<class Key, class T, typename Allocator> unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 @@ -508,7 +577,7 @@ template <class Key, class T, class Hash, class Pred, class Alloc> template <class Key, class T, class Hash, class Pred, class Alloc> bool operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, - const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); + const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20 } // std @@ -516,19 +585,24 @@ template <class Key, class T, class Hash, class Pred, class Alloc> #include <__algorithm/is_permutation.h> #include <__assert> // all public C++ headers provide the assertion handler +#include <__availability> #include <__config> -#include <__debug> #include <__functional/is_transparent.h> #include <__functional/operations.h> #include <__hash_table> #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> #include <stdexcept> #include <tuple> @@ -575,7 +649,7 @@ public: _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Key& __x) const {return static_cast<const _Hash&>(*this)(__x);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <typename _K2> _LIBCPP_INLINE_VISIBILITY size_t operator()(const _K2& __x) const @@ -611,7 +685,7 @@ public: _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Key& __x) const {return __hash_(__x);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <typename _K2> _LIBCPP_INLINE_VISIBILITY size_t operator()(const _K2& __x) const @@ -661,7 +735,7 @@ public: _LIBCPP_INLINE_VISIBILITY bool operator()(const _Key& __x, const _Cp& __y) const {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <typename _K2> _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _K2& __y) const @@ -712,7 +786,7 @@ public: _LIBCPP_INLINE_VISIBILITY bool operator()(const _Key& __x, const _Cp& __y) const {return __pred_(__x, __y.__get_value().first);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <typename _K2> _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _K2& __y) const @@ -825,7 +899,7 @@ public: _LIBCPP_INLINE_VISIBILITY value_type& __get_value() { -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 return *_VSTD::launder(_VSTD::addressof(__cc_)); #else return __cc_; @@ -835,7 +909,7 @@ public: _LIBCPP_INLINE_VISIBILITY const value_type& __get_value() const { -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 return *_VSTD::launder(_VSTD::addressof(__cc_)); #else return __cc_; @@ -953,9 +1027,11 @@ public: friend _LIBCPP_INLINE_VISIBILITY bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {return __x.__i_ == __y.__i_;} +#if _LIBCPP_STD_VER <= 17 friend _LIBCPP_INLINE_VISIBILITY bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {return __x.__i_ != __y.__i_;} +#endif template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; @@ -1007,9 +1083,11 @@ public: friend _LIBCPP_INLINE_VISIBILITY bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {return __x.__i_ == __y.__i_;} +#if _LIBCPP_STD_VER <= 17 friend _LIBCPP_INLINE_VISIBILITY bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {return __x.__i_ != __y.__i_;} +#endif template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; @@ -1035,7 +1113,7 @@ public: typedef value_type& reference; typedef const value_type& const_reference; static_assert((is_same<value_type, typename allocator_type::value_type>::value), - "Invalid allocator::value_type"); + "Allocator::value_type must be same type as value_type"); private: typedef __hash_value_type<key_type, mapped_type> __value_type; @@ -1075,7 +1153,7 @@ public: typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 typedef __map_node_handle<__node, allocator_type> node_type; typedef __insert_return_type<iterator, node_type> insert_return_type; #endif @@ -1089,41 +1167,55 @@ public: unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) { - _VSTD::__debug_db_insert_c(this); } - explicit unordered_map(size_type __n, const hasher& __hf = hasher(), + explicit _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); - unordered_map(size_type __n, const hasher& __hf, + _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); template <class _InputIterator> - unordered_map(_InputIterator __first, _InputIterator __last); + _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last); template <class _InputIterator> - unordered_map(_InputIterator __first, _InputIterator __last, + _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); template <class _InputIterator> - unordered_map(_InputIterator __first, _InputIterator __last, + _LIBCPP_HIDE_FROM_ABI unordered_map(_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<value_type> _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); - unordered_map(const unordered_map& __u); - unordered_map(const unordered_map& __u, const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u); + _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); - unordered_map(unordered_map&& __u, const allocator_type& __a); - unordered_map(initializer_list<value_type> __il); - unordered_map(initializer_list<value_type> __il, size_type __n, + _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il); + _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); - unordered_map(initializer_list<value_type> __il, size_type __n, + _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); #endif // _LIBCPP_CXX03_LANG -#if _LIBCPP_STD_VER > 11 +#if _LIBCPP_STD_VER >= 14 _LIBCPP_INLINE_VISIBILITY unordered_map(size_type __n, const allocator_type& __a) : unordered_map(__n, hasher(), key_equal(), __a) {} @@ -1139,6 +1231,19 @@ public: 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<value_type> _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<value_type> _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<value_type> __il, size_type __n, const allocator_type& __a) : unordered_map(__il, __n, hasher(), key_equal(), __a) {} @@ -1205,11 +1310,7 @@ public: pair<iterator, bool> insert(const value_type& __x) {return __table_.__insert_unique(__x);} - iterator insert(const_iterator __p, const value_type& __x) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, - "unordered_map::insert(const_iterator, const value_type&) called with an iterator not " - "referring to this unordered_map"); - ((void)__p); + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } @@ -1217,6 +1318,16 @@ public: _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + for (auto&& __element : __range) { + __table_.__insert_unique(std::forward<decltype(__element)>(__element)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY void insert(initializer_list<value_type> __il) @@ -1226,11 +1337,7 @@ public: pair<iterator, bool> insert(value_type&& __x) {return __table_.__insert_unique(_VSTD::move(__x));} - iterator insert(const_iterator __p, value_type&& __x) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, - "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" - " referring to this unordered_map"); - ((void)__p); + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return __table_.__insert_unique(_VSTD::move(__x)).first; } @@ -1243,12 +1350,8 @@ public: template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> > _LIBCPP_INLINE_VISIBILITY - iterator insert(const_iterator __p, _Pp&& __x) + iterator insert(const_iterator, _Pp&& __x) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, - "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" - " referring to this unordered_map"); - ((void)__p); return insert(_VSTD::forward<_Pp>(__x)).first; } @@ -1260,17 +1363,13 @@ public: template <class... _Args> _LIBCPP_INLINE_VISIBILITY - iterator emplace_hint(const_iterator __p, _Args&&... __args) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this, - "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" - " referring to this unordered_map"); - ((void)__p); + iterator emplace_hint(const_iterator, _Args&&... __args) { return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; } #endif // _LIBCPP_CXX03_LANG -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 template <class... _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) @@ -1291,23 +1390,15 @@ public: template <class... _Args> _LIBCPP_INLINE_VISIBILITY - iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) + iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__h)) == this, - "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" - " referring to this unordered_map"); - ((void)__h); return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first; } template <class... _Args> _LIBCPP_INLINE_VISIBILITY - iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) + iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__h)) == this, - "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" - " referring to this unordered_map"); - ((void)__h); return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first; } @@ -1339,7 +1430,6 @@ public: _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) { - // FIXME: Add debug mode checking for the iterator input return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first; } @@ -1347,10 +1437,9 @@ public: _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) { - // FIXME: Add debug mode checking for the iterator input return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first; } -#endif // _LIBCPP_STD_VER > 14 +#endif // _LIBCPP_STD_VER >= 17 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} @@ -1364,11 +1453,11 @@ public: _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__table_.clear();} -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 _LIBCPP_INLINE_VISIBILITY insert_return_type insert(node_type&& __nh) { - _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), "node_type with incompatible allocator passed to unordered_map::insert()"); return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(_VSTD::move(__nh)); @@ -1376,7 +1465,7 @@ public: _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __hint, node_type&& __nh) { - _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), "node_type with incompatible allocator passed to unordered_map::insert()"); return __table_.template __node_handle_insert_unique<node_type>( __hint.__i_, _VSTD::move(__nh)); @@ -1397,32 +1486,32 @@ public: _LIBCPP_INLINE_VISIBILITY void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_unique(__source.__table_); } template <class _H2, class _P2> _LIBCPP_INLINE_VISIBILITY void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_unique(__source.__table_); } template <class _H2, class _P2> _LIBCPP_INLINE_VISIBILITY void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_unique(__source.__table_); } template <class _H2, class _P2> _LIBCPP_INLINE_VISIBILITY void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_unique(__source.__table_); } #endif @@ -1443,31 +1532,31 @@ public: iterator find(const key_type& __k) {return __table_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __table_.find(__k);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY iterator find(const _K2& __k) {return __table_.find(__k);} template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY const_iterator find(const _K2& __k) const {return __table_.find(__k);} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 _LIBCPP_INLINE_VISIBILITY size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY size_type count(const _K2& __k) const {return __table_.__count_unique(__k);} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 _LIBCPP_INLINE_VISIBILITY bool contains(const key_type& __k) const {return find(__k) != end();} template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY bool contains(const _K2& __k) const {return find(__k) != end();} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 _LIBCPP_INLINE_VISIBILITY pair<iterator, iterator> equal_range(const key_type& __k) @@ -1475,7 +1564,7 @@ public: _LIBCPP_INLINE_VISIBILITY pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {return __table_.__equal_range_unique(__k);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY pair<iterator, iterator> equal_range(const _K2& __k) @@ -1484,15 +1573,15 @@ public: _LIBCPP_INLINE_VISIBILITY pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {return __table_.__equal_range_unique(__k);} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 - mapped_type& operator[](const key_type& __k); + _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); #ifndef _LIBCPP_CXX03_LANG - mapped_type& operator[](key_type&& __k); + _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k); #endif - mapped_type& at(const key_type& __k); - const mapped_type& at(const key_type& __k) const; + _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); + _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; _LIBCPP_INLINE_VISIBILITY size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} @@ -1529,23 +1618,10 @@ public: _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) {__table_.__reserve_unique(__n);} -#ifdef _LIBCPP_ENABLE_DEBUG_MODE - - bool __dereferenceable(const const_iterator* __i) const - {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));} - bool __decrementable(const const_iterator* __i) const - {return __table_.__decrementable(_VSTD::addressof(__i->__i_));} - bool __addable(const const_iterator* __i, ptrdiff_t __n) const - {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} - bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const - {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} - -#endif // _LIBCPP_ENABLE_DEBUG_MODE - private: #ifdef _LIBCPP_CXX03_LANG - __node_holder __construct_node_with_key(const key_type& __k); + _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); #endif }; @@ -1554,7 +1630,7 @@ template<class _InputIterator, class _Hash = hash<__iter_key_type<_InputIterator>>, class _Pred = equal_to<__iter_key_type<_InputIterator>>, class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<!__is_allocator<_Hash>::value>, class = enable_if_t<!is_integral<_Hash>::value>, class = enable_if_t<!__is_allocator<_Pred>::value>, @@ -1563,6 +1639,20 @@ unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocat _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 <ranges::input_range _Range, + class _Hash = hash<__range_key_type<_Range>>, + class _Pred = equal_to<__range_key_type<_Range>>, + class _Allocator = allocator<__range_to_alloc_type<_Range>>, + class = enable_if_t<!__is_allocator<_Hash>::value>, + class = enable_if_t<!is_integral<_Hash>::value>, + class = enable_if_t<!__is_allocator<_Pred>::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 _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>, class _Pred = equal_to<remove_const_t<_Key>>, class _Allocator = allocator<pair<const _Key, _Tp>>, @@ -1575,21 +1665,21 @@ unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allo -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; template<class _InputIterator, class _Allocator, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<__is_allocator<_Allocator>::value>> unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; template<class _InputIterator, class _Allocator, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<__is_allocator<_Allocator>::value>> unordered_map(_InputIterator, _InputIterator, _Allocator) -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; template<class _InputIterator, class _Hash, class _Allocator, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<!__is_allocator<_Hash>::value>, class = enable_if_t<!is_integral<_Hash>::value>, class = enable_if_t<__is_allocator<_Allocator>::value>> @@ -1597,6 +1687,30 @@ unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocat -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 + +template <ranges::input_range _Range, class _Allocator, + class = enable_if_t<__is_allocator<_Allocator>::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 <ranges::input_range _Range, class _Allocator, + class = enable_if_t<__is_allocator<_Allocator>::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 <ranges::input_range _Range, class _Hash, class _Allocator, + class = enable_if_t<!__is_allocator<_Hash>::value>, + class = enable_if_t<!is_integral<_Hash>::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<class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) @@ -1625,7 +1739,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( size_type __n, const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__n); } @@ -1635,7 +1748,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const allocator_type& __a) : __table_(__hf, __eql, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__n); } @@ -1645,7 +1757,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const allocator_type& __a) : __table_(typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1653,7 +1764,6 @@ template <class _InputIterator> unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( _InputIterator __first, _InputIterator __last) { - _VSTD::__debug_db_insert_c(this); insert(__first, __last); } @@ -1664,7 +1774,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__n); insert(__first, __last); } @@ -1676,7 +1785,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const hasher& __hf, const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__n); insert(__first, __last); } @@ -1686,7 +1794,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const unordered_map& __u) : __table_(__u.__table_) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -1696,7 +1803,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const unordered_map& __u, const allocator_type& __a) : __table_(__u.__table_, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -1710,8 +1816,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) : __table_(_VSTD::move(__u.__table_)) { - _VSTD::__debug_db_insert_c(this); - std::__debug_db_swap(this, std::addressof(__u)); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1719,7 +1823,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( unordered_map&& __u, const allocator_type& __a) : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); if (__a != __u.get_allocator()) { iterator __i = __u.begin(); @@ -1728,15 +1831,12 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( __u.__table_.remove((__i++).__i_)->__value_.__move()); } } - else - std::__debug_db_swap(this, std::addressof(__u)); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( initializer_list<value_type> __il) { - _VSTD::__debug_db_insert_c(this); insert(__il.begin(), __il.end()); } @@ -1746,7 +1846,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const key_equal& __eql) : __table_(__hf, __eql) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__n); insert(__il.begin(), __il.end()); } @@ -1757,7 +1856,6 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_unique(__n); insert(__il.begin(), __il.end()); } @@ -1874,7 +1972,7 @@ swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, __x.swap(__y); } -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate> inline _LIBCPP_INLINE_VISIBILITY @@ -1904,6 +2002,8 @@ operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, return true; } +#if _LIBCPP_STD_VER <= 17 + template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> inline _LIBCPP_INLINE_VISIBILITY bool @@ -1913,6 +2013,8 @@ operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, return !(__x == __y); } +#endif + template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, class _Alloc = allocator<pair<const _Key, _Tp> > > class _LIBCPP_TEMPLATE_VIS unordered_multimap @@ -1928,7 +2030,7 @@ public: typedef value_type& reference; typedef const value_type& const_reference; static_assert((is_same<value_type, typename allocator_type::value_type>::value), - "Invalid allocator::value_type"); + "Allocator::value_type must be same type as value_type"); private: typedef __hash_value_type<key_type, mapped_type> __value_type; @@ -1967,7 +2069,7 @@ private: typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 typedef __map_node_handle<__node, allocator_type> node_type; #endif @@ -1980,42 +2082,56 @@ private: unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) { - _VSTD::__debug_db_insert_c(this); } - explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), + explicit _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); - unordered_multimap(size_type __n, const hasher& __hf, + _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); template <class _InputIterator> - unordered_multimap(_InputIterator __first, _InputIterator __last); + _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last); template <class _InputIterator> - unordered_multimap(_InputIterator __first, _InputIterator __last, + _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); template <class _InputIterator> - unordered_multimap(_InputIterator __first, _InputIterator __last, + _LIBCPP_HIDE_FROM_ABI unordered_multimap(_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<value_type> _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); - unordered_multimap(const unordered_multimap& __u); - unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u); + _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY unordered_multimap(unordered_multimap&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); - unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); - unordered_multimap(initializer_list<value_type> __il); - unordered_multimap(initializer_list<value_type> __il, size_type __n, + _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il); + _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); - unordered_multimap(initializer_list<value_type> __il, size_type __n, + _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); #endif // _LIBCPP_CXX03_LANG -#if _LIBCPP_STD_VER > 11 +#if _LIBCPP_STD_VER >= 14 _LIBCPP_INLINE_VISIBILITY unordered_multimap(size_type __n, const allocator_type& __a) : unordered_multimap(__n, hasher(), key_equal(), __a) {} @@ -2031,6 +2147,19 @@ private: 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<value_type> _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<value_type> _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<value_type> __il, size_type __n, const allocator_type& __a) : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} @@ -2104,6 +2233,16 @@ private: _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI + void insert_range(_Range&& __range) { + for (auto&& __element : __range) { + __table_.__insert_multi(std::forward<decltype(__element)>(__element)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY void insert(initializer_list<value_type> __il) @@ -2128,12 +2267,12 @@ private: {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} template <class... _Args> - iterator emplace(_Args&&... __args) { + _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...); } template <class... _Args> - iterator emplace_hint(const_iterator __p, _Args&&... __args) { + _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); } #endif // _LIBCPP_CXX03_LANG @@ -2151,11 +2290,11 @@ private: _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__table_.clear();} -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 _LIBCPP_INLINE_VISIBILITY iterator insert(node_type&& __nh) { - _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), "node_type with incompatible allocator passed to unordered_multimap::insert()"); return __table_.template __node_handle_insert_multi<node_type>( _VSTD::move(__nh)); @@ -2163,7 +2302,7 @@ private: _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __hint, node_type&& __nh) { - _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), "node_type with incompatible allocator passed to unordered_multimap::insert()"); return __table_.template __node_handle_insert_multi<node_type>( __hint.__i_, _VSTD::move(__nh)); @@ -2184,32 +2323,32 @@ private: _LIBCPP_INLINE_VISIBILITY void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_multi(__source.__table_); } template <class _H2, class _P2> _LIBCPP_INLINE_VISIBILITY void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_multi(__source.__table_); } template <class _H2, class _P2> _LIBCPP_INLINE_VISIBILITY void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_multi(__source.__table_); } template <class _H2, class _P2> _LIBCPP_INLINE_VISIBILITY void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { - _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); return __table_.__node_handle_merge_multi(__source.__table_); } #endif @@ -2230,31 +2369,31 @@ private: iterator find(const key_type& __k) {return __table_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __table_.find(__k);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY iterator find(const _K2& __k) {return __table_.find(__k);} template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY const_iterator find(const _K2& __k) const {return __table_.find(__k);} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 _LIBCPP_INLINE_VISIBILITY size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY size_type count(const _K2& __k) const {return __table_.__count_multi(__k);} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 _LIBCPP_INLINE_VISIBILITY bool contains(const key_type& __k) const {return find(__k) != end();} template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY bool contains(const _K2& __k) const {return find(__k) != end();} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 _LIBCPP_INLINE_VISIBILITY pair<iterator, iterator> equal_range(const key_type& __k) @@ -2262,7 +2401,7 @@ private: _LIBCPP_INLINE_VISIBILITY pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {return __table_.__equal_range_multi(__k);} -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> _LIBCPP_INLINE_VISIBILITY pair<iterator, iterator> equal_range(const _K2& __k) @@ -2271,7 +2410,7 @@ private: _LIBCPP_INLINE_VISIBILITY pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {return __table_.__equal_range_multi(__k);} -#endif // _LIBCPP_STD_VER > 17 +#endif // _LIBCPP_STD_VER >= 20 _LIBCPP_INLINE_VISIBILITY size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} @@ -2308,21 +2447,6 @@ private: void rehash(size_type __n) {__table_.__rehash_multi(__n);} _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) {__table_.__reserve_multi(__n);} - -#ifdef _LIBCPP_ENABLE_DEBUG_MODE - - bool __dereferenceable(const const_iterator* __i) const - {return __table_.__dereferenceable(_VSTD::addressof(__i->__i_));} - bool __decrementable(const const_iterator* __i) const - {return __table_.__decrementable(_VSTD::addressof(__i->__i_));} - bool __addable(const const_iterator* __i, ptrdiff_t __n) const - {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} - bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const - {return __table_.__addable(_VSTD::addressof(__i->__i_), __n);} - -#endif // _LIBCPP_ENABLE_DEBUG_MODE - - }; #if _LIBCPP_STD_VER >= 17 @@ -2330,7 +2454,7 @@ template<class _InputIterator, class _Hash = hash<__iter_key_type<_InputIterator>>, class _Pred = equal_to<__iter_key_type<_InputIterator>>, class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<!__is_allocator<_Hash>::value>, class = enable_if_t<!is_integral<_Hash>::value>, class = enable_if_t<!__is_allocator<_Pred>::value>, @@ -2339,6 +2463,20 @@ unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Al _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 <ranges::input_range _Range, + class _Hash = hash<__range_key_type<_Range>>, + class _Pred = equal_to<__range_key_type<_Range>>, + class _Allocator = allocator<__range_to_alloc_type<_Range>>, + class = enable_if_t<!__is_allocator<_Hash>::value>, + class = enable_if_t<!is_integral<_Hash>::value>, + class = enable_if_t<!__is_allocator<_Pred>::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 _Key, class _Tp, class _Hash = hash<remove_const_t<_Key>>, class _Pred = equal_to<remove_const_t<_Key>>, class _Allocator = allocator<pair<const _Key, _Tp>>, @@ -2351,21 +2489,21 @@ unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits< -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; template<class _InputIterator, class _Allocator, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<__is_allocator<_Allocator>::value>> unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; template<class _InputIterator, class _Allocator, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<__is_allocator<_Allocator>::value>> unordered_multimap(_InputIterator, _InputIterator, _Allocator) -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, hash<__iter_key_type<_InputIterator>>, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; template<class _InputIterator, class _Hash, class _Allocator, - class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, class = enable_if_t<!__is_allocator<_Hash>::value>, class = enable_if_t<!is_integral<_Hash>::value>, class = enable_if_t<__is_allocator<_Allocator>::value>> @@ -2373,6 +2511,30 @@ unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Al -> unordered_multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, equal_to<__iter_key_type<_InputIterator>>, _Allocator>; +#if _LIBCPP_STD_VER >= 23 + +template <ranges::input_range _Range, class _Allocator, + class = enable_if_t<__is_allocator<_Allocator>::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 <ranges::input_range _Range, class _Allocator, + class = enable_if_t<__is_allocator<_Allocator>::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 <ranges::input_range _Range, class _Hash, class _Allocator, + class = enable_if_t<!__is_allocator<_Hash>::value>, + class = enable_if_t<!is_integral<_Hash>::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<class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) @@ -2401,7 +2563,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( size_type __n, const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__n); } @@ -2411,7 +2572,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const allocator_type& __a) : __table_(__hf, __eql, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__n); } @@ -2420,7 +2580,6 @@ template <class _InputIterator> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( _InputIterator __first, _InputIterator __last) { - _VSTD::__debug_db_insert_c(this); insert(__first, __last); } @@ -2431,7 +2590,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__n); insert(__first, __last); } @@ -2443,7 +2601,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const hasher& __hf, const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__n); insert(__first, __last); } @@ -2454,7 +2611,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const allocator_type& __a) : __table_(typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -2462,7 +2618,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const unordered_multimap& __u) : __table_(__u.__table_) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -2472,7 +2627,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const unordered_multimap& __u, const allocator_type& __a) : __table_(__u.__table_, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -2486,8 +2640,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) : __table_(_VSTD::move(__u.__table_)) { - _VSTD::__debug_db_insert_c(this); - std::__debug_db_swap(this, std::addressof(__u)); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -2495,7 +2647,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( unordered_multimap&& __u, const allocator_type& __a) : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); if (__a != __u.get_allocator()) { iterator __i = __u.begin(); @@ -2505,15 +2656,12 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( __u.__table_.remove((__i++).__i_)->__value_.__move()); } } - else - std::__debug_db_swap(this, std::addressof(__u)); } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( initializer_list<value_type> __il) { - _VSTD::__debug_db_insert_c(this); insert(__il.begin(), __il.end()); } @@ -2523,7 +2671,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const key_equal& __eql) : __table_(__hf, __eql) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__n); insert(__il.begin(), __il.end()); } @@ -2534,7 +2681,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, typename __table::allocator_type(__a)) { - _VSTD::__debug_db_insert_c(this); __table_.__rehash_multi(__n); insert(__il.begin(), __il.end()); } @@ -2584,7 +2730,7 @@ swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, __x.swap(__y); } -#if _LIBCPP_STD_VER > 17 +#if _LIBCPP_STD_VER >= 20 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate> inline _LIBCPP_INLINE_VISIBILITY @@ -2618,6 +2764,8 @@ operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, return true; } +#if _LIBCPP_STD_VER <= 17 + template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> inline _LIBCPP_INLINE_VISIBILITY bool @@ -2627,17 +2775,19 @@ operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, return !(__x == __y); } +#endif + _LIBCPP_END_NAMESPACE_STD -#if _LIBCPP_STD_VER > 14 +#if _LIBCPP_STD_VER >= 17 _LIBCPP_BEGIN_NAMESPACE_STD namespace pmr { template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> -using unordered_map = +using unordered_map _LIBCPP_AVAILABILITY_PMR = std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> -using unordered_multimap = +using unordered_multimap _LIBCPP_AVAILABILITY_PMR = std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; } // namespace pmr _LIBCPP_END_NAMESPACE_STD @@ -2647,7 +2797,9 @@ _LIBCPP_END_NAMESPACE_STD # include <algorithm> # include <bit> # include <concepts> +# include <cstdlib> # include <iterator> +# include <type_traits> #endif #endif // _LIBCPP_UNORDERED_MAP |