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