stl_construct.h (_Destroy): New three-argument overload that takes an allocator argument.

	* include/bits/stl_construct.h (_Destroy): New three-argument
	overload that takes an allocator argument.  Another inline
	three-argument overload that takes std::allocator and dispatches
	to the two-argument version.
	* include/bits/stl_uninitialized.h (__uninitialized_fill_n_aux):
	Change return type to void to match uninitialized_fill_n.
	(__uninitialized_copy_a_): New function.  Like uninitialized_copy
	except that it takes an allocator and uses it for construct and
	destroy.  If the allocator is std::allocator, dispatches to
	uninitialized_copy.
	(__uninitialized_fill_a): Likewise.
	(__uninitialized_fill_n_a): Likewise.
	(__uninitialized_copy_copy): Give it an allocator argument.
	(__uninitialized_fill_copy): Likewise.
	(__uninitialized_copy_fill): Likewise.
	* include/bits/deque.tcc: Use new forms defined in stl_construct.h
	and stl_uninitialized.h.  Replace use of single-argument _Construct
	and _Destroy with use of allocator's construct and destroy methods.
	* include/bits/list.tcc: Likewise.
	* include/bits/stl_deque.h: Likewise.
	* include/bits/stl_list.h: Likewise.
	* include/bits/stl_tree.h: Likewise.
	* include/bits/stl_vector.h: Likewise.
	* include/bits/vector.tcc: Likewise.
	* include/ext/hashtable.h: Use rebind so that allocator_type
	has correct type for a container's allocator.  Replace use of
	single-argument _Construct and _Destroy with use of allocator's
	construct and destroy methods.
	* include/ext/memory (__uninitialized_copy_n_a): New function.
	Like uninitialized_copy_n except that it takes an extra parameter,
	an allocator, and uses it for construct and destroy operations.
	* include/ext/rope: Use new forms defined in stl_construct.h,
	stl_uninitialized.h, and ext/memory.  Replace use of single-argument
	_Construct and _Destroy with allocator construct and destroy methods.
	* include/ext/ropeimpl.h: Likewise.
	* include/ext/slist.h: Likewise.
	* testsuite/testsuite_allocator.h (check_construct_destroy): New.
	* testsuite/testsuite_allocator.cc (check_construct_destroy): New.
	* testsuite/23_containers/deque/check_construct_destroy.cc: New.
	* testsuite/23_containers/list/check_construct_destroy.cc: New.
	* testsuite/23_containers/set/check_construct_destroy.cc: New.
	* testsuite/23_containers/vector/check_construct_destroy.cc: New.
	* testsuite/ext/hash_check_construct_destroy.cc: New.
	* testsuite/ext/slist_check_construct_destroy.cc: New.

From-SVN: r85265

23 files changed, 977 insertions, 169 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index aed1079..124f514 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,50 @@
+2004-07-28  Matt Austern  <austern@apple.com>
+
+	* include/bits/stl_construct.h (_Destroy): New three-argument
+	overload that takes an allocator argument.  Another inline
+	three-argument overload that takes std::allocator and dispatches
+	to the two-argument version.
+	* include/bits/stl_uninitialized.h (__uninitialized_fill_n_aux):
+	Change return type to void to match uninitialized_fill_n.
+	(__uninitialized_copy_a_): New function.  Like uninitialized_copy
+	except that it takes an allocator and uses it for construct and
+	destroy.  If the allocator is std::allocator, dispatches to
+	uninitialized_copy.
+	(__uninitialized_fill_a): Likewise.
+	(__uninitialized_fill_n_a): Likewise.
+	(__uninitialized_copy_copy): Give it an allocator argument.
+	(__uninitialized_fill_copy): Likewise.
+	(__uninitialized_copy_fill): Likewise.
+	* include/bits/deque.tcc: Use new forms defined in stl_construct.h
+	and stl_uninitialized.h.  Replace use of single-argument _Construct
+	and _Destroy with use of allocator's construct and destroy methods.
+	* include/bits/list.tcc: Likewise.
+	* include/bits/stl_deque.h: Likewise.
+	* include/bits/stl_list.h: Likewise.
+	* include/bits/stl_tree.h: Likewise.
+	* include/bits/stl_vector.h: Likewise.
+	* include/bits/vector.tcc: Likewise.
+	* include/ext/hashtable.h: Use rebind so that allocator_type
+	has correct type for a container's allocator.  Replace use of 
+	single-argument _Construct and _Destroy with use of allocator's 
+	construct and destroy methods.
+	* include/ext/memory (__uninitialized_copy_n_a): New function.
+	Like uninitialized_copy_n except that it takes an extra parameter,
+	an allocator, and uses it for construct and destroy operations.
+	* include/ext/rope: Use new forms defined in stl_construct.h,
+	stl_uninitialized.h, and ext/memory.  Replace use of single-argument 
+	_Construct and _Destroy with allocator construct and destroy methods.
+	* include/ext/ropeimpl.h: Likewise.
+	* include/ext/slist.h: Likewise.
+	* testsuite/testsuite_allocator.h (check_construct_destroy): New.
+	* testsuite/testsuite_allocator.cc (check_construct_destroy): New.
+	* testsuite/23_containers/deque/check_construct_destroy.cc: New.
+	* testsuite/23_containers/list/check_construct_destroy.cc: New.
+	* testsuite/23_containers/set/check_construct_destroy.cc: New.	
+	* testsuite/23_containers/vector/check_construct_destroy.cc: New. 
+	* testsuite/ext/hash_check_construct_destroy.cc
+	* testsuite/ext/slist_check_construct_destroy.cc
+	
 2004-07-28  Alexandre Oliva  <aoliva@redhat.com>
 
 	2003-10-01  Eric Christopher  <echristo@redhat.com>
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index dda81bf..6b87c3b 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -146,7 +146,8 @@ namespace _GLIBCXX_STD
 	    {
 	      std::copy_backward(this->_M_impl._M_start, __first, __last);
 	      iterator __new_start = this->_M_impl._M_start + __n;
-	      std::_Destroy(this->_M_impl._M_start, __new_start);
+	      std::_Destroy(this->_M_impl._M_start, __new_start,
+			    this->get_allocator());
 	      _M_destroy_nodes(this->_M_impl._M_start._M_node,
 			       __new_start._M_node);
 	      this->_M_impl._M_start = __new_start;
@@ -155,7 +156,8 @@ namespace _GLIBCXX_STD
 	    {
 	      std::copy(__last, this->_M_impl._M_finish, __first);
 	      iterator __new_finish = this->_M_impl._M_finish - __n;
-	      std::_Destroy(__new_finish, this->_M_impl._M_finish);
+	      std::_Destroy(__new_finish, this->_M_impl._M_finish,
+			    this->get_allocator());
 	      _M_destroy_nodes(__new_finish._M_node + 1,
 			       this->_M_impl._M_finish._M_node + 1);
 	      this->_M_impl._M_finish = __new_finish;
@@ -173,21 +175,25 @@ namespace _GLIBCXX_STD
            __node < this->_M_impl._M_finish._M_node;
            ++__node)
 	{
-	  std::_Destroy(*__node, *__node + _S_buffer_size());
+	  std::_Destroy(*__node, *__node + _S_buffer_size(),
+			this->get_allocator());
 	  _M_deallocate_node(*__node);
 	}
 
       if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node)
 	{
 	  std::_Destroy(this->_M_impl._M_start._M_cur,
-			this->_M_impl._M_start._M_last);
+			this->_M_impl._M_start._M_last,
+			this->get_allocator());
 	  std::_Destroy(this->_M_impl._M_finish._M_first,
-			this->_M_impl._M_finish._M_cur);
+			this->_M_impl._M_finish._M_cur,
+			this->get_allocator());
 	  _M_deallocate_node(this->_M_impl._M_finish._M_first);
 	}
       else
         std::_Destroy(this->_M_impl._M_start._M_cur,
-		      this->_M_impl._M_finish._M_cur);
+		      this->_M_impl._M_finish._M_cur,
+		      this->get_allocator());
 
       this->_M_impl._M_finish = this->_M_impl._M_start;
     }
@@ -218,7 +224,9 @@ namespace _GLIBCXX_STD
 	  iterator __new_start = _M_reserve_elements_at_front(__n);
 	  try
 	    {
-	      std::uninitialized_fill(__new_start, this->_M_impl._M_start, __x);
+	      std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
+					  __x,
+					  this->get_allocator());
 	      this->_M_impl._M_start = __new_start;
 	    }
 	  catch(...)
@@ -233,8 +241,9 @@ namespace _GLIBCXX_STD
 	  iterator __new_finish = _M_reserve_elements_at_back(__n);
 	  try
 	    {
-	      std::uninitialized_fill(this->_M_impl._M_finish,
-				      __new_finish, __x);
+	      std::__uninitialized_fill_a(this->_M_impl._M_finish,
+					  __new_finish, __x,
+					  this->get_allocator());
 	      this->_M_impl._M_finish = __new_finish;
 	    }
 	  catch(...)
@@ -259,14 +268,17 @@ namespace _GLIBCXX_STD
           for (__cur = this->_M_impl._M_start._M_node;
 	       __cur < this->_M_impl._M_finish._M_node;
 	       ++__cur)
-            std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
-          std::uninitialized_fill(this->_M_impl._M_finish._M_first,
-				  this->_M_impl._M_finish._M_cur,
-				  __value);
+            std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), __value,
+					this->get_allocator());
+          std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
+				      this->_M_impl._M_finish._M_cur,
+				      __value,
+				      this->get_allocator());
         }
       catch(...)
         {
-          std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur));
+          std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
+			this->get_allocator());
           __throw_exception_again;
         }
     }
@@ -310,16 +322,19 @@ namespace _GLIBCXX_STD
             {
               _ForwardIterator __mid = __first;
               std::advance(__mid, _S_buffer_size());
-              std::uninitialized_copy(__first, __mid, *__cur_node);
+              std::__uninitialized_copy_a(__first, __mid, *__cur_node,
+					  this->get_allocator());
               __first = __mid;
             }
-            std::uninitialized_copy(__first, __last,
-				    this->_M_impl._M_finish._M_first);
+            std::__uninitialized_copy_a(__first, __last,
+					this->_M_impl._M_finish._M_first,
+					this->get_allocator());
           }
         catch(...)
           {
             std::_Destroy(this->_M_impl._M_start,
-			  iterator(*__cur_node, __cur_node));
+			  iterator(*__cur_node, __cur_node),
+			  this->get_allocator());
             __throw_exception_again;
           }
       }
@@ -335,7 +350,7 @@ namespace _GLIBCXX_STD
       *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
       try
         {
-          std::_Construct(this->_M_impl._M_finish._M_cur, __t_copy);
+          this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy);
           this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 					      + 1);
           this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
@@ -361,7 +376,7 @@ namespace _GLIBCXX_STD
           this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
 					     - 1);
           this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
-          std::_Construct(this->_M_impl._M_start._M_cur, __t_copy);
+          this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy);
         }
       catch(...)
         {
@@ -379,7 +394,7 @@ namespace _GLIBCXX_STD
       _M_deallocate_node(this->_M_impl._M_finish._M_first);
       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
-      std::_Destroy(this->_M_impl._M_finish._M_cur);
+      this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
     }
 
   // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
@@ -391,7 +406,7 @@ namespace _GLIBCXX_STD
     void deque<_Tp, _Alloc>::
     _M_pop_front_aux()
     {
-      std::_Destroy(this->_M_impl._M_start._M_cur);
+      this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
       _M_deallocate_node(this->_M_impl._M_start._M_first);
       this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
       this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
@@ -420,7 +435,8 @@ namespace _GLIBCXX_STD
 	    iterator __new_start = _M_reserve_elements_at_front(__n);
 	    try
 	      {
-		std::uninitialized_copy(__first, __last, __new_start);
+		std::__uninitialized_copy_a(__first, __last, __new_start,
+					    this->get_allocator());
 		this->_M_impl._M_start = __new_start;
 	      }
 	    catch(...)
@@ -435,8 +451,9 @@ namespace _GLIBCXX_STD
 	    iterator __new_finish = _M_reserve_elements_at_back(__n);
 	    try
 	      {
-		std::uninitialized_copy(__first, __last,
-					this->_M_impl._M_finish);
+		std::__uninitialized_copy_a(__first, __last,
+					    this->_M_impl._M_finish,
+					    this->get_allocator());
 		this->_M_impl._M_finish = __new_finish;
 	      }
 	    catch(...)
@@ -502,8 +519,9 @@ namespace _GLIBCXX_STD
 		{
 		  iterator __start_n = (this->_M_impl._M_start
 					+ difference_type(__n));
-		  std::uninitialized_copy(this->_M_impl._M_start, __start_n,
-					  __new_start);
+		  std::__uninitialized_copy_a(this->_M_impl._M_start, __start_n,
+					      __new_start,
+					      this->get_allocator());
 		  this->_M_impl._M_start = __new_start;
 		  std::copy(__start_n, __pos, __old_start);
 		  fill(__pos - difference_type(__n), __pos, __x_copy);
@@ -513,7 +531,8 @@ namespace _GLIBCXX_STD
 		  std::__uninitialized_copy_fill(this->_M_impl._M_start,
 						 __pos, __new_start,
 						 this->_M_impl._M_start,
-						 __x_copy);
+						 __x_copy,
+						 this->get_allocator());
 		  this->_M_impl._M_start = __new_start;
 		  std::fill(__old_start, __pos, __x_copy);
 		}
@@ -538,8 +557,9 @@ namespace _GLIBCXX_STD
 		{
 		  iterator __finish_n = (this->_M_impl._M_finish
 					 - difference_type(__n));
-		  std::uninitialized_copy(__finish_n, this->_M_impl._M_finish,
-					  this->_M_impl._M_finish);
+		  std::__uninitialized_copy_a(__finish_n, this->_M_impl._M_finish,
+					      this->_M_impl._M_finish,
+					      this->get_allocator());
 		  this->_M_impl._M_finish = __new_finish;
 		  std::copy_backward(__pos, __finish_n, __old_finish);
 		  std::fill(__pos, __pos + difference_type(__n), __x_copy);
@@ -549,7 +569,8 @@ namespace _GLIBCXX_STD
 		  std::__uninitialized_fill_copy(this->_M_impl._M_finish,
 						 __pos + difference_type(__n),
 						 __x_copy, __pos,
-						 this->_M_impl._M_finish);
+						 this->_M_impl._M_finish,
+						 this->get_allocator());
 		  this->_M_impl._M_finish = __new_finish;
 		  std::fill(__pos, __old_finish, __x_copy);
 		}
@@ -584,8 +605,9 @@ namespace _GLIBCXX_STD
 		  {
 		    iterator __start_n = (this->_M_impl._M_start
 					  + difference_type(__n));
-		    std::uninitialized_copy(this->_M_impl._M_start, __start_n,
-					    __new_start);
+		    std::__uninitialized_copy_a(this->_M_impl._M_start, __start_n,
+						__new_start,
+						this->get_allocator());
 		    this->_M_impl._M_start = __new_start;
 		    std::copy(__start_n, __pos, __old_start);
 		    std::copy(__first, __last, __pos - difference_type(__n));
@@ -596,7 +618,8 @@ namespace _GLIBCXX_STD
 		    std::advance(__mid, difference_type(__n) - __elemsbefore);
 		    std::__uninitialized_copy_copy(this->_M_impl._M_start,
 						   __pos, __first, __mid,
-						   __new_start);
+						   __new_start,
+						   this->get_allocator());
 		    this->_M_impl._M_start = __new_start;
 		    std::copy(__mid, __last, __old_start);
 		  }
@@ -621,9 +644,10 @@ namespace _GLIBCXX_STD
 		{
 		  iterator __finish_n = (this->_M_impl._M_finish
 					 - difference_type(__n));
-		  std::uninitialized_copy(__finish_n,
-					  this->_M_impl._M_finish,
-					  this->_M_impl._M_finish);
+		  std::__uninitialized_copy_a(__finish_n,
+					      this->_M_impl._M_finish,
+					      this->_M_impl._M_finish,
+					      this->get_allocator());
 		  this->_M_impl._M_finish = __new_finish;
 		  std::copy_backward(__pos, __finish_n, __old_finish);
 		  std::copy(__first, __last, __pos);
@@ -634,7 +658,8 @@ namespace _GLIBCXX_STD
 		  std::advance(__mid, __elemsafter);
 		  std::__uninitialized_copy_copy(__mid, __last, __pos,
 						 this->_M_impl._M_finish,
-						 this->_M_impl._M_finish);
+						 this->_M_impl._M_finish,
+						 this->get_allocator());
 		  this->_M_impl._M_finish = __new_finish;
 		  std::copy(__first, __mid, __pos);
 		}
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index aaaa8c3..3362fe0 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -74,7 +74,7 @@ namespace _GLIBCXX_STD
       {
         _Node* __tmp = __cur;
         __cur = static_cast<_Node*>(__cur->_M_next);
-        std::_Destroy(&__tmp->_M_data);
+        this->get_allocator().destroy(&__tmp->_M_data);
         _M_put_node(__tmp);
       }
     }
diff --git a/libstdc++-v3/include/bits/stl_construct.h b/libstdc++-v3/include/bits/stl_construct.h
index cba3546..112276e 100644
--- a/libstdc++-v3/include/bits/stl_construct.h
+++ b/libstdc++-v3/include/bits/stl_construct.h
@@ -154,6 +154,35 @@ namespace std
 
       std::__destroy_aux(__first, __last, _Has_trivial_destructor());
     }
+
+  /**
+   * @if maint
+   * Destroy a range of objects using the supplied allocator.  For
+   * nondefault allocators we do not optimize away invocation of 
+   * destroy() even if _Tp has a trivial destructor.
+   * @endif
+   */
+
+  template <typename _Tp> class allocator;
+
+  template<typename _ForwardIterator, typename _Allocator>
+    void
+    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
+	     _Allocator __alloc)
+    {
+      for (; __first != __last; ++__first)
+	__alloc.destroy(&*__first);
+    }
+
+  template<typename _ForwardIterator, typename _Allocator, typename _Tp>
+    inline void
+    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
+	     allocator<_Tp>)
+    {
+      _Destroy(__first, __last);
+    }
+   
+
 } // namespace std
 
 #endif /* _STL_CONSTRUCT_H */
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 9dc9efb..36a7f39 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -677,8 +677,8 @@ namespace _GLIBCXX_STD
        */
       deque(const deque& __x)
       : _Base(__x.get_allocator(), __x.size())
-      { std::uninitialized_copy(__x.begin(), __x.end(),
-				this->_M_impl._M_start); }
+      { std::__uninitialized_copy_a(__x.begin(), __x.end(), this->_M_impl._M_start,
+				    this->get_allocator()); }
 
       /**
        *  @brief  Builds a %deque from a range.
@@ -710,7 +710,8 @@ namespace _GLIBCXX_STD
        *  way.  Managing the pointer is the user's responsibilty.
        */
       ~deque()
-      { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); }
+      { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+		      this->get_allocator()); }
 
       /**
        *  @brief  %Deque assignment operator.
@@ -1004,7 +1005,7 @@ namespace _GLIBCXX_STD
       {
 	if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
 	  {
-	    std::_Construct(this->_M_impl._M_start._M_cur - 1, __x);
+	    this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
 	    --this->_M_impl._M_start._M_cur;
 	  }
 	else
@@ -1025,7 +1026,7 @@ namespace _GLIBCXX_STD
 	if (this->_M_impl._M_finish._M_cur
 	    != this->_M_impl._M_finish._M_last - 1)
 	  {
-	    std::_Construct(this->_M_impl._M_finish._M_cur, __x);
+	    this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
 	    ++this->_M_impl._M_finish._M_cur;
 	  }
 	else
@@ -1046,7 +1047,7 @@ namespace _GLIBCXX_STD
 	if (this->_M_impl._M_start._M_cur
 	    != this->_M_impl._M_start._M_last - 1)
 	  {
-	    std::_Destroy(this->_M_impl._M_start._M_cur);
+	    this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
 	    ++this->_M_impl._M_start._M_cur;
 	  }
 	else
@@ -1068,7 +1069,7 @@ namespace _GLIBCXX_STD
 	    != this->_M_impl._M_finish._M_first)
 	  {
 	    --this->_M_impl._M_finish._M_cur;
-	    std::_Destroy(this->_M_impl._M_finish._M_cur);
+	    this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
 	  }
 	else
 	  _M_pop_back_aux();
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index 1671c9c..49df109 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -435,7 +435,7 @@ namespace _GLIBCXX_STD
 	_Node* __p = this->_M_get_node();
 	try
 	  {
-	    std::_Construct(&__p->_M_data, __x);
+	    this->get_allocator().construct(&__p->_M_data, __x);
 	  }
 	catch(...)
 	  {
@@ -457,7 +457,7 @@ namespace _GLIBCXX_STD
 	_Node* __p = this->_M_get_node();
 	try
 	  {
-	    std::_Construct(&__p->_M_data);
+	    this->get_allocator().construct(&__p->_M_data);
 	  }
 	catch(...)
 	  {
@@ -1170,7 +1170,7 @@ namespace _GLIBCXX_STD
       {
         __position._M_node->unhook();
         _Node* __n = static_cast<_Node*>(__position._M_node);
-        std::_Destroy(&__n->_M_data);
+        this->get_allocator().destroy(&__n->_M_data);
         _M_put_node(__n);
       }
     };
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index fdc2ea6..8ddb898 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -362,7 +362,7 @@ namespace std
       {
 	_Link_type __tmp = _M_get_node();
 	try
-	  { std::_Construct(&__tmp->_M_value_field, __x); }
+	  { get_allocator().construct(&__tmp->_M_value_field, __x); }
 	catch(...)
 	  {
 	    _M_put_node(__tmp);
@@ -384,7 +384,7 @@ namespace std
       void
       destroy_node(_Link_type __p)
       {
-	std::_Destroy(&__p->_M_value_field);
+	get_allocator().destroy(&__p->_M_value_field);
 	_M_put_node(__p);
       }
 
diff --git a/libstdc++-v3/include/bits/stl_uninitialized.h b/libstdc++-v3/include/bits/stl_uninitialized.h
index 898658c..5c65a26 100644
--- a/libstdc++-v3/include/bits/stl_uninitialized.h
+++ b/libstdc++-v3/include/bits/stl_uninitialized.h
@@ -177,13 +177,13 @@ namespace std
   // Valid if copy construction is equivalent to assignment, and if the
   //  destructor is trivial.
   template<typename _ForwardIterator, typename _Size, typename _Tp>
-    inline _ForwardIterator
+    inline void
     __uninitialized_fill_n_aux(_ForwardIterator __first, _Size __n,
 			       const _Tp& __x, __true_type)
-    { return std::fill_n(__first, __n, __x); }
+    { std::fill_n(__first, __n, __x); }
 
   template<typename _ForwardIterator, typename _Size, typename _Tp>
-    _ForwardIterator
+    void
     __uninitialized_fill_n_aux(_ForwardIterator __first, _Size __n,
 			       const _Tp& __x, __false_type)
     {
@@ -192,7 +192,6 @@ namespace std
 	{
 	  for (; __n > 0; --__n, ++__cur)
 	    std::_Construct(&*__cur, __x);
-	  return __cur;
 	}
       catch(...)
 	{
@@ -219,8 +218,102 @@ namespace std
       std::__uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
     }
 
+  // Extensions: versions of uninitialized_copy, uninitialized_fill,
+  //  and uninitialized_fill_n that take an allocator parameter.
+  //  We dispatch back to the standard versions when we're given the
+  //  default allocator.  For nondefault allocators we do not use 
+  //  any of the POD optimizations.
+
+  template<typename _InputIterator, typename _ForwardIterator,
+	   typename _Allocator>
+    _ForwardIterator
+    __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,
+			   _ForwardIterator __result,
+			   _Allocator __alloc)
+    {
+      _ForwardIterator __cur = __result;
+      try
+	{
+	  for (; __first != __last; ++__first, ++__cur)
+	    __alloc.construct(&*__cur, *__first);
+	  return __cur;
+	}
+      catch(...)
+	{
+	  std::_Destroy(__result, __cur, __alloc);
+	  __throw_exception_again;
+	}
+    }
+
+  template<typename _InputIterator, typename _ForwardIterator, typename _Tp>
+    inline _ForwardIterator
+    __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,
+			   _ForwardIterator __result,
+			   allocator<_Tp>)
+    {
+      return std::uninitialized_copy(__first, __last, __result);
+    }
+
+  template<typename _ForwardIterator, typename _Tp, typename _Allocator>
+    void
+    __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last,
+			   const _Tp& __x, _Allocator __alloc)
+    {
+      _ForwardIterator __cur = __first;
+      try
+	{
+	  for (; __cur != __last; ++__cur)
+	    __alloc.construct(&*__cur, __x);
+	}
+      catch(...)
+	{
+	  std::_Destroy(__first, __cur, __alloc);
+	  __throw_exception_again;
+	}
+    }
+
+  template<typename _ForwardIterator, typename _Tp, typename _Tp2>
+    inline void
+    __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last,
+			   const _Tp& __x, allocator<_Tp2>)
+    {
+      std::uninitialized_fill(__first, __last, __x);
+    }
+
+  template<typename _ForwardIterator, typename _Size, typename _Tp,
+	   typename _Allocator>
+    void
+    __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 
+			     const _Tp& __x,
+			     _Allocator __alloc)
+    {
+      _ForwardIterator __cur = __first;
+      try
+	{
+	  for (; __n > 0; --__n, ++__cur)
+	    __alloc.construct(&*__cur, __x);
+	}
+      catch(...)
+	{
+	  std::_Destroy(__first, __cur, __alloc);
+	  __throw_exception_again;
+	}
+    }
+
+  template<typename _ForwardIterator, typename _Size, typename _Tp,
+	   typename _Tp2>
+    void
+    __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 
+			     const _Tp& __x,
+			     allocator<_Tp2>)
+    {
+      std::uninitialized_fill_n(__first, __n, __x);
+    }
+
+
   // Extensions: __uninitialized_copy_copy, __uninitialized_copy_fill,
-  // __uninitialized_fill_copy.
+  // __uninitialized_fill_copy.  All of these algorithms take a user-
+  // supplied allocator, which is used for construction and destruction.
 
   // __uninitialized_copy_copy
   // Copies [first1, last1) into [result, result + (last1 - first1)), and
@@ -228,23 +321,25 @@ namespace std
   //  [result, result + (last1 - first1) + (last2 - first2)).
 
   template<typename _InputIterator1, typename _InputIterator2,
-	   typename _ForwardIterator>
+	   typename _ForwardIterator, typename _Allocator>
     inline _ForwardIterator
     __uninitialized_copy_copy(_InputIterator1 __first1,
 			      _InputIterator1 __last1,
 			      _InputIterator2 __first2,
 			      _InputIterator2 __last2,
-			      _ForwardIterator __result)
+			      _ForwardIterator __result,
+			      _Allocator __alloc)
     {
-      _ForwardIterator __mid = std::uninitialized_copy(__first1, __last1,
-						       __result);
+      _ForwardIterator __mid = std::__uninitialized_copy_a(__first1, __last1,
+							   __result,
+							   __alloc);
       try
 	{
-	  return std::uninitialized_copy(__first2, __last2, __mid);
+	  return std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc);
 	}
       catch(...)
 	{
-	  std::_Destroy(__result, __mid);
+	  std::_Destroy(__result, __mid, __alloc);
 	  __throw_exception_again;
 	}
     }
@@ -252,20 +347,22 @@ namespace std
   // __uninitialized_fill_copy
   // Fills [result, mid) with x, and copies [first, last) into
   //  [mid, mid + (last - first)).
-  template<typename _ForwardIterator, typename _Tp, typename _InputIterator>
+  template<typename _ForwardIterator, typename _Tp, typename _InputIterator,
+	   typename _Allocator>
     inline _ForwardIterator
     __uninitialized_fill_copy(_ForwardIterator __result, _ForwardIterator __mid,
 			      const _Tp& __x, _InputIterator __first,
-			      _InputIterator __last)
+			      _InputIterator __last,
+			      _Allocator __alloc)
     {
-      std::uninitialized_fill(__result, __mid, __x);
+      std::__uninitialized_fill_a(__result, __mid, __x, __alloc);
       try
 	{
-	  return std::uninitialized_copy(__first, __last, __mid);
+	  return std::__uninitialized_copy_a(__first, __last, __mid, __alloc);
 	}
       catch(...)
 	{
-	  std::_Destroy(__result, __mid);
+	  std::_Destroy(__result, __mid, __alloc);
 	  __throw_exception_again;
 	}
     }
@@ -273,21 +370,24 @@ namespace std
   // __uninitialized_copy_fill
   // Copies [first1, last1) into [first2, first2 + (last1 - first1)), and
   //  fills [first2 + (last1 - first1), last2) with x.
-  template<typename _InputIterator, typename _ForwardIterator, typename _Tp>
+  template<typename _InputIterator, typename _ForwardIterator, typename _Tp,
+	   typename _Allocator>
     inline void
     __uninitialized_copy_fill(_InputIterator __first1, _InputIterator __last1,
 			      _ForwardIterator __first2,
-			      _ForwardIterator __last2, const _Tp& __x)
+			      _ForwardIterator __last2, const _Tp& __x,
+			      _Allocator __alloc)
     {
-      _ForwardIterator __mid2 = std::uninitialized_copy(__first1, __last1,
-							__first2);
+      _ForwardIterator __mid2 = std::__uninitialized_copy_a(__first1, __last1,
+							    __first2,
+							    __alloc);
       try
 	{
-	  std::uninitialized_fill(__mid2, __last2, __x);
+	  std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc);
 	}
       catch(...)
 	{
-	  std::_Destroy(__first2, __mid2);
+	  std::_Destroy(__first2, __mid2, __alloc);
 	  __throw_exception_again;
 	}
     }
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 2e95845..10433f9 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -200,7 +200,8 @@ namespace _GLIBCXX_STD
 	     const allocator_type& __a = allocator_type())
       : _Base(__n, __a)
       {
-	std::uninitialized_fill_n(this->_M_impl._M_start, __n, __value);
+	std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
+				      this->get_allocator());
 	this->_M_impl._M_finish = this->_M_impl._M_start + __n;
       }
 
@@ -215,7 +216,8 @@ namespace _GLIBCXX_STD
       vector(size_type __n)
       : _Base(__n, allocator_type())
       {
-	std::uninitialized_fill_n(this->_M_impl._M_start, __n, value_type());
+	std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, value_type(),
+				      this->get_allocator());
 	this->_M_impl._M_finish = this->_M_impl._M_start + __n;	
       }
 
@@ -230,10 +232,11 @@ namespace _GLIBCXX_STD
        */
       vector(const vector& __x)
       : _Base(__x.size(), __x.get_allocator())
-      { this->_M_impl._M_finish = std::uninitialized_copy(__x.begin(),
-							  __x.end(),
-							  this->
-							  _M_impl._M_start); }
+      { this->_M_impl._M_finish =
+	  std::__uninitialized_copy_a(__x.begin(), __x.end(),
+				      this->_M_impl._M_start,
+				      this->get_allocator());
+      }
 
       /**
        *  @brief  Builds a %vector from a range.
@@ -267,7 +270,9 @@ namespace _GLIBCXX_STD
        *  responsibilty.
        */
       ~vector()
-      { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish); }
+      { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+		      this->get_allocator());
+      }
 
       /**
        *  @brief  %Vector assignment operator.
@@ -598,7 +603,7 @@ namespace _GLIBCXX_STD
       {
 	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 	  {
-	    std::_Construct(this->_M_impl._M_finish, __x);
+	    this->_M_impl.construct(this->_M_impl._M_finish, __x);
 	    ++this->_M_impl._M_finish;
 	  }
 	else
@@ -618,7 +623,7 @@ namespace _GLIBCXX_STD
       pop_back()
       {
 	--this->_M_impl._M_finish;
-	std::_Destroy(this->_M_impl._M_finish);
+	this->_M_impl.destroy(this->_M_impl._M_finish);
       }
 
       /**
@@ -758,7 +763,8 @@ namespace _GLIBCXX_STD
 	  pointer __result = this->_M_allocate(__n);
 	  try
 	    {
-	      std::uninitialized_copy(__first, __last, __result);
+	      std::__uninitialized_copy_a(__first, __last, __result,
+					  this->get_allocator());
 	      return __result;
 	    }
 	  catch(...)
@@ -778,7 +784,8 @@ namespace _GLIBCXX_STD
         {
 	  this->_M_impl._M_start = _M_allocate(__n);
 	  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
-	  std::uninitialized_fill_n(this->_M_impl._M_start, __n, __value);
+	  std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
+					this->get_allocator());
 	  this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
 	}
 
@@ -812,9 +819,10 @@ namespace _GLIBCXX_STD
 	  const size_type __n = std::distance(__first, __last);
 	  this->_M_impl._M_start = this->_M_allocate(__n);
 	  this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
-	  this->_M_impl._M_finish = std::uninitialized_copy(__first, __last,
-							    this->
-							    _M_impl._M_start);
+	  this->_M_impl._M_finish =
+	    std::__uninitialized_copy_a(__first, __last,
+					this->_M_impl._M_start,
+					this->get_allocator());
 	}
 
 
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 5337035..4231715 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -76,7 +76,8 @@ namespace _GLIBCXX_STD
 	  pointer __tmp = _M_allocate_and_copy(__n,
 					       this->_M_impl._M_start,
 					       this->_M_impl._M_finish);
-	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
+	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+			this->get_allocator());
 	  _M_deallocate(this->_M_impl._M_start,
 			this->_M_impl._M_end_of_storage
 			- this->_M_impl._M_start);
@@ -95,7 +96,7 @@ namespace _GLIBCXX_STD
       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
 	  && __position == end())
 	{
-	  std::_Construct(this->_M_impl._M_finish, __x);
+	  this->_M_impl.construct(this->_M_impl._M_finish, __x);
 	  ++this->_M_impl._M_finish;
 	}
       else
@@ -111,7 +112,7 @@ namespace _GLIBCXX_STD
       if (__position + 1 != end())
         std::copy(__position + 1, end(), __position);
       --this->_M_impl._M_finish;
-      std::_Destroy(this->_M_impl._M_finish);
+      this->_M_impl.destroy(this->_M_impl._M_finish);
       return __position;
     }
 
@@ -121,7 +122,7 @@ namespace _GLIBCXX_STD
     erase(iterator __first, iterator __last)
     {
       iterator __i(copy(__last, end(), __first));
-      std::_Destroy(__i, end());
+      std::_Destroy(__i, end(), this->get_allocator());
       this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first);
       return __first;
     }
@@ -138,8 +139,8 @@ namespace _GLIBCXX_STD
 	    {
 	      pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
 						   __x.end());
-	      std::_Destroy(this->_M_impl._M_start,
-			    this->_M_impl._M_finish);
+	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+			    this->get_allocator());
 	      _M_deallocate(this->_M_impl._M_start,
 			    this->_M_impl._M_end_of_storage
 			    - this->_M_impl._M_start);
@@ -149,14 +150,15 @@ namespace _GLIBCXX_STD
 	  else if (size() >= __xlen)
 	    {
 	      iterator __i(copy(__x.begin(), __x.end(), begin()));
-	      std::_Destroy(__i, end());
+	      std::_Destroy(__i, end(), this->get_allocator());
 	    }
 	  else
 	    {
 	      std::copy(__x.begin(), __x.begin() + size(),
 			this->_M_impl._M_start);
-	      std::uninitialized_copy(__x.begin() + size(),
-				      __x.end(), this->_M_impl._M_finish);
+	      std::__uninitialized_copy_a(__x.begin() + size(),
+					  __x.end(), this->_M_impl._M_finish,
+					  this->get_allocator());
 	    }
 	  this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
 	}
@@ -176,8 +178,9 @@ namespace _GLIBCXX_STD
       else if (__n > size())
 	{
 	  std::fill(begin(), end(), __val);
-	  std::uninitialized_fill_n(this->_M_impl._M_finish,
-				    __n - size(), __val);
+	  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
+					__n - size(), __val,
+					this->get_allocator());
 	  this->_M_impl._M_finish += __n - size();
 	}
       else
@@ -212,7 +215,8 @@ namespace _GLIBCXX_STD
 	if (__len > capacity())
 	  {
 	    pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
-	    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
+	    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+			  this->get_allocator());
 	    _M_deallocate(this->_M_impl._M_start,
 			  this->_M_impl._M_end_of_storage
 			  - this->_M_impl._M_start);
@@ -224,7 +228,7 @@ namespace _GLIBCXX_STD
 	  {
 	    iterator __new_finish(copy(__first, __last,
 				       this->_M_impl._M_start));
-	    std::_Destroy(__new_finish, end());
+	    std::_Destroy(__new_finish, end(), this->get_allocator());
 	    this->_M_impl._M_finish = __new_finish.base();
 	  }
 	else
@@ -232,10 +236,10 @@ namespace _GLIBCXX_STD
 	    _ForwardIterator __mid = __first;
 	    std::advance(__mid, size());
 	    std::copy(__first, __mid, this->_M_impl._M_start);
-	    this->_M_impl._M_finish = std::uninitialized_copy(__mid,
-							      __last,
-							      this->_M_impl.
-							      _M_finish);
+	    this->_M_impl._M_finish =
+	      std::__uninitialized_copy_a(__mid, __last,
+					  this->_M_impl._M_finish,
+					  this->get_allocator());
 	  }
       }
 
@@ -246,8 +250,8 @@ namespace _GLIBCXX_STD
     {
       if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 	{
-	  std::_Construct(this->_M_impl._M_finish,
-			  *(this->_M_impl._M_finish - 1));
+	  this->_M_impl.construct(this->_M_impl._M_finish,
+				  *(this->_M_impl._M_finish - 1));
 	  ++this->_M_impl._M_finish;
 	  _Tp __x_copy = __x;
 	  std::copy_backward(__position,
@@ -263,24 +267,26 @@ namespace _GLIBCXX_STD
 	  iterator __new_finish(__new_start);
 	  try
 	    {
-	      __new_finish = std::uninitialized_copy(iterator(this->
-							      _M_impl._M_start),
-						     __position,
-						     __new_start);
-	      std::_Construct(__new_finish.base(), __x);
+	      __new_finish =
+		std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
+					    __position,
+					    __new_start,
+					    this->get_allocator());
+	      this->_M_impl.construct(__new_finish.base(), __x);
 	      ++__new_finish;
-	      __new_finish = std::uninitialized_copy(__position,
-						     iterator(this->_M_impl.
-							      _M_finish),
-						     __new_finish);
+	      __new_finish =
+		std::__uninitialized_copy_a(__position,
+					    iterator(this->_M_impl._M_finish),
+					    __new_finish,
+					    this->get_allocator());
           }
 	  catch(...)
 	    {
-	      std::_Destroy(__new_start,__new_finish);
+	      std::_Destroy(__new_start, __new_finish, this->get_allocator());
 	      _M_deallocate(__new_start.base(),__len);
 	      __throw_exception_again;
 	    }
-	  std::_Destroy(begin(), end());
+	  std::_Destroy(begin(), end(), this->get_allocator());
 	  _M_deallocate(this->_M_impl._M_start,
 			this->_M_impl._M_end_of_storage
 			- this->_M_impl._M_start);
@@ -305,9 +311,10 @@ namespace _GLIBCXX_STD
 	      iterator __old_finish(this->_M_impl._M_finish);
 	      if (__elems_after > __n)
 		{
-		  std::uninitialized_copy(this->_M_impl._M_finish - __n,
-					  this->_M_impl._M_finish,
-					  this->_M_impl._M_finish);
+		  std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
+					      this->_M_impl._M_finish,
+					      this->_M_impl._M_finish,
+					      this->get_allocator());
 		  this->_M_impl._M_finish += __n;
 		  std::copy_backward(__position, __old_finish - __n,
 				     __old_finish);
@@ -315,12 +322,14 @@ namespace _GLIBCXX_STD
 		}
 	      else
 		{
-		  std::uninitialized_fill_n(this->_M_impl._M_finish,
-					    __n - __elems_after,
-					    __x_copy);
+		  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
+						__n - __elems_after,
+						__x_copy,
+						this->get_allocator());
 		  this->_M_impl._M_finish += __n - __elems_after;
-		  std::uninitialized_copy(__position, __old_finish,
-					  this->_M_impl._M_finish);
+		  std::__uninitialized_copy_a(__position, __old_finish,
+					      this->_M_impl._M_finish,
+					      this->get_allocator());
 		  this->_M_impl._M_finish += __elems_after;
 		  std::fill(__position, __old_finish, __x_copy);
 		}
@@ -333,20 +342,26 @@ namespace _GLIBCXX_STD
 	      iterator __new_finish(__new_start);
 	      try
 		{
-		  __new_finish = std::uninitialized_copy(begin(), __position,
-							 __new_start);
-		  std::uninitialized_fill_n(__new_finish, __n, __x);
+		  __new_finish =
+		    std::__uninitialized_copy_a(begin(), __position,
+						__new_start,
+						this->get_allocator());
+		  std::__uninitialized_fill_n_a(__new_finish, __n, __x,
+						this->get_allocator());
 		  __new_finish += __n;
-		  __new_finish = std::uninitialized_copy(__position, end(),
-							 __new_finish);
+		  __new_finish =
+		    std::__uninitialized_copy_a(__position, end(), __new_finish,
+						this->get_allocator());
 		}
 	      catch(...)
 		{
-		  std::_Destroy(__new_start, __new_finish);
+		  std::_Destroy(__new_start, __new_finish,
+				this->get_allocator());
 		  _M_deallocate(__new_start.base(), __len);
 		  __throw_exception_again;
 		}
-	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
+	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+			    this->get_allocator());
 	      _M_deallocate(this->_M_impl._M_start,
 			    this->_M_impl._M_end_of_storage
 			    - this->_M_impl._M_start);
@@ -387,9 +402,10 @@ namespace _GLIBCXX_STD
 		iterator __old_finish(this->_M_impl._M_finish);
 		if (__elems_after > __n)
 		  {
-		    std::uninitialized_copy(this->_M_impl._M_finish - __n,
-					    this->_M_impl._M_finish,
-					    this->_M_impl._M_finish);
+		    std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
+						this->_M_impl._M_finish,
+						this->_M_impl._M_finish,
+						this->get_allocator());
 		    this->_M_impl._M_finish += __n;
 		    std::copy_backward(__position, __old_finish - __n,
 				       __old_finish);
@@ -399,11 +415,13 @@ namespace _GLIBCXX_STD
 		  {
 		    _ForwardIterator __mid = __first;
 		    std::advance(__mid, __elems_after);
-		    std::uninitialized_copy(__mid, __last,
-					    this->_M_impl._M_finish);
+		    std::__uninitialized_copy_a(__mid, __last,
+						this->_M_impl._M_finish,
+						this->get_allocator());
 		    this->_M_impl._M_finish += __n - __elems_after;
-		    std::uninitialized_copy(__position, __old_finish,
-					    this->_M_impl._M_finish);
+		    std::__uninitialized_copy_a(__position, __old_finish,
+						this->_M_impl._M_finish,
+						this->get_allocator());
 		    this->_M_impl._M_finish += __elems_after;
 		    std::copy(__first, __mid, __position);
 		  }
@@ -416,26 +434,29 @@ namespace _GLIBCXX_STD
 		iterator __new_finish(__new_start);
 		try
 		  {
-		    __new_finish = std::uninitialized_copy(iterator(this->
-								    _M_impl.
-								    _M_start),
-							   __position,
-							   __new_start);
-		    __new_finish = std::uninitialized_copy(__first, __last,
-							   __new_finish);
-		    __new_finish = std::uninitialized_copy(__position,
-							   iterator(this->
-								    _M_impl.
-								    _M_finish),
-							   __new_finish);
+		    __new_finish =
+		      std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
+						  __position,
+						  __new_start,
+						  this->get_allocator());
+		    __new_finish =
+		      std::__uninitialized_copy_a(__first, __last, __new_finish,
+						  this->get_allocator());
+		    __new_finish =
+		      std::__uninitialized_copy_a(__position,
+						  iterator(this->_M_impl._M_finish),
+						  __new_finish,
+						  this->get_allocator());
 		  }
 		catch(...)
 		  {
-		    std::_Destroy(__new_start,__new_finish);
+		    std::_Destroy(__new_start,__new_finish,
+				  this->get_allocator());
 		    _M_deallocate(__new_start.base(), __len);
 		    __throw_exception_again;
 		  }
-		std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);
+		std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+			      this->get_allocator());
 		_M_deallocate(this->_M_impl._M_start,
 			      this->_M_impl._M_end_of_storage
 			      - this->_M_impl._M_start);
diff --git a/libstdc++-v3/include/ext/hashtable.h b/libstdc++-v3/include/ext/hashtable.h
index 15b0434..6f3aee4 100644
--- a/libstdc++-v3/include/ext/hashtable.h
+++ b/libstdc++-v3/include/ext/hashtable.h
@@ -281,7 +281,7 @@ namespace __gnu_cxx
       typedef _Hashtable_node<_Val> _Node;
 
     public:
-      typedef _Alloc allocator_type;
+      typedef typename _Alloc::template rebind<value_type>::other allocator_type;
       allocator_type
       get_allocator() const
       { return _M_node_allocator; }
@@ -607,7 +607,7 @@ namespace __gnu_cxx
 	__n->_M_next = 0;
 	try
 	  {
-	    _Construct(&__n->_M_val, __obj);
+	    this->get_allocator().construct(&__n->_M_val, __obj);
 	    return __n;
 	  }
 	catch(...)
@@ -620,7 +620,7 @@ namespace __gnu_cxx
       void
       _M_delete_node(_Node* __n)
       {
-	_Destroy(&__n->_M_val);
+	this->get_allocator().destroy(&__n->_M_val);
 	_M_put_node(__n);
       }
       
diff --git a/libstdc++-v3/include/ext/memory b/libstdc++-v3/include/ext/memory
index adb15ce..dc04657 100644
--- a/libstdc++-v3/include/ext/memory
+++ b/libstdc++-v3/include/ext/memory
@@ -128,6 +128,40 @@ namespace __gnu_cxx
     { return __uninitialized_copy_n(__first, __count, __result,
 				    __iterator_category(__first)); }
 
+
+  // An alternative version of uninitialized_copy_n that constructs
+  // and destroys objects with a user-provided allocator.
+  template<typename _InputIter, typename _Size, typename _ForwardIter,
+           typename _Allocator>
+    pair<_InputIter, _ForwardIter>
+    __uninitialized_copy_n_a(_InputIter __first, _Size __count,
+			     _ForwardIter __result,
+			     _Allocator __alloc)
+    {
+      _ForwardIter __cur = __result;
+      try
+	{
+	  for (; __count > 0 ; --__count, ++__first, ++__cur)
+	    __alloc.construct(&*__cur, *__first);
+	  return pair<_InputIter, _ForwardIter>(__first, __cur);
+	}
+      catch(...)
+	{
+	  std::_Destroy(__result, __cur, __alloc);
+	  __throw_exception_again;
+	}
+    }
+
+  template<typename _InputIter, typename _Size, typename _ForwardIter,
+           typename _Tp>
+    inline pair<_InputIter, _ForwardIter>
+    __uninitialized_copy_n_a(_InputIter __first, _Size __count,
+			     _ForwardIter __result,
+			     std::allocator<_Tp>)
+    {
+      return uninitialized_copy_n(__first, __count, __result);
+    }
+
   /**
    *  This class provides similar behavior and semantics of the standard
    *  functions get_temporary_buffer() and return_temporary_buffer(), but
diff --git a/libstdc++-v3/include/ext/rope b/libstdc++-v3/include/ext/rope
index 8cfcde9..ff9e3bd 100644
--- a/libstdc++-v3/include/ext/rope
+++ b/libstdc++-v3/include/ext/rope
@@ -1642,7 +1642,7 @@ protected:
 	  return 0;
 	_CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
 	
-	uninitialized_copy_n(__s, __size, __buf);
+	__uninitialized_copy_n_a(__s, __size, __buf, __a);
 	_S_cond_store_eos(__buf[__size]);
 	try
 	  { return _S_new_RopeLeaf(__buf, __size, __a); }
@@ -1790,7 +1790,7 @@ protected:
       {
 	_CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
 	
-	std::_Construct(__buf, __c);
+	get_allocator().construct(__buf, __c);
 	try
 	  { this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, __a); }
 	catch(...)
@@ -1905,7 +1905,7 @@ protected:
       void
       copy(_CharT* __buffer) const
       {
-	_Destroy(__buffer, __buffer + size());
+	_Destroy(__buffer, __buffer + size(), get_allocator());
 	_S_flatten(this->_M_tree_ptr, __buffer);
       }
 
@@ -1920,7 +1920,7 @@ protected:
 	size_t __size = size();
 	size_t __len = (__pos + __n > __size? __size - __pos : __n);
 	
-	_Destroy(__buffer, __buffer + __len);
+	_Destroy(__buffer, __buffer + __len, get_allocator());
 	_S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
 	return __len;
       }
diff --git a/libstdc++-v3/include/ext/ropeimpl.h b/libstdc++-v3/include/ext/ropeimpl.h
index e9f9271..7463196 100644
--- a/libstdc++-v3/include/ext/ropeimpl.h
+++ b/libstdc++-v3/include/ext/ropeimpl.h
@@ -346,7 +346,7 @@ namespace __gnu_cxx
       if (0 != __cstr)
 	{
 	  size_t __size = this->_M_size + 1;
-	  _Destroy(__cstr, __cstr + __size);
+	  _Destroy(__cstr, __cstr + __size, get_allocator());
 	  this->_Data_deallocate(__cstr, __size);
 	}
     }
@@ -357,7 +357,7 @@ namespace __gnu_cxx
     _S_free_string(_CharT* __s, size_t __n, allocator_type __a)
     {
       if (!_S_is_basic_char_type((_CharT*)0))
-	_Destroy(__s, __s + __n);
+	_Destroy(__s, __s + __n, __a);
       
       //  This has to be a static member, so this gets a bit messy
       __a.deallocate(__s,
@@ -1547,7 +1547,8 @@ namespace __gnu_cxx
       else
 	{
 	  __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
-	  uninitialized_fill_n(__rest_buffer, __rest, __c);
+	  __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
+				   get_allocator());
 	  _S_cond_store_eos(__rest_buffer[__rest]);
 	  try
 	    { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); }
@@ -1564,7 +1565,8 @@ namespace __gnu_cxx
 	    this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
 	  _RopeLeaf* __base_leaf;
 	  rope __base_rope;
-	  uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c);
+	  __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
+				   get_allocator());
 	  _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
 	  try
 	    {
diff --git a/libstdc++-v3/include/ext/slist b/libstdc++-v3/include/ext/slist
index 945a503..470e7a9 100644
--- a/libstdc++-v3/include/ext/slist
+++ b/libstdc++-v3/include/ext/slist
@@ -260,7 +260,7 @@ namespace __gnu_cxx
 	_Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
 	_Slist_node_base* __next_next = __next->_M_next;
 	__pos->_M_next = __next_next;
-	_Destroy(&__next->_M_data);
+	get_allocator().destroy(&__next->_M_data);
 	_M_put_node(__next);
 	return __next_next;
       }
@@ -277,7 +277,7 @@ namespace __gnu_cxx
 	{
 	  _Slist_node<_Tp>* __tmp = __cur;
 	  __cur = (_Slist_node<_Tp>*) __cur->_M_next;
-	  _Destroy(&__tmp->_M_data);
+	  get_allocator().destroy(&__tmp->_M_data);
 	  _M_put_node(__tmp);
 	}
       __before_first->_M_next = __last_node;
@@ -327,7 +327,7 @@ namespace __gnu_cxx
 	_Node* __node = this->_M_get_node();
 	try
 	  {
-	    _Construct(&__node->_M_data, __x);
+	    get_allocator().construct(&__node->_M_data, __x);
 	    __node->_M_next = 0;
 	  }
 	catch(...)
@@ -344,7 +344,7 @@ namespace __gnu_cxx
 	_Node* __node = this->_M_get_node();
 	try
 	  {
-	    _Construct(&__node->_M_data);
+	    get_allocator().construct(&__node->_M_data);
 	    __node->_M_next = 0;
 	  }
 	catch(...)
@@ -490,7 +490,7 @@ namespace __gnu_cxx
       {
 	_Node* __node = (_Node*) this->_M_head._M_next;
 	this->_M_head._M_next = __node->_M_next;
-	_Destroy(&__node->_M_data);
+	get_allocator().destroy(&__node->_M_data);
 	this->_M_put_node(__node);
       }
 
diff --git a/libstdc++-v3/testsuite/23_containers/deque/check_construct_destroy.cc b/libstdc++-v3/testsuite/23_containers/deque/check_construct_destroy.cc
new file mode 100644
index 0000000..ecd7979
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/check_construct_destroy.cc
@@ -0,0 +1,82 @@
+// 2004-07-26  Matt Austern  <austern@apple.com>
+//
+// Copyright (C) 2003 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <deque>
+#include <testsuite_allocator.h>
+
+using namespace __gnu_test;
+
+int main()
+{
+  typedef std::deque<int, tracker_alloc<int> > Container;
+  const int arr10[10] = { 2, 4, 1, 7, 3, 8, 10, 5, 9, 6 };
+  bool ok = true;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c;
+    ok = check_construct_destroy("empty container", 0, 0) && ok;
+  }
+  ok = check_construct_destroy("empty container", 0, 0) && ok;
+
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    ok = check_construct_destroy("Construct from range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Construct from range", 10, 10) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin(), arr10[0]);
+    ok = check_construct_destroy("Insert element", 1, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert element", 1, 11) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin() + 5, arr10, arr10+3);
+    ok = check_construct_destroy("Insert short range", 3, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert short range", 3, 13) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin() + 7, arr10, arr10+10);
+    ok = check_construct_destroy("Insert long range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert long range", 10, 20) && ok;
+
+  return ok ? 0 : 1;;
+}
+
diff --git a/libstdc++-v3/testsuite/23_containers/list/check_construct_destroy.cc b/libstdc++-v3/testsuite/23_containers/list/check_construct_destroy.cc
new file mode 100644
index 0000000..023724c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/check_construct_destroy.cc
@@ -0,0 +1,87 @@
+// 2004-07-26  Matt Austern  <austern@apple.com>
+//
+// Copyright (C) 2003 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <list>
+#include <iterator>
+#include <testsuite_allocator.h>
+
+using namespace __gnu_test;
+
+int main()
+{
+  typedef std::list<int, tracker_alloc<int> > Container;
+  const int arr10[10] = { 2, 4, 1, 7, 3, 8, 10, 5, 9, 6 };
+  bool ok = true;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c;
+    ok = check_construct_destroy("empty container", 0, 0) && ok;
+  }
+  ok = check_construct_destroy("empty container", 0, 0) && ok;
+
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    ok = check_construct_destroy("Construct from range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Construct from range", 10, 10) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin(), arr10[0]);
+    ok = check_construct_destroy("Insert element", 1, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert element", 1, 11) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    Container::iterator i5 = c.begin();
+    std::advance(i5, 5);
+    c.insert(i5, arr10, arr10+3);
+    ok = check_construct_destroy("Insert short range", 3, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert short range", 3, 13) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    Container::iterator i7 = c.begin();
+    std::advance(i7, 5);
+    c.insert(i7, arr10, arr10+10);
+    ok = check_construct_destroy("Insert long range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert long range", 10, 20) && ok;
+
+  return ok ? 0 : 1;
+}
+
diff --git a/libstdc++-v3/testsuite/23_containers/set/check_construct_destroy.cc b/libstdc++-v3/testsuite/23_containers/set/check_construct_destroy.cc
new file mode 100644
index 0000000..0f6d866
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/check_construct_destroy.cc
@@ -0,0 +1,85 @@
+// 2004-07-26  Matt Austern  <austern@apple.com>
+//
+// Copyright (C) 2003 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <set>
+#include <functional>
+#include <iterator>
+#include <testsuite_allocator.h>
+
+using namespace __gnu_test;
+
+int main()
+{
+  typedef std::set<int, std::less<int>, tracker_alloc<int> > Container;
+  const int arr10[10]  = { 2, 4, 1, 7, 3, 8, 10, 5, 9, 6 };
+  const int arr10a[10] = { 31, 23, 82, 46, 13, 17, 30, 71, 22, 51 };
+  bool ok = true;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c;
+    ok = check_construct_destroy("empty container", 0, 0) && ok;
+  }
+  ok = check_construct_destroy("empty container", 0, 0) && ok;
+
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    ok = check_construct_destroy("Construct from range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Construct from range", 10, 10) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(arr10a[0]);
+    ok = check_construct_destroy("Insert element", 1, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert element", 1, 11) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(arr10a, arr10a+3);
+    ok = check_construct_destroy("Insert short range", 3, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert short range", 3, 13) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(arr10a, arr10a+10);
+    ok = check_construct_destroy("Insert long range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert long range", 10, 20) && ok;
+
+  return ok ? 0 : 1;
+}
+
diff --git a/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc b/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
new file mode 100644
index 0000000..6c31235
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/check_construct_destroy.cc
@@ -0,0 +1,85 @@
+// 2004-07-26  Matt Austern  <austern@apple.com>
+//
+// Copyright (C) 2003 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <vector>
+#include <testsuite_allocator.h>
+
+using namespace __gnu_test;
+
+int main()
+{
+  typedef std::vector<int, tracker_alloc<int> > Container;
+  const int arr10[10] = { 2, 4, 1, 7, 3, 8, 10, 5, 9, 6 };
+  bool ok = true;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c;
+    ok = check_construct_destroy("empty container", 0, 0) && ok;
+  }
+  ok = check_construct_destroy("empty container", 0, 0) && ok;
+
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    ok = check_construct_destroy("Construct from range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Construct from range", 10, 10) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    c.reserve(100);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin(), arr10[0]);
+    ok = check_construct_destroy("Insert element", 1, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert element", 1, 11) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    c.reserve(100);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin() + 5, arr10, arr10+3);
+    ok = check_construct_destroy("Insert short range", 3, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert short range", 3, 13) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    c.reserve(100);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin() + 7, arr10, arr10+10);
+    ok = check_construct_destroy("Insert long range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert long range", 10, 20) && ok;
+
+  return ok ? 0 : 1;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/hash_check_construct_destroy.cc b/libstdc++-v3/testsuite/ext/hash_check_construct_destroy.cc
new file mode 100644
index 0000000..d95273e
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/hash_check_construct_destroy.cc
@@ -0,0 +1,91 @@
+// 2004-07-26  Matt Austern  <austern@apple.com>
+//
+// Copyright (C) 2003 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <ext/hash_set>
+#include <functional>
+#include <iterator>
+#include <testsuite_allocator.h>
+
+using namespace __gnu_test;
+
+int main()
+{
+  typedef __gnu_cxx::hash_set<int, __gnu_cxx::hash<int>, std::equal_to<int>,
+                              tracker_alloc<int> >
+    Container;
+
+  const int arr10[10]  = { 2, 4, 1, 7, 3, 8, 10, 5, 9, 6 };
+  const int arr10a[10] = { 31, 23, 82, 46, 13, 17, 30, 71, 22, 51 };
+  bool ok = true;
+
+  int buckets;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c;
+    buckets = c.bucket_count();
+    ok = check_construct_destroy("empty container", buckets, 0) && ok;
+  }
+  ok = check_construct_destroy("empty container", buckets, buckets) && ok;
+
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    ok = check_construct_destroy("Construct from range", buckets+10, 0) && ok;
+  }
+  ok = check_construct_destroy("Construct from range", buckets+10, buckets+10) && ok;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    c.insert(arr10a[0]);
+    ok = check_construct_destroy("Insert element", buckets+11, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert element", buckets+11, buckets+11) && ok;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    c.insert(arr10a, arr10a+3);
+    ok = check_construct_destroy("Insert short range", buckets+13, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert short range", buckets+13, buckets+13) && ok;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    c.insert(arr10a, arr10a+10);
+    ok = check_construct_destroy("Insert long range", buckets+20, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert long range", buckets+20, buckets+20) && ok;
+
+  return ok ? 0 : 1;
+}
+
diff --git a/libstdc++-v3/testsuite/ext/slist_check_construct_destroy.cc b/libstdc++-v3/testsuite/ext/slist_check_construct_destroy.cc
new file mode 100644
index 0000000..174c4da
--- /dev/null
+++ b/libstdc++-v3/testsuite/ext/slist_check_construct_destroy.cc
@@ -0,0 +1,87 @@
+// 2004-07-26  Matt Austern  <austern@apple.com>
+//
+// Copyright (C) 2003 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+//
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <ext/slist>
+#include <iterator>
+#include <testsuite_allocator.h>
+
+using namespace __gnu_test;
+
+int main()
+{
+  typedef __gnu_cxx::slist<int, tracker_alloc<int> > Container;
+  const int arr10[10] = { 2, 4, 1, 7, 3, 8, 10, 5, 9, 6 };
+  bool ok = true;
+
+  allocation_tracker::resetCounts();
+  {
+    Container c;
+    ok = check_construct_destroy("empty container", 0, 0) && ok;
+  }
+  ok = check_construct_destroy("empty container", 0, 0) && ok;
+
+
+  allocation_tracker::resetCounts();
+  {
+    Container c(arr10, arr10 + 10);
+    ok = check_construct_destroy("Construct from range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Construct from range", 10, 10) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    c.insert(c.begin(), arr10[0]);
+    ok = check_construct_destroy("Insert element", 1, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert element", 1, 11) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    Container::iterator i5 = c.begin();
+    std::advance(i5, 5);
+    c.insert(i5, arr10, arr10+3);
+    ok = check_construct_destroy("Insert short range", 3, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert short range", 3, 13) && ok;
+
+  {
+    Container c(arr10, arr10 + 10);
+    allocation_tracker::resetCounts();
+    Container::iterator i7 = c.begin();
+    std::advance(i7, 5);
+    c.insert(i7, arr10, arr10+10);
+    ok = check_construct_destroy("Insert long range", 10, 0) && ok;
+  }
+  ok = check_construct_destroy("Insert long range", 10, 20) && ok;
+
+  return ok ? 0 : 1;
+}
+
diff --git a/libstdc++-v3/testsuite/testsuite_allocator.cc b/libstdc++-v3/testsuite/testsuite_allocator.cc
index a98e388..6856226 100644
--- a/libstdc++-v3/testsuite/testsuite_allocator.cc
+++ b/libstdc++-v3/testsuite/testsuite_allocator.cc
@@ -28,6 +28,7 @@
 // invalidate any other reasons why the executable file might be covered by
 // the GNU General Public License.
 
+#include <iostream>
 #include <testsuite_allocator.h>
 
 namespace __gnu_test
@@ -36,5 +37,24 @@ namespace __gnu_test
   allocation_tracker::size_type allocation_tracker::deallocationTotal_ = 0;
   int allocation_tracker::constructCount_    = 0;
   int allocation_tracker::destructCount_     = 0;
+
+  bool
+  check_construct_destroy(const char* tag, int expected_c, int expected_d)
+  {
+    if (allocation_tracker::constructCount() == expected_c &&
+	allocation_tracker::destructCount() == expected_d)
+      return true;
+
+    else {
+      std::cerr << tag << ": "
+		<< " construct = " << allocation_tracker::constructCount()
+		<< " (should be " << expected_c << "),"
+		<< " destroy = " << allocation_tracker::destructCount()
+		<< " (should be " << expected_d << ")"
+		<< std::endl;
+      return false;
+    }
+  }
+
 }; // namespace __cxx_test
 
diff --git a/libstdc++-v3/testsuite/testsuite_allocator.h b/libstdc++-v3/testsuite/testsuite_allocator.h
index 866fe7c..46b7891 100644
--- a/libstdc++-v3/testsuite/testsuite_allocator.h
+++ b/libstdc++-v3/testsuite/testsuite_allocator.h
@@ -169,6 +169,10 @@ namespace __gnu_test
     bool
     operator!=(const tracker_alloc<T1>&, const tracker_alloc<T2>&) throw()
     { return false; }
+
+   bool
+   check_construct_destroy(const char* tag, int expected_c, int expected_d);
+
 }; // namespace __gnu_test
 
 #endif // _GLIBCXX_TESTSUITE_ALLOCATOR_H