diff mbox

libstdc++/29988 Rb_Tree reuse allocated nodes

Message ID 539F522D.2040600@gmail.com
State New
Headers show

Commit Message

François Dumont June 16, 2014, 8:23 p.m. UTC 
Hi

     Here is another proposal taking into account your remarks except 
the one below.

     In fact I had no problem with lambda, I just needed to store them 
in a variable, lambda do not need to be made mutable.

On 11/06/2014 14:02, Jonathan Wakely wrote:
>
>> @@ -514,11 +651,11 @@
>>       { return this->_M_impl._M_header._M_right; }
>>
>>       _Link_type
>> -      _M_begin() _GLIBCXX_NOEXCEPT
>> +      _M_begin() const _GLIBCXX_NOEXCEPT
>>       { return 
>> static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
>
> What's the purpose of this change?
> Although it can be 'const' it is consistent with the usual
> begin()/end() functions that the functions returning a mutable iterator
> are non-const and the functions returning a constant iterator are const.
>
>>       _Const_Link_type
>> -      _M_begin() const _GLIBCXX_NOEXCEPT
>> +      _M_cbegin() const _GLIBCXX_NOEXCEPT
>>       {
>>     return static_cast<_Const_Link_type>
>>       (this->_M_impl._M_header._M_parent);
>> @@ -529,7 +666,7 @@
>>       { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
>>
>>       _Const_Link_type
>> -      _M_end() const _GLIBCXX_NOEXCEPT
>> +      _M_cend() const _GLIBCXX_NOEXCEPT
>>       { return 
>> reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
>>
>>       static const_reference
>
> I'm not very comfortable with this renaming.
>
> Having consistent _M_begin() functions allows using them in template
> code that doesn't care if it's using the const or non-const version.
>
>
I try to revert this part and so remember why I did it in the first place.

I needed to change _M_copy signature to:

       _Link_type
       _M_copy(_Link_type __x, _Link_type __p)

     because I now use this method to also move the elements of the data 
structure, I cannot move from a _Const_Like_type so I change first 
parameter to _Link_type. I see that there are some code duplications to 
deal with _Const_Link_type and _Link_type in 2 different part of the 
code but I didn't want to duplicate again here and simply made _M_copy 
more more flexible by taking a _Link_type rather than a _Const_Link_type.

     I don't really see interest of the existing code duplications so I 
prefer to not do the same and write the code only once.

François
diff mbox

Patch

Index: include/bits/stl_map.h
===================================================================
--- include/bits/stl_map.h	(revision 211713)
+++ include/bits/stl_map.h	(working copy)
@@ -297,28 +297,9 @@ 
       }
 
 #if __cplusplus >= 201103L
-      /**
-       *  @brief  %Map move assignment operator.
-       *  @param  __x  A %map of identical element and allocator types.
-       *
-       *  The contents of @a __x are moved into this map (without copying
-       *  if the allocators compare equal or get moved on assignment).
-       *  Afterwards @a __x is in a valid, but unspecified state.
-       */
+      /// Move assignment operator.
       map&
-      operator=(map&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
-      {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x.begin()),
-		   std::__make_move_if_noexcept_iterator(__x.end()));
-	    __x.clear();
-	  }
-	return *this;
-      }
+      operator=(map&&) = default;
 
       /**
        *  @brief  %Map list assignment operator.
@@ -334,8 +315,7 @@ 
       map&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_unique(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_multimap.h
===================================================================
--- include/bits/stl_multimap.h	(revision 211713)
+++ include/bits/stl_multimap.h	(working copy)
@@ -292,28 +292,9 @@ 
       }
 
 #if __cplusplus >= 201103L
-      /**
-       *  @brief  %Multimap move assignment operator.
-       *  @param  __x  A %multimap of identical element and allocator types.
-       *
-       *  The contents of @a __x are moved into this multimap (without copying
-       *  if the allocators compare equal or get moved on assignment).
-       *  Afterwards @a __x is in a valid, but unspecified state.
-       */
+      /// Move assignment operator.
       multimap&
-      operator=(multimap&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
-      {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x.begin()),
-		   std::__make_move_if_noexcept_iterator(__x.end()));
-	    __x.clear();
-	  }
-	return *this;
-      }
+      operator=(multimap&&) = default;
 
       /**
        *  @brief  %Multimap list assignment operator.
@@ -329,8 +310,7 @@ 
       multimap&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_equal(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_multiset.h
===================================================================
--- include/bits/stl_multiset.h	(revision 211713)
+++ include/bits/stl_multiset.h	(working copy)
@@ -263,28 +263,9 @@ 
       }
 
 #if __cplusplus >= 201103L
-      /**
-       *  @brief  %Multiset move assignment operator.
-       *  @param  __x  A %multiset of identical element and allocator types.
-       *
-       *  The contents of @a __x are moved into this %multiset (without
-       *  copying if the allocators compare equal or get moved on assignment).
-       *  Afterwards @a __x is in a valid, but unspecified state.
-       */
+      /// Move assignment operator.
       multiset&
-      operator=(multiset&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
-      {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()),
-		   std::__make_move_if_noexcept_iterator(__x._M_t.end()));
-	    __x.clear();
-	  }
-	return *this;
-      }
+      operator=(multiset&&) = default;
 
       /**
        *  @brief  %Multiset list assignment operator.
@@ -300,8 +281,7 @@ 
       multiset&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_equal(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_set.h
===================================================================
--- include/bits/stl_set.h	(revision 211713)
+++ include/bits/stl_set.h	(working copy)
@@ -267,28 +267,9 @@ 
       }
 
 #if __cplusplus >= 201103L
-      /**
-       *  @brief %Set move assignment operator.
-       *  @param __x  A %set of identical element and allocator types.
-       *
-       *  The contents of @a __x are moved into this %set (without copying
-       *  if the allocators compare equal or get moved on assignment).
-       *  Afterwards @a __x is in a valid, but unspecified state.
-       */
+      /// Move assignment operator.
       set&
-      operator=(set&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
-      {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()),
-		   std::__make_move_if_noexcept_iterator(__x._M_t.end()));
-	    __x.clear();
-	  }
-      	return *this;
-      }
+      operator=(set&&) = default;
 
       /**
        *  @brief  %Set list assignment operator.
@@ -304,8 +285,7 @@ 
       set&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_unique(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h	(revision 211713)
+++ include/bits/stl_tree.h	(working copy)
@@ -353,7 +353,107 @@ 
     protected:
       typedef _Rb_tree_node_base* 		_Base_ptr;
       typedef const _Rb_tree_node_base* 	_Const_Base_ptr;
+      typedef _Rb_tree_node<_Val>* 		_Link_type;
+      typedef const _Rb_tree_node<_Val>*	_Const_Link_type;
 
+    private:
+      // Functor recycling a pool of nodes and using allocation once the pool is
+      // empty.
+      struct _Reuse_or_alloc_node
+      {
+	_Reuse_or_alloc_node(const _Rb_tree_node_base& __header,
+			     _Rb_tree& __t)
+	  : _M_root(__header._M_parent), _M_nodes(__header._M_right), _M_t(__t)
+	{
+	  if (_M_root)
+	    _M_root->_M_parent = 0;
+	  else
+	    _M_nodes = 0;
+	}
+
+#if __cplusplus >= 201103L
+	_Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
+#endif
+
+	~_Reuse_or_alloc_node()
+	{ _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
+
+	template<typename _Arg>
+	  _Link_type
+#if __cplusplus < 201103L
+	  operator()(const _Arg& __arg)
+#else
+	  operator()(_Arg&& __arg)
+#endif
+	  {
+	    _Link_type __node = static_cast<_Link_type>(_M_extract());
+	    if (__node)
+	      {
+		_M_t._M_destroy_node(__node);
+		_M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
+		return __node;
+	      }
+
+	    return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
+	  }
+
+      private:
+	_Base_ptr
+	_M_extract()
+	{
+	  if (!_M_nodes)
+	    return _M_nodes;
+
+	  _Base_ptr __node = _M_nodes;
+	  _M_nodes = _M_nodes->_M_parent;
+	  if (_M_nodes)
+	    {
+	      if (_M_nodes->_M_right == __node)
+		{
+		  _M_nodes->_M_right = 0;
+
+		  if (_M_nodes->_M_left)
+		    {
+		      _M_nodes = _M_nodes->_M_left;
+
+		      while (_M_nodes->_M_right)
+			_M_nodes = _M_nodes->_M_right;
+		    }
+		}
+	      else // __node is on the left.
+		_M_nodes->_M_left = 0;
+	    }
+	  else
+	    _M_root = 0;
+
+	  return __node;
+	}
+
+	_Base_ptr _M_root;
+	_Base_ptr _M_nodes;
+	_Rb_tree& _M_t;
+      };
+
+      // Functor similar to the previous one but without any pool of node to
+      // recycle.
+      struct _Alloc_node
+      {
+	_Alloc_node(_Rb_tree& __t)
+	  : _M_t(__t) { }
+
+	template<typename _Arg>
+	  _Link_type
+#if __cplusplus < 201103L
+	  operator()(const _Arg& __arg) const
+#else
+	  operator()(_Arg&& __arg) const
+#endif
+	  { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
+
+      private:
+	_Rb_tree& _M_t;
+      };
+
     public:
       typedef _Key 				key_type;
       typedef _Val 				value_type;
@@ -361,8 +461,6 @@ 
       typedef const value_type* 		const_pointer;
       typedef value_type& 			reference;
       typedef const value_type& 		const_reference;
-      typedef _Rb_tree_node<_Val>* 		_Link_type;
-      typedef const _Rb_tree_node<_Val>*	_Const_Link_type;
       typedef size_t 				size_type;
       typedef ptrdiff_t 			difference_type;
       typedef _Alloc 				allocator_type;
@@ -389,44 +487,55 @@ 
       { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
 
 #if __cplusplus < 201103L
-      _Link_type
-      _M_create_node(const value_type& __x)
+      void
+      _M_construct_node(_Link_type __node, const value_type& __x)
       {
-	_Link_type __tmp = _M_get_node();
 	__try
-	  { get_allocator().construct(__tmp->_M_valptr(), __x); }
+	  { get_allocator().construct(__node->_M_valptr(), __x); }
 	__catch(...)
 	  {
-	    _M_put_node(__tmp);
+	    _M_put_node(__node);
 	    __throw_exception_again;
 	  }
+      }
+
+      _Link_type
+      _M_create_node(const value_type& __x)
+      {
+	_Link_type __tmp = _M_get_node();
+	_M_construct_node(__tmp, __x);
 	return __tmp;
       }
 
       void
       _M_destroy_node(_Link_type __p)
-      {
-	get_allocator().destroy(__p->_M_valptr());
-	_M_put_node(__p);
-      }
+      { get_allocator().destroy(__p->_M_valptr()); }
 #else
       template<typename... _Args>
-        _Link_type
-        _M_create_node(_Args&&... __args)
+	void
+	_M_construct_node(_Link_type __node, _Args&&... __args)
 	{
-	  _Link_type __tmp = _M_get_node();
 	  __try
 	    {
-	      ::new(__tmp) _Rb_tree_node<_Val>;
+	      ::new(__node) _Rb_tree_node<_Val>;
 	      _Alloc_traits::construct(_M_get_Node_allocator(),
-				       __tmp->_M_valptr(),
+				       __node->_M_valptr(),
 				       std::forward<_Args>(__args)...);
 	    }
 	  __catch(...)
 	    {
-	      _M_put_node(__tmp);
+	      __node->~_Rb_tree_node<_Val>();
+	      _M_put_node(__node);
 	      __throw_exception_again;
 	    }
+	}
+
+      template<typename... _Args>
+        _Link_type
+        _M_create_node(_Args&&... __args)
+	{
+	  _Link_type __tmp = _M_get_node();
+	  _M_construct_node(__tmp, std::forward<_Args>(__args)...);
 	  return __tmp;
 	}
 
@@ -435,23 +544,29 @@ 
       {
 	_Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
 	__p->~_Rb_tree_node<_Val>();
-	_M_put_node(__p);
       }
 #endif
 
-      _Link_type
-      _M_clone_node(_Const_Link_type __x)
+      void
+      _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
       {
-	_Link_type __tmp = _M_create_node(*__x->_M_valptr());
-	__tmp->_M_color = __x->_M_color;
-	__tmp->_M_left = 0;
-	__tmp->_M_right = 0;
-	return __tmp;
+	_M_destroy_node(__p);
+	_M_put_node(__p);
       }
 
+      template<typename _NodeGen>
+	_Link_type
+	_M_clone_node(_Link_type __x, _NodeGen& __node_gen)
+	{
+	  _Link_type __tmp = __node_gen(*__x->_M_valptr());
+	  __tmp->_M_color = __x->_M_color;
+	  __tmp->_M_left = 0;
+	  __tmp->_M_right = 0;
+	  return __tmp;
+	}
+
     protected:
-      template<typename _Key_compare, 
-	       bool _Is_pod_comparator = __is_pod(_Key_compare)>
+      template<typename _Key_compare>
         struct _Rb_tree_impl : public _Node_allocator
         {
 	  _Key_compare		_M_key_compare;
@@ -475,6 +590,15 @@ 
 	  { _M_initialize(); }
 #endif
 
+	  void
+	  _M_reset()
+	  {
+	    this->_M_header._M_parent = 0;
+	    this->_M_header._M_left = &this->_M_header;
+	    this->_M_header._M_right = &this->_M_header;
+	    this->_M_node_count = 0;
+	  }
+
 	private:
 	  void
 	  _M_initialize()
@@ -514,11 +638,11 @@ 
       { return this->_M_impl._M_header._M_right; }
 
       _Link_type
-      _M_begin() _GLIBCXX_NOEXCEPT
+      _M_begin() const _GLIBCXX_NOEXCEPT
       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 
       _Const_Link_type
-      _M_begin() const _GLIBCXX_NOEXCEPT
+      _M_cbegin() const _GLIBCXX_NOEXCEPT
       {
 	return static_cast<_Const_Link_type>
 	  (this->_M_impl._M_header._M_parent);
@@ -529,7 +653,7 @@ 
       { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
 
       _Const_Link_type
-      _M_end() const _GLIBCXX_NOEXCEPT
+      _M_cend() const _GLIBCXX_NOEXCEPT
       { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 
       static const_reference
@@ -603,9 +727,9 @@ 
 				   const key_type& __k);
 
 #if __cplusplus >= 201103L
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGen>
         iterator
-        _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
+	_M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
 
       iterator
       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
@@ -624,9 +748,10 @@ 
       iterator
       _M_insert_equal_lower_node(_Link_type __z);
 #else
-      iterator
-      _M_insert_(_Base_ptr __x, _Base_ptr __y,
-		 const value_type& __v);
+      template<typename _NodeGen>
+	iterator
+	_M_insert_(_Base_ptr __x, _Base_ptr __y,
+		   const value_type& __v, _NodeGen&);
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 233. Insertion hints in associative containers.
@@ -637,8 +762,16 @@ 
       _M_insert_equal_lower(const value_type& __x);
 #endif
 
+      template<typename _NodeGen>
+	_Link_type
+	_M_copy(_Link_type __x, _Link_type __p, _NodeGen&);
+
       _Link_type
-      _M_copy(_Const_Link_type __x, _Link_type __p);
+      _M_copy(_Link_type __x, _Link_type __p)
+      {
+	_Alloc_node __an(*this);
+	return _M_copy(__x, __p, __an);
+      }
 
       void
       _M_erase(_Link_type __x);
@@ -688,7 +821,7 @@ 
       _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
       {
-	if (__x._M_root() != 0)
+	if (__x._M_root() != nullptr)
 	  {
 	    _M_root() = _M_copy(__x._M_begin(), _M_end());
 	    _M_leftmost() = _S_minimum(_M_root());
@@ -792,14 +925,30 @@ 
         iterator
         _M_insert_equal(_Arg&& __x);
 
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGen>
         iterator
-        _M_insert_unique_(const_iterator __position, _Arg&& __x);
+	_M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
 
       template<typename _Arg>
-        iterator
-        _M_insert_equal_(const_iterator __position, _Arg&& __x);
+	iterator
+	_M_insert_unique_(const_iterator __pos, _Arg&& __x)
+	{
+	  _Alloc_node __an(*this);
+	  return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
+	}
 
+      template<typename _Arg, typename _NodeGen>
+	iterator
+	_M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
+
+      template<typename _Arg>
+	iterator
+	_M_insert_equal_(const_iterator __pos, _Arg&& __x)
+	{
+	  _Alloc_node __an(*this);
+	  return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
+	}
+
       template<typename... _Args>
 	pair<iterator, bool>
 	_M_emplace_unique(_Args&&... __args);
@@ -822,11 +971,28 @@ 
       iterator
       _M_insert_equal(const value_type& __x);
 
+      template<typename _NodeGen>
+	iterator
+	_M_insert_unique_(const_iterator __pos, const value_type& __x,
+			  _NodeGen&);
+
       iterator
-      _M_insert_unique_(const_iterator __position, const value_type& __x);
+      _M_insert_unique_(const_iterator __pos, const value_type& __x)
+      {
+	_Alloc_node __an(*this);
+	return _M_insert_unique_(__pos, __x, __an);
+      }
 
+      template<typename _NodeGen>
+	iterator
+	_M_insert_equal_(const_iterator __pos, const value_type& __x,
+			 _NodeGen&);
       iterator
-      _M_insert_equal_(const_iterator __position, const value_type& __x);
+      _M_insert_equal_(const_iterator __pos, const value_type& __x)
+      {
+	_Alloc_node __an(*this);
+	return _M_insert_equal_(__pos, __x, __an);
+      }
 #endif
 
       template<typename _InputIterator>
@@ -906,10 +1072,7 @@ 
       clear() _GLIBCXX_NOEXCEPT
       {
         _M_erase(_M_begin());
-        _M_leftmost() = _M_end();
-        _M_root() = 0;
-        _M_rightmost() = _M_end();
-        _M_impl._M_node_count = 0;
+	_M_impl._M_reset();
       }
 
       // Set operations.
@@ -928,7 +1091,7 @@ 
 
       const_iterator
       lower_bound(const key_type& __k) const
-      { return _M_lower_bound(_M_begin(), _M_end(), __k); }
+      { return _M_lower_bound(_M_cbegin(), _M_cend(), __k); }
 
       iterator
       upper_bound(const key_type& __k)
@@ -936,7 +1099,7 @@ 
 
       const_iterator
       upper_bound(const key_type& __k) const
-      { return _M_upper_bound(_M_begin(), _M_end(), __k); }
+      { return _M_upper_bound(_M_cbegin(), _M_cend(), __k); }
 
       pair<iterator, iterator>
       equal_range(const key_type& __k);
@@ -949,9 +1112,17 @@ 
       __rb_verify() const;
 
 #if __cplusplus >= 201103L
-      bool
-      _M_move_assign(_Rb_tree&);
+      _Rb_tree&
+      operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move());
 
+      template<typename _Iterator>
+	void
+	_M_assign_unique(_Iterator, _Iterator);
+
+      template<typename _Iterator>
+	void
+	_M_assign_equal(_Iterator, _Iterator);
+
     private:
       // Move elements from container with equal allocator.
       void
@@ -1027,7 +1198,7 @@ 
     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
     {
       using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
-      if (__x._M_root() != 0)
+      if (__x._M_root() != nullptr)
 	_M_move_data(__x, __eq());
     }
 
@@ -1060,7 +1231,11 @@ 
 	  _M_move_data(__x, std::true_type());
       else
 	{
-	  _M_root() = _M_copy(__x._M_begin(), _M_end());
+	  _Alloc_node __an(*this);
+	  auto __lbd =
+	    [&__an](value_type& __val)
+	    { return __an(std::move_if_noexcept(__val)); };
+	  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
 	  _M_leftmost() = _S_minimum(_M_root());
 	  _M_rightmost() = _S_maximum(_M_root());
 	  _M_impl._M_node_count = __x._M_impl._M_node_count;
@@ -1069,9 +1244,10 @@ 
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-    bool
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_move_assign(_Rb_tree& __x)
+    operator=(_Rb_tree&& __x)
+    noexcept(_Alloc_traits::_S_nothrow_move())
     {
       _M_impl._M_key_compare = __x._M_impl._M_key_compare;
       if (_Alloc_traits::_S_propagate_on_move_assign()
@@ -1079,14 +1255,56 @@ 
 	  || _M_get_Node_allocator() == __x._M_get_Node_allocator())
 	{
 	  clear();
-	  if (__x._M_root() != 0)
+	  if (__x._M_root() != nullptr)
 	    _M_move_data(__x, std::true_type());
 	  std::__alloc_on_move(_M_get_Node_allocator(),
 			       __x._M_get_Node_allocator());
-	  return true;
+	  return *this;
 	}
-      return false;
+
+      // Try to move each node reusing existing nodes and copying __x nodes
+      // structure.
+      _Reuse_or_alloc_node __roan(_M_impl._M_header, *this);
+      _M_impl._M_reset();
+      if (__x._M_root() != nullptr)
+	{
+	  auto __lbd =
+	    [&__roan](value_type& __val)
+	    { return __roan(std::move_if_noexcept(__val)); };
+	  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
+	  _M_leftmost() = _S_minimum(_M_root());
+	  _M_rightmost() = _S_maximum(_M_root());
+	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  __x.clear();
+	}
+      return *this;
     }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename _Iterator>
+      void
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_assign_unique(_Iterator __first, _Iterator __last)
+      {
+	_Reuse_or_alloc_node __roan(this->_M_impl._M_header, *this);
+	_M_impl._M_reset();
+	for (; __first != __last; ++__first)
+	  _M_insert_unique_(end(), *__first, __roan);
+      }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename _Iterator>
+      void
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_assign_equal(_Iterator __first, _Iterator __last)
+      {
+	_Reuse_or_alloc_node __roan(this->_M_impl._M_header, *this);
+	_M_impl._M_reset();
+	for (; __first != __last; ++__first)
+	  _M_insert_equal_(end(), *__first, __roan);
+      }
 #endif
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1098,7 +1316,6 @@ 
       if (this != &__x)
 	{
 	  // Note that _Key may be a constant type.
-	  clear();
 #if __cplusplus >= 201103L
 	  if (_Alloc_traits::_S_propagate_on_copy_assign())
 	    {
@@ -1107,19 +1324,26 @@ 
 	      if (!_Alloc_traits::_S_always_equal()
 		  && __this_alloc != __that_alloc)
 		{
+		  // Replacement allocator cannot free existing storage, we need
+		  // to erase nodes first.
+		  clear();
 		  std::__alloc_on_copy(__this_alloc, __that_alloc);
 		}
 	    }
 #endif
+
+	  _Reuse_or_alloc_node __roan(this->_M_impl._M_header, *this);
+	  _M_impl._M_reset();
 	  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 	  if (__x._M_root() != 0)
 	    {
-	      _M_root() = _M_copy(__x._M_begin(), _M_end());
+	      _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
 	      _M_leftmost() = _S_minimum(_M_root());
 	      _M_rightmost() = _S_maximum(_M_root());
 	      _M_impl._M_node_count = __x._M_impl._M_node_count;
 	    }
 	}
+
       return *this;
     }
 
@@ -1126,27 +1350,31 @@ 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
 #if __cplusplus >= 201103L
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGen>
+#else
+    template<typename _NodeGen>
 #endif
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_insert_(_Base_ptr __x, _Base_ptr __p,
 #if __cplusplus >= 201103L
-    _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
+		 _Arg&& __v,
 #else
-    _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+		 const _Val& __v,
 #endif
-    {
-      bool __insert_left = (__x != 0 || __p == _M_end()
-			    || _M_impl._M_key_compare(_KeyOfValue()(__v),
-						      _S_key(__p)));
+		 _NodeGen& __node_gen)
+      {
+	bool __insert_left = (__x != 0 || __p == _M_end()
+			      || _M_impl._M_key_compare(_KeyOfValue()(__v),
+							_S_key(__p)));
 
-      _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
+	_Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
 
-      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
-				    this->_M_impl._M_header);
-      ++_M_impl._M_node_count;
-      return iterator(__z);
-    }
+	_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
+				      this->_M_impl._M_header);
+	++_M_impl._M_node_count;
+	return iterator(__z);
+      }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
@@ -1198,40 +1426,41 @@ 
     }
 
   template<typename _Key, typename _Val, typename _KoV,
-           typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
-    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
-    _M_copy(_Const_Link_type __x, _Link_type __p)
-    {
-      // Structural copy.  __x and __p must be non-null.
-      _Link_type __top = _M_clone_node(__x);
-      __top->_M_parent = __p;
+	   typename _Compare, typename _Alloc>
+    template<typename _NodeGen>
+      typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
+      _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
+      _M_copy(_Link_type __x, _Link_type __p, _NodeGen& __node_gen)
+      {
+	// Structural copy. __x and __p must be non-null.
+	_Link_type __top = _M_clone_node(__x, __node_gen);
+	__top->_M_parent = __p;
 
-      __try
-	{
-	  if (__x->_M_right)
-	    __top->_M_right = _M_copy(_S_right(__x), __top);
-	  __p = __top;
-	  __x = _S_left(__x);
+	__try
+	  {
+	    if (__x->_M_right)
+	      __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
+	    __p = __top;
+	    __x = _S_left(__x);
 
-	  while (__x != 0)
-	    {
-	      _Link_type __y = _M_clone_node(__x);
-	      __p->_M_left = __y;
-	      __y->_M_parent = __p;
-	      if (__x->_M_right)
-		__y->_M_right = _M_copy(_S_right(__x), __y);
-	      __p = __y;
-	      __x = _S_left(__x);
-	    }
-	}
-      __catch(...)
-	{
-	  _M_erase(__top);
-	  __throw_exception_again;
-	}
-      return __top;
-    }
+	    while (__x != 0)
+	      {
+		_Link_type __y = _M_clone_node(__x, __node_gen);
+		__p->_M_left = __y;
+		__y->_M_parent = __p;
+		if (__x->_M_right)
+		  __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
+		__p = __y;
+		__x = _S_left(__x);
+	      }
+	  }
+	__catch(...)
+	  {
+	    _M_erase(__top);
+	    __throw_exception_again;
+	  }
+	return __top;
+      }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
@@ -1244,7 +1473,7 @@ 
 	{
 	  _M_erase(_S_right(__x));
 	  _Link_type __y = _S_left(__x);
-	  _M_destroy_node(__x);
+	  _M_drop_node(__x);
 	  __x = __y;
 	}
     }
@@ -1353,8 +1582,8 @@ 
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     equal_range(const _Key& __k) const
     {
-      _Const_Link_type __x = _M_begin();
-      _Const_Link_type __y = _M_end();
+      _Const_Link_type __x = _M_cbegin();
+      _Const_Link_type __y = _M_cend();
       while (__x != 0)
 	{
 	  if (_M_impl._M_key_compare(_S_key(__x), __k))
@@ -1392,10 +1621,9 @@ 
 	      _M_leftmost() = __t._M_leftmost();
 	      _M_rightmost() = __t._M_rightmost();
 	      _M_root()->_M_parent = _M_end();
+	      _M_impl._M_node_count = __t._M_impl._M_node_count;
 	      
-	      __t._M_root() = 0;
-	      __t._M_leftmost() = __t._M_end();
-	      __t._M_rightmost() = __t._M_end();
+	      __t._M_impl._M_reset();
 	    }
 	}
       else if (__t._M_root() == 0)
@@ -1404,10 +1632,9 @@ 
 	  __t._M_leftmost() = _M_leftmost();
 	  __t._M_rightmost() = _M_rightmost();
 	  __t._M_root()->_M_parent = __t._M_end();
+	  __t._M_impl._M_node_count = _M_impl._M_node_count;
 	  
-	  _M_root() = 0;
-	  _M_leftmost() = _M_end();
-	  _M_rightmost() = _M_end();
+	  _M_impl._M_reset();
 	}
       else
 	{
@@ -1417,9 +1644,9 @@ 
 	  
 	  _M_root()->_M_parent = _M_end();
 	  __t._M_root()->_M_parent = __t._M_end();
+	  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
 	}
       // No need to swap header's color as it does not change.
-      std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
 
       _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
@@ -1498,9 +1725,12 @@ 
 	= _M_get_insert_unique_pos(_KeyOfValue()(__v));
 
       if (__res.second)
-	return _Res(_M_insert_(__res.first, __res.second,
-			       _GLIBCXX_FORWARD(_Arg, __v)),
-		    true);
+	{
+	  _Alloc_node __an(*this);
+	  return _Res(_M_insert_(__res.first, __res.second,
+				 _GLIBCXX_FORWARD(_Arg, __v), __an),
+		      true);
+	}
 
       return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
     }
@@ -1520,7 +1750,9 @@ 
     {
       pair<_Base_ptr, _Base_ptr> __res
 	= _M_get_insert_equal_pos(_KeyOfValue()(__v));
-      return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
+      _Alloc_node __an(*this);
+      return _M_insert_(__res.first, __res.second,
+			_GLIBCXX_FORWARD(_Arg, __v), __an);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1585,15 +1817,19 @@ 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
 #if __cplusplus >= 201103L
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGen>
+#else
+    template<typename _NodeGen>
 #endif
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_insert_unique_(const_iterator __position,
 #if __cplusplus >= 201103L
-    _M_insert_unique_(const_iterator __position, _Arg&& __v)
+			_Arg&& __v,
 #else
-    _M_insert_unique_(const_iterator __position, const _Val& __v)
+			const _Val& __v,
 #endif
+			_NodeGen& __node_gen)
     {
       pair<_Base_ptr, _Base_ptr> __res
 	= _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
@@ -1600,7 +1836,8 @@ 
 
       if (__res.second)
 	return _M_insert_(__res.first, __res.second,
-			  _GLIBCXX_FORWARD(_Arg, __v));
+			  _GLIBCXX_FORWARD(_Arg, __v),
+			  __node_gen);
       return iterator(static_cast<_Link_type>(__res.first));
     }
 
@@ -1662,25 +1899,30 @@ 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
 #if __cplusplus >= 201103L
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGen>
+#else
+    template<typename _NodeGen>
 #endif
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_insert_equal_(const_iterator __position,
 #if __cplusplus >= 201103L
-    _M_insert_equal_(const_iterator __position, _Arg&& __v)
+		       _Arg&& __v,
 #else
-    _M_insert_equal_(const_iterator __position, const _Val& __v)
+		       const _Val& __v,
 #endif
-    {
-      pair<_Base_ptr, _Base_ptr> __res
-	= _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
+		       _NodeGen& __node_gen)
+      {
+	pair<_Base_ptr, _Base_ptr> __res
+	  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
 
-      if (__res.second)
-	return _M_insert_(__res.first, __res.second,
-			  _GLIBCXX_FORWARD(_Arg, __v));
+	if (__res.second)
+	  return _M_insert_(__res.first, __res.second,
+			    _GLIBCXX_FORWARD(_Arg, __v),
+			    __node_gen);
 
-      return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
-    }
+	return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
+      }
 
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1749,12 +1991,12 @@ 
 	    if (__res.second)
 	      return _Res(_M_insert_node(__res.first, __res.second, __z), true);
 	
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1775,7 +2017,7 @@ 
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1796,12 +2038,12 @@ 
 	    if (__res.second)
 	      return _M_insert_node(__res.first, __res.second, __z);
 
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    return iterator(static_cast<_Link_type>(__res.first));
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1826,7 +2068,7 @@ 
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1839,8 +2081,9 @@ 
       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
       _M_insert_unique(_II __first, _II __last)
       {
+	_Alloc_node __an(*this);
 	for (; __first != __last; ++__first)
-	  _M_insert_unique_(end(), *__first);
+	  _M_insert_unique_(end(), *__first, __an);
       }
 
   template<typename _Key, typename _Val, typename _KoV,
@@ -1850,8 +2093,9 @@ 
       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
       _M_insert_equal(_II __first, _II __last)
       {
+	_Alloc_node __an(*this);
 	for (; __first != __last; ++__first)
-	  _M_insert_equal_(end(), *__first);
+	  _M_insert_equal_(end(), *__first, __an);
       }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1864,7 +2108,7 @@ 
 	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
 				(const_cast<_Base_ptr>(__position._M_node),
 				 this->_M_impl._M_header));
-      _M_destroy_node(__y);
+      _M_drop_node(__y);
       --_M_impl._M_node_count;
     }
 
@@ -1923,7 +2167,7 @@ 
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     find(const _Key& __k) const
     {
-      const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
+      const_iterator __j = _M_lower_bound(_M_cbegin(), _M_cend(), __k);
       return (__j == end()
 	      || _M_impl._M_key_compare(__k, 
 					_S_key(__j._M_node))) ? end() : __j;
Index: testsuite/23_containers/map/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/map/allocator/copy_assign.cc	(revision 211713)
+++ testsuite/23_containers/map/allocator/copy_assign.cc	(working copy)
@@ -59,9 +59,33 @@ 
   VERIFY(1 == v2.get_allocator().get_personality());
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+  typedef std::map<int, int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1 = { { 0, 0 }, { 1, 1 } };
+  test_type v2 = { { 2, 2 }, { 3, 3 } };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  v1 = v2;
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }
Index: testsuite/23_containers/map/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/map/allocator/init-list.cc	(revision 0)
+++ testsuite/23_containers/map/allocator/init-list.cc	(working copy)
@@ -0,0 +1,55 @@ 
+// Copyright (C) 2014 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=gnu++11" }
+
+#include <map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+  typedef std::map<int, int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1;
+  v1 = { { 0, 0 }, { 1, 1 } };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  VERIFY( allocs != 0 );
+  VERIFY( constructs != 0 );
+
+  // Check no allocation on list initialization.
+  v1 = { { 4, 4 }, { 5, 5 } };
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+  test01();
+}
Index: testsuite/23_containers/map/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/map/allocator/move_assign.cc	(revision 211713)
+++ testsuite/23_containers/map/allocator/move_assign.cc	(working copy)
@@ -43,8 +43,8 @@ 
   v2 = { test_type::value_type{} };
   v2 = std::move(v1);
 
-  VERIFY(1 == v1.get_allocator().get_personality());
-  VERIFY(2 == v2.get_allocator().get_personality());
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
 }
 
 void test02()
@@ -60,14 +60,47 @@ 
   v2 = { test_type::value_type{} };
   v2 = std::move(v1);
 
-  VERIFY(0 == v1.get_allocator().get_personality());
-  VERIFY(1 == v2.get_allocator().get_personality());
+  VERIFY( 0 == v1.get_allocator().get_personality() );
+  VERIFY( 1 == v2.get_allocator().get_personality() );
   VERIFY( it == v2.begin() );
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef propagating_allocator<std::pair<const int, int>, false,
+				tracker_allocator<std::pair<const int, int>>>
+    alloc_type;
+  typedef std::map<int, int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1(alloc_type(1));
+  v1 = { { 0, 0 }, { 1, 1 } };
+
+  test_type v2(alloc_type(2));
+  v2 = { { 2, 2 }, { 3, 3 } };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  // Check no allocation on move assignment with non propagating allocators.
+  v1 = std::move(v2);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }
Index: testsuite/util/testsuite_allocator.h
===================================================================
--- testsuite/util/testsuite_allocator.h	(revision 211713)
+++ testsuite/util/testsuite_allocator.h	(working copy)
@@ -29,6 +29,7 @@ 
 #include <tr1/unordered_map>
 #include <bits/move.h>
 #include <ext/pointer.h>
+#include <ext/alloc_traits.h>
 #include <testsuite_hooks.h>
 
 namespace __gnu_test
@@ -91,87 +92,87 @@ 
   // tracker_allocator_counter to fulfill memory requests.  This class
   // is templated on the target object type, but tracker isn't.
   template<class T>
-  class tracker_allocator
-  {
-  private:
-    typedef tracker_allocator_counter counter_type;
+    class tracker_allocator
+    {
+    private:
+      typedef tracker_allocator_counter counter_type;
 
-  public:
-    typedef T              value_type;
-    typedef T*             pointer;
-    typedef const T*       const_pointer;
-    typedef T&             reference;
-    typedef const T&       const_reference;
-    typedef std::size_t    size_type; 
-    typedef std::ptrdiff_t difference_type; 
+    public:
+      typedef T              value_type;
+      typedef T*             pointer;
+      typedef const T*       const_pointer;
+      typedef T&             reference;
+      typedef const T&       const_reference;
+      typedef std::size_t    size_type; 
+      typedef std::ptrdiff_t difference_type; 
     
-    template<class U> struct rebind { typedef tracker_allocator<U> other; };
+      template<class U> struct rebind { typedef tracker_allocator<U> other; };
     
-    pointer
-    address(reference value) const _GLIBCXX_NOEXCEPT
-    { return std::__addressof(value); }
+      pointer
+      address(reference value) const _GLIBCXX_NOEXCEPT
+      { return std::__addressof(value); }
 
-    const_pointer
-    address(const_reference value) const _GLIBCXX_NOEXCEPT
-    { return std::__addressof(value); }
+      const_pointer
+      address(const_reference value) const _GLIBCXX_NOEXCEPT
+      { return std::__addressof(value); }
 
-    tracker_allocator() _GLIBCXX_USE_NOEXCEPT
-    { }
+      tracker_allocator() _GLIBCXX_USE_NOEXCEPT
+      { }
 
-    tracker_allocator(const tracker_allocator&) _GLIBCXX_USE_NOEXCEPT
-    { }
+      tracker_allocator(const tracker_allocator&) _GLIBCXX_USE_NOEXCEPT
+      { }
 
-    template<class U>
-      tracker_allocator(const tracker_allocator<U>&) _GLIBCXX_USE_NOEXCEPT
+      template<class U>
+	tracker_allocator(const tracker_allocator<U>&) _GLIBCXX_USE_NOEXCEPT
+	{ }
+
+      ~tracker_allocator() _GLIBCXX_USE_NOEXCEPT
       { }
 
-    ~tracker_allocator() _GLIBCXX_USE_NOEXCEPT
-    { }
+      size_type
+      max_size() const _GLIBCXX_USE_NOEXCEPT
+      { return size_type(-1) / sizeof(T); }
 
-    size_type
-    max_size() const _GLIBCXX_USE_NOEXCEPT
-    { return size_type(-1) / sizeof(T); }
+      pointer
+      allocate(size_type n, const void* = 0)
+      { return static_cast<pointer>(counter_type::allocate(n * sizeof(T))); }
 
-    pointer
-    allocate(size_type n, const void* = 0)
-    { return static_cast<pointer>(counter_type::allocate(n * sizeof(T))); }
+#if __cplusplus >= 201103L
+      template<typename U, typename... Args>
+	void
+	construct(U* p, Args&&... args) 
+	{
+	  ::new((void *)p) U(std::forward<Args>(args)...);
+	  counter_type::construct();
+	}
 
-#if __cplusplus >= 201103L
-    template<typename U, typename... Args>
+      template<typename U>
+	void
+	destroy(U* p)
+	{
+	  p->~U();
+	  counter_type::destroy();
+	}
+#else
       void
-      construct(U* p, Args&&... args) 
+      construct(pointer p, const T& value)
       {
-	::new((void *)p) U(std::forward<Args>(args)...);
+	::new ((void *)p) T(value);
 	counter_type::construct();
       }
 
-    template<typename U>
       void
-      destroy(U* p)
+      destroy(pointer p)
       {
-	p->~U();
+	p->~T();
 	counter_type::destroy();
       }
-#else
-    void
-    construct(pointer p, const T& value)
-    {
-      ::new ((void *)p) T(value);
-      counter_type::construct();
-    }
-
-    void
-    destroy(pointer p)
-    {
-      p->~T();
-      counter_type::destroy();
-    }
 #endif
 
-    void
-    deallocate(pointer p, size_type num)
-    { counter_type::deallocate(p, num * sizeof(T)); }
-  };
+      void
+      deallocate(pointer p, size_type num)
+      { counter_type::deallocate(p, num * sizeof(T)); }
+    };
 
   template<class T1, class T2>
     bool
@@ -219,7 +220,16 @@ 
       throw;
     }
 
+  // Helper to detect inconsistency between type used to instantiate an
+  // allocator and the underlying allocator value_type.
+  template<typename T, typename Alloc,
+	   typename = typename Alloc::value_type>
+    struct check_consistent_alloc_value_type;
 
+  template<typename T, typename Alloc>
+    struct check_consistent_alloc_value_type<T, Alloc, T>
+    { typedef T value_type; };
+
   // A simple allocator which can be constructed endowed of a given
   // "personality" (an integer), queried in operator== to simulate the
   // behavior of realworld "unequal" allocators (i.e., not exploiting
@@ -244,26 +254,29 @@ 
     }
   };
 
-  template<typename Tp>
+  template<typename Tp, typename Alloc = std::allocator<Tp> >
     class uneq_allocator
-    : private uneq_allocator_base
+    : private uneq_allocator_base,
+      public Alloc
     {
+      typedef __gnu_cxx::__alloc_traits<Alloc> AllocTraits;
+
     public:
-      typedef std::size_t                         size_type;
-      typedef std::ptrdiff_t                      difference_type;
-      typedef Tp*                                 pointer;
-      typedef const Tp*                           const_pointer;
-      typedef Tp&                                 reference;
-      typedef const Tp&                           const_reference;
-      typedef Tp                                  value_type;
+      typedef typename check_consistent_alloc_value_type<Tp, Alloc>::value_type
+	value_type;
+      typedef typename AllocTraits::size_type	size_type;
+      typedef typename AllocTraits::pointer	pointer;
 
 #if __cplusplus >= 201103L
-      typedef std::true_type                      propagate_on_container_swap;
+      typedef std::true_type			propagate_on_container_swap;
 #endif
 
       template<typename Tp1>
-        struct rebind
-	{ typedef uneq_allocator<Tp1> other; };
+	struct rebind
+	{
+	  typedef uneq_allocator<Tp1,
+			typename AllocTraits::template rebind<Tp1>::other> other;
+	};
 
       uneq_allocator() _GLIBCXX_USE_NOEXCEPT
       : personality(0) { }
@@ -272,7 +285,9 @@ 
       : personality(person) { }
       
       template<typename Tp1>
-        uneq_allocator(const uneq_allocator<Tp1>& b) _GLIBCXX_USE_NOEXCEPT
+	uneq_allocator(const uneq_allocator<Tp1,
+		       typename AllocTraits::template rebind<Tp1>::other>& b)
+	_GLIBCXX_USE_NOEXCEPT
 	: personality(b.get_personality()) { }
 
       ~uneq_allocator() _GLIBCXX_USE_NOEXCEPT
@@ -281,20 +296,9 @@ 
       int get_personality() const { return personality; }
       
       pointer
-      address(reference x) const _GLIBCXX_NOEXCEPT
-      { return std::__addressof(x); }
-    
-      const_pointer
-      address(const_reference x) const _GLIBCXX_NOEXCEPT
-      { return std::__addressof(x); }
-
-      pointer
-      allocate(size_type n, const void* = 0)
+      allocate(size_type n, const void* hint = 0)
       { 
-	if (__builtin_expect(n > this->max_size(), false))
-	  std::__throw_bad_alloc();
-	
-	pointer p = static_cast<Tp*>(::operator new(n * sizeof(Tp)));
+	pointer p = Alloc::allocate(n, hint);
 	try
 	  {
 	    get_map().insert(map_type::value_type(reinterpret_cast<void*>(p),
@@ -302,7 +306,7 @@ 
 	  }
 	catch(...)
 	  {
-	    ::operator delete(p);
+	    Alloc::deallocate(p, n);
 	    __throw_exception_again;
 	  }
 	return p;
@@ -309,7 +313,7 @@ 
       }
 
       void
-      deallocate(pointer p, size_type)
+      deallocate(pointer p, size_type n)
       {
 	bool test __attribute__((unused)) = true;
 
@@ -323,34 +327,14 @@ 
 	VERIFY( it->second == personality );
 
 	get_map().erase(it);
-	::operator delete(p);
+	Alloc::deallocate(p, n);
       }
 
-      size_type
-      max_size() const _GLIBCXX_USE_NOEXCEPT 
-      { return size_type(-1) / sizeof(Tp); }
-
 #if __cplusplus >= 201103L
-      template<typename U, typename... Args>
-        void
-        construct(U* p, Args&&... args) 
-	{ ::new((void *)p) U(std::forward<Args>(args)...); }
-
-      template<typename U>
-	void 
-	destroy(U* p) { p->~U(); }
-
       // Not copy assignable...
       uneq_allocator&
       operator=(const uneq_allocator&) = delete;
 #else
-      void 
-      construct(pointer p, const Tp& val) 
-      { ::new((void *)p) Tp(val); }
-
-      void 
-      destroy(pointer p) { p->~Tp(); }
-
     private:
       // Not assignable...
       uneq_allocator&
@@ -358,21 +342,24 @@ 
 #endif
 
     private:
-
       // ... yet swappable!
       friend inline void
       swap(uneq_allocator& a, uneq_allocator& b)
       { std::swap(a.personality, b.personality); } 
-      
+
       template<typename Tp1>
-        friend inline bool
-        operator==(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
-        { return a.personality == b.personality; }
+	friend inline bool
+	operator==(const uneq_allocator& a,
+		   const uneq_allocator<Tp1,
+		   typename AllocTraits::template rebind<Tp1>::other>& b)
+	{ return a.personality == b.personality; }
 
       template<typename Tp1>
-        friend inline bool
-        operator!=(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
-        { return !(a == b); }
+	friend inline bool
+	operator!=(const uneq_allocator& a,
+		   const uneq_allocator<Tp1,
+		   typename AllocTraits::template rebind<Tp1>::other>& b)
+	{ return !(a == b); }
       
       int personality;
     };
@@ -379,10 +366,12 @@ 
 
 #if __cplusplus >= 201103L
   // An uneq_allocator which can be used to test allocator propagation.
-  template<typename Tp, bool Propagate>
-    class propagating_allocator : public uneq_allocator<Tp>
+  template<typename Tp, bool Propagate, typename Alloc = std::allocator<Tp>>
+    class propagating_allocator : public uneq_allocator<Tp, Alloc>
     {
-      typedef uneq_allocator<Tp> base_alloc;
+      typedef __gnu_cxx::__alloc_traits<Alloc> AllocTraits;
+
+      typedef uneq_allocator<Tp, Alloc> base_alloc;
       base_alloc& base() { return *this; }
       const base_alloc& base() const  { return *this; }
       void swap_base(base_alloc& b) { swap(b, this->base()); }
@@ -393,7 +382,11 @@ 
       // default allocator_traits::rebind_alloc would select
       // uneq_allocator::rebind so we must define rebind here
       template<typename Up>
-	struct rebind { typedef propagating_allocator<Up, Propagate> other; };
+	struct rebind
+	{
+	  typedef propagating_allocator<Up, Propagate,
+		typename AllocTraits::template rebind<Up>::other> other;
+	};
 
       propagating_allocator(int i) noexcept
       : base_alloc(i)
@@ -400,8 +393,9 @@ 
       { }
 
       template<typename Up>
-	propagating_allocator(const propagating_allocator<Up, Propagate>& a)
-       	noexcept
+	propagating_allocator(const propagating_allocator<Up, Propagate,
+			      typename AllocTraits::template rebind<Up>::other>& a)
+	noexcept
 	: base_alloc(a)
 	{ }
 
@@ -418,8 +412,8 @@ 
       }
 
       template<bool P2>
-  	propagating_allocator&
-  	operator=(const propagating_allocator<Tp, P2>& a) noexcept
+	propagating_allocator&
+	operator=(const propagating_allocator<Tp, P2, Alloc>& a) noexcept
   	{
 	  static_assert(P2, "assigning propagating_allocator<T, true>");
 	  propagating_allocator(a).swap_base(*this);
Index: testsuite/23_containers/set/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/set/allocator/copy_assign.cc	(revision 211713)
+++ testsuite/23_containers/set/allocator/copy_assign.cc	(working copy)
@@ -57,9 +57,33 @@ 
   VERIFY(1 == v2.get_allocator().get_personality());
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<int> alloc_type;
+  typedef std::set<int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1 = { 0, 1 };
+  test_type v2 = { 2, 3 };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  v1 = v2;
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }
Index: testsuite/23_containers/set/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/set/allocator/init-list.cc	(revision 0)
+++ testsuite/23_containers/set/allocator/init-list.cc	(working copy)
@@ -0,0 +1,55 @@ 
+// Copyright (C) 2014 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=gnu++11" }
+
+#include <set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<int> alloc_type;
+  typedef std::set<int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1;
+  v1 = { 0, 1 };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  VERIFY( allocs != 0 );
+  VERIFY( constructs != 0 );
+
+  // Check no allocation on list initialization.
+  v1 = { 4, 5 };
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+  test01();
+}
Index: testsuite/23_containers/set/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/set/allocator/move_assign.cc	(revision 211713)
+++ testsuite/23_containers/set/allocator/move_assign.cc	(working copy)
@@ -59,9 +59,40 @@ 
   VERIFY( it == v2.begin() );
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef propagating_allocator<int, false, tracker_allocator<int>> alloc_type;
+  typedef std::set<int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1(alloc_type(1));
+  v1 = { 0, 1 };
+
+  test_type v2(alloc_type(2));
+  v2 = { 2, 3 };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  // Check no allocation on move assignment with non propagating allocators.
+  v1 = std::move(v2);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }
Index: testsuite/23_containers/multimap/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/multimap/allocator/copy_assign.cc	(revision 211713)
+++ testsuite/23_containers/multimap/allocator/copy_assign.cc	(working copy)
@@ -59,9 +59,33 @@ 
   VERIFY(1 == v2.get_allocator().get_personality());
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+  typedef std::multimap<int, int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1 = { { 1, 1 }, { 1, 1 } };
+  test_type v2 = { { 2, 2 }, { 2, 2 } };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  v1 = v2;
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }
Index: testsuite/23_containers/multimap/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/multimap/allocator/init-list.cc	(revision 0)
+++ testsuite/23_containers/multimap/allocator/init-list.cc	(working copy)
@@ -0,0 +1,55 @@ 
+// Copyright (C) 2014 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=gnu++11" }
+
+#include <map>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<std::pair<const int, int>> alloc_type;
+  typedef std::multimap<int, int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1;
+  v1 = { { 0, 0 }, { 0, 0 } };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  VERIFY( allocs != 0 );
+  VERIFY( constructs != 0 );
+
+  // Check no allocation on list initialization.
+  v1 = { { 1, 1 }, { 1, 1 } };
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+  test01();
+}
Index: testsuite/23_containers/multimap/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/multimap/allocator/move_assign.cc	(revision 211713)
+++ testsuite/23_containers/multimap/allocator/move_assign.cc	(working copy)
@@ -61,9 +61,42 @@ 
   VERIFY( it == v2.begin()  );
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef propagating_allocator<std::pair<const int, int>, false,
+				tracker_allocator<std::pair<const int, int>>>
+    alloc_type;
+  typedef std::multimap<int, int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1(alloc_type(1));
+  v1 = { { 1, 1 }, { 1, 1 } };
+
+  test_type v2(alloc_type(2));
+  v2 = { { 2, 2 }, { 2, 2 } };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  // Check no allocation on move assignment with non propagating allocators.
+  v1 = std::move(v2);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }
Index: testsuite/23_containers/multiset/allocator/copy_assign.cc
===================================================================
--- testsuite/23_containers/multiset/allocator/copy_assign.cc	(revision 211713)
+++ testsuite/23_containers/multiset/allocator/copy_assign.cc	(working copy)
@@ -57,9 +57,33 @@ 
   VERIFY(1 == v2.get_allocator().get_personality());
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<int> alloc_type;
+  typedef std::multiset<int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1 = { 0, 0 };
+  test_type v2 = { 1, 1 };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  v1 = v2;
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }
Index: testsuite/23_containers/multiset/allocator/init-list.cc
===================================================================
--- testsuite/23_containers/multiset/allocator/init-list.cc	(revision 0)
+++ testsuite/23_containers/multiset/allocator/init-list.cc	(working copy)
@@ -0,0 +1,55 @@ 
+// Copyright (C) 2014 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=gnu++11" }
+
+#include <set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef tracker_allocator<int> alloc_type;
+  typedef std::multiset<int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1;
+  v1 = { 0, 0 };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  VERIFY( allocs != 0 );
+  VERIFY( constructs != 0 );
+
+  // Check no allocation on list initialization.
+  v1 = { 1, 1 };
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
+int main()
+{
+  test01();
+}
Index: testsuite/23_containers/multiset/allocator/move_assign.cc
===================================================================
--- testsuite/23_containers/multiset/allocator/move_assign.cc	(revision 211713)
+++ testsuite/23_containers/multiset/allocator/move_assign.cc	(working copy)
@@ -59,9 +59,40 @@ 
   VERIFY( it == v2.begin() );
 }
 
+void test03()
+{
+  bool test __attribute__((unused)) = true;
+
+  using namespace __gnu_test;
+
+  typedef propagating_allocator<int, false, tracker_allocator<int>> alloc_type;
+  typedef std::multiset<int, std::less<int>, alloc_type> test_type;
+
+  tracker_allocator_counter::reset();
+
+  test_type v1(alloc_type(1));
+  v1 = { 0, 0 };
+
+  test_type v2(alloc_type(2));
+  v2 = { 2, 2 };
+
+  auto allocs = tracker_allocator_counter::get_allocation_count();
+  auto constructs = tracker_allocator_counter::get_construct_count();
+
+  // Check no allocation on move assignment with non propagating allocators.
+  v1 = std::move(v2);
+
+  VERIFY( 1 == v1.get_allocator().get_personality() );
+  VERIFY( 2 == v2.get_allocator().get_personality() );
+
+  VERIFY( tracker_allocator_counter::get_allocation_count() == allocs );
+  VERIFY( tracker_allocator_counter::get_construct_count() == constructs + 2 );
+}
+
 int main()
 {
   test01();
   test02();
+  test03();
   return 0;
 }