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 #ifndef _GLIBCXX_ALGORITHMFWD_H
00031 #define _GLIBCXX_ALGORITHMFWD_H 1
00032
00033 #pragma GCC system_header
00034
00035 #include <bits/c++config.h>
00036 #include <bits/stl_pair.h>
00037 #include <bits/stl_iterator_base_types.h>
00038 #include <initializer_list>
00039
00040 _GLIBCXX_BEGIN_NAMESPACE(std)
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00190 template<typename _IIter, typename _Predicate>
00191 bool
00192 all_of(_IIter, _IIter, _Predicate);
00193
00194 template<typename _IIter, typename _Predicate>
00195 bool
00196 any_of(_IIter, _IIter, _Predicate);
00197 #endif
00198
00199 template<typename _FIter, typename _Tp>
00200 bool
00201 binary_search(_FIter, _FIter, const _Tp&);
00202
00203 template<typename _FIter, typename _Tp, typename _Compare>
00204 bool
00205 binary_search(_FIter, _FIter, const _Tp&, _Compare);
00206
00207 template<typename _IIter, typename _OIter>
00208 _OIter
00209 copy(_IIter, _IIter, _OIter);
00210
00211 template<typename _BIter1, typename _BIter2>
00212 _BIter2
00213 copy_backward(_BIter1, _BIter1, _BIter2);
00214
00215 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00216 template<typename _IIter, typename _OIter, typename _Predicate>
00217 _OIter
00218 copy_if(_IIter, _IIter, _OIter, _Predicate);
00219
00220 template<typename _IIter, typename _Size, typename _OIter>
00221 _OIter
00222 copy_n(_IIter, _Size, _OIter);
00223 #endif
00224
00225
00226
00227
00228 template<typename _FIter, typename _Tp>
00229 pair<_FIter, _FIter>
00230 equal_range(_FIter, _FIter, const _Tp&);
00231
00232 template<typename _FIter, typename _Tp, typename _Compare>
00233 pair<_FIter, _FIter>
00234 equal_range(_FIter, _FIter, const _Tp&, _Compare);
00235
00236 template<typename _FIter, typename _Tp>
00237 void
00238 fill(_FIter, _FIter, const _Tp&);
00239
00240 template<typename _OIter, typename _Size, typename _Tp>
00241 _OIter
00242 fill_n(_OIter, _Size, const _Tp&);
00243
00244
00245
00246 template<typename _FIter1, typename _FIter2>
00247 _FIter1
00248 find_end(_FIter1, _FIter1, _FIter2, _FIter2);
00249
00250 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
00251 _FIter1
00252 find_end(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
00253
00254
00255
00256
00257 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00258 template<typename _IIter, typename _Predicate>
00259 _IIter
00260 find_if_not(_IIter, _IIter, _Predicate);
00261 #endif
00262
00263
00264
00265
00266
00267 template<typename _IIter1, typename _IIter2>
00268 bool
00269 includes(_IIter1, _IIter1, _IIter2, _IIter2);
00270
00271 template<typename _IIter1, typename _IIter2, typename _Compare>
00272 bool
00273 includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
00274
00275 template<typename _BIter>
00276 void
00277 inplace_merge(_BIter, _BIter, _BIter);
00278
00279 template<typename _BIter, typename _Compare>
00280 void
00281 inplace_merge(_BIter, _BIter, _BIter, _Compare);
00282
00283 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00284 template<typename _RAIter>
00285 bool
00286 is_heap(_RAIter, _RAIter);
00287
00288 template<typename _RAIter, typename _Compare>
00289 bool
00290 is_heap(_RAIter, _RAIter, _Compare);
00291
00292 template<typename _RAIter>
00293 _RAIter
00294 is_heap_until(_RAIter, _RAIter);
00295
00296 template<typename _RAIter, typename _Compare>
00297 _RAIter
00298 is_heap_until(_RAIter, _RAIter, _Compare);
00299
00300 template<typename _IIter, typename _Predicate>
00301 bool
00302 is_partitioned(_IIter, _IIter, _Predicate);
00303
00304 template<typename _FIter>
00305 bool
00306 is_sorted(_FIter, _FIter);
00307
00308 template<typename _FIter, typename _Compare>
00309 bool
00310 is_sorted(_FIter, _FIter, _Compare);
00311
00312 template<typename _FIter>
00313 _FIter
00314 is_sorted_until(_FIter, _FIter);
00315
00316 template<typename _FIter, typename _Compare>
00317 _FIter
00318 is_sorted_until(_FIter, _FIter, _Compare);
00319 #endif
00320
00321 template<typename _FIter1, typename _FIter2>
00322 void
00323 iter_swap(_FIter1, _FIter2);
00324
00325 template<typename _FIter, typename _Tp>
00326 _FIter
00327 lower_bound(_FIter, _FIter, const _Tp&);
00328
00329 template<typename _FIter, typename _Tp, typename _Compare>
00330 _FIter
00331 lower_bound(_FIter, _FIter, const _Tp&, _Compare);
00332
00333 template<typename _RAIter>
00334 void
00335 make_heap(_RAIter, _RAIter);
00336
00337 template<typename _RAIter, typename _Compare>
00338 void
00339 make_heap(_RAIter, _RAIter, _Compare);
00340
00341 template<typename _Tp>
00342 const _Tp&
00343 max(const _Tp&, const _Tp&);
00344
00345 template<typename _Tp, typename _Compare>
00346 const _Tp&
00347 max(const _Tp&, const _Tp&, _Compare);
00348
00349
00350
00351
00352 template<typename _Tp>
00353 const _Tp&
00354 min(const _Tp&, const _Tp&);
00355
00356 template<typename _Tp, typename _Compare>
00357 const _Tp&
00358 min(const _Tp&, const _Tp&, _Compare);
00359
00360
00361
00362 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00363 template<typename _Tp>
00364 pair<const _Tp&, const _Tp&>
00365 minmax(const _Tp&, const _Tp&);
00366
00367 template<typename _Tp, typename _Compare>
00368 pair<const _Tp&, const _Tp&>
00369 minmax(const _Tp&, const _Tp&, _Compare);
00370
00371 template<typename _FIter>
00372 pair<_FIter, _FIter>
00373 minmax_element(_FIter, _FIter);
00374
00375 template<typename _FIter, typename _Compare>
00376 pair<_FIter, _FIter>
00377 minmax_element(_FIter, _FIter, _Compare);
00378
00379 template<typename _Tp>
00380 _Tp
00381 min(initializer_list<_Tp>);
00382
00383 template<typename _Tp, typename _Compare>
00384 _Tp
00385 min(initializer_list<_Tp>, _Compare);
00386
00387 template<typename _Tp>
00388 _Tp
00389 max(initializer_list<_Tp>);
00390
00391 template<typename _Tp, typename _Compare>
00392 _Tp
00393 max(initializer_list<_Tp>, _Compare);
00394
00395 template<typename _Tp>
00396 pair<_Tp, _Tp>
00397 minmax(initializer_list<_Tp>);
00398
00399 template<typename _Tp, typename _Compare>
00400 pair<_Tp, _Tp>
00401 minmax(initializer_list<_Tp>, _Compare);
00402 #endif
00403
00404
00405
00406 template<typename _BIter>
00407 bool
00408 next_permutation(_BIter, _BIter);
00409
00410 template<typename _BIter, typename _Compare>
00411 bool
00412 next_permutation(_BIter, _BIter, _Compare);
00413
00414 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00415 template<typename _IIter, typename _Predicate>
00416 bool
00417 none_of(_IIter, _IIter, _Predicate);
00418 #endif
00419
00420
00421
00422
00423 template<typename _IIter, typename _RAIter>
00424 _RAIter
00425 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter);
00426
00427 template<typename _IIter, typename _RAIter, typename _Compare>
00428 _RAIter
00429 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter, _Compare);
00430
00431
00432
00433 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00434 template<typename _IIter, typename _OIter1,
00435 typename _OIter2, typename _Predicate>
00436 pair<_OIter1, _OIter2>
00437 partition_copy(_IIter, _IIter, _OIter1, _OIter2, _Predicate);
00438
00439 template<typename _FIter, typename _Predicate>
00440 _FIter
00441 partition_point(_FIter, _FIter, _Predicate);
00442 #endif
00443
00444 template<typename _RAIter>
00445 void
00446 pop_heap(_RAIter, _RAIter);
00447
00448 template<typename _RAIter, typename _Compare>
00449 void
00450 pop_heap(_RAIter, _RAIter, _Compare);
00451
00452 template<typename _BIter>
00453 bool
00454 prev_permutation(_BIter, _BIter);
00455
00456 template<typename _BIter, typename _Compare>
00457 bool
00458 prev_permutation(_BIter, _BIter, _Compare);
00459
00460 template<typename _RAIter>
00461 void
00462 push_heap(_RAIter, _RAIter);
00463
00464 template<typename _RAIter, typename _Compare>
00465 void
00466 push_heap(_RAIter, _RAIter, _Compare);
00467
00468
00469
00470 template<typename _FIter, typename _Tp>
00471 _FIter
00472 remove(_FIter, _FIter, const _Tp&);
00473
00474 template<typename _FIter, typename _Predicate>
00475 _FIter
00476 remove_if(_FIter, _FIter, _Predicate);
00477
00478 template<typename _IIter, typename _OIter, typename _Tp>
00479 _OIter
00480 remove_copy(_IIter, _IIter, _OIter, const _Tp&);
00481
00482 template<typename _IIter, typename _OIter, typename _Predicate>
00483 _OIter
00484 remove_copy_if(_IIter, _IIter, _OIter, _Predicate);
00485
00486
00487
00488 template<typename _IIter, typename _OIter, typename _Tp>
00489 _OIter
00490 replace_copy(_IIter, _IIter, _OIter, const _Tp&, const _Tp&);
00491
00492 template<typename _Iter, typename _OIter, typename _Predicate, typename _Tp>
00493 _OIter
00494 replace_copy_if(_Iter, _Iter, _OIter, _Predicate, const _Tp&);
00495
00496
00497
00498 template<typename _BIter>
00499 void
00500 reverse(_BIter, _BIter);
00501
00502 template<typename _BIter, typename _OIter>
00503 _OIter
00504 reverse_copy(_BIter, _BIter, _OIter);
00505
00506 template<typename _FIter>
00507 void
00508 rotate(_FIter, _FIter, _FIter);
00509
00510 template<typename _FIter, typename _OIter>
00511 _OIter
00512 rotate_copy(_FIter, _FIter, _FIter, _OIter);
00513
00514
00515
00516
00517
00518
00519
00520
00521 #if defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
00522 template<typename _RAIter, typename _UGenerator>
00523 void
00524 shuffle(_RAIter, _RAIter, _UGenerator&);
00525 #endif
00526
00527 template<typename _RAIter>
00528 void
00529 sort_heap(_RAIter, _RAIter);
00530
00531 template<typename _RAIter, typename _Compare>
00532 void
00533 sort_heap(_RAIter, _RAIter, _Compare);
00534
00535 template<typename _BIter, typename _Predicate>
00536 _BIter
00537 stable_partition(_BIter, _BIter, _Predicate);
00538
00539 template<typename _Tp>
00540 void
00541 swap(_Tp&, _Tp&);
00542
00543 template<typename _Tp, size_t _Nm>
00544 void
00545 swap(_Tp (&)[_Nm], _Tp (&)[_Nm]);
00546
00547 template<typename _FIter1, typename _FIter2>
00548 _FIter2
00549 swap_ranges(_FIter1, _FIter1, _FIter2);
00550
00551
00552
00553 template<typename _FIter>
00554 _FIter
00555 unique(_FIter, _FIter);
00556
00557 template<typename _FIter, typename _BinaryPredicate>
00558 _FIter
00559 unique(_FIter, _FIter, _BinaryPredicate);
00560
00561
00562
00563 template<typename _FIter, typename _Tp>
00564 _FIter
00565 upper_bound(_FIter, _FIter, const _Tp&);
00566
00567 template<typename _FIter, typename _Tp, typename _Compare>
00568 _FIter
00569 upper_bound(_FIter, _FIter, const _Tp&, _Compare);
00570
00571 _GLIBCXX_END_NAMESPACE
00572
00573 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
00574
00575 template<typename _FIter>
00576 _FIter
00577 adjacent_find(_FIter, _FIter);
00578
00579 template<typename _FIter, typename _BinaryPredicate>
00580 _FIter
00581 adjacent_find(_FIter, _FIter, _BinaryPredicate);
00582
00583 template<typename _IIter, typename _Tp>
00584 typename iterator_traits<_IIter>::difference_type
00585 count(_IIter, _IIter, const _Tp&);
00586
00587 template<typename _IIter, typename _Predicate>
00588 typename iterator_traits<_IIter>::difference_type
00589 count_if(_IIter, _IIter, _Predicate);
00590
00591 template<typename _IIter1, typename _IIter2>
00592 bool
00593 equal(_IIter1, _IIter1, _IIter2);
00594
00595 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
00596 bool
00597 equal(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
00598
00599 template<typename _IIter, typename _Tp>
00600 _IIter
00601 find(_IIter, _IIter, const _Tp&);
00602
00603 template<typename _FIter1, typename _FIter2>
00604 _FIter1
00605 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2);
00606
00607 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
00608 _FIter1
00609 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
00610
00611 template<typename _IIter, typename _Predicate>
00612 _IIter
00613 find_if(_IIter, _IIter, _Predicate);
00614
00615 template<typename _IIter, typename _Funct>
00616 _Funct
00617 for_each(_IIter, _IIter, _Funct);
00618
00619 template<typename _FIter, typename _Generator>
00620 void
00621 generate(_FIter, _FIter, _Generator);
00622
00623 template<typename _OIter, typename _Size, typename _Generator>
00624 _OIter
00625 generate_n(_OIter, _Size, _Generator);
00626
00627 template<typename _IIter1, typename _IIter2>
00628 bool
00629 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
00630
00631 template<typename _IIter1, typename _IIter2, typename _Compare>
00632 bool
00633 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
00634
00635 template<typename _FIter>
00636 _FIter
00637 max_element(_FIter, _FIter);
00638
00639 template<typename _FIter, typename _Compare>
00640 _FIter
00641 max_element(_FIter, _FIter, _Compare);
00642
00643 template<typename _IIter1, typename _IIter2, typename _OIter>
00644 _OIter
00645 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
00646
00647 template<typename _IIter1, typename _IIter2, typename _OIter,
00648 typename _Compare>
00649 _OIter
00650 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
00651
00652 template<typename _FIter>
00653 _FIter
00654 min_element(_FIter, _FIter);
00655
00656 template<typename _FIter, typename _Compare>
00657 _FIter
00658 min_element(_FIter, _FIter, _Compare);
00659
00660 template<typename _IIter1, typename _IIter2>
00661 pair<_IIter1, _IIter2>
00662 mismatch(_IIter1, _IIter1, _IIter2);
00663
00664 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
00665 pair<_IIter1, _IIter2>
00666 mismatch(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
00667
00668 template<typename _RAIter>
00669 void
00670 nth_element(_RAIter, _RAIter, _RAIter);
00671
00672 template<typename _RAIter, typename _Compare>
00673 void
00674 nth_element(_RAIter, _RAIter, _RAIter, _Compare);
00675
00676 template<typename _RAIter>
00677 void
00678 partial_sort(_RAIter, _RAIter, _RAIter);
00679
00680 template<typename _RAIter, typename _Compare>
00681 void
00682 partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
00683
00684 template<typename _BIter, typename _Predicate>
00685 _BIter
00686 partition(_BIter, _BIter, _Predicate);
00687
00688 template<typename _RAIter>
00689 void
00690 random_shuffle(_RAIter, _RAIter);
00691
00692 template<typename _RAIter, typename _Generator>
00693 void
00694 random_shuffle(_RAIter, _RAIter,
00695 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00696 _Generator&&);
00697 #else
00698 _Generator&);
00699 #endif
00700
00701 template<typename _FIter, typename _Tp>
00702 void
00703 replace(_FIter, _FIter, const _Tp&, const _Tp&);
00704
00705 template<typename _FIter, typename _Predicate, typename _Tp>
00706 void
00707 replace_if(_FIter, _FIter, _Predicate, const _Tp&);
00708
00709 template<typename _FIter1, typename _FIter2>
00710 _FIter1
00711 search(_FIter1, _FIter1, _FIter2, _FIter2);
00712
00713 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
00714 _FIter1
00715 search(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
00716
00717 template<typename _FIter, typename _Size, typename _Tp>
00718 _FIter
00719 search_n(_FIter, _FIter, _Size, const _Tp&);
00720
00721 template<typename _FIter, typename _Size, typename _Tp,
00722 typename _BinaryPredicate>
00723 _FIter
00724 search_n(_FIter, _FIter, _Size, const _Tp&, _BinaryPredicate);
00725
00726 template<typename _IIter1, typename _IIter2, typename _OIter>
00727 _OIter
00728 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
00729
00730 template<typename _IIter1, typename _IIter2, typename _OIter,
00731 typename _Compare>
00732 _OIter
00733 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
00734
00735 template<typename _IIter1, typename _IIter2, typename _OIter>
00736 _OIter
00737 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
00738
00739 template<typename _IIter1, typename _IIter2, typename _OIter,
00740 typename _Compare>
00741 _OIter
00742 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
00743
00744 template<typename _IIter1, typename _IIter2, typename _OIter>
00745 _OIter
00746 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
00747
00748 template<typename _IIter1, typename _IIter2, typename _OIter,
00749 typename _Compare>
00750 _OIter
00751 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2,
00752 _OIter, _Compare);
00753
00754 template<typename _IIter1, typename _IIter2, typename _OIter>
00755 _OIter
00756 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
00757
00758 template<typename _IIter1, typename _IIter2, typename _OIter,
00759 typename _Compare>
00760 _OIter
00761 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
00762
00763 template<typename _RAIter>
00764 void
00765 sort(_RAIter, _RAIter);
00766
00767 template<typename _RAIter, typename _Compare>
00768 void
00769 sort(_RAIter, _RAIter, _Compare);
00770
00771 template<typename _RAIter>
00772 void
00773 stable_sort(_RAIter, _RAIter);
00774
00775 template<typename _RAIter, typename _Compare>
00776 void
00777 stable_sort(_RAIter, _RAIter, _Compare);
00778
00779 template<typename _IIter, typename _OIter, typename _UnaryOperation>
00780 _OIter
00781 transform(_IIter, _IIter, _OIter, _UnaryOperation);
00782
00783 template<typename _IIter1, typename _IIter2, typename _OIter,
00784 typename _BinaryOperation>
00785 _OIter
00786 transform(_IIter1, _IIter1, _IIter2, _OIter, _BinaryOperation);
00787
00788 template<typename _IIter, typename _OIter>
00789 _OIter
00790 unique_copy(_IIter, _IIter, _OIter);
00791
00792 template<typename _IIter, typename _OIter, typename _BinaryPredicate>
00793 _OIter
00794 unique_copy(_IIter, _IIter, _OIter, _BinaryPredicate);
00795
00796 _GLIBCXX_END_NESTED_NAMESPACE
00797
00798 #ifdef _GLIBCXX_NAMESPACE_ASSOCIATION_PARALLEL
00799 # include <parallel/algorithmfwd.h>
00800 #endif
00801
00802 #endif
00803