commit 1ba476f9780882419d333f5ac8f415ada8604e12
author Mark de Wever <koraq@xs4all.nl> Sat Sep 19 15:39:09 2020 +0200
committer Mark de Wever <koraq@xs4all.nl> Sat Sep 19 16:28:55 2020 +0200
tree 62aea322311a6accc0ce83788bd5e7d603ce8f30
parent 1a1fc9d855ba8f884e9cd8ba1d916ea4a1b07e7d

Fixes complexity of map insert_or_assign with a hint.

Mitsuru Kariya reported the map operations insert_or_assign with a hint
violates the complexity requirement. The function no longer uses a lower_bound,
which caused the wrong complexity.

Fixes PR38722: [C++17] std::map::insert_or_assign w/ hint violate complexity requirements

Differential Revision: https://reviews.llvm.org/D62779

Cr-Mirrored-From: https://chromium.googlesource.com/external/github.com/llvm/llvm-project
Cr-Mirrored-Commit: d4dd961300588ce7e50625a1947befb45e3a0c42

include/map

diff --git a/include/map b/include/map
index 96409f2..a27002c 100644
--- a/include/map
+++ b/include/map
@@ -1230,7 +1230,7 @@
         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
             _VSTD::piecewise_construct,
             _VSTD::forward_as_tuple(__k),
-            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
     }
 
     template <class... _Args>
@@ -1240,7 +1240,7 @@
         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
             _VSTD::piecewise_construct,
             _VSTD::forward_as_tuple(_VSTD::move(__k)),
-            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
+            _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
     }
 
     template <class _Vp>
@@ -1270,30 +1270,30 @@
     }
 
     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));
-     }
+    _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
+                                                        const key_type& __k,
+                                                        _Vp&& __v) {
+      auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
+          __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v));
+
+      if (!__inserted)
+        __r->__get_value().second = _VSTD::forward<_Vp>(__v);
+
+      return __r;
+    }
 
     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));
-     }
+    _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
+                                                        key_type&& __k,
+                                                        _Vp&& __v) {
+      auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
+          __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
+
+      if (!__inserted)
+        __r->__get_value().second = _VSTD::forward<_Vp>(__v);
+
+      return __r;
+    }
 
 #endif // _LIBCPP_STD_VER > 14