[gcc r11-719] libstdc++: Review unordered_map insert_or_assign/try_emplace (PR 95079)
Franथईois Dumont
fdumont@gcc.gnu.org
Fri May 29 11:13:15 GMT 2020
https://gcc.gnu.org/g:7688e5e8c4d46102a0cc0b9c25191ac7dde0d285
commit r11-719-g7688e5e8c4d46102a0cc0b9c25191ac7dde0d285
Author: François Dumont <fdumont@gcc.gnu.org>
Date: Sun May 24 12:04:38 2020 +0200
libstdc++: Review unordered_map insert_or_assign/try_emplace (PR 95079)
Those methods are making a double lookup in case of insertion, they can
perform only one.
PR libstdc++/95079
* include/bits/hashtable_policy.h (_Insert_base<>::try_emplace): New.
* include/bits/unordered_map.h (unordered_map<>::try_emplace): Adapt.
(unordered_map<>::insert_or_assign): Adapt.
Diff:
---
libstdc++-v3/include/bits/hashtable_policy.h | 22 ++++
libstdc++-v3/include/bits/unordered_map.h | 172 ++++++++++-----------------
2 files changed, 82 insertions(+), 112 deletions(-)
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index ef120134914..33f3f143bd0 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -848,6 +848,28 @@ namespace __detail
return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
}
+ template<typename _KType, typename... _Args>
+ std::pair<iterator, bool>
+ try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
+ {
+ __hashtable& __h = _M_conjure_hashtable();
+ auto __code = __h._M_hash_code(__k);
+ std::size_t __bkt = __h._M_bucket_index(__k, __code);
+ if (__node_type* __node = __h._M_find_node(__bkt, __k, __code))
+ return { iterator(__node), false };
+
+ typename __hashtable::_Scoped_node __node {
+ &__h,
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_KType>(__k)),
+ std::forward_as_tuple(std::forward<_Args>(__args)...)
+ };
+ auto __it
+ = __h._M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+ __node._M_node = nullptr;
+ return { __it, true };
+ }
+
void
insert(initializer_list<value_type> __l)
{ this->insert(__l.begin(), __l.end()); }
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 0071d62e462..33f632ddb79 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -466,39 +466,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* Insertion requires amortized constant time.
*/
template <typename... _Args>
- pair<iterator, bool>
- try_emplace(const key_type& __k, _Args&&... __args)
- {
- iterator __i = find(__k);
- if (__i == end())
- {
- __i = emplace(std::piecewise_construct,
- std::forward_as_tuple(__k),
- std::forward_as_tuple(
- std::forward<_Args>(__args)...))
- .first;
- return {__i, true};
- }
- return {__i, false};
- }
+ pair<iterator, bool>
+ try_emplace(const key_type& __k, _Args&&... __args)
+ {
+ return _M_h.try_emplace(cend(), __k, std::forward<_Args>(__args)...);
+ }
// move-capable overload
template <typename... _Args>
- pair<iterator, bool>
- try_emplace(key_type&& __k, _Args&&... __args)
- {
- iterator __i = find(__k);
- if (__i == end())
- {
- __i = emplace(std::piecewise_construct,
- std::forward_as_tuple(std::move(__k)),
- std::forward_as_tuple(
- std::forward<_Args>(__args)...))
- .first;
- return {__i, true};
- }
- return {__i, false};
- }
+ pair<iterator, bool>
+ try_emplace(key_type&& __k, _Args&&... __args)
+ {
+ return _M_h.try_emplace(cend(), std::move(__k),
+ std::forward<_Args>(__args)...);
+ }
/**
* @brief Attempts to build and insert a std::pair into the
@@ -529,32 +510,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* Insertion requires amortized constant time.
*/
template <typename... _Args>
- iterator
- try_emplace(const_iterator __hint, const key_type& __k,
- _Args&&... __args)
- {
- iterator __i = find(__k);
- if (__i == end())
- __i = emplace_hint(__hint, std::piecewise_construct,
- std::forward_as_tuple(__k),
- std::forward_as_tuple(
- std::forward<_Args>(__args)...));
- return __i;
- }
+ iterator
+ try_emplace(const_iterator __hint, const key_type& __k,
+ _Args&&... __args)
+ {
+ return _M_h.try_emplace(__hint, __k,
+ std::forward<_Args>(__args)...).first;
+ }
// move-capable overload
template <typename... _Args>
- iterator
- try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
- {
- iterator __i = find(__k);
- if (__i == end())
- __i = emplace_hint(__hint, std::piecewise_construct,
- std::forward_as_tuple(std::move(__k)),
- std::forward_as_tuple(
- std::forward<_Args>(__args)...));
- return __i;
- }
+ iterator
+ try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
+ {
+ return _M_h.try_emplace(__hint, std::move(__k),
+ std::forward<_Args>(__args)...).first;
+ }
#endif // C++17
//@{
@@ -678,39 +649,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* Insertion requires amortized constant time.
*/
template <typename _Obj>
- pair<iterator, bool>
- insert_or_assign(const key_type& __k, _Obj&& __obj)
- {
- iterator __i = find(__k);
- if (__i == end())
- {
- __i = emplace(std::piecewise_construct,
- std::forward_as_tuple(__k),
- std::forward_as_tuple(std::forward<_Obj>(__obj)))
- .first;
- return {__i, true};
- }
- (*__i).second = std::forward<_Obj>(__obj);
- return {__i, false};
- }
+ pair<iterator, bool>
+ insert_or_assign(const key_type& __k, _Obj&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(cend(), __k,
+ std::forward<_Obj>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Obj>(__obj);
+ return __ret;
+ }
// move-capable overload
template <typename _Obj>
- pair<iterator, bool>
- insert_or_assign(key_type&& __k, _Obj&& __obj)
- {
- iterator __i = find(__k);
- if (__i == end())
- {
- __i = emplace(std::piecewise_construct,
- std::forward_as_tuple(std::move(__k)),
- std::forward_as_tuple(std::forward<_Obj>(__obj)))
- .first;
- return {__i, true};
- }
- (*__i).second = std::forward<_Obj>(__obj);
- return {__i, false};
- }
+ pair<iterator, bool>
+ insert_or_assign(key_type&& __k, _Obj&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(cend(), std::move(__k),
+ std::forward<_Obj>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Obj>(__obj);
+ return __ret;
+ }
/**
* @brief Attempts to insert a std::pair into the %unordered_map.
@@ -739,38 +698,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* Insertion requires amortized constant time.
*/
template <typename _Obj>
- iterator
- insert_or_assign(const_iterator __hint, const key_type& __k,
- _Obj&& __obj)
- {
- iterator __i = find(__k);
- if (__i == end())
- {
- return emplace_hint(__hint, std::piecewise_construct,
- std::forward_as_tuple(__k),
- std::forward_as_tuple(
- std::forward<_Obj>(__obj)));
- }
- (*__i).second = std::forward<_Obj>(__obj);
- return __i;
- }
+ iterator
+ insert_or_assign(const_iterator __hint, const key_type& __k,
+ _Obj&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(__hint, __k, std::forward<_Obj>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Obj>(__obj);
+ return __ret.first;
+ }
// move-capable overload
template <typename _Obj>
- iterator
- insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
- {
- iterator __i = find(__k);
- if (__i == end())
- {
- return emplace_hint(__hint, std::piecewise_construct,
- std::forward_as_tuple(std::move(__k)),
- std::forward_as_tuple(
- std::forward<_Obj>(__obj)));
- }
- (*__i).second = std::forward<_Obj>(__obj);
- return __i;
- }
+ iterator
+ insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(__hint, std::move(__k),
+ std::forward<_Obj>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Obj>(__obj);
+ return __ret.first;
+ }
#endif
//@{
More information about the Libstdc++-cvs
mailing list