diff options
Diffstat (limited to 'include/map')
| -rw-r--r-- | include/map | 514 |
1 files changed, 134 insertions, 380 deletions
diff --git a/include/map b/include/map index 87add437a545..b8aa7a6d7a5d 100644 --- a/include/map +++ b/include/map @@ -162,7 +162,7 @@ public: void swap(map& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && - __is_nothrow_swappable<key_compare>::value); // C++17 + is_nothrow_swappable<key_compare>::value); // C++17 // observers: allocator_type get_allocator() const noexcept; @@ -357,7 +357,7 @@ public: void swap(multimap& m) noexcept(allocator_traits<allocator_type>::is_always_equal::value && - __is_nothrow_swappable<key_compare>::value); // C++17 + is_nothrow_swappable<key_compare>::value); // C++17 // observers: allocator_type get_allocator() const noexcept; @@ -564,13 +564,11 @@ class __map_node_destructor { typedef _Allocator 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; -private: - typedef typename value_type::value_type::first_type first_type; - typedef typename value_type::value_type::second_type second_type; +private: allocator_type& __na_; __map_node_destructor& operator=(const __map_node_destructor&); @@ -615,7 +613,7 @@ template <class _Key, class _Tp, class _Compare, class _Allocator> class multimap; template <class _TreeIterator> class __map_const_iterator; -#if __cplusplus >= 201103L +#ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp> union __value_type @@ -628,33 +626,29 @@ union __value_type value_type __cc; __nc_value_type __nc; - template <class ..._Args> - _LIBCPP_INLINE_VISIBILITY - __value_type(_Args&& ...__args) - : __cc(std::forward<_Args>(__args)...) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(const __value_type& __v) - : __cc(__v.__cc) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(__value_type& __v) - : __cc(__v.__cc) {} - - _LIBCPP_INLINE_VISIBILITY - __value_type(__value_type&& __v) - : __nc(std::move(__v.__nc)) {} - _LIBCPP_INLINE_VISIBILITY __value_type& operator=(const __value_type& __v) {__nc = __v.__cc; return *this;} _LIBCPP_INLINE_VISIBILITY __value_type& operator=(__value_type&& __v) - {__nc = std::move(__v.__nc); return *this;} + {__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 - ~__value_type() {__cc.~value_type();} + __value_type& operator=(_ValueTp&& __v) { + __nc = _VSTD::forward<_ValueTp>(__v); return *this; + } + +private: + __value_type() _LIBCPP_EQUAL_DELETE; + ~__value_type() _LIBCPP_EQUAL_DELETE; + __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE; + __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE; }; #else @@ -668,18 +662,11 @@ struct __value_type value_type __cc; - _LIBCPP_INLINE_VISIBILITY - __value_type() {} - - template <class _A0> - _LIBCPP_INLINE_VISIBILITY - __value_type(const _A0& __a0) - : __cc(__a0) {} - - template <class _A0, class _A1> - _LIBCPP_INLINE_VISIBILITY - __value_type(const _A0& __a0, const _A1& __a1) - : __cc(__a0, __a1) {} +private: + __value_type(); + __value_type(__value_type const&); + __value_type& operator=(__value_type const&); + ~__value_type(); }; #endif @@ -697,19 +684,17 @@ struct __extract_key_value_types<__value_type<_Key, _Tp> > template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_iterator { + typedef typename _TreeIterator::_NodeTypes _NodeTypes; + typedef typename _TreeIterator::__pointer_traits __pointer_traits; + _TreeIterator __i_; - typedef typename _TreeIterator::__pointer_traits __pointer_traits; - typedef typename _TreeIterator::value_type __value_type; - typedef typename __extract_key_value_types<__value_type>::__key_type __key_type; - typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type; public: typedef bidirectional_iterator_tag iterator_category; - typedef pair<__key_type, __mapped_type> value_type; + typedef typename _NodeTypes::__map_value_type value_type; typedef typename _TreeIterator::difference_type difference_type; typedef value_type& reference; - typedef typename __rebind_pointer<typename __pointer_traits::pointer, value_type>::type - pointer; + typedef typename _NodeTypes::__map_value_type_pointer pointer; _LIBCPP_INLINE_VISIBILITY __map_iterator() _NOEXCEPT {} @@ -758,19 +743,17 @@ public: template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator { + typedef typename _TreeIterator::_NodeTypes _NodeTypes; + typedef typename _TreeIterator::__pointer_traits __pointer_traits; + _TreeIterator __i_; - typedef typename _TreeIterator::__pointer_traits __pointer_traits; - typedef typename _TreeIterator::value_type __value_type; - typedef typename __extract_key_value_types<__value_type>::__key_type __key_type; - typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type; public: typedef bidirectional_iterator_tag iterator_category; - typedef pair<__key_type, __mapped_type> value_type; + typedef typename _NodeTypes::__map_value_type value_type; typedef typename _TreeIterator::difference_type difference_type; typedef const value_type& reference; - typedef typename __rebind_pointer<typename __pointer_traits::pointer, const value_type>::type - pointer; + typedef typename _NodeTypes::__const_map_value_type_pointer pointer; _LIBCPP_INLINE_VISIBILITY __map_const_iterator() _NOEXCEPT {} @@ -927,7 +910,7 @@ public: _LIBCPP_INLINE_VISIBILITY map& operator=(const map& __m) { -#if __cplusplus >= 201103L +#ifndef _LIBCPP_CXX03_LANG __tree_ = __m.__tree_; #else if (this != &__m) { @@ -1043,7 +1026,7 @@ public: size_type max_size() const _NOEXCEPT {return __tree_.max_size();} mapped_type& operator[](const key_type& __k); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +#ifndef _LIBCPP_CXX03_LANG mapped_type& operator[](key_type&& __k); #endif @@ -1057,18 +1040,18 @@ public: _LIBCPP_INLINE_VISIBILITY value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS - +#ifndef _LIBCPP_CXX03_LANG template <class ..._Args> - pair<iterator, bool> - emplace(_Args&& ...__args); + _LIBCPP_INLINE_VISIBILITY + pair<iterator, bool> emplace(_Args&& ...__args) { + return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...); + } template <class ..._Args> - iterator - emplace_hint(const_iterator __p, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS + _LIBCPP_INLINE_VISIBILITY + iterator emplace_hint(const_iterator __p, _Args&& ...__args) { + return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...); + } template <class _Pp, class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> @@ -1082,7 +1065,7 @@ public: iterator insert(const_iterator __pos, _Pp&& __p) {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> @@ -1093,15 +1076,14 @@ public: insert(const_iterator __p, const value_type& __v) {return __tree_.__insert_unique(__p.__i_, __v);} -#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) +#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> - insert( value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward<value_type>(__v));} + insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY - iterator - insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_unique(__p.__i_, _VSTD::forward<value_type>(__v));} + iterator insert(const_iterator __p, value_type&& __v) + {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));} #endif template <class _InputIterator> @@ -1121,62 +1103,45 @@ public: #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS #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 = lower_bound(__k); - if ( __p != end() && !key_comp()(__k, __p->first)) - 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 __tree_.__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 = lower_bound(__k); - if ( __p != end() && !key_comp()(__k, __p->first)) - 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 __tree_.__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 = lower_bound(__k); - if ( __p != end() && !key_comp()(__k, __p->first)) - return __p; - else - return emplace_hint(__p, - _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k), - _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); + return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, + _VSTD::piecewise_construct, + _VSTD::forward_as_tuple(__k), + _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); } template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) { - iterator __p = lower_bound(__k); - if ( __p != end() && !key_comp()(__k, __p->first)) - return __p; - else - return emplace_hint(__p, - _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)), - _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); + return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, + _VSTD::piecewise_construct, + _VSTD::forward_as_tuple(_VSTD::move(__k)), + _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); } template <class _Vp> @@ -1191,7 +1156,7 @@ public: } return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true); } - + template <class _Vp> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) @@ -1230,8 +1195,7 @@ public: } return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)); } -#endif -#endif + #endif _LIBCPP_INLINE_VISIBILITY @@ -1332,85 +1296,38 @@ private: typedef typename __base::__node __node; typedef typename __base::__node_allocator __node_allocator; typedef typename __base::__node_pointer __node_pointer; - typedef typename __base::__node_const_pointer __node_const_pointer; typedef typename __base::__node_base_pointer __node_base_pointer; - typedef typename __base::__node_base_const_pointer __node_base_const_pointer; + typedef __map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; -#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 +#ifdef _LIBCPP_CXX03_LANG __node_holder __construct_node_with_key(const key_type& __k); +#endif + + __node_base_pointer const& + __find_equal_key(__node_base_pointer& __parent, const key_type& __k) const; + _LIBCPP_INLINE_VISIBILITY __node_base_pointer& - __find_equal_key(__node_base_pointer& __parent, const key_type& __k); - __node_base_const_pointer - __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const; + __find_equal_key(__node_base_pointer& __parent, const key_type& __k) { + map const* __const_this = this; + return const_cast<__node_base_pointer&>( + __const_this->__find_equal_key(__parent, __k)); + } }; -// Find place to insert if __k doesn't exist -// Set __parent to parent of null leaf -// Return reference to null leaf -// If __k exists, set parent to node of __k and return reference to node of __k -template <class _Key, class _Tp, class _Compare, class _Allocator> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer& -map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent, - const key_type& __k) -{ - __node_pointer __nd = __tree_.__root(); - if (__nd != nullptr) - { - while (true) - { - if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first)) - { - if (__nd->__left_ != nullptr) - __nd = static_cast<__node_pointer>(__nd->__left_); - else - { - __parent = static_cast<__node_base_pointer>(__nd); - return __parent->__left_; - } - } - else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k)) - { - if (__nd->__right_ != nullptr) - __nd = static_cast<__node_pointer>(__nd->__right_); - else - { - __parent = static_cast<__node_base_pointer>(__nd); - return __parent->__right_; - } - } - else - { - __parent = static_cast<__node_base_pointer>(__nd); - return __parent; - } - } - } - __parent = static_cast<__node_base_pointer>(__tree_.__end_node()); - return __parent->__left_; -} // Find __k // Set __parent to parent of null leaf and // return reference to null leaf iv __k does not exist. // If __k exists, set parent to node of __k and return reference to node of __k template <class _Key, class _Tp, class _Compare, class _Allocator> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer -map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent, +typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer const& +map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent, const key_type& __k) const { - __node_const_pointer __nd = __tree_.__root(); + __node_pointer __nd = __tree_.__root(); if (__nd != nullptr) { while (true) @@ -1422,7 +1339,7 @@ map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer else { __parent = static_cast<__node_base_pointer>(__nd); - return const_cast<const __node_base_const_pointer&>(__parent->__left_); + return __parent->__left_; } } else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k)) @@ -1432,7 +1349,7 @@ map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer else { __parent = static_cast<__node_base_pointer>(__nd); - return const_cast<const __node_base_const_pointer&>(__parent->__right_); + return __parent->__right_; } } else @@ -1443,10 +1360,10 @@ map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer } } __parent = static_cast<__node_base_pointer>(__tree_.__end_node()); - return const_cast<const __node_base_const_pointer&>(__parent->__left_); + return __parent->__left_; } -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +#ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) @@ -1457,69 +1374,14 @@ map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) const_iterator __e = cend(); while (!__m.empty()) __tree_.__insert_unique(__e.__i_, - _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); + _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc)); } } -template <class _Key, class _Tp, class _Compare, class _Allocator> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node() -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class _A0> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __tree_.__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 _Compare, class _Allocator> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k) -{ - __node_allocator& __na = __tree_.__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 +#endif // !_LIBCPP_CXX03_LANG -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class _A0, class _A1, class ..._Args> -typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) -{ - __node_allocator& __na = __tree_.__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; -} -#endif // _LIBCPP_HAS_NO_VARIADICS - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#ifdef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder @@ -1550,25 +1412,29 @@ map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) return __r->__value_.__cc.second; } -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES +#else + +template <class _Key, class _Tp, class _Compare, class _Allocator> +_Tp& +map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) +{ + return __tree_.__emplace_unique_key_args(__k, + _VSTD::piecewise_construct, + _VSTD::forward_as_tuple(__k), + _VSTD::forward_as_tuple()).first->__cc.second; +} template <class _Key, class _Tp, class _Compare, class _Allocator> _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) { - __node_base_pointer __parent; - __node_base_pointer& __child = __find_equal_key(__parent, __k); - __node_pointer __r = static_cast<__node_pointer>(__child); - if (__child == nullptr) - { - __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); - __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - } - return __r->__value_.__cc.second; + return __tree_.__emplace_unique_key_args(__k, + _VSTD::piecewise_construct, + _VSTD::forward_as_tuple(_VSTD::move(__k)), + _VSTD::forward_as_tuple()).first->__cc.second; } -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // !_LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> _Tp& @@ -1587,43 +1453,15 @@ template <class _Key, class _Tp, class _Compare, class _Allocator> const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const { - __node_base_const_pointer __parent; - __node_base_const_pointer __child = __find_equal_key(__parent, __k); + __node_base_pointer __parent; + __node_base_pointer __child = __find_equal_key(__parent, __k); #ifndef _LIBCPP_NO_EXCEPTIONS if (__child == nullptr) throw out_of_range("map::at: key not found"); #endif // _LIBCPP_NO_EXCEPTIONS - return static_cast<__node_const_pointer>(__child)->__value_.__cc.second; -} - -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool> -map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get()); - if (__r.second) - __h.release(); - return __r; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -typename map<_Key, _Tp, _Compare, _Allocator>::iterator -map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, - _Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get()); - if (__r.__i_.__ptr_ == __h.get()) - __h.release(); - return __r; + return static_cast<__node_pointer>(__child)->__value_.__cc.second; } -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) template <class _Key, class _Tp, class _Compare, class _Allocator> inline _LIBCPP_INLINE_VISIBILITY @@ -1799,7 +1637,7 @@ public: _LIBCPP_INLINE_VISIBILITY multimap& operator=(const multimap& __m) { -#if __cplusplus >= 201103L +#ifndef _LIBCPP_CXX03_LANG __tree_ = __m.__tree_; #else if (this != &__m) { @@ -1921,18 +1759,19 @@ public: value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS +#ifndef _LIBCPP_CXX03_LANG template <class ..._Args> - iterator - emplace(_Args&& ...__args); + _LIBCPP_INLINE_VISIBILITY + iterator emplace(_Args&& ...__args) { + return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...); + } template <class ..._Args> - iterator - emplace_hint(const_iterator __p, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS + _LIBCPP_INLINE_VISIBILITY + iterator emplace_hint(const_iterator __p, _Args&& ...__args) { + return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); + } template <class _Pp, class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> @@ -1946,23 +1785,22 @@ public: iterator insert(const_iterator __pos, _Pp&& __p) {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));} -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - _LIBCPP_INLINE_VISIBILITY - iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} + iterator insert(value_type&& __v) + {return __tree_.__insert_multi(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY - iterator insert(const_iterator __p, const value_type& __v) - {return __tree_.__insert_multi(__p.__i_, __v);} + iterator insert(const_iterator __p, value_type&& __v) + {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));} + +#endif // _LIBCPP_CXX03_LANG -#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) _LIBCPP_INLINE_VISIBILITY - iterator insert( value_type&& __v) {return __tree_.__insert_multi(_VSTD::forward<value_type>(__v));} + iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} _LIBCPP_INLINE_VISIBILITY - iterator insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_multi(__p.__i_, _VSTD::forward<value_type>(__v));} -#endif + iterator insert(const_iterator __p, const value_type& __v) + {return __tree_.__insert_multi(__p.__i_, __v);} template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY @@ -2077,24 +1915,12 @@ private: typedef typename __base::__node __node; typedef typename __base::__node_allocator __node_allocator; typedef typename __base::__node_pointer __node_pointer; - typedef typename __base::__node_const_pointer __node_const_pointer; + typedef __map_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; - -#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 }; -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - +#ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) : __tree_(_VSTD::move(__m.__tree_), __a) @@ -2104,82 +1930,10 @@ multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const alloca const_iterator __e = cend(); while (!__m.empty()) __tree_.__insert_multi(__e.__i_, - _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_)); + _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc)); } } - -template <class _Key, class _Tp, class _Compare, class _Allocator> -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node() -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class _A0> -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __tree_.__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 _Compare, class _Allocator> -template <class _A0, class _A1, class ..._Args> -typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder -multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args) -{ - __node_allocator& __na = __tree_.__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; -} - -#endif // _LIBCPP_HAS_NO_VARIADICS -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator -multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_multi(__h.get()); - __h.release(); - return __r; -} - -template <class _Key, class _Tp, class _Compare, class _Allocator> -template <class ..._Args> -typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator -multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p, - _Args&& ...__args) -{ - __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); - iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get()); - __h.release(); - return __r; -} - -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) +#endif template <class _Key, class _Tp, class _Compare, class _Allocator> inline _LIBCPP_INLINE_VISIBILITY |