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 __move_merge_backward(_BidirectionalIterator1 __first1,
02724 _BidirectionalIterator1 __last1,
02725 _BidirectionalIterator2 __first2,
02726 _BidirectionalIterator2 __last2,
02727 _BidirectionalIterator3 __result)
02728 {
02729 if (__first1 == __last1)
02730 return _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
02731 if (__first2 == __last2)
02732 return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result);
02733 --__last1;
02734 --__last2;
02735 while (true)
02736 {
02737 if (*__last2 < *__last1)
02738 {
02739 *--__result = _GLIBCXX_MOVE(*__last1);
02740 if (__first1 == __last1)
02741 return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
02742 --__last1;
02743 }
02744 else
02745 {
02746 *--__result = _GLIBCXX_MOVE(*__last2);
02747 if (__first2 == __last2)
02748 return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result);
02749 --__last2;
02750 }
02751 }
02752 }
02753
02754
02755 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02756 typename _BidirectionalIterator3, typename _Compare>
02757 _BidirectionalIterator3
02758 __move_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 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
02767 if (__first2 == __last2)
02768 return _GLIBCXX_MOVE_BACKWARD3(__first1, __last1, __result);
02769 --__last1;
02770 --__last2;
02771 while (true)
02772 {
02773 if (__comp(*__last2, *__last1))
02774 {
02775 *--__result = _GLIBCXX_MOVE(*__last1);
02776 if (__first1 == __last1)
02777 return _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
02778 --__last1;
02779 }
02780 else
02781 {
02782 *--__result = _GLIBCXX_MOVE(*__last2);
02783 if (__first2 == __last2)
02784 return _GLIBCXX_MOVE_BACKWARD3(__first1, ++__last1, __result);
02785 --__last2;
02786 }
02787 }
02788 }
02789
02790
02791 template<typename _InputIterator1, typename _InputIterator2,
02792 typename _OutputIterator>
02793 _OutputIterator
02794 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
02795 _InputIterator2 __first2, _InputIterator2 __last2,
02796 _OutputIterator __result)
02797 {
02798 while (__first1 != __last1 && __first2 != __last2)
02799 {
02800 if (*__first2 < *__first1)
02801 {
02802 *__result = _GLIBCXX_MOVE(*__first2);
02803 ++__first2;
02804 }
02805 else
02806 {
02807 *__result = _GLIBCXX_MOVE(*__first1);
02808 ++__first1;
02809 }
02810 ++__result;
02811 }
02812 return _GLIBCXX_MOVE3(__first2, __last2,
02813 _GLIBCXX_MOVE3(__first1, __last1,
02814 __result));
02815 }
02816
02817
02818 template<typename _InputIterator1, typename _InputIterator2,
02819 typename _OutputIterator, typename _Compare>
02820 _OutputIterator
02821 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
02822 _InputIterator2 __first2, _InputIterator2 __last2,
02823 _OutputIterator __result, _Compare __comp)
02824 {
02825 while (__first1 != __last1 && __first2 != __last2)
02826 {
02827 if (__comp(*__first2, *__first1))
02828 {
02829 *__result = _GLIBCXX_MOVE(*__first2);
02830 ++__first2;
02831 }
02832 else
02833 {
02834 *__result = _GLIBCXX_MOVE(*__first1);
02835 ++__first1;
02836 }
02837 ++__result;
02838 }
02839 return _GLIBCXX_MOVE3(__first2, __last2,
02840 _GLIBCXX_MOVE3(__first1, __last1,
02841 __result));
02842 }
02843
02844
02845
02846 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02847 typename _Distance>
02848 _BidirectionalIterator1
02849 __rotate_adaptive(_BidirectionalIterator1 __first,
02850 _BidirectionalIterator1 __middle,
02851 _BidirectionalIterator1 __last,
02852 _Distance __len1, _Distance __len2,
02853 _BidirectionalIterator2 __buffer,
02854 _Distance __buffer_size)
02855 {
02856 _BidirectionalIterator2 __buffer_end;
02857 if (__len1 > __len2 && __len2 <= __buffer_size)
02858 {
02859 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02860 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
02861 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
02862 }
02863 else if (__len1 <= __buffer_size)
02864 {
02865 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02866 _GLIBCXX_MOVE3(__middle, __last, __first);
02867 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
02868 }
02869 else
02870 {
02871 std::rotate(__first, __middle, __last);
02872 std::advance(__first, std::distance(__middle, __last));
02873 return __first;
02874 }
02875 }
02876
02877
02878 template<typename _BidirectionalIterator, typename _Distance,
02879 typename _Pointer>
02880 void
02881 __merge_adaptive(_BidirectionalIterator __first,
02882 _BidirectionalIterator __middle,
02883 _BidirectionalIterator __last,
02884 _Distance __len1, _Distance __len2,
02885 _Pointer __buffer, _Distance __buffer_size)
02886 {
02887 if (__len1 <= __len2 && __len1 <= __buffer_size)
02888 {
02889 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02890 std::__move_merge(__buffer, __buffer_end, __middle, __last, __first);
02891 }
02892 else if (__len2 <= __buffer_size)
02893 {
02894 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02895 std::__move_merge_backward(__first, __middle, __buffer,
02896 __buffer_end, __last);
02897 }
02898 else
02899 {
02900 _BidirectionalIterator __first_cut = __first;
02901 _BidirectionalIterator __second_cut = __middle;
02902 _Distance __len11 = 0;
02903 _Distance __len22 = 0;
02904 if (__len1 > __len2)
02905 {
02906 __len11 = __len1 / 2;
02907 std::advance(__first_cut, __len11);
02908 __second_cut = std::lower_bound(__middle, __last,
02909 *__first_cut);
02910 __len22 = std::distance(__middle, __second_cut);
02911 }
02912 else
02913 {
02914 __len22 = __len2 / 2;
02915 std::advance(__second_cut, __len22);
02916 __first_cut = std::upper_bound(__first, __middle,
02917 *__second_cut);
02918 __len11 = std::distance(__first, __first_cut);
02919 }
02920 _BidirectionalIterator __new_middle =
02921 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
02922 __len1 - __len11, __len22, __buffer,
02923 __buffer_size);
02924 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
02925 __len22, __buffer, __buffer_size);
02926 std::__merge_adaptive(__new_middle, __second_cut, __last,
02927 __len1 - __len11,
02928 __len2 - __len22, __buffer, __buffer_size);
02929 }
02930 }
02931
02932
02933 template<typename _BidirectionalIterator, typename _Distance,
02934 typename _Pointer, typename _Compare>
02935 void
02936 __merge_adaptive(_BidirectionalIterator __first,
02937 _BidirectionalIterator __middle,
02938 _BidirectionalIterator __last,
02939 _Distance __len1, _Distance __len2,
02940 _Pointer __buffer, _Distance __buffer_size,
02941 _Compare __comp)
02942 {
02943 if (__len1 <= __len2 && __len1 <= __buffer_size)
02944 {
02945 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02946 std::__move_merge(__buffer, __buffer_end, __middle, __last,
02947 __first, __comp);
02948 }
02949 else if (__len2 <= __buffer_size)
02950 {
02951 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02952 std::__move_merge_backward(__first, __middle, __buffer, __buffer_end,
02953 __last, __comp);
02954 }
02955 else
02956 {
02957 _BidirectionalIterator __first_cut = __first;
02958 _BidirectionalIterator __second_cut = __middle;
02959 _Distance __len11 = 0;
02960 _Distance __len22 = 0;
02961 if (__len1 > __len2)
02962 {
02963 __len11 = __len1 / 2;
02964 std::advance(__first_cut, __len11);
02965 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
02966 __comp);
02967 __len22 = std::distance(__middle, __second_cut);
02968 }
02969 else
02970 {
02971 __len22 = __len2 / 2;
02972 std::advance(__second_cut, __len22);
02973 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
02974 __comp);
02975 __len11 = std::distance(__first, __first_cut);
02976 }
02977 _BidirectionalIterator __new_middle =
02978 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
02979 __len1 - __len11, __len22, __buffer,
02980 __buffer_size);
02981 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
02982 __len22, __buffer, __buffer_size, __comp);
02983 std::__merge_adaptive(__new_middle, __second_cut, __last,
02984 __len1 - __len11,
02985 __len2 - __len22, __buffer,
02986 __buffer_size, __comp);
02987 }
02988 }
02989
02990
02991 template<typename _BidirectionalIterator, typename _Distance>
02992 void
02993 __merge_without_buffer(_BidirectionalIterator __first,
02994 _BidirectionalIterator __middle,
02995 _BidirectionalIterator __last,
02996 _Distance __len1, _Distance __len2)
02997 {
02998 if (__len1 == 0 || __len2 == 0)
02999 return;
03000 if (__len1 + __len2 == 2)
03001 {
03002 if (*__middle < *__first)
03003 std::iter_swap(__first, __middle);
03004 return;
03005 }
03006 _BidirectionalIterator __first_cut = __first;
03007 _BidirectionalIterator __second_cut = __middle;
03008 _Distance __len11 = 0;
03009 _Distance __len22 = 0;
03010 if (__len1 > __len2)
03011 {
03012 __len11 = __len1 / 2;
03013 std::advance(__first_cut, __len11);
03014 __second_cut = std::lower_bound(__middle, __last, *__first_cut);
03015 __len22 = std::distance(__middle, __second_cut);
03016 }
03017 else
03018 {
03019 __len22 = __len2 / 2;
03020 std::advance(__second_cut, __len22);
03021 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
03022 __len11 = std::distance(__first, __first_cut);
03023 }
03024 std::rotate(__first_cut, __middle, __second_cut);
03025 _BidirectionalIterator __new_middle = __first_cut;
03026 std::advance(__new_middle, std::distance(__middle, __second_cut));
03027 std::__merge_without_buffer(__first, __first_cut, __new_middle,
03028 __len11, __len22);
03029 std::__merge_without_buffer(__new_middle, __second_cut, __last,
03030 __len1 - __len11, __len2 - __len22);
03031 }
03032
03033
03034 template<typename _BidirectionalIterator, typename _Distance,
03035 typename _Compare>
03036 void
03037 __merge_without_buffer(_BidirectionalIterator __first,
03038 _BidirectionalIterator __middle,
03039 _BidirectionalIterator __last,
03040 _Distance __len1, _Distance __len2,
03041 _Compare __comp)
03042 {
03043 if (__len1 == 0 || __len2 == 0)
03044 return;
03045 if (__len1 + __len2 == 2)
03046 {
03047 if (__comp(*__middle, *__first))
03048 std::iter_swap(__first, __middle);
03049 return;
03050 }
03051 _BidirectionalIterator __first_cut = __first;
03052 _BidirectionalIterator __second_cut = __middle;
03053 _Distance __len11 = 0;
03054 _Distance __len22 = 0;
03055 if (__len1 > __len2)
03056 {
03057 __len11 = __len1 / 2;
03058 std::advance(__first_cut, __len11);
03059 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03060 __comp);
03061 __len22 = std::distance(__middle, __second_cut);
03062 }
03063 else
03064 {
03065 __len22 = __len2 / 2;
03066 std::advance(__second_cut, __len22);
03067 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03068 __comp);
03069 __len11 = std::distance(__first, __first_cut);
03070 }
03071 std::rotate(__first_cut, __middle, __second_cut);
03072 _BidirectionalIterator __new_middle = __first_cut;
03073 std::advance(__new_middle, std::distance(__middle, __second_cut));
03074 std::__merge_without_buffer(__first, __first_cut, __new_middle,
03075 __len11, __len22, __comp);
03076 std::__merge_without_buffer(__new_middle, __second_cut, __last,
03077 __len1 - __len11, __len2 - __len22, __comp);
03078 }
03079
03080
03081
03082
03083
03084
03085
03086
03087
03088
03089
03090
03091
03092
03093
03094
03095
03096
03097
03098 template<typename _BidirectionalIterator>
03099 void
03100 inplace_merge(_BidirectionalIterator __first,
03101 _BidirectionalIterator __middle,
03102 _BidirectionalIterator __last)
03103 {
03104 typedef typename iterator_traits<_BidirectionalIterator>::value_type
03105 _ValueType;
03106 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03107 _DistanceType;
03108
03109
03110 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03111 _BidirectionalIterator>)
03112 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03113 __glibcxx_requires_sorted(__first, __middle);
03114 __glibcxx_requires_sorted(__middle, __last);
03115
03116 if (__first == __middle || __middle == __last)
03117 return;
03118
03119 _DistanceType __len1 = std::distance(__first, __middle);
03120 _DistanceType __len2 = std::distance(__middle, __last);
03121
03122 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03123 __last);
03124 if (__buf.begin() == 0)
03125 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
03126 else
03127 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03128 __buf.begin(), _DistanceType(__buf.size()));
03129 }
03130
03131
03132
03133
03134
03135
03136
03137
03138
03139
03140
03141
03142
03143
03144
03145
03146
03147
03148
03149
03150
03151
03152
03153 template<typename _BidirectionalIterator, typename _Compare>
03154 void
03155 inplace_merge(_BidirectionalIterator __first,
03156 _BidirectionalIterator __middle,
03157 _BidirectionalIterator __last,
03158 _Compare __comp)
03159 {
03160 typedef typename iterator_traits<_BidirectionalIterator>::value_type
03161 _ValueType;
03162 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03163 _DistanceType;
03164
03165
03166 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03167 _BidirectionalIterator>)
03168 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03169 _ValueType, _ValueType>)
03170 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
03171 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
03172
03173 if (__first == __middle || __middle == __last)
03174 return;
03175
03176 const _DistanceType __len1 = std::distance(__first, __middle);
03177 const _DistanceType __len2 = std::distance(__middle, __last);
03178
03179 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03180 __last);
03181 if (__buf.begin() == 0)
03182 std::__merge_without_buffer(__first, __middle, __last, __len1,
03183 __len2, __comp);
03184 else
03185 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03186 __buf.begin(), _DistanceType(__buf.size()),
03187 __comp);
03188 }
03189
03190 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03191 typename _Distance>
03192 void
03193 __merge_sort_loop(_RandomAccessIterator1 __first,
03194 _RandomAccessIterator1 __last,
03195 _RandomAccessIterator2 __result,
03196 _Distance __step_size)
03197 {
03198 const _Distance __two_step = 2 * __step_size;
03199
03200 while (__last - __first >= __two_step)
03201 {
03202 __result = std::__move_merge(__first, __first + __step_size,
03203 __first + __step_size,
03204 __first + __two_step, __result);
03205 __first += __two_step;
03206 }
03207
03208 __step_size = std::min(_Distance(__last - __first), __step_size);
03209 std::__move_merge(__first, __first + __step_size,
03210 __first + __step_size, __last, __result);
03211 }
03212
03213 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03214 typename _Distance, typename _Compare>
03215 void
03216 __merge_sort_loop(_RandomAccessIterator1 __first,
03217 _RandomAccessIterator1 __last,
03218 _RandomAccessIterator2 __result, _Distance __step_size,
03219 _Compare __comp)
03220 {
03221 const _Distance __two_step = 2 * __step_size;
03222
03223 while (__last - __first >= __two_step)
03224 {
03225 __result = std::__move_merge(__first, __first + __step_size,
03226 __first + __step_size,
03227 __first + __two_step,
03228 __result, __comp);
03229 __first += __two_step;
03230 }
03231 __step_size = std::min(_Distance(__last - __first), __step_size);
03232
03233 std::__move_merge(__first,__first + __step_size,
03234 __first + __step_size, __last, __result, __comp);
03235 }
03236
03237 template<typename _RandomAccessIterator, typename _Distance>
03238 void
03239 __chunk_insertion_sort(_RandomAccessIterator __first,
03240 _RandomAccessIterator __last,
03241 _Distance __chunk_size)
03242 {
03243 while (__last - __first >= __chunk_size)
03244 {
03245 std::__insertion_sort(__first, __first + __chunk_size);
03246 __first += __chunk_size;
03247 }
03248 std::__insertion_sort(__first, __last);
03249 }
03250
03251 template<typename _RandomAccessIterator, typename _Distance,
03252 typename _Compare>
03253 void
03254 __chunk_insertion_sort(_RandomAccessIterator __first,
03255 _RandomAccessIterator __last,
03256 _Distance __chunk_size, _Compare __comp)
03257 {
03258 while (__last - __first >= __chunk_size)
03259 {
03260 std::__insertion_sort(__first, __first + __chunk_size, __comp);
03261 __first += __chunk_size;
03262 }
03263 std::__insertion_sort(__first, __last, __comp);
03264 }
03265
03266 enum { _S_chunk_size = 7 };
03267
03268 template<typename _RandomAccessIterator, typename _Pointer>
03269 void
03270 __merge_sort_with_buffer(_RandomAccessIterator __first,
03271 _RandomAccessIterator __last,
03272 _Pointer __buffer)
03273 {
03274 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03275 _Distance;
03276
03277 const _Distance __len = __last - __first;
03278 const _Pointer __buffer_last = __buffer + __len;
03279
03280 _Distance __step_size = _S_chunk_size;
03281 std::__chunk_insertion_sort(__first, __last, __step_size);
03282
03283 while (__step_size < __len)
03284 {
03285 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
03286 __step_size *= 2;
03287 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
03288 __step_size *= 2;
03289 }
03290 }
03291
03292 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
03293 void
03294 __merge_sort_with_buffer(_RandomAccessIterator __first,
03295 _RandomAccessIterator __last,
03296 _Pointer __buffer, _Compare __comp)
03297 {
03298 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03299 _Distance;
03300
03301 const _Distance __len = __last - __first;
03302 const _Pointer __buffer_last = __buffer + __len;
03303
03304 _Distance __step_size = _S_chunk_size;
03305 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
03306
03307 while (__step_size < __len)
03308 {
03309 std::__merge_sort_loop(__first, __last, __buffer,
03310 __step_size, __comp);
03311 __step_size *= 2;
03312 std::__merge_sort_loop(__buffer, __buffer_last, __first,
03313 __step_size, __comp);
03314 __step_size *= 2;
03315 }
03316 }
03317
03318 template<typename _RandomAccessIterator, typename _Pointer,
03319 typename _Distance>
03320 void
03321 __stable_sort_adaptive(_RandomAccessIterator __first,
03322 _RandomAccessIterator __last,
03323 _Pointer __buffer, _Distance __buffer_size)
03324 {
03325 const _Distance __len = (__last - __first + 1) / 2;
03326 const _RandomAccessIterator __middle = __first + __len;
03327 if (__len > __buffer_size)
03328 {
03329 std::__stable_sort_adaptive(__first, __middle,
03330 __buffer, __buffer_size);
03331 std::__stable_sort_adaptive(__middle, __last,
03332 __buffer, __buffer_size);
03333 }
03334 else
03335 {
03336 std::__merge_sort_with_buffer(__first, __middle, __buffer);
03337 std::__merge_sort_with_buffer(__middle, __last, __buffer);
03338 }
03339 std::__merge_adaptive(__first, __middle, __last,
03340 _Distance(__middle - __first),
03341 _Distance(__last - __middle),
03342 __buffer, __buffer_size);
03343 }
03344
03345 template<typename _RandomAccessIterator, typename _Pointer,
03346 typename _Distance, typename _Compare>
03347 void
03348 __stable_sort_adaptive(_RandomAccessIterator __first,
03349 _RandomAccessIterator __last,
03350 _Pointer __buffer, _Distance __buffer_size,
03351 _Compare __comp)
03352 {
03353 const _Distance __len = (__last - __first + 1) / 2;
03354 const _RandomAccessIterator __middle = __first + __len;
03355 if (__len > __buffer_size)
03356 {
03357 std::__stable_sort_adaptive(__first, __middle, __buffer,
03358 __buffer_size, __comp);
03359 std::__stable_sort_adaptive(__middle, __last, __buffer,
03360 __buffer_size, __comp);
03361 }
03362 else
03363 {
03364 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
03365 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
03366 }
03367 std::__merge_adaptive(__first, __middle, __last,
03368 _Distance(__middle - __first),
03369 _Distance(__last - __middle),
03370 __buffer, __buffer_size,
03371 __comp);
03372 }
03373
03374
03375 template<typename _RandomAccessIterator>
03376 void
03377 __inplace_stable_sort(_RandomAccessIterator __first,
03378 _RandomAccessIterator __last)
03379 {
03380 if (__last - __first < 15)
03381 {
03382 std::__insertion_sort(__first, __last);
03383 return;
03384 }
03385 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03386 std::__inplace_stable_sort(__first, __middle);
03387 std::__inplace_stable_sort(__middle, __last);
03388 std::__merge_without_buffer(__first, __middle, __last,
03389 __middle - __first,
03390 __last - __middle);
03391 }
03392
03393
03394 template<typename _RandomAccessIterator, typename _Compare>
03395 void
03396 __inplace_stable_sort(_RandomAccessIterator __first,
03397 _RandomAccessIterator __last, _Compare __comp)
03398 {
03399 if (__last - __first < 15)
03400 {
03401 std::__insertion_sort(__first, __last, __comp);
03402 return;
03403 }
03404 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03405 std::__inplace_stable_sort(__first, __middle, __comp);
03406 std::__inplace_stable_sort(__middle, __last, __comp);
03407 std::__merge_without_buffer(__first, __middle, __last,
03408 __middle - __first,
03409 __last - __middle,
03410 __comp);
03411 }
03412
03413
03414
03415
03416
03417
03418
03419
03420
03421
03422
03423
03424
03425
03426
03427
03428
03429
03430
03431
03432
03433
03434
03435
03436 template<typename _InputIterator1, typename _InputIterator2>
03437 bool
03438 includes(_InputIterator1 __first1, _InputIterator1 __last1,
03439 _InputIterator2 __first2, _InputIterator2 __last2)
03440 {
03441 typedef typename iterator_traits<_InputIterator1>::value_type
03442 _ValueType1;
03443 typedef typename iterator_traits<_InputIterator2>::value_type
03444 _ValueType2;
03445
03446
03447 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03448 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03449 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
03450 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
03451 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
03452 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
03453
03454 while (__first1 != __last1 && __first2 != __last2)
03455 if (*__first2 < *__first1)
03456 return false;
03457 else if(*__first1 < *__first2)
03458 ++__first1;
03459 else
03460 ++__first1, ++__first2;
03461
03462 return __first2 == __last2;
03463 }
03464
03465
03466
03467
03468
03469
03470
03471
03472
03473
03474
03475
03476
03477
03478
03479
03480
03481
03482
03483
03484
03485 template<typename _InputIterator1, typename _InputIterator2,
03486 typename _Compare>
03487 bool
03488 includes(_InputIterator1 __first1, _InputIterator1 __last1,
03489 _InputIterator2 __first2, _InputIterator2 __last2,
03490 _Compare __comp)
03491 {
03492 typedef typename iterator_traits<_InputIterator1>::value_type
03493 _ValueType1;
03494 typedef typename iterator_traits<_InputIterator2>::value_type
03495 _ValueType2;
03496
03497
03498 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03499 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03500 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03501 _ValueType1, _ValueType2>)
03502 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03503 _ValueType2, _ValueType1>)
03504 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
03505 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
03506
03507 while (__first1 != __last1 && __first2 != __last2)
03508 if (__comp(*__first2, *__first1))
03509 return false;
03510 else if(__comp(*__first1, *__first2))
03511 ++__first1;
03512 else
03513 ++__first1, ++__first2;
03514
03515 return __first2 == __last2;
03516 }
03517
03518
03519
03520
03521
03522
03523
03524
03525
03526
03527
03528
03529
03530
03531
03532
03533
03534
03535
03536
03537
03538
03539
03540 template<typename _BidirectionalIterator>
03541 bool
03542 next_permutation(_BidirectionalIterator __first,
03543 _BidirectionalIterator __last)
03544 {
03545
03546 __glibcxx_function_requires(_BidirectionalIteratorConcept<
03547 _BidirectionalIterator>)
03548 __glibcxx_function_requires(_LessThanComparableConcept<
03549 typename iterator_traits<_BidirectionalIterator>::value_type>)
03550 __glibcxx_requires_valid_range(__first, __last);
03551
03552 if (__first == __last)
03553 return false;
03554 _BidirectionalIterator __i = __first;
03555 ++__i;
03556 if (__i == __last)
03557 return false;
03558 __i = __last;
03559 --__i;
03560
03561 for(;;)
03562 {
03563 _BidirectionalIterator __ii = __i;
03564 --__i;
03565 if (*__i < *__ii)
03566 {
03567 _BidirectionalIterator __j = __last;
03568 while (!(*__i < *--__j))
03569 {}
03570 std::iter_swap(__i, __j);
03571 std::reverse(__ii, __last);
03572 return true;
03573 }
03574 if (__i == __first)
03575 {
03576 std::reverse(__first, __last);
03577 return false;
03578 }
03579 }
03580 }
03581
03582
03583
03584
03585
03586
03587
03588
03589
03590
03591
03592
03593
03594
03595
03596
03597 template<typename _BidirectionalIterator, typename _Compare>
03598 bool
03599 next_permutation(_BidirectionalIterator __first,
03600 _BidirectionalIterator __last, _Compare __comp)
03601 {
03602
03603 __glibcxx_function_requires(_BidirectionalIteratorConcept<
03604 _BidirectionalIterator>)
03605 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03606 typename iterator_traits<_BidirectionalIterator>::value_type,
03607 typename iterator_traits<_BidirectionalIterator>::value_type>)
03608 __glibcxx_requires_valid_range(__first, __last);
03609
03610 if (__first == __last)
03611 return false;
03612 _BidirectionalIterator __i = __first;
03613 ++__i;
03614 if (__i == __last)
03615 return false;
03616 __i = __last;
03617 --__i;
03618
03619 for(;;)
03620 {
03621 _BidirectionalIterator __ii = __i;
03622 --__i;
03623 if (__comp(*__i, *__ii))
03624 {
03625 _BidirectionalIterator __j = __last;
03626 while (!bool(__comp(*__i, *--__j)))
03627 {}
03628 std::iter_swap(__i, __j);
03629 std::reverse(__ii, __last);
03630 return true;
03631 }
03632 if (__i == __first)
03633 {
03634 std::reverse(__first, __last);
03635 return false;
03636 }
03637 }
03638 }
03639
03640
03641
03642
03643
03644
03645
03646
03647
03648
03649
03650
03651
03652
03653 template<typename _BidirectionalIterator>
03654 bool
03655 prev_permutation(_BidirectionalIterator __first,
03656 _BidirectionalIterator __last)
03657 {
03658
03659 __glibcxx_function_requires(_BidirectionalIteratorConcept<
03660 _BidirectionalIterator>)
03661 __glibcxx_function_requires(_LessThanComparableConcept<
03662 typename iterator_traits<_BidirectionalIterator>::value_type>)
03663 __glibcxx_requires_valid_range(__first, __last);
03664
03665 if (__first == __last)
03666 return false;
03667 _BidirectionalIterator __i = __first;
03668 ++__i;
03669 if (__i == __last)
03670 return false;
03671 __i = __last;
03672 --__i;
03673
03674 for(;;)
03675 {
03676 _BidirectionalIterator __ii = __i;
03677 --__i;
03678 if (*__ii < *__i)
03679 {
03680 _BidirectionalIterator __j = __last;
03681 while (!(*--__j < *__i))
03682 {}
03683 std::iter_swap(__i, __j);
03684 std::reverse(__ii, __last);
03685 return true;
03686 }
03687 if (__i == __first)
03688 {
03689 std::reverse(__first, __last);
03690 return false;
03691 }
03692 }
03693 }
03694
03695
03696
03697
03698
03699
03700
03701
03702
03703
03704
03705
03706
03707
03708
03709
03710 template<typename _BidirectionalIterator, typename _Compare>
03711 bool
03712 prev_permutation(_BidirectionalIterator __first,
03713 _BidirectionalIterator __last, _Compare __comp)
03714 {
03715
03716 __glibcxx_function_requires(_BidirectionalIteratorConcept<
03717 _BidirectionalIterator>)
03718 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03719 typename iterator_traits<_BidirectionalIterator>::value_type,
03720 typename iterator_traits<_BidirectionalIterator>::value_type>)
03721 __glibcxx_requires_valid_range(__first, __last);
03722
03723 if (__first == __last)
03724 return false;
03725 _BidirectionalIterator __i = __first;
03726 ++__i;
03727 if (__i == __last)
03728 return false;
03729 __i = __last;
03730 --__i;
03731
03732 for(;;)
03733 {
03734 _BidirectionalIterator __ii = __i;
03735 --__i;
03736 if (__comp(*__ii, *__i))
03737 {
03738 _BidirectionalIterator __j = __last;
03739 while (!bool(__comp(*--__j, *__i)))
03740 {}
03741 std::iter_swap(__i, __j);
03742 std::reverse(__ii, __last);
03743 return true;
03744 }
03745 if (__i == __first)
03746 {
03747 std::reverse(__first, __last);
03748 return false;
03749 }
03750 }
03751 }
03752
03753
03754
03755
03756
03757
03758
03759
03760
03761
03762
03763
03764
03765
03766
03767
03768
03769
03770 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
03771 _OutputIterator
03772 replace_copy(_InputIterator __first, _InputIterator __last,
03773 _OutputIterator __result,
03774 const _Tp& __old_value, const _Tp& __new_value)
03775 {
03776
03777 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03778 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03779 typename iterator_traits<_InputIterator>::value_type>)
03780 __glibcxx_function_requires(_EqualOpConcept<
03781 typename iterator_traits<_InputIterator>::value_type, _Tp>)
03782 __glibcxx_requires_valid_range(__first, __last);
03783
03784 for (; __first != __last; ++__first, ++__result)
03785 if (*__first == __old_value)
03786 *__result = __new_value;
03787 else
03788 *__result = *__first;
03789 return __result;
03790 }
03791
03792
03793
03794
03795
03796
03797
03798
03799
03800
03801
03802
03803
03804
03805
03806
03807 template<typename _InputIterator, typename _OutputIterator,
03808 typename _Predicate, typename _Tp>
03809 _OutputIterator
03810 replace_copy_if(_InputIterator __first, _InputIterator __last,
03811 _OutputIterator __result,
03812 _Predicate __pred, const _Tp& __new_value)
03813 {
03814
03815 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03816 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03817 typename iterator_traits<_InputIterator>::value_type>)
03818 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03819 typename iterator_traits<_InputIterator>::value_type>)
03820 __glibcxx_requires_valid_range(__first, __last);
03821
03822 for (; __first != __last; ++__first, ++__result)
03823 if (__pred(*__first))
03824 *__result = __new_value;
03825 else
03826 *__result = *__first;
03827 return __result;
03828 }
03829
03830 #ifdef __GXX_EXPERIMENTAL_CXX0X__
03831
03832
03833
03834
03835
03836
03837
03838 template<typename _ForwardIterator>
03839 inline bool
03840 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
03841 { return std::is_sorted_until(__first, __last) == __last; }
03842
03843
03844
03845
03846
03847
03848
03849
03850
03851
03852 template<typename _ForwardIterator, typename _Compare>
03853 inline bool
03854 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
03855 _Compare __comp)
03856 { return std::is_sorted_until(__first, __last, __comp) == __last; }
03857
03858
03859
03860
03861
03862
03863
03864
03865
03866 template<typename _ForwardIterator>
03867 _ForwardIterator
03868 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
03869 {
03870
03871 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03872 __glibcxx_function_requires(_LessThanComparableConcept<
03873 typename iterator_traits<_ForwardIterator>::value_type>)
03874 __glibcxx_requires_valid_range(__first, __last);
03875
03876 if (__first == __last)
03877 return __last;
03878
03879 _ForwardIterator __next = __first;
03880 for (++__next; __next != __last; __first = __next, ++__next)
03881 if (*__next < *__first)
03882 return __next;
03883 return __next;
03884 }
03885
03886
03887
03888
03889
03890
03891
03892
03893
03894
03895 template<typename _ForwardIterator, typename _Compare>
03896 _ForwardIterator
03897 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
03898 _Compare __comp)
03899 {
03900
03901 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03902 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03903 typename iterator_traits<_ForwardIterator>::value_type,
03904 typename iterator_traits<_ForwardIterator>::value_type>)
03905 __glibcxx_requires_valid_range(__first, __last);
03906
03907 if (__first == __last)
03908 return __last;
03909
03910 _ForwardIterator __next = __first;
03911 for (++__next; __next != __last; __first = __next, ++__next)
03912 if (__comp(*__next, *__first))
03913 return __next;
03914 return __next;
03915 }
03916
03917
03918
03919
03920
03921
03922
03923
03924 template<typename _Tp>
03925 inline pair<const _Tp&, const _Tp&>
03926 minmax(const _Tp& __a, const _Tp& __b)
03927 {
03928
03929 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
03930
03931 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
03932 : pair<const _Tp&, const _Tp&>(__a, __b);
03933 }
03934
03935
03936
03937
03938
03939
03940
03941
03942
03943 template<typename _Tp, typename _Compare>
03944 inline pair<const _Tp&, const _Tp&>
03945 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
03946 {
03947 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
03948 : pair<const _Tp&, const _Tp&>(__a, __b);
03949 }
03950
03951
03952
03953
03954
03955
03956
03957
03958
03959
03960
03961
03962 template<typename _ForwardIterator>
03963 pair<_ForwardIterator, _ForwardIterator>
03964 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
03965 {
03966
03967 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03968 __glibcxx_function_requires(_LessThanComparableConcept<
03969 typename iterator_traits<_ForwardIterator>::value_type>)
03970 __glibcxx_requires_valid_range(__first, __last);
03971
03972 _ForwardIterator __next = __first;
03973 if (__first == __last
03974 || ++__next == __last)
03975 return std::make_pair(__first, __first);
03976
03977 _ForwardIterator __min, __max;
03978 if (*__next < *__first)
03979 {
03980 __min = __next;
03981 __max = __first;
03982 }
03983 else
03984 {
03985 __min = __first;
03986 __max = __next;
03987 }
03988
03989 __first = __next;
03990 ++__first;
03991
03992 while (__first != __last)
03993 {
03994 __next = __first;
03995 if (++__next == __last)
03996 {
03997 if (*__first < *__min)
03998 __min = __first;
03999 else if (!(*__first < *__max))
04000 __max = __first;
04001 break;
04002 }
04003
04004 if (*__next < *__first)
04005 {
04006 if (*__next < *__min)
04007 __min = __next;
04008 if (!(*__first < *__max))
04009 __max = __first;
04010 }
04011 else
04012 {
04013 if (*__first < *__min)
04014 __min = __first;
04015 if (!(*__next < *__max))
04016 __max = __next;
04017 }
04018
04019 __first = __next;
04020 ++__first;
04021 }
04022
04023 return std::make_pair(__min, __max);
04024 }
04025
04026
04027
04028
04029
04030
04031
04032
04033
04034
04035
04036
04037
04038 template<typename _ForwardIterator, typename _Compare>
04039 pair<_ForwardIterator, _ForwardIterator>
04040 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
04041 _Compare __comp)
04042 {
04043
04044 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04045 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04046 typename iterator_traits<_ForwardIterator>::value_type,
04047 typename iterator_traits<_ForwardIterator>::value_type>)
04048 __glibcxx_requires_valid_range(__first, __last);
04049
04050 _ForwardIterator __next = __first;
04051 if (__first == __last
04052 || ++__next == __last)
04053 return std::make_pair(__first, __first);
04054
04055 _ForwardIterator __min, __max;
04056 if (__comp(*__next, *__first))
04057 {
04058 __min = __next;
04059 __max = __first;
04060 }
04061 else
04062 {
04063 __min = __first;
04064 __max = __next;
04065 }
04066
04067 __first = __next;
04068 ++__first;
04069
04070 while (__first != __last)
04071 {
04072 __next = __first;
04073 if (++__next == __last)
04074 {
04075 if (__comp(*__first, *__min))
04076 __min = __first;
04077 else if (!__comp(*__first, *__max))
04078 __max = __first;
04079 break;
04080 }
04081
04082 if (__comp(*__next, *__first))
04083 {
04084 if (__comp(*__next, *__min))
04085 __min = __next;
04086 if (!__comp(*__first, *__max))
04087 __max = __first;
04088 }
04089 else
04090 {
04091 if (__comp(*__first, *__min))
04092 __min = __first;
04093 if (!__comp(*__next, *__max))
04094 __max = __next;
04095 }
04096
04097 __first = __next;
04098 ++__first;
04099 }
04100
04101 return std::make_pair(__min, __max);
04102 }
04103
04104
04105 template<typename _Tp>
04106 inline _Tp
04107 min(initializer_list<_Tp> __l)
04108 { return *std::min_element(__l.begin(), __l.end()); }
04109
04110 template<typename _Tp, typename _Compare>
04111 inline _Tp
04112 min(initializer_list<_Tp> __l, _Compare __comp)
04113 { return *std::min_element(__l.begin(), __l.end(), __comp); }
04114
04115 template<typename _Tp>
04116 inline _Tp
04117 max(initializer_list<_Tp> __l)
04118 { return *std::max_element(__l.begin(), __l.end()); }
04119
04120 template<typename _Tp, typename _Compare>
04121 inline _Tp
04122 max(initializer_list<_Tp> __l, _Compare __comp)
04123 { return *std::max_element(__l.begin(), __l.end(), __comp); }
04124
04125 template<typename _Tp>
04126 inline pair<_Tp, _Tp>
04127 minmax(initializer_list<_Tp> __l)
04128 {
04129 pair<const _Tp*, const _Tp*> __p =
04130 std::minmax_element(__l.begin(), __l.end());
04131 return std::make_pair(*__p.first, *__p.second);
04132 }
04133
04134 template<typename _Tp, typename _Compare>
04135 inline pair<_Tp, _Tp>
04136 minmax(initializer_list<_Tp> __l, _Compare __comp)
04137 {
04138 pair<const _Tp*, const _Tp*> __p =
04139 std::minmax_element(__l.begin(), __l.end(), __comp);
04140 return std::make_pair(*__p.first, *__p.second);
04141 }
04142
04143
04144
04145
04146
04147
04148
04149
04150
04151
04152
04153
04154
04155 template<typename _ForwardIterator1, typename _ForwardIterator2>
04156 bool
04157 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04158 _ForwardIterator2 __first2)
04159 {
04160
04161
04162 for (; __first1 != __last1; ++__first1, ++__first2)
04163 if (!(*__first1 == *__first2))
04164 break;
04165
04166 if (__first1 == __last1)
04167 return true;
04168
04169
04170
04171 _ForwardIterator2 __last2 = __first2;
04172 std::advance(__last2, std::distance(__first1, __last1));
04173 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04174 {
04175 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
04176 continue;
04177
04178 auto __matches = std::count(__first2, __last2, *__scan);
04179 if (0 == __matches
04180 || std::count(__scan, __last1, *__scan) != __matches)
04181 return false;
04182 }
04183 return true;
04184 }
04185
04186
04187
04188
04189
04190
04191
04192
04193
04194
04195
04196
04197
04198
04199 template<typename _ForwardIterator1, typename _ForwardIterator2,
04200 typename _BinaryPredicate>
04201 bool
04202 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04203 _ForwardIterator2 __first2, _BinaryPredicate __pred)
04204 {
04205
04206
04207 for (; __first1 != __last1; ++__first1, ++__first2)
04208 if (!bool(__pred(*__first1, *__first2)))
04209 break;
04210
04211 if (__first1 == __last1)
04212 return true;
04213
04214
04215
04216 _ForwardIterator2 __last2 = __first2;
04217 std::advance(__last2, std::distance(__first1, __last1));
04218 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04219 {
04220 using std::placeholders::_1;
04221
04222 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
04223 std::bind(__pred, _1, *__scan)))
04224 continue;
04225
04226 auto __matches = std::count_if(__first2, __last2,
04227 std::bind(__pred, _1, *__scan));
04228 if (0 == __matches
04229 || std::count_if(__scan, __last1,
04230 std::bind(__pred, _1, *__scan)) != __matches)
04231 return false;
04232 }
04233 return true;
04234 }
04235
04236 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
04237
04238
04239
04240
04241
04242
04243
04244
04245
04246
04247
04248
04249 template<typename _RandomAccessIterator,
04250 typename _UniformRandomNumberGenerator>
04251 void
04252 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
04253 _UniformRandomNumberGenerator&& __g)
04254 {
04255
04256 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04257 _RandomAccessIterator>)
04258 __glibcxx_requires_valid_range(__first, __last);
04259
04260 if (__first == __last)
04261 return;
04262
04263 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
04264 _DistanceType;
04265
04266 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
04267 typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
04268 typedef typename __distr_type::param_type __p_type;
04269 __distr_type __d;
04270
04271 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04272 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
04273 }
04274 #endif
04275
04276 #endif // __GXX_EXPERIMENTAL_CXX0X__
04277
04278 _GLIBCXX_END_NAMESPACE_VERSION
04279
04280 _GLIBCXX_BEGIN_NAMESPACE_ALGO
04281
04282
04283
04284
04285
04286
04287
04288
04289
04290
04291
04292
04293
04294 template<typename _InputIterator, typename _Function>
04295 _Function
04296 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
04297 {
04298
04299 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04300 __glibcxx_requires_valid_range(__first, __last);
04301 for (; __first != __last; ++__first)
04302 __f(*__first);
04303 return _GLIBCXX_MOVE(__f);
04304 }
04305
04306
04307
04308
04309
04310
04311
04312
04313
04314
04315 template<typename _InputIterator, typename _Tp>
04316 inline _InputIterator
04317 find(_InputIterator __first, _InputIterator __last,
04318 const _Tp& __val)
04319 {
04320
04321 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04322 __glibcxx_function_requires(_EqualOpConcept<
04323 typename iterator_traits<_InputIterator>::value_type, _Tp>)
04324 __glibcxx_requires_valid_range(__first, __last);
04325 return std::__find(__first, __last, __val,
04326 std::__iterator_category(__first));
04327 }
04328
04329
04330
04331
04332
04333
04334
04335
04336
04337
04338
04339 template<typename _InputIterator, typename _Predicate>
04340 inline _InputIterator
04341 find_if(_InputIterator __first, _InputIterator __last,
04342 _Predicate __pred)
04343 {
04344
04345 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04346 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04347 typename iterator_traits<_InputIterator>::value_type>)
04348 __glibcxx_requires_valid_range(__first, __last);
04349 return std::__find_if(__first, __last, __pred,
04350 std::__iterator_category(__first));
04351 }
04352
04353
04354
04355
04356
04357
04358
04359
04360
04361
04362
04363
04364
04365
04366
04367
04368 template<typename _InputIterator, typename _ForwardIterator>
04369 _InputIterator
04370 find_first_of(_InputIterator __first1, _InputIterator __last1,
04371 _ForwardIterator __first2, _ForwardIterator __last2)
04372 {
04373
04374 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04375 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04376 __glibcxx_function_requires(_EqualOpConcept<
04377 typename iterator_traits<_InputIterator>::value_type,
04378 typename iterator_traits<_ForwardIterator>::value_type>)
04379 __glibcxx_requires_valid_range(__first1, __last1);
04380 __glibcxx_requires_valid_range(__first2, __last2);
04381
04382 for (; __first1 != __last1; ++__first1)
04383 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04384 if (*__first1 == *__iter)
04385 return __first1;
04386 return __last1;
04387 }
04388
04389
04390
04391
04392
04393
04394
04395
04396
04397
04398
04399
04400
04401
04402
04403
04404
04405
04406
04407 template<typename _InputIterator, typename _ForwardIterator,
04408 typename _BinaryPredicate>
04409 _InputIterator
04410 find_first_of(_InputIterator __first1, _InputIterator __last1,
04411 _ForwardIterator __first2, _ForwardIterator __last2,
04412 _BinaryPredicate __comp)
04413 {
04414
04415 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04416 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04417 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04418 typename iterator_traits<_InputIterator>::value_type,
04419 typename iterator_traits<_ForwardIterator>::value_type>)
04420 __glibcxx_requires_valid_range(__first1, __last1);
04421 __glibcxx_requires_valid_range(__first2, __last2);
04422
04423 for (; __first1 != __last1; ++__first1)
04424 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04425 if (__comp(*__first1, *__iter))
04426 return __first1;
04427 return __last1;
04428 }
04429
04430
04431
04432
04433
04434
04435
04436
04437
04438
04439 template<typename _ForwardIterator>
04440 _ForwardIterator
04441 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
04442 {
04443
04444 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04445 __glibcxx_function_requires(_EqualityComparableConcept<
04446 typename iterator_traits<_ForwardIterator>::value_type>)
04447 __glibcxx_requires_valid_range(__first, __last);
04448 if (__first == __last)
04449 return __last;
04450 _ForwardIterator __next = __first;
04451 while(++__next != __last)
04452 {
04453 if (*__first == *__next)
04454 return __first;
04455 __first = __next;
04456 }
04457 return __last;
04458 }
04459
04460
04461
04462
04463
04464
04465
04466
04467
04468
04469
04470
04471 template<typename _ForwardIterator, typename _BinaryPredicate>
04472 _ForwardIterator
04473 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
04474 _BinaryPredicate __binary_pred)
04475 {
04476
04477 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04478 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04479 typename iterator_traits<_ForwardIterator>::value_type,
04480 typename iterator_traits<_ForwardIterator>::value_type>)
04481 __glibcxx_requires_valid_range(__first, __last);
04482 if (__first == __last)
04483 return __last;
04484 _ForwardIterator __next = __first;
04485 while(++__next != __last)
04486 {
04487 if (__binary_pred(*__first, *__next))
04488 return __first;
04489 __first = __next;
04490 }
04491 return __last;
04492 }
04493
04494
04495
04496
04497
04498
04499
04500
04501
04502
04503 template<typename _InputIterator, typename _Tp>
04504 typename iterator_traits<_InputIterator>::difference_type
04505 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
04506 {
04507
04508 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04509 __glibcxx_function_requires(_EqualOpConcept<
04510 typename iterator_traits<_InputIterator>::value_type, _Tp>)
04511 __glibcxx_requires_valid_range(__first, __last);
04512 typename iterator_traits<_InputIterator>::difference_type __n = 0;
04513 for (; __first != __last; ++__first)
04514 if (*__first == __value)
04515 ++__n;
04516 return __n;
04517 }
04518
04519
04520
04521
04522
04523
04524
04525
04526
04527
04528 template<typename _InputIterator, typename _Predicate>
04529 typename iterator_traits<_InputIterator>::difference_type
04530 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
04531 {
04532
04533 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04534 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04535 typename iterator_traits<_InputIterator>::value_type>)
04536 __glibcxx_requires_valid_range(__first, __last);
04537 typename iterator_traits<_InputIterator>::difference_type __n = 0;
04538 for (; __first != __last; ++__first)
04539 if (__pred(*__first))
04540 ++__n;
04541 return __n;
04542 }
04543
04544
04545
04546
04547
04548
04549
04550
04551
04552
04553
04554
04555
04556
04557
04558
04559
04560
04561
04562
04563
04564
04565
04566
04567
04568 template<typename _ForwardIterator1, typename _ForwardIterator2>
04569 _ForwardIterator1
04570 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04571 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
04572 {
04573
04574 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04575 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04576 __glibcxx_function_requires(_EqualOpConcept<
04577 typename iterator_traits<_ForwardIterator1>::value_type,
04578 typename iterator_traits<_ForwardIterator2>::value_type>)
04579 __glibcxx_requires_valid_range(__first1, __last1);
04580 __glibcxx_requires_valid_range(__first2, __last2);
04581
04582
04583 if (__first1 == __last1 || __first2 == __last2)
04584 return __first1;
04585
04586
04587 _ForwardIterator2 __p1(__first2);
04588 if (++__p1 == __last2)
04589 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04590
04591
04592 _ForwardIterator2 __p;
04593 _ForwardIterator1 __current = __first1;
04594
04595 for (;;)
04596 {
04597 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04598 if (__first1 == __last1)
04599 return __last1;
04600
04601 __p = __p1;
04602 __current = __first1;
04603 if (++__current == __last1)
04604 return __last1;
04605
04606 while (*__current == *__p)
04607 {
04608 if (++__p == __last2)
04609 return __first1;
04610 if (++__current == __last1)
04611 return __last1;
04612 }
04613 ++__first1;
04614 }
04615 return __first1;
04616 }
04617
04618
04619
04620
04621
04622
04623
04624
04625
04626
04627
04628
04629
04630
04631
04632
04633
04634
04635
04636
04637
04638
04639 template<typename _ForwardIterator1, typename _ForwardIterator2,
04640 typename _BinaryPredicate>
04641 _ForwardIterator1
04642 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04643 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04644 _BinaryPredicate __predicate)
04645 {
04646
04647 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04648 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04649 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04650 typename iterator_traits<_ForwardIterator1>::value_type,
04651 typename iterator_traits<_ForwardIterator2>::value_type>)
04652 __glibcxx_requires_valid_range(__first1, __last1);
04653 __glibcxx_requires_valid_range(__first2, __last2);
04654
04655
04656 if (__first1 == __last1 || __first2 == __last2)
04657 return __first1;
04658
04659
04660 _ForwardIterator2 __p1(__first2);
04661 if (++__p1 == __last2)
04662 {
04663 while (__first1 != __last1
04664 && !bool(__predicate(*__first1, *__first2)))
04665 ++__first1;
04666 return __first1;
04667 }
04668
04669
04670 _ForwardIterator2 __p;
04671 _ForwardIterator1 __current = __first1;
04672
04673 for (;;)
04674 {
04675 while (__first1 != __last1
04676 && !bool(__predicate(*__first1, *__first2)))
04677 ++__first1;
04678 if (__first1 == __last1)
04679 return __last1;
04680
04681 __p = __p1;
04682 __current = __first1;
04683 if (++__current == __last1)
04684 return __last1;
04685
04686 while (__predicate(*__current, *__p))
04687 {
04688 if (++__p == __last2)
04689 return __first1;
04690 if (++__current == __last1)
04691 return __last1;
04692 }
04693 ++__first1;
04694 }
04695 return __first1;
04696 }
04697
04698
04699
04700
04701
04702
04703
04704
04705
04706
04707
04708
04709
04710
04711
04712
04713 template<typename _ForwardIterator, typename _Integer, typename _Tp>
04714 _ForwardIterator
04715 search_n(_ForwardIterator __first, _ForwardIterator __last,
04716 _Integer __count, const _Tp& __val)
04717 {
04718
04719 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04720 __glibcxx_function_requires(_EqualOpConcept<
04721 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04722 __glibcxx_requires_valid_range(__first, __last);
04723
04724 if (__count <= 0)
04725 return __first;
04726 if (__count == 1)
04727 return _GLIBCXX_STD_A::find(__first, __last, __val);
04728 return std::__search_n(__first, __last, __count, __val,
04729 std::__iterator_category(__first));
04730 }
04731
04732
04733
04734
04735
04736
04737
04738
04739
04740
04741
04742
04743
04744
04745
04746
04747
04748
04749 template<typename _ForwardIterator, typename _Integer, typename _Tp,
04750 typename _BinaryPredicate>
04751 _ForwardIterator
04752 search_n(_ForwardIterator __first, _ForwardIterator __last,
04753 _Integer __count, const _Tp& __val,
04754 _BinaryPredicate __binary_pred)
04755 {
04756
04757 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04758 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04759 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04760 __glibcxx_requires_valid_range(__first, __last);
04761
04762 if (__count <= 0)
04763 return __first;
04764 if (__count == 1)
04765 {
04766 while (__first != __last && !bool(__binary_pred(*__first, __val)))
04767 ++__first;
04768 return __first;
04769 }
04770 return std::__search_n(__first, __last, __count, __val, __binary_pred,
04771 std::__iterator_category(__first));
04772 }
04773
04774
04775
04776
04777
04778
04779
04780
04781
04782
04783
04784
04785
04786
04787
04788
04789
04790
04791 template<typename _InputIterator, typename _OutputIterator,
04792 typename _UnaryOperation>
04793 _OutputIterator
04794 transform(_InputIterator __first, _InputIterator __last,
04795 _OutputIterator __result, _UnaryOperation __unary_op)
04796 {
04797
04798 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04799 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04800
04801 __typeof__(__unary_op(*__first))>)
04802 __glibcxx_requires_valid_range(__first, __last);
04803
04804 for (; __first != __last; ++__first, ++__result)
04805 *__result = __unary_op(*__first);
04806 return __result;
04807 }
04808
04809
04810
04811
04812
04813
04814
04815
04816
04817
04818
04819
04820
04821
04822
04823
04824
04825
04826
04827 template<typename _InputIterator1, typename _InputIterator2,
04828 typename _OutputIterator, typename _BinaryOperation>
04829 _OutputIterator
04830 transform(_InputIterator1 __first1, _InputIterator1 __last1,
04831 _InputIterator2 __first2, _OutputIterator __result,
04832 _BinaryOperation __binary_op)
04833 {
04834
04835 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04836 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04837 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04838
04839 __typeof__(__binary_op(*__first1,*__first2))>)
04840 __glibcxx_requires_valid_range(__first1, __last1);
04841
04842 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
04843 *__result = __binary_op(*__first1, *__first2);
04844 return __result;
04845 }
04846
04847
04848
04849
04850
04851
04852
04853
04854
04855
04856
04857
04858
04859
04860 template<typename _ForwardIterator, typename _Tp>
04861 void
04862 replace(_ForwardIterator __first, _ForwardIterator __last,
04863 const _Tp& __old_value, const _Tp& __new_value)
04864 {
04865
04866 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04867 _ForwardIterator>)
04868 __glibcxx_function_requires(_EqualOpConcept<
04869 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04870 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04871 typename iterator_traits<_ForwardIterator>::value_type>)
04872 __glibcxx_requires_valid_range(__first, __last);
04873
04874 for (; __first != __last; ++__first)
04875 if (*__first == __old_value)
04876 *__first = __new_value;
04877 }
04878
04879
04880
04881
04882
04883
04884
04885
04886
04887
04888
04889
04890
04891
04892 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
04893 void
04894 replace_if(_ForwardIterator __first, _ForwardIterator __last,
04895 _Predicate __pred, const _Tp& __new_value)
04896 {
04897
04898 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04899 _ForwardIterator>)
04900 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04901 typename iterator_traits<_ForwardIterator>::value_type>)
04902 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04903 typename iterator_traits<_ForwardIterator>::value_type>)
04904 __glibcxx_requires_valid_range(__first, __last);
04905
04906 for (; __first != __last; ++__first)
04907 if (__pred(*__first))
04908 *__first = __new_value;
04909 }
04910
04911
04912
04913
04914
04915
04916
04917
04918
04919
04920
04921
04922
04923
04924 template<typename _ForwardIterator, typename _Generator>
04925 void
04926 generate(_ForwardIterator __first, _ForwardIterator __last,
04927 _Generator __gen)
04928 {
04929
04930 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04931 __glibcxx_function_requires(_GeneratorConcept<_Generator,
04932 typename iterator_traits<_ForwardIterator>::value_type>)
04933 __glibcxx_requires_valid_range(__first, __last);
04934
04935 for (; __first != __last; ++__first)
04936 *__first = __gen();
04937 }
04938
04939
04940
04941
04942
04943
04944
04945
04946
04947
04948
04949
04950
04951
04952
04953
04954
04955 template<typename _OutputIterator, typename _Size, typename _Generator>
04956 _OutputIterator
04957 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
04958 {
04959
04960 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04961
04962 __typeof__(__gen())>)
04963
04964 for (__decltype(__n + 0) __niter = __n;
04965 __niter > 0; --__niter, ++__first)
04966 *__first = __gen();
04967 return __first;
04968 }
04969
04970
04971
04972
04973
04974
04975
04976
04977
04978
04979
04980
04981
04982
04983
04984
04985
04986
04987
04988
04989
04990
04991
04992 template<typename _InputIterator, typename _OutputIterator>
04993 inline _OutputIterator
04994 unique_copy(_InputIterator __first, _InputIterator __last,
04995 _OutputIterator __result)
04996 {
04997
04998 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04999 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05000 typename iterator_traits<_InputIterator>::value_type>)
05001 __glibcxx_function_requires(_EqualityComparableConcept<
05002 typename iterator_traits<_InputIterator>::value_type>)
05003 __glibcxx_requires_valid_range(__first, __last);
05004
05005 if (__first == __last)
05006 return __result;
05007 return std::__unique_copy(__first, __last, __result,
05008 std::__iterator_category(__first),
05009 std::__iterator_category(__result));
05010 }
05011
05012
05013
05014
05015
05016
05017
05018
05019
05020
05021
05022
05023
05024
05025
05026
05027
05028
05029
05030
05031 template<typename _InputIterator, typename _OutputIterator,
05032 typename _BinaryPredicate>
05033 inline _OutputIterator
05034 unique_copy(_InputIterator __first, _InputIterator __last,
05035 _OutputIterator __result,
05036 _BinaryPredicate __binary_pred)
05037 {
05038
05039 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05040 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05041 typename iterator_traits<_InputIterator>::value_type>)
05042 __glibcxx_requires_valid_range(__first, __last);
05043
05044 if (__first == __last)
05045 return __result;
05046 return std::__unique_copy(__first, __last, __result, __binary_pred,
05047 std::__iterator_category(__first),
05048 std::__iterator_category(__result));
05049 }
05050
05051
05052
05053
05054
05055
05056
05057
05058
05059
05060
05061
05062
05063 template<typename _RandomAccessIterator>
05064 inline void
05065 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
05066 {
05067
05068 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05069 _RandomAccessIterator>)
05070 __glibcxx_requires_valid_range(__first, __last);
05071
05072 if (__first != __last)
05073 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05074 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
05075 }
05076
05077
05078
05079
05080
05081
05082
05083
05084
05085
05086
05087
05088
05089
05090
05091 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
05092 void
05093 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
05094 #ifdef __GXX_EXPERIMENTAL_CXX0X__
05095 _RandomNumberGenerator&& __rand)
05096 #else
05097 _RandomNumberGenerator& __rand)
05098 #endif
05099 {
05100
05101 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05102 _RandomAccessIterator>)
05103 __glibcxx_requires_valid_range(__first, __last);
05104
05105 if (__first == __last)
05106 return;
05107 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05108 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
05109 }
05110
05111
05112
05113
05114
05115
05116
05117
05118
05119
05120
05121
05122
05123
05124
05125
05126
05127 template<typename _ForwardIterator, typename _Predicate>
05128 inline _ForwardIterator
05129 partition(_ForwardIterator __first, _ForwardIterator __last,
05130 _Predicate __pred)
05131 {
05132
05133 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
05134 _ForwardIterator>)
05135 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
05136 typename iterator_traits<_ForwardIterator>::value_type>)
05137 __glibcxx_requires_valid_range(__first, __last);
05138
05139 return std::__partition(__first, __last, __pred,
05140 std::__iterator_category(__first));
05141 }
05142
05143
05144
05145
05146
05147
05148
05149
05150
05151
05152
05153
05154
05155
05156
05157
05158
05159
05160
05161 template<typename _RandomAccessIterator>
05162 inline void
05163 partial_sort(_RandomAccessIterator __first,
05164 _RandomAccessIterator __middle,
05165 _RandomAccessIterator __last)
05166 {
05167 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05168 _ValueType;
05169
05170
05171 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05172 _RandomAccessIterator>)
05173 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05174 __glibcxx_requires_valid_range(__first, __middle);
05175 __glibcxx_requires_valid_range(__middle, __last);
05176
05177 std::__heap_select(__first, __middle, __last);
05178 std::sort_heap(__first, __middle);
05179 }
05180
05181
05182
05183
05184
05185
05186
05187
05188
05189
05190
05191
05192
05193
05194
05195
05196
05197
05198
05199
05200 template<typename _RandomAccessIterator, typename _Compare>
05201 inline void
05202 partial_sort(_RandomAccessIterator __first,
05203 _RandomAccessIterator __middle,
05204 _RandomAccessIterator __last,
05205 _Compare __comp)
05206 {
05207 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05208 _ValueType;
05209
05210
05211 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05212 _RandomAccessIterator>)
05213 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05214 _ValueType, _ValueType>)
05215 __glibcxx_requires_valid_range(__first, __middle);
05216 __glibcxx_requires_valid_range(__middle, __last);
05217
05218 std::__heap_select(__first, __middle, __last, __comp);
05219 std::sort_heap(__first, __middle, __comp);
05220 }
05221
05222
05223
05224
05225
05226
05227
05228
05229
05230
05231
05232
05233
05234
05235
05236
05237
05238 template<typename _RandomAccessIterator>
05239 inline void
05240 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05241 _RandomAccessIterator __last)
05242 {
05243 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05244 _ValueType;
05245
05246
05247 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05248 _RandomAccessIterator>)
05249 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05250 __glibcxx_requires_valid_range(__first, __nth);
05251 __glibcxx_requires_valid_range(__nth, __last);
05252
05253 if (__first == __last || __nth == __last)
05254 return;
05255
05256 std::__introselect(__first, __nth, __last,
05257 std::__lg(__last - __first) * 2);
05258 }
05259
05260
05261
05262
05263
05264
05265
05266
05267
05268
05269
05270
05271
05272
05273
05274
05275
05276
05277 template<typename _RandomAccessIterator, typename _Compare>
05278 inline void
05279 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05280 _RandomAccessIterator __last, _Compare __comp)
05281 {
05282 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05283 _ValueType;
05284
05285
05286 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05287 _RandomAccessIterator>)
05288 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05289 _ValueType, _ValueType>)
05290 __glibcxx_requires_valid_range(__first, __nth);
05291 __glibcxx_requires_valid_range(__nth, __last);
05292
05293 if (__first == __last || __nth == __last)
05294 return;
05295
05296 std::__introselect(__first, __nth, __last,
05297 std::__lg(__last - __first) * 2, __comp);
05298 }
05299
05300
05301
05302
05303
05304
05305
05306
05307
05308
05309
05310
05311
05312
05313
05314
05315 template<typename _RandomAccessIterator>
05316 inline void
05317 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05318 {
05319 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05320 _ValueType;
05321
05322
05323 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05324 _RandomAccessIterator>)
05325 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05326 __glibcxx_requires_valid_range(__first, __last);
05327
05328 if (__first != __last)
05329 {
05330 std::__introsort_loop(__first, __last,
05331 std::__lg(__last - __first) * 2);
05332 std::__final_insertion_sort(__first, __last);
05333 }
05334 }
05335
05336
05337
05338
05339
05340
05341
05342
05343
05344
05345
05346
05347
05348
05349
05350
05351 template<typename _RandomAccessIterator, typename _Compare>
05352 inline void
05353 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05354 _Compare __comp)
05355 {
05356 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05357 _ValueType;
05358
05359
05360 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05361 _RandomAccessIterator>)
05362 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
05363 _ValueType>)
05364 __glibcxx_requires_valid_range(__first, __last);
05365
05366 if (__first != __last)
05367 {
05368 std::__introsort_loop(__first, __last,
05369 std::__lg(__last - __first) * 2, __comp);
05370 std::__final_insertion_sort(__first, __last, __comp);
05371 }
05372 }
05373
05374
05375
05376
05377
05378
05379
05380
05381
05382
05383
05384
05385
05386
05387
05388
05389
05390
05391
05392 template<typename _InputIterator1, typename _InputIterator2,
05393 typename _OutputIterator>
05394 _OutputIterator
05395 merge(_InputIterator1 __first1, _InputIterator1 __last1,
05396 _InputIterator2 __first2, _InputIterator2 __last2,
05397 _OutputIterator __result)
05398 {
05399 typedef typename iterator_traits<_InputIterator1>::value_type
05400 _ValueType1;
05401 typedef typename iterator_traits<_InputIterator2>::value_type
05402 _ValueType2;
05403
05404
05405 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05406 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05407 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05408 _ValueType1>)
05409 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05410 _ValueType2>)
05411 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05412 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05413 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05414
05415 while (__first1 != __last1 && __first2 != __last2)
05416 {
05417 if (*__first2 < *__first1)
05418 {
05419 *__result = *__first2;
05420 ++__first2;
05421 }
05422 else
05423 {
05424 *__result = *__first1;
05425 ++__first1;
05426 }
05427 ++__result;
05428 }
05429 return std::copy(__first2, __last2, std::copy(__first1, __last1,
05430 __result));
05431 }
05432
05433
05434
05435
05436
05437
05438
05439
05440
05441
05442
05443
05444
05445
05446
05447
05448
05449
05450
05451
05452
05453
05454
05455 template<typename _InputIterator1, typename _InputIterator2,
05456 typename _OutputIterator, typename _Compare>
05457 _OutputIterator
05458 merge(_InputIterator1 __first1, _InputIterator1 __last1,
05459 _InputIterator2 __first2, _InputIterator2 __last2,
05460 _OutputIterator __result, _Compare __comp)
05461 {
05462 typedef typename iterator_traits<_InputIterator1>::value_type
05463 _ValueType1;
05464 typedef typename iterator_traits<_InputIterator2>::value_type
05465 _ValueType2;
05466
05467
05468 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05469 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05470 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05471 _ValueType1>)
05472 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05473 _ValueType2>)
05474 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05475 _ValueType2, _ValueType1>)
05476 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05477 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05478
05479 while (__first1 != __last1 && __first2 != __last2)
05480 {
05481 if (__comp(*__first2, *__first1))
05482 {
05483 *__result = *__first2;
05484 ++__first2;
05485 }
05486 else
05487 {
05488 *__result = *__first1;
05489 ++__first1;
05490 }
05491 ++__result;
05492 }
05493 return std::copy(__first2, __last2, std::copy(__first1, __last1,
05494 __result));
05495 }
05496
05497
05498
05499
05500
05501
05502
05503
05504
05505
05506
05507
05508
05509
05510
05511
05512
05513
05514
05515 template<typename _RandomAccessIterator>
05516 inline void
05517 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05518 {
05519 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05520 _ValueType;
05521 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05522 _DistanceType;
05523
05524
05525 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05526 _RandomAccessIterator>)
05527 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05528 __glibcxx_requires_valid_range(__first, __last);
05529
05530 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05531 __last);
05532 if (__buf.begin() == 0)
05533 std::__inplace_stable_sort(__first, __last);
05534 else
05535 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05536 _DistanceType(__buf.size()));
05537 }
05538
05539
05540
05541
05542
05543
05544
05545
05546
05547
05548
05549
05550
05551
05552
05553
05554
05555
05556
05557 template<typename _RandomAccessIterator, typename _Compare>
05558 inline void
05559 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05560 _Compare __comp)
05561 {
05562 typedef typename iterator_traits<_RandomAccessIterator>::value_type
05563 _ValueType;
05564 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05565 _DistanceType;
05566
05567
05568 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05569 _RandomAccessIterator>)
05570 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05571 _ValueType,
05572 _ValueType>)
05573 __glibcxx_requires_valid_range(__first, __last);
05574
05575 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05576 __last);
05577 if (__buf.begin() == 0)
05578 std::__inplace_stable_sort(__first, __last, __comp);
05579 else
05580 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05581 _DistanceType(__buf.size()), __comp);
05582 }
05583
05584
05585
05586
05587
05588
05589
05590
05591
05592
05593
05594
05595
05596
05597
05598
05599
05600
05601
05602
05603 template<typename _InputIterator1, typename _InputIterator2,
05604 typename _OutputIterator>
05605 _OutputIterator
05606 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05607 _InputIterator2 __first2, _InputIterator2 __last2,
05608 _OutputIterator __result)
05609 {
05610 typedef typename iterator_traits<_InputIterator1>::value_type
05611 _ValueType1;
05612 typedef typename iterator_traits<_InputIterator2>::value_type
05613 _ValueType2;
05614
05615
05616 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05617 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05618 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05619 _ValueType1>)
05620 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05621 _ValueType2>)
05622 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05623 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05624 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05625 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05626
05627 while (__first1 != __last1 && __first2 != __last2)
05628 {
05629 if (*__first1 < *__first2)
05630 {
05631 *__result = *__first1;
05632 ++__first1;
05633 }
05634 else if (*__first2 < *__first1)
05635 {
05636 *__result = *__first2;
05637 ++__first2;
05638 }
05639 else
05640 {
05641 *__result = *__first1;
05642 ++__first1;
05643 ++__first2;
05644 }
05645 ++__result;
05646 }
05647 return std::copy(__first2, __last2, std::copy(__first1, __last1,
05648 __result));
05649 }
05650
05651
05652
05653
05654
05655
05656
05657
05658
05659
05660
05661
05662
05663
05664
05665
05666
05667
05668
05669
05670 template<typename _InputIterator1, typename _InputIterator2,
05671 typename _OutputIterator, typename _Compare>
05672 _OutputIterator
05673 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05674 _InputIterator2 __first2, _InputIterator2 __last2,
05675 _OutputIterator __result, _Compare __comp)
05676 {
05677 typedef typename iterator_traits<_InputIterator1>::value_type
05678 _ValueType1;
05679 typedef typename iterator_traits<_InputIterator2>::value_type
05680 _ValueType2;
05681
05682
05683 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05684 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05685 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05686 _ValueType1>)
05687 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05688 _ValueType2>)
05689 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05690 _ValueType1, _ValueType2>)
05691 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05692 _ValueType2, _ValueType1>)
05693 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05694 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05695
05696 while (__first1 != __last1 && __first2 != __last2)
05697 {
05698 if (__comp(*__first1, *__first2))
05699 {
05700 *__result = *__first1;
05701 ++__first1;
05702 }
05703 else if (__comp(*__first2, *__first1))
05704 {
05705 *__result = *__first2;
05706 ++__first2;
05707 }
05708 else
05709 {
05710 *__result = *__first1;
05711 ++__first1;
05712 ++__first2;
05713 }
05714 ++__result;
05715 }
05716 return std::copy(__first2, __last2, std::copy(__first1, __last1,
05717 __result));
05718 }
05719
05720
05721
05722
05723
05724
05725
05726
05727
05728
05729
05730
05731
05732
05733
05734
05735
05736
05737 template<typename _InputIterator1, typename _InputIterator2,
05738 typename _OutputIterator>
05739 _OutputIterator
05740 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05741 _InputIterator2 __first2, _InputIterator2 __last2,
05742 _OutputIterator __result)
05743 {
05744 typedef typename iterator_traits<_InputIterator1>::value_type
05745 _ValueType1;
05746 typedef typename iterator_traits<_InputIterator2>::value_type
05747 _ValueType2;
05748
05749
05750 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05751 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05752 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05753 _ValueType1>)
05754 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05755 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05756 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05757 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05758
05759 while (__first1 != __last1 && __first2 != __last2)
05760 if (*__first1 < *__first2)
05761 ++__first1;
05762 else if (*__first2 < *__first1)
05763 ++__first2;
05764 else
05765 {
05766 *__result = *__first1;
05767 ++__first1;
05768 ++__first2;
05769 ++__result;
05770 }
05771 return __result;
05772 }
05773
05774
05775
05776
05777
05778
05779
05780
05781
05782
05783
05784
05785
05786
05787
05788
05789
05790
05791
05792
05793
05794 template<typename _InputIterator1, typename _InputIterator2,
05795 typename _OutputIterator, typename _Compare>
05796 _OutputIterator
05797 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05798 _InputIterator2 __first2, _InputIterator2 __last2,
05799 _OutputIterator __result, _Compare __comp)
05800 {
05801 typedef typename iterator_traits<_InputIterator1>::value_type
05802 _ValueType1;
05803 typedef typename iterator_traits<_InputIterator2>::value_type
05804 _ValueType2;
05805
05806
05807 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05808 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05809 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05810 _ValueType1>)
05811 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05812 _ValueType1, _ValueType2>)
05813 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05814 _ValueType2, _ValueType1>)
05815 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05816 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05817
05818 while (__first1 != __last1 && __first2 != __last2)
05819 if (__comp(*__first1, *__first2))
05820 ++__first1;
05821 else if (__comp(*__first2, *__first1))
05822 ++__first2;
05823 else
05824 {
05825 *__result = *__first1;
05826 ++__first1;
05827 ++__first2;
05828 ++__result;
05829 }
05830 return __result;
05831 }
05832
05833
05834
05835
05836
05837
05838
05839
05840
05841
05842
05843
05844
05845
05846
05847
05848
05849
05850
05851
05852 template<typename _InputIterator1, typename _InputIterator2,
05853 typename _OutputIterator>
05854 _OutputIterator
05855 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05856 _InputIterator2 __first2, _InputIterator2 __last2,
05857 _OutputIterator __result)
05858 {
05859 typedef typename iterator_traits<_InputIterator1>::value_type
05860 _ValueType1;
05861 typedef typename iterator_traits<_InputIterator2>::value_type
05862 _ValueType2;
05863
05864
05865 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05866 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05867 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05868 _ValueType1>)
05869 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05870 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05871 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05872 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05873
05874 while (__first1 != __last1 && __first2 != __last2)
05875 if (*__first1 < *__first2)
05876 {
05877 *__result = *__first1;
05878 ++__first1;
05879 ++__result;
05880 }
05881 else if (*__first2 < *__first1)
05882 ++__first2;
05883 else
05884 {
05885 ++__first1;
05886 ++__first2;
05887 }
05888 return std::copy(__first1, __last1, __result);
05889 }
05890
05891
05892
05893
05894
05895
05896
05897
05898
05899
05900
05901
05902
05903
05904
05905
05906
05907
05908
05909
05910
05911
05912
05913 template<typename _InputIterator1, typename _InputIterator2,
05914 typename _OutputIterator, typename _Compare>
05915 _OutputIterator
05916 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05917 _InputIterator2 __first2, _InputIterator2 __last2,
05918 _OutputIterator __result, _Compare __comp)
05919 {
05920 typedef typename iterator_traits<_InputIterator1>::value_type
05921 _ValueType1;
05922 typedef typename iterator_traits<_InputIterator2>::value_type
05923 _ValueType2;
05924
05925
05926 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05927 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05928 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05929 _ValueType1>)
05930 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05931 _ValueType1, _ValueType2>)
05932 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05933 _ValueType2, _ValueType1>)
05934 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05935 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05936
05937 while (__first1 != __last1 && __first2 != __last2)
05938 if (__comp(*__first1, *__first2))
05939 {
05940 *__result = *__first1;
05941 ++__first1;
05942 ++__result;
05943 }
05944 else if (__comp(*__first2, *__first1))
05945 ++__first2;
05946 else
05947 {
05948 ++__first1;
05949 ++__first2;
05950 }
05951 return std::copy(__first1, __last1, __result);
05952 }
05953
05954
05955
05956
05957
05958
05959
05960
05961
05962
05963
05964
05965
05966
05967
05968
05969
05970
05971 template<typename _InputIterator1, typename _InputIterator2,
05972 typename _OutputIterator>
05973 _OutputIterator
05974 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05975 _InputIterator2 __first2, _InputIterator2 __last2,
05976 _OutputIterator __result)
05977 {
05978 typedef typename iterator_traits<_InputIterator1>::value_type
05979 _ValueType1;
05980 typedef typename iterator_traits<_InputIterator2>::value_type
05981 _ValueType2;
05982
05983
05984 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05985 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05986 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05987 _ValueType1>)
05988 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05989 _ValueType2>)
05990 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05991 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05992 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05993 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05994
05995 while (__first1 != __last1 && __first2 != __last2)
05996 if (*__first1 < *__first2)
05997 {
05998 *__result = *__first1;
05999 ++__first1;
06000 ++__result;
06001 }
06002 else if (*__first2 < *__first1)
06003 {
06004 *__result = *__first2;
06005 ++__first2;
06006 ++__result;
06007 }
06008 else
06009 {
06010 ++__first1;
06011 ++__first2;
06012 }
06013 return std::copy(__first2, __last2, std::copy(__first1,
06014 __last1, __result));
06015 }
06016
06017
06018
06019
06020
06021
06022
06023
06024
06025
06026
06027
06028
06029
06030
06031
06032
06033
06034
06035
06036
06037 template<typename _InputIterator1, typename _InputIterator2,
06038 typename _OutputIterator, typename _Compare>
06039 _OutputIterator
06040 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06041 _InputIterator2 __first2, _InputIterator2 __last2,
06042 _OutputIterator __result,
06043 _Compare __comp)
06044 {
06045 typedef typename iterator_traits<_InputIterator1>::value_type
06046 _ValueType1;
06047 typedef typename iterator_traits<_InputIterator2>::value_type
06048 _ValueType2;
06049
06050
06051 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06052 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06053 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06054 _ValueType1>)
06055 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06056 _ValueType2>)
06057 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06058 _ValueType1, _ValueType2>)
06059 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06060 _ValueType2, _ValueType1>)
06061 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
06062 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
06063
06064 while (__first1 != __last1 && __first2 != __last2)
06065 if (__comp(*__first1, *__first2))
06066 {
06067 *__result = *__first1;
06068 ++__first1;
06069 ++__result;
06070 }
06071 else if (__comp(*__first2, *__first1))
06072 {
06073 *__result = *__first2;
06074 ++__first2;
06075 ++__result;
06076 }
06077 else
06078 {
06079 ++__first1;
06080 ++__first2;
06081 }
06082 return std::copy(__first2, __last2,
06083 std::copy(__first1, __last1, __result));
06084 }
06085
06086
06087
06088
06089
06090
06091
06092
06093
06094 template<typename _ForwardIterator>
06095 _ForwardIterator
06096 min_element(_ForwardIterator __first, _ForwardIterator __last)
06097 {
06098
06099 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06100 __glibcxx_function_requires(_LessThanComparableConcept<
06101 typename iterator_traits<_ForwardIterator>::value_type>)
06102 __glibcxx_requires_valid_range(__first, __last);
06103
06104 if (__first == __last)
06105 return __first;
06106 _ForwardIterator __result = __first;
06107 while (++__first != __last)
06108 if (*__first < *__result)
06109 __result = __first;
06110 return __result;
06111 }
06112
06113
06114
06115
06116
06117
06118
06119
06120
06121
06122 template<typename _ForwardIterator, typename _Compare>
06123 _ForwardIterator
06124 min_element(_ForwardIterator __first, _ForwardIterator __last,
06125 _Compare __comp)
06126 {
06127
06128 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06129 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06130 typename iterator_traits<_ForwardIterator>::value_type,
06131 typename iterator_traits<_ForwardIterator>::value_type>)
06132 __glibcxx_requires_valid_range(__first, __last);
06133
06134 if (__first == __last)
06135 return __first;
06136 _ForwardIterator __result = __first;
06137 while (++__first != __last)
06138 if (__comp(*__first, *__result))
06139 __result = __first;
06140 return __result;
06141 }
06142
06143
06144
06145
06146
06147
06148
06149
06150 template<typename _ForwardIterator>
06151 _ForwardIterator
06152 max_element(_ForwardIterator __first, _ForwardIterator __last)
06153 {
06154
06155 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06156 __glibcxx_function_requires(_LessThanComparableConcept<
06157 typename iterator_traits<_ForwardIterator>::value_type>)
06158 __glibcxx_requires_valid_range(__first, __last);
06159
06160 if (__first == __last)
06161 return __first;
06162 _ForwardIterator __result = __first;
06163 while (++__first != __last)
06164 if (*__result < *__first)
06165 __result = __first;
06166 return __result;
06167 }
06168
06169
06170
06171
06172
06173
06174
06175
06176
06177
06178 template<typename _ForwardIterator, typename _Compare>
06179 _ForwardIterator
06180 max_element(_ForwardIterator __first, _ForwardIterator __last,
06181 _Compare __comp)
06182 {
06183
06184 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06185 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06186 typename iterator_traits<_ForwardIterator>::value_type,
06187 typename iterator_traits<_ForwardIterator>::value_type>)
06188 __glibcxx_requires_valid_range(__first, __last);
06189
06190 if (__first == __last) return __first;
06191 _ForwardIterator __result = __first;
06192 while (++__first != __last)
06193 if (__comp(*__result, *__first))
06194 __result = __first;
06195 return __result;
06196 }
06197
06198 _GLIBCXX_END_NAMESPACE_ALGO
06199 }
06200
06201 #endif