On 09/06/20 17:11 +0100, Jonathan Wakely wrote:
On 09/06/20 00:02 +0100, Jonathan Wakely wrote:
On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
On 08/06/20 19:20 +0100, Jonathan Wakely wrote:
On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
Hi
   Here is the last of my algo patches this time to extend
the memcmp optimization to std::deque iterators and
_GLIBCXX_DEBUG mode.
   To do so I had to return int in implementation details of
lexicographical_compare to make sure we can treat a deque
iterator range by chunk in a performant way.
Here's a simpler version, which doesn't alter anything for the
existing code (i.e. all iterators that aren't deque iterators) and
also fixes the infinite loop bug.
This seems simpler and less invasive.
Please take a look.
I've actually tested it in debug mode now, and ...
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc
b/libstdc++-v3/include/debug/safe_iterator.tcc
index 888ac803ae5..db6a301655f 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>
+ int
This should return bool here.
+ __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
And here.
+ __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
And here.
And I've also enhanced the tests so they catch the bug I created where
the __lexicographical_compare_aux1 overload taking two ranges of deque
iterators was still trying to return a three-way result, rather than
bool.
Corrected patch attached.
*Really* attached this time.
But, the 25_algorithms/lexicographical_compare/deque_iterators/1.cc
test doesn't actually test the new code properly, because it only uses
deque<int> which means memcmp isn't even used. We need better tests.
commit 4d501ba840194a28799cb83bcd8aaecd0eec5304
Author: Fran??ois Dumont <fdum...@gcc.gnu.org>
Date: Tue Jun 9 00:01:51 2020 +0100
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 <jwak...@redhat.com>
libstdc++-v3/ChangeLog:
2020-06-08 Fran??ois Dumont <fdum...@gcc.gnu.org>
Jonathan Wakely <jwak...@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.
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 1d32a1691c7..7d1ec86456a 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 0163d8f902d..41dd740d34a 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 888ac803ae5..f694e514239 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 8c2f043f943..9bbc83b7af0 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 00000000000..1d5c758fc61
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
@@ -0,0 +1,165 @@
+// 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()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+ test06();
+}
