64#if __cplusplus >= 201103L
70# if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
77namespace std _GLIBCXX_VISIBILITY(default)
79_GLIBCXX_BEGIN_NAMESPACE_VERSION
82 template<
typename _Iterator,
typename _Compare>
86 _Iterator __c, _Compare __comp)
91 std::iter_swap(__result, __b);
92 else if (__comp(__a, __c))
93 std::iter_swap(__result, __c);
95 std::iter_swap(__result, __a);
97 else if (__comp(__a, __c))
98 std::iter_swap(__result, __a);
99 else if (__comp(__b, __c))
100 std::iter_swap(__result, __c);
102 std::iter_swap(__result, __b);
106 template<
typename _InputIterator,
typename _Predicate>
108 inline _InputIterator
113 __gnu_cxx::__ops::__negate(__pred),
120 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
125 for (; __len; --__len, (void) ++__first)
126 if (!__pred(__first))
148 template<
typename _ForwardIterator,
typename _Integer,
149 typename _UnaryPredicate>
153 _Integer __count, _UnaryPredicate __unary_pred,
157 while (__first != __last)
161 _ForwardIterator __i = __first;
163 while (__i != __last && __n != 1 && __unary_pred(__i))
181 template<
typename _RandomAccessIter,
typename _Integer,
182 typename _UnaryPredicate>
186 _Integer __count, _UnaryPredicate __unary_pred,
192 _DistanceType __tailSize = __last - __first;
193 _DistanceType __remainder = __count;
195 while (__remainder <= __tailSize)
197 __first += __remainder;
198 __tailSize -= __remainder;
201 _RandomAccessIter __backTrack = __first;
202 while (__unary_pred(--__backTrack))
204 if (--__remainder == 0)
205 return (__first - __count);
207 __remainder = __count + 1 - (__first - __backTrack);
212 template<
typename _ForwardIterator,
typename _Integer,
213 typename _UnaryPredicate>
216 __search_n(_ForwardIterator __first, _ForwardIterator __last,
218 _UnaryPredicate __unary_pred)
231 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
232 typename _BinaryPredicate>
235 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
236 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
237 forward_iterator_tag, forward_iterator_tag,
238 _BinaryPredicate __comp)
240 if (__first2 == __last2)
243 _ForwardIterator1 __result = __last1;
246 _ForwardIterator1 __new_result
247 = std::__search(__first1, __last1, __first2, __last2, __comp);
248 if (__new_result == __last1)
252 __result = __new_result;
253 __first1 = __new_result;
260 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
261 typename _BinaryPredicate>
263 _BidirectionalIterator1
264 __find_end(_BidirectionalIterator1 __first1,
265 _BidirectionalIterator1 __last1,
266 _BidirectionalIterator2 __first2,
267 _BidirectionalIterator2 __last2,
268 bidirectional_iterator_tag, bidirectional_iterator_tag,
269 _BinaryPredicate __comp)
272 __glibcxx_function_requires(_BidirectionalIteratorConcept<
273 _BidirectionalIterator1>)
274 __glibcxx_function_requires(_BidirectionalIteratorConcept<
275 _BidirectionalIterator2>)
277 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
278 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
280 _RevIterator1 __rlast1(__first1);
281 _RevIterator2 __rlast2(__first2);
282 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
283 _RevIterator2(__last2), __rlast2,
286 if (__rresult == __rlast1)
290 _BidirectionalIterator1 __result = __rresult.base();
322 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
323 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
324 inline _ForwardIterator1
325 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
326 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
329 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
330 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
331 __glibcxx_function_requires(_EqualOpConcept<
334 __glibcxx_requires_valid_range(__first1, __last1);
335 __glibcxx_requires_valid_range(__first2, __last2);
337 return std::__find_end(__first1, __last1, __first2, __last2,
340 __gnu_cxx::__ops::__iter_equal_to_iter());
371 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
372 typename _BinaryPredicate>
373 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
374 inline _ForwardIterator1
375 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
376 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
377 _BinaryPredicate __comp)
380 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
381 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
382 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
385 __glibcxx_requires_valid_range(__first1, __last1);
386 __glibcxx_requires_valid_range(__first2, __last2);
388 return std::__find_end(__first1, __last1, __first2, __last2,
391 __gnu_cxx::__ops::__iter_comp_iter(__comp));
394#if __cplusplus >= 201103L
407 template<
typename _InputIterator,
typename _Predicate>
408 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
410 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
411 {
return __last == std::find_if_not(__first, __last, __pred); }
425 template<
typename _InputIterator,
typename _Predicate>
426 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
428 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
429 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
444 template<
typename _InputIterator,
typename _Predicate>
445 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
447 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
448 {
return !std::none_of(__first, __last, __pred); }
460 template<
typename _InputIterator,
typename _Predicate>
461 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
462 inline _InputIterator
463 find_if_not(_InputIterator __first, _InputIterator __last,
467 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
468 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
470 __glibcxx_requires_valid_range(__first, __last);
472 __gnu_cxx::__ops::__pred_iter(__pred));
485 template<
typename _InputIterator,
typename _Predicate>
486 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
488 is_partitioned(_InputIterator __first, _InputIterator __last,
491 __first = std::find_if_not(__first, __last, __pred);
492 if (__first == __last)
495 return std::none_of(__first, __last, __pred);
507 template<
typename _ForwardIterator,
typename _Predicate>
508 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
510 partition_point(_ForwardIterator __first, _ForwardIterator __last,
514 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
515 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
519 __glibcxx_requires_valid_range(__first, __last);
528 _DistanceType __half = __len >> 1;
529 _ForwardIterator __middle = __first;
531 if (__pred(*__middle))
535 __len = __len - __half - 1;
544 template<
typename _InputIterator,
typename _OutputIterator,
548 __remove_copy_if(_InputIterator __first, _InputIterator __last,
549 _OutputIterator __result, _Predicate __pred)
551 for (; __first != __last; ++__first)
552 if (!__pred(__first))
554 *__result = *__first;
574 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
576 inline _OutputIterator
577 remove_copy(_InputIterator __first, _InputIterator __last,
578 _OutputIterator __result,
const _Tp& __value)
581 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
582 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
584 __glibcxx_function_requires(_EqualOpConcept<
586 __glibcxx_requires_valid_range(__first, __last);
588 return std::__remove_copy_if(__first, __last, __result,
589 __gnu_cxx::__ops::__iter_equals_val(__value));
607 template<
typename _InputIterator,
typename _OutputIterator,
610 inline _OutputIterator
611 remove_copy_if(_InputIterator __first, _InputIterator __last,
612 _OutputIterator __result, _Predicate __pred)
615 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
616 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
618 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
620 __glibcxx_requires_valid_range(__first, __last);
622 return std::__remove_copy_if(__first, __last, __result,
623 __gnu_cxx::__ops::__pred_iter(__pred));
626#if __cplusplus >= 201103L
642 template<
typename _InputIterator,
typename _OutputIterator,
646 copy_if(_InputIterator __first, _InputIterator __last,
647 _OutputIterator __result, _Predicate __pred)
650 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
651 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
653 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
655 __glibcxx_requires_valid_range(__first, __last);
657 for (; __first != __last; ++__first)
658 if (__pred(*__first))
660 *__result = *__first;
666 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
669 __copy_n(_InputIterator __first, _Size __n,
670 _OutputIterator __result, input_iterator_tag)
672 return std::__niter_wrap(__result,
673 __copy_n_a(__first, __n,
674 std::__niter_base(__result),
true));
677 template<
typename _RandomAccessIterator,
typename _Size,
678 typename _OutputIterator>
680 inline _OutputIterator
681 __copy_n(_RandomAccessIterator __first, _Size __n,
682 _OutputIterator __result, random_access_iterator_tag)
683 {
return std::copy(__first, __first + __n, __result); }
698 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
700 inline _OutputIterator
701 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
704 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
705 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
708 const auto __n2 = std::__size_to_integer(__n);
712 __glibcxx_requires_can_increment(__first, __n2);
713 __glibcxx_requires_can_increment(__result, __n2);
715 return std::__copy_n(__first, __n2, __result,
734 template<
typename _InputIterator,
typename _OutputIterator1,
735 typename _OutputIterator2,
typename _Predicate>
738 partition_copy(_InputIterator __first, _InputIterator __last,
739 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
743 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
744 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
746 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
748 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
750 __glibcxx_requires_valid_range(__first, __last);
752 for (; __first != __last; ++__first)
753 if (__pred(*__first))
755 *__out_true = *__first;
760 *__out_false = *__first;
785 template<
typename _ForwardIterator,
typename _Tp>
786 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
787 inline _ForwardIterator
788 remove(_ForwardIterator __first, _ForwardIterator __last,
792 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
794 __glibcxx_function_requires(_EqualOpConcept<
796 __glibcxx_requires_valid_range(__first, __last);
798 return std::__remove_if(__first, __last,
799 __gnu_cxx::__ops::__iter_equals_val(__value));
819 template<
typename _ForwardIterator,
typename _Predicate>
820 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
821 inline _ForwardIterator
822 remove_if(_ForwardIterator __first, _ForwardIterator __last,
826 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
828 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
830 __glibcxx_requires_valid_range(__first, __last);
832 return std::__remove_if(__first, __last,
833 __gnu_cxx::__ops::__pred_iter(__pred));
836 template<
typename _ForwardIterator,
typename _BinaryPredicate>
839 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
840 _BinaryPredicate __binary_pred)
842 if (__first == __last)
844 _ForwardIterator __next = __first;
845 while (++__next != __last)
847 if (__binary_pred(__first, __next))
854 template<
typename _ForwardIterator,
typename _BinaryPredicate>
857 __unique(_ForwardIterator __first, _ForwardIterator __last,
858 _BinaryPredicate __binary_pred)
861 __first = std::__adjacent_find(__first, __last, __binary_pred);
862 if (__first == __last)
866 _ForwardIterator __dest = __first;
868 while (++__first != __last)
869 if (!__binary_pred(__dest, __first))
870 *++__dest = _GLIBCXX_MOVE(*__first);
888 template<
typename _ForwardIterator>
889 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
890 inline _ForwardIterator
891 unique(_ForwardIterator __first, _ForwardIterator __last)
894 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
896 __glibcxx_function_requires(_EqualityComparableConcept<
898 __glibcxx_requires_valid_range(__first, __last);
900 return std::__unique(__first, __last,
901 __gnu_cxx::__ops::__iter_equal_to_iter());
919 template<
typename _ForwardIterator,
typename _BinaryPredicate>
920 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
921 inline _ForwardIterator
922 unique(_ForwardIterator __first, _ForwardIterator __last,
923 _BinaryPredicate __binary_pred)
926 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
928 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
931 __glibcxx_requires_valid_range(__first, __last);
933 return std::__unique(__first, __last,
934 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
943 template<
typename _ForwardIterator,
typename _OutputIterator,
944 typename _BinaryPredicate>
948 _OutputIterator __result, _BinaryPredicate __binary_pred,
952 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
956 _ForwardIterator __next = __first;
957 *__result = *__first;
958 while (++__next != __last)
959 if (!__binary_pred(__first, __next))
962 *++__result = *__first;
973 template<
typename _InputIterator,
typename _OutputIterator,
974 typename _BinaryPredicate>
978 _OutputIterator __result, _BinaryPredicate __binary_pred,
982 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
987 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
989 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
991 while (++__first != __last)
992 if (!__rebound_pred(__first, __value))
995 *++__result = __value;
1006 template<
typename _InputIterator,
typename _ForwardIterator,
1007 typename _BinaryPredicate>
1008 _GLIBCXX20_CONSTEXPR
1011 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1015 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1018 *__result = *__first;
1019 while (++__first != __last)
1020 if (!__binary_pred(__result, __first))
1021 *++__result = *__first;
1030 template<
typename _B
idirectionalIterator>
1031 _GLIBCXX20_CONSTEXPR
1033 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1037 if (__first == __last || __first == --__last)
1041 std::iter_swap(__first, __last);
1051 template<
typename _RandomAccessIterator>
1052 _GLIBCXX20_CONSTEXPR
1054 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1057 if (__first == __last)
1060 while (__first < __last)
1062 std::iter_swap(__first, __last);
1080 template<
typename _B
idirectionalIterator>
1081 _GLIBCXX20_CONSTEXPR
1083 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1086 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1087 _BidirectionalIterator>)
1088 __glibcxx_requires_valid_range(__first, __last);
1108 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1109 _GLIBCXX20_CONSTEXPR
1111 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1112 _OutputIterator __result)
1115 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1116 _BidirectionalIterator>)
1117 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1119 __glibcxx_requires_valid_range(__first, __last);
1121 while (__first != __last)
1124 *__result = *__last;
1134 template<
typename _Eucl
ideanRingElement>
1135 _GLIBCXX20_CONSTEXPR
1136 _EuclideanRingElement
1137 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1141 _EuclideanRingElement __t = __m % __n;
1148_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1151 template<
typename _ForwardIterator>
1152 _GLIBCXX20_CONSTEXPR
1155 _ForwardIterator __middle,
1156 _ForwardIterator __last,
1159 if (__first == __middle)
1161 else if (__last == __middle)
1164 _ForwardIterator __first2 = __middle;
1167 std::iter_swap(__first, __first2);
1170 if (__first == __middle)
1171 __middle = __first2;
1173 while (__first2 != __last);
1175 _ForwardIterator __ret = __first;
1177 __first2 = __middle;
1179 while (__first2 != __last)
1181 std::iter_swap(__first, __first2);
1184 if (__first == __middle)
1185 __middle = __first2;
1186 else if (__first2 == __last)
1187 __first2 = __middle;
1193 template<
typename _B
idirectionalIterator>
1194 _GLIBCXX20_CONSTEXPR
1195 _BidirectionalIterator
1197 _BidirectionalIterator __middle,
1198 _BidirectionalIterator __last,
1202 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1203 _BidirectionalIterator>)
1205 if (__first == __middle)
1207 else if (__last == __middle)
1213 while (__first != __middle && __middle != __last)
1215 std::iter_swap(__first, --__last);
1219 if (__first == __middle)
1232 template<
typename _RandomAccessIterator>
1233 _GLIBCXX20_CONSTEXPR
1234 _RandomAccessIterator
1236 _RandomAccessIterator __middle,
1237 _RandomAccessIterator __last,
1241 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1242 _RandomAccessIterator>)
1244 if (__first == __middle)
1246 else if (__last == __middle)
1254#if __cplusplus >= 201103L
1255 typedef typename make_unsigned<_Distance>::type _UDistance;
1257 typedef _Distance _UDistance;
1260 _Distance __n = __last - __first;
1261 _Distance __k = __middle - __first;
1263 if (__k == __n - __k)
1265 std::swap_ranges(__first, __middle, __middle);
1269 _RandomAccessIterator __p = __first;
1270 _RandomAccessIterator __ret = __first + (__last - __middle);
1274 if (__k < __n - __k)
1276 if (__is_pod(_ValueType) && __k == 1)
1278 _ValueType __t = _GLIBCXX_MOVE(*__p);
1279 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1280 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1283 _RandomAccessIterator __q = __p + __k;
1284 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1286 std::iter_swap(__p, __q);
1290 __n =
static_cast<_UDistance
>(__n) %
static_cast<_UDistance
>(__k);
1293 std::swap(__n, __k);
1299 if (__is_pod(_ValueType) && __k == 1)
1301 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1302 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1303 *__p = _GLIBCXX_MOVE(__t);
1306 _RandomAccessIterator __q = __p + __n;
1308 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1312 std::iter_swap(__p, __q);
1314 __n =
static_cast<_UDistance
>(__n) %
static_cast<_UDistance
>(__k);
1317 std::swap(__n, __k);
1345 template<
typename _ForwardIterator>
1346 _GLIBCXX20_CONSTEXPR
1347 inline _ForwardIterator
1348 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1349 _ForwardIterator __last)
1352 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1354 __glibcxx_requires_valid_range(__first, __middle);
1355 __glibcxx_requires_valid_range(__middle, __last);
1361_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1383 template<
typename _ForwardIterator,
typename _OutputIterator>
1384 _GLIBCXX20_CONSTEXPR
1385 inline _OutputIterator
1386 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1387 _ForwardIterator __last, _OutputIterator __result)
1390 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1391 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1393 __glibcxx_requires_valid_range(__first, __middle);
1394 __glibcxx_requires_valid_range(__middle, __last);
1396 return std::copy(__first, __middle,
1397 std::copy(__middle, __last, __result));
1401 template<
typename _ForwardIterator,
typename _Predicate>
1402 _GLIBCXX20_CONSTEXPR
1407 if (__first == __last)
1410 while (__pred(*__first))
1411 if (++__first == __last)
1414 _ForwardIterator __next = __first;
1416 while (++__next != __last)
1417 if (__pred(*__next))
1419 std::iter_swap(__first, __next);
1427 template<
typename _B
idirectionalIterator,
typename _Predicate>
1428 _GLIBCXX20_CONSTEXPR
1429 _BidirectionalIterator
1430 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1436 if (__first == __last)
1438 else if (__pred(*__first))
1444 if (__first == __last)
1446 else if (!
bool(__pred(*__last)))
1450 std::iter_swap(__first, __last);
1464 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1468 _ForwardIterator __last,
1469 _Predicate __pred, _Distance __len,
1471 _Distance __buffer_size)
1476 if (__len <= __buffer_size)
1478 _ForwardIterator __result1 = __first;
1479 _Pointer __result2 = __buffer;
1484 *__result2 = _GLIBCXX_MOVE(*__first);
1487 for (; __first != __last; ++__first)
1488 if (__pred(__first))
1490 *__result1 = _GLIBCXX_MOVE(*__first);
1495 *__result2 = _GLIBCXX_MOVE(*__first);
1499 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1503 _ForwardIterator __middle = __first;
1505 _ForwardIterator __left_split =
1507 __len / 2, __buffer,
1512 _Distance __right_len = __len - __len / 2;
1513 _ForwardIterator __right_split =
1520 __buffer, __buffer_size);
1522 return std::rotate(__left_split, __middle, __right_split);
1525 template<
typename _ForwardIterator,
typename _Predicate>
1527 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1532 if (__first == __last)
1535 typedef typename iterator_traits<_ForwardIterator>::value_type
1537 typedef typename iterator_traits<_ForwardIterator>::difference_type
1540 _Temporary_buffer<_ForwardIterator, _ValueType>
1544 _DistanceType(__buf.requested_size()),
1546 _DistanceType(__buf.size()));
1566 template<
typename _ForwardIterator,
typename _Predicate>
1567 inline _ForwardIterator
1568 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1572 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1574 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1576 __glibcxx_requires_valid_range(__first, __last);
1578 return std::__stable_partition(__first, __last,
1579 __gnu_cxx::__ops::__pred_iter(__pred));
1586 template<
typename _RandomAccessIterator,
typename _Compare>
1587 _GLIBCXX20_CONSTEXPR
1589 __heap_select(_RandomAccessIterator __first,
1590 _RandomAccessIterator __middle,
1591 _RandomAccessIterator __last, _Compare __comp)
1593 std::__make_heap(__first, __middle, __comp);
1594 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1595 if (__comp(__i, __first))
1596 std::__pop_heap(__first, __middle, __i, __comp);
1601 template<
typename _InputIterator,
typename _RandomAccessIterator,
1603 _GLIBCXX20_CONSTEXPR
1604 _RandomAccessIterator
1605 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1606 _RandomAccessIterator __result_first,
1607 _RandomAccessIterator __result_last,
1610 typedef typename iterator_traits<_InputIterator>::value_type
1612 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1613 typedef typename _RItTraits::difference_type _DistanceType;
1615 if (__result_first == __result_last)
1616 return __result_last;
1617 _RandomAccessIterator __result_real_last = __result_first;
1618 while (__first != __last && __result_real_last != __result_last)
1620 *__result_real_last = *__first;
1621 ++__result_real_last;
1625 std::__make_heap(__result_first, __result_real_last, __comp);
1626 while (__first != __last)
1628 if (__comp(__first, __result_first))
1629 std::__adjust_heap(__result_first, _DistanceType(0),
1630 _DistanceType(__result_real_last
1632 _InputValueType(*__first), __comp);
1635 std::__sort_heap(__result_first, __result_real_last, __comp);
1636 return __result_real_last;
1659 template<
typename _InputIterator,
typename _RandomAccessIterator>
1660 _GLIBCXX20_CONSTEXPR
1661 inline _RandomAccessIterator
1662 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1663 _RandomAccessIterator __result_first,
1664 _RandomAccessIterator __result_last)
1666#ifdef _GLIBCXX_CONCEPT_CHECKS
1674 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1675 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1677 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1679 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1680 __glibcxx_requires_valid_range(__first, __last);
1681 __glibcxx_requires_irreflexive(__first, __last);
1682 __glibcxx_requires_valid_range(__result_first, __result_last);
1684 return std::__partial_sort_copy(__first, __last,
1685 __result_first, __result_last,
1686 __gnu_cxx::__ops::__iter_less_iter());
1709 template<
typename _InputIterator,
typename _RandomAccessIterator,
1711 _GLIBCXX20_CONSTEXPR
1712 inline _RandomAccessIterator
1713 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1714 _RandomAccessIterator __result_first,
1715 _RandomAccessIterator __result_last,
1718#ifdef _GLIBCXX_CONCEPT_CHECKS
1726 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1727 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1728 _RandomAccessIterator>)
1729 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1731 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1732 _InputValueType, _OutputValueType>)
1733 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1734 _OutputValueType, _OutputValueType>)
1735 __glibcxx_requires_valid_range(__first, __last);
1736 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1737 __glibcxx_requires_valid_range(__result_first, __result_last);
1739 return std::__partial_sort_copy(__first, __last,
1740 __result_first, __result_last,
1741 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1747 template<
typename _RandomAccessIterator,
typename _Compare>
1748 _GLIBCXX20_CONSTEXPR
1750 __unguarded_linear_insert(_RandomAccessIterator __last,
1753 typename iterator_traits<_RandomAccessIterator>::value_type
1754 __val = _GLIBCXX_MOVE(*__last);
1755 _RandomAccessIterator __next = __last;
1757 while (__comp(__val, __next))
1759 *__last = _GLIBCXX_MOVE(*__next);
1763 *__last = _GLIBCXX_MOVE(__val);
1767 template<
typename _RandomAccessIterator,
typename _Compare>
1768 _GLIBCXX20_CONSTEXPR
1770 __insertion_sort(_RandomAccessIterator __first,
1771 _RandomAccessIterator __last, _Compare __comp)
1773 if (__first == __last)
return;
1775 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1777 if (__comp(__i, __first))
1779 typename iterator_traits<_RandomAccessIterator>::value_type
1780 __val = _GLIBCXX_MOVE(*__i);
1781 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1782 *__first = _GLIBCXX_MOVE(__val);
1785 std::__unguarded_linear_insert(__i,
1786 __gnu_cxx::__ops::__val_comp_iter(__comp));
1791 template<
typename _RandomAccessIterator,
typename _Compare>
1792 _GLIBCXX20_CONSTEXPR
1794 __unguarded_insertion_sort(_RandomAccessIterator __first,
1795 _RandomAccessIterator __last, _Compare __comp)
1797 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1798 std::__unguarded_linear_insert(__i,
1799 __gnu_cxx::__ops::__val_comp_iter(__comp));
1806 enum { _S_threshold = 16 };
1809 template<
typename _RandomAccessIterator,
typename _Compare>
1810 _GLIBCXX20_CONSTEXPR
1812 __final_insertion_sort(_RandomAccessIterator __first,
1813 _RandomAccessIterator __last, _Compare __comp)
1815 if (__last - __first >
int(_S_threshold))
1817 std::__insertion_sort(__first, __first +
int(_S_threshold), __comp);
1818 std::__unguarded_insertion_sort(__first +
int(_S_threshold), __last,
1822 std::__insertion_sort(__first, __last, __comp);
1826 template<
typename _RandomAccessIterator,
typename _Compare>
1827 _GLIBCXX20_CONSTEXPR
1828 _RandomAccessIterator
1829 __unguarded_partition(_RandomAccessIterator __first,
1830 _RandomAccessIterator __last,
1831 _RandomAccessIterator __pivot, _Compare __comp)
1835 while (__comp(__first, __pivot))
1838 while (__comp(__pivot, __last))
1840 if (!(__first < __last))
1842 std::iter_swap(__first, __last);
1848 template<
typename _RandomAccessIterator,
typename _Compare>
1849 _GLIBCXX20_CONSTEXPR
1850 inline _RandomAccessIterator
1851 __unguarded_partition_pivot(_RandomAccessIterator __first,
1852 _RandomAccessIterator __last, _Compare __comp)
1854 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1857 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1860 template<
typename _RandomAccessIterator,
typename _Compare>
1861 _GLIBCXX20_CONSTEXPR
1863 __partial_sort(_RandomAccessIterator __first,
1864 _RandomAccessIterator __middle,
1865 _RandomAccessIterator __last,
1868 std::__heap_select(__first, __middle, __last, __comp);
1869 std::__sort_heap(__first, __middle, __comp);
1873 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1874 _GLIBCXX20_CONSTEXPR
1876 __introsort_loop(_RandomAccessIterator __first,
1877 _RandomAccessIterator __last,
1878 _Size __depth_limit, _Compare __comp)
1880 while (__last - __first >
int(_S_threshold))
1882 if (__depth_limit == 0)
1884 std::__partial_sort(__first, __last, __last, __comp);
1888 _RandomAccessIterator __cut =
1889 std::__unguarded_partition_pivot(__first, __last, __comp);
1890 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1897 template<
typename _RandomAccessIterator,
typename _Compare>
1898 _GLIBCXX20_CONSTEXPR
1900 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1903 if (__first != __last)
1905 std::__introsort_loop(__first, __last,
1908 std::__final_insertion_sort(__first, __last, __comp);
1912 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1913 _GLIBCXX20_CONSTEXPR
1915 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1916 _RandomAccessIterator __last, _Size __depth_limit,
1919 while (__last - __first > 3)
1921 if (__depth_limit == 0)
1923 std::__heap_select(__first, __nth + 1, __last, __comp);
1925 std::iter_swap(__first, __nth);
1929 _RandomAccessIterator __cut =
1930 std::__unguarded_partition_pivot(__first, __last, __comp);
1936 std::__insertion_sort(__first, __last, __comp);
1960 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1961 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1962 inline _ForwardIterator
1963 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1964 const _Tp& __val, _Compare __comp)
1967 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1968 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1970 __glibcxx_requires_partitioned_lower_pred(__first, __last,
1973 return std::__lower_bound(__first, __last, __val,
1974 __gnu_cxx::__ops::__iter_comp_val(__comp));
1977 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1978 _GLIBCXX20_CONSTEXPR
1980 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
1981 const _Tp& __val, _Compare __comp)
1983 typedef typename iterator_traits<_ForwardIterator>::difference_type
1990 _DistanceType __half = __len >> 1;
1991 _ForwardIterator __middle = __first;
1993 if (__comp(__val, __middle))
1999 __len = __len - __half - 1;
2016 template<
typename _ForwardIterator,
typename _Tp>
2017 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2018 inline _ForwardIterator
2019 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2023 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2024 __glibcxx_function_requires(_LessThanOpConcept<
2026 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2028 return std::__upper_bound(__first, __last, __val,
2029 __gnu_cxx::__ops::__val_less_iter());
2047 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2048 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2049 inline _ForwardIterator
2050 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2051 const _Tp& __val, _Compare __comp)
2054 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2055 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2057 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2060 return std::__upper_bound(__first, __last, __val,
2061 __gnu_cxx::__ops::__val_comp_iter(__comp));
2064 template<
typename _ForwardIterator,
typename _Tp,
2065 typename _CompareItTp,
typename _CompareTpIt>
2066 _GLIBCXX20_CONSTEXPR
2068 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2070 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2072 typedef typename iterator_traits<_ForwardIterator>::difference_type
2079 _DistanceType __half = __len >> 1;
2080 _ForwardIterator __middle = __first;
2082 if (__comp_it_val(__middle, __val))
2086 __len = __len - __half - 1;
2088 else if (__comp_val_it(__val, __middle))
2092 _ForwardIterator __left
2093 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2095 _ForwardIterator __right
2096 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2120 template<
typename _ForwardIterator,
typename _Tp>
2121 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2123 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2127 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2128 __glibcxx_function_requires(_LessThanOpConcept<
2130 __glibcxx_function_requires(_LessThanOpConcept<
2132 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2133 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2135 return std::__equal_range(__first, __last, __val,
2136 __gnu_cxx::__ops::__iter_less_val(),
2137 __gnu_cxx::__ops::__val_less_iter());
2157 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2158 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2160 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2161 const _Tp& __val, _Compare __comp)
2164 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2165 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2167 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2169 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2171 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2174 return std::__equal_range(__first, __last, __val,
2175 __gnu_cxx::__ops::__iter_comp_val(__comp),
2176 __gnu_cxx::__ops::__val_comp_iter(__comp));
2191 template<
typename _ForwardIterator,
typename _Tp>
2192 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2194 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2198 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2199 __glibcxx_function_requires(_LessThanOpConcept<
2201 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2202 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2204 _ForwardIterator __i
2205 = std::__lower_bound(__first, __last, __val,
2206 __gnu_cxx::__ops::__iter_less_val());
2207 return __i != __last && !(__val < *__i);
2225 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2226 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2228 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2229 const _Tp& __val, _Compare __comp)
2232 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2235 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2237 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2240 _ForwardIterator __i
2241 = std::__lower_bound(__first, __last, __val,
2242 __gnu_cxx::__ops::__iter_comp_val(__comp));
2243 return __i != __last && !bool(__comp(__val, *__i));
2249 template<
typename _InputIterator1,
typename _InputIterator2,
2250 typename _OutputIterator,
typename _Compare>
2253 _InputIterator2 __first2, _InputIterator2 __last2,
2254 _OutputIterator __result, _Compare __comp)
2256 while (__first1 != __last1 && __first2 != __last2)
2258 if (__comp(__first2, __first1))
2260 *__result = _GLIBCXX_MOVE(*__first2);
2265 *__result = _GLIBCXX_MOVE(*__first1);
2270 if (__first1 != __last1)
2271 _GLIBCXX_MOVE3(__first1, __last1, __result);
2275 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2276 typename _BidirectionalIterator3,
typename _Compare>
2279 _BidirectionalIterator1 __last1,
2280 _BidirectionalIterator2 __first2,
2281 _BidirectionalIterator2 __last2,
2282 _BidirectionalIterator3 __result,
2285 if (__first1 == __last1)
2287 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2290 else if (__first2 == __last2)
2297 if (__comp(__last2, __last1))
2299 *--__result = _GLIBCXX_MOVE(*__last1);
2300 if (__first1 == __last1)
2302 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2309 *--__result = _GLIBCXX_MOVE(*__last2);
2310 if (__first2 == __last2)
2318 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2320 _BidirectionalIterator1
2322 _BidirectionalIterator1 __middle,
2323 _BidirectionalIterator1 __last,
2324 _Distance __len1, _Distance __len2,
2325 _BidirectionalIterator2 __buffer,
2326 _Distance __buffer_size)
2328 _BidirectionalIterator2 __buffer_end;
2329 if (__len1 > __len2 && __len2 <= __buffer_size)
2333 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2334 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2335 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2340 else if (__len1 <= __buffer_size)
2344 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2345 _GLIBCXX_MOVE3(__middle, __last, __first);
2346 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2352 return std::rotate(__first, __middle, __last);
2356 template<
typename _BidirectionalIterator,
typename _Distance,
2357 typename _Pointer,
typename _Compare>
2360 _BidirectionalIterator __middle,
2361 _BidirectionalIterator __last,
2362 _Distance __len1, _Distance __len2,
2363 _Pointer __buffer, _Compare __comp)
2365 if (__len1 <= __len2)
2367 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2373 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2375 __buffer_end, __last, __comp);
2379 template<
typename _BidirectionalIterator,
typename _Distance,
2380 typename _Pointer,
typename _Compare>
2382 __merge_adaptive_resize(_BidirectionalIterator __first,
2383 _BidirectionalIterator __middle,
2384 _BidirectionalIterator __last,
2385 _Distance __len1, _Distance __len2,
2386 _Pointer __buffer, _Distance __buffer_size,
2389 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2391 __len1, __len2, __buffer, __comp);
2394 _BidirectionalIterator __first_cut = __first;
2395 _BidirectionalIterator __second_cut = __middle;
2396 _Distance __len11 = 0;
2397 _Distance __len22 = 0;
2398 if (__len1 > __len2)
2400 __len11 = __len1 / 2;
2403 = std::__lower_bound(__middle, __last, *__first_cut,
2404 __gnu_cxx::__ops::__iter_comp_val(__comp));
2409 __len22 = __len2 / 2;
2412 = std::__upper_bound(__first, __middle, *__second_cut,
2413 __gnu_cxx::__ops::__val_comp_iter(__comp));
2417 _BidirectionalIterator __new_middle
2419 _Distance(__len1 - __len11), __len22,
2420 __buffer, __buffer_size);
2421 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2423 __buffer, __buffer_size, __comp);
2424 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2425 _Distance(__len1 - __len11),
2426 _Distance(__len2 - __len22),
2427 __buffer, __buffer_size, __comp);
2432 template<
typename _BidirectionalIterator,
typename _Distance,
2436 _BidirectionalIterator __middle,
2437 _BidirectionalIterator __last,
2438 _Distance __len1, _Distance __len2,
2441 if (__len1 == 0 || __len2 == 0)
2444 if (__len1 + __len2 == 2)
2446 if (__comp(__middle, __first))
2447 std::iter_swap(__first, __middle);
2451 _BidirectionalIterator __first_cut = __first;
2452 _BidirectionalIterator __second_cut = __middle;
2453 _Distance __len11 = 0;
2454 _Distance __len22 = 0;
2455 if (__len1 > __len2)
2457 __len11 = __len1 / 2;
2460 = std::__lower_bound(__middle, __last, *__first_cut,
2461 __gnu_cxx::__ops::__iter_comp_val(__comp));
2466 __len22 = __len2 / 2;
2469 = std::__upper_bound(__first, __middle, *__second_cut,
2470 __gnu_cxx::__ops::__val_comp_iter(__comp));
2474 _BidirectionalIterator __new_middle
2475 = std::rotate(__first_cut, __middle, __second_cut);
2477 __len11, __len22, __comp);
2479 __len1 - __len11, __len2 - __len22, __comp);
2482 template<
typename _B
idirectionalIterator,
typename _Compare>
2484 __inplace_merge(_BidirectionalIterator __first,
2485 _BidirectionalIterator __middle,
2486 _BidirectionalIterator __last,
2489 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2491 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2494 if (__first == __middle || __middle == __last)
2497 const _DistanceType __len1 =
std::distance(__first, __middle);
2498 const _DistanceType __len2 =
std::distance(__middle, __last);
2501 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2504 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2506 if (__builtin_expect(__buf.size() == __buf.requested_size(),
true))
2508 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2509 else if (__builtin_expect(__buf.begin() == 0,
false))
2511 (__first, __middle, __last, __len1, __len2, __comp);
2513 std::__merge_adaptive_resize
2514 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2515 _DistanceType(__buf.size()), __comp);
2518 (__first, __middle, __last, __len1, __len2, __comp);
2540 template<
typename _B
idirectionalIterator>
2542 inplace_merge(_BidirectionalIterator __first,
2543 _BidirectionalIterator __middle,
2544 _BidirectionalIterator __last)
2547 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2548 _BidirectionalIterator>)
2549 __glibcxx_function_requires(_LessThanComparableConcept<
2551 __glibcxx_requires_sorted(__first, __middle);
2552 __glibcxx_requires_sorted(__middle, __last);
2553 __glibcxx_requires_irreflexive(__first, __last);
2555 std::__inplace_merge(__first, __middle, __last,
2556 __gnu_cxx::__ops::__iter_less_iter());
2581 template<
typename _B
idirectionalIterator,
typename _Compare>
2583 inplace_merge(_BidirectionalIterator __first,
2584 _BidirectionalIterator __middle,
2585 _BidirectionalIterator __last,
2589 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2590 _BidirectionalIterator>)
2591 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2594 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2595 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2596 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2598 std::__inplace_merge(__first, __middle, __last,
2599 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2604 template<
typename _InputIterator,
typename _OutputIterator,
2608 _InputIterator __first2, _InputIterator __last2,
2609 _OutputIterator __result, _Compare __comp)
2611 while (__first1 != __last1 && __first2 != __last2)
2613 if (__comp(__first2, __first1))
2615 *__result = _GLIBCXX_MOVE(*__first2);
2620 *__result = _GLIBCXX_MOVE(*__first1);
2625 return _GLIBCXX_MOVE3(__first2, __last2,
2626 _GLIBCXX_MOVE3(__first1, __last1,
2630 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2631 typename _Distance,
typename _Compare>
2633 __merge_sort_loop(_RandomAccessIterator1 __first,
2634 _RandomAccessIterator1 __last,
2635 _RandomAccessIterator2 __result, _Distance __step_size,
2638 const _Distance __two_step = 2 * __step_size;
2640 while (__last - __first >= __two_step)
2643 __first + __step_size,
2644 __first + __two_step,
2646 __first += __two_step;
2648 __step_size =
std::min(_Distance(__last - __first), __step_size);
2651 __first + __step_size, __last, __result, __comp);
2654 template<
typename _RandomAccessIterator,
typename _Distance,
2656 _GLIBCXX20_CONSTEXPR
2658 __chunk_insertion_sort(_RandomAccessIterator __first,
2659 _RandomAccessIterator __last,
2660 _Distance __chunk_size, _Compare __comp)
2662 while (__last - __first >= __chunk_size)
2664 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2665 __first += __chunk_size;
2667 std::__insertion_sort(__first, __last, __comp);
2670 enum { _S_chunk_size = 7 };
2672 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2674 __merge_sort_with_buffer(_RandomAccessIterator __first,
2675 _RandomAccessIterator __last,
2676 _Pointer __buffer, _Compare __comp)
2678 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2681 const _Distance __len = __last - __first;
2682 const _Pointer __buffer_last = __buffer + __len;
2684 _Distance __step_size = _S_chunk_size;
2685 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2687 while (__step_size < __len)
2689 std::__merge_sort_loop(__first, __last, __buffer,
2690 __step_size, __comp);
2692 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2693 __step_size, __comp);
2698 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2700 __stable_sort_adaptive(_RandomAccessIterator __first,
2701 _RandomAccessIterator __middle,
2702 _RandomAccessIterator __last,
2703 _Pointer __buffer, _Compare __comp)
2705 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2706 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2709 __middle - __first, __last - __middle,
2713 template<
typename _RandomAccessIterator,
typename _Pointer,
2714 typename _Distance,
typename _Compare>
2716 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2717 _RandomAccessIterator __last,
2718 _Pointer __buffer, _Distance __buffer_size,
2721 const _Distance __len = (__last - __first + 1) / 2;
2722 const _RandomAccessIterator __middle = __first + __len;
2723 if (__len > __buffer_size)
2725 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2726 __buffer_size, __comp);
2727 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2728 __buffer_size, __comp);
2729 std::__merge_adaptive_resize(__first, __middle, __last,
2730 _Distance(__middle - __first),
2731 _Distance(__last - __middle),
2732 __buffer, __buffer_size,
2736 std::__stable_sort_adaptive(__first, __middle, __last,
2741 template<
typename _RandomAccessIterator,
typename _Compare>
2744 _RandomAccessIterator __last, _Compare __comp)
2746 if (__last - __first < 15)
2748 std::__insertion_sort(__first, __last, __comp);
2751 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2767 template<
typename _InputIterator1,
typename _InputIterator2,
2769 _GLIBCXX20_CONSTEXPR
2771 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2772 _InputIterator2 __first2, _InputIterator2 __last2,
2775 while (__first1 != __last1 && __first2 != __last2)
2777 if (__comp(__first2, __first1))
2779 if (!__comp(__first1, __first2))
2784 return __first2 == __last2;
2805 template<
typename _InputIterator1,
typename _InputIterator2>
2806 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2808 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2809 _InputIterator2 __first2, _InputIterator2 __last2)
2812 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2813 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2814 __glibcxx_function_requires(_LessThanOpConcept<
2817 __glibcxx_function_requires(_LessThanOpConcept<
2820 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2821 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2822 __glibcxx_requires_irreflexive2(__first1, __last1);
2823 __glibcxx_requires_irreflexive2(__first2, __last2);
2825 return std::__includes(__first1, __last1, __first2, __last2,
2826 __gnu_cxx::__ops::__iter_less_iter());
2850 template<
typename _InputIterator1,
typename _InputIterator2,
2852 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2854 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2855 _InputIterator2 __first2, _InputIterator2 __last2,
2859 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2860 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2861 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2864 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2867 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2868 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2869 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2870 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2872 return std::__includes(__first1, __last1, __first2, __last2,
2873 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2886 template<
typename _B
idirectionalIterator,
typename _Compare>
2887 _GLIBCXX20_CONSTEXPR
2889 __next_permutation(_BidirectionalIterator __first,
2890 _BidirectionalIterator __last, _Compare __comp)
2892 if (__first == __last)
2894 _BidirectionalIterator __i = __first;
2903 _BidirectionalIterator __ii = __i;
2905 if (__comp(__i, __ii))
2907 _BidirectionalIterator __j = __last;
2908 while (!__comp(__i, --__j))
2910 std::iter_swap(__i, __j);
2936 template<
typename _B
idirectionalIterator>
2937 _GLIBCXX20_CONSTEXPR
2939 next_permutation(_BidirectionalIterator __first,
2940 _BidirectionalIterator __last)
2943 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2944 _BidirectionalIterator>)
2945 __glibcxx_function_requires(_LessThanComparableConcept<
2947 __glibcxx_requires_valid_range(__first, __last);
2948 __glibcxx_requires_irreflexive(__first, __last);
2950 return std::__next_permutation
2951 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2969 template<
typename _B
idirectionalIterator,
typename _Compare>
2970 _GLIBCXX20_CONSTEXPR
2972 next_permutation(_BidirectionalIterator __first,
2973 _BidirectionalIterator __last, _Compare __comp)
2976 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2977 _BidirectionalIterator>)
2978 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2981 __glibcxx_requires_valid_range(__first, __last);
2982 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2984 return std::__next_permutation
2985 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2988 template<
typename _B
idirectionalIterator,
typename _Compare>
2989 _GLIBCXX20_CONSTEXPR
2991 __prev_permutation(_BidirectionalIterator __first,
2992 _BidirectionalIterator __last, _Compare __comp)
2994 if (__first == __last)
2996 _BidirectionalIterator __i = __first;
3005 _BidirectionalIterator __ii = __i;
3007 if (__comp(__ii, __i))
3009 _BidirectionalIterator __j = __last;
3010 while (!__comp(--__j, __i))
3012 std::iter_swap(__i, __j);
3039 template<
typename _B
idirectionalIterator>
3040 _GLIBCXX20_CONSTEXPR
3042 prev_permutation(_BidirectionalIterator __first,
3043 _BidirectionalIterator __last)
3046 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3047 _BidirectionalIterator>)
3048 __glibcxx_function_requires(_LessThanComparableConcept<
3050 __glibcxx_requires_valid_range(__first, __last);
3051 __glibcxx_requires_irreflexive(__first, __last);
3053 return std::__prev_permutation(__first, __last,
3054 __gnu_cxx::__ops::__iter_less_iter());
3072 template<
typename _B
idirectionalIterator,
typename _Compare>
3073 _GLIBCXX20_CONSTEXPR
3075 prev_permutation(_BidirectionalIterator __first,
3076 _BidirectionalIterator __last, _Compare __comp)
3079 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3080 _BidirectionalIterator>)
3081 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3084 __glibcxx_requires_valid_range(__first, __last);
3085 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3087 return std::__prev_permutation(__first, __last,
3088 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3094 template<
typename _InputIterator,
typename _OutputIterator,
3095 typename _Predicate,
typename _Tp>
3096 _GLIBCXX20_CONSTEXPR
3098 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3099 _OutputIterator __result,
3100 _Predicate __pred,
const _Tp& __new_value)
3102 for (; __first != __last; ++__first, (void)++__result)
3103 if (__pred(__first))
3104 *__result = __new_value;
3106 *__result = *__first;
3124 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3125 _GLIBCXX20_CONSTEXPR
3126 inline _OutputIterator
3127 replace_copy(_InputIterator __first, _InputIterator __last,
3128 _OutputIterator __result,
3129 const _Tp& __old_value,
const _Tp& __new_value)
3132 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3133 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3135 __glibcxx_function_requires(_EqualOpConcept<
3137 __glibcxx_requires_valid_range(__first, __last);
3139 return std::__replace_copy_if(__first, __last, __result,
3140 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3159 template<
typename _InputIterator,
typename _OutputIterator,
3160 typename _Predicate,
typename _Tp>
3161 _GLIBCXX20_CONSTEXPR
3162 inline _OutputIterator
3163 replace_copy_if(_InputIterator __first, _InputIterator __last,
3164 _OutputIterator __result,
3165 _Predicate __pred,
const _Tp& __new_value)
3168 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3169 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3171 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3173 __glibcxx_requires_valid_range(__first, __last);
3175 return std::__replace_copy_if(__first, __last, __result,
3176 __gnu_cxx::__ops::__pred_iter(__pred),
3180#if __cplusplus >= 201103L
3188 template<
typename _ForwardIterator>
3189 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3191 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3192 {
return std::is_sorted_until(__first, __last) == __last; }
3203 template<
typename _ForwardIterator,
typename _Compare>
3204 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3206 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3208 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3210 template<
typename _ForwardIterator,
typename _Compare>
3211 _GLIBCXX20_CONSTEXPR
3213 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3216 if (__first == __last)
3219 _ForwardIterator __next = __first;
3220 for (++__next; __next != __last; __first = __next, (void)++__next)
3221 if (__comp(__next, __first))
3234 template<
typename _ForwardIterator>
3235 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3236 inline _ForwardIterator
3237 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3240 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3241 __glibcxx_function_requires(_LessThanComparableConcept<
3243 __glibcxx_requires_valid_range(__first, __last);
3244 __glibcxx_requires_irreflexive(__first, __last);
3246 return std::__is_sorted_until(__first, __last,
3247 __gnu_cxx::__ops::__iter_less_iter());
3259 template<
typename _ForwardIterator,
typename _Compare>
3260 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3261 inline _ForwardIterator
3262 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3266 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3267 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3270 __glibcxx_requires_valid_range(__first, __last);
3271 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3273 return std::__is_sorted_until(__first, __last,
3274 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3285 template<
typename _Tp>
3286 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3291 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3293 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3306 template<
typename _Tp,
typename _Compare>
3307 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3309 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3315 template<
typename _ForwardIterator,
typename _Compare>
3316 _GLIBCXX14_CONSTEXPR
3318 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3321 _ForwardIterator __next = __first;
3322 if (__first == __last
3323 || ++__next == __last)
3326 _ForwardIterator __min{}, __max{};
3327 if (__comp(__next, __first))
3341 while (__first != __last)
3344 if (++__next == __last)
3346 if (__comp(__first, __min))
3348 else if (!__comp(__first, __max))
3353 if (__comp(__next, __first))
3355 if (__comp(__next, __min))
3357 if (!__comp(__first, __max))
3362 if (__comp(__first, __min))
3364 if (!__comp(__next, __max))
3386 template<
typename _ForwardIterator>
3387 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3389 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3392 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3393 __glibcxx_function_requires(_LessThanComparableConcept<
3395 __glibcxx_requires_valid_range(__first, __last);
3396 __glibcxx_requires_irreflexive(__first, __last);
3398 return std::__minmax_element(__first, __last,
3399 __gnu_cxx::__ops::__iter_less_iter());
3414 template<
typename _ForwardIterator,
typename _Compare>
3415 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3417 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3421 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3422 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3425 __glibcxx_requires_valid_range(__first, __last);
3426 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3428 return std::__minmax_element(__first, __last,
3429 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3432 template<
typename _Tp>
3433 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3435 minmax(initializer_list<_Tp> __l)
3437 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3439 std::__minmax_element(__l.begin(), __l.end(),
3440 __gnu_cxx::__ops::__iter_less_iter());
3444 template<
typename _Tp,
typename _Compare>
3445 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3447 minmax(initializer_list<_Tp> __l, _Compare __comp)
3449 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3451 std::__minmax_element(__l.begin(), __l.end(),
3452 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3470 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3471 typename _BinaryPredicate>
3472 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3474 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3475 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3478 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3479 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3480 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3483 __glibcxx_requires_valid_range(__first1, __last1);
3485 return std::__is_permutation(__first1, __last1, __first2,
3486 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3489#if __cplusplus > 201103L
3490#pragma GCC diagnostic push
3491#pragma GCC diagnostic ignored "-Wc++17-extensions"
3492 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3493 typename _BinaryPredicate>
3494 _GLIBCXX20_CONSTEXPR
3496 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3497 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3498 _BinaryPredicate __pred)
3501 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3503 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3504 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3505 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3506 constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
3507 if constexpr (__ra_iters)
3509 if ((__last1 - __first1) != (__last2 - __first2))
3515 for (; __first1 != __last1 && __first2 != __last2;
3516 ++__first1, (void)++__first2)
3517 if (!__pred(__first1, __first2))
3520 if constexpr (__ra_iters)
3522 if (__first1 == __last1)
3529 if (__d1 == 0 && __d2 == 0)
3535 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3538 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3541 auto __matches = std::__count_if(__first2, __last2,
3542 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3544 || std::__count_if(__scan, __last1,
3545 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3551#pragma GCC diagnostic pop
3566 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3567 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3569 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3570 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3572 __glibcxx_requires_valid_range(__first1, __last1);
3573 __glibcxx_requires_valid_range(__first2, __last2);
3576 std::__is_permutation(__first1, __last1, __first2, __last2,
3577 __gnu_cxx::__ops::__iter_equal_to_iter());
3594 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3595 typename _BinaryPredicate>
3596 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3598 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3599 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3600 _BinaryPredicate __pred)
3602 __glibcxx_requires_valid_range(__first1, __last1);
3603 __glibcxx_requires_valid_range(__first2, __last2);
3605 return std::__is_permutation(__first1, __last1, __first2, __last2,
3606 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3610#ifdef __glibcxx_clamp
3622 template<
typename _Tp>
3623 [[nodiscard]]
constexpr const _Tp&
3624 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3626 __glibcxx_assert(!(__hi < __lo));
3642 template<
typename _Tp,
typename _Compare>
3643 [[nodiscard]]
constexpr const _Tp&
3644 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3646 __glibcxx_assert(!__comp(__hi, __lo));
3672 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3675 _UniformRandomBitGenerator&& __g)
3694 template<
typename _RandomAccessIterator,
3695 typename _UniformRandomNumberGenerator>
3697 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3698 _UniformRandomNumberGenerator&& __g)
3701 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3702 _RandomAccessIterator>)
3703 __glibcxx_requires_valid_range(__first, __last);
3705 if (__first == __last)
3711 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3713 typedef typename __distr_type::param_type __p_type;
3715 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3720 const __uc_type __urngrange = __g.max() - __g.min();
3721 const __uc_type __urange = __uc_type(__last - __first);
3723 if (__urngrange / __urange >= __urange)
3726 _RandomAccessIterator __i = __first + 1;
3732 if ((__urange % 2) == 0)
3734 __distr_type __d{0, 1};
3735 std::iter_swap(__i++, __first + __d(__g));
3742 while (__i != __last)
3744 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3749 std::iter_swap(__i++, __first + __pospos.
first);
3750 std::iter_swap(__i++, __first + __pospos.
second);
3758 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3759 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3763_GLIBCXX_BEGIN_NAMESPACE_ALGO
3777 template<
typename _InputIterator,
typename _Function>
3778 _GLIBCXX20_CONSTEXPR
3780 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3783 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3784 __glibcxx_requires_valid_range(__first, __last);
3785 for (; __first != __last; ++__first)
3790#if __cplusplus >= 201703L
3803 template<
typename _InputIterator,
typename _Size,
typename _Function>
3804 _GLIBCXX20_CONSTEXPR
3808 auto __n2 = std::__size_to_integer(__n);
3810 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3814 auto __last = __first + __n2;
3815 std::for_each(__first, __last,
std::move(__f));
3839 template<
typename _InputIterator,
typename _Tp>
3840 _GLIBCXX20_CONSTEXPR
3841 inline _InputIterator
3842 find(_InputIterator __first, _InputIterator __last,
3846 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3847 __glibcxx_function_requires(_EqualOpConcept<
3849 __glibcxx_requires_valid_range(__first, __last);
3851 __gnu_cxx::__ops::__iter_equals_val(__val));
3864 template<
typename _InputIterator,
typename _Predicate>
3865 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3866 inline _InputIterator
3867 find_if(_InputIterator __first, _InputIterator __last,
3871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3872 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3874 __glibcxx_requires_valid_range(__first, __last);
3877 __gnu_cxx::__ops::__pred_iter(__pred));
3896 template<
typename _InputIterator,
typename _ForwardIterator>
3897 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3899 find_first_of(_InputIterator __first1, _InputIterator __last1,
3900 _ForwardIterator __first2, _ForwardIterator __last2)
3903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3904 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3905 __glibcxx_function_requires(_EqualOpConcept<
3908 __glibcxx_requires_valid_range(__first1, __last1);
3909 __glibcxx_requires_valid_range(__first2, __last2);
3911 for (; __first1 != __last1; ++__first1)
3912 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3913 if (*__first1 == *__iter)
3937 template<
typename _InputIterator,
typename _ForwardIterator,
3938 typename _BinaryPredicate>
3939 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3941 find_first_of(_InputIterator __first1, _InputIterator __last1,
3942 _ForwardIterator __first2, _ForwardIterator __last2,
3943 _BinaryPredicate __comp)
3946 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3947 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3948 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3951 __glibcxx_requires_valid_range(__first1, __last1);
3952 __glibcxx_requires_valid_range(__first2, __last2);
3954 for (; __first1 != __last1; ++__first1)
3955 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3956 if (__comp(*__first1, *__iter))
3970 template<
typename _ForwardIterator>
3971 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3972 inline _ForwardIterator
3973 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3976 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3977 __glibcxx_function_requires(_EqualityComparableConcept<
3979 __glibcxx_requires_valid_range(__first, __last);
3981 return std::__adjacent_find(__first, __last,
3982 __gnu_cxx::__ops::__iter_equal_to_iter());
3996 template<
typename _ForwardIterator,
typename _BinaryPredicate>
3997 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3998 inline _ForwardIterator
3999 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4000 _BinaryPredicate __binary_pred)
4003 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4004 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4007 __glibcxx_requires_valid_range(__first, __last);
4009 return std::__adjacent_find(__first, __last,
4010 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4022 template<
typename _InputIterator,
typename _Tp>
4023 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4024 inline typename iterator_traits<_InputIterator>::difference_type
4025 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4028 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4029 __glibcxx_function_requires(_EqualOpConcept<
4031 __glibcxx_requires_valid_range(__first, __last);
4033 return std::__count_if(__first, __last,
4034 __gnu_cxx::__ops::__iter_equals_val(__value));
4046 template<
typename _InputIterator,
typename _Predicate>
4047 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4048 inline typename iterator_traits<_InputIterator>::difference_type
4049 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4052 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4053 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4055 __glibcxx_requires_valid_range(__first, __last);
4057 return std::__count_if(__first, __last,
4058 __gnu_cxx::__ops::__pred_iter(__pred));
4087 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4088 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4089 inline _ForwardIterator1
4090 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4091 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4094 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4095 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4096 __glibcxx_function_requires(_EqualOpConcept<
4099 __glibcxx_requires_valid_range(__first1, __last1);
4100 __glibcxx_requires_valid_range(__first2, __last2);
4102 return std::__search(__first1, __last1, __first2, __last2,
4103 __gnu_cxx::__ops::__iter_equal_to_iter());
4121 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4122 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4123 inline _ForwardIterator
4124 search_n(_ForwardIterator __first, _ForwardIterator __last,
4125 _Integer __count,
const _Tp& __val)
4128 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4129 __glibcxx_function_requires(_EqualOpConcept<
4131 __glibcxx_requires_valid_range(__first, __last);
4133 return std::__search_n(__first, __last, __count,
4134 __gnu_cxx::__ops::__iter_equals_val(__val));
4155 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4156 typename _BinaryPredicate>
4157 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4158 inline _ForwardIterator
4159 search_n(_ForwardIterator __first, _ForwardIterator __last,
4160 _Integer __count,
const _Tp& __val,
4161 _BinaryPredicate __binary_pred)
4164 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4165 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4167 __glibcxx_requires_valid_range(__first, __last);
4169 return std::__search_n(__first, __last, __count,
4170 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4173#if __cplusplus >= 201703L
4181 template<
typename _ForwardIterator,
typename _Searcher>
4182 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4183 inline _ForwardIterator
4184 search(_ForwardIterator __first, _ForwardIterator __last,
4185 const _Searcher& __searcher)
4186 {
return __searcher(__first, __last).first; }
4205 template<
typename _InputIterator,
typename _OutputIterator,
4206 typename _UnaryOperation>
4207 _GLIBCXX20_CONSTEXPR
4209 transform(_InputIterator __first, _InputIterator __last,
4210 _OutputIterator __result, _UnaryOperation __unary_op)
4213 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4214 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4216 __typeof__(__unary_op(*__first))>)
4217 __glibcxx_requires_valid_range(__first, __last);
4219 for (; __first != __last; ++__first, (void)++__result)
4220 *__result = __unary_op(*__first);
4243 template<
typename _InputIterator1,
typename _InputIterator2,
4244 typename _OutputIterator,
typename _BinaryOperation>
4245 _GLIBCXX20_CONSTEXPR
4247 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4248 _InputIterator2 __first2, _OutputIterator __result,
4249 _BinaryOperation __binary_op)
4252 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4253 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4254 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4256 __typeof__(__binary_op(*__first1,*__first2))>)
4257 __glibcxx_requires_valid_range(__first1, __last1);
4259 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4260 *__result = __binary_op(*__first1, *__first2);
4277 template<
typename _ForwardIterator,
typename _Tp>
4278 _GLIBCXX20_CONSTEXPR
4280 replace(_ForwardIterator __first, _ForwardIterator __last,
4281 const _Tp& __old_value,
const _Tp& __new_value)
4284 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4286 __glibcxx_function_requires(_EqualOpConcept<
4288 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4290 __glibcxx_requires_valid_range(__first, __last);
4292 for (; __first != __last; ++__first)
4293 if (*__first == __old_value)
4294 *__first = __new_value;
4310 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4311 _GLIBCXX20_CONSTEXPR
4313 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4314 _Predicate __pred,
const _Tp& __new_value)
4317 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4319 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4321 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4323 __glibcxx_requires_valid_range(__first, __last);
4325 for (; __first != __last; ++__first)
4326 if (__pred(*__first))
4327 *__first = __new_value;
4342 template<
typename _ForwardIterator,
typename _Generator>
4343 _GLIBCXX20_CONSTEXPR
4345 generate(_ForwardIterator __first, _ForwardIterator __last,
4349 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4350 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4352 __glibcxx_requires_valid_range(__first, __last);
4354 for (; __first != __last; ++__first)
4375 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4376 _GLIBCXX20_CONSTEXPR
4378 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4381 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4383 __typeof__(__gen())>)
4385 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4386 for (_IntSize __niter = std::__size_to_integer(__n);
4387 __niter > 0; --__niter, (void) ++__first)
4410 template<
typename _InputIterator,
typename _OutputIterator>
4411 _GLIBCXX20_CONSTEXPR
4412 inline _OutputIterator
4413 unique_copy(_InputIterator __first, _InputIterator __last,
4414 _OutputIterator __result)
4417 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4418 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4420 __glibcxx_function_requires(_EqualityComparableConcept<
4422 __glibcxx_requires_valid_range(__first, __last);
4424 if (__first == __last)
4427 __gnu_cxx::__ops::__iter_equal_to_iter(),
4450 template<
typename _InputIterator,
typename _OutputIterator,
4451 typename _BinaryPredicate>
4452 _GLIBCXX20_CONSTEXPR
4453 inline _OutputIterator
4454 unique_copy(_InputIterator __first, _InputIterator __last,
4455 _OutputIterator __result,
4456 _BinaryPredicate __binary_pred)
4459 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4460 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4462 __glibcxx_requires_valid_range(__first, __last);
4464 if (__first == __last)
4467 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4472#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4489 template<
typename _RandomAccessIterator>
4490 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4492 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4495 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4496 _RandomAccessIterator>)
4497 __glibcxx_requires_valid_range(__first, __last);
4499 if (__first != __last)
4500 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4503 _RandomAccessIterator __j = __first
4504 + std::rand() % ((__i - __first) + 1);
4506 std::iter_swap(__i, __j);
4528 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4529 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4531 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4532#if __cplusplus >= 201103L
4533 _RandomNumberGenerator&& __rand)
4535 _RandomNumberGenerator& __rand)
4539 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4540 _RandomAccessIterator>)
4541 __glibcxx_requires_valid_range(__first, __last);
4543 if (__first == __last)
4545 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4547 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4549 std::iter_swap(__i, __j);
4570 template<
typename _ForwardIterator,
typename _Predicate>
4571 _GLIBCXX20_CONSTEXPR
4572 inline _ForwardIterator
4573 partition(_ForwardIterator __first, _ForwardIterator __last,
4577 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4579 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4581 __glibcxx_requires_valid_range(__first, __last);
4605 template<
typename _RandomAccessIterator>
4606 _GLIBCXX20_CONSTEXPR
4608 partial_sort(_RandomAccessIterator __first,
4609 _RandomAccessIterator __middle,
4610 _RandomAccessIterator __last)
4613 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4614 _RandomAccessIterator>)
4615 __glibcxx_function_requires(_LessThanComparableConcept<
4617 __glibcxx_requires_valid_range(__first, __middle);
4618 __glibcxx_requires_valid_range(__middle, __last);
4619 __glibcxx_requires_irreflexive(__first, __last);
4621 std::__partial_sort(__first, __middle, __last,
4622 __gnu_cxx::__ops::__iter_less_iter());
4644 template<
typename _RandomAccessIterator,
typename _Compare>
4645 _GLIBCXX20_CONSTEXPR
4647 partial_sort(_RandomAccessIterator __first,
4648 _RandomAccessIterator __middle,
4649 _RandomAccessIterator __last,
4653 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4654 _RandomAccessIterator>)
4655 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4658 __glibcxx_requires_valid_range(__first, __middle);
4659 __glibcxx_requires_valid_range(__middle, __last);
4660 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4662 std::__partial_sort(__first, __middle, __last,
4663 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4681 template<
typename _RandomAccessIterator>
4682 _GLIBCXX20_CONSTEXPR
4684 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4685 _RandomAccessIterator __last)
4688 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4689 _RandomAccessIterator>)
4690 __glibcxx_function_requires(_LessThanComparableConcept<
4692 __glibcxx_requires_valid_range(__first, __nth);
4693 __glibcxx_requires_valid_range(__nth, __last);
4694 __glibcxx_requires_irreflexive(__first, __last);
4696 if (__first == __last || __nth == __last)
4699 std::__introselect(__first, __nth, __last,
4701 __gnu_cxx::__ops::__iter_less_iter());
4721 template<
typename _RandomAccessIterator,
typename _Compare>
4722 _GLIBCXX20_CONSTEXPR
4724 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4725 _RandomAccessIterator __last, _Compare __comp)
4728 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4729 _RandomAccessIterator>)
4730 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4733 __glibcxx_requires_valid_range(__first, __nth);
4734 __glibcxx_requires_valid_range(__nth, __last);
4735 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4737 if (__first == __last || __nth == __last)
4740 std::__introselect(__first, __nth, __last,
4742 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4759 template<
typename _RandomAccessIterator>
4760 _GLIBCXX20_CONSTEXPR
4762 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4765 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4766 _RandomAccessIterator>)
4767 __glibcxx_function_requires(_LessThanComparableConcept<
4769 __glibcxx_requires_valid_range(__first, __last);
4770 __glibcxx_requires_irreflexive(__first, __last);
4772 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4790 template<
typename _RandomAccessIterator,
typename _Compare>
4791 _GLIBCXX20_CONSTEXPR
4793 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4797 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4798 _RandomAccessIterator>)
4799 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4802 __glibcxx_requires_valid_range(__first, __last);
4803 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4805 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4808 template<
typename _InputIterator1,
typename _InputIterator2,
4809 typename _OutputIterator,
typename _Compare>
4810 _GLIBCXX20_CONSTEXPR
4812 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4813 _InputIterator2 __first2, _InputIterator2 __last2,
4814 _OutputIterator __result, _Compare __comp)
4816 while (__first1 != __last1 && __first2 != __last2)
4818 if (__comp(__first2, __first1))
4820 *__result = *__first2;
4825 *__result = *__first1;
4830 return std::copy(__first2, __last2,
4831 std::copy(__first1, __last1, __result));
4853 template<
typename _InputIterator1,
typename _InputIterator2,
4854 typename _OutputIterator>
4855 _GLIBCXX20_CONSTEXPR
4856 inline _OutputIterator
4857 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4858 _InputIterator2 __first2, _InputIterator2 __last2,
4859 _OutputIterator __result)
4862 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4863 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4864 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4866 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4868 __glibcxx_function_requires(_LessThanOpConcept<
4871 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4872 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4873 __glibcxx_requires_irreflexive2(__first1, __last1);
4874 __glibcxx_requires_irreflexive2(__first2, __last2);
4876 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4877 __first2, __last2, __result,
4878 __gnu_cxx::__ops::__iter_less_iter());
4904 template<
typename _InputIterator1,
typename _InputIterator2,
4905 typename _OutputIterator,
typename _Compare>
4906 _GLIBCXX20_CONSTEXPR
4907 inline _OutputIterator
4908 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4909 _InputIterator2 __first2, _InputIterator2 __last2,
4910 _OutputIterator __result, _Compare __comp)
4913 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4914 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4915 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4917 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4919 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4922 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4923 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4924 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4925 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4927 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4928 __first2, __last2, __result,
4929 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4932 template<
typename _RandomAccessIterator,
typename _Compare>
4934 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4937 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4939 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4942 if (__first == __last)
4946 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4949 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
4951 if (__builtin_expect(__buf.requested_size() == __buf.size(),
true))
4952 std::__stable_sort_adaptive(__first,
4953 __first + _DistanceType(__buf.size()),
4954 __last, __buf.begin(), __comp);
4955 else if (__builtin_expect(__buf.begin() == 0,
false))
4958 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
4959 _DistanceType(__buf.size()), __comp);
4982 template<
typename _RandomAccessIterator>
4984 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4987 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4988 _RandomAccessIterator>)
4989 __glibcxx_function_requires(_LessThanComparableConcept<
4991 __glibcxx_requires_valid_range(__first, __last);
4992 __glibcxx_requires_irreflexive(__first, __last);
4994 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4995 __gnu_cxx::__ops::__iter_less_iter());
5016 template<
typename _RandomAccessIterator,
typename _Compare>
5018 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5022 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5023 _RandomAccessIterator>)
5024 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5027 __glibcxx_requires_valid_range(__first, __last);
5028 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5030 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5031 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5034 template<
typename _InputIterator1,
typename _InputIterator2,
5035 typename _OutputIterator,
5037 _GLIBCXX20_CONSTEXPR
5039 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5040 _InputIterator2 __first2, _InputIterator2 __last2,
5041 _OutputIterator __result, _Compare __comp)
5043 while (__first1 != __last1 && __first2 != __last2)
5045 if (__comp(__first1, __first2))
5047 *__result = *__first1;
5050 else if (__comp(__first2, __first1))
5052 *__result = *__first2;
5057 *__result = *__first1;
5063 return std::copy(__first2, __last2,
5064 std::copy(__first1, __last1, __result));
5086 template<
typename _InputIterator1,
typename _InputIterator2,
5087 typename _OutputIterator>
5088 _GLIBCXX20_CONSTEXPR
5089 inline _OutputIterator
5090 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5091 _InputIterator2 __first2, _InputIterator2 __last2,
5092 _OutputIterator __result)
5095 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5096 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5097 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5099 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5101 __glibcxx_function_requires(_LessThanOpConcept<
5104 __glibcxx_function_requires(_LessThanOpConcept<
5107 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5108 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5109 __glibcxx_requires_irreflexive2(__first1, __last1);
5110 __glibcxx_requires_irreflexive2(__first2, __last2);
5112 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5113 __first2, __last2, __result,
5114 __gnu_cxx::__ops::__iter_less_iter());
5137 template<
typename _InputIterator1,
typename _InputIterator2,
5138 typename _OutputIterator,
typename _Compare>
5139 _GLIBCXX20_CONSTEXPR
5140 inline _OutputIterator
5141 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5142 _InputIterator2 __first2, _InputIterator2 __last2,
5143 _OutputIterator __result, _Compare __comp)
5146 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5147 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5148 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5150 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5152 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5155 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5158 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5159 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5160 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5161 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5163 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5164 __first2, __last2, __result,
5165 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5168 template<
typename _InputIterator1,
typename _InputIterator2,
5169 typename _OutputIterator,
5171 _GLIBCXX20_CONSTEXPR
5173 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5174 _InputIterator2 __first2, _InputIterator2 __last2,
5175 _OutputIterator __result, _Compare __comp)
5177 while (__first1 != __last1 && __first2 != __last2)
5178 if (__comp(__first1, __first2))
5180 else if (__comp(__first2, __first1))
5184 *__result = *__first1;
5210 template<
typename _InputIterator1,
typename _InputIterator2,
5211 typename _OutputIterator>
5212 _GLIBCXX20_CONSTEXPR
5213 inline _OutputIterator
5214 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5215 _InputIterator2 __first2, _InputIterator2 __last2,
5216 _OutputIterator __result)
5219 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5220 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5221 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5223 __glibcxx_function_requires(_LessThanOpConcept<
5226 __glibcxx_function_requires(_LessThanOpConcept<
5229 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5230 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5231 __glibcxx_requires_irreflexive2(__first1, __last1);
5232 __glibcxx_requires_irreflexive2(__first2, __last2);
5234 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5235 __first2, __last2, __result,
5236 __gnu_cxx::__ops::__iter_less_iter());
5260 template<
typename _InputIterator1,
typename _InputIterator2,
5261 typename _OutputIterator,
typename _Compare>
5262 _GLIBCXX20_CONSTEXPR
5263 inline _OutputIterator
5264 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5265 _InputIterator2 __first2, _InputIterator2 __last2,
5266 _OutputIterator __result, _Compare __comp)
5269 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5270 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5271 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5273 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5276 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5279 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5280 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5281 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5282 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5284 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5285 __first2, __last2, __result,
5286 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5289 template<
typename _InputIterator1,
typename _InputIterator2,
5290 typename _OutputIterator,
5292 _GLIBCXX20_CONSTEXPR
5294 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5295 _InputIterator2 __first2, _InputIterator2 __last2,
5296 _OutputIterator __result, _Compare __comp)
5298 while (__first1 != __last1 && __first2 != __last2)
5299 if (__comp(__first1, __first2))
5301 *__result = *__first1;
5305 else if (__comp(__first2, __first1))
5312 return std::copy(__first1, __last1, __result);
5335 template<
typename _InputIterator1,
typename _InputIterator2,
5336 typename _OutputIterator>
5337 _GLIBCXX20_CONSTEXPR
5338 inline _OutputIterator
5339 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5340 _InputIterator2 __first2, _InputIterator2 __last2,
5341 _OutputIterator __result)
5344 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5345 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5346 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5348 __glibcxx_function_requires(_LessThanOpConcept<
5351 __glibcxx_function_requires(_LessThanOpConcept<
5354 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5355 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5356 __glibcxx_requires_irreflexive2(__first1, __last1);
5357 __glibcxx_requires_irreflexive2(__first2, __last2);
5359 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5360 __first2, __last2, __result,
5361 __gnu_cxx::__ops::__iter_less_iter());
5387 template<
typename _InputIterator1,
typename _InputIterator2,
5388 typename _OutputIterator,
typename _Compare>
5389 _GLIBCXX20_CONSTEXPR
5390 inline _OutputIterator
5391 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5392 _InputIterator2 __first2, _InputIterator2 __last2,
5393 _OutputIterator __result, _Compare __comp)
5396 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5397 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5398 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5400 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5403 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5406 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5407 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5408 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5409 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5411 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5412 __first2, __last2, __result,
5413 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5416 template<
typename _InputIterator1,
typename _InputIterator2,
5417 typename _OutputIterator,
5419 _GLIBCXX20_CONSTEXPR
5421 __set_symmetric_difference(_InputIterator1 __first1,
5422 _InputIterator1 __last1,
5423 _InputIterator2 __first2,
5424 _InputIterator2 __last2,
5425 _OutputIterator __result,
5428 while (__first1 != __last1 && __first2 != __last2)
5429 if (__comp(__first1, __first2))
5431 *__result = *__first1;
5435 else if (__comp(__first2, __first1))
5437 *__result = *__first2;
5446 return std::copy(__first2, __last2,
5447 std::copy(__first1, __last1, __result));
5468 template<
typename _InputIterator1,
typename _InputIterator2,
5469 typename _OutputIterator>
5470 _GLIBCXX20_CONSTEXPR
5471 inline _OutputIterator
5472 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5473 _InputIterator2 __first2, _InputIterator2 __last2,
5474 _OutputIterator __result)
5477 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5478 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5479 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5481 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5483 __glibcxx_function_requires(_LessThanOpConcept<
5486 __glibcxx_function_requires(_LessThanOpConcept<
5489 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5490 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5491 __glibcxx_requires_irreflexive2(__first1, __last1);
5492 __glibcxx_requires_irreflexive2(__first2, __last2);
5494 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5495 __first2, __last2, __result,
5496 __gnu_cxx::__ops::__iter_less_iter());
5520 template<
typename _InputIterator1,
typename _InputIterator2,
5521 typename _OutputIterator,
typename _Compare>
5522 _GLIBCXX20_CONSTEXPR
5523 inline _OutputIterator
5524 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5525 _InputIterator2 __first2, _InputIterator2 __last2,
5526 _OutputIterator __result,
5530 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5531 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5532 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5534 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5536 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5539 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5542 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5543 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5544 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5545 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5547 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5548 __first2, __last2, __result,
5549 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5552 template<
typename _ForwardIterator,
typename _Compare>
5553 _GLIBCXX14_CONSTEXPR
5555 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5558 if (__first == __last)
5560 _ForwardIterator __result = __first;
5561 while (++__first != __last)
5562 if (__comp(__first, __result))
5574 template<
typename _ForwardIterator>
5575 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5577 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5580 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5581 __glibcxx_function_requires(_LessThanComparableConcept<
5583 __glibcxx_requires_valid_range(__first, __last);
5584 __glibcxx_requires_irreflexive(__first, __last);
5586 return _GLIBCXX_STD_A::__min_element(__first, __last,
5587 __gnu_cxx::__ops::__iter_less_iter());
5599 template<
typename _ForwardIterator,
typename _Compare>
5600 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5601 inline _ForwardIterator
5602 min_element(_ForwardIterator __first, _ForwardIterator __last,
5606 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5607 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5610 __glibcxx_requires_valid_range(__first, __last);
5611 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5613 return _GLIBCXX_STD_A::__min_element(__first, __last,
5614 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5617 template<
typename _ForwardIterator,
typename _Compare>
5618 _GLIBCXX14_CONSTEXPR
5620 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5623 if (__first == __last)
return __first;
5624 _ForwardIterator __result = __first;
5625 while (++__first != __last)
5626 if (__comp(__result, __first))
5638 template<
typename _ForwardIterator>
5639 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5640 inline _ForwardIterator
5641 max_element(_ForwardIterator __first, _ForwardIterator __last)
5644 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5645 __glibcxx_function_requires(_LessThanComparableConcept<
5647 __glibcxx_requires_valid_range(__first, __last);
5648 __glibcxx_requires_irreflexive(__first, __last);
5650 return _GLIBCXX_STD_A::__max_element(__first, __last,
5651 __gnu_cxx::__ops::__iter_less_iter());
5663 template<
typename _ForwardIterator,
typename _Compare>
5664 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5665 inline _ForwardIterator
5666 max_element(_ForwardIterator __first, _ForwardIterator __last,
5670 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5671 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5674 __glibcxx_requires_valid_range(__first, __last);
5675 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5677 return _GLIBCXX_STD_A::__max_element(__first, __last,
5678 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5681#if __cplusplus >= 201103L
5683 template<
typename _Tp>
5684 _GLIBCXX14_CONSTEXPR
5686 min(initializer_list<_Tp> __l)
5688 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5689 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5690 __gnu_cxx::__ops::__iter_less_iter());
5693 template<
typename _Tp,
typename _Compare>
5694 _GLIBCXX14_CONSTEXPR
5696 min(initializer_list<_Tp> __l, _Compare __comp)
5698 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5699 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5700 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5703 template<
typename _Tp>
5704 _GLIBCXX14_CONSTEXPR
5706 max(initializer_list<_Tp> __l)
5708 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5709 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5710 __gnu_cxx::__ops::__iter_less_iter());
5713 template<
typename _Tp,
typename _Compare>
5714 _GLIBCXX14_CONSTEXPR
5716 max(initializer_list<_Tp> __l, _Compare __comp)
5718 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5719 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5720 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5724#if __cplusplus >= 201402L
5726 template<
typename _InputIterator,
typename _RandomAccessIterator,
5727 typename _Size,
typename _UniformRandomBitGenerator>
5728 _RandomAccessIterator
5731 _Size __n, _UniformRandomBitGenerator&& __g)
5734 using __param_type =
typename __distrib_type::param_type;
5735 __distrib_type __d{};
5736 _Size __sample_sz = 0;
5737 while (__first != __last && __sample_sz != __n)
5739 __out[__sample_sz++] = *__first;
5742 for (
auto __pop_sz = __sample_sz; __first != __last;
5743 ++__first, (void) ++__pop_sz)
5745 const auto __k = __d(__g, __param_type{0, __pop_sz});
5747 __out[__k] = *__first;
5749 return __out + __sample_sz;
5753 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5754 typename _Size,
typename _UniformRandomBitGenerator>
5756 __sample(_ForwardIterator __first, _ForwardIterator __last,
5758 _OutputIterator __out, _Cat,
5759 _Size __n, _UniformRandomBitGenerator&& __g)
5762 using __param_type =
typename __distrib_type::param_type;
5767 if (__first == __last)
5770 __distrib_type __d{};
5772 __n =
std::min(__n, __unsampled_sz);
5777 const __uc_type __urngrange = __g.max() - __g.min();
5778 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5782 while (__n != 0 && __unsampled_sz >= 2)
5788 if (__p.
first < __n)
5790 *__out++ = *__first;
5796 if (__n == 0)
break;
5801 *__out++ = *__first;
5811 for (; __n != 0; ++__first)
5812 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5814 *__out++ = *__first;
5821#ifdef __glibcxx_sample
5823 template<typename _PopulationIterator, typename _SampleIterator,
5824 typename _Distance,
typename _UniformRandomBitGenerator>
5826 sample(_PopulationIterator __first, _PopulationIterator __last,
5827 _SampleIterator __out, _Distance __n,
5828 _UniformRandomBitGenerator&& __g)
5830 using __pop_cat =
typename
5832 using __samp_cat =
typename
5836 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5837 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5838 "output range must use a RandomAccessIterator when input range"
5839 " does not meet the ForwardIterator requirements");
5842 "sample size must be an integer type");
5845 return _GLIBCXX_STD_A::
5846 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5851_GLIBCXX_END_NAMESPACE_ALGO
5852_GLIBCXX_END_NAMESPACE_VERSION
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 of the same type 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 _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
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.
Traits class for iterators.
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.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...