2010-11-25 François Dumont <francois.cppdevs@free.fr>

	* src/debug.cc: Introduce a mutex pool in get_safe_base_mutex.
	Move code used to manipulate sequence safe iterators from safe
	iterator methods to safe sequence ones. Remove usage of safe iterator
	mutex, keep _Safe_iterator_base::_M_get_mutex for library backward
	binary compatibility.
	* src/Makefile.am: Build debug.cc in gnu++0x mode for _Hash_impl usage.
	* src/Makefile.in: Regenerate
	* include/debug/safe_base.h: Add _Safe_iterator_base _M_invalidate
	and _M_reset. Add _Safe_sequence_base _M_attach, _M_attach_single,
	_M_detach and _M_detach_single.
	* include/debug.safe_iterator.h, safe_iterator.tcc: Remove
	_Safe_iterator _M_invalidate and _M_invalidate_single. Implement all
	methods in terms of normal iterators rather than safe ones.
	* include/debug/safe_sequence.h: Replace _Safe_sequence
	_M_transfe_iter with _M_transfer_from_if taking the source sequence
	and a predicate signaling when a safe iterator shall be transfered.
	Add _Equal_to predicate.
	* include/debug/safe_sequence.tcc: New.
	* include/Makefile.am: Adjust.
	* include/Makefile.in: Regenerate.
	* include/debug/forward_list: Swap safe iterators in move constructor.
	Do not invalidate before begin in _M_invalidate_all method.
	Reimplement safe methods using normal iterators rather than safe ones.
	* include/debug/set.h, unordered_map, multiset.h, vector,
	unordered_set, deque, map.h, list, multimap.h: Reimplement safe method
	using normal iterators rather than safe ones.
	* testsuite/23_containers/forward_list/debug/clear.cc, swap.cc,
	move_constructor.cc, splice_after.cc, splice_after1.cc,
	splice_after2.cc, splice_after3.cc, splice_after4.cc: New.
	* testsuite/23_containers/vector/debug/multithreaded_swap.cc: New.



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

30 files changed, 1360 insertions, 588 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index bf498c36ffc..dc22b52a12e 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,36 @@
+2010-11-25  François Dumont  <francois.cppdevs@free.fr>
+
+	* src/debug.cc: Introduce a mutex pool in get_safe_base_mutex.
+	Move code used to manipulate sequence safe iterators from safe
+	iterator methods to safe sequence ones. Remove usage of safe iterator
+	mutex, keep _Safe_iterator_base::_M_get_mutex for library backward
+	binary compatibility.
+	* src/Makefile.am: Build debug.cc in gnu++0x mode for _Hash_impl usage.
+	* src/Makefile.in: Regenerate
+	* include/debug/safe_base.h: Add _Safe_iterator_base _M_invalidate
+	and _M_reset. Add _Safe_sequence_base _M_attach, _M_attach_single,
+	_M_detach and _M_detach_single.
+	* include/debug.safe_iterator.h, safe_iterator.tcc: Remove
+	_Safe_iterator _M_invalidate and _M_invalidate_single. Implement all
+	methods in terms of normal iterators rather than safe ones.
+	* include/debug/safe_sequence.h: Replace _Safe_sequence
+	_M_transfe_iter with _M_transfer_from_if taking the source sequence
+	and a predicate signaling when a safe iterator shall be transfered.
+	Add _Equal_to predicate.
+	* include/debug/safe_sequence.tcc: New.
+	* include/Makefile.am: Adjust.
+	* include/Makefile.in: Regenerate.
+	* include/debug/forward_list: Swap safe iterators in move constructor.
+	Do not invalidate before begin in _M_invalidate_all method.
+	Reimplement safe methods using normal iterators rather than safe ones.
+	* include/debug/set.h, unordered_map, multiset.h, vector,
+	unordered_set, deque, map.h, list, multimap.h: Reimplement safe method
+	using normal iterators rather than safe ones.
+	* testsuite/23_containers/forward_list/debug/clear.cc, swap.cc,
+	move_constructor.cc, splice_after.cc, splice_after1.cc,
+	splice_after2.cc, splice_after3.cc, splice_after4.cc: New.
+	* testsuite/23_containers/vector/debug/multithreaded_swap.cc: New.
+
 2010-11-24  Benjamin Kosnik  <bkoz@redhat.com>
 
 	* include/std/tuple: Mark more constructors constexpr.
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 3fb1876fb47..6587179a4ef 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -708,6 +708,7 @@ debug_headers = \
 	${debug_srcdir}/safe_iterator.h \
 	${debug_srcdir}/safe_iterator.tcc \
 	${debug_srcdir}/safe_sequence.h \
+	${debug_srcdir}/safe_sequence.tcc \
 	${debug_srcdir}/set \
 	${debug_srcdir}/set.h \
 	${debug_srcdir}/string \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index 82cdd922049..7ed93210258 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -941,6 +941,7 @@ debug_headers = \
 	${debug_srcdir}/safe_iterator.h \
 	${debug_srcdir}/safe_iterator.tcc \
 	${debug_srcdir}/safe_sequence.h \
+	${debug_srcdir}/safe_sequence.tcc \
 	${debug_srcdir}/set \
 	${debug_srcdir}/set.h \
 	${debug_srcdir}/string \
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 9c21598ea67..cf63c3af090 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -47,14 +47,17 @@ namespace __debug
       typedef  _GLIBCXX_STD_D::deque<_Tp, _Allocator> _Base;
       typedef __gnu_debug::_Safe_sequence<deque> _Safe_base;
 
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
     public:
       typedef typename _Base::reference             reference;
       typedef typename _Base::const_reference       const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque>
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator,deque>
 						    iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque>
-						     const_iterator;
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,deque>
+						    const_iterator;
 
       typedef typename _Base::size_type             size_type;
       typedef typename _Base::difference_type       difference_type;
@@ -219,6 +222,15 @@ namespace __debug
       { return const_reverse_iterator(begin()); }
 #endif
 
+    private:
+      void
+      _M_invalidate_after_nth(difference_type __n)
+      {
+	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
+	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
+      }
+      
+    public:
       // 23.2.1.2 capacity:
       using _Base::size;
       using _Base::max_size;
@@ -227,12 +239,9 @@ namespace __debug
       void
       resize(size_type __sz)
       {
-	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()));
+	  this->_M_invalidate_after_nth(__sz);
 
 	_Base::resize(__sz);
 
@@ -243,12 +252,9 @@ namespace __debug
       void
       resize(size_type __sz, const _Tp& __c)
       {
-	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()));
+	  this->_M_invalidate_after_nth(__sz);
 
 	_Base::resize(__sz, __c);
 
@@ -259,12 +265,9 @@ namespace __debug
       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()));
+	  this->_M_invalidate_after_nth(__sz);
 
 	_Base::resize(__sz, __c);
 
@@ -369,8 +372,8 @@ namespace __debug
         emplace(iterator __position, _Args&&... __args)
 	{
 	  __glibcxx_check_insert(__position);
-	  typename _Base::iterator __res = _Base::emplace(__position.base(),
-					    std::forward<_Args>(__args)...);
+	  _Base_iterator __res = _Base::emplace(__position.base(),
+						std::forward<_Args>(__args)...);
 	  this->_M_invalidate_all();
 	  return iterator(__res, this);
 	}
@@ -380,7 +383,7 @@ namespace __debug
       insert(iterator __position, const _Tp& __x)
       {
 	__glibcxx_check_insert(__position);
-	typename _Base::iterator __res = _Base::insert(__position.base(), __x);
+	_Base_iterator __res = _Base::insert(__position.base(), __x);
 	this->_M_invalidate_all();
 	return iterator(__res, this);
       }
@@ -421,8 +424,7 @@ namespace __debug
       pop_front()
       {
 	__glibcxx_check_nonempty();
-	iterator __victim = begin();
-	__victim._M_invalidate();
+	this->_M_invalidate_if(_Equal(_Base::begin()));
 	_Base::pop_front();
       }
 
@@ -430,9 +432,7 @@ namespace __debug
       pop_back()
       {
 	__glibcxx_check_nonempty();
-	iterator __victim = end();
-	--__victim;
-	__victim._M_invalidate();
+	this->_M_invalidate_if(_Equal(--_Base::end()));
 	_Base::pop_back();
       }
 
@@ -440,14 +440,15 @@ namespace __debug
       erase(iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	if (__position == begin() || __position == end()-1)
+	_Base_iterator __victim = __position.base();
+	if (__victim == _Base::begin() || __victim == _Base::end()-1)
 	  {
-	    __position._M_invalidate();
-	    return iterator(_Base::erase(__position.base()), this);
+	    this->_M_invalidate_if(_Equal(__victim));
+	    return iterator(_Base::erase(__victim), this);
 	  }
 	else
 	  {
-	    typename _Base::iterator __res = _Base::erase(__position.base());
+	    _Base_iterator __res = _Base::erase(__victim);
 	    this->_M_invalidate_all();
 	    return iterator(__res, this);
 	  }
@@ -459,13 +460,13 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-        if (__first == begin() || __last == end())
+        if (__first.base() == _Base::begin() || __last.base() == _Base::end())
 	  {
 	    this->_M_detach_singular();
-	    for (iterator __position = __first; __position != __last; )
+	    for (_Base_iterator __position = __first.base();
+		 __position != __last.base(); ++__position)
 	      {
-		iterator __victim = __position++;
-		__victim._M_invalidate();
+		this->_M_invalidate_if(_Equal(__position));
 	      }
 	    __try
 	      {
@@ -480,8 +481,8 @@ namespace __debug
 	  }
 	else
 	  {
-	    typename _Base::iterator __res = _Base::erase(__first.base(),
-							  __last.base());
+	    _Base_iterator __res = _Base::erase(__first.base(),
+						__last.base());
 	    this->_M_invalidate_all();
 	    return iterator(__res, this);
 	  }
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index 6869269eacb..03b661ec221 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -48,13 +48,15 @@ namespace __debug
       typedef _GLIBCXX_STD_D::forward_list<_Tp, _Alloc> _Base;
       typedef __gnu_debug::_Safe_sequence<forward_list> _Safe_base;
 
+      typedef typename _Base::iterator       _Base_iterator;
+      typedef typename _Base::const_iterator _Base_const_iterator;
     public:
       typedef typename _Base::reference             reference;
       typedef typename _Base::const_reference       const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 					  forward_list> iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  forward_list> const_iterator;
 
       typedef typename _Base::size_type             size_type;
@@ -75,7 +77,7 @@ namespace __debug
       { }
 
       forward_list(forward_list&& __list, const _Alloc& __al)
-      : _Base(std::move(__list), __al)
+      : _Base(std::move(__list._M_base()), __al)
       {
 	this->_M_swap(__list);
       }
@@ -103,7 +105,10 @@ namespace __debug
       { }
 
       forward_list(forward_list&& __list)
-      : _Base(std::move(__list)) { }
+      : _Base(std::move(__list._M_base()))
+      {
+	this->_M_swap(__list);
+      }
 
       forward_list(std::initializer_list<_Tp> __il,
                    const _Alloc& __al = _Alloc())
@@ -231,8 +236,8 @@ namespace __debug
       pop_front()
       {
 	__glibcxx_check_nonempty();
-	iterator __victim = begin();
-	__victim._M_invalidate();
+	this->_M_invalidate_if([this](_Base_const_iterator __it)
+	  { return __it == this->_M_base().cbegin(); });
 	_Base::pop_front();
       }
 
@@ -288,25 +293,37 @@ namespace __debug
 	return iterator(_Base::insert_after(__pos.base(), __il), this);
       }
 
+    private:
+      _Base_iterator
+      _M_erase_after(_Base_const_iterator __pos)
+      {
+	_Base_const_iterator __next = std::next(__pos);
+	this->_M_invalidate_if([__next](_Base_const_iterator __it)
+	  { return __it == __next; });
+	return _Base::erase_after(__pos);
+      }
+    public:
       iterator
       erase_after(const_iterator __pos)
       {
 	__glibcxx_check_erase_after(__pos);
-	const_iterator __victim = __pos;
-	++__victim;
-	__victim._M_invalidate();
-	return iterator(_Base::erase_after(__pos.base()), this);
+	return iterator(_M_erase_after(__pos.base()), this);
       }
 
       iterator
       erase_after(const_iterator __pos, const_iterator __last)
       {
 	__glibcxx_check_erase_range_after(__pos, __last);
-	for (const_iterator __victim = std::next(__pos); __victim != __last; )
+	for (_Base_const_iterator __victim = std::next(__pos.base());
+	    __victim != __last.base(); ++__victim)
 	  {
-	    const_iterator __old = __victim;
-	    ++__victim;
-	    __old._M_invalidate();
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range2)
+				  ._M_sequence(*this, "this")
+				  ._M_iterator(__pos, "pos")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if([__victim](_Base_const_iterator __it)
+	      { return __it == __victim; });
 	  }
 	return iterator(_Base::erase_after(__pos.base(), __last.base()), this);
       }
@@ -324,15 +341,15 @@ namespace __debug
 	this->_M_detach_singular();
 
 	// if __sz < size(), invalidate all iterators in [begin+__sz, end()
-	iterator __victim = begin();
-	iterator __end = end();
+	_Base_iterator __victim = _Base::begin();
+	_Base_iterator __end = _Base::end();
 	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 	  ++__victim;
 
-	while (__victim != __end)
+	for (; __victim != __end; ++__victim)
 	  {
-	    iterator __real_victim = __victim++;
-	    __real_victim._M_invalidate();
+	    this->_M_invalidate_if([__victim](_Base_const_iterator __it)
+	      { return __it == __victim; });
 	  }
 
 	__try
@@ -352,15 +369,15 @@ namespace __debug
 	this->_M_detach_singular();
 
 	// if __sz < size(), invalidate all iterators in [begin+__sz, end())
-	iterator __victim = begin();
-	iterator __end = end();
+	_Base_iterator __victim = _Base::begin();
+	_Base_iterator __end = _Base::end();
 	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 	  ++__victim;
 
-	while (__victim != __end)
+	for (; __victim != __end; ++__victim)
 	  {
-	    iterator __real_victim = __victim++;
-	    __real_victim._M_invalidate();
+	    this->_M_invalidate_if([__victim](_Base_const_iterator __it)
+	      { return __it == __victim; });
 	  }
 
 	__try
@@ -382,29 +399,6 @@ namespace __debug
       }
 
       // 23.2.3.5 forward_list operations:
-    private:
-      void
-      _M_splice_after(const_iterator __pos, forward_list&& __list,
-		      const_iterator __before, const_iterator __last)
-      {
-	for (const_iterator __tmp = std::next(__before); __tmp != __last; )
-	  {
-	    _GLIBCXX_DEBUG_VERIFY(&__list != this || __tmp != __pos,
-                                  _M_message(__gnu_debug::__msg_splice_overlap)
-                                  ._M_iterator(__tmp, "position")
-				  ._M_iterator(__before, "before")
-				  ._M_iterator(__last, "last"));
-	    const_iterator __victim = __tmp++;
-	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
-	    // 250. splicing invalidates iterators
-	    this->_M_transfer_iter(__victim);
-	  }
-
-	_Base::splice_after(__pos.base(), std::move(__list._M_base()),
-			    __before.base(), __last.base());
-      }
-
-    public:
       void
       splice_after(const_iterator __pos, forward_list&& __list)
       {
@@ -412,8 +406,12 @@ namespace __debug
 	_GLIBCXX_DEBUG_VERIFY(&__list != this,
 			      _M_message(__gnu_debug::__msg_self_splice)
 			      ._M_sequence(*this, "this"));
-	_M_splice_after(__pos, std::move(__list),
-			__list.before_begin(), __list.end());
+	this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it)
+	  {
+	    return __it != __list._M_base().cbefore_begin()
+		   && __it != __list._M_base().end();
+	  });
+	_Base::splice_after(__pos.base(), std::move(__list._M_base()));
       }
 
       void
@@ -431,7 +429,9 @@ namespace __debug
 
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 250. splicing invalidates iterators
-	this->_M_transfer_iter(__i);
+	_Base_const_iterator __next = std::next(__i.base());
+	this->_M_transfer_from_if(__list, [__next](_Base_const_iterator __it)
+	  { return __it == __next; });
 	_Base::splice_after(__pos.base(), std::move(__list._M_base()),
 			    __i.base());
       }
@@ -457,21 +457,39 @@ namespace __debug
 			      ._M_sequence(__list, "list")
 			      ._M_iterator(__before, "before")
 			      ._M_iterator(__last, "last"));
-	_M_splice_after(__pos, std::move(__list), __before, __last);
+
+	for (_Base_const_iterator __tmp = std::next(__before.base());
+	     __tmp != __last.base(); ++__tmp)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__tmp != __list._M_base().end(),
+				  _M_message(__gnu_debug::__msg_valid_range2)
+				  ._M_sequence(__list, "list")
+				  ._M_iterator(__before, "before")
+				  ._M_iterator(__last, "last"));
+	    _GLIBCXX_DEBUG_VERIFY(&__list != this || __tmp != __pos.base(),
+                                  _M_message(__gnu_debug::__msg_splice_overlap)
+                                  ._M_iterator(__tmp, "position")
+				  ._M_iterator(__before, "before")
+				  ._M_iterator(__last, "last"));
+	    // _GLIBCXX_RESOLVE_LIB_DEFECTS
+	    // 250. splicing invalidates iterators
+	    this->_M_transfer_from_if(__list, [__tmp](_Base_const_iterator __it)
+	      { return __it == __tmp; });
+	  }
+
+	_Base::splice_after(__pos.base(), std::move(__list._M_base()),
+			    __before.base(), __last.base());
       }
 
       void
       remove(const _Tp& __val)
       {
-	iterator __x = before_begin();
-	iterator __old = __x++;
-	while (__x.base() != _Base::end())
+	_Base_iterator __x = _Base::before_begin();
+	_Base_iterator __old = __x++;
+	while (__x != _Base::end())
 	  {
 	    if (*__x == __val)
-	      {
-		erase_after(__old);
-		__x = __old; ++__x;
-	      }
+	      __x = _M_erase_after(__old);
 	    else
 	      __old = __x++;
 	  }
@@ -481,15 +499,12 @@ namespace __debug
         void
         remove_if(_Pred __pred)
 	{
-	  iterator __x = before_begin();
-	  iterator __old = __x++;
-	  while (__x.base() != _Base::end())
+	  _Base_iterator __x = _Base::before_begin();
+	  _Base_iterator __old = __x++;
+	  while (__x != _Base::end())
 	    {
 	      if (__pred(*__x))
-		{
-		  erase_after(__old);
-		  __x = std::next(__old);
-		}
+		__x = _M_erase_after(__old);
 	      else
 		__old = __x++;
 	    }
@@ -498,20 +513,17 @@ namespace __debug
       void
       unique()
       {
-	iterator __first = begin();
-	iterator __last = end();
+	_Base_iterator __first = _Base::begin();
+	_Base_iterator __last = _Base::end();
 	if (__first == __last)
 	  return;
-	iterator __next = __first;
-	while (++__next != __last)
+	_Base_iterator __next = std::next(__first);
+	while (__next != __last)
 	  {
 	    if (*__first == *__next)
-	      {
-		erase_after(__first);
-		__next = __first;
-	      }
+	      __next = _M_erase_after(__first);
 	    else
-	      __first = __next;
+	      __first = __next++;
 	  }
       }
 
@@ -519,20 +531,17 @@ namespace __debug
         void
         unique(_BinPred __binary_pred)
 	{
-	  iterator __first = begin();
-	  iterator __last = end();
+	  _Base_iterator __first = _Base::begin();
+	  _Base_iterator __last = _Base::end();
 	  if (__first == __last)
 	    return;
-	  iterator __next = __first;
-	  while (++__next != __last)
+	  _Base_iterator __next = std::next(__first);
+	  while (__next != __last)
 	    {
 	      if (__binary_pred(*__first, *__next))
-		{
-		  erase_after(__first);
-		  __next = __first;
-		}
+		__next = _M_erase_after(__first);
 	      else
-		__first = __next;
+		__first = __next++;
 	    }
 	}
 
@@ -544,11 +553,11 @@ namespace __debug
 	  __glibcxx_check_sorted(_Base::begin(), _Base::end());
 	  __glibcxx_check_sorted(__list._M_base().begin(),
 				 __list._M_base().end());
-	  for (iterator __tmp = __list.begin(); __tmp != __list.end();)
+	  this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it)
 	    {
-	      iterator __victim = __tmp++;
-	      this->_M_transfer_iter(__victim);
-	    }
+	      return __it != __list._M_base().cbefore_begin()
+		     && __it != __list._M_base().cend();
+	    });
 	  _Base::merge(std::move(__list._M_base()));
 	}
       }
@@ -562,11 +571,12 @@ namespace __debug
 	    __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp);
 	    __glibcxx_check_sorted_pred(__list._M_base().begin(),
 					__list._M_base().end(), __comp);
-	    for (iterator __tmp = __list.begin(); __tmp != __list.end();)
+	    this->_M_transfer_from_if(__list,
+				      [&__list](_Base_const_iterator __it)
 	      {
-		iterator __victim = __tmp++;
-		this->_M_transfer_iter(__victim);
-	      }
+	        return __it != __list._M_base().cbefore_begin()
+		       && __it != __list._M_base().cend();
+	      });
 	    _Base::merge(std::move(__list._M_base()), __comp);
 	  }
 	}
@@ -584,9 +594,11 @@ namespace __debug
       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()));
+	this->_M_invalidate_if([this](_Base_const_iterator __it)
+	  {
+	    return __it != this->_M_base().cbefore_begin()
+		   && __it != this->_M_base().cend();
+	  });
       }
     };
 
@@ -644,11 +656,13 @@ namespace __gnu_debug
   template<class _Tp, class _Alloc>
     struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> >
     {
-      typedef typename forward_list<_Tp, _Alloc>::const_iterator _It;
+      typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence;
+      typedef typename _Sequence::const_iterator _It;
+      typedef typename _It::iterator_type _BaseIt;
 
       static bool
-      _M_Is(_It __it, const forward_list<_Tp, _Alloc>* __seq)
-      { return __it == __seq->before_begin(); }
+      _M_Is(_BaseIt __it, const _Sequence* __seq)
+      { return __it == __seq->_M_base().cbefore_begin(); }
     };
 }
 
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index b6567846e9b..54b736c8a9c 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -47,13 +47,17 @@ namespace __debug
       typedef _GLIBCXX_STD_D::list<_Tp, _Allocator> _Base;
       typedef __gnu_debug::_Safe_sequence<list>  _Safe_base;
 
+      typedef typename _Base::iterator       _Base_iterator;
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
+      typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
     public:
       typedef typename _Base::reference             reference;
       typedef typename _Base::const_reference       const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list>
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
 						    iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, list>
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
 						    const_iterator;
 
       typedef typename _Base::size_type             size_type;
@@ -230,15 +234,14 @@ namespace __debug
 	this->_M_detach_singular();
 
 	// if __sz < size(), invalidate all iterators in [begin+__sz, end())
-	iterator __victim = begin();
-	iterator __end = end();
+	_Base_iterator __victim = _Base::begin();
+	_Base_iterator __end = _Base::end();
 	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 	  ++__victim;
 
-	while (__victim != __end)
+	for (; __victim != __end; ++__victim)
 	  {
-	    iterator __real_victim = __victim++;
-	    __real_victim._M_invalidate();
+	    this->_M_invalidate_if(_Equal(__victim));
 	  }
 
 	__try
@@ -258,15 +261,14 @@ namespace __debug
 	this->_M_detach_singular();
 
 	// if __sz < size(), invalidate all iterators in [begin+__sz, end())
-	iterator __victim = begin();
-	iterator __end = end();
+	_Base_iterator __victim = _Base::begin();
+	_Base_iterator __end = _Base::end();
 	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 	  ++__victim;
 
-	while (__victim != __end)
+	for (; __victim != __end; ++__victim)
 	  {
-	    iterator __real_victim = __victim++;
-	    __real_victim._M_invalidate();
+	    this->_M_invalidate_if(_Equal(__victim));
 	  }
 
 	__try
@@ -286,15 +288,14 @@ namespace __debug
 	this->_M_detach_singular();
 
 	// if __sz < size(), invalidate all iterators in [begin+__sz, end())
-	iterator __victim = begin();
-	iterator __end = end();
+	_Base_iterator __victim = _Base::begin();
+	_Base_iterator __end = _Base::end();
 	for (size_type __i = __sz; __victim != __end && __i > 0; --__i)
 	  ++__victim;
 
-	while (__victim != __end)
+	for (; __victim != __end; ++__victim)
 	  {
-	    iterator __real_victim = __victim++;
-	    __real_victim._M_invalidate();
+	    this->_M_invalidate_if(_Equal(__victim));
 	  }
 
 	__try
@@ -349,8 +350,7 @@ namespace __debug
       pop_front()
       {
 	__glibcxx_check_nonempty();
-	iterator __victim = begin();
-	__victim._M_invalidate();
+	this->_M_invalidate_if(_Equal(_Base::begin()));
 	_Base::pop_front();
       }
 
@@ -364,9 +364,7 @@ namespace __debug
       pop_back()
       {
 	__glibcxx_check_nonempty();
-	iterator __victim = end();
-	--__victim;
-	__victim._M_invalidate();
+	this->_M_invalidate_if(_Equal(--_Base::end()));
 	_Base::pop_back();
       }
 
@@ -418,12 +416,19 @@ namespace __debug
 					   __gnu_debug::__base(__last));
 	}
 
+    private:
+      _Base_iterator
+      _M_erase(_Base_iterator __position)
+      {
+	this->_M_invalidate_if(_Equal(__position));
+	return _Base::erase(__position);
+      }
+    public:
       iterator
       erase(iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
-	return iterator(_Base::erase(__position.base()), this);
+	return iterator(_M_erase(__position.base()), this);
       }
 
       iterator
@@ -432,11 +437,14 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__position, __last);
-	for (iterator __victim = __position; __victim != __last; )
+	for (_Base_iterator __victim = __position.base();
+	     __victim != __last.base(); ++__victim)
 	  {
-	    iterator __old = __victim;
-	    ++__victim;
-	    __old._M_invalidate();
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+			          _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__position, "position")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
 	  }
 	return iterator(_Base::erase(__position.base(), __last.base()), this);
       }
@@ -466,7 +474,8 @@ namespace __debug
 	_GLIBCXX_DEBUG_VERIFY(&__x != this,
 			      _M_message(__gnu_debug::__msg_self_splice)
 			      ._M_sequence(*this, "this"));
-	this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
+	this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
+	_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()));
       }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -496,7 +505,7 @@ namespace __debug
 
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 250. splicing invalidates iterators
-	this->_M_transfer_iter(__i);
+	this->_M_transfer_from_if(__x, _Equal(__i.base()));
 	_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 		      __i.base());
       }
@@ -526,17 +535,21 @@ namespace __debug
 	// We used to perform the splice_alloc check:  not anymore, redundant
 	// after implementing the relevant bits of N1599.
 
-	for (iterator __tmp = __first; __tmp != __last; )
+	for (_Base_iterator __tmp = __first.base();
+	     __tmp != __last.base(); ++__tmp)
 	  {
+	    _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "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);
+	    this->_M_transfer_from_if(__x, _Equal(__tmp));
 	  }
 
 	_Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
@@ -552,10 +565,10 @@ namespace __debug
       void
       remove(const _Tp& __value)
       {
-	for (iterator __x = begin(); __x.base() != _Base::end(); )
+	for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
 	  {
 	    if (*__x == __value)
-	      __x = erase(__x);
+	      __x = _M_erase(__x);
 	    else
 	      ++__x;
 	  }
@@ -565,10 +578,10 @@ namespace __debug
         void
         remove_if(_Predicate __pred)
         {
-	  for (iterator __x = begin(); __x.base() != _Base::end(); )
+	  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
 	    {
 	      if (__pred(*__x))
-		__x = erase(__x);
+		__x = _M_erase(__x);
 	      else
 		++__x;
 	    }
@@ -577,18 +590,17 @@ namespace __debug
       void
       unique()
       {
-	iterator __first = begin();
-	iterator __last = end();
+	_Base_iterator __first = _Base::begin();
+	_Base_iterator __last = _Base::end();
 	if (__first == __last)
 	  return;
-	iterator __next = __first;
-	while (++__next != __last)
+	_Base_iterator __next = __first; ++__next;
+	while (__next != __last)
 	  {
 	    if (*__first == *__next)
-	      erase(__next);
+	      __next = _M_erase(__next);
 	    else
-	      __first = __next;
-	    __next = __first;
+	      __first = __next++;
 	  }
       }
 
@@ -596,18 +608,17 @@ namespace __debug
         void
         unique(_BinaryPredicate __binary_pred)
         {
-	  iterator __first = begin();
-	  iterator __last = end();
+	  _Base_iterator __first = _Base::begin();
+	  _Base_iterator __last = _Base::end();
 	  if (__first == __last)
 	    return;
-	  iterator __next = __first;
-	  while (++__next != __last)
+	  _Base_iterator __next = __first; ++__next;
+	  while (__next != __last)
 	    {
 	      if (__binary_pred(*__first, *__next))
-		erase(__next);
+		__next = _M_erase(__next);
 	      else
-		__first = __next;
-	      __next = __first;
+		__first = __next++;
 	    }
 	}
 
@@ -624,11 +635,7 @@ namespace __debug
 	  {
 	    __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++;
-		this->_M_transfer_iter(__victim);
-	      }
+	    this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
 	    _Base::merge(_GLIBCXX_MOVE(__x._M_base()));
 	  }
       }
@@ -655,11 +662,7 @@ namespace __debug
 					  __comp);
 	      __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(),
 					  __comp);
-	      for (iterator __tmp = __x.begin(); __tmp != __x.end();)
-		{
-		  iterator __victim = __tmp++;
-		  this->_M_transfer_iter(__victim);
-		}
+	      this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end()));
 	      _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp);
 	    }
 	}
@@ -690,9 +693,7 @@ namespace __debug
       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()));
+	this->_M_invalidate_if(_Not_equal(_Base::end()));
       }
     };
 
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 6e8858c6706..79f9b8287d4 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -48,6 +48,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> _Base;
       typedef __gnu_debug::_Safe_sequence<map> _Safe_base;
 
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
     public:
       // types:
       typedef _Key                                  key_type;
@@ -269,7 +272,7 @@ namespace __debug
       erase(const_iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	return iterator(_Base::erase(__position.base()), this);
       }
 #else
@@ -277,7 +280,7 @@ namespace __debug
       erase(iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	_Base::erase(__position.base());
       }
 #endif
@@ -285,15 +288,15 @@ namespace __debug
       size_type
       erase(const key_type& __x)
       {
-	iterator __victim = find(__x);
-	if (__victim == end())
+	_Base_iterator __victim = _Base::find(__x);
+	if (__victim == _Base::end())
 	  return 0;
 	else
-	{
-	  __victim._M_invalidate();
-	  _Base::erase(__victim.base());
-	  return 1;
-	}
+	  {
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim);
+	    return 1;
+	  }
       }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -303,9 +306,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
-	return iterator(__last.base()._M_const_cast(), this);
+	for (_Base_const_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	return iterator(_Base::erase(__first.base(), __last.base()), this);
       }
 #else
       void
@@ -314,8 +324,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
+	for (_Base_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	_Base::erase(__first.base(), __last.base());
       }
 #endif
 
@@ -328,7 +346,10 @@ namespace __debug
 
       void
       clear()
-      { this->erase(begin(), end()); }
+      {
+	this->_M_invalidate_all();
+	_Base::clear();
+      }
 
       // observers:
       using _Base::key_comp;
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index 56f58ffce3b..58673cc7adf 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -49,6 +49,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
       typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base;
 
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
     public:
       // types:
       typedef _Key				     key_type;
@@ -59,9 +62,9 @@ namespace __debug
       typedef typename _Base::reference              reference;
       typedef typename _Base::const_reference        const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multimap>
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
                                                      iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
                                            multimap> const_iterator;
 
       typedef typename _Base::size_type              size_type;
@@ -216,7 +219,7 @@ namespace __debug
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
       insert(const_iterator __position, const value_type& __x)
 #else
-      insert(iterator __position, const value_type& __x)	
+      insert(iterator __position, const value_type& __x)
 #endif
       {
 	__glibcxx_check_insert(__position);
@@ -250,7 +253,7 @@ namespace __debug
       erase(const_iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	return iterator(_Base::erase(__position.base()), this);
       }
 #else
@@ -258,7 +261,7 @@ namespace __debug
       erase(iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	_Base::erase(__position.base());
       }
 #endif
@@ -266,15 +269,16 @@ namespace __debug
       size_type
       erase(const key_type& __x)
       {
-	std::pair<iterator, iterator> __victims = this->equal_range(__x);
+	std::pair<_Base_iterator, _Base_iterator> __victims =
+	  _Base::equal_range(__x);
 	size_type __count = 0;
-	while (__victims.first != __victims.second)
-	{
-	  iterator __victim = __victims.first++;
-	  __victim._M_invalidate();
-	  _Base::erase(__victim.base());
-	  ++__count;
-	}
+	_Base_iterator __victim = __victims.first;
+	while (__victim !=  __victims.second)
+	  {
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim++);
+	    ++__count;
+	  }
 	return __count;
       }
 
@@ -285,9 +289,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
-	return iterator(__last.base()._M_const_cast(), this);
+	for (_Base_const_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	return iterator(_Base::erase(__first.base(), __last.base()), this);
       }
 #else
       void
@@ -296,8 +307,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
+	for (_Base_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	_Base::erase(__first.base(), __last.base());
       }
 #endif
 
@@ -310,7 +329,10 @@ namespace __debug
 
       void
       clear()
-      { this->erase(begin(), end()); }
+      {
+	this->_M_invalidate_all();
+	_Base::clear();
+      }
 
       // observers:
       using _Base::key_comp;
@@ -346,7 +368,6 @@ namespace __debug
       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),
@@ -356,9 +377,8 @@ namespace __debug
       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);
+	  _Base::equal_range(__x);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
@@ -373,9 +393,8 @@ namespace __debug
       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()));
+	this->_M_invalidate_if(_Not_equal(_Base::end()));
       }
     };
 
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index 9c950a1d0c2..8462586b844 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -48,6 +48,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator> _Base;
       typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
 
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
     public:
       // types:
       typedef _Key				     key_type;
@@ -58,9 +61,9 @@ namespace __debug
       typedef typename _Base::reference	             reference;
       typedef typename _Base::const_reference        const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
       iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  multiset> const_iterator;
 
       typedef typename _Base::size_type              size_type;
@@ -237,7 +240,7 @@ namespace __debug
       erase(const_iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	return iterator(_Base::erase(__position.base()), this);
       }
 #else
@@ -245,7 +248,7 @@ namespace __debug
       erase(iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	_Base::erase(__position.base());
       }
 #endif
@@ -253,15 +256,16 @@ namespace __debug
       size_type
       erase(const key_type& __x)
       {
-	std::pair<iterator, iterator> __victims = this->equal_range(__x);
+	std::pair<_Base_iterator, _Base_iterator> __victims =
+	  _Base::equal_range(__x);
 	size_type __count = 0;
-	while (__victims.first != __victims.second)
-	{
-	  iterator __victim = __victims.first++;
-	  __victim._M_invalidate();
-	  _Base::erase(__victim.base());
-	  ++__count;
-	}
+	_Base_iterator __victim = __victims.first;
+	while (__victim != __victims.second)
+	  {
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim++);
+	    ++__count;
+	  }
 	return __count;
       }
 
@@ -272,9 +276,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
-	return __last; // iterator == const_iterator
+	for (_Base_const_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	return iterator(_Base::erase(__first.base(), __last.base()), this);
       }
 #else
       void
@@ -283,8 +294,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
+	for (_Base_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	_Base::erase(__first.base(), __last.base());
       }
 #endif
 
@@ -297,7 +316,10 @@ namespace __debug
 
       void
       clear()
-      { this->erase(begin(), end()); }
+      {
+	this->_M_invalidate_all();
+	_Base::clear();
+      }
 
       // observers:
       using _Base::key_comp;
@@ -339,9 +361,8 @@ namespace __debug
       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);
+	  _Base::equal_range(__x);
 	return std::make_pair(iterator(__res.first, this),
 			      iterator(__res.second, this));
       }
@@ -351,9 +372,8 @@ namespace __debug
       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);
+	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));
       }
@@ -368,9 +388,8 @@ namespace __debug
       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()));
+	this->_M_invalidate_if(_Not_equal(_Base::end()));
       }
     };
 
diff --git a/libstdc++-v3/include/debug/safe_base.h b/libstdc++-v3/include/debug/safe_base.h
index 3e81f9b8a99..2ebdd89b58f 100644
--- a/libstdc++-v3/include/debug/safe_base.h
+++ b/libstdc++-v3/include/debug/safe_base.h
@@ -137,6 +137,15 @@ namespace __gnu_debug
 	Returns true if both iterators are nonsingular and reference
 	the same sequence. */
     _GLIBCXX_PURE bool _M_can_compare(const _Safe_iterator_base& __x) const throw ();
+
+    /** Invalidate the iterator, making it singular. */
+    void
+    _M_invalidate()
+    { _M_version = 0; }
+
+    /** Reset all member variables */
+    void
+    _M_reset() throw ();
   };
 
   /**
@@ -214,6 +223,22 @@ namespace __gnu_debug
     void
     _M_invalidate_all() const
     { if (++_M_version == 0) _M_version = 1; }
+
+    /** Attach an iterator to this sequence. */
+    void
+    _M_attach(_Safe_iterator_base* __it, bool __constant);
+
+    /** Likewise but not thread safe. */
+    void
+    _M_attach_single(_Safe_iterator_base* __it, bool __constant) throw ();
+
+    /** Detach an iterator from this sequence */
+    void
+    _M_detach(_Safe_iterator_base* __it);
+
+    /** Likewise but not thread safe. */
+    void
+    _M_detach_single(_Safe_iterator_base* __it) throw ();
   };
 } // namespace __gnu_debug
 
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index 4bcca092826..733a2c6a0a7 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -47,9 +47,10 @@ namespace __gnu_debug
     struct _BeforeBeginHelper
     {
       typedef typename _Sequence::const_iterator _It;
+      typedef typename _It::iterator_type _BaseIt;
 
       static bool
-      _M_Is(_It __it, const _Sequence* __seq)
+      _M_Is(_BaseIt __it, const _Sequence* __seq)
       { return false; }
     };
 
@@ -176,7 +177,7 @@ namespace __gnu_debug
 			      ._M_iterator(*this, "this")
 			      ._M_iterator(__x, "other"));
 	_M_current = __x._M_current;
-	this->_M_attach(static_cast<_Sequence*>(__x._M_sequence));
+	this->_M_attach(__x._M_sequence);
 	return *this;
       }
 
@@ -331,28 +332,18 @@ namespace __gnu_debug
 
       /** Attach iterator to the given sequence. */
       void
-      _M_attach(const _Sequence* __seq)
+      _M_attach(_Safe_sequence_base* __seq)
       {
-	_Safe_iterator_base::_M_attach(const_cast<_Sequence*>(__seq),
-				       _M_constant());
+	_Safe_iterator_base::_M_attach(__seq, _M_constant());
       }
 
       /** Likewise, but not thread-safe. */
       void
-      _M_attach_single(const _Sequence* __seq)
+      _M_attach_single(_Safe_sequence_base* __seq)
       {
-	_Safe_iterator_base::_M_attach_single(const_cast<_Sequence*>(__seq),
-					      _M_constant());
+	_Safe_iterator_base::_M_attach_single(__seq, _M_constant());
       }
 
-      /** Invalidate the iterator, making it singular. */
-      void
-      _M_invalidate();
-
-      /** Likewise, but not thread-safe. */
-      void
-      _M_invalidate_single();
-
       /// Is the iterator dereferenceable?
       bool
       _M_dereferenceable() const
@@ -405,31 +396,26 @@ namespace __gnu_debug
       static std::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);
-      }
+      { return std::make_pair(__rhs - __lhs, __dp_exact); }
 
     template<typename _Iterator1, typename _Iterator2>
       static std::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);
-      }
+      { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); }
 
       /// Is this iterator equal to the sequence's begin() iterator?
       bool _M_is_begin() const
-      { return *this == _M_get_sequence()->begin(); }
+      { return base() == _M_get_sequence()->_M_base().begin(); }
 
       /// Is this iterator equal to the sequence's end() iterator?
       bool _M_is_end() const
-      { return *this == _M_get_sequence()->end(); }
+      { return base() == _M_get_sequence()->_M_base().end(); }
 
       /// Is this iterator equal to the sequence's before_begin() iterator if
       /// any?
       bool _M_is_before_begin() const
-      { return _BeforeBeginHelper<_Sequence>::_M_Is(*this, _M_get_sequence()); }
+      { return _BeforeBeginHelper<_Sequence>::_M_Is(base(), _M_get_sequence()); }
     };
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index d4f2aee584b..fe93c95c59f 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -37,7 +37,8 @@ namespace __gnu_debug
     _Safe_iterator<_Iterator, _Sequence>::
     _M_can_advance(const difference_type& __n) const
     {
-      typedef typename _Sequence::const_iterator const_iterator;
+      typedef typename _Sequence::const_iterator const_debug_iterator;
+      typedef typename const_debug_iterator::iterator_type const_iterator;
 
       if (this->_M_singular())
 	return false;
@@ -45,20 +46,18 @@ namespace __gnu_debug
 	return true;
       if (__n < 0)
 	{
-	  const_iterator __begin =
-	    static_cast<const _Sequence*>(_M_sequence)->begin();
+	  const_iterator __begin = _M_get_sequence()->_M_base().begin();
 	  std::pair<difference_type, _Distance_precision> __dist =
-	    this->_M_get_distance(__begin, *this);
+	    this->_M_get_distance(__begin, base());
 	  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();
+	  const_iterator __end = _M_get_sequence()->_M_base().end();
 	  std::pair<difference_type, _Distance_precision> __dist =
-	    this->_M_get_distance(*this, __end);
+	    this->_M_get_distance(base(), __end);
 	  bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n)
 		       || (__dist.second != __dp_exact && __dist.first > 0));
 	  return __ok;
@@ -77,7 +76,7 @@ namespace __gnu_debug
 	/* Determine if we can order the iterators without the help of
 	   the container */
 	std::pair<difference_type, _Distance_precision> __dist =
-	  this->_M_get_distance(*this, __rhs);
+	  this->_M_get_distance(base(), __rhs.base());
 	switch (__dist.second) {
 	case __dp_equality:
 	  if (__dist.first == 0)
@@ -91,52 +90,16 @@ namespace __gnu_debug
 
 	/* We can only test for equality, but check if one of the
 	   iterators is at an extreme. */
+	/* Optim for classic [begin, it) or [it, end) ranges, limit checks
+	 * when code is valid. */
 	if (_M_is_begin() || __rhs._M_is_end())
 	  return true;
-	else if (_M_is_end() || __rhs._M_is_begin())
+	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()
-    {
-      __gnu_cxx::__scoped_lock sentry(this->_M_get_mutex());
-      _M_invalidate_single();
-    }
-
-  template<typename _Iterator, typename _Sequence>
-    void
-    _Safe_iterator<_Iterator, _Sequence>::
-    _M_invalidate_single()
-    {
-      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; __iter = __iter->_M_next)
-	    {
-	      iterator* __victim = static_cast<iterator*>(__iter);
-	      if (this->base() == __victim->base())
-		__victim->_M_version = 0;
-	    }
-
-	  for (_Safe_iterator_base* __iter2 = _M_sequence->_M_const_iterators;
-	       __iter2; __iter2 = __iter2->_M_next)
-	    {
-	      const_iterator* __victim = static_cast<const_iterator*>(__iter2);
-	      if (__victim->base() == this->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
index 830372d78a0..843c9b11710 100644
--- a/libstdc++-v3/include/debug/safe_sequence.h
+++ b/libstdc++-v3/include/debug/safe_sequence.h
@@ -57,6 +57,21 @@ namespace __gnu_debug
       { return __value != __x; }
     };
 
+  /** A simple function object that returns true if the passed-in
+   *  value is equal to the stored value. */
+  template <typename _Type>
+    class _Equal_to
+    {
+      _Type __value;
+
+    public:
+      explicit _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>
@@ -99,85 +114,24 @@ namespace __gnu_debug
     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. */
+	  true. @c pred will be invoked with the normal iterators nested
+	  in the safe ones. */
       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>
+      /** Transfers all iterators @c x that reference @c from sequence,
+	  are not singular, and for which @c pred(x) returns @c
+	  true. @c pred will be invoked with the normal iterators nested
+	  in the safe ones. */
+      template<typename _Predicate>
         void
-        _M_transfer_iter(const _Safe_iterator<_Iterator, _Sequence>& __x);
+        _M_transfer_from_if(_Safe_sequence& __from, _Predicate __pred);
     };
-
-  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;
-
-	__gnu_cxx::__scoped_lock sentry(this->_M_get_mutex());
-        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_single();
-	      }
-	  }
-
-        for (_Safe_iterator_base* __iter2 = _M_const_iterators; __iter2;)
-	  {
-	    const_iterator* __victim = static_cast<const_iterator*>(__iter2);
-	    __iter2 = __iter2->_M_next;
-	    if (!__victim->_M_singular())
-	      {
-		if (__pred(__victim->base()))
-		  __victim->_M_invalidate_single();
-	      }
-	  }
-      }
-
-  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;
-
-	__gnu_cxx::__scoped_lock sentry(this->_M_get_mutex());
-        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_single(static_cast<_Sequence*>(this));
-	  }
-
-        for (_Safe_iterator_base* __iter2 = __from->_M_const_iterators; 
-	     __iter2;)
-	  {
-	    const_iterator* __victim = static_cast<const_iterator*>(__iter2);
-	    __iter2 = __iter2->_M_next;
-	    if (!__victim->_M_singular() && __victim->base() == __x.base())
-	      __victim->_M_attach_single(static_cast<_Sequence*>(this));
-	  }
-      }
 } // namespace __gnu_debug
 
+#ifndef _GLIBCXX_EXPORT_TEMPLATE
+#  include <debug/safe_sequence.tcc>
+#endif
+
 #endif
diff --git a/libstdc++-v3/include/debug/safe_sequence.tcc b/libstdc++-v3/include/debug/safe_sequence.tcc
new file mode 100644
index 00000000000..bf0295cfd05
--- /dev/null
+++ b/libstdc++-v3/include/debug/safe_sequence.tcc
@@ -0,0 +1,150 @@
+// Safe sequence implementation  -*- C++ -*-
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/safe_sequence.tcc
+ *  This file is a GNU debug extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_DEBUG_SAFE_SEQUENCE_TCC
+#define _GLIBCXX_DEBUG_SAFE_SEQUENCE_TCC 1
+
+namespace __gnu_debug
+{
+  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;
+
+	__gnu_cxx::__scoped_lock sentry(this->_M_get_mutex());
+        for (_Safe_iterator_base* __iter = _M_iterators; __iter;)
+	  {
+	    iterator* __victim = static_cast<iterator*>(__iter);
+	    __iter = __iter->_M_next;
+	    if (!__victim->_M_singular() && __pred(__victim->base()))
+	      {
+		__victim->_M_invalidate();
+	      }
+	  }
+
+        for (_Safe_iterator_base* __iter2 = _M_const_iterators; __iter2;)
+	  {
+	    const_iterator* __victim = static_cast<const_iterator*>(__iter2);
+	    __iter2 = __iter2->_M_next;
+	    if (!__victim->_M_singular() && __pred(__victim->base()))
+	      {
+		__victim->_M_invalidate();
+	      }
+	  }
+      }
+
+  template<typename _Sequence>
+    template<typename _Predicate>
+      void
+      _Safe_sequence<_Sequence>::
+      _M_transfer_from_if(_Safe_sequence& __from, _Predicate __pred)
+      {
+        typedef typename _Sequence::iterator iterator;
+        typedef typename _Sequence::const_iterator const_iterator;
+
+	_Safe_iterator_base* __transfered_iterators = 0;
+	_Safe_iterator_base* __transfered_const_iterators = 0;
+	_Safe_iterator_base* __last_iterator = 0;
+	_Safe_iterator_base* __last_const_iterator = 0;
+	{
+	  // We lock __from first and detach iterator(s) to transfer
+	  __gnu_cxx::__scoped_lock sentry(__from._M_get_mutex());
+
+          for (_Safe_iterator_base* __iter = __from._M_iterators; __iter;)
+	    {
+	      iterator* __victim = static_cast<iterator*>(__iter);
+	      __iter = __iter->_M_next;
+	      if (!__victim->_M_singular() && __pred(__victim->base()))
+		{
+		  __victim->_M_detach_single();
+		  if (__transfered_iterators)
+		    {
+		      __victim->_M_next = __transfered_iterators;
+		      __transfered_iterators->_M_prior = __victim;
+		    }
+		  else
+		    __last_iterator = __victim;
+		  __victim->_M_sequence = this;
+		  __victim->_M_version = this->_M_version;
+		  __transfered_iterators = __victim;
+		}
+	    }
+
+	  for (_Safe_iterator_base* __iter2 = __from._M_const_iterators;
+		 __iter2;)
+	    {
+	      const_iterator* __victim = static_cast<const_iterator*>(__iter2);
+	      __iter2 = __iter2->_M_next;
+	      if (!__victim->_M_singular() && __pred(__victim->base()))
+		{
+		  __victim->_M_detach_single();
+		  if (__transfered_const_iterators)
+		    {
+		      __victim->_M_next = __transfered_const_iterators;
+		      __transfered_const_iterators->_M_prior = __victim;
+		    }
+		  else
+		    __last_const_iterator = __victim;
+		  __victim->_M_sequence = this;
+		  __victim->_M_version = this->_M_version;
+		  __transfered_const_iterators = __victim;
+		}
+	    }
+	}
+
+	// Now we can lock *this and add the transfered iterators if any
+	if (__last_iterator || __last_const_iterator)
+	  {
+	    __gnu_cxx::__scoped_lock sentry(this->_M_get_mutex());
+	    if (__last_iterator)
+	      {
+		if (this->_M_iterators)
+		  {
+		    this->_M_iterators->_M_prior = __last_iterator;
+		    __last_iterator->_M_next = this->_M_iterators;
+		  }
+		this->_M_iterators = __transfered_iterators;
+	      }
+	    if (__last_const_iterator)
+	      {
+		if (this->_M_const_iterators)
+		  {
+		    this->_M_const_iterators->_M_prior = __last_const_iterator;
+		    __last_const_iterator->_M_next = this->_M_const_iterators;
+		  }
+		this->_M_const_iterators = __transfered_const_iterators;
+	      }
+	  }
+      }
+} // namespace __gnu_debug
+
+#endif
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index b8ff463b2cf..60fbd38f26b 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -48,6 +48,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::set<_Key, _Compare, _Allocator> _Base;
       typedef __gnu_debug::_Safe_sequence<set> _Safe_base;
 
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
     public:
       // types:
       typedef _Key				    key_type;
@@ -58,9 +61,9 @@ namespace __debug
       typedef typename _Base::reference             reference;
       typedef typename _Base::const_reference       const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set>
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
                                                     iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
                                                     const_iterator;
 
       typedef typename _Base::size_type             size_type;
@@ -193,7 +196,6 @@ namespace __debug
       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);
@@ -248,7 +250,7 @@ namespace __debug
       erase(const_iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	return iterator(_Base::erase(__position.base()), this);
       }
 #else
@@ -256,7 +258,7 @@ namespace __debug
       erase(iterator __position)
       {
 	__glibcxx_check_erase(__position);
-	__position._M_invalidate();
+	this->_M_invalidate_if(_Equal(__position.base()));
 	_Base::erase(__position.base());
       }
 #endif
@@ -264,15 +266,15 @@ namespace __debug
       size_type
       erase(const key_type& __x)
       {
-	iterator __victim = find(__x);
-	if (__victim == end())
+	_Base_iterator __victim = _Base::find(__x);
+	if (__victim == _Base::end())
           return 0;
 	else
-        {
-	  __victim._M_invalidate();
-	  _Base::erase(__victim.base());
-	  return 1;
-        }
+	  {
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim);
+	    return 1;
+	  }
       }
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -282,9 +284,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
-	return __last; // iterator == const_iterator
+	for (_Base_const_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	return iterator(_Base::erase(__first.base(), __last.base()), this);
       }
 #else
       void
@@ -293,8 +302,16 @@ namespace __debug
 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
 	// 151. can't currently clear() empty container
 	__glibcxx_check_erase_range(__first, __last);
-	while (__first != __last)
-	  this->erase(__first++);
+	for (_Base_iterator __victim = __first.base();
+	     __victim != __last.base(); ++__victim)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__victim));
+	  }
+	_Base::erase(__first.base(), __last.base());
       }
 #endif
 
@@ -307,7 +324,10 @@ namespace __debug
 
       void
       clear()
-      { this->erase(begin(), end()); }
+      {
+	this->_M_invalidate_all();
+	_Base::clear();
+      }
 
       // observers:
       using _Base::key_comp;
@@ -349,7 +369,6 @@ namespace __debug
       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),
@@ -361,7 +380,6 @@ namespace __debug
       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),
@@ -378,7 +396,6 @@ namespace __debug
       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()));
       }
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index 6f37e040a26..29484c1ccdc 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -55,6 +55,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::unordered_map<_Key, _Tp, _Hash,
 					    _Pred, _Alloc> _Base;
       typedef __gnu_debug::_Safe_sequence<unordered_map> _Safe_base;
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
       typedef typename _Base::size_type       size_type;
@@ -65,9 +68,9 @@ namespace __debug
       typedef typename _Base::key_type        key_type;
       typedef typename _Base::value_type      value_type;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 					  unordered_map> iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  unordered_map> const_iterator;
 
       explicit
@@ -177,17 +180,14 @@ namespace __debug
       std::pair<iterator, bool>
       insert(const value_type& __obj)
       {
-	typedef std::pair<typename _Base::iterator, bool> __pair_type;
-	__pair_type __res = _Base::insert(__obj);
+	std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
 	return std::make_pair(iterator(__res.first, this), __res.second);
       }
 
       iterator
       insert(const_iterator, const value_type& __obj)
       {
-	typedef std::pair<typename _Base::iterator, bool> __pair_type;
-	__pair_type __res = _Base::insert(__obj);
-	return iterator(__res.first, this);
+	return iterator(_Base::insert(__obj).first, this);
       }
 
       template<typename _Pair, typename = typename
@@ -196,8 +196,8 @@ namespace __debug
         std::pair<iterator, bool>
         insert(_Pair&& __obj)
         {
-	  typedef std::pair<typename _Base::iterator, bool> __pair_type;
-	  __pair_type __res = _Base::insert(std::forward<_Pair>(__obj));
+	  std::pair<_Base_iterator, bool> __res =
+	    _Base::insert(std::forward<_Pair>(__obj));
 	  return std::make_pair(iterator(__res.first, this), __res.second);
 	}
 
@@ -207,9 +207,8 @@ namespace __debug
         iterator
         insert(const_iterator, _Pair&& __obj)
         {
-	  typedef std::pair<typename _Base::iterator, bool> __pair_type;
-	  __pair_type __res = _Base::insert(std::forward<_Pair>(__obj));
-	  return iterator(__res.first, this);
+	  return iterator(_Base::insert(std::forward<_Pair>(__obj)).first,
+			  this);
 	}
 
       void
@@ -236,9 +235,8 @@ namespace __debug
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
-	typedef typename _Base::iterator _Base_iterator;
-	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
-	__pair_type __res = _Base::equal_range(__key);
+	std::pair<_Base_iterator, _Base_iterator> __res =
+	  _Base::equal_range(__key);
 	return std::make_pair(iterator(__res.first, this),
 			      iterator(__res.second, this));
       }
@@ -246,9 +244,8 @@ namespace __debug
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
-	typedef typename _Base::const_iterator _Base_iterator;
-	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
-	__pair_type __res = _Base::equal_range(__key);
+	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	  _Base::equal_range(__key);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
@@ -257,10 +254,11 @@ namespace __debug
       erase(const key_type& __key)
       {
 	size_type __ret(0);
-	iterator __victim(_Base::find(__key), this);
-	if (__victim != end())
+	_Base_iterator __victim(_Base::find(__key));
+	if (__victim != _Base::end())
 	  {
-	    this->erase(__victim);
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim);
 	    __ret = 1;
 	  }
 	return __ret;
@@ -270,7 +268,7 @@ namespace __debug
       erase(const_iterator __it)
       {
 	__glibcxx_check_erase(__it);
-	__it._M_invalidate();
+	this->_M_invalidate_if(_Equal(__it.base()));
 	return iterator(_Base::erase(__it.base()), this);
       }
 
@@ -278,11 +276,15 @@ namespace __debug
       erase(const_iterator __first, const_iterator __last)
       {
 	__glibcxx_check_erase_range(__first, __last);
-	for (const_iterator __tmp = __first; __tmp != __last;)
-	{
-	  const_iterator __victim = __tmp++;
-	  __victim._M_invalidate();
-	}
+	for (_Base_const_iterator __tmp = __first.base();
+	     __tmp != __last.base(); ++__tmp)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__tmp));
+	  }
 	return iterator(_Base::erase(__first.base(),
 				     __last.base()), this);
       }
@@ -297,9 +299,8 @@ namespace __debug
       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()));
+	this->_M_invalidate_if(_Not_equal(_Base::end()));
       }
     };
 
@@ -339,6 +340,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::unordered_multimap<_Key, _Tp, _Hash,
 						 _Pred, _Alloc> _Base;
       typedef __gnu_debug::_Safe_sequence<unordered_multimap> _Safe_base;
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
       typedef typename _Base::size_type       size_type;
@@ -349,9 +353,9 @@ namespace __debug
       typedef typename _Base::key_type        key_type;
       typedef typename _Base::value_type      value_type;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 					  unordered_multimap> iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  unordered_multimap> const_iterator;
 
       explicit
@@ -476,9 +480,9 @@ namespace __debug
       template<typename _Pair, typename = typename
 	       std::enable_if<std::is_convertible<_Pair,
 						  value_type>::value>::type>
-        iterator
-        insert(const_iterator, _Pair&& __obj)
-        { return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
+	iterator
+	insert(const_iterator, _Pair&& __obj)
+	{ return iterator(_Base::insert(std::forward<_Pair>(__obj)), this); }
 
       void
       insert(std::initializer_list<value_type> __l)
@@ -504,9 +508,8 @@ namespace __debug
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
-	typedef typename _Base::iterator _Base_iterator;
-	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
-	__pair_type __res = _Base::equal_range(__key);
+	std::pair<_Base_iterator, _Base_iterator> __res =
+	  _Base::equal_range(__key);
 	return std::make_pair(iterator(__res.first, this),
 			      iterator(__res.second, this));
       }
@@ -514,9 +517,8 @@ namespace __debug
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
-	typedef typename _Base::const_iterator _Base_iterator;
-	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
-	__pair_type __res = _Base::equal_range(__key);
+	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	  _Base::equal_range(__key);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
@@ -525,10 +527,11 @@ namespace __debug
       erase(const key_type& __key)
       {
 	size_type __ret(0);
-	iterator __victim(_Base::find(__key), this);
-	if (__victim != end())
+	_Base_iterator __victim(_Base::find(__key));
+	if (__victim != _Base::end())
 	  {
-	    this->erase(__victim);
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim);
 	    __ret = 1;
 	  }
 	return __ret;
@@ -538,7 +541,7 @@ namespace __debug
       erase(const_iterator __it)
       {
 	__glibcxx_check_erase(__it);
-	__it._M_invalidate();
+	this->_M_invalidate_if(_Equal(__it.base()));
 	return iterator(_Base::erase(__it.base()), this);
       }
 
@@ -546,11 +549,15 @@ namespace __debug
       erase(const_iterator __first, const_iterator __last)
       {
 	__glibcxx_check_erase_range(__first, __last);
-	for (const_iterator __tmp = __first; __tmp != __last;)
-	{
-	  const_iterator __victim = __tmp++;
-	  __victim._M_invalidate();
-	}
+	for (_Base_const_iterator __tmp = __first.base();
+	     __tmp != __last.base(); ++__tmp)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__tmp));
+	  }
 	return iterator(_Base::erase(__first.base(),
 				     __last.base()), this);
       }
@@ -565,9 +572,8 @@ namespace __debug
       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()));
+	this->_M_invalidate_if(_Not_equal(_Base::end()));
       }
     };
 
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 1d42905e236..a606efec26f 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -55,6 +55,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
 					    _Pred, _Alloc> _Base;
       typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
       typedef typename _Base::size_type       size_type;
@@ -65,9 +68,9 @@ namespace __debug
       typedef typename _Base::key_type        key_type;
       typedef typename _Base::value_type      value_type;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 					  unordered_set> iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  unordered_set> const_iterator;
 
       explicit
@@ -177,7 +180,7 @@ namespace __debug
       std::pair<iterator, bool>
       insert(const value_type& __obj)
       {
-	typedef std::pair<typename _Base::iterator, bool> __pair_type;
+	typedef std::pair<_Base_iterator, bool> __pair_type;
 	__pair_type __res = _Base::insert(__obj);
 	return std::make_pair(iterator(__res.first, this), __res.second);
       }
@@ -185,7 +188,7 @@ namespace __debug
       iterator
       insert(const_iterator, const value_type& __obj)
       {
-	typedef std::pair<typename _Base::iterator, bool> __pair_type;
+	typedef std::pair<_Base_iterator, bool> __pair_type;
 	__pair_type __res = _Base::insert(__obj);
 	return iterator(__res.first, this);
       }
@@ -230,7 +233,6 @@ namespace __debug
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
-	typedef typename _Base::iterator _Base_iterator;
 	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 	__pair_type __res = _Base::equal_range(__key);
 	return std::make_pair(iterator(__res.first, this),
@@ -240,9 +242,8 @@ namespace __debug
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
-	typedef typename _Base::const_iterator _Base_iterator;
-	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
-	__pair_type __res = _Base::equal_range(__key);
+	std::pair<_Base_const_iterator, _Base_const_iterator>
+	  __res = _Base::equal_range(__key);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
@@ -251,10 +252,11 @@ namespace __debug
       erase(const key_type& __key)
       {
 	size_type __ret(0);
-	iterator __victim(_Base::find(__key), this);
-	if (__victim != end())
+	_Base_iterator __victim(_Base::find(__key));
+	if (__victim != _Base::end())
 	  {
-	    this->erase(__victim);
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim);
 	    __ret = 1;
 	  }
 	return __ret;
@@ -264,7 +266,7 @@ namespace __debug
       erase(const_iterator __it)
       {
 	__glibcxx_check_erase(__it);
-	__it._M_invalidate();
+	this->_M_invalidate_if(_Equal(__it.base()));
 	return iterator(_Base::erase(__it.base()), this);
       }
 
@@ -272,11 +274,15 @@ namespace __debug
       erase(const_iterator __first, const_iterator __last)
       {
 	__glibcxx_check_erase_range(__first, __last);
-	for (const_iterator __tmp = __first; __tmp != __last;)
-	{
-	  const_iterator __victim = __tmp++;
-	  __victim._M_invalidate();
-	}
+	for (_Base_const_iterator __tmp = __first.base();
+	     __tmp != __last.base(); ++__tmp)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__tmp));
+	  }
 	return iterator(_Base::erase(__first.base(),
 				     __last.base()), this);
       }
@@ -291,9 +297,8 @@ namespace __debug
       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()));
+	this->_M_invalidate_if(_Not_equal(_Base::end()));
       }
     };
 
@@ -329,6 +334,9 @@ namespace __debug
       typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
 						 _Pred, _Alloc> _Base;
       typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
+      typedef typename _Base::const_iterator _Base_const_iterator;
+      typedef typename _Base::iterator _Base_iterator;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
       typedef typename _Base::size_type       size_type;
@@ -339,9 +347,9 @@ namespace __debug
       typedef typename _Base::key_type        key_type;
       typedef typename _Base::value_type      value_type;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 					  unordered_multiset> iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 					  unordered_multiset> const_iterator;
 
       explicit
@@ -488,7 +496,6 @@ namespace __debug
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
-	typedef typename _Base::iterator _Base_iterator;
 	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 	__pair_type __res = _Base::equal_range(__key);
 	return std::make_pair(iterator(__res.first, this),
@@ -498,9 +505,8 @@ namespace __debug
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
-	typedef typename _Base::const_iterator _Base_iterator;
-	typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
-	__pair_type __res = _Base::equal_range(__key);
+	std::pair<_Base_const_iterator, _Base_const_iterator>
+	  __res = _Base::equal_range(__key);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
@@ -509,10 +515,11 @@ namespace __debug
       erase(const key_type& __key)
       {
 	size_type __ret(0);
-	iterator __victim(_Base::find(__key), this);
-	if (__victim != end())
+	_Base_iterator __victim(_Base::find(__key));
+	if (__victim != _Base::end())
 	  {
-	    this->erase(__victim);
+	    this->_M_invalidate_if(_Equal(__victim));
+	    _Base::erase(__victim);
 	    __ret = 1;
 	  }
 	return __ret;
@@ -522,7 +529,7 @@ namespace __debug
       erase(const_iterator __it)
       {
 	__glibcxx_check_erase(__it);
-	__it._M_invalidate();
+	this->_M_invalidate_if(_Equal(__it.base()));
 	return iterator(_Base::erase(__it.base()), this);
       }
 
@@ -530,11 +537,15 @@ namespace __debug
       erase(const_iterator __first, const_iterator __last)
       {
 	__glibcxx_check_erase_range(__first, __last);
-	for (const_iterator __tmp = __first; __tmp != __last;)
-	{
-	  const_iterator __victim = __tmp++;
-	  __victim._M_invalidate();
-	}
+	for (_Base_const_iterator __tmp = __first.base();
+	     __tmp != __last.base(); ++__tmp)
+	  {
+	    _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
+				  _M_message(__gnu_debug::__msg_valid_range)
+				  ._M_iterator(__first, "first")
+				  ._M_iterator(__last, "last"));
+	    this->_M_invalidate_if(_Equal(__tmp));
+	  }
 	return iterator(_Base::erase(__first.base(),
 				     __last.base()), this);
       }
@@ -549,9 +560,8 @@ namespace __debug
       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()));
+	this->_M_invalidate_if(_Not_equal(_Base::end()));
       }
     };
 
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 9004f2902ae..322c170289a 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -49,16 +49,17 @@ namespace __debug
       typedef _GLIBCXX_STD_D::vector<_Tp, _Allocator> _Base;
       typedef __gnu_debug::_Safe_sequence<vector>              _Safe_base;
 
+      typedef typename _Base::iterator _Base_iterator;
       typedef typename _Base::const_iterator _Base_const_iterator;
-      typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
+      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
       typedef typename _Base::reference             reference;
       typedef typename _Base::const_reference       const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,vector>
+      typedef __gnu_debug::_Safe_iterator<_Base_iterator,vector>
       iterator;
-      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,vector>
+      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,vector>
       const_iterator;
 
       typedef typename _Base::size_type             size_type;
@@ -246,7 +247,7 @@ namespace __debug
       {
 	bool __realloc = _M_requires_reallocation(__sz);
 	if (__sz < this->size())
-	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
+	  this->_M_invalidate_after_nth(__sz);
 	_Base::resize(__sz);
 	if (__realloc)
 	  this->_M_invalidate_all();
@@ -258,7 +259,7 @@ namespace __debug
       {
 	bool __realloc = _M_requires_reallocation(__sz);
 	if (__sz < this->size())
-	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
+	  this->_M_invalidate_after_nth(__sz);
 	_Base::resize(__sz, __c);
 	if (__realloc)
 	  this->_M_invalidate_all();
@@ -270,7 +271,7 @@ namespace __debug
       {
 	bool __realloc = _M_requires_reallocation(__sz);
 	if (__sz < this->size())
-	  this->_M_invalidate_if(_After_nth(__sz, _M_base().begin()));
+	  this->_M_invalidate_after_nth(__sz);
 	_Base::resize(__sz, __c);
 	if (__realloc)
 	  this->_M_invalidate_all();
@@ -388,8 +389,7 @@ namespace __debug
       pop_back()
       {
 	__glibcxx_check_nonempty();
-	iterator __victim = end() - 1;
-	__victim._M_invalidate();
+	this->_M_invalidate_if(_Equal(--_Base::end()));
 	_Base::pop_back();
       }
 
@@ -400,13 +400,13 @@ namespace __debug
 	{
 	  __glibcxx_check_insert(__position);
 	  bool __realloc = _M_requires_reallocation(this->size() + 1);
-	  difference_type __offset = __position - begin();
-	  typename _Base::iterator __res = _Base::emplace(__position.base(),
-					    std::forward<_Args>(__args)...);
+	  difference_type __offset = __position.base() - _Base::begin();
+	  _Base_iterator __res = _Base::emplace(__position.base(),
+						std::forward<_Args>(__args)...);
 	  if (__realloc)
 	    this->_M_invalidate_all();
 	  else
-	    this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	    this->_M_invalidate_after_nth(__offset);
 	  _M_update_guaranteed_capacity();
 	  return iterator(__res, this);
 	}
@@ -417,12 +417,12 @@ namespace __debug
       {
 	__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);
+	difference_type __offset = __position.base() - _Base::begin();
+	_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()));
+	  this->_M_invalidate_after_nth(__offset);
 	_M_update_guaranteed_capacity();
 	return iterator(__res, this);
       }
@@ -444,12 +444,12 @@ namespace __debug
       {
 	__glibcxx_check_insert(__position);
 	bool __realloc = _M_requires_reallocation(this->size() + __n);
-	difference_type __offset = __position - begin();
+	difference_type __offset = __position.base() - _Base::begin();
 	_Base::insert(__position.base(), __n, __x);
 	if (__realloc)
 	  this->_M_invalidate_all();
 	else
-	  this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	  this->_M_invalidate_after_nth(__offset);
 	_M_update_guaranteed_capacity();
       }
 
@@ -463,15 +463,15 @@ namespace __debug
 	  /* 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_iterator __old_begin = _M_base().begin();
+	  difference_type __offset = __position.base() - _Base::begin();
 	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
 					   __gnu_debug::__base(__last));
 
 	  if (_M_base().begin() != __old_begin)
 	    this->_M_invalidate_all();
 	  else
-	    this->_M_invalidate_if(_After_nth(__offset, _M_base().begin()));
+	    this->_M_invalidate_after_nth(__offset);
 	  _M_update_guaranteed_capacity();
 	}
 
@@ -479,9 +479,9 @@ namespace __debug
       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()));
+	difference_type __offset = __position.base() - _Base::begin();
+	_Base_iterator __res = _Base::erase(__position.base());
+	this->_M_invalidate_after_nth(__offset);
 	return iterator(__res, this);
       }
 
@@ -492,10 +492,10 @@ namespace __debug
 	// 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()));
+	difference_type __offset = __first.base() - _Base::begin();
+	_Base_iterator __res = _Base::erase(__first.base(),
+						      __last.base());
+	this->_M_invalidate_after_nth(__offset);
 	return iterator(__res, this);
       }
 
@@ -534,6 +534,13 @@ namespace __debug
 	if (this->size() > _M_guaranteed_capacity)
 	  _M_guaranteed_capacity = this->size();
       }
+
+      void
+      _M_invalidate_after_nth(difference_type __n)
+      {
+	typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
+	this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
+      }
     };
 
   template<typename _Tp, typename _Alloc>
diff --git a/libstdc++-v3/src/Makefile.am b/libstdc++-v3/src/Makefile.am
index 958b77430dc..28a924e9f41 100644
--- a/libstdc++-v3/src/Makefile.am
+++ b/libstdc++-v3/src/Makefile.am
@@ -349,6 +349,11 @@ future.lo: future.cc
 future.o: future.cc
 	$(CXXCOMPILE) -std=gnu++0x -c $<
 
+debug.lo: debug.cc
+	$(LTCXXCOMPILE) -std=gnu++0x -c $<
+debug.o: debug.cc
+	$(CXXCOMPILE) -std=gnu++0x -c $<
+
 if GLIBCXX_LDBL_COMPAT
 # Use special rules for compatibility-ldbl.cc compilation, as we need to
 # pass -mlong-double-64.
diff --git a/libstdc++-v3/src/Makefile.in b/libstdc++-v3/src/Makefile.in
index 06e6a8b3957..fe38f37afcd 100644
--- a/libstdc++-v3/src/Makefile.in
+++ b/libstdc++-v3/src/Makefile.in
@@ -925,6 +925,11 @@ future.lo: future.cc
 future.o: future.cc
 	$(CXXCOMPILE) -std=gnu++0x -c $<
 
+debug.lo: debug.cc
+	$(LTCXXCOMPILE) -std=gnu++0x -c $<
+debug.o: debug.cc
+	$(CXXCOMPILE) -std=gnu++0x -c $<
+
 # Use special rules for compatibility-ldbl.cc compilation, as we need to
 # pass -mlong-double-64.
 @GLIBCXX_LDBL_COMPAT_TRUE@compatibility-ldbl.lo: compatibility-ldbl.cc
diff --git a/libstdc++-v3/src/debug.cc b/libstdc++-v3/src/debug.cc
index 9316ed6aea7..188495a3ea8 100644
--- a/libstdc++-v3/src/debug.cc
+++ b/libstdc++-v3/src/debug.cc
@@ -32,16 +32,40 @@
 #include <cctype>
 #include <cstdio>
 #include <cstdlib>
+#include <functional>
 
 using namespace std;
 
 namespace
 {
+  /** Returns different instances of __mutex depending on the passed address
+   *  in order to limit contention without breaking current library binary
+   *  compatibility. */
   __gnu_cxx::__mutex&
-  get_safe_base_mutex()
+  get_safe_base_mutex(void* __address)
   {
-    static __gnu_cxx::__mutex safe_base_mutex;
-    return safe_base_mutex;
+    const size_t mask = 0xf;
+    static __gnu_cxx::__mutex safe_base_mutex[mask + 1];
+    const size_t index = _Hash_impl::hash(__address) & mask;
+    return safe_base_mutex[index];
+  }
+
+  void
+  swap_seq(__gnu_debug::_Safe_sequence_base& __lhs,
+	   __gnu_debug::_Safe_sequence_base& __rhs)
+  {
+    swap(__lhs._M_iterators, __rhs._M_iterators);
+    swap(__lhs._M_const_iterators, __rhs._M_const_iterators);
+    swap(__lhs._M_version, __rhs._M_version);
+    __gnu_debug::_Safe_iterator_base* __iter;
+    for (__iter = __rhs._M_iterators; __iter; __iter = __iter->_M_next)
+      __iter->_M_sequence = &__rhs;
+    for (__iter = __lhs._M_iterators; __iter; __iter = __iter->_M_next)
+      __iter->_M_sequence = &__lhs;
+    for (__iter = __rhs._M_const_iterators; __iter; __iter = __iter->_M_next)
+      __iter->_M_sequence = &__rhs;
+    for (__iter = __lhs._M_const_iterators; __iter; __iter = __iter->_M_next)
+      __iter->_M_sequence = &__lhs;
   }
 } // anonymous namespace
 
@@ -122,15 +146,17 @@ namespace __gnu_debug
       {
 	_Safe_iterator_base* __old = __iter;
 	__iter = __iter->_M_next;
-	__old->_M_detach_single();
+	__old->_M_reset();
       }
+    _M_iterators = 0;
     
     for (_Safe_iterator_base* __iter2 = _M_const_iterators; __iter2;)
       {
 	_Safe_iterator_base* __old = __iter2;
 	__iter2 = __iter2->_M_next;
-	__old->_M_detach_single();
+	__old->_M_reset();
       }
+    _M_const_iterators = 0;
   }
 
   void
@@ -173,32 +199,88 @@ namespace __gnu_debug
   _Safe_sequence_base::
   _M_swap(_Safe_sequence_base& __x)
   {
-    __gnu_cxx::__scoped_lock sentry(_M_get_mutex());
-    swap(_M_iterators, __x._M_iterators);
-    swap(_M_const_iterators, __x._M_const_iterators);
-    swap(_M_version, __x._M_version);
-    _Safe_iterator_base* __iter;
-    for (__iter = _M_iterators; __iter; __iter = __iter->_M_next)
-      __iter->_M_sequence = this;
-    for (__iter = __x._M_iterators; __iter; __iter = __iter->_M_next)
-      __iter->_M_sequence = &__x;
-    for (__iter = _M_const_iterators; __iter; __iter = __iter->_M_next)
-      __iter->_M_sequence = this;
-    for (__iter = __x._M_const_iterators; __iter; __iter = __iter->_M_next)
-      __iter->_M_sequence = &__x;
+    // We need to lock both sequences to swap
+    using namespace __gnu_cxx;
+    __mutex *__this_mutex = &_M_get_mutex();
+    __mutex *__x_mutex = &__x._M_get_mutex();
+    if (__this_mutex == __x_mutex)
+      {
+	__scoped_lock __lock(*__this_mutex);
+	swap_seq(*this, __x);
+      }
+    else
+      {
+	__scoped_lock __l1(__this_mutex < __x_mutex
+			     ? *__this_mutex : *__x_mutex);
+	__scoped_lock __l2(__this_mutex < __x_mutex
+			     ? *__x_mutex : *__this_mutex);
+	swap_seq(*this, __x);
+      }
   }
 
   __gnu_cxx::__mutex&
   _Safe_sequence_base::
   _M_get_mutex() throw ()
-  { return get_safe_base_mutex(); }
+  { return get_safe_base_mutex(this); }
+
+  void
+  _Safe_sequence_base::
+  _M_attach(_Safe_iterator_base* __it, bool __constant)
+  {
+    __gnu_cxx::__scoped_lock sentry(_M_get_mutex());
+    _M_attach_single(__it, __constant);
+  }
+
+  void
+  _Safe_sequence_base::
+  _M_attach_single(_Safe_iterator_base* __it, bool __constant) throw ()
+  {
+    _Safe_iterator_base*& __its =
+      __constant ? _M_const_iterators : _M_iterators;
+    __it->_M_next = __its;
+    if (__it->_M_next)
+      __it->_M_next->_M_prior = __it;
+    __its = __it;
+  }
+
+  void
+  _Safe_sequence_base::
+  _M_detach(_Safe_iterator_base* __it)
+  {
+    // Remove __it from this sequence's list
+    __gnu_cxx::__scoped_lock sentry(_M_get_mutex());
+    _M_detach_single(__it);
+  }
+
+  void
+  _Safe_sequence_base::
+  _M_detach_single(_Safe_iterator_base* __it) throw ()
+  {
+    // Remove __it from this sequence's list
+    if (__it->_M_prior)
+      __it->_M_prior->_M_next = __it->_M_next;
+    if (__it->_M_next)
+      __it->_M_next->_M_prior = __it->_M_prior;
+	
+    if (_M_const_iterators == __it)
+      _M_const_iterators = __it->_M_next;
+    if (_M_iterators == __it)
+      _M_iterators = __it->_M_next;
+  }
 
   void
   _Safe_iterator_base::
   _M_attach(_Safe_sequence_base* __seq, bool __constant)
   {
-    __gnu_cxx::__scoped_lock sentry(_M_get_mutex());
-    _M_attach_single(__seq, __constant);
+    _M_detach();
+    
+    // Attach to the new sequence (if there is one)
+    if (__seq)
+      {
+	_M_sequence = __seq;
+	_M_version = _M_sequence->_M_version;
+	_M_sequence->_M_attach(this, __constant);
+      }
   }
   
   void
@@ -212,21 +294,7 @@ namespace __gnu_debug
       {
 	_M_sequence = __seq;
 	_M_version = _M_sequence->_M_version;
-	_M_prior = 0;
-	if (__constant)
-	  {
-	    _M_next = _M_sequence->_M_const_iterators;
-	    if (_M_next)
-	      _M_next->_M_prior = this;
-	    _M_sequence->_M_const_iterators = this;
-	  }
-	else
-	  {
-	    _M_next = _M_sequence->_M_iterators;
-	    if (_M_next)
-	      _M_next->_M_prior = this;
-	    _M_sequence->_M_iterators = this;
-	  }
+	_M_sequence->_M_attach_single(this, __constant);
       }
   }
 
@@ -234,8 +302,12 @@ namespace __gnu_debug
   _Safe_iterator_base::
   _M_detach()
   {
-    __gnu_cxx::__scoped_lock sentry(_M_get_mutex());
-    _M_detach_single();
+    if (_M_sequence)
+      {
+	_M_sequence->_M_detach(this);
+      }
+
+    _M_reset();
   }
 
   void
@@ -244,18 +316,16 @@ namespace __gnu_debug
   {
     if (_M_sequence)
       {
-	// Remove us from this sequence's list
-	if (_M_prior) 
-	  _M_prior->_M_next = _M_next;
-	if (_M_next)  
-	  _M_next->_M_prior = _M_prior;
-	
-	if (_M_sequence->_M_const_iterators == this)
-	  _M_sequence->_M_const_iterators = _M_next;
-	if (_M_sequence->_M_iterators == this)
-	  _M_sequence->_M_iterators = _M_next;
+	_M_sequence->_M_detach_single(this);
       }
 
+    _M_reset();
+  }
+
+  void
+  _Safe_iterator_base::
+  _M_reset() throw ()
+  {
     _M_sequence = 0;
     _M_version = 0;
     _M_prior = 0;
@@ -278,7 +348,7 @@ namespace __gnu_debug
   __gnu_cxx::__mutex&
   _Safe_iterator_base::
   _M_get_mutex() throw ()
-  { return get_safe_base_mutex(); }
+  { return get_safe_base_mutex(_M_sequence); }
 
   void
   _Error_formatter::_Parameter::
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/clear.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/clear.cc
new file mode 100644
index 00000000000..23ea900b87d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/clear.cc
@@ -0,0 +1,43 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// Check that iterators ownership is correctly manage on swap.
+#include <forward_list>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+  std::forward_list<int> fl{1, 2, 3};
+
+  auto before = fl.before_begin();
+  auto end = fl.end();
+  fl.clear();
+
+  VERIFY( end == fl.end() );
+  VERIFY( before == fl.before_begin() );
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/move_constructor.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/move_constructor.cc
new file mode 100644
index 00000000000..4a93666b224
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/move_constructor.cc
@@ -0,0 +1,43 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// Check that iterators ownership is correctly manage on swap.
+#include <forward_list>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+  std::forward_list<int> fl1{1, 3, 5};
+
+  auto flit = fl1.before_begin();
+  std::forward_list<int> fl2(std::move(fl1));
+
+#if !_GLIBCXX_DEBUG
+  VERIFY( flit == fl1.before_begin() );
+#endif
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after.cc
new file mode 100644
index 00000000000..60297551dcd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after.cc
@@ -0,0 +1,44 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// Check that iterators ownership is correctly manage on swap.
+#include <forward_list>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+  std::forward_list<int> fl1{1, 2, 3};
+  std::forward_list<int> fl2{4, 5, 6};
+
+  auto before = fl1.before_begin();
+  auto end = fl1.end();
+  fl2.splice_after(fl2.before_begin(), std::move(fl1));
+
+  VERIFY( before == fl1.before_begin() );
+  VERIFY( end == fl1.end() );
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after1.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after1.cc
new file mode 100644
index 00000000000..3ee7f689aeb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after1.cc
@@ -0,0 +1,36 @@
+// { dg-options "-std=gnu++0x" }
+// { dg-require-debug-mode "" }
+// { dg-do run { xfail *-*-* } }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <forward_list>
+
+void
+test01()
+{
+  std::forward_list<int> fl1{1, 2, 3};
+  fl1.splice_after(fl1.begin(), std::move(fl1));
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after2.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after2.cc
new file mode 100644
index 00000000000..6a7fcfb22c2
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after2.cc
@@ -0,0 +1,38 @@
+// { dg-options "-std=gnu++0x" }
+// { dg-require-debug-mode "" }
+// { dg-do run { xfail *-*-* } }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <forward_list>
+
+void
+test01()
+{
+  std::forward_list<int> fl1{1, 2, 3};
+  std::forward_list<int> fl2{1, 2, 3};
+
+  fl1.splice_after(fl1.before_begin(), std::move(fl2), fl1.begin());
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after3.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after3.cc
new file mode 100644
index 00000000000..55e50dc0511
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after3.cc
@@ -0,0 +1,38 @@
+// { dg-options "-std=gnu++0x" }
+// { dg-require-debug-mode "" }
+// { dg-do run { xfail *-*-* } }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <forward_list>
+
+void
+test01()
+{
+  std::forward_list<int> fl1{1, 2, 3};
+  std::forward_list<int> fl2{1, 2, 3};
+
+  fl1.splice_after(fl1.before_begin(), std::move(fl2), fl2.end());
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after4.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after4.cc
new file mode 100644
index 00000000000..4c161906e0a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after4.cc
@@ -0,0 +1,39 @@
+// { dg-options "-std=gnu++0x" }
+// { dg-require-debug-mode "" }
+// { dg-do run { xfail *-*-* } }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <forward_list>
+
+void
+test01()
+{
+  std::forward_list<int> fl1{1, 2, 3};
+  std::forward_list<int> fl2{1, 2, 3};
+
+  fl1.splice_after(fl1.before_begin(),
+		   std::move(fl2), ++(++fl2.begin()), ++fl2.begin());
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/swap.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/swap.cc
new file mode 100644
index 00000000000..0105791bedc
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/swap.cc
@@ -0,0 +1,83 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without Pred the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// Check that iterators ownership is correctly manage on swap.
+#include <vector>
+#include <forward_list>
+#include <iostream>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+  std::forward_list<int> fl1{1, 3, 5};
+  std::forward_list<int> fl2{2, 4, 6};
+
+  std::vector<std::forward_list<int>::iterator> fl1_its;
+  fl1_its.push_back(fl1.before_begin());
+  for (std::forward_list<int>::iterator it = fl1.begin();
+       it != fl1.end(); ++it)
+    {
+      fl1_its.push_back(it);
+    }
+  fl1_its.push_back(fl1.end());
+
+  std::vector<std::forward_list<int>::iterator> fl2_its;
+  fl2_its.push_back(fl2.before_begin());
+  for (std::forward_list<int>::iterator it = fl2.begin();
+       it != fl2.end(); ++it)
+    {
+      fl2_its.push_back(it);
+    }
+  fl2_its.push_back(fl2.end());
+
+  fl1.swap(fl2);
+
+  auto fit = fl1.before_begin();
+  // before-begin iterator is not transfered:
+  // TODO: Validate with LWG group how before begin should be
+  // treated.
+#if !_GLIBCXX_DEBUG
+  VERIFY( fit == fl1_its[0] );
+#endif
+  // All others are, even paste-the-end one:
+  for (size_t i = 1; i != fl2_its.size(); ++i)
+  {
+    VERIFY( ++fit == fl2_its[i] );
+  }
+
+  fit = fl2.before_begin();
+  // TODO: Validate with LWG group how before begin should be
+  // treated.
+#if !_GLIBCXX_DEBUG
+  VERIFY( fit == fl2_its[0] );
+#endif
+  for (size_t i = 1; i != fl1_its.size(); ++i)
+  {
+    VERIFY( ++fit == fl1_its[i] );
+  }
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/debug/multithreaded_swap.cc b/libstdc++-v3/testsuite/23_containers/vector/debug/multithreaded_swap.cc
new file mode 100644
index 00000000000..b2a50aa21c8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/debug/multithreaded_swap.cc
@@ -0,0 +1,100 @@
+// { dg-do run { target *-*-freebsd* *-*-netbsd* *-*-linux* *-*-solaris* *-*-cygwin *-*-darwin* alpha*-*-osf* mips-sgi-irix6* } }
+// { dg-options " -std=gnu++0x -pthread" { target *-*-freebsd* *-*-netbsd* *-*-linux* alpha*-*-osf* mips-sgi-irix6* } }
+// { dg-options " -std=gnu++0x -pthreads" { target *-*-solaris* } }
+// { dg-options " -std=gnu++0x " { target *-*-cygwin *-*-darwin* } }
+// { dg-require-cstdint "" }
+// { dg-require-gthreads "" }
+// { dg-require-debug-mode "" }
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+//
+
+// This test check for potential deadlock when swaping sequences in debug
+// mode as it requires acquiring 2 locks at the same time.
+
+#include <vector>
+#include <thread>
+#include <functional>
+#include <testsuite_hooks.h>
+
+// The following function mimic the one in src/debug.cc to associate a mutex
+// to a given safe sequence instance.
+size_t
+get_index(std::vector<int>& v)
+{
+  const size_t mask = 0xf;
+  // We have to check the address of the internal safe sequence that starts
+  // after the normal vector memory footprint that is to say a 3 pointers
+  // offset:
+  void* __address = reinterpret_cast<char*>(&v) + 3 * sizeof(void*);
+  return std::_Hash_impl::hash(__address) & mask;
+}
+
+void test01()
+{
+  using namespace std;
+  bool test __attribute__((unused)) = true;
+  vector<int> v1, v2;
+  vector<shared_ptr<vector<int> > > vs;
+  vector<int> *pv3 = 0, *pv4 = 0;
+  const int nb_attempts = 100;
+  for (int i = 0; i != nb_attempts; ++i)
+    {
+      vs.push_back(shared_ptr<vector<int> >(new vector<int>()));
+      if (!pv3)
+	{
+	  if (get_index(*vs.back()) == get_index(v1))
+	    pv3 = vs.back().get();
+	}
+      else if (!pv4)
+	{
+	  if (get_index(*vs.back()) == get_index(v2))
+	    {
+	      pv4 = vs.back().get();
+	      break;
+	    }
+	}
+    }
+
+  if (!pv3 || !pv4)
+    // Maybe an other time...
+    return;
+
+  vector<int> &v3 = *pv3, &v4 = *pv4;
+
+  // v1 and v3 shares the same mutex instance, like v2 and v4
+  // thread t1 lock v1 and v2
+  thread t1([&v1, &v2]()
+    {
+      for (int i = 0; i != 1000; ++i)
+	v1.swap(v2);
+    });
+  // thread t2 lock v4 and v3
+  thread t2([&v3, &v4]()
+    {
+      for (int i = 0; i != 1000; ++i)
+	v4.swap(v3);
+    });
+  t2.join();
+  t1.join();
+}
+
+int main()
+{
+  test01();
+  return 0;
+}