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