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