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