Teach __hash_table how to handle unordered_map's __hash_value_type.

This patch is fairly large and contains a number of changes. The main change
is teaching '__hash_table' how to handle '__hash_value_type'. Unfortunately
this change is a rampant layering violation, but it's required to make
unordered_map conforming without re-writing all of __hash_table.
After this change 'unordered_map' can delegate to '__hash_table' in almost all cases.

The major changes found in this patch are:

  * Teach __hash_table to differentiate between the true container value type
    and the node value type by introducing the "__container_value_type" and
    "__node_value_type" typedefs. In the case of unordered_map '__container_value_type'
    is 'pair<const Key, Value>' and '__node_value_type' is '__hash_value_type'.
    
  * Switch almost all overloads in '__hash_table' previously taking 'value_type'
    (AKA '__node_value_type) to take  '__container_value_type' instead. Previously
    'pair<K, V>' would be implicitly converted to '__hash_value_type<K, V>' because
    of the function signature.
    
  * Add '__get_key', '__get_value', '__get_ptr', and '__move' static functions to
    '__key_value_types'. These functions allow '__hash_table' to unwrap
    '__node_value_type' objects into '__container_value_type' and its sub-parts.

  * Pass  '__hash_value_type::__value_'  to 'a.construct(p, ...)' instead of
    '__hash_value_type' itself. The C++14 standard requires that 'a.construct()'
    and 'a.destroy()' are only ever instantiated for the containers value type.

  * Remove '__hash_value_type's constructors and destructors. We should never
    construct an instance of this type.
    (TODO this is UB but we already do it in plenty of places).
  
  * Add a generic "try-emplace" function to '__hash_table' called
    '__emplace_unique_key_args(Key const&, Args...)'.

  
The following changes were done as cleanup:

  * Introduce the '_LIBCPP_CXX03_LANG' macro to be used in place of
    '_LIBCPP_HAS_NO_VARIADICS' or '_LIBCPP_HAS_NO_RVALUE_REFERENCE'.
    
  * Cleanup C++11 only overloads that assume an incomplete C++11 implementation.
    For example this patch removes the __construct_node overloads that do
    manual pack expansion.
    
  * Forward 'unordered_map::emplace' to '__hash_table' and remove dead code
    resulting from the change. This includes almost all
    'unordered_map::__construct_node' overloads.


The following changes are planed for future revisions:

  * Fix LWG issue #2469 by delegating 'unordered_map::operator[]' to use
    '__emplace_unique_key_args'.
    
  * Rewrite 'unordered_map::try_emplace' in terms of '__emplace_unique_key_args'.
  
  * Optimize '__emplace_unique' to call '__emplace_unique_key_args' when possible.
    This prevent unneeded allocations when inserting duplicate entries.


The additional follow up work needed after this patch:

  * Respect the lifetime rules for '__hash_value_type' by actually constructing it.
  * Make '__insert_multi' act similar to '__insert_unique' for objects of type
    'T&' and 'T const &&' with 'T = __container_value_type'.
  
  

llvm-svn: 260513

1 files changed, 191 insertions, 146 deletions

diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index 5f21de4ceac..c35c6dfcdf5 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -30,6 +30,29 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+
+#ifndef _LIBCPP_CXX03_LANG
+template <class _Key, class _Tp>
+union __hash_value_type;
+#else
+template <class _Key, class _Tp>
+struct __hash_value_type;
+#endif
+
+#ifndef _LIBCPP_CXX03_LANG
+template <class _Tp>
+struct __is_hash_value_type_imp : false_type {};
+
+template <class _Key, class _Value>
+struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value>> : true_type {};
+
+template <class ..._Args>
+struct __is_hash_value_type : false_type {};
+
+template <class _One>
+struct __is_hash_value_type<_One> : __is_hash_value_type_imp<typename __uncvref<_One>::type> {};
+#endif
+
 _LIBCPP_FUNC_VIS
 size_t __next_prime(size_t __n);
 
@@ -86,14 +109,6 @@ template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_it
 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
 
-#if __cplusplus >= 201103L
-template <class _Key, class _Tp>
-union __hash_value_type;
-#else
-template <class _Key, class _Tp>
-struct __hash_value_type;
-#endif
-
 template <class _Tp>
 struct __key_value_types {
   static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
@@ -101,6 +116,25 @@ struct __key_value_types {
   typedef _Tp __node_value_type;
   typedef _Tp __container_value_type;
   static const bool __is_map = false;
+
+  _LIBCPP_INLINE_VISIBILITY
+  static key_type const& __get_key(_Tp const& __v) {
+    return __v;
+  }
+  _LIBCPP_INLINE_VISIBILITY
+  static __container_value_type const& __get_value(__node_value_type const& __v) {
+    return __v;
+  }
+  _LIBCPP_INLINE_VISIBILITY
+  static __container_value_type* __get_ptr(__node_value_type& __n) {
+    return _VSTD::addressof(__n);
+  }
+#ifndef _LIBCPP_CXX03_LANG
+  _LIBCPP_INLINE_VISIBILITY
+  static  __container_value_type&& __move(__node_value_type& __v) {
+    return _VSTD::move(__v);
+  }
+#endif
 };
 
 template <class _Key, class _Tp>
@@ -109,8 +143,42 @@ struct __key_value_types<__hash_value_type<_Key, _Tp> > {
   typedef _Tp                                          mapped_type;
   typedef __hash_value_type<_Key, _Tp>                 __node_value_type;
   typedef pair<const _Key, _Tp>                        __container_value_type;
+  typedef pair<_Key, _Tp>                              __nc_value_type;
   typedef __container_value_type                       __map_value_type;
   static const bool __is_map = true;
+
+  _LIBCPP_INLINE_VISIBILITY
+  static key_type const& __get_key(__container_value_type const& __v) {
+    return __v.first;
+  }
+
+  template <class _Up>
+  _LIBCPP_INLINE_VISIBILITY
+  static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value,
+      __container_value_type const&>::type
+  __get_value(_Up& __t) {
+    return __t.__cc;
+  }
+
+  template <class _Up>
+  _LIBCPP_INLINE_VISIBILITY
+  static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
+      __container_value_type const&>::type
+  __get_value(_Up& __t) {
+    return __t;
+  }
+
+  _LIBCPP_INLINE_VISIBILITY
+  static __container_value_type* __get_ptr(__node_value_type& __n) {
+    return _VSTD::addressof(__n.__cc);
+  }
+#ifndef _LIBCPP_CXX03_LANG
+  _LIBCPP_INLINE_VISIBILITY
+  static __nc_value_type&& __move(__node_value_type& __v) {
+    return _VSTD::move(__v.__nc);
+  }
+#endif
+
 };
 
 template <class _Tp, class _AllocPtr, class _KVTypes = __key_value_types<_Tp>,
@@ -787,6 +855,7 @@ class __hash_node_destructor
 public:
     typedef typename __alloc_traits::pointer                pointer;
 private:
+    typedef __hash_node_types<pointer> _NodeTypes;
 
     allocator_type& __na_;
 
@@ -806,7 +875,7 @@ public:
     void operator()(pointer __p) _NOEXCEPT
     {
         if (__value_constructed)
-            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
+            __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
         if (__p)
             __alloc_traits::deallocate(__na_, __p, 1);
     }
@@ -829,6 +898,9 @@ private:
       __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
                                                                      _NodeTypes;
 public:
+
+    typedef typename _NodeTypes::__node_value_type           __node_value_type;
+    typedef typename _NodeTypes::__container_value_type      __container_value_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
     typedef typename __alloc_traits::pointer         pointer;
@@ -925,7 +997,7 @@ public:
     explicit __hash_table(const allocator_type& __a);
     __hash_table(const __hash_table& __u);
     __hash_table(const __hash_table& __u, const allocator_type& __a);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
     __hash_table(__hash_table&& __u)
         _NOEXCEPT_(
             is_nothrow_move_constructible<__bucket_list>::value &&
@@ -934,11 +1006,11 @@ public:
             is_nothrow_move_constructible<hasher>::value &&
             is_nothrow_move_constructible<key_equal>::value);
     __hash_table(__hash_table&& __u, const allocator_type& __a);
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif  // _LIBCPP_CXX03_LANG
     ~__hash_table();
 
     __hash_table& operator=(const __hash_table& __u);
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     __hash_table& operator=(__hash_table&& __u)
         _NOEXCEPT_(
@@ -964,41 +1036,56 @@ public:
     iterator             __node_insert_multi(const_iterator __p,
                                              __node_pointer __nd);
 
-#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
+#ifndef _LIBCPP_CXX03_LANG
+    template <class _Key, class ..._Args>
+    pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
+
     template <class... _Args>
-        pair<iterator, bool> __emplace_unique(_Args&&... __args);
+    pair<iterator, bool> __emplace_unique(_Args&&... __args);
     template <class... _Args>
-        iterator __emplace_multi(_Args&&... __args);
+    iterator __emplace_multi(_Args&&... __args);
     template <class... _Args>
-        iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
-#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
+    iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
+
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-    template <class _ValueTp>
-    _LIBCPP_INLINE_VISIBILITY
-    pair<iterator, bool> __insert_unique_value(_ValueTp&& __x);
-#else
     _LIBCPP_INLINE_VISIBILITY
-    pair<iterator, bool> __insert_unique_value(const value_type& __x);
-#endif
+    pair<iterator, bool>
+    __insert_unique(__container_value_type&& __x) {
+      return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x));
+    }
 
-    pair<iterator, bool> __insert_unique(const value_type& __x);
+    template <class _Pp, class = typename enable_if<
+            !__is_same_uncvref<_Pp, __container_value_type>::value
+        >::type>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_unique(_Pp&& __x) {
+      return __emplace_unique(_VSTD::forward<_Pp>(__x));
+    }
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-    pair<iterator, bool> __insert_unique(value_type&& __x);
     template <class _Pp>
-    pair<iterator, bool> __insert_unique(_Pp&& __x);
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __insert_multi(_Pp&& __x) {
+      return __emplace_multi(_VSTD::forward<_Pp>(__x));
+    }
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-    template <class _Pp>
-        iterator __insert_multi(_Pp&& __x);
     template <class _Pp>
-        iterator __insert_multi(const_iterator __p, _Pp&& __x);
-#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-    iterator __insert_multi(const value_type& __x);
-    iterator __insert_multi(const_iterator __p, const value_type& __x);
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __insert_multi(const_iterator __p, _Pp&& __x) {
+        return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x));
+    }
+
+#else  // !defined(_LIBCPP_CXX03_LANG)
+    template <class _Key, class _Args>
+    pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args);
+
+    iterator __insert_multi(const __container_value_type& __x);
+    iterator __insert_multi(const_iterator __p, const __container_value_type& __x);
+#endif
+
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
+        return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
+    }
 
     void clear() _NOEXCEPT;
     void rehash(size_type __n);
@@ -1158,17 +1245,17 @@ public:
 private:
     void __rehash(size_type __n);
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
     template <class ..._Args>
-        __node_holder __construct_node(_Args&& ...__args);
-#endif  // _LIBCPP_HAS_NO_VARIADICS
-    template <class _ValueTp>
-    __node_holder __construct_node_hash(_ValueTp&& __v, size_t __hash);
-#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-    __node_holder __construct_node(const value_type& __v);
+    __node_holder __construct_node(_Args&& ...__args);
+
+    template <class _First, class ..._Rest>
+    __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
+#else // _LIBCPP_CXX03_LANG
+    __node_holder __construct_node(const __container_value_type& __v);
+    __node_holder __construct_node_hash(size_t __hash, const __container_value_type& __v);
 #endif
-    __node_holder __construct_node_hash(const value_type& __v, size_t __hash);
+
 
     _LIBCPP_INLINE_VISIBILITY
     void __copy_assign_alloc(const __hash_table& __u)
@@ -1178,6 +1265,7 @@ private:
     _LIBCPP_INLINE_VISIBILITY
         void __copy_assign_alloc(const __hash_table&, false_type) {}
 
+#ifndef _LIBCPP_CXX03_LANG
     void __move_assign(__hash_table& __u, false_type);
     void __move_assign(__hash_table& __u, true_type)
         _NOEXCEPT_(
@@ -1204,6 +1292,7 @@ private:
     }
     _LIBCPP_INLINE_VISIBILITY
         void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
+#endif // _LIBCPP_CXX03_LANG
 
     void __deallocate(__node_pointer __np) _NOEXCEPT;
     __node_pointer __detach() _NOEXCEPT;
@@ -1280,7 +1369,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
 {
 }
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
@@ -1329,7 +1418,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
     }
 }
 
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif  // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
@@ -1394,7 +1483,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np)
         }
         __get_db()->unlock();
 #endif
-        __node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
+        __node_traits::destroy(__na, _NodeTypes::__get_ptr(__np->__value_));
         __node_traits::deallocate(__na, __np, 1);
         __np = __next;
     }
@@ -1413,7 +1502,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
     return __cache;
 }
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
@@ -1486,8 +1575,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
         const_iterator __i = __u.begin();
         while (__u.size() != 0)
         {
-            __node_holder __h =
-                    __construct_node(_VSTD::move(__u.remove(__i++)->__value_));
+            __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_));
             __node_insert_multi(__h.get());
             __h.release();
         }
@@ -1509,7 +1597,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
     return *this;
 }
 
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif  // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _InputIterator>
@@ -1517,6 +1605,11 @@ void
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
                                                           _InputIterator __last)
 {
+    typedef iterator_traits<_InputIterator> _ITraits;
+    typedef typename _ITraits::value_type _ItValueType;
+    static_assert((is_same<_ItValueType, __container_value_type>::value),
+                  "__assign_unique may only be called with the containers value type");
+
     if (bucket_count() != 0)
     {
         __node_pointer __cache = __detach();
@@ -1551,6 +1644,12 @@ void
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
                                                          _InputIterator __last)
 {
+    typedef iterator_traits<_InputIterator> _ITraits;
+    typedef typename _ITraits::value_type _ItValueType;
+    static_assert((is_same<_ItValueType, __container_value_type>::value ||
+                  is_same<_ItValueType, __node_value_type>::value),
+                  "__assign_multi may only be called with the containers value type"
+                  " or the nodes value type");
     if (bucket_count() != 0)
     {
         __node_pointer __cache = __detach();
@@ -1576,7 +1675,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
         __deallocate(__cache);
     }
     for (; __first != __last; ++__first)
-        __insert_multi(*__first);
+        __insert_multi(_NodeTypes::__get_value(*__first));
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
@@ -1802,31 +1901,24 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
     return __node_insert_multi(__cp);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
-{
-    return __insert_unique_value(__x);
-}
 
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#ifndef _LIBCPP_CXX03_LANG
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _ValueTp>
+template <class _Key, class ..._Args>
 _LIBCPP_INLINE_VISIBILITY
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
 #else
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Key, class _Args>
 _LIBCPP_INLINE_VISIBILITY
 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args& __args)
 #endif
 {
-#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
-    typedef const value_type& _ValueTp;
-#endif
-    size_t __hash = hash_function()(__x);
+
+    size_t __hash = hash_function()(__k);
     size_type __bc = bucket_count();
     bool __inserted = false;
     __node_pointer __nd;
@@ -1841,13 +1933,17 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type
                                        __constrain_hash(__nd->__hash_, __bc) == __chash;
                                                            __nd = __nd->__next_)
             {
-                if (key_eq()(__nd->__value_, __x))
+                if (key_eq()(__nd->__value_, __k))
                     goto __done;
             }
         }
     }
     {
-        __node_holder __h = __construct_node_hash(_VSTD::forward<_ValueTp>(__x), __hash);
+#ifndef _LIBCPP_CXX03_LANG
+        __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
+#else
+        __node_holder __h = __construct_node_hash(__hash, __args);
+#endif
         if (size()+1 > __bc * max_load_factor() || __bc == 0)
         {
             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
@@ -1885,8 +1981,7 @@ __done:
 #endif
 }
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class... _Args>
@@ -1928,64 +2023,11 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
     return __r;
 }
 
-#endif  // _LIBCPP_HAS_NO_VARIADICS
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x)
-{
-    return __insert_unique_value(_VSTD::move(__x));
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Pp>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x)
-{
-    __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
-    pair<iterator, bool> __r = __node_insert_unique(__h.get());
-    if (__r.second)
-        __h.release();
-    return __r;
-}
-
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Pp>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x)
-{
-    __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
-    iterator __r = __node_insert_multi(__h.get());
-    __h.release();
-    return __r;
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Pp>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
-                                                         _Pp&& __x)
-{
-#if _LIBCPP_DEBUG_LEVEL >= 2
-    _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
-        "unordered container::insert(const_iterator, rvalue) called with an iterator not"
-        " referring to this unordered container");
-#endif
-    __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
-    iterator __r = __node_insert_multi(__p, __h.get());
-    __h.release();
-    return __r;
-}
-
-#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#else // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const __container_value_type& __x)
 {
     __node_holder __h = __construct_node(__x);
     iterator __r = __node_insert_multi(__h.get());
@@ -1996,7 +2038,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
-                                                         const value_type& __x)
+                                                         const __container_value_type& __x)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
@@ -2009,7 +2051,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
     return __r;
 }
 
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#endif  // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
@@ -2148,71 +2190,74 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
     return end();
 }
 
-#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
-#ifndef _LIBCPP_HAS_NO_VARIADICS
+#ifndef _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class ..._Args>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
 {
+    static_assert(!__is_hash_value_type<_Args...>::value,
+                  "Construct cannot be called with a hash value type");
     __node_allocator& __na = __node_alloc();
     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
+    __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
     __h.get_deleter().__value_constructed = true;
     __h->__hash_ = hash_function()(__h->__value_);
     __h->__next_ = nullptr;
     return __h;
 }
 
-#endif  // _LIBCPP_HAS_NO_VARIADICS
-
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _ValueTp>
+template <class _First, class ..._Rest>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(_ValueTp&& __v,
-                                                                size_t __hash)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
+    size_t __hash, _First&& __f, _Rest&& ...__rest)
 {
+    static_assert(!__is_hash_value_type<_First, _Rest...>::value,
+                  "Construct cannot be called with a hash value type");
     __node_allocator& __na = __node_alloc();
     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_ValueTp>(__v));
+    __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_),
+                             _VSTD::forward<_First>(__f),
+                             _VSTD::forward<_Rest>(__rest)...);
     __h.get_deleter().__value_constructed = true;
     __h->__hash_ = __hash;
     __h->__next_ = nullptr;
     return __h;
 }
 
-#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
+#else  // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const __container_value_type& __v)
 {
     __node_allocator& __na = __node_alloc();
     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
+    __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
     __h.get_deleter().__value_constructed = true;
     __h->__hash_ = hash_function()(__h->__value_);
     __h->__next_ = nullptr;
     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
 }
 
-#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
-
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(const value_type& __v,
-                                                                size_t __hash)
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash,
+                                                                const __container_value_type& __v)
 {
     __node_allocator& __na = __node_alloc();
     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
+    __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v);
     __h.get_deleter().__value_constructed = true;
     __h->__hash_ = __hash;
     __h->__next_ = nullptr;
     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
 }
 
+#endif  // _LIBCPP_CXX03_LANG
+
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)