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.

1 files changed, 22 insertions, 0 deletions

diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc
index 1ed2ce234a1..07b8a344169 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc
@@ -17,6 +17,7 @@
 
 // { dg-do run { target c++17 } }
 
+#include <string>
 #include <unordered_set>
 #include <algorithm>
 #include <testsuite_hooks.h>
@@ -105,6 +106,26 @@ test04()
   VERIFY( c2.empty() );
 }
 
+void
+test05()
+{
+  const std::unordered_multiset<std::string> c0{ "abcd", "abcd", "efgh", "efgh", "ijkl", "ijkl" };
+  std::unordered_multiset<std::string> c1 = c0;
+  std::unordered_set<std::string> c2( c0.begin(), c0.end() );
+
+  c1.merge(c2);
+  VERIFY( c1.size() == (1.5 * c0.size()) );
+  for (auto& i : c1)
+    VERIFY( c1.count(i) == (1.5 * c0.count(i)) );
+  VERIFY( c2.empty() );
+
+  c1.clear();
+  c2.insert( c0.begin(), c0.end() );
+  c1.merge(std::move(c2));
+  VERIFY( c1.size() == (0.5 * c0.size()) );
+  VERIFY( c2.empty() );
+}
+
 int
 main()
 {
@@ -112,4 +133,5 @@ main()
   test02();
   test03();
   test04();
+  test05();
 }