PR libstdc++/68222 Hide safe iterator operators

Message ID 5b2fbf84-6530-8aa8-0730-e892e681a12f@gmail.com
State New
Headers show
Series
  • PR libstdc++/68222 Hide safe iterator operators
Related show

Commit Message

François Dumont Aug. 2, 2018, 8:16 p.m.
Hi

     Here is a patch to avoid definition of invalid operators on the 
Debug mode safe iterator type depending on its category.

     Even if it is limited to the Debug mode code I would like to have a 
feedback before committing. Especially on the following points:

- _Safe_tagged_iterator: Is the name ok ?

- Inheritance between the different _Safe_tagged_iterator 
instantiations. I am already working on making the operators friends as 
we discuss in another thread so I might review this design at this moment.

- Are concept checks I added to testsuite_containers.h citerator ok ?

     This patch also does some cleanup on Debug functions. 
__check_dereferenceable was not used (anymore maybe) so I removed it. I 
also prefer to take iterator by value in the fallback implementations 
like it is done in std algos. Only _Safe_tagged_iterator are taken by 
lvalue ref as they are quite expensive to copy (mutex lock).

     I also attach the ChangeLog entry which is quite big.

Tested under Linux x86_64 Debug mode.

François
2018-08-03  François Dumont  <fdumont@gcc.gnu.org>

	* include/debug/safe_iterator.h
	(_Safe_tagged_iterator<_It, _Sq, _Cat =
	typename std::iterator_traits<_It>::iterator_category>): New.
	(_Safe_iterator<_It, _Sq>::operator++()): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::forward_iterator_tag>
	::operator++()): ...here.
	(_Safe_iterator<_It, _Sq>::operator++(int)): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::forward_iterator_tag>
	::operator++(int)): ...here.
	(_Safe_iterator<_It, _Sq>::operator--()): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::bidirectional_iterator_tag>
	::operator--()): ...here.
	(_Safe_iterator<_It, _Sq>::operator--(int)): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::bidirectional_iterator_tag>
	::operator--(int)): ...here.
	(_Safe_iterator<_It, _Sq>::operator[](const difference_type&)): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator[](const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq>::operator+=(const difference_type&)): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator+=(const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq>::operator+(const difference_type&)): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator+(const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq>::operator-=(const difference_type&)): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator-=(const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq>::operator-(const difference_type&)): Move...
	(_Safe_tagged_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator-(const difference_type&)): ...here.
	(operator==(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator==(const _Safe_tagged_iterator<>&,
	const _Safe_tagged_iterator<>&): ...that.
	(operator==(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator==(const _Safe_tagged_iterator<>&,
	const _Safe_tagged_iterator<>&): ...that.
	(operator!=(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator!=(const _Safe_tagged_iterator<>&,
	const _Safe_tagged_iterator<>&): ...that.
	(operator<(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator<(const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&,
		const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&)): ...that.
	(operator<=(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator<=(const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&,
		const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&)): ...that.
	(operator>(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator>(const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&,
		const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&)): ...that.
	(operator>=(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator>=(const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&,
		const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&)): ...that.
	(operator-(const _Safe_iterator<>&, const _Safe_iterator<>&)): Replace
	with...
	(operator-(const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&,
		const _Safe_tagged_iterator<_It, _Sq,
		std::random_access_iterator_tag>&)): ...that.
	(operator+(const difference_type&, const _Safe_iterator<>&)): Replace
	with...
	(operator+(const difference_type&,
		const _Safe_tagged_iterator<_It, _Sq,
	std::random_access_iterator_tag>&)): ...that.
	* include/debug/deque
	(std::__debug::deque<>::normal_type): New typedef.
	(std::__debug::deque<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::deque<>::const_iterator): Likewise.
	* include/debug/forward_list
	(std::__debug::forward_list<>::normal_type): New typedef.
	(std::__debug::forward_list<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::forward_list<>::const_iterator): Likewise.
	* include/debug/list
	(std::__debug::list<>::normal_type): New typedef.
	(std::__debug::list<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::list<>::const_iterator): Likewise.
	* include/debug/map.h
	(std::__debug::map<>::normal_type): New typedef.
	(std::__debug::map<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::map<>::const_iterator): Likewise.
	* include/debug/multimap.h
	(std::__debug::multimap<>::normal_type): New typedef.
	(std::__debug::multimap<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::multimap<>::const_iterator): Likewise.
	* include/debug/set.h
	(std::__debug::set<>::normal_type): New typedef.
	(std::__debug::set<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::set<>::const_iterator): Likewise.
	* include/debug/multiset.h
	(std::__debug::multiset<>::normal_type): New typedef.
	(std::__debug::multiset<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::multiset<>::const_iterator): Likewise.
	* include/debug/string
	(std::__debug::basic_string<>::normal_type): New typedef.
	(std::__debug::basic_string<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::basic_string<>::const_iterator): Likewise.
	* include/debug/unordered_map
	(std::__debug::unordered_map<>::normal_type): New typedef.
	(std::__debug::unordered_map<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::unordered_map<>::const_iterator): Likewise.
	(std::__debug::unordered_multimap<>::normal_type): New typedef.
	(std::__debug::unordered_multimap<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::unordered_multimap<>::const_iterator): Likewise.
	* include/debug/unordered_set
	(std::__debug::unordered_set<>::normal_type): New typedef.
	(std::__debug::unordered_set<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::unordered_set<>::const_iterator): Likewise.
	(std::__debug::unordered_multiset<>::normal_type): New typedef.
	(std::__debug::unordered_multiset<>::iterator): Use _Safe_tagged_iterator.
	(std::__debug::unordered_multiset<>::const_iterator): Likewise.
	* include/debug/formatter.h: Adapt.
	* include/debug/helper_functions.h
	(__get_distance<>(const _Safe_tagged_iterator<>&,
	const _Safe_tagged_iterator<>&)): New definition.
	(__get_distance<>(const _Safe_local_iterator<>&,
	const _Safe_local_iterator<>&)): Likewise.
	(__valid_range(const _Safe_tagged_iterator<>&,
	const _Safe_tagged_iterator<>&, typename _Distance_traits<>::__type&):
	Likewise.
	(__valid_range(const _Safe_local_iterator<>&,
	const _Safe_local_iterator<>&, typename _Distance_traits<>::__type&):
	Likewise.
	(__can_advance): Adapt.
	(__is_safe_random_iterator<>): Remove.
	* include/debug/functions.h: Include <bits/stl_iterator.h>.
	(__check_dereferenceable): Delete.
	(__foreign_iterator_aux4, __foreign_iterator_aux3): Adapt.
	(__foreign_iterator_aux2, __foreign_iterator_aux): Adapt.
	(__foreign_iterator): Adapt.
	* include/debug/stl_iterator.h
	(__is_safe_random_iterator<std::reverse_iterator<>>): Remove.
	(__base(const std::reverse_iterator<_Safe_tagged_iterator<_It, _Sq,
	std::random_access_iterator_tag>)): New overload.
	(__niter_base): Adapt.
	* testsuite/util/testsuite_containers.h:
	Include <bits/boost_concept_check.h>.
	(iterator_concept_checks<_It, _Mutable, _Category>): New.
	(citerator<_Cont>::forward_members::forward_members()): Instantiate
	latter for container iterator and const_iterator.
	* testsuite/23_containers/list/68222_neg.cc: New.
	* testsuite/23_containers/vector/cons/destructible_debug_neg.cc: Adapt
	line number.

Comments

Jonathan Wakely Aug. 7, 2018, 1:47 p.m. | #1
On 02/08/18 22:16 +0200, François Dumont wrote:
>Hi
>
>    Here is a patch to avoid definition of invalid operators on the 
>Debug mode safe iterator type depending on its category.
>
>    Even if it is limited to the Debug mode code I would like to have 
>a feedback before committing. Especially on the following points:
>
>- _Safe_tagged_iterator: Is the name ok ?

Hmm, maybe "strict" instead of tagged?

But do we need a new name? Can we just change _Safe_iterator instead
of adding a new type?

Where is _Safe_iterator still used? Just local iterators in unordered
containers?  Is it OK to remove most of the functions that used to
support it? (__niter_base etc).

Could we add a new type for the local iterators, and just change
_Safe_iterator directly so it doesn't expose unsupported operations?

That would make the patch *much* smaller, as you wouldn't need to
change all the uses of _Safe_iterator.


Another approach would be to use mixins to expose the operations:

template<typename _Iter, typename _Cat>
struct _Safe_iterator_mixin<_Iter, _Cat>
{
  typename iterator_traits<_Iter>::reference
  operator*()
  { return static_cast<_Iter*>(this)->_M_deref(); }
};

template<typename _Iter, typename _Cat>
struct _Safe_iterator_mixin<_Iter, forward_iterator_tag>
{
  _Iter& operator++()
  { return static_cast<_Iter*>(this)->_M_preinc(); }
  _Iter operator++(int)
  { return static_cast<_Iter*>(this)->_M_postinc(); }
};

template<typename _Iter, typename _Cat>
struct _Safe_iterator_mixin<_Iter, bidirectional_iterator_tag>
{
  _Iter& operator--()
  { return static_cast<_Iter*>(this)->_M_predec(); }
  _Iter operator--(int)
  { return static_cast<_Iter*>(this)->_M_postdec(); }
};

etc.

then in _Safe_iterator rename the operator functions, so operator*
becomes _M_deref, operator++ becomes _M_preinc etc. and then derive
from _Safe_iterator_mixin which declares the operators.


>- Inheritance between the different _Safe_tagged_iterator 
>instantiations. I am already working on making the operators friends 
>as we discuss in another thread so I might review this design at this 
>moment.
>
>- Are concept checks I added to testsuite_containers.h citerator ok ?

Yes, they look useful.

>    This patch also does some cleanup on Debug functions. 
>__check_dereferenceable was not used (anymore maybe) so I removed it. 

It would have made the patch a bit more manageable to keep that as a
separate patch, but nevermind.

>diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
>index 93b82cf..213e23b 100644
>--- a/libstdc++-v3/include/debug/deque
>+++ b/libstdc++-v3/include/debug/deque
>@@ -57,12 +57,14 @@ namespace __debug
>       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
> 
>     public:
>+      typedef _Base					normal_type;

normal_type is not a reserved name, so can't be used.


>diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
>index f20b000..fd20160 100644
>--- a/libstdc++-v3/include/debug/stl_iterator.h
>+++ b/libstdc++-v3/include/debug/stl_iterator.h
>@@ -75,12 +76,6 @@ namespace __gnu_debug
> #else
>   template<typename _Iterator>
>     inline auto
>-    __base(const std::reverse_iterator<_Iterator>& __it)
>-    -> decltype(std::__make_reverse_iterator(__base(__it.base())))
>-    { return std::__make_reverse_iterator(__base(__it.base())); }

This removal doesn't seem to be mentioned in the ChangeLog:

>	* include/debug/stl_iterator.h
>	(__is_safe_random_iterator<std::reverse_iterator<>>): Remove.
>	(__base(const std::reverse_iterator<_Safe_tagged_iterator<_It, _Sq,
>	std::random_access_iterator_tag>)): New overload.
Jonathan Wakely Aug. 7, 2018, 10:39 p.m. | #2
On 02/08/18 22:16 +0200, François Dumont wrote:
>+#if __cplusplus >= 201103L
>+      /** @brief Copy assignment. */
>+      _Safe_tagged_iterator&
>+      operator=(const _Safe_tagged_iterator&) = default;
>+
>+      /** @brief Move assignment. */
>+      _Safe_tagged_iterator&
>+      operator=(_Safe_tagged_iterator&&) = default;
>+#else
>+      /**
>+       * @brief Copy assignment.
>+       */
>+      _Safe_tagged_iterator&
>+      operator=(const _Safe_tagged_iterator& __x) _GLIBCXX_NOEXCEPT

This _GLIBCXX_NOEXCEPT can be removed, because it expands to nothing
for C++98 mode.


>+      {
>+	_Safe_base::operator=(__x);
>+	return *this;
>+      }
>+#endif
Jonathan Wakely Aug. 7, 2018, 10:41 p.m. | #3
On 07/08/18 14:47 +0100, Jonathan Wakely wrote:
>On 02/08/18 22:16 +0200, François Dumont wrote:
>>Hi
>>
>>    Here is a patch to avoid definition of invalid operators on the 
>>Debug mode safe iterator type depending on its category.
>>
>>    Even if it is limited to the Debug mode code I would like to 
>>have a feedback before committing. Especially on the following 
>>points:
>>
>>- _Safe_tagged_iterator: Is the name ok ?
>
>Hmm, maybe "strict" instead of tagged?
>
>But do we need a new name? Can we just change _Safe_iterator instead
>of adding a new type?
>
>Where is _Safe_iterator still used? Just local iterators in unordered
>containers?  Is it OK to remove most of the functions that used to
>support it? (__niter_base etc).
>
>Could we add a new type for the local iterators, and just change
>_Safe_iterator directly so it doesn't expose unsupported operations?
>
>That would make the patch *much* smaller, as you wouldn't need to
>change all the uses of _Safe_iterator.
>
>
>Another approach would be to use mixins to expose the operations:
>
>template<typename _Iter, typename _Cat>
>struct _Safe_iterator_mixin<_Iter, _Cat>
>{
> typename iterator_traits<_Iter>::reference
> operator*()
> { return static_cast<_Iter*>(this)->_M_deref(); }
>};
>
>template<typename _Iter, typename _Cat>
>struct _Safe_iterator_mixin<_Iter, forward_iterator_tag>
>{
> _Iter& operator++()
> { return static_cast<_Iter*>(this)->_M_preinc(); }
> _Iter operator++(int)
> { return static_cast<_Iter*>(this)->_M_postinc(); }
>};
>
>template<typename _Iter, typename _Cat>
>struct _Safe_iterator_mixin<_Iter, bidirectional_iterator_tag>
>{
> _Iter& operator--()
> { return static_cast<_Iter*>(this)->_M_predec(); }
> _Iter operator--(int)
> { return static_cast<_Iter*>(this)->_M_postdec(); }
>};
>
>etc.
>
>then in _Safe_iterator rename the operator functions, so operator*
>becomes _M_deref, operator++ becomes _M_preinc etc. and then derive
>from _Safe_iterator_mixin which declares the operators.

FWIW I think your proposal with partial specializations for each
iterator category is probably better than this mixins idea (although I
think it requires a lot more code to implement it).

But I would like to know if it's possible to just change
_Safe_iterator instead of introducing a new _Safe_tagged_iterator
type.
François Dumont Aug. 18, 2018, 8:31 p.m. | #4
Here is the new proposal. It is indeed possible to keep _Safe_iterator 
and just add a _Category template parameter to it.

I introduce a friend declaration to access container _Base nested 
typedef from the safe iterator.

I review the safe const_iterator constructor from safe iterator. I now 
check if we are in the a const_iterator context so that compilers don't 
even try to consider this constructor when we are in an iterator context.

I adapted _Safe_local_iterator the same way to keep consistency with 
_Safe_iterator and because I find the new design cleaner. It also fixes 
the same problem I fixed on _Safe_iterator when checking it iterator has 
been initialized using _MutableIterator() rather than _Iterator().

I stop overloading __get_distance for safe iterators or safe local 
iterators, it was useless. I prefer to introduce similar functions as 
members. Same for __get_distance_from_begin or __get_distance_to_end, 
and I move code in safe_iterator.tcc.

Tested under Linux x86_64 debug mode.

Ok to commit ?

François
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 93b82cf..a6047db 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -56,6 +56,9 @@ namespace __debug
       typedef typename _Base::iterator		_Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
index 7b3c30b..99f53c0 100644
--- a/libstdc++-v3/include/debug/formatter.h
+++ b/libstdc++-v3/include/debug/formatter.h
@@ -76,7 +76,7 @@ namespace __gnu_debug
 
   class _Safe_sequence_base;
 
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     class _Safe_iterator;
 
   template<typename _Iterator, typename _Sequence>
@@ -264,8 +264,8 @@ namespace __gnu_debug
 	_M_variant._M_string._M_value = __value;
       }
 
-      template<typename _Iterator, typename _Sequence>
-	_Parameter(_Safe_iterator<_Iterator, _Sequence> const& __it,
+      template<typename _Iterator, typename _Sequence, typename _Category>
+	_Parameter(_Safe_iterator<_Iterator, _Sequence, _Category> const& __it,
 		   const char* __name, _Is_iterator)
 	: _M_kind(__iterator),  _M_variant()
 	{
@@ -379,9 +379,9 @@ namespace __gnu_debug
 	    = _S_reverse_state(_M_variant._M_iterator._M_state);
 	}
 
-      template<typename _Iterator, typename _Sequence>
-	_Parameter(std::reverse_iterator<_Safe_iterator<_Iterator,
-							_Sequence>> const& __it,
+      template<typename _Iterator, typename _Sequence, typename _Category>
+	_Parameter(std::reverse_iterator<_Safe_iterator<_Iterator, _Sequence,
+							_Category>> const& __it,
 	  const char* __name, _Is_iterator)
 	: _Parameter(__it.base(), __name, _Is_iterator{})
 	{
@@ -397,9 +397,9 @@ namespace __gnu_debug
 	: _Parameter(__it.base(), __name, _Is_iterator{})
 	{ _M_variant._M_iterator._M_type = _GLIBCXX_TYPEID(__it); }
 
-      template<typename _Iterator, typename _Sequence>
-	_Parameter(std::move_iterator<_Safe_iterator<_Iterator,
-						     _Sequence>> const& __it,
+      template<typename _Iterator, typename _Sequence, typename _Category>
+	_Parameter(std::move_iterator<_Safe_iterator<_Iterator, _Sequence,
+						     _Category>> const& __it,
 	  const char* __name, _Is_iterator)
 	: _Parameter(__it.base(), __name, _Is_iterator{})
       {
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index 633af1a..e5ac09e8 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -193,6 +193,9 @@ namespace __debug
       typedef typename _Base::iterator		_Base_iterator;
       typedef typename _Base::const_iterator	_Base_const_iterator;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       typedef typename _Base::reference		reference;
       typedef typename _Base::const_reference	const_reference;
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index ce501f2..21b60df 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -31,7 +31,9 @@
 
 #include <bits/move.h>		// for __addressof
 #include <bits/stl_function.h>	// for less
+
 #if __cplusplus >= 201103L
+# include <bits/stl_iterator.h>	// for __miter_base
 # include <type_traits>		// for is_lvalue_reference and conditional.
 #endif
 
@@ -64,19 +66,6 @@ namespace __gnu_debug
     __check_singular(const _Tp* __ptr)
     { return __ptr == 0; }
 
-  /** Assume that some arbitrary iterator is dereferenceable, because we
-      can't prove that it isn't. */
-  template<typename _Iterator>
-    inline bool
-    __check_dereferenceable(const _Iterator&)
-    { return true; }
-
-  /** Non-NULL pointers are dereferenceable. */
-  template<typename _Tp>
-    inline bool
-    __check_dereferenceable(const _Tp* __ptr)
-    { return __ptr; }
-
   /* Checks that [first, last) is a valid range, and then returns
    * __first. This routine is useful when we can't use a separate
    * assertion statement because, e.g., we are in a constructor.
@@ -95,9 +84,10 @@ namespace __gnu_debug
     }
 
   /* Handle the case where __other is a pointer to _Sequence::value_type. */
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     inline bool
-    __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator_aux4(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
 	const typename _Sequence::value_type* __other)
     {
       typedef const typename _Sequence::value_type* _PointerType;
@@ -116,17 +106,19 @@ namespace __gnu_debug
     }
 
   /* Fallback overload for when we can't tell, assume it is valid. */
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     inline bool
-    __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...)
+    __foreign_iterator_aux4(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>&, ...)
     { return true; }
 
   /* Handle sequences with contiguous storage */
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
-			    const _InputIterator& __other,
-			    const _InputIterator& __other_end,
+    __foreign_iterator_aux3(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+	const _InputIterator& __other, const _InputIterator& __other_end,
 	std::__true_type)
     {
       if (__other == __other_end)
@@ -137,34 +129,44 @@ namespace __gnu_debug
     }
 
   /* Handle non-contiguous containers, assume it is valid. */
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&,
+    __foreign_iterator_aux3(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>&,
 	const _InputIterator&, const _InputIterator&,
 	std::__false_type)
     { return true; }
 
   /** Handle debug iterators from the same type of container. */
-  template<typename _Iterator, typename _Sequence, typename _OtherIterator>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _OtherIterator>
     inline bool
-    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
-		const _Safe_iterator<_OtherIterator, _Sequence>& __other,
-		const _Safe_iterator<_OtherIterator, _Sequence>&)
+    __foreign_iterator_aux2(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+	const _Safe_iterator<_OtherIterator, _Sequence, _Category>& __other,
+	const _Safe_iterator<_OtherIterator, _Sequence, _Category>&)
     { return __it._M_get_sequence() != __other._M_get_sequence(); }
 
   /** Handle debug iterators from different types of container. */
-  template<typename _Iterator, typename _Sequence, typename _OtherIterator,
-	   typename _OtherSequence>
-    inline bool
-    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
-		const _Safe_iterator<_OtherIterator, _OtherSequence>&,
-		const _Safe_iterator<_OtherIterator, _OtherSequence>&)
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _OtherIterator, typename _OtherSequence,
+	   typename _OtherCategory>
+    inline bool
+    __foreign_iterator_aux2(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>&,
+	const _Safe_iterator<_OtherIterator, _OtherSequence,
+			     _OtherCategory>&,
+	const _Safe_iterator<_OtherIterator, _OtherSequence,
+			     _OtherCategory>&)
     { return true; }
 
   /* Handle non-debug iterators. */
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator_aux2(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
 	const _InputIterator& __other,
 	const _InputIterator& __other_end)
     {
@@ -181,18 +183,20 @@ namespace __gnu_debug
     }
 
   /* Handle the case where we aren't really inserting a range after all */
-  template<typename _Iterator, typename _Sequence, typename _Integral>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _Integral>
     inline bool
-    __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
-			   _Integral, _Integral,
-			   std::__true_type)
+    __foreign_iterator_aux(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>&,
+	_Integral, _Integral, std::__true_type)
     { return true; }
 
   /* Handle all iterators. */
-  template<typename _Iterator, typename _Sequence,
+  template<typename _Iterator, typename _Sequence, typename _Category,
 	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator_aux(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
 	_InputIterator __other, _InputIterator __other_end,
 	std::__false_type)
     {
@@ -201,10 +205,11 @@ namespace __gnu_debug
 				   std::__miter_base(__other_end));
     }
 
-  template<typename _Iterator, typename _Sequence,
+  template<typename _Iterator, typename _Sequence, typename _Category,
 	   typename _InputIterator>
     inline bool
-    __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
 	_InputIterator __other, _InputIterator __other_end)
     {
       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
diff --git a/libstdc++-v3/include/debug/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h
index 2073df9..21d9693 100644
--- a/libstdc++-v3/include/debug/helper_functions.h
+++ b/libstdc++-v3/include/debug/helper_functions.h
@@ -37,9 +37,14 @@
 
 namespace __gnu_debug
 {
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     class _Safe_iterator;
 
+#if __cplusplus >= 201103L
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_local_iterator;
+#endif
+
   /** The precision to which we can calculate the distance between
    *  two iterators.
    */
@@ -83,13 +88,13 @@ namespace __gnu_debug
   */
   template<typename _Iterator>
     inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs,
+    __get_distance(_Iterator __lhs, _Iterator __rhs,
 		   std::random_access_iterator_tag)
     { return std::make_pair(__rhs - __lhs, __dp_exact); }
 
   template<typename _Iterator>
     inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs,
+    __get_distance(_Iterator __lhs, _Iterator __rhs,
 		   std::input_iterator_tag)
     {
       if (__lhs == __rhs)
@@ -100,7 +105,7 @@ namespace __gnu_debug
 
   template<typename _Iterator>
     inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs)
+    __get_distance(_Iterator __lhs, _Iterator __rhs)
     { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); }
 
   /** We say that integral types for a valid range, and defer to other
@@ -109,7 +114,7 @@ namespace __gnu_debug
   */
   template<typename _Integral>
     inline bool
-    __valid_range_aux(const _Integral&, const _Integral&,
+    __valid_range_aux(_Integral, _Integral,
 		      typename _Distance_traits<_Integral>::__type& __dist,
 		      std::__true_type)
     {
@@ -117,13 +122,12 @@ namespace __gnu_debug
       return true;
     }
 
-  /** We have iterators, so figure out what kind of iterators that are
+  /** We have iterators, so figure out what kind of iterators they are
    *  to see if we can check the range ahead of time.
   */
   template<typename _InputIterator>
     inline bool
-    __valid_range_aux(const _InputIterator& __first,
-		      const _InputIterator& __last,
+    __valid_range_aux(_InputIterator __first, _InputIterator __last,
 		      typename _Distance_traits<_InputIterator>::__type& __dist,
 		      std::__false_type)
     {
@@ -152,61 +156,69 @@ namespace __gnu_debug
   */
   template<typename _InputIterator>
     inline bool
-    __valid_range(const _InputIterator& __first, const _InputIterator& __last,
+    __valid_range(_InputIterator __first, _InputIterator __last,
 		  typename _Distance_traits<_InputIterator>::__type& __dist)
     {
       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
       return __valid_range_aux(__first, __last, __dist, _Integral());
     }
 
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    bool
+    __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
+		  const _Safe_iterator<_Iterator, _Sequence, _Category>&,
+		  typename _Distance_traits<_Iterator>::__type&);
+
+#if __cplusplus >= 201103L
+  template<typename _Iterator,typename _Sequence>
+    bool
+    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
+		  const _Safe_local_iterator<_Iterator, _Sequence>&,
+		  typename _Distance_traits<_Iterator>::__type&);
+#endif
+
   template<typename _InputIterator>
     inline bool
-    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
+    __valid_range(_InputIterator __first, _InputIterator __last)
     {
       typename _Distance_traits<_InputIterator>::__type __dist;
       return __valid_range(__first, __last, __dist);
     }
 
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    bool
+    __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
+		  const _Safe_iterator<_Iterator, _Sequence, _Category>&);
+
+#if __cplusplus >= 201103L
+  template<typename _Iterator, typename _Sequence>
+    bool
+    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
+		  const _Safe_local_iterator<_Iterator, _Sequence>&);
+#endif
+
   // Fallback method, always ok.
   template<typename _InputIterator, typename _Size>
     inline bool
     __can_advance(_InputIterator, _Size)
     { return true; }
 
-  template<typename _Iterator, typename _Sequence, typename _Size>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _Size>
     bool
-    __can_advance(const _Safe_iterator<_Iterator, _Sequence>&, _Size);
-
-#if __cplusplus < 201103L
-  // Helper struct to detect random access safe iterators.
-  template<typename _Iterator>
-    struct __is_safe_random_iterator
-    {
-      enum { __value = 0 };
-      typedef std::__false_type __type;
-    };
-
-  template<typename _Iterator>
-    struct _Siter_base
-    : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
-    { };
+    __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
+		  _Size);
 
   /** Helper function to extract base iterator of random access safe iterator
-      in order to reduce performance impact of debug mode.  Limited to random
-      access iterator because it is the only category for which it is possible
-      to check for correct iterators order in the __valid_range function
-      thanks to the < operator.
+   *  in order to reduce performance impact of debug mode.  Limited to random
+   *  access iterator because it is the only category for which it is possible
+   *  to check for correct iterators order in the __valid_range function
+   *  thanks to the < operator.
    */
   template<typename _Iterator>
-    inline typename _Siter_base<_Iterator>::iterator_type
-    __base(_Iterator __it)
-    { return _Siter_base<_Iterator>::_S_base(__it); }
-#else
-  template<typename _Iterator>
     inline _Iterator
     __base(_Iterator __it)
     { return __it; }
-#endif
 
 #if __cplusplus < 201103L
   template<typename _Iterator>
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index bf3179a..c6aea5d 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -57,6 +57,9 @@ namespace __debug
       typedef __gnu_debug::_Equal_to<_Base_const_iterator>	_Equal;
       typedef __gnu_debug::_Not_equal_to<_Base_const_iterator>  _Not_equal;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 1fd4416..cbfd7c3 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -56,6 +56,9 @@ namespace __debug
       typedef typename _Base::iterator		_Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       // types:
       typedef _Key					key_type;
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index 0994dc4..253b085 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -56,6 +56,9 @@ namespace __debug
       typedef typename _Base::iterator		_Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       // types:
       typedef _Key					key_type;
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index 6e4c1b0..fa747ff 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -55,6 +55,9 @@ namespace __debug
       typedef typename _Base::iterator		_Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       // types:
       typedef _Key					key_type;
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index b8256fc..2cb1860 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -44,14 +44,14 @@ namespace __gnu_debug
   template<typename _Sequence>
     struct _BeforeBeginHelper
     {
-      template<typename _Iterator>
+      template<typename _Iterator, typename _Category>
 	static bool
-	_S_Is(const _Safe_iterator<_Iterator, _Sequence>&)
+	_S_Is(const _Safe_iterator<_Iterator, _Sequence, _Category>&)
 	{ return false; }
 
-      template<typename _Iterator>
+      template<typename _Iterator, typename _Category>
 	static bool
-	_S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence>& __it)
+	_S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it)
 	{ return __it.base() == __it._M_get_sequence()->_M_base().begin(); }
     };
 
@@ -76,28 +76,35 @@ namespace __gnu_debug
    *  %_Safe_iterator has member functions for iterator invalidation,
    *  attaching/detaching the iterator from sequences, and querying
    *  the iterator's state.
-   *
    *  Note that _Iterator must be the first base class so that it gets
    *  initialized before the iterator is being attached to the container's list
    *  of iterators and it is being detached before _Iterator get
    *  destroyed. Otherwise it would result in a data race.
    */
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename
+	   = typename std::iterator_traits<_Iterator>::iterator_category>
     class _Safe_iterator
     : private _Iterator,
       public _Safe_iterator_base
     {
       typedef _Iterator _Iter_base;
       typedef _Safe_iterator_base _Safe_base;
-      typedef typename _Sequence::const_iterator _Const_iterator;
 
       typedef std::iterator_traits<_Iterator> _Traits;
 
+    protected:
+      typedef std::__are_same<typename _Sequence::_Base::const_iterator,
+			      _Iterator> _IsConstant;
+
+      typedef typename __gnu_cxx::__conditional_type<
+	_IsConstant::__value,
+	typename _Sequence::_Base::iterator,
+	typename _Sequence::_Base::const_iterator>::__type _OtherIterator;
+
       struct _Attach_single
       { };
 
-      _Safe_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
-		     _Attach_single)
+      _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
       _GLIBCXX_NOEXCEPT
       : _Iter_base(__i)
       { _M_attach_single(__seq); }
@@ -120,7 +127,7 @@ namespace __gnu_debug
        * @pre @p seq is not NULL
        * @post this is not singular
        */
-      _Safe_iterator(const _Iterator& __i, const _Safe_sequence_base* __seq)
+      _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
       _GLIBCXX_NOEXCEPT
       : _Iter_base(__i), _Safe_base(__seq, _S_constant())
       {
@@ -172,9 +179,10 @@ namespace __gnu_debug
       template<typename _MutableIterator>
 	_Safe_iterator(
 	  const _Safe_iterator<_MutableIterator,
-	  typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
-		      typename _Sequence::iterator::iterator_type>::__value),
-		   _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
+	  typename __gnu_cxx::__enable_if<_IsConstant::__value &&
+	    std::__are_same<_MutableIterator, _OtherIterator>::__value,
+					  _Sequence>::__type>& __x)
+	_GLIBCXX_NOEXCEPT
 	: _Iter_base(__x.base())
 	{
 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -309,93 +317,12 @@ namespace __gnu_debug
 	return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
       }
 
-      // ------ Bidirectional iterator requirements ------
-      /**
-       *  @brief Iterator predecrement
-       *  @pre iterator is decrementable
-       */
-      _Safe_iterator&
-      operator--() _GLIBCXX_NOEXCEPT
-      {
-	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
-			      _M_message(__msg_bad_dec)
-			      ._M_iterator(*this, "this"));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	--base();
-	return *this;
-      }
-
-      /**
-       *  @brief Iterator postdecrement
-       *  @pre iterator is decrementable
-       */
-      _Safe_iterator
-      operator--(int) _GLIBCXX_NOEXCEPT
-      {
-	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
-			      _M_message(__msg_bad_dec)
-			      ._M_iterator(*this, "this"));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
-      }
-
-      // ------ Random access iterator requirements ------
-      reference
-      operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
-      {
-	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
-			      && this->_M_can_advance(__n+1),
-			      _M_message(__msg_iter_subscript_oob)
-			      ._M_iterator(*this)._M_integer(__n));
-	return base()[__n];
-      }
-
-      _Safe_iterator&
-      operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
-      {
-	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
-			      _M_message(__msg_advance_oob)
-			      ._M_iterator(*this)._M_integer(__n));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	base() += __n;
-	return *this;
-      }
-
-      _Safe_iterator
-      operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
-      {
-	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
-			      _M_message(__msg_advance_oob)
-			      ._M_iterator(*this)._M_integer(__n));
-	return _Safe_iterator(base() + __n, this->_M_sequence);
-      }
-
-      _Safe_iterator&
-      operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
-      {
-	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
-			      _M_message(__msg_retreat_oob)
-			      ._M_iterator(*this)._M_integer(__n));
-	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	base() -= __n;
-	return *this;
-      }
-
-      _Safe_iterator
-      operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
-      {
-	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
-			      _M_message(__msg_retreat_oob)
-			      ._M_iterator(*this)._M_integer(__n));
-	return _Safe_iterator(base() - __n, this->_M_sequence);
-      }
-
       // ------ Utilities ------
 
       /// Determine if this is a constant iterator.
-      static bool
+      static _GLIBCXX_CONSTEXPR bool
       _S_constant()
-      { return std::__are_same<_Const_iterator, _Safe_iterator>::__value; }
+      { return _IsConstant::__value; }
 
       /**
        * @brief Return the underlying iterator
@@ -444,10 +371,6 @@ namespace __gnu_debug
       _M_incrementable() const
       { return !this->_M_singular() && !_M_is_end(); }
 
-      // Is the iterator decrementable?
-      bool
-      _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
-
       // Can we advance the iterator @p __n steps (@p __n may be negative)
       bool
       _M_can_advance(const difference_type& __n) const;
@@ -459,14 +382,23 @@ namespace __gnu_debug
 		     bool __check_dereferenceable = true) const;
 
       // The sequence this iterator references.
-      typename
-      __gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
-						    _Safe_iterator>::__value,
-				    const _Sequence*,
-				    _Sequence*>::__type
+      typename __gnu_cxx::__conditional_type<
+	_IsConstant::__value, const _Sequence*, _Sequence*>::__type
       _M_get_sequence() const
       { return static_cast<_Sequence*>(_M_sequence); }
 
+      // Get distance to __rhs.
+      typename _Distance_traits<_Iterator>::__type
+      _M_get_distance_to(const _Safe_iterator& __rhs) const;
+
+      // Get distance from sequence begin up to *this.
+      typename _Distance_traits<_Iterator>::__type
+      _M_get_distance_from_begin() const;
+
+      // Get distance from *this to sequence end.
+      typename _Distance_traits<_Iterator>::__type
+      _M_get_distance_to_end() const;
+
       /// Is this iterator equal to the sequence's begin() iterator?
       bool
       _M_is_begin() const
@@ -490,6 +422,342 @@ namespace __gnu_debug
       { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
     };
 
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag>
+    : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag>
+    {
+      typedef _Safe_iterator<_Iterator, _Sequence,
+			     std::forward_iterator_tag> _Safe_base;
+
+    protected:
+      typedef typename _Safe_base::_OtherIterator _OtherIterator;
+      typedef typename _Safe_base::_Attach_single _Attach_single;
+
+      _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
+      _GLIBCXX_NOEXCEPT
+      : _Safe_base(__i, __seq, _Attach_single())
+      { }
+
+    public:
+      /// @post the iterator is singular and unattached
+      _Safe_iterator() _GLIBCXX_NOEXCEPT { }
+
+      /**
+       * @brief Safe iterator construction from an unsafe iterator and
+       * its sequence.
+       *
+       * @pre @p seq is not NULL
+       * @post this is not singular
+       */
+      _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
+      _GLIBCXX_NOEXCEPT
+      : _Safe_base(__i, __seq)
+      { }
+
+      /**
+       * @brief Copy construction.
+       */
+      _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
+      : _Safe_base(__x)
+      { }
+
+#if __cplusplus >= 201103L
+      /** @brief Move construction. */
+      _Safe_iterator(_Safe_iterator&&) = default;
+#endif
+
+      /**
+       *  @brief Converting constructor from a mutable iterator to a
+       *  constant iterator.
+      */
+      template<typename _MutableIterator>
+	_Safe_iterator(
+	  const _Safe_iterator<_MutableIterator,
+	  typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
+	    std::__are_same<_MutableIterator, _OtherIterator>::__value,
+					  _Sequence>::__type>& __x)
+	_GLIBCXX_NOEXCEPT
+	: _Safe_base(__x)
+        { }
+
+#if __cplusplus >= 201103L
+      /** @brief Copy assignment. */
+      _Safe_iterator&
+      operator=(const _Safe_iterator&) = default;
+
+      /** @brief Move assignment. */
+      _Safe_iterator&
+      operator=(_Safe_iterator&&) = default;
+#else
+      /**
+       * @brief Copy assignment.
+       */
+      _Safe_iterator&
+      operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator=(__x);
+	return *this;
+      }
+#endif
+
+      // ------ Input iterator requirements ------
+      /**
+       *  @brief Iterator preincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_iterator&
+      operator++() _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator++();
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_iterator
+      operator++(int) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
+			      _M_message(__msg_bad_inc)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_iterator(this->base()++, this->_M_sequence,
+				     _Attach_single());
+      }
+
+      // ------ Bidirectional iterator requirements ------
+      /**
+       *  @brief Iterator predecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_iterator&
+      operator--() _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
+			      _M_message(__msg_bad_dec)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	--this->base();
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postdecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_iterator
+      operator--(int) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
+			      _M_message(__msg_bad_dec)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_iterator(this->base()--, this->_M_sequence,
+				     _Attach_single());
+      }
+
+      // ------ Utilities ------
+
+      // Is the iterator decrementable?
+      bool
+      _M_decrementable() const { return !this->_M_singular() && !this->_M_is_begin(); }
+    };
+
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>
+    : public _Safe_iterator<_Iterator, _Sequence,
+			    std::bidirectional_iterator_tag>
+    {
+      typedef _Safe_iterator<_Iterator, _Sequence,
+			     std::bidirectional_iterator_tag> _Safe_base;
+      typedef typename _Safe_base::_OtherIterator _OtherIterator;
+
+      typedef typename _Safe_base::_Attach_single _Attach_single;
+
+      _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
+      _GLIBCXX_NOEXCEPT
+      : _Safe_base(__i, __seq, _Attach_single())
+      { }
+
+    public:
+      typedef typename _Safe_base::difference_type	difference_type;
+      typedef typename _Safe_base::reference		reference;
+
+      /// @post the iterator is singular and unattached
+      _Safe_iterator() _GLIBCXX_NOEXCEPT { }
+
+      /**
+       * @brief Safe iterator construction from an unsafe iterator and
+       * its sequence.
+       *
+       * @pre @p seq is not NULL
+       * @post this is not singular
+       */
+      _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
+      _GLIBCXX_NOEXCEPT
+      : _Safe_base(__i, __seq)
+      { }
+
+      /**
+       * @brief Copy construction.
+       */
+      _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
+      : _Safe_base(__x)
+      { }
+
+#if __cplusplus >= 201103L
+      /** @brief Move construction. */
+      _Safe_iterator(_Safe_iterator&&) = default;
+#endif
+
+      /**
+       *  @brief Converting constructor from a mutable iterator to a
+       *  constant iterator.
+      */
+      template<typename _MutableIterator>
+	_Safe_iterator(
+	  const _Safe_iterator<_MutableIterator,
+	  typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
+	    std::__are_same<_MutableIterator, _OtherIterator>::__value,
+					  _Sequence>::__type>& __x)
+	_GLIBCXX_NOEXCEPT
+	: _Safe_base(__x)
+        { }
+
+#if __cplusplus >= 201103L
+      /** @brief Copy assignment. */
+      _Safe_iterator&
+      operator=(const _Safe_iterator&) = default;
+
+      /** @brief Move assignment. */
+      _Safe_iterator&
+      operator=(_Safe_iterator&&) = default;
+#else
+      /**
+       * @brief Copy assignment.
+       */
+      _Safe_iterator&
+      operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator=(__x);
+	return *this;
+      }
+#endif
+
+      // Is the iterator range [*this, __rhs) valid?
+      bool
+      _M_valid_range(const _Safe_iterator& __rhs,
+		     std::pair<difference_type,
+			       _Distance_precision>& __dist) const;
+
+      // ------ Input iterator requirements ------
+      /**
+       *  @brief Iterator preincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_iterator&
+      operator++() _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator++();
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_iterator
+      operator++(int) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
+			      _M_message(__msg_bad_inc)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_iterator(this->base()++, this->_M_sequence,
+			      _Attach_single());
+      }
+
+      // ------ Bidirectional iterator requirements ------
+      /**
+       *  @brief Iterator predecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_iterator&
+      operator--() _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator--();
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postdecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_iterator
+      operator--(int) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
+			      _M_message(__msg_bad_dec)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_iterator(this->base()--, this->_M_sequence,
+			      _Attach_single());
+      }
+
+      // ------ Random access iterator requirements ------
+      reference
+      operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
+			      && this->_M_can_advance(__n + 1),
+			      _M_message(__msg_iter_subscript_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	return this->base()[__n];
+      }
+
+      _Safe_iterator&
+      operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
+			      _M_message(__msg_advance_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	this->base() += __n;
+	return *this;
+      }
+
+      _Safe_iterator
+      operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
+			      _M_message(__msg_advance_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	return _Safe_iterator(this->base() + __n, this->_M_sequence);
+      }
+
+      _Safe_iterator&
+      operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
+			      _M_message(__msg_retreat_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	this->base() -= __n;
+	return *this;
+      }
+
+      _Safe_iterator
+      operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
+			      _M_message(__msg_retreat_oob)
+			      ._M_iterator(*this)._M_integer(__n));
+	return _Safe_iterator(this->base() - __n, this->_M_sequence);
+      }
+    };
+
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
     operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
@@ -560,8 +828,10 @@ namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator<(const _Safe_iterator<_IteratorL, _Sequence,
+				   std::random_access_iterator_tag>& __lhs,
+	      const _Safe_iterator<_IteratorR, _Sequence,
+				   std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -577,8 +847,10 @@ namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	      const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator<(const _Safe_iterator<_Iterator, _Sequence,
+				   std::random_access_iterator_tag>& __lhs,
+	      const _Safe_iterator<_Iterator, _Sequence,
+				   std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -594,8 +866,10 @@ namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator<=(const _Safe_iterator<_IteratorL, _Sequence,
+				    std::random_access_iterator_tag>& __lhs,
+	       const _Safe_iterator<_IteratorR, _Sequence,
+				    std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -611,8 +885,10 @@ namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator<=(const _Safe_iterator<_Iterator, _Sequence,
+				    std::random_access_iterator_tag>& __lhs,
+	       const _Safe_iterator<_Iterator, _Sequence,
+				    std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -628,8 +904,10 @@ namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator>(const _Safe_iterator<_IteratorL, _Sequence,
+				   std::random_access_iterator_tag>& __lhs,
+	      const _Safe_iterator<_IteratorR, _Sequence,
+				   std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -645,8 +923,10 @@ namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	      const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator>(const _Safe_iterator<_Iterator, _Sequence,
+				   std::random_access_iterator_tag>& __lhs,
+	      const _Safe_iterator<_Iterator, _Sequence,
+				   std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -662,8 +942,10 @@ namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator>=(const _Safe_iterator<_IteratorL, _Sequence,
+				    std::random_access_iterator_tag>& __lhs,
+	       const _Safe_iterator<_IteratorR, _Sequence,
+				    std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -679,8 +961,10 @@ namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator>=(const _Safe_iterator<_Iterator, _Sequence,
+				    std::random_access_iterator_tag>& __lhs,
+	       const _Safe_iterator<_Iterator, _Sequence,
+				    std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -699,9 +983,12 @@ namespace __gnu_debug
   // operators but also operator- must accept mixed iterator/const_iterator
   // parameters.
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
-    inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
-    operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    inline typename _Safe_iterator<_IteratorL, _Sequence,
+			std::random_access_iterator_tag>::difference_type
+    operator-(const _Safe_iterator<_IteratorL, _Sequence,
+				   std::random_access_iterator_tag>& __lhs,
+	      const _Safe_iterator<_IteratorR, _Sequence,
+				   std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -716,9 +1003,12 @@ namespace __gnu_debug
     }
 
   template<typename _Iterator, typename _Sequence>
-     inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
-     operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    inline typename _Safe_iterator<_Iterator, _Sequence,
+			std::random_access_iterator_tag>::difference_type
+    operator-(const _Safe_iterator<_Iterator, _Sequence,
+				   std::random_access_iterator_tag>& __lhs,
+	      const _Safe_iterator<_Iterator, _Sequence,
+				   std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -733,167 +1023,48 @@ namespace __gnu_debug
     }
 
   template<typename _Iterator, typename _Sequence>
-    inline _Safe_iterator<_Iterator, _Sequence>
-    operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
-	      const _Safe_iterator<_Iterator, _Sequence>& __i) _GLIBCXX_NOEXCEPT
+    inline _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>
+    operator+(typename _Safe_iterator<_Iterator,_Sequence,
+		std::random_access_iterator_tag>::difference_type __n,
+	      const _Safe_iterator<_Iterator, _Sequence,
+		std::random_access_iterator_tag>& __i)
+    _GLIBCXX_NOEXCEPT
     { return __i + __n; }
 
-  /** Safe iterators know if they are dereferenceable. */
-  template<typename _Iterator, typename _Sequence>
-    inline bool
-    __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
-    { return __x._M_dereferenceable(); }
-
   /** Safe iterators know how to check if they form a valid range. */
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     inline bool
-    __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
-		  const _Safe_iterator<_Iterator, _Sequence>& __last,
+    __valid_range(const _Safe_iterator<_Iterator, _Sequence,
+				       _Category>& __first,
+		  const _Safe_iterator<_Iterator, _Sequence,
+				       _Category>& __last,
 		  typename _Distance_traits<_Iterator>::__type& __dist)
     { return __first._M_valid_range(__last, __dist); }
 
-  /** Safe iterators can help to get better distance knowledge. */
-  template<typename _Iterator, typename _Sequence>
-    inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
-		   const _Safe_iterator<_Iterator, _Sequence>& __last,
-		   std::random_access_iterator_tag)
-    { return std::make_pair(__last.base() - __first.base(), __dp_exact); }
-
-  template<typename _Iterator, typename _Sequence>
-    inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
-		   const _Safe_iterator<_Iterator, _Sequence>& __last,
-		   std::input_iterator_tag)
-    {
-      typedef typename _Distance_traits<_Iterator>::__type _Diff;
-      typedef _Sequence_traits<_Sequence> _SeqTraits;
-
-      if (__first.base() == __last.base())
-	return std::make_pair(0, __dp_exact);
-
-      if (__first._M_is_before_begin())
-	{
-	  if (__last._M_is_begin())
-	    return std::make_pair(1, __dp_exact);
-
-	  return std::make_pair(1, __dp_sign);
-	}
-
-      if (__first._M_is_begin())
-	{
-	  if (__last._M_is_before_begin())
-	    return std::make_pair(-1, __dp_exact);
-
-	  if (__last._M_is_end())
-	    return _SeqTraits::_S_size(*__first._M_get_sequence());
-
-	  return std::make_pair(1, __dp_sign);
-	}
-
-      if (__first._M_is_end())
-	{
-	  if (__last._M_is_before_begin())
-	    return std::make_pair(-1, __dp_exact);
-
-	  if (__last._M_is_begin())
-	    {
-	      _Diff __diff = _SeqTraits::_S_size(*__first._M_get_sequence());
-	      return std::make_pair(-__diff.first, __diff.second);
-	    }
-
-	  return std::make_pair(-1, __dp_sign);
-	}
-
-      if (__last._M_is_before_begin() || __last._M_is_begin())
-	return std::make_pair(-1, __dp_sign);
-
-      if (__last._M_is_end())
-	return std::make_pair(1, __dp_sign);
-
-      return std::make_pair(1, __dp_equality);
-    }
-
-  // Get distance from sequence begin to specified iterator.
-  template<typename _Iterator, typename _Sequence>
-    inline typename _Distance_traits<_Iterator>::__type
-    __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __it)
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    inline bool
+    __valid_range(const _Safe_iterator<_Iterator, _Sequence,
+				       _Category>& __first,
+		  const _Safe_iterator<_Iterator, _Sequence,
+				       _Category>& __last)
     {
-      typedef _Sequence_traits<_Sequence> _SeqTraits;
-
-      // No need to consider before_begin as this function is only used in
-      // _M_can_advance which won't be used for forward_list iterators.
-      if (__it._M_is_begin())
-	return std::make_pair(0, __dp_exact);
-
-      if (__it._M_is_end())
-	return _SeqTraits::_S_size(*__it._M_get_sequence());
-
-      typename _Distance_traits<_Iterator>::__type __res
-	= __get_distance(__it._M_get_sequence()->_M_base().begin(), __it.base());
-
-      if (__res.second == __dp_equality)
-	return std::make_pair(1, __dp_sign);
-
-      return __res;
+      typename _Distance_traits<_Iterator>::__type __dist;
+      return __first._M_valid_range(__last, __dist);
     }
 
-  // Get distance from specified iterator to sequence end.
-  template<typename _Iterator, typename _Sequence>
-    inline typename _Distance_traits<_Iterator>::__type
-    __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __it)
-    {
-      typedef _Sequence_traits<_Sequence> _SeqTraits;
-
-      // No need to consider before_begin as this function is only used in
-      // _M_can_advance which won't be used for forward_list iterators.
-      if (__it._M_is_begin())
-	return _SeqTraits::_S_size(*__it._M_get_sequence());
-
-      if (__it._M_is_end())
-	return std::make_pair(0, __dp_exact);
-
-      typename _Distance_traits<_Iterator>::__type __res
-	= __get_distance(__it.base(), __it._M_get_sequence()->_M_base().end());
-
-      if (__res.second == __dp_equality)
-	return std::make_pair(1, __dp_sign);
-
-      return __res;
-    }
-
-  template<typename _Iterator, typename _Sequence, typename _Size>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _Size>
     inline bool
-    __can_advance(const _Safe_iterator<_Iterator, _Sequence>& __it, _Size __n)
+    __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+		  _Size __n)
     { return __it._M_can_advance(__n); }
 
-#if __cplusplus < 201103L
-  template<typename _Iterator, typename _Sequence>
-    struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
-    : std::__are_same<std::random_access_iterator_tag,
-                      typename std::iterator_traits<_Iterator>::
-		      iterator_category>
-    { };
-#else
   template<typename _Iterator, typename _Sequence>
     _Iterator
-    __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
-	   std::random_access_iterator_tag)
+    __base(const _Safe_iterator<_Iterator, _Sequence,
+				std::random_access_iterator_tag>& __it)
     { return __it.base(); }
 
-  template<typename _Iterator, typename _Sequence>
-    const _Safe_iterator<_Iterator, _Sequence>&
-    __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
-	   std::input_iterator_tag)
-    { return __it; }
-
-  template<typename _Iterator, typename _Sequence>
-    auto
-    __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
-    -> decltype(__base(__it, std::__iterator_category(__it)))
-    { return __base(__it, std::__iterator_category(__it)); }
-#endif
-
 #if __cplusplus < 201103L
   template<typename _Iterator, typename _Sequence>
     struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index bdd95bb..2841583 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -31,9 +31,57 @@
 
 namespace __gnu_debug
 {
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    typename _Distance_traits<_Iterator>::__type
+    _Safe_iterator<_Iterator, _Sequence, _Category>::
+    _M_get_distance_from_begin() const
+    {
+      typedef _Sequence_traits<_Sequence> _SeqTraits;
+
+      // No need to consider before_begin as this function is only used in
+      // _M_can_advance which won't be used for forward_list iterators.
+      if (_M_is_begin())
+	return std::make_pair(0, __dp_exact);
+
+      if (_M_is_end())
+	return _SeqTraits::_S_size(*_M_get_sequence());
+
+      typename _Distance_traits<_Iterator>::__type __res
+	= __get_distance(_M_get_sequence()->_M_base().begin(), base());
+
+      if (__res.second == __dp_equality)
+	return std::make_pair(1, __dp_sign);
+
+      return __res;
+    }
+
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    typename _Distance_traits<_Iterator>::__type
+    _Safe_iterator<_Iterator, _Sequence, _Category>::
+    _M_get_distance_to_end() const
+    {
+      typedef _Sequence_traits<_Sequence> _SeqTraits;
+
+      // No need to consider before_begin as this function is only used in
+      // _M_can_advance which won't be used for forward_list iterators.
+      if (_M_is_begin())
+	return _SeqTraits::_S_size(*_M_get_sequence());
+
+      if (_M_is_end())
+	return std::make_pair(0, __dp_exact);
+
+      typename _Distance_traits<_Iterator>::__type __res
+	= __get_distance(base(), _M_get_sequence()->_M_base().end());
+
+      if (__res.second == __dp_equality)
+	return std::make_pair(1, __dp_sign);
+
+      return __res;
+    }
+
+  template<typename _Iterator, typename _Sequence, typename _Category>
     bool
-    _Safe_iterator<_Iterator, _Sequence>::
+    _Safe_iterator<_Iterator, _Sequence, _Category>::
     _M_can_advance(const difference_type& __n) const
     {
       if (this->_M_singular())
@@ -45,7 +93,7 @@ namespace __gnu_debug
       if (__n < 0)
 	{
 	  std::pair<difference_type, _Distance_precision> __dist =
-	    __get_distance_from_begin(*this);
+	    _M_get_distance_from_begin();
 	  bool __ok =  ((__dist.second == __dp_exact && __dist.first >= -__n)
 			|| (__dist.second != __dp_exact && __dist.first > 0));
 	  return __ok;
@@ -53,16 +101,69 @@ namespace __gnu_debug
       else
 	{
 	  std::pair<difference_type, _Distance_precision> __dist =
-	    __get_distance_to_end(*this);
+	    _M_get_distance_to_end();
 	  bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n)
 		       || (__dist.second != __dp_exact && __dist.first > 0));
 	  return __ok;
 	}
     }
 
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    typename _Distance_traits<_Iterator>::__type
+    _Safe_iterator<_Iterator, _Sequence, _Category>::
+    _M_get_distance_to(const _Safe_iterator& __rhs) const
+    {
+      typedef typename _Distance_traits<_Iterator>::__type _Diff;
+      typedef _Sequence_traits<_Sequence> _SeqTraits;
+
+      if (this->base() == __rhs.base())
+	return std::make_pair(0, __dp_exact);
+
+      if (this->_M_is_before_begin())
+	{
+	  if (__rhs._M_is_begin())
+	    return std::make_pair(1, __dp_exact);
+
+	  return std::make_pair(1, __dp_sign);
+	}
+
+      if (this->_M_is_begin())
+	{
+	  if (__rhs._M_is_before_begin())
+	    return std::make_pair(-1, __dp_exact);
+
+	  if (__rhs._M_is_end())
+	    return _SeqTraits::_S_size(*this->_M_get_sequence());
+
+	  return std::make_pair(1, __dp_sign);
+	}
+
+      if (this->_M_is_end())
+	{
+	  if (__rhs._M_is_before_begin())
+	    return std::make_pair(-1, __dp_exact);
+
+	  if (__rhs._M_is_begin())
+	    {
+	      _Diff __diff = _SeqTraits::_S_size(*this->_M_get_sequence());
+	      return std::make_pair(-__diff.first, __diff.second);
+	    }
+
+	  return std::make_pair(-1, __dp_sign);
+	}
+
+      if (__rhs._M_is_before_begin() || __rhs._M_is_begin())
+	return std::make_pair(-1, __dp_sign);
+
+      if (__rhs._M_is_end())
+	return std::make_pair(1, __dp_sign);
+
+      return std::make_pair(1, __dp_equality);
+    }
+
+  template<typename _Iterator, typename _Sequence, typename _Category>
     bool
-    _Safe_iterator<_Iterator, _Sequence>::
+    _Safe_iterator<_Iterator, _Sequence, _Category>::
     _M_valid_range(const _Safe_iterator& __rhs,
 		   std::pair<difference_type, _Distance_precision>& __dist,
 		   bool __check_dereferenceable) const
@@ -71,7 +172,7 @@ namespace __gnu_debug
 	return false;
 
       /* Determine iterators order */
-      __dist = __get_distance(*this, __rhs);
+      __dist = _M_get_distance_to(__rhs);
       switch (__dist.second)
 	{
 	case __dp_equality:
@@ -90,6 +191,25 @@ namespace __gnu_debug
       // Assume that this is a valid range; we can't check anything else.
       return true;
     }
+
+  template<typename _Iterator, typename _Sequence>
+    bool
+    _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>::
+    _M_valid_range(const _Safe_iterator& __rhs,
+		   std::pair<difference_type,
+			     _Distance_precision>& __dist) const
+    {
+      if (!this->_M_can_compare(__rhs))
+	return false;
+
+      /* Determine iterators order */
+      __dist = std::make_pair(__rhs.base() - this->base(), __dp_exact);
+
+      // If range is not empty first iterator must be dereferenceable.
+      if (__dist.first > 0)
+	return this->_M_dereferenceable();
+      return __dist.first == 0;
+    }
 } // namespace __gnu_debug
 
 #endif
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h
index f9597a6..8545188 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -51,15 +51,24 @@ namespace __gnu_debug
     {
       typedef _Iterator _Iter_base;
       typedef _Safe_local_iterator_base _Safe_base;
-      typedef typename _Sequence::const_local_iterator _Const_local_iterator;
+
       typedef typename _Sequence::size_type size_type;
 
       typedef std::iterator_traits<_Iterator> _Traits;
 
+      typedef std::__are_same<
+	typename _Sequence::_Base::const_local_iterator,
+	_Iterator> _IsConstant;
+
+      typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value,
+	typename _Sequence::_Base::local_iterator,
+	typename _Sequence::_Base::const_local_iterator>::__type
+      _OtherIterator;
+
       struct _Attach_single
       { };
 
-      _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont,
+      _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont,
 			   _Attach_single) noexcept
       : _Iter_base(__i)
       { _M_attach_single(__cont); }
@@ -82,8 +91,7 @@ namespace __gnu_debug
        * @pre @p seq is not NULL
        * @post this is not singular
        */
-      _Safe_local_iterator(const _Iterator& __i,
-			   const _Safe_sequence_base* __cont)
+      _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont)
       : _Iter_base(__i), _Safe_base(__cont, _S_constant())
       {
 	_GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
@@ -132,16 +140,15 @@ namespace __gnu_debug
       template<typename _MutableIterator>
 	_Safe_local_iterator(
 	  const _Safe_local_iterator<_MutableIterator,
-	  typename __gnu_cxx::__enable_if<std::__are_same<
-	      _MutableIterator,
-	      typename _Sequence::local_iterator::iterator_type>::__value,
-					  _Sequence>::__type>& __x)
+	  typename __gnu_cxx::__enable_if<_IsConstant::__value &&
+	    std::__are_same<_MutableIterator, _OtherIterator>::__value,
+					  _Sequence>::__type>& __x) noexcept
 	: _Iter_base(__x.base())
 	{
 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
 	  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 	  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
-				|| __x.base() == _Iterator(),
+				|| __x.base() == _MutableIterator(),
 				_M_message(__msg_init_const_singular)
 				._M_iterator(*this, "this")
 				._M_iterator(__x, "other"));
@@ -272,12 +279,9 @@ namespace __gnu_debug
       // ------ Utilities ------
 
       /// Determine if this is a constant iterator.
-      static bool
+      static constexpr bool
       _S_constant()
-      {
-	return std::__are_same<_Const_local_iterator,
-			       _Safe_local_iterator>::__value;
-      }
+      { return _IsConstant::__value; }
 
       /**
        * @brief Return the underlying iterator
@@ -326,12 +330,13 @@ namespace __gnu_debug
 		     std::pair<difference_type,
 			       _Distance_precision>& __dist_info) const;
 
+      // Get distance to __rhs.
+      typename _Distance_traits<_Iterator>::__type
+      _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
+
       // The sequence this iterator references.
-      typename
-      __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator,
-						    _Safe_local_iterator>::__value,
-				    const _Sequence*,
-				    _Sequence*>::__type
+      typename __gnu_cxx::__conditional_type<
+	_IsConstant::__value, const _Sequence*, _Sequence*>::__type
       _M_get_sequence() const
       { return static_cast<_Sequence*>(_M_sequence); }
 
@@ -431,13 +436,6 @@ namespace __gnu_debug
       return __lhs.base() != __rhs.base();
     }
 
-  /** Safe local iterators know if they are dereferenceable. */
-  template<typename _Iterator, typename _Sequence>
-    inline bool
-    __check_dereferenceable(const _Safe_local_iterator<_Iterator,
-						       _Sequence>& __x)
-    { return __x._M_dereferenceable(); }
-
   /** Safe local iterators know how to check if they form a valid range. */
   template<typename _Iterator, typename _Sequence>
     inline bool
@@ -446,49 +444,13 @@ namespace __gnu_debug
 		  typename _Distance_traits<_Iterator>::__type& __dist_info)
     { return __first._M_valid_range(__last, __dist_info); }
 
-  /** Safe local iterators need a special method to get distance between each
-      other. */
   template<typename _Iterator, typename _Sequence>
-    inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
-		     _Distance_precision>
-    __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
-		   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
-		   std::input_iterator_tag)
-    {
-      if (__first.base() == __last.base())
-	return { 0, __dp_exact };
-
-      if (__first._M_is_begin())
-	{
-	  if (__last._M_is_end())
-	    return
-	      {
-		__first._M_get_sequence()->bucket_size(__first.bucket()),
-		__dp_exact
-	      };
-
-	  return { 1, __dp_sign };
-	}
-
-      if (__first._M_is_end())
-	{
-	  if (__last._M_is_begin())
-	    return
+    inline bool
+    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
+		  const _Safe_local_iterator<_Iterator, _Sequence>& __last)
     {
-		-__first._M_get_sequence()->bucket_size(__first.bucket()),
-		__dp_exact
-	      };
-
-	  return { -1, __dp_sign };
-	}
-
-      if (__last._M_is_begin())
-	return { -1, __dp_sign };
-
-      if (__last._M_is_end())
-	return { 1, __dp_sign };
-
-      return { 1, __dp_equality };
+      typename _Distance_traits<_Iterator>::__type __dist_info;
+      return __first._M_valid_range(__last, __dist_info);
     }
 
 #if __cplusplus < 201103L
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.tcc b/libstdc++-v3/include/debug/safe_local_iterator.tcc
index 24d8e17..9637e9f 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_local_iterator.tcc
@@ -32,6 +32,47 @@
 namespace __gnu_debug
 {
   template<typename _Iterator, typename _Sequence>
+    typename _Distance_traits<_Iterator>::__type
+    _Safe_local_iterator<_Iterator, _Sequence>::
+    _M_get_distance_to(const _Safe_local_iterator& __rhs) const
+    {
+      if (base() == __rhs.base())
+	return { 0, __dp_exact };
+
+      if (_M_is_begin())
+	{
+	  if (__rhs._M_is_end())
+	    return
+	      {
+		_M_get_sequence()->bucket_size(bucket()),
+		__dp_exact
+	      };
+
+	  return { 1, __dp_sign };
+	}
+
+      if (_M_is_end())
+	{
+	  if (__rhs._M_is_begin())
+	    return
+	      {
+		-_M_get_sequence()->bucket_size(bucket()),
+		__dp_exact
+	      };
+
+	  return { -1, __dp_sign };
+	}
+
+      if (__rhs._M_is_begin())
+	return { -1, __dp_sign };
+
+      if (__rhs._M_is_end())
+	return { 1, __dp_sign };
+
+      return { 1, __dp_equality };
+    }
+
+  template<typename _Iterator, typename _Sequence>
     bool
     _Safe_local_iterator<_Iterator, _Sequence>::
     _M_valid_range(const _Safe_local_iterator& __rhs,
@@ -45,7 +86,7 @@ namespace __gnu_debug
 
       /* Determine if we can order the iterators without the help of
 	 the container */
-      __dist = __get_distance(*this, __rhs);
+      __dist = _M_get_distance_to(__rhs);
       switch (__dist.second)
 	{
 	case __dp_equality:
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index 571cc47..6f1a507 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -55,6 +55,9 @@ namespace __debug
       typedef typename _Base::iterator		_Base_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       // types:
       typedef _Key					key_type;
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index f20b000..3dbe402 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -52,12 +52,13 @@ namespace __gnu_debug
     __can_advance(const std::reverse_iterator<_Iterator>& __it, _Size __n)
     { return __can_advance(__it.base(), -__n); }
 
-#if __cplusplus < 201103L
-  template<typename _Iterator>
-    struct __is_safe_random_iterator<std::reverse_iterator<_Iterator> >
-      : __is_safe_random_iterator<_Iterator>
-    { };
+  template<typename _Iterator, typename _Sequence>
+    inline std::reverse_iterator<_Iterator>
+    __base(const std::reverse_iterator<_Safe_iterator<
+	     _Iterator, _Sequence, std::random_access_iterator_tag> >& __it)
+    { return std::reverse_iterator<_Iterator>(__it.base().base()); }
 
+#if __cplusplus < 201103L
   template<typename _Iterator>
     struct _Unsafe_type<std::reverse_iterator<_Iterator> >
     {
@@ -75,12 +76,6 @@ namespace __gnu_debug
 #else
   template<typename _Iterator>
     inline auto
-    __base(const std::reverse_iterator<_Iterator>& __it)
-    -> decltype(std::__make_reverse_iterator(__base(__it.base())))
-    { return std::__make_reverse_iterator(__base(__it.base())); }
-
-  template<typename _Iterator>
-    inline auto
     __unsafe(const std::reverse_iterator<_Iterator>& __it)
     -> decltype(std::__make_reverse_iterator(__unsafe(__it.base())))
     { return std::__make_reverse_iterator(__unsafe(__it.base())); }
@@ -128,7 +123,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Iterator
     __niter_base(const __gnu_debug::_Safe_iterator<
 		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
-		 _Sequence>&);
+		 _Sequence, std::random_access_iterator_tag>&);
 
 _GLIBCXX_END_NAMESPACE_VERSION
 }
diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string
index 7fa39e3..1883cac 100644
--- a/libstdc++-v3/include/debug/string
+++ b/libstdc++-v3/include/debug/string
@@ -94,6 +94,9 @@ namespace __gnu_debug
 	basic_string, _Allocator, _Safe_sequence, bool(_GLIBCXX_USE_CXX11_ABI)>
       _Safe;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       // types:
       typedef _Traits					traits_type;
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index e4f7c5c..095a752 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -66,6 +66,11 @@ namespace __debug
 						_Base_const_local_iterator;
       typedef typename _Base::local_iterator	_Base_local_iterator;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+      template<typename _ItT, typename _SeqT>
+	friend class ::__gnu_debug::_Safe_local_iterator;
+
     public:
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
@@ -752,6 +757,11 @@ namespace __debug
       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
       typedef typename _Base::local_iterator	   _Base_local_iterator;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+      template<typename _ItT, typename _SeqT>
+	friend class ::__gnu_debug::_Safe_local_iterator;
+
     public:
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index adafdb7..ced9b18 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -66,6 +66,11 @@ namespace __debug
       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
       typedef typename _Base::local_iterator	   _Base_local_iterator;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+      template<typename _ItT, typename _SeqT>
+	friend class ::__gnu_debug::_Safe_local_iterator;
+
     public:
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
@@ -629,6 +634,11 @@ namespace __debug
 						_Base_const_local_iterator;
       typedef typename _Base::local_iterator	_Base_local_iterator;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+      template<typename _ItT, typename _SeqT>
+	friend class ::__gnu_debug::_Safe_local_iterator;
+
     public:
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index ced5520..bd09b24 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -127,6 +127,9 @@ namespace __debug
       typedef typename _Base::const_iterator	_Base_const_iterator;
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
+      template<typename _ItT, typename _SeqT, typename _CatT>
+	friend class ::__gnu_debug::_Safe_iterator;
+
     public:
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
@@ -789,7 +792,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Iterator
     __niter_base(const __gnu_debug::_Safe_iterator<
 		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
-		 _Sequence>& __it)
+		 _Sequence, std::random_access_iterator_tag>& __it)
     { return std::__niter_base(__it.base()); }
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc
index 9fb12ed..1d45e74 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc
@@ -21,31 +21,6 @@
 #include <unordered_set>
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  using namespace __gnu_debug;
-
-  std::unordered_set<int> u = { 0, 1, 2 };
-  VERIFY( __check_dereferenceable(u.begin()) );
-  auto it = u.begin();
-  VERIFY( __check_dereferenceable(it) );
-
-  VERIFY( __check_dereferenceable(u.cbegin()) );
-  auto cit = u.begin();
-  VERIFY( __check_dereferenceable(cit) );
-
-  VERIFY( !__check_dereferenceable(u.end()) );
-  it = u.end();
-  VERIFY( !__check_dereferenceable(it) );
-
-  auto bucket = u.bucket(0);
-  VERIFY( __check_dereferenceable(u.begin(bucket)) );
-  auto lit = u.begin(bucket);
-  VERIFY( __check_dereferenceable(lit) );
-
-  VERIFY( !__check_dereferenceable(u.end(bucket)) );
-}
-
 void test02()
 {
   using namespace __gnu_debug;
@@ -84,7 +59,6 @@ void test02()
 
 int main()
 {
-  test01();
   test02();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc b/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc
index 5127f51..a3acaf4 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc
@@ -45,4 +45,4 @@ test02()
 // { dg-error "value type is destructible" "" { target *-*-* } 0 }
 
 // In Debug Mode the "required from here" errors come from <debug/vector>
-// { dg-error "required from here" "" { target *-*-* } 155 }
+// { dg-error "required from here" "" { target *-*-* } 158 }
diff --git a/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc b/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc
index ea683ee..acbd0d1 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc
@@ -20,28 +20,6 @@
 #include <vector>
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  using namespace __gnu_debug;
-
-  std::vector<int> v1(3, 1);
-  VERIFY( __check_dereferenceable(v1.begin()) );
-  std::vector<int>::iterator it = v1.begin();
-  VERIFY( __check_dereferenceable(it) );
-
-  VERIFY( !__check_dereferenceable(v1.end()) );
-  it = v1.end();
-  VERIFY( !__check_dereferenceable(it) );
-
-  const volatile int* pi = 0;
-  VERIFY( !__check_dereferenceable(pi) );
-
-  int i;
-  pi = &i;
-
-  VERIFY( __check_dereferenceable(pi) );
-}
-
 void test02()
 {
   using namespace __gnu_debug;
@@ -67,7 +45,6 @@ void test02()
 
 int main()
 {
-  test01();
   test02();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/util/testsuite_containers.h b/libstdc++-v3/testsuite/util/testsuite_containers.h
index 2dd5a5f..d05d3ac 100644
--- a/libstdc++-v3/testsuite/util/testsuite_containers.h
+++ b/libstdc++-v3/testsuite/util/testsuite_containers.h
@@ -20,6 +20,7 @@
 #ifndef _GLIBCXX_TESTSUITE_CONTAINERS_H
 #define _GLIBCXX_TESTSUITE_CONTAINERS_H
 
+#include <bits/boost_concept_check.h>
 #include <cassert>
 #include <testsuite_container_traits.h>
 #include <utility> // for rel_ops.
@@ -192,6 +193,77 @@ namespace __gnu_test
       forward_members_unordered(_Tp& container) { }
     };
 
+  template<typename _Iterator,
+	   bool _Mutable,
+	   typename = typename std::iterator_traits<_Iterator>::iterator_category>
+    struct iterator_concept_checks;
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, false,
+				   std::forward_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_ForwardIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, true,
+				   std::forward_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_Mutable_ForwardIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, false,
+				   std::bidirectional_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_BidirectionalIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, true,
+				   std::bidirectional_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_Mutable_BidirectionalIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, false,
+				   std::random_access_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_RandomAccessIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, true,
+				   std::random_access_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_Mutable_RandomAccessIteratorConcept<_Iterator>>();
+      }
+    };
+
   template<typename _Tp>
     struct citerator
     {
@@ -210,6 +282,11 @@ namespace __gnu_test
 	  // when comparing iterators.
 	  using namespace std::rel_ops;
 
+	  iterator_concept_checks<typename _Tp::iterator,
+				  !(traits_type::is_associative::value
+				    || traits_type::is_unordered::value)> cc;
+	  iterator_concept_checks<typename _Tp::const_iterator, false> ccc;
+
 	  assert( _S_container.cbegin() == _S_container.begin() );
 	  assert( _S_container.end() == _S_container.cend() );
 	  assert( _S_container.cbegin() != _S_container.cend() );

Patch

diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 93b82cf..213e23b 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -57,12 +57,14 @@  namespace __debug
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
+      typedef _Base					normal_type;
+
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_iterator, deque>
 							iterator;
-      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_const_iterator, deque>
 							const_iterator;
 
       typedef typename _Base::size_type			size_type;
diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
index 7b3c30b..33bc2b2 100644
--- a/libstdc++-v3/include/debug/formatter.h
+++ b/libstdc++-v3/include/debug/formatter.h
@@ -76,8 +76,8 @@  namespace __gnu_debug
 
   class _Safe_sequence_base;
 
-  template<typename _Iterator, typename _Sequence>
-    class _Safe_iterator;
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    class _Safe_tagged_iterator;
 
   template<typename _Iterator, typename _Sequence>
     class _Safe_local_iterator;
@@ -264,8 +264,9 @@  namespace __gnu_debug
 	_M_variant._M_string._M_value = __value;
       }
 
-      template<typename _Iterator, typename _Sequence>
-	_Parameter(_Safe_iterator<_Iterator, _Sequence> const& __it,
+      template<typename _Iterator, typename _Sequence, typename _Category>
+	_Parameter(_Safe_tagged_iterator<_Iterator, _Sequence,
+					 _Category> const& __it,
 		   const char* __name, _Is_iterator)
 	: _M_kind(__iterator),  _M_variant()
 	{
@@ -379,9 +380,10 @@  namespace __gnu_debug
 	    = _S_reverse_state(_M_variant._M_iterator._M_state);
 	}
 
-      template<typename _Iterator, typename _Sequence>
-	_Parameter(std::reverse_iterator<_Safe_iterator<_Iterator,
-							_Sequence>> const& __it,
+      template<typename _Iterator, typename _Sequence, typename _Category>
+	_Parameter(
+	  std::reverse_iterator<_Safe_tagged_iterator<_Iterator, _Sequence,
+						      _Category>> const& __it,
 	  const char* __name, _Is_iterator)
 	: _Parameter(__it.base(), __name, _Is_iterator{})
 	{
@@ -397,9 +399,10 @@  namespace __gnu_debug
 	: _Parameter(__it.base(), __name, _Is_iterator{})
 	{ _M_variant._M_iterator._M_type = _GLIBCXX_TYPEID(__it); }
 
-      template<typename _Iterator, typename _Sequence>
-	_Parameter(std::move_iterator<_Safe_iterator<_Iterator,
-						     _Sequence>> const& __it,
+      template<typename _Iterator, typename _Sequence, typename _Category>
+	_Parameter(
+	  std::move_iterator<_Safe_tagged_iterator<_Iterator, _Sequence,
+						   _Category>> const& __it,
 	  const char* __name, _Is_iterator)
 	: _Parameter(__it.base(), __name, _Is_iterator{})
       {
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index 633af1a..6b874db 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -194,12 +194,14 @@  namespace __debug
       typedef typename _Base::const_iterator	_Base_const_iterator;
 
     public:
+      typedef _Base				normal_type;
+
       typedef typename _Base::reference		reference;
       typedef typename _Base::const_reference	const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_iterator, forward_list>		iterator;
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_const_iterator, forward_list>	const_iterator;
 
       typedef typename _Base::size_type		size_type;
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index ce501f2..6719703 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -31,7 +31,9 @@ 
 
 #include <bits/move.h>		// for __addressof
 #include <bits/stl_function.h>	// for less
+
 #if __cplusplus >= 201103L
+# include <bits/stl_iterator.h>	// for __miter_base
 # include <type_traits>		// for is_lvalue_reference and conditional.
 #endif
 
@@ -64,19 +66,6 @@  namespace __gnu_debug
     __check_singular(const _Tp* __ptr)
     { return __ptr == 0; }
 
-  /** Assume that some arbitrary iterator is dereferenceable, because we
-      can't prove that it isn't. */
-  template<typename _Iterator>
-    inline bool
-    __check_dereferenceable(const _Iterator&)
-    { return true; }
-
-  /** Non-NULL pointers are dereferenceable. */
-  template<typename _Tp>
-    inline bool
-    __check_dereferenceable(const _Tp* __ptr)
-    { return __ptr; }
-
   /* Checks that [first, last) is a valid range, and then returns
    * __first. This routine is useful when we can't use a separate
    * assertion statement because, e.g., we are in a constructor.
@@ -95,9 +84,10 @@  namespace __gnu_debug
     }
 
   /* Handle the case where __other is a pointer to _Sequence::value_type. */
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     inline bool
-    __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator_aux4(const _Safe_tagged_iterator<_Iterator, _Sequence,
+							_Category>& __it,
 			    const typename _Sequence::value_type* __other)
     {
       typedef const typename _Sequence::value_type* _PointerType;
@@ -116,15 +106,18 @@  namespace __gnu_debug
     }
 
   /* Fallback overload for when we can't tell, assume it is valid. */
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     inline bool
-    __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...)
+    __foreign_iterator_aux4(const _Safe_tagged_iterator<_Iterator, _Sequence,
+							_Category>&, ...)
     { return true; }
 
   /* Handle sequences with contiguous storage */
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator_aux3(const _Safe_tagged_iterator<_Iterator, _Sequence,
+							_Category>& __it,
 			    const _InputIterator& __other,
 			    const _InputIterator& __other_end,
 			    std::__true_type)
@@ -137,34 +130,46 @@  namespace __gnu_debug
     }
 
   /* Handle non-contiguous containers, assume it is valid. */
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&,
+    __foreign_iterator_aux3(const _Safe_tagged_iterator<_Iterator, _Sequence,
+							_Category>&,
 			    const _InputIterator&, const _InputIterator&,
 			    std::__false_type)
     { return true; }
 
   /** Handle debug iterators from the same type of container. */
-  template<typename _Iterator, typename _Sequence, typename _OtherIterator>
-    inline bool
-    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
-		const _Safe_iterator<_OtherIterator, _Sequence>& __other,
-		const _Safe_iterator<_OtherIterator, _Sequence>&)
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _OtherIterator>
+    inline bool
+    __foreign_iterator_aux2(const _Safe_tagged_iterator<_Iterator, _Sequence,
+							_Category>& __it,
+			    const _Safe_tagged_iterator<_OtherIterator, _Sequence,
+							_Category>& __other,
+			    const _Safe_tagged_iterator<_OtherIterator, _Sequence,
+							_Category>&)
     { return __it._M_get_sequence() != __other._M_get_sequence(); }
 
   /** Handle debug iterators from different types of container. */
-  template<typename _Iterator, typename _Sequence, typename _OtherIterator,
-	   typename _OtherSequence>
-    inline bool
-    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
-		const _Safe_iterator<_OtherIterator, _OtherSequence>&,
-		const _Safe_iterator<_OtherIterator, _OtherSequence>&)
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _OtherIterator, typename _OtherSequence,
+	   typename _OtherCategory>
+    inline bool
+    __foreign_iterator_aux2(const _Safe_tagged_iterator<_Iterator, _Sequence,
+							_Category>&,
+	const _Safe_tagged_iterator<_OtherIterator, _OtherSequence,
+				    _OtherCategory>&,
+	const _Safe_tagged_iterator<_OtherIterator, _OtherSequence,
+				    _OtherCategory>&)
     { return true; }
 
   /* Handle non-debug iterators. */
-  template<typename _Iterator, typename _Sequence, typename _InputIterator>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator_aux2(const _Safe_tagged_iterator<_Iterator, _Sequence,
+							_Category>& __it,
 			    const _InputIterator& __other,
 			    const _InputIterator& __other_end)
     {
@@ -181,18 +186,21 @@  namespace __gnu_debug
     }
 
   /* Handle the case where we aren't really inserting a range after all */
-  template<typename _Iterator, typename _Sequence, typename _Integral>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _Integral>
     inline bool
-    __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
+    __foreign_iterator_aux(const _Safe_tagged_iterator<_Iterator, _Sequence,
+						       _Category>&,
 			   _Integral, _Integral,
 			   std::__true_type)
     { return true; }
 
   /* Handle all iterators. */
-  template<typename _Iterator, typename _Sequence,
+  template<typename _Iterator, typename _Sequence, typename _Category,
 	   typename _InputIterator>
     inline bool
-    __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator_aux(const _Safe_tagged_iterator<_Iterator, _Sequence,
+						       _Category>& __it,
 			   _InputIterator __other, _InputIterator __other_end,
 			   std::__false_type)
     {
@@ -201,10 +209,11 @@  namespace __gnu_debug
 				   std::__miter_base(__other_end));
     }
 
-  template<typename _Iterator, typename _Sequence,
+  template<typename _Iterator, typename _Sequence, typename _Category,
 	   typename _InputIterator>
     inline bool
-    __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
+    __foreign_iterator(const _Safe_tagged_iterator<_Iterator, _Sequence,
+						   _Category>& __it,
 		       _InputIterator __other, _InputIterator __other_end)
     {
       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
diff --git a/libstdc++-v3/include/debug/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h
index 2073df9..67fbd83 100644
--- a/libstdc++-v3/include/debug/helper_functions.h
+++ b/libstdc++-v3/include/debug/helper_functions.h
@@ -37,8 +37,13 @@ 
 
 namespace __gnu_debug
 {
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    class _Safe_tagged_iterator;
+
+#if __cplusplus >= 201103L
   template<typename _Iterator, typename _Sequence>
-    class _Safe_iterator;
+    class _Safe_local_iterator;
+#endif
 
   /** The precision to which we can calculate the distance between
    *  two iterators.
@@ -83,13 +88,13 @@  namespace __gnu_debug
   */
   template<typename _Iterator>
     inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs,
+    __get_distance(_Iterator __lhs, _Iterator __rhs,
 		   std::random_access_iterator_tag)
     { return std::make_pair(__rhs - __lhs, __dp_exact); }
 
   template<typename _Iterator>
     inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs,
+    __get_distance(_Iterator __lhs, _Iterator __rhs,
 		   std::input_iterator_tag)
     {
       if (__lhs == __rhs)
@@ -100,16 +105,30 @@  namespace __gnu_debug
 
   template<typename _Iterator>
     inline typename _Distance_traits<_Iterator>::__type
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs)
+    __get_distance(_Iterator __lhs, _Iterator __rhs)
     { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); }
 
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    typename _Distance_traits<_Iterator>::__type
+    __get_distance(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					       _Category>&,
+		   const _Safe_tagged_iterator<_Iterator, _Sequence,
+					       _Category>&);
+
+#if __cplusplus >= 201103L
+  template<typename _Iterator, typename _Sequence>
+    typename _Distance_traits<_Iterator>::__type
+    __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>&,
+		   const _Safe_local_iterator<_Iterator, _Sequence>&);
+#endif
+
   /** We say that integral types for a valid range, and defer to other
    *  routines to realize what to do with integral types instead of
    *  iterators.
   */
   template<typename _Integral>
     inline bool
-    __valid_range_aux(const _Integral&, const _Integral&,
+    __valid_range_aux(_Integral, _Integral,
 		      typename _Distance_traits<_Integral>::__type& __dist,
 		      std::__true_type)
     {
@@ -122,8 +141,7 @@  namespace __gnu_debug
   */
   template<typename _InputIterator>
     inline bool
-    __valid_range_aux(const _InputIterator& __first,
-		      const _InputIterator& __last,
+    __valid_range_aux(_InputIterator __first, _InputIterator __last,
 		      typename _Distance_traits<_InputIterator>::__type& __dist,
 		      std::__false_type)
     {
@@ -152,61 +170,73 @@  namespace __gnu_debug
   */
   template<typename _InputIterator>
     inline bool
-    __valid_range(const _InputIterator& __first, const _InputIterator& __last,
+    __valid_range(_InputIterator __first, _InputIterator __last,
 		  typename _Distance_traits<_InputIterator>::__type& __dist)
     {
       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
       return __valid_range_aux(__first, __last, __dist, _Integral());
     }
 
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    bool
+    __valid_range(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>&,
+		  const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>&,
+		  typename _Distance_traits<_Iterator>::__type&);
+
+#if __cplusplus >= 201103L
+  template<typename _Iterator,typename _Sequence>
+    bool
+    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
+		  const _Safe_local_iterator<_Iterator, _Sequence>&,
+		  typename _Distance_traits<_Iterator>::__type&);
+#endif
+
   template<typename _InputIterator>
     inline bool
-    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
+    __valid_range(_InputIterator __first, _InputIterator __last)
     {
       typename _Distance_traits<_InputIterator>::__type __dist;
       return __valid_range(__first, __last, __dist);
     }
 
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    bool
+    __valid_range(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>&,
+		  const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>&);
+
+#if __cplusplus >= 201103L
+  template<typename _Iterator, typename _Sequence>
+    bool
+    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
+		  const _Safe_local_iterator<_Iterator, _Sequence>&);
+#endif
+
   // Fallback method, always ok.
   template<typename _InputIterator, typename _Size>
     inline bool
     __can_advance(_InputIterator, _Size)
     { return true; }
 
-  template<typename _Iterator, typename _Sequence, typename _Size>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _Size>
     bool
-    __can_advance(const _Safe_iterator<_Iterator, _Sequence>&, _Size);
-
-#if __cplusplus < 201103L
-  // Helper struct to detect random access safe iterators.
-  template<typename _Iterator>
-    struct __is_safe_random_iterator
-    {
-      enum { __value = 0 };
-      typedef std::__false_type __type;
-    };
-
-  template<typename _Iterator>
-    struct _Siter_base
-    : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
-    { };
+    __can_advance(const _Safe_tagged_iterator<_Iterator, _Sequence, _Category>&,
+		  _Size);
 
   /** Helper function to extract base iterator of random access safe iterator
-      in order to reduce performance impact of debug mode.  Limited to random
-      access iterator because it is the only category for which it is possible
-      to check for correct iterators order in the __valid_range function
-      thanks to the < operator.
+   *  in order to reduce performance impact of debug mode.  Limited to random
+   *  access iterator because it is the only category for which it is possible
+   *  to check for correct iterators order in the __valid_range function
+   *  thanks to the < operator.
    */
   template<typename _Iterator>
-    inline typename _Siter_base<_Iterator>::iterator_type
-    __base(_Iterator __it)
-    { return _Siter_base<_Iterator>::_S_base(__it); }
-#else
-  template<typename _Iterator>
     inline _Iterator
     __base(_Iterator __it)
     { return __it; }
-#endif
 
 #if __cplusplus < 201103L
   template<typename _Iterator>
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index bf3179a..dd91d5d 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -58,12 +58,14 @@  namespace __debug
       typedef __gnu_debug::_Not_equal_to<_Base_const_iterator>  _Not_equal;
 
     public:
+      typedef _Base					normal_type;
+
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<_Base_iterator, list>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_iterator, list>
 							iterator;
-      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_const_iterator, list>
 							const_iterator;
 
       typedef typename _Base::size_type			size_type;
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 1fd4416..3d0dba2 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -57,6 +57,8 @@  namespace __debug
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
+      typedef _Base					normal_type;
+
       // types:
       typedef _Key					key_type;
       typedef _Tp					mapped_type;
@@ -66,9 +68,9 @@  namespace __debug
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_iterator, map>
 							iterator;
-      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_const_iterator, map>
 							const_iterator;
 
       typedef typename _Base::size_type			size_type;
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index 0994dc4..7531130 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -57,6 +57,8 @@  namespace __debug
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
+      typedef _Base					normal_type;
+
       // types:
       typedef _Key					key_type;
       typedef _Tp					mapped_type;
@@ -66,10 +68,10 @@  namespace __debug
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_iterator, multimap>
 							iterator;
-      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
-					  multimap>	const_iterator;
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_const_iterator, multimap>
+							const_iterator;
 
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::difference_type		difference_type;
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index 6e4c1b0..b1ed3ca 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -56,6 +56,8 @@  namespace __debug
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
+      typedef _Base					normal_type;
+
       // types:
       typedef _Key					key_type;
       typedef _Key					value_type;
@@ -65,10 +67,10 @@  namespace __debug
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_iterator, multiset>
 							iterator;
-      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
-					  multiset>	const_iterator;
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_const_iterator, multiset>
+							const_iterator;
 
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::difference_type		difference_type;
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index b8256fc..430852c 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -38,6 +38,9 @@ 
 
 namespace __gnu_debug
 {
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_iterator;
+
   /** Helper struct to deal with sequence offering a before_begin
    *  iterator.
    **/
@@ -76,7 +79,6 @@  namespace __gnu_debug
    *  %_Safe_iterator has member functions for iterator invalidation,
    *  attaching/detaching the iterator from sequences, and querying
    *  the iterator's state.
-   *
    *  Note that _Iterator must be the first base class so that it gets
    *  initialized before the iterator is being attached to the container's list
    *  of iterators and it is being detached before _Iterator get
@@ -89,10 +91,10 @@  namespace __gnu_debug
     {
       typedef _Iterator _Iter_base;
       typedef _Safe_iterator_base _Safe_base;
-      typedef typename _Sequence::const_iterator _Const_iterator;
 
       typedef std::iterator_traits<_Iterator> _Traits;
 
+    protected:
       struct _Attach_single
       { };
 
@@ -173,7 +175,7 @@  namespace __gnu_debug
 	_Safe_iterator(
 	  const _Safe_iterator<_MutableIterator,
 	  typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
-		      typename _Sequence::iterator::iterator_type>::__value),
+			typename _Sequence::normal_type::iterator>::__value),
 		   _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
 	: _Iter_base(__x.base())
 	{
@@ -279,19 +281,306 @@  namespace __gnu_debug
 	return base().operator->();
       }
 
+      // ------ Utilities ------
+
+      /// Determine if this is a constant iterator.
+      static bool
+      _S_constant()
+      {
+	return std::__are_same<typename _Sequence::normal_type::const_iterator,
+			       _Iterator>::__value;
+      }
+
+      /**
+       * @brief Return the underlying iterator
+       */
+      _Iterator&
+      base() _GLIBCXX_NOEXCEPT { return *this; }
+
+      const _Iterator&
+      base() const _GLIBCXX_NOEXCEPT { return *this; }
+
+      /**
+       * @brief Conversion to underlying non-debug iterator to allow
+       * better interaction with non-debug containers.
+       */
+      operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
+
+      /** Attach iterator to the given sequence. */
+      void
+      _M_attach(_Safe_sequence_base* __seq)
+      { _Safe_base::_M_attach(__seq, _S_constant()); }
+
+      /** Likewise, but not thread-safe. */
+      void
+      _M_attach_single(_Safe_sequence_base* __seq)
+      { _Safe_base::_M_attach_single(__seq, _S_constant()); }
+
+      /// Is the iterator dereferenceable?
+      bool
+      _M_dereferenceable() const
+      { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
+
+      /// Is the iterator before a dereferenceable one?
+      bool
+      _M_before_dereferenceable() const
+      {
+	if (this->_M_incrementable())
+	{
+	  _Iterator __base = base();
+	  return ++__base != _M_get_sequence()->_M_base().end();
+	}
+	return false;
+      }
+
+      /// Is the iterator incrementable?
+      bool
+      _M_incrementable() const
+      { return !this->_M_singular() && !_M_is_end(); }
+
+      // Can we advance the iterator @p __n steps (@p __n may be negative)
+      bool
+      _M_can_advance(const difference_type& __n) const;
+
+      // Is the iterator range [*this, __rhs) valid?
+      bool
+      _M_valid_range(const _Safe_iterator& __rhs,
+		     std::pair<difference_type, _Distance_precision>& __dist,
+		     bool __check_dereferenceable = true) const;
+
+      // The sequence this iterator references.
+      typename __gnu_cxx::__conditional_type<
+	std::__are_same<typename _Sequence::normal_type::const_iterator,
+			_Iterator>::__value,
+	const _Sequence*,
+	_Sequence*>::__type
+      _M_get_sequence() const
+      { return static_cast<_Sequence*>(_M_sequence); }
+
+      /// Is this iterator equal to the sequence's begin() iterator?
+      bool
+      _M_is_begin() const
+      { return base() == _M_get_sequence()->_M_base().begin(); }
+
+      /// Is this iterator equal to the sequence's end() iterator?
+      bool
+      _M_is_end() const
+      { 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>::_S_Is(*this); }
+
+      /// Is this iterator equal to the sequence's before_begin() iterator if
+      /// any or begin() otherwise?
+      bool
+      _M_is_beginnest() const
+      { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
+    };
+
+  template<typename _Iterator, typename _Sequence, typename
+	   = typename std::iterator_traits<_Iterator>::iterator_category>
+    class _Safe_tagged_iterator;
+
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_tagged_iterator<_Iterator, _Sequence, std::forward_iterator_tag>
+    : public _Safe_iterator<_Iterator, _Sequence>
+    {
+      typedef _Safe_iterator<_Iterator, _Sequence> _Safe_base;
+
+    protected:
+      typedef typename _Safe_base::_Attach_single _Attach_single;
+
+      _Safe_tagged_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
+			    _Attach_single)
+      _GLIBCXX_NOEXCEPT
+	: _Safe_base(__i, __seq, _Attach_single())
+      { }
+
+    public:
+      /// @post the iterator is singular and unattached
+      _Safe_tagged_iterator() _GLIBCXX_NOEXCEPT { }
+
+      /**
+       * @brief Safe iterator construction from an unsafe iterator and
+       * its sequence.
+       *
+       * @pre @p seq is not NULL
+       * @post this is not singular
+       */
+      _Safe_tagged_iterator(const _Iterator& __i, const _Safe_sequence_base* __seq)
+      _GLIBCXX_NOEXCEPT
+      : _Safe_base(__i, __seq)
+      { }
+
+      /**
+       * @brief Copy construction.
+       */
+      _Safe_tagged_iterator(const _Safe_tagged_iterator& __x) _GLIBCXX_NOEXCEPT
+      : _Safe_base(__x)
+      { }
+
+#if __cplusplus >= 201103L
+      /** @brief Move construction. */
+      _Safe_tagged_iterator(_Safe_tagged_iterator&&) = default;
+#endif
+
+      /**
+       *  @brief Converting constructor from a mutable iterator to a
+       *  constant iterator.
+      */
+      template<typename _MutableIterator>
+	_Safe_tagged_iterator(
+	  const _Safe_tagged_iterator<_MutableIterator,
+	  typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
+			typename _Sequence::normal_type::iterator>::__value),
+		   _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
+	: _Safe_base(__x)
+        { }
+
+#if __cplusplus >= 201103L
+      /** @brief Copy assignment. */
+      _Safe_tagged_iterator&
+      operator=(const _Safe_tagged_iterator&) = default;
+
+      /** @brief Move assignment. */
+      _Safe_tagged_iterator&
+      operator=(_Safe_tagged_iterator&&) = default;
+#else
+      /**
+       * @brief Copy assignment.
+       */
+      _Safe_tagged_iterator&
+      operator=(const _Safe_tagged_iterator& __x) _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator=(__x);
+	return *this;
+      }
+#endif
+
       // ------ Input iterator requirements ------
       /**
        *  @brief Iterator preincrement
        *  @pre iterator is incrementable
        */
-      _Safe_iterator&
+      _Safe_tagged_iterator&
       operator++() _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	++base();
+	++this->base();
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_tagged_iterator
+      operator++(int) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
+			      _M_message(__msg_bad_inc)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_tagged_iterator(this->base()++, this->_M_sequence,
+				  _Attach_single());
+      }
+    };
+
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_tagged_iterator<_Iterator, _Sequence,
+				std::bidirectional_iterator_tag>
+    : public _Safe_tagged_iterator<_Iterator, _Sequence,
+				   std::forward_iterator_tag>
+    {
+      typedef _Safe_tagged_iterator<_Iterator, _Sequence,
+				    std::forward_iterator_tag> _Safe_base;
+
+    protected:
+      typedef typename _Safe_base::_Attach_single _Attach_single;
+
+      _Safe_tagged_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
+			    _Attach_single)
+      _GLIBCXX_NOEXCEPT
+	: _Safe_base(__i, __seq, _Attach_single())
+      { }
+
+    public:
+      /// @post the iterator is singular and unattached
+      _Safe_tagged_iterator() _GLIBCXX_NOEXCEPT { }
+
+      /**
+       * @brief Safe iterator construction from an unsafe iterator and
+       * its sequence.
+       *
+       * @pre @p seq is not NULL
+       * @post this is not singular
+       */
+      _Safe_tagged_iterator(const _Iterator& __i,
+			    const _Safe_sequence_base* __seq)
+      _GLIBCXX_NOEXCEPT
+	: _Safe_base(__i, __seq)
+      { }
+
+      /**
+       * @brief Copy construction.
+       */
+      _Safe_tagged_iterator(const _Safe_tagged_iterator& __x) _GLIBCXX_NOEXCEPT
+	: _Safe_base(__x)
+      { }
+
+#if __cplusplus >= 201103L
+      /** @brief Move construction. */
+      _Safe_tagged_iterator(_Safe_tagged_iterator&&) = default;
+#endif
+
+      /**
+       *  @brief Converting constructor from a mutable iterator to a
+       *  constant iterator.
+      */
+      template<typename _MutableIterator>
+	_Safe_tagged_iterator(
+	  const _Safe_tagged_iterator<_MutableIterator,
+	  typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
+			typename _Sequence::normal_type::iterator>::__value),
+		   _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
+	  : _Safe_base(__x)
+        { }
+
+#if __cplusplus >= 201103L
+      /** @brief Copy assignment. */
+      _Safe_tagged_iterator&
+      operator=(const _Safe_tagged_iterator&) = default;
+
+      /** @brief Move assignment. */
+      _Safe_tagged_iterator&
+      operator=(_Safe_tagged_iterator&&) = default;
+#else
+      /**
+       * @brief Copy assignment.
+       */
+      _Safe_tagged_iterator&
+      operator=(const _Safe_tagged_iterator& __x) _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator=(__x);
+	return *this;
+      }
+#endif
+
+      // ------ Input iterator requirements ------
+      /**
+       *  @brief Iterator preincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_tagged_iterator&
+      operator++() _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator++();
 	return *this;
       }
 
@@ -299,14 +588,15 @@  namespace __gnu_debug
        *  @brief Iterator postincrement
        *  @pre iterator is incrementable
        */
-      _Safe_iterator
+      _Safe_tagged_iterator
       operator++(int) _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 			      _M_message(__msg_bad_inc)
 			      ._M_iterator(*this, "this"));
 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
+	return _Safe_tagged_iterator(this->base()++, this->_M_sequence,
+				     _Attach_single());
       }
 
       // ------ Bidirectional iterator requirements ------
@@ -314,14 +604,157 @@  namespace __gnu_debug
        *  @brief Iterator predecrement
        *  @pre iterator is decrementable
        */
-      _Safe_iterator&
+      _Safe_tagged_iterator&
       operator--() _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 			      _M_message(__msg_bad_dec)
 			      ._M_iterator(*this, "this"));
 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	--base();
+	--this->base();
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postdecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_tagged_iterator
+      operator--(int) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
+			      _M_message(__msg_bad_dec)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_tagged_iterator(this->base()--, this->_M_sequence,
+				     _Attach_single());
+      }
+
+      // ------ Utilities ------
+
+      // Is the iterator decrementable?
+      bool
+      _M_decrementable() const { return !this->_M_singular() && !this->_M_is_begin(); }
+    };
+
+  template<typename _Iterator, typename _Sequence>
+    class _Safe_tagged_iterator<_Iterator, _Sequence,
+				std::random_access_iterator_tag>
+    : public _Safe_tagged_iterator<_Iterator, _Sequence,
+				   std::bidirectional_iterator_tag>
+    {
+      typedef _Safe_tagged_iterator<_Iterator, _Sequence,
+				    std::bidirectional_iterator_tag> _Safe_base;
+
+      typedef typename _Safe_base::_Attach_single _Attach_single;
+
+      _Safe_tagged_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
+			    _Attach_single)
+      _GLIBCXX_NOEXCEPT
+	: _Safe_base(__i, __seq, _Attach_single())
+      { }
+
+    public:
+      typedef typename _Safe_base::difference_type	difference_type;
+      typedef typename _Safe_base::reference		reference;
+
+      /// @post the iterator is singular and unattached
+      _Safe_tagged_iterator() _GLIBCXX_NOEXCEPT { }
+
+      /**
+       * @brief Safe iterator construction from an unsafe iterator and
+       * its sequence.
+       *
+       * @pre @p seq is not NULL
+       * @post this is not singular
+       */
+      _Safe_tagged_iterator(const _Iterator& __i,
+			    const _Safe_sequence_base* __seq)
+      _GLIBCXX_NOEXCEPT
+	: _Safe_base(__i, __seq)
+      { }
+
+      /**
+       * @brief Copy construction.
+       */
+      _Safe_tagged_iterator(const _Safe_tagged_iterator& __x) _GLIBCXX_NOEXCEPT
+	: _Safe_base(__x)
+      { }
+
+#if __cplusplus >= 201103L
+      /** @brief Move construction. */
+      _Safe_tagged_iterator(_Safe_tagged_iterator&&) = default;
+#endif
+
+      /**
+       *  @brief Converting constructor from a mutable iterator to a
+       *  constant iterator.
+      */
+      template<typename _MutableIterator>
+	_Safe_tagged_iterator(
+	  const _Safe_tagged_iterator<_MutableIterator,
+	  typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
+			typename _Sequence::normal_type::iterator>::__value),
+		   _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
+	  : _Safe_base(__x)
+        { }
+
+#if __cplusplus >= 201103L
+      /** @brief Copy assignment. */
+      _Safe_tagged_iterator&
+      operator=(const _Safe_tagged_iterator&) = default;
+
+      /** @brief Move assignment. */
+      _Safe_tagged_iterator&
+      operator=(_Safe_tagged_iterator&&) = default;
+#else
+      /**
+       * @brief Copy assignment.
+       */
+      _Safe_tagged_iterator&
+      operator=(const _Safe_tagged_iterator& __x) _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator=(__x);
+	return *this;
+      }
+#endif
+
+      // ------ Input iterator requirements ------
+      /**
+       *  @brief Iterator preincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_tagged_iterator&
+      operator++() _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator++();
+	return *this;
+      }
+
+      /**
+       *  @brief Iterator postincrement
+       *  @pre iterator is incrementable
+       */
+      _Safe_tagged_iterator
+      operator++(int) _GLIBCXX_NOEXCEPT
+      {
+	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
+			      _M_message(__msg_bad_inc)
+			      ._M_iterator(*this, "this"));
+	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+	return _Safe_tagged_iterator(this->base()++, this->_M_sequence,
+				     _Attach_single());
+      }
+
+      // ------ Bidirectional iterator requirements ------
+      /**
+       *  @brief Iterator predecrement
+       *  @pre iterator is decrementable
+       */
+      _Safe_tagged_iterator&
+      operator--() _GLIBCXX_NOEXCEPT
+      {
+	_Safe_base::operator--();
 	return *this;
       }
 
@@ -329,14 +762,15 @@  namespace __gnu_debug
        *  @brief Iterator postdecrement
        *  @pre iterator is decrementable
        */
-      _Safe_iterator
+      _Safe_tagged_iterator
       operator--(int) _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 			      _M_message(__msg_bad_dec)
 			      ._M_iterator(*this, "this"));
 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
+	return _Safe_tagged_iterator(this->base()--, this->_M_sequence,
+				     _Attach_single());
       }
 
       // ------ Random access iterator requirements ------
@@ -347,153 +781,54 @@  namespace __gnu_debug
 			      && this->_M_can_advance(__n + 1),
 			      _M_message(__msg_iter_subscript_oob)
 			      ._M_iterator(*this)._M_integer(__n));
-	return base()[__n];
+	return this->base()[__n];
       }
 
-      _Safe_iterator&
+      _Safe_tagged_iterator&
       operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 			      _M_message(__msg_advance_oob)
 			      ._M_iterator(*this)._M_integer(__n));
 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	base() += __n;
+	this->base() += __n;
 	return *this;
       }
 
-      _Safe_iterator
+      _Safe_tagged_iterator
       operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 			      _M_message(__msg_advance_oob)
 			      ._M_iterator(*this)._M_integer(__n));
-	return _Safe_iterator(base() + __n, this->_M_sequence);
+	return _Safe_tagged_iterator(this->base() + __n, this->_M_sequence);
       }
 
-      _Safe_iterator&
+      _Safe_tagged_iterator&
       operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 			      _M_message(__msg_retreat_oob)
 			      ._M_iterator(*this)._M_integer(__n));
 	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
-	base() -= __n;
+	this->base() -= __n;
 	return *this;
       }
 
-      _Safe_iterator
+      _Safe_tagged_iterator
       operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
       {
 	_GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 			      _M_message(__msg_retreat_oob)
 			      ._M_iterator(*this)._M_integer(__n));
-	return _Safe_iterator(base() - __n, this->_M_sequence);
-      }
-
-      // ------ Utilities ------
-
-      /// Determine if this is a constant iterator.
-      static bool
-      _S_constant()
-      { return std::__are_same<_Const_iterator, _Safe_iterator>::__value; }
-
-      /**
-       * @brief Return the underlying iterator
-       */
-      _Iterator&
-      base() _GLIBCXX_NOEXCEPT { return *this; }
-
-      const _Iterator&
-      base() const _GLIBCXX_NOEXCEPT { return *this; }
-
-      /**
-       * @brief Conversion to underlying non-debug iterator to allow
-       * better interaction with non-debug containers.
-       */
-      operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
-
-      /** Attach iterator to the given sequence. */
-      void
-      _M_attach(_Safe_sequence_base* __seq)
-      { _Safe_base::_M_attach(__seq, _S_constant()); }
-
-      /** Likewise, but not thread-safe. */
-      void
-      _M_attach_single(_Safe_sequence_base* __seq)
-      { _Safe_base::_M_attach_single(__seq, _S_constant()); }
-
-      /// Is the iterator dereferenceable?
-      bool
-      _M_dereferenceable() const
-      { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
-
-      /// Is the iterator before a dereferenceable one?
-      bool
-      _M_before_dereferenceable() const
-      {
-	if (this->_M_incrementable())
-	{
-	  _Iterator __base = base();
-	  return ++__base != _M_get_sequence()->_M_base().end();
+	return _Safe_tagged_iterator(this->base() - __n, this->_M_sequence);
       }
-	return false;
-      }
-
-      /// Is the iterator incrementable?
-      bool
-      _M_incrementable() const
-      { return !this->_M_singular() && !_M_is_end(); }
-
-      // Is the iterator decrementable?
-      bool
-      _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
-
-      // Can we advance the iterator @p __n steps (@p __n may be negative)
-      bool
-      _M_can_advance(const difference_type& __n) const;
-
-      // Is the iterator range [*this, __rhs) valid?
-      bool
-      _M_valid_range(const _Safe_iterator& __rhs,
-		     std::pair<difference_type, _Distance_precision>& __dist,
-		     bool __check_dereferenceable = true) const;
-
-      // The sequence this iterator references.
-      typename
-      __gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
-						    _Safe_iterator>::__value,
-				    const _Sequence*,
-				    _Sequence*>::__type
-      _M_get_sequence() const
-      { return static_cast<_Sequence*>(_M_sequence); }
-
-      /// Is this iterator equal to the sequence's begin() iterator?
-      bool
-      _M_is_begin() const
-      { return base() == _M_get_sequence()->_M_base().begin(); }
-
-      /// Is this iterator equal to the sequence's end() iterator?
-      bool
-      _M_is_end() const
-      { 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>::_S_Is(*this); }
-
-      /// Is this iterator equal to the sequence's before_begin() iterator if
-      /// any or begin() otherwise?
-      bool
-      _M_is_beginnest() const
-      { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
     };
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator==(const _Safe_tagged_iterator<_IteratorL, _Sequence>& __lhs,
+	       const _Safe_tagged_iterator<_IteratorR, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -509,8 +844,8 @@  namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator==(const _Safe_tagged_iterator<_Iterator, _Sequence>& __lhs,
+	       const _Safe_tagged_iterator<_Iterator, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -526,8 +861,8 @@  namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator!=(const _Safe_tagged_iterator<_IteratorL, _Sequence>& __lhs,
+	       const _Safe_tagged_iterator<_IteratorR, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -543,8 +878,8 @@  namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator!=(const _Safe_tagged_iterator<_Iterator, _Sequence>& __lhs,
+	       const _Safe_tagged_iterator<_Iterator, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -560,8 +895,10 @@  namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator<(const _Safe_tagged_iterator<_IteratorL, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	      const _Safe_tagged_iterator<_IteratorR, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -577,8 +914,10 @@  namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	      const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator<(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	      const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -594,8 +933,10 @@  namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator<=(const _Safe_tagged_iterator<_IteratorL, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	       const _Safe_tagged_iterator<_IteratorR, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -611,8 +952,10 @@  namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator<=(const _Safe_tagged_iterator<_Iterator, _Sequence,
+				    std::random_access_iterator_tag>& __lhs,
+	       const _Safe_tagged_iterator<_Iterator, _Sequence,
+				    std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -628,8 +971,10 @@  namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator>(const _Safe_tagged_iterator<_IteratorL, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	      const _Safe_tagged_iterator<_IteratorR, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -645,8 +990,10 @@  namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	      const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator>(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	      const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -662,8 +1009,10 @@  namespace __gnu_debug
 
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
     inline bool
-    operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    operator>=(const _Safe_tagged_iterator<_IteratorL, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	       const _Safe_tagged_iterator<_IteratorR, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -679,8 +1028,10 @@  namespace __gnu_debug
 
   template<typename _Iterator, typename _Sequence>
     inline bool
-    operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    operator>=(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	       const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -699,9 +1050,12 @@  namespace __gnu_debug
   // operators but also operator- must accept mixed iterator/const_iterator
   // parameters.
   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
-    inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
-    operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
-	      const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
+    inline typename _Safe_tagged_iterator<_IteratorL, _Sequence,
+			std::random_access_iterator_tag>::difference_type
+    operator-(const _Safe_tagged_iterator<_IteratorL, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	      const _Safe_tagged_iterator<_IteratorR, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -716,9 +1070,12 @@  namespace __gnu_debug
     }
 
   template<typename _Iterator, typename _Sequence>
-     inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
-     operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
-	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    inline typename _Safe_tagged_iterator<_Iterator, _Sequence,
+			std::random_access_iterator_tag>::difference_type
+    operator-(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __lhs,
+	      const _Safe_tagged_iterator<_Iterator, _Sequence,
+					std::random_access_iterator_tag>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
       _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
@@ -733,32 +1090,43 @@  namespace __gnu_debug
     }
 
   template<typename _Iterator, typename _Sequence>
-    inline _Safe_iterator<_Iterator, _Sequence>
-    operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
-	      const _Safe_iterator<_Iterator, _Sequence>& __i) _GLIBCXX_NOEXCEPT
+    inline _Safe_tagged_iterator<_Iterator, _Sequence,
+				 std::random_access_iterator_tag>
+    operator+(typename _Safe_tagged_iterator<_Iterator,_Sequence,
+		std::random_access_iterator_tag>::difference_type __n,
+	      const _Safe_tagged_iterator<_Iterator, _Sequence,
+		std::random_access_iterator_tag>& __i)
+    _GLIBCXX_NOEXCEPT
     { return __i + __n; }
 
-  /** Safe iterators know if they are dereferenceable. */
-  template<typename _Iterator, typename _Sequence>
-    inline bool
-    __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
-    { return __x._M_dereferenceable(); }
-
   /** Safe iterators know how to check if they form a valid range. */
-  template<typename _Iterator, typename _Sequence>
+  template<typename _Iterator, typename _Sequence, typename _Category>
     inline bool
-    __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
-		  const _Safe_iterator<_Iterator, _Sequence>& __last,
+    __valid_range(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>& __first,
+		  const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>& __last,
 		  typename _Distance_traits<_Iterator>::__type& __dist)
     { return __first._M_valid_range(__last, __dist); }
 
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    inline bool
+    __valid_range(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>& __first,
+		  const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>& __last)
+    {
+      typename _Distance_traits<_Iterator>::__type __dist;
+      return __first._M_valid_range(__last, __dist);
+    }
+
   /** Safe iterators can help to get better distance knowledge. */
   template<typename _Iterator, typename _Sequence>
     inline typename _Distance_traits<_Iterator>::__type
     __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
 		   const _Safe_iterator<_Iterator, _Sequence>& __last,
-		   std::random_access_iterator_tag)
-    { return std::make_pair(__last.base() - __first.base(), __dp_exact); }
+		   std::random_access_iterator_tag __tag)
+    { return __get_distance(__first.base(), __last.base(), __tag); }
 
   template<typename _Iterator, typename _Sequence>
     inline typename _Distance_traits<_Iterator>::__type
@@ -814,6 +1182,23 @@  namespace __gnu_debug
       return std::make_pair(1, __dp_equality);
     }
 
+  template<typename _Iterator, typename _Sequence, typename _Category>
+    inline typename _Distance_traits<_Iterator>::__type
+    __get_distance(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					       _Category>& __lhs,
+		   const _Safe_tagged_iterator<_Iterator, _Sequence,
+					       _Category>& __rhs)
+    { return __get_distance(__lhs, __rhs, _Category()); }
+
+  template<typename _Iterator, typename _Sequence>
+    inline typename _Distance_traits<_Iterator>::__type
+    __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
+		   const _Safe_iterator<_Iterator, _Sequence>& __rhs)
+    {
+      return __get_distance(__lhs, __rhs,
+			    std::__iterator_category(__lhs.base()));
+    }
+
   // Get distance from sequence begin to specified iterator.
   template<typename _Iterator, typename _Sequence>
     inline typename _Distance_traits<_Iterator>::__type
@@ -862,47 +1247,29 @@  namespace __gnu_debug
       return __res;
     }
 
-  template<typename _Iterator, typename _Sequence, typename _Size>
+  template<typename _Iterator, typename _Sequence, typename _Category,
+	   typename _Size>
     inline bool
-    __can_advance(const _Safe_iterator<_Iterator, _Sequence>& __it, _Size __n)
+    __can_advance(const _Safe_tagged_iterator<_Iterator, _Sequence,
+					      _Category>& __it,
+		  _Size __n)
     { return __it._M_can_advance(__n); }
 
-#if __cplusplus < 201103L
-  template<typename _Iterator, typename _Sequence>
-    struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
-    : std::__are_same<std::random_access_iterator_tag,
-                      typename std::iterator_traits<_Iterator>::
-		      iterator_category>
-    { };
-#else
   template<typename _Iterator, typename _Sequence>
     _Iterator
-    __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
-	   std::random_access_iterator_tag)
+    __base(const _Safe_tagged_iterator<_Iterator, _Sequence,
+				       std::random_access_iterator_tag>& __it)
     { return __it.base(); }
 
-  template<typename _Iterator, typename _Sequence>
-    const _Safe_iterator<_Iterator, _Sequence>&
-    __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
-	   std::input_iterator_tag)
-    { return __it; }
-
-  template<typename _Iterator, typename _Sequence>
-    auto
-    __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
-    -> decltype(__base(__it, std::__iterator_category(__it)))
-    { return __base(__it, std::__iterator_category(__it)); }
-#endif
-
 #if __cplusplus < 201103L
   template<typename _Iterator, typename _Sequence>
-    struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
+    struct _Unsafe_type<_Safe_tagged_iterator<_Iterator, _Sequence> >
     { typedef _Iterator _Type; };
 #endif
 
   template<typename _Iterator, typename _Sequence>
     inline _Iterator
-    __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
+    __unsafe(const _Safe_tagged_iterator<_Iterator, _Sequence>& __it)
     { return __it.base(); }
 
 } // namespace __gnu_debug
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h
index f9597a6..cbdd8ff 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -431,13 +431,6 @@  namespace __gnu_debug
       return __lhs.base() != __rhs.base();
     }
 
-  /** Safe local iterators know if they are dereferenceable. */
-  template<typename _Iterator, typename _Sequence>
-    inline bool
-    __check_dereferenceable(const _Safe_local_iterator<_Iterator,
-						       _Sequence>& __x)
-    { return __x._M_dereferenceable(); }
-
   /** Safe local iterators know how to check if they form a valid range. */
   template<typename _Iterator, typename _Sequence>
     inline bool
@@ -446,14 +439,21 @@  namespace __gnu_debug
 		  typename _Distance_traits<_Iterator>::__type& __dist_info)
     { return __first._M_valid_range(__last, __dist_info); }
 
+  template<typename _Iterator, typename _Sequence>
+    inline bool
+    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
+		  const _Safe_local_iterator<_Iterator, _Sequence>& __last)
+    {
+      typename _Distance_traits<_Iterator>::__type __dist_info;
+      return __first._M_valid_range(__last, __dist_info);
+    }
+
   /** Safe local iterators need a special method to get distance between each
       other. */
   template<typename _Iterator, typename _Sequence>
-    inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
-		     _Distance_precision>
+    inline typename _Distance_traits<_Iterator>::__type
     __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
-		   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
-		   std::input_iterator_tag)
+		   const _Safe_local_iterator<_Iterator, _Sequence>& __last)
     {
       if (__first.base() == __last.base())
 	return { 0, __dp_exact };
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index 571cc47..8f3d83a 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -56,6 +56,8 @@  namespace __debug
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
+      typedef _Base					normal_type;
+
       // types:
       typedef _Key					key_type;
       typedef _Key					value_type;
@@ -65,9 +67,9 @@  namespace __debug
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_iterator, set>
 							iterator;
-      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
+      typedef __gnu_debug::_Safe_tagged_iterator<_Base_const_iterator, set>
 							const_iterator;
 
       typedef typename _Base::size_type			size_type;
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index f20b000..fd20160 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -52,12 +52,13 @@  namespace __gnu_debug
     __can_advance(const std::reverse_iterator<_Iterator>& __it, _Size __n)
     { return __can_advance(__it.base(), -__n); }
 
-#if __cplusplus < 201103L
-  template<typename _Iterator>
-    struct __is_safe_random_iterator<std::reverse_iterator<_Iterator> >
-      : __is_safe_random_iterator<_Iterator>
-    { };
+  template<typename _Iterator, typename _Sequence>
+    inline std::reverse_iterator<_Iterator>
+    __base(const std::reverse_iterator<_Safe_tagged_iterator<
+	     _Iterator, _Sequence, std::random_access_iterator_tag> >& __it)
+    { return std::reverse_iterator<_Iterator>(__it.base().base()); }
 
+#if __cplusplus < 201103L
   template<typename _Iterator>
     struct _Unsafe_type<std::reverse_iterator<_Iterator> >
     {
@@ -75,12 +76,6 @@  namespace __gnu_debug
 #else
   template<typename _Iterator>
     inline auto
-    __base(const std::reverse_iterator<_Iterator>& __it)
-    -> decltype(std::__make_reverse_iterator(__base(__it.base())))
-    { return std::__make_reverse_iterator(__base(__it.base())); }
-
-  template<typename _Iterator>
-    inline auto
     __unsafe(const std::reverse_iterator<_Iterator>& __it)
     -> decltype(std::__make_reverse_iterator(__unsafe(__it.base())))
     { return std::__make_reverse_iterator(__unsafe(__it.base())); }
@@ -124,11 +119,12 @@  namespace std
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
-  template<typename _Iterator, typename _Container, typename _Sequence>
+  template<typename _Iterator, typename _Container, typename _Sequence,
+	   typename _Category>
     _Iterator
-    __niter_base(const __gnu_debug::_Safe_iterator<
+    __niter_base(const __gnu_debug::_Safe_tagged_iterator<
 		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
-		 _Sequence>&);
+		 _Sequence, _Category>&);
 
 _GLIBCXX_END_NAMESPACE_VERSION
 }
diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string
index 7fa39e3..3d936ce 100644
--- a/libstdc++-v3/include/debug/string
+++ b/libstdc++-v3/include/debug/string
@@ -95,6 +95,8 @@  namespace __gnu_debug
       _Safe;
 
     public:
+      typedef _Base					normal_type;
+
       // types:
       typedef _Traits					traits_type;
       typedef typename _Traits::char_type		value_type;
@@ -106,9 +108,9 @@  namespace __gnu_debug
       typedef typename _Base::pointer			pointer;
       typedef typename _Base::const_pointer		const_pointer;
 
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	typename _Base::iterator, basic_string>		iterator;
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	typename _Base::const_iterator, basic_string>	const_iterator;
 
       typedef std::reverse_iterator<iterator>		reverse_iterator;
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index e4f7c5c..bfc7203 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -67,6 +67,8 @@  namespace __debug
       typedef typename _Base::local_iterator	_Base_local_iterator;
 
     public:
+      typedef _Base					normal_type;
+
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
       typedef typename _Base::key_equal			key_equal;
@@ -75,9 +77,9 @@  namespace __debug
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
 
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_iterator, unordered_map>			iterator;
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_const_iterator, unordered_map>		const_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_local_iterator, unordered_map>		local_iterator;
@@ -753,6 +755,8 @@  namespace __debug
       typedef typename _Base::local_iterator	   _Base_local_iterator;
 
     public:
+      typedef _Base					normal_type;
+
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
       typedef typename _Base::key_equal			key_equal;
@@ -761,9 +765,9 @@  namespace __debug
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
 
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_iterator, unordered_multimap>		iterator;
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_const_iterator, unordered_multimap>	const_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_local_iterator, unordered_multimap>	local_iterator;
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index adafdb7..586bd18 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -67,6 +67,8 @@  namespace __debug
       typedef typename _Base::local_iterator	   _Base_local_iterator;
 
     public:
+      typedef _Base					normal_type;
+
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
       typedef typename _Base::key_equal			key_equal;
@@ -75,9 +77,9 @@  namespace __debug
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
 
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_iterator, unordered_set>			iterator;
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_const_iterator, unordered_set>		const_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_local_iterator, unordered_set>		local_iterator;
@@ -630,6 +632,8 @@  namespace __debug
       typedef typename _Base::local_iterator	_Base_local_iterator;
 
     public:
+      typedef _Base					normal_type;
+
       typedef typename _Base::size_type			size_type;
       typedef typename _Base::hasher			hasher;
       typedef typename _Base::key_equal			key_equal;
@@ -638,9 +642,9 @@  namespace __debug
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
 
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_iterator, unordered_multiset>		iterator;
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_const_iterator, unordered_multiset>	const_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_local_iterator, unordered_multiset>	local_iterator;
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index ced5520..624e4ce 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -128,12 +128,14 @@  namespace __debug
       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 
     public:
+      typedef _Base					normal_type;
+
       typedef typename _Base::reference			reference;
       typedef typename _Base::const_reference		const_reference;
 
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_iterator, vector>				iterator;
-      typedef __gnu_debug::_Safe_iterator<
+      typedef __gnu_debug::_Safe_tagged_iterator<
 	_Base_const_iterator, vector>			const_iterator;
 
       typedef typename _Base::size_type			size_type;
@@ -785,11 +787,12 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
     };
 
- template<typename _Iterator, typename _Container, typename _Sequence>
+ template<typename _Iterator, typename _Container, typename _Sequence,
+	  typename _Category>
     _Iterator
-    __niter_base(const __gnu_debug::_Safe_iterator<
+    __niter_base(const __gnu_debug::_Safe_tagged_iterator<
 		 __gnu_cxx::__normal_iterator<_Iterator, _Container>,
-		 _Sequence>& __it)
+		 _Sequence, _Category>& __it)
     { return std::__niter_base(__it.base()); }
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/testsuite/23_containers/list/68222_neg.cc b/libstdc++-v3/testsuite/23_containers/list/68222_neg.cc
new file mode 100644
index 0000000..d969b6a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/68222_neg.cc
@@ -0,0 +1,37 @@ 
+// Copyright (C) 2018 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do compile { target c++11 } }
+
+#include <list>
+
+void
+test01()
+{
+  // A list of int.
+  const std::list<int> nums = { 1, 2, 3, 4 };
+
+  // Grab the iterator type.
+  using list_itr_type = decltype( std::cbegin( nums ) );
+
+  // Confirm cend returns the same type.
+  static_assert( std::is_same< decltype( std::cend( nums ) ), list_itr_type >::value, "" );
+
+  // The list's iterator type provides a well-formed non-member operator-() with valid return type (long int)
+  using substraction_type
+    = decltype( std::declval<list_itr_type>() - std::declval<list_itr_type>() ); // { dg-error "no match for 'operator-'" }
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc
index 9fb12ed..1d45e74 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/debug_functions.cc
@@ -21,31 +21,6 @@ 
 #include <unordered_set>
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  using namespace __gnu_debug;
-
-  std::unordered_set<int> u = { 0, 1, 2 };
-  VERIFY( __check_dereferenceable(u.begin()) );
-  auto it = u.begin();
-  VERIFY( __check_dereferenceable(it) );
-
-  VERIFY( __check_dereferenceable(u.cbegin()) );
-  auto cit = u.begin();
-  VERIFY( __check_dereferenceable(cit) );
-
-  VERIFY( !__check_dereferenceable(u.end()) );
-  it = u.end();
-  VERIFY( !__check_dereferenceable(it) );
-
-  auto bucket = u.bucket(0);
-  VERIFY( __check_dereferenceable(u.begin(bucket)) );
-  auto lit = u.begin(bucket);
-  VERIFY( __check_dereferenceable(lit) );
-
-  VERIFY( !__check_dereferenceable(u.end(bucket)) );
-}
-
 void test02()
 {
   using namespace __gnu_debug;
@@ -84,7 +59,6 @@  void test02()
 
 int main()
 {
-  test01();
   test02();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc b/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc
index 5127f51..6490414 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/cons/destructible_debug_neg.cc
@@ -45,4 +45,4 @@  test02()
 // { dg-error "value type is destructible" "" { target *-*-* } 0 }
 
 // In Debug Mode the "required from here" errors come from <debug/vector>
-// { dg-error "required from here" "" { target *-*-* } 155 }
+// { dg-error "required from here" "" { target *-*-* } 157 }
diff --git a/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc b/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc
index ea683ee..acbd0d1 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/debug/debug_functions.cc
@@ -20,28 +20,6 @@ 
 #include <vector>
 #include <testsuite_hooks.h>
 
-void test01()
-{
-  using namespace __gnu_debug;
-
-  std::vector<int> v1(3, 1);
-  VERIFY( __check_dereferenceable(v1.begin()) );
-  std::vector<int>::iterator it = v1.begin();
-  VERIFY( __check_dereferenceable(it) );
-
-  VERIFY( !__check_dereferenceable(v1.end()) );
-  it = v1.end();
-  VERIFY( !__check_dereferenceable(it) );
-
-  const volatile int* pi = 0;
-  VERIFY( !__check_dereferenceable(pi) );
-
-  int i;
-  pi = &i;
-
-  VERIFY( __check_dereferenceable(pi) );
-}
-
 void test02()
 {
   using namespace __gnu_debug;
@@ -67,7 +45,6 @@  void test02()
 
 int main()
 {
-  test01();
   test02();
   return 0;
 }
diff --git a/libstdc++-v3/testsuite/util/testsuite_containers.h b/libstdc++-v3/testsuite/util/testsuite_containers.h
index 2dd5a5f..d05d3ac 100644
--- a/libstdc++-v3/testsuite/util/testsuite_containers.h
+++ b/libstdc++-v3/testsuite/util/testsuite_containers.h
@@ -20,6 +20,7 @@ 
 #ifndef _GLIBCXX_TESTSUITE_CONTAINERS_H
 #define _GLIBCXX_TESTSUITE_CONTAINERS_H
 
+#include <bits/boost_concept_check.h>
 #include <cassert>
 #include <testsuite_container_traits.h>
 #include <utility> // for rel_ops.
@@ -192,6 +193,77 @@  namespace __gnu_test
       forward_members_unordered(_Tp& container) { }
     };
 
+  template<typename _Iterator,
+	   bool _Mutable,
+	   typename = typename std::iterator_traits<_Iterator>::iterator_category>
+    struct iterator_concept_checks;
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, false,
+				   std::forward_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_ForwardIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, true,
+				   std::forward_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_Mutable_ForwardIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, false,
+				   std::bidirectional_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_BidirectionalIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, true,
+				   std::bidirectional_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_Mutable_BidirectionalIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, false,
+				   std::random_access_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_RandomAccessIteratorConcept<_Iterator>>();
+      }
+    };
+
+  template<typename _Iterator>
+    struct iterator_concept_checks<_Iterator, true,
+				   std::random_access_iterator_tag>
+    {
+      iterator_concept_checks()
+      {
+	using namespace __gnu_cxx;
+	__function_requires<_Mutable_RandomAccessIteratorConcept<_Iterator>>();
+      }
+    };
+
   template<typename _Tp>
     struct citerator
     {
@@ -210,6 +282,11 @@  namespace __gnu_test
 	  // when comparing iterators.
 	  using namespace std::rel_ops;
 
+	  iterator_concept_checks<typename _Tp::iterator,
+				  !(traits_type::is_associative::value
+				    || traits_type::is_unordered::value)> cc;
+	  iterator_concept_checks<typename _Tp::const_iterator, false> ccc;
+
 	  assert( _S_container.cbegin() == _S_container.begin() );
 	  assert( _S_container.end() == _S_container.cend() );
 	  assert( _S_container.cbegin() != _S_container.cend() );