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() );
Jonathan Wakely Aug. 21, 2018, 9:33 a.m. | #5
On 18/08/18 22:31 +0200, François Dumont wrote:
>Here is the new proposal. It is indeed possible to keep _Safe_iterator 
>and just add a _Category template parameter to it.

While this is still a large patch (obviously, because it's changing a
lot!) I think this version is much easier to understand, and doesn't
add a whole new class unnecessarily. Thanks for updating 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.

Nice.

>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 ?

OK for trunk, thanks again.
François Dumont Aug. 21, 2018, 8:18 p.m. | #6
On 21/08/2018 11:33, Jonathan Wakely wrote:
> On 18/08/18 22:31 +0200, François Dumont wrote:
>> Here is the new proposal. It is indeed possible to keep 
>> _Safe_iterator and just add a _Category template parameter to it.
>
> While this is still a large patch (obviously, because it's changing a
> lot!) I think this version is much easier to understand, and doesn't
> add a whole new class unnecessarily. Thanks for updating 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.
>
> Nice.
>
>> 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 ?
>
> OK for trunk, thanks again.
>
>
>
Note that it also avoids to adapt the pretty printers scripts.

I'll commit it tomorrow once I'll have rework the ChangeLog entry. I'll 
also add the test case in PR 68222 adapted for the testsuite.

François
Jonathan Wakely Aug. 23, 2018, 3:23 p.m. | #7
On 23/08/18 15:29 +0100, Jonathan Wakely wrote:
>On 23/08/18 08:51 +0100, Jonathan Wakely wrote:
>>On 21/08/18 22:18 +0200, François Dumont wrote:
>>>On 21/08/2018 11:33, Jonathan Wakely wrote:
>>>>On 18/08/18 22:31 +0200, François Dumont wrote:
>>>>>Here is the new proposal. It is indeed possible to keep 
>>>>>_Safe_iterator and just add a _Category template parameter to 
>>>>>it.
>>>>
>>>>While this is still a large patch (obviously, because it's changing a
>>>>lot!) I think this version is much easier to understand, and doesn't
>>>>add a whole new class unnecessarily. Thanks for updating 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.
>>>>
>>>>Nice.
>>>>
>>>>>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 ?
>>>>
>>>>OK for trunk, thanks again.
>>>>
>>>>
>>>>
>>>Note that it also avoids to adapt the pretty printers scripts.
>>>
>>>I'll commit it tomorrow once I'll have rework the ChangeLog entry. 
>>>I'll also add the test case in PR 68222 adapted for the testsuite.
>>
>>I'm not sure when it started, but I'm seeing a few failures in the
>>testsuite, with linker errors like this:
>>
>>FAIL: 25_algorithms/sort/34636.cc (test for excess errors)
>>Excess errors:
>>/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_algobase.h:614: undefined reference to `std::__debug::vector<int, std::allocator<int> >* std::__niter_base<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >(__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::random_access_iterator_tag> const&)'
>>/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_algobase.h:614: undefined reference to `std::__debug::vector<int, std::allocator<int> >* std::__niter_base<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >(__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::random_access_iterator_tag> const&)'
>>/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_algobase.h:614: undefined reference to `std::__debug::vector<int, std::allocator<int> >* std::__niter_base<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >(__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::random_access_iterator_tag> const&)'
>>/home/jwakely/src/gcc/build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_algobase.h:286: undefined reference to `std::__debug::vector<int, std::allocator<int> >* std::__niter_base<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >(__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<std::__debug::vector<int, std::allocator<int> >*, std::__cxx1998::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > > >, std::__debug::vector<std::__debug::vector<int, std::allocator<int> >, std::allocator<std::__debug::vector<int, std::allocator<int> > > >, std::random_access_iterator_tag> const&)'
>>collect2: error: ld returned 1 exit status
>>
>>This happens when run like:
>>
>>make check RUNTESTFLAGS="conformance.exp==25_algorithms/sort/*.cc --target_board=unix/-std=gnu++98/-D_GLIBCXX_USE_CXX11_ABI=0/-D_GLIBCXX_DEBUG"
>
>Seems to be caused by r262349
>
>   2018-07-03  François Dumont
>
>           * include/bits/stl_algobase.h (__niter_wrap): New.
>           (__copy_move_a2(_II, _II, _OI)): Use latter.
>           (__copy_move_backward_a2(_BI1, _BI1, _BI2)): Likewise.
>           (fill_n(_OI, _Size, const _Tp&)): Likewise.
>           (equal(_II1, _II1, _II2)): Use __glibcxx_requires_can_increment.
>           * include/debug/stl_iterator.h
>           (std::__niter_base(const __gnu_cxx::_Safe_iterator<
>           __gnu_cxx::__normal_iterator<>, _Sequence>&)): New declaration.
>           * include/debug/vector (__niter_base(const __gnu_cxx::_Safe_iterator<
>           __gnu_cxx::__normal_iterator<>, _Sequence>&)): New.
>
>
>I think because include/debug/stl_iterator.h declares the __niter_base
>overload unconditionally, but then include/debug/vector only defines
>it for C++11 and later.

Fixed by this patch. Tested x86_64-linux, committed to trunk.
commit ef605abf0a3ae6ee05996f7e9bdef8bdc13e37df
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Aug 23 16:11:22 2018 +0100

    Define debug mode function for C++98
    
    This function is declared unconditionally but was only defined for C++11
    and later, leading to linker errors when the testsuite was run with
    -std=gnu++98 -D_GLIBCXX_DEBUG added to the flags.
    
            * include/debug/vector (__niter_base): Define for C++98.

diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index bd09b2414fc..e8d0928c7c0 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -774,9 +774,9 @@ namespace __debug
 
 } // namespace __debug
 
-#if __cplusplus >= 201103L
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
+#if __cplusplus >= 201103L
   // DR 1182.
   /// std::hash specialization for vector<bool>.
   template<typename _Alloc>
@@ -787,6 +787,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
       { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
     };
+#endif
 
  template<typename _Iterator, typename _Container, typename _Sequence>
     _Iterator
@@ -796,8 +797,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     { return std::__niter_base(__it.base()); }
 
 _GLIBCXX_END_NAMESPACE_VERSION
-#endif
-
 } // namespace std
 
 namespace __gnu_debug

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() );