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;