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,
2420 _BidirectionalIterator __middle,
2421 _BidirectionalIterator __last,
2422 _Distance __len1, _Distance __len2,
2425 if (__len1 == 0 || __len2 == 0)
2428 if (__len1 + __len2 == 2)
2430 if (__comp(__middle, __first))
2431 std::iter_swap(__first, __middle);
2435 _BidirectionalIterator __first_cut = __first;
2436 _BidirectionalIterator __second_cut = __middle;
2437 _Distance __len11 = 0;
2438 _Distance __len22 = 0;
2439 if (__len1 > __len2)
2441 __len11 = __len1 / 2;
2444 = std::__lower_bound(__middle, __last, *__first_cut,
2445 __gnu_cxx::__ops::__iter_comp_val(__comp));
2450 __len22 = __len2 / 2;
2453 = std::__upper_bound(__first, __middle, *__second_cut,
2454 __gnu_cxx::__ops::__val_comp_iter(__comp));
2458 _BidirectionalIterator __new_middle
2459 = std::rotate(__first_cut, __middle, __second_cut);
2461 __len11, __len22, __comp);
2463 __len1 - __len11, __len2 - __len22, __comp);
2466 template<
typename _B
idirectionalIterator,
typename _Compare>
2468 __inplace_merge(_BidirectionalIterator __first,
2469 _BidirectionalIterator __middle,
2470 _BidirectionalIterator __last,
2473 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2475 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2478 if (__first == __middle || __middle == __last)
2481 const _DistanceType __len1 =
std::distance(__first, __middle);
2482 const _DistanceType __len2 =
std::distance(__middle, __last);
2485 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2488 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2490 if (__builtin_expect(__buf.size() == __buf.requested_size(),
true))
2492 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2493 else if (__builtin_expect(__buf.begin() == 0,
false))
2495 (__first, __middle, __last, __len1, __len2, __comp);
2497 std::__merge_adaptive_resize
2498 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2499 _DistanceType(__buf.size()), __comp);
2502 (__first, __middle, __last, __len1, __len2, __comp);
2524 template<
typename _B
idirectionalIterator>
2526 inplace_merge(_BidirectionalIterator __first,
2527 _BidirectionalIterator __middle,
2528 _BidirectionalIterator __last)
2531 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2532 _BidirectionalIterator>)
2533 __glibcxx_function_requires(_LessThanComparableConcept<
2535 __glibcxx_requires_sorted(__first, __middle);
2536 __glibcxx_requires_sorted(__middle, __last);
2537 __glibcxx_requires_irreflexive(__first, __last);
2539 std::__inplace_merge(__first, __middle, __last,
2540 __gnu_cxx::__ops::__iter_less_iter());
2565 template<
typename _B
idirectionalIterator,
typename _Compare>
2567 inplace_merge(_BidirectionalIterator __first,
2568 _BidirectionalIterator __middle,
2569 _BidirectionalIterator __last,
2573 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2574 _BidirectionalIterator>)
2575 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2578 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2579 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2580 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2582 std::__inplace_merge(__first, __middle, __last,
2583 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2588 template<
typename _InputIterator,
typename _OutputIterator,
2592 _InputIterator __first2, _InputIterator __last2,
2593 _OutputIterator __result, _Compare __comp)
2595 while (__first1 != __last1 && __first2 != __last2)
2597 if (__comp(__first2, __first1))
2599 *__result = _GLIBCXX_MOVE(*__first2);
2604 *__result = _GLIBCXX_MOVE(*__first1);
2609 return _GLIBCXX_MOVE3(__first2, __last2,
2610 _GLIBCXX_MOVE3(__first1, __last1,
2614 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2615 typename _Distance,
typename _Compare>
2617 __merge_sort_loop(_RandomAccessIterator1 __first,
2618 _RandomAccessIterator1 __last,
2619 _RandomAccessIterator2 __result, _Distance __step_size,
2622 const _Distance __two_step = 2 * __step_size;
2624 while (__last - __first >= __two_step)
2627 __first + __step_size,
2628 __first + __two_step,
2630 __first += __two_step;
2632 __step_size =
std::min(_Distance(__last - __first), __step_size);
2635 __first + __step_size, __last, __result, __comp);
2638 template<
typename _RandomAccessIterator,
typename _Distance,
2640 _GLIBCXX20_CONSTEXPR
2642 __chunk_insertion_sort(_RandomAccessIterator __first,
2643 _RandomAccessIterator __last,
2644 _Distance __chunk_size, _Compare __comp)
2646 while (__last - __first >= __chunk_size)
2648 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2649 __first += __chunk_size;
2651 std::__insertion_sort(__first, __last, __comp);
2654 enum { _S_chunk_size = 7 };
2656 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2658 __merge_sort_with_buffer(_RandomAccessIterator __first,
2659 _RandomAccessIterator __last,
2660 _Pointer __buffer, _Compare __comp)
2665 const _Distance __len = __last - __first;
2666 const _Pointer __buffer_last = __buffer + __len;
2668 _Distance __step_size = _S_chunk_size;
2669 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2671 while (__step_size < __len)
2673 std::__merge_sort_loop(__first, __last, __buffer,
2674 __step_size, __comp);
2676 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2677 __step_size, __comp);
2682 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2684 __stable_sort_adaptive(_RandomAccessIterator __first,
2685 _RandomAccessIterator __middle,
2686 _RandomAccessIterator __last,
2687 _Pointer __buffer, _Compare __comp)
2689 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2690 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2693 __middle - __first, __last - __middle,
2697 template<
typename _RandomAccessIterator,
typename _Pointer,
2698 typename _Distance,
typename _Compare>
2700 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2701 _RandomAccessIterator __last,
2702 _Pointer __buffer, _Distance __buffer_size,
2705 const _Distance __len = (__last - __first + 1) / 2;
2706 const _RandomAccessIterator __middle = __first + __len;
2707 if (__len > __buffer_size)
2709 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2710 __buffer_size, __comp);
2711 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2712 __buffer_size, __comp);
2713 std::__merge_adaptive_resize(__first, __middle, __last,
2714 _Distance(__middle - __first),
2715 _Distance(__last - __middle),
2716 __buffer, __buffer_size,
2720 std::__stable_sort_adaptive(__first, __middle, __last,
2725 template<
typename _RandomAccessIterator,
typename _Compare>
2728 _RandomAccessIterator __last, _Compare __comp)
2730 if (__last - __first < 15)
2732 std::__insertion_sort(__first, __last, __comp);
2735 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2751 template<
typename _InputIterator1,
typename _InputIterator2,
2753 _GLIBCXX20_CONSTEXPR
2755 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2756 _InputIterator2 __first2, _InputIterator2 __last2,
2759 while (__first1 != __last1 && __first2 != __last2)
2761 if (__comp(__first2, __first1))
2763 if (!__comp(__first1, __first2))
2768 return __first2 == __last2;
2789 template<
typename _InputIterator1,
typename _InputIterator2>
2790 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2792 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2793 _InputIterator2 __first2, _InputIterator2 __last2)
2796 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2798 __glibcxx_function_requires(_LessThanOpConcept<
2801 __glibcxx_function_requires(_LessThanOpConcept<
2804 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2805 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2806 __glibcxx_requires_irreflexive2(__first1, __last1);
2807 __glibcxx_requires_irreflexive2(__first2, __last2);
2809 return std::__includes(__first1, __last1, __first2, __last2,
2810 __gnu_cxx::__ops::__iter_less_iter());
2834 template<
typename _InputIterator1,
typename _InputIterator2,
2836 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2838 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2839 _InputIterator2 __first2, _InputIterator2 __last2,
2843 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2844 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2845 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2848 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2851 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2852 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2853 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2854 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2856 return std::__includes(__first1, __last1, __first2, __last2,
2857 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2870 template<
typename _B
idirectionalIterator,
typename _Compare>
2871 _GLIBCXX20_CONSTEXPR
2873 __next_permutation(_BidirectionalIterator __first,
2874 _BidirectionalIterator __last, _Compare __comp)
2876 if (__first == __last)
2878 _BidirectionalIterator __i = __first;
2887 _BidirectionalIterator __ii = __i;
2889 if (__comp(__i, __ii))
2891 _BidirectionalIterator __j = __last;
2892 while (!__comp(__i, --__j))
2894 std::iter_swap(__i, __j);
2920 template<
typename _B
idirectionalIterator>
2921 _GLIBCXX20_CONSTEXPR
2923 next_permutation(_BidirectionalIterator __first,
2924 _BidirectionalIterator __last)
2927 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2928 _BidirectionalIterator>)
2929 __glibcxx_function_requires(_LessThanComparableConcept<
2931 __glibcxx_requires_valid_range(__first, __last);
2932 __glibcxx_requires_irreflexive(__first, __last);
2934 return std::__next_permutation
2935 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2953 template<
typename _B
idirectionalIterator,
typename _Compare>
2954 _GLIBCXX20_CONSTEXPR
2956 next_permutation(_BidirectionalIterator __first,
2957 _BidirectionalIterator __last, _Compare __comp)
2960 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2961 _BidirectionalIterator>)
2962 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2965 __glibcxx_requires_valid_range(__first, __last);
2966 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2968 return std::__next_permutation
2969 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2972 template<
typename _B
idirectionalIterator,
typename _Compare>
2973 _GLIBCXX20_CONSTEXPR
2975 __prev_permutation(_BidirectionalIterator __first,
2976 _BidirectionalIterator __last, _Compare __comp)
2978 if (__first == __last)
2980 _BidirectionalIterator __i = __first;
2989 _BidirectionalIterator __ii = __i;
2991 if (__comp(__ii, __i))
2993 _BidirectionalIterator __j = __last;
2994 while (!__comp(--__j, __i))
2996 std::iter_swap(__i, __j);
3023 template<
typename _B
idirectionalIterator>
3024 _GLIBCXX20_CONSTEXPR
3026 prev_permutation(_BidirectionalIterator __first,
3027 _BidirectionalIterator __last)
3030 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3031 _BidirectionalIterator>)
3032 __glibcxx_function_requires(_LessThanComparableConcept<
3034 __glibcxx_requires_valid_range(__first, __last);
3035 __glibcxx_requires_irreflexive(__first, __last);
3037 return std::__prev_permutation(__first, __last,
3038 __gnu_cxx::__ops::__iter_less_iter());
3056 template<
typename _B
idirectionalIterator,
typename _Compare>
3057 _GLIBCXX20_CONSTEXPR
3059 prev_permutation(_BidirectionalIterator __first,
3060 _BidirectionalIterator __last, _Compare __comp)
3063 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3064 _BidirectionalIterator>)
3065 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3068 __glibcxx_requires_valid_range(__first, __last);
3069 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3071 return std::__prev_permutation(__first, __last,
3072 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3078 template<
typename _InputIterator,
typename _OutputIterator,
3079 typename _Predicate,
typename _Tp>
3080 _GLIBCXX20_CONSTEXPR
3082 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3083 _OutputIterator __result,
3084 _Predicate __pred,
const _Tp& __new_value)
3086 for (; __first != __last; ++__first, (void)++__result)
3087 if (__pred(__first))
3088 *__result = __new_value;
3090 *__result = *__first;
3108 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3109 _GLIBCXX20_CONSTEXPR
3110 inline _OutputIterator
3111 replace_copy(_InputIterator __first, _InputIterator __last,
3112 _OutputIterator __result,
3113 const _Tp& __old_value,
const _Tp& __new_value)
3116 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3117 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3119 __glibcxx_function_requires(_EqualOpConcept<
3121 __glibcxx_requires_valid_range(__first, __last);
3123 return std::__replace_copy_if(__first, __last, __result,
3124 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3143 template<
typename _InputIterator,
typename _OutputIterator,
3144 typename _Predicate,
typename _Tp>
3145 _GLIBCXX20_CONSTEXPR
3146 inline _OutputIterator
3147 replace_copy_if(_InputIterator __first, _InputIterator __last,
3148 _OutputIterator __result,
3149 _Predicate __pred,
const _Tp& __new_value)
3152 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3153 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3155 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3157 __glibcxx_requires_valid_range(__first, __last);
3159 return std::__replace_copy_if(__first, __last, __result,
3160 __gnu_cxx::__ops::__pred_iter(__pred),
3164#if __cplusplus >= 201103L
3172 template<
typename _ForwardIterator>
3173 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3175 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3176 {
return std::is_sorted_until(__first, __last) == __last; }
3187 template<
typename _ForwardIterator,
typename _Compare>
3188 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3190 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3192 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3194 template<
typename _ForwardIterator,
typename _Compare>
3195 _GLIBCXX20_CONSTEXPR
3197 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3200 if (__first == __last)
3203 _ForwardIterator __next = __first;
3204 for (++__next; __next != __last; __first = __next, (void)++__next)
3205 if (__comp(__next, __first))
3218 template<
typename _ForwardIterator>
3219 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3220 inline _ForwardIterator
3221 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3224 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3225 __glibcxx_function_requires(_LessThanComparableConcept<
3227 __glibcxx_requires_valid_range(__first, __last);
3228 __glibcxx_requires_irreflexive(__first, __last);
3230 return std::__is_sorted_until(__first, __last,
3231 __gnu_cxx::__ops::__iter_less_iter());
3243 template<
typename _ForwardIterator,
typename _Compare>
3244 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3245 inline _ForwardIterator
3246 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3250 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3251 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3254 __glibcxx_requires_valid_range(__first, __last);
3255 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3257 return std::__is_sorted_until(__first, __last,
3258 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3269 template<
typename _Tp>
3270 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3275 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3277 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3290 template<
typename _Tp,
typename _Compare>
3291 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3293 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3299 template<
typename _ForwardIterator,
typename _Compare>
3300 _GLIBCXX14_CONSTEXPR
3302 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3305 _ForwardIterator __next = __first;
3306 if (__first == __last
3307 || ++__next == __last)
3310 _ForwardIterator __min{}, __max{};
3311 if (__comp(__next, __first))
3325 while (__first != __last)
3328 if (++__next == __last)
3330 if (__comp(__first, __min))
3332 else if (!__comp(__first, __max))
3337 if (__comp(__next, __first))
3339 if (__comp(__next, __min))
3341 if (!__comp(__first, __max))
3346 if (__comp(__first, __min))
3348 if (!__comp(__next, __max))
3370 template<
typename _ForwardIterator>
3371 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3373 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3376 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3377 __glibcxx_function_requires(_LessThanComparableConcept<
3379 __glibcxx_requires_valid_range(__first, __last);
3380 __glibcxx_requires_irreflexive(__first, __last);
3382 return std::__minmax_element(__first, __last,
3383 __gnu_cxx::__ops::__iter_less_iter());
3398 template<
typename _ForwardIterator,
typename _Compare>
3399 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3401 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3405 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3406 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3409 __glibcxx_requires_valid_range(__first, __last);
3410 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3412 return std::__minmax_element(__first, __last,
3413 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3416 template<
typename _Tp>
3417 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3418 inline pair<_Tp, _Tp>
3419 minmax(initializer_list<_Tp> __l)
3421 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3423 std::__minmax_element(__l.begin(), __l.end(),
3424 __gnu_cxx::__ops::__iter_less_iter());
3428 template<
typename _Tp,
typename _Compare>
3429 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3433 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3435 std::__minmax_element(__l.begin(), __l.end(),
3436 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3454 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3455 typename _BinaryPredicate>
3456 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3458 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3459 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3462 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3463 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3464 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3467 __glibcxx_requires_valid_range(__first1, __last1);
3469 return std::__is_permutation(__first1, __last1, __first2,
3470 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3473#if __cplusplus > 201103L
3474#pragma GCC diagnostic push
3475#pragma GCC diagnostic ignored "-Wc++17-extensions"
3476 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3477 typename _BinaryPredicate>
3478 _GLIBCXX20_CONSTEXPR
3480 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3481 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3482 _BinaryPredicate __pred)
3485 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3487 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3488 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3489 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3490 constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
3491 if constexpr (__ra_iters)
3493 if ((__last1 - __first1) != (__last2 - __first2))
3499 for (; __first1 != __last1 && __first2 != __last2;
3500 ++__first1, (void)++__first2)
3501 if (!__pred(__first1, __first2))
3504 if constexpr (__ra_iters)
3506 if (__first1 == __last1)
3513 if (__d1 == 0 && __d2 == 0)
3519 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3521 if (__scan != std::__find_if(__first1, __scan,
3522 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3525 auto __matches = std::__count_if(__first2, __last2,
3526 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3528 || std::__count_if(__scan, __last1,
3529 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3535#pragma GCC diagnostic pop
3550 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3551 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3553 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3554 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3556 __glibcxx_requires_valid_range(__first1, __last1);
3557 __glibcxx_requires_valid_range(__first2, __last2);
3560 std::__is_permutation(__first1, __last1, __first2, __last2,
3561 __gnu_cxx::__ops::__iter_equal_to_iter());
3578 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3579 typename _BinaryPredicate>
3580 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3582 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3583 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3584 _BinaryPredicate __pred)
3586 __glibcxx_requires_valid_range(__first1, __last1);
3587 __glibcxx_requires_valid_range(__first2, __last2);
3589 return std::__is_permutation(__first1, __last1, __first2, __last2,
3590 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3594#ifdef __glibcxx_clamp
3606 template<
typename _Tp>
3607 [[nodiscard]]
constexpr const _Tp&
3608 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3610 __glibcxx_assert(!(__hi < __lo));
3626 template<
typename _Tp,
typename _Compare>
3627 [[nodiscard]]
constexpr const _Tp&
3628 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3630 __glibcxx_assert(!__comp(__hi, __lo));
3656 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3659 _UniformRandomBitGenerator&& __g)
3678 template<
typename _RandomAccessIterator,
3679 typename _UniformRandomNumberGenerator>
3681 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3682 _UniformRandomNumberGenerator&& __g)
3685 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3686 _RandomAccessIterator>)
3687 __glibcxx_requires_valid_range(__first, __last);
3689 if (__first == __last)
3695 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3697 typedef typename __distr_type::param_type __p_type;
3699 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3704 const __uc_type __urngrange = __g.max() - __g.min();
3705 const __uc_type __urange = __uc_type(__last - __first);
3707 if (__urngrange / __urange >= __urange)
3710 _RandomAccessIterator __i = __first + 1;
3716 if ((__urange % 2) == 0)
3718 __distr_type __d{0, 1};
3719 std::iter_swap(__i++, __first + __d(__g));
3726 while (__i != __last)
3728 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3733 std::iter_swap(__i++, __first + __pospos.
first);
3734 std::iter_swap(__i++, __first + __pospos.
second);
3742 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3743 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3747_GLIBCXX_BEGIN_NAMESPACE_ALGO
3761 template<
typename _InputIterator,
typename _Function>
3762 _GLIBCXX20_CONSTEXPR
3764 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3767 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3768 __glibcxx_requires_valid_range(__first, __last);
3769 for (; __first != __last; ++__first)
3774#if __cplusplus >= 201703L
3787 template<
typename _InputIterator,
typename _Size,
typename _Function>
3788 _GLIBCXX20_CONSTEXPR
3792 auto __n2 = std::__size_to_integer(__n);
3794 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3798 auto __last = __first + __n2;
3799 std::for_each(__first, __last,
std::move(__f));
3823 template<
typename _InputIterator,
typename _Tp>
3824 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3825 inline _InputIterator
3826 find(_InputIterator __first, _InputIterator __last,
const _Tp& __val)
3829 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3830 __glibcxx_function_requires(_EqualOpConcept<
3832 __glibcxx_requires_valid_range(__first, __last);
3834#if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates
3836 if constexpr (__can_use_memchr_for_find<_ValT, _Tp>)
3837 if constexpr (is_pointer_v<
decltype(std::__niter_base(__first))>
3838#
if __glibcxx_concepts && __glibcxx_to_address
3839 || contiguous_iterator<_InputIterator>
3847 if (!(
static_cast<_ValT
>(__val) == __val))
3849 else if (!__is_constant_evaluated())
3851 const int __ival =
static_cast<int>(__val);
3852 if (
auto __n = __last - __first; __n > 0)
3854#if __glibcxx_concepts && __glibcxx_to_address
3857 const void* __p0 = std::__niter_base(__first);
3859 if (
auto __p1 = __builtin_memchr(__p0, __ival, __n))
3860 return __first + ((
const char*)__p1 - (
const char*)__p0);
3867 return std::__find_if(__first, __last,
3868 __gnu_cxx::__ops::__iter_equals_val(__val));
3881 template<
typename _InputIterator,
typename _Predicate>
3882 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3883 inline _InputIterator
3884 find_if(_InputIterator __first, _InputIterator __last,
3888 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3889 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3891 __glibcxx_requires_valid_range(__first, __last);
3893 return std::__find_if(__first, __last,
3894 __gnu_cxx::__ops::__pred_iter(__pred));
3913 template<
typename _InputIterator,
typename _ForwardIterator>
3914 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3916 find_first_of(_InputIterator __first1, _InputIterator __last1,
3917 _ForwardIterator __first2, _ForwardIterator __last2)
3920 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3921 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3922 __glibcxx_function_requires(_EqualOpConcept<
3925 __glibcxx_requires_valid_range(__first1, __last1);
3926 __glibcxx_requires_valid_range(__first2, __last2);
3928 for (; __first1 != __last1; ++__first1)
3929 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3930 if (*__first1 == *__iter)
3954 template<
typename _InputIterator,
typename _ForwardIterator,
3955 typename _BinaryPredicate>
3956 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3958 find_first_of(_InputIterator __first1, _InputIterator __last1,
3959 _ForwardIterator __first2, _ForwardIterator __last2,
3960 _BinaryPredicate __comp)
3963 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3964 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3965 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3968 __glibcxx_requires_valid_range(__first1, __last1);
3969 __glibcxx_requires_valid_range(__first2, __last2);
3971 for (; __first1 != __last1; ++__first1)
3972 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3973 if (__comp(*__first1, *__iter))
3987 template<
typename _ForwardIterator>
3988 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3989 inline _ForwardIterator
3990 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3993 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3994 __glibcxx_function_requires(_EqualityComparableConcept<
3996 __glibcxx_requires_valid_range(__first, __last);
3998 return std::__adjacent_find(__first, __last,
3999 __gnu_cxx::__ops::__iter_equal_to_iter());
4013 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4014 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4015 inline _ForwardIterator
4016 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4017 _BinaryPredicate __binary_pred)
4020 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4021 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4024 __glibcxx_requires_valid_range(__first, __last);
4026 return std::__adjacent_find(__first, __last,
4027 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4039 template<
typename _InputIterator,
typename _Tp>
4040 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4041 inline typename iterator_traits<_InputIterator>::difference_type
4042 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4045 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4046 __glibcxx_function_requires(_EqualOpConcept<
4048 __glibcxx_requires_valid_range(__first, __last);
4050 return std::__count_if(__first, __last,
4051 __gnu_cxx::__ops::__iter_equals_val(__value));
4063 template<
typename _InputIterator,
typename _Predicate>
4064 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4065 inline typename iterator_traits<_InputIterator>::difference_type
4066 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4069 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4070 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4072 __glibcxx_requires_valid_range(__first, __last);
4074 return std::__count_if(__first, __last,
4075 __gnu_cxx::__ops::__pred_iter(__pred));
4104 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4105 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4106 inline _ForwardIterator1
4107 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4108 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4111 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4112 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4113 __glibcxx_function_requires(_EqualOpConcept<
4116 __glibcxx_requires_valid_range(__first1, __last1);
4117 __glibcxx_requires_valid_range(__first2, __last2);
4119 return std::__search(__first1, __last1, __first2, __last2,
4120 __gnu_cxx::__ops::__iter_equal_to_iter());
4138 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4139 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4140 inline _ForwardIterator
4141 search_n(_ForwardIterator __first, _ForwardIterator __last,
4142 _Integer __count,
const _Tp& __val)
4145 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4146 __glibcxx_function_requires(_EqualOpConcept<
4148 __glibcxx_requires_valid_range(__first, __last);
4150 return std::__search_n(__first, __last, __count,
4151 __gnu_cxx::__ops::__iter_equals_val(__val));
4172 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4173 typename _BinaryPredicate>
4174 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4175 inline _ForwardIterator
4176 search_n(_ForwardIterator __first, _ForwardIterator __last,
4177 _Integer __count,
const _Tp& __val,
4178 _BinaryPredicate __binary_pred)
4181 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4182 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4184 __glibcxx_requires_valid_range(__first, __last);
4186 return std::__search_n(__first, __last, __count,
4187 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4190#if __cplusplus >= 201703L
4198 template<
typename _ForwardIterator,
typename _Searcher>
4199 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4200 inline _ForwardIterator
4201 search(_ForwardIterator __first, _ForwardIterator __last,
4202 const _Searcher& __searcher)
4203 {
return __searcher(__first, __last).first; }
4222 template<
typename _InputIterator,
typename _OutputIterator,
4223 typename _UnaryOperation>
4224 _GLIBCXX20_CONSTEXPR
4226 transform(_InputIterator __first, _InputIterator __last,
4227 _OutputIterator __result, _UnaryOperation __unary_op)
4230 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4231 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4233 __typeof__(__unary_op(*__first))>)
4234 __glibcxx_requires_valid_range(__first, __last);
4236 for (; __first != __last; ++__first, (void)++__result)
4237 *__result = __unary_op(*__first);
4260 template<
typename _InputIterator1,
typename _InputIterator2,
4261 typename _OutputIterator,
typename _BinaryOperation>
4262 _GLIBCXX20_CONSTEXPR
4264 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4265 _InputIterator2 __first2, _OutputIterator __result,
4266 _BinaryOperation __binary_op)
4269 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4270 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4271 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4273 __typeof__(__binary_op(*__first1,*__first2))>)
4274 __glibcxx_requires_valid_range(__first1, __last1);
4276 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4277 *__result = __binary_op(*__first1, *__first2);
4294 template<
typename _ForwardIterator,
typename _Tp>
4295 _GLIBCXX20_CONSTEXPR
4297 replace(_ForwardIterator __first, _ForwardIterator __last,
4298 const _Tp& __old_value,
const _Tp& __new_value)
4301 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4303 __glibcxx_function_requires(_EqualOpConcept<
4305 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4307 __glibcxx_requires_valid_range(__first, __last);
4309 for (; __first != __last; ++__first)
4310 if (*__first == __old_value)
4311 *__first = __new_value;
4327 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4328 _GLIBCXX20_CONSTEXPR
4330 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4331 _Predicate __pred,
const _Tp& __new_value)
4334 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4336 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4338 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4340 __glibcxx_requires_valid_range(__first, __last);
4342 for (; __first != __last; ++__first)
4343 if (__pred(*__first))
4344 *__first = __new_value;
4359 template<
typename _ForwardIterator,
typename _Generator>
4360 _GLIBCXX20_CONSTEXPR
4362 generate(_ForwardIterator __first, _ForwardIterator __last,
4366 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4367 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4369 __glibcxx_requires_valid_range(__first, __last);
4371 for (; __first != __last; ++__first)
4392 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4393 _GLIBCXX20_CONSTEXPR
4395 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4398 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4400 __typeof__(__gen())>)
4402 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4403 for (_IntSize __niter = std::__size_to_integer(__n);
4404 __niter > 0; --__niter, (void) ++__first)
4427 template<
typename _InputIterator,
typename _OutputIterator>
4428 _GLIBCXX20_CONSTEXPR
4429 inline _OutputIterator
4430 unique_copy(_InputIterator __first, _InputIterator __last,
4431 _OutputIterator __result)
4434 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4435 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4437 __glibcxx_function_requires(_EqualityComparableConcept<
4439 __glibcxx_requires_valid_range(__first, __last);
4441 if (__first == __last)
4444 __gnu_cxx::__ops::__iter_equal_to_iter(),
4467 template<
typename _InputIterator,
typename _OutputIterator,
4468 typename _BinaryPredicate>
4469 _GLIBCXX20_CONSTEXPR
4470 inline _OutputIterator
4471 unique_copy(_InputIterator __first, _InputIterator __last,
4472 _OutputIterator __result,
4473 _BinaryPredicate __binary_pred)
4476 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4477 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4479 __glibcxx_requires_valid_range(__first, __last);
4481 if (__first == __last)
4484 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4489#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4506 template<
typename _RandomAccessIterator>
4507 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4509 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4512 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4513 _RandomAccessIterator>)
4514 __glibcxx_requires_valid_range(__first, __last);
4516 if (__first == __last)
4519#if RAND_MAX < __INT_MAX__
4520 if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
4525 = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
4526 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4529 __xss ^= __xss << 13;
4530 __xss ^= __xss >> 17;
4531 __xss ^= __xss << 5;
4532 _RandomAccessIterator __j = __first
4533 + (__xss % ((__i - __first) + 1));
4535 std::iter_swap(__i, __j);
4541 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4544 _RandomAccessIterator __j = __first
4545 + (std::rand() % ((__i - __first) + 1));
4547 std::iter_swap(__i, __j);
4569 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4570 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4572 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4573#if __cplusplus >= 201103L
4574 _RandomNumberGenerator&& __rand)
4576 _RandomNumberGenerator& __rand)
4580 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4581 _RandomAccessIterator>)
4582 __glibcxx_requires_valid_range(__first, __last);
4584 if (__first == __last)
4586 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4588 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4590 std::iter_swap(__i, __j);
4611 template<
typename _ForwardIterator,
typename _Predicate>
4612 _GLIBCXX20_CONSTEXPR
4613 inline _ForwardIterator
4614 partition(_ForwardIterator __first, _ForwardIterator __last,
4618 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4620 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4622 __glibcxx_requires_valid_range(__first, __last);
4646 template<
typename _RandomAccessIterator>
4647 _GLIBCXX20_CONSTEXPR
4649 partial_sort(_RandomAccessIterator __first,
4650 _RandomAccessIterator __middle,
4651 _RandomAccessIterator __last)
4654 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4655 _RandomAccessIterator>)
4656 __glibcxx_function_requires(_LessThanComparableConcept<
4658 __glibcxx_requires_valid_range(__first, __middle);
4659 __glibcxx_requires_valid_range(__middle, __last);
4660 __glibcxx_requires_irreflexive(__first, __last);
4662 std::__partial_sort(__first, __middle, __last,
4663 __gnu_cxx::__ops::__iter_less_iter());
4685 template<
typename _RandomAccessIterator,
typename _Compare>
4686 _GLIBCXX20_CONSTEXPR
4688 partial_sort(_RandomAccessIterator __first,
4689 _RandomAccessIterator __middle,
4690 _RandomAccessIterator __last,
4694 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4695 _RandomAccessIterator>)
4696 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4699 __glibcxx_requires_valid_range(__first, __middle);
4700 __glibcxx_requires_valid_range(__middle, __last);
4701 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4703 std::__partial_sort(__first, __middle, __last,
4704 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4722 template<
typename _RandomAccessIterator>
4723 _GLIBCXX20_CONSTEXPR
4725 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4726 _RandomAccessIterator __last)
4729 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4730 _RandomAccessIterator>)
4731 __glibcxx_function_requires(_LessThanComparableConcept<
4733 __glibcxx_requires_valid_range(__first, __nth);
4734 __glibcxx_requires_valid_range(__nth, __last);
4735 __glibcxx_requires_irreflexive(__first, __last);
4737 if (__first == __last || __nth == __last)
4740 std::__introselect(__first, __nth, __last,
4742 __gnu_cxx::__ops::__iter_less_iter());
4762 template<
typename _RandomAccessIterator,
typename _Compare>
4763 _GLIBCXX20_CONSTEXPR
4765 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4766 _RandomAccessIterator __last, _Compare __comp)
4769 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4770 _RandomAccessIterator>)
4771 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4774 __glibcxx_requires_valid_range(__first, __nth);
4775 __glibcxx_requires_valid_range(__nth, __last);
4776 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4778 if (__first == __last || __nth == __last)
4781 std::__introselect(__first, __nth, __last,
4783 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4800 template<
typename _RandomAccessIterator>
4801 _GLIBCXX20_CONSTEXPR
4803 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4806 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4807 _RandomAccessIterator>)
4808 __glibcxx_function_requires(_LessThanComparableConcept<
4810 __glibcxx_requires_valid_range(__first, __last);
4811 __glibcxx_requires_irreflexive(__first, __last);
4813 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4831 template<
typename _RandomAccessIterator,
typename _Compare>
4832 _GLIBCXX20_CONSTEXPR
4834 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4838 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4839 _RandomAccessIterator>)
4840 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4843 __glibcxx_requires_valid_range(__first, __last);
4844 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4846 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4849 template<
typename _InputIterator1,
typename _InputIterator2,
4850 typename _OutputIterator,
typename _Compare>
4851 _GLIBCXX20_CONSTEXPR
4853 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4854 _InputIterator2 __first2, _InputIterator2 __last2,
4855 _OutputIterator __result, _Compare __comp)
4857 while (__first1 != __last1 && __first2 != __last2)
4859 if (__comp(__first2, __first1))
4861 *__result = *__first2;
4866 *__result = *__first1;
4871 return std::copy(__first2, __last2,
4872 std::copy(__first1, __last1, __result));
4894 template<
typename _InputIterator1,
typename _InputIterator2,
4895 typename _OutputIterator>
4896 _GLIBCXX20_CONSTEXPR
4897 inline _OutputIterator
4898 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4899 _InputIterator2 __first2, _InputIterator2 __last2,
4900 _OutputIterator __result)
4903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4904 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4905 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4907 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4909 __glibcxx_function_requires(_LessThanOpConcept<
4912 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4913 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4914 __glibcxx_requires_irreflexive2(__first1, __last1);
4915 __glibcxx_requires_irreflexive2(__first2, __last2);
4917 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4918 __first2, __last2, __result,
4919 __gnu_cxx::__ops::__iter_less_iter());
4945 template<
typename _InputIterator1,
typename _InputIterator2,
4946 typename _OutputIterator,
typename _Compare>
4947 _GLIBCXX20_CONSTEXPR
4948 inline _OutputIterator
4949 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4950 _InputIterator2 __first2, _InputIterator2 __last2,
4951 _OutputIterator __result, _Compare __comp)
4954 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4955 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4956 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4958 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4960 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4963 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4964 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4965 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4966 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4968 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4969 __first2, __last2, __result,
4970 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4973 template<
typename _RandomAccessIterator,
typename _Compare>
4975 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4978 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4980 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4983 if (__first == __last)
4987 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4990 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
4992 if (__builtin_expect(__buf.requested_size() == __buf.size(),
true))
4993 std::__stable_sort_adaptive(__first,
4994 __first + _DistanceType(__buf.size()),
4995 __last, __buf.begin(), __comp);
4996 else if (__builtin_expect(__buf.begin() == 0,
false))
4999 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
5000 _DistanceType(__buf.size()), __comp);
5023 template<
typename _RandomAccessIterator>
5025 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5028 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5029 _RandomAccessIterator>)
5030 __glibcxx_function_requires(_LessThanComparableConcept<
5032 __glibcxx_requires_valid_range(__first, __last);
5033 __glibcxx_requires_irreflexive(__first, __last);
5035 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5036 __gnu_cxx::__ops::__iter_less_iter());
5057 template<
typename _RandomAccessIterator,
typename _Compare>
5059 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5063 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5064 _RandomAccessIterator>)
5065 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5068 __glibcxx_requires_valid_range(__first, __last);
5069 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5071 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5072 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5075 template<
typename _InputIterator1,
typename _InputIterator2,
5076 typename _OutputIterator,
5078 _GLIBCXX20_CONSTEXPR
5080 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5081 _InputIterator2 __first2, _InputIterator2 __last2,
5082 _OutputIterator __result, _Compare __comp)
5084 while (__first1 != __last1 && __first2 != __last2)
5086 if (__comp(__first1, __first2))
5088 *__result = *__first1;
5091 else if (__comp(__first2, __first1))
5093 *__result = *__first2;
5098 *__result = *__first1;
5104 return std::copy(__first2, __last2,
5105 std::copy(__first1, __last1, __result));
5127 template<
typename _InputIterator1,
typename _InputIterator2,
5128 typename _OutputIterator>
5129 _GLIBCXX20_CONSTEXPR
5130 inline _OutputIterator
5131 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5132 _InputIterator2 __first2, _InputIterator2 __last2,
5133 _OutputIterator __result)
5136 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5137 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5138 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5140 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5142 __glibcxx_function_requires(_LessThanOpConcept<
5145 __glibcxx_function_requires(_LessThanOpConcept<
5148 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5149 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5150 __glibcxx_requires_irreflexive2(__first1, __last1);
5151 __glibcxx_requires_irreflexive2(__first2, __last2);
5153 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5154 __first2, __last2, __result,
5155 __gnu_cxx::__ops::__iter_less_iter());
5178 template<
typename _InputIterator1,
typename _InputIterator2,
5179 typename _OutputIterator,
typename _Compare>
5180 _GLIBCXX20_CONSTEXPR
5181 inline _OutputIterator
5182 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5183 _InputIterator2 __first2, _InputIterator2 __last2,
5184 _OutputIterator __result, _Compare __comp)
5187 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5188 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5189 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5191 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5193 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5196 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5199 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5200 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5201 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5202 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5204 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5205 __first2, __last2, __result,
5206 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5209 template<
typename _InputIterator1,
typename _InputIterator2,
5210 typename _OutputIterator,
5212 _GLIBCXX20_CONSTEXPR
5214 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5215 _InputIterator2 __first2, _InputIterator2 __last2,
5216 _OutputIterator __result, _Compare __comp)
5218 while (__first1 != __last1 && __first2 != __last2)
5219 if (__comp(__first1, __first2))
5221 else if (__comp(__first2, __first1))
5225 *__result = *__first1;
5251 template<
typename _InputIterator1,
typename _InputIterator2,
5252 typename _OutputIterator>
5253 _GLIBCXX20_CONSTEXPR
5254 inline _OutputIterator
5255 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5256 _InputIterator2 __first2, _InputIterator2 __last2,
5257 _OutputIterator __result)
5260 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5261 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5262 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5264 __glibcxx_function_requires(_LessThanOpConcept<
5267 __glibcxx_function_requires(_LessThanOpConcept<
5270 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5271 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5272 __glibcxx_requires_irreflexive2(__first1, __last1);
5273 __glibcxx_requires_irreflexive2(__first2, __last2);
5275 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5276 __first2, __last2, __result,
5277 __gnu_cxx::__ops::__iter_less_iter());
5301 template<
typename _InputIterator1,
typename _InputIterator2,
5302 typename _OutputIterator,
typename _Compare>
5303 _GLIBCXX20_CONSTEXPR
5304 inline _OutputIterator
5305 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5306 _InputIterator2 __first2, _InputIterator2 __last2,
5307 _OutputIterator __result, _Compare __comp)
5310 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5311 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5312 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5314 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5317 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5320 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5321 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5322 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5323 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5325 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5326 __first2, __last2, __result,
5327 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5330 template<
typename _InputIterator1,
typename _InputIterator2,
5331 typename _OutputIterator,
5333 _GLIBCXX20_CONSTEXPR
5335 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5336 _InputIterator2 __first2, _InputIterator2 __last2,
5337 _OutputIterator __result, _Compare __comp)
5339 while (__first1 != __last1 && __first2 != __last2)
5340 if (__comp(__first1, __first2))
5342 *__result = *__first1;
5346 else if (__comp(__first2, __first1))
5353 return std::copy(__first1, __last1, __result);
5376 template<
typename _InputIterator1,
typename _InputIterator2,
5377 typename _OutputIterator>
5378 _GLIBCXX20_CONSTEXPR
5379 inline _OutputIterator
5380 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5381 _InputIterator2 __first2, _InputIterator2 __last2,
5382 _OutputIterator __result)
5385 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5386 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5387 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5389 __glibcxx_function_requires(_LessThanOpConcept<
5392 __glibcxx_function_requires(_LessThanOpConcept<
5395 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5396 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5397 __glibcxx_requires_irreflexive2(__first1, __last1);
5398 __glibcxx_requires_irreflexive2(__first2, __last2);
5400 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5401 __first2, __last2, __result,
5402 __gnu_cxx::__ops::__iter_less_iter());
5428 template<
typename _InputIterator1,
typename _InputIterator2,
5429 typename _OutputIterator,
typename _Compare>
5430 _GLIBCXX20_CONSTEXPR
5431 inline _OutputIterator
5432 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5433 _InputIterator2 __first2, _InputIterator2 __last2,
5434 _OutputIterator __result, _Compare __comp)
5437 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5438 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5439 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5441 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5444 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5447 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5448 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5449 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5450 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5452 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5453 __first2, __last2, __result,
5454 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5457 template<
typename _InputIterator1,
typename _InputIterator2,
5458 typename _OutputIterator,
5460 _GLIBCXX20_CONSTEXPR
5462 __set_symmetric_difference(_InputIterator1 __first1,
5463 _InputIterator1 __last1,
5464 _InputIterator2 __first2,
5465 _InputIterator2 __last2,
5466 _OutputIterator __result,
5469 while (__first1 != __last1 && __first2 != __last2)
5470 if (__comp(__first1, __first2))
5472 *__result = *__first1;
5476 else if (__comp(__first2, __first1))
5478 *__result = *__first2;
5487 return std::copy(__first2, __last2,
5488 std::copy(__first1, __last1, __result));
5509 template<
typename _InputIterator1,
typename _InputIterator2,
5510 typename _OutputIterator>
5511 _GLIBCXX20_CONSTEXPR
5512 inline _OutputIterator
5513 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5514 _InputIterator2 __first2, _InputIterator2 __last2,
5515 _OutputIterator __result)
5518 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5519 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5520 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5522 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5524 __glibcxx_function_requires(_LessThanOpConcept<
5527 __glibcxx_function_requires(_LessThanOpConcept<
5530 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5531 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5532 __glibcxx_requires_irreflexive2(__first1, __last1);
5533 __glibcxx_requires_irreflexive2(__first2, __last2);
5535 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5536 __first2, __last2, __result,
5537 __gnu_cxx::__ops::__iter_less_iter());
5561 template<
typename _InputIterator1,
typename _InputIterator2,
5562 typename _OutputIterator,
typename _Compare>
5563 _GLIBCXX20_CONSTEXPR
5564 inline _OutputIterator
5565 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5566 _InputIterator2 __first2, _InputIterator2 __last2,
5567 _OutputIterator __result,
5571 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5572 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5573 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5575 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5577 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5580 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5583 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5584 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5585 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5586 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5588 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5589 __first2, __last2, __result,
5590 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5593 template<
typename _ForwardIterator,
typename _Compare>
5594 _GLIBCXX14_CONSTEXPR
5596 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5599 if (__first == __last)
5601 _ForwardIterator __result = __first;
5602 while (++__first != __last)
5603 if (__comp(__first, __result))
5615 template<
typename _ForwardIterator>
5616 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5618 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5621 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5622 __glibcxx_function_requires(_LessThanComparableConcept<
5624 __glibcxx_requires_valid_range(__first, __last);
5625 __glibcxx_requires_irreflexive(__first, __last);
5627 return _GLIBCXX_STD_A::__min_element(__first, __last,
5628 __gnu_cxx::__ops::__iter_less_iter());
5640 template<
typename _ForwardIterator,
typename _Compare>
5641 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5642 inline _ForwardIterator
5643 min_element(_ForwardIterator __first, _ForwardIterator __last,
5647 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5648 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5651 __glibcxx_requires_valid_range(__first, __last);
5652 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5654 return _GLIBCXX_STD_A::__min_element(__first, __last,
5655 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5658 template<
typename _ForwardIterator,
typename _Compare>
5659 _GLIBCXX14_CONSTEXPR
5661 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5664 if (__first == __last)
return __first;
5665 _ForwardIterator __result = __first;
5666 while (++__first != __last)
5667 if (__comp(__result, __first))
5679 template<
typename _ForwardIterator>
5680 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5681 inline _ForwardIterator
5682 max_element(_ForwardIterator __first, _ForwardIterator __last)
5685 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5686 __glibcxx_function_requires(_LessThanComparableConcept<
5688 __glibcxx_requires_valid_range(__first, __last);
5689 __glibcxx_requires_irreflexive(__first, __last);
5691 return _GLIBCXX_STD_A::__max_element(__first, __last,
5692 __gnu_cxx::__ops::__iter_less_iter());
5704 template<
typename _ForwardIterator,
typename _Compare>
5705 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5706 inline _ForwardIterator
5707 max_element(_ForwardIterator __first, _ForwardIterator __last,
5711 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5712 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5715 __glibcxx_requires_valid_range(__first, __last);
5716 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5718 return _GLIBCXX_STD_A::__max_element(__first, __last,
5719 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5722#if __cplusplus >= 201103L
5724 template<
typename _Tp>
5725 _GLIBCXX14_CONSTEXPR
5727 min(initializer_list<_Tp> __l)
5729 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5730 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5731 __gnu_cxx::__ops::__iter_less_iter());
5734 template<
typename _Tp,
typename _Compare>
5735 _GLIBCXX14_CONSTEXPR
5739 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5740 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5741 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5744 template<
typename _Tp>
5745 _GLIBCXX14_CONSTEXPR
5749 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5750 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5751 __gnu_cxx::__ops::__iter_less_iter());
5754 template<
typename _Tp,
typename _Compare>
5755 _GLIBCXX14_CONSTEXPR
5759 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5760 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5761 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5765#if __cplusplus >= 201402L
5767 template<
typename _InputIterator,
typename _RandomAccessIterator,
5768 typename _Size,
typename _UniformRandomBitGenerator>
5769 _RandomAccessIterator
5772 _Size __n, _UniformRandomBitGenerator&& __g)
5775 using __param_type =
typename __distrib_type::param_type;
5776 __distrib_type __d{};
5777 _Size __sample_sz = 0;
5778 while (__first != __last && __sample_sz != __n)
5780 __out[__sample_sz++] = *__first;
5783 for (
auto __pop_sz = __sample_sz; __first != __last;
5784 ++__first, (void) ++__pop_sz)
5786 const auto __k = __d(__g, __param_type{0, __pop_sz});
5788 __out[__k] = *__first;
5790 return __out + __sample_sz;
5794 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5795 typename _Size,
typename _UniformRandomBitGenerator>
5797 __sample(_ForwardIterator __first, _ForwardIterator __last,
5799 _OutputIterator __out, _Cat,
5800 _Size __n, _UniformRandomBitGenerator&& __g)
5803 using __param_type =
typename __distrib_type::param_type;
5808 if (__first == __last)
5811 __distrib_type __d{};
5813 __n =
std::min(__n, __unsampled_sz);
5818 const __uc_type __urngrange = __g.max() - __g.min();
5819 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5823 while (__n != 0 && __unsampled_sz >= 2)
5829 if (__p.
first < __n)
5831 *__out++ = *__first;
5837 if (__n == 0)
break;
5842 *__out++ = *__first;
5852 for (; __n != 0; ++__first)
5853 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5855 *__out++ = *__first;
5862#ifdef __glibcxx_sample
5864 template<typename _PopulationIterator, typename _SampleIterator,
5865 typename _Distance,
typename _UniformRandomBitGenerator>
5867 sample(_PopulationIterator __first, _PopulationIterator __last,
5868 _SampleIterator __out, _Distance __n,
5869 _UniformRandomBitGenerator&& __g)
5871 using __pop_cat =
typename
5873 using __samp_cat =
typename
5877 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5878 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5879 "output range must use a RandomAccessIterator when input range"
5880 " does not meet the ForwardIterator requirements");
5883 "sample size must be an integer type");
5886 return _GLIBCXX_STD_A::
5887 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5892_GLIBCXX_END_NAMESPACE_ALGO
5893_GLIBCXX_END_NAMESPACE_VERSION
5896#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...