[libcxx] Almost fix some UB in <map> and <unordered_map>

[erik.pilkington]

Summary

<map> and <unordered_map> define __value_type as a union between pair<K, V> and pair<const K, V> so that various operations can move into/from these pairs [1]. This is a pretty blatant strict aliasing violation, and has the potential break code that was optimized by TBAA. We can't remove this, not only would that be a significant pessimization, but we are also required to provide a non-const reference to the key_type to implement splicing maps & sets. This patch fixes __value_type by downgrading it from "accidentally launch the missiles"-level UB to theoretical UB, namely, instead of type-punning between pairs we just const_cast the key. It's still undefined to mutate a const object, but clang doesn't actually optimize on this rule. Just to be paranoid this patch also launder()s to "pick-up" the new value of key whenever we read from it, though this isn't launder's actual use-case. Thanks to @rsmith for the suggestions!

To do this, this patch:

• removes the __nc_value_type data member of the __value_type union
• provides access to the pair with pair<key_type&, mapped_type&>, which is used to assign through to the pair
• changes __value_type.__cc to __value_type.__get_value(), the latter calls std::launder in C++1z mode.

https://reviews.llvm.org/D46845 depends on this patch.

[1]: https://stackoverflow.com/a/31667355

Thanks for taking a look!
Erik

[rsmith]

libcxx/include/map

617 ↗

(On Diff #149358)

This doesn't need to be a union any more; change to class?

633 ↗

(On Diff #149358)

Formally this should be return *_VSTD::launder(&this->__cc);, because this must already point to an in-lifetime object or the member function call would have been invalid.

[EricWF]

Overall this change seems reasonable to me. Thanks for working on this. Initially I was concerned we would hit issues optimizing const objects,
but I should have read your description first! Thanks for ensuring Clang doesn't optimize on this.

One other concern I have is if there will be any performance impact to using launder all the time, but better safe than sorry.

Other than the inline comments, this LGTM.

libcxx/include/map

633 ↗

(On Diff #149358)

return *_VSTD::launder(_VSTD::addressof(this->__cc)); because ADL.

648 ↗

(On Diff #149358)

I think __ref can be private.

653 ↗

(On Diff #149358)

Add a newline?

708 ↗

(On Diff #149358)

_LIBCPP_INLINE_VISIBILITY here and below it.

libcxx/include/unordered_map

586 ↗

(On Diff #149358)

union -> class

597 ↗

(On Diff #149358)

_LIBCPP_INLINE_VISIBILITY

606 ↗

(On Diff #149358)

_LIBCPP_INLINE_VISIBILITY

615 ↗

(On Diff #149358)

This can be private.

621 ↗

(On Diff #149358)

_LIBCPP_INLINE_VISIBILITY

677 ↗

(On Diff #149358)

_LIBCPP_INLINE_VISIBILITY

[EricWF]

I should have asked, have we actually seen a midcompile caused by this? Is there a reproducer? Or is this purerly speculative?

[erik.pilkington]

Address review comments. Thanks!

[erik.pilkington]

In D47607#1118547, @EricWF wrote:

I should have asked, have we actually seen a midcompile caused by this? Is there a reproducer? Or is this purerly speculative?

Nope, pure speculation. I still think we should still fix this though.

libcxx/include/map

648 ↗

(On Diff #149358)

That's true for this patch, but I'm planning on using __ref in __node_handle to implement key() and mapped() so we don't have to duplicate the const cast.

[rsmith]

In D47607#1118464, @EricWF wrote:

One other concern I have is if there will be any performance impact to using launder all the time, but better safe than sorry.

In the short-to-medium term, I think we can tackle this by adding an attribute:

// ...
struct pair {
  T first;
  [[clang::not_actually_const]] U second;
};

... to directly express that the second field of a non-const pair is never a const subobject, even if U is a const-qualified type. I think we'll need this once we head down the path of constexpr containers, otherwise node_handles are not going to work in constant expression evaluation.

Then we can remove the launder calls for implementations that support the attribute.

libcxx/trunk/include/__hash_table

 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
 _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
 
 template <class _Key, class _Cp, class _Hash,
           bool =  is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
 class __unordered_map_hasher;
 
 template <class _Key, class _Cp, class _Pred,
           bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value
          >
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) {
+  static __container_value_type&& __move(__node_value_type& __v) {
     return _VSTD::move(__v);
   }
 #endif
 };
 
 template <class _Key, class _Tp>
 struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
   typedef _Key                                         key_type;
   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;
+    return __t.__get_value();
   }
 
   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);
+    return _VSTD::addressof(__n.__get_value());
   }
 #ifndef _LIBCPP_CXX03_LANG
   _LIBCPP_INLINE_VISIBILITY
-  static __nc_value_type&& __move(__node_value_type& __v) {
-    return _VSTD::move(__v.__nc);
+  static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {
+    return __v.__move();
   }
 #endif
 
 };
 
 template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>,
           bool = _KVTypes::__is_map>
 struct __hash_map_pointer_types {};

libcxx/trunk/include/__tree

template <class _Tp, class _NodePtr, class _DiffType>
     class _LIBCPP_TEMPLATE_VIS __tree_iterator;
 template <class _Tp, class _ConstNodePtr, class _DiffType>
     class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
 
 template <class _Pointer> class __tree_end_node;
 template <class _VoidPtr> class __tree_node_base;
 template <class _Tp, class _VoidPtr> class __tree_node;
 
-#ifndef _LIBCPP_CXX03_LANG
-template <class _Key, class _Value>
-union __value_type;
-#else
 template <class _Key, class _Value>
 struct __value_type;
-#endif
 
 template <class _Key, class _CP, class _Compare,
     bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
 class __map_value_compare;
 
 template <class _Allocator> class __map_node_destructor;
 template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_iterator;
 template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
struct __tree_key_value_types {
   _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) {
+  static __container_value_type&& __move(__node_value_type& __v) {
     return _VSTD::move(__v);
   }
 #endif
 };
 
 template <class _Key, class _Tp>
 struct __tree_key_value_types<__value_type<_Key, _Tp> > {
   typedef _Key                                         key_type;
   typedef _Tp                                          mapped_type;
   typedef __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(__node_value_type const& __t) {
-    return __t.__cc.first;
+    return __t.__get_value().first;
   }
 
   template <class _Up>
   _LIBCPP_INLINE_VISIBILITY
   static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
       key_type const&>::type
   __get_key(_Up& __t) {
     return __t.first;
   }
 
   _LIBCPP_INLINE_VISIBILITY
   static __container_value_type const&
   __get_value(__node_value_type const& __t) {
-    return __t.__cc;
+    return __t.__get_value();
   }
 
   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);
+    return _VSTD::addressof(__n.__get_value());
   }
 
 #ifndef _LIBCPP_CXX03_LANG
   _LIBCPP_INLINE_VISIBILITY
-  static  __nc_value_type&& __move(__node_value_type& __v) {
-    return _VSTD::move(__v.__nc);
+  static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {
+    return __v.__move();
   }
 #endif
 };
 
 template <class _VoidPtr>
 struct __tree_node_base_types {
   typedef _VoidPtr                                               __void_pointer;
 

libcxx/trunk/include/map

public:
     _LIBCPP_INLINE_VISIBILITY
     __map_value_compare(_Compare c)
         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
         : _Compare(c) {}
     _LIBCPP_INLINE_VISIBILITY
     const _Compare& key_comp() const _NOEXCEPT {return *this;}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _CP& __x, const _CP& __y) const
-        {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
+        {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _CP& __x, const _Key& __y) const
-        {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
+        {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Key& __x, const _CP& __y) const
-        {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
+        {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
     void swap(__map_value_compare&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
     {
       using _VSTD::swap;
       swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
     }
 
 #if _LIBCPP_STD_VER > 11
     template <typename _K2>
     _LIBCPP_INLINE_VISIBILITY
     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
     operator () ( const _K2& __x, const _CP& __y ) const
-        {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
+        {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}
 
     template <typename _K2>
     _LIBCPP_INLINE_VISIBILITY
     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
     operator () (const _CP& __x, const _K2& __y) const
-        {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
+        {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}
 #endif
 };
 
 template <class _Key, class _CP, class _Compare>
 class __map_value_compare<_Key, _CP, _Compare, false>
 {
     _Compare comp;
 
 public:
     _LIBCPP_INLINE_VISIBILITY
     __map_value_compare()
         _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
         : comp() {}
     _LIBCPP_INLINE_VISIBILITY
     __map_value_compare(_Compare c)
         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
         : comp(c) {}
     _LIBCPP_INLINE_VISIBILITY
     const _Compare& key_comp() const _NOEXCEPT {return comp;}
 
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _CP& __x, const _CP& __y) const
-        {return comp(__x.__cc.first, __y.__cc.first);}
+        {return comp(__x.__get_value().first, __y.__get_value().first);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _CP& __x, const _Key& __y) const
-        {return comp(__x.__cc.first, __y);}
+        {return comp(__x.__get_value().first, __y);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Key& __x, const _CP& __y) const
-        {return comp(__x, __y.__cc.first);}
+        {return comp(__x, __y.__get_value().first);}
     void swap(__map_value_compare&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
     {
         using _VSTD::swap;
         swap(comp, __y.comp);
     }
 
 #if _LIBCPP_STD_VER > 11
     template <typename _K2>
     _LIBCPP_INLINE_VISIBILITY
     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
     operator () ( const _K2& __x, const _CP& __y ) const
-        {return comp (__x, __y.__cc.first);}
+        {return comp (__x, __y.__get_value().first);}
 
     template <typename _K2>
     _LIBCPP_INLINE_VISIBILITY
     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
     operator () (const _CP& __x, const _K2& __y) const
-        {return comp (__x.__cc.first, __y);}
+        {return comp (__x.__get_value().first, __y);}
 #endif
 };
 
 template <class _Key, class _CP, class _Compare, bool __b>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
      __map_value_compare<_Key, _CP, _Compare, __b>& __y)
__map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
             __x.__value_constructed = false;
         }
 #endif  // _LIBCPP_CXX03_LANG
 
     _LIBCPP_INLINE_VISIBILITY
     void operator()(pointer __p) _NOEXCEPT
     {
         if (__second_constructed)
-            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
+            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
         if (__first_constructed)
-            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
+            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
         if (__p)
             __alloc_traits::deallocate(__na_, __p, 1);
     }
 };
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
     class map;
 template <class _Key, class _Tp, class _Compare, class _Allocator>
     class multimap;
 template <class _TreeIterator> class __map_const_iterator;
 
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp>
-union __value_type
+struct __value_type
 {
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
-    typedef pair<key_type, mapped_type>              __nc_value_type;
+    typedef pair<key_type&, mapped_type&>            __nc_ref_pair_type;
+    typedef pair<key_type&&, mapped_type&&>          __nc_rref_pair_type;
 
+private:
     value_type __cc;
-    __nc_value_type __nc;
+
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    value_type& __get_value()
+    {
+#if _LIBCPP_STD_VER > 14
+        return *_VSTD::launder(_VSTD::addressof(__cc));
+#else
+        return __cc;
+#endif
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    const value_type& __get_value() const
+    {
+#if _LIBCPP_STD_VER > 14
+        return *_VSTD::launder(_VSTD::addressof(__cc));
+#else
+        return __cc;
+#endif
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __nc_ref_pair_type __ref()
+    {
+        value_type& __v = __get_value();
+        return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __nc_rref_pair_type __move()
+    {
+        value_type& __v = __get_value();
+        return __nc_rref_pair_type(
+            _VSTD::move(const_cast<key_type&>(__v.first)),
+            _VSTD::move(__v.second));
+    }
 
     _LIBCPP_INLINE_VISIBILITY
     __value_type& operator=(const __value_type& __v)
-        {__nc = __v.__cc; return *this;}
+    {
+        __ref() = __v.__get_value();
+        return *this;
+    }
 
     _LIBCPP_INLINE_VISIBILITY
     __value_type& operator=(__value_type&& __v)
-        {__nc = _VSTD::move(__v.__nc); return *this;}
+    {
+        __ref() = __v.__move();
+        return *this;
+    }
 
     template <class _ValueTp,
               class = typename enable_if<
                     __is_same_uncvref<_ValueTp, value_type>::value
                  >::type
              >
     _LIBCPP_INLINE_VISIBILITY
-    __value_type& operator=(_ValueTp&& __v) {
-        __nc = _VSTD::forward<_ValueTp>(__v); return *this;
+    __value_type& operator=(_ValueTp&& __v)
+    {
+        __ref() = _VSTD::forward<_ValueTp>(__v);
+        return *this;
     }
 
 private:
     __value_type() _LIBCPP_EQUAL_DELETE;
     ~__value_type() _LIBCPP_EQUAL_DELETE;
     __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
     __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
 };
 
 #else
 
 template <class _Key, class _Tp>
 struct __value_type
 {
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
 
+private:
     value_type __cc;
 
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    value_type& __get_value() { return __cc; }
+    _LIBCPP_INLINE_VISIBILITY
+    const value_type& __get_value() const { return __cc; }
+
 private:
    __value_type();
    __value_type(__value_type const&);
    __value_type& operator=(__value_type const&);
    ~__value_type();
 };
 
 #endif // _LIBCPP_CXX03_LANG
public:
 
     _LIBCPP_INLINE_VISIBILITY
     __map_iterator() _NOEXCEPT {}
 
     _LIBCPP_INLINE_VISIBILITY
     __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
 
     _LIBCPP_INLINE_VISIBILITY
-    reference operator*() const {return __i_->__cc;}
+    reference operator*() const {return __i_->__get_value();}
     _LIBCPP_INLINE_VISIBILITY
-    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
+    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 
     _LIBCPP_INLINE_VISIBILITY
     __map_iterator& operator++() {++__i_; return *this;}
     _LIBCPP_INLINE_VISIBILITY
     __map_iterator operator++(int)
     {
         __map_iterator __t(*this);
         ++(*this);
public:
     _LIBCPP_INLINE_VISIBILITY
     __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
     _LIBCPP_INLINE_VISIBILITY
     __map_const_iterator(__map_iterator<
         typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
         : __i_(__i.__i_) {}
 
     _LIBCPP_INLINE_VISIBILITY
-    reference operator*() const {return __i_->__cc;}
+    reference operator*() const {return __i_->__get_value();}
     _LIBCPP_INLINE_VISIBILITY
-    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
+    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 
     _LIBCPP_INLINE_VISIBILITY
     __map_const_iterator& operator++() {++__i_; return *this;}
     _LIBCPP_INLINE_VISIBILITY
     __map_const_iterator operator++(int)
     {
         __map_const_iterator __t(*this);
         ++(*this);
template <class _Key, class _Tp, class _Compare = less<_Key>,
           class _Allocator = allocator<pair<const _Key, _Tp> > >
 class _LIBCPP_TEMPLATE_VIS map
 {
 public:
     // types:
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
-    typedef pair<key_type, mapped_type>              __nc_value_type;
     typedef _Compare                                 key_compare;
     typedef _Allocator                               allocator_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
 
     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                   "Allocator::value_type must be same type as value_type");
 

 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
 {
     if (__a != __m.get_allocator())
     {
         const_iterator __e = cend();
         while (!__m.empty())
             __tree_.__insert_unique(__e.__i_,
-                    _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
+                    __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
     }
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
 {
     return __tree_.__emplace_unique_key_args(__k,
         _VSTD::piecewise_construct,
         _VSTD::forward_as_tuple(__k),
-        _VSTD::forward_as_tuple()).first->__cc.second;
+        _VSTD::forward_as_tuple()).first->__get_value().second;
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
 {
     return __tree_.__emplace_unique_key_args(__k,
         _VSTD::piecewise_construct,
         _VSTD::forward_as_tuple(_VSTD::move(__k)),
-        _VSTD::forward_as_tuple()).first->__cc.second;
+        _VSTD::forward_as_tuple()).first->__get_value().second;
 }
 
 #else // _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
 {
     __node_allocator& __na = __tree_.__node_alloc();
     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
+    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
     __h.get_deleter().__first_constructed = true;
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
+    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
     __h.get_deleter().__second_constructed = true;
     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
 {
     __parent_pointer __parent;
     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
     __node_pointer __r = static_cast<__node_pointer>(__child);
     if (__child == nullptr)
     {
         __node_holder __h = __construct_node_with_key(__k);
         __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
         __r = __h.release();
     }
-    return __r->__value_.__cc.second;
+    return __r->__value_.__get_value().second;
 }
 
 #endif  // _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
 {
     __parent_pointer __parent;
     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
 #ifndef _LIBCPP_NO_EXCEPTIONS
     if (__child == nullptr)
         throw out_of_range("map::at:  key not found");
 #endif  // _LIBCPP_NO_EXCEPTIONS
-    return static_cast<__node_pointer>(__child)->__value_.__cc.second;
+    return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 const _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
 {
     __parent_pointer __parent;
     __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
 #ifndef _LIBCPP_NO_EXCEPTIONS
     if (__child == nullptr)
         throw out_of_range("map::at:  key not found");
 #endif  // _LIBCPP_NO_EXCEPTIONS
-    return static_cast<__node_pointer>(__child)->__value_.__cc.second;
+    return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
 }
 
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
            const map<_Key, _Tp, _Compare, _Allocator>& __y)
template <class _Key, class _Tp, class _Compare = less<_Key>,
           class _Allocator = allocator<pair<const _Key, _Tp> > >
 class _LIBCPP_TEMPLATE_VIS multimap
 {
 public:
     // types:
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
-    typedef pair<key_type, mapped_type>              __nc_value_type;
     typedef _Compare                                 key_compare;
     typedef _Allocator                               allocator_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
 
     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                   "Allocator::value_type must be same type as value_type");
 

 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
 {
     if (__a != __m.get_allocator())
     {
         const_iterator __e = cend();
         while (!__m.empty())
             __tree_.__insert_multi(__e.__i_,
-                    _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
+                    _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
     }
 }
 #endif
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,

libcxx/trunk/include/unordered_map

public:
     _LIBCPP_INLINE_VISIBILITY
     __unordered_map_hasher(const _Hash& __h)
         _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
         : _Hash(__h) {}
     _LIBCPP_INLINE_VISIBILITY
     const _Hash& hash_function() const _NOEXCEPT {return *this;}
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Cp& __x) const
-        {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
+        {return static_cast<const _Hash&>(*this)(__x.__get_value().first);}
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Key& __x) const
         {return static_cast<const _Hash&>(*this)(__x);}
     void swap(__unordered_map_hasher&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
     {
         using _VSTD::swap;
         swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
public:
     _LIBCPP_INLINE_VISIBILITY
     __unordered_map_hasher(const _Hash& __h)
         _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
         : __hash_(__h) {}
     _LIBCPP_INLINE_VISIBILITY
     const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Cp& __x) const
-        {return __hash_(__x.__cc.first);}
+        {return __hash_(__x.__get_value().first);}
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Key& __x) const
         {return __hash_(__x);}
     void swap(__unordered_map_hasher&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
     {
         using _VSTD::swap;
         swap(__hash_, __y.__hash_);
public:
     _LIBCPP_INLINE_VISIBILITY
     __unordered_map_equal(const _Pred& __p)
         _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
         : _Pred(__p) {}
     _LIBCPP_INLINE_VISIBILITY
     const _Pred& key_eq() const _NOEXCEPT {return *this;}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Cp& __x, const _Cp& __y) const
-        {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
+        {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Cp& __x, const _Key& __y) const
-        {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
+        {return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Key& __x, const _Cp& __y) const
-        {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
+        {return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);}
     void swap(__unordered_map_equal&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
     {
         using _VSTD::swap;
         swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
     }
 };
 
public:
     _LIBCPP_INLINE_VISIBILITY
     __unordered_map_equal(const _Pred& __p)
         _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
         : __pred_(__p) {}
     _LIBCPP_INLINE_VISIBILITY
     const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Cp& __x, const _Cp& __y) const
-        {return __pred_(__x.__cc.first, __y.__cc.first);}
+        {return __pred_(__x.__get_value().first, __y.__get_value().first);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Cp& __x, const _Key& __y) const
-        {return __pred_(__x.__cc.first, __y);}
+        {return __pred_(__x.__get_value().first, __y);}
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Key& __x, const _Cp& __y) const
-        {return __pred_(__x, __y.__cc.first);}
+        {return __pred_(__x, __y.__get_value().first);}
     void swap(__unordered_map_equal&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
     {
         using _VSTD::swap;
         swap(__pred_, __y.__pred_);
     }
 };
 
__hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
             const_cast<bool&>(__x.__value_constructed) = false;
         }
 #endif  // _LIBCPP_CXX03_LANG
 
     _LIBCPP_INLINE_VISIBILITY
     void operator()(pointer __p) _NOEXCEPT
     {
         if (__second_constructed)
-            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
+            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
         if (__first_constructed)
-            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
+            __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
         if (__p)
             __alloc_traits::deallocate(__na_, __p, 1);
     }
 };
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Key, class _Tp>
-union __hash_value_type
+struct __hash_value_type
 {
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
-    typedef pair<key_type, mapped_type>              __nc_value_type;
+    typedef pair<key_type&, mapped_type&>            __nc_ref_pair_type;
+    typedef pair<key_type&&, mapped_type&&>          __nc_rref_pair_type;
 
+private:
     value_type __cc;
-    __nc_value_type __nc;
+
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    value_type& __get_value()
+    {
+#if _LIBCPP_STD_VER > 14
+        return *_VSTD::launder(_VSTD::addressof(__cc));
+#else
+        return __cc;
+#endif
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    const value_type& __get_value() const
+    {
+#if _LIBCPP_STD_VER > 14
+        return *_VSTD::launder(_VSTD::addressof(__cc));
+#else
+        return __cc;
+#endif
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __nc_ref_pair_type __ref()
+    {
+        value_type& __v = __get_value();
+        return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __nc_rref_pair_type __move()
+    {
+        value_type& __v = __get_value();
+        return __nc_rref_pair_type(
+            _VSTD::move(const_cast<key_type&>(__v.first)),
+            _VSTD::move(__v.second));
+    }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_value_type& operator=(const __hash_value_type& __v)
-        {__nc = __v.__cc; return *this;}
+    {
+        __ref() = __v.__get_value();
+        return *this;
+    }
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_value_type& operator=(__hash_value_type&& __v)
-        {__nc = _VSTD::move(__v.__nc); return *this;}
+    {
+        __ref() = __v.__move();
+        return *this;
+    }
 
     template <class _ValueTp,
               class = typename enable_if<
                     __is_same_uncvref<_ValueTp, value_type>::value
                  >::type
              >
     _LIBCPP_INLINE_VISIBILITY
-    __hash_value_type& operator=(_ValueTp&& __v) {
-        __nc = _VSTD::forward<_ValueTp>(__v); return *this;
+    __hash_value_type& operator=(_ValueTp&& __v)
+    {
+        __ref() = _VSTD::forward<_ValueTp>(__v);
+        return *this;
     }
 
 private:
     __hash_value_type(const __hash_value_type& __v) = delete;
     __hash_value_type(__hash_value_type&& __v) = delete;
     template <class ..._Args>
     explicit __hash_value_type(_Args&& ...__args) = delete;
 
     ~__hash_value_type() = delete;
 };
 
 #else
 
 template <class _Key, class _Tp>
 struct __hash_value_type
 {
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
 
+private:
     value_type __cc;
 
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    value_type& __get_value() { return __cc; }
+    _LIBCPP_INLINE_VISIBILITY
+    const value_type& __get_value() const { return __cc; }
+
 private:
    ~__hash_value_type();
 };
 
 #endif
 
 template <class _HashIterator>
 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator
public:
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_iterator() _NOEXCEPT {}
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
 
     _LIBCPP_INLINE_VISIBILITY
-    reference operator*() const {return __i_->__cc;}
+    reference operator*() const {return __i_->__get_value();}
     _LIBCPP_INLINE_VISIBILITY
-    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
+    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_iterator& operator++() {++__i_; return *this;}
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_iterator operator++(int)
     {
         __hash_map_iterator __t(*this);
         ++(*this);
public:
     __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_const_iterator(
             __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
                  _NOEXCEPT
                 : __i_(__i.__i_) {}
 
     _LIBCPP_INLINE_VISIBILITY
-    reference operator*() const {return __i_->__cc;}
+    reference operator*() const {return __i_->__get_value();}
     _LIBCPP_INLINE_VISIBILITY
-    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
+    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
 
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_const_iterator& operator++() {++__i_; return *this;}
     _LIBCPP_INLINE_VISIBILITY
     __hash_map_const_iterator operator++(int)
     {
         __hash_map_const_iterator __t(*this);
         ++(*this);

 public:
     // types
     typedef _Key                                           key_type;
     typedef _Tp                                            mapped_type;
     typedef _Hash                                          hasher;
     typedef _Pred                                          key_equal;
     typedef _Alloc                                         allocator_type;
     typedef pair<const key_type, mapped_type>              value_type;
-    typedef pair<key_type, mapped_type>                    __nc_value_type;
     typedef value_type&                                    reference;
     typedef const value_type&                              const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
 
 private:
     typedef __hash_value_type<key_type, mapped_type>                 __value_type;
     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;

 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
     if (__a != __u.get_allocator())
     {
         iterator __i = __u.begin();
         while (__u.size() != 0) {
-            __table_.__emplace_unique(_VSTD::move(
-                __u.__table_.remove((__i++).__i_)->__value_.__nc));
+            __table_.__emplace_unique(
+                __u.__table_.remove((__i++).__i_)->__value_.__move());
         }
     }
 #if _LIBCPP_DEBUG_LEVEL >= 2
     else
         __get_db()->swap(this, &__u);
 #endif
 }
 

 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp&
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
 {
     return __table_.__emplace_unique_key_args(__k,
         std::piecewise_construct, std::forward_as_tuple(__k),
-                                  std::forward_as_tuple()).first->__cc.second;
+                                  std::forward_as_tuple()).first->__get_value().second;
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp&
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
 {
     return __table_.__emplace_unique_key_args(__k,
         std::piecewise_construct, std::forward_as_tuple(std::move(__k)),
-                                  std::forward_as_tuple()).first->__cc.second;
+                                  std::forward_as_tuple()).first->__get_value().second;
 }
 #else // _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
 {
     __node_allocator& __na = __table_.__node_alloc();
     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
+    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
     __h.get_deleter().__first_constructed = true;
-    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
+    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
     __h.get_deleter().__second_constructed = true;
     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
 }
 
 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
 _Tp&
 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
 {

 public:
     // types
     typedef _Key                                           key_type;
     typedef _Tp                                            mapped_type;
     typedef _Hash                                          hasher;
     typedef _Pred                                          key_equal;
     typedef _Alloc                                         allocator_type;
     typedef pair<const key_type, mapped_type>              value_type;
-    typedef pair<key_type, mapped_type>                    __nc_value_type;
     typedef value_type&                                    reference;
     typedef const value_type&                              const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
 
 private:
     typedef __hash_value_type<key_type, mapped_type>                 __value_type;
     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
#if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif
     if (__a != __u.get_allocator())
     {
         iterator __i = __u.begin();
         while (__u.size() != 0)
         {
             __table_.__insert_multi(
-                      _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc)
-                                   );
+                __u.__table_.remove((__i++).__i_)->__value_.__move());
         }
     }
 #if _LIBCPP_DEBUG_LEVEL >= 2
     else
         __get_db()->swap(this, &__u);
 #endif
 }