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