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

[Erik Pilkington via Phabricator via cfe-commits]

erik.pilkington updated this revision to Diff 153964.
erik.pilkington added a comment.
Herald added a subscriber: dexonsmith.

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


https://reviews.llvm.org/D46845

Files:
  libcxx/include/__hash_table
  libcxx/include/__node_handle
  libcxx/include/__tree
  libcxx/include/map
  libcxx/include/module.modulemap
  libcxx/include/set
  libcxx/include/unordered_map
  libcxx/include/unordered_set
  
libcxx/test/std/containers/associative/map/map.modifiers/insert_extract.pass.cpp
  
libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_extract.pass.cpp
  libcxx/test/std/containers/associative/multiset/insert_extract.pass.cpp
  libcxx/test/std/containers/associative/set/insert_extract.pass.cpp
  libcxx/test/std/containers/container.node/node_handle.pass.cpp
  
libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp
  
libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_extract.pass.cpp
  libcxx/test/std/containers/unord/unord.multiset/insert_extract.pass.cpp
  libcxx/test/std/containers/unord/unord.set/insert_extract.pass.cpp
  libcxx/test/support/Counter.h


Index: libcxx/test/support/Counter.h
===================================================================
--- libcxx/test/support/Counter.h
+++ libcxx/test/support/Counter.h
@@ -49,7 +49,7 @@
     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());}
 };
 }
 
Index: libcxx/test/std/containers/unord/unord.set/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.set/insert_extract.pass.cpp
@@ -0,0 +1,220 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <unordered_set>
+#include <type_traits>
+#include <iterator>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::unordered_set<int> int_set_type;
+using intIRT = int_set_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>,
+                           std::equal_to<Counter<int>>,
+                           min_allocator<Counter<int>>> set_type;
+using minIRT = set_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == st.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        st.insert(0);
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        set_type st;
+        set_type::node_type nh;
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_set = std::unordered_set<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_set::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_set<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(other.size() == 1);
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/unord/unord.multiset/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multiset/insert_extract.pass.cpp
@@ -0,0 +1,158 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <unordered_set>
+#include <type_traits>
+#include <iterator>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_set = std::unordered_multiset<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_set::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_multiset<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_multiset<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(other.size() == 1);
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,154 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <unordered_map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_map = std::unordered_multimap<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_map::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_multimap<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_multimap<int, Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(24);
+        b = s.extract(42);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,218 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <unordered_map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::unordered_map<int, int> int_map_type;
+using intIRT = int_map_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::unordered_map<
+    Counter<int>, Counter<int>, std::hash<Counter<int> >,
+    std::equal_to<Counter<int> >,
+    min_allocator<std::pair<const Counter<int>, Counter<int> > > >
+    map_type;
+using minIRT = map_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        mp.insert({0, 0});
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        map_type mp;
+        map_type::node_type nh;
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_map = std::unordered_map<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_map::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_map<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_map<int, Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(24);
+        b = s.extract(42);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/container.node/node_handle.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/container.node/node_handle.pass.cpp
@@ -0,0 +1,99 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+{
+    typedef T argument_type;
+    typedef size_t result_type;
+    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>
+{
+    typedef Static argument_type;
+    typedef size_t result_type;
+    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,
+              "");
+
+int main()
+{
+    return 0;
+}
Index: libcxx/test/std/containers/associative/set/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/set/insert_extract.pass.cpp
@@ -0,0 +1,218 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::set<int> int_set_type;
+using intIRT = int_set_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::set<Counter<int>, std::less<Counter<int>>,
+                 min_allocator<Counter<int>>> set_type;
+using minIRT = set_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == st.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        st.insert(0);
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        set_type st;
+        set_type::node_type nh;
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_set = std::set<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_set::iterator i = s.begin();
+    assert(*i == 1);
+    ++i;
+    assert(*i == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::set<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::set<int, std::less<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::set<Counter<int>, std::less<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/associative/multiset/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multiset/insert_extract.pass.cpp
@@ -0,0 +1,200 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_set = std::multiset<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_set::iterator i = s.begin();
+    assert(*i == 1);
+    ++i;
+    assert(*i == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::multiset<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::multiset<int, std::less<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::multiset<Counter<int>, std::less<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_multi
+{
+typedef std::multiset<int> set_type;
+static void doit()
+{
+    {
+        set_type s = {1, 2, 2};
+        assert(s.count(2) == 2);
+        set_type::node_type nh = s.extract(2);
+        assert(s.count(1) == 1);
+        assert(s.count(2) == 1);
+        assert(s.size() == 2);
+        s.insert(std::move(nh));
+        assert(s.size() == 3);
+        assert(nh.empty());
+    }
+
+    {
+        set_type s = {0};
+        set_type::node_type nt = s.extract(s.begin());
+        assert(nt.value() == 0);
+        assert(s.size() == 0);
+        s.insert(std::move(nt));
+    }
+
+    {
+        set_type s = {1, 2};
+        set_type::node_type nh = s.extract(1);
+        s.insert(s.begin(), std::move(nh));
+        assert(nh.empty());
+        assert(s.size() == 2);
+    }
+
+    {
+        set_type s;
+        set_type::node_type nh;
+        set_type::iterator i = s.insert(std::move(nh));
+        assert(i == s.end());
+    }
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+    test_multi::doit();
+}
Index: libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,156 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_map = std::multimap<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_map::iterator i = s.begin();
+    assert((*i).first == 1);
+    ++i;
+    assert((*i).first == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::multimap<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::multimap<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::multimap<int, Counter<int>, std::less<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}
Index: libcxx/test/std/containers/associative/map/map.modifiers/insert_extract.pass.cpp
===================================================================
--- /dev/null
+++ libcxx/test/std/containers/associative/map/map.modifiers/insert_extract.pass.cpp
@@ -0,0 +1,217 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::map<int, int> int_map_type;
+using intIRT = int_map_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::map<Counter<int>, Counter<int>, std::less<Counter<int>>,
+                 min_allocator<std::pair<const Counter<int>, Counter<int>>>> map_type;
+using minIRT = map_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        mp.insert({0, 0});
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        map_type mp;
+        map_type::node_type nh;
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_map = std::map<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_map::iterator i = s.begin();
+    assert((*i).first == 1);
+    ++i;
+    assert((*i).first == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::map<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::map<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::map<int, Counter<int>, std::less<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}
Index: libcxx/include/unordered_set
===================================================================
--- libcxx/include/unordered_set
+++ libcxx/include/unordered_set
@@ -321,6 +321,7 @@
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 
 #include <__debug>
@@ -331,6 +332,9 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Value, class _Hash, class _Pred, class _Alloc>
+class unordered_multiset;
+
 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
           class _Alloc = allocator<_Value> >
 class _LIBCPP_TEMPLATE_VIS unordered_set
@@ -363,6 +367,13 @@
     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
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_set()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -541,6 +552,34 @@
     _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, node_type&& __nh)
+    {
+        _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
+            "node_type with incompatible allocator passed to unordered_set::insert()");
+        return insert(_VSTD::move(__nh)).position;
+    }
+    _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 +922,12 @@
     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
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multiset()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1019,6 +1064,36 @@
         _LIBCPP_INLINE_VISIBILITY
         void insert(_InputIterator __first, _InputIterator __last);
 
+#if _LIBCPP_STD_VER > 14
+    _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);
+    }
+    _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));
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __p) {return __table_.erase(__p);}
     _LIBCPP_INLINE_VISIBILITY
Index: libcxx/include/unordered_map
===================================================================
--- libcxx/include/unordered_map
+++ libcxx/include/unordered_map
@@ -367,6 +367,7 @@
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 #include <stdexcept>
 #include <tuple>
@@ -379,6 +380,9 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
+class unordered_multimap;
+
 template <class _Key, class _Cp, class _Hash, bool _IsEmpty>
 class __unordered_map_hasher
     : private _Hash
@@ -843,6 +847,13 @@
     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
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_map()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1136,7 +1147,37 @@
     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 +1631,12 @@
     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
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
@@ -1763,6 +1810,36 @@
     _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)
Index: libcxx/include/set
===================================================================
--- libcxx/include/set
+++ libcxx/include/set
@@ -387,14 +387,18 @@
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <functional>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Key, class _Compare, class _Allocator>
+class multiset;
+
 template <class _Key, class _Compare = less<_Key>,
           class _Allocator = allocator<_Key> >
 class _LIBCPP_TEMPLATE_VIS set
@@ -429,6 +433,13 @@
     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
+
+    __base& __get_tree() { return __tree_; }
+
     _LIBCPP_INLINE_VISIBILITY
     set()
         _NOEXCEPT_(
@@ -634,6 +645,35 @@
     _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 +878,12 @@
     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
+
+    __base& __get_tree() { return __tree_; }
+
     // construct/copy/destroy:
     _LIBCPP_INLINE_VISIBILITY
     multiset()
@@ -1042,6 +1088,35 @@
     _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)
Index: libcxx/include/module.modulemap
===================================================================
--- libcxx/include/module.modulemap
+++ libcxx/include/module.modulemap
@@ -494,6 +494,7 @@
   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
Index: libcxx/include/map
===================================================================
--- libcxx/include/map
+++ libcxx/include/map
@@ -440,6 +440,7 @@
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <iterator>
 #include <memory>
 #include <utility>
@@ -906,6 +907,13 @@
     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
+
+    __base& __get_tree() { return __tree_; }
+
     _LIBCPP_INLINE_VISIBILITY
     map()
         _NOEXCEPT_(
@@ -1253,6 +1261,35 @@
     _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 +1599,12 @@
     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
+
+    __base& __get_tree() { return __tree_; }
+
     _LIBCPP_INLINE_VISIBILITY
     multimap()
         _NOEXCEPT_(
@@ -1800,6 +1843,37 @@
     _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();}
 
Index: libcxx/include/__tree
===================================================================
--- libcxx/include/__tree
+++ libcxx/include/__tree
@@ -796,6 +796,16 @@
     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 @@
     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,132 @@
 
 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>
+_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>
+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>
+_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>
+_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>
+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>
+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);
Index: libcxx/include/__node_handle
===================================================================
--- /dev/null
+++ libcxx/include/__node_handle
@@ -0,0 +1,234 @@
+// -*- 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>
+class __node_handle_base
+{
+public:
+    typedef allocator_traits<_Alloc> __alloc_traits;
+    typedef typename __rebind_pointer<typename __alloc_traits::void_pointer,
+                                      _NodeType>::type
+        __node_pointer_type;
+
+    typedef _Alloc allocator_type;
+    typedef typename _NodeType::__node_value_type value_type;
+
+    __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
+    __node_handle_base() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_handle_base(__node_pointer_type __ptr, allocator_type const& __alloc)
+            : __ptr_(__ptr), __alloc_(__alloc)
+    {
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_handle_base(__node_handle_base&& __other) noexcept
+            : __ptr_(__other.__ptr_),
+              __alloc_(_VSTD::move(__other.__alloc_))
+    {
+        __other.__ptr_ = nullptr;
+        __other.__alloc_ = _VSTD::nullopt;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_handle_base& operator=(__node_handle_base&& __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(__node_handle_base& __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
+    ~__node_handle_base()
+    {
+        __destroy_node_pointer();
+    }
+};
+
+template <class _NodeType, class _Alloc>
+class _LIBCPP_TEMPLATE_VIS __set_node_handle
+    : public __node_handle_base<_NodeType, _Alloc>
+{
+    template <class _Tp, class _Compare, class _Allocator>
+        friend class __tree;
+    template <class _Tp, class _Hash, class _Equal, class _Allocator>
+        friend class __hash_table;
+
+    typedef __node_handle_base<_NodeType, _Alloc> __base;
+    using __base::__base;
+
+public:
+    typedef typename _NodeType::__node_value_type value_type;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __set_node_handle() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __set_node_handle(__set_node_handle&& __other) noexcept = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __set_node_handle& operator=(__set_node_handle&& __other) = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    value_type& value() const
+    {
+        return this->__ptr_->__value_;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    friend void swap(__set_node_handle& __a, __set_node_handle& __b)
+        noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); }
+
+    _LIBCPP_INLINE_VISIBILITY ~__set_node_handle() = default;
+};
+
+template <class _NodeType, class _Alloc>
+class _LIBCPP_TEMPLATE_VIS __map_node_handle
+    : public __node_handle_base<_NodeType, _Alloc>
+{
+    template <class _Tp, class _Compare, class _Allocator>
+        friend class __tree;
+    template <class _Tp, class _Hash, class _Equal, class _Allocator>
+        friend class __hash_table;
+
+    typedef __node_handle_base<_NodeType, _Alloc> __base;
+    using __base::__base;
+
+public:
+    typedef typename _NodeType::__node_value_type::key_type key_type;
+    typedef typename _NodeType::__node_value_type::mapped_type mapped_type;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __map_node_handle() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __map_node_handle(__map_node_handle&& __other) noexcept = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __map_node_handle& operator=(__map_node_handle&& __other) = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    key_type& key() const
+    {
+        return this->__ptr_->__value_.__ref().first;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    mapped_type& mapped() const
+    {
+        return this->__ptr_->__value_.__ref().second;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    friend void swap(__map_node_handle& __a, __map_node_handle& __b)
+        noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); }
+
+    _LIBCPP_INLINE_VISIBILITY ~__map_node_handle() = default;
+};
+
+template <class _Iterator, class _NodeType>
+struct __insert_return_type
+{
+    _Iterator position;
+    bool inserted;
+    _NodeType node;
+};
+
+#endif // _LIBCPP_STD_VER > 14
+
+_LIBCPP_END_NAMESPACE_STD
+_LIBCPP_POP_MACROS
+
+#endif
Index: libcxx/include/__hash_table
===================================================================
--- libcxx/include/__hash_table
+++ libcxx/include/__hash_table
@@ -859,6 +859,17 @@
     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 @@
         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,85 @@
 
 #endif  // _LIBCPP_CXX03_LANG
 
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle, class _InsertReturnType>
+_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>
+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>
+_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>
+_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>
+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>
+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)

_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits