diff options
Diffstat (limited to 'include/unordered_map')
| -rw-r--r-- | include/unordered_map | 592 |
1 files changed, 212 insertions, 380 deletions
diff --git a/include/unordered_map b/include/unordered_map index 85a54a7b6ddba..bf64ad66f39a6 100644 --- a/include/unordered_map +++ b/include/unordered_map @@ -369,6 +369,7 @@ template <class Key, class T, class Hash, class Pred, class Alloc> #include <__hash_table> #include <functional> #include <stdexcept> +#include <tuple> #include <__debug> @@ -413,7 +414,6 @@ template <class _Key, class _Cp, class _Hash> class __unordered_map_hasher<_Key, _Cp, _Hash, false> { _Hash __hash_; - public: _LIBCPP_INLINE_VISIBILITY __unordered_map_hasher() @@ -487,7 +487,6 @@ template <class _Key, class _Cp, class _Pred> class __unordered_map_equal<_Key, _Cp, _Pred, false> { _Pred __pred_; - public: _LIBCPP_INLINE_VISIBILITY __unordered_map_equal() @@ -531,12 +530,11 @@ class __hash_map_node_destructor { typedef _Alloc allocator_type; typedef allocator_traits<allocator_type> __alloc_traits; - typedef typename __alloc_traits::value_type::value_type value_type; + public: - typedef typename __alloc_traits::pointer pointer; + + typedef typename __alloc_traits::pointer pointer; private: - typedef typename value_type::value_type::first_type first_type; - typedef typename value_type::value_type::second_type second_type; allocator_type& __na_; @@ -586,8 +584,7 @@ public: } }; -#if __cplusplus >= 201103L - +#ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp> union __hash_value_type { @@ -599,19 +596,6 @@ union __hash_value_type value_type __cc; __nc_value_type __nc; - template <class ..._Args> - _LIBCPP_INLINE_VISIBILITY - __hash_value_type(_Args&& ...__args) - : __cc(std::forward<_Args>(__args)...) {} - - _LIBCPP_INLINE_VISIBILITY - __hash_value_type(const __hash_value_type& __v) - : __cc(__v.__cc) {} - - _LIBCPP_INLINE_VISIBILITY - __hash_value_type(__hash_value_type&& __v) - : __nc(_VSTD::move(__v.__nc)) {} - _LIBCPP_INLINE_VISIBILITY __hash_value_type& operator=(const __hash_value_type& __v) {__nc = __v.__cc; return *this;} @@ -620,8 +604,23 @@ union __hash_value_type __hash_value_type& operator=(__hash_value_type&& __v) {__nc = _VSTD::move(__v.__nc); return *this;} + template <class _ValueTp, + class = typename enable_if< + __is_same_uncvref<_ValueTp, value_type>::value + >::type + > _LIBCPP_INLINE_VISIBILITY - ~__hash_value_type() {__cc.~value_type();} + __hash_value_type& operator=(_ValueTp&& __v) { + __nc = _VSTD::forward<_ValueTp>(__v); return *this; + } + +private: + __hash_value_type(const __hash_value_type& __v) = delete; + __hash_value_type(__hash_value_type&& __v) = delete; + template <class ..._Args> + explicit __hash_value_type(_Args&& ...__args) = delete; + + ~__hash_value_type() = delete; }; #else @@ -635,18 +634,8 @@ struct __hash_value_type value_type __cc; - _LIBCPP_INLINE_VISIBILITY - __hash_value_type() {} - - template <class _A0> - _LIBCPP_INLINE_VISIBILITY - __hash_value_type(const _A0& __a0) - : __cc(__a0) {} - - template <class _A0, class _A1> - _LIBCPP_INLINE_VISIBILITY - __hash_value_type(const _A0& __a0, const _A1& __a1) - : __cc(__a0, __a1) {} +private: + ~__hash_value_type(); }; #endif @@ -656,15 +645,14 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator { _HashIterator __i_; - typedef const typename _HashIterator::value_type::value_type::first_type key_type; - typedef typename _HashIterator::value_type::value_type::second_type mapped_type; + typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; + public: typedef forward_iterator_tag iterator_category; - typedef pair<key_type, mapped_type> value_type; - typedef typename _HashIterator::difference_type difference_type; + typedef typename _NodeTypes::__map_value_type value_type; + typedef typename _NodeTypes::difference_type difference_type; typedef value_type& reference; - typedef typename __rebind_pointer<typename _HashIterator::pointer, value_type>::type - pointer; + typedef typename _NodeTypes::__map_value_type_pointer pointer; _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() _NOEXCEPT {} @@ -706,15 +694,14 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator { _HashIterator __i_; - typedef const typename _HashIterator::value_type::value_type::first_type key_type; - typedef typename _HashIterator::value_type::value_type::second_type mapped_type; + typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; + public: typedef forward_iterator_tag iterator_category; - typedef pair<key_type, mapped_type> value_type; - typedef typename _HashIterator::difference_type difference_type; + typedef typename _NodeTypes::__map_value_type value_type; + typedef typename _NodeTypes::difference_type difference_type; typedef const value_type& reference; - typedef typename __rebind_pointer<typename _HashIterator::pointer, const value_type>::type - pointer; + typedef typename _NodeTypes::__const_map_value_type_pointer pointer; _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() _NOEXCEPT {} @@ -785,6 +772,7 @@ private: __table __table_; + typedef typename __table::_NodeTypes _NodeTypes; typedef typename __table::__node_pointer __node_pointer; typedef typename __table::__node_const_pointer __node_const_pointer; typedef typename __table::__node_traits __node_traits; @@ -793,11 +781,14 @@ private: typedef __hash_map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; typedef allocator_traits<allocator_type> __alloc_traits; + + static_assert((is_same<typename __table::__container_value_type, value_type>::value), ""); + static_assert((is_same<typename __table::__node_value_type, __value_type>::value), ""); public: typedef typename __alloc_traits::pointer pointer; typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; + typedef typename __table::size_type size_type; + typedef typename __table::difference_type difference_type; typedef __hash_map_iterator<typename __table::iterator> iterator; typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; @@ -828,10 +819,12 @@ public: size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + _LIBCPP_INLINE_VISIBILITY explicit unordered_map(const allocator_type& __a); unordered_map(const unordered_map& __u); unordered_map(const unordered_map& __u, const allocator_type& __a); #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); unordered_map(unordered_map&& __u, const allocator_type& __a); @@ -872,7 +865,7 @@ public: _LIBCPP_INLINE_VISIBILITY unordered_map& operator=(const unordered_map& __u) { -#if __cplusplus >= 201103L +#ifndef _LIBCPP_CXX03_LANG __table_ = __u.__table_; #else if (this != &__u) { @@ -887,10 +880,12 @@ public: return *this; } #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY unordered_map& operator=(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); #endif #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS + _LIBCPP_INLINE_VISIBILITY unordered_map& operator=(initializer_list<value_type> __il); #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -918,189 +913,162 @@ public: _LIBCPP_INLINE_VISIBILITY const_iterator cend() const _NOEXCEPT {return __table_.end();} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS + _LIBCPP_INLINE_VISIBILITY + pair<iterator, bool> insert(const value_type& __x) + {return __table_.__insert_unique(__x);} - template <class... _Args> - pair<iterator, bool> emplace(_Args&&... __args); + iterator insert(const_iterator __p, const value_type& __x) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" + " referring to this unordered_map"); +#endif + return insert(__x).first; + } - template <class... _Args> + template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY + void insert(_InputIterator __first, _InputIterator __last); + +#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS + _LIBCPP_INLINE_VISIBILITY + void insert(initializer_list<value_type> __il) + {insert(__il.begin(), __il.end());} +#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS + +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY + pair<iterator, bool> insert(value_type&& __x) + {return __table_.__insert_unique(_VSTD::move(__x));} + + iterator insert(const_iterator __p, value_type&& __x) { #if _LIBCPP_DEBUG_LEVEL >= 2 - iterator emplace_hint(const_iterator __p, _Args&&... __args) - { - _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, - "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" - " referring to this unordered_map"); - return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; - } -#else - iterator emplace_hint(const_iterator, _Args&&... __args) - {return emplace(_VSTD::forward<_Args>(__args)...).first;} + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" + " referring to this unordered_map"); #endif -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - _LIBCPP_INLINE_VISIBILITY - pair<iterator, bool> insert(const value_type& __x) - {return __table_.__insert_unique(__x);} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + return __table_.__insert_unique(_VSTD::move(__x)).first; + } + template <class _Pp, class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> insert(_Pp&& __x) {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - _LIBCPP_INLINE_VISIBILITY -#if _LIBCPP_DEBUG_LEVEL >= 2 - iterator insert(const_iterator __p, const value_type& __x) - { - _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, - "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" - " referring to this unordered_map"); - return insert(__x).first; - } -#else - iterator insert(const_iterator, const value_type& __x) - {return insert(__x).first;} -#endif -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + template <class _Pp, class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> _LIBCPP_INLINE_VISIBILITY -#if _LIBCPP_DEBUG_LEVEL >= 2 iterator insert(const_iterator __p, _Pp&& __x) { +#if _LIBCPP_DEBUG_LEVEL >= 2 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" " referring to this unordered_map"); +#endif return insert(_VSTD::forward<_Pp>(__x)).first; } -#else - iterator insert(const_iterator, _Pp&& __x) - {return insert(_VSTD::forward<_Pp>(__x)).first;} -#endif -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - template <class _InputIterator> - void insert(_InputIterator __first, _InputIterator __last); -#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS + + template <class... _Args> _LIBCPP_INLINE_VISIBILITY - void insert(initializer_list<value_type> __il) - {insert(__il.begin(), __il.end());} -#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS + pair<iterator, bool> emplace(_Args&&... __args) { + return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...); + } + + template <class... _Args> + _LIBCPP_INLINE_VISIBILITY + iterator emplace_hint(const_iterator __p, _Args&&... __args) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" + " referring to this unordered_map"); +#endif + return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; + } + +#endif // _LIBCPP_CXX03_LANG #if _LIBCPP_STD_VER > 14 -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS template <class... _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) { - iterator __p = __table_.find(__k); - if ( __p != end()) - return _VSTD::make_pair(__p, false); - else - return _VSTD::make_pair( - emplace_hint(__p, - _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), - _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), - true); + return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct, + _VSTD::forward_as_tuple(__k), + _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); } template <class... _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) { - iterator __p = __table_.find(__k); - if ( __p != end()) - return _VSTD::make_pair(__p, false); - else - return _VSTD::make_pair( - emplace_hint(__p, - _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), - _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)), - true); + return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct, + _VSTD::forward_as_tuple(_VSTD::move(__k)), + _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); } template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) { - iterator __p = __table_.find(__k); - if ( __p != end()) - return __p; - else - return emplace_hint(__h, - _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), - _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" + " referring to this unordered_map"); +#endif + return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first; } template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) { - iterator __p = __table_.find(__k); - if ( __p != end()) - return __p; - else - return emplace_hint(__h, - _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), - _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); +#if _LIBCPP_DEBUG_LEVEL >= 2 + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" + " referring to this unordered_map"); +#endif + return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first; } template <class _Vp> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) { - iterator __p = __table_.find(__k); - if ( __p != end()) - { - __p->second = _VSTD::move(__v); - return _VSTD::make_pair(__p, false); + pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, + __k, _VSTD::forward<_Vp>(__v)); + if (!__res.second) { + __res.first->second = _VSTD::forward<_Vp>(__v); } - return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); + return __res; } - + template <class _Vp> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) { - iterator __p = __table_.find(__k); - if ( __p != end()) - { - __p->second = _VSTD::move(__v); - return _VSTD::make_pair(__p, false); + pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, + _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); + if (!__res.second) { + __res.first->second = _VSTD::forward<_Vp>(__v); } - return _VSTD::make_pair(emplace_hint(__p, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)), true); + return __res; } template <class _Vp> _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) { - iterator __p = __table_.find(__k); - if ( __p != end()) - { - __p->second = _VSTD::move(__v); - return __p; - } - return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v)); + return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first; } template <class _Vp> _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) { - iterator __p = __table_.find(__k); - if ( __p != end()) - { - __p->second = _VSTD::move(__v); - return __p; - } - return emplace_hint(__h, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)); + return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first; } #endif -#endif -#endif _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} @@ -1140,7 +1108,7 @@ public: {return __table_.__equal_range_unique(__k);} mapped_type& operator[](const key_type& __k); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +#ifndef _LIBCPP_CXX03_LANG mapped_type& operator[](key_type&& __k); #endif @@ -1196,18 +1164,10 @@ public: #endif // _LIBCPP_DEBUG_LEVEL >= 2 private: -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(); - template <class _A0> - __node_holder - __construct_node(_A0&& __a0); - __node_holder __construct_node_with_key(key_type&& __k); -#ifndef _LIBCPP_HAS_NO_VARIADICS - template <class _A0, class _A1, class ..._Args> - __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + +#ifdef _LIBCPP_CXX03_LANG __node_holder __construct_node_with_key(const key_type& __k); +#endif }; template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1234,7 +1194,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const allocator_type& __a) : __table_(__a) @@ -1310,7 +1270,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) @@ -1333,10 +1293,10 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( if (__a != __u.get_allocator()) { iterator __i = __u.begin(); - while (__u.size() != 0) - __table_.__insert_unique( - _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) - ); + while (__u.size() != 0) { + __table_.__emplace_unique(_VSTD::move( + __u.__table_.remove((__i++).__i_)->__value_.__nc)); + } } #if _LIBCPP_DEBUG_LEVEL >= 2 else @@ -1389,7 +1349,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) @@ -1403,7 +1363,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( initializer_list<value_type> __il) @@ -1414,81 +1374,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class _A0> -typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) -{ - __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), _VSTD::move(__k)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - -#ifndef _LIBCPP_HAS_NO_VARIADICS - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class _A0, class _A1, class ..._Args> -typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, - _A1&& __a1, - _Args&&... __args) -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), - _VSTD::forward<_Args>(__args)...); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class... _Args> -pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> -unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); - if (__r.second) - __h.release(); - return __r; -} - -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - +#ifdef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) @@ -1501,10 +1387,11 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const __h.get_deleter().__second_constructed = true; return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 } +#endif template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> -inline _LIBCPP_INLINE_VISIBILITY +inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) @@ -1513,6 +1400,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, __table_.__insert_unique(*__first); } +#ifdef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) @@ -1525,23 +1413,27 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) __h.release(); return __r.first->second; } +#else -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> +_Tp& +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; +} template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) { - iterator __i = find(__k); - if (__i != end()) - return __i->second; - __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); - pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); - __h.release(); - return __r.first->second; + return __table_.__emplace_unique_key_args(__k, + std::piecewise_construct, std::forward_as_tuple(std::move(__k)), + std::forward_as_tuple()).first->__cc.second; } -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // !_LIBCPP_CXX03_MODE template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> _Tp& @@ -1635,17 +1527,21 @@ private: __table __table_; + typedef typename __table::_NodeTypes _NodeTypes; typedef typename __table::__node_traits __node_traits; typedef typename __table::__node_allocator __node_allocator; typedef typename __table::__node __node; typedef __hash_map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; typedef allocator_traits<allocator_type> __alloc_traits; + static_assert((is_same<typename __node_traits::size_type, + typename __alloc_traits::size_type>::value), + "Allocator uses different size_type for different types"); public: typedef typename __alloc_traits::pointer pointer; typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; + typedef typename __table::size_type size_type; + typedef typename __table::difference_type difference_type; typedef __hash_map_iterator<typename __table::iterator> iterator; typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; @@ -1676,10 +1572,12 @@ public: size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + _LIBCPP_INLINE_VISIBILITY explicit unordered_multimap(const allocator_type& __a); unordered_multimap(const unordered_multimap& __u); unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY unordered_multimap(unordered_multimap&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); @@ -1721,7 +1619,7 @@ public: _LIBCPP_INLINE_VISIBILITY unordered_multimap& operator=(const unordered_multimap& __u) { -#if __cplusplus >= 201103L +#ifndef _LIBCPP_CXX03_LANG __table_ = __u.__table_; #else if (this != &__u) { @@ -1736,10 +1634,12 @@ public: return *this; } #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY unordered_multimap& operator=(unordered_multimap&& __u) _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); #endif #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS + _LIBCPP_INLINE_VISIBILITY unordered_multimap& operator=(initializer_list<value_type> __il); #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -1767,43 +1667,55 @@ public: _LIBCPP_INLINE_VISIBILITY const_iterator cend() const _NOEXCEPT {return __table_.end();} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS - - template <class... _Args> - iterator emplace(_Args&&... __args); - - template <class... _Args> - iterator emplace_hint(const_iterator __p, _Args&&... __args); -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES _LIBCPP_INLINE_VISIBILITY iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - template <class _Pp, - class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> - _LIBCPP_INLINE_VISIBILITY - iterator insert(_Pp&& __x) - {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __p, const value_type& __x) {return __table_.__insert_multi(__p.__i_, __x);} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - template <class _Pp, - class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> - _LIBCPP_INLINE_VISIBILITY - iterator insert(const_iterator __p, _Pp&& __x) - {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + template <class _InputIterator> - void insert(_InputIterator __first, _InputIterator __last); + _LIBCPP_INLINE_VISIBILITY + void insert(_InputIterator __first, _InputIterator __last); + #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS _LIBCPP_INLINE_VISIBILITY void insert(initializer_list<value_type> __il) {insert(__il.begin(), __il.end());} #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY + iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} + + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __p, value_type&& __x) + {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));} + + template <class _Pp, + class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> + _LIBCPP_INLINE_VISIBILITY + iterator insert(_Pp&& __x) + {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} + + template <class _Pp, + class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __p, _Pp&& __x) + {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} + + template <class... _Args> + iterator emplace(_Args&&... __args) { + return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...); + } + + template <class... _Args> + iterator emplace_hint(const_iterator __p, _Args&&... __args) { + return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); + } +#endif // _LIBCPP_CXX03_LANG + + _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} _LIBCPP_INLINE_VISIBILITY @@ -1890,17 +1802,7 @@ public: #endif // _LIBCPP_DEBUG_LEVEL >= 2 -private: -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(); - template <class _A0> - __node_holder - __construct_node(_A0&& __a0); -#ifndef _LIBCPP_HAS_NO_VARIADICS - template <class _A0, class _A1, class ..._Args> - __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + }; template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1966,7 +1868,7 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const allocator_type& __a) : __table_(__a) @@ -2003,7 +1905,7 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( unordered_multimap&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) @@ -2029,7 +1931,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_) + _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc) ); } } @@ -2084,7 +1986,7 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) @@ -2098,7 +2000,7 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multima #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY +inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( initializer_list<value_type> __il) @@ -2109,81 +2011,11 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class _A0> -typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0)); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -#ifndef _LIBCPP_HAS_NO_VARIADICS - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class _A0, class _A1, class ..._Args> -typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( - _A0&& __a0, _A1&& __a1, _Args&&... __args) -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_), - _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), - _VSTD::forward<_Args>(__args)...); - __h.get_deleter().__first_constructed = true; - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class... _Args> -typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator -unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __table_.__node_insert_multi(__h.get()); - __h.release(); - return __r; -} - -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class... _Args> -typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator -unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( - const_iterator __p, _Args&&... __args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); - __h.release(); - return __r; -} -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> -inline _LIBCPP_INLINE_VISIBILITY +inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) |