3 // Copyright (C) 2007-2021 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 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
24 // 25.1, non-modifying sequence operations:
25 template<typename _IIter
, typename _Funct
>
28 for_each(_IIter
, _IIter
, _Funct
);
30 template<typename _IIter
, typename _Tp
>
33 find(_IIter
, _IIter
, const _Tp
&);
35 template<typename _IIter
, typename _Predicate
>
38 find_if(_IIter
, _IIter
, _Predicate
);
40 #if __cplusplus >= 201103L
41 template<typename _IIter
, typename _Predicate
>
44 all_of(_IIter
, _IIter
, _Predicate
);
46 template<typename _IIter
, typename _Predicate
>
49 any_of(_IIter
, _IIter
, _Predicate
);
51 template<typename _IIter
, typename _Predicate
>
54 none_of(_IIter
, _IIter
, _Predicate
);
56 template<typename _IIter
, typename _Predicate
>
59 find_if_not(_IIter
, _IIter
, _Predicate
);
61 template<typename _IIter
, typename _Predicate
>
64 is_partitioned(_IIter
, _IIter
, _Predicate
);
66 template<typename _FIter
, typename _Predicate
>
69 partition_point(_FIter
, _FIter
, _Predicate
);
72 template<typename _FIter1
, typename _FIter2
>
75 find_end(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
77 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
80 find_end(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
82 template<typename _FIter1
, typename _FIter2
>
85 find_first_of(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
87 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
90 find_first_of(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
92 template<typename _FIter
>
95 adjacent_find(_FIter
, _FIter
);
97 template<typename _FIter
, typename _BinaryPredicate
>
100 adjacent_find(_FIter
, _FIter
, _BinaryPredicate
);
102 template<typename _IIter
, typename _Tp
>
104 typename iterator_traits
<_IIter
>::difference_type
105 count(_IIter
, _IIter
, const _Tp
&);
107 template<typename _IIter
, typename _Predicate
>
109 typename iterator_traits
<_IIter
>::difference_type
110 count_if(_IIter
, _IIter
, _Predicate
);
112 template<typename _IIter1
, typename _IIter2
>
114 pair
<_IIter1
, _IIter2
>
115 mismatch(_IIter1
, _IIter1
, _IIter2
);
117 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
119 pair
<_IIter1
, _IIter2
>
120 mismatch(_IIter1
, _IIter1
, _IIter2
, _BinaryPredicate
);
122 template<typename _IIter1
, typename _IIter2
>
125 equal(_IIter1
, _IIter1
, _IIter2
);
127 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
130 equal(_IIter1
, _IIter1
, _IIter2
, _BinaryPredicate
);
132 template<typename _FIter1
, typename _FIter2
>
135 search(_FIter1
, _FIter1
, _FIter2
, _FIter2
);
137 template<typename _FIter1
, typename _FIter2
, typename _BinaryPredicate
>
140 search(_FIter1
, _FIter1
, _FIter2
, _FIter2
, _BinaryPredicate
);
142 template<typename _FIter
, typename _Size
, typename _Tp
>
145 search_n(_FIter
, _FIter
, _Size
, const _Tp
&);
147 template<typename _FIter
, typename _Size
, typename _Tp
,
148 typename _BinaryPredicate
>
151 search_n(_FIter
, _FIter
, _Size
, const _Tp
&, _BinaryPredicate
);
153 // 25.2, modifying sequence operations:
155 template<typename _IIter
, typename _OIter
>
158 copy(_IIter
, _IIter
, _OIter
);
160 template<typename _BIter1
, typename _BIter2
>
163 copy_backward (_BIter1
, _BIter1
, _BIter2
);
166 #if __cplusplus < 201103L
167 template<typename _Tp
>
172 template<typename _Tp
, size_t _Nm
>
175 swap(_Tp (&)[_Nm
], _Tp (&)[_Nm
]);
177 // C++11 swap() has complicated SFINAE constraints, test signatures like so:
178 void (*swap_scalars
)(int&, int&) = &swap
;
179 void (*swap_arrays
)(int(&)[5], int(&)[5]) = &swap
;
182 template<typename _FIter1
, typename _FIter2
>
185 swap_ranges(_FIter1 first1
, _FIter1
, _FIter2
);
187 template<typename _FIter1
, typename _FIter2
>
190 iter_swap(_FIter1
, _FIter2 b
);
192 template<typename _IIter
, typename _OIter
, typename _UnaryOperation
>
195 transform(_IIter
, _IIter
, _OIter
, _UnaryOperation op
);
197 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
198 typename _BinaryOperation
>
201 transform(_IIter1
, _IIter1
, _IIter2
, _OIter
, _BinaryOperation
);
203 template<typename _FIter
, typename _Tp
>
206 replace(_FIter
, _FIter
, const _Tp
&, const _Tp
&);
208 template<typename _FIter
, typename _Predicate
, typename _Tp
>
211 replace_if(_FIter
, _FIter
, _Predicate
, const _Tp
&);
213 template<typename _IIter
, typename _OIter
, typename _Tp
>
216 replace_copy(_IIter
, _IIter
, _OIter
, const _Tp
&, const _Tp
&);
218 template<typename _Iter
, typename _OIter
, typename _Predicate
, typename _Tp
>
221 replace_copy_if(_Iter
, _Iter
, _OIter
, _Predicate
, const _Tp
&);
223 template<typename _FIter
, typename _Tp
>
226 fill(_FIter
, _FIter
, const _Tp
&);
228 template<typename _OIter
, typename _Size
, typename _Tp
>
231 fill_n(_OIter
, _Size n
, const _Tp
&);
233 template<typename _FIter
, typename _Generator
>
236 generate(_FIter
, _FIter
, _Generator
);
238 template<typename _OIter
, typename _Size
, typename _Generator
>
241 generate_n(_OIter
, _Size
, _Generator
);
243 template<typename _FIter
, typename _Tp
>
246 remove(_FIter
, _FIter
, const _Tp
&);
248 template<typename _FIter
, typename _Predicate
>
251 remove_if(_FIter
, _FIter
, _Predicate
);
253 template<typename _IIter
, typename _OIter
, typename _Tp
>
256 remove_copy(_IIter
, _IIter
, _OIter
, const _Tp
&);
258 template<typename _IIter
, typename _OIter
, typename _Predicate
>
261 remove_copy_if(_IIter
, _IIter
, _OIter
, _Predicate
);
263 #if __cplusplus >= 201103L
264 template<typename _IIter
, typename _OIter
, typename _Predicate
>
267 copy_if(_IIter
, _IIter
, _OIter
, _Predicate
);
269 template<typename _IIter
, typename _Size
, typename _OIter
>
272 copy_n(_IIter
, _Size
, _OIter
);
274 template<typename _IIter
, typename _OIter1
,
275 typename _OIter2
, typename _Predicate
>
277 pair
<_OIter1
, _OIter2
>
278 partition_copy(_IIter
, _IIter
, _OIter1
, _OIter2
, _Predicate
);
281 template<typename _FIter
>
284 unique(_FIter
, _FIter
);
286 template<typename _FIter
, typename _BinaryPredicate
>
289 unique(_FIter
, _FIter
, _BinaryPredicate
);
291 template<typename _IIter
, typename _OIter
>
294 unique_copy(_IIter
, _IIter
, _OIter
);
296 template<typename _IIter
, typename _OIter
, typename _BinaryPredicate
>
299 unique_copy(_IIter
, _IIter
, _OIter
, _BinaryPredicate
);
301 template<typename _BIter
>
304 reverse(_BIter
, _BIter
);
306 template<typename _BIter
, typename _OIter
>
309 reverse_copy(_BIter
, _BIter
, _OIter
);
311 template<typename _FIter
>
314 rotate(_FIter
, _FIter
, _FIter
);
316 template<typename _FIter
, typename _OIter
>
319 rotate_copy (_FIter
, _FIter
, _FIter
, _OIter
);
321 template<typename _RAIter
>
323 random_shuffle(_RAIter
, _RAIter
);
325 template<typename _RAIter
, typename _Generator
>
327 random_shuffle(_RAIter
, _RAIter
, _Generator
&);
329 // 25.2.12, partitions:
330 template<typename _BIter
, typename _Predicate
>
333 partition(_BIter
, _BIter
, _Predicate
);
335 template<typename _BIter
, typename _Predicate
>
337 stable_partition(_BIter
, _BIter
, _Predicate
);
339 // 25.3, sorting and related operations:
341 template<typename _RAIter
>
344 sort(_RAIter
, _RAIter
);
346 template<typename _RAIter
, typename _Compare
>
349 sort(_RAIter
, _RAIter
, _Compare
);
351 template<typename _RAIter
>
353 stable_sort(_RAIter
, _RAIter
);
355 template<typename _RAIter
, typename _Compare
>
357 stable_sort(_RAIter
, _RAIter
, _Compare
);
359 template<typename _RAIter
>
362 partial_sort(_RAIter
, _RAIter
, _RAIter
);
364 template<typename _RAIter
, typename _Compare
>
367 partial_sort(_RAIter
, _RAIter
, _RAIter
, _Compare
);
369 template<typename _IIter
, typename _RAIter
>
372 partial_sort_copy(_IIter
, _IIter
, _RAIter
, _RAIter
);
374 template<typename _IIter
, typename _RAIter
, typename _Compare
>
377 partial_sort_copy(_IIter
, _IIter
, _RAIter
, _RAIter
, _Compare
);
379 template<typename _RAIter
>
382 nth_element(_RAIter
, _RAIter
, _RAIter
);
384 template<typename _RAIter
, typename _Compare
>
387 nth_element(_RAIter
, _RAIter
, _RAIter
, _Compare
);
389 // 25.3.3, binary search:
390 template<typename _FIter
, typename _Tp
>
393 lower_bound(_FIter
, _FIter
, const _Tp
&);
395 template<typename _FIter
, typename _Tp
, typename _Compare
>
398 lower_bound(_FIter
, _FIter
, const _Tp
&, _Compare
);
400 template<typename _FIter
, typename _Tp
>
403 upper_bound(_FIter
, _FIter
, const _Tp
&);
405 template<typename _FIter
, typename _Tp
, typename _Compare
>
408 upper_bound(_FIter
, _FIter
, const _Tp
&, _Compare
);
410 template<typename _FIter
, typename _Tp
>
413 equal_range(_FIter
, _FIter
, const _Tp
&);
415 template<typename _FIter
, typename _Tp
, typename _Compare
>
418 equal_range(_FIter
, _FIter
, const _Tp
&, _Compare
);
420 template<typename _FIter
, typename _Tp
>
423 binary_search(_FIter
, _FIter
, const _Tp
&);
425 template<typename _FIter
, typename _Tp
, typename _Compare
>
428 binary_search(_FIter
, _FIter
, const _Tp
&, _Compare
);
431 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
434 merge(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
436 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
440 merge(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
442 template<typename _BIter
>
444 inplace_merge(_BIter
, _BIter
, _BIter
);
446 template<typename _BIter
, typename _Compare
>
448 inplace_merge(_BIter
, _BIter
, _BIter
, _Compare
);
450 // 25.3.5, set operations:
451 template<typename _IIter1
, typename _IIter2
>
454 includes(_IIter1
, _IIter1
, _IIter2
, _IIter2
);
456 template<typename _IIter1
, typename _IIter2
, typename _Compare
>
459 includes(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _Compare
);
461 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
464 set_union(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
466 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
470 set_union(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
472 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
475 set_intersection(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
477 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
481 set_intersection(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
483 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
486 set_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
488 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
492 set_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
, _Compare
);
494 template<typename _IIter1
, typename _IIter2
, typename _OIter
>
497 set_symmetric_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _OIter
);
499 template<typename _IIter1
, typename _IIter2
, typename _OIter
,
503 set_symmetric_difference(_IIter1
, _IIter1
, _IIter2
, _IIter2
,
506 // 25.3.6, heap operations:
507 template<typename _RAIter
>
510 push_heap(_RAIter
, _RAIter
);
512 template<typename _RAIter
, typename _Compare
>
515 push_heap(_RAIter
, _RAIter
, _Compare
);
517 template<typename _RAIter
>
520 pop_heap(_RAIter
, _RAIter
);
522 template<typename _RAIter
, typename _Compare
>
525 pop_heap(_RAIter
, _RAIter
, _Compare
);
527 template<typename _RAIter
>
530 make_heap(_RAIter
, _RAIter
);
532 template<typename _RAIter
, typename _Compare
>
535 make_heap(_RAIter
, _RAIter
, _Compare
);
537 template<typename _RAIter
>
540 sort_heap(_RAIter
, _RAIter
);
542 template<typename _RAIter
, typename _Compare
>
545 sort_heap(_RAIter
, _RAIter
, _Compare
);
547 #if __cplusplus >= 201103L
548 template<typename _RAIter
>
551 is_heap(_RAIter
, _RAIter
);
553 template<typename _RAIter
, typename _Compare
>
556 is_heap(_RAIter
, _RAIter
, _Compare
);
558 template<typename _RAIter
>
561 is_heap_until(_RAIter
, _RAIter
);
563 template<typename _RAIter
, typename _Compare
>
566 is_heap_until(_RAIter
, _RAIter
, _Compare
);
568 template<typename _FIter
>
571 is_sorted(_FIter
, _FIter
);
573 template<typename _FIter
, typename _Compare
>
576 is_sorted(_FIter
, _FIter
, _Compare
);
578 template<typename _FIter
>
581 is_sorted_until(_FIter
, _FIter
);
583 template<typename _FIter
, typename _Compare
>
586 is_sorted_until(_FIter
, _FIter
, _Compare
);
589 // 25.3.7, minimum and maximum:
590 template<typename _Tp
>
593 min(const _Tp
&, const _Tp
&);
595 template<typename _Tp
, typename _Compare
>
598 min(const _Tp
&, const _Tp
&, _Compare
);
600 template<typename _Tp
>
603 max(const _Tp
&, const _Tp
&);
605 template<typename _Tp
, typename _Compare
>
608 max(const _Tp
&, const _Tp
&, _Compare
);
610 template<typename _FIter
>
613 min_element(_FIter
, _FIter
);
615 template<typename _FIter
, typename _Compare
>
618 min_element(_FIter
, _FIter
, _Compare
);
620 template<typename _FIter
>
623 max_element(_FIter
, _FIter
);
625 template<typename _FIter
, typename _Compare
>
628 max_element(_FIter
, _FIter
, _Compare
);
630 #if __cplusplus >= 201103L
631 template<typename _Tp
>
633 pair
<const _Tp
&, const _Tp
&>
634 minmax(const _Tp
&, const _Tp
&);
636 template<typename _Tp
, typename _Compare
>
638 pair
<const _Tp
&, const _Tp
&>
639 minmax(const _Tp
&, const _Tp
&, _Compare
);
641 template<typename _FIter
>
644 minmax_element(_FIter
, _FIter
);
646 template<typename _FIter
, typename _Compare
>
649 minmax_element(_FIter
, _FIter
, _Compare
);
651 template<typename _Tp
>
654 min(initializer_list
<_Tp
>);
656 template<typename _Tp
, typename _Compare
>
659 min(initializer_list
<_Tp
>, _Compare
);
661 template<typename _Tp
>
664 max(initializer_list
<_Tp
>);
666 template<typename _Tp
, typename _Compare
>
669 max(initializer_list
<_Tp
>, _Compare
);
671 template<typename _Tp
>
674 minmax(initializer_list
<_Tp
>);
676 template<typename _Tp
, typename _Compare
>
679 minmax(initializer_list
<_Tp
>, _Compare
);
682 template<typename _IIter1
, typename _IIter2
>
685 lexicographical_compare(_IIter1
, _IIter1
, _IIter2
, _IIter2
);
687 template<typename _IIter1
, typename _IIter2
, typename _Compare
>
690 lexicographical_compare(_IIter1
, _IIter1
, _IIter2
, _IIter2
, _Compare
);
692 // 25.3.9, permutations
693 template<typename _BIter
>
696 next_permutation(_BIter
, _BIter
);
698 template<typename _BIter
, typename _Compare
>
701 next_permutation(_BIter
, _BIter
, _Compare
);
703 template<typename _BIter
>
706 prev_permutation(_BIter
, _BIter
);
708 template<typename _BIter
, typename _Compare
>
711 prev_permutation(_BIter
, _BIter
, _Compare
);