64#if __cplusplus >= 201103L
70# if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
75#pragma GCC diagnostic push
76#pragma GCC diagnostic ignored "-Wc++11-extensions"
80namespace std _GLIBCXX_VISIBILITY(default)
82_GLIBCXX_BEGIN_NAMESPACE_VERSION
85 template<
typename _Iterator,
typename _Compare>
89 _Iterator __c, _Compare __comp)
94 std::iter_swap(__result, __b);
95 else if (__comp(__a, __c))
96 std::iter_swap(__result, __c);
98 std::iter_swap(__result, __a);
100 else if (__comp(__a, __c))
101 std::iter_swap(__result, __a);
102 else if (__comp(__b, __c))
103 std::iter_swap(__result, __c);
105 std::iter_swap(__result, __b);
109 template<
typename _InputIterator,
typename _Predicate>
111 inline _InputIterator
115 return std::__find_if(__first, __last,
116 __gnu_cxx::__ops::__negate(__pred));
122 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
127 for (; __len; --__len, (void) ++__first)
128 if (!__pred(__first))
150 template<
typename _ForwardIterator,
typename _Integer,
151 typename _UnaryPredicate>
155 _Integer __count, _UnaryPredicate __unary_pred,
158 __first = std::__find_if(__first, __last, __unary_pred);
159 while (__first != __last)
163 _ForwardIterator __i = __first;
165 while (__i != __last && __n != 1 && __unary_pred(__i))
174 __first = std::__find_if(++__i, __last, __unary_pred);
183 template<
typename _RandomAccessIter,
typename _Integer,
184 typename _UnaryPredicate>
188 _Integer __count, _UnaryPredicate __unary_pred,
194 _DistanceType __tailSize = __last - __first;
195 _DistanceType __remainder = __count;
197 while (__remainder <= __tailSize)
199 __first += __remainder;
200 __tailSize -= __remainder;
203 _RandomAccessIter __backTrack = __first;
204 while (__unary_pred(--__backTrack))
206 if (--__remainder == 0)
207 return __first - _DistanceType(__count);
209 __remainder = __count + 1 - (__first - __backTrack);
214 template<
typename _ForwardIterator,
typename _Integer,
215 typename _UnaryPredicate>
218 __search_n(_ForwardIterator __first, _ForwardIterator __last,
220 _UnaryPredicate __unary_pred)
226 return std::__find_if(__first, __last, __unary_pred);
233 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
234 typename _BinaryPredicate>
237 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
238 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
240 _BinaryPredicate __comp)
242 if (__first2 == __last2)
245 _ForwardIterator1 __result = __last1;
248 _ForwardIterator1 __new_result
249 = std::__search(__first1, __last1, __first2, __last2, __comp);
250 if (__new_result == __last1)
254 __result = __new_result;
255 __first1 = __new_result;
262 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
263 typename _BinaryPredicate>
265 _BidirectionalIterator1
266 __find_end(_BidirectionalIterator1 __first1,
267 _BidirectionalIterator1 __last1,
268 _BidirectionalIterator2 __first2,
269 _BidirectionalIterator2 __last2,
271 _BinaryPredicate __comp)
274 __glibcxx_function_requires(_BidirectionalIteratorConcept<
275 _BidirectionalIterator1>)
276 __glibcxx_function_requires(_BidirectionalIteratorConcept<
277 _BidirectionalIterator2>)
282 _RevIterator1 __rlast1(__first1);
283 _RevIterator2 __rlast2(__first2);
284 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
285 _RevIterator2(__last2), __rlast2,
288 if (__rresult == __rlast1)
292 _BidirectionalIterator1 __result = __rresult.
base();
324 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
325 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
326 inline _ForwardIterator1
327 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
328 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
331 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
332 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
333 __glibcxx_function_requires(_EqualOpConcept<
336 __glibcxx_requires_valid_range(__first1, __last1);
337 __glibcxx_requires_valid_range(__first2, __last2);
339 return std::__find_end(__first1, __last1, __first2, __last2,
342 __gnu_cxx::__ops::__iter_equal_to_iter());
373 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
374 typename _BinaryPredicate>
375 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
376 inline _ForwardIterator1
377 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
378 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
379 _BinaryPredicate __comp)
382 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
383 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
384 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
387 __glibcxx_requires_valid_range(__first1, __last1);
388 __glibcxx_requires_valid_range(__first2, __last2);
390 return std::__find_end(__first1, __last1, __first2, __last2,
393 __gnu_cxx::__ops::__iter_comp_iter(__comp));
396#if __cplusplus >= 201103L
409 template<
typename _InputIterator,
typename _Predicate>
410 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
412 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
413 {
return __last == std::find_if_not(__first, __last, __pred); }
427 template<
typename _InputIterator,
typename _Predicate>
428 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
430 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
431 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
446 template<
typename _InputIterator,
typename _Predicate>
447 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
449 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
450 {
return !std::none_of(__first, __last, __pred); }
462 template<
typename _InputIterator,
typename _Predicate>
463 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
464 inline _InputIterator
465 find_if_not(_InputIterator __first, _InputIterator __last,
469 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
470 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
472 __glibcxx_requires_valid_range(__first, __last);
474 __gnu_cxx::__ops::__pred_iter(__pred));
487 template<
typename _InputIterator,
typename _Predicate>
488 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
490 is_partitioned(_InputIterator __first, _InputIterator __last,
493 __first = std::find_if_not(__first, __last, __pred);
494 if (__first == __last)
497 return std::none_of(__first, __last, __pred);
509 template<
typename _ForwardIterator,
typename _Predicate>
510 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
512 partition_point(_ForwardIterator __first, _ForwardIterator __last,
516 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
517 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
521 __glibcxx_requires_valid_range(__first, __last);
530 _DistanceType __half = __len >> 1;
531 _ForwardIterator __middle = __first;
533 if (__pred(*__middle))
537 __len = __len - __half - 1;
546 template<
typename _InputIterator,
typename _OutputIterator,
550 __remove_copy_if(_InputIterator __first, _InputIterator __last,
551 _OutputIterator __result, _Predicate __pred)
553 for (; __first != __last; ++__first)
554 if (!__pred(__first))
556 *__result = *__first;
576 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
578 inline _OutputIterator
579 remove_copy(_InputIterator __first, _InputIterator __last,
580 _OutputIterator __result,
const _Tp& __value)
583 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
584 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
586 __glibcxx_function_requires(_EqualOpConcept<
588 __glibcxx_requires_valid_range(__first, __last);
590 return std::__remove_copy_if(__first, __last, __result,
591 __gnu_cxx::__ops::__iter_equals_val(__value));
609 template<
typename _InputIterator,
typename _OutputIterator,
612 inline _OutputIterator
613 remove_copy_if(_InputIterator __first, _InputIterator __last,
614 _OutputIterator __result, _Predicate __pred)
617 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
618 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
620 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
622 __glibcxx_requires_valid_range(__first, __last);
624 return std::__remove_copy_if(__first, __last, __result,
625 __gnu_cxx::__ops::__pred_iter(__pred));
628#if __cplusplus >= 201103L
644 template<
typename _InputIterator,
typename _OutputIterator,
648 copy_if(_InputIterator __first, _InputIterator __last,
649 _OutputIterator __result, _Predicate __pred)
652 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
653 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
655 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
657 __glibcxx_requires_valid_range(__first, __last);
659 for (; __first != __last; ++__first)
660 if (__pred(*__first))
662 *__result = *__first;
681 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
683 inline _OutputIterator
684 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
687 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
688 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
691 const auto __n2 = std::__size_to_integer(__n);
695 __glibcxx_requires_can_increment(__first, __n2);
696 __glibcxx_requires_can_increment(__result, __n2);
698 auto __res = std::__copy_n_a(std::__niter_base(__first), __n2,
699 std::__niter_base(__result),
true);
700 return std::__niter_wrap(__result,
std::move(__res));
718 template<
typename _InputIterator,
typename _OutputIterator1,
719 typename _OutputIterator2,
typename _Predicate>
722 partition_copy(_InputIterator __first, _InputIterator __last,
723 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
727 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
728 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
730 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
732 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
734 __glibcxx_requires_valid_range(__first, __last);
736 for (; __first != __last; ++__first)
737 if (__pred(*__first))
739 *__out_true = *__first;
744 *__out_false = *__first;
769 template<
typename _ForwardIterator,
typename _Tp>
770 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
771 inline _ForwardIterator
772 remove(_ForwardIterator __first, _ForwardIterator __last,
776 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
778 __glibcxx_function_requires(_EqualOpConcept<
780 __glibcxx_requires_valid_range(__first, __last);
782 return std::__remove_if(__first, __last,
783 __gnu_cxx::__ops::__iter_equals_val(__value));
803 template<
typename _ForwardIterator,
typename _Predicate>
804 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
805 inline _ForwardIterator
806 remove_if(_ForwardIterator __first, _ForwardIterator __last,
810 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
812 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
814 __glibcxx_requires_valid_range(__first, __last);
816 return std::__remove_if(__first, __last,
817 __gnu_cxx::__ops::__pred_iter(__pred));
820 template<
typename _ForwardIterator,
typename _BinaryPredicate>
823 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
824 _BinaryPredicate __binary_pred)
826 if (__first == __last)
828 _ForwardIterator __next = __first;
829 while (++__next != __last)
831 if (__binary_pred(__first, __next))
838 template<
typename _ForwardIterator,
typename _BinaryPredicate>
841 __unique(_ForwardIterator __first, _ForwardIterator __last,
842 _BinaryPredicate __binary_pred)
845 __first = std::__adjacent_find(__first, __last, __binary_pred);
846 if (__first == __last)
850 _ForwardIterator __dest = __first;
852 while (++__first != __last)
853 if (!__binary_pred(__dest, __first))
854 *++__dest = _GLIBCXX_MOVE(*__first);
872 template<
typename _ForwardIterator>
873 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
874 inline _ForwardIterator
875 unique(_ForwardIterator __first, _ForwardIterator __last)
878 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
880 __glibcxx_function_requires(_EqualityComparableConcept<
882 __glibcxx_requires_valid_range(__first, __last);
884 return std::__unique(__first, __last,
885 __gnu_cxx::__ops::__iter_equal_to_iter());
903 template<
typename _ForwardIterator,
typename _BinaryPredicate>
904 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
905 inline _ForwardIterator
906 unique(_ForwardIterator __first, _ForwardIterator __last,
907 _BinaryPredicate __binary_pred)
910 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
912 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
915 __glibcxx_requires_valid_range(__first, __last);
917 return std::__unique(__first, __last,
918 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
926 template<
typename _ForwardIterator,
typename _OutputIterator,
927 typename _BinaryPredicate>
930 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
931 _OutputIterator __result, _BinaryPredicate __binary_pred,
932 forward_iterator_tag)
934 _ForwardIterator __prev = __first;
935 *__result = *__first;
936 while (++__first != __last)
937 if (!__binary_pred(__prev, __first))
939 *++__result = *__first;
947 template<
typename _InputIterator,
typename _OutputIterator,
948 typename _BinaryPredicate>
951 __unique_copy_1(_InputIterator __first, _InputIterator __last,
952 _OutputIterator __result, _BinaryPredicate __binary_pred,
956 _Val __value = *__first;
958 while (++__first != __last)
962 *++__result = __value;
969 template<
typename _InputIterator,
typename _ForwardIterator,
970 typename _BinaryPredicate>
972 __unique_copy_1(_InputIterator __first, _InputIterator __last,
973 _ForwardIterator __result, _BinaryPredicate __binary_pred,
976 *__result = *__first;
977 while (++__first != __last)
978 if (!__binary_pred(__result, __first))
979 *++__result = *__first;
986 template<
typename _InputIterator,
typename _OutputIterator,
987 typename _BinaryPredicate>
990 __unique_copy(_InputIterator __first, _InputIterator __last,
991 _OutputIterator __result, _BinaryPredicate __binary_pred,
998 typedef typename _OutItTraits::iterator_category _Cat;
1000 const bool __same_type = __is_same(
typename _OutItTraits::value_type,
1001 typename _InItTraits::value_type);
1002 typedef __truth_type<__output_is_fwd && __same_type> __cmp_with_output;
1003 return std::__unique_copy_1(__first, __last, __result, __binary_pred,
1004 typename __cmp_with_output::__type());
1013 template<
typename _B
idirectionalIterator>
1014 _GLIBCXX20_CONSTEXPR
1016 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1020 if (__first == __last || __first == --__last)
1024 std::iter_swap(__first, __last);
1034 template<
typename _RandomAccessIterator>
1035 _GLIBCXX20_CONSTEXPR
1037 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1040 if (__first == __last)
1043 while (__first < __last)
1045 std::iter_swap(__first, __last);
1063 template<
typename _B
idirectionalIterator>
1064 _GLIBCXX20_CONSTEXPR
1066 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1069 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1070 _BidirectionalIterator>)
1071 __glibcxx_requires_valid_range(__first, __last);
1091 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1092 _GLIBCXX20_CONSTEXPR
1094 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1095 _OutputIterator __result)
1098 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1099 _BidirectionalIterator>)
1100 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1102 __glibcxx_requires_valid_range(__first, __last);
1104 while (__first != __last)
1107 *__result = *__last;
1117 template<
typename _Eucl
ideanRingElement>
1118 _GLIBCXX20_CONSTEXPR
1119 _EuclideanRingElement
1120 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1124 _EuclideanRingElement __t = __m % __n;
1131_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1134 template<
typename _ForwardIterator>
1135 _GLIBCXX20_CONSTEXPR
1138 _ForwardIterator __middle,
1139 _ForwardIterator __last,
1142 if (__first == __middle)
1144 else if (__last == __middle)
1147 _ForwardIterator __first2 = __middle;
1150 std::iter_swap(__first, __first2);
1153 if (__first == __middle)
1154 __middle = __first2;
1156 while (__first2 != __last);
1158 _ForwardIterator __ret = __first;
1160 __first2 = __middle;
1162 while (__first2 != __last)
1164 std::iter_swap(__first, __first2);
1167 if (__first == __middle)
1168 __middle = __first2;
1169 else if (__first2 == __last)
1170 __first2 = __middle;
1176 template<
typename _B
idirectionalIterator>
1177 _GLIBCXX20_CONSTEXPR
1178 _BidirectionalIterator
1180 _BidirectionalIterator __middle,
1181 _BidirectionalIterator __last,
1185 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1186 _BidirectionalIterator>)
1188 if (__first == __middle)
1190 else if (__last == __middle)
1196 while (__first != __middle && __middle != __last)
1198 std::iter_swap(__first, --__last);
1202 if (__first == __middle)
1215 template<
typename _RandomAccessIterator>
1216 _GLIBCXX20_CONSTEXPR
1217 _RandomAccessIterator
1219 _RandomAccessIterator __middle,
1220 _RandomAccessIterator __last,
1224 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1225 _RandomAccessIterator>)
1227 if (__first == __middle)
1229 else if (__last == __middle)
1237#if __cplusplus >= 201103L
1238 typedef typename make_unsigned<_Distance>::type _UDistance;
1240 typedef _Distance _UDistance;
1243 _Distance __n = __last - __first;
1244 _Distance __k = __middle - __first;
1246 if (__k == __n - __k)
1248 std::swap_ranges(__first, __middle, __middle);
1252 _RandomAccessIterator __p = __first;
1253 _RandomAccessIterator __ret = __first + (__last - __middle);
1257 if (__k < __n - __k)
1259 if (__is_pod(_ValueType) && __k == 1)
1261 _RandomAccessIterator __mid = __p + _Distance(__n - 1);
1262 _RandomAccessIterator __end = __mid;
1264 _ValueType __t = _GLIBCXX_MOVE(*__p);
1265 _GLIBCXX_MOVE3(__p + _Distance(1), __end, __p);
1266 *__mid = _GLIBCXX_MOVE(__t);
1269 _RandomAccessIterator __q = __p + __k;
1270 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1272 std::iter_swap(__p, __q);
1276 __n =
static_cast<_UDistance
>(__n) %
static_cast<_UDistance
>(__k);
1279 std::swap(__n, __k);
1285 if (__is_pod(_ValueType) && __k == 1)
1287 _RandomAccessIterator __mid = __p + _Distance(__n - 1);
1288 _RandomAccessIterator __end = __mid;
1290 _ValueType __t = _GLIBCXX_MOVE(*__mid);
1291 _GLIBCXX_MOVE_BACKWARD3(__p, __mid, __end);
1292 *__p = _GLIBCXX_MOVE(__t);
1295 _RandomAccessIterator __q = __p + __n;
1297 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1301 std::iter_swap(__p, __q);
1303 __n =
static_cast<_UDistance
>(__n) %
static_cast<_UDistance
>(__k);
1306 std::swap(__n, __k);
1334 template<
typename _ForwardIterator>
1335 _GLIBCXX20_CONSTEXPR
1336 inline _ForwardIterator
1337 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1338 _ForwardIterator __last)
1341 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1343 __glibcxx_requires_valid_range(__first, __middle);
1344 __glibcxx_requires_valid_range(__middle, __last);
1350_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1372 template<
typename _ForwardIterator,
typename _OutputIterator>
1373 _GLIBCXX20_CONSTEXPR
1374 inline _OutputIterator
1375 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1376 _ForwardIterator __last, _OutputIterator __result)
1379 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1380 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1382 __glibcxx_requires_valid_range(__first, __middle);
1383 __glibcxx_requires_valid_range(__middle, __last);
1385 return std::copy(__first, __middle,
1386 std::copy(__middle, __last, __result));
1390 template<
typename _ForwardIterator,
typename _Predicate>
1391 _GLIBCXX20_CONSTEXPR
1396 if (__first == __last)
1399 while (__pred(*__first))
1400 if (++__first == __last)
1403 _ForwardIterator __next = __first;
1405 while (++__next != __last)
1406 if (__pred(*__next))
1408 std::iter_swap(__first, __next);
1416 template<
typename _B
idirectionalIterator,
typename _Predicate>
1417 _GLIBCXX20_CONSTEXPR
1418 _BidirectionalIterator
1419 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1425 if (__first == __last)
1427 else if (__pred(*__first))
1433 if (__first == __last)
1435 else if (!
bool(__pred(*__last)))
1439 std::iter_swap(__first, __last);
1453 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1455 _GLIBCXX26_CONSTEXPR
1458 _ForwardIterator __last,
1459 _Predicate __pred, _Distance __len,
1461 _Distance __buffer_size)
1466 if (__len <= __buffer_size)
1468 _ForwardIterator __result1 = __first;
1469 _Pointer __result2 = __buffer;
1474 *__result2 = _GLIBCXX_MOVE(*__first);
1477 for (; __first != __last; ++__first)
1478 if (__pred(__first))
1480 *__result1 = _GLIBCXX_MOVE(*__first);
1485 *__result2 = _GLIBCXX_MOVE(*__first);
1489 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1493 _ForwardIterator __middle = __first;
1495 _ForwardIterator __left_split =
1497 __len / 2, __buffer,
1502 _Distance __right_len = __len - __len / 2;
1503 _ForwardIterator __right_split =
1510 __buffer, __buffer_size);
1512 return std::rotate(__left_split, __middle, __right_split);
1515 template<
typename _ForwardIterator,
typename _Predicate>
1516 _GLIBCXX26_CONSTEXPR
1518 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1523 if (__first == __last)
1526 typedef typename iterator_traits<_ForwardIterator>::value_type
1528 typedef typename iterator_traits<_ForwardIterator>::difference_type
1533#if __glibcxx_constexpr_algorithms >= 202306L
1546 __buf(__first, __len);
1551 _DistanceType(__buf.size()));
1571 template<
typename _ForwardIterator,
typename _Predicate>
1572 _GLIBCXX26_CONSTEXPR
1573 inline _ForwardIterator
1574 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1578 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1580 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1582 __glibcxx_requires_valid_range(__first, __last);
1584 return std::__stable_partition(__first, __last,
1585 __gnu_cxx::__ops::__pred_iter(__pred));
1592 template<
typename _RandomAccessIterator,
typename _Compare>
1593 _GLIBCXX20_CONSTEXPR
1595 __heap_select(_RandomAccessIterator __first,
1596 _RandomAccessIterator __middle,
1597 _RandomAccessIterator __last, _Compare __comp)
1599 std::__make_heap(__first, __middle, __comp);
1600 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1601 if (__comp(__i, __first))
1602 std::__pop_heap(__first, __middle, __i, __comp);
1607 template<
typename _InputIterator,
typename _RandomAccessIterator,
1609 _GLIBCXX20_CONSTEXPR
1610 _RandomAccessIterator
1611 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1612 _RandomAccessIterator __result_first,
1613 _RandomAccessIterator __result_last,
1619 typedef typename _RItTraits::difference_type _DistanceType;
1621 if (__result_first == __result_last)
1622 return __result_last;
1623 _RandomAccessIterator __result_real_last = __result_first;
1624 while (__first != __last && __result_real_last != __result_last)
1626 *__result_real_last = *__first;
1627 ++__result_real_last;
1631 std::__make_heap(__result_first, __result_real_last, __comp);
1632 while (__first != __last)
1634 if (__comp(__first, __result_first))
1635 std::__adjust_heap(__result_first, _DistanceType(0),
1636 _DistanceType(__result_real_last
1638 _InputValueType(*__first), __comp);
1641 std::__sort_heap(__result_first, __result_real_last, __comp);
1642 return __result_real_last;
1665 template<
typename _InputIterator,
typename _RandomAccessIterator>
1666 _GLIBCXX20_CONSTEXPR
1667 inline _RandomAccessIterator
1668 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1669 _RandomAccessIterator __result_first,
1670 _RandomAccessIterator __result_last)
1672#ifdef _GLIBCXX_CONCEPT_CHECKS
1680 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1681 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1683 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1685 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1686 __glibcxx_requires_valid_range(__first, __last);
1687 __glibcxx_requires_irreflexive(__first, __last);
1688 __glibcxx_requires_valid_range(__result_first, __result_last);
1690 return std::__partial_sort_copy(__first, __last,
1691 __result_first, __result_last,
1692 __gnu_cxx::__ops::__iter_less_iter());
1715 template<
typename _InputIterator,
typename _RandomAccessIterator,
1717 _GLIBCXX20_CONSTEXPR
1718 inline _RandomAccessIterator
1719 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1720 _RandomAccessIterator __result_first,
1721 _RandomAccessIterator __result_last,
1724#ifdef _GLIBCXX_CONCEPT_CHECKS
1732 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1733 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1734 _RandomAccessIterator>)
1735 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1737 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1738 _InputValueType, _OutputValueType>)
1739 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1740 _OutputValueType, _OutputValueType>)
1741 __glibcxx_requires_valid_range(__first, __last);
1742 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1743 __glibcxx_requires_valid_range(__result_first, __result_last);
1745 return std::__partial_sort_copy(__first, __last,
1746 __result_first, __result_last,
1747 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1753 template<
typename _RandomAccessIterator,
typename _Compare>
1754 _GLIBCXX20_CONSTEXPR
1756 __unguarded_linear_insert(_RandomAccessIterator __last,
1759 typename iterator_traits<_RandomAccessIterator>::value_type
1760 __val = _GLIBCXX_MOVE(*__last);
1761 _RandomAccessIterator __next = __last;
1763 while (__comp(__val, __next))
1765 *__last = _GLIBCXX_MOVE(*__next);
1769 *__last = _GLIBCXX_MOVE(__val);
1773 template<
typename _RandomAccessIterator,
typename _Compare>
1774 _GLIBCXX20_CONSTEXPR
1776 __insertion_sort(_RandomAccessIterator __first,
1777 _RandomAccessIterator __last, _Compare __comp)
1779 if (__first == __last)
1783 typedef typename _IterTraits::difference_type _Dist;
1785 for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last; ++__i)
1787 if (__comp(__i, __first))
1789 typename _IterTraits::value_type __val = _GLIBCXX_MOVE(*__i);
1790 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + _Dist(1));
1791 *__first = _GLIBCXX_MOVE(__val);
1794 std::__unguarded_linear_insert(__i,
1795 __gnu_cxx::__ops::__val_comp_iter(__comp));
1800 template<
typename _RandomAccessIterator,
typename _Compare>
1801 _GLIBCXX20_CONSTEXPR
1803 __unguarded_insertion_sort(_RandomAccessIterator __first,
1804 _RandomAccessIterator __last, _Compare __comp)
1806 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1807 std::__unguarded_linear_insert(__i,
1808 __gnu_cxx::__ops::__val_comp_iter(__comp));
1815 enum { _S_threshold = 16 };
1818 template<
typename _RandomAccessIterator,
typename _Compare>
1819 _GLIBCXX20_CONSTEXPR
1821 __final_insertion_sort(_RandomAccessIterator __first,
1822 _RandomAccessIterator __last, _Compare __comp)
1825 __threshold = _S_threshold;
1827 if (__last - __first > __threshold)
1829 std::__insertion_sort(__first, __first + __threshold, __comp);
1830 std::__unguarded_insertion_sort(__first + __threshold, __last,
1834 std::__insertion_sort(__first, __last, __comp);
1838 template<
typename _RandomAccessIterator,
typename _Compare>
1839 _GLIBCXX20_CONSTEXPR
1840 _RandomAccessIterator
1841 __unguarded_partition(_RandomAccessIterator __first,
1842 _RandomAccessIterator __last,
1843 _RandomAccessIterator __pivot, _Compare __comp)
1847 while (__comp(__first, __pivot))
1850 while (__comp(__pivot, __last))
1852 if (!(__first < __last))
1854 std::iter_swap(__first, __last);
1860 template<
typename _RandomAccessIterator,
typename _Compare>
1861 _GLIBCXX20_CONSTEXPR
1862 inline _RandomAccessIterator
1863 __unguarded_partition_pivot(_RandomAccessIterator __first,
1864 _RandomAccessIterator __last, _Compare __comp)
1867 typedef typename _IterTraits::difference_type _Dist;
1869 _RandomAccessIterator __mid = __first + _Dist((__last - __first) / 2);
1870 _RandomAccessIterator __second = __first + _Dist(1);
1873 return std::__unguarded_partition(__second, __last, __first, __comp);
1876 template<
typename _RandomAccessIterator,
typename _Compare>
1877 _GLIBCXX20_CONSTEXPR
1879 __partial_sort(_RandomAccessIterator __first,
1880 _RandomAccessIterator __middle,
1881 _RandomAccessIterator __last,
1884 std::__heap_select(__first, __middle, __last, __comp);
1885 std::__sort_heap(__first, __middle, __comp);
1889 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1890 _GLIBCXX20_CONSTEXPR
1892 __introsort_loop(_RandomAccessIterator __first,
1893 _RandomAccessIterator __last,
1894 _Size __depth_limit, _Compare __comp)
1896 while (__last - __first >
int(_S_threshold))
1898 if (__depth_limit == 0)
1900 std::__partial_sort(__first, __last, __last, __comp);
1904 _RandomAccessIterator __cut =
1905 std::__unguarded_partition_pivot(__first, __last, __comp);
1906 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1913 template<
typename _RandomAccessIterator,
typename _Compare>
1914 _GLIBCXX20_CONSTEXPR
1916 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1919 if (__first != __last)
1921 std::__introsort_loop(__first, __last,
1924 std::__final_insertion_sort(__first, __last, __comp);
1928 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1929 _GLIBCXX20_CONSTEXPR
1931 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1932 _RandomAccessIterator __last, _Size __depth_limit,
1935 _RandomAccessIterator __after_nth = __nth;
1938 while (__last - __first > 3)
1940 if (__depth_limit == 0)
1942 std::__heap_select(__first, __after_nth, __last, __comp);
1944 std::iter_swap(__first, __nth);
1948 _RandomAccessIterator __cut =
1949 std::__unguarded_partition_pivot(__first, __last, __comp);
1955 std::__insertion_sort(__first, __last, __comp);
1979 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1980 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1981 inline _ForwardIterator
1982 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1983 const _Tp& __val, _Compare __comp)
1986 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1987 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1989 __glibcxx_requires_partitioned_lower_pred(__first, __last,
1992 return std::__lower_bound(__first, __last, __val,
1993 __gnu_cxx::__ops::__iter_comp_val(__comp));
1996 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1997 _GLIBCXX20_CONSTEXPR
1999 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2000 const _Tp& __val, _Compare __comp)
2002 typedef typename iterator_traits<_ForwardIterator>::difference_type
2009 _DistanceType __half = __len >> 1;
2010 _ForwardIterator __middle = __first;
2012 if (__comp(__val, __middle))
2018 __len = __len - __half - 1;
2035 template<
typename _ForwardIterator,
typename _Tp>
2036 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2037 inline _ForwardIterator
2038 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2042 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2043 __glibcxx_function_requires(_LessThanOpConcept<
2045 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2047 return std::__upper_bound(__first, __last, __val,
2048 __gnu_cxx::__ops::__val_less_iter());
2066 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2067 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2068 inline _ForwardIterator
2069 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2070 const _Tp& __val, _Compare __comp)
2073 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2074 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2076 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2079 return std::__upper_bound(__first, __last, __val,
2080 __gnu_cxx::__ops::__val_comp_iter(__comp));
2083 template<
typename _ForwardIterator,
typename _Tp,
2084 typename _CompareItTp,
typename _CompareTpIt>
2085 _GLIBCXX20_CONSTEXPR
2087 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2089 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2091 typedef typename iterator_traits<_ForwardIterator>::difference_type
2098 _DistanceType __half = __len >> 1;
2099 _ForwardIterator __middle = __first;
2101 if (__comp_it_val(__middle, __val))
2105 __len = __len - __half - 1;
2107 else if (__comp_val_it(__val, __middle))
2111 _ForwardIterator __left
2112 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2114 _ForwardIterator __right
2115 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2139 template<
typename _ForwardIterator,
typename _Tp>
2140 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2142 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2146 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2147 __glibcxx_function_requires(_LessThanOpConcept<
2149 __glibcxx_function_requires(_LessThanOpConcept<
2151 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2152 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2154 return std::__equal_range(__first, __last, __val,
2155 __gnu_cxx::__ops::__iter_less_val(),
2156 __gnu_cxx::__ops::__val_less_iter());
2176 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2177 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2179 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2180 const _Tp& __val, _Compare __comp)
2183 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2184 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2186 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2188 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2190 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2193 return std::__equal_range(__first, __last, __val,
2194 __gnu_cxx::__ops::__iter_comp_val(__comp),
2195 __gnu_cxx::__ops::__val_comp_iter(__comp));
2210 template<
typename _ForwardIterator,
typename _Tp>
2211 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2213 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2217 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2218 __glibcxx_function_requires(_LessThanOpConcept<
2220 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2221 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2223 _ForwardIterator __i
2224 = std::__lower_bound(__first, __last, __val,
2225 __gnu_cxx::__ops::__iter_less_val());
2226 return __i != __last && !(__val < *__i);
2244 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2245 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2247 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2248 const _Tp& __val, _Compare __comp)
2251 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2252 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2254 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2256 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2259 _ForwardIterator __i
2260 = std::__lower_bound(__first, __last, __val,
2261 __gnu_cxx::__ops::__iter_comp_val(__comp));
2262 return __i != __last && !bool(__comp(__val, *__i));
2268 template<
typename _InputIterator1,
typename _InputIterator2,
2269 typename _OutputIterator,
typename _Compare>
2272 _InputIterator2 __first2, _InputIterator2 __last2,
2273 _OutputIterator __result, _Compare __comp)
2275 while (__first1 != __last1 && __first2 != __last2)
2277 if (__comp(__first2, __first1))
2279 *__result = _GLIBCXX_MOVE(*__first2);
2284 *__result = _GLIBCXX_MOVE(*__first1);
2289 if (__first1 != __last1)
2290 _GLIBCXX_MOVE3(__first1, __last1, __result);
2294 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2295 typename _BidirectionalIterator3,
typename _Compare>
2298 _BidirectionalIterator1 __last1,
2299 _BidirectionalIterator2 __first2,
2300 _BidirectionalIterator2 __last2,
2301 _BidirectionalIterator3 __result,
2304 if (__first1 == __last1)
2306 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2309 else if (__first2 == __last2)
2316 if (__comp(__last2, __last1))
2318 *--__result = _GLIBCXX_MOVE(*__last1);
2319 if (__first1 == __last1)
2321 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2328 *--__result = _GLIBCXX_MOVE(*__last2);
2329 if (__first2 == __last2)
2337 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2339 _BidirectionalIterator1
2341 _BidirectionalIterator1 __middle,
2342 _BidirectionalIterator1 __last,
2343 _Distance __len1, _Distance __len2,
2344 _BidirectionalIterator2 __buffer,
2345 _Distance __buffer_size)
2347 _BidirectionalIterator2 __buffer_end;
2348 if (__len1 > __len2 && __len2 <= __buffer_size)
2352 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2353 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2354 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2359 else if (__len1 <= __buffer_size)
2363 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2364 _GLIBCXX_MOVE3(__middle, __last, __first);
2365 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2371 return std::rotate(__first, __middle, __last);
2375 template<
typename _BidirectionalIterator,
typename _Distance,
2376 typename _Pointer,
typename _Compare>
2379 _BidirectionalIterator __middle,
2380 _BidirectionalIterator __last,
2381 _Distance __len1, _Distance __len2,
2382 _Pointer __buffer, _Compare __comp)
2384 if (__len1 <= __len2)
2386 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2392 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2394 __buffer_end, __last, __comp);
2398 template<
typename _BidirectionalIterator,
typename _Distance,
2399 typename _Pointer,
typename _Compare>
2401 __merge_adaptive_resize(_BidirectionalIterator __first,
2402 _BidirectionalIterator __middle,
2403 _BidirectionalIterator __last,
2404 _Distance __len1, _Distance __len2,
2405 _Pointer __buffer, _Distance __buffer_size,
2408 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2410 __len1, __len2, __buffer, __comp);
2413 _BidirectionalIterator __first_cut = __first;
2414 _BidirectionalIterator __second_cut = __middle;
2415 _Distance __len11 = 0;
2416 _Distance __len22 = 0;
2417 if (__len1 > __len2)
2419 __len11 = __len1 / 2;
2422 = std::__lower_bound(__middle, __last, *__first_cut,
2423 __gnu_cxx::__ops::__iter_comp_val(__comp));
2428 __len22 = __len2 / 2;
2431 = std::__upper_bound(__first, __middle, *__second_cut,
2432 __gnu_cxx::__ops::__val_comp_iter(__comp));
2436 _BidirectionalIterator __new_middle
2438 _Distance(__len1 - __len11), __len22,
2439 __buffer, __buffer_size);
2440 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2442 __buffer, __buffer_size, __comp);
2443 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2444 _Distance(__len1 - __len11),
2445 _Distance(__len2 - __len22),
2446 __buffer, __buffer_size, __comp);
2451 template<
typename _BidirectionalIterator,
typename _Distance,
2453 _GLIBCXX26_CONSTEXPR
2456 _BidirectionalIterator __middle,
2457 _BidirectionalIterator __last,
2458 _Distance __len1, _Distance __len2,
2461 if (__len1 == 0 || __len2 == 0)
2464 if (__len1 + __len2 == 2)
2466 if (__comp(__middle, __first))
2467 std::iter_swap(__first, __middle);
2471 _BidirectionalIterator __first_cut = __first;
2472 _BidirectionalIterator __second_cut = __middle;
2473 _Distance __len11 = 0;
2474 _Distance __len22 = 0;
2475 if (__len1 > __len2)
2477 __len11 = __len1 / 2;
2480 = std::__lower_bound(__middle, __last, *__first_cut,
2481 __gnu_cxx::__ops::__iter_comp_val(__comp));
2486 __len22 = __len2 / 2;
2489 = std::__upper_bound(__first, __middle, *__second_cut,
2490 __gnu_cxx::__ops::__val_comp_iter(__comp));
2494 _BidirectionalIterator __new_middle
2495 = std::rotate(__first_cut, __middle, __second_cut);
2497 __len11, __len22, __comp);
2499 __len1 - __len11, __len2 - __len22, __comp);
2502 template<
typename _B
idirectionalIterator,
typename _Compare>
2503 _GLIBCXX26_CONSTEXPR
2505 __inplace_merge(_BidirectionalIterator __first,
2506 _BidirectionalIterator __middle,
2507 _BidirectionalIterator __last,
2510 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2512 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2515 if (__first == __middle || __middle == __last)
2518 const _DistanceType __len1 =
std::distance(__first, __middle);
2519 const _DistanceType __len2 =
std::distance(__middle, __last);
2522# if __glibcxx_constexpr_algorithms >= 202306L
2525 (__first, __middle, __last, __len1, __len2, __comp);
2531 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2533 if (__builtin_expect(__buf.size() == __buf._M_requested_size(),
true))
2535 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2536 else if (__builtin_expect(__buf.begin() == 0,
false))
2538 (__first, __middle, __last, __len1, __len2, __comp);
2540 std::__merge_adaptive_resize
2541 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2542 _DistanceType(__buf.size()), __comp);
2545 (__first, __middle, __last, __len1, __len2, __comp);
2567 template<
typename _B
idirectionalIterator>
2568 _GLIBCXX26_CONSTEXPR
2570 inplace_merge(_BidirectionalIterator __first,
2571 _BidirectionalIterator __middle,
2572 _BidirectionalIterator __last)
2575 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2576 _BidirectionalIterator>)
2577 __glibcxx_function_requires(_LessThanComparableConcept<
2579 __glibcxx_requires_sorted(__first, __middle);
2580 __glibcxx_requires_sorted(__middle, __last);
2581 __glibcxx_requires_irreflexive(__first, __last);
2583 std::__inplace_merge(__first, __middle, __last,
2584 __gnu_cxx::__ops::__iter_less_iter());
2609 template<
typename _B
idirectionalIterator,
typename _Compare>
2610 _GLIBCXX26_CONSTEXPR
2612 inplace_merge(_BidirectionalIterator __first,
2613 _BidirectionalIterator __middle,
2614 _BidirectionalIterator __last,
2618 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2619 _BidirectionalIterator>)
2620 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2623 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2624 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2625 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2627 std::__inplace_merge(__first, __middle, __last,
2628 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2633 template<
typename _InputIterator,
typename _OutputIterator,
2637 _InputIterator __first2, _InputIterator __last2,
2638 _OutputIterator __result, _Compare __comp)
2640 while (__first1 != __last1 && __first2 != __last2)
2642 if (__comp(__first2, __first1))
2644 *__result = _GLIBCXX_MOVE(*__first2);
2649 *__result = _GLIBCXX_MOVE(*__first1);
2654 return _GLIBCXX_MOVE3(__first2, __last2,
2655 _GLIBCXX_MOVE3(__first1, __last1,
2659 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2660 typename _Distance,
typename _Compare>
2662 __merge_sort_loop(_RandomAccessIterator1 __first,
2663 _RandomAccessIterator1 __last,
2664 _RandomAccessIterator2 __result, _Distance __step_size,
2667 const _Distance __two_step = 2 * __step_size;
2669 while (__last - __first >= __two_step)
2672 __first + __step_size,
2673 __first + __two_step,
2675 __first += __two_step;
2677 __step_size =
std::min(_Distance(__last - __first), __step_size);
2680 __first + __step_size, __last, __result, __comp);
2683 template<
typename _RandomAccessIterator,
typename _Distance,
2685 _GLIBCXX20_CONSTEXPR
2687 __chunk_insertion_sort(_RandomAccessIterator __first,
2688 _RandomAccessIterator __last,
2689 _Distance __chunk_size, _Compare __comp)
2691 while (__last - __first >= __chunk_size)
2693 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2694 __first += __chunk_size;
2696 std::__insertion_sort(__first, __last, __comp);
2699 enum { _S_chunk_size = 7 };
2701 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2703 __merge_sort_with_buffer(_RandomAccessIterator __first,
2704 _RandomAccessIterator __last,
2705 _Pointer __buffer, _Compare __comp)
2710 const _Distance __len = __last - __first;
2711 const _Pointer __buffer_last = __buffer + __len;
2713 _Distance __step_size = _S_chunk_size;
2714 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2716 while (__step_size < __len)
2718 std::__merge_sort_loop(__first, __last, __buffer,
2719 __step_size, __comp);
2721 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2722 __step_size, __comp);
2727 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2729 __stable_sort_adaptive(_RandomAccessIterator __first,
2730 _RandomAccessIterator __middle,
2731 _RandomAccessIterator __last,
2732 _Pointer __buffer, _Compare __comp)
2734 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2735 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2738 __middle - __first, __last - __middle,
2742 template<
typename _RandomAccessIterator,
typename _Pointer,
2743 typename _Distance,
typename _Compare>
2745 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2746 _RandomAccessIterator __last,
2747 _Pointer __buffer, _Distance __buffer_size,
2750 const _Distance __len = (__last - __first + 1) / 2;
2751 const _RandomAccessIterator __middle = __first + __len;
2752 if (__len > __buffer_size)
2754 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2755 __buffer_size, __comp);
2756 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2757 __buffer_size, __comp);
2758 std::__merge_adaptive_resize(__first, __middle, __last,
2759 _Distance(__middle - __first),
2760 _Distance(__last - __middle),
2761 __buffer, __buffer_size,
2765 std::__stable_sort_adaptive(__first, __middle, __last,
2770 template<
typename _RandomAccessIterator,
typename _Compare>
2771 _GLIBCXX26_CONSTEXPR
2774 _RandomAccessIterator __last, _Compare __comp)
2776 if (__last - __first < 15)
2778 std::__insertion_sort(__first, __last, __comp);
2781 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2797 template<
typename _InputIterator1,
typename _InputIterator2,
2799 _GLIBCXX20_CONSTEXPR
2801 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2802 _InputIterator2 __first2, _InputIterator2 __last2,
2805 while (__first1 != __last1 && __first2 != __last2)
2807 if (__comp(__first2, __first1))
2809 if (!__comp(__first1, __first2))
2814 return __first2 == __last2;
2835 template<
typename _InputIterator1,
typename _InputIterator2>
2836 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2838 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2839 _InputIterator2 __first2, _InputIterator2 __last2)
2842 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2843 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2844 __glibcxx_function_requires(_LessThanOpConcept<
2847 __glibcxx_function_requires(_LessThanOpConcept<
2850 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2851 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2852 __glibcxx_requires_irreflexive2(__first1, __last1);
2853 __glibcxx_requires_irreflexive2(__first2, __last2);
2855 return std::__includes(__first1, __last1, __first2, __last2,
2856 __gnu_cxx::__ops::__iter_less_iter());
2880 template<
typename _InputIterator1,
typename _InputIterator2,
2882 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2884 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2885 _InputIterator2 __first2, _InputIterator2 __last2,
2889 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2890 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2891 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2894 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2897 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2898 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2899 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2900 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2902 return std::__includes(__first1, __last1, __first2, __last2,
2903 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2916 template<
typename _B
idirectionalIterator,
typename _Compare>
2917 _GLIBCXX20_CONSTEXPR
2919 __next_permutation(_BidirectionalIterator __first,
2920 _BidirectionalIterator __last, _Compare __comp)
2922 if (__first == __last)
2924 _BidirectionalIterator __i = __first;
2933 _BidirectionalIterator __ii = __i;
2935 if (__comp(__i, __ii))
2937 _BidirectionalIterator __j = __last;
2938 while (!__comp(__i, --__j))
2940 std::iter_swap(__i, __j);
2966 template<
typename _B
idirectionalIterator>
2967 _GLIBCXX20_CONSTEXPR
2969 next_permutation(_BidirectionalIterator __first,
2970 _BidirectionalIterator __last)
2973 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2974 _BidirectionalIterator>)
2975 __glibcxx_function_requires(_LessThanComparableConcept<
2977 __glibcxx_requires_valid_range(__first, __last);
2978 __glibcxx_requires_irreflexive(__first, __last);
2980 return std::__next_permutation
2981 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2999 template<
typename _B
idirectionalIterator,
typename _Compare>
3000 _GLIBCXX20_CONSTEXPR
3002 next_permutation(_BidirectionalIterator __first,
3003 _BidirectionalIterator __last, _Compare __comp)
3006 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3007 _BidirectionalIterator>)
3008 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3011 __glibcxx_requires_valid_range(__first, __last);
3012 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3014 return std::__next_permutation
3015 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3018 template<
typename _B
idirectionalIterator,
typename _Compare>
3019 _GLIBCXX20_CONSTEXPR
3021 __prev_permutation(_BidirectionalIterator __first,
3022 _BidirectionalIterator __last, _Compare __comp)
3024 if (__first == __last)
3026 _BidirectionalIterator __i = __first;
3035 _BidirectionalIterator __ii = __i;
3037 if (__comp(__ii, __i))
3039 _BidirectionalIterator __j = __last;
3040 while (!__comp(--__j, __i))
3042 std::iter_swap(__i, __j);
3069 template<
typename _B
idirectionalIterator>
3070 _GLIBCXX20_CONSTEXPR
3072 prev_permutation(_BidirectionalIterator __first,
3073 _BidirectionalIterator __last)
3076 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3077 _BidirectionalIterator>)
3078 __glibcxx_function_requires(_LessThanComparableConcept<
3080 __glibcxx_requires_valid_range(__first, __last);
3081 __glibcxx_requires_irreflexive(__first, __last);
3083 return std::__prev_permutation(__first, __last,
3084 __gnu_cxx::__ops::__iter_less_iter());
3102 template<
typename _B
idirectionalIterator,
typename _Compare>
3103 _GLIBCXX20_CONSTEXPR
3105 prev_permutation(_BidirectionalIterator __first,
3106 _BidirectionalIterator __last, _Compare __comp)
3109 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3110 _BidirectionalIterator>)
3111 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3114 __glibcxx_requires_valid_range(__first, __last);
3115 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3117 return std::__prev_permutation(__first, __last,
3118 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3124 template<
typename _InputIterator,
typename _OutputIterator,
3125 typename _Predicate,
typename _Tp>
3126 _GLIBCXX20_CONSTEXPR
3128 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3129 _OutputIterator __result,
3130 _Predicate __pred,
const _Tp& __new_value)
3132 for (; __first != __last; ++__first, (void)++__result)
3133 if (__pred(__first))
3134 *__result = __new_value;
3136 *__result = *__first;
3154 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3155 _GLIBCXX20_CONSTEXPR
3156 inline _OutputIterator
3157 replace_copy(_InputIterator __first, _InputIterator __last,
3158 _OutputIterator __result,
3159 const _Tp& __old_value,
const _Tp& __new_value)
3162 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3163 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3165 __glibcxx_function_requires(_EqualOpConcept<
3167 __glibcxx_requires_valid_range(__first, __last);
3169 return std::__replace_copy_if(__first, __last, __result,
3170 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3189 template<
typename _InputIterator,
typename _OutputIterator,
3190 typename _Predicate,
typename _Tp>
3191 _GLIBCXX20_CONSTEXPR
3192 inline _OutputIterator
3193 replace_copy_if(_InputIterator __first, _InputIterator __last,
3194 _OutputIterator __result,
3195 _Predicate __pred,
const _Tp& __new_value)
3198 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3199 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3201 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3203 __glibcxx_requires_valid_range(__first, __last);
3205 return std::__replace_copy_if(__first, __last, __result,
3206 __gnu_cxx::__ops::__pred_iter(__pred),
3210#if __cplusplus >= 201103L
3218 template<
typename _ForwardIterator>
3219 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3221 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3222 {
return std::is_sorted_until(__first, __last) == __last; }
3233 template<
typename _ForwardIterator,
typename _Compare>
3234 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3236 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3238 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3240 template<
typename _ForwardIterator,
typename _Compare>
3241 _GLIBCXX20_CONSTEXPR
3243 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3246 if (__first == __last)
3249 _ForwardIterator __next = __first;
3250 for (++__next; __next != __last; __first = __next, (void)++__next)
3251 if (__comp(__next, __first))
3264 template<
typename _ForwardIterator>
3265 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3266 inline _ForwardIterator
3267 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3270 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3271 __glibcxx_function_requires(_LessThanComparableConcept<
3273 __glibcxx_requires_valid_range(__first, __last);
3274 __glibcxx_requires_irreflexive(__first, __last);
3276 return std::__is_sorted_until(__first, __last,
3277 __gnu_cxx::__ops::__iter_less_iter());
3289 template<
typename _ForwardIterator,
typename _Compare>
3290 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3291 inline _ForwardIterator
3292 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3296 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3297 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3300 __glibcxx_requires_valid_range(__first, __last);
3301 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3303 return std::__is_sorted_until(__first, __last,
3304 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3315 template<
typename _Tp>
3316 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3321 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3323 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3336 template<
typename _Tp,
typename _Compare>
3337 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3339 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3345 template<
typename _ForwardIterator,
typename _Compare>
3346 _GLIBCXX14_CONSTEXPR
3348 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3351 _ForwardIterator __next = __first;
3352 if (__first == __last
3353 || ++__next == __last)
3356 _ForwardIterator __min{}, __max{};
3357 if (__comp(__next, __first))
3371 while (__first != __last)
3374 if (++__next == __last)
3376 if (__comp(__first, __min))
3378 else if (!__comp(__first, __max))
3383 if (__comp(__next, __first))
3385 if (__comp(__next, __min))
3387 if (!__comp(__first, __max))
3392 if (__comp(__first, __min))
3394 if (!__comp(__next, __max))
3416 template<
typename _ForwardIterator>
3417 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3419 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3422 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3423 __glibcxx_function_requires(_LessThanComparableConcept<
3425 __glibcxx_requires_valid_range(__first, __last);
3426 __glibcxx_requires_irreflexive(__first, __last);
3428 return std::__minmax_element(__first, __last,
3429 __gnu_cxx::__ops::__iter_less_iter());
3444 template<
typename _ForwardIterator,
typename _Compare>
3445 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3447 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3451 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3452 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3455 __glibcxx_requires_valid_range(__first, __last);
3456 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3458 return std::__minmax_element(__first, __last,
3459 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3462 template<
typename _Tp>
3463 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3464 inline pair<_Tp, _Tp>
3465 minmax(initializer_list<_Tp> __l)
3467 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3469 std::__minmax_element(__l.begin(), __l.end(),
3470 __gnu_cxx::__ops::__iter_less_iter());
3474 template<
typename _Tp,
typename _Compare>
3475 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3479 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3481 std::__minmax_element(__l.begin(), __l.end(),
3482 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3500 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3501 typename _BinaryPredicate>
3502 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3504 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3505 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3508 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3509 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3510 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3513 __glibcxx_requires_valid_range(__first1, __last1);
3515 return std::__is_permutation(__first1, __last1, __first2,
3516 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3519#if __cplusplus > 201103L
3520#pragma GCC diagnostic push
3521#pragma GCC diagnostic ignored "-Wc++17-extensions"
3522 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3523 typename _BinaryPredicate>
3524 _GLIBCXX20_CONSTEXPR
3526 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3527 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3528 _BinaryPredicate __pred)
3531 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3533 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3534 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3535 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3536 constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
3537 if constexpr (__ra_iters)
3539 if ((__last1 - __first1) != (__last2 - __first2))
3545 for (; __first1 != __last1 && __first2 != __last2;
3546 ++__first1, (void)++__first2)
3547 if (!__pred(__first1, __first2))
3550 if constexpr (__ra_iters)
3552 if (__first1 == __last1)
3559 if (__d1 == 0 && __d2 == 0)
3565 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3567 if (__scan != std::__find_if(__first1, __scan,
3568 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3571 auto __matches = std::__count_if(__first2, __last2,
3572 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3574 || std::__count_if(__scan, __last1,
3575 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3581#pragma GCC diagnostic pop
3596 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3597 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3599 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3600 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3602 __glibcxx_requires_valid_range(__first1, __last1);
3603 __glibcxx_requires_valid_range(__first2, __last2);
3606 std::__is_permutation(__first1, __last1, __first2, __last2,
3607 __gnu_cxx::__ops::__iter_equal_to_iter());
3624 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3625 typename _BinaryPredicate>
3626 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3628 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3629 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3630 _BinaryPredicate __pred)
3632 __glibcxx_requires_valid_range(__first1, __last1);
3633 __glibcxx_requires_valid_range(__first2, __last2);
3635 return std::__is_permutation(__first1, __last1, __first2, __last2,
3636 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3640#ifdef __glibcxx_clamp
3652 template<
typename _Tp>
3653 [[nodiscard]]
constexpr const _Tp&
3654 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3656 __glibcxx_assert(!(__hi < __lo));
3672 template<
typename _Tp,
typename _Compare>
3673 [[nodiscard]]
constexpr const _Tp&
3674 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3676 __glibcxx_assert(!__comp(__hi, __lo));
3702 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3705 _UniformRandomBitGenerator&& __g)
3724 template<
typename _RandomAccessIterator,
3725 typename _UniformRandomNumberGenerator>
3727 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3728 _UniformRandomNumberGenerator&& __g)
3731 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3732 _RandomAccessIterator>)
3733 __glibcxx_requires_valid_range(__first, __last);
3735 if (__first == __last)
3741 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3743 typedef typename __distr_type::param_type __p_type;
3745 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3750 const __uc_type __urngrange = __g.max() - __g.min();
3751 const __uc_type __urange = __uc_type(__last - __first);
3753 if (__urngrange / __urange >= __urange)
3756 _RandomAccessIterator __i = __first + 1;
3762 if ((__urange % 2) == 0)
3764 __distr_type __d{0, 1};
3765 std::iter_swap(__i++, __first + __d(__g));
3772 while (__i != __last)
3774 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3779 std::iter_swap(__i++, __first + __pospos.
first);
3780 std::iter_swap(__i++, __first + __pospos.
second);
3788 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3789 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3793_GLIBCXX_BEGIN_NAMESPACE_ALGO
3807 template<
typename _InputIterator,
typename _Function>
3808 _GLIBCXX20_CONSTEXPR
3810 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3813 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3814 __glibcxx_requires_valid_range(__first, __last);
3815 for (; __first != __last; ++__first)
3820#if __cplusplus >= 201703L
3833 template<
typename _InputIterator,
typename _Size,
typename _Function>
3834 _GLIBCXX20_CONSTEXPR
3838 auto __n2 = std::__size_to_integer(__n);
3840 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3845 auto __last = __first + __d;
3846 std::for_each(__first, __last,
std::move(__f));
3870 template<
typename _InputIterator,
typename _Tp>
3871 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3872 inline _InputIterator
3873 find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
3876 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3877 __glibcxx_function_requires(_EqualOpConcept<
3879 __glibcxx_requires_valid_range(__first, __last);
3881#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
3883 if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
3884 if constexpr (is_pointer_v<
decltype(std::__niter_base(__first))>
3885#
if __glibcxx_concepts && __glibcxx_to_address
3886 || contiguous_iterator<_InputIterator>
3894 if (!(
static_cast<_ValT
>(__val) == __val))
3896 else if (!__is_constant_evaluated())
3898 const int __ival =
static_cast<int>(__val);
3899 if (
auto __n = __last - __first; __n > 0)
3901#if __glibcxx_concepts && __glibcxx_to_address
3904 const void* __p0 = std::__niter_base(__first);
3906 if (
auto __p1 = __builtin_memchr(__p0, __ival, __n))
3907 return __first + ((
const char*)__p1 - (
const char*)__p0);
3914 return std::__find_if(__first, __last,
3915 __gnu_cxx::__ops::__iter_equals_val(__val));
3928 template<
typename _InputIterator,
typename _Predicate>
3929 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3930 inline _InputIterator
3931 find_if(_InputIterator __first, _InputIterator __last,
3935 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3936 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3938 __glibcxx_requires_valid_range(__first, __last);
3940 return std::__find_if(__first, __last,
3941 __gnu_cxx::__ops::__pred_iter(__pred));
3960 template<
typename _InputIterator,
typename _ForwardIterator>
3961 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3963 find_first_of(_InputIterator __first1, _InputIterator __last1,
3964 _ForwardIterator __first2, _ForwardIterator __last2)
3967 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3968 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3969 __glibcxx_function_requires(_EqualOpConcept<
3972 __glibcxx_requires_valid_range(__first1, __last1);
3973 __glibcxx_requires_valid_range(__first2, __last2);
3975 for (; __first1 != __last1; ++__first1)
3976 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3977 if (*__first1 == *__iter)
4001 template<
typename _InputIterator,
typename _ForwardIterator,
4002 typename _BinaryPredicate>
4003 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4005 find_first_of(_InputIterator __first1, _InputIterator __last1,
4006 _ForwardIterator __first2, _ForwardIterator __last2,
4007 _BinaryPredicate __comp)
4010 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4011 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4012 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4015 __glibcxx_requires_valid_range(__first1, __last1);
4016 __glibcxx_requires_valid_range(__first2, __last2);
4018 for (; __first1 != __last1; ++__first1)
4019 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4020 if (__comp(*__first1, *__iter))
4034 template<
typename _ForwardIterator>
4035 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4036 inline _ForwardIterator
4037 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4040 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4041 __glibcxx_function_requires(_EqualityComparableConcept<
4043 __glibcxx_requires_valid_range(__first, __last);
4045 return std::__adjacent_find(__first, __last,
4046 __gnu_cxx::__ops::__iter_equal_to_iter());
4060 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4061 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4062 inline _ForwardIterator
4063 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4064 _BinaryPredicate __binary_pred)
4067 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4068 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4071 __glibcxx_requires_valid_range(__first, __last);
4073 return std::__adjacent_find(__first, __last,
4074 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4086 template<
typename _InputIterator,
typename _Tp>
4087 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4088 inline typename iterator_traits<_InputIterator>::difference_type
4089 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4092 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4093 __glibcxx_function_requires(_EqualOpConcept<
4095 __glibcxx_requires_valid_range(__first, __last);
4097 return std::__count_if(__first, __last,
4098 __gnu_cxx::__ops::__iter_equals_val(__value));
4110 template<
typename _InputIterator,
typename _Predicate>
4111 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4112 inline typename iterator_traits<_InputIterator>::difference_type
4113 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4116 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4117 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4119 __glibcxx_requires_valid_range(__first, __last);
4121 return std::__count_if(__first, __last,
4122 __gnu_cxx::__ops::__pred_iter(__pred));
4151 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4152 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4153 inline _ForwardIterator1
4154 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4155 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4158 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4159 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4160 __glibcxx_function_requires(_EqualOpConcept<
4163 __glibcxx_requires_valid_range(__first1, __last1);
4164 __glibcxx_requires_valid_range(__first2, __last2);
4166 return std::__search(__first1, __last1, __first2, __last2,
4167 __gnu_cxx::__ops::__iter_equal_to_iter());
4185 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4186 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4187 inline _ForwardIterator
4188 search_n(_ForwardIterator __first, _ForwardIterator __last,
4189 _Integer __count,
const _Tp& __val)
4192 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4193 __glibcxx_function_requires(_EqualOpConcept<
4195 __glibcxx_requires_valid_range(__first, __last);
4197 return std::__search_n(__first, __last, __count,
4198 __gnu_cxx::__ops::__iter_equals_val(__val));
4219 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4220 typename _BinaryPredicate>
4221 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4222 inline _ForwardIterator
4223 search_n(_ForwardIterator __first, _ForwardIterator __last,
4224 _Integer __count,
const _Tp& __val,
4225 _BinaryPredicate __binary_pred)
4228 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4229 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4231 __glibcxx_requires_valid_range(__first, __last);
4233 return std::__search_n(__first, __last, __count,
4234 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4237#if __cplusplus >= 201703L
4245 template<
typename _ForwardIterator,
typename _Searcher>
4246 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4247 inline _ForwardIterator
4248 search(_ForwardIterator __first, _ForwardIterator __last,
4249 const _Searcher& __searcher)
4250 {
return __searcher(__first, __last).first; }
4269 template<
typename _InputIterator,
typename _OutputIterator,
4270 typename _UnaryOperation>
4271 _GLIBCXX20_CONSTEXPR
4273 transform(_InputIterator __first, _InputIterator __last,
4274 _OutputIterator __result, _UnaryOperation __unary_op)
4277 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4278 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4280 __typeof__(__unary_op(*__first))>)
4281 __glibcxx_requires_valid_range(__first, __last);
4283 for (; __first != __last; ++__first, (void)++__result)
4284 *__result = __unary_op(*__first);
4307 template<
typename _InputIterator1,
typename _InputIterator2,
4308 typename _OutputIterator,
typename _BinaryOperation>
4309 _GLIBCXX20_CONSTEXPR
4311 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4312 _InputIterator2 __first2, _OutputIterator __result,
4313 _BinaryOperation __binary_op)
4316 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4317 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4318 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4320 __typeof__(__binary_op(*__first1,*__first2))>)
4321 __glibcxx_requires_valid_range(__first1, __last1);
4323 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4324 *__result = __binary_op(*__first1, *__first2);
4341 template<
typename _ForwardIterator,
typename _Tp>
4342 _GLIBCXX20_CONSTEXPR
4344 replace(_ForwardIterator __first, _ForwardIterator __last,
4345 const _Tp& __old_value,
const _Tp& __new_value)
4348 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4350 __glibcxx_function_requires(_EqualOpConcept<
4352 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4354 __glibcxx_requires_valid_range(__first, __last);
4356 for (; __first != __last; ++__first)
4357 if (*__first == __old_value)
4358 *__first = __new_value;
4374 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4375 _GLIBCXX20_CONSTEXPR
4377 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4378 _Predicate __pred,
const _Tp& __new_value)
4381 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4383 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4385 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4387 __glibcxx_requires_valid_range(__first, __last);
4389 for (; __first != __last; ++__first)
4390 if (__pred(*__first))
4391 *__first = __new_value;
4406 template<
typename _ForwardIterator,
typename _Generator>
4407 _GLIBCXX20_CONSTEXPR
4409 generate(_ForwardIterator __first, _ForwardIterator __last,
4413 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4414 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4416 __glibcxx_requires_valid_range(__first, __last);
4418 for (; __first != __last; ++__first)
4439 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4440 _GLIBCXX20_CONSTEXPR
4442 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4445 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4447 __typeof__(__gen())>)
4449 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4450 for (_IntSize __niter = std::__size_to_integer(__n);
4451 __niter > 0; --__niter, (void) ++__first)
4474 template<
typename _InputIterator,
typename _OutputIterator>
4475 _GLIBCXX20_CONSTEXPR
4476 inline _OutputIterator
4477 unique_copy(_InputIterator __first, _InputIterator __last,
4478 _OutputIterator __result)
4481 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4482 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4484 __glibcxx_function_requires(_EqualityComparableConcept<
4486 __glibcxx_requires_valid_range(__first, __last);
4488 if (__first == __last)
4490 return std::__unique_copy(__first, __last, __result,
4491 __gnu_cxx::__ops::__iter_equal_to_iter(),
4513 template<
typename _InputIterator,
typename _OutputIterator,
4514 typename _BinaryPredicate>
4515 _GLIBCXX20_CONSTEXPR
4516 inline _OutputIterator
4517 unique_copy(_InputIterator __first, _InputIterator __last,
4518 _OutputIterator __result,
4519 _BinaryPredicate __binary_pred)
4522 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4523 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4525 __glibcxx_requires_valid_range(__first, __last);
4526 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4530 if (__first == __last)
4532 return std::__unique_copy(__first, __last, __result,
4533 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4537#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4554 template<
typename _RandomAccessIterator>
4555 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4557 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4560 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4561 _RandomAccessIterator>)
4562 __glibcxx_requires_valid_range(__first, __last);
4564 if (__first == __last)
4570#if RAND_MAX < __INT_MAX__
4571 if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
4576 = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
4577 for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last;
4581 __xss ^= __xss << 13;
4582 __xss ^= __xss >> 17;
4583 __xss ^= __xss << 5;
4584 _RandomAccessIterator __j
4585 = __first + _Dist(__xss % ((__i - __first) + 1));
4587 std::iter_swap(__i, __j);
4593 for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last; ++__i)
4596 _RandomAccessIterator __j
4597 = __first + _Dist(std::rand() % ((__i - __first) + 1));
4599 std::iter_swap(__i, __j);
4621 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4622 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4624 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4625#if __cplusplus >= 201103L
4626 _RandomNumberGenerator&& __rand)
4628 _RandomNumberGenerator& __rand)
4632 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4633 _RandomAccessIterator>)
4634 __glibcxx_requires_valid_range(__first, __last);
4636 if (__first == __last)
4642 for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last; ++__i)
4644 _RandomAccessIterator __j
4645 = __first + _Dist(__rand((__i - __first) + 1));
4647 std::iter_swap(__i, __j);
4668 template<
typename _ForwardIterator,
typename _Predicate>
4669 _GLIBCXX20_CONSTEXPR
4670 inline _ForwardIterator
4671 partition(_ForwardIterator __first, _ForwardIterator __last,
4675 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4677 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4679 __glibcxx_requires_valid_range(__first, __last);
4703 template<
typename _RandomAccessIterator>
4704 _GLIBCXX20_CONSTEXPR
4706 partial_sort(_RandomAccessIterator __first,
4707 _RandomAccessIterator __middle,
4708 _RandomAccessIterator __last)
4711 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4712 _RandomAccessIterator>)
4713 __glibcxx_function_requires(_LessThanComparableConcept<
4715 __glibcxx_requires_valid_range(__first, __middle);
4716 __glibcxx_requires_valid_range(__middle, __last);
4717 __glibcxx_requires_irreflexive(__first, __last);
4719 std::__partial_sort(__first, __middle, __last,
4720 __gnu_cxx::__ops::__iter_less_iter());
4742 template<
typename _RandomAccessIterator,
typename _Compare>
4743 _GLIBCXX20_CONSTEXPR
4745 partial_sort(_RandomAccessIterator __first,
4746 _RandomAccessIterator __middle,
4747 _RandomAccessIterator __last,
4751 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4752 _RandomAccessIterator>)
4753 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4756 __glibcxx_requires_valid_range(__first, __middle);
4757 __glibcxx_requires_valid_range(__middle, __last);
4758 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4760 std::__partial_sort(__first, __middle, __last,
4761 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4779 template<
typename _RandomAccessIterator>
4780 _GLIBCXX20_CONSTEXPR
4782 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4783 _RandomAccessIterator __last)
4786 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4787 _RandomAccessIterator>)
4788 __glibcxx_function_requires(_LessThanComparableConcept<
4790 __glibcxx_requires_valid_range(__first, __nth);
4791 __glibcxx_requires_valid_range(__nth, __last);
4792 __glibcxx_requires_irreflexive(__first, __last);
4794 if (__first == __last || __nth == __last)
4797 std::__introselect(__first, __nth, __last,
4799 __gnu_cxx::__ops::__iter_less_iter());
4819 template<
typename _RandomAccessIterator,
typename _Compare>
4820 _GLIBCXX20_CONSTEXPR
4822 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4823 _RandomAccessIterator __last, _Compare __comp)
4826 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4827 _RandomAccessIterator>)
4828 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4831 __glibcxx_requires_valid_range(__first, __nth);
4832 __glibcxx_requires_valid_range(__nth, __last);
4833 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4835 if (__first == __last || __nth == __last)
4838 std::__introselect(__first, __nth, __last,
4840 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4857 template<
typename _RandomAccessIterator>
4858 _GLIBCXX20_CONSTEXPR
4860 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4863 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4864 _RandomAccessIterator>)
4865 __glibcxx_function_requires(_LessThanComparableConcept<
4867 __glibcxx_requires_valid_range(__first, __last);
4868 __glibcxx_requires_irreflexive(__first, __last);
4870 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4888 template<
typename _RandomAccessIterator,
typename _Compare>
4889 _GLIBCXX20_CONSTEXPR
4891 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4895 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4896 _RandomAccessIterator>)
4897 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4900 __glibcxx_requires_valid_range(__first, __last);
4901 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4903 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4906 template<
typename _InputIterator1,
typename _InputIterator2,
4907 typename _OutputIterator,
typename _Compare>
4908 _GLIBCXX20_CONSTEXPR
4910 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4911 _InputIterator2 __first2, _InputIterator2 __last2,
4912 _OutputIterator __result, _Compare __comp)
4914 while (__first1 != __last1 && __first2 != __last2)
4916 if (__comp(__first2, __first1))
4918 *__result = *__first2;
4923 *__result = *__first1;
4928 return std::copy(__first2, __last2,
4929 std::copy(__first1, __last1, __result));
4951 template<
typename _InputIterator1,
typename _InputIterator2,
4952 typename _OutputIterator>
4953 _GLIBCXX20_CONSTEXPR
4954 inline _OutputIterator
4955 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4956 _InputIterator2 __first2, _InputIterator2 __last2,
4957 _OutputIterator __result)
4960 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4961 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4962 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4964 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4966 __glibcxx_function_requires(_LessThanOpConcept<
4969 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4970 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4971 __glibcxx_requires_irreflexive2(__first1, __last1);
4972 __glibcxx_requires_irreflexive2(__first2, __last2);
4974 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4975 __first2, __last2, __result,
4976 __gnu_cxx::__ops::__iter_less_iter());
5002 template<
typename _InputIterator1,
typename _InputIterator2,
5003 typename _OutputIterator,
typename _Compare>
5004 _GLIBCXX20_CONSTEXPR
5005 inline _OutputIterator
5006 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5007 _InputIterator2 __first2, _InputIterator2 __last2,
5008 _OutputIterator __result, _Compare __comp)
5011 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5012 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5013 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5015 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5017 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5020 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5021 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5022 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5023 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5025 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5026 __first2, __last2, __result,
5027 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5030 template<
typename _RandomAccessIterator,
typename _Compare>
5031 _GLIBCXX26_CONSTEXPR
5033 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5036 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5038 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5041 if (__first == __last)
5045# if __glibcxx_constexpr_algorithms >= 202306L
5054 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
5056 if (__builtin_expect(__buf._M_requested_size() == __buf.size(),
true))
5057 std::__stable_sort_adaptive(__first,
5058 __first + _DistanceType(__buf.size()),
5059 __last, __buf.begin(), __comp);
5060 else if (__builtin_expect(__buf.begin() == 0,
false))
5063 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
5064 _DistanceType(__buf.size()), __comp);
5087 template<
typename _RandomAccessIterator>
5088 _GLIBCXX26_CONSTEXPR
5090 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5093 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5094 _RandomAccessIterator>)
5095 __glibcxx_function_requires(_LessThanComparableConcept<
5097 __glibcxx_requires_valid_range(__first, __last);
5098 __glibcxx_requires_irreflexive(__first, __last);
5100 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5101 __gnu_cxx::__ops::__iter_less_iter());
5122 template<
typename _RandomAccessIterator,
typename _Compare>
5123 _GLIBCXX26_CONSTEXPR
5125 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5129 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5130 _RandomAccessIterator>)
5131 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5134 __glibcxx_requires_valid_range(__first, __last);
5135 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5137 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5138 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5141 template<
typename _InputIterator1,
typename _InputIterator2,
5142 typename _OutputIterator,
5144 _GLIBCXX20_CONSTEXPR
5146 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5147 _InputIterator2 __first2, _InputIterator2 __last2,
5148 _OutputIterator __result, _Compare __comp)
5150 while (__first1 != __last1 && __first2 != __last2)
5152 if (__comp(__first1, __first2))
5154 *__result = *__first1;
5157 else if (__comp(__first2, __first1))
5159 *__result = *__first2;
5164 *__result = *__first1;
5170 return std::copy(__first2, __last2,
5171 std::copy(__first1, __last1, __result));
5193 template<
typename _InputIterator1,
typename _InputIterator2,
5194 typename _OutputIterator>
5195 _GLIBCXX20_CONSTEXPR
5196 inline _OutputIterator
5197 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5198 _InputIterator2 __first2, _InputIterator2 __last2,
5199 _OutputIterator __result)
5202 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5203 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5204 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5206 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5208 __glibcxx_function_requires(_LessThanOpConcept<
5211 __glibcxx_function_requires(_LessThanOpConcept<
5214 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5215 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5216 __glibcxx_requires_irreflexive2(__first1, __last1);
5217 __glibcxx_requires_irreflexive2(__first2, __last2);
5219 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5220 __first2, __last2, __result,
5221 __gnu_cxx::__ops::__iter_less_iter());
5244 template<
typename _InputIterator1,
typename _InputIterator2,
5245 typename _OutputIterator,
typename _Compare>
5246 _GLIBCXX20_CONSTEXPR
5247 inline _OutputIterator
5248 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5249 _InputIterator2 __first2, _InputIterator2 __last2,
5250 _OutputIterator __result, _Compare __comp)
5253 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5254 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5255 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5257 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5259 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5262 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5265 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5266 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5267 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5268 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5270 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5271 __first2, __last2, __result,
5272 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5275 template<
typename _InputIterator1,
typename _InputIterator2,
5276 typename _OutputIterator,
5278 _GLIBCXX20_CONSTEXPR
5280 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5281 _InputIterator2 __first2, _InputIterator2 __last2,
5282 _OutputIterator __result, _Compare __comp)
5284 while (__first1 != __last1 && __first2 != __last2)
5285 if (__comp(__first1, __first2))
5287 else if (__comp(__first2, __first1))
5291 *__result = *__first1;
5317 template<
typename _InputIterator1,
typename _InputIterator2,
5318 typename _OutputIterator>
5319 _GLIBCXX20_CONSTEXPR
5320 inline _OutputIterator
5321 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5322 _InputIterator2 __first2, _InputIterator2 __last2,
5323 _OutputIterator __result)
5326 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5327 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5328 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5330 __glibcxx_function_requires(_LessThanOpConcept<
5333 __glibcxx_function_requires(_LessThanOpConcept<
5336 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5337 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5338 __glibcxx_requires_irreflexive2(__first1, __last1);
5339 __glibcxx_requires_irreflexive2(__first2, __last2);
5341 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5342 __first2, __last2, __result,
5343 __gnu_cxx::__ops::__iter_less_iter());
5367 template<
typename _InputIterator1,
typename _InputIterator2,
5368 typename _OutputIterator,
typename _Compare>
5369 _GLIBCXX20_CONSTEXPR
5370 inline _OutputIterator
5371 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5372 _InputIterator2 __first2, _InputIterator2 __last2,
5373 _OutputIterator __result, _Compare __comp)
5376 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5377 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5378 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5380 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5383 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5386 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5387 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5388 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5389 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5391 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5392 __first2, __last2, __result,
5393 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5396 template<
typename _InputIterator1,
typename _InputIterator2,
5397 typename _OutputIterator,
5399 _GLIBCXX20_CONSTEXPR
5401 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5402 _InputIterator2 __first2, _InputIterator2 __last2,
5403 _OutputIterator __result, _Compare __comp)
5405 while (__first1 != __last1 && __first2 != __last2)
5406 if (__comp(__first1, __first2))
5408 *__result = *__first1;
5412 else if (__comp(__first2, __first1))
5419 return std::copy(__first1, __last1, __result);
5442 template<
typename _InputIterator1,
typename _InputIterator2,
5443 typename _OutputIterator>
5444 _GLIBCXX20_CONSTEXPR
5445 inline _OutputIterator
5446 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5447 _InputIterator2 __first2, _InputIterator2 __last2,
5448 _OutputIterator __result)
5451 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5452 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5453 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5455 __glibcxx_function_requires(_LessThanOpConcept<
5458 __glibcxx_function_requires(_LessThanOpConcept<
5461 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5462 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5463 __glibcxx_requires_irreflexive2(__first1, __last1);
5464 __glibcxx_requires_irreflexive2(__first2, __last2);
5466 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5467 __first2, __last2, __result,
5468 __gnu_cxx::__ops::__iter_less_iter());
5494 template<
typename _InputIterator1,
typename _InputIterator2,
5495 typename _OutputIterator,
typename _Compare>
5496 _GLIBCXX20_CONSTEXPR
5497 inline _OutputIterator
5498 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5499 _InputIterator2 __first2, _InputIterator2 __last2,
5500 _OutputIterator __result, _Compare __comp)
5503 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5504 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5505 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5507 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5510 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5513 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5514 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5515 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5516 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5518 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5519 __first2, __last2, __result,
5520 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5523 template<
typename _InputIterator1,
typename _InputIterator2,
5524 typename _OutputIterator,
5526 _GLIBCXX20_CONSTEXPR
5528 __set_symmetric_difference(_InputIterator1 __first1,
5529 _InputIterator1 __last1,
5530 _InputIterator2 __first2,
5531 _InputIterator2 __last2,
5532 _OutputIterator __result,
5535 while (__first1 != __last1 && __first2 != __last2)
5536 if (__comp(__first1, __first2))
5538 *__result = *__first1;
5542 else if (__comp(__first2, __first1))
5544 *__result = *__first2;
5553 return std::copy(__first2, __last2,
5554 std::copy(__first1, __last1, __result));
5575 template<
typename _InputIterator1,
typename _InputIterator2,
5576 typename _OutputIterator>
5577 _GLIBCXX20_CONSTEXPR
5578 inline _OutputIterator
5579 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5580 _InputIterator2 __first2, _InputIterator2 __last2,
5581 _OutputIterator __result)
5584 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5585 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5586 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5588 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5590 __glibcxx_function_requires(_LessThanOpConcept<
5593 __glibcxx_function_requires(_LessThanOpConcept<
5596 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5597 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5598 __glibcxx_requires_irreflexive2(__first1, __last1);
5599 __glibcxx_requires_irreflexive2(__first2, __last2);
5601 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5602 __first2, __last2, __result,
5603 __gnu_cxx::__ops::__iter_less_iter());
5627 template<
typename _InputIterator1,
typename _InputIterator2,
5628 typename _OutputIterator,
typename _Compare>
5629 _GLIBCXX20_CONSTEXPR
5630 inline _OutputIterator
5631 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5632 _InputIterator2 __first2, _InputIterator2 __last2,
5633 _OutputIterator __result,
5637 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5638 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5639 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5641 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5643 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5646 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5649 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5650 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5651 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5652 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5654 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5655 __first2, __last2, __result,
5656 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5659 template<
typename _ForwardIterator,
typename _Compare>
5660 _GLIBCXX14_CONSTEXPR
5662 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5665 if (__first == __last)
5667 _ForwardIterator __result = __first;
5668 while (++__first != __last)
5669 if (__comp(__first, __result))
5681 template<
typename _ForwardIterator>
5682 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5684 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5687 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5688 __glibcxx_function_requires(_LessThanComparableConcept<
5690 __glibcxx_requires_valid_range(__first, __last);
5691 __glibcxx_requires_irreflexive(__first, __last);
5693 return _GLIBCXX_STD_A::__min_element(__first, __last,
5694 __gnu_cxx::__ops::__iter_less_iter());
5706 template<
typename _ForwardIterator,
typename _Compare>
5707 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5708 inline _ForwardIterator
5709 min_element(_ForwardIterator __first, _ForwardIterator __last,
5713 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5714 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5717 __glibcxx_requires_valid_range(__first, __last);
5718 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5720 return _GLIBCXX_STD_A::__min_element(__first, __last,
5721 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5724 template<
typename _ForwardIterator,
typename _Compare>
5725 _GLIBCXX14_CONSTEXPR
5727 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5730 if (__first == __last)
return __first;
5731 _ForwardIterator __result = __first;
5732 while (++__first != __last)
5733 if (__comp(__result, __first))
5745 template<
typename _ForwardIterator>
5746 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5747 inline _ForwardIterator
5748 max_element(_ForwardIterator __first, _ForwardIterator __last)
5751 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5752 __glibcxx_function_requires(_LessThanComparableConcept<
5754 __glibcxx_requires_valid_range(__first, __last);
5755 __glibcxx_requires_irreflexive(__first, __last);
5757 return _GLIBCXX_STD_A::__max_element(__first, __last,
5758 __gnu_cxx::__ops::__iter_less_iter());
5770 template<
typename _ForwardIterator,
typename _Compare>
5771 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5772 inline _ForwardIterator
5773 max_element(_ForwardIterator __first, _ForwardIterator __last,
5777 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5778 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5781 __glibcxx_requires_valid_range(__first, __last);
5782 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5784 return _GLIBCXX_STD_A::__max_element(__first, __last,
5785 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5788#if __cplusplus >= 201103L
5790 template<
typename _Tp>
5791 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5793 min(initializer_list<_Tp> __l)
5795 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5796 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5797 __gnu_cxx::__ops::__iter_less_iter());
5800 template<
typename _Tp,
typename _Compare>
5801 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5805 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5806 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5807 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5810 template<
typename _Tp>
5811 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5815 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5816 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5817 __gnu_cxx::__ops::__iter_less_iter());
5820 template<
typename _Tp,
typename _Compare>
5821 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5825 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5826 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5827 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5831#if __cplusplus >= 201402L
5833 template<
typename _InputIterator,
typename _RandomAccessIterator,
5834 typename _Size,
typename _UniformRandomBitGenerator>
5835 _RandomAccessIterator
5838 _Size __n, _UniformRandomBitGenerator&& __g)
5841 using __param_type =
typename __distrib_type::param_type;
5842 __distrib_type __d{};
5843 _Size __sample_sz = 0;
5844 while (__first != __last && __sample_sz != __n)
5846 __out[__sample_sz++] = *__first;
5849 for (
auto __pop_sz = __sample_sz; __first != __last;
5850 ++__first, (void) ++__pop_sz)
5852 const auto __k = __d(__g, __param_type{0, __pop_sz});
5854 __out[__k] = *__first;
5856 return __out + __sample_sz;
5860 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5861 typename _Size,
typename _UniformRandomBitGenerator>
5863 __sample(_ForwardIterator __first, _ForwardIterator __last,
5865 _OutputIterator __out, _Cat,
5866 _Size __n, _UniformRandomBitGenerator&& __g)
5869 using __param_type =
typename __distrib_type::param_type;
5874 if (__first == __last)
5877 __distrib_type __d{};
5879 __n =
std::min(__n, __unsampled_sz);
5884 const __uc_type __urngrange = __g.max() - __g.min();
5885 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5889 while (__n != 0 && __unsampled_sz >= 2)
5895 if (__p.
first < __n)
5897 *__out++ = *__first;
5903 if (__n == 0)
break;
5908 *__out++ = *__first;
5918 for (; __n != 0; ++__first)
5919 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5921 *__out++ = *__first;
5928#ifdef __glibcxx_sample
5930 template<typename _PopulationIterator, typename _SampleIterator,
5931 typename _Distance,
typename _UniformRandomBitGenerator>
5933 sample(_PopulationIterator __first, _PopulationIterator __last,
5934 _SampleIterator __out, _Distance __n,
5935 _UniformRandomBitGenerator&& __g)
5937 using __pop_cat =
typename
5939 using __samp_cat =
typename
5943 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5944 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5945 "output range must use a RandomAccessIterator when input range"
5946 " does not meet the ForwardIterator requirements");
5949 "sample size must be an integer type");
5952 return _GLIBCXX_STD_A::
5953 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5958_GLIBCXX_END_NAMESPACE_ALGO
5959_GLIBCXX_END_NAMESPACE_VERSION
5962#pragma GCC diagnostic pop
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Compare __comp)
This is a helper function for the merge routines.
constexpr _InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
constexpr _Tp __lg(_Tp __n)
This is a helper function for the sort routines and for random.tcc.
constexpr _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
constexpr _ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
constexpr void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)
Take a random sample from a population.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
constexpr void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
constexpr _ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
constexpr _InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
constexpr iterator_type base() const noexcept(/*conditional */)
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
Forward iterators support a superset of input iterator operations.
Bidirectional iterators support a superset of forward iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Traits class for iterators.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...