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