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