1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001-2022 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
59 #include <bits/algorithmfwd.h>
60 #include <bits/stl_algobase.h>
61 #include <bits/stl_heap.h>
62 #include <bits/predefined_ops.h>
64 #if __cplusplus >= 201103L
65 #include <bits/uniform_int_dist.h>
69 # include <bits/stl_tempbuf.h> // for _Temporary_buffer
70 # if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
71 # include <cstdlib> // for rand
75 // See concept_check.h for the __glibcxx_*_requires macros.
77 namespace std
_GLIBCXX_VISIBILITY(default)
79 _GLIBCXX_BEGIN_NAMESPACE_VERSION
81 /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
82 template<typename _Iterator
, typename _Compare
>
85 __move_median_to_first(_Iterator __result
,_Iterator __a
, _Iterator __b
,
86 _Iterator __c
, _Compare __comp
)
91 std::iter_swap(__result
, __b
);
92 else if (__comp(__a
, __c
))
93 std::iter_swap(__result
, __c
);
95 std::iter_swap(__result
, __a
);
97 else if (__comp(__a
, __c
))
98 std::iter_swap(__result
, __a
);
99 else if (__comp(__b
, __c
))
100 std::iter_swap(__result
, __c
);
102 std::iter_swap(__result
, __b
);
105 /// Provided for stable_partition to use.
106 template<typename _InputIterator
, typename _Predicate
>
108 inline _InputIterator
109 __find_if_not(_InputIterator __first
, _InputIterator __last
,
112 return std::__find_if(__first
, __last
,
113 __gnu_cxx::__ops::__negate(__pred
),
114 std::__iterator_category(__first
));
117 /// Like find_if_not(), but uses and updates a count of the
118 /// remaining range length instead of comparing against an end
120 template<typename _InputIterator
, typename _Predicate
, typename _Distance
>
123 __find_if_not_n(_InputIterator __first
, _Distance
& __len
, _Predicate __pred
)
125 for (; __len
; --__len
, (void) ++__first
)
126 if (!__pred(__first
))
133 // set_symmetric_difference
144 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
145 typename _BinaryPredicate
>
148 __search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
149 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
150 _BinaryPredicate __predicate
)
152 // Test for empty ranges
153 if (__first1
== __last1
|| __first2
== __last2
)
156 // Test for a pattern of length 1.
157 _ForwardIterator2
__p1(__first2
);
158 if (++__p1
== __last2
)
159 return std::__find_if(__first1
, __last1
,
160 __gnu_cxx::__ops::__iter_comp_iter(__predicate
, __first2
));
163 _ForwardIterator1 __current
= __first1
;
168 std::__find_if(__first1
, __last1
,
169 __gnu_cxx::__ops::__iter_comp_iter(__predicate
, __first2
));
171 if (__first1
== __last1
)
174 _ForwardIterator2 __p
= __p1
;
175 __current
= __first1
;
176 if (++__current
== __last1
)
179 while (__predicate(__current
, __p
))
181 if (++__p
== __last2
)
183 if (++__current
== __last1
)
194 * This is an helper function for search_n overloaded for forward iterators.
196 template<typename _ForwardIterator
, typename _Integer
,
197 typename _UnaryPredicate
>
200 __search_n_aux(_ForwardIterator __first
, _ForwardIterator __last
,
201 _Integer __count
, _UnaryPredicate __unary_pred
,
202 std::forward_iterator_tag
)
204 __first
= std::__find_if(__first
, __last
, __unary_pred
);
205 while (__first
!= __last
)
207 typename iterator_traits
<_ForwardIterator
>::difference_type
209 _ForwardIterator __i
= __first
;
211 while (__i
!= __last
&& __n
!= 1 && __unary_pred(__i
))
220 __first
= std::__find_if(++__i
, __last
, __unary_pred
);
226 * This is an helper function for search_n overloaded for random access
229 template<typename _RandomAccessIter
, typename _Integer
,
230 typename _UnaryPredicate
>
233 __search_n_aux(_RandomAccessIter __first
, _RandomAccessIter __last
,
234 _Integer __count
, _UnaryPredicate __unary_pred
,
235 std::random_access_iterator_tag
)
237 typedef typename
std::iterator_traits
<_RandomAccessIter
>::difference_type
240 _DistanceType __tailSize
= __last
- __first
;
241 _DistanceType __remainder
= __count
;
243 while (__remainder
<= __tailSize
) // the main loop...
245 __first
+= __remainder
;
246 __tailSize
-= __remainder
;
247 // __first here is always pointing to one past the last element of
248 // next possible match.
249 _RandomAccessIter __backTrack
= __first
;
250 while (__unary_pred(--__backTrack
))
252 if (--__remainder
== 0)
253 return (__first
- __count
); // Success
255 __remainder
= __count
+ 1 - (__first
- __backTrack
);
257 return __last
; // Failure
260 template<typename _ForwardIterator
, typename _Integer
,
261 typename _UnaryPredicate
>
264 __search_n(_ForwardIterator __first
, _ForwardIterator __last
,
266 _UnaryPredicate __unary_pred
)
272 return std::__find_if(__first
, __last
, __unary_pred
);
274 return std::__search_n_aux(__first
, __last
, __count
, __unary_pred
,
275 std::__iterator_category(__first
));
278 // find_end for forward iterators.
279 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
280 typename _BinaryPredicate
>
283 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
284 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
285 forward_iterator_tag
, forward_iterator_tag
,
286 _BinaryPredicate __comp
)
288 if (__first2
== __last2
)
291 _ForwardIterator1 __result
= __last1
;
294 _ForwardIterator1 __new_result
295 = std::__search(__first1
, __last1
, __first2
, __last2
, __comp
);
296 if (__new_result
== __last1
)
300 __result
= __new_result
;
301 __first1
= __new_result
;
307 // find_end for bidirectional iterators (much faster).
308 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
309 typename _BinaryPredicate
>
311 _BidirectionalIterator1
312 __find_end(_BidirectionalIterator1 __first1
,
313 _BidirectionalIterator1 __last1
,
314 _BidirectionalIterator2 __first2
,
315 _BidirectionalIterator2 __last2
,
316 bidirectional_iterator_tag
, bidirectional_iterator_tag
,
317 _BinaryPredicate __comp
)
319 // concept requirements
320 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
321 _BidirectionalIterator1
>)
322 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
323 _BidirectionalIterator2
>)
325 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
326 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
328 _RevIterator1
__rlast1(__first1
);
329 _RevIterator2
__rlast2(__first2
);
330 _RevIterator1 __rresult
= std::__search(_RevIterator1(__last1
), __rlast1
,
331 _RevIterator2(__last2
), __rlast2
,
334 if (__rresult
== __rlast1
)
338 _BidirectionalIterator1 __result
= __rresult
.base();
339 std::advance(__result
, -std::distance(__first2
, __last2
));
345 * @brief Find last matching subsequence in a sequence.
346 * @ingroup non_mutating_algorithms
347 * @param __first1 Start of range to search.
348 * @param __last1 End of range to search.
349 * @param __first2 Start of sequence to match.
350 * @param __last2 End of sequence to match.
351 * @return The last iterator @c i in the range
352 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
353 * @p *(__first2+N) for each @c N in the range @p
354 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
356 * Searches the range @p [__first1,__last1) for a sub-sequence that
357 * compares equal value-by-value with the sequence given by @p
358 * [__first2,__last2) and returns an iterator to the __first
359 * element of the sub-sequence, or @p __last1 if the sub-sequence
360 * is not found. The sub-sequence will be the last such
361 * subsequence contained in [__first1,__last1).
363 * Because the sub-sequence must lie completely within the range @p
364 * [__first1,__last1) it must start at a position less than @p
365 * __last1-(__last2-__first2) where @p __last2-__first2 is the
366 * length of the sub-sequence. This means that the returned
367 * iterator @c i will be in the range @p
368 * [__first1,__last1-(__last2-__first2))
370 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
372 inline _ForwardIterator1
373 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
374 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
376 // concept requirements
377 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
378 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
379 __glibcxx_function_requires(_EqualOpConcept
<
380 typename iterator_traits
<_ForwardIterator1
>::value_type
,
381 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
382 __glibcxx_requires_valid_range(__first1
, __last1
);
383 __glibcxx_requires_valid_range(__first2
, __last2
);
385 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
386 std::__iterator_category(__first1
),
387 std::__iterator_category(__first2
),
388 __gnu_cxx::__ops::__iter_equal_to_iter());
392 * @brief Find last matching subsequence in a sequence using a predicate.
393 * @ingroup non_mutating_algorithms
394 * @param __first1 Start of range to search.
395 * @param __last1 End of range to search.
396 * @param __first2 Start of sequence to match.
397 * @param __last2 End of sequence to match.
398 * @param __comp The predicate to use.
399 * @return The last iterator @c i in the range @p
400 * [__first1,__last1-(__last2-__first2)) such that @c
401 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
402 * range @p [0,__last2-__first2), or @p __last1 if no such iterator
405 * Searches the range @p [__first1,__last1) for a sub-sequence that
406 * compares equal value-by-value with the sequence given by @p
407 * [__first2,__last2) using comp as a predicate and returns an
408 * iterator to the first element of the sub-sequence, or @p __last1
409 * if the sub-sequence is not found. The sub-sequence will be the
410 * last such subsequence contained in [__first,__last1).
412 * Because the sub-sequence must lie completely within the range @p
413 * [__first1,__last1) it must start at a position less than @p
414 * __last1-(__last2-__first2) where @p __last2-__first2 is the
415 * length of the sub-sequence. This means that the returned
416 * iterator @c i will be in the range @p
417 * [__first1,__last1-(__last2-__first2))
419 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
420 typename _BinaryPredicate
>
422 inline _ForwardIterator1
423 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
424 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
425 _BinaryPredicate __comp
)
427 // concept requirements
428 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
429 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
430 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
431 typename iterator_traits
<_ForwardIterator1
>::value_type
,
432 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
433 __glibcxx_requires_valid_range(__first1
, __last1
);
434 __glibcxx_requires_valid_range(__first2
, __last2
);
436 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
437 std::__iterator_category(__first1
),
438 std::__iterator_category(__first2
),
439 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
442 #if __cplusplus >= 201103L
444 * @brief Checks that a predicate is true for all the elements
446 * @ingroup non_mutating_algorithms
447 * @param __first An input iterator.
448 * @param __last An input iterator.
449 * @param __pred A predicate.
450 * @return True if the check is true, false otherwise.
452 * Returns true if @p __pred is true for each element in the range
453 * @p [__first,__last), and false otherwise.
455 template<typename _InputIterator
, typename _Predicate
>
458 all_of(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
459 { return __last
== std::find_if_not(__first
, __last
, __pred
); }
462 * @brief Checks that a predicate is false for all the elements
464 * @ingroup non_mutating_algorithms
465 * @param __first An input iterator.
466 * @param __last An input iterator.
467 * @param __pred A predicate.
468 * @return True if the check is true, false otherwise.
470 * Returns true if @p __pred is false for each element in the range
471 * @p [__first,__last), and false otherwise.
473 template<typename _InputIterator
, typename _Predicate
>
476 none_of(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
477 { return __last
== _GLIBCXX_STD_A::find_if(__first
, __last
, __pred
); }
480 * @brief Checks that a predicate is true for at least one element
482 * @ingroup non_mutating_algorithms
483 * @param __first An input iterator.
484 * @param __last An input iterator.
485 * @param __pred A predicate.
486 * @return True if the check is true, false otherwise.
488 * Returns true if an element exists in the range @p
489 * [__first,__last) such that @p __pred is true, and false
492 template<typename _InputIterator
, typename _Predicate
>
495 any_of(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
496 { return !std::none_of(__first
, __last
, __pred
); }
499 * @brief Find the first element in a sequence for which a
500 * predicate is false.
501 * @ingroup non_mutating_algorithms
502 * @param __first An input iterator.
503 * @param __last An input iterator.
504 * @param __pred A predicate.
505 * @return The first iterator @c i in the range @p [__first,__last)
506 * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
508 template<typename _InputIterator
, typename _Predicate
>
510 inline _InputIterator
511 find_if_not(_InputIterator __first
, _InputIterator __last
,
514 // concept requirements
515 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
516 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
517 typename iterator_traits
<_InputIterator
>::value_type
>)
518 __glibcxx_requires_valid_range(__first
, __last
);
519 return std::__find_if_not(__first
, __last
,
520 __gnu_cxx::__ops::__pred_iter(__pred
));
524 * @brief Checks whether the sequence is partitioned.
525 * @ingroup mutating_algorithms
526 * @param __first An input iterator.
527 * @param __last An input iterator.
528 * @param __pred A predicate.
529 * @return True if the range @p [__first,__last) is partioned by @p __pred,
530 * i.e. if all elements that satisfy @p __pred appear before those that
533 template<typename _InputIterator
, typename _Predicate
>
536 is_partitioned(_InputIterator __first
, _InputIterator __last
,
539 __first
= std::find_if_not(__first
, __last
, __pred
);
540 if (__first
== __last
)
543 return std::none_of(__first
, __last
, __pred
);
547 * @brief Find the partition point of a partitioned range.
548 * @ingroup mutating_algorithms
549 * @param __first An iterator.
550 * @param __last Another iterator.
551 * @param __pred A predicate.
552 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
553 * and @p none_of(mid, __last, __pred) are both true.
555 template<typename _ForwardIterator
, typename _Predicate
>
558 partition_point(_ForwardIterator __first
, _ForwardIterator __last
,
561 // concept requirements
562 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
563 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
564 typename iterator_traits
<_ForwardIterator
>::value_type
>)
566 // A specific debug-mode test will be necessary...
567 __glibcxx_requires_valid_range(__first
, __last
);
569 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
572 _DistanceType __len
= std::distance(__first
, __last
);
576 _DistanceType __half
= __len
>> 1;
577 _ForwardIterator __middle
= __first
;
578 std::advance(__middle
, __half
);
579 if (__pred(*__middle
))
583 __len
= __len
- __half
- 1;
592 template<typename _InputIterator
, typename _OutputIterator
,
596 __remove_copy_if(_InputIterator __first
, _InputIterator __last
,
597 _OutputIterator __result
, _Predicate __pred
)
599 for (; __first
!= __last
; ++__first
)
600 if (!__pred(__first
))
602 *__result
= *__first
;
609 * @brief Copy a sequence, removing elements of a given value.
610 * @ingroup mutating_algorithms
611 * @param __first An input iterator.
612 * @param __last An input iterator.
613 * @param __result An output iterator.
614 * @param __value The value to be removed.
615 * @return An iterator designating the end of the resulting sequence.
617 * Copies each element in the range @p [__first,__last) not equal
618 * to @p __value to the range beginning at @p __result.
619 * remove_copy() is stable, so the relative order of elements that
620 * are copied is unchanged.
622 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
624 inline _OutputIterator
625 remove_copy(_InputIterator __first
, _InputIterator __last
,
626 _OutputIterator __result
, const _Tp
& __value
)
628 // concept requirements
629 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
630 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
631 typename iterator_traits
<_InputIterator
>::value_type
>)
632 __glibcxx_function_requires(_EqualOpConcept
<
633 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
634 __glibcxx_requires_valid_range(__first
, __last
);
636 return std::__remove_copy_if(__first
, __last
, __result
,
637 __gnu_cxx::__ops::__iter_equals_val(__value
));
641 * @brief Copy a sequence, removing elements for which a predicate is true.
642 * @ingroup mutating_algorithms
643 * @param __first An input iterator.
644 * @param __last An input iterator.
645 * @param __result An output iterator.
646 * @param __pred A predicate.
647 * @return An iterator designating the end of the resulting sequence.
649 * Copies each element in the range @p [__first,__last) for which
650 * @p __pred returns false to the range beginning at @p __result.
652 * remove_copy_if() is stable, so the relative order of elements that are
653 * copied is unchanged.
655 template<typename _InputIterator
, typename _OutputIterator
,
658 inline _OutputIterator
659 remove_copy_if(_InputIterator __first
, _InputIterator __last
,
660 _OutputIterator __result
, _Predicate __pred
)
662 // concept requirements
663 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
664 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
665 typename iterator_traits
<_InputIterator
>::value_type
>)
666 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
667 typename iterator_traits
<_InputIterator
>::value_type
>)
668 __glibcxx_requires_valid_range(__first
, __last
);
670 return std::__remove_copy_if(__first
, __last
, __result
,
671 __gnu_cxx::__ops::__pred_iter(__pred
));
674 #if __cplusplus >= 201103L
676 * @brief Copy the elements of a sequence for which a predicate is true.
677 * @ingroup mutating_algorithms
678 * @param __first An input iterator.
679 * @param __last An input iterator.
680 * @param __result An output iterator.
681 * @param __pred A predicate.
682 * @return An iterator designating the end of the resulting sequence.
684 * Copies each element in the range @p [__first,__last) for which
685 * @p __pred returns true to the range beginning at @p __result.
687 * copy_if() is stable, so the relative order of elements that are
688 * copied is unchanged.
690 template<typename _InputIterator
, typename _OutputIterator
,
694 copy_if(_InputIterator __first
, _InputIterator __last
,
695 _OutputIterator __result
, _Predicate __pred
)
697 // concept requirements
698 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
699 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
700 typename iterator_traits
<_InputIterator
>::value_type
>)
701 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
702 typename iterator_traits
<_InputIterator
>::value_type
>)
703 __glibcxx_requires_valid_range(__first
, __last
);
705 for (; __first
!= __last
; ++__first
)
706 if (__pred(*__first
))
708 *__result
= *__first
;
714 template<typename _InputIterator
, typename _Size
, typename _OutputIterator
>
717 __copy_n(_InputIterator __first
, _Size __n
,
718 _OutputIterator __result
, input_iterator_tag
)
720 return std::__niter_wrap(__result
,
721 __copy_n_a(__first
, __n
,
722 std::__niter_base(__result
), true));
725 template<typename _RandomAccessIterator
, typename _Size
,
726 typename _OutputIterator
>
728 inline _OutputIterator
729 __copy_n(_RandomAccessIterator __first
, _Size __n
,
730 _OutputIterator __result
, random_access_iterator_tag
)
731 { return std::copy(__first
, __first
+ __n
, __result
); }
734 * @brief Copies the range [first,first+n) into [result,result+n).
735 * @ingroup mutating_algorithms
736 * @param __first An input iterator.
737 * @param __n The number of elements to copy.
738 * @param __result An output iterator.
741 * This inline function will boil down to a call to @c memmove whenever
742 * possible. Failing that, if random access iterators are passed, then the
743 * loop count will be known (and therefore a candidate for compiler
744 * optimizations such as unrolling).
746 template<typename _InputIterator
, typename _Size
, typename _OutputIterator
>
748 inline _OutputIterator
749 copy_n(_InputIterator __first
, _Size __n
, _OutputIterator __result
)
751 // concept requirements
752 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
753 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
754 typename iterator_traits
<_InputIterator
>::value_type
>)
756 const auto __n2
= std::__size_to_integer(__n
);
760 __glibcxx_requires_can_increment(__first
, __n2
);
761 __glibcxx_requires_can_increment(__result
, __n2
);
763 return std::__copy_n(__first
, __n2
, __result
,
764 std::__iterator_category(__first
));
768 * @brief Copy the elements of a sequence to separate output sequences
769 * depending on the truth value of a predicate.
770 * @ingroup mutating_algorithms
771 * @param __first An input iterator.
772 * @param __last An input iterator.
773 * @param __out_true An output iterator.
774 * @param __out_false An output iterator.
775 * @param __pred A predicate.
776 * @return A pair designating the ends of the resulting sequences.
778 * Copies each element in the range @p [__first,__last) for which
779 * @p __pred returns true to the range beginning at @p out_true
780 * and each element for which @p __pred returns false to @p __out_false.
782 template<typename _InputIterator
, typename _OutputIterator1
,
783 typename _OutputIterator2
, typename _Predicate
>
785 pair
<_OutputIterator1
, _OutputIterator2
>
786 partition_copy(_InputIterator __first
, _InputIterator __last
,
787 _OutputIterator1 __out_true
, _OutputIterator2 __out_false
,
790 // concept requirements
791 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
792 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator1
,
793 typename iterator_traits
<_InputIterator
>::value_type
>)
794 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator2
,
795 typename iterator_traits
<_InputIterator
>::value_type
>)
796 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
797 typename iterator_traits
<_InputIterator
>::value_type
>)
798 __glibcxx_requires_valid_range(__first
, __last
);
800 for (; __first
!= __last
; ++__first
)
801 if (__pred(*__first
))
803 *__out_true
= *__first
;
808 *__out_false
= *__first
;
812 return pair
<_OutputIterator1
, _OutputIterator2
>(__out_true
, __out_false
);
817 * @brief Remove elements from a sequence.
818 * @ingroup mutating_algorithms
819 * @param __first An input iterator.
820 * @param __last An input iterator.
821 * @param __value The value to be removed.
822 * @return An iterator designating the end of the resulting sequence.
824 * All elements equal to @p __value are removed from the range
825 * @p [__first,__last).
827 * remove() is stable, so the relative order of elements that are
828 * not removed is unchanged.
830 * Elements between the end of the resulting sequence and @p __last
831 * are still present, but their value is unspecified.
833 template<typename _ForwardIterator
, typename _Tp
>
835 inline _ForwardIterator
836 remove(_ForwardIterator __first
, _ForwardIterator __last
,
839 // concept requirements
840 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
842 __glibcxx_function_requires(_EqualOpConcept
<
843 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
844 __glibcxx_requires_valid_range(__first
, __last
);
846 return std::__remove_if(__first
, __last
,
847 __gnu_cxx::__ops::__iter_equals_val(__value
));
851 * @brief Remove elements from a sequence using a predicate.
852 * @ingroup mutating_algorithms
853 * @param __first A forward iterator.
854 * @param __last A forward iterator.
855 * @param __pred A predicate.
856 * @return An iterator designating the end of the resulting sequence.
858 * All elements for which @p __pred returns true are removed from the range
859 * @p [__first,__last).
861 * remove_if() is stable, so the relative order of elements that are
862 * not removed is unchanged.
864 * Elements between the end of the resulting sequence and @p __last
865 * are still present, but their value is unspecified.
867 template<typename _ForwardIterator
, typename _Predicate
>
869 inline _ForwardIterator
870 remove_if(_ForwardIterator __first
, _ForwardIterator __last
,
873 // concept requirements
874 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
876 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
877 typename iterator_traits
<_ForwardIterator
>::value_type
>)
878 __glibcxx_requires_valid_range(__first
, __last
);
880 return std::__remove_if(__first
, __last
,
881 __gnu_cxx::__ops::__pred_iter(__pred
));
884 template<typename _ForwardIterator
, typename _BinaryPredicate
>
887 __adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
,
888 _BinaryPredicate __binary_pred
)
890 if (__first
== __last
)
892 _ForwardIterator __next
= __first
;
893 while (++__next
!= __last
)
895 if (__binary_pred(__first
, __next
))
902 template<typename _ForwardIterator
, typename _BinaryPredicate
>
905 __unique(_ForwardIterator __first
, _ForwardIterator __last
,
906 _BinaryPredicate __binary_pred
)
908 // Skip the beginning, if already unique.
909 __first
= std::__adjacent_find(__first
, __last
, __binary_pred
);
910 if (__first
== __last
)
913 // Do the real copy work.
914 _ForwardIterator __dest
= __first
;
916 while (++__first
!= __last
)
917 if (!__binary_pred(__dest
, __first
))
918 *++__dest
= _GLIBCXX_MOVE(*__first
);
923 * @brief Remove consecutive duplicate values from a sequence.
924 * @ingroup mutating_algorithms
925 * @param __first A forward iterator.
926 * @param __last A forward iterator.
927 * @return An iterator designating the end of the resulting sequence.
929 * Removes all but the first element from each group of consecutive
930 * values that compare equal.
931 * unique() is stable, so the relative order of elements that are
932 * not removed is unchanged.
933 * Elements between the end of the resulting sequence and @p __last
934 * are still present, but their value is unspecified.
936 template<typename _ForwardIterator
>
938 inline _ForwardIterator
939 unique(_ForwardIterator __first
, _ForwardIterator __last
)
941 // concept requirements
942 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
944 __glibcxx_function_requires(_EqualityComparableConcept
<
945 typename iterator_traits
<_ForwardIterator
>::value_type
>)
946 __glibcxx_requires_valid_range(__first
, __last
);
948 return std::__unique(__first
, __last
,
949 __gnu_cxx::__ops::__iter_equal_to_iter());
953 * @brief Remove consecutive values from a sequence using a predicate.
954 * @ingroup mutating_algorithms
955 * @param __first A forward iterator.
956 * @param __last A forward iterator.
957 * @param __binary_pred A binary predicate.
958 * @return An iterator designating the end of the resulting sequence.
960 * Removes all but the first element from each group of consecutive
961 * values for which @p __binary_pred returns true.
962 * unique() is stable, so the relative order of elements that are
963 * not removed is unchanged.
964 * Elements between the end of the resulting sequence and @p __last
965 * are still present, but their value is unspecified.
967 template<typename _ForwardIterator
, typename _BinaryPredicate
>
969 inline _ForwardIterator
970 unique(_ForwardIterator __first
, _ForwardIterator __last
,
971 _BinaryPredicate __binary_pred
)
973 // concept requirements
974 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
976 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
977 typename iterator_traits
<_ForwardIterator
>::value_type
,
978 typename iterator_traits
<_ForwardIterator
>::value_type
>)
979 __glibcxx_requires_valid_range(__first
, __last
);
981 return std::__unique(__first
, __last
,
982 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
986 * This is an uglified
987 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
989 * overloaded for forward iterators and output iterator as result.
991 template<typename _ForwardIterator
, typename _OutputIterator
,
992 typename _BinaryPredicate
>
995 __unique_copy(_ForwardIterator __first
, _ForwardIterator __last
,
996 _OutputIterator __result
, _BinaryPredicate __binary_pred
,
997 forward_iterator_tag
, output_iterator_tag
)
999 // concept requirements -- iterators already checked
1000 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1001 typename iterator_traits
<_ForwardIterator
>::value_type
,
1002 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1004 _ForwardIterator __next
= __first
;
1005 *__result
= *__first
;
1006 while (++__next
!= __last
)
1007 if (!__binary_pred(__first
, __next
))
1010 *++__result
= *__first
;
1016 * This is an uglified
1017 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1019 * overloaded for input iterators and output iterator as result.
1021 template<typename _InputIterator
, typename _OutputIterator
,
1022 typename _BinaryPredicate
>
1023 _GLIBCXX20_CONSTEXPR
1025 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1026 _OutputIterator __result
, _BinaryPredicate __binary_pred
,
1027 input_iterator_tag
, output_iterator_tag
)
1029 // concept requirements -- iterators already checked
1030 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1031 typename iterator_traits
<_InputIterator
>::value_type
,
1032 typename iterator_traits
<_InputIterator
>::value_type
>)
1034 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1035 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred
))
1037 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred
);
1038 *__result
= __value
;
1039 while (++__first
!= __last
)
1040 if (!__rebound_pred(__first
, __value
))
1043 *++__result
= __value
;
1049 * This is an uglified
1050 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1052 * overloaded for input iterators and forward iterator as result.
1054 template<typename _InputIterator
, typename _ForwardIterator
,
1055 typename _BinaryPredicate
>
1056 _GLIBCXX20_CONSTEXPR
1058 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1059 _ForwardIterator __result
, _BinaryPredicate __binary_pred
,
1060 input_iterator_tag
, forward_iterator_tag
)
1062 // concept requirements -- iterators already checked
1063 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1064 typename iterator_traits
<_ForwardIterator
>::value_type
,
1065 typename iterator_traits
<_InputIterator
>::value_type
>)
1066 *__result
= *__first
;
1067 while (++__first
!= __last
)
1068 if (!__binary_pred(__result
, __first
))
1069 *++__result
= *__first
;
1074 * This is an uglified reverse(_BidirectionalIterator,
1075 * _BidirectionalIterator)
1076 * overloaded for bidirectional iterators.
1078 template<typename _BidirectionalIterator
>
1079 _GLIBCXX20_CONSTEXPR
1081 __reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1082 bidirectional_iterator_tag
)
1085 if (__first
== __last
|| __first
== --__last
)
1089 std::iter_swap(__first
, __last
);
1095 * This is an uglified reverse(_BidirectionalIterator,
1096 * _BidirectionalIterator)
1097 * overloaded for random access iterators.
1099 template<typename _RandomAccessIterator
>
1100 _GLIBCXX20_CONSTEXPR
1102 __reverse(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1103 random_access_iterator_tag
)
1105 if (__first
== __last
)
1108 while (__first
< __last
)
1110 std::iter_swap(__first
, __last
);
1117 * @brief Reverse a sequence.
1118 * @ingroup mutating_algorithms
1119 * @param __first A bidirectional iterator.
1120 * @param __last A bidirectional iterator.
1121 * @return reverse() returns no value.
1123 * Reverses the order of the elements in the range @p [__first,__last),
1124 * so that the first element becomes the last etc.
1125 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1126 * swaps @p *(__first+i) and @p *(__last-(i+1))
1128 template<typename _BidirectionalIterator
>
1129 _GLIBCXX20_CONSTEXPR
1131 reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
)
1133 // concept requirements
1134 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1135 _BidirectionalIterator
>)
1136 __glibcxx_requires_valid_range(__first
, __last
);
1137 std::__reverse(__first
, __last
, std::__iterator_category(__first
));
1141 * @brief Copy a sequence, reversing its elements.
1142 * @ingroup mutating_algorithms
1143 * @param __first A bidirectional iterator.
1144 * @param __last A bidirectional iterator.
1145 * @param __result An output iterator.
1146 * @return An iterator designating the end of the resulting sequence.
1148 * Copies the elements in the range @p [__first,__last) to the
1149 * range @p [__result,__result+(__last-__first)) such that the
1150 * order of the elements is reversed. For every @c i such that @p
1151 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1152 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1153 * The ranges @p [__first,__last) and @p
1154 * [__result,__result+(__last-__first)) must not overlap.
1156 template<typename _BidirectionalIterator
, typename _OutputIterator
>
1157 _GLIBCXX20_CONSTEXPR
1159 reverse_copy(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1160 _OutputIterator __result
)
1162 // concept requirements
1163 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
1164 _BidirectionalIterator
>)
1165 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1166 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
1167 __glibcxx_requires_valid_range(__first
, __last
);
1169 while (__first
!= __last
)
1172 *__result
= *__last
;
1179 * This is a helper function for the rotate algorithm specialized on RAIs.
1180 * It returns the greatest common divisor of two integer values.
1182 template<typename _EuclideanRingElement
>
1183 _GLIBCXX20_CONSTEXPR
1184 _EuclideanRingElement
1185 __gcd(_EuclideanRingElement __m
, _EuclideanRingElement __n
)
1189 _EuclideanRingElement __t
= __m
% __n
;
1196 _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2
)
1198 /// This is a helper function for the rotate algorithm.
1199 template<typename _ForwardIterator
>
1200 _GLIBCXX20_CONSTEXPR
1202 __rotate(_ForwardIterator __first
,
1203 _ForwardIterator __middle
,
1204 _ForwardIterator __last
,
1205 forward_iterator_tag
)
1207 if (__first
== __middle
)
1209 else if (__last
== __middle
)
1212 _ForwardIterator __first2
= __middle
;
1215 std::iter_swap(__first
, __first2
);
1218 if (__first
== __middle
)
1219 __middle
= __first2
;
1221 while (__first2
!= __last
);
1223 _ForwardIterator __ret
= __first
;
1225 __first2
= __middle
;
1227 while (__first2
!= __last
)
1229 std::iter_swap(__first
, __first2
);
1232 if (__first
== __middle
)
1233 __middle
= __first2
;
1234 else if (__first2
== __last
)
1235 __first2
= __middle
;
1240 /// This is a helper function for the rotate algorithm.
1241 template<typename _BidirectionalIterator
>
1242 _GLIBCXX20_CONSTEXPR
1243 _BidirectionalIterator
1244 __rotate(_BidirectionalIterator __first
,
1245 _BidirectionalIterator __middle
,
1246 _BidirectionalIterator __last
,
1247 bidirectional_iterator_tag
)
1249 // concept requirements
1250 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1251 _BidirectionalIterator
>)
1253 if (__first
== __middle
)
1255 else if (__last
== __middle
)
1258 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1259 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1261 while (__first
!= __middle
&& __middle
!= __last
)
1263 std::iter_swap(__first
, --__last
);
1267 if (__first
== __middle
)
1269 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1274 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1279 /// This is a helper function for the rotate algorithm.
1280 template<typename _RandomAccessIterator
>
1281 _GLIBCXX20_CONSTEXPR
1282 _RandomAccessIterator
1283 __rotate(_RandomAccessIterator __first
,
1284 _RandomAccessIterator __middle
,
1285 _RandomAccessIterator __last
,
1286 random_access_iterator_tag
)
1288 // concept requirements
1289 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1290 _RandomAccessIterator
>)
1292 if (__first
== __middle
)
1294 else if (__last
== __middle
)
1297 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
1299 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
1302 _Distance __n
= __last
- __first
;
1303 _Distance __k
= __middle
- __first
;
1305 if (__k
== __n
- __k
)
1307 std::swap_ranges(__first
, __middle
, __middle
);
1311 _RandomAccessIterator __p
= __first
;
1312 _RandomAccessIterator __ret
= __first
+ (__last
- __middle
);
1316 if (__k
< __n
- __k
)
1318 if (__is_pod(_ValueType
) && __k
== 1)
1320 _ValueType __t
= _GLIBCXX_MOVE(*__p
);
1321 _GLIBCXX_MOVE3(__p
+ 1, __p
+ __n
, __p
);
1322 *(__p
+ __n
- 1) = _GLIBCXX_MOVE(__t
);
1325 _RandomAccessIterator __q
= __p
+ __k
;
1326 for (_Distance __i
= 0; __i
< __n
- __k
; ++ __i
)
1328 std::iter_swap(__p
, __q
);
1335 std::swap(__n
, __k
);
1341 if (__is_pod(_ValueType
) && __k
== 1)
1343 _ValueType __t
= _GLIBCXX_MOVE(*(__p
+ __n
- 1));
1344 _GLIBCXX_MOVE_BACKWARD3(__p
, __p
+ __n
- 1, __p
+ __n
);
1345 *__p
= _GLIBCXX_MOVE(__t
);
1348 _RandomAccessIterator __q
= __p
+ __n
;
1350 for (_Distance __i
= 0; __i
< __n
- __k
; ++ __i
)
1354 std::iter_swap(__p
, __q
);
1359 std::swap(__n
, __k
);
1364 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1365 // DR 488. rotate throws away useful information
1367 * @brief Rotate the elements of a sequence.
1368 * @ingroup mutating_algorithms
1369 * @param __first A forward iterator.
1370 * @param __middle A forward iterator.
1371 * @param __last A forward iterator.
1372 * @return first + (last - middle).
1374 * Rotates the elements of the range @p [__first,__last) by
1375 * @p (__middle - __first) positions so that the element at @p __middle
1376 * is moved to @p __first, the element at @p __middle+1 is moved to
1377 * @p __first+1 and so on for each element in the range
1378 * @p [__first,__last).
1380 * This effectively swaps the ranges @p [__first,__middle) and
1381 * @p [__middle,__last).
1384 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1385 * for each @p n in the range @p [0,__last-__first).
1387 template<typename _ForwardIterator
>
1388 _GLIBCXX20_CONSTEXPR
1389 inline _ForwardIterator
1390 rotate(_ForwardIterator __first
, _ForwardIterator __middle
,
1391 _ForwardIterator __last
)
1393 // concept requirements
1394 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1396 __glibcxx_requires_valid_range(__first
, __middle
);
1397 __glibcxx_requires_valid_range(__middle
, __last
);
1399 return std::__rotate(__first
, __middle
, __last
,
1400 std::__iterator_category(__first
));
1403 _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2
)
1406 * @brief Copy a sequence, rotating its elements.
1407 * @ingroup mutating_algorithms
1408 * @param __first A forward iterator.
1409 * @param __middle A forward iterator.
1410 * @param __last A forward iterator.
1411 * @param __result An output iterator.
1412 * @return An iterator designating the end of the resulting sequence.
1414 * Copies the elements of the range @p [__first,__last) to the
1415 * range beginning at @result, rotating the copied elements by
1416 * @p (__middle-__first) positions so that the element at @p __middle
1417 * is moved to @p __result, the element at @p __middle+1 is moved
1418 * to @p __result+1 and so on for each element in the range @p
1422 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1423 * for each @p n in the range @p [0,__last-__first).
1425 template<typename _ForwardIterator
, typename _OutputIterator
>
1426 _GLIBCXX20_CONSTEXPR
1427 inline _OutputIterator
1428 rotate_copy(_ForwardIterator __first
, _ForwardIterator __middle
,
1429 _ForwardIterator __last
, _OutputIterator __result
)
1431 // concept requirements
1432 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1433 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1434 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1435 __glibcxx_requires_valid_range(__first
, __middle
);
1436 __glibcxx_requires_valid_range(__middle
, __last
);
1438 return std::copy(__first
, __middle
,
1439 std::copy(__middle
, __last
, __result
));
1442 /// This is a helper function...
1443 template<typename _ForwardIterator
, typename _Predicate
>
1444 _GLIBCXX20_CONSTEXPR
1446 __partition(_ForwardIterator __first
, _ForwardIterator __last
,
1447 _Predicate __pred
, forward_iterator_tag
)
1449 if (__first
== __last
)
1452 while (__pred(*__first
))
1453 if (++__first
== __last
)
1456 _ForwardIterator __next
= __first
;
1458 while (++__next
!= __last
)
1459 if (__pred(*__next
))
1461 std::iter_swap(__first
, __next
);
1468 /// This is a helper function...
1469 template<typename _BidirectionalIterator
, typename _Predicate
>
1470 _GLIBCXX20_CONSTEXPR
1471 _BidirectionalIterator
1472 __partition(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1473 _Predicate __pred
, bidirectional_iterator_tag
)
1478 if (__first
== __last
)
1480 else if (__pred(*__first
))
1486 if (__first
== __last
)
1488 else if (!bool(__pred(*__last
)))
1492 std::iter_swap(__first
, __last
);
1500 /// This is a helper function...
1501 /// Requires __first != __last and !__pred(__first)
1502 /// and __len == distance(__first, __last).
1504 /// !__pred(__first) allows us to guarantee that we don't
1505 /// move-assign an element onto itself.
1506 template<typename _ForwardIterator
, typename _Pointer
, typename _Predicate
,
1509 __stable_partition_adaptive(_ForwardIterator __first
,
1510 _ForwardIterator __last
,
1511 _Predicate __pred
, _Distance __len
,
1513 _Distance __buffer_size
)
1518 if (__len
<= __buffer_size
)
1520 _ForwardIterator __result1
= __first
;
1521 _Pointer __result2
= __buffer
;
1523 // The precondition guarantees that !__pred(__first), so
1524 // move that element to the buffer before starting the loop.
1525 // This ensures that we only call __pred once per element.
1526 *__result2
= _GLIBCXX_MOVE(*__first
);
1529 for (; __first
!= __last
; ++__first
)
1530 if (__pred(__first
))
1532 *__result1
= _GLIBCXX_MOVE(*__first
);
1537 *__result2
= _GLIBCXX_MOVE(*__first
);
1541 _GLIBCXX_MOVE3(__buffer
, __result2
, __result1
);
1545 _ForwardIterator __middle
= __first
;
1546 std::advance(__middle
, __len
/ 2);
1547 _ForwardIterator __left_split
=
1548 std::__stable_partition_adaptive(__first
, __middle
, __pred
,
1549 __len
/ 2, __buffer
,
1552 // Advance past true-predicate values to satisfy this
1553 // function's preconditions.
1554 _Distance __right_len
= __len
- __len
/ 2;
1555 _ForwardIterator __right_split
=
1556 std::__find_if_not_n(__middle
, __right_len
, __pred
);
1560 std::__stable_partition_adaptive(__right_split
, __last
, __pred
,
1562 __buffer
, __buffer_size
);
1564 return std::rotate(__left_split
, __middle
, __right_split
);
1567 template<typename _ForwardIterator
, typename _Predicate
>
1569 __stable_partition(_ForwardIterator __first
, _ForwardIterator __last
,
1572 __first
= std::__find_if_not(__first
, __last
, __pred
);
1574 if (__first
== __last
)
1577 typedef typename iterator_traits
<_ForwardIterator
>::value_type
1579 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
1582 _Temporary_buffer
<_ForwardIterator
, _ValueType
>
1583 __buf(__first
, std::distance(__first
, __last
));
1585 std::__stable_partition_adaptive(__first
, __last
, __pred
,
1586 _DistanceType(__buf
.requested_size()),
1588 _DistanceType(__buf
.size()));
1592 * @brief Move elements for which a predicate is true to the beginning
1593 * of a sequence, preserving relative ordering.
1594 * @ingroup mutating_algorithms
1595 * @param __first A forward iterator.
1596 * @param __last A forward iterator.
1597 * @param __pred A predicate functor.
1598 * @return An iterator @p middle such that @p __pred(i) is true for each
1599 * iterator @p i in the range @p [first,middle) and false for each @p i
1600 * in the range @p [middle,last).
1602 * Performs the same function as @p partition() with the additional
1603 * guarantee that the relative ordering of elements in each group is
1604 * preserved, so any two elements @p x and @p y in the range
1605 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1606 * relative ordering after calling @p stable_partition().
1608 template<typename _ForwardIterator
, typename _Predicate
>
1609 inline _ForwardIterator
1610 stable_partition(_ForwardIterator __first
, _ForwardIterator __last
,
1613 // concept requirements
1614 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1616 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1617 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1618 __glibcxx_requires_valid_range(__first
, __last
);
1620 return std::__stable_partition(__first
, __last
,
1621 __gnu_cxx::__ops::__pred_iter(__pred
));
1625 /// @cond undocumented
1627 /// This is a helper function for the sort routines.
1628 template<typename _RandomAccessIterator
, typename _Compare
>
1629 _GLIBCXX20_CONSTEXPR
1631 __heap_select(_RandomAccessIterator __first
,
1632 _RandomAccessIterator __middle
,
1633 _RandomAccessIterator __last
, _Compare __comp
)
1635 std::__make_heap(__first
, __middle
, __comp
);
1636 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
1637 if (__comp(__i
, __first
))
1638 std::__pop_heap(__first
, __middle
, __i
, __comp
);
1643 template<typename _InputIterator
, typename _RandomAccessIterator
,
1645 _GLIBCXX20_CONSTEXPR
1646 _RandomAccessIterator
1647 __partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
1648 _RandomAccessIterator __result_first
,
1649 _RandomAccessIterator __result_last
,
1652 typedef typename iterator_traits
<_InputIterator
>::value_type
1654 typedef iterator_traits
<_RandomAccessIterator
> _RItTraits
;
1655 typedef typename
_RItTraits::difference_type _DistanceType
;
1657 if (__result_first
== __result_last
)
1658 return __result_last
;
1659 _RandomAccessIterator __result_real_last
= __result_first
;
1660 while (__first
!= __last
&& __result_real_last
!= __result_last
)
1662 *__result_real_last
= *__first
;
1663 ++__result_real_last
;
1667 std::__make_heap(__result_first
, __result_real_last
, __comp
);
1668 while (__first
!= __last
)
1670 if (__comp(__first
, __result_first
))
1671 std::__adjust_heap(__result_first
, _DistanceType(0),
1672 _DistanceType(__result_real_last
1674 _InputValueType(*__first
), __comp
);
1677 std::__sort_heap(__result_first
, __result_real_last
, __comp
);
1678 return __result_real_last
;
1684 * @brief Copy the smallest elements of a sequence.
1685 * @ingroup sorting_algorithms
1686 * @param __first An iterator.
1687 * @param __last Another iterator.
1688 * @param __result_first A random-access iterator.
1689 * @param __result_last Another random-access iterator.
1690 * @return An iterator indicating the end of the resulting sequence.
1692 * Copies and sorts the smallest `N` values from the range
1693 * `[__first, __last)` to the range beginning at `__result_first`, where
1694 * the number of elements to be copied, `N`, is the smaller of
1695 * `(__last - __first)` and `(__result_last - __result_first)`.
1696 * After the sort if `i` and `j` are iterators in the range
1697 * `[__result_first,__result_first + N)` such that `i` precedes `j` then
1698 * `*j < *i` is false.
1699 * The value returned is `__result_first + N`.
1701 template<typename _InputIterator
, typename _RandomAccessIterator
>
1702 _GLIBCXX20_CONSTEXPR
1703 inline _RandomAccessIterator
1704 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
1705 _RandomAccessIterator __result_first
,
1706 _RandomAccessIterator __result_last
)
1708 #ifdef _GLIBCXX_CONCEPT_CHECKS
1709 typedef typename iterator_traits
<_InputIterator
>::value_type
1711 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
1715 // concept requirements
1716 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1717 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
1719 __glibcxx_function_requires(_LessThanOpConcept
<_InputValueType
,
1721 __glibcxx_function_requires(_LessThanComparableConcept
<_OutputValueType
>)
1722 __glibcxx_requires_valid_range(__first
, __last
);
1723 __glibcxx_requires_irreflexive(__first
, __last
);
1724 __glibcxx_requires_valid_range(__result_first
, __result_last
);
1726 return std::__partial_sort_copy(__first
, __last
,
1727 __result_first
, __result_last
,
1728 __gnu_cxx::__ops::__iter_less_iter());
1732 * @brief Copy the smallest elements of a sequence using a predicate for
1734 * @ingroup sorting_algorithms
1735 * @param __first An input iterator.
1736 * @param __last Another input iterator.
1737 * @param __result_first A random-access iterator.
1738 * @param __result_last Another random-access iterator.
1739 * @param __comp A comparison functor.
1740 * @return An iterator indicating the end of the resulting sequence.
1742 * Copies and sorts the smallest `N` values from the range
1743 * `[__first, __last)` to the range beginning at `result_first`, where
1744 * the number of elements to be copied, `N`, is the smaller of
1745 * `(__last - __first)` and `(__result_last - __result_first)`.
1746 * After the sort if `i` and `j` are iterators in the range
1747 * `[__result_first, __result_first + N)` such that `i` precedes `j` then
1748 * `__comp(*j, *i)` is false.
1749 * The value returned is `__result_first + N`.
1751 template<typename _InputIterator
, typename _RandomAccessIterator
,
1753 _GLIBCXX20_CONSTEXPR
1754 inline _RandomAccessIterator
1755 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
1756 _RandomAccessIterator __result_first
,
1757 _RandomAccessIterator __result_last
,
1760 #ifdef _GLIBCXX_CONCEPT_CHECKS
1761 typedef typename iterator_traits
<_InputIterator
>::value_type
1763 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
1767 // concept requirements
1768 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1769 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1770 _RandomAccessIterator
>)
1771 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
1773 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
1774 _InputValueType
, _OutputValueType
>)
1775 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
1776 _OutputValueType
, _OutputValueType
>)
1777 __glibcxx_requires_valid_range(__first
, __last
);
1778 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
1779 __glibcxx_requires_valid_range(__result_first
, __result_last
);
1781 return std::__partial_sort_copy(__first
, __last
,
1782 __result_first
, __result_last
,
1783 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
1786 /// @cond undocumented
1788 /// This is a helper function for the sort routine.
1789 template<typename _RandomAccessIterator
, typename _Compare
>
1790 _GLIBCXX20_CONSTEXPR
1792 __unguarded_linear_insert(_RandomAccessIterator __last
,
1795 typename iterator_traits
<_RandomAccessIterator
>::value_type
1796 __val
= _GLIBCXX_MOVE(*__last
);
1797 _RandomAccessIterator __next
= __last
;
1799 while (__comp(__val
, __next
))
1801 *__last
= _GLIBCXX_MOVE(*__next
);
1805 *__last
= _GLIBCXX_MOVE(__val
);
1808 /// This is a helper function for the sort routine.
1809 template<typename _RandomAccessIterator
, typename _Compare
>
1810 _GLIBCXX20_CONSTEXPR
1812 __insertion_sort(_RandomAccessIterator __first
,
1813 _RandomAccessIterator __last
, _Compare __comp
)
1815 if (__first
== __last
) return;
1817 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
1819 if (__comp(__i
, __first
))
1821 typename iterator_traits
<_RandomAccessIterator
>::value_type
1822 __val
= _GLIBCXX_MOVE(*__i
);
1823 _GLIBCXX_MOVE_BACKWARD3(__first
, __i
, __i
+ 1);
1824 *__first
= _GLIBCXX_MOVE(__val
);
1827 std::__unguarded_linear_insert(__i
,
1828 __gnu_cxx::__ops::__val_comp_iter(__comp
));
1832 /// This is a helper function for the sort routine.
1833 template<typename _RandomAccessIterator
, typename _Compare
>
1834 _GLIBCXX20_CONSTEXPR
1836 __unguarded_insertion_sort(_RandomAccessIterator __first
,
1837 _RandomAccessIterator __last
, _Compare __comp
)
1839 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
1840 std::__unguarded_linear_insert(__i
,
1841 __gnu_cxx::__ops::__val_comp_iter(__comp
));
1846 * This controls some aspect of the sort routines.
1848 enum { _S_threshold
= 16 };
1850 /// This is a helper function for the sort routine.
1851 template<typename _RandomAccessIterator
, typename _Compare
>
1852 _GLIBCXX20_CONSTEXPR
1854 __final_insertion_sort(_RandomAccessIterator __first
,
1855 _RandomAccessIterator __last
, _Compare __comp
)
1857 if (__last
- __first
> int(_S_threshold
))
1859 std::__insertion_sort(__first
, __first
+ int(_S_threshold
), __comp
);
1860 std::__unguarded_insertion_sort(__first
+ int(_S_threshold
), __last
,
1864 std::__insertion_sort(__first
, __last
, __comp
);
1867 /// This is a helper function...
1868 template<typename _RandomAccessIterator
, typename _Compare
>
1869 _GLIBCXX20_CONSTEXPR
1870 _RandomAccessIterator
1871 __unguarded_partition(_RandomAccessIterator __first
,
1872 _RandomAccessIterator __last
,
1873 _RandomAccessIterator __pivot
, _Compare __comp
)
1877 while (__comp(__first
, __pivot
))
1880 while (__comp(__pivot
, __last
))
1882 if (!(__first
< __last
))
1884 std::iter_swap(__first
, __last
);
1889 /// This is a helper function...
1890 template<typename _RandomAccessIterator
, typename _Compare
>
1891 _GLIBCXX20_CONSTEXPR
1892 inline _RandomAccessIterator
1893 __unguarded_partition_pivot(_RandomAccessIterator __first
,
1894 _RandomAccessIterator __last
, _Compare __comp
)
1896 _RandomAccessIterator __mid
= __first
+ (__last
- __first
) / 2;
1897 std::__move_median_to_first(__first
, __first
+ 1, __mid
, __last
- 1,
1899 return std::__unguarded_partition(__first
+ 1, __last
, __first
, __comp
);
1902 template<typename _RandomAccessIterator
, typename _Compare
>
1903 _GLIBCXX20_CONSTEXPR
1905 __partial_sort(_RandomAccessIterator __first
,
1906 _RandomAccessIterator __middle
,
1907 _RandomAccessIterator __last
,
1910 std::__heap_select(__first
, __middle
, __last
, __comp
);
1911 std::__sort_heap(__first
, __middle
, __comp
);
1914 /// This is a helper function for the sort routine.
1915 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
1916 _GLIBCXX20_CONSTEXPR
1918 __introsort_loop(_RandomAccessIterator __first
,
1919 _RandomAccessIterator __last
,
1920 _Size __depth_limit
, _Compare __comp
)
1922 while (__last
- __first
> int(_S_threshold
))
1924 if (__depth_limit
== 0)
1926 std::__partial_sort(__first
, __last
, __last
, __comp
);
1930 _RandomAccessIterator __cut
=
1931 std::__unguarded_partition_pivot(__first
, __last
, __comp
);
1932 std::__introsort_loop(__cut
, __last
, __depth_limit
, __comp
);
1939 template<typename _RandomAccessIterator
, typename _Compare
>
1940 _GLIBCXX20_CONSTEXPR
1942 __sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1945 if (__first
!= __last
)
1947 std::__introsort_loop(__first
, __last
,
1948 std::__lg(__last
- __first
) * 2,
1950 std::__final_insertion_sort(__first
, __last
, __comp
);
1954 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
1955 _GLIBCXX20_CONSTEXPR
1957 __introselect(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
1958 _RandomAccessIterator __last
, _Size __depth_limit
,
1961 while (__last
- __first
> 3)
1963 if (__depth_limit
== 0)
1965 std::__heap_select(__first
, __nth
+ 1, __last
, __comp
);
1966 // Place the nth largest element in its final position.
1967 std::iter_swap(__first
, __nth
);
1971 _RandomAccessIterator __cut
=
1972 std::__unguarded_partition_pivot(__first
, __last
, __comp
);
1978 std::__insertion_sort(__first
, __last
, __comp
);
1985 // lower_bound moved to stl_algobase.h
1988 * @brief Finds the first position in which `__val` could be inserted
1989 * without changing the ordering.
1990 * @ingroup binary_search_algorithms
1991 * @param __first An iterator to the start of a sorted range.
1992 * @param __last A past-the-end iterator for the sorted range.
1993 * @param __val The search term.
1994 * @param __comp A functor to use for comparisons.
1995 * @return An iterator pointing to the first element _not less than_
1996 * `__val`, or `end()` if every element is less than `__val`.
1997 * @ingroup binary_search_algorithms
1999 * The comparison function should have the same effects on ordering as
2000 * the function used for the initial sort.
2002 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2003 _GLIBCXX20_CONSTEXPR
2004 inline _ForwardIterator
2005 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2006 const _Tp
& __val
, _Compare __comp
)
2008 // concept requirements
2009 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2010 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2011 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
2012 __glibcxx_requires_partitioned_lower_pred(__first
, __last
,
2015 return std::__lower_bound(__first
, __last
, __val
,
2016 __gnu_cxx::__ops::__iter_comp_val(__comp
));
2019 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2020 _GLIBCXX20_CONSTEXPR
2022 __upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2023 const _Tp
& __val
, _Compare __comp
)
2025 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2028 _DistanceType __len
= std::distance(__first
, __last
);
2032 _DistanceType __half
= __len
>> 1;
2033 _ForwardIterator __middle
= __first
;
2034 std::advance(__middle
, __half
);
2035 if (__comp(__val
, __middle
))
2041 __len
= __len
- __half
- 1;
2048 * @brief Finds the last position in which @p __val could be inserted
2049 * without changing the ordering.
2050 * @ingroup binary_search_algorithms
2051 * @param __first An iterator.
2052 * @param __last Another iterator.
2053 * @param __val The search term.
2054 * @return An iterator pointing to the first element greater than @p __val,
2055 * or end() if no elements are greater than @p __val.
2056 * @ingroup binary_search_algorithms
2058 template<typename _ForwardIterator
, typename _Tp
>
2059 _GLIBCXX20_CONSTEXPR
2060 inline _ForwardIterator
2061 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2064 // concept requirements
2065 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2066 __glibcxx_function_requires(_LessThanOpConcept
<
2067 _Tp
, typename iterator_traits
<_ForwardIterator
>::value_type
>)
2068 __glibcxx_requires_partitioned_upper(__first
, __last
, __val
);
2070 return std::__upper_bound(__first
, __last
, __val
,
2071 __gnu_cxx::__ops::__val_less_iter());
2075 * @brief Finds the last position in which @p __val could be inserted
2076 * without changing the ordering.
2077 * @ingroup binary_search_algorithms
2078 * @param __first An iterator.
2079 * @param __last Another iterator.
2080 * @param __val The search term.
2081 * @param __comp A functor to use for comparisons.
2082 * @return An iterator pointing to the first element greater than @p __val,
2083 * or end() if no elements are greater than @p __val.
2084 * @ingroup binary_search_algorithms
2086 * The comparison function should have the same effects on ordering as
2087 * the function used for the initial sort.
2089 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2090 _GLIBCXX20_CONSTEXPR
2091 inline _ForwardIterator
2092 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2093 const _Tp
& __val
, _Compare __comp
)
2095 // concept requirements
2096 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2097 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2098 _Tp
, typename iterator_traits
<_ForwardIterator
>::value_type
>)
2099 __glibcxx_requires_partitioned_upper_pred(__first
, __last
,
2102 return std::__upper_bound(__first
, __last
, __val
,
2103 __gnu_cxx::__ops::__val_comp_iter(__comp
));
2106 template<typename _ForwardIterator
, typename _Tp
,
2107 typename _CompareItTp
, typename _CompareTpIt
>
2108 _GLIBCXX20_CONSTEXPR
2109 pair
<_ForwardIterator
, _ForwardIterator
>
2110 __equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
2112 _CompareItTp __comp_it_val
, _CompareTpIt __comp_val_it
)
2114 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2117 _DistanceType __len
= std::distance(__first
, __last
);
2121 _DistanceType __half
= __len
>> 1;
2122 _ForwardIterator __middle
= __first
;
2123 std::advance(__middle
, __half
);
2124 if (__comp_it_val(__middle
, __val
))
2128 __len
= __len
- __half
- 1;
2130 else if (__comp_val_it(__val
, __middle
))
2134 _ForwardIterator __left
2135 = std::__lower_bound(__first
, __middle
, __val
, __comp_it_val
);
2136 std::advance(__first
, __len
);
2137 _ForwardIterator __right
2138 = std::__upper_bound(++__middle
, __first
, __val
, __comp_val_it
);
2139 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
2142 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
2146 * @brief Finds the largest subrange in which @p __val could be inserted
2147 * at any place in it without changing the ordering.
2148 * @ingroup binary_search_algorithms
2149 * @param __first An iterator.
2150 * @param __last Another iterator.
2151 * @param __val The search term.
2152 * @return An pair of iterators defining the subrange.
2153 * @ingroup binary_search_algorithms
2155 * This is equivalent to
2157 * std::make_pair(lower_bound(__first, __last, __val),
2158 * upper_bound(__first, __last, __val))
2160 * but does not actually call those functions.
2162 template<typename _ForwardIterator
, typename _Tp
>
2163 _GLIBCXX20_CONSTEXPR
2164 inline pair
<_ForwardIterator
, _ForwardIterator
>
2165 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
2168 // concept requirements
2169 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2170 __glibcxx_function_requires(_LessThanOpConcept
<
2171 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
2172 __glibcxx_function_requires(_LessThanOpConcept
<
2173 _Tp
, typename iterator_traits
<_ForwardIterator
>::value_type
>)
2174 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
2175 __glibcxx_requires_partitioned_upper(__first
, __last
, __val
);
2177 return std::__equal_range(__first
, __last
, __val
,
2178 __gnu_cxx::__ops::__iter_less_val(),
2179 __gnu_cxx::__ops::__val_less_iter());
2183 * @brief Finds the largest subrange in which @p __val could be inserted
2184 * at any place in it without changing the ordering.
2185 * @param __first An iterator.
2186 * @param __last Another iterator.
2187 * @param __val The search term.
2188 * @param __comp A functor to use for comparisons.
2189 * @return An pair of iterators defining the subrange.
2190 * @ingroup binary_search_algorithms
2192 * This is equivalent to
2194 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2195 * upper_bound(__first, __last, __val, __comp))
2197 * but does not actually call those functions.
2199 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2200 _GLIBCXX20_CONSTEXPR
2201 inline pair
<_ForwardIterator
, _ForwardIterator
>
2202 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
2203 const _Tp
& __val
, _Compare __comp
)
2205 // concept requirements
2206 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2207 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2208 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
2209 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2210 _Tp
, typename iterator_traits
<_ForwardIterator
>::value_type
>)
2211 __glibcxx_requires_partitioned_lower_pred(__first
, __last
,
2213 __glibcxx_requires_partitioned_upper_pred(__first
, __last
,
2216 return std::__equal_range(__first
, __last
, __val
,
2217 __gnu_cxx::__ops::__iter_comp_val(__comp
),
2218 __gnu_cxx::__ops::__val_comp_iter(__comp
));
2222 * @brief Determines whether an element exists in a range.
2223 * @ingroup binary_search_algorithms
2224 * @param __first An iterator.
2225 * @param __last Another iterator.
2226 * @param __val The search term.
2227 * @return True if @p __val (or its equivalent) is in [@p
2228 * __first,@p __last ].
2230 * Note that this does not actually return an iterator to @p __val. For
2231 * that, use std::find or a container's specialized find member functions.
2233 template<typename _ForwardIterator
, typename _Tp
>
2234 _GLIBCXX20_CONSTEXPR
2236 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
2239 // concept requirements
2240 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2241 __glibcxx_function_requires(_LessThanOpConcept
<
2242 _Tp
, typename iterator_traits
<_ForwardIterator
>::value_type
>)
2243 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
2244 __glibcxx_requires_partitioned_upper(__first
, __last
, __val
);
2246 _ForwardIterator __i
2247 = std::__lower_bound(__first
, __last
, __val
,
2248 __gnu_cxx::__ops::__iter_less_val());
2249 return __i
!= __last
&& !(__val
< *__i
);
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 * @param __comp A functor to use for comparisons.
2259 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
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.
2264 * The comparison function should have the same effects on ordering as
2265 * the function used for the initial sort.
2267 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2268 _GLIBCXX20_CONSTEXPR
2270 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
2271 const _Tp
& __val
, _Compare __comp
)
2273 // concept requirements
2274 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2275 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2276 _Tp
, typename iterator_traits
<_ForwardIterator
>::value_type
>)
2277 __glibcxx_requires_partitioned_lower_pred(__first
, __last
,
2279 __glibcxx_requires_partitioned_upper_pred(__first
, __last
,
2282 _ForwardIterator __i
2283 = std::__lower_bound(__first
, __last
, __val
,
2284 __gnu_cxx::__ops::__iter_comp_val(__comp
));
2285 return __i
!= __last
&& !bool(__comp(__val
, *__i
));
2290 /// This is a helper function for the __merge_adaptive routines.
2291 template<typename _InputIterator1
, typename _InputIterator2
,
2292 typename _OutputIterator
, typename _Compare
>
2294 __move_merge_adaptive(_InputIterator1 __first1
, _InputIterator1 __last1
,
2295 _InputIterator2 __first2
, _InputIterator2 __last2
,
2296 _OutputIterator __result
, _Compare __comp
)
2298 while (__first1
!= __last1
&& __first2
!= __last2
)
2300 if (__comp(__first2
, __first1
))
2302 *__result
= _GLIBCXX_MOVE(*__first2
);
2307 *__result
= _GLIBCXX_MOVE(*__first1
);
2312 if (__first1
!= __last1
)
2313 _GLIBCXX_MOVE3(__first1
, __last1
, __result
);
2316 /// This is a helper function for the __merge_adaptive routines.
2317 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
2318 typename _BidirectionalIterator3
, typename _Compare
>
2320 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1
,
2321 _BidirectionalIterator1 __last1
,
2322 _BidirectionalIterator2 __first2
,
2323 _BidirectionalIterator2 __last2
,
2324 _BidirectionalIterator3 __result
,
2327 if (__first1
== __last1
)
2329 _GLIBCXX_MOVE_BACKWARD3(__first2
, __last2
, __result
);
2332 else if (__first2
== __last2
)
2339 if (__comp(__last2
, __last1
))
2341 *--__result
= _GLIBCXX_MOVE(*__last1
);
2342 if (__first1
== __last1
)
2344 _GLIBCXX_MOVE_BACKWARD3(__first2
, ++__last2
, __result
);
2351 *--__result
= _GLIBCXX_MOVE(*__last2
);
2352 if (__first2
== __last2
)
2359 /// This is a helper function for the merge routines.
2360 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
2362 _BidirectionalIterator1
2363 __rotate_adaptive(_BidirectionalIterator1 __first
,
2364 _BidirectionalIterator1 __middle
,
2365 _BidirectionalIterator1 __last
,
2366 _Distance __len1
, _Distance __len2
,
2367 _BidirectionalIterator2 __buffer
,
2368 _Distance __buffer_size
)
2370 _BidirectionalIterator2 __buffer_end
;
2371 if (__len1
> __len2
&& __len2
<= __buffer_size
)
2375 __buffer_end
= _GLIBCXX_MOVE3(__middle
, __last
, __buffer
);
2376 _GLIBCXX_MOVE_BACKWARD3(__first
, __middle
, __last
);
2377 return _GLIBCXX_MOVE3(__buffer
, __buffer_end
, __first
);
2382 else if (__len1
<= __buffer_size
)
2386 __buffer_end
= _GLIBCXX_MOVE3(__first
, __middle
, __buffer
);
2387 _GLIBCXX_MOVE3(__middle
, __last
, __first
);
2388 return _GLIBCXX_MOVE_BACKWARD3(__buffer
, __buffer_end
, __last
);
2394 return std::rotate(__first
, __middle
, __last
);
2397 /// This is a helper function for the merge routines.
2398 template<typename _BidirectionalIterator
, typename _Distance
,
2399 typename _Pointer
, typename _Compare
>
2401 __merge_adaptive(_BidirectionalIterator __first
,
2402 _BidirectionalIterator __middle
,
2403 _BidirectionalIterator __last
,
2404 _Distance __len1
, _Distance __len2
,
2405 _Pointer __buffer
, _Compare __comp
)
2407 if (__len1
<= __len2
)
2409 _Pointer __buffer_end
= _GLIBCXX_MOVE3(__first
, __middle
, __buffer
);
2410 std::__move_merge_adaptive(__buffer
, __buffer_end
, __middle
, __last
,
2415 _Pointer __buffer_end
= _GLIBCXX_MOVE3(__middle
, __last
, __buffer
);
2416 std::__move_merge_adaptive_backward(__first
, __middle
, __buffer
,
2417 __buffer_end
, __last
, __comp
);
2421 template<typename _BidirectionalIterator
, typename _Distance
,
2422 typename _Pointer
, typename _Compare
>
2424 __merge_adaptive_resize(_BidirectionalIterator __first
,
2425 _BidirectionalIterator __middle
,
2426 _BidirectionalIterator __last
,
2427 _Distance __len1
, _Distance __len2
,
2428 _Pointer __buffer
, _Distance __buffer_size
,
2431 if (__len1
<= __buffer_size
|| __len2
<= __buffer_size
)
2432 std::__merge_adaptive(__first
, __middle
, __last
,
2433 __len1
, __len2
, __buffer
, __comp
);
2436 _BidirectionalIterator __first_cut
= __first
;
2437 _BidirectionalIterator __second_cut
= __middle
;
2438 _Distance __len11
= 0;
2439 _Distance __len22
= 0;
2440 if (__len1
> __len2
)
2442 __len11
= __len1
/ 2;
2443 std::advance(__first_cut
, __len11
);
2445 = std::__lower_bound(__middle
, __last
, *__first_cut
,
2446 __gnu_cxx::__ops::__iter_comp_val(__comp
));
2447 __len22
= std::distance(__middle
, __second_cut
);
2451 __len22
= __len2
/ 2;
2452 std::advance(__second_cut
, __len22
);
2454 = std::__upper_bound(__first
, __middle
, *__second_cut
,
2455 __gnu_cxx::__ops::__val_comp_iter(__comp
));
2456 __len11
= std::distance(__first
, __first_cut
);
2459 _BidirectionalIterator __new_middle
2460 = std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
2461 __len1
- __len11
, __len22
,
2462 __buffer
, __buffer_size
);
2463 std::__merge_adaptive_resize(__first
, __first_cut
, __new_middle
,
2465 __buffer
, __buffer_size
, __comp
);
2466 std::__merge_adaptive_resize(__new_middle
, __second_cut
, __last
,
2467 __len1
- __len11
, __len2
- __len22
,
2468 __buffer
, __buffer_size
, __comp
);
2472 /// This is a helper function for the merge routines.
2473 template<typename _BidirectionalIterator
, typename _Distance
,
2476 __merge_without_buffer(_BidirectionalIterator __first
,
2477 _BidirectionalIterator __middle
,
2478 _BidirectionalIterator __last
,
2479 _Distance __len1
, _Distance __len2
,
2482 if (__len1
== 0 || __len2
== 0)
2485 if (__len1
+ __len2
== 2)
2487 if (__comp(__middle
, __first
))
2488 std::iter_swap(__first
, __middle
);
2492 _BidirectionalIterator __first_cut
= __first
;
2493 _BidirectionalIterator __second_cut
= __middle
;
2494 _Distance __len11
= 0;
2495 _Distance __len22
= 0;
2496 if (__len1
> __len2
)
2498 __len11
= __len1
/ 2;
2499 std::advance(__first_cut
, __len11
);
2501 = std::__lower_bound(__middle
, __last
, *__first_cut
,
2502 __gnu_cxx::__ops::__iter_comp_val(__comp
));
2503 __len22
= std::distance(__middle
, __second_cut
);
2507 __len22
= __len2
/ 2;
2508 std::advance(__second_cut
, __len22
);
2510 = std::__upper_bound(__first
, __middle
, *__second_cut
,
2511 __gnu_cxx::__ops::__val_comp_iter(__comp
));
2512 __len11
= std::distance(__first
, __first_cut
);
2515 _BidirectionalIterator __new_middle
2516 = std::rotate(__first_cut
, __middle
, __second_cut
);
2517 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
2518 __len11
, __len22
, __comp
);
2519 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
2520 __len1
- __len11
, __len2
- __len22
, __comp
);
2523 template<typename _BidirectionalIterator
, typename _Compare
>
2525 __inplace_merge(_BidirectionalIterator __first
,
2526 _BidirectionalIterator __middle
,
2527 _BidirectionalIterator __last
,
2530 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
2532 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
2535 if (__first
== __middle
|| __middle
== __last
)
2538 const _DistanceType __len1
= std::distance(__first
, __middle
);
2539 const _DistanceType __len2
= std::distance(__middle
, __last
);
2542 typedef _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> _TmpBuf
;
2543 // __merge_adaptive will use a buffer for the smaller of
2544 // [first,middle) and [middle,last).
2545 _TmpBuf
__buf(__first
, std::min(__len1
, __len2
));
2547 if (__builtin_expect(__buf
.size() == __buf
.requested_size(), true))
2548 std::__merge_adaptive
2549 (__first
, __middle
, __last
, __len1
, __len2
, __buf
.begin(), __comp
);
2550 else if (__builtin_expect(__buf
.begin() == 0, false))
2551 std::__merge_without_buffer
2552 (__first
, __middle
, __last
, __len1
, __len2
, __comp
);
2554 std::__merge_adaptive_resize
2555 (__first
, __middle
, __last
, __len1
, __len2
, __buf
.begin(),
2556 _DistanceType(__buf
.size()), __comp
);
2558 std::__merge_without_buffer
2559 (__first
, __middle
, __last
, __len1
, __len2
, __comp
);
2564 * @brief Merges two sorted ranges in place.
2565 * @ingroup sorting_algorithms
2566 * @param __first An iterator.
2567 * @param __middle Another iterator.
2568 * @param __last Another iterator.
2571 * Merges two sorted and consecutive ranges, [__first,__middle) and
2572 * [__middle,__last), and puts the result in [__first,__last). The
2573 * output will be sorted. The sort is @e stable, that is, for
2574 * equivalent elements in the two ranges, elements from the first
2575 * range will always come before elements from the second.
2577 * If enough additional memory is available, this takes (__last-__first)-1
2578 * comparisons. Otherwise an NlogN algorithm is used, where N is
2579 * distance(__first,__last).
2581 template<typename _BidirectionalIterator
>
2583 inplace_merge(_BidirectionalIterator __first
,
2584 _BidirectionalIterator __middle
,
2585 _BidirectionalIterator __last
)
2587 // concept requirements
2588 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
2589 _BidirectionalIterator
>)
2590 __glibcxx_function_requires(_LessThanComparableConcept
<
2591 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
2592 __glibcxx_requires_sorted(__first
, __middle
);
2593 __glibcxx_requires_sorted(__middle
, __last
);
2594 __glibcxx_requires_irreflexive(__first
, __last
);
2596 std::__inplace_merge(__first
, __middle
, __last
,
2597 __gnu_cxx::__ops::__iter_less_iter());
2601 * @brief Merges two sorted ranges in place.
2602 * @ingroup sorting_algorithms
2603 * @param __first An iterator.
2604 * @param __middle Another iterator.
2605 * @param __last Another iterator.
2606 * @param __comp A functor to use for comparisons.
2609 * Merges two sorted and consecutive ranges, [__first,__middle) and
2610 * [middle,last), and puts the result in [__first,__last). The output will
2611 * be sorted. The sort is @e stable, that is, for equivalent
2612 * elements in the two ranges, elements from the first range will always
2613 * come before elements from the second.
2615 * If enough additional memory is available, this takes (__last-__first)-1
2616 * comparisons. Otherwise an NlogN algorithm is used, where N is
2617 * distance(__first,__last).
2619 * The comparison function should have the same effects on ordering as
2620 * the function used for the initial sort.
2622 template<typename _BidirectionalIterator
, typename _Compare
>
2624 inplace_merge(_BidirectionalIterator __first
,
2625 _BidirectionalIterator __middle
,
2626 _BidirectionalIterator __last
,
2629 // concept requirements
2630 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
2631 _BidirectionalIterator
>)
2632 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2633 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
2634 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
2635 __glibcxx_requires_sorted_pred(__first
, __middle
, __comp
);
2636 __glibcxx_requires_sorted_pred(__middle
, __last
, __comp
);
2637 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
2639 std::__inplace_merge(__first
, __middle
, __last
,
2640 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
2644 /// This is a helper function for the __merge_sort_loop routines.
2645 template<typename _InputIterator
, typename _OutputIterator
,
2648 __move_merge(_InputIterator __first1
, _InputIterator __last1
,
2649 _InputIterator __first2
, _InputIterator __last2
,
2650 _OutputIterator __result
, _Compare __comp
)
2652 while (__first1
!= __last1
&& __first2
!= __last2
)
2654 if (__comp(__first2
, __first1
))
2656 *__result
= _GLIBCXX_MOVE(*__first2
);
2661 *__result
= _GLIBCXX_MOVE(*__first1
);
2666 return _GLIBCXX_MOVE3(__first2
, __last2
,
2667 _GLIBCXX_MOVE3(__first1
, __last1
,
2671 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
2672 typename _Distance
, typename _Compare
>
2674 __merge_sort_loop(_RandomAccessIterator1 __first
,
2675 _RandomAccessIterator1 __last
,
2676 _RandomAccessIterator2 __result
, _Distance __step_size
,
2679 const _Distance __two_step
= 2 * __step_size
;
2681 while (__last
- __first
>= __two_step
)
2683 __result
= std::__move_merge(__first
, __first
+ __step_size
,
2684 __first
+ __step_size
,
2685 __first
+ __two_step
,
2687 __first
+= __two_step
;
2689 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
2691 std::__move_merge(__first
, __first
+ __step_size
,
2692 __first
+ __step_size
, __last
, __result
, __comp
);
2695 template<typename _RandomAccessIterator
, typename _Distance
,
2697 _GLIBCXX20_CONSTEXPR
2699 __chunk_insertion_sort(_RandomAccessIterator __first
,
2700 _RandomAccessIterator __last
,
2701 _Distance __chunk_size
, _Compare __comp
)
2703 while (__last
- __first
>= __chunk_size
)
2705 std::__insertion_sort(__first
, __first
+ __chunk_size
, __comp
);
2706 __first
+= __chunk_size
;
2708 std::__insertion_sort(__first
, __last
, __comp
);
2711 enum { _S_chunk_size
= 7 };
2713 template<typename _RandomAccessIterator
, typename _Pointer
, typename _Compare
>
2715 __merge_sort_with_buffer(_RandomAccessIterator __first
,
2716 _RandomAccessIterator __last
,
2717 _Pointer __buffer
, _Compare __comp
)
2719 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2722 const _Distance __len
= __last
- __first
;
2723 const _Pointer __buffer_last
= __buffer
+ __len
;
2725 _Distance __step_size
= _S_chunk_size
;
2726 std::__chunk_insertion_sort(__first
, __last
, __step_size
, __comp
);
2728 while (__step_size
< __len
)
2730 std::__merge_sort_loop(__first
, __last
, __buffer
,
2731 __step_size
, __comp
);
2733 std::__merge_sort_loop(__buffer
, __buffer_last
, __first
,
2734 __step_size
, __comp
);
2739 template<typename _RandomAccessIterator
, typename _Pointer
, typename _Compare
>
2741 __stable_sort_adaptive(_RandomAccessIterator __first
,
2742 _RandomAccessIterator __middle
,
2743 _RandomAccessIterator __last
,
2744 _Pointer __buffer
, _Compare __comp
)
2746 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
, __comp
);
2747 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
, __comp
);
2749 std::__merge_adaptive(__first
, __middle
, __last
,
2750 __middle
- __first
, __last
- __middle
,
2754 template<typename _RandomAccessIterator
, typename _Pointer
,
2755 typename _Distance
, typename _Compare
>
2757 __stable_sort_adaptive_resize(_RandomAccessIterator __first
,
2758 _RandomAccessIterator __last
,
2759 _Pointer __buffer
, _Distance __buffer_size
,
2762 const _Distance __len
= (__last
- __first
+ 1) / 2;
2763 const _RandomAccessIterator __middle
= __first
+ __len
;
2764 if (__len
> __buffer_size
)
2766 std::__stable_sort_adaptive_resize(__first
, __middle
, __buffer
,
2767 __buffer_size
, __comp
);
2768 std::__stable_sort_adaptive_resize(__middle
, __last
, __buffer
,
2769 __buffer_size
, __comp
);
2770 std::__merge_adaptive_resize(__first
, __middle
, __last
,
2771 _Distance(__middle
- __first
),
2772 _Distance(__last
- __middle
),
2773 __buffer
, __buffer_size
,
2777 std::__stable_sort_adaptive(__first
, __middle
, __last
,
2781 /// This is a helper function for the stable sorting routines.
2782 template<typename _RandomAccessIterator
, typename _Compare
>
2784 __inplace_stable_sort(_RandomAccessIterator __first
,
2785 _RandomAccessIterator __last
, _Compare __comp
)
2787 if (__last
- __first
< 15)
2789 std::__insertion_sort(__first
, __last
, __comp
);
2792 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
2793 std::__inplace_stable_sort(__first
, __middle
, __comp
);
2794 std::__inplace_stable_sort(__middle
, __last
, __comp
);
2795 std::__merge_without_buffer(__first
, __middle
, __last
,
2803 // Set algorithms: includes, set_union, set_intersection, set_difference,
2804 // set_symmetric_difference. All of these algorithms have the precondition
2805 // that their input ranges are sorted and the postcondition that their output
2806 // ranges are sorted.
2808 template<typename _InputIterator1
, typename _InputIterator2
,
2810 _GLIBCXX20_CONSTEXPR
2812 __includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
2813 _InputIterator2 __first2
, _InputIterator2 __last2
,
2816 while (__first1
!= __last1
&& __first2
!= __last2
)
2818 if (__comp(__first2
, __first1
))
2820 if (!__comp(__first1
, __first2
))
2825 return __first2
== __last2
;
2829 * @brief Determines whether all elements of a sequence exists in a range.
2830 * @param __first1 Start of search range.
2831 * @param __last1 End of search range.
2832 * @param __first2 Start of sequence
2833 * @param __last2 End of sequence.
2834 * @return True if each element in [__first2,__last2) is contained in order
2835 * within [__first1,__last1). False otherwise.
2836 * @ingroup set_algorithms
2838 * This operation expects both [__first1,__last1) and
2839 * [__first2,__last2) to be sorted. Searches for the presence of
2840 * each element in [__first2,__last2) within [__first1,__last1).
2841 * The iterators over each range only move forward, so this is a
2842 * linear algorithm. If an element in [__first2,__last2) is not
2843 * found before the search iterator reaches @p __last2, false is
2846 template<typename _InputIterator1
, typename _InputIterator2
>
2847 _GLIBCXX20_CONSTEXPR
2849 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
2850 _InputIterator2 __first2
, _InputIterator2 __last2
)
2852 // concept requirements
2853 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
2854 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
2855 __glibcxx_function_requires(_LessThanOpConcept
<
2856 typename iterator_traits
<_InputIterator1
>::value_type
,
2857 typename iterator_traits
<_InputIterator2
>::value_type
>)
2858 __glibcxx_function_requires(_LessThanOpConcept
<
2859 typename iterator_traits
<_InputIterator2
>::value_type
,
2860 typename iterator_traits
<_InputIterator1
>::value_type
>)
2861 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
2862 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
2863 __glibcxx_requires_irreflexive2(__first1
, __last1
);
2864 __glibcxx_requires_irreflexive2(__first2
, __last2
);
2866 return std::__includes(__first1
, __last1
, __first2
, __last2
,
2867 __gnu_cxx::__ops::__iter_less_iter());
2871 * @brief Determines whether all elements of a sequence exists in a range
2873 * @ingroup set_algorithms
2874 * @param __first1 Start of search range.
2875 * @param __last1 End of search range.
2876 * @param __first2 Start of sequence
2877 * @param __last2 End of sequence.
2878 * @param __comp Comparison function to use.
2879 * @return True if each element in [__first2,__last2) is contained
2880 * in order within [__first1,__last1) according to comp. False
2881 * otherwise. @ingroup set_algorithms
2883 * This operation expects both [__first1,__last1) and
2884 * [__first2,__last2) to be sorted. Searches for the presence of
2885 * each element in [__first2,__last2) within [__first1,__last1),
2886 * using comp to decide. The iterators over each range only move
2887 * forward, so this is a linear algorithm. If an element in
2888 * [__first2,__last2) is not found before the search iterator
2889 * reaches @p __last2, false is returned.
2891 template<typename _InputIterator1
, typename _InputIterator2
,
2893 _GLIBCXX20_CONSTEXPR
2895 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
2896 _InputIterator2 __first2
, _InputIterator2 __last2
,
2899 // concept requirements
2900 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
2901 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
2902 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2903 typename iterator_traits
<_InputIterator1
>::value_type
,
2904 typename iterator_traits
<_InputIterator2
>::value_type
>)
2905 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2906 typename iterator_traits
<_InputIterator2
>::value_type
,
2907 typename iterator_traits
<_InputIterator1
>::value_type
>)
2908 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
2909 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
2910 __glibcxx_requires_irreflexive_pred2(__first1
, __last1
, __comp
);
2911 __glibcxx_requires_irreflexive_pred2(__first2
, __last2
, __comp
);
2913 return std::__includes(__first1
, __last1
, __first2
, __last2
,
2914 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
2923 // set_symmetric_difference
2927 template<typename _BidirectionalIterator
, typename _Compare
>
2928 _GLIBCXX20_CONSTEXPR
2930 __next_permutation(_BidirectionalIterator __first
,
2931 _BidirectionalIterator __last
, _Compare __comp
)
2933 if (__first
== __last
)
2935 _BidirectionalIterator __i
= __first
;
2944 _BidirectionalIterator __ii
= __i
;
2946 if (__comp(__i
, __ii
))
2948 _BidirectionalIterator __j
= __last
;
2949 while (!__comp(__i
, --__j
))
2951 std::iter_swap(__i
, __j
);
2952 std::__reverse(__ii
, __last
,
2953 std::__iterator_category(__first
));
2958 std::__reverse(__first
, __last
,
2959 std::__iterator_category(__first
));
2966 * @brief Permute range into the next @e dictionary ordering.
2967 * @ingroup sorting_algorithms
2968 * @param __first Start of range.
2969 * @param __last End of range.
2970 * @return False if wrapped to first permutation, true otherwise.
2972 * Treats all permutations of the range as a set of @e dictionary sorted
2973 * sequences. Permutes the current sequence into the next one of this set.
2974 * Returns true if there are more sequences to generate. If the sequence
2975 * is the largest of the set, the smallest is generated and false returned.
2977 template<typename _BidirectionalIterator
>
2978 _GLIBCXX20_CONSTEXPR
2980 next_permutation(_BidirectionalIterator __first
,
2981 _BidirectionalIterator __last
)
2983 // concept requirements
2984 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
2985 _BidirectionalIterator
>)
2986 __glibcxx_function_requires(_LessThanComparableConcept
<
2987 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
2988 __glibcxx_requires_valid_range(__first
, __last
);
2989 __glibcxx_requires_irreflexive(__first
, __last
);
2991 return std::__next_permutation
2992 (__first
, __last
, __gnu_cxx::__ops::__iter_less_iter());
2996 * @brief Permute range into the next @e dictionary ordering using
2997 * comparison functor.
2998 * @ingroup sorting_algorithms
2999 * @param __first Start of range.
3000 * @param __last End of range.
3001 * @param __comp A comparison functor.
3002 * @return False if wrapped to first permutation, true otherwise.
3004 * Treats all permutations of the range [__first,__last) as a set of
3005 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3006 * sequence into the next one of this set. Returns true if there are more
3007 * sequences to generate. If the sequence is the largest of the set, the
3008 * smallest is generated and false returned.
3010 template<typename _BidirectionalIterator
, typename _Compare
>
3011 _GLIBCXX20_CONSTEXPR
3013 next_permutation(_BidirectionalIterator __first
,
3014 _BidirectionalIterator __last
, _Compare __comp
)
3016 // concept requirements
3017 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
3018 _BidirectionalIterator
>)
3019 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3020 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
3021 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
3022 __glibcxx_requires_valid_range(__first
, __last
);
3023 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
3025 return std::__next_permutation
3026 (__first
, __last
, __gnu_cxx::__ops::__iter_comp_iter(__comp
));
3029 template<typename _BidirectionalIterator
, typename _Compare
>
3030 _GLIBCXX20_CONSTEXPR
3032 __prev_permutation(_BidirectionalIterator __first
,
3033 _BidirectionalIterator __last
, _Compare __comp
)
3035 if (__first
== __last
)
3037 _BidirectionalIterator __i
= __first
;
3046 _BidirectionalIterator __ii
= __i
;
3048 if (__comp(__ii
, __i
))
3050 _BidirectionalIterator __j
= __last
;
3051 while (!__comp(--__j
, __i
))
3053 std::iter_swap(__i
, __j
);
3054 std::__reverse(__ii
, __last
,
3055 std::__iterator_category(__first
));
3060 std::__reverse(__first
, __last
,
3061 std::__iterator_category(__first
));
3068 * @brief Permute range into the previous @e dictionary ordering.
3069 * @ingroup sorting_algorithms
3070 * @param __first Start of range.
3071 * @param __last End of range.
3072 * @return False if wrapped to last permutation, true otherwise.
3074 * Treats all permutations of the range as a set of @e dictionary sorted
3075 * sequences. Permutes the current sequence into the previous one of this
3076 * set. Returns true if there are more sequences to generate. If the
3077 * sequence is the smallest of the set, the largest is generated and false
3080 template<typename _BidirectionalIterator
>
3081 _GLIBCXX20_CONSTEXPR
3083 prev_permutation(_BidirectionalIterator __first
,
3084 _BidirectionalIterator __last
)
3086 // concept requirements
3087 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
3088 _BidirectionalIterator
>)
3089 __glibcxx_function_requires(_LessThanComparableConcept
<
3090 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
3091 __glibcxx_requires_valid_range(__first
, __last
);
3092 __glibcxx_requires_irreflexive(__first
, __last
);
3094 return std::__prev_permutation(__first
, __last
,
3095 __gnu_cxx::__ops::__iter_less_iter());
3099 * @brief Permute range into the previous @e dictionary ordering using
3100 * comparison functor.
3101 * @ingroup sorting_algorithms
3102 * @param __first Start of range.
3103 * @param __last End of range.
3104 * @param __comp A comparison functor.
3105 * @return False if wrapped to last permutation, true otherwise.
3107 * Treats all permutations of the range [__first,__last) as a set of
3108 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3109 * sequence into the previous one of this set. Returns true if there are
3110 * more sequences to generate. If the sequence is the smallest of the set,
3111 * the largest is generated and false returned.
3113 template<typename _BidirectionalIterator
, typename _Compare
>
3114 _GLIBCXX20_CONSTEXPR
3116 prev_permutation(_BidirectionalIterator __first
,
3117 _BidirectionalIterator __last
, _Compare __comp
)
3119 // concept requirements
3120 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
3121 _BidirectionalIterator
>)
3122 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3123 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
3124 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
3125 __glibcxx_requires_valid_range(__first
, __last
);
3126 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
3128 return std::__prev_permutation(__first
, __last
,
3129 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
3135 template<typename _InputIterator
, typename _OutputIterator
,
3136 typename _Predicate
, typename _Tp
>
3137 _GLIBCXX20_CONSTEXPR
3139 __replace_copy_if(_InputIterator __first
, _InputIterator __last
,
3140 _OutputIterator __result
,
3141 _Predicate __pred
, const _Tp
& __new_value
)
3143 for (; __first
!= __last
; ++__first
, (void)++__result
)
3144 if (__pred(__first
))
3145 *__result
= __new_value
;
3147 *__result
= *__first
;
3152 * @brief Copy a sequence, replacing each element of one value with another
3154 * @param __first An input iterator.
3155 * @param __last An input iterator.
3156 * @param __result An output iterator.
3157 * @param __old_value The value to be replaced.
3158 * @param __new_value The replacement value.
3159 * @return The end of the output sequence, @p result+(last-first).
3161 * Copies each element in the input range @p [__first,__last) to the
3162 * output range @p [__result,__result+(__last-__first)) replacing elements
3163 * equal to @p __old_value with @p __new_value.
3165 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
3166 _GLIBCXX20_CONSTEXPR
3167 inline _OutputIterator
3168 replace_copy(_InputIterator __first
, _InputIterator __last
,
3169 _OutputIterator __result
,
3170 const _Tp
& __old_value
, const _Tp
& __new_value
)
3172 // concept requirements
3173 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3174 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3175 typename iterator_traits
<_InputIterator
>::value_type
>)
3176 __glibcxx_function_requires(_EqualOpConcept
<
3177 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
3178 __glibcxx_requires_valid_range(__first
, __last
);
3180 return std::__replace_copy_if(__first
, __last
, __result
,
3181 __gnu_cxx::__ops::__iter_equals_val(__old_value
),
3186 * @brief Copy a sequence, replacing each value for which a predicate
3187 * returns true with another value.
3188 * @ingroup mutating_algorithms
3189 * @param __first An input iterator.
3190 * @param __last An input iterator.
3191 * @param __result An output iterator.
3192 * @param __pred A predicate.
3193 * @param __new_value The replacement value.
3194 * @return The end of the output sequence, @p __result+(__last-__first).
3196 * Copies each element in the range @p [__first,__last) to the range
3197 * @p [__result,__result+(__last-__first)) replacing elements for which
3198 * @p __pred returns true with @p __new_value.
3200 template<typename _InputIterator
, typename _OutputIterator
,
3201 typename _Predicate
, typename _Tp
>
3202 _GLIBCXX20_CONSTEXPR
3203 inline _OutputIterator
3204 replace_copy_if(_InputIterator __first
, _InputIterator __last
,
3205 _OutputIterator __result
,
3206 _Predicate __pred
, const _Tp
& __new_value
)
3208 // concept requirements
3209 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3210 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3211 typename iterator_traits
<_InputIterator
>::value_type
>)
3212 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
3213 typename iterator_traits
<_InputIterator
>::value_type
>)
3214 __glibcxx_requires_valid_range(__first
, __last
);
3216 return std::__replace_copy_if(__first
, __last
, __result
,
3217 __gnu_cxx::__ops::__pred_iter(__pred
),
3221 #if __cplusplus >= 201103L
3223 * @brief Determines whether the elements of a sequence are sorted.
3224 * @ingroup sorting_algorithms
3225 * @param __first An iterator.
3226 * @param __last Another iterator.
3227 * @return True if the elements are sorted, false otherwise.
3229 template<typename _ForwardIterator
>
3230 _GLIBCXX20_CONSTEXPR
3232 is_sorted(_ForwardIterator __first
, _ForwardIterator __last
)
3233 { return std::is_sorted_until(__first
, __last
) == __last
; }
3236 * @brief Determines whether the elements of a sequence are sorted
3237 * according to a comparison functor.
3238 * @ingroup sorting_algorithms
3239 * @param __first An iterator.
3240 * @param __last Another iterator.
3241 * @param __comp A comparison functor.
3242 * @return True if the elements are sorted, false otherwise.
3244 template<typename _ForwardIterator
, typename _Compare
>
3245 _GLIBCXX20_CONSTEXPR
3247 is_sorted(_ForwardIterator __first
, _ForwardIterator __last
,
3249 { return std::is_sorted_until(__first
, __last
, __comp
) == __last
; }
3251 template<typename _ForwardIterator
, typename _Compare
>
3252 _GLIBCXX20_CONSTEXPR
3254 __is_sorted_until(_ForwardIterator __first
, _ForwardIterator __last
,
3257 if (__first
== __last
)
3260 _ForwardIterator __next
= __first
;
3261 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
3262 if (__comp(__next
, __first
))
3268 * @brief Determines the end of a sorted sequence.
3269 * @ingroup sorting_algorithms
3270 * @param __first An iterator.
3271 * @param __last Another iterator.
3272 * @return An iterator pointing to the last iterator i in [__first, __last)
3273 * for which the range [__first, i) is sorted.
3275 template<typename _ForwardIterator
>
3276 _GLIBCXX20_CONSTEXPR
3277 inline _ForwardIterator
3278 is_sorted_until(_ForwardIterator __first
, _ForwardIterator __last
)
3280 // concept requirements
3281 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3282 __glibcxx_function_requires(_LessThanComparableConcept
<
3283 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3284 __glibcxx_requires_valid_range(__first
, __last
);
3285 __glibcxx_requires_irreflexive(__first
, __last
);
3287 return std::__is_sorted_until(__first
, __last
,
3288 __gnu_cxx::__ops::__iter_less_iter());
3292 * @brief Determines the end of a sorted sequence using comparison functor.
3293 * @ingroup sorting_algorithms
3294 * @param __first An iterator.
3295 * @param __last Another iterator.
3296 * @param __comp A comparison functor.
3297 * @return An iterator pointing to the last iterator i in [__first, __last)
3298 * for which the range [__first, i) is sorted.
3300 template<typename _ForwardIterator
, typename _Compare
>
3301 _GLIBCXX20_CONSTEXPR
3302 inline _ForwardIterator
3303 is_sorted_until(_ForwardIterator __first
, _ForwardIterator __last
,
3306 // concept requirements
3307 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3308 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3309 typename iterator_traits
<_ForwardIterator
>::value_type
,
3310 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3311 __glibcxx_requires_valid_range(__first
, __last
);
3312 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
3314 return std::__is_sorted_until(__first
, __last
,
3315 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
3319 * @brief Determines min and max at once as an ordered pair.
3320 * @ingroup sorting_algorithms
3321 * @param __a A thing of arbitrary type.
3322 * @param __b Another thing of arbitrary type.
3323 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3326 template<typename _Tp
>
3327 _GLIBCXX14_CONSTEXPR
3328 inline pair
<const _Tp
&, const _Tp
&>
3329 minmax(const _Tp
& __a
, const _Tp
& __b
)
3331 // concept requirements
3332 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
3334 return __b
< __a
? pair
<const _Tp
&, const _Tp
&>(__b
, __a
)
3335 : pair
<const _Tp
&, const _Tp
&>(__a
, __b
);
3339 * @brief Determines min and max at once as an ordered pair.
3340 * @ingroup sorting_algorithms
3341 * @param __a A thing of arbitrary type.
3342 * @param __b Another thing of arbitrary type.
3343 * @param __comp A @link comparison_functors comparison functor @endlink.
3344 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3347 template<typename _Tp
, typename _Compare
>
3348 _GLIBCXX14_CONSTEXPR
3349 inline pair
<const _Tp
&, const _Tp
&>
3350 minmax(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
3352 return __comp(__b
, __a
) ? pair
<const _Tp
&, const _Tp
&>(__b
, __a
)
3353 : pair
<const _Tp
&, const _Tp
&>(__a
, __b
);
3356 template<typename _ForwardIterator
, typename _Compare
>
3357 _GLIBCXX14_CONSTEXPR
3358 pair
<_ForwardIterator
, _ForwardIterator
>
3359 __minmax_element(_ForwardIterator __first
, _ForwardIterator __last
,
3362 _ForwardIterator __next
= __first
;
3363 if (__first
== __last
3364 || ++__next
== __last
)
3365 return std::make_pair(__first
, __first
);
3367 _ForwardIterator __min
{}, __max
{};
3368 if (__comp(__next
, __first
))
3382 while (__first
!= __last
)
3385 if (++__next
== __last
)
3387 if (__comp(__first
, __min
))
3389 else if (!__comp(__first
, __max
))
3394 if (__comp(__next
, __first
))
3396 if (__comp(__next
, __min
))
3398 if (!__comp(__first
, __max
))
3403 if (__comp(__first
, __min
))
3405 if (!__comp(__next
, __max
))
3413 return std::make_pair(__min
, __max
);
3417 * @brief Return a pair of iterators pointing to the minimum and maximum
3418 * elements in a range.
3419 * @ingroup sorting_algorithms
3420 * @param __first Start of range.
3421 * @param __last End of range.
3422 * @return make_pair(m, M), where m is the first iterator i in
3423 * [__first, __last) such that no other element in the range is
3424 * smaller, and where M is the last iterator i in [__first, __last)
3425 * such that no other element in the range is larger.
3427 template<typename _ForwardIterator
>
3428 _GLIBCXX14_CONSTEXPR
3429 inline pair
<_ForwardIterator
, _ForwardIterator
>
3430 minmax_element(_ForwardIterator __first
, _ForwardIterator __last
)
3432 // concept requirements
3433 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3434 __glibcxx_function_requires(_LessThanComparableConcept
<
3435 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3436 __glibcxx_requires_valid_range(__first
, __last
);
3437 __glibcxx_requires_irreflexive(__first
, __last
);
3439 return std::__minmax_element(__first
, __last
,
3440 __gnu_cxx::__ops::__iter_less_iter());
3444 * @brief Return a pair of iterators pointing to the minimum and maximum
3445 * elements in a range.
3446 * @ingroup sorting_algorithms
3447 * @param __first Start of range.
3448 * @param __last End of range.
3449 * @param __comp Comparison functor.
3450 * @return make_pair(m, M), where m is the first iterator i in
3451 * [__first, __last) such that no other element in the range is
3452 * smaller, and where M is the last iterator i in [__first, __last)
3453 * such that no other element in the range is larger.
3455 template<typename _ForwardIterator
, typename _Compare
>
3456 _GLIBCXX14_CONSTEXPR
3457 inline pair
<_ForwardIterator
, _ForwardIterator
>
3458 minmax_element(_ForwardIterator __first
, _ForwardIterator __last
,
3461 // concept requirements
3462 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3463 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3464 typename iterator_traits
<_ForwardIterator
>::value_type
,
3465 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3466 __glibcxx_requires_valid_range(__first
, __last
);
3467 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
3469 return std::__minmax_element(__first
, __last
,
3470 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
3473 template<typename _Tp
>
3474 _GLIBCXX14_CONSTEXPR
3475 inline pair
<_Tp
, _Tp
>
3476 minmax(initializer_list
<_Tp
> __l
)
3478 __glibcxx_requires_irreflexive(__l
.begin(), __l
.end());
3479 pair
<const _Tp
*, const _Tp
*> __p
=
3480 std::__minmax_element(__l
.begin(), __l
.end(),
3481 __gnu_cxx::__ops::__iter_less_iter());
3482 return std::make_pair(*__p
.first
, *__p
.second
);
3485 template<typename _Tp
, typename _Compare
>
3486 _GLIBCXX14_CONSTEXPR
3487 inline pair
<_Tp
, _Tp
>
3488 minmax(initializer_list
<_Tp
> __l
, _Compare __comp
)
3490 __glibcxx_requires_irreflexive_pred(__l
.begin(), __l
.end(), __comp
);
3491 pair
<const _Tp
*, const _Tp
*> __p
=
3492 std::__minmax_element(__l
.begin(), __l
.end(),
3493 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
3494 return std::make_pair(*__p
.first
, *__p
.second
);
3498 * @brief Checks whether a permutation of the second sequence is equal
3499 * to the first sequence.
3500 * @ingroup non_mutating_algorithms
3501 * @param __first1 Start of first range.
3502 * @param __last1 End of first range.
3503 * @param __first2 Start of second range.
3504 * @param __pred A binary predicate.
3505 * @return true if there exists a permutation of the elements in
3506 * the range [__first2, __first2 + (__last1 - __first1)),
3507 * beginning with ForwardIterator2 begin, such that
3508 * equal(__first1, __last1, __begin, __pred) returns true;
3509 * otherwise, returns false.
3511 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
3512 typename _BinaryPredicate
>
3513 _GLIBCXX20_CONSTEXPR
3515 is_permutation(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
3516 _ForwardIterator2 __first2
, _BinaryPredicate __pred
)
3518 // concept requirements
3519 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
3520 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
3521 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
3522 typename iterator_traits
<_ForwardIterator1
>::value_type
,
3523 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
3524 __glibcxx_requires_valid_range(__first1
, __last1
);
3526 return std::__is_permutation(__first1
, __last1
, __first2
,
3527 __gnu_cxx::__ops::__iter_comp_iter(__pred
));
3530 #if __cplusplus > 201103L
3531 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
3532 typename _BinaryPredicate
>
3533 _GLIBCXX20_CONSTEXPR
3535 __is_permutation(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
3536 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
3537 _BinaryPredicate __pred
)
3540 = typename iterator_traits
<_ForwardIterator1
>::iterator_category
;
3542 = typename iterator_traits
<_ForwardIterator2
>::iterator_category
;
3543 using _It1_is_RA
= is_same
<_Cat1
, random_access_iterator_tag
>;
3544 using _It2_is_RA
= is_same
<_Cat2
, random_access_iterator_tag
>;
3545 constexpr bool __ra_iters
= _It1_is_RA() && _It2_is_RA();
3548 auto __d1
= std::distance(__first1
, __last1
);
3549 auto __d2
= std::distance(__first2
, __last2
);
3554 // Efficiently compare identical prefixes: O(N) if sequences
3555 // have the same elements in the same order.
3556 for (; __first1
!= __last1
&& __first2
!= __last2
;
3557 ++__first1
, (void)++__first2
)
3558 if (!__pred(__first1
, __first2
))
3563 if (__first1
== __last1
)
3568 auto __d1
= std::distance(__first1
, __last1
);
3569 auto __d2
= std::distance(__first2
, __last2
);
3570 if (__d1
== 0 && __d2
== 0)
3576 for (_ForwardIterator1 __scan
= __first1
; __scan
!= __last1
; ++__scan
)
3578 if (__scan
!= std::__find_if(__first1
, __scan
,
3579 __gnu_cxx::__ops::__iter_comp_iter(__pred
, __scan
)))
3580 continue; // We've seen this one before.
3582 auto __matches
= std::__count_if(__first2
, __last2
,
3583 __gnu_cxx::__ops::__iter_comp_iter(__pred
, __scan
));
3585 || std::__count_if(__scan
, __last1
,
3586 __gnu_cxx::__ops::__iter_comp_iter(__pred
, __scan
))
3594 * @brief Checks whether a permutaion of the second sequence is equal
3595 * to the first sequence.
3596 * @ingroup non_mutating_algorithms
3597 * @param __first1 Start of first range.
3598 * @param __last1 End of first range.
3599 * @param __first2 Start of second range.
3600 * @param __last2 End of first range.
3601 * @return true if there exists a permutation of the elements in the range
3602 * [__first2, __last2), beginning with ForwardIterator2 begin,
3603 * such that equal(__first1, __last1, begin) returns true;
3604 * otherwise, returns false.
3606 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
3607 _GLIBCXX20_CONSTEXPR
3609 is_permutation(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
3610 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
3612 __glibcxx_requires_valid_range(__first1
, __last1
);
3613 __glibcxx_requires_valid_range(__first2
, __last2
);
3616 std::__is_permutation(__first1
, __last1
, __first2
, __last2
,
3617 __gnu_cxx::__ops::__iter_equal_to_iter());
3621 * @brief Checks whether a permutation of the second sequence is equal
3622 * to the first sequence.
3623 * @ingroup non_mutating_algorithms
3624 * @param __first1 Start of first range.
3625 * @param __last1 End of first range.
3626 * @param __first2 Start of second range.
3627 * @param __last2 End of first range.
3628 * @param __pred A binary predicate.
3629 * @return true if there exists a permutation of the elements in the range
3630 * [__first2, __last2), beginning with ForwardIterator2 begin,
3631 * such that equal(__first1, __last1, __begin, __pred) returns true;
3632 * otherwise, returns false.
3634 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
3635 typename _BinaryPredicate
>
3636 _GLIBCXX20_CONSTEXPR
3638 is_permutation(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
3639 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
3640 _BinaryPredicate __pred
)
3642 __glibcxx_requires_valid_range(__first1
, __last1
);
3643 __glibcxx_requires_valid_range(__first2
, __last2
);
3645 return std::__is_permutation(__first1
, __last1
, __first2
, __last2
,
3646 __gnu_cxx::__ops::__iter_comp_iter(__pred
));
3649 #if __cplusplus >= 201703L
3651 #define __cpp_lib_clamp 201603L
3654 * @brief Returns the value clamped between lo and hi.
3655 * @ingroup sorting_algorithms
3656 * @param __val A value of arbitrary type.
3657 * @param __lo A lower limit of arbitrary type.
3658 * @param __hi An upper limit of arbitrary type.
3659 * @retval `__lo` if `__val < __lo`
3660 * @retval `__hi` if `__hi < __val`
3661 * @retval `__val` otherwise.
3662 * @pre `_Tp` is LessThanComparable and `(__hi < __lo)` is false.
3664 template<typename _Tp
>
3665 constexpr const _Tp
&
3666 clamp(const _Tp
& __val
, const _Tp
& __lo
, const _Tp
& __hi
)
3668 __glibcxx_assert(!(__hi
< __lo
));
3669 return std::min(std::max(__val
, __lo
), __hi
);
3673 * @brief Returns the value clamped between lo and hi.
3674 * @ingroup sorting_algorithms
3675 * @param __val A value of arbitrary type.
3676 * @param __lo A lower limit of arbitrary type.
3677 * @param __hi An upper limit of arbitrary type.
3678 * @param __comp A comparison functor.
3679 * @retval `__lo` if `__comp(__val, __lo)`
3680 * @retval `__hi` if `__comp(__hi, __val)`
3681 * @retval `__val` otherwise.
3682 * @pre `__comp(__hi, __lo)` is false.
3684 template<typename _Tp
, typename _Compare
>
3685 constexpr const _Tp
&
3686 clamp(const _Tp
& __val
, const _Tp
& __lo
, const _Tp
& __hi
, _Compare __comp
)
3688 __glibcxx_assert(!__comp(__hi
, __lo
));
3689 return std::min(std::max(__val
, __lo
, __comp
), __hi
, __comp
);
3694 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
3696 * @brief Generate two uniformly distributed integers using a
3697 * single distribution invocation.
3698 * @param __b0 The upper bound for the first integer.
3699 * @param __b1 The upper bound for the second integer.
3700 * @param __g A UniformRandomBitGenerator.
3701 * @return A pair (i, j) with i and j uniformly distributed
3702 * over [0, __b0) and [0, __b1), respectively.
3704 * Requires: __b0 * __b1 <= __g.max() - __g.min().
3706 * Using uniform_int_distribution with a range that is very
3707 * small relative to the range of the generator ends up wasting
3708 * potentially expensively generated randomness, since
3709 * uniform_int_distribution does not store leftover randomness
3710 * between invocations.
3712 * If we know we want two integers in ranges that are sufficiently
3713 * small, we can compose the ranges, use a single distribution
3714 * invocation, and significantly reduce the waste.
3716 template<typename _IntType
, typename _UniformRandomBitGenerator
>
3717 pair
<_IntType
, _IntType
>
3718 __gen_two_uniform_ints(_IntType __b0
, _IntType __b1
,
3719 _UniformRandomBitGenerator
&& __g
)
3722 = uniform_int_distribution
<_IntType
>{0, (__b0
* __b1
) - 1}(__g
);
3723 return std::make_pair(__x
/ __b1
, __x
% __b1
);
3727 * @brief Shuffle the elements of a sequence using a uniform random
3729 * @ingroup mutating_algorithms
3730 * @param __first A forward iterator.
3731 * @param __last A forward iterator.
3732 * @param __g A UniformRandomNumberGenerator (26.5.1.3).
3735 * Reorders the elements in the range @p [__first,__last) using @p __g to
3736 * provide random numbers.
3738 template<typename _RandomAccessIterator
,
3739 typename _UniformRandomNumberGenerator
>
3741 shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
3742 _UniformRandomNumberGenerator
&& __g
)
3744 // concept requirements
3745 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3746 _RandomAccessIterator
>)
3747 __glibcxx_requires_valid_range(__first
, __last
);
3749 if (__first
== __last
)
3752 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3755 typedef typename
std::make_unsigned
<_DistanceType
>::type __ud_type
;
3756 typedef typename
std::uniform_int_distribution
<__ud_type
> __distr_type
;
3757 typedef typename
__distr_type::param_type __p_type
;
3759 typedef typename remove_reference
<_UniformRandomNumberGenerator
>::type
3761 typedef typename common_type
<typename
_Gen::result_type
, __ud_type
>::type
3764 const __uc_type __urngrange
= __g
.max() - __g
.min();
3765 const __uc_type __urange
= __uc_type(__last
- __first
);
3767 if (__urngrange
/ __urange
>= __urange
)
3768 // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
3770 _RandomAccessIterator __i
= __first
+ 1;
3772 // Since we know the range isn't empty, an even number of elements
3773 // means an uneven number of elements /to swap/, in which case we
3774 // do the first one up front:
3776 if ((__urange
% 2) == 0)
3778 __distr_type __d
{0, 1};
3779 std::iter_swap(__i
++, __first
+ __d(__g
));
3782 // Now we know that __last - __i is even, so we do the rest in pairs,
3783 // using a single distribution invocation to produce swap positions
3784 // for two successive elements at a time:
3786 while (__i
!= __last
)
3788 const __uc_type __swap_range
= __uc_type(__i
- __first
) + 1;
3790 const pair
<__uc_type
, __uc_type
> __pospos
=
3791 __gen_two_uniform_ints(__swap_range
, __swap_range
+ 1, __g
);
3793 std::iter_swap(__i
++, __first
+ __pospos
.first
);
3794 std::iter_swap(__i
++, __first
+ __pospos
.second
);
3802 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
3803 std::iter_swap(__i
, __first
+ __d(__g
, __p_type(0, __i
- __first
)));
3805 #endif // USE C99_STDINT
3809 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3812 * @brief Apply a function to every element of a sequence.
3813 * @ingroup non_mutating_algorithms
3814 * @param __first An input iterator.
3815 * @param __last An input iterator.
3816 * @param __f A unary function object.
3819 * Applies the function object @p __f to each element in the range
3820 * @p [first,last). @p __f must not modify the order of the sequence.
3821 * If @p __f has a return value it is ignored.
3823 template<typename _InputIterator
, typename _Function
>
3824 _GLIBCXX20_CONSTEXPR
3826 for_each(_InputIterator __first
, _InputIterator __last
, _Function __f
)
3828 // concept requirements
3829 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3830 __glibcxx_requires_valid_range(__first
, __last
);
3831 for (; __first
!= __last
; ++__first
)
3833 return __f
; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3836 #if __cplusplus >= 201703L
3838 * @brief Apply a function to every element of a sequence.
3839 * @ingroup non_mutating_algorithms
3840 * @param __first An input iterator.
3841 * @param __n A value convertible to an integer.
3842 * @param __f A unary function object.
3843 * @return `__first+__n`
3845 * Applies the function object `__f` to each element in the range
3846 * `[first, first+n)`. `__f` must not modify the order of the sequence.
3847 * If `__f` has a return value it is ignored.
3849 template<typename _InputIterator
, typename _Size
, typename _Function
>
3850 _GLIBCXX20_CONSTEXPR
3852 for_each_n(_InputIterator __first
, _Size __n
, _Function __f
)
3854 auto __n2
= std::__size_to_integer(__n
);
3855 using _Cat
= typename iterator_traits
<_InputIterator
>::iterator_category
;
3856 if constexpr (is_base_of_v
<random_access_iterator_tag
, _Cat
>)
3860 auto __last
= __first
+ __n2
;
3861 std::for_each(__first
, __last
, std::move(__f
));
3877 * @brief Find the first occurrence of a value in a sequence.
3878 * @ingroup non_mutating_algorithms
3879 * @param __first An input iterator.
3880 * @param __last An input iterator.
3881 * @param __val The value to find.
3882 * @return The first iterator @c i in the range @p [__first,__last)
3883 * such that @c *i == @p __val, or @p __last if no such iterator exists.
3885 template<typename _InputIterator
, typename _Tp
>
3886 _GLIBCXX20_CONSTEXPR
3887 inline _InputIterator
3888 find(_InputIterator __first
, _InputIterator __last
,
3891 // concept requirements
3892 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3893 __glibcxx_function_requires(_EqualOpConcept
<
3894 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
3895 __glibcxx_requires_valid_range(__first
, __last
);
3896 return std::__find_if(__first
, __last
,
3897 __gnu_cxx::__ops::__iter_equals_val(__val
));
3901 * @brief Find the first element in a sequence for which a
3902 * predicate is true.
3903 * @ingroup non_mutating_algorithms
3904 * @param __first An input iterator.
3905 * @param __last An input iterator.
3906 * @param __pred A predicate.
3907 * @return The first iterator @c i in the range @p [__first,__last)
3908 * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3910 template<typename _InputIterator
, typename _Predicate
>
3911 _GLIBCXX20_CONSTEXPR
3912 inline _InputIterator
3913 find_if(_InputIterator __first
, _InputIterator __last
,
3916 // concept requirements
3917 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3918 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
3919 typename iterator_traits
<_InputIterator
>::value_type
>)
3920 __glibcxx_requires_valid_range(__first
, __last
);
3922 return std::__find_if(__first
, __last
,
3923 __gnu_cxx::__ops::__pred_iter(__pred
));
3927 * @brief Find element from a set in a sequence.
3928 * @ingroup non_mutating_algorithms
3929 * @param __first1 Start of range to search.
3930 * @param __last1 End of range to search.
3931 * @param __first2 Start of match candidates.
3932 * @param __last2 End of match candidates.
3933 * @return The first iterator @c i in the range
3934 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3935 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3937 * Searches the range @p [__first1,__last1) for an element that is
3938 * equal to some element in the range [__first2,__last2). If
3939 * found, returns an iterator in the range [__first1,__last1),
3940 * otherwise returns @p __last1.
3942 template<typename _InputIterator
, typename _ForwardIterator
>
3943 _GLIBCXX20_CONSTEXPR
3945 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
3946 _ForwardIterator __first2
, _ForwardIterator __last2
)
3948 // concept requirements
3949 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3950 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3951 __glibcxx_function_requires(_EqualOpConcept
<
3952 typename iterator_traits
<_InputIterator
>::value_type
,
3953 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3954 __glibcxx_requires_valid_range(__first1
, __last1
);
3955 __glibcxx_requires_valid_range(__first2
, __last2
);
3957 for (; __first1
!= __last1
; ++__first1
)
3958 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
3959 if (*__first1
== *__iter
)
3965 * @brief Find element from a set in a sequence using a predicate.
3966 * @ingroup non_mutating_algorithms
3967 * @param __first1 Start of range to search.
3968 * @param __last1 End of range to search.
3969 * @param __first2 Start of match candidates.
3970 * @param __last2 End of match candidates.
3971 * @param __comp Predicate to use.
3972 * @return The first iterator @c i in the range
3973 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
3974 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3975 * such iterator exists.
3978 * Searches the range @p [__first1,__last1) for an element that is
3979 * equal to some element in the range [__first2,__last2). If
3980 * found, returns an iterator in the range [__first1,__last1),
3981 * otherwise returns @p __last1.
3983 template<typename _InputIterator
, typename _ForwardIterator
,
3984 typename _BinaryPredicate
>
3985 _GLIBCXX20_CONSTEXPR
3987 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
3988 _ForwardIterator __first2
, _ForwardIterator __last2
,
3989 _BinaryPredicate __comp
)
3991 // concept requirements
3992 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3993 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3994 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
3995 typename iterator_traits
<_InputIterator
>::value_type
,
3996 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3997 __glibcxx_requires_valid_range(__first1
, __last1
);
3998 __glibcxx_requires_valid_range(__first2
, __last2
);
4000 for (; __first1
!= __last1
; ++__first1
)
4001 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
4002 if (__comp(*__first1
, *__iter
))
4008 * @brief Find two adjacent values in a sequence that are equal.
4009 * @ingroup non_mutating_algorithms
4010 * @param __first A forward iterator.
4011 * @param __last A forward iterator.
4012 * @return The first iterator @c i such that @c i and @c i+1 are both
4013 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4014 * or @p __last if no such iterator exists.
4016 template<typename _ForwardIterator
>
4017 _GLIBCXX20_CONSTEXPR
4018 inline _ForwardIterator
4019 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
)
4021 // concept requirements
4022 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4023 __glibcxx_function_requires(_EqualityComparableConcept
<
4024 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4025 __glibcxx_requires_valid_range(__first
, __last
);
4027 return std::__adjacent_find(__first
, __last
,
4028 __gnu_cxx::__ops::__iter_equal_to_iter());
4032 * @brief Find two adjacent values in a sequence using a predicate.
4033 * @ingroup non_mutating_algorithms
4034 * @param __first A forward iterator.
4035 * @param __last A forward iterator.
4036 * @param __binary_pred A binary predicate.
4037 * @return The first iterator @c i such that @c i and @c i+1 are both
4038 * valid iterators in @p [__first,__last) and such that
4039 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4042 template<typename _ForwardIterator
, typename _BinaryPredicate
>
4043 _GLIBCXX20_CONSTEXPR
4044 inline _ForwardIterator
4045 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
,
4046 _BinaryPredicate __binary_pred
)
4048 // concept requirements
4049 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4050 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4051 typename iterator_traits
<_ForwardIterator
>::value_type
,
4052 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4053 __glibcxx_requires_valid_range(__first
, __last
);
4055 return std::__adjacent_find(__first
, __last
,
4056 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
4060 * @brief Count the number of copies of a value in a sequence.
4061 * @ingroup non_mutating_algorithms
4062 * @param __first An input iterator.
4063 * @param __last An input iterator.
4064 * @param __value The value to be counted.
4065 * @return The number of iterators @c i in the range @p [__first,__last)
4066 * for which @c *i == @p __value
4068 template<typename _InputIterator
, typename _Tp
>
4069 _GLIBCXX20_CONSTEXPR
4070 inline typename iterator_traits
<_InputIterator
>::difference_type
4071 count(_InputIterator __first
, _InputIterator __last
, const _Tp
& __value
)
4073 // concept requirements
4074 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4075 __glibcxx_function_requires(_EqualOpConcept
<
4076 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
4077 __glibcxx_requires_valid_range(__first
, __last
);
4079 return std::__count_if(__first
, __last
,
4080 __gnu_cxx::__ops::__iter_equals_val(__value
));
4084 * @brief Count the elements of a sequence for which a predicate is true.
4085 * @ingroup non_mutating_algorithms
4086 * @param __first An input iterator.
4087 * @param __last An input iterator.
4088 * @param __pred A predicate.
4089 * @return The number of iterators @c i in the range @p [__first,__last)
4090 * for which @p __pred(*i) is true.
4092 template<typename _InputIterator
, typename _Predicate
>
4093 _GLIBCXX20_CONSTEXPR
4094 inline typename iterator_traits
<_InputIterator
>::difference_type
4095 count_if(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
4097 // concept requirements
4098 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4099 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
4100 typename iterator_traits
<_InputIterator
>::value_type
>)
4101 __glibcxx_requires_valid_range(__first
, __last
);
4103 return std::__count_if(__first
, __last
,
4104 __gnu_cxx::__ops::__pred_iter(__pred
));
4108 * @brief Search a sequence for a matching sub-sequence.
4109 * @ingroup non_mutating_algorithms
4110 * @param __first1 A forward iterator.
4111 * @param __last1 A forward iterator.
4112 * @param __first2 A forward iterator.
4113 * @param __last2 A forward iterator.
4114 * @return The first iterator @c i in the range @p
4115 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4116 * *(__first2+N) for each @c N in the range @p
4117 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4119 * Searches the range @p [__first1,__last1) for a sub-sequence that
4120 * compares equal value-by-value with the sequence given by @p
4121 * [__first2,__last2) and returns an iterator to the first element
4122 * of the sub-sequence, or @p __last1 if the sub-sequence is not
4125 * Because the sub-sequence must lie completely within the range @p
4126 * [__first1,__last1) it must start at a position less than @p
4127 * __last1-(__last2-__first2) where @p __last2-__first2 is the
4128 * length of the sub-sequence.
4130 * This means that the returned iterator @c i will be in the range
4131 * @p [__first1,__last1-(__last2-__first2))
4133 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
4134 _GLIBCXX20_CONSTEXPR
4135 inline _ForwardIterator1
4136 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
4137 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
4139 // concept requirements
4140 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
4141 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
4142 __glibcxx_function_requires(_EqualOpConcept
<
4143 typename iterator_traits
<_ForwardIterator1
>::value_type
,
4144 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
4145 __glibcxx_requires_valid_range(__first1
, __last1
);
4146 __glibcxx_requires_valid_range(__first2
, __last2
);
4148 return std::__search(__first1
, __last1
, __first2
, __last2
,
4149 __gnu_cxx::__ops::__iter_equal_to_iter());
4153 * @brief Search a sequence for a matching sub-sequence using a predicate.
4154 * @ingroup non_mutating_algorithms
4155 * @param __first1 A forward iterator.
4156 * @param __last1 A forward iterator.
4157 * @param __first2 A forward iterator.
4158 * @param __last2 A forward iterator.
4159 * @param __predicate A binary predicate.
4160 * @return The first iterator @c i in the range
4161 * @p [__first1,__last1-(__last2-__first2)) such that
4162 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4163 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4165 * Searches the range @p [__first1,__last1) for a sub-sequence that
4166 * compares equal value-by-value with the sequence given by @p
4167 * [__first2,__last2), using @p __predicate to determine equality,
4168 * and returns an iterator to the first element of the
4169 * sub-sequence, or @p __last1 if no such iterator exists.
4171 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4173 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
4174 typename _BinaryPredicate
>
4175 _GLIBCXX20_CONSTEXPR
4176 inline _ForwardIterator1
4177 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
4178 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
4179 _BinaryPredicate __predicate
)
4181 // concept requirements
4182 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
4183 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
4184 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4185 typename iterator_traits
<_ForwardIterator1
>::value_type
,
4186 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
4187 __glibcxx_requires_valid_range(__first1
, __last1
);
4188 __glibcxx_requires_valid_range(__first2
, __last2
);
4190 return std::__search(__first1
, __last1
, __first2
, __last2
,
4191 __gnu_cxx::__ops::__iter_comp_iter(__predicate
));
4195 * @brief Search a sequence for a number of consecutive values.
4196 * @ingroup non_mutating_algorithms
4197 * @param __first A forward iterator.
4198 * @param __last A forward iterator.
4199 * @param __count The number of consecutive values.
4200 * @param __val The value to find.
4201 * @return The first iterator @c i in the range @p
4202 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4203 * each @c N in the range @p [0,__count), or @p __last if no such
4206 * Searches the range @p [__first,__last) for @p count consecutive elements
4207 * equal to @p __val.
4209 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
4210 _GLIBCXX20_CONSTEXPR
4211 inline _ForwardIterator
4212 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
4213 _Integer __count
, const _Tp
& __val
)
4215 // concept requirements
4216 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4217 __glibcxx_function_requires(_EqualOpConcept
<
4218 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
4219 __glibcxx_requires_valid_range(__first
, __last
);
4221 return std::__search_n(__first
, __last
, __count
,
4222 __gnu_cxx::__ops::__iter_equals_val(__val
));
4227 * @brief Search a sequence for a number of consecutive values using a
4229 * @ingroup non_mutating_algorithms
4230 * @param __first A forward iterator.
4231 * @param __last A forward iterator.
4232 * @param __count The number of consecutive values.
4233 * @param __val The value to find.
4234 * @param __binary_pred A binary predicate.
4235 * @return The first iterator @c i in the range @p
4236 * [__first,__last-__count) such that @p
4237 * __binary_pred(*(i+N),__val) is true for each @c N in the range
4238 * @p [0,__count), or @p __last if no such iterator exists.
4240 * Searches the range @p [__first,__last) for @p __count
4241 * consecutive elements for which the predicate returns true.
4243 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
4244 typename _BinaryPredicate
>
4245 _GLIBCXX20_CONSTEXPR
4246 inline _ForwardIterator
4247 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
4248 _Integer __count
, const _Tp
& __val
,
4249 _BinaryPredicate __binary_pred
)
4251 // concept requirements
4252 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4253 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4254 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
4255 __glibcxx_requires_valid_range(__first
, __last
);
4257 return std::__search_n(__first
, __last
, __count
,
4258 __gnu_cxx::__ops::__iter_comp_val(__binary_pred
, __val
));
4261 #if __cplusplus >= 201703L
4262 /** @brief Search a sequence using a Searcher object.
4264 * @param __first A forward iterator.
4265 * @param __last A forward iterator.
4266 * @param __searcher A callable object.
4267 * @return @p __searcher(__first,__last).first
4269 template<typename _ForwardIterator
, typename _Searcher
>
4270 _GLIBCXX20_CONSTEXPR
4271 inline _ForwardIterator
4272 search(_ForwardIterator __first
, _ForwardIterator __last
,
4273 const _Searcher
& __searcher
)
4274 { return __searcher(__first
, __last
).first
; }
4278 * @brief Perform an operation on a sequence.
4279 * @ingroup mutating_algorithms
4280 * @param __first An input iterator.
4281 * @param __last An input iterator.
4282 * @param __result An output iterator.
4283 * @param __unary_op A unary operator.
4284 * @return An output iterator equal to @p __result+(__last-__first).
4286 * Applies the operator to each element in the input range and assigns
4287 * the results to successive elements of the output sequence.
4288 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4289 * range @p [0,__last-__first).
4291 * @p unary_op must not alter its argument.
4293 template<typename _InputIterator
, typename _OutputIterator
,
4294 typename _UnaryOperation
>
4295 _GLIBCXX20_CONSTEXPR
4297 transform(_InputIterator __first
, _InputIterator __last
,
4298 _OutputIterator __result
, _UnaryOperation __unary_op
)
4300 // concept requirements
4301 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4302 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4303 // "the type returned by a _UnaryOperation"
4304 __typeof__(__unary_op(*__first
))>)
4305 __glibcxx_requires_valid_range(__first
, __last
);
4307 for (; __first
!= __last
; ++__first
, (void)++__result
)
4308 *__result
= __unary_op(*__first
);
4313 * @brief Perform an operation on corresponding elements of two sequences.
4314 * @ingroup mutating_algorithms
4315 * @param __first1 An input iterator.
4316 * @param __last1 An input iterator.
4317 * @param __first2 An input iterator.
4318 * @param __result An output iterator.
4319 * @param __binary_op A binary operator.
4320 * @return An output iterator equal to @p result+(last-first).
4322 * Applies the operator to the corresponding elements in the two
4323 * input ranges and assigns the results to successive elements of the
4326 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4327 * @c N in the range @p [0,__last1-__first1).
4329 * @p binary_op must not alter either of its arguments.
4331 template<typename _InputIterator1
, typename _InputIterator2
,
4332 typename _OutputIterator
, typename _BinaryOperation
>
4333 _GLIBCXX20_CONSTEXPR
4335 transform(_InputIterator1 __first1
, _InputIterator1 __last1
,
4336 _InputIterator2 __first2
, _OutputIterator __result
,
4337 _BinaryOperation __binary_op
)
4339 // concept requirements
4340 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4341 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4342 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4343 // "the type returned by a _BinaryOperation"
4344 __typeof__(__binary_op(*__first1
,*__first2
))>)
4345 __glibcxx_requires_valid_range(__first1
, __last1
);
4347 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
, ++__result
)
4348 *__result
= __binary_op(*__first1
, *__first2
);
4353 * @brief Replace each occurrence of one value in a sequence with another
4355 * @ingroup mutating_algorithms
4356 * @param __first A forward iterator.
4357 * @param __last A forward iterator.
4358 * @param __old_value The value to be replaced.
4359 * @param __new_value The replacement value.
4360 * @return replace() returns no value.
4362 * For each iterator `i` in the range `[__first,__last)` if
4363 * `*i == __old_value` then the assignment `*i = __new_value` is performed.
4365 template<typename _ForwardIterator
, typename _Tp
>
4366 _GLIBCXX20_CONSTEXPR
4368 replace(_ForwardIterator __first
, _ForwardIterator __last
,
4369 const _Tp
& __old_value
, const _Tp
& __new_value
)
4371 // concept requirements
4372 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
4374 __glibcxx_function_requires(_EqualOpConcept
<
4375 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
4376 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
4377 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4378 __glibcxx_requires_valid_range(__first
, __last
);
4380 for (; __first
!= __last
; ++__first
)
4381 if (*__first
== __old_value
)
4382 *__first
= __new_value
;
4386 * @brief Replace each value in a sequence for which a predicate returns
4387 * true with another value.
4388 * @ingroup mutating_algorithms
4389 * @param __first A forward iterator.
4390 * @param __last A forward iterator.
4391 * @param __pred A predicate.
4392 * @param __new_value The replacement value.
4393 * @return replace_if() returns no value.
4395 * For each iterator `i` in the range `[__first,__last)` if `__pred(*i)`
4396 * is true then the assignment `*i = __new_value` is performed.
4398 template<typename _ForwardIterator
, typename _Predicate
, typename _Tp
>
4399 _GLIBCXX20_CONSTEXPR
4401 replace_if(_ForwardIterator __first
, _ForwardIterator __last
,
4402 _Predicate __pred
, const _Tp
& __new_value
)
4404 // concept requirements
4405 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
4407 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
4408 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4409 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
4410 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4411 __glibcxx_requires_valid_range(__first
, __last
);
4413 for (; __first
!= __last
; ++__first
)
4414 if (__pred(*__first
))
4415 *__first
= __new_value
;
4419 * @brief Assign the result of a function object to each value in a
4421 * @ingroup mutating_algorithms
4422 * @param __first A forward iterator.
4423 * @param __last A forward iterator.
4424 * @param __gen A function object callable with no arguments.
4425 * @return generate() returns no value.
4427 * Performs the assignment `*i = __gen()` for each `i` in the range
4428 * `[__first, __last)`.
4430 template<typename _ForwardIterator
, typename _Generator
>
4431 _GLIBCXX20_CONSTEXPR
4433 generate(_ForwardIterator __first
, _ForwardIterator __last
,
4436 // concept requirements
4437 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4438 __glibcxx_function_requires(_GeneratorConcept
<_Generator
,
4439 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4440 __glibcxx_requires_valid_range(__first
, __last
);
4442 for (; __first
!= __last
; ++__first
)
4447 * @brief Assign the result of a function object to each value in a
4449 * @ingroup mutating_algorithms
4450 * @param __first A forward iterator.
4451 * @param __n The length of the sequence.
4452 * @param __gen A function object callable with no arguments.
4453 * @return The end of the sequence, i.e., `__first + __n`
4455 * Performs the assignment `*i = __gen()` for each `i` in the range
4456 * `[__first, __first + __n)`.
4458 * If `__n` is negative, the function does nothing and returns `__first`.
4460 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4461 // DR 865. More algorithms that throw away information
4462 // DR 426. search_n(), fill_n(), and generate_n() with negative n
4463 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
4464 _GLIBCXX20_CONSTEXPR
4466 generate_n(_OutputIterator __first
, _Size __n
, _Generator __gen
)
4468 // concept requirements
4469 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4470 // "the type returned by a _Generator"
4471 __typeof__(__gen())>)
4473 typedef __decltype(std::__size_to_integer(__n
)) _IntSize
;
4474 for (_IntSize __niter
= std::__size_to_integer(__n
);
4475 __niter
> 0; --__niter
, (void) ++__first
)
4481 * @brief Copy a sequence, removing consecutive duplicate values.
4482 * @ingroup mutating_algorithms
4483 * @param __first An input iterator.
4484 * @param __last An input iterator.
4485 * @param __result An output iterator.
4486 * @return An iterator designating the end of the resulting sequence.
4488 * Copies each element in the range `[__first, __last)` to the range
4489 * beginning at `__result`, except that only the first element is copied
4490 * from groups of consecutive elements that compare equal.
4491 * `unique_copy()` is stable, so the relative order of elements that are
4492 * copied is unchanged.
4494 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4495 // DR 241. Does unique_copy() require CopyConstructible and Assignable?
4496 // DR 538. 241 again: Does unique_copy() require CopyConstructible and
4498 template<typename _InputIterator
, typename _OutputIterator
>
4499 _GLIBCXX20_CONSTEXPR
4500 inline _OutputIterator
4501 unique_copy(_InputIterator __first
, _InputIterator __last
,
4502 _OutputIterator __result
)
4504 // concept requirements
4505 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4506 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4507 typename iterator_traits
<_InputIterator
>::value_type
>)
4508 __glibcxx_function_requires(_EqualityComparableConcept
<
4509 typename iterator_traits
<_InputIterator
>::value_type
>)
4510 __glibcxx_requires_valid_range(__first
, __last
);
4512 if (__first
== __last
)
4514 return std::__unique_copy(__first
, __last
, __result
,
4515 __gnu_cxx::__ops::__iter_equal_to_iter(),
4516 std::__iterator_category(__first
),
4517 std::__iterator_category(__result
));
4521 * @brief Copy a sequence, removing consecutive values using a predicate.
4522 * @ingroup mutating_algorithms
4523 * @param __first An input iterator.
4524 * @param __last An input iterator.
4525 * @param __result An output iterator.
4526 * @param __binary_pred A binary predicate.
4527 * @return An iterator designating the end of the resulting sequence.
4529 * Copies each element in the range `[__first, __last)` to the range
4530 * beginning at `__result`, except that only the first element is copied
4531 * from groups of consecutive elements for which `__binary_pred` returns
4533 * `unique_copy()` is stable, so the relative order of elements that are
4534 * copied is unchanged.
4536 // _GLIBCXX_RESOLVE_LIB_DEFECTS
4537 // DR 241. Does unique_copy() require CopyConstructible and Assignable?
4538 template<typename _InputIterator
, typename _OutputIterator
,
4539 typename _BinaryPredicate
>
4540 _GLIBCXX20_CONSTEXPR
4541 inline _OutputIterator
4542 unique_copy(_InputIterator __first
, _InputIterator __last
,
4543 _OutputIterator __result
,
4544 _BinaryPredicate __binary_pred
)
4546 // concept requirements -- predicates checked later
4547 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4548 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4549 typename iterator_traits
<_InputIterator
>::value_type
>)
4550 __glibcxx_requires_valid_range(__first
, __last
);
4552 if (__first
== __last
)
4554 return std::__unique_copy(__first
, __last
, __result
,
4555 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
),
4556 std::__iterator_category(__first
),
4557 std::__iterator_category(__result
));
4560 #if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4563 * @brief Randomly shuffle the elements of a sequence.
4564 * @ingroup mutating_algorithms
4565 * @param __first A forward iterator.
4566 * @param __last A forward iterator.
4569 * Reorder the elements in the range `[__first, __last)` using a random
4570 * distribution, so that every possible ordering of the sequence is
4574 * Since C++14 `std::random_shuffle` is not part of the C++ standard.
4575 * Use `std::shuffle` instead, which was introduced in C++11.
4577 template<typename _RandomAccessIterator
>
4578 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4580 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
4582 // concept requirements
4583 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4584 _RandomAccessIterator
>)
4585 __glibcxx_requires_valid_range(__first
, __last
);
4587 if (__first
!= __last
)
4588 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
4590 // XXX rand() % N is not uniformly distributed
4591 _RandomAccessIterator __j
= __first
4592 + std::rand() % ((__i
- __first
) + 1);
4594 std::iter_swap(__i
, __j
);
4599 * @brief Shuffle the elements of a sequence using a random number
4601 * @ingroup mutating_algorithms
4602 * @param __first A forward iterator.
4603 * @param __last A forward iterator.
4604 * @param __rand The RNG functor or function.
4607 * Reorders the elements in the range `[__first, __last)` using `__rand`
4608 * to provide a random distribution. Calling `__rand(N)` for a positive
4609 * integer `N` should return a randomly chosen integer from the
4613 * Since C++14 `std::random_shuffle` is not part of the C++ standard.
4614 * Use `std::shuffle` instead, which was introduced in C++11.
4616 template<typename _RandomAccessIterator
, typename _RandomNumberGenerator
>
4617 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4619 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
4620 #if __cplusplus >= 201103L
4621 _RandomNumberGenerator
&& __rand
)
4623 _RandomNumberGenerator
& __rand
)
4626 // concept requirements
4627 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4628 _RandomAccessIterator
>)
4629 __glibcxx_requires_valid_range(__first
, __last
);
4631 if (__first
== __last
)
4633 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
4635 _RandomAccessIterator __j
= __first
+ __rand((__i
- __first
) + 1);
4637 std::iter_swap(__i
, __j
);
4641 #endif // C++11 || USE_DEPRECATED
4644 * @brief Move elements for which a predicate is true to the beginning
4646 * @ingroup mutating_algorithms
4647 * @param __first A forward iterator.
4648 * @param __last A forward iterator.
4649 * @param __pred A predicate functor.
4650 * @return An iterator `middle` such that `__pred(i)` is true for each
4651 * iterator `i` in the range `[__first, middle)` and false for each `i`
4652 * in the range `[middle, __last)`.
4654 * `__pred` must not modify its operand. `partition()` does not preserve
4655 * the relative ordering of elements in each group, use
4656 * `stable_partition()` if this is needed.
4658 template<typename _ForwardIterator
, typename _Predicate
>
4659 _GLIBCXX20_CONSTEXPR
4660 inline _ForwardIterator
4661 partition(_ForwardIterator __first
, _ForwardIterator __last
,
4664 // concept requirements
4665 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
4667 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
4668 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4669 __glibcxx_requires_valid_range(__first
, __last
);
4671 return std::__partition(__first
, __last
, __pred
,
4672 std::__iterator_category(__first
));
4677 * @brief Sort the smallest elements of a sequence.
4678 * @ingroup sorting_algorithms
4679 * @param __first An iterator.
4680 * @param __middle Another iterator.
4681 * @param __last Another iterator.
4684 * Sorts the smallest `(__middle - __first)` elements in the range
4685 * `[first, last)` and moves them to the range `[__first, __middle)`. The
4686 * order of the remaining elements in the range `[__middle, __last)` is
4688 * After the sort if `i` and `j` are iterators in the range
4689 * `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4690 * in the range `[__middle, __last)` then `*j < *i` and `*k < *i` are
4693 template<typename _RandomAccessIterator
>
4694 _GLIBCXX20_CONSTEXPR
4696 partial_sort(_RandomAccessIterator __first
,
4697 _RandomAccessIterator __middle
,
4698 _RandomAccessIterator __last
)
4700 // concept requirements
4701 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4702 _RandomAccessIterator
>)
4703 __glibcxx_function_requires(_LessThanComparableConcept
<
4704 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
4705 __glibcxx_requires_valid_range(__first
, __middle
);
4706 __glibcxx_requires_valid_range(__middle
, __last
);
4707 __glibcxx_requires_irreflexive(__first
, __last
);
4709 std::__partial_sort(__first
, __middle
, __last
,
4710 __gnu_cxx::__ops::__iter_less_iter());
4714 * @brief Sort the smallest elements of a sequence using a predicate
4716 * @ingroup sorting_algorithms
4717 * @param __first An iterator.
4718 * @param __middle Another iterator.
4719 * @param __last Another iterator.
4720 * @param __comp A comparison functor.
4723 * Sorts the smallest `(__middle - __first)` elements in the range
4724 * `[__first, __last)` and moves them to the range `[__first, __middle)`.
4725 * The order of the remaining elements in the range `[__middle, __last)` is
4727 * After the sort if `i` and `j` are iterators in the range
4728 * `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4729 * in the range `[__middle, __last)` then `*__comp(j, *i)` and
4730 * `__comp(*k, *i)` are both false.
4732 template<typename _RandomAccessIterator
, typename _Compare
>
4733 _GLIBCXX20_CONSTEXPR
4735 partial_sort(_RandomAccessIterator __first
,
4736 _RandomAccessIterator __middle
,
4737 _RandomAccessIterator __last
,
4740 // concept requirements
4741 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4742 _RandomAccessIterator
>)
4743 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4744 typename iterator_traits
<_RandomAccessIterator
>::value_type
,
4745 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
4746 __glibcxx_requires_valid_range(__first
, __middle
);
4747 __glibcxx_requires_valid_range(__middle
, __last
);
4748 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
4750 std::__partial_sort(__first
, __middle
, __last
,
4751 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
4755 * @brief Sort a sequence just enough to find a particular position.
4756 * @ingroup sorting_algorithms
4757 * @param __first An iterator.
4758 * @param __nth Another iterator.
4759 * @param __last Another iterator.
4762 * Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4763 * is the same element that would have been in that position had the
4764 * whole sequence been sorted. The elements either side of `*__nth` are
4765 * not completely sorted, but for any iterator `i` in the range
4766 * `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)` it
4767 * holds that `*j < *i` is false.
4769 template<typename _RandomAccessIterator
>
4770 _GLIBCXX20_CONSTEXPR
4772 nth_element(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
4773 _RandomAccessIterator __last
)
4775 // concept requirements
4776 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4777 _RandomAccessIterator
>)
4778 __glibcxx_function_requires(_LessThanComparableConcept
<
4779 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
4780 __glibcxx_requires_valid_range(__first
, __nth
);
4781 __glibcxx_requires_valid_range(__nth
, __last
);
4782 __glibcxx_requires_irreflexive(__first
, __last
);
4784 if (__first
== __last
|| __nth
== __last
)
4787 std::__introselect(__first
, __nth
, __last
,
4788 std::__lg(__last
- __first
) * 2,
4789 __gnu_cxx::__ops::__iter_less_iter());
4793 * @brief Sort a sequence just enough to find a particular position
4794 * using a predicate for comparison.
4795 * @ingroup sorting_algorithms
4796 * @param __first An iterator.
4797 * @param __nth Another iterator.
4798 * @param __last Another iterator.
4799 * @param __comp A comparison functor.
4802 * Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4803 * is the same element that would have been in that position had the
4804 * whole sequence been sorted. The elements either side of `*__nth` are
4805 * not completely sorted, but for any iterator `i` in the range
4806 * `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)`
4807 * it holds that `__comp(*j, *i)` is false.
4809 template<typename _RandomAccessIterator
, typename _Compare
>
4810 _GLIBCXX20_CONSTEXPR
4812 nth_element(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
4813 _RandomAccessIterator __last
, _Compare __comp
)
4815 // concept requirements
4816 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4817 _RandomAccessIterator
>)
4818 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4819 typename iterator_traits
<_RandomAccessIterator
>::value_type
,
4820 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
4821 __glibcxx_requires_valid_range(__first
, __nth
);
4822 __glibcxx_requires_valid_range(__nth
, __last
);
4823 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
4825 if (__first
== __last
|| __nth
== __last
)
4828 std::__introselect(__first
, __nth
, __last
,
4829 std::__lg(__last
- __first
) * 2,
4830 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
4834 * @brief Sort the elements of a sequence.
4835 * @ingroup sorting_algorithms
4836 * @param __first An iterator.
4837 * @param __last Another iterator.
4840 * Sorts the elements in the range `[__first, __last)` in ascending order,
4841 * such that for each iterator `i` in the range `[__first, __last - 1)`,
4842 * `*(i+1) < *i` is false.
4844 * The relative ordering of equivalent elements is not preserved, use
4845 * `stable_sort()` if this is needed.
4847 template<typename _RandomAccessIterator
>
4848 _GLIBCXX20_CONSTEXPR
4850 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
4852 // concept requirements
4853 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4854 _RandomAccessIterator
>)
4855 __glibcxx_function_requires(_LessThanComparableConcept
<
4856 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
4857 __glibcxx_requires_valid_range(__first
, __last
);
4858 __glibcxx_requires_irreflexive(__first
, __last
);
4860 std::__sort(__first
, __last
, __gnu_cxx::__ops::__iter_less_iter());
4864 * @brief Sort the elements of a sequence using a predicate for comparison.
4865 * @ingroup sorting_algorithms
4866 * @param __first An iterator.
4867 * @param __last Another iterator.
4868 * @param __comp A comparison functor.
4871 * Sorts the elements in the range `[__first, __last)` in ascending order,
4872 * such that `__comp(*(i+1), *i)` is false for every iterator `i` in the
4873 * range `[__first, __last - 1)`.
4875 * The relative ordering of equivalent elements is not preserved, use
4876 * `stable_sort()` if this is needed.
4878 template<typename _RandomAccessIterator
, typename _Compare
>
4879 _GLIBCXX20_CONSTEXPR
4881 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
4884 // concept requirements
4885 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4886 _RandomAccessIterator
>)
4887 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4888 typename iterator_traits
<_RandomAccessIterator
>::value_type
,
4889 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
4890 __glibcxx_requires_valid_range(__first
, __last
);
4891 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
4893 std::__sort(__first
, __last
, __gnu_cxx::__ops::__iter_comp_iter(__comp
));
4896 template<typename _InputIterator1
, typename _InputIterator2
,
4897 typename _OutputIterator
, typename _Compare
>
4898 _GLIBCXX20_CONSTEXPR
4900 __merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
4901 _InputIterator2 __first2
, _InputIterator2 __last2
,
4902 _OutputIterator __result
, _Compare __comp
)
4904 while (__first1
!= __last1
&& __first2
!= __last2
)
4906 if (__comp(__first2
, __first1
))
4908 *__result
= *__first2
;
4913 *__result
= *__first1
;
4918 return std::copy(__first2
, __last2
,
4919 std::copy(__first1
, __last1
, __result
));
4923 * @brief Merges two sorted ranges.
4924 * @ingroup sorting_algorithms
4925 * @param __first1 An iterator.
4926 * @param __first2 Another iterator.
4927 * @param __last1 Another iterator.
4928 * @param __last2 Another iterator.
4929 * @param __result An iterator pointing to the end of the merged range.
4930 * @return An output iterator equal to @p __result + (__last1 - __first1)
4931 * + (__last2 - __first2).
4933 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4934 * the sorted range @p [__result, __result + (__last1-__first1) +
4935 * (__last2-__first2)). Both input ranges must be sorted, and the
4936 * output range must not overlap with either of the input ranges.
4937 * The sort is @e stable, that is, for equivalent elements in the
4938 * two ranges, elements from the first range will always come
4939 * before elements from the second.
4941 template<typename _InputIterator1
, typename _InputIterator2
,
4942 typename _OutputIterator
>
4943 _GLIBCXX20_CONSTEXPR
4944 inline _OutputIterator
4945 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
4946 _InputIterator2 __first2
, _InputIterator2 __last2
,
4947 _OutputIterator __result
)
4949 // concept requirements
4950 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4951 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4952 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4953 typename iterator_traits
<_InputIterator1
>::value_type
>)
4954 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4955 typename iterator_traits
<_InputIterator2
>::value_type
>)
4956 __glibcxx_function_requires(_LessThanOpConcept
<
4957 typename iterator_traits
<_InputIterator2
>::value_type
,
4958 typename iterator_traits
<_InputIterator1
>::value_type
>)
4959 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
4960 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
4961 __glibcxx_requires_irreflexive2(__first1
, __last1
);
4962 __glibcxx_requires_irreflexive2(__first2
, __last2
);
4964 return _GLIBCXX_STD_A::__merge(__first1
, __last1
,
4965 __first2
, __last2
, __result
,
4966 __gnu_cxx::__ops::__iter_less_iter());
4970 * @brief Merges two sorted ranges.
4971 * @ingroup sorting_algorithms
4972 * @param __first1 An iterator.
4973 * @param __first2 Another iterator.
4974 * @param __last1 Another iterator.
4975 * @param __last2 Another iterator.
4976 * @param __result An iterator pointing to the end of the merged range.
4977 * @param __comp A functor to use for comparisons.
4978 * @return An output iterator equal to @p __result + (__last1 - __first1)
4979 * + (__last2 - __first2).
4981 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4982 * the sorted range @p [__result, __result + (__last1-__first1) +
4983 * (__last2-__first2)). Both input ranges must be sorted, and the
4984 * output range must not overlap with either of the input ranges.
4985 * The sort is @e stable, that is, for equivalent elements in the
4986 * two ranges, elements from the first range will always come
4987 * before elements from the second.
4989 * The comparison function should have the same effects on ordering as
4990 * the function used for the initial sort.
4992 template<typename _InputIterator1
, typename _InputIterator2
,
4993 typename _OutputIterator
, typename _Compare
>
4994 _GLIBCXX20_CONSTEXPR
4995 inline _OutputIterator
4996 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
4997 _InputIterator2 __first2
, _InputIterator2 __last2
,
4998 _OutputIterator __result
, _Compare __comp
)
5000 // concept requirements
5001 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5002 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5003 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5004 typename iterator_traits
<_InputIterator1
>::value_type
>)
5005 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5006 typename iterator_traits
<_InputIterator2
>::value_type
>)
5007 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5008 typename iterator_traits
<_InputIterator2
>::value_type
,
5009 typename iterator_traits
<_InputIterator1
>::value_type
>)
5010 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5011 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5012 __glibcxx_requires_irreflexive_pred2(__first1
, __last1
, __comp
);
5013 __glibcxx_requires_irreflexive_pred2(__first2
, __last2
, __comp
);
5015 return _GLIBCXX_STD_A::__merge(__first1
, __last1
,
5016 __first2
, __last2
, __result
,
5017 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5020 template<typename _RandomAccessIterator
, typename _Compare
>
5022 __stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
5025 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5027 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
5030 if (__first
== __last
)
5034 typedef _Temporary_buffer
<_RandomAccessIterator
, _ValueType
> _TmpBuf
;
5035 // __stable_sort_adaptive sorts the range in two halves,
5036 // so the buffer only needs to fit half the range at once.
5037 _TmpBuf
__buf(__first
, (__last
- __first
+ 1) / 2);
5039 if (__builtin_expect(__buf
.requested_size() == __buf
.size(), true))
5040 std::__stable_sort_adaptive(__first
,
5041 __first
+ _DistanceType(__buf
.size()),
5042 __last
, __buf
.begin(), __comp
);
5043 else if (__builtin_expect(__buf
.begin() == 0, false))
5044 std::__inplace_stable_sort(__first
, __last
, __comp
);
5046 std::__stable_sort_adaptive_resize(__first
, __last
, __buf
.begin(),
5047 _DistanceType(__buf
.size()), __comp
);
5049 std::__inplace_stable_sort(__first
, __last
, __comp
);
5054 * @brief Sort the elements of a sequence, preserving the relative order
5055 * of equivalent elements.
5056 * @ingroup sorting_algorithms
5057 * @param __first An iterator.
5058 * @param __last Another iterator.
5061 * Sorts the elements in the range @p [__first,__last) in ascending order,
5062 * such that for each iterator @p i in the range @p [__first,__last-1),
5063 * @p *(i+1)<*i is false.
5065 * The relative ordering of equivalent elements is preserved, so any two
5066 * elements @p x and @p y in the range @p [__first,__last) such that
5067 * @p x<y is false and @p y<x is false will have the same relative
5068 * ordering after calling @p stable_sort().
5070 template<typename _RandomAccessIterator
>
5072 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
5074 // concept requirements
5075 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5076 _RandomAccessIterator
>)
5077 __glibcxx_function_requires(_LessThanComparableConcept
<
5078 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
5079 __glibcxx_requires_valid_range(__first
, __last
);
5080 __glibcxx_requires_irreflexive(__first
, __last
);
5082 _GLIBCXX_STD_A::__stable_sort(__first
, __last
,
5083 __gnu_cxx::__ops::__iter_less_iter());
5087 * @brief Sort the elements of a sequence using a predicate for comparison,
5088 * preserving the relative order of equivalent elements.
5089 * @ingroup sorting_algorithms
5090 * @param __first An iterator.
5091 * @param __last Another iterator.
5092 * @param __comp A comparison functor.
5095 * Sorts the elements in the range @p [__first,__last) in ascending order,
5096 * such that for each iterator @p i in the range @p [__first,__last-1),
5097 * @p __comp(*(i+1),*i) is false.
5099 * The relative ordering of equivalent elements is preserved, so any two
5100 * elements @p x and @p y in the range @p [__first,__last) such that
5101 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5102 * relative ordering after calling @p stable_sort().
5104 template<typename _RandomAccessIterator
, typename _Compare
>
5106 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
5109 // concept requirements
5110 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5111 _RandomAccessIterator
>)
5112 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5113 typename iterator_traits
<_RandomAccessIterator
>::value_type
,
5114 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
5115 __glibcxx_requires_valid_range(__first
, __last
);
5116 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
5118 _GLIBCXX_STD_A::__stable_sort(__first
, __last
,
5119 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5122 template<typename _InputIterator1
, typename _InputIterator2
,
5123 typename _OutputIterator
,
5125 _GLIBCXX20_CONSTEXPR
5127 __set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
5128 _InputIterator2 __first2
, _InputIterator2 __last2
,
5129 _OutputIterator __result
, _Compare __comp
)
5131 while (__first1
!= __last1
&& __first2
!= __last2
)
5133 if (__comp(__first1
, __first2
))
5135 *__result
= *__first1
;
5138 else if (__comp(__first2
, __first1
))
5140 *__result
= *__first2
;
5145 *__result
= *__first1
;
5151 return std::copy(__first2
, __last2
,
5152 std::copy(__first1
, __last1
, __result
));
5156 * @brief Return the union of two sorted ranges.
5157 * @ingroup set_algorithms
5158 * @param __first1 Start of first range.
5159 * @param __last1 End of first range.
5160 * @param __first2 Start of second range.
5161 * @param __last2 End of second range.
5162 * @param __result Start of output range.
5163 * @return End of the output range.
5164 * @ingroup set_algorithms
5166 * This operation iterates over both ranges, copying elements present in
5167 * each range in order to the output range. Iterators increment for each
5168 * range. When the current element of one range is less than the other,
5169 * that element is copied and the iterator advanced. If an element is
5170 * contained in both ranges, the element from the first range is copied and
5171 * both ranges advance. The output range may not overlap either input
5174 template<typename _InputIterator1
, typename _InputIterator2
,
5175 typename _OutputIterator
>
5176 _GLIBCXX20_CONSTEXPR
5177 inline _OutputIterator
5178 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
5179 _InputIterator2 __first2
, _InputIterator2 __last2
,
5180 _OutputIterator __result
)
5182 // concept requirements
5183 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5184 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5185 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5186 typename iterator_traits
<_InputIterator1
>::value_type
>)
5187 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5188 typename iterator_traits
<_InputIterator2
>::value_type
>)
5189 __glibcxx_function_requires(_LessThanOpConcept
<
5190 typename iterator_traits
<_InputIterator1
>::value_type
,
5191 typename iterator_traits
<_InputIterator2
>::value_type
>)
5192 __glibcxx_function_requires(_LessThanOpConcept
<
5193 typename iterator_traits
<_InputIterator2
>::value_type
,
5194 typename iterator_traits
<_InputIterator1
>::value_type
>)
5195 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5196 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5197 __glibcxx_requires_irreflexive2(__first1
, __last1
);
5198 __glibcxx_requires_irreflexive2(__first2
, __last2
);
5200 return _GLIBCXX_STD_A::__set_union(__first1
, __last1
,
5201 __first2
, __last2
, __result
,
5202 __gnu_cxx::__ops::__iter_less_iter());
5206 * @brief Return the union of two sorted ranges using a comparison functor.
5207 * @ingroup set_algorithms
5208 * @param __first1 Start of first range.
5209 * @param __last1 End of first range.
5210 * @param __first2 Start of second range.
5211 * @param __last2 End of second range.
5212 * @param __result Start of output range.
5213 * @param __comp The comparison functor.
5214 * @return End of the output range.
5215 * @ingroup set_algorithms
5217 * This operation iterates over both ranges, copying elements present in
5218 * each range in order to the output range. Iterators increment for each
5219 * range. When the current element of one range is less than the other
5220 * according to @p __comp, that element is copied and the iterator advanced.
5221 * If an equivalent element according to @p __comp is contained in both
5222 * ranges, the element from the first range is copied and both ranges
5223 * advance. The output range may not overlap either input range.
5225 template<typename _InputIterator1
, typename _InputIterator2
,
5226 typename _OutputIterator
, typename _Compare
>
5227 _GLIBCXX20_CONSTEXPR
5228 inline _OutputIterator
5229 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
5230 _InputIterator2 __first2
, _InputIterator2 __last2
,
5231 _OutputIterator __result
, _Compare __comp
)
5233 // concept requirements
5234 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5235 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5236 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5237 typename iterator_traits
<_InputIterator1
>::value_type
>)
5238 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5239 typename iterator_traits
<_InputIterator2
>::value_type
>)
5240 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5241 typename iterator_traits
<_InputIterator1
>::value_type
,
5242 typename iterator_traits
<_InputIterator2
>::value_type
>)
5243 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5244 typename iterator_traits
<_InputIterator2
>::value_type
,
5245 typename iterator_traits
<_InputIterator1
>::value_type
>)
5246 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5247 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5248 __glibcxx_requires_irreflexive_pred2(__first1
, __last1
, __comp
);
5249 __glibcxx_requires_irreflexive_pred2(__first2
, __last2
, __comp
);
5251 return _GLIBCXX_STD_A::__set_union(__first1
, __last1
,
5252 __first2
, __last2
, __result
,
5253 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5256 template<typename _InputIterator1
, typename _InputIterator2
,
5257 typename _OutputIterator
,
5259 _GLIBCXX20_CONSTEXPR
5261 __set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
5262 _InputIterator2 __first2
, _InputIterator2 __last2
,
5263 _OutputIterator __result
, _Compare __comp
)
5265 while (__first1
!= __last1
&& __first2
!= __last2
)
5266 if (__comp(__first1
, __first2
))
5268 else if (__comp(__first2
, __first1
))
5272 *__result
= *__first1
;
5281 * @brief Return the intersection of two sorted ranges.
5282 * @ingroup set_algorithms
5283 * @param __first1 Start of first range.
5284 * @param __last1 End of first range.
5285 * @param __first2 Start of second range.
5286 * @param __last2 End of second range.
5287 * @param __result Start of output range.
5288 * @return End of the output range.
5289 * @ingroup set_algorithms
5291 * This operation iterates over both ranges, copying elements present in
5292 * both ranges in order to the output range. Iterators increment for each
5293 * range. When the current element of one range is less than the other,
5294 * that iterator advances. If an element is contained in both ranges, the
5295 * element from the first range is copied and both ranges advance. The
5296 * output range may not overlap either input range.
5298 template<typename _InputIterator1
, typename _InputIterator2
,
5299 typename _OutputIterator
>
5300 _GLIBCXX20_CONSTEXPR
5301 inline _OutputIterator
5302 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
5303 _InputIterator2 __first2
, _InputIterator2 __last2
,
5304 _OutputIterator __result
)
5306 // concept requirements
5307 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5308 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5309 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5310 typename iterator_traits
<_InputIterator1
>::value_type
>)
5311 __glibcxx_function_requires(_LessThanOpConcept
<
5312 typename iterator_traits
<_InputIterator1
>::value_type
,
5313 typename iterator_traits
<_InputIterator2
>::value_type
>)
5314 __glibcxx_function_requires(_LessThanOpConcept
<
5315 typename iterator_traits
<_InputIterator2
>::value_type
,
5316 typename iterator_traits
<_InputIterator1
>::value_type
>)
5317 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5318 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5319 __glibcxx_requires_irreflexive2(__first1
, __last1
);
5320 __glibcxx_requires_irreflexive2(__first2
, __last2
);
5322 return _GLIBCXX_STD_A::__set_intersection(__first1
, __last1
,
5323 __first2
, __last2
, __result
,
5324 __gnu_cxx::__ops::__iter_less_iter());
5328 * @brief Return the intersection of two sorted ranges using comparison
5330 * @ingroup set_algorithms
5331 * @param __first1 Start of first range.
5332 * @param __last1 End of first range.
5333 * @param __first2 Start of second range.
5334 * @param __last2 End of second range.
5335 * @param __result Start of output range.
5336 * @param __comp The comparison functor.
5337 * @return End of the output range.
5338 * @ingroup set_algorithms
5340 * This operation iterates over both ranges, copying elements present in
5341 * both ranges in order to the output range. Iterators increment for each
5342 * range. When the current element of one range is less than the other
5343 * according to @p __comp, that iterator advances. If an element is
5344 * contained in both ranges according to @p __comp, the element from the
5345 * first range is copied and both ranges advance. The output range may not
5346 * overlap either input range.
5348 template<typename _InputIterator1
, typename _InputIterator2
,
5349 typename _OutputIterator
, typename _Compare
>
5350 _GLIBCXX20_CONSTEXPR
5351 inline _OutputIterator
5352 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
5353 _InputIterator2 __first2
, _InputIterator2 __last2
,
5354 _OutputIterator __result
, _Compare __comp
)
5356 // concept requirements
5357 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5358 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5359 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5360 typename iterator_traits
<_InputIterator1
>::value_type
>)
5361 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5362 typename iterator_traits
<_InputIterator1
>::value_type
,
5363 typename iterator_traits
<_InputIterator2
>::value_type
>)
5364 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5365 typename iterator_traits
<_InputIterator2
>::value_type
,
5366 typename iterator_traits
<_InputIterator1
>::value_type
>)
5367 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5368 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5369 __glibcxx_requires_irreflexive_pred2(__first1
, __last1
, __comp
);
5370 __glibcxx_requires_irreflexive_pred2(__first2
, __last2
, __comp
);
5372 return _GLIBCXX_STD_A::__set_intersection(__first1
, __last1
,
5373 __first2
, __last2
, __result
,
5374 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5377 template<typename _InputIterator1
, typename _InputIterator2
,
5378 typename _OutputIterator
,
5380 _GLIBCXX20_CONSTEXPR
5382 __set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5383 _InputIterator2 __first2
, _InputIterator2 __last2
,
5384 _OutputIterator __result
, _Compare __comp
)
5386 while (__first1
!= __last1
&& __first2
!= __last2
)
5387 if (__comp(__first1
, __first2
))
5389 *__result
= *__first1
;
5393 else if (__comp(__first2
, __first1
))
5400 return std::copy(__first1
, __last1
, __result
);
5404 * @brief Return the difference of two sorted ranges.
5405 * @ingroup set_algorithms
5406 * @param __first1 Start of first range.
5407 * @param __last1 End of first range.
5408 * @param __first2 Start of second range.
5409 * @param __last2 End of second range.
5410 * @param __result Start of output range.
5411 * @return End of the output range.
5412 * @ingroup set_algorithms
5414 * This operation iterates over both ranges, copying elements present in
5415 * the first range but not the second in order to the output range.
5416 * Iterators increment for each range. When the current element of the
5417 * first range is less than the second, that element is copied and the
5418 * iterator advances. If the current element of the second range is less,
5419 * the iterator advances, but no element is copied. If an element is
5420 * contained in both ranges, no elements are copied and both ranges
5421 * advance. The output range may not overlap either input range.
5423 template<typename _InputIterator1
, typename _InputIterator2
,
5424 typename _OutputIterator
>
5425 _GLIBCXX20_CONSTEXPR
5426 inline _OutputIterator
5427 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5428 _InputIterator2 __first2
, _InputIterator2 __last2
,
5429 _OutputIterator __result
)
5431 // concept requirements
5432 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5433 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5434 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5435 typename iterator_traits
<_InputIterator1
>::value_type
>)
5436 __glibcxx_function_requires(_LessThanOpConcept
<
5437 typename iterator_traits
<_InputIterator1
>::value_type
,
5438 typename iterator_traits
<_InputIterator2
>::value_type
>)
5439 __glibcxx_function_requires(_LessThanOpConcept
<
5440 typename iterator_traits
<_InputIterator2
>::value_type
,
5441 typename iterator_traits
<_InputIterator1
>::value_type
>)
5442 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5443 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5444 __glibcxx_requires_irreflexive2(__first1
, __last1
);
5445 __glibcxx_requires_irreflexive2(__first2
, __last2
);
5447 return _GLIBCXX_STD_A::__set_difference(__first1
, __last1
,
5448 __first2
, __last2
, __result
,
5449 __gnu_cxx::__ops::__iter_less_iter());
5453 * @brief Return the difference of two sorted ranges using comparison
5455 * @ingroup set_algorithms
5456 * @param __first1 Start of first range.
5457 * @param __last1 End of first range.
5458 * @param __first2 Start of second range.
5459 * @param __last2 End of second range.
5460 * @param __result Start of output range.
5461 * @param __comp The comparison functor.
5462 * @return End of the output range.
5463 * @ingroup set_algorithms
5465 * This operation iterates over both ranges, copying elements present in
5466 * the first range but not the second in order to the output range.
5467 * Iterators increment for each range. When the current element of the
5468 * first range is less than the second according to @p __comp, that element
5469 * is copied and the iterator advances. If the current element of the
5470 * second range is less, no element is copied and the iterator advances.
5471 * If an element is contained in both ranges according to @p __comp, no
5472 * elements are copied and both ranges advance. The output range may not
5473 * overlap either input range.
5475 template<typename _InputIterator1
, typename _InputIterator2
,
5476 typename _OutputIterator
, typename _Compare
>
5477 _GLIBCXX20_CONSTEXPR
5478 inline _OutputIterator
5479 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5480 _InputIterator2 __first2
, _InputIterator2 __last2
,
5481 _OutputIterator __result
, _Compare __comp
)
5483 // concept requirements
5484 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5485 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5486 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5487 typename iterator_traits
<_InputIterator1
>::value_type
>)
5488 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5489 typename iterator_traits
<_InputIterator1
>::value_type
,
5490 typename iterator_traits
<_InputIterator2
>::value_type
>)
5491 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5492 typename iterator_traits
<_InputIterator2
>::value_type
,
5493 typename iterator_traits
<_InputIterator1
>::value_type
>)
5494 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5495 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5496 __glibcxx_requires_irreflexive_pred2(__first1
, __last1
, __comp
);
5497 __glibcxx_requires_irreflexive_pred2(__first2
, __last2
, __comp
);
5499 return _GLIBCXX_STD_A::__set_difference(__first1
, __last1
,
5500 __first2
, __last2
, __result
,
5501 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5504 template<typename _InputIterator1
, typename _InputIterator2
,
5505 typename _OutputIterator
,
5507 _GLIBCXX20_CONSTEXPR
5509 __set_symmetric_difference(_InputIterator1 __first1
,
5510 _InputIterator1 __last1
,
5511 _InputIterator2 __first2
,
5512 _InputIterator2 __last2
,
5513 _OutputIterator __result
,
5516 while (__first1
!= __last1
&& __first2
!= __last2
)
5517 if (__comp(__first1
, __first2
))
5519 *__result
= *__first1
;
5523 else if (__comp(__first2
, __first1
))
5525 *__result
= *__first2
;
5534 return std::copy(__first2
, __last2
,
5535 std::copy(__first1
, __last1
, __result
));
5539 * @brief Return the symmetric difference of two sorted ranges.
5540 * @ingroup set_algorithms
5541 * @param __first1 Start of first range.
5542 * @param __last1 End of first range.
5543 * @param __first2 Start of second range.
5544 * @param __last2 End of second range.
5545 * @param __result Start of output range.
5546 * @return End of the output range.
5547 * @ingroup set_algorithms
5549 * This operation iterates over both ranges, copying elements present in
5550 * one range but not the other in order to the output range. Iterators
5551 * increment for each range. When the current element of one range is less
5552 * than the other, that element is copied and the iterator advances. If an
5553 * element is contained in both ranges, no elements are copied and both
5554 * ranges advance. The output range may not overlap either input range.
5556 template<typename _InputIterator1
, typename _InputIterator2
,
5557 typename _OutputIterator
>
5558 _GLIBCXX20_CONSTEXPR
5559 inline _OutputIterator
5560 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5561 _InputIterator2 __first2
, _InputIterator2 __last2
,
5562 _OutputIterator __result
)
5564 // concept requirements
5565 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5566 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5567 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5568 typename iterator_traits
<_InputIterator1
>::value_type
>)
5569 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5570 typename iterator_traits
<_InputIterator2
>::value_type
>)
5571 __glibcxx_function_requires(_LessThanOpConcept
<
5572 typename iterator_traits
<_InputIterator1
>::value_type
,
5573 typename iterator_traits
<_InputIterator2
>::value_type
>)
5574 __glibcxx_function_requires(_LessThanOpConcept
<
5575 typename iterator_traits
<_InputIterator2
>::value_type
,
5576 typename iterator_traits
<_InputIterator1
>::value_type
>)
5577 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5578 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5579 __glibcxx_requires_irreflexive2(__first1
, __last1
);
5580 __glibcxx_requires_irreflexive2(__first2
, __last2
);
5582 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1
, __last1
,
5583 __first2
, __last2
, __result
,
5584 __gnu_cxx::__ops::__iter_less_iter());
5588 * @brief Return the symmetric difference of two sorted ranges using
5589 * comparison functor.
5590 * @ingroup set_algorithms
5591 * @param __first1 Start of first range.
5592 * @param __last1 End of first range.
5593 * @param __first2 Start of second range.
5594 * @param __last2 End of second range.
5595 * @param __result Start of output range.
5596 * @param __comp The comparison functor.
5597 * @return End of the output range.
5598 * @ingroup set_algorithms
5600 * This operation iterates over both ranges, copying elements present in
5601 * one range but not the other in order to the output range. Iterators
5602 * increment for each range. When the current element of one range is less
5603 * than the other according to @p comp, that element is copied and the
5604 * iterator advances. If an element is contained in both ranges according
5605 * to @p __comp, no elements are copied and both ranges advance. The output
5606 * range may not overlap either input range.
5608 template<typename _InputIterator1
, typename _InputIterator2
,
5609 typename _OutputIterator
, typename _Compare
>
5610 _GLIBCXX20_CONSTEXPR
5611 inline _OutputIterator
5612 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5613 _InputIterator2 __first2
, _InputIterator2 __last2
,
5614 _OutputIterator __result
,
5617 // concept requirements
5618 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5619 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5620 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5621 typename iterator_traits
<_InputIterator1
>::value_type
>)
5622 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5623 typename iterator_traits
<_InputIterator2
>::value_type
>)
5624 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5625 typename iterator_traits
<_InputIterator1
>::value_type
,
5626 typename iterator_traits
<_InputIterator2
>::value_type
>)
5627 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5628 typename iterator_traits
<_InputIterator2
>::value_type
,
5629 typename iterator_traits
<_InputIterator1
>::value_type
>)
5630 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5631 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5632 __glibcxx_requires_irreflexive_pred2(__first1
, __last1
, __comp
);
5633 __glibcxx_requires_irreflexive_pred2(__first2
, __last2
, __comp
);
5635 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1
, __last1
,
5636 __first2
, __last2
, __result
,
5637 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5640 template<typename _ForwardIterator
, typename _Compare
>
5641 _GLIBCXX14_CONSTEXPR
5643 __min_element(_ForwardIterator __first
, _ForwardIterator __last
,
5646 if (__first
== __last
)
5648 _ForwardIterator __result
= __first
;
5649 while (++__first
!= __last
)
5650 if (__comp(__first
, __result
))
5656 * @brief Return the minimum element in a range.
5657 * @ingroup sorting_algorithms
5658 * @param __first Start of range.
5659 * @param __last End of range.
5660 * @return Iterator referencing the first instance of the smallest value.
5662 template<typename _ForwardIterator
>
5663 _GLIBCXX14_CONSTEXPR
5665 inline min_element(_ForwardIterator __first
, _ForwardIterator __last
)
5667 // concept requirements
5668 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5669 __glibcxx_function_requires(_LessThanComparableConcept
<
5670 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5671 __glibcxx_requires_valid_range(__first
, __last
);
5672 __glibcxx_requires_irreflexive(__first
, __last
);
5674 return _GLIBCXX_STD_A::__min_element(__first
, __last
,
5675 __gnu_cxx::__ops::__iter_less_iter());
5679 * @brief Return the minimum element in a range using comparison functor.
5680 * @ingroup sorting_algorithms
5681 * @param __first Start of range.
5682 * @param __last End of range.
5683 * @param __comp Comparison functor.
5684 * @return Iterator referencing the first instance of the smallest value
5685 * according to __comp.
5687 template<typename _ForwardIterator
, typename _Compare
>
5688 _GLIBCXX14_CONSTEXPR
5689 inline _ForwardIterator
5690 min_element(_ForwardIterator __first
, _ForwardIterator __last
,
5693 // concept requirements
5694 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5695 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5696 typename iterator_traits
<_ForwardIterator
>::value_type
,
5697 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5698 __glibcxx_requires_valid_range(__first
, __last
);
5699 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
5701 return _GLIBCXX_STD_A::__min_element(__first
, __last
,
5702 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5705 template<typename _ForwardIterator
, typename _Compare
>
5706 _GLIBCXX14_CONSTEXPR
5708 __max_element(_ForwardIterator __first
, _ForwardIterator __last
,
5711 if (__first
== __last
) return __first
;
5712 _ForwardIterator __result
= __first
;
5713 while (++__first
!= __last
)
5714 if (__comp(__result
, __first
))
5720 * @brief Return the maximum element in a range.
5721 * @ingroup sorting_algorithms
5722 * @param __first Start of range.
5723 * @param __last End of range.
5724 * @return Iterator referencing the first instance of the largest value.
5726 template<typename _ForwardIterator
>
5727 _GLIBCXX14_CONSTEXPR
5728 inline _ForwardIterator
5729 max_element(_ForwardIterator __first
, _ForwardIterator __last
)
5731 // concept requirements
5732 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5733 __glibcxx_function_requires(_LessThanComparableConcept
<
5734 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5735 __glibcxx_requires_valid_range(__first
, __last
);
5736 __glibcxx_requires_irreflexive(__first
, __last
);
5738 return _GLIBCXX_STD_A::__max_element(__first
, __last
,
5739 __gnu_cxx::__ops::__iter_less_iter());
5743 * @brief Return the maximum element in a range using comparison functor.
5744 * @ingroup sorting_algorithms
5745 * @param __first Start of range.
5746 * @param __last End of range.
5747 * @param __comp Comparison functor.
5748 * @return Iterator referencing the first instance of the largest value
5749 * according to __comp.
5751 template<typename _ForwardIterator
, typename _Compare
>
5752 _GLIBCXX14_CONSTEXPR
5753 inline _ForwardIterator
5754 max_element(_ForwardIterator __first
, _ForwardIterator __last
,
5757 // concept requirements
5758 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5759 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5760 typename iterator_traits
<_ForwardIterator
>::value_type
,
5761 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5762 __glibcxx_requires_valid_range(__first
, __last
);
5763 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
5765 return _GLIBCXX_STD_A::__max_element(__first
, __last
,
5766 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5769 #if __cplusplus >= 201103L
5771 template<typename _Tp
>
5772 _GLIBCXX14_CONSTEXPR
5774 min(initializer_list
<_Tp
> __l
)
5776 __glibcxx_requires_irreflexive(__l
.begin(), __l
.end());
5777 return *_GLIBCXX_STD_A::__min_element(__l
.begin(), __l
.end(),
5778 __gnu_cxx::__ops::__iter_less_iter());
5781 template<typename _Tp
, typename _Compare
>
5782 _GLIBCXX14_CONSTEXPR
5784 min(initializer_list
<_Tp
> __l
, _Compare __comp
)
5786 __glibcxx_requires_irreflexive_pred(__l
.begin(), __l
.end(), __comp
);
5787 return *_GLIBCXX_STD_A::__min_element(__l
.begin(), __l
.end(),
5788 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5791 template<typename _Tp
>
5792 _GLIBCXX14_CONSTEXPR
5794 max(initializer_list
<_Tp
> __l
)
5796 __glibcxx_requires_irreflexive(__l
.begin(), __l
.end());
5797 return *_GLIBCXX_STD_A::__max_element(__l
.begin(), __l
.end(),
5798 __gnu_cxx::__ops::__iter_less_iter());
5801 template<typename _Tp
, typename _Compare
>
5802 _GLIBCXX14_CONSTEXPR
5804 max(initializer_list
<_Tp
> __l
, _Compare __comp
)
5806 __glibcxx_requires_irreflexive_pred(__l
.begin(), __l
.end(), __comp
);
5807 return *_GLIBCXX_STD_A::__max_element(__l
.begin(), __l
.end(),
5808 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
5812 #if __cplusplus >= 201402L
5813 /// Reservoir sampling algorithm.
5814 template<typename _InputIterator
, typename _RandomAccessIterator
,
5815 typename _Size
, typename _UniformRandomBitGenerator
>
5816 _RandomAccessIterator
5817 __sample(_InputIterator __first
, _InputIterator __last
, input_iterator_tag
,
5818 _RandomAccessIterator __out
, random_access_iterator_tag
,
5819 _Size __n
, _UniformRandomBitGenerator
&& __g
)
5821 using __distrib_type
= uniform_int_distribution
<_Size
>;
5822 using __param_type
= typename
__distrib_type::param_type
;
5823 __distrib_type __d
{};
5824 _Size __sample_sz
= 0;
5825 while (__first
!= __last
&& __sample_sz
!= __n
)
5827 __out
[__sample_sz
++] = *__first
;
5830 for (auto __pop_sz
= __sample_sz
; __first
!= __last
;
5831 ++__first
, (void) ++__pop_sz
)
5833 const auto __k
= __d(__g
, __param_type
{0, __pop_sz
});
5835 __out
[__k
] = *__first
;
5837 return __out
+ __sample_sz
;
5840 /// Selection sampling algorithm.
5841 template<typename _ForwardIterator
, typename _OutputIterator
, typename _Cat
,
5842 typename _Size
, typename _UniformRandomBitGenerator
>
5844 __sample(_ForwardIterator __first
, _ForwardIterator __last
,
5845 forward_iterator_tag
,
5846 _OutputIterator __out
, _Cat
,
5847 _Size __n
, _UniformRandomBitGenerator
&& __g
)
5849 using __distrib_type
= uniform_int_distribution
<_Size
>;
5850 using __param_type
= typename
__distrib_type::param_type
;
5851 using _USize
= make_unsigned_t
<_Size
>;
5852 using _Gen
= remove_reference_t
<_UniformRandomBitGenerator
>;
5853 using __uc_type
= common_type_t
<typename
_Gen::result_type
, _USize
>;
5855 if (__first
== __last
)
5858 __distrib_type __d
{};
5859 _Size __unsampled_sz
= std::distance(__first
, __last
);
5860 __n
= std::min(__n
, __unsampled_sz
);
5862 // If possible, we use __gen_two_uniform_ints to efficiently produce
5863 // two random numbers using a single distribution invocation:
5865 const __uc_type __urngrange
= __g
.max() - __g
.min();
5866 if (__urngrange
/ __uc_type(__unsampled_sz
) >= __uc_type(__unsampled_sz
))
5867 // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
5870 while (__n
!= 0 && __unsampled_sz
>= 2)
5872 const pair
<_Size
, _Size
> __p
=
5873 __gen_two_uniform_ints(__unsampled_sz
, __unsampled_sz
- 1, __g
);
5876 if (__p
.first
< __n
)
5878 *__out
++ = *__first
;
5884 if (__n
== 0) break;
5887 if (__p
.second
< __n
)
5889 *__out
++ = *__first
;
5897 // The loop above is otherwise equivalent to this one-at-a-time version:
5899 for (; __n
!= 0; ++__first
)
5900 if (__d(__g
, __param_type
{0, --__unsampled_sz
}) < __n
)
5902 *__out
++ = *__first
;
5908 #if __cplusplus > 201402L
5909 #define __cpp_lib_sample 201603L
5910 /// Take a random sample from a population.
5911 template<typename _PopulationIterator
, typename _SampleIterator
,
5912 typename _Distance
, typename _UniformRandomBitGenerator
>
5914 sample(_PopulationIterator __first
, _PopulationIterator __last
,
5915 _SampleIterator __out
, _Distance __n
,
5916 _UniformRandomBitGenerator
&& __g
)
5918 using __pop_cat
= typename
5919 std::iterator_traits
<_PopulationIterator
>::iterator_category
;
5920 using __samp_cat
= typename
5921 std::iterator_traits
<_SampleIterator
>::iterator_category
;
5924 __or_
<is_convertible
<__pop_cat
, forward_iterator_tag
>,
5925 is_convertible
<__samp_cat
, random_access_iterator_tag
>>::value
,
5926 "output range must use a RandomAccessIterator when input range"
5927 " does not meet the ForwardIterator requirements");
5929 static_assert(is_integral
<_Distance
>::value
,
5930 "sample size must be an integer type");
5932 typename iterator_traits
<_PopulationIterator
>::difference_type __d
= __n
;
5933 return _GLIBCXX_STD_A::
5934 __sample(__first
, __last
, __pop_cat
{}, __out
, __samp_cat
{}, __d
,
5935 std::forward
<_UniformRandomBitGenerator
>(__g
));
5940 _GLIBCXX_END_NAMESPACE_ALGO
5941 _GLIBCXX_END_NAMESPACE_VERSION
5944 #endif /* _STL_ALGO_H */