2015-06-29 François Dumont <fdumont@gcc.gnu.org>

	* include/bits/stl_iterator_base_types.h (_Iter_base): Limit definition
	to pre-C++11 mode.
	* include/debug/functions.h
	(__gnu_debug::__valid_range, __gnu_debug::__base): Move...
	* include/debug/safe_iterator.h
	(__gnu_debug::_Sequence_traits): New.
	(__gnu_debug::__get_distance_from_begin): New.
	(__gnu_debug::__get_distance_to_end): New.
	(__gnu_debug::_Safe_iterator<>::_M_valid_range): Expose iterator range
	distance information. Add optional check_dereferenceable parameter,
	default true.
	(__gnu_debug::_Distance_precision, __gnu_debug::__get_distance): Move
	default definition...
	(__gnu_debug::__get_distance): New overload for _Safe_iterator.
	(__gnu_debug::__unsafe): Likewise.
	* include/debug/helper_functions.h: ...here. New.
	(__gnu_debug::__unsafe): New helper function to remove safe iterator
	layer.
	* include/debug/stl_iterator.h: New. Include latter.
	* include/bits/stl_iterator.h: Include latter in debug mode.
	* include/debug/stl_iterator.tcc: Adapt.
	* include/debug/safe_local_iterator.h (__gnu_debug::__get_distance): Add
	overload for _Safe_local_iterator.
	(__gnu_debug::__unsafe): Likewise.
	* include/debug/safe_local_iterator.tcc: Adapt.
	* include/debug/macros.h (__glibcxx_check_valid_range2): New.
	(__glibcxx_check_insert_range): Add _Dist parameter.
	(__glibcxx_check_insert_range_after): Likewise.
	(__glibcxx_check_string, __glibcxx_check_string_len): Implement using
	_GLIBCXX_DEBUG_PEDASSERT.
	* include/debug/deque (deque<>::assign): Remove iterator debug layer
	when possible.
	(deque<>::insert): Likewise.
	* include/debug/forward_list (__glibcxx_check_valid_fl_range): New.
	(forward_list<>::splice_after): Use latter.
	(forward_list<>::assign): Remove iterator debug layer when possible.
	(forward_list<>::insert_after): Likewise.
	(__gnu_debug::_Sequence_traits<>): Partial specialization.
	* include/debug/list (list<>::assign): Remove iterator debug layer when
	possible.
	(list<>::insert): Likewise.
	[__gnu_debug::_Sequence_traits<>]: Partial specialization pre C++11 ABI.
	* include/debug/map.h (map<>::insert): Remove iterator debug layer when
	possible.
	* include/debug/multimap.h (multimap<>::insert): Likewise.
	* include/debug/set.h (set<>::insert): Likewise.
	* include/debug/multiset.h (multiset<>::insert): Likewise.
	* include/debug/string (basic_string<>::append, basic_string<>::assign,
	basic_string<>::insert, basic_string<>::replace): Likewise.
	* include/debug/unordered_map
	(unordered_map<>::insert, unordered_multimap<>::insert): Likewise.
	* include/debug/unordered_set
	(unordered_set<>::insert, unordered_multiset<>insert): Likewise.
	* include/debug/vector
	(vector<>::assign, vector<>::insert): Likewise.
	* include/Makefile.am: Add new debug headers.
	* include/Makefile.in: Regenerate.


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

24 files changed, 904 insertions, 246 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 9e76cc4d27e..90a6e9a877c 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,63 @@
+2015-06-29  François Dumont  <fdumont@gcc.gnu.org>
+
+	* include/bits/stl_iterator_base_types.h (_Iter_base): Limit definition
+	to pre-C++11 mode.
+	* include/debug/functions.h
+	(__gnu_debug::__valid_range, __gnu_debug::__base): Move...
+	* include/debug/safe_iterator.h
+	(__gnu_debug::_Sequence_traits): New.
+	(__gnu_debug::__get_distance_from_begin): New.
+	(__gnu_debug::__get_distance_to_end): New.
+	(__gnu_debug::_Safe_iterator<>::_M_valid_range): Expose iterator range
+	distance information. Add optional check_dereferenceable parameter,
+	default true.
+	(__gnu_debug::_Distance_precision, __gnu_debug::__get_distance): Move
+	default definition...
+	(__gnu_debug::__get_distance): New overload for _Safe_iterator.
+	(__gnu_debug::__unsafe): Likewise.
+	* include/debug/helper_functions.h: ...here. New.
+	(__gnu_debug::__unsafe): New helper function to remove safe iterator
+	layer.
+	* include/debug/stl_iterator.h: New. Include latter.
+	* include/bits/stl_iterator.h: Include latter in debug mode.
+	* include/debug/stl_iterator.tcc: Adapt.
+	* include/debug/safe_local_iterator.h (__gnu_debug::__get_distance): Add
+	overload for _Safe_local_iterator.
+	(__gnu_debug::__unsafe): Likewise.
+	* include/debug/safe_local_iterator.tcc: Adapt.
+	* include/debug/macros.h (__glibcxx_check_valid_range2): New.
+	(__glibcxx_check_insert_range): Add _Dist parameter.
+	(__glibcxx_check_insert_range_after): Likewise.
+	(__glibcxx_check_string, __glibcxx_check_string_len): Implement using
+	_GLIBCXX_DEBUG_PEDASSERT.
+	* include/debug/deque (deque<>::assign): Remove iterator debug layer
+	when possible.
+	(deque<>::insert): Likewise.
+	* include/debug/forward_list (__glibcxx_check_valid_fl_range): New.
+	(forward_list<>::splice_after): Use latter.
+	(forward_list<>::assign): Remove iterator debug layer when possible.
+	(forward_list<>::insert_after): Likewise.
+	(__gnu_debug::_Sequence_traits<>): Partial specialization.
+	* include/debug/list (list<>::assign): Remove iterator debug layer when
+	possible.
+	(list<>::insert): Likewise.
+	[__gnu_debug::_Sequence_traits<>]: Partial specialization pre C++11 ABI.
+	* include/debug/map.h (map<>::insert): Remove iterator debug layer when
+	possible.
+	* include/debug/multimap.h (multimap<>::insert): Likewise.
+	* include/debug/set.h (set<>::insert): Likewise.
+	* include/debug/multiset.h (multiset<>::insert): Likewise.
+	* include/debug/string (basic_string<>::append, basic_string<>::assign,
+	basic_string<>::insert, basic_string<>::replace): Likewise.
+	* include/debug/unordered_map
+	(unordered_map<>::insert, unordered_multimap<>::insert): Likewise.
+	* include/debug/unordered_set
+	(unordered_set<>::insert, unordered_multiset<>insert): Likewise.
+	* include/debug/vector
+	(vector<>::assign, vector<>::insert): Likewise.
+	* include/Makefile.am: Add new debug headers.
+	* include/Makefile.in: Regenerate.
+
 2015-06-26  Jonathan Wakely  <jwakely@redhat.com>
 
 	* doc/xml/manual/intro.xml: Document LWG 2108 status.
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index 927418ed8b0..05be8ad1b84 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -766,6 +766,7 @@ debug_headers = \
 	${debug_srcdir}/formatter.h \
 	${debug_srcdir}/forward_list \
 	${debug_srcdir}/functions.h \
+	${debug_srcdir}/helper_functions.h \
 	${debug_srcdir}/list \
 	${debug_srcdir}/map \
 	${debug_srcdir}/macros.h \
@@ -785,6 +786,7 @@ debug_headers = \
 	${debug_srcdir}/safe_unordered_container.tcc \
 	${debug_srcdir}/set \
 	${debug_srcdir}/set.h \
+	${debug_srcdir}/stl_iterator.h \
 	${debug_srcdir}/string \
 	${debug_srcdir}/unordered_map \
 	${debug_srcdir}/unordered_set \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index 0674d8ca976..bab83b40018 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -1047,6 +1047,7 @@ debug_headers = \
 	${debug_srcdir}/formatter.h \
 	${debug_srcdir}/forward_list \
 	${debug_srcdir}/functions.h \
+	${debug_srcdir}/helper_functions.h \
 	${debug_srcdir}/list \
 	${debug_srcdir}/map \
 	${debug_srcdir}/macros.h \
@@ -1066,6 +1067,7 @@ debug_headers = \
 	${debug_srcdir}/safe_unordered_container.tcc \
 	${debug_srcdir}/set \
 	${debug_srcdir}/set.h \
+	${debug_srcdir}/stl_iterator.h \
 	${debug_srcdir}/string \
 	${debug_srcdir}/unordered_map \
 	${debug_srcdir}/unordered_set \
diff --git a/libstdc++-v3/include/bits/stl_iterator.h b/libstdc++-v3/include/bits/stl_iterator.h
index 58b9aabf2e6..1060433d0bd 100644
--- a/libstdc++-v3/include/bits/stl_iterator.h
+++ b/libstdc++-v3/include/bits/stl_iterator.h
@@ -1246,4 +1246,8 @@ _GLIBCXX_END_NAMESPACE_VERSION
 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
 #endif // C++11
 
+#ifdef _GLIBCXX_DEBUG
+# include <debug/stl_iterator.h>
+#endif
+
 #endif
diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h
index 83e6444ab1c..eba9e398be7 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_types.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h
@@ -206,6 +206,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   //@}
 
+#if __cplusplus < 201103L
   // If _Iterator has a base returns it otherwise _Iterator is returned
   // untouched
   template<typename _Iterator, bool _HasBase>
@@ -223,6 +224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       static iterator_type _S_base(_Iterator __it)
       { return __it.base(); }
     };
+#endif
 
 #if __cplusplus >= 201103L
   template<typename _InIter>
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index fffc5e4ab63..7d15e33606b 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -169,9 +169,14 @@ namespace __debug
 	void
 	assign(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::assign(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::assign(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::assign(__first, __last);
+
 	  this->_M_invalidate_all();
 	}
 
@@ -460,10 +465,16 @@ namespace __debug
 	insert(const_iterator __position,
 	       _InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_insert_range(__position, __first, __last);
-	  _Base_iterator __res = _Base::insert(__position.base(),
-					       __gnu_debug::__base(__first),
-					       __gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
+	  _Base_iterator __res;
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    __res = _Base::insert(__position.base(),
+				  __gnu_debug::__unsafe(__first),
+				  __gnu_debug::__unsafe(__last));
+	  else
+	    __res = _Base::insert(__position.base(), __first, __last);
+
 	  this->_M_invalidate_all();
 	  return iterator(__res, this);
 	}
@@ -473,9 +484,16 @@ namespace __debug
 	insert(iterator __position,
 	       _InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_insert_range(__position, __first, __last);
-	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
-					   __gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__position.base(),
+			  __gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__position.base(), __first, __last);
+
 	  this->_M_invalidate_all();
 	}
 #endif
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index 2b42a3f8d29..df35bc29cf5 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -36,6 +36,13 @@
 #include <debug/safe_container.h>
 #include <debug/safe_iterator.h>
 
+// Special validity check for forward_list ranges.
+#define __glibcxx_check_valid_fl_range(_First,_Last,_Dist)		\
+_GLIBCXX_DEBUG_VERIFY(_First._M_valid_range(_Last, _Dist, false),	\
+		      _M_message(__gnu_debug::__msg_valid_range)	\
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last))
+
 namespace __gnu_debug
 {
   /// Special iterators swap and invalidation for forward_list because of the
@@ -269,9 +276,15 @@ namespace __debug
 	void
 	assign(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::assign(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::assign(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::assign(__first, __last);
+
 	  this->_M_invalidate_all();
 	}
 
@@ -401,11 +414,19 @@ namespace __debug
 	insert_after(const_iterator __pos,
 		     _InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_insert_range_after(__pos, __first, __last);
-	  return iterator(_Base::insert_after(__pos.base(),
-					      __gnu_debug::__base(__first),
-					      __gnu_debug::__base(__last)),
-			  this);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_insert_range_after(__pos, __first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    return
+	      {
+		_Base::insert_after(__pos.base(),
+				    __gnu_debug::__unsafe(__first),
+				    __gnu_debug::__unsafe(__last)),
+		this
+	      };
+	  else
+	    return { _Base::insert_after(__pos.base(), __first, __last), this };
 	}
 
       iterator
@@ -580,9 +601,10 @@ namespace __debug
       splice_after(const_iterator __pos, forward_list&& __list,
 		   const_iterator __before, const_iterator __last)
       {
+	typename __gnu_debug::_Distance_traits<const_iterator>::__type __dist;
 	auto __listptr = std::__addressof(__list);
 	__glibcxx_check_insert_after(__pos);
-	__glibcxx_check_valid_range(__before, __last);
+	__glibcxx_check_valid_fl_range(__before, __last, __dist);
 	_GLIBCXX_DEBUG_VERIFY(__before._M_attached_to(__listptr),
 			      _M_message(__gnu_debug::__msg_splice_other)
 			      ._M_sequence(__list, "list")
@@ -801,7 +823,7 @@ namespace __debug
 
 namespace __gnu_debug
 {
-  template<class _Tp, class _Alloc>
+  template<typename _Tp, typename _Alloc>
     struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> >
     {
       typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence;
@@ -820,6 +842,19 @@ namespace __gnu_debug
 	{ return _S_Is(__it); }
     };
 
+  template<typename _Tp, typename _Alloc>
+    struct _Sequence_traits<std::__debug::forward_list<_Tp, _Alloc> >
+    {
+      typedef typename std::__debug::forward_list<_Tp, _Alloc>::iterator _It;
+
+      static typename _Distance_traits<_It>::__type
+      _S_size(const std::__debug::forward_list<_Tp, _Alloc>& __seq)
+      {
+	return __seq.empty()
+	  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
+      }
+    };
+
 #ifndef _GLIBCXX_DEBUG_PEDANTIC
   template<class _Tp, class _Alloc>
     struct _Insert_range_from_self_is_safe<
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index bf60ccc23c6..7f0659f5b25 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -29,11 +29,6 @@
 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1
 
-#include <bits/c++config.h>
-#include <bits/stl_iterator_base_types.h>	// for iterator_traits,
-						// categories and _Iter_base
-#include <bits/cpp_type_traits.h>		// for __is_integer
-
 #include <bits/move.h>				// for __addressof
 #include <bits/stl_function.h>			// for less
 #if __cplusplus >= 201103L
@@ -41,6 +36,7 @@
 						// conditional.
 #endif
 
+#include <debug/helper_functions.h>
 #include <debug/formatter.h>
 
 namespace __gnu_debug
@@ -85,58 +81,6 @@ namespace __gnu_debug
     __check_dereferenceable(const _Tp* __ptr)
     { return __ptr; }
 
-  /** If the distance between two random access iterators is
-   *  nonnegative, assume the range is valid.
-  */
-  template<typename _RandomAccessIterator>
-    inline bool
-    __valid_range_aux2(const _RandomAccessIterator& __first,
-		       const _RandomAccessIterator& __last,
-		       std::random_access_iterator_tag)
-    { return __last - __first >= 0; }
-
-  /** Can't test for a valid range with input iterators, because
-   *  iteration may be destructive. So we just assume that the range
-   *  is valid.
-  */
-  template<typename _InputIterator>
-    inline bool
-    __valid_range_aux2(const _InputIterator&, const _InputIterator&,
-		       std::input_iterator_tag)
-    { return true; }
-
-  /** We say that integral types for a valid range, and defer to other
-   *  routines to realize what to do with integral types instead of
-   *  iterators.
-  */
-  template<typename _Integral>
-    inline bool
-    __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
-    { return true; }
-
-  /** We have iterators, so figure out what kind of iterators that are
-   *  to see if we can check the range ahead of time.
-  */
-  template<typename _InputIterator>
-    inline bool
-    __valid_range_aux(const _InputIterator& __first,
-		      const _InputIterator& __last, std::__false_type)
-    { return __valid_range_aux2(__first, __last,
-				std::__iterator_category(__first)); }
-
-  /** Don't know what these iterators are, or if they are even
-   *  iterators (we may get an integral type for InputIterator), so
-   *  see if they are integral and pass them on to the next phase
-   *  otherwise.
-  */
-  template<typename _InputIterator>
-    inline bool
-    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
-    {
-      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
-      return __valid_range_aux(__first, __last, _Integral());
-    }
-
   /* 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.
@@ -500,29 +444,6 @@ namespace __gnu_debug
       return __first == __last;
     }
 
-  // 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>
-    { };
-
-  /** 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); }
 } // namespace __gnu_debug
 
 #endif
diff --git a/libstdc++-v3/include/debug/helper_functions.h b/libstdc++-v3/include/debug/helper_functions.h
new file mode 100644
index 00000000000..a2db00d29cc
--- /dev/null
+++ b/libstdc++-v3/include/debug/helper_functions.h
@@ -0,0 +1,210 @@
+// Debugging support implementation -*- C++ -*-
+
+// Copyright (C) 2003-2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/helper_functions.h
+ *  This file is a GNU debug extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H
+#define _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H 1
+
+#include <bits/stl_iterator_base_types.h>	// for iterator_traits,
+						// categories and _Iter_base
+#include <bits/cpp_type_traits.h>		// for __is_integer
+
+#include <bits/stl_pair.h>			// for pair
+
+namespace __gnu_debug
+{
+  /** The precision to which we can calculate the distance between
+   *  two iterators.
+   */
+  enum _Distance_precision
+    {
+      __dp_none,	// Not even an iterator type
+      __dp_equality,	//< Can compare iterator equality, only
+      __dp_sign,	//< Can determine equality and ordering
+      __dp_exact	//< Can determine distance precisely
+    };
+
+  template<typename _Iterator,
+	   typename = typename std::__is_integer<_Iterator>::__type>
+    struct _Distance_traits
+    {
+    private:
+      typedef
+      typename std::iterator_traits<_Iterator>::difference_type _ItDiffType;
+
+      template<typename _DiffType,
+	       typename = typename std::__is_void<_DiffType>::__type>
+	struct _DiffTraits
+	{ typedef _DiffType __type; };
+
+      template<typename _DiffType>
+	struct _DiffTraits<_DiffType, std::__true_type>
+	{ typedef std::ptrdiff_t __type; };
+
+      typedef typename _DiffTraits<_ItDiffType>::__type _DiffType;
+
+    public:
+      typedef std::pair<_DiffType, _Distance_precision> __type;
+    };
+
+  template<typename _Integral>
+    struct _Distance_traits<_Integral, std::__true_type>
+    { typedef std::pair<std::ptrdiff_t, _Distance_precision> __type; };
+
+  /** Determine the distance between two iterators with some known
+   *	precision.
+  */
+  template<typename _Iterator>
+    inline typename _Distance_traits<_Iterator>::__type
+    __get_distance(const _Iterator& __lhs, const _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,
+		   std::input_iterator_tag)
+    {
+      if (__lhs == __rhs)
+	return std::make_pair(0, __dp_exact);
+
+      return std::make_pair(1, __dp_equality);
+    }
+
+  template<typename _Iterator>
+    inline typename _Distance_traits<_Iterator>::__type
+    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs)
+    { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); }
+
+  /** We say that integral types for a valid range, and defer to other
+   *  routines to realize what to do with integral types instead of
+   *  iterators.
+  */
+  template<typename _Integral>
+    inline bool
+    __valid_range_aux(const _Integral&, const _Integral&,
+		      typename _Distance_traits<_Integral>::__type& __dist,
+		      std::__true_type)
+    {
+      __dist = std::make_pair(0, __dp_none);
+      return true;
+    }
+
+  /** We have iterators, so figure out what kind of iterators that are
+   *  to see if we can check the range ahead of time.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range_aux(const _InputIterator& __first,
+		      const _InputIterator& __last,
+		      typename _Distance_traits<_InputIterator>::__type& __dist,
+		      std::__false_type)
+    {
+      __dist = __get_distance(__first, __last);
+      switch (__dist.second)
+	{
+	case __dp_none:
+	  break;
+	case __dp_equality:
+	  if (__dist.first == 0)
+	    return true;
+	  break;
+	case __dp_sign:
+	case __dp_exact:
+	  return __dist.first >= 0;
+	}
+
+      return true;
+    }
+
+  /** Don't know what these iterators are, or if they are even
+   *  iterators (we may get an integral type for InputIterator), so
+   *  see if they are integral and pass them on to the next phase
+   *  otherwise.
+  */
+  template<typename _InputIterator>
+    inline bool
+    __valid_range(const _InputIterator& __first, const _InputIterator& __last,
+		  typename _Distance_traits<_InputIterator>::__type& __dist)
+    {
+      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
+      return __valid_range_aux(__first, __last, __dist, _Integral());
+    }
+
+  template<typename _InputIterator>
+    inline bool
+    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
+    {
+      typename _Distance_traits<_InputIterator>::__type __dist;
+      return __valid_range(__first, __last, __dist);
+    }
+
+#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>
+    { };
+
+  /** 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
+  template<typename _Iterator>
+    inline _Iterator
+    __base(_Iterator __it)
+    { return __it; }
+#endif
+
+#if __cplusplus < 201103L
+  template<typename _Iterator>
+    struct _Unsafe_type
+    { typedef _Iterator _Type; };
+#endif
+
+  /* Remove debug mode safe iterator layer, if any. */
+  template<typename _Iterator>
+    inline _Iterator
+    __unsafe(_Iterator __it)
+    { return __it; }
+}
+
+#endif
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index 12ac53c4675..0f3f1a0e241 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -177,9 +177,15 @@ namespace __debug
 	void
 	assign(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::assign(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::assign(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::assign(__first, __last);
+
 	  this->_M_invalidate_all();
 	}
 
@@ -441,11 +447,18 @@ namespace __debug
 	insert(const_iterator __position, _InputIterator __first,
 	       _InputIterator __last)
 	{
-	  __glibcxx_check_insert_range(__position, __first, __last);
-	  return iterator(_Base::insert(__position.base(),
-					__gnu_debug::__base(__first),
-					__gnu_debug::__base(__last)),
-			  this);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    return
+	      {
+		_Base::insert(__position.base(),
+			      __gnu_debug::__unsafe(__first),
+			      __gnu_debug::__unsafe(__last)),
+		  this
+	      };
+	  else
+	    return { _Base::insert(__position.base(), __first, __last), this };
 	}
 #else
       template<class _InputIterator>
@@ -453,9 +466,14 @@ namespace __debug
 	insert(iterator __position, _InputIterator __first,
 	       _InputIterator __last)
 	{
-	  __glibcxx_check_insert_range(__position, __first, __last);
-	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
-					   __gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
+					     __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__position.base(), __first, __last);
 	}
 #endif
 
@@ -795,13 +813,29 @@ namespace __debug
 } // namespace __debug
 } // namespace std
 
-#ifndef _GLIBCXX_DEBUG_PEDANTIC
 namespace __gnu_debug
 {
+#ifndef _GLIBCXX_USE_CXX11_ABI
+  // If not using C++11 list::size() is not in O(1) so we do not use it.
+  template<typename _Tp, typename _Alloc>
+    struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> >
+    {
+      typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It;
+
+      static typename _Distance_traits<_It>::__type
+      _S_size(const std::__debug::list<_Tp, _Alloc>& __seq)
+      {
+	return __seq.empty()
+	  ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality);
+      }
+    };
+#endif
+
+#ifndef _GLIBCXX_DEBUG_PEDANTIC
   template<class _Tp, class _Alloc>
     struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> >
     { enum { __value = 1 }; };
-}
 #endif
+}
 
 #endif
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index f796e718770..a4c2649c843 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -56,6 +56,12 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__valid_range(_First, _Last),	\
 		      ._M_iterator(_First, #_First)			\
 		      ._M_iterator(_Last, #_Last))
 
+#define __glibcxx_check_valid_range2(_First,_Last,_Dist)		\
+_GLIBCXX_DEBUG_VERIFY(__gnu_debug::__valid_range(_First, _Last, _Dist),	\
+		      _M_message(__gnu_debug::__msg_valid_range)	\
+		      ._M_iterator(_First, #_First)			\
+		      ._M_iterator(_Last, #_Last))
+
 // Verify that [_First, _Last) forms a non-empty iterator range.
 #define __glibcxx_check_non_empty_range(_First,_Last)			\
 _GLIBCXX_DEBUG_VERIFY(_First != _Last,					\
@@ -104,8 +110,8 @@ _GLIBCXX_DEBUG_VERIFY(!_Position._M_is_end(),				\
  *  Note that this macro is only valid when the container is a
  *  _Safe_sequence and the _Position iterator is a _Safe_iterator.
 */
-#define __glibcxx_check_insert_range(_Position,_First,_Last)		\
-__glibcxx_check_valid_range(_First,_Last);				\
+#define __glibcxx_check_insert_range(_Position,_First,_Last,_Dist)	\
+__glibcxx_check_valid_range2(_First,_Last,_Dist);			\
 __glibcxx_check_insert(_Position);					\
 _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First,_Last),\
 		      _M_message(__gnu_debug::__msg_insert_range_from_self)\
@@ -123,8 +129,8 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First,_Last),\
  *  Note that this macro is only valid when the container is a
  *  _Safe_sequence and the _Position iterator is a _Safe_iterator.
 */
-#define __glibcxx_check_insert_range_after(_Position,_First,_Last)	\
-__glibcxx_check_valid_range(_First,_Last);				\
+#define __glibcxx_check_insert_range_after(_Position,_First,_Last,_Dist)\
+  __glibcxx_check_valid_range2(_First,_Last,_Dist);			\
 __glibcxx_check_insert_after(_Position);				\
 _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__foreign_iterator(_Position,_First,_Last),\
 		      _M_message(__gnu_debug::__msg_insert_range_from_self)\
@@ -352,13 +358,8 @@ _GLIBCXX_DEBUG_VERIFY(_This.get_allocator() == _Other.get_allocator(),	\
 		      _M_message(__gnu_debug::__msg_equal_allocs)	\
 		      ._M_sequence(_This, "this"))
 
-#ifdef _GLIBCXX_DEBUG_PEDANTIC
-#  define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_ASSERT(_String != 0)
-#  define __glibcxx_check_string_len(_String,_Len) \
-       _GLIBCXX_DEBUG_ASSERT(_String != 0 || _Len == 0)
-#else
-#  define __glibcxx_check_string(_String)
-#  define __glibcxx_check_string_len(_String,_Len)
-#endif
+#define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_PEDASSERT(_String != 0)
+#define __glibcxx_check_string_len(_String,_Len) \
+  _GLIBCXX_DEBUG_PEDASSERT(_String != 0 || _Len == 0)
 
 #endif
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 688fb99d499..9bda8eba1da 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -307,9 +307,14 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::insert(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
 	}
 
 #if __cplusplus >= 201103L
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index e2c806131f0..b9b0a74c94e 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -286,9 +286,14 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::insert(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
 	}
 
 #if __cplusplus >= 201103L
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index b4d738f4bec..f1f6e2c576a 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -271,9 +271,14 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::insert(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
 	}
 
 #if __cplusplus >= 201103L
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index 9f2dcd1e238..a8bee214e36 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -41,7 +41,7 @@ namespace __gnu_debug
   /** Helper struct to deal with sequence offering a before_begin
    *  iterator.
    **/
-  template <typename _Sequence>
+  template<typename _Sequence>
     struct _BeforeBeginHelper
     {
       template<typename _Iterator>
@@ -55,38 +55,16 @@ namespace __gnu_debug
 	{ return __it.base() == __it._M_get_sequence()->_M_base().begin(); }
     };
 
-  /** The precision to which we can calculate the distance between
-   *  two iterators.
-   */
-  enum _Distance_precision
+  /** Sequence traits giving the size of a container if possible. */
+  template<typename _Sequence>
+    struct _Sequence_traits
     {
-      __dp_equality, //< Can compare iterator equality, only
-      __dp_sign,     //< Can determine equality and ordering
-      __dp_exact     //< Can determine distance precisely
-    };
-
-  /** Determine the distance between two iterators with some known
-   *	precision.
-  */
-  template<typename _Iterator>
-    inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
-		     _Distance_precision>
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs,
-		   std::random_access_iterator_tag)
-    { return std::make_pair(__rhs - __lhs, __dp_exact); }
+      typedef _Distance_traits<typename _Sequence::iterator> _DistTraits;
 
-  template<typename _Iterator>
-    inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
-		     _Distance_precision>
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs,
-		   std::forward_iterator_tag)
-    { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); }
-
-  template<typename _Iterator>
-    inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
-		     _Distance_precision>
-    __get_distance(const _Iterator& __lhs, const _Iterator& __rhs)
-    { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); }
+      static typename _DistTraits::__type
+      _S_size(const _Sequence& __seq)
+      { return std::make_pair(__seq.size(), __dp_exact); }
+    };
 
   /** \brief Safe iterator wrapper.
    *
@@ -476,7 +454,9 @@ namespace __gnu_debug
 
       // Is the iterator range [*this, __rhs) valid?
       bool
-      _M_valid_range(const _Safe_iterator& __rhs) const;
+      _M_valid_range(const _Safe_iterator& __rhs,
+		     std::pair<difference_type, _Distance_precision>& __dist,
+		     bool __check_dereferenceable = true) const;
 
       // The sequence this iterator references.
       typename
@@ -768,15 +748,157 @@ namespace __gnu_debug
   template<typename _Iterator, typename _Sequence>
     inline bool
     __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
-		  const _Safe_iterator<_Iterator, _Sequence>& __last)
-    { return __first._M_valid_range(__last); }
+		  const _Safe_iterator<_Iterator, _Sequence>& __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)
+    {
+      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;
+    }
+
+#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)
+    { 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> >
+    { typedef _Iterator _Type; };
+#endif
+
+  template<typename _Iterator, typename _Sequence>
+    inline _Iterator
+    __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
+    { return __it.base(); }
 
 } // namespace __gnu_debug
 
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 47b6f2f1dd3..1ad26e3e07b 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -38,12 +38,14 @@ namespace __gnu_debug
     {
       if (this->_M_singular())
 	return false;
+
       if (__n == 0)
 	return true;
+
       if (__n < 0)
 	{
 	  std::pair<difference_type, _Distance_precision> __dist =
-	    __get_distance(_M_get_sequence()->_M_base().begin(), base());
+	    __get_distance_from_begin(*this);
 	  bool __ok =  ((__dist.second == __dp_exact && __dist.first >= -__n)
 			|| (__dist.second != __dp_exact && __dist.first > 0));
 	  return __ok;
@@ -51,7 +53,7 @@ namespace __gnu_debug
       else
 	{
 	  std::pair<difference_type, _Distance_precision> __dist =
-	    __get_distance(base(), _M_get_sequence()->_M_base().end());
+	    __get_distance_to_end(*this);
 	  bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n)
 		       || (__dist.second != __dp_exact && __dist.first > 0));
 	  return __ok;
@@ -61,37 +63,31 @@ namespace __gnu_debug
   template<typename _Iterator, typename _Sequence>
     bool
     _Safe_iterator<_Iterator, _Sequence>::
-    _M_valid_range(const _Safe_iterator& __rhs) const
+    _M_valid_range(const _Safe_iterator& __rhs,
+		   std::pair<difference_type, _Distance_precision>& __dist,
+		   bool __check_dereferenceable) const
     {
       if (!_M_can_compare(__rhs))
 	return false;
 
-      /* Determine if we can order the iterators without the help of
-	 the container */
-      std::pair<difference_type, _Distance_precision> __dist =
-	__get_distance(base(), __rhs.base());
-      switch (__dist.second) {
-      case __dp_equality:
-	if (__dist.first == 0)
-	  return true;
-	break;
-
-      case __dp_sign:
-      case __dp_exact:
-	return __dist.first >= 0;
-      }
+      /* Determine iterators order */
+      __dist = __get_distance(*this, __rhs);
+      switch (__dist.second)
+	{
+	case __dp_equality:
+	  if (__dist.first == 0)
+	    return true;
+	  break;
 
-      /* We can only test for equality, but check if one of the
-	 iterators is at an extreme. */
-      /* Optim for classic [begin, it) or [it, end) ranges, limit checks
-       * when code is valid.  Note, for the special case of forward_list,
-       * before_begin replaces the role of begin.  */ 
-      if (_M_is_beginnest() || __rhs._M_is_end())
-	return true;
-      if (_M_is_end() || __rhs._M_is_beginnest())
-	return false;
+	case __dp_sign:
+	case __dp_exact:
+	  // If range is not empty first iterator must be dereferenceable.
+	  if (__dist.first > 0)
+	    return !__check_dereferenceable || _M_dereferenceable();
+	  return __dist.first == 0;
+	}
 
-      // Assume that this is a valid range; we can't check anything else
+      // Assume that this is a valid range; we can't check anything else.
       return true;
     }
 } // namespace __gnu_debug
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h
index dcbe4400cac..350a1d249ed 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -322,7 +322,9 @@ namespace __gnu_debug
 
       // Is the iterator range [*this, __rhs) valid?
       bool
-      _M_valid_range(const _Safe_local_iterator& __rhs) const;
+      _M_valid_range(const _Safe_local_iterator& __rhs,
+		     std::pair<difference_type,
+			       _Distance_precision>& __dist_info) const;
 
       // The sequence this iterator references.
       typename
@@ -440,8 +442,66 @@ namespace __gnu_debug
   template<typename _Iterator, typename _Sequence>
     inline bool
     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
-		  const _Safe_local_iterator<_Iterator, _Sequence>& __last)
-    { return __first._M_valid_range(__last); }
+		  const _Safe_local_iterator<_Iterator, _Sequence>& __last,
+		  typename _Distance_traits<_Iterator>::__type& __dist_info)
+    { return __first._M_valid_range(__last, __dist_info); }
+
+  /** Safe local iterators need a special method to get distance between each
+      other. */
+  template<typename _Iterator, typename _Sequence>
+    inline std::pair<typename std::iterator_traits<_Iterator>::difference_type,
+		     _Distance_precision>
+    __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
+		   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
+		   std::input_iterator_tag)
+    {
+      if (__first.base() == __last.base())
+	return { 0, __dp_exact };
+
+      if (__first._M_is_begin())
+	{
+	  if (__last._M_is_end())
+	    return
+	      {
+		__first._M_get_sequence()->bucket_size(__first.bucket()),
+		__dp_exact
+	      };
+
+	  return { 1, __dp_sign };
+	}
+
+      if (__first._M_is_end())
+	{
+	  if (__last._M_is_begin())
+	    return
+	      {
+		-__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 };
+    }
+
+#if __cplusplus < 201103L
+  template<typename _Iterator, typename _Sequence>
+    struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
+    { typedef _Iterator _Type; };
+#endif
+
+  template<typename _Iterator, typename _Sequence>
+    inline _Iterator
+    __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
+    { return __it.base(); }
+
 } // namespace __gnu_debug
 
 #include <debug/safe_local_iterator.tcc>
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.tcc b/libstdc++-v3/include/debug/safe_local_iterator.tcc
index 455e4cd5dd7..f846bf78307 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_local_iterator.tcc
@@ -34,17 +34,18 @@ namespace __gnu_debug
   template<typename _Iterator, typename _Sequence>
     bool
     _Safe_local_iterator<_Iterator, _Sequence>::
-    _M_valid_range(const _Safe_local_iterator& __rhs) const
+    _M_valid_range(const _Safe_local_iterator& __rhs,
+		std::pair<difference_type, _Distance_precision>& __dist) const
     {
       if (!_M_can_compare(__rhs))
 	return false;
+
       if (bucket() != __rhs.bucket())
 	return false;
 
       /* Determine if we can order the iterators without the help of
 	 the container */
-      std::pair<difference_type, _Distance_precision> __dist =
-	__get_distance(base(), __rhs.base());
+      __dist = __get_distance(*this, __rhs);
       switch (__dist.second)
 	{
 	case __dp_equality:
@@ -57,15 +58,6 @@ namespace __gnu_debug
 	  return __dist.first >= 0;
 	}
 
-      /* We can only test for equality, but check if one of the
-	 iterators is at an extreme. */
-      /* Optim for classic [begin, it) or [it, end) ranges, limit checks
-       * when code is valid. */
-      if (_M_is_begin() || __rhs._M_is_end())
-	return true;
-      if (_M_is_end() || __rhs._M_is_begin())
-	return false;
-
       // Assume that this is a valid range; we can't check anything else
       return true;
     }
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index c13ee811aaa..1ca6dda9c0e 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -280,9 +280,14 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::insert(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
 	}
 
 #if __cplusplus >= 201103L
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
new file mode 100644
index 00000000000..d1e57ea75a0
--- /dev/null
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -0,0 +1,113 @@
+// Debugging support implementation -*- C++ -*-
+
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file debug/stl_iterator.h
+ *  This file is a GNU debug extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_DEBUG_STL_ITERATOR_H
+#define _GLIBCXX_DEBUG_STL_ITERATOR_H 1
+
+#include <debug/helper_functions.h>
+
+namespace __gnu_debug
+{
+  // Help Debug mode to see through reverse_iterator.
+  template<typename _Iterator>
+    inline bool
+    __valid_range(const std::reverse_iterator<_Iterator>& __first,
+		  const std::reverse_iterator<_Iterator>& __last,
+		  typename _Distance_traits<_Iterator>::__type& __dist)
+    { return __valid_range(__last.base(), __first.base(), __dist); }
+
+  template<typename _Iterator>
+    inline typename _Distance_traits<_Iterator>::__type
+    __get_distance(const std::reverse_iterator<_Iterator>& __first,
+		   const std::reverse_iterator<_Iterator>& __last)
+    { return __get_distance(__last.base(), __first.base()); }
+
+#if __cplusplus < 201103L
+  template<typename _Iterator>
+    struct __is_safe_random_iterator<std::reverse_iterator<_Iterator> >
+      : __is_safe_random_iterator<_Iterator>
+    { };
+
+  template<typename _Iterator>
+    struct _Unsafe_type<std::reverse_iterator<_Iterator> >
+    {
+      typedef typename _Unsafe_type<_Iterator>::_Type _UnsafeType;
+      typedef std::reverse_iterator<_UnsafeType> _Type;
+    };
+
+  template<typename _Iterator>
+    inline std::reverse_iterator<typename _Unsafe_type<_Iterator>::_Type>
+    __unsafe(const std::reverse_iterator<_Iterator>& __it)
+    {
+      typedef typename _Unsafe_type<_Iterator>::_Type _UnsafeType;
+      return std::reverse_iterator<_UnsafeType>(__unsafe(__it.base()));
+    }
+#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())); }
+#endif
+
+#if __cplusplus >= 201103L
+  // Help Debug mode to see through move_iterator.
+  template<typename _Iterator>
+    inline bool
+    __valid_range(const std::move_iterator<_Iterator>& __first,
+		  const std::move_iterator<_Iterator>& __last,
+		  typename _Distance_traits<_Iterator>::__type& __dist)
+    { return __valid_range(__first.base(), __last.base(), __dist); }
+
+  template<typename _Iterator>
+    inline typename _Distance_traits<_Iterator>::__type
+    __get_distance(const std::move_iterator<_Iterator>& __first,
+		   const std::move_iterator<_Iterator>& __last)
+    { return __get_distance(__first.base(), __last.base()); }
+
+  template<typename _Iterator>
+    inline auto
+    __unsafe(const std::move_iterator<_Iterator>& __it)
+    -> decltype(std::make_move_iterator(__unsafe(__it.base())))
+    { return std::make_move_iterator(__unsafe(__it.base())); }
+
+  template<typename _Iterator>
+    inline auto
+    __base(const std::move_iterator<_Iterator>& __it)
+    -> decltype(std::make_move_iterator(__base(__it.base())))
+    { return std::make_move_iterator(__base(__it.base())); }
+#endif
+}
+
+#endif
diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string
index f068ef04fe8..72ae88e5495 100644
--- a/libstdc++-v3/include/debug/string
+++ b/libstdc++-v3/include/debug/string
@@ -380,9 +380,15 @@ namespace __gnu_debug
       basic_string&
       append(_InputIterator __first, _InputIterator __last)
       {
-	__glibcxx_check_valid_range(__first, __last);
-	_Base::append(__gnu_debug::__base(__first),
-		      __gnu_debug::__base(__last));
+	typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	__glibcxx_check_valid_range2(__first, __last, __dist);
+
+	if (__dist.second >= __dp_sign)
+	  _Base::append(__gnu_debug::__unsafe(__first),
+			__gnu_debug::__unsafe(__last));
+	else
+	  _Base::append(__first, __last);
+
 	this->_M_invalidate_all();
 	return *this;
       }
@@ -452,9 +458,15 @@ namespace __gnu_debug
       basic_string&
       assign(_InputIterator __first, _InputIterator __last)
       {
-	__glibcxx_check_valid_range(__first, __last);
-	_Base::assign(__gnu_debug::__base(__first),
-		      __gnu_debug::__base(__last));
+	typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	__glibcxx_check_valid_range2(__first, __last, __dist);
+
+	if (__dist.second >= __dp_sign)
+	  _Base::assign(__gnu_debug::__unsafe(__first),
+			__gnu_debug::__unsafe(__last));
+	else
+	  _Base::assign(__first, __last);
+
 	this->_M_invalidate_all();
 	return *this;
       }
@@ -533,9 +545,15 @@ namespace __gnu_debug
       void
       insert(iterator __p, _InputIterator __first, _InputIterator __last)
       {
-	__glibcxx_check_insert_range(__p, __first, __last);
-	_Base::insert(__p.base(), __gnu_debug::__base(__first),
-				  __gnu_debug::__base(__last));
+	typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	__glibcxx_check_insert_range2(__p, __first, __last, __dist);
+
+	if (__dist.second >= __dp_sign)
+	  _Base::insert(__p.base(), __gnu_debug::__unsafe(__first),
+				    __gnu_debug::__unsafe(__last));
+	else
+	  _Base::insert(__p.base(), __first, __last);
+
 	this->_M_invalidate_all();
       }
 
@@ -676,8 +694,17 @@ namespace __gnu_debug
 	      _InputIterator __j1, _InputIterator __j2)
       {
 	__glibcxx_check_erase_range(__i1, __i2);
-	__glibcxx_check_valid_range(__j1, __j2);
-	_Base::replace(__i1.base(), __i2.base(), __j1, __j2);
+
+	typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	__glibcxx_check_valid_range2(__j1, __j2, __dist);
+
+	if (__dist.second >= __dp_sign)
+	  _Base::replace(__i1.base(), __i2.base(),
+			 __gnu_debug::__unsafe(__j1),
+			 __gnu_debug::__unsafe(__j2));
+	else
+	  _Base::replace(__i1.base(), __i2.base(), __j1, __j2);
+
 	this->_M_invalidate_all();
 	return *this;
       }
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index 3f46641d678..41e20d7f203 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -364,10 +364,16 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
 	  size_type __bucket_count = this->bucket_count();
-	  _Base::insert(__gnu_debug::__base(__first),
-			  __gnu_debug::__base(__last));
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
+
 	  _M_check_rehashed(__bucket_count);
 	}
 
@@ -809,10 +815,16 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
 	  size_type __bucket_count = this->bucket_count();
-	  _Base::insert(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
+
 	  _M_check_rehashed(__bucket_count);
 	}
 
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 10a9c270ed0..1e6846140ab 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -355,10 +355,16 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
 	  size_type __bucket_count = this->bucket_count();
-	  _Base::insert(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
+
 	  _M_check_rehashed(__bucket_count);
 	}
 
@@ -799,10 +805,16 @@ namespace __debug
 	void
 	insert(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
 	  size_type __bucket_count = this->bucket_count();
-	  _Base::insert(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__first, __last);
+
 	  _M_check_rehashed(__bucket_count);
 	}
 
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index be679920949..310009756c0 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -244,9 +244,15 @@ namespace __debug
 	void
 	assign(_InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_valid_range(__first, __last);
-	  _Base::assign(__gnu_debug::__base(__first),
-			__gnu_debug::__base(__last));
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_valid_range2(__first, __last, __dist);
+
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::assign(__gnu_debug::__unsafe(__first),
+			  __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::assign(__first, __last);
+
 	  this->_M_invalidate_all();
 	  this->_M_update_guaranteed_capacity();
 	}
@@ -574,16 +580,21 @@ namespace __debug
 	insert(const_iterator __position,
 	       _InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_insert_range(__position, __first, __last);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
 
 	  /* Hard to guess if invalidation will occur, because __last
 	     - __first can't be calculated in all cases, so we just
 	     punt here by checking if it did occur. */
 	  _Base_iterator __old_begin = _M_base().begin();
 	  difference_type __offset = __position.base() - _Base::cbegin();
-	  _Base_iterator __res = _Base::insert(__position.base(),
-					       __gnu_debug::__base(__first),
-					       __gnu_debug::__base(__last));
+	  _Base_iterator __res;
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    __res = _Base::insert(__position.base(),
+				  __gnu_debug::__unsafe(__first),
+				  __gnu_debug::__unsafe(__last));
+	  else
+	    __res = _Base::insert(__position.base(), __first, __last);
 
 	  if (_M_base().begin() != __old_begin)
 	    this->_M_invalidate_all();
@@ -598,15 +609,19 @@ namespace __debug
 	insert(iterator __position,
 	       _InputIterator __first, _InputIterator __last)
 	{
-	  __glibcxx_check_insert_range(__position, __first, __last);
+	  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
+	  __glibcxx_check_insert_range(__position, __first, __last, __dist);
 
 	  /* Hard to guess if invalidation will occur, because __last
 	     - __first can't be calculated in all cases, so we just
 	     punt here by checking if it did occur. */
 	  _Base_iterator __old_begin = _M_base().begin();
 	  difference_type __offset = __position.base() - _Base::begin();
-	  _Base::insert(__position.base(), __gnu_debug::__base(__first),
-					   __gnu_debug::__base(__last));
+	  if (__dist.second >= __gnu_debug::__dp_sign)
+	    _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
+					     __gnu_debug::__unsafe(__last));
+	  else
+	    _Base::insert(__position.base(), __first, __last);
 
 	  if (_M_base().begin() != __old_begin)
 	    this->_M_invalidate_all();