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 - __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,
239 forward_iterator_tag, forward_iterator_tag,
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,
270 bidirectional_iterator_tag, bidirectional_iterator_tag,
271 _BinaryPredicate __comp)
274 __glibcxx_function_requires(_BidirectionalIteratorConcept<
275 _BidirectionalIterator1>)
276 __glibcxx_function_requires(_BidirectionalIteratorConcept<
277 _BidirectionalIterator2>)
279 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
280 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
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>
721 pair<_OutputIterator1, _OutputIterator2>
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));
927 template<
typename _ForwardIterator,
typename _OutputIterator,
928 typename _BinaryPredicate>
932 _OutputIterator __result, _BinaryPredicate __binary_pred,
936 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
940 _ForwardIterator __next = __first;
941 *__result = *__first;
942 while (++__next != __last)
943 if (!__binary_pred(__first, __next))
946 *++__result = *__first;
957 template<
typename _InputIterator,
typename _OutputIterator,
958 typename _BinaryPredicate>
962 _OutputIterator __result, _BinaryPredicate __binary_pred,
966 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
971 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
973 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
975 while (++__first != __last)
976 if (!__rebound_pred(__first, __value))
979 *++__result = __value;
990 template<
typename _InputIterator,
typename _ForwardIterator,
991 typename _BinaryPredicate>
995 _ForwardIterator __result, _BinaryPredicate __binary_pred,
999 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1002 *__result = *__first;
1003 while (++__first != __last)
1004 if (!__binary_pred(__result, __first))
1005 *++__result = *__first;
1014 template<
typename _B
idirectionalIterator>
1015 _GLIBCXX20_CONSTEXPR
1017 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1021 if (__first == __last || __first == --__last)
1025 std::iter_swap(__first, __last);
1035 template<
typename _RandomAccessIterator>
1036 _GLIBCXX20_CONSTEXPR
1038 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1041 if (__first == __last)
1044 while (__first < __last)
1046 std::iter_swap(__first, __last);
1064 template<
typename _B
idirectionalIterator>
1065 _GLIBCXX20_CONSTEXPR
1067 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1070 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1071 _BidirectionalIterator>)
1072 __glibcxx_requires_valid_range(__first, __last);
1092 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1093 _GLIBCXX20_CONSTEXPR
1095 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1096 _OutputIterator __result)
1099 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1100 _BidirectionalIterator>)
1101 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1103 __glibcxx_requires_valid_range(__first, __last);
1105 while (__first != __last)
1108 *__result = *__last;
1118 template<
typename _Eucl
ideanRingElement>
1119 _GLIBCXX20_CONSTEXPR
1120 _EuclideanRingElement
1121 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1125 _EuclideanRingElement __t = __m % __n;
1132_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1135 template<
typename _ForwardIterator>
1136 _GLIBCXX20_CONSTEXPR
1139 _ForwardIterator __middle,
1140 _ForwardIterator __last,
1143 if (__first == __middle)
1145 else if (__last == __middle)
1148 _ForwardIterator __first2 = __middle;
1151 std::iter_swap(__first, __first2);
1154 if (__first == __middle)
1155 __middle = __first2;
1157 while (__first2 != __last);
1159 _ForwardIterator __ret = __first;
1161 __first2 = __middle;
1163 while (__first2 != __last)
1165 std::iter_swap(__first, __first2);
1168 if (__first == __middle)
1169 __middle = __first2;
1170 else if (__first2 == __last)
1171 __first2 = __middle;
1177 template<
typename _B
idirectionalIterator>
1178 _GLIBCXX20_CONSTEXPR
1179 _BidirectionalIterator
1181 _BidirectionalIterator __middle,
1182 _BidirectionalIterator __last,
1186 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1187 _BidirectionalIterator>)
1189 if (__first == __middle)
1191 else if (__last == __middle)
1197 while (__first != __middle && __middle != __last)
1199 std::iter_swap(__first, --__last);
1203 if (__first == __middle)
1216 template<
typename _RandomAccessIterator>
1217 _GLIBCXX20_CONSTEXPR
1218 _RandomAccessIterator
1220 _RandomAccessIterator __middle,
1221 _RandomAccessIterator __last,
1225 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1226 _RandomAccessIterator>)
1228 if (__first == __middle)
1230 else if (__last == __middle)
1238#if __cplusplus >= 201103L
1239 typedef typename make_unsigned<_Distance>::type _UDistance;
1241 typedef _Distance _UDistance;
1244 _Distance __n = __last - __first;
1245 _Distance __k = __middle - __first;
1247 if (__k == __n - __k)
1249 std::swap_ranges(__first, __middle, __middle);
1253 _RandomAccessIterator __p = __first;
1254 _RandomAccessIterator __ret = __first + (__last - __middle);
1258 if (__k < __n - __k)
1260 if (__is_pod(_ValueType) && __k == 1)
1262 _ValueType __t = _GLIBCXX_MOVE(*__p);
1263 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1264 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1267 _RandomAccessIterator __q = __p + __k;
1268 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1270 std::iter_swap(__p, __q);
1274 __n =
static_cast<_UDistance
>(__n) %
static_cast<_UDistance
>(__k);
1277 std::swap(__n, __k);
1283 if (__is_pod(_ValueType) && __k == 1)
1285 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1286 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1287 *__p = _GLIBCXX_MOVE(__t);
1290 _RandomAccessIterator __q = __p + __n;
1292 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1296 std::iter_swap(__p, __q);
1298 __n =
static_cast<_UDistance
>(__n) %
static_cast<_UDistance
>(__k);
1301 std::swap(__n, __k);
1329 template<
typename _ForwardIterator>
1330 _GLIBCXX20_CONSTEXPR
1331 inline _ForwardIterator
1332 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1333 _ForwardIterator __last)
1336 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1338 __glibcxx_requires_valid_range(__first, __middle);
1339 __glibcxx_requires_valid_range(__middle, __last);
1345_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1367 template<
typename _ForwardIterator,
typename _OutputIterator>
1368 _GLIBCXX20_CONSTEXPR
1369 inline _OutputIterator
1370 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1371 _ForwardIterator __last, _OutputIterator __result)
1374 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1375 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1377 __glibcxx_requires_valid_range(__first, __middle);
1378 __glibcxx_requires_valid_range(__middle, __last);
1380 return std::copy(__first, __middle,
1381 std::copy(__middle, __last, __result));
1385 template<
typename _ForwardIterator,
typename _Predicate>
1386 _GLIBCXX20_CONSTEXPR
1391 if (__first == __last)
1394 while (__pred(*__first))
1395 if (++__first == __last)
1398 _ForwardIterator __next = __first;
1400 while (++__next != __last)
1401 if (__pred(*__next))
1403 std::iter_swap(__first, __next);
1411 template<
typename _B
idirectionalIterator,
typename _Predicate>
1412 _GLIBCXX20_CONSTEXPR
1413 _BidirectionalIterator
1414 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1420 if (__first == __last)
1422 else if (__pred(*__first))
1428 if (__first == __last)
1430 else if (!
bool(__pred(*__last)))
1434 std::iter_swap(__first, __last);
1448 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1450 _GLIBCXX26_CONSTEXPR
1453 _ForwardIterator __last,
1454 _Predicate __pred, _Distance __len,
1456 _Distance __buffer_size)
1461 if (__len <= __buffer_size)
1463 _ForwardIterator __result1 = __first;
1464 _Pointer __result2 = __buffer;
1469 *__result2 = _GLIBCXX_MOVE(*__first);
1472 for (; __first != __last; ++__first)
1473 if (__pred(__first))
1475 *__result1 = _GLIBCXX_MOVE(*__first);
1480 *__result2 = _GLIBCXX_MOVE(*__first);
1484 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1488 _ForwardIterator __middle = __first;
1490 _ForwardIterator __left_split =
1492 __len / 2, __buffer,
1497 _Distance __right_len = __len - __len / 2;
1498 _ForwardIterator __right_split =
1505 __buffer, __buffer_size);
1507 return std::rotate(__left_split, __middle, __right_split);
1510 template<
typename _ForwardIterator,
typename _Predicate>
1511 _GLIBCXX26_CONSTEXPR
1513 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1518 if (__first == __last)
1521 typedef typename iterator_traits<_ForwardIterator>::value_type
1523 typedef typename iterator_traits<_ForwardIterator>::difference_type
1528#if __glibcxx_constexpr_algorithms >= 202306L
1540 _Temporary_buffer<_ForwardIterator, _ValueType>
1541 __buf(__first, __len);
1546 _DistanceType(__buf.size()));
1566 template<
typename _ForwardIterator,
typename _Predicate>
1567 _GLIBCXX26_CONSTEXPR
1568 inline _ForwardIterator
1569 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1573 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1575 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1577 __glibcxx_requires_valid_range(__first, __last);
1579 return std::__stable_partition(__first, __last,
1580 __gnu_cxx::__ops::__pred_iter(__pred));
1587 template<
typename _RandomAccessIterator,
typename _Compare>
1588 _GLIBCXX20_CONSTEXPR
1590 __heap_select(_RandomAccessIterator __first,
1591 _RandomAccessIterator __middle,
1592 _RandomAccessIterator __last, _Compare __comp)
1594 std::__make_heap(__first, __middle, __comp);
1595 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1596 if (__comp(__i, __first))
1597 std::__pop_heap(__first, __middle, __i, __comp);
1602 template<
typename _InputIterator,
typename _RandomAccessIterator,
1604 _GLIBCXX20_CONSTEXPR
1605 _RandomAccessIterator
1606 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1607 _RandomAccessIterator __result_first,
1608 _RandomAccessIterator __result_last,
1611 typedef typename iterator_traits<_InputIterator>::value_type
1613 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1614 typedef typename _RItTraits::difference_type _DistanceType;
1616 if (__result_first == __result_last)
1617 return __result_last;
1618 _RandomAccessIterator __result_real_last = __result_first;
1619 while (__first != __last && __result_real_last != __result_last)
1621 *__result_real_last = *__first;
1622 ++__result_real_last;
1626 std::__make_heap(__result_first, __result_real_last, __comp);
1627 while (__first != __last)
1629 if (__comp(__first, __result_first))
1630 std::__adjust_heap(__result_first, _DistanceType(0),
1631 _DistanceType(__result_real_last
1633 _InputValueType(*__first), __comp);
1636 std::__sort_heap(__result_first, __result_real_last, __comp);
1637 return __result_real_last;
1660 template<
typename _InputIterator,
typename _RandomAccessIterator>
1661 _GLIBCXX20_CONSTEXPR
1662 inline _RandomAccessIterator
1663 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1664 _RandomAccessIterator __result_first,
1665 _RandomAccessIterator __result_last)
1667#ifdef _GLIBCXX_CONCEPT_CHECKS
1675 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1676 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1678 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1680 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1681 __glibcxx_requires_valid_range(__first, __last);
1682 __glibcxx_requires_irreflexive(__first, __last);
1683 __glibcxx_requires_valid_range(__result_first, __result_last);
1685 return std::__partial_sort_copy(__first, __last,
1686 __result_first, __result_last,
1687 __gnu_cxx::__ops::__iter_less_iter());
1710 template<
typename _InputIterator,
typename _RandomAccessIterator,
1712 _GLIBCXX20_CONSTEXPR
1713 inline _RandomAccessIterator
1714 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1715 _RandomAccessIterator __result_first,
1716 _RandomAccessIterator __result_last,
1719#ifdef _GLIBCXX_CONCEPT_CHECKS
1727 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1728 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1729 _RandomAccessIterator>)
1730 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1732 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1733 _InputValueType, _OutputValueType>)
1734 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1735 _OutputValueType, _OutputValueType>)
1736 __glibcxx_requires_valid_range(__first, __last);
1737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1738 __glibcxx_requires_valid_range(__result_first, __result_last);
1740 return std::__partial_sort_copy(__first, __last,
1741 __result_first, __result_last,
1742 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1748 template<
typename _RandomAccessIterator,
typename _Compare>
1749 _GLIBCXX20_CONSTEXPR
1751 __unguarded_linear_insert(_RandomAccessIterator __last,
1754 typename iterator_traits<_RandomAccessIterator>::value_type
1755 __val = _GLIBCXX_MOVE(*__last);
1756 _RandomAccessIterator __next = __last;
1758 while (__comp(__val, __next))
1760 *__last = _GLIBCXX_MOVE(*__next);
1764 *__last = _GLIBCXX_MOVE(__val);
1768 template<
typename _RandomAccessIterator,
typename _Compare>
1769 _GLIBCXX20_CONSTEXPR
1771 __insertion_sort(_RandomAccessIterator __first,
1772 _RandomAccessIterator __last, _Compare __comp)
1774 if (__first == __last)
return;
1776 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1778 if (__comp(__i, __first))
1780 typename iterator_traits<_RandomAccessIterator>::value_type
1781 __val = _GLIBCXX_MOVE(*__i);
1782 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1783 *__first = _GLIBCXX_MOVE(__val);
1786 std::__unguarded_linear_insert(__i,
1787 __gnu_cxx::__ops::__val_comp_iter(__comp));
1792 template<
typename _RandomAccessIterator,
typename _Compare>
1793 _GLIBCXX20_CONSTEXPR
1795 __unguarded_insertion_sort(_RandomAccessIterator __first,
1796 _RandomAccessIterator __last, _Compare __comp)
1798 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1799 std::__unguarded_linear_insert(__i,
1800 __gnu_cxx::__ops::__val_comp_iter(__comp));
1807 enum { _S_threshold = 16 };
1810 template<
typename _RandomAccessIterator,
typename _Compare>
1811 _GLIBCXX20_CONSTEXPR
1813 __final_insertion_sort(_RandomAccessIterator __first,
1814 _RandomAccessIterator __last, _Compare __comp)
1816 if (__last - __first >
int(_S_threshold))
1818 std::__insertion_sort(__first, __first +
int(_S_threshold), __comp);
1819 std::__unguarded_insertion_sort(__first +
int(_S_threshold), __last,
1823 std::__insertion_sort(__first, __last, __comp);
1827 template<
typename _RandomAccessIterator,
typename _Compare>
1828 _GLIBCXX20_CONSTEXPR
1829 _RandomAccessIterator
1830 __unguarded_partition(_RandomAccessIterator __first,
1831 _RandomAccessIterator __last,
1832 _RandomAccessIterator __pivot, _Compare __comp)
1836 while (__comp(__first, __pivot))
1839 while (__comp(__pivot, __last))
1841 if (!(__first < __last))
1843 std::iter_swap(__first, __last);
1849 template<
typename _RandomAccessIterator,
typename _Compare>
1850 _GLIBCXX20_CONSTEXPR
1851 inline _RandomAccessIterator
1852 __unguarded_partition_pivot(_RandomAccessIterator __first,
1853 _RandomAccessIterator __last, _Compare __comp)
1855 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1858 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1861 template<
typename _RandomAccessIterator,
typename _Compare>
1862 _GLIBCXX20_CONSTEXPR
1864 __partial_sort(_RandomAccessIterator __first,
1865 _RandomAccessIterator __middle,
1866 _RandomAccessIterator __last,
1869 std::__heap_select(__first, __middle, __last, __comp);
1870 std::__sort_heap(__first, __middle, __comp);
1874 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1875 _GLIBCXX20_CONSTEXPR
1877 __introsort_loop(_RandomAccessIterator __first,
1878 _RandomAccessIterator __last,
1879 _Size __depth_limit, _Compare __comp)
1881 while (__last - __first >
int(_S_threshold))
1883 if (__depth_limit == 0)
1885 std::__partial_sort(__first, __last, __last, __comp);
1889 _RandomAccessIterator __cut =
1890 std::__unguarded_partition_pivot(__first, __last, __comp);
1891 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1898 template<
typename _RandomAccessIterator,
typename _Compare>
1899 _GLIBCXX20_CONSTEXPR
1901 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1904 if (__first != __last)
1906 std::__introsort_loop(__first, __last,
1909 std::__final_insertion_sort(__first, __last, __comp);
1913 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1914 _GLIBCXX20_CONSTEXPR
1916 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1917 _RandomAccessIterator __last, _Size __depth_limit,
1920 while (__last - __first > 3)
1922 if (__depth_limit == 0)
1924 std::__heap_select(__first, __nth + 1, __last, __comp);
1926 std::iter_swap(__first, __nth);
1930 _RandomAccessIterator __cut =
1931 std::__unguarded_partition_pivot(__first, __last, __comp);
1937 std::__insertion_sort(__first, __last, __comp);
1961 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1962 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1963 inline _ForwardIterator
1964 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1965 const _Tp& __val, _Compare __comp)
1968 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1969 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1971 __glibcxx_requires_partitioned_lower_pred(__first, __last,
1974 return std::__lower_bound(__first, __last, __val,
1975 __gnu_cxx::__ops::__iter_comp_val(__comp));
1978 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1979 _GLIBCXX20_CONSTEXPR
1981 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
1982 const _Tp& __val, _Compare __comp)
1984 typedef typename iterator_traits<_ForwardIterator>::difference_type
1991 _DistanceType __half = __len >> 1;
1992 _ForwardIterator __middle = __first;
1994 if (__comp(__val, __middle))
2000 __len = __len - __half - 1;
2017 template<
typename _ForwardIterator,
typename _Tp>
2018 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2019 inline _ForwardIterator
2020 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2024 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2025 __glibcxx_function_requires(_LessThanOpConcept<
2027 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2029 return std::__upper_bound(__first, __last, __val,
2030 __gnu_cxx::__ops::__val_less_iter());
2048 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2049 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2050 inline _ForwardIterator
2051 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2052 const _Tp& __val, _Compare __comp)
2055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2056 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2058 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2061 return std::__upper_bound(__first, __last, __val,
2062 __gnu_cxx::__ops::__val_comp_iter(__comp));
2065 template<
typename _ForwardIterator,
typename _Tp,
2066 typename _CompareItTp,
typename _CompareTpIt>
2067 _GLIBCXX20_CONSTEXPR
2068 pair<_ForwardIterator, _ForwardIterator>
2069 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2071 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2073 typedef typename iterator_traits<_ForwardIterator>::difference_type
2080 _DistanceType __half = __len >> 1;
2081 _ForwardIterator __middle = __first;
2083 if (__comp_it_val(__middle, __val))
2087 __len = __len - __half - 1;
2089 else if (__comp_val_it(__val, __middle))
2093 _ForwardIterator __left
2094 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2096 _ForwardIterator __right
2097 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2098 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2101 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2121 template<
typename _ForwardIterator,
typename _Tp>
2122 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2123 inline pair<_ForwardIterator, _ForwardIterator>
2124 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2128 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2129 __glibcxx_function_requires(_LessThanOpConcept<
2131 __glibcxx_function_requires(_LessThanOpConcept<
2133 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2134 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2136 return std::__equal_range(__first, __last, __val,
2137 __gnu_cxx::__ops::__iter_less_val(),
2138 __gnu_cxx::__ops::__val_less_iter());
2158 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2159 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2160 inline pair<_ForwardIterator, _ForwardIterator>
2161 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2162 const _Tp& __val, _Compare __comp)
2165 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2166 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2168 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2170 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2172 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2175 return std::__equal_range(__first, __last, __val,
2176 __gnu_cxx::__ops::__iter_comp_val(__comp),
2177 __gnu_cxx::__ops::__val_comp_iter(__comp));
2192 template<
typename _ForwardIterator,
typename _Tp>
2193 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2195 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2199 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2200 __glibcxx_function_requires(_LessThanOpConcept<
2202 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2203 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2205 _ForwardIterator __i
2206 = std::__lower_bound(__first, __last, __val,
2207 __gnu_cxx::__ops::__iter_less_val());
2208 return __i != __last && !(__val < *__i);
2226 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2227 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2229 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2230 const _Tp& __val, _Compare __comp)
2233 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2234 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2236 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2238 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2241 _ForwardIterator __i
2242 = std::__lower_bound(__first, __last, __val,
2243 __gnu_cxx::__ops::__iter_comp_val(__comp));
2244 return __i != __last && !bool(__comp(__val, *__i));
2250 template<
typename _InputIterator1,
typename _InputIterator2,
2251 typename _OutputIterator,
typename _Compare>
2254 _InputIterator2 __first2, _InputIterator2 __last2,
2255 _OutputIterator __result, _Compare __comp)
2257 while (__first1 != __last1 && __first2 != __last2)
2259 if (__comp(__first2, __first1))
2261 *__result = _GLIBCXX_MOVE(*__first2);
2266 *__result = _GLIBCXX_MOVE(*__first1);
2271 if (__first1 != __last1)
2272 _GLIBCXX_MOVE3(__first1, __last1, __result);
2276 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2277 typename _BidirectionalIterator3,
typename _Compare>
2280 _BidirectionalIterator1 __last1,
2281 _BidirectionalIterator2 __first2,
2282 _BidirectionalIterator2 __last2,
2283 _BidirectionalIterator3 __result,
2286 if (__first1 == __last1)
2288 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2291 else if (__first2 == __last2)
2298 if (__comp(__last2, __last1))
2300 *--__result = _GLIBCXX_MOVE(*__last1);
2301 if (__first1 == __last1)
2303 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2310 *--__result = _GLIBCXX_MOVE(*__last2);
2311 if (__first2 == __last2)
2319 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2321 _BidirectionalIterator1
2323 _BidirectionalIterator1 __middle,
2324 _BidirectionalIterator1 __last,
2325 _Distance __len1, _Distance __len2,
2326 _BidirectionalIterator2 __buffer,
2327 _Distance __buffer_size)
2329 _BidirectionalIterator2 __buffer_end;
2330 if (__len1 > __len2 && __len2 <= __buffer_size)
2334 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2335 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2336 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2341 else if (__len1 <= __buffer_size)
2345 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2346 _GLIBCXX_MOVE3(__middle, __last, __first);
2347 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2353 return std::rotate(__first, __middle, __last);
2357 template<
typename _BidirectionalIterator,
typename _Distance,
2358 typename _Pointer,
typename _Compare>
2361 _BidirectionalIterator __middle,
2362 _BidirectionalIterator __last,
2363 _Distance __len1, _Distance __len2,
2364 _Pointer __buffer, _Compare __comp)
2366 if (__len1 <= __len2)
2368 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2374 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2376 __buffer_end, __last, __comp);
2380 template<
typename _BidirectionalIterator,
typename _Distance,
2381 typename _Pointer,
typename _Compare>
2383 __merge_adaptive_resize(_BidirectionalIterator __first,
2384 _BidirectionalIterator __middle,
2385 _BidirectionalIterator __last,
2386 _Distance __len1, _Distance __len2,
2387 _Pointer __buffer, _Distance __buffer_size,
2390 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2392 __len1, __len2, __buffer, __comp);
2395 _BidirectionalIterator __first_cut = __first;
2396 _BidirectionalIterator __second_cut = __middle;
2397 _Distance __len11 = 0;
2398 _Distance __len22 = 0;
2399 if (__len1 > __len2)
2401 __len11 = __len1 / 2;
2404 = std::__lower_bound(__middle, __last, *__first_cut,
2405 __gnu_cxx::__ops::__iter_comp_val(__comp));
2410 __len22 = __len2 / 2;
2413 = std::__upper_bound(__first, __middle, *__second_cut,
2414 __gnu_cxx::__ops::__val_comp_iter(__comp));
2418 _BidirectionalIterator __new_middle
2420 _Distance(__len1 - __len11), __len22,
2421 __buffer, __buffer_size);
2422 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2424 __buffer, __buffer_size, __comp);
2425 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2426 _Distance(__len1 - __len11),
2427 _Distance(__len2 - __len22),
2428 __buffer, __buffer_size, __comp);
2433 template<
typename _BidirectionalIterator,
typename _Distance,
2435 _GLIBCXX26_CONSTEXPR
2438 _BidirectionalIterator __middle,
2439 _BidirectionalIterator __last,
2440 _Distance __len1, _Distance __len2,
2443 if (__len1 == 0 || __len2 == 0)
2446 if (__len1 + __len2 == 2)
2448 if (__comp(__middle, __first))
2449 std::iter_swap(__first, __middle);
2453 _BidirectionalIterator __first_cut = __first;
2454 _BidirectionalIterator __second_cut = __middle;
2455 _Distance __len11 = 0;
2456 _Distance __len22 = 0;
2457 if (__len1 > __len2)
2459 __len11 = __len1 / 2;
2462 = std::__lower_bound(__middle, __last, *__first_cut,
2463 __gnu_cxx::__ops::__iter_comp_val(__comp));
2468 __len22 = __len2 / 2;
2471 = std::__upper_bound(__first, __middle, *__second_cut,
2472 __gnu_cxx::__ops::__val_comp_iter(__comp));
2476 _BidirectionalIterator __new_middle
2477 = std::rotate(__first_cut, __middle, __second_cut);
2479 __len11, __len22, __comp);
2481 __len1 - __len11, __len2 - __len22, __comp);
2484 template<
typename _B
idirectionalIterator,
typename _Compare>
2485 _GLIBCXX26_CONSTEXPR
2487 __inplace_merge(_BidirectionalIterator __first,
2488 _BidirectionalIterator __middle,
2489 _BidirectionalIterator __last,
2492 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2494 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2497 if (__first == __middle || __middle == __last)
2500 const _DistanceType __len1 =
std::distance(__first, __middle);
2501 const _DistanceType __len2 =
std::distance(__middle, __last);
2504# if __glibcxx_constexpr_algorithms >= 202306L
2507 (__first, __middle, __last, __len1, __len2, __comp);
2510 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2513 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2515 if (__builtin_expect(__buf.size() == __buf.requested_size(),
true))
2517 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2518 else if (__builtin_expect(__buf.begin() == 0,
false))
2520 (__first, __middle, __last, __len1, __len2, __comp);
2522 std::__merge_adaptive_resize
2523 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2524 _DistanceType(__buf.size()), __comp);
2527 (__first, __middle, __last, __len1, __len2, __comp);
2549 template<
typename _B
idirectionalIterator>
2550 _GLIBCXX26_CONSTEXPR
2552 inplace_merge(_BidirectionalIterator __first,
2553 _BidirectionalIterator __middle,
2554 _BidirectionalIterator __last)
2557 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2558 _BidirectionalIterator>)
2559 __glibcxx_function_requires(_LessThanComparableConcept<
2561 __glibcxx_requires_sorted(__first, __middle);
2562 __glibcxx_requires_sorted(__middle, __last);
2563 __glibcxx_requires_irreflexive(__first, __last);
2565 std::__inplace_merge(__first, __middle, __last,
2566 __gnu_cxx::__ops::__iter_less_iter());
2591 template<
typename _B
idirectionalIterator,
typename _Compare>
2592 _GLIBCXX26_CONSTEXPR
2594 inplace_merge(_BidirectionalIterator __first,
2595 _BidirectionalIterator __middle,
2596 _BidirectionalIterator __last,
2600 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2601 _BidirectionalIterator>)
2602 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2605 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2606 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2607 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2609 std::__inplace_merge(__first, __middle, __last,
2610 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2615 template<
typename _InputIterator,
typename _OutputIterator,
2619 _InputIterator __first2, _InputIterator __last2,
2620 _OutputIterator __result, _Compare __comp)
2622 while (__first1 != __last1 && __first2 != __last2)
2624 if (__comp(__first2, __first1))
2626 *__result = _GLIBCXX_MOVE(*__first2);
2631 *__result = _GLIBCXX_MOVE(*__first1);
2636 return _GLIBCXX_MOVE3(__first2, __last2,
2637 _GLIBCXX_MOVE3(__first1, __last1,
2641 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2642 typename _Distance,
typename _Compare>
2644 __merge_sort_loop(_RandomAccessIterator1 __first,
2645 _RandomAccessIterator1 __last,
2646 _RandomAccessIterator2 __result, _Distance __step_size,
2649 const _Distance __two_step = 2 * __step_size;
2651 while (__last - __first >= __two_step)
2654 __first + __step_size,
2655 __first + __two_step,
2657 __first += __two_step;
2659 __step_size =
std::min(_Distance(__last - __first), __step_size);
2662 __first + __step_size, __last, __result, __comp);
2665 template<
typename _RandomAccessIterator,
typename _Distance,
2667 _GLIBCXX20_CONSTEXPR
2669 __chunk_insertion_sort(_RandomAccessIterator __first,
2670 _RandomAccessIterator __last,
2671 _Distance __chunk_size, _Compare __comp)
2673 while (__last - __first >= __chunk_size)
2675 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2676 __first += __chunk_size;
2678 std::__insertion_sort(__first, __last, __comp);
2681 enum { _S_chunk_size = 7 };
2683 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2685 __merge_sort_with_buffer(_RandomAccessIterator __first,
2686 _RandomAccessIterator __last,
2687 _Pointer __buffer, _Compare __comp)
2689 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2692 const _Distance __len = __last - __first;
2693 const _Pointer __buffer_last = __buffer + __len;
2695 _Distance __step_size = _S_chunk_size;
2696 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2698 while (__step_size < __len)
2700 std::__merge_sort_loop(__first, __last, __buffer,
2701 __step_size, __comp);
2703 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2704 __step_size, __comp);
2709 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2711 __stable_sort_adaptive(_RandomAccessIterator __first,
2712 _RandomAccessIterator __middle,
2713 _RandomAccessIterator __last,
2714 _Pointer __buffer, _Compare __comp)
2716 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2717 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2720 __middle - __first, __last - __middle,
2724 template<
typename _RandomAccessIterator,
typename _Pointer,
2725 typename _Distance,
typename _Compare>
2727 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2728 _RandomAccessIterator __last,
2729 _Pointer __buffer, _Distance __buffer_size,
2732 const _Distance __len = (__last - __first + 1) / 2;
2733 const _RandomAccessIterator __middle = __first + __len;
2734 if (__len > __buffer_size)
2736 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2737 __buffer_size, __comp);
2738 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2739 __buffer_size, __comp);
2740 std::__merge_adaptive_resize(__first, __middle, __last,
2741 _Distance(__middle - __first),
2742 _Distance(__last - __middle),
2743 __buffer, __buffer_size,
2747 std::__stable_sort_adaptive(__first, __middle, __last,
2752 template<
typename _RandomAccessIterator,
typename _Compare>
2753 _GLIBCXX26_CONSTEXPR
2756 _RandomAccessIterator __last, _Compare __comp)
2758 if (__last - __first < 15)
2760 std::__insertion_sort(__first, __last, __comp);
2763 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2779 template<
typename _InputIterator1,
typename _InputIterator2,
2781 _GLIBCXX20_CONSTEXPR
2783 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2784 _InputIterator2 __first2, _InputIterator2 __last2,
2787 while (__first1 != __last1 && __first2 != __last2)
2789 if (__comp(__first2, __first1))
2791 if (!__comp(__first1, __first2))
2796 return __first2 == __last2;
2817 template<
typename _InputIterator1,
typename _InputIterator2>
2818 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2820 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2821 _InputIterator2 __first2, _InputIterator2 __last2)
2824 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2825 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2826 __glibcxx_function_requires(_LessThanOpConcept<
2829 __glibcxx_function_requires(_LessThanOpConcept<
2832 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2833 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2834 __glibcxx_requires_irreflexive2(__first1, __last1);
2835 __glibcxx_requires_irreflexive2(__first2, __last2);
2837 return std::__includes(__first1, __last1, __first2, __last2,
2838 __gnu_cxx::__ops::__iter_less_iter());
2862 template<
typename _InputIterator1,
typename _InputIterator2,
2864 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2866 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2867 _InputIterator2 __first2, _InputIterator2 __last2,
2871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2872 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2873 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2876 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2879 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2880 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2881 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2882 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2884 return std::__includes(__first1, __last1, __first2, __last2,
2885 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2898 template<
typename _B
idirectionalIterator,
typename _Compare>
2899 _GLIBCXX20_CONSTEXPR
2901 __next_permutation(_BidirectionalIterator __first,
2902 _BidirectionalIterator __last, _Compare __comp)
2904 if (__first == __last)
2906 _BidirectionalIterator __i = __first;
2915 _BidirectionalIterator __ii = __i;
2917 if (__comp(__i, __ii))
2919 _BidirectionalIterator __j = __last;
2920 while (!__comp(__i, --__j))
2922 std::iter_swap(__i, __j);
2948 template<
typename _B
idirectionalIterator>
2949 _GLIBCXX20_CONSTEXPR
2951 next_permutation(_BidirectionalIterator __first,
2952 _BidirectionalIterator __last)
2955 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2956 _BidirectionalIterator>)
2957 __glibcxx_function_requires(_LessThanComparableConcept<
2959 __glibcxx_requires_valid_range(__first, __last);
2960 __glibcxx_requires_irreflexive(__first, __last);
2962 return std::__next_permutation
2963 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2981 template<
typename _B
idirectionalIterator,
typename _Compare>
2982 _GLIBCXX20_CONSTEXPR
2984 next_permutation(_BidirectionalIterator __first,
2985 _BidirectionalIterator __last, _Compare __comp)
2988 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2989 _BidirectionalIterator>)
2990 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2993 __glibcxx_requires_valid_range(__first, __last);
2994 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2996 return std::__next_permutation
2997 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3000 template<
typename _B
idirectionalIterator,
typename _Compare>
3001 _GLIBCXX20_CONSTEXPR
3003 __prev_permutation(_BidirectionalIterator __first,
3004 _BidirectionalIterator __last, _Compare __comp)
3006 if (__first == __last)
3008 _BidirectionalIterator __i = __first;
3017 _BidirectionalIterator __ii = __i;
3019 if (__comp(__ii, __i))
3021 _BidirectionalIterator __j = __last;
3022 while (!__comp(--__j, __i))
3024 std::iter_swap(__i, __j);
3051 template<
typename _B
idirectionalIterator>
3052 _GLIBCXX20_CONSTEXPR
3054 prev_permutation(_BidirectionalIterator __first,
3055 _BidirectionalIterator __last)
3058 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3059 _BidirectionalIterator>)
3060 __glibcxx_function_requires(_LessThanComparableConcept<
3062 __glibcxx_requires_valid_range(__first, __last);
3063 __glibcxx_requires_irreflexive(__first, __last);
3065 return std::__prev_permutation(__first, __last,
3066 __gnu_cxx::__ops::__iter_less_iter());
3084 template<
typename _B
idirectionalIterator,
typename _Compare>
3085 _GLIBCXX20_CONSTEXPR
3087 prev_permutation(_BidirectionalIterator __first,
3088 _BidirectionalIterator __last, _Compare __comp)
3091 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3092 _BidirectionalIterator>)
3093 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3096 __glibcxx_requires_valid_range(__first, __last);
3097 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3099 return std::__prev_permutation(__first, __last,
3100 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3106 template<
typename _InputIterator,
typename _OutputIterator,
3107 typename _Predicate,
typename _Tp>
3108 _GLIBCXX20_CONSTEXPR
3110 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3111 _OutputIterator __result,
3112 _Predicate __pred,
const _Tp& __new_value)
3114 for (; __first != __last; ++__first, (void)++__result)
3115 if (__pred(__first))
3116 *__result = __new_value;
3118 *__result = *__first;
3136 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3137 _GLIBCXX20_CONSTEXPR
3138 inline _OutputIterator
3139 replace_copy(_InputIterator __first, _InputIterator __last,
3140 _OutputIterator __result,
3141 const _Tp& __old_value,
const _Tp& __new_value)
3144 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3145 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3147 __glibcxx_function_requires(_EqualOpConcept<
3149 __glibcxx_requires_valid_range(__first, __last);
3151 return std::__replace_copy_if(__first, __last, __result,
3152 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3171 template<
typename _InputIterator,
typename _OutputIterator,
3172 typename _Predicate,
typename _Tp>
3173 _GLIBCXX20_CONSTEXPR
3174 inline _OutputIterator
3175 replace_copy_if(_InputIterator __first, _InputIterator __last,
3176 _OutputIterator __result,
3177 _Predicate __pred,
const _Tp& __new_value)
3180 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3181 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3183 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3185 __glibcxx_requires_valid_range(__first, __last);
3187 return std::__replace_copy_if(__first, __last, __result,
3188 __gnu_cxx::__ops::__pred_iter(__pred),
3192#if __cplusplus >= 201103L
3200 template<
typename _ForwardIterator>
3201 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3203 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3204 {
return std::is_sorted_until(__first, __last) == __last; }
3215 template<
typename _ForwardIterator,
typename _Compare>
3216 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3218 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3220 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3222 template<
typename _ForwardIterator,
typename _Compare>
3223 _GLIBCXX20_CONSTEXPR
3225 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3228 if (__first == __last)
3231 _ForwardIterator __next = __first;
3232 for (++__next; __next != __last; __first = __next, (void)++__next)
3233 if (__comp(__next, __first))
3246 template<
typename _ForwardIterator>
3247 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3248 inline _ForwardIterator
3249 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3253 __glibcxx_function_requires(_LessThanComparableConcept<
3255 __glibcxx_requires_valid_range(__first, __last);
3256 __glibcxx_requires_irreflexive(__first, __last);
3258 return std::__is_sorted_until(__first, __last,
3259 __gnu_cxx::__ops::__iter_less_iter());
3271 template<
typename _ForwardIterator,
typename _Compare>
3272 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3273 inline _ForwardIterator
3274 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3278 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3279 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3282 __glibcxx_requires_valid_range(__first, __last);
3283 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3285 return std::__is_sorted_until(__first, __last,
3286 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3297 template<
typename _Tp>
3298 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3299 inline pair<const _Tp&, const _Tp&>
3303 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3305 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3318 template<
typename _Tp,
typename _Compare>
3319 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3320 inline pair<const _Tp&, const _Tp&>
3321 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3327 template<
typename _ForwardIterator,
typename _Compare>
3328 _GLIBCXX14_CONSTEXPR
3329 pair<_ForwardIterator, _ForwardIterator>
3330 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3333 _ForwardIterator __next = __first;
3334 if (__first == __last
3335 || ++__next == __last)
3336 return std::make_pair(__first, __first);
3338 _ForwardIterator __min{}, __max{};
3339 if (__comp(__next, __first))
3353 while (__first != __last)
3356 if (++__next == __last)
3358 if (__comp(__first, __min))
3360 else if (!__comp(__first, __max))
3365 if (__comp(__next, __first))
3367 if (__comp(__next, __min))
3369 if (!__comp(__first, __max))
3374 if (__comp(__first, __min))
3376 if (!__comp(__next, __max))
3384 return std::make_pair(__min, __max);
3398 template<
typename _ForwardIterator>
3399 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3400 inline pair<_ForwardIterator, _ForwardIterator>
3401 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3404 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3405 __glibcxx_function_requires(_LessThanComparableConcept<
3407 __glibcxx_requires_valid_range(__first, __last);
3408 __glibcxx_requires_irreflexive(__first, __last);
3410 return std::__minmax_element(__first, __last,
3411 __gnu_cxx::__ops::__iter_less_iter());
3426 template<
typename _ForwardIterator,
typename _Compare>
3427 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3428 inline pair<_ForwardIterator, _ForwardIterator>
3429 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3433 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3437 __glibcxx_requires_valid_range(__first, __last);
3438 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3440 return std::__minmax_element(__first, __last,
3441 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3444 template<
typename _Tp>
3445 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3446 inline pair<_Tp, _Tp>
3447 minmax(initializer_list<_Tp> __l)
3449 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3450 pair<const _Tp*, const _Tp*> __p =
3451 std::__minmax_element(__l.begin(), __l.end(),
3452 __gnu_cxx::__ops::__iter_less_iter());
3453 return std::make_pair(*__p.first, *__p.second);
3456 template<
typename _Tp,
typename _Compare>
3457 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3458 inline pair<_Tp, _Tp>
3459 minmax(initializer_list<_Tp> __l, _Compare __comp)
3461 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3462 pair<const _Tp*, const _Tp*> __p =
3463 std::__minmax_element(__l.begin(), __l.end(),
3464 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3465 return std::make_pair(*__p.first, *__p.second);
3482 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3483 typename _BinaryPredicate>
3484 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3486 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3487 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3490 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3491 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3492 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3495 __glibcxx_requires_valid_range(__first1, __last1);
3497 return std::__is_permutation(__first1, __last1, __first2,
3498 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3501#if __cplusplus > 201103L
3502#pragma GCC diagnostic push
3503#pragma GCC diagnostic ignored "-Wc++17-extensions"
3504 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3505 typename _BinaryPredicate>
3506 _GLIBCXX20_CONSTEXPR
3508 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3509 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3510 _BinaryPredicate __pred)
3513 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3515 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3516 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3517 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3518 constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
3519 if constexpr (__ra_iters)
3521 if ((__last1 - __first1) != (__last2 - __first2))
3527 for (; __first1 != __last1 && __first2 != __last2;
3528 ++__first1, (void)++__first2)
3529 if (!__pred(__first1, __first2))
3532 if constexpr (__ra_iters)
3534 if (__first1 == __last1)
3541 if (__d1 == 0 && __d2 == 0)
3547 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3549 if (__scan != std::__find_if(__first1, __scan,
3550 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3553 auto __matches = std::__count_if(__first2, __last2,
3554 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3556 || std::__count_if(__scan, __last1,
3557 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3563#pragma GCC diagnostic pop
3578 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3579 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3581 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3582 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3584 __glibcxx_requires_valid_range(__first1, __last1);
3585 __glibcxx_requires_valid_range(__first2, __last2);
3588 std::__is_permutation(__first1, __last1, __first2, __last2,
3589 __gnu_cxx::__ops::__iter_equal_to_iter());
3606 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3607 typename _BinaryPredicate>
3608 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3610 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3611 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3612 _BinaryPredicate __pred)
3614 __glibcxx_requires_valid_range(__first1, __last1);
3615 __glibcxx_requires_valid_range(__first2, __last2);
3617 return std::__is_permutation(__first1, __last1, __first2, __last2,
3618 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3622#ifdef __glibcxx_clamp
3634 template<
typename _Tp>
3635 [[nodiscard]]
constexpr const _Tp&
3636 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3638 __glibcxx_assert(!(__hi < __lo));
3654 template<
typename _Tp,
typename _Compare>
3655 [[nodiscard]]
constexpr const _Tp&
3656 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3658 __glibcxx_assert(!__comp(__hi, __lo));
3684 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3685 pair<_IntType, _IntType>
3687 _UniformRandomBitGenerator&& __g)
3691 return std::make_pair(__x / __b1, __x % __b1);
3706 template<
typename _RandomAccessIterator,
3707 typename _UniformRandomNumberGenerator>
3709 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3710 _UniformRandomNumberGenerator&& __g)
3713 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3714 _RandomAccessIterator>)
3715 __glibcxx_requires_valid_range(__first, __last);
3717 if (__first == __last)
3723 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3725 typedef typename __distr_type::param_type __p_type;
3727 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3732 const __uc_type __urngrange = __g.max() - __g.min();
3733 const __uc_type __urange = __uc_type(__last - __first);
3735 if (__urngrange / __urange >= __urange)
3738 _RandomAccessIterator __i = __first + 1;
3744 if ((__urange % 2) == 0)
3746 __distr_type __d{0, 1};
3747 std::iter_swap(__i++, __first + __d(__g));
3754 while (__i != __last)
3756 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3761 std::iter_swap(__i++, __first + __pospos.
first);
3762 std::iter_swap(__i++, __first + __pospos.
second);
3770 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3771 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3775_GLIBCXX_BEGIN_NAMESPACE_ALGO
3789 template<
typename _InputIterator,
typename _Function>
3790 _GLIBCXX20_CONSTEXPR
3792 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3795 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3796 __glibcxx_requires_valid_range(__first, __last);
3797 for (; __first != __last; ++__first)
3802#if __cplusplus >= 201703L
3815 template<
typename _InputIterator,
typename _Size,
typename _Function>
3816 _GLIBCXX20_CONSTEXPR
3820 auto __n2 = std::__size_to_integer(__n);
3822 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3826 auto __last = __first + __n2;
3827 std::for_each(__first, __last,
std::move(__f));
3851 template<
typename _InputIterator,
typename _Tp>
3852 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3853 inline _InputIterator
3854 find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
3857 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3858 __glibcxx_function_requires(_EqualOpConcept<
3860 __glibcxx_requires_valid_range(__first, __last);
3862#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
3864 if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
3865 if constexpr (is_pointer_v<
decltype(std::__niter_base(__first))>
3866#if __glibcxx_concepts && __glibcxx_to_address
3867 || contiguous_iterator<_InputIterator>
3875 if (!(
static_cast<_ValT
>(__val) == __val))
3877 else if (!__is_constant_evaluated())
3879 const int __ival =
static_cast<int>(__val);
3880 if (
auto __n = __last - __first; __n > 0)
3882#if __glibcxx_concepts && __glibcxx_to_address
3885 const void* __p0 = std::__niter_base(__first);
3887 if (
auto __p1 = __builtin_memchr(__p0, __ival, __n))
3888 return __first + ((
const char*)__p1 - (
const char*)__p0);
3895 return std::__find_if(__first, __last,
3896 __gnu_cxx::__ops::__iter_equals_val(__val));
3909 template<
typename _InputIterator,
typename _Predicate>
3910 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3911 inline _InputIterator
3912 find_if(_InputIterator __first, _InputIterator __last,
3916 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3917 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3919 __glibcxx_requires_valid_range(__first, __last);
3921 return std::__find_if(__first, __last,
3922 __gnu_cxx::__ops::__pred_iter(__pred));
3941 template<
typename _InputIterator,
typename _ForwardIterator>
3942 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3944 find_first_of(_InputIterator __first1, _InputIterator __last1,
3945 _ForwardIterator __first2, _ForwardIterator __last2)
3948 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3949 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3950 __glibcxx_function_requires(_EqualOpConcept<
3953 __glibcxx_requires_valid_range(__first1, __last1);
3954 __glibcxx_requires_valid_range(__first2, __last2);
3956 for (; __first1 != __last1; ++__first1)
3957 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3958 if (*__first1 == *__iter)
3982 template<
typename _InputIterator,
typename _ForwardIterator,
3983 typename _BinaryPredicate>
3984 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3986 find_first_of(_InputIterator __first1, _InputIterator __last1,
3987 _ForwardIterator __first2, _ForwardIterator __last2,
3988 _BinaryPredicate __comp)
3991 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3992 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3993 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3996 __glibcxx_requires_valid_range(__first1, __last1);
3997 __glibcxx_requires_valid_range(__first2, __last2);
3999 for (; __first1 != __last1; ++__first1)
4000 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4001 if (__comp(*__first1, *__iter))
4015 template<
typename _ForwardIterator>
4016 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4017 inline _ForwardIterator
4018 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4021 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4022 __glibcxx_function_requires(_EqualityComparableConcept<
4024 __glibcxx_requires_valid_range(__first, __last);
4026 return std::__adjacent_find(__first, __last,
4027 __gnu_cxx::__ops::__iter_equal_to_iter());
4041 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4042 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4043 inline _ForwardIterator
4044 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4045 _BinaryPredicate __binary_pred)
4048 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4049 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4052 __glibcxx_requires_valid_range(__first, __last);
4054 return std::__adjacent_find(__first, __last,
4055 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4067 template<
typename _InputIterator,
typename _Tp>
4068 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4069 inline typename iterator_traits<_InputIterator>::difference_type
4070 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4073 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4074 __glibcxx_function_requires(_EqualOpConcept<
4076 __glibcxx_requires_valid_range(__first, __last);
4078 return std::__count_if(__first, __last,
4079 __gnu_cxx::__ops::__iter_equals_val(__value));
4091 template<
typename _InputIterator,
typename _Predicate>
4092 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4093 inline typename iterator_traits<_InputIterator>::difference_type
4094 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4097 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4098 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4100 __glibcxx_requires_valid_range(__first, __last);
4102 return std::__count_if(__first, __last,
4103 __gnu_cxx::__ops::__pred_iter(__pred));
4132 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4133 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4134 inline _ForwardIterator1
4135 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4136 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4139 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4140 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4141 __glibcxx_function_requires(_EqualOpConcept<
4144 __glibcxx_requires_valid_range(__first1, __last1);
4145 __glibcxx_requires_valid_range(__first2, __last2);
4147 return std::__search(__first1, __last1, __first2, __last2,
4148 __gnu_cxx::__ops::__iter_equal_to_iter());
4166 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4167 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4168 inline _ForwardIterator
4169 search_n(_ForwardIterator __first, _ForwardIterator __last,
4170 _Integer __count,
const _Tp& __val)
4173 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4174 __glibcxx_function_requires(_EqualOpConcept<
4176 __glibcxx_requires_valid_range(__first, __last);
4178 return std::__search_n(__first, __last, __count,
4179 __gnu_cxx::__ops::__iter_equals_val(__val));
4200 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4201 typename _BinaryPredicate>
4202 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4203 inline _ForwardIterator
4204 search_n(_ForwardIterator __first, _ForwardIterator __last,
4205 _Integer __count,
const _Tp& __val,
4206 _BinaryPredicate __binary_pred)
4209 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4210 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4212 __glibcxx_requires_valid_range(__first, __last);
4214 return std::__search_n(__first, __last, __count,
4215 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4218#if __cplusplus >= 201703L
4226 template<
typename _ForwardIterator,
typename _Searcher>
4227 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4228 inline _ForwardIterator
4229 search(_ForwardIterator __first, _ForwardIterator __last,
4230 const _Searcher& __searcher)
4231 {
return __searcher(__first, __last).first; }
4250 template<
typename _InputIterator,
typename _OutputIterator,
4251 typename _UnaryOperation>
4252 _GLIBCXX20_CONSTEXPR
4254 transform(_InputIterator __first, _InputIterator __last,
4255 _OutputIterator __result, _UnaryOperation __unary_op)
4258 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4259 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4261 __typeof__(__unary_op(*__first))>)
4262 __glibcxx_requires_valid_range(__first, __last);
4264 for (; __first != __last; ++__first, (void)++__result)
4265 *__result = __unary_op(*__first);
4288 template<
typename _InputIterator1,
typename _InputIterator2,
4289 typename _OutputIterator,
typename _BinaryOperation>
4290 _GLIBCXX20_CONSTEXPR
4292 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4293 _InputIterator2 __first2, _OutputIterator __result,
4294 _BinaryOperation __binary_op)
4297 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4298 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4299 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4301 __typeof__(__binary_op(*__first1,*__first2))>)
4302 __glibcxx_requires_valid_range(__first1, __last1);
4304 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4305 *__result = __binary_op(*__first1, *__first2);
4322 template<
typename _ForwardIterator,
typename _Tp>
4323 _GLIBCXX20_CONSTEXPR
4325 replace(_ForwardIterator __first, _ForwardIterator __last,
4326 const _Tp& __old_value,
const _Tp& __new_value)
4329 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4331 __glibcxx_function_requires(_EqualOpConcept<
4333 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4335 __glibcxx_requires_valid_range(__first, __last);
4337 for (; __first != __last; ++__first)
4338 if (*__first == __old_value)
4339 *__first = __new_value;
4355 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4356 _GLIBCXX20_CONSTEXPR
4358 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4359 _Predicate __pred,
const _Tp& __new_value)
4362 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4364 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4366 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4368 __glibcxx_requires_valid_range(__first, __last);
4370 for (; __first != __last; ++__first)
4371 if (__pred(*__first))
4372 *__first = __new_value;
4387 template<
typename _ForwardIterator,
typename _Generator>
4388 _GLIBCXX20_CONSTEXPR
4390 generate(_ForwardIterator __first, _ForwardIterator __last,
4394 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4395 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4397 __glibcxx_requires_valid_range(__first, __last);
4399 for (; __first != __last; ++__first)
4420 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4421 _GLIBCXX20_CONSTEXPR
4423 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4426 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4428 __typeof__(__gen())>)
4430 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4431 for (_IntSize __niter = std::__size_to_integer(__n);
4432 __niter > 0; --__niter, (void) ++__first)
4455 template<
typename _InputIterator,
typename _OutputIterator>
4456 _GLIBCXX20_CONSTEXPR
4457 inline _OutputIterator
4458 unique_copy(_InputIterator __first, _InputIterator __last,
4459 _OutputIterator __result)
4462 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4463 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4465 __glibcxx_function_requires(_EqualityComparableConcept<
4467 __glibcxx_requires_valid_range(__first, __last);
4469 if (__first == __last)
4472 __gnu_cxx::__ops::__iter_equal_to_iter(),
4495 template<
typename _InputIterator,
typename _OutputIterator,
4496 typename _BinaryPredicate>
4497 _GLIBCXX20_CONSTEXPR
4498 inline _OutputIterator
4499 unique_copy(_InputIterator __first, _InputIterator __last,
4500 _OutputIterator __result,
4501 _BinaryPredicate __binary_pred)
4504 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4505 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4507 __glibcxx_requires_valid_range(__first, __last);
4509 if (__first == __last)
4512 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4517#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4534 template<
typename _RandomAccessIterator>
4535 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4537 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4540 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4541 _RandomAccessIterator>)
4542 __glibcxx_requires_valid_range(__first, __last);
4544 if (__first == __last)
4547#if RAND_MAX < __INT_MAX__
4548 if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
4553 = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
4554 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4557 __xss ^= __xss << 13;
4558 __xss ^= __xss >> 17;
4559 __xss ^= __xss << 5;
4560 _RandomAccessIterator __j = __first
4561 + (__xss % ((__i - __first) + 1));
4563 std::iter_swap(__i, __j);
4569 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4572 _RandomAccessIterator __j = __first
4573 + (std::rand() % ((__i - __first) + 1));
4575 std::iter_swap(__i, __j);
4597 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4598 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4600 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4601#if __cplusplus >= 201103L
4602 _RandomNumberGenerator&& __rand)
4604 _RandomNumberGenerator& __rand)
4608 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4609 _RandomAccessIterator>)
4610 __glibcxx_requires_valid_range(__first, __last);
4612 if (__first == __last)
4614 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4616 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4618 std::iter_swap(__i, __j);
4639 template<
typename _ForwardIterator,
typename _Predicate>
4640 _GLIBCXX20_CONSTEXPR
4641 inline _ForwardIterator
4642 partition(_ForwardIterator __first, _ForwardIterator __last,
4646 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4648 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4650 __glibcxx_requires_valid_range(__first, __last);
4674 template<
typename _RandomAccessIterator>
4675 _GLIBCXX20_CONSTEXPR
4677 partial_sort(_RandomAccessIterator __first,
4678 _RandomAccessIterator __middle,
4679 _RandomAccessIterator __last)
4682 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4683 _RandomAccessIterator>)
4684 __glibcxx_function_requires(_LessThanComparableConcept<
4686 __glibcxx_requires_valid_range(__first, __middle);
4687 __glibcxx_requires_valid_range(__middle, __last);
4688 __glibcxx_requires_irreflexive(__first, __last);
4690 std::__partial_sort(__first, __middle, __last,
4691 __gnu_cxx::__ops::__iter_less_iter());
4713 template<
typename _RandomAccessIterator,
typename _Compare>
4714 _GLIBCXX20_CONSTEXPR
4716 partial_sort(_RandomAccessIterator __first,
4717 _RandomAccessIterator __middle,
4718 _RandomAccessIterator __last,
4722 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4723 _RandomAccessIterator>)
4724 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4727 __glibcxx_requires_valid_range(__first, __middle);
4728 __glibcxx_requires_valid_range(__middle, __last);
4729 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4731 std::__partial_sort(__first, __middle, __last,
4732 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4750 template<
typename _RandomAccessIterator>
4751 _GLIBCXX20_CONSTEXPR
4753 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4754 _RandomAccessIterator __last)
4757 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4758 _RandomAccessIterator>)
4759 __glibcxx_function_requires(_LessThanComparableConcept<
4761 __glibcxx_requires_valid_range(__first, __nth);
4762 __glibcxx_requires_valid_range(__nth, __last);
4763 __glibcxx_requires_irreflexive(__first, __last);
4765 if (__first == __last || __nth == __last)
4768 std::__introselect(__first, __nth, __last,
4770 __gnu_cxx::__ops::__iter_less_iter());
4790 template<
typename _RandomAccessIterator,
typename _Compare>
4791 _GLIBCXX20_CONSTEXPR
4793 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4794 _RandomAccessIterator __last, _Compare __comp)
4797 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4798 _RandomAccessIterator>)
4799 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4802 __glibcxx_requires_valid_range(__first, __nth);
4803 __glibcxx_requires_valid_range(__nth, __last);
4804 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4806 if (__first == __last || __nth == __last)
4809 std::__introselect(__first, __nth, __last,
4811 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4828 template<
typename _RandomAccessIterator>
4829 _GLIBCXX20_CONSTEXPR
4831 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4834 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4835 _RandomAccessIterator>)
4836 __glibcxx_function_requires(_LessThanComparableConcept<
4838 __glibcxx_requires_valid_range(__first, __last);
4839 __glibcxx_requires_irreflexive(__first, __last);
4841 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4859 template<
typename _RandomAccessIterator,
typename _Compare>
4860 _GLIBCXX20_CONSTEXPR
4862 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4866 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4867 _RandomAccessIterator>)
4868 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4871 __glibcxx_requires_valid_range(__first, __last);
4872 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4874 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4877 template<
typename _InputIterator1,
typename _InputIterator2,
4878 typename _OutputIterator,
typename _Compare>
4879 _GLIBCXX20_CONSTEXPR
4881 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4882 _InputIterator2 __first2, _InputIterator2 __last2,
4883 _OutputIterator __result, _Compare __comp)
4885 while (__first1 != __last1 && __first2 != __last2)
4887 if (__comp(__first2, __first1))
4889 *__result = *__first2;
4894 *__result = *__first1;
4899 return std::copy(__first2, __last2,
4900 std::copy(__first1, __last1, __result));
4922 template<
typename _InputIterator1,
typename _InputIterator2,
4923 typename _OutputIterator>
4924 _GLIBCXX20_CONSTEXPR
4925 inline _OutputIterator
4926 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4927 _InputIterator2 __first2, _InputIterator2 __last2,
4928 _OutputIterator __result)
4931 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4932 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4933 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4935 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4937 __glibcxx_function_requires(_LessThanOpConcept<
4940 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4941 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4942 __glibcxx_requires_irreflexive2(__first1, __last1);
4943 __glibcxx_requires_irreflexive2(__first2, __last2);
4945 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4946 __first2, __last2, __result,
4947 __gnu_cxx::__ops::__iter_less_iter());
4973 template<
typename _InputIterator1,
typename _InputIterator2,
4974 typename _OutputIterator,
typename _Compare>
4975 _GLIBCXX20_CONSTEXPR
4976 inline _OutputIterator
4977 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4978 _InputIterator2 __first2, _InputIterator2 __last2,
4979 _OutputIterator __result, _Compare __comp)
4982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4984 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4986 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4988 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4991 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4992 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4993 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4994 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4996 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4997 __first2, __last2, __result,
4998 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5001 template<
typename _RandomAccessIterator,
typename _Compare>
5002 _GLIBCXX26_CONSTEXPR
5004 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5007 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5009 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5012 if (__first == __last)
5016# if __glibcxx_constexpr_algorithms >= 202306L
5022 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5025 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
5027 if (__builtin_expect(__buf.requested_size() == __buf.size(),
true))
5028 std::__stable_sort_adaptive(__first,
5029 __first + _DistanceType(__buf.size()),
5030 __last, __buf.begin(), __comp);
5031 else if (__builtin_expect(__buf.begin() == 0,
false))
5034 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
5035 _DistanceType(__buf.size()), __comp);
5058 template<
typename _RandomAccessIterator>
5059 _GLIBCXX26_CONSTEXPR
5061 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5064 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5065 _RandomAccessIterator>)
5066 __glibcxx_function_requires(_LessThanComparableConcept<
5068 __glibcxx_requires_valid_range(__first, __last);
5069 __glibcxx_requires_irreflexive(__first, __last);
5071 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5072 __gnu_cxx::__ops::__iter_less_iter());
5093 template<
typename _RandomAccessIterator,
typename _Compare>
5094 _GLIBCXX26_CONSTEXPR
5096 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5100 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5101 _RandomAccessIterator>)
5102 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5105 __glibcxx_requires_valid_range(__first, __last);
5106 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5108 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5109 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5112 template<
typename _InputIterator1,
typename _InputIterator2,
5113 typename _OutputIterator,
5115 _GLIBCXX20_CONSTEXPR
5117 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5118 _InputIterator2 __first2, _InputIterator2 __last2,
5119 _OutputIterator __result, _Compare __comp)
5121 while (__first1 != __last1 && __first2 != __last2)
5123 if (__comp(__first1, __first2))
5125 *__result = *__first1;
5128 else if (__comp(__first2, __first1))
5130 *__result = *__first2;
5135 *__result = *__first1;
5141 return std::copy(__first2, __last2,
5142 std::copy(__first1, __last1, __result));
5164 template<
typename _InputIterator1,
typename _InputIterator2,
5165 typename _OutputIterator>
5166 _GLIBCXX20_CONSTEXPR
5167 inline _OutputIterator
5168 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5169 _InputIterator2 __first2, _InputIterator2 __last2,
5170 _OutputIterator __result)
5173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5174 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5175 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5177 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5179 __glibcxx_function_requires(_LessThanOpConcept<
5182 __glibcxx_function_requires(_LessThanOpConcept<
5185 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5186 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5187 __glibcxx_requires_irreflexive2(__first1, __last1);
5188 __glibcxx_requires_irreflexive2(__first2, __last2);
5190 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5191 __first2, __last2, __result,
5192 __gnu_cxx::__ops::__iter_less_iter());
5215 template<
typename _InputIterator1,
typename _InputIterator2,
5216 typename _OutputIterator,
typename _Compare>
5217 _GLIBCXX20_CONSTEXPR
5218 inline _OutputIterator
5219 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5220 _InputIterator2 __first2, _InputIterator2 __last2,
5221 _OutputIterator __result, _Compare __comp)
5224 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5225 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5226 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5228 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5230 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5236 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5237 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5238 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5239 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5241 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5242 __first2, __last2, __result,
5243 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5246 template<
typename _InputIterator1,
typename _InputIterator2,
5247 typename _OutputIterator,
5249 _GLIBCXX20_CONSTEXPR
5251 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5252 _InputIterator2 __first2, _InputIterator2 __last2,
5253 _OutputIterator __result, _Compare __comp)
5255 while (__first1 != __last1 && __first2 != __last2)
5256 if (__comp(__first1, __first2))
5258 else if (__comp(__first2, __first1))
5262 *__result = *__first1;
5288 template<
typename _InputIterator1,
typename _InputIterator2,
5289 typename _OutputIterator>
5290 _GLIBCXX20_CONSTEXPR
5291 inline _OutputIterator
5292 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5293 _InputIterator2 __first2, _InputIterator2 __last2,
5294 _OutputIterator __result)
5297 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5298 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5299 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5301 __glibcxx_function_requires(_LessThanOpConcept<
5304 __glibcxx_function_requires(_LessThanOpConcept<
5307 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5308 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5309 __glibcxx_requires_irreflexive2(__first1, __last1);
5310 __glibcxx_requires_irreflexive2(__first2, __last2);
5312 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5313 __first2, __last2, __result,
5314 __gnu_cxx::__ops::__iter_less_iter());
5338 template<
typename _InputIterator1,
typename _InputIterator2,
5339 typename _OutputIterator,
typename _Compare>
5340 _GLIBCXX20_CONSTEXPR
5341 inline _OutputIterator
5342 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5343 _InputIterator2 __first2, _InputIterator2 __last2,
5344 _OutputIterator __result, _Compare __comp)
5347 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5348 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5349 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5351 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5354 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5357 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5358 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5359 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5360 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5362 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5363 __first2, __last2, __result,
5364 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5367 template<
typename _InputIterator1,
typename _InputIterator2,
5368 typename _OutputIterator,
5370 _GLIBCXX20_CONSTEXPR
5372 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5373 _InputIterator2 __first2, _InputIterator2 __last2,
5374 _OutputIterator __result, _Compare __comp)
5376 while (__first1 != __last1 && __first2 != __last2)
5377 if (__comp(__first1, __first2))
5379 *__result = *__first1;
5383 else if (__comp(__first2, __first1))
5390 return std::copy(__first1, __last1, __result);
5413 template<
typename _InputIterator1,
typename _InputIterator2,
5414 typename _OutputIterator>
5415 _GLIBCXX20_CONSTEXPR
5416 inline _OutputIterator
5417 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5418 _InputIterator2 __first2, _InputIterator2 __last2,
5419 _OutputIterator __result)
5422 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5423 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5424 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5426 __glibcxx_function_requires(_LessThanOpConcept<
5429 __glibcxx_function_requires(_LessThanOpConcept<
5432 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5433 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5434 __glibcxx_requires_irreflexive2(__first1, __last1);
5435 __glibcxx_requires_irreflexive2(__first2, __last2);
5437 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5438 __first2, __last2, __result,
5439 __gnu_cxx::__ops::__iter_less_iter());
5465 template<
typename _InputIterator1,
typename _InputIterator2,
5466 typename _OutputIterator,
typename _Compare>
5467 _GLIBCXX20_CONSTEXPR
5468 inline _OutputIterator
5469 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5470 _InputIterator2 __first2, _InputIterator2 __last2,
5471 _OutputIterator __result, _Compare __comp)
5474 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5475 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5478 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5481 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5484 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5485 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5486 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5487 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5489 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5490 __first2, __last2, __result,
5491 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5494 template<
typename _InputIterator1,
typename _InputIterator2,
5495 typename _OutputIterator,
5497 _GLIBCXX20_CONSTEXPR
5499 __set_symmetric_difference(_InputIterator1 __first1,
5500 _InputIterator1 __last1,
5501 _InputIterator2 __first2,
5502 _InputIterator2 __last2,
5503 _OutputIterator __result,
5506 while (__first1 != __last1 && __first2 != __last2)
5507 if (__comp(__first1, __first2))
5509 *__result = *__first1;
5513 else if (__comp(__first2, __first1))
5515 *__result = *__first2;
5524 return std::copy(__first2, __last2,
5525 std::copy(__first1, __last1, __result));
5546 template<
typename _InputIterator1,
typename _InputIterator2,
5547 typename _OutputIterator>
5548 _GLIBCXX20_CONSTEXPR
5549 inline _OutputIterator
5550 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5551 _InputIterator2 __first2, _InputIterator2 __last2,
5552 _OutputIterator __result)
5555 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5556 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5557 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5559 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5561 __glibcxx_function_requires(_LessThanOpConcept<
5564 __glibcxx_function_requires(_LessThanOpConcept<
5567 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5568 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5569 __glibcxx_requires_irreflexive2(__first1, __last1);
5570 __glibcxx_requires_irreflexive2(__first2, __last2);
5572 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5573 __first2, __last2, __result,
5574 __gnu_cxx::__ops::__iter_less_iter());
5598 template<
typename _InputIterator1,
typename _InputIterator2,
5599 typename _OutputIterator,
typename _Compare>
5600 _GLIBCXX20_CONSTEXPR
5601 inline _OutputIterator
5602 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5603 _InputIterator2 __first2, _InputIterator2 __last2,
5604 _OutputIterator __result,
5608 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5609 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5610 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5612 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5614 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5617 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5620 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5621 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5622 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5623 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5625 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5626 __first2, __last2, __result,
5627 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5630 template<
typename _ForwardIterator,
typename _Compare>
5631 _GLIBCXX14_CONSTEXPR
5633 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5636 if (__first == __last)
5638 _ForwardIterator __result = __first;
5639 while (++__first != __last)
5640 if (__comp(__first, __result))
5652 template<
typename _ForwardIterator>
5653 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5655 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5658 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5659 __glibcxx_function_requires(_LessThanComparableConcept<
5661 __glibcxx_requires_valid_range(__first, __last);
5662 __glibcxx_requires_irreflexive(__first, __last);
5664 return _GLIBCXX_STD_A::__min_element(__first, __last,
5665 __gnu_cxx::__ops::__iter_less_iter());
5677 template<
typename _ForwardIterator,
typename _Compare>
5678 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5679 inline _ForwardIterator
5680 min_element(_ForwardIterator __first, _ForwardIterator __last,
5684 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5685 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5688 __glibcxx_requires_valid_range(__first, __last);
5689 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5691 return _GLIBCXX_STD_A::__min_element(__first, __last,
5692 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5695 template<
typename _ForwardIterator,
typename _Compare>
5696 _GLIBCXX14_CONSTEXPR
5698 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5701 if (__first == __last)
return __first;
5702 _ForwardIterator __result = __first;
5703 while (++__first != __last)
5704 if (__comp(__result, __first))
5716 template<
typename _ForwardIterator>
5717 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5718 inline _ForwardIterator
5719 max_element(_ForwardIterator __first, _ForwardIterator __last)
5722 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5723 __glibcxx_function_requires(_LessThanComparableConcept<
5725 __glibcxx_requires_valid_range(__first, __last);
5726 __glibcxx_requires_irreflexive(__first, __last);
5728 return _GLIBCXX_STD_A::__max_element(__first, __last,
5729 __gnu_cxx::__ops::__iter_less_iter());
5741 template<
typename _ForwardIterator,
typename _Compare>
5742 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5743 inline _ForwardIterator
5744 max_element(_ForwardIterator __first, _ForwardIterator __last,
5748 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5749 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5752 __glibcxx_requires_valid_range(__first, __last);
5753 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5755 return _GLIBCXX_STD_A::__max_element(__first, __last,
5756 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5759#if __cplusplus >= 201103L
5761 template<
typename _Tp>
5762 _GLIBCXX14_CONSTEXPR
5764 min(initializer_list<_Tp> __l)
5766 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5767 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5768 __gnu_cxx::__ops::__iter_less_iter());
5771 template<
typename _Tp,
typename _Compare>
5772 _GLIBCXX14_CONSTEXPR
5774 min(initializer_list<_Tp> __l, _Compare __comp)
5776 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5777 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5778 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5781 template<
typename _Tp>
5782 _GLIBCXX14_CONSTEXPR
5784 max(initializer_list<_Tp> __l)
5786 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5787 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5788 __gnu_cxx::__ops::__iter_less_iter());
5791 template<
typename _Tp,
typename _Compare>
5792 _GLIBCXX14_CONSTEXPR
5794 max(initializer_list<_Tp> __l, _Compare __comp)
5796 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5797 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5798 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5802#if __cplusplus >= 201402L
5804 template<
typename _InputIterator,
typename _RandomAccessIterator,
5805 typename _Size,
typename _UniformRandomBitGenerator>
5806 _RandomAccessIterator
5809 _Size __n, _UniformRandomBitGenerator&& __g)
5812 using __param_type =
typename __distrib_type::param_type;
5813 __distrib_type __d{};
5814 _Size __sample_sz = 0;
5815 while (__first != __last && __sample_sz != __n)
5817 __out[__sample_sz++] = *__first;
5820 for (
auto __pop_sz = __sample_sz; __first != __last;
5821 ++__first, (void) ++__pop_sz)
5823 const auto __k = __d(__g, __param_type{0, __pop_sz});
5825 __out[__k] = *__first;
5827 return __out + __sample_sz;
5831 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5832 typename _Size,
typename _UniformRandomBitGenerator>
5834 __sample(_ForwardIterator __first, _ForwardIterator __last,
5836 _OutputIterator __out, _Cat,
5837 _Size __n, _UniformRandomBitGenerator&& __g)
5840 using __param_type =
typename __distrib_type::param_type;
5845 if (__first == __last)
5848 __distrib_type __d{};
5850 __n =
std::min(__n, __unsampled_sz);
5855 const __uc_type __urngrange = __g.max() - __g.min();
5856 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5860 while (__n != 0 && __unsampled_sz >= 2)
5866 if (__p.
first < __n)
5868 *__out++ = *__first;
5874 if (__n == 0)
break;
5879 *__out++ = *__first;
5889 for (; __n != 0; ++__first)
5890 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5892 *__out++ = *__first;
5899#ifdef __glibcxx_sample
5901 template<typename _PopulationIterator, typename _SampleIterator,
5902 typename _Distance,
typename _UniformRandomBitGenerator>
5904 sample(_PopulationIterator __first, _PopulationIterator __last,
5905 _SampleIterator __out, _Distance __n,
5906 _UniformRandomBitGenerator&& __g)
5908 using __pop_cat =
typename
5910 using __samp_cat =
typename
5914 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5916 "output range must use a RandomAccessIterator when input range"
5917 " does not meet the ForwardIterator requirements");
5920 "sample size must be an integer type");
5923 return _GLIBCXX_STD_A::
5924 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5925 std::forward<_UniformRandomBitGenerator>(__g));
5929_GLIBCXX_END_NAMESPACE_ALGO
5930_GLIBCXX_END_NAMESPACE_VERSION
5933#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 make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
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...
constexpr _OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
_GLIBCXX26_CONSTEXPR 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.
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.
_GLIBCXX26_CONSTEXPR _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(__...
_GLIBCXX26_CONSTEXPR void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
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.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
Marking output iterators.
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...