From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 42191 invoked by alias); 16 Sep 2019 19:57:40 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 42176 invoked by uid 89); 16 Sep 2019 19:57:39 -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=cd1 X-HELO: mail-wr1-f42.google.com Received: from mail-wr1-f42.google.com (HELO mail-wr1-f42.google.com) (209.85.221.42) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 16 Sep 2019 19:57:35 +0000 Received: by mail-wr1-f42.google.com with SMTP id i18so666765wru.11; Mon, 16 Sep 2019 12:57:35 -0700 (PDT) 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=KaCt1b6nW/7N6iU6mvMRleu2WW2skub6wxCsUglq45E=; b=MXLtQMqdb4gDtDQnMGPP0D72CtUbj0dn3uZJGrj7DCeYVxb/pee7cnzsfxm30rr0x5 bYkDJoIGMQEUbT6ZmEbLrTogUormr8xm4JAKhQbeZthp1TFR/toOpU3YXwaO2LiiTw6f 3ytP2CdDV8DuXtjUVdTsaAV0W6AhClEnM5CEThfuJ9sv/adyB5lmCdMfxnMScJd64KWU w/3by2uARydRI81lhphENDOZGU8GwPceJedEQf9K/jt09uSBnfa9F18AC+VrtVqUNsm2 hzETS0+jryNMzH3cR6plr8zGtnwgfG+RUmB+uClXHNUyjxcBqtK7scgWUAZkTQprO0ui +J5Q== Return-Path: Received: from ?IPv6:2a01:e0a:1dc:b1c0:9007:d5a6:aa27:643e? ([2a01:e0a:1dc:b1c0:9007:d5a6:aa27:643e]) by smtp.googlemail.com with ESMTPSA id h63sm203281wmf.15.2019.09.16.12.57.31 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 16 Sep 2019 12:57:32 -0700 (PDT) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: [PATCH] lexicographical_comparison enhancements Message-ID: Date: Mon, 16 Sep 2019 19:57:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.8.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------FA0F6A4FD02B448F7B0083ED" X-SW-Source: 2019-09/txt/msg00956.txt.bz2 This is a multi-part message in MIME format. --------------FA0F6A4FD02B448F7B0083ED Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-length: 2015 Hi This is the next part of: https://gcc.gnu.org/ml/libstdc++/2019-09/msg00048.html This time it is to improve behavior of std::lexicographical_compare for deque or safe iterators. To do so I had to make lc internal implementation return int rather than bool otherwise it is impossible to have a chunk base approach for the deque iterators. I'm surprised that std::lexicographical_compare returns a bool by the way, usually comparisons return int. Tested under Linux x86_64 normal and debug modes. Ok to commit ?     * 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/stl_deque.h (__lexicographical_compare_aux1): New     declarations.     * include/bits/deque.tcc (__lex_cmp_dit): New.     (__lexicographical_compare_aux1): New definitions.     * include/debug/safe_iterator.h (__lexicographical_compare_aux): New.     * testsuite/25_algorithms/lexicographical_compare/1.cc (test6, test7):     New.     * testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:     New. François --------------FA0F6A4FD02B448F7B0083ED Content-Type: text/x-patch; name="lexicographical_cmp.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="lexicographical_cmp.patch" Content-length: 20953 diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index ab996ca52fa..db8f1b03eec 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -1208,6 +1208,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 a165f299a71..4eba053ac75 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -1250,7 +1250,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER template _GLIBCXX20_CONSTEXPR - bool + int __lexicographical_compare_impl(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp) @@ -1259,16 +1259,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 @@ -1276,13 +1278,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) { @@ -1296,7 +1298,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) { @@ -1304,16 +1306,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; @@ -1328,6 +1358,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 @@ -1627,10 +1694,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; } /** @@ -1660,7 +1725,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; } template); + 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>); + _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /** diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index 5f73ee38b6b..1665c95f5df 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -1185,6 +1185,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; +} --------------FA0F6A4FD02B448F7B0083ED--