Vendor import of libc++ trunk r256945:vendor/libc++/r256945

https://llvm.org/svn/llvm-project/libcxx/trunk@256945

8 files changed, 312 insertions, 331 deletions

diff --git a/include/__config b/include/__config
index f141f4f1b7f9..c0b1ef201c05 100644
--- a/include/__config
+++ b/include/__config
@@ -39,6 +39,8 @@
 #define _LIBCPP_ABI_ALTERNATE_STRING_LAYOUT
 // Fix deque iterator type in order to support incomplete types.
 #define _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE
+// Fix undefined behavior in how std::list stores it's linked nodes.
+#define _LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB
 #endif
 
 #define _LIBCPP_CONCAT1(_LIBCPP_X,_LIBCPP_Y) _LIBCPP_X##_LIBCPP_Y
diff --git a/include/__hash_table b/include/__hash_table
index cfa763ab217a..c7d1ef3d082f 100644
--- a/include/__hash_table
+++ b/include/__hash_table
@@ -46,12 +46,7 @@ template <class _Tp, class _VoidPtr>
 struct __hash_node
     : public __hash_node_base
              <
-                 typename pointer_traits<_VoidPtr>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-                     rebind<__hash_node<_Tp, _VoidPtr> >
-#else
-                     rebind<__hash_node<_Tp, _VoidPtr> >::other
-#endif
+                 typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type
              >
 {
     typedef _Tp value_type;
@@ -98,13 +93,7 @@ public:
     typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type;
     typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
     typedef value_type&                                  reference;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-                     rebind<value_type>
-#else
-                     rebind<value_type>::other
-#endif
-                                                         pointer;
+    typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
 
     _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
@@ -229,20 +218,8 @@ public:
     typedef typename __node::value_type                value_type;
     typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
     typedef const value_type&                          reference;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const value_type>
-#else
-            rebind<const value_type>::other
-#endif
-                                                       pointer;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__node>
-#else
-            rebind<__node>::other
-#endif
-                                                      __non_const_node_pointer;
+    typedef typename __rebind_pointer<__node_pointer, const value_type>::type pointer;
+    typedef typename __rebind_pointer<__node_pointer, __node>::type __non_const_node_pointer;
     typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
 
     _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT
@@ -376,13 +353,7 @@ public:
     typedef typename __pointer_traits::element_type::value_type value_type;
     typedef typename __pointer_traits::difference_type          difference_type;
     typedef value_type&                                         reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<value_type>
-#else
-            rebind<value_type>::other
-#endif
-                                                                pointer;
+    typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
 
     _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT
     {
@@ -514,13 +485,9 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator
     typedef pointer_traits<__node_pointer>          __pointer_traits;
     typedef typename __pointer_traits::element_type __node;
     typedef typename remove_const<__node>::type     __non_const_node;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__non_const_node>
-#else
-            rebind<__non_const_node>::other
-#endif
-                                                    __non_const_node_pointer;
+    typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
+        __non_const_node_pointer;
+
     typedef __hash_local_iterator<__non_const_node_pointer>
                                                     __non_const_iterator;
 public:
@@ -530,13 +497,9 @@ public:
                      >::type                           value_type;
     typedef typename __pointer_traits::difference_type difference_type;
     typedef const value_type&                          reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const value_type>
-#else
-            rebind<const value_type>::other
-#endif
-                                                       pointer;
+    typedef typename __rebind_pointer<__node_pointer, const value_type>::type
+        pointer;
+
 
     _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT
     {
@@ -780,13 +743,8 @@ public:
     typedef typename __node_traits::pointer          __node_pointer;
     typedef typename __node_traits::pointer          __node_const_pointer;
     typedef __hash_node_base<__node_pointer>         __first_node;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__first_node>
-#else
-            rebind<__first_node>::other
-#endif
-                                                     __node_base_pointer;
+    typedef typename __rebind_pointer<__node_pointer, __first_node>::type
+        __node_base_pointer;
 
 private:
 
diff --git a/include/__tree b/include/__tree
index 6391609b3982..94565bc3f74c 100644
--- a/include/__tree
+++ b/include/__tree
@@ -548,31 +548,15 @@ template <class _VoidPtr>
 class __tree_node_base
     : public __tree_end_node
              <
-                typename pointer_traits<_VoidPtr>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-                     rebind<__tree_node_base<_VoidPtr> >
-#else
-                     rebind<__tree_node_base<_VoidPtr> >::other
-#endif
+                typename __rebind_pointer<_VoidPtr, __tree_node_base<_VoidPtr> >::type
              >
 {
     __tree_node_base(const __tree_node_base&);
     __tree_node_base& operator=(const __tree_node_base&);
 public:
-    typedef typename pointer_traits<_VoidPtr>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__tree_node_base>
-#else
-            rebind<__tree_node_base>::other
-#endif
-                                                pointer;
-    typedef typename pointer_traits<_VoidPtr>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const __tree_node_base>
-#else
-            rebind<const __tree_node_base>::other
-#endif
-                                                const_pointer;
+    typedef typename __rebind_pointer<_VoidPtr, __tree_node_base>::type pointer;
+    typedef typename __rebind_pointer<_VoidPtr, const __tree_node_base>::type const_pointer;
+
     typedef __tree_end_node<pointer> base;
 
     pointer __right_;
@@ -623,13 +607,7 @@ public:
     typedef _Tp                        value_type;
     typedef _DiffType                  difference_type;
     typedef value_type&                reference;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<value_type>
-#else
-            rebind<value_type>::other
-#endif
-                                       pointer;
+    typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
 
     _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
@@ -694,13 +672,7 @@ public:
     typedef _Tp                              value_type;
     typedef _DiffType                        difference_type;
     typedef const value_type&                reference;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const value_type>
-#else
-            rebind<const value_type>::other
-#endif
-                                       pointer;
+    typedef typename __rebind_pointer<__node_pointer, const value_type>::type pointer;
 
     _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
@@ -710,13 +682,8 @@ public:
 
 private:
     typedef typename remove_const<__node>::type  __non_const_node;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__non_const_node>
-#else
-            rebind<__non_const_node>::other
-#endif
-                                                 __non_const_node_pointer;
+    typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
+        __non_const_node_pointer;
     typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type>
                                                  __non_const_iterator;
 public:
@@ -730,14 +697,8 @@ public:
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator& operator++() {
-      typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-          rebind<typename __node::base>
-#else
-          rebind<typename __node::base>::other
-#endif
-              __node_base_pointer;
-
+      typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type
+        __node_base_pointer;
       __ptr_ = static_cast<__node_pointer>(
           __tree_next(static_cast<__node_base_pointer>(__ptr_)));
       return *this;
@@ -749,14 +710,8 @@ public:
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator& operator--() {
-      typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-          rebind<typename __node::base>
-#else
-          rebind<typename __node::base>::other
-#endif
-              __node_base_pointer;
-
+      typedef typename __rebind_pointer<__node_pointer, typename __node::base>::type
+        __node_base_pointer;
       __ptr_ = static_cast<__node_pointer>(
           __tree_prev(static_cast<__node_base_pointer>(__ptr_)));
       return *this;
@@ -810,20 +765,9 @@ public:
     typedef typename __node_base::pointer            __node_base_const_pointer;
 private:
     typedef typename __node_base::base __end_node_t;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__end_node_t>
-#else
-            rebind<__end_node_t>::other
-#endif
-                                                     __end_node_ptr;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__end_node_t>
-#else
-            rebind<__end_node_t>::other
-#endif
-                                                     __end_node_const_ptr;
+    typedef typename __rebind_pointer<__node_pointer, __end_node_t>::type
+        __end_node_ptr;
+    typedef __end_node_ptr __end_node_const_ptr;
 
     __node_pointer                                          __begin_node_;
     __compressed_pair<__end_node_t, __node_allocator>  __pair1_;
@@ -965,6 +909,13 @@ public:
     iterator __insert_multi(const value_type& __v);
     iterator __insert_multi(const_iterator __p, const value_type& __v);
 
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    pair<iterator, bool> __insert_unique(        value_type&& __v);
+    iterator __insert_unique(const_iterator __p, value_type&& __v);
+    iterator __insert_multi(                    value_type&& __v);
+    iterator __insert_multi(const_iterator __p, value_type&& __v);
+#endif
+
     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
     iterator             __node_insert_unique(const_iterator __p,
                                               __node_pointer __nd);
@@ -1786,6 +1737,28 @@ __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p,
 #endif  // _LIBCPP_HAS_NO_VARIADICS
 
 template <class _Tp, class _Compare, class _Allocator>
+pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
+__tree<_Tp, _Compare, _Allocator>::__insert_unique(value_type&& __v)
+{
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    pair<iterator, bool> __r = __node_insert_unique(__h.get());
+    if (__r.second)
+        __h.release();
+    return __r;
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, value_type&& __v)
+{
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    iterator __r = __node_insert_unique(__p, __h.get());
+    if (__r.__ptr_ == __h.get())
+        __h.release();
+    return __r;
+}
+
+template <class _Tp, class _Compare, class _Allocator>
 template <class _Vp>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __tree<_Tp, _Compare, _Allocator>::__insert_unique(_Vp&& __v)
@@ -1810,6 +1783,28 @@ __tree<_Tp, _Compare, _Allocator>::__insert_unique(const_iterator __p, _Vp&& __v
 }
 
 template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__insert_multi(value_type&& __v)
+{
+    __node_base_pointer __parent;
+    __node_base_pointer& __child = __find_leaf_high(__parent, __v);
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+    return iterator(__h.release());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, value_type&& __v)
+{
+    __node_base_pointer __parent;
+    __node_base_pointer& __child = __find_leaf(__p, __parent, __v);
+    __node_holder __h = __construct_node(_VSTD::forward<value_type>(__v));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+    return iterator(__h.release());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
 template <class _Vp>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__insert_multi(_Vp&& __v)
diff --git a/include/ext/hash_map b/include/ext/hash_map
index 0e4ab6910eb5..3ac27b2ca330 100644
--- a/include/ext/hash_map
+++ b/include/ext/hash_map
@@ -368,7 +368,6 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator
 {
     _HashIterator __i_;
 
-    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
     typedef const typename _HashIterator::value_type::first_type key_type;
     typedef typename _HashIterator::value_type::second_type      mapped_type;
 public:
@@ -376,13 +375,8 @@ public:
     typedef pair<key_type, mapped_type>                          value_type;
     typedef typename _HashIterator::difference_type              difference_type;
     typedef value_type&                                          reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<value_type>
-#else
-            rebind<value_type>::other
-#endif
-                                                                 pointer;
+    typedef typename __rebind_pointer<typename _HashIterator::pointer, value_type>::type
+        pointer;
 
     _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {}
 
@@ -419,7 +413,6 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
 {
     _HashIterator __i_;
 
-    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
     typedef const typename _HashIterator::value_type::first_type key_type;
     typedef typename _HashIterator::value_type::second_type      mapped_type;
 public:
@@ -427,13 +420,8 @@ public:
     typedef pair<key_type, mapped_type>                          value_type;
     typedef typename _HashIterator::difference_type              difference_type;
     typedef const value_type&                                    reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const value_type>
-#else
-            rebind<const value_type>::other
-#endif
-                                                                 pointer;
+    typedef typename __rebind_pointer<typename _HashIterator::pointer, const value_type>::type
+        pointer;
 
     _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {}
 
diff --git a/include/forward_list b/include/forward_list
index adbc32cf861c..4f9ecf49bd58 100644
--- a/include/forward_list
+++ b/include/forward_list
@@ -197,15 +197,9 @@ struct __forward_begin_node
 template <class _Tp, class _VoidPtr>
 struct _LIBCPP_HIDDEN __begin_node_of
 {
-    typedef __forward_begin_node
-        <
-             typename pointer_traits<_VoidPtr>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-                 rebind<__forward_list_node<_Tp, _VoidPtr> >
-#else
-                 rebind<__forward_list_node<_Tp, _VoidPtr> >::other
-#endif
-         > type;
+    typedef __forward_begin_node<
+        typename __rebind_pointer<_VoidPtr, __forward_list_node<_Tp, _VoidPtr> >::type
+    > type;
 };
 
 template <class _Tp, class _VoidPtr>
@@ -240,13 +234,7 @@ public:
     typedef value_type&                                       reference;
     typedef typename pointer_traits<__node_pointer>::difference_type
                                                               difference_type;
-    typedef typename pointer_traits<__node_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<value_type>
-#else
-            rebind<value_type>::other
-#endif
-                                                              pointer;
+    typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer;
 
     _LIBCPP_INLINE_VISIBILITY
     __forward_list_iterator() _NOEXCEPT : __ptr_(nullptr) {}
@@ -295,13 +283,7 @@ class _LIBCPP_TYPE_VIS_ONLY __forward_list_const_iterator
         <
             typename pointer_traits<__node_const_pointer>::element_type
         >::type                                               __node;
-    typedef typename pointer_traits<__node_const_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<__node>
-#else
-            rebind<__node>::other
-#endif
-                                                              __node_pointer;
+    typedef typename __rebind_pointer<__node_const_pointer, __node>::type __node_pointer;
 
     template<class, class> friend class forward_list;
 
@@ -311,13 +293,7 @@ public:
     typedef const value_type&                                 reference;
     typedef typename pointer_traits<__node_const_pointer>::difference_type
                                                               difference_type;
-    typedef typename pointer_traits<__node_const_pointer>::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const value_type>
-#else
-            rebind<const value_type>::other
-#endif
-                                                              pointer;
+    typedef typename __rebind_pointer<__node_const_pointer, const value_type>::type pointer;
 
     _LIBCPP_INLINE_VISIBILITY
     __forward_list_const_iterator() _NOEXCEPT : __ptr_(nullptr) {}
diff --git a/include/list b/include/list
index 28d505582c0d..44b20e2fa28c 100644
--- a/include/list
+++ b/include/list
@@ -175,6 +175,7 @@ template <class T, class Alloc>
 #include <initializer_list>
 #include <iterator>
 #include <algorithm>
+#include <type_traits>
 
 #include <__undef_min_max>
 
@@ -187,25 +188,66 @@ template <class T, class Alloc>
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Tp, class _VoidPtr> struct __list_node;
+template <class _Tp, class _VoidPtr> struct __list_node_base;
+
+template <class _Tp, class _VoidPtr>
+struct __list_node_pointer_traits {
+  typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
+        __node_pointer;
+  typedef typename __rebind_pointer<_VoidPtr, __list_node_base<_Tp, _VoidPtr> >::type
+        __base_pointer;
+
+#if defined(_LIBCPP_ABI_LIST_REMOVE_NODE_POINTER_UB)
+  typedef __base_pointer __link_pointer;
+#else
+  typedef typename conditional<
+          is_pointer<_VoidPtr>::value,
+          __base_pointer,
+          __node_pointer
+  >::type __link_pointer;
+#endif
+
+  typedef typename conditional<
+          is_same<__link_pointer, __node_pointer>::value,
+          __base_pointer,
+          __node_pointer
+  >::type __non_link_pointer;
+
+  static _LIBCPP_INLINE_VISIBILITY
+  __link_pointer __unsafe_link_pointer_cast(__link_pointer __p) {
+      return __p;
+  }
+
+  static _LIBCPP_INLINE_VISIBILITY
+  __link_pointer __unsafe_link_pointer_cast(__non_link_pointer __p) {
+      return static_cast<__link_pointer>(static_cast<_VoidPtr>(__p));
+  }
+
+};
 
 template <class _Tp, class _VoidPtr>
 struct __list_node_base
 {
-    typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
-        pointer;
-    typedef typename __rebind_pointer<_VoidPtr, __list_node_base>::type
-        __base_pointer;
+    typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
+    typedef typename _NodeTraits::__node_pointer __node_pointer;
+    typedef typename _NodeTraits::__base_pointer __base_pointer;
+    typedef typename _NodeTraits::__link_pointer __link_pointer;
 
-    pointer __prev_;
-    pointer __next_;
+    __link_pointer __prev_;
+    __link_pointer __next_;
 
     _LIBCPP_INLINE_VISIBILITY
-    __list_node_base() : __prev_(__self()), __next_(__self()) {}
+    __list_node_base() : __prev_(_NodeTraits::__unsafe_link_pointer_cast(__self())),
+                         __next_(_NodeTraits::__unsafe_link_pointer_cast(__self())) {}
 
     _LIBCPP_INLINE_VISIBILITY
-    pointer __self()
-    {
-        return static_cast<pointer>(pointer_traits<__base_pointer>::pointer_to(*this));
+    __base_pointer __self() {
+        return pointer_traits<__base_pointer>::pointer_to(*this);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_pointer __as_node() {
+        return static_cast<__node_pointer>(__self());
     }
 };
 
@@ -214,6 +256,14 @@ struct __list_node
     : public __list_node_base<_Tp, _VoidPtr>
 {
     _Tp __value_;
+
+    typedef __list_node_base<_Tp, _VoidPtr> __base;
+    typedef typename __base::__link_pointer __link_pointer;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __link_pointer __as_link() {
+        return static_cast<__link_pointer>(__base::__self());
+    }
 };
 
 template <class _Tp, class _Alloc = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY list;
@@ -223,21 +273,21 @@ template <class _Tp, class _VoidPtr> class _LIBCPP_TYPE_VIS_ONLY __list_const_it
 template <class _Tp, class _VoidPtr>
 class _LIBCPP_TYPE_VIS_ONLY __list_iterator
 {
-    typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
-        __node_pointer;
+    typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
+    typedef typename _NodeTraits::__link_pointer __link_pointer;
 
-    __node_pointer __ptr_;
+    __link_pointer __ptr_;
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
+    explicit __list_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
         : __ptr_(__p)
     {
         __get_db()->__insert_ic(this, __c);
     }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+    explicit __list_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 #endif
 
 
@@ -295,7 +345,7 @@ public:
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::iterator");
 #endif
-        return __ptr_->__value_;
+        return __ptr_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     pointer operator->() const
@@ -304,7 +354,7 @@ public:
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::iterator");
 #endif
-        return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
+        return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
     }
 
     _LIBCPP_INLINE_VISIBILITY
@@ -346,21 +396,21 @@ public:
 template <class _Tp, class _VoidPtr>
 class _LIBCPP_TYPE_VIS_ONLY __list_const_iterator
 {
-    typedef typename __rebind_pointer<_VoidPtr, __list_node<_Tp, _VoidPtr> >::type
-        __node_pointer;
+    typedef __list_node_pointer_traits<_Tp, _VoidPtr> _NodeTraits;
+    typedef typename _NodeTraits::__link_pointer __link_pointer;
 
-    __node_pointer __ptr_;
+    __link_pointer __ptr_;
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
+    explicit __list_const_iterator(__link_pointer __p, const void* __c) _NOEXCEPT
         : __ptr_(__p)
     {
         __get_db()->__insert_ic(this, __c);
     }
 #else
     _LIBCPP_INLINE_VISIBILITY
-    explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
+    explicit __list_const_iterator(__link_pointer __p) _NOEXCEPT : __ptr_(__p) {}
 #endif
 
     template<class, class> friend class list;
@@ -422,7 +472,7 @@ public:
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::const_iterator");
 #endif
-        return __ptr_->__value_;
+        return __ptr_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     pointer operator->() const
@@ -431,7 +481,7 @@ public:
         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
                        "Attempted to dereference a non-dereferenceable list::iterator");
 #endif
-        return pointer_traits<pointer>::pointer_to(__ptr_->__value_);
+        return pointer_traits<pointer>::pointer_to(__ptr_->__as_node()->__value_);
     }
 
     _LIBCPP_INLINE_VISIBILITY
@@ -489,6 +539,9 @@ protected:
     typedef allocator_traits<__node_allocator>                       __node_alloc_traits;
     typedef typename __node_alloc_traits::pointer                    __node_pointer;
     typedef typename __node_alloc_traits::pointer                    __node_const_pointer;
+    typedef __list_node_pointer_traits<value_type, __void_pointer> __node_pointer_traits;
+    typedef typename __node_pointer_traits::__link_pointer __link_pointer;
+    typedef __link_pointer __link_const_pointer;
     typedef typename __alloc_traits::pointer                         pointer;
     typedef typename __alloc_traits::const_pointer                   const_pointer;
     typedef typename __alloc_traits::difference_type                 difference_type;
@@ -500,6 +553,12 @@ protected:
     __compressed_pair<size_type, __node_allocator> __size_alloc_;
 
     _LIBCPP_INLINE_VISIBILITY
+    __link_pointer __end_as_link() const _NOEXCEPT {
+        return __node_pointer_traits::__unsafe_link_pointer_cast(
+                const_cast<__node_base&>(__end_).__self());
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
           size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
     _LIBCPP_INLINE_VISIBILITY
     const size_type& __sz() const _NOEXCEPT
@@ -511,7 +570,7 @@ protected:
     const __node_allocator& __node_alloc() const _NOEXCEPT
         {return __size_alloc_.second();}
 
-    static void __unlink_nodes(__node_pointer __f, __node_pointer __l) _NOEXCEPT;
+    static void __unlink_nodes(__link_pointer __f, __link_pointer __l) _NOEXCEPT;
 
     __list_imp()
         _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
@@ -543,22 +602,18 @@ protected:
     iterator end() _NOEXCEPT
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        return iterator(static_cast<__node_pointer>(
-                pointer_traits<__node_base_pointer>::pointer_to(__end_)), this);
+        return iterator(__end_as_link(), this);
 #else
-        return iterator(static_cast<__node_pointer>(
-                      pointer_traits<__node_base_pointer>::pointer_to(__end_)));
+        return iterator(__end_as_link());
 #endif
     }
     _LIBCPP_INLINE_VISIBILITY
     const_iterator end() const _NOEXCEPT
     {
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        return const_iterator(static_cast<__node_const_pointer>(
-        pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))), this);
+        return const_iterator(__end_as_link(), this);
 #else
-        return const_iterator(static_cast<__node_const_pointer>(
-        pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(__end_))));
+        return const_iterator(__end_as_link());
 #endif
     }
 
@@ -613,7 +668,7 @@ private:
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_pointer __f, __node_pointer __l)
+__list_imp<_Tp, _Alloc>::__unlink_nodes(__link_pointer __f, __link_pointer __l)
     _NOEXCEPT
 {
     __f->__prev_->__next_ = __l->__next_;
@@ -651,17 +706,16 @@ __list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
     if (!empty())
     {
         __node_allocator& __na = __node_alloc();
-        __node_pointer __f = __end_.__next_;
-        __node_pointer __l = static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__end_));
+        __link_pointer __f = __end_.__next_;
+        __link_pointer __l = __end_as_link();
         __unlink_nodes(__f, __l->__prev_);
         __sz() = 0;
         while (__f != __l)
         {
-            __node_pointer __n = __f;
+            __node_pointer __np = __f->__as_node();
             __f = __f->__next_;
-            __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-            __node_alloc_traits::deallocate(__na, __n, 1);
+            __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+            __node_alloc_traits::deallocate(__na, __np, 1);
         }
 #if _LIBCPP_DEBUG_LEVEL >= 2
         __c_node* __c = __get_db()->__find_c_and_lock(this);
@@ -700,13 +754,13 @@ __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
     swap(__sz(), __c.__sz());
     swap(__end_, __c.__end_);
     if (__sz() == 0)
-        __end_.__next_ = __end_.__prev_ = __end_.__self();
+        __end_.__next_ = __end_.__prev_ = __end_as_link();
     else
-        __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_.__self();
+        __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
     if (__c.__sz() == 0)
-        __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_.__self();
+        __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();
     else
-        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_.__self();
+        __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ = __c.__end_as_link();
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __libcpp_db* __db = __get_db();
@@ -719,8 +773,7 @@ __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
     {
         --__p;
         const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
-        if (__i->__ptr_ == static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
+        if (__i->__ptr_ == __c.__end_as_link())
         {
             __cn2->__add(*__p);
             if (--__cn1->end_ != __p)
@@ -733,8 +786,7 @@ __list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
     {
         --__p;
         const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
-        if (__i->__ptr_ == static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__end_)))
+        if (__i->__ptr_ == __end_as_link())
         {
             __cn1->__add(*__p);
             if (--__cn2->end_ != __p)
@@ -758,6 +810,7 @@ class _LIBCPP_TYPE_VIS_ONLY list
     typedef typename base::__node_alloc_traits __node_alloc_traits;
     typedef typename base::__node_base         __node_base;
     typedef typename base::__node_base_pointer __node_base_pointer;
+    typedef typename base::__link_pointer __link_pointer;
 
 public:
     typedef _Tp                                      value_type;
@@ -881,25 +934,25 @@ public:
     reference front()
     {
         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
-        return base::__end_.__next_->__value_;
+        return base::__end_.__next_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     const_reference front() const
     {
         _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
-        return base::__end_.__next_->__value_;
+        return base::__end_.__next_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     reference back()
     {
         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
-        return base::__end_.__prev_->__value_;
+        return base::__end_.__prev_->__as_node()->__value_;
     }
     _LIBCPP_INLINE_VISIBILITY
     const_reference back() const
     {
         _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
-        return base::__end_.__prev_->__value_;
+        return base::__end_.__prev_->__as_node()->__value_;
     }
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1004,9 +1057,9 @@ public:
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
 private:
-    static void __link_nodes  (__node_pointer __p, __node_pointer __f, __node_pointer __l);
-    void __link_nodes_at_front(__node_pointer __f, __node_pointer __l);
-    void __link_nodes_at_back (__node_pointer __f, __node_pointer __l);
+    static void __link_nodes  (__link_pointer __p, __link_pointer __f, __link_pointer __l);
+    void __link_nodes_at_front(__link_pointer __f, __link_pointer __l);
+    void __link_nodes_at_back (__link_pointer __f, __link_pointer __l);
     iterator __iterator(size_type __n);
     template <class _Comp>
         static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
@@ -1020,7 +1073,7 @@ private:
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-list<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_pointer __l)
+list<_Tp, _Alloc>::__link_nodes(__link_pointer __p, __link_pointer __f, __link_pointer __l)
 {
     __p->__prev_->__next_ = __f;
     __f->__prev_ = __p->__prev_;
@@ -1032,9 +1085,9 @@ list<_Tp, _Alloc>::__link_nodes(__node_pointer __p, __node_pointer __f, __node_p
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-list<_Tp, _Alloc>::__link_nodes_at_front(__node_pointer __f, __node_pointer __l)
+list<_Tp, _Alloc>::__link_nodes_at_front(__link_pointer __f, __link_pointer __l)
 {
-    __f->__prev_ = base::__end_.__self();
+    __f->__prev_ = base::__end_as_link();
     __l->__next_ = base::__end_.__next_;
     __l->__next_->__prev_ = __l;
     base::__end_.__next_ = __f;
@@ -1044,9 +1097,9 @@ list<_Tp, _Alloc>::__link_nodes_at_front(__node_pointer __f, __node_pointer __l)
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-list<_Tp, _Alloc>::__link_nodes_at_back(__node_pointer __f, __node_pointer __l)
+list<_Tp, _Alloc>::__link_nodes_at_back(__link_pointer __f, __link_pointer __l)
 {
-    __l->__next_ = base::__end_.__self();
+    __l->__next_ = base::__end_as_link();
     __f->__prev_ = base::__end_.__prev_;
     __f->__prev_->__next_ = __f;
     base::__end_.__prev_ = __l;
@@ -1323,12 +1376,12 @@ list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
+    __link_nodes(__p.__ptr_, __hold->__as_link(), __hold->__as_link());
     ++base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__hold.release()->__as_link(), this);
 #else
-    return iterator(__hold.release());
+    return iterator(__hold.release()->__as_link());
 #endif
 }
 
@@ -1354,9 +1407,9 @@ list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& _
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        __r = iterator(__hold.get(), this);
+        __r = iterator(__hold->__as_link(), this);
 #else
-        __r = iterator(__hold.get());
+        __r = iterator(__hold->__as_link());
 #endif
         __hold.release();
         iterator __e = __r;
@@ -1368,7 +1421,7 @@ list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& _
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
@@ -1379,8 +1432,8 @@ list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& _
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1422,9 +1475,9 @@ list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        __r = iterator(__hold.get(), this);
+        __r = iterator(__hold.get()->__as_link(), this);
 #else
-        __r = iterator(__hold.get());
+        __r = iterator(__hold.get()->__as_link());
 #endif
         __hold.release();
         iterator __e = __r;
@@ -1436,7 +1489,7 @@ list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold.get()->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
@@ -1447,8 +1500,8 @@ list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1474,7 +1527,8 @@ list<_Tp, _Alloc>::push_front(const value_type& __x)
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes_at_front(__hold.get(), __hold.get());
+    __link_pointer __nl = __hold->__as_link();
+    __link_nodes_at_front(__nl, __nl);
     ++base::__sz();
     __hold.release();
 }
@@ -1487,7 +1541,7 @@ list<_Tp, _Alloc>::push_back(const value_type& __x)
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-    __link_nodes_at_back(__hold.get(), __hold.get());
+    __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
@@ -1502,7 +1556,7 @@ list<_Tp, _Alloc>::push_front(value_type&& __x)
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes_at_front(__hold.get(), __hold.get());
+    __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
@@ -1515,7 +1569,7 @@ list<_Tp, _Alloc>::push_back(value_type&& __x)
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes_at_back(__hold.get(), __hold.get());
+    __link_nodes_at_back(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
@@ -1531,7 +1585,7 @@ list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_nodes_at_front(__hold.get(), __hold.get());
+    __link_nodes_at_front(__hold.get()->__as_link(), __hold.get()->__as_link());
     ++base::__sz();
     __hold.release();
 }
@@ -1545,7 +1599,8 @@ list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
     typedef __allocator_destructor<__node_allocator> _Dp;
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_nodes_at_back(__hold.get(), __hold.get());
+    __link_pointer __nl = __hold->__as_link();
+    __link_nodes_at_back(__nl, __nl);
     ++base::__sz();
     __hold.release();
 }
@@ -1565,12 +1620,14 @@ list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
-    __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
+    __link_pointer __nl = __hold.get()->__as_link();
+    __link_nodes(__p.__ptr_, __nl, __nl);
     ++base::__sz();
+    __hold.release();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__nl, this);
 #else
-    return iterator(__hold.release());
+    return iterator(__nl);
 #endif
 }
 
@@ -1590,12 +1647,14 @@ list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
     unique_ptr<__node, _Dp> __hold(__node_alloc_traits::allocate(__na, 1), _Dp(__na, 1));
     __hold->__prev_ = 0;
     __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
-    __link_nodes(__p.__ptr_, __hold.get(), __hold.get());
+    __link_pointer __nl = __hold->__as_link();
+    __link_nodes(__p.__ptr_, __nl, __nl);
     ++base::__sz();
+    __hold.release();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return iterator(__hold.release(), this);
+    return iterator(__nl, this);
 #else
-    return iterator(__hold.release());
+    return iterator(__nl);
 #endif
 }
 
@@ -1607,7 +1666,7 @@ list<_Tp, _Alloc>::pop_front()
 {
     _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = base::__end_.__next_;
+    __link_pointer __n = base::__end_.__next_;
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1625,8 +1684,9 @@ list<_Tp, _Alloc>::pop_front()
     }
     __get_db()->unlock();
 #endif
-    __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-    __node_alloc_traits::deallocate(__na, __n, 1);
+    __node_pointer __np = __n->__as_node();
+    __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+    __node_alloc_traits::deallocate(__na, __np, 1);
 }
 
 template <class _Tp, class _Alloc>
@@ -1635,7 +1695,7 @@ list<_Tp, _Alloc>::pop_back()
 {
     _LIBCPP_ASSERT(!empty(), "list::pop_back() called with empty list");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = base::__end_.__prev_;
+    __link_pointer __n = base::__end_.__prev_;
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1653,8 +1713,9 @@ list<_Tp, _Alloc>::pop_back()
     }
     __get_db()->unlock();
 #endif
-    __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-    __node_alloc_traits::deallocate(__na, __n, 1);
+    __node_pointer __np = __n->__as_node();
+    __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+    __node_alloc_traits::deallocate(__na, __np, 1);
 }
 
 template <class _Tp, class _Alloc>
@@ -1669,8 +1730,8 @@ list<_Tp, _Alloc>::erase(const_iterator __p)
     _LIBCPP_ASSERT(__p != end(),
         "list::erase(iterator) called with a non-dereferenceable iterator");
     __node_allocator& __na = base::__node_alloc();
-    __node_pointer __n = __p.__ptr_;
-    __node_pointer __r = __n->__next_;
+    __link_pointer __n = __p.__ptr_;
+    __link_pointer __r = __n->__next_;
     base::__unlink_nodes(__n, __n);
     --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1688,8 +1749,9 @@ list<_Tp, _Alloc>::erase(const_iterator __p)
     }
     __get_db()->unlock();
 #endif
-    __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-    __node_alloc_traits::deallocate(__na, __n, 1);
+    __node_pointer __np = __n->__as_node();
+    __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+    __node_alloc_traits::deallocate(__na, __np, 1);
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__r, this);
 #else
@@ -1712,7 +1774,7 @@ list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
         base::__unlink_nodes(__f.__ptr_, __l.__ptr_->__prev_);
         while (__f != __l)
         {
-            __node_pointer __n = __f.__ptr_;
+            __link_pointer __n = __f.__ptr_;
             ++__f;
             --base::__sz();
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1730,8 +1792,9 @@ list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
             }
             __get_db()->unlock();
 #endif
-            __node_alloc_traits::destroy(__na, _VSTD::addressof(__n->__value_));
-            __node_alloc_traits::deallocate(__na, __n, 1);
+            __node_pointer __np = __n->__as_node();
+            __node_alloc_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+            __node_alloc_traits::deallocate(__na, __np, 1);
         }
     }
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1758,9 +1821,9 @@ list<_Tp, _Alloc>::resize(size_type __n)
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
         ++__ds;
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        iterator __r = iterator(__hold.release(), this);
+        iterator __r = iterator(__hold.release()->__as_link(), this);
 #else
-        iterator __r = iterator(__hold.release());
+        iterator __r = iterator(__hold.release()->__as_link());
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
@@ -1771,7 +1834,7 @@ list<_Tp, _Alloc>::resize(size_type __n)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold.get()->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
@@ -1782,8 +1845,8 @@ list<_Tp, _Alloc>::resize(size_type __n)
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1816,10 +1879,11 @@ list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
         __hold->__prev_ = 0;
         __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
         ++__ds;
+        __link_pointer __nl = __hold.release()->__as_link();
 #if _LIBCPP_DEBUG_LEVEL >= 2
-        iterator __r = iterator(__hold.release(), this);
+        iterator __r = iterator(__nl, this);
 #else
-        iterator __r = iterator(__hold.release());
+        iterator __r = iterator(__nl);
 #endif
         iterator __e = __r;
 #ifndef _LIBCPP_NO_EXCEPTIONS
@@ -1830,7 +1894,7 @@ list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
             {
                 __hold.reset(__node_alloc_traits::allocate(__na, 1));
                 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
-                __e.__ptr_->__next_ = __hold.get();
+                __e.__ptr_->__next_ = __hold.get()->__as_link();
                 __hold->__prev_ = __e.__ptr_;
                 __hold.release();
             }
@@ -1841,8 +1905,8 @@ list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
             while (true)
             {
                 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
-                __node_pointer __prev = __e.__ptr_->__prev_;
-                __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
+                __link_pointer __prev = __e.__ptr_->__prev_;
+                __node_alloc_traits::deallocate(__na, __e.__ptr_->__as_node(), 1);
                 if (__prev == 0)
                     break;
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1854,8 +1918,7 @@ list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
             throw;
         }
 #endif  // _LIBCPP_NO_EXCEPTIONS
-        __link_nodes(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::
-                         pointer_to(base::__end_)), __r.__ptr_, __e.__ptr_);
+        __link_nodes(base::__end_as_link(), __r.__ptr_, __e.__ptr_);
         base::__sz() += __ds;
     }
 }
@@ -1873,8 +1936,8 @@ list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
 #endif
     if (!__c.empty())
     {
-        __node_pointer __f = __c.__end_.__next_;
-        __node_pointer __l = __c.__end_.__prev_;
+        __link_pointer __f = __c.__end_.__next_;
+        __link_pointer __l = __c.__end_.__prev_;
         base::__unlink_nodes(__f, __l);
         __link_nodes(__p.__ptr_, __f, __l);
         base::__sz() += __c.__sz();
@@ -1887,8 +1950,7 @@ list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
         {
             --__p;
             iterator* __i = static_cast<iterator*>((*__p)->__i_);
-            if (__i->__ptr_ != static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
+            if (__i->__ptr_ != __c.__end_as_link())
             {
                 __cn1->__add(*__p);
                 (*__p)->__c_ = __cn1;
@@ -1918,7 +1980,7 @@ list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
 #endif
     if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
     {
-        __node_pointer __f = __i.__ptr_;
+        __link_pointer __f = __i.__ptr_;
         base::__unlink_nodes(__f, __f);
         __link_nodes(__p.__ptr_, __f, __f);
         --__c.__sz();
@@ -1972,9 +2034,9 @@ list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, con
             __c.__sz() -= __s;
             base::__sz() += __s;
         }
-        __node_pointer __first = __f.__ptr_;
+        __link_pointer __first = __f.__ptr_;
         --__l;
-        __node_pointer __last = __l.__ptr_;
+        __link_pointer __last = __l.__ptr_;
         base::__unlink_nodes(__first, __last);
         __link_nodes(__p.__ptr_, __first, __last);
 #if _LIBCPP_DEBUG_LEVEL >= 2
@@ -1985,7 +2047,7 @@ list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, con
         {
             --__p;
             iterator* __j = static_cast<iterator*>((*__p)->__i_);
-            for (__node_pointer __k = __f.__ptr_;
+            for (__link_pointer __k = __f.__ptr_;
                                           __k != __l.__ptr_; __k = __k->__next_)
             {
                 if (__j->__ptr_ == __k)
@@ -2097,8 +2159,8 @@ list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
                     ;
                 base::__sz() += __ds;
                 __c.__sz() -= __ds;
-                __node_pointer __f = __f2.__ptr_;
-                __node_pointer __l = __m2.__ptr_->__prev_;
+                __link_pointer __f = __f2.__ptr_;
+                __link_pointer __l = __m2.__ptr_->__prev_;
                 __f2 = __m2;
                 base::__unlink_nodes(__f, __l);
                 __m2 = _VSTD::next(__f1);
@@ -2117,8 +2179,7 @@ list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
         {
             --__p;
             iterator* __i = static_cast<iterator*>((*__p)->__i_);
-            if (__i->__ptr_ != static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(__c.__end_)))
+            if (__i->__ptr_ != __c.__end_as_link())
             {
                 __cn1->__add(*__p);
                 (*__p)->__c_ = __cn1;
@@ -2161,7 +2222,7 @@ list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __
     case 2:
         if (__comp(*--__e2, *__f1))
         {
-            __node_pointer __f = __e2.__ptr_;
+            __link_pointer __f = __e2.__ptr_;
             base::__unlink_nodes(__f, __f);
             __link_nodes(__f1.__ptr_, __f, __f);
             return __e2;
@@ -2177,8 +2238,8 @@ list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __
         iterator __m2 = _VSTD::next(__f2);
         for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
             ;
-        __node_pointer __f = __f2.__ptr_;
-        __node_pointer __l = __m2.__ptr_->__prev_;
+        __link_pointer __f = __f2.__ptr_;
+        __link_pointer __l = __m2.__ptr_->__prev_;
         __r = __f2;
         __e1 = __f2 = __m2;
         base::__unlink_nodes(__f, __l);
@@ -2195,8 +2256,8 @@ list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __
             iterator __m2 = _VSTD::next(__f2);
             for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
                 ;
-            __node_pointer __f = __f2.__ptr_;
-            __node_pointer __l = __m2.__ptr_->__prev_;
+            __link_pointer __f = __f2.__ptr_;
+            __link_pointer __l = __m2.__ptr_->__prev_;
             if (__e1 == __f2)
                 __e1 = __m2;
             __f2 = __m2;
@@ -2240,8 +2301,7 @@ template <class _Tp, class _Alloc>
 bool
 list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
 {
-    return __i->__ptr_ != static_cast<__node_pointer>(
-                       pointer_traits<__node_base_pointer>::pointer_to(const_cast<__node_base&>(this->__end_)));
+    return __i->__ptr_ != this->__end_as_link();
 }
 
 template <class _Tp, class _Alloc>
diff --git a/include/map b/include/map
index adfb4cdb5e9e..87add437a545 100644
--- a/include/map
+++ b/include/map
@@ -126,9 +126,11 @@ public:
     template <class... Args>
         iterator emplace_hint(const_iterator position, Args&&... args);
     pair<iterator, bool> insert(const value_type& v);
+    pair<iterator, bool> insert(      value_type&& v);                                // C++17
     template <class P>
         pair<iterator, bool> insert(P&& p);
     iterator insert(const_iterator position, const value_type& v);
+    iterator insert(const_iterator position,       value_type&& v);                   // C++17
     template <class P>
         iterator insert(const_iterator position, P&& p);
     template <class InputIterator>
@@ -336,9 +338,11 @@ public:
     template <class... Args>
         iterator emplace_hint(const_iterator position, Args&&... args);
     iterator insert(const value_type& v);
+    iterator insert(      value_type&& v);                                            // C++17
     template <class P>
         iterator insert(P&& p);
     iterator insert(const_iterator position, const value_type& v);
+    iterator insert(const_iterator position,       value_type&& v);                   // C++17
     template <class P>
         iterator insert(const_iterator position, P&& p);
     template <class InputIterator>
@@ -704,13 +708,8 @@ public:
     typedef pair<__key_type, __mapped_type>                      value_type;
     typedef typename _TreeIterator::difference_type              difference_type;
     typedef value_type&                                          reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<value_type>
-#else
-            rebind<value_type>::other
-#endif
-                                                                 pointer;
+    typedef typename __rebind_pointer<typename __pointer_traits::pointer, value_type>::type
+        pointer;
 
     _LIBCPP_INLINE_VISIBILITY
     __map_iterator() _NOEXCEPT {}
@@ -770,13 +769,8 @@ public:
     typedef pair<__key_type, __mapped_type>                      value_type;
     typedef typename _TreeIterator::difference_type              difference_type;
     typedef const value_type&                                    reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const value_type>
-#else
-            rebind<const value_type>::other
-#endif
-                                                                 pointer;
+    typedef typename __rebind_pointer<typename __pointer_traits::pointer, const value_type>::type
+        pointer;
 
     _LIBCPP_INLINE_VISIBILITY
     __map_const_iterator() _NOEXCEPT {}
@@ -1099,6 +1093,17 @@ public:
         insert(const_iterator __p, const value_type& __v)
             {return __tree_.__insert_unique(__p.__i_, __v);}
 
+#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool>
+        insert(     value_type&& __v) {return __tree_.__insert_unique(_VSTD::forward<value_type>(__v));}
+
+    _LIBCPP_INLINE_VISIBILITY
+    iterator
+        insert(const_iterator __p,       value_type&& __v)
+            {return __tree_.__insert_unique(__p.__i_, _VSTD::forward<value_type>(__v));}
+#endif
+
     template <class _InputIterator>
         _LIBCPP_INLINE_VISIBILITY
         void insert(_InputIterator __f, _InputIterator __l)
@@ -1950,6 +1955,15 @@ public:
     iterator insert(const_iterator __p, const value_type& __v)
             {return __tree_.__insert_multi(__p.__i_, __v);}
 
+#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert( value_type&& __v) {return __tree_.__insert_multi(_VSTD::forward<value_type>(__v));}
+
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __p, value_type&& __v)
+            {return __tree_.__insert_multi(__p.__i_, _VSTD::forward<value_type>(__v));}
+#endif
+
     template <class _InputIterator>
         _LIBCPP_INLINE_VISIBILITY
         void insert(_InputIterator __f, _InputIterator __l)
diff --git a/include/unordered_map b/include/unordered_map
index 3c774d4094e0..85a54a7b6ddb 100644
--- a/include/unordered_map
+++ b/include/unordered_map
@@ -656,7 +656,6 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator
 {
     _HashIterator __i_;
 
-    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
     typedef const typename _HashIterator::value_type::value_type::first_type key_type;
     typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;
 public:
@@ -664,13 +663,8 @@ public:
     typedef pair<key_type, mapped_type>                          value_type;
     typedef typename _HashIterator::difference_type              difference_type;
     typedef value_type&                                          reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<value_type>
-#else
-            rebind<value_type>::other
-#endif
-                                                                 pointer;
+    typedef typename __rebind_pointer<typename _HashIterator::pointer, value_type>::type
+        pointer;
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_iterator() _NOEXCEPT {}
@@ -712,7 +706,6 @@ class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
 {
     _HashIterator __i_;
 
-    typedef pointer_traits<typename _HashIterator::pointer>      __pointer_traits;
     typedef const typename _HashIterator::value_type::value_type::first_type key_type;
     typedef typename _HashIterator::value_type::value_type::second_type      mapped_type;
 public:
@@ -720,13 +713,8 @@ public:
     typedef pair<key_type, mapped_type>                          value_type;
     typedef typename _HashIterator::difference_type              difference_type;
     typedef const value_type&                                    reference;
-    typedef typename __pointer_traits::template
-#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
-            rebind<const value_type>
-#else
-            rebind<const value_type>::other
-#endif
-                                                                 pointer;
+    typedef typename __rebind_pointer<typename _HashIterator::pointer, const value_type>::type
+        pointer;
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_const_iterator() _NOEXCEPT {}