From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1059) id D1C333870884; Thu, 25 Jun 2020 14:31:14 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D1C333870884 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1593095474; bh=/n+DHj4MA+dIiioD0l4QhCu6PL589/YZQUSRad/wAXQ=; h=From:To:Subject:Date:From; b=kgFxpEMEqTq5himeFvGQmljDOof4q8yx60NOzqJlJSmIGUQapQm41i3YoSEWICGhI VT3dUhF7hXJy9V0fIHFzqkJmWSANHp4fHApJOIo/8SbEXGmI9VJV+ZeT099SROEIHL V8Nou+5mfd3ihUOMtWdN9/IZ+MqdUSwJ08/P4jn4= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit From: Nathan Sidwell To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc/devel/c++-modules] libstdc++: Extend memcmp optimization in std::lexicographical_compare X-Act-Checkin: gcc X-Git-Author: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Git-Refname: refs/heads/devel/c++-modules X-Git-Oldrev: 371cc683371bedb0e53ebcee0c0e89604a1e74b1 X-Git-Newrev: 3a391adf7a38780f8d01dbac08a2a143fc80b469 Message-Id: <20200625143114.D1C333870884@sourceware.org> Date: Thu, 25 Jun 2020 14:31:14 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 25 Jun 2020 14:31:14 -0000 https://gcc.gnu.org/g:3a391adf7a38780f8d01dbac08a2a143fc80b469 commit 3a391adf7a38780f8d01dbac08a2a143fc80b469 Author: François Dumont Date: Wed Jun 10 17:48:46 2020 +0100 libstdc++: Extend memcmp optimization in std::lexicographical_compare Make the memcmp optimization work for std::deque iterators and safe iterators. Co-authored-by: Jonathan Wakely libstdc++-v3/ChangeLog: 2020-06-08 François Dumont Jonathan Wakely * include/bits/deque.tcc (__lex_cmp_dit): New. (__lexicographical_compare_aux1): Define overloads for deque iterators. * include/bits/stl_algobase.h (__lexicographical_compare::__3way): New static member function. (__lexicographical_compare::__3way): Likewise. (__lexicographical_compare::__lc): Use __3way. (__lexicographical_compare_aux): Rename to __lexicographical_compare_aux1 and declare overloads for deque iterators. (__lexicographical_compare_aux): Define new forwarding function that calls __lexicographical_compare_aux1 and declare new overloads for safe iterators. (lexicographical_compare): Do not use __niter_base on parameters. * include/debug/safe_iterator.tcc (__lexicographical_compare_aux): Define overloads for safe iterators. * testsuite/25_algorithms/lexicographical_compare/1.cc: Add checks with random access iterators. * testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc: New test. Diff: --- libstdc++-v3/include/bits/deque.tcc | 103 +++++++ libstdc++-v3/include/bits/stl_algobase.h | 101 ++++++- libstdc++-v3/include/debug/safe_iterator.tcc | 74 +++++ .../25_algorithms/lexicographical_compare/1.cc | 45 ++- .../lexicographical_compare/deque_iterators/1.cc | 301 +++++++++++++++++++++ 5 files changed, 606 insertions(+), 18 deletions(-) diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index 1d32a1691c7..7d1ec86456a 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -1261,6 +1261,109 @@ _GLIBCXX_END_NAMESPACE_CONTAINER return true; } + template + int + __lex_cmp_dit( + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1, + const _Tp2* __first2, const _Tp2* __last2) + { + const bool __simple = + (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value + && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed + && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed + && __is_pointer<_Ptr>::__value +#if __cplusplus > 201703L && __cpp_lib_concepts + // For C++20 iterator_traits::value_type is non-volatile + // so __is_byte could be true, but we can't use memcmp with + // volatile data. + && !is_volatile_v<_Tp1> + && !is_volatile_v<_Tp2> +#endif + ); + typedef std::__lexicographical_compare<__simple> _Lc; + + while (__first1._M_node != __last1._M_node) + { + const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur; + const ptrdiff_t __len2 = __last2 - __first2; + const ptrdiff_t __len = std::min(__len1, __len2); + // if __len1 > __len2 this will return a positive value: + if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last, + __first2, __first2 + __len)) + return __ret; + + __first1 += __len; + __first2 += __len; + } + return _Lc::__3way(__first1._M_cur, __last1._M_cur, + __first2, __last2); + } + + template + inline bool + __lexicographical_compare_aux1( + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, + _Tp2* __first2, _Tp2* __last2) + { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; } + + template + inline bool + __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) + { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; } + + template + inline bool + __lexicographical_compare_aux1( + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) + { + const bool __simple = + (__is_byte<_Tp1>::__value && __is_byte<_Tp2>::__value + && !__gnu_cxx::__numeric_traits<_Tp1>::__is_signed + && !__gnu_cxx::__numeric_traits<_Tp2>::__is_signed + && __is_pointer<_Ptr1>::__value + && __is_pointer<_Ptr2>::__value +#if __cplusplus > 201703L && __cpp_lib_concepts + // For C++20 iterator_traits::value_type is non-volatile + // so __is_byte could be true, but we can't use memcmp with + // volatile data. + && !is_volatile_v<_Tp1> + && !is_volatile_v<_Tp2> +#endif + ); + typedef std::__lexicographical_compare<__simple> _Lc; + + while (__first1 != __last1) + { + const ptrdiff_t __len2 = __first2._M_node == __last2._M_node + ? __last2._M_cur - __first2._M_cur + : __first2._M_last - __first2._M_cur; + if (__len2 == 0) + return false; + const ptrdiff_t __len1 = __first1._M_node == __last1._M_node + ? __last1._M_cur - __first1._M_cur + : __first1._M_last - __first1._M_cur; + const ptrdiff_t __len = std::min(__len1, __len2); + if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len, + __first2._M_cur, __first2._M_cur + __len)) + return __ret < 0; + + __first1 += __len; + __first2 += __len; + } + + return __last2 != __first2; + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 0163d8f902d..41dd740d34a 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -1313,6 +1313,25 @@ _GLIBCXX_END_NAMESPACE_CONTAINER __first2, __last2, __iter_less_iter()); } + + template + _GLIBCXX20_CONSTEXPR + static int + __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) + { + while (__first1 != __last1) + { + if (__first2 == __last2) + return +1; + if (*__first1 < *__first2) + return -1; + if (*__first2 < *__first1) + return +1; + ++__first1; + ++__first2; + } + return int(__first2 == __last2) - 1; + } }; template<> @@ -1323,21 +1342,28 @@ _GLIBCXX_END_NAMESPACE_CONTAINER static bool __lc(const _Tp* __first1, const _Tp* __last1, const _Up* __first2, const _Up* __last2) + { return __3way(__first1, __last1, __first2, __last2) < 0; } + + template + _GLIBCXX20_CONSTEXPR + static ptrdiff_t + __3way(const _Tp* __first1, const _Tp* __last1, + const _Up* __first2, const _Up* __last2) { const size_t __len1 = __last1 - __first1; const size_t __len2 = __last2 - __first2; if (const size_t __len = std::min(__len1, __len2)) if (int __result = std::__memcmp(__first1, __first2, __len)) - return __result < 0; - return __len1 < __len2; + return __result; + return ptrdiff_t(__len1 - __len2); } }; template _GLIBCXX20_CONSTEXPR inline bool - __lexicographical_compare_aux(_II1 __first1, _II1 __last1, - _II2 __first2, _II2 __last2) + __lexicographical_compare_aux1(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2) { typedef typename iterator_traits<_II1>::value_type _ValueType1; typedef typename iterator_traits<_II2>::value_type _ValueType2; @@ -1360,6 +1386,67 @@ _GLIBCXX_END_NAMESPACE_CONTAINER __first2, __last2); } + template + bool + __lexicographical_compare_aux1( + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _Tp2*, _Tp2*); + + template + bool + __lexicographical_compare_aux1(_Tp1*, _Tp1*, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); + + template + bool + __lexicographical_compare_aux1( + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); + + template + _GLIBCXX20_CONSTEXPR + inline bool + __lexicographical_compare_aux(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2) + { + return std::__lexicographical_compare_aux1(std::__niter_base(__first1), + std::__niter_base(__last1), + std::__niter_base(__first2), + std::__niter_base(__last2)); + } + + template + bool + __lexicographical_compare_aux( + const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, + _II2, _II2); + + template + bool + __lexicographical_compare_aux( + _II1, _II1, + const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&, + const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&); + + template + bool + __lexicographical_compare_aux( + const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&, + const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&); + template _GLIBCXX20_CONSTEXPR _ForwardIterator @@ -1659,10 +1746,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - return std::__lexicographical_compare_aux(std::__niter_base(__first1), - std::__niter_base(__last1), - std::__niter_base(__first2), - std::__niter_base(__last2)); + return std::__lexicographical_compare_aux(__first1, __last1, + __first2, __last2); } /** diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc index 888ac803ae5..f694e514239 100644 --- a/libstdc++-v3/include/debug/safe_iterator.tcc +++ b/libstdc++-v3/include/debug/safe_iterator.tcc @@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __equal_aux1(__first1, __last1, __first2); } + template + bool + __lexicographical_compare_aux( + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1, + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1, + _II2 __first2, _II2 __last2) + { + typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1; + __glibcxx_check_valid_range2(__first1, __last1, __dist1); + __glibcxx_check_valid_range(__first2, __last2); + + if (__dist1.second > ::__gnu_debug::__dp_equality) + return std::__lexicographical_compare_aux(__first1.base(), + __last1.base(), + __first2, __last2); + return std::__lexicographical_compare_aux1(__first1, __last1, + __first2, __last2); + } + + template + bool + __lexicographical_compare_aux( + _II1 __first1, _II1 __last1, + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2, + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2) + { + __glibcxx_check_valid_range(__first1, __last1); + typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2; + __glibcxx_check_valid_range2(__first2, __last2, __dist2); + + if (__dist2.second > ::__gnu_debug::__dp_equality) + return std::__lexicographical_compare_aux(__first1, __last1, + __first2.base(), + __last2.base()); + return std::__lexicographical_compare_aux1(__first1, __last1, + __first2, __last2); + } + + template + bool + __lexicographical_compare_aux( + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1, + const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1, + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2, + const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2) + { + typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1; + __glibcxx_check_valid_range2(__first1, __last1, __dist1); + typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2; + __glibcxx_check_valid_range2(__first2, __last2, __dist2); + + if (__dist1.second > ::__gnu_debug::__dp_equality) + { + if (__dist2.second > ::__gnu_debug::__dp_equality) + return std::__lexicographical_compare_aux(__first1.base(), + __last1.base(), + __first2.base(), + __last2.base()); + return std::__lexicographical_compare_aux(__first1.base(), + __last1.base(), + __first2, __last2); + } + + if (__dist2.second > ::__gnu_debug::__dp_equality) + return std::__lexicographical_compare_aux(__first1, __last1, + __first2.base(), + __last2.base()); + return std::__lexicographical_compare_aux1(__first1, __last1, + __first2, __last2); + } + _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc index 8c2f043f943..9bbc83b7af0 100644 --- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc @@ -29,43 +29,43 @@ int array1[] = {0, 1}; int array2[] = {1, 0}; int array3[] = {1, 0, 1}; -void +void test1() { Container con1(array1, array1); Container con2(array2, array2); - VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(), + VERIFY( !std::lexicographical_compare(con1.begin(), con1.end(), con2.begin(), con2.end()) ); } -void +void test2() { Container con1(array1, array1 + 2); Container con2(array2, array2 + 2); - VERIFY( std::lexicographical_compare(con1.begin(), con1.end(), + VERIFY( std::lexicographical_compare(con1.begin(), con1.end(), con2.begin(), con2.end()) ); } -void +void test3() { Container con1(array1, array1 + 2); Container con2(array2, array2 + 2); - VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(), + VERIFY( !std::lexicographical_compare(con2.begin(), con2.end(), con1.begin(), con1.end()) ); } -void +void test4() { Container con3(array3, array3 + 3); Container con2(array2, array2 + 2); - VERIFY( std::lexicographical_compare(con2.begin(), con2.end(), + VERIFY( std::lexicographical_compare(con2.begin(), con2.end(), con3.begin(), con3.end()) ); } -void +void test5() { Container con3(array3, array3 + 3); @@ -74,7 +74,30 @@ test5() con2.begin(), con2.end()) ); } -int +void +test6() +{ + VERIFY( std::lexicographical_compare(array2, array2 + 2, + array3, array3 + 3) ); + VERIFY( !std::lexicographical_compare(array3, array3 + 3, + array2, array2 + 2) ); +} + +using __gnu_test::random_access_iterator_wrapper; +typedef test_container RaiContainer; + +void +test7() +{ + RaiContainer con2(array2, array2 + 2); + RaiContainer con3(array3, array3 + 3); + VERIFY( std::lexicographical_compare(con2.begin(), con2.end(), + con3.begin(), con3.end()) ); + VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(), + con2.begin(), con2.end()) ); +} + +int main() { test1(); @@ -82,4 +105,6 @@ main() test3(); test4(); test5(); + test6(); + test7(); } diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc new file mode 100644 index 00000000000..14a75358db4 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc @@ -0,0 +1,301 @@ +// 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()) ); + + const deque::iterator first = d.begin(), last = d.end(); + VERIFY( lexicographical_compare(first, last - 1, first, last) ); + VERIFY( !lexicographical_compare(first, last, first, last - 1) ); + VERIFY( lexicographical_compare(first, last, first + 1, last) ); + VERIFY( !lexicographical_compare(first + 1, last, first, last) ); +} + +void test02() +{ + using namespace std; + + deque d; + for (int i = 0; i != 1000; ++i) + d.push_back(i % 10); + + VERIFY( lexicographical_compare(d.begin(), d.begin() + 10, + d.begin() + 21, d.begin() + 31) ); + VERIFY( lexicographical_compare(d.begin(), d.begin() + 10, + d.begin() + 20, d.begin() + 31) ); + VERIFY( ! lexicographical_compare(d.begin() + 1, d.begin() + 10, + d.begin() + 21, d.begin() + 30) ); + VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10, + d.begin() + 20, d.begin() + 30) ); + VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10, + d.begin() + 1 + 20, d.begin() + 30) ); + VERIFY( lexicographical_compare(d.begin(), d.begin() + 10, + d.begin() + 20, d.begin() + 31) ); + VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10, + d.begin(), d.end() - 20) ); + + const deque& cd = d; + + VERIFY( lexicographical_compare(cd.begin(), cd.begin() + 10, + cd.begin() + 21, cd.begin() + 31) ); + VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10, + cd.begin() + 21, cd.begin() + 32) ); + VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10, + cd.begin() + 20, cd.begin() + 30) ); + VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10, + cd.begin() + 21, cd.begin() + 30) ); + VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10, + d.begin(), d.end() - 20) ); + VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10, + cd.begin(), cd.end() - 20) ); +} + +void test03() +{ + using namespace std; + + deque 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()) ); +} + +void +test06() +{ + using namespace std; + + deque d; + int i = 0; + VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) ); + VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) ); +} + +void test07() +{ + 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()) ); + + const deque::iterator first = d.begin(), last = d.end(); + VERIFY( lexicographical_compare(first, last - 1, first, last) ); + VERIFY( !lexicographical_compare(first, last, first, last - 1) ); + VERIFY( lexicographical_compare(first, last, first + 1, last) ); + VERIFY( !lexicographical_compare(first + 1, last, first, last) ); +} + +void test08() +{ + 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() + 21, d.begin() + 31) ); + VERIFY( lexicographical_compare(d.begin(), d.begin() + 10, + d.begin() + 20, d.begin() + 31) ); + VERIFY( ! lexicographical_compare(d.begin() + 1, d.begin() + 10, + d.begin() + 21, d.begin() + 30) ); + VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10, + d.begin() + 20, d.begin() + 30) ); + VERIFY( !lexicographical_compare(d.begin() + 1, d.begin() + 10, + d.begin() + 1 + 20, d.begin() + 30) ); + VERIFY( lexicographical_compare(d.begin(), d.begin() + 10, + d.begin() + 20, d.begin() + 31) ); + VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10, + d.begin(), d.end() - 20) ); + + const deque& cd = d; + + VERIFY( lexicographical_compare(cd.begin(), cd.begin() + 10, + cd.begin() + 21, cd.begin() + 31) ); + VERIFY( lexicographical_compare(cd.begin() + 1, cd.begin() + 10, + cd.begin() + 21, cd.begin() + 32) ); + VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10, + cd.begin() + 20, cd.begin() + 30) ); + VERIFY( !lexicographical_compare(cd.begin() + 1, cd.begin() + 10, + cd.begin() + 21, cd.begin() + 30) ); + VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10, + d.begin(), d.end() - 20) ); + VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10, + cd.begin(), cd.end() - 20) ); +} + +void test09() +{ + 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 test10() +{ + 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 test11() +{ + 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()) ); +} + +void +test12() +{ + using namespace std; + + deque d; + int i = 0; + VERIFY( lexicographical_compare(d.begin(), d.end(), &i, &i + 1) ); + VERIFY( !lexicographical_compare(&i, &i + 1, d.begin(), d.end()) ); +} + +int main() +{ + test01(); + test02(); + test03(); + test04(); + test05(); + test06(); + test07(); + test08(); + test09(); + test10(); + test11(); + test12(); +}