2003-11-11 Doug Gregor <gregod@cs.rpi.edu>

	* docs/html/debug.html: Document libstdc++ debug mode.
	* docs/html/debug_mode.html: Document libstdc++ debug mode design.
	* docs/html/test.html: Document how to test under debug mode.
	* docs/html/17_intro/howto.html: Document debug-mode macros.
	* include/Makefile.am: Install debug-mode headers.
	* src/Makefile.am: Include debug.cc.
	* include/bits/basic_string.tcc:
	  (basic_string::_S_construct): Fix NULL pointer check.
	  (__is_null_pointer): New.
	  Add precondition annotations.
	* include/bits/stream_iterator.h (istream_iterator,
	ostream_iterator): Added precondition annotations.
	* include/bits/streambuf_iterator.h (istreambuf_iterator): Ditto.
	* include/bits/stl_queue.h (queue, priority_queue): Ditto.
	* include/bits/stl_stack.h (stack): Ditto.
	* include/bits/basic_string.h (basic_string): Ditto.
	* include/bits/basic_string.tcc (basic_string): Ditto.
	* include/std/std_memory.h (auto_ptr): Ditto.
	* include/std/std_valarray.h (valarray): Ditto.
	* include/bits/stl_algo.h: Added algorithm precondition
	annotations.
	* include/bits/stl_algobase.h: Added algorithm precondition
	annotations.
	* include/bits/stl_numeric.h: Ditto.
	* include/ext/algorithm: Added algorithm precondition
	annotations.
	(__is_heap): Moved away from here.
	* include/bits/stl_heap.h: Added algorithm precondition
	annotations.
	(__is_heap): Moved to the top of this file.
	(__is_heap): Added iterator range overloads.
	* testsuite/20_util/auto_ptr_neg.cc: Fix line numbers to match up
	with changes in std_memory.h.
	* testsuite/23_containers/list/operators/4.cc: Don't verify
	performance guarantees when in debug mode.
	* testsuite/23_containers/bitset/invalidation/1.cc: New.
	* testsuite/23_containers/deque/invalidation/1.cc: New.
	* testsuite/23_containers/deque/invalidation/2.cc: New.
	* testsuite/23_containers/deque/invalidation/3.cc: New.
	* testsuite/23_containers/deque/invalidation/4.cc: New.
	* testsuite/23_containers/list/invalidation/1.cc: New.
	* testsuite/23_containers/list/invalidation/2.cc: New.
	* testsuite/23_containers/list/invalidation/3.cc: New.
	* testsuite/23_containers/list/invalidation/4.cc: New.
	* testsuite/23_containers/map/invalidation/1.cc: New.
	* testsuite/23_containers/map/invalidation/2.cc: New.
	* testsuite/23_containers/multimap/invalidation/1.cc: New.
	* testsuite/23_containers/multimap/invalidation/2.cc: New.
	* testsuite/23_containers/multiset/invalidation/1.cc: New.
	* testsuite/23_containers/multiset/invalidation/2.cc: New.
	* testsuite/23_containers/set/invalidation/1.cc: New.
	* testsuite/23_containers/set/invalidation/2.cc: New.
	* testsuite/23_containers/vector/invalidation/1.cc: New.
	* testsuite/23_containers/vector/invalidation/2.cc: New.
	* testsuite/23_containers/vector/invalidation/3.cc: New.
	* testsuite/23_containers/vector/invalidation/4.cc: New.
	* testsuite/25_algorithms/heap.cc: Don't verify
	performance guarantees when in debug mode.
	* include/debug/bitset: New.
	* include/debug/debug.h: New.
	* include/debug/deque: New.
	* include/debug/formatter.h: New.
	* include/debug/hash_map: New.
	* include/debug/hash_map.h: New.
	* include/debug/hash_multimap.h: New.
	* include/debug/hash_set: New.
	* include/debug/hash_set.h: New.
	* include/debug/hash_multiset.h: New.
	* include/debug/list: New.
	* include/debug/map: New.
	* include/debug/map.h: New.
	* include/debug/multimap.h: New.
	* include/debug/multiset.h: New.
	* include/debug/safe_base.h: New.
	* include/debug/safe_iterator.h: New.
	* include/debug/safe_iterator.tcc: New.
	* include/debug/safe_sequence.h: New.
	* include/debug/set: New.
	* include/debug/set.h: New.
	* include/debug/string: New.
	* include/debug/vector: New.
	* src/debug.cc: New.
	* config/linker-map.gnu: Add debug mode symbols.

2003-11-11  Benjamin Kosnik  <bkoz@redhat.com>

	* src/string-inst.cc: Tweak namespaces.
	* src/misc-inst.cc: Same.
	* docs/html/debug.html: Edits.
	* config/link-map.gnu: Remove cruft.

	* include/bits/c++config: Add in namespace associations.
	* include/std/std_bitset.h: Adjust namespace to __gnu_norm,
	comment tweaks.
	* include/bits/deque.tcc: Same.
	* include/bits/list.tcc: Same.
	* include/bits/stl_bvector.h: Same.
	* include/bits/stl_deque.h: Same.
	* include/bits/stl_list.h: Same.
	* include/bits/stl_map.h: Same.
	* include/bits/stl_multimap.h: Same.
	* include/bits/stl_multiset.h: Same.
	* include/bits/stl_set.h: Same.
	* include/bits/stl_vector.h: Same.
	* include/bits/vector.tcc: Same.

	* include/std/std_algorithm.h: Remove markup comments.
	* include/std/std_functional.h: Same.
	* include/std/std_iterator.h: Same.
	* include/std/std_numeric.h: Same.
	* include/std/std_utility.h: Same.
	* include/bits/stl_queue.h: Formatting tweaks.
	* include/bits/stl_stack.h: Same.
	* include/std/std_deque.h: Include debugging version in debug mode.
	* include/std/std_list.h: Same.
	* include/std/std_map.h: Same.
	* include/std/std_set.h: Same.
	* include/std/std_vector.h: Same.
	* include/std/std_queue.h: Use deque, vector.
	* include/std/std_stack.h: Same.


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

23 files changed, 7088 insertions, 0 deletions

diff --git a/libstdc++-v3/include/debug/bitset b/libstdc++-v3/include/debug/bitset
new file mode 100644
index 00000000000..3c474cf9d82
--- /dev/null
+++ b/libstdc++-v3/include/debug/bitset
@@ -0,0 +1,298 @@
+// Debugging bitset implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_BITSET
+#define _GLIBCXX_DEBUG_BITSET
+
+#include <bitset>
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{ 
+  template<size_t _Nb> 
+    class bitset
+    : public __gnu_norm::bitset<_Nb>, public __gnu_debug::_Safe_sequence_base
+    {
+      typedef  __gnu_norm::bitset<_Nb> 	   	_Base;
+      typedef __gnu_debug::_Safe_sequence_base  _Safe_base;
+
+    public:
+      // bit reference:
+      class reference 
+      : private _Base::reference, public __gnu_debug::_Safe_iterator_base
+      {
+	typedef typename _Base::reference _Base_ref;
+
+	friend class bitset;
+	reference();
+	
+	reference(const _Base_ref& __base, bitset* __seq) 
+	: _Base_ref(__base), _Safe_iterator_base(__seq, false)
+	{ }
+
+      public:
+	reference(const reference& __x)
+	: _Base_ref(__x), _Safe_iterator_base(__x, false)
+	{ }
+
+	reference& 
+	operator=(bool __x)
+	{
+	  _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+			      _M_message(::__gnu_debug::__msg_bad_bitset_write)
+				._M_iterator(*this));
+	  *static_cast<_Base_ref*>(this) = __x;
+	  return *this;
+	}
+
+	reference& 
+	operator=(const reference& __x)
+	{
+	  _GLIBCXX_DEBUG_VERIFY(! __x._M_singular(),
+			       _M_message(::__gnu_debug::__msg_bad_bitset_read)
+				._M_iterator(__x));
+	  _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+			      _M_message(::__gnu_debug::__msg_bad_bitset_write)
+				._M_iterator(*this));
+	  *static_cast<_Base_ref*>(this) = __x;
+	  return *this;
+	}
+	
+	bool 
+	operator~() const
+	{
+	  _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+			       _M_message(::__gnu_debug::__msg_bad_bitset_read)
+				._M_iterator(*this));
+	  return ~(*static_cast<const _Base_ref*>(this));
+	}
+	
+	operator bool() const
+	{
+	  _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+			      _M_message(::__gnu_debug::__msg_bad_bitset_read)
+				._M_iterator(*this));
+	  return *static_cast<const _Base_ref*>(this);
+	}
+	
+	reference& 
+	flip()
+	{
+	  _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+			      _M_message(::__gnu_debug::__msg_bad_bitset_flip)
+				._M_iterator(*this));
+	  _Base_ref::flip();
+	  return *this;
+	}
+      };
+
+      // 23.3.5.1 constructors:
+      bitset() : _Base() { }
+      
+      bitset(unsigned long __val) : _Base(__val) { }
+      
+      template<typename _CharT, typename _Traits, typename _Allocator>
+        explicit 
+        bitset(const std::basic_string<_CharT,_Traits,_Allocator>& __str,
+	       typename std::basic_string<_CharT,_Traits,_Allocator>::size_type
+	       __pos = 0,
+	       typename std::basic_string<_CharT,_Traits,_Allocator>::size_type
+  	       __n = (std::basic_string<_CharT,_Traits,_Allocator>::npos))
+	: _Base(__str, __pos, __n) { }
+
+      bitset(const _Base& __x) : _Base(__x), _Safe_base() { }
+
+      // 23.3.5.2 bitset operations:
+      bitset<_Nb>& 
+      operator&=(const bitset<_Nb>& __rhs)
+      {
+	_M_base() &= __rhs;
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator|=(const bitset<_Nb>& __rhs)
+      {
+	_M_base() != __rhs;
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator^=(const bitset<_Nb>& __rhs)
+      {
+	_M_base() ^= __rhs;
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator<<=(size_t __pos)
+      {
+	_M_base() <<= __pos;
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      operator>>=(size_t __pos)
+      {
+	_M_base() >>= __pos;
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      set()
+      {
+	_Base::set();
+	return *this;
+      }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 186. bitset::set() second parameter should be bool 
+      bitset<_Nb>& 
+      set(size_t __pos, bool __val = true)
+      {
+	_Base::set(__pos, __val);
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      reset()
+      {
+	_Base::reset();
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      reset(size_t __pos)
+      {
+	_Base::reset(__pos);
+	return *this;
+      }
+      
+      bitset<_Nb> operator~() const { return bitset(~_M_base()); }
+      
+      bitset<_Nb>& 
+      flip()
+      {
+	_Base::flip();
+	return *this;
+      }
+      
+      bitset<_Nb>& 
+      flip(size_t __pos)
+      {
+	_Base::flip(__pos);
+	return *this;
+      }
+      
+      // element access:
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 11. Bitset minor problems 
+      reference 
+      operator[](size_t __pos)
+      { 
+	__glibcxx_check_subscript(__pos);
+	return reference(_M_base()[__pos], this); 
+      }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 11. Bitset minor problems 
+      bool 
+      operator[](size_t __pos) const 
+      { 
+	__glibcxx_check_subscript(__pos);
+	return _M_base()[__pos]; 
+      }
+      
+      using _Base::to_ulong;
+      
+      template <typename _CharT, typename _Traits, typename _Allocator>
+        std::basic_string<_CharT, _Traits, _Allocator> 
+        to_string() const
+        { return _M_base().template to_string<_CharT, _Traits, _Allocator>(); }
+      
+      using _Base::count;
+      using _Base::size;
+      
+      bool 
+      operator==(const bitset<_Nb>& __rhs) const
+      { return _M_base() == __rhs; }
+
+      bool 
+      operator!=(const bitset<_Nb>& __rhs) const
+      { return _M_base() != __rhs; }
+      
+      using _Base::test;
+      using _Base::any;
+      using _Base::none;
+      
+      bitset<_Nb> 
+      operator<<(size_t __pos) const
+      { return bitset<_Nb>(_M_base() << __pos); }
+      
+      bitset<_Nb> 
+      operator>>(size_t __pos) const
+      { return bitset<_Nb>(_M_base() >> __pos); }
+      
+      _Base&       
+      _M_base() { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+    };
+ 
+  template<size_t _Nb>
+    bitset<_Nb> 
+    operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
+    { return bitset<_Nb>(__x) &= __y; }
+  
+  template<size_t _Nb>
+    bitset<_Nb> 
+    operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
+    { return bitset<_Nb>(__x) |= __y; }
+
+  template<size_t _Nb>
+    bitset<_Nb> 
+    operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
+    { return bitset<_Nb>(__x) ^= __y; }
+
+  template<typename _CharT, typename _Traits, size_t _Nb>
+    std::basic_istream<_CharT, _Traits>&
+    operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
+    { return __is >> __x._M_base(); }
+
+  template<typename _CharT, typename _Traits, size_t _Nb>
+    std::basic_ostream<_CharT, _Traits>&
+    operator<<(std::basic_ostream<_CharT, _Traits>& __os, 
+	       const bitset<_Nb>& __x)
+    { return __os << __x._M_base(); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
new file mode 100644
index 00000000000..edb19aa85c3
--- /dev/null
+++ b/libstdc++-v3/include/debug/debug.h
@@ -0,0 +1,531 @@
+// Debugging support implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_DEBUG_H
+#define _GLIBCXX_DEBUG_DEBUG_H 1
+
+/**
+ * Macros used by the implementation to verify certain
+ * properties. These macros may only be used directly by the debug
+ * wrappers. Note that these are macros (instead of the more obviously
+ * "correct" choice of making them functions) because we need line and
+ * file information at the call site, to minimize the distance between
+ * the user error and where the error is reported.
+ *
+ */
+#define _GLIBCXX_DEBUG_VERIFY(_Condition,_ErrorMessage)		\
+  do {									\
+    if (! (_Condition))							\
+      ::__gnu_debug::_Error_formatter::_M_at(__FILE__, __LINE__)	\
+	  ._ErrorMessage._M_error();					\
+  } while (false)
+
+// Verify that [_First, _Last) forms a valid iterator range.
+#define __glibcxx_check_valid_range(_First,_Last)			\
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__valid_range(_First, _Last),	\
+		      _M_message(::__gnu_debug::__msg_valid_range)	\
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last))
+
+/** Verify that we can insert into *this with the iterator _Position.
+ *  Insertion into a container at a specific position requires that
+ *  the iterator be nonsingular (i.e., either dereferenceable or
+ *  past-the-end) and that it reference the sequence we are inserting
+ *  into. Note that this macro is only valid when the container is a
+ *  _Safe_sequence and the iterator is a _Safe_iterator.
+*/
+#define __glibcxx_check_insert(_Position)				\
+_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(),				\
+		      _M_message(::__gnu_debug::__msg_insert_singular) \
+		      ._M_sequence(*this, "this")			\
+		      ._M_iterator(_Position, #_Position));		\
+_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),			\
+		      _M_message(::__gnu_debug::__msg_insert_different) \
+		      ._M_sequence(*this, "this")			\
+		      ._M_iterator(_Position, #_Position))
+
+/** Verify that we can insert the values in the iterator range
+ *  [_First, _Last) into *this with the iterator _Position.  Insertion
+ *  into a container at a specific position requires that the iterator
+ *  be nonsingular (i.e., either dereferenceable or past-the-end),
+ *  that it reference the sequence we are inserting into, and that the
+ *  iterator range [_First, Last) is a valid (possibly empty)
+ *  range. Note that this macro is only valid when the container is a
+ *  _Safe_sequence and the iterator is a _Safe_iterator.
+ *
+ *  @tbd We would like to be able to check for noninterference of
+ *  _Position and the range [_First, _Last), but that can't (in
+ *  general) be done.
+*/
+#define __glibcxx_check_insert_range(_Position,_First,_Last)		\
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(),				\
+		      _M_message(::__gnu_debug::__msg_insert_singular) \
+                      ._M_sequence(*this, "this")			\
+		      ._M_iterator(_Position, #_Position));		\
+_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),			\
+		      _M_message(::__gnu_debug::__msg_insert_different) \
+		      ._M_sequence(*this, "this")			\
+		      ._M_iterator(_Position, #_Position))
+
+/** Verify that we can erase the element referenced by the iterator
+ * _Position. We can erase the element if the _Position iterator is
+ * dereferenceable and references this sequence.
+*/
+#define __glibcxx_check_erase(_Position)				\
+_GLIBCXX_DEBUG_VERIFY(_Position._M_dereferenceable(),			\
+		      _M_message(::__gnu_debug::__msg_erase_bad)	\
+                      ._M_sequence(*this, "this")			\
+		      ._M_iterator(_Position, #_Position));		\
+_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this),			\
+		      _M_message(::__gnu_debug::__msg_erase_different) \
+		      ._M_sequence(*this, "this")			\
+		      ._M_iterator(_Position, #_Position))
+
+/** Verify that we can erase the elements in the iterator range
+ *  [_First, _Last). We can erase the elements if [_First, _Last) is a
+ *  valid iterator range within this sequence.
+*/
+#define __glibcxx_check_erase_range(_First,_Last)			\
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(_First._M_attached_to(this),			\
+		      _M_message(::__gnu_debug::__msg_erase_different) \
+                      ._M_sequence(*this, "this")			\
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last))
+
+// Verify that the subscript _N is less than the container's size.
+#define __glibcxx_check_subscript(_N)					\
+_GLIBCXX_DEBUG_VERIFY(_N < this->size(),				\
+		      _M_message(::__gnu_debug::__msg_subscript_oob) \
+                      ._M_sequence(*this, "this")			\
+		      ._M_integer(_N, #_N)				\
+		      ._M_integer(this->size(), "size"))
+
+// Verify that the container is nonempty
+#define __glibcxx_check_nonempty()					\
+_GLIBCXX_DEBUG_VERIFY(! this->empty(),					\
+		      _M_message(::__gnu_debug::__msg_empty)	\
+                      ._M_sequence(*this, "this"))
+
+// Verify that the < operator for elements in the sequence is a
+// StrictWeakOrdering by checking that it is irreflexive.
+#define __glibcxx_check_strict_weak_ordering(_First,_Last)	\
+_GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First))
+
+// Verify that the predicate is StrictWeakOrdering by checking that it
+// is irreflexive.
+#define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred)	\
+_GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First))
+
+
+// Verify that the iterator range [_First, _Last) is sorted
+#define __glibcxx_check_sorted(_First,_Last)				\
+__glibcxx_check_valid_range(_First,_Last);				\
+__glibcxx_check_strict_weak_ordering(_First,_Last);			\
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last),	\
+		      _M_message(::__gnu_debug::__msg_unsorted)	\
+                      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last))
+
+/** Verify that the iterator range [_First, _Last) is sorted by the
+    predicate _Pred. */
+#define __glibcxx_check_sorted_pred(_First,_Last,_Pred)			\
+__glibcxx_check_valid_range(_First,_Last);				\
+__glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred);	        \
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last, _Pred), \
+		      _M_message(::__gnu_debug::__msg_unsorted_pred) \
+                      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last)			\
+		      ._M_string(#_Pred))
+
+/** Verify that the iterator range [_First, _Last) is partitioned
+    w.r.t. the value _Value. */
+#define __glibcxx_check_partitioned(_First,_Last,_Value)		\
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last,	\
+							 _Value),	\
+		      _M_message(::__gnu_debug::__msg_unpartitioned) \
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last) 			\
+		      ._M_string(#_Value))
+
+/** Verify that the iterator range [_First, _Last) is partitioned
+    w.r.t. the value _Value and predicate _Pred. */
+#define __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred)	\
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last,	\
+							 _Value, _Pred), \
+		      _M_message(::__gnu_debug::__msg_unpartitioned_pred) \
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last) 			\
+		      ._M_string(#_Pred)				\
+                      ._M_string(#_Value))
+
+// Verify that the iterator range [_First, _Last) is a heap
+#define __glibcxx_check_heap(_First,_Last)				\
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last),		\
+		      _M_message(::__gnu_debug::__msg_not_heap)	\
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last))
+
+/** Verify that the iterator range [_First, _Last) is a heap
+    w.r.t. the predicate _Pred. */
+#define __glibcxx_check_heap_pred(_First,_Last,_Pred)			\
+__glibcxx_check_valid_range(_First,_Last);				\
+_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred),		\
+		      _M_message(::__gnu_debug::__msg_not_heap_pred) \
+                      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last)			\
+		      ._M_string(#_Pred))
+
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+#  define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_ASSERT(_String != 0)
+#  define __glibcxx_check_string_len(_String,_Len) \
+       _GLIBCXX_DEBUG_ASSERT(_String != 0 || _Len == 0)
+#else
+#  define __glibcxx_check_string(_String)
+#  define __glibcxx_check_string_len(_String,_Len)
+#endif
+
+/** Macros used by the implementation outside of debug wrappers to
+ *  verify certain properties. The __glibcxx_requires_xxx macros are
+ *  merely wrappers around the __glibcxx_check_xxx wrappers when we
+ *  are compiling with debug mode, but disappear when we are in
+ *  release mode so that there is no checking performed in, e.g., the
+ *  standard library algorithms.
+*/
+#ifdef _GLIBCXX_DEBUG
+#  define _GLIBCXX_DEBUG_ASSERT(_Condition) assert(_Condition)
+
+#  ifdef _GLIBXX_DEBUG_PEDANTIC
+#    define _GLIBCXX_DEBUG_PEDASSERT(_Condition) assert(_Condition)
+#  else
+#    define _GLIBCXX_DEBUG_PEDASSERT(_Condition)
+#  endif
+
+#  define __glibcxx_requires_cond(_Cond,_Msg) _GLIBCXX_DEBUG_VERIFY(_Cond,_Msg)
+#  define __glibcxx_requires_valid_range(_First,_Last) \
+     __glibcxx_check_valid_range(_First,_Last)
+#  define __glibcxx_requires_sorted(_First,_Last) \
+     __glibcxx_check_sorted(_First,_Last)
+#  define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \
+     __glibcxx_check_sorted_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_partitioned(_First,_Last,_Value)	\
+     __glibcxx_check_partitioned(_First,_Last,_Value)
+#  define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred) \
+     __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred)
+#  define __glibcxx_requires_heap(_First,_Last) \
+     __glibcxx_check_heap(_First,_Last)
+#  define __glibcxx_requires_heap_pred(_First,_Last,_Pred) \
+     __glibcxx_check_heap_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_nonempty() __glibcxx_check_nonempty()
+#  define __glibcxx_requires_string(_String) __glibcxx_check_string(_String)
+#  define __glibcxx_requires_string_len(_String,_Len)	\
+     __glibcxx_check_string_len(_String,_Len)
+#  define __glibcxx_requires_subscript(_N) __glibcxx_check_subscript(_N)
+#else
+#  define _GLIBCXX_DEBUG_ASSERT(_Condition)
+#  define _GLIBCXX_DEBUG_PEDASSERT(_Condition)
+#  define __glibcxx_requires_cond(_Cond,_Msg)
+#  define __glibcxx_requires_valid_range(_First,_Last)
+#  define __glibcxx_requires_sorted(_First,_Last)
+#  define __glibcxx_requires_sorted_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_partitioned(_First,_Last,_Value)
+#  define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred)
+#  define __glibcxx_requires_heap(_First,_Last)
+#  define __glibcxx_requires_heap_pred(_First,_Last,_Pred)
+#  define __glibcxx_requires_nonempty()
+#  define __glibcxx_requires_string(_String)
+#  define __glibcxx_requires_string_len(_String,_Len)
+#  define __glibcxx_requires_subscript(_N)
+#endif 
+
+#include <cassert> // TBD: temporary
+
+#include <stddef.h>                       // for ptrdiff_t
+#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories
+#include <bits/type_traits.h>             // for _Is_integer
+
+namespace __gnu_debug
+{
+  template<typename _Iterator, typename _Sequence> 
+    class _Safe_iterator;
+
+  // An arbitrary iterator pointer is not singular.
+  inline bool 
+  __check_singular_aux(const void*) { return false; }
+
+  // We may have an iterator that derives from _Safe_iterator_base but isn't
+  // a _Safe_iterator.
+  template<typename _Iterator>
+    inline bool
+    __check_singular(_Iterator& __x)
+    { return __gnu_debug::__check_singular_aux(&__x); }
+
+  /** Non-NULL pointers are nonsingular. */
+  template<typename _Tp>
+    inline bool
+    __check_singular(const _Tp* __ptr)
+    { return __ptr == 0; }
+
+  /** Safe iterators know if they are singular. */
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x)
+    { return __x._M_singular(); }
+
+  /** Assume that some arbitrary iterator is dereferenceable, because we
+      can't prove that it isn't. */
+  template<typename _Iterator>
+    inline bool
+    __check_dereferenceable(_Iterator&)
+    { return true; }
+
+  /** Non-NULL pointers are dereferenceable. */
+  template<typename _Tp>
+    inline bool
+    __check_dereferenceable(const _Tp* __ptr)
+    { return __ptr; }
+
+  /** Safe iterators know if they are singular. */
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
+    { return __x._M_dereferenceable(); }
+
+  /** If the distance between two random access iterators is
+   *  nonnegative, assume the range is valid. 
+  */
+  template<typename _RandomAccessIterator>
+    inline bool
+    __valid_range_aux2(const _RandomAccessIterator& __first, 
+		       const _RandomAccessIterator& __last,
+		       std::random_access_iterator_tag)
+    { return __last - __first >= 0; }
+
+  /** Can't test for a valid range with input iterators, because
+   *  iteration may be destructive. So we just assume that the range
+   *  is valid.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range_aux2(const _InputIterator&, const _InputIterator&,
+		       std::input_iterator_tag)
+    { return true; }
+
+  /** We say that integral types for a valid range, and defer to other
+   *  routines to realize what to do with integral types instead of
+   *  iterators. 
+  */
+  template<typename _Integral>
+    inline bool
+    __valid_range_aux(const _Integral&, const _Integral&, __true_type)
+    { return true; }
+
+  /** We have iterators, so figure out what kind of iterators that are
+   *  to see if we can check the range ahead of time.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range_aux(const _InputIterator& __first, 
+		      const _InputIterator& __last, __false_type)
+  {
+    typedef typename std::iterator_traits<_InputIterator>::iterator_category
+      _Category;
+    return __gnu_debug::__valid_range_aux2(__first, __last, _Category()); 
+  }
+
+  /** Don't know what these iterators are, or if they are even
+   *  iterators (we may get an integral type for InputIterator), so
+   *  see if they are integral and pass them on to the next phase
+   *  otherwise.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
+    { 
+      typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+      return __gnu_debug::__valid_range_aux(__first, __last, _Integral());
+    }
+
+  /** Safe iterators know how to check if they form a valid range. */
+  template<typename _Iterator, typename _Sequence>
+    inline bool 
+    __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
+		  const _Safe_iterator<_Iterator, _Sequence>& __last)
+    { return __first._M_valid_range(__last); }
+
+  /* Checks that [first, last) is a valid range, and then returns
+   * __first. This routine is useful when we can't use a separate
+   * assertion statement because, e.g., we are in a constructor. 
+  */
+  template<typename _InputIterator>
+    inline _InputIterator
+    __check_valid_range(const _InputIterator& __first, 
+			const _InputIterator& __last)
+    {
+      _GLIBCXX_DEBUG_ASSERT(__gnu_debug::__valid_range(__first, __last));
+      return __first;
+    }
+
+  /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
+  template<typename _CharT, typename _Integer>
+    inline const _CharT*
+    __check_string(const _CharT* __s, const _Integer& __n)
+    {
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+      _GLIBCXX_DEBUG_ASSERT(__s != 0 || __n == 0);
+#endif
+      return __s;
+    }
+
+  /** Checks that __s is non-NULL and then returns __s. */
+  template<typename _CharT>
+    inline const _CharT*
+    __check_string(const _CharT* __s)
+    {
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+      _GLIBCXX_DEBUG_ASSERT(__s != 0);
+#endif
+      return __s;
+    }
+
+  // Can't check if an input iterator sequence is sorted, because we
+  // can't step through the sequence.
+  template<typename _InputIterator>
+    inline bool 
+    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
+                       std::input_iterator_tag)
+    { return true; }
+
+  // Can verify if a forward iterator sequence is in fact sorted using
+  // std::__is_sorted
+  template<typename _ForwardIterator>
+    inline bool
+    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
+                       std::forward_iterator_tag)
+    { 
+      if (__first == __last)
+        return true;
+
+      _ForwardIterator __next = __first;
+      for (++__next; __next != __last; __first = __next, ++__next) {
+        if (*__next < *__first)
+          return false;
+      }
+
+      return true;
+    }
+
+  // Can't check if an input iterator sequence is sorted, because we can't step
+  // through the sequence.
+  template<typename _InputIterator, typename _Predicate>
+    inline bool 
+    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
+                       _Predicate, std::input_iterator_tag)
+    { return true; }
+
+  // Can verify if a forward iterator sequence is in fact sorted using
+  // std::__is_sorted
+  template<typename _ForwardIterator, typename _Predicate>
+    inline bool
+    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 
+                       _Predicate __pred, std::forward_iterator_tag)
+    { 
+      if (__first == __last)
+        return true;
+
+      _ForwardIterator __next = __first;
+      for (++__next; __next != __last; __first = __next, ++__next) {
+        if (__pred(*__next, *__first))
+          return false;
+      }
+
+      return true;
+    }
+
+  // Determine if a sequence is sorted.
+  template<typename _InputIterator>
+    inline bool
+    __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
+    { 
+      typedef typename std::iterator_traits<_InputIterator>::iterator_category 
+        _Category;
+      return __gnu_debug::__check_sorted_aux(__first, __last, _Category());
+    }
+
+  template<typename _InputIterator, typename _Predicate>
+    inline bool
+    __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
+                   _Predicate __pred)
+    { 
+      typedef typename std::iterator_traits<_InputIterator>::iterator_category 
+        _Category;
+      return __gnu_debug::__check_sorted_aux(__first, __last, __pred,
+					     _Category());
+    }
+
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // 270. Binary search requirements overly strict 
+  // Determine if a sequence is partitioned w.r.t. this element.
+  template<typename _ForwardIterator, typename _Tp>
+    inline bool
+    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
+			const _Tp& __value)
+    {
+      while (__first != __last && *__first < __value)
+	++__first;
+      while (__first != __last && !(*__first < __value))
+	++__first;
+      return __first == __last;
+    }
+
+  // Determine if a sequence is partitioned w.r.t. this element.
+  template<typename _ForwardIterator, typename _Tp, typename _Pred>
+    inline bool
+    __check_partitioned(_ForwardIterator __first, _ForwardIterator __last,
+			const _Tp& __value, _Pred __pred)
+    {
+      while (__first != __last && __pred(*__first, __value))
+	++__first;
+      while (__first != __last && !__pred(*__first, __value))
+	++__first;
+      return __first == __last;
+    }
+} // namespace __gnu_debug
+
+#ifdef _GLIBCXX_DEBUG
+// We need the error formatter
+#  include <debug/formatter.h>
+#endif
+
+#endif 
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
new file mode 100644
index 00000000000..b9d68af598a
--- /dev/null
+++ b/libstdc++-v3/include/debug/deque
@@ -0,0 +1,386 @@
+// Debugging deque implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_DEQUE
+#define _GLIBCXX_DEBUG_DEQUE 1
+
+#include <deque>
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
+    class deque 
+    : public  __gnu_norm::deque<_Tp, _Allocator>,
+    public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> >
+    {
+      typedef  __gnu_norm::deque<_Tp, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
+
+    public:
+      typedef typename _Allocator::reference        reference;
+      typedef typename _Allocator::const_reference  const_reference;
+      
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque> 
+      						    iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
+						     const_iterator;
+      
+      typedef typename _Base::size_type             size_type;
+      typedef typename _Base::difference_type       difference_type;
+      
+      typedef _Tp        			    value_type;
+      typedef _Allocator 			    allocator_type;
+      typedef typename _Allocator::pointer          pointer;
+      typedef typename _Allocator::const_pointer    const_pointer;
+      typedef std::reverse_iterator<iterator>       reverse_iterator;
+      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+      // 23.2.1.1 construct/copy/destroy:
+      explicit deque(const _Allocator& __a = _Allocator())
+      : _Base(__a) { }
+
+      explicit deque(size_type __n, const _Tp& __value = _Tp(),
+		     const _Allocator& __a = _Allocator())
+      : _Base(__n, __value, __a) { }
+
+      template<class _InputIterator>
+        deque(_InputIterator __first, _InputIterator __last,
+	      const _Allocator& __a = _Allocator())
+	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
+        { }
+
+      deque(const deque<_Tp,_Allocator>& __x) : _Base(__x), _Safe_base() { }
+
+      deque(const _Base& __x) : _Base(__x), _Safe_base() { }
+      
+      ~deque() { }
+      
+      deque<_Tp,_Allocator>& 
+      operator=(const deque<_Tp,_Allocator>& __x)
+      {
+	*static_cast<_Base*>(this) = __x;
+	this->_M_invalidate_all();
+	return *this;
+      }
+      
+      template<class _InputIterator>
+        void 
+        assign(_InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::assign(__first, __last);
+	  this->_M_invalidate_all();
+	}
+
+      void 
+      assign(size_type __n, const _Tp& __t)
+      {
+	_Base::assign(__n, __t);
+	this->_M_invalidate_all();
+      }
+      
+      using _Base::get_allocator;
+      
+      // iterators:
+      iterator 
+      begin() 
+      { return iterator(_Base::begin(), this); }
+      
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+      
+      iterator 
+      end() 
+      { return iterator(_Base::end(), this); }
+      
+      const_iterator 
+      end() const 
+      { return const_iterator(_Base::end(), this); }
+      
+      reverse_iterator 
+      rbegin() 
+      { return reverse_iterator(end()); }
+      
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+      
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+      
+      const_reverse_iterator 
+      rend() const
+      { return const_reverse_iterator(begin()); }
+      
+      // 23.2.1.2 capacity:
+      using _Base::size;
+      using _Base::max_size;
+      
+      void 
+      resize(size_type __sz, _Tp __c = _Tp())
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
+	
+	bool __invalidate_all = __sz > this->size();
+	if (__sz < this->size())
+	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
+	
+	_Base::resize(__sz, __c);
+	
+	if (__invalidate_all)
+	  this->_M_invalidate_all();
+      }
+      
+      using _Base::empty;
+      
+      // element access:
+      reference 
+      operator[](size_type __n)
+      {
+	__glibcxx_check_subscript(__n);
+	return _M_base()[__n];
+      }
+      
+      const_reference 
+      operator[](size_type __n) const
+      {
+	__glibcxx_check_subscript(__n);
+	return _M_base()[__n];
+      }
+      
+      using _Base::at;
+      
+      reference 
+      front()
+      {
+	__glibcxx_check_nonempty();
+	return _Base::front();
+      }
+      
+      const_reference 
+      front() const
+      {
+	__glibcxx_check_nonempty();
+	return _Base::front();
+      }
+      
+      reference 
+      back()
+      {
+	__glibcxx_check_nonempty();
+	return _Base::back();
+      }
+      
+      const_reference 
+      back() const
+      {
+	__glibcxx_check_nonempty();
+	return _Base::back();
+      }
+      
+      // 23.2.1.3 modifiers:
+      void 
+      push_front(const _Tp& __x)
+      {
+	_Base::push_front(__x);
+	this->_M_invalidate_all();
+      }
+      
+      void 
+      push_back(const _Tp& __x)
+      {
+	_Base::push_back(__x);
+	this->_M_invalidate_all();
+      }
+      
+      iterator 
+      insert(iterator __position, const _Tp& __x)
+      {
+	__glibcxx_check_insert(__position);
+	typename _Base::iterator __res = _Base::insert(__position.base(), __x);
+	this->_M_invalidate_all();
+	return iterator(__res, this);
+      }
+      
+      void 
+      insert(iterator __position, size_type __n, const _Tp& __x)
+      {
+	__glibcxx_check_insert(__position);
+	_Base::insert(__position.base(), __n, __x);
+	this->_M_invalidate_all();
+      }
+      
+      template<class _InputIterator>
+        void 
+        insert(iterator __position, 
+	       _InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_check_insert_range(__position, __first, __last);
+	  _Base::insert(__position.base(), __first, __last);
+	  this->_M_invalidate_all();
+	}
+      
+      void 
+      pop_front()
+      {
+	__glibcxx_check_nonempty();
+	iterator __victim = begin();
+	__victim._M_invalidate();
+	_Base::pop_front();
+      }
+      
+      void 
+      pop_back()
+      {
+	__glibcxx_check_nonempty();
+	iterator __victim = end();
+	--__victim;
+	__victim._M_invalidate();
+	_Base::pop_back();
+      }
+      
+      iterator 
+      erase(iterator __position)
+      {
+	__glibcxx_check_erase(__position);
+	if (__position == begin() || __position == end()-1)
+	  {
+	    __position._M_invalidate();
+	    return iterator(_Base::erase(__position.base()), this);
+	  }
+	else
+	  {
+	    typename _Base::iterator __res = _Base::erase(__position.base());
+	    this->_M_invalidate_all();
+	    return iterator(__res, this);
+	  }
+      }
+      
+      iterator 
+      erase(iterator __first, iterator __last)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 151. can't currently clear() empty container
+	__glibcxx_check_erase_range(__first, __last);
+	if (__first == begin() || __last == end()-1)
+	  {
+	    this->_M_detach_singular();
+	    for (iterator __position = __first; __position != __last; )
+	      {
+		iterator __victim = __position++;
+		__victim._M_invalidate();
+	      }
+	    try 
+	      { 
+		return iterator(_Base::erase(__first.base(), __last.base()),
+				this); 
+	      }
+	    catch (...)
+	      {
+		this->_M_revalidate_singular();
+		__throw_exception_again;
+	      }
+	  }
+	else
+	  {
+	    typename _Base::iterator __res = _Base::erase(__first.base(), 
+							  __last.base());
+	    this->_M_invalidate_all();
+	    return iterator(__res, this);
+	  }
+      }
+      
+      void 
+      swap(deque<_Tp,_Allocator>& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+      
+      void 
+      clear()
+      {
+	_Base::clear();
+	this->_M_invalidate_all();
+      }
+      
+      _Base&       
+      _M_base()       { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+    };
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator==(const deque<_Tp, _Alloc>& __lhs, 
+	       const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator!=(const deque<_Tp, _Alloc>& __lhs, 
+	       const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<=(const deque<_Tp, _Alloc>& __lhs, 
+	       const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>=(const deque<_Tp, _Alloc>& __lhs, 
+	       const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>(const deque<_Tp, _Alloc>& __lhs, const deque<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline void
+    swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
+    { __lhs.swap(__rhs); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
new file mode 100644
index 00000000000..317ce21bc25
--- /dev/null
+++ b/libstdc++-v3/include/debug/formatter.h
@@ -0,0 +1,385 @@
+// Debug-mode error formatting implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_FORMATTER_H
+#define _GLIBCXX_DEBUG_FORMATTER_H 1
+
+#include <typeinfo>
+#include <debug/debug.h>
+
+namespace __gnu_debug
+{
+  /** Determine if the two types are the same. */
+  template<typename _Type1, typename _Type2>
+    struct __is_same
+    {
+      static const bool value = false;
+    };
+
+  template<typename _Type>
+    struct __is_same<_Type, _Type>
+    {
+      static const bool value = true;
+    };
+
+  template<bool> struct __truth { };
+
+  class _Safe_sequence_base;
+
+  template<typename _Iterator, typename _Sequence> 
+    class _Safe_iterator;
+
+  template<typename _Sequence> 
+    class _Safe_sequence;
+
+  enum _Debug_msg_id
+  {
+    // General checks
+    __msg_valid_range,
+    __msg_insert_singular,
+    __msg_insert_different,
+    __msg_erase_bad,
+    __msg_erase_different,
+    __msg_subscript_oob,
+    __msg_empty,
+    __msg_unpartitioned,
+    __msg_unpartitioned_pred,
+    __msg_unsorted,
+    __msg_unsorted_pred,
+    __msg_not_heap,
+    __msg_not_heap_pred,
+    // std::bitset checks
+    __msg_bad_bitset_write,
+    __msg_bad_bitset_read,
+    __msg_bad_bitset_flip,
+    // std::list checks
+    __msg_self_splice,
+    __msg_splice_alloc,
+    __msg_splice_bad,
+    __msg_splice_other,
+    __msg_splice_overlap,
+    // iterator checks
+    __msg_init_singular,
+    __msg_init_copy_singular,
+    __msg_init_const_singular,
+    __msg_copy_singular,
+    __msg_bad_deref,
+    __msg_bad_inc,
+    __msg_bad_dec,
+    __msg_iter_subscript_oob,
+    __msg_advance_oob,
+    __msg_retreat_oob,
+    __msg_iter_compare_bad,
+    __msg_compare_different,
+    __msg_iter_order_bad,
+    __msg_order_different,
+    __msg_distance_bad,
+    __msg_distance_different,
+    // istream_iterator
+    __msg_deref_istream,
+    __msg_inc_istream,
+    // ostream_iterator
+    __msg_output_ostream,
+    // istreambuf_iterator
+    __msg_deref_istreambuf,
+    __msg_inc_istreambuf
+  };
+
+  class _Error_formatter
+  {
+    /// Whether an iterator is constant, mutable, or unknown
+    enum _Constness
+    {
+      __unknown_constness,
+      __const_iterator,
+      __mutable_iterator,
+      __last_constness
+    }; 
+
+    // The state of the iterator (fine-grained), if we know it.
+    enum _Iterator_state
+    {
+      __unknown_state,
+      __singular,      // singular, may still be attached to a sequence
+      __begin,         // dereferenceable, and at the beginning
+      __middle,        // dereferenceable, not at the beginning
+      __end,           // past-the-end, may be at beginning if sequence empty
+      __last_state
+    };
+
+    // Tags denoting the type of parameter for construction
+    struct _Is_iterator { };
+    struct _Is_sequence { };
+
+    // A parameter that may be referenced by an error message
+    struct _Parameter
+    {
+      enum 
+      { 
+	__unused_param, 
+	__iterator, 
+	__sequence, 
+	__integer,
+	__string
+      } _M_kind;
+      
+      union
+      {
+	// When _M_kind == __iterator
+	struct 
+	{
+	  const char*      _M_name;      
+	  const void*      _M_address;   
+	  const type_info* _M_type;   
+	  _Constness       _M_constness;
+	  _Iterator_state  _M_state;
+	  const void*      _M_sequence;  
+	  const type_info* _M_seq_type;
+	} _M_iterator;
+	
+	// When _M_kind == __sequence
+	struct
+	{
+	  const char*      _M_name;
+	  const void*      _M_address;
+	  const type_info* _M_type;
+	} _M_sequence;
+
+	// When _M_kind == __integer
+	struct
+	{
+	  const char* _M_name;
+	  long        _M_value;
+	} _M_integer;
+
+	// When _M_kind == __string
+	struct
+	{
+	  const char* _M_name;
+	  const char* _M_value;
+	} _M_string;
+      } _M_variant;
+
+      _Parameter() : _M_kind(__unused_param) { }
+      
+      _Parameter(long __value, const char* __name) 
+      : _M_kind(__integer)
+      { 
+	_M_variant._M_integer._M_name = __name;
+	_M_variant._M_integer._M_value = __value; 
+      }
+
+      _Parameter(const char* __value, const char* __name)
+      : _M_kind(__string)
+      {
+	_M_variant._M_string._M_name = __name;
+	_M_variant._M_string._M_value = __value; 
+      }
+
+      template<typename _Iterator, typename _Sequence>
+        _Parameter(const _Safe_iterator<_Iterator, _Sequence>& __it,
+		   const char* __name, _Is_iterator)
+	: _M_kind(__iterator)
+        {
+	  _M_variant._M_iterator._M_name = __name;
+	  _M_variant._M_iterator._M_address = &__it;
+	  _M_variant._M_iterator._M_type = &typeid(__it);
+	  _M_variant._M_iterator._M_constness = 
+	    __is_same<_Safe_iterator<_Iterator, _Sequence>,
+	                         typename _Sequence::iterator>::
+	      value? __mutable_iterator : __const_iterator;
+	  _M_variant._M_iterator._M_sequence = __it._M_get_sequence();
+	  _M_variant._M_iterator._M_seq_type = &typeid(_Sequence);
+
+	  if (__it._M_singular())
+	    _M_variant._M_iterator._M_state = __singular;
+	  else
+	    {
+	      bool __is_begin = __it._M_is_begin();
+	      bool __is_end = __it._M_is_end();
+	      if (__is_end)
+		_M_variant._M_iterator._M_state = __end;
+	      else if (__is_begin)
+		_M_variant._M_iterator._M_state = __begin;
+	      else
+		_M_variant._M_iterator._M_state = __middle;
+	    }
+	}
+
+      template<typename _Type>
+        _Parameter(const _Type*& __it, const char* __name, _Is_iterator)
+	: _M_kind(__iterator)
+        {
+	  _M_variant._M_iterator._M_name = __name;
+	  _M_variant._M_iterator._M_address = &__it;
+	  _M_variant._M_iterator._M_type = &typeid(__it);
+	  _M_variant._M_iterator._M_constness = __mutable_iterator;
+	  _M_variant._M_iterator._M_state = __it? __unknown_state : __singular;
+	  _M_variant._M_iterator._M_sequence = 0;
+	  _M_variant._M_iterator._M_seq_type = 0;
+	}
+
+      template<typename _Type>
+        _Parameter(_Type*& __it, const char* __name, _Is_iterator)
+        : _M_kind(__iterator)
+        {
+	  _M_variant._M_iterator._M_name = __name;
+	  _M_variant._M_iterator._M_address = &__it;
+	  _M_variant._M_iterator._M_type = &typeid(__it);
+	  _M_variant._M_iterator._M_constness = __const_iterator;
+	  _M_variant._M_iterator._M_state = __it? __unknown_state : __singular;
+	  _M_variant._M_iterator._M_sequence = 0;
+	  _M_variant._M_iterator._M_seq_type = 0;
+	}
+      
+      template<typename _Iterator>
+        _Parameter(const _Iterator& __it, const char* __name, _Is_iterator)
+	: _M_kind(__iterator)
+        {
+	  _M_variant._M_iterator._M_name = __name;
+	  _M_variant._M_iterator._M_address = &__it;
+	  _M_variant._M_iterator._M_type = &typeid(__it);
+	  _M_variant._M_iterator._M_constness = __unknown_constness;
+	  _M_variant._M_iterator._M_state = 
+	    __gnu_debug::__check_singular(__it)? __singular : __unknown_state;
+	  _M_variant._M_iterator._M_sequence = 0;
+	  _M_variant._M_iterator._M_seq_type = 0;
+	}
+
+      template<typename _Sequence>
+        _Parameter(const _Safe_sequence<_Sequence>& __seq,
+		   const char* __name, _Is_sequence)
+	: _M_kind(__sequence)
+        {
+	  _M_variant._M_sequence._M_name = __name;
+	  _M_variant._M_sequence._M_address = 
+	    static_cast<const _Sequence*>(&__seq);
+	  _M_variant._M_sequence._M_type = &typeid(_Sequence);
+	}
+
+      template<typename _Sequence>
+        _Parameter(const _Sequence& __seq, const char* __name, _Is_sequence)
+	: _M_kind(__sequence)
+        {
+	  _M_variant._M_sequence._M_name = __name;
+	  _M_variant._M_sequence._M_address = &__seq;
+	  _M_variant._M_sequence._M_type = &typeid(_Sequence);
+	}
+      
+      void
+      _M_print_field(const _Error_formatter* __formatter, 
+		     const char* __name) const;
+					 
+      void
+      _M_print_description(const _Error_formatter* __formatter) const;
+    };
+
+    friend struct _Parameter;
+
+  public:    
+    template<typename _Iterator>
+      const _Error_formatter&
+      _M_iterator(const _Iterator& __it, const char* __name = 0)  const
+      {
+	if (_M_num_parameters < __max_parameters)
+	  _M_parameters[_M_num_parameters++] = _Parameter(__it, __name,
+							  _Is_iterator());
+	return *this;
+      }
+
+    const _Error_formatter&
+    _M_integer(long __value, const char* __name = 0) const
+    {
+      if (_M_num_parameters < __max_parameters)
+	_M_parameters[_M_num_parameters++] = _Parameter(__value, __name);
+      return *this;
+    }
+
+    const _Error_formatter&
+    _M_string(const char* __value, const char* __name = 0) const
+    {
+      if (_M_num_parameters < __max_parameters)
+	_M_parameters[_M_num_parameters++] = _Parameter(__value, __name);
+      return *this;
+    }
+
+    template<typename _Sequence>
+      const _Error_formatter&
+      _M_sequence(const _Sequence& __seq, const char* __name = 0) const
+      {
+	if (_M_num_parameters < __max_parameters)
+	  _M_parameters[_M_num_parameters++] = _Parameter(__seq, __name, 
+							  _Is_sequence());
+	return *this;
+      }
+
+    const _Error_formatter&
+    _M_message(const char* __text) const
+    { _M_text = __text; return *this; }
+
+    const _Error_formatter&
+    _M_message(_Debug_msg_id __id) const;
+
+    void 
+    _M_error() const;
+
+  private:
+    _Error_formatter(const char* __file, size_t __line)
+    : _M_file(__file), _M_line(__line), _M_num_parameters(0), _M_text(0),
+      _M_max_length(78), _M_column(1), _M_first_line(true), _M_wordwrap(false)
+    { }
+
+    void 
+    _M_print_word(const char* __word) const;
+
+    void 
+    _M_print_string(const char* __string) const;
+
+    enum { __max_parameters = 9 };
+
+    const char*         _M_file;
+    size_t              _M_line;
+    mutable _Parameter  _M_parameters[__max_parameters];
+    mutable size_t      _M_num_parameters;
+    mutable const char* _M_text;
+    mutable size_t      _M_max_length;
+    enum { _M_indent = 4 } ;
+    mutable size_t      _M_column;
+    mutable bool        _M_first_line;
+    mutable bool        _M_wordwrap;
+
+  public:
+    static _Error_formatter
+    _M_at(const char* __file, size_t __line)
+    { return _Error_formatter(__file, __line); }
+  };
+} // namespace __gnu_debug
+
+#endif 
diff --git a/libstdc++-v3/include/debug/hash_map b/libstdc++-v3/include/debug/hash_map
new file mode 100644
index 00000000000..570a9af6b69
--- /dev/null
+++ b/libstdc++-v3/include/debug/hash_map
@@ -0,0 +1,38 @@
+// Debugging hash_map/hash_multimap implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_MAP
+#define _GLIBCXX_DEBUG_HASH_MAP 1
+
+#include <hash_map>
+#include <debug/dbg_hash_map.h>
+#include <debug/dbg_hash_multimap.h>
+
+#endif
diff --git a/libstdc++-v3/include/debug/hash_map.h b/libstdc++-v3/include/debug/hash_map.h
new file mode 100644
index 00000000000..5ca102ad68a
--- /dev/null
+++ b/libstdc++-v3/include/debug/hash_map.h
@@ -0,0 +1,270 @@
+// Debugging hash_map implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_MAP_H
+#define _GLIBCXX_DEBUG_HASH_MAP_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Value, typename _Tp,
+	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
+	   typename _EqualKey = std::equal_to<_Value>,
+	   typename _Alloc = std::allocator<_Value> >
+    class hash_map
+    : public __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>,
+      public __gnu_debug::_Safe_sequence<hash_map<_Value, _Tp, _HashFcn,
+						 _EqualKey, _Alloc> >
+    {
+      typedef __gnu_cxx::hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc> 
+      							_Base;
+      typedef __gnu_debug::_Safe_sequence<hash_map> 	_Safe_base;
+
+    public:
+      typedef typename _Base::key_type        key_type;
+      typedef typename _Base::data_type       data_type;
+      typedef typename _Base::mapped_type     mapped_type;
+      typedef typename _Base::value_type      value_type;
+      typedef typename _Base::hasher          hasher;
+      typedef typename _Base::key_equal       key_equal;
+      typedef typename _Base::size_type       size_type;
+      typedef typename _Base::difference_type difference_type;
+      typedef typename _Base::pointer         pointer;
+      typedef typename _Base::const_pointer   const_pointer;
+      typedef typename _Base::reference       reference;
+      typedef typename _Base::const_reference const_reference;
+      
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_map>
+      					      iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 
+					  hash_map>
+      					      const_iterator;
+      
+      typedef typename _Base::allocator_type  allocator_type;
+
+      using _Base::hash_funct;
+      using _Base::key_eq;
+      using _Base::get_allocator;
+      
+      hash_map() { }
+      
+      explicit hash_map(size_type __n) : _Base(__n) { }
+      
+      hash_map(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
+
+      hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
+	       const allocator_type& __a = allocator_type())
+      : _Base(__n, __hf, __eql, __a) { }
+    
+      template<typename _InputIterator>
+        hash_map(_InputIterator __f, _InputIterator __l)
+        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
+
+      template<typename _InputIterator>
+        hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
+
+      template<typename _InputIterator>
+        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
+		 const hasher& __hf)
+        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
+
+      template<typename _InputIterator>
+        hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
+		 const hasher& __hf, const key_equal& __eql,
+		 const allocator_type& __a = allocator_type())
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
+		__eql, __a) { }
+
+      hash_map(const _Base& __x) : _Base(__x), _Safe_base() { }
+
+      using _Base::size;
+      using _Base::max_size;
+      using _Base::empty;
+      
+      void 
+      swap(hash_map& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+      
+      iterator 
+      begin() { return iterator(_Base::begin(), this); }
+
+      iterator 
+      end() { return iterator(_Base::end(),   this); }
+      
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+      
+      const_iterator 
+      end() const 
+      { return const_iterator(_Base::end(),   this); }
+      
+      std::pair<iterator, bool> 
+      insert(const value_type& __obj)
+      { 
+	std::pair<typename _Base::iterator, bool> __res = _Base::insert(__obj);
+	return std::make_pair(iterator(__res.first, this), __res.second);
+      }
+      
+      template <typename _InputIterator>
+        void 
+        insert(_InputIterator __first, _InputIterator __last) 
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::insert(__first.base(), __last.base());
+	}
+
+
+      std::pair<iterator, bool> 
+      insert_noresize(const value_type& __obj)
+      { 
+	std::pair<typename _Base::iterator, bool> __res = 
+	                                        _Base::insert_noresize(__obj);
+	return std::make_pair(iterator(__res.first, this), __res.second);
+      }
+      
+      iterator 
+      find(const key_type& __key)
+      { return iterator(_Base::find(__key), this); }
+      
+      const_iterator 
+      find(const key_type& __key) const 
+      { return const_iterator(_Base::find(__key), this); }
+      
+      using _Base::operator[];
+      using _Base::count;
+      
+      std::pair<iterator, iterator> 
+      equal_range(const key_type& __key)
+      { 
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res = 
+	                  _Base::equal_range(__key);
+	return std::make_pair(iterator(__res.first, this),
+			      iterator(__res.second, this));
+      }
+      
+      std::pair<const_iterator, const_iterator> 
+      equal_range(const key_type& __key) const
+      { 
+	typedef typename _Base::const_iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res = 
+	_Base::equal_range(__key);
+	return std::make_pair(const_iterator(__res.first, this),
+			      const_iterator(__res.second, this));
+      }
+      
+      size_type 
+      erase(const key_type& __key) 
+      {
+	iterator __victim(_Base::find(__key), this);
+	if (__victim != end())
+  	  return this->erase(__victim), 1;
+	else
+	  return 0;
+      }
+      
+      void 
+      erase(iterator __it) 
+      {
+	__glibcxx_check_erase(__it);
+	__it._M_invalidate();
+	_Base::erase(__it.base());
+      }
+      
+      void 
+      erase(iterator __first, iterator __last)
+      {
+	__glibcxx_check_erase_range(__first, __last);
+	for (iterator __tmp = __first; __tmp != __last;)
+	{
+	  iterator __victim = __tmp++;
+	  __victim._M_invalidate();
+	}
+	_Base::erase(__first.base(), __last.base());
+      }
+      
+      void 
+      clear() 
+      { 
+	_Base::clear();
+	this->_M_invalidate_all(); 
+      }
+      
+      using _Base::resize;
+      using _Base::bucket_count;
+      using _Base::max_bucket_count;
+      using _Base::elems_in_bucket;
+      
+      _Base&       
+      _M_base()       { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+      
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+  
+  template<typename _Value, typename _Tp, typename _HashFcn, 
+	   typename _EqualKey, typename _Alloc>
+    inline bool
+    operator==(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
+	       const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
+    { return __x._M_base() == __y._M_base(); }
+
+  template<typename _Value, typename _Tp, typename _HashFcn, 
+	   typename _EqualKey, typename _Alloc>
+    inline bool
+    operator!=(const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
+	       const hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
+    { return __x._M_base() != __y._M_base(); }
+
+  template<typename _Value, typename _Tp, typename _HashFcn, 
+	   typename _EqualKey, typename _Alloc>
+    inline void
+    swap(hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
+	 hash_map<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
+    { __x.swap(__y); }
+} // namespace __gnu_debug_def
+
+#endif 
diff --git a/libstdc++-v3/include/debug/hash_multimap.h b/libstdc++-v3/include/debug/hash_multimap.h
new file mode 100644
index 00000000000..dd453d61c72
--- /dev/null
+++ b/libstdc++-v3/include/debug/hash_multimap.h
@@ -0,0 +1,261 @@
+// Debugging hash_multimap implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_MULTIMAP_H
+#define _GLIBCXX_DEBUG_HASH_MULTIMAP_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Value, typename _Tp,
+	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
+	   typename _EqualKey = std::equal_to<_Value>,
+	   typename _Alloc =  std::allocator<_Value> >
+    class hash_multimap
+    : public __gnu_cxx::hash_multimap<_Value,_Tp,_HashFcn, _EqualKey,_Alloc>,
+      public __gnu_debug::_Safe_sequence<hash_multimap<_Value, _Tp, _HashFcn,
+						       _EqualKey, _Alloc> >
+    {
+      typedef __gnu_cxx::hash_multimap<_Value,_Tp,_HashFcn, _EqualKey,_Alloc>
+      							_Base;
+      typedef __gnu_debug::_Safe_sequence<hash_multimap> _Safe_base;
+
+  public:
+      typedef typename _Base::key_type        		key_type;
+      typedef typename _Base::data_type       		data_type;
+      typedef typename _Base::mapped_type     		mapped_type;
+      typedef typename _Base::value_type      		value_type;
+      typedef typename _Base::hasher          		hasher;
+      typedef typename _Base::key_equal       		key_equal;
+      typedef typename _Base::size_type       		size_type;
+      typedef typename _Base::difference_type 		difference_type;
+      typedef typename _Base::pointer         		pointer;
+      typedef typename _Base::const_pointer   		const_pointer;
+      typedef typename _Base::reference       		reference;
+      typedef typename _Base::const_reference 		const_reference;
+
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 
+					  hash_multimap> iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+					  hash_multimap> const_iterator;
+
+      typedef typename _Base::allocator_type              allocator_type;
+
+      using _Base::hash_funct;
+      using _Base::key_eq;
+      using _Base::get_allocator;
+      
+      hash_multimap() { }
+      
+      explicit hash_multimap(size_type __n) : _Base(__n) { }
+      
+      hash_multimap(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
+
+      hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
+		    const allocator_type& __a = allocator_type())
+      : _Base(__n, __hf, __eql, __a) { }
+    
+      template<typename _InputIterator>
+        hash_multimap(_InputIterator __f, _InputIterator __l)
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
+
+      template<typename _InputIterator>
+        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
+        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
+
+      template<typename _InputIterator>
+        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
+		      const hasher& __hf)
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
+
+      template<typename _InputIterator>
+        hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
+		      const hasher& __hf, const key_equal& __eql,
+		      const allocator_type& __a = allocator_type())
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
+		__eql, __a) { }
+
+      using _Base::size;
+      using _Base::max_size;
+      using _Base::empty;
+      
+      void 
+      swap(hash_multimap& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+      
+      iterator 
+      begin() { return iterator(_Base::begin(), this); }
+
+      iterator 
+      end()   { return iterator(_Base::end(),   this); }
+      
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+      
+      const_iterator 
+      end() const 
+      { return const_iterator(_Base::end(),   this); }
+      
+      iterator
+      insert(const value_type& __obj)
+      { return iterator(_Base::insert(__obj), this); }
+      
+      template <typename _InputIterator>
+        void 
+        insert(_InputIterator __first, _InputIterator __last) 
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::insert(__first.base(), __last.base());
+	}
+      
+      iterator
+      insert_noresize(const value_type& __obj)
+      { return iterator(_Base::insert_noresize(__obj), this); }
+      
+      iterator 
+      find(const key_type& __key)
+      { return iterator(_Base::find(__key), this); }
+      
+      const_iterator 
+      find(const key_type& __key) const 
+      { return const_iterator(_Base::find(__key), this); }
+      
+      using _Base::count;
+      
+      std::pair<iterator, iterator> 
+      equal_range(const key_type& __key)
+      { 
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res = 
+	                                             _Base::equal_range(__key);
+	return std::make_pair(iterator(__res.first, this),
+			      iterator(__res.second, this));
+      }
+      
+      std::pair<const_iterator, const_iterator> 
+      equal_range(const key_type& __key) const
+      { 
+	typedef typename _Base::const_iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res = 
+        _Base::equal_range(__key);
+	return std::make_pair(const_iterator(__res.first, this),
+			      const_iterator(__res.second, this));
+      }
+      
+      size_type 
+      erase(const key_type& __key) 
+      {
+	std::pair<iterator, iterator> __victims = this->equal_range(__key);
+	size_t __num_victims = 0;
+	while (__victims.first != __victims.second) 
+	{
+	  this->erase(__victims.first++);
+	  ++__num_victims;
+	}
+	return __num_victims;
+      }
+    
+      void 
+      erase(iterator __it) 
+      {
+	__glibcxx_check_erase(__it);
+	__it._M_invalidate();
+	_Base::erase(__it.base());
+      }
+      
+      void 
+      erase(iterator __first, iterator __last)
+      {
+	__glibcxx_check_erase_range(__first, __last);
+	for (iterator __tmp = __first; __tmp != __last;)
+	{
+	  iterator __victim = __tmp++;
+	  __victim._M_invalidate();
+	}
+	_Base::erase(__first.base(), __last.base());
+      }
+      
+      void 
+      clear() 
+      { 
+	_Base::clear();
+	this->_M_invalidate_all(); 
+      }
+      
+      using _Base::resize;
+      using _Base::bucket_count;
+      using _Base::max_bucket_count;
+      using _Base::elems_in_bucket;
+      
+      _Base&       
+      _M_base()       { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+      
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+  
+  template<typename _Value, typename _Tp, typename _HashFcn, 
+	   typename _EqualKey, typename _Alloc>
+    inline bool
+    operator==(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
+	       const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
+    { return __x._M_base() == __y._M_base(); }
+
+  template<typename _Value, typename _Tp, typename _HashFcn, 
+	   typename _EqualKey, typename _Alloc>
+    inline bool
+    operator!=(const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __x,
+	       const hash_multimap<_Value,_Tp,_HashFcn,_EqualKey,_Alloc>& __y)
+    { return __x._M_base() != __y._M_base(); }
+  
+  template<typename _Value, typename _Tp, typename _HashFcn, 
+	   typename _EqualKey, typename _Alloc>
+    inline void
+    swap(hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __x,
+	 hash_multimap<_Value, _Tp, _HashFcn, _EqualKey, _Alloc>& __y)
+    { __x.swap(__y); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/hash_multiset.h b/libstdc++-v3/include/debug/hash_multiset.h
new file mode 100644
index 00000000000..cacad0353be
--- /dev/null
+++ b/libstdc++-v3/include/debug/hash_multiset.h
@@ -0,0 +1,236 @@
+// Debugging hash_multiset implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_MULTISET_H
+#define _GLIBCXX_DEBUG_HASH_MULTISET_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Value,
+	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
+	   typename _EqualKey = std::equal_to<_Value>,
+	   typename _Alloc =  std::allocator<_Value> >
+    class hash_multiset
+    : public __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>,
+      public __gnu_debug::_Safe_sequence<hash_multiset<_Value, _HashFcn,
+						       _EqualKey, _Alloc> >
+    {
+      typedef __gnu_cxx:: hash_multiset<_Value,_HashFcn, _EqualKey,_Alloc>
+      							_Base;
+      typedef __gnu_debug::_Safe_sequence<hash_multiset> _Safe_base;
+
+  public:
+    typedef typename _Base::key_type        		key_type;
+    typedef typename _Base::value_type      		value_type;
+    typedef typename _Base::hasher          		hasher;
+    typedef typename _Base::key_equal       		key_equal;
+    typedef typename _Base::size_type       		size_type;
+    typedef typename _Base::difference_type 		difference_type;
+    typedef typename _Base::pointer         		pointer;
+    typedef typename _Base::const_pointer   		const_pointer;
+    typedef typename _Base::reference       		reference;
+    typedef typename _Base::const_reference 		const_reference;
+
+    typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, 
+					 hash_multiset> iterator;
+    typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+					 hash_multiset> const_iterator;
+
+    typedef typename _Base::allocator_type              allocator_type;
+
+    using _Base::hash_funct;
+    using _Base::key_eq;
+    using _Base::get_allocator;
+
+    hash_multiset() { }
+
+    explicit hash_multiset(size_type __n) : _Base(__n) { }
+
+    hash_multiset(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
+
+    hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
+		  const allocator_type& __a = allocator_type())
+    : _Base(__n, __hf, __eql, __a)
+    { }
+    
+    template<typename _InputIterator>
+      hash_multiset(_InputIterator __f, _InputIterator __l)
+      : _Base(__gnu_debug::__check_valid_range(__f, __l), __l)
+      { }
+
+    template<typename _InputIterator>
+      hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
+      : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n)
+      { }
+
+    template<typename _InputIterator>
+      hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
+		    const hasher& __hf)
+      : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf)
+      { }
+
+    template<typename _InputIterator>
+      hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
+		    const hasher& __hf, const key_equal& __eql,
+		    const allocator_type& __a = allocator_type())
+      : _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
+	      __eql, __a)
+      { }
+
+    hash_multiset(const _Base& __x) : _Base(__x), _Safe_base() { }
+
+    using _Base::size;
+    using _Base::max_size;
+    using _Base::empty;
+
+    void 
+    swap(hash_multiset& __x)
+    {
+      _Base::swap(__x);
+      this->_M_swap(__x);
+    }
+
+    iterator begin() const { return iterator(_Base::begin(), this); }
+    iterator end() const   { return iterator(_Base::end(),   this); }
+
+    iterator
+    insert(const value_type& __obj)
+    { return iterator(_Base::insert(__obj), this); }
+
+    template <typename _InputIterator>
+      void 
+      insert(_InputIterator __first, _InputIterator __last) 
+      {
+	__glibcxx_check_valid_range(__first, __last);
+	_Base::insert(__first.base(), __last.base());
+      }
+
+
+    iterator
+    insert_noresize(const value_type& __obj)
+    { return iterator(_Base::insert_noresize(__obj), this); }
+
+    iterator 
+    find(const key_type& __key) const 
+    { return iterator(_Base::find(__key), this); }
+
+    using _Base::count;
+    
+    std::pair<iterator, iterator> 
+    equal_range(const key_type& __key) const
+    { 
+      typedef typename _Base::iterator _Base_iterator;
+      std::pair<_Base_iterator, _Base_iterator> __res = 
+	_Base::equal_range(__key);
+      return std::make_pair(iterator(__res.first, this),
+			    iterator(__res.second, this));
+    }
+
+    size_type 
+    erase(const key_type& __key) 
+    {
+      size_type __count = 0;
+      std::pair<iterator, iterator> __victims = this->equal_range(__key);
+      while (__victims.first != __victims.second)
+	{
+	  this->erase(__victims++);
+	  ++__count;
+	}
+      return __count;
+    }
+    
+    void 
+    erase(iterator __it) 
+    {
+      __glibcxx_check_erase(__it);
+      __it._M_invalidate();
+      _Base::erase(__it.base());
+    }
+
+    void 
+    erase(iterator __first, iterator __last)
+    {
+      __glibcxx_check_erase_range(__first, __last);
+      for (iterator __tmp = __first; __tmp != __last;)
+	{
+	  iterator __victim = __tmp++;
+	  __victim._M_invalidate();
+	}
+      _Base::erase(__first.base(), __last.base());
+    }
+
+    void 
+    clear() 
+    { 
+      _Base::clear();
+      this->_M_invalidate_all(); 
+    }
+
+    using _Base::resize;
+    using _Base::bucket_count;
+    using _Base::max_bucket_count;
+    using _Base::elems_in_bucket;
+
+    _Base&       _M_base()       { return *this; }
+    const _Base& _M_base() const { return *this; }
+
+  private:
+    void 
+    _M_invalidate_all()
+    {
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+      this->_M_invalidate_if(_Not_equal(_M_base().end()));
+    }
+  };
+
+template<typename _Value, typename _HashFcn, typename _EqualKey, typename _Alloc>
+  inline bool
+  operator==(const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
+	     const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
+  { return __x._M_base() == __y._M_base(); }
+
+template<typename _Value, typename _HashFcn, typename _EqualKey, typename _Alloc>
+  inline bool
+  operator!=(const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
+	     const hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
+  { return __x._M_base() != __y._M_base(); }
+
+template<typename _Value, typename _HashFcn, typename _EqualKey, typename _Alloc>
+  inline void
+  swap(hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
+       hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
+  { __x.swap(__y); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/hash_set b/libstdc++-v3/include/debug/hash_set
new file mode 100644
index 00000000000..13d879de5bb
--- /dev/null
+++ b/libstdc++-v3/include/debug/hash_set
@@ -0,0 +1,38 @@
+// Debugging hash_set/hash_multiset implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_SET
+#define _GLIBCXX_DEBUG_HASH_SET 1
+
+#include <hash_set>
+#include <debug/dbg_hash_set.h>
+#include <debug/dbg_hash_multiset.h>
+
+#endif 
diff --git a/libstdc++-v3/include/debug/hash_set.h b/libstdc++-v3/include/debug/hash_set.h
new file mode 100644
index 00000000000..88afb9092d9
--- /dev/null
+++ b/libstdc++-v3/include/debug/hash_set.h
@@ -0,0 +1,245 @@
+// Debugging hash_set implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_HASH_SET_H
+#define _GLIBCXX_DEBUG_HASH_SET_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Value,
+	   typename _HashFcn  = __gnu_cxx::hash<_Value>,
+	   typename _EqualKey = std::equal_to<_Value>,
+	   typename _Alloc =  std::allocator<_Value> >
+    class hash_set
+    : public __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>,
+      public __gnu_debug::_Safe_sequence<hash_set<_Value, _HashFcn, _EqualKey,
+						  _Alloc> >
+    {
+      typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Base;
+      typedef __gnu_debug::_Safe_sequence<hash_set> _Safe_base;
+      
+    public:
+      typedef typename _Base::key_type        key_type;
+      typedef typename _Base::value_type      value_type;
+      typedef typename _Base::hasher          hasher;
+      typedef typename _Base::key_equal       key_equal;
+      typedef typename _Base::size_type       size_type;
+      typedef typename _Base::difference_type difference_type;
+      typedef typename _Base::pointer         pointer;
+      typedef typename _Base::const_pointer   const_pointer;
+      typedef typename _Base::reference       reference;
+      typedef typename _Base::const_reference const_reference;
+
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, hash_set>
+                                              iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+					  hash_set>
+                                              const_iterator;
+
+      typedef typename _Base::allocator_type allocator_type;
+      
+      using _Base::hash_funct;
+      using _Base::key_eq;
+      using _Base::get_allocator;
+      
+      hash_set() { }
+      
+      explicit hash_set(size_type __n) : _Base(__n) { }
+      
+      hash_set(size_type __n, const hasher& __hf) : _Base(__n, __hf) { }
+      
+      hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
+	       const allocator_type& __a = allocator_type())
+      : _Base(__n, __hf, __eql, __a) { }
+    
+      template<typename _InputIterator>
+        hash_set(_InputIterator __f, _InputIterator __l)
+        : _Base(__gnu_debug::__check_valid_range(__f, __l), __l) { }
+
+      template<typename _InputIterator>
+        hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n) { }
+
+      template<typename _InputIterator>
+        hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
+		 const hasher& __hf)
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf) { }
+
+      template<typename _InputIterator>
+        hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
+		 const hasher& __hf, const key_equal& __eql,
+		 const allocator_type& __a = allocator_type())
+	: _Base(__gnu_debug::__check_valid_range(__f, __l), __l, __n, __hf,
+		__eql, __a) { }
+
+      hash_set(const _Base& __x) : _Base(__x), _Safe_base() { }
+      
+      using _Base::size;
+      using _Base::max_size;
+      using _Base::empty;
+      
+      void 
+      swap(hash_set& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+      
+      iterator 
+      begin() const { return iterator(_Base::begin(), this); }
+
+      iterator 
+      end() const   { return iterator(_Base::end(),   this); }
+
+      std::pair<iterator, bool> 
+      insert(const value_type& __obj)
+      { 		    
+	std::pair<typename _Base::iterator, bool> __res =
+        _Base::insert(__obj);
+	return std::make_pair(iterator(__res.first, this), __res.second);
+      }
+      
+      template <typename _InputIterator>
+        void 
+        insert(_InputIterator __first, _InputIterator __last) 
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::insert(__first.base(), __last.base());
+	}
+      
+
+      std::pair<iterator, bool> 
+      insert_noresize(const value_type& __obj)
+      {
+	std::pair<typename _Base::iterator, bool> __res =
+        _Base::insert_noresize(__obj);
+	return std::make_pair(iterator(__res.first, this), __res.second);
+      }
+      
+      iterator 
+      find(const key_type& __key) const 
+      { return iterator(_Base::find(__key), this); }
+      
+      using _Base::count;
+      
+      std::pair<iterator, iterator> 
+      equal_range(const key_type& __key) const
+      { 
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res = 
+	  _Base::equal_range(__key);
+	return std::make_pair(iterator(__res.first, this),
+			      iterator(__res.second, this));
+      }
+      
+      size_type 
+      erase(const key_type& __key) 
+      {
+	iterator __victim(_Base::find(__key), this);
+	if (__victim != end())
+	  return this->erase(__victim), 1;
+	else
+	  return 0;
+      }
+    
+      void 
+      erase(iterator __it) 
+      {
+	__glibcxx_check_erase(__it);
+	__it._M_invalidate();
+	_Base::erase(__it.base());
+      }
+      
+      void 
+      erase(iterator __first, iterator __last)
+      {
+	__glibcxx_check_erase_range(__first, __last);
+	for (iterator __tmp = __first; __tmp != __last;)
+	{
+	  iterator __victim = __tmp++;
+	  __victim._M_invalidate();
+	}
+	_Base::erase(__first.base(), __last.base());
+      }
+      
+      void 
+      clear() 
+      { 
+	_Base::clear();
+	this->_M_invalidate_all(); 
+      }
+      
+      using _Base::resize;
+      using _Base::bucket_count;
+      using _Base::max_bucket_count;
+      using _Base::elems_in_bucket;
+      
+      _Base&       
+      _M_base()       { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+
+  template<typename _Value, typename _HashFcn, typename _EqualKey, 
+	   typename _Alloc>
+    inline bool
+    operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
+	       const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
+    { return __x._M_base() == __y._M_base(); }
+
+  template<typename _Value, typename _HashFcn, typename _EqualKey, 
+	   typename _Alloc>
+    inline bool
+    operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
+	       const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
+    { return __x._M_base() != __y._M_base(); }
+
+  template<typename _Value, typename _HashFcn, typename _EqualKey, 
+	   typename _Alloc>
+    inline void
+    swap(hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __x,
+	 hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __y)
+    { __x.swap(__y); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
new file mode 100644
index 00000000000..79dcb1d13d8
--- /dev/null
+++ b/libstdc++-v3/include/debug/list
@@ -0,0 +1,505 @@
+// Debugging list implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_LIST
+#define _GLIBCXX_DEBUG_LIST 1
+
+#include <list>
+#include <bits/stl_algo.h>
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
+    class list
+    : public __gnu_norm::list<_Tp, _Allocator>,
+      public __gnu_debug::_Safe_sequence<list<_Tp, _Allocator> >
+    {
+      typedef __gnu_norm::list<_Tp, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
+
+    public:
+      typedef typename _Allocator::reference        reference;
+      typedef typename _Allocator::const_reference  const_reference;
+      
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list> 
+      						    iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
+						    const_iterator;
+
+      typedef typename _Base::size_type             size_type;
+      typedef typename _Base::difference_type       difference_type;
+      
+      typedef _Tp        			    value_type;
+      typedef _Allocator 			    allocator_type;
+      typedef typename _Allocator::pointer          pointer;
+      typedef typename _Allocator::const_pointer    const_pointer;
+      typedef std::reverse_iterator<iterator>       reverse_iterator;
+      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+      // 23.2.2.1 construct/copy/destroy:
+      explicit list(const _Allocator& __a = _Allocator())
+      : _Base(__a) { }
+
+      explicit list(size_type __n, const _Tp& __value = _Tp(),
+		    const _Allocator& __a = _Allocator())
+      : _Base(__n, __value, __a) { }
+
+      template<class _InputIterator>
+      list(_InputIterator __first, _InputIterator __last,
+	   const _Allocator& __a = _Allocator())
+	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a)
+      { }
+      
+
+      list(const list& __x) : _Base(__x), _Safe_base() { }
+      
+      list(const _Base& __x) : _Base(__x), _Safe_base() { }
+      
+      ~list() { }
+      
+      list& 
+      operator=(const list& __x)
+      {
+	static_cast<_Base&>(*this) = __x;
+	this->_M_invalidate_all();
+	return *this;
+      }
+      
+      template<class _InputIterator>
+        void 
+        assign(_InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::assign(__first, __last);
+	  this->_M_invalidate_all();
+	}
+      
+      void 
+      assign(size_type __n, const _Tp& __t)
+      {
+	_Base::assign(__n, __t);
+	this->_M_invalidate_all();
+      }
+      
+      using _Base::get_allocator;
+      
+      // iterators:
+      iterator       
+      begin()       
+      { return iterator(_Base::begin(), this); }
+      
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+      
+      iterator 
+      end() 
+      { return iterator(_Base::end(), this); }
+      
+      const_iterator 
+      end() const   
+      { return const_iterator(_Base::end(), this); }
+      
+      reverse_iterator 
+      rbegin() 
+      { return reverse_iterator(end()); }
+      
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+      
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+      
+      const_reverse_iterator 
+      rend() const 
+      { return const_reverse_iterator(begin()); }
+      
+      // 23.2.2.2 capacity:
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+      
+      void 
+      resize(size_type __sz, _Tp __c = _Tp())
+      {
+	this->_M_detach_singular();
+	
+	// if __sz < size(), invalidate all iterators in [begin+__sz, end())
+	iterator __victim = begin();
+	iterator __end = end();
+	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
+	  ++__victim;
+	
+	while (__victim != __end)
+	  {
+	    iterator __real_victim = __victim++;
+	    __real_victim._M_invalidate();
+	  }
+	
+	try 
+	  {
+	    _Base::resize(__sz, __c);
+	  }
+	catch(...)
+	  {
+	    this->_M_revalidate_singular();
+	    __throw_exception_again;
+	  }
+      }
+      
+      // element access:
+      reference 
+      front()
+      {
+	__glibcxx_check_nonempty();
+	return _Base::front();
+      }
+      
+      const_reference 
+      front() const
+      {
+	__glibcxx_check_nonempty();
+	return _Base::front();
+      }
+      
+      reference 
+      back()
+      {
+	__glibcxx_check_nonempty();
+	return _Base::back();
+      }
+      
+      const_reference 
+      back() const
+      {
+	__glibcxx_check_nonempty();
+	return _Base::back();
+      }
+      
+      // 23.2.2.3 modifiers:
+      using _Base::push_front;
+      
+      void 
+      pop_front()
+      {
+	__glibcxx_check_nonempty();
+	iterator __victim = begin();
+	__victim._M_invalidate();
+	_Base::pop_front();
+      }
+      
+      using _Base::push_back;
+      
+      void 
+      pop_back()
+      {
+	__glibcxx_check_nonempty();
+	iterator __victim = end();
+	--__victim;
+	__victim._M_invalidate();
+	_Base::pop_back();
+      }
+      
+      iterator 
+      insert(iterator __position, const _Tp& __x)
+      {
+	__glibcxx_check_insert(__position);
+	return iterator(_Base::insert(__position.base(), __x), this);
+      }
+      
+      void 
+      insert(iterator __position, size_type __n, const _Tp& __x)
+      {
+	__glibcxx_check_insert(__position);
+	_Base::insert(__position.base(), __n, __x);
+      }
+      
+      template<class _InputIterator>
+        void 
+        insert(iterator __position, _InputIterator __first,
+	       _InputIterator __last)
+        {
+	  __glibcxx_check_insert_range(__position, __first, __last);
+	  _Base::insert(__position.base(), __first, __last);
+	}
+      
+      iterator 
+      erase(iterator __position)
+      {
+	__glibcxx_check_erase(__position);
+	__position._M_invalidate();
+	return iterator(_Base::erase(__position.base()), this);
+      }
+      
+      iterator 
+      erase(iterator __position, iterator __last)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 151. can't currently clear() empty container
+	__glibcxx_check_erase_range(__position, __last);
+	for (iterator __victim = __position; __victim != __last; )
+	  {
+	    iterator __old = __victim;
+	    ++__victim;
+	    __old._M_invalidate();
+	  }
+	return iterator(_Base::erase(__position.base(), __last.base()), this);
+      }
+      
+      void 
+      swap(list& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+      
+      void 
+      clear()
+      {
+	_Base::clear();
+	this->_M_invalidate_all();
+      }
+      
+      // 23.2.2.4 list operations:
+      void 
+      splice(iterator __position, list& __x)
+      {
+	_GLIBCXX_DEBUG_VERIFY(&__x != this,
+			      _M_message(::__gnu_debug::__msg_self_splice)
+			      ._M_sequence(*this, "this"));
+	this->splice(__position, __x, __x.begin(), __x.end());
+      }
+      
+      void 
+      splice(iterator __position, list& __x, iterator __i)
+      {
+	__glibcxx_check_insert(__position);
+	_GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
+			      _M_message(::__gnu_debug::__msg_splice_alloc)
+			    ._M_sequence(*this)._M_sequence(__x, "__x"));
+	_GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(),
+			      _M_message(::__gnu_debug::__msg_splice_bad)
+			      ._M_iterator(__i, "__i"));
+	_GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__x),
+			      _M_message(::__gnu_debug::__msg_splice_other)
+			     ._M_iterator(__i, "__i")._M_sequence(__x, "__x"));
+	
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 250. splicing invalidates iterators
+	this->_M_transfer_iter(__i);
+	_Base::splice(__position.base(), __x._M_base(), __i.base());
+      }
+      
+      void 
+      splice(iterator __position, list& __x, iterator __first, iterator __last)
+      {
+	__glibcxx_check_insert(__position);
+	__glibcxx_check_valid_range(__first, __last);
+	_GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(&__x),
+			      _M_message(::__gnu_debug::__msg_splice_other)
+			      ._M_sequence(__x, "x")
+			      ._M_iterator(__first, "first"));
+	_GLIBCXX_DEBUG_VERIFY(__x.get_allocator() == this->get_allocator(),
+			      _M_message(::__gnu_debug::__msg_splice_alloc)
+			      ._M_sequence(*this)._M_sequence(__x));
+	
+	for (iterator __tmp = __first; __tmp != __last; )
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position,
+				_M_message(::__gnu_debug::__msg_splice_overlap)
+				  ._M_iterator(__tmp, "position")
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    iterator __victim = __tmp++;
+	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
+	    // 250. splicing invalidates iterators
+	    this->_M_transfer_iter(__victim);
+	  }
+	
+	_Base::splice(__position.base(), __x._M_base(), __first.base(),
+		      __last.base());
+      }
+      
+      void 
+      remove(const _Tp& __value)
+      {
+	for (iterator __x = begin(); __x.base() != _Base::end(); )
+	  {
+	    if (*__x == __value)
+	      __x = erase(__x);
+	    else
+	      ++__x;
+	  }
+      }
+      
+      template<class _Predicate> 
+        void 
+        remove_if(_Predicate __pred)
+        {
+	  for (iterator __x = begin(); __x.base() != _Base::end(); )
+	    {
+	      if (__pred(*__x))
+		__x = erase(__x);
+	      else
+		++__x;
+	    }
+	}
+      
+      void 
+      unique()
+      {
+	iterator __first = begin();
+	iterator __last = end();
+	if (__first == __last) 
+	  return;
+	iterator __next = __first;
+	while (++__next != __last)
+	  {
+	    if (*__first == *__next)
+	      erase(__next);
+	    else
+	      __first = __next;
+	    __next = __first;
+	  }
+      }
+      
+      template<class _BinaryPredicate>
+        void 
+        unique(_BinaryPredicate __binary_pred)
+        {
+	  iterator __first = begin();
+	  iterator __last = end();
+	  if (__first == __last) 
+	    return;
+	  iterator __next = __first;
+	  while (++__next != __last)
+	    {
+	      if (__binary_pred(*__first, *__next))
+		erase(__next);
+	      else
+		__first = __next;
+	      __next = __first;
+	    }
+	}
+      
+      void 
+      merge(list& __x)
+      {
+	__glibcxx_check_sorted(_Base::begin(), _Base::end());
+	__glibcxx_check_sorted(__x.begin().base(), __x.end().base());
+	for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
+	  {
+	    iterator __victim = __tmp++;
+	    __victim._M_attach(&__x);
+	  }
+	_Base::merge(__x._M_base());
+      }
+      
+      template<class _Compare> 
+        void 
+        merge(list& __x, _Compare __comp)
+        {
+	  __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
+	  __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 
+				      __comp);
+	  for (iterator __tmp = __x.begin(); __tmp != __x.end(); )
+	    {
+	      iterator __victim = __tmp++;
+	      __victim._M_attach(&__x);
+	    }
+	  _Base::merge(__x._M_base(), __comp);
+	}
+      
+      void 
+      sort() { _Base::sort(); }
+      
+      template<typename _StrictWeakOrdering>
+        void 
+        sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
+      
+      using _Base::reverse;
+      
+      _Base&       
+      _M_base()       { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+  
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator==(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator!=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+  
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+  
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>=(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+  
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>(const list<_Tp, _Alloc>& __lhs, const list<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+  
+  template<typename _Tp, typename _Alloc>
+    inline void
+    swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
+    { __lhs.swap(__rhs); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/map b/libstdc++-v3/include/debug/map
new file mode 100644
index 00000000000..2c384048718
--- /dev/null
+++ b/libstdc++-v3/include/debug/map
@@ -0,0 +1,38 @@
+// Debugging map/multimap implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_MAP
+#define _GLIBCXX_DEBUG_MAP 1
+
+#include <map>
+#include <debug/map.h>
+#include <debug/multimap.h>
+
+#endif
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
new file mode 100644
index 00000000000..d8609bdffb8
--- /dev/null
+++ b/libstdc++-v3/include/debug/map.h
@@ -0,0 +1,323 @@
+// Debugging map implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_MAP_H
+#define _GLIBCXX_DEBUG_MAP_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+#include <utility>
+
+namespace __gnu_debug_def
+{
+  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
+	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
+    class map
+    : public __gnu_norm::map<_Key, _Tp, _Compare, _Allocator>,
+      public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> >
+    {
+      typedef __gnu_norm::map<_Key, _Tp, _Compare, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<map> _Safe_base;
+
+    public:
+      // types:
+      typedef _Key                                  key_type;
+      typedef _Tp                                   mapped_type;
+      typedef std::pair<const _Key, _Tp>            value_type;
+      typedef _Compare                              key_compare;
+      typedef _Allocator                            allocator_type;
+      typedef typename _Allocator::reference        reference;
+      typedef typename _Allocator::const_reference  const_reference;
+      
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map> 
+                                                    iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, map>
+                                                    const_iterator;
+
+      typedef typename _Base::size_type             size_type;
+      typedef typename _Base::difference_type       difference_type;
+      typedef typename _Allocator::pointer          pointer;
+      typedef typename _Allocator::const_pointer    const_pointer;
+      typedef std::reverse_iterator<iterator>       reverse_iterator;
+      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+      
+      using _Base::value_compare;
+      
+      // 23.3.1.1 construct/copy/destroy:
+      explicit map(const _Compare& __comp = _Compare(), 
+		   const _Allocator& __a = _Allocator())
+      : _Base(__comp, __a) { }
+
+      template<typename _InputIterator>
+        map(_InputIterator __first, _InputIterator __last,
+	    const _Compare& __comp = _Compare(), 
+	    const _Allocator& __a = _Allocator())
+	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
+		__comp, __a), _Safe_base() { }
+
+      map(const map<_Key,_Tp,_Compare,_Allocator>& __x) 
+      : _Base(__x), _Safe_base() { } 
+      
+      map(const _Base& __x) : _Base(__x), _Safe_base() { }
+
+      ~map() { }
+      
+      map<_Key,_Tp,_Compare,_Allocator>&
+      operator=(const map<_Key,_Tp,_Compare,_Allocator>& __x)
+      {
+	*static_cast<_Base*>(this) = __x;
+	this->_M_invalidate_all();
+	return *this;
+      }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 133. map missing get_allocator()
+      using _Base::get_allocator;
+      
+      // iterators:
+      iterator       
+      begin()  
+      { return iterator(_Base::begin(), this); }
+      
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+      
+      iterator       
+      end()         
+      { return iterator(_Base::end(), this); }
+      
+      const_iterator 
+      end() const   
+      { return const_iterator(_Base::end(), this); }
+      
+      reverse_iterator 
+      rbegin() 
+      { return reverse_iterator(end()); }
+      
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+      
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+      
+      const_reverse_iterator 
+      rend() const 
+      { return const_reverse_iterator(begin()); }
+      
+      // capacity:
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+      
+      // 23.3.1.2 element access:
+      using _Base::operator[];
+      
+      // modifiers:
+      std::pair<iterator, bool> 
+      insert(const value_type& __x)
+      {
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
+	return std::pair<iterator, bool>(iterator(__res.first, this), 
+					 __res.second);
+      }
+      
+      iterator 
+      insert(iterator __position, const value_type& __x)
+      {
+	__glibcxx_check_insert(__position);
+	return iterator(_Base::insert(__position.base(), __x), this);
+      }
+      
+      template<typename _InputIterator>
+        void 
+        insert(_InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_valid_range(__first, __last);
+	  _Base::insert(__first, __last);
+	}
+      
+      void 
+      erase(iterator __position)
+      {
+	__glibcxx_check_erase(__position);
+	__position._M_invalidate();
+	_Base::erase(__position.base());
+      }
+      
+      size_type 
+      erase(const key_type& __x)
+      {
+	iterator __victim = find(__x);
+	if (__victim == end())
+	  return 0;
+	else
+	{
+	  __victim._M_invalidate();
+	  _Base::erase(__victim.base());
+	  return 1;
+	}
+      }
+      
+      void 
+      erase(iterator __first, iterator __last)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 151. can't currently clear() empty container
+	__glibcxx_check_erase_range(__first, __last);
+	while (__first != __last)
+	  this->erase(__first++);
+      }
+      
+      void 
+      swap(map<_Key,_Tp,_Compare,_Allocator>& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+      
+      void 
+      clear()
+      { this->erase(begin(), end()); }
+      
+      // observers:
+      using _Base::key_comp;
+      using _Base::value_comp;
+      
+      // 23.3.1.3 map operations:
+      iterator 
+      find(const key_type& __x)
+      { return iterator(_Base::find(__x), this); }
+      
+      const_iterator 
+      find(const key_type& __x) const
+      { return const_iterator(_Base::find(__x), this); }
+      
+      using _Base::count;
+      
+      iterator 
+      lower_bound(const key_type& __x)
+      { return iterator(_Base::lower_bound(__x), this); }
+      
+      const_iterator 
+      lower_bound(const key_type& __x) const
+      { return const_iterator(_Base::lower_bound(__x), this); }
+      
+      iterator 
+      upper_bound(const key_type& __x)
+      { return iterator(_Base::upper_bound(__x), this); }
+      
+      const_iterator 
+      upper_bound(const key_type& __x) const
+      { return const_iterator(_Base::upper_bound(__x), this); }
+      
+      std::pair<iterator,iterator>
+      equal_range(const key_type& __x)
+      {
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res =
+	_Base::equal_range(__x);
+	return std::make_pair(iterator(__res.first, this),
+			      iterator(__res.second, this));
+      }
+      
+      std::pair<const_iterator,const_iterator>
+      equal_range(const key_type& __x) const
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	_Base::equal_range(__x);
+	return std::make_pair(const_iterator(__res.first, this),
+			      const_iterator(__res.second, this));
+      }
+      
+      _Base&       
+      _M_base() { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+      
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator> 
+    inline bool
+    operator==(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator!=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator<(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	      const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator<=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator>=(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator>(const map<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	      const map<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline void
+    swap(map<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	 map<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { __lhs.swap(__rhs); }
+} // namespace __gnu_debug_def
+
+#endif 
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
new file mode 100644
index 00000000000..8c3bd317bbe
--- /dev/null
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -0,0 +1,314 @@
+// Debugging multimap implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_MULTIMAP_H
+#define _GLIBCXX_DEBUG_MULTIMAP_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+#include <utility>
+
+namespace __gnu_debug_def
+{
+  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
+	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
+    class multimap 
+    : public __gnu_norm::multimap<_Key, _Tp, _Compare, _Allocator>,
+    public __gnu_debug::_Safe_sequence<multimap<_Key,_Tp,_Compare,_Allocator> >
+    {
+      typedef __gnu_norm::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base;
+      
+    public:
+      // types:
+      typedef _Key   			   	     key_type;
+      typedef _Tp  			   	     mapped_type;
+      typedef std::pair<const _Key, _Tp>             value_type;
+      typedef _Compare                               key_compare;
+      typedef _Allocator                             allocator_type;
+      typedef typename _Allocator::reference         reference;
+      typedef typename _Allocator::const_reference   const_reference;
+      
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multimap> 
+                                                     iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+                                           multimap> const_iterator;
+
+      typedef typename _Base::size_type              size_type;
+      typedef typename _Base::difference_type        difference_type;
+      typedef typename _Allocator::pointer           pointer;
+      typedef typename _Allocator::const_pointer     const_pointer;
+      typedef std::reverse_iterator<iterator>        reverse_iterator;
+      typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
+      
+      using _Base::value_compare;
+      
+      // 23.3.1.1 construct/copy/destroy:
+      explicit multimap(const _Compare& __comp = _Compare(),
+			const _Allocator& __a = _Allocator())
+      : _Base(__comp, __a) { }
+
+      template<typename _InputIterator>
+      multimap(_InputIterator __first, _InputIterator __last,
+	       const _Compare& __comp = _Compare(), 
+	       const _Allocator& __a = _Allocator())
+      : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
+	      __comp, __a) { }
+
+      multimap(const multimap<_Key,_Tp,_Compare,_Allocator>& __x)
+      : _Base(__x), _Safe_base() { } 
+
+      multimap(const _Base& __x) : _Base(__x), _Safe_base() { }
+
+      ~multimap() { }
+
+      multimap<_Key,_Tp,_Compare,_Allocator>&
+      operator=(const multimap<_Key,_Tp,_Compare,_Allocator>& __x)
+      {
+	*static_cast<_Base*>(this) = __x;
+	this->_M_invalidate_all();
+	return *this;
+      }
+
+      using _Base::get_allocator;
+
+      // iterators:
+      iterator       
+      begin() 
+      { return iterator(_Base::begin(), this); }
+
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+
+      iterator       
+      end() 
+      { return iterator(_Base::end(), this); }
+
+      const_iterator 
+      end() const   
+      { return const_iterator(_Base::end(), this); }
+
+      reverse_iterator 
+      rbegin() 
+      { return reverse_iterator(end()); }
+
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+
+      const_reverse_iterator 
+      rend() const 
+      { return const_reverse_iterator(begin()); }
+
+      // capacity:
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+
+      // modifiers:
+      iterator 
+      insert(const value_type& __x)
+      { return iterator(_Base::insert(__x), this); }
+
+      iterator 
+      insert(iterator __position, const value_type& __x)
+      {
+	__glibcxx_check_insert(__position);
+	return iterator(_Base::insert(__position.base(), __x), this);
+      }
+
+      template<typename _InputIterator>
+        void 
+        insert(_InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::insert(__first, __last);
+	}
+
+      void 
+      erase(iterator __position)
+      {
+	__glibcxx_check_erase(__position);
+	__position._M_invalidate();
+	_Base::erase(__position.base());
+      }
+
+      size_type 
+      erase(const key_type& __x)
+      {
+	std::pair<iterator, iterator> __victims = this->equal_range(__x);
+	size_type __count = 0;
+	while (__victims.first != __victims.second)
+	{
+	  iterator __victim = __victims.first++;
+	  __victim._M_invalidate();
+	  _Base::erase(__victim.base());
+	  ++__count;
+	}
+	return __count;
+      }
+
+      void 
+      erase(iterator __first, iterator __last)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 151. can't currently clear() empty container
+	__glibcxx_check_erase_range(__first, __last);
+	while (__first != __last)
+	this->erase(__first++);
+      }
+
+      void 
+      swap(multimap<_Key,_Tp,_Compare,_Allocator>& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+
+      void 
+      clear()
+      { this->erase(begin(), end()); }
+
+      // observers:
+      using _Base::key_comp;
+      using _Base::value_comp;
+
+      // 23.3.1.3 multimap operations:
+      iterator 
+      find(const key_type& __x)
+      { return iterator(_Base::find(__x), this); }
+
+      const_iterator 
+      find(const key_type& __x) const
+      { return const_iterator(_Base::find(__x), this); }
+
+      using _Base::count;
+
+      iterator 
+      lower_bound(const key_type& __x)
+      { return iterator(_Base::lower_bound(__x), this); }
+
+      const_iterator 
+      lower_bound(const key_type& __x) const
+      { return const_iterator(_Base::lower_bound(__x), this); }
+
+      iterator 
+      upper_bound(const key_type& __x)
+      { return iterator(_Base::upper_bound(__x), this); }
+
+      const_iterator 
+      upper_bound(const key_type& __x) const
+      { return const_iterator(_Base::upper_bound(__x), this); }
+
+      std::pair<iterator,iterator>
+      equal_range(const key_type& __x)
+      {
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res =
+	_Base::equal_range(__x);
+	return std::make_pair(iterator(__res.first, this),
+			      iterator(__res.second, this));
+      }
+
+      std::pair<const_iterator,const_iterator>
+      equal_range(const key_type& __x) const
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	_Base::equal_range(__x);
+	return std::make_pair(const_iterator(__res.first, this),
+			      const_iterator(__res.second, this));
+      }
+
+      _Base&       
+      _M_base() { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator==(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator!=(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator<(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	      const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator<=(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator>=(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	       const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline bool
+    operator>(const multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	      const multimap<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+
+  template<typename _Key,typename _Tp,typename _Compare,typename _Allocator>
+    inline void
+    swap(multimap<_Key,_Tp,_Compare,_Allocator>& __lhs, 
+	 multimap<_Key,_Tp,_Compare,_Allocator>& __rhs)
+    { __lhs.swap(__rhs); }
+} // namespace __gnu_debug_def
+
+#endif 
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
new file mode 100644
index 00000000000..083c8fb69a2
--- /dev/null
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -0,0 +1,320 @@
+// Debugging multiset implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_MULTISET_H
+#define _GLIBCXX_DEBUG_MULTISET_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+#include <utility>
+
+namespace __gnu_debug_def
+{
+  template<typename _Key, typename _Compare = std::less<_Key>,
+	   typename _Allocator = std::allocator<_Key> >
+    class multiset 
+    : public __gnu_norm::multiset<_Key, _Compare, _Allocator>,
+      public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
+    {
+      typedef __gnu_norm::multiset<_Key, _Compare, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
+
+    public:
+      // types:
+      typedef _Key 	 			   key_type;
+      typedef _Key 	 			   value_type;
+      typedef _Compare   			   	   key_compare;
+      typedef _Compare   			   	   value_compare;
+      typedef _Allocator 			   	   allocator_type;
+      typedef typename _Allocator::reference         reference;
+      typedef typename _Allocator::const_reference   const_reference;
+
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset> 
+      iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+					  multiset> const_iterator;
+
+      typedef typename _Base::size_type              size_type;
+      typedef typename _Base::difference_type        difference_type;
+      typedef typename _Allocator::pointer           pointer;
+      typedef typename _Allocator::const_pointer     const_pointer;
+      typedef std::reverse_iterator<iterator>        reverse_iterator;
+      typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
+
+      // 23.3.3.1 construct/copy/destroy:
+      explicit multiset(const _Compare& __comp = _Compare(),
+			const _Allocator& __a = _Allocator())
+      : _Base(__comp, __a) { }
+
+      template<typename _InputIterator>
+        multiset(_InputIterator __first, _InputIterator __last,
+		 const _Compare& __comp = _Compare(),
+		 const _Allocator& __a = _Allocator())
+	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
+		__comp, __a) { }
+
+      multiset(const multiset<_Key,_Compare,_Allocator>& __x) 
+      : _Base(__x), _Safe_base() { }
+    
+      multiset(const _Base& __x) : _Base(__x), _Safe_base() { }
+
+      ~multiset() { }
+
+      multiset<_Key,_Compare,_Allocator>& 
+      operator=(const multiset<_Key,_Compare,_Allocator>& __x)
+      {
+	*static_cast<_Base*>(this) = __x;
+	this->_M_invalidate_all();
+	return *this;
+      }
+
+      using _Base::get_allocator;
+
+      // iterators:
+      iterator
+      begin()
+      { return iterator(_Base::begin(), this); }
+
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+
+      iterator 
+      end()
+      { return iterator(_Base::end(), this); }
+
+      const_iterator 
+      end() const   
+      { return const_iterator(_Base::end(), this); }
+
+      reverse_iterator 
+      rbegin() 
+      { return reverse_iterator(end()); }
+
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+
+      const_reverse_iterator 
+      rend() const 
+      { return const_reverse_iterator(begin()); }
+
+      // capacity:
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+
+      // modifiers:
+      iterator 
+      insert(const value_type& __x)
+      { return iterator(_Base::insert(__x), this); }
+
+      iterator 
+      insert(iterator __position, const value_type& __x)
+      {
+	__glibcxx_check_insert(__position);
+	return iterator(_Base::insert(__position.base(), __x), this);
+      }
+
+      template<typename _InputIterator>
+      void 
+      insert(_InputIterator __first, _InputIterator __last)
+      {
+	__glibcxx_check_valid_range(__first, __last);
+	_Base::insert(__first, __last);
+      }
+
+      void 
+      erase(iterator __position)
+      {
+	__glibcxx_check_erase(__position);
+	__position._M_invalidate();
+	_Base::erase(__position.base());
+      }
+
+      size_type
+      erase(const key_type& __x)
+      {
+	std::pair<iterator, iterator> __victims = this->equal_range(__x);
+	size_type __count = 0;
+	while (__victims.first != __victims.second)
+	{
+	  iterator __victim = __victims.first++;
+	  __victim._M_invalidate();
+	  _Base::erase(__victim.base());
+	  ++__count;
+	}
+	return __count;
+      }
+
+      void 
+      erase(iterator __first, iterator __last)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 151. can't currently clear() empty container
+	__glibcxx_check_erase_range(__first, __last);
+	while (__first != __last)
+	this->erase(__first++);
+      }
+
+      void 
+      swap(multiset<_Key,_Compare,_Allocator>& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+
+      void 
+      clear()
+      { this->erase(begin(), end()); }
+
+      // observers:
+      using _Base::key_comp;
+      using _Base::value_comp;
+
+      // multiset operations:
+      iterator 
+      find(const key_type& __x)
+      { return iterator(_Base::find(__x), this); }
+
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      const_iterator 
+      find(const key_type& __x) const
+      { return const_iterator(_Base::find(__x), this); }
+
+      using _Base::count;
+
+      iterator 
+      lower_bound(const key_type& __x)
+      { return iterator(_Base::lower_bound(__x), this); }
+
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      const_iterator 
+      lower_bound(const key_type& __x) const
+      { return const_iterator(_Base::lower_bound(__x), this); }
+
+      iterator 
+      upper_bound(const key_type& __x)
+      { return iterator(_Base::upper_bound(__x), this); }
+
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      const_iterator 
+      upper_bound(const key_type& __x) const
+      { return const_iterator(_Base::upper_bound(__x), this); }
+
+      std::pair<iterator,iterator>
+      equal_range(const key_type& __x)
+      {
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res =
+        _Base::equal_range(__x);
+	return std::make_pair(iterator(__res.first, this),
+			      iterator(__res.second, this));
+      }
+
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      std::pair<const_iterator,const_iterator>
+      equal_range(const key_type& __x) const
+      {
+	typedef typename _Base::const_iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res =
+        _Base::equal_range(__x);
+	return std::make_pair(const_iterator(__res.first, this),
+			      const_iterator(__res.second, this));
+      }
+
+      _Base& 
+      _M_base() { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+      
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator==(const multiset<_Key,_Compare,_Allocator>& __lhs,
+	       const multiset<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator!=(const multiset<_Key,_Compare,_Allocator>& __lhs,
+	       const multiset<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator<(const multiset<_Key,_Compare,_Allocator>& __lhs,
+	      const multiset<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator<=(const multiset<_Key,_Compare,_Allocator>& __lhs,
+	       const multiset<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator>=(const multiset<_Key,_Compare,_Allocator>& __lhs,
+	       const multiset<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator>(const multiset<_Key,_Compare,_Allocator>& __lhs,
+	      const multiset<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    void
+    swap(multiset<_Key,_Compare,_Allocator>& __x,
+	 multiset<_Key,_Compare,_Allocator>& __y)
+    { return __x.swap(__y); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/safe_base.h b/libstdc++-v3/include/debug/safe_base.h
new file mode 100644
index 00000000000..93b17618e35
--- /dev/null
+++ b/libstdc++-v3/include/debug/safe_base.h
@@ -0,0 +1,201 @@
+// Safe sequence/iterator base implementation  -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_SAFE_BASE_H
+#define _GLIBCXX_DEBUG_SAFE_BASE_H 1
+
+namespace __gnu_debug
+{
+  class _Safe_sequence_base;
+
+  /** \brief Basic functionality for a "safe" iterator.
+   *
+   *  The %_Safe_iterator_base base class implements the functionality
+   *  of a safe iterator that is not specific to a particular iterator
+   *  type. It contains a pointer back to the sequence it references
+   *  along with iterator version information and pointers to form a
+   *  doubly-linked list of iterators referenced by the container.
+   *
+   *  This class must not perform any operations that can throw an
+   *  exception, or the exception guarantees of derived iterators will
+   *  be broken.
+   */
+  class _Safe_iterator_base
+  {
+  public:
+    /** The sequence this iterator references; may be NULL to indicate
+	a singular iterator. */
+    _Safe_sequence_base* _M_sequence;
+
+    /** The version number of this iterator. The sentinel value 0 is
+     *  used to indicate an invalidated iterator (i.e., one that is
+     *  singular because of an operation on the container). This
+     *  version number must equal the version number in the sequence
+     *  referenced by _M_sequence for the iterator to be
+     *  non-singular. 
+     */
+    unsigned int         _M_version;
+
+    /** Pointer to the previous iterator in the sequence's list of
+	iterators. Only valid when _M_sequence != NULL. */
+    _Safe_iterator_base* _M_prior;
+
+    /** Pointer to the next iterator in the sequence's list of
+	iterators. Only valid when _M_sequence != NULL. */
+    _Safe_iterator_base* _M_next;
+
+  protected:
+    /** Initializes the iterator and makes it singular. */
+    _Safe_iterator_base() 
+    : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
+    { }
+
+    /** Initialize the iterator to reference the sequence pointed to
+     *  by @p__seq. @p __constant is true when we are initializing a
+     *  constant iterator, and false if it is a mutable iterator. Note
+     *  that @p __seq may be NULL, in which case the iterator will be
+     *  singular. Otherwise, the iterator will reference @p __seq and
+     *  be nonsingular. 
+     */
+    _Safe_iterator_base(const _Safe_sequence_base* __seq, bool __constant)
+    : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
+    { this->_M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); }
+
+    /** Initializes the iterator to reference the same sequence that
+	@p __x does. @p __constant is true if this is a constant
+	iterator, and false if it is mutable. */
+    _Safe_iterator_base(const _Safe_iterator_base& __x, bool __constant)
+    : _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
+    { this->_M_attach(__x._M_sequence, __constant); }
+
+    ~_Safe_iterator_base() { this->_M_detach(); }
+
+  public:
+    /** Attaches this iterator to the given sequence, detaching it
+     *	from whatever sequence it was attached to originally. If the
+     *	new sequence is the NULL pointer, the iterator is left
+     *	unattached.
+     */ 
+    void _M_attach(_Safe_sequence_base* __seq, bool __constant);
+
+    /** Detach the iterator for whatever sequence it is attached to,
+     *	if any. 
+    */
+    void _M_detach();
+
+    /** Determines if we are attached to the given sequence. */
+    bool _M_attached_to(const _Safe_sequence_base* __seq) const
+    { return _M_sequence == __seq; }
+
+    /** Is this iterator singular? */
+    bool _M_singular() const;
+
+    /** Can we compare this iterator to the given iterator @p __x?
+	Returns true if both iterators are nonsingular and reference
+	the same sequence. */
+    bool _M_can_compare(const _Safe_iterator_base& __x) const;
+  };
+
+  /**
+   * @brief Base class that supports tracking of iterators that
+   * reference a sequence.
+   *
+   * The %_Safe_sequence_base class provides basic support for
+   * tracking iterators into a sequence. Sequences that track
+   * iterators must derived from %_Safe_sequence_base publicly, so
+   * that safe iterators (which inherit _Safe_iterator_base) can
+   * attach to them. This class contains two linked lists of
+   * iterators, one for constant iterators and one for mutable
+   * iterators, and a version number that allows very fast
+   * invalidation of all iterators that reference the container.
+   *
+   * This class must ensure that no operation on it may throw an
+   * exception, otherwise "safe" sequences may fail to provide the
+   * exception-safety guarantees required by the C++ standard.
+   */
+  class _Safe_sequence_base
+  {
+  public:
+    /// The list of mutable iterators that reference this container
+    _Safe_iterator_base* _M_iterators;
+    
+    /// The list of constant iterators that reference this container
+    _Safe_iterator_base* _M_const_iterators;
+    
+    /// The container version number. This number may never be 0.
+    mutable unsigned int _M_version;
+    
+  protected:
+    // Initialize with a version number of 1 and no iterators
+    _Safe_sequence_base()
+    : _M_iterators(0), _M_const_iterators(0), _M_version(1)
+    { }
+    
+    /** Notify all iterators that reference this sequence that the
+	sequence is being destroyed. */
+    ~_Safe_sequence_base()
+    { this->_M_detach_all(); }
+    
+    /** Detach all iterators, leaving them singular. */
+    void 
+    _M_detach_all();
+    
+    /** Detach all singular iterators. 
+     *  @post for all iterators i attached to this sequence, 
+     *   i->_M_version == _M_version.
+     */
+    void
+    _M_detach_singular();
+    
+    /** Revalidates all attached singular iterators.  This method may
+     *  be used to validate iterators that were invalidated before
+     *  (but for some reasion, such as an exception, need to become
+     *  valid again).
+     */
+    void
+    _M_revalidate_singular();
+    
+    /** Swap this sequence with the given sequence. This operation
+     *  also swaps ownership of the iterators, so that when the
+     *  operation is complete all iterators that originally referenced
+     *  one container now reference the other container.
+     */
+    void 
+    _M_swap(_Safe_sequence_base& __x);
+      
+  public:
+    /** Invalidates all iterators. */
+    void 
+    _M_invalidate_all() const
+    { if (++_M_version == 0) _M_version = 1; }
+  };
+} // namespace __gnu_debug
+
+#endif 
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
new file mode 100644
index 00000000000..5d7ee27fb3c
--- /dev/null
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -0,0 +1,607 @@
+// Safe iterator implementation  -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
+#define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
+
+#include <bits/stl_pair.h>
+#include <debug/debug.h>
+#include <debug/formatter.h>
+#include <debug/safe_base.h>
+
+namespace __gnu_debug
+{
+  /** Iterators that derive from _Safe_iterator_base but that aren't
+   *  _Safe_iterators can be determined singular or non-singular via
+   *  _Safe_iterator_base. 
+   */
+  inline bool __check_singular_aux(const _Safe_iterator_base* __x)
+  { return __x->_M_singular(); }
+  
+  /** \brief Safe iterator wrapper.
+   *  
+   *  The class template %_Safe_iterator is a wrapper around an
+   *  iterator that tracks the iterator's movement among sequences and
+   *  checks that operations performed on the "safe" iterator are
+   *  legal. In additional to the basic iterator operations (which are
+   *  validated, and then passed to the underlying iterator),
+   *  %_Safe_iterator has member functions for iterator invalidation,
+   *  attaching/detaching the iterator from sequences, and querying
+   *  the iterator's state.
+   */
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_iterator : public _Safe_iterator_base
+    {
+      typedef _Safe_iterator _Self;
+
+      /** The precision to which we can calculate the distance between
+       *  two iterators.
+       */
+      enum _Distance_precision
+	{
+	  __dp_equality, //< Can compare iterator equality, only
+	  __dp_sign,     //< Can determine equality and ordering
+	  __dp_exact     //< Can determine distance precisely
+	};
+      
+      /// The underlying iterator
+      _Iterator _M_current;
+
+      /// Determine if this is a constant iterator.
+      bool 
+      _M_constant() const
+      {
+	typedef typename _Sequence::const_iterator const_iterator;
+	return __is_same<const_iterator, _Safe_iterator>::value;
+      }
+
+      typedef iterator_traits<_Iterator> _Traits;
+
+    public:
+      typedef typename _Traits::iterator_category iterator_category;
+      typedef typename _Traits::value_type        value_type;
+      typedef typename _Traits::difference_type   difference_type;
+      typedef typename _Traits::reference         reference;
+      typedef typename _Traits::pointer           pointer;
+
+      /// @post the iterator is singular and unattached
+      _Safe_iterator() : _M_current() { }
+
+      /**
+       * @brief Safe iterator construction from an unsafe iterator and
+       * its sequence.
+       *
+       * @pre @p seq is not NULL
+       * @post this is not singular
+       */
+      _Safe_iterator(const _Iterator& __i, const _Sequence* __seq)
+      : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i)
+      { 
+	_GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
+			      _M_message(__msg_init_singular)
+			      ._M_iterator(*this, "this"));
+      }
+
+      /**
+       * @brief Copy construction.
+       * @pre @p x is not singular
+       */
+      _Safe_iterator(const _Safe_iterator& __x)
+      : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current)
+      { 
+	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
+			      _M_message(__msg_init_copy_singular)
+			      ._M_iterator(*this, "this")
+			      ._M_iterator(__x, "other"));
+      }
+
+      /** 
+       *  @brief Converting constructor from a mutable iterator to a
+       *  constant iterator.
+       *
+       *  @pre @p x is not singular
+      */
+      template<typename _MutableIterator>
+        _Safe_iterator(const _Safe_iterator<_MutableIterator, _Sequence>& __x)
+	: _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
+        { 
+	  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
+				_M_message(__msg_init_const_singular)
+				._M_iterator(*this, "this")
+				._M_iterator(__x, "other"));
+	}
+
+      /**
+       * @brief Copy assignment.
+       * @pre @p x is not singular
+       */
+      _Safe_iterator& 
+      operator=(const _Safe_iterator& __x)
+      {
+	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular(),
+			      _M_message(__msg_copy_singular)
+			      ._M_iterator(*this, "this")
+			      ._M_iterator(__x, "other"));
+	_M_current = __x._M_current;
+	this->_M_attach(static_cast<_Sequence*>(__x._M_sequence));
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator dereference.
+       *  @pre iterator is dereferenceable
+       */
+      reference 
+      operator*() const 
+      {
+
+	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
+			      _M_message(__msg_bad_deref)
+			      ._M_iterator(*this, "this"));
+	return *_M_current;
+      }
+
+      /**
+       *  @brief Iterator dereference.
+       *  @pre iterator is dereferenceable
+       *  @todo Make this correct w.r.t. iterators that return proxies
+       *  @todo Use addressof() instead of & operator
+       */
+      pointer 
+      operator->() const
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
+			      _M_message(__msg_bad_deref)
+			      ._M_iterator(*this, "this"));
+	return &*_M_current;
+      }
+
+      // ------ Input iterator requirements ------
+      /**
+       *  @brief Iterator preincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_iterator& 
+      operator++()
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
+			      _M_message(__msg_bad_inc)
+			      ._M_iterator(*this, "this"));
+	++_M_current;
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_iterator 
+      operator++(int)
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
+			      _M_message(__msg_bad_inc)
+			      ._M_iterator(*this, "this"));
+	_Safe_iterator __tmp(*this);
+	++_M_current;
+	return __tmp;
+      }
+
+      // ------ Bidirectional iterator requirements ------
+      /**
+       *  @brief Iterator predecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_iterator& 
+      operator--()
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
+			      _M_message(__msg_bad_dec)
+			      ._M_iterator(*this, "this"));
+	--_M_current;
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postdecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_iterator 
+      operator--(int)
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
+			      _M_message(__msg_bad_dec)
+			      ._M_iterator(*this, "this"));
+	_Safe_iterator __tmp(*this);
+	--_M_current;
+	return __tmp;
+      }
+
+      // ------ Random access iterator requirements ------
+      reference 
+      operator[](const difference_type& __n) const
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n) 
+			      && this->_M_can_advance(__n+1),
+			      _M_message(__msg_iter_subscript_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+
+	return _M_current[__n];
+      }
+
+      _Safe_iterator& 
+      operator+=(const difference_type& __n)
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
+			      _M_message(__msg_advance_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	_M_current += __n;
+	return *this;
+      }
+
+      _Safe_iterator 
+      operator+(const difference_type& __n) const
+      {
+	_Safe_iterator __tmp(*this);
+	__tmp += __n;
+	return __tmp;
+      }
+
+      _Safe_iterator& 
+      operator-=(const difference_type& __n)
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
+			      _M_message(__msg_retreat_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	_M_current += -__n;
+	return *this;
+      }
+
+      _Safe_iterator 
+      operator-(const difference_type& __n) const
+      {
+	_Safe_iterator __tmp(*this);
+	__tmp -= __n;
+	return __tmp;
+      }
+
+      // ------ Utilities ------
+      /**
+       * @brief Return the underlying iterator
+       */      
+      _Iterator 
+      base() const { return _M_current; }
+
+      /**
+       * @brief Conversion to underlying non-debug iterator to allow
+       * better interaction with non-debug containers.
+       */
+      operator _Iterator() const { return _M_current; }
+
+      /** Attach iterator to the given sequence. */
+      void 
+      _M_attach(const _Sequence* __seq)
+      { 
+	_Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq),
+				       _M_constant()); 
+      }
+
+      /** Invalidate the iterator, making it singular. */
+      void 
+      _M_invalidate();
+
+      /// Is the iterator dereferenceable?
+      bool 
+      _M_dereferenceable() const
+      { return !this->_M_singular() && !_M_is_end(); }
+
+      /// Is the iterator incrementable?
+      bool 
+      _M_incrementable() const { return this->_M_dereferenceable(); }
+
+      // Is the iterator decrementable?
+      bool 
+      _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
+
+      // Can we advance the iterator @p __n steps (@p __n may be negative)
+      bool 
+      _M_can_advance(const difference_type& __n) const;
+
+      // Is the iterator range [*this, __rhs) valid?
+      template<typename _Other>
+        bool 
+        _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const;
+
+      // The sequence this iterator references.
+      const _Sequence* 
+      _M_get_sequence() const
+      { return static_cast<const _Sequence*>(_M_sequence); }
+
+    /** Determine the distance between two iterators with some known
+     *	precision. 
+    */
+    template<typename _Iterator1, typename _Iterator2>
+      static pair<difference_type, _Distance_precision>
+      _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs)
+      {
+        typedef typename iterator_traits<_Iterator1>::iterator_category
+	  _Category;
+        return _M_get_distance(__lhs, __rhs, _Category());
+      }
+
+    template<typename _Iterator1, typename _Iterator2>
+      static pair<difference_type, _Distance_precision>
+      _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
+		      std::random_access_iterator_tag)
+      {
+        return std::make_pair(__rhs.base() - __lhs.base(), __dp_exact);
+      }
+
+    template<typename _Iterator1, typename _Iterator2>
+      static pair<difference_type, _Distance_precision>
+      _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
+    		    std::forward_iterator_tag)
+      {
+        return std::make_pair(__lhs.base() == __rhs.base()? 0 : 1, 
+			      __dp_equality);
+      }
+
+      /// Is this iterator equal to the sequence's begin() iterator?
+      bool _M_is_begin() const
+      {	return *this == static_cast<const _Sequence*>(_M_sequence)->begin(); }
+
+      /// Is this iterator equal to the sequence's end() iterator?
+      bool _M_is_end() const
+      {	return *this == static_cast<const _Sequence*>(_M_sequence)->end(); }
+    };
+
+  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+    inline bool
+    operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
+  	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_compare_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_compare_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() == __rhs.base(); 
+    }
+
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_compare_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_compare_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() == __rhs.base(); 
+    }
+
+  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+    inline bool
+    operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
+  	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_compare_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_compare_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() != __rhs.base(); 
+    }
+
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_compare_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_compare_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() != __rhs.base(); 
+    }
+
+  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+    inline bool
+    operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
+	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() < __rhs.base(); 
+    }
+
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+	      const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() < __rhs.base(); 
+    }
+
+  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+    inline bool
+    operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
+  	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() <= __rhs.base(); 
+    }
+
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() <= __rhs.base(); 
+    }
+
+  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+    inline bool
+    operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
+	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() > __rhs.base(); 
+    }
+
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+	      const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() > __rhs.base(); 
+    }
+
+  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+    inline bool
+    operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
+  	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() >= __rhs.base(); 
+    }
+
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_iter_order_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_order_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() >= __rhs.base(); 
+    }
+
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // According to the resolution of DR179 not only the various comparison
+  // operators but also operator- must accept mixed iterator/const_iterator
+  // parameters.
+  template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+    inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
+    operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
+	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    { 
+      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+			    _M_message(__msg_distance_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_distance_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() - __rhs.base(); 
+    }
+
+  template<typename _Iterator, typename _Sequence>
+    inline _Safe_iterator<_Iterator, _Sequence>
+    operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
+	      const _Safe_iterator<_Iterator, _Sequence>& __i)
+    { return __i + __n; }
+} // namespace __gnu_debug
+
+#ifndef _GLIBCXX_EXPORT_TEMPLATE
+#  include <debug/safe_iterator.tcc>
+#endif 
+
+#endif
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
new file mode 100644
index 00000000000..0af21b9eb2d
--- /dev/null
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -0,0 +1,140 @@
+// Debugging iterator implementation (out of line) -*- C++ -*-
+
+// 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.
+
+/** @file safe_iterator.tcc
+ *  This is an internal header file, included by other library headers.
+ *  You should not attempt to use it directly.
+ */
+
+#ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC
+#define _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC 1
+
+namespace __gnu_debug
+{
+  template<typename _Iterator, typename _Sequence>
+    bool 
+    _Safe_iterator<_Iterator, _Sequence>::
+    _M_can_advance(const difference_type& __n) const
+    {
+      typedef typename _Sequence::const_iterator const_iterator;
+      
+      if (this->_M_singular())
+	return false;
+      if (__n == 0)
+	return true;
+      if (__n < 0) 
+	{
+	  const_iterator __begin = 
+	    static_cast<const _Sequence*>(_M_sequence)->begin();
+	  pair<difference_type, _Distance_precision> __dist =
+	    this->_M_get_distance(__begin, *this);
+	  bool __ok =  (__dist.second == __dp_exact && __dist.first >= -__n
+			|| __dist.second != __dp_exact && __dist.first > 0);
+	  return __ok;
+	}
+      else
+	{
+	  const_iterator __end = 
+	    static_cast<const _Sequence*>(_M_sequence)->end();
+	  pair<difference_type, _Distance_precision> __dist = 
+	    this->_M_get_distance(*this, __end);
+	  bool __ok = (__dist.second == __dp_exact && __dist.first >= __n
+		       || __dist.second != __dp_exact && __dist.first > 0);
+	  return __ok;
+	}
+    }
+  
+  template<typename _Iterator, typename _Sequence>
+    template<typename _Other>
+      bool 
+      _Safe_iterator<_Iterator, _Sequence>::
+      _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const
+      {
+	if (!_M_can_compare(__rhs))
+	  return false;
+	
+	/* Determine if we can order the iterators without the help of
+	   the container */
+	pair<difference_type, _Distance_precision> __dist = 
+	  this->_M_get_distance(*this, __rhs);
+	switch (__dist.second) {
+	case __dp_equality:
+	  if (__dist.first == 0)
+	    return true;
+	  break;
+	  
+	case __dp_sign:
+	case __dp_exact:
+	  return __dist.first >= 0;
+	}
+	
+	/* We can only test for equality, but check if one of the
+	   iterators is at an extreme. */
+	if (_M_is_begin() || __rhs._M_is_end())
+	  return true;
+	else if (_M_is_end() || __rhs._M_is_begin())
+	  return false;
+	
+	// Assume that this is a valid range; we can't check anything else
+	return true;
+      }
+
+  template<typename _Iterator, typename _Sequence>
+    void
+    _Safe_iterator<_Iterator, _Sequence>::
+    _M_invalidate()
+    {
+      typedef typename _Sequence::iterator iterator;
+      typedef typename _Sequence::const_iterator const_iterator;
+      
+      if (!this->_M_singular())
+	{
+	  for (_Safe_iterator_base* iter = _M_sequence->_M_iterators; iter; )
+	    {
+	      iterator* __victim = static_cast<iterator*>(iter);
+	      iter = iter->_M_next;
+	      if (this->base() == __victim->base())
+		__victim->_M_version = 0;
+	    }
+	  for (_Safe_iterator_base* iter = _M_sequence->_M_const_iterators;
+	       iter; /* increment in loop */)
+	    {
+	      const_iterator* __victim = static_cast<const_iterator*>(iter);
+	      iter = iter->_M_next;
+	      if (this->base() == __victim->base())
+		__victim->_M_version = 0;
+	    }
+	  _M_version = 0;
+	}
+    }
+} // namespace __gnu_debug
+
+#endif 
+
diff --git a/libstdc++-v3/include/debug/safe_sequence.h b/libstdc++-v3/include/debug/safe_sequence.h
new file mode 100644
index 00000000000..cb2d8ae3872
--- /dev/null
+++ b/libstdc++-v3/include/debug/safe_sequence.h
@@ -0,0 +1,179 @@
+// Safe sequence implementation  -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_SAFE_SEQUENCE_H
+#define _GLIBCXX_DEBUG_SAFE_SEQUENCE_H 1
+
+#include <debug/debug.h>
+#include <debug/safe_base.h>
+
+namespace __gnu_debug
+{
+  template<typename _Iterator, typename _Sequence> 
+    class _Safe_iterator;
+
+  /** A simple function object that returns true if the passed-in
+   *  value is not equal to the stored value. It saves typing over
+   *  using both bind1st and not_equal. 
+   */
+  template<typename _Type>
+    class _Not_equal_to
+    {
+      _Type __value;
+      
+    public:
+      explicit _Not_equal_to(const _Type& __v) : __value(__v) { }
+      
+      bool 
+      operator()(const _Type& __x) const 
+      { return __value != __x; }
+    };
+  
+  /** A function object that returns true when the given random access
+      iterator is at least @c n steps away from the given iterator. */
+  template<typename _Iterator>
+    class _After_nth_from
+    {
+      typedef typename std::iterator_traits<_Iterator>::difference_type
+      difference_type;
+      
+      _Iterator _M_base;
+      difference_type _M_n;
+      
+    public:
+      _After_nth_from(const difference_type& __n, const _Iterator& __base)
+      : _M_base(__base), _M_n(__n) { }
+      
+      bool 
+      operator()(const _Iterator& __x) const
+      { return __x - _M_base >= _M_n; }
+    };
+  
+  /**
+   * @brief Base class for constructing a "safe" sequence type that
+   * tracks iterators that reference it.
+   *
+   * The class template %_Safe_sequence simplifies the construction of
+   * "safe" sequences that track the iterators that reference the
+   * sequence, so that the iterators are notified of changes in the
+   * sequence that may affect their operation, e.g., if the container
+   * invalidates its iterators or is destructed. This class template
+   * may only be used by deriving from it and passing the name of the
+   * derived class as its template parameter via the curiously
+   * recurring template pattern. The derived class must have @c
+   * iterator and @const_iterator types that are instantiations of
+   * class template _Safe_iterator for this sequence. Iterators will
+   * then be tracked automatically.
+   */
+  template<typename _Sequence>
+    class _Safe_sequence : public _Safe_sequence_base
+    {
+    public:
+      /** Invalidates all iterators @c x that reference this sequence,
+	  are not singular, and for which @c pred(x) returns @c
+	  true. The user of this routine should be careful not to make
+	  copies of the iterators passed to @p pred, as the copies may
+	  interfere with the invalidation. */
+      template<typename _Predicate> 
+        void 
+        _M_invalidate_if(_Predicate __pred);
+
+      /** Transfers all iterators that reference this memory location
+	  to this sequence from whatever sequence they are attached
+	  to. */
+      template<typename _Iterator>
+        void
+        _M_transfer_iter(const _Safe_iterator<_Iterator, _Sequence>& __x);
+    };
+
+  template<typename _Sequence>
+    template<typename _Predicate> 
+      void 
+      _Safe_sequence<_Sequence>::
+      _M_invalidate_if(_Predicate __pred)
+      {
+        typedef typename _Sequence::iterator iterator;
+        typedef typename _Sequence::const_iterator const_iterator;
+        
+        for (_Safe_iterator_base* __iter = _M_iterators; __iter; )
+        {
+          iterator* __victim = static_cast<iterator*>(__iter);
+          __iter = __iter->_M_next;
+          if (!__victim->_M_singular()) 
+          {
+	    if (__pred(__victim->base()))
+	      __victim->_M_invalidate();
+          }
+        }
+
+        for (_Safe_iterator_base* __iter = _M_const_iterators; __iter; )
+        {
+          const_iterator* __victim = static_cast<const_iterator*>(__iter);
+          __iter = __iter->_M_next;
+          if (!__victim->_M_singular()) 
+          {
+	    if (__pred(__victim->base()))
+	      __victim->_M_invalidate();
+          }
+        }    
+      }
+
+  template<typename _Sequence>
+    template<typename _Iterator>
+      void
+      _Safe_sequence<_Sequence>::
+      _M_transfer_iter(const _Safe_iterator<_Iterator, _Sequence>& __x)
+      {
+	_Safe_sequence_base* __from = __x._M_sequence;
+	if (!__from)
+	  return;
+
+        typedef typename _Sequence::iterator iterator;
+        typedef typename _Sequence::const_iterator const_iterator;
+        
+        for (_Safe_iterator_base* __iter = __from->_M_iterators; __iter; )
+        {
+          iterator* __victim = static_cast<iterator*>(__iter);
+          __iter = __iter->_M_next;
+          if (!__victim->_M_singular() && __victim->base() == __x.base())
+	    __victim->_M_attach(static_cast<_Sequence*>(this));
+        }
+
+        for (_Safe_iterator_base* __iter = __from->_M_const_iterators; __iter;)
+        {
+          const_iterator* __victim = static_cast<const_iterator*>(__iter);
+          __iter = __iter->_M_next;
+          if (!__victim->_M_singular() && __victim->base() == __x.base())
+	    __victim->_M_attach(static_cast<_Sequence*>(this));
+        }
+      }
+} // namespace __gnu_debug
+
+#endif 
diff --git a/libstdc++-v3/include/debug/set b/libstdc++-v3/include/debug/set
new file mode 100644
index 00000000000..a1a69efb4f4
--- /dev/null
+++ b/libstdc++-v3/include/debug/set
@@ -0,0 +1,38 @@
+// Debugging set/multiset implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_SET
+#define _GLIBCXX_DEBUG_SET 1
+
+#include <set>
+#include <debug/set.h>
+#include <debug/multiset.h>
+
+#endif
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
new file mode 100644
index 00000000000..861077d7557
--- /dev/null
+++ b/libstdc++-v3/include/debug/set.h
@@ -0,0 +1,325 @@
+// Debugging set implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_SET_H
+#define _GLIBCXX_DEBUG_SET_H 1
+
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+#include <utility>
+
+namespace __gnu_debug_def
+{
+  template<typename _Key, typename _Compare = std::less<_Key>,
+	   typename _Allocator = std::allocator<_Key> >
+    class set
+    : public __gnu_norm::set<_Key,_Compare,_Allocator>,
+      public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
+    {
+      typedef __gnu_norm::set<_Key,_Compare,_Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<set> _Safe_base;
+      
+    public:
+      // types:
+      typedef _Key 	 			    key_type;
+      typedef _Key 	 			    value_type;
+      typedef _Compare   			    key_compare;
+      typedef _Compare   			    value_compare;
+      typedef _Allocator 			    allocator_type;
+      typedef typename _Allocator::reference        reference;
+      typedef typename _Allocator::const_reference  const_reference;
+      
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set> 
+                                                    iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
+                                                    const_iterator;
+
+      typedef typename _Base::size_type             size_type;
+      typedef typename _Base::difference_type       difference_type;
+      typedef typename _Allocator::pointer          pointer;
+      typedef typename _Allocator::const_pointer    const_pointer;
+      typedef std::reverse_iterator<iterator>       reverse_iterator;
+      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+      
+      // 23.3.3.1 construct/copy/destroy:
+      explicit set(const _Compare& __comp = _Compare(),
+		   const _Allocator& __a = _Allocator())
+      : _Base(__comp, __a) { }
+      
+      template<typename _InputIterator>
+        set(_InputIterator __first, _InputIterator __last,
+	    const _Compare& __comp = _Compare(),
+	    const _Allocator& __a = _Allocator())
+	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
+		__comp, __a) { }
+
+      set(const set<_Key,_Compare,_Allocator>& __x) 
+      : _Base(__x), _Safe_base() { }
+    
+      set(const _Base& __x) : _Base(__x), _Safe_base() { }
+      
+      ~set() { }
+      
+      set<_Key,_Compare,_Allocator>& 
+      operator=(const set<_Key,_Compare,_Allocator>& __x)
+      {
+	*static_cast<_Base*>(this) = __x;
+	this->_M_invalidate_all();
+	return *this;
+      }
+      
+      using _Base::get_allocator;
+      
+      // iterators:
+      iterator       
+      begin() 
+      { return iterator(_Base::begin(), this); }
+      
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+      
+      iterator       
+      end()
+      { return iterator(_Base::end(), this); }
+      
+      const_iterator 
+      end() const   
+      { return const_iterator(_Base::end(), this); }
+      
+      reverse_iterator 
+      rbegin()
+      { return reverse_iterator(end()); }
+      
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+      
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+      
+      const_reverse_iterator 
+      rend() const 
+      { return const_reverse_iterator(begin()); }
+      
+      // capacity:
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+      
+      // modifiers:
+      std::pair<iterator, bool> 
+      insert(const value_type& __x)
+      {
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
+	return std::pair<iterator, bool>(iterator(__res.first, this),
+					 __res.second);
+      }
+      
+      iterator 
+      insert(iterator __position, const value_type& __x)
+      {
+	__glibcxx_check_insert(__position);
+	return iterator(_Base::insert(__position.base(), __x), this);
+      }
+      
+      template <typename _InputIterator>
+        void 
+        insert(_InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::insert(__first, __last);
+	}
+      
+      void 
+      erase(iterator __position)
+      {
+	__glibcxx_check_erase(__position);
+	__position._M_invalidate();
+	_Base::erase(__position.base());
+      }
+      
+      size_type 
+      erase(const key_type& __x)
+      {
+	iterator __victim = find(__x);
+	if (__victim == end())
+          return 0;
+	else
+        {
+	  __victim._M_invalidate();
+	  _Base::erase(__victim.base());
+	  return 1;
+        }
+      }
+      
+      void 
+      erase(iterator __first, iterator __last)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 151. can't currently clear() empty container
+	__glibcxx_check_erase_range(__first, __last);
+	
+	while (__first != __last)
+        this->erase(__first++);
+      }
+      
+      void 
+      swap(set<_Key,_Compare,_Allocator>& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+      
+      void 
+      clear()
+      { this->erase(begin(), end()); }
+      
+      // observers:
+      using _Base::key_comp;
+      using _Base::value_comp;
+      
+      // set operations:
+      iterator 
+      find(const key_type& __x)
+      { return iterator(_Base::find(__x), this); }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      const_iterator 
+      find(const key_type& __x) const
+      { return const_iterator(_Base::find(__x), this); }
+      
+      using _Base::count;
+      
+      iterator 
+      lower_bound(const key_type& __x)
+      { return iterator(_Base::lower_bound(__x), this); }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      const_iterator 
+      lower_bound(const key_type& __x) const
+      { return const_iterator(_Base::lower_bound(__x), this); }
+      
+      iterator 
+      upper_bound(const key_type& __x)
+      { return iterator(_Base::upper_bound(__x), this); }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      const_iterator 
+      upper_bound(const key_type& __x) const
+      { return const_iterator(_Base::upper_bound(__x), this); }
+      
+      std::pair<iterator,iterator>
+      equal_range(const key_type& __x)
+      {
+	typedef typename _Base::iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res =
+        _Base::equal_range(__x);
+	return std::make_pair(iterator(__res.first, this),
+			      iterator(__res.second, this));
+      }
+      
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 214. set::find() missing const overload
+      std::pair<const_iterator,const_iterator>
+      equal_range(const key_type& __x) const
+      {
+	typedef typename _Base::const_iterator _Base_iterator;
+	std::pair<_Base_iterator, _Base_iterator> __res =
+        _Base::equal_range(__x);
+	return std::make_pair(const_iterator(__res.first, this),
+			      const_iterator(__res.second, this));
+      }
+      
+      _Base&       
+      _M_base() { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+      
+    private:
+      void 
+      _M_invalidate_all()
+      {
+	typedef typename _Base::const_iterator _Base_const_iterator;
+	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
+	this->_M_invalidate_if(_Not_equal(_M_base().end()));
+      }
+    };
+  
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator==(const set<_Key,_Compare,_Allocator>& __lhs,
+	       const set<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator!=(const set<_Key,_Compare,_Allocator>& __lhs,
+	       const set<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator<(const set<_Key,_Compare,_Allocator>& __lhs,
+	      const set<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator<=(const set<_Key,_Compare,_Allocator>& __lhs,
+	       const set<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator>=(const set<_Key,_Compare,_Allocator>& __lhs,
+	       const set<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    inline bool 
+    operator>(const set<_Key,_Compare,_Allocator>& __lhs,
+	      const set<_Key,_Compare,_Allocator>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+
+  template<typename _Key, typename _Compare, typename _Allocator>
+    void
+    swap(set<_Key,_Compare,_Allocator>& __x, 
+	 set<_Key,_Compare,_Allocator>& __y)
+    { return __x.swap(__y); }
+} // namespace __gnu_debug_def
+
+#endif
diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string
new file mode 100644
index 00000000000..5be5da6c129
--- /dev/null
+++ b/libstdc++-v3/include/debug/string
@@ -0,0 +1,1001 @@
+// Debugging string implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_STRING
+#define _GLIBCXX_DEBUG_STRING 1
+
+#include <string>
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug
+{
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    class basic_string 
+    : public std::basic_string<_CharT, _Traits, _Allocator>,
+      public __gnu_debug::_Safe_sequence<basic_string<_CharT, _Traits,
+						      _Allocator> >
+    {
+      typedef std::basic_string<_CharT, _Traits, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<basic_string>     _Safe_base;
+
+  public:
+    // types:
+    typedef _Traits                     	       traits_type;
+    typedef typename _Traits::char_type 	       value_type;
+    typedef _Allocator                  	       allocator_type;
+    typedef typename _Allocator::size_type             size_type;
+    typedef typename _Allocator::difference_type       difference_type;
+    typedef typename _Allocator::reference             reference;
+    typedef typename _Allocator::const_reference       const_reference;
+    typedef typename _Allocator::pointer               pointer;
+    typedef typename _Allocator::const_pointer         const_pointer;
+
+    typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, basic_string>
+                                                       iterator;
+    typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, 
+                                         basic_string> const_iterator;
+
+    typedef std::reverse_iterator<iterator>            reverse_iterator;
+    typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
+
+    using _Base::npos;
+
+    // 21.3.1 construct/copy/destroy:
+    explicit basic_string(const _Allocator& __a = _Allocator())
+    : _Base(__a)
+    { }
+
+    // Provides conversion from a release-mode string to a debug-mode string
+    basic_string(const _Base& __base) : _Base(__base), _Safe_base() { }
+
+    // _GLIBCXX_RESOLVE_LIB_DEFECTS
+    // 42. string ctors specify wrong default allocator 
+    basic_string(const basic_string& __str)
+    : _Base(__str, 0, _Base::npos, __str.get_allocator()), _Safe_base()
+    { }
+
+    // _GLIBCXX_RESOLVE_LIB_DEFECTS
+    // 42. string ctors specify wrong default allocator 
+    basic_string(const basic_string& __str, size_type __pos,
+		   size_type __n = _Base::npos,
+		   const _Allocator& __a = _Allocator())
+    : _Base(__str, __pos, __n, __a)
+    { }
+
+    basic_string(const _CharT* __s, size_type __n,
+		   const _Allocator& __a = _Allocator())
+    : _Base(__gnu_debug::__check_string(__s, __n), __n, __a)
+    { }
+
+    basic_string(const _CharT* __s, const _Allocator& __a = _Allocator())
+    : _Base(__gnu_debug::__check_string(__s), __a)
+    { this->assign(__s); }
+
+    basic_string(size_type __n, _CharT __c,
+		   const _Allocator& __a = _Allocator())
+    : _Base(__n, __c, __a)
+    { }
+
+    template<typename _InputIterator>
+      basic_string(_InputIterator __begin, _InputIterator __end,
+		     const _Allocator& __a = _Allocator())
+      : _Base(__gnu_debug::__check_valid_range(__begin, __end), __end, __a)
+      { }
+
+    ~basic_string() { }
+
+    basic_string& 
+    operator=(const basic_string& __str)
+    {
+      *static_cast<_Base*>(this) = __str;
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    operator=(const _CharT* __s)
+    {
+      __glibcxx_check_string(__s);
+      *static_cast<_Base*>(this) = __s;
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    operator=(_CharT __c)
+    {
+      *static_cast<_Base*>(this) = __c;
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    // 21.3.2 iterators:
+    iterator 
+    begin() 
+    { return iterator(_Base::begin(), this); }
+
+    const_iterator 
+    begin() const 
+    { return const_iterator(_Base::begin(), this); }
+
+    iterator 
+    end() 
+    { return iterator(_Base::end(), this); }
+
+    const_iterator 
+    end() const
+    { return const_iterator(_Base::end(), this); }
+
+    reverse_iterator 
+    rbegin() 
+    { return reverse_iterator(end()); }
+
+    const_reverse_iterator 
+    rbegin() const
+    { return const_reverse_iterator(end()); }
+
+    reverse_iterator
+    rend()
+    { return reverse_iterator(begin()); }
+
+    const_reverse_iterator 
+    rend() const 
+    { return const_reverse_iterator(begin()); }
+
+    // 21.3.3 capacity:
+    using _Base::size;
+    using _Base::length;
+    using _Base::max_size;
+
+    void 
+    resize(size_type __n, _CharT __c)
+    {
+      _Base::resize(__n, __c);
+      this->_M_invalidate_all();
+    }
+
+    void 
+    resize(size_type __n)
+    { this->resize(__n, _CharT()); }
+
+    using _Base::capacity;
+    using _Base::reserve;
+
+    void 
+    clear()
+    {
+      _Base::clear();
+      this->_M_invalidate_all();
+    }
+
+    using _Base::empty;
+
+    // 21.3.4 element access:
+    const_reference 
+    operator[](size_type __pos) const
+    {
+      _GLIBCXX_DEBUG_VERIFY(__pos <= this->size(),
+			    _M_message(::__gnu_debug::__msg_subscript_oob)
+			    ._M_sequence(*this, "this")
+			    ._M_integer(__pos, "__pos")
+			    ._M_integer(this->size(), "size"));
+      return _M_base()[__pos];
+    }
+
+    reference 
+    operator[](size_type __pos)
+    {
+      __glibcxx_check_subscript(__pos);
+      return _M_base()[__pos];
+    }
+
+    using _Base::at;
+
+    // 21.3.5 modifiers:
+    basic_string& 
+    operator+=(const basic_string& __str)
+    {
+      _M_base() += __str;
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    operator+=(const _CharT* __s)
+    {
+      __glibcxx_check_string(__s);
+      _M_base() += __s;
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    operator+=(_CharT __c)
+    {
+      _M_base() += __c;
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    append(const basic_string& __str)
+    {
+      _Base::append(__str);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    append(const basic_string& __str, size_type __pos, size_type __n)
+    {
+      _Base::append(__str, __pos, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    append(const _CharT* __s, size_type __n)
+    {
+      __glibcxx_check_string_len(__s, __n);
+      _Base::append(__s, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    append(const _CharT* __s)
+    {
+      __glibcxx_check_string(__s);
+      _Base::append(__s);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    append(size_type __n, _CharT __c)
+    {
+      _Base::append(__n, __c);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    template<typename _InputIterator>
+      basic_string& 
+      append(_InputIterator __first, _InputIterator __last)
+      {
+	__glibcxx_check_valid_range(__first, __last);
+	_Base::append(__first, __last);
+	this->_M_invalidate_all();
+	return *this;
+      }
+
+    // _GLIBCXX_RESOLVE_LIB_DEFECTS
+    // 7. string clause minor problems 
+    void 
+    push_back(_CharT __c)
+    {
+      _Base::push_back(__c);
+      this->_M_invalidate_all();
+    }
+
+    basic_string& 
+    assign(const basic_string& __x)
+    {
+      _Base::assign(__x);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    assign(const basic_string& __str, size_type __pos, size_type __n)
+    {
+      _Base::assign(__str, __pos, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    assign(const _CharT* __s, size_type __n)
+    {
+      __glibcxx_check_string_len(__s, __n);
+      _Base::assign(__s, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    assign(const _CharT* __s)
+    {
+      __glibcxx_check_string(__s);
+      _Base::assign(__s);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    assign(size_type __n, _CharT __c)
+    {
+      _Base::assign(__n, __c);
+      this->_M_invalidate_all();
+      return *this;	
+    }
+
+    template<typename _InputIterator>
+      basic_string& 
+      assign(_InputIterator __first, _InputIterator __last)
+      {
+	__glibcxx_check_valid_range(__first, __last);
+	_Base::assign(__first, __last);
+	this->_M_invalidate_all();
+	return *this;	
+      }
+
+    basic_string& 
+    insert(size_type __pos1, const basic_string& __str)
+    {
+      _Base::insert(__pos1, __str);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    insert(size_type __pos1, const basic_string& __str,
+	   size_type __pos2, size_type __n)
+    {
+      _Base::insert(__pos1, __str, __pos2, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    insert(size_type __pos, const _CharT* __s, size_type __n)
+    {
+      __glibcxx_check_string(__s);
+      _Base::insert(__pos, __s, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    insert(size_type __pos, const _CharT* __s)
+    {
+      __glibcxx_check_string(__s);
+      _Base::insert(__pos, __s);
+      this->_M_invalidate_all();
+      return *this;	
+    }
+
+    basic_string& 
+    insert(size_type __pos, size_type __n, _CharT __c)
+    {
+      _Base::insert(__pos, __n, __c);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    iterator 
+    insert(iterator __p, _CharT __c)
+    {
+      __glibcxx_check_insert(__p);
+      typename _Base::iterator __res = _Base::insert(__p.base(), __c);
+      this->_M_invalidate_all();
+      return iterator(__res, this);
+    }
+
+    void 
+    insert(iterator __p, size_type __n, _CharT __c)
+    {
+      __glibcxx_check_insert(__p);
+      _Base::insert(__p.base(), __n, __c);
+      this->_M_invalidate_all();
+    }
+
+    template<typename _InputIterator>
+      void 
+      insert(iterator __p, _InputIterator __first, _InputIterator __last)
+      {
+	__glibcxx_check_insert_range(__p, __first, __last);
+	_Base::insert(__p.base(), __first, __last);
+	this->_M_invalidate_all();
+      }
+
+    basic_string& 
+    erase(size_type __pos = 0, size_type __n = _Base::npos)
+    {
+      _Base::erase(__pos, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    iterator 
+    erase(iterator __position)
+    {
+      __glibcxx_check_erase(__position);
+      typename _Base::iterator __res = _Base::erase(__position.base());
+      this->_M_invalidate_all();
+      return iterator(__res, this);
+    }
+
+    iterator 
+    erase(iterator __first, iterator __last)
+    {
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 151. can't currently clear() empty container
+      __glibcxx_check_erase_range(__first, __last);
+      typename _Base::iterator __res = _Base::erase(__first.base(),
+						       __last.base());
+      this->_M_invalidate_all();
+      return iterator(__res, this);
+    }
+
+    basic_string& 
+    replace(size_type __pos1, size_type __n1, const basic_string& __str)
+    {
+      _Base::replace(__pos1, __n1, __str);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    replace(size_type __pos1, size_type __n1, const basic_string& __str,
+	    size_type __pos2, size_type __n2)
+    {
+      _Base::replace(__pos1, __n1, __str, __pos2, __n2);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    replace(size_type __pos, size_type __n1, const _CharT* __s, 
+	    size_type __n2)
+    {
+      __glibcxx_check_string_len(__s, __n2);
+      _Base::replace(__pos, __n1, __s, __n2);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    replace(size_type __pos, size_type __n1, const _CharT* __s)
+    {
+      __glibcxx_check_string(__s);
+      _Base::replace(__pos, __n1, __s);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
+    {
+      _Base::replace(__pos, __n1, __n2, __c);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    replace(iterator __i1, iterator __i2, const basic_string& __str)
+    {
+      __glibcxx_check_erase_range(__i1, __i2);
+      _Base::replace(__i1.base(), __i2.base(), __str);
+      this->_M_invalidate_all();
+      return *this;
+    }
+    
+    basic_string& 
+    replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
+    {
+      __glibcxx_check_erase_range(__i1, __i2);
+      __glibcxx_check_string_len(__s, __n);
+      _Base::replace(__i1.base(), __i2.base(), __s, __n);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    replace(iterator __i1, iterator __i2, const _CharT* __s)
+    {
+      __glibcxx_check_erase_range(__i1, __i2);
+      __glibcxx_check_string(__s);
+      _Base::replace(__i1.base(), __i2.base(), __s);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    basic_string& 
+    replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
+    {
+      __glibcxx_check_erase_range(__i1, __i2);
+      _Base::replace(__i1.base(), __i2.base(), __n, __c);
+      this->_M_invalidate_all();
+      return *this;
+    }
+
+    template<typename _InputIterator>
+      basic_string& 
+      replace(iterator __i1, iterator __i2,
+	      _InputIterator __j1, _InputIterator __j2)
+      {
+	__glibcxx_check_erase_range(__i1, __i2);
+	__glibcxx_check_valid_range(__j1, __j2);
+	_Base::replace(__i1.base(), __i2.base(), __j1, __j2);
+	this->_M_invalidate_all();
+	return *this;
+      }
+
+    size_type 
+    copy(_CharT* __s, size_type __n, size_type __pos = 0) const
+    {
+      __glibcxx_check_string_len(__s, __n);
+      return _Base::copy(__s, __n, __pos);
+    }
+
+    void 
+    swap(basic_string<_CharT,_Traits,_Allocator>& __x)
+    {
+      _Base::swap(__x);
+      this->_M_swap(__x);
+      this->_M_invalidate_all();
+      __x._M_invalidate_all();
+    }
+
+    // 21.3.6 string operations:
+    const _CharT* 
+    c_str() const
+    {
+      const _CharT* __res = _Base::c_str();
+      this->_M_invalidate_all();
+      return __res;
+    }
+
+    const _CharT* 
+    data() const
+    {
+      const _CharT* __res = _Base::data();
+      this->_M_invalidate_all();
+      return __res;
+    }
+
+    using _Base::get_allocator;
+
+    size_type 
+    find(const basic_string& __str, size_type __pos = 0) const
+    { return _Base::find(__str, __pos); }
+
+    size_type 
+    find(const _CharT* __s, size_type __pos, size_type __n) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::find(__s, __pos, __n);
+    }
+
+    size_type 
+    find(const _CharT* __s, size_type __pos = 0) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::find(__s, __pos);
+    }
+
+    size_type 
+    find(_CharT __c, size_type __pos = 0) const
+    { return _Base::find(__c, __pos); }
+
+    size_type 
+    rfind(const basic_string& __str, size_type __pos = _Base::npos) const
+    { return _Base::rfind(__str, __pos); }
+
+    size_type 
+    rfind(const _CharT* __s, size_type __pos, size_type __n) const
+    { 
+      __glibcxx_check_string_len(__s, __n);
+      return _Base::rfind(__s, __pos, __n);
+    }
+
+    size_type 
+    rfind(const _CharT* __s, size_type __pos = _Base::npos) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::rfind(__s, __pos);
+    }
+
+    size_type 
+    rfind(_CharT __c, size_type __pos = _Base::npos) const
+    { return _Base::rfind(__c, __pos); }
+	
+    size_type 
+    find_first_of(const basic_string& __str, size_type __pos = 0) const
+    { return _Base::find_first_of(__str, __pos); }
+
+    size_type 
+    find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
+    { 
+      __glibcxx_check_string(__s);
+      return _Base::find_first_of(__s, __pos, __n); 
+    }
+
+    size_type 
+    find_first_of(const _CharT* __s, size_type __pos = 0) const
+    { 
+      __glibcxx_check_string(__s);
+      return _Base::find_first_of(__s, __pos); 
+    }
+
+    size_type 
+    find_first_of(_CharT __c, size_type __pos = 0) const
+    { return _Base::find_first_of(__c, __pos); }
+
+    size_type 
+    find_last_of(const basic_string& __str, size_type __pos = _Base::npos) const
+    { return _Base::find_last_of(__str, __pos); }
+
+    size_type 
+    find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
+    { 
+      __glibcxx_check_string(__s);
+      return _Base::find_last_of(__s, __pos, __n);
+    }
+
+    size_type 
+    find_last_of(const _CharT* __s, size_type __pos = _Base::npos) const
+    { 
+      __glibcxx_check_string(__s);
+      return _Base::find_last_of(__s, __pos);
+    }
+
+    size_type 
+    find_last_of(_CharT __c, size_type __pos = _Base::npos) const
+    { return _Base::find_last_of(__c, __pos); }
+
+    size_type 
+    find_first_not_of(const basic_string& __str, size_type __pos = 0) const
+    { return _Base::find_first_not_of(__str, __pos); }
+
+    size_type 
+    find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
+    {
+      __glibcxx_check_string_len(__s, __n);
+      return _Base::find_first_not_of(__s, __pos, __n);
+    }
+
+    size_type 
+    find_first_not_of(const _CharT* __s, size_type __pos = 0) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::find_first_not_of(__s, __pos);
+    }
+
+    size_type 
+    find_first_not_of(_CharT __c, size_type __pos = 0) const
+    { return _Base::find_first_not_of(__c, __pos); }
+
+    size_type 
+    find_last_not_of(const basic_string& __str,
+				  size_type __pos = _Base::npos) const
+    { return _Base::find_last_not_of(__str, __pos); }
+
+    size_type 
+    find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::find_last_not_of(__s, __pos, __n);
+    }
+
+    size_type 
+    find_last_not_of(const _CharT* __s, size_type __pos = _Base::npos) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::find_last_not_of(__s, __pos);
+    }
+
+    size_type 
+    find_last_not_of(_CharT __c, size_type __pos = _Base::npos) const
+    { return _Base::find_last_not_of(__c, __pos); }
+
+    basic_string 
+    substr(size_type __pos = 0, size_type __n = _Base::npos) const
+    { return basic_string(_Base::substr(__pos, __n)); }
+
+    int 
+    compare(const basic_string& __str) const
+    { return _Base::compare(__str); }
+
+    int 
+    compare(size_type __pos1, size_type __n1,
+		  const basic_string& __str) const
+    { return _Base::compare(__pos1, __n1, __str); }
+
+    int 
+    compare(size_type __pos1, size_type __n1, const basic_string& __str,
+	      size_type __pos2, size_type __n2) const
+    { return _Base::compare(__pos1, __n1, __str, __pos2, __n2); }
+
+    int 
+    compare(const _CharT* __s) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::compare(__s);
+    }
+
+    //  _GLIBCXX_RESOLVE_LIB_DEFECTS
+    //  5. string::compare specification questionable
+    int 
+    compare(size_type __pos1, size_type __n1, const _CharT* __s) const
+    {
+      __glibcxx_check_string(__s);
+      return _Base::compare(__pos1, __n1, __s);
+    }
+
+    //  _GLIBCXX_RESOLVE_LIB_DEFECTS
+    //  5. string::compare specification questionable
+    int 
+    compare(size_type __pos1, size_type __n1,const _CharT* __s,
+	      size_type __n2) const
+    {
+      __glibcxx_check_string_len(__s, __n2);
+      return _Base::compare(__pos1, __n1, __s, __n2);
+    }
+
+    _Base&       
+    _M_base() { return *this; }
+
+    const _Base& 
+    _M_base() const { return *this; }
+
+    using _Safe_base::_M_invalidate_all;
+  };
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline basic_string<_CharT,_Traits,_Allocator>
+    operator+(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	      const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return basic_string<_CharT,_Traits,_Allocator>(__lhs) += __rhs; }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline basic_string<_CharT,_Traits,_Allocator>
+    operator+(const _CharT* __lhs,
+	      const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { 
+      __glibcxx_check_string(__lhs);
+      return basic_string<_CharT,_Traits,_Allocator>(__lhs) += __rhs;
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline basic_string<_CharT,_Traits,_Allocator>
+    operator+(_CharT __lhs, 
+	      const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return basic_string<_CharT,_Traits,_Allocator>(1, __lhs) += __rhs; }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline basic_string<_CharT,_Traits,_Allocator>
+    operator+(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	      const _CharT* __rhs)
+    { 
+      __glibcxx_check_string(__rhs);
+      return basic_string<_CharT,_Traits,_Allocator>(__lhs) += __rhs; 
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline basic_string<_CharT,_Traits,_Allocator>
+    operator+(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	      _CharT __rhs)
+    { return basic_string<_CharT,_Traits,_Allocator>(__lhs) += __rhs; }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool 
+    operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator==(const _CharT* __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    {
+      __glibcxx_check_string(__lhs);
+      return __lhs == __rhs._M_base();
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const _CharT* __rhs)
+    {
+      __glibcxx_check_string(__rhs);
+      return __lhs._M_base() == __rhs;
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool 
+    operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator!=(const _CharT* __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    {
+      __glibcxx_check_string(__lhs);
+      return __lhs != __rhs._M_base();
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const _CharT* __rhs)
+    {
+      __glibcxx_check_string(__rhs);
+      return __lhs._M_base() != __rhs;
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool 
+    operator<(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	      const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator<(const _CharT* __lhs,
+	      const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    {
+      __glibcxx_check_string(__lhs);
+      return __lhs < __rhs._M_base();
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator<(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	      const _CharT* __rhs)
+    {
+      __glibcxx_check_string(__rhs);
+      return __lhs._M_base() < __rhs;
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool 
+    operator<=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator<=(const _CharT* __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    {
+      __glibcxx_check_string(__lhs);
+      return __lhs <= __rhs._M_base();
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator<=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const _CharT* __rhs)
+    {
+      __glibcxx_check_string(__rhs);
+      return __lhs._M_base() <= __rhs;
+    }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool 
+    operator>=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator>=(const _CharT* __lhs,
+	       const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    {
+      __glibcxx_check_string(__lhs);
+      return __lhs >= __rhs._M_base();
+    }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator>=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	       const _CharT* __rhs)
+    {
+      __glibcxx_check_string(__rhs);
+      return __lhs._M_base() >= __rhs;
+    }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool 
+    operator>(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	      const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator>(const _CharT* __lhs,
+	      const basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    {
+      __glibcxx_check_string(__lhs);
+      return __lhs > __rhs._M_base();
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline bool
+    operator>(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	      const _CharT* __rhs)
+    {
+      __glibcxx_check_string(__rhs);
+      return __lhs._M_base() > __rhs;
+    }
+
+  // 21.3.7.8:
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    inline void 
+    swap(basic_string<_CharT,_Traits,_Allocator>& __lhs,
+	 basic_string<_CharT,_Traits,_Allocator>& __rhs)
+    { __lhs.swap(__rhs); }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    std::basic_ostream<_CharT, _Traits>&
+    operator<<(std::basic_ostream<_CharT, _Traits>& __os,
+	       const basic_string<_CharT, _Traits, _Allocator>& __str)
+    { return __os << __str._M_base(); }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    std::basic_istream<_CharT,_Traits>&
+    operator>>(std::basic_istream<_CharT,_Traits>& __is,
+	       basic_string<_CharT,_Traits,_Allocator>& __str)
+    {
+      std::basic_istream<_CharT,_Traits>& __res = __is >> __str._M_base();
+      __str._M_invalidate_all();
+      return __res;
+    }
+
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    std::basic_istream<_CharT,_Traits>&
+    getline(std::basic_istream<_CharT,_Traits>& __is,
+	    basic_string<_CharT,_Traits,_Allocator>& __str, _CharT __delim)
+    {
+      std::basic_istream<_CharT,_Traits>& __res = getline(__is, 
+							  __str._M_base(),
+							__delim);
+      __str._M_invalidate_all();
+      return __res;
+    }
+  
+  template<typename _CharT, typename _Traits, typename _Allocator>
+    std::basic_istream<_CharT,_Traits>&
+    getline(std::basic_istream<_CharT,_Traits>& __is,
+	    basic_string<_CharT,_Traits,_Allocator>& __str)
+    {
+      std::basic_istream<_CharT,_Traits>& __res = getline(__is, 
+							  __str._M_base());
+      __str._M_invalidate_all();
+      return __res;
+    }
+} // namespace __gnu_debug
+
+#endif 
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
new file mode 100644
index 00000000000..19249b6bb81
--- /dev/null
+++ b/libstdc++-v3/include/debug/vector
@@ -0,0 +1,409 @@
+// Debugging vector implementation -*- C++ -*-
+
+// 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.
+
+#ifndef _GLIBCXX_DEBUG_VECTOR
+#define _GLIBCXX_DEBUG_VECTOR 1
+
+#include <vector>
+#include <debug/safe_sequence.h>
+#include <debug/safe_iterator.h>
+
+namespace __gnu_debug_def
+{
+  template<typename _Tp, 
+	   typename _Allocator = std::allocator<_Tp> >
+    class vector
+    : public __gnu_norm::vector<_Tp, _Allocator>,
+      public __gnu_debug::_Safe_sequence<vector<_Tp, _Allocator> >
+    {
+      typedef __gnu_norm::vector<_Tp, _Allocator> _Base;
+      typedef __gnu_debug::_Safe_sequence<vector>              _Safe_base;
+
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
+
+    public:
+      typedef typename _Base::reference             reference;
+      typedef typename _Base::const_reference       const_reference;
+
+      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector> 
+      iterator;
+      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector>
+      const_iterator;
+
+      typedef typename _Base::size_type             size_type;
+      typedef typename _Base::difference_type       difference_type;
+
+      typedef _Tp        			    value_type;
+      typedef _Allocator 			    allocator_type;
+      typedef typename _Allocator::pointer          pointer;
+      typedef typename _Allocator::const_pointer    const_pointer;
+      typedef std::reverse_iterator<iterator>       reverse_iterator;
+      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+      // 23.2.4.1 construct/copy/destroy:
+      explicit vector(const _Allocator& __a = _Allocator())
+      : _Base(__a), _M_guaranteed_capacity(0) { }
+
+      explicit vector(size_type __n, const _Tp& __value = _Tp(),
+		      const _Allocator& __a = _Allocator())
+      : _Base(__n, __value, __a), _M_guaranteed_capacity(__n) { }
+
+      template<class _InputIterator>
+        vector(_InputIterator __first, _InputIterator __last,
+	       const _Allocator& __a = _Allocator())
+	: _Base(__gnu_debug::__check_valid_range(__first, __last), 
+		__last, __a),
+	  _M_guaranteed_capacity(0)
+        { _M_update_guaranteed_capacity(); }
+
+      vector(const vector<_Tp,_Allocator>& __x) 
+      : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
+
+      /// Construction from a release-mode vector
+      vector(const _Base& __x) 
+      : _Base(__x), _Safe_base(), _M_guaranteed_capacity(__x.size()) { }
+
+      ~vector() { }
+
+      vector<_Tp,_Allocator>& 
+      operator=(const vector<_Tp,_Allocator>& __x)
+      {
+	static_cast<_Base&>(*this) = __x;
+	this->_M_invalidate_all();
+	_M_update_guaranteed_capacity();
+	return *this;
+      }
+
+      template<typename _InputIterator>
+        void 
+        assign(_InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_check_valid_range(__first, __last);
+	  _Base::assign(__first, __last);
+	  this->_M_invalidate_all();
+	  _M_update_guaranteed_capacity();
+	}
+
+      void 
+      assign(size_type __n, const _Tp& __u)
+      {
+	_Base::assign(__n, __u);
+	this->_M_invalidate_all();
+	_M_update_guaranteed_capacity();
+      }
+
+      using _Base::get_allocator;
+
+      // iterators:
+      iterator 
+      begin() 
+      { return iterator(_Base::begin(), this); }
+
+      const_iterator 
+      begin() const 
+      { return const_iterator(_Base::begin(), this); }
+
+      iterator 
+      end()
+      { return iterator(_Base::end(), this); }
+
+      const_iterator 
+      end() const
+      { return const_iterator(_Base::end(), this); }
+
+      reverse_iterator 
+      rbegin() 
+      { return reverse_iterator(end()); }
+
+      const_reverse_iterator 
+      rbegin() const
+      { return const_reverse_iterator(end()); }
+
+      reverse_iterator 
+      rend() 
+      { return reverse_iterator(begin()); }
+
+      const_reverse_iterator 
+      rend() const 
+      { return const_reverse_iterator(begin()); }
+
+      // 23.2.4.2 capacity:
+      using _Base::size;
+      using _Base::max_size;
+
+      void 
+      resize(size_type __sz, _Tp __c = _Tp())
+      {
+	bool __realloc = _M_requires_reallocation(__sz);
+	if (__sz < this->size())
+	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
+	_Base::resize(__sz, __c);
+	if (__realloc)
+	  this->_M_invalidate_all();
+      }
+
+      using _Base::capacity;
+      using _Base::empty;
+
+      void 
+      reserve(size_type __n)
+      {
+	bool __realloc = _M_requires_reallocation(__n);
+	_Base::reserve(__n);
+	if (__n > _M_guaranteed_capacity)
+	  _M_guaranteed_capacity = __n;
+	if (__realloc)
+	  this->_M_invalidate_all();
+      }
+
+      // element access:
+      reference 
+      operator[](size_type __n)
+      {
+	__glibcxx_check_subscript(__n);
+	return _M_base()[__n];
+      }
+
+      const_reference 
+      operator[](size_type __n) const
+      {
+	__glibcxx_check_subscript(__n);
+	return _M_base()[__n];
+      }
+
+      using _Base::at;
+
+      reference 
+      front()
+      {
+	__glibcxx_check_nonempty();
+	return _Base::front();
+      }
+
+      const_reference 
+      front() const
+      {
+	__glibcxx_check_nonempty();
+	return _Base::front();
+      }
+
+      reference 
+      back()
+      {
+	__glibcxx_check_nonempty();
+	return _Base::back();
+      }
+
+      const_reference 
+      back() const
+      {
+	__glibcxx_check_nonempty();
+	return _Base::back();
+      }
+
+      // 23.2.4.3 modifiers:
+      void 
+      push_back(const _Tp& __x)
+      {
+	bool __realloc = _M_requires_reallocation(this->size() + 1);
+	_Base::push_back(__x);
+	if (__realloc)
+	  this->_M_invalidate_all();
+	_M_update_guaranteed_capacity();
+      }
+
+      void 
+      pop_back()
+      {
+	__glibcxx_check_nonempty();
+	iterator __victim = end() - 1;
+	__victim._M_invalidate();
+	_Base::pop_back();
+      }
+
+      iterator 
+      insert(iterator __position, const _Tp& __x)
+      {
+	__glibcxx_check_insert(__position);
+	bool __realloc = _M_requires_reallocation(this->size() + 1);
+	difference_type __offset = __position - begin();
+	typename _Base::iterator __res = _Base::insert(__position.base(),__x);
+	if (__realloc)
+	  this->_M_invalidate_all();
+	else
+	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	_M_update_guaranteed_capacity();
+	return iterator(__res, this);
+      }
+
+      void 
+      insert(iterator __position, size_type __n, const _Tp& __x)
+      {
+	__glibcxx_check_insert(__position);
+	bool __realloc = _M_requires_reallocation(this->size() + __n);
+	difference_type __offset = __position - begin();
+	_Base::insert(__position.base(), __n, __x);
+	if (__realloc)
+	  this->_M_invalidate_all();
+	else
+	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	_M_update_guaranteed_capacity();
+      }
+
+      template<class _InputIterator>
+        void 
+        insert(iterator __position, 
+	       _InputIterator __first, _InputIterator __last)
+        {
+	  __glibcxx_check_insert_range(__position, __first, __last);
+	  
+	  /* Hard to guess if invalidation will occur, because __last
+	     - __first can't be calculated in all cases, so we just
+	     punt here by checking if it did occur. */
+	  typename _Base::iterator __old_begin = _M_base().begin();
+	  difference_type __offset = __position - begin();
+	  _Base::insert(__position.base(), __first, __last);
+	  
+	  if (_M_base().begin() != __old_begin)
+	    this->_M_invalidate_all();
+	  else
+	    this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	  _M_update_guaranteed_capacity();
+	}
+      
+      iterator 
+      erase(iterator __position)
+      {
+	__glibcxx_check_erase(__position);
+	difference_type __offset = __position - begin();
+	typename _Base::iterator __res = _Base::erase(__position.base());
+	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	return iterator(__res, this);
+      }
+
+      iterator 
+      erase(iterator __first, iterator __last)
+      {
+	// _GLIBCXX_RESOLVE_LIB_DEFECTS
+	// 151. can't currently clear() empty container
+	__glibcxx_check_erase_range(__first, __last);
+      
+	difference_type __offset = __first - begin();
+	typename _Base::iterator __res = _Base::erase(__first.base(), 
+							 __last.base());
+	this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	return iterator(__res, this);
+      }
+
+      void 
+      swap(vector<_Tp,_Allocator>& __x)
+      {
+	_Base::swap(__x);
+	this->_M_swap(__x);
+      }
+
+      void 
+      clear()
+      {
+	_Base::clear();
+	this->_M_invalidate_all();
+      }
+
+      _Base&       
+      _M_base() { return *this; }
+
+      const _Base& 
+      _M_base() const { return *this; }
+
+    private:
+      size_type _M_guaranteed_capacity;
+
+      bool 
+      _M_requires_reallocation(size_type __elements)
+      {
+#ifdef _GLIBCXX_DEBUG_PEDANTIC
+	return __elements > this->capacity();
+#else
+	return __elements > _M_guaranteed_capacity;
+#endif
+      }
+      
+      void 
+      _M_update_guaranteed_capacity()
+      {
+	if (this->size() > _M_guaranteed_capacity)
+	  _M_guaranteed_capacity = this->size();
+      }
+    };
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator==(const vector<_Tp, _Alloc>& __lhs,
+	       const vector<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() == __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator!=(const vector<_Tp, _Alloc>& __lhs, 
+	       const vector<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() != __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<(const vector<_Tp, _Alloc>& __lhs, 
+	      const vector<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() < __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator<=(const vector<_Tp, _Alloc>& __lhs, 
+	       const vector<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() <= __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>=(const vector<_Tp, _Alloc>& __lhs, 
+	       const vector<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() >= __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline bool
+    operator>(const vector<_Tp, _Alloc>& __lhs, 
+	      const vector<_Tp, _Alloc>& __rhs)
+    { return __lhs._M_base() > __rhs._M_base(); }
+
+  template<typename _Tp, typename _Alloc>
+    inline void
+    swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
+    { __lhs.swap(__rhs); }
+} // namespace __gnu_debug_def
+
+#endif