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