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