From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2100) id D61D93850418; Sat, 22 Aug 2020 21:43:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D61D93850418 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1598132581; bh=bJRRIjqv22TKlXItx4/7YfnwYQw9HclADs1fJQ1G6us=; h=From:To:Subject:Date:From; b=ZQ31MK+ZArTLJwgd3Z6O+PUP6L04/xEWP5nXPTHYq4uUQ1QY1ar25gYQab/eGtkRG 7zirbo//EWlKtJ1LoqQKP49TjS0AJTEoHwjIdj1pBTL1W+r2kCT6ptWLN9HfogOzry 0hIZsW6L32+KE7I0gW2LIAW8eEgi7pwSLu/ZXaiw= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit From: Giuliano Belinassi To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc/devel/autopar_devel] 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/autopar_devel X-Git-Oldrev: 5b98b21b909fa655e37de78afa805b2e584df166 X-Git-Newrev: e16d44a8402646546ae0bc05c9f103ec90eae0b2 Message-Id: <20200822214301.D61D93850418@sourceware.org> Date: Sat, 22 Aug 2020 21:43:01 +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: Sat, 22 Aug 2020 21:43:01 -0000 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 //@{