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);
@@ -2510,6 +2518,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
 
Index: libcxx/test/std/containers/associative/map/map.modifiers/insert_or_assign.pass.cpp
===================================================================
--- libcxx/test/std/containers/associative/map/map.modifiers/insert_or_assign.pass.cpp
+++ libcxx/test/std/containers/associative/map/map.modifiers/insert_or_assign.pass.cpp
@@ -155,6 +155,51 @@
         assert(mv2.moved());           // was moved from
         assert(r->first        == 3);  // key
         assert(r->second.get() == 5);  // value
+
+        // wrong hint: begin()
+        Moveable mv3(7, 7.0);
+        r = m.insert_or_assign(m.begin(), 4, std::move(mv3));
+        assert(m.size() == 11);
+        assert(mv3.moved());           // was moved from
+        assert(r->first        == 4);  // key
+        assert(r->second.get() == 7);  // value
+
+        Moveable mv4(9, 9.0);
+        r = m.insert_or_assign(m.begin(), 5, std::move(mv4));
+        assert(m.size() == 12);
+        assert(mv4.moved());           // was moved from
+        assert(r->first        == 5);  // key
+        assert(r->second.get() == 9);  // value
+
+        // wrong hint: end()
+        Moveable mv5(11, 11.0);
+        r = m.insert_or_assign(m.end(), 6, std::move(mv5));
+        assert(m.size() == 12);
+        assert(mv5.moved());           // was moved from
+        assert(r->first        == 6);  // key
+        assert(r->second.get() == 11); // value
+
+        Moveable mv6(13, 13.0);
+        r = m.insert_or_assign(m.end(), 7, std::move(mv6));
+        assert(m.size() == 13);
+        assert(mv6.moved());           // was moved from
+        assert(r->first        == 7);  // key
+        assert(r->second.get() == 13); // value
+
+        // wrong hint: third element
+        Moveable mv7(15, 15.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), 8, std::move(mv7));
+        assert(m.size() == 13);
+        assert(mv7.moved());           // was moved from
+        assert(r->first        == 8);  // key
+        assert(r->second.get() == 15); // value
+
+        Moveable mv8(17, 17.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), 9, std::move(mv8));
+        assert(m.size() == 14);
+        assert(mv8.moved());           // was moved from
+        assert(r->first        == 9);  // key
+        assert(r->second.get() == 17); // value
     }
     { // iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
         typedef std::map<Moveable, Moveable> M;
@@ -182,6 +227,63 @@
         assert(mvkey2.moved());        // was moved from
         assert(r->first.get()  == 3);  // key
         assert(r->second.get() == 5);  // value
+
+        // wrong hint: begin()
+        Moveable mvkey3(6, 6.0);
+        Moveable mv3(8, 8.0);
+        r = m.insert_or_assign(m.begin(), std::move(mvkey3), std::move(mv3));
+        assert(m.size() == 11);
+        assert(mv3.moved());           // was moved from
+        assert(!mvkey3.moved());       // was not moved from
+        assert(r->first == mvkey3);    // key
+        assert(r->second.get() == 8);  // value
+
+        Moveable mvkey4(7, 7.0);
+        Moveable mv4(9, 9.0);
+        r = m.insert_or_assign(m.begin(), std::move(mvkey4), std::move(mv4));
+        assert(m.size() == 12);
+        assert(mv4.moved());           // was moved from
+        assert(mvkey4.moved());        // was moved from
+        assert(r->first.get()  == 7);  // key
+        assert(r->second.get() == 9);  // value
+
+        // wrong hint: end()
+        Moveable mvkey5(8, 8.0);
+        Moveable mv5(10, 10.0);
+        r = m.insert_or_assign(m.end(), std::move(mvkey5), std::move(mv5));
+        assert(m.size() == 12);
+        assert(mv5.moved());           // was moved from
+        assert(!mvkey5.moved());       // was not moved from
+        assert(r->first == mvkey5);    // key
+        assert(r->second.get() == 10); // value
+
+        Moveable mvkey6(9, 9.0);
+        Moveable mv6(11, 11.0);
+        r = m.insert_or_assign(m.end(), std::move(mvkey6), std::move(mv6));
+        assert(m.size() == 13);
+        assert(mv6.moved());           // was moved from
+        assert(mvkey6.moved());        // was moved from
+        assert(r->first.get()  == 9);  // key
+        assert(r->second.get() == 11); // value
+
+        // wrong hint: third element
+        Moveable mvkey7(10, 10.0);
+        Moveable mv7(12, 12.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), std::move(mvkey7), std::move(mv7));
+        assert(m.size() == 13);
+        assert(mv7.moved());           // was moved from
+        assert(!mvkey7.moved());       // was not moved from
+        assert(r->first == mvkey7);    // key
+        assert(r->second.get() == 12); // value
+
+        Moveable mvkey8(11, 11.0);
+        Moveable mv8(13, 13.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), std::move(mvkey8), std::move(mv8));
+        assert(m.size() == 14);
+        assert(mv8.moved());           // was moved from
+        assert(mvkey8.moved());        // was moved from
+        assert(r->first.get()  == 11); // key
+        assert(r->second.get() == 13); // value
     }
 
   return 0;