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 _B
idirectionalIter>
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 _B
idirectionalIter>
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 _B
idirectionalIter,
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 _Eucl
ideanRingElement>
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 _B
idirectionalIter>
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 _B
idirectionalIter,
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 _Po
inter>
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 _Po
inter,
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 _Po
inter,
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 _B
idirectionalIter,
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 _B
idirectionalIter,
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 _B
idirectionalIter,
typename _Distance,
typename _Po
inter>
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 _B
idirectionalIter>
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 _B
idirectionalIter,
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 _B
idirectionalIter,
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 _B
idirectionalIter>
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 _B
idirectionalIter,
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 _B
idirectionalIter1,
typename _B
idirectionalIter2>
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