{"id":2226226,"url":"http://patchwork.ozlabs.org/api/patches/2226226/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.11@forge-stage.sourceware.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/projects/17/?format=json","name":"GNU Compiler Collection","link_name":"gcc","list_id":"gcc-patches.gcc.gnu.org","list_email":"gcc-patches@gcc.gnu.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"<bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.11@forge-stage.sourceware.org>","list_archive_url":null,"date":"2026-04-22T10:25:20","name":"[v1,11/12] libstdc++: Simplify _Hashtable merge functions","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"de48fa79d944bb95dc6cf3ddb5d12e340a2bfd6e","submitter":{"id":93210,"url":"http://patchwork.ozlabs.org/api/people/93210/?format=json","name":"Jonathan Wakely via Sourceware Forge","email":"forge-bot+redi@forge-stage.sourceware.org"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.11@forge-stage.sourceware.org/mbox/","series":[{"id":500966,"url":"http://patchwork.ozlabs.org/api/series/500966/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=500966","date":"2026-04-22T10:25:11","name":"WIP: libstdc++: Refactor hash table code","version":1,"mbox":"http://patchwork.ozlabs.org/series/500966/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2226226/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226226/checks/","tags":{},"related":[],"headers":{"Return-Path":"<gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org>","X-Original-To":["incoming@patchwork.ozlabs.org","gcc-patches@gcc.gnu.org"],"Delivered-To":["patchwork-incoming@legolas.ozlabs.org","gcc-patches@gcc.gnu.org"],"Authentication-Results":["legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)","sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org","sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org","server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39"],"Received":["from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g0wp36MMSz1yCv\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 20:44:27 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 3F748435864C\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 10:44:25 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 142624BB5886\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:26:20 +0000 (GMT)","from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id 4C8B4405AA\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 10:26:15 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 3F748435864C","OpenDKIM Filter v2.11.0 sourceware.org 142624BB5886"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org 142624BB5886","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org 142624BB5886","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776853580; cv=none;\n b=dMfY7x6koHfUVynzClWI1Hfk5v6hlR6144lufuoDMiniWu/nixDgzyeKzk8lrAUVjQffHZD5LmLDfC+MKKouzqnmWEh2nDdqhWv4nJh6uZ5zoanpwQ/K4QYYa3fwjWjr6hV3lWyBTASVIGMM28DKSMCrKRclgagCE2yViYeSOgg=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776853580; c=relaxed/simple;\n bh=ra/QO8dILOwYzQ/YBCV9kVBvCpUhc9eqNeSH6taU7U4=;\n h=From:Date:Subject:To:Message-ID;\n b=jGKGHAw9Tey8LxnjZuwwH0cNW7Te61zwIIMhu0epJlMJ3/CQ4tSmS08obcOgaU6PsY5056FG2tE5vK64JeUWS/xbLHJ/lPfpTr5xX7MTJGl/fHcdCAkZ8HTcnG0lwRU/Hu/gYVysP8EqlOWN9f7+/EEDrINBhSgNGa3rs+0VO0M=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"Jonathan Wakely via Sourceware Forge\n <forge-bot+redi@forge-stage.sourceware.org>","Date":"Wed, 22 Apr 2026 10:25:20 +0000","Subject":"[PATCH v1 11/12] libstdc++: Simplify _Hashtable merge functions","To":"gcc-patches mailing list <gcc-patches@gcc.gnu.org>","Message-ID":"\n <bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.11@forge-stage.sourceware.org>","X-Mailer":"batrachomyomachia","X-Requested-Reviewer":"fdumont","X-Pull-Request-Organization":"gcc","X-Pull-Request-Repository":"gcc-TEST","X-Pull-Request":"https://forge.sourceware.org/gcc/gcc-TEST/pulls/15","References":"\n <bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.0@forge-stage.sourceware.org>","In-Reply-To":"\n <bmm.hhub8n5f78.gcc.gcc-TEST.redi.15.1.0@forge-stage.sourceware.org>","X-Patch-URL":"\n https://forge.sourceware.org/redi/gcc/commit/8e2990aa9f9fa9b7a7bb08c9d7fec6518328d80d","X-BeenThere":"gcc-patches@gcc.gnu.org","X-Mailman-Version":"2.1.30","Precedence":"list","List-Id":"Gcc-patches mailing list <gcc-patches.gcc.gnu.org>","List-Unsubscribe":"<https://gcc.gnu.org/mailman/options/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe>","List-Archive":"<https://gcc.gnu.org/pipermail/gcc-patches/>","List-Post":"<mailto:gcc-patches@gcc.gnu.org>","List-Help":"<mailto:gcc-patches-request@gcc.gnu.org?subject=help>","List-Subscribe":"<https://gcc.gnu.org/mailman/listinfo/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe>","Reply-To":"gcc-patches mailing list <gcc-patches@gcc.gnu.org>, redi@gcc.gnu.org","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"From: Jonathan Wakely <jwakely@redhat.com>\n\nI realised that _M_merge_unique and _M_merge_multi call extract(iter)\nwhich then has to call _M_get_previous_node to iterate through the\nbucket to find the node before the one iter points to. Since the merge\nfunction is already iterating over the entire container, we had the\nprevious node a moment ago. Walking the whole bucket to find it again is\nwasteful. We could just rewrite the loop in terms of node pointers\ninstead of iterators, and then call _M_extract_node directly. However,\nthis is only possible when the source container is the same type as the\ndestination, because otherwise we can't access the source's private\nmembers (_M_before_begin, _M_begin, _M_extract_node etc.)\n\nAdd overloads of _M_merge_unique and _M_merge_multi that work with\nsource containers of the same type, to enable this optimization.\n\nFor both overloads of _M_merge_unique we can also remove the conditional\nmodifications to __n_elt and just consistently decrement it for every\nelement processed. Use a multiplier of one or zero that dictates whether\n__n_elt is passed to _M_insert_unique_node or not. We can also remove\nthe repeated calls to size() and just keep track of the size in a local\nvariable.\n\nAlthough _M_merge_unique and _M_merge_multi should be safe for\n\"self-merge\", i.e. when doing c.merge(c), it's wasteful to search/insert\nevery element when we don't need to do anything. Add 'this == &source'\nchecks to the overloads taking an lvalue of the container's own type.\nBecause those checks aren't needed for the rvalue overloads, change\nthose to call the underlying _M_merge_xxx function directly instead of\ngoing through the lvalue overload that checks the address.\n\nI've also added more extensive tests for better coverage of the new\noverloads added in this commit.\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/hashtable.h (_M_merge_unique): Add overload for\n\tmerging from same type.\n\t(_M_merge_unique<Compatible>): Simplify size tracking. Add\n\tcomment.\n\t(_M_merge_multi): Add overload for merging from same type.\n\t(_M_merge_multi<Compatible>): Add comment.\n\t* include/bits/unordered_map.h (unordered_map::merge): Check for\n\tself-merge in the lvalue overload. Call _M_merge_unique directly\n\tfor the rvalue overload.\n\t(unordered_multimap::merge): Likewise.\n\t* include/bits/unordered_set.h (unordered_set::merge): Likewise.\n\t(unordered_multiset::merge): Likewise.\n\t* testsuite/23_containers/unordered_map/modifiers/merge.cc:\n\tAdd more tests.\n\t* testsuite/23_containers/unordered_multimap/modifiers/merge.cc:\n\tLikewise.\n\t* testsuite/23_containers/unordered_multiset/modifiers/merge.cc:\n\tLikewise.\n\t* testsuite/23_containers/unordered_set/modifiers/merge.cc:\n\tLikewise.\n---\n libstdc++-v3/include/bits/hashtable.h         | 118 ++++++++++++----\n libstdc++-v3/include/bits/unordered_map.h     |  19 ++-\n libstdc++-v3/include/bits/unordered_set.h     |  19 ++-\n .../unordered_map/modifiers/merge.cc          | 130 ++++++++++++++++++\n .../unordered_multimap/modifiers/merge.cc     | 119 ++++++++++++++++\n .../unordered_multiset/modifiers/merge.cc     | 121 ++++++++++++++++\n .../unordered_set/modifiers/merge.cc          | 128 +++++++++++++++++\n 7 files changed, 626 insertions(+), 28 deletions(-)","diff":"diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h\nindex 7b0a684a2d29..aca431ae216f 100644\n--- a/libstdc++-v3/include/bits/hashtable.h\n+++ b/libstdc++-v3/include/bits/hashtable.h\n@@ -1212,6 +1212,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \treturn __nh;\n       }\n \n+      /// Merge from another container of the same type.\n+      void\n+      _M_merge_unique(_Hashtable& __src)\n+      {\n+\t__glibcxx_assert(get_allocator() == __src.get_allocator());\n+\n+\tauto __size = size();\n+\tauto __n_elt = __src.size();\n+\tsize_type __first = 1;\n+\t// For a container of identical type we can use its private members.\n+\tauto __p = static_cast<__node_ptr>(&__src._M_before_begin);\n+\twhile (__n_elt--)\n+\t  {\n+\t    const auto __prev = __p;\n+\t    __p = __p->_M_next();\n+\t    const auto& __node = *__p;\n+\t    const key_type& __k = _ExtractKey{}(__node._M_v());\n+\t    if (__size <= __small_size_threshold())\n+\t      {\n+\t\tauto __n = _M_begin();\n+\t\tfor (; __n; __n = __n->_M_next())\n+\t\t  if (this->_M_key_equals(__k, *__n))\n+\t\t    break;\n+\t\tif (__n)\n+\t\t  continue;\n+\t      }\n+\n+\t    __hash_code __code\n+\t      = _M_src_hash_code(__src.hash_function(), __k, __node);\n+\t    size_type __bkt = _M_bucket_index(__code);\n+\t    if (__size > __small_size_threshold())\n+\t      if (_M_find_node(__bkt, __k, __code) != nullptr)\n+\t\tcontinue;\n+\n+\t    __hash_code __src_code = __src.hash_function()(__k);\n+\t    size_type __src_bkt = __src._M_bucket_index(__src_code);\n+\t    auto __nh = __src._M_extract_node(__src_bkt, __prev);\n+\t    _M_insert_unique_node(__bkt, __code, __nh._M_ptr,\n+\t\t\t\t  __first * __n_elt + 1);\n+\t    __nh.release();\n+\t    __first = 0;\n+\t    ++__size;\n+\t    __p = __prev;\n+\t  }\n+      }\n+\n       /// Merge from a compatible container into one with unique keys.\n       template<typename _Compatible_Hashtable>\n \tvoid\n@@ -1221,46 +1267,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \t      node_type>, \"Node types are compatible\");\n \t  __glibcxx_assert(get_allocator() == __src.get_allocator());\n \n+\t  auto __size = size();\n \t  auto __n_elt = __src.size();\n+\t  size_type __first = 1;\n+\t  // For a compatible container we can only use the public API,\n+\t  // so cbegin(), cend(), hash_function(), and extract(iterator).\n \t  for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)\n \t    {\n+\t      --__n_elt;\n \t      auto __pos = __i++;\n-\t      const size_type __size = size();\n \t      const key_type& __k = _ExtractKey{}(*__pos);\n \t      if (__size <= __small_size_threshold())\n \t\t{\n-\t\t  bool __found = false;\n-\t\t  for (auto __n = _M_begin(); __n; __n = __n->_M_next())\n+\t\t  auto __n = _M_begin();\n+\t\t  for (; __n; __n = __n->_M_next())\n \t\t    if (this->_M_key_equals(__k, *__n))\n-\t\t      {\n-\t\t\t__found = true;\n-\t\t\tbreak;\n-\t\t      }\n-\n-\t\t  if (__found)\n-\t\t    {\n-\t\t      if (__n_elt != 1)\n-\t\t\t--__n_elt;\n-\t\t      continue;\n-\t\t    }\n+\t\t      break;\n+\t\t  if (__n)\n+\t\t    continue;\n \t\t}\n \n \t      __hash_code __code\n \t\t= _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);\n \t      size_type __bkt = _M_bucket_index(__code);\n-\t      if (__size <= __small_size_threshold()\n-\t\t  || _M_find_node(__bkt, __k, __code) == nullptr)\n-\t\t{\n-\t\t  auto __nh = __src.extract(__pos);\n-\t\t  _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);\n-\t\t  __nh.release();\n-\t\t  __n_elt = 1;\n-\t\t}\n-\t      else if (__n_elt != 1)\n-\t\t--__n_elt;\n+\t      if (__size > __small_size_threshold())\n+\t\tif (_M_find_node(__bkt, __k, __code) != nullptr)\n+\t\t  continue;\n+\n+\t      auto __nh = __src.extract(__pos);\n+\t      _M_insert_unique_node(__bkt, __code, __nh._M_ptr,\n+\t\t\t\t    __first * __n_elt + 1);\n+\t      __nh.release();\n+\t      __first = 0;\n+\t      ++__size;\n \t    }\n \t}\n \n+      /// Merge from another container of the same type.\n+      void\n+      _M_merge_multi(_Hashtable& __src)\n+      {\n+\t__glibcxx_assert(get_allocator() == __src.get_allocator());\n+\n+\tif (__src.size() == 0) [[__unlikely__]]\n+\t  return;\n+\n+\t__node_ptr __hint = nullptr;\n+\tthis->reserve(size() + __src.size());\n+\t// For a container of identical type we can use its private members.\n+\tauto __prev = static_cast<__node_ptr>(&__src._M_before_begin);\n+\tdo\n+\t  {\n+\t    const auto& __node = *__prev->_M_next();\n+\t    const key_type& __k = _ExtractKey{}(__node._M_v());\n+\t    __hash_code __code = this->_M_hash_code(__k);\n+\t    size_type __src_bkt = __src._M_bucket_index(__node);\n+\t    auto __nh = __src._M_extract_node(__src_bkt, __prev);\n+\t    __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;\n+\t    __nh.release();\n+\t  }\n+\twhile (__prev->_M_nxt != nullptr);\n+      }\n+\n       /// Merge from a compatible container into one with equivalent keys.\n       template<typename _Compatible_Hashtable>\n \tvoid\n@@ -1272,6 +1340,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION\n \n \t  __node_ptr __hint = nullptr;\n \t  this->reserve(size() + __src.size());\n+\t  // For a compatible container we can only use the public API,\n+\t  // so cbegin(), cend(), hash_function(), and extract(iterator).\n \t  for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)\n \t    {\n \t      auto __pos = __i++;\ndiff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h\nindex 3b472534c660..9bc1cca7e1b4 100644\n--- a/libstdc++-v3/include/bits/unordered_map.h\n+++ b/libstdc++-v3/include/bits/unordered_map.h\n@@ -821,6 +821,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n \tvoid\n \tmerge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)\n \t{\n+\t  if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)\n+\t    if (std::__addressof(__source) == this) [[__unlikely__]]\n+\t      return;\n+\n \t  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;\n \t  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));\n \t}\n@@ -828,7 +832,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n       template<typename _H2, typename _P2>\n \tvoid\n \tmerge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)\n-\t{ merge(__source); }\n+\t{\n+\t  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;\n+\t  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));\n+\t}\n \n       template<typename _H2, typename _P2>\n \tvoid\n@@ -1764,6 +1771,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n \tvoid\n \tmerge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)\n \t{\n+\t  if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)\n+\t    if (std::__addressof(__source) == this) [[__unlikely__]]\n+\t      return;\n+\n \t  using _Merge_helper\n \t    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;\n \t  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));\n@@ -1772,7 +1783,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n       template<typename _H2, typename _P2>\n \tvoid\n \tmerge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)\n-\t{ merge(__source); }\n+\t{\n+\t  using _Merge_helper\n+\t    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;\n+\t  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));\n+\t}\n \n       template<typename _H2, typename _P2>\n \tvoid\ndiff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h\nindex 08dcfa2a9b9a..a76769df9b93 100644\n--- a/libstdc++-v3/include/bits/unordered_set.h\n+++ b/libstdc++-v3/include/bits/unordered_set.h\n@@ -602,6 +602,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n \tvoid\n \tmerge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)\n \t{\n+\t  if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)\n+\t    if (std::__addressof(__source) == this) [[__unlikely__]]\n+\t      return;\n+\n \t  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;\n \t  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));\n \t}\n@@ -609,7 +613,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n       template<typename _H2, typename _P2>\n \tvoid\n \tmerge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)\n-\t{ merge(__source); }\n+\t{\n+\t  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;\n+\t  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));\n+\t}\n \n       template<typename _H2, typename _P2>\n \tvoid\n@@ -1452,6 +1459,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n \tvoid\n \tmerge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)\n \t{\n+\t  if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)\n+\t    if (std::__addressof(__source) == this) [[__unlikely__]]\n+\t      return;\n+\n \t  using _Merge_helper\n \t    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;\n \t  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));\n@@ -1460,7 +1471,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER\n       template<typename _H2, typename _P2>\n \tvoid\n \tmerge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)\n-\t{ merge(__source); }\n+\t{\n+\t  using _Merge_helper\n+\t    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;\n+\t  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));\n+\t}\n \n       template<typename _H2, typename _P2>\n \tvoid\ndiff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc\nindex df9d79ebeaa7..c84ef8cb6f75 100644\n--- a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc\n+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc\n@@ -290,6 +290,133 @@ test06()\n   VERIFY( c2.empty() );\n }\n \n+void\n+test07()\n+{\n+  test_type c1{ {1, 1}, {3, 3}, {5, 5} };\n+  test_type c2{ {2, 2}, {4, 4}, {6, 6} };\n+  const test_type c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+  const test_type c4 = c1;\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  test_type c5 = c3;\n+  c2.merge(c5);\n+  VERIFY( c2 == c3 );\n+  VERIFY( c5 == c3 );\n+\n+  c5.emplace(9, 9);\n+  c2.merge(c5);\n+  VERIFY( c2.size() == c3.size() + 1 );\n+  VERIFY( c5 == c3 );\n+}\n+\n+void\n+test08()\n+{\n+  test_type c1{ {1, 1}, {3, 3}, {5, 5} };\n+  std::unordered_map<int, int, xhash<int>, equal> c2{ {2, 2}, {4, 4}, {6, 6} };\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+  const test_type c4 = c1;\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( equal_elements(c1, c3) );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  auto c5 = c3;\n+  c2.merge(c5);\n+  VERIFY( c2 == c3 );\n+  VERIFY( c5 == c3 );\n+\n+  c5.emplace(9, 9);\n+  c2.merge(c5);\n+  VERIFY( c2.size() == c3.size() + 1 );\n+  VERIFY( c5 == c3 );\n+}\n+\n+void\n+test09()\n+{\n+  struct stateful_hash\n+  {\n+    size_t seed = 0;\n+\n+    auto operator()(const int& i) const noexcept\n+    { return std::hash<int>()(i) + seed; }\n+  };\n+\n+  using map_type = std::unordered_map<int, int, stateful_hash>;\n+  map_type c1({ {1, 1}, {3, 3}, {5, 5} }, 0, stateful_hash{1});\n+  map_type c2({ {2, 2}, {4, 4}, {6, 6} }, 0, stateful_hash{2});\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  test_type c5{ {-1, 1}, {-3, 3}, {-5, 5} };\n+  c2.merge(c5);\n+  VERIFY( c2.size() == 6 );\n+  VERIFY( c5.empty() );\n+  auto c6 = c3;\n+  c6.merge(c2);\n+  VERIFY( c6.size() == 6 );\n+  VERIFY( c2.size() == 3 );\n+}\n+\n int\n main()\n {\n@@ -299,4 +426,7 @@ main()\n   test04();\n   test05();\n   test06();\n+  test07();\n+  test08();\n+  test09();\n }\ndiff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc\nindex 3e2b26380f9a..bf03c4cc34e4 100644\n--- a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc\n+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc\n@@ -105,6 +105,122 @@ test04()\n   VERIFY( c2.empty() );\n }\n \n+void\n+test07()\n+{\n+  test_type c1{ {1, 1}, {3, 3}, {5, 5} };\n+  test_type c2{ {2, 2}, {4, 4}, {6, 6} };\n+  const test_type c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+  const test_type c4 = c1;\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  auto c5 = c4;\n+  c2.merge(c5);\n+  VERIFY( c2.size() == 9 );\n+  VERIFY( c5.empty() );\n+\n+  c5 = c4;\n+  c5.emplace(9, 9);\n+  c2.merge(c5);\n+  VERIFY( c2.size() == 16 );\n+  VERIFY( c5.empty() );\n+}\n+\n+void\n+test08()\n+{\n+  test_type c1{ {1, 1}, {3, 3}, {5, 5} };\n+  std::unordered_map<int, int, hash, equal> c2{ {2, 2}, {4, 4}, {6, 6} };\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+  const test_type c4 = c1;\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+}\n+\n+void\n+test09()\n+{\n+  struct stateful_hash\n+  {\n+    size_t seed = 0;\n+\n+    auto operator()(const int& i) const noexcept\n+    { return std::hash<int>()(i) + seed; }\n+  };\n+\n+  using map_type = std::unordered_multimap<int, int, stateful_hash>;\n+  map_type c1({ {1, 1}, {3, 3}, {5, 5} }, 0, stateful_hash{1});\n+  map_type c2({ {2, 2}, {4, 4}, {6, 6} }, 0, stateful_hash{2});\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  test_type c4{ {-1, 0}, {-3, 0}, {-5, 0} };\n+  c2.merge(c4);\n+  VERIFY( c2.size() == 6 );\n+  VERIFY( c4.empty() );\n+  auto c6 = c3;\n+  c6.merge(c2);\n+  VERIFY( c6.size() == 9 );\n+  VERIFY( c2.size() == 0 );\n+}\n int\n main()\n {\n@@ -112,4 +228,7 @@ main()\n   test02();\n   test03();\n   test04();\n+  test07();\n+  test08();\n+  test09();\n }\ndiff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc\nindex 41f98f282492..291b4866281e 100644\n--- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc\n+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc\n@@ -126,6 +126,124 @@ test05()\n   VERIFY( c2.empty() );\n }\n \n+void\n+test07()\n+{\n+  test_type c1{ 1, 3, 5 };\n+  test_type c2{ 2, 4, 6 };\n+  const test_type c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+  const test_type c4 = c1;\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  auto c5 = c4;\n+  c2.merge(c5);\n+  VERIFY( c2.size() == 9 );\n+  VERIFY( c5.empty() );\n+\n+  c5 = c4;\n+  c5.emplace(9);\n+  c2.merge(c5);\n+  VERIFY( c2.size() == 16 );\n+  VERIFY( c5.empty() );\n+\n+}\n+\n+void\n+test08()\n+{\n+  test_type c1{ 1, 3, 5 };\n+  std::unordered_set<int, hash, equal> c2{ 2, 4, 6 };\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+  const test_type c4 = c1;\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+}\n+\n+void\n+test09()\n+{\n+  struct stateful_hash\n+  {\n+    size_t seed = 0;\n+\n+    auto operator()(const int& i) const noexcept\n+    { return std::hash<int>()(i) + seed; }\n+  };\n+\n+  using set_type = std::unordered_multiset<int, stateful_hash>;\n+  set_type c1({ 1, 3, 5 }, 0, stateful_hash{1});\n+  set_type c2({ 2, 4, 6 }, 0, stateful_hash{2});\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  test_type c4{ -1, -3, -5 };\n+  c2.merge(c4);\n+  VERIFY( c2.size() == 6 );\n+  VERIFY( c4.empty() );\n+  auto c6 = c3;\n+  c6.merge(c2);\n+  VERIFY( c6.size() == 9 );\n+  VERIFY( c2.size() == 0 );\n+}\n+\n int\n main()\n {\n@@ -134,4 +252,7 @@ main()\n   test03();\n   test04();\n   test05();\n+  test07();\n+  test08();\n+  test09();\n }\ndiff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc\nindex 45fe3952ebbb..6cf2c98d4b3e 100644\n--- a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc\n+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc\n@@ -167,6 +167,131 @@ test04()\n   VERIFY( c2.empty() );\n }\n \n+void\n+test07()\n+{\n+  test_type c1{ 1, 3, 5 };\n+  test_type c2{ 2, 4, 6 };\n+  const test_type c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  test_type c4 = c3;\n+  c2.merge(c4);\n+  VERIFY( c2 == c3 );\n+  VERIFY( c4 == c3 );\n+\n+  c4.emplace(9);\n+  c2.merge(c4);\n+  VERIFY( c2.size() == c3.size() + 1 );\n+  VERIFY( c4 == c3 );\n+}\n+\n+void\n+test08()\n+{\n+  test_type c1{ 1, 3, 5 };\n+  std::unordered_set<int, hash, equal> c2{ 2, 4, 6 };\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( equal_elements(c1, c3) );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  auto c4 = c3;\n+  c2.merge(c4);\n+  VERIFY( c2 == c3 );\n+  VERIFY( c4 == c3 );\n+\n+  c4.emplace(9);\n+  c2.merge(c4);\n+  VERIFY( c2.size() == c3.size() + 1 );\n+  VERIFY( c4 == c3 );\n+}\n+\n+void\n+test09()\n+{\n+  struct stateful_hash\n+  {\n+    size_t seed = 0;\n+\n+    auto operator()(const int& i) const noexcept\n+    { return std::hash<int>()(i) + seed; }\n+  };\n+\n+  using set_type = std::unordered_set<int, stateful_hash>;\n+  set_type c1({ 1, 3, 5 }, 0, stateful_hash{1});\n+  set_type c2({ 2, 4, 6 }, 0, stateful_hash{2});\n+  const auto c3 = c2;\n+\n+  c1.merge(c2);\n+  VERIFY( c1.size() == 6 );\n+  VERIFY( c2.empty() );\n+\n+  c2 = c3;\n+  c1.clear();\n+  c1.merge(std::move(c2));\n+  VERIFY( c1 == c3 );\n+  VERIFY( c2.empty() );\n+\n+  c2.merge(std::move(c1));\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c1);\n+  VERIFY( c1.empty() );\n+  VERIFY( c2 == c3 );\n+\n+  c2.merge(c2);\n+  VERIFY( c2 == c3 );\n+\n+  test_type c4{ -1, -3, -5 };\n+  c2.merge(c4);\n+  VERIFY( c2.size() == 6 );\n+  VERIFY( c4.empty() );\n+  auto c6 = c3;\n+  c6.merge(c2);\n+  VERIFY( c6.size() == 6 );\n+  VERIFY( c2.size() == 3 );\n+}\n+\n int\n main()\n {\n@@ -174,4 +299,7 @@ main()\n   test02();\n   test03();\n   test04();\n+  test07();\n+  test08();\n+  test09();\n }\n","prefixes":["v1","11/12"]}