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