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 #ifndef __GLIBCPP_INTERNAL_ALGO_H
00062 #define __GLIBCPP_INTERNAL_ALGO_H
00063
00064 #include <bits/stl_heap.h>
00065 #include <bits/stl_tempbuf.h>
00066
00067
00068
00069 namespace std
00070 {
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084 template<typename _Tp>
00085 inline const _Tp&
00086 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
00087 {
00088
00089 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
00090 if (__a < __b)
00091 if (__b < __c)
00092 return __b;
00093 else if (__a < __c)
00094 return __c;
00095 else
00096 return __a;
00097 else if (__a < __c)
00098 return __a;
00099 else if (__b < __c)
00100 return __c;
00101 else
00102 return __b;
00103 }
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118 template<typename _Tp, typename _Compare>
00119 inline const _Tp&
00120 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
00121 {
00122
00123 __glibcpp_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
00124 if (__comp(__a, __b))
00125 if (__comp(__b, __c))
00126 return __b;
00127 else if (__comp(__a, __c))
00128 return __c;
00129 else
00130 return __a;
00131 else if (__comp(__a, __c))
00132 return __a;
00133 else if (__comp(__b, __c))
00134 return __c;
00135 else
00136 return __b;
00137 }
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150 template<typename _InputIter, typename _Function>
00151 _Function
00152 for_each(_InputIter __first, _InputIter __last, _Function __f)
00153 {
00154
00155 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00156 for ( ; __first != __last; ++__first)
00157 __f(*__first);
00158 return __f;
00159 }
00160
00161
00162
00163
00164
00165
00166 template<typename _InputIter, typename _Tp>
00167 inline _InputIter
00168 find(_InputIter __first, _InputIter __last,
00169 const _Tp& __val,
00170 input_iterator_tag)
00171 {
00172 while (__first != __last && !(*__first == __val))
00173 ++__first;
00174 return __first;
00175 }
00176
00177
00178
00179
00180
00181
00182 template<typename _InputIter, typename _Predicate>
00183 inline _InputIter
00184 find_if(_InputIter __first, _InputIter __last,
00185 _Predicate __pred,
00186 input_iterator_tag)
00187 {
00188 while (__first != __last && !__pred(*__first))
00189 ++__first;
00190 return __first;
00191 }
00192
00193
00194
00195
00196
00197
00198 template<typename _RandomAccessIter, typename _Tp>
00199 _RandomAccessIter
00200 find(_RandomAccessIter __first, _RandomAccessIter __last,
00201 const _Tp& __val,
00202 random_access_iterator_tag)
00203 {
00204 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
00205 = (__last - __first) >> 2;
00206
00207 for ( ; __trip_count > 0 ; --__trip_count) {
00208 if (*__first == __val) return __first;
00209 ++__first;
00210
00211 if (*__first == __val) return __first;
00212 ++__first;
00213
00214 if (*__first == __val) return __first;
00215 ++__first;
00216
00217 if (*__first == __val) return __first;
00218 ++__first;
00219 }
00220
00221 switch(__last - __first) {
00222 case 3:
00223 if (*__first == __val) return __first;
00224 ++__first;
00225 case 2:
00226 if (*__first == __val) return __first;
00227 ++__first;
00228 case 1:
00229 if (*__first == __val) return __first;
00230 ++__first;
00231 case 0:
00232 default:
00233 return __last;
00234 }
00235 }
00236
00237
00238
00239
00240
00241
00242 template<typename _RandomAccessIter, typename _Predicate>
00243 _RandomAccessIter
00244 find_if(_RandomAccessIter __first, _RandomAccessIter __last,
00245 _Predicate __pred,
00246 random_access_iterator_tag)
00247 {
00248 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
00249 = (__last - __first) >> 2;
00250
00251 for ( ; __trip_count > 0 ; --__trip_count) {
00252 if (__pred(*__first)) return __first;
00253 ++__first;
00254
00255 if (__pred(*__first)) return __first;
00256 ++__first;
00257
00258 if (__pred(*__first)) return __first;
00259 ++__first;
00260
00261 if (__pred(*__first)) return __first;
00262 ++__first;
00263 }
00264
00265 switch(__last - __first) {
00266 case 3:
00267 if (__pred(*__first)) return __first;
00268 ++__first;
00269 case 2:
00270 if (__pred(*__first)) return __first;
00271 ++__first;
00272 case 1:
00273 if (__pred(*__first)) return __first;
00274 ++__first;
00275 case 0:
00276 default:
00277 return __last;
00278 }
00279 }
00280
00281
00282
00283
00284
00285
00286
00287
00288
00289 template<typename _InputIter, typename _Tp>
00290 inline _InputIter
00291 find(_InputIter __first, _InputIter __last,
00292 const _Tp& __val)
00293 {
00294
00295 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00296 __glibcpp_function_requires(_EqualOpConcept<
00297 typename iterator_traits<_InputIter>::value_type, _Tp>)
00298 return find(__first, __last, __val, __iterator_category(__first));
00299 }
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309 template<typename _InputIter, typename _Predicate>
00310 inline _InputIter
00311 find_if(_InputIter __first, _InputIter __last,
00312 _Predicate __pred)
00313 {
00314
00315 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00316 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00317 typename iterator_traits<_InputIter>::value_type>)
00318 return find_if(__first, __last, __pred, __iterator_category(__first));
00319 }
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329 template<typename _ForwardIter>
00330 _ForwardIter
00331 adjacent_find(_ForwardIter __first, _ForwardIter __last)
00332 {
00333
00334 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00335 __glibcpp_function_requires(_EqualityComparableConcept<
00336 typename iterator_traits<_ForwardIter>::value_type>)
00337 if (__first == __last)
00338 return __last;
00339 _ForwardIter __next = __first;
00340 while(++__next != __last) {
00341 if (*__first == *__next)
00342 return __first;
00343 __first = __next;
00344 }
00345 return __last;
00346 }
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358 template<typename _ForwardIter, typename _BinaryPredicate>
00359 _ForwardIter
00360 adjacent_find(_ForwardIter __first, _ForwardIter __last,
00361 _BinaryPredicate __binary_pred)
00362 {
00363
00364 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00365 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00366 typename iterator_traits<_ForwardIter>::value_type,
00367 typename iterator_traits<_ForwardIter>::value_type>)
00368 if (__first == __last)
00369 return __last;
00370 _ForwardIter __next = __first;
00371 while(++__next != __last) {
00372 if (__binary_pred(*__first, *__next))
00373 return __first;
00374 __first = __next;
00375 }
00376 return __last;
00377 }
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387 template<typename _InputIter, typename _Tp>
00388 typename iterator_traits<_InputIter>::difference_type
00389 count(_InputIter __first, _InputIter __last, const _Tp& __value)
00390 {
00391
00392 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00393 __glibcpp_function_requires(_EqualityComparableConcept<
00394 typename iterator_traits<_InputIter>::value_type >)
00395 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
00396 typename iterator_traits<_InputIter>::difference_type __n = 0;
00397 for ( ; __first != __last; ++__first)
00398 if (*__first == __value)
00399 ++__n;
00400 return __n;
00401 }
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411 template<typename _InputIter, typename _Predicate>
00412 typename iterator_traits<_InputIter>::difference_type
00413 count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
00414 {
00415
00416 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00417 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00418 typename iterator_traits<_InputIter>::value_type>)
00419 typename iterator_traits<_InputIter>::difference_type __n = 0;
00420 for ( ; __first != __last; ++__first)
00421 if (__pred(*__first))
00422 ++__n;
00423 return __n;
00424 }
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450 template<typename _ForwardIter1, typename _ForwardIter2>
00451 _ForwardIter1
00452 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00453 _ForwardIter2 __first2, _ForwardIter2 __last2)
00454 {
00455
00456 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
00457 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
00458 __glibcpp_function_requires(_EqualOpConcept<
00459 typename iterator_traits<_ForwardIter1>::value_type,
00460 typename iterator_traits<_ForwardIter2>::value_type>)
00461
00462
00463 if (__first1 == __last1 || __first2 == __last2)
00464 return __first1;
00465
00466
00467 _ForwardIter2 __tmp(__first2);
00468 ++__tmp;
00469 if (__tmp == __last2)
00470 return find(__first1, __last1, *__first2);
00471
00472
00473
00474 _ForwardIter2 __p1, __p;
00475
00476 __p1 = __first2; ++__p1;
00477
00478 _ForwardIter1 __current = __first1;
00479
00480 while (__first1 != __last1) {
00481 __first1 = find(__first1, __last1, *__first2);
00482 if (__first1 == __last1)
00483 return __last1;
00484
00485 __p = __p1;
00486 __current = __first1;
00487 if (++__current == __last1)
00488 return __last1;
00489
00490 while (*__current == *__p) {
00491 if (++__p == __last2)
00492 return __first1;
00493 if (++__current == __last1)
00494 return __last1;
00495 }
00496
00497 ++__first1;
00498 }
00499 return __first1;
00500 }
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522 template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred>
00523 _ForwardIter1
00524 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00525 _ForwardIter2 __first2, _ForwardIter2 __last2,
00526 _BinaryPred __predicate)
00527 {
00528
00529 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
00530 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
00531 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
00532 typename iterator_traits<_ForwardIter1>::value_type,
00533 typename iterator_traits<_ForwardIter2>::value_type>)
00534
00535
00536 if (__first1 == __last1 || __first2 == __last2)
00537 return __first1;
00538
00539
00540 _ForwardIter2 __tmp(__first2);
00541 ++__tmp;
00542 if (__tmp == __last2) {
00543 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00544 ++__first1;
00545 return __first1;
00546 }
00547
00548
00549
00550 _ForwardIter2 __p1, __p;
00551
00552 __p1 = __first2; ++__p1;
00553
00554 _ForwardIter1 __current = __first1;
00555
00556 while (__first1 != __last1) {
00557 while (__first1 != __last1) {
00558 if (__predicate(*__first1, *__first2))
00559 break;
00560 ++__first1;
00561 }
00562 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00563 ++__first1;
00564 if (__first1 == __last1)
00565 return __last1;
00566
00567 __p = __p1;
00568 __current = __first1;
00569 if (++__current == __last1) return __last1;
00570
00571 while (__predicate(*__current, *__p)) {
00572 if (++__p == __last2)
00573 return __first1;
00574 if (++__current == __last1)
00575 return __last1;
00576 }
00577
00578 ++__first1;
00579 }
00580 return __first1;
00581 }
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596 template<typename _ForwardIter, typename _Integer, typename _Tp>
00597 _ForwardIter
00598 search_n(_ForwardIter __first, _ForwardIter __last,
00599 _Integer __count, const _Tp& __val)
00600 {
00601
00602 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00603 __glibcpp_function_requires(_EqualityComparableConcept<
00604 typename iterator_traits<_ForwardIter>::value_type>)
00605 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
00606
00607 if (__count <= 0)
00608 return __first;
00609 else {
00610 __first = find(__first, __last, __val);
00611 while (__first != __last) {
00612 typename iterator_traits<_ForwardIter>::difference_type __n = __count;
00613 --__n;
00614 _ForwardIter __i = __first;
00615 ++__i;
00616 while (__i != __last && __n != 0 && *__i == __val) {
00617 ++__i;
00618 --__n;
00619 }
00620 if (__n == 0)
00621 return __first;
00622 else
00623 __first = find(__i, __last, __val);
00624 }
00625 return __last;
00626 }
00627 }
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644 template<typename _ForwardIter, typename _Integer, typename _Tp,
00645 typename _BinaryPred>
00646 _ForwardIter
00647 search_n(_ForwardIter __first, _ForwardIter __last,
00648 _Integer __count, const _Tp& __val,
00649 _BinaryPred __binary_pred)
00650 {
00651
00652 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00653 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
00654 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
00655
00656 if (__count <= 0)
00657 return __first;
00658 else {
00659 while (__first != __last) {
00660 if (__binary_pred(*__first, __val))
00661 break;
00662 ++__first;
00663 }
00664 while (__first != __last) {
00665 typename iterator_traits<_ForwardIter>::difference_type __n = __count;
00666 --__n;
00667 _ForwardIter __i = __first;
00668 ++__i;
00669 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
00670 ++__i;
00671 --__n;
00672 }
00673 if (__n == 0)
00674 return __first;
00675 else {
00676 while (__i != __last) {
00677 if (__binary_pred(*__i, __val))
00678 break;
00679 ++__i;
00680 }
00681 __first = __i;
00682 }
00683 }
00684 return __last;
00685 }
00686 }
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698
00699 template<typename _ForwardIter1, typename _ForwardIter2>
00700 _ForwardIter2
00701 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
00702 _ForwardIter2 __first2)
00703 {
00704
00705 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
00706 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
00707 __glibcpp_function_requires(_ConvertibleConcept<
00708 typename iterator_traits<_ForwardIter1>::value_type,
00709 typename iterator_traits<_ForwardIter2>::value_type>)
00710 __glibcpp_function_requires(_ConvertibleConcept<
00711 typename iterator_traits<_ForwardIter2>::value_type,
00712 typename iterator_traits<_ForwardIter1>::value_type>)
00713
00714 for ( ; __first1 != __last1; ++__first1, ++__first2)
00715 iter_swap(__first1, __first2);
00716 return __first2;
00717 }
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734 template<typename _InputIter, typename _OutputIter, typename _UnaryOperation>
00735 _OutputIter
00736 transform(_InputIter __first, _InputIter __last,
00737 _OutputIter __result, _UnaryOperation __unary_op)
00738 {
00739
00740 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00741 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00742
00743 __typeof__(__unary_op(*__first))>)
00744
00745 for ( ; __first != __last; ++__first, ++__result)
00746 *__result = __unary_op(*__first);
00747 return __result;
00748 }
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
00768 typename _BinaryOperation>
00769 _OutputIter
00770 transform(_InputIter1 __first1, _InputIter1 __last1,
00771 _InputIter2 __first2, _OutputIter __result,
00772 _BinaryOperation __binary_op)
00773 {
00774
00775 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00776 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00777 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00778
00779 __typeof__(__binary_op(*__first1,*__first2))>)
00780
00781 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
00782 *__result = __binary_op(*__first1, *__first2);
00783 return __result;
00784 }
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798 template<typename _ForwardIter, typename _Tp>
00799 void
00800 replace(_ForwardIter __first, _ForwardIter __last,
00801 const _Tp& __old_value, const _Tp& __new_value)
00802 {
00803
00804 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
00805 __glibcpp_function_requires(_EqualOpConcept<
00806 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
00807 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
00808 typename iterator_traits<_ForwardIter>::value_type>)
00809
00810 for ( ; __first != __last; ++__first)
00811 if (*__first == __old_value)
00812 *__first = __new_value;
00813 }
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827 template<typename _ForwardIter, typename _Predicate, typename _Tp>
00828 void
00829 replace_if(_ForwardIter __first, _ForwardIter __last,
00830 _Predicate __pred, const _Tp& __new_value)
00831 {
00832
00833 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
00834 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
00835 typename iterator_traits<_ForwardIter>::value_type>)
00836 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00837 typename iterator_traits<_ForwardIter>::value_type>)
00838
00839 for ( ; __first != __last; ++__first)
00840 if (__pred(*__first))
00841 *__first = __new_value;
00842 }
00843
00844
00845
00846
00847
00848
00849
00850
00851
00852
00853
00854
00855
00856
00857
00858 template<typename _InputIter, typename _OutputIter, typename _Tp>
00859 _OutputIter
00860 replace_copy(_InputIter __first, _InputIter __last,
00861 _OutputIter __result,
00862 const _Tp& __old_value, const _Tp& __new_value)
00863 {
00864
00865 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00866 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00867 typename iterator_traits<_InputIter>::value_type>)
00868 __glibcpp_function_requires(_EqualOpConcept<
00869 typename iterator_traits<_InputIter>::value_type, _Tp>)
00870
00871 for ( ; __first != __last; ++__first, ++__result)
00872 *__result = *__first == __old_value ? __new_value : *__first;
00873 return __result;
00874 }
00875
00876
00877
00878
00879
00880
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890 template<typename _InputIter, typename _OutputIter, typename _Predicate,
00891 typename _Tp>
00892 _OutputIter
00893 replace_copy_if(_InputIter __first, _InputIter __last,
00894 _OutputIter __result,
00895 _Predicate __pred, const _Tp& __new_value)
00896 {
00897
00898 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00899 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00900 typename iterator_traits<_InputIter>::value_type>)
00901 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00902 typename iterator_traits<_InputIter>::value_type>)
00903
00904 for ( ; __first != __last; ++__first, ++__result)
00905 *__result = __pred(*__first) ? __new_value : *__first;
00906 return __result;
00907 }
00908
00909
00910
00911
00912
00913
00914
00915
00916
00917
00918
00919
00920 template<typename _ForwardIter, typename _Generator>
00921 void
00922 generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
00923 {
00924
00925 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00926 __glibcpp_function_requires(_GeneratorConcept<_Generator,
00927 typename iterator_traits<_ForwardIter>::value_type>)
00928
00929 for ( ; __first != __last; ++__first)
00930 *__first = __gen();
00931 }
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942
00943
00944 template<typename _OutputIter, typename _Size, typename _Generator>
00945 _OutputIter
00946 generate_n(_OutputIter __first, _Size __n, _Generator __gen)
00947 {
00948
00949 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00950
00951 __typeof__(__gen())>)
00952
00953 for ( ; __n > 0; --__n, ++__first)
00954 *__first = __gen();
00955 return __first;
00956 }
00957
00958
00959
00960
00961
00962
00963
00964
00965
00966
00967
00968
00969
00970
00971 template<typename _InputIter, typename _OutputIter, typename _Tp>
00972 _OutputIter
00973 remove_copy(_InputIter __first, _InputIter __last,
00974 _OutputIter __result, const _Tp& __value)
00975 {
00976
00977 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00978 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00979 typename iterator_traits<_InputIter>::value_type>)
00980 __glibcpp_function_requires(_EqualOpConcept<
00981 typename iterator_traits<_InputIter>::value_type, _Tp>)
00982
00983 for ( ; __first != __last; ++__first)
00984 if (!(*__first == __value)) {
00985 *__result = *__first;
00986 ++__result;
00987 }
00988 return __result;
00989 }
00990
00991
00992
00993
00994
00995
00996
00997
00998
00999
01000
01001
01002
01003
01004
01005 template<typename _InputIter, typename _OutputIter, typename _Predicate>
01006 _OutputIter
01007 remove_copy_if(_InputIter __first, _InputIter __last,
01008 _OutputIter __result, _Predicate __pred)
01009 {
01010
01011 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
01012 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01013 typename iterator_traits<_InputIter>::value_type>)
01014 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01015 typename iterator_traits<_InputIter>::value_type>)
01016
01017 for ( ; __first != __last; ++__first)
01018 if (!__pred(*__first)) {
01019 *__result = *__first;
01020 ++__result;
01021 }
01022 return __result;
01023 }
01024
01025
01026
01027
01028
01029
01030
01031
01032
01033
01034
01035
01036
01037
01038
01039
01040
01041 template<typename _ForwardIter, typename _Tp>
01042 _ForwardIter
01043 remove(_ForwardIter __first, _ForwardIter __last,
01044 const _Tp& __value)
01045 {
01046
01047 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01048 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
01049 typename iterator_traits<_ForwardIter>::value_type>)
01050 __glibcpp_function_requires(_EqualOpConcept<
01051 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
01052
01053 __first = find(__first, __last, __value);
01054 _ForwardIter __i = __first;
01055 return __first == __last ? __first
01056 : remove_copy(++__i, __last, __first, __value);
01057 }
01058
01059
01060
01061
01062
01063
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075 template<typename _ForwardIter, typename _Predicate>
01076 _ForwardIter
01077 remove_if(_ForwardIter __first, _ForwardIter __last,
01078 _Predicate __pred)
01079 {
01080
01081 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01082 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01083 typename iterator_traits<_ForwardIter>::value_type>)
01084
01085 __first = find_if(__first, __last, __pred);
01086 _ForwardIter __i = __first;
01087 return __first == __last ? __first
01088 : remove_copy_if(++__i, __last, __first, __pred);
01089 }
01090
01091
01092
01093
01094
01095
01096
01097 template<typename _InputIter, typename _OutputIter>
01098 _OutputIter
01099 __unique_copy(_InputIter __first, _InputIter __last,
01100 _OutputIter __result,
01101 output_iterator_tag)
01102 {
01103
01104 typename iterator_traits<_InputIter>::value_type __value = *__first;
01105 *__result = __value;
01106 while (++__first != __last)
01107 if (!(__value == *__first)) {
01108 __value = *__first;
01109 *++__result = __value;
01110 }
01111 return ++__result;
01112 }
01113
01114
01115
01116
01117
01118
01119
01120 template<typename _InputIter, typename _ForwardIter>
01121 _ForwardIter
01122 __unique_copy(_InputIter __first, _InputIter __last,
01123 _ForwardIter __result,
01124 forward_iterator_tag)
01125 {
01126
01127 *__result = *__first;
01128 while (++__first != __last)
01129 if (!(*__result == *__first))
01130 *++__result = *__first;
01131 return ++__result;
01132 }
01133
01134
01135
01136
01137
01138
01139
01140
01141
01142
01143
01144
01145
01146
01147 template<typename _InputIter, typename _OutputIter>
01148 inline _OutputIter
01149 unique_copy(_InputIter __first, _InputIter __last,
01150 _OutputIter __result)
01151 {
01152
01153 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
01154 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01155 typename iterator_traits<_InputIter>::value_type>)
01156 __glibcpp_function_requires(_EqualityComparableConcept<
01157 typename iterator_traits<_InputIter>::value_type>)
01158
01159 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
01160
01161 if (__first == __last) return __result;
01162 return __unique_copy(__first, __last, __result, _IterType());
01163 }
01164
01165
01166
01167
01168
01169
01170
01171
01172 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
01173 _OutputIter
01174 __unique_copy(_InputIter __first, _InputIter __last,
01175 _OutputIter __result,
01176 _BinaryPredicate __binary_pred,
01177 output_iterator_tag)
01178 {
01179
01180 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01181 typename iterator_traits<_InputIter>::value_type,
01182 typename iterator_traits<_InputIter>::value_type>)
01183
01184 typename iterator_traits<_InputIter>::value_type __value = *__first;
01185 *__result = __value;
01186 while (++__first != __last)
01187 if (!__binary_pred(__value, *__first)) {
01188 __value = *__first;
01189 *++__result = __value;
01190 }
01191 return ++__result;
01192 }
01193
01194
01195
01196
01197
01198
01199
01200
01201 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
01202 _ForwardIter
01203 __unique_copy(_InputIter __first, _InputIter __last,
01204 _ForwardIter __result,
01205 _BinaryPredicate __binary_pred,
01206 forward_iterator_tag)
01207 {
01208
01209 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01210 typename iterator_traits<_ForwardIter>::value_type,
01211 typename iterator_traits<_InputIter>::value_type>)
01212
01213 *__result = *__first;
01214 while (++__first != __last)
01215 if (!__binary_pred(*__result, *__first)) *++__result = *__first;
01216 return ++__result;
01217 }
01218
01219
01220
01221
01222
01223
01224
01225
01226
01227
01228
01229
01230
01231
01232
01233
01234 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
01235 inline _OutputIter
01236 unique_copy(_InputIter __first, _InputIter __last,
01237 _OutputIter __result,
01238 _BinaryPredicate __binary_pred)
01239 {
01240
01241 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
01242 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01243 typename iterator_traits<_InputIter>::value_type>)
01244
01245 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
01246
01247 if (__first == __last) return __result;
01248 return __unique_copy(__first, __last,
01249 __result, __binary_pred, _IterType());
01250 }
01251
01252
01253
01254
01255
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265 template<typename _ForwardIter>
01266 _ForwardIter
01267 unique(_ForwardIter __first, _ForwardIter __last)
01268 {
01269
01270 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01271 __glibcpp_function_requires(_EqualityComparableConcept<
01272 typename iterator_traits<_ForwardIter>::value_type>)
01273
01274 __first = adjacent_find(__first, __last);
01275 return unique_copy(__first, __last, __first);
01276 }
01277
01278
01279
01280
01281
01282
01283
01284
01285
01286
01287
01288
01289
01290
01291
01292 template<typename _ForwardIter, typename _BinaryPredicate>
01293 _ForwardIter
01294 unique(_ForwardIter __first, _ForwardIter __last,
01295 _BinaryPredicate __binary_pred)
01296 {
01297
01298 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01299 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01300 typename iterator_traits<_ForwardIter>::value_type,
01301 typename iterator_traits<_ForwardIter>::value_type>)
01302
01303 __first = adjacent_find(__first, __last, __binary_pred);
01304 return unique_copy(__first, __last, __first, __binary_pred);
01305 }
01306
01307
01308
01309
01310
01311
01312
01313 template<typename _BidirectionalIter>
01314 void
01315 __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
01316 bidirectional_iterator_tag)
01317 {
01318 while (true)
01319 if (__first == __last || __first == --__last)
01320 return;
01321 else
01322 iter_swap(__first++, __last);
01323 }
01324
01325
01326
01327
01328
01329
01330
01331 template<typename _RandomAccessIter>
01332 void
01333 __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
01334 random_access_iterator_tag)
01335 {
01336 while (__first < __last)
01337 iter_swap(__first++, --__last);
01338 }
01339
01340
01341
01342
01343
01344
01345
01346
01347
01348
01349
01350
01351 template<typename _BidirectionalIter>
01352 inline void
01353 reverse(_BidirectionalIter __first, _BidirectionalIter __last)
01354 {
01355
01356 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
01357 _BidirectionalIter>)
01358 __reverse(__first, __last, __iterator_category(__first));
01359 }
01360
01361
01362
01363
01364
01365
01366
01367
01368
01369
01370
01371
01372
01373
01374
01375
01376 template<typename _BidirectionalIter, typename _OutputIter>
01377 _OutputIter
01378 reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last,
01379 _OutputIter __result)
01380 {
01381
01382 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
01383 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01384 typename iterator_traits<_BidirectionalIter>::value_type>)
01385
01386 while (__first != __last) {
01387 --__last;
01388 *__result = *__last;
01389 ++__result;
01390 }
01391 return __result;
01392 }
01393
01394
01395
01396
01397
01398
01399
01400
01401 template<typename _EuclideanRingElement>
01402 _EuclideanRingElement
01403 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
01404 {
01405 while (__n != 0) {
01406 _EuclideanRingElement __t = __m % __n;
01407 __m = __n;
01408 __n = __t;
01409 }
01410 return __m;
01411 }
01412
01413
01414
01415
01416
01417
01418 template<typename _ForwardIter>
01419 void
01420 __rotate(_ForwardIter __first,
01421 _ForwardIter __middle,
01422 _ForwardIter __last,
01423 forward_iterator_tag)
01424 {
01425 if ((__first == __middle) || (__last == __middle))
01426 return;
01427
01428 _ForwardIter __first2 = __middle;
01429 do {
01430 swap(*__first++, *__first2++);
01431 if (__first == __middle)
01432 __middle = __first2;
01433 } while (__first2 != __last);
01434
01435 __first2 = __middle;
01436
01437 while (__first2 != __last) {
01438 swap(*__first++, *__first2++);
01439 if (__first == __middle)
01440 __middle = __first2;
01441 else if (__first2 == __last)
01442 __first2 = __middle;
01443 }
01444 }
01445
01446
01447
01448
01449
01450
01451 template<typename _BidirectionalIter>
01452 void
01453 __rotate(_BidirectionalIter __first,
01454 _BidirectionalIter __middle,
01455 _BidirectionalIter __last,
01456 bidirectional_iterator_tag)
01457 {
01458
01459 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
01460 _BidirectionalIter>)
01461
01462 if ((__first == __middle) || (__last == __middle))
01463 return;
01464
01465 __reverse(__first, __middle, bidirectional_iterator_tag());
01466 __reverse(__middle, __last, bidirectional_iterator_tag());
01467
01468 while (__first != __middle && __middle != __last)
01469 swap (*__first++, *--__last);
01470
01471 if (__first == __middle) {
01472 __reverse(__middle, __last, bidirectional_iterator_tag());
01473 }
01474 else {
01475 __reverse(__first, __middle, bidirectional_iterator_tag());
01476 }
01477 }
01478
01479
01480
01481
01482
01483
01484 template<typename _RandomAccessIter>
01485 void
01486 __rotate(_RandomAccessIter __first,
01487 _RandomAccessIter __middle,
01488 _RandomAccessIter __last,
01489 random_access_iterator_tag)
01490 {
01491
01492 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01493 _RandomAccessIter>)
01494
01495 if ((__first == __middle) || (__last == __middle))
01496 return;
01497
01498 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
01499 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
01500
01501 _Distance __n = __last - __first;
01502 _Distance __k = __middle - __first;
01503 _Distance __l = __n - __k;
01504
01505 if (__k == __l) {
01506 swap_ranges(__first, __middle, __middle);
01507 return;
01508 }
01509
01510 _Distance __d = __gcd(__n, __k);
01511
01512 for (_Distance __i = 0; __i < __d; __i++) {
01513 _ValueType __tmp = *__first;
01514 _RandomAccessIter __p = __first;
01515
01516 if (__k < __l) {
01517 for (_Distance __j = 0; __j < __l/__d; __j++) {
01518 if (__p > __first + __l) {
01519 *__p = *(__p - __l);
01520 __p -= __l;
01521 }
01522
01523 *__p = *(__p + __k);
01524 __p += __k;
01525 }
01526 }
01527
01528 else {
01529 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
01530 if (__p < __last - __k) {
01531 *__p = *(__p + __k);
01532 __p += __k;
01533 }
01534
01535 *__p = * (__p - __l);
01536 __p -= __l;
01537 }
01538 }
01539
01540 *__p = __tmp;
01541 ++__first;
01542 }
01543 }
01544
01545
01546
01547
01548
01549
01550
01551
01552
01553
01554
01555
01556
01557
01558
01559
01560
01561
01562
01563 template<typename _ForwardIter>
01564 inline void
01565 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
01566 {
01567
01568 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01569
01570 typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
01571 __rotate(__first, __middle, __last, _IterType());
01572 }
01573
01574
01575
01576
01577
01578
01579
01580
01581
01582
01583
01584
01585
01586
01587
01588
01589
01590
01591 template<typename _ForwardIter, typename _OutputIter>
01592 _OutputIter
01593 rotate_copy(_ForwardIter __first, _ForwardIter __middle,
01594 _ForwardIter __last, _OutputIter __result)
01595 {
01596
01597 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
01598 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01599 typename iterator_traits<_ForwardIter>::value_type>)
01600
01601 return copy(__first, __middle, copy(__middle, __last, __result));
01602 }
01603
01604
01605
01606
01607
01608
01609
01610
01611
01612
01613
01614 template<typename _Distance>
01615 inline _Distance
01616 __random_number(_Distance __n)
01617 {
01618 #ifdef _GLIBCPP_HAVE_DRAND48
01619 return lrand48() % __n;
01620 #else
01621 return rand() % __n;
01622 #endif
01623 }
01624
01625
01626
01627
01628
01629
01630
01631
01632
01633
01634
01635
01636 template<typename _RandomAccessIter>
01637 inline void
01638 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
01639 {
01640
01641 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01642 _RandomAccessIter>)
01643
01644 if (__first == __last) return;
01645 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01646 iter_swap(__i, __first + __random_number((__i - __first) + 1));
01647 }
01648
01649
01650
01651
01652
01653
01654
01655
01656
01657
01658
01659
01660
01661
01662 template<typename _RandomAccessIter, typename _RandomNumberGenerator>
01663 void
01664 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
01665 _RandomNumberGenerator& __rand)
01666 {
01667
01668 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01669 _RandomAccessIter>)
01670
01671 if (__first == __last) return;
01672 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01673 iter_swap(__i, __first + __rand((__i - __first) + 1));
01674 }
01675
01676
01677
01678
01679
01680
01681
01682 template<typename _ForwardIter, typename _Predicate>
01683 _ForwardIter
01684 __partition(_ForwardIter __first, _ForwardIter __last,
01685 _Predicate __pred,
01686 forward_iterator_tag)
01687 {
01688 if (__first == __last) return __first;
01689
01690 while (__pred(*__first))
01691 if (++__first == __last) return __first;
01692
01693 _ForwardIter __next = __first;
01694
01695 while (++__next != __last)
01696 if (__pred(*__next)) {
01697 swap(*__first, *__next);
01698 ++__first;
01699 }
01700
01701 return __first;
01702 }
01703
01704
01705
01706
01707
01708
01709 template<typename _BidirectionalIter, typename _Predicate>
01710 _BidirectionalIter
01711 __partition(_BidirectionalIter __first, _BidirectionalIter __last,
01712 _Predicate __pred,
01713 bidirectional_iterator_tag)
01714 {
01715 while (true) {
01716 while (true)
01717 if (__first == __last)
01718 return __first;
01719 else if (__pred(*__first))
01720 ++__first;
01721 else
01722 break;
01723 --__last;
01724 while (true)
01725 if (__first == __last)
01726 return __first;
01727 else if (!__pred(*__last))
01728 --__last;
01729 else
01730 break;
01731 iter_swap(__first, __last);
01732 ++__first;
01733 }
01734 }
01735
01736
01737
01738
01739
01740
01741
01742
01743
01744
01745
01746
01747
01748
01749
01750 template<typename _ForwardIter, typename _Predicate>
01751 inline _ForwardIter
01752 partition(_ForwardIter __first, _ForwardIter __last,
01753 _Predicate __pred)
01754 {
01755
01756 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01757 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01758 typename iterator_traits<_ForwardIter>::value_type>)
01759
01760 return __partition(__first, __last, __pred, __iterator_category(__first));
01761 }
01762
01763
01764
01765
01766
01767
01768
01769 template<typename _ForwardIter, typename _Predicate, typename _Distance>
01770 _ForwardIter
01771 __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last,
01772 _Predicate __pred, _Distance __len)
01773 {
01774 if (__len == 1)
01775 return __pred(*__first) ? __last : __first;
01776 _ForwardIter __middle = __first;
01777 advance(__middle, __len / 2);
01778 _ForwardIter __begin = __inplace_stable_partition(__first, __middle,
01779 __pred,
01780 __len / 2);
01781 _ForwardIter __end = __inplace_stable_partition(__middle, __last,
01782 __pred,
01783 __len - __len / 2);
01784 rotate(__begin, __middle, __end);
01785 advance(__begin, distance(__middle, __end));
01786 return __begin;
01787 }
01788
01789
01790
01791
01792
01793
01794 template<typename _ForwardIter, typename _Pointer, typename _Predicate,
01795 typename _Distance>
01796 _ForwardIter
01797 __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last,
01798 _Predicate __pred, _Distance __len,
01799 _Pointer __buffer,
01800 _Distance __buffer_size)
01801 {
01802 if (__len <= __buffer_size) {
01803 _ForwardIter __result1 = __first;
01804 _Pointer __result2 = __buffer;
01805 for ( ; __first != __last ; ++__first)
01806 if (__pred(*__first)) {
01807 *__result1 = *__first;
01808 ++__result1;
01809 }
01810 else {
01811 *__result2 = *__first;
01812 ++__result2;
01813 }
01814 copy(__buffer, __result2, __result1);
01815 return __result1;
01816 }
01817 else {
01818 _ForwardIter __middle = __first;
01819 advance(__middle, __len / 2);
01820 _ForwardIter __begin = __stable_partition_adaptive(__first, __middle,
01821 __pred,
01822 __len / 2,
01823 __buffer, __buffer_size);
01824 _ForwardIter __end = __stable_partition_adaptive( __middle, __last,
01825 __pred,
01826 __len - __len / 2,
01827 __buffer, __buffer_size);
01828 rotate(__begin, __middle, __end);
01829 advance(__begin, distance(__middle, __end));
01830 return __begin;
01831 }
01832 }
01833
01834
01835
01836
01837
01838
01839
01840
01841
01842
01843
01844
01845
01846
01847
01848
01849
01850 template<typename _ForwardIter, typename _Predicate>
01851 _ForwardIter
01852 stable_partition(_ForwardIter __first, _ForwardIter __last,
01853 _Predicate __pred)
01854 {
01855
01856 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01857 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01858 typename iterator_traits<_ForwardIter>::value_type>)
01859
01860 if (__first == __last)
01861 return __first;
01862 else
01863 {
01864 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
01865 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
01866
01867 _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last);
01868 if (__buf.size() > 0)
01869 return __stable_partition_adaptive(__first, __last, __pred,
01870 _DistanceType(__buf.requested_size()),
01871 __buf.begin(), __buf.size());
01872 else
01873 return __inplace_stable_partition(__first, __last, __pred,
01874 _DistanceType(__buf.requested_size()));
01875 }
01876 }
01877
01878
01879
01880
01881
01882
01883 template<typename _RandomAccessIter, typename _Tp>
01884 _RandomAccessIter
01885 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
01886 _Tp __pivot)
01887 {
01888 while (true) {
01889 while (*__first < __pivot)
01890 ++__first;
01891 --__last;
01892 while (__pivot < *__last)
01893 --__last;
01894 if (!(__first < __last))
01895 return __first;
01896 iter_swap(__first, __last);
01897 ++__first;
01898 }
01899 }
01900
01901
01902
01903
01904
01905
01906 template<typename _RandomAccessIter, typename _Tp, typename _Compare>
01907 _RandomAccessIter
01908 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
01909 _Tp __pivot, _Compare __comp)
01910 {
01911 while (true) {
01912 while (__comp(*__first, __pivot))
01913 ++__first;
01914 --__last;
01915 while (__comp(__pivot, *__last))
01916 --__last;
01917 if (!(__first < __last))
01918 return __first;
01919 iter_swap(__first, __last);
01920 ++__first;
01921 }
01922 }
01923
01924
01925
01926
01927
01928
01929
01930
01931 enum { _M_threshold = 16 };
01932
01933
01934
01935
01936
01937
01938 template<typename _RandomAccessIter, typename _Tp>
01939 void
01940 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
01941 {
01942 _RandomAccessIter __next = __last;
01943 --__next;
01944 while (__val < *__next) {
01945 *__last = *__next;
01946 __last = __next;
01947 --__next;
01948 }
01949 *__last = __val;
01950 }
01951
01952
01953
01954
01955
01956
01957 template<typename _RandomAccessIter, typename _Tp, typename _Compare>
01958 void
01959 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp)
01960 {
01961 _RandomAccessIter __next = __last;
01962 --__next;
01963 while (__comp(__val, *__next)) {
01964 *__last = *__next;
01965 __last = __next;
01966 --__next;
01967 }
01968 *__last = __val;
01969 }
01970
01971
01972
01973
01974
01975
01976 template<typename _RandomAccessIter>
01977 void
01978 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
01979 {
01980 if (__first == __last) return;
01981
01982 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01983 {
01984 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
01985 if (__val < *__first) {
01986 copy_backward(__first, __i, __i + 1);
01987 *__first = __val;
01988 }
01989 else
01990 __unguarded_linear_insert(__i, __val);
01991 }
01992 }
01993
01994
01995
01996
01997
01998
01999 template<typename _RandomAccessIter, typename _Compare>
02000 void
02001 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02002 _Compare __comp)
02003 {
02004 if (__first == __last) return;
02005
02006 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
02007 {
02008 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
02009 if (__comp(__val, *__first)) {
02010 copy_backward(__first, __i, __i + 1);
02011 *__first = __val;
02012 }
02013 else
02014 __unguarded_linear_insert(__i, __val, __comp);
02015 }
02016 }
02017
02018
02019
02020
02021
02022
02023 template<typename _RandomAccessIter>
02024 inline void
02025 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02026 {
02027 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02028
02029 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
02030 __unguarded_linear_insert(__i, _ValueType(*__i));
02031 }
02032
02033
02034
02035
02036
02037
02038 template<typename _RandomAccessIter, typename _Compare>
02039 inline void
02040 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02041 _Compare __comp)
02042 {
02043 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02044
02045 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
02046 __unguarded_linear_insert(__i, _ValueType(*__i), __comp);
02047 }
02048
02049
02050
02051
02052
02053
02054 template<typename _RandomAccessIter>
02055 void
02056 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02057 {
02058 if (__last - __first > _M_threshold) {
02059 __insertion_sort(__first, __first + _M_threshold);
02060 __unguarded_insertion_sort(__first + _M_threshold, __last);
02061 }
02062 else
02063 __insertion_sort(__first, __last);
02064 }
02065
02066
02067
02068
02069
02070
02071 template<typename _RandomAccessIter, typename _Compare>
02072 void
02073 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02074 _Compare __comp)
02075 {
02076 if (__last - __first > _M_threshold) {
02077 __insertion_sort(__first, __first + _M_threshold, __comp);
02078 __unguarded_insertion_sort(__first + _M_threshold, __last, __comp);
02079 }
02080 else
02081 __insertion_sort(__first, __last, __comp);
02082 }
02083
02084
02085
02086
02087
02088
02089 template<typename _Size>
02090 inline _Size
02091 __lg(_Size __n)
02092 {
02093 _Size __k;
02094 for (__k = 0; __n != 1; __n >>= 1) ++__k;
02095 return __k;
02096 }
02097
02098
02099
02100
02101
02102
02103 template<typename _RandomAccessIter, typename _Size>
02104 void
02105 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
02106 _Size __depth_limit)
02107 {
02108 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02109
02110 while (__last - __first > _M_threshold) {
02111 if (__depth_limit == 0) {
02112 partial_sort(__first, __last, __last);
02113 return;
02114 }
02115 --__depth_limit;
02116 _RandomAccessIter __cut =
02117 __unguarded_partition(__first, __last,
02118 _ValueType(__median(*__first,
02119 *(__first + (__last - __first)/2),
02120 *(__last - 1))));
02121 __introsort_loop(__cut, __last, __depth_limit);
02122 __last = __cut;
02123 }
02124 }
02125
02126
02127
02128
02129
02130
02131 template<typename _RandomAccessIter, typename _Size, typename _Compare>
02132 void
02133 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
02134 _Size __depth_limit, _Compare __comp)
02135 {
02136 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02137
02138 while (__last - __first > _M_threshold) {
02139 if (__depth_limit == 0) {
02140 partial_sort(__first, __last, __last, __comp);
02141 return;
02142 }
02143 --__depth_limit;
02144 _RandomAccessIter __cut =
02145 __unguarded_partition(__first, __last,
02146 _ValueType(__median(*__first,
02147 *(__first + (__last - __first)/2),
02148 *(__last - 1), __comp)),
02149 __comp);
02150 __introsort_loop(__cut, __last, __depth_limit, __comp);
02151 __last = __cut;
02152 }
02153 }
02154
02155
02156
02157
02158
02159
02160
02161
02162
02163
02164
02165
02166
02167
02168 template<typename _RandomAccessIter>
02169 inline void
02170 sort(_RandomAccessIter __first, _RandomAccessIter __last)
02171 {
02172 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02173
02174
02175 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02176 _RandomAccessIter>)
02177 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02178
02179 if (__first != __last) {
02180 __introsort_loop(__first, __last, __lg(__last - __first) * 2);
02181 __final_insertion_sort(__first, __last);
02182 }
02183 }
02184
02185
02186
02187
02188
02189
02190
02191
02192
02193
02194
02195
02196
02197
02198
02199 template<typename _RandomAccessIter, typename _Compare>
02200 inline void
02201 sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
02202 {
02203 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02204
02205
02206 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02207 _RandomAccessIter>)
02208 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
02209
02210 if (__first != __last) {
02211 __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp);
02212 __final_insertion_sort(__first, __last, __comp);
02213 }
02214 }
02215
02216
02217
02218
02219
02220
02221
02222 template<typename _RandomAccessIter>
02223 void
02224 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02225 {
02226 if (__last - __first < 15) {
02227 __insertion_sort(__first, __last);
02228 return;
02229 }
02230 _RandomAccessIter __middle = __first + (__last - __first) / 2;
02231 __inplace_stable_sort(__first, __middle);
02232 __inplace_stable_sort(__middle, __last);
02233 __merge_without_buffer(__first, __middle, __last,
02234 __middle - __first,
02235 __last - __middle);
02236 }
02237
02238
02239
02240
02241
02242
02243 template<typename _RandomAccessIter, typename _Compare>
02244 void
02245 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02246 _Compare __comp)
02247 {
02248 if (__last - __first < 15) {
02249 __insertion_sort(__first, __last, __comp);
02250 return;
02251 }
02252 _RandomAccessIter __middle = __first + (__last - __first) / 2;
02253 __inplace_stable_sort(__first, __middle, __comp);
02254 __inplace_stable_sort(__middle, __last, __comp);
02255 __merge_without_buffer(__first, __middle, __last,
02256 __middle - __first,
02257 __last - __middle,
02258 __comp);
02259 }
02260
02261 template<typename _RandomAccessIter1, typename _RandomAccessIter2,
02262 typename _Distance>
02263 void
02264 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
02265 _RandomAccessIter2 __result, _Distance __step_size)
02266 {
02267 _Distance __two_step = 2 * __step_size;
02268
02269 while (__last - __first >= __two_step) {
02270 __result = merge(__first, __first + __step_size,
02271 __first + __step_size, __first + __two_step,
02272 __result);
02273 __first += __two_step;
02274 }
02275
02276 __step_size = min(_Distance(__last - __first), __step_size);
02277 merge(__first, __first + __step_size, __first + __step_size, __last,
02278 __result);
02279 }
02280
02281 template<typename _RandomAccessIter1, typename _RandomAccessIter2,
02282 typename _Distance, typename _Compare>
02283 void
02284 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
02285 _RandomAccessIter2 __result, _Distance __step_size,
02286 _Compare __comp)
02287 {
02288 _Distance __two_step = 2 * __step_size;
02289
02290 while (__last - __first >= __two_step) {
02291 __result = merge(__first, __first + __step_size,
02292 __first + __step_size, __first + __two_step,
02293 __result,
02294 __comp);
02295 __first += __two_step;
02296 }
02297 __step_size = min(_Distance(__last - __first), __step_size);
02298
02299 merge(__first, __first + __step_size,
02300 __first + __step_size, __last,
02301 __result,
02302 __comp);
02303 }
02304
02305 enum { _M_chunk_size = 7 };
02306
02307 template<typename _RandomAccessIter, typename _Distance>
02308 void
02309 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02310 _Distance __chunk_size)
02311 {
02312 while (__last - __first >= __chunk_size) {
02313 __insertion_sort(__first, __first + __chunk_size);
02314 __first += __chunk_size;
02315 }
02316 __insertion_sort(__first, __last);
02317 }
02318
02319 template<typename _RandomAccessIter, typename _Distance, typename _Compare>
02320 void
02321 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02322 _Distance __chunk_size, _Compare __comp)
02323 {
02324 while (__last - __first >= __chunk_size) {
02325 __insertion_sort(__first, __first + __chunk_size, __comp);
02326 __first += __chunk_size;
02327 }
02328 __insertion_sort(__first, __last, __comp);
02329 }
02330
02331 template<typename _RandomAccessIter, typename _Pointer>
02332 void
02333 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
02334 _Pointer __buffer)
02335 {
02336 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
02337
02338 _Distance __len = __last - __first;
02339 _Pointer __buffer_last = __buffer + __len;
02340
02341 _Distance __step_size = _M_chunk_size;
02342 __chunk_insertion_sort(__first, __last, __step_size);
02343
02344 while (__step_size < __len) {
02345 __merge_sort_loop(__first, __last, __buffer, __step_size);
02346 __step_size *= 2;
02347 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
02348 __step_size *= 2;
02349 }
02350 }
02351
02352 template<typename _RandomAccessIter, typename _Pointer, typename _Compare>
02353 void
02354 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
02355 _Pointer __buffer, _Compare __comp)
02356 {
02357 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
02358
02359 _Distance __len = __last - __first;
02360 _Pointer __buffer_last = __buffer + __len;
02361
02362 _Distance __step_size = _M_chunk_size;
02363 __chunk_insertion_sort(__first, __last, __step_size, __comp);
02364
02365 while (__step_size < __len) {
02366 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
02367 __step_size *= 2;
02368 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
02369 __step_size *= 2;
02370 }
02371 }
02372
02373 template<typename _RandomAccessIter, typename _Pointer, typename _Distance>
02374 void
02375 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
02376 _Pointer __buffer, _Distance __buffer_size)
02377 {
02378 _Distance __len = (__last - __first + 1) / 2;
02379 _RandomAccessIter __middle = __first + __len;
02380 if (__len > __buffer_size) {
02381 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
02382 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
02383 }
02384 else {
02385 __merge_sort_with_buffer(__first, __middle, __buffer);
02386 __merge_sort_with_buffer(__middle, __last, __buffer);
02387 }
02388 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
02389 _Distance(__last - __middle), __buffer, __buffer_size);
02390 }
02391
02392 template<typename _RandomAccessIter, typename _Pointer, typename _Distance,
02393 typename _Compare>
02394 void
02395 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
02396 _Pointer __buffer, _Distance __buffer_size,
02397 _Compare __comp)
02398 {
02399 _Distance __len = (__last - __first + 1) / 2;
02400 _RandomAccessIter __middle = __first + __len;
02401 if (__len > __buffer_size) {
02402 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
02403 __comp);
02404 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
02405 __comp);
02406 }
02407 else {
02408 __merge_sort_with_buffer(__first, __middle, __buffer, __comp);
02409 __merge_sort_with_buffer(__middle, __last, __buffer, __comp);
02410 }
02411 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
02412 _Distance(__last - __middle), __buffer, __buffer_size,
02413 __comp);
02414 }
02415
02416
02417
02418
02419
02420
02421
02422
02423
02424
02425
02426
02427
02428
02429
02430
02431
02432 template<typename _RandomAccessIter>
02433 inline void
02434 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02435 {
02436 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02437 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02438
02439
02440 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02441 _RandomAccessIter>)
02442 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02443
02444 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
02445 if (buf.begin() == 0)
02446 __inplace_stable_sort(__first, __last);
02447 else
02448 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
02449 }
02450
02451
02452
02453
02454
02455
02456
02457
02458
02459
02460
02461
02462
02463
02464
02465
02466
02467
02468 template<typename _RandomAccessIter, typename _Compare>
02469 inline void
02470 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
02471 {
02472 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02473 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02474
02475
02476 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02477 _RandomAccessIter>)
02478 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02479 _ValueType, _ValueType>)
02480
02481 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
02482 if (buf.begin() == 0)
02483 __inplace_stable_sort(__first, __last, __comp);
02484 else
02485 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
02486 __comp);
02487 }
02488
02489
02490
02491
02492
02493
02494
02495
02496
02497
02498
02499
02500
02501
02502
02503
02504 template<typename _RandomAccessIter>
02505 void
02506 partial_sort(_RandomAccessIter __first,
02507 _RandomAccessIter __middle,
02508 _RandomAccessIter __last)
02509 {
02510 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02511
02512
02513 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02514 _RandomAccessIter>)
02515 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02516
02517 make_heap(__first, __middle);
02518 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
02519 if (*__i < *__first)
02520 __pop_heap(__first, __middle, __i, _ValueType(*__i));
02521 sort_heap(__first, __middle);
02522 }
02523
02524
02525
02526
02527
02528
02529
02530
02531
02532
02533
02534
02535
02536
02537
02538
02539
02540
02541
02542 template<typename _RandomAccessIter, typename _Compare>
02543 void
02544 partial_sort(_RandomAccessIter __first,
02545 _RandomAccessIter __middle,
02546 _RandomAccessIter __last,
02547 _Compare __comp)
02548 {
02549 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02550
02551
02552 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02553 _RandomAccessIter>)
02554 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02555 _ValueType, _ValueType>)
02556
02557 make_heap(__first, __middle, __comp);
02558 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
02559 if (__comp(*__i, *__first))
02560 __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
02561 sort_heap(__first, __middle, __comp);
02562 }
02563
02564
02565
02566
02567
02568
02569
02570
02571
02572
02573
02574
02575
02576
02577
02578
02579
02580
02581 template<typename _InputIter, typename _RandomAccessIter>
02582 _RandomAccessIter
02583 partial_sort_copy(_InputIter __first, _InputIter __last,
02584 _RandomAccessIter __result_first,
02585 _RandomAccessIter __result_last)
02586 {
02587 typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
02588 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
02589 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02590
02591
02592 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
02593 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
02594 __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>)
02595 __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>)
02596
02597 if (__result_first == __result_last) return __result_last;
02598 _RandomAccessIter __result_real_last = __result_first;
02599 while(__first != __last && __result_real_last != __result_last) {
02600 *__result_real_last = *__first;
02601 ++__result_real_last;
02602 ++__first;
02603 }
02604 make_heap(__result_first, __result_real_last);
02605 while (__first != __last) {
02606 if (*__first < *__result_first)
02607 __adjust_heap(__result_first, _DistanceType(0),
02608 _DistanceType(__result_real_last - __result_first),
02609 _InputValueType(*__first));
02610 ++__first;
02611 }
02612 sort_heap(__result_first, __result_real_last);
02613 return __result_real_last;
02614 }
02615
02616
02617
02618
02619
02620
02621
02622
02623
02624
02625
02626
02627
02628
02629
02630
02631
02632
02633
02634
02635 template<typename _InputIter, typename _RandomAccessIter, typename _Compare>
02636 _RandomAccessIter
02637 partial_sort_copy(_InputIter __first, _InputIter __last,
02638 _RandomAccessIter __result_first,
02639 _RandomAccessIter __result_last,
02640 _Compare __comp)
02641 {
02642 typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
02643 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
02644 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02645
02646
02647 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
02648 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
02649 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
02650 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02651 _OutputValueType, _OutputValueType>)
02652
02653 if (__result_first == __result_last) return __result_last;
02654 _RandomAccessIter __result_real_last = __result_first;
02655 while(__first != __last && __result_real_last != __result_last) {
02656 *__result_real_last = *__first;
02657 ++__result_real_last;
02658 ++__first;
02659 }
02660 make_heap(__result_first, __result_real_last, __comp);
02661 while (__first != __last) {
02662 if (__comp(*__first, *__result_first))
02663 __adjust_heap(__result_first, _DistanceType(0),
02664 _DistanceType(__result_real_last - __result_first),
02665 _InputValueType(*__first),
02666 __comp);
02667 ++__first;
02668 }
02669 sort_heap(__result_first, __result_real_last, __comp);
02670 return __result_real_last;
02671 }
02672
02673
02674
02675
02676
02677
02678
02679
02680
02681
02682
02683
02684
02685
02686
02687
02688 template<typename _RandomAccessIter>
02689 void
02690 nth_element(_RandomAccessIter __first,
02691 _RandomAccessIter __nth,
02692 _RandomAccessIter __last)
02693 {
02694 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02695
02696
02697 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
02698 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02699
02700 while (__last - __first > 3) {
02701 _RandomAccessIter __cut =
02702 __unguarded_partition(__first, __last,
02703 _ValueType(__median(*__first,
02704 *(__first + (__last - __first)/2),
02705 *(__last - 1))));
02706 if (__cut <= __nth)
02707 __first = __cut;
02708 else
02709 __last = __cut;
02710 }
02711 __insertion_sort(__first, __last);
02712 }
02713
02714
02715
02716
02717
02718
02719
02720
02721
02722
02723
02724
02725
02726
02727
02728
02729
02730 template<typename _RandomAccessIter, typename _Compare>
02731 void
02732 nth_element(_RandomAccessIter __first,
02733 _RandomAccessIter __nth,
02734 _RandomAccessIter __last,
02735 _Compare __comp)
02736 {
02737 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02738
02739
02740 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
02741 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02742 _ValueType, _ValueType>)
02743
02744 while (__last - __first > 3) {
02745 _RandomAccessIter __cut =
02746 __unguarded_partition(__first, __last,
02747 _ValueType(__median(*__first,
02748 *(__first + (__last - __first)/2),
02749 *(__last - 1),
02750 __comp)),
02751 __comp);
02752 if (__cut <= __nth)
02753 __first = __cut;
02754 else
02755 __last = __cut;
02756 }
02757 __insertion_sort(__first, __last, __comp);
02758 }
02759
02760
02761
02762
02763
02764
02765
02766
02767
02768
02769
02770 template<typename _ForwardIter, typename _Tp>
02771 _ForwardIter
02772 lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
02773 {
02774 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02775 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02776
02777
02778
02779
02780
02781
02782 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02783 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02784 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
02785
02786 _DistanceType __len = distance(__first, __last);
02787 _DistanceType __half;
02788 _ForwardIter __middle;
02789
02790 while (__len > 0) {
02791 __half = __len >> 1;
02792 __middle = __first;
02793 advance(__middle, __half);
02794 if (*__middle < __val) {
02795 __first = __middle;
02796 ++__first;
02797 __len = __len - __half - 1;
02798 }
02799 else
02800 __len = __half;
02801 }
02802 return __first;
02803 }
02804
02805
02806
02807
02808
02809
02810
02811
02812
02813
02814
02815
02816
02817
02818 template<typename _ForwardIter, typename _Tp, typename _Compare>
02819 _ForwardIter
02820 lower_bound(_ForwardIter __first, _ForwardIter __last,
02821 const _Tp& __val, _Compare __comp)
02822 {
02823 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02824 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02825
02826
02827 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02828 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
02829
02830 _DistanceType __len = distance(__first, __last);
02831 _DistanceType __half;
02832 _ForwardIter __middle;
02833
02834 while (__len > 0) {
02835 __half = __len >> 1;
02836 __middle = __first;
02837 advance(__middle, __half);
02838 if (__comp(*__middle, __val)) {
02839 __first = __middle;
02840 ++__first;
02841 __len = __len - __half - 1;
02842 }
02843 else
02844 __len = __half;
02845 }
02846 return __first;
02847 }
02848
02849
02850
02851
02852
02853
02854
02855
02856
02857
02858 template<typename _ForwardIter, typename _Tp>
02859 _ForwardIter
02860 upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
02861 {
02862 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02863 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02864
02865
02866
02867 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02868 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02869 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
02870
02871 _DistanceType __len = distance(__first, __last);
02872 _DistanceType __half;
02873 _ForwardIter __middle;
02874
02875 while (__len > 0) {
02876 __half = __len >> 1;
02877 __middle = __first;
02878 advance(__middle, __half);
02879 if (__val < *__middle)
02880 __len = __half;
02881 else {
02882 __first = __middle;
02883 ++__first;
02884 __len = __len - __half - 1;
02885 }
02886 }
02887 return __first;
02888 }
02889
02890
02891
02892
02893
02894
02895
02896
02897
02898
02899
02900
02901
02902
02903 template<typename _ForwardIter, typename _Tp, typename _Compare>
02904 _ForwardIter
02905 upper_bound(_ForwardIter __first, _ForwardIter __last,
02906 const _Tp& __val, _Compare __comp)
02907 {
02908 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02909 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02910
02911
02912 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02913 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
02914
02915 _DistanceType __len = distance(__first, __last);
02916 _DistanceType __half;
02917 _ForwardIter __middle;
02918
02919 while (__len > 0) {
02920 __half = __len >> 1;
02921 __middle = __first;
02922 advance(__middle, __half);
02923 if (__comp(__val, *__middle))
02924 __len = __half;
02925 else {
02926 __first = __middle;
02927 ++__first;
02928 __len = __len - __half - 1;
02929 }
02930 }
02931 return __first;
02932 }
02933
02934
02935
02936
02937
02938
02939
02940
02941
02942
02943
02944
02945
02946
02947
02948
02949
02950 template<typename _ForwardIter, typename _Tp>
02951 pair<_ForwardIter, _ForwardIter>
02952 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
02953 {
02954 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02955 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02956
02957
02958
02959 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02960 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02961 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
02962
02963 _DistanceType __len = distance(__first, __last);
02964 _DistanceType __half;
02965 _ForwardIter __middle, __left, __right;
02966
02967 while (__len > 0) {
02968 __half = __len >> 1;
02969 __middle = __first;
02970 advance(__middle, __half);
02971 if (*__middle < __val) {
02972 __first = __middle;
02973 ++__first;
02974 __len = __len - __half - 1;
02975 }
02976 else if (__val < *__middle)
02977 __len = __half;
02978 else {
02979 __left = lower_bound(__first, __middle, __val);
02980 advance(__first, __len);
02981 __right = upper_bound(++__middle, __first, __val);
02982 return pair<_ForwardIter, _ForwardIter>(__left, __right);
02983 }
02984 }
02985 return pair<_ForwardIter, _ForwardIter>(__first, __first);
02986 }
02987
02988
02989
02990
02991
02992
02993
02994
02995
02996
02997
02998
02999
03000
03001
03002
03003
03004
03005 template<typename _ForwardIter, typename _Tp, typename _Compare>
03006 pair<_ForwardIter, _ForwardIter>
03007 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
03008 _Compare __comp)
03009 {
03010 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
03011 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
03012
03013
03014 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03015 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
03016 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
03017
03018 _DistanceType __len = distance(__first, __last);
03019 _DistanceType __half;
03020 _ForwardIter __middle, __left, __right;
03021
03022 while (__len > 0) {
03023 __half = __len >> 1;
03024 __middle = __first;
03025 advance(__middle, __half);
03026 if (__comp(*__middle, __val)) {
03027 __first = __middle;
03028 ++__first;
03029 __len = __len - __half - 1;
03030 }
03031 else if (__comp(__val, *__middle))
03032 __len = __half;
03033 else {
03034 __left = lower_bound(__first, __middle, __val, __comp);
03035 advance(__first, __len);
03036 __right = upper_bound(++__middle, __first, __val, __comp);
03037 return pair<_ForwardIter, _ForwardIter>(__left, __right);
03038 }
03039 }
03040 return pair<_ForwardIter, _ForwardIter>(__first, __first);
03041 }
03042
03043
03044
03045
03046
03047
03048
03049
03050
03051
03052
03053
03054 template<typename _ForwardIter, typename _Tp>
03055 bool
03056 binary_search(_ForwardIter __first, _ForwardIter __last,
03057 const _Tp& __val)
03058 {
03059
03060
03061 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03062 __glibcpp_function_requires(_SameTypeConcept<_Tp,
03063 typename iterator_traits<_ForwardIter>::value_type>)
03064 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
03065
03066 _ForwardIter __i = lower_bound(__first, __last, __val);
03067 return __i != __last && !(__val < *__i);
03068 }
03069
03070
03071
03072
03073
03074
03075
03076
03077
03078
03079
03080
03081
03082
03083
03084
03085 template<typename _ForwardIter, typename _Tp, typename _Compare>
03086 bool
03087 binary_search(_ForwardIter __first, _ForwardIter __last,
03088 const _Tp& __val, _Compare __comp)
03089 {
03090
03091 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03092 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03093 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
03094 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
03095 typename iterator_traits<_ForwardIter>::value_type>)
03096
03097 _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
03098 return __i != __last && !__comp(__val, *__i);
03099 }
03100
03101
03102
03103
03104
03105
03106
03107
03108
03109
03110
03111
03112
03113
03114
03115
03116
03117 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
03118 _OutputIter
03119 merge(_InputIter1 __first1, _InputIter1 __last1,
03120 _InputIter2 __first2, _InputIter2 __last2,
03121 _OutputIter __result)
03122 {
03123
03124 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03125 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03126 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03127 typename iterator_traits<_InputIter1>::value_type>)
03128 __glibcpp_function_requires(_SameTypeConcept<
03129 typename iterator_traits<_InputIter1>::value_type,
03130 typename iterator_traits<_InputIter2>::value_type>)
03131 __glibcpp_function_requires(_LessThanComparableConcept<
03132 typename iterator_traits<_InputIter1>::value_type>)
03133
03134 while (__first1 != __last1 && __first2 != __last2) {
03135 if (*__first2 < *__first1) {
03136 *__result = *__first2;
03137 ++__first2;
03138 }
03139 else {
03140 *__result = *__first1;
03141 ++__first1;
03142 }
03143 ++__result;
03144 }
03145 return copy(__first2, __last2, copy(__first1, __last1, __result));
03146 }
03147
03148
03149
03150
03151
03152
03153
03154
03155
03156
03157
03158
03159
03160
03161
03162
03163
03164
03165
03166
03167
03168 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
03169 typename _Compare>
03170 _OutputIter
03171 merge(_InputIter1 __first1, _InputIter1 __last1,
03172 _InputIter2 __first2, _InputIter2 __last2,
03173 _OutputIter __result, _Compare __comp)
03174 {
03175
03176 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03177 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03178 __glibcpp_function_requires(_SameTypeConcept<
03179 typename iterator_traits<_InputIter1>::value_type,
03180 typename iterator_traits<_InputIter2>::value_type>)
03181 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03182 typename iterator_traits<_InputIter1>::value_type>)
03183 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03184 typename iterator_traits<_InputIter1>::value_type,
03185 typename iterator_traits<_InputIter2>::value_type>)
03186
03187 while (__first1 != __last1 && __first2 != __last2) {
03188 if (__comp(*__first2, *__first1)) {
03189 *__result = *__first2;
03190 ++__first2;
03191 }
03192 else {
03193 *__result = *__first1;
03194 ++__first1;
03195 }
03196 ++__result;
03197 }
03198 return copy(__first2, __last2, copy(__first1, __last1, __result));
03199 }
03200
03201
03202
03203
03204
03205
03206 template<typename _BidirectionalIter, typename _Distance>
03207 void
03208 __merge_without_buffer(_BidirectionalIter __first,
03209 _BidirectionalIter __middle,
03210 _BidirectionalIter __last,
03211 _Distance __len1, _Distance __len2)
03212 {
03213 if (__len1 == 0 || __len2 == 0)
03214 return;
03215 if (__len1 + __len2 == 2) {
03216 if (*__middle < *__first)
03217 iter_swap(__first, __middle);
03218 return;
03219 }
03220 _BidirectionalIter __first_cut = __first;
03221 _BidirectionalIter __second_cut = __middle;
03222 _Distance __len11 = 0;
03223 _Distance __len22 = 0;
03224 if (__len1 > __len2) {
03225 __len11 = __len1 / 2;
03226 advance(__first_cut, __len11);
03227 __second_cut = lower_bound(__middle, __last, *__first_cut);
03228 __len22 = distance(__middle, __second_cut);
03229 }
03230 else {
03231 __len22 = __len2 / 2;
03232 advance(__second_cut, __len22);
03233 __first_cut = upper_bound(__first, __middle, *__second_cut);
03234 __len11 = distance(__first, __first_cut);
03235 }
03236 rotate(__first_cut, __middle, __second_cut);
03237 _BidirectionalIter __new_middle = __first_cut;
03238 advance(__new_middle, distance(__middle, __second_cut));
03239 __merge_without_buffer(__first, __first_cut, __new_middle,
03240 __len11, __len22);
03241 __merge_without_buffer(__new_middle, __second_cut, __last,
03242 __len1 - __len11, __len2 - __len22);
03243 }
03244
03245
03246
03247
03248
03249
03250 template<typename _BidirectionalIter, typename _Distance, typename _Compare>
03251 void
03252 __merge_without_buffer(_BidirectionalIter __first,
03253 _BidirectionalIter __middle,
03254 _BidirectionalIter __last,
03255 _Distance __len1, _Distance __len2,
03256 _Compare __comp)
03257 {
03258 if (__len1 == 0 || __len2 == 0)
03259 return;
03260 if (__len1 + __len2 == 2) {
03261 if (__comp(*__middle, *__first))
03262 iter_swap(__first, __middle);
03263 return;
03264 }
03265 _BidirectionalIter __first_cut = __first;
03266 _BidirectionalIter __second_cut = __middle;
03267 _Distance __len11 = 0;
03268 _Distance __len22 = 0;
03269 if (__len1 > __len2) {
03270 __len11 = __len1 / 2;
03271 advance(__first_cut, __len11);
03272 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
03273 __len22 = distance(__middle, __second_cut);
03274 }
03275 else {
03276 __len22 = __len2 / 2;
03277 advance(__second_cut, __len22);
03278 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
03279 __len11 = distance(__first, __first_cut);
03280 }
03281 rotate(__first_cut, __middle, __second_cut);
03282 _BidirectionalIter __new_middle = __first_cut;
03283 advance(__new_middle, distance(__middle, __second_cut));
03284 __merge_without_buffer(__first, __first_cut, __new_middle,
03285 __len11, __len22, __comp);
03286 __merge_without_buffer(__new_middle, __second_cut, __last,
03287 __len1 - __len11, __len2 - __len22, __comp);
03288 }
03289
03290
03291
03292
03293
03294
03295 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
03296 typename _Distance>
03297 _BidirectionalIter1
03298 __rotate_adaptive(_BidirectionalIter1 __first,
03299 _BidirectionalIter1 __middle,
03300 _BidirectionalIter1 __last,
03301 _Distance __len1, _Distance __len2,
03302 _BidirectionalIter2 __buffer,
03303 _Distance __buffer_size)
03304 {
03305 _BidirectionalIter2 __buffer_end;
03306 if (__len1 > __len2 && __len2 <= __buffer_size) {
03307 __buffer_end = copy(__middle, __last, __buffer);
03308 copy_backward(__first, __middle, __last);
03309 return copy(__buffer, __buffer_end, __first);
03310 }
03311 else if (__len1 <= __buffer_size) {
03312 __buffer_end = copy(__first, __middle, __buffer);
03313 copy(__middle, __last, __first);
03314 return copy_backward(__buffer, __buffer_end, __last);
03315 }
03316 else {
03317 rotate(__first, __middle, __last);
03318 advance(__first, distance(__middle, __last));
03319 return __first;
03320 }
03321 }
03322
03323
03324
03325
03326
03327
03328 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
03329 typename _BidirectionalIter3>
03330 _BidirectionalIter3
03331 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
03332 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
03333 _BidirectionalIter3 __result)
03334 {
03335 if (__first1 == __last1)
03336 return copy_backward(__first2, __last2, __result);
03337 if (__first2 == __last2)
03338 return copy_backward(__first1, __last1, __result);
03339 --__last1;
03340 --__last2;
03341 while (true) {
03342 if (*__last2 < *__last1) {
03343 *--__result = *__last1;
03344 if (__first1 == __last1)
03345 return copy_backward(__first2, ++__last2, __result);
03346 --__last1;
03347 }
03348 else {
03349 *--__result = *__last2;
03350 if (__first2 == __last2)
03351 return copy_backward(__first1, ++__last1, __result);
03352 --__last2;
03353 }
03354 }
03355 }
03356
03357
03358
03359
03360
03361
03362 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
03363 typename _BidirectionalIter3, typename _Compare>
03364 _BidirectionalIter3
03365 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
03366 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
03367 _BidirectionalIter3 __result,
03368 _Compare __comp)
03369 {
03370 if (__first1 == __last1)
03371 return copy_backward(__first2, __last2, __result);
03372 if (__first2 == __last2)
03373 return copy_backward(__first1, __last1, __result);
03374 --__last1;
03375 --__last2;
03376 while (true) {
03377 if (__comp(*__last2, *__last1)) {
03378 *--__result = *__last1;
03379 if (__first1 == __last1)
03380 return copy_backward(__first2, ++__last2, __result);
03381 --__last1;
03382 }
03383 else {
03384 *--__result = *__last2;
03385 if (__first2 == __last2)
03386 return copy_backward(__first1, ++__last1, __result);
03387 --__last2;
03388 }
03389 }
03390 }
03391
03392
03393
03394
03395
03396
03397 template<typename _BidirectionalIter, typename _Distance, typename _Pointer>
03398 void
03399 __merge_adaptive(_BidirectionalIter __first,
03400 _BidirectionalIter __middle,
03401 _BidirectionalIter __last,
03402 _Distance __len1, _Distance __len2,
03403 _Pointer __buffer, _Distance __buffer_size)
03404 {
03405 if (__len1 <= __len2 && __len1 <= __buffer_size) {
03406 _Pointer __buffer_end = copy(__first, __middle, __buffer);
03407 merge(__buffer, __buffer_end, __middle, __last, __first);
03408 }
03409 else if (__len2 <= __buffer_size) {
03410 _Pointer __buffer_end = copy(__middle, __last, __buffer);
03411 __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
03412 }
03413 else {
03414 _BidirectionalIter __first_cut = __first;
03415 _BidirectionalIter __second_cut = __middle;
03416 _Distance __len11 = 0;
03417 _Distance __len22 = 0;
03418 if (__len1 > __len2) {
03419 __len11 = __len1 / 2;
03420 advance(__first_cut, __len11);
03421 __second_cut = lower_bound(__middle, __last, *__first_cut);
03422 __len22 = distance(__middle, __second_cut);
03423 }
03424 else {
03425 __len22 = __len2 / 2;
03426 advance(__second_cut, __len22);
03427 __first_cut = upper_bound(__first, __middle, *__second_cut);
03428 __len11 = distance(__first, __first_cut);
03429 }
03430 _BidirectionalIter __new_middle =
03431 __rotate_adaptive(__first_cut, __middle, __second_cut,
03432 __len1 - __len11, __len22, __buffer,
03433 __buffer_size);
03434 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
03435 __len22, __buffer, __buffer_size);
03436 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
03437 __len2 - __len22, __buffer, __buffer_size);
03438 }
03439 }
03440
03441
03442
03443
03444
03445
03446 template<typename _BidirectionalIter, typename _Distance, typename _Pointer,
03447 typename _Compare>
03448 void
03449 __merge_adaptive(_BidirectionalIter __first,
03450 _BidirectionalIter __middle,
03451 _BidirectionalIter __last,
03452 _Distance __len1, _Distance __len2,
03453 _Pointer __buffer, _Distance __buffer_size,
03454 _Compare __comp)
03455 {
03456 if (__len1 <= __len2 && __len1 <= __buffer_size) {
03457 _Pointer __buffer_end = copy(__first, __middle, __buffer);
03458 merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
03459 }
03460 else if (__len2 <= __buffer_size) {
03461 _Pointer __buffer_end = copy(__middle, __last, __buffer);
03462 __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
03463 __comp);
03464 }
03465 else {
03466 _BidirectionalIter __first_cut = __first;
03467 _BidirectionalIter __second_cut = __middle;
03468 _Distance __len11 = 0;
03469 _Distance __len22 = 0;
03470 if (__len1 > __len2) {
03471 __len11 = __len1 / 2;
03472 advance(__first_cut, __len11);
03473 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
03474 __len22 = distance(__middle, __second_cut);
03475 }
03476 else {
03477 __len22 = __len2 / 2;
03478 advance(__second_cut, __len22);
03479 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
03480 __len11 = distance(__first, __first_cut);
03481 }
03482 _BidirectionalIter __new_middle =
03483 __rotate_adaptive(__first_cut, __middle, __second_cut,
03484 __len1 - __len11, __len22, __buffer,
03485 __buffer_size);
03486 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
03487 __len22, __buffer, __buffer_size, __comp);
03488 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
03489 __len2 - __len22, __buffer, __buffer_size, __comp);
03490 }
03491 }
03492
03493
03494
03495
03496
03497
03498
03499
03500
03501
03502
03503
03504
03505
03506
03507
03508
03509
03510 template<typename _BidirectionalIter>
03511 void
03512 inplace_merge(_BidirectionalIter __first,
03513 _BidirectionalIter __middle,
03514 _BidirectionalIter __last)
03515 {
03516 typedef typename iterator_traits<_BidirectionalIter>::value_type
03517 _ValueType;
03518 typedef typename iterator_traits<_BidirectionalIter>::difference_type
03519 _DistanceType;
03520
03521
03522 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
03523 _BidirectionalIter>)
03524 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
03525
03526 if (__first == __middle || __middle == __last)
03527 return;
03528
03529 _DistanceType __len1 = distance(__first, __middle);
03530 _DistanceType __len2 = distance(__middle, __last);
03531
03532 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
03533 if (__buf.begin() == 0)
03534 __merge_without_buffer(__first, __middle, __last, __len1, __len2);
03535 else
03536 __merge_adaptive(__first, __middle, __last, __len1, __len2,
03537 __buf.begin(), _DistanceType(__buf.size()));
03538 }
03539
03540
03541
03542
03543
03544
03545
03546
03547
03548
03549
03550
03551
03552
03553
03554
03555
03556
03557
03558
03559
03560
03561 template<typename _BidirectionalIter, typename _Compare>
03562 void
03563 inplace_merge(_BidirectionalIter __first,
03564 _BidirectionalIter __middle,
03565 _BidirectionalIter __last,
03566 _Compare __comp)
03567 {
03568 typedef typename iterator_traits<_BidirectionalIter>::value_type
03569 _ValueType;
03570 typedef typename iterator_traits<_BidirectionalIter>::difference_type
03571 _DistanceType;
03572
03573
03574 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
03575 _BidirectionalIter>)
03576 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03577 _ValueType, _ValueType>)
03578
03579 if (__first == __middle || __middle == __last)
03580 return;
03581
03582 _DistanceType __len1 = distance(__first, __middle);
03583 _DistanceType __len2 = distance(__middle, __last);
03584
03585 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
03586 if (__buf.begin() == 0)
03587 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
03588 else
03589 __merge_adaptive(__first, __middle, __last, __len1, __len2,
03590 __buf.begin(), _DistanceType(__buf.size()),
03591 __comp);
03592 }
03593
03594
03595
03596
03597
03598
03599 template<typename _InputIter1, typename _InputIter2>
03600 bool
03601 includes(_InputIter1 __first1, _InputIter1 __last1,
03602 _InputIter2 __first2, _InputIter2 __last2)
03603 {
03604
03605 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03606 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03607 __glibcpp_function_requires(_SameTypeConcept<
03608 typename iterator_traits<_InputIter1>::value_type,
03609 typename iterator_traits<_InputIter2>::value_type>)
03610 __glibcpp_function_requires(_LessThanComparableConcept<
03611 typename iterator_traits<_InputIter1>::value_type>)
03612
03613 while (__first1 != __last1 && __first2 != __last2)
03614 if (*__first2 < *__first1)
03615 return false;
03616 else if(*__first1 < *__first2)
03617 ++__first1;
03618 else
03619 ++__first1, ++__first2;
03620
03621 return __first2 == __last2;
03622 }
03623
03624 template<typename _InputIter1, typename _InputIter2, typename _Compare>
03625 bool
03626 includes(_InputIter1 __first1, _InputIter1 __last1,
03627 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
03628 {
03629
03630 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03631 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03632 __glibcpp_function_requires(_SameTypeConcept<
03633 typename iterator_traits<_InputIter1>::value_type,
03634 typename iterator_traits<_InputIter2>::value_type>)
03635 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03636 typename iterator_traits<_InputIter1>::value_type,
03637 typename iterator_traits<_InputIter2>::value_type>)
03638
03639 while (__first1 != __last1 && __first2 != __last2)
03640 if (__comp(*__first2, *__first1))
03641 return false;
03642 else if(__comp(*__first1, *__first2))
03643 ++__first1;
03644 else
03645 ++__first1, ++__first2;
03646
03647 return __first2 == __last2;
03648 }
03649
03650 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
03651 _OutputIter
03652 set_union(_InputIter1 __first1, _InputIter1 __last1,
03653 _InputIter2 __first2, _InputIter2 __last2,
03654 _OutputIter __result)
03655 {
03656
03657 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03658 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03659 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03660 typename iterator_traits<_InputIter1>::value_type>)
03661 __glibcpp_function_requires(_SameTypeConcept<
03662 typename iterator_traits<_InputIter1>::value_type,
03663 typename iterator_traits<_InputIter2>::value_type>)
03664 __glibcpp_function_requires(_LessThanComparableConcept<
03665 typename iterator_traits<_InputIter1>::value_type>)
03666
03667 while (__first1 != __last1 && __first2 != __last2) {
03668 if (*__first1 < *__first2) {
03669 *__result = *__first1;
03670 ++__first1;
03671 }
03672 else if (*__first2 < *__first1) {
03673 *__result = *__first2;
03674 ++__first2;
03675 }
03676 else {
03677 *__result = *__first1;
03678 ++__first1;
03679 ++__first2;
03680 }
03681 ++__result;
03682 }
03683 return copy(__first2, __last2, copy(__first1, __last1, __result));
03684 }
03685
03686 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
03687 typename _Compare>
03688 _OutputIter
03689 set_union(_InputIter1 __first1, _InputIter1 __last1,
03690 _InputIter2 __first2, _InputIter2 __last2,
03691 _OutputIter __result, _Compare __comp)
03692 {
03693
03694 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03695 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03696 __glibcpp_function_requires(_SameTypeConcept<
03697 typename iterator_traits<_InputIter1>::value_type,
03698 typename iterator_traits<_InputIter2>::value_type>)
03699 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03700 typename iterator_traits<_InputIter1>::value_type>)
03701 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03702 typename iterator_traits<_InputIter1>::value_type,
03703 typename iterator_traits<_InputIter2>::value_type>)
03704
03705 while (__first1 != __last1 && __first2 != __last2) {
03706 if (__comp(*__first1, *__first2)) {
03707 *__result = *__first1;
03708 ++__first1;
03709 }
03710 else if (__comp(*__first2, *__first1)) {
03711 *__result = *__first2;
03712 ++__first2;
03713 }
03714 else {
03715 *__result = *__first1;
03716 ++__first1;
03717 ++__first2;
03718 }
03719 ++__result;
03720 }
03721 return copy(__first2, __last2, copy(__first1, __last1, __result));
03722 }
03723
03724 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
03725 _OutputIter
03726 set_intersection(_InputIter1 __first1, _InputIter1 __last1,
03727 _InputIter2 __first2, _InputIter2 __last2,
03728 _OutputIter __result)
03729 {
03730
03731 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03732 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03733 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03734 typename iterator_traits<_InputIter1>::value_type>)
03735 __glibcpp_function_requires(_SameTypeConcept<
03736 typename iterator_traits<_InputIter1>::value_type,
03737 typename iterator_traits<_InputIter2>::value_type>)
03738 __glibcpp_function_requires(_LessThanComparableConcept<
03739 typename iterator_traits<_InputIter1>::value_type>)
03740
03741 while (__first1 != __last1 && __first2 != __last2)
03742 if (*__first1 < *__first2)
03743 ++__first1;
03744 else if (*__first2 < *__first1)
03745 ++__first2;
03746 else {
03747 *__result = *__first1;
03748 ++__first1;
03749 ++__first2;
03750 ++__result;
03751 }
03752 return __result;
03753 }
03754
03755 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
03756 typename _Compare>
03757 _OutputIter
03758 set_intersection(_InputIter1 __first1, _InputIter1 __last1,
03759 _InputIter2 __first2, _InputIter2 __last2,
03760 _OutputIter __result, _Compare __comp)
03761 {
03762
03763 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03764 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03765 __glibcpp_function_requires(_SameTypeConcept<
03766 typename iterator_traits<_InputIter1>::value_type,
03767 typename iterator_traits<_InputIter2>::value_type>)
03768 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03769 typename iterator_traits<_InputIter1>::value_type>)
03770 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03771 typename iterator_traits<_InputIter1>::value_type,
03772 typename iterator_traits<_InputIter2>::value_type>)
03773
03774 while (__first1 != __last1 && __first2 != __last2)
03775 if (__comp(*__first1, *__first2))
03776 ++__first1;
03777 else if (__comp(*__first2, *__first1))
03778 ++__first2;
03779 else {
03780 *__result = *__first1;
03781 ++__first1;
03782 ++__first2;
03783 ++__result;
03784 }
03785 return __result;
03786 }
03787
03788 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
03789 _OutputIter
03790 set_difference(_InputIter1 __first1, _InputIter1 __last1,
03791 _InputIter2 __first2, _InputIter2 __last2,
03792 _OutputIter __result)
03793 {
03794
03795 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03796 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03797 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03798 typename iterator_traits<_InputIter1>::value_type>)
03799 __glibcpp_function_requires(_SameTypeConcept<
03800 typename iterator_traits<_InputIter1>::value_type,
03801 typename iterator_traits<_InputIter2>::value_type>)
03802 __glibcpp_function_requires(_LessThanComparableConcept<
03803 typename iterator_traits<_InputIter1>::value_type>)
03804
03805 while (__first1 != __last1 && __first2 != __last2)
03806 if (*__first1 < *__first2) {
03807 *__result = *__first1;
03808 ++__first1;
03809 ++__result;
03810 }
03811 else if (*__first2 < *__first1)
03812 ++__first2;
03813 else {
03814 ++__first1;
03815 ++__first2;
03816 }
03817 return copy(__first1, __last1, __result);
03818 }
03819
03820 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
03821 typename _Compare>
03822 _OutputIter
03823 set_difference(_InputIter1 __first1, _InputIter1 __last1,
03824 _InputIter2 __first2, _InputIter2 __last2,
03825 _OutputIter __result, _Compare __comp)
03826 {
03827
03828 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03829 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03830 __glibcpp_function_requires(_SameTypeConcept<
03831 typename iterator_traits<_InputIter1>::value_type,
03832 typename iterator_traits<_InputIter2>::value_type>)
03833 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03834 typename iterator_traits<_InputIter1>::value_type>)
03835 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03836 typename iterator_traits<_InputIter1>::value_type,
03837 typename iterator_traits<_InputIter2>::value_type>)
03838
03839 while (__first1 != __last1 && __first2 != __last2)
03840 if (__comp(*__first1, *__first2)) {
03841 *__result = *__first1;
03842 ++__first1;
03843 ++__result;
03844 }
03845 else if (__comp(*__first2, *__first1))
03846 ++__first2;
03847 else {
03848 ++__first1;
03849 ++__first2;
03850 }
03851 return copy(__first1, __last1, __result);
03852 }
03853
03854 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
03855 _OutputIter
03856 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
03857 _InputIter2 __first2, _InputIter2 __last2,
03858 _OutputIter __result)
03859 {
03860
03861 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03862 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03863 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03864 typename iterator_traits<_InputIter1>::value_type>)
03865 __glibcpp_function_requires(_SameTypeConcept<
03866 typename iterator_traits<_InputIter1>::value_type,
03867 typename iterator_traits<_InputIter2>::value_type>)
03868 __glibcpp_function_requires(_LessThanComparableConcept<
03869 typename iterator_traits<_InputIter1>::value_type>)
03870
03871 while (__first1 != __last1 && __first2 != __last2)
03872 if (*__first1 < *__first2) {
03873 *__result = *__first1;
03874 ++__first1;
03875 ++__result;
03876 }
03877 else if (*__first2 < *__first1) {
03878 *__result = *__first2;
03879 ++__first2;
03880 ++__result;
03881 }
03882 else {
03883 ++__first1;
03884 ++__first2;
03885 }
03886 return copy(__first2, __last2, copy(__first1, __last1, __result));
03887 }
03888
03889 template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
03890 typename _Compare>
03891 _OutputIter
03892 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
03893 _InputIter2 __first2, _InputIter2 __last2,
03894 _OutputIter __result,
03895 _Compare __comp)
03896 {
03897
03898 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03899 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03900 __glibcpp_function_requires(_SameTypeConcept<
03901 typename iterator_traits<_InputIter1>::value_type,
03902 typename iterator_traits<_InputIter2>::value_type>)
03903 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03904 typename iterator_traits<_InputIter1>::value_type>)
03905 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03906 typename iterator_traits<_InputIter1>::value_type,
03907 typename iterator_traits<_InputIter2>::value_type>)
03908
03909 while (__first1 != __last1 && __first2 != __last2)
03910 if (__comp(*__first1, *__first2)) {
03911 *__result = *__first1;
03912 ++__first1;
03913 ++__result;
03914 }
03915 else if (__comp(*__first2, *__first1)) {
03916 *__result = *__first2;
03917 ++__first2;
03918 ++__result;
03919 }
03920 else {
03921 ++__first1;
03922 ++__first2;
03923 }
03924 return copy(__first2, __last2, copy(__first1, __last1, __result));
03925 }
03926
03927
03928
03929
03930 template<typename _ForwardIter>
03931 _ForwardIter
03932 max_element(_ForwardIter __first, _ForwardIter __last)
03933 {
03934
03935 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03936 __glibcpp_function_requires(_LessThanComparableConcept<
03937 typename iterator_traits<_ForwardIter>::value_type>)
03938
03939 if (__first == __last) return __first;
03940 _ForwardIter __result = __first;
03941 while (++__first != __last)
03942 if (*__result < *__first)
03943 __result = __first;
03944 return __result;
03945 }
03946
03947 template<typename _ForwardIter, typename _Compare>
03948 _ForwardIter
03949 max_element(_ForwardIter __first, _ForwardIter __last,
03950 _Compare __comp)
03951 {
03952
03953 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03954 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03955 typename iterator_traits<_ForwardIter>::value_type,
03956 typename iterator_traits<_ForwardIter>::value_type>)
03957
03958 if (__first == __last) return __first;
03959 _ForwardIter __result = __first;
03960 while (++__first != __last)
03961 if (__comp(*__result, *__first)) __result = __first;
03962 return __result;
03963 }
03964
03965 template<typename _ForwardIter>
03966 _ForwardIter
03967 min_element(_ForwardIter __first, _ForwardIter __last)
03968 {
03969
03970 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03971 __glibcpp_function_requires(_LessThanComparableConcept<
03972 typename iterator_traits<_ForwardIter>::value_type>)
03973
03974 if (__first == __last) return __first;
03975 _ForwardIter __result = __first;
03976 while (++__first != __last)
03977 if (*__first < *__result)
03978 __result = __first;
03979 return __result;
03980 }
03981
03982 template<typename _ForwardIter, typename _Compare>
03983 _ForwardIter
03984 min_element(_ForwardIter __first, _ForwardIter __last,
03985 _Compare __comp)
03986 {
03987
03988 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03989 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03990 typename iterator_traits<_ForwardIter>::value_type,
03991 typename iterator_traits<_ForwardIter>::value_type>)
03992
03993 if (__first == __last) return __first;
03994 _ForwardIter __result = __first;
03995 while (++__first != __last)
03996 if (__comp(*__first, *__result))
03997 __result = __first;
03998 return __result;
03999 }
04000
04001
04002
04003
04004 template<typename _BidirectionalIter>
04005 bool
04006 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
04007 {
04008
04009 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04010 __glibcpp_function_requires(_LessThanComparableConcept<
04011 typename iterator_traits<_BidirectionalIter>::value_type>)
04012
04013 if (__first == __last)
04014 return false;
04015 _BidirectionalIter __i = __first;
04016 ++__i;
04017 if (__i == __last)
04018 return false;
04019 __i = __last;
04020 --__i;
04021
04022 for(;;) {
04023 _BidirectionalIter __ii = __i;
04024 --__i;
04025 if (*__i < *__ii) {
04026 _BidirectionalIter __j = __last;
04027 while (!(*__i < *--__j))
04028 {}
04029 iter_swap(__i, __j);
04030 reverse(__ii, __last);
04031 return true;
04032 }
04033 if (__i == __first) {
04034 reverse(__first, __last);
04035 return false;
04036 }
04037 }
04038 }
04039
04040 template<typename _BidirectionalIter, typename _Compare>
04041 bool
04042 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
04043 _Compare __comp)
04044 {
04045
04046 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04047 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
04048 typename iterator_traits<_BidirectionalIter>::value_type,
04049 typename iterator_traits<_BidirectionalIter>::value_type>)
04050
04051 if (__first == __last)
04052 return false;
04053 _BidirectionalIter __i = __first;
04054 ++__i;
04055 if (__i == __last)
04056 return false;
04057 __i = __last;
04058 --__i;
04059
04060 for(;;) {
04061 _BidirectionalIter __ii = __i;
04062 --__i;
04063 if (__comp(*__i, *__ii)) {
04064 _BidirectionalIter __j = __last;
04065 while (!__comp(*__i, *--__j))
04066 {}
04067 iter_swap(__i, __j);
04068 reverse(__ii, __last);
04069 return true;
04070 }
04071 if (__i == __first) {
04072 reverse(__first, __last);
04073 return false;
04074 }
04075 }
04076 }
04077
04078 template<typename _BidirectionalIter>
04079 bool
04080 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
04081 {
04082
04083 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04084 __glibcpp_function_requires(_LessThanComparableConcept<
04085 typename iterator_traits<_BidirectionalIter>::value_type>)
04086
04087 if (__first == __last)
04088 return false;
04089 _BidirectionalIter __i = __first;
04090 ++__i;
04091 if (__i == __last)
04092 return false;
04093 __i = __last;
04094 --__i;
04095
04096 for(;;) {
04097 _BidirectionalIter __ii = __i;
04098 --__i;
04099 if (*__ii < *__i) {
04100 _BidirectionalIter __j = __last;
04101 while (!(*--__j < *__i))
04102 {}
04103 iter_swap(__i, __j);
04104 reverse(__ii, __last);
04105 return true;
04106 }
04107 if (__i == __first) {
04108 reverse(__first, __last);
04109 return false;
04110 }
04111 }
04112 }
04113
04114 template<typename _BidirectionalIter, typename _Compare>
04115 bool
04116 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
04117 _Compare __comp)
04118 {
04119
04120 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04121 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
04122 typename iterator_traits<_BidirectionalIter>::value_type,
04123 typename iterator_traits<_BidirectionalIter>::value_type>)
04124
04125 if (__first == __last)
04126 return false;
04127 _BidirectionalIter __i = __first;
04128 ++__i;
04129 if (__i == __last)
04130 return false;
04131 __i = __last;
04132 --__i;
04133
04134 for(;;) {
04135 _BidirectionalIter __ii = __i;
04136 --__i;
04137 if (__comp(*__ii, *__i)) {
04138 _BidirectionalIter __j = __last;
04139 while (!__comp(*--__j, *__i))
04140 {}
04141 iter_swap(__i, __j);
04142 reverse(__ii, __last);
04143 return true;
04144 }
04145 if (__i == __first) {
04146 reverse(__first, __last);
04147 return false;
04148 }
04149 }
04150 }
04151
04152
04153
04154 template<typename _InputIter, typename _ForwardIter>
04155 _InputIter
04156 find_first_of(_InputIter __first1, _InputIter __last1,
04157 _ForwardIter __first2, _ForwardIter __last2)
04158 {
04159
04160 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
04161 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
04162 __glibcpp_function_requires(_EqualOpConcept<
04163 typename iterator_traits<_InputIter>::value_type,
04164 typename iterator_traits<_ForwardIter>::value_type>)
04165
04166 for ( ; __first1 != __last1; ++__first1)
04167 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
04168 if (*__first1 == *__iter)
04169 return __first1;
04170 return __last1;
04171 }
04172
04173 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
04174 _InputIter
04175 find_first_of(_InputIter __first1, _InputIter __last1,
04176 _ForwardIter __first2, _ForwardIter __last2,
04177 _BinaryPredicate __comp)
04178 {
04179
04180 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
04181 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
04182 __glibcpp_function_requires(_EqualOpConcept<
04183 typename iterator_traits<_InputIter>::value_type,
04184 typename iterator_traits<_ForwardIter>::value_type>)
04185 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04186 typename iterator_traits<_InputIter>::value_type,
04187 typename iterator_traits<_ForwardIter>::value_type>)
04188
04189 for ( ; __first1 != __last1; ++__first1)
04190 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
04191 if (__comp(*__first1, *__iter))
04192 return __first1;
04193 return __last1;
04194 }
04195
04196
04197
04198
04199
04200
04201
04202
04203 template<typename _ForwardIter1, typename _ForwardIter2>
04204 _ForwardIter1
04205 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04206 _ForwardIter2 __first2, _ForwardIter2 __last2,
04207 forward_iterator_tag, forward_iterator_tag)
04208 {
04209 if (__first2 == __last2)
04210 return __last1;
04211 else {
04212 _ForwardIter1 __result = __last1;
04213 while (1) {
04214 _ForwardIter1 __new_result
04215 = search(__first1, __last1, __first2, __last2);
04216 if (__new_result == __last1)
04217 return __result;
04218 else {
04219 __result = __new_result;
04220 __first1 = __new_result;
04221 ++__first1;
04222 }
04223 }
04224 }
04225 }
04226
04227 template<typename _ForwardIter1, typename _ForwardIter2,
04228 typename _BinaryPredicate>
04229 _ForwardIter1
04230 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04231 _ForwardIter2 __first2, _ForwardIter2 __last2,
04232 forward_iterator_tag, forward_iterator_tag,
04233 _BinaryPredicate __comp)
04234 {
04235 if (__first2 == __last2)
04236 return __last1;
04237 else {
04238 _ForwardIter1 __result = __last1;
04239 while (1) {
04240 _ForwardIter1 __new_result
04241 = search(__first1, __last1, __first2, __last2, __comp);
04242 if (__new_result == __last1)
04243 return __result;
04244 else {
04245 __result = __new_result;
04246 __first1 = __new_result;
04247 ++__first1;
04248 }
04249 }
04250 }
04251 }
04252
04253
04254 template<typename _BidirectionalIter1, typename _BidirectionalIter2>
04255 _BidirectionalIter1
04256 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
04257 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
04258 bidirectional_iterator_tag, bidirectional_iterator_tag)
04259 {
04260
04261 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
04262 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
04263
04264 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
04265 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
04266
04267 _RevIter1 __rlast1(__first1);
04268 _RevIter2 __rlast2(__first2);
04269 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
04270 _RevIter2(__last2), __rlast2);
04271
04272 if (__rresult == __rlast1)
04273 return __last1;
04274 else {
04275 _BidirectionalIter1 __result = __rresult.base();
04276 advance(__result, -distance(__first2, __last2));
04277 return __result;
04278 }
04279 }
04280
04281 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
04282 typename _BinaryPredicate>
04283 _BidirectionalIter1
04284 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
04285 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
04286 bidirectional_iterator_tag, bidirectional_iterator_tag,
04287 _BinaryPredicate __comp)
04288 {
04289
04290 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
04291 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
04292
04293 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
04294 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
04295
04296 _RevIter1 __rlast1(__first1);
04297 _RevIter2 __rlast2(__first2);
04298 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
04299 _RevIter2(__last2), __rlast2,
04300 __comp);
04301
04302 if (__rresult == __rlast1)
04303 return __last1;
04304 else {
04305 _BidirectionalIter1 __result = __rresult.base();
04306 advance(__result, -distance(__first2, __last2));
04307 return __result;
04308 }
04309 }
04310
04311
04312
04313 template<typename _ForwardIter1, typename _ForwardIter2>
04314 inline _ForwardIter1
04315 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04316 _ForwardIter2 __first2, _ForwardIter2 __last2)
04317 {
04318
04319 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
04320 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
04321 __glibcpp_function_requires(_EqualOpConcept<
04322 typename iterator_traits<_ForwardIter1>::value_type,
04323 typename iterator_traits<_ForwardIter2>::value_type>)
04324
04325 return __find_end(__first1, __last1, __first2, __last2,
04326 __iterator_category(__first1),
04327 __iterator_category(__first2));
04328 }
04329
04330 template<typename _ForwardIter1, typename _ForwardIter2,
04331 typename _BinaryPredicate>
04332 inline _ForwardIter1
04333 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04334 _ForwardIter2 __first2, _ForwardIter2 __last2,
04335 _BinaryPredicate __comp)
04336 {
04337
04338 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
04339 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
04340 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04341 typename iterator_traits<_ForwardIter1>::value_type,
04342 typename iterator_traits<_ForwardIter2>::value_type>)
04343
04344 return __find_end(__first1, __last1, __first2, __last2,
04345 __iterator_category(__first1),
04346 __iterator_category(__first2),
04347 __comp);
04348 }
04349
04350 }
04351
04352 #endif
04353