diff options
Diffstat (limited to 'include/__tree')
| -rw-r--r-- | include/__tree | 137 |
1 files changed, 66 insertions, 71 deletions
diff --git a/include/__tree b/include/__tree index 6391609b3982..94565bc3f74c 100644 --- a/include/__tree +++ b/include/__tree @@ -548,31 +548,15 @@ template <class _VoidPtr> class __tree_node_base : public __tree_end_node < - typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__tree_node_base<_VoidPtr> > -#else - rebind<__tree_node_base<_VoidPtr> >::other -#endif + typename __rebind_pointer<_VoidPtr, __tree_node_base<_VoidPtr> >::type > { __tree_node_base(const __tree_node_base&); __tree_node_base& operator=(const __tree_node_base&); public: - typedef typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__tree_node_base> -#else - rebind<__tree_node_base>::other -#endif - pointer; - typedef typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const __tree_node_base> -#else - rebind<const __tree_node_base>::other -#endif - const_pointer; + typedef typename __rebind_pointer<_VoidPtr, __tree_node_base>::type pointer; + typedef typename __rebind_pointer<_VoidPtr, const __tree_node_base>::type const_pointer; + typedef __tree_end_node<pointer> base; pointer __right_; @@ -623,13 +607,7 @@ public: typedef _Tp value_type; typedef _DiffType difference_type; typedef value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<value_type> -#else - rebind<value_type>::other -#endif - pointer; + typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT #if _LIBCPP_STD_VER > 11 @@ -694,13 +672,7 @@ public: typedef _Tp value_type; typedef _DiffType difference_type; typedef const value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const value_type> -#else - rebind<const value_type>::other -#endif - pointer; + typedef typename __rebind_pointer<__node_pointer, const value_type>::type pointer; _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT #if _LIBCPP_STD_VER > 11 @@ -710,13 +682,8 @@ public: private: typedef typename remove_const<__node>::type __non_const_node; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__non_const_node> -#else - rebind<__non_const_node>::other -#endif - __non_const_node_pointer; + typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type + __non_const_node_pointer; typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> __non_const_iterator; public: @@ -730,14 +697,8 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator++() { - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<typename __node::base> -#else - rebind<typename __node::base>::other -#endif - __node_base_pointer; - + typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type + __node_base_pointer; __ptr_ = static_cast<__node_pointer>( __tree_next(static_cast<__node_base_pointer>(__ptr_))); return *this; @@ -749,14 +710,8 @@ public: _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator--() { - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<typename __node::base> -#else - rebind<typename __node::base>::other -#endif - __node_base_pointer; - + typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type + __node_base_pointer; __ptr_ = static_cast<__node_pointer>( __tree_prev(static_cast<__node_base_pointer>(__ptr_))); return *this; @@ -810,20 +765,9 @@ public: typedef typename __node_base::pointer __node_base_const_pointer; private: typedef typename __node_base::base __end_node_t; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__end_node_t> -#else - rebind<__end_node_t>::other -#endif - __end_node_ptr; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__end_node_t> -#else - rebind<__end_node_t>::other -#endif - __end_node_const_ptr; + typedef typename __rebind_pointer<__node_pointer, __end_node_t>::type + __end_node_ptr; + typedef __end_node_ptr __end_node_const_ptr; __node_pointer __begin_node_; __compressed_pair<__end_node_t, __node_allocator> __pair1_; @@ -965,6 +909,13 @@ public: iterator __insert_multi(const value_type& __v); iterator __insert_multi(const_iterator __p, const value_type& __v); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + pair<iterator, bool> __insert_unique( value_type&& __v); + iterator __insert_unique(const_iterator __p, value_type&& __v); + iterator __insert_multi( value_type&& __v); + iterator __insert_multi(const_iterator __p, value_type&& __v); +#endif + pair<iterator, bool> __node_insert_unique(__node_pointer __nd); iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); @@ -1786,6 +1737,28 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, #endif // _LIBCPP_HAS_NO_VARIADICS template <class _Tp, class _Compare, class _Allocator> +pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> +__tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v) +{ + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + pair<iterator, bool> __r = __node_insert_unique(__h.get()); + if (__r.second) + __h.release(); + return __r; +} + +template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v) +{ + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + iterator __r = __node_insert_unique(__p, __h.get()); + if (__r.__ptr_ == __h.get()) + __h.release(); + return __r; +} + +template <class _Tp, class _Compare, class _Allocator> template <class _Vp> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v) @@ -1810,6 +1783,28 @@ __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v } template <class _Tp, class _Compare, class _Allocator> +typename __tree<_Tp, _Compare, _Allocator>::iterator +__tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v) +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_leaf_high(__parent, __v); + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__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, value_type&& __v) +{ + __node_base_pointer __parent; + __node_base_pointer& __child = __find_leaf(__p, __parent, __v); + __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v)); + __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + return iterator(__h.release()); +} + +template <class _Tp, class _Compare, class _Allocator> template <class _Vp> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v) |