diff options
Diffstat (limited to 'libcxx/include')
| -rw-r--r-- | libcxx/include/__hash_table | 255 | ||||
| -rw-r--r-- | libcxx/include/__node_handle | 3 | ||||
| -rw-r--r-- | libcxx/include/__tree | 70 | ||||
| -rw-r--r-- | libcxx/include/map | 92 | ||||
| -rw-r--r-- | libcxx/include/set | 95 | ||||
| -rw-r--r-- | libcxx/include/unordered_map | 97 | ||||
| -rw-r--r-- | libcxx/include/unordered_set | 97 | ||||
| -rw-r--r-- | libcxx/include/version | 1 |
8 files changed, 642 insertions, 68 deletions
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table index c77de961be6..69ed8dd8b94 100644 --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -1058,8 +1058,26 @@ public: ); } +private: + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_multi_prepare(size_t __cp_hash, + value_type& __cp_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_multi_perform(__node_pointer __cp, + __next_pointer __pn) _NOEXCEPT; + + _LIBCPP_INLINE_VISIBILITY + __next_pointer __node_insert_unique_prepare(size_t __nd_hash, + value_type& __nd_val); + _LIBCPP_INLINE_VISIBILITY + void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; + +public: + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); @@ -1170,6 +1188,9 @@ public: _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Table& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1177,6 +1198,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); + template <class _Table> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Table& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1849,73 +1873,112 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT } } + +// Prepare the container for an insertion of the value __value with the hash +// __hash. This does a lookup into the container to see if __value is already +// present, and performs a rehash if necessary. Returns a pointer to the +// existing element if it exists, otherwise nullptr. +// +// Note that this function does forward exceptions if key_eq() throws, and never +// mutates __value or actually inserts into the map. template <class _Tp, class _Hash, class _Equal, class _Alloc> -pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( + size_t __hash, value_type& __value) { - __nd->__hash_ = hash_function()(__nd->__value_); size_type __bc = bucket_count(); - bool __inserted = false; - __next_pointer __ndptr; - size_t __chash; + if (__bc != 0) { - __chash = __constrain_hash(__nd->__hash_, __bc); - __ndptr = __bucket_list_[__chash]; + size_t __chash = __constrain_hash(__hash, __bc); + __next_pointer __ndptr = __bucket_list_[__chash]; if (__ndptr != nullptr) { for (__ndptr = __ndptr->__next_; __ndptr != nullptr && __constrain_hash(__ndptr->__hash(), __bc) == __chash; __ndptr = __ndptr->__next_) { - if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_)) - goto __done; + if (key_eq()(__ndptr->__upcast()->__value_, __value)) + return __ndptr; } } } + if (size()+1 > __bc * max_load_factor() || __bc == 0) { - if (size()+1 > __bc * max_load_factor() || __bc == 0) - { - rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), - size_type(ceil(float(size() + 1) / max_load_factor())))); - __bc = bucket_count(); - __chash = __constrain_hash(__nd->__hash_, __bc); - } - // insert_after __bucket_list_[__chash], or __first_node if bucket is null - __next_pointer __pn = __bucket_list_[__chash]; - if (__pn == nullptr) - { - __pn =__p1_.first().__ptr(); - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__nd->__next_ != nullptr) - __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); - } - else - { - __nd->__next_ = __pn->__next_; - __pn->__next_ = __nd->__ptr(); - } - __ndptr = __nd->__ptr(); - // increment size - ++size(); + rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), + size_type(ceil(float(size() + 1) / max_load_factor())))); + } + return nullptr; +} + +// Insert the node __nd into the container by pushing it into the right bucket, +// and updating size(). Assumes that __nd->__hash is up-to-date, and that +// rehashing has already occurred and that no element with the same key exists +// in the map. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( + __node_pointer __nd) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__nd->__hash(), __bc); + // insert_after __bucket_list_[__chash], or __first_node if bucket is null + __next_pointer __pn = __bucket_list_[__chash]; + if (__pn == nullptr) + { + __pn =__p1_.first().__ptr(); + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; + if (__nd->__next_ != nullptr) + __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); + } + else + { + __nd->__next_ = __pn->__next_; + __pn->__next_ = __nd->__ptr(); + } + ++size(); +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) +{ + __nd->__hash_ = hash_function()(__nd->__value_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); + + // Insert the node, unless it already exists in the container. + bool __inserted = false; + if (__existing_node == nullptr) + { + __node_insert_unique_perform(__nd); + __existing_node = __nd->__ptr(); __inserted = true; } -__done: #if _LIBCPP_DEBUG_LEVEL >= 2 - return pair<iterator, bool>(iterator(__ndptr, this), __inserted); + return pair<iterator, bool>(iterator(__existing_node, this), __inserted); #else - return pair<iterator, bool>(iterator(__ndptr), __inserted); + return pair<iterator, bool>(iterator(__existing_node), __inserted); #endif } +// Prepare the container for an insertion of the value __cp_val with the hash +// __cp_hash. This does a lookup into the container to see if __cp_value is +// already present, and performs a rehash if necessary. Returns a pointer to the +// last occurance of __cp_val in the map. +// +// Note that this function does forward exceptions if key_eq() throws, and never +// mutates __value or actually inserts into the map. template <class _Tp, class _Hash, class _Equal, class _Alloc> -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( + size_t __cp_hash, value_type& __cp_val) { - __cp->__hash_ = hash_function()(__cp->__value_); size_type __bc = bucket_count(); if (size()+1 > __bc * max_load_factor() || __bc == 0) { @@ -1923,20 +1986,9 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c size_type(ceil(float(size() + 1) / max_load_factor())))); __bc = bucket_count(); } - size_t __chash = __constrain_hash(__cp->__hash_, __bc); + size_t __chash = __constrain_hash(__cp_hash, __bc); __next_pointer __pn = __bucket_list_[__chash]; - if (__pn == nullptr) - { - __pn =__p1_.first().__ptr(); - __cp->__next_ = __pn->__next_; - __pn->__next_ = __cp->__ptr(); - // fix up __bucket_list_ - __bucket_list_[__chash] = __pn; - if (__cp->__next_ != nullptr) - __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] - = __cp->__ptr(); - } - else + if (__pn != nullptr) { for (bool __found = false; __pn->__next_ != nullptr && __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; @@ -1947,8 +1999,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c // true true loop // false true set __found to true // true false break - if (__found != (__pn->__next_->__hash() == __cp->__hash_ && - key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_))) + if (__found != (__pn->__next_->__hash() == __cp_hash && + key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) { if (!__found) __found = true; @@ -1956,6 +2008,35 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c break; } } + } + return __pn; +} + +// Insert the node __cp into the container after __pn (which is the last node in +// the bucket that compares equal to __cp). Rehashing, and checking for +// uniqueness has already been performed (in __node_insert_multi_prepare), so +// all we need to do is update the bucket and size(). Assumes that __cp->__hash +// is up-to-date. +template <class _Tp, class _Hash, class _Equal, class _Alloc> +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( + __node_pointer __cp, __next_pointer __pn) _NOEXCEPT +{ + size_type __bc = bucket_count(); + size_t __chash = __constrain_hash(__cp->__hash_, __bc); + if (__pn == nullptr) + { + __pn =__p1_.first().__ptr(); + __cp->__next_ = __pn->__next_; + __pn->__next_ = __cp->__ptr(); + // fix up __bucket_list_ + __bucket_list_[__chash] = __pn; + if (__cp->__next_ != nullptr) + __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] + = __cp->__ptr(); + } + else + { __cp->__next_ = __pn->__next_; __pn->__next_ = __cp->__ptr(); if (__cp->__next_ != nullptr) @@ -1966,6 +2047,17 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c } } ++size(); +} + + +template <class _Tp, class _Hash, class _Equal, class _Alloc> +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) +{ + __cp->__hash_ = hash_function()(__cp->__value_); + __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_); + __node_insert_multi_perform(__cp, __pn); + #if _LIBCPP_DEBUG_LEVEL >= 2 return iterator(__cp->__ptr(), this); #else @@ -2217,6 +2309,32 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( } template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( + _Table& __source) +{ + static_assert(is_same<__node, typename _Table::__node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __hash = hash_function()(__src_ptr->__value_); + __next_pointer __existing_node = + __node_insert_unique_prepare(__hash, __src_ptr->__value_); + auto __prev_iter = __it++; + if (__existing_node == nullptr) + { + (void)__source.remove(__prev_iter).release(); + __src_ptr->__hash_ = __hash; + __node_insert_unique_perform(__src_ptr); + } + } +} + +template <class _Tp, class _Hash, class _Equal, class _Alloc> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator @@ -2244,6 +2362,27 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( return __result; } +template <class _Tp, class _Hash, class _Equal, class _Alloc> +template <class _Table> +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( + _Table& __source) +{ + static_assert(is_same<typename _Table::__node, __node>::value, ""); + + for (typename _Table::iterator __it = __source.begin(); + __it != __source.end();) + { + __node_pointer __src_ptr = __it.__node_->__upcast(); + size_t __src_hash = hash_function()(__src_ptr->__value_); + __next_pointer __pn = + __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); + (void)__source.remove(__it++).release(); + __src_ptr->__hash_ = __src_hash; + __node_insert_multi_perform(__src_ptr, __pn); + } +} #endif // _LIBCPP_STD_VER > 14 template <class _Tp, class _Hash, class _Equal, class _Alloc> diff --git a/libcxx/include/__node_handle b/libcxx/include/__node_handle index 567f8b047a3..a9cf3b7217a 100644 --- a/libcxx/include/__node_handle +++ b/libcxx/include/__node_handle @@ -26,9 +26,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD #if _LIBCPP_STD_VER > 14 -// FIXME: Uncomment this when we support the 'merge' functionality. -// #define __cpp_lib_node_extract 201606L - // Specialized in __tree & __hash_table for their _NodeType. template <class _NodeType, class _Alloc> struct __generic_container_node_destructor; diff --git a/libcxx/include/__tree b/libcxx/include/__tree index 3b3586ca697..aa7370bfb04 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -1341,15 +1341,20 @@ public: #endif // !_LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer); + _LIBCPP_INLINE_VISIBILITY iterator + __remove_node_pointer(__node_pointer) _NOEXCEPT; #if _LIBCPP_STD_VER > 14 template <class _NodeHandle, class _InsertReturnType> @@ -1358,6 +1363,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Tree& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1365,6 +1373,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Tree& __source); template <class _NodeHandle> @@ -1384,7 +1395,7 @@ public: void __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, - __node_base_pointer __new_node); + __node_base_pointer __new_node) _NOEXCEPT; template <class _Key> iterator find(const _Key& __v); @@ -2129,10 +2140,9 @@ __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, } template <class _Tp, class _Compare, class _Allocator> -void -__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer __parent, - __node_base_pointer& __child, - __node_base_pointer __new_node) +void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( + __parent_pointer __parent, __node_base_pointer& __child, + __node_base_pointer __new_node) _NOEXCEPT { __new_node->__left_ = nullptr; __new_node->__right_ = nullptr; @@ -2384,7 +2394,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) +__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT { iterator __r(__ptr); ++__r; @@ -2472,6 +2482,30 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) } template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = + __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + if (__child != nullptr) + continue; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + +template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY typename __tree<_Tp, _Compare, _Allocator>::iterator @@ -2507,6 +2541,28 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi( return iterator(__ptr); } +template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = __find_leaf_high( + __parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + #endif // _LIBCPP_STD_VER > 14 template <class _Tp, class _Compare, class _Allocator> diff --git a/libcxx/include/map b/libcxx/include/map index cfd82805870..472ac314bc1 100644 --- a/libcxx/include/map +++ b/libcxx/include/map @@ -167,6 +167,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(map<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 + void swap(map& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && is_nothrow_swappable<key_compare>::value); // C++17 @@ -368,6 +377,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(multimap<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multimap<Key, T, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>& source); // C++17 + template<class C2> + void merge(map<Key, T, C2, Allocator>&& source); // C++17 + void swap(multimap& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && is_nothrow_swappable<key_compare>::value); // C++17 @@ -926,6 +944,11 @@ public: typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multimap; + _LIBCPP_INLINE_VISIBILITY map() _NOEXCEPT_( @@ -1300,6 +1323,38 @@ public: { return __tree_.template __node_handle_extract<node_type>(__it.__i_); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -1615,6 +1670,11 @@ public: typedef __map_node_handle<typename __base::__node, allocator_type> node_type; #endif + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multimap; + _LIBCPP_INLINE_VISIBILITY multimap() _NOEXCEPT_( @@ -1882,6 +1942,38 @@ public: return __tree_.template __node_handle_extract<node_type>( __it.__i_); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/libcxx/include/set b/libcxx/include/set index f2ce6ea2f36..80cc7b04c37 100644 --- a/libcxx/include/set +++ b/libcxx/include/set @@ -128,6 +128,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(set<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>&& source); // C++17 + void swap(set& s) noexcept( __is_nothrow_swappable<key_compare>::value && @@ -316,6 +325,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class C2> + void merge(multiset<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(multiset<Key, C2, Allocator>&& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>& source); // C++17 + template<class C2> + void merge(set<Key, C2, Allocator>&& source); // C++17 + void swap(multiset& s) noexcept( __is_nothrow_swappable<key_compare>::value && @@ -410,6 +428,9 @@ swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) _LIBCPP_BEGIN_NAMESPACE_STD +template <class _Key, class _Compare, class _Allocator> +class multiset; + template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> > class _LIBCPP_TEMPLATE_VIS set @@ -449,6 +470,11 @@ public: typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS set; + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multiset; + _LIBCPP_INLINE_VISIBILITY set() _NOEXCEPT_( @@ -681,6 +707,38 @@ public: { return __tree_.template __node_handle_extract<node_type>(__it); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -891,6 +949,11 @@ public: typedef __set_node_handle<typename __base::__node, allocator_type> node_type; #endif + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS set; + template <class _Key2, class _Compare2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multiset; + // construct/copy/destroy: _LIBCPP_INLINE_VISIBILITY multiset() @@ -1122,6 +1185,38 @@ public: { return __tree_.template __node_handle_extract<node_type>(__it); } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(multiset<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _C2> + _LIBCPP_INLINE_VISIBILITY + void merge(set<key_type, _C2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map index fc3cfb6a950..6f60749c93d 100644 --- a/libcxx/include/unordered_map +++ b/libcxx/include/unordered_map @@ -153,6 +153,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_map&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -325,6 +334,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_multimap&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -808,6 +826,9 @@ public: template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; }; +template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> +class unordered_multimap; + 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_map @@ -865,6 +886,11 @@ public: typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_map; + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; + _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1188,6 +1214,39 @@ public: return __table_.template __node_handle_extract<node_type>( __it.__i_); } + + 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"); + 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"); + 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"); + 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"); + return __table_.__node_handle_merge_unique(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -1646,6 +1705,11 @@ public: typedef __map_node_handle<__node, allocator_type> node_type; #endif + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_map; + template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; + _LIBCPP_INLINE_VISIBILITY unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1847,6 +1911,39 @@ public: return __table_.template __node_handle_extract<node_type>( __it.__i_); } + + 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"); + 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"); + 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"); + 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"); + return __table_.__node_handle_merge_multi(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/libcxx/include/unordered_set b/libcxx/include/unordered_set index a219fa60912..de23ca2a396 100644 --- a/libcxx/include/unordered_set +++ b/libcxx/include/unordered_set @@ -127,6 +127,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_set&) noexcept(allocator_traits<Allocator>::is_always_equal::value && noexcept(swap(declval<hasher&>(), declval<hasher&>())) && @@ -282,6 +291,15 @@ public: iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 + template<class H2, class P2> + void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 + void swap(unordered_multiset&) noexcept(allocator_traits<Allocator>::is_always_equal::value && noexcept(swap(declval<hasher&>(), declval<hasher&>())) && @@ -348,6 +366,9 @@ template <class Value, class Hash, class Pred, class Alloc> _LIBCPP_BEGIN_NAMESPACE_STD +template <class _Value, class _Hash, class _Pred, class _Alloc> +class unordered_multiset; + template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > class _LIBCPP_TEMPLATE_VIS unordered_set @@ -385,6 +406,11 @@ public: typedef __insert_return_type<iterator, node_type> insert_return_type; #endif + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_set; + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; + _LIBCPP_INLINE_VISIBILITY unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -590,6 +616,39 @@ public: { return __table_.template __node_handle_extract<node_type>(__it); } + + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template<class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY @@ -938,6 +997,11 @@ public: typedef __set_node_handle<typename __table::__node, allocator_type> node_type; #endif + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_set; + template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; + _LIBCPP_INLINE_VISIBILITY unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1102,6 +1166,39 @@ public: { return __table_.template __node_handle_extract<node_type>(__key); } + + template <class _H2, class _P2> + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__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_multiset<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__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_set<key_type, _H2, _P2, allocator_type>& __source) + { + _LIBCPP_ASSERT(__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_set<key_type, _H2, _P2, allocator_type>&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } #endif _LIBCPP_INLINE_VISIBILITY diff --git a/libcxx/include/version b/libcxx/include/version index 6e61693cf85..aca84f8edf0 100644 --- a/libcxx/include/version +++ b/libcxx/include/version @@ -110,6 +110,7 @@ __cpp_lib_void_t 201411L <type_traits> # define __cpp_lib_filesystem 201703L # define __cpp_lib_invoke 201411L # define __cpp_lib_void_t 201411L +# define __cpp_lib_node_extract 201606L #endif #if _LIBCPP_STD_VER > 17 |
