Following:
https://gcc.gnu.org/ml/libstdc++/2019-12/msg00028.html
I've done the same kind of work on std::lexicographical_compare algo.
I had to make the internal lexicographical_compare functions return int
rather than bool cause with bool you can't use a chunck based approach
unless you double the number of comparison (once a < b and and another b
< a).
* include/bits/stl_algobase.h
(__lexicographical_compare_impl): Return int.
(__lexicographical_compare::__lc): Likewise.
(__lexicographical_compare_aux1(_II1, _II1, _II2, _II2)): New.
(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
_II2, _II2)): New.
(__lexicographical_compare_aux1(_II1, _II1,
_Deque_iterator<>, _Deque_iterator<>)): New.
(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
_Deque_iterator<>, _Deque_iterator<>)): New.
(__lexicographical_compare_aux): Adapt, call later.
(__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
_II2, _II2)): New.
(__lexicographical_compare_aux(_II1, _II1,
_Safe_iterator<>, _Safe_iterator<>)): New.
(__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
_Safe_iterator<>, _Safe_iterator<>)): New.
(std::lexicographical_compare): Adapt, call later.
* include/bits/deque.tcc (__lex_cmp_dit): New.
(__lexicographical_compare_aux1): Add definitions.
* include/debug/safe_iterator.tcc (__lexicographical_compare_aux): New.
* testsuite/25_algorithms/lexicographical_compare/1.cc (test6, test7):
New.
* testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
New.
Tested under Linux x86_64 normal and debug modes.
François
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index ae5366d6208..ef32d2d19dd 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -1210,6 +1210,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
return true;
}
+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
+ int
+ __lex_cmp_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
+ _II __first2, _II __last2)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ typedef typename _Iter::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_aux1(
+ __first1._M_cur, __first1._M_last, __first2, __first2 + __flen))
+ return __ret;
+
+ __first2 += __flen;
+ __len -= __flen;
+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
+ for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
+ __node != __last1._M_node;
+ __first2 += __flen, __len -= __flen,
+ __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
+ ++__node)
+ if (int __ret = std::__lexicographical_compare_aux1(
+ *__node, *__node + _Iter::_S_buffer_size(),
+ __first2, __first2 + __flen))
+ return __ret;
+
+ return std::__lexicographical_compare_aux1(
+ __last1._M_first, __last1._M_cur, __first2, __last2);
+ }
+
+ return std::__lexicographical_compare_aux1(
+ __first1._M_cur, __last1._M_cur, __first2, __last2);
+ }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _II2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II2>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _II2 __first2, _II2 __last2)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ int
+ __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)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2); }
+
+ template<typename _II1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II1>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _II1 __first1, _II1 __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> _Iter;
+ typedef typename _Iter::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_aux1(
+ __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;
+ }
+
_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 1548afcad4d..26addc26252 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1278,7 +1278,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
template<typename _II1, typename _II2, typename _Compare>
_GLIBCXX20_CONSTEXPR
- bool
+ int
__lexicographical_compare_impl(_II1 __first1, _II1 __last1,
_II2 __first2, _II2 __last2,
_Compare __comp)
@@ -1287,16 +1287,18 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
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>
@@ -1304,13 +1306,13 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
{
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
- static bool __lc(_II1, _II1, _II2, _II2);
+ static int __lc(_II1, _II1, _II2, _II2);
};
template<bool _BoolType>
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
- bool
+ int
__lexicographical_compare<_BoolType>::
__lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
{
@@ -1324,7 +1326,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
{
template<typename _Tp, typename _Up>
_GLIBCXX20_CONSTEXPR
- static bool
+ static int
__lc(const _Tp* __first1, const _Tp* __last1,
const _Up* __first2, const _Up* __last2)
{
@@ -1332,16 +1334,44 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
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 __len1 < __len2 ? -1 : (__len2 < __len1 ? 1 : 0);
}
};
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _II2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II2>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II1>::__value, int>::__type
+ __lexicographical_compare_aux1(
+ _II1, _II1,
+ _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>
+ int
+ __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)
+ inline int
+ __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;
@@ -1356,6 +1386,43 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__first2, __last2);
}
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ inline int
+ __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 _Ite1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ _II1, _II1,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
+
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _Ite2, typename _Seq2, typename _Cat2>
+ int
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
+
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
@@ -1655,10 +1722,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) < 0;
}
/**
@@ -1688,7 +1753,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;
}
#if __cpp_lib_three_way_comparison
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 1d98a882d56..15b1a361e58 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -464,6 +464,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __equal_aux1(__first1, __last1, __first2);
}
+ template<typename _Ite1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ int
+ __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>
+ int
+ __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>
+ int
+ __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 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;
+}
