1// { dg-do compile }
2
3// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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/>.
19
20#include <algorithm>
21
22namespace std
23 {
24  // 25.1, non-modifying sequence operations:
25  template<typename _IIter, typename _Funct>
26    _Funct
27    for_each(_IIter, _IIter, _Funct);
28
29  template<typename _IIter, typename _Tp>
30    _IIter
31    find(_IIter, _IIter, const _Tp&);
32
33  template<typename _IIter, typename _Predicate>
34    _IIter
35    find_if(_IIter, _IIter, _Predicate);
36
37#ifdef __GXX_EXPERIMENTAL_CXX0X__
38  template<typename _IIter, typename _Predicate>
39    bool
40    all_of(_IIter, _IIter, _Predicate);
41
42  template<typename _IIter, typename _Predicate>
43    bool
44    any_of(_IIter, _IIter, _Predicate);
45
46  template<typename _IIter, typename _Predicate>
47    bool
48    none_of(_IIter, _IIter, _Predicate);
49
50  template<typename _IIter, typename _Predicate>
51    _IIter
52    find_if_not(_IIter, _IIter, _Predicate);
53
54  template<typename _IIter, typename _Predicate>
55    bool
56    is_partitioned(_IIter, _IIter, _Predicate);
57
58  template<typename _FIter, typename _Predicate>
59    _FIter
60    partition_point(_FIter, _FIter, _Predicate);
61#endif
62
63  template<typename _FIter1, typename _FIter2>
64    _FIter1
65    find_end(_FIter1, _FIter1, _FIter2, _FIter2);
66
67  template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
68    _FIter1
69    find_end(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
70
71  template<typename _FIter1, typename _FIter2>
72    _FIter1
73    find_first_of(_FIter1, _FIter1, _FIter2, _FIter2);
74
75  template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
76    _FIter1
77    find_first_of(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
78
79  template<typename _FIter>
80    _FIter
81    adjacent_find(_FIter, _FIter);
82
83  template<typename _FIter, typename _BinaryPredicate>
84    _FIter
85    adjacent_find(_FIter, _FIter, _BinaryPredicate);
86
87  template<typename _IIter, typename _Tp>
88    typename iterator_traits<_IIter>::difference_type
89    count(_IIter, _IIter, const _Tp&);
90
91  template<typename _IIter, typename _Predicate>
92    typename iterator_traits<_IIter>::difference_type
93    count_if(_IIter, _IIter, _Predicate);
94
95  template<typename _IIter1, typename _IIter2>
96    pair<_IIter1, _IIter2>
97    mismatch(_IIter1, _IIter1, _IIter2);
98
99  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
100    pair<_IIter1, _IIter2>
101    mismatch(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
102
103  template<typename _IIter1, typename _IIter2>
104    bool
105    equal(_IIter1, _IIter1, _IIter2);
106
107  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
108    bool
109    equal(_IIter1, _IIter1, _IIter2, _BinaryPredicate);
110
111  template<typename _FIter1, typename _FIter2>
112    _FIter1
113    search(_FIter1, _FIter1, _FIter2, _FIter2);
114
115  template<typename _FIter1, typename _FIter2, typename _BinaryPredicate>
116    _FIter1
117    search(_FIter1, _FIter1, _FIter2, _FIter2, _BinaryPredicate);
118
119  template<typename _FIter, typename _Size, typename _Tp>
120    _FIter
121    search_n(_FIter, _FIter, _Size, const _Tp&);
122
123  template<typename _FIter, typename _Size, typename _Tp,
124	   typename _BinaryPredicate>
125    _FIter
126    search_n(_FIter, _FIter, _Size, const _Tp&, _BinaryPredicate);
127
128  // 25.2, modifying sequence operations:
129  // 25.2.1, copy:
130  template<typename _IIter, typename _OIter>
131    _OIter
132    copy(_IIter, _IIter, _OIter);
133
134  template<typename _BIter1, typename _BIter2>
135    _BIter2
136    copy_backward (_BIter1, _BIter1, _BIter2);
137
138  // 25.2.2, swap:
139  template<typename _Tp>
140    void
141    swap(_Tp&, _Tp& b);
142
143#ifdef __GXX_EXPERIMENTAL_CXX0X__
144  template<typename _Tp, size_t _Nm>
145    void
146    swap(_Tp (&)[_Nm], _Tp (&)[_Nm]);
147#endif
148
149  template<typename _FIter1, typename _FIter2>
150    _FIter2
151    swap_ranges(_FIter1 first1, _FIter1, _FIter2);
152
153  template<typename _FIter1, typename _FIter2>
154    void
155    iter_swap(_FIter1, _FIter2 b);
156
157  template<typename _IIter, typename _OIter, typename _UnaryOperation>
158    _OIter
159    transform(_IIter, _IIter, _OIter, _UnaryOperation op);
160
161  template<typename _IIter1, typename _IIter2, typename _OIter,
162	   typename _BinaryOperation>
163    _OIter
164    transform(_IIter1, _IIter1, _IIter2, _OIter, _BinaryOperation);
165
166  template<typename _FIter, typename _Tp>
167    void
168    replace(_FIter, _FIter, const _Tp&, const _Tp&);
169
170  template<typename _FIter, typename _Predicate, typename _Tp>
171    void
172    replace_if(_FIter, _FIter, _Predicate, const _Tp&);
173
174  template<typename _IIter, typename _OIter, typename _Tp>
175    _OIter
176    replace_copy(_IIter, _IIter, _OIter, const _Tp&, const _Tp&);
177
178  template<typename _Iter, typename _OIter, typename _Predicate, typename _Tp>
179    _OIter
180    replace_copy_if(_Iter, _Iter, _OIter, _Predicate, const _Tp&);
181
182  template<typename _FIter, typename _Tp>
183    void
184    fill(_FIter, _FIter, const _Tp&);
185
186  template<typename _OIter, typename _Size, typename _Tp>
187    void
188    fill_n(_OIter, _Size n, const _Tp&);
189
190  template<typename _FIter, typename _Generator>
191    void
192    generate(_FIter, _FIter, _Generator);
193
194  template<typename _OIter, typename _Size, typename _Generator>
195    void
196    generate_n(_OIter, _Size, _Generator);
197
198  template<typename _FIter, typename _Tp>
199    _FIter
200    remove(_FIter, _FIter, const _Tp&);
201
202  template<typename _FIter, typename _Predicate>
203    _FIter
204    remove_if(_FIter, _FIter, _Predicate);
205
206  template<typename _IIter, typename _OIter, typename _Tp>
207    _OIter
208    remove_copy(_IIter, _IIter, _OIter, const _Tp&);
209
210  template<typename _IIter, typename _OIter, typename _Predicate>
211    _OIter
212    remove_copy_if(_IIter, _IIter, _OIter, _Predicate);
213
214#ifdef __GXX_EXPERIMENTAL_CXX0X__
215  template<typename _IIter, typename _OIter, typename _Predicate>
216    _OIter
217    copy_if(_IIter, _IIter, _OIter, _Predicate);
218
219  template<typename _IIter, typename _Size, typename _OIter>
220    _OIter
221    copy_n(_IIter, _Size, _OIter);
222
223  template<typename _IIter, typename _OIter1,
224	   typename _OIter2, typename _Predicate>
225    pair<_OIter1, _OIter2>
226    partition_copy(_IIter, _IIter, _OIter1, _OIter2, _Predicate);
227#endif
228
229  template<typename _FIter>
230    _FIter
231    unique(_FIter, _FIter);
232
233  template<typename _FIter, typename _BinaryPredicate>
234    _FIter
235    unique(_FIter, _FIter, _BinaryPredicate);
236
237  template<typename _IIter, typename _OIter>
238    _OIter
239    unique_copy(_IIter, _IIter, _OIter);
240
241  template<typename _IIter, typename _OIter, typename _BinaryPredicate>
242    _OIter
243    unique_copy(_IIter, _IIter, _OIter, _BinaryPredicate);
244
245  template<typename _BIter>
246    void
247    reverse(_BIter, _BIter);
248
249  template<typename _BIter, typename _OIter>
250    _OIter
251    reverse_copy(_BIter, _BIter, _OIter);
252
253  template<typename _FIter>
254    void
255    rotate(_FIter, _FIter, _FIter);
256
257  template<typename _FIter, typename _OIter>
258    _OIter
259    rotate_copy (_FIter, _FIter, _FIter, _OIter);
260
261  template<typename _RAIter>
262    void
263    random_shuffle(_RAIter, _RAIter);
264
265  template<typename _RAIter, typename _Generator>
266    void
267    random_shuffle(_RAIter, _RAIter, _Generator&);
268
269  // 25.2.12, partitions:
270  template<typename _BIter, typename _Predicate>
271    _BIter
272    partition(_BIter, _BIter, _Predicate);
273
274  template<typename _BIter, typename _Predicate>
275    _BIter
276    stable_partition(_BIter, _BIter, _Predicate);
277
278  // 25.3, sorting and related operations:
279  // 25.3.1, sorting:
280  template<typename _RAIter>
281    void
282    sort(_RAIter, _RAIter);
283
284  template<typename _RAIter, typename _Compare>
285    void
286    sort(_RAIter, _RAIter, _Compare);
287
288  template<typename _RAIter>
289    void
290    stable_sort(_RAIter, _RAIter);
291
292  template<typename _RAIter, typename _Compare>
293    void
294    stable_sort(_RAIter, _RAIter, _Compare);
295
296  template<typename _RAIter>
297    void
298    partial_sort(_RAIter, _RAIter, _RAIter);
299
300  template<typename _RAIter, typename _Compare>
301    void
302    partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
303
304  template<typename _IIter, typename _RAIter>
305    _RAIter
306    partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter);
307
308  template<typename _IIter, typename _RAIter, typename _Compare>
309    _RAIter
310    partial_sort_copy(_IIter, _IIter, _RAIter, _RAIter, _Compare);
311
312  template<typename _RAIter>
313    void
314    nth_element(_RAIter, _RAIter, _RAIter);
315
316  template<typename _RAIter, typename _Compare>
317    void
318    nth_element(_RAIter, _RAIter, _RAIter, _Compare);
319
320  // 25.3.3, binary search:
321  template<typename _FIter, typename _Tp>
322    _FIter
323    lower_bound(_FIter, _FIter, const _Tp&);
324
325  template<typename _FIter, typename _Tp, typename _Compare>
326    _FIter
327    lower_bound(_FIter, _FIter, const _Tp&, _Compare);
328
329  template<typename _FIter, typename _Tp>
330    _FIter
331    upper_bound(_FIter, _FIter, const _Tp&);
332
333  template<typename _FIter, typename _Tp, typename _Compare>
334    _FIter
335    upper_bound(_FIter, _FIter, const _Tp&, _Compare);
336
337  template<typename _FIter, typename _Tp>
338    pair<_FIter, _FIter>
339    equal_range(_FIter, _FIter, const _Tp&);
340
341  template<typename _FIter, typename _Tp, typename _Compare>
342    pair<_FIter, _FIter>
343    equal_range(_FIter, _FIter, const _Tp&, _Compare);
344
345  template<typename _FIter, typename _Tp>
346    bool
347    binary_search(_FIter, _FIter, const _Tp&);
348
349  template<typename _FIter, typename _Tp, typename _Compare>
350    bool
351    binary_search(_FIter, _FIter, const _Tp&, _Compare);
352
353  // 25.3.4, merge:
354  template<typename _IIter1, typename _IIter2, typename _OIter>
355    _OIter
356    merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
357
358  template<typename _IIter1, typename _IIter2, typename _OIter,
359	   typename _Compare>
360    _OIter
361    merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
362
363  template<typename _BIter>
364    void
365    inplace_merge(_BIter, _BIter, _BIter);
366
367  template<typename _BIter, typename _Compare>
368    void
369    inplace_merge(_BIter, _BIter, _BIter, _Compare);
370
371  // 25.3.5, set operations:
372  template<typename _IIter1, typename _IIter2>
373    bool
374    includes(_IIter1, _IIter1, _IIter2, _IIter2);
375
376  template<typename _IIter1, typename _IIter2, typename _Compare>
377    bool
378    includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
379
380  template<typename _IIter1, typename _IIter2, typename _OIter>
381    _OIter
382    set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
383
384  template<typename _IIter1, typename _IIter2, typename _OIter,
385	   typename _Compare>
386    _OIter
387    set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
388
389  template<typename _IIter1, typename _IIter2, typename _OIter>
390    _OIter
391    set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
392
393  template<typename _IIter1, typename _IIter2, typename _OIter,
394	   typename _Compare>
395    _OIter
396    set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
397
398  template<typename _IIter1, typename _IIter2, typename _OIter>
399    _OIter
400    set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
401
402  template<typename _IIter1, typename _IIter2, typename _OIter,
403	   typename _Compare>
404    _OIter
405    set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
406
407  template<typename _IIter1, typename _IIter2, typename _OIter>
408    _OIter
409    set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
410
411  template<typename _IIter1, typename _IIter2, typename _OIter,
412	   typename _Compare>
413    _OIter
414    set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2,
415			     _OIter, _Compare);
416
417  // 25.3.6, heap operations:
418  template<typename _RAIter>
419    void
420    push_heap(_RAIter, _RAIter);
421
422  template<typename _RAIter, typename _Compare>
423    void
424    push_heap(_RAIter, _RAIter, _Compare);
425
426  template<typename _RAIter>
427    void
428    pop_heap(_RAIter, _RAIter);
429
430  template<typename _RAIter, typename _Compare>
431    void
432    pop_heap(_RAIter, _RAIter, _Compare);
433
434  template<typename _RAIter>
435    void
436    make_heap(_RAIter, _RAIter);
437
438  template<typename _RAIter, typename _Compare>
439    void
440    make_heap(_RAIter, _RAIter, _Compare);
441
442  template<typename _RAIter>
443    void
444    sort_heap(_RAIter, _RAIter);
445
446  template<typename _RAIter, typename _Compare>
447    void
448    sort_heap(_RAIter, _RAIter, _Compare);
449
450#ifdef __GXX_EXPERIMENTAL_CXX0X__
451  template<typename _RAIter>
452    bool
453    is_heap(_RAIter, _RAIter);
454
455  template<typename _RAIter, typename _Compare>
456    bool
457    is_heap(_RAIter, _RAIter, _Compare);
458
459  template<typename _RAIter>
460    _RAIter
461    is_heap_until(_RAIter, _RAIter);
462
463  template<typename _RAIter, typename _Compare>
464    _RAIter
465    is_heap_until(_RAIter, _RAIter, _Compare);
466
467  template<typename _FIter>
468    bool
469    is_sorted(_FIter, _FIter);
470
471  template<typename _FIter, typename _Compare>
472    bool
473    is_sorted(_FIter, _FIter, _Compare);
474
475  template<typename _FIter>
476    _FIter
477    is_sorted_until(_FIter, _FIter);
478
479  template<typename _FIter, typename _Compare>
480    _FIter
481    is_sorted_until(_FIter, _FIter, _Compare);
482#endif
483
484  // 25.3.7, minimum and maximum:
485  template<typename _Tp>
486    const _Tp&
487    min(const _Tp&, const _Tp&);
488
489  template<typename _Tp, typename _Compare>
490    const _Tp&
491    min(const _Tp&, const _Tp&, _Compare);
492
493  template<typename _Tp>
494    const _Tp&
495    max(const _Tp&, const _Tp&);
496
497  template<typename _Tp, typename _Compare>
498    const _Tp&
499    max(const _Tp&, const _Tp&, _Compare);
500
501  template<typename _FIter>
502    _FIter
503    min_element(_FIter, _FIter);
504
505  template<typename _FIter, typename _Compare>
506    _FIter
507    min_element(_FIter, _FIter, _Compare);
508
509  template<typename _FIter>
510    _FIter
511    max_element(_FIter, _FIter);
512
513  template<typename _FIter, typename _Compare>
514    _FIter
515    max_element(_FIter, _FIter, _Compare);
516
517#ifdef __GXX_EXPERIMENTAL_CXX0X__
518  template<typename _Tp>
519    pair<const _Tp&, const _Tp&>
520    minmax(const _Tp&, const _Tp&);
521
522  template<typename _Tp, typename _Compare>
523    pair<const _Tp&, const _Tp&>
524    minmax(const _Tp&, const _Tp&, _Compare);
525
526  template<typename _FIter>
527    pair<_FIter, _FIter>
528    minmax_element(_FIter, _FIter);
529
530  template<typename _FIter, typename _Compare>
531    pair<_FIter, _FIter>
532    minmax_element(_FIter, _FIter, _Compare);
533
534  template<typename _Tp>
535    _Tp
536    min(initializer_list<_Tp>);
537
538  template<typename _Tp, typename _Compare>
539    _Tp
540    min(initializer_list<_Tp>, _Compare);
541
542  template<typename _Tp>
543    _Tp
544    max(initializer_list<_Tp>);
545
546  template<typename _Tp, typename _Compare>
547    _Tp
548    max(initializer_list<_Tp>, _Compare);
549
550  template<typename _Tp>
551    pair<_Tp, _Tp>
552    minmax(initializer_list<_Tp>);
553
554  template<typename _Tp, typename _Compare>
555    pair<_Tp, _Tp>
556    minmax(initializer_list<_Tp>, _Compare);
557#endif
558
559  template<typename _IIter1, typename _IIter2>
560    bool
561    lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
562
563  template<typename _IIter1, typename _IIter2, typename _Compare>
564    bool
565    lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
566
567  // 25.3.9, permutations
568  template<typename _BIter>
569    bool
570    next_permutation(_BIter, _BIter);
571
572  template<typename _BIter, typename _Compare>
573    bool
574    next_permutation(_BIter, _BIter, _Compare);
575
576  template<typename _BIter>
577    bool
578    prev_permutation(_BIter, _BIter);
579
580  template<typename _BIter, typename _Compare>
581    bool
582    prev_permutation(_BIter, _BIter, _Compare);
583}
584