diff mbox series

Deque iterators lexicographical_compare overloads

Message ID e30c042a-994b-f04c-2628-9dc4b283f308@gmail.com
State New
Headers show
Series Deque iterators lexicographical_compare overloads | expand

Commit Message

François Dumont July 26, 2019, 5:07 a.m. UTC 
And here are the lexicographical_compare overloads.

I am submitting this seperately from the others cause some might argue 
that it is a lot of code for a scope limited to the moment to unsigned 
byte types.

I had to overload __lexicographical_compare_aux here cause the 
std::lexicographical_compare returning a bool can't be implemented in 
chunk unless you double the comparisons to find out when 2 ranges are 
equivalent.


     * include/bits/stl_deque.h
     (std::__lexicographical_compare_aux): New overloads for deque 
iterators.
     * include/bits/deque.tcc
     (std::__detail::__lc_from_dit): New.
     (std::__detail::__lc_to_dit): New.
     (std::__lexicographical_compare_aux): New overloads definitions, use
     latters.
     * include/debug/deque
     (std::__lexicographical_compare_aux): New overloads for deque debug
     iterators.
     * include/bits_stl_algobase.h:
     (__lexicographical_compare_impl): Return int.
     (__lexicographical_compare<>::__lc): Likewise.
     (_Deque_iterator<>): New type declaration.
     (__lexicographical_compare_aux): Add overload declarations for deque
     iterators normal and debug modes.
     (__lexicographical_compare_aux): Return int.
     (std::lexicographical_compare): Adapt.
     * testsuite/25_algorithms/lexicographical_compare/1.cc (test6): New.
     (test7): New.
     * testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
     New.

Tested uner Linux x86_64 normal and debug modes.

Ok to commit ?

François
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 9db869fb666..87514992f50 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1167,6 +1167,80 @@  _GLIBCXX_END_NAMESPACE_CONTAINER
 	return true;
       }
 
+    template<typename _Tp, typename _II>
+      int
+      __lc_from_dit(
+	const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+					      const _Tp*>& __first1,
+	const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+					      const _Tp*>& __last1,
+	_II __first2, _II __last2)
+      {
+	typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+	typedef typename _Self::difference_type difference_type;
+
+	if (__first1._M_node != __last1._M_node)
+	  {
+	    difference_type __len = __last2 - __first2;
+	    difference_type __flen
+	      = std::min(__len, __first1._M_last() - __first1._M_cur);
+	    if (int __ret = std::__lexicographical_compare_aux(
+		__first1._M_cur, __first1._M_last(), __first2, __first2 + __flen))
+	      return __ret;
+
+	    __first2 += __flen;
+	    __len -= __flen;
+	    __flen = std::min<size_t>(__len, _Self::_S_buffer_size());
+	    for (typename _Self::_Map_pointer __node = __first1._M_node + 1;
+		 __node != __last1._M_node;
+		 __first2 += __flen, __len -= __flen,
+		   __flen = std::min<size_t>(__len, _Self::_S_buffer_size()), ++__node)
+	      if (int __ret = std::__lexicographical_compare_aux(
+					*__node, *__node + _Self::_S_buffer_size(),
+					__first2, __first2 + __flen))
+		return __ret;
+
+	    return std::__lexicographical_compare_aux(
+		__last1._M_first, __last1._M_cur, __first2, __last2);
+	  }
+
+	return std::__lexicographical_compare_aux(
+		__first1._M_cur, __last1._M_cur, __first2, __last2);
+      }
+
+    template<typename _II, typename _Tp>
+      int
+      __lc_to_dit(_II __first1, _II __last1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last2)
+      {
+	typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+	typedef typename _Self::difference_type difference_type;
+
+	difference_type __len = __last1 - __first1;
+	while (__len > 0)
+	  {
+	    const difference_type __flen = __first2._M_node == __last2._M_node
+	      ? __last2._M_cur - __first2._M_cur
+	      : __first2._M_last() - __first2._M_cur;
+	    const difference_type __clen
+	      = std::min(__len, __flen);
+	    if (int __ret = std::__lexicographical_compare_aux(
+		__first1, __first1 + __clen, __first2._M_cur, __first2._M_cur + __flen))
+	      return __ret;
+
+	    __first1 += __clen;
+	    __len -= __clen;
+	    __first2 += __clen;
+	  }
+
+	return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
+      }
+
 #if __cplusplus >= 201103L
     template<typename _Tp, typename _OI>
       _OI
@@ -1394,6 +1468,36 @@  _GLIBCXX_END_NAMESPACE_CONTAINER
       return __detail::__equal_to_dit(__first1, __last1, __first2);
     }
 
+  template<typename _Tp, typename _II>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last1,
+      _II __first2, _II __last2)
+    { return __detail::__lc_from_dit(__first1, __last1, __first2, __last2); }
+
+  template<typename _Tp>
+    int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last2)
+    { return __detail::__lc_from_dit(__first1, __last1, __first2, __last2); }
+
+  template<typename _II, typename _Tp>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II __first1, _II __last1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last2)
+    { return __detail::__lc_to_dit(__first1, __last1, __first2, __last2); }
+
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _OI>
     _OI
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 58bfb6c0f05..72485ce405f 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -944,7 +944,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
   template<typename _II1, typename _II2, typename _Compare>
-    bool
+    int
     __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
 				   _II2 __first2, _II2 __last2,
 				   _Compare __comp)
@@ -953,28 +953,30 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef typename iterator_traits<_II2>::iterator_category _Category2;
       typedef std::__lc_rai<_Category1, _Category2> __rai_type;
 
-      __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
-      for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
+      _II1 __new_last1
+	= __rai_type::__newlast1(__first1, __last1, __first2, __last2);
+      for (; __first1 != __new_last1 && __rai_type::__cnd2(__first2, __last2);
 	   ++__first1, (void)++__first2)
 	{
 	  if (__comp(__first1, __first2))
-	    return true;
+	    return -1;
 	  if (__comp(__first2, __first1))
-	    return false;
+	    return 1;
 	}
-      return __first1 == __last1 && __first2 != __last2;
+
+      return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
     }
 
   template<bool _BoolType>
     struct __lexicographical_compare
     {
       template<typename _II1, typename _II2>
-	static bool __lc(_II1, _II1, _II2, _II2);
+	static int __lc(_II1, _II1, _II2, _II2);
     };
 
   template<bool _BoolType>
     template<typename _II1, typename _II2>
-      bool
+      int
       __lexicographical_compare<_BoolType>::
       __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
       {
@@ -987,7 +989,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     struct __lexicographical_compare<true>
     {
       template<typename _Tp, typename _Up>
-	static bool
+	static int
 	__lc(const _Tp* __first1, const _Tp* __last1,
 	     const _Up* __first2, const _Up* __last2)
 	{
@@ -995,13 +997,221 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  const size_t __len2 = __last2 - __first2;
 	  if (const size_t __len = std::min(__len1, __len2))
 	    if (int __result = __builtin_memcmp(__first1, __first2, __len))
-	      return __result < 0;
-	  return __len1 < __len2;
+	      return __result;
+
+	  return __len1 < __len2 ? -1 : (__len2 < __len1 ? 1 : 0);
 	}
     };
 
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
+
+  template<typename _Tp, typename _Ref, typename _Ptr>
+    struct _Deque_iterator;
+
+_GLIBCXX_END_NAMESPACE_CONTAINER
+
+  template<typename _Tp, typename _II>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _II, _II);
+
+  template<typename _Tp, typename _II>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _II, _II);
+
+  template<typename _Tp>
+    int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>);
+
+  template<typename _Tp>
+    int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>);
+
+  template<typename _Tp>
+    int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+  template<typename _Tp>
+    int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+  template<typename _II, typename _Tp>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II, _II,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>);
+
+  template<typename _II, typename _Tp>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II, _II,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+#if _GLIBCXX_DEBUG
+_GLIBCXX_END_NAMESPACE_VERSION
+
+namespace __debug
+{
+  template<typename _Tp, typename _Allocator>
+    class deque;
+}
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  template<typename _Tp, typename _Alloc, typename _II>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&,
+      _II, _II);
+
+  template<typename _Tp, typename _Alloc, typename _II>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&,
+      _II, _II);
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&);
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&);
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&);
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >&);
+
+  template<typename _II, typename _Tp, typename _Alloc>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II, _II,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&);
+
+  template<typename _II, typename _Tp, typename _Alloc>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II, _II,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >&);
+#endif
+
   template<typename _II1, typename _II2>
-    inline bool
+    inline int
     __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
 				  _II2 __first2, _II2 __last2)
     {
@@ -1313,7 +1523,7 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
       return std::__lexicographical_compare_aux(std::__niter_base(__first1),
 						std::__niter_base(__last1),
 						std::__niter_base(__first2),
-						std::__niter_base(__last2));
+						std::__niter_base(__last2)) < 0;
     }
 
   /**
@@ -1342,7 +1552,7 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
 
       return std::__lexicographical_compare_impl
 	(__first1, __last1, __first2, __last2,
-	 __gnu_cxx::__ops::__iter_comp_iter(__comp));
+	 __gnu_cxx::__ops::__iter_comp_iter(__comp)) < 0;
     }
 
   template<typename _InputIterator1, typename _InputIterator2,
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 23aea66c42c..b7af5a1a854 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -2451,6 +2451,106 @@  _GLIBCXX_END_NAMESPACE_CONTAINER
 	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first2));
     }
 
+  template<typename _Tp, typename _II>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _II, _II);
+
+  template<typename _Tp, typename _II>
+    inline typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last1,
+      _II __first2, _II __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first1),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last1),
+	__first2, __last2);
+    }
+
+  template<typename _Tp>
+    int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>);
+
+  template<typename _Tp>
+    inline int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first1),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last1),
+	__first2, __last2);
+    }
+
+  template<typename _Tp>
+    inline int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first2,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	__first1, __last1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first2),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last2));
+    }
+
+  template<typename _Tp>
+    inline int
+    __lexicographical_compare_aux(
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first2,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first1),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last1),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first2),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last2));
+    }
+
+  template<typename _II, typename _Tp>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II, _II,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>);
+
+  template<typename _II, typename _Tp>
+    inline typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II __first1, _II __last1,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first2,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last2)
+    {
+      return std::__lexicographical_compare_aux(__first1, __last1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first2),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last2));
+    }
+
 #if __cplusplus >= 201103L
   // std::allocator is safe, but it is not the only allocator
   // for which this is valid.
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 64a29fbe1bc..e2f2159912d 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -1099,6 +1099,160 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			__first2.base());
     }
 
+  template<typename _Tp, typename _Alloc, typename _II>
+    inline typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __first1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __last1,
+      _II __first2, _II __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	__first1.base(), __last1.base(),
+	::__gnu_debug::__unsafe(__first2), ::__gnu_debug::__unsafe(__last2));
+    }
+
+  template<typename _Tp, typename _Alloc, typename _II>
+    inline typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __first1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __last1,
+      _II __first2, _II __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	__first1.base(), __last1.base(),
+	::__gnu_debug::__unsafe(__first2), ::__gnu_debug::__unsafe(__last2));
+    }
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __first1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __last1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __first2,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	__first1.base(), __last1.base(), __first2.base(), __last2.base());
+    }
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __first1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __last1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __first2,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	__first1.base(), __last1.base(), __first2.base(), __last2.base());
+    }
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __first1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __last1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __first2,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	__first1.base(), __last1.base(), __first2.base(), __last2.base());
+    }
+
+  template<typename _Tp, typename _Alloc1, typename _Alloc2>
+    int
+    __lexicographical_compare_aux(
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __first1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc1> >& __last1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __first2,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc2> >& __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	__first1.base(), __last1.base(), __first2.base(), __last2.base());
+    }
+
+  template<typename _II, typename _Tp, typename _Alloc>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II __first1, _II __last1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __first2,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	::__gnu_debug::__unsafe(__first1), ::__gnu_debug::__unsafe(__last1),
+	__first2.base(), __last2.base());
+    }
+
+  template<typename _II, typename _Tp, typename _Alloc>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      int>::__type
+    __lexicographical_compare_aux(_II __first1, _II __last1,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __first2,
+      const ::__gnu_debug::_Safe_iterator<
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+	__debug::deque<_Tp, _Alloc> >& __last2)
+    {
+      return std::__lexicographical_compare_aux(
+	::__gnu_debug::__unsafe(__first1), ::__gnu_debug::__unsafe(__last1),
+	__first2.base(), __last2.base());
+    }
+
 #if __cplusplus >= 201103L
 
   namespace __detail
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
index a7645a40ac3..d745fec052d 100644
--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
@@ -23,11 +23,12 @@ 
 
 using __gnu_test::test_container;
 using __gnu_test::input_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
 
 typedef test_container<int, input_iterator_wrapper> Container;
-int array1[] = {0, 1};
-int array2[] = {1, 0};
-int array3[] = {1, 0, 1};
+int array1[] = { 0, 1 };
+int array2[] = { 1, 0 };
+int array3[] = { 1, 0, 1 };
 
 void 
 test1()
@@ -74,6 +75,28 @@  test5()
 					con2.begin(), con2.end()) );
 }
 
+void
+test6()
+{
+  VERIFY( std::lexicographical_compare(array2, array2 + 2,
+				       array3, array3 + 3) );
+  VERIFY( !std::lexicographical_compare(array3, array3 + 3,
+					array2, array2 + 2) );
+}
+
+typedef test_container<int, random_access_iterator_wrapper> RaiContainer;
+
+void
+test7()
+{
+  RaiContainer con2(array2, array2 + 2);
+  RaiContainer con3(array3, array3 + 3);
+  VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
+				       con3.begin(), con3.end()) );
+  VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
+					con2.begin(), con2.end()) );
+}
+
 int 
 main()
 {
@@ -82,4 +105,6 @@  main()
   test3();
   test4();
   test5();
+  test6();
+  test7();
 }
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
new file mode 100644
index 00000000000..4b7275a1522
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
@@ -0,0 +1,134 @@ 
+// Copyright (C) 2019 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/>.
+
+#include <algorithm>
+#include <vector>
+#include <deque>
+
+#include <ext/new_allocator.h>
+#include <ext/malloc_allocator.h>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  using namespace std;
+
+  deque<int> d;
+  for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+    d.push_back(i);
+
+  const deque<int>& cd = d;
+
+  VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) );
+  VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) );
+  VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) );
+  VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) );
+}
+
+void test02()
+{
+  using namespace std;
+
+  deque<int> d;
+  for (int i = 0; i != 1000; ++i)
+    d.push_back(i % 10);
+
+  VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+				   d.begin() + 20, d.begin() + 30) );
+  VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+				  d.begin() + 20, d.begin() + 31) );
+  VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+				   d.begin(), d.end() - 20) );
+
+  const deque<int>& cd = d;
+
+  VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+				   cd.begin() + 20, cd.begin() + 30) );
+  VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
+				   d.begin(), d.end() - 20) );
+  VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
+				   cd.begin(), cd.end() - 20) );
+}
+
+void test03()
+{
+  using namespace std;
+
+  deque<int> d1;
+  for (int i = 0; i != 1000; ++i)
+    d1.push_back(i % 10);
+
+  deque<int> d2(d1);
+  for (int i = 0; i != 10; ++i)
+    d2.pop_front();
+
+  VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
+				   d2.begin(), d2.begin() + 10) );
+  VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
+				   d2.begin(), d2.end() - 10) );
+
+  const deque<int>& cd1 = d1;
+  const deque<int>& cd2 = d2;
+
+  VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
+				   cd2.begin() + 20, cd2.begin() + 30) );
+  VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
+				   d2.begin(), d2.end() - 10) );
+  VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
+				  cd1.begin(), cd1.end() - 20) );
+}
+
+void test04()
+{
+  using namespace std;
+
+  deque<int> d;
+  for (int i = 0; i != 1024; ++i)
+    d.push_back(i);
+
+  vector<int> v(d.begin(), d.end());
+
+  VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) );
+  VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) );
+
+  const deque<int>& cd = d;
+
+  VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) );
+  VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) );
+}
+
+void test05()
+{
+  using namespace std;
+
+  int a[] { 0, 1, 2, 3, 4 };
+  deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
+  deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
+
+  VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+  return 0;
+}