Index: libcxx/include/__tree
===================================================================
--- libcxx/include/__tree
+++ libcxx/include/__tree
@@ -1374,6 +1374,14 @@
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(const_iterator);
+
+
+    template <class _Vp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __insert_or_assign_hint(const_iterator __p, key_type const& __k, _Vp&& __v);
+    template <class _Vp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __insert_or_assign_hint(const_iterator __p, key_type&& __k, _Vp&& __v);
 #endif
 
     iterator erase(const_iterator __p);
@@ -2549,6 +2557,49 @@
     }
 }
 
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Vp>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::
+    __insert_or_assign_hint(const_iterator __p, key_type const& __k, _Vp&& __v)
+{
+    __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)
+    {
+        __node_holder __h = __construct_node(__k, _VSTD::forward<_Vp>(__v));
+        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+        __r = __h.release();
+    }
+    else
+        iterator(__r)->__get_value().second = std::forward<_Vp>(__v);
+    return iterator(__r);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Vp>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::
+    __insert_or_assign_hint(const_iterator __p, key_type && __k, _Vp&& __v)
+{
+    __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)
+    {
+        __node_holder __h = __construct_node(_VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v));
+        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+        __r = __h.release();
+    }
+    else
+        iterator(__r)->__get_value().second = std::forward<_Vp>(__v);
+    return iterator(__r);
+}
 #endif  // _LIBCPP_STD_VER > 14
 
 template <class _Tp, class _Compare, class _Allocator>
Index: libcxx/include/map
===================================================================
--- libcxx/include/map
+++ libcxx/include/map
@@ -1270,28 +1270,15 @@
     template <class _Vp>
         _LIBCPP_INLINE_VISIBILITY
         iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
-     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-        {
-            __p->second = _VSTD::forward<_Vp>(__v);
-            return __p;
-        }
-        return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
-     }
-
+    {
+         return __tree_.__insert_or_assign_hint(__h.__i_, __k,  _VSTD::forward<_Vp>(__v));
+    }
     template <class _Vp>
         _LIBCPP_INLINE_VISIBILITY
         iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
-     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-        {
-            __p->second = _VSTD::forward<_Vp>(__v);
-            return __p;
-        }
-        return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
-     }
+    {
+       return __tree_.__insert_or_assign_hint(__h.__i_, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
+    }
 
 #endif // _LIBCPP_STD_VER > 14