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