libstdc++: Extend memcmp optimization in std::lexicographical_compare

Make the memcmp optimization work for std::deque iterators and safe
iterators.

Co-authored-by: Jonathan Wakely  <jwakely@redhat.com>

libstdc++-v3/ChangeLog:

2020-06-08  François Dumont  <fdumont@gcc.gnu.org>
	    Jonathan Wakely  <jwakely@redhat.com>

	* include/bits/deque.tcc (__lex_cmp_dit): New.
	(__lexicographical_compare_aux1): Define overloads for deque
	iterators.
	* include/bits/stl_algobase.h (__lexicographical_compare::__3way):
	New static member function.
	(__lexicographical_compare<true>::__3way): Likewise.
	(__lexicographical_compare<true>::__lc): Use __3way.
	(__lexicographical_compare_aux): Rename to
	__lexicographical_compare_aux1 and declare overloads for deque
	iterators.
	(__lexicographical_compare_aux): Define new forwarding function
	that calls __lexicographical_compare_aux1 and declare new overloads
	for safe iterators.
	(lexicographical_compare): Do not use __niter_base on
	parameters.
	* include/debug/safe_iterator.tcc
	(__lexicographical_compare_aux): Define overloads for safe
	iterators.
	* testsuite/25_algorithms/lexicographical_compare/1.cc: Add
	checks with random access iterators.
	* testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
	New test.

5 files changed, 606 insertions, 18 deletions

diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 1d32a16..7d1ec86 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1261,6 +1261,109 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
       return true;
     }
 
+  template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2>
+    int
+    __lex_cmp_dit(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
+	const _Tp2* __first2, const _Tp2* __last2)
+    {
+      const bool __simple =
+	(__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+	 && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+	 && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+	 && __is_pointer<_Ptr>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+	 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+	 // so __is_byte<T> could be true, but we can't use memcmp with
+	 // volatile data.
+	 && !is_volatile_v<_Tp1>
+	 && !is_volatile_v<_Tp2>
+#endif
+	 );
+      typedef std::__lexicographical_compare<__simple> _Lc;
+
+      while (__first1._M_node != __last1._M_node)
+	{
+	  const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
+	  const ptrdiff_t __len2 = __last2 - __first2;
+	  const ptrdiff_t __len = std::min(__len1, __len2);
+	  // if __len1 > __len2 this will return a positive value:
+	  if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
+				      __first2, __first2 + __len))
+	    return __ret;
+
+	  __first1 += __len;
+	  __first2 += __len;
+	}
+      return _Lc::__3way(__first1._M_cur, __last1._M_cur,
+			 __first2, __last2);
+    }
+
+  template<typename _Tp1, typename _Ref1, typename _Ptr1,
+	   typename _Tp2>
+    inline bool
+    __lexicographical_compare_aux1(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+	_Tp2* __first2, _Tp2* __last2)
+    { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
+
+  template<typename _Tp1,
+	   typename _Tp2, typename _Ref2, typename _Ptr2>
+    inline  bool
+    __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+    { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
+
+  template<typename _Tp1, typename _Ref1, typename _Ptr1,
+	   typename _Tp2, typename _Ref2, typename _Ptr2>
+    inline bool
+    __lexicographical_compare_aux1(
+		_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+		_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+		_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+		_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+    {
+      const bool __simple =
+	(__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value
+	 && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed
+	 && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed
+	 && __is_pointer<_Ptr1>::__value
+	 && __is_pointer<_Ptr2>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+	 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+	 // so __is_byte<T> could be true, but we can't use memcmp with
+	 // volatile data.
+	 && !is_volatile_v<_Tp1>
+	 && !is_volatile_v<_Tp2>
+#endif
+	 );
+      typedef std::__lexicographical_compare<__simple> _Lc;
+
+      while (__first1 != __last1)
+	{
+	  const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
+	    ? __last2._M_cur - __first2._M_cur
+	    : __first2._M_last - __first2._M_cur;
+	  if (__len2 == 0)
+	    return false;
+	  const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
+	    ? __last1._M_cur - __first1._M_cur
+	    : __first1._M_last - __first1._M_cur;
+	  const ptrdiff_t __len = std::min(__len1, __len2);
+	  if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
+				      __first2._M_cur, __first2._M_cur + __len))
+	    return __ret < 0;
+
+	  __first1 += __len;
+	  __first2 += __len;
+	}
+
+      return __last2 != __first2;
+    }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 0163d8f..41dd740d 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1313,6 +1313,25 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 						     __first2, __last2,
 						     __iter_less_iter());
 	}
+
+      template<typename _II1, typename _II2>
+	_GLIBCXX20_CONSTEXPR
+	static int
+	__3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+	{
+	  while (__first1 != __last1)
+	    {
+	      if (__first2 == __last2)
+		return +1;
+	      if (*__first1 < *__first2)
+		return -1;
+	      if (*__first2 < *__first1)
+		return +1;
+	      ++__first1;
+	      ++__first2;
+	    }
+	  return int(__first2 == __last2) - 1;
+	}
     };
 
   template<>
@@ -1323,21 +1342,28 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 	static bool
 	__lc(const _Tp* __first1, const _Tp* __last1,
 	     const _Up* __first2, const _Up* __last2)
+	{ return __3way(__first1, __last1, __first2, __last2) < 0; }
+
+      template<typename _Tp, typename _Up>
+	_GLIBCXX20_CONSTEXPR
+	static ptrdiff_t
+	__3way(const _Tp* __first1, const _Tp* __last1,
+	       const _Up* __first2, const _Up* __last2)
 	{
 	  const size_t __len1 = __last1 - __first1;
 	  const size_t __len2 = __last2 - __first2;
 	  if (const size_t __len = std::min(__len1, __len2))
 	    if (int __result = std::__memcmp(__first1, __first2, __len))
-	      return __result < 0;
-	  return __len1 < __len2;
+	      return __result;
+	  return ptrdiff_t(__len1 - __len2);
 	}
     };
 
   template<typename _II1, typename _II2>
     _GLIBCXX20_CONSTEXPR
     inline bool
-    __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
-				  _II2 __first2, _II2 __last2)
+    __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
+				   _II2 __first2, _II2 __last2)
     {
       typedef typename iterator_traits<_II1>::value_type _ValueType1;
       typedef typename iterator_traits<_II2>::value_type _ValueType2;
@@ -1360,6 +1386,67 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 							    __first2, __last2);
     }
 
+  template<typename _Tp1, typename _Ref1, typename _Ptr1,
+	   typename _Tp2>
+    bool
+    __lexicographical_compare_aux1(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+	_Tp2*, _Tp2*);
+
+  template<typename _Tp1,
+	   typename _Tp2, typename _Ref2, typename _Ptr2>
+    bool
+    __lexicographical_compare_aux1(_Tp1*, _Tp1*,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+  template<typename _Tp1, typename _Ref1, typename _Ptr1,
+	   typename _Tp2, typename _Ref2, typename _Ptr2>
+    bool
+    __lexicographical_compare_aux1(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+  template<typename _II1, typename _II2>
+    _GLIBCXX20_CONSTEXPR
+    inline bool
+    __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
+				  _II2 __first2, _II2 __last2)
+    {
+      return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
+						 std::__niter_base(__last1),
+						 std::__niter_base(__first2),
+						 std::__niter_base(__last2));
+    }
+
+  template<typename _Iter1, typename _Seq1, typename _Cat1,
+	   typename _II2>
+    bool
+    __lexicographical_compare_aux(
+		const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+		const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+		_II2, _II2);
+
+  template<typename _II1,
+	   typename _Iter2, typename _Seq2, typename _Cat2>
+    bool
+    __lexicographical_compare_aux(
+		_II1, _II1,
+		const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+		const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
+  template<typename _Iter1, typename _Seq1, typename _Cat1,
+	   typename _Iter2, typename _Seq2, typename _Cat2>
+    bool
+    __lexicographical_compare_aux(
+		const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+		const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+		const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+		const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
     _GLIBCXX20_CONSTEXPR
     _ForwardIterator
@@ -1659,10 +1746,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
 
-      return std::__lexicographical_compare_aux(std::__niter_base(__first1),
-						std::__niter_base(__last1),
-						std::__niter_base(__first2),
-						std::__niter_base(__last2));
+      return std::__lexicographical_compare_aux(__first1, __last1,
+						__first2, __last2);
     }
 
   /**
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 888ac80..f694e51 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __equal_aux1(__first1, __last1, __first2);
     }
 
+  template<typename _Ite1, typename _Seq1, typename _Cat1,
+	   typename _II2>
+    bool
+    __lexicographical_compare_aux(
+	const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+	const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+	_II2 __first2, _II2 __last2)
+    {
+      typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+      __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+      __glibcxx_check_valid_range(__first2, __last2);
+
+      if (__dist1.second > ::__gnu_debug::__dp_equality)
+	return std::__lexicographical_compare_aux(__first1.base(),
+						  __last1.base(),
+						  __first2, __last2);
+      return std::__lexicographical_compare_aux1(__first1, __last1,
+						 __first2, __last2);
+    }
+
+  template<typename _II1,
+	   typename _Ite2, typename _Seq2, typename _Cat2>
+    bool
+    __lexicographical_compare_aux(
+	_II1 __first1, _II1 __last1,
+	const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+	const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+    {
+      __glibcxx_check_valid_range(__first1, __last1);
+      typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
+      __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+      if (__dist2.second > ::__gnu_debug::__dp_equality)
+	return std::__lexicographical_compare_aux(__first1, __last1,
+						  __first2.base(),
+						  __last2.base());
+      return std::__lexicographical_compare_aux1(__first1, __last1,
+						 __first2, __last2);
+    }
+
+  template<typename _Ite1, typename _Seq1, typename _Cat1,
+	   typename _Ite2, typename _Seq2, typename _Cat2>
+    bool
+    __lexicographical_compare_aux(
+	const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
+	const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
+	const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
+	const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
+    {
+      typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
+      __glibcxx_check_valid_range2(__first1, __last1, __dist1);
+      typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
+      __glibcxx_check_valid_range2(__first2, __last2, __dist2);
+
+      if (__dist1.second > ::__gnu_debug::__dp_equality)
+	{
+	  if (__dist2.second > ::__gnu_debug::__dp_equality)
+	    return std::__lexicographical_compare_aux(__first1.base(),
+						      __last1.base(),
+						      __first2.base(),
+						      __last2.base());
+	  return std::__lexicographical_compare_aux(__first1.base(),
+						    __last1.base(),
+						    __first2, __last2);
+	}
+
+      if (__dist2.second > ::__gnu_debug::__dp_equality)
+	return std::__lexicographical_compare_aux(__first1, __last1,
+						  __first2.base(),
+						  __last2.base());
+      return std::__lexicographical_compare_aux1(__first1, __last1,
+						 __first2, __last2);
+    }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
index 8c2f043..9bbc83b 100644
--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
@@ -29,43 +29,43 @@ int array1[] = {0, 1};
 int array2[] = {1, 0};
 int array3[] = {1, 0, 1};
 
-void 
+void
 test1()
 {
   Container con1(array1, array1);
   Container con2(array2, array2);
-  VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(), 
+  VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(),
 					con2.begin(), con2.end()) );
 }
 
-void 
+void
 test2()
 {
   Container con1(array1, array1 + 2);
   Container con2(array2, array2 + 2);
-  VERIFY( std::lexicographical_compare(con1.begin(), con1.end(), 
+  VERIFY( std::lexicographical_compare(con1.begin(), con1.end(),
 				       con2.begin(), con2.end()) );
 }
 
-void 
+void
 test3()
 {
   Container con1(array1, array1 + 2);
   Container con2(array2, array2 + 2);
-  VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(), 
+  VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(),
 				        con1.begin(), con1.end()) );
 }
 
-void 
+void
 test4()
 {
   Container con3(array3, array3 + 3);
   Container con2(array2, array2 + 2);
-  VERIFY( std::lexicographical_compare(con2.begin(), con2.end(), 
+  VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
 				       con3.begin(), con3.end()) );
 }
 
-void 
+void
 test5()
 {
   Container con3(array3, array3 + 3);
@@ -74,7 +74,30 @@ test5()
 					con2.begin(), con2.end()) );
 }
 
-int 
+void
+test6()
+{
+  VERIFY( std::lexicographical_compare(array2, array2 + 2,
+				       array3, array3 + 3) );
+  VERIFY( !std::lexicographical_compare(array3, array3 + 3,
+					array2, array2 + 2) );
+}
+
+using __gnu_test::random_access_iterator_wrapper;
+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()
 {
   test1();
@@ -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 0000000..14a7535
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
@@ -0,0 +1,301 @@
+// Copyright (C) 2020 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()) );
+
+  const deque<int>::iterator first = d.begin(), last = d.end();
+  VERIFY( lexicographical_compare(first, last - 1, first, last) );
+  VERIFY( !lexicographical_compare(first, last, first, last - 1) );
+  VERIFY( lexicographical_compare(first, last, first + 1, last) );
+  VERIFY( !lexicographical_compare(first + 1, last, first, last) );
+}
+
+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() + 21, d.begin() + 31) );
+  VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+				  d.begin() + 20, d.begin() + 31) );
+  VERIFY( ! lexicographical_compare(d.begin() + 1, d.begin() + 10,
+				    d.begin() + 21, d.begin() + 30) );
+  VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+				   d.begin() + 20, d.begin() + 30) );
+  VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10,
+				   d.begin() + 1 + 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() + 21, cd.begin() + 31) );
+  VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+				  cd.begin() + 21, cd.begin() + 32) );
+  VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+				   cd.begin() + 20, cd.begin() + 30) );
+  VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+				   cd.begin() + 21, 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()) );
+}
+
+void
+test06()
+{
+  using namespace std;
+
+  deque<int> d;
+  int i = 0;
+  VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) );
+  VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) );
+}
+
+void test07()
+{
+  using namespace std;
+
+  deque<unsigned char> d;
+  for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+    d.push_back(i);
+
+  const deque<unsigned char>& 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()) );
+
+  const deque<unsigned char>::iterator first = d.begin(), last = d.end();
+  VERIFY( lexicographical_compare(first, last - 1, first, last) );
+  VERIFY( !lexicographical_compare(first, last, first, last - 1) );
+  VERIFY( lexicographical_compare(first, last, first + 1, last) );
+  VERIFY( !lexicographical_compare(first + 1, last, first, last) );
+}
+
+void test08()
+{
+  using namespace std;
+
+  deque<unsigned char> d;
+  for (int i = 0; i != 1000; ++i)
+    d.push_back(i % 10);
+
+  VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+				  d.begin() + 21, d.begin() + 31) );
+  VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
+				  d.begin() + 20, d.begin() + 31) );
+  VERIFY( ! lexicographical_compare(d.begin() + 1, d.begin() + 10,
+				    d.begin() + 21, d.begin() + 30) );
+  VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
+				   d.begin() + 20, d.begin() + 30) );
+  VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10,
+				   d.begin() + 1 + 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<unsigned char>& cd = d;
+
+  VERIFY( lexicographical_compare(cd.begin(), cd.begin() + 10,
+				  cd.begin() + 21, cd.begin() + 31) );
+  VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+				  cd.begin() + 21, cd.begin() + 32) );
+  VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
+				   cd.begin() + 20, cd.begin() + 30) );
+  VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10,
+				   cd.begin() + 21, 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 test09()
+{
+  using namespace std;
+
+  deque<unsigned char> d1;
+  for (int i = 0; i != 1000; ++i)
+    d1.push_back(i % 10);
+
+  deque<unsigned char> 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<unsigned char>& cd1 = d1;
+  const deque<unsigned char>& 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 test10()
+{
+  using namespace std;
+
+  deque<unsigned char> d;
+  for (int i = 0; i != 1024; ++i)
+    d.push_back(i);
+
+  vector<unsigned char> 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<unsigned char>& 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 test11()
+{
+  using namespace std;
+
+  int a[] = { 0, 1, 2, 3, 4 };
+  deque<unsigned char, __gnu_cxx::new_allocator<unsigned char> > d1(a, a + 5);
+  deque<unsigned char, __gnu_cxx::malloc_allocator<unsigned char> > d2(a, a + 5);
+
+  VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) );
+}
+
+void
+test12()
+{
+  using namespace std;
+
+  deque<unsigned char> d;
+  int i = 0;
+  VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) );
+  VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+  test06();
+  test07();
+  test08();
+  test09();
+  test10();
+  test11();
+  test12();
+}