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