2013-04-22 François Dumont <fdumont@gcc.gnu.org>

	* include/bits/hashtable_policy.h: Add C++11 allocator support.
	* include/bits/hashtable.h: Likewise.
	* include/bits/unordered_set.h: Likewise.
	* include/bits/unordered_map.h: Likewise.
	* include/debug/unordered_set: Likewise.
	* include/debug/unordered_map: Likewise.
	* include/std/unordered_set: Remove bits/algobase.h
	include. Replace bits/alloc_traits.h by ext/alloc_traits.h.
	* include/std/unordered_map: Likewise.
	* include/ext/throw_allocator.h: Add checks on calls to allocator
	construct/destroy.
	(std::hash<__gnu_cxx::throw_value_limit>): Add conditional throw.
	(std::hash<__gnu_cxx::throw_value_random>): Likewise.
	* testsuite/util/regression/rand/priority_queue
	/container_rand_regression_test.tcc: Adapt.
	* testsuite/util/regression/rand/assoc
	/container_rand_regression_test.tcc: Likewise.
	* testsuite/util/testsuite_counter_type.h: Add count of destructors.
	* testsuite/23_containers/unordered_set
	/not_default_constructible_hash_neg.cc: Adjust dg-error line number.
	* testsuite/23_containers/unordered_set/instantiation_neg.cc: Likewise.
	* testsuite/23_containers/unordered_set/allocator/copy.cc: New.
	* testsuite/23_containers/unordered_set/allocator/copy_assign.cc: New.
	* testsuite/23_containers/unordered_set/allocator/minimal.cc: New.
	* testsuite/23_containers/unordered_set/allocator/move_assign.cc: New.
	* testsuite/23_containers/unordered_set/allocator/noexcept.cc: New.
	* testsuite/23_containers/unordered_set/allocator/swap.cc: New.
	* testsuite/23_containers/unordered_multiset/allocator/copy.cc: New.
	* testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc:
	New.
	* testsuite/23_containers/unordered_multiset/allocator/minimal.cc: New.
	* testsuite/23_containers/unordered_multiset/allocator/move_assign.cc:
	New.
	* testsuite/23_containers/unordered_multiset/allocator/noexcept.cc: New.
	* testsuite/23_containers/unordered_multiset/allocator/swap.cc: New.
	* testsuite/23_containers/unordered_map/allocator/copy.cc: New.
	* testsuite/23_containers/unordered_map/allocator/copy_assign.cc: New.
	* testsuite/23_containers/unordered_map/allocator/minimal.cc: New.
	* testsuite/23_containers/unordered_map/allocator/move_assign.cc: New.
	* testsuite/23_containers/unordered_map/allocator/noexcept.cc:
	New.
	* testsuite/23_containers/unordered_map/allocator/swap.cc: New.
	* testsuite/23_containers/unordered_multimap/allocator/copy.cc: New.
	* testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc:
	New.
	* testsuite/23_containers/unordered_multimap/allocator/minimal.cc: New.
	* testsuite/23_containers/unordered_multimap/allocator/move_assign.cc:
	New.
	* testsuite/23_containers/unordered_multimap/allocator/noexcept.cc: New.
	* testsuite/23_containers/unordered_multimap/allocator/swap.cc: New.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@198158 138bc75d-0d04-0410-961f-82ee72b054a4

9 files changed, 1109 insertions, 237 deletions

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 246e9bb3bcf..0ff6e132a83 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -183,18 +183,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 				 _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
+      typedef std::allocator_traits<_Alloc> _Alloc_traits;
+      typedef typename _Alloc_traits::template rebind_alloc<_Value>
+							_Value_alloc_type;
+      typedef __gnu_cxx::__alloc_traits<_Value_alloc_type> _Value_alloc_traits;
+
     public:
-      typedef _Key                                    key_type;
-      typedef _Value                                  value_type;
-      typedef _Alloc                                  allocator_type;
-      typedef _Equal                                  key_equal;
+      typedef _Key						key_type;
+      typedef _Value						value_type;
+      typedef _Alloc						allocator_type;
+      typedef _Equal						key_equal;
 
       // mapped_type, if present, comes from _Map_base.
       // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
-      typedef typename _Alloc::pointer		      pointer;
-      typedef typename _Alloc::const_pointer          const_pointer;
-      typedef typename _Alloc::reference              reference;
-      typedef typename _Alloc::const_reference        const_reference;
+      typedef typename _Value_alloc_traits::pointer		pointer;
+      typedef typename _Value_alloc_traits::const_pointer	const_pointer;
+      typedef value_type&					reference;
+      typedef const value_type&					const_reference;
 
     private:
       using __rehash_type = _RehashPolicy;
@@ -236,8 +241,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					    _RehashPolicy, _Traits>;
 
       // Metaprogramming for picking apart hash caching.
-      using __hash_noexcept = __detail::__is_noexcept_hash<_Key, _H1>;
-
       template<typename _Cond>
 	using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
 
@@ -246,12 +249,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Compile-time diagnostics.
 
-      // When hash codes are not cached the hash functor shall not
-      // throw because it is used in methods (erase, swap...) that
-      // shall not throw.
-      static_assert(__if_hash_not_cached<__hash_noexcept>::value,
-		    "Cache the hash code"
-		    " or qualify your hash functor with noexcept");
+      // Getting a bucket index from a node shall not throw because it is used
+      // in methods (erase, swap...) that shall not throw.
+      static_assert(noexcept(declval<const _Hashtable&>()
+			     ._M_bucket_index((const __node_type*)nullptr,
+					      (std::size_t)0)),
+		    "Cache the hash code or qualify your functors involved"
+		    " in hash code and bucket index computation with noexcept");
 
       // Following two static assertions are necessary to guarantee
       // that local_iterator will be default constructible.
@@ -302,6 +306,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       bool _Constant_iteratorsa, bool _Unique_keysa>
 	friend struct __detail::_Insert;
 
+      template<typename _Keya, typename _Valuea, typename _Alloca,
+	       typename _ExtractKeya, typename _Equala,
+	       typename _H1a, typename _H2a, typename _Hasha,
+	       typename _RehashPolicya, typename _Traitsa,
+	       bool _IsCopyAssignable>
+	friend struct __detail::_ReuseOrAllocNode;
+
+      template<typename _Keya, typename _Valuea, typename _Alloca,
+	       typename _ExtractKeya, typename _Equala,
+	       typename _H1a, typename _H2a, typename _Hasha,
+	       typename _RehashPolicya, typename _Traitsa,
+	       bool _IsMoveAssignable>
+	friend struct __detail::_MoveReuseOrAllocNode;
+
       using size_type = typename __hashtable_base::size_type;
       using difference_type = typename __hashtable_base::difference_type;
 
@@ -313,12 +331,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				   const_local_iterator;
 
     private:
-      typedef typename _Alloc::template rebind<__node_type>::other
-							_Node_allocator_type;
-      typedef typename _Alloc::template rebind<__bucket_type>::other
-							_Bucket_allocator_type;
+      typedef typename _Alloc_traits::template rebind_alloc<__node_type>
+							_Node_alloc_type;
+      // Use __gnu_cxx to benefit from _S_always_equal and al.
+      typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
 
-      using __before_begin = __detail::_Before_begin<_Node_allocator_type>;
+      typedef
+      typename _Alloc_traits::template rebind_alloc<__bucket_type>
+							_Bucket_alloc_type;
+      typedef std::allocator_traits<_Bucket_alloc_type> _Bucket_alloc_traits;
+
+      using __before_begin = __detail::_Before_begin<_Node_alloc_type>;
 
       __bucket_type*		_M_buckets;
       size_type			_M_bucket_count;
@@ -326,11 +349,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       size_type			_M_element_count;
       _RehashPolicy		_M_rehash_policy;
 
-      _Node_allocator_type&
+      _Node_alloc_type&
       _M_node_allocator()
       { return _M_bbegin; }
 
-      const _Node_allocator_type&
+      const _Node_alloc_type&
       _M_node_allocator() const
       { return _M_bbegin; }
 
@@ -359,6 +382,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_deallocate_buckets(__bucket_type*, size_type __n);
 
+      void
+      _M_deallocate_buckets()
+      { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+
       // Gets bucket begin, deals with the fact that non-empty buckets contain
       // their before begin node.
       __node_type*
@@ -368,6 +395,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_begin() const
       { return static_cast<__node_type*>(_M_before_begin()._M_nxt); }
 
+      template<typename _UnaryOp>
+	void
+	_M_assign(const _Hashtable&, const _UnaryOp&);
+
+      void
+      _M_move_assign(_Hashtable&&, std::true_type);
+
+      void
+      _M_move_assign(_Hashtable&&, std::false_type);
+
+      void
+      _M_reset() noexcept;
+
     public:
       // Constructor, destructor, assignment, swap
       _Hashtable(size_type __bucket_hint,
@@ -384,10 +424,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       _Hashtable(const _Hashtable&);
 
-      _Hashtable(_Hashtable&&);
+      _Hashtable(_Hashtable&&) noexcept;
+
+      _Hashtable(const _Hashtable&, const allocator_type&);
+
+      _Hashtable(_Hashtable&&, const allocator_type&);
 
       // Use delegating constructors.
       explicit
+      _Hashtable(const allocator_type& __a)
+	: _Hashtable(10, _H1(), __detail::_Mod_range_hashing(),
+		     __detail::_Default_ranged_hash(), key_equal(),
+		     __key_extract(), __a)
+      { }
+
+      explicit
       _Hashtable(size_type __n = 10,
 		 const _H1& __hf = _H1(),
 		 const key_equal& __eql = key_equal(),
@@ -420,34 +471,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { }
 
       _Hashtable&
-      operator=(const _Hashtable& __ht)
-      {
-	_Hashtable __tmp(__ht);
-	this->swap(__tmp);
-	return *this;
-      }
+      operator=(const _Hashtable& __ht);
 
       _Hashtable&
       operator=(_Hashtable&& __ht)
+      noexcept(_Node_alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-	// NB: DR 675.
-	this->clear();
-	this->swap(__ht);
+        constexpr bool __move_storage =
+          _Node_alloc_traits::_S_propagate_on_move_assign()
+          || _Node_alloc_traits::_S_always_equal();
+        _M_move_assign(std::move(__ht),
+                       integral_constant<bool, __move_storage>());
 	return *this;
       }
 
       _Hashtable&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
+	clear();
 	this->insert(__l.begin(), __l.end());
 	return *this;
       }
 
       ~_Hashtable() noexcept;
 
-      void swap(_Hashtable&);
+      void
+      swap(_Hashtable&)
+      noexcept(_Node_alloc_traits::_S_nothrow_swap());
 
       // Basic container operations
       iterator
@@ -488,7 +538,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       max_size() const noexcept
-      { return _M_node_allocator().max_size(); }
+      { return _Node_alloc_traits::max_size(_M_node_allocator()); }
 
       // Observers
       key_equal
@@ -585,7 +635,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     protected:
       // Bucket index computation helpers.
       size_type
-      _M_bucket_index(__node_type* __n) const
+      _M_bucket_index(__node_type* __n) const noexcept
       { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
 
       size_type
@@ -682,7 +732,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       erase(const key_type& __k)
-      { return _M_erase(__unique_keys(), __k); }
+      {
+	if (__builtin_expect(_M_bucket_count == 0, false))
+	  return 0;
+	return _M_erase(__unique_keys(), __k);
+      }
 
       iterator
       erase(const_iterator, const_iterator);
@@ -721,15 +775,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_allocate_node(_Args&&... __args)
       {
-	__node_type* __n = _M_node_allocator().allocate(1);
+	__node_type* __n = _Node_alloc_traits::allocate(_M_node_allocator(), 1);
 	__try
 	  {
-	    _M_node_allocator().construct(__n, std::forward<_Args>(__args)...);
+	    _Value_alloc_type __a(_M_node_allocator());
+	    ::new ((void*)__n) __node_type();
+	    _Value_alloc_traits::construct(__a, __n->_M_valptr(),
+					   std::forward<_Args>(__args)...);
 	    return __n;
 	  }
 	__catch(...)
 	  {
-	    _M_node_allocator().deallocate(__n, 1);
+	    _Node_alloc_traits::deallocate(_M_node_allocator(), __n, 1);
 	    __throw_exception_again;
 	  }
       }
@@ -743,8 +800,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_deallocate_node(__node_type* __n)
     {
-      _M_node_allocator().destroy(__n);
-      _M_node_allocator().deallocate(__n, 1);
+      _Value_alloc_type __a(_M_node_allocator());
+      _Value_alloc_traits::destroy(__a, __n->_M_valptr());
+      __n->~__node_type();
+      _Node_alloc_traits::deallocate(_M_node_allocator(), __n, 1);
     }
 
   template<typename _Key, typename _Value,
@@ -774,9 +833,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_allocate_buckets(size_type __n)
     {
-      _Bucket_allocator_type __alloc(_M_node_allocator());
+      _Bucket_alloc_type __alloc(_M_node_allocator());
 
-      __bucket_type* __p = __alloc.allocate(__n);
+      __bucket_type* __p = _Bucket_alloc_traits::allocate(__alloc, __n);
       __builtin_memset(__p, 0, __n * sizeof(__bucket_type));
       return __p;
     }
@@ -788,10 +847,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_deallocate_buckets(__bucket_type* __p, size_type __n)
+    _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
     {
-      _Bucket_allocator_type __alloc(_M_node_allocator());
-      __alloc.deallocate(__p, __n);
+      _Bucket_alloc_type __alloc(_M_node_allocator());
+      _Bucket_alloc_traits::deallocate(__alloc, __bkts, __n);
     }
 
   template<typename _Key, typename _Value,
@@ -822,7 +881,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     : __hashtable_base(__exk, __h1, __h2, __h, __eq),
       __map_base(),
       __rehash_base(),
-      _M_bucket_count(0),
       _M_bbegin(__a),
       _M_element_count(0),
       _M_rehash_policy()
@@ -846,7 +904,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : __hashtable_base(__exk, __h1, __h2, __h, __eq),
 	__map_base(),
 	__rehash_base(),
-	_M_bucket_count(0),
 	_M_bbegin(__a),
 	_M_element_count(0),
 	_M_rehash_policy()
@@ -866,7 +923,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__catch(...)
 	  {
 	    clear();
-	    _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+	    _M_deallocate_buckets();
 	    __throw_exception_again;
 	  }
       }
@@ -876,49 +933,266 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>&
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::operator=(
+		const _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+				 _H1, _H2, _Hash, _RehashPolicy, _Traits>& __ht)
+      {
+	if (&__ht == this)
+	  return *this;
+
+	if (_Node_alloc_traits::_S_propagate_on_copy_assign())
+	  {
+	    auto& __this_alloc = this->_M_node_allocator();
+	    auto& __that_alloc = __ht._M_node_allocator();
+	    if (!_Node_alloc_traits::_S_always_equal()
+		&& __this_alloc != __that_alloc)
+	      {
+		// Replacement allocator cannot free existing storage.
+		_M_deallocate_nodes(_M_begin());
+		if (__builtin_expect(_M_bucket_count != 0, true))
+		  _M_deallocate_buckets();
+		_M_reset();
+		std::__alloc_on_copy(__this_alloc, __that_alloc);
+		__hashtable_base::operator=(__ht);
+		_M_bucket_count = __ht._M_bucket_count;
+		_M_element_count = __ht._M_element_count;
+		_M_rehash_policy = __ht._M_rehash_policy;
+		__try
+		  {
+		    _M_assign(__ht,
+			      [this](const __node_type* __n)
+			      { return _M_allocate_node(__n->_M_v()); });
+		  }
+		__catch(...)
+		  {
+		    // _M_assign took care of deallocating all memory. Now we
+		    // must make sure this instance remains in a usable state.
+		    _M_reset();
+		    __throw_exception_again;
+		  }
+		return *this;
+	      }
+	    std::__alloc_on_copy(__this_alloc, __that_alloc);
+	  }
+
+	// Reuse allocated buckets and nodes.
+	__bucket_type* __former_buckets = nullptr;
+	std::size_t __former_bucket_count = _M_bucket_count;
+	const __rehash_state& __former_state = _M_rehash_policy._M_state();
+	
+	if (_M_bucket_count != __ht._M_bucket_count)
+	  {
+	    __former_buckets = _M_buckets;
+	    _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
+	    _M_bucket_count = __ht._M_bucket_count;
+	  }
+	else
+	  __builtin_memset(_M_buckets, 0,
+			   _M_bucket_count * sizeof(__bucket_type));
+
+	__try
+	  {
+	    __hashtable_base::operator=(__ht);
+	    _M_element_count = __ht._M_element_count;
+	    _M_rehash_policy = __ht._M_rehash_policy;
+	    __detail::_ReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
+					_Equal, _H1, _H2, _Hash,
+					_RehashPolicy, _Traits>
+	      __roan(_M_begin(), *this);
+	    _M_before_begin()._M_nxt = nullptr;
+	    _M_assign(__ht, __roan);
+	    if (__former_buckets)
+	      _M_deallocate_buckets(__former_buckets, __former_bucket_count);
+	  }
+	__catch(...)
+	  {
+	    if (__former_buckets)
+	      {
+		// Restore previous buckets.
+		_M_deallocate_buckets();
+		_M_rehash_policy._M_reset(__former_state);
+		_M_buckets = __former_buckets;
+		_M_bucket_count = __former_bucket_count;
+	      }
+	    __builtin_memset(_M_buckets, 0,
+			     _M_bucket_count * sizeof(__bucket_type));
+	    __throw_exception_again;
+	  }
+	return *this;
+      }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    template<typename _UnaryOp>
+      void
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+      _M_assign(const _Hashtable& __ht, const _UnaryOp& __node_getter)
+      {
+	__bucket_type* __buckets = nullptr;
+	if (!_M_buckets)
+	  _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
+
+	__try
+	  {
+	    if (!__ht._M_before_begin()._M_nxt)
+	      return;
+
+	    // First deal with the special first node pointed to by
+	    // _M_before_begin.
+	    __node_type* __ht_n = __ht._M_begin();
+	    __node_type* __this_n = __node_getter(__ht_n);
+	    this->_M_copy_code(__this_n, __ht_n);
+	    _M_before_begin()._M_nxt = __this_n;
+	    _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin();
+
+	    // Then deal with other nodes.
+	    __node_base* __prev_n = __this_n;
+	    for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
+	      {
+		__this_n = __node_getter(__ht_n);
+		__prev_n->_M_nxt = __this_n;
+		this->_M_copy_code(__this_n, __ht_n);
+		size_type __bkt = _M_bucket_index(__this_n);
+		if (!_M_buckets[__bkt])
+		  _M_buckets[__bkt] = __prev_n;
+		__prev_n = __this_n;
+	      }
+	  }
+	__catch(...)
+	  {
+	    clear();
+	    if (__buckets)
+	      _M_deallocate_buckets();
+	    __throw_exception_again;
+	  }
+      }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    void
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_reset() noexcept
+    {
+      _M_rehash_policy._M_reset();
+      _M_bucket_count = 0;
+      _M_buckets = nullptr;
+      _M_before_begin()._M_nxt = nullptr;
+      _M_element_count = 0;
+    }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    void
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_move_assign(_Hashtable&& __ht, std::true_type)
+    {
+      _M_deallocate_nodes(_M_begin());
+      if (__builtin_expect(_M_bucket_count != 0, true))
+	_M_deallocate_buckets();
+
+      __hashtable_base::operator=(std::move(__ht));
+      _M_rehash_policy = __ht._M_rehash_policy;
+      _M_buckets = __ht._M_buckets;
+      _M_bucket_count = __ht._M_bucket_count;
+      _M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
+      _M_element_count = __ht._M_element_count;
+      std::__alloc_on_move(_M_node_allocator(), __ht._M_node_allocator());
+
+      // Fix buckets containing the _M_before_begin pointers that can't be
+      // moved.
+      if (_M_begin())
+	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+      __ht._M_reset();
+    }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    void
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_move_assign(_Hashtable&& __ht, std::false_type)
+    {
+      if (__ht._M_node_allocator() == _M_node_allocator())
+	_M_move_assign(std::move(__ht), std::true_type());
+      else
+	{
+	  // Can't move memory, move elements then.
+	  __bucket_type* __former_buckets = nullptr;
+	  size_type __former_bucket_count = _M_bucket_count;
+	  const __rehash_state& __former_state = _M_rehash_policy._M_state();
+
+	  if (_M_bucket_count != __ht._M_bucket_count)
+	    {
+	      __former_buckets = _M_buckets;
+	      _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
+	      _M_bucket_count = __ht._M_bucket_count;
+	    }
+	  else
+	    __builtin_memset(_M_buckets, 0,
+			     _M_bucket_count * sizeof(__bucket_type));
+
+	  __try
+	    {
+	      __hashtable_base::operator=(std::move(__ht));
+	      _M_element_count = __ht._M_element_count;
+	      _M_rehash_policy = __ht._M_rehash_policy;
+	      __detail::_MoveReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
+					      _Equal, _H1, _H2, _Hash,
+					      _RehashPolicy, _Traits>
+		__mroan(_M_begin(), *this);
+	      _M_before_begin()._M_nxt = nullptr;
+	      _M_assign(__ht, __mroan);
+	      __ht.clear();
+	    }
+	  __catch(...)
+	    {
+	      if (__former_buckets)
+		{
+		  _M_deallocate_buckets();
+		  _M_rehash_policy._M_reset(__former_state);
+		  _M_buckets = __former_buckets;
+		  _M_bucket_count = __former_bucket_count;
+		}
+	      __builtin_memset(_M_buckets, 0,
+			       _M_bucket_count * sizeof(__bucket_type));
+	      __throw_exception_again;
+	    }
+	}
+    }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _Hashtable(const _Hashtable& __ht)
     : __hashtable_base(__ht),
       __map_base(__ht),
       __rehash_base(__ht),
+      _M_buckets(),
       _M_bucket_count(__ht._M_bucket_count),
-      _M_bbegin(__ht._M_bbegin),
+      _M_bbegin(_Node_alloc_traits::_S_select_on_copy(
+		__ht._M_node_allocator())),
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {
-      _M_buckets = _M_allocate_buckets(_M_bucket_count);
-      __try
-	{
-	  if (!__ht._M_before_begin()._M_nxt)
-	    return;
-
-	  // First deal with the special first node pointed to by
-	  // _M_before_begin.
-	  const __node_type* __ht_n = __ht._M_begin();
-	  __node_type* __this_n = _M_allocate_node(__ht_n->_M_v);
-	  this->_M_copy_code(__this_n, __ht_n);
-	  _M_before_begin()._M_nxt = __this_n;
-	  _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin();
-
-	  // Then deal with other nodes.
-	  __node_base* __prev_n = __this_n;
-	  for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
-	    {
-	      __this_n = _M_allocate_node(__ht_n->_M_v);
-	      __prev_n->_M_nxt = __this_n;
-	      this->_M_copy_code(__this_n, __ht_n);
-	      size_type __bkt = _M_bucket_index(__this_n);
-	      if (!_M_buckets[__bkt])
-		_M_buckets[__bkt] = __prev_n;
-	      __prev_n = __this_n;
-	    }
-	}
-      __catch(...)
-	{
-	  clear();
-	  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
-	  __throw_exception_again;
-	}
+      _M_assign(__ht,
+		[this](const __node_type* __n)
+		{ return _M_allocate_node(__n->_M_v()); });
     }
 
   template<typename _Key, typename _Value,
@@ -927,7 +1201,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _Traits>
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _Hashtable(_Hashtable&& __ht)
+    _Hashtable(_Hashtable&& __ht) noexcept
     : __hashtable_base(__ht),
       __map_base(__ht),
       __rehash_base(__ht),
@@ -937,14 +1211,70 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {
-      // Update, if necessary, bucket pointing to before begin that hasn't moved.
+      // Update, if necessary, bucket pointing to before begin that hasn't
+      // moved.
       if (_M_begin())
 	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
-      __ht._M_rehash_policy = _RehashPolicy();
-      __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
-      __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
-      __ht._M_before_begin()._M_nxt = nullptr;
-      __ht._M_element_count = 0;
+      __ht._M_reset();
+    }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _Hashtable(const _Hashtable& __ht, const allocator_type& __a)
+    : __hashtable_base(__ht),
+      __map_base(__ht),
+      __rehash_base(__ht),
+      _M_buckets(),
+      _M_bucket_count(__ht._M_bucket_count),
+      _M_bbegin(_Node_alloc_type(__a)),
+      _M_element_count(__ht._M_element_count),
+      _M_rehash_policy(__ht._M_rehash_policy)
+    {
+      _M_assign(__ht,
+		[this](const __node_type* __n)
+		{ return _M_allocate_node(__n->_M_v()); });
+    }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _Hashtable(_Hashtable&& __ht, const allocator_type& __a)
+    : __hashtable_base(__ht),
+      __map_base(__ht),
+      __rehash_base(__ht),
+      _M_buckets(),
+      _M_bucket_count(__ht._M_bucket_count),
+      _M_bbegin(_Node_alloc_type(__a)),
+      _M_element_count(__ht._M_element_count),
+      _M_rehash_policy(__ht._M_rehash_policy)
+    {
+      if (__ht._M_node_allocator() == _M_node_allocator())
+	{
+	  _M_buckets = __ht._M_buckets;
+	  _M_before_begin()._M_nxt = __ht._M_before_begin()._M_nxt;
+	  // Update, if necessary, bucket pointing to before begin that hasn't
+	  // moved.
+	  if (_M_begin())
+	    _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
+	  __ht._M_reset();
+	}
+      else
+	{
+	  _M_assign(__ht,
+		    [this](__node_type* __n)
+		    {
+		      return _M_allocate_node(
+					std::move_if_noexcept(__n->_M_v()));
+		    });
+	  __ht.clear();
+	}
     }
 
   template<typename _Key, typename _Value,
@@ -956,7 +1286,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     ~_Hashtable() noexcept
     {
       clear();
-      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      if (_M_buckets)
+	_M_deallocate_buckets();
     }
 
   template<typename _Key, typename _Value,
@@ -967,25 +1298,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     swap(_Hashtable& __x)
+    noexcept(_Node_alloc_traits::_S_nothrow_swap())
     {
       // The only base class with member variables is hash_code_base.
       // We define _Hash_code_base::_M_swap because different
       // specializations have different members.
       this->_M_swap(__x);
 
-      // _GLIBCXX_RESOLVE_LIB_DEFECTS
-      // 431. Swapping containers with unequal allocators.
-      std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator(),
-							__x._M_node_allocator());
-
+      std::__alloc_on_swap(_M_node_allocator(), __x._M_node_allocator());
       std::swap(_M_rehash_policy, __x._M_rehash_policy);
       std::swap(_M_buckets, __x._M_buckets);
       std::swap(_M_bucket_count, __x._M_bucket_count);
       std::swap(_M_before_begin()._M_nxt, __x._M_before_begin()._M_nxt);
       std::swap(_M_element_count, __x._M_element_count);
 
-      // Fix buckets containing the _M_before_begin pointers that
-      // can't be swapped.
+      // Fix buckets containing the _M_before_begin pointers that can't be
+      // swapped.
       if (_M_begin())
 	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin();
       if (__x._M_begin())
@@ -1020,10 +1348,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     find(const key_type& __k)
     {
+      if (__builtin_expect(_M_bucket_count == 0, false))
+	return end();
+
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
-      return __p ? iterator(__p) : this->end();
+      return __p ? iterator(__p) : end();
     }
 
   template<typename _Key, typename _Value,
@@ -1037,10 +1368,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     find(const key_type& __k) const
     {
+      if (__builtin_expect(_M_bucket_count == 0, false))
+	return end();
+      
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
-      return __p ? const_iterator(__p) : this->end();
+      return __p ? const_iterator(__p) : end();
     }
 
   template<typename _Key, typename _Value,
@@ -1054,6 +1388,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     count(const key_type& __k) const
     {
+      if (__builtin_expect(_M_bucket_count == 0, false))
+	return 0;
+
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_bucket_begin(__n);
@@ -1092,6 +1429,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     equal_range(const key_type& __k)
     {
+      if (__builtin_expect(_M_bucket_count == 0, false))
+	return std::make_pair(end(), end());
+
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
@@ -1106,7 +1446,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return std::make_pair(iterator(__p), iterator(__p1));
 	}
       else
-	return std::make_pair(this->end(), this->end());
+	return std::make_pair(end(), end());
     }
 
   template<typename _Key, typename _Value,
@@ -1125,6 +1465,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     equal_range(const key_type& __k) const
     {
+      if (__builtin_expect(_M_bucket_count == 0, false))
+	return std::make_pair(end(), end());
+	
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __n = _M_bucket_index(__k, __code);
       __node_type* __p = _M_find_node(__n, __k, __code);
@@ -1139,7 +1482,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return std::make_pair(const_iterator(__p), const_iterator(__p1));
 	}
       else
-	return std::make_pair(this->end(), this->end());
+	return std::make_pair(end(), end());
     }
 
   // Find the node whose key compares equal to k in the bucket n.
@@ -1258,7 +1601,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       {
 	// First build the node to get access to the hash code
 	__node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...);
-	const key_type& __k = this->_M_extract()(__node->_M_v);
+	const key_type& __k = this->_M_extract()(__node->_M_v());
 	__hash_code __code;
 	__try
 	  {
@@ -1301,7 +1644,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__hash_code __code;
 	__try
 	  {
-	    __code = this->_M_hash_code(this->_M_extract()(__node->_M_v));
+	    __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
 	  }
 	__catch(...)
 	  {
@@ -1333,7 +1676,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  if (__do_rehash.first)
 	    {
 	      _M_rehash(__do_rehash.second, __saved_state);
-	      __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v), __code);
+	      __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
 	    }
 
 	  this->_M_store_code(__node, __code);
@@ -1373,7 +1716,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _M_rehash(__do_rehash.second, __saved_state);
 
 	  this->_M_store_code(__node, __code);
-	  const key_type& __k = this->_M_extract()(__node->_M_v);
+	  const key_type& __k = this->_M_extract()(__node->_M_v());
 	  size_type __bkt = _M_bucket_index(__k, __code);
 
 	  // Find the node before an equivalent one.
@@ -1722,7 +2065,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  __p = __next;
 	}
-      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+
+      if (__builtin_expect(_M_bucket_count != 0, true))
+	_M_deallocate_buckets();
       _M_bucket_count = __n;
       _M_buckets = __new_buckets;
     }
@@ -1812,7 +2157,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    __new_buckets[__next_bkt] = __prev_p;
 	}
 
-      _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+      if (__builtin_expect(_M_bucket_count != 0, true))
+	_M_deallocate_buckets();
       _M_bucket_count = __n;
       _M_buckets = __new_buckets;
     }
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f75f49fcd6d..5cabb53bb6d 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -156,6 +156,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   };
 
   /**
+   *  struct _Hash_node_value_base
+   *
+   *  Node type with the value to store.
+   */
+  template<typename _Value>
+    struct _Hash_node_value_base : _Hash_node_base
+    {
+      __gnu_cxx::__aligned_buffer<_Value> _M_storage;
+
+      _Value*
+      _M_valptr() noexcept
+      { return _M_storage._M_ptr(); }
+
+      const _Value*
+      _M_valptr() const noexcept
+      { return _M_storage._M_ptr(); }
+
+      _Value&
+      _M_v() noexcept
+      { return *_M_valptr(); }
+
+      const _Value&
+      _M_v() const noexcept
+      { return *_M_valptr(); }
+    };
+
+  /**
    *  Primary template struct _Hash_node.
    */
   template<typename _Value, bool _Cache_hash_code>
@@ -164,38 +191,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /**
    *  Specialization for nodes with caches, struct _Hash_node.
    *
-   *  Base class is __detail::_Hash_node_base.
+   *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, true> : _Hash_node_base
+    struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
     {
-      _Value       _M_v;
       std::size_t  _M_hash_code;
 
-      template<typename... _Args>
-	_Hash_node(_Args&&... __args)
-	: _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
-
       _Hash_node*
-      _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
+      _M_next() const { return static_cast<_Hash_node*>(this->_M_nxt); }
     };
 
   /**
    *  Specialization for nodes without caches, struct _Hash_node.
    *
-   *  Base class is __detail::_Hash_node_base.
+   *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, false> : _Hash_node_base
+    struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
     {
-      _Value       _M_v;
-
-      template<typename... _Args>
-	_Hash_node(_Args&&... __args)
-	: _M_v(std::forward<_Args>(__args)...) { }
-
       _Hash_node*
-      _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
+      _M_next() const { return static_cast<_Hash_node*>(this->_M_nxt); }
     };
 
   /// Base class for node iterators.
@@ -255,11 +271,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       reference
       operator*() const
-      { return this->_M_cur->_M_v; }
+      { return this->_M_cur->_M_v(); }
 
       pointer
       operator->() const
-      { return std::__addressof(this->_M_cur->_M_v); }
+      { return this->_M_cur->_M_valptr(); }
 
       _Node_iterator&
       operator++()
@@ -307,11 +323,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       reference
       operator*() const
-      { return this->_M_cur->_M_v; }
+      { return this->_M_cur->_M_v(); }
 
       pointer
       operator->() const
-      { return std::__addressof(this->_M_cur->_M_v); }
+      { return this->_M_cur->_M_valptr(); }
 
       _Node_const_iterator&
       operator++()
@@ -341,7 +357,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     typedef std::size_t result_type;
 
     result_type
-    operator()(first_argument_type __num, second_argument_type __den) const
+    operator()(first_argument_type __num,
+	       second_argument_type __den) const noexcept
     { return __num % __den; }
   };
 
@@ -387,6 +404,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     { return _M_next_resize; }
 
     void
+    _M_reset() noexcept
+    { _M_next_resize = 0; }
+
+    void
     _M_reset(_State __state)
     { _M_next_resize = __state; }
 
@@ -496,7 +517,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return __h->_M_insert_unique_node(__n, __code, __p)->second;
 	}
 
-      return (__p->_M_v).second;
+      return __p->_M_v().second;
     }
 
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -522,7 +543,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return __h->_M_insert_unique_node(__n, __code, __p)->second;
 	}
 
-      return (__p->_M_v).second;
+      return __p->_M_v().second;
     }
 
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -542,7 +563,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (!__p)
 	__throw_out_of_range(__N("_Map_base::at"));
-      return (__p->_M_v).second;
+      return __p->_M_v().second;
     }
 
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -562,7 +583,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (!__p)
 	__throw_out_of_range(__N("_Map_base::at"));
-      return (__p->_M_v).second;
+      return __p->_M_v().second;
     }
 
   /**
@@ -939,7 +960,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       std::size_t
       _M_bucket_index(const __node_type* __p, std::size_t __n) const
-      { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
+	noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(), (std::size_t)0)) )
+      { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
 
       void
       _M_store_code(__node_type*, __hash_code) const
@@ -1023,9 +1045,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return _M_h2()(__c, __n); }
 
       std::size_t
-      _M_bucket_index(const __node_type* __p,
-		      std::size_t __n) const
-      { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
+      _M_bucket_index(const __node_type* __p, std::size_t __n) const
+	noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
+		  && noexcept(declval<const _H2&>()((__hash_code)0, (std::size_t)0)) )
+      { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
 
       void
       _M_store_code(__node_type*, __hash_code) const
@@ -1109,6 +1132,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       std::size_t
       _M_bucket_index(const __node_type* __p, std::size_t __n) const
+	noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
+						 (std::size_t)0)) )
       { return _M_h2()(__p->_M_hash_code, __n); }
 
       void
@@ -1163,7 +1188,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     static bool
     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
 	      const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
-    { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); }
+    { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
   };
 
   /// Specialization.
@@ -1174,7 +1199,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     static bool
     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
 	      const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
-    { return __eq(__k, __extract(__n->_M_v)); }
+    { return __eq(__k, __extract(__n->_M_v())); }
   };
 
 
@@ -1305,11 +1330,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       reference
       operator*() const
-      { return this->_M_cur->_M_v; }
+      { return this->_M_cur->_M_v(); }
 
       pointer
       operator->() const
-      { return std::__addressof(this->_M_cur->_M_v); }
+      { return this->_M_cur->_M_valptr(); }
 
       _Local_iterator&
       operator++()
@@ -1364,11 +1389,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       reference
       operator*() const
-      { return this->_M_cur->_M_v; }
+      { return this->_M_cur->_M_v(); }
 
       pointer
       operator->() const
-      { return std::__addressof(this->_M_cur->_M_v); }
+      { return this->_M_cur->_M_valptr(); }
 
       _Local_const_iterator&
       operator++()
@@ -1662,6 +1687,120 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{ }
     };
 
+  /*
+   * Following are functors recyclicing a pool of nodes and using allocation
+   * once the pool is empty.
+   */
+  /// Version using copy semantic through the copy constructor.
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _RehashPolicy, typename _Traits>
+    struct _ReuseOrAllocNode
+    {
+    private:
+      using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+				     _Equal, _H1, _H2, _Hash,
+				     _RehashPolicy, _Traits>;
+      using __val_alloc_type = typename __hashtable::_Value_alloc_type;
+      using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
+      using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
+      using __node_type = typename __hashtable::__node_type;
+
+    public:
+      _ReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+	: _M_nodes(__nodes), _M_h(__h) { }
+      _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
+
+      ~_ReuseOrAllocNode()
+      { _M_h._M_deallocate_nodes(_M_nodes); }
+
+      __node_type*
+      operator()(const __node_type* __n) const
+      {
+	if (_M_nodes)
+	  {
+	    __node_type* __node = _M_nodes;
+	    _M_nodes = _M_nodes->_M_next();
+	    __node->_M_nxt = nullptr;
+	    __val_alloc_type __a(_M_h._M_node_allocator());
+	    __val_alloc_traits::destroy(__a, __node->_M_valptr());
+	    __try
+	      {
+		__val_alloc_traits::construct(__a, __node->_M_valptr(),
+					      __n->_M_v());
+	      }
+	    __catch(...)
+	      {
+		__node->~__node_type();
+		__node_alloc_traits::deallocate(_M_h._M_node_allocator(),
+						__node, 1);
+		__throw_exception_again;
+	      }
+	    return __node;
+	  }
+	return _M_h._M_allocate_node(__n->_M_v());
+      }
+
+      mutable __node_type* _M_nodes;
+      __hashtable& _M_h;
+    };
+
+  /// Version using move semantic through the move constructor.
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _RehashPolicy, typename _Traits>
+    struct _MoveReuseOrAllocNode
+    {
+    private:
+      using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+				     _Equal, _H1, _H2, _Hash,
+				     _RehashPolicy, _Traits>;
+      using __val_alloc_type = typename __hashtable::_Value_alloc_type;
+      using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
+      using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
+      using __node_type = typename __hashtable::__node_type;
+
+    public:
+      _MoveReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+	: _M_nodes(__nodes), _M_h(__h) { }
+      _MoveReuseOrAllocNode(const _MoveReuseOrAllocNode&) = delete;
+
+      ~_MoveReuseOrAllocNode()
+      { _M_h._M_deallocate_nodes(_M_nodes); }
+
+      __node_type*
+      operator()(__node_type* __n) const
+      {
+	if (_M_nodes)
+	  {
+	    __node_type* __node = _M_nodes;
+	    _M_nodes = _M_nodes->_M_next();
+	    __node->_M_nxt = nullptr;
+	    __val_alloc_type  __a(_M_h._M_node_allocator());
+	    __val_alloc_traits::destroy(__a, __node->_M_valptr());
+	    __try
+	      {
+		__val_alloc_traits::construct(__a, __node->_M_valptr(),
+					std::move_if_noexcept(__n->_M_v()));
+	      }
+	    __catch(...)
+	      {
+		__node->~__node_type();
+		__node_alloc_traits::deallocate(_M_h._M_node_allocator(),
+						__node, 1);
+		__throw_exception_again;
+	      }
+	    return __node;
+	  }
+	return _M_h._M_allocate_node(std::move_if_noexcept(__n->_M_v()));
+      }
+
+      mutable __node_type* _M_nodes;
+      __hashtable& _M_h;
+    };
+
  //@} hashtable-detail
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace __detail
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index be213e04a79..7fd84e35cc0 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -113,10 +113,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       //@{
       ///  Iterator-related typedefs.
-      typedef typename allocator_type::pointer		pointer;
-      typedef typename allocator_type::const_pointer	const_pointer;
-      typedef typename allocator_type::reference	reference;
-      typedef typename allocator_type::const_reference	const_reference;
+      typedef typename _Hashtable::pointer		pointer;
+      typedef typename _Hashtable::const_pointer	const_pointer;
+      typedef typename _Hashtable::reference		reference;
+      typedef typename _Hashtable::const_reference	const_reference;
       typedef typename _Hashtable::iterator		iterator;
       typedef typename _Hashtable::const_iterator	const_iterator;
       typedef typename _Hashtable::local_iterator	local_iterator;
@@ -171,6 +171,35 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       unordered_map(unordered_map&&) = default;
 
       /**
+       *  @brief Creates an %unordered_map with no elements.
+       *  @param __a An allocator object.
+       */
+      explicit
+      unordered_map(const allocator_type& __a)
+	: _M_h(__a)
+      { }
+
+      /*
+       *  @brief Copy constructor with allocator argument.
+       * @param  __uset  Input %unordered_map to copy.
+       * @param  __a  An allocator object.
+       */
+      unordered_map(const unordered_map& __umap,
+		    const allocator_type& __a)
+	: _M_h(__umap._M_h, __a)
+      { }
+
+      /*
+       *  @brief  Move constructor with allocator argument.
+       *  @param  __uset Input %unordered_map to move.
+       *  @param  __a    An allocator object.
+       */
+      unordered_map(unordered_map&& __umap,
+		    const allocator_type& __a)
+	: _M_h(std::move(__umap._M_h), __a)
+      { }
+
+      /**
        *  @brief  Builds an %unordered_map from an initializer_list.
        *  @param  __l  An initializer_list.
        *  @param __n  Minimal initial number of buckets.
@@ -508,6 +537,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       swap(unordered_map& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
@@ -794,10 +824,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       //@{
       ///  Iterator-related typedefs.
-      typedef typename allocator_type::pointer		pointer;
-      typedef typename allocator_type::const_pointer	const_pointer;
-      typedef typename allocator_type::reference	reference;
-      typedef typename allocator_type::const_reference	const_reference;
+      typedef typename _Hashtable::pointer		pointer;
+      typedef typename _Hashtable::const_pointer	const_pointer;
+      typedef typename _Hashtable::reference		reference;
+      typedef typename _Hashtable::const_reference	const_reference;
       typedef typename _Hashtable::iterator		iterator;
       typedef typename _Hashtable::const_iterator	const_iterator;
       typedef typename _Hashtable::local_iterator	local_iterator;
@@ -852,6 +882,35 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       unordered_multimap(unordered_multimap&&) = default;
 
       /**
+       *  @brief Creates an %unordered_multimap with no elements.
+       *  @param __a An allocator object.
+       */
+      explicit
+      unordered_multimap(const allocator_type& __a)
+	: _M_h(__a)
+      { }
+
+      /*
+       *  @brief Copy constructor with allocator argument.
+       * @param  __uset  Input %unordered_multimap to copy.
+       * @param  __a  An allocator object.
+       */
+      unordered_multimap(const unordered_multimap& __ummap,
+			 const allocator_type& __a)
+	: _M_h(__ummap._M_h, __a)
+      { }
+
+      /*
+       *  @brief  Move constructor with allocator argument.
+       *  @param  __uset Input %unordered_multimap to move.
+       *  @param  __a    An allocator object.
+       */
+      unordered_multimap(unordered_multimap&& __ummap,
+			 const allocator_type& __a)
+	: _M_h(std::move(__ummap._M_h), __a)
+      { }
+
+      /**
        *  @brief  Builds an %unordered_multimap from an initializer_list.
        *  @param  __l  An initializer_list.
        *  @param __n  Minimal initial number of buckets.
@@ -1173,6 +1232,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       swap(unordered_multimap& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index 50c233d0595..89deb496f11 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -108,10 +108,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       //@{
       ///  Iterator-related typedefs.
-      typedef typename allocator_type::pointer		pointer;
-      typedef typename allocator_type::const_pointer	const_pointer;
-      typedef typename allocator_type::reference	reference;
-      typedef typename allocator_type::const_reference	const_reference;
+      typedef typename _Hashtable::pointer		pointer;
+      typedef typename _Hashtable::const_pointer	const_pointer;
+      typedef typename _Hashtable::reference		reference;
+      typedef typename _Hashtable::const_reference	const_reference;
       typedef typename _Hashtable::iterator		iterator;
       typedef typename _Hashtable::const_iterator	const_iterator;
       typedef typename _Hashtable::local_iterator	local_iterator;
@@ -165,6 +165,35 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       unordered_set(unordered_set&&) = default;
 
       /**
+       *  @brief Creates an %unordered_set with no elements.
+       *  @param __a An allocator object.
+       */
+      explicit
+      unordered_set(const allocator_type& __a)
+	: _M_h(__a)
+      { }
+
+      /*
+       *  @brief Copy constructor with allocator argument.
+       * @param  __uset  Input %unordered_set to copy.
+       * @param  __a  An allocator object.
+       */
+      unordered_set(const unordered_set& __uset,
+		    const allocator_type& __a)
+	: _M_h(__uset._M_h, __a)
+      { }
+
+      /*
+       *  @brief  Move constructor with allocator argument.
+       *  @param  __uset Input %unordered_set to move.
+       *  @param  __a    An allocator object.
+       */
+      unordered_set(unordered_set&& __uset,
+		    const allocator_type& __a)
+	: _M_h(std::move(__uset._M_h), __a)
+      { }
+
+      /**
        *  @brief  Builds an %unordered_set from an initializer_list.
        *  @param  __l  An initializer_list.
        *  @param __n  Minimal initial number of buckets.
@@ -482,6 +511,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       swap(unordered_set& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
@@ -713,10 +743,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       //@{
       ///  Iterator-related typedefs.
-      typedef typename allocator_type::pointer		pointer;
-      typedef typename allocator_type::const_pointer	const_pointer;
-      typedef typename allocator_type::reference	reference;
-      typedef typename allocator_type::const_reference	const_reference;
+      typedef typename _Hashtable::pointer		pointer;
+      typedef typename _Hashtable::const_pointer	const_pointer;
+      typedef typename _Hashtable::reference		reference;
+      typedef typename _Hashtable::const_reference	const_reference;
       typedef typename _Hashtable::iterator		iterator;
       typedef typename _Hashtable::const_iterator	const_iterator;
       typedef typename _Hashtable::local_iterator	local_iterator;
@@ -794,7 +824,36 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Move assignment operator.
       unordered_multiset&
-      operator=(unordered_multiset&& __x) = default;
+      operator=(unordered_multiset&&) = default;
+
+      /**
+       *  @brief Creates an %unordered_multiset with no elements.
+       *  @param __a An allocator object.
+       */
+      explicit
+      unordered_multiset(const allocator_type& __a)
+	: _M_h(__a)
+      { }
+
+      /*
+       *  @brief Copy constructor with allocator argument.
+       * @param  __uset  Input %unordered_multiset to copy.
+       * @param  __a  An allocator object.
+       */
+      unordered_multiset(const unordered_multiset& __umset,
+			 const allocator_type& __a)
+	: _M_h(__umset._M_h, __a)
+      { }
+
+      /*
+       *  @brief  Move constructor with allocator argument.
+       *  @param  __umset  Input %unordered_multiset to move.
+       *  @param  __a  An allocator object.
+       */
+      unordered_multiset(unordered_multiset&& __umset,
+			 const allocator_type& __a)
+	: _M_h(std::move(__umset._M_h), __a)
+      { }
 
       /**
        *  @brief  %Unordered_multiset list assignment operator.
@@ -1070,6 +1129,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       void
       swap(unordered_multiset& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index a826b0190d5..d62deac3917 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -60,6 +60,9 @@ namespace __debug
       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
       typedef typename _Base::local_iterator _Base_local_iterator;
 
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
+
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -96,12 +99,27 @@ namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_map(const unordered_map& __x) = default;
+      unordered_map(const unordered_map&) = default;
 
       unordered_map(const _Base& __x)
       : _Base(__x) { }
 
-      unordered_map(unordered_map&& __x) = default;
+      unordered_map(unordered_map&&) = default;
+
+      explicit
+      unordered_map(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_map(const unordered_map& __umap,
+		    const allocator_type& __a)
+	: _Base(__umap._M_base(), __a)
+      { }
+
+      unordered_map(unordered_map&& __umap,
+		    const allocator_type& __a)
+	: _Base(std::move(__umap._M_base()), __a)
+      { }
 
       unordered_map(initializer_list<value_type> __l,
 		    size_type __n = 0,
@@ -115,33 +133,41 @@ namespace __debug
       unordered_map&
       operator=(const unordered_map& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x._M_base();
 	this->_M_invalidate_all();
 	return *this;
       }
 
       unordered_map&
       operator=(unordered_map&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-   	// NB: DR 1204.
-	// NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());	
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       unordered_map&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 
       void
       swap(unordered_map& __x)
+      noexcept(_Alloc_traits::_S_nothrow_swap())
       {
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
 	_Base::swap(__x);
 	_Safe_base::_M_swap(__x);
       }
@@ -490,6 +516,9 @@ namespace __debug
       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
       typedef typename _Base::local_iterator _Base_local_iterator;
 
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
+
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -526,12 +555,27 @@ namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_multimap(const unordered_multimap& __x) = default;
+      unordered_multimap(const unordered_multimap&) = default;
 
       unordered_multimap(const _Base& __x) 
       : _Base(__x) { }
 
-      unordered_multimap(unordered_multimap&& __x) = default;
+      unordered_multimap(unordered_multimap&&) = default;
+
+      explicit
+      unordered_multimap(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_multimap(const unordered_multimap& __umap,
+			 const allocator_type& __a)
+	: _Base(__umap._M_base(), __a)
+      { }
+
+      unordered_multimap(unordered_multimap&& __umap,
+			 const allocator_type& __a)
+	: _Base(std::move(__umap._M_base()), __a)
+      { }
 
       unordered_multimap(initializer_list<value_type> __l,
 			 size_type __n = 0,
@@ -545,33 +589,41 @@ namespace __debug
       unordered_multimap&
       operator=(const unordered_multimap& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x._M_base();
 	this->_M_invalidate_all();
 	return *this;
       }
 
       unordered_multimap&
       operator=(unordered_multimap&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-	// NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       unordered_multimap&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 
       void
       swap(unordered_multimap& __x)
+      noexcept(_Alloc_traits::_S_nothrow_swap())
       {
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
 	_Base::swap(__x);
 	_Safe_base::_M_swap(__x);
       }
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 8e88addd87f..66898e243b1 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -60,6 +60,8 @@ namespace __debug
       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
       typedef typename _Base::local_iterator _Base_local_iterator;
 
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -96,12 +98,27 @@ namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_set(const unordered_set& __x) = default;
+      unordered_set(const unordered_set&) = default;
 
-      unordered_set(const _Base& __x) 
-      : _Base(__x) { }
+      unordered_set(const _Base& __x)
+	: _Base(__x) { }
+
+      unordered_set(unordered_set&&) = default;
+
+      explicit
+      unordered_set(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_set(const unordered_set& __uset,
+		    const allocator_type& __a)
+	: _Base(__uset._M_base(), __a)
+      { }
 
-      unordered_set(unordered_set&& __x) = default;
+      unordered_set(unordered_set&& __uset,
+		    const allocator_type& __a)
+	: _Base(std::move(__uset._M_base()), __a)
+      { }
 
       unordered_set(initializer_list<value_type> __l,
 		    size_type __n = 0,
@@ -115,33 +132,41 @@ namespace __debug
       unordered_set&
       operator=(const unordered_set& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x._M_base();
 	this->_M_invalidate_all();
 	return *this;
       }
 
       unordered_set&
       operator=(unordered_set&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-	// NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       unordered_set&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 
       void
       swap(unordered_set& __x)
+      noexcept(_Alloc_traits::_S_nothrow_swap())
       {
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
 	_Base::swap(__x);
 	_Safe_base::_M_swap(__x);
       }
@@ -485,6 +510,9 @@ namespace __debug
       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
       typedef typename _Base::local_iterator _Base_local_iterator;
 
+      typedef __gnu_cxx::__alloc_traits<typename
+					_Base::allocator_type> _Alloc_traits;
+
     public:
       typedef typename _Base::size_type       size_type;
       typedef typename _Base::hasher          hasher;
@@ -521,12 +549,27 @@ namespace __debug
 		__gnu_debug::__base(__last), __n,
 		__hf, __eql, __a) { }
 
-      unordered_multiset(const unordered_multiset& __x) = default;
+      unordered_multiset(const unordered_multiset&) = default;
 
       unordered_multiset(const _Base& __x) 
       : _Base(__x) { }
 
-      unordered_multiset(unordered_multiset&& __x) = default;
+      unordered_multiset(unordered_multiset&&) = default;
+
+      explicit
+      unordered_multiset(const allocator_type& __a)
+	: _Base(__a)
+      { }
+
+      unordered_multiset(const unordered_multiset& __uset,
+			 const allocator_type& __a)
+	: _Base(__uset._M_base(), __a)
+      { }
+      
+      unordered_multiset(unordered_multiset&& __uset,
+			 const allocator_type& __a)
+	: _Base(std::move(__uset._M_base()), __a)
+      { }
 
       unordered_multiset(initializer_list<value_type> __l,
 			 size_type __n = 0,
@@ -540,33 +583,41 @@ namespace __debug
       unordered_multiset&
       operator=(const unordered_multiset& __x)
       {
-	*static_cast<_Base*>(this) = __x;
+	_M_base() = __x._M_base();
 	this->_M_invalidate_all();
 	return *this;
       }
 
       unordered_multiset&
       operator=(unordered_multiset&& __x)
+      noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	// NB: DR 1204.
-        // NB: DR 675.
 	__glibcxx_check_self_move_assign(__x);
-	clear();
-	swap(__x);
+	bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
+	    || __x.get_allocator() == this->get_allocator();
+	_M_base() = std::move(__x._M_base());
+	if (xfer_memory)
+	  this->_M_swap(__x);
+	else
+	  this->_M_invalidate_all();
+	__x._M_invalidate_all();
 	return *this;
       }
 
       unordered_multiset&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l);
+	_M_base() = __l;
+	this->_M_invalidate_all();
 	return *this;
       }
 
       void
       swap(unordered_multiset& __x)
+      noexcept(_Alloc_traits::_S_nothrow_swap())
       {
+	if (!_Alloc_traits::_S_propagate_on_swap())
+	  __glibcxx_check_equal_allocs(__x);
 	_Base::swap(__x);
 	_Safe_base::_M_swap(__x);
       }
diff --git a/libstdc++-v3/include/ext/throw_allocator.h b/libstdc++-v3/include/ext/throw_allocator.h
index 7e610ed17fe..31f22dc386a 100644
--- a/libstdc++-v3/include/ext/throw_allocator.h
+++ b/libstdc++-v3/include/ext/throw_allocator.h
@@ -90,7 +90,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     annotate_base()
     {
       label();
-      map();
+      map_alloc();
     }
 
     static void
@@ -111,8 +111,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  std::__throw_logic_error(error.c_str());
 	}
 
-      const_iterator found = map().find(p);
-      if (found != map().end())
+      const_iterator found = map_alloc().find(p);
+      if (found != map_alloc().end())
 	{
 	  std::string error("annotate_base::insert double insert!\n");
 	  log_to_string(error, make_entry(p, size));
@@ -120,22 +120,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  std::__throw_logic_error(error.c_str());
 	}
 
-      map().insert(make_entry(p, size));
+      map_alloc().insert(make_entry(p, size));
     }
 
     void
     erase(void* p, size_t size)
     {
       check_allocated(p, size);
-      map().erase(p);
+      map_alloc().erase(p);
     }
 
+#if __cplusplus >= 201103L
+    void
+    insert_construct(void* p)
+    {
+      if (!p)
+	{
+	  std::string error("annotate_base::insert_construct null!\n");
+	  std::__throw_logic_error(error.c_str());
+	}
+
+      auto found = map_construct().find(p);
+      if (found != map_construct().end())
+	{
+	  std::string error("annotate_base::insert_construct double insert!\n");
+	  log_to_string(error, std::make_pair(p, get_label()));
+	  log_to_string(error, *found);
+	  std::__throw_logic_error(error.c_str());
+	}
+
+      map_construct().insert(std::make_pair(p, get_label()));
+    }
+
+    void
+    erase_construct(void* p)
+    {
+      check_constructed(p);
+      map_construct().erase(p);
+    }
+#endif
+
     // See if a particular address and allocation size has been saved.
     inline void
     check_allocated(void* p, size_t size)
     {
-      const_iterator found = map().find(p);
-      if (found == map().end())
+      const_iterator found = map_alloc().find(p);
+      if (found == map_alloc().end())
 	{
 	  std::string error("annotate_base::check_allocated by value "
 			    "null erase!\n");
@@ -155,32 +185,121 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
     // See if a given label has been allocated.
     inline void
-    check_allocated(size_t label)
+    check(size_t label)
+    {
+      std::string found;
+      {
+	const_iterator beg = map_alloc().begin();
+	const_iterator end = map_alloc().end();
+	while (beg != end)
+	  {
+	    if (beg->second.first == label)
+	      log_to_string(found, *beg);
+	    ++beg;
+	  }
+      }
+
+#if __cplusplus >= 201103L
+      {
+	auto beg = map_construct().begin();
+	auto end = map_construct().end();
+	while (beg != end)
+	  {
+	    if (beg->second == label)
+	      log_to_string(found, *beg);
+	    ++beg;
+	  }
+      }
+#endif
+
+      if (!found.empty())
+	{
+	  std::string error("annotate_base::check by label\n");
+	  error += found;
+	  std::__throw_logic_error(error.c_str());
+	}
+    }
+
+    // See if there is anything left allocated or constructed.
+    inline static void
+    check()
+    {
+      std::string found;
+      {
+	const_iterator beg = map_alloc().begin();
+	const_iterator end = map_alloc().end();
+	while (beg != end)
+	  {
+	    log_to_string(found, *beg);
+	    ++beg;
+	  }
+      }
+
+#if __cplusplus >= 201103L
+      {
+	auto beg = map_construct().begin();
+	auto end = map_construct().end();
+	while (beg != end)
+	  {
+	    log_to_string(found, *beg);
+	    ++beg;
+	  }
+      }
+#endif
+
+      if (!found.empty())
+	{
+	  std::string error("annotate_base::check \n");
+	  error += found;
+	  std::__throw_logic_error(error.c_str());
+	}
+    }
+
+#if __cplusplus >= 201103L
+    inline void
+    check_constructed(void* p)
+    {
+      auto found = map_construct().find(p);
+      if (found == map_construct().end())
+	{
+	  std::string error("annotate_base::check_constructed not "
+			    "constructed!\n");
+	  log_to_string(error, std::make_pair(p, get_label()));
+	  std::__throw_logic_error(error.c_str());
+	}
+    }
+
+    inline void
+    check_constructed(size_t label)
     {
-      const_iterator beg = map().begin();
-      const_iterator end = map().end();
+      auto beg = map_construct().begin();
+      auto end = map_construct().end();
       std::string found;
       while (beg != end)
 	{
-	  if (beg->second.first == label)
+	  if (beg->second == label)
 	    log_to_string(found, *beg);
 	  ++beg;
 	}
 
       if (!found.empty())
 	{
-	  std::string error("annotate_base::check_allocated by label\n");
+	  std::string error("annotate_base::check_constructed by label\n");
 	  error += found;
 	  std::__throw_logic_error(error.c_str());
 	}
     }
+#endif
 
   private:
-    typedef std::pair<size_t, size_t> 		data_type;
-    typedef std::map<void*, data_type> 		map_type;
-    typedef map_type::value_type 		entry_type;
-    typedef map_type::const_iterator 		const_iterator;
-    typedef map_type::const_reference 		const_reference;
+    typedef std::pair<size_t, size_t>		data_type;
+    typedef std::map<void*, data_type> 		map_alloc_type;
+    typedef map_alloc_type::value_type 		entry_type;
+    typedef map_alloc_type::const_iterator 		const_iterator;
+    typedef map_alloc_type::const_reference 		const_reference;
+#if __cplusplus >= 201103L
+    typedef std::map<void*, size_t>		map_construct_type;
+#endif
 
     friend std::ostream&
     operator<<(std::ostream&, const annotate_base&);
@@ -189,8 +308,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     make_entry(void* p, size_t size)
     { return std::make_pair(p, data_type(get_label(), size)); }
 
-    void
-    log_to_string(std::string& s, const_reference ref) const
+    static void
+    log_to_string(std::string& s, const_reference ref)
     {
       char buf[40];
       const char tab('\t');
@@ -210,6 +329,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       s += '\n';
     }
 
+#if __cplusplus >= 201103L
+    static void
+    log_to_string(std::string& s, const std::pair<const void*, size_t>& ref)
+    {
+      char buf[40];
+      const char tab('\t');
+      s += "label: ";
+      unsigned long l = static_cast<unsigned long>(ref.second);
+      __builtin_sprintf(buf, "%lu", l);
+      s += buf;
+      s += tab;
+      s += "address: ";
+      __builtin_sprintf(buf, "%p", ref.first);
+      s += buf;
+      s += '\n';
+    }
+#endif
+
     static size_t&
     label()
     {
@@ -217,12 +354,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return _S_label;
     }
 
-    static map_type&
-    map()
+    static map_alloc_type&
+    map_alloc()
     {
-      static map_type _S_map;
+      static map_alloc_type _S_map;
       return _S_map;
     }
+
+#if __cplusplus >= 201103L
+    static map_construct_type&
+    map_construct()
+    {
+      static map_construct_type _S_map;
+      return _S_map;
+    }
+#endif
   };
 
   inline std::ostream&
@@ -230,10 +376,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   {
     std::string error;
     typedef annotate_base base_type;
-    base_type::const_iterator beg = __b.map().begin();
-    base_type::const_iterator end = __b.map().end();
-    for (; beg != end; ++beg)
-      __b.log_to_string(error, *beg);
+    {
+      base_type::const_iterator beg = __b.map_alloc().begin();
+      base_type::const_iterator end = __b.map_alloc().end();
+      for (; beg != end; ++beg)
+	__b.log_to_string(error, *beg);
+    }
+#if __cplusplus >= 201103L
+    {
+      auto beg = __b.map_construct().begin();
+      auto end = __b.map_construct().end();
+      for (; beg != end; ++beg)
+	__b.log_to_string(error, *beg);      
+    }
+#endif
     return os << error;
   }
 
@@ -685,12 +841,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Up, typename... _Args>
         void
         construct(_Up* __p, _Args&&... __args)
-	{ return _M_allocator.construct(__p, std::forward<_Args>(__args)...); }
+	{
+	  _M_allocator.construct(__p, std::forward<_Args>(__args)...);
+	  insert_construct(__p);
+	}
 
       template<typename _Up>
         void 
         destroy(_Up* __p)
-        { _M_allocator.destroy(__p); }
+        {
+	  erase_construct(__p);
+	  _M_allocator.destroy(__p);
+	}
 #else
       void
       construct(pointer __p, const value_type& val)
@@ -716,8 +878,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
 
       void
-      check_allocated(size_type __n)
-      { annotate_base::check_allocated(__n); }
+      check(size_type __n)
+      { annotate_base::check(__n); }
   };
 
   template<typename _Tp, typename _Cond>
@@ -791,13 +953,14 @@ namespace std _GLIBCXX_VISIBILITY(default)
       size_t
       operator()(const __gnu_cxx::throw_value_limit& __val) const
       {
+	__gnu_cxx::throw_value_limit::throw_conditionally();
 	std::hash<std::size_t> __h;
 	size_t __result = __h(__val._M_i);
 	return __result;
       }
     };
 
-  /// Explicit specialization of std::hash for __gnu_cxx::throw_value_limit.
+  /// Explicit specialization of std::hash for __gnu_cxx::throw_value_random.
   template<>
     struct hash<__gnu_cxx::throw_value_random>
     : public std::unary_function<__gnu_cxx::throw_value_random, size_t>
@@ -805,6 +968,7 @@ namespace std _GLIBCXX_VISIBILITY(default)
       size_t
       operator()(const __gnu_cxx::throw_value_random& __val) const
       {
+	__gnu_cxx::throw_value_random::throw_conditionally();
 	std::hash<std::size_t> __h;
 	size_t __result = __h(__val._M_i);
 	return __result;
diff --git a/libstdc++-v3/include/std/unordered_map b/libstdc++-v3/include/std/unordered_map
index 7c10173f9b1..ed5bf83431c 100644
--- a/libstdc++-v3/include/std/unordered_map
+++ b/libstdc++-v3/include/std/unordered_map
@@ -39,9 +39,9 @@
 #include <type_traits>
 #include <initializer_list>
 #include <tuple>
-#include <bits/stl_algobase.h>
 #include <bits/allocator.h>
-#include <bits/alloc_traits.h>
+#include <ext/alloc_traits.h>
+#include <ext/aligned_buffer.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/functional_hash.h>
 #include <bits/hashtable.h>
diff --git a/libstdc++-v3/include/std/unordered_set b/libstdc++-v3/include/std/unordered_set
index cfe91ad3d91..12f39917f57 100644
--- a/libstdc++-v3/include/std/unordered_set
+++ b/libstdc++-v3/include/std/unordered_set
@@ -39,9 +39,9 @@
 #include <type_traits>
 #include <initializer_list>
 #include <tuple>
-#include <bits/stl_algobase.h>
 #include <bits/allocator.h>
-#include <bits/alloc_traits.h>
+#include <ext/alloc_traits.h>
+#include <ext/aligned_buffer.h>
 #include <bits/stl_function.h> // equal_to, _Identity, _Select1st
 #include <bits/functional_hash.h>
 #include <bits/hashtable.h>