public inbox for libstdc++-cvs@sourceware.org help / color / mirror / Atom feed
From: Ian Lance Taylor <ian@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc/devel/gccgo] libstdc++: Review unordered_map insert_or_assign/try_emplace (PR 95079) Date: Sun, 12 Jul 2020 18:44:13 +0000 (GMT) [thread overview] Message-ID: <20200712184413.EBDE83875476@sourceware.org> (raw) [-- Warning: decoded text below may be mangled, UTF-8 assumed --] [-- Attachment #1: Type: text/plain; charset="us-ascii", Size: 9486 bytes --] https://gcc.gnu.org/g:7688e5e8c4d46102a0cc0b9c25191ac7dde0d285 commit 7688e5e8c4d46102a0cc0b9c25191ac7dde0d285 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 //@{
reply other threads:[~2020-07-12 18:44 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20200712184413.EBDE83875476@sourceware.org \ --to=ian@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ --cc=libstdc++-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).