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