[libc++] Refactor key extraction for __hash_table and __tree (#154512)

This patch replaces `__can_extract_key` with an overload set to try to
extract the key. This simplifies the code, since we don't need to have
separate overload sets for the unordered and associative containers. It
also allows extending the set of extraction cases more easily, since we
have a single place to define how the key is extracted.

15 files changed, 308 insertions, 352 deletions

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index c6b87a3..6fd1641 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -792,7 +792,6 @@ set(files
   __type_traits/aligned_storage.h
   __type_traits/aligned_union.h
   __type_traits/alignment_of.h
-  __type_traits/can_extract_key.h
   __type_traits/common_reference.h
   __type_traits/common_type.h
   __type_traits/conditional.h
@@ -933,6 +932,7 @@ set(files
   __utility/small_buffer.h
   __utility/swap.h
   __utility/to_underlying.h
+  __utility/try_key_extraction.h
   __utility/unreachable.h
   __variant/monostate.h
   __vector/comparison.h
diff --git a/libcxx/include/__fwd/tuple.h b/libcxx/include/__fwd/tuple.h
index 39ed94d..b3cac4e 100644
--- a/libcxx/include/__fwd/tuple.h
+++ b/libcxx/include/__fwd/tuple.h
@@ -26,6 +26,12 @@ struct tuple_element;
 template <class...>
 class tuple;
 
+template <class>
+inline const bool __is_tuple_v = false;
+
+template <class... _Tp>
+inline const bool __is_tuple_v<tuple<_Tp...>> = true;
+
 template <size_t _Ip, class... _Tp>
 struct tuple_element<_Ip, tuple<_Tp...> > {
   using type _LIBCPP_NODEBUG = __type_pack_element<_Ip, _Tp...>;
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index f0f335a..91f660d 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -29,7 +29,6 @@
 #include <__memory/swap_allocator.h>
 #include <__memory/unique_ptr.h>
 #include <__new/launder.h>
-#include <__type_traits/can_extract_key.h>
 #include <__type_traits/copy_cvref.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/invoke.h>
@@ -46,6 +45,7 @@
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <__utility/swap.h>
+#include <__utility/try_key_extraction.h>
 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -797,40 +797,66 @@ public:
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
-  template <class _Key, class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
-
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
-    return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
-  }
-
-  template <class _First,
-            class _Second,
-            __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
-    return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
-  }
-
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
-    return __emplace_unique_impl(std::forward<_Args>(__args)...);
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
-    return __emplace_unique_impl(std::forward<_Pp>(__x));
-  }
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
-    return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
-  }
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
-    return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
+    return std::__try_key_extraction<key_type>(
+        [this](const key_type& __key, _Args&&... __args2) {
+          size_t __hash   = hash_function()(__key);
+          size_type __bc  = bucket_count();
+          bool __inserted = false;
+          __next_pointer __nd;
+          size_t __chash;
+          if (__bc != 0) {
+            __chash = std::__constrain_hash(__hash, __bc);
+            __nd    = __bucket_list_[__chash];
+            if (__nd != nullptr) {
+              for (__nd = __nd->__next_;
+                   __nd != nullptr &&
+                   (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
+                   __nd = __nd->__next_) {
+                if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __key))
+                  goto __done;
+              }
+            }
+          }
+          {
+            __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args2)...);
+            if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
+              __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
+                                                  size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
+              __bc    = bucket_count();
+              __chash = std::__constrain_hash(__hash, __bc);
+            }
+            // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+            __next_pointer __pn = __bucket_list_[__chash];
+            if (__pn == nullptr) {
+              __pn          = __first_node_.__ptr();
+              __h->__next_  = __pn->__next_;
+              __pn->__next_ = __h.get()->__ptr();
+              // fix up __bucket_list_
+              __bucket_list_[__chash] = __pn;
+              if (__h->__next_ != nullptr)
+                __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
+            } else {
+              __h->__next_  = __pn->__next_;
+              __pn->__next_ = static_cast<__next_pointer>(__h.get());
+            }
+            __nd = static_cast<__next_pointer>(__h.release());
+            // increment size
+            ++size();
+            __inserted = true;
+          }
+        __done:
+          return pair<iterator, bool>(iterator(__nd), __inserted);
+        },
+        [this](_Args&&... __args2) {
+          __node_holder __h        = __construct_node(std::forward<_Args>(__args2)...);
+          pair<iterator, bool> __r = __node_insert_unique(__h.get());
+          if (__r.second)
+            __h.release();
+          return __r;
+        },
+        std::forward<_Args>(__args)...);
   }
 
   template <class... _Args>
@@ -999,8 +1025,8 @@ private:
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
 
-  template <class _First, class... _Rest>
-  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
+  template <class... _Args>
+  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _Args&&... __args);
 
   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
     __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
@@ -1615,69 +1641,6 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Key, class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
-  size_t __hash   = hash_function()(__k);
-  size_type __bc  = bucket_count();
-  bool __inserted = false;
-  __next_pointer __nd;
-  size_t __chash;
-  if (__bc != 0) {
-    __chash = std::__constrain_hash(__hash, __bc);
-    __nd    = __bucket_list_[__chash];
-    if (__nd != nullptr) {
-      for (__nd = __nd->__next_;
-           __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
-           __nd = __nd->__next_) {
-        if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
-          goto __done;
-      }
-    }
-  }
-  {
-    __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
-    if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
-      __rehash_unique(std::max<size_type>(
-          2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
-      __bc    = bucket_count();
-      __chash = std::__constrain_hash(__hash, __bc);
-    }
-    // insert_after __bucket_list_[__chash], or __first_node if bucket is null
-    __next_pointer __pn = __bucket_list_[__chash];
-    if (__pn == nullptr) {
-      __pn          = __first_node_.__ptr();
-      __h->__next_  = __pn->__next_;
-      __pn->__next_ = __h.get()->__ptr();
-      // fix up __bucket_list_
-      __bucket_list_[__chash] = __pn;
-      if (__h->__next_ != nullptr)
-        __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
-    } else {
-      __h->__next_  = __pn->__next_;
-      __pn->__next_ = static_cast<__next_pointer>(__h.get());
-    }
-    __nd = static_cast<__next_pointer>(__h.release());
-    // increment size
-    ++size();
-    __inserted = true;
-  }
-__done:
-  return pair<iterator, bool>(iterator(__nd), __inserted);
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) {
-  __node_holder __h        = __construct_node(std::forward<_Args>(__args)...);
-  pair<iterator, bool> __r = __node_insert_unique(__h.get());
-  if (__r.second)
-    __h.release();
-  return __r;
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class... _Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {
@@ -1928,15 +1891,14 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _First, class... _Rest>
+template <class... _Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) {
-  static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _Args&&... __args) {
+  static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
   __node_allocator& __na = __node_alloc();
   __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
   std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash);
-  __node_traits::construct(
-      __na, std::addressof(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
+  __node_traits::construct(__na, std::addressof(__h->__get_value()), std::forward<_Args>(__args)...);
   __h.get_deleter().__value_constructed = true;
   return __h;
 }
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 0f3640e..3ad2129 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -23,7 +23,6 @@
 #include <__memory/pointer_traits.h>
 #include <__memory/swap_allocator.h>
 #include <__memory/unique_ptr.h>
-#include <__type_traits/can_extract_key.h>
 #include <__type_traits/copy_cvref.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/invoke.h>
@@ -38,6 +37,7 @@
 #include <__utility/move.h>
 #include <__utility/pair.h>
 #include <__utility/swap.h>
+#include <__utility/try_key_extraction.h>
 #include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -900,88 +900,74 @@ public:
       _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>);
 #endif
 
-  template <class _Key, class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args);
-  template <class _Key, class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...);
-
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
-
-  template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args);
-
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
 
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
-    return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
-  }
-
-  template <class _First,
-            class _Second,
-            __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
-    return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
-  }
-
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
-    return __emplace_unique_impl(std::forward<_Args>(__args)...);
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
-    return __emplace_unique_impl(std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
-    return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
-    return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
-    return __emplace_hint_unique_extract_key(__p, std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
-  }
-
-  template <class _First,
-            class _Second,
-            __enable_if_t<__can_extract_map_key<_First, key_type, value_type>::value, int> = 0>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) {
-    return __emplace_hint_unique_key_args(__p, __f, std::forward<_First>(__f), std::forward<_Second>(__s)).first;
+    return std::__try_key_extraction<key_type>(
+        [this](const key_type& __key, _Args&&... __args2) {
+          __end_node_pointer __parent;
+          __node_base_pointer& __child = __find_equal(__parent, __key);
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          bool __inserted              = false;
+          if (__child == nullptr) {
+            __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r        = __h.release();
+            __inserted = true;
+          }
+          return pair<iterator, bool>(iterator(__r), __inserted);
+        },
+        [this](_Args&&... __args2) {
+          __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+          __end_node_pointer __parent;
+          __node_base_pointer& __child = __find_equal(__parent, __h->__get_value());
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          bool __inserted              = false;
+          if (__child == nullptr) {
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r        = __h.release();
+            __inserted = true;
+          }
+          return pair<iterator, bool>(iterator(__r), __inserted);
+        },
+        std::forward<_Args>(__args)...);
   }
 
   template <class... _Args>
-  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
-    return __emplace_hint_unique_impl(__p, std::forward<_Args>(__args)...);
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator
-  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
-    return __emplace_hint_unique_impl(__p, std::forward<_Pp>(__x));
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator
-  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
-    return __emplace_hint_unique_key_args(__p, __x, std::forward<_Pp>(__x)).first;
-  }
-
-  template <class _Pp>
-  _LIBCPP_HIDE_FROM_ABI iterator
-  __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
-    return __emplace_hint_unique_key_args(__p, __x.first, std::forward<_Pp>(__x)).first;
+  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_hint_unique(const_iterator __p, _Args&&... __args) {
+    return std::__try_key_extraction<key_type>(
+        [this, __p](const key_type& __key, _Args&&... __args2) {
+          __end_node_pointer __parent;
+          __node_base_pointer __dummy;
+          __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __key);
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          bool __inserted              = false;
+          if (__child == nullptr) {
+            __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r        = __h.release();
+            __inserted = true;
+          }
+          return pair<iterator, bool>(iterator(__r), __inserted);
+        },
+        [this, __p](_Args&&... __args2) {
+          __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
+          __end_node_pointer __parent;
+          __node_base_pointer __dummy;
+          __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__get_value());
+          __node_pointer __r           = static_cast<__node_pointer>(__child);
+          if (__child == nullptr) {
+            __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+            __r = __h.release();
+          }
+          return pair<iterator, bool>(iterator(__r), __child == nullptr);
+        },
+        std::forward<_Args>(__args)...);
   }
 
   template <class _ValueT = _Tp, __enable_if_t<__is_tree_value_type_v<_ValueT>, int> = 0>
@@ -1802,42 +1788,6 @@ void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
 }
 
 template <class _Tp, class _Compare, class _Allocator>
-template <class _Key, class... _Args>
-pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
-  __end_node_pointer __parent;
-  __node_base_pointer& __child = __find_equal(__parent, __k);
-  __node_pointer __r           = static_cast<__node_pointer>(__child);
-  bool __inserted              = false;
-  if (__child == nullptr) {
-    __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
-    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
-    __r        = __h.release();
-    __inserted = true;
-  }
-  return pair<iterator, bool>(iterator(__r), __inserted);
-}
-
-template <class _Tp, class _Compare, class _Allocator>
-template <class _Key, class... _Args>
-pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args(
-    const_iterator __p, _Key const& __k, _Args&&... __args) {
-  __end_node_pointer __parent;
-  __node_base_pointer __dummy;
-  __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
-  __node_pointer __r           = static_cast<__node_pointer>(__child);
-  bool __inserted              = false;
-  if (__child == nullptr) {
-    __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
-    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
-    __r        = __h.release();
-    __inserted = true;
-  }
-  return pair<iterator, bool>(iterator(__r), __inserted);
-}
-
-template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::__node_holder
 __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {
@@ -1850,39 +1800,6 @@ __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) {
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class... _Args>
-pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
-__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) {
-  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
-  __end_node_pointer __parent;
-  __node_base_pointer& __child = __find_equal(__parent, __h->__get_value());
-  __node_pointer __r           = static_cast<__node_pointer>(__child);
-  bool __inserted              = false;
-  if (__child == nullptr) {
-    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
-    __r        = __h.release();
-    __inserted = true;
-  }
-  return pair<iterator, bool>(iterator(__r), __inserted);
-}
-
-template <class _Tp, class _Compare, class _Allocator>
-template <class... _Args>
-typename __tree<_Tp, _Compare, _Allocator>::iterator
-__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) {
-  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
-  __end_node_pointer __parent;
-  __node_base_pointer __dummy;
-  __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__get_value());
-  __node_pointer __r           = static_cast<__node_pointer>(__child);
-  if (__child == nullptr) {
-    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
-    __r = __h.release();
-  }
-  return iterator(__r);
-}
-
-template <class _Tp, class _Compare, class _Allocator>
-template <class... _Args>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) {
   __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
diff --git a/libcxx/include/__type_traits/can_extract_key.h b/libcxx/include/__type_traits/can_extract_key.h
deleted file mode 100644
index b8359d0..0000000
--- a/libcxx/include/__type_traits/can_extract_key.h
+++ /dev/null
@@ -1,53 +0,0 @@
-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H
-#define _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H
-
-#include <__config>
-#include <__fwd/pair.h>
-#include <__type_traits/conditional.h>
-#include <__type_traits/integral_constant.h>
-#include <__type_traits/is_same.h>
-#include <__type_traits/remove_const.h>
-#include <__type_traits/remove_const_ref.h>
-
-#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
-#  pragma GCC system_header
-#endif
-
-_LIBCPP_BEGIN_NAMESPACE_STD
-
-// These traits are used in __tree and __hash_table
-struct __extract_key_fail_tag {};
-struct __extract_key_self_tag {};
-struct __extract_key_first_tag {};
-
-template <class _ValTy, class _Key, class _RawValTy = __remove_const_ref_t<_ValTy> >
-struct __can_extract_key
-    : __conditional_t<_IsSame<_RawValTy, _Key>::value, __extract_key_self_tag, __extract_key_fail_tag> {};
-
-template <class _Pair, class _Key, class _First, class _Second>
-struct __can_extract_key<_Pair, _Key, pair<_First, _Second> >
-    : __conditional_t<_IsSame<__remove_const_t<_First>, _Key>::value, __extract_key_first_tag, __extract_key_fail_tag> {
-};
-
-// __can_extract_map_key uses true_type/false_type instead of the tags.
-// It returns true if _Key != _ContainerValueTy (the container is a map not a set)
-// and _ValTy == _Key.
-template <class _ValTy, class _Key, class _ContainerValueTy, class _RawValTy = __remove_const_ref_t<_ValTy> >
-struct __can_extract_map_key : integral_constant<bool, _IsSame<_RawValTy, _Key>::value> {};
-
-// This specialization returns __extract_key_fail_tag for non-map containers
-// because _Key == _ContainerValueTy
-template <class _ValTy, class _Key, class _RawValTy>
-struct __can_extract_map_key<_ValTy, _Key, _Key, _RawValTy> : false_type {};
-
-_LIBCPP_END_NAMESPACE_STD
-
-#endif // _LIBCPP___TYPE_TRAITS_CAN_EXTRACT_KEY_H
diff --git a/libcxx/include/__utility/try_key_extraction.h b/libcxx/include/__utility/try_key_extraction.h
new file mode 100644
index 0000000..755c082
--- /dev/null
+++ b/libcxx/include/__utility/try_key_extraction.h
@@ -0,0 +1,114 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H
+#define _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H
+
+#include <__config>
+#include <__fwd/pair.h>
+#include <__fwd/tuple.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/is_same.h>
+#include <__type_traits/remove_const.h>
+#include <__type_traits/remove_const_ref.h>
+#include <__utility/declval.h>
+#include <__utility/forward.h>
+#include <__utility/piecewise_construct.h>
+#include <__utility/priority_tag.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _KeyT, class _Ret, class _WithKey, class _WithoutKey, class... _Args>
+_LIBCPP_HIDE_FROM_ABI _Ret
+__try_key_extraction_impl(__priority_tag<0>, _WithKey, _WithoutKey __without_key, _Args&&... __args) {
+  return __without_key(std::forward<_Args>(__args)...);
+}
+
+template <class _KeyT,
+          class _Ret,
+          class _WithKey,
+          class _WithoutKey,
+          class _Arg,
+          __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg> >::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Ret
+__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) {
+  return __with_key(__arg, std::forward<_Arg>(__arg));
+}
+
+template <class _KeyT,
+          class _Ret,
+          class _WithKey,
+          class _WithoutKey,
+          class _Arg,
+          __enable_if_t<__is_pair_v<__remove_const_ref_t<_Arg> > &&
+                            is_same<__remove_const_t<typename __remove_const_ref_t<_Arg>::first_type>, _KeyT>::value,
+                        int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Ret
+__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg&& __arg) {
+  return __with_key(__arg.first, std::forward<_Arg>(__arg));
+}
+
+template <class _KeyT,
+          class _Ret,
+          class _WithKey,
+          class _WithoutKey,
+          class _Arg1,
+          class _Arg2,
+          __enable_if_t<is_same<_KeyT, __remove_const_ref_t<_Arg1> >::value, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Ret
+__try_key_extraction_impl(__priority_tag<1>, _WithKey __with_key, _WithoutKey, _Arg1&& __arg1, _Arg2&& __arg2) {
+  return __with_key(__arg1, std::forward<_Arg1>(__arg1), std::forward<_Arg2>(__arg2));
+}
+
+#ifndef _LIBCPP_CXX03_LANG
+template <class _KeyT,
+          class _Ret,
+          class _WithKey,
+          class _WithoutKey,
+          class _PiecewiseConstruct,
+          class _Tuple1,
+          class _Tuple2,
+          __enable_if_t<is_same<__remove_const_ref_t<_PiecewiseConstruct>, piecewise_construct_t>::value &&
+                            __is_tuple_v<_Tuple1> && tuple_size<_Tuple1>::value == 1 &&
+                            is_same<__remove_const_ref_t<typename tuple_element<0, _Tuple1>::type>, _KeyT>::value,
+                        int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Ret __try_key_extraction_impl(
+    __priority_tag<1>,
+    _WithKey __with_key,
+    _WithoutKey,
+    _PiecewiseConstruct&& __pc,
+    _Tuple1&& __tuple1,
+    _Tuple2&& __tuple2) {
+  return __with_key(
+      std::get<0>(__tuple1),
+      std::forward<_PiecewiseConstruct>(__pc),
+      std::forward<_Tuple1>(__tuple1),
+      std::forward<_Tuple2>(__tuple2));
+}
+#endif // _LIBCPP_CXX03_LANG
+
+// This function tries extracting the given _KeyT from _Args...
+// If it succeeds to extract the key, it calls the `__with_key` function with the extracted key and all of the
+// arguments. Otherwise it calls the `__without_key` function with all of the arguments.
+//
+// Both `__with_key` and `__without_key` must take all arguments by reference.
+template <class _KeyT, class _WithKey, class _WithoutKey, class... _Args>
+_LIBCPP_HIDE_FROM_ABI decltype(std::declval<_WithoutKey>()(std::declval<_Args>()...))
+__try_key_extraction(_WithKey __with_key, _WithoutKey __without_key, _Args&&... __args) {
+  using _Ret = decltype(__without_key(std::forward<_Args>(__args)...));
+  return std::__try_key_extraction_impl<_KeyT, _Ret>(
+      __priority_tag<1>(), __with_key, __without_key, std::forward<_Args>(__args)...);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___UTILITY_TRY_EXTRACT_KEY_H
diff --git a/libcxx/include/map b/libcxx/include/map
index 9bd2282..b53e1c4 100644
--- a/libcxx/include/map
+++ b/libcxx/include/map
@@ -1055,7 +1055,7 @@ public:
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
-    return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...);
+    return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...).first;
   }
 
   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
@@ -1065,7 +1065,7 @@ public:
 
   template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
-    return __tree_.__emplace_hint_unique(__pos.__i_, std::forward<_Pp>(__p));
+    return __tree_.__emplace_hint_unique(__pos.__i_, std::forward<_Pp>(__p)).first;
   }
 
 #  endif // _LIBCPP_CXX03_LANG
@@ -1073,7 +1073,7 @@ public:
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); }
 
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
-    return __tree_.__emplace_hint_unique(__p.__i_, __v);
+    return __tree_.__emplace_hint_unique(__p.__i_, __v).first;
   }
 
 #  ifndef _LIBCPP_CXX03_LANG
@@ -1082,7 +1082,7 @@ public:
   }
 
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
-    return __tree_.__emplace_hint_unique(__p.__i_, std::move(__v));
+    return __tree_.__emplace_hint_unique(__p.__i_, std::move(__v)).first;
   }
 
   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
@@ -1108,17 +1108,13 @@ public:
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
-    return __tree_.__emplace_unique_key_args(
-        __k,
-        std::piecewise_construct,
-        std::forward_as_tuple(__k),
-        std::forward_as_tuple(std::forward<_Args>(__args)...));
+    return __tree_.__emplace_unique(
+        std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
   }
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
-    return __tree_.__emplace_unique_key_args(
-        __k,
+    return __tree_.__emplace_unique(
         std::piecewise_construct,
         std::forward_as_tuple(std::move(__k)),
         std::forward_as_tuple(std::forward<_Args>(__args)...));
@@ -1127,9 +1123,8 @@ public:
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {
     return __tree_
-        .__emplace_hint_unique_key_args(
+        .__emplace_hint_unique(
             __h.__i_,
-            __k,
             std::piecewise_construct,
             std::forward_as_tuple(__k),
             std::forward_as_tuple(std::forward<_Args>(__args)...))
@@ -1139,9 +1134,8 @@ public:
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {
     return __tree_
-        .__emplace_hint_unique_key_args(
+        .__emplace_hint_unique(
             __h.__i_,
-            __k,
             std::piecewise_construct,
             std::forward_as_tuple(std::move(__k)),
             std::forward_as_tuple(std::forward<_Args>(__args)...))
@@ -1170,7 +1164,7 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {
-    auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v));
+    auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, __k, std::forward<_Vp>(__v));
 
     if (!__inserted)
       __r->second = std::forward<_Vp>(__v);
@@ -1180,8 +1174,7 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {
-    auto [__r, __inserted] =
-        __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v));
+    auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, std::move(__k), std::forward<_Vp>(__v));
 
     if (!__inserted)
       __r->second = std::forward<_Vp>(__v);
@@ -1398,20 +1391,15 @@ map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
-  return __tree_
-      .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
+  return __tree_.__emplace_unique(std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
       .first->second;
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {
-  // TODO investigate this clang-tidy warning.
-  // NOLINTBEGIN(bugprone-use-after-move)
   return __tree_
-      .__emplace_unique_key_args(
-          __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
+      .__emplace_unique(std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
       .first->second;
-  // NOLINTEND(bugprone-use-after-move)
 }
 
 #  else // _LIBCPP_CXX03_LANG
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index c431c0c..ee18d04 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -70,7 +70,6 @@ module std_core [system] {
     module aligned_storage                            { header "__type_traits/aligned_storage.h" }
     module aligned_union                              { header "__type_traits/aligned_union.h" }
     module alignment_of                               { header "__type_traits/alignment_of.h" }
-    module can_extract_key                            { header "__type_traits/can_extract_key.h" }
     module common_reference                           { header "__type_traits/common_reference.h" }
     module common_type {
       header "__type_traits/common_type.h"
@@ -2178,6 +2177,7 @@ module std [system] {
     module small_buffer               { header "__utility/small_buffer.h" }
     module swap                       { header "__utility/swap.h" }
     module to_underlying              { header "__utility/to_underlying.h" }
+    module try_key_extraction         { header "__utility/try_key_extraction.h" }
     module unreachable                { header "__utility/unreachable.h" }
 
     header "utility"
diff --git a/libcxx/include/set b/libcxx/include/set
index 5190fc1..b444e83 100644
--- a/libcxx/include/set
+++ b/libcxx/include/set
@@ -732,13 +732,13 @@ public:
   }
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
-    return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...);
+    return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...).first;
   }
 #  endif // _LIBCPP_CXX03_LANG
 
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); }
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
-    return __tree_.__emplace_hint_unique(__p, __v);
+    return __tree_.__emplace_hint_unique(__p, __v).first;
   }
 
   template <class _InputIterator>
@@ -763,7 +763,7 @@ public:
   }
 
   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
-    return __tree_.__emplace_hint_unique(__p, std::move(__v));
+    return __tree_.__emplace_hint_unique(__p, std::move(__v)).first;
   }
 
   _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
diff --git a/libcxx/include/tuple b/libcxx/include/tuple
index 8cc061c..d2cc0f5 100644
--- a/libcxx/include/tuple
+++ b/libcxx/include/tuple
@@ -324,12 +324,6 @@ _LIBCPP_HIDE_FROM_ABI constexpr _Ret __tuple_compare_three_way(const _Tp& __x, c
 #    endif // _LIBCPP_STD_VER >= 20
 
 #    if _LIBCPP_STD_VER >= 23
-template <class>
-inline constexpr bool __is_tuple_v = false;
-
-template <class... _Tp>
-inline constexpr bool __is_tuple_v<tuple<_Tp...>> = true;
-
 template <class _Tp>
 concept __tuple_like_no_tuple = __tuple_like<_Tp> && !__is_tuple_v<_Tp>;
 
diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map
index a934953..9b02ecf0 100644
--- a/libcxx/include/unordered_map
+++ b/libcxx/include/unordered_map
@@ -1172,14 +1172,13 @@ public:
 #  if _LIBCPP_STD_VER >= 17
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
-    return __table_.__emplace_unique_key_args(
-        __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
+    return __table_.__emplace_unique(
+        piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
   }
 
   template <class... _Args>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
-    return __table_.__emplace_unique_key_args(
-        __k,
+    return __table_.__emplace_unique(
         piecewise_construct,
         std::forward_as_tuple(std::move(__k)),
         std::forward_as_tuple(std::forward<_Args>(__args)...));
@@ -1197,7 +1196,7 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
-    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v));
+    pair<iterator, bool> __res = __table_.__emplace_unique(__k, std::forward<_Vp>(__v));
     if (!__res.second) {
       __res.first->second = std::forward<_Vp>(__v);
     }
@@ -1206,7 +1205,7 @@ public:
 
   template <class _Vp>
   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
-    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v));
+    pair<iterator, bool> __res = __table_.__emplace_unique(std::move(__k), std::forward<_Vp>(__v));
     if (!__res.second) {
       __res.first->second = std::forward<_Vp>(__v);
     }
@@ -1612,16 +1611,13 @@ inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterato
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
-  return __table_
-      .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
+  return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
       .first->second;
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) {
-  return __table_
-      .__emplace_unique_key_args(
-          __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
+  return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
       .first->second;
 }
 #  else // _LIBCPP_CXX03_LANG
diff --git a/libcxx/test/std/containers/associative/multiset/emplace.pass.cpp b/libcxx/test/std/containers/associative/multiset/emplace.pass.cpp
index bddfd8f..97cae1c 100644
--- a/libcxx/test/std/containers/associative/multiset/emplace.pass.cpp
+++ b/libcxx/test/std/containers/associative/multiset/emplace.pass.cpp
@@ -15,12 +15,12 @@
 // template <class... Args>
 //   iterator emplace(Args&&... args);
 
-#include <set>
 #include <cassert>
+#include <set>
 
-#include "test_macros.h"
 #include "../../Emplaceable.h"
 #include "DefaultOnly.h"
+#include "MoveOnly.h"
 #include "min_allocator.h"
 
 int main(int, char**) {
@@ -77,6 +77,12 @@ int main(int, char**) {
     assert(m.size() == 1);
     assert(*r == 2);
   }
+  { // We're unwrapping pairs for `{,multi}map`. Make sure we're not trying to do that for multiset.
+    using Set = std::multiset<std::pair<MoveOnly, MoveOnly>>;
+    Set set;
+    auto iter = set.emplace(std::pair<MoveOnly, MoveOnly>(2, 4));
+    assert(set.begin() == iter);
+  }
 
   return 0;
 }
diff --git a/libcxx/test/std/containers/associative/set/emplace.pass.cpp b/libcxx/test/std/containers/associative/set/emplace.pass.cpp
index e038de7..e5a9f95 100644
--- a/libcxx/test/std/containers/associative/set/emplace.pass.cpp
+++ b/libcxx/test/std/containers/associative/set/emplace.pass.cpp
@@ -15,12 +15,12 @@
 // template <class... Args>
 //   pair<iterator, bool> emplace(Args&&... args);
 
-#include <set>
 #include <cassert>
+#include <set>
 
-#include "test_macros.h"
 #include "../../Emplaceable.h"
 #include "DefaultOnly.h"
+#include "MoveOnly.h"
 #include "min_allocator.h"
 
 int main(int, char**) {
@@ -84,6 +84,13 @@ int main(int, char**) {
     assert(m.size() == 1);
     assert(*r.first == 2);
   }
+  { // We're unwrapping pairs for `{,multi}map`. Make sure we're not trying to do that for set.
+    using Set = std::set<std::pair<MoveOnly, MoveOnly>>;
+    Set set;
+    auto res = set.emplace(std::pair<MoveOnly, MoveOnly>(2, 4));
+    assert(std::get<1>(res));
+    assert(set.begin() == std::get<0>(res));
+  }
 
   return 0;
 }
diff --git a/libcxx/test/std/containers/unord/unord.multiset/emplace.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/emplace.pass.cpp
index 886ddd7..434f205 100644
--- a/libcxx/test/std/containers/unord/unord.multiset/emplace.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.multiset/emplace.pass.cpp
@@ -17,11 +17,11 @@
 // template <class... Args>
 //     iterator emplace(Args&&... args);
 
-#include <unordered_set>
 #include <cassert>
+#include <unordered_set>
 
-#include "test_macros.h"
 #include "../../Emplaceable.h"
+#include "MoveOnly.h"
 #include "min_allocator.h"
 
 int main(int, char**) {
@@ -59,6 +59,15 @@ int main(int, char**) {
     assert(c.size() == 3);
     assert(*r == Emplaceable(5, 6));
   }
+  { // We're unwrapping pairs for `unordered_{,multi}map`. Make sure we're not trying to do that for unordered_multiset.
+    struct PairHasher {
+      size_t operator()(const std::pair<MoveOnly, MoveOnly>& val) const { return std::hash<MoveOnly>()(val.first); }
+    };
+    using Set = std::unordered_multiset<std::pair<MoveOnly, MoveOnly>, PairHasher>;
+    Set set;
+    auto iter = set.emplace(std::pair<MoveOnly, MoveOnly>(2, 4));
+    assert(set.begin() == iter);
+  }
 
   return 0;
 }
diff --git a/libcxx/test/std/containers/unord/unord.set/emplace.pass.cpp b/libcxx/test/std/containers/unord/unord.set/emplace.pass.cpp
index 8972f03..24e85a1 100644
--- a/libcxx/test/std/containers/unord/unord.set/emplace.pass.cpp
+++ b/libcxx/test/std/containers/unord/unord.set/emplace.pass.cpp
@@ -17,11 +17,11 @@
 // template <class... Args>
 //     pair<iterator, bool> emplace(Args&&... args);
 
-#include <unordered_set>
 #include <cassert>
+#include <unordered_set>
 
-#include "test_macros.h"
 #include "../../Emplaceable.h"
+#include "MoveOnly.h"
 #include "min_allocator.h"
 
 int main(int, char**) {
@@ -65,6 +65,16 @@ int main(int, char**) {
     assert(*r.first == Emplaceable(5, 6));
     assert(!r.second);
   }
+  { // We're unwrapping pairs for `unordered_{,multi}map`. Make sure we're not trying to do that for unordered_set.
+    struct PairHasher {
+      size_t operator()(const std::pair<MoveOnly, MoveOnly>& val) const { return std::hash<MoveOnly>()(val.first); }
+    };
+    using Set = std::unordered_set<std::pair<MoveOnly, MoveOnly>, PairHasher>;
+    Set set;
+    auto res = set.emplace(std::pair<MoveOnly, MoveOnly>(2, 4));
+    assert(std::get<1>(res));
+    assert(set.begin() == std::get<0>(res));
+  }
 
   return 0;
 }