1 // <algorithm> Forward declarations -*- C++ -*-
3 // Copyright (C) 2007-2018 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/algorithmfwd.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{algorithm}
30 #ifndef _GLIBCXX_ALGORITHMFWD_H
31 #define _GLIBCXX_ALGORITHMFWD_H 1
33 #pragma GCC system_header
35 #include <bits/c++config.h>
36 #include <bits/stl_pair.h>
37 #include <bits/stl_iterator_base_types.h>
38 #if __cplusplus >= 201103L
39 #include <initializer_list>
42 namespace std
_GLIBCXX_VISIBILITY(default)
44 _GLIBCXX_BEGIN_NAMESPACE_VERSION
74 is_partitioned (C++11)
76 is_sorted_until (C++11)
78 lexicographical_compare
87 minmax_element (C++11)
95 partition_copy (C++11)
96 partition_point (C++11)
117 set_symmetric_difference
133 * @defgroup algorithms Algorithms
135 * Components for performing algorithmic operations. Includes
136 * non-modifying sequence, modifying (mutating) sequence, sorting,
137 * searching, merge, partition, heap, set, minima, maxima, and
138 * permutation operations.
142 * @defgroup mutating_algorithms Mutating
143 * @ingroup algorithms
147 * @defgroup non_mutating_algorithms Non-Mutating
148 * @ingroup algorithms
152 * @defgroup sorting_algorithms Sorting
153 * @ingroup algorithms
157 * @defgroup set_algorithms Set Operation
158 * @ingroup sorting_algorithms
160 * These algorithms are common set operations performed on sequences
161 * that are already sorted. The number of comparisons will be
166 * @defgroup binary_search_algorithms Binary Search
167 * @ingroup sorting_algorithms
169 * These algorithms are variations of a classic binary search, and
170 * all assume that the sequence being searched is already sorted.
172 * The number of comparisons will be logarithmic (and as few as
173 * possible). The number of steps through the sequence will be
174 * logarithmic for random-access iterators (e.g., pointers), and
177 * The LWG has passed Defect Report 270, which notes: <em>The
178 * proposed resolution reinterprets binary search. Instead of
179 * thinking about searching for a value in a sorted range, we view
180 * that as an important special case of a more general algorithm:
181 * searching for the partition point in a partitioned range. We
182 * also add a guarantee that the old wording did not: we ensure that
183 * the upper bound is no earlier than the lower bound, that the pair
184 * returned by equal_range is a valid range, and that the first part
185 * of that pair is the lower bound.</em>
187 * The actual effect of the first sentence is that a comparison
188 * functor passed by the user doesn't necessarily need to induce a
189 * strict weak ordering relation. Rather, it partitions the range.
194 #if __cplusplus >= 201103L
195 template<typename _IIter
, typename _Predicate
>
197 all_of(_IIter
, _IIter
, _Predicate
);
199 template<typename _IIter
, typename _Predicate
>
201 any_of(_IIter
, _IIter
, _Predicate
);
204 template<typename _FIter
, typename _Tp
>
206 binary_search(_FIter
, _FIter
, const _Tp
&);
208 template<typename _FIter
, typename _Tp
, typename _Compare
>
210 binary_search(_FIter
, _FIter
, const _Tp
&, _Compare
);
212 #if __cplusplus > 201402L
213 template<typename _Tp
>
216 clamp(const _Tp
&, const _Tp
&, const _Tp
&);
218 template<typename _Tp
, typename _Compare
>
221 clamp(const _Tp
&, const _Tp
&, const _Tp
&, _Compare
);
224 template<typename _IIter
, typename _OIter
>
226 copy(_IIter
, _IIter
, _OIter
);
228 template<typename _BIter1
, typename _BIter2
>
230 copy_backward(_BIter1
, _BIter1
, _BIter2
);
232 #if __cplusplus >= 201103L
233 template<typename _IIter
, typename _OIter
, typename _Predicate
>
235 copy_if(_IIter
, _IIter
, _OIter
, _Predicate
);
237 template<typename _IIter
, typename _Size
, typename _OIter
>
239 copy_n(_IIter
, _Size
, _OIter
);
245 template<typename _FIter
, typename _Tp
>
247 equal_range(_FIter
, _FIter
, const _Tp
&);
249 template<typename _FIter
, typename _Tp
, typename _Compare
>
251 equal_range(_FIter
, _FIter
, const _Tp
&, _Compare
);
253 template<typename _FIter
, typename _Tp
>
255 fill(_FIter
, _FIter
, const _Tp
&);
257 template<typename _OIter
, typename _Size
, typename _Tp
>
259 fill_n(_OIter
, _Size
, const _Tp
&);
263 template<typename _FIter1
, typename _FIter2
>
265 find_end(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
267 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
269 find_end(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
274 #if __cplusplus >= 201103L
275 template<typename _IIter
, typename _Predicate
>
277 find_if_not(_IIter
, _IIter
, _Predicate
);
284 template<typename _IIter1
, typename _IIter2
>
286 includes(_IIter1
, _IIter1
, _IIter2
, _IIter2
);
288 template<typename _IIter1
, typename _IIter2
, typename _Compare
>
290 includes(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _Compare
);
292 template<typename _BIter
>
294 inplace_merge(_BIter
, _BIter
, _BIter
);
296 template<typename _BIter
, typename _Compare
>
298 inplace_merge(_BIter
, _BIter
, _BIter
, _Compare
);
300 #if __cplusplus >= 201103L
301 template<typename _RAIter
>
303 is_heap(_RAIter
, _RAIter
);
305 template<typename _RAIter
, typename _Compare
>
307 is_heap(_RAIter
, _RAIter
, _Compare
);
309 template<typename _RAIter
>
311 is_heap_until(_RAIter
, _RAIter
);
313 template<typename _RAIter
, typename _Compare
>
315 is_heap_until(_RAIter
, _RAIter
, _Compare
);
317 template<typename _IIter
, typename _Predicate
>
319 is_partitioned(_IIter
, _IIter
, _Predicate
);
321 template<typename _FIter1
, typename _FIter2
>
323 is_permutation(_FIter1
, _FIter1
, _FIter2
);
325 template<typename _FIter1
, typename _FIter2
,
326 typename _BinaryPredicate
>
328 is_permutation(_FIter1
, _FIter1
, _FIter2
, _BinaryPredicate
);
330 template<typename _FIter
>
332 is_sorted(_FIter
, _FIter
);
334 template<typename _FIter
, typename _Compare
>
336 is_sorted(_FIter
, _FIter
, _Compare
);
338 template<typename _FIter
>
340 is_sorted_until(_FIter
, _FIter
);
342 template<typename _FIter
, typename _Compare
>
344 is_sorted_until(_FIter
, _FIter
, _Compare
);
347 template<typename _FIter1
, typename _FIter2
>
349 iter_swap(_FIter1
, _FIter2
);
351 template<typename _FIter
, typename _Tp
>
353 lower_bound(_FIter
, _FIter
, const _Tp
&);
355 template<typename _FIter
, typename _Tp
, typename _Compare
>
357 lower_bound(_FIter
, _FIter
, const _Tp
&, _Compare
);
359 template<typename _RAIter
>
361 make_heap(_RAIter
, _RAIter
);
363 template<typename _RAIter
, typename _Compare
>
365 make_heap(_RAIter
, _RAIter
, _Compare
);
367 template<typename _Tp
>
370 max(const _Tp
&, const _Tp
&);
372 template<typename _Tp
, typename _Compare
>
375 max(const _Tp
&, const _Tp
&, _Compare
);
380 template<typename _Tp
>
383 min(const _Tp
&, const _Tp
&);
385 template<typename _Tp
, typename _Compare
>
388 min(const _Tp
&, const _Tp
&, _Compare
);
392 #if __cplusplus >= 201103L
393 template<typename _Tp
>
395 pair
<const _Tp
&, const _Tp
&>
396 minmax(const _Tp
&, const _Tp
&);
398 template<typename _Tp
, typename _Compare
>
400 pair
<const _Tp
&, const _Tp
&>
401 minmax(const _Tp
&, const _Tp
&, _Compare
);
403 template<typename _FIter
>
406 minmax_element(_FIter
, _FIter
);
408 template<typename _FIter
, typename _Compare
>
411 minmax_element(_FIter
, _FIter
, _Compare
);
413 template<typename _Tp
>
416 min(initializer_list
<_Tp
>);
418 template<typename _Tp
, typename _Compare
>
421 min(initializer_list
<_Tp
>, _Compare
);
423 template<typename _Tp
>
426 max(initializer_list
<_Tp
>);
428 template<typename _Tp
, typename _Compare
>
431 max(initializer_list
<_Tp
>, _Compare
);
433 template<typename _Tp
>
436 minmax(initializer_list
<_Tp
>);
438 template<typename _Tp
, typename _Compare
>
441 minmax(initializer_list
<_Tp
>, _Compare
);
446 template<typename _BIter
>
448 next_permutation(_BIter
, _BIter
);
450 template<typename _BIter
, typename _Compare
>
452 next_permutation(_BIter
, _BIter
, _Compare
);
454 #if __cplusplus >= 201103L
455 template<typename _IIter
, typename _Predicate
>
457 none_of(_IIter
, _IIter
, _Predicate
);
463 template<typename _IIter
, typename _RAIter
>
465 partial_sort_copy(_IIter
, _IIter
, _RAIter
, _RAIter
);
467 template<typename _IIter
, typename _RAIter
, typename _Compare
>
469 partial_sort_copy(_IIter
, _IIter
, _RAIter
, _RAIter
, _Compare
);
473 #if __cplusplus >= 201103L
474 template<typename _IIter
, typename _OIter1
,
475 typename _OIter2
, typename _Predicate
>
476 pair
<_OIter1
, _OIter2
>
477 partition_copy(_IIter
, _IIter
, _OIter1
, _OIter2
, _Predicate
);
479 template<typename _FIter
, typename _Predicate
>
481 partition_point(_FIter
, _FIter
, _Predicate
);
484 template<typename _RAIter
>
486 pop_heap(_RAIter
, _RAIter
);
488 template<typename _RAIter
, typename _Compare
>
490 pop_heap(_RAIter
, _RAIter
, _Compare
);
492 template<typename _BIter
>
494 prev_permutation(_BIter
, _BIter
);
496 template<typename _BIter
, typename _Compare
>
498 prev_permutation(_BIter
, _BIter
, _Compare
);
500 template<typename _RAIter
>
502 push_heap(_RAIter
, _RAIter
);
504 template<typename _RAIter
, typename _Compare
>
506 push_heap(_RAIter
, _RAIter
, _Compare
);
510 template<typename _FIter
, typename _Tp
>
512 remove(_FIter
, _FIter
, const _Tp
&);
514 template<typename _FIter
, typename _Predicate
>
516 remove_if(_FIter
, _FIter
, _Predicate
);
518 template<typename _IIter
, typename _OIter
, typename _Tp
>
520 remove_copy(_IIter
, _IIter
, _OIter
, const _Tp
&);
522 template<typename _IIter
, typename _OIter
, typename _Predicate
>
524 remove_copy_if(_IIter
, _IIter
, _OIter
, _Predicate
);
528 template<typename _IIter
, typename _OIter
, typename _Tp
>
530 replace_copy(_IIter
, _IIter
, _OIter
, const _Tp
&, const _Tp
&);
532 template<typename _Iter
, typename _OIter
, typename _Predicate
, typename _Tp
>
534 replace_copy_if(_Iter
, _Iter
, _OIter
, _Predicate
, const _Tp
&);
538 template<typename _BIter
>
540 reverse(_BIter
, _BIter
);
542 template<typename _BIter
, typename _OIter
>
544 reverse_copy(_BIter
, _BIter
, _OIter
);
548 template<typename _FIter
>
550 rotate(_FIter
, _FIter
, _FIter
);
553 template<typename _FIter
, typename _OIter
>
555 rotate_copy(_FIter
, _FIter
, _FIter
, _OIter
);
561 // set_symmetric_difference
564 #if (__cplusplus >= 201103L) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
565 template<typename _RAIter
, typename _UGenerator
>
567 shuffle(_RAIter
, _RAIter
, _UGenerator
&&);
570 template<typename _RAIter
>
572 sort_heap(_RAIter
, _RAIter
);
574 template<typename _RAIter
, typename _Compare
>
576 sort_heap(_RAIter
, _RAIter
, _Compare
);
578 template<typename _BIter
, typename _Predicate
>
580 stable_partition(_BIter
, _BIter
, _Predicate
);
582 #if __cplusplus < 201103L
583 // For C++11 swap() is declared in <type_traits>.
585 template<typename _Tp
, size_t _Nm
>
587 swap(_Tp
& __a
, _Tp
& __b
);
589 template<typename _Tp
, size_t _Nm
>
591 swap(_Tp (&__a
)[_Nm
], _Tp (&__b
)[_Nm
]);
594 template<typename _FIter1
, typename _FIter2
>
596 swap_ranges(_FIter1
, _FIter1
, _FIter2
);
600 template<typename _FIter
>
602 unique(_FIter
, _FIter
);
604 template<typename _FIter
, typename _BinaryPredicate
>
606 unique(_FIter
, _FIter
, _BinaryPredicate
);
610 template<typename _FIter
, typename _Tp
>
612 upper_bound(_FIter
, _FIter
, const _Tp
&);
614 template<typename _FIter
, typename _Tp
, typename _Compare
>
616 upper_bound(_FIter
, _FIter
, const _Tp
&, _Compare
);
618 _GLIBCXX_BEGIN_NAMESPACE_ALGO
620 template<typename _FIter
>
622 adjacent_find(_FIter
, _FIter
);
624 template<typename _FIter
, typename _BinaryPredicate
>
626 adjacent_find(_FIter
, _FIter
, _BinaryPredicate
);
628 template<typename _IIter
, typename _Tp
>
629 typename iterator_traits
<_IIter
>::difference_type
630 count(_IIter
, _IIter
, const _Tp
&);
632 template<typename _IIter
, typename _Predicate
>
633 typename iterator_traits
<_IIter
>::difference_type
634 count_if(_IIter
, _IIter
, _Predicate
);
636 template<typename _IIter1
, typename _IIter2
>
638 equal(_IIter1
, _IIter1
, _IIter2
);
640 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
642 equal(_IIter1
, _IIter1
, _IIter2
, _BinaryPredicate
);
644 template<typename _IIter
, typename _Tp
>
646 find(_IIter
, _IIter
, const _Tp
&);
648 template<typename _FIter1
, typename _FIter2
>
650 find_first_of(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
652 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
654 find_first_of(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
656 template<typename _IIter
, typename _Predicate
>
658 find_if(_IIter
, _IIter
, _Predicate
);
660 template<typename _IIter
, typename _Funct
>
662 for_each(_IIter
, _IIter
, _Funct
);
664 template<typename _FIter
, typename _Generator
>
666 generate(_FIter
, _FIter
, _Generator
);
668 template<typename _OIter
, typename _Size
, typename _Generator
>
670 generate_n(_OIter
, _Size
, _Generator
);
672 template<typename _IIter1
, typename _IIter2
>
674 lexicographical_compare(_IIter1
, _IIter1
, _IIter2
, _IIter2
);
676 template<typename _IIter1
, typename _IIter2
, typename _Compare
>
678 lexicographical_compare(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _Compare
);
680 template<typename _FIter
>
683 max_element(_FIter
, _FIter
);
685 template<typename _FIter
, typename _Compare
>
688 max_element(_FIter
, _FIter
, _Compare
);
690 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
692 merge(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
694 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
697 merge(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
699 template<typename _FIter
>
702 min_element(_FIter
, _FIter
);
704 template<typename _FIter
, typename _Compare
>
707 min_element(_FIter
, _FIter
, _Compare
);
709 template<typename _IIter1
, typename _IIter2
>
710 pair
<_IIter1
, _IIter2
>
711 mismatch(_IIter1
, _IIter1
, _IIter2
);
713 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
714 pair
<_IIter1
, _IIter2
>
715 mismatch(_IIter1
, _IIter1
, _IIter2
, _BinaryPredicate
);
717 template<typename _RAIter
>
719 nth_element(_RAIter
, _RAIter
, _RAIter
);
721 template<typename _RAIter
, typename _Compare
>
723 nth_element(_RAIter
, _RAIter
, _RAIter
, _Compare
);
725 template<typename _RAIter
>
727 partial_sort(_RAIter
, _RAIter
, _RAIter
);
729 template<typename _RAIter
, typename _Compare
>
731 partial_sort(_RAIter
, _RAIter
, _RAIter
, _Compare
);
733 template<typename _BIter
, typename _Predicate
>
735 partition(_BIter
, _BIter
, _Predicate
);
737 template<typename _RAIter
>
739 random_shuffle(_RAIter
, _RAIter
);
741 template<typename _RAIter
, typename _Generator
>
743 random_shuffle(_RAIter
, _RAIter
,
744 #if __cplusplus >= 201103L
750 template<typename _FIter
, typename _Tp
>
752 replace(_FIter
, _FIter
, const _Tp
&, const _Tp
&);
754 template<typename _FIter
, typename _Predicate
, typename _Tp
>
756 replace_if(_FIter
, _FIter
, _Predicate
, const _Tp
&);
758 template<typename _FIter1
, typename _FIter2
>
760 search(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
762 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
764 search(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
766 template<typename _FIter
, typename _Size
, typename _Tp
>
768 search_n(_FIter
, _FIter
, _Size
, const _Tp
&);
770 template<typename _FIter
, typename _Size
, typename _Tp
,
771 typename _BinaryPredicate
>
773 search_n(_FIter
, _FIter
, _Size
, const _Tp
&, _BinaryPredicate
);
775 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
777 set_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
779 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
782 set_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
784 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
786 set_intersection(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
788 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
791 set_intersection(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
793 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
795 set_symmetric_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
797 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
800 set_symmetric_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
,
803 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
805 set_union(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
807 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
810 set_union(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
812 template<typename _RAIter
>
814 sort(_RAIter
, _RAIter
);
816 template<typename _RAIter
, typename _Compare
>
818 sort(_RAIter
, _RAIter
, _Compare
);
820 template<typename _RAIter
>
822 stable_sort(_RAIter
, _RAIter
);
824 template<typename _RAIter
, typename _Compare
>
826 stable_sort(_RAIter
, _RAIter
, _Compare
);
828 template<typename _IIter
, typename _OIter
, typename _UnaryOperation
>
830 transform(_IIter
, _IIter
, _OIter
, _UnaryOperation
);
832 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
833 typename _BinaryOperation
>
835 transform(_IIter1
, _IIter1
, _IIter2
, _OIter
, _BinaryOperation
);
837 template<typename _IIter
, typename _OIter
>
839 unique_copy(_IIter
, _IIter
, _OIter
);
841 template<typename _IIter
, typename _OIter
, typename _BinaryPredicate
>
843 unique_copy(_IIter
, _IIter
, _OIter
, _BinaryPredicate
);
845 _GLIBCXX_END_NAMESPACE_ALGO
846 _GLIBCXX_END_NAMESPACE_VERSION
849 #ifdef _GLIBCXX_PARALLEL
850 # include <parallel/algorithmfwd.h>