diff options
Diffstat (limited to 'lib/libcxx/include/unordered_map')
| -rw-r--r-- | lib/libcxx/include/unordered_map | 199 |
1 files changed, 167 insertions, 32 deletions
diff --git a/lib/libcxx/include/unordered_map b/lib/libcxx/include/unordered_map index 725cb6af275..348f57923b5 100644 --- a/lib/libcxx/include/unordered_map +++ b/lib/libcxx/include/unordered_map @@ -44,6 +44,9 @@ public: typedef /unspecified/ local_iterator; typedef /unspecified/ const_local_iterator; + typedef unspecified node_type; // C++17 + typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 + unordered_map() noexcept( is_nothrow_default_constructible<hasher>::value && @@ -122,6 +125,11 @@ public: void insert(InputIterator first, InputIterator last); void insert(initializer_list<value_type>); + 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 <class... Args> pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 template <class... Args> @@ -226,6 +234,8 @@ public: typedef /unspecified/ local_iterator; typedef /unspecified/ const_local_iterator; + typedef unspecified node_type; // C++17 + unordered_multimap() noexcept( is_nothrow_default_constructible<hasher>::value && @@ -304,6 +314,11 @@ public: void insert(InputIterator first, InputIterator last); void insert(initializer_list<value_type>); + 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 @@ template <class Key, class T, class Hash, class Pred, class Alloc> #include <__config> #include <__hash_table> +#include <__node_handle> #include <functional> #include <stdexcept> #include <tuple> @@ -396,7 +412,7 @@ public: const _Hash& hash_function() const _NOEXCEPT {return *this;} _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Cp& __x) const - {return static_cast<const _Hash&>(*this)(__x.__cc.first);} + {return static_cast<const _Hash&>(*this)(__x.__get_value().first);} _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Key& __x) const {return static_cast<const _Hash&>(*this)(__x);} @@ -425,7 +441,7 @@ public: const _Hash& hash_function() const _NOEXCEPT {return __hash_;} _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Cp& __x) const - {return __hash_(__x.__cc.first);} + {return __hash_(__x.__get_value().first);} _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Key& __x) const {return __hash_(__x);} @@ -464,13 +480,13 @@ public: const _Pred& key_eq() const _NOEXCEPT {return *this;} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Cp& __y) const - {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} + {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Key& __y) const - {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} + {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Key& __x, const _Cp& __y) const - {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} + {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);} void swap(__unordered_map_equal&__y) _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) { @@ -496,13 +512,13 @@ public: const _Pred& key_eq() const _NOEXCEPT {return __pred_;} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Cp& __y) const - {return __pred_(__x.__cc.first, __y.__cc.first);} + {return __pred_(__x.__get_value().first, __y.__get_value().first);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Key& __y) const - {return __pred_(__x.__cc.first, __y);} + {return __pred_(__x.__get_value().first, __y);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Key& __x, const _Cp& __y) const - {return __pred_(__x, __y.__cc.first);} + {return __pred_(__x, __y.__get_value().first);} void swap(__unordered_map_equal&__y) _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) { @@ -572,9 +588,9 @@ public: void operator()(pointer __p) _NOEXCEPT { if (__second_constructed) - __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); + __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second)); if (__first_constructed) - __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); + __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first)); if (__p) __alloc_traits::deallocate(__na_, __p, 1); } @@ -582,23 +598,67 @@ public: #ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp> -union __hash_value_type +struct __hash_value_type { typedef _Key key_type; typedef _Tp mapped_type; typedef pair<const key_type, mapped_type> value_type; - typedef pair<key_type, mapped_type> __nc_value_type; + typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; + typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; +private: value_type __cc; - __nc_value_type __nc; + +public: + _LIBCPP_INLINE_VISIBILITY + value_type& __get_value() + { +#if _LIBCPP_STD_VER > 14 + return *_VSTD::launder(_VSTD::addressof(__cc)); +#else + return __cc; +#endif + } + + _LIBCPP_INLINE_VISIBILITY + const value_type& __get_value() const + { +#if _LIBCPP_STD_VER > 14 + return *_VSTD::launder(_VSTD::addressof(__cc)); +#else + return __cc; +#endif + } + + _LIBCPP_INLINE_VISIBILITY + __nc_ref_pair_type __ref() + { + value_type& __v = __get_value(); + return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); + } + + _LIBCPP_INLINE_VISIBILITY + __nc_rref_pair_type __move() + { + value_type& __v = __get_value(); + return __nc_rref_pair_type( + _VSTD::move(const_cast<key_type&>(__v.first)), + _VSTD::move(__v.second)); + } _LIBCPP_INLINE_VISIBILITY __hash_value_type& operator=(const __hash_value_type& __v) - {__nc = __v.__cc; return *this;} + { + __ref() = __v.__get_value(); + return *this; + } _LIBCPP_INLINE_VISIBILITY __hash_value_type& operator=(__hash_value_type&& __v) - {__nc = _VSTD::move(__v.__nc); return *this;} + { + __ref() = __v.__move(); + return *this; + } template <class _ValueTp, class = typename enable_if< @@ -606,8 +666,10 @@ union __hash_value_type >::type > _LIBCPP_INLINE_VISIBILITY - __hash_value_type& operator=(_ValueTp&& __v) { - __nc = _VSTD::forward<_ValueTp>(__v); return *this; + __hash_value_type& operator=(_ValueTp&& __v) + { + __ref() = _VSTD::forward<_ValueTp>(__v); + return *this; } private: @@ -628,8 +690,15 @@ struct __hash_value_type typedef _Tp mapped_type; typedef pair<const key_type, mapped_type> value_type; +private: value_type __cc; +public: + _LIBCPP_INLINE_VISIBILITY + value_type& __get_value() { return __cc; } + _LIBCPP_INLINE_VISIBILITY + const value_type& __get_value() const { return __cc; } + private: ~__hash_value_type(); }; @@ -657,9 +726,9 @@ public: __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __i_->__cc;} + reference operator*() const {return __i_->__get_value();} _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} + pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;} @@ -711,9 +780,9 @@ public: : __i_(__i.__i_) {} _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __i_->__cc;} + reference operator*() const {return __i_->__get_value();} _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} + pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator& operator++() {++__i_; return *this;} @@ -750,7 +819,6 @@ public: typedef _Pred key_equal; typedef _Alloc allocator_type; typedef pair<const key_type, mapped_type> value_type; - typedef pair<key_type, mapped_type> __nc_value_type; typedef value_type& reference; typedef const value_type& const_reference; static_assert((is_same<value_type, typename allocator_type::value_type>::value), @@ -791,6 +859,11 @@ public: typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle<__node, allocator_type> node_type; + typedef __insert_return_type<iterator, node_type> insert_return_type; +#endif + _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1084,7 +1157,37 @@ public: 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<node_type>( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract<node_type>(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract<node_type>( + __it.__i_); + } +#endif _LIBCPP_INLINE_VISIBILITY void swap(unordered_map& __u) @@ -1298,8 +1401,8 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( { iterator __i = __u.begin(); while (__u.size() != 0) { - __table_.__emplace_unique(_VSTD::move( - __u.__table_.remove((__i++).__i_)->__value_.__nc)); + __table_.__emplace_unique( + __u.__table_.remove((__i++).__i_)->__value_.__move()); } } #if _LIBCPP_DEBUG_LEVEL >= 2 @@ -1385,7 +1488,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { return __table_.__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), - std::forward_as_tuple()).first->__cc.second; + std::forward_as_tuple()).first->__get_value().second; } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1394,7 +1497,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) { return __table_.__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), - std::forward_as_tuple()).first->__cc.second; + std::forward_as_tuple()).first->__get_value().second; } #else // _LIBCPP_CXX03_LANG @@ -1404,9 +1507,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const { __node_allocator& __na = __table_.__node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); + __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k); __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); + __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second)); __h.get_deleter().__second_constructed = true; return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 } @@ -1500,7 +1603,6 @@ public: typedef _Pred key_equal; typedef _Alloc allocator_type; typedef pair<const key_type, mapped_type> value_type; - typedef pair<key_type, mapped_type> __nc_value_type; typedef value_type& reference; typedef const value_type& const_reference; static_assert((is_same<value_type, typename allocator_type::value_type>::value), @@ -1539,6 +1641,10 @@ public: typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; +#if _LIBCPP_STD_VER > 14 + typedef __map_node_handle<__node, allocator_type> node_type; +#endif + _LIBCPP_INLINE_VISIBILITY unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) @@ -1712,6 +1818,36 @@ public: _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<node_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_multimap::insert()"); + return __table_.template __node_handle_insert_multi<node_type>( + __hint.__i_, _VSTD::move(__nh)); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(key_type const& __key) + { + return __table_.template __node_handle_extract<node_type>(__key); + } + _LIBCPP_INLINE_VISIBILITY + node_type extract(const_iterator __it) + { + return __table_.template __node_handle_extract<node_type>( + __it.__i_); + } +#endif + _LIBCPP_INLINE_VISIBILITY void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) @@ -1915,8 +2051,7 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( while (__u.size() != 0) { __table_.__insert_multi( - _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc) - ); + __u.__table_.remove((__i++).__i_)->__value_.__move()); } } #if _LIBCPP_DEBUG_LEVEL >= 2 |