1 // <algorithm> declarations -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010 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 * You should not attempt to use it directly.
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 #include <initializer_list>
40 _GLIBCXX_BEGIN_NAMESPACE(std)
69 is_partitioned (C++0x)
71 is_sorted_until (C++0x)
73 lexicographical_compare
82 minmax_element (C++0x)
90 partition_copy (C++0x)
91 partition_point (C++0x)
112 set_symmetric_difference
128 * @defgroup algorithms Algorithms
130 * Components for performing algorithmic operations. Includes
131 * non-modifying sequence, modifying (mutating) sequence, sorting,
132 * searching, merge, partition, heap, set, minima, maxima, and
133 * permutation operations.
137 * @defgroup mutating_algorithms Mutating Algorithms
138 * @ingroup algorithms
142 * @defgroup non_mutating_algorithms Non-Mutating Algorithms
143 * @ingroup algorithms
147 * @defgroup sorting_algorithms Sorting Algorithms
148 * @ingroup algorithms
152 * @defgroup set_algorithms Set Operation Algorithms
153 * @ingroup sorting_algorithms
155 * These algorithms are common set operations performed on sequences
156 * that are already sorted. The number of comparisons will be
161 * @defgroup binary_search_algorithms Binary Search Algorithms
162 * @ingroup sorting_algorithms
164 * These algorithms are variations of a classic binary search, and
165 * all assume that the sequence being searched is already sorted.
167 * The number of comparisons will be logarithmic (and as few as
168 * possible). The number of steps through the sequence will be
169 * logarithmic for random-access iterators (e.g., pointers), and
172 * The LWG has passed Defect Report 270, which notes: <em>The
173 * proposed resolution reinterprets binary search. Instead of
174 * thinking about searching for a value in a sorted range, we view
175 * that as an important special case of a more general algorithm:
176 * searching for the partition point in a partitioned range. We
177 * also add a guarantee that the old wording did not: we ensure that
178 * the upper bound is no earlier than the lower bound, that the pair
179 * returned by equal_range is a valid range, and that the first part
180 * of that pair is the lower bound.</em>
182 * The actual effect of the first sentence is that a comparison
183 * functor passed by the user doesn't necessarily need to induce a
184 * strict weak ordering relation. Rather, it partitions the range.
189 #ifdef __GXX_EXPERIMENTAL_CXX0X__
190 template<typename _IIter, typename _Predicate>
192 all_of(_IIter, _IIter, _Predicate);
194 template<typename _IIter, typename _Predicate>
196 any_of(_IIter, _IIter, _Predicate);
199 template<typename _FIter, typename _Tp>
201 binary_search(_FIter, _FIter, const _Tp&);
203 template<typename _FIter, typename _Tp, typename _Compare>
205 binary_search(_FIter, _FIter, const _Tp&, _Compare);
207 template<typename _IIter, typename _OIter>
209 copy(_IIter, _IIter, _OIter);
211 template<typename _BIter1, typename _BIter2>
213 copy_backward(_BIter1, _BIter1, _BIter2);
215 #ifdef __GXX_EXPERIMENTAL_CXX0X__
216 template<typename _IIter, typename _OIter, typename _Predicate>
218 copy_if(_IIter, _IIter, _OIter, _Predicate);
220 template<typename _IIter, typename _Size, typename _OIter>
222 copy_n(_IIter, _Size, _OIter);
228 template<typename _FIter, typename _Tp>
230 equal_range(_FIter, _FIter, const _Tp&);
232 template<typename _FIter, typename _Tp, typename _Compare>
234 equal_range(_FIter, _FIter, const _Tp&, _Compare);
236 template<typename _FIter, typename _Tp>
238 fill(_FIter, _FIter, const _Tp&);
240 template<typename _OIter, typename _Size, typename _Tp>
242 fill_n(_OIter, _Size, const _Tp&);
246 template<typename _FIter1, typename _FIter2>
248 find_end(_FIter1, _FIter1, _FIter2, _FIter2);
250 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
252 find_end(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
257 #ifdef __GXX_EXPERIMENTAL_CXX0X__
258 template<typename _IIter, typename _Predicate>
260 find_if_not(_IIter, _IIter, _Predicate);
267 template<typename _IIter1, typename _IIter2>
269 includes(_IIter1, _IIter1, _IIter2, _IIter2);
271 template<typename _IIter1, typename _IIter2, typename _Compare>
273 includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
275 template<typename _BIter>
277 inplace_merge(_BIter, _BIter, _BIter);
279 template<typename _BIter, typename _Compare>
281 inplace_merge(_BIter, _BIter, _BIter, _Compare);
283 #ifdef __GXX_EXPERIMENTAL_CXX0X__
284 template<typename _RAIter>
286 is_heap(_RAIter, _RAIter);
288 template<typename _RAIter, typename _Compare>
290 is_heap(_RAIter, _RAIter, _Compare);
292 template<typename _RAIter>
294 is_heap_until(_RAIter, _RAIter);
296 template<typename _RAIter, typename _Compare>
298 is_heap_until(_RAIter, _RAIter, _Compare);
300 template<typename _IIter, typename _Predicate>
302 is_partitioned(_IIter, _IIter, _Predicate);
304 template<typename _FIter>
306 is_sorted(_FIter, _FIter);
308 template<typename _FIter, typename _Compare>
310 is_sorted(_FIter, _FIter, _Compare);
312 template<typename _FIter>
314 is_sorted_until(_FIter, _FIter);
316 template<typename _FIter, typename _Compare>
318 is_sorted_until(_FIter, _FIter, _Compare);
321 template<typename _FIter1, typename _FIter2>
323 iter_swap(_FIter1, _FIter2);
325 template<typename _FIter, typename _Tp>
327 lower_bound(_FIter, _FIter, const _Tp&);
329 template<typename _FIter, typename _Tp, typename _Compare>
331 lower_bound(_FIter, _FIter, const _Tp&, _Compare);
333 template<typename _RAIter>
335 make_heap(_RAIter, _RAIter);
337 template<typename _RAIter, typename _Compare>
339 make_heap(_RAIter, _RAIter, _Compare);
341 template<typename _Tp>
343 max(const _Tp&, const _Tp&);
345 template<typename _Tp, typename _Compare>
347 max(const _Tp&, const _Tp&, _Compare);
352 template<typename _Tp>
354 min(const _Tp&, const _Tp&);
356 template<typename _Tp, typename _Compare>
358 min(const _Tp&, const _Tp&, _Compare);
362 #ifdef __GXX_EXPERIMENTAL_CXX0X__
363 template<typename _Tp>
364 pair<const _Tp&, const _Tp&>
365 minmax(const _Tp&, const _Tp&);
367 template<typename _Tp, typename _Compare>
368 pair<const _Tp&, const _Tp&>
369 minmax(const _Tp&, const _Tp&, _Compare);
371 template<typename _FIter>
373 minmax_element(_FIter, _FIter);
375 template<typename _FIter, typename _Compare>
377 minmax_element(_FIter, _FIter, _Compare);
379 template<typename _Tp>
381 min(initializer_list<_Tp>);
383 template<typename _Tp, typename _Compare>
385 min(initializer_list<_Tp>, _Compare);
387 template<typename _Tp>
389 max(initializer_list<_Tp>);
391 template<typename _Tp, typename _Compare>
393 max(initializer_list<_Tp>, _Compare);
395 template<typename _Tp>
397 minmax(initializer_list<_Tp>);
399 template<typename _Tp, typename _Compare>
401 minmax(initializer_list<_Tp>, _Compare);
406 template<typename _BIter>
408 next_permutation(_BIter, _BIter);
410 template<typename _BIter, typename _Compare>
412 next_permutation(_BIter, _BIter, _Compare);
414 #ifdef __GXX_EXPERIMENTAL_CXX0X__
415 template<typename _IIter, typename _Predicate>
417 none_of(_IIter, _IIter, _Predicate);
423 template<typename _IIter, typename _RAIter>
425 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter);
427 template<typename _IIter, typename _RAIter, typename _Compare>
429 partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter, _Compare);
433 #ifdef __GXX_EXPERIMENTAL_CXX0X__
434 template<typename _IIter, typename _OIter1,
435 typename _OIter2, typename _Predicate>
436 pair<_OIter1, _OIter2>
437 partition_copy(_IIter, _IIter, _OIter1, _OIter2, _Predicate);
439 template<typename _FIter, typename _Predicate>
441 partition_point(_FIter, _FIter, _Predicate);
444 template<typename _RAIter>
446 pop_heap(_RAIter, _RAIter);
448 template<typename _RAIter, typename _Compare>
450 pop_heap(_RAIter, _RAIter, _Compare);
452 template<typename _BIter>
454 prev_permutation(_BIter, _BIter);
456 template<typename _BIter, typename _Compare>
458 prev_permutation(_BIter, _BIter, _Compare);
460 template<typename _RAIter>
462 push_heap(_RAIter, _RAIter);
464 template<typename _RAIter, typename _Compare>
466 push_heap(_RAIter, _RAIter, _Compare);
470 template<typename _FIter, typename _Tp>
472 remove(_FIter, _FIter, const _Tp&);
474 template<typename _FIter, typename _Predicate>
476 remove_if(_FIter, _FIter, _Predicate);
478 template<typename _IIter, typename _OIter, typename _Tp>
480 remove_copy(_IIter, _IIter, _OIter, const _Tp&);
482 template<typename _IIter, typename _OIter, typename _Predicate>
484 remove_copy_if(_IIter, _IIter, _OIter, _Predicate);
488 template<typename _IIter, typename _OIter, typename _Tp>
490 replace_copy(_IIter, _IIter, _OIter, const _Tp&, const _Tp&);
492 template<typename _Iter, typename _OIter, typename _Predicate, typename _Tp>
494 replace_copy_if(_Iter, _Iter, _OIter, _Predicate, const _Tp&);
498 template<typename _BIter>
500 reverse(_BIter, _BIter);
502 template<typename _BIter, typename _OIter>
504 reverse_copy(_BIter, _BIter, _OIter);
506 template<typename _FIter>
508 rotate(_FIter, _FIter, _FIter);
510 template<typename _FIter, typename _OIter>
512 rotate_copy(_FIter, _FIter, _FIter, _OIter);
518 // set_symmetric_difference
521 #if defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99_STDINT_TR1)
522 template<typename _RAIter, typename _UGenerator>
524 shuffle(_RAIter, _RAIter, _UGenerator&);
527 template<typename _RAIter>
529 sort_heap(_RAIter, _RAIter);
531 template<typename _RAIter, typename _Compare>
533 sort_heap(_RAIter, _RAIter, _Compare);
535 template<typename _BIter, typename _Predicate>
537 stable_partition(_BIter, _BIter, _Predicate);
539 template<typename _Tp>
543 template<typename _Tp, size_t _Nm>
545 swap(_Tp (&)[_Nm], _Tp (&)[_Nm]);
547 template<typename _FIter1, typename _FIter2>
549 swap_ranges(_FIter1, _FIter1, _FIter2);
553 template<typename _FIter>
555 unique(_FIter, _FIter);
557 template<typename _FIter, typename _BinaryPredicate>
559 unique(_FIter, _FIter, _BinaryPredicate);
563 template<typename _FIter, typename _Tp>
565 upper_bound(_FIter, _FIter, const _Tp&);
567 template<typename _FIter, typename _Tp, typename _Compare>
569 upper_bound(_FIter, _FIter, const _Tp&, _Compare);
571 _GLIBCXX_END_NAMESPACE
573 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
575 template<typename _FIter>
577 adjacent_find(_FIter, _FIter);
579 template<typename _FIter, typename _BinaryPredicate>
581 adjacent_find(_FIter, _FIter, _BinaryPredicate);
583 template<typename _IIter, typename _Tp>
584 typename iterator_traits<_IIter>::difference_type
585 count(_IIter, _IIter, const _Tp&);
587 template<typename _IIter, typename _Predicate>
588 typename iterator_traits<_IIter>::difference_type
589 count_if(_IIter, _IIter, _Predicate);
591 template<typename _IIter1, typename _IIter2>
593 equal(_IIter1, _IIter1, _IIter2);
595 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
597 equal(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
599 template<typename _IIter, typename _Tp>
601 find(_IIter, _IIter, const _Tp&);
603 template<typename _FIter1, typename _FIter2>
605 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2);
607 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
609 find_first_of(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
611 template<typename _IIter, typename _Predicate>
613 find_if(_IIter, _IIter, _Predicate);
615 template<typename _IIter, typename _Funct>
617 for_each(_IIter, _IIter, _Funct);
619 template<typename _FIter, typename _Generator>
621 generate(_FIter, _FIter, _Generator);
623 template<typename _OIter, typename _Size, typename _Generator>
625 generate_n(_OIter, _Size, _Generator);
627 template<typename _IIter1, typename _IIter2>
629 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
631 template<typename _IIter1, typename _IIter2, typename _Compare>
633 lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
635 template<typename _FIter>
637 max_element(_FIter, _FIter);
639 template<typename _FIter, typename _Compare>
641 max_element(_FIter, _FIter, _Compare);
643 template<typename _IIter1, typename _IIter2, typename _OIter>
645 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
647 template<typename _IIter1, typename _IIter2, typename _OIter,
650 merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
652 template<typename _FIter>
654 min_element(_FIter, _FIter);
656 template<typename _FIter, typename _Compare>
658 min_element(_FIter, _FIter, _Compare);
660 template<typename _IIter1, typename _IIter2>
661 pair<_IIter1, _IIter2>
662 mismatch(_IIter1, _IIter1, _IIter2);
664 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
665 pair<_IIter1, _IIter2>
666 mismatch(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
668 template<typename _RAIter>
670 nth_element(_RAIter, _RAIter, _RAIter);
672 template<typename _RAIter, typename _Compare>
674 nth_element(_RAIter, _RAIter, _RAIter, _Compare);
676 template<typename _RAIter>
678 partial_sort(_RAIter, _RAIter, _RAIter);
680 template<typename _RAIter, typename _Compare>
682 partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
684 template<typename _BIter, typename _Predicate>
686 partition(_BIter, _BIter, _Predicate);
688 template<typename _RAIter>
690 random_shuffle(_RAIter, _RAIter);
692 template<typename _RAIter, typename _Generator>
694 random_shuffle(_RAIter, _RAIter,
695 #ifdef __GXX_EXPERIMENTAL_CXX0X__
701 template<typename _FIter, typename _Tp>
703 replace(_FIter, _FIter, const _Tp&, const _Tp&);
705 template<typename _FIter, typename _Predicate, typename _Tp>
707 replace_if(_FIter, _FIter, _Predicate, const _Tp&);
709 template<typename _FIter1, typename _FIter2>
711 search(_FIter1, _FIter1, _FIter2, _FIter2);
713 template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
715 search(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
717 template<typename _FIter, typename _Size, typename _Tp>
719 search_n(_FIter, _FIter, _Size, const _Tp&);
721 template<typename _FIter, typename _Size, typename _Tp,
722 typename _BinaryPredicate>
724 search_n(_FIter, _FIter, _Size, const _Tp&, _BinaryPredicate);
726 template<typename _IIter1, typename _IIter2, typename _OIter>
728 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
730 template<typename _IIter1, typename _IIter2, typename _OIter,
733 set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
735 template<typename _IIter1, typename _IIter2, typename _OIter>
737 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
739 template<typename _IIter1, typename _IIter2, typename _OIter,
742 set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
744 template<typename _IIter1, typename _IIter2, typename _OIter>
746 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
748 template<typename _IIter1, typename _IIter2, typename _OIter,
751 set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2,
754 template<typename _IIter1, typename _IIter2, typename _OIter>
756 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
758 template<typename _IIter1, typename _IIter2, typename _OIter,
761 set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
763 template<typename _RAIter>
765 sort(_RAIter, _RAIter);
767 template<typename _RAIter, typename _Compare>
769 sort(_RAIter, _RAIter, _Compare);
771 template<typename _RAIter>
773 stable_sort(_RAIter, _RAIter);
775 template<typename _RAIter, typename _Compare>
777 stable_sort(_RAIter, _RAIter, _Compare);
779 template<typename _IIter, typename _OIter, typename _UnaryOperation>
781 transform(_IIter, _IIter, _OIter, _UnaryOperation);
783 template<typename _IIter1, typename _IIter2, typename _OIter,
784 typename _BinaryOperation>
786 transform(_IIter1, _IIter1, _IIter2, _OIter, _BinaryOperation);
788 template<typename _IIter, typename _OIter>
790 unique_copy(_IIter, _IIter, _OIter);
792 template<typename _IIter, typename _OIter, typename _BinaryPredicate>
794 unique_copy(_IIter, _IIter, _OIter, _BinaryPredicate);
796 _GLIBCXX_END_NESTED_NAMESPACE
798 #ifdef _GLIBCXX_NAMESPACE_ASSOCIATION_PARALLEL
799 # include <parallel/algorithmfwd.h>