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 #ifndef _STL_ALGOBASE_H
00058 #define _STL_ALGOBASE_H 1
00059
00060 #include <bits/c++config.h>
00061 #include <cstddef>
00062 #include <bits/functexcept.h>
00063 #include <bits/cpp_type_traits.h>
00064 #include <ext/type_traits.h>
00065 #include <ext/numeric_traits.h>
00066 #include <bits/stl_pair.h>
00067 #include <bits/stl_iterator_base_types.h>
00068 #include <bits/stl_iterator_base_funcs.h>
00069 #include <bits/stl_iterator.h>
00070 #include <bits/concept_check.h>
00071 #include <debug/debug.h>
00072 #include <bits/move.h>
00073
00074 _GLIBCXX_BEGIN_NAMESPACE(std)
00075
00076
00077
00078
00079 template<bool _BoolType>
00080 struct __iter_swap
00081 {
00082 template<typename _ForwardIterator1, typename _ForwardIterator2>
00083 static void
00084 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00085 {
00086 typedef typename iterator_traits<_ForwardIterator1>::value_type
00087 _ValueType1;
00088 _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);
00089 *__a = _GLIBCXX_MOVE(*__b);
00090 *__b = _GLIBCXX_MOVE(__tmp);
00091 }
00092 };
00093
00094 template<>
00095 struct __iter_swap<true>
00096 {
00097 template<typename _ForwardIterator1, typename _ForwardIterator2>
00098 static void
00099 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00100 {
00101 swap(*__a, *__b);
00102 }
00103 };
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115 template<typename _ForwardIterator1, typename _ForwardIterator2>
00116 inline void
00117 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00118 {
00119 typedef typename iterator_traits<_ForwardIterator1>::value_type
00120 _ValueType1;
00121 typedef typename iterator_traits<_ForwardIterator2>::value_type
00122 _ValueType2;
00123
00124
00125 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00126 _ForwardIterator1>)
00127 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00128 _ForwardIterator2>)
00129 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
00130 _ValueType2>)
00131 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
00132 _ValueType1>)
00133
00134 typedef typename iterator_traits<_ForwardIterator1>::reference
00135 _ReferenceType1;
00136 typedef typename iterator_traits<_ForwardIterator2>::reference
00137 _ReferenceType2;
00138 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
00139 && __are_same<_ValueType1&, _ReferenceType1>::__value
00140 && __are_same<_ValueType2&, _ReferenceType2>::__value>::
00141 iter_swap(__a, __b);
00142 }
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156 template<typename _ForwardIterator1, typename _ForwardIterator2>
00157 _ForwardIterator2
00158 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00159 _ForwardIterator2 __first2)
00160 {
00161
00162 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00163 _ForwardIterator1>)
00164 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00165 _ForwardIterator2>)
00166 __glibcxx_requires_valid_range(__first1, __last1);
00167
00168 for (; __first1 != __last1; ++__first1, ++__first2)
00169 std::iter_swap(__first1, __first2);
00170 return __first2;
00171 }
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184 template<typename _Tp>
00185 inline const _Tp&
00186 min(const _Tp& __a, const _Tp& __b)
00187 {
00188
00189 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00190
00191 if (__b < __a)
00192 return __b;
00193 return __a;
00194 }
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207 template<typename _Tp>
00208 inline const _Tp&
00209 max(const _Tp& __a, const _Tp& __b)
00210 {
00211
00212 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00213
00214 if (__a < __b)
00215 return __b;
00216 return __a;
00217 }
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230 template<typename _Tp, typename _Compare>
00231 inline const _Tp&
00232 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
00233 {
00234
00235 if (__comp(__b, __a))
00236 return __b;
00237 return __a;
00238 }
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251 template<typename _Tp, typename _Compare>
00252 inline const _Tp&
00253 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
00254 {
00255
00256 if (__comp(__a, __b))
00257 return __b;
00258 return __a;
00259 }
00260
00261
00262
00263
00264 template<typename _Iterator,
00265 bool _IsNormal = __is_normal_iterator<_Iterator>::__value>
00266 struct __niter_base
00267 {
00268 static _Iterator
00269 __b(_Iterator __it)
00270 { return __it; }
00271 };
00272
00273 template<typename _Iterator>
00274 struct __niter_base<_Iterator, true>
00275 {
00276 static typename _Iterator::iterator_type
00277 __b(_Iterator __it)
00278 { return __it.base(); }
00279 };
00280
00281
00282 template<typename _Iterator,
00283 bool _IsMove = __is_move_iterator<_Iterator>::__value>
00284 struct __miter_base
00285 {
00286 static _Iterator
00287 __b(_Iterator __it)
00288 { return __it; }
00289 };
00290
00291 template<typename _Iterator>
00292 struct __miter_base<_Iterator, true>
00293 {
00294 static typename _Iterator::iterator_type
00295 __b(_Iterator __it)
00296 { return __it.base(); }
00297 };
00298
00299
00300
00301
00302
00303
00304
00305 template<bool, bool, typename>
00306 struct __copy_move
00307 {
00308 template<typename _II, typename _OI>
00309 static _OI
00310 __copy_m(_II __first, _II __last, _OI __result)
00311 {
00312 for (; __first != __last; ++__result, ++__first)
00313 *__result = *__first;
00314 return __result;
00315 }
00316 };
00317
00318 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00319 template<typename _Category>
00320 struct __copy_move<true, false, _Category>
00321 {
00322 template<typename _II, typename _OI>
00323 static _OI
00324 __copy_m(_II __first, _II __last, _OI __result)
00325 {
00326 for (; __first != __last; ++__result, ++__first)
00327 *__result = std::move(*__first);
00328 return __result;
00329 }
00330 };
00331 #endif
00332
00333 template<>
00334 struct __copy_move<false, false, random_access_iterator_tag>
00335 {
00336 template<typename _II, typename _OI>
00337 static _OI
00338 __copy_m(_II __first, _II __last, _OI __result)
00339 {
00340 typedef typename iterator_traits<_II>::difference_type _Distance;
00341 for(_Distance __n = __last - __first; __n > 0; --__n)
00342 {
00343 *__result = *__first;
00344 ++__first;
00345 ++__result;
00346 }
00347 return __result;
00348 }
00349 };
00350
00351 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00352 template<>
00353 struct __copy_move<true, false, random_access_iterator_tag>
00354 {
00355 template<typename _II, typename _OI>
00356 static _OI
00357 __copy_m(_II __first, _II __last, _OI __result)
00358 {
00359 typedef typename iterator_traits<_II>::difference_type _Distance;
00360 for(_Distance __n = __last - __first; __n > 0; --__n)
00361 {
00362 *__result = std::move(*__first);
00363 ++__first;
00364 ++__result;
00365 }
00366 return __result;
00367 }
00368 };
00369 #endif
00370
00371 template<bool _IsMove>
00372 struct __copy_move<_IsMove, true, random_access_iterator_tag>
00373 {
00374 template<typename _Tp>
00375 static _Tp*
00376 __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
00377 {
00378 __builtin_memmove(__result, __first,
00379 sizeof(_Tp) * (__last - __first));
00380 return __result + (__last - __first);
00381 }
00382 };
00383
00384 template<bool _IsMove, typename _II, typename _OI>
00385 inline _OI
00386 __copy_move_a(_II __first, _II __last, _OI __result)
00387 {
00388 typedef typename iterator_traits<_II>::value_type _ValueTypeI;
00389 typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
00390 typedef typename iterator_traits<_II>::iterator_category _Category;
00391 const bool __simple = (__is_pod(_ValueTypeI)
00392 && __is_pointer<_II>::__value
00393 && __is_pointer<_OI>::__value
00394 && __are_same<_ValueTypeI, _ValueTypeO>::__value);
00395
00396 return std::__copy_move<_IsMove, __simple,
00397 _Category>::__copy_m(__first, __last, __result);
00398 }
00399
00400
00401
00402 template<typename _CharT>
00403 struct char_traits;
00404
00405 template<typename _CharT, typename _Traits>
00406 class istreambuf_iterator;
00407
00408 template<typename _CharT, typename _Traits>
00409 class ostreambuf_iterator;
00410
00411 template<bool _IsMove, typename _CharT>
00412 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00413 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
00414 __copy_move_a2(_CharT*, _CharT*,
00415 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
00416
00417 template<bool _IsMove, typename _CharT>
00418 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00419 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
00420 __copy_move_a2(const _CharT*, const _CharT*,
00421 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
00422
00423 template<bool _IsMove, typename _CharT>
00424 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00425 _CharT*>::__type
00426 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
00427 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
00428
00429 template<bool _IsMove, typename _II, typename _OI>
00430 inline _OI
00431 __copy_move_a2(_II __first, _II __last, _OI __result)
00432 {
00433 return _OI(std::__copy_move_a<_IsMove>
00434 (std::__niter_base<_II>::__b(__first),
00435 std::__niter_base<_II>::__b(__last),
00436 std::__niter_base<_OI>::__b(__result)));
00437 }
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456 template<typename _II, typename _OI>
00457 inline _OI
00458 copy(_II __first, _II __last, _OI __result)
00459 {
00460
00461 __glibcxx_function_requires(_InputIteratorConcept<_II>)
00462 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
00463 typename iterator_traits<_II>::value_type>)
00464 __glibcxx_requires_valid_range(__first, __last);
00465
00466 return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
00467 (std::__miter_base<_II>::__b(__first),
00468 std::__miter_base<_II>::__b(__last), __result));
00469 }
00470
00471 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00472
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489 template<typename _II, typename _OI>
00490 inline _OI
00491 move(_II __first, _II __last, _OI __result)
00492 {
00493
00494 __glibcxx_function_requires(_InputIteratorConcept<_II>)
00495 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
00496 typename iterator_traits<_II>::value_type>)
00497 __glibcxx_requires_valid_range(__first, __last);
00498
00499 return (std::__copy_move_a2<true>
00500 (std::__miter_base<_II>::__b(__first),
00501 std::__miter_base<_II>::__b(__last), __result));
00502 }
00503
00504 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
00505 #else
00506 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
00507 #endif
00508
00509 template<bool, bool, typename>
00510 struct __copy_move_backward
00511 {
00512 template<typename _BI1, typename _BI2>
00513 static _BI2
00514 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00515 {
00516 while (__first != __last)
00517 *--__result = *--__last;
00518 return __result;
00519 }
00520 };
00521
00522 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00523 template<typename _Category>
00524 struct __copy_move_backward<true, false, _Category>
00525 {
00526 template<typename _BI1, typename _BI2>
00527 static _BI2
00528 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00529 {
00530 while (__first != __last)
00531 *--__result = std::move(*--__last);
00532 return __result;
00533 }
00534 };
00535 #endif
00536
00537 template<>
00538 struct __copy_move_backward<false, false, random_access_iterator_tag>
00539 {
00540 template<typename _BI1, typename _BI2>
00541 static _BI2
00542 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00543 {
00544 typename iterator_traits<_BI1>::difference_type __n;
00545 for (__n = __last - __first; __n > 0; --__n)
00546 *--__result = *--__last;
00547 return __result;
00548 }
00549 };
00550
00551 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00552 template<>
00553 struct __copy_move_backward<true, false, random_access_iterator_tag>
00554 {
00555 template<typename _BI1, typename _BI2>
00556 static _BI2
00557 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00558 {
00559 typename iterator_traits<_BI1>::difference_type __n;
00560 for (__n = __last - __first; __n > 0; --__n)
00561 *--__result = std::move(*--__last);
00562 return __result;
00563 }
00564 };
00565 #endif
00566
00567 template<bool _IsMove>
00568 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
00569 {
00570 template<typename _Tp>
00571 static _Tp*
00572 __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
00573 {
00574 const ptrdiff_t _Num = __last - __first;
00575 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
00576 return __result - _Num;
00577 }
00578 };
00579
00580 template<bool _IsMove, typename _BI1, typename _BI2>
00581 inline _BI2
00582 __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
00583 {
00584 typedef typename iterator_traits<_BI1>::value_type _ValueType1;
00585 typedef typename iterator_traits<_BI2>::value_type _ValueType2;
00586 typedef typename iterator_traits<_BI1>::iterator_category _Category;
00587 const bool __simple = (__is_pod(_ValueType1)
00588 && __is_pointer<_BI1>::__value
00589 && __is_pointer<_BI2>::__value
00590 && __are_same<_ValueType1, _ValueType2>::__value);
00591
00592 return std::__copy_move_backward<_IsMove, __simple,
00593 _Category>::__copy_move_b(__first,
00594 __last,
00595 __result);
00596 }
00597
00598 template<bool _IsMove, typename _BI1, typename _BI2>
00599 inline _BI2
00600 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
00601 {
00602 return _BI2(std::__copy_move_backward_a<_IsMove>
00603 (std::__niter_base<_BI1>::__b(__first),
00604 std::__niter_base<_BI1>::__b(__last),
00605 std::__niter_base<_BI2>::__b(__result)));
00606 }
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626 template<typename _BI1, typename _BI2>
00627 inline _BI2
00628 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00629 {
00630
00631 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
00632 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
00633 __glibcxx_function_requires(_ConvertibleConcept<
00634 typename iterator_traits<_BI1>::value_type,
00635 typename iterator_traits<_BI2>::value_type>)
00636 __glibcxx_requires_valid_range(__first, __last);
00637
00638 return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
00639 (std::__miter_base<_BI1>::__b(__first),
00640 std::__miter_base<_BI1>::__b(__last), __result));
00641 }
00642
00643 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660
00661
00662 template<typename _BI1, typename _BI2>
00663 inline _BI2
00664 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00665 {
00666
00667 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
00668 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
00669 __glibcxx_function_requires(_ConvertibleConcept<
00670 typename iterator_traits<_BI1>::value_type,
00671 typename iterator_traits<_BI2>::value_type>)
00672 __glibcxx_requires_valid_range(__first, __last);
00673
00674 return (std::__copy_move_backward_a2<true>
00675 (std::__miter_base<_BI1>::__b(__first),
00676 std::__miter_base<_BI1>::__b(__last), __result));
00677 }
00678
00679 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
00680 #else
00681 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
00682 #endif
00683
00684 template<typename _ForwardIterator, typename _Tp>
00685 inline typename
00686 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
00687 __fill_a(_ForwardIterator __first, _ForwardIterator __last,
00688 const _Tp& __value)
00689 {
00690 for (; __first != __last; ++__first)
00691 *__first = __value;
00692 }
00693
00694 template<typename _ForwardIterator, typename _Tp>
00695 inline typename
00696 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
00697 __fill_a(_ForwardIterator __first, _ForwardIterator __last,
00698 const _Tp& __value)
00699 {
00700 const _Tp __tmp = __value;
00701 for (; __first != __last; ++__first)
00702 *__first = __tmp;
00703 }
00704
00705
00706 template<typename _Tp>
00707 inline typename
00708 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
00709 __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
00710 {
00711 const _Tp __tmp = __c;
00712 __builtin_memset(__first, static_cast<unsigned char>(__tmp),
00713 __last - __first);
00714 }
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728 template<typename _ForwardIterator, typename _Tp>
00729 inline void
00730 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
00731 {
00732
00733 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00734 _ForwardIterator>)
00735 __glibcxx_requires_valid_range(__first, __last);
00736
00737 std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first),
00738 std::__niter_base<_ForwardIterator>::__b(__last), __value);
00739 }
00740
00741 template<typename _OutputIterator, typename _Size, typename _Tp>
00742 inline typename
00743 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
00744 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
00745 {
00746 for (; __n > 0; --__n, ++__first)
00747 *__first = __value;
00748 return __first;
00749 }
00750
00751 template<typename _OutputIterator, typename _Size, typename _Tp>
00752 inline typename
00753 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
00754 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
00755 {
00756 const _Tp __tmp = __value;
00757 for (; __n > 0; --__n, ++__first)
00758 *__first = __tmp;
00759 return __first;
00760 }
00761
00762 template<typename _Size, typename _Tp>
00763 inline typename
00764 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
00765 __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
00766 {
00767 std::__fill_a(__first, __first + __n, __c);
00768 return __first + __n;
00769 }
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780
00781
00782
00783 template<typename _OI, typename _Size, typename _Tp>
00784 inline _OI
00785 fill_n(_OI __first, _Size __n, const _Tp& __value)
00786 {
00787
00788 __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
00789
00790 return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first),
00791 __n, __value));
00792 }
00793
00794 template<bool _BoolType>
00795 struct __equal
00796 {
00797 template<typename _II1, typename _II2>
00798 static bool
00799 equal(_II1 __first1, _II1 __last1, _II2 __first2)
00800 {
00801 for (; __first1 != __last1; ++__first1, ++__first2)
00802 if (!(*__first1 == *__first2))
00803 return false;
00804 return true;
00805 }
00806 };
00807
00808 template<>
00809 struct __equal<true>
00810 {
00811 template<typename _Tp>
00812 static bool
00813 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
00814 {
00815 return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
00816 * (__last1 - __first1));
00817 }
00818 };
00819
00820 template<typename _II1, typename _II2>
00821 inline bool
00822 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
00823 {
00824 typedef typename iterator_traits<_II1>::value_type _ValueType1;
00825 typedef typename iterator_traits<_II2>::value_type _ValueType2;
00826 const bool __simple = (__is_integer<_ValueType1>::__value
00827 && __is_pointer<_II1>::__value
00828 && __is_pointer<_II2>::__value
00829 && __are_same<_ValueType1, _ValueType2>::__value);
00830
00831 return std::__equal<__simple>::equal(__first1, __last1, __first2);
00832 }
00833
00834
00835 template<typename, typename>
00836 struct __lc_rai
00837 {
00838 template<typename _II1, typename _II2>
00839 static _II1
00840 __newlast1(_II1, _II1 __last1, _II2, _II2)
00841 { return __last1; }
00842
00843 template<typename _II>
00844 static bool
00845 __cnd2(_II __first, _II __last)
00846 { return __first != __last; }
00847 };
00848
00849 template<>
00850 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
00851 {
00852 template<typename _RAI1, typename _RAI2>
00853 static _RAI1
00854 __newlast1(_RAI1 __first1, _RAI1 __last1,
00855 _RAI2 __first2, _RAI2 __last2)
00856 {
00857 const typename iterator_traits<_RAI1>::difference_type
00858 __diff1 = __last1 - __first1;
00859 const typename iterator_traits<_RAI2>::difference_type
00860 __diff2 = __last2 - __first2;
00861 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
00862 }
00863
00864 template<typename _RAI>
00865 static bool
00866 __cnd2(_RAI, _RAI)
00867 { return true; }
00868 };
00869
00870 template<bool _BoolType>
00871 struct __lexicographical_compare
00872 {
00873 template<typename _II1, typename _II2>
00874 static bool __lc(_II1, _II1, _II2, _II2);
00875 };
00876
00877 template<bool _BoolType>
00878 template<typename _II1, typename _II2>
00879 bool
00880 __lexicographical_compare<_BoolType>::
00881 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
00882 {
00883 typedef typename iterator_traits<_II1>::iterator_category _Category1;
00884 typedef typename iterator_traits<_II2>::iterator_category _Category2;
00885 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
00886
00887 __last1 = __rai_type::__newlast1(__first1, __last1,
00888 __first2, __last2);
00889 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
00890 ++__first1, ++__first2)
00891 {
00892 if (*__first1 < *__first2)
00893 return true;
00894 if (*__first2 < *__first1)
00895 return false;
00896 }
00897 return __first1 == __last1 && __first2 != __last2;
00898 }
00899
00900 template<>
00901 struct __lexicographical_compare<true>
00902 {
00903 template<typename _Tp, typename _Up>
00904 static bool
00905 __lc(const _Tp* __first1, const _Tp* __last1,
00906 const _Up* __first2, const _Up* __last2)
00907 {
00908 const size_t __len1 = __last1 - __first1;
00909 const size_t __len2 = __last2 - __first2;
00910 const int __result = __builtin_memcmp(__first1, __first2,
00911 std::min(__len1, __len2));
00912 return __result != 0 ? __result < 0 : __len1 < __len2;
00913 }
00914 };
00915
00916 template<typename _II1, typename _II2>
00917 inline bool
00918 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
00919 _II2 __first2, _II2 __last2)
00920 {
00921 typedef typename iterator_traits<_II1>::value_type _ValueType1;
00922 typedef typename iterator_traits<_II2>::value_type _ValueType2;
00923 const bool __simple =
00924 (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
00925 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
00926 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
00927 && __is_pointer<_II1>::__value
00928 && __is_pointer<_II2>::__value);
00929
00930 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
00931 __first2, __last2);
00932 }
00933
00934 _GLIBCXX_END_NAMESPACE
00935
00936 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
00937
00938
00939
00940
00941
00942
00943
00944
00945
00946
00947
00948
00949
00950 template<typename _II1, typename _II2>
00951 inline bool
00952 equal(_II1 __first1, _II1 __last1, _II2 __first2)
00953 {
00954
00955 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
00956 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
00957 __glibcxx_function_requires(_EqualOpConcept<
00958 typename iterator_traits<_II1>::value_type,
00959 typename iterator_traits<_II2>::value_type>)
00960 __glibcxx_requires_valid_range(__first1, __last1);
00961
00962 return std::__equal_aux(std::__niter_base<_II1>::__b(__first1),
00963 std::__niter_base<_II1>::__b(__last1),
00964 std::__niter_base<_II2>::__b(__first2));
00965 }
00966
00967
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979
00980
00981
00982 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
00983 inline bool
00984 equal(_IIter1 __first1, _IIter1 __last1,
00985 _IIter2 __first2, _BinaryPredicate __binary_pred)
00986 {
00987
00988 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
00989 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
00990 __glibcxx_requires_valid_range(__first1, __last1);
00991
00992 for (; __first1 != __last1; ++__first1, ++__first2)
00993 if (!bool(__binary_pred(*__first1, *__first2)))
00994 return false;
00995 return true;
00996 }
00997
00998
00999
01000
01001
01002
01003
01004
01005
01006
01007
01008
01009
01010
01011
01012
01013 template<typename _II1, typename _II2>
01014 inline bool
01015 lexicographical_compare(_II1 __first1, _II1 __last1,
01016 _II2 __first2, _II2 __last2)
01017 {
01018
01019 typedef typename iterator_traits<_II1>::value_type _ValueType1;
01020 typedef typename iterator_traits<_II2>::value_type _ValueType2;
01021 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
01022 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
01023 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
01024 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
01025 __glibcxx_requires_valid_range(__first1, __last1);
01026 __glibcxx_requires_valid_range(__first2, __last2);
01027
01028 return std::__lexicographical_compare_aux
01029 (std::__niter_base<_II1>::__b(__first1),
01030 std::__niter_base<_II1>::__b(__last1),
01031 std::__niter_base<_II2>::__b(__first2),
01032 std::__niter_base<_II2>::__b(__last2));
01033 }
01034
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044
01045
01046
01047
01048 template<typename _II1, typename _II2, typename _Compare>
01049 bool
01050 lexicographical_compare(_II1 __first1, _II1 __last1,
01051 _II2 __first2, _II2 __last2, _Compare __comp)
01052 {
01053 typedef typename iterator_traits<_II1>::iterator_category _Category1;
01054 typedef typename iterator_traits<_II2>::iterator_category _Category2;
01055 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
01056
01057
01058 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
01059 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
01060 __glibcxx_requires_valid_range(__first1, __last1);
01061 __glibcxx_requires_valid_range(__first2, __last2);
01062
01063 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
01064 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
01065 ++__first1, ++__first2)
01066 {
01067 if (__comp(*__first1, *__first2))
01068 return true;
01069 if (__comp(*__first2, *__first1))
01070 return false;
01071 }
01072 return __first1 == __last1 && __first2 != __last2;
01073 }
01074
01075
01076
01077
01078
01079
01080
01081
01082
01083
01084
01085
01086
01087
01088 template<typename _InputIterator1, typename _InputIterator2>
01089 pair<_InputIterator1, _InputIterator2>
01090 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
01091 _InputIterator2 __first2)
01092 {
01093
01094 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
01095 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
01096 __glibcxx_function_requires(_EqualOpConcept<
01097 typename iterator_traits<_InputIterator1>::value_type,
01098 typename iterator_traits<_InputIterator2>::value_type>)
01099 __glibcxx_requires_valid_range(__first1, __last1);
01100
01101 while (__first1 != __last1 && *__first1 == *__first2)
01102 {
01103 ++__first1;
01104 ++__first2;
01105 }
01106 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
01107 }
01108
01109
01110
01111
01112
01113
01114
01115
01116
01117
01118
01119
01120
01121
01122
01123
01124
01125 template<typename _InputIterator1, typename _InputIterator2,
01126 typename _BinaryPredicate>
01127 pair<_InputIterator1, _InputIterator2>
01128 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
01129 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
01130 {
01131
01132 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
01133 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
01134 __glibcxx_requires_valid_range(__first1, __last1);
01135
01136 while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
01137 {
01138 ++__first1;
01139 ++__first2;
01140 }
01141 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
01142 }
01143
01144 _GLIBCXX_END_NESTED_NAMESPACE
01145
01146
01147
01148
01149 #ifdef _GLIBCXX_PARALLEL
01150 # include <parallel/algobase.h>
01151 #endif
01152
01153 #endif