[libcxx][c++17] P0083R5: Splicing Maps and Sets

[erik.pilkington]

Summary

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0083r3.pdf

This patch adds support for p0083, splicing maps and sets. This feature allows users to extract a container node from a unordered or associative container, then insert it into another container without having to copy the node. The container_type::node_type member is a smart pointer that holds an extracted node. This proposal also includes a merge member function that can extract and insert nodes from a source container without losing nodes if an exception is thrown (from, i.e., a comparator).

This implementation for this is pretty straightforward, most of the operations necessary to write this API are already part of __tree and __hash_table. In __hash_table, I split up the functions __node_insert_unqiue and __node_insert_multi into 2 parts in order to implement merge. The first part, __node_insert_{multi,unique}_prepare checks to see if a node already is present in the container (as needed), and rehashes the container. This function can forward exceptions, but doesn't mutate the node it's preparing to insert. the __node_insert_{multi,unique}_perform is noexcept, but mutates the pointers in the node to actually insert it into the container. This allows merge to call a _prepare function on a node while it is in the source container, without invalidating anything or losing nodes if an exception is thrown. Another quirk is the __generic_container_node_destructor templated struct, this is forward-declared (and used, in a dependent context) in <__node_handle> and specialized in <__tree> and <__hash_table>. This allows <__node_handle> to call into __hash_node_destructor and __tree_node_destructor without including those headers.

As far as testing goes, I added some tests and ran them with msan, ubsan, and asan. I also ran the libstdc++ tests for this with the same sanitizers on linux and macos.

I'm still pretty new to libc++, so take this patch with a grain of salt!
Thanks for taking a look,
Erik

[rsmith]

How do you deal with the fact that node handles for map-like types need to be able to mutate a const member of a pair in-place? Are you assuming/hoping the compiler won't do bad things to the program as a result, or is there some reason why it would be unlikely to do so / disallowed from doing so? If you're just casting pair<const K, V> to / from pair<K, V> (and I think that's what's happening), there is a very real risk that struct-path-sensitive TBAA will decide that pair<const K, V>::first and pair<K, V>::first cannot alias (and likewise for ::second) and then miscompile code using libc++'s node pointers.

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

Another possibility would be a compiler intrinsic to change the type of the pair, in-place, from a std::pair<const K, V> to a std::pair<K, V>, without changing anything about the members -- except that the first member changes type.

Yet another possibility would be to only ever access the key field through a type annotated with __attribute__((may_alias)), and then launder the node pointer when we're ready to insert it back into the container (to "pick up" the new value of the const member). That's formally breaking the rules (a launder isn't enough, because we didn't actually create a new object, and in any case we still mutated the value of a const subobject), but it'll probably work fine across compilers that support the attribute.

libcxx/include/__node_handle

148 ↗

(On Diff #146659)

using __base::__base; would be a much more reasonable way to write an inheriting constructor declaration here.

[erik.pilkington]

Use the simpler inherited constructor spelling @rsmith suggested.

[erik.pilkington]

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

I'm a fan of this idea, this would also have the bonus of fixing some pre-existing type-punning between pair<const K, V> and pair<K, V> (see __hash_value_type and __value_type in <unordered_map> and <map>).

Another possibility would be a compiler intrinsic to change the type of the pair, in-place, from a std::pair<const K, V> to a std::pair<K, V>, without changing anything about the members -- except that the first member changes type.

How could this work? It would still be possible for TBAA to assume that void m(std::pair<const K, V>*, std::pair<K, V>*);'s parameters don't alias when optimizing m, regardless of how we form the non-const pair, right?

Yet another possibility would be to only ever access the key field through a type annotated with __attribute__((may_alias)), and then launder the node pointer when we're ready to insert it back into the container (to "pick up" the new value of the const member). That's formally breaking the rules (a launder isn't enough, because we didn't actually create a new object, and in any case we still mutated the value of a const subobject), but it'll probably work fine across compilers that support the attribute.

I think we could fall back to this in cases where the attribute from idea (1) isn't available. There, we could mark std::pair as may_alias and still fix __hash_value_type and __value_type. This would pessimize std::pair, but only for "older" compilers.

So unless I've gotten this all wrong, I'll write a patch to support that new attribute and come back to this patch if/when that lands. Sound good?

Thanks for the feedback!
Erik

[mclow.lists]

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

I'm a fan of this idea, this would also have the bonus of fixing some pre-existing type-punning between pair<const K, V> and pair<K, V> (see hash_value_type and value_type in <unordered_map> and <map>).

This was supposed to be taken care of by [class.mem]/21 (common initial sequence), but that foundered on "standard-layout".

[rsmith]

In D46845#1099732, @mclow.lists wrote:

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

I'm a fan of this idea, this would also have the bonus of fixing some pre-existing type-punning between pair<const K, V> and pair<K, V> (see hash_value_type and value_type in <unordered_map> and <map>).

This was supposed to be taken care of by [class.mem]/21 (common initial sequence), but that foundered on "standard-layout".

Also, the common initial sequence rule only allows loads through the wrong type, not stores, and in any case does not alter the rule that modifying a const object results in UB.

[erik.pilkington]

In D46845#1098634, @rsmith wrote:

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

Would you mind elaborating on this? If we don't optimize on a member being const, then what should this attribute actually do? The only thing I can think of is making a field with type const T with the attribute claim it's a T to TBAA, but that would be a no-op because loads and stores through those types are compatible anyways.

In D46845#1098634, @rsmith wrote:

Yet another possibility would be to only ever access the key field through a type annotated with __attribute__((may_alias)), and then launder the node pointer when we're ready to insert it back into the container (to "pick up" the new value of the const member). That's formally breaking the rules (a launder isn't enough, because we didn't actually create a new object, and in any case we still mutated the value of a const subobject), but it'll probably work fine across compilers that support the attribute.

What about instead of type-punning between pair<const K, V> and pair<K, V> (with may_alias) we just did a const_cast in key, and launder the pair when finished? Because loads and stores to const K and K are already assumed to alias each other, we should be able to omit the may_alias attribute (right?). Would that be enough to placate the compiler? If it is, then I think we should just do this and avoid adding another attribute to clang. I'll upload a patch with this to show what I mean.

Thanks!
Erik

[erik.pilkington]

make __map_node_handle use a const_cast on the key instead of type-punning between pair<const K, V> and pair<K, V>. Add calls to std::launder in key() and before inserting a node handle.

[erik.pilkington]

Add _LIBCPP_ASSERT calls to all the entry points, friendly ping!

[rsmith]

In D46845#1105638, @erik.pilkington wrote:

make __map_node_handle use a const_cast on the key instead of type-punning between pair<const K, V> and pair<K, V>. Add calls to std::launder in key() and before inserting a node handle.

Can you do this as a separate change, prior to adding node_handle? I would in particular expect this to result in the removal of the union __value_type from <map>.

[erik.pilkington]

Update this patch to depend on https://reviews.llvm.org/D47607, which fixes __value_type in map and unordered_map. Thanks!

[EricWF]

libcxx/include/__hash_table

2261 ↗

(On Diff #149362)

If I'm not mistaken, __node_handle_extract_unique and __node_handle_extract_multi have the exact same implementation. This is intentional, no? If so can't we just use one implementation?

libcxx/include/__node_handle

1 ↗

(On Diff #149362)

This header needs to be added to the module.modulemap.

82 ↗

(On Diff #149362)

I'm not sure we should by trying to move a pointer. It's misleading, and we shouldn't expect it to act any differently.

118 ↗

(On Diff #149362)

Missing _LIBCPP_NODISCARD_AFTER_CXX17

libcxx/test/std/containers/associative/set/merge.pass.cpp

20 ↗

(On Diff #149362)

Please include test_macros.h directly.

[erik.pilkington]

Address @EricWF's comments.

libcxx/include/__hash_table

2261 ↗

(On Diff #149362)

Yep, good point. The new patch just has __node_handle_extract.

[erik.pilkington]

Ping!

[erik.pilkington]

Ping! If it'd make this easier to review, I'd be happy to split this up a bit.

[erik.pilkington]

Split this up. I'm moving the merge stuff to a follow-up, that makes this diff a lot easier to read.

[erik.pilkington]

Ping!

[EricWF]

I'm working on this! I'll be taking what is hopefully a final pass at the tests today.

[ldionne]

Generally looks pretty good, but I have a couple questions/suggestions.

libcxx/include/__hash_table

2165 ↗

(On Diff #153964)

When a function is declared with a visibility macro (_LIBCPP_INLINE_VISIBILITY in this case), I think it is customary in libc++ to repeat the visibility macro on the definition as well. If that's correct, apply here and to other similar functions below, and also in __tree.

2212 ↗

(On Diff #153964)

Just a quick Q: am I mistaken or remove() is not part of the unordered_map API? We're not naming it __remove() just because we already have other functions called remove(), so any macro redefining remove would already break things -- is that the idea?

libcxx/include/__node_handle

33 ↗

(On Diff #153964)

Clever way of reducing header dependencies. I like it.

36 ↗

(On Diff #153964)

I'd like to suggest a different approach for implementing the node handles for sets and maps. I believe this would simplify things slightly:

template <class _NodeType, class _Alloc, template <class...> class _MapOrSetSpecifics>
class __basic_node_handle 
    : public _MapOrSetSpecifics<_NodeType, __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>
{
    // same as right now
};

Then, you can get the two different node handles by simply providing the methods in the base class:

template <class _NodeType, class _Derived>
struct __map_node_handle_specifics {
    using key_type = typename _NodeType::__node_value_type::key_type;
    using mapped_type = typename _NodeType::__node_value_type::mapped_type;

    _LIBCPP_INLINE_VISIBILITY
    key_type& key() const
    {
        return static_cast<_Derived const*>(this)->__ptr_->__value_.__ref().first;
    }

    _LIBCPP_INLINE_VISIBILITY
    mapped_type& mapped() const
    {
        return static_cast<_Derived const*>(this)->__ptr_->__value_.__ref().second;
    }
};

template <class _NodeType, class _Derived>
struct __set_node_handle_specifics {
    using value_type = typename _NodeType::__node_value_type;

    _LIBCPP_INLINE_VISIBILITY
    value_type& value() const
    {
        return static_cast<_Derived const*>(this)->__ptr_->__value_;
    }
};

template <class _NodeType, class _Alloc>
using __map_node_handle = __basic_node_handle<_NodeType, _Alloc, __map_node_handle_specifics>;

template <class _NodeType, class _Alloc>
using __set_node_handle = __basic_node_handle<_NodeType, _Alloc, __set_node_handle_specifics>;

This is a classic application of the CRTP. I believe it would reduce the amount of boilerplate currently required for special member functions. It's possible that you thought of this and realized it didn't work for a reason I'm missing right now, too, but the idea seems to work on the surface: https://wandbox.org/permlink/nMaKEg43PVJpA0ld.

You don't have to do this, but please consider it if you think it would simplify the code.

libcxx/include/map

915 ↗

(On Diff #153964)

I believe this function should be marked with _LIBCPP_INLINE_VISIBILITY -- even though in practice the compiler will probably always inline it.

Also, you don't seem to be using that function at all in the diff -- is that right?

So please either mark with _LIBCPP_INLINE_VISIBILITY and use it, or remove it altogether. This comment applies to all 8 containers to which similar methods were added.

libcxx/include/set

399 ↗

(On Diff #153964)

Is this forward declaration necessary?

libcxx/include/unordered_set

569 ↗

(On Diff #153964)

Why don't you use

return __table.template __node_handle_insert_unique<node_type>(__hint, _VSTD::move(__nh));

instead? It seems like this way, if __node_handle_insert_unique(const_iterator, node_type) eventually starts taking advantage of the iterator hint, you'd get the improvement here for free.

1069 ↗

(On Diff #153964)

For the other containers, the two insert methods come before the two extract methods. This is very nitpicky, but you should consider keeping the same order here too for consistency.

libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp

14 ↗

(On Diff #153964)

Please be more specific about which functions you're testing. I find it useful to look at those comments to quickly see what exact signatures are being tested when I'm looking for tests that exercice some specific piece of code.

Actually, perhaps you should extract those tests into multiple files:
unord.map/unord.map.modifiers/insert.node_handle.pass.cpp => test overload of insert on node_type
unord.map/unord.map.modifiers/insert.hint_node_handle.pass.cpp => test overload of insert with a hint and a node_type
unord.map/unord.map.modifiers/extract.node_handle.pass.cpp => test overload of extract on node_type
unord.map/unord.map.modifiers/extract.iterator.pass.cpp => test overload of extract on iterator
unord.map/insert_return_type.pass.cpp => test insert_return_type
unord.map/node_type.pass.cpp => test node handle operations

I believe this would be more consistent with the way things are currently organized for other functions. This comment applies to all containers touched by this review.

23 ↗

(On Diff #153964)

Consider using using XXX = YYY consistently.

33 ↗

(On Diff #153964)

You don't need spaces between consecutive >'s since those tests are not supported in C++03. Feel free to keep them or remove them, I'm just pointing it out.

99–101 ↗

(On Diff #153964)

Why is this test useful?

[ldionne]

I forgot to mention it in my initial review, but it also seems like you forgot to update all the synopsis in the comments at the beginning of headers.

[erik.pilkington]

Address @ldionne's comments.

libcxx/include/__hash_table

2165 ↗

(On Diff #153964)

I can't say I know libc++'s policy here either, but it couldn't hurt, so I added the attributes to the new patch. Maybe @EricWF or @mclow.lists could weigh in here?

2212 ↗

(On Diff #153964)

Yep, I think that was the thinking. IMO it would be nice to just call it __remove to avoid any confusion.

libcxx/include/__node_handle

36 ↗

(On Diff #153964)

Oh, neat! That's a great idea, I didn't even consider CRTP here for some reason. Makes this simpler though. I added this to the new patch.

libcxx/include/map

915 ↗

(On Diff #153964)

Oh, sorry! This was used in the implementation of merge, which I moved to a follow-up. I'll sink it down there and add the visibility attribute.

libcxx/include/set

399 ↗

(On Diff #153964)

No, nice catch! This was also supposed to be a part of the follow-up, I'll move it there.

libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp

14 ↗

(On Diff #153964)

Okay, the new patch divides up the tests for each container into 4 files: extract_iterator.pass.cpp, extract_key.pass.cpp, insert_node_type.pass.cpp, and insert_node_type_hint.pass.cpp. I decided to move the insert_return_type and node_type testing to container.node/node_handle.pass.cpp because they don't really depend on any specific container, and it matches how the standard defines these.

23 ↗

(On Diff #153964)

done!

33 ↗

(On Diff #153964)

Sure, sorry! clang-format adds these in because it isn't smart enough to know when we're in a C++11 context.

99–101 ↗

(On Diff #153964)

I guess it isn't really, it was more of a sanity check.

[ldionne]

libcxx/include/map

43 ↗

(On Diff #155276)

You are missing // since C++17 comments here and elsewhere.

[erik.pilkington]

Add // C++17 to the header comments.

[ldionne]

LGTM -- great! Just make sure the commit message does not pretend the change includes merge.

This may be obvious, but my LGTM alone should probably not be enough to submit.

[erik.pilkington]

Ping!

[erik.pilkington]

Ping!

[mclow.lists]

One more thing -
When you add a new header file, you need to update include/module.modulemap, test/libcxx/double_include.sh.cpp, and include/CMakeLists.txt.
Take a look at D49338 for an example.

[erik.pilkington]

Address @mclow.lists's comment. Thanks!

[erik.pilkington]

In D46845#1183435, @mclow.lists wrote:

One more thing -
When you add a new header file, you need to update include/module.modulemap, test/libcxx/double_include.sh.cpp, and include/CMakeLists.txt.
Take a look at D49338 for an example.

Are you sure we have to update test/libcxx/double_include.sh.cpp? Looks like that file only has public headers, but this patch only adds __node_handle, which is internal. The new patch adds this header to include/CMakeLists.txt though (__node_handle already appeared in module.modulemap)

[mclow.lists]

In D46845#1183462, @erik.pilkington wrote:

In D46845#1183435, @mclow.lists wrote:

One more thing -
When you add a new header file, you need to update include/module.modulemap, test/libcxx/double_include.sh.cpp, and include/CMakeLists.txt.
Take a look at D49338 for an example.

Are you sure we have to update test/libcxx/double_include.sh.cpp? Looks like that file only has public headers, but this patch only adds __node_handle, which is internal. The new patch adds this header to include/CMakeLists.txt though (__node_handle already appeared in module.modulemap)

D'oh! You're right. I didn't see that you had a patch for module.modulemap.
Sorry for the noise.

Go ahead and commit (and thanks for doing this!)

include/CMakeLists.txt

 set(files
   __bit_reference
   __bsd_locale_defaults.h
   __bsd_locale_fallbacks.h
   __errc
   __debug
   __functional_03
   __functional_base
   __functional_base_03
   __hash_table
   __libcpp_version
   __locale
   __mutex_base
+  __node_handle
   __nullptr
   __split_buffer
   __sso_allocator
   __std_stream
   __string
   __threading_support
   __tree
   __tuple

include/__hash_table

void operator()(pointer __p) _NOEXCEPT
             __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
         if (__p)
             __alloc_traits::deallocate(__na_, __p, 1);
     }
 
     template <class> friend class __hash_map_node_destructor;
 };
 
+#if _LIBCPP_STD_VER > 14
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+
+template <class _Tp, class _VoidPtr, class _Alloc>
+struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc>
+    : __hash_node_destructor<_Alloc>
+{
+    using __hash_node_destructor<_Alloc>::__hash_node_destructor;
+};
+#endif
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Key, class _Hash, class _Equal, class _Alloc>
 struct __diagnose_hash_table_helper {
   static constexpr bool __trigger_diagnostics()
     _LIBCPP_DIAGNOSE_WARNING(__check_hash_requirements<_Key, _Hash>::value
                          && !__invokable<_Hash const&, _Key const&>::value,
       "the specified hash functor does not provide a const call operator")
#else  // !defined(_LIBCPP_CXX03_LANG)
     iterator __insert_multi(const_iterator __p, const __container_value_type& __x);
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
         return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
     }
 
+#if _LIBCPP_STD_VER > 14
+    template <class _NodeHandle, class _InsertReturnType>
+    _LIBCPP_INLINE_VISIBILITY
+    _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_unique(const_iterator __hint,
+                                         _NodeHandle&& __nh);
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(_NodeHandle&& __nh);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract(key_type const& __key);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract(const_iterator __it);
+#endif
+
     void clear() _NOEXCEPT;
     void rehash(size_type __n);
     _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
         {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT
     {
#endif
     __node_holder __h = __construct_node(__x);
     iterator __r = __node_insert_multi(__p, __h.get());
     __h.release();
     return __r;
 }
 
 #endif  // _LIBCPP_CXX03_LANG
 
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle, class _InsertReturnType>
+_LIBCPP_INLINE_VISIBILITY
+_InsertReturnType
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+    _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return _InsertReturnType{end(), false, _NodeHandle()};
+    pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
+    if (__result.second)
+        __nh.__release();
+    return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)};
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+    const_iterator, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+    pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
+    if (__result.second)
+        __nh.__release();
+    return __result.first;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
+    key_type const& __key)
+{
+    iterator __i = find(__key);
+    if (__i == end())
+        return _NodeHandle();
+    return __node_handle_extract<_NodeHandle>(__i);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
+    const_iterator __p)
+{
+    allocator_type __alloc(__node_alloc());
+    return _NodeHandle(remove(__p).release(), __alloc);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+    _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+    iterator __result = __node_insert_multi(__nh.__ptr_);
+    __nh.__release();
+    return __result;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+    iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
+    __nh.__release();
+    return __result;
+}
+
+#endif  // _LIBCPP_STD_VER > 14
+
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
 {
     if (__n == 1)
         __n = 2;
     else if (__n & (__n - 1))
         __n = __next_prime(__n);

include/__node_handle

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___NODE_HANDLE
+#define _LIBCPP___NODE_HANDLE
+
+#include <__config>
+#include <memory>
+#include <optional>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 14
+
+#define __cpp_lib_node_extract 201606L
+
+// Specialized in __tree & __hash_table for their _NodeType.
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+
+template <class _NodeType, class _Alloc,
+          template <class, class> class _MapOrSetSpecifics>
+class _LIBCPP_TEMPLATE_VIS __basic_node_handle
+    : public _MapOrSetSpecifics<
+          _NodeType,
+          __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>
+{
+    template <class _Tp, class _Compare, class _Allocator>
+        friend class __tree;
+    template <class _Tp, class _Hash, class _Equal, class _Allocator>
+        friend class __hash_table;
+    friend struct _MapOrSetSpecifics<
+        _NodeType, __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>;
+
+    typedef allocator_traits<_Alloc> __alloc_traits;
+    typedef typename __rebind_pointer<typename __alloc_traits::void_pointer,
+                                      _NodeType>::type
+        __node_pointer_type;
+
+public:
+    typedef _Alloc allocator_type;
+
+private:
+    __node_pointer_type __ptr_ = nullptr;
+    optional<allocator_type> __alloc_;
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __release()
+    {
+        __ptr_ = nullptr;
+        __alloc_ = _VSTD::nullopt;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __destroy_node_pointer()
+    {
+        if (__ptr_ != nullptr)
+        {
+            typedef typename __allocator_traits_rebind<
+                allocator_type, _NodeType>::type __node_alloc_type;
+            __node_alloc_type __alloc(*__alloc_);
+            __generic_container_node_destructor<_NodeType, __node_alloc_type>(
+                __alloc, true)(__ptr_);
+            __ptr_ = nullptr;
+        }
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __basic_node_handle(__node_pointer_type __ptr,
+                        allocator_type const& __alloc)
+            : __ptr_(__ptr), __alloc_(__alloc)
+    {
+    }
+
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    __basic_node_handle() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __basic_node_handle(__basic_node_handle&& __other) noexcept
+            : __ptr_(__other.__ptr_),
+              __alloc_(_VSTD::move(__other.__alloc_))
+    {
+        __other.__ptr_ = nullptr;
+        __other.__alloc_ = _VSTD::nullopt;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __basic_node_handle& operator=(__basic_node_handle&& __other)
+    {
+        _LIBCPP_ASSERT(
+            __alloc_ == _VSTD::nullopt ||
+            __alloc_traits::propagate_on_container_move_assignment::value ||
+            __alloc_ == __other.__alloc_,
+            "node_type with incompatible allocator passed to "
+            "node_type::operator=(node_type&&)");
+
+        __destroy_node_pointer();
+        __ptr_ = __other.__ptr_;
+
+        if (__alloc_traits::propagate_on_container_move_assignment::value ||
+            __alloc_ == _VSTD::nullopt)
+            __alloc_ = _VSTD::move(__other.__alloc_);
+
+        __other.__ptr_ = nullptr;
+        __other.__alloc_ = _VSTD::nullopt;
+
+        return *this;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    allocator_type get_allocator() const { return *__alloc_; }
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit operator bool() const { return __ptr_ != nullptr; }
+
+    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
+    bool empty() const { return __ptr_ == nullptr; }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void swap(__basic_node_handle& __other) noexcept(
+        __alloc_traits::propagate_on_container_swap::value ||
+        __alloc_traits::is_always_equal::value)
+    {
+        using _VSTD::swap;
+        swap(__ptr_, __other.__ptr_);
+        if (__alloc_traits::propagate_on_container_swap::value ||
+            __alloc_ == _VSTD::nullopt || __other.__alloc_ == _VSTD::nullopt)
+            swap(__alloc_, __other.__alloc_);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    friend void swap(__basic_node_handle& __a, __basic_node_handle& __b)
+        noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); }
+
+    _LIBCPP_INLINE_VISIBILITY
+    ~__basic_node_handle()
+    {
+        __destroy_node_pointer();
+    }
+};
+
+template <class _NodeType, class _Derived>
+struct __set_node_handle_specifics
+{
+    typedef typename _NodeType::__node_value_type value_type;
+
+    _LIBCPP_INLINE_VISIBILITY
+    value_type& value() const
+    {
+        return static_cast<_Derived const*>(this)->__ptr_->__value_;
+    }
+};
+
+template <class _NodeType, class _Derived>
+struct __map_node_handle_specifics
+{
+    typedef typename _NodeType::__node_value_type::key_type key_type;
+    typedef typename _NodeType::__node_value_type::mapped_type mapped_type;
+
+    _LIBCPP_INLINE_VISIBILITY
+    key_type& key() const
+    {
+        return static_cast<_Derived const*>(this)->
+            __ptr_->__value_.__ref().first;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    mapped_type& mapped() const
+    {
+        return static_cast<_Derived const*>(this)->
+            __ptr_->__value_.__ref().second;
+    }
+};
+
+template <class _NodeType, class _Alloc>
+using __set_node_handle =
+    __basic_node_handle< _NodeType, _Alloc, __set_node_handle_specifics>;
+
+template <class _NodeType, class _Alloc>
+using __map_node_handle =
+    __basic_node_handle< _NodeType, _Alloc, __map_node_handle_specifics>;
+
+template <class _Iterator, class _NodeType>
+_LIBCPP_TEMPLATE_VIS
+struct __insert_return_type
+{
+    _Iterator position;
+    bool inserted;
+    _NodeType node;
+};
+
+#endif // _LIBCPP_STD_VER > 14
+
+_LIBCPP_END_NAMESPACE_STD
+_LIBCPP_POP_MACROS
+
+#endif

include/__tree

void operator()(pointer __p) _NOEXCEPT
             __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
         if (__p)
             __alloc_traits::deallocate(__na_, __p, 1);
     }
 
     template <class> friend class __map_node_destructor;
 };
 
+#if _LIBCPP_STD_VER > 14
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+template <class _Tp, class _VoidPtr, class _Alloc>
+struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>
+    : __tree_node_destructor<_Alloc>
+{
+    using __tree_node_destructor<_Alloc>::__tree_node_destructor;
+};
+#endif
 
 template <class _Tp, class _NodePtr, class _DiffType>
 class _LIBCPP_TEMPLATE_VIS __tree_iterator
 {
     typedef __tree_node_types<_NodePtr>                     _NodeTypes;
     typedef _NodePtr                                        __node_pointer;
     typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
     typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;
#endif // !_LIBCPP_CXX03_LANG
 
     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
     iterator             __node_insert_unique(const_iterator __p,
                                               __node_pointer __nd);
 
     iterator __node_insert_multi(__node_pointer __nd);
     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
+
+    _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer);
+
+#if _LIBCPP_STD_VER > 14
+    template <class _NodeHandle, class _InsertReturnType>
+    _LIBCPP_INLINE_VISIBILITY
+    _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(_NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
+
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract(key_type const&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract(const_iterator);
+#endif
+
     iterator erase(const_iterator __p);
     iterator erase(const_iterator __f, const_iterator __l);
     template <class _Key>
         size_type __erase_unique(const _Key& __k);
     template <class _Key>
         size_type __erase_multi(const _Key& __k);
 
     void __insert_node_at(__parent_pointer     __parent,
__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
     __parent_pointer __parent;
     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
     return iterator(__nd);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
-__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr)
 {
-    __node_pointer __np = __p.__get_np();
-    iterator __r(__p.__ptr_);
+    iterator __r(__ptr);
     ++__r;
-    if (__begin_node() == __p.__ptr_)
+    if (__begin_node() == __ptr)
         __begin_node() = __r.__ptr_;
     --size();
-    __node_allocator& __na = __node_alloc();
     __tree_remove(__end_node()->__left_,
-                  static_cast<__node_base_pointer>(__np));
+                  static_cast<__node_base_pointer>(__ptr));
+    return __r;
+}
+
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle, class _InsertReturnType>
+_LIBCPP_INLINE_VISIBILITY
+_InsertReturnType
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+    _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return _InsertReturnType{end(), false, _NodeHandle()};
+
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_equal(__parent,
+                                                __ptr->__value_);
+    if (__child != nullptr)
+        return _InsertReturnType{
+            iterator(static_cast<__node_pointer>(__child)),
+            false, _VSTD::move(__nh)};
+
+    __insert_node_at(__parent, __child,
+                     static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer __dummy;
+    __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy,
+                                                __ptr->__value_);
+    __node_pointer __r = static_cast<__node_pointer>(__child);
+    if (__child == nullptr)
+    {
+        __insert_node_at(__parent, __child,
+                         static_cast<__node_base_pointer>(__ptr));
+        __r = __ptr;
+        __nh.__release();
+    }
+    return iterator(__r);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key)
+{
+    iterator __it = find(__key);
+    if (__it == end())
+        return _NodeHandle();
+    return __node_handle_extract<_NodeHandle>(__it);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p)
+{
+    __node_pointer __np = __p.__get_np();
+    __remove_node_pointer(__np);
+    return _NodeHandle(__np, __alloc());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_leaf_high(
+        __parent, _NodeTypes::__get_key(__ptr->__value_));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return iterator(__ptr);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    __node_pointer __ptr = __nh.__ptr_;
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_leaf(__hint, __parent,
+                                               _NodeTypes::__get_key(__ptr->__value_));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return iterator(__ptr);
+}
+
+#endif  // _LIBCPP_STD_VER > 14
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+{
+    __node_pointer __np = __p.__get_np();
+    iterator __r = __remove_node_pointer(__np);
+    __node_allocator& __na = __node_alloc();
     __node_traits::destroy(__na, _NodeTypes::__get_ptr(
         const_cast<__node_value_type&>(*__p)));
     __node_traits::deallocate(__na, __np, 1);
     return __r;
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator

include/map

public:
     typedef typename allocator_type::const_pointer   const_pointer;
     typedef typename allocator_type::size_type       size_type;
     typedef typename allocator_type::difference_type difference_type;
 
     typedef implementation-defined                   iterator;
     typedef implementation-defined                   const_iterator;
     typedef std::reverse_iterator<iterator>          reverse_iterator;
     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
+    typedef unspecified                              node_type;              // C++17
+    typedef INSERT_RETURN_TYPE<iterator, node_type>  insert_return_type;     // C++17
 
     class value_compare
         : public binary_function<value_type, value_type, bool>
     {
         friend class map;
     protected:
         key_compare comp;
 
~map();
     iterator insert(const_iterator position, const value_type& v);
     iterator insert(const_iterator position,       value_type&& v);                   // C++17
     template <class P>
         iterator insert(const_iterator position, P&& p);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type> il);
 
+    node_type extract(const_iterator position);                                       // C++17
+    node_type extract(const key_type& x);                                             // C++17
+    insert_return_type insert(node_type&& nh);                                        // C++17
+    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
+
     template <class... Args>
         pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17
     template <class... Args>
         pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17
     template <class... Args>
         iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
     template <class... Args>
         iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17
public:
     typedef typename allocator_type::difference_type difference_type;
     typedef typename allocator_type::pointer         pointer;
     typedef typename allocator_type::const_pointer   const_pointer;
 
     typedef implementation-defined                   iterator;
     typedef implementation-defined                   const_iterator;
     typedef std::reverse_iterator<iterator>          reverse_iterator;
     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
+    typedef unspecified                              node_type;              // C++17
 
     class value_compare
         : public binary_function<value_type,value_type,bool>
     {
         friend class multimap;
     protected:
         key_compare comp;
         value_compare(key_compare c);
public:
     iterator insert(const_iterator position, const value_type& v);
     iterator insert(const_iterator position,       value_type&& v);                   // C++17
     template <class P>
         iterator insert(const_iterator position, P&& p);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type> il);
 
+    node_type extract(const_iterator position);                                       // C++17
+    node_type extract(const key_type& x);                                             // C++17
+    iterator insert(node_type&& nh);                                                  // C++17
+    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
+
     iterator  erase(const_iterator position);
     iterator  erase(iterator position); // C++14
     size_type erase(const key_type& k);
     iterator  erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
     void swap(multimap& m)
         noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
swap(multimap<Key, T, Compare, Allocator>& x,
     noexcept(noexcept(x.swap(y)));
 
 }  // std
 
 */
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <iterator>
 #include <memory>
 #include <utility>
 #include <functional>
 #include <initializer_list>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
public:
     typedef typename __alloc_traits::const_pointer         const_pointer;
     typedef typename __alloc_traits::size_type             size_type;
     typedef typename __alloc_traits::difference_type       difference_type;
     typedef __map_iterator<typename __base::iterator>             iterator;
     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     map()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(__vc(key_compare())) {}
 
#endif // _LIBCPP_STD_VER > 14
     size_type erase(const key_type& __k)
         {return __tree_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f.__i_, __l.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__tree_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to map::insert()");
+        return __tree_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to map::insert()");
+        return __tree_.template __node_handle_insert_unique<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract<node_type>(__it.__i_);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(map& __m)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__m.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY
     iterator find(const key_type& __k)             {return __tree_.find(__k);}
     _LIBCPP_INLINE_VISIBILITY
public:
     typedef typename __alloc_traits::const_pointer         const_pointer;
     typedef typename __alloc_traits::size_type             size_type;
     typedef typename __alloc_traits::difference_type       difference_type;
     typedef __map_iterator<typename __base::iterator>      iterator;
     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     multimap()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(__vc(key_compare())) {}
 
#endif  // _LIBCPP_CXX03_LANG
     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f.__i_, __l.__i_);}
+
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to multimap::insert()");
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to multimap::insert()");
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract<node_type>(
+            __it.__i_);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void clear() {__tree_.clear();}
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(multimap& __m)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__m.__tree_);}
 

include/module.modulemap

module std [system] {
   module __mutex_base { header "__mutex_base" export * }
   module __split_buffer { header "__split_buffer" export * }
   module __sso_allocator { header "__sso_allocator" export * }
   module __std_stream { header "__std_stream" export * }
   module __string { header "__string" export * }
   module __tree { header "__tree" export * }
   module __tuple { header "__tuple" export * }
   module __undef_macros { header "__undef_macros" export * }
+  module __node_handle { header "__node_handle" export * }
 
   module experimental {
     requires cplusplus11
 
     module algorithm {
       header "experimental/algorithm"
       export *
     }

include/set

public:
     typedef typename allocator_type::difference_type difference_type;
     typedef typename allocator_type::pointer         pointer;
     typedef typename allocator_type::const_pointer   const_pointer;
 
     typedef implementation-defined                   iterator;
     typedef implementation-defined                   const_iterator;
     typedef std::reverse_iterator<iterator>          reverse_iterator;
     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
+    typedef unspecified                              node_type;               // C++17
+    typedef INSERT_RETURN_TYPE<iterator, node_type>  insert_return_type;      // C++17
 
     // construct/copy/destroy:
     set()
         noexcept(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value);
     explicit set(const value_compare& comp);
public:
     pair<iterator,bool> insert(const value_type& v);
     pair<iterator,bool> insert(value_type&& v);
     iterator insert(const_iterator position, const value_type& v);
     iterator insert(const_iterator position, value_type&& v);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type> il);
 
+    node_type extract(const_iterator position);                                       // C++17
+    node_type extract(const key_type& x);                                             // C++17
+    insert_return_type insert(node_type&& nh);                                        // C++17
+    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
+
     iterator  erase(const_iterator position);
     iterator  erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator  erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
     void swap(set& s)
         noexcept(
public:
     typedef typename allocator_type::difference_type difference_type;
     typedef typename allocator_type::pointer         pointer;
     typedef typename allocator_type::const_pointer   const_pointer;
 
     typedef implementation-defined                   iterator;
     typedef implementation-defined                   const_iterator;
     typedef std::reverse_iterator<iterator>          reverse_iterator;
     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
+    typedef unspecified                              node_type;               // C++17
 
     // construct/copy/destroy:
     multiset()
         noexcept(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value);
     explicit multiset(const value_compare& comp);
public:
     iterator insert(const value_type& v);
     iterator insert(value_type&& v);
     iterator insert(const_iterator position, const value_type& v);
     iterator insert(const_iterator position, value_type&& v);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type> il);
 
+    node_type extract(const_iterator position);                                       // C++17
+    node_type extract(const key_type& x);                                             // C++17
+    iterator insert(node_type&& nh);                                                  // C++17
+    iterator insert(const_iterator hint, node_type&& nh);                             // C++17
+
     iterator  erase(const_iterator position);
     iterator  erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator  erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
     void swap(multiset& s)
         noexcept(
swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
     noexcept(noexcept(x.swap(y)));
 
 }  // std
 
 */
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <functional>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
public:
     typedef typename __base::const_pointer         const_pointer;
     typedef typename __base::size_type             size_type;
     typedef typename __base::difference_type       difference_type;
     typedef typename __base::const_iterator        iterator;
     typedef typename __base::const_iterator        const_iterator;
     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     set()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(value_compare()) {}
 
#endif  // _LIBCPP_CXX03_LANG
     size_type erase(const key_type& __k)
         {return __tree_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f, __l);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__tree_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to set::insert()");
+        return __tree_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to set::insert()");
+        return __tree_.template __node_handle_insert_unique<node_type>(
+            __hint, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract<node_type>(__it);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__s.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY
     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
     _LIBCPP_INLINE_VISIBILITY
     key_compare    key_comp()      const {return __tree_.value_comp();}
public:
     typedef typename __base::const_pointer         const_pointer;
     typedef typename __base::size_type             size_type;
     typedef typename __base::difference_type       difference_type;
     typedef typename __base::const_iterator        iterator;
     typedef typename __base::const_iterator        const_iterator;
     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
+#endif
+
     // construct/copy/destroy:
     _LIBCPP_INLINE_VISIBILITY
     multiset()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(value_compare()) {}
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f, __l);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__tree_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to multiset::insert()");
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to multiset::insert()");
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            __hint, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract<node_type>(__it);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(multiset& __s)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__s.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY
     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
     _LIBCPP_INLINE_VISIBILITY

include/unordered_map

public:
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
     typedef /unspecified/ iterator;
     typedef /unspecified/ const_iterator;
     typedef /unspecified/ local_iterator;
     typedef /unspecified/ const_local_iterator;
 
+    typedef unspecified                             node_type;            // C++17
+    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
+
     unordered_map()
         noexcept(
             is_nothrow_default_constructible<hasher>::value &&
             is_nothrow_default_constructible<key_equal>::value &&
             is_nothrow_default_constructible<allocator_type>::value);
     explicit unordered_map(size_type n, const hasher& hf = hasher(),
                            const key_equal& eql = key_equal(),
                            const allocator_type& a = allocator_type());
template <class P>
         pair<iterator, bool> insert(P&& obj);
     iterator insert(const_iterator hint, const value_type& obj);
     template <class P>
         iterator insert(const_iterator hint, P&& obj);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type>);
 
+    node_type extract(const_iterator position);                                       // C++17
+    node_type extract(const key_type& x);                                             // C++17
+    insert_return_type insert(node_type&& nh);                                        // C++17
+    iterator           insert(const_iterator hint, node_type&& nh);                   // C++17
+
     template <class... Args>
         pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17
     template <class... Args>
         pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17
     template <class... Args>
         iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
     template <class... Args>
         iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17
public:
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
     typedef /unspecified/ iterator;
     typedef /unspecified/ const_iterator;
     typedef /unspecified/ local_iterator;
     typedef /unspecified/ const_local_iterator;
 
+    typedef unspecified node_type;    // C++17
+
     unordered_multimap()
         noexcept(
             is_nothrow_default_constructible<hasher>::value &&
             is_nothrow_default_constructible<key_equal>::value &&
             is_nothrow_default_constructible<allocator_type>::value);
     explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
                            const key_equal& eql = key_equal(),
                            const allocator_type& a = allocator_type());
template <class P>
         iterator insert(P&& obj);
     iterator insert(const_iterator hint, const value_type& obj);
     template <class P>
         iterator insert(const_iterator hint, P&& obj);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type>);
 
+    node_type extract(const_iterator position);                // C++17
+    node_type extract(const key_type& x);                      // C++17
+    iterator insert(node_type&& nh);                           // C++17
+    iterator insert(const_iterator hint, node_type&& nh);      // C++17
+
     iterator erase(const_iterator position);
     iterator erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
     void swap(unordered_multimap&)
         noexcept(
operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
                const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
 }  // std
 
 */
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 #include <stdexcept>
 #include <tuple>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
public:
     typedef typename __table::size_type              size_type;
     typedef typename __table::difference_type        difference_type;
 
     typedef __hash_map_iterator<typename __table::iterator>       iterator;
     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_map()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif // _LIBCPP_STD_VER > 14
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first.__i_, __last.__i_);}
     _LIBCPP_INLINE_VISIBILITY
         void clear() _NOEXCEPT {__table_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_map::insert()");
+        return __table_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_map::insert()");
+        return __table_.template __node_handle_insert_unique<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __table_.template __node_handle_extract<node_type>(
+            __it.__i_);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_map& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         { __table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
     hasher hash_function() const
         {return __table_.hash_function().hash_function();}
public:
     typedef typename __table::size_type              size_type;
     typedef typename __table::difference_type        difference_type;
 
     typedef __hash_map_iterator<typename __table::iterator>       iterator;
     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<__node, allocator_type> node_type;
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first.__i_, __last.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__table_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_multimap::insert()");
+        return __table_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_multimap::insert()");
+        return __table_.template __node_handle_insert_multi<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __table_.template __node_handle_extract<node_type>(
+            __it.__i_);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_multimap& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         {__table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
     hasher hash_function() const
         {return __table_.hash_function().hash_function();}

include/unordered_set

public:
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
     typedef /unspecified/ iterator;
     typedef /unspecified/ const_iterator;
     typedef /unspecified/ local_iterator;
     typedef /unspecified/ const_local_iterator;
 
+    typedef unspecified node_type unspecified;                            // C++17
+    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
+
     unordered_set()
         noexcept(
             is_nothrow_default_constructible<hasher>::value &&
             is_nothrow_default_constructible<key_equal>::value &&
             is_nothrow_default_constructible<allocator_type>::value);
     explicit unordered_set(size_type n, const hasher& hf = hasher(),
                            const key_equal& eql = key_equal(),
                            const allocator_type& a = allocator_type());
public:
     pair<iterator, bool> insert(const value_type& obj);
     pair<iterator, bool> insert(value_type&& obj);
     iterator insert(const_iterator hint, const value_type& obj);
     iterator insert(const_iterator hint, value_type&& obj);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type>);
 
+    node_type extract(const_iterator position);                       // C++17
+    node_type extract(const key_type& x);                             // C++17
+    insert_return_type insert(node_type&& nh);                        // C++17
+    iterator           insert(const_iterator hint, node_type&& nh);   // C++17
+
     iterator erase(const_iterator position);
     iterator erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
     void swap(unordered_set&)
        noexcept(allocator_traits<Allocator>::is_always_equal::value &&
public:
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
     typedef /unspecified/ iterator;
     typedef /unspecified/ const_iterator;
     typedef /unspecified/ local_iterator;
     typedef /unspecified/ const_local_iterator;
 
+    typedef unspecified node_type unspecified;   // C++17
+
     unordered_multiset()
         noexcept(
             is_nothrow_default_constructible<hasher>::value &&
             is_nothrow_default_constructible<key_equal>::value &&
             is_nothrow_default_constructible<allocator_type>::value);
     explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
                            const key_equal& eql = key_equal(),
                            const allocator_type& a = allocator_type());
public:
     iterator insert(const value_type& obj);
     iterator insert(value_type&& obj);
     iterator insert(const_iterator hint, const value_type& obj);
     iterator insert(const_iterator hint, value_type&& obj);
     template <class InputIterator>
         void insert(InputIterator first, InputIterator last);
     void insert(initializer_list<value_type>);
 
+    node_type extract(const_iterator position);             // C++17
+    node_type extract(const key_type& x);                   // C++17
+    iterator insert(node_type&& nh);                        // C++17
+    iterator insert(const_iterator hint, node_type&& nh);   // C++17
+
     iterator erase(const_iterator position);
     iterator erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
     void swap(unordered_multiset&)
        noexcept(allocator_traits<Allocator>::is_always_equal::value &&
template <class Value, class Hash, class Pred, class Alloc>
     operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 }  // std
 
 */
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
public:
     typedef typename __table::size_type       size_type;
     typedef typename __table::difference_type difference_type;
 
     typedef typename __table::const_iterator       iterator;
     typedef typename __table::const_iterator       const_iterator;
     typedef typename __table::const_local_iterator local_iterator;
     typedef typename __table::const_local_iterator const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_set()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first, __last);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__table_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_set::insert()");
+        return __table_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __h, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_set::insert()");
+        return __table_.template __node_handle_insert_unique<node_type>(
+            __h, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __table_.template __node_handle_extract<node_type>(__it);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_set& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         {__table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
     hasher hash_function() const {return __table_.hash_function();}
     _LIBCPP_INLINE_VISIBILITY
public:
     typedef typename __table::size_type       size_type;
     typedef typename __table::difference_type difference_type;
 
     typedef typename __table::const_iterator       iterator;
     typedef typename __table::const_iterator       const_iterator;
     typedef typename __table::const_local_iterator local_iterator;
     typedef typename __table::const_local_iterator const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multiset()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     iterator insert(const_iterator __p, const value_type& __x)
         {return __table_.__insert_multi(__p, __x);}
 
     template <class _InputIterator>
         _LIBCPP_INLINE_VISIBILITY
         void insert(_InputIterator __first, _InputIterator __last);
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_multiset::insert()");
+        return __table_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_multiset::insert()");
+        return __table_.template __node_handle_insert_multi<node_type>(
+            __hint, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __position)
+    {
+        return __table_.template __node_handle_extract<node_type>(
+            __position);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract<node_type>(__key);
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __p) {return __table_.erase(__p);}
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first, __last);}
     _LIBCPP_INLINE_VISIBILITY

test/std/containers/associative/map/map.modifiers/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// node_type extract(const_iterator);
+
+#include <map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    auto some_key = c.cbegin()->first;
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = first->first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.key() == key_value);
+        t.key() = some_key;
+        assert(t.key() == some_key);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using map_type = std::map<int, int>;
+        map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        test(m);
+    }
+
+    {
+        std::map<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        assert(Counter_base::gConstructed == 12);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::map<int, int, std::less<int>,
+                     min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        test(m);
+    }
+}

test/std/containers/associative/map/map.modifiers/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// node_type extract(key_type const&);
+
+#include <map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.key() == *copy);
+        t.key() = *first; // We should be able to mutate key.
+        assert(t.key() == *first);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::map<int, int> m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::map<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 12+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::map<int, int, std::less<int>,
+                     min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// insert_return_type insert(node_type&&);
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto p = c.insert({key, mapped});
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        typename Container::insert_return_type irt = c.insert(std::move(node));
+        assert(node.empty());
+        assert(irt.inserted);
+        assert(irt.node.empty());
+        assert(irt.position->first == i && irt.position->second == i + 1);
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto irt = c.insert(std::move(def));
+        assert(def.empty());
+        assert(!irt.inserted);
+        assert(irt.node.empty());
+        assert(irt.position == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0, 42);
+        auto irt = c.insert(std::move(dupl));
+        assert(dupl.empty());
+        assert(!irt.inserted);
+        assert(!irt.node.empty());
+        assert(irt.position == c.find(0));
+        assert(irt.node.key() == 0 && irt.node.mapped() == 42);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c[i] == i + 1);
+    }
+}
+
+int main()
+{
+    std::map<int, int> m;
+    test(m);
+    std::map<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <map>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto p = c.insert({key, mapped});
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(node.empty());
+        assert(prev + 1 == c.size());
+        assert(it->first == i);
+        assert(it->second == i + 1);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c[i] == i + 1);
+    }
+}
+
+int main()
+{
+    std::map<int, int> m;
+    test(m);
+    std::map<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/associative/multimap/multimap.modifiers/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+// node_type extract(const_iterator);
+
+#include <map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    auto some_key = c.cbegin()->first;
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = first->first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.key() == key_value);
+        t.key() = some_key;
+        assert(t.key() == some_key);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using map_type = std::multimap<int, int>;
+        map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        test(m);
+    }
+
+    {
+        std::multimap<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        assert(Counter_base::gConstructed == 12);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::multimap<int, int, std::less<int>,
+                     min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        test(m);
+    }
+}

test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+// node_type extract(key_type const&);
+
+#include <map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.key() == *copy);
+        t.key() = *first; // We should be able to mutate key.
+        assert(t.key() == *first);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::multimap<int, int> m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::multimap<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 12+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::multimap<int, int, std::less<int>,
+                          min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/associative/multimap/multimap.modifiers/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+// iterator insert(node_type&&);
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto it = c.insert({key, mapped});
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        typename Container::iterator it = c.insert(std::move(node));
+        assert(node.empty());
+        assert(it == c.find(i) && it != c.end());
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto it = c.insert(std::move(def));
+        assert(def.empty());
+        assert(it == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0, 42);
+        auto it = c.insert(std::move(dupl));
+        assert(dupl.empty());
+        assert(it != c.end());
+        assert(it->second == 42);
+    }
+
+    assert(c.size() == 11);
+    assert(c.count(0) == 2);
+    for (int i = 1; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c.find(i)->second == i + 1);
+    }
+}
+
+int main()
+{
+    std::multimap<int, int> m;
+    test(m);
+    std::multimap<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/associative/multimap/multimap.modifiers/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <map>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto it = c.insert({key, mapped});
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(node.empty());
+        assert(prev + 1 == c.size());
+        assert(it == c.find(i));
+        assert(it->first == i);
+        assert(it->second == i + 1);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c.find(i)->second == i + 1);
+    }
+}
+
+int main()
+{
+    std::multimap<int, int> m;
+    test(m);
+    std::multimap<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/associative/multiset/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+// node_type extract(const_iterator);
+
+#include <set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = *first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.value() == key_value);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using set_type = std::multiset<int>;
+        set_type m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+
+    {
+        std::multiset<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        assert(Counter_base::gConstructed == 6);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::multiset<int, std::less<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+}

test/std/containers/associative/multiset/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+// node_type extract(key_type const&);
+
+#include <set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.value() == *copy);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::multiset<int> m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::multiset<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 6+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::multiset<int, std::less<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/associative/multiset/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+// iterator insert(node_type&&);
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto it = c.insert(key);
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        typename Container::iterator it = c.insert(std::move(node));
+        assert(node.empty());
+        assert(it == c.find(i) && it != c.end());
+        assert(*it == i);
+        assert(node.empty());
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto it = c.insert(std::move(def));
+        assert(def.empty());
+        assert(it == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0);
+        auto it = c.insert(std::move(dupl));
+        assert(*it == 0);
+    }
+
+    assert(c.size() == 11);
+
+    assert(c.count(0) == 2);
+    for (int i = 1; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::multiset<int> m;
+    test(m);
+    std::multiset<int, std::less<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/std/containers/associative/multiset/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <set>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto it = c.insert(key);
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(prev + 1 == c.size());
+        assert(*it == i);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::multiset<int> m;
+    test(m);
+    std::multiset<int, std::less<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/std/containers/associative/set/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+// node_type extract(const_iterator);
+
+#include <set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = *first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.value() == key_value);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using set_type = std::set<int>;
+        set_type m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+
+    {
+        std::set<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        assert(Counter_base::gConstructed == 6);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::set<int, std::less<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+}

test/std/containers/associative/set/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+// node_type extract(key_type const&);
+
+#include <set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.value() == *copy);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::set<int> m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::set<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 6+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::set<int, std::less<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/associative/set/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+// insert_return_type insert(node_type&&);
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto p = c.insert(key);
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        typename Container::insert_return_type irt = c.insert(std::move(node));
+        assert(node.empty());
+        assert(irt.inserted);
+        assert(irt.node.empty());
+        assert(*irt.position == i);
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto irt = c.insert(std::move(def));
+        assert(def.empty());
+        assert(!irt.inserted);
+        assert(irt.node.empty());
+        assert(irt.position == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0);
+        auto irt = c.insert(std::move(dupl));
+        assert(dupl.empty());
+        assert(!irt.inserted);
+        assert(!irt.node.empty());
+        assert(irt.position == c.find(0));
+        assert(irt.node.value() == 0);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::set<int> m;
+    test(m);
+    std::set<int, std::less<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/std/containers/associative/set/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <set>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto p = c.insert(key);
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(node.empty());
+        assert(prev + 1 == c.size());
+        assert(*it == i);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::set<int> m;
+    test(m);
+    std::set<int, std::less<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/std/containers/container.node/node_handle.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+#include <unordered_set>
+#include <unordered_map>
+#include <set>
+#include <map>
+#include "min_allocator.h"
+
+using namespace std;
+
+// [container.node.overview] Table 83.
+template <class K, class T, class C1, class C2, class H1, class H2, class E1, class E2, class A_set, class A_map>
+struct node_compatibility_table
+{
+    static constexpr bool value =
+        is_same_v<typename map<K, T, C1, A_map>::node_type,               typename map<K, T, C2, A_map>::node_type> &&
+        is_same_v<typename map<K, T, C1, A_map>::node_type,               typename multimap<K, T, C2, A_map>::node_type> &&
+        is_same_v<typename set<K, C1, A_set>::node_type,                  typename set<K, C2, A_set>::node_type> &&
+        is_same_v<typename set<K, C1, A_set>::node_type,                  typename multiset<K, C2, A_set>::node_type> &&
+        is_same_v<typename unordered_map<K, T, H1, E1, A_map>::node_type, typename unordered_map<K, T, H2, E2, A_map>::node_type> &&
+        is_same_v<typename unordered_map<K, T, H1, E1, A_map>::node_type, typename unordered_multimap<K, T, H2, E2, A_map>::node_type> &&
+        is_same_v<typename unordered_set<K, H1, E1, A_set>::node_type,    typename unordered_set<K, H2, E2, A_set>::node_type> &&
+        is_same_v<typename unordered_set<K, H1, E1, A_set>::node_type,    typename unordered_multiset<K, H2, E2, A_set>::node_type>;
+};
+
+template <class T> struct my_hash
+{
+    using argument_type = T;
+    using result_type = size_t;
+    my_hash() = default;
+    size_t operator()(const T&) const {return 0;}
+};
+
+template <class T> struct my_compare
+{
+    my_compare() = default;
+    bool operator()(const T&, const T&) const {return true;}
+};
+
+template <class T> struct my_equal
+{
+    my_equal() = default;
+    bool operator()(const T&, const T&) const {return true;}
+};
+
+struct Static
+{
+    Static() = default;
+    Static(const Static&) = delete;
+    Static(Static&&) = delete;
+    Static& operator=(const Static&) = delete;
+    Static& operator=(Static&&) = delete;
+};
+
+namespace std
+{
+template <> struct hash<Static>
+{
+    using argument_type = Static;
+    using result_type = size_t;
+    hash() = default;
+    size_t operator()(const Static&) const;
+};
+}
+
+static_assert(node_compatibility_table<
+                  int, int, std::less<int>, std::less<int>, std::hash<int>,
+                  std::hash<int>, std::equal_to<int>, std::equal_to<int>,
+                  std::allocator<int>,
+                  std::allocator<std::pair<const int, int>>>::value,
+              "");
+
+static_assert(
+    node_compatibility_table<int, int, std::less<int>, my_compare<int>,
+                             std::hash<int>, my_hash<int>, std::equal_to<int>,
+                             my_equal<int>, allocator<int>,
+                             allocator<std::pair<const int, int>>>::value,
+    "");
+
+static_assert(node_compatibility_table<
+                  Static, int, my_compare<Static>, std::less<Static>,
+                  my_hash<Static>, std::hash<Static>, my_equal<Static>,
+                  std::equal_to<Static>, min_allocator<Static>,
+                  min_allocator<std::pair<const Static, int>>>::value,
+              "");
+
+template <class Container>
+void test_node_handle_operations()
+{
+    Container c;
+
+    typename Container::node_type nt1, nt2 = c.extract(c.emplace().first);
+    assert(nt2.get_allocator() == c.get_allocator());
+    assert(!nt2.empty());
+    assert(nt1.empty());
+    std::swap(nt1, nt2);
+    assert(nt1.get_allocator() == c.get_allocator());
+    assert(nt2.empty());
+}
+
+template <class Container>
+void test_node_handle_operations_multi()
+{
+    Container c;
+
+    typename Container::node_type nt1, nt2 = c.extract(c.emplace());
+    assert(nt2.get_allocator() == c.get_allocator());
+    assert(!nt2.empty());
+    assert(nt1.empty());
+    std::swap(nt1, nt2);
+    assert(nt1.get_allocator() == c.get_allocator());
+    assert(nt2.empty());
+}
+
+template <class Container>
+void test_insert_return_type()
+{
+    using irt_type = typename Container::insert_return_type;
+}
+
+int main()
+{
+    test_node_handle_operations<std::map<int, int>>();
+    test_node_handle_operations_multi<std::multimap<int, int>>();
+    test_node_handle_operations<std::set<int>>();
+    test_node_handle_operations_multi<std::multiset<int>>();
+    test_node_handle_operations<std::unordered_map<int, int>>();
+    test_node_handle_operations_multi<std::unordered_multimap<int, int>>();
+    test_node_handle_operations<std::unordered_set<int>>();
+    test_node_handle_operations_multi<std::unordered_multiset<int>>();
+
+    test_insert_return_type<std::map<int, int>>();
+    test_insert_return_type<std::set<int>>();
+    test_insert_return_type<std::unordered_map<int, int>>();
+    test_insert_return_type<std::unordered_set<int>>();
+}

test/std/containers/unord/unord.map/unord.map.modifiers/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+// node_type extract(const_iterator);
+
+#include <unordered_map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    auto some_key = c.cbegin()->first;
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = first->first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.key() == key_value);
+        t.key() = some_key;
+        assert(t.key() == some_key);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using map_type = std::unordered_map<int, int>;
+        map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        test(m);
+    }
+
+    {
+        std::unordered_map<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        assert(Counter_base::gConstructed == 12);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
+                               min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        test(m);
+    }
+}

test/std/containers/unord/unord.map/unord.map.modifiers/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+// node_type extract(key_type const&);
+
+#include <unordered_map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.key() == *copy);
+        t.key() = *first; // We should be able to mutate key.
+        assert(t.key() == *first);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::unordered_map<int, int> m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::unordered_map<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 12+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
+                               min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+// insert_return_type insert(node_type&&);
+
+#include <unordered_map>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto p = c.insert({key, mapped});
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        typename Container::insert_return_type irt = c.insert(std::move(node));
+        assert(node.empty());
+        assert(irt.inserted);
+        assert(irt.node.empty());
+        assert(irt.position->first == i && irt.position->second == i + 1);
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto irt = c.insert(std::move(def));
+        assert(def.empty());
+        assert(!irt.inserted);
+        assert(irt.node.empty());
+        assert(irt.position == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0, 42);
+        auto irt = c.insert(std::move(dupl));
+        assert(dupl.empty());
+        assert(!irt.inserted);
+        assert(!irt.node.empty());
+        assert(irt.position == c.find(0));
+        assert(irt.node.key() == 0 && irt.node.mapped() == 42);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c[i] == i + 1);
+    }
+}
+
+int main()
+{
+    std::unordered_map<int, int> m;
+    test(m);
+    std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <unordered_map>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto p = c.insert({key, mapped});
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(node.empty());
+        assert(prev + 1 == c.size());
+        assert(it->first == i);
+        assert(it->second == i + 1);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c[i] == i + 1);
+    }
+}
+
+int main()
+{
+    std::unordered_map<int, int> m;
+    test(m);
+    std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// node_type extract(const_iterator);
+
+#include <unordered_map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    auto some_key = c.cbegin()->first;
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = first->first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.key() == key_value);
+        t.key() = some_key;
+        assert(t.key() == some_key);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using map_type = std::unordered_multimap<int, int>;
+        map_type m = {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        test(m);
+    }
+
+    {
+        std::unordered_multimap<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        assert(Counter_base::gConstructed == 12);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>,
+                                    min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        test(m);
+    }
+}

test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// node_type extract(key_type const&);
+
+#include <unordered_map>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.key() == *copy);
+        t.key() = *first; // We should be able to mutate key.
+        assert(t.key() == *first);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::unordered_multimap<int, int> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::unordered_multimap<Counter<int>, Counter<int>> m =
+            {{1,1}, {2,2}, {3,3}, {4,4}, {5,5}, {6,6}};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 12+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_map =
+            std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>,
+                                    min_allocator<std::pair<const int, int>>>;
+        min_alloc_map m = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// iterator insert(node_type&&);
+
+#include <unordered_map>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto it = c.insert({key, mapped});
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        typename Container::iterator it = c.insert(std::move(node));
+        assert(node.empty());
+        assert(it == c.find(i) && it != c.end());
+        assert(it->first == i && it->second == i + 1);
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto it = c.insert(std::move(def));
+        assert(def.empty());
+        assert(it == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0, 42);
+        auto it = c.insert(std::move(dupl));
+        assert(dupl.empty());
+        assert(it != c.end() && it->second == 42);
+    }
+
+    assert(c.size() == 11);
+    assert(c.count(0) == 2);
+    for (int i = 1; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c.find(i)->second == i + 1);
+    }
+}
+
+int main()
+{
+    std::unordered_multimap<int, int> m;
+    test(m);
+    std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <unordered_map>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key,
+             typename Container::mapped_type const& mapped)
+{
+    static Container c;
+    auto it = c.insert({key, mapped});
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i, i + 1);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(node.empty());
+        assert(prev + 1 == c.size());
+        assert(it->first == i);
+        assert(it->second == i + 1);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+        assert(c.find(i)->second == i + 1);
+    }
+}
+
+int main()
+{
+    std::unordered_multimap<int, int> m;
+    test(m);
+    std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> m2;
+    test(m2);
+}

test/std/containers/unord/unord.multiset/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// node_type extract(const_iterator);
+
+#include <unordered_set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = *first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.value() == key_value);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using set_type = std::unordered_multiset<int>;
+        set_type m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+
+    {
+        std::unordered_multiset<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        assert(Counter_base::gConstructed == 6);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+}

test/std/containers/unord/unord.multiset/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_multiset>
+
+// class unordered_multiset
+
+// node_type extract(key_type const&);
+
+#include <unordered_set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.value() == *copy);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::unordered_multiset<int> m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::unordered_multiset<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 6+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/unord/unord.multiset/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// iterator insert(node_type&&);
+
+#include <unordered_set>
+#include <type_traits>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto it = c.insert(key);
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        typename Container::iterator it = c.insert(std::move(node));
+        assert(node.empty());
+        assert(it == c.find(i) && it != c.end());
+        assert(*it == i);
+        assert(node.empty());
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto it = c.insert(std::move(def));
+        assert(def.empty());
+        assert(it == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0);
+        auto it = c.insert(std::move(dupl));
+        assert(*it == 0);
+    }
+
+    assert(c.size() == 11);
+    assert(c.count(0) == 2);
+    for (int i = 1; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::unordered_multiset<int> m;
+    test(m);
+    std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/std/containers/unord/unord.multiset/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <unordered_set>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto it = c.insert(key);
+    return c.extract(it);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(prev + 1 == c.size());
+        assert(*it == i);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::unordered_multiset<int> m;
+    test(m);
+    std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/std/containers/unord/unord.set/extract_iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+// node_type extract(const_iterator);
+
+#include <unordered_set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container>
+void test(Container& c)
+{
+    size_t sz = c.size();
+
+    for (auto first = c.cbegin(); first != c.cend();)
+    {
+        auto key_value = *first;
+        typename Container::node_type t = c.extract(first++);
+        --sz;
+        assert(t.value() == key_value);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+}
+
+int main()
+{
+    {
+        using set_type = std::unordered_set<int>;
+        set_type m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+
+    {
+        std::unordered_set<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        assert(Counter_base::gConstructed == 6);
+        test(m);
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::unordered_set<int, std::hash<int>, std::equal_to<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        test(m);
+    }
+}

test/std/containers/unord/unord.set/extract_key.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+// node_type extract(key_type const&);
+
+#include <unordered_set>
+#include "min_allocator.h"
+#include "Counter.h"
+
+template <class Container, class KeyTypeIter>
+void test(Container& c, KeyTypeIter first, KeyTypeIter last)
+{
+    size_t sz = c.size();
+    assert((size_t)std::distance(first, last) == sz);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(!t.empty());
+        --sz;
+        assert(t.value() == *copy);
+        assert(t.get_allocator() == c.get_allocator());
+        assert(sz == c.size());
+    }
+
+    assert(c.size() == 0);
+
+    for (KeyTypeIter copy = first; copy != last; ++copy)
+    {
+        typename Container::node_type t = c.extract(*copy);
+        assert(t.empty());
+    }
+}
+
+int main()
+{
+    {
+        std::unordered_set<int> m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+
+    {
+        std::unordered_set<Counter<int>> m = {1, 2, 3, 4, 5, 6};
+        {
+            Counter<int> keys[] = {1, 2, 3, 4, 5, 6};
+            assert(Counter_base::gConstructed == 6+6);
+            test(m, std::begin(keys), std::end(keys));
+        }
+        assert(Counter_base::gConstructed == 0);
+    }
+
+    {
+        using min_alloc_set = std::unordered_set<int, std::hash<int>, std::equal_to<int>, min_allocator<int>>;
+        min_alloc_set m = {1, 2, 3, 4, 5, 6};
+        int keys[] = {1, 2, 3, 4, 5, 6};
+        test(m, std::begin(keys), std::end(keys));
+    }
+}

test/std/containers/unord/unord.set/insert_node_type.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+// insert_return_type insert(node_type&&);
+
+#include <unordered_set>
+#include <type_traits>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto p = c.insert(key);
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        typename Container::insert_return_type irt = c.insert(std::move(node));
+        assert(node.empty());
+        assert(irt.inserted);
+        assert(irt.node.empty());
+        assert(*irt.position == i);
+    }
+
+    assert(c.size() == 10);
+
+    { // Insert empty node.
+        typename Container::node_type def;
+        auto irt = c.insert(std::move(def));
+        assert(def.empty());
+        assert(!irt.inserted);
+        assert(irt.node.empty());
+        assert(irt.position == c.end());
+    }
+
+    { // Insert duplicate node.
+        typename Container::node_type dupl = nf(0);
+        auto irt = c.insert(std::move(dupl));
+        assert(dupl.empty());
+        assert(!irt.inserted);
+        assert(!irt.node.empty());
+        assert(irt.position == c.find(0));
+        assert(irt.node.value() == 0);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::unordered_set<int> m;
+    test(m);
+    std::unordered_set<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/std/containers/unord/unord.set/insert_node_type_hint.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+// iterator insert(const_iterator hint, node_type&&);
+
+#include <unordered_set>
+#include "min_allocator.h"
+
+template <class Container>
+typename Container::node_type
+node_factory(typename Container::key_type const& key)
+{
+    static Container c;
+    auto p = c.insert(key);
+    assert(p.second);
+    return c.extract(p.first);
+}
+
+template <class Container>
+void test(Container& c)
+{
+    auto* nf = &node_factory<Container>;
+
+    for (int i = 0; i != 10; ++i)
+    {
+        typename Container::node_type node = nf(i);
+        assert(!node.empty());
+        size_t prev = c.size();
+        auto it = c.insert(c.end(), std::move(node));
+        assert(node.empty());
+        assert(prev + 1 == c.size());
+        assert(*it == i);
+    }
+
+    assert(c.size() == 10);
+
+    for (int i = 0; i != 10; ++i)
+    {
+        assert(c.count(i) == 1);
+    }
+}
+
+int main()
+{
+    std::unordered_set<int> m;
+    test(m);
+    std::unordered_set<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> m2;
+    test(m2);
+}

test/support/Counter.h

 
 template <typename T>
 class Counter : public Counter_base
 {
 public:
     Counter() : data_()                             { ++gConstructed; }
     Counter(const T &data) : data_(data)            { ++gConstructed; }
     Counter(const Counter& rhs) : data_(rhs.data_)  { ++gConstructed; }
-    Counter& operator=(const Counter& rhs)          { ++gConstructed; data_ = rhs.data_; return *this; }
+    Counter& operator=(const Counter& rhs)          { data_ = rhs.data_; return *this; }
 #if TEST_STD_VER >= 11
     Counter(Counter&& rhs) : data_(std::move(rhs.data_))  { ++gConstructed; }
     Counter& operator=(Counter&& rhs) { ++gConstructed; data_ = std::move(rhs.data_); return *this; }
 #endif
     ~Counter() { --gConstructed; }
 
     const T& get() const {return data_;}
 

 namespace std {
 
 template <class T>
 struct hash<Counter<T> >
 {
     typedef Counter<T> argument_type;
     typedef std::size_t result_type;
 
-    std::size_t operator()(const Counter<T>& x) const {return std::hash<T>(x.get());}
+    std::size_t operator()(const Counter<T>& x) const {return std::hash<T>()(x.get());}
 };
 }
 
 #endif