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
00061
#ifndef __GLIBCPP_INTERNAL_ALGO_H
00062
#define __GLIBCPP_INTERNAL_ALGO_H
00063
00064
#include <bits/stl_heap.h>
00065
#include <bits/stl_tempbuf.h>
00066
00067
00068
00069
namespace std
00070 {
00071
00084
template<
typename _Tp>
00085
inline const _Tp&
00086 __median(
const _Tp& __a,
const _Tp& __b,
const _Tp& __c)
00087 {
00088
00089 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
00090
if (__a < __b)
00091
if (__b < __c)
00092
return __b;
00093
else if (__a < __c)
00094
return __c;
00095
else
00096
return __a;
00097
else if (__a < __c)
00098
return __a;
00099
else if (__b < __c)
00100
return __c;
00101
else
00102
return __b;
00103 }
00104
00118
template<
typename _Tp,
typename _Compare>
00119
inline const _Tp&
00120 __median(
const _Tp& __a,
const _Tp& __b,
const _Tp& __c, _Compare __comp)
00121 {
00122
00123 __glibcpp_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
00124
if (__comp(__a, __b))
00125
if (__comp(__b, __c))
00126
return __b;
00127
else if (__comp(__a, __c))
00128
return __c;
00129
else
00130
return __a;
00131
else if (__comp(__a, __c))
00132
return __a;
00133
else if (__comp(__b, __c))
00134
return __c;
00135
else
00136
return __b;
00137 }
00138
00150
template<
typename _InputIter,
typename _Function>
00151 _Function
00152 for_each(_InputIter __first, _InputIter __last, _Function __f)
00153 {
00154
00155 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00156
for ( ; __first != __last; ++__first)
00157 __f(*__first);
00158
return __f;
00159 }
00160
00166
template<
typename _InputIter,
typename _Tp>
00167
inline _InputIter
00168
find(_InputIter __first, _InputIter __last,
00169
const _Tp& __val,
00170 input_iterator_tag)
00171 {
00172
while (__first != __last && !(*__first == __val))
00173 ++__first;
00174
return __first;
00175 }
00176
00182
template<
typename _InputIter,
typename _Predicate>
00183
inline _InputIter
00184
find_if(_InputIter __first, _InputIter __last,
00185 _Predicate __pred,
00186 input_iterator_tag)
00187 {
00188
while (__first != __last && !__pred(*__first))
00189 ++__first;
00190
return __first;
00191 }
00192
00198
template<
typename _RandomAccessIter,
typename _Tp>
00199 _RandomAccessIter
00200
find(_RandomAccessIter __first, _RandomAccessIter __last,
00201
const _Tp& __val,
00202 random_access_iterator_tag)
00203 {
00204
typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
00205 = (__last - __first) >> 2;
00206
00207
for ( ; __trip_count > 0 ; --__trip_count) {
00208
if (*__first == __val)
return __first;
00209 ++__first;
00210
00211
if (*__first == __val)
return __first;
00212 ++__first;
00213
00214
if (*__first == __val)
return __first;
00215 ++__first;
00216
00217
if (*__first == __val)
return __first;
00218 ++__first;
00219 }
00220
00221
switch(__last - __first) {
00222
case 3:
00223
if (*__first == __val)
return __first;
00224 ++__first;
00225
case 2:
00226
if (*__first == __val)
return __first;
00227 ++__first;
00228
case 1:
00229
if (*__first == __val)
return __first;
00230 ++__first;
00231
case 0:
00232
default:
00233
return __last;
00234 }
00235 }
00236
00242
template<
typename _RandomAccessIter,
typename _Predicate>
00243 _RandomAccessIter
00244
find_if(_RandomAccessIter __first, _RandomAccessIter __last,
00245 _Predicate __pred,
00246 random_access_iterator_tag)
00247 {
00248
typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
00249 = (__last - __first) >> 2;
00250
00251
for ( ; __trip_count > 0 ; --__trip_count) {
00252
if (__pred(*__first))
return __first;
00253 ++__first;
00254
00255
if (__pred(*__first))
return __first;
00256 ++__first;
00257
00258
if (__pred(*__first))
return __first;
00259 ++__first;
00260
00261
if (__pred(*__first))
return __first;
00262 ++__first;
00263 }
00264
00265
switch(__last - __first) {
00266
case 3:
00267
if (__pred(*__first))
return __first;
00268 ++__first;
00269
case 2:
00270
if (__pred(*__first))
return __first;
00271 ++__first;
00272
case 1:
00273
if (__pred(*__first))
return __first;
00274 ++__first;
00275
case 0:
00276
default:
00277
return __last;
00278 }
00279 }
00280
00289
template<
typename _InputIter,
typename _Tp>
00290
inline _InputIter
00291 find(_InputIter __first, _InputIter __last,
00292
const _Tp& __val)
00293 {
00294
00295 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00296 __glibcpp_function_requires(_EqualOpConcept<
00297
typename iterator_traits<_InputIter>::value_type, _Tp>)
00298
return find(__first, __last, __val, __iterator_category(__first));
00299 }
00300
00309
template<
typename _InputIter,
typename _Predicate>
00310
inline _InputIter
00311 find_if(_InputIter __first, _InputIter __last,
00312 _Predicate __pred)
00313 {
00314
00315 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00316 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00317
typename iterator_traits<_InputIter>::value_type>)
00318
return find_if(__first, __last, __pred, __iterator_category(__first));
00319 }
00320
00329
template<
typename _ForwardIter>
00330 _ForwardIter
00331 adjacent_find(_ForwardIter __first, _ForwardIter __last)
00332 {
00333
00334 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00335 __glibcpp_function_requires(_EqualityComparableConcept<
00336
typename iterator_traits<_ForwardIter>::value_type>)
00337
if (__first == __last)
00338
return __last;
00339 _ForwardIter __next = __first;
00340
while(++__next != __last) {
00341
if (*__first == *__next)
00342
return __first;
00343 __first = __next;
00344 }
00345
return __last;
00346 }
00347
00358
template<
typename _ForwardIter,
typename _BinaryPredicate>
00359 _ForwardIter
00360 adjacent_find(_ForwardIter __first, _ForwardIter __last,
00361 _BinaryPredicate __binary_pred)
00362 {
00363
00364 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00365 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00366
typename iterator_traits<_ForwardIter>::value_type,
00367
typename iterator_traits<_ForwardIter>::value_type>)
00368
if (__first == __last)
00369
return __last;
00370 _ForwardIter __next = __first;
00371
while(++__next != __last) {
00372
if (__binary_pred(*__first, *__next))
00373
return __first;
00374 __first = __next;
00375 }
00376
return __last;
00377 }
00378
00387
template<
typename _InputIter,
typename _Tp>
00388
typename iterator_traits<_InputIter>::difference_type
00389 count(_InputIter __first, _InputIter __last,
const _Tp& __value)
00390 {
00391
00392 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00393 __glibcpp_function_requires(_EqualityComparableConcept<
00394
typename iterator_traits<_InputIter>::value_type >)
00395 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
00396
typename iterator_traits<_InputIter>::difference_type __n = 0;
00397
for ( ; __first != __last; ++__first)
00398
if (*__first == __value)
00399 ++__n;
00400
return __n;
00401 }
00402
00411
template<
typename _InputIter,
typename _Predicate>
00412
typename iterator_traits<_InputIter>::difference_type
00413 count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
00414 {
00415
00416 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00417 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00418
typename iterator_traits<_InputIter>::value_type>)
00419
typename iterator_traits<_InputIter>::difference_type __n = 0;
00420
for ( ; __first != __last; ++__first)
00421
if (__pred(*__first))
00422 ++__n;
00423
return __n;
00424 }
00425
00426
00450
template<
typename _ForwardIter1,
typename _ForwardIter2>
00451 _ForwardIter1
00452 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00453 _ForwardIter2 __first2, _ForwardIter2 __last2)
00454 {
00455
00456 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
00457 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
00458 __glibcpp_function_requires(_EqualOpConcept<
00459
typename iterator_traits<_ForwardIter1>::value_type,
00460
typename iterator_traits<_ForwardIter2>::value_type>)
00461
00462
00463
if (__first1 == __last1 || __first2 == __last2)
00464
return __first1;
00465
00466
00467 _ForwardIter2 __tmp(__first2);
00468 ++__tmp;
00469
if (__tmp == __last2)
00470
return find(__first1, __last1, *__first2);
00471
00472
00473
00474 _ForwardIter2 __p1, __p;
00475
00476 __p1 = __first2; ++__p1;
00477
00478 _ForwardIter1 __current = __first1;
00479
00480
while (__first1 != __last1) {
00481 __first1 =
find(__first1, __last1, *__first2);
00482
if (__first1 == __last1)
00483
return __last1;
00484
00485 __p = __p1;
00486 __current = __first1;
00487
if (++__current == __last1)
00488
return __last1;
00489
00490
while (*__current == *__p) {
00491
if (++__p == __last2)
00492
return __first1;
00493
if (++__current == __last1)
00494
return __last1;
00495 }
00496
00497 ++__first1;
00498 }
00499
return __first1;
00500 }
00501
00522
template<
typename _ForwardIter1,
typename _ForwardIter2,
typename _BinaryPred>
00523 _ForwardIter1
00524 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00525 _ForwardIter2 __first2, _ForwardIter2 __last2,
00526 _BinaryPred __predicate)
00527 {
00528
00529 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
00530 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
00531 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
00532
typename iterator_traits<_ForwardIter1>::value_type,
00533
typename iterator_traits<_ForwardIter2>::value_type>)
00534
00535
00536
if (__first1 == __last1 || __first2 == __last2)
00537
return __first1;
00538
00539
00540 _ForwardIter2 __tmp(__first2);
00541 ++__tmp;
00542
if (__tmp == __last2) {
00543
while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00544 ++__first1;
00545
return __first1;
00546 }
00547
00548
00549
00550 _ForwardIter2 __p1, __p;
00551
00552 __p1 = __first2; ++__p1;
00553
00554 _ForwardIter1 __current = __first1;
00555
00556
while (__first1 != __last1) {
00557
while (__first1 != __last1) {
00558
if (__predicate(*__first1, *__first2))
00559
break;
00560 ++__first1;
00561 }
00562
while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00563 ++__first1;
00564
if (__first1 == __last1)
00565
return __last1;
00566
00567 __p = __p1;
00568 __current = __first1;
00569
if (++__current == __last1)
return __last1;
00570
00571
while (__predicate(*__current, *__p)) {
00572
if (++__p == __last2)
00573
return __first1;
00574
if (++__current == __last1)
00575
return __last1;
00576 }
00577
00578 ++__first1;
00579 }
00580
return __first1;
00581 }
00582
00596
template<
typename _ForwardIter,
typename _Integer,
typename _Tp>
00597 _ForwardIter
00598 search_n(_ForwardIter __first, _ForwardIter __last,
00599 _Integer __count,
const _Tp& __val)
00600 {
00601
00602 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00603 __glibcpp_function_requires(_EqualityComparableConcept<
00604
typename iterator_traits<_ForwardIter>::value_type>)
00605 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
00606
00607
if (__count <= 0)
00608
return __first;
00609
else {
00610 __first =
find(__first, __last, __val);
00611
while (__first != __last) {
00612 _Integer __n = __count - 1;
00613 _ForwardIter __i = __first;
00614 ++__i;
00615
while (__i != __last && __n != 0 && *__i == __val) {
00616 ++__i;
00617 --__n;
00618 }
00619
if (__n == 0)
00620
return __first;
00621
else
00622 __first =
find(__i, __last, __val);
00623 }
00624
return __last;
00625 }
00626 }
00627
00643
template<
typename _ForwardIter,
typename _Integer,
typename _Tp,
00644
typename _BinaryPred>
00645 _ForwardIter
00646 search_n(_ForwardIter __first, _ForwardIter __last,
00647 _Integer __count,
const _Tp& __val,
00648 _BinaryPred __binary_pred)
00649 {
00650
00651 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00652 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
00653
typename iterator_traits<_ForwardIter>::value_type, _Tp>)
00654
00655
if (__count <= 0)
00656
return __first;
00657
else {
00658
while (__first != __last) {
00659
if (__binary_pred(*__first, __val))
00660
break;
00661 ++__first;
00662 }
00663
while (__first != __last) {
00664 _Integer __n = __count - 1;
00665 _ForwardIter __i = __first;
00666 ++__i;
00667
while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
00668 ++__i;
00669 --__n;
00670 }
00671
if (__n == 0)
00672
return __first;
00673
else {
00674
while (__i != __last) {
00675
if (__binary_pred(*__i, __val))
00676
break;
00677 ++__i;
00678 }
00679 __first = __i;
00680 }
00681 }
00682
return __last;
00683 }
00684 }
00685
00697
template<
typename _ForwardIter1,
typename _ForwardIter2>
00698 _ForwardIter2
00699 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
00700 _ForwardIter2 __first2)
00701 {
00702
00703 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
00704 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
00705 __glibcpp_function_requires(_ConvertibleConcept<
00706
typename iterator_traits<_ForwardIter1>::value_type,
00707
typename iterator_traits<_ForwardIter2>::value_type>)
00708 __glibcpp_function_requires(_ConvertibleConcept<
00709
typename iterator_traits<_ForwardIter2>::value_type,
00710
typename iterator_traits<_ForwardIter1>::value_type>)
00711
00712
for ( ; __first1 != __last1; ++__first1, ++__first2)
00713
iter_swap(__first1, __first2);
00714
return __first2;
00715 }
00716
00732
template<
typename _InputIter,
typename _OutputIter,
typename _UnaryOperation>
00733 _OutputIter
00734 transform(_InputIter __first, _InputIter __last,
00735 _OutputIter __result, _UnaryOperation __unary_op)
00736 {
00737
00738 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00739 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00740
00741 __typeof__(__unary_op(*__first))>)
00742
00743
for ( ; __first != __last; ++__first, ++__result)
00744 *__result = __unary_op(*__first);
00745
return __result;
00746 }
00747
00765
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter,
00766
typename _BinaryOperation>
00767 _OutputIter
00768 transform(_InputIter1 __first1, _InputIter1 __last1,
00769 _InputIter2 __first2, _OutputIter __result,
00770 _BinaryOperation __binary_op)
00771 {
00772
00773 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00774 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00775 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00776
00777 __typeof__(__binary_op(*__first1,*__first2))>)
00778
00779
for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
00780 *__result = __binary_op(*__first1, *__first2);
00781
return __result;
00782 }
00783
00796
template<
typename _ForwardIter,
typename _Tp>
00797
void
00798 replace(_ForwardIter __first, _ForwardIter __last,
00799
const _Tp& __old_value,
const _Tp& __new_value)
00800 {
00801
00802 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
00803 __glibcpp_function_requires(_EqualOpConcept<
00804
typename iterator_traits<_ForwardIter>::value_type, _Tp>)
00805 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
00806
typename iterator_traits<_ForwardIter>::value_type>)
00807
00808
for ( ; __first != __last; ++__first)
00809
if (*__first == __old_value)
00810 *__first = __new_value;
00811 }
00812
00825
template<
typename _ForwardIter,
typename _Predicate,
typename _Tp>
00826
void
00827 replace_if(_ForwardIter __first, _ForwardIter __last,
00828 _Predicate __pred,
const _Tp& __new_value)
00829 {
00830
00831 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
00832 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
00833
typename iterator_traits<_ForwardIter>::value_type>)
00834 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00835
typename iterator_traits<_ForwardIter>::value_type>)
00836
00837
for ( ; __first != __last; ++__first)
00838
if (__pred(*__first))
00839 *__first = __new_value;
00840 }
00841
00856
template<
typename _InputIter,
typename _OutputIter,
typename _Tp>
00857 _OutputIter
00858 replace_copy(_InputIter __first, _InputIter __last,
00859 _OutputIter __result,
00860
const _Tp& __old_value,
const _Tp& __new_value)
00861 {
00862
00863 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00864 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00865
typename iterator_traits<_InputIter>::value_type>)
00866 __glibcpp_function_requires(_EqualOpConcept<
00867
typename iterator_traits<_InputIter>::value_type, _Tp>)
00868
00869
for ( ; __first != __last; ++__first, ++__result)
00870 *__result = *__first == __old_value ? __new_value : *__first;
00871
return __result;
00872 }
00873
00888
template<
typename _InputIter,
typename _OutputIter,
typename _Predicate,
00889
typename _Tp>
00890 _OutputIter
00891 replace_copy_if(_InputIter __first, _InputIter __last,
00892 _OutputIter __result,
00893 _Predicate __pred,
const _Tp& __new_value)
00894 {
00895
00896 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00897 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00898
typename iterator_traits<_InputIter>::value_type>)
00899 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00900
typename iterator_traits<_InputIter>::value_type>)
00901
00902
for ( ; __first != __last; ++__first, ++__result)
00903 *__result = __pred(*__first) ? __new_value : *__first;
00904
return __result;
00905 }
00906
00918
template<
typename _ForwardIter,
typename _Generator>
00919
void
00920 generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
00921 {
00922
00923 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00924 __glibcpp_function_requires(_GeneratorConcept<_Generator,
00925
typename iterator_traits<_ForwardIter>::value_type>)
00926
00927
for ( ; __first != __last; ++__first)
00928 *__first = __gen();
00929 }
00930
00942
template<
typename _OutputIter,
typename _Size,
typename _Generator>
00943 _OutputIter
00944 generate_n(_OutputIter __first, _Size __n, _Generator __gen)
00945 {
00946
00947 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00948
00949 __typeof__(gen())>)
00950
00951
for ( ; __n > 0; --__n, ++__first)
00952 *__first = __gen();
00953
return __first;
00954 }
00955
00969
template<
typename _InputIter,
typename _OutputIter,
typename _Tp>
00970 _OutputIter
00971 remove_copy(_InputIter __first, _InputIter __last,
00972 _OutputIter __result,
const _Tp& __value)
00973 {
00974
00975 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00976 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00977
typename iterator_traits<_InputIter>::value_type>)
00978 __glibcpp_function_requires(_EqualOpConcept<
00979
typename iterator_traits<_InputIter>::value_type, _Tp>)
00980
00981
for ( ; __first != __last; ++__first)
00982
if (!(*__first == __value)) {
00983 *__result = *__first;
00984 ++__result;
00985 }
00986
return __result;
00987 }
00988
01003
template<
typename _InputIter,
typename _OutputIter,
typename _Predicate>
01004 _OutputIter
01005 remove_copy_if(_InputIter __first, _InputIter __last,
01006 _OutputIter __result, _Predicate __pred)
01007 {
01008
01009 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
01010 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01011
typename iterator_traits<_InputIter>::value_type>)
01012 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01013
typename iterator_traits<_InputIter>::value_type>)
01014
01015
for ( ; __first != __last; ++__first)
01016
if (!__pred(*__first)) {
01017 *__result = *__first;
01018 ++__result;
01019 }
01020
return __result;
01021 }
01022
01039
template<
typename _ForwardIter,
typename _Tp>
01040 _ForwardIter
01041 remove(_ForwardIter __first, _ForwardIter __last,
01042
const _Tp& __value)
01043 {
01044
01045 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01046 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
01047
typename iterator_traits<_ForwardIter>::value_type>)
01048 __glibcpp_function_requires(_EqualOpConcept<
01049
typename iterator_traits<_ForwardIter>::value_type, _Tp>)
01050
01051 __first =
find(__first, __last, __value);
01052 _ForwardIter __i = __first;
01053
return __first == __last ? __first
01054 :
remove_copy(++__i, __last, __first, __value);
01055 }
01056
01073
template<
typename _ForwardIter,
typename _Predicate>
01074 _ForwardIter
01075 remove_if(_ForwardIter __first, _ForwardIter __last,
01076 _Predicate __pred)
01077 {
01078
01079 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01080 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01081
typename iterator_traits<_ForwardIter>::value_type>)
01082
01083 __first =
find_if(__first, __last, __pred);
01084 _ForwardIter __i = __first;
01085
return __first == __last ? __first
01086 :
remove_copy_if(++__i, __last, __first, __pred);
01087 }
01088
01095
template<
typename _InputIter,
typename _OutputIter>
01096 _OutputIter
01097 __unique_copy(_InputIter __first, _InputIter __last,
01098 _OutputIter __result,
01099 output_iterator_tag)
01100 {
01101
01102
typename iterator_traits<_InputIter>::value_type __value = *__first;
01103 *__result = __value;
01104
while (++__first != __last)
01105
if (!(__value == *__first)) {
01106 __value = *__first;
01107 *++__result = __value;
01108 }
01109
return ++__result;
01110 }
01111
01118
template<
typename _InputIter,
typename _ForwardIter>
01119 _ForwardIter
01120 __unique_copy(_InputIter __first, _InputIter __last,
01121 _ForwardIter __result,
01122 forward_iterator_tag)
01123 {
01124
01125 *__result = *__first;
01126
while (++__first != __last)
01127
if (!(*__result == *__first))
01128 *++__result = *__first;
01129
return ++__result;
01130 }
01131
01145
template<
typename _InputIter,
typename _OutputIter>
01146
inline _OutputIter
01147 unique_copy(_InputIter __first, _InputIter __last,
01148 _OutputIter __result)
01149 {
01150
01151 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
01152 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01153
typename iterator_traits<_InputIter>::value_type>)
01154 __glibcpp_function_requires(_EqualityComparableConcept<
01155
typename iterator_traits<_InputIter>::value_type>)
01156
01157
typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
01158
01159
if (__first == __last)
return __result;
01160
return __unique_copy(__first, __last, __result, _IterType());
01161 }
01162
01170
template<
typename _InputIter,
typename _OutputIter,
typename _BinaryPredicate>
01171 _OutputIter
01172 __unique_copy(_InputIter __first, _InputIter __last,
01173 _OutputIter __result,
01174 _BinaryPredicate __binary_pred,
01175 output_iterator_tag)
01176 {
01177
01178 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01179
typename iterator_traits<_InputIter>::value_type,
01180
typename iterator_traits<_InputIter>::value_type>)
01181
01182
typename iterator_traits<_InputIter>::value_type __value = *__first;
01183 *__result = __value;
01184
while (++__first != __last)
01185
if (!__binary_pred(__value, *__first)) {
01186 __value = *__first;
01187 *++__result = __value;
01188 }
01189
return ++__result;
01190 }
01191
01199
template<
typename _InputIter,
typename _ForwardIter,
typename _BinaryPredicate>
01200 _ForwardIter
01201 __unique_copy(_InputIter __first, _InputIter __last,
01202 _ForwardIter __result,
01203 _BinaryPredicate __binary_pred,
01204 forward_iterator_tag)
01205 {
01206
01207 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01208
typename iterator_traits<_ForwardIter>::value_type,
01209
typename iterator_traits<_InputIter>::value_type>)
01210
01211 *__result = *__first;
01212
while (++__first != __last)
01213
if (!__binary_pred(*__result, *__first)) *++__result = *__first;
01214
return ++__result;
01215 }
01216
01232
template<
typename _InputIter,
typename _OutputIter,
typename _BinaryPredicate>
01233
inline _OutputIter
01234 unique_copy(_InputIter __first, _InputIter __last,
01235 _OutputIter __result,
01236 _BinaryPredicate __binary_pred)
01237 {
01238
01239 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
01240 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01241
typename iterator_traits<_InputIter>::value_type>)
01242
01243
typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
01244
01245
if (__first == __last)
return __result;
01246
return __unique_copy(__first, __last,
01247 __result, __binary_pred, _IterType());
01248 }
01249
01263
template<
typename _ForwardIter>
01264 _ForwardIter
01265 unique(_ForwardIter __first, _ForwardIter __last)
01266 {
01267
01268 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01269 __glibcpp_function_requires(_EqualityComparableConcept<
01270
typename iterator_traits<_ForwardIter>::value_type>)
01271
01272 __first =
adjacent_find(__first, __last);
01273
return unique_copy(__first, __last, __first);
01274 }
01275
01290
template<
typename _ForwardIter,
typename _BinaryPredicate>
01291 _ForwardIter
01292 unique(_ForwardIter __first, _ForwardIter __last,
01293 _BinaryPredicate __binary_pred)
01294 {
01295
01296 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01297 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01298
typename iterator_traits<_ForwardIter>::value_type,
01299
typename iterator_traits<_ForwardIter>::value_type>)
01300
01301 __first =
adjacent_find(__first, __last, __binary_pred);
01302
return unique_copy(__first, __last, __first, __binary_pred);
01303 }
01304
01311
template<
typename _B
idirectionalIter>
01312
void
01313 __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
01314
bidirectional_iterator_tag)
01315 {
01316
while (
true)
01317
if (__first == __last || __first == --__last)
01318
return;
01319
else
01320
iter_swap(__first++, __last);
01321 }
01322
01329
template<
typename _RandomAccessIter>
01330
void
01331 __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
01332 random_access_iterator_tag)
01333 {
01334
while (__first < __last)
01335
iter_swap(__first++, --__last);
01336 }
01337
01349
template<
typename _B
idirectionalIter>
01350
inline void
01351 reverse(_BidirectionalIter __first, _BidirectionalIter __last)
01352 {
01353
01354 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
01355 _BidirectionalIter>)
01356 __reverse(__first, __last, __iterator_category(__first));
01357 }
01358
01374
template<
typename _B
idirectionalIter,
typename _OutputIter>
01375 _OutputIter
01376 reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last,
01377 _OutputIter __result)
01378 {
01379
01380 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
01381 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01382
typename iterator_traits<_BidirectionalIter>::value_type>)
01383
01384
while (__first != __last) {
01385 --__last;
01386 *__result = *__last;
01387 ++__result;
01388 }
01389
return __result;
01390 }
01391
01392
01399
template<
typename _Eucl
ideanRingElement>
01400 _EuclideanRingElement
01401 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
01402 {
01403
while (__n != 0) {
01404 _EuclideanRingElement __t = __m % __n;
01405 __m = __n;
01406 __n = __t;
01407 }
01408
return __m;
01409 }
01410
01416
template<
typename _ForwardIter>
01417
void
01418 __rotate(_ForwardIter __first,
01419 _ForwardIter __middle,
01420 _ForwardIter __last,
01421 forward_iterator_tag)
01422 {
01423
if ((__first == __middle) || (__last == __middle))
01424
return;
01425
01426 _ForwardIter __first2 = __middle;
01427
do {
01428
swap(*__first++, *__first2++);
01429
if (__first == __middle)
01430 __middle = __first2;
01431 }
while (__first2 != __last);
01432
01433 __first2 = __middle;
01434
01435
while (__first2 != __last) {
01436
swap(*__first++, *__first2++);
01437
if (__first == __middle)
01438 __middle = __first2;
01439
else if (__first2 == __last)
01440 __first2 = __middle;
01441 }
01442 }
01443
01449
template<
typename _B
idirectionalIter>
01450
void
01451 __rotate(_BidirectionalIter __first,
01452 _BidirectionalIter __middle,
01453 _BidirectionalIter __last,
01454
bidirectional_iterator_tag)
01455 {
01456
01457 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
01458 _BidirectionalIter>)
01459
01460
if ((__first == __middle) || (__last == __middle))
01461
return;
01462
01463 __reverse(__first, __middle,
bidirectional_iterator_tag());
01464 __reverse(__middle, __last,
bidirectional_iterator_tag());
01465
01466
while (__first != __middle && __middle != __last)
01467
swap (*__first++, *--__last);
01468
01469
if (__first == __middle) {
01470 __reverse(__middle, __last,
bidirectional_iterator_tag());
01471 }
01472
else {
01473 __reverse(__first, __middle,
bidirectional_iterator_tag());
01474 }
01475 }
01476
01482
template<
typename _RandomAccessIter>
01483
void
01484 __rotate(_RandomAccessIter __first,
01485 _RandomAccessIter __middle,
01486 _RandomAccessIter __last,
01487 random_access_iterator_tag)
01488 {
01489
01490 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01491 _RandomAccessIter>)
01492
01493
if ((__first == __middle) || (__last == __middle))
01494
return;
01495
01496
typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
01497
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
01498
01499 _Distance __n = __last - __first;
01500 _Distance __k = __middle - __first;
01501 _Distance __l = __n - __k;
01502
01503
if (__k == __l) {
01504
swap_ranges(__first, __middle, __middle);
01505
return;
01506 }
01507
01508 _Distance __d = __gcd(__n, __k);
01509
01510
for (_Distance __i = 0; __i < __d; __i++) {
01511 _ValueType __tmp = *__first;
01512 _RandomAccessIter __p = __first;
01513
01514
if (__k < __l) {
01515
for (_Distance __j = 0; __j < __l/__d; __j++) {
01516
if (__p > __first + __l) {
01517 *__p = *(__p - __l);
01518 __p -= __l;
01519 }
01520
01521 *__p = *(__p + __k);
01522 __p += __k;
01523 }
01524 }
01525
01526
else {
01527
for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
01528
if (__p < __last - __k) {
01529 *__p = *(__p + __k);
01530 __p += __k;
01531 }
01532
01533 *__p = * (__p - __l);
01534 __p -= __l;
01535 }
01536 }
01537
01538 *__p = __tmp;
01539 ++__first;
01540 }
01541 }
01542
01561
template<
typename _ForwardIter>
01562
inline void
01563 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
01564 {
01565
01566 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01567
01568
typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
01569 __rotate(__first, __middle, __last, _IterType());
01570 }
01571
01589
template<
typename _ForwardIter,
typename _OutputIter>
01590 _OutputIter
01591 rotate_copy(_ForwardIter __first, _ForwardIter __middle,
01592 _ForwardIter __last, _OutputIter __result)
01593 {
01594
01595 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
01596 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01597
typename iterator_traits<_ForwardIter>::value_type>)
01598
01599
return copy(__first, __middle,
copy(__middle, __last, __result));
01600 }
01601
01602
01612
template<
typename _Distance>
01613
inline _Distance
01614 __random_number(_Distance __n)
01615 {
01616
#ifdef _GLIBCPP_HAVE_DRAND48
01617
return lrand48() % __n;
01618
#else
01619
return rand() % __n;
01620
#endif
01621
}
01622
01623
01634
template<
typename _RandomAccessIter>
01635
inline void
01636 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
01637 {
01638
01639 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01640 _RandomAccessIter>)
01641
01642
if (__first == __last)
return;
01643
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01644
iter_swap(__i, __first + __random_number((__i - __first) + 1));
01645 }
01646
01660
template<
typename _RandomAccessIter,
typename _RandomNumberGenerator>
01661
void
01662 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
01663 _RandomNumberGenerator& __rand)
01664 {
01665
01666 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01667 _RandomAccessIter>)
01668
01669
if (__first == __last)
return;
01670
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01671
iter_swap(__i, __first + __rand((__i - __first) + 1));
01672 }
01673
01674
01680
template<
typename _ForwardIter,
typename _Predicate>
01681 _ForwardIter
01682 __partition(_ForwardIter __first, _ForwardIter __last,
01683 _Predicate __pred,
01684 forward_iterator_tag)
01685 {
01686
if (__first == __last)
return __first;
01687
01688
while (__pred(*__first))
01689
if (++__first == __last)
return __first;
01690
01691 _ForwardIter __next = __first;
01692
01693
while (++__next != __last)
01694
if (__pred(*__next)) {
01695
swap(*__first, *__next);
01696 ++__first;
01697 }
01698
01699
return __first;
01700 }
01701
01707
template<
typename _B
idirectionalIter,
typename _Predicate>
01708 _BidirectionalIter
01709 __partition(_BidirectionalIter __first, _BidirectionalIter __last,
01710 _Predicate __pred,
01711
bidirectional_iterator_tag)
01712 {
01713
while (
true) {
01714
while (
true)
01715
if (__first == __last)
01716
return __first;
01717
else if (__pred(*__first))
01718 ++__first;
01719
else
01720
break;
01721 --__last;
01722
while (
true)
01723
if (__first == __last)
01724
return __first;
01725
else if (!__pred(*__last))
01726 --__last;
01727
else
01728
break;
01729
iter_swap(__first, __last);
01730 ++__first;
01731 }
01732 }
01733
01748
template<
typename _ForwardIter,
typename _Predicate>
01749
inline _ForwardIter
01750 partition(_ForwardIter __first, _ForwardIter __last,
01751 _Predicate __pred)
01752 {
01753
01754 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01755 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01756
typename iterator_traits<_ForwardIter>::value_type>)
01757
01758
return __partition(__first, __last, __pred, __iterator_category(__first));
01759 }
01760
01761
01767
template<
typename _ForwardIter,
typename _Predicate,
typename _Distance>
01768 _ForwardIter
01769 __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last,
01770 _Predicate __pred, _Distance __len)
01771 {
01772
if (__len == 1)
01773
return __pred(*__first) ? __last : __first;
01774 _ForwardIter __middle = __first;
01775
advance(__middle, __len / 2);
01776 _ForwardIter __begin = __inplace_stable_partition(__first, __middle,
01777 __pred,
01778 __len / 2);
01779 _ForwardIter __end = __inplace_stable_partition(__middle, __last,
01780 __pred,
01781 __len - __len / 2);
01782
rotate(__begin, __middle, __end);
01783
advance(__begin,
distance(__middle, __end));
01784
return __begin;
01785 }
01786
01792
template<
typename _ForwardIter,
typename _Pointer,
typename _Predicate,
01793
typename _Distance>
01794 _ForwardIter
01795 __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last,
01796 _Predicate __pred, _Distance __len,
01797 _Pointer __buffer,
01798 _Distance __buffer_size)
01799 {
01800
if (__len <= __buffer_size) {
01801 _ForwardIter __result1 = __first;
01802 _Pointer __result2 = __buffer;
01803
for ( ; __first != __last ; ++__first)
01804
if (__pred(*__first)) {
01805 *__result1 = *__first;
01806 ++__result1;
01807 }
01808
else {
01809 *__result2 = *__first;
01810 ++__result2;
01811 }
01812
copy(__buffer, __result2, __result1);
01813
return __result1;
01814 }
01815
else {
01816 _ForwardIter __middle = __first;
01817
advance(__middle, __len / 2);
01818 _ForwardIter __begin = __stable_partition_adaptive(__first, __middle,
01819 __pred,
01820 __len / 2,
01821 __buffer, __buffer_size);
01822 _ForwardIter __end = __stable_partition_adaptive( __middle, __last,
01823 __pred,
01824 __len - __len / 2,
01825 __buffer, __buffer_size);
01826
rotate(__begin, __middle, __end);
01827
advance(__begin,
distance(__middle, __end));
01828
return __begin;
01829 }
01830 }
01831
01848
template<
typename _ForwardIter,
typename _Predicate>
01849 _ForwardIter
01850 stable_partition(_ForwardIter __first, _ForwardIter __last,
01851 _Predicate __pred)
01852 {
01853
01854 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
01855 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01856
typename iterator_traits<_ForwardIter>::value_type>)
01857
01858
if (__first == __last)
01859
return __first;
01860
else
01861 {
01862
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
01863
typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
01864
01865 _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last);
01866
if (__buf.size() > 0)
01867
return __stable_partition_adaptive(__first, __last, __pred,
01868 _DistanceType(__buf.requested_size()),
01869 __buf.begin(), __buf.size());
01870
else
01871
return __inplace_stable_partition(__first, __last, __pred,
01872 _DistanceType(__buf.requested_size()));
01873 }
01874 }
01875
01881
template<
typename _RandomAccessIter,
typename _Tp>
01882 _RandomAccessIter
01883 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
01884 _Tp __pivot)
01885 {
01886
while (
true) {
01887
while (*__first < __pivot)
01888 ++__first;
01889 --__last;
01890
while (__pivot < *__last)
01891 --__last;
01892
if (!(__first < __last))
01893
return __first;
01894
iter_swap(__first, __last);
01895 ++__first;
01896 }
01897 }
01898
01904
template<
typename _RandomAccessIter,
typename _Tp,
typename _Compare>
01905 _RandomAccessIter
01906 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
01907 _Tp __pivot, _Compare __comp)
01908 {
01909
while (
true) {
01910
while (__comp(*__first, __pivot))
01911 ++__first;
01912 --__last;
01913
while (__comp(__pivot, *__last))
01914 --__last;
01915
if (!(__first < __last))
01916
return __first;
01917
iter_swap(__first, __last);
01918 ++__first;
01919 }
01920 }
01921
01922
01929
enum { _M_threshold = 16 };
01930
01936
template<
typename _RandomAccessIter,
typename _Tp>
01937
void
01938 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
01939 {
01940 _RandomAccessIter __next = __last;
01941 --__next;
01942
while (__val < *__next) {
01943 *__last = *__next;
01944 __last = __next;
01945 --__next;
01946 }
01947 *__last = __val;
01948 }
01949
01955
template<
typename _RandomAccessIter,
typename _Tp,
typename _Compare>
01956
void
01957 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp)
01958 {
01959 _RandomAccessIter __next = __last;
01960 --__next;
01961
while (__comp(__val, *__next)) {
01962 *__last = *__next;
01963 __last = __next;
01964 --__next;
01965 }
01966 *__last = __val;
01967 }
01968
01974
template<
typename _RandomAccessIter>
01975
void
01976 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
01977 {
01978
if (__first == __last)
return;
01979
01980
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01981 {
01982
typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
01983
if (__val < *__first) {
01984
copy_backward(__first, __i, __i + 1);
01985 *__first = __val;
01986 }
01987
else
01988 __unguarded_linear_insert(__i, __val);
01989 }
01990 }
01991
01997
template<
typename _RandomAccessIter,
typename _Compare>
01998
void
01999 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02000 _Compare __comp)
02001 {
02002
if (__first == __last)
return;
02003
02004
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
02005 {
02006
typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
02007
if (__comp(__val, *__first)) {
02008
copy_backward(__first, __i, __i + 1);
02009 *__first = __val;
02010 }
02011
else
02012 __unguarded_linear_insert(__i, __val, __comp);
02013 }
02014 }
02015
02021
template<
typename _RandomAccessIter>
02022
inline void
02023 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02024 {
02025
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02026
02027
for (_RandomAccessIter __i = __first; __i != __last; ++__i)
02028 __unguarded_linear_insert(__i, _ValueType(*__i));
02029 }
02030
02036
template<
typename _RandomAccessIter,
typename _Compare>
02037
inline void
02038 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02039 _Compare __comp)
02040 {
02041
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02042
02043
for (_RandomAccessIter __i = __first; __i != __last; ++__i)
02044 __unguarded_linear_insert(__i, _ValueType(*__i), __comp);
02045 }
02046
02052
template<
typename _RandomAccessIter>
02053
void
02054 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02055 {
02056
if (__last - __first > _M_threshold) {
02057 __insertion_sort(__first, __first + _M_threshold);
02058 __unguarded_insertion_sort(__first + _M_threshold, __last);
02059 }
02060
else
02061 __insertion_sort(__first, __last);
02062 }
02063
02069
template<
typename _RandomAccessIter,
typename _Compare>
02070
void
02071 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02072 _Compare __comp)
02073 {
02074
if (__last - __first > _M_threshold) {
02075 __insertion_sort(__first, __first + _M_threshold, __comp);
02076 __unguarded_insertion_sort(__first + _M_threshold, __last, __comp);
02077 }
02078
else
02079 __insertion_sort(__first, __last, __comp);
02080 }
02081
02087
template<
typename _Size>
02088
inline _Size
02089 __lg(_Size __n)
02090 {
02091 _Size __k;
02092
for (__k = 0; __n != 1; __n >>= 1) ++__k;
02093
return __k;
02094 }
02095
02101
template<
typename _RandomAccessIter,
typename _Size>
02102
void
02103 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
02104 _Size __depth_limit)
02105 {
02106
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02107
02108
while (__last - __first > _M_threshold) {
02109
if (__depth_limit == 0) {
02110
partial_sort(__first, __last, __last);
02111
return;
02112 }
02113 --__depth_limit;
02114 _RandomAccessIter __cut =
02115 __unguarded_partition(__first, __last,
02116 _ValueType(
__median(*__first,
02117 *(__first + (__last - __first)/2),
02118 *(__last - 1))));
02119 __introsort_loop(__cut, __last, __depth_limit);
02120 __last = __cut;
02121 }
02122 }
02123
02129
template<
typename _RandomAccessIter,
typename _Size,
typename _Compare>
02130
void
02131 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
02132 _Size __depth_limit, _Compare __comp)
02133 {
02134
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02135
02136
while (__last - __first > _M_threshold) {
02137
if (__depth_limit == 0) {
02138
partial_sort(__first, __last, __last, __comp);
02139
return;
02140 }
02141 --__depth_limit;
02142 _RandomAccessIter __cut =
02143 __unguarded_partition(__first, __last,
02144 _ValueType(
__median(*__first,
02145 *(__first + (__last - __first)/2),
02146 *(__last - 1), __comp)),
02147 __comp);
02148 __introsort_loop(__cut, __last, __depth_limit, __comp);
02149 __last = __cut;
02150 }
02151 }
02152
02166
template<
typename _RandomAccessIter>
02167
inline void
02168
sort(_RandomAccessIter __first, _RandomAccessIter __last)
02169 {
02170
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02171
02172
02173 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02174 _RandomAccessIter>)
02175 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02176
02177
if (__first != __last) {
02178 __introsort_loop(__first, __last, __lg(__last - __first) * 2);
02179 __final_insertion_sort(__first, __last);
02180 }
02181 }
02182
02197
template<
typename _RandomAccessIter,
typename _Compare>
02198
inline void
02199
sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
02200 {
02201
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02202
02203
02204 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02205 _RandomAccessIter>)
02206 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
02207
02208
if (__first != __last) {
02209 __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp);
02210 __final_insertion_sort(__first, __last, __comp);
02211 }
02212 }
02213
02214
02220
template<
typename _RandomAccessIter>
02221
void
02222 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02223 {
02224
if (__last - __first < 15) {
02225 __insertion_sort(__first, __last);
02226
return;
02227 }
02228 _RandomAccessIter __middle = __first + (__last - __first) / 2;
02229 __inplace_stable_sort(__first, __middle);
02230 __inplace_stable_sort(__middle, __last);
02231 __merge_without_buffer(__first, __middle, __last,
02232 __middle - __first,
02233 __last - __middle);
02234 }
02235
02241
template<
typename _RandomAccessIter,
typename _Compare>
02242
void
02243 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02244 _Compare __comp)
02245 {
02246
if (__last - __first < 15) {
02247 __insertion_sort(__first, __last, __comp);
02248
return;
02249 }
02250 _RandomAccessIter __middle = __first + (__last - __first) / 2;
02251 __inplace_stable_sort(__first, __middle, __comp);
02252 __inplace_stable_sort(__middle, __last, __comp);
02253 __merge_without_buffer(__first, __middle, __last,
02254 __middle - __first,
02255 __last - __middle,
02256 __comp);
02257 }
02258
02259
template<
typename _RandomAccessIter1,
typename _RandomAccessIter2,
02260
typename _Distance>
02261
void
02262 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
02263 _RandomAccessIter2 __result, _Distance __step_size)
02264 {
02265 _Distance __two_step = 2 * __step_size;
02266
02267
while (__last - __first >= __two_step) {
02268 __result =
merge(__first, __first + __step_size,
02269 __first + __step_size, __first + __two_step,
02270 __result);
02271 __first += __two_step;
02272 }
02273
02274 __step_size =
min(_Distance(__last - __first), __step_size);
02275
merge(__first, __first + __step_size, __first + __step_size, __last,
02276 __result);
02277 }
02278
02279
template<
typename _RandomAccessIter1,
typename _RandomAccessIter2,
02280
typename _Distance,
typename _Compare>
02281
void
02282 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
02283 _RandomAccessIter2 __result, _Distance __step_size,
02284 _Compare __comp)
02285 {
02286 _Distance __two_step = 2 * __step_size;
02287
02288
while (__last - __first >= __two_step) {
02289 __result =
merge(__first, __first + __step_size,
02290 __first + __step_size, __first + __two_step,
02291 __result,
02292 __comp);
02293 __first += __two_step;
02294 }
02295 __step_size =
min(_Distance(__last - __first), __step_size);
02296
02297
merge(__first, __first + __step_size,
02298 __first + __step_size, __last,
02299 __result,
02300 __comp);
02301 }
02302
02303
enum { _M_chunk_size = 7 };
02304
02305
template<
typename _RandomAccessIter,
typename _Distance>
02306
void
02307 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02308 _Distance __chunk_size)
02309 {
02310
while (__last - __first >= __chunk_size) {
02311 __insertion_sort(__first, __first + __chunk_size);
02312 __first += __chunk_size;
02313 }
02314 __insertion_sort(__first, __last);
02315 }
02316
02317
template<
typename _RandomAccessIter,
typename _Distance,
typename _Compare>
02318
void
02319 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
02320 _Distance __chunk_size, _Compare __comp)
02321 {
02322
while (__last - __first >= __chunk_size) {
02323 __insertion_sort(__first, __first + __chunk_size, __comp);
02324 __first += __chunk_size;
02325 }
02326 __insertion_sort(__first, __last, __comp);
02327 }
02328
02329
template<
typename _RandomAccessIter,
typename _Po
inter>
02330
void
02331 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
02332 _Pointer __buffer)
02333 {
02334
typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
02335
02336 _Distance __len = __last - __first;
02337 _Pointer __buffer_last = __buffer + __len;
02338
02339 _Distance __step_size = _M_chunk_size;
02340 __chunk_insertion_sort(__first, __last, __step_size);
02341
02342
while (__step_size < __len) {
02343 __merge_sort_loop(__first, __last, __buffer, __step_size);
02344 __step_size *= 2;
02345 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
02346 __step_size *= 2;
02347 }
02348 }
02349
02350
template<
typename _RandomAccessIter,
typename _Po
inter,
typename _Compare>
02351
void
02352 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
02353 _Pointer __buffer, _Compare __comp)
02354 {
02355
typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
02356
02357 _Distance __len = __last - __first;
02358 _Pointer __buffer_last = __buffer + __len;
02359
02360 _Distance __step_size = _M_chunk_size;
02361 __chunk_insertion_sort(__first, __last, __step_size, __comp);
02362
02363
while (__step_size < __len) {
02364 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
02365 __step_size *= 2;
02366 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
02367 __step_size *= 2;
02368 }
02369 }
02370
02371
template<
typename _RandomAccessIter,
typename _Po
inter,
typename _Distance>
02372
void
02373 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
02374 _Pointer __buffer, _Distance __buffer_size)
02375 {
02376 _Distance __len = (__last - __first + 1) / 2;
02377 _RandomAccessIter __middle = __first + __len;
02378
if (__len > __buffer_size) {
02379 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
02380 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
02381 }
02382
else {
02383 __merge_sort_with_buffer(__first, __middle, __buffer);
02384 __merge_sort_with_buffer(__middle, __last, __buffer);
02385 }
02386 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
02387 _Distance(__last - __middle), __buffer, __buffer_size);
02388 }
02389
02390
template<
typename _RandomAccessIter,
typename _Pointer,
typename _Distance,
02391
typename _Compare>
02392
void
02393 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
02394 _Pointer __buffer, _Distance __buffer_size,
02395 _Compare __comp)
02396 {
02397 _Distance __len = (__last - __first + 1) / 2;
02398 _RandomAccessIter __middle = __first + __len;
02399
if (__len > __buffer_size) {
02400 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
02401 __comp);
02402 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
02403 __comp);
02404 }
02405
else {
02406 __merge_sort_with_buffer(__first, __middle, __buffer, __comp);
02407 __merge_sort_with_buffer(__middle, __last, __buffer, __comp);
02408 }
02409 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
02410 _Distance(__last - __middle), __buffer, __buffer_size,
02411 __comp);
02412 }
02413
02430
template<
typename _RandomAccessIter>
02431
inline void
02432
stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
02433 {
02434
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02435
typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02436
02437
02438 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02439 _RandomAccessIter>)
02440 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02441
02442 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
02443
if (buf.begin() == 0)
02444 __inplace_stable_sort(__first, __last);
02445
else
02446 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
02447 }
02448
02466
template<
typename _RandomAccessIter,
typename _Compare>
02467
inline void
02468
stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
02469 {
02470
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02471
typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02472
02473
02474 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02475 _RandomAccessIter>)
02476 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02477 _ValueType, _ValueType>)
02478
02479 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
02480
if (buf.begin() == 0)
02481 __inplace_stable_sort(__first, __last, __comp);
02482
else
02483 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
02484 __comp);
02485 }
02486
02502
template<
typename _RandomAccessIter>
02503
void
02504
partial_sort(_RandomAccessIter __first,
02505 _RandomAccessIter __middle,
02506 _RandomAccessIter __last)
02507 {
02508
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02509
02510
02511 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02512 _RandomAccessIter>)
02513 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02514
02515 make_heap(__first, __middle);
02516
for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
02517
if (*__i < *__first)
02518 __pop_heap(__first, __middle, __i, _ValueType(*__i));
02519 sort_heap(__first, __middle);
02520 }
02521
02540
template<
typename _RandomAccessIter,
typename _Compare>
02541
void
02542
partial_sort(_RandomAccessIter __first,
02543 _RandomAccessIter __middle,
02544 _RandomAccessIter __last,
02545 _Compare __comp)
02546 {
02547
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02548
02549
02550 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02551 _RandomAccessIter>)
02552 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02553 _ValueType, _ValueType>)
02554
02555 make_heap(__first, __middle, __comp);
02556
for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
02557
if (__comp(*__i, *__first))
02558 __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
02559 sort_heap(__first, __middle, __comp);
02560 }
02561
02579
template<
typename _InputIter,
typename _RandomAccessIter>
02580 _RandomAccessIter
02581
partial_sort_copy(_InputIter __first, _InputIter __last,
02582 _RandomAccessIter __result_first,
02583 _RandomAccessIter __result_last)
02584 {
02585
typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
02586
typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
02587
typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02588
02589
02590 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
02591 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
02592 __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>)
02593 __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>)
02594
02595
if (__result_first == __result_last)
return __result_last;
02596 _RandomAccessIter __result_real_last = __result_first;
02597
while(__first != __last && __result_real_last != __result_last) {
02598 *__result_real_last = *__first;
02599 ++__result_real_last;
02600 ++__first;
02601 }
02602 make_heap(__result_first, __result_real_last);
02603
while (__first != __last) {
02604
if (*__first < *__result_first)
02605 __adjust_heap(__result_first, _DistanceType(0),
02606 _DistanceType(__result_real_last - __result_first),
02607 _InputValueType(*__first));
02608 ++__first;
02609 }
02610 sort_heap(__result_first, __result_real_last);
02611
return __result_real_last;
02612 }
02613
02633
template<
typename _InputIter,
typename _RandomAccessIter,
typename _Compare>
02634 _RandomAccessIter
02635
partial_sort_copy(_InputIter __first, _InputIter __last,
02636 _RandomAccessIter __result_first,
02637 _RandomAccessIter __result_last,
02638 _Compare __comp)
02639 {
02640
typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
02641
typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
02642
typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
02643
02644
02645 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
02646 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
02647 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
02648 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02649 _OutputValueType, _OutputValueType>)
02650
02651
if (__result_first == __result_last)
return __result_last;
02652 _RandomAccessIter __result_real_last = __result_first;
02653
while(__first != __last && __result_real_last != __result_last) {
02654 *__result_real_last = *__first;
02655 ++__result_real_last;
02656 ++__first;
02657 }
02658 make_heap(__result_first, __result_real_last, __comp);
02659
while (__first != __last) {
02660
if (__comp(*__first, *__result_first))
02661 __adjust_heap(__result_first, _DistanceType(0),
02662 _DistanceType(__result_real_last - __result_first),
02663 _InputValueType(*__first),
02664 __comp);
02665 ++__first;
02666 }
02667 sort_heap(__result_first, __result_real_last, __comp);
02668
return __result_real_last;
02669 }
02670
02686
template<
typename _RandomAccessIter>
02687
void
02688
nth_element(_RandomAccessIter __first,
02689 _RandomAccessIter __nth,
02690 _RandomAccessIter __last)
02691 {
02692
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02693
02694
02695 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
02696 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
02697
02698
while (__last - __first > 3) {
02699 _RandomAccessIter __cut =
02700 __unguarded_partition(__first, __last,
02701 _ValueType(
__median(*__first,
02702 *(__first + (__last - __first)/2),
02703 *(__last - 1))));
02704
if (__cut <= __nth)
02705 __first = __cut;
02706
else
02707 __last = __cut;
02708 }
02709 __insertion_sort(__first, __last);
02710 }
02711
02728
template<
typename _RandomAccessIter,
typename _Compare>
02729
void
02730
nth_element(_RandomAccessIter __first,
02731 _RandomAccessIter __nth,
02732 _RandomAccessIter __last,
02733 _Compare __comp)
02734 {
02735
typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
02736
02737
02738 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
02739 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02740 _ValueType, _ValueType>)
02741
02742
while (__last - __first > 3) {
02743 _RandomAccessIter __cut =
02744 __unguarded_partition(__first, __last,
02745 _ValueType(
__median(*__first,
02746 *(__first + (__last - __first)/2),
02747 *(__last - 1),
02748 __comp)),
02749 __comp);
02750
if (__cut <= __nth)
02751 __first = __cut;
02752
else
02753 __last = __cut;
02754 }
02755 __insertion_sort(__first, __last, __comp);
02756 }
02757
02758
02768
template<
typename _ForwardIter,
typename _Tp>
02769 _ForwardIter
02770
lower_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val)
02771 {
02772
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02773
typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02774
02775
02776
02777
02778
02779
02780 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02781 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02782 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
02783
02784 _DistanceType __len =
distance(__first, __last);
02785 _DistanceType __half;
02786 _ForwardIter __middle;
02787
02788
while (__len > 0) {
02789 __half = __len >> 1;
02790 __middle = __first;
02791
advance(__middle, __half);
02792
if (*__middle < __val) {
02793 __first = __middle;
02794 ++__first;
02795 __len = __len - __half - 1;
02796 }
02797
else
02798 __len = __half;
02799 }
02800
return __first;
02801 }
02802
02816
template<
typename _ForwardIter,
typename _Tp,
typename _Compare>
02817 _ForwardIter
02818
lower_bound(_ForwardIter __first, _ForwardIter __last,
02819 const _Tp& __val, _Compare __comp)
02820 {
02821
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02822
typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02823
02824
02825 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02826 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
02827
02828 _DistanceType __len =
distance(__first, __last);
02829 _DistanceType __half;
02830 _ForwardIter __middle;
02831
02832
while (__len > 0) {
02833 __half = __len >> 1;
02834 __middle = __first;
02835
advance(__middle, __half);
02836
if (__comp(*__middle, __val)) {
02837 __first = __middle;
02838 ++__first;
02839 __len = __len - __half - 1;
02840 }
02841
else
02842 __len = __half;
02843 }
02844
return __first;
02845 }
02846
02856
template<
typename _ForwardIter,
typename _Tp>
02857 _ForwardIter
02858
upper_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val)
02859 {
02860
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02861
typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02862
02863
02864
02865 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02866 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02867 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
02868
02869 _DistanceType __len =
distance(__first, __last);
02870 _DistanceType __half;
02871 _ForwardIter __middle;
02872
02873
while (__len > 0) {
02874 __half = __len >> 1;
02875 __middle = __first;
02876
advance(__middle, __half);
02877
if (__val < *__middle)
02878 __len = __half;
02879
else {
02880 __first = __middle;
02881 ++__first;
02882 __len = __len - __half - 1;
02883 }
02884 }
02885
return __first;
02886 }
02887
02901
template<
typename _ForwardIter,
typename _Tp,
typename _Compare>
02902 _ForwardIter
02903
upper_bound(_ForwardIter __first, _ForwardIter __last,
02904 const _Tp& __val, _Compare __comp)
02905 {
02906
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02907
typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02908
02909
02910 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02911 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
02912
02913 _DistanceType __len =
distance(__first, __last);
02914 _DistanceType __half;
02915 _ForwardIter __middle;
02916
02917
while (__len > 0) {
02918 __half = __len >> 1;
02919 __middle = __first;
02920
advance(__middle, __half);
02921
if (__comp(__val, *__middle))
02922 __len = __half;
02923
else {
02924 __first = __middle;
02925 ++__first;
02926 __len = __len - __half - 1;
02927 }
02928 }
02929
return __first;
02930 }
02931
02948
template<
typename _ForwardIter,
typename _Tp>
02949 pair<_ForwardIter, _ForwardIter>
02950
equal_range(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val)
02951 {
02952
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
02953
typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
02954
02955
02956
02957 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
02958 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
02959 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
02960
02961 _DistanceType __len =
distance(__first, __last);
02962 _DistanceType __half;
02963 _ForwardIter __middle, __left, __right;
02964
02965
while (__len > 0) {
02966 __half = __len >> 1;
02967 __middle = __first;
02968
advance(__middle, __half);
02969
if (*__middle < __val) {
02970 __first = __middle;
02971 ++__first;
02972 __len = __len - __half - 1;
02973 }
02974
else if (__val < *__middle)
02975 __len = __half;
02976
else {
02977 __left =
lower_bound(__first, __middle, __val);
02978
advance(__first, __len);
02979 __right =
upper_bound(++__middle, __first, __val);
02980
return pair<_ForwardIter, _ForwardIter>(__left, __right);
02981 }
02982 }
02983
return pair<_ForwardIter, _ForwardIter>(__first, __first);
02984 }
02985
03003
template<
typename _ForwardIter,
typename _Tp,
typename _Compare>
03004 pair<_ForwardIter, _ForwardIter>
03005
equal_range(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val,
03006 _Compare __comp)
03007 {
03008
typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
03009
typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
03010
03011
03012 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03013 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
03014 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
03015
03016 _DistanceType __len =
distance(__first, __last);
03017 _DistanceType __half;
03018 _ForwardIter __middle, __left, __right;
03019
03020
while (__len > 0) {
03021 __half = __len >> 1;
03022 __middle = __first;
03023
advance(__middle, __half);
03024
if (__comp(*__middle, __val)) {
03025 __first = __middle;
03026 ++__first;
03027 __len = __len - __half - 1;
03028 }
03029
else if (__comp(__val, *__middle))
03030 __len = __half;
03031
else {
03032 __left =
lower_bound(__first, __middle, __val, __comp);
03033
advance(__first, __len);
03034 __right =
upper_bound(++__middle, __first, __val, __comp);
03035
return pair<_ForwardIter, _ForwardIter>(__left, __right);
03036 }
03037 }
03038
return pair<_ForwardIter, _ForwardIter>(__first, __first);
03039 }
03040
03052
template<
typename _ForwardIter,
typename _Tp>
03053
bool
03054
binary_search(_ForwardIter __first, _ForwardIter __last,
03055 const _Tp& __val)
03056 {
03057
03058
03059 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03060 __glibcpp_function_requires(_SameTypeConcept<_Tp,
03061
typename iterator_traits<_ForwardIter>::value_type>)
03062 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
03063
03064 _ForwardIter __i =
lower_bound(__first, __last, __val);
03065
return __i != __last && !(__val < *__i);
03066 }
03067
03083
template<
typename _ForwardIter,
typename _Tp,
typename _Compare>
03084
bool
03085
binary_search(_ForwardIter __first, _ForwardIter __last,
03086 const _Tp& __val, _Compare __comp)
03087 {
03088
03089 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03090 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03091
typename iterator_traits<_ForwardIter>::value_type, _Tp>)
03092 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
03093
typename iterator_traits<_ForwardIter>::value_type>)
03094
03095 _ForwardIter __i =
lower_bound(__first, __last, __val, __comp);
03096
return __i != __last && !__comp(__val, *__i);
03097 }
03098
03115
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter>
03116 _OutputIter
03117
merge(_InputIter1 __first1, _InputIter1 __last1,
03118 _InputIter2 __first2, _InputIter2 __last2,
03119 _OutputIter __result)
03120 {
03121
03122 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03123 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03124 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03125
typename iterator_traits<_InputIter1>::value_type>)
03126 __glibcpp_function_requires(_SameTypeConcept<
03127
typename iterator_traits<_InputIter1>::value_type,
03128
typename iterator_traits<_InputIter2>::value_type>)
03129 __glibcpp_function_requires(_LessThanComparableConcept<
03130
typename iterator_traits<_InputIter1>::value_type>)
03131
03132
while (__first1 != __last1 && __first2 != __last2) {
03133
if (*__first2 < *__first1) {
03134 *__result = *__first2;
03135 ++__first2;
03136 }
03137
else {
03138 *__result = *__first1;
03139 ++__first1;
03140 }
03141 ++__result;
03142 }
03143
return copy(__first2, __last2,
copy(__first1, __last1, __result));
03144 }
03145
03166
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter,
03167
typename _Compare>
03168 _OutputIter
03169
merge(_InputIter1 __first1, _InputIter1 __last1,
03170 _InputIter2 __first2, _InputIter2 __last2,
03171 _OutputIter __result, _Compare __comp)
03172 {
03173
03174 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03175 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03176 __glibcpp_function_requires(_SameTypeConcept<
03177
typename iterator_traits<_InputIter1>::value_type,
03178
typename iterator_traits<_InputIter2>::value_type>)
03179 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03180
typename iterator_traits<_InputIter1>::value_type>)
03181 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03182
typename iterator_traits<_InputIter1>::value_type,
03183
typename iterator_traits<_InputIter2>::value_type>)
03184
03185
while (__first1 != __last1 && __first2 != __last2) {
03186
if (__comp(*__first2, *__first1)) {
03187 *__result = *__first2;
03188 ++__first2;
03189 }
03190
else {
03191 *__result = *__first1;
03192 ++__first1;
03193 }
03194 ++__result;
03195 }
03196
return copy(__first2, __last2,
copy(__first1, __last1, __result));
03197 }
03198
03204
template<
typename _B
idirectionalIter,
typename _Distance>
03205
void
03206 __merge_without_buffer(_BidirectionalIter __first,
03207 _BidirectionalIter __middle,
03208 _BidirectionalIter __last,
03209 _Distance __len1, _Distance __len2)
03210 {
03211
if (__len1 == 0 || __len2 == 0)
03212
return;
03213
if (__len1 + __len2 == 2) {
03214
if (*__middle < *__first)
03215
iter_swap(__first, __middle);
03216
return;
03217 }
03218 _BidirectionalIter __first_cut = __first;
03219 _BidirectionalIter __second_cut = __middle;
03220 _Distance __len11 = 0;
03221 _Distance __len22 = 0;
03222
if (__len1 > __len2) {
03223 __len11 = __len1 / 2;
03224
advance(__first_cut, __len11);
03225 __second_cut =
lower_bound(__middle, __last, *__first_cut);
03226 __len22 =
distance(__middle, __second_cut);
03227 }
03228
else {
03229 __len22 = __len2 / 2;
03230
advance(__second_cut, __len22);
03231 __first_cut =
upper_bound(__first, __middle, *__second_cut);
03232 __len11 =
distance(__first, __first_cut);
03233 }
03234
rotate(__first_cut, __middle, __second_cut);
03235 _BidirectionalIter __new_middle = __first_cut;
03236
advance(__new_middle,
distance(__middle, __second_cut));
03237 __merge_without_buffer(__first, __first_cut, __new_middle,
03238 __len11, __len22);
03239 __merge_without_buffer(__new_middle, __second_cut, __last,
03240 __len1 - __len11, __len2 - __len22);
03241 }
03242
03248
template<
typename _B
idirectionalIter,
typename _Distance,
typename _Compare>
03249
void
03250 __merge_without_buffer(_BidirectionalIter __first,
03251 _BidirectionalIter __middle,
03252 _BidirectionalIter __last,
03253 _Distance __len1, _Distance __len2,
03254 _Compare __comp)
03255 {
03256
if (__len1 == 0 || __len2 == 0)
03257
return;
03258
if (__len1 + __len2 == 2) {
03259
if (__comp(*__middle, *__first))
03260
iter_swap(__first, __middle);
03261
return;
03262 }
03263 _BidirectionalIter __first_cut = __first;
03264 _BidirectionalIter __second_cut = __middle;
03265 _Distance __len11 = 0;
03266 _Distance __len22 = 0;
03267
if (__len1 > __len2) {
03268 __len11 = __len1 / 2;
03269
advance(__first_cut, __len11);
03270 __second_cut =
lower_bound(__middle, __last, *__first_cut, __comp);
03271 __len22 =
distance(__middle, __second_cut);
03272 }
03273
else {
03274 __len22 = __len2 / 2;
03275
advance(__second_cut, __len22);
03276 __first_cut =
upper_bound(__first, __middle, *__second_cut, __comp);
03277 __len11 =
distance(__first, __first_cut);
03278 }
03279
rotate(__first_cut, __middle, __second_cut);
03280 _BidirectionalIter __new_middle = __first_cut;
03281
advance(__new_middle,
distance(__middle, __second_cut));
03282 __merge_without_buffer(__first, __first_cut, __new_middle,
03283 __len11, __len22, __comp);
03284 __merge_without_buffer(__new_middle, __second_cut, __last,
03285 __len1 - __len11, __len2 - __len22, __comp);
03286 }
03287
03293
template<
typename _BidirectionalIter1,
typename _BidirectionalIter2,
03294
typename _Distance>
03295 _BidirectionalIter1
03296 __rotate_adaptive(_BidirectionalIter1 __first,
03297 _BidirectionalIter1 __middle,
03298 _BidirectionalIter1 __last,
03299 _Distance __len1, _Distance __len2,
03300 _BidirectionalIter2 __buffer,
03301 _Distance __buffer_size)
03302 {
03303 _BidirectionalIter2 __buffer_end;
03304
if (__len1 > __len2 && __len2 <= __buffer_size) {
03305 __buffer_end =
copy(__middle, __last, __buffer);
03306
copy_backward(__first, __middle, __last);
03307
return copy(__buffer, __buffer_end, __first);
03308 }
03309
else if (__len1 <= __buffer_size) {
03310 __buffer_end =
copy(__first, __middle, __buffer);
03311
copy(__middle, __last, __first);
03312
return copy_backward(__buffer, __buffer_end, __last);
03313 }
03314
else {
03315
rotate(__first, __middle, __last);
03316
advance(__first,
distance(__middle, __last));
03317
return __first;
03318 }
03319 }
03320
03326
template<
typename _BidirectionalIter1,
typename _BidirectionalIter2,
03327
typename _BidirectionalIter3>
03328 _BidirectionalIter3
03329 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
03330 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
03331 _BidirectionalIter3 __result)
03332 {
03333
if (__first1 == __last1)
03334
return copy_backward(__first2, __last2, __result);
03335
if (__first2 == __last2)
03336
return copy_backward(__first1, __last1, __result);
03337 --__last1;
03338 --__last2;
03339
while (
true) {
03340
if (*__last2 < *__last1) {
03341 *--__result = *__last1;
03342
if (__first1 == __last1)
03343
return copy_backward(__first2, ++__last2, __result);
03344 --__last1;
03345 }
03346
else {
03347 *--__result = *__last2;
03348
if (__first2 == __last2)
03349
return copy_backward(__first1, ++__last1, __result);
03350 --__last2;
03351 }
03352 }
03353 }
03354
03360
template<
typename _BidirectionalIter1,
typename _BidirectionalIter2,
03361
typename _BidirectionalIter3,
typename _Compare>
03362 _BidirectionalIter3
03363 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
03364 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
03365 _BidirectionalIter3 __result,
03366 _Compare __comp)
03367 {
03368
if (__first1 == __last1)
03369
return copy_backward(__first2, __last2, __result);
03370
if (__first2 == __last2)
03371
return copy_backward(__first1, __last1, __result);
03372 --__last1;
03373 --__last2;
03374
while (
true) {
03375
if (__comp(*__last2, *__last1)) {
03376 *--__result = *__last1;
03377
if (__first1 == __last1)
03378
return copy_backward(__first2, ++__last2, __result);
03379 --__last1;
03380 }
03381
else {
03382 *--__result = *__last2;
03383
if (__first2 == __last2)
03384
return copy_backward(__first1, ++__last1, __result);
03385 --__last2;
03386 }
03387 }
03388 }
03389
03395
template<
typename _B
idirectionalIter,
typename _Distance,
typename _Po
inter>
03396
void
03397 __merge_adaptive(_BidirectionalIter __first,
03398 _BidirectionalIter __middle,
03399 _BidirectionalIter __last,
03400 _Distance __len1, _Distance __len2,
03401 _Pointer __buffer, _Distance __buffer_size)
03402 {
03403
if (__len1 <= __len2 && __len1 <= __buffer_size) {
03404 _Pointer __buffer_end =
copy(__first, __middle, __buffer);
03405
merge(__buffer, __buffer_end, __middle, __last, __first);
03406 }
03407
else if (__len2 <= __buffer_size) {
03408 _Pointer __buffer_end =
copy(__middle, __last, __buffer);
03409 __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
03410 }
03411
else {
03412 _BidirectionalIter __first_cut = __first;
03413 _BidirectionalIter __second_cut = __middle;
03414 _Distance __len11 = 0;
03415 _Distance __len22 = 0;
03416
if (__len1 > __len2) {
03417 __len11 = __len1 / 2;
03418
advance(__first_cut, __len11);
03419 __second_cut =
lower_bound(__middle, __last, *__first_cut);
03420 __len22 =
distance(__middle, __second_cut);
03421 }
03422
else {
03423 __len22 = __len2 / 2;
03424
advance(__second_cut, __len22);
03425 __first_cut =
upper_bound(__first, __middle, *__second_cut);
03426 __len11 =
distance(__first, __first_cut);
03427 }
03428 _BidirectionalIter __new_middle =
03429 __rotate_adaptive(__first_cut, __middle, __second_cut,
03430 __len1 - __len11, __len22, __buffer,
03431 __buffer_size);
03432 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
03433 __len22, __buffer, __buffer_size);
03434 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
03435 __len2 - __len22, __buffer, __buffer_size);
03436 }
03437 }
03438
03444
template<
typename _BidirectionalIter,
typename _Distance,
typename _Pointer,
03445
typename _Compare>
03446
void
03447 __merge_adaptive(_BidirectionalIter __first,
03448 _BidirectionalIter __middle,
03449 _BidirectionalIter __last,
03450 _Distance __len1, _Distance __len2,
03451 _Pointer __buffer, _Distance __buffer_size,
03452 _Compare __comp)
03453 {
03454
if (__len1 <= __len2 && __len1 <= __buffer_size) {
03455 _Pointer __buffer_end =
copy(__first, __middle, __buffer);
03456
merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
03457 }
03458
else if (__len2 <= __buffer_size) {
03459 _Pointer __buffer_end =
copy(__middle, __last, __buffer);
03460 __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
03461 __comp);
03462 }
03463
else {
03464 _BidirectionalIter __first_cut = __first;
03465 _BidirectionalIter __second_cut = __middle;
03466 _Distance __len11 = 0;
03467 _Distance __len22 = 0;
03468
if (__len1 > __len2) {
03469 __len11 = __len1 / 2;
03470
advance(__first_cut, __len11);
03471 __second_cut =
lower_bound(__middle, __last, *__first_cut, __comp);
03472 __len22 =
distance(__middle, __second_cut);
03473 }
03474
else {
03475 __len22 = __len2 / 2;
03476
advance(__second_cut, __len22);
03477 __first_cut =
upper_bound(__first, __middle, *__second_cut, __comp);
03478 __len11 =
distance(__first, __first_cut);
03479 }
03480 _BidirectionalIter __new_middle =
03481 __rotate_adaptive(__first_cut, __middle, __second_cut,
03482 __len1 - __len11, __len22, __buffer,
03483 __buffer_size);
03484 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
03485 __len22, __buffer, __buffer_size, __comp);
03486 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
03487 __len2 - __len22, __buffer, __buffer_size, __comp);
03488 }
03489 }
03490
03508
template<
typename _B
idirectionalIter>
03509
void
03510
inplace_merge(_BidirectionalIter __first,
03511 _BidirectionalIter __middle,
03512 _BidirectionalIter __last)
03513 {
03514
typedef typename iterator_traits<_BidirectionalIter>::value_type
03515 _ValueType;
03516
typedef typename iterator_traits<_BidirectionalIter>::difference_type
03517 _DistanceType;
03518
03519
03520 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
03521 _BidirectionalIter>)
03522 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
03523
03524
if (__first == __middle || __middle == __last)
03525
return;
03526
03527 _DistanceType __len1 =
distance(__first, __middle);
03528 _DistanceType __len2 =
distance(__middle, __last);
03529
03530 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
03531
if (__buf.begin() == 0)
03532 __merge_without_buffer(__first, __middle, __last, __len1, __len2);
03533
else
03534 __merge_adaptive(__first, __middle, __last, __len1, __len2,
03535 __buf.begin(), _DistanceType(__buf.size()));
03536 }
03537
03559
template<
typename _B
idirectionalIter,
typename _Compare>
03560
void
03561
inplace_merge(_BidirectionalIter __first,
03562 _BidirectionalIter __middle,
03563 _BidirectionalIter __last,
03564 _Compare __comp)
03565 {
03566
typedef typename iterator_traits<_BidirectionalIter>::value_type
03567 _ValueType;
03568
typedef typename iterator_traits<_BidirectionalIter>::difference_type
03569 _DistanceType;
03570
03571
03572 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
03573 _BidirectionalIter>)
03574 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03575 _ValueType, _ValueType>)
03576
03577
if (__first == __middle || __middle == __last)
03578
return;
03579
03580 _DistanceType __len1 =
distance(__first, __middle);
03581 _DistanceType __len2 =
distance(__middle, __last);
03582
03583 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
03584
if (__buf.begin() == 0)
03585 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
03586
else
03587 __merge_adaptive(__first, __middle, __last, __len1, __len2,
03588 __buf.begin(), _DistanceType(__buf.size()),
03589 __comp);
03590 }
03591
03592
03593
03594
03595
03596
03597
template<
typename _InputIter1,
typename _InputIter2>
03598
bool
03599 includes(_InputIter1 __first1, _InputIter1 __last1,
03600 _InputIter2 __first2, _InputIter2 __last2)
03601 {
03602
03603 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03604 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03605 __glibcpp_function_requires(_SameTypeConcept<
03606 typename iterator_traits<_InputIter1>::value_type,
03607 typename iterator_traits<_InputIter2>::value_type>)
03608 __glibcpp_function_requires(_LessThanComparableConcept<
03609 typename iterator_traits<_InputIter1>::value_type>)
03610
03611 while (__first1 != __last1 && __first2 != __last2)
03612 if (*__first2 < *__first1)
03613 return false;
03614 else if(*__first1 < *__first2)
03615 ++__first1;
03616 else
03617 ++__first1, ++__first2;
03618
03619 return __first2 == __last2;
03620 }
03621
03622 template<typename _InputIter1, typename _InputIter2, typename _Compare>
03623
bool
03624 includes(_InputIter1 __first1, _InputIter1 __last1,
03625 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
03626 {
03627
03628 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03629 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03630 __glibcpp_function_requires(_SameTypeConcept<
03631 typename iterator_traits<_InputIter1>::value_type,
03632 typename iterator_traits<_InputIter2>::value_type>)
03633 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03634 typename iterator_traits<_InputIter1>::value_type,
03635 typename iterator_traits<_InputIter2>::value_type>)
03636
03637 while (__first1 != __last1 && __first2 != __last2)
03638 if (__comp(*__first2, *__first1))
03639 return false;
03640 else if(__comp(*__first1, *__first2))
03641 ++__first1;
03642 else
03643 ++__first1, ++__first2;
03644
03645 return __first2 == __last2;
03646 }
03647
03648 template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
03649 _OutputIter
03650 set_union(_InputIter1 __first1, _InputIter1 __last1,
03651 _InputIter2 __first2, _InputIter2 __last2,
03652 _OutputIter __result)
03653 {
03654
03655 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03656 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03657 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03658 typename iterator_traits<_InputIter1>::value_type>)
03659 __glibcpp_function_requires(_SameTypeConcept<
03660 typename iterator_traits<_InputIter1>::value_type,
03661 typename iterator_traits<_InputIter2>::value_type>)
03662 __glibcpp_function_requires(_LessThanComparableConcept<
03663 typename iterator_traits<_InputIter1>::value_type>)
03664
03665 while (__first1 != __last1 && __first2 != __last2) {
03666
if (*__first1 < *__first2) {
03667 *__result = *__first1;
03668 ++__first1;
03669 }
03670
else if (*__first2 < *__first1) {
03671 *__result = *__first2;
03672 ++__first2;
03673 }
03674
else {
03675 *__result = *__first1;
03676 ++__first1;
03677 ++__first2;
03678 }
03679 ++__result;
03680 }
03681
return copy(__first2, __last2,
copy(__first1, __last1, __result));
03682 }
03683
03684
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter,
03685
typename _Compare>
03686 _OutputIter
03687 set_union(_InputIter1 __first1, _InputIter1 __last1,
03688 _InputIter2 __first2, _InputIter2 __last2,
03689 _OutputIter __result, _Compare __comp)
03690 {
03691
03692 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03693 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03694 __glibcpp_function_requires(_SameTypeConcept<
03695 typename iterator_traits<_InputIter1>::value_type,
03696 typename iterator_traits<_InputIter2>::value_type>)
03697 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03698 typename iterator_traits<_InputIter1>::value_type>)
03699 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03700 typename iterator_traits<_InputIter1>::value_type,
03701 typename iterator_traits<_InputIter2>::value_type>)
03702
03703 while (__first1 != __last1 && __first2 != __last2) {
03704
if (__comp(*__first1, *__first2)) {
03705 *__result = *__first1;
03706 ++__first1;
03707 }
03708
else if (__comp(*__first2, *__first1)) {
03709 *__result = *__first2;
03710 ++__first2;
03711 }
03712
else {
03713 *__result = *__first1;
03714 ++__first1;
03715 ++__first2;
03716 }
03717 ++__result;
03718 }
03719
return copy(__first2, __last2,
copy(__first1, __last1, __result));
03720 }
03721
03722
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter>
03723 _OutputIter
03724 set_intersection(_InputIter1 __first1, _InputIter1 __last1,
03725 _InputIter2 __first2, _InputIter2 __last2,
03726 _OutputIter __result)
03727 {
03728
03729 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03730 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03731 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03732 typename iterator_traits<_InputIter1>::value_type>)
03733 __glibcpp_function_requires(_SameTypeConcept<
03734 typename iterator_traits<_InputIter1>::value_type,
03735 typename iterator_traits<_InputIter2>::value_type>)
03736 __glibcpp_function_requires(_LessThanComparableConcept<
03737 typename iterator_traits<_InputIter1>::value_type>)
03738
03739 while (__first1 != __last1 && __first2 != __last2)
03740 if (*__first1 < *__first2)
03741 ++__first1;
03742 else if (*__first2 < *__first1)
03743 ++__first2;
03744 else {
03745 *__result = *__first1;
03746 ++__first1;
03747 ++__first2;
03748 ++__result;
03749 }
03750
return __result;
03751 }
03752
03753
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter,
03754
typename _Compare>
03755 _OutputIter
03756 set_intersection(_InputIter1 __first1, _InputIter1 __last1,
03757 _InputIter2 __first2, _InputIter2 __last2,
03758 _OutputIter __result, _Compare __comp)
03759 {
03760
03761 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03762 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03763 __glibcpp_function_requires(_SameTypeConcept<
03764 typename iterator_traits<_InputIter1>::value_type,
03765 typename iterator_traits<_InputIter2>::value_type>)
03766 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03767 typename iterator_traits<_InputIter1>::value_type>)
03768 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03769 typename iterator_traits<_InputIter1>::value_type,
03770 typename iterator_traits<_InputIter2>::value_type>)
03771
03772 while (__first1 != __last1 && __first2 != __last2)
03773 if (__comp(*__first1, *__first2))
03774 ++__first1;
03775 else if (__comp(*__first2, *__first1))
03776 ++__first2;
03777 else {
03778 *__result = *__first1;
03779 ++__first1;
03780 ++__first2;
03781 ++__result;
03782 }
03783
return __result;
03784 }
03785
03786
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter>
03787 _OutputIter
03788 set_difference(_InputIter1 __first1, _InputIter1 __last1,
03789 _InputIter2 __first2, _InputIter2 __last2,
03790 _OutputIter __result)
03791 {
03792
03793 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03794 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03795 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03796 typename iterator_traits<_InputIter1>::value_type>)
03797 __glibcpp_function_requires(_SameTypeConcept<
03798 typename iterator_traits<_InputIter1>::value_type,
03799 typename iterator_traits<_InputIter2>::value_type>)
03800 __glibcpp_function_requires(_LessThanComparableConcept<
03801 typename iterator_traits<_InputIter1>::value_type>)
03802
03803 while (__first1 != __last1 && __first2 != __last2)
03804 if (*__first1 < *__first2) {
03805 *__result = *__first1;
03806 ++__first1;
03807 ++__result;
03808 }
03809
else if (*__first2 < *__first1)
03810 ++__first2;
03811
else {
03812 ++__first1;
03813 ++__first2;
03814 }
03815
return copy(__first1, __last1, __result);
03816 }
03817
03818
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter,
03819
typename _Compare>
03820 _OutputIter
03821 set_difference(_InputIter1 __first1, _InputIter1 __last1,
03822 _InputIter2 __first2, _InputIter2 __last2,
03823 _OutputIter __result, _Compare __comp)
03824 {
03825
03826 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03827 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03828 __glibcpp_function_requires(_SameTypeConcept<
03829 typename iterator_traits<_InputIter1>::value_type,
03830 typename iterator_traits<_InputIter2>::value_type>)
03831 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03832 typename iterator_traits<_InputIter1>::value_type>)
03833 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03834 typename iterator_traits<_InputIter1>::value_type,
03835 typename iterator_traits<_InputIter2>::value_type>)
03836
03837 while (__first1 != __last1 && __first2 != __last2)
03838 if (__comp(*__first1, *__first2)) {
03839 *__result = *__first1;
03840 ++__first1;
03841 ++__result;
03842 }
03843
else if (__comp(*__first2, *__first1))
03844 ++__first2;
03845
else {
03846 ++__first1;
03847 ++__first2;
03848 }
03849
return copy(__first1, __last1, __result);
03850 }
03851
03852
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter>
03853 _OutputIter
03854 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
03855 _InputIter2 __first2, _InputIter2 __last2,
03856 _OutputIter __result)
03857 {
03858
03859 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03860 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03861 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03862 typename iterator_traits<_InputIter1>::value_type>)
03863 __glibcpp_function_requires(_SameTypeConcept<
03864 typename iterator_traits<_InputIter1>::value_type,
03865 typename iterator_traits<_InputIter2>::value_type>)
03866 __glibcpp_function_requires(_LessThanComparableConcept<
03867 typename iterator_traits<_InputIter1>::value_type>)
03868
03869 while (__first1 != __last1 && __first2 != __last2)
03870 if (*__first1 < *__first2) {
03871 *__result = *__first1;
03872 ++__first1;
03873 ++__result;
03874 }
03875
else if (*__first2 < *__first1) {
03876 *__result = *__first2;
03877 ++__first2;
03878 ++__result;
03879 }
03880
else {
03881 ++__first1;
03882 ++__first2;
03883 }
03884
return copy(__first2, __last2,
copy(__first1, __last1, __result));
03885 }
03886
03887
template<
typename _InputIter1,
typename _InputIter2,
typename _OutputIter,
03888
typename _Compare>
03889 _OutputIter
03890 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
03891 _InputIter2 __first2, _InputIter2 __last2,
03892 _OutputIter __result,
03893 _Compare __comp)
03894 {
03895
03896 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
03897 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
03898 __glibcpp_function_requires(_SameTypeConcept<
03899 typename iterator_traits<_InputIter1>::value_type,
03900 typename iterator_traits<_InputIter2>::value_type>)
03901 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03902 typename iterator_traits<_InputIter1>::value_type>)
03903 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03904 typename iterator_traits<_InputIter1>::value_type,
03905 typename iterator_traits<_InputIter2>::value_type>)
03906
03907 while (__first1 != __last1 && __first2 != __last2)
03908 if (__comp(*__first1, *__first2)) {
03909 *__result = *__first1;
03910 ++__first1;
03911 ++__result;
03912 }
03913
else if (__comp(*__first2, *__first1)) {
03914 *__result = *__first2;
03915 ++__first2;
03916 ++__result;
03917 }
03918
else {
03919 ++__first1;
03920 ++__first2;
03921 }
03922
return copy(__first2, __last2,
copy(__first1, __last1, __result));
03923 }
03924
03925
03926
03927
03928
template<
typename _ForwardIter>
03929 _ForwardIter
03930 max_element(_ForwardIter __first, _ForwardIter __last)
03931 {
03932
03933 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03934 __glibcpp_function_requires(_LessThanComparableConcept<
03935 typename iterator_traits<_ForwardIter>::value_type>)
03936
03937 if (__first == __last) return __first;
03938 _ForwardIter __result = __first;
03939 while (++__first != __last)
03940 if (*__result < *__first)
03941 __result = __first;
03942 return __result;
03943 }
03944
03945 template<typename _ForwardIter, typename _Compare>
03946 _ForwardIter
03947 max_element(_ForwardIter __first, _ForwardIter __last,
03948 _Compare __comp)
03949 {
03950
03951 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03952 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03953 typename iterator_traits<_ForwardIter>::value_type,
03954 typename iterator_traits<_ForwardIter>::value_type>)
03955
03956 if (__first == __last) return __first;
03957 _ForwardIter __result = __first;
03958 while (++__first != __last)
03959 if (__comp(*__result, *__first)) __result = __first;
03960 return __result;
03961 }
03962
03963 template<typename _ForwardIter>
03964 _ForwardIter
03965 min_element(_ForwardIter __first, _ForwardIter __last)
03966 {
03967
03968 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03969 __glibcpp_function_requires(_LessThanComparableConcept<
03970 typename iterator_traits<_ForwardIter>::value_type>)
03971
03972 if (__first == __last) return __first;
03973 _ForwardIter __result = __first;
03974 while (++__first != __last)
03975 if (*__first < *__result)
03976 __result = __first;
03977 return __result;
03978 }
03979
03980 template<typename _ForwardIter, typename _Compare>
03981 _ForwardIter
03982 min_element(_ForwardIter __first, _ForwardIter __last,
03983 _Compare __comp)
03984 {
03985
03986 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
03987 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03988 typename iterator_traits<_ForwardIter>::value_type,
03989 typename iterator_traits<_ForwardIter>::value_type>)
03990
03991 if (__first == __last) return __first;
03992 _ForwardIter __result = __first;
03993 while (++__first != __last)
03994 if (__comp(*__first, *__result))
03995 __result = __first;
03996 return __result;
03997 }
03998
03999
04000
04001
04002 template<typename _BidirectionalIter>
04003
bool
04004 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
04005 {
04006
04007 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04008 __glibcpp_function_requires(_LessThanComparableConcept<
04009 typename iterator_traits<_BidirectionalIter>::value_type>)
04010
04011 if (__first == __last)
04012 return false;
04013 _BidirectionalIter __i = __first;
04014 ++__i;
04015 if (__i == __last)
04016 return false;
04017 __i = __last;
04018 --__i;
04019
04020 for(;;) {
04021 _BidirectionalIter __ii = __i;
04022 --__i;
04023
if (*__i < *__ii) {
04024 _BidirectionalIter __j = __last;
04025
while (!(*__i < *--__j))
04026 {}
04027
iter_swap(__i, __j);
04028
reverse(__ii, __last);
04029
return true;
04030 }
04031
if (__i == __first) {
04032
reverse(__first, __last);
04033
return false;
04034 }
04035 }
04036 }
04037
04038
template<
typename _B
idirectionalIter,
typename _Compare>
04039
bool
04040 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
04041 _Compare __comp)
04042 {
04043
04044 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04045 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
04046 typename iterator_traits<_BidirectionalIter>::value_type,
04047 typename iterator_traits<_BidirectionalIter>::value_type>)
04048
04049 if (__first == __last)
04050 return false;
04051 _BidirectionalIter __i = __first;
04052 ++__i;
04053 if (__i == __last)
04054 return false;
04055 __i = __last;
04056 --__i;
04057
04058 for(;;) {
04059 _BidirectionalIter __ii = __i;
04060 --__i;
04061
if (__comp(*__i, *__ii)) {
04062 _BidirectionalIter __j = __last;
04063
while (!__comp(*__i, *--__j))
04064 {}
04065
iter_swap(__i, __j);
04066
reverse(__ii, __last);
04067
return true;
04068 }
04069
if (__i == __first) {
04070
reverse(__first, __last);
04071
return false;
04072 }
04073 }
04074 }
04075
04076
template<
typename _B
idirectionalIter>
04077
bool
04078 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
04079 {
04080
04081 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04082 __glibcpp_function_requires(_LessThanComparableConcept<
04083 typename iterator_traits<_BidirectionalIter>::value_type>)
04084
04085 if (__first == __last)
04086 return false;
04087 _BidirectionalIter __i = __first;
04088 ++__i;
04089 if (__i == __last)
04090 return false;
04091 __i = __last;
04092 --__i;
04093
04094 for(;;) {
04095 _BidirectionalIter __ii = __i;
04096 --__i;
04097
if (*__ii < *__i) {
04098 _BidirectionalIter __j = __last;
04099
while (!(*--__j < *__i))
04100 {}
04101
iter_swap(__i, __j);
04102
reverse(__ii, __last);
04103
return true;
04104 }
04105
if (__i == __first) {
04106
reverse(__first, __last);
04107
return false;
04108 }
04109 }
04110 }
04111
04112
template<
typename _B
idirectionalIter,
typename _Compare>
04113
bool
04114 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
04115 _Compare __comp)
04116 {
04117
04118 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
04119 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
04120 typename iterator_traits<_BidirectionalIter>::value_type,
04121 typename iterator_traits<_BidirectionalIter>::value_type>)
04122
04123 if (__first == __last)
04124 return false;
04125 _BidirectionalIter __i = __first;
04126 ++__i;
04127 if (__i == __last)
04128 return false;
04129 __i = __last;
04130 --__i;
04131
04132 for(;;) {
04133 _BidirectionalIter __ii = __i;
04134 --__i;
04135
if (__comp(*__ii, *__i)) {
04136 _BidirectionalIter __j = __last;
04137
while (!__comp(*--__j, *__i))
04138 {}
04139
iter_swap(__i, __j);
04140
reverse(__ii, __last);
04141
return true;
04142 }
04143
if (__i == __first) {
04144
reverse(__first, __last);
04145
return false;
04146 }
04147 }
04148 }
04149
04150
04151
04152
template<
typename _InputIter,
typename _ForwardIter>
04153 _InputIter
04154 find_first_of(_InputIter __first1, _InputIter __last1,
04155 _ForwardIter __first2, _ForwardIter __last2)
04156 {
04157
04158 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
04159 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
04160 __glibcpp_function_requires(_EqualOpConcept<
04161 typename iterator_traits<_InputIter>::value_type,
04162 typename iterator_traits<_ForwardIter>::value_type>)
04163
04164 for ( ; __first1 != __last1; ++__first1)
04165 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
04166 if (*__first1 == *__iter)
04167 return __first1;
04168 return __last1;
04169 }
04170
04171 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
04172 _InputIter
04173 find_first_of(_InputIter __first1, _InputIter __last1,
04174 _ForwardIter __first2, _ForwardIter __last2,
04175 _BinaryPredicate __comp)
04176 {
04177
04178 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
04179 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
04180 __glibcpp_function_requires(_EqualOpConcept<
04181 typename iterator_traits<_InputIter>::value_type,
04182 typename iterator_traits<_ForwardIter>::value_type>)
04183 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04184 typename iterator_traits<_InputIter>::value_type,
04185 typename iterator_traits<_ForwardIter>::value_type>)
04186
04187 for ( ; __first1 != __last1; ++__first1)
04188 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
04189 if (__comp(*__first1, *__iter))
04190 return __first1;
04191 return __last1;
04192 }
04193
04194
04195
04196
04197
04198
04199
04200
04201 template<typename _ForwardIter1, typename _ForwardIter2>
04202 _ForwardIter1
04203 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04204 _ForwardIter2 __first2, _ForwardIter2 __last2,
04205 forward_iterator_tag, forward_iterator_tag)
04206 {
04207
if (__first2 == __last2)
04208
return __last1;
04209
else {
04210 _ForwardIter1 __result = __last1;
04211
while (1) {
04212 _ForwardIter1 __new_result
04213 =
search(__first1, __last1, __first2, __last2);
04214
if (__new_result == __last1)
04215
return __result;
04216
else {
04217 __result = __new_result;
04218 __first1 = __new_result;
04219 ++__first1;
04220 }
04221 }
04222 }
04223 }
04224
04225
template<
typename _ForwardIter1,
typename _ForwardIter2,
04226
typename _BinaryPredicate>
04227 _ForwardIter1
04228 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04229 _ForwardIter2 __first2, _ForwardIter2 __last2,
04230 forward_iterator_tag, forward_iterator_tag,
04231 _BinaryPredicate __comp)
04232 {
04233
if (__first2 == __last2)
04234
return __last1;
04235
else {
04236 _ForwardIter1 __result = __last1;
04237
while (1) {
04238 _ForwardIter1 __new_result
04239 =
search(__first1, __last1, __first2, __last2, __comp);
04240
if (__new_result == __last1)
04241
return __result;
04242
else {
04243 __result = __new_result;
04244 __first1 = __new_result;
04245 ++__first1;
04246 }
04247 }
04248 }
04249 }
04250
04251
04252
template<
typename _B
idirectionalIter1,
typename _B
idirectionalIter2>
04253 _BidirectionalIter1
04254 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
04255 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
04256
bidirectional_iterator_tag,
bidirectional_iterator_tag)
04257 {
04258
04259 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
04260 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
04261
04262 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
04263 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
04264
04265 _RevIter1 __rlast1(__first1);
04266 _RevIter2 __rlast2(__first2);
04267 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
04268 _RevIter2(__last2), __rlast2);
04269
04270 if (__rresult == __rlast1)
04271 return __last1;
04272 else {
04273 _BidirectionalIter1 __result = __rresult.base();
04274
advance(__result, -
distance(__first2, __last2));
04275
return __result;
04276 }
04277 }
04278
04279
template<
typename _BidirectionalIter1,
typename _BidirectionalIter2,
04280
typename _BinaryPredicate>
04281 _BidirectionalIter1
04282 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
04283 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
04284
bidirectional_iterator_tag,
bidirectional_iterator_tag,
04285 _BinaryPredicate __comp)
04286 {
04287
04288 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
04289 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
04290
04291 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
04292 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
04293
04294 _RevIter1 __rlast1(__first1);
04295 _RevIter2 __rlast2(__first2);
04296 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
04297 _RevIter2(__last2), __rlast2,
04298 __comp);
04299
04300 if (__rresult == __rlast1)
04301 return __last1;
04302 else {
04303 _BidirectionalIter1 __result = __rresult.base();
04304
advance(__result, -
distance(__first2, __last2));
04305
return __result;
04306 }
04307 }
04308
04309
04310
04311
template<
typename _ForwardIter1,
typename _ForwardIter2>
04312
inline _ForwardIter1
04313 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04314 _ForwardIter2 __first2, _ForwardIter2 __last2)
04315 {
04316
04317 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
04318 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
04319 __glibcpp_function_requires(_EqualOpConcept<
04320 typename iterator_traits<_ForwardIter1>::value_type,
04321 typename iterator_traits<_ForwardIter2>::value_type>)
04322
04323 return __find_end(__first1, __last1, __first2, __last2,
04324 __iterator_category(__first1),
04325 __iterator_category(__first2));
04326 }
04327
04328 template<typename _ForwardIter1, typename _ForwardIter2,
04329 typename _BinaryPredicate>
04330 inline _ForwardIter1
04331 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
04332 _ForwardIter2 __first2, _ForwardIter2 __last2,
04333 _BinaryPredicate __comp)
04334 {
04335
04336 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
04337 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
04338 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04339 typename iterator_traits<_ForwardIter1>::value_type,
04340 typename iterator_traits<_ForwardIter2>::value_type>)
04341
04342 return __find_end(__first1, __last1, __first2, __last2,
04343 __iterator_category(__first1),
04344 __iterator_category(__first2),
04345 __comp);
04346 }
04347
04348 }
04349
04350 #endif
04351