65 #if __cplusplus >= 201103L
71 namespace std _GLIBCXX_VISIBILITY(default)
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator,
typename _Compare>
80 _Iterator __c, _Compare __comp)
86 else if (__comp(__a, __c))
91 else if (__comp(__a, __c))
93 else if (__comp(__b, __c))
100 template<
typename _InputIterator,
typename _Predicate>
102 inline _InputIterator
103 __find_if(_InputIterator __first, _InputIterator __last,
106 while (__first != __last && !__pred(__first))
112 template<
typename _RandomAccessIterator,
typename _Predicate>
114 _RandomAccessIterator
115 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
119 __trip_count = (__last - __first) >> 2;
121 for (; __trip_count > 0; --__trip_count)
140 switch (__last - __first)
160 template<
typename _Iterator,
typename _Predicate>
163 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
165 return __find_if(__first, __last, __pred,
170 template<
typename _InputIterator,
typename _Predicate>
172 inline _InputIterator
177 __gnu_cxx::__ops::__negate(__pred),
184 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
189 for (; __len; --__len, (void) ++__first)
190 if (!__pred(__first))
208 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
209 typename _BinaryPredicate>
212 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
213 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
214 _BinaryPredicate __predicate)
217 if (__first1 == __last1 || __first2 == __last2)
221 _ForwardIterator2 __p1(__first2);
222 if (++__p1 == __last2)
224 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
227 _ForwardIterator1 __current = __first1;
233 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
235 if (__first1 == __last1)
238 _ForwardIterator2 __p = __p1;
239 __current = __first1;
240 if (++__current == __last1)
243 while (__predicate(__current, __p))
245 if (++__p == __last2)
247 if (++__current == __last1)
260 template<
typename _ForwardIterator,
typename _Integer,
261 typename _UnaryPredicate>
265 _Integer __count, _UnaryPredicate __unary_pred,
269 while (__first != __last)
273 _ForwardIterator __i = __first;
275 while (__i != __last && __n != 1 && __unary_pred(__i))
293 template<
typename _RandomAccessIter,
typename _Integer,
294 typename _UnaryPredicate>
298 _Integer __count, _UnaryPredicate __unary_pred,
304 _DistanceType __tailSize = __last - __first;
305 _DistanceType __remainder = __count;
307 while (__remainder <= __tailSize)
309 __first += __remainder;
310 __tailSize -= __remainder;
313 _RandomAccessIter __backTrack = __first;
314 while (__unary_pred(--__backTrack))
316 if (--__remainder == 0)
317 return (__first - __count);
319 __remainder = __count + 1 - (__first - __backTrack);
324 template<
typename _ForwardIterator,
typename _Integer,
325 typename _UnaryPredicate>
328 __search_n(_ForwardIterator __first, _ForwardIterator __last,
330 _UnaryPredicate __unary_pred)
343 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
344 typename _BinaryPredicate>
347 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
348 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
349 forward_iterator_tag, forward_iterator_tag,
350 _BinaryPredicate __comp)
352 if (__first2 == __last2)
355 _ForwardIterator1 __result = __last1;
358 _ForwardIterator1 __new_result
359 = std::__search(__first1, __last1, __first2, __last2, __comp);
360 if (__new_result == __last1)
364 __result = __new_result;
365 __first1 = __new_result;
372 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
373 typename _BinaryPredicate>
375 _BidirectionalIterator1
376 __find_end(_BidirectionalIterator1 __first1,
377 _BidirectionalIterator1 __last1,
378 _BidirectionalIterator2 __first2,
379 _BidirectionalIterator2 __last2,
380 bidirectional_iterator_tag, bidirectional_iterator_tag,
381 _BinaryPredicate __comp)
384 __glibcxx_function_requires(_BidirectionalIteratorConcept<
385 _BidirectionalIterator1>)
386 __glibcxx_function_requires(_BidirectionalIteratorConcept<
387 _BidirectionalIterator2>)
389 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
390 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
392 _RevIterator1 __rlast1(__first1);
393 _RevIterator2 __rlast2(__first2);
394 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
395 _RevIterator2(__last2), __rlast2,
398 if (__rresult == __rlast1)
402 _BidirectionalIterator1 __result = __rresult.base();
434 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
436 inline _ForwardIterator1
437 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
438 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
441 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
442 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
443 __glibcxx_function_requires(_EqualOpConcept<
446 __glibcxx_requires_valid_range(__first1, __last1);
447 __glibcxx_requires_valid_range(__first2, __last2);
449 return std::__find_end(__first1, __last1, __first2, __last2,
452 __gnu_cxx::__ops::__iter_equal_to_iter());
483 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
484 typename _BinaryPredicate>
486 inline _ForwardIterator1
487 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
488 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
489 _BinaryPredicate __comp)
492 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
493 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
494 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
497 __glibcxx_requires_valid_range(__first1, __last1);
498 __glibcxx_requires_valid_range(__first2, __last2);
500 return std::__find_end(__first1, __last1, __first2, __last2,
503 __gnu_cxx::__ops::__iter_comp_iter(__comp));
506 #if __cplusplus >= 201103L
519 template<
typename _InputIterator,
typename _Predicate>
522 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
537 template<
typename _InputIterator,
typename _Predicate>
540 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
556 template<
typename _InputIterator,
typename _Predicate>
559 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
572 template<
typename _InputIterator,
typename _Predicate>
574 inline _InputIterator
575 find_if_not(_InputIterator __first, _InputIterator __last,
579 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
580 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
582 __glibcxx_requires_valid_range(__first, __last);
584 __gnu_cxx::__ops::__pred_iter(__pred));
597 template<
typename _InputIterator,
typename _Predicate>
600 is_partitioned(_InputIterator __first, _InputIterator __last,
604 if (__first == __last)
619 template<
typename _ForwardIterator,
typename _Predicate>
622 partition_point(_ForwardIterator __first, _ForwardIterator __last,
626 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
627 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
631 __glibcxx_requires_valid_range(__first, __last);
640 _DistanceType __half = __len >> 1;
641 _ForwardIterator __middle = __first;
643 if (__pred(*__middle))
647 __len = __len - __half - 1;
656 template<
typename _InputIterator,
typename _OutputIterator,
660 __remove_copy_if(_InputIterator __first, _InputIterator __last,
661 _OutputIterator __result, _Predicate __pred)
663 for (; __first != __last; ++__first)
664 if (!__pred(__first))
666 *__result = *__first;
686 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
688 inline _OutputIterator
689 remove_copy(_InputIterator __first, _InputIterator __last,
690 _OutputIterator __result,
const _Tp& __value)
693 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
694 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
696 __glibcxx_function_requires(_EqualOpConcept<
698 __glibcxx_requires_valid_range(__first, __last);
700 return std::__remove_copy_if(__first, __last, __result,
701 __gnu_cxx::__ops::__iter_equals_val(__value));
719 template<
typename _InputIterator,
typename _OutputIterator,
722 inline _OutputIterator
723 remove_copy_if(_InputIterator __first, _InputIterator __last,
724 _OutputIterator __result, _Predicate __pred)
727 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
728 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
730 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
732 __glibcxx_requires_valid_range(__first, __last);
734 return std::__remove_copy_if(__first, __last, __result,
735 __gnu_cxx::__ops::__pred_iter(__pred));
738 #if __cplusplus >= 201103L
754 template<
typename _InputIterator,
typename _OutputIterator,
758 copy_if(_InputIterator __first, _InputIterator __last,
759 _OutputIterator __result, _Predicate __pred)
762 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
763 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
765 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
767 __glibcxx_requires_valid_range(__first, __last);
769 for (; __first != __last; ++__first)
770 if (__pred(*__first))
772 *__result = *__first;
778 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
781 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result)
787 *__result = *__first;
798 template<
typename _CharT,
typename _Size>
799 __enable_if_t<__is_char<_CharT>::__value, _CharT*>
800 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT>>,
803 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
806 __copy_n(_InputIterator __first, _Size __n,
807 _OutputIterator __result, input_iterator_tag)
809 return std::__niter_wrap(__result,
810 __copy_n_a(__first, __n,
811 std::__niter_base(__result)));
814 template<
typename _RandomAccessIterator,
typename _Size,
815 typename _OutputIterator>
817 inline _OutputIterator
818 __copy_n(_RandomAccessIterator __first, _Size __n,
819 _OutputIterator __result, random_access_iterator_tag)
820 {
return std::copy(__first, __first + __n, __result); }
835 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
837 inline _OutputIterator
838 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
841 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
842 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
844 __glibcxx_requires_can_increment(__first, __n);
845 __glibcxx_requires_can_increment(__result, __n);
847 return std::__copy_n(__first, __n, __result,
866 template<
typename _InputIterator,
typename _OutputIterator1,
867 typename _OutputIterator2,
typename _Predicate>
869 pair<_OutputIterator1, _OutputIterator2>
870 partition_copy(_InputIterator __first, _InputIterator __last,
871 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
875 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
876 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
878 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
880 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
882 __glibcxx_requires_valid_range(__first, __last);
884 for (; __first != __last; ++__first)
885 if (__pred(*__first))
887 *__out_true = *__first;
892 *__out_false = *__first;
900 template<
typename _ForwardIterator,
typename _Predicate>
903 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
907 if (__first == __last)
909 _ForwardIterator __result = __first;
911 for (; __first != __last; ++__first)
912 if (!__pred(__first))
914 *__result = _GLIBCXX_MOVE(*__first);
937 template<
typename _ForwardIterator,
typename _Tp>
939 inline _ForwardIterator
940 remove(_ForwardIterator __first, _ForwardIterator __last,
944 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
946 __glibcxx_function_requires(_EqualOpConcept<
948 __glibcxx_requires_valid_range(__first, __last);
950 return std::__remove_if(__first, __last,
951 __gnu_cxx::__ops::__iter_equals_val(__value));
971 template<
typename _ForwardIterator,
typename _Predicate>
973 inline _ForwardIterator
974 remove_if(_ForwardIterator __first, _ForwardIterator __last,
978 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
980 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
982 __glibcxx_requires_valid_range(__first, __last);
984 return std::__remove_if(__first, __last,
985 __gnu_cxx::__ops::__pred_iter(__pred));
988 template<
typename _ForwardIterator,
typename _BinaryPredicate>
991 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
992 _BinaryPredicate __binary_pred)
994 if (__first == __last)
996 _ForwardIterator __next = __first;
997 while (++__next != __last)
999 if (__binary_pred(__first, __next))
1006 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1007 _GLIBCXX20_CONSTEXPR
1009 __unique(_ForwardIterator __first, _ForwardIterator __last,
1010 _BinaryPredicate __binary_pred)
1013 __first = std::__adjacent_find(__first, __last, __binary_pred);
1014 if (__first == __last)
1018 _ForwardIterator __dest = __first;
1020 while (++__first != __last)
1021 if (!__binary_pred(__dest, __first))
1022 *++__dest = _GLIBCXX_MOVE(*__first);
1040 template<
typename _ForwardIterator>
1041 _GLIBCXX20_CONSTEXPR
1042 inline _ForwardIterator
1043 unique(_ForwardIterator __first, _ForwardIterator __last)
1046 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1048 __glibcxx_function_requires(_EqualityComparableConcept<
1050 __glibcxx_requires_valid_range(__first, __last);
1052 return std::__unique(__first, __last,
1053 __gnu_cxx::__ops::__iter_equal_to_iter());
1071 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1072 _GLIBCXX20_CONSTEXPR
1073 inline _ForwardIterator
1074 unique(_ForwardIterator __first, _ForwardIterator __last,
1075 _BinaryPredicate __binary_pred)
1078 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1080 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1083 __glibcxx_requires_valid_range(__first, __last);
1085 return std::__unique(__first, __last,
1086 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1095 template<
typename _ForwardIterator,
typename _OutputIterator,
1096 typename _BinaryPredicate>
1097 _GLIBCXX20_CONSTEXPR
1100 _OutputIterator __result, _BinaryPredicate __binary_pred,
1104 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1108 _ForwardIterator __next = __first;
1109 *__result = *__first;
1110 while (++__next != __last)
1111 if (!__binary_pred(__first, __next))
1114 *++__result = *__first;
1125 template<
typename _InputIterator,
typename _OutputIterator,
1126 typename _BinaryPredicate>
1127 _GLIBCXX20_CONSTEXPR
1130 _OutputIterator __result, _BinaryPredicate __binary_pred,
1134 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1139 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1141 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1142 *__result = __value;
1143 while (++__first != __last)
1144 if (!__rebound_pred(__first, __value))
1147 *++__result = __value;
1158 template<
typename _InputIterator,
typename _ForwardIterator,
1159 typename _BinaryPredicate>
1160 _GLIBCXX20_CONSTEXPR
1163 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1167 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1170 *__result = *__first;
1171 while (++__first != __last)
1172 if (!__binary_pred(__result, __first))
1173 *++__result = *__first;
1182 template<
typename _B
idirectionalIterator>
1183 _GLIBCXX20_CONSTEXPR
1185 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1189 if (__first == __last || __first == --__last)
1203 template<
typename _RandomAccessIterator>
1204 _GLIBCXX20_CONSTEXPR
1206 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1209 if (__first == __last)
1212 while (__first < __last)
1232 template<
typename _B
idirectionalIterator>
1233 _GLIBCXX20_CONSTEXPR
1235 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1238 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1239 _BidirectionalIterator>)
1240 __glibcxx_requires_valid_range(__first, __last);
1260 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1261 _GLIBCXX20_CONSTEXPR
1263 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1264 _OutputIterator __result)
1267 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1268 _BidirectionalIterator>)
1269 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1271 __glibcxx_requires_valid_range(__first, __last);
1273 while (__first != __last)
1276 *__result = *__last;
1286 template<
typename _Eucl
ideanRingElement>
1287 _GLIBCXX20_CONSTEXPR
1288 _EuclideanRingElement
1289 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1293 _EuclideanRingElement __t = __m % __n;
1300 inline namespace _V2
1304 template<
typename _ForwardIterator>
1305 _GLIBCXX20_CONSTEXPR
1308 _ForwardIterator __middle,
1309 _ForwardIterator __last,
1312 if (__first == __middle)
1314 else if (__last == __middle)
1317 _ForwardIterator __first2 = __middle;
1323 if (__first == __middle)
1324 __middle = __first2;
1326 while (__first2 != __last);
1328 _ForwardIterator __ret = __first;
1330 __first2 = __middle;
1332 while (__first2 != __last)
1337 if (__first == __middle)
1338 __middle = __first2;
1339 else if (__first2 == __last)
1340 __first2 = __middle;
1346 template<
typename _B
idirectionalIterator>
1347 _GLIBCXX20_CONSTEXPR
1348 _BidirectionalIterator
1350 _BidirectionalIterator __middle,
1351 _BidirectionalIterator __last,
1355 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1356 _BidirectionalIterator>)
1358 if (__first == __middle)
1360 else if (__last == __middle)
1366 while (__first != __middle && __middle != __last)
1372 if (__first == __middle)
1385 template<
typename _RandomAccessIterator>
1386 _GLIBCXX20_CONSTEXPR
1387 _RandomAccessIterator
1389 _RandomAccessIterator __middle,
1390 _RandomAccessIterator __last,
1394 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1395 _RandomAccessIterator>)
1397 if (__first == __middle)
1399 else if (__last == __middle)
1407 _Distance __n = __last - __first;
1408 _Distance __k = __middle - __first;
1410 if (__k == __n - __k)
1416 _RandomAccessIterator __p = __first;
1417 _RandomAccessIterator __ret = __first + (__last - __middle);
1421 if (__k < __n - __k)
1423 if (__is_pod(_ValueType) && __k == 1)
1425 _ValueType __t = _GLIBCXX_MOVE(*__p);
1426 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1427 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1430 _RandomAccessIterator __q = __p + __k;
1431 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1440 std::swap(__n, __k);
1446 if (__is_pod(_ValueType) && __k == 1)
1448 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1449 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1450 *__p = _GLIBCXX_MOVE(__t);
1453 _RandomAccessIterator __q = __p + __n;
1455 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1464 std::swap(__n, __k);
1492 template<
typename _ForwardIterator>
1493 _GLIBCXX20_CONSTEXPR
1494 inline _ForwardIterator
1495 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1496 _ForwardIterator __last)
1499 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1501 __glibcxx_requires_valid_range(__first, __middle);
1502 __glibcxx_requires_valid_range(__middle, __last);
1530 template<
typename _ForwardIterator,
typename _OutputIterator>
1531 _GLIBCXX20_CONSTEXPR
1532 inline _OutputIterator
1533 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1534 _ForwardIterator __last, _OutputIterator __result)
1537 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1538 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1540 __glibcxx_requires_valid_range(__first, __middle);
1541 __glibcxx_requires_valid_range(__middle, __last);
1543 return std::copy(__first, __middle,
1544 std::copy(__middle, __last, __result));
1548 template<
typename _ForwardIterator,
typename _Predicate>
1549 _GLIBCXX20_CONSTEXPR
1554 if (__first == __last)
1557 while (__pred(*__first))
1558 if (++__first == __last)
1561 _ForwardIterator __next = __first;
1563 while (++__next != __last)
1564 if (__pred(*__next))
1574 template<
typename _B
idirectionalIterator,
typename _Predicate>
1575 _GLIBCXX20_CONSTEXPR
1576 _BidirectionalIterator
1577 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1583 if (__first == __last)
1585 else if (__pred(*__first))
1591 if (__first == __last)
1593 else if (!
bool(__pred(*__last)))
1610 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1614 _ForwardIterator __last,
1615 _Predicate __pred, _Distance __len,
1617 _Distance __buffer_size)
1622 if (__len <= __buffer_size)
1624 _ForwardIterator __result1 = __first;
1625 _Pointer __result2 = __buffer;
1630 *__result2 = _GLIBCXX_MOVE(*__first);
1633 for (; __first != __last; ++__first)
1634 if (__pred(__first))
1636 *__result1 = _GLIBCXX_MOVE(*__first);
1641 *__result2 = _GLIBCXX_MOVE(*__first);
1645 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1649 _ForwardIterator __middle = __first;
1651 _ForwardIterator __left_split =
1653 __len / 2, __buffer,
1658 _Distance __right_len = __len - __len / 2;
1659 _ForwardIterator __right_split =
1666 __buffer, __buffer_size);
1668 return std::rotate(__left_split, __middle, __right_split);
1671 template<
typename _ForwardIterator,
typename _Predicate>
1673 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1678 if (__first == __last)
1681 typedef typename iterator_traits<_ForwardIterator>::value_type
1683 typedef typename iterator_traits<_ForwardIterator>::difference_type
1686 _Temporary_buffer<_ForwardIterator, _ValueType>
1690 _DistanceType(__buf.requested_size()),
1692 _DistanceType(__buf.size()));
1712 template<
typename _ForwardIterator,
typename _Predicate>
1713 inline _ForwardIterator
1714 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1718 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1720 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1722 __glibcxx_requires_valid_range(__first, __last);
1724 return std::__stable_partition(__first, __last,
1725 __gnu_cxx::__ops::__pred_iter(__pred));
1729 template<
typename _RandomAccessIterator,
typename _Compare>
1730 _GLIBCXX20_CONSTEXPR
1733 _RandomAccessIterator __middle,
1734 _RandomAccessIterator __last, _Compare __comp)
1736 std::__make_heap(__first, __middle, __comp);
1737 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1738 if (__comp(__i, __first))
1739 std::__pop_heap(__first, __middle, __i, __comp);
1744 template<
typename _InputIterator,
typename _RandomAccessIterator,
1746 _GLIBCXX20_CONSTEXPR
1747 _RandomAccessIterator
1748 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1749 _RandomAccessIterator __result_first,
1750 _RandomAccessIterator __result_last,
1753 typedef typename iterator_traits<_InputIterator>::value_type
1755 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1756 typedef typename _RItTraits::difference_type _DistanceType;
1758 if (__result_first == __result_last)
1759 return __result_last;
1760 _RandomAccessIterator __result_real_last = __result_first;
1761 while (__first != __last && __result_real_last != __result_last)
1763 *__result_real_last = *__first;
1764 ++__result_real_last;
1768 std::__make_heap(__result_first, __result_real_last, __comp);
1769 while (__first != __last)
1771 if (__comp(__first, __result_first))
1772 std::__adjust_heap(__result_first, _DistanceType(0),
1773 _DistanceType(__result_real_last
1775 _InputValueType(*__first), __comp);
1778 std::__sort_heap(__result_first, __result_real_last, __comp);
1779 return __result_real_last;
1800 template<
typename _InputIterator,
typename _RandomAccessIterator>
1801 _GLIBCXX20_CONSTEXPR
1802 inline _RandomAccessIterator
1803 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1804 _RandomAccessIterator __result_first,
1805 _RandomAccessIterator __result_last)
1807 #ifdef _GLIBCXX_CONCEPT_CHECKS
1815 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1816 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1818 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1820 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1821 __glibcxx_requires_valid_range(__first, __last);
1822 __glibcxx_requires_irreflexive(__first, __last);
1823 __glibcxx_requires_valid_range(__result_first, __result_last);
1825 return std::__partial_sort_copy(__first, __last,
1826 __result_first, __result_last,
1827 __gnu_cxx::__ops::__iter_less_iter());
1850 template<
typename _InputIterator,
typename _RandomAccessIterator,
1852 _GLIBCXX20_CONSTEXPR
1853 inline _RandomAccessIterator
1854 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1855 _RandomAccessIterator __result_first,
1856 _RandomAccessIterator __result_last,
1859 #ifdef _GLIBCXX_CONCEPT_CHECKS
1867 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1868 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1869 _RandomAccessIterator>)
1870 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1872 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1873 _InputValueType, _OutputValueType>)
1874 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1875 _OutputValueType, _OutputValueType>)
1876 __glibcxx_requires_valid_range(__first, __last);
1877 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1878 __glibcxx_requires_valid_range(__result_first, __result_last);
1880 return std::__partial_sort_copy(__first, __last,
1881 __result_first, __result_last,
1882 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1886 template<
typename _RandomAccessIterator,
typename _Compare>
1887 _GLIBCXX20_CONSTEXPR
1893 __val = _GLIBCXX_MOVE(*__last);
1894 _RandomAccessIterator __next = __last;
1896 while (__comp(__val, __next))
1898 *__last = _GLIBCXX_MOVE(*__next);
1902 *__last = _GLIBCXX_MOVE(__val);
1906 template<
typename _RandomAccessIterator,
typename _Compare>
1907 _GLIBCXX20_CONSTEXPR
1910 _RandomAccessIterator __last, _Compare __comp)
1912 if (__first == __last)
return;
1914 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1916 if (__comp(__i, __first))
1919 __val = _GLIBCXX_MOVE(*__i);
1920 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1921 *__first = _GLIBCXX_MOVE(__val);
1925 __gnu_cxx::__ops::__val_comp_iter(__comp));
1930 template<
typename _RandomAccessIterator,
typename _Compare>
1931 _GLIBCXX20_CONSTEXPR
1934 _RandomAccessIterator __last, _Compare __comp)
1936 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1938 __gnu_cxx::__ops::__val_comp_iter(__comp));
1945 enum { _S_threshold = 16 };
1948 template<
typename _RandomAccessIterator,
typename _Compare>
1949 _GLIBCXX20_CONSTEXPR
1952 _RandomAccessIterator __last, _Compare __comp)
1954 if (__last - __first >
int(_S_threshold))
1965 template<
typename _RandomAccessIterator,
typename _Compare>
1966 _GLIBCXX20_CONSTEXPR
1967 _RandomAccessIterator
1969 _RandomAccessIterator __last,
1970 _RandomAccessIterator __pivot, _Compare __comp)
1974 while (__comp(__first, __pivot))
1977 while (__comp(__pivot, __last))
1979 if (!(__first < __last))
1987 template<
typename _RandomAccessIterator,
typename _Compare>
1988 _GLIBCXX20_CONSTEXPR
1989 inline _RandomAccessIterator
1991 _RandomAccessIterator __last, _Compare __comp)
1993 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1999 template<
typename _RandomAccessIterator,
typename _Compare>
2000 _GLIBCXX20_CONSTEXPR
2002 __partial_sort(_RandomAccessIterator __first,
2003 _RandomAccessIterator __middle,
2004 _RandomAccessIterator __last,
2008 std::__sort_heap(__first, __middle, __comp);
2012 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2013 _GLIBCXX20_CONSTEXPR
2016 _RandomAccessIterator __last,
2017 _Size __depth_limit, _Compare __comp)
2019 while (__last - __first >
int(_S_threshold))
2021 if (__depth_limit == 0)
2023 std::__partial_sort(__first, __last, __last, __comp);
2027 _RandomAccessIterator __cut =
2036 template<
typename _RandomAccessIterator,
typename _Compare>
2037 _GLIBCXX20_CONSTEXPR
2039 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2042 if (__first != __last)
2051 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2052 _GLIBCXX20_CONSTEXPR
2054 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2055 _RandomAccessIterator __last, _Size __depth_limit,
2058 while (__last - __first > 3)
2060 if (__depth_limit == 0)
2068 _RandomAccessIterator __cut =
2098 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2099 _GLIBCXX20_CONSTEXPR
2100 inline _ForwardIterator
2101 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2102 const _Tp& __val, _Compare __comp)
2105 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2106 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2108 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2111 return std::__lower_bound(__first, __last, __val,
2112 __gnu_cxx::__ops::__iter_comp_val(__comp));
2115 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2116 _GLIBCXX20_CONSTEXPR
2118 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2119 const _Tp& __val, _Compare __comp)
2121 typedef typename iterator_traits<_ForwardIterator>::difference_type
2128 _DistanceType __half = __len >> 1;
2129 _ForwardIterator __middle = __first;
2131 if (__comp(__val, __middle))
2137 __len = __len - __half - 1;
2154 template<
typename _ForwardIterator,
typename _Tp>
2155 _GLIBCXX20_CONSTEXPR
2156 inline _ForwardIterator
2157 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2161 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2162 __glibcxx_function_requires(_LessThanOpConcept<
2164 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2166 return std::__upper_bound(__first, __last, __val,
2167 __gnu_cxx::__ops::__val_less_iter());
2185 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2186 _GLIBCXX20_CONSTEXPR
2187 inline _ForwardIterator
2188 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2189 const _Tp& __val, _Compare __comp)
2192 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2193 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2195 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2198 return std::__upper_bound(__first, __last, __val,
2199 __gnu_cxx::__ops::__val_comp_iter(__comp));
2202 template<
typename _ForwardIterator,
typename _Tp,
2203 typename _CompareItTp,
typename _CompareTpIt>
2204 _GLIBCXX20_CONSTEXPR
2205 pair<_ForwardIterator, _ForwardIterator>
2206 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2208 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2210 typedef typename iterator_traits<_ForwardIterator>::difference_type
2217 _DistanceType __half = __len >> 1;
2218 _ForwardIterator __middle = __first;
2220 if (__comp_it_val(__middle, __val))
2224 __len = __len - __half - 1;
2226 else if (__comp_val_it(__val, __middle))
2230 _ForwardIterator __left
2231 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2233 _ForwardIterator __right
2234 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2235 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2238 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2258 template<
typename _ForwardIterator,
typename _Tp>
2259 _GLIBCXX20_CONSTEXPR
2260 inline pair<_ForwardIterator, _ForwardIterator>
2261 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2265 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2266 __glibcxx_function_requires(_LessThanOpConcept<
2268 __glibcxx_function_requires(_LessThanOpConcept<
2270 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2271 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2273 return std::__equal_range(__first, __last, __val,
2274 __gnu_cxx::__ops::__iter_less_val(),
2275 __gnu_cxx::__ops::__val_less_iter());
2295 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2296 _GLIBCXX20_CONSTEXPR
2297 inline pair<_ForwardIterator, _ForwardIterator>
2298 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2299 const _Tp& __val, _Compare __comp)
2302 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2303 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2305 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2307 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2309 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2312 return std::__equal_range(__first, __last, __val,
2313 __gnu_cxx::__ops::__iter_comp_val(__comp),
2314 __gnu_cxx::__ops::__val_comp_iter(__comp));
2329 template<
typename _ForwardIterator,
typename _Tp>
2330 _GLIBCXX20_CONSTEXPR
2332 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2336 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2337 __glibcxx_function_requires(_LessThanOpConcept<
2339 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2340 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2342 _ForwardIterator __i
2343 = std::__lower_bound(__first, __last, __val,
2344 __gnu_cxx::__ops::__iter_less_val());
2345 return __i != __last && !(__val < *__i);
2363 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2364 _GLIBCXX20_CONSTEXPR
2366 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2367 const _Tp& __val, _Compare __comp)
2370 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2371 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2373 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2375 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2378 _ForwardIterator __i
2379 = std::__lower_bound(__first, __last, __val,
2380 __gnu_cxx::__ops::__iter_comp_val(__comp));
2381 return __i != __last && !bool(__comp(__val, *__i));
2387 template<
typename _InputIterator1,
typename _InputIterator2,
2388 typename _OutputIterator,
typename _Compare>
2391 _InputIterator2 __first2, _InputIterator2 __last2,
2392 _OutputIterator __result, _Compare __comp)
2394 while (__first1 != __last1 && __first2 != __last2)
2396 if (__comp(__first2, __first1))
2398 *__result = _GLIBCXX_MOVE(*__first2);
2403 *__result = _GLIBCXX_MOVE(*__first1);
2408 if (__first1 != __last1)
2409 _GLIBCXX_MOVE3(__first1, __last1, __result);
2413 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2414 typename _BidirectionalIterator3,
typename _Compare>
2417 _BidirectionalIterator1 __last1,
2418 _BidirectionalIterator2 __first2,
2419 _BidirectionalIterator2 __last2,
2420 _BidirectionalIterator3 __result,
2423 if (__first1 == __last1)
2425 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2428 else if (__first2 == __last2)
2435 if (__comp(__last2, __last1))
2437 *--__result = _GLIBCXX_MOVE(*__last1);
2438 if (__first1 == __last1)
2440 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2447 *--__result = _GLIBCXX_MOVE(*__last2);
2448 if (__first2 == __last2)
2456 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2458 _BidirectionalIterator1
2460 _BidirectionalIterator1 __middle,
2461 _BidirectionalIterator1 __last,
2462 _Distance __len1, _Distance __len2,
2463 _BidirectionalIterator2 __buffer,
2464 _Distance __buffer_size)
2466 _BidirectionalIterator2 __buffer_end;
2467 if (__len1 > __len2 && __len2 <= __buffer_size)
2471 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2472 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2473 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2478 else if (__len1 <= __buffer_size)
2482 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2483 _GLIBCXX_MOVE3(__middle, __last, __first);
2484 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2490 return std::rotate(__first, __middle, __last);
2494 template<
typename _BidirectionalIterator,
typename _Distance,
2495 typename _Pointer,
typename _Compare>
2498 _BidirectionalIterator __middle,
2499 _BidirectionalIterator __last,
2500 _Distance __len1, _Distance __len2,
2501 _Pointer __buffer, _Distance __buffer_size,
2504 if (__len1 <= __len2 && __len1 <= __buffer_size)
2506 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2510 else if (__len2 <= __buffer_size)
2512 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2514 __buffer_end, __last, __comp);
2518 _BidirectionalIterator __first_cut = __first;
2519 _BidirectionalIterator __second_cut = __middle;
2520 _Distance __len11 = 0;
2521 _Distance __len22 = 0;
2522 if (__len1 > __len2)
2524 __len11 = __len1 / 2;
2527 = std::__lower_bound(__middle, __last, *__first_cut,
2528 __gnu_cxx::__ops::__iter_comp_val(__comp));
2533 __len22 = __len2 / 2;
2536 = std::__upper_bound(__first, __middle, *__second_cut,
2537 __gnu_cxx::__ops::__val_comp_iter(__comp));
2541 _BidirectionalIterator __new_middle
2543 __len1 - __len11, __len22, __buffer,
2546 __len22, __buffer, __buffer_size, __comp);
2549 __len2 - __len22, __buffer,
2550 __buffer_size, __comp);
2555 template<
typename _BidirectionalIterator,
typename _Distance,
2559 _BidirectionalIterator __middle,
2560 _BidirectionalIterator __last,
2561 _Distance __len1, _Distance __len2,
2564 if (__len1 == 0 || __len2 == 0)
2567 if (__len1 + __len2 == 2)
2569 if (__comp(__middle, __first))
2574 _BidirectionalIterator __first_cut = __first;
2575 _BidirectionalIterator __second_cut = __middle;
2576 _Distance __len11 = 0;
2577 _Distance __len22 = 0;
2578 if (__len1 > __len2)
2580 __len11 = __len1 / 2;
2583 = std::__lower_bound(__middle, __last, *__first_cut,
2584 __gnu_cxx::__ops::__iter_comp_val(__comp));
2589 __len22 = __len2 / 2;
2592 = std::__upper_bound(__first, __middle, *__second_cut,
2593 __gnu_cxx::__ops::__val_comp_iter(__comp));
2597 _BidirectionalIterator __new_middle
2598 = std::rotate(__first_cut, __middle, __second_cut);
2600 __len11, __len22, __comp);
2602 __len1 - __len11, __len2 - __len22, __comp);
2605 template<
typename _B
idirectionalIterator,
typename _Compare>
2607 __inplace_merge(_BidirectionalIterator __first,
2608 _BidirectionalIterator __middle,
2609 _BidirectionalIterator __last,
2612 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2614 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2617 if (__first == __middle || __middle == __last)
2620 const _DistanceType __len1 =
std::distance(__first, __middle);
2621 const _DistanceType __len2 =
std::distance(__middle, __last);
2623 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2624 _TmpBuf __buf(__first, __len1 + __len2);
2626 if (__buf.begin() == 0)
2628 (__first, __middle, __last, __len1, __len2, __comp);
2631 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2632 _DistanceType(__buf.size()), __comp);
2653 template<
typename _B
idirectionalIterator>
2655 inplace_merge(_BidirectionalIterator __first,
2656 _BidirectionalIterator __middle,
2657 _BidirectionalIterator __last)
2660 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2661 _BidirectionalIterator>)
2662 __glibcxx_function_requires(_LessThanComparableConcept<
2664 __glibcxx_requires_sorted(__first, __middle);
2665 __glibcxx_requires_sorted(__middle, __last);
2666 __glibcxx_requires_irreflexive(__first, __last);
2668 std::__inplace_merge(__first, __middle, __last,
2669 __gnu_cxx::__ops::__iter_less_iter());
2694 template<
typename _B
idirectionalIterator,
typename _Compare>
2696 inplace_merge(_BidirectionalIterator __first,
2697 _BidirectionalIterator __middle,
2698 _BidirectionalIterator __last,
2702 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2703 _BidirectionalIterator>)
2704 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2707 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2708 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2709 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2711 std::__inplace_merge(__first, __middle, __last,
2712 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2717 template<
typename _InputIterator,
typename _OutputIterator,
2721 _InputIterator __first2, _InputIterator __last2,
2722 _OutputIterator __result, _Compare __comp)
2724 while (__first1 != __last1 && __first2 != __last2)
2726 if (__comp(__first2, __first1))
2728 *__result = _GLIBCXX_MOVE(*__first2);
2733 *__result = _GLIBCXX_MOVE(*__first1);
2738 return _GLIBCXX_MOVE3(__first2, __last2,
2739 _GLIBCXX_MOVE3(__first1, __last1,
2743 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2744 typename _Distance,
typename _Compare>
2746 __merge_sort_loop(_RandomAccessIterator1 __first,
2747 _RandomAccessIterator1 __last,
2748 _RandomAccessIterator2 __result, _Distance __step_size,
2751 const _Distance __two_step = 2 * __step_size;
2753 while (__last - __first >= __two_step)
2756 __first + __step_size,
2757 __first + __two_step,
2759 __first += __two_step;
2761 __step_size =
std::min(_Distance(__last - __first), __step_size);
2764 __first + __step_size, __last, __result, __comp);
2767 template<
typename _RandomAccessIterator,
typename _Distance,
2769 _GLIBCXX20_CONSTEXPR
2771 __chunk_insertion_sort(_RandomAccessIterator __first,
2772 _RandomAccessIterator __last,
2773 _Distance __chunk_size, _Compare __comp)
2775 while (__last - __first >= __chunk_size)
2778 __first += __chunk_size;
2783 enum { _S_chunk_size = 7 };
2785 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2787 __merge_sort_with_buffer(_RandomAccessIterator __first,
2788 _RandomAccessIterator __last,
2789 _Pointer __buffer, _Compare __comp)
2791 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2794 const _Distance __len = __last - __first;
2795 const _Pointer __buffer_last = __buffer + __len;
2797 _Distance __step_size = _S_chunk_size;
2798 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2800 while (__step_size < __len)
2802 std::__merge_sort_loop(__first, __last, __buffer,
2803 __step_size, __comp);
2805 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2806 __step_size, __comp);
2811 template<
typename _RandomAccessIterator,
typename _Pointer,
2812 typename _Distance,
typename _Compare>
2814 __stable_sort_adaptive(_RandomAccessIterator __first,
2815 _RandomAccessIterator __last,
2816 _Pointer __buffer, _Distance __buffer_size,
2819 const _Distance __len = (__last - __first + 1) / 2;
2820 const _RandomAccessIterator __middle = __first + __len;
2821 if (__len > __buffer_size)
2823 std::__stable_sort_adaptive(__first, __middle, __buffer,
2824 __buffer_size, __comp);
2825 std::__stable_sort_adaptive(__middle, __last, __buffer,
2826 __buffer_size, __comp);
2830 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2831 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2834 _Distance(__middle - __first),
2835 _Distance(__last - __middle),
2836 __buffer, __buffer_size,
2841 template<
typename _RandomAccessIterator,
typename _Compare>
2844 _RandomAccessIterator __last, _Compare __comp)
2846 if (__last - __first < 15)
2851 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2867 template<
typename _InputIterator1,
typename _InputIterator2,
2869 _GLIBCXX20_CONSTEXPR
2871 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2872 _InputIterator2 __first2, _InputIterator2 __last2,
2875 while (__first1 != __last1 && __first2 != __last2)
2876 if (__comp(__first2, __first1))
2878 else if (__comp(__first1, __first2))
2886 return __first2 == __last2;
2907 template<
typename _InputIterator1,
typename _InputIterator2>
2908 _GLIBCXX20_CONSTEXPR
2910 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2911 _InputIterator2 __first2, _InputIterator2 __last2)
2914 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2915 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2916 __glibcxx_function_requires(_LessThanOpConcept<
2919 __glibcxx_function_requires(_LessThanOpConcept<
2922 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2923 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2924 __glibcxx_requires_irreflexive2(__first1, __last1);
2925 __glibcxx_requires_irreflexive2(__first2, __last2);
2927 return std::__includes(__first1, __last1, __first2, __last2,
2928 __gnu_cxx::__ops::__iter_less_iter());
2952 template<
typename _InputIterator1,
typename _InputIterator2,
2954 _GLIBCXX20_CONSTEXPR
2956 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2957 _InputIterator2 __first2, _InputIterator2 __last2,
2961 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2962 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2963 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2966 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2969 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2970 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2971 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2972 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2974 return std::__includes(__first1, __last1, __first2, __last2,
2975 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2988 template<
typename _B
idirectionalIterator,
typename _Compare>
2989 _GLIBCXX20_CONSTEXPR
2991 __next_permutation(_BidirectionalIterator __first,
2992 _BidirectionalIterator __last, _Compare __comp)
2994 if (__first == __last)
2996 _BidirectionalIterator __i = __first;
3005 _BidirectionalIterator __ii = __i;
3007 if (__comp(__i, __ii))
3009 _BidirectionalIterator __j = __last;
3010 while (!__comp(__i, --__j))
3038 template<
typename _B
idirectionalIterator>
3039 _GLIBCXX20_CONSTEXPR
3041 next_permutation(_BidirectionalIterator __first,
3042 _BidirectionalIterator __last)
3045 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3046 _BidirectionalIterator>)
3047 __glibcxx_function_requires(_LessThanComparableConcept<
3049 __glibcxx_requires_valid_range(__first, __last);
3050 __glibcxx_requires_irreflexive(__first, __last);
3052 return std::__next_permutation
3053 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
3071 template<
typename _B
idirectionalIterator,
typename _Compare>
3072 _GLIBCXX20_CONSTEXPR
3074 next_permutation(_BidirectionalIterator __first,
3075 _BidirectionalIterator __last, _Compare __comp)
3078 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3079 _BidirectionalIterator>)
3080 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3083 __glibcxx_requires_valid_range(__first, __last);
3084 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3086 return std::__next_permutation
3087 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3090 template<
typename _B
idirectionalIterator,
typename _Compare>
3091 _GLIBCXX20_CONSTEXPR
3093 __prev_permutation(_BidirectionalIterator __first,
3094 _BidirectionalIterator __last, _Compare __comp)
3096 if (__first == __last)
3098 _BidirectionalIterator __i = __first;
3107 _BidirectionalIterator __ii = __i;
3109 if (__comp(__ii, __i))
3111 _BidirectionalIterator __j = __last;
3112 while (!__comp(--__j, __i))
3141 template<
typename _B
idirectionalIterator>
3142 _GLIBCXX20_CONSTEXPR
3144 prev_permutation(_BidirectionalIterator __first,
3145 _BidirectionalIterator __last)
3148 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3149 _BidirectionalIterator>)
3150 __glibcxx_function_requires(_LessThanComparableConcept<
3152 __glibcxx_requires_valid_range(__first, __last);
3153 __glibcxx_requires_irreflexive(__first, __last);
3155 return std::__prev_permutation(__first, __last,
3156 __gnu_cxx::__ops::__iter_less_iter());
3174 template<
typename _B
idirectionalIterator,
typename _Compare>
3175 _GLIBCXX20_CONSTEXPR
3177 prev_permutation(_BidirectionalIterator __first,
3178 _BidirectionalIterator __last, _Compare __comp)
3181 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3182 _BidirectionalIterator>)
3183 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3186 __glibcxx_requires_valid_range(__first, __last);
3187 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3189 return std::__prev_permutation(__first, __last,
3190 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3196 template<
typename _InputIterator,
typename _OutputIterator,
3197 typename _Predicate,
typename _Tp>
3198 _GLIBCXX20_CONSTEXPR
3200 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3201 _OutputIterator __result,
3202 _Predicate __pred,
const _Tp& __new_value)
3204 for (; __first != __last; ++__first, (void)++__result)
3205 if (__pred(__first))
3206 *__result = __new_value;
3208 *__result = *__first;
3226 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3227 _GLIBCXX20_CONSTEXPR
3228 inline _OutputIterator
3229 replace_copy(_InputIterator __first, _InputIterator __last,
3230 _OutputIterator __result,
3231 const _Tp& __old_value,
const _Tp& __new_value)
3234 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3235 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3237 __glibcxx_function_requires(_EqualOpConcept<
3239 __glibcxx_requires_valid_range(__first, __last);
3241 return std::__replace_copy_if(__first, __last, __result,
3242 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3261 template<
typename _InputIterator,
typename _OutputIterator,
3262 typename _Predicate,
typename _Tp>
3263 _GLIBCXX20_CONSTEXPR
3264 inline _OutputIterator
3265 replace_copy_if(_InputIterator __first, _InputIterator __last,
3266 _OutputIterator __result,
3267 _Predicate __pred,
const _Tp& __new_value)
3270 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3271 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3273 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3275 __glibcxx_requires_valid_range(__first, __last);
3277 return std::__replace_copy_if(__first, __last, __result,
3278 __gnu_cxx::__ops::__pred_iter(__pred),
3282 template<
typename _InputIterator,
typename _Predicate>
3283 _GLIBCXX20_CONSTEXPR
3284 typename iterator_traits<_InputIterator>::difference_type
3285 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3287 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3288 for (; __first != __last; ++__first)
3289 if (__pred(__first))
3294 #if __cplusplus >= 201103L
3302 template<
typename _ForwardIterator>
3303 _GLIBCXX20_CONSTEXPR
3305 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3317 template<
typename _ForwardIterator,
typename _Compare>
3318 _GLIBCXX20_CONSTEXPR
3320 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3324 template<
typename _ForwardIterator,
typename _Compare>
3325 _GLIBCXX20_CONSTEXPR
3327 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3330 if (__first == __last)
3333 _ForwardIterator __next = __first;
3334 for (++__next; __next != __last; __first = __next, (void)++__next)
3335 if (__comp(__next, __first))
3348 template<
typename _ForwardIterator>
3349 _GLIBCXX20_CONSTEXPR
3350 inline _ForwardIterator
3351 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3354 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3355 __glibcxx_function_requires(_LessThanComparableConcept<
3357 __glibcxx_requires_valid_range(__first, __last);
3358 __glibcxx_requires_irreflexive(__first, __last);
3360 return std::__is_sorted_until(__first, __last,
3361 __gnu_cxx::__ops::__iter_less_iter());
3373 template<
typename _ForwardIterator,
typename _Compare>
3374 _GLIBCXX20_CONSTEXPR
3375 inline _ForwardIterator
3376 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3380 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3381 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3384 __glibcxx_requires_valid_range(__first, __last);
3385 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3387 return std::__is_sorted_until(__first, __last,
3388 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3399 template<
typename _Tp>
3400 _GLIBCXX14_CONSTEXPR
3401 inline pair<const _Tp&, const _Tp&>
3405 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3407 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3420 template<
typename _Tp,
typename _Compare>
3421 _GLIBCXX14_CONSTEXPR
3422 inline pair<const _Tp&, const _Tp&>
3423 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3429 template<
typename _ForwardIterator,
typename _Compare>
3430 _GLIBCXX14_CONSTEXPR
3431 pair<_ForwardIterator, _ForwardIterator>
3432 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3435 _ForwardIterator __next = __first;
3436 if (__first == __last
3437 || ++__next == __last)
3438 return std::make_pair(__first, __first);
3440 _ForwardIterator __min{}, __max{};
3441 if (__comp(__next, __first))
3455 while (__first != __last)
3458 if (++__next == __last)
3460 if (__comp(__first, __min))
3462 else if (!__comp(__first, __max))
3467 if (__comp(__next, __first))
3469 if (__comp(__next, __min))
3471 if (!__comp(__first, __max))
3476 if (__comp(__first, __min))
3478 if (!__comp(__next, __max))
3486 return std::make_pair(__min, __max);
3500 template<
typename _ForwardIterator>
3501 _GLIBCXX14_CONSTEXPR
3502 inline pair<_ForwardIterator, _ForwardIterator>
3503 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3506 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3507 __glibcxx_function_requires(_LessThanComparableConcept<
3509 __glibcxx_requires_valid_range(__first, __last);
3510 __glibcxx_requires_irreflexive(__first, __last);
3512 return std::__minmax_element(__first, __last,
3513 __gnu_cxx::__ops::__iter_less_iter());
3528 template<
typename _ForwardIterator,
typename _Compare>
3529 _GLIBCXX14_CONSTEXPR
3530 inline pair<_ForwardIterator, _ForwardIterator>
3531 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3535 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3536 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3539 __glibcxx_requires_valid_range(__first, __last);
3540 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3542 return std::__minmax_element(__first, __last,
3543 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3547 template<
typename _Tp>
3548 _GLIBCXX14_CONSTEXPR
3550 min(initializer_list<_Tp> __l)
3551 {
return *std::min_element(__l.begin(), __l.end()); }
3553 template<
typename _Tp,
typename _Compare>
3554 _GLIBCXX14_CONSTEXPR
3556 min(initializer_list<_Tp> __l, _Compare __comp)
3559 template<
typename _Tp>
3560 _GLIBCXX14_CONSTEXPR
3562 max(initializer_list<_Tp> __l)
3565 template<
typename _Tp,
typename _Compare>
3566 _GLIBCXX14_CONSTEXPR
3568 max(initializer_list<_Tp> __l, _Compare __comp)
3571 template<
typename _Tp>
3572 _GLIBCXX14_CONSTEXPR
3573 inline pair<_Tp, _Tp>
3574 minmax(initializer_list<_Tp> __l)
3576 pair<const _Tp*, const _Tp*> __p =
3578 return std::make_pair(*__p.first, *__p.second);
3581 template<
typename _Tp,
typename _Compare>
3582 _GLIBCXX14_CONSTEXPR
3583 inline pair<_Tp, _Tp>
3584 minmax(initializer_list<_Tp> __l, _Compare __comp)
3586 pair<const _Tp*, const _Tp*> __p =
3588 return std::make_pair(*__p.first, *__p.second);
3591 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3592 typename _BinaryPredicate>
3593 _GLIBCXX20_CONSTEXPR
3595 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3596 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3600 for (; __first1 != __last1; ++__first1, (void)++__first2)
3601 if (!__pred(__first1, __first2))
3604 if (__first1 == __last1)
3609 _ForwardIterator2 __last2 = __first2;
3611 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3614 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3618 = std::__count_if(__first2, __last2,
3619 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3620 if (0 == __matches ||
3621 std::__count_if(__scan, __last1,
3622 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3641 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3642 _GLIBCXX20_CONSTEXPR
3644 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3645 _ForwardIterator2 __first2)
3648 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3649 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3650 __glibcxx_function_requires(_EqualOpConcept<
3653 __glibcxx_requires_valid_range(__first1, __last1);
3655 return std::__is_permutation(__first1, __last1, __first2,
3656 __gnu_cxx::__ops::__iter_equal_to_iter());
3673 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3674 typename _BinaryPredicate>
3675 _GLIBCXX20_CONSTEXPR
3677 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3678 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3681 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3682 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3683 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3686 __glibcxx_requires_valid_range(__first1, __last1);
3688 return std::__is_permutation(__first1, __last1, __first2,
3689 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3692 #if __cplusplus > 201103L
3693 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3694 typename _BinaryPredicate>
3695 _GLIBCXX20_CONSTEXPR
3697 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3698 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3699 _BinaryPredicate __pred)
3702 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3704 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3705 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3706 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3707 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3718 for (; __first1 != __last1 && __first2 != __last2;
3719 ++__first1, (void)++__first2)
3720 if (!__pred(__first1, __first2))
3725 if (__first1 == __last1)
3732 if (__d1 == 0 && __d2 == 0)
3738 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3741 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3744 auto __matches = std::__count_if(__first2, __last2,
3745 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3747 || std::__count_if(__scan, __last1,
3748 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3768 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3769 _GLIBCXX20_CONSTEXPR
3771 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3772 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3774 __glibcxx_requires_valid_range(__first1, __last1);
3775 __glibcxx_requires_valid_range(__first2, __last2);
3778 std::__is_permutation(__first1, __last1, __first2, __last2,
3779 __gnu_cxx::__ops::__iter_equal_to_iter());
3796 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3797 typename _BinaryPredicate>
3798 _GLIBCXX20_CONSTEXPR
3800 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3801 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3802 _BinaryPredicate __pred)
3804 __glibcxx_requires_valid_range(__first1, __last1);
3805 __glibcxx_requires_valid_range(__first2, __last2);
3807 return std::__is_permutation(__first1, __last1, __first2, __last2,
3808 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3811 #if __cplusplus > 201402L
3813 #define __cpp_lib_clamp 201603
3823 template<
typename _Tp>
3824 constexpr
const _Tp&
3825 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3827 __glibcxx_assert(!(__hi < __lo));
3828 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3841 template<
typename _Tp,
typename _Compare>
3842 constexpr
const _Tp&
3843 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3845 __glibcxx_assert(!__comp(__hi, __lo));
3846 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3851 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
3873 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3874 pair<_IntType, _IntType>
3876 _UniformRandomBitGenerator&& __g)
3880 return std::make_pair(__x / __b1, __x % __b1);
3895 template<
typename _RandomAccessIterator,
3896 typename _UniformRandomNumberGenerator>
3898 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3899 _UniformRandomNumberGenerator&& __g)
3902 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3903 _RandomAccessIterator>)
3904 __glibcxx_requires_valid_range(__first, __last);
3906 if (__first == __last)
3912 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3914 typedef typename __distr_type::param_type __p_type;
3916 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3921 const __uc_type __urngrange = __g.max() - __g.min();
3922 const __uc_type __urange = __uc_type(__last - __first);
3924 if (__urngrange / __urange >= __urange)
3927 _RandomAccessIterator __i = __first + 1;
3933 if ((__urange % 2) == 0)
3935 __distr_type __d{0, 1};
3943 while (__i != __last)
3945 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3959 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3960 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3966 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3980 template<
typename _InputIterator,
typename _Function>
3981 _GLIBCXX20_CONSTEXPR
3983 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3986 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3987 __glibcxx_requires_valid_range(__first, __last);
3988 for (; __first != __last; ++__first)
3993 #if __cplusplus >= 201703L
4006 template<
typename _InputIterator,
typename _Size,
typename _Function>
4008 for_each_n(_InputIterator __first, _Size __n, _Function __f)
4010 auto __n2 = std::__size_to_integer(__n);
4011 using _Cat =
typename iterator_traits<_InputIterator>::iterator_category;
4012 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
4016 auto __last = __first + __n2;
4017 std::for_each(__first, __last,
std::move(__f));
4041 template<
typename _InputIterator,
typename _Tp>
4042 _GLIBCXX20_CONSTEXPR
4043 inline _InputIterator
4044 find(_InputIterator __first, _InputIterator __last,
4048 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4049 __glibcxx_function_requires(_EqualOpConcept<
4051 __glibcxx_requires_valid_range(__first, __last);
4053 __gnu_cxx::__ops::__iter_equals_val(__val));
4066 template<
typename _InputIterator,
typename _Predicate>
4067 _GLIBCXX20_CONSTEXPR
4068 inline _InputIterator
4069 find_if(_InputIterator __first, _InputIterator __last,
4073 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4074 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4076 __glibcxx_requires_valid_range(__first, __last);
4079 __gnu_cxx::__ops::__pred_iter(__pred));
4098 template<
typename _InputIterator,
typename _ForwardIterator>
4099 _GLIBCXX20_CONSTEXPR
4101 find_first_of(_InputIterator __first1, _InputIterator __last1,
4102 _ForwardIterator __first2, _ForwardIterator __last2)
4105 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4106 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4107 __glibcxx_function_requires(_EqualOpConcept<
4110 __glibcxx_requires_valid_range(__first1, __last1);
4111 __glibcxx_requires_valid_range(__first2, __last2);
4113 for (; __first1 != __last1; ++__first1)
4114 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4115 if (*__first1 == *__iter)
4139 template<
typename _InputIterator,
typename _ForwardIterator,
4140 typename _BinaryPredicate>
4141 _GLIBCXX20_CONSTEXPR
4143 find_first_of(_InputIterator __first1, _InputIterator __last1,
4144 _ForwardIterator __first2, _ForwardIterator __last2,
4145 _BinaryPredicate __comp)
4148 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4149 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4150 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4153 __glibcxx_requires_valid_range(__first1, __last1);
4154 __glibcxx_requires_valid_range(__first2, __last2);
4156 for (; __first1 != __last1; ++__first1)
4157 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4158 if (__comp(*__first1, *__iter))
4172 template<
typename _ForwardIterator>
4173 _GLIBCXX20_CONSTEXPR
4174 inline _ForwardIterator
4175 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4178 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4179 __glibcxx_function_requires(_EqualityComparableConcept<
4181 __glibcxx_requires_valid_range(__first, __last);
4183 return std::__adjacent_find(__first, __last,
4184 __gnu_cxx::__ops::__iter_equal_to_iter());
4198 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4199 _GLIBCXX20_CONSTEXPR
4200 inline _ForwardIterator
4201 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4202 _BinaryPredicate __binary_pred)
4205 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4206 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4209 __glibcxx_requires_valid_range(__first, __last);
4211 return std::__adjacent_find(__first, __last,
4212 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4224 template<
typename _InputIterator,
typename _Tp>
4225 _GLIBCXX20_CONSTEXPR
4226 inline typename iterator_traits<_InputIterator>::difference_type
4227 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4230 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4231 __glibcxx_function_requires(_EqualOpConcept<
4233 __glibcxx_requires_valid_range(__first, __last);
4235 return std::__count_if(__first, __last,
4236 __gnu_cxx::__ops::__iter_equals_val(__value));
4248 template<
typename _InputIterator,
typename _Predicate>
4249 _GLIBCXX20_CONSTEXPR
4250 inline typename iterator_traits<_InputIterator>::difference_type
4251 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4254 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4255 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4257 __glibcxx_requires_valid_range(__first, __last);
4259 return std::__count_if(__first, __last,
4260 __gnu_cxx::__ops::__pred_iter(__pred));
4289 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4290 _GLIBCXX20_CONSTEXPR
4291 inline _ForwardIterator1
4292 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4293 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4296 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4297 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4298 __glibcxx_function_requires(_EqualOpConcept<
4301 __glibcxx_requires_valid_range(__first1, __last1);
4302 __glibcxx_requires_valid_range(__first2, __last2);
4304 return std::__search(__first1, __last1, __first2, __last2,
4305 __gnu_cxx::__ops::__iter_equal_to_iter());
4329 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4330 typename _BinaryPredicate>
4331 _GLIBCXX20_CONSTEXPR
4332 inline _ForwardIterator1
4333 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4334 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4335 _BinaryPredicate __predicate)
4338 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4339 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4340 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4343 __glibcxx_requires_valid_range(__first1, __last1);
4344 __glibcxx_requires_valid_range(__first2, __last2);
4346 return std::__search(__first1, __last1, __first2, __last2,
4347 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4365 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4366 _GLIBCXX20_CONSTEXPR
4367 inline _ForwardIterator
4368 search_n(_ForwardIterator __first, _ForwardIterator __last,
4369 _Integer __count,
const _Tp& __val)
4372 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4373 __glibcxx_function_requires(_EqualOpConcept<
4375 __glibcxx_requires_valid_range(__first, __last);
4377 return std::__search_n(__first, __last, __count,
4378 __gnu_cxx::__ops::__iter_equals_val(__val));
4399 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4400 typename _BinaryPredicate>
4401 _GLIBCXX20_CONSTEXPR
4402 inline _ForwardIterator
4403 search_n(_ForwardIterator __first, _ForwardIterator __last,
4404 _Integer __count,
const _Tp& __val,
4405 _BinaryPredicate __binary_pred)
4408 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4409 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4411 __glibcxx_requires_valid_range(__first, __last);
4413 return std::__search_n(__first, __last, __count,
4414 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4417 #if __cplusplus > 201402L
4425 template<
typename _ForwardIterator,
typename _Searcher>
4426 inline _ForwardIterator
4427 search(_ForwardIterator __first, _ForwardIterator __last,
4428 const _Searcher& __searcher)
4429 {
return __searcher(__first, __last).first; }
4448 template<
typename _InputIterator,
typename _OutputIterator,
4449 typename _UnaryOperation>
4450 _GLIBCXX20_CONSTEXPR
4452 transform(_InputIterator __first, _InputIterator __last,
4453 _OutputIterator __result, _UnaryOperation __unary_op)
4456 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4457 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4459 __typeof__(__unary_op(*__first))>)
4460 __glibcxx_requires_valid_range(__first, __last);
4462 for (; __first != __last; ++__first, (void)++__result)
4463 *__result = __unary_op(*__first);
4486 template<
typename _InputIterator1,
typename _InputIterator2,
4487 typename _OutputIterator,
typename _BinaryOperation>
4488 _GLIBCXX20_CONSTEXPR
4490 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4491 _InputIterator2 __first2, _OutputIterator __result,
4492 _BinaryOperation __binary_op)
4495 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4496 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4497 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4499 __typeof__(__binary_op(*__first1,*__first2))>)
4500 __glibcxx_requires_valid_range(__first1, __last1);
4502 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4503 *__result = __binary_op(*__first1, *__first2);
4520 template<
typename _ForwardIterator,
typename _Tp>
4521 _GLIBCXX20_CONSTEXPR
4523 replace(_ForwardIterator __first, _ForwardIterator __last,
4524 const _Tp& __old_value,
const _Tp& __new_value)
4527 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4529 __glibcxx_function_requires(_EqualOpConcept<
4531 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4533 __glibcxx_requires_valid_range(__first, __last);
4535 for (; __first != __last; ++__first)
4536 if (*__first == __old_value)
4537 *__first = __new_value;
4553 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4554 _GLIBCXX20_CONSTEXPR
4556 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4557 _Predicate __pred,
const _Tp& __new_value)
4560 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4562 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4564 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4566 __glibcxx_requires_valid_range(__first, __last);
4568 for (; __first != __last; ++__first)
4569 if (__pred(*__first))
4570 *__first = __new_value;
4586 template<
typename _ForwardIterator,
typename _Generator>
4587 _GLIBCXX20_CONSTEXPR
4589 generate(_ForwardIterator __first, _ForwardIterator __last,
4593 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4594 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4596 __glibcxx_requires_valid_range(__first, __last);
4598 for (; __first != __last; ++__first)
4620 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4621 _GLIBCXX20_CONSTEXPR
4623 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4626 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4628 __typeof__(__gen())>)
4630 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4631 for (_IntSize __niter = std::__size_to_integer(__n);
4632 __niter > 0; --__niter, (void) ++__first)
4658 template<
typename _InputIterator,
typename _OutputIterator>
4659 _GLIBCXX20_CONSTEXPR
4660 inline _OutputIterator
4661 unique_copy(_InputIterator __first, _InputIterator __last,
4662 _OutputIterator __result)
4665 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4666 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4668 __glibcxx_function_requires(_EqualityComparableConcept<
4670 __glibcxx_requires_valid_range(__first, __last);
4672 if (__first == __last)
4675 __gnu_cxx::__ops::__iter_equal_to_iter(),
4699 template<
typename _InputIterator,
typename _OutputIterator,
4700 typename _BinaryPredicate>
4701 _GLIBCXX20_CONSTEXPR
4702 inline _OutputIterator
4703 unique_copy(_InputIterator __first, _InputIterator __last,
4704 _OutputIterator __result,
4705 _BinaryPredicate __binary_pred)
4708 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4709 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4711 __glibcxx_requires_valid_range(__first, __last);
4713 if (__first == __last)
4716 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4733 template<
typename _RandomAccessIterator>
4735 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4738 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4739 _RandomAccessIterator>)
4740 __glibcxx_requires_valid_range(__first, __last);
4742 if (__first != __last)
4743 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4746 _RandomAccessIterator __j = __first
4747 + std::rand() % ((__i - __first) + 1);
4749 std::iter_swap(__i, __j);
4768 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4770 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4771 #
if __cplusplus >= 201103L
4772 _RandomNumberGenerator&& __rand)
4774 _RandomNumberGenerator& __rand)
4778 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4779 _RandomAccessIterator>)
4780 __glibcxx_requires_valid_range(__first, __last);
4782 if (__first == __last)
4784 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4786 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4808 template<
typename _ForwardIterator,
typename _Predicate>
4809 _GLIBCXX20_CONSTEXPR
4810 inline _ForwardIterator
4811 partition(_ForwardIterator __first, _ForwardIterator __last,
4815 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4817 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4819 __glibcxx_requires_valid_range(__first, __last);
4842 template<
typename _RandomAccessIterator>
4843 _GLIBCXX20_CONSTEXPR
4845 partial_sort(_RandomAccessIterator __first,
4846 _RandomAccessIterator __middle,
4847 _RandomAccessIterator __last)
4850 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4851 _RandomAccessIterator>)
4852 __glibcxx_function_requires(_LessThanComparableConcept<
4854 __glibcxx_requires_valid_range(__first, __middle);
4855 __glibcxx_requires_valid_range(__middle, __last);
4856 __glibcxx_requires_irreflexive(__first, __last);
4858 std::__partial_sort(__first, __middle, __last,
4859 __gnu_cxx::__ops::__iter_less_iter());
4881 template<
typename _RandomAccessIterator,
typename _Compare>
4882 _GLIBCXX20_CONSTEXPR
4884 partial_sort(_RandomAccessIterator __first,
4885 _RandomAccessIterator __middle,
4886 _RandomAccessIterator __last,
4890 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4891 _RandomAccessIterator>)
4892 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4895 __glibcxx_requires_valid_range(__first, __middle);
4896 __glibcxx_requires_valid_range(__middle, __last);
4897 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4899 std::__partial_sort(__first, __middle, __last,
4900 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4918 template<
typename _RandomAccessIterator>
4919 _GLIBCXX20_CONSTEXPR
4921 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4922 _RandomAccessIterator __last)
4925 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4926 _RandomAccessIterator>)
4927 __glibcxx_function_requires(_LessThanComparableConcept<
4929 __glibcxx_requires_valid_range(__first, __nth);
4930 __glibcxx_requires_valid_range(__nth, __last);
4931 __glibcxx_requires_irreflexive(__first, __last);
4933 if (__first == __last || __nth == __last)
4936 std::__introselect(__first, __nth, __last,
4938 __gnu_cxx::__ops::__iter_less_iter());
4958 template<
typename _RandomAccessIterator,
typename _Compare>
4959 _GLIBCXX20_CONSTEXPR
4961 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4962 _RandomAccessIterator __last, _Compare __comp)
4965 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4966 _RandomAccessIterator>)
4967 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4970 __glibcxx_requires_valid_range(__first, __nth);
4971 __glibcxx_requires_valid_range(__nth, __last);
4972 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4974 if (__first == __last || __nth == __last)
4977 std::__introselect(__first, __nth, __last,
4979 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4996 template<
typename _RandomAccessIterator>
4997 _GLIBCXX20_CONSTEXPR
4999 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5002 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5003 _RandomAccessIterator>)
5004 __glibcxx_function_requires(_LessThanComparableConcept<
5006 __glibcxx_requires_valid_range(__first, __last);
5007 __glibcxx_requires_irreflexive(__first, __last);
5009 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
5027 template<
typename _RandomAccessIterator,
typename _Compare>
5028 _GLIBCXX20_CONSTEXPR
5030 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5034 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5035 _RandomAccessIterator>)
5036 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5039 __glibcxx_requires_valid_range(__first, __last);
5040 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5042 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
5045 template<
typename _InputIterator1,
typename _InputIterator2,
5046 typename _OutputIterator,
typename _Compare>
5047 _GLIBCXX20_CONSTEXPR
5049 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
5050 _InputIterator2 __first2, _InputIterator2 __last2,
5051 _OutputIterator __result, _Compare __comp)
5053 while (__first1 != __last1 && __first2 != __last2)
5055 if (__comp(__first2, __first1))
5057 *__result = *__first2;
5062 *__result = *__first1;
5067 return std::copy(__first2, __last2,
5068 std::copy(__first1, __last1, __result));
5090 template<
typename _InputIterator1,
typename _InputIterator2,
5091 typename _OutputIterator>
5092 _GLIBCXX20_CONSTEXPR
5093 inline _OutputIterator
5094 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5095 _InputIterator2 __first2, _InputIterator2 __last2,
5096 _OutputIterator __result)
5099 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5100 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5101 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5103 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5105 __glibcxx_function_requires(_LessThanOpConcept<
5108 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5109 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5110 __glibcxx_requires_irreflexive2(__first1, __last1);
5111 __glibcxx_requires_irreflexive2(__first2, __last2);
5113 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5114 __first2, __last2, __result,
5115 __gnu_cxx::__ops::__iter_less_iter());
5141 template<
typename _InputIterator1,
typename _InputIterator2,
5142 typename _OutputIterator,
typename _Compare>
5143 _GLIBCXX20_CONSTEXPR
5144 inline _OutputIterator
5145 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5146 _InputIterator2 __first2, _InputIterator2 __last2,
5147 _OutputIterator __result, _Compare __comp)
5150 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5151 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5152 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5154 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5156 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5159 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5160 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5161 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5162 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5164 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5165 __first2, __last2, __result,
5166 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5169 template<
typename _RandomAccessIterator,
typename _Compare>
5171 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5174 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5176 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5179 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5182 if (__buf.begin() == 0)
5185 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5186 _DistanceType(__buf.size()), __comp);
5206 template<
typename _RandomAccessIterator>
5208 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5211 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5212 _RandomAccessIterator>)
5213 __glibcxx_function_requires(_LessThanComparableConcept<
5215 __glibcxx_requires_valid_range(__first, __last);
5216 __glibcxx_requires_irreflexive(__first, __last);
5218 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5219 __gnu_cxx::__ops::__iter_less_iter());
5240 template<
typename _RandomAccessIterator,
typename _Compare>
5242 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5246 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5247 _RandomAccessIterator>)
5248 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5251 __glibcxx_requires_valid_range(__first, __last);
5252 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5254 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5255 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5258 template<
typename _InputIterator1,
typename _InputIterator2,
5259 typename _OutputIterator,
5261 _GLIBCXX20_CONSTEXPR
5263 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5264 _InputIterator2 __first2, _InputIterator2 __last2,
5265 _OutputIterator __result, _Compare __comp)
5267 while (__first1 != __last1 && __first2 != __last2)
5269 if (__comp(__first1, __first2))
5271 *__result = *__first1;
5274 else if (__comp(__first2, __first1))
5276 *__result = *__first2;
5281 *__result = *__first1;
5287 return std::copy(__first2, __last2,
5288 std::copy(__first1, __last1, __result));
5310 template<
typename _InputIterator1,
typename _InputIterator2,
5311 typename _OutputIterator>
5312 _GLIBCXX20_CONSTEXPR
5313 inline _OutputIterator
5314 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5315 _InputIterator2 __first2, _InputIterator2 __last2,
5316 _OutputIterator __result)
5319 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5320 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5321 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5323 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5325 __glibcxx_function_requires(_LessThanOpConcept<
5328 __glibcxx_function_requires(_LessThanOpConcept<
5331 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5332 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5333 __glibcxx_requires_irreflexive2(__first1, __last1);
5334 __glibcxx_requires_irreflexive2(__first2, __last2);
5336 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5337 __first2, __last2, __result,
5338 __gnu_cxx::__ops::__iter_less_iter());
5361 template<
typename _InputIterator1,
typename _InputIterator2,
5362 typename _OutputIterator,
typename _Compare>
5363 _GLIBCXX20_CONSTEXPR
5364 inline _OutputIterator
5365 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5366 _InputIterator2 __first2, _InputIterator2 __last2,
5367 _OutputIterator __result, _Compare __comp)
5370 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5371 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5372 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5374 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5376 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5379 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5382 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5383 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5384 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5385 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5387 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5388 __first2, __last2, __result,
5389 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5392 template<
typename _InputIterator1,
typename _InputIterator2,
5393 typename _OutputIterator,
5395 _GLIBCXX20_CONSTEXPR
5397 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5398 _InputIterator2 __first2, _InputIterator2 __last2,
5399 _OutputIterator __result, _Compare __comp)
5401 while (__first1 != __last1 && __first2 != __last2)
5402 if (__comp(__first1, __first2))
5404 else if (__comp(__first2, __first1))
5408 *__result = *__first1;
5434 template<
typename _InputIterator1,
typename _InputIterator2,
5435 typename _OutputIterator>
5436 _GLIBCXX20_CONSTEXPR
5437 inline _OutputIterator
5438 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5439 _InputIterator2 __first2, _InputIterator2 __last2,
5440 _OutputIterator __result)
5443 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5444 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5445 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5447 __glibcxx_function_requires(_LessThanOpConcept<
5450 __glibcxx_function_requires(_LessThanOpConcept<
5453 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5454 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5455 __glibcxx_requires_irreflexive2(__first1, __last1);
5456 __glibcxx_requires_irreflexive2(__first2, __last2);
5458 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5459 __first2, __last2, __result,
5460 __gnu_cxx::__ops::__iter_less_iter());
5484 template<
typename _InputIterator1,
typename _InputIterator2,
5485 typename _OutputIterator,
typename _Compare>
5486 _GLIBCXX20_CONSTEXPR
5487 inline _OutputIterator
5488 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5489 _InputIterator2 __first2, _InputIterator2 __last2,
5490 _OutputIterator __result, _Compare __comp)
5493 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5494 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5495 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5497 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5500 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5503 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5504 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5505 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5506 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5508 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5509 __first2, __last2, __result,
5510 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5513 template<
typename _InputIterator1,
typename _InputIterator2,
5514 typename _OutputIterator,
5516 _GLIBCXX20_CONSTEXPR
5518 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5519 _InputIterator2 __first2, _InputIterator2 __last2,
5520 _OutputIterator __result, _Compare __comp)
5522 while (__first1 != __last1 && __first2 != __last2)
5523 if (__comp(__first1, __first2))
5525 *__result = *__first1;
5529 else if (__comp(__first2, __first1))
5536 return std::copy(__first1, __last1, __result);
5559 template<
typename _InputIterator1,
typename _InputIterator2,
5560 typename _OutputIterator>
5561 _GLIBCXX20_CONSTEXPR
5562 inline _OutputIterator
5563 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5564 _InputIterator2 __first2, _InputIterator2 __last2,
5565 _OutputIterator __result)
5568 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5569 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5570 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5572 __glibcxx_function_requires(_LessThanOpConcept<
5575 __glibcxx_function_requires(_LessThanOpConcept<
5578 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5579 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5580 __glibcxx_requires_irreflexive2(__first1, __last1);
5581 __glibcxx_requires_irreflexive2(__first2, __last2);
5583 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5584 __first2, __last2, __result,
5585 __gnu_cxx::__ops::__iter_less_iter());
5611 template<
typename _InputIterator1,
typename _InputIterator2,
5612 typename _OutputIterator,
typename _Compare>
5613 _GLIBCXX20_CONSTEXPR
5614 inline _OutputIterator
5615 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5616 _InputIterator2 __first2, _InputIterator2 __last2,
5617 _OutputIterator __result, _Compare __comp)
5620 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5621 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
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_difference(__first1, __last1,
5636 __first2, __last2, __result,
5637 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5640 template<
typename _InputIterator1,
typename _InputIterator2,
5641 typename _OutputIterator,
5643 _GLIBCXX20_CONSTEXPR
5645 __set_symmetric_difference(_InputIterator1 __first1,
5646 _InputIterator1 __last1,
5647 _InputIterator2 __first2,
5648 _InputIterator2 __last2,
5649 _OutputIterator __result,
5652 while (__first1 != __last1 && __first2 != __last2)
5653 if (__comp(__first1, __first2))
5655 *__result = *__first1;
5659 else if (__comp(__first2, __first1))
5661 *__result = *__first2;
5670 return std::copy(__first2, __last2,
5671 std::copy(__first1, __last1, __result));
5692 template<
typename _InputIterator1,
typename _InputIterator2,
5693 typename _OutputIterator>
5694 _GLIBCXX20_CONSTEXPR
5695 inline _OutputIterator
5696 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5697 _InputIterator2 __first2, _InputIterator2 __last2,
5698 _OutputIterator __result)
5701 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5702 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5703 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5705 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5707 __glibcxx_function_requires(_LessThanOpConcept<
5710 __glibcxx_function_requires(_LessThanOpConcept<
5713 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5714 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5715 __glibcxx_requires_irreflexive2(__first1, __last1);
5716 __glibcxx_requires_irreflexive2(__first2, __last2);
5718 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5719 __first2, __last2, __result,
5720 __gnu_cxx::__ops::__iter_less_iter());
5744 template<
typename _InputIterator1,
typename _InputIterator2,
5745 typename _OutputIterator,
typename _Compare>
5746 _GLIBCXX20_CONSTEXPR
5747 inline _OutputIterator
5748 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5749 _InputIterator2 __first2, _InputIterator2 __last2,
5750 _OutputIterator __result,
5754 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5755 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5756 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5758 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5760 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5763 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5766 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5767 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5768 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5769 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5771 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5772 __first2, __last2, __result,
5773 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5776 template<
typename _ForwardIterator,
typename _Compare>
5777 _GLIBCXX14_CONSTEXPR
5779 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5782 if (__first == __last)
5784 _ForwardIterator __result = __first;
5785 while (++__first != __last)
5786 if (__comp(__first, __result))
5798 template<
typename _ForwardIterator>
5799 _GLIBCXX14_CONSTEXPR
5801 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5804 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5805 __glibcxx_function_requires(_LessThanComparableConcept<
5807 __glibcxx_requires_valid_range(__first, __last);
5808 __glibcxx_requires_irreflexive(__first, __last);
5810 return _GLIBCXX_STD_A::__min_element(__first, __last,
5811 __gnu_cxx::__ops::__iter_less_iter());
5823 template<
typename _ForwardIterator,
typename _Compare>
5824 _GLIBCXX14_CONSTEXPR
5825 inline _ForwardIterator
5826 min_element(_ForwardIterator __first, _ForwardIterator __last,
5830 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5831 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5834 __glibcxx_requires_valid_range(__first, __last);
5835 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5837 return _GLIBCXX_STD_A::__min_element(__first, __last,
5838 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5841 template<
typename _ForwardIterator,
typename _Compare>
5842 _GLIBCXX14_CONSTEXPR
5844 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5847 if (__first == __last)
return __first;
5848 _ForwardIterator __result = __first;
5849 while (++__first != __last)
5850 if (__comp(__result, __first))
5862 template<
typename _ForwardIterator>
5863 _GLIBCXX14_CONSTEXPR
5864 inline _ForwardIterator
5865 max_element(_ForwardIterator __first, _ForwardIterator __last)
5868 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5869 __glibcxx_function_requires(_LessThanComparableConcept<
5871 __glibcxx_requires_valid_range(__first, __last);
5872 __glibcxx_requires_irreflexive(__first, __last);
5874 return _GLIBCXX_STD_A::__max_element(__first, __last,
5875 __gnu_cxx::__ops::__iter_less_iter());
5887 template<
typename _ForwardIterator,
typename _Compare>
5888 _GLIBCXX14_CONSTEXPR
5889 inline _ForwardIterator
5890 max_element(_ForwardIterator __first, _ForwardIterator __last,
5894 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5895 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5898 __glibcxx_requires_valid_range(__first, __last);
5899 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5901 return _GLIBCXX_STD_A::__max_element(__first, __last,
5902 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5905 #if __cplusplus >= 201402L
5907 template<
typename _InputIterator,
typename _RandomAccessIterator,
5908 typename _Size,
typename _UniformRandomBitGenerator>
5909 _RandomAccessIterator
5912 _Size __n, _UniformRandomBitGenerator&& __g)
5915 using __param_type =
typename __distrib_type::param_type;
5916 __distrib_type __d{};
5917 _Size __sample_sz = 0;
5918 while (__first != __last && __sample_sz != __n)
5920 __out[__sample_sz++] = *__first;
5923 for (
auto __pop_sz = __sample_sz; __first != __last;
5924 ++__first, (void) ++__pop_sz)
5926 const auto __k = __d(__g, __param_type{0, __pop_sz});
5928 __out[__k] = *__first;
5930 return __out + __sample_sz;
5934 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5935 typename _Size,
typename _UniformRandomBitGenerator>
5937 __sample(_ForwardIterator __first, _ForwardIterator __last,
5939 _OutputIterator __out, _Cat,
5940 _Size __n, _UniformRandomBitGenerator&& __g)
5943 using __param_type =
typename __distrib_type::param_type;
5948 __distrib_type __d{};
5950 __n =
std::min(__n, __unsampled_sz);
5955 const __uc_type __urngrange = __g.max() - __g.min();
5956 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5960 while (__n != 0 && __unsampled_sz >= 2)
5966 if (__p.
first < __n)
5968 *__out++ = *__first;
5974 if (__n == 0)
break;
5979 *__out++ = *__first;
5989 for (; __n != 0; ++__first)
5990 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5992 *__out++ = *__first;
5998 #if __cplusplus > 201402L
5999 #define __cpp_lib_sample 201603
6001 template<
typename _PopulationIterator,
typename _SampleIterator,
6002 typename _Distance,
typename _UniformRandomBitGenerator>
6004 sample(_PopulationIterator __first, _PopulationIterator __last,
6005 _SampleIterator __out, _Distance __n,
6006 _UniformRandomBitGenerator&& __g)
6008 using __pop_cat =
typename
6010 using __samp_cat =
typename
6014 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
6015 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
6016 "output range must use a RandomAccessIterator when input range"
6017 " does not meet the ForwardIterator requirements");
6019 static_assert(is_integral<_Distance>::value,
6020 "sample size must be an integer type");
6022 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
6024 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
6025 std::forward<_UniformRandomBitGenerator>(__g));
6030 _GLIBCXX_END_NAMESPACE_ALGO
6031 _GLIBCXX_END_NAMESPACE_VERSION