First half of C++17's splicing maps and sets

This commit adds a node handle type, (located in __node_handle), and adds
extract() and insert() members to all map and set types, as well as their
implementations in __tree and __hash_table.

The second half of this feature is adding merge() members, which splice nodes
in bulk from one container into another. This will be committed in a follow-up.

Differential revision: https://reviews.llvm.org/D46845

llvm-svn: 338472

43 files changed, 3214 insertions, 9 deletions

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index c5e92e4c4bd..a45b80160ec 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -11,6 +11,7 @@ set(files
   __libcpp_version
   __locale
   __mutex_base
+  __node_handle
   __nullptr
   __split_buffer
   __sso_allocator
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index 44ba268a0ec..c77de961be6 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -859,6 +859,17 @@ public:
     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>
@@ -1151,6 +1162,30 @@ public:
         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)
@@ -2126,6 +2161,91 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
 
 #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)
diff --git a/libcxx/include/__node_handle b/libcxx/include/__node_handle
new file mode 100644
index 00000000000..fe09f3c1e51
--- /dev/null
+++ b/libcxx/include/__node_handle
@@ -0,0 +1,212 @@
+// -*- 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
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 30c32f16393..af9b9616df8 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -796,6 +796,16 @@ public:
     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
@@ -1338,6 +1348,33 @@ public:
     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>
@@ -2347,17 +2384,138 @@ __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
 
 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);
diff --git a/libcxx/include/map b/libcxx/include/map
index 97ce4d0b18c..559ec484aca 100644
--- a/libcxx/include/map
+++ b/libcxx/include/map
@@ -40,6 +40,8 @@ public:
     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>
@@ -137,6 +139,11 @@ public:
         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>
@@ -260,6 +267,7 @@ public:
     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>
@@ -349,6 +357,11 @@ public:
         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);
@@ -440,6 +453,7 @@ swap(multimap<Key, T, Compare, Allocator>& x,
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <iterator>
 #include <memory>
 #include <utility>
@@ -906,6 +920,11 @@ public:
     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_(
@@ -1253,6 +1272,35 @@ public:
     _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)
@@ -1562,6 +1610,10 @@ public:
     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_(
@@ -1800,6 +1852,37 @@ public:
     _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();}
 
diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap
index 127a42b0633..3b66390fb8b 100644
--- a/libcxx/include/module.modulemap
+++ b/libcxx/include/module.modulemap
@@ -498,6 +498,7 @@ module std [system] {
   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
diff --git a/libcxx/include/set b/libcxx/include/set
index 94db8c79d10..108a9e97f88 100644
--- a/libcxx/include/set
+++ b/libcxx/include/set
@@ -40,6 +40,8 @@ public:
     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()
@@ -115,6 +117,11 @@ public:
         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);
@@ -222,6 +229,7 @@ public:
     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()
@@ -297,6 +305,11 @@ public:
         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);
@@ -387,6 +400,7 @@ swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <functional>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -429,6 +443,11 @@ public:
     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_(
@@ -634,6 +653,35 @@ public:
     _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_);}
@@ -838,6 +886,10 @@ public:
     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()
@@ -1042,6 +1094,35 @@ public:
     _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)
diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map
index f34d82efdc3..348f57923b5 100644
--- a/libcxx/include/unordered_map
+++ b/libcxx/include/unordered_map
@@ -44,6 +44,9 @@ public:
     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 &&
@@ -122,6 +125,11 @@ public:
         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>
@@ -226,6 +234,8 @@ public:
     typedef /unspecified/ local_iterator;
     typedef /unspecified/ const_local_iterator;
 
+    typedef unspecified node_type;    // C++17
+
     unordered_multimap()
         noexcept(
             is_nothrow_default_constructible<hasher>::value &&
@@ -304,6 +314,11 @@ public:
         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);
@@ -367,6 +382,7 @@ template <class Key, class T, class Hash, class Pred, class Alloc>
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 #include <stdexcept>
 #include <tuple>
@@ -843,6 +859,11 @@ public:
     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)
@@ -1136,7 +1157,37 @@ public:
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first.__i_, __last.__i_);}
     _LIBCPP_INLINE_VISIBILITY
-    void clear() _NOEXCEPT {__table_.clear();}
+        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)
@@ -1590,6 +1641,10 @@ public:
     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)
@@ -1763,6 +1818,36 @@ public:
     _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)
diff --git a/libcxx/include/unordered_set b/libcxx/include/unordered_set
index 3ae024a45ee..9b8560da494 100644
--- a/libcxx/include/unordered_set
+++ b/libcxx/include/unordered_set
@@ -43,6 +43,9 @@ public:
     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 &&
@@ -113,6 +116,11 @@ public:
         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);
@@ -191,6 +199,8 @@ public:
     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 &&
@@ -261,6 +271,11 @@ public:
         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);
@@ -321,6 +336,7 @@ template <class Value, class Hash, class Pred, class Alloc>
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 
 #include <__debug>
@@ -363,6 +379,11 @@ public:
     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)
@@ -541,6 +562,35 @@ public:
     _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)
@@ -883,6 +933,10 @@ public:
     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)
@@ -1019,6 +1073,36 @@ public:
         _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
diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/extract_iterator.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..ea7fd890764
--- /dev/null
+++ b/libcxx/test/std/containers/associative/map/map.modifiers/extract_iterator.pass.cpp
@@ -0,0 +1,67 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/extract_key.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/extract_key.pass.cpp
new file mode 100644
index 00000000000..41cd09300b2
--- /dev/null
+++ b/libcxx/test/std/containers/associative/map/map.modifiers/extract_key.pass.cpp
@@ -0,0 +1,76 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..cc1704c3087
--- /dev/null
+++ b/libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type.pass.cpp
@@ -0,0 +1,85 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..3c6b3e31af4
--- /dev/null
+++ b/libcxx/test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp
@@ -0,0 +1,64 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_iterator.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..3e00d2b98d7
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_iterator.pass.cpp
@@ -0,0 +1,67 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp
new file mode 100644
index 00000000000..ca69cca6b0e
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/extract_key.pass.cpp
@@ -0,0 +1,76 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_node_type.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..90677051419
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_node_type.pass.cpp
@@ -0,0 +1,78 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..82e7d80c06e
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_node_type_hint.pass.cpp
@@ -0,0 +1,64 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/associative/multiset/extract_iterator.pass.cpp b/libcxx/test/std/containers/associative/multiset/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..0f41169e9fe
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multiset/extract_iterator.pass.cpp
@@ -0,0 +1,60 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/associative/multiset/extract_key.pass.cpp b/libcxx/test/std/containers/associative/multiset/extract_key.pass.cpp
new file mode 100644
index 00000000000..9ad0184100b
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multiset/extract_key.pass.cpp
@@ -0,0 +1,71 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/associative/multiset/insert_node_type.pass.cpp b/libcxx/test/std/containers/associative/multiset/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..ca51ec9f093
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multiset/insert_node_type.pass.cpp
@@ -0,0 +1,77 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/associative/multiset/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/associative/multiset/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..9d0af0653f6
--- /dev/null
+++ b/libcxx/test/std/containers/associative/multiset/insert_node_type_hint.pass.cpp
@@ -0,0 +1,59 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/associative/set/extract_iterator.pass.cpp b/libcxx/test/std/containers/associative/set/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..ffcf7148688
--- /dev/null
+++ b/libcxx/test/std/containers/associative/set/extract_iterator.pass.cpp
@@ -0,0 +1,60 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/associative/set/extract_key.pass.cpp b/libcxx/test/std/containers/associative/set/extract_key.pass.cpp
new file mode 100644
index 00000000000..1fb7ab9116e
--- /dev/null
+++ b/libcxx/test/std/containers/associative/set/extract_key.pass.cpp
@@ -0,0 +1,71 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/associative/set/insert_node_type.pass.cpp b/libcxx/test/std/containers/associative/set/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..4186f20e771
--- /dev/null
+++ b/libcxx/test/std/containers/associative/set/insert_node_type.pass.cpp
@@ -0,0 +1,83 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/associative/set/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/associative/set/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..761ceef6a4a
--- /dev/null
+++ b/libcxx/test/std/containers/associative/set/insert_node_type_hint.pass.cpp
@@ -0,0 +1,61 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/container.node/node_handle.pass.cpp b/libcxx/test/std/containers/container.node/node_handle.pass.cpp
new file mode 100644
index 00000000000..6314ec1fb77
--- /dev/null
+++ b/libcxx/test/std/containers/container.node/node_handle.pass.cpp
@@ -0,0 +1,145 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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>>();
+}
diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/extract_iterator.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..4cc13ded23f
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/extract_iterator.pass.cpp
@@ -0,0 +1,67 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/extract_key.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/extract_key.pass.cpp
new file mode 100644
index 00000000000..25aa2488886
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/extract_key.pass.cpp
@@ -0,0 +1,76 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..d434864885f
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type.pass.cpp
@@ -0,0 +1,84 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..ef98453b627
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_node_type_hint.pass.cpp
@@ -0,0 +1,64 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_iterator.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..adb2ddb2ba8
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_iterator.pass.cpp
@@ -0,0 +1,67 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_key.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_key.pass.cpp
new file mode 100644
index 00000000000..8cf26fc7750
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/extract_key.pass.cpp
@@ -0,0 +1,77 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..93c0462b324
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type.pass.cpp
@@ -0,0 +1,77 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..99a47cabb51
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_node_type_hint.pass.cpp
@@ -0,0 +1,63 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/unord/unord.multiset/extract_iterator.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..1595c55a423
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multiset/extract_iterator.pass.cpp
@@ -0,0 +1,60 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.multiset/extract_key.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/extract_key.pass.cpp
new file mode 100644
index 00000000000..ffe46fb30f1
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multiset/extract_key.pass.cpp
@@ -0,0 +1,71 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.multiset/insert_node_type.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..c3d4cd2a0e8
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multiset/insert_node_type.pass.cpp
@@ -0,0 +1,76 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/unord/unord.multiset/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..79712d3ded7
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.multiset/insert_node_type_hint.pass.cpp
@@ -0,0 +1,59 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/unord/unord.set/extract_iterator.pass.cpp b/libcxx/test/std/containers/unord/unord.set/extract_iterator.pass.cpp
new file mode 100644
index 00000000000..40feb0e2f85
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.set/extract_iterator.pass.cpp
@@ -0,0 +1,60 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.set/extract_key.pass.cpp b/libcxx/test/std/containers/unord/unord.set/extract_key.pass.cpp
new file mode 100644
index 00000000000..f686342b298
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.set/extract_key.pass.cpp
@@ -0,0 +1,71 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+    }
+}
diff --git a/libcxx/test/std/containers/unord/unord.set/insert_node_type.pass.cpp b/libcxx/test/std/containers/unord/unord.set/insert_node_type.pass.cpp
new file mode 100644
index 00000000000..6c91b539356
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.set/insert_node_type.pass.cpp
@@ -0,0 +1,83 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/std/containers/unord/unord.set/insert_node_type_hint.pass.cpp b/libcxx/test/std/containers/unord/unord.set/insert_node_type_hint.pass.cpp
new file mode 100644
index 00000000000..626f27271da
--- /dev/null
+++ b/libcxx/test/std/containers/unord/unord.set/insert_node_type_hint.pass.cpp
@@ -0,0 +1,61 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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);
+}
diff --git a/libcxx/test/support/Counter.h b/libcxx/test/support/Counter.h
index 4a658c58c06..63ed6080155 100644
--- a/libcxx/test/support/Counter.h
+++ b/libcxx/test/support/Counter.h
@@ -23,7 +23,7 @@ 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; }
@@ -49,7 +49,7 @@ 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());}
 };
 }