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
diff --git a/include/__tree b/include/__tree
index ed23d56..4c00ef8 100644
--- a/include/__tree
+++ b/include/__tree
@@ -1151,7 +1151,7 @@
pair<iterator, bool>
__emplace_unique_key_args(_Key const&, _Args&&... __args);
template <class _Key, class ..._Args>
- iterator
+ pair<iterator, bool>
__emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
template <class... _Args>
@@ -1225,7 +1225,7 @@
>::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
return __emplace_hint_unique_key_args(__p, __f,
_VSTD::forward<_First>(__f),
- _VSTD::forward<_Second>(__s));
+ _VSTD::forward<_Second>(__s)).first;
}
template <class... _Args>
@@ -1245,14 +1245,14 @@
_LIBCPP_INLINE_VISIBILITY
iterator
__emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
- return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x));
+ return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first;
}
template <class _Pp>
_LIBCPP_INLINE_VISIBILITY
iterator
__emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
- return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x));
+ return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first;
}
#else
@@ -1261,7 +1261,7 @@
pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args);
template <class _Key, class _Args>
_LIBCPP_INLINE_VISIBILITY
- iterator __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&);
+ pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&);
#endif
_LIBCPP_INLINE_VISIBILITY
@@ -1271,7 +1271,7 @@
_LIBCPP_INLINE_VISIBILITY
iterator __insert_unique(const_iterator __p, const __container_value_type& __v) {
- return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v);
+ return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v).first;
}
#ifdef _LIBCPP_CXX03_LANG
@@ -1287,7 +1287,7 @@
_LIBCPP_INLINE_VISIBILITY
iterator __insert_unique(const_iterator __p, __container_value_type&& __v) {
- return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v));
+ return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)).first;
}
template <class _Vp, class = typename enable_if<
@@ -2147,17 +2147,16 @@
return pair<iterator, bool>(iterator(__r), __inserted);
}
-
#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Compare, class _Allocator>
template <class _Key, class... _Args>
-typename __tree<_Tp, _Compare, _Allocator>::iterator
+pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
const_iterator __p, _Key const& __k, _Args&&... __args)
#else
template <class _Tp, class _Compare, class _Allocator>
template <class _Key, class _Args>
-typename __tree<_Tp, _Compare, _Allocator>::iterator
+pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
const_iterator __p, _Key const& __k, _Args& __args)
#endif
@@ -2166,6 +2165,7 @@
__node_base_pointer __dummy;
__node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
__node_pointer __r = static_cast<__node_pointer>(__child);
+ bool __inserted = false;
if (__child == nullptr)
{
#ifndef _LIBCPP_CXX03_LANG
@@ -2175,11 +2175,11 @@
#endif
__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
__r = __h.release();
+ __inserted = true;
}
- return iterator(__r);
+ return pair<iterator, bool>(iterator(__r), __inserted);
}
-
#ifndef _LIBCPP_CXX03_LANG
template <class _Tp, class _Compare, class _Allocator>