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