Index: include/__config
===================================================================
--- include/__config
+++ include/__config
@@ -42,6 +42,8 @@
 // Fix undefined behavior in how std::list stores it's linked nodes.
 #define _LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB
 #define _LIBCPP_ABI_FORWARD_LIST_REMOVE_NODE_POINTER_UB
+// Fix undefined behavior in  how __tree stores its end and parent nodes.
+#define _LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB
 #define _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
 #endif
 
Index: include/__tree
===================================================================
--- include/__tree
+++ include/__tree
@@ -165,21 +165,33 @@
     if (__x->__right_ != nullptr)
         return __tree_min(__x->__right_);
     while (!__tree_is_left_child(__x))
-        __x = __x->__parent_;
-    return __x->__parent_;
+        __x = __x->__parent_unsafe();
+    return __x->__parent_unsafe();
+}
+
+template <class _NodeBasePtr, class _NodePtr>
+_NodeBasePtr
+__tree_next_iter(_NodePtr __x) _NOEXCEPT
+{
+    if (__x->__right_ != nullptr)
+        return static_cast<_NodeBasePtr>(__tree_min(__x->__right_));
+    while (!__tree_is_left_child(__x))
+        __x = __x->__parent_unsafe();
+    return __x->__parent_; // decltype(__parent_) == _NodeBasePtr
 }
 
 // Returns:  pointer to the previous in-order node before __x.
 // Precondition:  __x != nullptr.
-template <class _NodePtr>
+template <class _NodePtr, class _NodeBasePtr>
 _NodePtr
-__tree_prev(_NodePtr __x) _NOEXCEPT
+__tree_prev_iter(_NodeBasePtr __x) _NOEXCEPT
 {
     if (__x->__left_ != nullptr)
         return __tree_max(__x->__left_);
-    while (__tree_is_left_child(__x))
-        __x = __x->__parent_;
-    return __x->__parent_;
+    _NodePtr __xx = static_cast<_NodePtr>(__x);
+    while (__tree_is_left_child(__xx))
+        __xx = __xx->__parent_unsafe();
+    return __xx->__parent_unsafe();
 }
 
 // Returns:  pointer to a node which has no children
@@ -215,14 +227,14 @@
     _NodePtr __y = __x->__right_;
     __x->__right_ = __y->__left_;
     if (__x->__right_ != nullptr)
-        __x->__right_->__parent_ = __x;
+        __x->__right_->__set_parent(__x);
     __y->__parent_ = __x->__parent_;
     if (__tree_is_left_child(__x))
         __x->__parent_->__left_ = __y;
     else
-        __x->__parent_->__right_ = __y;
+        __x->__parent_unsafe()->__right_ = __y;
     __y->__left_ = __x;
-    __x->__parent_ = __y;
+    __x->__set_parent(__y);
 }
 
 // Effects:  Makes __x->__left_ the subtree root with __x as its right child
@@ -235,14 +247,14 @@
     _NodePtr __y = __x->__left_;
     __x->__left_ = __y->__right_;
     if (__x->__left_ != nullptr)
-        __x->__left_->__parent_ = __x;
+        __x->__left_->__set_parent(__x);
     __y->__parent_ = __x->__parent_;
     if (__tree_is_left_child(__x))
         __x->__parent_->__left_ = __y;
     else
-        __x->__parent_->__right_ = __y;
+        __x->__parent_unsafe()->__right_ = __y;
     __y->__right_ = __x;
-    __x->__parent_ = __y;
+    __x->__set_parent(__y);
 }
 
 // Effects:  Rebalances __root after attaching __x to a leaf.
@@ -258,17 +270,17 @@
 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
 {
     __x->__is_black_ = __x == __root;
-    while (__x != __root && !__x->__parent_->__is_black_)
+    while (__x != __root && !__x->__parent_unsafe()->__is_black_)
     {
         // __x->__parent_ != __root because __x->__parent_->__is_black == false
-        if (__tree_is_left_child(__x->__parent_))
+        if (__tree_is_left_child(__x->__parent_unsafe()))
         {
-            _NodePtr __y = __x->__parent_->__parent_->__right_;
+            _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;
             if (__y != nullptr && !__y->__is_black_)
             {
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = __x == __root;
                 __y->__is_black_ = true;
             }
@@ -276,12 +288,12 @@
             {
                 if (!__tree_is_left_child(__x))
                 {
-                    __x = __x->__parent_;
+                    __x = __x->__parent_unsafe();
                     __tree_left_rotate(__x);
                 }
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = false;
                 __tree_right_rotate(__x);
                 break;
@@ -289,12 +301,12 @@
         }
         else
         {
-            _NodePtr __y = __x->__parent_->__parent_->__left_;
+            _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;
             if (__y != nullptr && !__y->__is_black_)
             {
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = __x == __root;
                 __y->__is_black_ = true;
             }
@@ -302,12 +314,12 @@
             {
                 if (__tree_is_left_child(__x))
                 {
-                    __x = __x->__parent_;
+                    __x = __x->__parent_unsafe();
                     __tree_right_rotate(__x);
                 }
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
-                __x = __x->__parent_;
+                __x = __x->__parent_unsafe();
                 __x->__is_black_ = false;
                 __tree_left_rotate(__x);
                 break;
@@ -344,13 +356,13 @@
     {
         __y->__parent_->__left_ = __x;
         if (__y != __root)
-            __w = __y->__parent_->__right_;
+            __w = __y->__parent_unsafe()->__right_;
         else
             __root = __x;  // __w == nullptr
     }
     else
     {
-        __y->__parent_->__right_ = __x;
+        __y->__parent_unsafe()->__right_ = __x;
         // __y can't be root if it is a right child
         __w = __y->__parent_->__left_;
     }
@@ -364,12 +376,12 @@
         if (__tree_is_left_child(__z))
             __y->__parent_->__left_ = __y;
         else
-            __y->__parent_->__right_ = __y;
+            __y->__parent_unsafe()->__right_ = __y;
         __y->__left_ = __z->__left_;
-        __y->__left_->__parent_ = __y;
+        __y->__left_->__set_parent(__y);
         __y->__right_ = __z->__right_;
         if (__y->__right_ != nullptr)
-            __y->__right_->__parent_ = __y;
+            __y->__right_->__set_parent(__y);
         __y->__is_black_ = __z->__is_black_;
         if (__root == __z)
             __root = __y;
@@ -406,8 +418,8 @@
                     if (!__w->__is_black_)
                     {
                         __w->__is_black_ = true;
-                        __w->__parent_->__is_black_ = false;
-                        __tree_left_rotate(__w->__parent_);
+                        __w->__parent_unsafe()->__is_black_ = false;
+                        __tree_left_rotate(__w->__parent_unsafe());
                         // __x is still valid
                         // reset __root only if necessary
                         if (__root == __w->__left_)
@@ -420,7 +432,7 @@
                         (__w->__right_ == nullptr || __w->__right_->__is_black_))
                     {
                         __w->__is_black_ = false;
-                        __x = __w->__parent_;
+                        __x = __w->__parent_unsafe();
                         // __x can no longer be null
                         if (__x == __root || !__x->__is_black_)
                         {
@@ -429,7 +441,7 @@
                         }
                         // reset sibling, and it still can't be null
                         __w = __tree_is_left_child(__x) ?
-                                    __x->__parent_->__right_ :
+                                    __x->__parent_unsafe()->__right_ :
                                     __x->__parent_->__left_;
                         // continue;
                     }
@@ -443,13 +455,13 @@
                             __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_;
+                            __w = __w->__parent_unsafe();
                         }
                         // __w has a right red child, left child may be null
-                        __w->__is_black_ = __w->__parent_->__is_black_;
-                        __w->__parent_->__is_black_ = true;
+                        __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
+                        __w->__parent_unsafe()->__is_black_ = true;
                         __w->__right_->__is_black_ = true;
-                        __tree_left_rotate(__w->__parent_);
+                        __tree_left_rotate(__w->__parent_unsafe());
                         break;
                     }
                 }
@@ -458,8 +470,8 @@
                     if (!__w->__is_black_)
                     {
                         __w->__is_black_ = true;
-                        __w->__parent_->__is_black_ = false;
-                        __tree_right_rotate(__w->__parent_);
+                        __w->__parent_unsafe()->__is_black_ = false;
+                        __tree_right_rotate(__w->__parent_unsafe());
                         // __x is still valid
                         // reset __root only if necessary
                         if (__root == __w->__right_)
@@ -472,7 +484,7 @@
                         (__w->__right_ == nullptr || __w->__right_->__is_black_))
                     {
                         __w->__is_black_ = false;
-                        __x = __w->__parent_;
+                        __x = __w->__parent_unsafe();
                         // __x can no longer be null
                         if (!__x->__is_black_ || __x == __root)
                         {
@@ -481,7 +493,7 @@
                         }
                         // reset sibling, and it still can't be null
                         __w = __tree_is_left_child(__x) ?
-                                    __x->__parent_->__right_ :
+                                    __x->__parent_unsafe()->__right_ :
                                     __x->__parent_->__left_;
                         // continue;
                     }
@@ -495,13 +507,13 @@
                             __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_;
+                            __w = __w->__parent_unsafe();
                         }
                         // __w has a left red child, right child may be null
-                        __w->__is_black_ = __w->__parent_->__is_black_;
-                        __w->__parent_->__is_black_ = true;
+                        __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
+                        __w->__parent_unsafe()->__is_black_ = true;
                         __w->__left_->__is_black_ = true;
-                        __tree_right_rotate(__w->__parent_);
+                        __tree_right_rotate(__w->__parent_unsafe());
                         break;
                     }
                 }
@@ -617,6 +629,15 @@
   typedef __tree_end_node<__node_base_pointer>                  __end_node_type;
   typedef typename __rebind_pointer<_VoidPtr, __end_node_type>::type
                                                              __end_node_pointer;
+#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)
+  typedef __end_node_pointer __parent_pointer;
+#else
+  typedef typename conditional<
+      is_pointer<__end_node_pointer>::value,
+        __end_node_pointer,
+        __node_base_pointer>::type __parent_pointer;
+#endif
+
 private:
   static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
                   "_VoidPtr does not point to unqualified void type");
@@ -657,6 +678,14 @@
                                                       __node_value_type_pointer;
   typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
                                                 __const_node_value_type_pointer;
+#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB)
+  typedef typename __base::__end_node_pointer __iter_pointer;
+#else
+  typedef typename conditional<
+      is_pointer<__node_pointer>::value,
+        typename __base::__end_node_pointer,
+        __node_pointer>::type __iter_pointer;
+#endif
 private:
     static_assert(!is_const<__node_type>::value,
                 "_NodePtr should never be a pointer to const");
@@ -692,11 +721,20 @@
 
 public:
     typedef typename _NodeBaseTypes::__node_base_pointer pointer;
+    typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer;
 
-    pointer __right_;
-    pointer __parent_;
+    pointer          __right_;
+    __parent_pointer __parent_;
     bool __is_black_;
 
+    _LIBCPP_INLINE_VISIBILITY
+    pointer __parent_unsafe() const { return static_cast<pointer>(__parent_);}
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __set_parent(pointer __p) {
+        __parent_ = static_cast<__parent_pointer>(__p);
+    }
+
 private:
   ~__tree_node_base() _LIBCPP_EQUAL_DELETE;
   __tree_node_base(__tree_node_base const&) _LIBCPP_EQUAL_DELETE;
@@ -761,9 +799,11 @@
     typedef __tree_node_types<_NodePtr>                     _NodeTypes;
     typedef _NodePtr                                        __node_pointer;
     typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
+    typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;
+    typedef typename _NodeTypes::__iter_pointer             __iter_pointer;
     typedef pointer_traits<__node_pointer> __pointer_traits;
 
-    __node_pointer __ptr_;
+    __iter_pointer __ptr_;
 
 public:
     typedef bidirectional_iterator_tag                     iterator_category;
@@ -778,14 +818,15 @@
 #endif
     {}
 
-    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
+    _LIBCPP_INLINE_VISIBILITY reference operator*() const
+        {return __get_np()->__value_;}
     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
-        {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
+        {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_iterator& operator++() {
-      __ptr_ = static_cast<__node_pointer>(
-          __tree_next(static_cast<__node_base_pointer>(__ptr_)));
+      __ptr_ = static_cast<__iter_pointer>(
+          __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
       return *this;
     }
     _LIBCPP_INLINE_VISIBILITY
@@ -794,8 +835,8 @@
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_iterator& operator--() {
-      __ptr_ = static_cast<__node_pointer>(
-          __tree_prev(static_cast<__node_base_pointer>(__ptr_)));
+      __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(
+          static_cast<__end_node_pointer>(__ptr_)));
       return *this;
     }
     _LIBCPP_INLINE_VISIBILITY
@@ -812,6 +853,9 @@
 private:
     _LIBCPP_INLINE_VISIBILITY
     explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+    explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+    _LIBCPP_INLINE_VISIBILITY
+    __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
     template <class, class, class> friend class __tree;
     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator;
@@ -827,9 +871,11 @@
     typedef __tree_node_types<_NodePtr>                     _NodeTypes;
     typedef typename _NodeTypes::__node_pointer             __node_pointer;
     typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
+    typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;
+    typedef typename _NodeTypes::__iter_pointer             __iter_pointer;
     typedef pointer_traits<__node_pointer> __pointer_traits;
 
-    __node_pointer __ptr_;
+    __iter_pointer __ptr_;
 
 public:
     typedef bidirectional_iterator_tag                           iterator_category;
@@ -852,14 +898,15 @@
     __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT
         : __ptr_(__p.__ptr_) {}
 
-    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
+    _LIBCPP_INLINE_VISIBILITY reference operator*() const
+        {return __get_np()->__value_;}
     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
-        {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
+        {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator& operator++() {
-      __ptr_ = static_cast<__node_pointer>(
-          __tree_next(static_cast<__node_base_pointer>(__ptr_)));
+      __ptr_ = static_cast<__iter_pointer>(
+          __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
       return *this;
     }
 
@@ -869,8 +916,8 @@
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator& operator--() {
-      __ptr_ = static_cast<__node_pointer>(
-          __tree_prev(static_cast<__node_base_pointer>(__ptr_)));
+      __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(
+          static_cast<__end_node_pointer>(__ptr_)));
       return *this;
     }
 
@@ -889,12 +936,19 @@
     _LIBCPP_INLINE_VISIBILITY
     explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT
         : __ptr_(__p) {}
+    _LIBCPP_INLINE_VISIBILITY
+    explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT
+        : __ptr_(__p) {}
+    _LIBCPP_INLINE_VISIBILITY
+    __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); }
+
     template <class, class, class> friend class __tree;
     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;
     template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
+
 };
 
 template <class _Tp, class _Compare, class _Allocator>
@@ -932,6 +986,9 @@
     typedef typename _NodeTypes::__end_node_type       __end_node_t;
     typedef typename _NodeTypes::__end_node_pointer    __end_node_ptr;
 
+    typedef typename _NodeTypes::__parent_pointer      __parent_pointer;
+    typedef typename _NodeTypes::__iter_pointer        __iter_pointer;
+
     typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
     typedef allocator_traits<__node_allocator>         __node_traits;
 
@@ -948,22 +1005,22 @@
                  "Allocator does not rebind pointers in a sane manner.");
 
 private:
-    __node_pointer                                     __begin_node_;
+    __iter_pointer                                     __begin_node_;
     __compressed_pair<__end_node_t, __node_allocator>  __pair1_;
     __compressed_pair<size_type, value_compare>        __pair3_;
 
 public:
     _LIBCPP_INLINE_VISIBILITY
-    __node_pointer __end_node() _NOEXCEPT
+    __iter_pointer __end_node() _NOEXCEPT
     {
-        return static_cast<__node_pointer>(
+        return static_cast<__iter_pointer>(
                 pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())
         );
     }
     _LIBCPP_INLINE_VISIBILITY
-    __node_pointer __end_node() const _NOEXCEPT
+    __iter_pointer __end_node() const _NOEXCEPT
     {
-        return static_cast<__node_pointer>(
+        return static_cast<__iter_pointer>(
             pointer_traits<__end_node_ptr>::pointer_to(
                 const_cast<__end_node_t&>(__pair1_.first())
             )
@@ -976,9 +1033,12 @@
     const __node_allocator& __node_alloc() const _NOEXCEPT
         {return __pair1_.second();}
     _LIBCPP_INLINE_VISIBILITY
-          __node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
+          __iter_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}
+    _LIBCPP_INLINE_VISIBILITY
+    const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
     _LIBCPP_INLINE_VISIBILITY
-    const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}
+    __node_pointer __begin_node_downcast() const _NOEXCEPT
+        { return static_cast<__node_pointer>(__begin_node_);}
 public:
     _LIBCPP_INLINE_VISIBILITY
     allocator_type __alloc() const _NOEXCEPT
@@ -1000,6 +1060,10 @@
     __node_pointer __root() const _NOEXCEPT
         {return static_cast<__node_pointer>(__end_node()->__left_);}
 
+    __node_base_pointer* __root_ptr() const _NOEXCEPT {
+        return _VSTD::addressof(__end_node()->__left_);
+    }
+
     typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
     typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
 
@@ -1257,7 +1321,7 @@
     template <class _Key>
         size_type __erase_multi(const _Key& __k);
 
-    void __insert_node_at(__node_base_pointer __parent,
+    void __insert_node_at(__parent_pointer     __parent,
                           __node_base_pointer& __child,
                           __node_base_pointer __new_node);
 
@@ -1278,7 +1342,7 @@
     template <class _Key>
         iterator __lower_bound(const _Key& __v,
                                __node_pointer __root,
-                               __node_pointer __result);
+                               __iter_pointer __result);
     template <class _Key>
         _LIBCPP_INLINE_VISIBILITY
         const_iterator lower_bound(const _Key& __v) const
@@ -1286,7 +1350,7 @@
     template <class _Key>
         const_iterator __lower_bound(const _Key& __v,
                                      __node_pointer __root,
-                                     __node_pointer __result) const;
+                                     __iter_pointer __result) const;
     template <class _Key>
         _LIBCPP_INLINE_VISIBILITY
         iterator upper_bound(const _Key& __v)
@@ -1294,7 +1358,7 @@
     template <class _Key>
         iterator __upper_bound(const _Key& __v,
                                __node_pointer __root,
-                               __node_pointer __result);
+                               __iter_pointer __result);
     template <class _Key>
         _LIBCPP_INLINE_VISIBILITY
         const_iterator upper_bound(const _Key& __v) const
@@ -1302,7 +1366,7 @@
     template <class _Key>
         const_iterator __upper_bound(const _Key& __v,
                                      __node_pointer __root,
-                                     __node_pointer __result) const;
+                                     __iter_pointer __result) const;
     template <class _Key>
         pair<iterator, iterator>
         __equal_range_unique(const _Key& __k);
@@ -1322,19 +1386,20 @@
 
     __node_holder remove(const_iterator __p) _NOEXCEPT;
 private:
-    typename __node_base::pointer&
-        __find_leaf_low(typename __node_base::pointer& __parent, const key_type& __v);
-    typename __node_base::pointer&
-        __find_leaf_high(typename __node_base::pointer& __parent, const key_type& __v);
-    typename __node_base::pointer&
+    __node_base_pointer&
+        __find_leaf_low(__parent_pointer& __parent, const key_type& __v);
+    __node_base_pointer&
+        __find_leaf_high(__parent_pointer& __parent, const key_type& __v);
+    __node_base_pointer&
         __find_leaf(const_iterator __hint,
-                    typename __node_base::pointer& __parent, const key_type& __v);
+                    __parent_pointer& __parent, const key_type& __v);
     template <class _Key>
-        typename __node_base::pointer&
-        __find_equal(typename __node_base::pointer& __parent, const _Key& __v);
+    __node_base_pointer&
+        __find_equal(__parent_pointer& __parent, const _Key& __v);
     template <class _Key>
-        typename __node_base::pointer&
-        __find_equal(const_iterator __hint, typename __node_base::pointer& __parent,
+    __node_base_pointer&
+        __find_equal(const_iterator __hint, __parent_pointer& __parent,
+                     __node_base_pointer& __dummy,
                      const _Key& __v);
 
 #ifndef _LIBCPP_CXX03_LANG
@@ -1418,7 +1483,7 @@
 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
 __tree<_Tp, _Compare, _Allocator>::__detach()
 {
-    __node_pointer __cache = __begin_node();
+    __node_pointer __cache = __begin_node_downcast();
     __begin_node() = __end_node();
     __end_node()->__left_->__parent_ = nullptr;
     __end_node()->__left_ = nullptr;
@@ -1450,7 +1515,7 @@
         return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
     }
     // __cache is right child
-    __cache->__parent_->__right_ = nullptr;
+    __cache->__parent_unsafe()->__right_ = nullptr;
     __cache = static_cast<__node_pointer>(__cache->__parent_);
     if (__cache->__left_ == nullptr)
         return __cache;
@@ -1585,7 +1650,7 @@
         __begin_node() = __end_node();
     else
     {
-        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+        __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
         __t.__begin_node() = __t.__end_node();
         __t.__end_node()->__left_ = nullptr;
         __t.size() = 0;
@@ -1605,7 +1670,7 @@
         {
             __begin_node() = __t.__begin_node();
             __end_node()->__left_ = __t.__end_node()->__left_;
-            __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+            __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
             size() = __t.size();
             __t.__begin_node() = __t.__end_node();
             __t.__end_node()->__left_ = nullptr;
@@ -1633,7 +1698,7 @@
         __begin_node() = __end_node();
     else
     {
-        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+        __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
         __t.__begin_node() = __t.__end_node();
         __t.__end_node()->__left_ = nullptr;
         __t.size() = 0;
@@ -1741,11 +1806,11 @@
     if (size() == 0)
         __begin_node() = __end_node();
     else
-        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
+        __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
     if (__t.size() == 0)
         __t.__begin_node() = __t.__end_node();
     else
-        __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
+        __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());
 }
 
 template <class _Tp, class _Compare, class _Allocator>
@@ -1762,8 +1827,8 @@
 // Set __parent to parent of null leaf
 // Return reference to null leaf
 template <class _Tp, class _Compare, class _Allocator>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
-__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(typename __node_base::pointer& __parent,
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
+__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent,
                                                    const key_type& __v)
 {
     __node_pointer __nd = __root();
@@ -1777,8 +1842,8 @@
                     __nd = static_cast<__node_pointer>(__nd->__right_);
                 else
                 {
-                    __parent = static_cast<__node_base_pointer>(__nd);
-                    return __parent->__right_;
+                    __parent = static_cast<__parent_pointer>(__nd);
+                    return __nd->__right_;
                 }
             }
             else
@@ -1787,13 +1852,13 @@
                     __nd = static_cast<__node_pointer>(__nd->__left_);
                 else
                 {
-                    __parent = static_cast<__node_base_pointer>(__nd);
+                    __parent = static_cast<__parent_pointer>(__nd);
                     return __parent->__left_;
                 }
             }
         }
     }
-    __parent = static_cast<__node_base_pointer>(__end_node());
+    __parent = static_cast<__parent_pointer>(__end_node());
     return __parent->__left_;
 }
 
@@ -1801,8 +1866,8 @@
 // Set __parent to parent of null leaf
 // Return reference to null leaf
 template <class _Tp, class _Compare, class _Allocator>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
-__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(typename __node_base::pointer& __parent,
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
+__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent,
                                                     const key_type& __v)
 {
     __node_pointer __nd = __root();
@@ -1816,7 +1881,7 @@
                     __nd = static_cast<__node_pointer>(__nd->__left_);
                 else
                 {
-                    __parent = static_cast<__node_base_pointer>(__nd);
+                    __parent = static_cast<__parent_pointer>(__nd);
                     return __parent->__left_;
                 }
             }
@@ -1826,13 +1891,13 @@
                     __nd = static_cast<__node_pointer>(__nd->__right_);
                 else
                 {
-                    __parent = static_cast<__node_base_pointer>(__nd);
-                    return __parent->__right_;
+                    __parent = static_cast<__parent_pointer>(__nd);
+                    return __nd->__right_;
                 }
             }
         }
     }
-    __parent = static_cast<__node_base_pointer>(__end_node());
+    __parent = static_cast<__parent_pointer>(__end_node());
     return __parent->__left_;
 }
 
@@ -1843,9 +1908,9 @@
 // Set __parent to parent of null leaf
 // Return reference to null leaf
 template <class _Tp, class _Compare, class _Allocator>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
 __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint,
-                                               typename __node_base::pointer& __parent,
+                                               __parent_pointer& __parent,
                                                const key_type& __v)
 {
     if (__hint == end() || !value_comp()(*__hint, __v))  // check before
@@ -1857,13 +1922,13 @@
             // *prev(__hint) <= __v <= *__hint
             if (__hint.__ptr_->__left_ == nullptr)
             {
-                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
+                __parent = static_cast<__parent_pointer>(__hint.__ptr_);
                 return __parent->__left_;
             }
             else
             {
-                __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
-                return __parent->__right_;
+                __parent = static_cast<__parent_pointer>(__prior.__ptr_);
+                return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
             }
         }
         // __v < *prev(__hint)
@@ -1879,43 +1944,44 @@
 // If __v exists, set parent to node of __v and return reference to node of __v
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
-__tree<_Tp, _Compare, _Allocator>::__find_equal(typename __node_base::pointer& __parent,
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
+__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent,
                                                 const _Key& __v)
 {
     __node_pointer __nd = __root();
+    __node_base_pointer* __nd_ptr = __root_ptr();
     if (__nd != nullptr)
     {
         while (true)
         {
             if (value_comp()(__v, __nd->__value_))
             {
-                if (__nd->__left_ != nullptr)
+                if (__nd->__left_ != nullptr) {
+                    __nd_ptr = _VSTD::addressof(__nd->__left_);
                     __nd = static_cast<__node_pointer>(__nd->__left_);
-                else
-                {
-                    __parent = static_cast<__node_base_pointer>(__nd);
+                } else {
+                    __parent = static_cast<__parent_pointer>(__nd);
                     return __parent->__left_;
                 }
             }
             else if (value_comp()(__nd->__value_, __v))
             {
-                if (__nd->__right_ != nullptr)
+                if (__nd->__right_ != nullptr) {
+                    __nd_ptr = _VSTD::addressof(__nd->__right_);
                     __nd = static_cast<__node_pointer>(__nd->__right_);
-                else
-                {
-                    __parent = static_cast<__node_base_pointer>(__nd);
-                    return __parent->__right_;
+                } else {
+                    __parent = static_cast<__parent_pointer>(__nd);
+                    return __nd->__right_;
                 }
             }
             else
             {
-                __parent = static_cast<__node_base_pointer>(__nd);
-                return __parent;
+                __parent = static_cast<__parent_pointer>(__nd);
+                return *__nd_ptr;
             }
         }
     }
-    __parent = static_cast<__node_base_pointer>(__end_node());
+    __parent = static_cast<__parent_pointer>(__end_node());
     return __parent->__left_;
 }
 
@@ -1928,9 +1994,10 @@
 // If __v exists, set parent to node of __v and return reference to node of __v
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
-typename __tree<_Tp, _Compare, _Allocator>::__node_base::pointer&
+typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&
 __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
-                                                typename __node_base::pointer& __parent,
+                                                __parent_pointer& __parent,
+                                                __node_base_pointer& __dummy,
                                                 const _Key& __v)
 {
     if (__hint == end() || value_comp()(__v, *__hint))  // check before
@@ -1942,13 +2009,13 @@
             // *prev(__hint) < __v < *__hint
             if (__hint.__ptr_->__left_ == nullptr)
             {
-                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
+                __parent = static_cast<__parent_pointer>(__hint.__ptr_);
                 return __parent->__left_;
             }
             else
             {
-                __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
-                return __parent->__right_;
+                __parent = static_cast<__parent_pointer>(__prior.__ptr_);
+                return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_;
             }
         }
         // __v <= *prev(__hint)
@@ -1961,14 +2028,14 @@
         if (__next == end() || value_comp()(__v, *__next))
         {
             // *__hint < __v < *_VSTD::next(__hint)
-            if (__hint.__ptr_->__right_ == nullptr)
+            if (__hint.__get_np()->__right_ == nullptr)
             {
-                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
-                return __parent->__right_;
+                __parent = static_cast<__parent_pointer>(__hint.__ptr_);
+                return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_;
             }
             else
             {
-                __parent = static_cast<__node_base_pointer>(__next.__ptr_);
+                __parent = static_cast<__parent_pointer>(__next.__ptr_);
                 return __parent->__left_;
             }
         }
@@ -1976,15 +2043,16 @@
         return __find_equal(__parent, __v);
     }
     // else __v == *__hint
-    __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
-    return __parent;
+    __parent = static_cast<__parent_pointer>(__hint.__ptr_);
+    __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
+    return __dummy;
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 void
-__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__node_base_pointer __parent,
+__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer     __parent,
                                                     __node_base_pointer& __child,
-                                                    __node_base_pointer __new_node)
+                                                    __node_base_pointer  __new_node)
 {
     __new_node->__left_   = nullptr;
     __new_node->__right_  = nullptr;
@@ -1992,7 +2060,7 @@
     // __new_node->__is_black_ is initialized in __tree_balance_after_insert
     __child = __new_node;
     if (__begin_node()->__left_ != nullptr)
-        __begin_node() = static_cast<__node_pointer>(__begin_node()->__left_);
+        __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
     __tree_balance_after_insert(__end_node()->__left_, __child);
     ++size();
 }
@@ -2009,7 +2077,7 @@
 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
 #endif
 {
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
     __node_base_pointer& __child = __find_equal(__parent, __k);
     __node_pointer __r = static_cast<__node_pointer>(__child);
     bool __inserted = false;
@@ -2042,8 +2110,9 @@
     const_iterator __p, _Key const& __k, _Args& __args)
 #endif
 {
-    __node_base_pointer __parent;
-    __node_base_pointer& __child = __find_equal(__p, __parent, __k);
+    __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);
     if (__child == nullptr)
     {
@@ -2082,7 +2151,7 @@
 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args)
 {
     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
     __node_base_pointer& __child = __find_equal(__parent, __h->__value_);
     __node_pointer __r = static_cast<__node_pointer>(__child);
     bool __inserted = false;
@@ -2101,8 +2170,9 @@
 __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args)
 {
     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
-    __node_base_pointer __parent;
-    __node_base_pointer& __child = __find_equal(__p, __parent, __h->__value_);
+    __parent_pointer __parent;
+    __node_base_pointer __dummy;
+    __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_);
     __node_pointer __r = static_cast<__node_pointer>(__child);
     if (__child == nullptr)
     {
@@ -2118,7 +2188,7 @@
 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args)
 {
     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_));
     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
     return iterator(static_cast<__node_pointer>(__h.release()));
@@ -2131,7 +2201,7 @@
                                                         _Args&&... __args)
 {
     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_));
     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
     return iterator(static_cast<__node_pointer>(__h.release()));
@@ -2158,7 +2228,7 @@
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const __container_value_type& __v)
 {
-    __node_base_pointer __parent;
+    __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()));
@@ -2169,7 +2239,7 @@
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const __container_value_type& __v)
 {
-    __node_base_pointer __parent;
+    __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()));
@@ -2181,7 +2251,7 @@
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd)
 {
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
     __node_base_pointer& __child = __find_equal(__parent, __nd->__value_);
     __node_pointer __r = static_cast<__node_pointer>(__child);
     bool __inserted = false;
@@ -2199,7 +2269,8 @@
 __tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p,
                                                         __node_pointer __nd)
 {
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
+    __node_base_pointer __dummy;
     __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_);
     __node_pointer __r = static_cast<__node_pointer>(__child);
     if (__child == nullptr)
@@ -2214,7 +2285,7 @@
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd)
 {
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
     __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_));
     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
     return iterator(__nd);
@@ -2225,7 +2296,7 @@
 __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
                                                        __node_pointer __nd)
 {
-    __node_base_pointer __parent;
+    __parent_pointer __parent;
     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
     return iterator(__nd);
@@ -2235,10 +2306,10 @@
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
 {
-    __node_pointer __np = __p.__ptr_;
-    iterator __r(__np);
+    __node_pointer __np = __p.__get_np();
+    iterator __r(__p.__ptr_);
     ++__r;
-    if (__begin_node() == __np)
+    if (__begin_node() == __p.__ptr_)
         __begin_node() = __r.__ptr_;
     --size();
     __node_allocator& __na = __node_alloc();
@@ -2310,13 +2381,11 @@
 typename __tree<_Tp, _Compare, _Allocator>::size_type
 __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
 {
-    __node_pointer __result = __end_node();
     __node_pointer __rt = __root();
     while (__rt != nullptr)
     {
         if (value_comp()(__k, __rt->__value_))
         {
-            __result = __rt;
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
@@ -2332,20 +2401,20 @@
 typename __tree<_Tp, _Compare, _Allocator>::size_type
 __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const
 {
-    __node_pointer __result = __end_node();
+    __iter_pointer __result = __end_node();
     __node_pointer __rt = __root();
     while (__rt != nullptr)
     {
         if (value_comp()(__k, __rt->__value_))
         {
-            __result = __rt;
+            __result = static_cast<__iter_pointer>(__rt);
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
             __rt = static_cast<__node_pointer>(__rt->__right_);
         else
             return _VSTD::distance(
-                __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
+                __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
                 __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)
             );
     }
@@ -2357,13 +2426,13 @@
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
                                                  __node_pointer __root,
-                                                 __node_pointer __result)
+                                                 __iter_pointer __result)
 {
     while (__root != nullptr)
     {
         if (!value_comp()(__root->__value_, __v))
         {
-            __result = __root;
+            __result = static_cast<__iter_pointer>(__root);
             __root = static_cast<__node_pointer>(__root->__left_);
         }
         else
@@ -2377,13 +2446,13 @@
 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
 __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v,
                                                  __node_pointer __root,
-                                                 __node_pointer __result) const
+                                                 __iter_pointer __result) const
 {
     while (__root != nullptr)
     {
         if (!value_comp()(__root->__value_, __v))
         {
-            __result = __root;
+            __result = static_cast<__iter_pointer>(__root);
             __root = static_cast<__node_pointer>(__root->__left_);
         }
         else
@@ -2397,13 +2466,13 @@
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
                                                  __node_pointer __root,
-                                                 __node_pointer __result)
+                                                 __iter_pointer __result)
 {
     while (__root != nullptr)
     {
         if (value_comp()(__v, __root->__value_))
         {
-            __result = __root;
+            __result = static_cast<__iter_pointer>(__root);
             __root = static_cast<__node_pointer>(__root->__left_);
         }
         else
@@ -2417,13 +2486,13 @@
 typename __tree<_Tp, _Compare, _Allocator>::const_iterator
 __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v,
                                                  __node_pointer __root,
-                                                 __node_pointer __result) const
+                                                 __iter_pointer __result) const
 {
     while (__root != nullptr)
     {
         if (value_comp()(__v, __root->__value_))
         {
-            __result = __root;
+            __result = static_cast<__iter_pointer>(__root);
             __root = static_cast<__node_pointer>(__root->__left_);
         }
         else
@@ -2439,13 +2508,13 @@
 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k)
 {
     typedef pair<iterator, iterator> _Pp;
-    __node_pointer __result = __end_node();
+    __iter_pointer __result = __end_node();
     __node_pointer __rt = __root();
     while (__rt != nullptr)
     {
         if (value_comp()(__k, __rt->__value_))
         {
-            __result = __rt;
+            __result = static_cast<__iter_pointer>(__rt);
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
@@ -2454,7 +2523,7 @@
             return _Pp(iterator(__rt),
                       iterator(
                           __rt->__right_ != nullptr ?
-                              static_cast<__node_pointer>(__tree_min(__rt->__right_))
+                              static_cast<__iter_pointer>(__tree_min(__rt->__right_))
                             : __result));
     }
     return _Pp(iterator(__result), iterator(__result));
@@ -2467,13 +2536,13 @@
 __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const
 {
     typedef pair<const_iterator, const_iterator> _Pp;
-    __node_pointer __result = __end_node();
+    __iter_pointer __result = __end_node();
     __node_pointer __rt = __root();
     while (__rt != nullptr)
     {
         if (value_comp()(__k, __rt->__value_))
         {
-            __result = __rt;
+            __result = static_cast<__iter_pointer>(__rt);
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
@@ -2482,7 +2551,7 @@
             return _Pp(const_iterator(__rt),
                       const_iterator(
                           __rt->__right_ != nullptr ?
-                              static_cast<__node_pointer>(__tree_min(__rt->__right_))
+                              static_cast<__iter_pointer>(__tree_min(__rt->__right_))
                             : __result));
     }
     return _Pp(const_iterator(__result), const_iterator(__result));
@@ -2495,19 +2564,19 @@
 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k)
 {
     typedef pair<iterator, iterator> _Pp;
-    __node_pointer __result = __end_node();
+    __iter_pointer __result = __end_node();
     __node_pointer __rt = __root();
     while (__rt != nullptr)
     {
         if (value_comp()(__k, __rt->__value_))
         {
-            __result = __rt;
+            __result = static_cast<__iter_pointer>(__rt);
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
             __rt = static_cast<__node_pointer>(__rt->__right_);
         else
-            return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
+            return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
     }
     return _Pp(iterator(__result), iterator(__result));
@@ -2520,19 +2589,19 @@
 __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const
 {
     typedef pair<const_iterator, const_iterator> _Pp;
-    __node_pointer __result = __end_node();
+    __iter_pointer __result = __end_node();
     __node_pointer __rt = __root();
     while (__rt != nullptr)
     {
         if (value_comp()(__k, __rt->__value_))
         {
-            __result = __rt;
+            __result = static_cast<__iter_pointer>(__rt);
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
             __rt = static_cast<__node_pointer>(__rt->__right_);
         else
-            return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), __rt),
+            return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)),
                       __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result));
     }
     return _Pp(const_iterator(__result), const_iterator(__result));
@@ -2542,13 +2611,13 @@
 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
 __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
 {
-    __node_pointer __np = __p.__ptr_;
-    if (__begin_node() == __np)
+    __node_pointer __np = __p.__get_np();
+    if (__begin_node() == __p.__ptr_)
     {
         if (__np->__right_ != nullptr)
-            __begin_node() = static_cast<__node_pointer>(__np->__right_);
+            __begin_node() = static_cast<__iter_pointer>(__np->__right_);
         else
-            __begin_node() = static_cast<__node_pointer>(__np->__parent_);
+            __begin_node() = static_cast<__iter_pointer>(__np->__parent_);
     }
     --size();
     __tree_remove(__end_node()->__left_,