From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1059) id 070B43947C04; Thu, 11 Jun 2020 12:57:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 070B43947C04 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1591880225; bh=53GLMlB4kao4x0Tlf9MkSCXe8tXXUjLtdMGzC3FPA54=; h=From:To:Subject:Date:From; b=VOKvYBxiQLAuxjygjrA30MrVkSCJIyXrA4Fhorf21szziQvp0x7fPEL+I7bXhvt3B ZP9lMQtREkhoYCPa/YLGze9+z87lVu47oQsaP9rgvkDcfehNeTQYIqmLLoOI/c78wR 6TV+dX6AlOUSJOYi1vN0ItB/7N4SRLJTCfzRlWQI= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit From: Nathan Sidwell To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc/devel/c++-modules] libstdc++: Review unordered_map insert_or_assign/try_emplace (PR 95079) X-Act-Checkin: gcc X-Git-Author: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Git-Refname: refs/heads/devel/c++-modules X-Git-Oldrev: c735929a2503a7d03ac4739bba5b25336bf954c3 X-Git-Newrev: 7688e5e8c4d46102a0cc0b9c25191ac7dde0d285 Message-Id: <20200611125705.070B43947C04@sourceware.org> Date: Thu, 11 Jun 2020 12:57:05 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 11 Jun 2020 12:57:05 -0000 https://gcc.gnu.org/g:7688e5e8c4d46102a0cc0b9c25191ac7dde0d285 commit 7688e5e8c4d46102a0cc0b9c25191ac7dde0d285 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 //@{