00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 #ifndef _ALGOBASE_H
00063 #define _ALGOBASE_H 1
00064
00065 #include <bits/c++config.h>
00066 #include <cstring>
00067 #include <climits>
00068 #include <cstdlib>
00069 #include <cstddef>
00070 #include <iosfwd>
00071 #include <bits/stl_pair.h>
00072 #include <bits/cpp_type_traits.h>
00073 #include <ext/type_traits.h>
00074 #include <bits/stl_iterator_base_types.h>
00075 #include <bits/stl_iterator_base_funcs.h>
00076 #include <bits/stl_iterator.h>
00077 #include <bits/concept_check.h>
00078 #include <debug/debug.h>
00079
00080 _GLIBCXX_BEGIN_NAMESPACE(std)
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091 template<typename _Tp>
00092 inline void
00093 swap(_Tp& __a, _Tp& __b)
00094 {
00095
00096 __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
00097
00098 _Tp __tmp = __a;
00099 __a = __b;
00100 __b = __tmp;
00101 }
00102
00103
00104
00105
00106 template<bool _BoolType>
00107 struct __iter_swap
00108 {
00109 template<typename _ForwardIterator1, typename _ForwardIterator2>
00110 static void
00111 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00112 {
00113 typedef typename iterator_traits<_ForwardIterator1>::value_type
00114 _ValueType1;
00115 _ValueType1 __tmp = *__a;
00116 *__a = *__b;
00117 *__b = __tmp;
00118 }
00119 };
00120
00121 template<>
00122 struct __iter_swap<true>
00123 {
00124 template<typename _ForwardIterator1, typename _ForwardIterator2>
00125 static void
00126 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00127 {
00128 swap(*__a, *__b);
00129 }
00130 };
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141 template<typename _ForwardIterator1, typename _ForwardIterator2>
00142 inline void
00143 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00144 {
00145 typedef typename iterator_traits<_ForwardIterator1>::value_type
00146 _ValueType1;
00147 typedef typename iterator_traits<_ForwardIterator2>::value_type
00148 _ValueType2;
00149
00150
00151 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00152 _ForwardIterator1>)
00153 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00154 _ForwardIterator2>)
00155 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
00156 _ValueType2>)
00157 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
00158 _ValueType1>)
00159
00160 typedef typename iterator_traits<_ForwardIterator1>::reference
00161 _ReferenceType1;
00162 typedef typename iterator_traits<_ForwardIterator2>::reference
00163 _ReferenceType2;
00164 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value &&
00165 __are_same<_ValueType1 &, _ReferenceType1>::__value &&
00166 __are_same<_ValueType2 &, _ReferenceType2>::__value>::
00167 iter_swap(__a, __b);
00168 }
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180 template<typename _Tp>
00181 inline const _Tp&
00182 min(const _Tp& __a, const _Tp& __b)
00183 {
00184
00185 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00186
00187 if (__b < __a)
00188 return __b;
00189 return __a;
00190 }
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202 template<typename _Tp>
00203 inline const _Tp&
00204 max(const _Tp& __a, const _Tp& __b)
00205 {
00206
00207 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00208
00209 if (__a < __b)
00210 return __b;
00211 return __a;
00212 }
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224 template<typename _Tp, typename _Compare>
00225 inline const _Tp&
00226 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
00227 {
00228
00229 if (__comp(__b, __a))
00230 return __b;
00231 return __a;
00232 }
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244 template<typename _Tp, typename _Compare>
00245 inline const _Tp&
00246 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
00247 {
00248
00249 if (__comp(__a, __b))
00250 return __b;
00251 return __a;
00252 }
00253
00254
00255
00256
00257
00258
00259
00260 template<bool, typename>
00261 struct __copy
00262 {
00263 template<typename _II, typename _OI>
00264 static _OI
00265 copy(_II __first, _II __last, _OI __result)
00266 {
00267 for (; __first != __last; ++__result, ++__first)
00268 *__result = *__first;
00269 return __result;
00270 }
00271 };
00272
00273 template<bool _BoolType>
00274 struct __copy<_BoolType, random_access_iterator_tag>
00275 {
00276 template<typename _II, typename _OI>
00277 static _OI
00278 copy(_II __first, _II __last, _OI __result)
00279 {
00280 typedef typename iterator_traits<_II>::difference_type _Distance;
00281 for(_Distance __n = __last - __first; __n > 0; --__n)
00282 {
00283 *__result = *__first;
00284 ++__first;
00285 ++__result;
00286 }
00287 return __result;
00288 }
00289 };
00290
00291 template<>
00292 struct __copy<true, random_access_iterator_tag>
00293 {
00294 template<typename _Tp>
00295 static _Tp*
00296 copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
00297 {
00298 std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
00299 return __result + (__last - __first);
00300 }
00301 };
00302
00303 template<typename _II, typename _OI>
00304 inline _OI
00305 __copy_aux(_II __first, _II __last, _OI __result)
00306 {
00307 typedef typename iterator_traits<_II>::value_type _ValueTypeI;
00308 typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
00309 typedef typename iterator_traits<_II>::iterator_category _Category;
00310 const bool __simple = (__is_scalar<_ValueTypeI>::__value
00311 && __is_pointer<_II>::__value
00312 && __is_pointer<_OI>::__value
00313 && __are_same<_ValueTypeI, _ValueTypeO>::__value);
00314
00315 return std::__copy<__simple, _Category>::copy(__first, __last, __result);
00316 }
00317
00318
00319 template<typename _CharT>
00320 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00321 ostreambuf_iterator<_CharT> >::__type
00322 __copy_aux(_CharT*, _CharT*, ostreambuf_iterator<_CharT>);
00323
00324 template<typename _CharT>
00325 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00326 ostreambuf_iterator<_CharT> >::__type
00327 __copy_aux(const _CharT*, const _CharT*, ostreambuf_iterator<_CharT>);
00328
00329 template<typename _CharT>
00330 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, _CharT*>::__type
00331 __copy_aux(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>,
00332 _CharT*);
00333
00334 template<bool, bool>
00335 struct __copy_normal
00336 {
00337 template<typename _II, typename _OI>
00338 static _OI
00339 __copy_n(_II __first, _II __last, _OI __result)
00340 { return std::__copy_aux(__first, __last, __result); }
00341 };
00342
00343 template<>
00344 struct __copy_normal<true, false>
00345 {
00346 template<typename _II, typename _OI>
00347 static _OI
00348 __copy_n(_II __first, _II __last, _OI __result)
00349 { return std::__copy_aux(__first.base(), __last.base(), __result); }
00350 };
00351
00352 template<>
00353 struct __copy_normal<false, true>
00354 {
00355 template<typename _II, typename _OI>
00356 static _OI
00357 __copy_n(_II __first, _II __last, _OI __result)
00358 { return _OI(std::__copy_aux(__first, __last, __result.base())); }
00359 };
00360
00361 template<>
00362 struct __copy_normal<true, true>
00363 {
00364 template<typename _II, typename _OI>
00365 static _OI
00366 __copy_n(_II __first, _II __last, _OI __result)
00367 { return _OI(std::__copy_aux(__first.base(), __last.base(),
00368 __result.base())); }
00369 };
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387 template<typename _InputIterator, typename _OutputIterator>
00388 inline _OutputIterator
00389 copy(_InputIterator __first, _InputIterator __last,
00390 _OutputIterator __result)
00391 {
00392
00393 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00394 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00395 typename iterator_traits<_InputIterator>::value_type>)
00396 __glibcxx_requires_valid_range(__first, __last);
00397
00398 const bool __in = __is_normal_iterator<_InputIterator>::__value;
00399 const bool __out = __is_normal_iterator<_OutputIterator>::__value;
00400 return std::__copy_normal<__in, __out>::__copy_n(__first, __last,
00401 __result);
00402 }
00403
00404
00405 template<typename _CharT>
00406 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00407 ostreambuf_iterator<_CharT> >::__type
00408 copy(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>,
00409 ostreambuf_iterator<_CharT>);
00410
00411 template<bool, typename>
00412 struct __copy_backward
00413 {
00414 template<typename _BI1, typename _BI2>
00415 static _BI2
00416 __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
00417 {
00418 while (__first != __last)
00419 *--__result = *--__last;
00420 return __result;
00421 }
00422 };
00423
00424 template<bool _BoolType>
00425 struct __copy_backward<_BoolType, random_access_iterator_tag>
00426 {
00427 template<typename _BI1, typename _BI2>
00428 static _BI2
00429 __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
00430 {
00431 typename iterator_traits<_BI1>::difference_type __n;
00432 for (__n = __last - __first; __n > 0; --__n)
00433 *--__result = *--__last;
00434 return __result;
00435 }
00436 };
00437
00438 template<>
00439 struct __copy_backward<true, random_access_iterator_tag>
00440 {
00441 template<typename _Tp>
00442 static _Tp*
00443 __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
00444 {
00445 const ptrdiff_t _Num = __last - __first;
00446 std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
00447 return __result - _Num;
00448 }
00449 };
00450
00451 template<typename _BI1, typename _BI2>
00452 inline _BI2
00453 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
00454 {
00455 typedef typename iterator_traits<_BI1>::value_type _ValueType1;
00456 typedef typename iterator_traits<_BI2>::value_type _ValueType2;
00457 typedef typename iterator_traits<_BI1>::iterator_category _Category;
00458 const bool __simple = (__is_scalar<_ValueType1>::__value
00459 && __is_pointer<_BI1>::__value
00460 && __is_pointer<_BI2>::__value
00461 && __are_same<_ValueType1, _ValueType2>::__value);
00462
00463 return std::__copy_backward<__simple, _Category>::__copy_b(__first,
00464 __last,
00465 __result);
00466 }
00467
00468 template<bool, bool>
00469 struct __copy_backward_normal
00470 {
00471 template<typename _BI1, typename _BI2>
00472 static _BI2
00473 __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00474 { return std::__copy_backward_aux(__first, __last, __result); }
00475 };
00476
00477 template<>
00478 struct __copy_backward_normal<true, false>
00479 {
00480 template<typename _BI1, typename _BI2>
00481 static _BI2
00482 __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00483 { return std::__copy_backward_aux(__first.base(), __last.base(),
00484 __result); }
00485 };
00486
00487 template<>
00488 struct __copy_backward_normal<false, true>
00489 {
00490 template<typename _BI1, typename _BI2>
00491 static _BI2
00492 __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00493 { return _BI2(std::__copy_backward_aux(__first, __last,
00494 __result.base())); }
00495 };
00496
00497 template<>
00498 struct __copy_backward_normal<true, true>
00499 {
00500 template<typename _BI1, typename _BI2>
00501 static _BI2
00502 __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
00503 { return _BI2(std::__copy_backward_aux(__first.base(), __last.base(),
00504 __result.base())); }
00505 };
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524 template <typename _BI1, typename _BI2>
00525 inline _BI2
00526 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00527 {
00528
00529 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
00530 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
00531 __glibcxx_function_requires(_ConvertibleConcept<
00532 typename iterator_traits<_BI1>::value_type,
00533 typename iterator_traits<_BI2>::value_type>)
00534 __glibcxx_requires_valid_range(__first, __last);
00535
00536 const bool __bi1 = __is_normal_iterator<_BI1>::__value;
00537 const bool __bi2 = __is_normal_iterator<_BI2>::__value;
00538 return std::__copy_backward_normal<__bi1, __bi2>::__copy_b_n(__first,
00539 __last,
00540 __result);
00541 }
00542
00543 template<bool>
00544 struct __fill
00545 {
00546 template<typename _ForwardIterator, typename _Tp>
00547 static void
00548 fill(_ForwardIterator __first, _ForwardIterator __last,
00549 const _Tp& __value)
00550 {
00551 for (; __first != __last; ++__first)
00552 *__first = __value;
00553 }
00554 };
00555
00556 template<>
00557 struct __fill<true>
00558 {
00559 template<typename _ForwardIterator, typename _Tp>
00560 static void
00561 fill(_ForwardIterator __first, _ForwardIterator __last,
00562 const _Tp& __value)
00563 {
00564 const _Tp __tmp = __value;
00565 for (; __first != __last; ++__first)
00566 *__first = __tmp;
00567 }
00568 };
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578
00579
00580
00581 template<typename _ForwardIterator, typename _Tp>
00582 void
00583 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
00584 {
00585
00586 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00587 _ForwardIterator>)
00588 __glibcxx_requires_valid_range(__first, __last);
00589
00590 const bool __scalar = __is_scalar<_Tp>::__value;
00591 std::__fill<__scalar>::fill(__first, __last, __value);
00592 }
00593
00594
00595 inline void
00596 fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
00597 {
00598 __glibcxx_requires_valid_range(__first, __last);
00599 const unsigned char __tmp = __c;
00600 std::memset(__first, __tmp, __last - __first);
00601 }
00602
00603 inline void
00604 fill(signed char* __first, signed char* __last, const signed char& __c)
00605 {
00606 __glibcxx_requires_valid_range(__first, __last);
00607 const signed char __tmp = __c;
00608 std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00609 }
00610
00611 inline void
00612 fill(char* __first, char* __last, const char& __c)
00613 {
00614 __glibcxx_requires_valid_range(__first, __last);
00615 const char __tmp = __c;
00616 std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00617 }
00618
00619 template<bool>
00620 struct __fill_n
00621 {
00622 template<typename _OutputIterator, typename _Size, typename _Tp>
00623 static _OutputIterator
00624 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
00625 {
00626 for (; __n > 0; --__n, ++__first)
00627 *__first = __value;
00628 return __first;
00629 }
00630 };
00631
00632 template<>
00633 struct __fill_n<true>
00634 {
00635 template<typename _OutputIterator, typename _Size, typename _Tp>
00636 static _OutputIterator
00637 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
00638 {
00639 const _Tp __tmp = __value;
00640 for (; __n > 0; --__n, ++__first)
00641 *__first = __tmp;
00642 return __first;
00643 }
00644 };
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657 template<typename _OutputIterator, typename _Size, typename _Tp>
00658 _OutputIterator
00659 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
00660 {
00661
00662 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
00663
00664 const bool __scalar = __is_scalar<_Tp>::__value;
00665 return std::__fill_n<__scalar>::fill_n(__first, __n, __value);
00666 }
00667
00668 template<typename _Size>
00669 inline unsigned char*
00670 fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
00671 {
00672 std::fill(__first, __first + __n, __c);
00673 return __first + __n;
00674 }
00675
00676 template<typename _Size>
00677 inline signed char*
00678 fill_n(signed char* __first, _Size __n, const signed char& __c)
00679 {
00680 std::fill(__first, __first + __n, __c);
00681 return __first + __n;
00682 }
00683
00684 template<typename _Size>
00685 inline char*
00686 fill_n(char* __first, _Size __n, const char& __c)
00687 {
00688 std::fill(__first, __first + __n, __c);
00689 return __first + __n;
00690 }
00691
00692
00693
00694
00695
00696
00697
00698
00699
00700
00701
00702
00703
00704 template<typename _InputIterator1, typename _InputIterator2>
00705 pair<_InputIterator1, _InputIterator2>
00706 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
00707 _InputIterator2 __first2)
00708 {
00709
00710 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00711 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00712 __glibcxx_function_requires(_EqualOpConcept<
00713 typename iterator_traits<_InputIterator1>::value_type,
00714 typename iterator_traits<_InputIterator2>::value_type>)
00715 __glibcxx_requires_valid_range(__first1, __last1);
00716
00717 while (__first1 != __last1 && *__first1 == *__first2)
00718 {
00719 ++__first1;
00720 ++__first2;
00721 }
00722 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
00723 }
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739 template<typename _InputIterator1, typename _InputIterator2,
00740 typename _BinaryPredicate>
00741 pair<_InputIterator1, _InputIterator2>
00742 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
00743 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
00744 {
00745
00746 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00747 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00748 __glibcxx_requires_valid_range(__first1, __last1);
00749
00750 while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
00751 {
00752 ++__first1;
00753 ++__first2;
00754 }
00755 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
00756 }
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769 template<typename _InputIterator1, typename _InputIterator2>
00770 inline bool
00771 equal(_InputIterator1 __first1, _InputIterator1 __last1,
00772 _InputIterator2 __first2)
00773 {
00774
00775 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00776 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00777 __glibcxx_function_requires(_EqualOpConcept<
00778 typename iterator_traits<_InputIterator1>::value_type,
00779 typename iterator_traits<_InputIterator2>::value_type>)
00780 __glibcxx_requires_valid_range(__first1, __last1);
00781
00782 for (; __first1 != __last1; ++__first1, ++__first2)
00783 if (!(*__first1 == *__first2))
00784 return false;
00785 return true;
00786 }
00787
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798
00799
00800
00801 template<typename _InputIterator1, typename _InputIterator2,
00802 typename _BinaryPredicate>
00803 inline bool
00804 equal(_InputIterator1 __first1, _InputIterator1 __last1,
00805 _InputIterator2 __first2,
00806 _BinaryPredicate __binary_pred)
00807 {
00808
00809 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00810 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00811 __glibcxx_requires_valid_range(__first1, __last1);
00812
00813 for (; __first1 != __last1; ++__first1, ++__first2)
00814 if (!__binary_pred(*__first1, *__first2))
00815 return false;
00816 return true;
00817 }
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829
00830
00831
00832
00833 template<typename _InputIterator1, typename _InputIterator2>
00834 bool
00835 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
00836 _InputIterator2 __first2, _InputIterator2 __last2)
00837 {
00838
00839 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00840 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00841 __glibcxx_function_requires(_LessThanOpConcept<
00842 typename iterator_traits<_InputIterator1>::value_type,
00843 typename iterator_traits<_InputIterator2>::value_type>)
00844 __glibcxx_function_requires(_LessThanOpConcept<
00845 typename iterator_traits<_InputIterator2>::value_type,
00846 typename iterator_traits<_InputIterator1>::value_type>)
00847 __glibcxx_requires_valid_range(__first1, __last1);
00848 __glibcxx_requires_valid_range(__first2, __last2);
00849
00850 for (; __first1 != __last1 && __first2 != __last2;
00851 ++__first1, ++__first2)
00852 {
00853 if (*__first1 < *__first2)
00854 return true;
00855 if (*__first2 < *__first1)
00856 return false;
00857 }
00858 return __first1 == __last1 && __first2 != __last2;
00859 }
00860
00861
00862
00863
00864
00865
00866
00867
00868
00869
00870
00871
00872
00873 template<typename _InputIterator1, typename _InputIterator2,
00874 typename _Compare>
00875 bool
00876 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
00877 _InputIterator2 __first2, _InputIterator2 __last2,
00878 _Compare __comp)
00879 {
00880
00881 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00882 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00883 __glibcxx_requires_valid_range(__first1, __last1);
00884 __glibcxx_requires_valid_range(__first2, __last2);
00885
00886 for (; __first1 != __last1 && __first2 != __last2;
00887 ++__first1, ++__first2)
00888 {
00889 if (__comp(*__first1, *__first2))
00890 return true;
00891 if (__comp(*__first2, *__first1))
00892 return false;
00893 }
00894 return __first1 == __last1 && __first2 != __last2;
00895 }
00896
00897 inline bool
00898 lexicographical_compare(const unsigned char* __first1,
00899 const unsigned char* __last1,
00900 const unsigned char* __first2,
00901 const unsigned char* __last2)
00902 {
00903 __glibcxx_requires_valid_range(__first1, __last1);
00904 __glibcxx_requires_valid_range(__first2, __last2);
00905
00906 const size_t __len1 = __last1 - __first1;
00907 const size_t __len2 = __last2 - __first2;
00908 const int __result = std::memcmp(__first1, __first2,
00909 std::min(__len1, __len2));
00910 return __result != 0 ? __result < 0 : __len1 < __len2;
00911 }
00912
00913 inline bool
00914 lexicographical_compare(const char* __first1, const char* __last1,
00915 const char* __first2, const char* __last2)
00916 {
00917 __glibcxx_requires_valid_range(__first1, __last1);
00918 __glibcxx_requires_valid_range(__first2, __last2);
00919
00920 #if CHAR_MAX == SCHAR_MAX
00921 return std::lexicographical_compare((const signed char*) __first1,
00922 (const signed char*) __last1,
00923 (const signed char*) __first2,
00924 (const signed char*) __last2);
00925 #else
00926 return std::lexicographical_compare((const unsigned char*) __first1,
00927 (const unsigned char*) __last1,
00928 (const unsigned char*) __first2,
00929 (const unsigned char*) __last2);
00930 #endif
00931 }
00932
00933 _GLIBCXX_END_NAMESPACE
00934
00935 #endif