1 // <algorithm> Forward declarations -*- C++ -*-
3 // Copyright (C) 2007-2013 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
73 is_partitioned (C++0x)
75 is_sorted_until (C++0x)
77 lexicographical_compare
86 minmax_element (C++0x)
94 partition_copy (C++0x)
95 partition_point (C++0x)
116 set_symmetric_difference
132 * @defgroup algorithms Algorithms
134 * Components for performing algorithmic operations. Includes
135 * non-modifying sequence, modifying (mutating) sequence, sorting,
136 * searching, merge, partition, heap, set, minima, maxima, and
137 * permutation operations.
141 * @defgroup mutating_algorithms Mutating
142 * @ingroup algorithms
146 * @defgroup non_mutating_algorithms Non-Mutating
147 * @ingroup algorithms
151 * @defgroup sorting_algorithms Sorting
152 * @ingroup algorithms
156 * @defgroup set_algorithms Set Operation
157 * @ingroup sorting_algorithms
159 * These algorithms are common set operations performed on sequences
160 * that are already sorted. The number of comparisons will be
165 * @defgroup binary_search_algorithms Binary Search
166 * @ingroup sorting_algorithms
168 * These algorithms are variations of a classic binary search, and
169 * all assume that the sequence being searched is already sorted.
171 * The number of comparisons will be logarithmic (and as few as
172 * possible). The number of steps through the sequence will be
173 * logarithmic for random-access iterators (e.g., pointers), and
176 * The LWG has passed Defect Report 270, which notes: <em>The
177 * proposed resolution reinterprets binary search. Instead of
178 * thinking about searching for a value in a sorted range, we view
179 * that as an important special case of a more general algorithm:
180 * searching for the partition point in a partitioned range. We
181 * also add a guarantee that the old wording did not: we ensure that
182 * the upper bound is no earlier than the lower bound, that the pair
183 * returned by equal_range is a valid range, and that the first part
184 * of that pair is the lower bound.</em>
186 * The actual effect of the first sentence is that a comparison
187 * functor passed by the user doesn't necessarily need to induce a
188 * strict weak ordering relation. Rather, it partitions the range.
193 #if __cplusplus >= 201103L
194 template<typename _IIter, typename _Predicate>
196 all_of(_IIter, _IIter, _Predicate);
198 template<typename _IIter, typename _Predicate>
200 any_of(_IIter, _IIter, _Predicate);
203 template<typename _FIter, typename _Tp>
205 binary_search(_FIter, _FIter, const _Tp&);
207 template<typename _FIter, typename _Tp, typename _Compare>
209 binary_search(_FIter, _FIter, const _Tp&, _Compare);
211 template<typename _IIter, typename _OIter>
213 copy(_IIter, _IIter, _OIter);
215 template<typename _BIter1, typename _BIter2>
217 copy_backward(_BIter1, _BIter1, _BIter2);
219 #if __cplusplus >= 201103L
220 template<typename _IIter, typename _OIter, typename _Predicate>
222 copy_if(_IIter, _IIter, _OIter, _Predicate);
224 template<typename _IIter, typename _Size, typename _OIter>
226 copy_n(_IIter, _Size, _OIter);
232 template<typename _FIter, typename _Tp>
234 equal_range(_FIter, _FIter, const _Tp&);
236 template<typename _FIter, typename _Tp, typename _Compare>
238 equal_range(_FIter, _FIter, const _Tp&, _Compare);
240 template<typename _FIter, typename _Tp>
242 fill(_FIter, _FIter, const _Tp&);
244 template<typename _OIter, typename _Size, typename _Tp>
246 fill_n(_OIter, _Size, const _Tp&);
250 template<typename _FIter1, typename _FIter2>
252 find_end(_FIter1, _FIter1, _FIter2, _FIter2);
254 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
256 find_end(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
261 #if __cplusplus >= 201103L
262 template<typename _IIter, typename _Predicate>
264 find_if_not(_IIter, _IIter, _Predicate);
271 template<typename _IIter1, typename _IIter2>
273 includes(_IIter1, _IIter1, _IIter2, _IIter2);
275 template<typename _IIter1, typename _IIter2, typename _Compare>
277 includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
279 template<typename _BIter>
281 inplace_merge(_BIter, _BIter, _BIter);
283 template<typename _BIter, typename _Compare>
285 inplace_merge(_BIter, _BIter, _BIter, _Compare);
287 #if __cplusplus >= 201103L
288 template<typename _RAIter>
290 is_heap(_RAIter, _RAIter);
292 template<typename _RAIter, typename _Compare>
294 is_heap(_RAIter, _RAIter, _Compare);
296 template<typename _RAIter>
298 is_heap_until(_RAIter, _RAIter);
300 template<typename _RAIter, typename _Compare>
302 is_heap_until(_RAIter, _RAIter, _Compare);
304 template<typename _IIter, typename _Predicate>
306 is_partitioned(_IIter, _IIter, _Predicate);
308 template<typename _FIter1, typename _FIter2>
310 is_permutation(_FIter1, _FIter1, _FIter2);
312 template<typename _FIter1, typename _FIter2,
313 typename _BinaryPredicate>
315 is_permutation(_FIter1, _FIter1, _FIter2, _BinaryPredicate);
317 template<typename _FIter>
319 is_sorted(_FIter, _FIter);
321 template<typename _FIter, typename _Compare>
323 is_sorted(_FIter, _FIter, _Compare);
325 template<typename _FIter>
327 is_sorted_until(_FIter, _FIter);
329 template<typename _FIter, typename _Compare>
331 is_sorted_until(_FIter, _FIter, _Compare);
334 template<typename _FIter1, typename _FIter2>
336 iter_swap(_FIter1, _FIter2);
338 template<typename _FIter, typename _Tp>
340 lower_bound(_FIter, _FIter, const _Tp&);
342 template<typename _FIter, typename _Tp, typename _Compare>
344 lower_bound(_FIter, _FIter, const _Tp&, _Compare);
346 template<typename _RAIter>
348 make_heap(_RAIter, _RAIter);
350 template<typename _RAIter, typename _Compare>
352 make_heap(_RAIter, _RAIter, _Compare);
354 template<typename _Tp>
356 max(const _Tp&, const _Tp&);
358 template<typename _Tp, typename _Compare>
360 max(const _Tp&, const _Tp&, _Compare);
365 template<typename _Tp>
367 min(const _Tp&, const _Tp&);
369 template<typename _Tp, typename _Compare>
371 min(const _Tp&, const _Tp&, _Compare);
375 #if __cplusplus >= 201103L
376 template<typename _Tp>
377 pair<const _Tp&, const _Tp&>
378 minmax(const _Tp&, const _Tp&);
380 template<typename _Tp, typename _Compare>
381 pair<const _Tp&, const _Tp&>
382 minmax(const _Tp&, const _Tp&, _Compare);
384 template<typename _FIter>
386 minmax_element(_FIter, _FIter);
388 template<typename _FIter, typename _Compare>
390 minmax_element(_FIter, _FIter, _Compare);
392 template<typename _Tp>
394 min(initializer_list<_Tp>);
396 template<typename _Tp, typename _Compare>
398 min(initializer_list<_Tp>, _Compare);
400 template<typename _Tp>
402 max(initializer_list<_Tp>);
404 template<typename _Tp, typename _Compare>
406 max(initializer_list<_Tp>, _Compare);
408 template<typename _Tp>
410 minmax(initializer_list<_Tp>);
412 template<typename _Tp, typename _Compare>
414 minmax(initializer_list<_Tp>, _Compare);
419 template<typename _BIter>
421 next_permutation(_BIter, _BIter);
423 template<typename _BIter, typename _Compare>
425 next_permutation(_BIter, _BIter, _Compare);
427 #if __cplusplus >= 201103L
428 template<typename _IIter, typename _Predicate>
430 none_of(_IIter, _IIter, _Predicate);
436 template<typename _IIter, typename _RAIter>
438 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter);
440 template<typename _IIter, typename _RAIter, typename _Compare>
442 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter, _Compare);
446 #if __cplusplus >= 201103L
447 template<typename _IIter, typename _OIter1,
448 typename _OIter2, typename _Predicate>
449 pair<_OIter1, _OIter2>
450 partition_copy(_IIter, _IIter, _OIter1, _OIter2, _Predicate);
452 template<typename _FIter, typename _Predicate>
454 partition_point(_FIter, _FIter, _Predicate);
457 template<typename _RAIter>
459 pop_heap(_RAIter, _RAIter);
461 template<typename _RAIter, typename _Compare>
463 pop_heap(_RAIter, _RAIter, _Compare);
465 template<typename _BIter>
467 prev_permutation(_BIter, _BIter);
469 template<typename _BIter, typename _Compare>
471 prev_permutation(_BIter, _BIter, _Compare);
473 template<typename _RAIter>
475 push_heap(_RAIter, _RAIter);
477 template<typename _RAIter, typename _Compare>
479 push_heap(_RAIter, _RAIter, _Compare);
483 template<typename _FIter, typename _Tp>
485 remove(_FIter, _FIter, const _Tp&);
487 template<typename _FIter, typename _Predicate>
489 remove_if(_FIter, _FIter, _Predicate);
491 template<typename _IIter, typename _OIter, typename _Tp>
493 remove_copy(_IIter, _IIter, _OIter, const _Tp&);
495 template<typename _IIter, typename _OIter, typename _Predicate>
497 remove_copy_if(_IIter, _IIter, _OIter, _Predicate);
501 template<typename _IIter, typename _OIter, typename _Tp>
503 replace_copy(_IIter, _IIter, _OIter, const _Tp&, const _Tp&);
505 template<typename _Iter, typename _OIter, typename _Predicate, typename _Tp>
507 replace_copy_if(_Iter, _Iter, _OIter, _Predicate, const _Tp&);
511 template<typename _BIter>
513 reverse(_BIter, _BIter);
515 template<typename _BIter, typename _OIter>
517 reverse_copy(_BIter, _BIter, _OIter);
519 template<typename _FIter>
521 rotate(_FIter, _FIter, _FIter);
523 template<typename _FIter, typename _OIter>
525 rotate_copy(_FIter, _FIter, _FIter, _OIter);
531 // set_symmetric_difference
534 #if (__cplusplus >= 201103L) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
535 template<typename _RAIter, typename _UGenerator>
537 shuffle(_RAIter, _RAIter, _UGenerator&&);
540 template<typename _RAIter>
542 sort_heap(_RAIter, _RAIter);
544 template<typename _RAIter, typename _Compare>
546 sort_heap(_RAIter, _RAIter, _Compare);
548 template<typename _BIter, typename _Predicate>
550 stable_partition(_BIter, _BIter, _Predicate);
552 template<typename _Tp>
555 #if __cplusplus >= 201103L
556 noexcept(__and_<is_nothrow_move_constructible<_Tp>,
557 is_nothrow_move_assignable<_Tp>>::value)
561 template<typename _Tp, size_t _Nm>
563 swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
564 #if __cplusplus >= 201103L
565 noexcept(noexcept(swap(*__a, *__b)))
569 template<typename _FIter1, typename _FIter2>
571 swap_ranges(_FIter1, _FIter1, _FIter2);
575 template<typename _FIter>
577 unique(_FIter, _FIter);
579 template<typename _FIter, typename _BinaryPredicate>
581 unique(_FIter, _FIter, _BinaryPredicate);
585 template<typename _FIter, typename _Tp>
587 upper_bound(_FIter, _FIter, const _Tp&);
589 template<typename _FIter, typename _Tp, typename _Compare>
591 upper_bound(_FIter, _FIter, const _Tp&, _Compare);
593 _GLIBCXX_END_NAMESPACE_VERSION
595 _GLIBCXX_BEGIN_NAMESPACE_ALGO
597 template<typename _FIter>
599 adjacent_find(_FIter, _FIter);
601 template<typename _FIter, typename _BinaryPredicate>
603 adjacent_find(_FIter, _FIter, _BinaryPredicate);
605 template<typename _IIter, typename _Tp>
606 typename iterator_traits<_IIter>::difference_type
607 count(_IIter, _IIter, const _Tp&);
609 template<typename _IIter, typename _Predicate>
610 typename iterator_traits<_IIter>::difference_type
611 count_if(_IIter, _IIter, _Predicate);
613 template<typename _IIter1, typename _IIter2>
615 equal(_IIter1, _IIter1, _IIter2);
617 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
619 equal(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
621 template<typename _IIter, typename _Tp>
623 find(_IIter, _IIter, const _Tp&);
625 template<typename _FIter1, typename _FIter2>
627 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2);
629 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
631 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
633 template<typename _IIter, typename _Predicate>
635 find_if(_IIter, _IIter, _Predicate);
637 template<typename _IIter, typename _Funct>
639 for_each(_IIter, _IIter, _Funct);
641 template<typename _FIter, typename _Generator>
643 generate(_FIter, _FIter, _Generator);
645 template<typename _OIter, typename _Size, typename _Generator>
647 generate_n(_OIter, _Size, _Generator);
649 template<typename _IIter1, typename _IIter2>
651 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
653 template<typename _IIter1, typename _IIter2, typename _Compare>
655 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
657 template<typename _FIter>
659 max_element(_FIter, _FIter);
661 template<typename _FIter, typename _Compare>
663 max_element(_FIter, _FIter, _Compare);
665 template<typename _IIter1, typename _IIter2, typename _OIter>
667 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
669 template<typename _IIter1, typename _IIter2, typename _OIter,
672 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
674 template<typename _FIter>
676 min_element(_FIter, _FIter);
678 template<typename _FIter, typename _Compare>
680 min_element(_FIter, _FIter, _Compare);
682 template<typename _IIter1, typename _IIter2>
683 pair<_IIter1, _IIter2>
684 mismatch(_IIter1, _IIter1, _IIter2);
686 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
687 pair<_IIter1, _IIter2>
688 mismatch(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
690 template<typename _RAIter>
692 nth_element(_RAIter, _RAIter, _RAIter);
694 template<typename _RAIter, typename _Compare>
696 nth_element(_RAIter, _RAIter, _RAIter, _Compare);
698 template<typename _RAIter>
700 partial_sort(_RAIter, _RAIter, _RAIter);
702 template<typename _RAIter, typename _Compare>
704 partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
706 template<typename _BIter, typename _Predicate>
708 partition(_BIter, _BIter, _Predicate);
710 template<typename _RAIter>
712 random_shuffle(_RAIter, _RAIter);
714 template<typename _RAIter, typename _Generator>
716 random_shuffle(_RAIter, _RAIter,
717 #if __cplusplus >= 201103L
723 template<typename _FIter, typename _Tp>
725 replace(_FIter, _FIter, const _Tp&, const _Tp&);
727 template<typename _FIter, typename _Predicate, typename _Tp>
729 replace_if(_FIter, _FIter, _Predicate, const _Tp&);
731 template<typename _FIter1, typename _FIter2>
733 search(_FIter1, _FIter1, _FIter2, _FIter2);
735 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
737 search(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
739 template<typename _FIter, typename _Size, typename _Tp>
741 search_n(_FIter, _FIter, _Size, const _Tp&);
743 template<typename _FIter, typename _Size, typename _Tp,
744 typename _BinaryPredicate>
746 search_n(_FIter, _FIter, _Size, const _Tp&, _BinaryPredicate);
748 template<typename _IIter1, typename _IIter2, typename _OIter>
750 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
752 template<typename _IIter1, typename _IIter2, typename _OIter,
755 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
757 template<typename _IIter1, typename _IIter2, typename _OIter>
759 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
761 template<typename _IIter1, typename _IIter2, typename _OIter,
764 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
766 template<typename _IIter1, typename _IIter2, typename _OIter>
768 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
770 template<typename _IIter1, typename _IIter2, typename _OIter,
773 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2,
776 template<typename _IIter1, typename _IIter2, typename _OIter>
778 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
780 template<typename _IIter1, typename _IIter2, typename _OIter,
783 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
785 template<typename _RAIter>
787 sort(_RAIter, _RAIter);
789 template<typename _RAIter, typename _Compare>
791 sort(_RAIter, _RAIter, _Compare);
793 template<typename _RAIter>
795 stable_sort(_RAIter, _RAIter);
797 template<typename _RAIter, typename _Compare>
799 stable_sort(_RAIter, _RAIter, _Compare);
801 template<typename _IIter, typename _OIter, typename _UnaryOperation>
803 transform(_IIter, _IIter, _OIter, _UnaryOperation);
805 template<typename _IIter1, typename _IIter2, typename _OIter,
806 typename _BinaryOperation>
808 transform(_IIter1, _IIter1, _IIter2, _OIter, _BinaryOperation);
810 template<typename _IIter, typename _OIter>
812 unique_copy(_IIter, _IIter, _OIter);
814 template<typename _IIter, typename _OIter, typename _BinaryPredicate>
816 unique_copy(_IIter, _IIter, _OIter, _BinaryPredicate);
818 _GLIBCXX_END_NAMESPACE_ALGO
821 #ifdef _GLIBCXX_PARALLEL
822 # include <parallel/algorithmfwd.h>