re PR libstdc++/68222 (_Safe_iterator provides operators the wrapped iterator can't actually support)

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

	PR libstdc++/68222
	* include/debug/safe_iterator.h
	(_Safe_iterator<_It, _Sq, _Cat>): Add category template parameter.
	(_Safe_iterator<>::_Const_iterator): Remove.
	(_Safe_iterator<>::_IsConstant): New.
	(_Safe_iterator<>::_OtherIterator): New.
	(_Safe_iterator<_It, _Sq, _Cat>::_Safe_iterator<_MutIte>(
	const _Safe_iterator<_MutIte, _Sq, _Cat>&)): Add _IsConstant::__value in
	__gnu_cxx::__enable_if condition.
	(_Safe_iterator<_It, _Sq, _Cat>::_M_get_distance_to): New.
	(_Safe_iterator<_It, _Sq, _Cat>::_M_get_distance_from_begin): New.
	(_Safe_iterator<_It, _Sq, _Cat>::_M_get_distance_to_end): New.
	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>): New.
	(_Safe_iterator<_It, _Sq, _Cat>::operator--()): Move...
	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>
	::operator--()): ...here.
	(_Safe_iterator<_It, _Sq, _Cat>::operator--(int)): Move...
	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>
	::operator--(int)): ...here.
	(_Safe_iterator<_It, _Sq, _Cat>::_M_decrementable()): Move...
	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>
	::_M_decrementable()): ...here.
	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>): New.
	(_Safe_iterator<_It, _Sq, _Cat>::operator[](const difference_type&)):
	Move...
	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator[](const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq, _Cat>::operator+=(const difference_type&)):
	Move...
	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator+=(const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq, _Cat>::operator+(const difference_type&)):
	Move...
	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator+(const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq, _Cat>::operator-=(const difference_type&)):
	Move...
	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator-=(const difference_type&)): ...here.
	(_Safe_iterator<_It, _Sq, _Cat>::operator-(const difference_type&)):
	Move...
	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
	::operator-(const difference_type&)): ...here.
	(operator<(const _Safe_iterator<>&, const _Safe_iterator<>&)):
	Constraint to random access iterators.
	(operator<=(const _Safe_iterator<>&, const _Safe_iterator<>&)):
	Likewise.
	(operator>(const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
	(operator>=(const _Safe_iterator<>&, const _Safe_iterator<>&)):
	Likewise.
	(operator-(const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
	(operator+(const difference_type&, const _Safe_iterator<>&)): Likewise.
	(__check_dereferenceable(const _Safe_iterator<>&)): Remove.
	(__get_distance): Remove.
	(__get_distance_from_begin): Remove.
	(__get_distance_to_end): Remove.
	(struct __is_safe_random_iterator<_Safe_iterator<>>): Remove partial
	specialization.
	(__base(const _Safe_iterator<>&, std::input_iterator_tag)): Remove.
	(__base(const _Safe_iterator<>&, std::random_access_iterator_tag)): Remove.
	(__base(const _Safe_iterator<>&)): Constraint to random access iterator.
	* include/debug/safe_iterator.tcc
	(_Safe_iterator<>::_M_get_distance_from_begin()): New.
	(_Safe_iterator<>::_M_get_distance_to_end()): New.
	(_Safe_iterator<>::_M_get_distance_to(const _Safe_iterator<>&)): New.
	(_Safe_iterator<_It, _Seq, std::random_access_iterator_tag>
	::_M_valid_range): New.
	* include/debug/safe_local_iterator.h
	(_Safe_local_iterator<>::_Const_local_iterator): Remove.
	(_Safe_local_iterator<>::_IsConstant): New.
	(_Safe_local_iterator<>::_OtherIterator): New.
	(_Safe_local_iterator<_It, _Cont>::_Safe_local_iterator<_MutIte, _Cont>(
	const _Safe_local_iterator<_MutIte, _Seq>&)): Add _IsConstant::__value
	in __gnu_cxx::__enable_if condition. If singular compare base iterator
	with _MutIte rather than _It.
	(_Safe_local_iterator<>::_S_constant): Make constexpr.
	(_Safe_local_iterator<>::_M_get_distance_to): New.
	(__check_dereferenceable(const _Safe_local_iterator<>&)): Remove.
	(__get_distance(const _Safe_local_iterator<>&,
	const _Safe_local_iterator<>&, std::input_iterator_tag)): Remove.
	(__valid_range(const _Safe_local_iterator<>&,
	const _Safe_local_iterator<>&)): New.
	* include/debug/safe_local_iterator.tcc
	(_Safe_local_iterator<>::_M_get_distance_to): New.
	* include/debug/deque (std::__debug::deque<>): Add
	::__gnu_debug::_Safe_iterator<> friend declaration.
	* include/debug/forward_list (std::__debug::forward_list<>): Likewise.
	* include/debug/list (std::__debug::list<>): Likewise.
	* include/debug/map.h (std::__debug::map<>): Likewise.
	* include/debug/multimap.h (std::__debug::multimap<>): Likewise.
	* include/debug/set.h (std::__debug::set<>): Likewise.
	* include/debug/multiset.h (std::__debug::multiset<>): Likewise.
	* include/debug/string (std::__debug::basic_string<>): Likewise.
	* include/debug/unordered_map (std::__debug::unordered_map<>): Likewise
	and add ::__gnu_debug::_Safe_local_iterator<> friend declaration.
	(std::__debug::unordered_multimap<>): Likewise.
	* include/debug/unordered_set (std::__debug::unordered_set<>): Likewise.
	(std::__debug::unordered_multiset<>): Likewise.
	* include/debug/formatter.h: Adapt.
	* include/debug/helper_functions.h
	(__gnu_debug::_Safe_local_iterator<>): Add declaration.
	(__get_distance<_Ite>(_Ite, _Ite, std::random_access_iterator_tag):
	Pass parameter by copy.
	(__get_distance<_Ite>(_Ite, _Ite, std::input_iterator_tag): Likewise.
	(__get_distance<_Ite>(_Ite, _Ite): Likewise.
	(__valid_range_aux<_Integral>): Pass _Integral by copy.
	(__valid_range<_InputIterator>): Pass _InputIterator by copy.
	(__valid_range<>(const _Safe_iterator<>&,
	const _Safe_iterator<>&, typename _Distance_traits<>::__type&)):
	Declare.
	(__valid_range(const _Safe_local_iterator<>&,
	const _Safe_local_iterator<>&, typename _Distance_traits<>::__type&)):
	Declare.
	(__valid_range<>(const _Safe_iterator<>&, const _Safe_iterator<>&)):
	Declare.
	(__valid_range(const _Safe_local_iterator<>&, const _Safe_local_iterator<>&)):
	Declare.
	(__can_advance): Adapt.
	(struct __is_safe_random_iterator<>): Remove.
	(struct _SIter_base<>): Remove.
	* include/debug/functions.h: Include <bits/stl_iterator.h>.
	(__check_dereferenceable): Remove.
	(__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_iterator<_It, _Sq>)):
	Constraint for random access iterators.
	(__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.
	* testsuite/23_containers/unordered_set/debug/debug_functions.cc:
	(test01): Remove.
	* testsuite/23_containers/vector/debug/debug_functions.cc (test01):
	Remove.

From-SVN: r263786

25 files changed, 1093 insertions, 537 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index ec29980..4639c5e 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,148 @@
+2018-08-22  François Dumont  <fdumont@gcc.gnu.org>
+
+	PR libstdc++/68222
+	* include/debug/safe_iterator.h
+	(_Safe_iterator<_It, _Sq, _Cat>): Add category template parameter.
+	(_Safe_iterator<>::_Const_iterator): Remove.
+	(_Safe_iterator<>::_IsConstant): New.
+	(_Safe_iterator<>::_OtherIterator): New.
+	(_Safe_iterator<_It, _Sq, _Cat>::_Safe_iterator<_MutIte>(
+	const _Safe_iterator<_MutIte, _Sq, _Cat>&)): Add _IsConstant::__value in
+	__gnu_cxx::__enable_if condition.
+	(_Safe_iterator<_It, _Sq, _Cat>::_M_get_distance_to): New.
+	(_Safe_iterator<_It, _Sq, _Cat>::_M_get_distance_from_begin): New.
+	(_Safe_iterator<_It, _Sq, _Cat>::_M_get_distance_to_end): New.
+	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>): New.
+	(_Safe_iterator<_It, _Sq, _Cat>::operator--()): Move...
+	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>
+	::operator--()): ...here.
+	(_Safe_iterator<_It, _Sq, _Cat>::operator--(int)): Move...
+	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>
+	::operator--(int)): ...here.
+	(_Safe_iterator<_It, _Sq, _Cat>::_M_decrementable()): Move...
+	(_Safe_iterator<_It, _Sq, std::bidirectional_iterator_tag>
+	::_M_decrementable()): ...here.
+	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>): New.
+	(_Safe_iterator<_It, _Sq, _Cat>::operator[](const difference_type&)):
+	Move...
+	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
+	::operator[](const difference_type&)): ...here.
+	(_Safe_iterator<_It, _Sq, _Cat>::operator+=(const difference_type&)):
+	Move...
+	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
+	::operator+=(const difference_type&)): ...here.
+	(_Safe_iterator<_It, _Sq, _Cat>::operator+(const difference_type&)):
+	Move...
+	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
+	::operator+(const difference_type&)): ...here.
+	(_Safe_iterator<_It, _Sq, _Cat>::operator-=(const difference_type&)):
+	Move...
+	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
+	::operator-=(const difference_type&)): ...here.
+	(_Safe_iterator<_It, _Sq, _Cat>::operator-(const difference_type&)):
+	Move...
+	(_Safe_iterator<_It, _Sq, std::random_access_iterator_tag>
+	::operator-(const difference_type&)): ...here.
+	(operator<(const _Safe_iterator<>&, const _Safe_iterator<>&)):
+	Constraint to random access iterators.
+	(operator<=(const _Safe_iterator<>&, const _Safe_iterator<>&)):
+	Likewise.
+	(operator>(const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
+	(operator>=(const _Safe_iterator<>&, const _Safe_iterator<>&)):
+	Likewise.
+	(operator-(const _Safe_iterator<>&, const _Safe_iterator<>&)): Likewise.
+	(operator+(const difference_type&, const _Safe_iterator<>&)): Likewise.
+	(__check_dereferenceable(const _Safe_iterator<>&)): Remove.
+	(__get_distance): Remove.
+	(__get_distance_from_begin): Remove.
+	(__get_distance_to_end): Remove.
+	(struct __is_safe_random_iterator<_Safe_iterator<>>): Remove partial
+	specialization.
+	(__base(const _Safe_iterator<>&, std::input_iterator_tag)): Remove.
+	(__base(const _Safe_iterator<>&, std::random_access_iterator_tag)): Remove.
+	(__base(const _Safe_iterator<>&)): Constraint to random access iterator.
+	* include/debug/safe_iterator.tcc
+	(_Safe_iterator<>::_M_get_distance_from_begin()): New.
+	(_Safe_iterator<>::_M_get_distance_to_end()): New.
+	(_Safe_iterator<>::_M_get_distance_to(const _Safe_iterator<>&)): New.
+	(_Safe_iterator<_It, _Seq, std::random_access_iterator_tag>
+	::_M_valid_range): New.
+	* include/debug/safe_local_iterator.h
+	(_Safe_local_iterator<>::_Const_local_iterator): Remove.
+	(_Safe_local_iterator<>::_IsConstant): New.
+	(_Safe_local_iterator<>::_OtherIterator): New.
+	(_Safe_local_iterator<_It, _Cont>::_Safe_local_iterator<_MutIte, _Cont>(
+	const _Safe_local_iterator<_MutIte, _Seq>&)): Add _IsConstant::__value
+	in __gnu_cxx::__enable_if condition. If singular compare base iterator
+	with _MutIte rather than _It.
+	(_Safe_local_iterator<>::_S_constant): Make constexpr.
+	(_Safe_local_iterator<>::_M_get_distance_to): New.
+	(__check_dereferenceable(const _Safe_local_iterator<>&)): Remove.
+	(__get_distance(const _Safe_local_iterator<>&,
+	const _Safe_local_iterator<>&, std::input_iterator_tag)): Remove.
+	(__valid_range(const _Safe_local_iterator<>&,
+	const _Safe_local_iterator<>&)): New.
+	* include/debug/safe_local_iterator.tcc
+	(_Safe_local_iterator<>::_M_get_distance_to): New.
+	* include/debug/deque (std::__debug::deque<>): Add
+	::__gnu_debug::_Safe_iterator<> friend declaration.
+	* include/debug/forward_list (std::__debug::forward_list<>): Likewise.
+	* include/debug/list (std::__debug::list<>): Likewise.
+	* include/debug/map.h (std::__debug::map<>): Likewise.
+	* include/debug/multimap.h (std::__debug::multimap<>): Likewise.
+	* include/debug/set.h (std::__debug::set<>): Likewise.
+	* include/debug/multiset.h (std::__debug::multiset<>): Likewise.
+	* include/debug/string (std::__debug::basic_string<>): Likewise.
+	* include/debug/unordered_map (std::__debug::unordered_map<>): Likewise
+	and add ::__gnu_debug::_Safe_local_iterator<> friend declaration.
+	(std::__debug::unordered_multimap<>): Likewise.
+	* include/debug/unordered_set (std::__debug::unordered_set<>): Likewise.
+	(std::__debug::unordered_multiset<>): Likewise.
+	* include/debug/formatter.h: Adapt.
+	* include/debug/helper_functions.h
+	(__gnu_debug::_Safe_local_iterator<>): Add declaration.
+	(__get_distance<_Ite>(_Ite, _Ite, std::random_access_iterator_tag):
+	Pass parameter by copy.
+	(__get_distance<_Ite>(_Ite, _Ite, std::input_iterator_tag): Likewise.
+	(__get_distance<_Ite>(_Ite, _Ite): Likewise.
+	(__valid_range_aux<_Integral>): Pass _Integral by copy.
+	(__valid_range<_InputIterator>): Pass _InputIterator by copy.
+	(__valid_range<>(const _Safe_iterator<>&,
+	const _Safe_iterator<>&, typename _Distance_traits<>::__type&)):
+	Declare.
+	(__valid_range(const _Safe_local_iterator<>&,
+	const _Safe_local_iterator<>&, typename _Distance_traits<>::__type&)):
+	Declare.
+	(__valid_range<>(const _Safe_iterator<>&, const _Safe_iterator<>&)):
+	Declare.
+	(__valid_range(const _Safe_local_iterator<>&, const _Safe_local_iterator<>&)):
+	Declare.
+	(__can_advance): Adapt.
+	(struct __is_safe_random_iterator<>): Remove.
+	(struct _SIter_base<>): Remove.
+	* include/debug/functions.h: Include <bits/stl_iterator.h>.
+	(__check_dereferenceable): Remove.
+	(__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_iterator<_It, _Sq>)):
+	Constraint for random access iterators.
+	(__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.
+	* testsuite/23_containers/unordered_set/debug/debug_functions.cc:
+	(test01): Remove.
+	* testsuite/23_containers/vector/debug/debug_functions.cc (test01):
+	Remove.
+
 2018-08-22  Jonathan Wakely  <jwakely@redhat.com>
 
 	PR libstdc++/77854
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 383a340..1f03f25 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>
@@ -263,8 +263,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()
 	{
@@ -378,10 +378,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,
-		   const char* __name, _Is_iterator)
+      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{})
 	{
 	  _M_variant._M_iterator._M_type
@@ -396,10 +396,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,
-		   const char* __name, _Is_iterator)
+      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{})
       {
 	_M_variant._M_iterator._M_type
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index 75d4f63..840ed09 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,10 +84,11 @@ 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,
-			    const typename _Sequence::value_type* __other)
+    __foreign_iterator_aux4(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+	const typename _Sequence::value_type* __other)
     {
       typedef const typename _Sequence::value_type* _PointerType;
       typedef std::less<_PointerType> _Less;
@@ -116,18 +106,20 @@ 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,
-			    std::__true_type)
+    __foreign_iterator_aux3(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+	const _InputIterator& __other, const _InputIterator& __other_end,
+	std::__true_type)
     {
       if (__other == __other_end)
 	return true;  // inserting nothing is safe even if not foreign iters
@@ -137,36 +129,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>&,
-			    const _InputIterator&, const _InputIterator&,
-			    std::__false_type)
+    __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,
-			    const _InputIterator& __other,
-			    const _InputIterator& __other_end)
+    __foreign_iterator_aux2(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+	const _InputIterator& __other,
+	const _InputIterator& __other_end)
     {
 #if __cplusplus < 201103L
       typedef _Is_contiguous_sequence<_Sequence> __tag;
@@ -181,31 +183,34 @@ 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,
-			   _InputIterator __other, _InputIterator __other_end,
-			   std::__false_type)
+    __foreign_iterator_aux(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+	_InputIterator __other, _InputIterator __other_end,
+	std::__false_type)
     {
       return _Insert_range_from_self_is_safe<_Sequence>::__value
 	|| __foreign_iterator_aux2(__it, std::__miter_base(__other),
 				   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,
-		       _InputIterator __other, _InputIterator __other_end)
+    __foreign_iterator(
+	const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
+	_InputIterator __other, _InputIterator __other_end)
     {
       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
       return __foreign_iterator_aux(__it, __other, __other_end, _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.
-  */
-  template<typename _Iterator>
-    inline typename _Siter_base<_Iterator>::iterator_type
-    __base(_Iterator __it)
-    { return _Siter_base<_Iterator>::_S_base(__it); }
-#else
+   *  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 _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 80fa304..e6df4dc 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 23966ba..f4b4e8d 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 8054984..992ccf0 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..86211b9 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(); }
     };
 
@@ -82,22 +82,30 @@ namespace __gnu_debug
    *  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 _Category
+	   = 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 +128,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())
       {
@@ -171,10 +179,11 @@ 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
+	  const _Safe_iterator<_MutableIterator, _Sequence,
+	  typename __gnu_cxx::__enable_if<_IsConstant::__value &&
+	    std::__are_same<_MutableIterator, _OtherIterator>::__value,
+					  _Category>::__type>& __x)
+	_GLIBCXX_NOEXCEPT
 	: _Iter_base(__x.base())
 	{
 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -309,93 +318,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 +372,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 +383,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,13 +423,346 @@ 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, _Sequence,
+	  typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
+	    std::__are_same<_MutableIterator, _OtherIterator>::__value,
+			       std::bidirectional_iterator_tag>::__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)
+      {
+	_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, _Sequence,
+	    typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
+	      std::__are_same<_MutableIterator, _OtherIterator>::__value,
+			       std::random_access_iterator_tag>::__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)
+      {
+	_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,
 	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
-      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_compare_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -513,7 +779,7 @@ namespace __gnu_debug
 	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
-      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_compare_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -530,7 +796,7 @@ namespace __gnu_debug
 	       const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
-      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_compare_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -547,7 +813,7 @@ namespace __gnu_debug
 	       const _Safe_iterator<_Iterator, _Sequence>& __rhs)
     _GLIBCXX_NOEXCEPT
     {
-      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_compare_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -560,11 +826,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -577,11 +845,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -594,11 +864,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -611,11 +883,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -628,11 +902,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -645,11 +921,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -662,11 +940,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -679,11 +959,13 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_order_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -699,12 +981,15 @@ 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(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_distance_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -715,185 +1000,69 @@ namespace __gnu_debug
       return __lhs.base() - __rhs.base();
     }
 
-   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)
+  template<typename _Iterator, typename _Sequence>
+    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(),
-			     _M_message(__msg_distance_bad)
-			     ._M_iterator(__lhs, "lhs")
-			     ._M_iterator(__rhs, "rhs"));
-       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
-			     _M_message(__msg_distance_different)
-			     ._M_iterator(__lhs, "lhs")
-			     ._M_iterator(__rhs, "rhs"));
-       return __lhs.base() - __rhs.base();
-     }
+    {
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
+			    _M_message(__msg_distance_bad)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
+			    _M_message(__msg_distance_different)
+			    ._M_iterator(__lhs, "lhs")
+			    ._M_iterator(__rhs, "rhs"));
+      return __lhs.base() - __rhs.base();
+    }
 
   template<typename _Iterator, typename _Sequence>
-    inline _Safe_iterator<_Iterator, _Sequence>
-    operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
-	      const _Safe_iterator<_Iterator, _Sequence>& __i) _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)
-    {
-      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;
-    }
-
-  // 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)
+  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 _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;
+      typename _Distance_traits<_Iterator>::__type __dist;
+      return __first._M_valid_range(__last, __dist);
     }
 
-  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); }
 
@@ -396,7 +401,7 @@ namespace __gnu_debug
     operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs,
 	       const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs)
     {
-      _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
+      _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(),
 			    _M_message(__msg_iter_compare_bad)
 			    ._M_iterator(__lhs, "lhs")
 			    ._M_iterator(__rhs, "rhs"));
@@ -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)
+    inline bool
+    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
+		  const _Safe_local_iterator<_Iterator, _Sequence>& __last)
     {
-      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
-	      {
-		-__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;
@@ -768,7 +778,7 @@ namespace __debug
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_local_iterator, unordered_multimap>	local_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
-	_Base_const_local_iterator, unordered_multimap> const_local_iterator;
+	_Base_const_local_iterator, unordered_multimap>	const_local_iterator;
 
       unordered_multimap() = default;
 
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;
@@ -645,7 +655,7 @@ namespace __debug
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_local_iterator, unordered_multiset>	local_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
-	_Base_const_local_iterator, unordered_multiset> const_local_iterator;
+	_Base_const_local_iterator, unordered_multiset>	const_local_iterator;
 
       unordered_multiset() = default;
 
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/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..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 89c88cc..759f4d6 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>
 
@@ -191,6 +192,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
     {