diff options
| author | François Dumont <fdumont@gcc.gnu.org> | 2021-10-25 15:59:35 +0200 |
|---|---|---|
| committer | François Dumont <fdumont@gcc.gnu.org> | 2021-11-15 18:52:07 +0100 |
| commit | d10b863fa3de8b202aadbdef1b012188ab0868d8 (patch) | |
| tree | 6f4311493baaa5509b1c2abe64dee5874baa1fe7 /libstdc++-v3/include/bits/hashtable.h | |
| parent | f861ed8b29a5eb6164d1ddbcfbb6232dddae713f (diff) | |
| download | gcc-d10b863fa3de8b202aadbdef1b012188ab0868d8.zip gcc-d10b863fa3de8b202aadbdef1b012188ab0868d8.tar.gz gcc-d10b863fa3de8b202aadbdef1b012188ab0868d8.tar.bz2 | |
libstdc++: Unordered containers merge re-use hash code
When merging 2 unordered containers with same hasher we can re-use the hash code from
the cache if any.
Also in the context of the merge operation on multi-container use previous insert iterator as a hint
for the next insert.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h:
(_Hash_code_base<>::_M_hash_code(const _Hash&, const _Hash_node_value<_Value, true>&)): New.
(_Hash_code_base<>::_M_hash_code<_H2>(const _H2&, const _Hash_node_value<>&)): New.
* include/bits/hashtable.h (_Hashtable<>::_M_merge_unique): Use latter.
(_Hashtable<>::_M_merge_multi): Likewise.
* testsuite/23_containers/unordered_multiset/modifiers/merge.cc (test05): New test.
* testsuite/23_containers/unordered_set/modifiers/merge.cc (test04): New test.
Diffstat (limited to 'libstdc++-v3/include/bits/hashtable.h')
| -rw-r--r-- | libstdc++-v3/include/bits/hashtable.h | 10 |
1 files changed, 6 insertions, 4 deletions
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 0e949d7..6e2d4c1 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1076,7 +1076,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { auto __pos = __i++; const key_type& __k = _ExtractKey{}(*__pos); - __hash_code __code = this->_M_hash_code(__k); + __hash_code __code + = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); size_type __bkt = _M_bucket_index(__code); if (_M_find_node(__bkt, __k, __code) == nullptr) { @@ -1099,14 +1100,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + __node_ptr __hint = nullptr; this->reserve(size() + __src.size()); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; - const key_type& __k = _ExtractKey{}(*__pos); - __hash_code __code = this->_M_hash_code(__k); + __hash_code __code + = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); auto __nh = __src.extract(__pos); - _M_insert_multi_node(nullptr, __code, __nh._M_ptr); + __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; __nh._M_ptr = nullptr; } } |