Index: libcxx/trunk/include/__hash_table =================================================================== --- libcxx/trunk/include/__hash_table +++ libcxx/trunk/include/__hash_table @@ -1058,8 +1058,26 @@ ); } +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 __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 @@ _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Table& __source); template _LIBCPP_INLINE_VISIBILITY @@ -1177,6 +1198,9 @@ template _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Table& __source); template _LIBCPP_INLINE_VISIBILITY @@ -1849,73 +1873,112 @@ } } + +// 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 -pair::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(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(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 +_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 +pair::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(__ndptr, this), __inserted); + return pair(iterator(__existing_node, this), __inserted); #else - return pair(iterator(__ndptr), __inserted); + return pair(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 -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 @@ 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 @@ // 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 @@ 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 +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 @@ } } ++size(); +} + + +template +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 @@ } template +template +_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 template _LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator @@ -2244,6 +2362,27 @@ return __result; } +template +template +_LIBCPP_INLINE_VISIBILITY +void +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( + _Table& __source) +{ + static_assert(is_same::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 Index: libcxx/trunk/include/__node_handle =================================================================== --- libcxx/trunk/include/__node_handle +++ libcxx/trunk/include/__node_handle @@ -26,9 +26,6 @@ #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 struct __generic_container_node_destructor; Index: libcxx/trunk/include/__tree =================================================================== --- libcxx/trunk/include/__tree +++ libcxx/trunk/include/__tree @@ -1341,15 +1341,20 @@ #endif // !_LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY pair __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 @@ -1358,6 +1363,9 @@ template _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Tree& __source); template _LIBCPP_INLINE_VISIBILITY @@ -1365,6 +1373,9 @@ template _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Tree& __source); template @@ -1384,7 +1395,7 @@ void __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, - __node_base_pointer __new_node); + __node_base_pointer __new_node) _NOEXCEPT; template iterator find(const _Key& __v); @@ -2129,10 +2140,9 @@ } template -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 @@ template 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 @@ } template +template +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) +{ + static_assert(is_same::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 template _LIBCPP_INLINE_VISIBILITY typename __tree<_Tp, _Compare, _Allocator>::iterator @@ -2507,6 +2541,28 @@ return iterator(__ptr); } +template +template +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) +{ + static_assert(is_same::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 Index: libcxx/trunk/include/map =================================================================== --- libcxx/trunk/include/map +++ libcxx/trunk/include/map @@ -167,6 +167,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(map& source); // C++17 + template + void merge(map&& source); // C++17 + template + void merge(multimap& source); // C++17 + template + void merge(multimap&& source); // C++17 + void swap(map& m) noexcept(allocator_traits::is_always_equal::value && is_nothrow_swappable::value); // C++17 @@ -368,6 +377,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(multimap& source); // C++17 + template + void merge(multimap&& source); // C++17 + template + void merge(map& source); // C++17 + template + void merge(map&& source); // C++17 + void swap(multimap& m) noexcept(allocator_traits::is_always_equal::value && is_nothrow_swappable::value); // C++17 @@ -926,6 +944,11 @@ typedef __insert_return_type insert_return_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS map; + template + friend class _LIBCPP_TEMPLATE_VIS multimap; + _LIBCPP_INLINE_VISIBILITY map() _NOEXCEPT_( @@ -1300,6 +1323,38 @@ { return __tree_.template __node_handle_extract(__it.__i_); } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap&& __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 @@ typedef __map_node_handle node_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS map; + template + friend class _LIBCPP_TEMPLATE_VIS multimap; + _LIBCPP_INLINE_VISIBILITY multimap() _NOEXCEPT_( @@ -1882,6 +1942,38 @@ return __tree_.template __node_handle_extract( __it.__i_); } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multimap&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(map&& __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 Index: libcxx/trunk/include/set =================================================================== --- libcxx/trunk/include/set +++ libcxx/trunk/include/set @@ -128,6 +128,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(set& source); // C++17 + template + void merge(set&& source); // C++17 + template + void merge(multiset& source); // C++17 + template + void merge(multiset&& source); // C++17 + void swap(set& s) noexcept( __is_nothrow_swappable::value && @@ -316,6 +325,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(multiset& source); // C++17 + template + void merge(multiset&& source); // C++17 + template + void merge(set& source); // C++17 + template + void merge(set&& source); // C++17 + void swap(multiset& s) noexcept( __is_nothrow_swappable::value && @@ -410,6 +428,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +class multiset; + template , class _Allocator = allocator<_Key> > class _LIBCPP_TEMPLATE_VIS set @@ -449,6 +470,11 @@ typedef __insert_return_type insert_return_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS set; + template + friend class _LIBCPP_TEMPLATE_VIS multiset; + _LIBCPP_INLINE_VISIBILITY set() _NOEXCEPT_( @@ -681,6 +707,38 @@ { return __tree_.template __node_handle_extract(__it); } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset&& __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 @@ typedef __set_node_handle node_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS set; + template + friend class _LIBCPP_TEMPLATE_VIS multiset; + // construct/copy/destroy: _LIBCPP_INLINE_VISIBILITY multiset() @@ -1122,6 +1185,38 @@ { return __tree_.template __node_handle_extract(__it); } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(multiset&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(set&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __tree_.__node_handle_merge_multi(__source.__tree_); + } #endif _LIBCPP_INLINE_VISIBILITY Index: libcxx/trunk/include/unordered_map =================================================================== --- libcxx/trunk/include/unordered_map +++ libcxx/trunk/include/unordered_map @@ -153,6 +153,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(unordered_map& source); // C++17 + template + void merge(unordered_map&& source); // C++17 + template + void merge(unordered_multimap& source); // C++17 + template + void merge(unordered_multimap&& source); // C++17 + void swap(unordered_map&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -325,6 +334,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(unordered_multimap& source); // C++17 + template + void merge(unordered_multimap&& source); // C++17 + template + void merge(unordered_map& source); // C++17 + template + void merge(unordered_map&& source); // C++17 + void swap(unordered_multimap&) noexcept( (!allocator_type::propagate_on_container_swap::value || @@ -808,6 +826,9 @@ template friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; }; +template +class unordered_multimap; + template , class _Pred = equal_to<_Key>, class _Alloc = allocator > > class _LIBCPP_TEMPLATE_VIS unordered_map @@ -865,6 +886,11 @@ typedef __insert_return_type insert_return_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS unordered_map; + template + friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; + _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1188,6 +1214,39 @@ return __table_.template __node_handle_extract( __it.__i_); } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_unique(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap&& __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 @@ typedef __map_node_handle<__node, allocator_type> node_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS unordered_map; + template + friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; + _LIBCPP_INLINE_VISIBILITY unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1847,6 +1911,39 @@ return __table_.template __node_handle_extract( __it.__i_); } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multimap&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_map&& __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 Index: libcxx/trunk/include/unordered_set =================================================================== --- libcxx/trunk/include/unordered_set +++ libcxx/trunk/include/unordered_set @@ -127,6 +127,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(unordered_set& source); // C++17 + template + void merge(unordered_set&& source); // C++17 + template + void merge(unordered_multiset& source); // C++17 + template + void merge(unordered_multiset&& source); // C++17 + void swap(unordered_set&) noexcept(allocator_traits::is_always_equal::value && noexcept(swap(declval(), declval())) && @@ -282,6 +291,15 @@ iterator erase(const_iterator first, const_iterator last); void clear() noexcept; + template + void merge(unordered_multiset& source); // C++17 + template + void merge(unordered_multiset&& source); // C++17 + template + void merge(unordered_set& source); // C++17 + template + void merge(unordered_set&& source); // C++17 + void swap(unordered_multiset&) noexcept(allocator_traits::is_always_equal::value && noexcept(swap(declval(), declval())) && @@ -348,6 +366,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template +class unordered_multiset; + template , class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > class _LIBCPP_TEMPLATE_VIS unordered_set @@ -385,6 +406,11 @@ typedef __insert_return_type insert_return_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS unordered_set; + template + friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; + _LIBCPP_INLINE_VISIBILITY unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -590,6 +616,39 @@ { return __table_.template __node_handle_extract(__it); } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + __table_.__node_handle_merge_unique(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset&& __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 @@ typedef __set_node_handle node_type; #endif + template + friend class _LIBCPP_TEMPLATE_VIS unordered_set; + template + friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; + _LIBCPP_INLINE_VISIBILITY unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1102,6 +1166,39 @@ { return __table_.template __node_handle_extract(__key); } + + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_multiset&& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set& __source) + { + _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), + "merging container with incompatible allocator"); + return __table_.__node_handle_merge_multi(__source.__table_); + } + template + _LIBCPP_INLINE_VISIBILITY + void merge(unordered_set&& __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 Index: libcxx/trunk/include/version =================================================================== --- libcxx/trunk/include/version +++ libcxx/trunk/include/version @@ -110,6 +110,7 @@ # 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 Index: libcxx/trunk/test/std/containers/associative/map/map.modifiers/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/associative/map/map.modifiers/merge.pass.cpp +++ libcxx/trunk/test/std/containers/associative/map/map.modifiers/merge.pass.cpp @@ -0,0 +1,149 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class map + +// template +// void merge(map& source); +// template +// void merge(map&& source); +// template +// void merge(multimap& source); +// template +// void merge(multimap&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::map src{{1, 0}, {3, 0}, {5, 0}}; + std::map dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {{5,0}})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::map, int, throw_comparator> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::map, int, std::less>> first_map_type; + typedef std::map, int, comparator> second_map_type; + typedef std::multimap, int, comparator> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + assert(Counter_base::gConstructed == 0); + { + std::map first; + { + std::map second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multimap second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/trunk/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp +++ libcxx/trunk/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp @@ -0,0 +1,149 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class multimap + +// template +// void merge(map& source); +// template +// void merge(map&& source); +// template +// void merge(multimap& source); +// template +// void merge(multimap&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::multimap src{{1, 0}, {3, 0}, {5, 0}}; + std::multimap dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::multimap, int, throw_comparator> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::multimap, int, std::less>> first_map_type; + typedef std::multimap, int, comparator> second_map_type; + typedef std::map, int, comparator> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {1, 0}, {2, 0}, {2, 0}, {3, 0}, {3, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {1, 0}, {2, 0}, {2, 0}, {3, 0}, {3, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + assert(Counter_base::gConstructed == 0); + { + std::multimap first; + { + std::multimap second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multimap second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/trunk/test/std/containers/associative/multiset/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/associative/multiset/merge.pass.cpp +++ libcxx/trunk/test/std/containers/associative/multiset/merge.pass.cpp @@ -0,0 +1,148 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class multiset + +// template +// void merge(set& source); +// template +// void merge(set&& source); +// template +// void merge(multiset& source); +// template +// void merge(multiset&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::multiset src{1, 3, 5}; + std::multiset dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {})); + assert(set_equal(dst, {1, 2, 3, 4, 5, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::multiset, throw_comparator> set_type; + set_type src({1, 3, 5}, throw_comparator(do_throw)); + set_type dst({2, 4, 5}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::multiset, std::less>> first_set_type; + typedef std::multiset, comparator> second_set_type; + typedef std::set, comparator> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 1, 2, 2, 3, 3, 3, 4})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 1, 2, 2, 3, 3, 3, 4})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::multiset first; + { + std::multiset second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::set second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/trunk/test/std/containers/associative/set/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/associative/set/merge.pass.cpp +++ libcxx/trunk/test/std/containers/associative/set/merge.pass.cpp @@ -0,0 +1,148 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class set + +// template +// void merge(set& source); +// template +// void merge(set&& source); +// template +// void merge(multiset& source); +// template +// void merge(multiset&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +struct throw_comparator +{ + bool& should_throw_; + + throw_comparator(bool& should_throw) : should_throw_(should_throw) {} + + template + bool operator()(const T& lhs, const T& rhs) const + { + if (should_throw_) + throw 0; + return lhs < rhs; + } +}; +#endif + +int main() +{ + { + std::set src{1, 3, 5}; + std::set dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {5})); + assert(set_equal(dst, {1, 2, 3, 4, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::set, throw_comparator> set_type; + set_type src({1, 3, 5}, throw_comparator(do_throw)); + set_type dst({2, 4, 5}, throw_comparator(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct comparator + { + comparator() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs < rhs; + } + }; + { + typedef std::set, std::less>> first_set_type; + typedef std::set, comparator> second_set_type; + typedef std::multiset, comparator> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::set first; + { + std::set second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::multiset second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp +++ libcxx/trunk/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp @@ -0,0 +1,161 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class unordered_map + +// template +// void merge(unordered_map& source); +// template +// void merge(unordered_map&& source); +// template +// void merge(unordered_multimap& source); +// template +// void merge(unordered_multimap&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_map src{{1, 0}, {3, 0}, {5, 0}}; + std::unordered_map dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {{5,0}})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_map, int, throw_hasher>> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher>(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const + { + return std::hash>()(p); + } + }; + { + typedef std::unordered_map, int, std::hash>, std::equal_to>> first_map_type; + typedef std::unordered_map, int, hasher, equal> second_map_type; + typedef std::unordered_multimap, int, hasher, equal> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}})); + assert(map_equal(second, {{2, 0}, {3, 0}})); + assert(map_equal(third, {{1, 0}, {3, 0}})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_map first; + { + std::unordered_map second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_multimap second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/trunk/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp +++ libcxx/trunk/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp @@ -0,0 +1,161 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class unordered_multimap + +// template +// void merge(unordered_map& source); +// template +// void merge(unordered_map&& source); +// template +// void merge(unordered_multimap& source); +// template +// void merge(unordered_multimap&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool map_equal(const Map& map, Map other) +{ + return map == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_multimap src{{1, 0}, {3, 0}, {5, 0}}; + std::unordered_multimap dst{{2, 0}, {4, 0}, {5, 0}}; + dst.merge(src); + assert(map_equal(src, {})); + assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_multimap, int, throw_hasher>> map_type; + map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher>(do_throw)); + map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher>(do_throw)))); + assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const + { + return std::hash>()(p); + } + }; + { + typedef std::unordered_multimap, int, std::hash>, std::equal_to>> first_map_type; + typedef std::unordered_multimap, int, hasher, equal> second_map_type; + typedef std::unordered_map, int, hasher, equal> third_map_type; + + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {2, 0}, {3, 0}, {1, 0}, {3, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_map_type first{{1, 0}, {2, 0}, {3, 0}}; + second_map_type second{{2, 0}, {3, 0}, {4, 0}}; + third_map_type third{{1, 0}, {3, 0}}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {2, 0}, {3, 0}, {1, 0}, {3, 0}})); + assert(map_equal(second, {})); + assert(map_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_multimap first; + { + std::unordered_multimap second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_map second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/trunk/test/std/containers/unord/unord.multiset/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/unord/unord.multiset/merge.pass.cpp +++ libcxx/trunk/test/std/containers/unord/unord.multiset/merge.pass.cpp @@ -0,0 +1,158 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class unordered_multiset + +// template +// void merge(unordered_set& source); +// template +// void merge(unordered_set&& source); +// template +// void merge(unordered_multiset& source); +// template +// void merge(unordered_multiset&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_multiset src{1, 3, 5}; + std::unordered_multiset dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {})); + assert(set_equal(dst, {1, 2, 3, 4, 5, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_multiset, throw_hasher>> set_type; + set_type src({1, 3, 5}, 0, throw_hasher>(do_throw)); + set_type dst({2, 4, 5}, 0, throw_hasher>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher>(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const { return std::hash>()(p); } + }; + { + typedef std::unordered_multiset, std::hash>, std::equal_to>> first_set_type; + typedef std::unordered_multiset, hasher, equal> second_set_type; + typedef std::unordered_set, hasher, equal> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 2, 3, 4, 2, 3, 1, 3})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 2, 3, 4, 2, 3, 1, 3})); + assert(set_equal(second, {})); + assert(set_equal(third, {})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_multiset first; + { + std::unordered_multiset second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_set second; + first.merge(second); + first.merge(std::move(second)); + } + } +} Index: libcxx/trunk/test/std/containers/unord/unord.set/merge.pass.cpp =================================================================== --- libcxx/trunk/test/std/containers/unord/unord.set/merge.pass.cpp +++ libcxx/trunk/test/std/containers/unord/unord.set/merge.pass.cpp @@ -0,0 +1,158 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// + +// class unordered_set + +// template +// void merge(unordered_set& source); +// template +// void merge(unordered_set&& source); +// template +// void merge(unordered_multiset& source); +// template +// void merge(unordered_multiset&& source); + +#include +#include "test_macros.h" +#include "Counter.h" + +template +bool set_equal(const Set& set, Set other) +{ + return set == other; +} + +#ifndef TEST_HAS_NO_EXCEPTIONS +template +struct throw_hasher +{ + bool& should_throw_; + + throw_hasher(bool& should_throw) : should_throw_(should_throw) {} + + typedef size_t result_type; + typedef T argument_type; + + size_t operator()(const T& p) const + { + if (should_throw_) + throw 0; + return std::hash()(p); + } +}; +#endif + +int main() +{ + { + std::unordered_set src{1, 3, 5}; + std::unordered_set dst{2, 4, 5}; + dst.merge(src); + assert(set_equal(src, {5})); + assert(set_equal(dst, {1, 2, 3, 4, 5})); + } + +#ifndef TEST_HAS_NO_EXCEPTIONS + { + bool do_throw = false; + typedef std::unordered_set, throw_hasher>> set_type; + set_type src({1, 3, 5}, 0, throw_hasher>(do_throw)); + set_type dst({2, 4, 5}, 0, throw_hasher>(do_throw)); + + assert(Counter_base::gConstructed == 6); + + do_throw = true; + try + { + dst.merge(src); + } + catch (int) + { + do_throw = false; + } + assert(!do_throw); + assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher>(do_throw)))); + assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher>(do_throw)))); + } +#endif + assert(Counter_base::gConstructed == 0); + struct equal + { + equal() = default; + + bool operator()(const Counter& lhs, const Counter& rhs) const + { + return lhs == rhs; + } + }; + struct hasher + { + hasher() = default; + typedef Counter argument_type; + typedef size_t result_type; + size_t operator()(const Counter& p) const { return std::hash>()(p); } + }; + { + typedef std::unordered_set, std::hash>, std::equal_to>> first_set_type; + typedef std::unordered_set, hasher, equal> second_set_type; + typedef std::unordered_multiset, hasher, equal> third_set_type; + + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(second); + first.merge(third); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + { + first_set_type first{1, 2, 3}; + second_set_type second{2, 3, 4}; + third_set_type third{1, 3}; + + assert(Counter_base::gConstructed == 8); + + first.merge(std::move(second)); + first.merge(std::move(third)); + + assert(set_equal(first, {1, 2, 3, 4})); + assert(set_equal(second, {2, 3})); + assert(set_equal(third, {1, 3})); + + assert(Counter_base::gConstructed == 8); + } + assert(Counter_base::gConstructed == 0); + } + { + std::unordered_set first; + { + std::unordered_set second; + first.merge(second); + first.merge(std::move(second)); + } + { + std::unordered_multiset second; + first.merge(second); + first.merge(std::move(second)); + } + } +}