This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Add std::unordered_* C++11 allocator support


Hi

    Here is another proposal with:
- No attempt to remove const key
- No attempt to use assignment operator
- noexcept move constructor; I slightly modify a static assertion so that it checks that _M_bucket_index is noexcept qualified which depends on the noexcept qualification of the functors involved in bucket computation

2013-04-21  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.
    * 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.

Tested under Linux x86_64.

Ok to commit ?

François


On 04/08/2013 10:24 AM, Jonathan Wakely wrote:
On 6 April 2013 19:53, Jonathan Wakely wrote:
I'm not very comfortable with the "mutable value type" part which
accesses the stored value through a pointer to a different type. This
violates strict aliasing rules and would also give the wrong result if
users provide an explicit specialization of std::pair<int, Foo> which
stores pair::second before pair::first, then tries to store that type
in an unordered_map.  When a pair<const int, Foo>* is cast to
pair<int, Foo>* the user's explicit specialization would not be used
and the layout would be wrong.  Would it be possible to separate the
C++11 allocator support from the new feature that attempts to reuse
existing nodes?  Or maybe remove the mutable value type stuff so that
nodes can be reused for unordered sets but not unordered maps?
For a non-assignable value_type we can reuse the node (but not the
value_type) by destroying and constructing a new value_type in place:

       __node_type*
       operator()(const __node_type* __n) const
       {
     if (_M_nodes)
       {
         __node_type* __node = _M_nodes;
         allocator_traits<A>::destroy(a, __node->_M_valptr());
         __try {
           allocator_traits<A>::construct(a, __node->_M_valptr(),
*__n->_M_valptr());
           // Construction didn't throw, we can unlink the node.
           _M_nodes = _M_nodes->_M_next();
           __node->_M_nxt = nullptr;
           return __node;
         } __catch (...) {
           // TODO deallocate node
           __throw_exception_again;
         }
       }
     return _M_h._M_allocate_node(__n->_M_v());
       }

This can be much less efficient than assignment if the value_type has
its own allocated memory, but I don't see any alternative. Casting
pair<const A,B>& to pair<A,B>& is not an option.

N.B. the code above


Index: include/ext/throw_allocator.h
===================================================================
--- include/ext/throw_allocator.h	(revision 198117)
+++ include/ext/throw_allocator.h	(working copy)
@@ -90,7 +90,7 @@
     annotate_base()
     {
       label();
-      map();
+      map_alloc();
     }
 
     static void
@@ -111,8 +111,8 @@
 	  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 @@
 	  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 @@
 
     // See if a given label has been allocated.
     inline void
-    check_allocated(size_t label)
+    check(size_t label)
     {
-      const_iterator beg = map().begin();
-      const_iterator end = map().end();
       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)
+    {
+      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 @@
     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 @@
       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 @@
       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 @@
   {
     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 @@
       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 @@
       }
 
       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 @@
       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 @@
       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;
Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 198117)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -156,6 +156,33 @@
   };
 
   /**
+   *  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 @@
   /**
    *  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 @@
 
       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 @@
 
       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 @@
     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 @@
     { 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 @@
 	  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 @@
 	  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 @@
 
       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 @@
 
       if (!__p)
 	__throw_out_of_range(__N("_Map_base::at"));
-      return (__p->_M_v).second;
+      return __p->_M_v().second;
     }
 
   /**
@@ -939,7 +960,8 @@
 
       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 @@
       { 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 @@
 
       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 @@
     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 @@
     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 @@
 
       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 @@
 
       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 @@
 	{ }
     };
 
+  /*
+   * 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
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 198117)
+++ include/bits/hashtable.h	(working copy)
@@ -183,18 +183,23 @@
       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 @@
 					    _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 @@
 
       // 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 @@
 	       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,24 +331,29 @@
 				   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;
       __before_begin		_M_bbegin;
       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 @@
       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 @@
       _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 @@
 
       _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 @@
       { }
 
       _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 @@
 
       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 @@
     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 @@
 
       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 @@
 		 _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 @@
 	       _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 @@
 	       _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 @@
     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 @@
     : __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 @@
       : __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 @@
 	__catch(...)
 	  {
 	    clear();
-	    _M_deallocate_buckets(_M_buckets, _M_bucket_count);
+	    _M_deallocate_buckets();
 	    __throw_exception_again;
 	  }
       }
@@ -876,49 +933,266 @@
 	   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 @@
 	   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,11 @@
       _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,
@@ -953,10 +1224,70 @@
 	   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,
+	   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() 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 @@
     _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 @@
 	       _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 @@
 	       _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 @@
 	       _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 @@
 	       _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 @@
 	  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 @@
 	       _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 @@
 	  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 @@
       {
 	// 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 @@
 	__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 @@
 	  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 @@
 	    _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 @@
 	    }
 	  __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 @@
 	    __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;
     }
Index: include/bits/unordered_set.h
===================================================================
--- include/bits/unordered_set.h	(revision 198117)
+++ include/bits/unordered_set.h	(working copy)
@@ -108,10 +108,10 @@
 
       //@{
       ///  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 @@
       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 @@
        */
       void
       swap(unordered_set& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
@@ -713,10 +743,10 @@
 
       //@{
       ///  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,9 +824,38 @@
 
       /// 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.
        *  @param  __l  An initializer_list.
        *
@@ -1070,6 +1129,7 @@
        */
       void
       swap(unordered_multiset& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
Index: include/bits/unordered_map.h
===================================================================
--- include/bits/unordered_map.h	(revision 198117)
+++ include/bits/unordered_map.h	(working copy)
@@ -113,10 +113,10 @@
 
       //@{
       ///  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 @@
       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 @@
        */
       void
       swap(unordered_map& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
@@ -794,10 +824,10 @@
 
       //@{
       ///  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 @@
       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 @@
        */
       void
       swap(unordered_multimap& __x)
+      noexcept( noexcept(_M_h.swap(__x._M_h)) )
       { _M_h.swap(__x._M_h); }
 
       // observers.
Index: include/std/unordered_set
===================================================================
--- include/std/unordered_set	(revision 198117)
+++ include/std/unordered_set	(working copy)
@@ -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>
Index: include/std/unordered_map
===================================================================
--- include/std/unordered_map	(revision 198117)
+++ include/std/unordered_map	(working copy)
@@ -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>
Index: include/debug/unordered_set
===================================================================
--- include/debug/unordered_set	(revision 198117)
+++ include/debug/unordered_set	(working copy)
@@ -60,6 +60,8 @@
       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,13 +98,28 @@
 		__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&& __x) = default;
+      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&& __uset,
+		    const allocator_type& __a)
+	: _Base(std::move(__uset._M_base()), __a)
+      { }
+
       unordered_set(initializer_list<value_type> __l,
 		    size_type __n = 0,
 		    const hasher& __hf = hasher(),
@@ -115,33 +132,41 @@
       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 @@
       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,13 +549,28 @@
 		__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,
 			 const hasher& __hf = hasher(),
@@ -540,33 +583,41 @@
       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);
       }
Index: include/debug/unordered_map
===================================================================
--- include/debug/unordered_map	(revision 198117)
+++ include/debug/unordered_map	(working copy)
@@ -60,6 +60,9 @@
       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,13 +99,28 @@
 		__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,
 		    const hasher& __hf = hasher(),
@@ -115,33 +133,41 @@
       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 @@
       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,13 +555,28 @@
 		__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,
 			 const hasher& __hf = hasher(),
@@ -545,33 +589,41 @@
       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);
       }
Index: testsuite/util/testsuite_counter_type.h
===================================================================
--- testsuite/util/testsuite_counter_type.h	(revision 198117)
+++ testsuite/util/testsuite_counter_type.h	(working copy)
@@ -36,24 +36,22 @@
     static int move_count;
     static int move_assign_count;
 #endif
+    static int destructor_count;
 
     int val;
     
     counter_type() : val(0)
-    {
-      ++default_count;
-    }
+    { ++default_count; }
 
     counter_type(int inval) : val(inval)
-    {
-      ++specialize_count;
-    }
+    { ++specialize_count; }
 
     counter_type(const counter_type& in) : val(in.val)
-    {
-      ++copy_count;
-    }
+    { ++copy_count; }
 
+    ~counter_type()
+    { ++destructor_count; }
+
     counter_type&
     operator=(const counter_type& in)
     {
@@ -70,7 +68,7 @@
     }
 
     counter_type&
-    operator=(counter_type&& rhs)
+    operator=(counter_type&& rhs) noexcept
     {
       val = rhs.val;
       ++move_assign_count;
@@ -90,6 +88,7 @@
       move_count = 0;
       move_assign_count = 0;
 #endif
+      destructor_count = 0;
     }
 
     bool operator==(const counter_type& rhs) const
@@ -109,6 +108,7 @@
   int counter_type::move_count = 0;
   int counter_type::move_assign_count = 0;
 #endif
+  int counter_type::destructor_count = 0;
 
   struct counter_type_hasher
   {
Index: testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc
===================================================================
--- testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc	(revision 198117)
+++ testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc	(working copy)
@@ -352,11 +352,11 @@
   try 
     { 
       for (size_t n = starting_label; n <= m_n; ++n)
-	m_alloc.check_allocated(n); 
+	m_alloc.check(n); 
     }
   catch (std::logic_error& obj)
     {
-      // On fail, check_allocated should throw std::logic_error.
+      // On fail, check should throw std::logic_error.
       std::cerr << obj.what() << std::endl;
       std::cerr << typeid(Cntnr).name() << std::endl;
       throw;
Index: testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc
===================================================================
--- testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc	(revision 198117)
+++ testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc	(working copy)
@@ -1003,7 +1003,7 @@
   delete m_p_c;
 
   try 
-    { m_alloc.check_allocated(memory_label); }
+    { m_alloc.check(memory_label); }
   catch (...)
     {
       std::cerr << "detected leaks!" << std::endl;
Index: testsuite/util/exception/safety.h
===================================================================
--- testsuite/util/exception/safety.h	(revision 198117)
+++ testsuite/util/exception/safety.h	(working copy)
@@ -1292,6 +1292,48 @@
 	    { throw; }
 	}
       };
+
+    template<typename _Tp>
+      struct assign_operator
+      {
+	_Tp _M_other;
+
+	void
+	operator()(_Tp& __container)
+	{
+	  try
+	    {
+	      // An exception while assigning might leave the container empty
+	      // making future attemps less relevant. So we copy it before to
+	      // always assign to a non empty container. It also check for copy
+	      // constructor exception safety at the same time.
+	      _Tp __clone(__container);
+	      __clone = _M_other;
+	    }
+	  catch(const __gnu_cxx::forced_error&)
+	    { throw; }
+	}
+      };
+
+
+#if __cplusplus >= 201103L
+    template<typename _Tp>
+      struct move_assign_operator
+      {
+	_Tp _M_other;
+
+	void
+	operator()(_Tp& __container)
+	{
+	  try
+	    {
+	      __container = std::move(_M_other);
+	    }
+	  catch(const __gnu_cxx::forced_error&)
+	    { throw; }
+	}
+      };
+#endif
   };
 
   // Base class for exception tests.
@@ -1320,27 +1362,12 @@
       typedef swap<container_type> 			swap;
       typedef iterator_operations<container_type>	iterator_ops;
       typedef const_iterator_operations<container_type>	const_iterator_ops;
+      typedef assign_operator<container_type>		assign_operator;
+#if __cplusplus >= 201103L
+      typedef move_assign_operator<container_type>	move_assign_operator;
+#endif
 
       using base_type::compare;
-
-      // Functor objects.
-      clear			_M_clear;
-      erase_point		_M_erasep;
-      erase_range		_M_eraser;
-      insert_point		_M_insertp;
-      emplace			_M_emplace;
-      emplace_point		_M_emplacep;
-      emplace_front		_M_emplacef;
-      emplace_back		_M_emplaceb;
-      pop_front			_M_popf;
-      pop_back			_M_popb;
-      push_front	       	_M_pushf;
-      push_back			_M_pushb;
-      rehash			_M_rehash;
-      swap			_M_swap;
-
-      iterator_ops	       	_M_iops;
-      const_iterator_ops	_M_ciops;
     };
 
 
@@ -1369,67 +1396,97 @@
 
       using base_type::generate;
 
-      container_type 					_M_container;
-      std::vector<function_type>			_M_functions;
-
       basic_safety() { run(); }
 
       void
       run()
       {
-	// Setup.
-	condition_type::never_adjustor off;
+	{
+	  // Setup.
+	  condition_type::never_adjustor off;
+
+	  // Construct containers.
+	  container_type container;
+	  populate p1(container);
+
+	  // Construct list of member functions to exercise.
+	  std::vector<function_type> functions;
+	  typename base_type::iterator_ops iops;
+	  functions.push_back(function_type(iops));
+	  typename base_type::const_iterator_ops ciops;
+	  functions.push_back(function_type(ciops));
 	
-	// Construct containers.
-	populate p1(_M_container);
-	populate p2(base_type::_M_swap._M_other);
-	
-	// Construct list of member functions to exercise.
-	_M_functions.push_back(function_type(base_type::_M_iops));
-	_M_functions.push_back(function_type(base_type::_M_ciops));
-	
-	_M_functions.push_back(function_type(base_type::_M_erasep));
-	_M_functions.push_back(function_type(base_type::_M_eraser));
-	_M_functions.push_back(function_type(base_type::_M_insertp));
-	_M_functions.push_back(function_type(base_type::_M_emplace));
-	_M_functions.push_back(function_type(base_type::_M_emplacep));
-	_M_functions.push_back(function_type(base_type::_M_emplacef));
-	_M_functions.push_back(function_type(base_type::_M_emplaceb));
-	_M_functions.push_back(function_type(base_type::_M_popf));
-	_M_functions.push_back(function_type(base_type::_M_popb));
-	_M_functions.push_back(function_type(base_type::_M_pushf));
-	_M_functions.push_back(function_type(base_type::_M_pushb));
-	_M_functions.push_back(function_type(base_type::_M_rehash));
-	_M_functions.push_back(function_type(base_type::_M_swap));
-	
-	// Last.
-	_M_functions.push_back(function_type(base_type::_M_clear));
+	  typename base_type::erase_point erasep;
+	  functions.push_back(function_type(erasep));
+	  typename base_type::erase_range eraser;
+	  functions.push_back(function_type(eraser));
+	  typename base_type::insert_point insertp;
+	  functions.push_back(function_type(insertp));
+	  typename base_type::emplace emplace;
+	  functions.push_back(function_type(emplace));
+	  typename base_type::emplace_point emplacep;
+	  functions.push_back(function_type(emplacep));
+	  typename base_type::emplace_front emplacef;
+	  functions.push_back(function_type(emplacef));
+	  typename base_type::emplace_back emplaceb;
+	  functions.push_back(function_type(emplaceb));
+	  typename base_type::pop_front popf;
+	  functions.push_back(function_type(popf));
+	  typename base_type::pop_back popb;
+	  functions.push_back(function_type(popb));
+	  typename base_type::push_front pushf;
+	  functions.push_back(function_type(pushf));
+	  typename base_type::push_back pushb;
+	  functions.push_back(function_type(pushb));
+	  typename base_type::rehash rehash;
+	  functions.push_back(function_type(rehash));
+	  typename base_type::swap swap;
+	  populate p2(swap._M_other);
+	  functions.push_back(function_type(swap));
+	  typename base_type::assign_operator assignop;
+	  populate p3(assignop._M_other);
+	  functions.push_back(function_type(assignop));
+#if __cplusplus >= 201103L
+	  typename base_type::move_assign_operator massignop;
+	  populate p4(massignop._M_other);
+	  functions.push_back(function_type(massignop));
+#endif	
+	  // Last.
+	  typename base_type::clear clear;
+	  functions.push_back(function_type(clear));
 
-	// Run tests.
-	for (auto i = _M_functions.begin(); i != _M_functions.end(); ++i)
-	  {
-	    function_type& f = *i;
-	    run_steps_to_limit(f);
-	  }
+	  // Run tests.
+	  size_t i(1);
+	  for (auto it = functions.begin(); it != functions.end(); ++it)
+	    {
+	      function_type& f = *it;
+	      i = run_steps_to_limit(i, container, f);
+	    }
+	}
+
+	// Now that all instances has been destroyed check that there is no
+	// allocation remaining.
+	std::cout << "Checking remaining stuff" << std::endl;
+	__gnu_cxx::annotate_base::check();
       }
 
       template<typename _Funct>
-	void
-	run_steps_to_limit(const _Funct& __f)
+	size_t
+	run_steps_to_limit(size_t __step, container_type& __cont,
+			   const _Funct& __f)
 	{
-	  size_t i(1);
 	  bool exit(false);
-	  auto a = _M_container.get_allocator();
+	  auto a = __cont.get_allocator();
 
 	  do
 	    {
 	      // Use the current step as an allocator label.
-	      a.set_label(i);
+	      a.set_label(__step);
 
 	      try
 		{
-		  condition_type::limit_adjustor limit(i);
-		  __f(_M_container);
+		  condition_type::limit_adjustor limit(__step);
+		  __f(__cont);
 
 		  // If we get here, done.
 		  exit = true;
@@ -1438,18 +1495,19 @@
 		{
 		  // Check this step for allocations.
 		  // NB: Will throw std::logic_error if allocations.
-		  a.check_allocated(i);
+		  a.check(__step);
 
 		  // Check memory allocated with operator new.
 
-		  ++i;
 		}
+	      ++__step;
 	    }
 	  while (!exit);
 
 	  // Log count info.
 	  std::cout << __f.target_type().name() << std::endl;
-	  std::cout << "end count " << i << std::endl;
+	  std::cout << "end count " << __step << std::endl;
+	  return __step;
 	}
   };
 
@@ -1467,8 +1525,6 @@
       typedef typename base_type::populate 		populate;
       typedef __gnu_cxx::random_condition		condition_type;
 
-      container_type 					_M_container;
-
       generation_prohibited()  { run(); }
 
       void
@@ -1479,10 +1535,13 @@
 	// propagated and in error. Sudden death!
 
 	// Setup.
+	container_type container;
+	typename base_type::swap swap;
+
 	{
 	  condition_type::never_adjustor off;
-	  populate p1(_M_container);
-	  populate p2(base_type::_M_swap._M_other);
+	  populate p1(container);
+	  populate p2(swap._M_other);
 	}
 
 	// Run tests.
@@ -1493,20 +1552,27 @@
 	  // constructor or assignment operator of value_type throws.
 	  if (!traits<container_type>::has_throwing_erase::value)
 	    {
-	      this->_M_erasep(_M_container);
-	      this->_M_eraser(_M_container);
+	      typename base_type::erase_point erasep;
+	      erasep(container);
+	      typename base_type::erase_range eraser;
+	      eraser(container);
 	    }
 
-	  this->_M_popf(_M_container);
-	  this->_M_popb(_M_container);
+	  typename base_type::pop_front popf;
+	  popf(container);
+	  typename base_type::pop_back popb;
+	  popb(container);
 
-	  this->_M_iops(_M_container);
-	  this->_M_ciops(_M_container);
+	  typename base_type::iterator_ops iops;
+	  iops(container);
+	  typename base_type::const_iterator_ops ciops;
+	  ciops(container);
 
-	  this->_M_swap(_M_container);
+	  swap(container);
 
 	  // Last.
-	  this->_M_clear(_M_container);
+	  typename base_type::clear clear;
+	  clear(container);
 	}
       }
     };
@@ -1529,16 +1595,8 @@
 
       using base_type::compare;
 
-      container_type 					_M_container_test;
-      container_type 					_M_container_control;
-      std::vector<function_type>			_M_functions;
-
       propagation_consistent() { run(); }
 
-      void
-      sync()
-      { _M_container_test = _M_container_control; }
-
       // Run test.
       void
       run()
@@ -1547,48 +1605,59 @@
 	condition_type::never_adjustor off;
 
 	// Construct containers.
-	populate p(_M_container_control);
+	container_type container_control;
 
+	populate p(container_control);
+
 	// Construct list of member functions to exercise.
-	_M_functions.push_back(function_type(base_type::_M_emplace));
-	_M_functions.push_back(function_type(base_type::_M_emplacep));
-	_M_functions.push_back(function_type(base_type::_M_emplacef));
-	_M_functions.push_back(function_type(base_type::_M_emplaceb));
-	_M_functions.push_back(function_type(base_type::_M_pushf));
-	_M_functions.push_back(function_type(base_type::_M_pushb));
-	_M_functions.push_back(function_type(base_type::_M_insertp));
-	_M_functions.push_back(function_type(base_type::_M_rehash));
+	std::vector<function_type> functions;
+	typename base_type::emplace emplace;
+	functions.push_back(function_type(emplace));
+	typename base_type::emplace_point emplacep;
+	functions.push_back(function_type(emplacep));
+	typename base_type::emplace_front emplacef;
+	functions.push_back(function_type(emplacef));
+	typename base_type::emplace_back emplaceb;
+	functions.push_back(function_type(emplaceb));
+	typename base_type::push_front pushf;
+	functions.push_back(function_type(pushf));
+	typename base_type::push_back pushb;
+	functions.push_back(function_type(pushb));
+	typename base_type::insert_point insertp;
+	functions.push_back(function_type(insertp));
+	typename base_type::rehash rehash;
+	functions.push_back(function_type(rehash));
 
 	// Run tests.
-	for (auto i = _M_functions.begin(); i != _M_functions.end(); ++i)
+	for (auto i = functions.begin(); i != functions.end(); ++i)
 	  {
 	    function_type& f = *i;
-	    run_steps_to_limit(f);
+	    run_steps_to_limit(container_control, f);
 	  }
       }
 
       template<typename _Funct>
 	void
-	run_steps_to_limit(const _Funct& __f)
+	run_steps_to_limit(container_type& container_control, const _Funct& __f)
 	{
 	  size_t i(1);
 	  bool exit(false);
 
 	  do
 	    {
-	      sync();
+	      container_type container_test(container_control);
 
 	      try
 		{
 		  condition_type::limit_adjustor limit(i);
-		  __f(_M_container_test);
+		  __f(container_test);
 
 		  // If we get here, done.
 		  exit = true;
 		}
 	      catch(const __gnu_cxx::forced_error&)
 		{
-		  compare(_M_container_control, _M_container_test);
+		  compare(container_control, container_test);
 		  ++i;
 		}
 	    }
Index: testsuite/23_containers/unordered_map/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/copy_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/allocator/copy_assign.cc	(revision 0)
@@ -0,0 +1,77 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/noexcept.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/allocator/noexcept.cc	(revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+  inline void
+  swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+  noexcept(false)
+  {
+    typedef uneq_allocator<T> base_alloc;
+    swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+  }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  typedef std::allocator<T> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1;
+  test_type v2;
+  // this is a GNU extension for std::allocator
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/minimal.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/allocator/minimal.cc	(revision 0)
@@ -0,0 +1,63 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_map<T, T, hash, equal_to, SimpleAllocator<T>>;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef SimpleAllocator<T> alloc_type;
+  typedef std::allocator_traits<alloc_type> traits_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v(alloc_type{});
+  v.emplace(std::piecewise_construct,
+	    std::make_tuple(T()), std::make_tuple(T()));
+  VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/swap.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/allocator/swap.cc	(revision 0)
@@ -0,0 +1,96 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<std::pair<const T, T>, false>&,
+           const propagating_allocator<std::pair<const T, T>, false>&)
+{
+  return true;
+}
+
+bool
+operator!=(const propagating_allocator<std::pair<const T, T>, false>&,
+           const propagating_allocator<std::pair<const T, T>, false>&)
+{
+  return false;
+}
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<std::pair<const T, T>, false> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  std::swap(v1, v2);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+  // swap back so assertions in uneq_allocator::deallocate don't fail
+  std::swap(v1, v2);
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<std::pair<const T, T>, true> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  std::swap(v1, v2);
+  VERIFY(2 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/copy.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/allocator/copy.cc	(revision 0)
@@ -0,0 +1,71 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_map<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_map/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_map/allocator/move_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/allocator/move_assign.cc	(revision 0)
@@ -0,0 +1,89 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, false> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_map<counter_type, counter_type, hash,
+			     std::equal_to<counter_type>,
+			     alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(1), std::make_tuple(1));
+
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(2), std::make_tuple(2));
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  // No move because key is const.
+  VERIFY( counter_type::move_assign_count == 0  );
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, true> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_map<counter_type, counter_type, hash,
+			     std::equal_to<counter_type>,
+			     alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(1), std::make_tuple(1));
+
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(2), std::make_tuple(2));
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY(0 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+
+  VERIFY( counter_type::move_assign_count == 0 );
+  VERIFY( counter_type::destructor_count == 2 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/noexcept.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/noexcept.cc	(revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+  inline void
+  swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+  noexcept(false)
+  {
+    typedef uneq_allocator<T> base_alloc;
+    swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+  }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  typedef std::allocator<T> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1;
+  test_type v2;
+  // this is a GNU extension for std::allocator
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/minimal.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/minimal.cc	(revision 0)
@@ -0,0 +1,64 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_multimap<T, T, hash, equal_to,
+				       SimpleAllocator<T>>;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef SimpleAllocator<T> alloc_type;
+  typedef std::allocator_traits<alloc_type> traits_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v(alloc_type{});
+  v.emplace(std::piecewise_construct,
+	    std::make_tuple(T()), std::make_tuple(T()));
+  VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/swap.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/swap.cc	(revision 0)
@@ -0,0 +1,96 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<std::pair<const T, T>, false>&,
+           const propagating_allocator<std::pair<const T, T>, false>&)
+{
+  return true;
+}
+
+bool
+operator!=(const propagating_allocator<std::pair<const T, T>, false>&,
+           const propagating_allocator<std::pair<const T, T>, false>&)
+{
+  return false;
+}
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<std::pair<const T, T>, false> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  std::swap(v1, v2);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+  // swap back so assertions in uneq_allocator::deallocate don't fail
+  std::swap(v1, v2);
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<std::pair<const T, T>, true> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  std::swap(v1, v2);
+  VERIFY(2 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/copy.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/copy.cc	(revision 0)
@@ -0,0 +1,71 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/move_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/move_assign.cc	(revision 0)
@@ -0,0 +1,89 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, false> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_multimap<counter_type, counter_type, hash,
+				  std::equal_to<counter_type>,
+				  alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(1), std::make_tuple(1));
+
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(2), std::make_tuple(2));
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  // No move because key is const.
+  VERIFY( counter_type::move_assign_count == 0  );
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, true> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_multimap<counter_type, counter_type, hash,
+				  std::equal_to<counter_type>,
+				  alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(1), std::make_tuple(1));
+
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(2), std::make_tuple(2));
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY(0 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+
+  VERIFY( counter_type::move_assign_count == 0 );
+  VERIFY( counter_type::destructor_count == 2 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/allocator/copy_assign.cc	(revision 0)
@@ -0,0 +1,77 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_multimap<T, T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  test_type v2(alloc_type(2));
+  v2.emplace(std::piecewise_construct,
+	     std::make_tuple(T()), std::make_tuple(T()));
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/noexcept.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/noexcept.cc	(revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+  inline void
+  swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+  noexcept(false)
+  {
+    typedef uneq_allocator<T> base_alloc;
+    swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+  }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  typedef std::allocator<T> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1;
+  test_type v2;
+  // this is a GNU extension for std::allocator
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/minimal.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/minimal.cc	(revision 0)
@@ -0,0 +1,62 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_multiset<T, hash, equal_to, SimpleAllocator<T>>;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef SimpleAllocator<T> alloc_type;
+  typedef std::allocator_traits<alloc_type> traits_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v(alloc_type{});
+  v.insert(T());
+  VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/swap.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/swap.cc	(revision 0)
@@ -0,0 +1,92 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<T, false>&,
+           const propagating_allocator<T, false>&)
+{
+  return true;
+}
+
+bool
+operator!=(const propagating_allocator<T, false>&,
+           const propagating_allocator<T, false>&)
+{
+  return false;
+}
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  std::swap(v1, v2);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+  // swap back so assertions in uneq_allocator::deallocate don't fail
+  std::swap(v1, v2);
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  std::swap(v1, v2);
+  VERIFY(2 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/copy.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/copy.cc	(revision 0)
@@ -0,0 +1,69 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/move_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/move_assign.cc	(revision 0)
@@ -0,0 +1,86 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, false> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_multiset<counter_type, hash,
+				  std::equal_to<counter_type>,
+				  alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(0);
+
+  test_type v2(alloc_type(2));
+  v2.emplace(1);
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  VERIFY( counter_type::move_count == 1  );
+  VERIFY( counter_type::destructor_count == 2 );
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, true> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_multiset<counter_type, hash,
+				  std::equal_to<counter_type>,
+				  alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(0);
+
+  test_type v2(alloc_type(2));
+  v2.emplace(0);
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY(0 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+
+  VERIFY( counter_type::move_count == 0 );
+  VERIFY( counter_type::copy_count == 0 );
+  VERIFY( counter_type::destructor_count == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/allocator/copy_assign.cc	(revision 0)
@@ -0,0 +1,73 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_multiset<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc	(revision 198117)
+++ testsuite/23_containers/unordered_set/instantiation_neg.cc	(working copy)
@@ -19,7 +19,7 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "with noexcept" "" { target *-*-* } 252 }
+// { dg-error "with noexcept" "" { target *-*-* } 254 }
 
 #include <unordered_set>
 
Index: testsuite/23_containers/unordered_set/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/copy_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/allocator/copy_assign.cc	(revision 0)
@@ -0,0 +1,73 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  v2 = v1;
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/noexcept.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/noexcept.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/allocator/noexcept.cc	(revision 0)
@@ -0,0 +1,88 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+namespace __gnu_test
+{
+  inline void
+  swap(propagating_allocator<T, true>& l, propagating_allocator<T, true>& r)
+  noexcept(false)
+  {
+    typedef uneq_allocator<T> base_alloc;
+    swap(static_cast<base_alloc&>(l), static_cast<base_alloc&>(r));
+  }
+}
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  typedef std::allocator<T> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1;
+  test_type v2;
+  // this is a GNU extension for std::allocator
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test02()
+{
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( !noexcept( v1 = std::move(v2) ), "Move assign can throw" );
+  static_assert( noexcept( v1.swap(v2) ), "Swap cannot throw" );
+}
+
+void test03()
+{
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  test_type v2(alloc_type(2));
+  static_assert( noexcept( v1 = std::move(v2) ), "Move assign cannot throw" );
+  // static_assert( !noexcept( v1.swap(v2) ), "Swap can throw" );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/minimal.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/minimal.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/allocator/minimal.cc	(revision 0)
@@ -0,0 +1,62 @@
+// Copyright (C) 2012-2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+
+bool operator==(const T& l, const T& r) { return l.i == r.i; }
+bool operator<(const T& l, const T& r) { return l.i < r.i; }
+
+using __gnu_test::SimpleAllocator;
+
+template class std::unordered_set<T, hash, equal_to, SimpleAllocator<T>>;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef SimpleAllocator<T> alloc_type;
+  typedef std::allocator_traits<alloc_type> traits_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v(alloc_type{});
+  v.insert(T());
+  VERIFY( v.max_size() == traits_type::max_size(v.get_allocator()) );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/swap.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/swap.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/allocator/swap.cc	(revision 0)
@@ -0,0 +1,92 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+// It is undefined behaviour to swap() containers wth unequal allocators
+// if the allocator doesn't propagate, so ensure the allocators compare
+// equal, while still being able to test propagation via get_personality().
+bool
+operator==(const propagating_allocator<T, false>&,
+           const propagating_allocator<T, false>&)
+{
+  return true;
+}
+
+bool
+operator!=(const propagating_allocator<T, false>&,
+           const propagating_allocator<T, false>&)
+{
+  return false;
+}
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  std::swap(v1, v2);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(2 == v2.get_allocator().get_personality());
+  // swap back so assertions in uneq_allocator::deallocate don't fail
+  std::swap(v1, v2);
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(alloc_type(2));
+  v2.insert(T());
+  std::swap(v1, v2);
+  VERIFY(2 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/copy.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/copy.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/allocator/copy.cc	(revision 0)
@@ -0,0 +1,69 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+struct T { int i; };
+
+struct hash
+{
+  std::size_t operator()(const T t) const noexcept
+  { return t.i; }
+};
+
+struct equal_to
+{
+  bool operator()(const T& lhs, const T& rhs) const noexcept
+  { return lhs.i == rhs.i; }
+};
+
+using __gnu_test::propagating_allocator;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, false> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(0 == v2.get_allocator().get_personality());
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<T, true> alloc_type;
+  typedef std::unordered_set<T, hash, equal_to, alloc_type> test_type;
+  test_type v1(alloc_type(1));
+  v1.insert(T());
+  test_type v2(v1);
+  VERIFY(1 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/unordered_set/allocator/move_assign.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/allocator/move_assign.cc	(revision 0)
@@ -0,0 +1,86 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=c++11" }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+#include <testsuite_counter_type.h>
+
+using __gnu_test::propagating_allocator;
+using __gnu_test::counter_type;
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, false> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_set<counter_type, hash,
+			     std::equal_to<counter_type>,
+			     alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(0);
+
+  test_type v2(alloc_type(2));
+  v2.emplace(1);
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  VERIFY( counter_type::move_count == 1  );
+  VERIFY( counter_type::destructor_count == 2 );
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+  typedef propagating_allocator<counter_type, true> alloc_type;
+  typedef __gnu_test::counter_type_hasher hash;
+  typedef std::unordered_set<counter_type, hash,
+			     std::equal_to<counter_type>,
+			     alloc_type> test_type;
+
+  test_type v1(alloc_type(1));
+  v1.emplace(0);
+
+  test_type v2(alloc_type(2));
+  v2.emplace(0);
+
+  counter_type::reset();
+
+  v2 = std::move(v1);
+
+  VERIFY(0 == v1.get_allocator().get_personality());
+  VERIFY(1 == v2.get_allocator().get_personality());
+
+  VERIFY( counter_type::move_count == 0 );
+  VERIFY( counter_type::copy_count == 0 );
+  VERIFY( counter_type::destructor_count == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc	(revision 198117)
+++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc	(working copy)
@@ -19,7 +19,7 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "default constructible" "" { target *-*-* } 268 }
+// { dg-error "default constructible" "" { target *-*-* } 272 }
 
 #include <unordered_set>
 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]