64#if __cplusplus >= 201103L
68#if _GLIBCXX_HOSTED && (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
74namespace std _GLIBCXX_VISIBILITY(default)
76_GLIBCXX_BEGIN_NAMESPACE_VERSION
79 template<
typename _Iterator,
typename _Compare>
83 _Iterator __c, _Compare __comp)
88 std::iter_swap(__result, __b);
89 else if (__comp(__a, __c))
90 std::iter_swap(__result, __c);
92 std::iter_swap(__result, __a);
94 else if (__comp(__a, __c))
95 std::iter_swap(__result, __a);
96 else if (__comp(__b, __c))
97 std::iter_swap(__result, __c);
99 std::iter_swap(__result, __b);
103 template<
typename _InputIterator,
typename _Predicate>
105 inline _InputIterator
110 __gnu_cxx::__ops::__negate(__pred),
117 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
122 for (; __len; --__len, (void) ++__first)
123 if (!__pred(__first))
141 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
142 typename _BinaryPredicate>
145 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
146 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
147 _BinaryPredicate __predicate)
150 if (__first1 == __last1 || __first2 == __last2)
154 _ForwardIterator2 __p1(__first2);
155 if (++__p1 == __last2)
157 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
160 _ForwardIterator1 __current = __first1;
166 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
168 if (__first1 == __last1)
171 _ForwardIterator2 __p = __p1;
172 __current = __first1;
173 if (++__current == __last1)
176 while (__predicate(__current, __p))
178 if (++__p == __last2)
180 if (++__current == __last1)
193 template<
typename _ForwardIterator,
typename _Integer,
194 typename _UnaryPredicate>
198 _Integer __count, _UnaryPredicate __unary_pred,
202 while (__first != __last)
206 _ForwardIterator __i = __first;
208 while (__i != __last && __n != 1 && __unary_pred(__i))
226 template<
typename _RandomAccessIter,
typename _Integer,
227 typename _UnaryPredicate>
231 _Integer __count, _UnaryPredicate __unary_pred,
237 _DistanceType __tailSize = __last - __first;
238 _DistanceType __remainder = __count;
240 while (__remainder <= __tailSize)
242 __first += __remainder;
243 __tailSize -= __remainder;
246 _RandomAccessIter __backTrack = __first;
247 while (__unary_pred(--__backTrack))
249 if (--__remainder == 0)
250 return (__first - __count);
252 __remainder = __count + 1 - (__first - __backTrack);
257 template<
typename _ForwardIterator,
typename _Integer,
258 typename _UnaryPredicate>
261 __search_n(_ForwardIterator __first, _ForwardIterator __last,
263 _UnaryPredicate __unary_pred)
276 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
277 typename _BinaryPredicate>
280 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
281 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
282 forward_iterator_tag, forward_iterator_tag,
283 _BinaryPredicate __comp)
285 if (__first2 == __last2)
288 _ForwardIterator1 __result = __last1;
291 _ForwardIterator1 __new_result
292 = std::__search(__first1, __last1, __first2, __last2, __comp);
293 if (__new_result == __last1)
297 __result = __new_result;
298 __first1 = __new_result;
305 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
306 typename _BinaryPredicate>
308 _BidirectionalIterator1
309 __find_end(_BidirectionalIterator1 __first1,
310 _BidirectionalIterator1 __last1,
311 _BidirectionalIterator2 __first2,
312 _BidirectionalIterator2 __last2,
313 bidirectional_iterator_tag, bidirectional_iterator_tag,
314 _BinaryPredicate __comp)
317 __glibcxx_function_requires(_BidirectionalIteratorConcept<
318 _BidirectionalIterator1>)
319 __glibcxx_function_requires(_BidirectionalIteratorConcept<
320 _BidirectionalIterator2>)
322 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
323 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
325 _RevIterator1 __rlast1(__first1);
326 _RevIterator2 __rlast2(__first2);
327 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
328 _RevIterator2(__last2), __rlast2,
331 if (__rresult == __rlast1)
335 _BidirectionalIterator1 __result = __rresult.base();
367 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
369 inline _ForwardIterator1
370 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
371 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
374 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
375 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
376 __glibcxx_function_requires(_EqualOpConcept<
379 __glibcxx_requires_valid_range(__first1, __last1);
380 __glibcxx_requires_valid_range(__first2, __last2);
382 return std::__find_end(__first1, __last1, __first2, __last2,
385 __gnu_cxx::__ops::__iter_equal_to_iter());
416 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
417 typename _BinaryPredicate>
419 inline _ForwardIterator1
420 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
421 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
422 _BinaryPredicate __comp)
425 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
426 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
427 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
430 __glibcxx_requires_valid_range(__first1, __last1);
431 __glibcxx_requires_valid_range(__first2, __last2);
433 return std::__find_end(__first1, __last1, __first2, __last2,
436 __gnu_cxx::__ops::__iter_comp_iter(__comp));
439#if __cplusplus >= 201103L
452 template<
typename _InputIterator,
typename _Predicate>
455 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
456 {
return __last == std::find_if_not(__first, __last, __pred); }
470 template<
typename _InputIterator,
typename _Predicate>
473 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
489 template<
typename _InputIterator,
typename _Predicate>
492 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
493 {
return !std::none_of(__first, __last, __pred); }
505 template<
typename _InputIterator,
typename _Predicate>
507 inline _InputIterator
508 find_if_not(_InputIterator __first, _InputIterator __last,
512 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
513 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
515 __glibcxx_requires_valid_range(__first, __last);
517 __gnu_cxx::__ops::__pred_iter(__pred));
530 template<
typename _InputIterator,
typename _Predicate>
533 is_partitioned(_InputIterator __first, _InputIterator __last,
536 __first = std::find_if_not(__first, __last, __pred);
537 if (__first == __last)
540 return std::none_of(__first, __last, __pred);
552 template<
typename _ForwardIterator,
typename _Predicate>
555 partition_point(_ForwardIterator __first, _ForwardIterator __last,
559 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
560 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
564 __glibcxx_requires_valid_range(__first, __last);
573 _DistanceType __half = __len >> 1;
574 _ForwardIterator __middle = __first;
576 if (__pred(*__middle))
580 __len = __len - __half - 1;
589 template<
typename _InputIterator,
typename _OutputIterator,
593 __remove_copy_if(_InputIterator __first, _InputIterator __last,
594 _OutputIterator __result, _Predicate __pred)
596 for (; __first != __last; ++__first)
597 if (!__pred(__first))
599 *__result = *__first;
619 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
621 inline _OutputIterator
622 remove_copy(_InputIterator __first, _InputIterator __last,
623 _OutputIterator __result,
const _Tp& __value)
626 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
627 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
629 __glibcxx_function_requires(_EqualOpConcept<
631 __glibcxx_requires_valid_range(__first, __last);
633 return std::__remove_copy_if(__first, __last, __result,
634 __gnu_cxx::__ops::__iter_equals_val(__value));
652 template<
typename _InputIterator,
typename _OutputIterator,
655 inline _OutputIterator
656 remove_copy_if(_InputIterator __first, _InputIterator __last,
657 _OutputIterator __result, _Predicate __pred)
660 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
661 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
663 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
665 __glibcxx_requires_valid_range(__first, __last);
667 return std::__remove_copy_if(__first, __last, __result,
668 __gnu_cxx::__ops::__pred_iter(__pred));
671#if __cplusplus >= 201103L
687 template<
typename _InputIterator,
typename _OutputIterator,
691 copy_if(_InputIterator __first, _InputIterator __last,
692 _OutputIterator __result, _Predicate __pred)
695 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
696 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
698 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
700 __glibcxx_requires_valid_range(__first, __last);
702 for (; __first != __last; ++__first)
703 if (__pred(*__first))
705 *__result = *__first;
711 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
714 __copy_n(_InputIterator __first, _Size __n,
715 _OutputIterator __result, input_iterator_tag)
717 return std::__niter_wrap(__result,
718 __copy_n_a(__first, __n,
719 std::__niter_base(__result),
true));
722 template<
typename _RandomAccessIterator,
typename _Size,
723 typename _OutputIterator>
725 inline _OutputIterator
726 __copy_n(_RandomAccessIterator __first, _Size __n,
727 _OutputIterator __result, random_access_iterator_tag)
728 {
return std::copy(__first, __first + __n, __result); }
743 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
745 inline _OutputIterator
746 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
749 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
750 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
753 const auto __n2 = std::__size_to_integer(__n);
757 __glibcxx_requires_can_increment(__first, __n2);
758 __glibcxx_requires_can_increment(__result, __n2);
760 return std::__copy_n(__first, __n2, __result,
779 template<
typename _InputIterator,
typename _OutputIterator1,
780 typename _OutputIterator2,
typename _Predicate>
782 pair<_OutputIterator1, _OutputIterator2>
783 partition_copy(_InputIterator __first, _InputIterator __last,
784 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
788 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
789 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
791 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
793 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
795 __glibcxx_requires_valid_range(__first, __last);
797 for (; __first != __last; ++__first)
798 if (__pred(*__first))
800 *__out_true = *__first;
805 *__out_false = *__first;
830 template<
typename _ForwardIterator,
typename _Tp>
832 inline _ForwardIterator
833 remove(_ForwardIterator __first, _ForwardIterator __last,
837 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
839 __glibcxx_function_requires(_EqualOpConcept<
841 __glibcxx_requires_valid_range(__first, __last);
843 return std::__remove_if(__first, __last,
844 __gnu_cxx::__ops::__iter_equals_val(__value));
864 template<
typename _ForwardIterator,
typename _Predicate>
866 inline _ForwardIterator
867 remove_if(_ForwardIterator __first, _ForwardIterator __last,
871 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
873 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
875 __glibcxx_requires_valid_range(__first, __last);
877 return std::__remove_if(__first, __last,
878 __gnu_cxx::__ops::__pred_iter(__pred));
881 template<
typename _ForwardIterator,
typename _BinaryPredicate>
884 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
885 _BinaryPredicate __binary_pred)
887 if (__first == __last)
889 _ForwardIterator __next = __first;
890 while (++__next != __last)
892 if (__binary_pred(__first, __next))
899 template<
typename _ForwardIterator,
typename _BinaryPredicate>
902 __unique(_ForwardIterator __first, _ForwardIterator __last,
903 _BinaryPredicate __binary_pred)
906 __first = std::__adjacent_find(__first, __last, __binary_pred);
907 if (__first == __last)
911 _ForwardIterator __dest = __first;
913 while (++__first != __last)
914 if (!__binary_pred(__dest, __first))
915 *++__dest = _GLIBCXX_MOVE(*__first);
933 template<
typename _ForwardIterator>
935 inline _ForwardIterator
936 unique(_ForwardIterator __first, _ForwardIterator __last)
939 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
941 __glibcxx_function_requires(_EqualityComparableConcept<
943 __glibcxx_requires_valid_range(__first, __last);
945 return std::__unique(__first, __last,
946 __gnu_cxx::__ops::__iter_equal_to_iter());
964 template<
typename _ForwardIterator,
typename _BinaryPredicate>
966 inline _ForwardIterator
967 unique(_ForwardIterator __first, _ForwardIterator __last,
968 _BinaryPredicate __binary_pred)
971 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
973 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
976 __glibcxx_requires_valid_range(__first, __last);
978 return std::__unique(__first, __last,
979 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
988 template<
typename _ForwardIterator,
typename _OutputIterator,
989 typename _BinaryPredicate>
993 _OutputIterator __result, _BinaryPredicate __binary_pred,
997 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1001 _ForwardIterator __next = __first;
1002 *__result = *__first;
1003 while (++__next != __last)
1004 if (!__binary_pred(__first, __next))
1007 *++__result = *__first;
1018 template<
typename _InputIterator,
typename _OutputIterator,
1019 typename _BinaryPredicate>
1020 _GLIBCXX20_CONSTEXPR
1023 _OutputIterator __result, _BinaryPredicate __binary_pred,
1027 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1032 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1034 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1035 *__result = __value;
1036 while (++__first != __last)
1037 if (!__rebound_pred(__first, __value))
1040 *++__result = __value;
1051 template<
typename _InputIterator,
typename _ForwardIterator,
1052 typename _BinaryPredicate>
1053 _GLIBCXX20_CONSTEXPR
1056 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1060 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1063 *__result = *__first;
1064 while (++__first != __last)
1065 if (!__binary_pred(__result, __first))
1066 *++__result = *__first;
1075 template<
typename _B
idirectionalIterator>
1076 _GLIBCXX20_CONSTEXPR
1078 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1082 if (__first == __last || __first == --__last)
1086 std::iter_swap(__first, __last);
1096 template<
typename _RandomAccessIterator>
1097 _GLIBCXX20_CONSTEXPR
1099 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1102 if (__first == __last)
1105 while (__first < __last)
1107 std::iter_swap(__first, __last);
1125 template<
typename _B
idirectionalIterator>
1126 _GLIBCXX20_CONSTEXPR
1128 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1131 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1132 _BidirectionalIterator>)
1133 __glibcxx_requires_valid_range(__first, __last);
1153 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1154 _GLIBCXX20_CONSTEXPR
1156 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1157 _OutputIterator __result)
1160 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1161 _BidirectionalIterator>)
1162 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1164 __glibcxx_requires_valid_range(__first, __last);
1166 while (__first != __last)
1169 *__result = *__last;
1179 template<
typename _Eucl
ideanRingElement>
1180 _GLIBCXX20_CONSTEXPR
1181 _EuclideanRingElement
1182 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1186 _EuclideanRingElement __t = __m % __n;
1193_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1196 template<
typename _ForwardIterator>
1197 _GLIBCXX20_CONSTEXPR
1200 _ForwardIterator __middle,
1201 _ForwardIterator __last,
1204 if (__first == __middle)
1206 else if (__last == __middle)
1209 _ForwardIterator __first2 = __middle;
1212 std::iter_swap(__first, __first2);
1215 if (__first == __middle)
1216 __middle = __first2;
1218 while (__first2 != __last);
1220 _ForwardIterator __ret = __first;
1222 __first2 = __middle;
1224 while (__first2 != __last)
1226 std::iter_swap(__first, __first2);
1229 if (__first == __middle)
1230 __middle = __first2;
1231 else if (__first2 == __last)
1232 __first2 = __middle;
1238 template<
typename _B
idirectionalIterator>
1239 _GLIBCXX20_CONSTEXPR
1240 _BidirectionalIterator
1242 _BidirectionalIterator __middle,
1243 _BidirectionalIterator __last,
1247 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1248 _BidirectionalIterator>)
1250 if (__first == __middle)
1252 else if (__last == __middle)
1258 while (__first != __middle && __middle != __last)
1260 std::iter_swap(__first, --__last);
1264 if (__first == __middle)
1277 template<
typename _RandomAccessIterator>
1278 _GLIBCXX20_CONSTEXPR
1279 _RandomAccessIterator
1281 _RandomAccessIterator __middle,
1282 _RandomAccessIterator __last,
1286 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1287 _RandomAccessIterator>)
1289 if (__first == __middle)
1291 else if (__last == __middle)
1299 _Distance __n = __last - __first;
1300 _Distance __k = __middle - __first;
1302 if (__k == __n - __k)
1304 std::swap_ranges(__first, __middle, __middle);
1308 _RandomAccessIterator __p = __first;
1309 _RandomAccessIterator __ret = __first + (__last - __middle);
1313 if (__k < __n - __k)
1315 if (__is_pod(_ValueType) && __k == 1)
1317 _ValueType __t = _GLIBCXX_MOVE(*__p);
1318 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1319 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1322 _RandomAccessIterator __q = __p + __k;
1323 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1325 std::iter_swap(__p, __q);
1338 if (__is_pod(_ValueType) && __k == 1)
1340 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1341 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1342 *__p = _GLIBCXX_MOVE(__t);
1345 _RandomAccessIterator __q = __p + __n;
1347 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1351 std::iter_swap(__p, __q);
1384 template<
typename _ForwardIterator>
1385 _GLIBCXX20_CONSTEXPR
1386 inline _ForwardIterator
1387 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1388 _ForwardIterator __last)
1391 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1393 __glibcxx_requires_valid_range(__first, __middle);
1394 __glibcxx_requires_valid_range(__middle, __last);
1400_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1422 template<
typename _ForwardIterator,
typename _OutputIterator>
1423 _GLIBCXX20_CONSTEXPR
1424 inline _OutputIterator
1425 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1426 _ForwardIterator __last, _OutputIterator __result)
1429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1432 __glibcxx_requires_valid_range(__first, __middle);
1433 __glibcxx_requires_valid_range(__middle, __last);
1435 return std::copy(__first, __middle,
1436 std::copy(__middle, __last, __result));
1440 template<
typename _ForwardIterator,
typename _Predicate>
1441 _GLIBCXX20_CONSTEXPR
1446 if (__first == __last)
1449 while (__pred(*__first))
1450 if (++__first == __last)
1453 _ForwardIterator __next = __first;
1455 while (++__next != __last)
1456 if (__pred(*__next))
1458 std::iter_swap(__first, __next);
1466 template<
typename _B
idirectionalIterator,
typename _Predicate>
1467 _GLIBCXX20_CONSTEXPR
1468 _BidirectionalIterator
1469 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1475 if (__first == __last)
1477 else if (__pred(*__first))
1483 if (__first == __last)
1485 else if (!
bool(__pred(*__last)))
1489 std::iter_swap(__first, __last);
1502 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1506 _ForwardIterator __last,
1507 _Predicate __pred, _Distance __len,
1509 _Distance __buffer_size)
1514 if (__len <= __buffer_size)
1516 _ForwardIterator __result1 = __first;
1517 _Pointer __result2 = __buffer;
1522 *__result2 = _GLIBCXX_MOVE(*__first);
1525 for (; __first != __last; ++__first)
1526 if (__pred(__first))
1528 *__result1 = _GLIBCXX_MOVE(*__first);
1533 *__result2 = _GLIBCXX_MOVE(*__first);
1537 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1541 _ForwardIterator __middle = __first;
1543 _ForwardIterator __left_split =
1545 __len / 2, __buffer,
1550 _Distance __right_len = __len - __len / 2;
1551 _ForwardIterator __right_split =
1558 __buffer, __buffer_size);
1560 return std::rotate(__left_split, __middle, __right_split);
1563 template<
typename _ForwardIterator,
typename _Predicate>
1565 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1570 if (__first == __last)
1573 typedef typename iterator_traits<_ForwardIterator>::value_type
1575 typedef typename iterator_traits<_ForwardIterator>::difference_type
1578 _Temporary_buffer<_ForwardIterator, _ValueType>
1582 _DistanceType(__buf.requested_size()),
1584 _DistanceType(__buf.size()));
1604 template<
typename _ForwardIterator,
typename _Predicate>
1605 inline _ForwardIterator
1606 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1610 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1612 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1614 __glibcxx_requires_valid_range(__first, __last);
1616 return std::__stable_partition(__first, __last,
1617 __gnu_cxx::__ops::__pred_iter(__pred));
1623 template<
typename _RandomAccessIterator,
typename _Compare>
1624 _GLIBCXX20_CONSTEXPR
1626 __heap_select(_RandomAccessIterator __first,
1627 _RandomAccessIterator __middle,
1628 _RandomAccessIterator __last, _Compare __comp)
1630 std::__make_heap(__first, __middle, __comp);
1631 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1632 if (__comp(__i, __first))
1633 std::__pop_heap(__first, __middle, __i, __comp);
1638 template<
typename _InputIterator,
typename _RandomAccessIterator,
1640 _GLIBCXX20_CONSTEXPR
1641 _RandomAccessIterator
1642 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1643 _RandomAccessIterator __result_first,
1644 _RandomAccessIterator __result_last,
1647 typedef typename iterator_traits<_InputIterator>::value_type
1649 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1650 typedef typename _RItTraits::difference_type _DistanceType;
1652 if (__result_first == __result_last)
1653 return __result_last;
1654 _RandomAccessIterator __result_real_last = __result_first;
1655 while (__first != __last && __result_real_last != __result_last)
1657 *__result_real_last = *__first;
1658 ++__result_real_last;
1662 std::__make_heap(__result_first, __result_real_last, __comp);
1663 while (__first != __last)
1665 if (__comp(__first, __result_first))
1666 std::__adjust_heap(__result_first, _DistanceType(0),
1667 _DistanceType(__result_real_last
1669 _InputValueType(*__first), __comp);
1672 std::__sort_heap(__result_first, __result_real_last, __comp);
1673 return __result_real_last;
1696 template<
typename _InputIterator,
typename _RandomAccessIterator>
1697 _GLIBCXX20_CONSTEXPR
1698 inline _RandomAccessIterator
1699 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1700 _RandomAccessIterator __result_first,
1701 _RandomAccessIterator __result_last)
1703#ifdef _GLIBCXX_CONCEPT_CHECKS
1711 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1712 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1714 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1716 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1717 __glibcxx_requires_valid_range(__first, __last);
1718 __glibcxx_requires_irreflexive(__first, __last);
1719 __glibcxx_requires_valid_range(__result_first, __result_last);
1721 return std::__partial_sort_copy(__first, __last,
1722 __result_first, __result_last,
1723 __gnu_cxx::__ops::__iter_less_iter());
1746 template<
typename _InputIterator,
typename _RandomAccessIterator,
1748 _GLIBCXX20_CONSTEXPR
1749 inline _RandomAccessIterator
1750 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1751 _RandomAccessIterator __result_first,
1752 _RandomAccessIterator __result_last,
1755#ifdef _GLIBCXX_CONCEPT_CHECKS
1763 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1764 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1765 _RandomAccessIterator>)
1766 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1768 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1769 _InputValueType, _OutputValueType>)
1770 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1771 _OutputValueType, _OutputValueType>)
1772 __glibcxx_requires_valid_range(__first, __last);
1773 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1774 __glibcxx_requires_valid_range(__result_first, __result_last);
1776 return std::__partial_sort_copy(__first, __last,
1777 __result_first, __result_last,
1778 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1784 template<
typename _RandomAccessIterator,
typename _Compare>
1785 _GLIBCXX20_CONSTEXPR
1787 __unguarded_linear_insert(_RandomAccessIterator __last,
1790 typename iterator_traits<_RandomAccessIterator>::value_type
1791 __val = _GLIBCXX_MOVE(*__last);
1792 _RandomAccessIterator __next = __last;
1794 while (__comp(__val, __next))
1796 *__last = _GLIBCXX_MOVE(*__next);
1800 *__last = _GLIBCXX_MOVE(__val);
1804 template<
typename _RandomAccessIterator,
typename _Compare>
1805 _GLIBCXX20_CONSTEXPR
1807 __insertion_sort(_RandomAccessIterator __first,
1808 _RandomAccessIterator __last, _Compare __comp)
1810 if (__first == __last)
return;
1812 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1814 if (__comp(__i, __first))
1816 typename iterator_traits<_RandomAccessIterator>::value_type
1817 __val = _GLIBCXX_MOVE(*__i);
1818 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1819 *__first = _GLIBCXX_MOVE(__val);
1822 std::__unguarded_linear_insert(__i,
1823 __gnu_cxx::__ops::__val_comp_iter(__comp));
1828 template<
typename _RandomAccessIterator,
typename _Compare>
1829 _GLIBCXX20_CONSTEXPR
1831 __unguarded_insertion_sort(_RandomAccessIterator __first,
1832 _RandomAccessIterator __last, _Compare __comp)
1834 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1835 std::__unguarded_linear_insert(__i,
1836 __gnu_cxx::__ops::__val_comp_iter(__comp));
1843 enum { _S_threshold = 16 };
1846 template<
typename _RandomAccessIterator,
typename _Compare>
1847 _GLIBCXX20_CONSTEXPR
1849 __final_insertion_sort(_RandomAccessIterator __first,
1850 _RandomAccessIterator __last, _Compare __comp)
1852 if (__last - __first >
int(_S_threshold))
1854 std::__insertion_sort(__first, __first +
int(_S_threshold), __comp);
1855 std::__unguarded_insertion_sort(__first +
int(_S_threshold), __last,
1859 std::__insertion_sort(__first, __last, __comp);
1863 template<
typename _RandomAccessIterator,
typename _Compare>
1864 _GLIBCXX20_CONSTEXPR
1865 _RandomAccessIterator
1866 __unguarded_partition(_RandomAccessIterator __first,
1867 _RandomAccessIterator __last,
1868 _RandomAccessIterator __pivot, _Compare __comp)
1872 while (__comp(__first, __pivot))
1875 while (__comp(__pivot, __last))
1877 if (!(__first < __last))
1879 std::iter_swap(__first, __last);
1885 template<
typename _RandomAccessIterator,
typename _Compare>
1886 _GLIBCXX20_CONSTEXPR
1887 inline _RandomAccessIterator
1888 __unguarded_partition_pivot(_RandomAccessIterator __first,
1889 _RandomAccessIterator __last, _Compare __comp)
1891 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1894 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1897 template<
typename _RandomAccessIterator,
typename _Compare>
1898 _GLIBCXX20_CONSTEXPR
1900 __partial_sort(_RandomAccessIterator __first,
1901 _RandomAccessIterator __middle,
1902 _RandomAccessIterator __last,
1905 std::__heap_select(__first, __middle, __last, __comp);
1906 std::__sort_heap(__first, __middle, __comp);
1910 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1911 _GLIBCXX20_CONSTEXPR
1913 __introsort_loop(_RandomAccessIterator __first,
1914 _RandomAccessIterator __last,
1915 _Size __depth_limit, _Compare __comp)
1917 while (__last - __first >
int(_S_threshold))
1919 if (__depth_limit == 0)
1921 std::__partial_sort(__first, __last, __last, __comp);
1925 _RandomAccessIterator __cut =
1926 std::__unguarded_partition_pivot(__first, __last, __comp);
1927 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1934 template<
typename _RandomAccessIterator,
typename _Compare>
1935 _GLIBCXX20_CONSTEXPR
1937 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1940 if (__first != __last)
1942 std::__introsort_loop(__first, __last,
1945 std::__final_insertion_sort(__first, __last, __comp);
1949 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1950 _GLIBCXX20_CONSTEXPR
1952 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1953 _RandomAccessIterator __last, _Size __depth_limit,
1956 while (__last - __first > 3)
1958 if (__depth_limit == 0)
1960 std::__heap_select(__first, __nth + 1, __last, __comp);
1962 std::iter_swap(__first, __nth);
1966 _RandomAccessIterator __cut =
1967 std::__unguarded_partition_pivot(__first, __last, __comp);
1973 std::__insertion_sort(__first, __last, __comp);
1997 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1998 _GLIBCXX20_CONSTEXPR
1999 inline _ForwardIterator
2000 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2001 const _Tp& __val, _Compare __comp)
2004 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2005 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2007 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2010 return std::__lower_bound(__first, __last, __val,
2011 __gnu_cxx::__ops::__iter_comp_val(__comp));
2014 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2015 _GLIBCXX20_CONSTEXPR
2017 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2018 const _Tp& __val, _Compare __comp)
2020 typedef typename iterator_traits<_ForwardIterator>::difference_type
2027 _DistanceType __half = __len >> 1;
2028 _ForwardIterator __middle = __first;
2030 if (__comp(__val, __middle))
2036 __len = __len - __half - 1;
2053 template<
typename _ForwardIterator,
typename _Tp>
2054 _GLIBCXX20_CONSTEXPR
2055 inline _ForwardIterator
2056 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2060 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2061 __glibcxx_function_requires(_LessThanOpConcept<
2063 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2065 return std::__upper_bound(__first, __last, __val,
2066 __gnu_cxx::__ops::__val_less_iter());
2084 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2085 _GLIBCXX20_CONSTEXPR
2086 inline _ForwardIterator
2087 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2088 const _Tp& __val, _Compare __comp)
2091 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2092 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2094 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2097 return std::__upper_bound(__first, __last, __val,
2098 __gnu_cxx::__ops::__val_comp_iter(__comp));
2101 template<
typename _ForwardIterator,
typename _Tp,
2102 typename _CompareItTp,
typename _CompareTpIt>
2103 _GLIBCXX20_CONSTEXPR
2104 pair<_ForwardIterator, _ForwardIterator>
2105 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2107 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2109 typedef typename iterator_traits<_ForwardIterator>::difference_type
2116 _DistanceType __half = __len >> 1;
2117 _ForwardIterator __middle = __first;
2119 if (__comp_it_val(__middle, __val))
2123 __len = __len - __half - 1;
2125 else if (__comp_val_it(__val, __middle))
2129 _ForwardIterator __left
2130 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2132 _ForwardIterator __right
2133 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2134 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2137 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2157 template<
typename _ForwardIterator,
typename _Tp>
2158 _GLIBCXX20_CONSTEXPR
2159 inline pair<_ForwardIterator, _ForwardIterator>
2160 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2164 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2165 __glibcxx_function_requires(_LessThanOpConcept<
2167 __glibcxx_function_requires(_LessThanOpConcept<
2169 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2170 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2172 return std::__equal_range(__first, __last, __val,
2173 __gnu_cxx::__ops::__iter_less_val(),
2174 __gnu_cxx::__ops::__val_less_iter());
2194 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2195 _GLIBCXX20_CONSTEXPR
2196 inline pair<_ForwardIterator, _ForwardIterator>
2197 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2198 const _Tp& __val, _Compare __comp)
2201 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2202 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2204 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2206 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2208 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2211 return std::__equal_range(__first, __last, __val,
2212 __gnu_cxx::__ops::__iter_comp_val(__comp),
2213 __gnu_cxx::__ops::__val_comp_iter(__comp));
2228 template<
typename _ForwardIterator,
typename _Tp>
2229 _GLIBCXX20_CONSTEXPR
2231 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2235 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2236 __glibcxx_function_requires(_LessThanOpConcept<
2238 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2239 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2241 _ForwardIterator __i
2242 = std::__lower_bound(__first, __last, __val,
2243 __gnu_cxx::__ops::__iter_less_val());
2244 return __i != __last && !(__val < *__i);
2262 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2263 _GLIBCXX20_CONSTEXPR
2265 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2266 const _Tp& __val, _Compare __comp)
2269 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2270 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2272 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2274 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2277 _ForwardIterator __i
2278 = std::__lower_bound(__first, __last, __val,
2279 __gnu_cxx::__ops::__iter_comp_val(__comp));
2280 return __i != __last && !bool(__comp(__val, *__i));
2286 template<
typename _InputIterator1,
typename _InputIterator2,
2287 typename _OutputIterator,
typename _Compare>
2290 _InputIterator2 __first2, _InputIterator2 __last2,
2291 _OutputIterator __result, _Compare __comp)
2293 while (__first1 != __last1 && __first2 != __last2)
2295 if (__comp(__first2, __first1))
2297 *__result = _GLIBCXX_MOVE(*__first2);
2302 *__result = _GLIBCXX_MOVE(*__first1);
2307 if (__first1 != __last1)
2308 _GLIBCXX_MOVE3(__first1, __last1, __result);
2312 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2313 typename _BidirectionalIterator3,
typename _Compare>
2316 _BidirectionalIterator1 __last1,
2317 _BidirectionalIterator2 __first2,
2318 _BidirectionalIterator2 __last2,
2319 _BidirectionalIterator3 __result,
2322 if (__first1 == __last1)
2324 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2327 else if (__first2 == __last2)
2334 if (__comp(__last2, __last1))
2336 *--__result = _GLIBCXX_MOVE(*__last1);
2337 if (__first1 == __last1)
2339 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2346 *--__result = _GLIBCXX_MOVE(*__last2);
2347 if (__first2 == __last2)
2355 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2357 _BidirectionalIterator1
2359 _BidirectionalIterator1 __middle,
2360 _BidirectionalIterator1 __last,
2361 _Distance __len1, _Distance __len2,
2362 _BidirectionalIterator2 __buffer,
2363 _Distance __buffer_size)
2365 _BidirectionalIterator2 __buffer_end;
2366 if (__len1 > __len2 && __len2 <= __buffer_size)
2370 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2371 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2372 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2377 else if (__len1 <= __buffer_size)
2381 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2382 _GLIBCXX_MOVE3(__middle, __last, __first);
2383 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2389 return std::rotate(__first, __middle, __last);
2393 template<
typename _BidirectionalIterator,
typename _Distance,
2394 typename _Pointer,
typename _Compare>
2397 _BidirectionalIterator __middle,
2398 _BidirectionalIterator __last,
2399 _Distance __len1, _Distance __len2,
2400 _Pointer __buffer, _Distance __buffer_size,
2403 if (__len1 <= __len2 && __len1 <= __buffer_size)
2405 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2409 else if (__len2 <= __buffer_size)
2411 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2413 __buffer_end, __last, __comp);
2417 _BidirectionalIterator __first_cut = __first;
2418 _BidirectionalIterator __second_cut = __middle;
2419 _Distance __len11 = 0;
2420 _Distance __len22 = 0;
2421 if (__len1 > __len2)
2423 __len11 = __len1 / 2;
2426 = std::__lower_bound(__middle, __last, *__first_cut,
2427 __gnu_cxx::__ops::__iter_comp_val(__comp));
2432 __len22 = __len2 / 2;
2435 = std::__upper_bound(__first, __middle, *__second_cut,
2436 __gnu_cxx::__ops::__val_comp_iter(__comp));
2440 _BidirectionalIterator __new_middle
2442 __len1 - __len11, __len22, __buffer,
2445 __len22, __buffer, __buffer_size, __comp);
2448 __len2 - __len22, __buffer,
2449 __buffer_size, __comp);
2454 template<
typename _BidirectionalIterator,
typename _Distance,
2458 _BidirectionalIterator __middle,
2459 _BidirectionalIterator __last,
2460 _Distance __len1, _Distance __len2,
2463 if (__len1 == 0 || __len2 == 0)
2466 if (__len1 + __len2 == 2)
2468 if (__comp(__middle, __first))
2469 std::iter_swap(__first, __middle);
2473 _BidirectionalIterator __first_cut = __first;
2474 _BidirectionalIterator __second_cut = __middle;
2475 _Distance __len11 = 0;
2476 _Distance __len22 = 0;
2477 if (__len1 > __len2)
2479 __len11 = __len1 / 2;
2482 = std::__lower_bound(__middle, __last, *__first_cut,
2483 __gnu_cxx::__ops::__iter_comp_val(__comp));
2488 __len22 = __len2 / 2;
2491 = std::__upper_bound(__first, __middle, *__second_cut,
2492 __gnu_cxx::__ops::__val_comp_iter(__comp));
2496 _BidirectionalIterator __new_middle
2497 = std::rotate(__first_cut, __middle, __second_cut);
2499 __len11, __len22, __comp);
2501 __len1 - __len11, __len2 - __len22, __comp);
2504 template<
typename _B
idirectionalIterator,
typename _Compare>
2506 __inplace_merge(_BidirectionalIterator __first,
2507 _BidirectionalIterator __middle,
2508 _BidirectionalIterator __last,
2511 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2513 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2515 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2517 if (__first == __middle || __middle == __last)
2520 const _DistanceType __len1 =
std::distance(__first, __middle);
2521 const _DistanceType __len2 =
std::distance(__middle, __last);
2525 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2527 if (__buf.begin() == 0)
2529 (__first, __middle, __last, __len1, __len2, __comp);
2532 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2533 _DistanceType(__buf.size()), __comp);
2554 template<
typename _B
idirectionalIterator>
2556 inplace_merge(_BidirectionalIterator __first,
2557 _BidirectionalIterator __middle,
2558 _BidirectionalIterator __last)
2561 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2562 _BidirectionalIterator>)
2563 __glibcxx_function_requires(_LessThanComparableConcept<
2565 __glibcxx_requires_sorted(__first, __middle);
2566 __glibcxx_requires_sorted(__middle, __last);
2567 __glibcxx_requires_irreflexive(__first, __last);
2569 std::__inplace_merge(__first, __middle, __last,
2570 __gnu_cxx::__ops::__iter_less_iter());
2595 template<
typename _B
idirectionalIterator,
typename _Compare>
2597 inplace_merge(_BidirectionalIterator __first,
2598 _BidirectionalIterator __middle,
2599 _BidirectionalIterator __last,
2603 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2604 _BidirectionalIterator>)
2605 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2608 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2609 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2610 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2612 std::__inplace_merge(__first, __middle, __last,
2613 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2618 template<
typename _InputIterator,
typename _OutputIterator,
2622 _InputIterator __first2, _InputIterator __last2,
2623 _OutputIterator __result, _Compare __comp)
2625 while (__first1 != __last1 && __first2 != __last2)
2627 if (__comp(__first2, __first1))
2629 *__result = _GLIBCXX_MOVE(*__first2);
2634 *__result = _GLIBCXX_MOVE(*__first1);
2639 return _GLIBCXX_MOVE3(__first2, __last2,
2640 _GLIBCXX_MOVE3(__first1, __last1,
2644 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2645 typename _Distance,
typename _Compare>
2647 __merge_sort_loop(_RandomAccessIterator1 __first,
2648 _RandomAccessIterator1 __last,
2649 _RandomAccessIterator2 __result, _Distance __step_size,
2652 const _Distance __two_step = 2 * __step_size;
2654 while (__last - __first >= __two_step)
2657 __first + __step_size,
2658 __first + __two_step,
2660 __first += __two_step;
2662 __step_size =
std::min(_Distance(__last - __first), __step_size);
2665 __first + __step_size, __last, __result, __comp);
2668 template<
typename _RandomAccessIterator,
typename _Distance,
2670 _GLIBCXX20_CONSTEXPR
2672 __chunk_insertion_sort(_RandomAccessIterator __first,
2673 _RandomAccessIterator __last,
2674 _Distance __chunk_size, _Compare __comp)
2676 while (__last - __first >= __chunk_size)
2678 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2679 __first += __chunk_size;
2681 std::__insertion_sort(__first, __last, __comp);
2684 enum { _S_chunk_size = 7 };
2686 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2688 __merge_sort_with_buffer(_RandomAccessIterator __first,
2689 _RandomAccessIterator __last,
2690 _Pointer __buffer, _Compare __comp)
2692 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2695 const _Distance __len = __last - __first;
2696 const _Pointer __buffer_last = __buffer + __len;
2698 _Distance __step_size = _S_chunk_size;
2699 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2701 while (__step_size < __len)
2703 std::__merge_sort_loop(__first, __last, __buffer,
2704 __step_size, __comp);
2706 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2707 __step_size, __comp);
2712 template<
typename _RandomAccessIterator,
typename _Pointer,
2713 typename _Distance,
typename _Compare>
2715 __stable_sort_adaptive(_RandomAccessIterator __first,
2716 _RandomAccessIterator __last,
2717 _Pointer __buffer, _Distance __buffer_size,
2720 const _Distance __len = (__last - __first + 1) / 2;
2721 const _RandomAccessIterator __middle = __first + __len;
2722 if (__len > __buffer_size)
2724 std::__stable_sort_adaptive(__first, __middle, __buffer,
2725 __buffer_size, __comp);
2726 std::__stable_sort_adaptive(__middle, __last, __buffer,
2727 __buffer_size, __comp);
2731 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2732 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2736 _Distance(__middle - __first),
2737 _Distance(__last - __middle),
2738 __buffer, __buffer_size,
2743 template<
typename _RandomAccessIterator,
typename _Compare>
2746 _RandomAccessIterator __last, _Compare __comp)
2748 if (__last - __first < 15)
2750 std::__insertion_sort(__first, __last, __comp);
2753 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2769 template<
typename _InputIterator1,
typename _InputIterator2,
2771 _GLIBCXX20_CONSTEXPR
2773 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2774 _InputIterator2 __first2, _InputIterator2 __last2,
2777 while (__first1 != __last1 && __first2 != __last2)
2779 if (__comp(__first2, __first1))
2781 if (!__comp(__first1, __first2))
2786 return __first2 == __last2;
2807 template<
typename _InputIterator1,
typename _InputIterator2>
2808 _GLIBCXX20_CONSTEXPR
2810 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2811 _InputIterator2 __first2, _InputIterator2 __last2)
2814 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2815 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2816 __glibcxx_function_requires(_LessThanOpConcept<
2819 __glibcxx_function_requires(_LessThanOpConcept<
2822 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2823 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2824 __glibcxx_requires_irreflexive2(__first1, __last1);
2825 __glibcxx_requires_irreflexive2(__first2, __last2);
2827 return std::__includes(__first1, __last1, __first2, __last2,
2828 __gnu_cxx::__ops::__iter_less_iter());
2852 template<
typename _InputIterator1,
typename _InputIterator2,
2854 _GLIBCXX20_CONSTEXPR
2856 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2857 _InputIterator2 __first2, _InputIterator2 __last2,
2861 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2862 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2863 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2866 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2869 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2870 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2871 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2872 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2874 return std::__includes(__first1, __last1, __first2, __last2,
2875 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2888 template<
typename _B
idirectionalIterator,
typename _Compare>
2889 _GLIBCXX20_CONSTEXPR
2891 __next_permutation(_BidirectionalIterator __first,
2892 _BidirectionalIterator __last, _Compare __comp)
2894 if (__first == __last)
2896 _BidirectionalIterator __i = __first;
2905 _BidirectionalIterator __ii = __i;
2907 if (__comp(__i, __ii))
2909 _BidirectionalIterator __j = __last;
2910 while (!__comp(__i, --__j))
2912 std::iter_swap(__i, __j);
2938 template<
typename _B
idirectionalIterator>
2939 _GLIBCXX20_CONSTEXPR
2941 next_permutation(_BidirectionalIterator __first,
2942 _BidirectionalIterator __last)
2945 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2946 _BidirectionalIterator>)
2947 __glibcxx_function_requires(_LessThanComparableConcept<
2949 __glibcxx_requires_valid_range(__first, __last);
2950 __glibcxx_requires_irreflexive(__first, __last);
2952 return std::__next_permutation
2953 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2971 template<
typename _B
idirectionalIterator,
typename _Compare>
2972 _GLIBCXX20_CONSTEXPR
2974 next_permutation(_BidirectionalIterator __first,
2975 _BidirectionalIterator __last, _Compare __comp)
2978 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2979 _BidirectionalIterator>)
2980 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2983 __glibcxx_requires_valid_range(__first, __last);
2984 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2986 return std::__next_permutation
2987 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2990 template<
typename _B
idirectionalIterator,
typename _Compare>
2991 _GLIBCXX20_CONSTEXPR
2993 __prev_permutation(_BidirectionalIterator __first,
2994 _BidirectionalIterator __last, _Compare __comp)
2996 if (__first == __last)
2998 _BidirectionalIterator __i = __first;
3007 _BidirectionalIterator __ii = __i;
3009 if (__comp(__ii, __i))
3011 _BidirectionalIterator __j = __last;
3012 while (!__comp(--__j, __i))
3014 std::iter_swap(__i, __j);
3041 template<
typename _B
idirectionalIterator>
3042 _GLIBCXX20_CONSTEXPR
3044 prev_permutation(_BidirectionalIterator __first,
3045 _BidirectionalIterator __last)
3048 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3049 _BidirectionalIterator>)
3050 __glibcxx_function_requires(_LessThanComparableConcept<
3052 __glibcxx_requires_valid_range(__first, __last);
3053 __glibcxx_requires_irreflexive(__first, __last);
3055 return std::__prev_permutation(__first, __last,
3056 __gnu_cxx::__ops::__iter_less_iter());
3074 template<
typename _B
idirectionalIterator,
typename _Compare>
3075 _GLIBCXX20_CONSTEXPR
3077 prev_permutation(_BidirectionalIterator __first,
3078 _BidirectionalIterator __last, _Compare __comp)
3081 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3082 _BidirectionalIterator>)
3083 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3086 __glibcxx_requires_valid_range(__first, __last);
3087 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3089 return std::__prev_permutation(__first, __last,
3090 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3096 template<
typename _InputIterator,
typename _OutputIterator,
3097 typename _Predicate,
typename _Tp>
3098 _GLIBCXX20_CONSTEXPR
3100 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3101 _OutputIterator __result,
3102 _Predicate __pred,
const _Tp& __new_value)
3104 for (; __first != __last; ++__first, (void)++__result)
3105 if (__pred(__first))
3106 *__result = __new_value;
3108 *__result = *__first;
3126 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3127 _GLIBCXX20_CONSTEXPR
3128 inline _OutputIterator
3129 replace_copy(_InputIterator __first, _InputIterator __last,
3130 _OutputIterator __result,
3131 const _Tp& __old_value,
const _Tp& __new_value)
3134 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3135 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3137 __glibcxx_function_requires(_EqualOpConcept<
3139 __glibcxx_requires_valid_range(__first, __last);
3141 return std::__replace_copy_if(__first, __last, __result,
3142 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3161 template<
typename _InputIterator,
typename _OutputIterator,
3162 typename _Predicate,
typename _Tp>
3163 _GLIBCXX20_CONSTEXPR
3164 inline _OutputIterator
3165 replace_copy_if(_InputIterator __first, _InputIterator __last,
3166 _OutputIterator __result,
3167 _Predicate __pred,
const _Tp& __new_value)
3170 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3173 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3175 __glibcxx_requires_valid_range(__first, __last);
3177 return std::__replace_copy_if(__first, __last, __result,
3178 __gnu_cxx::__ops::__pred_iter(__pred),
3182#if __cplusplus >= 201103L
3190 template<
typename _ForwardIterator>
3191 _GLIBCXX20_CONSTEXPR
3193 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3194 {
return std::is_sorted_until(__first, __last) == __last; }
3205 template<
typename _ForwardIterator,
typename _Compare>
3206 _GLIBCXX20_CONSTEXPR
3208 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3210 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3212 template<
typename _ForwardIterator,
typename _Compare>
3213 _GLIBCXX20_CONSTEXPR
3215 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3218 if (__first == __last)
3221 _ForwardIterator __next = __first;
3222 for (++__next; __next != __last; __first = __next, (void)++__next)
3223 if (__comp(__next, __first))
3236 template<
typename _ForwardIterator>
3237 _GLIBCXX20_CONSTEXPR
3238 inline _ForwardIterator
3239 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3242 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3243 __glibcxx_function_requires(_LessThanComparableConcept<
3245 __glibcxx_requires_valid_range(__first, __last);
3246 __glibcxx_requires_irreflexive(__first, __last);
3248 return std::__is_sorted_until(__first, __last,
3249 __gnu_cxx::__ops::__iter_less_iter());
3261 template<
typename _ForwardIterator,
typename _Compare>
3262 _GLIBCXX20_CONSTEXPR
3263 inline _ForwardIterator
3264 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3268 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3269 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3272 __glibcxx_requires_valid_range(__first, __last);
3273 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3275 return std::__is_sorted_until(__first, __last,
3276 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3287 template<
typename _Tp>
3288 _GLIBCXX14_CONSTEXPR
3289 inline pair<const _Tp&, const _Tp&>
3293 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3295 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3308 template<
typename _Tp,
typename _Compare>
3309 _GLIBCXX14_CONSTEXPR
3310 inline pair<const _Tp&, const _Tp&>
3311 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3317 template<
typename _ForwardIterator,
typename _Compare>
3318 _GLIBCXX14_CONSTEXPR
3319 pair<_ForwardIterator, _ForwardIterator>
3320 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3323 _ForwardIterator __next = __first;
3324 if (__first == __last
3325 || ++__next == __last)
3326 return std::make_pair(__first, __first);
3328 _ForwardIterator __min{}, __max{};
3329 if (__comp(__next, __first))
3343 while (__first != __last)
3346 if (++__next == __last)
3348 if (__comp(__first, __min))
3350 else if (!__comp(__first, __max))
3355 if (__comp(__next, __first))
3357 if (__comp(__next, __min))
3359 if (!__comp(__first, __max))
3364 if (__comp(__first, __min))
3366 if (!__comp(__next, __max))
3374 return std::make_pair(__min, __max);
3388 template<
typename _ForwardIterator>
3389 _GLIBCXX14_CONSTEXPR
3390 inline pair<_ForwardIterator, _ForwardIterator>
3391 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3394 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3395 __glibcxx_function_requires(_LessThanComparableConcept<
3397 __glibcxx_requires_valid_range(__first, __last);
3398 __glibcxx_requires_irreflexive(__first, __last);
3400 return std::__minmax_element(__first, __last,
3401 __gnu_cxx::__ops::__iter_less_iter());
3416 template<
typename _ForwardIterator,
typename _Compare>
3417 _GLIBCXX14_CONSTEXPR
3418 inline pair<_ForwardIterator, _ForwardIterator>
3419 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3423 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3424 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3427 __glibcxx_requires_valid_range(__first, __last);
3428 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3430 return std::__minmax_element(__first, __last,
3431 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3434 template<
typename _Tp>
3435 _GLIBCXX14_CONSTEXPR
3436 inline pair<_Tp, _Tp>
3437 minmax(initializer_list<_Tp> __l)
3439 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3440 pair<const _Tp*, const _Tp*> __p =
3441 std::__minmax_element(__l.begin(), __l.end(),
3442 __gnu_cxx::__ops::__iter_less_iter());
3443 return std::make_pair(*__p.first, *__p.second);
3446 template<
typename _Tp,
typename _Compare>
3447 _GLIBCXX14_CONSTEXPR
3448 inline pair<_Tp, _Tp>
3449 minmax(initializer_list<_Tp> __l, _Compare __comp)
3451 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3452 pair<const _Tp*, const _Tp*> __p =
3453 std::__minmax_element(__l.begin(), __l.end(),
3454 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3455 return std::make_pair(*__p.first, *__p.second);
3472 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3473 typename _BinaryPredicate>
3474 _GLIBCXX20_CONSTEXPR
3476 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3477 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3481 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3482 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3485 __glibcxx_requires_valid_range(__first1, __last1);
3487 return std::__is_permutation(__first1, __last1, __first2,
3488 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3491#if __cplusplus > 201103L
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 = _It1_is_RA() && _It2_is_RA();
3517 for (; __first1 != __last1 && __first2 != __last2;
3518 ++__first1, (void)++__first2)
3519 if (!__pred(__first1, __first2))
3524 if (__first1 == __last1)
3531 if (__d1 == 0 && __d2 == 0)
3537 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3540 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3543 auto __matches = std::__count_if(__first2, __last2,
3544 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3546 || std::__count_if(__scan, __last1,
3547 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3567 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3568 _GLIBCXX20_CONSTEXPR
3570 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3571 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3573 __glibcxx_requires_valid_range(__first1, __last1);
3574 __glibcxx_requires_valid_range(__first2, __last2);
3577 std::__is_permutation(__first1, __last1, __first2, __last2,
3578 __gnu_cxx::__ops::__iter_equal_to_iter());
3595 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3596 typename _BinaryPredicate>
3597 _GLIBCXX20_CONSTEXPR
3599 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3600 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3601 _BinaryPredicate __pred)
3603 __glibcxx_requires_valid_range(__first1, __last1);
3604 __glibcxx_requires_valid_range(__first2, __last2);
3606 return std::__is_permutation(__first1, __last1, __first2, __last2,
3607 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3610#if __cplusplus >= 201703L
3612#define __cpp_lib_clamp 201603L
3625 template<
typename _Tp>
3626 constexpr const _Tp&
3627 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3629 __glibcxx_assert(!(__hi < __lo));
3645 template<
typename _Tp,
typename _Compare>
3646 constexpr const _Tp&
3647 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3649 __glibcxx_assert(!__comp(__hi, __lo));
3655#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3677 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3678 pair<_IntType, _IntType>
3680 _UniformRandomBitGenerator&& __g)
3684 return std::make_pair(__x / __b1, __x % __b1);
3699 template<
typename _RandomAccessIterator,
3700 typename _UniformRandomNumberGenerator>
3702 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3703 _UniformRandomNumberGenerator&& __g)
3706 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3707 _RandomAccessIterator>)
3708 __glibcxx_requires_valid_range(__first, __last);
3710 if (__first == __last)
3716 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3718 typedef typename __distr_type::param_type __p_type;
3720 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3725 const __uc_type __urngrange = __g.max() - __g.min();
3726 const __uc_type __urange = __uc_type(__last - __first);
3728 if (__urngrange / __urange >= __urange)
3731 _RandomAccessIterator __i = __first + 1;
3737 if ((__urange % 2) == 0)
3739 __distr_type __d{0, 1};
3740 std::iter_swap(__i++, __first + __d(__g));
3747 while (__i != __last)
3749 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3754 std::iter_swap(__i++, __first + __pospos.
first);
3755 std::iter_swap(__i++, __first + __pospos.
second);
3763 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3764 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3770_GLIBCXX_BEGIN_NAMESPACE_ALGO
3784 template<
typename _InputIterator,
typename _Function>
3785 _GLIBCXX20_CONSTEXPR
3787 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3790 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3791 __glibcxx_requires_valid_range(__first, __last);
3792 for (; __first != __last; ++__first)
3797#if __cplusplus >= 201703L
3810 template<
typename _InputIterator,
typename _Size,
typename _Function>
3811 _GLIBCXX20_CONSTEXPR
3815 auto __n2 = std::__size_to_integer(__n);
3817 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3821 auto __last = __first + __n2;
3822 std::for_each(__first, __last,
std::move(__f));
3846 template<
typename _InputIterator,
typename _Tp>
3847 _GLIBCXX20_CONSTEXPR
3848 inline _InputIterator
3849 find(_InputIterator __first, _InputIterator __last,
3853 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3854 __glibcxx_function_requires(_EqualOpConcept<
3856 __glibcxx_requires_valid_range(__first, __last);
3858 __gnu_cxx::__ops::__iter_equals_val(__val));
3871 template<
typename _InputIterator,
typename _Predicate>
3872 _GLIBCXX20_CONSTEXPR
3873 inline _InputIterator
3874 find_if(_InputIterator __first, _InputIterator __last,
3878 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3879 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3881 __glibcxx_requires_valid_range(__first, __last);
3884 __gnu_cxx::__ops::__pred_iter(__pred));
3903 template<
typename _InputIterator,
typename _ForwardIterator>
3904 _GLIBCXX20_CONSTEXPR
3906 find_first_of(_InputIterator __first1, _InputIterator __last1,
3907 _ForwardIterator __first2, _ForwardIterator __last2)
3910 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3911 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3912 __glibcxx_function_requires(_EqualOpConcept<
3915 __glibcxx_requires_valid_range(__first1, __last1);
3916 __glibcxx_requires_valid_range(__first2, __last2);
3918 for (; __first1 != __last1; ++__first1)
3919 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3920 if (*__first1 == *__iter)
3944 template<
typename _InputIterator,
typename _ForwardIterator,
3945 typename _BinaryPredicate>
3946 _GLIBCXX20_CONSTEXPR
3948 find_first_of(_InputIterator __first1, _InputIterator __last1,
3949 _ForwardIterator __first2, _ForwardIterator __last2,
3950 _BinaryPredicate __comp)
3953 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3954 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3955 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3958 __glibcxx_requires_valid_range(__first1, __last1);
3959 __glibcxx_requires_valid_range(__first2, __last2);
3961 for (; __first1 != __last1; ++__first1)
3962 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3963 if (__comp(*__first1, *__iter))
3977 template<
typename _ForwardIterator>
3978 _GLIBCXX20_CONSTEXPR
3979 inline _ForwardIterator
3980 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3983 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3984 __glibcxx_function_requires(_EqualityComparableConcept<
3986 __glibcxx_requires_valid_range(__first, __last);
3988 return std::__adjacent_find(__first, __last,
3989 __gnu_cxx::__ops::__iter_equal_to_iter());
4003 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4004 _GLIBCXX20_CONSTEXPR
4005 inline _ForwardIterator
4006 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4007 _BinaryPredicate __binary_pred)
4010 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4011 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4014 __glibcxx_requires_valid_range(__first, __last);
4016 return std::__adjacent_find(__first, __last,
4017 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4029 template<
typename _InputIterator,
typename _Tp>
4030 _GLIBCXX20_CONSTEXPR
4031 inline typename iterator_traits<_InputIterator>::difference_type
4032 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4035 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4036 __glibcxx_function_requires(_EqualOpConcept<
4038 __glibcxx_requires_valid_range(__first, __last);
4040 return std::__count_if(__first, __last,
4041 __gnu_cxx::__ops::__iter_equals_val(__value));
4053 template<
typename _InputIterator,
typename _Predicate>
4054 _GLIBCXX20_CONSTEXPR
4055 inline typename iterator_traits<_InputIterator>::difference_type
4056 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4059 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4060 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4062 __glibcxx_requires_valid_range(__first, __last);
4064 return std::__count_if(__first, __last,
4065 __gnu_cxx::__ops::__pred_iter(__pred));
4094 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4095 _GLIBCXX20_CONSTEXPR
4096 inline _ForwardIterator1
4097 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4098 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4101 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4102 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4103 __glibcxx_function_requires(_EqualOpConcept<
4106 __glibcxx_requires_valid_range(__first1, __last1);
4107 __glibcxx_requires_valid_range(__first2, __last2);
4109 return std::__search(__first1, __last1, __first2, __last2,
4110 __gnu_cxx::__ops::__iter_equal_to_iter());
4134 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4135 typename _BinaryPredicate>
4136 _GLIBCXX20_CONSTEXPR
4137 inline _ForwardIterator1
4138 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4139 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4140 _BinaryPredicate __predicate)
4143 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4144 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4145 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4148 __glibcxx_requires_valid_range(__first1, __last1);
4149 __glibcxx_requires_valid_range(__first2, __last2);
4151 return std::__search(__first1, __last1, __first2, __last2,
4152 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4170 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4171 _GLIBCXX20_CONSTEXPR
4172 inline _ForwardIterator
4173 search_n(_ForwardIterator __first, _ForwardIterator __last,
4174 _Integer __count,
const _Tp& __val)
4177 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4178 __glibcxx_function_requires(_EqualOpConcept<
4180 __glibcxx_requires_valid_range(__first, __last);
4182 return std::__search_n(__first, __last, __count,
4183 __gnu_cxx::__ops::__iter_equals_val(__val));
4204 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4205 typename _BinaryPredicate>
4206 _GLIBCXX20_CONSTEXPR
4207 inline _ForwardIterator
4208 search_n(_ForwardIterator __first, _ForwardIterator __last,
4209 _Integer __count,
const _Tp& __val,
4210 _BinaryPredicate __binary_pred)
4213 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4214 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4216 __glibcxx_requires_valid_range(__first, __last);
4218 return std::__search_n(__first, __last, __count,
4219 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4222#if __cplusplus >= 201703L
4230 template<
typename _ForwardIterator,
typename _Searcher>
4231 _GLIBCXX20_CONSTEXPR
4232 inline _ForwardIterator
4233 search(_ForwardIterator __first, _ForwardIterator __last,
4234 const _Searcher& __searcher)
4235 {
return __searcher(__first, __last).first; }
4254 template<
typename _InputIterator,
typename _OutputIterator,
4255 typename _UnaryOperation>
4256 _GLIBCXX20_CONSTEXPR
4258 transform(_InputIterator __first, _InputIterator __last,
4259 _OutputIterator __result, _UnaryOperation __unary_op)
4262 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4263 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4265 __typeof__(__unary_op(*__first))>)
4266 __glibcxx_requires_valid_range(__first, __last);
4268 for (; __first != __last; ++__first, (void)++__result)
4269 *__result = __unary_op(*__first);
4292 template<
typename _InputIterator1,
typename _InputIterator2,
4293 typename _OutputIterator,
typename _BinaryOperation>
4294 _GLIBCXX20_CONSTEXPR
4296 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4297 _InputIterator2 __first2, _OutputIterator __result,
4298 _BinaryOperation __binary_op)
4301 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4302 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4303 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4305 __typeof__(__binary_op(*__first1,*__first2))>)
4306 __glibcxx_requires_valid_range(__first1, __last1);
4308 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4309 *__result = __binary_op(*__first1, *__first2);
4326 template<
typename _ForwardIterator,
typename _Tp>
4327 _GLIBCXX20_CONSTEXPR
4329 replace(_ForwardIterator __first, _ForwardIterator __last,
4330 const _Tp& __old_value,
const _Tp& __new_value)
4333 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4335 __glibcxx_function_requires(_EqualOpConcept<
4337 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4339 __glibcxx_requires_valid_range(__first, __last);
4341 for (; __first != __last; ++__first)
4342 if (*__first == __old_value)
4343 *__first = __new_value;
4359 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4360 _GLIBCXX20_CONSTEXPR
4362 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4363 _Predicate __pred,
const _Tp& __new_value)
4366 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4368 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4370 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4372 __glibcxx_requires_valid_range(__first, __last);
4374 for (; __first != __last; ++__first)
4375 if (__pred(*__first))
4376 *__first = __new_value;
4391 template<
typename _ForwardIterator,
typename _Generator>
4392 _GLIBCXX20_CONSTEXPR
4394 generate(_ForwardIterator __first, _ForwardIterator __last,
4398 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4399 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4401 __glibcxx_requires_valid_range(__first, __last);
4403 for (; __first != __last; ++__first)
4424 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4425 _GLIBCXX20_CONSTEXPR
4427 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4432 __typeof__(__gen())>)
4434 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4435 for (_IntSize __niter = std::__size_to_integer(__n);
4436 __niter > 0; --__niter, (void) ++__first)
4459 template<
typename _InputIterator,
typename _OutputIterator>
4460 _GLIBCXX20_CONSTEXPR
4461 inline _OutputIterator
4462 unique_copy(_InputIterator __first, _InputIterator __last,
4463 _OutputIterator __result)
4466 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4467 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4469 __glibcxx_function_requires(_EqualityComparableConcept<
4471 __glibcxx_requires_valid_range(__first, __last);
4473 if (__first == __last)
4476 __gnu_cxx::__ops::__iter_equal_to_iter(),
4499 template<
typename _InputIterator,
typename _OutputIterator,
4500 typename _BinaryPredicate>
4501 _GLIBCXX20_CONSTEXPR
4502 inline _OutputIterator
4503 unique_copy(_InputIterator __first, _InputIterator __last,
4504 _OutputIterator __result,
4505 _BinaryPredicate __binary_pred)
4508 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4509 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4511 __glibcxx_requires_valid_range(__first, __last);
4513 if (__first == __last)
4516 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4521#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4538 template<
typename _RandomAccessIterator>
4539 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4541 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4544 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4545 _RandomAccessIterator>)
4546 __glibcxx_requires_valid_range(__first, __last);
4548 if (__first != __last)
4549 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4552 _RandomAccessIterator __j = __first
4553 + std::rand() % ((__i - __first) + 1);
4555 std::iter_swap(__i, __j);
4578 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4579 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4581 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4582#if __cplusplus >= 201103L
4583 _RandomNumberGenerator&& __rand)
4585 _RandomNumberGenerator& __rand)
4589 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4590 _RandomAccessIterator>)
4591 __glibcxx_requires_valid_range(__first, __last);
4593 if (__first == __last)
4595 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4597 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4599 std::iter_swap(__i, __j);
4619 template<
typename _ForwardIterator,
typename _Predicate>
4620 _GLIBCXX20_CONSTEXPR
4621 inline _ForwardIterator
4622 partition(_ForwardIterator __first, _ForwardIterator __last,
4626 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4628 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4630 __glibcxx_requires_valid_range(__first, __last);
4654 template<
typename _RandomAccessIterator>
4655 _GLIBCXX20_CONSTEXPR
4657 partial_sort(_RandomAccessIterator __first,
4658 _RandomAccessIterator __middle,
4659 _RandomAccessIterator __last)
4662 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4663 _RandomAccessIterator>)
4664 __glibcxx_function_requires(_LessThanComparableConcept<
4666 __glibcxx_requires_valid_range(__first, __middle);
4667 __glibcxx_requires_valid_range(__middle, __last);
4668 __glibcxx_requires_irreflexive(__first, __last);
4670 std::__partial_sort(__first, __middle, __last,
4671 __gnu_cxx::__ops::__iter_less_iter());
4693 template<
typename _RandomAccessIterator,
typename _Compare>
4694 _GLIBCXX20_CONSTEXPR
4696 partial_sort(_RandomAccessIterator __first,
4697 _RandomAccessIterator __middle,
4698 _RandomAccessIterator __last,
4702 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4703 _RandomAccessIterator>)
4704 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4707 __glibcxx_requires_valid_range(__first, __middle);
4708 __glibcxx_requires_valid_range(__middle, __last);
4709 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4711 std::__partial_sort(__first, __middle, __last,
4712 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4730 template<
typename _RandomAccessIterator>
4731 _GLIBCXX20_CONSTEXPR
4733 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4734 _RandomAccessIterator __last)
4737 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4738 _RandomAccessIterator>)
4739 __glibcxx_function_requires(_LessThanComparableConcept<
4741 __glibcxx_requires_valid_range(__first, __nth);
4742 __glibcxx_requires_valid_range(__nth, __last);
4743 __glibcxx_requires_irreflexive(__first, __last);
4745 if (__first == __last || __nth == __last)
4748 std::__introselect(__first, __nth, __last,
4750 __gnu_cxx::__ops::__iter_less_iter());
4770 template<
typename _RandomAccessIterator,
typename _Compare>
4771 _GLIBCXX20_CONSTEXPR
4773 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4774 _RandomAccessIterator __last, _Compare __comp)
4777 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4778 _RandomAccessIterator>)
4779 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4782 __glibcxx_requires_valid_range(__first, __nth);
4783 __glibcxx_requires_valid_range(__nth, __last);
4784 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4786 if (__first == __last || __nth == __last)
4789 std::__introselect(__first, __nth, __last,
4791 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4808 template<
typename _RandomAccessIterator>
4809 _GLIBCXX20_CONSTEXPR
4811 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4814 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4815 _RandomAccessIterator>)
4816 __glibcxx_function_requires(_LessThanComparableConcept<
4818 __glibcxx_requires_valid_range(__first, __last);
4819 __glibcxx_requires_irreflexive(__first, __last);
4821 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4839 template<
typename _RandomAccessIterator,
typename _Compare>
4840 _GLIBCXX20_CONSTEXPR
4842 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4846 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4847 _RandomAccessIterator>)
4848 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4851 __glibcxx_requires_valid_range(__first, __last);
4852 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4854 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4857 template<
typename _InputIterator1,
typename _InputIterator2,
4858 typename _OutputIterator,
typename _Compare>
4859 _GLIBCXX20_CONSTEXPR
4861 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4862 _InputIterator2 __first2, _InputIterator2 __last2,
4863 _OutputIterator __result, _Compare __comp)
4865 while (__first1 != __last1 && __first2 != __last2)
4867 if (__comp(__first2, __first1))
4869 *__result = *__first2;
4874 *__result = *__first1;
4879 return std::copy(__first2, __last2,
4880 std::copy(__first1, __last1, __result));
4902 template<
typename _InputIterator1,
typename _InputIterator2,
4903 typename _OutputIterator>
4904 _GLIBCXX20_CONSTEXPR
4905 inline _OutputIterator
4906 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4907 _InputIterator2 __first2, _InputIterator2 __last2,
4908 _OutputIterator __result)
4911 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4912 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4913 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4915 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4917 __glibcxx_function_requires(_LessThanOpConcept<
4920 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4921 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4922 __glibcxx_requires_irreflexive2(__first1, __last1);
4923 __glibcxx_requires_irreflexive2(__first2, __last2);
4925 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4926 __first2, __last2, __result,
4927 __gnu_cxx::__ops::__iter_less_iter());
4953 template<
typename _InputIterator1,
typename _InputIterator2,
4954 typename _OutputIterator,
typename _Compare>
4955 _GLIBCXX20_CONSTEXPR
4956 inline _OutputIterator
4957 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4958 _InputIterator2 __first2, _InputIterator2 __last2,
4959 _OutputIterator __result, _Compare __comp)
4962 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4963 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4964 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4966 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4968 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4971 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4972 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4973 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4974 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4976 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4977 __first2, __last2, __result,
4978 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4981 template<
typename _RandomAccessIterator,
typename _Compare>
4983 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4986 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4988 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4990 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4992 if (__first == __last)
4997 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
4999 if (__buf.begin() == 0)
5002 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5003 _DistanceType(__buf.size()), __comp);
5023 template<
typename _RandomAccessIterator>
5025 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5028 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5029 _RandomAccessIterator>)
5030 __glibcxx_function_requires(_LessThanComparableConcept<
5032 __glibcxx_requires_valid_range(__first, __last);
5033 __glibcxx_requires_irreflexive(__first, __last);
5035 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5036 __gnu_cxx::__ops::__iter_less_iter());
5057 template<
typename _RandomAccessIterator,
typename _Compare>
5059 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5063 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5064 _RandomAccessIterator>)
5065 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5068 __glibcxx_requires_valid_range(__first, __last);
5069 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5071 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5072 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5075 template<
typename _InputIterator1,
typename _InputIterator2,
5076 typename _OutputIterator,
5078 _GLIBCXX20_CONSTEXPR
5080 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5081 _InputIterator2 __first2, _InputIterator2 __last2,
5082 _OutputIterator __result, _Compare __comp)
5084 while (__first1 != __last1 && __first2 != __last2)
5086 if (__comp(__first1, __first2))
5088 *__result = *__first1;
5091 else if (__comp(__first2, __first1))
5093 *__result = *__first2;
5098 *__result = *__first1;
5104 return std::copy(__first2, __last2,
5105 std::copy(__first1, __last1, __result));
5127 template<
typename _InputIterator1,
typename _InputIterator2,
5128 typename _OutputIterator>
5129 _GLIBCXX20_CONSTEXPR
5130 inline _OutputIterator
5131 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5132 _InputIterator2 __first2, _InputIterator2 __last2,
5133 _OutputIterator __result)
5136 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5137 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5138 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5140 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5142 __glibcxx_function_requires(_LessThanOpConcept<
5145 __glibcxx_function_requires(_LessThanOpConcept<
5148 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5149 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5150 __glibcxx_requires_irreflexive2(__first1, __last1);
5151 __glibcxx_requires_irreflexive2(__first2, __last2);
5153 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5154 __first2, __last2, __result,
5155 __gnu_cxx::__ops::__iter_less_iter());
5178 template<
typename _InputIterator1,
typename _InputIterator2,
5179 typename _OutputIterator,
typename _Compare>
5180 _GLIBCXX20_CONSTEXPR
5181 inline _OutputIterator
5182 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5183 _InputIterator2 __first2, _InputIterator2 __last2,
5184 _OutputIterator __result, _Compare __comp)
5187 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5188 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5189 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5191 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5193 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5196 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5199 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5200 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5201 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5202 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5204 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5205 __first2, __last2, __result,
5206 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5209 template<
typename _InputIterator1,
typename _InputIterator2,
5210 typename _OutputIterator,
5212 _GLIBCXX20_CONSTEXPR
5214 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5215 _InputIterator2 __first2, _InputIterator2 __last2,
5216 _OutputIterator __result, _Compare __comp)
5218 while (__first1 != __last1 && __first2 != __last2)
5219 if (__comp(__first1, __first2))
5221 else if (__comp(__first2, __first1))
5225 *__result = *__first1;
5251 template<
typename _InputIterator1,
typename _InputIterator2,
5252 typename _OutputIterator>
5253 _GLIBCXX20_CONSTEXPR
5254 inline _OutputIterator
5255 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5256 _InputIterator2 __first2, _InputIterator2 __last2,
5257 _OutputIterator __result)
5260 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5261 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5262 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5264 __glibcxx_function_requires(_LessThanOpConcept<
5267 __glibcxx_function_requires(_LessThanOpConcept<
5270 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5271 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5272 __glibcxx_requires_irreflexive2(__first1, __last1);
5273 __glibcxx_requires_irreflexive2(__first2, __last2);
5275 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5276 __first2, __last2, __result,
5277 __gnu_cxx::__ops::__iter_less_iter());
5301 template<
typename _InputIterator1,
typename _InputIterator2,
5302 typename _OutputIterator,
typename _Compare>
5303 _GLIBCXX20_CONSTEXPR
5304 inline _OutputIterator
5305 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5306 _InputIterator2 __first2, _InputIterator2 __last2,
5307 _OutputIterator __result, _Compare __comp)
5310 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5311 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5312 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5314 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5317 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5320 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5321 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5322 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5323 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5325 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5326 __first2, __last2, __result,
5327 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5330 template<
typename _InputIterator1,
typename _InputIterator2,
5331 typename _OutputIterator,
5333 _GLIBCXX20_CONSTEXPR
5335 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5336 _InputIterator2 __first2, _InputIterator2 __last2,
5337 _OutputIterator __result, _Compare __comp)
5339 while (__first1 != __last1 && __first2 != __last2)
5340 if (__comp(__first1, __first2))
5342 *__result = *__first1;
5346 else if (__comp(__first2, __first1))
5353 return std::copy(__first1, __last1, __result);
5376 template<
typename _InputIterator1,
typename _InputIterator2,
5377 typename _OutputIterator>
5378 _GLIBCXX20_CONSTEXPR
5379 inline _OutputIterator
5380 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5381 _InputIterator2 __first2, _InputIterator2 __last2,
5382 _OutputIterator __result)
5385 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5386 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5387 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5389 __glibcxx_function_requires(_LessThanOpConcept<
5392 __glibcxx_function_requires(_LessThanOpConcept<
5395 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5396 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5397 __glibcxx_requires_irreflexive2(__first1, __last1);
5398 __glibcxx_requires_irreflexive2(__first2, __last2);
5400 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5401 __first2, __last2, __result,
5402 __gnu_cxx::__ops::__iter_less_iter());
5428 template<
typename _InputIterator1,
typename _InputIterator2,
5429 typename _OutputIterator,
typename _Compare>
5430 _GLIBCXX20_CONSTEXPR
5431 inline _OutputIterator
5432 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5433 _InputIterator2 __first2, _InputIterator2 __last2,
5434 _OutputIterator __result, _Compare __comp)
5437 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5438 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5439 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5441 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5444 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5447 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5448 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5449 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5450 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5452 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5453 __first2, __last2, __result,
5454 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5457 template<
typename _InputIterator1,
typename _InputIterator2,
5458 typename _OutputIterator,
5460 _GLIBCXX20_CONSTEXPR
5462 __set_symmetric_difference(_InputIterator1 __first1,
5463 _InputIterator1 __last1,
5464 _InputIterator2 __first2,
5465 _InputIterator2 __last2,
5466 _OutputIterator __result,
5469 while (__first1 != __last1 && __first2 != __last2)
5470 if (__comp(__first1, __first2))
5472 *__result = *__first1;
5476 else if (__comp(__first2, __first1))
5478 *__result = *__first2;
5487 return std::copy(__first2, __last2,
5488 std::copy(__first1, __last1, __result));
5509 template<
typename _InputIterator1,
typename _InputIterator2,
5510 typename _OutputIterator>
5511 _GLIBCXX20_CONSTEXPR
5512 inline _OutputIterator
5513 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5514 _InputIterator2 __first2, _InputIterator2 __last2,
5515 _OutputIterator __result)
5518 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5519 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5520 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5522 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5524 __glibcxx_function_requires(_LessThanOpConcept<
5527 __glibcxx_function_requires(_LessThanOpConcept<
5530 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5531 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5532 __glibcxx_requires_irreflexive2(__first1, __last1);
5533 __glibcxx_requires_irreflexive2(__first2, __last2);
5535 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5536 __first2, __last2, __result,
5537 __gnu_cxx::__ops::__iter_less_iter());
5561 template<
typename _InputIterator1,
typename _InputIterator2,
5562 typename _OutputIterator,
typename _Compare>
5563 _GLIBCXX20_CONSTEXPR
5564 inline _OutputIterator
5565 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5566 _InputIterator2 __first2, _InputIterator2 __last2,
5567 _OutputIterator __result,
5571 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5572 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5573 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5575 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5577 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5580 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5583 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5584 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5585 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5586 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5588 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5589 __first2, __last2, __result,
5590 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5593 template<
typename _ForwardIterator,
typename _Compare>
5594 _GLIBCXX14_CONSTEXPR
5596 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5599 if (__first == __last)
5601 _ForwardIterator __result = __first;
5602 while (++__first != __last)
5603 if (__comp(__first, __result))
5615 template<
typename _ForwardIterator>
5616 _GLIBCXX14_CONSTEXPR
5618 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5621 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5622 __glibcxx_function_requires(_LessThanComparableConcept<
5624 __glibcxx_requires_valid_range(__first, __last);
5625 __glibcxx_requires_irreflexive(__first, __last);
5627 return _GLIBCXX_STD_A::__min_element(__first, __last,
5628 __gnu_cxx::__ops::__iter_less_iter());
5640 template<
typename _ForwardIterator,
typename _Compare>
5641 _GLIBCXX14_CONSTEXPR
5642 inline _ForwardIterator
5643 min_element(_ForwardIterator __first, _ForwardIterator __last,
5647 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5648 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5651 __glibcxx_requires_valid_range(__first, __last);
5652 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5654 return _GLIBCXX_STD_A::__min_element(__first, __last,
5655 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5658 template<
typename _ForwardIterator,
typename _Compare>
5659 _GLIBCXX14_CONSTEXPR
5661 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5664 if (__first == __last)
return __first;
5665 _ForwardIterator __result = __first;
5666 while (++__first != __last)
5667 if (__comp(__result, __first))
5679 template<
typename _ForwardIterator>
5680 _GLIBCXX14_CONSTEXPR
5681 inline _ForwardIterator
5682 max_element(_ForwardIterator __first, _ForwardIterator __last)
5685 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5686 __glibcxx_function_requires(_LessThanComparableConcept<
5688 __glibcxx_requires_valid_range(__first, __last);
5689 __glibcxx_requires_irreflexive(__first, __last);
5691 return _GLIBCXX_STD_A::__max_element(__first, __last,
5692 __gnu_cxx::__ops::__iter_less_iter());
5704 template<
typename _ForwardIterator,
typename _Compare>
5705 _GLIBCXX14_CONSTEXPR
5706 inline _ForwardIterator
5707 max_element(_ForwardIterator __first, _ForwardIterator __last,
5711 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5712 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5715 __glibcxx_requires_valid_range(__first, __last);
5716 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5718 return _GLIBCXX_STD_A::__max_element(__first, __last,
5719 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5722#if __cplusplus >= 201103L
5724 template<
typename _Tp>
5725 _GLIBCXX14_CONSTEXPR
5727 min(initializer_list<_Tp> __l)
5729 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5730 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5731 __gnu_cxx::__ops::__iter_less_iter());
5734 template<
typename _Tp,
typename _Compare>
5735 _GLIBCXX14_CONSTEXPR
5737 min(initializer_list<_Tp> __l, _Compare __comp)
5739 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5740 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5741 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5744 template<
typename _Tp>
5745 _GLIBCXX14_CONSTEXPR
5747 max(initializer_list<_Tp> __l)
5749 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5750 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5751 __gnu_cxx::__ops::__iter_less_iter());
5754 template<
typename _Tp,
typename _Compare>
5755 _GLIBCXX14_CONSTEXPR
5757 max(initializer_list<_Tp> __l, _Compare __comp)
5759 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5760 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5761 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5765#if __cplusplus >= 201402L
5767 template<
typename _InputIterator,
typename _RandomAccessIterator,
5768 typename _Size,
typename _UniformRandomBitGenerator>
5769 _RandomAccessIterator
5772 _Size __n, _UniformRandomBitGenerator&& __g)
5775 using __param_type =
typename __distrib_type::param_type;
5776 __distrib_type __d{};
5777 _Size __sample_sz = 0;
5778 while (__first != __last && __sample_sz != __n)
5780 __out[__sample_sz++] = *__first;
5783 for (
auto __pop_sz = __sample_sz; __first != __last;
5784 ++__first, (void) ++__pop_sz)
5786 const auto __k = __d(__g, __param_type{0, __pop_sz});
5788 __out[__k] = *__first;
5790 return __out + __sample_sz;
5794 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5795 typename _Size,
typename _UniformRandomBitGenerator>
5797 __sample(_ForwardIterator __first, _ForwardIterator __last,
5799 _OutputIterator __out, _Cat,
5800 _Size __n, _UniformRandomBitGenerator&& __g)
5803 using __param_type =
typename __distrib_type::param_type;
5808 if (__first == __last)
5811 __distrib_type __d{};
5813 __n =
std::min(__n, __unsampled_sz);
5818 const __uc_type __urngrange = __g.max() - __g.min();
5819 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5823 while (__n != 0 && __unsampled_sz >= 2)
5829 if (__p.
first < __n)
5831 *__out++ = *__first;
5837 if (__n == 0)
break;
5842 *__out++ = *__first;
5852 for (; __n != 0; ++__first)
5853 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5855 *__out++ = *__first;
5861#if __cplusplus > 201402L
5862#define __cpp_lib_sample 201603L
5864 template<
typename _PopulationIterator,
typename _SampleIterator,
5865 typename _Distance,
typename _UniformRandomBitGenerator>
5867 sample(_PopulationIterator __first, _PopulationIterator __last,
5868 _SampleIterator __out, _Distance __n,
5869 _UniformRandomBitGenerator&& __g)
5871 using __pop_cat =
typename
5873 using __samp_cat =
typename
5877 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5879 "output range must use a RandomAccessIterator when input range"
5880 " does not meet the ForwardIterator requirements");
5883 "sample size must be an integer type");
5887 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5888 std::forward<_UniformRandomBitGenerator>(__g));
5893_GLIBCXX_END_NAMESPACE_ALGO
5894_GLIBCXX_END_NAMESPACE_VERSION
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
constexpr _InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
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.
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.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_OutputIterator __sample(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag, _OutputIterator __out, _Cat, _Size __n, _UniformRandomBitGenerator &&__g)
Selection sampling algorithm.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
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)
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)
Take a random sample from a population.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
constexpr void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
constexpr _ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
constexpr _InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
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...