Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -860,10 +860,19 @@
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     template <class _ValueTp>
     _LIBCPP_INLINE_VISIBILITY
-    pair<iterator, bool> __insert_unique_value(_ValueTp&& __x);
+    pair<iterator, bool> __insert_unique_value(_ValueTp&& __x)
+        {return __insert_unique_key_value(__x, std::forward<_ValueTp>(__x));}
+    template <class _KeyTp, class _ValueTp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_unique_key_value(const _KeyTp& __key, _ValueTp&& __x);
 #else
+    template <class _ValueTp>
     _LIBCPP_INLINE_VISIBILITY
-    pair<iterator, bool> __insert_unique_value(const value_type& __x);
+    pair<iterator, bool> __insert_unique_value(const _ValueTp& __x) {
+        {return __insert_unique_key_value(__x, __x);}
+    template <class _ValueTp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_unique_key_value(const _ValueTp& __key, const _ValueTp& __x);
 #endif
 
     pair<iterator, bool> __insert_unique(const value_type& __x);
@@ -1696,21 +1705,22 @@
 
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _ValueTp>
+template <class _KeyTp, class _ValueTp>
 _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>::__insert_unique_key_value(const _KeyTp& __key, _ValueTp&& __x)
 #else
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _RawValueTp>
 _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>::__insert_unique_key_value(const _RawValueTp& __key, const _RawValueTp& __x)
 #endif
 {
 #if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
-    typedef const value_type& _ValueTp;
+    typedef const _RawValueTp& _ValueTp;
 #endif
-    size_t __hash = hash_function()(__x);
+    size_t __hash = hash_function()(__key);
     size_type __bc = bucket_count();
     bool __inserted = false;
     __node_pointer __nd;
@@ -1725,7 +1735,7 @@
                                        __constrain_hash(__nd->__hash_, __bc) == __chash;
                                                            __nd = __nd->__next_)
             {
-                if (key_eq()(__nd->__value_, __x))
+                if (key_eq()(__nd->__value_, __key))
                     goto __done;
             }
         }
Index: include/unordered_map
===================================================================
--- include/unordered_map
+++ include/unordered_map
@@ -398,6 +398,11 @@
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Cp& __x) const
         {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
+#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    size_t operator()(const typename _Cp::value_type& __x) const
+        {return static_cast<const _Hash&>(*this)(__x.first);}
+#endif
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Key& __x) const
         {return static_cast<const _Hash&>(*this)(__x);}
@@ -428,6 +433,11 @@
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Cp& __x) const
         {return __hash_(__x.__cc.first);}
+#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    size_t operator()(const typename _Cp::value_type& __x) const
+        {return __hash_(__x.first);}
+#endif
     _LIBCPP_INLINE_VISIBILITY
     size_t operator()(const _Key& __x) const
         {return __hash_(__x);}
@@ -475,6 +485,11 @@
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Key& __x, const _Cp& __y) const
         {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
+#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    bool operator()(const _Cp& __x, const typename _Cp::value_type& __y) const
+        {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.first);}
+#endif
     void swap(__unordered_map_equal&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
     {
@@ -508,6 +523,11 @@
     _LIBCPP_INLINE_VISIBILITY
     bool operator()(const _Key& __x, const _Cp& __y) const
         {return __pred_(__x, __y.__cc.first);}
+#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
+    _LIBCPP_INLINE_VISIBILITY
+    bool operator()(const _Cp& __x, const typename _Cp::value_type& __y) const
+        {return __pred_(__x.__cc.first, __y.first);}
+#endif
     void swap(__unordered_map_equal&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
     {
@@ -966,13 +986,47 @@
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> insert(const value_type& __x)
-        {return __table_.__insert_unique(__x);}
+        {return __table_.__insert_unique_value(__x);}
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     template <class _Pp,
               class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
-        _LIBCPP_INLINE_VISIBILITY
-        pair<iterator, bool> insert(_Pp&& __x)
-            {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> insert(_Pp&& __x)
+        {return __insert_extract_key_if_pair(_VSTD::forward<_Pp>(__x));}
+
+private:
+    template <class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_extract_key_if_pair(_Pp&& __x)
+        {return __table_.__insert_unique(std::forward<_Pp>(__x));}
+    template <class _FirstTp, class _SecondTp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_extract_key_if_pair(pair<_FirstTp, _SecondTp>&& __x)
+        {return __insert_extract_key<_FirstTp>(_VSTD::move(__x));}
+    template <class _FirstTp, class _SecondTp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_extract_key_if_pair(const pair<_FirstTp, _SecondTp>& __x)
+        {return __insert_extract_key<_FirstTp>(__x);}
+
+    template <class _FirstTp, class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_extract_key(_Pp&& __x)
+        {
+            return __insert_extract_key_if_referenceable<_FirstTp>(
+                _VSTD::forward<_Pp>(__x),
+                is_same<typename remove_const<_FirstTp>::type, key_type>());
+        }
+
+    template <class _FirstTp, class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_extract_key_if_referenceable(_Pp&& __x, false_type)
+        {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
+    template <class _FirstTp, class _Pp>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<iterator, bool> __insert_extract_key_if_referenceable(_Pp&& __x, true_type)
+        {return __table_.__insert_unique_key_value(__x.first, _VSTD::forward<_Pp>(__x));}
+
+public:
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
     _LIBCPP_INLINE_VISIBILITY
 #if _LIBCPP_DEBUG_LEVEL >= 2
Index: test/libcxx/containers/unord/unord.map/insert_dup_alloc.pass.cpp
===================================================================
--- /dev/null
+++ test/libcxx/containers/unord/unord.map/insert_dup_alloc.pass.cpp
@@ -0,0 +1,87 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// Check that we don't allocate when trying to insert a duplicate value into a
+// unordered_map.
+
+#include <cassert>
+#include <unordered_map>
+#include "count_new.hpp"
+#include "MoveOnly.h"
+
+int main()
+{
+    {
+    std::unordered_map<int, int> s;
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    for(int i=0; i < 100; ++i) {
+        s.insert(std::make_pair(3, i));
+        s.insert(std::make_pair(3, unsigned(i)));
+        s.insert(s.end(), std::make_pair(3, i));
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+        s.emplace(std::make_pair(3, i));
+        s.emplace_hint(s.end(), std::make_pair(3, i));
+#endif
+        {
+            const std::pair<int, int> P(3, i);
+            s.insert(P);
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+            s.emplace(P);
+            s.emplace_hint(s.end(), P);
+#endif
+        }
+    }
+
+    assert(s.size() == 1);
+    assert(s.count(3) == 1);
+    assert(s.at(3) == 0);
+    assert(globalMemCounter.checkNewCalledEq(2));
+    }
+    assert(globalMemCounter.checkOutstandingNewEq(0));
+    globalMemCounter.reset();
+#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
+    {
+    std::unordered_map<MoveOnly, MoveOnly> s;
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    for(int i=0; i<100; i++) {
+        s.insert(std::make_pair(MoveOnly(3), MoveOnly(i)));
+        s.insert(s.end(), std::make_pair(MoveOnly(3), MoveOnly(i)));
+        s.emplace(std::make_pair(MoveOnly(3), MoveOnly(i)));
+        s.emplace_hint(s.end(), std::make_pair(MoveOnly(3), MoveOnly(i)));
+    }
+
+    assert(s.size() == 1);
+    assert(s.count(MoveOnly(3)) == 1);
+    assert(s.at(MoveOnly(3)) == 0);
+    assert(globalMemCounter.checkNewCalledEq(2));
+    }
+    assert(globalMemCounter.checkOutstandingNewEq(0));
+    globalMemCounter.reset();
+    {
+    std::unordered_map<int, MoveOnly> s;
+    assert(globalMemCounter.checkNewCalledEq(0));
+
+    for(int i=0; i<100; i++) {
+        s.insert(std::make_pair(3, MoveOnly(i)));
+        s.insert(s.end(), std::make_pair(3, MoveOnly(i)));
+        s.emplace(std::make_pair(3, MoveOnly(i)));
+        s.emplace_hint(s.end(), std::make_pair(3, MoveOnly(i)));
+    }
+
+    assert(s.size() == 1);
+    assert(s.count(3) == 1);
+    assert(s.at(3) == 0);
+    assert(globalMemCounter.checkNewCalledEq(2));
+    }
+    assert(globalMemCounter.checkOutstandingNewEq(0));
+    globalMemCounter.reset();
+#endif
+}