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
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
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
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
190 {
193
194 _DistanceType __tailSize = __last - __first;
195 _DistanceType __remainder = __count;
196
197 while (__remainder <= __tailSize) // the main loop...
198 {
199 __first += __remainder;
201 // __first here is always pointing to one past the last element of
202 // next possible match.
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,
239 forward_iterator_tag, forward_iterator_tag,
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,
270 bidirectional_iterator_tag, bidirectional_iterator_tag,
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
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,
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
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,
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
525
526 _DistanceType __len = std::distance(__first, __last);
527
528 while (__len > 0)
529 {
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
721 pair<_OutputIterator1, _OutputIterator2>
722 partition_copy(_InputIterator __first, _InputIterator __last,
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
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<
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<
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<
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,
908 {
909 // concept requirements
910 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
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
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
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))
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
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
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
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
1068 {
1069 // concept requirements
1070 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
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
1096 _OutputIterator __result)
1097 {
1098 // concept requirements
1099 __glibcxx_function_requires(_BidirectionalIteratorConcept<
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
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
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
1181 _BidirectionalIterator __middle,
1184 {
1185 // concept requirements
1186 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
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
1220 _RandomAccessIterator __middle,
1221 _RandomAccessIterator __last,
1223 {
1224 // concept requirements
1225 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
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<
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
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
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 _GLIBCXX26_CONSTEXPR
1451 _ForwardIterator
1453 _ForwardIterator __last,
1454 _Predicate __pred, _Distance __len,
1455 _Pointer __buffer,
1457 {
1458 if (__len == 1)
1459 return __first;
1460
1461 if (__len <= __buffer_size)
1462 {
1463 _ForwardIterator __result1 = __first;
1464 _Pointer __result2 = __buffer;
1465
1466 // The precondition guarantees that !__pred(__first), so
1467 // move that element to the buffer before starting the loop.
1468 // This ensures that we only call __pred once per element.
1469 *__result2 = _GLIBCXX_MOVE(*__first);
1470 ++__result2;
1471 ++__first;
1472 for (; __first != __last; ++__first)
1473 if (__pred(__first))
1474 {
1475 *__result1 = _GLIBCXX_MOVE(*__first);
1476 ++__result1;
1477 }
1478 else
1479 {
1480 *__result2 = _GLIBCXX_MOVE(*__first);
1481 ++__result2;
1482 }
1483
1484 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1485 return __result1;
1486 }
1487
1488 _ForwardIterator __middle = __first;
1489 std::advance(__middle, __len / 2);
1491 std::__stable_partition_adaptive(__first, __middle, __pred,
1492 __len / 2, __buffer,
1494
1495 // Advance past true-predicate values to satisfy this
1496 // function's preconditions.
1500
1501 if (__right_len)
1506
1507 return std::rotate(__left_split, __middle, __right_split);
1508 }
1509
1510 template<typename _ForwardIterator, typename _Predicate>
1511 _GLIBCXX26_CONSTEXPR
1512 _ForwardIterator
1513 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1514 _Predicate __pred)
1515 {
1516 __first = std::__find_if_not(__first, __last, __pred);
1517
1518 if (__first == __last)
1519 return __first;
1520
1521 typedef typename iterator_traits<_ForwardIterator>::value_type
1522 _ValueType;
1523 typedef typename iterator_traits<_ForwardIterator>::difference_type
1524 _DistanceType;
1525
1526 const _DistanceType __len = std::distance(__first, __last);
1527
1528#if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
1529 if consteval {
1530 // Simulate a _Temporary_buffer of length 1:
1531 _ValueType __buf = std::move(*__first);
1532 *__first = std::move(__buf);
1533 return std::__stable_partition_adaptive(__first, __last, __pred,
1534 __len,
1535 &__buf,
1536 _DistanceType(1));
1537 }
1538#endif
1539
1540 _Temporary_buffer<_ForwardIterator, _ValueType>
1541 __buf(__first, __len);
1542 return
1543 std::__stable_partition_adaptive(__first, __last, __pred,
1544 __len,
1545 __buf.begin(),
1546 _DistanceType(__buf.size()));
1547 }
1548
1549 /**
1550 * @brief Move elements for which a predicate is true to the beginning
1551 * of a sequence, preserving relative ordering.
1552 * @ingroup mutating_algorithms
1553 * @param __first A forward iterator.
1554 * @param __last A forward iterator.
1555 * @param __pred A predicate functor.
1556 * @return An iterator @p middle such that @p __pred(i) is true for each
1557 * iterator @p i in the range @p [first,middle) and false for each @p i
1558 * in the range @p [middle,last).
1559 *
1560 * Performs the same function as @p partition() with the additional
1561 * guarantee that the relative ordering of elements in each group is
1562 * preserved, so any two elements @p x and @p y in the range
1563 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1564 * relative ordering after calling @p stable_partition().
1565 */
1566 template<typename _ForwardIterator, typename _Predicate>
1567 _GLIBCXX26_CONSTEXPR
1568 inline _ForwardIterator
1569 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1570 _Predicate __pred)
1571 {
1572 // concept requirements
1573 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1575 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1577 __glibcxx_requires_valid_range(__first, __last);
1578
1579 return std::__stable_partition(__first, __last,
1580 __gnu_cxx::__ops::__pred_iter(__pred));
1581 }
1582#endif // HOSTED
1583
1584 /// @cond undocumented
1585
1586 /// This is a helper function for the sort routines.
1587 template<typename _RandomAccessIterator, typename _Compare>
1588 _GLIBCXX20_CONSTEXPR
1589 void
1590 __heap_select(_RandomAccessIterator __first,
1591 _RandomAccessIterator __middle,
1592 _RandomAccessIterator __last, _Compare __comp)
1593 {
1594 std::__make_heap(__first, __middle, __comp);
1595 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1596 if (__comp(__i, __first))
1597 std::__pop_heap(__first, __middle, __i, __comp);
1598 }
1599
1600 // partial_sort
1601
1602 template<typename _InputIterator, typename _RandomAccessIterator,
1603 typename _Compare>
1604 _GLIBCXX20_CONSTEXPR
1605 _RandomAccessIterator
1606 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1607 _RandomAccessIterator __result_first,
1608 _RandomAccessIterator __result_last,
1609 _Compare __comp)
1610 {
1611 typedef typename iterator_traits<_InputIterator>::value_type
1612 _InputValueType;
1613 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1614 typedef typename _RItTraits::difference_type _DistanceType;
1615
1616 if (__result_first == __result_last)
1617 return __result_last;
1618 _RandomAccessIterator __result_real_last = __result_first;
1619 while (__first != __last && __result_real_last != __result_last)
1620 {
1621 *__result_real_last = *__first;
1622 ++__result_real_last;
1623 ++__first;
1624 }
1625
1626 std::__make_heap(__result_first, __result_real_last, __comp);
1627 while (__first != __last)
1628 {
1629 if (__comp(__first, __result_first))
1630 std::__adjust_heap(__result_first, _DistanceType(0),
1631 _DistanceType(__result_real_last
1632 - __result_first),
1633 _InputValueType(*__first), __comp);
1634 ++__first;
1635 }
1636 std::__sort_heap(__result_first, __result_real_last, __comp);
1637 return __result_real_last;
1638 }
1639
1640 /// @endcond
1641
1642 /**
1643 * @brief Copy the smallest elements of a sequence.
1644 * @ingroup sorting_algorithms
1645 * @param __first An iterator.
1646 * @param __last Another iterator.
1647 * @param __result_first A random-access iterator.
1648 * @param __result_last Another random-access iterator.
1649 * @return An iterator indicating the end of the resulting sequence.
1650 *
1651 * Copies and sorts the smallest `N` values from the range
1652 * `[__first, __last)` to the range beginning at `__result_first`, where
1653 * the number of elements to be copied, `N`, is the smaller of
1654 * `(__last - __first)` and `(__result_last - __result_first)`.
1655 * After the sort if `i` and `j` are iterators in the range
1656 * `[__result_first,__result_first + N)` such that `i` precedes `j` then
1657 * `*j < *i` is false.
1658 * The value returned is `__result_first + N`.
1659 */
1660 template<typename _InputIterator, typename _RandomAccessIterator>
1661 _GLIBCXX20_CONSTEXPR
1662 inline _RandomAccessIterator
1663 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1666 {
1667#ifdef _GLIBCXX_CONCEPT_CHECKS
1672#endif
1673
1674 // concept requirements
1675 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1676 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1678 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1680 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1681 __glibcxx_requires_valid_range(__first, __last);
1682 __glibcxx_requires_irreflexive(__first, __last);
1683 __glibcxx_requires_valid_range(__result_first, __result_last);
1684
1685 return std::__partial_sort_copy(__first, __last,
1687 __gnu_cxx::__ops::__iter_less_iter());
1688 }
1689
1690 /**
1691 * @brief Copy the smallest elements of a sequence using a predicate for
1692 * comparison.
1693 * @ingroup sorting_algorithms
1694 * @param __first An input iterator.
1695 * @param __last Another input iterator.
1696 * @param __result_first A random-access iterator.
1697 * @param __result_last Another random-access iterator.
1698 * @param __comp A comparison functor.
1699 * @return An iterator indicating the end of the resulting sequence.
1700 *
1701 * Copies and sorts the smallest `N` values from the range
1702 * `[__first, __last)` to the range beginning at `result_first`, where
1703 * the number of elements to be copied, `N`, is the smaller of
1704 * `(__last - __first)` and `(__result_last - __result_first)`.
1705 * After the sort if `i` and `j` are iterators in the range
1706 * `[__result_first, __result_first + N)` such that `i` precedes `j` then
1707 * `__comp(*j, *i)` is false.
1708 * The value returned is `__result_first + N`.
1709 */
1710 template<typename _InputIterator, typename _RandomAccessIterator,
1711 typename _Compare>
1712 _GLIBCXX20_CONSTEXPR
1713 inline _RandomAccessIterator
1714 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1717 _Compare __comp)
1718 {
1719#ifdef _GLIBCXX_CONCEPT_CHECKS
1724#endif
1725
1726 // concept requirements
1727 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1728 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1730 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1732 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1734 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1736 __glibcxx_requires_valid_range(__first, __last);
1737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1738 __glibcxx_requires_valid_range(__result_first, __result_last);
1739
1740 return std::__partial_sort_copy(__first, __last,
1742 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1743 }
1744
1745 /// @cond undocumented
1746
1747 /// This is a helper function for the sort routine.
1748 template<typename _RandomAccessIterator, typename _Compare>
1749 _GLIBCXX20_CONSTEXPR
1750 void
1751 __unguarded_linear_insert(_RandomAccessIterator __last,
1752 _Compare __comp)
1753 {
1754 typename iterator_traits<_RandomAccessIterator>::value_type
1755 __val = _GLIBCXX_MOVE(*__last);
1756 _RandomAccessIterator __next = __last;
1757 --__next;
1758 while (__comp(__val, __next))
1759 {
1760 *__last = _GLIBCXX_MOVE(*__next);
1761 __last = __next;
1762 --__next;
1763 }
1764 *__last = _GLIBCXX_MOVE(__val);
1765 }
1766
1767 /// This is a helper function for the sort routine.
1768 template<typename _RandomAccessIterator, typename _Compare>
1769 _GLIBCXX20_CONSTEXPR
1770 void
1771 __insertion_sort(_RandomAccessIterator __first,
1772 _RandomAccessIterator __last, _Compare __comp)
1773 {
1774 if (__first == __last) return;
1775
1776 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1777 {
1778 if (__comp(__i, __first))
1779 {
1780 typename iterator_traits<_RandomAccessIterator>::value_type
1781 __val = _GLIBCXX_MOVE(*__i);
1782 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1783 *__first = _GLIBCXX_MOVE(__val);
1784 }
1785 else
1787 __gnu_cxx::__ops::__val_comp_iter(__comp));
1788 }
1789 }
1790
1791 /// This is a helper function for the sort routine.
1792 template<typename _RandomAccessIterator, typename _Compare>
1793 _GLIBCXX20_CONSTEXPR
1794 inline void
1795 __unguarded_insertion_sort(_RandomAccessIterator __first,
1796 _RandomAccessIterator __last, _Compare __comp)
1797 {
1798 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1800 __gnu_cxx::__ops::__val_comp_iter(__comp));
1801 }
1802
1803 /**
1804 * @doctodo
1805 * This controls some aspect of the sort routines.
1806 */
1807 enum { _S_threshold = 16 };
1808
1809 /// This is a helper function for the sort routine.
1810 template<typename _RandomAccessIterator, typename _Compare>
1811 _GLIBCXX20_CONSTEXPR
1812 void
1813 __final_insertion_sort(_RandomAccessIterator __first,
1814 _RandomAccessIterator __last, _Compare __comp)
1815 {
1816 if (__last - __first > int(_S_threshold))
1817 {
1818 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1819 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1820 __comp);
1821 }
1822 else
1823 std::__insertion_sort(__first, __last, __comp);
1824 }
1825
1826 /// This is a helper function...
1827 template<typename _RandomAccessIterator, typename _Compare>
1828 _GLIBCXX20_CONSTEXPR
1829 _RandomAccessIterator
1830 __unguarded_partition(_RandomAccessIterator __first,
1831 _RandomAccessIterator __last,
1832 _RandomAccessIterator __pivot, _Compare __comp)
1833 {
1834 while (true)
1835 {
1836 while (__comp(__first, __pivot))
1837 ++__first;
1838 --__last;
1839 while (__comp(__pivot, __last))
1840 --__last;
1841 if (!(__first < __last))
1842 return __first;
1843 std::iter_swap(__first, __last);
1844 ++__first;
1845 }
1846 }
1847
1848 /// This is a helper function...
1849 template<typename _RandomAccessIterator, typename _Compare>
1850 _GLIBCXX20_CONSTEXPR
1851 inline _RandomAccessIterator
1852 __unguarded_partition_pivot(_RandomAccessIterator __first,
1853 _RandomAccessIterator __last, _Compare __comp)
1854 {
1855 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1856 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1857 __comp);
1858 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1859 }
1860
1861 template<typename _RandomAccessIterator, typename _Compare>
1862 _GLIBCXX20_CONSTEXPR
1863 inline void
1864 __partial_sort(_RandomAccessIterator __first,
1865 _RandomAccessIterator __middle,
1866 _RandomAccessIterator __last,
1867 _Compare __comp)
1868 {
1869 std::__heap_select(__first, __middle, __last, __comp);
1870 std::__sort_heap(__first, __middle, __comp);
1871 }
1872
1873 /// This is a helper function for the sort routine.
1874 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1875 _GLIBCXX20_CONSTEXPR
1876 void
1877 __introsort_loop(_RandomAccessIterator __first,
1878 _RandomAccessIterator __last,
1879 _Size __depth_limit, _Compare __comp)
1880 {
1881 while (__last - __first > int(_S_threshold))
1882 {
1883 if (__depth_limit == 0)
1884 {
1885 std::__partial_sort(__first, __last, __last, __comp);
1886 return;
1887 }
1888 --__depth_limit;
1889 _RandomAccessIterator __cut =
1890 std::__unguarded_partition_pivot(__first, __last, __comp);
1891 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1892 __last = __cut;
1893 }
1894 }
1895
1896 // sort
1897
1898 template<typename _RandomAccessIterator, typename _Compare>
1899 _GLIBCXX20_CONSTEXPR
1900 inline void
1901 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1902 _Compare __comp)
1903 {
1904 if (__first != __last)
1905 {
1906 std::__introsort_loop(__first, __last,
1907 std::__lg(__last - __first) * 2,
1908 __comp);
1909 std::__final_insertion_sort(__first, __last, __comp);
1910 }
1911 }
1912
1913 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1914 _GLIBCXX20_CONSTEXPR
1915 void
1916 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1917 _RandomAccessIterator __last, _Size __depth_limit,
1918 _Compare __comp)
1919 {
1920 while (__last - __first > 3)
1921 {
1922 if (__depth_limit == 0)
1923 {
1924 std::__heap_select(__first, __nth + 1, __last, __comp);
1925 // Place the nth largest element in its final position.
1926 std::iter_swap(__first, __nth);
1927 return;
1928 }
1929 --__depth_limit;
1930 _RandomAccessIterator __cut =
1931 std::__unguarded_partition_pivot(__first, __last, __comp);
1932 if (__cut <= __nth)
1933 __first = __cut;
1934 else
1935 __last = __cut;
1936 }
1937 std::__insertion_sort(__first, __last, __comp);
1938 }
1939
1940 /// @endcond
1941
1942 // nth_element
1943
1944 // lower_bound moved to stl_algobase.h
1945
1946 /**
1947 * @brief Finds the first position in which `__val` could be inserted
1948 * without changing the ordering.
1949 * @ingroup binary_search_algorithms
1950 * @param __first An iterator to the start of a sorted range.
1951 * @param __last A past-the-end iterator for the sorted range.
1952 * @param __val The search term.
1953 * @param __comp A functor to use for comparisons.
1954 * @return An iterator pointing to the first element _not less than_
1955 * `__val`, or `end()` if every element is less than `__val`.
1956 * @ingroup binary_search_algorithms
1957 *
1958 * The comparison function should have the same effects on ordering as
1959 * the function used for the initial sort.
1960 */
1961 template<typename _ForwardIterator, typename _Tp, typename _Compare>
1962 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1963 inline _ForwardIterator
1964 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1965 const _Tp& __val, _Compare __comp)
1966 {
1967 // concept requirements
1968 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1969 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1971 __glibcxx_requires_partitioned_lower_pred(__first, __last,
1972 __val, __comp);
1973
1974 return std::__lower_bound(__first, __last, __val,
1975 __gnu_cxx::__ops::__iter_comp_val(__comp));
1976 }
1977
1978 template<typename _ForwardIterator, typename _Tp, typename _Compare>
1979 _GLIBCXX20_CONSTEXPR
1980 _ForwardIterator
1981 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
1982 const _Tp& __val, _Compare __comp)
1983 {
1984 typedef typename iterator_traits<_ForwardIterator>::difference_type
1985 _DistanceType;
1986
1987 _DistanceType __len = std::distance(__first, __last);
1988
1989 while (__len > 0)
1990 {
1991 _DistanceType __half = __len >> 1;
1992 _ForwardIterator __middle = __first;
1993 std::advance(__middle, __half);
1994 if (__comp(__val, __middle))
1995 __len = __half;
1996 else
1997 {
1998 __first = __middle;
1999 ++__first;
2000 __len = __len - __half - 1;
2001 }
2002 }
2003 return __first;
2004 }
2005
2006 /**
2007 * @brief Finds the last position in which @p __val could be inserted
2008 * without changing the ordering.
2009 * @ingroup binary_search_algorithms
2010 * @param __first An iterator.
2011 * @param __last Another iterator.
2012 * @param __val The search term.
2013 * @return An iterator pointing to the first element greater than @p __val,
2014 * or end() if no elements are greater than @p __val.
2015 * @ingroup binary_search_algorithms
2016 */
2017 template<typename _ForwardIterator, typename _Tp>
2018 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2019 inline _ForwardIterator
2020 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2021 const _Tp& __val)
2022 {
2023 // concept requirements
2024 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2025 __glibcxx_function_requires(_LessThanOpConcept<
2027 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2028
2029 return std::__upper_bound(__first, __last, __val,
2030 __gnu_cxx::__ops::__val_less_iter());
2031 }
2032
2033 /**
2034 * @brief Finds the last position in which @p __val could be inserted
2035 * without changing the ordering.
2036 * @ingroup binary_search_algorithms
2037 * @param __first An iterator.
2038 * @param __last Another iterator.
2039 * @param __val The search term.
2040 * @param __comp A functor to use for comparisons.
2041 * @return An iterator pointing to the first element greater than @p __val,
2042 * or end() if no elements are greater than @p __val.
2043 * @ingroup binary_search_algorithms
2044 *
2045 * The comparison function should have the same effects on ordering as
2046 * the function used for the initial sort.
2047 */
2048 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2049 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2050 inline _ForwardIterator
2051 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2052 const _Tp& __val, _Compare __comp)
2053 {
2054 // concept requirements
2055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2056 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2058 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2059 __val, __comp);
2060
2061 return std::__upper_bound(__first, __last, __val,
2062 __gnu_cxx::__ops::__val_comp_iter(__comp));
2063 }
2064
2065 template<typename _ForwardIterator, typename _Tp,
2066 typename _CompareItTp, typename _CompareTpIt>
2067 _GLIBCXX20_CONSTEXPR
2068 pair<_ForwardIterator, _ForwardIterator>
2069 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2070 const _Tp& __val,
2071 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2072 {
2073 typedef typename iterator_traits<_ForwardIterator>::difference_type
2074 _DistanceType;
2075
2076 _DistanceType __len = std::distance(__first, __last);
2077
2078 while (__len > 0)
2079 {
2080 _DistanceType __half = __len >> 1;
2081 _ForwardIterator __middle = __first;
2082 std::advance(__middle, __half);
2083 if (__comp_it_val(__middle, __val))
2084 {
2085 __first = __middle;
2086 ++__first;
2087 __len = __len - __half - 1;
2088 }
2089 else if (__comp_val_it(__val, __middle))
2090 __len = __half;
2091 else
2092 {
2093 _ForwardIterator __left
2094 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2095 std::advance(__first, __len);
2096 _ForwardIterator __right
2097 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2098 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2099 }
2100 }
2101 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2102 }
2103
2104 /**
2105 * @brief Finds the largest subrange in which @p __val could be inserted
2106 * at any place in it without changing the ordering.
2107 * @ingroup binary_search_algorithms
2108 * @param __first An iterator.
2109 * @param __last Another iterator.
2110 * @param __val The search term.
2111 * @return An pair of iterators defining the subrange.
2112 * @ingroup binary_search_algorithms
2113 *
2114 * This is equivalent to
2115 * @code
2116 * std::make_pair(lower_bound(__first, __last, __val),
2117 * upper_bound(__first, __last, __val))
2118 * @endcode
2119 * but does not actually call those functions.
2120 */
2121 template<typename _ForwardIterator, typename _Tp>
2122 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2123 inline pair<_ForwardIterator, _ForwardIterator>
2124 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2125 const _Tp& __val)
2126 {
2127 // concept requirements
2128 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2129 __glibcxx_function_requires(_LessThanOpConcept<
2131 __glibcxx_function_requires(_LessThanOpConcept<
2133 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2134 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2135
2136 return std::__equal_range(__first, __last, __val,
2137 __gnu_cxx::__ops::__iter_less_val(),
2138 __gnu_cxx::__ops::__val_less_iter());
2139 }
2140
2141 /**
2142 * @brief Finds the largest subrange in which @p __val could be inserted
2143 * at any place in it without changing the ordering.
2144 * @param __first An iterator.
2145 * @param __last Another iterator.
2146 * @param __val The search term.
2147 * @param __comp A functor to use for comparisons.
2148 * @return An pair of iterators defining the subrange.
2149 * @ingroup binary_search_algorithms
2150 *
2151 * This is equivalent to
2152 * @code
2153 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2154 * upper_bound(__first, __last, __val, __comp))
2155 * @endcode
2156 * but does not actually call those functions.
2157 */
2158 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2159 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2160 inline pair<_ForwardIterator, _ForwardIterator>
2161 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2162 const _Tp& __val, _Compare __comp)
2163 {
2164 // concept requirements
2165 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2166 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2168 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2170 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2171 __val, __comp);
2172 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2173 __val, __comp);
2174
2175 return std::__equal_range(__first, __last, __val,
2176 __gnu_cxx::__ops::__iter_comp_val(__comp),
2177 __gnu_cxx::__ops::__val_comp_iter(__comp));
2178 }
2179
2180 /**
2181 * @brief Determines whether an element exists in a range.
2182 * @ingroup binary_search_algorithms
2183 * @param __first An iterator.
2184 * @param __last Another iterator.
2185 * @param __val The search term.
2186 * @return True if @p __val (or its equivalent) is in [@p
2187 * __first,@p __last ].
2188 *
2189 * Note that this does not actually return an iterator to @p __val. For
2190 * that, use std::find or a container's specialized find member functions.
2191 */
2192 template<typename _ForwardIterator, typename _Tp>
2193 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2194 bool
2195 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2196 const _Tp& __val)
2197 {
2198 // concept requirements
2199 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2200 __glibcxx_function_requires(_LessThanOpConcept<
2202 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2203 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2204
2206 = std::__lower_bound(__first, __last, __val,
2207 __gnu_cxx::__ops::__iter_less_val());
2208 return __i != __last && !(__val < *__i);
2209 }
2210
2211 /**
2212 * @brief Determines whether an element exists in a range.
2213 * @ingroup binary_search_algorithms
2214 * @param __first An iterator.
2215 * @param __last Another iterator.
2216 * @param __val The search term.
2217 * @param __comp A functor to use for comparisons.
2218 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2219 *
2220 * Note that this does not actually return an iterator to @p __val. For
2221 * that, use std::find or a container's specialized find member functions.
2222 *
2223 * The comparison function should have the same effects on ordering as
2224 * the function used for the initial sort.
2225 */
2226 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2227 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2228 bool
2229 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2230 const _Tp& __val, _Compare __comp)
2231 {
2232 // concept requirements
2233 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2234 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2236 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2237 __val, __comp);
2238 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2239 __val, __comp);
2240
2242 = std::__lower_bound(__first, __last, __val,
2243 __gnu_cxx::__ops::__iter_comp_val(__comp));
2244 return __i != __last && !bool(__comp(__val, *__i));
2245 }
2246
2247 // merge
2248
2249 /// This is a helper function for the __merge_adaptive routines.
2250 template<typename _InputIterator1, typename _InputIterator2,
2251 typename _OutputIterator, typename _Compare>
2252 void
2255 _OutputIterator __result, _Compare __comp)
2256 {
2257 while (__first1 != __last1 && __first2 != __last2)
2258 {
2259 if (__comp(__first2, __first1))
2260 {
2261 *__result = _GLIBCXX_MOVE(*__first2);
2262 ++__first2;
2263 }
2264 else
2265 {
2266 *__result = _GLIBCXX_MOVE(*__first1);
2267 ++__first1;
2268 }
2269 ++__result;
2270 }
2271 if (__first1 != __last1)
2272 _GLIBCXX_MOVE3(__first1, __last1, __result);
2273 }
2274
2275 /// This is a helper function for the __merge_adaptive routines.
2276 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2277 typename _BidirectionalIterator3, typename _Compare>
2278 void
2283 _BidirectionalIterator3 __result,
2284 _Compare __comp)
2285 {
2286 if (__first1 == __last1)
2287 {
2288 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2289 return;
2290 }
2291 else if (__first2 == __last2)
2292 return;
2293
2294 --__last1;
2295 --__last2;
2296 while (true)
2297 {
2298 if (__comp(__last2, __last1))
2299 {
2300 *--__result = _GLIBCXX_MOVE(*__last1);
2301 if (__first1 == __last1)
2302 {
2303 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2304 return;
2305 }
2306 --__last1;
2307 }
2308 else
2309 {
2310 *--__result = _GLIBCXX_MOVE(*__last2);
2311 if (__first2 == __last2)
2312 return;
2313 --__last2;
2314 }
2315 }
2316 }
2317
2318 /// This is a helper function for the merge routines.
2319 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2320 typename _Distance>
2321 _BidirectionalIterator1
2323 _BidirectionalIterator1 __middle,
2328 {
2330 if (__len1 > __len2 && __len2 <= __buffer_size)
2331 {
2332 if (__len2)
2333 {
2334 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2335 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2336 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2337 }
2338 else
2339 return __first;
2340 }
2341 else if (__len1 <= __buffer_size)
2342 {
2343 if (__len1)
2344 {
2345 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2346 _GLIBCXX_MOVE3(__middle, __last, __first);
2347 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2348 }
2349 else
2350 return __last;
2351 }
2352 else
2353 return std::rotate(__first, __middle, __last);
2354 }
2355
2356 /// This is a helper function for the merge routines.
2357 template<typename _BidirectionalIterator, typename _Distance,
2358 typename _Pointer, typename _Compare>
2359 void
2361 _BidirectionalIterator __middle,
2364 _Pointer __buffer, _Compare __comp)
2365 {
2366 if (__len1 <= __len2)
2367 {
2368 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2370 __first, __comp);
2371 }
2372 else
2373 {
2374 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2376 __buffer_end, __last, __comp);
2377 }
2378 }
2379
2380 template<typename _BidirectionalIterator, typename _Distance,
2381 typename _Pointer, typename _Compare>
2382 void
2383 __merge_adaptive_resize(_BidirectionalIterator __first,
2384 _BidirectionalIterator __middle,
2385 _BidirectionalIterator __last,
2386 _Distance __len1, _Distance __len2,
2387 _Pointer __buffer, _Distance __buffer_size,
2388 _Compare __comp)
2389 {
2390 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2391 std::__merge_adaptive(__first, __middle, __last,
2392 __len1, __len2, __buffer, __comp);
2393 else
2394 {
2395 _BidirectionalIterator __first_cut = __first;
2396 _BidirectionalIterator __second_cut = __middle;
2397 _Distance __len11 = 0;
2398 _Distance __len22 = 0;
2399 if (__len1 > __len2)
2400 {
2401 __len11 = __len1 / 2;
2402 std::advance(__first_cut, __len11);
2403 __second_cut
2404 = std::__lower_bound(__middle, __last, *__first_cut,
2405 __gnu_cxx::__ops::__iter_comp_val(__comp));
2406 __len22 = std::distance(__middle, __second_cut);
2407 }
2408 else
2409 {
2410 __len22 = __len2 / 2;
2411 std::advance(__second_cut, __len22);
2412 __first_cut
2413 = std::__upper_bound(__first, __middle, *__second_cut,
2414 __gnu_cxx::__ops::__val_comp_iter(__comp));
2415 __len11 = std::distance(__first, __first_cut);
2416 }
2417
2418 _BidirectionalIterator __new_middle
2419 = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2420 _Distance(__len1 - __len11), __len22,
2421 __buffer, __buffer_size);
2422 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2423 __len11, __len22,
2424 __buffer, __buffer_size, __comp);
2425 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2426 _Distance(__len1 - __len11),
2427 _Distance(__len2 - __len22),
2428 __buffer, __buffer_size, __comp);
2429 }
2430 }
2431
2432 /// This is a helper function for the merge routines.
2433 template<typename _BidirectionalIterator, typename _Distance,
2434 typename _Compare>
2435 _GLIBCXX26_CONSTEXPR
2436 void
2438 _BidirectionalIterator __middle,
2441 _Compare __comp)
2442 {
2443 if (__len1 == 0 || __len2 == 0)
2444 return;
2445
2446 if (__len1 + __len2 == 2)
2447 {
2448 if (__comp(__middle, __first))
2449 std::iter_swap(__first, __middle);
2450 return;
2451 }
2452
2455 _Distance __len11 = 0;
2456 _Distance __len22 = 0;
2457 if (__len1 > __len2)
2458 {
2459 __len11 = __len1 / 2;
2462 = std::__lower_bound(__middle, __last, *__first_cut,
2463 __gnu_cxx::__ops::__iter_comp_val(__comp));
2464 __len22 = std::distance(__middle, __second_cut);
2465 }
2466 else
2467 {
2468 __len22 = __len2 / 2;
2471 = std::__upper_bound(__first, __middle, *__second_cut,
2472 __gnu_cxx::__ops::__val_comp_iter(__comp));
2473 __len11 = std::distance(__first, __first_cut);
2474 }
2475
2477 = std::rotate(__first_cut, __middle, __second_cut);
2479 __len11, __len22, __comp);
2481 __len1 - __len11, __len2 - __len22, __comp);
2482 }
2483
2484 template<typename _BidirectionalIterator, typename _Compare>
2485 _GLIBCXX26_CONSTEXPR
2486 void
2487 __inplace_merge(_BidirectionalIterator __first,
2488 _BidirectionalIterator __middle,
2489 _BidirectionalIterator __last,
2490 _Compare __comp)
2491 {
2492 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2493 _ValueType;
2494 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2495 _DistanceType;
2496
2497 if (__first == __middle || __middle == __last)
2498 return;
2499
2500 const _DistanceType __len1 = std::distance(__first, __middle);
2501 const _DistanceType __len2 = std::distance(__middle, __last);
2502
2503#if _GLIBCXX_HOSTED
2504# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
2505 if consteval {
2507 (__first, __middle, __last, __len1, __len2, __comp);
2508 }
2509# endif
2510 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2511 // __merge_adaptive will use a buffer for the smaller of
2512 // [first,middle) and [middle,last).
2513 _TmpBuf __buf(__first, std::min(__len1, __len2));
2514
2515 if (__builtin_expect(__buf.size() == __buf.requested_size(), true))
2517 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2518 else if (__builtin_expect(__buf.begin() == 0, false))
2520 (__first, __middle, __last, __len1, __len2, __comp);
2521 else
2522 std::__merge_adaptive_resize
2523 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2524 _DistanceType(__buf.size()), __comp);
2525#else
2527 (__first, __middle, __last, __len1, __len2, __comp);
2528#endif
2529 }
2530
2531 /**
2532 * @brief Merges two sorted ranges in place.
2533 * @ingroup sorting_algorithms
2534 * @param __first An iterator.
2535 * @param __middle Another iterator.
2536 * @param __last Another iterator.
2537 * @return Nothing.
2538 *
2539 * Merges two sorted and consecutive ranges, [__first,__middle) and
2540 * [__middle,__last), and puts the result in [__first,__last). The
2541 * output will be sorted. The sort is @e stable, that is, for
2542 * equivalent elements in the two ranges, elements from the first
2543 * range will always come before elements from the second.
2544 *
2545 * If enough additional memory is available, this takes (__last-__first)-1
2546 * comparisons. Otherwise an NlogN algorithm is used, where N is
2547 * distance(__first,__last).
2548 */
2549 template<typename _BidirectionalIterator>
2550 _GLIBCXX26_CONSTEXPR
2551 inline void
2552 inplace_merge(_BidirectionalIterator __first,
2553 _BidirectionalIterator __middle,
2555 {
2556 // concept requirements
2557 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2559 __glibcxx_function_requires(_LessThanComparableConcept<
2561 __glibcxx_requires_sorted(__first, __middle);
2562 __glibcxx_requires_sorted(__middle, __last);
2563 __glibcxx_requires_irreflexive(__first, __last);
2564
2565 std::__inplace_merge(__first, __middle, __last,
2566 __gnu_cxx::__ops::__iter_less_iter());
2567 }
2568
2569 /**
2570 * @brief Merges two sorted ranges in place.
2571 * @ingroup sorting_algorithms
2572 * @param __first An iterator.
2573 * @param __middle Another iterator.
2574 * @param __last Another iterator.
2575 * @param __comp A functor to use for comparisons.
2576 * @return Nothing.
2577 *
2578 * Merges two sorted and consecutive ranges, [__first,__middle) and
2579 * [middle,last), and puts the result in [__first,__last). The output will
2580 * be sorted. The sort is @e stable, that is, for equivalent
2581 * elements in the two ranges, elements from the first range will always
2582 * come before elements from the second.
2583 *
2584 * If enough additional memory is available, this takes (__last-__first)-1
2585 * comparisons. Otherwise an NlogN algorithm is used, where N is
2586 * distance(__first,__last).
2587 *
2588 * The comparison function should have the same effects on ordering as
2589 * the function used for the initial sort.
2590 */
2591 template<typename _BidirectionalIterator, typename _Compare>
2592 _GLIBCXX26_CONSTEXPR
2593 inline void
2594 inplace_merge(_BidirectionalIterator __first,
2595 _BidirectionalIterator __middle,
2597 _Compare __comp)
2598 {
2599 // concept requirements
2600 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2602 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2605 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2606 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2607 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2608
2609 std::__inplace_merge(__first, __middle, __last,
2610 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2611 }
2612
2613
2614 /// This is a helper function for the __merge_sort_loop routines.
2615 template<typename _InputIterator, typename _OutputIterator,
2616 typename _Compare>
2617 _OutputIterator
2620 _OutputIterator __result, _Compare __comp)
2621 {
2622 while (__first1 != __last1 && __first2 != __last2)
2623 {
2624 if (__comp(__first2, __first1))
2625 {
2626 *__result = _GLIBCXX_MOVE(*__first2);
2627 ++__first2;
2628 }
2629 else
2630 {
2631 *__result = _GLIBCXX_MOVE(*__first1);
2632 ++__first1;
2633 }
2634 ++__result;
2635 }
2636 return _GLIBCXX_MOVE3(__first2, __last2,
2637 _GLIBCXX_MOVE3(__first1, __last1,
2638 __result));
2639 }
2640
2641 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2642 typename _Distance, typename _Compare>
2643 void
2644 __merge_sort_loop(_RandomAccessIterator1 __first,
2645 _RandomAccessIterator1 __last,
2646 _RandomAccessIterator2 __result, _Distance __step_size,
2647 _Compare __comp)
2648 {
2649 const _Distance __two_step = 2 * __step_size;
2650
2651 while (__last - __first >= __two_step)
2652 {
2653 __result = std::__move_merge(__first, __first + __step_size,
2654 __first + __step_size,
2655 __first + __two_step,
2656 __result, __comp);
2657 __first += __two_step;
2658 }
2659 __step_size = std::min(_Distance(__last - __first), __step_size);
2660
2661 std::__move_merge(__first, __first + __step_size,
2662 __first + __step_size, __last, __result, __comp);
2663 }
2664
2665 template<typename _RandomAccessIterator, typename _Distance,
2666 typename _Compare>
2667 _GLIBCXX20_CONSTEXPR
2668 void
2669 __chunk_insertion_sort(_RandomAccessIterator __first,
2670 _RandomAccessIterator __last,
2671 _Distance __chunk_size, _Compare __comp)
2672 {
2673 while (__last - __first >= __chunk_size)
2674 {
2675 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2676 __first += __chunk_size;
2677 }
2678 std::__insertion_sort(__first, __last, __comp);
2679 }
2680
2681 enum { _S_chunk_size = 7 };
2682
2683 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2684 void
2685 __merge_sort_with_buffer(_RandomAccessIterator __first,
2686 _RandomAccessIterator __last,
2687 _Pointer __buffer, _Compare __comp)
2688 {
2689 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2690 _Distance;
2691
2692 const _Distance __len = __last - __first;
2693 const _Pointer __buffer_last = __buffer + __len;
2694
2695 _Distance __step_size = _S_chunk_size;
2696 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2697
2698 while (__step_size < __len)
2699 {
2700 std::__merge_sort_loop(__first, __last, __buffer,
2701 __step_size, __comp);
2702 __step_size *= 2;
2703 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2704 __step_size, __comp);
2705 __step_size *= 2;
2706 }
2707 }
2708
2709 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2710 void
2711 __stable_sort_adaptive(_RandomAccessIterator __first,
2712 _RandomAccessIterator __middle,
2713 _RandomAccessIterator __last,
2714 _Pointer __buffer, _Compare __comp)
2715 {
2716 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2717 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2718
2719 std::__merge_adaptive(__first, __middle, __last,
2720 __middle - __first, __last - __middle,
2721 __buffer, __comp);
2722 }
2723
2724 template<typename _RandomAccessIterator, typename _Pointer,
2725 typename _Distance, typename _Compare>
2726 void
2727 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2728 _RandomAccessIterator __last,
2729 _Pointer __buffer, _Distance __buffer_size,
2730 _Compare __comp)
2731 {
2732 const _Distance __len = (__last - __first + 1) / 2;
2733 const _RandomAccessIterator __middle = __first + __len;
2734 if (__len > __buffer_size)
2735 {
2736 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2737 __buffer_size, __comp);
2738 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2739 __buffer_size, __comp);
2740 std::__merge_adaptive_resize(__first, __middle, __last,
2741 _Distance(__middle - __first),
2742 _Distance(__last - __middle),
2743 __buffer, __buffer_size,
2744 __comp);
2745 }
2746 else
2747 std::__stable_sort_adaptive(__first, __middle, __last,
2748 __buffer, __comp);
2749 }
2750
2751 /// This is a helper function for the stable sorting routines.
2752 template<typename _RandomAccessIterator, typename _Compare>
2753 _GLIBCXX26_CONSTEXPR
2754 void
2756 _RandomAccessIterator __last, _Compare __comp)
2757 {
2758 if (__last - __first < 15)
2759 {
2760 std::__insertion_sort(__first, __last, __comp);
2761 return;
2762 }
2763 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2764 std::__inplace_stable_sort(__first, __middle, __comp);
2765 std::__inplace_stable_sort(__middle, __last, __comp);
2766 std::__merge_without_buffer(__first, __middle, __last,
2767 __middle - __first,
2768 __last - __middle,
2769 __comp);
2770 }
2771
2772 // stable_sort
2773
2774 // Set algorithms: includes, set_union, set_intersection, set_difference,
2775 // set_symmetric_difference. All of these algorithms have the precondition
2776 // that their input ranges are sorted and the postcondition that their output
2777 // ranges are sorted.
2778
2779 template<typename _InputIterator1, typename _InputIterator2,
2780 typename _Compare>
2781 _GLIBCXX20_CONSTEXPR
2782 bool
2783 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2784 _InputIterator2 __first2, _InputIterator2 __last2,
2785 _Compare __comp)
2786 {
2787 while (__first1 != __last1 && __first2 != __last2)
2788 {
2789 if (__comp(__first2, __first1))
2790 return false;
2791 if (!__comp(__first1, __first2))
2792 ++__first2;
2793 ++__first1;
2794 }
2795
2796 return __first2 == __last2;
2797 }
2798
2799 /**
2800 * @brief Determines whether all elements of a sequence exists in a range.
2801 * @param __first1 Start of search range.
2802 * @param __last1 End of search range.
2803 * @param __first2 Start of sequence
2804 * @param __last2 End of sequence.
2805 * @return True if each element in [__first2,__last2) is contained in order
2806 * within [__first1,__last1). False otherwise.
2807 * @ingroup set_algorithms
2808 *
2809 * This operation expects both [__first1,__last1) and
2810 * [__first2,__last2) to be sorted. Searches for the presence of
2811 * each element in [__first2,__last2) within [__first1,__last1).
2812 * The iterators over each range only move forward, so this is a
2813 * linear algorithm. If an element in [__first2,__last2) is not
2814 * found before the search iterator reaches @p __last2, false is
2815 * returned.
2816 */
2817 template<typename _InputIterator1, typename _InputIterator2>
2818 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2819 inline bool
2822 {
2823 // concept requirements
2824 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2825 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2826 __glibcxx_function_requires(_LessThanOpConcept<
2829 __glibcxx_function_requires(_LessThanOpConcept<
2832 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2833 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2834 __glibcxx_requires_irreflexive2(__first1, __last1);
2835 __glibcxx_requires_irreflexive2(__first2, __last2);
2836
2837 return std::__includes(__first1, __last1, __first2, __last2,
2838 __gnu_cxx::__ops::__iter_less_iter());
2839 }
2840
2841 /**
2842 * @brief Determines whether all elements of a sequence exists in a range
2843 * using comparison.
2844 * @ingroup set_algorithms
2845 * @param __first1 Start of search range.
2846 * @param __last1 End of search range.
2847 * @param __first2 Start of sequence
2848 * @param __last2 End of sequence.
2849 * @param __comp Comparison function to use.
2850 * @return True if each element in [__first2,__last2) is contained
2851 * in order within [__first1,__last1) according to comp. False
2852 * otherwise. @ingroup set_algorithms
2853 *
2854 * This operation expects both [__first1,__last1) and
2855 * [__first2,__last2) to be sorted. Searches for the presence of
2856 * each element in [__first2,__last2) within [__first1,__last1),
2857 * using comp to decide. The iterators over each range only move
2858 * forward, so this is a linear algorithm. If an element in
2859 * [__first2,__last2) is not found before the search iterator
2860 * reaches @p __last2, false is returned.
2861 */
2862 template<typename _InputIterator1, typename _InputIterator2,
2863 typename _Compare>
2864 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2865 inline bool
2868 _Compare __comp)
2869 {
2870 // concept requirements
2871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2872 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2873 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2876 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2879 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2880 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2881 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2882 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2883
2884 return std::__includes(__first1, __last1, __first2, __last2,
2885 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2886 }
2887
2888 // nth_element
2889 // merge
2890 // set_difference
2891 // set_intersection
2892 // set_union
2893 // stable_sort
2894 // set_symmetric_difference
2895 // min_element
2896 // max_element
2897
2898 template<typename _BidirectionalIterator, typename _Compare>
2899 _GLIBCXX20_CONSTEXPR
2900 bool
2901 __next_permutation(_BidirectionalIterator __first,
2902 _BidirectionalIterator __last, _Compare __comp)
2903 {
2904 if (__first == __last)
2905 return false;
2906 _BidirectionalIterator __i = __first;
2907 ++__i;
2908 if (__i == __last)
2909 return false;
2910 __i = __last;
2911 --__i;
2912
2913 for(;;)
2914 {
2915 _BidirectionalIterator __ii = __i;
2916 --__i;
2917 if (__comp(__i, __ii))
2918 {
2919 _BidirectionalIterator __j = __last;
2920 while (!__comp(__i, --__j))
2921 {}
2922 std::iter_swap(__i, __j);
2923 std::__reverse(__ii, __last,
2924 std::__iterator_category(__first));
2925 return true;
2926 }
2927 if (__i == __first)
2928 {
2929 std::__reverse(__first, __last,
2930 std::__iterator_category(__first));
2931 return false;
2932 }
2933 }
2934 }
2935
2936 /**
2937 * @brief Permute range into the next @e dictionary ordering.
2938 * @ingroup sorting_algorithms
2939 * @param __first Start of range.
2940 * @param __last End of range.
2941 * @return False if wrapped to first permutation, true otherwise.
2942 *
2943 * Treats all permutations of the range as a set of @e dictionary sorted
2944 * sequences. Permutes the current sequence into the next one of this set.
2945 * Returns true if there are more sequences to generate. If the sequence
2946 * is the largest of the set, the smallest is generated and false returned.
2947 */
2948 template<typename _BidirectionalIterator>
2949 _GLIBCXX20_CONSTEXPR
2950 inline bool
2951 next_permutation(_BidirectionalIterator __first,
2953 {
2954 // concept requirements
2955 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2957 __glibcxx_function_requires(_LessThanComparableConcept<
2959 __glibcxx_requires_valid_range(__first, __last);
2960 __glibcxx_requires_irreflexive(__first, __last);
2961
2962 return std::__next_permutation
2963 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2964 }
2965
2966 /**
2967 * @brief Permute range into the next @e dictionary ordering using
2968 * comparison functor.
2969 * @ingroup sorting_algorithms
2970 * @param __first Start of range.
2971 * @param __last End of range.
2972 * @param __comp A comparison functor.
2973 * @return False if wrapped to first permutation, true otherwise.
2974 *
2975 * Treats all permutations of the range [__first,__last) as a set of
2976 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
2977 * sequence into the next one of this set. Returns true if there are more
2978 * sequences to generate. If the sequence is the largest of the set, the
2979 * smallest is generated and false returned.
2980 */
2981 template<typename _BidirectionalIterator, typename _Compare>
2982 _GLIBCXX20_CONSTEXPR
2983 inline bool
2984 next_permutation(_BidirectionalIterator __first,
2985 _BidirectionalIterator __last, _Compare __comp)
2986 {
2987 // concept requirements
2988 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2990 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2993 __glibcxx_requires_valid_range(__first, __last);
2994 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2995
2996 return std::__next_permutation
2997 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2998 }
2999
3000 template<typename _BidirectionalIterator, typename _Compare>
3001 _GLIBCXX20_CONSTEXPR
3002 bool
3003 __prev_permutation(_BidirectionalIterator __first,
3004 _BidirectionalIterator __last, _Compare __comp)
3005 {
3006 if (__first == __last)
3007 return false;
3008 _BidirectionalIterator __i = __first;
3009 ++__i;
3010 if (__i == __last)
3011 return false;
3012 __i = __last;
3013 --__i;
3014
3015 for(;;)
3016 {
3017 _BidirectionalIterator __ii = __i;
3018 --__i;
3019 if (__comp(__ii, __i))
3020 {
3021 _BidirectionalIterator __j = __last;
3022 while (!__comp(--__j, __i))
3023 {}
3024 std::iter_swap(__i, __j);
3025 std::__reverse(__ii, __last,
3026 std::__iterator_category(__first));
3027 return true;
3028 }
3029 if (__i == __first)
3030 {
3031 std::__reverse(__first, __last,
3032 std::__iterator_category(__first));
3033 return false;
3034 }
3035 }
3036 }
3037
3038 /**
3039 * @brief Permute range into the previous @e dictionary ordering.
3040 * @ingroup sorting_algorithms
3041 * @param __first Start of range.
3042 * @param __last End of range.
3043 * @return False if wrapped to last permutation, true otherwise.
3044 *
3045 * Treats all permutations of the range as a set of @e dictionary sorted
3046 * sequences. Permutes the current sequence into the previous one of this
3047 * set. Returns true if there are more sequences to generate. If the
3048 * sequence is the smallest of the set, the largest is generated and false
3049 * returned.
3050 */
3051 template<typename _BidirectionalIterator>
3052 _GLIBCXX20_CONSTEXPR
3053 inline bool
3054 prev_permutation(_BidirectionalIterator __first,
3056 {
3057 // concept requirements
3058 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3060 __glibcxx_function_requires(_LessThanComparableConcept<
3062 __glibcxx_requires_valid_range(__first, __last);
3063 __glibcxx_requires_irreflexive(__first, __last);
3064
3065 return std::__prev_permutation(__first, __last,
3066 __gnu_cxx::__ops::__iter_less_iter());
3067 }
3068
3069 /**
3070 * @brief Permute range into the previous @e dictionary ordering using
3071 * comparison functor.
3072 * @ingroup sorting_algorithms
3073 * @param __first Start of range.
3074 * @param __last End of range.
3075 * @param __comp A comparison functor.
3076 * @return False if wrapped to last permutation, true otherwise.
3077 *
3078 * Treats all permutations of the range [__first,__last) as a set of
3079 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3080 * sequence into the previous one of this set. Returns true if there are
3081 * more sequences to generate. If the sequence is the smallest of the set,
3082 * the largest is generated and false returned.
3083 */
3084 template<typename _BidirectionalIterator, typename _Compare>
3085 _GLIBCXX20_CONSTEXPR
3086 inline bool
3087 prev_permutation(_BidirectionalIterator __first,
3088 _BidirectionalIterator __last, _Compare __comp)
3089 {
3090 // concept requirements
3091 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3093 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3096 __glibcxx_requires_valid_range(__first, __last);
3097 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3098
3099 return std::__prev_permutation(__first, __last,
3100 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3101 }
3102
3103 // replace
3104 // replace_if
3105
3106 template<typename _InputIterator, typename _OutputIterator,
3107 typename _Predicate, typename _Tp>
3108 _GLIBCXX20_CONSTEXPR
3109 _OutputIterator
3110 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3111 _OutputIterator __result,
3112 _Predicate __pred, const _Tp& __new_value)
3113 {
3114 for (; __first != __last; ++__first, (void)++__result)
3115 if (__pred(__first))
3116 *__result = __new_value;
3117 else
3118 *__result = *__first;
3119 return __result;
3120 }
3121
3122 /**
3123 * @brief Copy a sequence, replacing each element of one value with another
3124 * value.
3125 * @param __first An input iterator.
3126 * @param __last An input iterator.
3127 * @param __result An output iterator.
3128 * @param __old_value The value to be replaced.
3129 * @param __new_value The replacement value.
3130 * @return The end of the output sequence, @p result+(last-first).
3131 *
3132 * Copies each element in the input range @p [__first,__last) to the
3133 * output range @p [__result,__result+(__last-__first)) replacing elements
3134 * equal to @p __old_value with @p __new_value.
3135 */
3136 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3137 _GLIBCXX20_CONSTEXPR
3138 inline _OutputIterator
3139 replace_copy(_InputIterator __first, _InputIterator __last,
3140 _OutputIterator __result,
3141 const _Tp& __old_value, const _Tp& __new_value)
3142 {
3143 // concept requirements
3144 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3145 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3147 __glibcxx_function_requires(_EqualOpConcept<
3149 __glibcxx_requires_valid_range(__first, __last);
3150
3151 return std::__replace_copy_if(__first, __last, __result,
3152 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3153 __new_value);
3154 }
3155
3156 /**
3157 * @brief Copy a sequence, replacing each value for which a predicate
3158 * returns true with another value.
3159 * @ingroup mutating_algorithms
3160 * @param __first An input iterator.
3161 * @param __last An input iterator.
3162 * @param __result An output iterator.
3163 * @param __pred A predicate.
3164 * @param __new_value The replacement value.
3165 * @return The end of the output sequence, @p __result+(__last-__first).
3166 *
3167 * Copies each element in the range @p [__first,__last) to the range
3168 * @p [__result,__result+(__last-__first)) replacing elements for which
3169 * @p __pred returns true with @p __new_value.
3170 */
3171 template<typename _InputIterator, typename _OutputIterator,
3172 typename _Predicate, typename _Tp>
3173 _GLIBCXX20_CONSTEXPR
3174 inline _OutputIterator
3175 replace_copy_if(_InputIterator __first, _InputIterator __last,
3176 _OutputIterator __result,
3177 _Predicate __pred, const _Tp& __new_value)
3178 {
3179 // concept requirements
3180 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3181 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3183 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3185 __glibcxx_requires_valid_range(__first, __last);
3186
3187 return std::__replace_copy_if(__first, __last, __result,
3188 __gnu_cxx::__ops::__pred_iter(__pred),
3189 __new_value);
3190 }
3191
3192#if __cplusplus >= 201103L
3193 /**
3194 * @brief Determines whether the elements of a sequence are sorted.
3195 * @ingroup sorting_algorithms
3196 * @param __first An iterator.
3197 * @param __last Another iterator.
3198 * @return True if the elements are sorted, false otherwise.
3199 */
3200 template<typename _ForwardIterator>
3201 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3202 inline bool
3203 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3204 { return std::is_sorted_until(__first, __last) == __last; }
3205
3206 /**
3207 * @brief Determines whether the elements of a sequence are sorted
3208 * according to a comparison functor.
3209 * @ingroup sorting_algorithms
3210 * @param __first An iterator.
3211 * @param __last Another iterator.
3212 * @param __comp A comparison functor.
3213 * @return True if the elements are sorted, false otherwise.
3214 */
3215 template<typename _ForwardIterator, typename _Compare>
3216 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3217 inline bool
3218 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3219 _Compare __comp)
3220 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3221
3222 template<typename _ForwardIterator, typename _Compare>
3223 _GLIBCXX20_CONSTEXPR
3224 _ForwardIterator
3225 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3226 _Compare __comp)
3227 {
3228 if (__first == __last)
3229 return __last;
3230
3231 _ForwardIterator __next = __first;
3232 for (++__next; __next != __last; __first = __next, (void)++__next)
3233 if (__comp(__next, __first))
3234 return __next;
3235 return __next;
3236 }
3237
3238 /**
3239 * @brief Determines the end of a sorted sequence.
3240 * @ingroup sorting_algorithms
3241 * @param __first An iterator.
3242 * @param __last Another iterator.
3243 * @return An iterator pointing to the last iterator i in [__first, __last)
3244 * for which the range [__first, i) is sorted.
3245 */
3246 template<typename _ForwardIterator>
3247 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3248 inline _ForwardIterator
3249 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3250 {
3251 // concept requirements
3252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3253 __glibcxx_function_requires(_LessThanComparableConcept<
3255 __glibcxx_requires_valid_range(__first, __last);
3256 __glibcxx_requires_irreflexive(__first, __last);
3257
3258 return std::__is_sorted_until(__first, __last,
3259 __gnu_cxx::__ops::__iter_less_iter());
3260 }
3261
3262 /**
3263 * @brief Determines the end of a sorted sequence using comparison functor.
3264 * @ingroup sorting_algorithms
3265 * @param __first An iterator.
3266 * @param __last Another iterator.
3267 * @param __comp A comparison functor.
3268 * @return An iterator pointing to the last iterator i in [__first, __last)
3269 * for which the range [__first, i) is sorted.
3270 */
3271 template<typename _ForwardIterator, typename _Compare>
3272 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3273 inline _ForwardIterator
3274 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3275 _Compare __comp)
3276 {
3277 // concept requirements
3278 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3279 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3282 __glibcxx_requires_valid_range(__first, __last);
3283 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3284
3285 return std::__is_sorted_until(__first, __last,
3286 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3287 }
3288
3289 /**
3290 * @brief Determines min and max at once as an ordered pair.
3291 * @ingroup sorting_algorithms
3292 * @param __a A thing of arbitrary type.
3293 * @param __b Another thing of arbitrary type.
3294 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3295 * __b) otherwise.
3296 */
3297 template<typename _Tp>
3298 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3299 inline pair<const _Tp&, const _Tp&>
3300 minmax(const _Tp& __a, const _Tp& __b)
3301 {
3302 // concept requirements
3303 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3304
3306 : pair<const _Tp&, const _Tp&>(__a, __b);
3307 }
3308
3309 /**
3310 * @brief Determines min and max at once as an ordered pair.
3311 * @ingroup sorting_algorithms
3312 * @param __a A thing of arbitrary type.
3313 * @param __b Another thing of arbitrary type.
3314 * @param __comp A @link comparison_functors comparison functor @endlink.
3315 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3316 * __b) otherwise.
3317 */
3318 template<typename _Tp, typename _Compare>
3319 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3320 inline pair<const _Tp&, const _Tp&>
3321 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3322 {
3323 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3324 : pair<const _Tp&, const _Tp&>(__a, __b);
3325 }
3326
3327 template<typename _ForwardIterator, typename _Compare>
3328 _GLIBCXX14_CONSTEXPR
3329 pair<_ForwardIterator, _ForwardIterator>
3330 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3331 _Compare __comp)
3332 {
3333 _ForwardIterator __next = __first;
3334 if (__first == __last
3335 || ++__next == __last)
3336 return std::make_pair(__first, __first);
3337
3338 _ForwardIterator __min{}, __max{};
3339 if (__comp(__next, __first))
3340 {
3341 __min = __next;
3342 __max = __first;
3343 }
3344 else
3345 {
3346 __min = __first;
3347 __max = __next;
3348 }
3349
3350 __first = __next;
3351 ++__first;
3352
3353 while (__first != __last)
3354 {
3355 __next = __first;
3356 if (++__next == __last)
3357 {
3358 if (__comp(__first, __min))
3359 __min = __first;
3360 else if (!__comp(__first, __max))
3361 __max = __first;
3362 break;
3363 }
3364
3365 if (__comp(__next, __first))
3366 {
3367 if (__comp(__next, __min))
3368 __min = __next;
3369 if (!__comp(__first, __max))
3370 __max = __first;
3371 }
3372 else
3373 {
3374 if (__comp(__first, __min))
3375 __min = __first;
3376 if (!__comp(__next, __max))
3377 __max = __next;
3378 }
3379
3380 __first = __next;
3381 ++__first;
3382 }
3383
3384 return std::make_pair(__min, __max);
3385 }
3386
3387 /**
3388 * @brief Return a pair of iterators pointing to the minimum and maximum
3389 * elements in a range.
3390 * @ingroup sorting_algorithms
3391 * @param __first Start of range.
3392 * @param __last End of range.
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>
3399 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3400 inline pair<_ForwardIterator, _ForwardIterator>
3401 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3402 {
3403 // concept requirements
3404 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3405 __glibcxx_function_requires(_LessThanComparableConcept<
3407 __glibcxx_requires_valid_range(__first, __last);
3408 __glibcxx_requires_irreflexive(__first, __last);
3409
3410 return std::__minmax_element(__first, __last,
3411 __gnu_cxx::__ops::__iter_less_iter());
3412 }
3413
3414 /**
3415 * @brief Return a pair of iterators pointing to the minimum and maximum
3416 * elements in a range.
3417 * @ingroup sorting_algorithms
3418 * @param __first Start of range.
3419 * @param __last End of range.
3420 * @param __comp Comparison functor.
3421 * @return make_pair(m, M), where m is the first iterator i in
3422 * [__first, __last) such that no other element in the range is
3423 * smaller, and where M is the last iterator i in [__first, __last)
3424 * such that no other element in the range is larger.
3425 */
3426 template<typename _ForwardIterator, typename _Compare>
3427 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3428 inline pair<_ForwardIterator, _ForwardIterator>
3429 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3430 _Compare __comp)
3431 {
3432 // concept requirements
3433 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3437 __glibcxx_requires_valid_range(__first, __last);
3438 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3439
3440 return std::__minmax_element(__first, __last,
3441 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3442 }
3443
3444 template<typename _Tp>
3445 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3446 inline pair<_Tp, _Tp>
3447 minmax(initializer_list<_Tp> __l)
3448 {
3449 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3450 pair<const _Tp*, const _Tp*> __p =
3451 std::__minmax_element(__l.begin(), __l.end(),
3452 __gnu_cxx::__ops::__iter_less_iter());
3453 return std::make_pair(*__p.first, *__p.second);
3454 }
3455
3456 template<typename _Tp, typename _Compare>
3457 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3458 inline pair<_Tp, _Tp>
3459 minmax(initializer_list<_Tp> __l, _Compare __comp)
3460 {
3461 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3462 pair<const _Tp*, const _Tp*> __p =
3463 std::__minmax_element(__l.begin(), __l.end(),
3464 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3465 return std::make_pair(*__p.first, *__p.second);
3466 }
3467
3468 /**
3469 * @brief Checks whether a permutation of the second sequence is equal
3470 * to the first sequence.
3471 * @ingroup non_mutating_algorithms
3472 * @param __first1 Start of first range.
3473 * @param __last1 End of first range.
3474 * @param __first2 Start of second range.
3475 * @param __pred A binary predicate.
3476 * @return true if there exists a permutation of the elements in
3477 * the range [__first2, __first2 + (__last1 - __first1)),
3478 * beginning with ForwardIterator2 begin, such that
3479 * equal(__first1, __last1, __begin, __pred) returns true;
3480 * otherwise, returns false.
3481 */
3482 template<typename _ForwardIterator1, typename _ForwardIterator2,
3483 typename _BinaryPredicate>
3484 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3485 inline bool
3488 {
3489 // concept requirements
3490 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3491 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3492 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3495 __glibcxx_requires_valid_range(__first1, __last1);
3496
3497 return std::__is_permutation(__first1, __last1, __first2,
3498 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3499 }
3500
3501#if __cplusplus > 201103L
3502#pragma GCC diagnostic push
3503#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
3504 template<typename _ForwardIterator1, typename _ForwardIterator2,
3505 typename _BinaryPredicate>
3506 _GLIBCXX20_CONSTEXPR
3507 bool
3508 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3509 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3510 _BinaryPredicate __pred)
3511 {
3512 using _Cat1
3513 = typename iterator_traits<_ForwardIterator1>::iterator_category;
3514 using _Cat2
3515 = typename iterator_traits<_ForwardIterator2>::iterator_category;
3516 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3517 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3518 constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
3519 if constexpr (__ra_iters)
3520 {
3521 if ((__last1 - __first1) != (__last2 - __first2))
3522 return false;
3523 }
3524
3525 // Efficiently compare identical prefixes: O(N) if sequences
3526 // have the same elements in the same order.
3527 for (; __first1 != __last1 && __first2 != __last2;
3528 ++__first1, (void)++__first2)
3529 if (!__pred(__first1, __first2))
3530 break;
3531
3532 if constexpr (__ra_iters)
3533 {
3534 if (__first1 == __last1)
3535 return true;
3536 }
3537 else
3538 {
3539 auto __d1 = std::distance(__first1, __last1);
3540 auto __d2 = std::distance(__first2, __last2);
3541 if (__d1 == 0 && __d2 == 0)
3542 return true;
3543 if (__d1 != __d2)
3544 return false;
3545 }
3546
3547 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3548 {
3549 if (__scan != std::__find_if(__first1, __scan,
3550 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3551 continue; // We've seen this one before.
3552
3553 auto __matches = std::__count_if(__first2, __last2,
3554 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3555 if (0 == __matches
3556 || std::__count_if(__scan, __last1,
3557 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3558 != __matches)
3559 return false;
3560 }
3561 return true;
3562 }
3563#pragma GCC diagnostic pop
3564
3565 /**
3566 * @brief Checks whether a permutaion of the second sequence is equal
3567 * to the first sequence.
3568 * @ingroup non_mutating_algorithms
3569 * @param __first1 Start of first range.
3570 * @param __last1 End of first range.
3571 * @param __first2 Start of second range.
3572 * @param __last2 End of first range.
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) returns true;
3576 * otherwise, returns false.
3577 */
3578 template<typename _ForwardIterator1, typename _ForwardIterator2>
3579 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3580 inline bool
3583 {
3584 __glibcxx_requires_valid_range(__first1, __last1);
3585 __glibcxx_requires_valid_range(__first2, __last2);
3586
3587 return
3588 std::__is_permutation(__first1, __last1, __first2, __last2,
3589 __gnu_cxx::__ops::__iter_equal_to_iter());
3590 }
3591
3592 /**
3593 * @brief Checks whether a permutation of the second sequence is equal
3594 * to the first sequence.
3595 * @ingroup non_mutating_algorithms
3596 * @param __first1 Start of first range.
3597 * @param __last1 End of first range.
3598 * @param __first2 Start of second range.
3599 * @param __last2 End of first range.
3600 * @param __pred A binary predicate.
3601 * @return true if there exists a permutation of the elements in the range
3602 * [__first2, __last2), beginning with ForwardIterator2 begin,
3603 * such that equal(__first1, __last1, __begin, __pred) returns true;
3604 * otherwise, returns false.
3605 */
3606 template<typename _ForwardIterator1, typename _ForwardIterator2,
3607 typename _BinaryPredicate>
3608 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3609 inline bool
3613 {
3614 __glibcxx_requires_valid_range(__first1, __last1);
3615 __glibcxx_requires_valid_range(__first2, __last2);
3616
3617 return std::__is_permutation(__first1, __last1, __first2, __last2,
3618 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3619 }
3620#endif // C++14
3621
3622#ifdef __glibcxx_clamp // C++ >= 17
3623 /**
3624 * @brief Returns the value clamped between lo and hi.
3625 * @ingroup sorting_algorithms
3626 * @param __val A value of arbitrary type.
3627 * @param __lo A lower limit of arbitrary type.
3628 * @param __hi An upper limit of arbitrary type.
3629 * @retval `__lo` if `__val < __lo`
3630 * @retval `__hi` if `__hi < __val`
3631 * @retval `__val` otherwise.
3632 * @pre `_Tp` is LessThanComparable and `(__hi < __lo)` is false.
3633 */
3634 template<typename _Tp>
3635 [[nodiscard]] constexpr const _Tp&
3636 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
3637 {
3638 __glibcxx_assert(!(__hi < __lo));
3639 return std::min(std::max(__val, __lo), __hi);
3640 }
3641
3642 /**
3643 * @brief Returns the value clamped between lo and hi.
3644 * @ingroup sorting_algorithms
3645 * @param __val A value of arbitrary type.
3646 * @param __lo A lower limit of arbitrary type.
3647 * @param __hi An upper limit of arbitrary type.
3648 * @param __comp A comparison functor.
3649 * @retval `__lo` if `__comp(__val, __lo)`
3650 * @retval `__hi` if `__comp(__hi, __val)`
3651 * @retval `__val` otherwise.
3652 * @pre `__comp(__hi, __lo)` is false.
3653 */
3654 template<typename _Tp, typename _Compare>
3655 [[nodiscard]] constexpr const _Tp&
3656 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
3657 {
3658 __glibcxx_assert(!__comp(__hi, __lo));
3659 return std::min(std::max(__val, __lo, __comp), __hi, __comp);
3660 }
3661#endif // __glibcxx_clamp
3662
3663 /**
3664 * @brief Generate two uniformly distributed integers using a
3665 * single distribution invocation.
3666 * @param __b0 The upper bound for the first integer.
3667 * @param __b1 The upper bound for the second integer.
3668 * @param __g A UniformRandomBitGenerator.
3669 * @return A pair (i, j) with i and j uniformly distributed
3670 * over [0, __b0) and [0, __b1), respectively.
3671 *
3672 * Requires: __b0 * __b1 <= __g.max() - __g.min().
3673 *
3674 * Using uniform_int_distribution with a range that is very
3675 * small relative to the range of the generator ends up wasting
3676 * potentially expensively generated randomness, since
3677 * uniform_int_distribution does not store leftover randomness
3678 * between invocations.
3679 *
3680 * If we know we want two integers in ranges that are sufficiently
3681 * small, we can compose the ranges, use a single distribution
3682 * invocation, and significantly reduce the waste.
3683 */
3684 template<typename _IntType, typename _UniformRandomBitGenerator>
3685 pair<_IntType, _IntType>
3688 {
3689 _IntType __x
3691 return std::make_pair(__x / __b1, __x % __b1);
3692 }
3693
3694 /**
3695 * @brief Shuffle the elements of a sequence using a uniform random
3696 * number generator.
3697 * @ingroup mutating_algorithms
3698 * @param __first A forward iterator.
3699 * @param __last A forward iterator.
3700 * @param __g A UniformRandomNumberGenerator (26.5.1.3).
3701 * @return Nothing.
3702 *
3703 * Reorders the elements in the range @p [__first,__last) using @p __g to
3704 * provide random numbers.
3705 */
3706 template<typename _RandomAccessIterator,
3707 typename _UniformRandomNumberGenerator>
3708 void
3711 {
3712 // concept requirements
3713 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3715 __glibcxx_requires_valid_range(__first, __last);
3716
3717 if (__first == __last)
3718 return;
3719
3722
3723 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3725 typedef typename __distr_type::param_type __p_type;
3726
3727 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3728 _Gen;
3730 __uc_type;
3731
3732 const __uc_type __urngrange = __g.max() - __g.min();
3733 const __uc_type __urange = __uc_type(__last - __first);
3734
3735 if (__urngrange / __urange >= __urange)
3736 // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
3737 {
3738 _RandomAccessIterator __i = __first + 1;
3739
3740 // Since we know the range isn't empty, an even number of elements
3741 // means an uneven number of elements /to swap/, in which case we
3742 // do the first one up front:
3743
3744 if ((__urange % 2) == 0)
3745 {
3746 __distr_type __d{0, 1};
3747 std::iter_swap(__i++, __first + __d(__g));
3748 }
3749
3750 // Now we know that __last - __i is even, so we do the rest in pairs,
3751 // using a single distribution invocation to produce swap positions
3752 // for two successive elements at a time:
3753
3754 while (__i != __last)
3755 {
3756 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3757
3760
3761 std::iter_swap(__i++, __first + __pospos.first);
3762 std::iter_swap(__i++, __first + __pospos.second);
3763 }
3764
3765 return;
3766 }
3767
3768 __distr_type __d;
3769
3770 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3771 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3772 }
3773#endif // C++11
3774
3775_GLIBCXX_BEGIN_NAMESPACE_ALGO
3776
3777 /**
3778 * @brief Apply a function to every element of a sequence.
3779 * @ingroup non_mutating_algorithms
3780 * @param __first An input iterator.
3781 * @param __last An input iterator.
3782 * @param __f A unary function object.
3783 * @return @p __f
3784 *
3785 * Applies the function object @p __f to each element in the range
3786 * @p [first,last). @p __f must not modify the order of the sequence.
3787 * If @p __f has a return value it is ignored.
3788 */
3789 template<typename _InputIterator, typename _Function>
3790 _GLIBCXX20_CONSTEXPR
3791 _Function
3792 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3793 {
3794 // concept requirements
3795 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3796 __glibcxx_requires_valid_range(__first, __last);
3797 for (; __first != __last; ++__first)
3798 __f(*__first);
3799 return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3800 }
3801
3802#if __cplusplus >= 201703L
3803 /**
3804 * @brief Apply a function to every element of a sequence.
3805 * @ingroup non_mutating_algorithms
3806 * @param __first An input iterator.
3807 * @param __n A value convertible to an integer.
3808 * @param __f A unary function object.
3809 * @return `__first+__n`
3810 *
3811 * Applies the function object `__f` to each element in the range
3812 * `[first, first+n)`. `__f` must not modify the order of the sequence.
3813 * If `__f` has a return value it is ignored.
3814 */
3815 template<typename _InputIterator, typename _Size, typename _Function>
3816 _GLIBCXX20_CONSTEXPR
3817 _InputIterator
3818 for_each_n(_InputIterator __first, _Size __n, _Function __f)
3819 {
3820 auto __n2 = std::__size_to_integer(__n);
3823 {
3824 if (__n2 <= 0)
3825 return __first;
3826 auto __last = __first + __n2;
3827 std::for_each(__first, __last, std::move(__f));
3828 return __last;
3829 }
3830 else
3831 {
3832 while (__n2-->0)
3833 {
3834 __f(*__first);
3835 ++__first;
3836 }
3837 return __first;
3838 }
3839 }
3840#endif // C++17
3841
3842 /**
3843 * @brief Find the first occurrence of a value in a sequence.
3844 * @ingroup non_mutating_algorithms
3845 * @param __first An input iterator.
3846 * @param __last An input iterator.
3847 * @param __val The value to find.
3848 * @return The first iterator @c i in the range @p [__first,__last)
3849 * such that @c *i == @p __val, or @p __last if no such iterator exists.
3850 */
3851 template<typename _InputIterator, typename _Tp>
3852 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3853 inline _InputIterator
3854 find(_InputIterator __first, _InputIterator __last, const _Tp& __val)
3855 {
3856 // concept requirements
3857 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3858 __glibcxx_function_requires(_EqualOpConcept<
3860 __glibcxx_requires_valid_range(__first, __last);
3861
3862#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
3865 if constexpr (is_pointer_v<decltype(std::__niter_base(__first))>
3866#if __glibcxx_concepts && __glibcxx_to_address
3868#endif
3869 )
3870 {
3871 // If conversion to the 1-byte value_type alters the value,
3872 // it would not be found by std::find using equality comparison.
3873 // We need to check this here, because otherwise something like
3874 // memchr("a", 'a'+256, 1) would give a false positive match.
3875 if (!(static_cast<_ValT>(__val) == __val))
3876 return __last;
3877 else if (!__is_constant_evaluated())
3878 {
3879 const int __ival = static_cast<int>(__val);
3880 if (auto __n = __last - __first; __n > 0)
3881 {
3882#if __glibcxx_concepts && __glibcxx_to_address
3883 const void* __p0 = std::to_address(__first);
3884#else
3885 const void* __p0 = std::__niter_base(__first);
3886#endif
3887 if (auto __p1 = __builtin_memchr(__p0, __ival, __n))
3888 return __first + ((const char*)__p1 - (const char*)__p0);
3889 }
3890 return __last;
3891 }
3892 }
3893#endif
3894
3895 return std::__find_if(__first, __last,
3896 __gnu_cxx::__ops::__iter_equals_val(__val));
3897 }
3898
3899 /**
3900 * @brief Find the first element in a sequence for which a
3901 * predicate is true.
3902 * @ingroup non_mutating_algorithms
3903 * @param __first An input iterator.
3904 * @param __last An input iterator.
3905 * @param __pred A predicate.
3906 * @return The first iterator @c i in the range @p [__first,__last)
3907 * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3908 */
3909 template<typename _InputIterator, typename _Predicate>
3910 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3911 inline _InputIterator
3912 find_if(_InputIterator __first, _InputIterator __last,
3913 _Predicate __pred)
3914 {
3915 // concept requirements
3916 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3917 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3919 __glibcxx_requires_valid_range(__first, __last);
3920
3921 return std::__find_if(__first, __last,
3922 __gnu_cxx::__ops::__pred_iter(__pred));
3923 }
3924
3925 /**
3926 * @brief Find element from a set in a sequence.
3927 * @ingroup non_mutating_algorithms
3928 * @param __first1 Start of range to search.
3929 * @param __last1 End of range to search.
3930 * @param __first2 Start of match candidates.
3931 * @param __last2 End of match candidates.
3932 * @return The first iterator @c i in the range
3933 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3934 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3935 *
3936 * Searches the range @p [__first1,__last1) for an element that is
3937 * equal to some element in the range [__first2,__last2). If
3938 * found, returns an iterator in the range [__first1,__last1),
3939 * otherwise returns @p __last1.
3940 */
3941 template<typename _InputIterator, typename _ForwardIterator>
3942 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3943 _InputIterator
3946 {
3947 // concept requirements
3948 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3949 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3950 __glibcxx_function_requires(_EqualOpConcept<
3953 __glibcxx_requires_valid_range(__first1, __last1);
3954 __glibcxx_requires_valid_range(__first2, __last2);
3955
3956 for (; __first1 != __last1; ++__first1)
3957 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3958 if (*__first1 == *__iter)
3959 return __first1;
3960 return __last1;
3961 }
3962
3963 /**
3964 * @brief Find element from a set in a sequence using a predicate.
3965 * @ingroup non_mutating_algorithms
3966 * @param __first1 Start of range to search.
3967 * @param __last1 End of range to search.
3968 * @param __first2 Start of match candidates.
3969 * @param __last2 End of match candidates.
3970 * @param __comp Predicate to use.
3971 * @return The first iterator @c i in the range
3972 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
3973 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3974 * such iterator exists.
3975 *
3976
3977 * Searches the range @p [__first1,__last1) for an element that is
3978 * equal to some element in the range [__first2,__last2). If
3979 * found, returns an iterator in the range [__first1,__last1),
3980 * otherwise returns @p __last1.
3981 */
3982 template<typename _InputIterator, typename _ForwardIterator,
3983 typename _BinaryPredicate>
3984 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3985 _InputIterator
3988 _BinaryPredicate __comp)
3989 {
3990 // concept requirements
3991 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3992 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3993 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3996 __glibcxx_requires_valid_range(__first1, __last1);
3997 __glibcxx_requires_valid_range(__first2, __last2);
3998
3999 for (; __first1 != __last1; ++__first1)
4000 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4001 if (__comp(*__first1, *__iter))
4002 return __first1;
4003 return __last1;
4004 }
4005
4006 /**
4007 * @brief Find two adjacent values in a sequence that are equal.
4008 * @ingroup non_mutating_algorithms
4009 * @param __first A forward iterator.
4010 * @param __last A forward iterator.
4011 * @return The first iterator @c i such that @c i and @c i+1 are both
4012 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4013 * or @p __last if no such iterator exists.
4014 */
4015 template<typename _ForwardIterator>
4016 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4017 inline _ForwardIterator
4018 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4019 {
4020 // concept requirements
4021 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4022 __glibcxx_function_requires(_EqualityComparableConcept<
4024 __glibcxx_requires_valid_range(__first, __last);
4025
4026 return std::__adjacent_find(__first, __last,
4027 __gnu_cxx::__ops::__iter_equal_to_iter());
4028 }
4029
4030 /**
4031 * @brief Find two adjacent values in a sequence using a predicate.
4032 * @ingroup non_mutating_algorithms
4033 * @param __first A forward iterator.
4034 * @param __last A forward iterator.
4035 * @param __binary_pred A binary predicate.
4036 * @return The first iterator @c i such that @c i and @c i+1 are both
4037 * valid iterators in @p [__first,__last) and such that
4038 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4039 * exists.
4040 */
4041 template<typename _ForwardIterator, typename _BinaryPredicate>
4042 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4043 inline _ForwardIterator
4044 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4046 {
4047 // concept requirements
4048 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4049 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4052 __glibcxx_requires_valid_range(__first, __last);
4053
4054 return std::__adjacent_find(__first, __last,
4055 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4056 }
4057
4058 /**
4059 * @brief Count the number of copies of a value in a sequence.
4060 * @ingroup non_mutating_algorithms
4061 * @param __first An input iterator.
4062 * @param __last An input iterator.
4063 * @param __value The value to be counted.
4064 * @return The number of iterators @c i in the range @p [__first,__last)
4065 * for which @c *i == @p __value
4066 */
4067 template<typename _InputIterator, typename _Tp>
4068 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4069 inline typename iterator_traits<_InputIterator>::difference_type
4070 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4071 {
4072 // concept requirements
4073 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4074 __glibcxx_function_requires(_EqualOpConcept<
4076 __glibcxx_requires_valid_range(__first, __last);
4077
4078 return std::__count_if(__first, __last,
4079 __gnu_cxx::__ops::__iter_equals_val(__value));
4080 }
4081
4082 /**
4083 * @brief Count the elements of a sequence for which a predicate is true.
4084 * @ingroup non_mutating_algorithms
4085 * @param __first An input iterator.
4086 * @param __last An input iterator.
4087 * @param __pred A predicate.
4088 * @return The number of iterators @c i in the range @p [__first,__last)
4089 * for which @p __pred(*i) is true.
4090 */
4091 template<typename _InputIterator, typename _Predicate>
4092 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4093 inline typename iterator_traits<_InputIterator>::difference_type
4094 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4095 {
4096 // concept requirements
4097 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4098 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4100 __glibcxx_requires_valid_range(__first, __last);
4101
4102 return std::__count_if(__first, __last,
4103 __gnu_cxx::__ops::__pred_iter(__pred));
4104 }
4105
4106 /**
4107 * @brief Search a sequence for a matching sub-sequence.
4108 * @ingroup non_mutating_algorithms
4109 * @param __first1 A forward iterator.
4110 * @param __last1 A forward iterator.
4111 * @param __first2 A forward iterator.
4112 * @param __last2 A forward iterator.
4113 * @return The first iterator @c i in the range @p
4114 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4115 * *(__first2+N) for each @c N in the range @p
4116 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4117 *
4118 * Searches the range @p [__first1,__last1) for a sub-sequence that
4119 * compares equal value-by-value with the sequence given by @p
4120 * [__first2,__last2) and returns an iterator to the first element
4121 * of the sub-sequence, or @p __last1 if the sub-sequence is not
4122 * found.
4123 *
4124 * Because the sub-sequence must lie completely within the range @p
4125 * [__first1,__last1) it must start at a position less than @p
4126 * __last1-(__last2-__first2) where @p __last2-__first2 is the
4127 * length of the sub-sequence.
4128 *
4129 * This means that the returned iterator @c i will be in the range
4130 * @p [__first1,__last1-(__last2-__first2))
4131 */
4132 template<typename _ForwardIterator1, typename _ForwardIterator2>
4133 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4134 inline _ForwardIterator1
4137 {
4138 // concept requirements
4139 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4140 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4141 __glibcxx_function_requires(_EqualOpConcept<
4144 __glibcxx_requires_valid_range(__first1, __last1);
4145 __glibcxx_requires_valid_range(__first2, __last2);
4146
4147 return std::__search(__first1, __last1, __first2, __last2,
4148 __gnu_cxx::__ops::__iter_equal_to_iter());
4149 }
4150
4151 /**
4152 * @brief Search a sequence for a number of consecutive values.
4153 * @ingroup non_mutating_algorithms
4154 * @param __first A forward iterator.
4155 * @param __last A forward iterator.
4156 * @param __count The number of consecutive values.
4157 * @param __val The value to find.
4158 * @return The first iterator @c i in the range @p
4159 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4160 * each @c N in the range @p [0,__count), or @p __last if no such
4161 * iterator exists.
4162 *
4163 * Searches the range @p [__first,__last) for @p count consecutive elements
4164 * equal to @p __val.
4165 */
4166 template<typename _ForwardIterator, typename _Integer, typename _Tp>
4167 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4168 inline _ForwardIterator
4169 search_n(_ForwardIterator __first, _ForwardIterator __last,
4170 _Integer __count, const _Tp& __val)
4171 {
4172 // concept requirements
4173 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4174 __glibcxx_function_requires(_EqualOpConcept<
4176 __glibcxx_requires_valid_range(__first, __last);
4177
4178 return std::__search_n(__first, __last, __count,
4179 __gnu_cxx::__ops::__iter_equals_val(__val));
4180 }
4181
4182
4183 /**
4184 * @brief Search a sequence for a number of consecutive values using a
4185 * predicate.
4186 * @ingroup non_mutating_algorithms
4187 * @param __first A forward iterator.
4188 * @param __last A forward iterator.
4189 * @param __count The number of consecutive values.
4190 * @param __val The value to find.
4191 * @param __binary_pred A binary predicate.
4192 * @return The first iterator @c i in the range @p
4193 * [__first,__last-__count) such that @p
4194 * __binary_pred(*(i+N),__val) is true for each @c N in the range
4195 * @p [0,__count), or @p __last if no such iterator exists.
4196 *
4197 * Searches the range @p [__first,__last) for @p __count
4198 * consecutive elements for which the predicate returns true.
4199 */
4200 template<typename _ForwardIterator, typename _Integer, typename _Tp,
4201 typename _BinaryPredicate>
4202 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4203 inline _ForwardIterator
4204 search_n(_ForwardIterator __first, _ForwardIterator __last,
4205 _Integer __count, const _Tp& __val,
4207 {
4208 // concept requirements
4209 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4210 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4212 __glibcxx_requires_valid_range(__first, __last);
4213
4214 return std::__search_n(__first, __last, __count,
4215 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4216 }
4217
4218#if __cplusplus >= 201703L
4219 /** @brief Search a sequence using a Searcher object.
4220 *
4221 * @param __first A forward iterator.
4222 * @param __last A forward iterator.
4223 * @param __searcher A callable object.
4224 * @return @p __searcher(__first,__last).first
4225 */
4226 template<typename _ForwardIterator, typename _Searcher>
4227 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4228 inline _ForwardIterator
4229 search(_ForwardIterator __first, _ForwardIterator __last,
4230 const _Searcher& __searcher)
4231 { return __searcher(__first, __last).first; }
4232#endif
4233
4234 /**
4235 * @brief Perform an operation on a sequence.
4236 * @ingroup mutating_algorithms
4237 * @param __first An input iterator.
4238 * @param __last An input iterator.
4239 * @param __result An output iterator.
4240 * @param __unary_op A unary operator.
4241 * @return An output iterator equal to @p __result+(__last-__first).
4242 *
4243 * Applies the operator to each element in the input range and assigns
4244 * the results to successive elements of the output sequence.
4245 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4246 * range @p [0,__last-__first).
4247 *
4248 * @p unary_op must not alter its argument.
4249 */
4250 template<typename _InputIterator, typename _OutputIterator,
4251 typename _UnaryOperation>
4252 _GLIBCXX20_CONSTEXPR
4253 _OutputIterator
4254 transform(_InputIterator __first, _InputIterator __last,
4255 _OutputIterator __result, _UnaryOperation __unary_op)
4256 {
4257 // concept requirements
4258 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4259 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4260 // "the type returned by a _UnaryOperation"
4261 __typeof__(__unary_op(*__first))>)
4262 __glibcxx_requires_valid_range(__first, __last);
4263
4264 for (; __first != __last; ++__first, (void)++__result)
4265 *__result = __unary_op(*__first);
4266 return __result;
4267 }
4268
4269 /**
4270 * @brief Perform an operation on corresponding elements of two sequences.
4271 * @ingroup mutating_algorithms
4272 * @param __first1 An input iterator.
4273 * @param __last1 An input iterator.
4274 * @param __first2 An input iterator.
4275 * @param __result An output iterator.
4276 * @param __binary_op A binary operator.
4277 * @return An output iterator equal to @p result+(last-first).
4278 *
4279 * Applies the operator to the corresponding elements in the two
4280 * input ranges and assigns the results to successive elements of the
4281 * output sequence.
4282 * Evaluates @p
4283 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4284 * @c N in the range @p [0,__last1-__first1).
4285 *
4286 * @p binary_op must not alter either of its arguments.
4287 */
4288 template<typename _InputIterator1, typename _InputIterator2,
4289 typename _OutputIterator, typename _BinaryOperation>
4290 _GLIBCXX20_CONSTEXPR
4291 _OutputIterator
4293 _InputIterator2 __first2, _OutputIterator __result,
4295 {
4296 // concept requirements
4297 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4298 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4299 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4300 // "the type returned by a _BinaryOperation"
4301 __typeof__(__binary_op(*__first1,*__first2))>)
4302 __glibcxx_requires_valid_range(__first1, __last1);
4303
4304 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4305 *__result = __binary_op(*__first1, *__first2);
4306 return __result;
4307 }
4308
4309 /**
4310 * @brief Replace each occurrence of one value in a sequence with another
4311 * value.
4312 * @ingroup mutating_algorithms
4313 * @param __first A forward iterator.
4314 * @param __last A forward iterator.
4315 * @param __old_value The value to be replaced.
4316 * @param __new_value The replacement value.
4317 * @return replace() returns no value.
4318 *
4319 * For each iterator `i` in the range `[__first,__last)` if
4320 * `*i == __old_value` then the assignment `*i = __new_value` is performed.
4321 */
4322 template<typename _ForwardIterator, typename _Tp>
4323 _GLIBCXX20_CONSTEXPR
4324 void
4325 replace(_ForwardIterator __first, _ForwardIterator __last,
4326 const _Tp& __old_value, const _Tp& __new_value)
4327 {
4328 // concept requirements
4329 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4331 __glibcxx_function_requires(_EqualOpConcept<
4333 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4335 __glibcxx_requires_valid_range(__first, __last);
4336
4337 for (; __first != __last; ++__first)
4338 if (*__first == __old_value)
4339 *__first = __new_value;
4340 }
4341
4342 /**
4343 * @brief Replace each value in a sequence for which a predicate returns
4344 * true with another value.
4345 * @ingroup mutating_algorithms
4346 * @param __first A forward iterator.
4347 * @param __last A forward iterator.
4348 * @param __pred A predicate.
4349 * @param __new_value The replacement value.
4350 * @return replace_if() returns no value.
4351 *
4352 * For each iterator `i` in the range `[__first,__last)` if `__pred(*i)`
4353 * is true then the assignment `*i = __new_value` is performed.
4354 */
4355 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4356 _GLIBCXX20_CONSTEXPR
4357 void
4358 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4359 _Predicate __pred, const _Tp& __new_value)
4360 {
4361 // concept requirements
4362 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4364 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4366 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4368 __glibcxx_requires_valid_range(__first, __last);
4369
4370 for (; __first != __last; ++__first)
4371 if (__pred(*__first))
4372 *__first = __new_value;
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 __last A forward iterator.
4381 * @param __gen A function object callable with no arguments.
4382 * @return generate() returns no value.
4383 *
4384 * Performs the assignment `*i = __gen()` for each `i` in the range
4385 * `[__first, __last)`.
4386 */
4387 template<typename _ForwardIterator, typename _Generator>
4388 _GLIBCXX20_CONSTEXPR
4389 void
4390 generate(_ForwardIterator __first, _ForwardIterator __last,
4392 {
4393 // concept requirements
4394 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4395 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4397 __glibcxx_requires_valid_range(__first, __last);
4398
4399 for (; __first != __last; ++__first)
4400 *__first = __gen();
4401 }
4402
4403 /**
4404 * @brief Assign the result of a function object to each value in a
4405 * sequence.
4406 * @ingroup mutating_algorithms
4407 * @param __first A forward iterator.
4408 * @param __n The length of the sequence.
4409 * @param __gen A function object callable with no arguments.
4410 * @return The end of the sequence, i.e., `__first + __n`
4411 *
4412 * Performs the assignment `*i = __gen()` for each `i` in the range
4413 * `[__first, __first + __n)`.
4414 *
4415 * If `__n` is negative, the function does nothing and returns `__first`.
4416 */
4417 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4418 // DR 865. More algorithms that throw away information
4419 // DR 426. search_n(), fill_n(), and generate_n() with negative n
4420 template<typename _OutputIterator, typename _Size, typename _Generator>
4421 _GLIBCXX20_CONSTEXPR
4422 _OutputIterator
4423 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4424 {
4425 // concept requirements
4426 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4427 // "the type returned by a _Generator"
4428 __typeof__(__gen())>)
4429
4430 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4431 for (_IntSize __niter = std::__size_to_integer(__n);
4432 __niter > 0; --__niter, (void) ++__first)
4433 *__first = __gen();
4434 return __first;
4435 }
4436
4437 /**
4438 * @brief Copy a sequence, removing consecutive duplicate values.
4439 * @ingroup mutating_algorithms
4440 * @param __first An input iterator.
4441 * @param __last An input iterator.
4442 * @param __result An output iterator.
4443 * @return An iterator designating the end of the resulting sequence.
4444 *
4445 * Copies each element in the range `[__first, __last)` to the range
4446 * beginning at `__result`, except that only the first element is copied
4447 * from groups of consecutive elements that compare equal.
4448 * `unique_copy()` is stable, so the relative order of elements that are
4449 * copied is unchanged.
4450 */
4451 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4452 // DR 241. Does unique_copy() require CopyConstructible and Assignable?
4453 // DR 538. 241 again: Does unique_copy() require CopyConstructible and
4454 // Assignable?
4455 template<typename _InputIterator, typename _OutputIterator>
4456 _GLIBCXX20_CONSTEXPR
4457 inline _OutputIterator
4458 unique_copy(_InputIterator __first, _InputIterator __last,
4459 _OutputIterator __result)
4460 {
4461 // concept requirements
4462 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4463 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4465 __glibcxx_function_requires(_EqualityComparableConcept<
4467 __glibcxx_requires_valid_range(__first, __last);
4468
4469 if (__first == __last)
4470 return __result;
4471 return std::__unique_copy(__first, __last, __result,
4472 __gnu_cxx::__ops::__iter_equal_to_iter(),
4473 std::__iterator_category(__first),
4474 std::__iterator_category(__result));
4475 }
4476
4477 /**
4478 * @brief Copy a sequence, removing consecutive values using a predicate.
4479 * @ingroup mutating_algorithms
4480 * @param __first An input iterator.
4481 * @param __last An input iterator.
4482 * @param __result An output iterator.
4483 * @param __binary_pred A binary predicate.
4484 * @return An iterator designating the end of the resulting sequence.
4485 *
4486 * Copies each element in the range `[__first, __last)` to the range
4487 * beginning at `__result`, except that only the first element is copied
4488 * from groups of consecutive elements for which `__binary_pred` returns
4489 * true.
4490 * `unique_copy()` is stable, so the relative order of elements that are
4491 * copied is unchanged.
4492 */
4493 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4494 // DR 241. Does unique_copy() require CopyConstructible and Assignable?
4495 template<typename _InputIterator, typename _OutputIterator,
4496 typename _BinaryPredicate>
4497 _GLIBCXX20_CONSTEXPR
4498 inline _OutputIterator
4499 unique_copy(_InputIterator __first, _InputIterator __last,
4500 _OutputIterator __result,
4502 {
4503 // concept requirements -- predicates checked later
4504 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4505 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4507 __glibcxx_requires_valid_range(__first, __last);
4508
4509 if (__first == __last)
4510 return __result;
4511 return std::__unique_copy(__first, __last, __result,
4512 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4513 std::__iterator_category(__first),
4514 std::__iterator_category(__result));
4515 }
4516
4517#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4518#if _GLIBCXX_HOSTED
4519 /**
4520 * @brief Randomly shuffle the elements of a sequence.
4521 * @ingroup mutating_algorithms
4522 * @param __first A forward iterator.
4523 * @param __last A forward iterator.
4524 * @return Nothing.
4525 *
4526 * Reorder the elements in the range `[__first, __last)` using a random
4527 * distribution, so that every possible ordering of the sequence is
4528 * equally likely.
4529 *
4530 * @deprecated
4531 * Since C++17, `std::random_shuffle` is not part of the C++ standard.
4532 * Use `std::shuffle` instead, which was introduced in C++11.
4533 */
4534 template<typename _RandomAccessIterator>
4535 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4536 inline void
4537 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4538 {
4539 // concept requirements
4540 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4542 __glibcxx_requires_valid_range(__first, __last);
4543
4544 if (__first == __last)
4545 return;
4546
4547#if RAND_MAX < __INT_MAX__
4548 if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
4549 {
4550 // Use a xorshift implementation seeded by two calls to rand()
4551 // instead of using rand() for all the random numbers needed.
4552 unsigned __xss
4553 = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
4554 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4555 {
4556 __xss += !__xss;
4557 __xss ^= __xss << 13;
4558 __xss ^= __xss >> 17;
4559 __xss ^= __xss << 5;
4560 _RandomAccessIterator __j = __first
4561 + (__xss % ((__i - __first) + 1));
4562 if (__i != __j)
4563 std::iter_swap(__i, __j);
4564 }
4565 return;
4566 }
4567#endif
4568
4569 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4570 {
4571 // XXX rand() % N is not uniformly distributed
4572 _RandomAccessIterator __j = __first
4573 + (std::rand() % ((__i - __first) + 1));
4574 if (__i != __j)
4575 std::iter_swap(__i, __j);
4576 }
4577 }
4578
4579 /**
4580 * @brief Shuffle the elements of a sequence using a random number
4581 * generator.
4582 * @ingroup mutating_algorithms
4583 * @param __first A forward iterator.
4584 * @param __last A forward iterator.
4585 * @param __rand The RNG functor or function.
4586 * @return Nothing.
4587 *
4588 * Reorders the elements in the range `[__first, __last)` using `__rand`
4589 * to provide a random distribution. Calling `__rand(N)` for a positive
4590 * integer `N` should return a randomly chosen integer from the
4591 * range `[0, N)`.
4592 *
4593 * @deprecated
4594 * Since C++17, `std::random_shuffle` is not part of the C++ standard.
4595 * Use `std::shuffle` instead, which was introduced in C++11.
4596 */
4597 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4598 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4599 void
4600 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4601#if __cplusplus >= 201103L
4603#else
4605#endif
4606 {
4607 // concept requirements
4608 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4610 __glibcxx_requires_valid_range(__first, __last);
4611
4612 if (__first == __last)
4613 return;
4614 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4615 {
4616 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4617 if (__i != __j)
4618 std::iter_swap(__i, __j);
4619 }
4620 }
4621#endif // HOSTED
4622#endif // <= C++11 || USE_DEPRECATED
4623
4624 /**
4625 * @brief Move elements for which a predicate is true to the beginning
4626 * of a sequence.
4627 * @ingroup mutating_algorithms
4628 * @param __first A forward iterator.
4629 * @param __last A forward iterator.
4630 * @param __pred A predicate functor.
4631 * @return An iterator `middle` such that `__pred(i)` is true for each
4632 * iterator `i` in the range `[__first, middle)` and false for each `i`
4633 * in the range `[middle, __last)`.
4634 *
4635 * `__pred` must not modify its operand. `partition()` does not preserve
4636 * the relative ordering of elements in each group, use
4637 * `stable_partition()` if this is needed.
4638 */
4639 template<typename _ForwardIterator, typename _Predicate>
4640 _GLIBCXX20_CONSTEXPR
4641 inline _ForwardIterator
4642 partition(_ForwardIterator __first, _ForwardIterator __last,
4643 _Predicate __pred)
4644 {
4645 // concept requirements
4646 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4648 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4650 __glibcxx_requires_valid_range(__first, __last);
4651
4652 return std::__partition(__first, __last, __pred,
4653 std::__iterator_category(__first));
4654 }
4655
4656
4657 /**
4658 * @brief Sort the smallest elements of a sequence.
4659 * @ingroup sorting_algorithms
4660 * @param __first An iterator.
4661 * @param __middle Another iterator.
4662 * @param __last Another iterator.
4663 * @return Nothing.
4664 *
4665 * Sorts the smallest `(__middle - __first)` elements in the range
4666 * `[first, last)` and moves them to the range `[__first, __middle)`. The
4667 * order of the remaining elements in the range `[__middle, __last)` is
4668 * unspecified.
4669 * After the sort if `i` and `j` are iterators in the range
4670 * `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4671 * in the range `[__middle, __last)` then `*j < *i` and `*k < *i` are
4672 * both false.
4673 */
4674 template<typename _RandomAccessIterator>
4675 _GLIBCXX20_CONSTEXPR
4676 inline void
4677 partial_sort(_RandomAccessIterator __first,
4678 _RandomAccessIterator __middle,
4679 _RandomAccessIterator __last)
4680 {
4681 // concept requirements
4682 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4684 __glibcxx_function_requires(_LessThanComparableConcept<
4686 __glibcxx_requires_valid_range(__first, __middle);
4687 __glibcxx_requires_valid_range(__middle, __last);
4688 __glibcxx_requires_irreflexive(__first, __last);
4689
4690 std::__partial_sort(__first, __middle, __last,
4691 __gnu_cxx::__ops::__iter_less_iter());
4692 }
4693
4694 /**
4695 * @brief Sort the smallest elements of a sequence using a predicate
4696 * for comparison.
4697 * @ingroup sorting_algorithms
4698 * @param __first An iterator.
4699 * @param __middle Another iterator.
4700 * @param __last Another iterator.
4701 * @param __comp A comparison functor.
4702 * @return Nothing.
4703 *
4704 * Sorts the smallest `(__middle - __first)` elements in the range
4705 * `[__first, __last)` and moves them to the range `[__first, __middle)`.
4706 * The order of the remaining elements in the range `[__middle, __last)` is
4707 * unspecified.
4708 * After the sort if `i` and `j` are iterators in the range
4709 * `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4710 * in the range `[__middle, __last)` then `*__comp(j, *i)` and
4711 * `__comp(*k, *i)` are both false.
4712 */
4713 template<typename _RandomAccessIterator, typename _Compare>
4714 _GLIBCXX20_CONSTEXPR
4715 inline void
4716 partial_sort(_RandomAccessIterator __first,
4717 _RandomAccessIterator __middle,
4718 _RandomAccessIterator __last,
4719 _Compare __comp)
4720 {
4721 // concept requirements
4722 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4724 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4727 __glibcxx_requires_valid_range(__first, __middle);
4728 __glibcxx_requires_valid_range(__middle, __last);
4729 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4730
4731 std::__partial_sort(__first, __middle, __last,
4732 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4733 }
4734
4735 /**
4736 * @brief Sort a sequence just enough to find a particular position.
4737 * @ingroup sorting_algorithms
4738 * @param __first An iterator.
4739 * @param __nth Another iterator.
4740 * @param __last Another iterator.
4741 * @return Nothing.
4742 *
4743 * Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4744 * is the same element that would have been in that position had the
4745 * whole sequence been sorted. The elements either side of `*__nth` are
4746 * not completely sorted, but for any iterator `i` in the range
4747 * `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)` it
4748 * holds that `*j < *i` is false.
4749 */
4750 template<typename _RandomAccessIterator>
4751 _GLIBCXX20_CONSTEXPR
4752 inline void
4754 _RandomAccessIterator __last)
4755 {
4756 // concept requirements
4757 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4759 __glibcxx_function_requires(_LessThanComparableConcept<
4761 __glibcxx_requires_valid_range(__first, __nth);
4762 __glibcxx_requires_valid_range(__nth, __last);
4763 __glibcxx_requires_irreflexive(__first, __last);
4764
4765 if (__first == __last || __nth == __last)
4766 return;
4767
4768 std::__introselect(__first, __nth, __last,
4769 std::__lg(__last - __first) * 2,
4770 __gnu_cxx::__ops::__iter_less_iter());
4771 }
4772
4773 /**
4774 * @brief Sort a sequence just enough to find a particular position
4775 * using a predicate for comparison.
4776 * @ingroup sorting_algorithms
4777 * @param __first An iterator.
4778 * @param __nth Another iterator.
4779 * @param __last Another iterator.
4780 * @param __comp A comparison functor.
4781 * @return Nothing.
4782 *
4783 * Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4784 * is the same element that would have been in that position had the
4785 * whole sequence been sorted. The elements either side of `*__nth` are
4786 * not completely sorted, but for any iterator `i` in the range
4787 * `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)`
4788 * it holds that `__comp(*j, *i)` is false.
4789 */
4790 template<typename _RandomAccessIterator, typename _Compare>
4791 _GLIBCXX20_CONSTEXPR
4792 inline void
4794 _RandomAccessIterator __last, _Compare __comp)
4795 {
4796 // concept requirements
4797 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4799 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4802 __glibcxx_requires_valid_range(__first, __nth);
4803 __glibcxx_requires_valid_range(__nth, __last);
4804 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4805
4806 if (__first == __last || __nth == __last)
4807 return;
4808
4809 std::__introselect(__first, __nth, __last,
4810 std::__lg(__last - __first) * 2,
4811 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4812 }
4813
4814 /**
4815 * @brief Sort the elements of a sequence.
4816 * @ingroup sorting_algorithms
4817 * @param __first An iterator.
4818 * @param __last Another iterator.
4819 * @return Nothing.
4820 *
4821 * Sorts the elements in the range `[__first, __last)` in ascending order,
4822 * such that for each iterator `i` in the range `[__first, __last - 1)`,
4823 * `*(i+1) < *i` is false.
4824 *
4825 * The relative ordering of equivalent elements is not preserved, use
4826 * `stable_sort()` if this is needed.
4827 */
4828 template<typename _RandomAccessIterator>
4829 _GLIBCXX20_CONSTEXPR
4830 inline void
4832 {
4833 // concept requirements
4834 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4836 __glibcxx_function_requires(_LessThanComparableConcept<
4838 __glibcxx_requires_valid_range(__first, __last);
4839 __glibcxx_requires_irreflexive(__first, __last);
4840
4841 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4842 }
4843
4844 /**
4845 * @brief Sort the elements of a sequence using a predicate for comparison.
4846 * @ingroup sorting_algorithms
4847 * @param __first An iterator.
4848 * @param __last Another iterator.
4849 * @param __comp A comparison functor.
4850 * @return Nothing.
4851 *
4852 * Sorts the elements in the range `[__first, __last)` in ascending order,
4853 * such that `__comp(*(i+1), *i)` is false for every iterator `i` in the
4854 * range `[__first, __last - 1)`.
4855 *
4856 * The relative ordering of equivalent elements is not preserved, use
4857 * `stable_sort()` if this is needed.
4858 */
4859 template<typename _RandomAccessIterator, typename _Compare>
4860 _GLIBCXX20_CONSTEXPR
4861 inline void
4863 _Compare __comp)
4864 {
4865 // concept requirements
4866 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4868 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4871 __glibcxx_requires_valid_range(__first, __last);
4872 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4873
4874 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4875 }
4876
4877 template<typename _InputIterator1, typename _InputIterator2,
4878 typename _OutputIterator, typename _Compare>
4879 _GLIBCXX20_CONSTEXPR
4880 _OutputIterator
4881 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4882 _InputIterator2 __first2, _InputIterator2 __last2,
4883 _OutputIterator __result, _Compare __comp)
4884 {
4885 while (__first1 != __last1 && __first2 != __last2)
4886 {
4887 if (__comp(__first2, __first1))
4888 {
4889 *__result = *__first2;
4890 ++__first2;
4891 }
4892 else
4893 {
4894 *__result = *__first1;
4895 ++__first1;
4896 }
4897 ++__result;
4898 }
4899 return std::copy(__first2, __last2,
4900 std::copy(__first1, __last1, __result));
4901 }
4902
4903 /**
4904 * @brief Merges two sorted ranges.
4905 * @ingroup sorting_algorithms
4906 * @param __first1 An iterator.
4907 * @param __first2 Another iterator.
4908 * @param __last1 Another iterator.
4909 * @param __last2 Another iterator.
4910 * @param __result An iterator pointing to the end of the merged range.
4911 * @return An output iterator equal to @p __result + (__last1 - __first1)
4912 * + (__last2 - __first2).
4913 *
4914 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4915 * the sorted range @p [__result, __result + (__last1-__first1) +
4916 * (__last2-__first2)). Both input ranges must be sorted, and the
4917 * output range must not overlap with either of the input ranges.
4918 * The sort is @e stable, that is, for equivalent elements in the
4919 * two ranges, elements from the first range will always come
4920 * before elements from the second.
4921 */
4922 template<typename _InputIterator1, typename _InputIterator2,
4923 typename _OutputIterator>
4924 _GLIBCXX20_CONSTEXPR
4925 inline _OutputIterator
4928 _OutputIterator __result)
4929 {
4930 // concept requirements
4931 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4932 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4933 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4935 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4937 __glibcxx_function_requires(_LessThanOpConcept<
4940 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4941 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4942 __glibcxx_requires_irreflexive2(__first1, __last1);
4943 __glibcxx_requires_irreflexive2(__first2, __last2);
4944
4945 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4946 __first2, __last2, __result,
4947 __gnu_cxx::__ops::__iter_less_iter());
4948 }
4949
4950 /**
4951 * @brief Merges two sorted ranges.
4952 * @ingroup sorting_algorithms
4953 * @param __first1 An iterator.
4954 * @param __first2 Another iterator.
4955 * @param __last1 Another iterator.
4956 * @param __last2 Another iterator.
4957 * @param __result An iterator pointing to the end of the merged range.
4958 * @param __comp A functor to use for comparisons.
4959 * @return An output iterator equal to @p __result + (__last1 - __first1)
4960 * + (__last2 - __first2).
4961 *
4962 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4963 * the sorted range @p [__result, __result + (__last1-__first1) +
4964 * (__last2-__first2)). Both input ranges must be sorted, and the
4965 * output range must not overlap with either of the input ranges.
4966 * The sort is @e stable, that is, for equivalent elements in the
4967 * two ranges, elements from the first range will always come
4968 * before elements from the second.
4969 *
4970 * The comparison function should have the same effects on ordering as
4971 * the function used for the initial sort.
4972 */
4973 template<typename _InputIterator1, typename _InputIterator2,
4974 typename _OutputIterator, typename _Compare>
4975 _GLIBCXX20_CONSTEXPR
4976 inline _OutputIterator
4979 _OutputIterator __result, _Compare __comp)
4980 {
4981 // concept requirements
4982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4984 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4986 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4988 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4991 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4992 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4993 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4994 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4995
4996 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4997 __first2, __last2, __result,
4998 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4999 }
5000
5001 template<typename _RandomAccessIterator, typename _Compare>
5002 _GLIBCXX26_CONSTEXPR
5003 inline void
5004 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5005 _Compare __comp)
5006 {
5007 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5008 _ValueType;
5009 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5010 _DistanceType;
5011
5012 if (__first == __last)
5013 return;
5014
5015#if _GLIBCXX_HOSTED
5016# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
5017 if consteval {
5018 return std::__inplace_stable_sort(__first, __last, __comp);
5019 }
5020# endif
5021
5022 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5023 // __stable_sort_adaptive sorts the range in two halves,
5024 // so the buffer only needs to fit half the range at once.
5025 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
5026
5027 if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
5028 std::__stable_sort_adaptive(__first,
5029 __first + _DistanceType(__buf.size()),
5030 __last, __buf.begin(), __comp);
5031 else if (__builtin_expect(__buf.begin() == 0, false))
5032 std::__inplace_stable_sort(__first, __last, __comp);
5033 else
5034 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
5035 _DistanceType(__buf.size()), __comp);
5036#else
5037 std::__inplace_stable_sort(__first, __last, __comp);
5038#endif
5039 }
5040
5041 /**
5042 * @brief Sort the elements of a sequence, preserving the relative order
5043 * of equivalent elements.
5044 * @ingroup sorting_algorithms
5045 * @param __first An iterator.
5046 * @param __last Another iterator.
5047 * @return Nothing.
5048 *
5049 * Sorts the elements in the range @p [__first,__last) in ascending order,
5050 * such that for each iterator @p i in the range @p [__first,__last-1),
5051 * @p *(i+1)<*i is false.
5052 *
5053 * The relative ordering of equivalent elements is preserved, so any two
5054 * elements @p x and @p y in the range @p [__first,__last) such that
5055 * @p x<y is false and @p y<x is false will have the same relative
5056 * ordering after calling @p stable_sort().
5057 */
5058 template<typename _RandomAccessIterator>
5059 _GLIBCXX26_CONSTEXPR
5060 inline void
5062 {
5063 // concept requirements
5064 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5066 __glibcxx_function_requires(_LessThanComparableConcept<
5068 __glibcxx_requires_valid_range(__first, __last);
5069 __glibcxx_requires_irreflexive(__first, __last);
5070
5071 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5072 __gnu_cxx::__ops::__iter_less_iter());
5073 }
5074
5075 /**
5076 * @brief Sort the elements of a sequence using a predicate for comparison,
5077 * preserving the relative order of equivalent elements.
5078 * @ingroup sorting_algorithms
5079 * @param __first An iterator.
5080 * @param __last Another iterator.
5081 * @param __comp A comparison functor.
5082 * @return Nothing.
5083 *
5084 * Sorts the elements in the range @p [__first,__last) in ascending order,
5085 * such that for each iterator @p i in the range @p [__first,__last-1),
5086 * @p __comp(*(i+1),*i) is false.
5087 *
5088 * The relative ordering of equivalent elements is preserved, so any two
5089 * elements @p x and @p y in the range @p [__first,__last) such that
5090 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5091 * relative ordering after calling @p stable_sort().
5092 */
5093 template<typename _RandomAccessIterator, typename _Compare>
5094 _GLIBCXX26_CONSTEXPR
5095 inline void
5097 _Compare __comp)
5098 {
5099 // concept requirements
5100 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5102 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5105 __glibcxx_requires_valid_range(__first, __last);
5106 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5107
5108 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5109 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5110 }
5111
5112 template<typename _InputIterator1, typename _InputIterator2,
5113 typename _OutputIterator,
5114 typename _Compare>
5115 _GLIBCXX20_CONSTEXPR
5116 _OutputIterator
5117 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5118 _InputIterator2 __first2, _InputIterator2 __last2,
5119 _OutputIterator __result, _Compare __comp)
5120 {
5121 while (__first1 != __last1 && __first2 != __last2)
5122 {
5123 if (__comp(__first1, __first2))
5124 {
5125 *__result = *__first1;
5126 ++__first1;
5127 }
5128 else if (__comp(__first2, __first1))
5129 {
5130 *__result = *__first2;
5131 ++__first2;
5132 }
5133 else
5134 {
5135 *__result = *__first1;
5136 ++__first1;
5137 ++__first2;
5138 }
5139 ++__result;
5140 }
5141 return std::copy(__first2, __last2,
5142 std::copy(__first1, __last1, __result));
5143 }
5144
5145 /**
5146 * @brief Return the union of two sorted ranges.
5147 * @ingroup set_algorithms
5148 * @param __first1 Start of first range.
5149 * @param __last1 End of first range.
5150 * @param __first2 Start of second range.
5151 * @param __last2 End of second range.
5152 * @param __result Start of output range.
5153 * @return End of the output range.
5154 * @ingroup set_algorithms
5155 *
5156 * This operation iterates over both ranges, copying elements present in
5157 * each range in order to the output range. Iterators increment for each
5158 * range. When the current element of one range is less than the other,
5159 * that element is copied and the iterator advanced. If an element is
5160 * contained in both ranges, the element from the first range is copied and
5161 * both ranges advance. The output range may not overlap either input
5162 * range.
5163 */
5164 template<typename _InputIterator1, typename _InputIterator2,
5165 typename _OutputIterator>
5166 _GLIBCXX20_CONSTEXPR
5167 inline _OutputIterator
5170 _OutputIterator __result)
5171 {
5172 // concept requirements
5173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5174 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5175 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5177 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5179 __glibcxx_function_requires(_LessThanOpConcept<
5182 __glibcxx_function_requires(_LessThanOpConcept<
5185 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5186 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5187 __glibcxx_requires_irreflexive2(__first1, __last1);
5188 __glibcxx_requires_irreflexive2(__first2, __last2);
5189
5190 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5191 __first2, __last2, __result,
5192 __gnu_cxx::__ops::__iter_less_iter());
5193 }
5194
5195 /**
5196 * @brief Return the union of two sorted ranges using a comparison functor.
5197 * @ingroup set_algorithms
5198 * @param __first1 Start of first range.
5199 * @param __last1 End of first range.
5200 * @param __first2 Start of second range.
5201 * @param __last2 End of second range.
5202 * @param __result Start of output range.
5203 * @param __comp The comparison functor.
5204 * @return End of the output range.
5205 * @ingroup set_algorithms
5206 *
5207 * This operation iterates over both ranges, copying elements present in
5208 * each range in order to the output range. Iterators increment for each
5209 * range. When the current element of one range is less than the other
5210 * according to @p __comp, that element is copied and the iterator advanced.
5211 * If an equivalent element according to @p __comp is contained in both
5212 * ranges, the element from the first range is copied and both ranges
5213 * advance. The output range may not overlap either input range.
5214 */
5215 template<typename _InputIterator1, typename _InputIterator2,
5216 typename _OutputIterator, typename _Compare>
5217 _GLIBCXX20_CONSTEXPR
5218 inline _OutputIterator
5221 _OutputIterator __result, _Compare __comp)
5222 {
5223 // concept requirements
5224 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5225 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5226 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5228 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5230 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5236 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5237 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5238 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5239 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5240
5241 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5242 __first2, __last2, __result,
5243 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5244 }
5245
5246 template<typename _InputIterator1, typename _InputIterator2,
5247 typename _OutputIterator,
5248 typename _Compare>
5249 _GLIBCXX20_CONSTEXPR
5250 _OutputIterator
5251 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5252 _InputIterator2 __first2, _InputIterator2 __last2,
5253 _OutputIterator __result, _Compare __comp)
5254 {
5255 while (__first1 != __last1 && __first2 != __last2)
5256 if (__comp(__first1, __first2))
5257 ++__first1;
5258 else if (__comp(__first2, __first1))
5259 ++__first2;
5260 else
5261 {
5262 *__result = *__first1;
5263 ++__first1;
5264 ++__first2;
5265 ++__result;
5266 }
5267 return __result;
5268 }
5269
5270 /**
5271 * @brief Return the intersection of two sorted ranges.
5272 * @ingroup set_algorithms
5273 * @param __first1 Start of first range.
5274 * @param __last1 End of first range.
5275 * @param __first2 Start of second range.
5276 * @param __last2 End of second range.
5277 * @param __result Start of output range.
5278 * @return End of the output range.
5279 * @ingroup set_algorithms
5280 *
5281 * This operation iterates over both ranges, copying elements present in
5282 * both ranges in order to the output range. Iterators increment for each
5283 * range. When the current element of one range is less than the other,
5284 * that iterator advances. If an element is contained in both ranges, the
5285 * element from the first range is copied and both ranges advance. The
5286 * output range may not overlap either input range.
5287 */
5288 template<typename _InputIterator1, typename _InputIterator2,
5289 typename _OutputIterator>
5290 _GLIBCXX20_CONSTEXPR
5291 inline _OutputIterator
5294 _OutputIterator __result)
5295 {
5296 // concept requirements
5297 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5298 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5299 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5301 __glibcxx_function_requires(_LessThanOpConcept<
5304 __glibcxx_function_requires(_LessThanOpConcept<
5307 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5308 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5309 __glibcxx_requires_irreflexive2(__first1, __last1);
5310 __glibcxx_requires_irreflexive2(__first2, __last2);
5311
5312 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5313 __first2, __last2, __result,
5314 __gnu_cxx::__ops::__iter_less_iter());
5315 }
5316
5317 /**
5318 * @brief Return the intersection of two sorted ranges using comparison
5319 * functor.
5320 * @ingroup set_algorithms
5321 * @param __first1 Start of first range.
5322 * @param __last1 End of first range.
5323 * @param __first2 Start of second range.
5324 * @param __last2 End of second range.
5325 * @param __result Start of output range.
5326 * @param __comp The comparison functor.
5327 * @return End of the output range.
5328 * @ingroup set_algorithms
5329 *
5330 * This operation iterates over both ranges, copying elements present in
5331 * both ranges in order to the output range. Iterators increment for each
5332 * range. When the current element of one range is less than the other
5333 * according to @p __comp, that iterator advances. If an element is
5334 * contained in both ranges according to @p __comp, the element from the
5335 * first range is copied and both ranges advance. The output range may not
5336 * overlap either input range.
5337 */
5338 template<typename _InputIterator1, typename _InputIterator2,
5339 typename _OutputIterator, typename _Compare>
5340 _GLIBCXX20_CONSTEXPR
5341 inline _OutputIterator
5344 _OutputIterator __result, _Compare __comp)
5345 {
5346 // concept requirements
5347 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5348 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5349 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5351 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5354 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5357 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5358 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5359 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5360 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5361
5362 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5363 __first2, __last2, __result,
5364 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5365 }
5366
5367 template<typename _InputIterator1, typename _InputIterator2,
5368 typename _OutputIterator,
5369 typename _Compare>
5370 _GLIBCXX20_CONSTEXPR
5371 _OutputIterator
5372 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5373 _InputIterator2 __first2, _InputIterator2 __last2,
5374 _OutputIterator __result, _Compare __comp)
5375 {
5376 while (__first1 != __last1 && __first2 != __last2)
5377 if (__comp(__first1, __first2))
5378 {
5379 *__result = *__first1;
5380 ++__first1;
5381 ++__result;
5382 }
5383 else if (__comp(__first2, __first1))
5384 ++__first2;
5385 else
5386 {
5387 ++__first1;
5388 ++__first2;
5389 }
5390 return std::copy(__first1, __last1, __result);
5391 }
5392
5393 /**
5394 * @brief Return the difference of two sorted ranges.
5395 * @ingroup set_algorithms
5396 * @param __first1 Start of first range.
5397 * @param __last1 End of first range.
5398 * @param __first2 Start of second range.
5399 * @param __last2 End of second range.
5400 * @param __result Start of output range.
5401 * @return End of the output range.
5402 * @ingroup set_algorithms
5403 *
5404 * This operation iterates over both ranges, copying elements present in
5405 * the first range but not the second in order to the output range.
5406 * Iterators increment for each range. When the current element of the
5407 * first range is less than the second, that element is copied and the
5408 * iterator advances. If the current element of the second range is less,
5409 * the iterator advances, but no element is copied. If an element is
5410 * contained in both ranges, no elements are copied and both ranges
5411 * advance. The output range may not overlap either input range.
5412 */
5413 template<typename _InputIterator1, typename _InputIterator2,
5414 typename _OutputIterator>
5415 _GLIBCXX20_CONSTEXPR
5416 inline _OutputIterator
5419 _OutputIterator __result)
5420 {
5421 // concept requirements
5422 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5423 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5424 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5426 __glibcxx_function_requires(_LessThanOpConcept<
5429 __glibcxx_function_requires(_LessThanOpConcept<
5432 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5433 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5434 __glibcxx_requires_irreflexive2(__first1, __last1);
5435 __glibcxx_requires_irreflexive2(__first2, __last2);
5436
5437 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5438 __first2, __last2, __result,
5439 __gnu_cxx::__ops::__iter_less_iter());
5440 }
5441
5442 /**
5443 * @brief Return the difference of two sorted ranges using comparison
5444 * functor.
5445 * @ingroup set_algorithms
5446 * @param __first1 Start of first range.
5447 * @param __last1 End of first range.
5448 * @param __first2 Start of second range.
5449 * @param __last2 End of second range.
5450 * @param __result Start of output range.
5451 * @param __comp The comparison functor.
5452 * @return End of the output range.
5453 * @ingroup set_algorithms
5454 *
5455 * This operation iterates over both ranges, copying elements present in
5456 * the first range but not the second in order to the output range.
5457 * Iterators increment for each range. When the current element of the
5458 * first range is less than the second according to @p __comp, that element
5459 * is copied and the iterator advances. If the current element of the
5460 * second range is less, no element is copied and the iterator advances.
5461 * If an element is contained in both ranges according to @p __comp, no
5462 * elements are copied and both ranges advance. The output range may not
5463 * overlap either input range.
5464 */
5465 template<typename _InputIterator1, typename _InputIterator2,
5466 typename _OutputIterator, typename _Compare>
5467 _GLIBCXX20_CONSTEXPR
5468 inline _OutputIterator
5471 _OutputIterator __result, _Compare __comp)
5472 {
5473 // concept requirements
5474 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5475 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5478 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5481 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5484 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5485 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5486 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5487 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5488
5489 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5490 __first2, __last2, __result,
5491 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5492 }
5493
5494 template<typename _InputIterator1, typename _InputIterator2,
5495 typename _OutputIterator,
5496 typename _Compare>
5497 _GLIBCXX20_CONSTEXPR
5498 _OutputIterator
5499 __set_symmetric_difference(_InputIterator1 __first1,
5500 _InputIterator1 __last1,
5501 _InputIterator2 __first2,
5502 _InputIterator2 __last2,
5503 _OutputIterator __result,
5504 _Compare __comp)
5505 {
5506 while (__first1 != __last1 && __first2 != __last2)
5507 if (__comp(__first1, __first2))
5508 {
5509 *__result = *__first1;
5510 ++__first1;
5511 ++__result;
5512 }
5513 else if (__comp(__first2, __first1))
5514 {
5515 *__result = *__first2;
5516 ++__first2;
5517 ++__result;
5518 }
5519 else
5520 {
5521 ++__first1;
5522 ++__first2;
5523 }
5524 return std::copy(__first2, __last2,
5525 std::copy(__first1, __last1, __result));
5526 }
5527
5528 /**
5529 * @brief Return the symmetric difference of two sorted ranges.
5530 * @ingroup set_algorithms
5531 * @param __first1 Start of first range.
5532 * @param __last1 End of first range.
5533 * @param __first2 Start of second range.
5534 * @param __last2 End of second range.
5535 * @param __result Start of output range.
5536 * @return End of the output range.
5537 * @ingroup set_algorithms
5538 *
5539 * This operation iterates over both ranges, copying elements present in
5540 * one range but not the other in order to the output range. Iterators
5541 * increment for each range. When the current element of one range is less
5542 * than the other, that element is copied and the iterator advances. If an
5543 * element is contained in both ranges, no elements are copied and both
5544 * ranges advance. The output range may not overlap either input range.
5545 */
5546 template<typename _InputIterator1, typename _InputIterator2,
5547 typename _OutputIterator>
5548 _GLIBCXX20_CONSTEXPR
5549 inline _OutputIterator
5552 _OutputIterator __result)
5553 {
5554 // concept requirements
5555 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5556 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5557 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5559 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5561 __glibcxx_function_requires(_LessThanOpConcept<
5564 __glibcxx_function_requires(_LessThanOpConcept<
5567 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5568 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5569 __glibcxx_requires_irreflexive2(__first1, __last1);
5570 __glibcxx_requires_irreflexive2(__first2, __last2);
5571
5572 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5573 __first2, __last2, __result,
5574 __gnu_cxx::__ops::__iter_less_iter());
5575 }
5576
5577 /**
5578 * @brief Return the symmetric difference of two sorted ranges using
5579 * comparison functor.
5580 * @ingroup set_algorithms
5581 * @param __first1 Start of first range.
5582 * @param __last1 End of first range.
5583 * @param __first2 Start of second range.
5584 * @param __last2 End of second range.
5585 * @param __result Start of output range.
5586 * @param __comp The comparison functor.
5587 * @return End of the output range.
5588 * @ingroup set_algorithms
5589 *
5590 * This operation iterates over both ranges, copying elements present in
5591 * one range but not the other in order to the output range. Iterators
5592 * increment for each range. When the current element of one range is less
5593 * than the other according to @p comp, that element is copied and the
5594 * iterator advances. If an element is contained in both ranges according
5595 * to @p __comp, no elements are copied and both ranges advance. The output
5596 * range may not overlap either input range.
5597 */
5598 template<typename _InputIterator1, typename _InputIterator2,
5599 typename _OutputIterator, typename _Compare>
5600 _GLIBCXX20_CONSTEXPR
5601 inline _OutputIterator
5604 _OutputIterator __result,
5605 _Compare __comp)
5606 {
5607 // concept requirements
5608 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5609 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5610 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5612 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5614 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5617 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5620 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5621 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5622 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5623 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5624
5625 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5626 __first2, __last2, __result,
5627 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5628 }
5629
5630 template<typename _ForwardIterator, typename _Compare>
5631 _GLIBCXX14_CONSTEXPR
5632 _ForwardIterator
5633 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5634 _Compare __comp)
5635 {
5636 if (__first == __last)
5637 return __first;
5638 _ForwardIterator __result = __first;
5639 while (++__first != __last)
5640 if (__comp(__first, __result))
5641 __result = __first;
5642 return __result;
5643 }
5644
5645 /**
5646 * @brief Return the minimum element in a range.
5647 * @ingroup sorting_algorithms
5648 * @param __first Start of range.
5649 * @param __last End of range.
5650 * @return Iterator referencing the first instance of the smallest value.
5651 */
5652 template<typename _ForwardIterator>
5653 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5654 _ForwardIterator
5655 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5656 {
5657 // concept requirements
5658 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5659 __glibcxx_function_requires(_LessThanComparableConcept<
5661 __glibcxx_requires_valid_range(__first, __last);
5662 __glibcxx_requires_irreflexive(__first, __last);
5663
5664 return _GLIBCXX_STD_A::__min_element(__first, __last,
5665 __gnu_cxx::__ops::__iter_less_iter());
5666 }
5667
5668 /**
5669 * @brief Return the minimum element in a range using comparison functor.
5670 * @ingroup sorting_algorithms
5671 * @param __first Start of range.
5672 * @param __last End of range.
5673 * @param __comp Comparison functor.
5674 * @return Iterator referencing the first instance of the smallest value
5675 * according to __comp.
5676 */
5677 template<typename _ForwardIterator, typename _Compare>
5678 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5679 inline _ForwardIterator
5680 min_element(_ForwardIterator __first, _ForwardIterator __last,
5681 _Compare __comp)
5682 {
5683 // concept requirements
5684 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5685 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5688 __glibcxx_requires_valid_range(__first, __last);
5689 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5690
5691 return _GLIBCXX_STD_A::__min_element(__first, __last,
5692 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5693 }
5694
5695 template<typename _ForwardIterator, typename _Compare>
5696 _GLIBCXX14_CONSTEXPR
5697 _ForwardIterator
5698 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5699 _Compare __comp)
5700 {
5701 if (__first == __last) return __first;
5702 _ForwardIterator __result = __first;
5703 while (++__first != __last)
5704 if (__comp(__result, __first))
5705 __result = __first;
5706 return __result;
5707 }
5708
5709 /**
5710 * @brief Return the maximum element in a range.
5711 * @ingroup sorting_algorithms
5712 * @param __first Start of range.
5713 * @param __last End of range.
5714 * @return Iterator referencing the first instance of the largest value.
5715 */
5716 template<typename _ForwardIterator>
5717 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5718 inline _ForwardIterator
5719 max_element(_ForwardIterator __first, _ForwardIterator __last)
5720 {
5721 // concept requirements
5722 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5723 __glibcxx_function_requires(_LessThanComparableConcept<
5725 __glibcxx_requires_valid_range(__first, __last);
5726 __glibcxx_requires_irreflexive(__first, __last);
5727
5728 return _GLIBCXX_STD_A::__max_element(__first, __last,
5729 __gnu_cxx::__ops::__iter_less_iter());
5730 }
5731
5732 /**
5733 * @brief Return the maximum element in a range using comparison functor.
5734 * @ingroup sorting_algorithms
5735 * @param __first Start of range.
5736 * @param __last End of range.
5737 * @param __comp Comparison functor.
5738 * @return Iterator referencing the first instance of the largest value
5739 * according to __comp.
5740 */
5741 template<typename _ForwardIterator, typename _Compare>
5742 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5743 inline _ForwardIterator
5744 max_element(_ForwardIterator __first, _ForwardIterator __last,
5745 _Compare __comp)
5746 {
5747 // concept requirements
5748 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5749 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5752 __glibcxx_requires_valid_range(__first, __last);
5753 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5754
5755 return _GLIBCXX_STD_A::__max_element(__first, __last,
5756 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5757 }
5758
5759#if __cplusplus >= 201103L
5760 // N2722 + DR 915.
5761 template<typename _Tp>
5762 _GLIBCXX14_CONSTEXPR
5763 inline _Tp
5764 min(initializer_list<_Tp> __l)
5765 {
5766 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5767 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5768 __gnu_cxx::__ops::__iter_less_iter());
5769 }
5770
5771 template<typename _Tp, typename _Compare>
5772 _GLIBCXX14_CONSTEXPR
5773 inline _Tp
5774 min(initializer_list<_Tp> __l, _Compare __comp)
5775 {
5776 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5777 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5778 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5779 }
5780
5781 template<typename _Tp>
5782 _GLIBCXX14_CONSTEXPR
5783 inline _Tp
5784 max(initializer_list<_Tp> __l)
5785 {
5786 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5787 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5788 __gnu_cxx::__ops::__iter_less_iter());
5789 }
5790
5791 template<typename _Tp, typename _Compare>
5792 _GLIBCXX14_CONSTEXPR
5793 inline _Tp
5794 max(initializer_list<_Tp> __l, _Compare __comp)
5795 {
5796 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5797 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5798 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5799 }
5800#endif // C++11
5801
5802#if __cplusplus >= 201402L
5803 /// Reservoir sampling algorithm.
5804 template<typename _InputIterator, typename _RandomAccessIterator,
5805 typename _Size, typename _UniformRandomBitGenerator>
5806 _RandomAccessIterator
5809 _Size __n, _UniformRandomBitGenerator&& __g)
5810 {
5812 using __param_type = typename __distrib_type::param_type;
5813 __distrib_type __d{};
5814 _Size __sample_sz = 0;
5815 while (__first != __last && __sample_sz != __n)
5816 {
5817 __out[__sample_sz++] = *__first;
5818 ++__first;
5819 }
5820 for (auto __pop_sz = __sample_sz; __first != __last;
5821 ++__first, (void) ++__pop_sz)
5822 {
5823 const auto __k = __d(__g, __param_type{0, __pop_sz});
5824 if (__k < __n)
5825 __out[__k] = *__first;
5826 }
5827 return __out + __sample_sz;
5828 }
5829
5830 /// Selection sampling algorithm.
5831 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5832 typename _Size, typename _UniformRandomBitGenerator>
5833 _OutputIterator
5836 _OutputIterator __out, _Cat,
5837 _Size __n, _UniformRandomBitGenerator&& __g)
5838 {
5840 using __param_type = typename __distrib_type::param_type;
5844
5845 if (__first == __last)
5846 return __out;
5847
5848 __distrib_type __d{};
5849 _Size __unsampled_sz = std::distance(__first, __last);
5850 __n = std::min(__n, __unsampled_sz);
5851
5852 // If possible, we use __gen_two_uniform_ints to efficiently produce
5853 // two random numbers using a single distribution invocation:
5854
5855 const __uc_type __urngrange = __g.max() - __g.min();
5857 // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
5858 // wrapping issues.
5859 {
5860 while (__n != 0 && __unsampled_sz >= 2)
5861 {
5862 const pair<_Size, _Size> __p =
5864
5866 if (__p.first < __n)
5867 {
5868 *__out++ = *__first;
5869 --__n;
5870 }
5871
5872 ++__first;
5873
5874 if (__n == 0) break;
5875
5877 if (__p.second < __n)
5878 {
5879 *__out++ = *__first;
5880 --__n;
5881 }
5882
5883 ++__first;
5884 }
5885 }
5886
5887 // The loop above is otherwise equivalent to this one-at-a-time version:
5888
5889 for (; __n != 0; ++__first)
5890 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5891 {
5892 *__out++ = *__first;
5893 --__n;
5894 }
5895 return __out;
5896 }
5897#endif // C++14
5898
5899#ifdef __glibcxx_sample // C++ >= 17
5900 /// Take a random sample from a population.
5901 template<typename _PopulationIterator, typename _SampleIterator,
5902 typename _Distance, typename _UniformRandomBitGenerator>
5903 _SampleIterator
5907 {
5908 using __pop_cat = typename
5910 using __samp_cat = typename
5912
5913 static_assert(
5916 "output range must use a RandomAccessIterator when input range"
5917 " does not meet the ForwardIterator requirements");
5918
5919 static_assert(is_integral<_Distance>::value,
5920 "sample size must be an integer type");
5921
5923 return _GLIBCXX_STD_A::
5924 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5926 }
5927#endif // __glibcxx_sample
5928
5929_GLIBCXX_END_NAMESPACE_ALGO
5930_GLIBCXX_END_NAMESPACE_VERSION
5931} // namespace std
5932
5933#pragma GCC diagnostic pop
5934
5935#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
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
Definition stl_algo.h:3818
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
Definition stl_algo.h:3636
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:3300
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:2322
_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:5807
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:2360
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
_GLIBCXX26_CONSTEXPR 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:2437
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:3686
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
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:2253
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:5904
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
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 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:2279
_GLIBCXX26_CONSTEXPR _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:1452
_GLIBCXX26_CONSTEXPR void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
Definition stl_algo.h:2755
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:2618
is_integral
Definition type_traits:468
common_type
Definition type_traits:2470
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.