https://gcc.gnu.org/g:e16d44a8402646546ae0bc05c9f103ec90eae0b2 commit e16d44a8402646546ae0bc05c9f103ec90eae0b2 Author: François Dumont 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 + std::pair + 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 __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 - pair - 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 + try_emplace(const key_type& __k, _Args&&... __args) + { + return _M_h.try_emplace(cend(), __k, std::forward<_Args>(__args)...); + } // move-capable overload template - pair - 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 + 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 - 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 - 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 - pair - 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 + 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 - pair - 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 + 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 - 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 - 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 //@{