64#if __cplusplus >= 201103L
70# if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
77namespace std _GLIBCXX_VISIBILITY(default)
79_GLIBCXX_BEGIN_NAMESPACE_VERSION
82 template<
typename _Iterator,
typename _Compare>
86 _Iterator __c, _Compare __comp)
91 std::iter_swap(__result, __b);
92 else if (__comp(__a, __c))
93 std::iter_swap(__result, __c);
95 std::iter_swap(__result, __a);
97 else if (__comp(__a, __c))
98 std::iter_swap(__result, __a);
99 else if (__comp(__b, __c))
100 std::iter_swap(__result, __c);
102 std::iter_swap(__result, __b);
106 template<
typename _InputIterator,
typename _Predicate>
108 inline _InputIterator
113 __gnu_cxx::__ops::__negate(__pred),
120 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
125 for (; __len; --__len, (void) ++__first)
126 if (!__pred(__first))
144 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
145 typename _BinaryPredicate>
148 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
149 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
150 _BinaryPredicate __predicate)
153 if (__first1 == __last1 || __first2 == __last2)
157 _ForwardIterator2 __p1(__first2);
158 if (++__p1 == __last2)
160 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
163 _ForwardIterator1 __current = __first1;
169 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
171 if (__first1 == __last1)
174 _ForwardIterator2 __p = __p1;
175 __current = __first1;
176 if (++__current == __last1)
179 while (__predicate(__current, __p))
181 if (++__p == __last2)
183 if (++__current == __last1)
196 template<
typename _ForwardIterator,
typename _Integer,
197 typename _UnaryPredicate>
201 _Integer __count, _UnaryPredicate __unary_pred,
205 while (__first != __last)
209 _ForwardIterator __i = __first;
211 while (__i != __last && __n != 1 && __unary_pred(__i))
229 template<
typename _RandomAccessIter,
typename _Integer,
230 typename _UnaryPredicate>
234 _Integer __count, _UnaryPredicate __unary_pred,
240 _DistanceType __tailSize = __last - __first;
241 _DistanceType __remainder = __count;
243 while (__remainder <= __tailSize)
245 __first += __remainder;
246 __tailSize -= __remainder;
249 _RandomAccessIter __backTrack = __first;
250 while (__unary_pred(--__backTrack))
252 if (--__remainder == 0)
253 return (__first - __count);
255 __remainder = __count + 1 - (__first - __backTrack);
260 template<
typename _ForwardIterator,
typename _Integer,
261 typename _UnaryPredicate>
264 __search_n(_ForwardIterator __first, _ForwardIterator __last,
266 _UnaryPredicate __unary_pred)
279 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
280 typename _BinaryPredicate>
283 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
284 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
285 forward_iterator_tag, forward_iterator_tag,
286 _BinaryPredicate __comp)
288 if (__first2 == __last2)
291 _ForwardIterator1 __result = __last1;
294 _ForwardIterator1 __new_result
295 = std::__search(__first1, __last1, __first2, __last2, __comp);
296 if (__new_result == __last1)
300 __result = __new_result;
301 __first1 = __new_result;
308 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
309 typename _BinaryPredicate>
311 _BidirectionalIterator1
312 __find_end(_BidirectionalIterator1 __first1,
313 _BidirectionalIterator1 __last1,
314 _BidirectionalIterator2 __first2,
315 _BidirectionalIterator2 __last2,
316 bidirectional_iterator_tag, bidirectional_iterator_tag,
317 _BinaryPredicate __comp)
320 __glibcxx_function_requires(_BidirectionalIteratorConcept<
321 _BidirectionalIterator1>)
322 __glibcxx_function_requires(_BidirectionalIteratorConcept<
323 _BidirectionalIterator2>)
325 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
326 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
328 _RevIterator1 __rlast1(__first1);
329 _RevIterator2 __rlast2(__first2);
330 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
331 _RevIterator2(__last2), __rlast2,
334 if (__rresult == __rlast1)
338 _BidirectionalIterator1 __result = __rresult.base();
370 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
372 inline _ForwardIterator1
373 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
374 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
377 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
378 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
379 __glibcxx_function_requires(_EqualOpConcept<
382 __glibcxx_requires_valid_range(__first1, __last1);
383 __glibcxx_requires_valid_range(__first2, __last2);
385 return std::__find_end(__first1, __last1, __first2, __last2,
388 __gnu_cxx::__ops::__iter_equal_to_iter());
419 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
420 typename _BinaryPredicate>
422 inline _ForwardIterator1
423 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
424 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
425 _BinaryPredicate __comp)
428 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
430 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
433 __glibcxx_requires_valid_range(__first1, __last1);
434 __glibcxx_requires_valid_range(__first2, __last2);
436 return std::__find_end(__first1, __last1, __first2, __last2,
439 __gnu_cxx::__ops::__iter_comp_iter(__comp));
442#if __cplusplus >= 201103L
455 template<
typename _InputIterator,
typename _Predicate>
458 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
459 {
return __last == std::find_if_not(__first, __last, __pred); }
473 template<
typename _InputIterator,
typename _Predicate>
476 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
492 template<
typename _InputIterator,
typename _Predicate>
495 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
496 {
return !std::none_of(__first, __last, __pred); }
508 template<
typename _InputIterator,
typename _Predicate>
510 inline _InputIterator
511 find_if_not(_InputIterator __first, _InputIterator __last,
515 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
516 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
518 __glibcxx_requires_valid_range(__first, __last);
520 __gnu_cxx::__ops::__pred_iter(__pred));
533 template<
typename _InputIterator,
typename _Predicate>
536 is_partitioned(_InputIterator __first, _InputIterator __last,
539 __first = std::find_if_not(__first, __last, __pred);
540 if (__first == __last)
543 return std::none_of(__first, __last, __pred);
555 template<
typename _ForwardIterator,
typename _Predicate>
558 partition_point(_ForwardIterator __first, _ForwardIterator __last,
562 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
563 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
567 __glibcxx_requires_valid_range(__first, __last);
576 _DistanceType __half = __len >> 1;
577 _ForwardIterator __middle = __first;
579 if (__pred(*__middle))
583 __len = __len - __half - 1;
592 template<
typename _InputIterator,
typename _OutputIterator,
596 __remove_copy_if(_InputIterator __first, _InputIterator __last,
597 _OutputIterator __result, _Predicate __pred)
599 for (; __first != __last; ++__first)
600 if (!__pred(__first))
602 *__result = *__first;
622 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
624 inline _OutputIterator
625 remove_copy(_InputIterator __first, _InputIterator __last,
626 _OutputIterator __result,
const _Tp& __value)
629 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
630 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
632 __glibcxx_function_requires(_EqualOpConcept<
634 __glibcxx_requires_valid_range(__first, __last);
636 return std::__remove_copy_if(__first, __last, __result,
637 __gnu_cxx::__ops::__iter_equals_val(__value));
655 template<
typename _InputIterator,
typename _OutputIterator,
658 inline _OutputIterator
659 remove_copy_if(_InputIterator __first, _InputIterator __last,
660 _OutputIterator __result, _Predicate __pred)
663 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
664 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
666 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
668 __glibcxx_requires_valid_range(__first, __last);
670 return std::__remove_copy_if(__first, __last, __result,
671 __gnu_cxx::__ops::__pred_iter(__pred));
674#if __cplusplus >= 201103L
690 template<
typename _InputIterator,
typename _OutputIterator,
694 copy_if(_InputIterator __first, _InputIterator __last,
695 _OutputIterator __result, _Predicate __pred)
698 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
699 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
701 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
703 __glibcxx_requires_valid_range(__first, __last);
705 for (; __first != __last; ++__first)
706 if (__pred(*__first))
708 *__result = *__first;
714 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
717 __copy_n(_InputIterator __first, _Size __n,
718 _OutputIterator __result, input_iterator_tag)
720 return std::__niter_wrap(__result,
721 __copy_n_a(__first, __n,
722 std::__niter_base(__result),
true));
725 template<
typename _RandomAccessIterator,
typename _Size,
726 typename _OutputIterator>
728 inline _OutputIterator
729 __copy_n(_RandomAccessIterator __first, _Size __n,
730 _OutputIterator __result, random_access_iterator_tag)
731 {
return std::copy(__first, __first + __n, __result); }
746 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
748 inline _OutputIterator
749 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
752 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
753 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
756 const auto __n2 = std::__size_to_integer(__n);
760 __glibcxx_requires_can_increment(__first, __n2);
761 __glibcxx_requires_can_increment(__result, __n2);
763 return std::__copy_n(__first, __n2, __result,
782 template<
typename _InputIterator,
typename _OutputIterator1,
783 typename _OutputIterator2,
typename _Predicate>
785 pair<_OutputIterator1, _OutputIterator2>
786 partition_copy(_InputIterator __first, _InputIterator __last,
787 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
791 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
792 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
794 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
796 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
798 __glibcxx_requires_valid_range(__first, __last);
800 for (; __first != __last; ++__first)
801 if (__pred(*__first))
803 *__out_true = *__first;
808 *__out_false = *__first;
833 template<
typename _ForwardIterator,
typename _Tp>
835 inline _ForwardIterator
836 remove(_ForwardIterator __first, _ForwardIterator __last,
840 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
842 __glibcxx_function_requires(_EqualOpConcept<
844 __glibcxx_requires_valid_range(__first, __last);
846 return std::__remove_if(__first, __last,
847 __gnu_cxx::__ops::__iter_equals_val(__value));
867 template<
typename _ForwardIterator,
typename _Predicate>
869 inline _ForwardIterator
870 remove_if(_ForwardIterator __first, _ForwardIterator __last,
874 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
876 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
878 __glibcxx_requires_valid_range(__first, __last);
880 return std::__remove_if(__first, __last,
881 __gnu_cxx::__ops::__pred_iter(__pred));
884 template<
typename _ForwardIterator,
typename _BinaryPredicate>
887 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
888 _BinaryPredicate __binary_pred)
890 if (__first == __last)
892 _ForwardIterator __next = __first;
893 while (++__next != __last)
895 if (__binary_pred(__first, __next))
902 template<
typename _ForwardIterator,
typename _BinaryPredicate>
905 __unique(_ForwardIterator __first, _ForwardIterator __last,
906 _BinaryPredicate __binary_pred)
909 __first = std::__adjacent_find(__first, __last, __binary_pred);
910 if (__first == __last)
914 _ForwardIterator __dest = __first;
916 while (++__first != __last)
917 if (!__binary_pred(__dest, __first))
918 *++__dest = _GLIBCXX_MOVE(*__first);
936 template<
typename _ForwardIterator>
938 inline _ForwardIterator
939 unique(_ForwardIterator __first, _ForwardIterator __last)
942 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
944 __glibcxx_function_requires(_EqualityComparableConcept<
946 __glibcxx_requires_valid_range(__first, __last);
948 return std::__unique(__first, __last,
949 __gnu_cxx::__ops::__iter_equal_to_iter());
967 template<
typename _ForwardIterator,
typename _BinaryPredicate>
969 inline _ForwardIterator
970 unique(_ForwardIterator __first, _ForwardIterator __last,
971 _BinaryPredicate __binary_pred)
974 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
976 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
979 __glibcxx_requires_valid_range(__first, __last);
981 return std::__unique(__first, __last,
982 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
991 template<
typename _ForwardIterator,
typename _OutputIterator,
992 typename _BinaryPredicate>
996 _OutputIterator __result, _BinaryPredicate __binary_pred,
1000 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1004 _ForwardIterator __next = __first;
1005 *__result = *__first;
1006 while (++__next != __last)
1007 if (!__binary_pred(__first, __next))
1010 *++__result = *__first;
1021 template<
typename _InputIterator,
typename _OutputIterator,
1022 typename _BinaryPredicate>
1023 _GLIBCXX20_CONSTEXPR
1026 _OutputIterator __result, _BinaryPredicate __binary_pred,
1030 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1035 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1037 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1038 *__result = __value;
1039 while (++__first != __last)
1040 if (!__rebound_pred(__first, __value))
1043 *++__result = __value;
1054 template<
typename _InputIterator,
typename _ForwardIterator,
1055 typename _BinaryPredicate>
1056 _GLIBCXX20_CONSTEXPR
1059 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1063 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1066 *__result = *__first;
1067 while (++__first != __last)
1068 if (!__binary_pred(__result, __first))
1069 *++__result = *__first;
1078 template<
typename _B
idirectionalIterator>
1079 _GLIBCXX20_CONSTEXPR
1081 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1085 if (__first == __last || __first == --__last)
1089 std::iter_swap(__first, __last);
1099 template<
typename _RandomAccessIterator>
1100 _GLIBCXX20_CONSTEXPR
1102 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1105 if (__first == __last)
1108 while (__first < __last)
1110 std::iter_swap(__first, __last);
1128 template<
typename _B
idirectionalIterator>
1129 _GLIBCXX20_CONSTEXPR
1131 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1134 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1135 _BidirectionalIterator>)
1136 __glibcxx_requires_valid_range(__first, __last);
1156 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1157 _GLIBCXX20_CONSTEXPR
1159 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1160 _OutputIterator __result)
1163 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1164 _BidirectionalIterator>)
1165 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1167 __glibcxx_requires_valid_range(__first, __last);
1169 while (__first != __last)
1172 *__result = *__last;
1182 template<
typename _Eucl
ideanRingElement>
1183 _GLIBCXX20_CONSTEXPR
1184 _EuclideanRingElement
1185 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1189 _EuclideanRingElement __t = __m % __n;
1196_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1199 template<
typename _ForwardIterator>
1200 _GLIBCXX20_CONSTEXPR
1203 _ForwardIterator __middle,
1204 _ForwardIterator __last,
1207 if (__first == __middle)
1209 else if (__last == __middle)
1212 _ForwardIterator __first2 = __middle;
1215 std::iter_swap(__first, __first2);
1218 if (__first == __middle)
1219 __middle = __first2;
1221 while (__first2 != __last);
1223 _ForwardIterator __ret = __first;
1225 __first2 = __middle;
1227 while (__first2 != __last)
1229 std::iter_swap(__first, __first2);
1232 if (__first == __middle)
1233 __middle = __first2;
1234 else if (__first2 == __last)
1235 __first2 = __middle;
1241 template<
typename _B
idirectionalIterator>
1242 _GLIBCXX20_CONSTEXPR
1243 _BidirectionalIterator
1245 _BidirectionalIterator __middle,
1246 _BidirectionalIterator __last,
1250 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1251 _BidirectionalIterator>)
1253 if (__first == __middle)
1255 else if (__last == __middle)
1261 while (__first != __middle && __middle != __last)
1263 std::iter_swap(__first, --__last);
1267 if (__first == __middle)
1280 template<
typename _RandomAccessIterator>
1281 _GLIBCXX20_CONSTEXPR
1282 _RandomAccessIterator
1284 _RandomAccessIterator __middle,
1285 _RandomAccessIterator __last,
1289 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1290 _RandomAccessIterator>)
1292 if (__first == __middle)
1294 else if (__last == __middle)
1302 _Distance __n = __last - __first;
1303 _Distance __k = __middle - __first;
1305 if (__k == __n - __k)
1307 std::swap_ranges(__first, __middle, __middle);
1311 _RandomAccessIterator __p = __first;
1312 _RandomAccessIterator __ret = __first + (__last - __middle);
1316 if (__k < __n - __k)
1318 if (__is_pod(_ValueType) && __k == 1)
1320 _ValueType __t = _GLIBCXX_MOVE(*__p);
1321 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1322 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1325 _RandomAccessIterator __q = __p + __k;
1326 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1328 std::iter_swap(__p, __q);
1341 if (__is_pod(_ValueType) && __k == 1)
1343 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1344 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1345 *__p = _GLIBCXX_MOVE(__t);
1348 _RandomAccessIterator __q = __p + __n;
1350 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1354 std::iter_swap(__p, __q);
1387 template<
typename _ForwardIterator>
1388 _GLIBCXX20_CONSTEXPR
1389 inline _ForwardIterator
1390 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1391 _ForwardIterator __last)
1394 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1396 __glibcxx_requires_valid_range(__first, __middle);
1397 __glibcxx_requires_valid_range(__middle, __last);
1403_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1425 template<
typename _ForwardIterator,
typename _OutputIterator>
1426 _GLIBCXX20_CONSTEXPR
1427 inline _OutputIterator
1428 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1429 _ForwardIterator __last, _OutputIterator __result)
1432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1433 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1435 __glibcxx_requires_valid_range(__first, __middle);
1436 __glibcxx_requires_valid_range(__middle, __last);
1438 return std::copy(__first, __middle,
1439 std::copy(__middle, __last, __result));
1443 template<
typename _ForwardIterator,
typename _Predicate>
1444 _GLIBCXX20_CONSTEXPR
1449 if (__first == __last)
1452 while (__pred(*__first))
1453 if (++__first == __last)
1456 _ForwardIterator __next = __first;
1458 while (++__next != __last)
1459 if (__pred(*__next))
1461 std::iter_swap(__first, __next);
1469 template<
typename _B
idirectionalIterator,
typename _Predicate>
1470 _GLIBCXX20_CONSTEXPR
1471 _BidirectionalIterator
1472 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1478 if (__first == __last)
1480 else if (__pred(*__first))
1486 if (__first == __last)
1488 else if (!
bool(__pred(*__last)))
1492 std::iter_swap(__first, __last);
1506 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1510 _ForwardIterator __last,
1511 _Predicate __pred, _Distance __len,
1513 _Distance __buffer_size)
1518 if (__len <= __buffer_size)
1520 _ForwardIterator __result1 = __first;
1521 _Pointer __result2 = __buffer;
1526 *__result2 = _GLIBCXX_MOVE(*__first);
1529 for (; __first != __last; ++__first)
1530 if (__pred(__first))
1532 *__result1 = _GLIBCXX_MOVE(*__first);
1537 *__result2 = _GLIBCXX_MOVE(*__first);
1541 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1545 _ForwardIterator __middle = __first;
1547 _ForwardIterator __left_split =
1549 __len / 2, __buffer,
1554 _Distance __right_len = __len - __len / 2;
1555 _ForwardIterator __right_split =
1562 __buffer, __buffer_size);
1564 return std::rotate(__left_split, __middle, __right_split);
1567 template<
typename _ForwardIterator,
typename _Predicate>
1569 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1574 if (__first == __last)
1577 typedef typename iterator_traits<_ForwardIterator>::value_type
1579 typedef typename iterator_traits<_ForwardIterator>::difference_type
1582 _Temporary_buffer<_ForwardIterator, _ValueType>
1586 _DistanceType(__buf.requested_size()),
1588 _DistanceType(__buf.size()));
1608 template<
typename _ForwardIterator,
typename _Predicate>
1609 inline _ForwardIterator
1610 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1614 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1616 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1618 __glibcxx_requires_valid_range(__first, __last);
1620 return std::__stable_partition(__first, __last,
1621 __gnu_cxx::__ops::__pred_iter(__pred));
1628 template<
typename _RandomAccessIterator,
typename _Compare>
1629 _GLIBCXX20_CONSTEXPR
1631 __heap_select(_RandomAccessIterator __first,
1632 _RandomAccessIterator __middle,
1633 _RandomAccessIterator __last, _Compare __comp)
1635 std::__make_heap(__first, __middle, __comp);
1636 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1637 if (__comp(__i, __first))
1638 std::__pop_heap(__first, __middle, __i, __comp);
1643 template<
typename _InputIterator,
typename _RandomAccessIterator,
1645 _GLIBCXX20_CONSTEXPR
1646 _RandomAccessIterator
1647 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1648 _RandomAccessIterator __result_first,
1649 _RandomAccessIterator __result_last,
1652 typedef typename iterator_traits<_InputIterator>::value_type
1654 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1655 typedef typename _RItTraits::difference_type _DistanceType;
1657 if (__result_first == __result_last)
1658 return __result_last;
1659 _RandomAccessIterator __result_real_last = __result_first;
1660 while (__first != __last && __result_real_last != __result_last)
1662 *__result_real_last = *__first;
1663 ++__result_real_last;
1667 std::__make_heap(__result_first, __result_real_last, __comp);
1668 while (__first != __last)
1670 if (__comp(__first, __result_first))
1671 std::__adjust_heap(__result_first, _DistanceType(0),
1672 _DistanceType(__result_real_last
1674 _InputValueType(*__first), __comp);
1677 std::__sort_heap(__result_first, __result_real_last, __comp);
1678 return __result_real_last;
1701 template<
typename _InputIterator,
typename _RandomAccessIterator>
1702 _GLIBCXX20_CONSTEXPR
1703 inline _RandomAccessIterator
1704 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1705 _RandomAccessIterator __result_first,
1706 _RandomAccessIterator __result_last)
1708#ifdef _GLIBCXX_CONCEPT_CHECKS
1716 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1717 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1719 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1721 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1722 __glibcxx_requires_valid_range(__first, __last);
1723 __glibcxx_requires_irreflexive(__first, __last);
1724 __glibcxx_requires_valid_range(__result_first, __result_last);
1726 return std::__partial_sort_copy(__first, __last,
1727 __result_first, __result_last,
1728 __gnu_cxx::__ops::__iter_less_iter());
1751 template<
typename _InputIterator,
typename _RandomAccessIterator,
1753 _GLIBCXX20_CONSTEXPR
1754 inline _RandomAccessIterator
1755 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1756 _RandomAccessIterator __result_first,
1757 _RandomAccessIterator __result_last,
1760#ifdef _GLIBCXX_CONCEPT_CHECKS
1768 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1769 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1770 _RandomAccessIterator>)
1771 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1773 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1774 _InputValueType, _OutputValueType>)
1775 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1776 _OutputValueType, _OutputValueType>)
1777 __glibcxx_requires_valid_range(__first, __last);
1778 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1779 __glibcxx_requires_valid_range(__result_first, __result_last);
1781 return std::__partial_sort_copy(__first, __last,
1782 __result_first, __result_last,
1783 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1789 template<
typename _RandomAccessIterator,
typename _Compare>
1790 _GLIBCXX20_CONSTEXPR
1792 __unguarded_linear_insert(_RandomAccessIterator __last,
1795 typename iterator_traits<_RandomAccessIterator>::value_type
1796 __val = _GLIBCXX_MOVE(*__last);
1797 _RandomAccessIterator __next = __last;
1799 while (__comp(__val, __next))
1801 *__last = _GLIBCXX_MOVE(*__next);
1805 *__last = _GLIBCXX_MOVE(__val);
1809 template<
typename _RandomAccessIterator,
typename _Compare>
1810 _GLIBCXX20_CONSTEXPR
1812 __insertion_sort(_RandomAccessIterator __first,
1813 _RandomAccessIterator __last, _Compare __comp)
1815 if (__first == __last)
return;
1817 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1819 if (__comp(__i, __first))
1821 typename iterator_traits<_RandomAccessIterator>::value_type
1822 __val = _GLIBCXX_MOVE(*__i);
1823 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1824 *__first = _GLIBCXX_MOVE(__val);
1827 std::__unguarded_linear_insert(__i,
1828 __gnu_cxx::__ops::__val_comp_iter(__comp));
1833 template<
typename _RandomAccessIterator,
typename _Compare>
1834 _GLIBCXX20_CONSTEXPR
1836 __unguarded_insertion_sort(_RandomAccessIterator __first,
1837 _RandomAccessIterator __last, _Compare __comp)
1839 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1840 std::__unguarded_linear_insert(__i,
1841 __gnu_cxx::__ops::__val_comp_iter(__comp));
1848 enum { _S_threshold = 16 };
1851 template<
typename _RandomAccessIterator,
typename _Compare>
1852 _GLIBCXX20_CONSTEXPR
1854 __final_insertion_sort(_RandomAccessIterator __first,
1855 _RandomAccessIterator __last, _Compare __comp)
1857 if (__last - __first >
int(_S_threshold))
1859 std::__insertion_sort(__first, __first +
int(_S_threshold), __comp);
1860 std::__unguarded_insertion_sort(__first +
int(_S_threshold), __last,
1864 std::__insertion_sort(__first, __last, __comp);
1868 template<
typename _RandomAccessIterator,
typename _Compare>
1869 _GLIBCXX20_CONSTEXPR
1870 _RandomAccessIterator
1871 __unguarded_partition(_RandomAccessIterator __first,
1872 _RandomAccessIterator __last,
1873 _RandomAccessIterator __pivot, _Compare __comp)
1877 while (__comp(__first, __pivot))
1880 while (__comp(__pivot, __last))
1882 if (!(__first < __last))
1884 std::iter_swap(__first, __last);
1890 template<
typename _RandomAccessIterator,
typename _Compare>
1891 _GLIBCXX20_CONSTEXPR
1892 inline _RandomAccessIterator
1893 __unguarded_partition_pivot(_RandomAccessIterator __first,
1894 _RandomAccessIterator __last, _Compare __comp)
1896 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1899 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1902 template<
typename _RandomAccessIterator,
typename _Compare>
1903 _GLIBCXX20_CONSTEXPR
1905 __partial_sort(_RandomAccessIterator __first,
1906 _RandomAccessIterator __middle,
1907 _RandomAccessIterator __last,
1910 std::__heap_select(__first, __middle, __last, __comp);
1911 std::__sort_heap(__first, __middle, __comp);
1915 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1916 _GLIBCXX20_CONSTEXPR
1918 __introsort_loop(_RandomAccessIterator __first,
1919 _RandomAccessIterator __last,
1920 _Size __depth_limit, _Compare __comp)
1922 while (__last - __first >
int(_S_threshold))
1924 if (__depth_limit == 0)
1926 std::__partial_sort(__first, __last, __last, __comp);
1930 _RandomAccessIterator __cut =
1931 std::__unguarded_partition_pivot(__first, __last, __comp);
1932 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1939 template<
typename _RandomAccessIterator,
typename _Compare>
1940 _GLIBCXX20_CONSTEXPR
1942 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1945 if (__first != __last)
1947 std::__introsort_loop(__first, __last,
1950 std::__final_insertion_sort(__first, __last, __comp);
1954 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1955 _GLIBCXX20_CONSTEXPR
1957 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1958 _RandomAccessIterator __last, _Size __depth_limit,
1961 while (__last - __first > 3)
1963 if (__depth_limit == 0)
1965 std::__heap_select(__first, __nth + 1, __last, __comp);
1967 std::iter_swap(__first, __nth);
1971 _RandomAccessIterator __cut =
1972 std::__unguarded_partition_pivot(__first, __last, __comp);
1978 std::__insertion_sort(__first, __last, __comp);
2002 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2003 _GLIBCXX20_CONSTEXPR
2004 inline _ForwardIterator
2005 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2006 const _Tp& __val, _Compare __comp)
2009 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2010 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2012 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2015 return std::__lower_bound(__first, __last, __val,
2016 __gnu_cxx::__ops::__iter_comp_val(__comp));
2019 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2020 _GLIBCXX20_CONSTEXPR
2022 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2023 const _Tp& __val, _Compare __comp)
2025 typedef typename iterator_traits<_ForwardIterator>::difference_type
2032 _DistanceType __half = __len >> 1;
2033 _ForwardIterator __middle = __first;
2035 if (__comp(__val, __middle))
2041 __len = __len - __half - 1;
2058 template<
typename _ForwardIterator,
typename _Tp>
2059 _GLIBCXX20_CONSTEXPR
2060 inline _ForwardIterator
2061 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2065 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2066 __glibcxx_function_requires(_LessThanOpConcept<
2068 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2070 return std::__upper_bound(__first, __last, __val,
2071 __gnu_cxx::__ops::__val_less_iter());
2089 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2090 _GLIBCXX20_CONSTEXPR
2091 inline _ForwardIterator
2092 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2093 const _Tp& __val, _Compare __comp)
2096 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2097 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2099 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2102 return std::__upper_bound(__first, __last, __val,
2103 __gnu_cxx::__ops::__val_comp_iter(__comp));
2106 template<
typename _ForwardIterator,
typename _Tp,
2107 typename _CompareItTp,
typename _CompareTpIt>
2108 _GLIBCXX20_CONSTEXPR
2109 pair<_ForwardIterator, _ForwardIterator>
2110 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2112 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2114 typedef typename iterator_traits<_ForwardIterator>::difference_type
2121 _DistanceType __half = __len >> 1;
2122 _ForwardIterator __middle = __first;
2124 if (__comp_it_val(__middle, __val))
2128 __len = __len - __half - 1;
2130 else if (__comp_val_it(__val, __middle))
2134 _ForwardIterator __left
2135 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2137 _ForwardIterator __right
2138 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2139 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2142 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2162 template<
typename _ForwardIterator,
typename _Tp>
2163 _GLIBCXX20_CONSTEXPR
2164 inline pair<_ForwardIterator, _ForwardIterator>
2165 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2169 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2170 __glibcxx_function_requires(_LessThanOpConcept<
2172 __glibcxx_function_requires(_LessThanOpConcept<
2174 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2175 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2177 return std::__equal_range(__first, __last, __val,
2178 __gnu_cxx::__ops::__iter_less_val(),
2179 __gnu_cxx::__ops::__val_less_iter());
2199 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2200 _GLIBCXX20_CONSTEXPR
2201 inline pair<_ForwardIterator, _ForwardIterator>
2202 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2203 const _Tp& __val, _Compare __comp)
2206 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2207 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2209 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2211 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2213 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2216 return std::__equal_range(__first, __last, __val,
2217 __gnu_cxx::__ops::__iter_comp_val(__comp),
2218 __gnu_cxx::__ops::__val_comp_iter(__comp));
2233 template<
typename _ForwardIterator,
typename _Tp>
2234 _GLIBCXX20_CONSTEXPR
2236 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2240 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2241 __glibcxx_function_requires(_LessThanOpConcept<
2243 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2244 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2246 _ForwardIterator __i
2247 = std::__lower_bound(__first, __last, __val,
2248 __gnu_cxx::__ops::__iter_less_val());
2249 return __i != __last && !(__val < *__i);
2267 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2268 _GLIBCXX20_CONSTEXPR
2270 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2271 const _Tp& __val, _Compare __comp)
2274 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2275 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2277 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2279 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2282 _ForwardIterator __i
2283 = std::__lower_bound(__first, __last, __val,
2284 __gnu_cxx::__ops::__iter_comp_val(__comp));
2285 return __i != __last && !bool(__comp(__val, *__i));
2291 template<
typename _InputIterator1,
typename _InputIterator2,
2292 typename _OutputIterator,
typename _Compare>
2295 _InputIterator2 __first2, _InputIterator2 __last2,
2296 _OutputIterator __result, _Compare __comp)
2298 while (__first1 != __last1 && __first2 != __last2)
2300 if (__comp(__first2, __first1))
2302 *__result = _GLIBCXX_MOVE(*__first2);
2307 *__result = _GLIBCXX_MOVE(*__first1);
2312 if (__first1 != __last1)
2313 _GLIBCXX_MOVE3(__first1, __last1, __result);
2317 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2318 typename _BidirectionalIterator3,
typename _Compare>
2321 _BidirectionalIterator1 __last1,
2322 _BidirectionalIterator2 __first2,
2323 _BidirectionalIterator2 __last2,
2324 _BidirectionalIterator3 __result,
2327 if (__first1 == __last1)
2329 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2332 else if (__first2 == __last2)
2339 if (__comp(__last2, __last1))
2341 *--__result = _GLIBCXX_MOVE(*__last1);
2342 if (__first1 == __last1)
2344 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2351 *--__result = _GLIBCXX_MOVE(*__last2);
2352 if (__first2 == __last2)
2360 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2362 _BidirectionalIterator1
2364 _BidirectionalIterator1 __middle,
2365 _BidirectionalIterator1 __last,
2366 _Distance __len1, _Distance __len2,
2367 _BidirectionalIterator2 __buffer,
2368 _Distance __buffer_size)
2370 _BidirectionalIterator2 __buffer_end;
2371 if (__len1 > __len2 && __len2 <= __buffer_size)
2375 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2376 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2377 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2382 else if (__len1 <= __buffer_size)
2386 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2387 _GLIBCXX_MOVE3(__middle, __last, __first);
2388 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2394 return std::rotate(__first, __middle, __last);
2398 template<
typename _BidirectionalIterator,
typename _Distance,
2399 typename _Pointer,
typename _Compare>
2402 _BidirectionalIterator __middle,
2403 _BidirectionalIterator __last,
2404 _Distance __len1, _Distance __len2,
2405 _Pointer __buffer, _Compare __comp)
2407 if (__len1 <= __len2)
2409 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2415 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2417 __buffer_end, __last, __comp);
2421 template<
typename _BidirectionalIterator,
typename _Distance,
2422 typename _Pointer,
typename _Compare>
2424 __merge_adaptive_resize(_BidirectionalIterator __first,
2425 _BidirectionalIterator __middle,
2426 _BidirectionalIterator __last,
2427 _Distance __len1, _Distance __len2,
2428 _Pointer __buffer, _Distance __buffer_size,
2431 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2433 __len1, __len2, __buffer, __comp);
2436 _BidirectionalIterator __first_cut = __first;
2437 _BidirectionalIterator __second_cut = __middle;
2438 _Distance __len11 = 0;
2439 _Distance __len22 = 0;
2440 if (__len1 > __len2)
2442 __len11 = __len1 / 2;
2445 = std::__lower_bound(__middle, __last, *__first_cut,
2446 __gnu_cxx::__ops::__iter_comp_val(__comp));
2451 __len22 = __len2 / 2;
2454 = std::__upper_bound(__first, __middle, *__second_cut,
2455 __gnu_cxx::__ops::__val_comp_iter(__comp));
2459 _BidirectionalIterator __new_middle
2461 __len1 - __len11, __len22,
2462 __buffer, __buffer_size);
2463 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2465 __buffer, __buffer_size, __comp);
2466 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2467 __len1 - __len11, __len2 - __len22,
2468 __buffer, __buffer_size, __comp);
2473 template<
typename _BidirectionalIterator,
typename _Distance,
2477 _BidirectionalIterator __middle,
2478 _BidirectionalIterator __last,
2479 _Distance __len1, _Distance __len2,
2482 if (__len1 == 0 || __len2 == 0)
2485 if (__len1 + __len2 == 2)
2487 if (__comp(__middle, __first))
2488 std::iter_swap(__first, __middle);
2492 _BidirectionalIterator __first_cut = __first;
2493 _BidirectionalIterator __second_cut = __middle;
2494 _Distance __len11 = 0;
2495 _Distance __len22 = 0;
2496 if (__len1 > __len2)
2498 __len11 = __len1 / 2;
2501 = std::__lower_bound(__middle, __last, *__first_cut,
2502 __gnu_cxx::__ops::__iter_comp_val(__comp));
2507 __len22 = __len2 / 2;
2510 = std::__upper_bound(__first, __middle, *__second_cut,
2511 __gnu_cxx::__ops::__val_comp_iter(__comp));
2515 _BidirectionalIterator __new_middle
2516 = std::rotate(__first_cut, __middle, __second_cut);
2518 __len11, __len22, __comp);
2520 __len1 - __len11, __len2 - __len22, __comp);
2523 template<
typename _B
idirectionalIterator,
typename _Compare>
2525 __inplace_merge(_BidirectionalIterator __first,
2526 _BidirectionalIterator __middle,
2527 _BidirectionalIterator __last,
2530 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2532 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2535 if (__first == __middle || __middle == __last)
2538 const _DistanceType __len1 =
std::distance(__first, __middle);
2539 const _DistanceType __len2 =
std::distance(__middle, __last);
2542 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2545 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2547 if (__builtin_expect(__buf.size() == __buf.requested_size(),
true))
2549 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2550 else if (__builtin_expect(__buf.begin() == 0,
false))
2552 (__first, __middle, __last, __len1, __len2, __comp);
2554 std::__merge_adaptive_resize
2555 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2556 _DistanceType(__buf.size()), __comp);
2559 (__first, __middle, __last, __len1, __len2, __comp);
2581 template<
typename _B
idirectionalIterator>
2583 inplace_merge(_BidirectionalIterator __first,
2584 _BidirectionalIterator __middle,
2585 _BidirectionalIterator __last)
2588 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2589 _BidirectionalIterator>)
2590 __glibcxx_function_requires(_LessThanComparableConcept<
2592 __glibcxx_requires_sorted(__first, __middle);
2593 __glibcxx_requires_sorted(__middle, __last);
2594 __glibcxx_requires_irreflexive(__first, __last);
2596 std::__inplace_merge(__first, __middle, __last,
2597 __gnu_cxx::__ops::__iter_less_iter());
2622 template<
typename _B
idirectionalIterator,
typename _Compare>
2624 inplace_merge(_BidirectionalIterator __first,
2625 _BidirectionalIterator __middle,
2626 _BidirectionalIterator __last,
2630 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2631 _BidirectionalIterator>)
2632 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2635 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2636 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2637 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2639 std::__inplace_merge(__first, __middle, __last,
2640 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2645 template<
typename _InputIterator,
typename _OutputIterator,
2649 _InputIterator __first2, _InputIterator __last2,
2650 _OutputIterator __result, _Compare __comp)
2652 while (__first1 != __last1 && __first2 != __last2)
2654 if (__comp(__first2, __first1))
2656 *__result = _GLIBCXX_MOVE(*__first2);
2661 *__result = _GLIBCXX_MOVE(*__first1);
2666 return _GLIBCXX_MOVE3(__first2, __last2,
2667 _GLIBCXX_MOVE3(__first1, __last1,
2671 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2672 typename _Distance,
typename _Compare>
2674 __merge_sort_loop(_RandomAccessIterator1 __first,
2675 _RandomAccessIterator1 __last,
2676 _RandomAccessIterator2 __result, _Distance __step_size,
2679 const _Distance __two_step = 2 * __step_size;
2681 while (__last - __first >= __two_step)
2684 __first + __step_size,
2685 __first + __two_step,
2687 __first += __two_step;
2689 __step_size =
std::min(_Distance(__last - __first), __step_size);
2692 __first + __step_size, __last, __result, __comp);
2695 template<
typename _RandomAccessIterator,
typename _Distance,
2697 _GLIBCXX20_CONSTEXPR
2699 __chunk_insertion_sort(_RandomAccessIterator __first,
2700 _RandomAccessIterator __last,
2701 _Distance __chunk_size, _Compare __comp)
2703 while (__last - __first >= __chunk_size)
2705 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2706 __first += __chunk_size;
2708 std::__insertion_sort(__first, __last, __comp);
2711 enum { _S_chunk_size = 7 };
2713 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2715 __merge_sort_with_buffer(_RandomAccessIterator __first,
2716 _RandomAccessIterator __last,
2717 _Pointer __buffer, _Compare __comp)
2719 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2722 const _Distance __len = __last - __first;
2723 const _Pointer __buffer_last = __buffer + __len;
2725 _Distance __step_size = _S_chunk_size;
2726 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2728 while (__step_size < __len)
2730 std::__merge_sort_loop(__first, __last, __buffer,
2731 __step_size, __comp);
2733 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2734 __step_size, __comp);
2739 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2741 __stable_sort_adaptive(_RandomAccessIterator __first,
2742 _RandomAccessIterator __middle,
2743 _RandomAccessIterator __last,
2744 _Pointer __buffer, _Compare __comp)
2746 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2747 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2750 __middle - __first, __last - __middle,
2754 template<
typename _RandomAccessIterator,
typename _Pointer,
2755 typename _Distance,
typename _Compare>
2757 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2758 _RandomAccessIterator __last,
2759 _Pointer __buffer, _Distance __buffer_size,
2762 const _Distance __len = (__last - __first + 1) / 2;
2763 const _RandomAccessIterator __middle = __first + __len;
2764 if (__len > __buffer_size)
2766 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2767 __buffer_size, __comp);
2768 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2769 __buffer_size, __comp);
2770 std::__merge_adaptive_resize(__first, __middle, __last,
2771 _Distance(__middle - __first),
2772 _Distance(__last - __middle),
2773 __buffer, __buffer_size,
2777 std::__stable_sort_adaptive(__first, __middle, __last,
2782 template<
typename _RandomAccessIterator,
typename _Compare>
2785 _RandomAccessIterator __last, _Compare __comp)
2787 if (__last - __first < 15)
2789 std::__insertion_sort(__first, __last, __comp);
2792 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2808 template<
typename _InputIterator1,
typename _InputIterator2,
2810 _GLIBCXX20_CONSTEXPR
2812 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2813 _InputIterator2 __first2, _InputIterator2 __last2,
2816 while (__first1 != __last1 && __first2 != __last2)
2818 if (__comp(__first2, __first1))
2820 if (!__comp(__first1, __first2))
2825 return __first2 == __last2;
2846 template<
typename _InputIterator1,
typename _InputIterator2>
2847 _GLIBCXX20_CONSTEXPR
2849 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2850 _InputIterator2 __first2, _InputIterator2 __last2)
2853 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2854 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2855 __glibcxx_function_requires(_LessThanOpConcept<
2858 __glibcxx_function_requires(_LessThanOpConcept<
2861 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2862 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2863 __glibcxx_requires_irreflexive2(__first1, __last1);
2864 __glibcxx_requires_irreflexive2(__first2, __last2);
2866 return std::__includes(__first1, __last1, __first2, __last2,
2867 __gnu_cxx::__ops::__iter_less_iter());
2891 template<
typename _InputIterator1,
typename _InputIterator2,
2893 _GLIBCXX20_CONSTEXPR
2895 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2896 _InputIterator2 __first2, _InputIterator2 __last2,
2900 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2901 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2902 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2905 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2908 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2909 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2910 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2911 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2913 return std::__includes(__first1, __last1, __first2, __last2,
2914 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2927 template<
typename _B
idirectionalIterator,
typename _Compare>
2928 _GLIBCXX20_CONSTEXPR
2930 __next_permutation(_BidirectionalIterator __first,
2931 _BidirectionalIterator __last, _Compare __comp)
2933 if (__first == __last)
2935 _BidirectionalIterator __i = __first;
2944 _BidirectionalIterator __ii = __i;
2946 if (__comp(__i, __ii))
2948 _BidirectionalIterator __j = __last;
2949 while (!__comp(__i, --__j))
2951 std::iter_swap(__i, __j);
2977 template<
typename _B
idirectionalIterator>
2978 _GLIBCXX20_CONSTEXPR
2980 next_permutation(_BidirectionalIterator __first,
2981 _BidirectionalIterator __last)
2984 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2985 _BidirectionalIterator>)
2986 __glibcxx_function_requires(_LessThanComparableConcept<
2988 __glibcxx_requires_valid_range(__first, __last);
2989 __glibcxx_requires_irreflexive(__first, __last);
2991 return std::__next_permutation
2992 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
3010 template<
typename _B
idirectionalIterator,
typename _Compare>
3011 _GLIBCXX20_CONSTEXPR
3013 next_permutation(_BidirectionalIterator __first,
3014 _BidirectionalIterator __last, _Compare __comp)
3017 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3018 _BidirectionalIterator>)
3019 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3022 __glibcxx_requires_valid_range(__first, __last);
3023 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3025 return std::__next_permutation
3026 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3029 template<
typename _B
idirectionalIterator,
typename _Compare>
3030 _GLIBCXX20_CONSTEXPR
3032 __prev_permutation(_BidirectionalIterator __first,
3033 _BidirectionalIterator __last, _Compare __comp)
3035 if (__first == __last)
3037 _BidirectionalIterator __i = __first;
3046 _BidirectionalIterator __ii = __i;
3048 if (__comp(__ii, __i))
3050 _BidirectionalIterator __j = __last;
3051 while (!__comp(--__j, __i))
3053 std::iter_swap(__i, __j);
3080 template<
typename _B
idirectionalIterator>
3081 _GLIBCXX20_CONSTEXPR
3083 prev_permutation(_BidirectionalIterator __first,
3084 _BidirectionalIterator __last)
3087 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3088 _BidirectionalIterator>)
3089 __glibcxx_function_requires(_LessThanComparableConcept<
3091 __glibcxx_requires_valid_range(__first, __last);
3092 __glibcxx_requires_irreflexive(__first, __last);
3094 return std::__prev_permutation(__first, __last,
3095 __gnu_cxx::__ops::__iter_less_iter());
3113 template<
typename _B
idirectionalIterator,
typename _Compare>
3114 _GLIBCXX20_CONSTEXPR
3116 prev_permutation(_BidirectionalIterator __first,
3117 _BidirectionalIterator __last, _Compare __comp)
3120 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3121 _BidirectionalIterator>)
3122 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3125 __glibcxx_requires_valid_range(__first, __last);
3126 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3128 return std::__prev_permutation(__first, __last,
3129 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3135 template<
typename _InputIterator,
typename _OutputIterator,
3136 typename _Predicate,
typename _Tp>
3137 _GLIBCXX20_CONSTEXPR
3139 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3140 _OutputIterator __result,
3141 _Predicate __pred,
const _Tp& __new_value)
3143 for (; __first != __last; ++__first, (void)++__result)
3144 if (__pred(__first))
3145 *__result = __new_value;
3147 *__result = *__first;
3165 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3166 _GLIBCXX20_CONSTEXPR
3167 inline _OutputIterator
3168 replace_copy(_InputIterator __first, _InputIterator __last,
3169 _OutputIterator __result,
3170 const _Tp& __old_value,
const _Tp& __new_value)
3173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3174 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3176 __glibcxx_function_requires(_EqualOpConcept<
3178 __glibcxx_requires_valid_range(__first, __last);
3180 return std::__replace_copy_if(__first, __last, __result,
3181 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3200 template<
typename _InputIterator,
typename _OutputIterator,
3201 typename _Predicate,
typename _Tp>
3202 _GLIBCXX20_CONSTEXPR
3203 inline _OutputIterator
3204 replace_copy_if(_InputIterator __first, _InputIterator __last,
3205 _OutputIterator __result,
3206 _Predicate __pred,
const _Tp& __new_value)
3209 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3212 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3214 __glibcxx_requires_valid_range(__first, __last);
3216 return std::__replace_copy_if(__first, __last, __result,
3217 __gnu_cxx::__ops::__pred_iter(__pred),
3221#if __cplusplus >= 201103L
3229 template<
typename _ForwardIterator>
3230 _GLIBCXX20_CONSTEXPR
3232 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3233 {
return std::is_sorted_until(__first, __last) == __last; }
3244 template<
typename _ForwardIterator,
typename _Compare>
3245 _GLIBCXX20_CONSTEXPR
3247 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3249 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3251 template<
typename _ForwardIterator,
typename _Compare>
3252 _GLIBCXX20_CONSTEXPR
3254 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3257 if (__first == __last)
3260 _ForwardIterator __next = __first;
3261 for (++__next; __next != __last; __first = __next, (void)++__next)
3262 if (__comp(__next, __first))
3275 template<
typename _ForwardIterator>
3276 _GLIBCXX20_CONSTEXPR
3277 inline _ForwardIterator
3278 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3281 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3282 __glibcxx_function_requires(_LessThanComparableConcept<
3284 __glibcxx_requires_valid_range(__first, __last);
3285 __glibcxx_requires_irreflexive(__first, __last);
3287 return std::__is_sorted_until(__first, __last,
3288 __gnu_cxx::__ops::__iter_less_iter());
3300 template<
typename _ForwardIterator,
typename _Compare>
3301 _GLIBCXX20_CONSTEXPR
3302 inline _ForwardIterator
3303 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3307 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3308 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3311 __glibcxx_requires_valid_range(__first, __last);
3312 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3314 return std::__is_sorted_until(__first, __last,
3315 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3326 template<
typename _Tp>
3327 _GLIBCXX14_CONSTEXPR
3328 inline pair<const _Tp&, const _Tp&>
3332 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3334 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3347 template<
typename _Tp,
typename _Compare>
3348 _GLIBCXX14_CONSTEXPR
3349 inline pair<const _Tp&, const _Tp&>
3350 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3356 template<
typename _ForwardIterator,
typename _Compare>
3357 _GLIBCXX14_CONSTEXPR
3358 pair<_ForwardIterator, _ForwardIterator>
3359 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3362 _ForwardIterator __next = __first;
3363 if (__first == __last
3364 || ++__next == __last)
3365 return std::make_pair(__first, __first);
3367 _ForwardIterator __min{}, __max{};
3368 if (__comp(__next, __first))
3382 while (__first != __last)
3385 if (++__next == __last)
3387 if (__comp(__first, __min))
3389 else if (!__comp(__first, __max))
3394 if (__comp(__next, __first))
3396 if (__comp(__next, __min))
3398 if (!__comp(__first, __max))
3403 if (__comp(__first, __min))
3405 if (!__comp(__next, __max))
3413 return std::make_pair(__min, __max);
3427 template<
typename _ForwardIterator>
3428 _GLIBCXX14_CONSTEXPR
3429 inline pair<_ForwardIterator, _ForwardIterator>
3430 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3433 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3434 __glibcxx_function_requires(_LessThanComparableConcept<
3436 __glibcxx_requires_valid_range(__first, __last);
3437 __glibcxx_requires_irreflexive(__first, __last);
3439 return std::__minmax_element(__first, __last,
3440 __gnu_cxx::__ops::__iter_less_iter());
3455 template<
typename _ForwardIterator,
typename _Compare>
3456 _GLIBCXX14_CONSTEXPR
3457 inline pair<_ForwardIterator, _ForwardIterator>
3458 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3462 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3463 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3466 __glibcxx_requires_valid_range(__first, __last);
3467 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3469 return std::__minmax_element(__first, __last,
3470 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3473 template<
typename _Tp>
3474 _GLIBCXX14_CONSTEXPR
3475 inline pair<_Tp, _Tp>
3476 minmax(initializer_list<_Tp> __l)
3478 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3479 pair<const _Tp*, const _Tp*> __p =
3480 std::__minmax_element(__l.begin(), __l.end(),
3481 __gnu_cxx::__ops::__iter_less_iter());
3482 return std::make_pair(*__p.first, *__p.second);
3485 template<
typename _Tp,
typename _Compare>
3486 _GLIBCXX14_CONSTEXPR
3487 inline pair<_Tp, _Tp>
3488 minmax(initializer_list<_Tp> __l, _Compare __comp)
3490 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3491 pair<const _Tp*, const _Tp*> __p =
3492 std::__minmax_element(__l.begin(), __l.end(),
3493 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3494 return std::make_pair(*__p.first, *__p.second);
3511 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3512 typename _BinaryPredicate>
3513 _GLIBCXX20_CONSTEXPR
3515 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3516 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3519 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3520 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3521 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3524 __glibcxx_requires_valid_range(__first1, __last1);
3526 return std::__is_permutation(__first1, __last1, __first2,
3527 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3530#if __cplusplus > 201103L
3531 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3532 typename _BinaryPredicate>
3533 _GLIBCXX20_CONSTEXPR
3535 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3536 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3537 _BinaryPredicate __pred)
3540 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3542 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3543 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3544 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3545 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3556 for (; __first1 != __last1 && __first2 != __last2;
3557 ++__first1, (void)++__first2)
3558 if (!__pred(__first1, __first2))
3563 if (__first1 == __last1)
3570 if (__d1 == 0 && __d2 == 0)
3576 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3579 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3582 auto __matches = std::__count_if(__first2, __last2,
3583 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3585 || std::__count_if(__scan, __last1,
3586 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3606 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3607 _GLIBCXX20_CONSTEXPR
3609 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3610 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3612 __glibcxx_requires_valid_range(__first1, __last1);
3613 __glibcxx_requires_valid_range(__first2, __last2);
3616 std::__is_permutation(__first1, __last1, __first2, __last2,
3617 __gnu_cxx::__ops::__iter_equal_to_iter());
3634 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3635 typename _BinaryPredicate>
3636 _GLIBCXX20_CONSTEXPR
3638 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3639 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3640 _BinaryPredicate __pred)
3642 __glibcxx_requires_valid_range(__first1, __last1);
3643 __glibcxx_requires_valid_range(__first2, __last2);
3645 return std::__is_permutation(__first1, __last1, __first2, __last2,
3646 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3649#if __cplusplus >= 201703L
3651#define __cpp_lib_clamp 201603L
3664 template<
typename _Tp>
3665 constexpr const _Tp&
3666 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3668 __glibcxx_assert(!(__hi < __lo));
3684 template<
typename _Tp,
typename _Compare>
3685 constexpr const _Tp&
3686 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3688 __glibcxx_assert(!__comp(__hi, __lo));
3694#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3716 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3717 pair<_IntType, _IntType>
3719 _UniformRandomBitGenerator&& __g)
3723 return std::make_pair(__x / __b1, __x % __b1);
3738 template<
typename _RandomAccessIterator,
3739 typename _UniformRandomNumberGenerator>
3741 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3742 _UniformRandomNumberGenerator&& __g)
3745 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3746 _RandomAccessIterator>)
3747 __glibcxx_requires_valid_range(__first, __last);
3749 if (__first == __last)
3755 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3757 typedef typename __distr_type::param_type __p_type;
3759 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3764 const __uc_type __urngrange = __g.max() - __g.min();
3765 const __uc_type __urange = __uc_type(__last - __first);
3767 if (__urngrange / __urange >= __urange)
3770 _RandomAccessIterator __i = __first + 1;
3776 if ((__urange % 2) == 0)
3778 __distr_type __d{0, 1};
3779 std::iter_swap(__i++, __first + __d(__g));
3786 while (__i != __last)
3788 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3793 std::iter_swap(__i++, __first + __pospos.
first);
3794 std::iter_swap(__i++, __first + __pospos.
second);
3802 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3803 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3809_GLIBCXX_BEGIN_NAMESPACE_ALGO
3823 template<
typename _InputIterator,
typename _Function>
3824 _GLIBCXX20_CONSTEXPR
3826 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3829 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3830 __glibcxx_requires_valid_range(__first, __last);
3831 for (; __first != __last; ++__first)
3836#if __cplusplus >= 201703L
3849 template<
typename _InputIterator,
typename _Size,
typename _Function>
3850 _GLIBCXX20_CONSTEXPR
3854 auto __n2 = std::__size_to_integer(__n);
3856 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3860 auto __last = __first + __n2;
3861 std::for_each(__first, __last,
std::move(__f));
3885 template<
typename _InputIterator,
typename _Tp>
3886 _GLIBCXX20_CONSTEXPR
3887 inline _InputIterator
3888 find(_InputIterator __first, _InputIterator __last,
3892 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3893 __glibcxx_function_requires(_EqualOpConcept<
3895 __glibcxx_requires_valid_range(__first, __last);
3897 __gnu_cxx::__ops::__iter_equals_val(__val));
3910 template<
typename _InputIterator,
typename _Predicate>
3911 _GLIBCXX20_CONSTEXPR
3912 inline _InputIterator
3913 find_if(_InputIterator __first, _InputIterator __last,
3917 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3918 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3920 __glibcxx_requires_valid_range(__first, __last);
3923 __gnu_cxx::__ops::__pred_iter(__pred));
3942 template<
typename _InputIterator,
typename _ForwardIterator>
3943 _GLIBCXX20_CONSTEXPR
3945 find_first_of(_InputIterator __first1, _InputIterator __last1,
3946 _ForwardIterator __first2, _ForwardIterator __last2)
3949 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3950 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3951 __glibcxx_function_requires(_EqualOpConcept<
3954 __glibcxx_requires_valid_range(__first1, __last1);
3955 __glibcxx_requires_valid_range(__first2, __last2);
3957 for (; __first1 != __last1; ++__first1)
3958 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3959 if (*__first1 == *__iter)
3983 template<
typename _InputIterator,
typename _ForwardIterator,
3984 typename _BinaryPredicate>
3985 _GLIBCXX20_CONSTEXPR
3987 find_first_of(_InputIterator __first1, _InputIterator __last1,
3988 _ForwardIterator __first2, _ForwardIterator __last2,
3989 _BinaryPredicate __comp)
3992 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3993 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3994 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3997 __glibcxx_requires_valid_range(__first1, __last1);
3998 __glibcxx_requires_valid_range(__first2, __last2);
4000 for (; __first1 != __last1; ++__first1)
4001 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4002 if (__comp(*__first1, *__iter))
4016 template<
typename _ForwardIterator>
4017 _GLIBCXX20_CONSTEXPR
4018 inline _ForwardIterator
4019 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4022 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4023 __glibcxx_function_requires(_EqualityComparableConcept<
4025 __glibcxx_requires_valid_range(__first, __last);
4027 return std::__adjacent_find(__first, __last,
4028 __gnu_cxx::__ops::__iter_equal_to_iter());
4042 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4043 _GLIBCXX20_CONSTEXPR
4044 inline _ForwardIterator
4045 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4046 _BinaryPredicate __binary_pred)
4049 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4050 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4053 __glibcxx_requires_valid_range(__first, __last);
4055 return std::__adjacent_find(__first, __last,
4056 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4068 template<
typename _InputIterator,
typename _Tp>
4069 _GLIBCXX20_CONSTEXPR
4070 inline typename iterator_traits<_InputIterator>::difference_type
4071 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4074 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4075 __glibcxx_function_requires(_EqualOpConcept<
4077 __glibcxx_requires_valid_range(__first, __last);
4079 return std::__count_if(__first, __last,
4080 __gnu_cxx::__ops::__iter_equals_val(__value));
4092 template<
typename _InputIterator,
typename _Predicate>
4093 _GLIBCXX20_CONSTEXPR
4094 inline typename iterator_traits<_InputIterator>::difference_type
4095 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4098 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4099 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4101 __glibcxx_requires_valid_range(__first, __last);
4103 return std::__count_if(__first, __last,
4104 __gnu_cxx::__ops::__pred_iter(__pred));
4133 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4134 _GLIBCXX20_CONSTEXPR
4135 inline _ForwardIterator1
4136 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4137 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4140 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4141 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4142 __glibcxx_function_requires(_EqualOpConcept<
4145 __glibcxx_requires_valid_range(__first1, __last1);
4146 __glibcxx_requires_valid_range(__first2, __last2);
4148 return std::__search(__first1, __last1, __first2, __last2,
4149 __gnu_cxx::__ops::__iter_equal_to_iter());
4173 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4174 typename _BinaryPredicate>
4175 _GLIBCXX20_CONSTEXPR
4176 inline _ForwardIterator1
4177 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4178 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4179 _BinaryPredicate __predicate)
4182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4183 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4184 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4187 __glibcxx_requires_valid_range(__first1, __last1);
4188 __glibcxx_requires_valid_range(__first2, __last2);
4190 return std::__search(__first1, __last1, __first2, __last2,
4191 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4209 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4210 _GLIBCXX20_CONSTEXPR
4211 inline _ForwardIterator
4212 search_n(_ForwardIterator __first, _ForwardIterator __last,
4213 _Integer __count,
const _Tp& __val)
4216 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4217 __glibcxx_function_requires(_EqualOpConcept<
4219 __glibcxx_requires_valid_range(__first, __last);
4221 return std::__search_n(__first, __last, __count,
4222 __gnu_cxx::__ops::__iter_equals_val(__val));
4243 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4244 typename _BinaryPredicate>
4245 _GLIBCXX20_CONSTEXPR
4246 inline _ForwardIterator
4247 search_n(_ForwardIterator __first, _ForwardIterator __last,
4248 _Integer __count,
const _Tp& __val,
4249 _BinaryPredicate __binary_pred)
4252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4253 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4255 __glibcxx_requires_valid_range(__first, __last);
4257 return std::__search_n(__first, __last, __count,
4258 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4261#if __cplusplus >= 201703L
4269 template<
typename _ForwardIterator,
typename _Searcher>
4270 _GLIBCXX20_CONSTEXPR
4271 inline _ForwardIterator
4272 search(_ForwardIterator __first, _ForwardIterator __last,
4273 const _Searcher& __searcher)
4274 {
return __searcher(__first, __last).first; }
4293 template<
typename _InputIterator,
typename _OutputIterator,
4294 typename _UnaryOperation>
4295 _GLIBCXX20_CONSTEXPR
4297 transform(_InputIterator __first, _InputIterator __last,
4298 _OutputIterator __result, _UnaryOperation __unary_op)
4301 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4302 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4304 __typeof__(__unary_op(*__first))>)
4305 __glibcxx_requires_valid_range(__first, __last);
4307 for (; __first != __last; ++__first, (void)++__result)
4308 *__result = __unary_op(*__first);
4331 template<
typename _InputIterator1,
typename _InputIterator2,
4332 typename _OutputIterator,
typename _BinaryOperation>
4333 _GLIBCXX20_CONSTEXPR
4335 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4336 _InputIterator2 __first2, _OutputIterator __result,
4337 _BinaryOperation __binary_op)
4340 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4341 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4342 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4344 __typeof__(__binary_op(*__first1,*__first2))>)
4345 __glibcxx_requires_valid_range(__first1, __last1);
4347 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4348 *__result = __binary_op(*__first1, *__first2);
4365 template<
typename _ForwardIterator,
typename _Tp>
4366 _GLIBCXX20_CONSTEXPR
4368 replace(_ForwardIterator __first, _ForwardIterator __last,
4369 const _Tp& __old_value,
const _Tp& __new_value)
4372 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4374 __glibcxx_function_requires(_EqualOpConcept<
4376 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4378 __glibcxx_requires_valid_range(__first, __last);
4380 for (; __first != __last; ++__first)
4381 if (*__first == __old_value)
4382 *__first = __new_value;
4398 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4399 _GLIBCXX20_CONSTEXPR
4401 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4402 _Predicate __pred,
const _Tp& __new_value)
4405 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4407 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4409 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4411 __glibcxx_requires_valid_range(__first, __last);
4413 for (; __first != __last; ++__first)
4414 if (__pred(*__first))
4415 *__first = __new_value;
4430 template<
typename _ForwardIterator,
typename _Generator>
4431 _GLIBCXX20_CONSTEXPR
4433 generate(_ForwardIterator __first, _ForwardIterator __last,
4437 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4438 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4440 __glibcxx_requires_valid_range(__first, __last);
4442 for (; __first != __last; ++__first)
4463 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4464 _GLIBCXX20_CONSTEXPR
4466 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4469 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4471 __typeof__(__gen())>)
4473 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4474 for (_IntSize __niter = std::__size_to_integer(__n);
4475 __niter > 0; --__niter, (void) ++__first)
4498 template<
typename _InputIterator,
typename _OutputIterator>
4499 _GLIBCXX20_CONSTEXPR
4500 inline _OutputIterator
4501 unique_copy(_InputIterator __first, _InputIterator __last,
4502 _OutputIterator __result)
4505 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4506 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4508 __glibcxx_function_requires(_EqualityComparableConcept<
4510 __glibcxx_requires_valid_range(__first, __last);
4512 if (__first == __last)
4515 __gnu_cxx::__ops::__iter_equal_to_iter(),
4538 template<
typename _InputIterator,
typename _OutputIterator,
4539 typename _BinaryPredicate>
4540 _GLIBCXX20_CONSTEXPR
4541 inline _OutputIterator
4542 unique_copy(_InputIterator __first, _InputIterator __last,
4543 _OutputIterator __result,
4544 _BinaryPredicate __binary_pred)
4547 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4548 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4550 __glibcxx_requires_valid_range(__first, __last);
4552 if (__first == __last)
4555 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4560#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4577 template<
typename _RandomAccessIterator>
4578 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4580 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4583 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4584 _RandomAccessIterator>)
4585 __glibcxx_requires_valid_range(__first, __last);
4587 if (__first != __last)
4588 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4591 _RandomAccessIterator __j = __first
4592 + std::rand() % ((__i - __first) + 1);
4594 std::iter_swap(__i, __j);
4616 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4617 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4619 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4620#if __cplusplus >= 201103L
4621 _RandomNumberGenerator&& __rand)
4623 _RandomNumberGenerator& __rand)
4627 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4628 _RandomAccessIterator>)
4629 __glibcxx_requires_valid_range(__first, __last);
4631 if (__first == __last)
4633 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4635 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4637 std::iter_swap(__i, __j);
4658 template<
typename _ForwardIterator,
typename _Predicate>
4659 _GLIBCXX20_CONSTEXPR
4660 inline _ForwardIterator
4661 partition(_ForwardIterator __first, _ForwardIterator __last,
4665 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4667 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4669 __glibcxx_requires_valid_range(__first, __last);
4693 template<
typename _RandomAccessIterator>
4694 _GLIBCXX20_CONSTEXPR
4696 partial_sort(_RandomAccessIterator __first,
4697 _RandomAccessIterator __middle,
4698 _RandomAccessIterator __last)
4701 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4702 _RandomAccessIterator>)
4703 __glibcxx_function_requires(_LessThanComparableConcept<
4705 __glibcxx_requires_valid_range(__first, __middle);
4706 __glibcxx_requires_valid_range(__middle, __last);
4707 __glibcxx_requires_irreflexive(__first, __last);
4709 std::__partial_sort(__first, __middle, __last,
4710 __gnu_cxx::__ops::__iter_less_iter());
4732 template<
typename _RandomAccessIterator,
typename _Compare>
4733 _GLIBCXX20_CONSTEXPR
4735 partial_sort(_RandomAccessIterator __first,
4736 _RandomAccessIterator __middle,
4737 _RandomAccessIterator __last,
4741 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4742 _RandomAccessIterator>)
4743 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4746 __glibcxx_requires_valid_range(__first, __middle);
4747 __glibcxx_requires_valid_range(__middle, __last);
4748 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4750 std::__partial_sort(__first, __middle, __last,
4751 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4769 template<
typename _RandomAccessIterator>
4770 _GLIBCXX20_CONSTEXPR
4772 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4773 _RandomAccessIterator __last)
4776 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4777 _RandomAccessIterator>)
4778 __glibcxx_function_requires(_LessThanComparableConcept<
4780 __glibcxx_requires_valid_range(__first, __nth);
4781 __glibcxx_requires_valid_range(__nth, __last);
4782 __glibcxx_requires_irreflexive(__first, __last);
4784 if (__first == __last || __nth == __last)
4787 std::__introselect(__first, __nth, __last,
4789 __gnu_cxx::__ops::__iter_less_iter());
4809 template<
typename _RandomAccessIterator,
typename _Compare>
4810 _GLIBCXX20_CONSTEXPR
4812 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4813 _RandomAccessIterator __last, _Compare __comp)
4816 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4817 _RandomAccessIterator>)
4818 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4821 __glibcxx_requires_valid_range(__first, __nth);
4822 __glibcxx_requires_valid_range(__nth, __last);
4823 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4825 if (__first == __last || __nth == __last)
4828 std::__introselect(__first, __nth, __last,
4830 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4847 template<
typename _RandomAccessIterator>
4848 _GLIBCXX20_CONSTEXPR
4850 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4853 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4854 _RandomAccessIterator>)
4855 __glibcxx_function_requires(_LessThanComparableConcept<
4857 __glibcxx_requires_valid_range(__first, __last);
4858 __glibcxx_requires_irreflexive(__first, __last);
4860 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4878 template<
typename _RandomAccessIterator,
typename _Compare>
4879 _GLIBCXX20_CONSTEXPR
4881 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4885 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4886 _RandomAccessIterator>)
4887 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4890 __glibcxx_requires_valid_range(__first, __last);
4891 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4893 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4896 template<
typename _InputIterator1,
typename _InputIterator2,
4897 typename _OutputIterator,
typename _Compare>
4898 _GLIBCXX20_CONSTEXPR
4900 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4901 _InputIterator2 __first2, _InputIterator2 __last2,
4902 _OutputIterator __result, _Compare __comp)
4904 while (__first1 != __last1 && __first2 != __last2)
4906 if (__comp(__first2, __first1))
4908 *__result = *__first2;
4913 *__result = *__first1;
4918 return std::copy(__first2, __last2,
4919 std::copy(__first1, __last1, __result));
4941 template<
typename _InputIterator1,
typename _InputIterator2,
4942 typename _OutputIterator>
4943 _GLIBCXX20_CONSTEXPR
4944 inline _OutputIterator
4945 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4946 _InputIterator2 __first2, _InputIterator2 __last2,
4947 _OutputIterator __result)
4950 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4951 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4952 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4954 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4956 __glibcxx_function_requires(_LessThanOpConcept<
4959 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4960 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4961 __glibcxx_requires_irreflexive2(__first1, __last1);
4962 __glibcxx_requires_irreflexive2(__first2, __last2);
4964 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4965 __first2, __last2, __result,
4966 __gnu_cxx::__ops::__iter_less_iter());
4992 template<
typename _InputIterator1,
typename _InputIterator2,
4993 typename _OutputIterator,
typename _Compare>
4994 _GLIBCXX20_CONSTEXPR
4995 inline _OutputIterator
4996 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4997 _InputIterator2 __first2, _InputIterator2 __last2,
4998 _OutputIterator __result, _Compare __comp)
5001 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5002 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5003 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5005 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5007 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5010 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5011 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5012 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5013 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5015 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5016 __first2, __last2, __result,
5017 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5020 template<
typename _RandomAccessIterator,
typename _Compare>
5022 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5025 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5027 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5030 if (__first == __last)
5034 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5037 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
5039 if (__builtin_expect(__buf.requested_size() == __buf.size(),
true))
5040 std::__stable_sort_adaptive(__first,
5041 __first + _DistanceType(__buf.size()),
5042 __last, __buf.begin(), __comp);
5043 else if (__builtin_expect(__buf.begin() == 0,
false))
5046 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
5047 _DistanceType(__buf.size()), __comp);
5070 template<
typename _RandomAccessIterator>
5072 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5075 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5076 _RandomAccessIterator>)
5077 __glibcxx_function_requires(_LessThanComparableConcept<
5079 __glibcxx_requires_valid_range(__first, __last);
5080 __glibcxx_requires_irreflexive(__first, __last);
5082 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5083 __gnu_cxx::__ops::__iter_less_iter());
5104 template<
typename _RandomAccessIterator,
typename _Compare>
5106 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5110 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5111 _RandomAccessIterator>)
5112 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5115 __glibcxx_requires_valid_range(__first, __last);
5116 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5118 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5119 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5122 template<
typename _InputIterator1,
typename _InputIterator2,
5123 typename _OutputIterator,
5125 _GLIBCXX20_CONSTEXPR
5127 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5128 _InputIterator2 __first2, _InputIterator2 __last2,
5129 _OutputIterator __result, _Compare __comp)
5131 while (__first1 != __last1 && __first2 != __last2)
5133 if (__comp(__first1, __first2))
5135 *__result = *__first1;
5138 else if (__comp(__first2, __first1))
5140 *__result = *__first2;
5145 *__result = *__first1;
5151 return std::copy(__first2, __last2,
5152 std::copy(__first1, __last1, __result));
5174 template<
typename _InputIterator1,
typename _InputIterator2,
5175 typename _OutputIterator>
5176 _GLIBCXX20_CONSTEXPR
5177 inline _OutputIterator
5178 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5179 _InputIterator2 __first2, _InputIterator2 __last2,
5180 _OutputIterator __result)
5183 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5184 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5185 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5187 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5189 __glibcxx_function_requires(_LessThanOpConcept<
5192 __glibcxx_function_requires(_LessThanOpConcept<
5195 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5196 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5197 __glibcxx_requires_irreflexive2(__first1, __last1);
5198 __glibcxx_requires_irreflexive2(__first2, __last2);
5200 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5201 __first2, __last2, __result,
5202 __gnu_cxx::__ops::__iter_less_iter());
5225 template<
typename _InputIterator1,
typename _InputIterator2,
5226 typename _OutputIterator,
typename _Compare>
5227 _GLIBCXX20_CONSTEXPR
5228 inline _OutputIterator
5229 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5230 _InputIterator2 __first2, _InputIterator2 __last2,
5231 _OutputIterator __result, _Compare __comp)
5234 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5235 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5236 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5238 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5240 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5243 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5246 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5247 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5248 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5249 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5251 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5252 __first2, __last2, __result,
5253 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5256 template<
typename _InputIterator1,
typename _InputIterator2,
5257 typename _OutputIterator,
5259 _GLIBCXX20_CONSTEXPR
5261 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5262 _InputIterator2 __first2, _InputIterator2 __last2,
5263 _OutputIterator __result, _Compare __comp)
5265 while (__first1 != __last1 && __first2 != __last2)
5266 if (__comp(__first1, __first2))
5268 else if (__comp(__first2, __first1))
5272 *__result = *__first1;
5298 template<
typename _InputIterator1,
typename _InputIterator2,
5299 typename _OutputIterator>
5300 _GLIBCXX20_CONSTEXPR
5301 inline _OutputIterator
5302 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5303 _InputIterator2 __first2, _InputIterator2 __last2,
5304 _OutputIterator __result)
5307 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5308 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5309 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5311 __glibcxx_function_requires(_LessThanOpConcept<
5314 __glibcxx_function_requires(_LessThanOpConcept<
5317 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5318 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5319 __glibcxx_requires_irreflexive2(__first1, __last1);
5320 __glibcxx_requires_irreflexive2(__first2, __last2);
5322 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5323 __first2, __last2, __result,
5324 __gnu_cxx::__ops::__iter_less_iter());
5348 template<
typename _InputIterator1,
typename _InputIterator2,
5349 typename _OutputIterator,
typename _Compare>
5350 _GLIBCXX20_CONSTEXPR
5351 inline _OutputIterator
5352 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5353 _InputIterator2 __first2, _InputIterator2 __last2,
5354 _OutputIterator __result, _Compare __comp)
5357 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5358 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5359 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5361 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5364 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5367 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5368 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5369 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5370 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5372 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5373 __first2, __last2, __result,
5374 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5377 template<
typename _InputIterator1,
typename _InputIterator2,
5378 typename _OutputIterator,
5380 _GLIBCXX20_CONSTEXPR
5382 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5383 _InputIterator2 __first2, _InputIterator2 __last2,
5384 _OutputIterator __result, _Compare __comp)
5386 while (__first1 != __last1 && __first2 != __last2)
5387 if (__comp(__first1, __first2))
5389 *__result = *__first1;
5393 else if (__comp(__first2, __first1))
5400 return std::copy(__first1, __last1, __result);
5423 template<
typename _InputIterator1,
typename _InputIterator2,
5424 typename _OutputIterator>
5425 _GLIBCXX20_CONSTEXPR
5426 inline _OutputIterator
5427 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5428 _InputIterator2 __first2, _InputIterator2 __last2,
5429 _OutputIterator __result)
5432 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5433 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5434 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5436 __glibcxx_function_requires(_LessThanOpConcept<
5439 __glibcxx_function_requires(_LessThanOpConcept<
5442 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5443 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5444 __glibcxx_requires_irreflexive2(__first1, __last1);
5445 __glibcxx_requires_irreflexive2(__first2, __last2);
5447 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5448 __first2, __last2, __result,
5449 __gnu_cxx::__ops::__iter_less_iter());
5475 template<
typename _InputIterator1,
typename _InputIterator2,
5476 typename _OutputIterator,
typename _Compare>
5477 _GLIBCXX20_CONSTEXPR
5478 inline _OutputIterator
5479 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5480 _InputIterator2 __first2, _InputIterator2 __last2,
5481 _OutputIterator __result, _Compare __comp)
5484 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5485 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5486 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5488 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5491 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5494 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5495 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5496 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5497 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5499 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5500 __first2, __last2, __result,
5501 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5504 template<
typename _InputIterator1,
typename _InputIterator2,
5505 typename _OutputIterator,
5507 _GLIBCXX20_CONSTEXPR
5509 __set_symmetric_difference(_InputIterator1 __first1,
5510 _InputIterator1 __last1,
5511 _InputIterator2 __first2,
5512 _InputIterator2 __last2,
5513 _OutputIterator __result,
5516 while (__first1 != __last1 && __first2 != __last2)
5517 if (__comp(__first1, __first2))
5519 *__result = *__first1;
5523 else if (__comp(__first2, __first1))
5525 *__result = *__first2;
5534 return std::copy(__first2, __last2,
5535 std::copy(__first1, __last1, __result));
5556 template<
typename _InputIterator1,
typename _InputIterator2,
5557 typename _OutputIterator>
5558 _GLIBCXX20_CONSTEXPR
5559 inline _OutputIterator
5560 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5561 _InputIterator2 __first2, _InputIterator2 __last2,
5562 _OutputIterator __result)
5565 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5566 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5567 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5569 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5571 __glibcxx_function_requires(_LessThanOpConcept<
5574 __glibcxx_function_requires(_LessThanOpConcept<
5577 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5578 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5579 __glibcxx_requires_irreflexive2(__first1, __last1);
5580 __glibcxx_requires_irreflexive2(__first2, __last2);
5582 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5583 __first2, __last2, __result,
5584 __gnu_cxx::__ops::__iter_less_iter());
5608 template<
typename _InputIterator1,
typename _InputIterator2,
5609 typename _OutputIterator,
typename _Compare>
5610 _GLIBCXX20_CONSTEXPR
5611 inline _OutputIterator
5612 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5613 _InputIterator2 __first2, _InputIterator2 __last2,
5614 _OutputIterator __result,
5618 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5619 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5620 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5622 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5624 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5627 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5630 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5631 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5632 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5633 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5635 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5636 __first2, __last2, __result,
5637 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5640 template<
typename _ForwardIterator,
typename _Compare>
5641 _GLIBCXX14_CONSTEXPR
5643 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5646 if (__first == __last)
5648 _ForwardIterator __result = __first;
5649 while (++__first != __last)
5650 if (__comp(__first, __result))
5662 template<
typename _ForwardIterator>
5663 _GLIBCXX14_CONSTEXPR
5665 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5668 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5669 __glibcxx_function_requires(_LessThanComparableConcept<
5671 __glibcxx_requires_valid_range(__first, __last);
5672 __glibcxx_requires_irreflexive(__first, __last);
5674 return _GLIBCXX_STD_A::__min_element(__first, __last,
5675 __gnu_cxx::__ops::__iter_less_iter());
5687 template<
typename _ForwardIterator,
typename _Compare>
5688 _GLIBCXX14_CONSTEXPR
5689 inline _ForwardIterator
5690 min_element(_ForwardIterator __first, _ForwardIterator __last,
5694 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5695 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5698 __glibcxx_requires_valid_range(__first, __last);
5699 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5701 return _GLIBCXX_STD_A::__min_element(__first, __last,
5702 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5705 template<
typename _ForwardIterator,
typename _Compare>
5706 _GLIBCXX14_CONSTEXPR
5708 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5711 if (__first == __last)
return __first;
5712 _ForwardIterator __result = __first;
5713 while (++__first != __last)
5714 if (__comp(__result, __first))
5726 template<
typename _ForwardIterator>
5727 _GLIBCXX14_CONSTEXPR
5728 inline _ForwardIterator
5729 max_element(_ForwardIterator __first, _ForwardIterator __last)
5732 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5733 __glibcxx_function_requires(_LessThanComparableConcept<
5735 __glibcxx_requires_valid_range(__first, __last);
5736 __glibcxx_requires_irreflexive(__first, __last);
5738 return _GLIBCXX_STD_A::__max_element(__first, __last,
5739 __gnu_cxx::__ops::__iter_less_iter());
5751 template<
typename _ForwardIterator,
typename _Compare>
5752 _GLIBCXX14_CONSTEXPR
5753 inline _ForwardIterator
5754 max_element(_ForwardIterator __first, _ForwardIterator __last,
5758 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5759 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5762 __glibcxx_requires_valid_range(__first, __last);
5763 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5765 return _GLIBCXX_STD_A::__max_element(__first, __last,
5766 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5769#if __cplusplus >= 201103L
5771 template<
typename _Tp>
5772 _GLIBCXX14_CONSTEXPR
5774 min(initializer_list<_Tp> __l)
5776 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5777 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5778 __gnu_cxx::__ops::__iter_less_iter());
5781 template<
typename _Tp,
typename _Compare>
5782 _GLIBCXX14_CONSTEXPR
5784 min(initializer_list<_Tp> __l, _Compare __comp)
5786 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5787 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5788 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5791 template<
typename _Tp>
5792 _GLIBCXX14_CONSTEXPR
5794 max(initializer_list<_Tp> __l)
5796 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5797 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5798 __gnu_cxx::__ops::__iter_less_iter());
5801 template<
typename _Tp,
typename _Compare>
5802 _GLIBCXX14_CONSTEXPR
5804 max(initializer_list<_Tp> __l, _Compare __comp)
5806 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5807 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5808 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5812#if __cplusplus >= 201402L
5814 template<
typename _InputIterator,
typename _RandomAccessIterator,
5815 typename _Size,
typename _UniformRandomBitGenerator>
5816 _RandomAccessIterator
5819 _Size __n, _UniformRandomBitGenerator&& __g)
5822 using __param_type =
typename __distrib_type::param_type;
5823 __distrib_type __d{};
5824 _Size __sample_sz = 0;
5825 while (__first != __last && __sample_sz != __n)
5827 __out[__sample_sz++] = *__first;
5830 for (
auto __pop_sz = __sample_sz; __first != __last;
5831 ++__first, (void) ++__pop_sz)
5833 const auto __k = __d(__g, __param_type{0, __pop_sz});
5835 __out[__k] = *__first;
5837 return __out + __sample_sz;
5841 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5842 typename _Size,
typename _UniformRandomBitGenerator>
5844 __sample(_ForwardIterator __first, _ForwardIterator __last,
5846 _OutputIterator __out, _Cat,
5847 _Size __n, _UniformRandomBitGenerator&& __g)
5850 using __param_type =
typename __distrib_type::param_type;
5855 if (__first == __last)
5858 __distrib_type __d{};
5860 __n =
std::min(__n, __unsampled_sz);
5865 const __uc_type __urngrange = __g.max() - __g.min();
5866 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5870 while (__n != 0 && __unsampled_sz >= 2)
5876 if (__p.
first < __n)
5878 *__out++ = *__first;
5884 if (__n == 0)
break;
5889 *__out++ = *__first;
5899 for (; __n != 0; ++__first)
5900 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5902 *__out++ = *__first;
5908#if __cplusplus > 201402L
5909#define __cpp_lib_sample 201603L
5911 template<
typename _PopulationIterator,
typename _SampleIterator,
5912 typename _Distance,
typename _UniformRandomBitGenerator>
5914 sample(_PopulationIterator __first, _PopulationIterator __last,
5915 _SampleIterator __out, _Distance __n,
5916 _UniformRandomBitGenerator&& __g)
5918 using __pop_cat =
typename
5920 using __samp_cat =
typename
5924 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5925 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5926 "output range must use a RandomAccessIterator when input range"
5927 " does not meet the ForwardIterator requirements");
5930 "sample size must be an integer type");
5934 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5935 std::forward<_UniformRandomBitGenerator>(__g));
5940_GLIBCXX_END_NAMESPACE_ALGO
5941_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.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Compare __comp)
This is a helper function for the merge routines.
constexpr _InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
constexpr _OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_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...