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,
240 _BinaryPredicate __comp)
242 if (__first2 == __last2)
245 _ForwardIterator1 __result = __last1;
248 _ForwardIterator1 __new_result
249 = std::__search(__first1, __last1, __first2, __last2, __comp);
250 if (__new_result == __last1)
254 __result = __new_result;
255 __first1 = __new_result;
262 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
263 typename _BinaryPredicate>
265 _BidirectionalIterator1
266 __find_end(_BidirectionalIterator1 __first1,
267 _BidirectionalIterator1 __last1,
268 _BidirectionalIterator2 __first2,
269 _BidirectionalIterator2 __last2,
271 _BinaryPredicate __comp)
274 __glibcxx_function_requires(_BidirectionalIteratorConcept<
275 _BidirectionalIterator1>)
276 __glibcxx_function_requires(_BidirectionalIteratorConcept<
277 _BidirectionalIterator2>)
282 _RevIterator1 __rlast1(__first1);
283 _RevIterator2 __rlast2(__first2);
284 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
285 _RevIterator2(__last2), __rlast2,
288 if (__rresult == __rlast1)
292 _BidirectionalIterator1 __result = __rresult.
base();
324 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
325 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
326 inline _ForwardIterator1
327 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
328 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
331 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
332 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
333 __glibcxx_function_requires(_EqualOpConcept<
336 __glibcxx_requires_valid_range(__first1, __last1);
337 __glibcxx_requires_valid_range(__first2, __last2);
339 return std::__find_end(__first1, __last1, __first2, __last2,
342 __gnu_cxx::__ops::__iter_equal_to_iter());
373 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
374 typename _BinaryPredicate>
375 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
376 inline _ForwardIterator1
377 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
378 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
379 _BinaryPredicate __comp)
382 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
383 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
384 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
387 __glibcxx_requires_valid_range(__first1, __last1);
388 __glibcxx_requires_valid_range(__first2, __last2);
390 return std::__find_end(__first1, __last1, __first2, __last2,
393 __gnu_cxx::__ops::__iter_comp_iter(__comp));
396#if __cplusplus >= 201103L
409 template<
typename _InputIterator,
typename _Predicate>
410 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
412 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
413 {
return __last == std::find_if_not(__first, __last, __pred); }
427 template<
typename _InputIterator,
typename _Predicate>
428 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
430 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
431 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
446 template<
typename _InputIterator,
typename _Predicate>
447 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
449 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
450 {
return !std::none_of(__first, __last, __pred); }
462 template<
typename _InputIterator,
typename _Predicate>
463 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
464 inline _InputIterator
465 find_if_not(_InputIterator __first, _InputIterator __last,
469 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
470 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
472 __glibcxx_requires_valid_range(__first, __last);
474 __gnu_cxx::__ops::__pred_iter(__pred));
487 template<
typename _InputIterator,
typename _Predicate>
488 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
490 is_partitioned(_InputIterator __first, _InputIterator __last,
493 __first = std::find_if_not(__first, __last, __pred);
494 if (__first == __last)
497 return std::none_of(__first, __last, __pred);
509 template<
typename _ForwardIterator,
typename _Predicate>
510 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
512 partition_point(_ForwardIterator __first, _ForwardIterator __last,
516 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
517 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
521 __glibcxx_requires_valid_range(__first, __last);
530 _DistanceType __half = __len >> 1;
531 _ForwardIterator __middle = __first;
533 if (__pred(*__middle))
537 __len = __len - __half - 1;
546 template<
typename _InputIterator,
typename _OutputIterator,
550 __remove_copy_if(_InputIterator __first, _InputIterator __last,
551 _OutputIterator __result, _Predicate __pred)
553 for (; __first != __last; ++__first)
554 if (!__pred(__first))
556 *__result = *__first;
576 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
578 inline _OutputIterator
579 remove_copy(_InputIterator __first, _InputIterator __last,
580 _OutputIterator __result,
const _Tp& __value)
583 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
584 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
586 __glibcxx_function_requires(_EqualOpConcept<
588 __glibcxx_requires_valid_range(__first, __last);
590 return std::__remove_copy_if(__first, __last, __result,
591 __gnu_cxx::__ops::__iter_equals_val(__value));
609 template<
typename _InputIterator,
typename _OutputIterator,
612 inline _OutputIterator
613 remove_copy_if(_InputIterator __first, _InputIterator __last,
614 _OutputIterator __result, _Predicate __pred)
617 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
618 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
620 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
622 __glibcxx_requires_valid_range(__first, __last);
624 return std::__remove_copy_if(__first, __last, __result,
625 __gnu_cxx::__ops::__pred_iter(__pred));
628#if __cplusplus >= 201103L
644 template<
typename _InputIterator,
typename _OutputIterator,
648 copy_if(_InputIterator __first, _InputIterator __last,
649 _OutputIterator __result, _Predicate __pred)
652 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
653 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
655 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
657 __glibcxx_requires_valid_range(__first, __last);
659 for (; __first != __last; ++__first)
660 if (__pred(*__first))
662 *__result = *__first;
681 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
683 inline _OutputIterator
684 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
687 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
688 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
691 const auto __n2 = std::__size_to_integer(__n);
695 __glibcxx_requires_can_increment(__first, __n2);
696 __glibcxx_requires_can_increment(__result, __n2);
698 auto __res = std::__copy_n_a(std::__niter_base(__first), __n2,
699 std::__niter_base(__result),
true);
700 return std::__niter_wrap(__result,
std::move(__res));
718 template<
typename _InputIterator,
typename _OutputIterator1,
719 typename _OutputIterator2,
typename _Predicate>
722 partition_copy(_InputIterator __first, _InputIterator __last,
723 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
727 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
728 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
730 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
732 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
734 __glibcxx_requires_valid_range(__first, __last);
736 for (; __first != __last; ++__first)
737 if (__pred(*__first))
739 *__out_true = *__first;
744 *__out_false = *__first;
769 template<
typename _ForwardIterator,
typename _Tp>
770 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
771 inline _ForwardIterator
772 remove(_ForwardIterator __first, _ForwardIterator __last,
776 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
778 __glibcxx_function_requires(_EqualOpConcept<
780 __glibcxx_requires_valid_range(__first, __last);
782 return std::__remove_if(__first, __last,
783 __gnu_cxx::__ops::__iter_equals_val(__value));
803 template<
typename _ForwardIterator,
typename _Predicate>
804 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
805 inline _ForwardIterator
806 remove_if(_ForwardIterator __first, _ForwardIterator __last,
810 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
812 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
814 __glibcxx_requires_valid_range(__first, __last);
816 return std::__remove_if(__first, __last,
817 __gnu_cxx::__ops::__pred_iter(__pred));
820 template<
typename _ForwardIterator,
typename _BinaryPredicate>
823 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
824 _BinaryPredicate __binary_pred)
826 if (__first == __last)
828 _ForwardIterator __next = __first;
829 while (++__next != __last)
831 if (__binary_pred(__first, __next))
838 template<
typename _ForwardIterator,
typename _BinaryPredicate>
841 __unique(_ForwardIterator __first, _ForwardIterator __last,
842 _BinaryPredicate __binary_pred)
845 __first = std::__adjacent_find(__first, __last, __binary_pred);
846 if (__first == __last)
850 _ForwardIterator __dest = __first;
852 while (++__first != __last)
853 if (!__binary_pred(__dest, __first))
854 *++__dest = _GLIBCXX_MOVE(*__first);
872 template<
typename _ForwardIterator>
873 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
874 inline _ForwardIterator
875 unique(_ForwardIterator __first, _ForwardIterator __last)
878 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
880 __glibcxx_function_requires(_EqualityComparableConcept<
882 __glibcxx_requires_valid_range(__first, __last);
884 return std::__unique(__first, __last,
885 __gnu_cxx::__ops::__iter_equal_to_iter());
903 template<
typename _ForwardIterator,
typename _BinaryPredicate>
904 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
905 inline _ForwardIterator
906 unique(_ForwardIterator __first, _ForwardIterator __last,
907 _BinaryPredicate __binary_pred)
910 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
912 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
915 __glibcxx_requires_valid_range(__first, __last);
917 return std::__unique(__first, __last,
918 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
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,
1452 _ForwardIterator __last,
1453 _Predicate __pred, _Distance __len,
1455 _Distance __buffer_size)
1460 if (__len <= __buffer_size)
1462 _ForwardIterator __result1 = __first;
1463 _Pointer __result2 = __buffer;
1468 *__result2 = _GLIBCXX_MOVE(*__first);
1471 for (; __first != __last; ++__first)
1472 if (__pred(__first))
1474 *__result1 = _GLIBCXX_MOVE(*__first);
1479 *__result2 = _GLIBCXX_MOVE(*__first);
1483 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1487 _ForwardIterator __middle = __first;
1489 _ForwardIterator __left_split =
1491 __len / 2, __buffer,
1496 _Distance __right_len = __len - __len / 2;
1497 _ForwardIterator __right_split =
1504 __buffer, __buffer_size);
1506 return std::rotate(__left_split, __middle, __right_split);
1509 template<
typename _ForwardIterator,
typename _Predicate>
1511 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1516 if (__first == __last)
1519 typedef typename iterator_traits<_ForwardIterator>::value_type
1521 typedef typename iterator_traits<_ForwardIterator>::difference_type
1524 _Temporary_buffer<_ForwardIterator, _ValueType>
1528 _DistanceType(__buf.requested_size()),
1530 _DistanceType(__buf.size()));
1550 template<
typename _ForwardIterator,
typename _Predicate>
1551 inline _ForwardIterator
1552 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1556 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1558 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1560 __glibcxx_requires_valid_range(__first, __last);
1562 return std::__stable_partition(__first, __last,
1563 __gnu_cxx::__ops::__pred_iter(__pred));
1570 template<
typename _RandomAccessIterator,
typename _Compare>
1571 _GLIBCXX20_CONSTEXPR
1573 __heap_select(_RandomAccessIterator __first,
1574 _RandomAccessIterator __middle,
1575 _RandomAccessIterator __last, _Compare __comp)
1577 std::__make_heap(__first, __middle, __comp);
1578 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1579 if (__comp(__i, __first))
1580 std::__pop_heap(__first, __middle, __i, __comp);
1585 template<
typename _InputIterator,
typename _RandomAccessIterator,
1587 _GLIBCXX20_CONSTEXPR
1588 _RandomAccessIterator
1589 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1590 _RandomAccessIterator __result_first,
1591 _RandomAccessIterator __result_last,
1597 typedef typename _RItTraits::difference_type _DistanceType;
1599 if (__result_first == __result_last)
1600 return __result_last;
1601 _RandomAccessIterator __result_real_last = __result_first;
1602 while (__first != __last && __result_real_last != __result_last)
1604 *__result_real_last = *__first;
1605 ++__result_real_last;
1609 std::__make_heap(__result_first, __result_real_last, __comp);
1610 while (__first != __last)
1612 if (__comp(__first, __result_first))
1613 std::__adjust_heap(__result_first, _DistanceType(0),
1614 _DistanceType(__result_real_last
1616 _InputValueType(*__first), __comp);
1619 std::__sort_heap(__result_first, __result_real_last, __comp);
1620 return __result_real_last;
1643 template<
typename _InputIterator,
typename _RandomAccessIterator>
1644 _GLIBCXX20_CONSTEXPR
1645 inline _RandomAccessIterator
1646 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1647 _RandomAccessIterator __result_first,
1648 _RandomAccessIterator __result_last)
1650#ifdef _GLIBCXX_CONCEPT_CHECKS
1658 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1659 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1661 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1663 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1664 __glibcxx_requires_valid_range(__first, __last);
1665 __glibcxx_requires_irreflexive(__first, __last);
1666 __glibcxx_requires_valid_range(__result_first, __result_last);
1668 return std::__partial_sort_copy(__first, __last,
1669 __result_first, __result_last,
1670 __gnu_cxx::__ops::__iter_less_iter());
1693 template<
typename _InputIterator,
typename _RandomAccessIterator,
1695 _GLIBCXX20_CONSTEXPR
1696 inline _RandomAccessIterator
1697 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1698 _RandomAccessIterator __result_first,
1699 _RandomAccessIterator __result_last,
1702#ifdef _GLIBCXX_CONCEPT_CHECKS
1710 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1711 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1712 _RandomAccessIterator>)
1713 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1715 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1716 _InputValueType, _OutputValueType>)
1717 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1718 _OutputValueType, _OutputValueType>)
1719 __glibcxx_requires_valid_range(__first, __last);
1720 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1721 __glibcxx_requires_valid_range(__result_first, __result_last);
1723 return std::__partial_sort_copy(__first, __last,
1724 __result_first, __result_last,
1725 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1731 template<
typename _RandomAccessIterator,
typename _Compare>
1732 _GLIBCXX20_CONSTEXPR
1734 __unguarded_linear_insert(_RandomAccessIterator __last,
1737 typename iterator_traits<_RandomAccessIterator>::value_type
1738 __val = _GLIBCXX_MOVE(*__last);
1739 _RandomAccessIterator __next = __last;
1741 while (__comp(__val, __next))
1743 *__last = _GLIBCXX_MOVE(*__next);
1747 *__last = _GLIBCXX_MOVE(__val);
1751 template<
typename _RandomAccessIterator,
typename _Compare>
1752 _GLIBCXX20_CONSTEXPR
1754 __insertion_sort(_RandomAccessIterator __first,
1755 _RandomAccessIterator __last, _Compare __comp)
1757 if (__first == __last)
return;
1759 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1761 if (__comp(__i, __first))
1764 __val = _GLIBCXX_MOVE(*__i);
1765 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1766 *__first = _GLIBCXX_MOVE(__val);
1769 std::__unguarded_linear_insert(__i,
1770 __gnu_cxx::__ops::__val_comp_iter(__comp));
1775 template<
typename _RandomAccessIterator,
typename _Compare>
1776 _GLIBCXX20_CONSTEXPR
1778 __unguarded_insertion_sort(_RandomAccessIterator __first,
1779 _RandomAccessIterator __last, _Compare __comp)
1781 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1782 std::__unguarded_linear_insert(__i,
1783 __gnu_cxx::__ops::__val_comp_iter(__comp));
1790 enum { _S_threshold = 16 };
1793 template<
typename _RandomAccessIterator,
typename _Compare>
1794 _GLIBCXX20_CONSTEXPR
1796 __final_insertion_sort(_RandomAccessIterator __first,
1797 _RandomAccessIterator __last, _Compare __comp)
1799 if (__last - __first >
int(_S_threshold))
1801 std::__insertion_sort(__first, __first +
int(_S_threshold), __comp);
1802 std::__unguarded_insertion_sort(__first +
int(_S_threshold), __last,
1806 std::__insertion_sort(__first, __last, __comp);
1810 template<
typename _RandomAccessIterator,
typename _Compare>
1811 _GLIBCXX20_CONSTEXPR
1812 _RandomAccessIterator
1813 __unguarded_partition(_RandomAccessIterator __first,
1814 _RandomAccessIterator __last,
1815 _RandomAccessIterator __pivot, _Compare __comp)
1819 while (__comp(__first, __pivot))
1822 while (__comp(__pivot, __last))
1824 if (!(__first < __last))
1826 std::iter_swap(__first, __last);
1832 template<
typename _RandomAccessIterator,
typename _Compare>
1833 _GLIBCXX20_CONSTEXPR
1834 inline _RandomAccessIterator
1835 __unguarded_partition_pivot(_RandomAccessIterator __first,
1836 _RandomAccessIterator __last, _Compare __comp)
1838 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1841 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1844 template<
typename _RandomAccessIterator,
typename _Compare>
1845 _GLIBCXX20_CONSTEXPR
1847 __partial_sort(_RandomAccessIterator __first,
1848 _RandomAccessIterator __middle,
1849 _RandomAccessIterator __last,
1852 std::__heap_select(__first, __middle, __last, __comp);
1853 std::__sort_heap(__first, __middle, __comp);
1857 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1858 _GLIBCXX20_CONSTEXPR
1860 __introsort_loop(_RandomAccessIterator __first,
1861 _RandomAccessIterator __last,
1862 _Size __depth_limit, _Compare __comp)
1864 while (__last - __first >
int(_S_threshold))
1866 if (__depth_limit == 0)
1868 std::__partial_sort(__first, __last, __last, __comp);
1872 _RandomAccessIterator __cut =
1873 std::__unguarded_partition_pivot(__first, __last, __comp);
1874 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1881 template<
typename _RandomAccessIterator,
typename _Compare>
1882 _GLIBCXX20_CONSTEXPR
1884 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1887 if (__first != __last)
1889 std::__introsort_loop(__first, __last,
1892 std::__final_insertion_sort(__first, __last, __comp);
1896 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1897 _GLIBCXX20_CONSTEXPR
1899 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1900 _RandomAccessIterator __last, _Size __depth_limit,
1903 while (__last - __first > 3)
1905 if (__depth_limit == 0)
1907 std::__heap_select(__first, __nth + 1, __last, __comp);
1909 std::iter_swap(__first, __nth);
1913 _RandomAccessIterator __cut =
1914 std::__unguarded_partition_pivot(__first, __last, __comp);
1920 std::__insertion_sort(__first, __last, __comp);
1944 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1945 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1946 inline _ForwardIterator
1947 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1948 const _Tp& __val, _Compare __comp)
1951 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1952 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1954 __glibcxx_requires_partitioned_lower_pred(__first, __last,
1957 return std::__lower_bound(__first, __last, __val,
1958 __gnu_cxx::__ops::__iter_comp_val(__comp));
1961 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1962 _GLIBCXX20_CONSTEXPR
1964 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
1965 const _Tp& __val, _Compare __comp)
1967 typedef typename iterator_traits<_ForwardIterator>::difference_type
1974 _DistanceType __half = __len >> 1;
1975 _ForwardIterator __middle = __first;
1977 if (__comp(__val, __middle))
1983 __len = __len - __half - 1;
2000 template<
typename _ForwardIterator,
typename _Tp>
2001 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2002 inline _ForwardIterator
2003 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2007 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2008 __glibcxx_function_requires(_LessThanOpConcept<
2010 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2012 return std::__upper_bound(__first, __last, __val,
2013 __gnu_cxx::__ops::__val_less_iter());
2031 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2032 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2033 inline _ForwardIterator
2034 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2035 const _Tp& __val, _Compare __comp)
2038 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2039 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2041 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2044 return std::__upper_bound(__first, __last, __val,
2045 __gnu_cxx::__ops::__val_comp_iter(__comp));
2048 template<
typename _ForwardIterator,
typename _Tp,
2049 typename _CompareItTp,
typename _CompareTpIt>
2050 _GLIBCXX20_CONSTEXPR
2052 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2054 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2056 typedef typename iterator_traits<_ForwardIterator>::difference_type
2063 _DistanceType __half = __len >> 1;
2064 _ForwardIterator __middle = __first;
2066 if (__comp_it_val(__middle, __val))
2070 __len = __len - __half - 1;
2072 else if (__comp_val_it(__val, __middle))
2076 _ForwardIterator __left
2077 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2079 _ForwardIterator __right
2080 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2104 template<
typename _ForwardIterator,
typename _Tp>
2105 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2107 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2111 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2112 __glibcxx_function_requires(_LessThanOpConcept<
2114 __glibcxx_function_requires(_LessThanOpConcept<
2116 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2117 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2119 return std::__equal_range(__first, __last, __val,
2120 __gnu_cxx::__ops::__iter_less_val(),
2121 __gnu_cxx::__ops::__val_less_iter());
2141 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2142 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2144 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2145 const _Tp& __val, _Compare __comp)
2148 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2149 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2151 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2153 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2155 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2158 return std::__equal_range(__first, __last, __val,
2159 __gnu_cxx::__ops::__iter_comp_val(__comp),
2160 __gnu_cxx::__ops::__val_comp_iter(__comp));
2175 template<
typename _ForwardIterator,
typename _Tp>
2176 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2178 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2183 __glibcxx_function_requires(_LessThanOpConcept<
2185 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2186 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2188 _ForwardIterator __i
2189 = std::__lower_bound(__first, __last, __val,
2190 __gnu_cxx::__ops::__iter_less_val());
2191 return __i != __last && !(__val < *__i);
2209 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2210 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2212 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2213 const _Tp& __val, _Compare __comp)
2216 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2217 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2219 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2221 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2224 _ForwardIterator __i
2225 = std::__lower_bound(__first, __last, __val,
2226 __gnu_cxx::__ops::__iter_comp_val(__comp));
2227 return __i != __last && !bool(__comp(__val, *__i));
2233 template<
typename _InputIterator1,
typename _InputIterator2,
2234 typename _OutputIterator,
typename _Compare>
2237 _InputIterator2 __first2, _InputIterator2 __last2,
2238 _OutputIterator __result, _Compare __comp)
2240 while (__first1 != __last1 && __first2 != __last2)
2242 if (__comp(__first2, __first1))
2244 *__result = _GLIBCXX_MOVE(*__first2);
2249 *__result = _GLIBCXX_MOVE(*__first1);
2254 if (__first1 != __last1)
2255 _GLIBCXX_MOVE3(__first1, __last1, __result);
2259 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2260 typename _BidirectionalIterator3,
typename _Compare>
2263 _BidirectionalIterator1 __last1,
2264 _BidirectionalIterator2 __first2,
2265 _BidirectionalIterator2 __last2,
2266 _BidirectionalIterator3 __result,
2269 if (__first1 == __last1)
2271 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2274 else if (__first2 == __last2)
2281 if (__comp(__last2, __last1))
2283 *--__result = _GLIBCXX_MOVE(*__last1);
2284 if (__first1 == __last1)
2286 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2293 *--__result = _GLIBCXX_MOVE(*__last2);
2294 if (__first2 == __last2)
2302 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2304 _BidirectionalIterator1
2306 _BidirectionalIterator1 __middle,
2307 _BidirectionalIterator1 __last,
2308 _Distance __len1, _Distance __len2,
2309 _BidirectionalIterator2 __buffer,
2310 _Distance __buffer_size)
2312 _BidirectionalIterator2 __buffer_end;
2313 if (__len1 > __len2 && __len2 <= __buffer_size)
2317 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2318 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2319 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2324 else if (__len1 <= __buffer_size)
2328 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2329 _GLIBCXX_MOVE3(__middle, __last, __first);
2330 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2336 return std::rotate(__first, __middle, __last);
2340 template<
typename _BidirectionalIterator,
typename _Distance,
2341 typename _Pointer,
typename _Compare>
2344 _BidirectionalIterator __middle,
2345 _BidirectionalIterator __last,
2346 _Distance __len1, _Distance __len2,
2347 _Pointer __buffer, _Compare __comp)
2349 if (__len1 <= __len2)
2351 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2357 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2359 __buffer_end, __last, __comp);
2363 template<
typename _BidirectionalIterator,
typename _Distance,
2364 typename _Pointer,
typename _Compare>
2366 __merge_adaptive_resize(_BidirectionalIterator __first,
2367 _BidirectionalIterator __middle,
2368 _BidirectionalIterator __last,
2369 _Distance __len1, _Distance __len2,
2370 _Pointer __buffer, _Distance __buffer_size,
2373 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2375 __len1, __len2, __buffer, __comp);
2378 _BidirectionalIterator __first_cut = __first;
2379 _BidirectionalIterator __second_cut = __middle;
2380 _Distance __len11 = 0;
2381 _Distance __len22 = 0;
2382 if (__len1 > __len2)
2384 __len11 = __len1 / 2;
2387 = std::__lower_bound(__middle, __last, *__first_cut,
2388 __gnu_cxx::__ops::__iter_comp_val(__comp));
2393 __len22 = __len2 / 2;
2396 = std::__upper_bound(__first, __middle, *__second_cut,
2397 __gnu_cxx::__ops::__val_comp_iter(__comp));
2401 _BidirectionalIterator __new_middle
2403 _Distance(__len1 - __len11), __len22,
2404 __buffer, __buffer_size);
2405 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2407 __buffer, __buffer_size, __comp);
2408 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2409 _Distance(__len1 - __len11),
2410 _Distance(__len2 - __len22),
2411 __buffer, __buffer_size, __comp);
2416 template<
typename _BidirectionalIterator,
typename _Distance,
2418 _GLIBCXX26_CONSTEXPR
2421 _BidirectionalIterator __middle,
2422 _BidirectionalIterator __last,
2423 _Distance __len1, _Distance __len2,
2426 if (__len1 == 0 || __len2 == 0)
2429 if (__len1 + __len2 == 2)
2431 if (__comp(__middle, __first))
2432 std::iter_swap(__first, __middle);
2436 _BidirectionalIterator __first_cut = __first;
2437 _BidirectionalIterator __second_cut = __middle;
2438 _Distance __len11 = 0;
2439 _Distance __len22 = 0;
2440 if (__len1 > __len2)
2442 __len11 = __len1 / 2;
2445 = std::__lower_bound(__middle, __last, *__first_cut,
2446 __gnu_cxx::__ops::__iter_comp_val(__comp));
2451 __len22 = __len2 / 2;
2454 = std::__upper_bound(__first, __middle, *__second_cut,
2455 __gnu_cxx::__ops::__val_comp_iter(__comp));
2459 _BidirectionalIterator __new_middle
2460 = std::rotate(__first_cut, __middle, __second_cut);
2462 __len11, __len22, __comp);
2464 __len1 - __len11, __len2 - __len22, __comp);
2467 template<
typename _B
idirectionalIterator,
typename _Compare>
2469 __inplace_merge(_BidirectionalIterator __first,
2470 _BidirectionalIterator __middle,
2471 _BidirectionalIterator __last,
2474 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2476 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2479 if (__first == __middle || __middle == __last)
2482 const _DistanceType __len1 =
std::distance(__first, __middle);
2483 const _DistanceType __len2 =
std::distance(__middle, __last);
2486 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2489 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2491 if (__builtin_expect(__buf.size() == __buf.requested_size(),
true))
2493 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2494 else if (__builtin_expect(__buf.begin() == 0,
false))
2496 (__first, __middle, __last, __len1, __len2, __comp);
2498 std::__merge_adaptive_resize
2499 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2500 _DistanceType(__buf.size()), __comp);
2503 (__first, __middle, __last, __len1, __len2, __comp);
2525 template<
typename _B
idirectionalIterator>
2527 inplace_merge(_BidirectionalIterator __first,
2528 _BidirectionalIterator __middle,
2529 _BidirectionalIterator __last)
2532 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2533 _BidirectionalIterator>)
2534 __glibcxx_function_requires(_LessThanComparableConcept<
2536 __glibcxx_requires_sorted(__first, __middle);
2537 __glibcxx_requires_sorted(__middle, __last);
2538 __glibcxx_requires_irreflexive(__first, __last);
2540 std::__inplace_merge(__first, __middle, __last,
2541 __gnu_cxx::__ops::__iter_less_iter());
2566 template<
typename _B
idirectionalIterator,
typename _Compare>
2568 inplace_merge(_BidirectionalIterator __first,
2569 _BidirectionalIterator __middle,
2570 _BidirectionalIterator __last,
2574 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2575 _BidirectionalIterator>)
2576 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2579 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2580 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2581 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2583 std::__inplace_merge(__first, __middle, __last,
2584 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2589 template<
typename _InputIterator,
typename _OutputIterator,
2593 _InputIterator __first2, _InputIterator __last2,
2594 _OutputIterator __result, _Compare __comp)
2596 while (__first1 != __last1 && __first2 != __last2)
2598 if (__comp(__first2, __first1))
2600 *__result = _GLIBCXX_MOVE(*__first2);
2605 *__result = _GLIBCXX_MOVE(*__first1);
2610 return _GLIBCXX_MOVE3(__first2, __last2,
2611 _GLIBCXX_MOVE3(__first1, __last1,
2615 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2616 typename _Distance,
typename _Compare>
2618 __merge_sort_loop(_RandomAccessIterator1 __first,
2619 _RandomAccessIterator1 __last,
2620 _RandomAccessIterator2 __result, _Distance __step_size,
2623 const _Distance __two_step = 2 * __step_size;
2625 while (__last - __first >= __two_step)
2628 __first + __step_size,
2629 __first + __two_step,
2631 __first += __two_step;
2633 __step_size =
std::min(_Distance(__last - __first), __step_size);
2636 __first + __step_size, __last, __result, __comp);
2639 template<
typename _RandomAccessIterator,
typename _Distance,
2641 _GLIBCXX20_CONSTEXPR
2643 __chunk_insertion_sort(_RandomAccessIterator __first,
2644 _RandomAccessIterator __last,
2645 _Distance __chunk_size, _Compare __comp)
2647 while (__last - __first >= __chunk_size)
2649 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2650 __first += __chunk_size;
2652 std::__insertion_sort(__first, __last, __comp);
2655 enum { _S_chunk_size = 7 };
2657 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2659 __merge_sort_with_buffer(_RandomAccessIterator __first,
2660 _RandomAccessIterator __last,
2661 _Pointer __buffer, _Compare __comp)
2666 const _Distance __len = __last - __first;
2667 const _Pointer __buffer_last = __buffer + __len;
2669 _Distance __step_size = _S_chunk_size;
2670 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2672 while (__step_size < __len)
2674 std::__merge_sort_loop(__first, __last, __buffer,
2675 __step_size, __comp);
2677 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2678 __step_size, __comp);
2683 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2685 __stable_sort_adaptive(_RandomAccessIterator __first,
2686 _RandomAccessIterator __middle,
2687 _RandomAccessIterator __last,
2688 _Pointer __buffer, _Compare __comp)
2690 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2691 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2694 __middle - __first, __last - __middle,
2698 template<
typename _RandomAccessIterator,
typename _Pointer,
2699 typename _Distance,
typename _Compare>
2701 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2702 _RandomAccessIterator __last,
2703 _Pointer __buffer, _Distance __buffer_size,
2706 const _Distance __len = (__last - __first + 1) / 2;
2707 const _RandomAccessIterator __middle = __first + __len;
2708 if (__len > __buffer_size)
2710 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2711 __buffer_size, __comp);
2712 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2713 __buffer_size, __comp);
2714 std::__merge_adaptive_resize(__first, __middle, __last,
2715 _Distance(__middle - __first),
2716 _Distance(__last - __middle),
2717 __buffer, __buffer_size,
2721 std::__stable_sort_adaptive(__first, __middle, __last,
2726 template<
typename _RandomAccessIterator,
typename _Compare>
2727 _GLIBCXX26_CONSTEXPR
2730 _RandomAccessIterator __last, _Compare __comp)
2732 if (__last - __first < 15)
2734 std::__insertion_sort(__first, __last, __comp);
2737 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2753 template<
typename _InputIterator1,
typename _InputIterator2,
2755 _GLIBCXX20_CONSTEXPR
2757 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2758 _InputIterator2 __first2, _InputIterator2 __last2,
2761 while (__first1 != __last1 && __first2 != __last2)
2763 if (__comp(__first2, __first1))
2765 if (!__comp(__first1, __first2))
2770 return __first2 == __last2;
2791 template<
typename _InputIterator1,
typename _InputIterator2>
2792 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2794 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2795 _InputIterator2 __first2, _InputIterator2 __last2)
2798 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2799 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2800 __glibcxx_function_requires(_LessThanOpConcept<
2803 __glibcxx_function_requires(_LessThanOpConcept<
2806 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2807 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2808 __glibcxx_requires_irreflexive2(__first1, __last1);
2809 __glibcxx_requires_irreflexive2(__first2, __last2);
2811 return std::__includes(__first1, __last1, __first2, __last2,
2812 __gnu_cxx::__ops::__iter_less_iter());
2836 template<
typename _InputIterator1,
typename _InputIterator2,
2838 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2840 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2841 _InputIterator2 __first2, _InputIterator2 __last2,
2845 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2846 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2847 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2850 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2853 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2854 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2855 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2856 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2858 return std::__includes(__first1, __last1, __first2, __last2,
2859 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2872 template<
typename _B
idirectionalIterator,
typename _Compare>
2873 _GLIBCXX20_CONSTEXPR
2875 __next_permutation(_BidirectionalIterator __first,
2876 _BidirectionalIterator __last, _Compare __comp)
2878 if (__first == __last)
2880 _BidirectionalIterator __i = __first;
2889 _BidirectionalIterator __ii = __i;
2891 if (__comp(__i, __ii))
2893 _BidirectionalIterator __j = __last;
2894 while (!__comp(__i, --__j))
2896 std::iter_swap(__i, __j);
2922 template<
typename _B
idirectionalIterator>
2923 _GLIBCXX20_CONSTEXPR
2925 next_permutation(_BidirectionalIterator __first,
2926 _BidirectionalIterator __last)
2929 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2930 _BidirectionalIterator>)
2931 __glibcxx_function_requires(_LessThanComparableConcept<
2933 __glibcxx_requires_valid_range(__first, __last);
2934 __glibcxx_requires_irreflexive(__first, __last);
2936 return std::__next_permutation
2937 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2955 template<
typename _B
idirectionalIterator,
typename _Compare>
2956 _GLIBCXX20_CONSTEXPR
2958 next_permutation(_BidirectionalIterator __first,
2959 _BidirectionalIterator __last, _Compare __comp)
2962 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2963 _BidirectionalIterator>)
2964 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2967 __glibcxx_requires_valid_range(__first, __last);
2968 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2970 return std::__next_permutation
2971 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2974 template<
typename _B
idirectionalIterator,
typename _Compare>
2975 _GLIBCXX20_CONSTEXPR
2977 __prev_permutation(_BidirectionalIterator __first,
2978 _BidirectionalIterator __last, _Compare __comp)
2980 if (__first == __last)
2982 _BidirectionalIterator __i = __first;
2991 _BidirectionalIterator __ii = __i;
2993 if (__comp(__ii, __i))
2995 _BidirectionalIterator __j = __last;
2996 while (!__comp(--__j, __i))
2998 std::iter_swap(__i, __j);
3025 template<
typename _B
idirectionalIterator>
3026 _GLIBCXX20_CONSTEXPR
3028 prev_permutation(_BidirectionalIterator __first,
3029 _BidirectionalIterator __last)
3032 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3033 _BidirectionalIterator>)
3034 __glibcxx_function_requires(_LessThanComparableConcept<
3036 __glibcxx_requires_valid_range(__first, __last);
3037 __glibcxx_requires_irreflexive(__first, __last);
3039 return std::__prev_permutation(__first, __last,
3040 __gnu_cxx::__ops::__iter_less_iter());
3058 template<
typename _B
idirectionalIterator,
typename _Compare>
3059 _GLIBCXX20_CONSTEXPR
3061 prev_permutation(_BidirectionalIterator __first,
3062 _BidirectionalIterator __last, _Compare __comp)
3065 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3066 _BidirectionalIterator>)
3067 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3070 __glibcxx_requires_valid_range(__first, __last);
3071 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3073 return std::__prev_permutation(__first, __last,
3074 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3080 template<
typename _InputIterator,
typename _OutputIterator,
3081 typename _Predicate,
typename _Tp>
3082 _GLIBCXX20_CONSTEXPR
3084 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3085 _OutputIterator __result,
3086 _Predicate __pred,
const _Tp& __new_value)
3088 for (; __first != __last; ++__first, (void)++__result)
3089 if (__pred(__first))
3090 *__result = __new_value;
3092 *__result = *__first;
3110 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3111 _GLIBCXX20_CONSTEXPR
3112 inline _OutputIterator
3113 replace_copy(_InputIterator __first, _InputIterator __last,
3114 _OutputIterator __result,
3115 const _Tp& __old_value,
const _Tp& __new_value)
3118 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3119 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3121 __glibcxx_function_requires(_EqualOpConcept<
3123 __glibcxx_requires_valid_range(__first, __last);
3125 return std::__replace_copy_if(__first, __last, __result,
3126 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3145 template<
typename _InputIterator,
typename _OutputIterator,
3146 typename _Predicate,
typename _Tp>
3147 _GLIBCXX20_CONSTEXPR
3148 inline _OutputIterator
3149 replace_copy_if(_InputIterator __first, _InputIterator __last,
3150 _OutputIterator __result,
3151 _Predicate __pred,
const _Tp& __new_value)
3154 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3155 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3157 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3159 __glibcxx_requires_valid_range(__first, __last);
3161 return std::__replace_copy_if(__first, __last, __result,
3162 __gnu_cxx::__ops::__pred_iter(__pred),
3166#if __cplusplus >= 201103L
3174 template<
typename _ForwardIterator>
3175 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3177 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3178 {
return std::is_sorted_until(__first, __last) == __last; }
3189 template<
typename _ForwardIterator,
typename _Compare>
3190 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3192 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3194 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3196 template<
typename _ForwardIterator,
typename _Compare>
3197 _GLIBCXX20_CONSTEXPR
3199 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3202 if (__first == __last)
3205 _ForwardIterator __next = __first;
3206 for (++__next; __next != __last; __first = __next, (void)++__next)
3207 if (__comp(__next, __first))
3220 template<
typename _ForwardIterator>
3221 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3222 inline _ForwardIterator
3223 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3226 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3227 __glibcxx_function_requires(_LessThanComparableConcept<
3229 __glibcxx_requires_valid_range(__first, __last);
3230 __glibcxx_requires_irreflexive(__first, __last);
3232 return std::__is_sorted_until(__first, __last,
3233 __gnu_cxx::__ops::__iter_less_iter());
3245 template<
typename _ForwardIterator,
typename _Compare>
3246 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3247 inline _ForwardIterator
3248 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3253 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3256 __glibcxx_requires_valid_range(__first, __last);
3257 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3259 return std::__is_sorted_until(__first, __last,
3260 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3271 template<
typename _Tp>
3272 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3277 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3279 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3292 template<
typename _Tp,
typename _Compare>
3293 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3295 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3301 template<
typename _ForwardIterator,
typename _Compare>
3302 _GLIBCXX14_CONSTEXPR
3304 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3307 _ForwardIterator __next = __first;
3308 if (__first == __last
3309 || ++__next == __last)
3312 _ForwardIterator __min{}, __max{};
3313 if (__comp(__next, __first))
3327 while (__first != __last)
3330 if (++__next == __last)
3332 if (__comp(__first, __min))
3334 else if (!__comp(__first, __max))
3339 if (__comp(__next, __first))
3341 if (__comp(__next, __min))
3343 if (!__comp(__first, __max))
3348 if (__comp(__first, __min))
3350 if (!__comp(__next, __max))
3372 template<
typename _ForwardIterator>
3373 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3375 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3378 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3379 __glibcxx_function_requires(_LessThanComparableConcept<
3381 __glibcxx_requires_valid_range(__first, __last);
3382 __glibcxx_requires_irreflexive(__first, __last);
3384 return std::__minmax_element(__first, __last,
3385 __gnu_cxx::__ops::__iter_less_iter());
3400 template<
typename _ForwardIterator,
typename _Compare>
3401 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3403 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3407 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3408 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3411 __glibcxx_requires_valid_range(__first, __last);
3412 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3414 return std::__minmax_element(__first, __last,
3415 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3418 template<
typename _Tp>
3419 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3420 inline pair<_Tp, _Tp>
3421 minmax(initializer_list<_Tp> __l)
3423 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3425 std::__minmax_element(__l.begin(), __l.end(),
3426 __gnu_cxx::__ops::__iter_less_iter());
3430 template<
typename _Tp,
typename _Compare>
3431 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3435 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3437 std::__minmax_element(__l.begin(), __l.end(),
3438 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3456 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3457 typename _BinaryPredicate>
3458 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3460 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3461 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3464 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3465 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3466 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3469 __glibcxx_requires_valid_range(__first1, __last1);
3471 return std::__is_permutation(__first1, __last1, __first2,
3472 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3475#if __cplusplus > 201103L
3476#pragma GCC diagnostic push
3477#pragma GCC diagnostic ignored "-Wc++17-extensions"
3478 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3479 typename _BinaryPredicate>
3480 _GLIBCXX20_CONSTEXPR
3482 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3483 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3484 _BinaryPredicate __pred)
3487 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3489 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3490 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3491 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3492 constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
3493 if constexpr (__ra_iters)
3495 if ((__last1 - __first1) != (__last2 - __first2))
3501 for (; __first1 != __last1 && __first2 != __last2;
3502 ++__first1, (void)++__first2)
3503 if (!__pred(__first1, __first2))
3506 if constexpr (__ra_iters)
3508 if (__first1 == __last1)
3515 if (__d1 == 0 && __d2 == 0)
3521 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3523 if (__scan != std::__find_if(__first1, __scan,
3524 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3527 auto __matches = std::__count_if(__first2, __last2,
3528 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3530 || std::__count_if(__scan, __last1,
3531 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3537#pragma GCC diagnostic pop
3552 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3553 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3555 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3556 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3558 __glibcxx_requires_valid_range(__first1, __last1);
3559 __glibcxx_requires_valid_range(__first2, __last2);
3562 std::__is_permutation(__first1, __last1, __first2, __last2,
3563 __gnu_cxx::__ops::__iter_equal_to_iter());
3580 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3581 typename _BinaryPredicate>
3582 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3584 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3585 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3586 _BinaryPredicate __pred)
3588 __glibcxx_requires_valid_range(__first1, __last1);
3589 __glibcxx_requires_valid_range(__first2, __last2);
3591 return std::__is_permutation(__first1, __last1, __first2, __last2,
3592 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3596#ifdef __glibcxx_clamp
3608 template<
typename _Tp>
3609 [[nodiscard]]
constexpr const _Tp&
3610 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3612 __glibcxx_assert(!(__hi < __lo));
3628 template<
typename _Tp,
typename _Compare>
3629 [[nodiscard]]
constexpr const _Tp&
3630 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3632 __glibcxx_assert(!__comp(__hi, __lo));
3658 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3661 _UniformRandomBitGenerator&& __g)
3680 template<
typename _RandomAccessIterator,
3681 typename _UniformRandomNumberGenerator>
3683 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3684 _UniformRandomNumberGenerator&& __g)
3687 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3688 _RandomAccessIterator>)
3689 __glibcxx_requires_valid_range(__first, __last);
3691 if (__first == __last)
3697 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3699 typedef typename __distr_type::param_type __p_type;
3701 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3706 const __uc_type __urngrange = __g.max() - __g.min();
3707 const __uc_type __urange = __uc_type(__last - __first);
3709 if (__urngrange / __urange >= __urange)
3712 _RandomAccessIterator __i = __first + 1;
3718 if ((__urange % 2) == 0)
3720 __distr_type __d{0, 1};
3721 std::iter_swap(__i++, __first + __d(__g));
3728 while (__i != __last)
3730 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3735 std::iter_swap(__i++, __first + __pospos.
first);
3736 std::iter_swap(__i++, __first + __pospos.
second);
3744 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3745 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3749_GLIBCXX_BEGIN_NAMESPACE_ALGO
3763 template<
typename _InputIterator,
typename _Function>
3764 _GLIBCXX20_CONSTEXPR
3766 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3769 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3770 __glibcxx_requires_valid_range(__first, __last);
3771 for (; __first != __last; ++__first)
3776#if __cplusplus >= 201703L
3789 template<
typename _InputIterator,
typename _Size,
typename _Function>
3790 _GLIBCXX20_CONSTEXPR
3794 auto __n2 = std::__size_to_integer(__n);
3796 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3800 auto __last = __first + __n2;
3801 std::for_each(__first, __last,
std::move(__f));
3825 template<
typename _InputIterator,
typename _Tp>
3826 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3827 inline _InputIterator
3828 find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
3831 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3832 __glibcxx_function_requires(_EqualOpConcept<
3834 __glibcxx_requires_valid_range(__first, __last);
3836#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
3838 if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
3839 if constexpr (is_pointer_v<
decltype(std::__niter_base(__first))>
3840#
if __glibcxx_concepts && __glibcxx_to_address
3841 || contiguous_iterator<_InputIterator>
3849 if (!(
static_cast<_ValT
>(__val) == __val))
3851 else if (!__is_constant_evaluated())
3853 const int __ival =
static_cast<int>(__val);
3854 if (
auto __n = __last - __first; __n > 0)
3856#if __glibcxx_concepts && __glibcxx_to_address
3859 const void* __p0 = std::__niter_base(__first);
3861 if (
auto __p1 = __builtin_memchr(__p0, __ival, __n))
3862 return __first + ((
const char*)__p1 - (
const char*)__p0);
3869 return std::__find_if(__first, __last,
3870 __gnu_cxx::__ops::__iter_equals_val(__val));
3883 template<
typename _InputIterator,
typename _Predicate>
3884 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3885 inline _InputIterator
3886 find_if(_InputIterator __first, _InputIterator __last,
3890 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3891 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3893 __glibcxx_requires_valid_range(__first, __last);
3895 return std::__find_if(__first, __last,
3896 __gnu_cxx::__ops::__pred_iter(__pred));
3915 template<
typename _InputIterator,
typename _ForwardIterator>
3916 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3918 find_first_of(_InputIterator __first1, _InputIterator __last1,
3919 _ForwardIterator __first2, _ForwardIterator __last2)
3922 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3923 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3924 __glibcxx_function_requires(_EqualOpConcept<
3927 __glibcxx_requires_valid_range(__first1, __last1);
3928 __glibcxx_requires_valid_range(__first2, __last2);
3930 for (; __first1 != __last1; ++__first1)
3931 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3932 if (*__first1 == *__iter)
3956 template<
typename _InputIterator,
typename _ForwardIterator,
3957 typename _BinaryPredicate>
3958 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3960 find_first_of(_InputIterator __first1, _InputIterator __last1,
3961 _ForwardIterator __first2, _ForwardIterator __last2,
3962 _BinaryPredicate __comp)
3965 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3966 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3967 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3970 __glibcxx_requires_valid_range(__first1, __last1);
3971 __glibcxx_requires_valid_range(__first2, __last2);
3973 for (; __first1 != __last1; ++__first1)
3974 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3975 if (__comp(*__first1, *__iter))
3989 template<
typename _ForwardIterator>
3990 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3991 inline _ForwardIterator
3992 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3995 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3996 __glibcxx_function_requires(_EqualityComparableConcept<
3998 __glibcxx_requires_valid_range(__first, __last);
4000 return std::__adjacent_find(__first, __last,
4001 __gnu_cxx::__ops::__iter_equal_to_iter());
4015 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4016 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4017 inline _ForwardIterator
4018 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4019 _BinaryPredicate __binary_pred)
4022 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4023 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4026 __glibcxx_requires_valid_range(__first, __last);
4028 return std::__adjacent_find(__first, __last,
4029 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4041 template<
typename _InputIterator,
typename _Tp>
4042 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4043 inline typename iterator_traits<_InputIterator>::difference_type
4044 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4047 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4048 __glibcxx_function_requires(_EqualOpConcept<
4050 __glibcxx_requires_valid_range(__first, __last);
4052 return std::__count_if(__first, __last,
4053 __gnu_cxx::__ops::__iter_equals_val(__value));
4065 template<
typename _InputIterator,
typename _Predicate>
4066 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4067 inline typename iterator_traits<_InputIterator>::difference_type
4068 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4071 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4072 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4074 __glibcxx_requires_valid_range(__first, __last);
4076 return std::__count_if(__first, __last,
4077 __gnu_cxx::__ops::__pred_iter(__pred));
4106 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4107 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4108 inline _ForwardIterator1
4109 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4110 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4113 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4114 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4115 __glibcxx_function_requires(_EqualOpConcept<
4118 __glibcxx_requires_valid_range(__first1, __last1);
4119 __glibcxx_requires_valid_range(__first2, __last2);
4121 return std::__search(__first1, __last1, __first2, __last2,
4122 __gnu_cxx::__ops::__iter_equal_to_iter());
4140 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4141 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4142 inline _ForwardIterator
4143 search_n(_ForwardIterator __first, _ForwardIterator __last,
4144 _Integer __count,
const _Tp& __val)
4147 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4148 __glibcxx_function_requires(_EqualOpConcept<
4150 __glibcxx_requires_valid_range(__first, __last);
4152 return std::__search_n(__first, __last, __count,
4153 __gnu_cxx::__ops::__iter_equals_val(__val));
4174 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4175 typename _BinaryPredicate>
4176 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4177 inline _ForwardIterator
4178 search_n(_ForwardIterator __first, _ForwardIterator __last,
4179 _Integer __count,
const _Tp& __val,
4180 _BinaryPredicate __binary_pred)
4183 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4184 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4186 __glibcxx_requires_valid_range(__first, __last);
4188 return std::__search_n(__first, __last, __count,
4189 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4192#if __cplusplus >= 201703L
4200 template<
typename _ForwardIterator,
typename _Searcher>
4201 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4202 inline _ForwardIterator
4203 search(_ForwardIterator __first, _ForwardIterator __last,
4204 const _Searcher& __searcher)
4205 {
return __searcher(__first, __last).first; }
4224 template<
typename _InputIterator,
typename _OutputIterator,
4225 typename _UnaryOperation>
4226 _GLIBCXX20_CONSTEXPR
4228 transform(_InputIterator __first, _InputIterator __last,
4229 _OutputIterator __result, _UnaryOperation __unary_op)
4232 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4233 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4235 __typeof__(__unary_op(*__first))>)
4236 __glibcxx_requires_valid_range(__first, __last);
4238 for (; __first != __last; ++__first, (void)++__result)
4239 *__result = __unary_op(*__first);
4262 template<
typename _InputIterator1,
typename _InputIterator2,
4263 typename _OutputIterator,
typename _BinaryOperation>
4264 _GLIBCXX20_CONSTEXPR
4266 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4267 _InputIterator2 __first2, _OutputIterator __result,
4268 _BinaryOperation __binary_op)
4271 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4272 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4273 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4275 __typeof__(__binary_op(*__first1,*__first2))>)
4276 __glibcxx_requires_valid_range(__first1, __last1);
4278 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4279 *__result = __binary_op(*__first1, *__first2);
4296 template<
typename _ForwardIterator,
typename _Tp>
4297 _GLIBCXX20_CONSTEXPR
4299 replace(_ForwardIterator __first, _ForwardIterator __last,
4300 const _Tp& __old_value,
const _Tp& __new_value)
4303 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4305 __glibcxx_function_requires(_EqualOpConcept<
4307 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4309 __glibcxx_requires_valid_range(__first, __last);
4311 for (; __first != __last; ++__first)
4312 if (*__first == __old_value)
4313 *__first = __new_value;
4329 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4330 _GLIBCXX20_CONSTEXPR
4332 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4333 _Predicate __pred,
const _Tp& __new_value)
4336 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4338 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4340 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4342 __glibcxx_requires_valid_range(__first, __last);
4344 for (; __first != __last; ++__first)
4345 if (__pred(*__first))
4346 *__first = __new_value;
4361 template<
typename _ForwardIterator,
typename _Generator>
4362 _GLIBCXX20_CONSTEXPR
4364 generate(_ForwardIterator __first, _ForwardIterator __last,
4368 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4369 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4371 __glibcxx_requires_valid_range(__first, __last);
4373 for (; __first != __last; ++__first)
4394 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4395 _GLIBCXX20_CONSTEXPR
4397 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4400 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4402 __typeof__(__gen())>)
4404 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4405 for (_IntSize __niter = std::__size_to_integer(__n);
4406 __niter > 0; --__niter, (void) ++__first)
4429 template<
typename _InputIterator,
typename _OutputIterator>
4430 _GLIBCXX20_CONSTEXPR
4431 inline _OutputIterator
4432 unique_copy(_InputIterator __first, _InputIterator __last,
4433 _OutputIterator __result)
4436 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4437 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4439 __glibcxx_function_requires(_EqualityComparableConcept<
4441 __glibcxx_requires_valid_range(__first, __last);
4443 if (__first == __last)
4446 __gnu_cxx::__ops::__iter_equal_to_iter(),
4469 template<
typename _InputIterator,
typename _OutputIterator,
4470 typename _BinaryPredicate>
4471 _GLIBCXX20_CONSTEXPR
4472 inline _OutputIterator
4473 unique_copy(_InputIterator __first, _InputIterator __last,
4474 _OutputIterator __result,
4475 _BinaryPredicate __binary_pred)
4478 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4479 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4481 __glibcxx_requires_valid_range(__first, __last);
4483 if (__first == __last)
4486 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4491#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4508 template<
typename _RandomAccessIterator>
4509 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4511 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4514 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4515 _RandomAccessIterator>)
4516 __glibcxx_requires_valid_range(__first, __last);
4518 if (__first == __last)
4521#if RAND_MAX < __INT_MAX__
4522 if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
4527 = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
4528 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4531 __xss ^= __xss << 13;
4532 __xss ^= __xss >> 17;
4533 __xss ^= __xss << 5;
4534 _RandomAccessIterator __j = __first
4535 + (__xss % ((__i - __first) + 1));
4537 std::iter_swap(__i, __j);
4543 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4546 _RandomAccessIterator __j = __first
4547 + (std::rand() % ((__i - __first) + 1));
4549 std::iter_swap(__i, __j);
4571 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4572 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4574 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4575#if __cplusplus >= 201103L
4576 _RandomNumberGenerator&& __rand)
4578 _RandomNumberGenerator& __rand)
4582 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4583 _RandomAccessIterator>)
4584 __glibcxx_requires_valid_range(__first, __last);
4586 if (__first == __last)
4588 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4590 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4592 std::iter_swap(__i, __j);
4613 template<
typename _ForwardIterator,
typename _Predicate>
4614 _GLIBCXX20_CONSTEXPR
4615 inline _ForwardIterator
4616 partition(_ForwardIterator __first, _ForwardIterator __last,
4620 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4622 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4624 __glibcxx_requires_valid_range(__first, __last);
4648 template<
typename _RandomAccessIterator>
4649 _GLIBCXX20_CONSTEXPR
4651 partial_sort(_RandomAccessIterator __first,
4652 _RandomAccessIterator __middle,
4653 _RandomAccessIterator __last)
4656 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4657 _RandomAccessIterator>)
4658 __glibcxx_function_requires(_LessThanComparableConcept<
4660 __glibcxx_requires_valid_range(__first, __middle);
4661 __glibcxx_requires_valid_range(__middle, __last);
4662 __glibcxx_requires_irreflexive(__first, __last);
4664 std::__partial_sort(__first, __middle, __last,
4665 __gnu_cxx::__ops::__iter_less_iter());
4687 template<
typename _RandomAccessIterator,
typename _Compare>
4688 _GLIBCXX20_CONSTEXPR
4690 partial_sort(_RandomAccessIterator __first,
4691 _RandomAccessIterator __middle,
4692 _RandomAccessIterator __last,
4696 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4697 _RandomAccessIterator>)
4698 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4701 __glibcxx_requires_valid_range(__first, __middle);
4702 __glibcxx_requires_valid_range(__middle, __last);
4703 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4705 std::__partial_sort(__first, __middle, __last,
4706 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4724 template<
typename _RandomAccessIterator>
4725 _GLIBCXX20_CONSTEXPR
4727 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4728 _RandomAccessIterator __last)
4731 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4732 _RandomAccessIterator>)
4733 __glibcxx_function_requires(_LessThanComparableConcept<
4735 __glibcxx_requires_valid_range(__first, __nth);
4736 __glibcxx_requires_valid_range(__nth, __last);
4737 __glibcxx_requires_irreflexive(__first, __last);
4739 if (__first == __last || __nth == __last)
4742 std::__introselect(__first, __nth, __last,
4744 __gnu_cxx::__ops::__iter_less_iter());
4764 template<
typename _RandomAccessIterator,
typename _Compare>
4765 _GLIBCXX20_CONSTEXPR
4767 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4768 _RandomAccessIterator __last, _Compare __comp)
4771 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4772 _RandomAccessIterator>)
4773 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4776 __glibcxx_requires_valid_range(__first, __nth);
4777 __glibcxx_requires_valid_range(__nth, __last);
4778 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4780 if (__first == __last || __nth == __last)
4783 std::__introselect(__first, __nth, __last,
4785 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4802 template<
typename _RandomAccessIterator>
4803 _GLIBCXX20_CONSTEXPR
4805 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4808 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4809 _RandomAccessIterator>)
4810 __glibcxx_function_requires(_LessThanComparableConcept<
4812 __glibcxx_requires_valid_range(__first, __last);
4813 __glibcxx_requires_irreflexive(__first, __last);
4815 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4833 template<
typename _RandomAccessIterator,
typename _Compare>
4834 _GLIBCXX20_CONSTEXPR
4836 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4840 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4841 _RandomAccessIterator>)
4842 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4845 __glibcxx_requires_valid_range(__first, __last);
4846 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4848 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4851 template<
typename _InputIterator1,
typename _InputIterator2,
4852 typename _OutputIterator,
typename _Compare>
4853 _GLIBCXX20_CONSTEXPR
4855 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4856 _InputIterator2 __first2, _InputIterator2 __last2,
4857 _OutputIterator __result, _Compare __comp)
4859 while (__first1 != __last1 && __first2 != __last2)
4861 if (__comp(__first2, __first1))
4863 *__result = *__first2;
4868 *__result = *__first1;
4873 return std::copy(__first2, __last2,
4874 std::copy(__first1, __last1, __result));
4896 template<
typename _InputIterator1,
typename _InputIterator2,
4897 typename _OutputIterator>
4898 _GLIBCXX20_CONSTEXPR
4899 inline _OutputIterator
4900 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4901 _InputIterator2 __first2, _InputIterator2 __last2,
4902 _OutputIterator __result)
4905 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4906 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4907 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4909 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4911 __glibcxx_function_requires(_LessThanOpConcept<
4914 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4915 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4916 __glibcxx_requires_irreflexive2(__first1, __last1);
4917 __glibcxx_requires_irreflexive2(__first2, __last2);
4919 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4920 __first2, __last2, __result,
4921 __gnu_cxx::__ops::__iter_less_iter());
4947 template<
typename _InputIterator1,
typename _InputIterator2,
4948 typename _OutputIterator,
typename _Compare>
4949 _GLIBCXX20_CONSTEXPR
4950 inline _OutputIterator
4951 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4952 _InputIterator2 __first2, _InputIterator2 __last2,
4953 _OutputIterator __result, _Compare __comp)
4956 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4957 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4958 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4960 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4962 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4965 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4966 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4967 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4968 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4970 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4971 __first2, __last2, __result,
4972 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4975 template<
typename _RandomAccessIterator,
typename _Compare>
4976 _GLIBCXX26_CONSTEXPR
4978 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4981 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4983 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4986 if (__first == __last)
4990# if __glibcxx_constexpr_algorithms >= 202306L
4999 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
5001 if (__builtin_expect(__buf.requested_size() == __buf.size(),
true))
5002 std::__stable_sort_adaptive(__first,
5003 __first + _DistanceType(__buf.size()),
5004 __last, __buf.begin(), __comp);
5005 else if (__builtin_expect(__buf.begin() == 0,
false))
5008 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
5009 _DistanceType(__buf.size()), __comp);
5032 template<
typename _RandomAccessIterator>
5033 _GLIBCXX26_CONSTEXPR
5035 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5038 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5039 _RandomAccessIterator>)
5040 __glibcxx_function_requires(_LessThanComparableConcept<
5042 __glibcxx_requires_valid_range(__first, __last);
5043 __glibcxx_requires_irreflexive(__first, __last);
5045 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5046 __gnu_cxx::__ops::__iter_less_iter());
5067 template<
typename _RandomAccessIterator,
typename _Compare>
5068 _GLIBCXX26_CONSTEXPR
5070 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5074 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5075 _RandomAccessIterator>)
5076 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5079 __glibcxx_requires_valid_range(__first, __last);
5080 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5082 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5083 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5086 template<
typename _InputIterator1,
typename _InputIterator2,
5087 typename _OutputIterator,
5089 _GLIBCXX20_CONSTEXPR
5091 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5092 _InputIterator2 __first2, _InputIterator2 __last2,
5093 _OutputIterator __result, _Compare __comp)
5095 while (__first1 != __last1 && __first2 != __last2)
5097 if (__comp(__first1, __first2))
5099 *__result = *__first1;
5102 else if (__comp(__first2, __first1))
5104 *__result = *__first2;
5109 *__result = *__first1;
5115 return std::copy(__first2, __last2,
5116 std::copy(__first1, __last1, __result));
5138 template<
typename _InputIterator1,
typename _InputIterator2,
5139 typename _OutputIterator>
5140 _GLIBCXX20_CONSTEXPR
5141 inline _OutputIterator
5142 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5143 _InputIterator2 __first2, _InputIterator2 __last2,
5144 _OutputIterator __result)
5147 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5148 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5149 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5151 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5153 __glibcxx_function_requires(_LessThanOpConcept<
5156 __glibcxx_function_requires(_LessThanOpConcept<
5159 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5160 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5161 __glibcxx_requires_irreflexive2(__first1, __last1);
5162 __glibcxx_requires_irreflexive2(__first2, __last2);
5164 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5165 __first2, __last2, __result,
5166 __gnu_cxx::__ops::__iter_less_iter());
5189 template<
typename _InputIterator1,
typename _InputIterator2,
5190 typename _OutputIterator,
typename _Compare>
5191 _GLIBCXX20_CONSTEXPR
5192 inline _OutputIterator
5193 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5194 _InputIterator2 __first2, _InputIterator2 __last2,
5195 _OutputIterator __result, _Compare __comp)
5198 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5199 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5200 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5202 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5204 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5207 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5210 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5211 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5212 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5213 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5215 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5216 __first2, __last2, __result,
5217 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5220 template<
typename _InputIterator1,
typename _InputIterator2,
5221 typename _OutputIterator,
5223 _GLIBCXX20_CONSTEXPR
5225 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5226 _InputIterator2 __first2, _InputIterator2 __last2,
5227 _OutputIterator __result, _Compare __comp)
5229 while (__first1 != __last1 && __first2 != __last2)
5230 if (__comp(__first1, __first2))
5232 else if (__comp(__first2, __first1))
5236 *__result = *__first1;
5262 template<
typename _InputIterator1,
typename _InputIterator2,
5263 typename _OutputIterator>
5264 _GLIBCXX20_CONSTEXPR
5265 inline _OutputIterator
5266 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5267 _InputIterator2 __first2, _InputIterator2 __last2,
5268 _OutputIterator __result)
5271 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5272 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5273 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5275 __glibcxx_function_requires(_LessThanOpConcept<
5278 __glibcxx_function_requires(_LessThanOpConcept<
5281 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5282 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5283 __glibcxx_requires_irreflexive2(__first1, __last1);
5284 __glibcxx_requires_irreflexive2(__first2, __last2);
5286 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5287 __first2, __last2, __result,
5288 __gnu_cxx::__ops::__iter_less_iter());
5312 template<
typename _InputIterator1,
typename _InputIterator2,
5313 typename _OutputIterator,
typename _Compare>
5314 _GLIBCXX20_CONSTEXPR
5315 inline _OutputIterator
5316 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5317 _InputIterator2 __first2, _InputIterator2 __last2,
5318 _OutputIterator __result, _Compare __comp)
5321 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5322 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5323 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5325 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5328 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5331 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5332 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5333 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5334 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5336 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5337 __first2, __last2, __result,
5338 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5341 template<
typename _InputIterator1,
typename _InputIterator2,
5342 typename _OutputIterator,
5344 _GLIBCXX20_CONSTEXPR
5346 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5347 _InputIterator2 __first2, _InputIterator2 __last2,
5348 _OutputIterator __result, _Compare __comp)
5350 while (__first1 != __last1 && __first2 != __last2)
5351 if (__comp(__first1, __first2))
5353 *__result = *__first1;
5357 else if (__comp(__first2, __first1))
5364 return std::copy(__first1, __last1, __result);
5387 template<
typename _InputIterator1,
typename _InputIterator2,
5388 typename _OutputIterator>
5389 _GLIBCXX20_CONSTEXPR
5390 inline _OutputIterator
5391 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5392 _InputIterator2 __first2, _InputIterator2 __last2,
5393 _OutputIterator __result)
5396 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5397 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5398 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5400 __glibcxx_function_requires(_LessThanOpConcept<
5403 __glibcxx_function_requires(_LessThanOpConcept<
5406 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5407 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5408 __glibcxx_requires_irreflexive2(__first1, __last1);
5409 __glibcxx_requires_irreflexive2(__first2, __last2);
5411 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5412 __first2, __last2, __result,
5413 __gnu_cxx::__ops::__iter_less_iter());
5439 template<
typename _InputIterator1,
typename _InputIterator2,
5440 typename _OutputIterator,
typename _Compare>
5441 _GLIBCXX20_CONSTEXPR
5442 inline _OutputIterator
5443 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5444 _InputIterator2 __first2, _InputIterator2 __last2,
5445 _OutputIterator __result, _Compare __comp)
5448 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5449 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5450 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5452 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5455 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5458 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5459 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5460 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5461 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5463 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5464 __first2, __last2, __result,
5465 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5468 template<
typename _InputIterator1,
typename _InputIterator2,
5469 typename _OutputIterator,
5471 _GLIBCXX20_CONSTEXPR
5473 __set_symmetric_difference(_InputIterator1 __first1,
5474 _InputIterator1 __last1,
5475 _InputIterator2 __first2,
5476 _InputIterator2 __last2,
5477 _OutputIterator __result,
5480 while (__first1 != __last1 && __first2 != __last2)
5481 if (__comp(__first1, __first2))
5483 *__result = *__first1;
5487 else if (__comp(__first2, __first1))
5489 *__result = *__first2;
5498 return std::copy(__first2, __last2,
5499 std::copy(__first1, __last1, __result));
5520 template<
typename _InputIterator1,
typename _InputIterator2,
5521 typename _OutputIterator>
5522 _GLIBCXX20_CONSTEXPR
5523 inline _OutputIterator
5524 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5525 _InputIterator2 __first2, _InputIterator2 __last2,
5526 _OutputIterator __result)
5529 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5530 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5531 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5533 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5535 __glibcxx_function_requires(_LessThanOpConcept<
5538 __glibcxx_function_requires(_LessThanOpConcept<
5541 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5542 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5543 __glibcxx_requires_irreflexive2(__first1, __last1);
5544 __glibcxx_requires_irreflexive2(__first2, __last2);
5546 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5547 __first2, __last2, __result,
5548 __gnu_cxx::__ops::__iter_less_iter());
5572 template<
typename _InputIterator1,
typename _InputIterator2,
5573 typename _OutputIterator,
typename _Compare>
5574 _GLIBCXX20_CONSTEXPR
5575 inline _OutputIterator
5576 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5577 _InputIterator2 __first2, _InputIterator2 __last2,
5578 _OutputIterator __result,
5582 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5583 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5584 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5586 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5588 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5591 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5594 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5595 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5596 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5597 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5599 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5600 __first2, __last2, __result,
5601 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5604 template<
typename _ForwardIterator,
typename _Compare>
5605 _GLIBCXX14_CONSTEXPR
5607 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5610 if (__first == __last)
5612 _ForwardIterator __result = __first;
5613 while (++__first != __last)
5614 if (__comp(__first, __result))
5626 template<
typename _ForwardIterator>
5627 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5629 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5632 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5633 __glibcxx_function_requires(_LessThanComparableConcept<
5635 __glibcxx_requires_valid_range(__first, __last);
5636 __glibcxx_requires_irreflexive(__first, __last);
5638 return _GLIBCXX_STD_A::__min_element(__first, __last,
5639 __gnu_cxx::__ops::__iter_less_iter());
5651 template<
typename _ForwardIterator,
typename _Compare>
5652 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5653 inline _ForwardIterator
5654 min_element(_ForwardIterator __first, _ForwardIterator __last,
5658 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5659 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5662 __glibcxx_requires_valid_range(__first, __last);
5663 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5665 return _GLIBCXX_STD_A::__min_element(__first, __last,
5666 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5669 template<
typename _ForwardIterator,
typename _Compare>
5670 _GLIBCXX14_CONSTEXPR
5672 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5675 if (__first == __last)
return __first;
5676 _ForwardIterator __result = __first;
5677 while (++__first != __last)
5678 if (__comp(__result, __first))
5690 template<
typename _ForwardIterator>
5691 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5692 inline _ForwardIterator
5693 max_element(_ForwardIterator __first, _ForwardIterator __last)
5696 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5697 __glibcxx_function_requires(_LessThanComparableConcept<
5699 __glibcxx_requires_valid_range(__first, __last);
5700 __glibcxx_requires_irreflexive(__first, __last);
5702 return _GLIBCXX_STD_A::__max_element(__first, __last,
5703 __gnu_cxx::__ops::__iter_less_iter());
5715 template<
typename _ForwardIterator,
typename _Compare>
5716 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5717 inline _ForwardIterator
5718 max_element(_ForwardIterator __first, _ForwardIterator __last,
5722 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5723 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5726 __glibcxx_requires_valid_range(__first, __last);
5727 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5729 return _GLIBCXX_STD_A::__max_element(__first, __last,
5730 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5733#if __cplusplus >= 201103L
5735 template<
typename _Tp>
5736 _GLIBCXX14_CONSTEXPR
5738 min(initializer_list<_Tp> __l)
5740 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5741 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5742 __gnu_cxx::__ops::__iter_less_iter());
5745 template<
typename _Tp,
typename _Compare>
5746 _GLIBCXX14_CONSTEXPR
5750 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5751 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5752 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5755 template<
typename _Tp>
5756 _GLIBCXX14_CONSTEXPR
5760 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5761 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5762 __gnu_cxx::__ops::__iter_less_iter());
5765 template<
typename _Tp,
typename _Compare>
5766 _GLIBCXX14_CONSTEXPR
5770 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5771 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5772 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5776#if __cplusplus >= 201402L
5778 template<
typename _InputIterator,
typename _RandomAccessIterator,
5779 typename _Size,
typename _UniformRandomBitGenerator>
5780 _RandomAccessIterator
5783 _Size __n, _UniformRandomBitGenerator&& __g)
5786 using __param_type =
typename __distrib_type::param_type;
5787 __distrib_type __d{};
5788 _Size __sample_sz = 0;
5789 while (__first != __last && __sample_sz != __n)
5791 __out[__sample_sz++] = *__first;
5794 for (
auto __pop_sz = __sample_sz; __first != __last;
5795 ++__first, (void) ++__pop_sz)
5797 const auto __k = __d(__g, __param_type{0, __pop_sz});
5799 __out[__k] = *__first;
5801 return __out + __sample_sz;
5805 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5806 typename _Size,
typename _UniformRandomBitGenerator>
5808 __sample(_ForwardIterator __first, _ForwardIterator __last,
5810 _OutputIterator __out, _Cat,
5811 _Size __n, _UniformRandomBitGenerator&& __g)
5814 using __param_type =
typename __distrib_type::param_type;
5819 if (__first == __last)
5822 __distrib_type __d{};
5824 __n =
std::min(__n, __unsampled_sz);
5829 const __uc_type __urngrange = __g.max() - __g.min();
5830 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5834 while (__n != 0 && __unsampled_sz >= 2)
5840 if (__p.
first < __n)
5842 *__out++ = *__first;
5848 if (__n == 0)
break;
5853 *__out++ = *__first;
5863 for (; __n != 0; ++__first)
5864 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5866 *__out++ = *__first;
5873#ifdef __glibcxx_sample
5875 template<typename _PopulationIterator, typename _SampleIterator,
5876 typename _Distance,
typename _UniformRandomBitGenerator>
5878 sample(_PopulationIterator __first, _PopulationIterator __last,
5879 _SampleIterator __out, _Distance __n,
5880 _UniformRandomBitGenerator&& __g)
5882 using __pop_cat =
typename
5884 using __samp_cat =
typename
5888 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5889 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5890 "output range must use a RandomAccessIterator when input range"
5891 " does not meet the ForwardIterator requirements");
5894 "sample size must be an integer type");
5897 return _GLIBCXX_STD_A::
5898 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5903_GLIBCXX_END_NAMESPACE_ALGO
5904_GLIBCXX_END_NAMESPACE_VERSION
5907#pragma GCC diagnostic pop
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Compare __comp)
This is a helper function for the merge routines.
constexpr _InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
constexpr _OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
constexpr _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
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 void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
constexpr _ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
constexpr _InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
constexpr iterator_type base() const noexcept(/*conditional */)
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
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...