1 // <algorithm> Forward declarations -*- C++ -*-
3 // Copyright (C) 2007-2024 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 Operations
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
>
198 all_of(_IIter
, _IIter
, _Predicate
);
200 template<typename _IIter
, typename _Predicate
>
203 any_of(_IIter
, _IIter
, _Predicate
);
206 template<typename _FIter
, typename _Tp
>
209 binary_search(_FIter
, _FIter
, const _Tp
&);
211 template<typename _FIter
, typename _Tp
, typename _Compare
>
214 binary_search(_FIter
, _FIter
, const _Tp
&, _Compare
);
216 #if __cplusplus > 201402L
217 template<typename _Tp
>
220 clamp(const _Tp
&, const _Tp
&, const _Tp
&);
222 template<typename _Tp
, typename _Compare
>
225 clamp(const _Tp
&, const _Tp
&, const _Tp
&, _Compare
);
228 template<typename _IIter
, typename _OIter
>
231 copy(_IIter
, _IIter
, _OIter
);
233 template<typename _BIter1
, typename _BIter2
>
236 copy_backward(_BIter1
, _BIter1
, _BIter2
);
238 #if __cplusplus >= 201103L
239 template<typename _IIter
, typename _OIter
, typename _Predicate
>
242 copy_if(_IIter
, _IIter
, _OIter
, _Predicate
);
244 template<typename _IIter
, typename _Size
, typename _OIter
>
247 copy_n(_IIter
, _Size
, _OIter
);
253 template<typename _FIter
, typename _Tp
>
256 equal_range(_FIter
, _FIter
, const _Tp
&);
258 template<typename _FIter
, typename _Tp
, typename _Compare
>
261 equal_range(_FIter
, _FIter
, const _Tp
&, _Compare
);
263 template<typename _FIter
, typename _Tp
>
266 fill(_FIter
, _FIter
, const _Tp
&);
268 template<typename _OIter
, typename _Size
, typename _Tp
>
271 fill_n(_OIter
, _Size
, const _Tp
&);
275 template<typename _FIter1
, typename _FIter2
>
278 find_end(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
280 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
283 find_end(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
288 #if __cplusplus >= 201103L
289 template<typename _IIter
, typename _Predicate
>
292 find_if_not(_IIter
, _IIter
, _Predicate
);
299 template<typename _IIter1
, typename _IIter2
>
302 includes(_IIter1
, _IIter1
, _IIter2
, _IIter2
);
304 template<typename _IIter1
, typename _IIter2
, typename _Compare
>
307 includes(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _Compare
);
309 template<typename _BIter
>
311 inplace_merge(_BIter
, _BIter
, _BIter
);
313 template<typename _BIter
, typename _Compare
>
315 inplace_merge(_BIter
, _BIter
, _BIter
, _Compare
);
317 #if __cplusplus >= 201103L
318 template<typename _RAIter
>
321 is_heap(_RAIter
, _RAIter
);
323 template<typename _RAIter
, typename _Compare
>
326 is_heap(_RAIter
, _RAIter
, _Compare
);
328 template<typename _RAIter
>
331 is_heap_until(_RAIter
, _RAIter
);
333 template<typename _RAIter
, typename _Compare
>
336 is_heap_until(_RAIter
, _RAIter
, _Compare
);
338 template<typename _IIter
, typename _Predicate
>
341 is_partitioned(_IIter
, _IIter
, _Predicate
);
343 template<typename _FIter1
, typename _FIter2
>
346 is_permutation(_FIter1
, _FIter1
, _FIter2
);
348 template<typename _FIter1
, typename _FIter2
,
349 typename _BinaryPredicate
>
352 is_permutation(_FIter1
, _FIter1
, _FIter2
, _BinaryPredicate
);
354 template<typename _FIter
>
357 is_sorted(_FIter
, _FIter
);
359 template<typename _FIter
, typename _Compare
>
362 is_sorted(_FIter
, _FIter
, _Compare
);
364 template<typename _FIter
>
367 is_sorted_until(_FIter
, _FIter
);
369 template<typename _FIter
, typename _Compare
>
372 is_sorted_until(_FIter
, _FIter
, _Compare
);
375 template<typename _FIter1
, typename _FIter2
>
378 iter_swap(_FIter1
, _FIter2
);
380 template<typename _FIter
, typename _Tp
>
383 lower_bound(_FIter
, _FIter
, const _Tp
&);
385 template<typename _FIter
, typename _Tp
, typename _Compare
>
388 lower_bound(_FIter
, _FIter
, const _Tp
&, _Compare
);
390 template<typename _RAIter
>
393 make_heap(_RAIter
, _RAIter
);
395 template<typename _RAIter
, typename _Compare
>
398 make_heap(_RAIter
, _RAIter
, _Compare
);
400 template<typename _Tp
>
403 max(const _Tp
&, const _Tp
&);
405 template<typename _Tp
, typename _Compare
>
408 max(const _Tp
&, const _Tp
&, _Compare
);
413 template<typename _Tp
>
416 min(const _Tp
&, const _Tp
&);
418 template<typename _Tp
, typename _Compare
>
421 min(const _Tp
&, const _Tp
&, _Compare
);
425 #if __cplusplus >= 201103L
426 template<typename _Tp
>
428 pair
<const _Tp
&, const _Tp
&>
429 minmax(const _Tp
&, const _Tp
&);
431 template<typename _Tp
, typename _Compare
>
433 pair
<const _Tp
&, const _Tp
&>
434 minmax(const _Tp
&, const _Tp
&, _Compare
);
436 template<typename _FIter
>
439 minmax_element(_FIter
, _FIter
);
441 template<typename _FIter
, typename _Compare
>
444 minmax_element(_FIter
, _FIter
, _Compare
);
446 template<typename _Tp
>
449 min(initializer_list
<_Tp
>);
451 template<typename _Tp
, typename _Compare
>
454 min(initializer_list
<_Tp
>, _Compare
);
456 template<typename _Tp
>
459 max(initializer_list
<_Tp
>);
461 template<typename _Tp
, typename _Compare
>
464 max(initializer_list
<_Tp
>, _Compare
);
466 template<typename _Tp
>
469 minmax(initializer_list
<_Tp
>);
471 template<typename _Tp
, typename _Compare
>
474 minmax(initializer_list
<_Tp
>, _Compare
);
479 template<typename _BIter
>
482 next_permutation(_BIter
, _BIter
);
484 template<typename _BIter
, typename _Compare
>
487 next_permutation(_BIter
, _BIter
, _Compare
);
489 #if __cplusplus >= 201103L
490 template<typename _IIter
, typename _Predicate
>
493 none_of(_IIter
, _IIter
, _Predicate
);
499 template<typename _IIter
, typename _RAIter
>
502 partial_sort_copy(_IIter
, _IIter
, _RAIter
, _RAIter
);
504 template<typename _IIter
, typename _RAIter
, typename _Compare
>
507 partial_sort_copy(_IIter
, _IIter
, _RAIter
, _RAIter
, _Compare
);
511 #if __cplusplus >= 201103L
512 template<typename _IIter
, typename _OIter1
,
513 typename _OIter2
, typename _Predicate
>
515 pair
<_OIter1
, _OIter2
>
516 partition_copy(_IIter
, _IIter
, _OIter1
, _OIter2
, _Predicate
);
518 template<typename _FIter
, typename _Predicate
>
521 partition_point(_FIter
, _FIter
, _Predicate
);
524 template<typename _RAIter
>
527 pop_heap(_RAIter
, _RAIter
);
529 template<typename _RAIter
, typename _Compare
>
532 pop_heap(_RAIter
, _RAIter
, _Compare
);
534 template<typename _BIter
>
537 prev_permutation(_BIter
, _BIter
);
539 template<typename _BIter
, typename _Compare
>
542 prev_permutation(_BIter
, _BIter
, _Compare
);
544 template<typename _RAIter
>
547 push_heap(_RAIter
, _RAIter
);
549 template<typename _RAIter
, typename _Compare
>
552 push_heap(_RAIter
, _RAIter
, _Compare
);
556 template<typename _FIter
, typename _Tp
>
559 remove(_FIter
, _FIter
, const _Tp
&);
561 template<typename _FIter
, typename _Predicate
>
564 remove_if(_FIter
, _FIter
, _Predicate
);
566 template<typename _IIter
, typename _OIter
, typename _Tp
>
569 remove_copy(_IIter
, _IIter
, _OIter
, const _Tp
&);
571 template<typename _IIter
, typename _OIter
, typename _Predicate
>
574 remove_copy_if(_IIter
, _IIter
, _OIter
, _Predicate
);
578 template<typename _IIter
, typename _OIter
, typename _Tp
>
581 replace_copy(_IIter
, _IIter
, _OIter
, const _Tp
&, const _Tp
&);
583 template<typename _Iter
, typename _OIter
, typename _Predicate
, typename _Tp
>
586 replace_copy_if(_Iter
, _Iter
, _OIter
, _Predicate
, const _Tp
&);
590 template<typename _BIter
>
593 reverse(_BIter
, _BIter
);
595 template<typename _BIter
, typename _OIter
>
598 reverse_copy(_BIter
, _BIter
, _OIter
);
600 _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2
)
602 template<typename _FIter
>
605 rotate(_FIter
, _FIter
, _FIter
);
607 _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2
)
609 template<typename _FIter
, typename _OIter
>
612 rotate_copy(_FIter
, _FIter
, _FIter
, _OIter
);
618 // set_symmetric_difference
621 #if __cplusplus >= 201103L
622 template<typename _RAIter
, typename _UGenerator
>
624 shuffle(_RAIter
, _RAIter
, _UGenerator
&&);
627 template<typename _RAIter
>
630 sort_heap(_RAIter
, _RAIter
);
632 template<typename _RAIter
, typename _Compare
>
635 sort_heap(_RAIter
, _RAIter
, _Compare
);
638 template<typename _BIter
, typename _Predicate
>
640 stable_partition(_BIter
, _BIter
, _Predicate
);
643 #if __cplusplus < 201103L
644 // For C++11 swap() is declared in <type_traits>.
646 template<typename _Tp
, size_t _Nm
>
649 swap(_Tp
& __a
, _Tp
& __b
);
651 template<typename _Tp
, size_t _Nm
>
654 swap(_Tp (&__a
)[_Nm
], _Tp (&__b
)[_Nm
]);
657 template<typename _FIter1
, typename _FIter2
>
660 swap_ranges(_FIter1
, _FIter1
, _FIter2
);
664 template<typename _FIter
>
667 unique(_FIter
, _FIter
);
669 template<typename _FIter
, typename _BinaryPredicate
>
672 unique(_FIter
, _FIter
, _BinaryPredicate
);
676 template<typename _FIter
, typename _Tp
>
679 upper_bound(_FIter
, _FIter
, const _Tp
&);
681 template<typename _FIter
, typename _Tp
, typename _Compare
>
684 upper_bound(_FIter
, _FIter
, const _Tp
&, _Compare
);
686 _GLIBCXX_BEGIN_NAMESPACE_ALGO
688 template<typename _FIter
>
691 adjacent_find(_FIter
, _FIter
);
693 template<typename _FIter
, typename _BinaryPredicate
>
696 adjacent_find(_FIter
, _FIter
, _BinaryPredicate
);
698 template<typename _IIter
, typename _Tp
>
700 typename iterator_traits
<_IIter
>::difference_type
701 count(_IIter
, _IIter
, const _Tp
&);
703 template<typename _IIter
, typename _Predicate
>
705 typename iterator_traits
<_IIter
>::difference_type
706 count_if(_IIter
, _IIter
, _Predicate
);
708 template<typename _IIter1
, typename _IIter2
>
711 equal(_IIter1
, _IIter1
, _IIter2
);
713 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
716 equal(_IIter1
, _IIter1
, _IIter2
, _BinaryPredicate
);
718 template<typename _IIter
, typename _Tp
>
721 find(_IIter
, _IIter
, const _Tp
&);
723 template<typename _FIter1
, typename _FIter2
>
726 find_first_of(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
728 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
731 find_first_of(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
733 template<typename _IIter
, typename _Predicate
>
736 find_if(_IIter
, _IIter
, _Predicate
);
738 template<typename _IIter
, typename _Funct
>
741 for_each(_IIter
, _IIter
, _Funct
);
743 template<typename _FIter
, typename _Generator
>
746 generate(_FIter
, _FIter
, _Generator
);
748 template<typename _OIter
, typename _Size
, typename _Generator
>
751 generate_n(_OIter
, _Size
, _Generator
);
753 template<typename _IIter1
, typename _IIter2
>
756 lexicographical_compare(_IIter1
, _IIter1
, _IIter2
, _IIter2
);
758 template<typename _IIter1
, typename _IIter2
, typename _Compare
>
761 lexicographical_compare(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _Compare
);
763 template<typename _FIter
>
766 max_element(_FIter
, _FIter
);
768 template<typename _FIter
, typename _Compare
>
771 max_element(_FIter
, _FIter
, _Compare
);
773 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
776 merge(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
778 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
782 merge(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
784 template<typename _FIter
>
787 min_element(_FIter
, _FIter
);
789 template<typename _FIter
, typename _Compare
>
792 min_element(_FIter
, _FIter
, _Compare
);
794 template<typename _IIter1
, typename _IIter2
>
796 pair
<_IIter1
, _IIter2
>
797 mismatch(_IIter1
, _IIter1
, _IIter2
);
799 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
801 pair
<_IIter1
, _IIter2
>
802 mismatch(_IIter1
, _IIter1
, _IIter2
, _BinaryPredicate
);
804 template<typename _RAIter
>
807 nth_element(_RAIter
, _RAIter
, _RAIter
);
809 template<typename _RAIter
, typename _Compare
>
812 nth_element(_RAIter
, _RAIter
, _RAIter
, _Compare
);
814 template<typename _RAIter
>
817 partial_sort(_RAIter
, _RAIter
, _RAIter
);
819 template<typename _RAIter
, typename _Compare
>
822 partial_sort(_RAIter
, _RAIter
, _RAIter
, _Compare
);
824 template<typename _BIter
, typename _Predicate
>
827 partition(_BIter
, _BIter
, _Predicate
);
830 template<typename _RAIter
>
831 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
833 random_shuffle(_RAIter
, _RAIter
);
835 template<typename _RAIter
, typename _Generator
>
836 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
838 random_shuffle(_RAIter
, _RAIter
,
839 #if __cplusplus >= 201103L
846 template<typename _FIter
, typename _Tp
>
849 replace(_FIter
, _FIter
, const _Tp
&, const _Tp
&);
851 template<typename _FIter
, typename _Predicate
, typename _Tp
>
854 replace_if(_FIter
, _FIter
, _Predicate
, const _Tp
&);
856 template<typename _FIter1
, typename _FIter2
>
859 search(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
861 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
864 search(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
866 template<typename _FIter
, typename _Size
, typename _Tp
>
869 search_n(_FIter
, _FIter
, _Size
, const _Tp
&);
871 template<typename _FIter
, typename _Size
, typename _Tp
,
872 typename _BinaryPredicate
>
875 search_n(_FIter
, _FIter
, _Size
, const _Tp
&, _BinaryPredicate
);
877 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
880 set_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
882 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
886 set_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
888 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
891 set_intersection(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
893 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
897 set_intersection(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
899 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
902 set_symmetric_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
904 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
908 set_symmetric_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
,
911 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
914 set_union(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
916 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
920 set_union(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
922 template<typename _RAIter
>
925 sort(_RAIter
, _RAIter
);
927 template<typename _RAIter
, typename _Compare
>
930 sort(_RAIter
, _RAIter
, _Compare
);
932 template<typename _RAIter
>
934 stable_sort(_RAIter
, _RAIter
);
936 template<typename _RAIter
, typename _Compare
>
938 stable_sort(_RAIter
, _RAIter
, _Compare
);
940 template<typename _IIter
, typename _OIter
, typename _UnaryOperation
>
943 transform(_IIter
, _IIter
, _OIter
, _UnaryOperation
);
945 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
946 typename _BinaryOperation
>
949 transform(_IIter1
, _IIter1
, _IIter2
, _OIter
, _BinaryOperation
);
951 template<typename _IIter
, typename _OIter
>
954 unique_copy(_IIter
, _IIter
, _OIter
);
956 template<typename _IIter
, typename _OIter
, typename _BinaryPredicate
>
959 unique_copy(_IIter
, _IIter
, _OIter
, _BinaryPredicate
);
961 _GLIBCXX_END_NAMESPACE_ALGO
962 _GLIBCXX_END_NAMESPACE_VERSION
965 #ifdef _GLIBCXX_PARALLEL
966 # include <parallel/algorithmfwd.h>