From patchwork Mon Dec 9 10:05:47 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 1206094 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-515490-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="ec8PAGVq"; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="Ok53lfI1"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47Wf3K3WK4z9sNH for ; Mon, 9 Dec 2019 21:06:03 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=M62dN+rnNN/UgayPWGOtmcaZKXaEWbfpcUSJqbHB7mKL5QmF3E IdvcasQ/W/eb3qx9L//gcK/S9bBnYfUMJLy/iXaBhXjs0Ws2jL1RvFO9SliyJ9e6 JIOmoGY4cxm35lRsvaXe8aPHYEeQJ9tkz605xqDLSi+uub82CbM+KPIgk= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=8SOQAr3tL+7Re5kkuRsGtcGLxLU=; b=ec8PAGVqeq3F1nEPMSTS CiZ35BuxOKAbRKp+pAAPrz7cos5SD+PZFdlgH6DRDk9n1eOIoSvhSMAxAeSGNl5N XUPVQyId/mDnW7cv9osKrEuJ7UzkROOp4GmeTkX4mfzNjhtMhOeittP+hNbe817i Qu+9zmF3kxWTpwdbSbLHjRY= Received: (qmail 120230 invoked by alias); 9 Dec 2019 10:05:55 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 120214 invoked by uid 89); 9 Dec 2019 10:05:55 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mail-wr1-f53.google.com Received: from mail-wr1-f53.google.com (HELO mail-wr1-f53.google.com) (209.85.221.53) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 09 Dec 2019 10:05:51 +0000 Received: by mail-wr1-f53.google.com with SMTP id y11so15459752wrt.6; Mon, 09 Dec 2019 02:05:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:from:subject:message-id:date:user-agent:mime-version :content-language; bh=JLDwo/CtXtSNvXd+/dX442PAWSvDutdYv0b3Q1seWng=; b=Ok53lfI1jyQJiLkZpG2oYWfSZBlA4Vz0aKtjhHgDAsgX13k8c8vDwAAPcZhrP/5+6P vYW6RXgD1WPpWOCK/8/Qepd/wbJM1edjrIs98RS24lOakgg//ccLgVehh++UX/zpM/mq MbBH81oWh9LIa29JsFfDLnL7Z09M8+9tuFxQaWbzTTAHAt3pWgHdKmGq5Y9GgKzx7IqF o4wzZIbOcHwoIghpTyBM6MK6g30RRgK82/ooyggoHckn/tJQ6FEyEABhXCaJnsUILsBJ rvBMIx48/bwVleIfOA61WBZLYbSfx2rvH7kJr5XHH+fIxz6YjK03v1oiJ9wZIhGmiZQu JJ4Q== Received: from ?IPv6:2a01:e0a:1dc:b1c0:e5ff:368:85e7:dbaf? ([2a01:e0a:1dc:b1c0:e5ff:368:85e7:dbaf]) by smtp.googlemail.com with ESMTPSA id v17sm26445248wrt.91.2019.12.09.02.05.47 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 09 Dec 2019 02:05:48 -0800 (PST) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH] Extend std::lexicographical_compare optimizations Message-ID: <0386bae1-db5c-fefa-1ff2-bc6ee815c75c@gmail.com> Date: Mon, 9 Dec 2019 11:05:47 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 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 + 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(__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 __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 + 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 __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 _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 @@ -1304,13 +1306,13 @@ _GLIBCXX_END_NAMESPACE_CONTAINER { template _GLIBCXX20_CONSTEXPR - static bool __lc(_II1, _II1, _II2, _II2); + static int __lc(_II1, _II1, _II2, _II2); }; template template _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 _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 __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 __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 + 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) { 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 + _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 + int + __lexicographical_compare_aux( + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&, + _II2, _II2); + + template + int + __lexicographical_compare_aux( + _II1, _II1, + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&, + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&); + + template + 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 @@ -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 + 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 + 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 + 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 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 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 +// . + +#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; +}