diff options
Diffstat (limited to 'include/__tree')
| -rw-r--r-- | include/__tree | 70 |
1 files changed, 63 insertions, 7 deletions
diff --git a/include/__tree b/include/__tree index 3b3586ca6..aa7370bfb 100644 --- a/include/__tree +++ b/include/__tree @@ -1341,15 +1341,20 @@ public: #endif // !_LIBCPP_CXX03_LANG + _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __node_insert_unique(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(__node_pointer __nd); + _LIBCPP_INLINE_VISIBILITY iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); - _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer); + _LIBCPP_INLINE_VISIBILITY iterator + __remove_node_pointer(__node_pointer) _NOEXCEPT; #if _LIBCPP_STD_VER > 14 template <class _NodeHandle, class _InsertReturnType> @@ -1358,6 +1363,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_unique(_Tree& __source); template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY @@ -1365,6 +1373,9 @@ public: template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&); + template <class _Tree> + _LIBCPP_INLINE_VISIBILITY + void __node_handle_merge_multi(_Tree& __source); template <class _NodeHandle> @@ -1384,7 +1395,7 @@ public: void __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, - __node_base_pointer __new_node); + __node_base_pointer __new_node) _NOEXCEPT; template <class _Key> iterator find(const _Key& __v); @@ -2129,10 +2140,9 @@ __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, } template <class _Tp, class _Compare, class _Allocator> -void -__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer __parent, - __node_base_pointer& __child, - __node_base_pointer __new_node) +void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( + __parent_pointer __parent, __node_base_pointer& __child, + __node_base_pointer __new_node) _NOEXCEPT { __new_node->__left_ = nullptr; __new_node->__right_ = nullptr; @@ -2384,7 +2394,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator -__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) +__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT { iterator __r(__ptr); ++__r; @@ -2472,6 +2482,30 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) } template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = + __find_equal(__parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + if (__child != nullptr) + continue; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + +template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_INLINE_VISIBILITY typename __tree<_Tp, _Compare, _Allocator>::iterator @@ -2507,6 +2541,28 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi( return iterator(__ptr); } +template <class _Tp, class _Compare, class _Allocator> +template <class _Tree> +_LIBCPP_INLINE_VISIBILITY +void +__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) +{ + static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, ""); + + for (typename _Tree::iterator __i = __source.begin(); + __i != __source.end();) + { + __node_pointer __src_ptr = __i.__get_np(); + __parent_pointer __parent; + __node_base_pointer& __child = __find_leaf_high( + __parent, _NodeTypes::__get_key(__src_ptr->__value_)); + ++__i; + __source.__remove_node_pointer(__src_ptr); + __insert_node_at(__parent, __child, + static_cast<__node_base_pointer>(__src_ptr)); + } +} + #endif // _LIBCPP_STD_VER > 14 template <class _Tp, class _Compare, class _Allocator> |