re PR libstdc++/21770 (rebinding allocator::value type vs. container::value_type)

2005-06-03  Paolo Carlini  <pcarlini@suse.de>

	PR libstdc++/21770
	* include/bits/stl_deque.h: Add concept-check. In class _Deque_base
	rebind _Alloc to  _Tp_alloc_type, change _Deque_impl to inherit from
	the latter and add _M_get_Tp_allocator() which returns it. Use
	everywhere _M_get_Tp_allocator() instead of get_allocator().
	* include/bits/deque.tcc: Likewise, use _M_get_Tp_allocator().
	* include/bits/stl_list.h: Add concept-check. In class _List_base
	rebind _Alloc to _Tp_alloc_type and add _M_get_Tp_allocator(), which
	returns the allocator (of type _Node_alloc_type) converted to
	_Tp_alloc_type. Use everywhere _M_get_Tp_allocator() instead of
	get_allocator().
	* include/bits/list.tcc: Likewise, use _M_get_Tp_allocator().
	* include/bits/stl_vector.h: Add concept-check. In class _Vector_base
	rebind _Alloc to _Tp_alloc_type, change _Vector_impl to inherit from
	the latter and add _M_get_Tp_allocator() which returns it. Use
	everywhere _M_get_Tp_allocator() instead of get_allocator().
	* include/bits/vector.tcc: Likewise, use _M_get_Tp_allocator().
	* include/bits/stl_map.h: Add concept-check. Rebind _Alloc to
	_Pair_alloc_type and use it for _Rb_tree.
	* include/bits/stl_multimap.h: Likewise.
	* include/bits/stl_multiset.h: Add concept-check. Rebind _Alloc to
	_Key_alloc_type and use it for _Rb_tree.
	* include/bits/stl_set.h: Likewise.
	* include/bits/basic_string.h: Rebind _Alloc to _CharT_alloc_type and
	use it for the allocator typedefs.
	* testsuite/21_strings/basic_string/1.cc: New.
	* testsuite/23_containers/deque/explicit_instantiation.cc: Move to...
	* testsuite/23_containers/deque/explicit_instantiation/1.cc: ... here.
	* testsuite/23_containers/deque/explicit_instantiation/3.cc: New.
	* testsuite/23_containers/list/explicit_instantiation.cc: Move to...
	* testsuite/23_containers/list/explicit_instantiation/1.cc: ... here.
	* testsuite/23_containers/list/explicit_instantiation/3.cc: New.
	* testsuite/23_containers/map/explicit_instantiation.cc: Move to...
	* testsuite/23_containers/map/explicit_instantiation/1.cc: ... here.
	* testsuite/23_containers/map/explicit_instantiation/3.cc: New.
	* testsuite/23_containers/multimap/explicit_instantiation.cc: Move to...
	* testsuite/23_containers/multimap/explicit_instantiation/1.cc: .. here.
	* testsuite/23_containers/multimap/explicit_instantiation/3.cc: New.
	* testsuite/23_containers/multiset/explicit_instantiation.cc: Move to...
	* testsuite/23_containers/multiset/explicit_instantiation/1.cc: .. here.
	* testsuite/23_containers/multiset/explicit_instantiation/3.cc: New.
	* testsuite/23_containers/set/explicit_instantiation.cc: Move to...
	* testsuite/23_containers/set/explicit_instantiation/1.cc: .. here.
	* testsuite/23_containers/set/explicit_instantiation/3.cc: New.
	* testsuite/23_containers/vector/explicit_instantiation.cc: Move to...
	* testsuite/23_containers/vector/explicit_instantiation/1.cc: ... here.
	* testsuite/23_containers/vector/explicit_instantiation/3.cc: New.

From-SVN: r100546

27 files changed, 660 insertions, 266 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index d2ecd58..77cc306 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,53 @@
+2005-06-03  Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/21770
+	* include/bits/stl_deque.h: Add concept-check. In class _Deque_base
+	rebind _Alloc to  _Tp_alloc_type, change _Deque_impl to inherit from
+	the latter and add _M_get_Tp_allocator() which returns it. Use
+	everywhere _M_get_Tp_allocator() instead of get_allocator().
+	* include/bits/deque.tcc: Likewise, use _M_get_Tp_allocator().
+	* include/bits/stl_list.h: Add concept-check. In class _List_base
+	rebind _Alloc to _Tp_alloc_type and add _M_get_Tp_allocator(), which
+	returns the allocator (of type _Node_alloc_type) converted to
+	_Tp_alloc_type. Use everywhere _M_get_Tp_allocator() instead of
+	get_allocator().
+	* include/bits/list.tcc: Likewise, use _M_get_Tp_allocator().
+	* include/bits/stl_vector.h: Add concept-check. In class _Vector_base
+	rebind _Alloc to _Tp_alloc_type, change _Vector_impl to inherit from
+	the latter and add _M_get_Tp_allocator() which returns it. Use
+	everywhere _M_get_Tp_allocator() instead of get_allocator().
+	* include/bits/vector.tcc: Likewise, use _M_get_Tp_allocator().
+	* include/bits/stl_map.h: Add concept-check. Rebind _Alloc to
+	_Pair_alloc_type and use it for _Rb_tree.
+	* include/bits/stl_multimap.h: Likewise.
+	* include/bits/stl_multiset.h: Add concept-check. Rebind _Alloc to
+	_Key_alloc_type and use it for _Rb_tree.
+	* include/bits/stl_set.h: Likewise.
+	* include/bits/basic_string.h: Rebind _Alloc to _CharT_alloc_type and
+	use it for the allocator typedefs.
+	* testsuite/21_strings/basic_string/1.cc: New.
+	* testsuite/23_containers/deque/explicit_instantiation.cc: Move to...
+	* testsuite/23_containers/deque/explicit_instantiation/1.cc: ... here.
+	* testsuite/23_containers/deque/explicit_instantiation/3.cc: New.
+	* testsuite/23_containers/list/explicit_instantiation.cc: Move to...
+	* testsuite/23_containers/list/explicit_instantiation/1.cc: ... here.
+	* testsuite/23_containers/list/explicit_instantiation/3.cc: New.
+	* testsuite/23_containers/map/explicit_instantiation.cc: Move to...
+	* testsuite/23_containers/map/explicit_instantiation/1.cc: ... here.
+	* testsuite/23_containers/map/explicit_instantiation/3.cc: New.
+	* testsuite/23_containers/multimap/explicit_instantiation.cc: Move to...
+	* testsuite/23_containers/multimap/explicit_instantiation/1.cc: .. here.
+	* testsuite/23_containers/multimap/explicit_instantiation/3.cc: New.
+	* testsuite/23_containers/multiset/explicit_instantiation.cc: Move to...
+	* testsuite/23_containers/multiset/explicit_instantiation/1.cc: .. here.
+	* testsuite/23_containers/multiset/explicit_instantiation/3.cc: New.
+	* testsuite/23_containers/set/explicit_instantiation.cc: Move to...
+	* testsuite/23_containers/set/explicit_instantiation/1.cc: .. here.
+	* testsuite/23_containers/set/explicit_instantiation/3.cc: New.
+	* testsuite/23_containers/vector/explicit_instantiation.cc: Move to...
+	* testsuite/23_containers/vector/explicit_instantiation/1.cc: ... here.
+	* testsuite/23_containers/vector/explicit_instantiation/3.cc: New.
+
 2005-06-02  Nathan Sidwell  <nathan@codesourcery.com>
 
 	PR c++/21280
diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index c889ce6..07b66d6 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -109,17 +109,19 @@ namespace std
   template<typename _CharT, typename _Traits, typename _Alloc>
     class basic_string
     {
+      typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
+
       // Types:
     public:
       typedef _Traits					    traits_type;
       typedef typename _Traits::char_type		    value_type;
       typedef _Alloc					    allocator_type;
-      typedef typename _Alloc::size_type		    size_type;
-      typedef typename _Alloc::difference_type		    difference_type;
-      typedef typename _Alloc::reference		    reference;
-      typedef typename _Alloc::const_reference		    const_reference;
-      typedef typename _Alloc::pointer			    pointer;
-      typedef typename _Alloc::const_pointer		    const_pointer;
+      typedef typename _CharT_alloc_type::size_type	    size_type;
+      typedef typename _CharT_alloc_type::difference_type   difference_type;
+      typedef typename _CharT_alloc_type::reference	    reference;
+      typedef typename _CharT_alloc_type::const_reference   const_reference;
+      typedef typename _CharT_alloc_type::pointer	    pointer;
+      typedef typename _CharT_alloc_type::const_pointer	    const_pointer;
       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
                                                             const_iterator;
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index c5440b2..35ceb69 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -147,7 +147,7 @@ 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,
-			    this->get_allocator());
+			    _M_get_Tp_allocator());
 	      _M_destroy_nodes(this->_M_impl._M_start._M_node,
 			       __new_start._M_node);
 	      this->_M_impl._M_start = __new_start;
@@ -157,7 +157,7 @@ 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,
-			    this->get_allocator());
+			    _M_get_Tp_allocator());
 	      _M_destroy_nodes(__new_finish._M_node + 1,
 			       this->_M_impl._M_finish._M_node + 1);
 	      this->_M_impl._M_finish = __new_finish;
@@ -176,7 +176,7 @@ namespace _GLIBCXX_STD
            ++__node)
 	{
 	  std::_Destroy(*__node, *__node + _S_buffer_size(),
-			this->get_allocator());
+			_M_get_Tp_allocator());
 	  _M_deallocate_node(*__node);
 	}
 
@@ -184,16 +184,16 @@ namespace _GLIBCXX_STD
 	{
 	  std::_Destroy(this->_M_impl._M_start._M_cur,
 			this->_M_impl._M_start._M_last,
-			this->get_allocator());
+			_M_get_Tp_allocator());
 	  std::_Destroy(this->_M_impl._M_finish._M_first,
 			this->_M_impl._M_finish._M_cur,
-			this->get_allocator());
+			_M_get_Tp_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->get_allocator());
+		      _M_get_Tp_allocator());
 
       this->_M_impl._M_finish = this->_M_impl._M_start;
     }
@@ -226,7 +226,7 @@ namespace _GLIBCXX_STD
 	    {
 	      std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
 					  __x,
-					  this->get_allocator());
+					  _M_get_Tp_allocator());
 	      this->_M_impl._M_start = __new_start;
 	    }
 	  catch(...)
@@ -243,7 +243,7 @@ namespace _GLIBCXX_STD
 	    {
 	      std::__uninitialized_fill_a(this->_M_impl._M_finish,
 					  __new_finish, __x,
-					  this->get_allocator());
+					  _M_get_Tp_allocator());
 	      this->_M_impl._M_finish = __new_finish;
 	    }
 	  catch(...)
@@ -269,15 +269,15 @@ namespace _GLIBCXX_STD
 	       __cur < this->_M_impl._M_finish._M_node;
 	       ++__cur)
             std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
-					__value, this->get_allocator());
+					__value, _M_get_Tp_allocator());
           std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
 				      this->_M_impl._M_finish._M_cur,
-				      __value, this->get_allocator());
+				      __value, _M_get_Tp_allocator());
         }
       catch(...)
         {
           std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
-			this->get_allocator());
+			_M_get_Tp_allocator());
           __throw_exception_again;
         }
     }
@@ -322,18 +322,18 @@ namespace _GLIBCXX_STD
               _ForwardIterator __mid = __first;
               std::advance(__mid, _S_buffer_size());
               std::__uninitialized_copy_a(__first, __mid, *__cur_node,
-					  this->get_allocator());
+					  _M_get_Tp_allocator());
               __first = __mid;
             }
             std::__uninitialized_copy_a(__first, __last,
 					this->_M_impl._M_finish._M_first,
-					this->get_allocator());
+					_M_get_Tp_allocator());
           }
         catch(...)
           {
             std::_Destroy(this->_M_impl._M_start,
 			  iterator(*__cur_node, __cur_node),
-			  this->get_allocator());
+			  _M_get_Tp_allocator());
             __throw_exception_again;
           }
       }
@@ -435,7 +435,7 @@ namespace _GLIBCXX_STD
 	    try
 	      {
 		std::__uninitialized_copy_a(__first, __last, __new_start,
-					    this->get_allocator());
+					    _M_get_Tp_allocator());
 		this->_M_impl._M_start = __new_start;
 	      }
 	    catch(...)
@@ -452,7 +452,7 @@ namespace _GLIBCXX_STD
 	      {
 		std::__uninitialized_copy_a(__first, __last,
 					    this->_M_impl._M_finish,
-					    this->get_allocator());
+					    _M_get_Tp_allocator());
 		this->_M_impl._M_finish = __new_finish;
 	      }
 	    catch(...)
@@ -520,7 +520,7 @@ namespace _GLIBCXX_STD
 					+ difference_type(__n));
 		  std::__uninitialized_copy_a(this->_M_impl._M_start,
 					      __start_n, __new_start,
-					      this->get_allocator());
+					      _M_get_Tp_allocator());
 		  this->_M_impl._M_start = __new_start;
 		  std::copy(__start_n, __pos, __old_start);
 		  fill(__pos - difference_type(__n), __pos, __x_copy);
@@ -531,7 +531,7 @@ namespace _GLIBCXX_STD
 						 __pos, __new_start,
 						 this->_M_impl._M_start,
 						 __x_copy,
-						 this->get_allocator());
+						 _M_get_Tp_allocator());
 		  this->_M_impl._M_start = __new_start;
 		  std::fill(__old_start, __pos, __x_copy);
 		}
@@ -559,7 +559,7 @@ namespace _GLIBCXX_STD
 		  std::__uninitialized_copy_a(__finish_n,
 					      this->_M_impl._M_finish,
 					      this->_M_impl._M_finish,
-					      this->get_allocator());
+					      _M_get_Tp_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);
@@ -570,7 +570,7 @@ namespace _GLIBCXX_STD
 						 __pos + difference_type(__n),
 						 __x_copy, __pos,
 						 this->_M_impl._M_finish,
-						 this->get_allocator());
+						 _M_get_Tp_allocator());
 		  this->_M_impl._M_finish = __new_finish;
 		  std::fill(__pos, __old_finish, __x_copy);
 		}
@@ -607,7 +607,7 @@ namespace _GLIBCXX_STD
 					  + difference_type(__n));
 		    std::__uninitialized_copy_a(this->_M_impl._M_start,
 						__start_n, __new_start,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		    this->_M_impl._M_start = __new_start;
 		    std::copy(__start_n, __pos, __old_start);
 		    std::copy(__first, __last, __pos - difference_type(__n));
@@ -619,7 +619,7 @@ namespace _GLIBCXX_STD
 		    std::__uninitialized_copy_copy(this->_M_impl._M_start,
 						   __pos, __first, __mid,
 						   __new_start,
-						   this->get_allocator());
+						   _M_get_Tp_allocator());
 		    this->_M_impl._M_start = __new_start;
 		    std::copy(__mid, __last, __old_start);
 		  }
@@ -647,7 +647,7 @@ namespace _GLIBCXX_STD
 		  std::__uninitialized_copy_a(__finish_n,
 					      this->_M_impl._M_finish,
 					      this->_M_impl._M_finish,
-					      this->get_allocator());
+					      _M_get_Tp_allocator());
 		  this->_M_impl._M_finish = __new_finish;
 		  std::copy_backward(__pos, __finish_n, __old_finish);
 		  std::copy(__first, __last, __pos);
@@ -659,7 +659,7 @@ namespace _GLIBCXX_STD
 		  std::__uninitialized_copy_copy(__mid, __last, __pos,
 						 this->_M_impl._M_finish,
 						 this->_M_impl._M_finish,
-						 this->get_allocator());
+						 _M_get_Tp_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 59f9d1a..14ea0f0 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);
-	  this->get_allocator().destroy(&__tmp->_M_data);
+	  _M_get_Tp_allocator().destroy(&__tmp->_M_data);
 	  _M_put_node(__tmp);
 	}
     }
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index fdee3d5..249c4f2 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -358,7 +358,7 @@ namespace _GLIBCXX_STD
 
       allocator_type
       get_allocator() const
-      { return *static_cast<const _Alloc*>(&this->_M_impl); }
+      { return _M_get_Tp_allocator(); }
 
       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
@@ -377,30 +377,43 @@ namespace _GLIBCXX_STD
       //This struct encapsulates the implementation of the std::deque
       //standard container and at the same time makes use of the EBO
       //for empty allocators.
+      typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
+
+      typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;
+
       struct _Deque_impl
-      : public _Alloc
+      : public _Tp_alloc_type
       {
 	_Tp** _M_map;
 	size_t _M_map_size;
 	iterator _M_start;
 	iterator _M_finish;
 
-	_Deque_impl(const _Alloc& __a)
-	: _Alloc(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish()
+	_Deque_impl(const _Tp_alloc_type& __a)
+	: _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
+	  _M_start(), _M_finish()
 	{ }
       };
 
-      typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
-      _Map_alloc_type _M_get_map_allocator() const
-      { return _Map_alloc_type(this->get_allocator()); }
+      _Tp_alloc_type
+      _M_get_Tp_allocator() const
+      { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
+
+      _Map_alloc_type
+      _M_get_map_allocator() const
+      { return _M_get_Tp_allocator(); }
 
       _Tp*
       _M_allocate_node()
-      { return _M_impl._Alloc::allocate(__deque_buf_size(sizeof(_Tp))); }
+      { 
+	return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
+      }
 
       void
       _M_deallocate_node(_Tp* __p)
-      { _M_impl._Alloc::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
+      {
+	_M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
+      }
 
       _Tp**
       _M_allocate_map(size_t __n)
@@ -595,23 +608,26 @@ namespace _GLIBCXX_STD
     class deque : protected _Deque_base<_Tp, _Alloc>
     {
       // concept requirements
+      typedef typename _Alloc::value_type        _Alloc_value_type;
       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
+      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
 
       typedef _Deque_base<_Tp, _Alloc>           _Base;
+      typedef typename _Base::_Tp_alloc_type	 _Tp_alloc_type;
 
     public:
-      typedef _Tp                                value_type;
-      typedef typename _Alloc::pointer           pointer;
-      typedef typename _Alloc::const_pointer     const_pointer;
-      typedef typename _Alloc::reference         reference;
-      typedef typename _Alloc::const_reference   const_reference;
-      typedef typename _Base::iterator           iterator;
-      typedef typename _Base::const_iterator     const_iterator;
-      typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
-      typedef std::reverse_iterator<iterator>         reverse_iterator;
+      typedef _Tp                                        value_type;
+      typedef typename _Tp_alloc_type::pointer           pointer;
+      typedef typename _Tp_alloc_type::const_pointer     const_pointer;
+      typedef typename _Tp_alloc_type::reference         reference;
+      typedef typename _Tp_alloc_type::const_reference   const_reference;
+      typedef typename _Base::iterator                   iterator;
+      typedef typename _Base::const_iterator             const_iterator;
+      typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
+      typedef std::reverse_iterator<iterator>            reverse_iterator;
       typedef size_t                             size_type;
       typedef ptrdiff_t                          difference_type;
-      typedef typename _Base::allocator_type     allocator_type;
+      typedef _Alloc                             allocator_type;
 
     protected:
       typedef pointer*                           _Map_pointer;
@@ -627,6 +643,7 @@ namespace _GLIBCXX_STD
       using _Base::_M_deallocate_node;
       using _Base::_M_allocate_map;
       using _Base::_M_deallocate_map;
+      using _Base::_M_get_Tp_allocator;
 
       /** @if maint
        *  A total of four data members accumulated down the heirarchy.
@@ -680,7 +697,7 @@ namespace _GLIBCXX_STD
       : _Base(__x.get_allocator(), __x.size())
       { std::__uninitialized_copy_a(__x.begin(), __x.end(), 
 				    this->_M_impl._M_start,
-				    this->get_allocator()); }
+				    _M_get_Tp_allocator()); }
 
       /**
        *  @brief  Builds a %deque from a range.
@@ -713,7 +730,7 @@ namespace _GLIBCXX_STD
        */
       ~deque()
       { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-		      this->get_allocator()); }
+		      _M_get_Tp_allocator()); }
 
       /**
        *  @brief  %Deque assignment operator.
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index ce167ef..8790480 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -290,18 +290,19 @@ namespace _GLIBCXX_STD
       //
       // We put this to the test in the constructors and in
       // get_allocator, where we use conversions between
-      // allocator_type and _Node_Alloc_type. The conversion is
+      // allocator_type and _Node_alloc_type. The conversion is
       // required by table 32 in [20.1.5].
       typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
+        _Node_alloc_type;
 
-      _Node_Alloc_type;
+      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
 
       struct _List_impl 
-      : public _Node_Alloc_type
+      : public _Node_alloc_type
       {
 	_List_node_base _M_node;
-	_List_impl (const _Node_Alloc_type& __a)
-	: _Node_Alloc_type(__a)
+	_List_impl(const _Node_alloc_type& __a)
+	: _Node_alloc_type(__a)
 	{ }
       };
 
@@ -309,19 +310,22 @@ namespace _GLIBCXX_STD
 
       _List_node<_Tp>*
       _M_get_node()
-      { return _M_impl._Node_Alloc_type::allocate(1); }
+      { return _M_impl._Node_alloc_type::allocate(1); }
       
       void
       _M_put_node(_List_node<_Tp>* __p)
-      { _M_impl._Node_Alloc_type::deallocate(__p, 1); }
+      { _M_impl._Node_alloc_type::deallocate(__p, 1); }
       
   public:
       typedef _Alloc allocator_type;
 
+      _Tp_alloc_type
+      _M_get_Tp_allocator() const
+      { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); }
+
       allocator_type
       get_allocator() const
-      { return allocator_type(*static_cast<
-			      const _Node_Alloc_type*>(&this->_M_impl)); }
+      { return _M_get_Tp_allocator(); }
 
       _List_base(const allocator_type& __a)
       : _M_impl(__a)
@@ -391,28 +395,31 @@ namespace _GLIBCXX_STD
     class list : protected _List_base<_Tp, _Alloc>
     {
       // concept requirements
+      typedef typename _Alloc::value_type                _Alloc_value_type;
       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
+      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
 
-      typedef _List_base<_Tp, _Alloc>                   _Base;
+      typedef _List_base<_Tp, _Alloc>                    _Base;
+      typedef typename _Base::_Tp_alloc_type		 _Tp_alloc_type;
 
     public:
       typedef _Tp                                        value_type;
-      typedef typename _Alloc::pointer                   pointer;
-      typedef typename _Alloc::const_pointer             const_pointer;
-      typedef typename _Alloc::reference                 reference;
-      typedef typename _Alloc::const_reference           const_reference;
+      typedef typename _Tp_alloc_type::pointer           pointer;
+      typedef typename _Tp_alloc_type::const_pointer     const_pointer;
+      typedef typename _Tp_alloc_type::reference         reference;
+      typedef typename _Tp_alloc_type::const_reference   const_reference;
       typedef _List_iterator<_Tp>                        iterator;
       typedef _List_const_iterator<_Tp>                  const_iterator;
       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
       typedef std::reverse_iterator<iterator>            reverse_iterator;
       typedef size_t                                     size_type;
       typedef ptrdiff_t                                  difference_type;
-      typedef typename _Base::allocator_type             allocator_type;
+      typedef _Alloc                                     allocator_type;
 
     protected:
       // Note that pointers-to-_Node's can be ctor-converted to
       // iterator types.
-      typedef _List_node<_Tp>				_Node;
+      typedef _List_node<_Tp>				 _Node;
 
       /** @if maint
        *  One data member plus two memory-handling functions.  If the
@@ -423,6 +430,7 @@ namespace _GLIBCXX_STD
       using _Base::_M_impl;
       using _Base::_M_put_node;
       using _Base::_M_get_node;
+      using _Base::_M_get_Tp_allocator;
 
       /**
        *  @if maint
@@ -437,7 +445,7 @@ namespace _GLIBCXX_STD
 	_Node* __p = this->_M_get_node();
 	try
 	  {
-	    this->get_allocator().construct(&__p->_M_data, __x);
+	    _M_get_Tp_allocator().construct(&__p->_M_data, __x);
 	  }
 	catch(...)
 	  {
@@ -1158,7 +1166,7 @@ namespace _GLIBCXX_STD
       {
         __position._M_node->unhook();
         _Node* __n = static_cast<_Node*>(__position._M_node);
-        this->get_allocator().destroy(&__n->_M_data);
+        _M_get_Tp_allocator().destroy(&__n->_M_data);
         _M_put_node(__n);
       }
     };
diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index a0834a7..5f4be56 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -90,21 +90,26 @@ namespace _GLIBCXX_STD
             typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
     class map
     {
-      // concept requirements
-      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
-      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
-				_BinaryFunctionConcept)
-
     public:
       typedef _Key                                          key_type;
       typedef _Tp                                           mapped_type;
       typedef std::pair<const _Key, _Tp>                    value_type;
       typedef _Compare                                      key_compare;
+      typedef _Alloc                                        allocator_type;
+
+    private:
+      // concept requirements
+      typedef typename _Alloc::value_type                   _Alloc_value_type;
+      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
+      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
+				_BinaryFunctionConcept)
+      __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
 
+    public:
       class value_compare
       : public std::binary_function<value_type, value_type, bool>
       {
-	friend class map<_Key,_Tp,_Compare,_Alloc>;
+	friend class map<_Key, _Tp, _Compare, _Alloc>;
       protected:
 	_Compare comp;
 
@@ -118,19 +123,22 @@ namespace _GLIBCXX_STD
 
     private:
       /// @if maint  This turns a red-black tree into a [multi]map.  @endif
-      typedef _Rb_tree<key_type, value_type,
-		       _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
+      typedef typename _Alloc::template rebind<value_type>::other 
+        _Pair_alloc_type;
+
+      typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
+		       key_compare, _Pair_alloc_type> _Rep_type;
+
       /// @if maint  The actual tree structure.  @endif
       _Rep_type _M_t;
 
     public:
       // many of these are specified differently in ISO, but the following are
       // "functionally equivalent"
-      typedef typename _Alloc::pointer                   pointer;
-      typedef typename _Alloc::const_pointer             const_pointer;
-      typedef typename _Alloc::reference                 reference;
-      typedef typename _Alloc::const_reference           const_reference;
-      typedef typename _Rep_type::allocator_type         allocator_type;
+      typedef typename _Pair_alloc_type::pointer         pointer;
+      typedef typename _Pair_alloc_type::const_pointer   const_pointer;
+      typedef typename _Pair_alloc_type::reference       reference;
+      typedef typename _Pair_alloc_type::const_reference const_reference;
       typedef typename _Rep_type::iterator               iterator;
       typedef typename _Rep_type::const_iterator         const_iterator;
       typedef typename _Rep_type::size_type              size_type;
@@ -589,7 +597,7 @@ namespace _GLIBCXX_STD
        *
        *  This function probably only makes sense for multimaps.
        */
-      std::pair<iterator,iterator>
+      std::pair<iterator, iterator>
       equal_range(const key_type& __x)
       { return _M_t.equal_range(__x); }
 
@@ -608,19 +616,19 @@ namespace _GLIBCXX_STD
        *
        *  This function probably only makes sense for multimaps.
        */
-      std::pair<const_iterator,const_iterator>
+      std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
 
       template <typename _K1, typename _T1, typename _C1, typename _A1>
         friend bool
-        operator== (const map<_K1,_T1,_C1,_A1>&,
-		    const map<_K1,_T1,_C1,_A1>&);
+        operator== (const map<_K1, _T1, _C1, _A1>&,
+		    const map<_K1, _T1, _C1, _A1>&);
 
       template <typename _K1, typename _T1, typename _C1, typename _A1>
         friend bool
-        operator< (const map<_K1,_T1,_C1,_A1>&,
-		   const map<_K1,_T1,_C1,_A1>&);
+        operator< (const map<_K1, _T1, _C1, _A1>&,
+		   const map<_K1, _T1, _C1, _A1>&);
     };
 
   /**
@@ -635,8 +643,8 @@ namespace _GLIBCXX_STD
   */
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
-               const map<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x,
+               const map<_Key, _Tp, _Compare, _Alloc>& __y)
     { return __x._M_t == __y._M_t; }
 
   /**
@@ -652,42 +660,43 @@ namespace _GLIBCXX_STD
   */
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
-              const map<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x,
+              const map<_Key, _Tp, _Compare, _Alloc>& __y)
     { return __x._M_t < __y._M_t; }
 
   /// Based on operator==
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
-               const map<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
+               const map<_Key, _Tp, _Compare, _Alloc>& __y)
     { return !(__x == __y); }
 
   /// Based on operator<
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
-              const map<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x,
+              const map<_Key, _Tp, _Compare, _Alloc>& __y)
     { return __y < __x; }
 
   /// Based on operator<
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
-               const map<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
+               const map<_Key, _Tp, _Compare, _Alloc>& __y)
     { return !(__y < __x); }
 
   /// Based on operator<
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
-               const map<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x,
+               const map<_Key, _Tp, _Compare, _Alloc>& __y)
     { return !(__x < __y); }
 
   /// See std::map::swap().
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline void
-    swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y)
+    swap(map<_Key, _Tp, _Compare, _Alloc>& __x,
+	 map<_Key, _Tp, _Compare, _Alloc>& __y)
     { __x.swap(__y); }
 } // namespace std
 
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 524b236..dca9556 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -74,13 +74,13 @@ namespace _GLIBCXX_STD
 
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-	       const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
+    operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+	       const multimap<_Key, _Tp, _Compare, _Alloc>& __y);
 
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-	      const multimap<_Key,_Tp,_Compare,_Alloc>& __y);
+    operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+	      const multimap<_Key, _Tp, _Compare, _Alloc>& __y);
 
   /**
    *  @brief A standard container made up of (key,value) pairs, which can be
@@ -106,21 +106,26 @@ namespace _GLIBCXX_STD
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     class multimap
     {
-      // concept requirements
-      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
-      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
-				_BinaryFunctionConcept)
-
     public:
       typedef _Key                                          key_type;
       typedef _Tp                                           mapped_type;
       typedef std::pair<const _Key, _Tp>                    value_type;
       typedef _Compare                                      key_compare;
+      typedef _Alloc                                        allocator_type;
 
+    private:
+      // concept requirements
+      typedef typename _Alloc::value_type                   _Alloc_value_type;
+      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
+      __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
+				_BinaryFunctionConcept)
+      __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)	
+
+    public:
       class value_compare
       : public std::binary_function<value_type, value_type, bool>
       {
-	friend class multimap<_Key,_Tp,_Compare,_Alloc>;
+	friend class multimap<_Key, _Tp, _Compare, _Alloc>;
       protected:
 	_Compare comp;
 
@@ -134,19 +139,21 @@ namespace _GLIBCXX_STD
 
     private:
       /// @if maint  This turns a red-black tree into a [multi]map.  @endif
-      typedef _Rb_tree<key_type, value_type,
-		       _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
+      typedef typename _Alloc::template rebind<value_type>::other 
+        _Pair_alloc_type;
+
+      typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
+		       key_compare, _Pair_alloc_type> _Rep_type;
       /// @if maint  The actual tree structure.  @endif
       _Rep_type _M_t;
 
     public:
       // many of these are specified differently in ISO, but the following are
       // "functionally equivalent"
-      typedef typename _Alloc::pointer                   pointer;
-      typedef typename _Alloc::const_pointer             const_pointer;
-      typedef typename _Alloc::reference                 reference;
-      typedef typename _Alloc::const_reference           const_reference;
-      typedef typename _Rep_type::allocator_type         allocator_type;
+      typedef typename _Pair_alloc_type::pointer         pointer;
+      typedef typename _Pair_alloc_type::const_pointer   const_pointer;
+      typedef typename _Pair_alloc_type::reference       reference;
+      typedef typename _Pair_alloc_type::const_reference const_reference;
       typedef typename _Rep_type::iterator               iterator;
       typedef typename _Rep_type::const_iterator         const_iterator;
       typedef typename _Rep_type::size_type              size_type;
@@ -573,7 +580,7 @@ namespace _GLIBCXX_STD
        *  @endcode
        *  (but is faster than making the calls separately).
        */
-      std::pair<iterator,iterator>
+      std::pair<iterator, iterator>
       equal_range(const key_type& __x)
       { return _M_t.equal_range(__x); }
 
@@ -590,19 +597,19 @@ namespace _GLIBCXX_STD
        *  @endcode
        *  (but is faster than making the calls separately).
        */
-      std::pair<const_iterator,const_iterator>
+      std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
 
       template <typename _K1, typename _T1, typename _C1, typename _A1>
         friend bool
-        operator== (const multimap<_K1,_T1,_C1,_A1>&,
-		    const multimap<_K1,_T1,_C1,_A1>&);
+        operator== (const multimap<_K1, _T1, _C1, _A1>&,
+		    const multimap<_K1, _T1, _C1, _A1>&);
 
       template <typename _K1, typename _T1, typename _C1, typename _A1>
         friend bool
-        operator< (const multimap<_K1,_T1,_C1,_A1>&,
-		   const multimap<_K1,_T1,_C1,_A1>&);
+        operator< (const multimap<_K1, _T1, _C1, _A1>&,
+		   const multimap<_K1, _T1, _C1, _A1>&);
   };
 
   /**
@@ -617,8 +624,8 @@ namespace _GLIBCXX_STD
   */
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-               const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
     { return __x._M_t == __y._M_t; }
 
   /**
@@ -634,43 +641,43 @@ namespace _GLIBCXX_STD
   */
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-              const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+              const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
     { return __x._M_t < __y._M_t; }
 
   /// Based on operator==
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-               const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
     { return !(__x == __y); }
 
   /// Based on operator<
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-              const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+              const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
     { return __y < __x; }
 
   /// Based on operator<
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-               const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
     { return !(__y < __x); }
 
   /// Based on operator<
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline bool
-    operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-               const multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+    operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+               const multimap<_Key, _Tp, _Compare, _Alloc>& __y)
     { return !(__x < __y); }
 
   /// See std::multimap::swap().
   template <typename _Key, typename _Tp, typename _Compare, typename _Alloc>
     inline void
-    swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
-         multimap<_Key,_Tp,_Compare,_Alloc>& __y)
+    swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x,
+         multimap<_Key, _Tp, _Compare, _Alloc>& __y)
     { __x.swap(__y); }
 } // namespace std
 
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index 3f42ef4..f401db7 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -73,13 +73,13 @@ namespace _GLIBCXX_STD
 
   template <class _Key, class _Compare, class _Alloc>
     inline bool
-    operator==(const multiset<_Key,_Compare,_Alloc>& __x,
-	       const multiset<_Key,_Compare,_Alloc>& __y);
+    operator==(const multiset<_Key, _Compare, _Alloc>& __x,
+	       const multiset<_Key, _Compare, _Alloc>& __y);
 
   template <class _Key, class _Compare, class _Alloc>
     inline bool
-    operator<(const multiset<_Key,_Compare,_Alloc>& __x,
-	      const multiset<_Key,_Compare,_Alloc>& __y);
+    operator<(const multiset<_Key, _Compare, _Alloc>& __x,
+	      const multiset<_Key, _Compare, _Alloc>& __y);
 
   /**
    *  @brief A standard container made up of elements, which can be retrieved
@@ -105,9 +105,11 @@ namespace _GLIBCXX_STD
     class multiset
     {
       // concept requirements
+      typedef typename _Alloc::value_type                   _Alloc_value_type;
       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
 				_BinaryFunctionConcept)
+      __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)	
 
     public:
       // typedefs:
@@ -115,35 +117,37 @@ namespace _GLIBCXX_STD
       typedef _Key     value_type;
       typedef _Compare key_compare;
       typedef _Compare value_compare;
+      typedef _Alloc   allocator_type;
 
     private:
       /// @if maint  This turns a red-black tree into a [multi]set.  @endif
-      typedef _Rb_tree<key_type, value_type,
-		       _Identity<value_type>, key_compare, _Alloc> _Rep_type;
+      typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
+
+      typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
+		       key_compare, _Key_alloc_type> _Rep_type;
       /// @if maint  The actual tree structure.  @endif
       _Rep_type _M_t;
 
     public:
-      typedef typename _Alloc::pointer pointer;
-      typedef typename _Alloc::const_pointer const_pointer;
-      typedef typename _Alloc::reference reference;
-      typedef typename _Alloc::const_reference const_reference;
+      typedef typename _Key_alloc_type::pointer             pointer;
+      typedef typename _Key_alloc_type::const_pointer       const_pointer;
+      typedef typename _Key_alloc_type::reference           reference;
+      typedef typename _Key_alloc_type::const_reference     const_reference;
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // DR 103. set::iterator is required to be modifiable,
       // but this allows modification of keys.
-      typedef typename _Rep_type::const_iterator iterator;
-      typedef typename _Rep_type::const_iterator const_iterator;
-      typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
-      typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
-      typedef typename _Rep_type::size_type size_type;
-      typedef typename _Rep_type::difference_type difference_type;
-      typedef typename _Rep_type::allocator_type allocator_type;
-
-    // allocation/deallocation
-
-    /**
-     *  @brief  Default constructor creates no elements.
-     */
+      typedef typename _Rep_type::const_iterator            iterator;
+      typedef typename _Rep_type::const_iterator            const_iterator;
+      typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
+      typedef typename _Rep_type::const_reverse_iterator    const_reverse_iterator;
+      typedef typename _Rep_type::size_type                 size_type;
+      typedef typename _Rep_type::difference_type           difference_type;
+
+      // allocation/deallocation
+
+      /**
+       *  @brief  Default constructor creates no elements.
+       */
       multiset()
       : _M_t(_Compare(), allocator_type()) { }
 
@@ -286,7 +290,7 @@ namespace _GLIBCXX_STD
        *  std::swap(s1,s2) will feed to this function.
        */
       void
-      swap(multiset<_Key,_Compare,_Alloc>& __x)
+      swap(multiset<_Key, _Compare, _Alloc>& __x)
       { _M_t.swap(__x._M_t); }
 
       // insert/erase
@@ -492,23 +496,23 @@ namespace _GLIBCXX_STD
        *
        *  This function probably only makes sense for multisets.
        */
-      std::pair<iterator,iterator>
+      std::pair<iterator, iterator>
       equal_range(const key_type& __x)
       { return _M_t.equal_range(__x); }
 
-      std::pair<const_iterator,const_iterator>
+      std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
 
       template <class _K1, class _C1, class _A1>
         friend bool
-        operator== (const multiset<_K1,_C1,_A1>&,
-		    const multiset<_K1,_C1,_A1>&);
+        operator== (const multiset<_K1, _C1, _A1>&,
+		    const multiset<_K1, _C1, _A1>&);
 
       template <class _K1, class _C1, class _A1>
         friend bool
-        operator< (const multiset<_K1,_C1,_A1>&,
-		   const multiset<_K1,_C1,_A1>&);
+        operator< (const multiset<_K1, _C1, _A1>&,
+		   const multiset<_K1, _C1, _A1>&);
     };
 
   /**
@@ -524,8 +528,8 @@ namespace _GLIBCXX_STD
   */
   template <class _Key, class _Compare, class _Alloc>
     inline bool
-    operator==(const multiset<_Key,_Compare,_Alloc>& __x,
-	       const multiset<_Key,_Compare,_Alloc>& __y)
+    operator==(const multiset<_Key, _Compare, _Alloc>& __x,
+	       const multiset<_Key, _Compare, _Alloc>& __y)
     { return __x._M_t == __y._M_t; }
 
   /**
@@ -541,15 +545,15 @@ namespace _GLIBCXX_STD
   */
   template <class _Key, class _Compare, class _Alloc>
     inline bool
-    operator<(const multiset<_Key,_Compare,_Alloc>& __x,
-	      const multiset<_Key,_Compare,_Alloc>& __y)
+    operator<(const multiset<_Key, _Compare, _Alloc>& __x,
+	      const multiset<_Key, _Compare, _Alloc>& __y)
     { return __x._M_t < __y._M_t; }
 
   ///  Returns !(x == y).
   template <class _Key, class _Compare, class _Alloc>
     inline bool
-    operator!=(const multiset<_Key,_Compare,_Alloc>& __x,
-	       const multiset<_Key,_Compare,_Alloc>& __y)
+    operator!=(const multiset<_Key, _Compare, _Alloc>& __x,
+	       const multiset<_Key, _Compare, _Alloc>& __y)
     { return !(__x == __y); }
 
   ///  Returns y < x.
@@ -562,22 +566,22 @@ namespace _GLIBCXX_STD
   ///  Returns !(y < x)
   template <class _Key, class _Compare, class _Alloc>
     inline bool
-    operator<=(const multiset<_Key,_Compare,_Alloc>& __x,
-	       const multiset<_Key,_Compare,_Alloc>& __y)
+    operator<=(const multiset<_Key, _Compare, _Alloc>& __x,
+	       const multiset<_Key, _Compare, _Alloc>& __y)
     { return !(__y < __x); }
 
   ///  Returns !(x < y)
   template <class _Key, class _Compare, class _Alloc>
     inline bool
-    operator>=(const multiset<_Key,_Compare,_Alloc>& __x,
-	       const multiset<_Key,_Compare,_Alloc>& __y)
+    operator>=(const multiset<_Key, _Compare, _Alloc>& __x,
+	       const multiset<_Key, _Compare, _Alloc>& __y)
     { return !(__x < __y); }
 
   /// See std::multiset::swap().
   template <class _Key, class _Compare, class _Alloc>
     inline void
-    swap(multiset<_Key,_Compare,_Alloc>& __x,
-	 multiset<_Key,_Compare,_Alloc>& __y)
+    swap(multiset<_Key, _Compare, _Alloc>& __x,
+	 multiset<_Key, _Compare, _Alloc>& __y)
     { __x.swap(__y); }
 
 } // namespace std
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index 1a15d11..c76e554 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -72,13 +72,13 @@ namespace _GLIBCXX_STD
 
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator==(const set<_Key,_Compare,_Alloc>& __x,
-	       const set<_Key,_Compare,_Alloc>& __y);
+    operator==(const set<_Key, _Compare, _Alloc>& __x,
+	       const set<_Key, _Compare, _Alloc>& __y);
 
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator<(const set<_Key,_Compare,_Alloc>& __x,
-	      const set<_Key,_Compare,_Alloc>& __y);
+    operator<(const set<_Key, _Compare, _Alloc>& __x,
+	      const set<_Key, _Compare, _Alloc>& __y);
 
   /**
    *  @brief A standard container made up of unique keys, which can be
@@ -107,9 +107,11 @@ namespace _GLIBCXX_STD
     class set
     {
       // concept requirements
+      typedef typename _Alloc::value_type                   _Alloc_value_type;
       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
       __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
 				_BinaryFunctionConcept)
+      __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)	
 
     public:
       // typedefs:
@@ -119,29 +121,32 @@ namespace _GLIBCXX_STD
       typedef _Key     value_type;
       typedef _Compare key_compare;
       typedef _Compare value_compare;
+      typedef _Alloc   allocator_type;
       //@}
 
     private:
-      typedef _Rb_tree<key_type, value_type,
-		       _Identity<value_type>, key_compare, _Alloc> _Rep_type;
+      typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
+
+      typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
+		       key_compare, _Key_alloc_type> _Rep_type;
       _Rep_type _M_t;  // red-black tree representing set
+
     public:
       //@{
       ///  Iterator-related typedefs.
-      typedef typename _Alloc::pointer pointer;
-      typedef typename _Alloc::const_pointer const_pointer;
-      typedef typename _Alloc::reference reference;
-      typedef typename _Alloc::const_reference const_reference;
+      typedef typename _Key_alloc_type::pointer             pointer;
+      typedef typename _Key_alloc_type::const_pointer       const_pointer;
+      typedef typename _Key_alloc_type::reference           reference;
+      typedef typename _Key_alloc_type::const_reference     const_reference;
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // DR 103. set::iterator is required to be modifiable,
       // but this allows modification of keys.
-      typedef typename _Rep_type::const_iterator iterator;
-      typedef typename _Rep_type::const_iterator const_iterator;
-      typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
-      typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
-      typedef typename _Rep_type::size_type size_type;
-      typedef typename _Rep_type::difference_type difference_type;
-      typedef typename _Rep_type::allocator_type allocator_type;
+      typedef typename _Rep_type::const_iterator            iterator;
+      typedef typename _Rep_type::const_iterator            const_iterator;
+      typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
+      typedef typename _Rep_type::const_reverse_iterator    const_reverse_iterator;
+      typedef typename _Rep_type::size_type                 size_type;
+      typedef typename _Rep_type::difference_type           difference_type;
       //@}
 
       // allocation/deallocation
@@ -155,8 +160,9 @@ namespace _GLIBCXX_STD
        *  @param  comp  Comparator to use.
        *  @param  a  Allocator to use.
        */
-      explicit set(const _Compare& __comp,
-		   const allocator_type& __a = allocator_type())
+      explicit
+      set(const _Compare& __comp,
+	  const allocator_type& __a = allocator_type())
       : _M_t(__comp, __a) {}
 
       /**
@@ -503,22 +509,22 @@ namespace _GLIBCXX_STD
        *
        *  This function probably only makes sense for multisets.
        */
-      std::pair<iterator,iterator>
+      std::pair<iterator, iterator>
       equal_range(const key_type& __x)
       { return _M_t.equal_range(__x); }
 
-      std::pair<const_iterator,const_iterator>
+      std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
       //@}
 
       template<class _K1, class _C1, class _A1>
         friend bool
-        operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
+        operator== (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
 
       template<class _K1, class _C1, class _A1>
         friend bool
-        operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
+        operator< (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&);
     };
 
 
@@ -534,8 +540,8 @@ namespace _GLIBCXX_STD
   */
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator==(const set<_Key,_Compare,_Alloc>& __x,
-	       const set<_Key,_Compare,_Alloc>& __y)
+    operator==(const set<_Key, _Compare, _Alloc>& __x,
+	       const set<_Key, _Compare, _Alloc>& __y)
     { return __x._M_t == __y._M_t; }
 
   /**
@@ -551,42 +557,42 @@ namespace _GLIBCXX_STD
   */
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator<(const set<_Key,_Compare,_Alloc>& __x,
-	      const set<_Key,_Compare,_Alloc>& __y)
+    operator<(const set<_Key, _Compare, _Alloc>& __x,
+	      const set<_Key, _Compare, _Alloc>& __y)
     { return __x._M_t < __y._M_t; }
 
   ///  Returns !(x == y).
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator!=(const set<_Key,_Compare,_Alloc>& __x,
-	       const set<_Key,_Compare,_Alloc>& __y)
+    operator!=(const set<_Key, _Compare, _Alloc>& __x,
+	       const set<_Key, _Compare, _Alloc>& __y)
     { return !(__x == __y); }
 
   ///  Returns y < x.
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator>(const set<_Key,_Compare,_Alloc>& __x,
-	      const set<_Key,_Compare,_Alloc>& __y)
+    operator>(const set<_Key, _Compare, _Alloc>& __x,
+	      const set<_Key, _Compare, _Alloc>& __y)
     { return __y < __x; }
 
   ///  Returns !(y < x)
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator<=(const set<_Key,_Compare,_Alloc>& __x,
-	       const set<_Key,_Compare,_Alloc>& __y)
+    operator<=(const set<_Key, _Compare, _Alloc>& __x,
+	       const set<_Key, _Compare, _Alloc>& __y)
     { return !(__y < __x); }
 
   ///  Returns !(x < y)
   template<class _Key, class _Compare, class _Alloc>
     inline bool
-    operator>=(const set<_Key,_Compare,_Alloc>& __x,
-	       const set<_Key,_Compare,_Alloc>& __y)
+    operator>=(const set<_Key, _Compare, _Alloc>& __x,
+	       const set<_Key, _Compare, _Alloc>& __y)
     { return !(__x < __y); }
 
   /// See std::set::swap().
   template<class _Key, class _Compare, class _Alloc>
     inline void
-    swap(set<_Key,_Compare,_Alloc>& __x, set<_Key,_Compare,_Alloc>& __y)
+    swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y)
     { __x.swap(__y); }
 
 } // namespace std
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index d532c2d..dccc9dd 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -75,23 +75,29 @@ namespace _GLIBCXX_STD
   template<typename _Tp, typename _Alloc>
     struct _Vector_base
     {
+      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
+
       struct _Vector_impl 
-      : public _Alloc
+      : public _Tp_alloc_type
       {
 	_Tp*           _M_start;
 	_Tp*           _M_finish;
 	_Tp*           _M_end_of_storage;
-	_Vector_impl(_Alloc const& __a)
-	: _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
+	_Vector_impl(_Tp_alloc_type const& __a)
+	: _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
 	{ }
       };
       
     public:
       typedef _Alloc allocator_type;
 
+      _Tp_alloc_type
+      _M_get_Tp_allocator() const
+      { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
+
       allocator_type
       get_allocator() const
-      { return *static_cast<const _Alloc*>(&this->_M_impl); }
+      { return _M_get_Tp_allocator(); }
 
       _Vector_base(const allocator_type& __a)
       : _M_impl(__a)
@@ -148,17 +154,20 @@ namespace _GLIBCXX_STD
     class vector : protected _Vector_base<_Tp, _Alloc>
     {
       // Concept requirements.
+      typedef typename _Alloc::value_type                _Alloc_value_type;
       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
-
-      typedef _Vector_base<_Tp, _Alloc>			_Base;
-      typedef vector<_Tp, _Alloc>			vector_type;
+      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
+      
+      typedef _Vector_base<_Tp, _Alloc>			 _Base;
+      typedef vector<_Tp, _Alloc>			 vector_type;
+      typedef typename _Base::_Tp_alloc_type		 _Tp_alloc_type;
 
     public:
       typedef _Tp					 value_type;
-      typedef typename _Alloc::pointer                   pointer;
-      typedef typename _Alloc::const_pointer             const_pointer;
-      typedef typename _Alloc::reference                 reference;
-      typedef typename _Alloc::const_reference           const_reference;
+      typedef typename _Tp_alloc_type::pointer           pointer;
+      typedef typename _Tp_alloc_type::const_pointer     const_pointer;
+      typedef typename _Tp_alloc_type::reference         reference;
+      typedef typename _Tp_alloc_type::const_reference   const_reference;
       typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
       typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
       const_iterator;
@@ -166,7 +175,7 @@ namespace _GLIBCXX_STD
       typedef std::reverse_iterator<iterator>		 reverse_iterator;
       typedef size_t					 size_type;
       typedef ptrdiff_t					 difference_type;
-      typedef typename _Base::allocator_type		 allocator_type;
+      typedef _Alloc                        		 allocator_type;
 
     protected:
       /** @if maint
@@ -177,6 +186,7 @@ namespace _GLIBCXX_STD
       using _Base::_M_allocate;
       using _Base::_M_deallocate;
       using _Base::_M_impl;
+      using _Base::_M_get_Tp_allocator;
 
     public:
       // [23.2.4.1] construct/copy/destroy
@@ -201,7 +211,7 @@ namespace _GLIBCXX_STD
       : _Base(__n, __a)
       {
 	std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
-				      this->get_allocator());
+				      _M_get_Tp_allocator());
 	this->_M_impl._M_finish = this->_M_impl._M_start + __n;
       }
 
@@ -217,7 +227,7 @@ namespace _GLIBCXX_STD
       : _Base(__n, allocator_type())
       {
 	std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, value_type(),
-				      this->get_allocator());
+				      _M_get_Tp_allocator());
 	this->_M_impl._M_finish = this->_M_impl._M_start + __n;	
       }
 
@@ -235,7 +245,7 @@ namespace _GLIBCXX_STD
       { this->_M_impl._M_finish =
 	  std::__uninitialized_copy_a(__x.begin(), __x.end(),
 				      this->_M_impl._M_start,
-				      this->get_allocator());
+				      _M_get_Tp_allocator());
       }
 
       /**
@@ -271,7 +281,7 @@ namespace _GLIBCXX_STD
        */
       ~vector()
       { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-		      this->get_allocator());
+		      _M_get_Tp_allocator());
       }
 
       /**
@@ -764,7 +774,7 @@ namespace _GLIBCXX_STD
 	  try
 	    {
 	      std::__uninitialized_copy_a(__first, __last, __result,
-					  this->get_allocator());
+					  _M_get_Tp_allocator());
 	      return __result;
 	    }
 	  catch(...)
@@ -785,7 +795,7 @@ 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_a(this->_M_impl._M_start, __n, __value,
-					this->get_allocator());
+					_M_get_Tp_allocator());
 	  this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
 	}
 
@@ -822,7 +832,7 @@ namespace _GLIBCXX_STD
 	  this->_M_impl._M_finish =
 	    std::__uninitialized_copy_a(__first, __last,
 					this->_M_impl._M_start,
-					this->get_allocator());
+					_M_get_Tp_allocator());
 	}
 
 
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index f9f5e5a..aa1634b 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -77,7 +77,7 @@ namespace _GLIBCXX_STD
 					       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_get_Tp_allocator());
 	  _M_deallocate(this->_M_impl._M_start,
 			this->_M_impl._M_end_of_storage
 			- this->_M_impl._M_start);
@@ -122,7 +122,7 @@ namespace _GLIBCXX_STD
     erase(iterator __first, iterator __last)
     {
       iterator __i(std::copy(__last, end(), __first));
-      std::_Destroy(__i, end(), this->get_allocator());
+      std::_Destroy(__i, end(), _M_get_Tp_allocator());
       this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first);
       return __first;
     }
@@ -140,7 +140,7 @@ 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,
-			    this->get_allocator());
+			    _M_get_Tp_allocator());
 	      _M_deallocate(this->_M_impl._M_start,
 			    this->_M_impl._M_end_of_storage
 			    - this->_M_impl._M_start);
@@ -150,7 +150,7 @@ namespace _GLIBCXX_STD
 	  else if (size() >= __xlen)
 	    {
 	      iterator __i(std::copy(__x.begin(), __x.end(), begin()));
-	      std::_Destroy(__i, end(), this->get_allocator());
+	      std::_Destroy(__i, end(), _M_get_Tp_allocator());
 	    }
 	  else
 	    {
@@ -158,7 +158,7 @@ namespace _GLIBCXX_STD
 			this->_M_impl._M_start);
 	      std::__uninitialized_copy_a(__x.begin() + size(),
 					  __x.end(), this->_M_impl._M_finish,
-					  this->get_allocator());
+					  _M_get_Tp_allocator());
 	    }
 	  this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
 	}
@@ -172,7 +172,7 @@ namespace _GLIBCXX_STD
     {
       if (__n > capacity())
 	{
-	  vector __tmp(__n, __val, get_allocator());
+	  vector __tmp(__n, __val, _M_get_Tp_allocator());
 	  __tmp.swap(*this);
 	}
       else if (__n > size())
@@ -180,7 +180,7 @@ namespace _GLIBCXX_STD
 	  std::fill(begin(), end(), __val);
 	  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 					__n - size(), __val,
-					this->get_allocator());
+					_M_get_Tp_allocator());
 	  this->_M_impl._M_finish += __n - size();
 	}
       else
@@ -216,7 +216,7 @@ namespace _GLIBCXX_STD
 	  {
 	    pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
 	    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-			  this->get_allocator());
+			  _M_get_Tp_allocator());
 	    _M_deallocate(this->_M_impl._M_start,
 			  this->_M_impl._M_end_of_storage
 			  - this->_M_impl._M_start);
@@ -228,7 +228,7 @@ namespace _GLIBCXX_STD
 	  {
 	    iterator __new_finish(std::copy(__first, __last,
 				       this->_M_impl._M_start));
-	    std::_Destroy(__new_finish, end(), this->get_allocator());
+	    std::_Destroy(__new_finish, end(), _M_get_Tp_allocator());
 	    this->_M_impl._M_finish = __new_finish.base();
 	  }
 	else
@@ -239,7 +239,7 @@ namespace _GLIBCXX_STD
 	    this->_M_impl._M_finish =
 	      std::__uninitialized_copy_a(__mid, __last,
 					  this->_M_impl._M_finish,
-					  this->get_allocator());
+					  _M_get_Tp_allocator());
 	  }
       }
 
@@ -280,22 +280,22 @@ namespace _GLIBCXX_STD
 		std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
 					    __position,
 					    __new_start,
-					    this->get_allocator());
+					    _M_get_Tp_allocator());
 	      this->_M_impl.construct(__new_finish.base(), __x);
 	      ++__new_finish;
 	      __new_finish =
 		std::__uninitialized_copy_a(__position,
 					    iterator(this->_M_impl._M_finish),
 					    __new_finish,
-					    this->get_allocator());
+					    _M_get_Tp_allocator());
 	    }
 	  catch(...)
 	    {
-	      std::_Destroy(__new_start, __new_finish, this->get_allocator());
+	      std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
 	      _M_deallocate(__new_start.base(),__len);
 	      __throw_exception_again;
 	    }
-	  std::_Destroy(begin(), end(), this->get_allocator());
+	  std::_Destroy(begin(), end(), _M_get_Tp_allocator());
 	  _M_deallocate(this->_M_impl._M_start,
 			this->_M_impl._M_end_of_storage
 			- this->_M_impl._M_start);
@@ -323,7 +323,7 @@ namespace _GLIBCXX_STD
 		  std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
 					      this->_M_impl._M_finish,
 					      this->_M_impl._M_finish,
-					      this->get_allocator());
+					      _M_get_Tp_allocator());
 		  this->_M_impl._M_finish += __n;
 		  std::copy_backward(__position, __old_finish - __n,
 				     __old_finish);
@@ -334,11 +334,11 @@ namespace _GLIBCXX_STD
 		  std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
 						__n - __elems_after,
 						__x_copy,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		  this->_M_impl._M_finish += __n - __elems_after;
 		  std::__uninitialized_copy_a(__position, __old_finish,
 					      this->_M_impl._M_finish,
-					      this->get_allocator());
+					      _M_get_Tp_allocator());
 		  this->_M_impl._M_finish += __elems_after;
 		  std::fill(__position, __old_finish, __x_copy);
 		}
@@ -361,23 +361,23 @@ namespace _GLIBCXX_STD
 		  __new_finish =
 		    std::__uninitialized_copy_a(begin(), __position,
 						__new_start,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		  std::__uninitialized_fill_n_a(__new_finish, __n, __x,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		  __new_finish += __n;
 		  __new_finish =
 		    std::__uninitialized_copy_a(__position, end(), __new_finish,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		}
 	      catch(...)
 		{
 		  std::_Destroy(__new_start, __new_finish,
-				this->get_allocator());
+				_M_get_Tp_allocator());
 		  _M_deallocate(__new_start.base(), __len);
 		  __throw_exception_again;
 		}
 	      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-			    this->get_allocator());
+			    _M_get_Tp_allocator());
 	      _M_deallocate(this->_M_impl._M_start,
 			    this->_M_impl._M_end_of_storage
 			    - this->_M_impl._M_start);
@@ -421,7 +421,7 @@ namespace _GLIBCXX_STD
 		    std::__uninitialized_copy_a(this->_M_impl._M_finish - __n,
 						this->_M_impl._M_finish,
 						this->_M_impl._M_finish,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		    this->_M_impl._M_finish += __n;
 		    std::copy_backward(__position, __old_finish - __n,
 				       __old_finish);
@@ -433,11 +433,11 @@ namespace _GLIBCXX_STD
 		    std::advance(__mid, __elems_after);
 		    std::__uninitialized_copy_a(__mid, __last,
 						this->_M_impl._M_finish,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		    this->_M_impl._M_finish += __n - __elems_after;
 		    std::__uninitialized_copy_a(__position, __old_finish,
 						this->_M_impl._M_finish,
-						this->get_allocator());
+						_M_get_Tp_allocator());
 		    this->_M_impl._M_finish += __elems_after;
 		    std::copy(__first, __mid, __position);
 		  }
@@ -461,25 +461,25 @@ namespace _GLIBCXX_STD
 		      std::__uninitialized_copy_a(iterator(this->_M_impl._M_start),
 						  __position,
 						  __new_start,
-						  this->get_allocator());
+						  _M_get_Tp_allocator());
 		    __new_finish =
 		      std::__uninitialized_copy_a(__first, __last, __new_finish,
-						  this->get_allocator());
+						  _M_get_Tp_allocator());
 		    __new_finish =
 		      std::__uninitialized_copy_a(__position,
 						  iterator(this->_M_impl._M_finish),
 						  __new_finish,
-						  this->get_allocator());
+						  _M_get_Tp_allocator());
 		  }
 		catch(...)
 		  {
 		    std::_Destroy(__new_start,__new_finish,
-				  this->get_allocator());
+				  _M_get_Tp_allocator());
 		    _M_deallocate(__new_start.base(), __len);
 		    __throw_exception_again;
 		  }
 		std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-			      this->get_allocator());
+			      _M_get_Tp_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/testsuite/21_strings/basic_string/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/1.cc
new file mode 100644
index 0000000..e65fdd8
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/1.cc
@@ -0,0 +1,36 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of basic_string
+
+#include <string>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::basic_string<int, std::char_traits<int>,
+				 std::allocator<char> >;
diff --git a/libstdc++-v3/testsuite/23_containers/deque/explicit_instantiation.cc b/libstdc++-v3/testsuite/23_containers/deque/explicit_instantiation/1.cc
index e6e758d..e6e758d 100644
--- a/libstdc++-v3/testsuite/23_containers/deque/explicit_instantiation.cc
+++ b/libstdc++-v3/testsuite/23_containers/deque/explicit_instantiation/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/deque/explicit_instantiation/3.cc b/libstdc++-v3/testsuite/23_containers/deque/explicit_instantiation/3.cc
new file mode 100644
index 0000000..51b4551
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/explicit_instantiation/3.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of library containers
+
+#include <deque>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::deque<int, std::allocator<char> >;
diff --git a/libstdc++-v3/testsuite/23_containers/list/explicit_instantiation.cc b/libstdc++-v3/testsuite/23_containers/list/explicit_instantiation/1.cc
index 2c9db8d..2c9db8d 100644
--- a/libstdc++-v3/testsuite/23_containers/list/explicit_instantiation.cc
+++ b/libstdc++-v3/testsuite/23_containers/list/explicit_instantiation/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/list/explicit_instantiation/3.cc b/libstdc++-v3/testsuite/23_containers/list/explicit_instantiation/3.cc
new file mode 100644
index 0000000..19f719d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/explicit_instantiation/3.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of library containers
+
+#include <list>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::list<int, std::allocator<char> >;
diff --git a/libstdc++-v3/testsuite/23_containers/map/explicit_instantiation.cc b/libstdc++-v3/testsuite/23_containers/map/explicit_instantiation/1.cc
index 4ceb250..4ceb250 100644
--- a/libstdc++-v3/testsuite/23_containers/map/explicit_instantiation.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/explicit_instantiation/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/map/explicit_instantiation/3.cc b/libstdc++-v3/testsuite/23_containers/map/explicit_instantiation/3.cc
new file mode 100644
index 0000000..8ce3b6f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/explicit_instantiation/3.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of library containers
+
+#include <map>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::map<int, double, std::less<int>, std::allocator<char> >;
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/explicit_instantiation.cc b/libstdc++-v3/testsuite/23_containers/multimap/explicit_instantiation/1.cc
index 4a740b2..4a740b2 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/explicit_instantiation.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/explicit_instantiation/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/explicit_instantiation/3.cc b/libstdc++-v3/testsuite/23_containers/multimap/explicit_instantiation/3.cc
new file mode 100644
index 0000000..1c434b8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/explicit_instantiation/3.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of library containers
+
+#include <map>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::multimap<int, double, std::less<int>, std::allocator<char> >;
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/explicit_instantiation.cc b/libstdc++-v3/testsuite/23_containers/multiset/explicit_instantiation/1.cc
index fb6b5f1..fb6b5f1 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/explicit_instantiation.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/explicit_instantiation/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/explicit_instantiation/3.cc b/libstdc++-v3/testsuite/23_containers/multiset/explicit_instantiation/3.cc
new file mode 100644
index 0000000..2b36bb9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/explicit_instantiation/3.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of library containers
+
+#include <set>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::multiset<int, std::less<int>, std::allocator<char> >;
diff --git a/libstdc++-v3/testsuite/23_containers/set/explicit_instantiation.cc b/libstdc++-v3/testsuite/23_containers/set/explicit_instantiation/1.cc
index 02e33be..02e33be 100644
--- a/libstdc++-v3/testsuite/23_containers/set/explicit_instantiation.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/explicit_instantiation/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/set/explicit_instantiation/3.cc b/libstdc++-v3/testsuite/23_containers/set/explicit_instantiation/3.cc
new file mode 100644
index 0000000..c232322
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/explicit_instantiation/3.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of library containers
+
+#include <set>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::set<int, std::less<int>, std::allocator<char> >;
diff --git a/libstdc++-v3/testsuite/23_containers/vector/explicit_instantiation.cc b/libstdc++-v3/testsuite/23_containers/vector/explicit_instantiation/1.cc
index 0668bbd1..0668bbd1 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/explicit_instantiation.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/explicit_instantiation/1.cc
diff --git a/libstdc++-v3/testsuite/23_containers/vector/explicit_instantiation/3.cc b/libstdc++-v3/testsuite/23_containers/vector/explicit_instantiation/3.cc
new file mode 100644
index 0000000..2cd0b23
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/explicit_instantiation/3.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2005 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.
+
+// This file tests explicit instantiation of library containers
+
+#include <vector>
+
+// { dg-do compile }
+
+// libstdc++/21770
+template class std::vector<int, std::allocator<char> >;