libstdc++: Extend memcmp optimization in std::lexicographical_compare
Jonathan Wakely
jwakely@redhat.com
Mon Jun 8 18:20:40 GMT 2020
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.
>
>Tested under Linux x86_64 normal and debug modes.
>
>Â Â Â Â Â Â Â Â Â Â Â * 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)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1(_II1, _II1,
>Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>(__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>Â Â Â Â Â Â Â Â Â Â Â _Deque_iterator<>, _Deque_iterator<>)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux): Adapt, call later.
Is this meant to say "latter"? That's still not correct grammar
though. I think it would be better to name the function it calls
explicitly: "Call __lexicographical_compare_aux1."
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_Safe_iterator<>,
>_Safe_iterator<>,
>Â Â Â Â Â Â Â Â Â Â Â _II2, _II2)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_II1, _II1,
>Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(_Safe_iterator<>,
>_Safe_iterator<>,
>Â Â Â Â Â Â Â Â Â Â Â _Safe_iterator<>, _Safe_iterator<>)): Declare.
>Â Â Â Â Â Â Â Â Â Â Â (std::lexicographical_compare): Adapt, call later without
>__niter_base
>Â Â Â Â Â Â Â Â Â Â Â usage.
>Â Â Â Â Â Â Â Â Â Â Â * include/bits/deque.tcc (__lex_cmp_dit): New.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux1): New.
>Â Â Â Â Â Â Â Â Â Â Â * include/debug/safe_iterator.tcc
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(const _Safe_iterator<>&,
>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, _II2, _II2)): New.
>Â Â Â Â Â Â Â Â Â Â Â (__lexicographical_compare_aux(
>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const_Safe_iterator<>&,
>Â Â Â Â Â Â Â Â Â Â Â const _Safe_iterator<>&, const _Safe_iterator<>&)): New.
>Â Â Â Â Â Â Â Â Â Â Â * testsuite/25_algorithms/lexicographical_compare/1.cc
>(test6, test7):
>Â Â Â Â Â Â Â Â Â Â Â New.
>Â Â Â Â Â Â Â Â Â Â Â *
>testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>Â Â Â Â Â Â Â Â Â Â Â New test.
>
>Ok to commit ?
>
>François
>
>
>diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
>index 1d32a1691c7..d7dbe64f3e1 100644
>--- a/libstdc++-v3/include/bits/deque.tcc
>+++ b/libstdc++-v3/include/bits/deque.tcc
>@@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> return true;
> }
>
>+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
_II is the wrong name here, it mean InputIterator. All callers of this
function are constrained for random access iterators. This cannot be
called with an input iterator. Please use _RAIter.
>+ 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
What does "flen" mean? Why not use len2 for last2 - first2, as we do
elsewhere? And then use len for min(len1, len2)?
>+ = std::min(__len, __first1._M_last - __first1._M_cur);
>+ if (int __ret = std::__lexicographical_compare_aux1(
This call (and the three later in this function) will do overload
resolution again on the full set of __lexicographical_compare_aux1
overloads, which includes the ones for deque iterators. But we know
that __first1._M_cur and __first1._M_last are not deque iterators.
__first2 could be a deque iterator, but I'm not sure if we really want
one function that has to handle that case anyway.
>+ __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>
This is not an input iterator either.
>+ typename __gnu_cxx::__enable_if<
>+ __is_random_access_iter<_II2>::__value, int>::__type
This should be inline.
Also, I'm curious why these overloads use __enable_if rather than the
conventional approach of tag dispatching using iterator_category.
(The same question applies to th __equal_aux1 and __copy_move_a1
overloads for deque iterators as well). It doesn't really matter
though.
>+ __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
This should be inline.
>+ __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); }
I'm not convinced it's useful for this function and the one above it
to share the same logic.
>+ 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);
"flen"? "clen"?
>+ 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;
Isn't this function doing basically the same as __lex_cmp_dit? Why
does it not use the same logic?
Can this whole function just negate the result of __lex_cmp_dit called
with the arguments switched?
return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
That would also fix the bug that makes the following loop forever:
std::deque<int> d;
int i = 0;
std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
>+ }
>+
> _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..ecc50a10c9d 100644
>--- a/libstdc++-v3/include/bits/stl_algobase.h
>+++ b/libstdc++-v3/include/bits/stl_algobase.h
>@@ -1279,7 +1279,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)
>@@ -1288,16 +1288,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;
This is going to produce worse code for the common (non-deque) case,
isn't it?
> }
>
> template<bool _BoolType>
>@@ -1305,7 +1307,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
> {
> template<typename _II1, typename _II2>
> _GLIBCXX20_CONSTEXPR
>- static bool
>+ static int
> __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
> {
> using __gnu_cxx::__ops::__iter_less_iter;
>@@ -1320,7 +1322,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)
> {
>@@ -1328,16 +1330,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);
Again, this will produce worse code.
If you made it return ptrdiff_t instead of int you could just do:
return ptrdiff_t(__len1 - __len2);
But I think we should just not change these __lc helpers, and not try
to reuse them for deque iterators. We can define new helpers that
return the 3-way result that is needed for comparing deque iterators.
>+ 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)
If you rename this to __lexicographical_compare_aux2 instead and add
a one-line forwarding function called __lexicographical_compare_aux1,
then the code above for deque iterators can call the aux2 overload
directly, to avoid doing overload resolution on aux1 again.
> {
> typedef typename iterator_traits<_II1>::value_type _ValueType1;
> typedef typename iterator_traits<_II2>::value_type _ValueType2;
>@@ -1360,6 +1390,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,
Please don't introduce any more "Ite" parameters, this should be _It1
or _Iter1.
>+ 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
>@@ -1659,10 +1726,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;
Why does __lexicographical_compare_aux need to change to return int?
It looks like only __lexicographical_compare_aux1 gets called
recursively for deque iterators, so only that needs to be able to
return -1/0/+1 values.
> }
>
> /**
>@@ -1692,7 +1757,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 888ac803ae5..ca4e2d52d1d 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
>+ __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 8c2f043f943..b8f92bacd85 100644
>--- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>@@ -74,6 +74,29 @@ 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) );
>+}
>+
>+using __gnu_test::random_access_iterator_wrapper;
>+typedef test_container<int, random_access_iterator_wrapper> RaiContainer;
Since last week you can use __gnu_test::random_access_container<int>
for this.
>+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..c686ad5677d
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
>@@ -0,0 +1,134 @@
>+// 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()) );
>+}
>+
>+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;
>+}
More information about the Gcc-patches
mailing list