]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/include/bits/stl_algo.h
stl_algo.h (is_permutation): Add overloads from N3671.
[thirdparty/gcc.git] / libstdc++-v3 / include / bits / stl_algo.h
CommitLineData
c0d88161 1// Algorithm implementation -*- C++ -*-
42526146 2
405feeb8 3// Copyright (C) 2001-2013 Free Software Foundation, Inc.
42526146
PE
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
748086b7 8// Free Software Foundation; either version 3, or (at your option)
42526146
PE
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
748086b7
JJ
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.
42526146 19
748086b7
JJ
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/>.
42526146 24
725dc051
BK
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
f910786b 51/** @file bits/stl_algo.h
729e3d3f 52 * This is an internal header file, included by other library headers.
f910786b 53 * Do not attempt to use it directly. @headername{algorithm}
725dc051
BK
54 */
55
046d30f4
PC
56#ifndef _STL_ALGO_H
57#define _STL_ALGO_H 1
725dc051 58
c2ba9709 59#include <cstdlib> // for rand
4f39bf5c 60#include <bits/algorithmfwd.h>
725dc051 61#include <bits/stl_heap.h>
39b8cd70 62#include <bits/stl_tempbuf.h> // for _Temporary_buffer
725dc051 63
734f5023 64#if __cplusplus >= 201103L
632469d0
PC
65#include <random> // for std::uniform_int_distribution
66#include <functional> // for std::bind
247d8075
PC
67#endif
68
3d7c150e 69// See concept_check.h for the __glibcxx_*_requires macros.
725dc051 70
12ffa228
BK
71namespace std _GLIBCXX_VISIBILITY(default)
72{
73_GLIBCXX_BEGIN_NAMESPACE_VERSION
3cbc7af0 74
f9590eae
CJ
75 /// Swaps the median value of *__a, *__b and *__c to *__a
76 template<typename _Iterator>
77 void
78 __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
79 {
80 // concept requirements
81 __glibcxx_function_requires(_LessThanComparableConcept<
82 typename iterator_traits<_Iterator>::value_type>)
83
84 if (*__a < *__b)
85 {
86 if (*__b < *__c)
87 std::iter_swap(__a, __b);
88 else if (*__a < *__c)
89 std::iter_swap(__a, __c);
90 }
91 else if (*__a < *__c)
92 return;
93 else if (*__b < *__c)
94 std::iter_swap(__a, __c);
95 else
96 std::iter_swap(__a, __b);
97 }
98
99 /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
100 template<typename _Iterator, typename _Compare>
101 void
102 __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
103 _Compare __comp)
104 {
105 // concept requirements
106 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
107 typename iterator_traits<_Iterator>::value_type,
108 typename iterator_traits<_Iterator>::value_type>)
109
110 if (__comp(*__a, *__b))
111 {
112 if (__comp(*__b, *__c))
113 std::iter_swap(__a, __b);
114 else if (__comp(*__a, *__c))
115 std::iter_swap(__a, __c);
116 }
117 else if (__comp(*__a, *__c))
118 return;
119 else if (__comp(*__b, *__c))
120 std::iter_swap(__a, __c);
121 else
122 std::iter_swap(__a, __b);
123 }
124
c2ba9709 125 // for_each
02d92e3b 126
4312e020 127 /// This is an overload used by find() for the Input Iterator case.
08addde6
PE
128 template<typename _InputIterator, typename _Tp>
129 inline _InputIterator
c1806f89
PC
130 __find(_InputIterator __first, _InputIterator __last,
131 const _Tp& __val, input_iterator_tag)
02d92e3b
SW
132 {
133 while (__first != __last && !(*__first == __val))
134 ++__first;
135 return __first;
136 }
725dc051 137
4312e020 138 /// This is an overload used by find_if() for the Input Iterator case.
08addde6
PE
139 template<typename _InputIterator, typename _Predicate>
140 inline _InputIterator
c1806f89
PC
141 __find_if(_InputIterator __first, _InputIterator __last,
142 _Predicate __pred, input_iterator_tag)
02d92e3b 143 {
dded9d2c 144 while (__first != __last && !bool(__pred(*__first)))
02d92e3b
SW
145 ++__first;
146 return __first;
147 }
725dc051 148
4312e020 149 /// This is an overload used by find() for the RAI case.
08addde6
PE
150 template<typename _RandomAccessIterator, typename _Tp>
151 _RandomAccessIterator
c1806f89
PC
152 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
153 const _Tp& __val, random_access_iterator_tag)
02d92e3b 154 {
ffa67767
PC
155 typename iterator_traits<_RandomAccessIterator>::difference_type
156 __trip_count = (__last - __first) >> 2;
725dc051 157
da5a2efd 158 for (; __trip_count > 0; --__trip_count)
ffa67767
PC
159 {
160 if (*__first == __val)
161 return __first;
162 ++__first;
725dc051 163
ffa67767
PC
164 if (*__first == __val)
165 return __first;
166 ++__first;
ed6814f7 167
ffa67767
PC
168 if (*__first == __val)
169 return __first;
170 ++__first;
725dc051 171
ffa67767
PC
172 if (*__first == __val)
173 return __first;
174 ++__first;
175 }
725dc051 176
ffa67767
PC
177 switch (__last - __first)
178 {
179 case 3:
180 if (*__first == __val)
181 return __first;
182 ++__first;
183 case 2:
184 if (*__first == __val)
185 return __first;
186 ++__first;
187 case 1:
188 if (*__first == __val)
189 return __first;
190 ++__first;
191 case 0:
192 default:
193 return __last;
194 }
02d92e3b 195 }
725dc051 196
4312e020 197 /// This is an overload used by find_if() for the RAI case.
08addde6
PE
198 template<typename _RandomAccessIterator, typename _Predicate>
199 _RandomAccessIterator
c1806f89
PC
200 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
201 _Predicate __pred, random_access_iterator_tag)
02d92e3b 202 {
ffa67767
PC
203 typename iterator_traits<_RandomAccessIterator>::difference_type
204 __trip_count = (__last - __first) >> 2;
725dc051 205
da5a2efd 206 for (; __trip_count > 0; --__trip_count)
ffa67767
PC
207 {
208 if (__pred(*__first))
209 return __first;
210 ++__first;
725dc051 211
ffa67767
PC
212 if (__pred(*__first))
213 return __first;
214 ++__first;
725dc051 215
ffa67767
PC
216 if (__pred(*__first))
217 return __first;
218 ++__first;
725dc051 219
ffa67767
PC
220 if (__pred(*__first))
221 return __first;
222 ++__first;
223 }
725dc051 224
ffa67767
PC
225 switch (__last - __first)
226 {
227 case 3:
228 if (__pred(*__first))
229 return __first;
230 ++__first;
231 case 2:
232 if (__pred(*__first))
233 return __first;
234 ++__first;
235 case 1:
236 if (__pred(*__first))
237 return __first;
238 ++__first;
239 case 0:
240 default:
241 return __last;
242 }
725dc051
BK
243 }
244
76cc1b70
PC
245 /// This is an overload used by find_if_not() for the Input Iterator case.
246 template<typename _InputIterator, typename _Predicate>
247 inline _InputIterator
248 __find_if_not(_InputIterator __first, _InputIterator __last,
249 _Predicate __pred, input_iterator_tag)
250 {
251 while (__first != __last && bool(__pred(*__first)))
252 ++__first;
253 return __first;
254 }
255
256 /// This is an overload used by find_if_not() for the RAI case.
257 template<typename _RandomAccessIterator, typename _Predicate>
258 _RandomAccessIterator
259 __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
260 _Predicate __pred, random_access_iterator_tag)
261 {
262 typename iterator_traits<_RandomAccessIterator>::difference_type
263 __trip_count = (__last - __first) >> 2;
264
265 for (; __trip_count > 0; --__trip_count)
266 {
267 if (!bool(__pred(*__first)))
268 return __first;
269 ++__first;
270
271 if (!bool(__pred(*__first)))
272 return __first;
273 ++__first;
274
275 if (!bool(__pred(*__first)))
276 return __first;
277 ++__first;
278
279 if (!bool(__pred(*__first)))
280 return __first;
281 ++__first;
282 }
283
284 switch (__last - __first)
285 {
286 case 3:
287 if (!bool(__pred(*__first)))
288 return __first;
289 ++__first;
290 case 2:
291 if (!bool(__pred(*__first)))
292 return __first;
293 ++__first;
294 case 1:
295 if (!bool(__pred(*__first)))
296 return __first;
297 ++__first;
298 case 0:
299 default:
300 return __last;
301 }
302 }
2fc9b37d
JY
303
304 /// Provided for stable_partition to use.
305 template<typename _InputIterator, typename _Predicate>
306 inline _InputIterator
307 __find_if_not(_InputIterator __first, _InputIterator __last,
308 _Predicate __pred)
309 {
310 return std::__find_if_not(__first, __last, __pred,
311 std::__iterator_category(__first));
312 }
313
314 /// Like find_if_not(), but uses and updates a count of the
315 /// remaining range length instead of comparing against an end
316 /// iterator.
317 template<typename _InputIterator, typename _Predicate, typename _Distance>
318 _InputIterator
319 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
320 {
321 for (; __len; --__len, ++__first)
322 if (!bool(__pred(*__first)))
323 break;
324 return __first;
325 }
76cc1b70 326
c2ba9709
JS
327 // set_difference
328 // set_intersection
329 // set_symmetric_difference
330 // set_union
331 // for_each
332 // find
333 // find_if
334 // find_first_of
335 // adjacent_find
336 // count
337 // count_if
338 // search
02d92e3b 339
c0d88161 340 /**
c2ba9709
JS
341 * This is an uglified
342 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
343 * overloaded for forward iterators.
c0d88161 344 */
c2ba9709
JS
345 template<typename _ForwardIterator, typename _Integer, typename _Tp>
346 _ForwardIterator
347 __search_n(_ForwardIterator __first, _ForwardIterator __last,
348 _Integer __count, const _Tp& __val,
349 std::forward_iterator_tag)
02d92e3b 350 {
12ffa228 351 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
c2ba9709
JS
352 while (__first != __last)
353 {
354 typename iterator_traits<_ForwardIterator>::difference_type
355 __n = __count;
356 _ForwardIterator __i = __first;
357 ++__i;
358 while (__i != __last && __n != 1 && *__i == __val)
359 {
360 ++__i;
361 --__n;
362 }
363 if (__n == 1)
364 return __first;
365 if (__i == __last)
366 return __last;
12ffa228 367 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
c2ba9709
JS
368 }
369 return __last;
02d92e3b
SW
370 }
371
da5a2efd 372 /**
c2ba9709
JS
373 * This is an uglified
374 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
375 * overloaded for random access iterators.
da5a2efd 376 */
c2ba9709
JS
377 template<typename _RandomAccessIter, typename _Integer, typename _Tp>
378 _RandomAccessIter
379 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
380 _Integer __count, const _Tp& __val,
381 std::random_access_iterator_tag)
da5a2efd 382 {
c2ba9709
JS
383
384 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
385 _DistanceType;
da5a2efd 386
c2ba9709
JS
387 _DistanceType __tailSize = __last - __first;
388 const _DistanceType __pattSize = __count;
da5a2efd 389
c2ba9709
JS
390 if (__tailSize < __pattSize)
391 return __last;
da5a2efd 392
c2ba9709
JS
393 const _DistanceType __skipOffset = __pattSize - 1;
394 _RandomAccessIter __lookAhead = __first + __skipOffset;
395 __tailSize -= __pattSize;
396
397 while (1) // the main loop...
398 {
399 // __lookAhead here is always pointing to the last element of next
400 // possible match.
401 while (!(*__lookAhead == __val)) // the skip loop...
402 {
403 if (__tailSize < __pattSize)
404 return __last; // Failure
405 __lookAhead += __pattSize;
406 __tailSize -= __pattSize;
407 }
408 _DistanceType __remainder = __skipOffset;
409 for (_RandomAccessIter __backTrack = __lookAhead - 1;
410 *__backTrack == __val; --__backTrack)
411 {
412 if (--__remainder == 0)
413 return (__lookAhead - __skipOffset); // Success
414 }
415 if (__remainder > __tailSize)
416 return __last; // Failure
417 __lookAhead += __remainder;
418 __tailSize -= __remainder;
419 }
da5a2efd
PC
420 }
421
c2ba9709
JS
422 // search_n
423
c0d88161 424 /**
c2ba9709
JS
425 * This is an uglified
426 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
427 * _BinaryPredicate)
428 * overloaded for forward iterators.
c0d88161 429 */
c2ba9709
JS
430 template<typename _ForwardIterator, typename _Integer, typename _Tp,
431 typename _BinaryPredicate>
08addde6 432 _ForwardIterator
c2ba9709
JS
433 __search_n(_ForwardIterator __first, _ForwardIterator __last,
434 _Integer __count, const _Tp& __val,
435 _BinaryPredicate __binary_pred, std::forward_iterator_tag)
02d92e3b 436 {
c2ba9709
JS
437 while (__first != __last && !bool(__binary_pred(*__first, __val)))
438 ++__first;
439
440 while (__first != __last)
ffa67767 441 {
c2ba9709
JS
442 typename iterator_traits<_ForwardIterator>::difference_type
443 __n = __count;
444 _ForwardIterator __i = __first;
445 ++__i;
446 while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
447 {
448 ++__i;
449 --__n;
450 }
451 if (__n == 1)
ffa67767 452 return __first;
c2ba9709
JS
453 if (__i == __last)
454 return __last;
455 __first = ++__i;
456 while (__first != __last
457 && !bool(__binary_pred(*__first, __val)))
458 ++__first;
ffa67767 459 }
02d92e3b
SW
460 return __last;
461 }
462
c0d88161 463 /**
c2ba9709
JS
464 * This is an uglified
465 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
466 * _BinaryPredicate)
467 * overloaded for random access iterators.
c2ba9709
JS
468 */
469 template<typename _RandomAccessIter, typename _Integer, typename _Tp,
470 typename _BinaryPredicate>
471 _RandomAccessIter
472 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
473 _Integer __count, const _Tp& __val,
474 _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
02d92e3b 475 {
c2ba9709
JS
476
477 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
478 _DistanceType;
479
480 _DistanceType __tailSize = __last - __first;
481 const _DistanceType __pattSize = __count;
482
483 if (__tailSize < __pattSize)
484 return __last;
485
486 const _DistanceType __skipOffset = __pattSize - 1;
487 _RandomAccessIter __lookAhead = __first + __skipOffset;
488 __tailSize -= __pattSize;
489
490 while (1) // the main loop...
ffa67767 491 {
c2ba9709
JS
492 // __lookAhead here is always pointing to the last element of next
493 // possible match.
494 while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
495 {
496 if (__tailSize < __pattSize)
497 return __last; // Failure
498 __lookAhead += __pattSize;
499 __tailSize -= __pattSize;
500 }
501 _DistanceType __remainder = __skipOffset;
502 for (_RandomAccessIter __backTrack = __lookAhead - 1;
503 __binary_pred(*__backTrack, __val); --__backTrack)
504 {
505 if (--__remainder == 0)
506 return (__lookAhead - __skipOffset); // Success
507 }
508 if (__remainder > __tailSize)
509 return __last; // Failure
510 __lookAhead += __remainder;
511 __tailSize -= __remainder;
ffa67767 512 }
02d92e3b
SW
513 }
514
c2ba9709
JS
515 // find_end for forward iterators.
516 template<typename _ForwardIterator1, typename _ForwardIterator2>
517 _ForwardIterator1
518 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
519 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
520 forward_iterator_tag, forward_iterator_tag)
02d92e3b 521 {
c2ba9709
JS
522 if (__first2 == __last2)
523 return __last1;
524 else
525 {
526 _ForwardIterator1 __result = __last1;
527 while (1)
528 {
529 _ForwardIterator1 __new_result
12ffa228 530 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
c2ba9709
JS
531 if (__new_result == __last1)
532 return __result;
533 else
534 {
535 __result = __new_result;
536 __first1 = __new_result;
537 ++__first1;
538 }
539 }
540 }
02d92e3b
SW
541 }
542
c2ba9709
JS
543 template<typename _ForwardIterator1, typename _ForwardIterator2,
544 typename _BinaryPredicate>
545 _ForwardIterator1
546 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
547 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
548 forward_iterator_tag, forward_iterator_tag,
549 _BinaryPredicate __comp)
02d92e3b 550 {
c2ba9709
JS
551 if (__first2 == __last2)
552 return __last1;
553 else
554 {
555 _ForwardIterator1 __result = __last1;
556 while (1)
557 {
558 _ForwardIterator1 __new_result
12ffa228 559 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
d98f312c 560 __last2, __comp);
c2ba9709
JS
561 if (__new_result == __last1)
562 return __result;
563 else
564 {
565 __result = __new_result;
566 __first1 = __new_result;
567 ++__first1;
568 }
569 }
570 }
02d92e3b
SW
571 }
572
c2ba9709
JS
573 // find_end for bidirectional iterators (much faster).
574 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
575 _BidirectionalIterator1
576 __find_end(_BidirectionalIterator1 __first1,
577 _BidirectionalIterator1 __last1,
578 _BidirectionalIterator2 __first2,
579 _BidirectionalIterator2 __last2,
580 bidirectional_iterator_tag, bidirectional_iterator_tag)
1d1c53d5
PC
581 {
582 // concept requirements
c2ba9709
JS
583 __glibcxx_function_requires(_BidirectionalIteratorConcept<
584 _BidirectionalIterator1>)
585 __glibcxx_function_requires(_BidirectionalIteratorConcept<
586 _BidirectionalIterator2>)
1d1c53d5 587
c2ba9709
JS
588 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
589 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
590
591 _RevIterator1 __rlast1(__first1);
592 _RevIterator2 __rlast2(__first2);
12ffa228 593 _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
d98f312c
PC
594 __rlast1,
595 _RevIterator2(__last2),
596 __rlast2);
c2ba9709
JS
597
598 if (__rresult == __rlast1)
599 return __last1;
600 else
601 {
602 _BidirectionalIterator1 __result = __rresult.base();
603 std::advance(__result, -std::distance(__first2, __last2));
604 return __result;
605 }
1d1c53d5
PC
606 }
607
c2ba9709 608 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
1d1c53d5 609 typename _BinaryPredicate>
c2ba9709
JS
610 _BidirectionalIterator1
611 __find_end(_BidirectionalIterator1 __first1,
612 _BidirectionalIterator1 __last1,
613 _BidirectionalIterator2 __first2,
614 _BidirectionalIterator2 __last2,
615 bidirectional_iterator_tag, bidirectional_iterator_tag,
616 _BinaryPredicate __comp)
1d1c53d5
PC
617 {
618 // concept requirements
c2ba9709
JS
619 __glibcxx_function_requires(_BidirectionalIteratorConcept<
620 _BidirectionalIterator1>)
621 __glibcxx_function_requires(_BidirectionalIteratorConcept<
622 _BidirectionalIterator2>)
1d1c53d5 623
c2ba9709
JS
624 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
625 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
626
627 _RevIterator1 __rlast1(__first1);
628 _RevIterator2 __rlast2(__first2);
629 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
630 _RevIterator2(__last2), __rlast2,
631 __comp);
632
633 if (__rresult == __rlast1)
634 return __last1;
635 else
636 {
637 _BidirectionalIterator1 __result = __rresult.base();
638 std::advance(__result, -std::distance(__first2, __last2));
639 return __result;
640 }
1d1c53d5
PC
641 }
642
c0d88161 643 /**
c2ba9709 644 * @brief Find last matching subsequence in a sequence.
5b9daa7e 645 * @ingroup non_mutating_algorithms
93c66bc6
BK
646 * @param __first1 Start of range to search.
647 * @param __last1 End of range to search.
648 * @param __first2 Start of sequence to match.
649 * @param __last2 End of sequence to match.
c2ba9709 650 * @return The last iterator @c i in the range
93c66bc6
BK
651 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
652 * @p *(__first2+N) for each @c N in the range @p
653 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
c0d88161 654 *
93c66bc6
BK
655 * Searches the range @p [__first1,__last1) for a sub-sequence that
656 * compares equal value-by-value with the sequence given by @p
657 * [__first2,__last2) and returns an iterator to the __first
658 * element of the sub-sequence, or @p __last1 if the sub-sequence
659 * is not found. The sub-sequence will be the last such
660 * subsequence contained in [__first,__last1).
c0d88161 661 *
93c66bc6
BK
662 * Because the sub-sequence must lie completely within the range @p
663 * [__first1,__last1) it must start at a position less than @p
664 * __last1-(__last2-__first2) where @p __last2-__first2 is the
665 * length of the sub-sequence. This means that the returned
666 * iterator @c i will be in the range @p
667 * [__first1,__last1-(__last2-__first2))
c0d88161 668 */
08addde6 669 template<typename _ForwardIterator1, typename _ForwardIterator2>
c2ba9709
JS
670 inline _ForwardIterator1
671 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
672 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
02d92e3b
SW
673 {
674 // concept requirements
3d7c150e
BK
675 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
676 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
677 __glibcxx_function_requires(_EqualOpConcept<
08addde6
PE
678 typename iterator_traits<_ForwardIterator1>::value_type,
679 typename iterator_traits<_ForwardIterator2>::value_type>)
285b36d6
BK
680 __glibcxx_requires_valid_range(__first1, __last1);
681 __glibcxx_requires_valid_range(__first2, __last2);
58b9f26a 682
c2ba9709
JS
683 return std::__find_end(__first1, __last1, __first2, __last2,
684 std::__iterator_category(__first1),
685 std::__iterator_category(__first2));
02d92e3b
SW
686 }
687
c0d88161 688 /**
c2ba9709 689 * @brief Find last matching subsequence in a sequence using a predicate.
5b9daa7e 690 * @ingroup non_mutating_algorithms
93c66bc6
BK
691 * @param __first1 Start of range to search.
692 * @param __last1 End of range to search.
693 * @param __first2 Start of sequence to match.
694 * @param __last2 End of sequence to match.
695 * @param __comp The predicate to use.
696 * @return The last iterator @c i in the range @p
697 * [__first1,__last1-(__last2-__first2)) such that @c
698 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
699 * range @p [0,__last2-__first2), or @p __last1 if no such iterator
700 * exists.
c0d88161 701 *
93c66bc6
BK
702 * Searches the range @p [__first1,__last1) for a sub-sequence that
703 * compares equal value-by-value with the sequence given by @p
704 * [__first2,__last2) using comp as a predicate and returns an
705 * iterator to the first element of the sub-sequence, or @p __last1
706 * if the sub-sequence is not found. The sub-sequence will be the
707 * last such subsequence contained in [__first,__last1).
c0d88161 708 *
93c66bc6
BK
709 * Because the sub-sequence must lie completely within the range @p
710 * [__first1,__last1) it must start at a position less than @p
711 * __last1-(__last2-__first2) where @p __last2-__first2 is the
712 * length of the sub-sequence. This means that the returned
713 * iterator @c i will be in the range @p
714 * [__first1,__last1-(__last2-__first2))
c0d88161 715 */
ffa67767
PC
716 template<typename _ForwardIterator1, typename _ForwardIterator2,
717 typename _BinaryPredicate>
c2ba9709
JS
718 inline _ForwardIterator1
719 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
720 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
721 _BinaryPredicate __comp)
02d92e3b
SW
722 {
723 // concept requirements
3d7c150e
BK
724 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
725 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
726 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
08addde6
PE
727 typename iterator_traits<_ForwardIterator1>::value_type,
728 typename iterator_traits<_ForwardIterator2>::value_type>)
285b36d6
BK
729 __glibcxx_requires_valid_range(__first1, __last1);
730 __glibcxx_requires_valid_range(__first2, __last2);
02d92e3b 731
c2ba9709
JS
732 return std::__find_end(__first1, __last1, __first2, __last2,
733 std::__iterator_category(__first1),
734 std::__iterator_category(__first2),
735 __comp);
736 }
725dc051 737
734f5023 738#if __cplusplus >= 201103L
76cc1b70 739 /**
04dbd891
PC
740 * @brief Checks that a predicate is true for all the elements
741 * of a sequence.
5b9daa7e 742 * @ingroup non_mutating_algorithms
93c66bc6
BK
743 * @param __first An input iterator.
744 * @param __last An input iterator.
745 * @param __pred A predicate.
76cc1b70
PC
746 * @return True if the check is true, false otherwise.
747 *
93c66bc6
BK
748 * Returns true if @p __pred is true for each element in the range
749 * @p [__first,__last), and false otherwise.
76cc1b70
PC
750 */
751 template<typename _InputIterator, typename _Predicate>
752 inline bool
753 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
754 { return __last == std::find_if_not(__first, __last, __pred); }
755
756 /**
04dbd891
PC
757 * @brief Checks that a predicate is false for all the elements
758 * of a sequence.
5b9daa7e 759 * @ingroup non_mutating_algorithms
93c66bc6
BK
760 * @param __first An input iterator.
761 * @param __last An input iterator.
762 * @param __pred A predicate.
76cc1b70
PC
763 * @return True if the check is true, false otherwise.
764 *
93c66bc6
BK
765 * Returns true if @p __pred is false for each element in the range
766 * @p [__first,__last), and false otherwise.
76cc1b70
PC
767 */
768 template<typename _InputIterator, typename _Predicate>
769 inline bool
770 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
12ffa228 771 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
76cc1b70
PC
772
773 /**
04dbd891
PC
774 * @brief Checks that a predicate is false for at least an element
775 * of a sequence.
5b9daa7e 776 * @ingroup non_mutating_algorithms
93c66bc6
BK
777 * @param __first An input iterator.
778 * @param __last An input iterator.
779 * @param __pred A predicate.
76cc1b70
PC
780 * @return True if the check is true, false otherwise.
781 *
93c66bc6
BK
782 * Returns true if an element exists in the range @p
783 * [__first,__last) such that @p __pred is true, and false
784 * otherwise.
76cc1b70
PC
785 */
786 template<typename _InputIterator, typename _Predicate>
787 inline bool
788 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
789 { return !std::none_of(__first, __last, __pred); }
790
791 /**
04dbd891
PC
792 * @brief Find the first element in a sequence for which a
793 * predicate is false.
5b9daa7e 794 * @ingroup non_mutating_algorithms
93c66bc6
BK
795 * @param __first An input iterator.
796 * @param __last An input iterator.
797 * @param __pred A predicate.
798 * @return The first iterator @c i in the range @p [__first,__last)
799 * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
76cc1b70
PC
800 */
801 template<typename _InputIterator, typename _Predicate>
802 inline _InputIterator
803 find_if_not(_InputIterator __first, _InputIterator __last,
804 _Predicate __pred)
805 {
806 // concept requirements
807 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
808 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
809 typename iterator_traits<_InputIterator>::value_type>)
810 __glibcxx_requires_valid_range(__first, __last);
2fc9b37d 811 return std::__find_if_not(__first, __last, __pred);
76cc1b70 812 }
04dbd891
PC
813
814 /**
815 * @brief Checks whether the sequence is partitioned.
5b9daa7e 816 * @ingroup mutating_algorithms
93c66bc6
BK
817 * @param __first An input iterator.
818 * @param __last An input iterator.
819 * @param __pred A predicate.
820 * @return True if the range @p [__first,__last) is partioned by @p __pred,
821 * i.e. if all elements that satisfy @p __pred appear before those that
04dbd891
PC
822 * do not.
823 */
824 template<typename _InputIterator, typename _Predicate>
825 inline bool
826 is_partitioned(_InputIterator __first, _InputIterator __last,
827 _Predicate __pred)
828 {
829 __first = std::find_if_not(__first, __last, __pred);
830 return std::none_of(__first, __last, __pred);
831 }
d9be9bb3
PC
832
833 /**
834 * @brief Find the partition point of a partitioned range.
5b9daa7e 835 * @ingroup mutating_algorithms
93c66bc6
BK
836 * @param __first An iterator.
837 * @param __last Another iterator.
838 * @param __pred A predicate.
839 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
840 * and @p none_of(mid, __last, __pred) are both true.
d9be9bb3
PC
841 */
842 template<typename _ForwardIterator, typename _Predicate>
843 _ForwardIterator
844 partition_point(_ForwardIterator __first, _ForwardIterator __last,
845 _Predicate __pred)
846 {
847 // concept requirements
848 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
849 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
850 typename iterator_traits<_ForwardIterator>::value_type>)
851
852 // A specific debug-mode test will be necessary...
853 __glibcxx_requires_valid_range(__first, __last);
854
855 typedef typename iterator_traits<_ForwardIterator>::difference_type
856 _DistanceType;
857
858 _DistanceType __len = std::distance(__first, __last);
859 _DistanceType __half;
860 _ForwardIterator __middle;
861
862 while (__len > 0)
863 {
864 __half = __len >> 1;
865 __middle = __first;
866 std::advance(__middle, __half);
867 if (__pred(*__middle))
868 {
869 __first = __middle;
870 ++__first;
871 __len = __len - __half - 1;
872 }
873 else
874 __len = __half;
875 }
876 return __first;
877 }
76cc1b70
PC
878#endif
879
02d92e3b 880
c2ba9709
JS
881 /**
882 * @brief Copy a sequence, removing elements of a given value.
5b9daa7e 883 * @ingroup mutating_algorithms
93c66bc6
BK
884 * @param __first An input iterator.
885 * @param __last An input iterator.
886 * @param __result An output iterator.
887 * @param __value The value to be removed.
c2ba9709
JS
888 * @return An iterator designating the end of the resulting sequence.
889 *
93c66bc6
BK
890 * Copies each element in the range @p [__first,__last) not equal
891 * to @p __value to the range beginning at @p __result.
892 * remove_copy() is stable, so the relative order of elements that
893 * are copied is unchanged.
c2ba9709
JS
894 */
895 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
896 _OutputIterator
897 remove_copy(_InputIterator __first, _InputIterator __last,
898 _OutputIterator __result, const _Tp& __value)
899 {
900 // concept requirements
901 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
902 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
903 typename iterator_traits<_InputIterator>::value_type>)
904 __glibcxx_function_requires(_EqualOpConcept<
905 typename iterator_traits<_InputIterator>::value_type, _Tp>)
906 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 907
c2ba9709
JS
908 for (; __first != __last; ++__first)
909 if (!(*__first == __value))
910 {
911 *__result = *__first;
912 ++__result;
913 }
914 return __result;
725dc051 915 }
725dc051 916
b35c0822 917 /**
c2ba9709 918 * @brief Copy a sequence, removing elements for which a predicate is true.
5b9daa7e 919 * @ingroup mutating_algorithms
93c66bc6
BK
920 * @param __first An input iterator.
921 * @param __last An input iterator.
922 * @param __result An output iterator.
923 * @param __pred A predicate.
c2ba9709
JS
924 * @return An iterator designating the end of the resulting sequence.
925 *
93c66bc6
BK
926 * Copies each element in the range @p [__first,__last) for which
927 * @p __pred returns false to the range beginning at @p __result.
c2ba9709
JS
928 *
929 * remove_copy_if() is stable, so the relative order of elements that are
930 * copied is unchanged.
b35c0822 931 */
c2ba9709
JS
932 template<typename _InputIterator, typename _OutputIterator,
933 typename _Predicate>
934 _OutputIterator
935 remove_copy_if(_InputIterator __first, _InputIterator __last,
936 _OutputIterator __result, _Predicate __pred)
b35c0822 937 {
c2ba9709
JS
938 // concept requirements
939 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
940 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
941 typename iterator_traits<_InputIterator>::value_type>)
942 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
943 typename iterator_traits<_InputIterator>::value_type>)
944 __glibcxx_requires_valid_range(__first, __last);
945
946 for (; __first != __last; ++__first)
947 if (!bool(__pred(*__first)))
948 {
949 *__result = *__first;
950 ++__result;
951 }
952 return __result;
b35c0822
PC
953 }
954
734f5023 955#if __cplusplus >= 201103L
a057a4f1
PC
956 /**
957 * @brief Copy the elements of a sequence for which a predicate is true.
5b9daa7e 958 * @ingroup mutating_algorithms
93c66bc6
BK
959 * @param __first An input iterator.
960 * @param __last An input iterator.
961 * @param __result An output iterator.
962 * @param __pred A predicate.
a057a4f1
PC
963 * @return An iterator designating the end of the resulting sequence.
964 *
93c66bc6
BK
965 * Copies each element in the range @p [__first,__last) for which
966 * @p __pred returns true to the range beginning at @p __result.
a057a4f1
PC
967 *
968 * copy_if() is stable, so the relative order of elements that are
969 * copied is unchanged.
970 */
971 template<typename _InputIterator, typename _OutputIterator,
972 typename _Predicate>
973 _OutputIterator
974 copy_if(_InputIterator __first, _InputIterator __last,
975 _OutputIterator __result, _Predicate __pred)
976 {
977 // concept requirements
978 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
979 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
980 typename iterator_traits<_InputIterator>::value_type>)
981 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
982 typename iterator_traits<_InputIterator>::value_type>)
983 __glibcxx_requires_valid_range(__first, __last);
984
985 for (; __first != __last; ++__first)
986 if (__pred(*__first))
987 {
988 *__result = *__first;
989 ++__result;
990 }
991 return __result;
992 }
688a7a07 993
b0371776
PC
994
995 template<typename _InputIterator, typename _Size, typename _OutputIterator>
996 _OutputIterator
997 __copy_n(_InputIterator __first, _Size __n,
998 _OutputIterator __result, input_iterator_tag)
999 {
6ba30237 1000 if (__n > 0)
b0371776 1001 {
6ba30237
PC
1002 while (true)
1003 {
1004 *__result = *__first;
1005 ++__result;
1006 if (--__n > 0)
1007 ++__first;
1008 else
1009 break;
1010 }
b0371776
PC
1011 }
1012 return __result;
1013 }
1014
1015 template<typename _RandomAccessIterator, typename _Size,
1016 typename _OutputIterator>
1017 inline _OutputIterator
1018 __copy_n(_RandomAccessIterator __first, _Size __n,
1019 _OutputIterator __result, random_access_iterator_tag)
1020 { return std::copy(__first, __first + __n, __result); }
1021
1022 /**
1023 * @brief Copies the range [first,first+n) into [result,result+n).
5b9daa7e 1024 * @ingroup mutating_algorithms
93c66bc6
BK
1025 * @param __first An input iterator.
1026 * @param __n The number of elements to copy.
1027 * @param __result An output iterator.
b0371776
PC
1028 * @return result+n.
1029 *
1030 * This inline function will boil down to a call to @c memmove whenever
1031 * possible. Failing that, if random access iterators are passed, then the
1032 * loop count will be known (and therefore a candidate for compiler
1033 * optimizations such as unrolling).
1034 */
1035 template<typename _InputIterator, typename _Size, typename _OutputIterator>
1036 inline _OutputIterator
1037 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1038 {
1039 // concept requirements
1040 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1041 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1042 typename iterator_traits<_InputIterator>::value_type>)
1043
1044 return std::__copy_n(__first, __n, __result,
1045 std::__iterator_category(__first));
1046 }
1047
688a7a07
PC
1048 /**
1049 * @brief Copy the elements of a sequence to separate output sequences
1050 * depending on the truth value of a predicate.
5b9daa7e 1051 * @ingroup mutating_algorithms
93c66bc6
BK
1052 * @param __first An input iterator.
1053 * @param __last An input iterator.
1054 * @param __out_true An output iterator.
1055 * @param __out_false An output iterator.
1056 * @param __pred A predicate.
688a7a07
PC
1057 * @return A pair designating the ends of the resulting sequences.
1058 *
93c66bc6
BK
1059 * Copies each element in the range @p [__first,__last) for which
1060 * @p __pred returns true to the range beginning at @p out_true
1061 * and each element for which @p __pred returns false to @p __out_false.
688a7a07
PC
1062 */
1063 template<typename _InputIterator, typename _OutputIterator1,
1064 typename _OutputIterator2, typename _Predicate>
1065 pair<_OutputIterator1, _OutputIterator2>
1066 partition_copy(_InputIterator __first, _InputIterator __last,
1067 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1068 _Predicate __pred)
1069 {
1070 // concept requirements
1071 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1072 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1073 typename iterator_traits<_InputIterator>::value_type>)
1074 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1075 typename iterator_traits<_InputIterator>::value_type>)
1076 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1077 typename iterator_traits<_InputIterator>::value_type>)
1078 __glibcxx_requires_valid_range(__first, __last);
1079
1080 for (; __first != __last; ++__first)
1081 if (__pred(*__first))
1082 {
1083 *__out_true = *__first;
1084 ++__out_true;
1085 }
1086 else
1087 {
1088 *__out_false = *__first;
1089 ++__out_false;
1090 }
1091
1092 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1093 }
a057a4f1
PC
1094#endif
1095
b35c0822 1096 /**
c2ba9709 1097 * @brief Remove elements from a sequence.
5b9daa7e 1098 * @ingroup mutating_algorithms
93c66bc6
BK
1099 * @param __first An input iterator.
1100 * @param __last An input iterator.
1101 * @param __value The value to be removed.
c2ba9709
JS
1102 * @return An iterator designating the end of the resulting sequence.
1103 *
93c66bc6
BK
1104 * All elements equal to @p __value are removed from the range
1105 * @p [__first,__last).
c2ba9709
JS
1106 *
1107 * remove() is stable, so the relative order of elements that are
1108 * not removed is unchanged.
1109 *
93c66bc6 1110 * Elements between the end of the resulting sequence and @p __last
c2ba9709 1111 * are still present, but their value is unspecified.
b35c0822 1112 */
c2ba9709
JS
1113 template<typename _ForwardIterator, typename _Tp>
1114 _ForwardIterator
1115 remove(_ForwardIterator __first, _ForwardIterator __last,
1116 const _Tp& __value)
b35c0822 1117 {
c2ba9709
JS
1118 // concept requirements
1119 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1120 _ForwardIterator>)
1121 __glibcxx_function_requires(_EqualOpConcept<
1122 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1123 __glibcxx_requires_valid_range(__first, __last);
b35c0822 1124
12ffa228 1125 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
3a6b0f54
PC
1126 if(__first == __last)
1127 return __first;
1128 _ForwardIterator __result = __first;
1129 ++__first;
1130 for(; __first != __last; ++__first)
1131 if(!(*__first == __value))
1132 {
1133 *__result = _GLIBCXX_MOVE(*__first);
1134 ++__result;
1135 }
1136 return __result;
c2ba9709 1137 }
b35c0822 1138
c0d88161 1139 /**
c2ba9709 1140 * @brief Remove elements from a sequence using a predicate.
5b9daa7e 1141 * @ingroup mutating_algorithms
93c66bc6
BK
1142 * @param __first A forward iterator.
1143 * @param __last A forward iterator.
1144 * @param __pred A predicate.
c2ba9709 1145 * @return An iterator designating the end of the resulting sequence.
c0d88161 1146 *
93c66bc6
BK
1147 * All elements for which @p __pred returns true are removed from the range
1148 * @p [__first,__last).
c2ba9709
JS
1149 *
1150 * remove_if() is stable, so the relative order of elements that are
1151 * not removed is unchanged.
1152 *
93c66bc6 1153 * Elements between the end of the resulting sequence and @p __last
c2ba9709 1154 * are still present, but their value is unspecified.
c0d88161 1155 */
c2ba9709 1156 template<typename _ForwardIterator, typename _Predicate>
08addde6 1157 _ForwardIterator
c2ba9709
JS
1158 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1159 _Predicate __pred)
02d92e3b
SW
1160 {
1161 // concept requirements
c2ba9709
JS
1162 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1163 _ForwardIterator>)
1164 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1165 typename iterator_traits<_ForwardIterator>::value_type>)
285b36d6 1166 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 1167
12ffa228 1168 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
3a6b0f54
PC
1169 if(__first == __last)
1170 return __first;
1171 _ForwardIterator __result = __first;
1172 ++__first;
1173 for(; __first != __last; ++__first)
a057a4f1 1174 if(!bool(__pred(*__first)))
3a6b0f54
PC
1175 {
1176 *__result = _GLIBCXX_MOVE(*__first);
1177 ++__result;
1178 }
1179 return __result;
b35c0822
PC
1180 }
1181
1182 /**
c2ba9709 1183 * @brief Remove consecutive duplicate values from a sequence.
5b9daa7e 1184 * @ingroup mutating_algorithms
93c66bc6
BK
1185 * @param __first A forward iterator.
1186 * @param __last A forward iterator.
c2ba9709
JS
1187 * @return An iterator designating the end of the resulting sequence.
1188 *
1189 * Removes all but the first element from each group of consecutive
1190 * values that compare equal.
1191 * unique() is stable, so the relative order of elements that are
1192 * not removed is unchanged.
93c66bc6 1193 * Elements between the end of the resulting sequence and @p __last
c2ba9709 1194 * are still present, but their value is unspecified.
b35c0822 1195 */
c2ba9709 1196 template<typename _ForwardIterator>
b35c0822 1197 _ForwardIterator
c2ba9709 1198 unique(_ForwardIterator __first, _ForwardIterator __last)
b35c0822 1199 {
c2ba9709
JS
1200 // concept requirements
1201 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1202 _ForwardIterator>)
1203 __glibcxx_function_requires(_EqualityComparableConcept<
1204 typename iterator_traits<_ForwardIterator>::value_type>)
1205 __glibcxx_requires_valid_range(__first, __last);
b35c0822 1206
c2ba9709 1207 // Skip the beginning, if already unique.
12ffa228 1208 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
c2ba9709
JS
1209 if (__first == __last)
1210 return __last;
b35c0822 1211
c2ba9709
JS
1212 // Do the real copy work.
1213 _ForwardIterator __dest = __first;
1214 ++__first;
1215 while (++__first != __last)
1216 if (!(*__dest == *__first))
3a6b0f54 1217 *++__dest = _GLIBCXX_MOVE(*__first);
c2ba9709 1218 return ++__dest;
02d92e3b
SW
1219 }
1220
c0d88161 1221 /**
c2ba9709 1222 * @brief Remove consecutive values from a sequence using a predicate.
5b9daa7e 1223 * @ingroup mutating_algorithms
93c66bc6
BK
1224 * @param __first A forward iterator.
1225 * @param __last A forward iterator.
1226 * @param __binary_pred A binary predicate.
c2ba9709 1227 * @return An iterator designating the end of the resulting sequence.
c0d88161 1228 *
c2ba9709 1229 * Removes all but the first element from each group of consecutive
93c66bc6 1230 * values for which @p __binary_pred returns true.
c2ba9709
JS
1231 * unique() is stable, so the relative order of elements that are
1232 * not removed is unchanged.
93c66bc6 1233 * Elements between the end of the resulting sequence and @p __last
c2ba9709 1234 * are still present, but their value is unspecified.
c0d88161 1235 */
c2ba9709 1236 template<typename _ForwardIterator, typename _BinaryPredicate>
08addde6 1237 _ForwardIterator
c2ba9709
JS
1238 unique(_ForwardIterator __first, _ForwardIterator __last,
1239 _BinaryPredicate __binary_pred)
02d92e3b
SW
1240 {
1241 // concept requirements
c2ba9709
JS
1242 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1243 _ForwardIterator>)
3d7c150e 1244 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
c2ba9709
JS
1245 typename iterator_traits<_ForwardIterator>::value_type,
1246 typename iterator_traits<_ForwardIterator>::value_type>)
285b36d6 1247 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 1248
c2ba9709 1249 // Skip the beginning, if already unique.
12ffa228 1250 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
c2ba9709
JS
1251 if (__first == __last)
1252 return __last;
1253
1254 // Do the real copy work.
1255 _ForwardIterator __dest = __first;
1256 ++__first;
1257 while (++__first != __last)
1258 if (!bool(__binary_pred(*__dest, *__first)))
3a6b0f54 1259 *++__dest = _GLIBCXX_MOVE(*__first);
c2ba9709 1260 return ++__dest;
c0d88161 1261 }
02d92e3b 1262
c2ba9709 1263 /**
c2ba9709
JS
1264 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1265 * _OutputIterator)
1266 * overloaded for forward iterators and output iterator as result.
c2ba9709
JS
1267 */
1268 template<typename _ForwardIterator, typename _OutputIterator>
1269 _OutputIterator
1270 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1271 _OutputIterator __result,
1272 forward_iterator_tag, output_iterator_tag)
02d92e3b 1273 {
c2ba9709
JS
1274 // concept requirements -- taken care of in dispatching function
1275 _ForwardIterator __next = __first;
1276 *__result = *__first;
1277 while (++__next != __last)
1278 if (!(*__first == *__next))
1279 {
1280 __first = __next;
1281 *++__result = *__first;
1282 }
1283 return ++__result;
da5a2efd 1284 }
02d92e3b 1285
c2ba9709 1286 /**
c2ba9709
JS
1287 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1288 * _OutputIterator)
1289 * overloaded for input iterators and output iterator as result.
c2ba9709
JS
1290 */
1291 template<typename _InputIterator, typename _OutputIterator>
1292 _OutputIterator
1293 __unique_copy(_InputIterator __first, _InputIterator __last,
1294 _OutputIterator __result,
1295 input_iterator_tag, output_iterator_tag)
da5a2efd 1296 {
c2ba9709
JS
1297 // concept requirements -- taken care of in dispatching function
1298 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1299 *__result = __value;
1300 while (++__first != __last)
1301 if (!(__value == *__first))
1302 {
1303 __value = *__first;
1304 *++__result = __value;
1305 }
1306 return ++__result;
02d92e3b
SW
1307 }
1308
c2ba9709 1309 /**
c2ba9709
JS
1310 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1311 * _OutputIterator)
1312 * overloaded for input iterators and forward iterator as result.
c2ba9709
JS
1313 */
1314 template<typename _InputIterator, typename _ForwardIterator>
1315 _ForwardIterator
1316 __unique_copy(_InputIterator __first, _InputIterator __last,
1317 _ForwardIterator __result,
1318 input_iterator_tag, forward_iterator_tag)
02d92e3b 1319 {
c2ba9709
JS
1320 // concept requirements -- taken care of in dispatching function
1321 *__result = *__first;
1322 while (++__first != __last)
1323 if (!(*__result == *__first))
1324 *++__result = *__first;
1325 return ++__result;
02d92e3b
SW
1326 }
1327
c2ba9709 1328 /**
c2ba9709
JS
1329 * This is an uglified
1330 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1331 * _BinaryPredicate)
1332 * overloaded for forward iterators and output iterator as result.
c2ba9709
JS
1333 */
1334 template<typename _ForwardIterator, typename _OutputIterator,
da5a2efd 1335 typename _BinaryPredicate>
c2ba9709
JS
1336 _OutputIterator
1337 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1338 _OutputIterator __result, _BinaryPredicate __binary_pred,
1339 forward_iterator_tag, output_iterator_tag)
02d92e3b 1340 {
c2ba9709
JS
1341 // concept requirements -- iterators already checked
1342 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1343 typename iterator_traits<_ForwardIterator>::value_type,
1344 typename iterator_traits<_ForwardIterator>::value_type>)
da5a2efd 1345
c2ba9709
JS
1346 _ForwardIterator __next = __first;
1347 *__result = *__first;
1348 while (++__next != __last)
1349 if (!bool(__binary_pred(*__first, *__next)))
1350 {
1351 __first = __next;
1352 *++__result = *__first;
1353 }
1354 return ++__result;
da5a2efd
PC
1355 }
1356
1357 /**
c2ba9709
JS
1358 * This is an uglified
1359 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1360 * _BinaryPredicate)
1361 * overloaded for input iterators and output iterator as result.
da5a2efd 1362 */
c2ba9709
JS
1363 template<typename _InputIterator, typename _OutputIterator,
1364 typename _BinaryPredicate>
1365 _OutputIterator
1366 __unique_copy(_InputIterator __first, _InputIterator __last,
1367 _OutputIterator __result, _BinaryPredicate __binary_pred,
1368 input_iterator_tag, output_iterator_tag)
da5a2efd 1369 {
c2ba9709
JS
1370 // concept requirements -- iterators already checked
1371 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1372 typename iterator_traits<_InputIterator>::value_type,
1373 typename iterator_traits<_InputIterator>::value_type>)
da5a2efd 1374
c2ba9709
JS
1375 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1376 *__result = __value;
1377 while (++__first != __last)
1378 if (!bool(__binary_pred(__value, *__first)))
1379 {
1380 __value = *__first;
1381 *++__result = __value;
1382 }
1383 return ++__result;
da5a2efd
PC
1384 }
1385
1386 /**
c2ba9709
JS
1387 * This is an uglified
1388 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1389 * _BinaryPredicate)
1390 * overloaded for input iterators and forward iterator as result.
da5a2efd 1391 */
c2ba9709 1392 template<typename _InputIterator, typename _ForwardIterator,
da5a2efd 1393 typename _BinaryPredicate>
c2ba9709
JS
1394 _ForwardIterator
1395 __unique_copy(_InputIterator __first, _InputIterator __last,
1396 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1397 input_iterator_tag, forward_iterator_tag)
da5a2efd 1398 {
c2ba9709 1399 // concept requirements -- iterators already checked
da5a2efd 1400 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
c2ba9709
JS
1401 typename iterator_traits<_ForwardIterator>::value_type,
1402 typename iterator_traits<_InputIterator>::value_type>)
da5a2efd 1403
c2ba9709
JS
1404 *__result = *__first;
1405 while (++__first != __last)
1406 if (!bool(__binary_pred(*__result, *__first)))
1407 *++__result = *__first;
1408 return ++__result;
da5a2efd
PC
1409 }
1410
1411 /**
c2ba9709
JS
1412 * This is an uglified reverse(_BidirectionalIterator,
1413 * _BidirectionalIterator)
1414 * overloaded for bidirectional iterators.
da5a2efd 1415 */
c2ba9709
JS
1416 template<typename _BidirectionalIterator>
1417 void
1418 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1419 bidirectional_iterator_tag)
da5a2efd 1420 {
c2ba9709
JS
1421 while (true)
1422 if (__first == __last || __first == --__last)
1423 return;
1424 else
1425 {
1426 std::iter_swap(__first, __last);
1427 ++__first;
1428 }
da5a2efd
PC
1429 }
1430
1431 /**
c2ba9709
JS
1432 * This is an uglified reverse(_BidirectionalIterator,
1433 * _BidirectionalIterator)
1434 * overloaded for random access iterators.
da5a2efd 1435 */
c2ba9709 1436 template<typename _RandomAccessIterator>
da5a2efd 1437 void
c2ba9709
JS
1438 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1439 random_access_iterator_tag)
da5a2efd 1440 {
c2ba9709
JS
1441 if (__first == __last)
1442 return;
1443 --__last;
1444 while (__first < __last)
1445 {
1446 std::iter_swap(__first, __last);
1447 ++__first;
1448 --__last;
1449 }
da5a2efd
PC
1450 }
1451
1452 /**
c2ba9709 1453 * @brief Reverse a sequence.
5b9daa7e 1454 * @ingroup mutating_algorithms
93c66bc6
BK
1455 * @param __first A bidirectional iterator.
1456 * @param __last A bidirectional iterator.
c2ba9709 1457 * @return reverse() returns no value.
c0d88161 1458 *
93c66bc6 1459 * Reverses the order of the elements in the range @p [__first,__last),
c2ba9709 1460 * so that the first element becomes the last etc.
93c66bc6
BK
1461 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1462 * swaps @p *(__first+i) and @p *(__last-(i+1))
c0d88161 1463 */
c2ba9709
JS
1464 template<typename _BidirectionalIterator>
1465 inline void
1466 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
02d92e3b
SW
1467 {
1468 // concept requirements
c2ba9709
JS
1469 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1470 _BidirectionalIterator>)
285b36d6 1471 __glibcxx_requires_valid_range(__first, __last);
c2ba9709 1472 std::__reverse(__first, __last, std::__iterator_category(__first));
02d92e3b
SW
1473 }
1474
c0d88161 1475 /**
c2ba9709 1476 * @brief Copy a sequence, reversing its elements.
5b9daa7e 1477 * @ingroup mutating_algorithms
93c66bc6
BK
1478 * @param __first A bidirectional iterator.
1479 * @param __last A bidirectional iterator.
1480 * @param __result An output iterator.
c2ba9709 1481 * @return An iterator designating the end of the resulting sequence.
c0d88161 1482 *
93c66bc6
BK
1483 * Copies the elements in the range @p [__first,__last) to the
1484 * range @p [__result,__result+(__last-__first)) such that the
1485 * order of the elements is reversed. For every @c i such that @p
1486 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1b5dc776 1487 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
93c66bc6
BK
1488 * The ranges @p [__first,__last) and @p
1489 * [__result,__result+(__last-__first)) must not overlap.
c0d88161 1490 */
c2ba9709 1491 template<typename _BidirectionalIterator, typename _OutputIterator>
08addde6 1492 _OutputIterator
c2ba9709 1493 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
76cc1b70 1494 _OutputIterator __result)
02d92e3b
SW
1495 {
1496 // concept requirements
c2ba9709
JS
1497 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1498 _BidirectionalIterator>)
3d7c150e 1499 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
c2ba9709 1500 typename iterator_traits<_BidirectionalIterator>::value_type>)
285b36d6 1501 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 1502
c2ba9709
JS
1503 while (__first != __last)
1504 {
1505 --__last;
1506 *__result = *__last;
1507 ++__result;
1508 }
02d92e3b
SW
1509 return __result;
1510 }
1511
c0d88161 1512 /**
c2ba9709
JS
1513 * This is a helper function for the rotate algorithm specialized on RAIs.
1514 * It returns the greatest common divisor of two integer values.
c0d88161 1515 */
c2ba9709
JS
1516 template<typename _EuclideanRingElement>
1517 _EuclideanRingElement
1518 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
02d92e3b 1519 {
c2ba9709
JS
1520 while (__n != 0)
1521 {
1522 _EuclideanRingElement __t = __m % __n;
1523 __m = __n;
1524 __n = __t;
1525 }
1526 return __m;
02d92e3b
SW
1527 }
1528
4312e020 1529 /// This is a helper function for the rotate algorithm.
c2ba9709 1530 template<typename _ForwardIterator>
02d92e3b 1531 void
c2ba9709
JS
1532 __rotate(_ForwardIterator __first,
1533 _ForwardIterator __middle,
1534 _ForwardIterator __last,
1535 forward_iterator_tag)
02d92e3b 1536 {
c2ba9709
JS
1537 if (__first == __middle || __last == __middle)
1538 return;
02d92e3b 1539
c2ba9709
JS
1540 _ForwardIterator __first2 = __middle;
1541 do
1542 {
3a6b0f54 1543 std::iter_swap(__first, __first2);
c2ba9709
JS
1544 ++__first;
1545 ++__first2;
1546 if (__first == __middle)
1547 __middle = __first2;
1548 }
1549 while (__first2 != __last);
1550
1551 __first2 = __middle;
1552
1553 while (__first2 != __last)
1554 {
3a6b0f54 1555 std::iter_swap(__first, __first2);
c2ba9709
JS
1556 ++__first;
1557 ++__first2;
1558 if (__first == __middle)
1559 __middle = __first2;
1560 else if (__first2 == __last)
1561 __first2 = __middle;
1562 }
02d92e3b
SW
1563 }
1564
4312e020 1565 /// This is a helper function for the rotate algorithm.
c2ba9709
JS
1566 template<typename _BidirectionalIterator>
1567 void
1568 __rotate(_BidirectionalIterator __first,
1569 _BidirectionalIterator __middle,
1570 _BidirectionalIterator __last,
1571 bidirectional_iterator_tag)
02d92e3b 1572 {
02669b68 1573 // concept requirements
c2ba9709
JS
1574 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1575 _BidirectionalIterator>)
02d92e3b 1576
c2ba9709
JS
1577 if (__first == __middle || __last == __middle)
1578 return;
1579
1580 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1581 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1582
1583 while (__first != __middle && __middle != __last)
1584 {
3a6b0f54 1585 std::iter_swap(__first, --__last);
c2ba9709
JS
1586 ++__first;
1587 }
1588
1589 if (__first == __middle)
1590 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1591 else
1592 std::__reverse(__first, __middle, bidirectional_iterator_tag());
725dc051 1593 }
725dc051 1594
4312e020 1595 /// This is a helper function for the rotate algorithm.
c2ba9709
JS
1596 template<typename _RandomAccessIterator>
1597 void
1598 __rotate(_RandomAccessIterator __first,
1599 _RandomAccessIterator __middle,
1600 _RandomAccessIterator __last,
1601 random_access_iterator_tag)
02d92e3b
SW
1602 {
1603 // concept requirements
c2ba9709
JS
1604 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1605 _RandomAccessIterator>)
02d92e3b 1606
c2ba9709
JS
1607 if (__first == __middle || __last == __middle)
1608 return;
1609
1610 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1611 _Distance;
1612 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1613 _ValueType;
1614
6e924e07
DK
1615 _Distance __n = __last - __first;
1616 _Distance __k = __middle - __first;
c2ba9709 1617
6e924e07 1618 if (__k == __n - __k)
c2ba9709
JS
1619 {
1620 std::swap_ranges(__first, __middle, __middle);
1621 return;
1622 }
1623
6e924e07 1624 _RandomAccessIterator __p = __first;
c2ba9709 1625
6e924e07 1626 for (;;)
c2ba9709 1627 {
6e924e07 1628 if (__k < __n - __k)
c2ba9709 1629 {
6e924e07
DK
1630 if (__is_pod(_ValueType) && __k == 1)
1631 {
1632 _ValueType __t = _GLIBCXX_MOVE(*__p);
1633 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1634 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1635 return;
1636 }
1637 _RandomAccessIterator __q = __p + __k;
1638 for (_Distance __i = 0; __i < __n - __k; ++ __i)
c2ba9709 1639 {
6e924e07
DK
1640 std::iter_swap(__p, __q);
1641 ++__p;
1642 ++__q;
c2ba9709 1643 }
6e924e07
DK
1644 __n %= __k;
1645 if (__n == 0)
1646 return;
1647 std::swap(__n, __k);
1648 __k = __n - __k;
c2ba9709
JS
1649 }
1650 else
1651 {
6e924e07
DK
1652 __k = __n - __k;
1653 if (__is_pod(_ValueType) && __k == 1)
c2ba9709 1654 {
6e924e07
DK
1655 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1656 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1657 *__p = _GLIBCXX_MOVE(__t);
1658 return;
c2ba9709 1659 }
6e924e07
DK
1660 _RandomAccessIterator __q = __p + __n;
1661 __p = __q - __k;
1662 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1663 {
1664 --__p;
1665 --__q;
1666 std::iter_swap(__p, __q);
1667 }
1668 __n %= __k;
1669 if (__n == 0)
1670 return;
1671 std::swap(__n, __k);
c2ba9709 1672 }
c2ba9709 1673 }
02d92e3b
SW
1674 }
1675
c0d88161 1676 /**
c2ba9709 1677 * @brief Rotate the elements of a sequence.
5b9daa7e 1678 * @ingroup mutating_algorithms
93c66bc6
BK
1679 * @param __first A forward iterator.
1680 * @param __middle A forward iterator.
1681 * @param __last A forward iterator.
c2ba9709 1682 * @return Nothing.
c0d88161 1683 *
93c66bc6 1684 * Rotates the elements of the range @p [__first,__last) by
7897a1c0 1685 * @p (__middle - __first) positions so that the element at @p __middle
93c66bc6 1686 * is moved to @p __first, the element at @p __middle+1 is moved to
7897a1c0 1687 * @p __first+1 and so on for each element in the range
93c66bc6 1688 * @p [__first,__last).
c0d88161 1689 *
93c66bc6
BK
1690 * This effectively swaps the ranges @p [__first,__middle) and
1691 * @p [__middle,__last).
c2ba9709 1692 *
93c66bc6
BK
1693 * Performs
1694 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1695 * for each @p n in the range @p [0,__last-__first).
c0d88161 1696 */
c2ba9709
JS
1697 template<typename _ForwardIterator>
1698 inline void
1699 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1700 _ForwardIterator __last)
02d92e3b
SW
1701 {
1702 // concept requirements
ffa67767
PC
1703 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1704 _ForwardIterator>)
c2ba9709
JS
1705 __glibcxx_requires_valid_range(__first, __middle);
1706 __glibcxx_requires_valid_range(__middle, __last);
02d92e3b 1707
c2ba9709
JS
1708 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1709 _IterType;
1710 std::__rotate(__first, __middle, __last, _IterType());
02d92e3b 1711 }
725dc051 1712
c0d88161 1713 /**
c2ba9709 1714 * @brief Copy a sequence, rotating its elements.
5b9daa7e 1715 * @ingroup mutating_algorithms
93c66bc6
BK
1716 * @param __first A forward iterator.
1717 * @param __middle A forward iterator.
1718 * @param __last A forward iterator.
1719 * @param __result An output iterator.
c0d88161
JW
1720 * @return An iterator designating the end of the resulting sequence.
1721 *
93c66bc6
BK
1722 * Copies the elements of the range @p [__first,__last) to the
1723 * range beginning at @result, rotating the copied elements by
1724 * @p (__middle-__first) positions so that the element at @p __middle
1725 * is moved to @p __result, the element at @p __middle+1 is moved
7897a1c0 1726 * to @p __result+1 and so on for each element in the range @p
93c66bc6 1727 * [__first,__last).
c0d88161 1728 *
93c66bc6
BK
1729 * Performs
1730 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1731 * for each @p n in the range @p [0,__last-__first).
c0d88161 1732 */
c2ba9709
JS
1733 template<typename _ForwardIterator, typename _OutputIterator>
1734 _OutputIterator
1735 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1736 _ForwardIterator __last, _OutputIterator __result)
02d92e3b
SW
1737 {
1738 // concept requirements
c2ba9709
JS
1739 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1740 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1741 typename iterator_traits<_ForwardIterator>::value_type>)
1742 __glibcxx_requires_valid_range(__first, __middle);
1743 __glibcxx_requires_valid_range(__middle, __last);
30a20a1e 1744
c2ba9709
JS
1745 return std::copy(__first, __middle,
1746 std::copy(__middle, __last, __result));
02d92e3b
SW
1747 }
1748
4312e020 1749 /// This is a helper function...
c2ba9709 1750 template<typename _ForwardIterator, typename _Predicate>
da5a2efd 1751 _ForwardIterator
c2ba9709 1752 __partition(_ForwardIterator __first, _ForwardIterator __last,
3a6b0f54 1753 _Predicate __pred, forward_iterator_tag)
02d92e3b 1754 {
da5a2efd 1755 if (__first == __last)
c2ba9709 1756 return __first;
da5a2efd 1757
c2ba9709
JS
1758 while (__pred(*__first))
1759 if (++__first == __last)
1760 return __first;
da5a2efd 1761
c2ba9709 1762 _ForwardIterator __next = __first;
da5a2efd 1763
c2ba9709
JS
1764 while (++__next != __last)
1765 if (__pred(*__next))
1766 {
3a6b0f54 1767 std::iter_swap(__first, __next);
c2ba9709
JS
1768 ++__first;
1769 }
da5a2efd 1770
c2ba9709 1771 return __first;
da5a2efd
PC
1772 }
1773
4312e020 1774 /// This is a helper function...
c2ba9709
JS
1775 template<typename _BidirectionalIterator, typename _Predicate>
1776 _BidirectionalIterator
1777 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
3a6b0f54 1778 _Predicate __pred, bidirectional_iterator_tag)
da5a2efd 1779 {
c2ba9709
JS
1780 while (true)
1781 {
1782 while (true)
1783 if (__first == __last)
1784 return __first;
1785 else if (__pred(*__first))
1786 ++__first;
1787 else
1788 break;
1789 --__last;
1790 while (true)
1791 if (__first == __last)
1792 return __first;
1793 else if (!bool(__pred(*__last)))
1794 --__last;
1795 else
1796 break;
1797 std::iter_swap(__first, __last);
1798 ++__first;
1799 }
da5a2efd
PC
1800 }
1801
c2ba9709
JS
1802 // partition
1803
4312e020 1804 /// This is a helper function...
2fc9b37d
JY
1805 /// Requires __len != 0 and !__pred(*__first),
1806 /// same as __stable_partition_adaptive.
c2ba9709
JS
1807 template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1808 _ForwardIterator
1809 __inplace_stable_partition(_ForwardIterator __first,
c2ba9709 1810 _Predicate __pred, _Distance __len)
3089d5a4 1811 {
c2ba9709 1812 if (__len == 1)
2fc9b37d 1813 return __first;
c2ba9709
JS
1814 _ForwardIterator __middle = __first;
1815 std::advance(__middle, __len / 2);
2fc9b37d
JY
1816 _ForwardIterator __left_split =
1817 std::__inplace_stable_partition(__first, __pred, __len / 2);
1818 // Advance past true-predicate values to satisfy this
1819 // function's preconditions.
1820 _Distance __right_len = __len - __len / 2;
1821 _ForwardIterator __right_split =
1822 std::__find_if_not_n(__middle, __right_len, __pred);
1823 if (__right_len)
1824 __right_split = std::__inplace_stable_partition(__middle,
1825 __pred,
1826 __right_len);
1827 std::rotate(__left_split, __middle, __right_split);
1828 std::advance(__left_split, std::distance(__middle, __right_split));
1829 return __left_split;
3089d5a4
PC
1830 }
1831
4312e020 1832 /// This is a helper function...
2fc9b37d
JY
1833 /// Requires __first != __last and !__pred(*__first)
1834 /// and __len == distance(__first, __last).
1835 ///
1836 /// !__pred(*__first) allows us to guarantee that we don't
1837 /// move-assign an element onto itself.
c2ba9709
JS
1838 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1839 typename _Distance>
08addde6 1840 _ForwardIterator
c2ba9709
JS
1841 __stable_partition_adaptive(_ForwardIterator __first,
1842 _ForwardIterator __last,
1843 _Predicate __pred, _Distance __len,
1844 _Pointer __buffer,
1845 _Distance __buffer_size)
02d92e3b 1846 {
c2ba9709
JS
1847 if (__len <= __buffer_size)
1848 {
1849 _ForwardIterator __result1 = __first;
1850 _Pointer __result2 = __buffer;
2fc9b37d
JY
1851 // The precondition guarantees that !__pred(*__first), so
1852 // move that element to the buffer before starting the loop.
1853 // This ensures that we only call __pred once per element.
1854 *__result2 = _GLIBCXX_MOVE(*__first);
1855 ++__result2;
1856 ++__first;
c2ba9709
JS
1857 for (; __first != __last; ++__first)
1858 if (__pred(*__first))
1859 {
fe03b3df 1860 *__result1 = _GLIBCXX_MOVE(*__first);
c2ba9709
JS
1861 ++__result1;
1862 }
1863 else
1864 {
fe03b3df 1865 *__result2 = _GLIBCXX_MOVE(*__first);
c2ba9709
JS
1866 ++__result2;
1867 }
fe03b3df 1868 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
c2ba9709
JS
1869 return __result1;
1870 }
1871 else
1872 {
1873 _ForwardIterator __middle = __first;
1874 std::advance(__middle, __len / 2);
2fc9b37d 1875 _ForwardIterator __left_split =
c2ba9709
JS
1876 std::__stable_partition_adaptive(__first, __middle, __pred,
1877 __len / 2, __buffer,
1878 __buffer_size);
2fc9b37d
JY
1879 // Advance past true-predicate values to satisfy this
1880 // function's preconditions.
1881 _Distance __right_len = __len - __len / 2;
1882 _ForwardIterator __right_split =
1883 std::__find_if_not_n(__middle, __right_len, __pred);
1884 if (__right_len)
1885 __right_split =
1886 std::__stable_partition_adaptive(__right_split, __last, __pred,
1887 __right_len,
1888 __buffer, __buffer_size);
1889 std::rotate(__left_split, __middle, __right_split);
1890 std::advance(__left_split, std::distance(__middle, __right_split));
1891 return __left_split;
c2ba9709 1892 }
02d92e3b
SW
1893 }
1894
c0d88161 1895 /**
c2ba9709
JS
1896 * @brief Move elements for which a predicate is true to the beginning
1897 * of a sequence, preserving relative ordering.
5b9daa7e 1898 * @ingroup mutating_algorithms
93c66bc6
BK
1899 * @param __first A forward iterator.
1900 * @param __last A forward iterator.
1901 * @param __pred A predicate functor.
1902 * @return An iterator @p middle such that @p __pred(i) is true for each
c2ba9709
JS
1903 * iterator @p i in the range @p [first,middle) and false for each @p i
1904 * in the range @p [middle,last).
1905 *
1906 * Performs the same function as @p partition() with the additional
1907 * guarantee that the relative ordering of elements in each group is
1908 * preserved, so any two elements @p x and @p y in the range
93c66bc6 1909 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
c2ba9709 1910 * relative ordering after calling @p stable_partition().
3089d5a4 1911 */
c2ba9709
JS
1912 template<typename _ForwardIterator, typename _Predicate>
1913 _ForwardIterator
1914 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1915 _Predicate __pred)
3089d5a4 1916 {
c2ba9709
JS
1917 // concept requirements
1918 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1919 _ForwardIterator>)
1920 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1921 typename iterator_traits<_ForwardIterator>::value_type>)
1922 __glibcxx_requires_valid_range(__first, __last);
3089d5a4 1923
2fc9b37d
JY
1924 __first = std::__find_if_not(__first, __last, __pred);
1925
c2ba9709
JS
1926 if (__first == __last)
1927 return __first;
1928 else
1929 {
1930 typedef typename iterator_traits<_ForwardIterator>::value_type
1931 _ValueType;
1932 typedef typename iterator_traits<_ForwardIterator>::difference_type
1933 _DistanceType;
1934
1935 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1936 __last);
1937 if (__buf.size() > 0)
1938 return
1939 std::__stable_partition_adaptive(__first, __last, __pred,
1940 _DistanceType(__buf.requested_size()),
1941 __buf.begin(),
1942 _DistanceType(__buf.size()));
1943 else
1944 return
2fc9b37d 1945 std::__inplace_stable_partition(__first, __pred,
c2ba9709
JS
1946 _DistanceType(__buf.requested_size()));
1947 }
3089d5a4
PC
1948 }
1949
4312e020 1950 /// This is a helper function for the sort routines.
c2ba9709
JS
1951 template<typename _RandomAccessIterator>
1952 void
1953 __heap_select(_RandomAccessIterator __first,
1954 _RandomAccessIterator __middle,
1955 _RandomAccessIterator __last)
02d92e3b 1956 {
c2ba9709
JS
1957 std::make_heap(__first, __middle);
1958 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1959 if (*__i < *__first)
d70e9d81 1960 std::__pop_heap(__first, __middle, __i);
02d92e3b
SW
1961 }
1962
4312e020 1963 /// This is a helper function for the sort routines.
c2ba9709
JS
1964 template<typename _RandomAccessIterator, typename _Compare>
1965 void
1966 __heap_select(_RandomAccessIterator __first,
1967 _RandomAccessIterator __middle,
1968 _RandomAccessIterator __last, _Compare __comp)
02d92e3b 1969 {
c2ba9709
JS
1970 std::make_heap(__first, __middle, __comp);
1971 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1972 if (__comp(*__i, *__first))
d70e9d81 1973 std::__pop_heap(__first, __middle, __i, __comp);
02d92e3b
SW
1974 }
1975
c2ba9709
JS
1976 // partial_sort
1977
c868f37e 1978 /**
c2ba9709 1979 * @brief Copy the smallest elements of a sequence.
5b9daa7e 1980 * @ingroup sorting_algorithms
93c66bc6
BK
1981 * @param __first An iterator.
1982 * @param __last Another iterator.
1983 * @param __result_first A random-access iterator.
1984 * @param __result_last Another random-access iterator.
c2ba9709 1985 * @return An iterator indicating the end of the resulting sequence.
3089d5a4 1986 *
93c66bc6
BK
1987 * Copies and sorts the smallest N values from the range @p [__first,__last)
1988 * to the range beginning at @p __result_first, where the number of
1989 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1990 * @p (__result_last-__result_first).
7897a1c0
BK
1991 * After the sort if @e i and @e j are iterators in the range
1992 * @p [__result_first,__result_first+N) such that i precedes j then
1993 * *j<*i is false.
93c66bc6 1994 * The value returned is @p __result_first+N.
c868f37e 1995 */
c2ba9709
JS
1996 template<typename _InputIterator, typename _RandomAccessIterator>
1997 _RandomAccessIterator
1998 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1999 _RandomAccessIterator __result_first,
2000 _RandomAccessIterator __result_last)
c868f37e 2001 {
c2ba9709
JS
2002 typedef typename iterator_traits<_InputIterator>::value_type
2003 _InputValueType;
2004 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2005 _OutputValueType;
2006 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2007 _DistanceType;
2008
2009 // concept requirements
2010 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2011 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2012 _OutputValueType>)
2013 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2014 _OutputValueType>)
2015 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
285b36d6 2016 __glibcxx_requires_valid_range(__first, __last);
c2ba9709 2017 __glibcxx_requires_valid_range(__result_first, __result_last);
c868f37e 2018
c2ba9709
JS
2019 if (__result_first == __result_last)
2020 return __result_last;
2021 _RandomAccessIterator __result_real_last = __result_first;
2022 while(__first != __last && __result_real_last != __result_last)
2023 {
2024 *__result_real_last = *__first;
2025 ++__result_real_last;
2026 ++__first;
2027 }
2028 std::make_heap(__result_first, __result_real_last);
2029 while (__first != __last)
2030 {
2031 if (*__first < *__result_first)
2032 std::__adjust_heap(__result_first, _DistanceType(0),
2033 _DistanceType(__result_real_last
2034 - __result_first),
2035 _InputValueType(*__first));
2036 ++__first;
2037 }
2038 std::sort_heap(__result_first, __result_real_last);
2039 return __result_real_last;
c868f37e
PC
2040 }
2041
c0d88161 2042 /**
c2ba9709
JS
2043 * @brief Copy the smallest elements of a sequence using a predicate for
2044 * comparison.
5b9daa7e 2045 * @ingroup sorting_algorithms
93c66bc6
BK
2046 * @param __first An input iterator.
2047 * @param __last Another input iterator.
2048 * @param __result_first A random-access iterator.
2049 * @param __result_last Another random-access iterator.
2050 * @param __comp A comparison functor.
c2ba9709 2051 * @return An iterator indicating the end of the resulting sequence.
3089d5a4 2052 *
93c66bc6 2053 * Copies and sorts the smallest N values from the range @p [__first,__last)
c2ba9709 2054 * to the range beginning at @p result_first, where the number of
93c66bc6
BK
2055 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
2056 * @p (__result_last-__result_first).
7897a1c0
BK
2057 * After the sort if @e i and @e j are iterators in the range
2058 * @p [__result_first,__result_first+N) such that i precedes j then
93c66bc6
BK
2059 * @p __comp(*j,*i) is false.
2060 * The value returned is @p __result_first+N.
c0d88161 2061 */
c2ba9709
JS
2062 template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2063 _RandomAccessIterator
2064 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2065 _RandomAccessIterator __result_first,
2066 _RandomAccessIterator __result_last,
2067 _Compare __comp)
02d92e3b 2068 {
c2ba9709
JS
2069 typedef typename iterator_traits<_InputIterator>::value_type
2070 _InputValueType;
2071 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2072 _OutputValueType;
2073 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2074 _DistanceType;
2075
2076 // concept requirements
3d7c150e 2077 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
c2ba9709
JS
2078 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2079 _RandomAccessIterator>)
2080 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2081 _OutputValueType>)
2082 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2083 _InputValueType, _OutputValueType>)
2084 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2085 _OutputValueType, _OutputValueType>)
285b36d6 2086 __glibcxx_requires_valid_range(__first, __last);
c2ba9709 2087 __glibcxx_requires_valid_range(__result_first, __result_last);
c0d88161 2088
c2ba9709
JS
2089 if (__result_first == __result_last)
2090 return __result_last;
2091 _RandomAccessIterator __result_real_last = __result_first;
2092 while(__first != __last && __result_real_last != __result_last)
2093 {
2094 *__result_real_last = *__first;
2095 ++__result_real_last;
2096 ++__first;
2097 }
2098 std::make_heap(__result_first, __result_real_last, __comp);
2099 while (__first != __last)
2100 {
2101 if (__comp(*__first, *__result_first))
2102 std::__adjust_heap(__result_first, _DistanceType(0),
2103 _DistanceType(__result_real_last
2104 - __result_first),
2105 _InputValueType(*__first),
2106 __comp);
2107 ++__first;
2108 }
2109 std::sort_heap(__result_first, __result_real_last, __comp);
2110 return __result_real_last;
02d92e3b
SW
2111 }
2112
4312e020 2113 /// This is a helper function for the sort routine.
f9590eae 2114 template<typename _RandomAccessIterator>
02d92e3b 2115 void
f9590eae 2116 __unguarded_linear_insert(_RandomAccessIterator __last)
02d92e3b 2117 {
f9590eae
CJ
2118 typename iterator_traits<_RandomAccessIterator>::value_type
2119 __val = _GLIBCXX_MOVE(*__last);
c2ba9709
JS
2120 _RandomAccessIterator __next = __last;
2121 --__next;
2122 while (__val < *__next)
2123 {
f9590eae 2124 *__last = _GLIBCXX_MOVE(*__next);
c2ba9709
JS
2125 __last = __next;
2126 --__next;
2127 }
f9590eae 2128 *__last = _GLIBCXX_MOVE(__val);
02d92e3b
SW
2129 }
2130
4312e020 2131 /// This is a helper function for the sort routine.
f9590eae 2132 template<typename _RandomAccessIterator, typename _Compare>
02d92e3b 2133 void
f9590eae 2134 __unguarded_linear_insert(_RandomAccessIterator __last,
c2ba9709 2135 _Compare __comp)
02d92e3b 2136 {
f9590eae
CJ
2137 typename iterator_traits<_RandomAccessIterator>::value_type
2138 __val = _GLIBCXX_MOVE(*__last);
c2ba9709
JS
2139 _RandomAccessIterator __next = __last;
2140 --__next;
2141 while (__comp(__val, *__next))
dbb8bfe8 2142 {
f9590eae 2143 *__last = _GLIBCXX_MOVE(*__next);
c2ba9709
JS
2144 __last = __next;
2145 --__next;
dbb8bfe8 2146 }
f9590eae 2147 *__last = _GLIBCXX_MOVE(__val);
02d92e3b
SW
2148 }
2149
4312e020 2150 /// This is a helper function for the sort routine.
c2ba9709
JS
2151 template<typename _RandomAccessIterator>
2152 void
2153 __insertion_sort(_RandomAccessIterator __first,
2154 _RandomAccessIterator __last)
02d92e3b 2155 {
c2ba9709
JS
2156 if (__first == __last)
2157 return;
02d92e3b 2158
c2ba9709 2159 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
ffa67767 2160 {
f9590eae 2161 if (*__i < *__first)
c2ba9709 2162 {
f9590eae
CJ
2163 typename iterator_traits<_RandomAccessIterator>::value_type
2164 __val = _GLIBCXX_MOVE(*__i);
2165 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2166 *__first = _GLIBCXX_MOVE(__val);
c2ba9709
JS
2167 }
2168 else
f9590eae 2169 std::__unguarded_linear_insert(__i);
ffa67767 2170 }
02d92e3b 2171 }
725dc051 2172
4312e020 2173 /// This is a helper function for the sort routine.
c2ba9709
JS
2174 template<typename _RandomAccessIterator, typename _Compare>
2175 void
2176 __insertion_sort(_RandomAccessIterator __first,
2177 _RandomAccessIterator __last, _Compare __comp)
02d92e3b 2178 {
c2ba9709
JS
2179 if (__first == __last) return;
2180
2181 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
ffa67767 2182 {
f9590eae 2183 if (__comp(*__i, *__first))
c2ba9709 2184 {
f9590eae
CJ
2185 typename iterator_traits<_RandomAccessIterator>::value_type
2186 __val = _GLIBCXX_MOVE(*__i);
2187 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2188 *__first = _GLIBCXX_MOVE(__val);
c2ba9709
JS
2189 }
2190 else
f9590eae 2191 std::__unguarded_linear_insert(__i, __comp);
ffa67767 2192 }
02d92e3b
SW
2193 }
2194
4312e020 2195 /// This is a helper function for the sort routine.
c2ba9709
JS
2196 template<typename _RandomAccessIterator>
2197 inline void
2198 __unguarded_insertion_sort(_RandomAccessIterator __first,
2199 _RandomAccessIterator __last)
02d92e3b 2200 {
c2ba9709
JS
2201 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2202 _ValueType;
c0d88161 2203
c2ba9709 2204 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
f9590eae 2205 std::__unguarded_linear_insert(__i);
02d92e3b 2206 }
c0d88161 2207
4312e020 2208 /// This is a helper function for the sort routine.
c2ba9709
JS
2209 template<typename _RandomAccessIterator, typename _Compare>
2210 inline void
2211 __unguarded_insertion_sort(_RandomAccessIterator __first,
2212 _RandomAccessIterator __last, _Compare __comp)
02d92e3b 2213 {
c2ba9709
JS
2214 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2215 _ValueType;
c0d88161 2216
c2ba9709 2217 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
f9590eae 2218 std::__unguarded_linear_insert(__i, __comp);
c2ba9709 2219 }
c0d88161 2220
c2ba9709 2221 /**
c2ba9709
JS
2222 * @doctodo
2223 * This controls some aspect of the sort routines.
c2ba9709
JS
2224 */
2225 enum { _S_threshold = 16 };
c0d88161 2226
4312e020 2227 /// This is a helper function for the sort routine.
c2ba9709
JS
2228 template<typename _RandomAccessIterator>
2229 void
2230 __final_insertion_sort(_RandomAccessIterator __first,
2231 _RandomAccessIterator __last)
2232 {
2233 if (__last - __first > int(_S_threshold))
dbb8bfe8 2234 {
c2ba9709
JS
2235 std::__insertion_sort(__first, __first + int(_S_threshold));
2236 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
dbb8bfe8 2237 }
ffa67767 2238 else
c2ba9709 2239 std::__insertion_sort(__first, __last);
02d92e3b 2240 }
c0d88161 2241
4312e020 2242 /// This is a helper function for the sort routine.
c2ba9709 2243 template<typename _RandomAccessIterator, typename _Compare>
02d92e3b 2244 void
c2ba9709
JS
2245 __final_insertion_sort(_RandomAccessIterator __first,
2246 _RandomAccessIterator __last, _Compare __comp)
02d92e3b 2247 {
c2ba9709 2248 if (__last - __first > int(_S_threshold))
ffa67767 2249 {
c2ba9709
JS
2250 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2251 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2252 __comp);
02d92e3b 2253 }
c2ba9709
JS
2254 else
2255 std::__insertion_sort(__first, __last, __comp);
2256 }
c0d88161 2257
4312e020 2258 /// This is a helper function...
c2ba9709
JS
2259 template<typename _RandomAccessIterator, typename _Tp>
2260 _RandomAccessIterator
2261 __unguarded_partition(_RandomAccessIterator __first,
f9590eae 2262 _RandomAccessIterator __last, const _Tp& __pivot)
c2ba9709
JS
2263 {
2264 while (true)
ffa67767 2265 {
c2ba9709
JS
2266 while (*__first < __pivot)
2267 ++__first;
2268 --__last;
2269 while (__pivot < *__last)
2270 --__last;
2271 if (!(__first < __last))
2272 return __first;
2273 std::iter_swap(__first, __last);
ffa67767 2274 ++__first;
02d92e3b 2275 }
02d92e3b 2276 }
c0d88161 2277
4312e020 2278 /// This is a helper function...
c2ba9709
JS
2279 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2280 _RandomAccessIterator
2281 __unguarded_partition(_RandomAccessIterator __first,
2282 _RandomAccessIterator __last,
f9590eae 2283 const _Tp& __pivot, _Compare __comp)
02d92e3b 2284 {
c2ba9709
JS
2285 while (true)
2286 {
2287 while (__comp(*__first, __pivot))
2288 ++__first;
2289 --__last;
2290 while (__comp(__pivot, *__last))
2291 --__last;
2292 if (!(__first < __last))
2293 return __first;
2294 std::iter_swap(__first, __last);
2295 ++__first;
2296 }
02d92e3b
SW
2297 }
2298
f9590eae
CJ
2299 /// This is a helper function...
2300 template<typename _RandomAccessIterator>
2301 inline _RandomAccessIterator
2302 __unguarded_partition_pivot(_RandomAccessIterator __first,
2303 _RandomAccessIterator __last)
2304 {
2305 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2306 std::__move_median_first(__first, __mid, (__last - 1));
2307 return std::__unguarded_partition(__first + 1, __last, *__first);
2308 }
2309
2310
2311 /// This is a helper function...
2312 template<typename _RandomAccessIterator, typename _Compare>
2313 inline _RandomAccessIterator
2314 __unguarded_partition_pivot(_RandomAccessIterator __first,
2315 _RandomAccessIterator __last, _Compare __comp)
2316 {
2317 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2318 std::__move_median_first(__first, __mid, (__last - 1), __comp);
2319 return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2320 }
2321
4312e020 2322 /// This is a helper function for the sort routine.
c2ba9709
JS
2323 template<typename _RandomAccessIterator, typename _Size>
2324 void
2325 __introsort_loop(_RandomAccessIterator __first,
2326 _RandomAccessIterator __last,
2327 _Size __depth_limit)
02d92e3b 2328 {
c2ba9709
JS
2329 while (__last - __first > int(_S_threshold))
2330 {
2331 if (__depth_limit == 0)
2332 {
12ffa228 2333 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
c2ba9709
JS
2334 return;
2335 }
2336 --__depth_limit;
2337 _RandomAccessIterator __cut =
f9590eae 2338 std::__unguarded_partition_pivot(__first, __last);
c2ba9709
JS
2339 std::__introsort_loop(__cut, __last, __depth_limit);
2340 __last = __cut;
2341 }
02d92e3b
SW
2342 }
2343
4312e020 2344 /// This is a helper function for the sort routine.
c2ba9709 2345 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02d92e3b 2346 void
c2ba9709
JS
2347 __introsort_loop(_RandomAccessIterator __first,
2348 _RandomAccessIterator __last,
2349 _Size __depth_limit, _Compare __comp)
02d92e3b 2350 {
c2ba9709
JS
2351 while (__last - __first > int(_S_threshold))
2352 {
2353 if (__depth_limit == 0)
2354 {
12ffa228 2355 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
c2ba9709
JS
2356 return;
2357 }
2358 --__depth_limit;
2359 _RandomAccessIterator __cut =
f9590eae 2360 std::__unguarded_partition_pivot(__first, __last, __comp);
c2ba9709
JS
2361 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2362 __last = __cut;
2363 }
02d92e3b
SW
2364 }
2365
c2ba9709 2366 // sort
725dc051 2367
c2ba9709
JS
2368 template<typename _RandomAccessIterator, typename _Size>
2369 void
2370 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2371 _RandomAccessIterator __last, _Size __depth_limit)
2372 {
2373 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2374 _ValueType;
725dc051 2375
c2ba9709
JS
2376 while (__last - __first > 3)
2377 {
2378 if (__depth_limit == 0)
2379 {
2380 std::__heap_select(__first, __nth + 1, __last);
4312e020 2381
c2ba9709
JS
2382 // Place the nth largest element in its final position.
2383 std::iter_swap(__first, __nth);
2384 return;
2385 }
2386 --__depth_limit;
2387 _RandomAccessIterator __cut =
f9590eae 2388 std::__unguarded_partition_pivot(__first, __last);
c2ba9709
JS
2389 if (__cut <= __nth)
2390 __first = __cut;
2391 else
2392 __last = __cut;
2393 }
2394 std::__insertion_sort(__first, __last);
02d92e3b 2395 }
725dc051 2396
c2ba9709
JS
2397 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2398 void
2399 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2400 _RandomAccessIterator __last, _Size __depth_limit,
2401 _Compare __comp)
02d92e3b 2402 {
c2ba9709
JS
2403 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2404 _ValueType;
2405
2406 while (__last - __first > 3)
ffa67767 2407 {
c2ba9709
JS
2408 if (__depth_limit == 0)
2409 {
2410 std::__heap_select(__first, __nth + 1, __last, __comp);
2411 // Place the nth largest element in its final position.
2412 std::iter_swap(__first, __nth);
2413 return;
2414 }
2415 --__depth_limit;
2416 _RandomAccessIterator __cut =
f9590eae 2417 std::__unguarded_partition_pivot(__first, __last, __comp);
c2ba9709
JS
2418 if (__cut <= __nth)
2419 __first = __cut;
2420 else
2421 __last = __cut;
ffa67767 2422 }
c2ba9709 2423 std::__insertion_sort(__first, __last, __comp);
02d92e3b 2424 }
725dc051 2425
c2ba9709
JS
2426 // nth_element
2427
247d8075 2428 // lower_bound moved to stl_algobase.h
02d92e3b 2429
7c842056 2430 /**
7897a1c0 2431 * @brief Finds the first position in which @p __val could be inserted
7c842056
PC
2432 * without changing the ordering.
2433 * @ingroup binary_search_algorithms
93c66bc6
BK
2434 * @param __first An iterator.
2435 * @param __last Another iterator.
2436 * @param __val The search term.
2437 * @param __comp A functor to use for comparisons.
7c842056 2438 * @return An iterator pointing to the first element <em>not less
7897a1c0
BK
2439 * than</em> @p __val, or end() if every element is less
2440 * than @p __val.
7c842056
PC
2441 * @ingroup binary_search_algorithms
2442 *
2443 * The comparison function should have the same effects on ordering as
2444 * the function used for the initial sort.
2445 */
2446 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2447 _ForwardIterator
2448 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2449 const _Tp& __val, _Compare __comp)
2450 {
2451 typedef typename iterator_traits<_ForwardIterator>::value_type
2452 _ValueType;
2453 typedef typename iterator_traits<_ForwardIterator>::difference_type
2454 _DistanceType;
2455
2456 // concept requirements
2457 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2458 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2459 _ValueType, _Tp>)
2460 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2461 __val, __comp);
2462
2463 _DistanceType __len = std::distance(__first, __last);
7c842056
PC
2464
2465 while (__len > 0)
2466 {
1ed78d6c
CY
2467 _DistanceType __half = __len >> 1;
2468 _ForwardIterator __middle = __first;
7c842056
PC
2469 std::advance(__middle, __half);
2470 if (__comp(*__middle, __val))
2471 {
2472 __first = __middle;
2473 ++__first;
2474 __len = __len - __half - 1;
2475 }
2476 else
2477 __len = __half;
2478 }
2479 return __first;
2480 }
2481
037cfe71 2482 /**
7897a1c0 2483 * @brief Finds the last position in which @p __val could be inserted
c2ba9709 2484 * without changing the ordering.
5b9daa7e 2485 * @ingroup binary_search_algorithms
93c66bc6
BK
2486 * @param __first An iterator.
2487 * @param __last Another iterator.
2488 * @param __val The search term.
7897a1c0
BK
2489 * @return An iterator pointing to the first element greater than @p __val,
2490 * or end() if no elements are greater than @p __val.
aac2878e 2491 * @ingroup binary_search_algorithms
037cfe71 2492 */
c2ba9709 2493 template<typename _ForwardIterator, typename _Tp>
08addde6 2494 _ForwardIterator
c2ba9709
JS
2495 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2496 const _Tp& __val)
02d92e3b 2497 {
c2ba9709
JS
2498 typedef typename iterator_traits<_ForwardIterator>::value_type
2499 _ValueType;
2500 typedef typename iterator_traits<_ForwardIterator>::difference_type
2501 _DistanceType;
2502
2503 // concept requirements
2504 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2505 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
f5ad3163 2506 __glibcxx_requires_partitioned_upper(__first, __last, __val);
c2ba9709
JS
2507
2508 _DistanceType __len = std::distance(__first, __last);
c2ba9709
JS
2509
2510 while (__len > 0)
ffa67767 2511 {
1ed78d6c
CY
2512 _DistanceType __half = __len >> 1;
2513 _ForwardIterator __middle = __first;
c2ba9709
JS
2514 std::advance(__middle, __half);
2515 if (__val < *__middle)
2516 __len = __half;
2517 else
2518 {
2519 __first = __middle;
2520 ++__first;
2521 __len = __len - __half - 1;
2522 }
ffa67767 2523 }
c2ba9709 2524 return __first;
725dc051
BK
2525 }
2526
037cfe71 2527 /**
7897a1c0 2528 * @brief Finds the last position in which @p __val could be inserted
c2ba9709 2529 * without changing the ordering.
5b9daa7e 2530 * @ingroup binary_search_algorithms
93c66bc6
BK
2531 * @param __first An iterator.
2532 * @param __last Another iterator.
2533 * @param __val The search term.
2534 * @param __comp A functor to use for comparisons.
7897a1c0
BK
2535 * @return An iterator pointing to the first element greater than @p __val,
2536 * or end() if no elements are greater than @p __val.
aac2878e 2537 * @ingroup binary_search_algorithms
ed6814f7 2538 *
c2ba9709
JS
2539 * The comparison function should have the same effects on ordering as
2540 * the function used for the initial sort.
037cfe71 2541 */
c2ba9709 2542 template<typename _ForwardIterator, typename _Tp, typename _Compare>
08addde6 2543 _ForwardIterator
c2ba9709
JS
2544 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2545 const _Tp& __val, _Compare __comp)
02d92e3b 2546 {
c2ba9709
JS
2547 typedef typename iterator_traits<_ForwardIterator>::value_type
2548 _ValueType;
2549 typedef typename iterator_traits<_ForwardIterator>::difference_type
2550 _DistanceType;
2551
02d92e3b 2552 // concept requirements
c2ba9709
JS
2553 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2554 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2555 _Tp, _ValueType>)
f5ad3163
PC
2556 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2557 __val, __comp);
c0d88161 2558
c2ba9709 2559 _DistanceType __len = std::distance(__first, __last);
ffa67767 2560
c2ba9709
JS
2561 while (__len > 0)
2562 {
1ed78d6c
CY
2563 _DistanceType __half = __len >> 1;
2564 _ForwardIterator __middle = __first;
c2ba9709
JS
2565 std::advance(__middle, __half);
2566 if (__comp(__val, *__middle))
2567 __len = __half;
2568 else
2569 {
2570 __first = __middle;
2571 ++__first;
2572 __len = __len - __half - 1;
2573 }
ffa67767 2574 }
c2ba9709 2575 return __first;
02d92e3b 2576 }
725dc051 2577
037cfe71 2578 /**
7897a1c0 2579 * @brief Finds the largest subrange in which @p __val could be inserted
c2ba9709 2580 * at any place in it without changing the ordering.
5b9daa7e 2581 * @ingroup binary_search_algorithms
93c66bc6
BK
2582 * @param __first An iterator.
2583 * @param __last Another iterator.
2584 * @param __val The search term.
c2ba9709 2585 * @return An pair of iterators defining the subrange.
aac2878e 2586 * @ingroup binary_search_algorithms
c2ba9709
JS
2587 *
2588 * This is equivalent to
2589 * @code
93c66bc6
BK
2590 * std::make_pair(lower_bound(__first, __last, __val),
2591 * upper_bound(__first, __last, __val))
c2ba9709
JS
2592 * @endcode
2593 * but does not actually call those functions.
037cfe71 2594 */
c2ba9709
JS
2595 template<typename _ForwardIterator, typename _Tp>
2596 pair<_ForwardIterator, _ForwardIterator>
2597 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2598 const _Tp& __val)
02d92e3b 2599 {
c2ba9709 2600 typedef typename iterator_traits<_ForwardIterator>::value_type
da5a2efd 2601 _ValueType;
c2ba9709
JS
2602 typedef typename iterator_traits<_ForwardIterator>::difference_type
2603 _DistanceType;
02d92e3b 2604
c2ba9709
JS
2605 // concept requirements
2606 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2607 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2608 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
f5ad3163
PC
2609 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2610 __glibcxx_requires_partitioned_upper(__first, __last, __val);
c2ba9709
JS
2611
2612 _DistanceType __len = std::distance(__first, __last);
1ed78d6c 2613
c2ba9709
JS
2614 while (__len > 0)
2615 {
1ed78d6c
CY
2616 _DistanceType __half = __len >> 1;
2617 _ForwardIterator __middle = __first;
c2ba9709
JS
2618 std::advance(__middle, __half);
2619 if (*__middle < __val)
2620 {
2621 __first = __middle;
2622 ++__first;
2623 __len = __len - __half - 1;
2624 }
2625 else if (__val < *__middle)
2626 __len = __half;
2627 else
2628 {
1ed78d6c
CY
2629 _ForwardIterator __left = std::lower_bound(__first, __middle,
2630 __val);
c2ba9709 2631 std::advance(__first, __len);
1ed78d6c
CY
2632 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2633 __val);
c2ba9709
JS
2634 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2635 }
2636 }
2637 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
725dc051
BK
2638 }
2639
037cfe71 2640 /**
7897a1c0 2641 * @brief Finds the largest subrange in which @p __val could be inserted
c2ba9709 2642 * at any place in it without changing the ordering.
93c66bc6
BK
2643 * @param __first An iterator.
2644 * @param __last Another iterator.
2645 * @param __val The search term.
2646 * @param __comp A functor to use for comparisons.
c2ba9709 2647 * @return An pair of iterators defining the subrange.
aac2878e 2648 * @ingroup binary_search_algorithms
c2ba9709
JS
2649 *
2650 * This is equivalent to
2651 * @code
93c66bc6
BK
2652 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2653 * upper_bound(__first, __last, __val, __comp))
c2ba9709
JS
2654 * @endcode
2655 * but does not actually call those functions.
037cfe71 2656 */
c2ba9709
JS
2657 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2658 pair<_ForwardIterator, _ForwardIterator>
2659 equal_range(_ForwardIterator __first, _ForwardIterator __last,
1ed78d6c 2660 const _Tp& __val, _Compare __comp)
02d92e3b 2661 {
c2ba9709 2662 typedef typename iterator_traits<_ForwardIterator>::value_type
da5a2efd 2663 _ValueType;
c2ba9709
JS
2664 typedef typename iterator_traits<_ForwardIterator>::difference_type
2665 _DistanceType;
da5a2efd 2666
c2ba9709
JS
2667 // concept requirements
2668 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2669 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2670 _ValueType, _Tp>)
2671 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2672 _Tp, _ValueType>)
f5ad3163
PC
2673 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2674 __val, __comp);
2675 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2676 __val, __comp);
c2ba9709
JS
2677
2678 _DistanceType __len = std::distance(__first, __last);
c2ba9709
JS
2679
2680 while (__len > 0)
2681 {
1ed78d6c
CY
2682 _DistanceType __half = __len >> 1;
2683 _ForwardIterator __middle = __first;
c2ba9709
JS
2684 std::advance(__middle, __half);
2685 if (__comp(*__middle, __val))
2686 {
2687 __first = __middle;
2688 ++__first;
2689 __len = __len - __half - 1;
2690 }
2691 else if (__comp(__val, *__middle))
2692 __len = __half;
2693 else
2694 {
1ed78d6c
CY
2695 _ForwardIterator __left = std::lower_bound(__first, __middle,
2696 __val, __comp);
c2ba9709 2697 std::advance(__first, __len);
1ed78d6c
CY
2698 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2699 __val, __comp);
c2ba9709
JS
2700 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2701 }
2702 }
2703 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02d92e3b
SW
2704 }
2705
c868f37e 2706 /**
c2ba9709 2707 * @brief Determines whether an element exists in a range.
5b9daa7e 2708 * @ingroup binary_search_algorithms
93c66bc6
BK
2709 * @param __first An iterator.
2710 * @param __last Another iterator.
2711 * @param __val The search term.
7897a1c0
BK
2712 * @return True if @p __val (or its equivalent) is in [@p
2713 * __first,@p __last ].
c868f37e 2714 *
7897a1c0 2715 * Note that this does not actually return an iterator to @p __val. For
c2ba9709 2716 * that, use std::find or a container's specialized find member functions.
c868f37e 2717 */
c2ba9709
JS
2718 template<typename _ForwardIterator, typename _Tp>
2719 bool
2720 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2721 const _Tp& __val)
c868f37e 2722 {
c2ba9709 2723 typedef typename iterator_traits<_ForwardIterator>::value_type
ffa67767 2724 _ValueType;
c868f37e
PC
2725
2726 // concept requirements
c2ba9709
JS
2727 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2728 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
f5ad3163
PC
2729 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2730 __glibcxx_requires_partitioned_upper(__first, __last, __val);
c868f37e 2731
c2ba9709
JS
2732 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2733 return __i != __last && !(__val < *__i);
c868f37e
PC
2734 }
2735
2736 /**
c2ba9709 2737 * @brief Determines whether an element exists in a range.
5b9daa7e 2738 * @ingroup binary_search_algorithms
93c66bc6
BK
2739 * @param __first An iterator.
2740 * @param __last Another iterator.
2741 * @param __val The search term.
2742 * @param __comp A functor to use for comparisons.
7897a1c0 2743 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
c868f37e 2744 *
7897a1c0 2745 * Note that this does not actually return an iterator to @p __val. For
c2ba9709
JS
2746 * that, use std::find or a container's specialized find member functions.
2747 *
2748 * The comparison function should have the same effects on ordering as
2749 * the function used for the initial sort.
c868f37e 2750 */
c2ba9709
JS
2751 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2752 bool
2753 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2754 const _Tp& __val, _Compare __comp)
c868f37e 2755 {
c2ba9709 2756 typedef typename iterator_traits<_ForwardIterator>::value_type
ffa67767 2757 _ValueType;
c868f37e
PC
2758
2759 // concept requirements
c2ba9709 2760 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3d7c150e 2761 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
c2ba9709 2762 _Tp, _ValueType>)
f5ad3163
PC
2763 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2764 __val, __comp);
2765 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2766 __val, __comp);
c868f37e 2767
c2ba9709
JS
2768 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2769 return __i != __last && !bool(__comp(__val, *__i));
c868f37e
PC
2770 }
2771
c2ba9709
JS
2772 // merge
2773
848ca96f
PC
2774 /// This is a helper function for the __merge_adaptive routines.
2775 template<typename _InputIterator1, typename _InputIterator2,
2776 typename _OutputIterator>
2777 void
2778 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2779 _InputIterator2 __first2, _InputIterator2 __last2,
2780 _OutputIterator __result)
2781 {
2782 while (__first1 != __last1 && __first2 != __last2)
2783 {
2784 if (*__first2 < *__first1)
2785 {
2786 *__result = _GLIBCXX_MOVE(*__first2);
2787 ++__first2;
2788 }
2789 else
2790 {
2791 *__result = _GLIBCXX_MOVE(*__first1);
2792 ++__first1;
2793 }
2794 ++__result;
2795 }
2796 if (__first1 != __last1)
2797 _GLIBCXX_MOVE3(__first1, __last1, __result);
2798 }
2799
2800 /// This is a helper function for the __merge_adaptive routines.
2801 template<typename _InputIterator1, typename _InputIterator2,
2802 typename _OutputIterator, typename _Compare>
2803 void
2804 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2805 _InputIterator2 __first2, _InputIterator2 __last2,
2806 _OutputIterator __result, _Compare __comp)
2807 {
2808 while (__first1 != __last1 && __first2 != __last2)
2809 {
2810 if (__comp(*__first2, *__first1))
2811 {
2812 *__result = _GLIBCXX_MOVE(*__first2);
2813 ++__first2;
2814 }
2815 else
2816 {
2817 *__result = _GLIBCXX_MOVE(*__first1);
2818 ++__first1;
2819 }
2820 ++__result;
2821 }
2822 if (__first1 != __last1)
2823 _GLIBCXX_MOVE3(__first1, __last1, __result);
2824 }
2825
2826 /// This is a helper function for the __merge_adaptive routines.
c2ba9709
JS
2827 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2828 typename _BidirectionalIterator3>
848ca96f
PC
2829 void
2830 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2831 _BidirectionalIterator1 __last1,
2832 _BidirectionalIterator2 __first2,
2833 _BidirectionalIterator2 __last2,
2834 _BidirectionalIterator3 __result)
c868f37e 2835 {
c2ba9709 2836 if (__first1 == __last1)
848ca96f
PC
2837 {
2838 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2839 return;
2840 }
2841 else if (__first2 == __last2)
2842 return;
2843
c2ba9709
JS
2844 --__last1;
2845 --__last2;
2846 while (true)
ffa67767 2847 {
c2ba9709
JS
2848 if (*__last2 < *__last1)
2849 {
60c5236e 2850 *--__result = _GLIBCXX_MOVE(*__last1);
c2ba9709 2851 if (__first1 == __last1)
848ca96f
PC
2852 {
2853 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2854 return;
2855 }
c2ba9709
JS
2856 --__last1;
2857 }
2858 else
2859 {
60c5236e 2860 *--__result = _GLIBCXX_MOVE(*__last2);
c2ba9709 2861 if (__first2 == __last2)
848ca96f 2862 return;
c2ba9709
JS
2863 --__last2;
2864 }
ffa67767 2865 }
c868f37e
PC
2866 }
2867
848ca96f 2868 /// This is a helper function for the __merge_adaptive routines.
c2ba9709
JS
2869 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2870 typename _BidirectionalIterator3, typename _Compare>
848ca96f
PC
2871 void
2872 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2873 _BidirectionalIterator1 __last1,
2874 _BidirectionalIterator2 __first2,
2875 _BidirectionalIterator2 __last2,
2876 _BidirectionalIterator3 __result,
2877 _Compare __comp)
02d92e3b 2878 {
c2ba9709 2879 if (__first1 == __last1)
848ca96f
PC
2880 {
2881 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2882 return;
2883 }
2884 else if (__first2 == __last2)
2885 return;
2886
c2ba9709
JS
2887 --__last1;
2888 --__last2;
2889 while (true)
ffa67767 2890 {
c2ba9709
JS
2891 if (__comp(*__last2, *__last1))
2892 {
60c5236e 2893 *--__result = _GLIBCXX_MOVE(*__last1);
c2ba9709 2894 if (__first1 == __last1)
848ca96f
PC
2895 {
2896 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2897 return;
2898 }
c2ba9709
JS
2899 --__last1;
2900 }
2901 else
2902 {
60c5236e 2903 *--__result = _GLIBCXX_MOVE(*__last2);
c2ba9709 2904 if (__first2 == __last2)
848ca96f 2905 return;
c2ba9709
JS
2906 --__last2;
2907 }
02d92e3b 2908 }
02d92e3b 2909 }
725dc051 2910
4312e020 2911 /// This is a helper function for the merge routines.
c2ba9709
JS
2912 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2913 typename _Distance>
2914 _BidirectionalIterator1
2915 __rotate_adaptive(_BidirectionalIterator1 __first,
2916 _BidirectionalIterator1 __middle,
2917 _BidirectionalIterator1 __last,
2918 _Distance __len1, _Distance __len2,
2919 _BidirectionalIterator2 __buffer,
2920 _Distance __buffer_size)
02d92e3b 2921 {
c2ba9709
JS
2922 _BidirectionalIterator2 __buffer_end;
2923 if (__len1 > __len2 && __len2 <= __buffer_size)
ffa67767 2924 {
848ca96f
PC
2925 if (__len2)
2926 {
2927 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2928 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2929 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2930 }
2931 else
2932 return __first;
c2ba9709
JS
2933 }
2934 else if (__len1 <= __buffer_size)
2935 {
848ca96f
PC
2936 if (__len1)
2937 {
2938 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2939 _GLIBCXX_MOVE3(__middle, __last, __first);
2940 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2941 }
2942 else
2943 return __last;
c2ba9709
JS
2944 }
2945 else
2946 {
2947 std::rotate(__first, __middle, __last);
2948 std::advance(__first, std::distance(__middle, __last));
2949 return __first;
02d92e3b 2950 }
02d92e3b 2951 }
725dc051 2952
4312e020 2953 /// This is a helper function for the merge routines.
c2ba9709
JS
2954 template<typename _BidirectionalIterator, typename _Distance,
2955 typename _Pointer>
da5a2efd 2956 void
c2ba9709
JS
2957 __merge_adaptive(_BidirectionalIterator __first,
2958 _BidirectionalIterator __middle,
2959 _BidirectionalIterator __last,
2960 _Distance __len1, _Distance __len2,
2961 _Pointer __buffer, _Distance __buffer_size)
02d92e3b 2962 {
c2ba9709 2963 if (__len1 <= __len2 && __len1 <= __buffer_size)
ffa67767 2964 {
fe03b3df 2965 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
848ca96f
PC
2966 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2967 __first);
c2ba9709
JS
2968 }
2969 else if (__len2 <= __buffer_size)
2970 {
fe03b3df 2971 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
848ca96f
PC
2972 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2973 __buffer_end, __last);
c2ba9709
JS
2974 }
2975 else
2976 {
2977 _BidirectionalIterator __first_cut = __first;
2978 _BidirectionalIterator __second_cut = __middle;
2979 _Distance __len11 = 0;
2980 _Distance __len22 = 0;
2981 if (__len1 > __len2)
da5a2efd 2982 {
c2ba9709
JS
2983 __len11 = __len1 / 2;
2984 std::advance(__first_cut, __len11);
2985 __second_cut = std::lower_bound(__middle, __last,
2986 *__first_cut);
2987 __len22 = std::distance(__middle, __second_cut);
da5a2efd
PC
2988 }
2989 else
c2ba9709
JS
2990 {
2991 __len22 = __len2 / 2;
2992 std::advance(__second_cut, __len22);
2993 __first_cut = std::upper_bound(__first, __middle,
2994 *__second_cut);
2995 __len11 = std::distance(__first, __first_cut);
2996 }
2997 _BidirectionalIterator __new_middle =
2998 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2999 __len1 - __len11, __len22, __buffer,
3000 __buffer_size);
3001 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3002 __len22, __buffer, __buffer_size);
3003 std::__merge_adaptive(__new_middle, __second_cut, __last,
3004 __len1 - __len11,
3005 __len2 - __len22, __buffer, __buffer_size);
ffa67767 3006 }
02d92e3b 3007 }
c0d88161 3008
4312e020 3009 /// This is a helper function for the merge routines.
c2ba9709
JS
3010 template<typename _BidirectionalIterator, typename _Distance,
3011 typename _Pointer, typename _Compare>
da5a2efd 3012 void
c2ba9709
JS
3013 __merge_adaptive(_BidirectionalIterator __first,
3014 _BidirectionalIterator __middle,
3015 _BidirectionalIterator __last,
3016 _Distance __len1, _Distance __len2,
3017 _Pointer __buffer, _Distance __buffer_size,
3018 _Compare __comp)
02d92e3b 3019 {
c2ba9709 3020 if (__len1 <= __len2 && __len1 <= __buffer_size)
ffa67767 3021 {
fe03b3df 3022 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
848ca96f
PC
3023 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
3024 __first, __comp);
c2ba9709
JS
3025 }
3026 else if (__len2 <= __buffer_size)
3027 {
fe03b3df 3028 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
848ca96f
PC
3029 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
3030 __buffer_end, __last, __comp);
c2ba9709
JS
3031 }
3032 else
3033 {
3034 _BidirectionalIterator __first_cut = __first;
3035 _BidirectionalIterator __second_cut = __middle;
3036 _Distance __len11 = 0;
3037 _Distance __len22 = 0;
3038 if (__len1 > __len2)
da5a2efd 3039 {
c2ba9709
JS
3040 __len11 = __len1 / 2;
3041 std::advance(__first_cut, __len11);
3042 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3043 __comp);
3044 __len22 = std::distance(__middle, __second_cut);
da5a2efd
PC
3045 }
3046 else
c2ba9709
JS
3047 {
3048 __len22 = __len2 / 2;
3049 std::advance(__second_cut, __len22);
3050 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3051 __comp);
3052 __len11 = std::distance(__first, __first_cut);
3053 }
3054 _BidirectionalIterator __new_middle =
3055 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3056 __len1 - __len11, __len22, __buffer,
3057 __buffer_size);
3058 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3059 __len22, __buffer, __buffer_size, __comp);
3060 std::__merge_adaptive(__new_middle, __second_cut, __last,
3061 __len1 - __len11,
3062 __len2 - __len22, __buffer,
3063 __buffer_size, __comp);
ffa67767 3064 }
02d92e3b 3065 }
725dc051 3066
4312e020 3067 /// This is a helper function for the merge routines.
c2ba9709 3068 template<typename _BidirectionalIterator, typename _Distance>
da5a2efd 3069 void
c2ba9709
JS
3070 __merge_without_buffer(_BidirectionalIterator __first,
3071 _BidirectionalIterator __middle,
3072 _BidirectionalIterator __last,
3073 _Distance __len1, _Distance __len2)
da5a2efd 3074 {
c2ba9709
JS
3075 if (__len1 == 0 || __len2 == 0)
3076 return;
3077 if (__len1 + __len2 == 2)
ffa67767 3078 {
c2ba9709
JS
3079 if (*__middle < *__first)
3080 std::iter_swap(__first, __middle);
3081 return;
3082 }
3083 _BidirectionalIterator __first_cut = __first;
3084 _BidirectionalIterator __second_cut = __middle;
3085 _Distance __len11 = 0;
3086 _Distance __len22 = 0;
3087 if (__len1 > __len2)
3088 {
3089 __len11 = __len1 / 2;
3090 std::advance(__first_cut, __len11);
3091 __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3092 __len22 = std::distance(__middle, __second_cut);
c868f37e 3093 }
da5a2efd 3094 else
c2ba9709
JS
3095 {
3096 __len22 = __len2 / 2;
3097 std::advance(__second_cut, __len22);
3098 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3099 __len11 = std::distance(__first, __first_cut);
3100 }
3101 std::rotate(__first_cut, __middle, __second_cut);
3102 _BidirectionalIterator __new_middle = __first_cut;
3103 std::advance(__new_middle, std::distance(__middle, __second_cut));
3104 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3105 __len11, __len22);
3106 std::__merge_without_buffer(__new_middle, __second_cut, __last,
3107 __len1 - __len11, __len2 - __len22);
02d92e3b 3108 }
725dc051 3109
4312e020 3110 /// This is a helper function for the merge routines.
c2ba9709
JS
3111 template<typename _BidirectionalIterator, typename _Distance,
3112 typename _Compare>
da5a2efd 3113 void
c2ba9709
JS
3114 __merge_without_buffer(_BidirectionalIterator __first,
3115 _BidirectionalIterator __middle,
3116 _BidirectionalIterator __last,
3117 _Distance __len1, _Distance __len2,
3118 _Compare __comp)
02d92e3b 3119 {
c2ba9709
JS
3120 if (__len1 == 0 || __len2 == 0)
3121 return;
3122 if (__len1 + __len2 == 2)
ffa67767 3123 {
c2ba9709
JS
3124 if (__comp(*__middle, *__first))
3125 std::iter_swap(__first, __middle);
3126 return;
3127 }
3128 _BidirectionalIterator __first_cut = __first;
3129 _BidirectionalIterator __second_cut = __middle;
3130 _Distance __len11 = 0;
3131 _Distance __len22 = 0;
3132 if (__len1 > __len2)
3133 {
3134 __len11 = __len1 / 2;
3135 std::advance(__first_cut, __len11);
3136 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
da5a2efd 3137 __comp);
c2ba9709 3138 __len22 = std::distance(__middle, __second_cut);
c868f37e 3139 }
da5a2efd 3140 else
ffa67767 3141 {
c2ba9709
JS
3142 __len22 = __len2 / 2;
3143 std::advance(__second_cut, __len22);
3144 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3145 __comp);
3146 __len11 = std::distance(__first, __first_cut);
c868f37e 3147 }
c2ba9709
JS
3148 std::rotate(__first_cut, __middle, __second_cut);
3149 _BidirectionalIterator __new_middle = __first_cut;
3150 std::advance(__new_middle, std::distance(__middle, __second_cut));
3151 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3152 __len11, __len22, __comp);
3153 std::__merge_without_buffer(__new_middle, __second_cut, __last,
3154 __len1 - __len11, __len2 - __len22, __comp);
02d92e3b
SW
3155 }
3156
c868f37e 3157 /**
c2ba9709 3158 * @brief Merges two sorted ranges in place.
5b9daa7e 3159 * @ingroup sorting_algorithms
93c66bc6
BK
3160 * @param __first An iterator.
3161 * @param __middle Another iterator.
3162 * @param __last Another iterator.
da5a2efd 3163 * @return Nothing.
037cfe71 3164 *
93c66bc6
BK
3165 * Merges two sorted and consecutive ranges, [__first,__middle) and
3166 * [__middle,__last), and puts the result in [__first,__last). The
3167 * output will be sorted. The sort is @e stable, that is, for
3168 * equivalent elements in the two ranges, elements from the first
3169 * range will always come before elements from the second.
da5a2efd 3170 *
93c66bc6 3171 * If enough additional memory is available, this takes (__last-__first)-1
c2ba9709 3172 * comparisons. Otherwise an NlogN algorithm is used, where N is
93c66bc6 3173 * distance(__first,__last).
037cfe71 3174 */
c2ba9709
JS
3175 template<typename _BidirectionalIterator>
3176 void
3177 inplace_merge(_BidirectionalIterator __first,
3178 _BidirectionalIterator __middle,
3179 _BidirectionalIterator __last)
02d92e3b 3180 {
c2ba9709
JS
3181 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3182 _ValueType;
3183 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3184 _DistanceType;
e75ea710 3185
02d92e3b 3186 // concept requirements
c2ba9709
JS
3187 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3188 _BidirectionalIterator>)
da5a2efd 3189 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
c2ba9709
JS
3190 __glibcxx_requires_sorted(__first, __middle);
3191 __glibcxx_requires_sorted(__middle, __last);
c0d88161 3192
c2ba9709
JS
3193 if (__first == __middle || __middle == __last)
3194 return;
3195
3196 _DistanceType __len1 = std::distance(__first, __middle);
3197 _DistanceType __len2 = std::distance(__middle, __last);
3198
3199 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3200 __last);
3201 if (__buf.begin() == 0)
3202 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3203 else
3204 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3205 __buf.begin(), _DistanceType(__buf.size()));
02d92e3b
SW
3206 }
3207
037cfe71 3208 /**
c2ba9709 3209 * @brief Merges two sorted ranges in place.
5b9daa7e 3210 * @ingroup sorting_algorithms
93c66bc6
BK
3211 * @param __first An iterator.
3212 * @param __middle Another iterator.
3213 * @param __last Another iterator.
3214 * @param __comp A functor to use for comparisons.
da5a2efd 3215 * @return Nothing.
037cfe71 3216 *
93c66bc6
BK
3217 * Merges two sorted and consecutive ranges, [__first,__middle) and
3218 * [middle,last), and puts the result in [__first,__last). The output will
c2ba9709
JS
3219 * be sorted. The sort is @e stable, that is, for equivalent
3220 * elements in the two ranges, elements from the first range will always
3221 * come before elements from the second.
c868f37e 3222 *
93c66bc6 3223 * If enough additional memory is available, this takes (__last-__first)-1
c2ba9709 3224 * comparisons. Otherwise an NlogN algorithm is used, where N is
93c66bc6 3225 * distance(__first,__last).
c2ba9709
JS
3226 *
3227 * The comparison function should have the same effects on ordering as
3228 * the function used for the initial sort.
037cfe71 3229 */
c2ba9709
JS
3230 template<typename _BidirectionalIterator, typename _Compare>
3231 void
3232 inplace_merge(_BidirectionalIterator __first,
3233 _BidirectionalIterator __middle,
3234 _BidirectionalIterator __last,
3235 _Compare __comp)
02d92e3b 3236 {
c2ba9709
JS
3237 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3238 _ValueType;
3239 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3240 _DistanceType;
e75ea710 3241
02d92e3b 3242 // concept requirements
c2ba9709
JS
3243 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3244 _BidirectionalIterator>)
3245 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3246 _ValueType, _ValueType>)
3247 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3248 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
c0d88161 3249
c2ba9709
JS
3250 if (__first == __middle || __middle == __last)
3251 return;
3252
3253 const _DistanceType __len1 = std::distance(__first, __middle);
3254 const _DistanceType __len2 = std::distance(__middle, __last);
3255
3256 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3257 __last);
3258 if (__buf.begin() == 0)
3259 std::__merge_without_buffer(__first, __middle, __last, __len1,
3260 __len2, __comp);
3261 else
3262 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3263 __buf.begin(), _DistanceType(__buf.size()),
3264 __comp);
02d92e3b
SW
3265 }
3266
848ca96f
PC
3267
3268 /// This is a helper function for the __merge_sort_loop routines.
3269 template<typename _InputIterator1, typename _InputIterator2,
3270 typename _OutputIterator>
3271 _OutputIterator
3272 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3273 _InputIterator2 __first2, _InputIterator2 __last2,
3274 _OutputIterator __result)
3275 {
3276 while (__first1 != __last1 && __first2 != __last2)
3277 {
3278 if (*__first2 < *__first1)
3279 {
3280 *__result = _GLIBCXX_MOVE(*__first2);
3281 ++__first2;
3282 }
3283 else
3284 {
3285 *__result = _GLIBCXX_MOVE(*__first1);
3286 ++__first1;
3287 }
3288 ++__result;
3289 }
3290 return _GLIBCXX_MOVE3(__first2, __last2,
3291 _GLIBCXX_MOVE3(__first1, __last1,
3292 __result));
3293 }
3294
3295 /// This is a helper function for the __merge_sort_loop routines.
3296 template<typename _InputIterator1, typename _InputIterator2,
3297 typename _OutputIterator, typename _Compare>
3298 _OutputIterator
3299 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3300 _InputIterator2 __first2, _InputIterator2 __last2,
3301 _OutputIterator __result, _Compare __comp)
3302 {
3303 while (__first1 != __last1 && __first2 != __last2)
3304 {
3305 if (__comp(*__first2, *__first1))
3306 {
3307 *__result = _GLIBCXX_MOVE(*__first2);
3308 ++__first2;
3309 }
3310 else
3311 {
3312 *__result = _GLIBCXX_MOVE(*__first1);
3313 ++__first1;
3314 }
3315 ++__result;
3316 }
3317 return _GLIBCXX_MOVE3(__first2, __last2,
3318 _GLIBCXX_MOVE3(__first1, __last1,
3319 __result));
3320 }
3321
c2ba9709
JS
3322 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3323 typename _Distance>
02d92e3b 3324 void
c2ba9709
JS
3325 __merge_sort_loop(_RandomAccessIterator1 __first,
3326 _RandomAccessIterator1 __last,
3327 _RandomAccessIterator2 __result,
3328 _Distance __step_size)
ffa67767 3329 {
c2ba9709 3330 const _Distance __two_step = 2 * __step_size;
ffa67767 3331
c2ba9709 3332 while (__last - __first >= __two_step)
ffa67767 3333 {
60c5236e
PC
3334 __result = std::__move_merge(__first, __first + __step_size,
3335 __first + __step_size,
3336 __first + __two_step, __result);
c2ba9709 3337 __first += __two_step;
ffa67767 3338 }
c2ba9709
JS
3339
3340 __step_size = std::min(_Distance(__last - __first), __step_size);
60c5236e
PC
3341 std::__move_merge(__first, __first + __step_size,
3342 __first + __step_size, __last, __result);
02d92e3b
SW
3343 }
3344
c2ba9709
JS
3345 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3346 typename _Distance, typename _Compare>
02d92e3b 3347 void
c2ba9709
JS
3348 __merge_sort_loop(_RandomAccessIterator1 __first,
3349 _RandomAccessIterator1 __last,
3350 _RandomAccessIterator2 __result, _Distance __step_size,
3351 _Compare __comp)
02d92e3b 3352 {
c2ba9709 3353 const _Distance __two_step = 2 * __step_size;
c0d88161 3354
c2ba9709 3355 while (__last - __first >= __two_step)
ffa67767 3356 {
60c5236e
PC
3357 __result = std::__move_merge(__first, __first + __step_size,
3358 __first + __step_size,
3359 __first + __two_step,
3360 __result, __comp);
c2ba9709 3361 __first += __two_step;
ffa67767 3362 }
c2ba9709
JS
3363 __step_size = std::min(_Distance(__last - __first), __step_size);
3364
60c5236e
PC
3365 std::__move_merge(__first,__first + __step_size,
3366 __first + __step_size, __last, __result, __comp);
c868f37e
PC
3367 }
3368
c2ba9709
JS
3369 template<typename _RandomAccessIterator, typename _Distance>
3370 void
3371 __chunk_insertion_sort(_RandomAccessIterator __first,
3372 _RandomAccessIterator __last,
3373 _Distance __chunk_size)
02d92e3b 3374 {
c2ba9709
JS
3375 while (__last - __first >= __chunk_size)
3376 {
3377 std::__insertion_sort(__first, __first + __chunk_size);
3378 __first += __chunk_size;
3379 }
3380 std::__insertion_sort(__first, __last);
02d92e3b 3381 }
725dc051 3382
d98f312c
PC
3383 template<typename _RandomAccessIterator, typename _Distance,
3384 typename _Compare>
c2ba9709
JS
3385 void
3386 __chunk_insertion_sort(_RandomAccessIterator __first,
3387 _RandomAccessIterator __last,
3388 _Distance __chunk_size, _Compare __comp)
02d92e3b 3389 {
c2ba9709
JS
3390 while (__last - __first >= __chunk_size)
3391 {
3392 std::__insertion_sort(__first, __first + __chunk_size, __comp);
3393 __first += __chunk_size;
3394 }
3395 std::__insertion_sort(__first, __last, __comp);
02d92e3b 3396 }
725dc051 3397
c2ba9709
JS
3398 enum { _S_chunk_size = 7 };
3399
3400 template<typename _RandomAccessIterator, typename _Pointer>
3401 void
3402 __merge_sort_with_buffer(_RandomAccessIterator __first,
3403 _RandomAccessIterator __last,
3404 _Pointer __buffer)
02d92e3b 3405 {
c2ba9709
JS
3406 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3407 _Distance;
da5a2efd 3408
c2ba9709
JS
3409 const _Distance __len = __last - __first;
3410 const _Pointer __buffer_last = __buffer + __len;
da5a2efd 3411
c2ba9709
JS
3412 _Distance __step_size = _S_chunk_size;
3413 std::__chunk_insertion_sort(__first, __last, __step_size);
da5a2efd 3414
c2ba9709 3415 while (__step_size < __len)
ffa67767 3416 {
c2ba9709
JS
3417 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3418 __step_size *= 2;
3419 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3420 __step_size *= 2;
02d92e3b 3421 }
02d92e3b 3422 }
c0d88161 3423
c2ba9709
JS
3424 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3425 void
3426 __merge_sort_with_buffer(_RandomAccessIterator __first,
3427 _RandomAccessIterator __last,
3428 _Pointer __buffer, _Compare __comp)
02d92e3b 3429 {
c2ba9709
JS
3430 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3431 _Distance;
da5a2efd 3432
c2ba9709
JS
3433 const _Distance __len = __last - __first;
3434 const _Pointer __buffer_last = __buffer + __len;
da5a2efd 3435
c2ba9709
JS
3436 _Distance __step_size = _S_chunk_size;
3437 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
da5a2efd 3438
c2ba9709 3439 while (__step_size < __len)
ffa67767 3440 {
c2ba9709
JS
3441 std::__merge_sort_loop(__first, __last, __buffer,
3442 __step_size, __comp);
3443 __step_size *= 2;
3444 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3445 __step_size, __comp);
3446 __step_size *= 2;
02d92e3b 3447 }
02d92e3b 3448 }
c0d88161 3449
c2ba9709
JS
3450 template<typename _RandomAccessIterator, typename _Pointer,
3451 typename _Distance>
3452 void
3453 __stable_sort_adaptive(_RandomAccessIterator __first,
3454 _RandomAccessIterator __last,
3455 _Pointer __buffer, _Distance __buffer_size)
02d92e3b 3456 {
c2ba9709
JS
3457 const _Distance __len = (__last - __first + 1) / 2;
3458 const _RandomAccessIterator __middle = __first + __len;
3459 if (__len > __buffer_size)
3460 {
3461 std::__stable_sort_adaptive(__first, __middle,
3462 __buffer, __buffer_size);
3463 std::__stable_sort_adaptive(__middle, __last,
3464 __buffer, __buffer_size);
3465 }
3466 else
3467 {
3468 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3469 std::__merge_sort_with_buffer(__middle, __last, __buffer);
3470 }
3471 std::__merge_adaptive(__first, __middle, __last,
3472 _Distance(__middle - __first),
3473 _Distance(__last - __middle),
3474 __buffer, __buffer_size);
3475 }
da5a2efd 3476
c2ba9709
JS
3477 template<typename _RandomAccessIterator, typename _Pointer,
3478 typename _Distance, typename _Compare>
3479 void
3480 __stable_sort_adaptive(_RandomAccessIterator __first,
3481 _RandomAccessIterator __last,
3482 _Pointer __buffer, _Distance __buffer_size,
3483 _Compare __comp)
3484 {
3485 const _Distance __len = (__last - __first + 1) / 2;
3486 const _RandomAccessIterator __middle = __first + __len;
3487 if (__len > __buffer_size)
ffa67767 3488 {
c2ba9709
JS
3489 std::__stable_sort_adaptive(__first, __middle, __buffer,
3490 __buffer_size, __comp);
3491 std::__stable_sort_adaptive(__middle, __last, __buffer,
3492 __buffer_size, __comp);
ffa67767 3493 }
c2ba9709
JS
3494 else
3495 {
3496 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3497 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3498 }
3499 std::__merge_adaptive(__first, __middle, __last,
3500 _Distance(__middle - __first),
3501 _Distance(__last - __middle),
3502 __buffer, __buffer_size,
3503 __comp);
c868f37e
PC
3504 }
3505
4312e020 3506 /// This is a helper function for the stable sorting routines.
c2ba9709
JS
3507 template<typename _RandomAccessIterator>
3508 void
3509 __inplace_stable_sort(_RandomAccessIterator __first,
3510 _RandomAccessIterator __last)
c868f37e 3511 {
c2ba9709 3512 if (__last - __first < 15)
ffa67767 3513 {
c2ba9709
JS
3514 std::__insertion_sort(__first, __last);
3515 return;
ffa67767 3516 }
c2ba9709
JS
3517 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3518 std::__inplace_stable_sort(__first, __middle);
3519 std::__inplace_stable_sort(__middle, __last);
3520 std::__merge_without_buffer(__first, __middle, __last,
3521 __middle - __first,
3522 __last - __middle);
02d92e3b 3523 }
c0d88161 3524
4312e020 3525 /// This is a helper function for the stable sorting routines.
c2ba9709
JS
3526 template<typename _RandomAccessIterator, typename _Compare>
3527 void
3528 __inplace_stable_sort(_RandomAccessIterator __first,
3529 _RandomAccessIterator __last, _Compare __comp)
02d92e3b 3530 {
c2ba9709 3531 if (__last - __first < 15)
ffa67767 3532 {
c2ba9709
JS
3533 std::__insertion_sort(__first, __last, __comp);
3534 return;
ffa67767 3535 }
c2ba9709
JS
3536 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3537 std::__inplace_stable_sort(__first, __middle, __comp);
3538 std::__inplace_stable_sort(__middle, __last, __comp);
3539 std::__merge_without_buffer(__first, __middle, __last,
3540 __middle - __first,
3541 __last - __middle,
3542 __comp);
c0d88161 3543 }
02d92e3b 3544
c2ba9709
JS
3545 // stable_sort
3546
3547 // Set algorithms: includes, set_union, set_intersection, set_difference,
3548 // set_symmetric_difference. All of these algorithms have the precondition
3549 // that their input ranges are sorted and the postcondition that their output
3550 // ranges are sorted.
3551
bf551f96 3552 /**
c2ba9709 3553 * @brief Determines whether all elements of a sequence exists in a range.
93c66bc6
BK
3554 * @param __first1 Start of search range.
3555 * @param __last1 End of search range.
3556 * @param __first2 Start of sequence
3557 * @param __last2 End of sequence.
3558 * @return True if each element in [__first2,__last2) is contained in order
3559 * within [__first1,__last1). False otherwise.
aac2878e 3560 * @ingroup set_algorithms
c868f37e 3561 *
93c66bc6
BK
3562 * This operation expects both [__first1,__last1) and
3563 * [__first2,__last2) to be sorted. Searches for the presence of
3564 * each element in [__first2,__last2) within [__first1,__last1).
3565 * The iterators over each range only move forward, so this is a
3566 * linear algorithm. If an element in [__first2,__last2) is not
7897a1c0 3567 * found before the search iterator reaches @p __last2, false is
93c66bc6 3568 * returned.
bf551f96 3569 */
c2ba9709 3570 template<typename _InputIterator1, typename _InputIterator2>
da5a2efd 3571 bool
c2ba9709
JS
3572 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3573 _InputIterator2 __first2, _InputIterator2 __last2)
02d92e3b 3574 {
da5a2efd
PC
3575 typedef typename iterator_traits<_InputIterator1>::value_type
3576 _ValueType1;
3577 typedef typename iterator_traits<_InputIterator2>::value_type
3578 _ValueType2;
c868f37e 3579
02d92e3b 3580 // concept requirements
da5a2efd
PC
3581 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3582 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
c2ba9709
JS
3583 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3584 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
a4c07f2d
PC
3585 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3586 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
8c093661 3587
da5a2efd 3588 while (__first1 != __last1 && __first2 != __last2)
c2ba9709
JS
3589 if (*__first2 < *__first1)
3590 return false;
3591 else if(*__first1 < *__first2)
3592 ++__first1;
3593 else
3594 ++__first1, ++__first2;
3595
3596 return __first2 == __last2;
8c093661
RS
3597 }
3598
da5a2efd 3599 /**
c2ba9709
JS
3600 * @brief Determines whether all elements of a sequence exists in a range
3601 * using comparison.
5b9daa7e 3602 * @ingroup set_algorithms
93c66bc6
BK
3603 * @param __first1 Start of search range.
3604 * @param __last1 End of search range.
3605 * @param __first2 Start of sequence
3606 * @param __last2 End of sequence.
3607 * @param __comp Comparison function to use.
3608 * @return True if each element in [__first2,__last2) is contained
3609 * in order within [__first1,__last1) according to comp. False
3610 * otherwise. @ingroup set_algorithms
da5a2efd 3611 *
93c66bc6
BK
3612 * This operation expects both [__first1,__last1) and
3613 * [__first2,__last2) to be sorted. Searches for the presence of
3614 * each element in [__first2,__last2) within [__first1,__last1),
3615 * using comp to decide. The iterators over each range only move
3616 * forward, so this is a linear algorithm. If an element in
3617 * [__first2,__last2) is not found before the search iterator
7897a1c0 3618 * reaches @p __last2, false is returned.
da5a2efd
PC
3619 */
3620 template<typename _InputIterator1, typename _InputIterator2,
c2ba9709
JS
3621 typename _Compare>
3622 bool
3623 includes(_InputIterator1 __first1, _InputIterator1 __last1,
a4c07f2d
PC
3624 _InputIterator2 __first2, _InputIterator2 __last2,
3625 _Compare __comp)
8c093661 3626 {
da5a2efd
PC
3627 typedef typename iterator_traits<_InputIterator1>::value_type
3628 _ValueType1;
3629 typedef typename iterator_traits<_InputIterator2>::value_type
3630 _ValueType2;
8c093661 3631
da5a2efd
PC
3632 // concept requirements
3633 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3634 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
c2ba9709
JS
3635 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3636 _ValueType1, _ValueType2>)
da5a2efd
PC
3637 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3638 _ValueType2, _ValueType1>)
a4c07f2d
PC
3639 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3640 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
da5a2efd
PC
3641
3642 while (__first1 != __last1 && __first2 != __last2)
c2ba9709
JS
3643 if (__comp(*__first2, *__first1))
3644 return false;
3645 else if(__comp(*__first1, *__first2))
3646 ++__first1;
3647 else
3648 ++__first1, ++__first2;
3649
3650 return __first2 == __last2;
8c093661
RS
3651 }
3652
c2ba9709
JS
3653 // nth_element
3654 // merge
3655 // set_difference
3656 // set_intersection
3657 // set_union
3658 // stable_sort
3659 // set_symmetric_difference
3660 // min_element
3661 // max_element
3662
bf551f96 3663 /**
7897a1c0 3664 * @brief Permute range into the next @e dictionary ordering.
5b9daa7e 3665 * @ingroup sorting_algorithms
93c66bc6
BK
3666 * @param __first Start of range.
3667 * @param __last End of range.
c2ba9709
JS
3668 * @return False if wrapped to first permutation, true otherwise.
3669 *
7897a1c0 3670 * Treats all permutations of the range as a set of @e dictionary sorted
c2ba9709
JS
3671 * sequences. Permutes the current sequence into the next one of this set.
3672 * Returns true if there are more sequences to generate. If the sequence
3673 * is the largest of the set, the smallest is generated and false returned.
bf551f96 3674 */
c2ba9709
JS
3675 template<typename _BidirectionalIterator>
3676 bool
3677 next_permutation(_BidirectionalIterator __first,
3678 _BidirectionalIterator __last)
02d92e3b 3679 {
c2ba9709
JS
3680 // concept requirements
3681 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3682 _BidirectionalIterator>)
3683 __glibcxx_function_requires(_LessThanComparableConcept<
3684 typename iterator_traits<_BidirectionalIterator>::value_type>)
3685 __glibcxx_requires_valid_range(__first, __last);
3686
3687 if (__first == __last)
3688 return false;
3689 _BidirectionalIterator __i = __first;
3690 ++__i;
3691 if (__i == __last)
3692 return false;
3693 __i = __last;
3694 --__i;
3695
3696 for(;;)
da5a2efd 3697 {
c2ba9709
JS
3698 _BidirectionalIterator __ii = __i;
3699 --__i;
3700 if (*__i < *__ii)
da5a2efd 3701 {
c2ba9709
JS
3702 _BidirectionalIterator __j = __last;
3703 while (!(*__i < *--__j))
3704 {}
3705 std::iter_swap(__i, __j);
3706 std::reverse(__ii, __last);
3707 return true;
da5a2efd 3708 }
c2ba9709 3709 if (__i == __first)
da5a2efd 3710 {
c2ba9709
JS
3711 std::reverse(__first, __last);
3712 return false;
da5a2efd
PC
3713 }
3714 }
02d92e3b
SW
3715 }
3716
bf551f96 3717 /**
7897a1c0 3718 * @brief Permute range into the next @e dictionary ordering using
4b7ed13a 3719 * comparison functor.
5b9daa7e 3720 * @ingroup sorting_algorithms
93c66bc6
BK
3721 * @param __first Start of range.
3722 * @param __last End of range.
3723 * @param __comp A comparison functor.
c2ba9709
JS
3724 * @return False if wrapped to first permutation, true otherwise.
3725 *
93c66bc6 3726 * Treats all permutations of the range [__first,__last) as a set of
7897a1c0 3727 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
c2ba9709
JS
3728 * sequence into the next one of this set. Returns true if there are more
3729 * sequences to generate. If the sequence is the largest of the set, the
3730 * smallest is generated and false returned.
da5a2efd 3731 */
c2ba9709
JS
3732 template<typename _BidirectionalIterator, typename _Compare>
3733 bool
3734 next_permutation(_BidirectionalIterator __first,
3735 _BidirectionalIterator __last, _Compare __comp)
da5a2efd 3736 {
c2ba9709
JS
3737 // concept requirements
3738 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3739 _BidirectionalIterator>)
3740 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3741 typename iterator_traits<_BidirectionalIterator>::value_type,
3742 typename iterator_traits<_BidirectionalIterator>::value_type>)
3743 __glibcxx_requires_valid_range(__first, __last);
3744
3745 if (__first == __last)
3746 return false;
3747 _BidirectionalIterator __i = __first;
3748 ++__i;
3749 if (__i == __last)
3750 return false;
3751 __i = __last;
3752 --__i;
3753
3754 for(;;)
da5a2efd 3755 {
c2ba9709
JS
3756 _BidirectionalIterator __ii = __i;
3757 --__i;
3758 if (__comp(*__i, *__ii))
da5a2efd 3759 {
c2ba9709
JS
3760 _BidirectionalIterator __j = __last;
3761 while (!bool(__comp(*__i, *--__j)))
3762 {}
3763 std::iter_swap(__i, __j);
3764 std::reverse(__ii, __last);
3765 return true;
da5a2efd 3766 }
c2ba9709 3767 if (__i == __first)
da5a2efd 3768 {
c2ba9709
JS
3769 std::reverse(__first, __last);
3770 return false;
da5a2efd
PC
3771 }
3772 }
3773 }
3774
3775 /**
7897a1c0 3776 * @brief Permute range into the previous @e dictionary ordering.
5b9daa7e 3777 * @ingroup sorting_algorithms
93c66bc6
BK
3778 * @param __first Start of range.
3779 * @param __last End of range.
c2ba9709
JS
3780 * @return False if wrapped to last permutation, true otherwise.
3781 *
7897a1c0 3782 * Treats all permutations of the range as a set of @e dictionary sorted
c2ba9709
JS
3783 * sequences. Permutes the current sequence into the previous one of this
3784 * set. Returns true if there are more sequences to generate. If the
3785 * sequence is the smallest of the set, the largest is generated and false
3786 * returned.
da5a2efd 3787 */
c2ba9709
JS
3788 template<typename _BidirectionalIterator>
3789 bool
3790 prev_permutation(_BidirectionalIterator __first,
3791 _BidirectionalIterator __last)
da5a2efd 3792 {
c2ba9709
JS
3793 // concept requirements
3794 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3795 _BidirectionalIterator>)
3796 __glibcxx_function_requires(_LessThanComparableConcept<
3797 typename iterator_traits<_BidirectionalIterator>::value_type>)
3798 __glibcxx_requires_valid_range(__first, __last);
da5a2efd 3799
c2ba9709
JS
3800 if (__first == __last)
3801 return false;
3802 _BidirectionalIterator __i = __first;
3803 ++__i;
3804 if (__i == __last)
3805 return false;
3806 __i = __last;
3807 --__i;
3808
3809 for(;;)
da5a2efd 3810 {
c2ba9709
JS
3811 _BidirectionalIterator __ii = __i;
3812 --__i;
3813 if (*__ii < *__i)
da5a2efd 3814 {
c2ba9709
JS
3815 _BidirectionalIterator __j = __last;
3816 while (!(*--__j < *__i))
3817 {}
3818 std::iter_swap(__i, __j);
3819 std::reverse(__ii, __last);
3820 return true;
da5a2efd 3821 }
c2ba9709 3822 if (__i == __first)
da5a2efd 3823 {
c2ba9709
JS
3824 std::reverse(__first, __last);
3825 return false;
da5a2efd 3826 }
da5a2efd
PC
3827 }
3828 }
3829
3830 /**
7897a1c0 3831 * @brief Permute range into the previous @e dictionary ordering using
4b7ed13a 3832 * comparison functor.
5b9daa7e 3833 * @ingroup sorting_algorithms
93c66bc6
BK
3834 * @param __first Start of range.
3835 * @param __last End of range.
3836 * @param __comp A comparison functor.
c2ba9709
JS
3837 * @return False if wrapped to last permutation, true otherwise.
3838 *
93c66bc6 3839 * Treats all permutations of the range [__first,__last) as a set of
7897a1c0 3840 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
c2ba9709
JS
3841 * sequence into the previous one of this set. Returns true if there are
3842 * more sequences to generate. If the sequence is the smallest of the set,
3843 * the largest is generated and false returned.
da5a2efd 3844 */
c2ba9709
JS
3845 template<typename _BidirectionalIterator, typename _Compare>
3846 bool
3847 prev_permutation(_BidirectionalIterator __first,
3848 _BidirectionalIterator __last, _Compare __comp)
da5a2efd 3849 {
c2ba9709
JS
3850 // concept requirements
3851 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3852 _BidirectionalIterator>)
3853 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3854 typename iterator_traits<_BidirectionalIterator>::value_type,
3855 typename iterator_traits<_BidirectionalIterator>::value_type>)
3856 __glibcxx_requires_valid_range(__first, __last);
3857
3858 if (__first == __last)
3859 return false;
3860 _BidirectionalIterator __i = __first;
3861 ++__i;
3862 if (__i == __last)
3863 return false;
3864 __i = __last;
3865 --__i;
3866
3867 for(;;)
da5a2efd 3868 {
c2ba9709
JS
3869 _BidirectionalIterator __ii = __i;
3870 --__i;
3871 if (__comp(*__ii, *__i))
da5a2efd 3872 {
c2ba9709
JS
3873 _BidirectionalIterator __j = __last;
3874 while (!bool(__comp(*--__j, *__i)))
3875 {}
3876 std::iter_swap(__i, __j);
3877 std::reverse(__ii, __last);
3878 return true;
da5a2efd 3879 }
c2ba9709 3880 if (__i == __first)
da5a2efd 3881 {
c2ba9709
JS
3882 std::reverse(__first, __last);
3883 return false;
da5a2efd 3884 }
da5a2efd
PC
3885 }
3886 }
3887
c2ba9709
JS
3888 // replace
3889 // replace_if
3890
da5a2efd 3891 /**
c2ba9709
JS
3892 * @brief Copy a sequence, replacing each element of one value with another
3893 * value.
93c66bc6
BK
3894 * @param __first An input iterator.
3895 * @param __last An input iterator.
3896 * @param __result An output iterator.
3897 * @param __old_value The value to be replaced.
3898 * @param __new_value The replacement value.
c2ba9709
JS
3899 * @return The end of the output sequence, @p result+(last-first).
3900 *
93c66bc6
BK
3901 * Copies each element in the input range @p [__first,__last) to the
3902 * output range @p [__result,__result+(__last-__first)) replacing elements
3903 * equal to @p __old_value with @p __new_value.
da5a2efd 3904 */
c2ba9709
JS
3905 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3906 _OutputIterator
3907 replace_copy(_InputIterator __first, _InputIterator __last,
3908 _OutputIterator __result,
3909 const _Tp& __old_value, const _Tp& __new_value)
da5a2efd 3910 {
c2ba9709
JS
3911 // concept requirements
3912 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3913 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3914 typename iterator_traits<_InputIterator>::value_type>)
3915 __glibcxx_function_requires(_EqualOpConcept<
3916 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3917 __glibcxx_requires_valid_range(__first, __last);
3918
3919 for (; __first != __last; ++__first, ++__result)
3920 if (*__first == __old_value)
3921 *__result = __new_value;
3922 else
3923 *__result = *__first;
3924 return __result;
da5a2efd
PC
3925 }
3926
3927 /**
c2ba9709
JS
3928 * @brief Copy a sequence, replacing each value for which a predicate
3929 * returns true with another value.
5b9daa7e 3930 * @ingroup mutating_algorithms
93c66bc6
BK
3931 * @param __first An input iterator.
3932 * @param __last An input iterator.
3933 * @param __result An output iterator.
3934 * @param __pred A predicate.
3935 * @param __new_value The replacement value.
3936 * @return The end of the output sequence, @p __result+(__last-__first).
c2ba9709 3937 *
93c66bc6
BK
3938 * Copies each element in the range @p [__first,__last) to the range
3939 * @p [__result,__result+(__last-__first)) replacing elements for which
3940 * @p __pred returns true with @p __new_value.
da5a2efd 3941 */
c2ba9709
JS
3942 template<typename _InputIterator, typename _OutputIterator,
3943 typename _Predicate, typename _Tp>
3944 _OutputIterator
3945 replace_copy_if(_InputIterator __first, _InputIterator __last,
3946 _OutputIterator __result,
3947 _Predicate __pred, const _Tp& __new_value)
da5a2efd 3948 {
c2ba9709
JS
3949 // concept requirements
3950 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3951 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3952 typename iterator_traits<_InputIterator>::value_type>)
3953 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3954 typename iterator_traits<_InputIterator>::value_type>)
3955 __glibcxx_requires_valid_range(__first, __last);
3956
3957 for (; __first != __last; ++__first, ++__result)
3958 if (__pred(*__first))
3959 *__result = __new_value;
3960 else
3961 *__result = *__first;
3962 return __result;
3963 }
3964
734f5023 3965#if __cplusplus >= 201103L
4b7ed13a
PC
3966 /**
3967 * @brief Determines whether the elements of a sequence are sorted.
5b9daa7e 3968 * @ingroup sorting_algorithms
93c66bc6
BK
3969 * @param __first An iterator.
3970 * @param __last Another iterator.
4b7ed13a
PC
3971 * @return True if the elements are sorted, false otherwise.
3972 */
3973 template<typename _ForwardIterator>
3974 inline bool
3975 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3976 { return std::is_sorted_until(__first, __last) == __last; }
3977
3978 /**
3979 * @brief Determines whether the elements of a sequence are sorted
3980 * according to a comparison functor.
5b9daa7e 3981 * @ingroup sorting_algorithms
93c66bc6
BK
3982 * @param __first An iterator.
3983 * @param __last Another iterator.
3984 * @param __comp A comparison functor.
4b7ed13a
PC
3985 * @return True if the elements are sorted, false otherwise.
3986 */
3987 template<typename _ForwardIterator, typename _Compare>
3988 inline bool
3989 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3990 _Compare __comp)
3991 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3992
3993 /**
3994 * @brief Determines the end of a sorted sequence.
5b9daa7e 3995 * @ingroup sorting_algorithms
93c66bc6
BK
3996 * @param __first An iterator.
3997 * @param __last Another iterator.
3998 * @return An iterator pointing to the last iterator i in [__first, __last)
3999 * for which the range [__first, i) is sorted.
4b7ed13a
PC
4000 */
4001 template<typename _ForwardIterator>
4002 _ForwardIterator
4003 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
4004 {
4005 // concept requirements
4006 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4007 __glibcxx_function_requires(_LessThanComparableConcept<
4008 typename iterator_traits<_ForwardIterator>::value_type>)
4009 __glibcxx_requires_valid_range(__first, __last);
4010
4011 if (__first == __last)
4012 return __last;
4013
4014 _ForwardIterator __next = __first;
4015 for (++__next; __next != __last; __first = __next, ++__next)
4016 if (*__next < *__first)
4017 return __next;
4018 return __next;
4019 }
4020
4021 /**
4022 * @brief Determines the end of a sorted sequence using comparison functor.
5b9daa7e 4023 * @ingroup sorting_algorithms
93c66bc6
BK
4024 * @param __first An iterator.
4025 * @param __last Another iterator.
4026 * @param __comp A comparison functor.
4027 * @return An iterator pointing to the last iterator i in [__first, __last)
4028 * for which the range [__first, i) is sorted.
4b7ed13a
PC
4029 */
4030 template<typename _ForwardIterator, typename _Compare>
4031 _ForwardIterator
4032 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4033 _Compare __comp)
4034 {
4035 // concept requirements
4036 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4037 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4038 typename iterator_traits<_ForwardIterator>::value_type,
4039 typename iterator_traits<_ForwardIterator>::value_type>)
4040 __glibcxx_requires_valid_range(__first, __last);
4041
4042 if (__first == __last)
4043 return __last;
4044
4045 _ForwardIterator __next = __first;
4046 for (++__next; __next != __last; __first = __next, ++__next)
4047 if (__comp(*__next, *__first))
4048 return __next;
4049 return __next;
4050 }
f6547b68
PC
4051
4052 /**
4053 * @brief Determines min and max at once as an ordered pair.
5b9daa7e 4054 * @ingroup sorting_algorithms
93c66bc6
BK
4055 * @param __a A thing of arbitrary type.
4056 * @param __b Another thing of arbitrary type.
4057 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4058 * __b) otherwise.
f6547b68
PC
4059 */
4060 template<typename _Tp>
4061 inline pair<const _Tp&, const _Tp&>
4062 minmax(const _Tp& __a, const _Tp& __b)
4063 {
4064 // concept requirements
4065 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4066
4067 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4068 : pair<const _Tp&, const _Tp&>(__a, __b);
4069 }
4070
4071 /**
4072 * @brief Determines min and max at once as an ordered pair.
5b9daa7e 4073 * @ingroup sorting_algorithms
93c66bc6
BK
4074 * @param __a A thing of arbitrary type.
4075 * @param __b Another thing of arbitrary type.
7897a1c0 4076 * @param __comp A @link comparison_functors comparison functor @endlink.
93c66bc6
BK
4077 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4078 * __b) otherwise.
f6547b68
PC
4079 */
4080 template<typename _Tp, typename _Compare>
4081 inline pair<const _Tp&, const _Tp&>
4082 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
4083 {
4084 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
4085 : pair<const _Tp&, const _Tp&>(__a, __b);
4086 }
4087
4088 /**
4089 * @brief Return a pair of iterators pointing to the minimum and maximum
4090 * elements in a range.
5b9daa7e 4091 * @ingroup sorting_algorithms
93c66bc6
BK
4092 * @param __first Start of range.
4093 * @param __last End of range.
f6547b68 4094 * @return make_pair(m, M), where m is the first iterator i in
93c66bc6
BK
4095 * [__first, __last) such that no other element in the range is
4096 * smaller, and where M is the last iterator i in [__first, __last)
f6547b68
PC
4097 * such that no other element in the range is larger.
4098 */
4099 template<typename _ForwardIterator>
4100 pair<_ForwardIterator, _ForwardIterator>
4101 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4102 {
4103 // concept requirements
4104 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4105 __glibcxx_function_requires(_LessThanComparableConcept<
4106 typename iterator_traits<_ForwardIterator>::value_type>)
4107 __glibcxx_requires_valid_range(__first, __last);
4108
4109 _ForwardIterator __next = __first;
4110 if (__first == __last
4111 || ++__next == __last)
4112 return std::make_pair(__first, __first);
4113
4114 _ForwardIterator __min, __max;
4115 if (*__next < *__first)
4116 {
4117 __min = __next;
4118 __max = __first;
4119 }
4120 else
4121 {
4122 __min = __first;
4123 __max = __next;
4124 }
4125
4126 __first = __next;
4127 ++__first;
4128
4129 while (__first != __last)
4130 {
4131 __next = __first;
4132 if (++__next == __last)
4133 {
4134 if (*__first < *__min)
4135 __min = __first;
4136 else if (!(*__first < *__max))
4137 __max = __first;
4138 break;
4139 }
4140
4141 if (*__next < *__first)
4142 {
4143 if (*__next < *__min)
4144 __min = __next;
4145 if (!(*__first < *__max))
4146 __max = __first;
4147 }
4148 else
4149 {
4150 if (*__first < *__min)
4151 __min = __first;
4152 if (!(*__next < *__max))
4153 __max = __next;
4154 }
4155
4156 __first = __next;
4157 ++__first;
4158 }
4159
4160 return std::make_pair(__min, __max);
4161 }
4162
4163 /**
4164 * @brief Return a pair of iterators pointing to the minimum and maximum
4165 * elements in a range.
5b9daa7e 4166 * @ingroup sorting_algorithms
93c66bc6
BK
4167 * @param __first Start of range.
4168 * @param __last End of range.
4169 * @param __comp Comparison functor.
f6547b68 4170 * @return make_pair(m, M), where m is the first iterator i in
93c66bc6
BK
4171 * [__first, __last) such that no other element in the range is
4172 * smaller, and where M is the last iterator i in [__first, __last)
f6547b68
PC
4173 * such that no other element in the range is larger.
4174 */
4175 template<typename _ForwardIterator, typename _Compare>
4176 pair<_ForwardIterator, _ForwardIterator>
4177 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4178 _Compare __comp)
4179 {
4180 // concept requirements
4181 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4182 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4183 typename iterator_traits<_ForwardIterator>::value_type,
4184 typename iterator_traits<_ForwardIterator>::value_type>)
4185 __glibcxx_requires_valid_range(__first, __last);
4186
4187 _ForwardIterator __next = __first;
4188 if (__first == __last
4189 || ++__next == __last)
4190 return std::make_pair(__first, __first);
4191
4192 _ForwardIterator __min, __max;
4193 if (__comp(*__next, *__first))
4194 {
4195 __min = __next;
4196 __max = __first;
4197 }
4198 else
4199 {
4200 __min = __first;
4201 __max = __next;
4202 }
4203
4204 __first = __next;
4205 ++__first;
4206
4207 while (__first != __last)
4208 {
4209 __next = __first;
4210 if (++__next == __last)
4211 {
4212 if (__comp(*__first, *__min))
4213 __min = __first;
4214 else if (!__comp(*__first, *__max))
4215 __max = __first;
4216 break;
4217 }
4218
4219 if (__comp(*__next, *__first))
4220 {
4221 if (__comp(*__next, *__min))
4222 __min = __next;
4223 if (!__comp(*__first, *__max))
4224 __max = __first;
4225 }
4226 else
4227 {
4228 if (__comp(*__first, *__min))
4229 __min = __first;
4230 if (!__comp(*__next, *__max))
4231 __max = __next;
4232 }
4233
4234 __first = __next;
4235 ++__first;
4236 }
4237
4238 return std::make_pair(__min, __max);
4239 }
1edd1a83 4240
e962c1b0 4241 // N2722 + DR 915.
1edd1a83 4242 template<typename _Tp>
116a365b 4243 inline _Tp
1edd1a83
PC
4244 min(initializer_list<_Tp> __l)
4245 { return *std::min_element(__l.begin(), __l.end()); }
4246
4247 template<typename _Tp, typename _Compare>
116a365b 4248 inline _Tp
1edd1a83
PC
4249 min(initializer_list<_Tp> __l, _Compare __comp)
4250 { return *std::min_element(__l.begin(), __l.end(), __comp); }
4251
4252 template<typename _Tp>
116a365b 4253 inline _Tp
1edd1a83
PC
4254 max(initializer_list<_Tp> __l)
4255 { return *std::max_element(__l.begin(), __l.end()); }
4256
4257 template<typename _Tp, typename _Compare>
116a365b 4258 inline _Tp
1edd1a83
PC
4259 max(initializer_list<_Tp> __l, _Compare __comp)
4260 { return *std::max_element(__l.begin(), __l.end(), __comp); }
4261
4262 template<typename _Tp>
116a365b 4263 inline pair<_Tp, _Tp>
1edd1a83
PC
4264 minmax(initializer_list<_Tp> __l)
4265 {
4266 pair<const _Tp*, const _Tp*> __p =
4267 std::minmax_element(__l.begin(), __l.end());
aa4652fa 4268 return std::make_pair(*__p.first, *__p.second);
1edd1a83
PC
4269 }
4270
4271 template<typename _Tp, typename _Compare>
116a365b 4272 inline pair<_Tp, _Tp>
1edd1a83
PC
4273 minmax(initializer_list<_Tp> __l, _Compare __comp)
4274 {
4275 pair<const _Tp*, const _Tp*> __p =
4276 std::minmax_element(__l.begin(), __l.end(), __comp);
4277 return std::make_pair(*__p.first, *__p.second);
4278 }
247d8075 4279
632469d0
PC
4280 /**
4281 * @brief Checks whether a permutaion of the second sequence is equal
4282 * to the first sequence.
4283 * @ingroup non_mutating_algorithms
93c66bc6
BK
4284 * @param __first1 Start of first range.
4285 * @param __last1 End of first range.
4286 * @param __first2 Start of second range.
632469d0 4287 * @return true if there exists a permutation of the elements in the range
93c66bc6
BK
4288 * [__first2, __first2 + (__last1 - __first1)), beginning with
4289 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
632469d0
PC
4290 * returns true; otherwise, returns false.
4291 */
4292 template<typename _ForwardIterator1, typename _ForwardIterator2>
4293 bool
4294 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4295 _ForwardIterator2 __first2)
4296 {
4297 // Efficiently compare identical prefixes: O(N) if sequences
4298 // have the same elements in the same order.
4299 for (; __first1 != __last1; ++__first1, ++__first2)
4300 if (!(*__first1 == *__first2))
4301 break;
4302
4303 if (__first1 == __last1)
4304 return true;
4305
4306 // Establish __last2 assuming equal ranges by iterating over the
4307 // rest of the list.
4308 _ForwardIterator2 __last2 = __first2;
4309 std::advance(__last2, std::distance(__first1, __last1));
4310 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4311 {
12ffa228 4312 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
632469d0
PC
4313 continue; // We've seen this one before.
4314
4315 auto __matches = std::count(__first2, __last2, *__scan);
4316 if (0 == __matches
4317 || std::count(__scan, __last1, *__scan) != __matches)
4318 return false;
4319 }
4320 return true;
4321 }
4322
4323 /**
4324 * @brief Checks whether a permutation of the second sequence is equal
4325 * to the first sequence.
4326 * @ingroup non_mutating_algorithms
93c66bc6
BK
4327 * @param __first1 Start of first range.
4328 * @param __last1 End of first range.
4329 * @param __first2 Start of second range.
4330 * @param __pred A binary predicate.
4331 * @return true if there exists a permutation of the elements in
4332 * the range [__first2, __first2 + (__last1 - __first1)),
4333 * beginning with ForwardIterator2 begin, such that
4334 * equal(__first1, __last1, __begin, __pred) returns true;
4335 * otherwise, returns false.
632469d0
PC
4336 */
4337 template<typename _ForwardIterator1, typename _ForwardIterator2,
4338 typename _BinaryPredicate>
4339 bool
4340 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4341 _ForwardIterator2 __first2, _BinaryPredicate __pred)
4342 {
4343 // Efficiently compare identical prefixes: O(N) if sequences
4344 // have the same elements in the same order.
4345 for (; __first1 != __last1; ++__first1, ++__first2)
4346 if (!bool(__pred(*__first1, *__first2)))
4347 break;
4348
4349 if (__first1 == __last1)
4350 return true;
4351
4352 // Establish __last2 assuming equal ranges by iterating over the
4353 // rest of the list.
4354 _ForwardIterator2 __last2 = __first2;
4355 std::advance(__last2, std::distance(__first1, __last1));
4356 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4357 {
4358 using std::placeholders::_1;
4359
12ffa228 4360 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
632469d0
PC
4361 std::bind(__pred, _1, *__scan)))
4362 continue; // We've seen this one before.
4363
4364 auto __matches = std::count_if(__first2, __last2,
4365 std::bind(__pred, _1, *__scan));
4366 if (0 == __matches
4367 || std::count_if(__scan, __last1,
4368 std::bind(__pred, _1, *__scan)) != __matches)
4369 return false;
4370 }
4371 return true;
4372 }
4373
f7fbb003
JW
4374#if __cplusplus > 201103L
4375 /**
4376 * @brief Checks whether a permutaion of the second sequence is equal
4377 * to the first sequence.
4378 * @ingroup non_mutating_algorithms
4379 * @param __first1 Start of first range.
4380 * @param __last1 End of first range.
4381 * @param __first2 Start of second range.
4382 * @param __last2 End of first range.
4383 * @return true if there exists a permutation of the elements in the range
4384 * [__first2, __last2), beginning with ForwardIterator2 begin,
4385 * such that equal(__first1, __last1, begin) returns true;
4386 * otherwise, returns false.
4387 */
4388 template<typename _ForwardIterator1, typename _ForwardIterator2>
4389 bool
4390 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4391 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4392 {
4393 using _Cat1
4394 = typename iterator_traits<_ForwardIterator1>::iterator_category;
4395 using _Cat2
4396 = typename iterator_traits<_ForwardIterator2>::iterator_category;
4397 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
4398 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
4399 if (_It1_is_RA() && _It1_is_RA())
4400 {
4401 auto __d1 = std::distance(__first1, __last1);
4402 auto __d2 = std::distance(__first2, __last2);
4403 if (__d1 != __d2)
4404 return false;
4405 }
4406
4407 // Efficiently compare identical prefixes: O(N) if sequences
4408 // have the same elements in the same order.
4409 for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
4410 if (!(*__first1 == *__first2))
4411 break;
4412
4413 if (__first1 == __last1 && __first2 == __last2)
4414 return true;
4415
4416 if (std::distance(__first1, __last1) != std::distance(__first2, __last2))
4417 return false;
4418
4419 for (auto __scan = __first1; __scan != __last1; ++__scan)
4420 {
4421 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4422 continue; // We've seen this one before.
4423
4424 auto __matches = std::count(__first2, __last2, *__scan);
4425 if (0 == __matches
4426 || std::count(__scan, __last1, *__scan) != __matches)
4427 return false;
4428 }
4429 return true;
4430 }
4431
4432 /**
4433 * @brief Checks whether a permutation of the second sequence is equal
4434 * to the first sequence.
4435 * @ingroup non_mutating_algorithms
4436 * @param __first1 Start of first range.
4437 * @param __last1 End of first range.
4438 * @param __first2 Start of second range.
4439 * @param __last2 End of first range.
4440 * @param __pred A binary predicate.
4441 * @return true if there exists a permutation of the elements in the range
4442 * [__first2, __last2), beginning with ForwardIterator2 begin,
4443 * such that equal(__first1, __last1, __begin, __pred) returns true;
4444 * otherwise, returns false.
4445 */
4446 template<typename _ForwardIterator1, typename _ForwardIterator2,
4447 typename _BinaryPredicate>
4448 bool
4449 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4450 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4451 _BinaryPredicate __pred)
4452 {
4453 using _Cat1
4454 = typename iterator_traits<_ForwardIterator1>::iterator_category;
4455 using _Cat2
4456 = typename iterator_traits<_ForwardIterator2>::iterator_category;
4457 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
4458 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
4459 constexpr bool __ra_iters = _It1_is_RA() && _It1_is_RA();
4460 if (__ra_iters)
4461 {
4462 auto __d1 = std::distance(__first1, __last1);
4463 auto __d2 = std::distance(__first2, __last2);
4464 if (__d1 != __d2)
4465 return false;
4466 }
4467
4468 // Efficiently compare identical prefixes: O(N) if sequences
4469 // have the same elements in the same order.
4470 for (; __first1 != __last1; ++__first1, ++__first2)
4471 if (!bool(__pred(*__first1, *__first2)))
4472 break;
4473
4474 if (__ra_iters)
4475 {
4476 if (__first1 == __last1)
4477 return true;
4478 }
4479 else
4480 {
4481 auto __d1 = std::distance(__first1, __last1);
4482 auto __d2 = std::distance(__first2, __last2);
4483 if (__d1 == 0 && __d2 == 0)
4484 return true;
4485 if (__d1 != __d2)
4486 return false;
4487 }
4488
4489 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4490 {
4491 using std::placeholders::_1;
4492
4493 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4494 std::bind(__pred, _1, *__scan)))
4495 continue; // We've seen this one before.
4496
4497 auto __matches = std::count_if(__first2, __last2,
4498 std::bind(__pred, _1, *__scan));
4499 if (0 == __matches
4500 || std::count_if(__scan, __last1,
4501 std::bind(__pred, _1, *__scan)) != __matches)
4502 return false;
4503 }
4504 return true;
4505 }
4506#endif
4507
247d8075
PC
4508#ifdef _GLIBCXX_USE_C99_STDINT_TR1
4509 /**
4510 * @brief Shuffle the elements of a sequence using a uniform random
4511 * number generator.
4512 * @ingroup mutating_algorithms
93c66bc6
BK
4513 * @param __first A forward iterator.
4514 * @param __last A forward iterator.
4515 * @param __g A UniformRandomNumberGenerator (26.5.1.3).
247d8075
PC
4516 * @return Nothing.
4517 *
93c66bc6 4518 * Reorders the elements in the range @p [__first,__last) using @p __g to
247d8075
PC
4519 * provide random numbers.
4520 */
4521 template<typename _RandomAccessIterator,
4522 typename _UniformRandomNumberGenerator>
4523 void
4524 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
633e8e19 4525 _UniformRandomNumberGenerator&& __g)
247d8075
PC
4526 {
4527 // concept requirements
4528 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4529 _RandomAccessIterator>)
4530 __glibcxx_requires_valid_range(__first, __last);
4531
4532 if (__first == __last)
4533 return;
4534
4535 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4536 _DistanceType;
4537
4538 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4539 typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
4540 typedef typename __distr_type::param_type __p_type;
4541 __distr_type __d;
4542
4543 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4544 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4545 }
4546#endif
4547
734f5023 4548#endif // C++11
4b7ed13a 4549
12ffa228 4550_GLIBCXX_END_NAMESPACE_VERSION
c2ba9709 4551
12ffa228 4552_GLIBCXX_BEGIN_NAMESPACE_ALGO
c2ba9709
JS
4553
4554 /**
4555 * @brief Apply a function to every element of a sequence.
5b9daa7e 4556 * @ingroup non_mutating_algorithms
93c66bc6
BK
4557 * @param __first An input iterator.
4558 * @param __last An input iterator.
4559 * @param __f A unary function object.
4560 * @return @p __f (std::move(@p __f) in C++0x).
c2ba9709 4561 *
93c66bc6
BK
4562 * Applies the function object @p __f to each element in the range
4563 * @p [first,last). @p __f must not modify the order of the sequence.
4564 * If @p __f has a return value it is ignored.
c2ba9709
JS
4565 */
4566 template<typename _InputIterator, typename _Function>
4567 _Function
4568 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4569 {
4570 // concept requirements
4571 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4572 __glibcxx_requires_valid_range(__first, __last);
4573 for (; __first != __last; ++__first)
4574 __f(*__first);
488d2837 4575 return _GLIBCXX_MOVE(__f);
c2ba9709
JS
4576 }
4577
4578 /**
4579 * @brief Find the first occurrence of a value in a sequence.
5b9daa7e 4580 * @ingroup non_mutating_algorithms
93c66bc6
BK
4581 * @param __first An input iterator.
4582 * @param __last An input iterator.
4583 * @param __val The value to find.
4584 * @return The first iterator @c i in the range @p [__first,__last)
4585 * such that @c *i == @p __val, or @p __last if no such iterator exists.
c2ba9709
JS
4586 */
4587 template<typename _InputIterator, typename _Tp>
4588 inline _InputIterator
4589 find(_InputIterator __first, _InputIterator __last,
4590 const _Tp& __val)
4591 {
4592 // concept requirements
4593 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4594 __glibcxx_function_requires(_EqualOpConcept<
4595 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4596 __glibcxx_requires_valid_range(__first, __last);
4597 return std::__find(__first, __last, __val,
4598 std::__iterator_category(__first));
4599 }
4600
4601 /**
4602 * @brief Find the first element in a sequence for which a
4603 * predicate is true.
5b9daa7e 4604 * @ingroup non_mutating_algorithms
93c66bc6
BK
4605 * @param __first An input iterator.
4606 * @param __last An input iterator.
4607 * @param __pred A predicate.
4608 * @return The first iterator @c i in the range @p [__first,__last)
4609 * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
c2ba9709
JS
4610 */
4611 template<typename _InputIterator, typename _Predicate>
4612 inline _InputIterator
4613 find_if(_InputIterator __first, _InputIterator __last,
4614 _Predicate __pred)
4615 {
4616 // concept requirements
4617 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4618 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4619 typename iterator_traits<_InputIterator>::value_type>)
4620 __glibcxx_requires_valid_range(__first, __last);
4621 return std::__find_if(__first, __last, __pred,
4622 std::__iterator_category(__first));
4623 }
4624
4625 /**
4626 * @brief Find element from a set in a sequence.
5b9daa7e 4627 * @ingroup non_mutating_algorithms
93c66bc6
BK
4628 * @param __first1 Start of range to search.
4629 * @param __last1 End of range to search.
4630 * @param __first2 Start of match candidates.
4631 * @param __last2 End of match candidates.
c2ba9709 4632 * @return The first iterator @c i in the range
93c66bc6
BK
4633 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
4634 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
c2ba9709 4635 *
93c66bc6
BK
4636 * Searches the range @p [__first1,__last1) for an element that is
4637 * equal to some element in the range [__first2,__last2). If
4638 * found, returns an iterator in the range [__first1,__last1),
4639 * otherwise returns @p __last1.
c2ba9709
JS
4640 */
4641 template<typename _InputIterator, typename _ForwardIterator>
4642 _InputIterator
4643 find_first_of(_InputIterator __first1, _InputIterator __last1,
4644 _ForwardIterator __first2, _ForwardIterator __last2)
4645 {
4646 // concept requirements
4647 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4648 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4649 __glibcxx_function_requires(_EqualOpConcept<
4650 typename iterator_traits<_InputIterator>::value_type,
4651 typename iterator_traits<_ForwardIterator>::value_type>)
4652 __glibcxx_requires_valid_range(__first1, __last1);
4653 __glibcxx_requires_valid_range(__first2, __last2);
4654
4655 for (; __first1 != __last1; ++__first1)
4656 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4657 if (*__first1 == *__iter)
4658 return __first1;
4659 return __last1;
4660 }
4661
4662 /**
4663 * @brief Find element from a set in a sequence using a predicate.
5b9daa7e 4664 * @ingroup non_mutating_algorithms
93c66bc6
BK
4665 * @param __first1 Start of range to search.
4666 * @param __last1 End of range to search.
4667 * @param __first2 Start of match candidates.
4668 * @param __last2 End of match candidates.
4669 * @param __comp Predicate to use.
c2ba9709 4670 * @return The first iterator @c i in the range
93c66bc6
BK
4671 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
4672 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
4673 * such iterator exists.
c2ba9709
JS
4674 *
4675
93c66bc6
BK
4676 * Searches the range @p [__first1,__last1) for an element that is
4677 * equal to some element in the range [__first2,__last2). If
4678 * found, returns an iterator in the range [__first1,__last1),
4679 * otherwise returns @p __last1.
c2ba9709
JS
4680 */
4681 template<typename _InputIterator, typename _ForwardIterator,
4682 typename _BinaryPredicate>
4683 _InputIterator
4684 find_first_of(_InputIterator __first1, _InputIterator __last1,
4685 _ForwardIterator __first2, _ForwardIterator __last2,
4686 _BinaryPredicate __comp)
4687 {
4688 // concept requirements
4689 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4690 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4691 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4692 typename iterator_traits<_InputIterator>::value_type,
4693 typename iterator_traits<_ForwardIterator>::value_type>)
4694 __glibcxx_requires_valid_range(__first1, __last1);
4695 __glibcxx_requires_valid_range(__first2, __last2);
4696
4697 for (; __first1 != __last1; ++__first1)
4698 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4699 if (__comp(*__first1, *__iter))
4700 return __first1;
4701 return __last1;
4702 }
4703
4704 /**
4705 * @brief Find two adjacent values in a sequence that are equal.
5b9daa7e 4706 * @ingroup non_mutating_algorithms
93c66bc6
BK
4707 * @param __first A forward iterator.
4708 * @param __last A forward iterator.
c2ba9709 4709 * @return The first iterator @c i such that @c i and @c i+1 are both
93c66bc6
BK
4710 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4711 * or @p __last if no such iterator exists.
c2ba9709
JS
4712 */
4713 template<typename _ForwardIterator>
4714 _ForwardIterator
4715 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4716 {
4717 // concept requirements
4718 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4719 __glibcxx_function_requires(_EqualityComparableConcept<
4720 typename iterator_traits<_ForwardIterator>::value_type>)
4721 __glibcxx_requires_valid_range(__first, __last);
4722 if (__first == __last)
4723 return __last;
4724 _ForwardIterator __next = __first;
4725 while(++__next != __last)
4726 {
4727 if (*__first == *__next)
4728 return __first;
4729 __first = __next;
4730 }
4731 return __last;
4732 }
4733
4734 /**
4735 * @brief Find two adjacent values in a sequence using a predicate.
5b9daa7e 4736 * @ingroup non_mutating_algorithms
93c66bc6
BK
4737 * @param __first A forward iterator.
4738 * @param __last A forward iterator.
4739 * @param __binary_pred A binary predicate.
c2ba9709 4740 * @return The first iterator @c i such that @c i and @c i+1 are both
93c66bc6
BK
4741 * valid iterators in @p [__first,__last) and such that
4742 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
c2ba9709
JS
4743 * exists.
4744 */
4745 template<typename _ForwardIterator, typename _BinaryPredicate>
4746 _ForwardIterator
4747 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4748 _BinaryPredicate __binary_pred)
4749 {
4750 // concept requirements
4751 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4752 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4753 typename iterator_traits<_ForwardIterator>::value_type,
4754 typename iterator_traits<_ForwardIterator>::value_type>)
4755 __glibcxx_requires_valid_range(__first, __last);
4756 if (__first == __last)
4757 return __last;
4758 _ForwardIterator __next = __first;
4759 while(++__next != __last)
4760 {
4761 if (__binary_pred(*__first, *__next))
4762 return __first;
4763 __first = __next;
4764 }
4765 return __last;
4766 }
4767
4768 /**
4769 * @brief Count the number of copies of a value in a sequence.
5b9daa7e 4770 * @ingroup non_mutating_algorithms
93c66bc6
BK
4771 * @param __first An input iterator.
4772 * @param __last An input iterator.
4773 * @param __value The value to be counted.
4774 * @return The number of iterators @c i in the range @p [__first,__last)
4775 * for which @c *i == @p __value
c2ba9709
JS
4776 */
4777 template<typename _InputIterator, typename _Tp>
4778 typename iterator_traits<_InputIterator>::difference_type
4779 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4780 {
4781 // concept requirements
4782 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4783 __glibcxx_function_requires(_EqualOpConcept<
4784 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4785 __glibcxx_requires_valid_range(__first, __last);
4786 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4787 for (; __first != __last; ++__first)
4788 if (*__first == __value)
4789 ++__n;
4790 return __n;
4791 }
4792
4793 /**
4794 * @brief Count the elements of a sequence for which a predicate is true.
5b9daa7e 4795 * @ingroup non_mutating_algorithms
93c66bc6
BK
4796 * @param __first An input iterator.
4797 * @param __last An input iterator.
4798 * @param __pred A predicate.
4799 * @return The number of iterators @c i in the range @p [__first,__last)
4800 * for which @p __pred(*i) is true.
c2ba9709
JS
4801 */
4802 template<typename _InputIterator, typename _Predicate>
4803 typename iterator_traits<_InputIterator>::difference_type
4804 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4805 {
4806 // concept requirements
4807 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4808 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4809 typename iterator_traits<_InputIterator>::value_type>)
4810 __glibcxx_requires_valid_range(__first, __last);
4811 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4812 for (; __first != __last; ++__first)
4813 if (__pred(*__first))
4814 ++__n;
4815 return __n;
4816 }
4817
4818 /**
4819 * @brief Search a sequence for a matching sub-sequence.
5b9daa7e 4820 * @ingroup non_mutating_algorithms
93c66bc6
BK
4821 * @param __first1 A forward iterator.
4822 * @param __last1 A forward iterator.
4823 * @param __first2 A forward iterator.
4824 * @param __last2 A forward iterator.
4825 * @return The first iterator @c i in the range @p
4826 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4827 * *(__first2+N) for each @c N in the range @p
4828 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
c2ba9709 4829 *
93c66bc6
BK
4830 * Searches the range @p [__first1,__last1) for a sub-sequence that
4831 * compares equal value-by-value with the sequence given by @p
4832 * [__first2,__last2) and returns an iterator to the first element
4833 * of the sub-sequence, or @p __last1 if the sub-sequence is not
4834 * found.
4835 *
4836 * Because the sub-sequence must lie completely within the range @p
4837 * [__first1,__last1) it must start at a position less than @p
4838 * __last1-(__last2-__first2) where @p __last2-__first2 is the
4839 * length of the sub-sequence.
c2ba9709 4840 *
c2ba9709 4841 * This means that the returned iterator @c i will be in the range
93c66bc6 4842 * @p [__first1,__last1-(__last2-__first2))
c2ba9709
JS
4843 */
4844 template<typename _ForwardIterator1, typename _ForwardIterator2>
4845 _ForwardIterator1
4846 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4847 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4848 {
4849 // concept requirements
4850 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4851 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4852 __glibcxx_function_requires(_EqualOpConcept<
4853 typename iterator_traits<_ForwardIterator1>::value_type,
4854 typename iterator_traits<_ForwardIterator2>::value_type>)
4855 __glibcxx_requires_valid_range(__first1, __last1);
4856 __glibcxx_requires_valid_range(__first2, __last2);
4857
4858 // Test for empty ranges
4859 if (__first1 == __last1 || __first2 == __last2)
4860 return __first1;
4861
4862 // Test for a pattern of length 1.
4863 _ForwardIterator2 __p1(__first2);
4864 if (++__p1 == __last2)
12ffa228 4865 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
c2ba9709
JS
4866
4867 // General case.
4868 _ForwardIterator2 __p;
4869 _ForwardIterator1 __current = __first1;
4870
4871 for (;;)
4872 {
12ffa228 4873 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
c2ba9709
JS
4874 if (__first1 == __last1)
4875 return __last1;
4876
4877 __p = __p1;
4878 __current = __first1;
4879 if (++__current == __last1)
4880 return __last1;
4881
4882 while (*__current == *__p)
4883 {
4884 if (++__p == __last2)
4885 return __first1;
4886 if (++__current == __last1)
4887 return __last1;
4888 }
4889 ++__first1;
4890 }
4891 return __first1;
4892 }
4893
4894 /**
4895 * @brief Search a sequence for a matching sub-sequence using a predicate.
5b9daa7e 4896 * @ingroup non_mutating_algorithms
93c66bc6
BK
4897 * @param __first1 A forward iterator.
4898 * @param __last1 A forward iterator.
4899 * @param __first2 A forward iterator.
4900 * @param __last2 A forward iterator.
4901 * @param __predicate A binary predicate.
c2ba9709 4902 * @return The first iterator @c i in the range
93c66bc6
BK
4903 * @p [__first1,__last1-(__last2-__first2)) such that
4904 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4905 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
c2ba9709 4906 *
93c66bc6
BK
4907 * Searches the range @p [__first1,__last1) for a sub-sequence that
4908 * compares equal value-by-value with the sequence given by @p
4909 * [__first2,__last2), using @p __predicate to determine equality,
4910 * and returns an iterator to the first element of the
4911 * sub-sequence, or @p __last1 if no such iterator exists.
c2ba9709
JS
4912 *
4913 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4914 */
4915 template<typename _ForwardIterator1, typename _ForwardIterator2,
4916 typename _BinaryPredicate>
4917 _ForwardIterator1
4918 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4919 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4920 _BinaryPredicate __predicate)
4921 {
4922 // concept requirements
4923 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4924 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4925 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4926 typename iterator_traits<_ForwardIterator1>::value_type,
4927 typename iterator_traits<_ForwardIterator2>::value_type>)
4928 __glibcxx_requires_valid_range(__first1, __last1);
4929 __glibcxx_requires_valid_range(__first2, __last2);
4930
4931 // Test for empty ranges
4932 if (__first1 == __last1 || __first2 == __last2)
4933 return __first1;
4934
4935 // Test for a pattern of length 1.
4936 _ForwardIterator2 __p1(__first2);
4937 if (++__p1 == __last2)
4938 {
4939 while (__first1 != __last1
4940 && !bool(__predicate(*__first1, *__first2)))
4941 ++__first1;
4942 return __first1;
4943 }
4944
4945 // General case.
4946 _ForwardIterator2 __p;
4947 _ForwardIterator1 __current = __first1;
4948
4949 for (;;)
4950 {
4951 while (__first1 != __last1
4952 && !bool(__predicate(*__first1, *__first2)))
4953 ++__first1;
4954 if (__first1 == __last1)
4955 return __last1;
4956
4957 __p = __p1;
4958 __current = __first1;
4959 if (++__current == __last1)
4960 return __last1;
4961
4962 while (__predicate(*__current, *__p))
4963 {
4964 if (++__p == __last2)
4965 return __first1;
4966 if (++__current == __last1)
4967 return __last1;
4968 }
4969 ++__first1;
4970 }
4971 return __first1;
4972 }
4973
4974
4975 /**
4976 * @brief Search a sequence for a number of consecutive values.
5b9daa7e 4977 * @ingroup non_mutating_algorithms
93c66bc6
BK
4978 * @param __first A forward iterator.
4979 * @param __last A forward iterator.
4980 * @param __count The number of consecutive values.
4981 * @param __val The value to find.
4982 * @return The first iterator @c i in the range @p
4983 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4984 * each @c N in the range @p [0,__count), or @p __last if no such
4985 * iterator exists.
c2ba9709 4986 *
93c66bc6
BK
4987 * Searches the range @p [__first,__last) for @p count consecutive elements
4988 * equal to @p __val.
c2ba9709
JS
4989 */
4990 template<typename _ForwardIterator, typename _Integer, typename _Tp>
4991 _ForwardIterator
4992 search_n(_ForwardIterator __first, _ForwardIterator __last,
4993 _Integer __count, const _Tp& __val)
4994 {
4995 // concept requirements
4996 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4997 __glibcxx_function_requires(_EqualOpConcept<
4998 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4999 __glibcxx_requires_valid_range(__first, __last);
5000
5001 if (__count <= 0)
5002 return __first;
5003 if (__count == 1)
12ffa228 5004 return _GLIBCXX_STD_A::find(__first, __last, __val);
c2ba9709
JS
5005 return std::__search_n(__first, __last, __count, __val,
5006 std::__iterator_category(__first));
5007 }
5008
5009
5010 /**
5011 * @brief Search a sequence for a number of consecutive values using a
5012 * predicate.
5b9daa7e 5013 * @ingroup non_mutating_algorithms
93c66bc6
BK
5014 * @param __first A forward iterator.
5015 * @param __last A forward iterator.
5016 * @param __count The number of consecutive values.
5017 * @param __val The value to find.
5018 * @param __binary_pred A binary predicate.
5019 * @return The first iterator @c i in the range @p
5020 * [__first,__last-__count) such that @p
5021 * __binary_pred(*(i+N),__val) is true for each @c N in the range
5022 * @p [0,__count), or @p __last if no such iterator exists.
c2ba9709 5023 *
93c66bc6
BK
5024 * Searches the range @p [__first,__last) for @p __count
5025 * consecutive elements for which the predicate returns true.
c2ba9709
JS
5026 */
5027 template<typename _ForwardIterator, typename _Integer, typename _Tp,
5028 typename _BinaryPredicate>
5029 _ForwardIterator
5030 search_n(_ForwardIterator __first, _ForwardIterator __last,
5031 _Integer __count, const _Tp& __val,
5032 _BinaryPredicate __binary_pred)
5033 {
5034 // concept requirements
5035 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5036 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
5037 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
5038 __glibcxx_requires_valid_range(__first, __last);
5039
5040 if (__count <= 0)
5041 return __first;
5042 if (__count == 1)
5043 {
5044 while (__first != __last && !bool(__binary_pred(*__first, __val)))
5045 ++__first;
5046 return __first;
5047 }
5048 return std::__search_n(__first, __last, __count, __val, __binary_pred,
5049 std::__iterator_category(__first));
5050 }
5051
5052
5053 /**
5054 * @brief Perform an operation on a sequence.
5b9daa7e 5055 * @ingroup mutating_algorithms
93c66bc6
BK
5056 * @param __first An input iterator.
5057 * @param __last An input iterator.
5058 * @param __result An output iterator.
5059 * @param __unary_op A unary operator.
5060 * @return An output iterator equal to @p __result+(__last-__first).
c2ba9709
JS
5061 *
5062 * Applies the operator to each element in the input range and assigns
5063 * the results to successive elements of the output sequence.
93c66bc6
BK
5064 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
5065 * range @p [0,__last-__first).
c2ba9709
JS
5066 *
5067 * @p unary_op must not alter its argument.
5068 */
5069 template<typename _InputIterator, typename _OutputIterator,
5070 typename _UnaryOperation>
5071 _OutputIterator
5072 transform(_InputIterator __first, _InputIterator __last,
5073 _OutputIterator __result, _UnaryOperation __unary_op)
5074 {
5075 // concept requirements
5076 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5077 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5078 // "the type returned by a _UnaryOperation"
5079 __typeof__(__unary_op(*__first))>)
5080 __glibcxx_requires_valid_range(__first, __last);
5081
5082 for (; __first != __last; ++__first, ++__result)
5083 *__result = __unary_op(*__first);
5084 return __result;
5085 }
5086
5087 /**
5088 * @brief Perform an operation on corresponding elements of two sequences.
5b9daa7e 5089 * @ingroup mutating_algorithms
93c66bc6
BK
5090 * @param __first1 An input iterator.
5091 * @param __last1 An input iterator.
5092 * @param __first2 An input iterator.
5093 * @param __result An output iterator.
5094 * @param __binary_op A binary operator.
c2ba9709
JS
5095 * @return An output iterator equal to @p result+(last-first).
5096 *
5097 * Applies the operator to the corresponding elements in the two
5098 * input ranges and assigns the results to successive elements of the
5099 * output sequence.
93c66bc6
BK
5100 * Evaluates @p
5101 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
5102 * @c N in the range @p [0,__last1-__first1).
c2ba9709
JS
5103 *
5104 * @p binary_op must not alter either of its arguments.
5105 */
5106 template<typename _InputIterator1, typename _InputIterator2,
5107 typename _OutputIterator, typename _BinaryOperation>
5108 _OutputIterator
5109 transform(_InputIterator1 __first1, _InputIterator1 __last1,
5110 _InputIterator2 __first2, _OutputIterator __result,
5111 _BinaryOperation __binary_op)
5112 {
5113 // concept requirements
5114 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5115 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5116 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5117 // "the type returned by a _BinaryOperation"
5118 __typeof__(__binary_op(*__first1,*__first2))>)
5119 __glibcxx_requires_valid_range(__first1, __last1);
5120
5121 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
5122 *__result = __binary_op(*__first1, *__first2);
5123 return __result;
5124 }
5125
5126 /**
5127 * @brief Replace each occurrence of one value in a sequence with another
5128 * value.
5b9daa7e 5129 * @ingroup mutating_algorithms
93c66bc6
BK
5130 * @param __first A forward iterator.
5131 * @param __last A forward iterator.
5132 * @param __old_value The value to be replaced.
5133 * @param __new_value The replacement value.
c2ba9709
JS
5134 * @return replace() returns no value.
5135 *
93c66bc6
BK
5136 * For each iterator @c i in the range @p [__first,__last) if @c *i ==
5137 * @p __old_value then the assignment @c *i = @p __new_value is performed.
c2ba9709
JS
5138 */
5139 template<typename _ForwardIterator, typename _Tp>
5140 void
5141 replace(_ForwardIterator __first, _ForwardIterator __last,
5142 const _Tp& __old_value, const _Tp& __new_value)
5143 {
5144 // concept requirements
5145 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5146 _ForwardIterator>)
5147 __glibcxx_function_requires(_EqualOpConcept<
5148 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
5149 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5150 typename iterator_traits<_ForwardIterator>::value_type>)
5151 __glibcxx_requires_valid_range(__first, __last);
5152
5153 for (; __first != __last; ++__first)
5154 if (*__first == __old_value)
5155 *__first = __new_value;
5156 }
5157
5158 /**
5159 * @brief Replace each value in a sequence for which a predicate returns
5160 * true with another value.
5b9daa7e 5161 * @ingroup mutating_algorithms
93c66bc6
BK
5162 * @param __first A forward iterator.
5163 * @param __last A forward iterator.
5164 * @param __pred A predicate.
5165 * @param __new_value The replacement value.
c2ba9709
JS
5166 * @return replace_if() returns no value.
5167 *
93c66bc6
BK
5168 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
5169 * is true then the assignment @c *i = @p __new_value is performed.
c2ba9709
JS
5170 */
5171 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
5172 void
5173 replace_if(_ForwardIterator __first, _ForwardIterator __last,
5174 _Predicate __pred, const _Tp& __new_value)
5175 {
5176 // concept requirements
5177 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5178 _ForwardIterator>)
5179 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5180 typename iterator_traits<_ForwardIterator>::value_type>)
5181 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5182 typename iterator_traits<_ForwardIterator>::value_type>)
5183 __glibcxx_requires_valid_range(__first, __last);
5184
5185 for (; __first != __last; ++__first)
5186 if (__pred(*__first))
5187 *__first = __new_value;
5188 }
5189
5190 /**
5191 * @brief Assign the result of a function object to each value in a
5192 * sequence.
5b9daa7e 5193 * @ingroup mutating_algorithms
93c66bc6
BK
5194 * @param __first A forward iterator.
5195 * @param __last A forward iterator.
5196 * @param __gen A function object taking no arguments and returning
4f99f3d0 5197 * std::iterator_traits<_ForwardIterator>::value_type
c2ba9709
JS
5198 * @return generate() returns no value.
5199 *
93c66bc6
BK
5200 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5201 * @p [__first,__last).
c2ba9709
JS
5202 */
5203 template<typename _ForwardIterator, typename _Generator>
5204 void
5205 generate(_ForwardIterator __first, _ForwardIterator __last,
5206 _Generator __gen)
5207 {
5208 // concept requirements
5209 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5210 __glibcxx_function_requires(_GeneratorConcept<_Generator,
5211 typename iterator_traits<_ForwardIterator>::value_type>)
5212 __glibcxx_requires_valid_range(__first, __last);
5213
5214 for (; __first != __last; ++__first)
5215 *__first = __gen();
5216 }
5217
5218 /**
5219 * @brief Assign the result of a function object to each value in a
5220 * sequence.
5b9daa7e 5221 * @ingroup mutating_algorithms
93c66bc6
BK
5222 * @param __first A forward iterator.
5223 * @param __n The length of the sequence.
5224 * @param __gen A function object taking no arguments and returning
4f99f3d0 5225 * std::iterator_traits<_ForwardIterator>::value_type
93c66bc6 5226 * @return The end of the sequence, @p __first+__n
c2ba9709 5227 *
93c66bc6
BK
5228 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5229 * @p [__first,__first+__n).
82ab4b64
PC
5230 *
5231 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5232 * DR 865. More algorithms that throw away information
c2ba9709
JS
5233 */
5234 template<typename _OutputIterator, typename _Size, typename _Generator>
5235 _OutputIterator
5236 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5237 {
5238 // concept requirements
5239 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5240 // "the type returned by a _Generator"
5241 __typeof__(__gen())>)
5242
759149fb
PC
5243 for (__decltype(__n + 0) __niter = __n;
5244 __niter > 0; --__niter, ++__first)
c2ba9709
JS
5245 *__first = __gen();
5246 return __first;
5247 }
5248
5249
5250 /**
5251 * @brief Copy a sequence, removing consecutive duplicate values.
5b9daa7e 5252 * @ingroup mutating_algorithms
93c66bc6
BK
5253 * @param __first An input iterator.
5254 * @param __last An input iterator.
5255 * @param __result An output iterator.
c2ba9709
JS
5256 * @return An iterator designating the end of the resulting sequence.
5257 *
93c66bc6
BK
5258 * Copies each element in the range @p [__first,__last) to the range
5259 * beginning at @p __result, except that only the first element is copied
c2ba9709
JS
5260 * from groups of consecutive elements that compare equal.
5261 * unique_copy() is stable, so the relative order of elements that are
5262 * copied is unchanged.
5263 *
c2ba9709
JS
5264 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5265 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5266 *
5267 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5268 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
5269 * Assignable?
c2ba9709
JS
5270 */
5271 template<typename _InputIterator, typename _OutputIterator>
5272 inline _OutputIterator
5273 unique_copy(_InputIterator __first, _InputIterator __last,
5274 _OutputIterator __result)
5275 {
5276 // concept requirements
5277 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5278 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5279 typename iterator_traits<_InputIterator>::value_type>)
5280 __glibcxx_function_requires(_EqualityComparableConcept<
5281 typename iterator_traits<_InputIterator>::value_type>)
5282 __glibcxx_requires_valid_range(__first, __last);
5283
5284 if (__first == __last)
5285 return __result;
5286 return std::__unique_copy(__first, __last, __result,
5287 std::__iterator_category(__first),
5288 std::__iterator_category(__result));
da5a2efd
PC
5289 }
5290
5291 /**
c2ba9709 5292 * @brief Copy a sequence, removing consecutive values using a predicate.
5b9daa7e 5293 * @ingroup mutating_algorithms
93c66bc6
BK
5294 * @param __first An input iterator.
5295 * @param __last An input iterator.
5296 * @param __result An output iterator.
5297 * @param __binary_pred A binary predicate.
c2ba9709 5298 * @return An iterator designating the end of the resulting sequence.
c868f37e 5299 *
93c66bc6
BK
5300 * Copies each element in the range @p [__first,__last) to the range
5301 * beginning at @p __result, except that only the first element is copied
5302 * from groups of consecutive elements for which @p __binary_pred returns
c2ba9709
JS
5303 * true.
5304 * unique_copy() is stable, so the relative order of elements that are
5305 * copied is unchanged.
da5a2efd 5306 *
c2ba9709
JS
5307 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5308 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
bf551f96 5309 */
c2ba9709
JS
5310 template<typename _InputIterator, typename _OutputIterator,
5311 typename _BinaryPredicate>
5312 inline _OutputIterator
5313 unique_copy(_InputIterator __first, _InputIterator __last,
5314 _OutputIterator __result,
5315 _BinaryPredicate __binary_pred)
02d92e3b 5316 {
c2ba9709
JS
5317 // concept requirements -- predicates checked later
5318 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5319 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5320 typename iterator_traits<_InputIterator>::value_type>)
5321 __glibcxx_requires_valid_range(__first, __last);
da5a2efd 5322
c2ba9709
JS
5323 if (__first == __last)
5324 return __result;
5325 return std::__unique_copy(__first, __last, __result, __binary_pred,
5326 std::__iterator_category(__first),
5327 std::__iterator_category(__result));
5328 }
da5a2efd 5329
da5a2efd 5330
c2ba9709
JS
5331 /**
5332 * @brief Randomly shuffle the elements of a sequence.
5b9daa7e 5333 * @ingroup mutating_algorithms
93c66bc6
BK
5334 * @param __first A forward iterator.
5335 * @param __last A forward iterator.
c2ba9709
JS
5336 * @return Nothing.
5337 *
93c66bc6 5338 * Reorder the elements in the range @p [__first,__last) using a random
c2ba9709
JS
5339 * distribution, so that every possible ordering of the sequence is
5340 * equally likely.
5341 */
5342 template<typename _RandomAccessIterator>
5343 inline void
5344 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5345 {
5346 // concept requirements
5347 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5348 _RandomAccessIterator>)
5349 __glibcxx_requires_valid_range(__first, __last);
da5a2efd 5350
c2ba9709
JS
5351 if (__first != __last)
5352 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5353 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
da5a2efd
PC
5354 }
5355
5356 /**
c2ba9709
JS
5357 * @brief Shuffle the elements of a sequence using a random number
5358 * generator.
5b9daa7e 5359 * @ingroup mutating_algorithms
93c66bc6
BK
5360 * @param __first A forward iterator.
5361 * @param __last A forward iterator.
5362 * @param __rand The RNG functor or function.
da5a2efd
PC
5363 * @return Nothing.
5364 *
93c66bc6
BK
5365 * Reorders the elements in the range @p [__first,__last) using @p __rand to
5366 * provide a random distribution. Calling @p __rand(N) for a positive
c2ba9709
JS
5367 * integer @p N should return a randomly chosen integer from the
5368 * range [0,N).
da5a2efd 5369 */
c2ba9709 5370 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
da5a2efd 5371 void
c2ba9709 5372 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
734f5023 5373#if __cplusplus >= 201103L
247d8075
PC
5374 _RandomNumberGenerator&& __rand)
5375#else
c2ba9709 5376 _RandomNumberGenerator& __rand)
247d8075 5377#endif
da5a2efd 5378 {
da5a2efd 5379 // concept requirements
c2ba9709
JS
5380 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5381 _RandomAccessIterator>)
5382 __glibcxx_requires_valid_range(__first, __last);
da5a2efd 5383
c2ba9709 5384 if (__first == __last)
da5a2efd 5385 return;
c2ba9709
JS
5386 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5387 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
da5a2efd
PC
5388 }
5389
da5a2efd 5390
c2ba9709
JS
5391 /**
5392 * @brief Move elements for which a predicate is true to the beginning
5393 * of a sequence.
5b9daa7e 5394 * @ingroup mutating_algorithms
93c66bc6
BK
5395 * @param __first A forward iterator.
5396 * @param __last A forward iterator.
5397 * @param __pred A predicate functor.
5398 * @return An iterator @p middle such that @p __pred(i) is true for each
5399 * iterator @p i in the range @p [__first,middle) and false for each @p i
5400 * in the range @p [middle,__last).
c2ba9709 5401 *
93c66bc6 5402 * @p __pred must not modify its operand. @p partition() does not preserve
c2ba9709
JS
5403 * the relative ordering of elements in each group, use
5404 * @p stable_partition() if this is needed.
5405 */
5406 template<typename _ForwardIterator, typename _Predicate>
5407 inline _ForwardIterator
5408 partition(_ForwardIterator __first, _ForwardIterator __last,
5409 _Predicate __pred)
5410 {
5411 // concept requirements
5412 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5413 _ForwardIterator>)
5414 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5415 typename iterator_traits<_ForwardIterator>::value_type>)
5416 __glibcxx_requires_valid_range(__first, __last);
da5a2efd 5417
c2ba9709
JS
5418 return std::__partition(__first, __last, __pred,
5419 std::__iterator_category(__first));
da5a2efd
PC
5420 }
5421
c2ba9709
JS
5422
5423
5424 /**
5425 * @brief Sort the smallest elements of a sequence.
5b9daa7e 5426 * @ingroup sorting_algorithms
93c66bc6
BK
5427 * @param __first An iterator.
5428 * @param __middle Another iterator.
5429 * @param __last Another iterator.
c2ba9709
JS
5430 * @return Nothing.
5431 *
93c66bc6
BK
5432 * Sorts the smallest @p (__middle-__first) elements in the range
5433 * @p [first,last) and moves them to the range @p [__first,__middle). The
5434 * order of the remaining elements in the range @p [__middle,__last) is
c2ba9709 5435 * undefined.
7897a1c0
BK
5436 * After the sort if @e i and @e j are iterators in the range
5437 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5438 * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
c2ba9709
JS
5439 */
5440 template<typename _RandomAccessIterator>
5441 inline void
5442 partial_sort(_RandomAccessIterator __first,
5443 _RandomAccessIterator __middle,
5444 _RandomAccessIterator __last)
da5a2efd 5445 {
c2ba9709
JS
5446 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5447 _ValueType;
da5a2efd 5448
c2ba9709
JS
5449 // concept requirements
5450 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5451 _RandomAccessIterator>)
5452 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5453 __glibcxx_requires_valid_range(__first, __middle);
5454 __glibcxx_requires_valid_range(__middle, __last);
da5a2efd 5455
c2ba9709
JS
5456 std::__heap_select(__first, __middle, __last);
5457 std::sort_heap(__first, __middle);
da5a2efd
PC
5458 }
5459
c2ba9709
JS
5460 /**
5461 * @brief Sort the smallest elements of a sequence using a predicate
5462 * for comparison.
5b9daa7e 5463 * @ingroup sorting_algorithms
93c66bc6
BK
5464 * @param __first An iterator.
5465 * @param __middle Another iterator.
5466 * @param __last Another iterator.
5467 * @param __comp A comparison functor.
c2ba9709
JS
5468 * @return Nothing.
5469 *
93c66bc6
BK
5470 * Sorts the smallest @p (__middle-__first) elements in the range
5471 * @p [__first,__last) and moves them to the range @p [__first,__middle). The
5472 * order of the remaining elements in the range @p [__middle,__last) is
c2ba9709 5473 * undefined.
7897a1c0
BK
5474 * After the sort if @e i and @e j are iterators in the range
5475 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
93c66bc6 5476 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
c2ba9709
JS
5477 * are both false.
5478 */
5479 template<typename _RandomAccessIterator, typename _Compare>
5480 inline void
5481 partial_sort(_RandomAccessIterator __first,
5482 _RandomAccessIterator __middle,
5483 _RandomAccessIterator __last,
5484 _Compare __comp)
da5a2efd 5485 {
c2ba9709
JS
5486 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5487 _ValueType;
da5a2efd 5488
c2ba9709
JS
5489 // concept requirements
5490 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5491 _RandomAccessIterator>)
5492 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5493 _ValueType, _ValueType>)
5494 __glibcxx_requires_valid_range(__first, __middle);
5495 __glibcxx_requires_valid_range(__middle, __last);
da5a2efd 5496
c2ba9709
JS
5497 std::__heap_select(__first, __middle, __last, __comp);
5498 std::sort_heap(__first, __middle, __comp);
5499 }
da5a2efd 5500
c2ba9709
JS
5501 /**
5502 * @brief Sort a sequence just enough to find a particular position.
5b9daa7e 5503 * @ingroup sorting_algorithms
93c66bc6
BK
5504 * @param __first An iterator.
5505 * @param __nth Another iterator.
5506 * @param __last Another iterator.
c2ba9709
JS
5507 * @return Nothing.
5508 *
93c66bc6 5509 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
c2ba9709 5510 * is the same element that would have been in that position had the
93c66bc6 5511 * whole sequence been sorted. The elements either side of @p *__nth are
7897a1c0
BK
5512 * not completely sorted, but for any iterator @e i in the range
5513 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5514 * holds that *j < *i is false.
c2ba9709
JS
5515 */
5516 template<typename _RandomAccessIterator>
5517 inline void
5518 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5519 _RandomAccessIterator __last)
da5a2efd 5520 {
c2ba9709
JS
5521 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5522 _ValueType;
02d92e3b 5523
c2ba9709
JS
5524 // concept requirements
5525 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5526 _RandomAccessIterator>)
5527 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5528 __glibcxx_requires_valid_range(__first, __nth);
5529 __glibcxx_requires_valid_range(__nth, __last);
c868f37e 5530
c2ba9709
JS
5531 if (__first == __last || __nth == __last)
5532 return;
8c093661 5533
c2ba9709
JS
5534 std::__introselect(__first, __nth, __last,
5535 std::__lg(__last - __first) * 2);
02d92e3b 5536 }
725dc051 5537
c2ba9709
JS
5538 /**
5539 * @brief Sort a sequence just enough to find a particular position
5540 * using a predicate for comparison.
5b9daa7e 5541 * @ingroup sorting_algorithms
93c66bc6
BK
5542 * @param __first An iterator.
5543 * @param __nth Another iterator.
5544 * @param __last Another iterator.
5545 * @param __comp A comparison functor.
c2ba9709
JS
5546 * @return Nothing.
5547 *
93c66bc6 5548 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
c2ba9709 5549 * is the same element that would have been in that position had the
93c66bc6 5550 * whole sequence been sorted. The elements either side of @p *__nth are
7897a1c0
BK
5551 * not completely sorted, but for any iterator @e i in the range
5552 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
93c66bc6 5553 * holds that @p __comp(*j,*i) is false.
c2ba9709
JS
5554 */
5555 template<typename _RandomAccessIterator, typename _Compare>
5556 inline void
5557 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5558 _RandomAccessIterator __last, _Compare __comp)
02d92e3b 5559 {
c2ba9709
JS
5560 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5561 _ValueType;
c868f37e 5562
c2ba9709
JS
5563 // concept requirements
5564 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5565 _RandomAccessIterator>)
5566 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5567 _ValueType, _ValueType>)
5568 __glibcxx_requires_valid_range(__first, __nth);
5569 __glibcxx_requires_valid_range(__nth, __last);
c868f37e 5570
c2ba9709
JS
5571 if (__first == __last || __nth == __last)
5572 return;
c868f37e 5573
c2ba9709
JS
5574 std::__introselect(__first, __nth, __last,
5575 std::__lg(__last - __first) * 2, __comp);
725dc051 5576 }
02d92e3b 5577
c2ba9709
JS
5578
5579 /**
5580 * @brief Sort the elements of a sequence.
5b9daa7e 5581 * @ingroup sorting_algorithms
93c66bc6
BK
5582 * @param __first An iterator.
5583 * @param __last Another iterator.
c2ba9709
JS
5584 * @return Nothing.
5585 *
93c66bc6 5586 * Sorts the elements in the range @p [__first,__last) in ascending order,
7897a1c0
BK
5587 * such that for each iterator @e i in the range @p [__first,__last-1),
5588 * *(i+1)<*i is false.
c2ba9709
JS
5589 *
5590 * The relative ordering of equivalent elements is not preserved, use
5591 * @p stable_sort() if this is needed.
5592 */
5593 template<typename _RandomAccessIterator>
5594 inline void
5595 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
02d92e3b 5596 {
c2ba9709
JS
5597 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5598 _ValueType;
5599
5600 // concept requirements
5601 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5602 _RandomAccessIterator>)
5603 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5604 __glibcxx_requires_valid_range(__first, __last);
5605
5606 if (__first != __last)
da5a2efd 5607 {
c2ba9709
JS
5608 std::__introsort_loop(__first, __last,
5609 std::__lg(__last - __first) * 2);
5610 std::__final_insertion_sort(__first, __last);
da5a2efd 5611 }
da5a2efd 5612 }
c868f37e 5613
c2ba9709
JS
5614 /**
5615 * @brief Sort the elements of a sequence using a predicate for comparison.
5b9daa7e 5616 * @ingroup sorting_algorithms
93c66bc6
BK
5617 * @param __first An iterator.
5618 * @param __last Another iterator.
5619 * @param __comp A comparison functor.
c2ba9709
JS
5620 * @return Nothing.
5621 *
93c66bc6 5622 * Sorts the elements in the range @p [__first,__last) in ascending order,
7897a1c0 5623 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
93c66bc6 5624 * range @p [__first,__last-1).
c2ba9709
JS
5625 *
5626 * The relative ordering of equivalent elements is not preserved, use
5627 * @p stable_sort() if this is needed.
5628 */
5629 template<typename _RandomAccessIterator, typename _Compare>
5630 inline void
5631 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5632 _Compare __comp)
da5a2efd 5633 {
c2ba9709
JS
5634 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5635 _ValueType;
5636
5637 // concept requirements
5638 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5639 _RandomAccessIterator>)
5640 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5641 _ValueType>)
5642 __glibcxx_requires_valid_range(__first, __last);
5643
5644 if (__first != __last)
da5a2efd 5645 {
c2ba9709
JS
5646 std::__introsort_loop(__first, __last,
5647 std::__lg(__last - __first) * 2, __comp);
5648 std::__final_insertion_sort(__first, __last, __comp);
da5a2efd 5649 }
da5a2efd 5650 }
c868f37e 5651
da5a2efd 5652 /**
c2ba9709 5653 * @brief Merges two sorted ranges.
5b9daa7e 5654 * @ingroup sorting_algorithms
93c66bc6
BK
5655 * @param __first1 An iterator.
5656 * @param __first2 Another iterator.
5657 * @param __last1 Another iterator.
5658 * @param __last2 Another iterator.
5659 * @param __result An iterator pointing to the end of the merged range.
2a60a9f6 5660 * @return An iterator pointing to the first element <em>not less
7897a1c0 5661 * than</em> @e val.
c2ba9709 5662 *
7897a1c0
BK
5663 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5664 * the sorted range @p [__result, __result + (__last1-__first1) +
93c66bc6
BK
5665 * (__last2-__first2)). Both input ranges must be sorted, and the
5666 * output range must not overlap with either of the input ranges.
5667 * The sort is @e stable, that is, for equivalent elements in the
5668 * two ranges, elements from the first range will always come
5669 * before elements from the second.
da5a2efd 5670 */
c2ba9709
JS
5671 template<typename _InputIterator1, typename _InputIterator2,
5672 typename _OutputIterator>
5673 _OutputIterator
5674 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5675 _InputIterator2 __first2, _InputIterator2 __last2,
5676 _OutputIterator __result)
da5a2efd 5677 {
c2ba9709
JS
5678 typedef typename iterator_traits<_InputIterator1>::value_type
5679 _ValueType1;
5680 typedef typename iterator_traits<_InputIterator2>::value_type
5681 _ValueType2;
5682
5683 // concept requirements
5684 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5685 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5686 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5687 _ValueType1>)
5688 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5689 _ValueType2>)
5690 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
a4c07f2d
PC
5691 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5692 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
c2ba9709
JS
5693
5694 while (__first1 != __last1 && __first2 != __last2)
da5a2efd 5695 {
c2ba9709
JS
5696 if (*__first2 < *__first1)
5697 {
5698 *__result = *__first2;
5699 ++__first2;
5700 }
5701 else
5702 {
5703 *__result = *__first1;
5704 ++__first1;
5705 }
5706 ++__result;
da5a2efd 5707 }
c2ba9709
JS
5708 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5709 __result));
da5a2efd 5710 }
c868f37e 5711
da5a2efd 5712 /**
c2ba9709 5713 * @brief Merges two sorted ranges.
5b9daa7e 5714 * @ingroup sorting_algorithms
93c66bc6
BK
5715 * @param __first1 An iterator.
5716 * @param __first2 Another iterator.
5717 * @param __last1 Another iterator.
5718 * @param __last2 Another iterator.
5719 * @param __result An iterator pointing to the end of the merged range.
5720 * @param __comp A functor to use for comparisons.
c2ba9709 5721 * @return An iterator pointing to the first element "not less
7897a1c0 5722 * than" @e val.
c2ba9709 5723 *
7897a1c0
BK
5724 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5725 * the sorted range @p [__result, __result + (__last1-__first1) +
93c66bc6
BK
5726 * (__last2-__first2)). Both input ranges must be sorted, and the
5727 * output range must not overlap with either of the input ranges.
5728 * The sort is @e stable, that is, for equivalent elements in the
5729 * two ranges, elements from the first range will always come
5730 * before elements from the second.
c2ba9709
JS
5731 *
5732 * The comparison function should have the same effects on ordering as
5733 * the function used for the initial sort.
da5a2efd 5734 */
c2ba9709
JS
5735 template<typename _InputIterator1, typename _InputIterator2,
5736 typename _OutputIterator, typename _Compare>
5737 _OutputIterator
5738 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5739 _InputIterator2 __first2, _InputIterator2 __last2,
5740 _OutputIterator __result, _Compare __comp)
da5a2efd 5741 {
c2ba9709
JS
5742 typedef typename iterator_traits<_InputIterator1>::value_type
5743 _ValueType1;
5744 typedef typename iterator_traits<_InputIterator2>::value_type
5745 _ValueType2;
5746
5747 // concept requirements
5748 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5749 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5750 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5751 _ValueType1>)
5752 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5753 _ValueType2>)
5754 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5755 _ValueType2, _ValueType1>)
a4c07f2d
PC
5756 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5757 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
c2ba9709
JS
5758
5759 while (__first1 != __last1 && __first2 != __last2)
ffa67767 5760 {
c2ba9709
JS
5761 if (__comp(*__first2, *__first1))
5762 {
5763 *__result = *__first2;
5764 ++__first2;
5765 }
5766 else
5767 {
5768 *__result = *__first1;
5769 ++__first1;
5770 }
5771 ++__result;
02d92e3b 5772 }
c2ba9709
JS
5773 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5774 __result));
725dc051 5775 }
725dc051 5776
c2ba9709 5777
bf551f96 5778 /**
da5a2efd
PC
5779 * @brief Sort the elements of a sequence, preserving the relative order
5780 * of equivalent elements.
5b9daa7e 5781 * @ingroup sorting_algorithms
93c66bc6
BK
5782 * @param __first An iterator.
5783 * @param __last Another iterator.
da5a2efd 5784 * @return Nothing.
bf551f96 5785 *
93c66bc6 5786 * Sorts the elements in the range @p [__first,__last) in ascending order,
7897a1c0
BK
5787 * such that for each iterator @p i in the range @p [__first,__last-1),
5788 * @p *(i+1)<*i is false.
da5a2efd
PC
5789 *
5790 * The relative ordering of equivalent elements is preserved, so any two
93c66bc6 5791 * elements @p x and @p y in the range @p [__first,__last) such that
da5a2efd
PC
5792 * @p x<y is false and @p y<x is false will have the same relative
5793 * ordering after calling @p stable_sort().
bf551f96 5794 */
da5a2efd
PC
5795 template<typename _RandomAccessIterator>
5796 inline void
5797 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
02d92e3b 5798 {
da5a2efd 5799 typedef typename iterator_traits<_RandomAccessIterator>::value_type
e75ea710 5800 _ValueType;
da5a2efd
PC
5801 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5802 _DistanceType;
e75ea710 5803
02d92e3b 5804 // concept requirements
da5a2efd
PC
5805 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5806 _RandomAccessIterator>)
5807 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5808 __glibcxx_requires_valid_range(__first, __last);
c0d88161 5809
da5a2efd
PC
5810 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5811 __last);
5812 if (__buf.begin() == 0)
5813 std::__inplace_stable_sort(__first, __last);
5814 else
5815 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5816 _DistanceType(__buf.size()));
02d92e3b
SW
5817 }
5818
bf551f96 5819 /**
da5a2efd
PC
5820 * @brief Sort the elements of a sequence using a predicate for comparison,
5821 * preserving the relative order of equivalent elements.
5b9daa7e 5822 * @ingroup sorting_algorithms
93c66bc6
BK
5823 * @param __first An iterator.
5824 * @param __last Another iterator.
5825 * @param __comp A comparison functor.
da5a2efd 5826 * @return Nothing.
bf551f96 5827 *
93c66bc6 5828 * Sorts the elements in the range @p [__first,__last) in ascending order,
7897a1c0
BK
5829 * such that for each iterator @p i in the range @p [__first,__last-1),
5830 * @p __comp(*(i+1),*i) is false.
bf551f96 5831 *
da5a2efd 5832 * The relative ordering of equivalent elements is preserved, so any two
93c66bc6
BK
5833 * elements @p x and @p y in the range @p [__first,__last) such that
5834 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
da5a2efd 5835 * relative ordering after calling @p stable_sort().
bf551f96 5836 */
da5a2efd
PC
5837 template<typename _RandomAccessIterator, typename _Compare>
5838 inline void
5839 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5840 _Compare __comp)
02d92e3b 5841 {
da5a2efd 5842 typedef typename iterator_traits<_RandomAccessIterator>::value_type
e75ea710 5843 _ValueType;
c2ba9709
JS
5844 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5845 _DistanceType;
e75ea710 5846
02d92e3b 5847 // concept requirements
c2ba9709
JS
5848 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5849 _RandomAccessIterator>)
e75ea710 5850 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
c2ba9709
JS
5851 _ValueType,
5852 _ValueType>)
5853 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 5854
c2ba9709
JS
5855 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5856 __last);
5857 if (__buf.begin() == 0)
5858 std::__inplace_stable_sort(__first, __last, __comp);
5859 else
5860 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5861 _DistanceType(__buf.size()), __comp);
02d92e3b
SW
5862 }
5863
c2ba9709 5864
119dbb1f
JQ
5865 /**
5866 * @brief Return the union of two sorted ranges.
5b9daa7e 5867 * @ingroup set_algorithms
93c66bc6
BK
5868 * @param __first1 Start of first range.
5869 * @param __last1 End of first range.
5870 * @param __first2 Start of second range.
5871 * @param __last2 End of second range.
119dbb1f 5872 * @return End of the output range.
aac2878e 5873 * @ingroup set_algorithms
119dbb1f
JQ
5874 *
5875 * This operation iterates over both ranges, copying elements present in
5876 * each range in order to the output range. Iterators increment for each
5877 * range. When the current element of one range is less than the other,
5878 * that element is copied and the iterator advanced. If an element is
5879 * contained in both ranges, the element from the first range is copied and
5880 * both ranges advance. The output range may not overlap either input
5881 * range.
5882 */
ffa67767
PC
5883 template<typename _InputIterator1, typename _InputIterator2,
5884 typename _OutputIterator>
08addde6
PE
5885 _OutputIterator
5886 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5887 _InputIterator2 __first2, _InputIterator2 __last2,
5888 _OutputIterator __result)
02d92e3b 5889 {
e75ea710
PC
5890 typedef typename iterator_traits<_InputIterator1>::value_type
5891 _ValueType1;
5892 typedef typename iterator_traits<_InputIterator2>::value_type
5893 _ValueType2;
5894
02d92e3b 5895 // concept requirements
3d7c150e
BK
5896 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5897 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5898 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710
PC
5899 _ValueType1>)
5900 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5901 _ValueType2>)
5902 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5903 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
a4c07f2d
PC
5904 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5905 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
02d92e3b 5906
ffa67767
PC
5907 while (__first1 != __last1 && __first2 != __last2)
5908 {
5909 if (*__first1 < *__first2)
5910 {
5911 *__result = *__first1;
5912 ++__first1;
5913 }
5914 else if (*__first2 < *__first1)
5915 {
5916 *__result = *__first2;
5917 ++__first2;
5918 }
5919 else
5920 {
5921 *__result = *__first1;
5922 ++__first1;
5923 ++__first2;
5924 }
5925 ++__result;
02d92e3b 5926 }
ffa67767
PC
5927 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5928 __result));
02d92e3b
SW
5929 }
5930
119dbb1f
JQ
5931 /**
5932 * @brief Return the union of two sorted ranges using a comparison functor.
5b9daa7e 5933 * @ingroup set_algorithms
93c66bc6
BK
5934 * @param __first1 Start of first range.
5935 * @param __last1 End of first range.
5936 * @param __first2 Start of second range.
5937 * @param __last2 End of second range.
5938 * @param __comp The comparison functor.
119dbb1f 5939 * @return End of the output range.
aac2878e 5940 * @ingroup set_algorithms
119dbb1f
JQ
5941 *
5942 * This operation iterates over both ranges, copying elements present in
5943 * each range in order to the output range. Iterators increment for each
5944 * range. When the current element of one range is less than the other
7897a1c0
BK
5945 * according to @p __comp, that element is copied and the iterator advanced.
5946 * If an equivalent element according to @p __comp is contained in both
119dbb1f
JQ
5947 * ranges, the element from the first range is copied and both ranges
5948 * advance. The output range may not overlap either input range.
5949 */
ffa67767
PC
5950 template<typename _InputIterator1, typename _InputIterator2,
5951 typename _OutputIterator, typename _Compare>
08addde6
PE
5952 _OutputIterator
5953 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5954 _InputIterator2 __first2, _InputIterator2 __last2,
5955 _OutputIterator __result, _Compare __comp)
02d92e3b 5956 {
e75ea710
PC
5957 typedef typename iterator_traits<_InputIterator1>::value_type
5958 _ValueType1;
5959 typedef typename iterator_traits<_InputIterator2>::value_type
5960 _ValueType2;
5961
02d92e3b 5962 // concept requirements
3d7c150e
BK
5963 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5964 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3d7c150e 5965 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710
PC
5966 _ValueType1>)
5967 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5968 _ValueType2>)
5969 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5970 _ValueType1, _ValueType2>)
3d7c150e 5971 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
e75ea710 5972 _ValueType2, _ValueType1>)
a4c07f2d
PC
5973 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5974 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
02d92e3b 5975
ffa67767
PC
5976 while (__first1 != __last1 && __first2 != __last2)
5977 {
5978 if (__comp(*__first1, *__first2))
5979 {
5980 *__result = *__first1;
5981 ++__first1;
5982 }
5983 else if (__comp(*__first2, *__first1))
5984 {
5985 *__result = *__first2;
5986 ++__first2;
5987 }
ed6814f7 5988 else
ffa67767
PC
5989 {
5990 *__result = *__first1;
5991 ++__first1;
5992 ++__first2;
5993 }
5994 ++__result;
02d92e3b 5995 }
ed6814f7 5996 return std::copy(__first2, __last2, std::copy(__first1, __last1,
ffa67767 5997 __result));
02d92e3b
SW
5998 }
5999
119dbb1f
JQ
6000 /**
6001 * @brief Return the intersection of two sorted ranges.
5b9daa7e 6002 * @ingroup set_algorithms
93c66bc6
BK
6003 * @param __first1 Start of first range.
6004 * @param __last1 End of first range.
6005 * @param __first2 Start of second range.
6006 * @param __last2 End of second range.
119dbb1f 6007 * @return End of the output range.
aac2878e 6008 * @ingroup set_algorithms
119dbb1f
JQ
6009 *
6010 * This operation iterates over both ranges, copying elements present in
6011 * both ranges in order to the output range. Iterators increment for each
6012 * range. When the current element of one range is less than the other,
6013 * that iterator advances. If an element is contained in both ranges, the
6014 * element from the first range is copied and both ranges advance. The
6015 * output range may not overlap either input range.
6016 */
ffa67767
PC
6017 template<typename _InputIterator1, typename _InputIterator2,
6018 typename _OutputIterator>
08addde6
PE
6019 _OutputIterator
6020 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
6021 _InputIterator2 __first2, _InputIterator2 __last2,
6022 _OutputIterator __result)
02d92e3b 6023 {
e75ea710
PC
6024 typedef typename iterator_traits<_InputIterator1>::value_type
6025 _ValueType1;
6026 typedef typename iterator_traits<_InputIterator2>::value_type
6027 _ValueType2;
6028
02d92e3b 6029 // concept requirements
3d7c150e
BK
6030 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6031 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6032 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710
PC
6033 _ValueType1>)
6034 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6035 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
a4c07f2d
PC
6036 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6037 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
02d92e3b 6038
c0d88161
JW
6039 while (__first1 != __last1 && __first2 != __last2)
6040 if (*__first1 < *__first2)
02d92e3b 6041 ++__first1;
c0d88161 6042 else if (*__first2 < *__first1)
02d92e3b 6043 ++__first2;
ffa67767
PC
6044 else
6045 {
6046 *__result = *__first1;
6047 ++__first1;
6048 ++__first2;
6049 ++__result;
6050 }
02d92e3b
SW
6051 return __result;
6052 }
6053
119dbb1f
JQ
6054 /**
6055 * @brief Return the intersection of two sorted ranges using comparison
ed6814f7 6056 * functor.
5b9daa7e 6057 * @ingroup set_algorithms
93c66bc6
BK
6058 * @param __first1 Start of first range.
6059 * @param __last1 End of first range.
6060 * @param __first2 Start of second range.
6061 * @param __last2 End of second range.
6062 * @param __comp The comparison functor.
119dbb1f 6063 * @return End of the output range.
aac2878e 6064 * @ingroup set_algorithms
119dbb1f
JQ
6065 *
6066 * This operation iterates over both ranges, copying elements present in
6067 * both ranges in order to the output range. Iterators increment for each
6068 * range. When the current element of one range is less than the other
7897a1c0
BK
6069 * according to @p __comp, that iterator advances. If an element is
6070 * contained in both ranges according to @p __comp, the element from the
119dbb1f
JQ
6071 * first range is copied and both ranges advance. The output range may not
6072 * overlap either input range.
6073 */
ffa67767
PC
6074 template<typename _InputIterator1, typename _InputIterator2,
6075 typename _OutputIterator, typename _Compare>
08addde6
PE
6076 _OutputIterator
6077 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
6078 _InputIterator2 __first2, _InputIterator2 __last2,
6079 _OutputIterator __result, _Compare __comp)
02d92e3b 6080 {
e75ea710
PC
6081 typedef typename iterator_traits<_InputIterator1>::value_type
6082 _ValueType1;
6083 typedef typename iterator_traits<_InputIterator2>::value_type
6084 _ValueType2;
6085
02d92e3b 6086 // concept requirements
3d7c150e
BK
6087 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6088 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3d7c150e 6089 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710 6090 _ValueType1>)
3d7c150e 6091 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
e75ea710
PC
6092 _ValueType1, _ValueType2>)
6093 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6094 _ValueType2, _ValueType1>)
a4c07f2d
PC
6095 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6096 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
02d92e3b
SW
6097
6098 while (__first1 != __last1 && __first2 != __last2)
6099 if (__comp(*__first1, *__first2))
6100 ++__first1;
6101 else if (__comp(*__first2, *__first1))
6102 ++__first2;
ffa67767
PC
6103 else
6104 {
6105 *__result = *__first1;
6106 ++__first1;
6107 ++__first2;
6108 ++__result;
6109 }
02d92e3b
SW
6110 return __result;
6111 }
6112
119dbb1f
JQ
6113 /**
6114 * @brief Return the difference of two sorted ranges.
5b9daa7e 6115 * @ingroup set_algorithms
93c66bc6
BK
6116 * @param __first1 Start of first range.
6117 * @param __last1 End of first range.
6118 * @param __first2 Start of second range.
6119 * @param __last2 End of second range.
119dbb1f 6120 * @return End of the output range.
aac2878e 6121 * @ingroup set_algorithms
119dbb1f
JQ
6122 *
6123 * This operation iterates over both ranges, copying elements present in
6124 * the first range but not the second in order to the output range.
6125 * Iterators increment for each range. When the current element of the
6126 * first range is less than the second, that element is copied and the
6127 * iterator advances. If the current element of the second range is less,
6128 * the iterator advances, but no element is copied. If an element is
6129 * contained in both ranges, no elements are copied and both ranges
6130 * advance. The output range may not overlap either input range.
6131 */
ffa67767
PC
6132 template<typename _InputIterator1, typename _InputIterator2,
6133 typename _OutputIterator>
08addde6
PE
6134 _OutputIterator
6135 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6136 _InputIterator2 __first2, _InputIterator2 __last2,
6137 _OutputIterator __result)
02d92e3b 6138 {
e75ea710
PC
6139 typedef typename iterator_traits<_InputIterator1>::value_type
6140 _ValueType1;
6141 typedef typename iterator_traits<_InputIterator2>::value_type
6142 _ValueType2;
6143
02d92e3b 6144 // concept requirements
3d7c150e
BK
6145 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6146 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6147 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710
PC
6148 _ValueType1>)
6149 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6150 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
a4c07f2d
PC
6151 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6152 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
02d92e3b
SW
6153
6154 while (__first1 != __last1 && __first2 != __last2)
ffa67767
PC
6155 if (*__first1 < *__first2)
6156 {
6157 *__result = *__first1;
6158 ++__first1;
6159 ++__result;
6160 }
02d92e3b
SW
6161 else if (*__first2 < *__first1)
6162 ++__first2;
ffa67767
PC
6163 else
6164 {
6165 ++__first1;
6166 ++__first2;
6167 }
c868f37e 6168 return std::copy(__first1, __last1, __result);
02d92e3b
SW
6169 }
6170
119dbb1f
JQ
6171 /**
6172 * @brief Return the difference of two sorted ranges using comparison
6173 * functor.
5b9daa7e 6174 * @ingroup set_algorithms
93c66bc6
BK
6175 * @param __first1 Start of first range.
6176 * @param __last1 End of first range.
6177 * @param __first2 Start of second range.
6178 * @param __last2 End of second range.
6179 * @param __comp The comparison functor.
119dbb1f 6180 * @return End of the output range.
aac2878e 6181 * @ingroup set_algorithms
119dbb1f
JQ
6182 *
6183 * This operation iterates over both ranges, copying elements present in
6184 * the first range but not the second in order to the output range.
6185 * Iterators increment for each range. When the current element of the
7897a1c0 6186 * first range is less than the second according to @p __comp, that element
119dbb1f
JQ
6187 * is copied and the iterator advances. If the current element of the
6188 * second range is less, no element is copied and the iterator advances.
7897a1c0 6189 * If an element is contained in both ranges according to @p __comp, no
119dbb1f
JQ
6190 * elements are copied and both ranges advance. The output range may not
6191 * overlap either input range.
6192 */
ffa67767
PC
6193 template<typename _InputIterator1, typename _InputIterator2,
6194 typename _OutputIterator, typename _Compare>
08addde6
PE
6195 _OutputIterator
6196 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6197 _InputIterator2 __first2, _InputIterator2 __last2,
6198 _OutputIterator __result, _Compare __comp)
02d92e3b 6199 {
e75ea710
PC
6200 typedef typename iterator_traits<_InputIterator1>::value_type
6201 _ValueType1;
6202 typedef typename iterator_traits<_InputIterator2>::value_type
6203 _ValueType2;
6204
02d92e3b 6205 // concept requirements
3d7c150e
BK
6206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6207 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3d7c150e 6208 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710 6209 _ValueType1>)
3d7c150e 6210 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
e75ea710
PC
6211 _ValueType1, _ValueType2>)
6212 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6213 _ValueType2, _ValueType1>)
a4c07f2d
PC
6214 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6215 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
02d92e3b
SW
6216
6217 while (__first1 != __last1 && __first2 != __last2)
ffa67767
PC
6218 if (__comp(*__first1, *__first2))
6219 {
6220 *__result = *__first1;
6221 ++__first1;
6222 ++__result;
6223 }
02d92e3b
SW
6224 else if (__comp(*__first2, *__first1))
6225 ++__first2;
ffa67767
PC
6226 else
6227 {
6228 ++__first1;
6229 ++__first2;
6230 }
c868f37e 6231 return std::copy(__first1, __last1, __result);
02d92e3b
SW
6232 }
6233
119dbb1f
JQ
6234 /**
6235 * @brief Return the symmetric difference of two sorted ranges.
5b9daa7e 6236 * @ingroup set_algorithms
93c66bc6
BK
6237 * @param __first1 Start of first range.
6238 * @param __last1 End of first range.
6239 * @param __first2 Start of second range.
6240 * @param __last2 End of second range.
119dbb1f 6241 * @return End of the output range.
aac2878e 6242 * @ingroup set_algorithms
119dbb1f
JQ
6243 *
6244 * This operation iterates over both ranges, copying elements present in
6245 * one range but not the other in order to the output range. Iterators
6246 * increment for each range. When the current element of one range is less
6247 * than the other, that element is copied and the iterator advances. If an
6248 * element is contained in both ranges, no elements are copied and both
6249 * ranges advance. The output range may not overlap either input range.
6250 */
ffa67767
PC
6251 template<typename _InputIterator1, typename _InputIterator2,
6252 typename _OutputIterator>
08addde6
PE
6253 _OutputIterator
6254 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6255 _InputIterator2 __first2, _InputIterator2 __last2,
6256 _OutputIterator __result)
02d92e3b 6257 {
e75ea710
PC
6258 typedef typename iterator_traits<_InputIterator1>::value_type
6259 _ValueType1;
6260 typedef typename iterator_traits<_InputIterator2>::value_type
6261 _ValueType2;
6262
02d92e3b 6263 // concept requirements
3d7c150e
BK
6264 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6265 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6266 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710
PC
6267 _ValueType1>)
6268 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6269 _ValueType2>)
6270 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6271 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
a4c07f2d
PC
6272 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6273 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
02d92e3b
SW
6274
6275 while (__first1 != __last1 && __first2 != __last2)
ffa67767
PC
6276 if (*__first1 < *__first2)
6277 {
6278 *__result = *__first1;
6279 ++__first1;
6280 ++__result;
6281 }
6282 else if (*__first2 < *__first1)
6283 {
6284 *__result = *__first2;
6285 ++__first2;
6286 ++__result;
6287 }
6288 else
6289 {
6290 ++__first1;
6291 ++__first2;
6292 }
ed6814f7 6293 return std::copy(__first2, __last2, std::copy(__first1,
ffa67767 6294 __last1, __result));
02d92e3b
SW
6295 }
6296
119dbb1f
JQ
6297 /**
6298 * @brief Return the symmetric difference of two sorted ranges using
6299 * comparison functor.
5b9daa7e 6300 * @ingroup set_algorithms
93c66bc6
BK
6301 * @param __first1 Start of first range.
6302 * @param __last1 End of first range.
6303 * @param __first2 Start of second range.
6304 * @param __last2 End of second range.
6305 * @param __comp The comparison functor.
119dbb1f 6306 * @return End of the output range.
aac2878e 6307 * @ingroup set_algorithms
119dbb1f
JQ
6308 *
6309 * This operation iterates over both ranges, copying elements present in
6310 * one range but not the other in order to the output range. Iterators
6311 * increment for each range. When the current element of one range is less
7897a1c0 6312 * than the other according to @p comp, that element is copied and the
119dbb1f 6313 * iterator advances. If an element is contained in both ranges according
7897a1c0 6314 * to @p __comp, no elements are copied and both ranges advance. The output
119dbb1f
JQ
6315 * range may not overlap either input range.
6316 */
ffa67767
PC
6317 template<typename _InputIterator1, typename _InputIterator2,
6318 typename _OutputIterator, typename _Compare>
08addde6
PE
6319 _OutputIterator
6320 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6321 _InputIterator2 __first2, _InputIterator2 __last2,
6322 _OutputIterator __result,
02d92e3b
SW
6323 _Compare __comp)
6324 {
e75ea710
PC
6325 typedef typename iterator_traits<_InputIterator1>::value_type
6326 _ValueType1;
6327 typedef typename iterator_traits<_InputIterator2>::value_type
6328 _ValueType2;
6329
02d92e3b 6330 // concept requirements
3d7c150e
BK
6331 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6332 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3d7c150e 6333 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
e75ea710
PC
6334 _ValueType1>)
6335 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6336 _ValueType2>)
6337 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6338 _ValueType1, _ValueType2>)
3d7c150e 6339 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
e75ea710 6340 _ValueType2, _ValueType1>)
a4c07f2d
PC
6341 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6342 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
02d92e3b
SW
6343
6344 while (__first1 != __last1 && __first2 != __last2)
ffa67767
PC
6345 if (__comp(*__first1, *__first2))
6346 {
6347 *__result = *__first1;
6348 ++__first1;
6349 ++__result;
6350 }
6351 else if (__comp(*__first2, *__first1))
6352 {
6353 *__result = *__first2;
6354 ++__first2;
6355 ++__result;
6356 }
6357 else
6358 {
6359 ++__first1;
6360 ++__first2;
6361 }
c2ba9709
JS
6362 return std::copy(__first2, __last2,
6363 std::copy(__first1, __last1, __result));
02d92e3b
SW
6364 }
6365
02d92e3b 6366
119dbb1f
JQ
6367 /**
6368 * @brief Return the minimum element in a range.
5b9daa7e 6369 * @ingroup sorting_algorithms
93c66bc6
BK
6370 * @param __first Start of range.
6371 * @param __last End of range.
119dbb1f
JQ
6372 * @return Iterator referencing the first instance of the smallest value.
6373 */
08addde6
PE
6374 template<typename _ForwardIterator>
6375 _ForwardIterator
6376 min_element(_ForwardIterator __first, _ForwardIterator __last)
02d92e3b
SW
6377 {
6378 // concept requirements
3d7c150e
BK
6379 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6380 __glibcxx_function_requires(_LessThanComparableConcept<
08addde6 6381 typename iterator_traits<_ForwardIterator>::value_type>)
285b36d6 6382 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 6383
ffa67767
PC
6384 if (__first == __last)
6385 return __first;
08addde6 6386 _ForwardIterator __result = __first;
c0d88161 6387 while (++__first != __last)
02d92e3b
SW
6388 if (*__first < *__result)
6389 __result = __first;
6390 return __result;
6391 }
6392
119dbb1f
JQ
6393 /**
6394 * @brief Return the minimum element in a range using comparison functor.
5b9daa7e 6395 * @ingroup sorting_algorithms
93c66bc6
BK
6396 * @param __first Start of range.
6397 * @param __last End of range.
6398 * @param __comp Comparison functor.
119dbb1f 6399 * @return Iterator referencing the first instance of the smallest value
7897a1c0 6400 * according to __comp.
119dbb1f 6401 */
08addde6
PE
6402 template<typename _ForwardIterator, typename _Compare>
6403 _ForwardIterator
6404 min_element(_ForwardIterator __first, _ForwardIterator __last,
02d92e3b
SW
6405 _Compare __comp)
6406 {
6407 // concept requirements
3d7c150e
BK
6408 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6409 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
08addde6
PE
6410 typename iterator_traits<_ForwardIterator>::value_type,
6411 typename iterator_traits<_ForwardIterator>::value_type>)
285b36d6 6412 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 6413
ffa67767
PC
6414 if (__first == __last)
6415 return __first;
08addde6 6416 _ForwardIterator __result = __first;
c0d88161 6417 while (++__first != __last)
02d92e3b
SW
6418 if (__comp(*__first, *__result))
6419 __result = __first;
6420 return __result;
6421 }
6422
119dbb1f 6423 /**
da5a2efd 6424 * @brief Return the maximum element in a range.
5b9daa7e 6425 * @ingroup sorting_algorithms
93c66bc6
BK
6426 * @param __first Start of range.
6427 * @param __last End of range.
da5a2efd 6428 * @return Iterator referencing the first instance of the largest value.
119dbb1f 6429 */
da5a2efd
PC
6430 template<typename _ForwardIterator>
6431 _ForwardIterator
6432 max_element(_ForwardIterator __first, _ForwardIterator __last)
02d92e3b
SW
6433 {
6434 // concept requirements
da5a2efd 6435 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3d7c150e 6436 __glibcxx_function_requires(_LessThanComparableConcept<
da5a2efd 6437 typename iterator_traits<_ForwardIterator>::value_type>)
285b36d6 6438 __glibcxx_requires_valid_range(__first, __last);
02d92e3b
SW
6439
6440 if (__first == __last)
da5a2efd
PC
6441 return __first;
6442 _ForwardIterator __result = __first;
6443 while (++__first != __last)
6444 if (*__result < *__first)
6445 __result = __first;
6446 return __result;
725dc051 6447 }
725dc051 6448
119dbb1f 6449 /**
da5a2efd 6450 * @brief Return the maximum element in a range using comparison functor.
5b9daa7e 6451 * @ingroup sorting_algorithms
93c66bc6
BK
6452 * @param __first Start of range.
6453 * @param __last End of range.
6454 * @param __comp Comparison functor.
da5a2efd 6455 * @return Iterator referencing the first instance of the largest value
93c66bc6 6456 * according to __comp.
119dbb1f 6457 */
da5a2efd
PC
6458 template<typename _ForwardIterator, typename _Compare>
6459 _ForwardIterator
6460 max_element(_ForwardIterator __first, _ForwardIterator __last,
6461 _Compare __comp)
02d92e3b
SW
6462 {
6463 // concept requirements
da5a2efd
PC
6464 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6465 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6466 typename iterator_traits<_ForwardIterator>::value_type,
6467 typename iterator_traits<_ForwardIterator>::value_type>)
285b36d6 6468 __glibcxx_requires_valid_range(__first, __last);
02d92e3b 6469
da5a2efd
PC
6470 if (__first == __last) return __first;
6471 _ForwardIterator __result = __first;
6472 while (++__first != __last)
6473 if (__comp(*__result, *__first))
6474 __result = __first;
6475 return __result;
725dc051 6476 }
02d92e3b 6477
12ffa228
BK
6478_GLIBCXX_END_NAMESPACE_ALGO
6479} // namespace std
725dc051 6480
046d30f4 6481#endif /* _STL_ALGO_H */