diff options
| -rw-r--r-- | libstdc++-v3/include/bits/deque.tcc | 103 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algobase.h | 101 | ||||
| -rw-r--r-- | libstdc++-v3/include/debug/safe_iterator.tcc | 74 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc | 45 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/25_algorithms/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 1d32a16..7d1ec86 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<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2> + 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<volatile T*>::value_type is non-volatile + // so __is_byte<T> 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<typename _Tp1, typename _Ref1, typename _Ptr1, + typename _Tp2> + 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<typename _Tp1, + typename _Tp2, typename _Ref2, typename _Ptr2> + 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<typename _Tp1, typename _Ref1, typename _Ptr1, + typename _Tp2, typename _Ref2, typename _Ptr2> + 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<volatile T*>::value_type is non-volatile + // so __is_byte<T> 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 0163d8f..41dd740d 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<typename _II1, typename _II2> + _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<typename _Tp, typename _Up> + _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<typename _II1, typename _II2> _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<typename _Tp1, typename _Ref1, typename _Ptr1, + typename _Tp2> + bool + __lexicographical_compare_aux1( + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, + _Tp2*, _Tp2*); + + template<typename _Tp1, + typename _Tp2, typename _Ref2, typename _Ptr2> + bool + __lexicographical_compare_aux1(_Tp1*, _Tp1*, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>, + _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); + + template<typename _Tp1, typename _Ref1, typename _Ptr1, + typename _Tp2, typename _Ref2, typename _Ptr2> + 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<typename _II1, typename _II2> + _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<typename _Iter1, typename _Seq1, typename _Cat1, + typename _II2> + bool + __lexicographical_compare_aux( + const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, + const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, + _II2, _II2); + + template<typename _II1, + typename _Iter2, typename _Seq2, typename _Cat2> + bool + __lexicographical_compare_aux( + _II1, _II1, + const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&, + const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&); + + template<typename _Iter1, typename _Seq1, typename _Cat1, + typename _Iter2, typename _Seq2, typename _Cat2> + 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<typename _ForwardIterator, typename _Tp, typename _Compare> _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 888ac80..f694e51 100644 --- a/libstdc++-v3/include/debug/safe_iterator.tcc +++ b/libstdc++-v3/include/debug/safe_iterator.tcc @@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __equal_aux1(__first1, __last1, __first2); } + template<typename _Ite1, typename _Seq1, typename _Cat1, + typename _II2> + 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<typename _II1, + typename _Ite2, typename _Seq2, typename _Cat2> + 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<typename _Ite1, typename _Seq1, typename _Cat1, + typename _Ite2, typename _Seq2, typename _Cat2> + 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 8c2f043..9bbc83b 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<int, random_access_iterator_wrapper> 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 0000000..14a7535 --- /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 +// <http://www.gnu.org/licenses/>. + +#include <algorithm> +#include <vector> +#include <deque> + +#include <ext/new_allocator.h> +#include <ext/malloc_allocator.h> + +#include <testsuite_hooks.h> + +void test01() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + const deque<int>& cd = d; + + VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), cd.end()) ); + VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), d.end()) ); + VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), d.end()) ); + VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), cd.end()) ); + + const deque<int>::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<int> 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<int>& 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<int> d1; + for (int i = 0; i != 1000; ++i) + d1.push_back(i % 10); + + deque<int> d2(d1); + for (int i = 0; i != 10; ++i) + d2.pop_front(); + + VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10, + d2.begin(), d2.begin() + 10) ); + VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10, + d2.begin(), d2.end() - 10) ); + + const deque<int>& cd1 = d1; + const deque<int>& cd2 = d2; + + VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10, + cd2.begin() + 20, cd2.begin() + 30) ); + VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10, + d2.begin(), d2.end() - 10) ); + VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10, + cd1.begin(), cd1.end() - 20) ); +} + +void test04() +{ + using namespace std; + + deque<int> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + vector<int> v(d.begin(), d.end()); + + VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, v.begin() + 5, v.end()) ); + VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), d.end()) ); + + const deque<int>& cd = d; + + VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), v.end()) ); + VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), cd.end()) ); +} + +void test05() +{ + using namespace std; + + int a[] = { 0, 1, 2, 3, 4 }; + deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5); + deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5); + + VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) ); +} + +void +test06() +{ + using namespace std; + + deque<int> 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<unsigned char> d; + for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i) + d.push_back(i); + + const deque<unsigned char>& 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<unsigned char>::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<unsigned char> 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<unsigned char>& 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<unsigned char> d1; + for (int i = 0; i != 1000; ++i) + d1.push_back(i % 10); + + deque<unsigned char> 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<unsigned char>& cd1 = d1; + const deque<unsigned char>& 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<unsigned char> d; + for (int i = 0; i != 1024; ++i) + d.push_back(i); + + vector<unsigned char> 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<unsigned char>& 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<unsigned char, __gnu_cxx::new_allocator<unsigned char> > d1(a, a + 5); + deque<unsigned char, __gnu_cxx::malloc_allocator<unsigned char> > d2(a, a + 5); + + VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), d2.end()) ); +} + +void +test12() +{ + using namespace std; + + deque<unsigned char> 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(); +} |