From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-1.mimecast.com (us-smtp-2.mimecast.com [207.211.31.81]) by sourceware.org (Postfix) with ESMTP id 2D0343851C13 for ; Mon, 8 Jun 2020 18:20:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 2D0343851C13 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-123-XX6jny1WNmW1yubm3uEvDw-1; Mon, 08 Jun 2020 14:20:42 -0400 X-MC-Unique: XX6jny1WNmW1yubm3uEvDw-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 91E53835B48; Mon, 8 Jun 2020 18:20:41 +0000 (UTC) Received: from localhost (unknown [10.33.36.10]) by smtp.corp.redhat.com (Postfix) with ESMTP id 03C765D9E5; Mon, 8 Jun 2020 18:20:40 +0000 (UTC) Date: Mon, 8 Jun 2020 19:20:40 +0100 From: Jonathan Wakely To: =?iso-8859-1?Q?Fran=E7ois?= Dumont Cc: "libstdc++@gcc.gnu.org" , gcc-patches Subject: Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare Message-ID: <20200608182040.GA352899@redhat.com> References: <0cfba2ec-cd66-fe64-a41c-4028403d9dea@gmail.com> MIME-Version: 1.0 In-Reply-To: <0cfba2ec-cd66-fe64-a41c-4028403d9dea@gmail.com> X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=iso-8859-1; format=flowed Content-Transfer-Encoding: 8bit Content-Disposition: inline X-Spam-Status: No, score=-15.3 required=5.0 tests=BAYES_00, BODY_8BITS, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=unavailable autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 08 Jun 2020 18:20:50 -0000 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 _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(__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(__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 _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 _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 _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 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 > _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 >@@ -1305,7 +1307,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER > { > template > _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 > _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 _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 _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 _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 > _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 >+ _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 _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 _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 _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 > _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 _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 _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 _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 RaiContainer; Since last week you can use __gnu_test::random_access_container 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 >+// . >+ >+#include >+#include >+#include >+ >+#include >+#include >+ >+#include >+ >+void test01() >+{ >+ using namespace std; >+ >+ deque d; >+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) >+ d.push_back(i); >+ >+ const deque& 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 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& 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 d1; >+ for (int i = 0; i != 1000; ++i) >+ d1.push_back(i % 10); >+ >+ deque 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& cd1 = d1; >+ const deque& 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 d; >+ for (int i = 0; i != 1024; ++i) >+ d.push_back(i); >+ >+ vector 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& 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 > d1(a, a + 5); >+ deque > d2(a, a + 5); >+ >+ VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) ); >+} >+ >+int main() >+{ >+ test01(); >+ test02(); >+ test03(); >+ test04(); >+ test05(); >+ return 0; >+}