Index: include/CMakeLists.txt =================================================================== --- include/CMakeLists.txt +++ include/CMakeLists.txt @@ -11,6 +11,7 @@ __libcpp_version __locale __mutex_base + __node_handle __nullptr __split_buffer __sso_allocator Index: include/__hash_table =================================================================== --- include/__hash_table +++ include/__hash_table @@ -859,6 +859,17 @@ template friend class __hash_map_node_destructor; }; +#if _LIBCPP_STD_VER > 14 +template +struct __generic_container_node_destructor; + +template +struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> + : __hash_node_destructor<_Alloc> +{ + using __hash_node_destructor<_Alloc>::__hash_node_destructor; +}; +#endif #ifndef _LIBCPP_CXX03_LANG template @@ -1151,6 +1162,30 @@ return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x); } +#if _LIBCPP_STD_VER > 14 + template + _LIBCPP_INLINE_VISIBILITY + _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_unique(const_iterator __hint, + _NodeHandle&& __nh); + + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(_NodeHandle&& __nh); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); + + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract(key_type const& __key); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract(const_iterator __it); +#endif + void clear() _NOEXCEPT; void rehash(size_type __n); _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) @@ -2126,6 +2161,91 @@ #endif // _LIBCPP_CXX03_LANG +#if _LIBCPP_STD_VER > 14 +template +template +_LIBCPP_INLINE_VISIBILITY +_InsertReturnType +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( + _NodeHandle&& __nh) +{ + if (__nh.empty()) + return _InsertReturnType{end(), false, _NodeHandle()}; + pair __result = __node_insert_unique(__nh.__ptr_); + if (__result.second) + __nh.__release(); + return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)}; +} + +template +template +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( + const_iterator, _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + pair __result = __node_insert_unique(__nh.__ptr_); + if (__result.second) + __nh.__release(); + return __result.first; +} + +template +template +_LIBCPP_INLINE_VISIBILITY +_NodeHandle +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( + key_type const& __key) +{ + iterator __i = find(__key); + if (__i == end()) + return _NodeHandle(); + return __node_handle_extract<_NodeHandle>(__i); +} + +template +template +_LIBCPP_INLINE_VISIBILITY +_NodeHandle +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( + const_iterator __p) +{ + allocator_type __alloc(__node_alloc()); + return _NodeHandle(remove(__p).release(), __alloc); +} + +template +template +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( + _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + iterator __result = __node_insert_multi(__nh.__ptr_); + __nh.__release(); + return __result; +} + +template +template +_LIBCPP_INLINE_VISIBILITY +typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator +__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( + const_iterator __hint, _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + iterator __result = __node_insert_multi(__hint, __nh.__ptr_); + __nh.__release(); + return __result; +} + +#endif // _LIBCPP_STD_VER > 14 + template void __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) Index: include/__node_handle =================================================================== --- include/__node_handle +++ include/__node_handle @@ -0,0 +1,212 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___NODE_HANDLE +#define _LIBCPP___NODE_HANDLE + +#include <__config> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 14 + +#define __cpp_lib_node_extract 201606L + +// Specialized in __tree & __hash_table for their _NodeType. +template +struct __generic_container_node_destructor; + +template class _MapOrSetSpecifics> +class _LIBCPP_TEMPLATE_VIS __basic_node_handle + : public _MapOrSetSpecifics< + _NodeType, + __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>> +{ + template + friend class __tree; + template + friend class __hash_table; + friend struct _MapOrSetSpecifics< + _NodeType, __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>; + + typedef allocator_traits<_Alloc> __alloc_traits; + typedef typename __rebind_pointer::type + __node_pointer_type; + +public: + typedef _Alloc allocator_type; + +private: + __node_pointer_type __ptr_ = nullptr; + optional __alloc_; + + _LIBCPP_INLINE_VISIBILITY + void __release() + { + __ptr_ = nullptr; + __alloc_ = _VSTD::nullopt; + } + + _LIBCPP_INLINE_VISIBILITY + void __destroy_node_pointer() + { + if (__ptr_ != nullptr) + { + typedef typename __allocator_traits_rebind< + allocator_type, _NodeType>::type __node_alloc_type; + __node_alloc_type __alloc(*__alloc_); + __generic_container_node_destructor<_NodeType, __node_alloc_type>( + __alloc, true)(__ptr_); + __ptr_ = nullptr; + } + } + + _LIBCPP_INLINE_VISIBILITY + __basic_node_handle(__node_pointer_type __ptr, + allocator_type const& __alloc) + : __ptr_(__ptr), __alloc_(__alloc) + { + } + +public: + _LIBCPP_INLINE_VISIBILITY + __basic_node_handle() = default; + + _LIBCPP_INLINE_VISIBILITY + __basic_node_handle(__basic_node_handle&& __other) noexcept + : __ptr_(__other.__ptr_), + __alloc_(_VSTD::move(__other.__alloc_)) + { + __other.__ptr_ = nullptr; + __other.__alloc_ = _VSTD::nullopt; + } + + _LIBCPP_INLINE_VISIBILITY + __basic_node_handle& operator=(__basic_node_handle&& __other) + { + _LIBCPP_ASSERT( + __alloc_ == _VSTD::nullopt || + __alloc_traits::propagate_on_container_move_assignment::value || + __alloc_ == __other.__alloc_, + "node_type with incompatible allocator passed to " + "node_type::operator=(node_type&&)"); + + __destroy_node_pointer(); + __ptr_ = __other.__ptr_; + + if (__alloc_traits::propagate_on_container_move_assignment::value || + __alloc_ == _VSTD::nullopt) + __alloc_ = _VSTD::move(__other.__alloc_); + + __other.__ptr_ = nullptr; + __other.__alloc_ = _VSTD::nullopt; + + return *this; + } + + _LIBCPP_INLINE_VISIBILITY + allocator_type get_allocator() const { return *__alloc_; } + + _LIBCPP_INLINE_VISIBILITY + explicit operator bool() const { return __ptr_ != nullptr; } + + _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY + bool empty() const { return __ptr_ == nullptr; } + + _LIBCPP_INLINE_VISIBILITY + void swap(__basic_node_handle& __other) noexcept( + __alloc_traits::propagate_on_container_swap::value || + __alloc_traits::is_always_equal::value) + { + using _VSTD::swap; + swap(__ptr_, __other.__ptr_); + if (__alloc_traits::propagate_on_container_swap::value || + __alloc_ == _VSTD::nullopt || __other.__alloc_ == _VSTD::nullopt) + swap(__alloc_, __other.__alloc_); + } + + _LIBCPP_INLINE_VISIBILITY + friend void swap(__basic_node_handle& __a, __basic_node_handle& __b) + noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); } + + _LIBCPP_INLINE_VISIBILITY + ~__basic_node_handle() + { + __destroy_node_pointer(); + } +}; + +template +struct __set_node_handle_specifics +{ + typedef typename _NodeType::__node_value_type value_type; + + _LIBCPP_INLINE_VISIBILITY + value_type& value() const + { + return static_cast<_Derived const*>(this)->__ptr_->__value_; + } +}; + +template +struct __map_node_handle_specifics +{ + typedef typename _NodeType::__node_value_type::key_type key_type; + typedef typename _NodeType::__node_value_type::mapped_type mapped_type; + + _LIBCPP_INLINE_VISIBILITY + key_type& key() const + { + return static_cast<_Derived const*>(this)-> + __ptr_->__value_.__ref().first; + } + + _LIBCPP_INLINE_VISIBILITY + mapped_type& mapped() const + { + return static_cast<_Derived const*>(this)-> + __ptr_->__value_.__ref().second; + } +}; + +template +using __set_node_handle = + __basic_node_handle< _NodeType, _Alloc, __set_node_handle_specifics>; + +template +using __map_node_handle = + __basic_node_handle< _NodeType, _Alloc, __map_node_handle_specifics>; + +template +_LIBCPP_TEMPLATE_VIS +struct __insert_return_type +{ + _Iterator position; + bool inserted; + _NodeType node; +}; + +#endif // _LIBCPP_STD_VER > 14 + +_LIBCPP_END_NAMESPACE_STD +_LIBCPP_POP_MACROS + +#endif Index: include/__tree =================================================================== --- include/__tree +++ include/__tree @@ -796,6 +796,16 @@ template friend class __map_node_destructor; }; +#if _LIBCPP_STD_VER > 14 +template +struct __generic_container_node_destructor; +template +struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc> + : __tree_node_destructor<_Alloc> +{ + using __tree_node_destructor<_Alloc>::__tree_node_destructor; +}; +#endif template class _LIBCPP_TEMPLATE_VIS __tree_iterator @@ -1338,6 +1348,33 @@ iterator __node_insert_multi(__node_pointer __nd); iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); + + _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer); + +#if _LIBCPP_STD_VER > 14 + template + _LIBCPP_INLINE_VISIBILITY + _InsertReturnType __node_handle_insert_unique(_NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(_NodeHandle&&); + template + _LIBCPP_INLINE_VISIBILITY + iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); + + + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract(key_type const&); + template + _LIBCPP_INLINE_VISIBILITY + _NodeHandle __node_handle_extract(const_iterator); +#endif + iterator erase(const_iterator __p); iterator erase(const_iterator __f, const_iterator __l); template @@ -2347,17 +2384,138 @@ template typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) +__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) { - __node_pointer __np = __p.__get_np(); - iterator __r(__p.__ptr_); + iterator __r(__ptr); ++__r; - if (__begin_node() == __p.__ptr_) + if (__begin_node() == __ptr) __begin_node() = __r.__ptr_; --size(); - __node_allocator& __na = __node_alloc(); __tree_remove(__end_node()->__left_, - static_cast<__node_base_pointer>(__np)); + static_cast<__node_base_pointer>(__ptr)); + return __r; +} + +#if _LIBCPP_STD_VER > 14 +template +template +_LIBCPP_INLINE_VISIBILITY +_InsertReturnType +__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique( + _NodeHandle&& __nh) +{ + if (__nh.empty()) + return _InsertReturnType{end(), false, _NodeHandle()}; + + __node_pointer __ptr = __nh.__ptr_; + __parent_pointer __parent; + __node_base_pointer& __child = __find_equal(__parent, + __ptr->__value_); + if (__child != nullptr) + return _InsertReturnType{ + iterator(static_cast<__node_pointer>(__child)), + false, _VSTD::move(__nh)}; + + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__ptr)); + __nh.__release(); + return _InsertReturnType{iterator(__ptr), true, _NodeHandle()}; +} + +template +template +_LIBCPP_INLINE_VISIBILITY +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique( + const_iterator __hint, _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + + __node_pointer __ptr = __nh.__ptr_; + __parent_pointer __parent; + __node_base_pointer __dummy; + __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy, + __ptr->__value_); + __node_pointer __r = static_cast<__node_pointer>(__child); + if (__child == nullptr) + { + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__ptr)); + __r = __ptr; + __nh.__release(); + } + return iterator(__r); +} + +template +template +_LIBCPP_INLINE_VISIBILITY +_NodeHandle +__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) +{ + iterator __it = find(__key); + if (__it == end()) + return _NodeHandle(); + return __node_handle_extract<_NodeHandle>(__it); +} + +template +template +_LIBCPP_INLINE_VISIBILITY +_NodeHandle +__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) +{ + __node_pointer __np = __p.__get_np(); + __remove_node_pointer(__np); + return _NodeHandle(__np, __alloc()); +} + +template +template +_LIBCPP_INLINE_VISIBILITY +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + __node_pointer __ptr = __nh.__ptr_; + __parent_pointer __parent; + __node_base_pointer& __child = __find_leaf_high( + __parent, _NodeTypes::__get_key(__ptr->__value_)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); + __nh.__release(); + return iterator(__ptr); +} + +template +template +_LIBCPP_INLINE_VISIBILITY +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi( + const_iterator __hint, _NodeHandle&& __nh) +{ + if (__nh.empty()) + return end(); + + __node_pointer __ptr = __nh.__ptr_; + __parent_pointer __parent; + __node_base_pointer& __child = __find_leaf(__hint, __parent, + _NodeTypes::__get_key(__ptr->__value_)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr)); + __nh.__release(); + return iterator(__ptr); +} + +#endif // _LIBCPP_STD_VER > 14 + +template +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) +{ + __node_pointer __np = __p.__get_np(); + iterator __r = __remove_node_pointer(__np); + __node_allocator& __na = __node_alloc(); __node_traits::destroy(__na, _NodeTypes::__get_ptr( const_cast<__node_value_type&>(*__p))); __node_traits::deallocate(__na, __np, 1); Index: include/map =================================================================== --- include/map +++ include/map @@ -40,6 +40,8 @@ typedef implementation-defined const_iterator; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; + typedef unspecified node_type; // C++17 + typedef INSERT_RETURN_TYPE insert_return_type; // C++17 class value_compare : public binary_function @@ -137,6 +139,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list il); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + insert_return_type insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + template pair try_emplace(const key_type& k, Args&&... args); // C++17 template @@ -260,6 +267,7 @@ typedef implementation-defined const_iterator; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; + typedef unspecified node_type; // C++17 class value_compare : public binary_function @@ -349,6 +357,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list il); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + iterator insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); @@ -440,6 +453,7 @@ #include <__config> #include <__tree> +#include <__node_handle> #include #include #include @@ -906,6 +920,11 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle node_type; + typedef __insert_return_type insert_return_type; +#endif + _LIBCPP_INLINE_VISIBILITY map() _NOEXCEPT_( @@ -1253,6 +1272,35 @@ _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__tree_.clear();} +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + insert_return_type insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to map::insert()"); + return __tree_.template __node_handle_insert_unique< + node_type, insert_return_type>(_VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __hint, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to map::insert()"); + return __tree_.template __node_handle_insert_unique( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract(__it.__i_); + } +#endif + _LIBCPP_INLINE_VISIBILITY void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) @@ -1562,6 +1610,10 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle node_type; +#endif + _LIBCPP_INLINE_VISIBILITY multimap() _NOEXCEPT_( @@ -1800,6 +1852,37 @@ _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __f, const_iterator __l) {return __tree_.erase(__f.__i_, __l.__i_);} + +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + iterator insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to multimap::insert()"); + return __tree_.template __node_handle_insert_multi( + _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __hint, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to multimap::insert()"); + return __tree_.template __node_handle_insert_multi( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract( + __it.__i_); + } +#endif + _LIBCPP_INLINE_VISIBILITY void clear() {__tree_.clear();} Index: include/module.modulemap =================================================================== --- include/module.modulemap +++ include/module.modulemap @@ -498,6 +498,7 @@ module __tree { header "__tree" export * } module __tuple { header "__tuple" export * } module __undef_macros { header "__undef_macros" export * } + module __node_handle { header "__node_handle" export * } module experimental { requires cplusplus11 Index: include/set =================================================================== --- include/set +++ include/set @@ -40,6 +40,8 @@ typedef implementation-defined const_iterator; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; + typedef unspecified node_type; // C++17 + typedef INSERT_RETURN_TYPE insert_return_type; // C++17 // construct/copy/destroy: set() @@ -115,6 +117,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list il); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + insert_return_type insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); @@ -222,6 +229,7 @@ typedef implementation-defined const_iterator; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; + typedef unspecified node_type; // C++17 // construct/copy/destroy: multiset() @@ -297,6 +305,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list il); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + iterator insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); @@ -387,6 +400,7 @@ #include <__config> #include <__tree> +#include <__node_handle> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -429,6 +443,11 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __set_node_handle node_type; + typedef __insert_return_type insert_return_type; +#endif + _LIBCPP_INLINE_VISIBILITY set() _NOEXCEPT_( @@ -634,6 +653,35 @@ _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__tree_.clear();} +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + insert_return_type insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to set::insert()"); + return __tree_.template __node_handle_insert_unique< + node_type, insert_return_type>(_VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __hint, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to set::insert()"); + return __tree_.template __node_handle_insert_unique( + __hint, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract(__it); + } +#endif + _LIBCPP_INLINE_VISIBILITY void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) {__tree_.swap(__s.__tree_);} @@ -838,6 +886,10 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __set_node_handle node_type; +#endif + // construct/copy/destroy: _LIBCPP_INLINE_VISIBILITY multiset() @@ -1042,6 +1094,35 @@ _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__tree_.clear();} +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + iterator insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to multiset::insert()"); + return __tree_.template __node_handle_insert_multi( + _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __hint, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to multiset::insert()"); + return __tree_.template __node_handle_insert_multi( + __hint, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __tree_.template __node_handle_extract(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __tree_.template __node_handle_extract(__it); + } +#endif + _LIBCPP_INLINE_VISIBILITY void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) Index: include/unordered_map =================================================================== --- include/unordered_map +++ include/unordered_map @@ -44,6 +44,9 @@ typedef /unspecified/ local_iterator; typedef /unspecified/ const_local_iterator; + typedef unspecified node_type; // C++17 + typedef INSERT_RETURN_TYPE insert_return_type; // C++17 + unordered_map() noexcept( is_nothrow_default_constructible::value && @@ -122,6 +125,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + insert_return_type insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + template pair try_emplace(const key_type& k, Args&&... args); // C++17 template @@ -226,6 +234,8 @@ typedef /unspecified/ local_iterator; typedef /unspecified/ const_local_iterator; + typedef unspecified node_type; // C++17 + unordered_multimap() noexcept( is_nothrow_default_constructible::value && @@ -304,6 +314,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + iterator insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); @@ -367,6 +382,7 @@ #include <__config> #include <__hash_table> +#include <__node_handle> #include #include #include @@ -843,6 +859,11 @@ typedef __hash_map_iterator local_iterator; typedef __hash_map_const_iterator const_local_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle<__node, allocator_type> node_type; + typedef __insert_return_type insert_return_type; +#endif + _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1136,7 +1157,37 @@ iterator erase(const_iterator __first, const_iterator __last) {return __table_.erase(__first.__i_, __last.__i_);} _LIBCPP_INLINE_VISIBILITY - void clear() _NOEXCEPT {__table_.clear();} + void clear() _NOEXCEPT {__table_.clear();} + +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + insert_return_type insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_map::insert()"); + return __table_.template __node_handle_insert_unique< + node_type, insert_return_type>(_VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __hint, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_map::insert()"); + return __table_.template __node_handle_insert_unique( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract( + __it.__i_); + } +#endif _LIBCPP_INLINE_VISIBILITY void swap(unordered_map& __u) @@ -1590,6 +1641,10 @@ typedef __hash_map_iterator local_iterator; typedef __hash_map_const_iterator const_local_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle<__node, allocator_type> node_type; +#endif + _LIBCPP_INLINE_VISIBILITY unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1763,6 +1818,36 @@ _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__table_.clear();} +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + iterator insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_multimap::insert()"); + return __table_.template __node_handle_insert_multi( + _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __hint, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_multimap::insert()"); + return __table_.template __node_handle_insert_multi( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract( + __it.__i_); + } +#endif + _LIBCPP_INLINE_VISIBILITY void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) Index: include/unordered_set =================================================================== --- include/unordered_set +++ include/unordered_set @@ -43,6 +43,9 @@ typedef /unspecified/ local_iterator; typedef /unspecified/ const_local_iterator; + typedef unspecified node_type unspecified; // C++17 + typedef INSERT_RETURN_TYPE insert_return_type; // C++17 + unordered_set() noexcept( is_nothrow_default_constructible::value && @@ -113,6 +116,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + insert_return_type insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); @@ -191,6 +199,8 @@ typedef /unspecified/ local_iterator; typedef /unspecified/ const_local_iterator; + typedef unspecified node_type unspecified; // C++17 + unordered_multiset() noexcept( is_nothrow_default_constructible::value && @@ -261,6 +271,11 @@ void insert(InputIterator first, InputIterator last); void insert(initializer_list); + node_type extract(const_iterator position); // C++17 + node_type extract(const key_type& x); // C++17 + iterator insert(node_type&& nh); // C++17 + iterator insert(const_iterator hint, node_type&& nh); // C++17 + iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); @@ -321,6 +336,7 @@ #include <__config> #include <__hash_table> +#include <__node_handle> #include #include <__debug> @@ -363,6 +379,11 @@ typedef typename __table::const_local_iterator local_iterator; typedef typename __table::const_local_iterator const_local_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __set_node_handle node_type; + typedef __insert_return_type insert_return_type; +#endif + _LIBCPP_INLINE_VISIBILITY unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -541,6 +562,35 @@ _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__table_.clear();} +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + insert_return_type insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_set::insert()"); + return __table_.template __node_handle_insert_unique< + node_type, insert_return_type>(_VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __h, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_set::insert()"); + return __table_.template __node_handle_insert_unique( + __h, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract(__it); + } +#endif + _LIBCPP_INLINE_VISIBILITY void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) @@ -883,6 +933,10 @@ typedef typename __table::const_local_iterator local_iterator; typedef typename __table::const_local_iterator const_local_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __set_node_handle node_type; +#endif + _LIBCPP_INLINE_VISIBILITY unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1019,6 +1073,36 @@ _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER > 14 + _LIBCPP_INLINE_VISIBILITY + iterator insert(node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_multiset::insert()"); + return __table_.template __node_handle_insert_multi( + _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __hint, node_type&& __nh) + { + _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to unordered_multiset::insert()"); + return __table_.template __node_handle_insert_multi( + __hint, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __position) + { + return __table_.template __node_handle_extract( + __position); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract(__key); + } +#endif + _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __table_.erase(__p);} _LIBCPP_INLINE_VISIBILITY Index: test/std/containers/associative/map/map.modifiers/extract_iterator.pass.cpp =================================================================== --- test/std/containers/associative/map/map.modifiers/extract_iterator.pass.cpp +++ test/std/containers/associative/map/map.modifiers/extract_iterator.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + auto some_key = c.cbegin()->first; + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = first->first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.key() == key_value); + t.key() = some_key; + assert(t.key() == some_key); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using map_type = std::map; + map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + test(m); + } + + { + std::map, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + assert(Counter_base::gConstructed == 12); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::map, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + test(m); + } +} Index: test/std/containers/associative/map/map.modifiers/extract_key.pass.cpp =================================================================== --- test/std/containers/associative/map/map.modifiers/extract_key.pass.cpp +++ test/std/containers/associative/map/map.modifiers/extract_key.pass.cpp @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.key() == *copy); + t.key() = *first; // We should be able to mutate key. + assert(t.key() == *first); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::map m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::map, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 12+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::map, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp =================================================================== --- test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp +++ test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp @@ -0,0 +1,85 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// insert_return_type insert(node_type&&); + +#include +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto p = c.insert({key, mapped}); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + typename Container::insert_return_type irt = c.insert(std::move(node)); + assert(node.empty()); + assert(irt.inserted); + assert(irt.node.empty()); + assert(irt.position->first == i && irt.position->second == i + 1); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto irt = c.insert(std::move(def)); + assert(def.empty()); + assert(!irt.inserted); + assert(irt.node.empty()); + assert(irt.position == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0, 42); + auto irt = c.insert(std::move(dupl)); + assert(dupl.empty()); + assert(!irt.inserted); + assert(!irt.node.empty()); + assert(irt.position == c.find(0)); + assert(irt.node.key() == 0 && irt.node.mapped() == 42); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c[i] == i + 1); + } +} + +int main() +{ + std::map m; + test(m); + std::map, min_allocator>> m2; + test(m2); +} Index: test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp +++ test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp @@ -0,0 +1,64 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto p = c.insert({key, mapped}); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(node.empty()); + assert(prev + 1 == c.size()); + assert(it->first == i); + assert(it->second == i + 1); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c[i] == i + 1); + } +} + +int main() +{ + std::map m; + test(m); + std::map, min_allocator>> m2; + test(m2); +} Index: test/std/containers/associative/multimap/multimap.modifiers/extract_iterator.pass.cpp =================================================================== --- test/std/containers/associative/multimap/multimap.modifiers/extract_iterator.pass.cpp +++ test/std/containers/associative/multimap/multimap.modifiers/extract_iterator.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + auto some_key = c.cbegin()->first; + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = first->first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.key() == key_value); + t.key() = some_key; + assert(t.key() == some_key); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using map_type = std::multimap; + map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + test(m); + } + + { + std::multimap, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + assert(Counter_base::gConstructed == 12); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::multimap, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + test(m); + } +} Index: test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp =================================================================== --- test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp +++ test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.key() == *copy); + t.key() = *first; // We should be able to mutate key. + assert(t.key() == *first); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::multimap m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::multimap, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 12+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::multimap, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/associative/multimap/multimap.modifiers/insert_node_type.pass.cpp =================================================================== --- test/std/containers/associative/multimap/multimap.modifiers/insert_node_type.pass.cpp +++ test/std/containers/associative/multimap/multimap.modifiers/insert_node_type.pass.cpp @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(node_type&&); + +#include +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto it = c.insert({key, mapped}); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + typename Container::iterator it = c.insert(std::move(node)); + assert(node.empty()); + assert(it == c.find(i) && it != c.end()); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto it = c.insert(std::move(def)); + assert(def.empty()); + assert(it == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0, 42); + auto it = c.insert(std::move(dupl)); + assert(dupl.empty()); + assert(it != c.end()); + assert(it->second == 42); + } + + assert(c.size() == 11); + assert(c.count(0) == 2); + for (int i = 1; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c.find(i)->second == i + 1); + } +} + +int main() +{ + std::multimap m; + test(m); + std::multimap, min_allocator>> m2; + test(m2); +} Index: test/std/containers/associative/multimap/multimap.modifiers/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/associative/multimap/multimap.modifiers/insert_node_type_hint.pass.cpp +++ test/std/containers/associative/multimap/multimap.modifiers/insert_node_type_hint.pass.cpp @@ -0,0 +1,64 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto it = c.insert({key, mapped}); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(node.empty()); + assert(prev + 1 == c.size()); + assert(it == c.find(i)); + assert(it->first == i); + assert(it->second == i + 1); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c.find(i)->second == i + 1); + } +} + +int main() +{ + std::multimap m; + test(m); + std::multimap, min_allocator>> m2; + test(m2); +} Index: test/std/containers/associative/multiset/extract_iterator.pass.cpp =================================================================== --- test/std/containers/associative/multiset/extract_iterator.pass.cpp +++ test/std/containers/associative/multiset/extract_iterator.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = *first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.value() == key_value); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using set_type = std::multiset; + set_type m = {1, 2, 3, 4, 5, 6}; + test(m); + } + + { + std::multiset> m = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::multiset, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + test(m); + } +} Index: test/std/containers/associative/multiset/extract_key.pass.cpp =================================================================== --- test/std/containers/associative/multiset/extract_key.pass.cpp +++ test/std/containers/associative/multiset/extract_key.pass.cpp @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.value() == *copy); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::multiset m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::multiset> m = {1, 2, 3, 4, 5, 6}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::multiset, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/associative/multiset/insert_node_type.pass.cpp =================================================================== --- test/std/containers/associative/multiset/insert_node_type.pass.cpp +++ test/std/containers/associative/multiset/insert_node_type.pass.cpp @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(node_type&&); + +#include +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto it = c.insert(key); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + typename Container::iterator it = c.insert(std::move(node)); + assert(node.empty()); + assert(it == c.find(i) && it != c.end()); + assert(*it == i); + assert(node.empty()); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto it = c.insert(std::move(def)); + assert(def.empty()); + assert(it == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0); + auto it = c.insert(std::move(dupl)); + assert(*it == 0); + } + + assert(c.size() == 11); + + assert(c.count(0) == 2); + for (int i = 1; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::multiset m; + test(m); + std::multiset, min_allocator> m2; + test(m2); +} Index: test/std/containers/associative/multiset/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/associative/multiset/insert_node_type_hint.pass.cpp +++ test/std/containers/associative/multiset/insert_node_type_hint.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto it = c.insert(key); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(prev + 1 == c.size()); + assert(*it == i); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::multiset m; + test(m); + std::multiset, min_allocator> m2; + test(m2); +} Index: test/std/containers/associative/set/extract_iterator.pass.cpp =================================================================== --- test/std/containers/associative/set/extract_iterator.pass.cpp +++ test/std/containers/associative/set/extract_iterator.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = *first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.value() == key_value); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using set_type = std::set; + set_type m = {1, 2, 3, 4, 5, 6}; + test(m); + } + + { + std::set> m = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::set, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + test(m); + } +} Index: test/std/containers/associative/set/extract_key.pass.cpp =================================================================== --- test/std/containers/associative/set/extract_key.pass.cpp +++ test/std/containers/associative/set/extract_key.pass.cpp @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.value() == *copy); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::set m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::set> m = {1, 2, 3, 4, 5, 6}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::set, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/associative/set/insert_node_type.pass.cpp =================================================================== --- test/std/containers/associative/set/insert_node_type.pass.cpp +++ test/std/containers/associative/set/insert_node_type.pass.cpp @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// insert_return_type insert(node_type&&); + +#include +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto p = c.insert(key); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + typename Container::insert_return_type irt = c.insert(std::move(node)); + assert(node.empty()); + assert(irt.inserted); + assert(irt.node.empty()); + assert(*irt.position == i); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto irt = c.insert(std::move(def)); + assert(def.empty()); + assert(!irt.inserted); + assert(irt.node.empty()); + assert(irt.position == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0); + auto irt = c.insert(std::move(dupl)); + assert(dupl.empty()); + assert(!irt.inserted); + assert(!irt.node.empty()); + assert(irt.position == c.find(0)); + assert(irt.node.value() == 0); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::set m; + test(m); + std::set, min_allocator> m2; + test(m2); +} Index: test/std/containers/associative/set/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/associative/set/insert_node_type_hint.pass.cpp +++ test/std/containers/associative/set/insert_node_type_hint.pass.cpp @@ -0,0 +1,61 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto p = c.insert(key); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(node.empty()); + assert(prev + 1 == c.size()); + assert(*it == i); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::set m; + test(m); + std::set, min_allocator> m2; + test(m2); +} Index: test/std/containers/container.node/node_handle.pass.cpp =================================================================== --- test/std/containers/container.node/node_handle.pass.cpp +++ test/std/containers/container.node/node_handle.pass.cpp @@ -0,0 +1,145 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include +#include +#include +#include +#include "min_allocator.h" + +using namespace std; + +// [container.node.overview] Table 83. +template +struct node_compatibility_table +{ + static constexpr bool value = + is_same_v::node_type, typename map::node_type> && + is_same_v::node_type, typename multimap::node_type> && + is_same_v::node_type, typename set::node_type> && + is_same_v::node_type, typename multiset::node_type> && + is_same_v::node_type, typename unordered_map::node_type> && + is_same_v::node_type, typename unordered_multimap::node_type> && + is_same_v::node_type, typename unordered_set::node_type> && + is_same_v::node_type, typename unordered_multiset::node_type>; +}; + +template struct my_hash +{ + using argument_type = T; + using result_type = size_t; + my_hash() = default; + size_t operator()(const T&) const {return 0;} +}; + +template struct my_compare +{ + my_compare() = default; + bool operator()(const T&, const T&) const {return true;} +}; + +template struct my_equal +{ + my_equal() = default; + bool operator()(const T&, const T&) const {return true;} +}; + +struct Static +{ + Static() = default; + Static(const Static&) = delete; + Static(Static&&) = delete; + Static& operator=(const Static&) = delete; + Static& operator=(Static&&) = delete; +}; + +namespace std +{ +template <> struct hash +{ + using argument_type = Static; + using result_type = size_t; + hash() = default; + size_t operator()(const Static&) const; +}; +} + +static_assert(node_compatibility_table< + int, int, std::less, std::less, std::hash, + std::hash, std::equal_to, std::equal_to, + std::allocator, + std::allocator>>::value, + ""); + +static_assert( + node_compatibility_table, my_compare, + std::hash, my_hash, std::equal_to, + my_equal, allocator, + allocator>>::value, + ""); + +static_assert(node_compatibility_table< + Static, int, my_compare, std::less, + my_hash, std::hash, my_equal, + std::equal_to, min_allocator, + min_allocator>>::value, + ""); + +template +void test_node_handle_operations() +{ + Container c; + + typename Container::node_type nt1, nt2 = c.extract(c.emplace().first); + assert(nt2.get_allocator() == c.get_allocator()); + assert(!nt2.empty()); + assert(nt1.empty()); + std::swap(nt1, nt2); + assert(nt1.get_allocator() == c.get_allocator()); + assert(nt2.empty()); +} + +template +void test_node_handle_operations_multi() +{ + Container c; + + typename Container::node_type nt1, nt2 = c.extract(c.emplace()); + assert(nt2.get_allocator() == c.get_allocator()); + assert(!nt2.empty()); + assert(nt1.empty()); + std::swap(nt1, nt2); + assert(nt1.get_allocator() == c.get_allocator()); + assert(nt2.empty()); +} + +template +void test_insert_return_type() +{ + using irt_type = typename Container::insert_return_type; +} + +int main() +{ + test_node_handle_operations>(); + test_node_handle_operations_multi>(); + test_node_handle_operations>(); + test_node_handle_operations_multi>(); + test_node_handle_operations>(); + test_node_handle_operations_multi>(); + test_node_handle_operations>(); + test_node_handle_operations_multi>(); + + test_insert_return_type>(); + test_insert_return_type>(); + test_insert_return_type>(); + test_insert_return_type>(); +} Index: test/std/containers/unord/unord.map/unord.map.modifiers/extract_iterator.pass.cpp =================================================================== --- test/std/containers/unord/unord.map/unord.map.modifiers/extract_iterator.pass.cpp +++ test/std/containers/unord/unord.map/unord.map.modifiers/extract_iterator.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + auto some_key = c.cbegin()->first; + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = first->first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.key() == key_value); + t.key() = some_key; + assert(t.key() == some_key); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using map_type = std::unordered_map; + map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + test(m); + } + + { + std::unordered_map, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + assert(Counter_base::gConstructed == 12); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::unordered_map, std::equal_to, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + test(m); + } +} Index: test/std/containers/unord/unord.map/unord.map.modifiers/extract_key.pass.cpp =================================================================== --- test/std/containers/unord/unord.map/unord.map.modifiers/extract_key.pass.cpp +++ test/std/containers/unord/unord.map/unord.map.modifiers/extract_key.pass.cpp @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.key() == *copy); + t.key() = *first; // We should be able to mutate key. + assert(t.key() == *first); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::unordered_map m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::unordered_map, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 12+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::unordered_map, std::equal_to, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type.pass.cpp =================================================================== --- test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type.pass.cpp +++ test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type.pass.cpp @@ -0,0 +1,84 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// insert_return_type insert(node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto p = c.insert({key, mapped}); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + typename Container::insert_return_type irt = c.insert(std::move(node)); + assert(node.empty()); + assert(irt.inserted); + assert(irt.node.empty()); + assert(irt.position->first == i && irt.position->second == i + 1); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto irt = c.insert(std::move(def)); + assert(def.empty()); + assert(!irt.inserted); + assert(irt.node.empty()); + assert(irt.position == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0, 42); + auto irt = c.insert(std::move(dupl)); + assert(dupl.empty()); + assert(!irt.inserted); + assert(!irt.node.empty()); + assert(irt.position == c.find(0)); + assert(irt.node.key() == 0 && irt.node.mapped() == 42); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c[i] == i + 1); + } +} + +int main() +{ + std::unordered_map m; + test(m); + std::unordered_map, std::equal_to, min_allocator>> m2; + test(m2); +} Index: test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type_hint.pass.cpp +++ test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type_hint.pass.cpp @@ -0,0 +1,64 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto p = c.insert({key, mapped}); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(node.empty()); + assert(prev + 1 == c.size()); + assert(it->first == i); + assert(it->second == i + 1); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c[i] == i + 1); + } +} + +int main() +{ + std::unordered_map m; + test(m); + std::unordered_map, std::equal_to, min_allocator>> m2; + test(m2); +} Index: test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_iterator.pass.cpp =================================================================== --- test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_iterator.pass.cpp +++ test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_iterator.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + auto some_key = c.cbegin()->first; + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = first->first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.key() == key_value); + t.key() = some_key; + assert(t.key() == some_key); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using map_type = std::unordered_multimap; + map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + test(m); + } + + { + std::unordered_multimap, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + assert(Counter_base::gConstructed == 12); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::unordered_multimap, std::equal_to, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + test(m); + } +} Index: test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_key.pass.cpp =================================================================== --- test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_key.pass.cpp +++ test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_key.pass.cpp @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.key() == *copy); + t.key() = *first; // We should be able to mutate key. + assert(t.key() == *first); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::unordered_multimap m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::unordered_multimap, Counter> m = + {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 12+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_map = + std::unordered_multimap, std::equal_to, + min_allocator>>; + min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type.pass.cpp =================================================================== --- test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type.pass.cpp +++ test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type.pass.cpp @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto it = c.insert({key, mapped}); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + typename Container::iterator it = c.insert(std::move(node)); + assert(node.empty()); + assert(it == c.find(i) && it != c.end()); + assert(it->first == i && it->second == i + 1); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto it = c.insert(std::move(def)); + assert(def.empty()); + assert(it == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0, 42); + auto it = c.insert(std::move(dupl)); + assert(dupl.empty()); + assert(it != c.end() && it->second == 42); + } + + assert(c.size() == 11); + assert(c.count(0) == 2); + for (int i = 1; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c.find(i)->second == i + 1); + } +} + +int main() +{ + std::unordered_multimap m; + test(m); + std::unordered_multimap, std::equal_to, min_allocator>> m2; + test(m2); +} Index: test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type_hint.pass.cpp +++ test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type_hint.pass.cpp @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key, + typename Container::mapped_type const& mapped) +{ + static Container c; + auto it = c.insert({key, mapped}); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i, i + 1); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(node.empty()); + assert(prev + 1 == c.size()); + assert(it->first == i); + assert(it->second == i + 1); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + assert(c.find(i)->second == i + 1); + } +} + +int main() +{ + std::unordered_multimap m; + test(m); + std::unordered_multimap, std::equal_to, min_allocator>> m2; + test(m2); +} Index: test/std/containers/unord/unord.multiset/extract_iterator.pass.cpp =================================================================== --- test/std/containers/unord/unord.multiset/extract_iterator.pass.cpp +++ test/std/containers/unord/unord.multiset/extract_iterator.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = *first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.value() == key_value); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using set_type = std::unordered_multiset; + set_type m = {1, 2, 3, 4, 5, 6}; + test(m); + } + + { + std::unordered_multiset> m = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::unordered_multiset, std::equal_to, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + test(m); + } +} Index: test/std/containers/unord/unord.multiset/extract_key.pass.cpp =================================================================== --- test/std/containers/unord/unord.multiset/extract_key.pass.cpp +++ test/std/containers/unord/unord.multiset/extract_key.pass.cpp @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.value() == *copy); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::unordered_multiset m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::unordered_multiset> m = {1, 2, 3, 4, 5, 6}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::unordered_multiset, std::equal_to, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/unord/unord.multiset/insert_node_type.pass.cpp =================================================================== --- test/std/containers/unord/unord.multiset/insert_node_type.pass.cpp +++ test/std/containers/unord/unord.multiset/insert_node_type.pass.cpp @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(node_type&&); + +#include +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto it = c.insert(key); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + typename Container::iterator it = c.insert(std::move(node)); + assert(node.empty()); + assert(it == c.find(i) && it != c.end()); + assert(*it == i); + assert(node.empty()); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto it = c.insert(std::move(def)); + assert(def.empty()); + assert(it == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0); + auto it = c.insert(std::move(dupl)); + assert(*it == 0); + } + + assert(c.size() == 11); + assert(c.count(0) == 2); + for (int i = 1; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::unordered_multiset m; + test(m); + std::unordered_multiset, std::equal_to, min_allocator> m2; + test(m2); +} Index: test/std/containers/unord/unord.multiset/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/unord/unord.multiset/insert_node_type_hint.pass.cpp +++ test/std/containers/unord/unord.multiset/insert_node_type_hint.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto it = c.insert(key); + return c.extract(it); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(prev + 1 == c.size()); + assert(*it == i); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::unordered_multiset m; + test(m); + std::unordered_multiset, std::equal_to, min_allocator> m2; + test(m2); +} Index: test/std/containers/unord/unord.set/extract_iterator.pass.cpp =================================================================== --- test/std/containers/unord/unord.set/extract_iterator.pass.cpp +++ test/std/containers/unord/unord.set/extract_iterator.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(const_iterator); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c) +{ + size_t sz = c.size(); + + for (auto first = c.cbegin(); first != c.cend();) + { + auto key_value = *first; + typename Container::node_type t = c.extract(first++); + --sz; + assert(t.value() == key_value); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); +} + +int main() +{ + { + using set_type = std::unordered_set; + set_type m = {1, 2, 3, 4, 5, 6}; + test(m); + } + + { + std::unordered_set> m = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6); + test(m); + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::unordered_set, std::equal_to, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + test(m); + } +} Index: test/std/containers/unord/unord.set/extract_key.pass.cpp =================================================================== --- test/std/containers/unord/unord.set/extract_key.pass.cpp +++ test/std/containers/unord/unord.set/extract_key.pass.cpp @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// node_type extract(key_type const&); + +#include +#include "min_allocator.h" +#include "Counter.h" + +template +void test(Container& c, KeyTypeIter first, KeyTypeIter last) +{ + size_t sz = c.size(); + assert((size_t)std::distance(first, last) == sz); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(!t.empty()); + --sz; + assert(t.value() == *copy); + assert(t.get_allocator() == c.get_allocator()); + assert(sz == c.size()); + } + + assert(c.size() == 0); + + for (KeyTypeIter copy = first; copy != last; ++copy) + { + typename Container::node_type t = c.extract(*copy); + assert(t.empty()); + } +} + +int main() +{ + { + std::unordered_set m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } + + { + std::unordered_set> m = {1, 2, 3, 4, 5, 6}; + { + Counter keys[] = {1, 2, 3, 4, 5, 6}; + assert(Counter_base::gConstructed == 6+6); + test(m, std::begin(keys), std::end(keys)); + } + assert(Counter_base::gConstructed == 0); + } + + { + using min_alloc_set = std::unordered_set, std::equal_to, min_allocator>; + min_alloc_set m = {1, 2, 3, 4, 5, 6}; + int keys[] = {1, 2, 3, 4, 5, 6}; + test(m, std::begin(keys), std::end(keys)); + } +} Index: test/std/containers/unord/unord.set/insert_node_type.pass.cpp =================================================================== --- test/std/containers/unord/unord.set/insert_node_type.pass.cpp +++ test/std/containers/unord/unord.set/insert_node_type.pass.cpp @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// insert_return_type insert(node_type&&); + +#include +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto p = c.insert(key); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + typename Container::insert_return_type irt = c.insert(std::move(node)); + assert(node.empty()); + assert(irt.inserted); + assert(irt.node.empty()); + assert(*irt.position == i); + } + + assert(c.size() == 10); + + { // Insert empty node. + typename Container::node_type def; + auto irt = c.insert(std::move(def)); + assert(def.empty()); + assert(!irt.inserted); + assert(irt.node.empty()); + assert(irt.position == c.end()); + } + + { // Insert duplicate node. + typename Container::node_type dupl = nf(0); + auto irt = c.insert(std::move(dupl)); + assert(dupl.empty()); + assert(!irt.inserted); + assert(!irt.node.empty()); + assert(irt.position == c.find(0)); + assert(irt.node.value() == 0); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::unordered_set m; + test(m); + std::unordered_set, std::equal_to, min_allocator> m2; + test(m2); +} Index: test/std/containers/unord/unord.set/insert_node_type_hint.pass.cpp =================================================================== --- test/std/containers/unord/unord.set/insert_node_type_hint.pass.cpp +++ test/std/containers/unord/unord.set/insert_node_type_hint.pass.cpp @@ -0,0 +1,61 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// iterator insert(const_iterator hint, node_type&&); + +#include +#include "min_allocator.h" + +template +typename Container::node_type +node_factory(typename Container::key_type const& key) +{ + static Container c; + auto p = c.insert(key); + assert(p.second); + return c.extract(p.first); +} + +template +void test(Container& c) +{ + auto* nf = &node_factory; + + for (int i = 0; i != 10; ++i) + { + typename Container::node_type node = nf(i); + assert(!node.empty()); + size_t prev = c.size(); + auto it = c.insert(c.end(), std::move(node)); + assert(node.empty()); + assert(prev + 1 == c.size()); + assert(*it == i); + } + + assert(c.size() == 10); + + for (int i = 0; i != 10; ++i) + { + assert(c.count(i) == 1); + } +} + +int main() +{ + std::unordered_set m; + test(m); + std::unordered_set, std::equal_to, min_allocator> m2; + test(m2); +} Index: test/support/Counter.h =================================================================== --- test/support/Counter.h +++ test/support/Counter.h @@ -23,7 +23,7 @@ Counter() : data_() { ++gConstructed; } Counter(const T &data) : data_(data) { ++gConstructed; } Counter(const Counter& rhs) : data_(rhs.data_) { ++gConstructed; } - Counter& operator=(const Counter& rhs) { ++gConstructed; data_ = rhs.data_; return *this; } + Counter& operator=(const Counter& rhs) { data_ = rhs.data_; return *this; } #if TEST_STD_VER >= 11 Counter(Counter&& rhs) : data_(std::move(rhs.data_)) { ++gConstructed; } Counter& operator=(Counter&& rhs) { ++gConstructed; data_ = std::move(rhs.data_); return *this; } @@ -49,7 +49,7 @@ typedef Counter argument_type; typedef std::size_t result_type; - std::size_t operator()(const Counter& x) const {return std::hash(x.get());} + std::size_t operator()(const Counter& x) const {return std::hash()(x.get());} }; }