diff options
Diffstat (limited to 'libcxx/include/__tree')
| -rw-r--r-- | libcxx/include/__tree | 220 |
1 files changed, 60 insertions, 160 deletions
diff --git a/libcxx/include/__tree b/libcxx/include/__tree index cb7a1022e626..0f6e4ec37921 100644 --- a/libcxx/include/__tree +++ b/libcxx/include/__tree @@ -108,10 +108,10 @@ __tree_sub_invariant(_NodePtr __x) if (__x->__right_ && !__x->__right_->__is_black_) return 0; } - unsigned __h = __tree_sub_invariant(__x->__left_); + unsigned __h = _VSTD::__tree_sub_invariant(__x->__left_); if (__h == 0) return 0; // invalid left subtree - if (__h != __tree_sub_invariant(__x->__right_)) + if (__h != _VSTD::__tree_sub_invariant(__x->__right_)) return 0; // invalid or different height right subtree return __h + __x->__is_black_; // return black height of this node } @@ -128,13 +128,13 @@ __tree_invariant(_NodePtr __root) // check __x->__parent_ consistency if (__root->__parent_ == nullptr) return false; - if (!__tree_is_left_child(__root)) + if (!_VSTD::__tree_is_left_child(__root)) return false; // root must be black if (!__root->__is_black_) return false; // do normal node checks - return __tree_sub_invariant(__root) != 0; + return _VSTD::__tree_sub_invariant(__root) != 0; } // Returns: pointer to the left-most node under __x. @@ -168,8 +168,8 @@ _NodePtr __tree_next(_NodePtr __x) _NOEXCEPT { if (__x->__right_ != nullptr) - return __tree_min(__x->__right_); - while (!__tree_is_left_child(__x)) + return _VSTD::__tree_min(__x->__right_); + while (!_VSTD::__tree_is_left_child(__x)) __x = __x->__parent_unsafe(); return __x->__parent_unsafe(); } @@ -180,8 +180,8 @@ _EndNodePtr __tree_next_iter(_NodePtr __x) _NOEXCEPT { if (__x->__right_ != nullptr) - return static_cast<_EndNodePtr>(__tree_min(__x->__right_)); - while (!__tree_is_left_child(__x)) + return static_cast<_EndNodePtr>(_VSTD::__tree_min(__x->__right_)); + while (!_VSTD::__tree_is_left_child(__x)) __x = __x->__parent_unsafe(); return static_cast<_EndNodePtr>(__x->__parent_); } @@ -195,9 +195,9 @@ _NodePtr __tree_prev_iter(_EndNodePtr __x) _NOEXCEPT { if (__x->__left_ != nullptr) - return __tree_max(__x->__left_); + return _VSTD::__tree_max(__x->__left_); _NodePtr __xx = static_cast<_NodePtr>(__x); - while (__tree_is_left_child(__xx)) + while (_VSTD::__tree_is_left_child(__xx)) __xx = __xx->__parent_unsafe(); return __xx->__parent_unsafe(); } @@ -237,7 +237,7 @@ __tree_left_rotate(_NodePtr __x) _NOEXCEPT if (__x->__right_ != nullptr) __x->__right_->__set_parent(__x); __y->__parent_ = __x->__parent_; - if (__tree_is_left_child(__x)) + if (_VSTD::__tree_is_left_child(__x)) __x->__parent_->__left_ = __y; else __x->__parent_unsafe()->__right_ = __y; @@ -257,7 +257,7 @@ __tree_right_rotate(_NodePtr __x) _NOEXCEPT if (__x->__left_ != nullptr) __x->__left_->__set_parent(__x); __y->__parent_ = __x->__parent_; - if (__tree_is_left_child(__x)) + if (_VSTD::__tree_is_left_child(__x)) __x->__parent_->__left_ = __y; else __x->__parent_unsafe()->__right_ = __y; @@ -281,7 +281,7 @@ __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT while (__x != __root && !__x->__parent_unsafe()->__is_black_) { // __x->__parent_ != __root because __x->__parent_->__is_black == false - if (__tree_is_left_child(__x->__parent_unsafe())) + if (_VSTD::__tree_is_left_child(__x->__parent_unsafe())) { _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_; if (__y != nullptr && !__y->__is_black_) @@ -294,16 +294,16 @@ __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT } else { - if (!__tree_is_left_child(__x)) + if (!_VSTD::__tree_is_left_child(__x)) { __x = __x->__parent_unsafe(); - __tree_left_rotate(__x); + _VSTD::__tree_left_rotate(__x); } __x = __x->__parent_unsafe(); __x->__is_black_ = true; __x = __x->__parent_unsafe(); __x->__is_black_ = false; - __tree_right_rotate(__x); + _VSTD::__tree_right_rotate(__x); break; } } @@ -320,16 +320,16 @@ __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT } else { - if (__tree_is_left_child(__x)) + if (_VSTD::__tree_is_left_child(__x)) { __x = __x->__parent_unsafe(); - __tree_right_rotate(__x); + _VSTD::__tree_right_rotate(__x); } __x = __x->__parent_unsafe(); __x->__is_black_ = true; __x = __x->__parent_unsafe(); __x->__is_black_ = false; - __tree_left_rotate(__x); + _VSTD::__tree_left_rotate(__x); break; } } @@ -352,7 +352,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT // __y will have at most one child. // __y will be the initial hole in the tree (make the hole at a leaf) _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? - __z : __tree_next(__z); + __z : _VSTD::__tree_next(__z); // __x is __y's possibly null single child _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_; // __w is __x's possibly null uncle (will become __x's sibling) @@ -360,7 +360,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT // link __x to __y's parent, and find __w if (__x != nullptr) __x->__parent_ = __y->__parent_; - if (__tree_is_left_child(__y)) + if (_VSTD::__tree_is_left_child(__y)) { __y->__parent_->__left_ = __x; if (__y != __root) @@ -381,7 +381,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT { // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr __y->__parent_ = __z->__parent_; - if (__tree_is_left_child(__z)) + if (_VSTD::__tree_is_left_child(__z)) __y->__parent_->__left_ = __y; else __y->__parent_unsafe()->__right_ = __y; @@ -421,13 +421,13 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT // with a non-null black child). while (true) { - if (!__tree_is_left_child(__w)) // if x is left child + if (!_VSTD::__tree_is_left_child(__w)) // if x is left child { if (!__w->__is_black_) { __w->__is_black_ = true; __w->__parent_unsafe()->__is_black_ = false; - __tree_left_rotate(__w->__parent_unsafe()); + _VSTD::__tree_left_rotate(__w->__parent_unsafe()); // __x is still valid // reset __root only if necessary if (__root == __w->__left_) @@ -448,7 +448,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT break; } // reset sibling, and it still can't be null - __w = __tree_is_left_child(__x) ? + __w = _VSTD::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_; // continue; @@ -460,7 +460,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT // __w left child is non-null and red __w->__left_->__is_black_ = true; __w->__is_black_ = false; - __tree_right_rotate(__w); + _VSTD::__tree_right_rotate(__w); // __w is known not to be root, so root hasn't changed // reset sibling, and it still can't be null __w = __w->__parent_unsafe(); @@ -469,7 +469,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT __w->__is_black_ = __w->__parent_unsafe()->__is_black_; __w->__parent_unsafe()->__is_black_ = true; __w->__right_->__is_black_ = true; - __tree_left_rotate(__w->__parent_unsafe()); + _VSTD::__tree_left_rotate(__w->__parent_unsafe()); break; } } @@ -479,7 +479,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT { __w->__is_black_ = true; __w->__parent_unsafe()->__is_black_ = false; - __tree_right_rotate(__w->__parent_unsafe()); + _VSTD::__tree_right_rotate(__w->__parent_unsafe()); // __x is still valid // reset __root only if necessary if (__root == __w->__right_) @@ -500,7 +500,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT break; } // reset sibling, and it still can't be null - __w = __tree_is_left_child(__x) ? + __w = _VSTD::__tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_; // continue; @@ -512,7 +512,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT // __w right child is non-null and red __w->__right_->__is_black_ = true; __w->__is_black_ = false; - __tree_left_rotate(__w); + _VSTD::__tree_left_rotate(__w); // __w is known not to be root, so root hasn't changed // reset sibling, and it still can't be null __w = __w->__parent_unsafe(); @@ -521,7 +521,7 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT __w->__is_black_ = __w->__parent_unsafe()->__is_black_; __w->__parent_unsafe()->__is_black_ = true; __w->__left_->__is_black_ = true; - __tree_right_rotate(__w->__parent_unsafe()); + _VSTD::__tree_right_rotate(__w->__parent_unsafe()); break; } } @@ -533,19 +533,17 @@ __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT // node traits -#ifndef _LIBCPP_CXX03_LANG template <class _Tp> struct __is_tree_value_type_imp : false_type {}; template <class _Key, class _Value> -struct __is_tree_value_type_imp<__value_type<_Key, _Value>> : true_type {}; +struct __is_tree_value_type_imp<__value_type<_Key, _Value> > : true_type {}; template <class ..._Args> struct __is_tree_value_type : false_type {}; template <class _One> struct __is_tree_value_type<_One> : __is_tree_value_type_imp<typename __uncvref<_One>::type> {}; -#endif template <class _Tp> struct __tree_key_value_types { @@ -566,12 +564,10 @@ struct __tree_key_value_types { static __container_value_type* __get_ptr(__node_value_type& __n) { return _VSTD::addressof(__n); } -#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY static __container_value_type&& __move(__node_value_type& __v) { return _VSTD::move(__v); } -#endif }; template <class _Key, class _Tp> @@ -616,12 +612,10 @@ struct __tree_key_value_types<__value_type<_Key, _Tp> > { return _VSTD::addressof(__n.__get_value()); } -#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); } -#endif }; template <class _VoidPtr> @@ -845,7 +839,7 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_iterator& operator++() { __ptr_ = static_cast<__iter_pointer>( - __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); + _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); return *this; } _LIBCPP_INLINE_VISIBILITY @@ -854,7 +848,7 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_iterator& operator--() { - __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>( + __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>( static_cast<__end_node_pointer>(__ptr_))); return *this; } @@ -926,7 +920,7 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator++() { __ptr_ = static_cast<__iter_pointer>( - __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); + _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); return *this; } @@ -936,7 +930,7 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator--() { - __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>( + __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>( static_cast<__end_node_pointer>(__ptr_))); return *this; } @@ -973,7 +967,7 @@ private: template<class _Tp, class _Compare> #ifndef _LIBCPP_CXX03_LANG - _LIBCPP_DIAGNOSE_WARNING(!std::__invokable<_Compare const&, _Tp const&, _Tp const&>::value, + _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, "the specified comparator type does not provide a viable const call operator") #endif int __diagnose_non_const_comparator(); @@ -1103,7 +1097,6 @@ public: void __assign_unique(_ForwardIterator __first, _ForwardIterator __last); template <class _InputIterator> void __assign_multi(_InputIterator __first, _InputIterator __last); -#ifndef _LIBCPP_CXX03_LANG __tree(__tree&& __t) _NOEXCEPT_( is_nothrow_move_constructible<__node_allocator>::value && @@ -1114,8 +1107,6 @@ public: __node_traits::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<value_compare>::value && is_nothrow_move_assignable<__node_allocator>::value); -#endif // _LIBCPP_CXX03_LANG - ~__tree(); _LIBCPP_INLINE_VISIBILITY @@ -1129,7 +1120,7 @@ public: _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT - {return std::min<size_type>( + {return _VSTD::min<size_type>( __node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());} @@ -1146,12 +1137,11 @@ public: _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value); #endif -#ifndef _LIBCPP_CXX03_LANG template <class _Key, class ..._Args> pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args); template <class _Key, class ..._Args> - iterator + pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); template <class... _Args> @@ -1225,7 +1215,7 @@ public: >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { return __emplace_hint_unique_key_args(__p, __f, _VSTD::forward<_First>(__f), - _VSTD::forward<_Second>(__s)); + _VSTD::forward<_Second>(__s)).first; } template <class... _Args> @@ -1245,25 +1235,16 @@ public: _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { - return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)); + return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first; } template <class _Pp> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { - return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)); + return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first; } -#else - template <class _Key, class _Args> - _LIBCPP_INLINE_VISIBILITY - pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args); - template <class _Key, class _Args> - _LIBCPP_INLINE_VISIBILITY - iterator __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&); -#endif - _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __insert_unique(const __container_value_type& __v) { return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v); @@ -1271,15 +1252,9 @@ public: _LIBCPP_INLINE_VISIBILITY iterator __insert_unique(const_iterator __p, const __container_value_type& __v) { - return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v); + return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first; } -#ifdef _LIBCPP_CXX03_LANG - _LIBCPP_INLINE_VISIBILITY - iterator __insert_multi(const __container_value_type& __v); - _LIBCPP_INLINE_VISIBILITY - iterator __insert_multi(const_iterator __p, const __container_value_type& __v); -#else _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __insert_unique(__container_value_type&& __v) { return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v)); @@ -1287,7 +1262,7 @@ public: _LIBCPP_INLINE_VISIBILITY iterator __insert_unique(const_iterator __p, __container_value_type&& __v) { - return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)); + return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)).first; } template <class _Vp, class = typename enable_if< @@ -1332,8 +1307,6 @@ public: return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v)); } -#endif // !_LIBCPP_CXX03_LANG - _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_assign_unique(const __container_value_type& __v, __node_pointer __dest); @@ -1455,7 +1428,7 @@ private: __node_base_pointer& __find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v); - // FIXME: Make this function const qualified. Unfortunetly doing so + // FIXME: Make this function const qualified. Unfortunately doing so // breaks existing code which uses non-const callable comparators. template <class _Key> __node_base_pointer& @@ -1471,12 +1444,8 @@ private: __node_base_pointer& __dummy, const _Key& __v); -#ifndef _LIBCPP_CXX03_LANG template <class ..._Args> __node_holder __construct_node(_Args&& ...__args); -#else - __node_holder __construct_node(const __container_value_type& __v); -#endif void destroy(__node_pointer __nd) _NOEXCEPT; @@ -1621,20 +1590,20 @@ __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_poin { if (__cache->__parent_ == nullptr) return nullptr; - if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) + if (_VSTD::__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) { __cache->__parent_->__left_ = nullptr; __cache = static_cast<__node_pointer>(__cache->__parent_); if (__cache->__right_ == nullptr) return __cache; - return static_cast<__node_pointer>(__tree_leaf(__cache->__right_)); + return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__right_)); } // __cache is right child __cache->__parent_unsafe()->__right_ = nullptr; __cache = static_cast<__node_pointer>(__cache->__parent_); if (__cache->__left_ == nullptr) return __cache; - return static_cast<__node_pointer>(__tree_leaf(__cache->__left_)); + return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__left_)); } template <class _Tp, class _Compare, class _Allocator> @@ -1706,8 +1675,6 @@ __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) __begin_node() = __end_node(); } -#ifndef _LIBCPP_CXX03_LANG - template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_( @@ -1814,8 +1781,6 @@ __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) return *this; } -#endif // _LIBCPP_CXX03_LANG - template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::~__tree() { @@ -1854,7 +1819,7 @@ __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) using _VSTD::swap; swap(__begin_node_, __t.__begin_node_); swap(__pair1_.first(), __t.__pair1_.first()); - __swap_allocator(__node_alloc(), __t.__node_alloc()); + _VSTD::__swap_allocator(__node_alloc(), __t.__node_alloc()); __pair3_.swap(__t.__pair3_); if (size() == 0) __begin_node() = __end_node(); @@ -2113,21 +2078,14 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( __child = __new_node; if (__begin_node()->__left_ != nullptr) __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_); - __tree_balance_after_insert(__end_node()->__left_, __child); + _VSTD::__tree_balance_after_insert(__end_node()->__left_, __child); ++size(); } -#ifndef _LIBCPP_CXX03_LANG template <class _Tp, class _Compare, class _Allocator> template <class _Key, class... _Args> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) -#else -template <class _Tp, class _Compare, class _Allocator> -template <class _Key, class _Args> -pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> -__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args& __args) -#endif { __parent_pointer __parent; __node_base_pointer& __child = __find_equal(__parent, __k); @@ -2135,11 +2093,7 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _A bool __inserted = false; if (__child == nullptr) { -#ifndef _LIBCPP_CXX03_LANG __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); -#else - __node_holder __h = __construct_node(__args); -#endif __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); __r = __h.release(); __inserted = true; @@ -2147,41 +2101,27 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _A return pair<iterator, bool>(iterator(__r), __inserted); } - -#ifndef _LIBCPP_CXX03_LANG template <class _Tp, class _Compare, class _Allocator> template <class _Key, class... _Args> -typename __tree<_Tp, _Compare, _Allocator>::iterator +pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( const_iterator __p, _Key const& __k, _Args&&... __args) -#else -template <class _Tp, class _Compare, class _Allocator> -template <class _Key, class _Args> -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( - const_iterator __p, _Key const& __k, _Args& __args) -#endif { __parent_pointer __parent; __node_base_pointer __dummy; __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k); __node_pointer __r = static_cast<__node_pointer>(__child); + bool __inserted = false; if (__child == nullptr) { -#ifndef _LIBCPP_CXX03_LANG __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); -#else - __node_holder __h = __construct_node(__args); -#endif __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); __r = __h.release(); + __inserted = true; } - return iterator(__r); + return pair<iterator, bool>(iterator(__r), __inserted); } - -#ifndef _LIBCPP_CXX03_LANG - template <class _Tp, class _Compare, class _Allocator> template <class ..._Args> typename __tree<_Tp, _Compare, _Allocator>::__node_holder @@ -2259,46 +2199,6 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, return iterator(static_cast<__node_pointer>(__h.release())); } - -#else // _LIBCPP_CXX03_LANG - -template <class _Tp, class _Compare, class _Allocator> -typename __tree<_Tp, _Compare, _Allocator>::__node_holder -__tree<_Tp, _Compare, _Allocator>::__construct_node(const __container_value_type& __v) -{ - __node_allocator& __na = __node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); - __h.get_deleter().__value_constructed = true; - return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 -} - -#endif // _LIBCPP_CXX03_LANG - -#ifdef _LIBCPP_CXX03_LANG -template <class _Tp, class _Compare, class _Allocator> -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(const __container_value_type& __v) -{ - __parent_pointer __parent; - __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__v)); - __node_holder __h = __construct_node(__v); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - return iterator(__h.release()); -} - -template <class _Tp, class _Compare, class _Allocator> -typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const __container_value_type& __v) -{ - __parent_pointer __parent; - __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__v)); - __node_holder __h = __construct_node(__v); - __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - return iterator(__h.release()); -} -#endif - template <class _Tp, class _Compare, class _Allocator> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd) @@ -2348,8 +2248,8 @@ __tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _ if (__begin_node() == __ptr) __begin_node() = __r.__ptr_; --size(); - __tree_remove(__end_node()->__left_, - static_cast<__node_base_pointer>(__ptr)); + _VSTD::__tree_remove(__end_node()->__left_, + static_cast<__node_base_pointer>(__ptr)); return __r; } @@ -2727,7 +2627,7 @@ __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) return _Pp(iterator(__rt), iterator( __rt->__right_ != nullptr ? - static_cast<__iter_pointer>(__tree_min(__rt->__right_)) + static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_)) : __result)); } return _Pp(iterator(__result), iterator(__result)); @@ -2755,7 +2655,7 @@ __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const return _Pp(const_iterator(__rt), const_iterator( __rt->__right_ != nullptr ? - static_cast<__iter_pointer>(__tree_min(__rt->__right_)) + static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_)) : __result)); } return _Pp(const_iterator(__result), const_iterator(__result)); @@ -2824,8 +2724,8 @@ __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT __begin_node() = static_cast<__iter_pointer>(__np->__parent_); } --size(); - __tree_remove(__end_node()->__left_, - static_cast<__node_base_pointer>(__np)); + _VSTD::__tree_remove(__end_node()->__left_, + static_cast<__node_base_pointer>(__np)); return __node_holder(__np, _Dp(__node_alloc(), true)); } |