64#if __cplusplus >= 201103L
70# if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
77namespace std _GLIBCXX_VISIBILITY(default)
79_GLIBCXX_BEGIN_NAMESPACE_VERSION
82 template<
typename _Iterator,
typename _Compare>
86 _Iterator __c, _Compare __comp)
91 std::iter_swap(__result, __b);
92 else if (__comp(__a, __c))
93 std::iter_swap(__result, __c);
95 std::iter_swap(__result, __a);
97 else if (__comp(__a, __c))
98 std::iter_swap(__result, __a);
99 else if (__comp(__b, __c))
100 std::iter_swap(__result, __c);
102 std::iter_swap(__result, __b);
106 template<
typename _InputIterator,
typename _Predicate>
108 inline _InputIterator
113 __gnu_cxx::__ops::__negate(__pred),
120 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
125 for (; __len; --__len, (void) ++__first)
126 if (!__pred(__first))
148 template<
typename _ForwardIterator,
typename _Integer,
149 typename _UnaryPredicate>
153 _Integer __count, _UnaryPredicate __unary_pred,
157 while (__first != __last)
161 _ForwardIterator __i = __first;
163 while (__i != __last && __n != 1 && __unary_pred(__i))
181 template<
typename _RandomAccessIter,
typename _Integer,
182 typename _UnaryPredicate>
186 _Integer __count, _UnaryPredicate __unary_pred,
192 _DistanceType __tailSize = __last - __first;
193 _DistanceType __remainder = __count;
195 while (__remainder <= __tailSize)
197 __first += __remainder;
198 __tailSize -= __remainder;
201 _RandomAccessIter __backTrack = __first;
202 while (__unary_pred(--__backTrack))
204 if (--__remainder == 0)
205 return (__first - __count);
207 __remainder = __count + 1 - (__first - __backTrack);
212 template<
typename _ForwardIterator,
typename _Integer,
213 typename _UnaryPredicate>
216 __search_n(_ForwardIterator __first, _ForwardIterator __last,
218 _UnaryPredicate __unary_pred)
231 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
232 typename _BinaryPredicate>
235 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
236 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
237 forward_iterator_tag, forward_iterator_tag,
238 _BinaryPredicate __comp)
240 if (__first2 == __last2)
243 _ForwardIterator1 __result = __last1;
246 _ForwardIterator1 __new_result
247 = std::__search(__first1, __last1, __first2, __last2, __comp);
248 if (__new_result == __last1)
252 __result = __new_result;
253 __first1 = __new_result;
260 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
261 typename _BinaryPredicate>
263 _BidirectionalIterator1
264 __find_end(_BidirectionalIterator1 __first1,
265 _BidirectionalIterator1 __last1,
266 _BidirectionalIterator2 __first2,
267 _BidirectionalIterator2 __last2,
268 bidirectional_iterator_tag, bidirectional_iterator_tag,
269 _BinaryPredicate __comp)
272 __glibcxx_function_requires(_BidirectionalIteratorConcept<
273 _BidirectionalIterator1>)
274 __glibcxx_function_requires(_BidirectionalIteratorConcept<
275 _BidirectionalIterator2>)
277 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
278 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
280 _RevIterator1 __rlast1(__first1);
281 _RevIterator2 __rlast2(__first2);
282 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
283 _RevIterator2(__last2), __rlast2,
286 if (__rresult == __rlast1)
290 _BidirectionalIterator1 __result = __rresult.base();
322 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
324 inline _ForwardIterator1
325 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
326 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
329 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
330 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
331 __glibcxx_function_requires(_EqualOpConcept<
334 __glibcxx_requires_valid_range(__first1, __last1);
335 __glibcxx_requires_valid_range(__first2, __last2);
337 return std::__find_end(__first1, __last1, __first2, __last2,
340 __gnu_cxx::__ops::__iter_equal_to_iter());
371 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
372 typename _BinaryPredicate>
374 inline _ForwardIterator1
375 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
376 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
377 _BinaryPredicate __comp)
380 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
381 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
382 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
385 __glibcxx_requires_valid_range(__first1, __last1);
386 __glibcxx_requires_valid_range(__first2, __last2);
388 return std::__find_end(__first1, __last1, __first2, __last2,
391 __gnu_cxx::__ops::__iter_comp_iter(__comp));
394#if __cplusplus >= 201103L
407 template<
typename _InputIterator,
typename _Predicate>
410 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
411 {
return __last == std::find_if_not(__first, __last, __pred); }
425 template<
typename _InputIterator,
typename _Predicate>
428 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
429 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
444 template<
typename _InputIterator,
typename _Predicate>
447 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
448 {
return !std::none_of(__first, __last, __pred); }
460 template<
typename _InputIterator,
typename _Predicate>
462 inline _InputIterator
463 find_if_not(_InputIterator __first, _InputIterator __last,
467 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
468 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
470 __glibcxx_requires_valid_range(__first, __last);
472 __gnu_cxx::__ops::__pred_iter(__pred));
485 template<
typename _InputIterator,
typename _Predicate>
488 is_partitioned(_InputIterator __first, _InputIterator __last,
491 __first = std::find_if_not(__first, __last, __pred);
492 if (__first == __last)
495 return std::none_of(__first, __last, __pred);
507 template<
typename _ForwardIterator,
typename _Predicate>
510 partition_point(_ForwardIterator __first, _ForwardIterator __last,
514 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
515 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
519 __glibcxx_requires_valid_range(__first, __last);
528 _DistanceType __half = __len >> 1;
529 _ForwardIterator __middle = __first;
531 if (__pred(*__middle))
535 __len = __len - __half - 1;
544 template<
typename _InputIterator,
typename _OutputIterator,
548 __remove_copy_if(_InputIterator __first, _InputIterator __last,
549 _OutputIterator __result, _Predicate __pred)
551 for (; __first != __last; ++__first)
552 if (!__pred(__first))
554 *__result = *__first;
574 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
576 inline _OutputIterator
577 remove_copy(_InputIterator __first, _InputIterator __last,
578 _OutputIterator __result,
const _Tp& __value)
581 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
582 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
584 __glibcxx_function_requires(_EqualOpConcept<
586 __glibcxx_requires_valid_range(__first, __last);
588 return std::__remove_copy_if(__first, __last, __result,
589 __gnu_cxx::__ops::__iter_equals_val(__value));
607 template<
typename _InputIterator,
typename _OutputIterator,
610 inline _OutputIterator
611 remove_copy_if(_InputIterator __first, _InputIterator __last,
612 _OutputIterator __result, _Predicate __pred)
615 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
616 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
618 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
620 __glibcxx_requires_valid_range(__first, __last);
622 return std::__remove_copy_if(__first, __last, __result,
623 __gnu_cxx::__ops::__pred_iter(__pred));
626#if __cplusplus >= 201103L
642 template<
typename _InputIterator,
typename _OutputIterator,
646 copy_if(_InputIterator __first, _InputIterator __last,
647 _OutputIterator __result, _Predicate __pred)
650 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
651 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
653 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
655 __glibcxx_requires_valid_range(__first, __last);
657 for (; __first != __last; ++__first)
658 if (__pred(*__first))
660 *__result = *__first;
666 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
669 __copy_n(_InputIterator __first, _Size __n,
670 _OutputIterator __result, input_iterator_tag)
672 return std::__niter_wrap(__result,
673 __copy_n_a(__first, __n,
674 std::__niter_base(__result),
true));
677 template<
typename _RandomAccessIterator,
typename _Size,
678 typename _OutputIterator>
680 inline _OutputIterator
681 __copy_n(_RandomAccessIterator __first, _Size __n,
682 _OutputIterator __result, random_access_iterator_tag)
683 {
return std::copy(__first, __first + __n, __result); }
698 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
700 inline _OutputIterator
701 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
704 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
705 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
708 const auto __n2 = std::__size_to_integer(__n);
712 __glibcxx_requires_can_increment(__first, __n2);
713 __glibcxx_requires_can_increment(__result, __n2);
715 return std::__copy_n(__first, __n2, __result,
734 template<
typename _InputIterator,
typename _OutputIterator1,
735 typename _OutputIterator2,
typename _Predicate>
737 pair<_OutputIterator1, _OutputIterator2>
738 partition_copy(_InputIterator __first, _InputIterator __last,
739 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
743 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
744 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
746 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
748 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
750 __glibcxx_requires_valid_range(__first, __last);
752 for (; __first != __last; ++__first)
753 if (__pred(*__first))
755 *__out_true = *__first;
760 *__out_false = *__first;
785 template<
typename _ForwardIterator,
typename _Tp>
787 inline _ForwardIterator
788 remove(_ForwardIterator __first, _ForwardIterator __last,
792 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
794 __glibcxx_function_requires(_EqualOpConcept<
796 __glibcxx_requires_valid_range(__first, __last);
798 return std::__remove_if(__first, __last,
799 __gnu_cxx::__ops::__iter_equals_val(__value));
819 template<
typename _ForwardIterator,
typename _Predicate>
821 inline _ForwardIterator
822 remove_if(_ForwardIterator __first, _ForwardIterator __last,
826 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
828 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
830 __glibcxx_requires_valid_range(__first, __last);
832 return std::__remove_if(__first, __last,
833 __gnu_cxx::__ops::__pred_iter(__pred));
836 template<
typename _ForwardIterator,
typename _BinaryPredicate>
839 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
840 _BinaryPredicate __binary_pred)
842 if (__first == __last)
844 _ForwardIterator __next = __first;
845 while (++__next != __last)
847 if (__binary_pred(__first, __next))
854 template<
typename _ForwardIterator,
typename _BinaryPredicate>
857 __unique(_ForwardIterator __first, _ForwardIterator __last,
858 _BinaryPredicate __binary_pred)
861 __first = std::__adjacent_find(__first, __last, __binary_pred);
862 if (__first == __last)
866 _ForwardIterator __dest = __first;
868 while (++__first != __last)
869 if (!__binary_pred(__dest, __first))
870 *++__dest = _GLIBCXX_MOVE(*__first);
888 template<
typename _ForwardIterator>
890 inline _ForwardIterator
891 unique(_ForwardIterator __first, _ForwardIterator __last)
894 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
896 __glibcxx_function_requires(_EqualityComparableConcept<
898 __glibcxx_requires_valid_range(__first, __last);
900 return std::__unique(__first, __last,
901 __gnu_cxx::__ops::__iter_equal_to_iter());
919 template<
typename _ForwardIterator,
typename _BinaryPredicate>
921 inline _ForwardIterator
922 unique(_ForwardIterator __first, _ForwardIterator __last,
923 _BinaryPredicate __binary_pred)
926 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
928 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
931 __glibcxx_requires_valid_range(__first, __last);
933 return std::__unique(__first, __last,
934 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
943 template<
typename _ForwardIterator,
typename _OutputIterator,
944 typename _BinaryPredicate>
948 _OutputIterator __result, _BinaryPredicate __binary_pred,
952 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
956 _ForwardIterator __next = __first;
957 *__result = *__first;
958 while (++__next != __last)
959 if (!__binary_pred(__first, __next))
962 *++__result = *__first;
973 template<
typename _InputIterator,
typename _OutputIterator,
974 typename _BinaryPredicate>
978 _OutputIterator __result, _BinaryPredicate __binary_pred,
982 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
987 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
989 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
991 while (++__first != __last)
992 if (!__rebound_pred(__first, __value))
995 *++__result = __value;
1006 template<
typename _InputIterator,
typename _ForwardIterator,
1007 typename _BinaryPredicate>
1008 _GLIBCXX20_CONSTEXPR
1011 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1015 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1018 *__result = *__first;
1019 while (++__first != __last)
1020 if (!__binary_pred(__result, __first))
1021 *++__result = *__first;
1030 template<
typename _B
idirectionalIterator>
1031 _GLIBCXX20_CONSTEXPR
1033 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1037 if (__first == __last || __first == --__last)
1041 std::iter_swap(__first, __last);
1051 template<
typename _RandomAccessIterator>
1052 _GLIBCXX20_CONSTEXPR
1054 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1057 if (__first == __last)
1060 while (__first < __last)
1062 std::iter_swap(__first, __last);
1080 template<
typename _B
idirectionalIterator>
1081 _GLIBCXX20_CONSTEXPR
1083 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1086 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1087 _BidirectionalIterator>)
1088 __glibcxx_requires_valid_range(__first, __last);
1108 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1109 _GLIBCXX20_CONSTEXPR
1111 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1112 _OutputIterator __result)
1115 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1116 _BidirectionalIterator>)
1117 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1119 __glibcxx_requires_valid_range(__first, __last);
1121 while (__first != __last)
1124 *__result = *__last;
1134 template<
typename _Eucl
ideanRingElement>
1135 _GLIBCXX20_CONSTEXPR
1136 _EuclideanRingElement
1137 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1141 _EuclideanRingElement __t = __m % __n;
1148_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1151 template<
typename _ForwardIterator>
1152 _GLIBCXX20_CONSTEXPR
1155 _ForwardIterator __middle,
1156 _ForwardIterator __last,
1159 if (__first == __middle)
1161 else if (__last == __middle)
1164 _ForwardIterator __first2 = __middle;
1167 std::iter_swap(__first, __first2);
1170 if (__first == __middle)
1171 __middle = __first2;
1173 while (__first2 != __last);
1175 _ForwardIterator __ret = __first;
1177 __first2 = __middle;
1179 while (__first2 != __last)
1181 std::iter_swap(__first, __first2);
1184 if (__first == __middle)
1185 __middle = __first2;
1186 else if (__first2 == __last)
1187 __first2 = __middle;
1193 template<
typename _B
idirectionalIterator>
1194 _GLIBCXX20_CONSTEXPR
1195 _BidirectionalIterator
1197 _BidirectionalIterator __middle,
1198 _BidirectionalIterator __last,
1202 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1203 _BidirectionalIterator>)
1205 if (__first == __middle)
1207 else if (__last == __middle)
1213 while (__first != __middle && __middle != __last)
1215 std::iter_swap(__first, --__last);
1219 if (__first == __middle)
1232 template<
typename _RandomAccessIterator>
1233 _GLIBCXX20_CONSTEXPR
1234 _RandomAccessIterator
1236 _RandomAccessIterator __middle,
1237 _RandomAccessIterator __last,
1241 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1242 _RandomAccessIterator>)
1244 if (__first == __middle)
1246 else if (__last == __middle)
1254 _Distance __n = __last - __first;
1255 _Distance __k = __middle - __first;
1257 if (__k == __n - __k)
1259 std::swap_ranges(__first, __middle, __middle);
1263 _RandomAccessIterator __p = __first;
1264 _RandomAccessIterator __ret = __first + (__last - __middle);
1268 if (__k < __n - __k)
1270 if (__is_pod(_ValueType) && __k == 1)
1272 _ValueType __t = _GLIBCXX_MOVE(*__p);
1273 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1274 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1277 _RandomAccessIterator __q = __p + __k;
1278 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1280 std::iter_swap(__p, __q);
1287 std::swap(__n, __k);
1293 if (__is_pod(_ValueType) && __k == 1)
1295 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1296 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1297 *__p = _GLIBCXX_MOVE(__t);
1300 _RandomAccessIterator __q = __p + __n;
1302 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1306 std::iter_swap(__p, __q);
1311 std::swap(__n, __k);
1339 template<
typename _ForwardIterator>
1340 _GLIBCXX20_CONSTEXPR
1341 inline _ForwardIterator
1342 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1343 _ForwardIterator __last)
1346 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1348 __glibcxx_requires_valid_range(__first, __middle);
1349 __glibcxx_requires_valid_range(__middle, __last);
1355_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1377 template<
typename _ForwardIterator,
typename _OutputIterator>
1378 _GLIBCXX20_CONSTEXPR
1379 inline _OutputIterator
1380 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1381 _ForwardIterator __last, _OutputIterator __result)
1384 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1385 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1387 __glibcxx_requires_valid_range(__first, __middle);
1388 __glibcxx_requires_valid_range(__middle, __last);
1390 return std::copy(__first, __middle,
1391 std::copy(__middle, __last, __result));
1395 template<
typename _ForwardIterator,
typename _Predicate>
1396 _GLIBCXX20_CONSTEXPR
1401 if (__first == __last)
1404 while (__pred(*__first))
1405 if (++__first == __last)
1408 _ForwardIterator __next = __first;
1410 while (++__next != __last)
1411 if (__pred(*__next))
1413 std::iter_swap(__first, __next);
1421 template<
typename _B
idirectionalIterator,
typename _Predicate>
1422 _GLIBCXX20_CONSTEXPR
1423 _BidirectionalIterator
1424 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1430 if (__first == __last)
1432 else if (__pred(*__first))
1438 if (__first == __last)
1440 else if (!
bool(__pred(*__last)))
1444 std::iter_swap(__first, __last);
1458 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1462 _ForwardIterator __last,
1463 _Predicate __pred, _Distance __len,
1465 _Distance __buffer_size)
1470 if (__len <= __buffer_size)
1472 _ForwardIterator __result1 = __first;
1473 _Pointer __result2 = __buffer;
1478 *__result2 = _GLIBCXX_MOVE(*__first);
1481 for (; __first != __last; ++__first)
1482 if (__pred(__first))
1484 *__result1 = _GLIBCXX_MOVE(*__first);
1489 *__result2 = _GLIBCXX_MOVE(*__first);
1493 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1497 _ForwardIterator __middle = __first;
1499 _ForwardIterator __left_split =
1501 __len / 2, __buffer,
1506 _Distance __right_len = __len - __len / 2;
1507 _ForwardIterator __right_split =
1514 __buffer, __buffer_size);
1516 return std::rotate(__left_split, __middle, __right_split);
1519 template<
typename _ForwardIterator,
typename _Predicate>
1521 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1526 if (__first == __last)
1529 typedef typename iterator_traits<_ForwardIterator>::value_type
1531 typedef typename iterator_traits<_ForwardIterator>::difference_type
1534 _Temporary_buffer<_ForwardIterator, _ValueType>
1538 _DistanceType(__buf.requested_size()),
1540 _DistanceType(__buf.size()));
1560 template<
typename _ForwardIterator,
typename _Predicate>
1561 inline _ForwardIterator
1562 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1566 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1568 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1570 __glibcxx_requires_valid_range(__first, __last);
1572 return std::__stable_partition(__first, __last,
1573 __gnu_cxx::__ops::__pred_iter(__pred));
1580 template<
typename _RandomAccessIterator,
typename _Compare>
1581 _GLIBCXX20_CONSTEXPR
1583 __heap_select(_RandomAccessIterator __first,
1584 _RandomAccessIterator __middle,
1585 _RandomAccessIterator __last, _Compare __comp)
1587 std::__make_heap(__first, __middle, __comp);
1588 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1589 if (__comp(__i, __first))
1590 std::__pop_heap(__first, __middle, __i, __comp);
1595 template<
typename _InputIterator,
typename _RandomAccessIterator,
1597 _GLIBCXX20_CONSTEXPR
1598 _RandomAccessIterator
1599 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1600 _RandomAccessIterator __result_first,
1601 _RandomAccessIterator __result_last,
1604 typedef typename iterator_traits<_InputIterator>::value_type
1606 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1607 typedef typename _RItTraits::difference_type _DistanceType;
1609 if (__result_first == __result_last)
1610 return __result_last;
1611 _RandomAccessIterator __result_real_last = __result_first;
1612 while (__first != __last && __result_real_last != __result_last)
1614 *__result_real_last = *__first;
1615 ++__result_real_last;
1619 std::__make_heap(__result_first, __result_real_last, __comp);
1620 while (__first != __last)
1622 if (__comp(__first, __result_first))
1623 std::__adjust_heap(__result_first, _DistanceType(0),
1624 _DistanceType(__result_real_last
1626 _InputValueType(*__first), __comp);
1629 std::__sort_heap(__result_first, __result_real_last, __comp);
1630 return __result_real_last;
1653 template<
typename _InputIterator,
typename _RandomAccessIterator>
1654 _GLIBCXX20_CONSTEXPR
1655 inline _RandomAccessIterator
1656 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1657 _RandomAccessIterator __result_first,
1658 _RandomAccessIterator __result_last)
1660#ifdef _GLIBCXX_CONCEPT_CHECKS
1668 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1669 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1671 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1673 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1674 __glibcxx_requires_valid_range(__first, __last);
1675 __glibcxx_requires_irreflexive(__first, __last);
1676 __glibcxx_requires_valid_range(__result_first, __result_last);
1678 return std::__partial_sort_copy(__first, __last,
1679 __result_first, __result_last,
1680 __gnu_cxx::__ops::__iter_less_iter());
1703 template<
typename _InputIterator,
typename _RandomAccessIterator,
1705 _GLIBCXX20_CONSTEXPR
1706 inline _RandomAccessIterator
1707 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1708 _RandomAccessIterator __result_first,
1709 _RandomAccessIterator __result_last,
1712#ifdef _GLIBCXX_CONCEPT_CHECKS
1720 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1721 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1722 _RandomAccessIterator>)
1723 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1725 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1726 _InputValueType, _OutputValueType>)
1727 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1728 _OutputValueType, _OutputValueType>)
1729 __glibcxx_requires_valid_range(__first, __last);
1730 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1731 __glibcxx_requires_valid_range(__result_first, __result_last);
1733 return std::__partial_sort_copy(__first, __last,
1734 __result_first, __result_last,
1735 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1741 template<
typename _RandomAccessIterator,
typename _Compare>
1742 _GLIBCXX20_CONSTEXPR
1744 __unguarded_linear_insert(_RandomAccessIterator __last,
1747 typename iterator_traits<_RandomAccessIterator>::value_type
1748 __val = _GLIBCXX_MOVE(*__last);
1749 _RandomAccessIterator __next = __last;
1751 while (__comp(__val, __next))
1753 *__last = _GLIBCXX_MOVE(*__next);
1757 *__last = _GLIBCXX_MOVE(__val);
1761 template<
typename _RandomAccessIterator,
typename _Compare>
1762 _GLIBCXX20_CONSTEXPR
1764 __insertion_sort(_RandomAccessIterator __first,
1765 _RandomAccessIterator __last, _Compare __comp)
1767 if (__first == __last)
return;
1769 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1771 if (__comp(__i, __first))
1773 typename iterator_traits<_RandomAccessIterator>::value_type
1774 __val = _GLIBCXX_MOVE(*__i);
1775 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1776 *__first = _GLIBCXX_MOVE(__val);
1779 std::__unguarded_linear_insert(__i,
1780 __gnu_cxx::__ops::__val_comp_iter(__comp));
1785 template<
typename _RandomAccessIterator,
typename _Compare>
1786 _GLIBCXX20_CONSTEXPR
1788 __unguarded_insertion_sort(_RandomAccessIterator __first,
1789 _RandomAccessIterator __last, _Compare __comp)
1791 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1792 std::__unguarded_linear_insert(__i,
1793 __gnu_cxx::__ops::__val_comp_iter(__comp));
1800 enum { _S_threshold = 16 };
1803 template<
typename _RandomAccessIterator,
typename _Compare>
1804 _GLIBCXX20_CONSTEXPR
1806 __final_insertion_sort(_RandomAccessIterator __first,
1807 _RandomAccessIterator __last, _Compare __comp)
1809 if (__last - __first >
int(_S_threshold))
1811 std::__insertion_sort(__first, __first +
int(_S_threshold), __comp);
1812 std::__unguarded_insertion_sort(__first +
int(_S_threshold), __last,
1816 std::__insertion_sort(__first, __last, __comp);
1820 template<
typename _RandomAccessIterator,
typename _Compare>
1821 _GLIBCXX20_CONSTEXPR
1822 _RandomAccessIterator
1823 __unguarded_partition(_RandomAccessIterator __first,
1824 _RandomAccessIterator __last,
1825 _RandomAccessIterator __pivot, _Compare __comp)
1829 while (__comp(__first, __pivot))
1832 while (__comp(__pivot, __last))
1834 if (!(__first < __last))
1836 std::iter_swap(__first, __last);
1842 template<
typename _RandomAccessIterator,
typename _Compare>
1843 _GLIBCXX20_CONSTEXPR
1844 inline _RandomAccessIterator
1845 __unguarded_partition_pivot(_RandomAccessIterator __first,
1846 _RandomAccessIterator __last, _Compare __comp)
1848 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1851 return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1854 template<
typename _RandomAccessIterator,
typename _Compare>
1855 _GLIBCXX20_CONSTEXPR
1857 __partial_sort(_RandomAccessIterator __first,
1858 _RandomAccessIterator __middle,
1859 _RandomAccessIterator __last,
1862 std::__heap_select(__first, __middle, __last, __comp);
1863 std::__sort_heap(__first, __middle, __comp);
1867 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1868 _GLIBCXX20_CONSTEXPR
1870 __introsort_loop(_RandomAccessIterator __first,
1871 _RandomAccessIterator __last,
1872 _Size __depth_limit, _Compare __comp)
1874 while (__last - __first >
int(_S_threshold))
1876 if (__depth_limit == 0)
1878 std::__partial_sort(__first, __last, __last, __comp);
1882 _RandomAccessIterator __cut =
1883 std::__unguarded_partition_pivot(__first, __last, __comp);
1884 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1891 template<
typename _RandomAccessIterator,
typename _Compare>
1892 _GLIBCXX20_CONSTEXPR
1894 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1897 if (__first != __last)
1899 std::__introsort_loop(__first, __last,
1902 std::__final_insertion_sort(__first, __last, __comp);
1906 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1907 _GLIBCXX20_CONSTEXPR
1909 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1910 _RandomAccessIterator __last, _Size __depth_limit,
1913 while (__last - __first > 3)
1915 if (__depth_limit == 0)
1917 std::__heap_select(__first, __nth + 1, __last, __comp);
1919 std::iter_swap(__first, __nth);
1923 _RandomAccessIterator __cut =
1924 std::__unguarded_partition_pivot(__first, __last, __comp);
1930 std::__insertion_sort(__first, __last, __comp);
1954 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1955 _GLIBCXX20_CONSTEXPR
1956 inline _ForwardIterator
1957 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1958 const _Tp& __val, _Compare __comp)
1961 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1962 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1964 __glibcxx_requires_partitioned_lower_pred(__first, __last,
1967 return std::__lower_bound(__first, __last, __val,
1968 __gnu_cxx::__ops::__iter_comp_val(__comp));
1971 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1972 _GLIBCXX20_CONSTEXPR
1974 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
1975 const _Tp& __val, _Compare __comp)
1977 typedef typename iterator_traits<_ForwardIterator>::difference_type
1984 _DistanceType __half = __len >> 1;
1985 _ForwardIterator __middle = __first;
1987 if (__comp(__val, __middle))
1993 __len = __len - __half - 1;
2010 template<
typename _ForwardIterator,
typename _Tp>
2011 _GLIBCXX20_CONSTEXPR
2012 inline _ForwardIterator
2013 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2017 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2018 __glibcxx_function_requires(_LessThanOpConcept<
2020 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2022 return std::__upper_bound(__first, __last, __val,
2023 __gnu_cxx::__ops::__val_less_iter());
2041 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2042 _GLIBCXX20_CONSTEXPR
2043 inline _ForwardIterator
2044 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2045 const _Tp& __val, _Compare __comp)
2048 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2049 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2051 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2054 return std::__upper_bound(__first, __last, __val,
2055 __gnu_cxx::__ops::__val_comp_iter(__comp));
2058 template<
typename _ForwardIterator,
typename _Tp,
2059 typename _CompareItTp,
typename _CompareTpIt>
2060 _GLIBCXX20_CONSTEXPR
2061 pair<_ForwardIterator, _ForwardIterator>
2062 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2064 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2066 typedef typename iterator_traits<_ForwardIterator>::difference_type
2073 _DistanceType __half = __len >> 1;
2074 _ForwardIterator __middle = __first;
2076 if (__comp_it_val(__middle, __val))
2080 __len = __len - __half - 1;
2082 else if (__comp_val_it(__val, __middle))
2086 _ForwardIterator __left
2087 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2089 _ForwardIterator __right
2090 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2091 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2094 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2114 template<
typename _ForwardIterator,
typename _Tp>
2115 _GLIBCXX20_CONSTEXPR
2116 inline pair<_ForwardIterator, _ForwardIterator>
2117 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2121 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2122 __glibcxx_function_requires(_LessThanOpConcept<
2124 __glibcxx_function_requires(_LessThanOpConcept<
2126 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2127 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2129 return std::__equal_range(__first, __last, __val,
2130 __gnu_cxx::__ops::__iter_less_val(),
2131 __gnu_cxx::__ops::__val_less_iter());
2151 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2152 _GLIBCXX20_CONSTEXPR
2153 inline pair<_ForwardIterator, _ForwardIterator>
2154 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2155 const _Tp& __val, _Compare __comp)
2158 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2159 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2161 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2163 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2165 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2168 return std::__equal_range(__first, __last, __val,
2169 __gnu_cxx::__ops::__iter_comp_val(__comp),
2170 __gnu_cxx::__ops::__val_comp_iter(__comp));
2185 template<
typename _ForwardIterator,
typename _Tp>
2186 _GLIBCXX20_CONSTEXPR
2188 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2192 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2193 __glibcxx_function_requires(_LessThanOpConcept<
2195 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2196 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2198 _ForwardIterator __i
2199 = std::__lower_bound(__first, __last, __val,
2200 __gnu_cxx::__ops::__iter_less_val());
2201 return __i != __last && !(__val < *__i);
2219 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2220 _GLIBCXX20_CONSTEXPR
2222 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2223 const _Tp& __val, _Compare __comp)
2226 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2227 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2229 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2231 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2234 _ForwardIterator __i
2235 = std::__lower_bound(__first, __last, __val,
2236 __gnu_cxx::__ops::__iter_comp_val(__comp));
2237 return __i != __last && !bool(__comp(__val, *__i));
2243 template<
typename _InputIterator1,
typename _InputIterator2,
2244 typename _OutputIterator,
typename _Compare>
2247 _InputIterator2 __first2, _InputIterator2 __last2,
2248 _OutputIterator __result, _Compare __comp)
2250 while (__first1 != __last1 && __first2 != __last2)
2252 if (__comp(__first2, __first1))
2254 *__result = _GLIBCXX_MOVE(*__first2);
2259 *__result = _GLIBCXX_MOVE(*__first1);
2264 if (__first1 != __last1)
2265 _GLIBCXX_MOVE3(__first1, __last1, __result);
2269 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2270 typename _BidirectionalIterator3,
typename _Compare>
2273 _BidirectionalIterator1 __last1,
2274 _BidirectionalIterator2 __first2,
2275 _BidirectionalIterator2 __last2,
2276 _BidirectionalIterator3 __result,
2279 if (__first1 == __last1)
2281 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2284 else if (__first2 == __last2)
2291 if (__comp(__last2, __last1))
2293 *--__result = _GLIBCXX_MOVE(*__last1);
2294 if (__first1 == __last1)
2296 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2303 *--__result = _GLIBCXX_MOVE(*__last2);
2304 if (__first2 == __last2)
2312 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2314 _BidirectionalIterator1
2316 _BidirectionalIterator1 __middle,
2317 _BidirectionalIterator1 __last,
2318 _Distance __len1, _Distance __len2,
2319 _BidirectionalIterator2 __buffer,
2320 _Distance __buffer_size)
2322 _BidirectionalIterator2 __buffer_end;
2323 if (__len1 > __len2 && __len2 <= __buffer_size)
2327 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2328 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2329 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2334 else if (__len1 <= __buffer_size)
2338 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2339 _GLIBCXX_MOVE3(__middle, __last, __first);
2340 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2346 return std::rotate(__first, __middle, __last);
2350 template<
typename _BidirectionalIterator,
typename _Distance,
2351 typename _Pointer,
typename _Compare>
2354 _BidirectionalIterator __middle,
2355 _BidirectionalIterator __last,
2356 _Distance __len1, _Distance __len2,
2357 _Pointer __buffer, _Compare __comp)
2359 if (__len1 <= __len2)
2361 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2367 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2369 __buffer_end, __last, __comp);
2373 template<
typename _BidirectionalIterator,
typename _Distance,
2374 typename _Pointer,
typename _Compare>
2376 __merge_adaptive_resize(_BidirectionalIterator __first,
2377 _BidirectionalIterator __middle,
2378 _BidirectionalIterator __last,
2379 _Distance __len1, _Distance __len2,
2380 _Pointer __buffer, _Distance __buffer_size,
2383 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2385 __len1, __len2, __buffer, __comp);
2388 _BidirectionalIterator __first_cut = __first;
2389 _BidirectionalIterator __second_cut = __middle;
2390 _Distance __len11 = 0;
2391 _Distance __len22 = 0;
2392 if (__len1 > __len2)
2394 __len11 = __len1 / 2;
2397 = std::__lower_bound(__middle, __last, *__first_cut,
2398 __gnu_cxx::__ops::__iter_comp_val(__comp));
2403 __len22 = __len2 / 2;
2406 = std::__upper_bound(__first, __middle, *__second_cut,
2407 __gnu_cxx::__ops::__val_comp_iter(__comp));
2411 _BidirectionalIterator __new_middle
2413 _Distance(__len1 - __len11), __len22,
2414 __buffer, __buffer_size);
2415 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2417 __buffer, __buffer_size, __comp);
2418 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2419 _Distance(__len1 - __len11),
2420 _Distance(__len2 - __len22),
2421 __buffer, __buffer_size, __comp);
2426 template<
typename _BidirectionalIterator,
typename _Distance,
2430 _BidirectionalIterator __middle,
2431 _BidirectionalIterator __last,
2432 _Distance __len1, _Distance __len2,
2435 if (__len1 == 0 || __len2 == 0)
2438 if (__len1 + __len2 == 2)
2440 if (__comp(__middle, __first))
2441 std::iter_swap(__first, __middle);
2445 _BidirectionalIterator __first_cut = __first;
2446 _BidirectionalIterator __second_cut = __middle;
2447 _Distance __len11 = 0;
2448 _Distance __len22 = 0;
2449 if (__len1 > __len2)
2451 __len11 = __len1 / 2;
2454 = std::__lower_bound(__middle, __last, *__first_cut,
2455 __gnu_cxx::__ops::__iter_comp_val(__comp));
2460 __len22 = __len2 / 2;
2463 = std::__upper_bound(__first, __middle, *__second_cut,
2464 __gnu_cxx::__ops::__val_comp_iter(__comp));
2468 _BidirectionalIterator __new_middle
2469 = std::rotate(__first_cut, __middle, __second_cut);
2471 __len11, __len22, __comp);
2473 __len1 - __len11, __len2 - __len22, __comp);
2476 template<
typename _B
idirectionalIterator,
typename _Compare>
2478 __inplace_merge(_BidirectionalIterator __first,
2479 _BidirectionalIterator __middle,
2480 _BidirectionalIterator __last,
2483 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2485 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2488 if (__first == __middle || __middle == __last)
2491 const _DistanceType __len1 =
std::distance(__first, __middle);
2492 const _DistanceType __len2 =
std::distance(__middle, __last);
2495 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2498 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2500 if (__builtin_expect(__buf.size() == __buf.requested_size(),
true))
2502 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2503 else if (__builtin_expect(__buf.begin() == 0,
false))
2505 (__first, __middle, __last, __len1, __len2, __comp);
2507 std::__merge_adaptive_resize
2508 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2509 _DistanceType(__buf.size()), __comp);
2512 (__first, __middle, __last, __len1, __len2, __comp);
2534 template<
typename _B
idirectionalIterator>
2536 inplace_merge(_BidirectionalIterator __first,
2537 _BidirectionalIterator __middle,
2538 _BidirectionalIterator __last)
2541 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2542 _BidirectionalIterator>)
2543 __glibcxx_function_requires(_LessThanComparableConcept<
2545 __glibcxx_requires_sorted(__first, __middle);
2546 __glibcxx_requires_sorted(__middle, __last);
2547 __glibcxx_requires_irreflexive(__first, __last);
2549 std::__inplace_merge(__first, __middle, __last,
2550 __gnu_cxx::__ops::__iter_less_iter());
2575 template<
typename _B
idirectionalIterator,
typename _Compare>
2577 inplace_merge(_BidirectionalIterator __first,
2578 _BidirectionalIterator __middle,
2579 _BidirectionalIterator __last,
2583 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2584 _BidirectionalIterator>)
2585 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2588 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2589 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2590 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2592 std::__inplace_merge(__first, __middle, __last,
2593 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2598 template<
typename _InputIterator,
typename _OutputIterator,
2602 _InputIterator __first2, _InputIterator __last2,
2603 _OutputIterator __result, _Compare __comp)
2605 while (__first1 != __last1 && __first2 != __last2)
2607 if (__comp(__first2, __first1))
2609 *__result = _GLIBCXX_MOVE(*__first2);
2614 *__result = _GLIBCXX_MOVE(*__first1);
2619 return _GLIBCXX_MOVE3(__first2, __last2,
2620 _GLIBCXX_MOVE3(__first1, __last1,
2624 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2625 typename _Distance,
typename _Compare>
2627 __merge_sort_loop(_RandomAccessIterator1 __first,
2628 _RandomAccessIterator1 __last,
2629 _RandomAccessIterator2 __result, _Distance __step_size,
2632 const _Distance __two_step = 2 * __step_size;
2634 while (__last - __first >= __two_step)
2637 __first + __step_size,
2638 __first + __two_step,
2640 __first += __two_step;
2642 __step_size =
std::min(_Distance(__last - __first), __step_size);
2645 __first + __step_size, __last, __result, __comp);
2648 template<
typename _RandomAccessIterator,
typename _Distance,
2650 _GLIBCXX20_CONSTEXPR
2652 __chunk_insertion_sort(_RandomAccessIterator __first,
2653 _RandomAccessIterator __last,
2654 _Distance __chunk_size, _Compare __comp)
2656 while (__last - __first >= __chunk_size)
2658 std::__insertion_sort(__first, __first + __chunk_size, __comp);
2659 __first += __chunk_size;
2661 std::__insertion_sort(__first, __last, __comp);
2664 enum { _S_chunk_size = 7 };
2666 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2668 __merge_sort_with_buffer(_RandomAccessIterator __first,
2669 _RandomAccessIterator __last,
2670 _Pointer __buffer, _Compare __comp)
2672 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2675 const _Distance __len = __last - __first;
2676 const _Pointer __buffer_last = __buffer + __len;
2678 _Distance __step_size = _S_chunk_size;
2679 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2681 while (__step_size < __len)
2683 std::__merge_sort_loop(__first, __last, __buffer,
2684 __step_size, __comp);
2686 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2687 __step_size, __comp);
2692 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2694 __stable_sort_adaptive(_RandomAccessIterator __first,
2695 _RandomAccessIterator __middle,
2696 _RandomAccessIterator __last,
2697 _Pointer __buffer, _Compare __comp)
2699 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2700 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2703 __middle - __first, __last - __middle,
2707 template<
typename _RandomAccessIterator,
typename _Pointer,
2708 typename _Distance,
typename _Compare>
2710 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2711 _RandomAccessIterator __last,
2712 _Pointer __buffer, _Distance __buffer_size,
2715 const _Distance __len = (__last - __first + 1) / 2;
2716 const _RandomAccessIterator __middle = __first + __len;
2717 if (__len > __buffer_size)
2719 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2720 __buffer_size, __comp);
2721 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2722 __buffer_size, __comp);
2723 std::__merge_adaptive_resize(__first, __middle, __last,
2724 _Distance(__middle - __first),
2725 _Distance(__last - __middle),
2726 __buffer, __buffer_size,
2730 std::__stable_sort_adaptive(__first, __middle, __last,
2735 template<
typename _RandomAccessIterator,
typename _Compare>
2738 _RandomAccessIterator __last, _Compare __comp)
2740 if (__last - __first < 15)
2742 std::__insertion_sort(__first, __last, __comp);
2745 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2761 template<
typename _InputIterator1,
typename _InputIterator2,
2763 _GLIBCXX20_CONSTEXPR
2765 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2766 _InputIterator2 __first2, _InputIterator2 __last2,
2769 while (__first1 != __last1 && __first2 != __last2)
2771 if (__comp(__first2, __first1))
2773 if (!__comp(__first1, __first2))
2778 return __first2 == __last2;
2799 template<
typename _InputIterator1,
typename _InputIterator2>
2800 _GLIBCXX20_CONSTEXPR
2802 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2803 _InputIterator2 __first2, _InputIterator2 __last2)
2806 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2807 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2808 __glibcxx_function_requires(_LessThanOpConcept<
2811 __glibcxx_function_requires(_LessThanOpConcept<
2814 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2815 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2816 __glibcxx_requires_irreflexive2(__first1, __last1);
2817 __glibcxx_requires_irreflexive2(__first2, __last2);
2819 return std::__includes(__first1, __last1, __first2, __last2,
2820 __gnu_cxx::__ops::__iter_less_iter());
2844 template<
typename _InputIterator1,
typename _InputIterator2,
2846 _GLIBCXX20_CONSTEXPR
2848 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2849 _InputIterator2 __first2, _InputIterator2 __last2,
2853 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2854 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2855 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2858 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2861 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2862 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2863 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2864 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2866 return std::__includes(__first1, __last1, __first2, __last2,
2867 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2880 template<
typename _B
idirectionalIterator,
typename _Compare>
2881 _GLIBCXX20_CONSTEXPR
2883 __next_permutation(_BidirectionalIterator __first,
2884 _BidirectionalIterator __last, _Compare __comp)
2886 if (__first == __last)
2888 _BidirectionalIterator __i = __first;
2897 _BidirectionalIterator __ii = __i;
2899 if (__comp(__i, __ii))
2901 _BidirectionalIterator __j = __last;
2902 while (!__comp(__i, --__j))
2904 std::iter_swap(__i, __j);
2930 template<
typename _B
idirectionalIterator>
2931 _GLIBCXX20_CONSTEXPR
2933 next_permutation(_BidirectionalIterator __first,
2934 _BidirectionalIterator __last)
2937 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2938 _BidirectionalIterator>)
2939 __glibcxx_function_requires(_LessThanComparableConcept<
2941 __glibcxx_requires_valid_range(__first, __last);
2942 __glibcxx_requires_irreflexive(__first, __last);
2944 return std::__next_permutation
2945 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2963 template<
typename _B
idirectionalIterator,
typename _Compare>
2964 _GLIBCXX20_CONSTEXPR
2966 next_permutation(_BidirectionalIterator __first,
2967 _BidirectionalIterator __last, _Compare __comp)
2970 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2971 _BidirectionalIterator>)
2972 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2975 __glibcxx_requires_valid_range(__first, __last);
2976 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2978 return std::__next_permutation
2979 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2982 template<
typename _B
idirectionalIterator,
typename _Compare>
2983 _GLIBCXX20_CONSTEXPR
2985 __prev_permutation(_BidirectionalIterator __first,
2986 _BidirectionalIterator __last, _Compare __comp)
2988 if (__first == __last)
2990 _BidirectionalIterator __i = __first;
2999 _BidirectionalIterator __ii = __i;
3001 if (__comp(__ii, __i))
3003 _BidirectionalIterator __j = __last;
3004 while (!__comp(--__j, __i))
3006 std::iter_swap(__i, __j);
3033 template<
typename _B
idirectionalIterator>
3034 _GLIBCXX20_CONSTEXPR
3036 prev_permutation(_BidirectionalIterator __first,
3037 _BidirectionalIterator __last)
3040 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3041 _BidirectionalIterator>)
3042 __glibcxx_function_requires(_LessThanComparableConcept<
3044 __glibcxx_requires_valid_range(__first, __last);
3045 __glibcxx_requires_irreflexive(__first, __last);
3047 return std::__prev_permutation(__first, __last,
3048 __gnu_cxx::__ops::__iter_less_iter());
3066 template<
typename _B
idirectionalIterator,
typename _Compare>
3067 _GLIBCXX20_CONSTEXPR
3069 prev_permutation(_BidirectionalIterator __first,
3070 _BidirectionalIterator __last, _Compare __comp)
3073 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3074 _BidirectionalIterator>)
3075 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3078 __glibcxx_requires_valid_range(__first, __last);
3079 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3081 return std::__prev_permutation(__first, __last,
3082 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3088 template<
typename _InputIterator,
typename _OutputIterator,
3089 typename _Predicate,
typename _Tp>
3090 _GLIBCXX20_CONSTEXPR
3092 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3093 _OutputIterator __result,
3094 _Predicate __pred,
const _Tp& __new_value)
3096 for (; __first != __last; ++__first, (void)++__result)
3097 if (__pred(__first))
3098 *__result = __new_value;
3100 *__result = *__first;
3118 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3119 _GLIBCXX20_CONSTEXPR
3120 inline _OutputIterator
3121 replace_copy(_InputIterator __first, _InputIterator __last,
3122 _OutputIterator __result,
3123 const _Tp& __old_value,
const _Tp& __new_value)
3126 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3127 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3129 __glibcxx_function_requires(_EqualOpConcept<
3131 __glibcxx_requires_valid_range(__first, __last);
3133 return std::__replace_copy_if(__first, __last, __result,
3134 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3153 template<
typename _InputIterator,
typename _OutputIterator,
3154 typename _Predicate,
typename _Tp>
3155 _GLIBCXX20_CONSTEXPR
3156 inline _OutputIterator
3157 replace_copy_if(_InputIterator __first, _InputIterator __last,
3158 _OutputIterator __result,
3159 _Predicate __pred,
const _Tp& __new_value)
3162 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3163 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3165 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3167 __glibcxx_requires_valid_range(__first, __last);
3169 return std::__replace_copy_if(__first, __last, __result,
3170 __gnu_cxx::__ops::__pred_iter(__pred),
3174#if __cplusplus >= 201103L
3182 template<
typename _ForwardIterator>
3183 _GLIBCXX20_CONSTEXPR
3185 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3186 {
return std::is_sorted_until(__first, __last) == __last; }
3197 template<
typename _ForwardIterator,
typename _Compare>
3198 _GLIBCXX20_CONSTEXPR
3200 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3202 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3204 template<
typename _ForwardIterator,
typename _Compare>
3205 _GLIBCXX20_CONSTEXPR
3207 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3210 if (__first == __last)
3213 _ForwardIterator __next = __first;
3214 for (++__next; __next != __last; __first = __next, (void)++__next)
3215 if (__comp(__next, __first))
3228 template<
typename _ForwardIterator>
3229 _GLIBCXX20_CONSTEXPR
3230 inline _ForwardIterator
3231 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3234 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3235 __glibcxx_function_requires(_LessThanComparableConcept<
3237 __glibcxx_requires_valid_range(__first, __last);
3238 __glibcxx_requires_irreflexive(__first, __last);
3240 return std::__is_sorted_until(__first, __last,
3241 __gnu_cxx::__ops::__iter_less_iter());
3253 template<
typename _ForwardIterator,
typename _Compare>
3254 _GLIBCXX20_CONSTEXPR
3255 inline _ForwardIterator
3256 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3260 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3261 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3264 __glibcxx_requires_valid_range(__first, __last);
3265 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3267 return std::__is_sorted_until(__first, __last,
3268 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3279 template<
typename _Tp>
3280 _GLIBCXX14_CONSTEXPR
3281 inline pair<const _Tp&, const _Tp&>
3285 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3287 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3300 template<
typename _Tp,
typename _Compare>
3301 _GLIBCXX14_CONSTEXPR
3302 inline pair<const _Tp&, const _Tp&>
3303 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3309 template<
typename _ForwardIterator,
typename _Compare>
3310 _GLIBCXX14_CONSTEXPR
3311 pair<_ForwardIterator, _ForwardIterator>
3312 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3315 _ForwardIterator __next = __first;
3316 if (__first == __last
3317 || ++__next == __last)
3318 return std::make_pair(__first, __first);
3320 _ForwardIterator __min{}, __max{};
3321 if (__comp(__next, __first))
3335 while (__first != __last)
3338 if (++__next == __last)
3340 if (__comp(__first, __min))
3342 else if (!__comp(__first, __max))
3347 if (__comp(__next, __first))
3349 if (__comp(__next, __min))
3351 if (!__comp(__first, __max))
3356 if (__comp(__first, __min))
3358 if (!__comp(__next, __max))
3366 return std::make_pair(__min, __max);
3380 template<
typename _ForwardIterator>
3381 _GLIBCXX14_CONSTEXPR
3382 inline pair<_ForwardIterator, _ForwardIterator>
3383 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3386 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3387 __glibcxx_function_requires(_LessThanComparableConcept<
3389 __glibcxx_requires_valid_range(__first, __last);
3390 __glibcxx_requires_irreflexive(__first, __last);
3392 return std::__minmax_element(__first, __last,
3393 __gnu_cxx::__ops::__iter_less_iter());
3408 template<
typename _ForwardIterator,
typename _Compare>
3409 _GLIBCXX14_CONSTEXPR
3410 inline pair<_ForwardIterator, _ForwardIterator>
3411 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3415 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3416 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3419 __glibcxx_requires_valid_range(__first, __last);
3420 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3422 return std::__minmax_element(__first, __last,
3423 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3426 template<
typename _Tp>
3427 _GLIBCXX14_CONSTEXPR
3428 inline pair<_Tp, _Tp>
3429 minmax(initializer_list<_Tp> __l)
3431 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3432 pair<const _Tp*, const _Tp*> __p =
3433 std::__minmax_element(__l.begin(), __l.end(),
3434 __gnu_cxx::__ops::__iter_less_iter());
3435 return std::make_pair(*__p.first, *__p.second);
3438 template<
typename _Tp,
typename _Compare>
3439 _GLIBCXX14_CONSTEXPR
3440 inline pair<_Tp, _Tp>
3441 minmax(initializer_list<_Tp> __l, _Compare __comp)
3443 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3444 pair<const _Tp*, const _Tp*> __p =
3445 std::__minmax_element(__l.begin(), __l.end(),
3446 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3447 return std::make_pair(*__p.first, *__p.second);
3464 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3465 typename _BinaryPredicate>
3466 _GLIBCXX20_CONSTEXPR
3468 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3469 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3472 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3473 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3474 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3477 __glibcxx_requires_valid_range(__first1, __last1);
3479 return std::__is_permutation(__first1, __last1, __first2,
3480 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3483#if __cplusplus > 201103L
3484 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3485 typename _BinaryPredicate>
3486 _GLIBCXX20_CONSTEXPR
3488 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3489 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3490 _BinaryPredicate __pred)
3493 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3495 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3496 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3497 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3498 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3509 for (; __first1 != __last1 && __first2 != __last2;
3510 ++__first1, (void)++__first2)
3511 if (!__pred(__first1, __first2))
3516 if (__first1 == __last1)
3523 if (__d1 == 0 && __d2 == 0)
3529 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3532 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3535 auto __matches = std::__count_if(__first2, __last2,
3536 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3538 || std::__count_if(__scan, __last1,
3539 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3559 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3560 _GLIBCXX20_CONSTEXPR
3562 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3563 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3565 __glibcxx_requires_valid_range(__first1, __last1);
3566 __glibcxx_requires_valid_range(__first2, __last2);
3569 std::__is_permutation(__first1, __last1, __first2, __last2,
3570 __gnu_cxx::__ops::__iter_equal_to_iter());
3587 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3588 typename _BinaryPredicate>
3589 _GLIBCXX20_CONSTEXPR
3591 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3592 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3593 _BinaryPredicate __pred)
3595 __glibcxx_requires_valid_range(__first1, __last1);
3596 __glibcxx_requires_valid_range(__first2, __last2);
3598 return std::__is_permutation(__first1, __last1, __first2, __last2,
3599 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3603#ifdef __glibcxx_clamp
3615 template<
typename _Tp>
3616 constexpr const _Tp&
3617 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3619 __glibcxx_assert(!(__hi < __lo));
3635 template<
typename _Tp,
typename _Compare>
3636 constexpr const _Tp&
3637 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3639 __glibcxx_assert(!__comp(__hi, __lo));
3665 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3666 pair<_IntType, _IntType>
3668 _UniformRandomBitGenerator&& __g)
3672 return std::make_pair(__x / __b1, __x % __b1);
3687 template<
typename _RandomAccessIterator,
3688 typename _UniformRandomNumberGenerator>
3690 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3691 _UniformRandomNumberGenerator&& __g)
3694 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3695 _RandomAccessIterator>)
3696 __glibcxx_requires_valid_range(__first, __last);
3698 if (__first == __last)
3704 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3706 typedef typename __distr_type::param_type __p_type;
3708 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3713 const __uc_type __urngrange = __g.max() - __g.min();
3714 const __uc_type __urange = __uc_type(__last - __first);
3716 if (__urngrange / __urange >= __urange)
3719 _RandomAccessIterator __i = __first + 1;
3725 if ((__urange % 2) == 0)
3727 __distr_type __d{0, 1};
3728 std::iter_swap(__i++, __first + __d(__g));
3735 while (__i != __last)
3737 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3742 std::iter_swap(__i++, __first + __pospos.
first);
3743 std::iter_swap(__i++, __first + __pospos.
second);
3751 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3752 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3756_GLIBCXX_BEGIN_NAMESPACE_ALGO
3770 template<
typename _InputIterator,
typename _Function>
3771 _GLIBCXX20_CONSTEXPR
3773 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3776 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3777 __glibcxx_requires_valid_range(__first, __last);
3778 for (; __first != __last; ++__first)
3783#if __cplusplus >= 201703L
3796 template<
typename _InputIterator,
typename _Size,
typename _Function>
3797 _GLIBCXX20_CONSTEXPR
3801 auto __n2 = std::__size_to_integer(__n);
3803 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3807 auto __last = __first + __n2;
3808 std::for_each(__first, __last,
std::move(__f));
3832 template<
typename _InputIterator,
typename _Tp>
3833 _GLIBCXX20_CONSTEXPR
3834 inline _InputIterator
3835 find(_InputIterator __first, _InputIterator __last,
3839 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3840 __glibcxx_function_requires(_EqualOpConcept<
3842 __glibcxx_requires_valid_range(__first, __last);
3844 __gnu_cxx::__ops::__iter_equals_val(__val));
3857 template<
typename _InputIterator,
typename _Predicate>
3858 _GLIBCXX20_CONSTEXPR
3859 inline _InputIterator
3860 find_if(_InputIterator __first, _InputIterator __last,
3864 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3865 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3867 __glibcxx_requires_valid_range(__first, __last);
3870 __gnu_cxx::__ops::__pred_iter(__pred));
3889 template<
typename _InputIterator,
typename _ForwardIterator>
3890 _GLIBCXX20_CONSTEXPR
3892 find_first_of(_InputIterator __first1, _InputIterator __last1,
3893 _ForwardIterator __first2, _ForwardIterator __last2)
3896 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3897 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3898 __glibcxx_function_requires(_EqualOpConcept<
3901 __glibcxx_requires_valid_range(__first1, __last1);
3902 __glibcxx_requires_valid_range(__first2, __last2);
3904 for (; __first1 != __last1; ++__first1)
3905 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3906 if (*__first1 == *__iter)
3930 template<
typename _InputIterator,
typename _ForwardIterator,
3931 typename _BinaryPredicate>
3932 _GLIBCXX20_CONSTEXPR
3934 find_first_of(_InputIterator __first1, _InputIterator __last1,
3935 _ForwardIterator __first2, _ForwardIterator __last2,
3936 _BinaryPredicate __comp)
3939 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3940 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3941 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3944 __glibcxx_requires_valid_range(__first1, __last1);
3945 __glibcxx_requires_valid_range(__first2, __last2);
3947 for (; __first1 != __last1; ++__first1)
3948 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3949 if (__comp(*__first1, *__iter))
3963 template<
typename _ForwardIterator>
3964 _GLIBCXX20_CONSTEXPR
3965 inline _ForwardIterator
3966 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3969 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3970 __glibcxx_function_requires(_EqualityComparableConcept<
3972 __glibcxx_requires_valid_range(__first, __last);
3974 return std::__adjacent_find(__first, __last,
3975 __gnu_cxx::__ops::__iter_equal_to_iter());
3989 template<
typename _ForwardIterator,
typename _BinaryPredicate>
3990 _GLIBCXX20_CONSTEXPR
3991 inline _ForwardIterator
3992 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
3993 _BinaryPredicate __binary_pred)
3996 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3997 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4000 __glibcxx_requires_valid_range(__first, __last);
4002 return std::__adjacent_find(__first, __last,
4003 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4015 template<
typename _InputIterator,
typename _Tp>
4016 _GLIBCXX20_CONSTEXPR
4017 inline typename iterator_traits<_InputIterator>::difference_type
4018 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4021 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4022 __glibcxx_function_requires(_EqualOpConcept<
4024 __glibcxx_requires_valid_range(__first, __last);
4026 return std::__count_if(__first, __last,
4027 __gnu_cxx::__ops::__iter_equals_val(__value));
4039 template<
typename _InputIterator,
typename _Predicate>
4040 _GLIBCXX20_CONSTEXPR
4041 inline typename iterator_traits<_InputIterator>::difference_type
4042 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4045 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4046 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4048 __glibcxx_requires_valid_range(__first, __last);
4050 return std::__count_if(__first, __last,
4051 __gnu_cxx::__ops::__pred_iter(__pred));
4080 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4081 _GLIBCXX20_CONSTEXPR
4082 inline _ForwardIterator1
4083 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4084 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4087 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4088 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4089 __glibcxx_function_requires(_EqualOpConcept<
4092 __glibcxx_requires_valid_range(__first1, __last1);
4093 __glibcxx_requires_valid_range(__first2, __last2);
4095 return std::__search(__first1, __last1, __first2, __last2,
4096 __gnu_cxx::__ops::__iter_equal_to_iter());
4114 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4115 _GLIBCXX20_CONSTEXPR
4116 inline _ForwardIterator
4117 search_n(_ForwardIterator __first, _ForwardIterator __last,
4118 _Integer __count,
const _Tp& __val)
4121 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4122 __glibcxx_function_requires(_EqualOpConcept<
4124 __glibcxx_requires_valid_range(__first, __last);
4126 return std::__search_n(__first, __last, __count,
4127 __gnu_cxx::__ops::__iter_equals_val(__val));
4148 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4149 typename _BinaryPredicate>
4150 _GLIBCXX20_CONSTEXPR
4151 inline _ForwardIterator
4152 search_n(_ForwardIterator __first, _ForwardIterator __last,
4153 _Integer __count,
const _Tp& __val,
4154 _BinaryPredicate __binary_pred)
4157 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4158 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4160 __glibcxx_requires_valid_range(__first, __last);
4162 return std::__search_n(__first, __last, __count,
4163 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4166#if __cplusplus >= 201703L
4174 template<
typename _ForwardIterator,
typename _Searcher>
4175 _GLIBCXX20_CONSTEXPR
4176 inline _ForwardIterator
4177 search(_ForwardIterator __first, _ForwardIterator __last,
4178 const _Searcher& __searcher)
4179 {
return __searcher(__first, __last).first; }
4198 template<
typename _InputIterator,
typename _OutputIterator,
4199 typename _UnaryOperation>
4200 _GLIBCXX20_CONSTEXPR
4202 transform(_InputIterator __first, _InputIterator __last,
4203 _OutputIterator __result, _UnaryOperation __unary_op)
4206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4207 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4209 __typeof__(__unary_op(*__first))>)
4210 __glibcxx_requires_valid_range(__first, __last);
4212 for (; __first != __last; ++__first, (void)++__result)
4213 *__result = __unary_op(*__first);
4236 template<
typename _InputIterator1,
typename _InputIterator2,
4237 typename _OutputIterator,
typename _BinaryOperation>
4238 _GLIBCXX20_CONSTEXPR
4240 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4241 _InputIterator2 __first2, _OutputIterator __result,
4242 _BinaryOperation __binary_op)
4245 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4246 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4247 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4249 __typeof__(__binary_op(*__first1,*__first2))>)
4250 __glibcxx_requires_valid_range(__first1, __last1);
4252 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4253 *__result = __binary_op(*__first1, *__first2);
4270 template<
typename _ForwardIterator,
typename _Tp>
4271 _GLIBCXX20_CONSTEXPR
4273 replace(_ForwardIterator __first, _ForwardIterator __last,
4274 const _Tp& __old_value,
const _Tp& __new_value)
4277 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4279 __glibcxx_function_requires(_EqualOpConcept<
4281 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4283 __glibcxx_requires_valid_range(__first, __last);
4285 for (; __first != __last; ++__first)
4286 if (*__first == __old_value)
4287 *__first = __new_value;
4303 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4304 _GLIBCXX20_CONSTEXPR
4306 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4307 _Predicate __pred,
const _Tp& __new_value)
4310 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4312 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4314 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4316 __glibcxx_requires_valid_range(__first, __last);
4318 for (; __first != __last; ++__first)
4319 if (__pred(*__first))
4320 *__first = __new_value;
4335 template<
typename _ForwardIterator,
typename _Generator>
4336 _GLIBCXX20_CONSTEXPR
4338 generate(_ForwardIterator __first, _ForwardIterator __last,
4342 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4343 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4345 __glibcxx_requires_valid_range(__first, __last);
4347 for (; __first != __last; ++__first)
4368 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4369 _GLIBCXX20_CONSTEXPR
4371 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4374 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4376 __typeof__(__gen())>)
4378 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4379 for (_IntSize __niter = std::__size_to_integer(__n);
4380 __niter > 0; --__niter, (void) ++__first)
4403 template<
typename _InputIterator,
typename _OutputIterator>
4404 _GLIBCXX20_CONSTEXPR
4405 inline _OutputIterator
4406 unique_copy(_InputIterator __first, _InputIterator __last,
4407 _OutputIterator __result)
4410 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4411 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4413 __glibcxx_function_requires(_EqualityComparableConcept<
4415 __glibcxx_requires_valid_range(__first, __last);
4417 if (__first == __last)
4420 __gnu_cxx::__ops::__iter_equal_to_iter(),
4443 template<
typename _InputIterator,
typename _OutputIterator,
4444 typename _BinaryPredicate>
4445 _GLIBCXX20_CONSTEXPR
4446 inline _OutputIterator
4447 unique_copy(_InputIterator __first, _InputIterator __last,
4448 _OutputIterator __result,
4449 _BinaryPredicate __binary_pred)
4452 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4453 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4455 __glibcxx_requires_valid_range(__first, __last);
4457 if (__first == __last)
4460 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4465#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4482 template<
typename _RandomAccessIterator>
4483 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4485 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4488 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4489 _RandomAccessIterator>)
4490 __glibcxx_requires_valid_range(__first, __last);
4492 if (__first != __last)
4493 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4496 _RandomAccessIterator __j = __first
4497 + std::rand() % ((__i - __first) + 1);
4499 std::iter_swap(__i, __j);
4521 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4522 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4524 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4525#if __cplusplus >= 201103L
4526 _RandomNumberGenerator&& __rand)
4528 _RandomNumberGenerator& __rand)
4532 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4533 _RandomAccessIterator>)
4534 __glibcxx_requires_valid_range(__first, __last);
4536 if (__first == __last)
4538 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4540 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4542 std::iter_swap(__i, __j);
4563 template<
typename _ForwardIterator,
typename _Predicate>
4564 _GLIBCXX20_CONSTEXPR
4565 inline _ForwardIterator
4566 partition(_ForwardIterator __first, _ForwardIterator __last,
4570 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4572 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4574 __glibcxx_requires_valid_range(__first, __last);
4598 template<
typename _RandomAccessIterator>
4599 _GLIBCXX20_CONSTEXPR
4601 partial_sort(_RandomAccessIterator __first,
4602 _RandomAccessIterator __middle,
4603 _RandomAccessIterator __last)
4606 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4607 _RandomAccessIterator>)
4608 __glibcxx_function_requires(_LessThanComparableConcept<
4610 __glibcxx_requires_valid_range(__first, __middle);
4611 __glibcxx_requires_valid_range(__middle, __last);
4612 __glibcxx_requires_irreflexive(__first, __last);
4614 std::__partial_sort(__first, __middle, __last,
4615 __gnu_cxx::__ops::__iter_less_iter());
4637 template<
typename _RandomAccessIterator,
typename _Compare>
4638 _GLIBCXX20_CONSTEXPR
4640 partial_sort(_RandomAccessIterator __first,
4641 _RandomAccessIterator __middle,
4642 _RandomAccessIterator __last,
4646 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4647 _RandomAccessIterator>)
4648 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4651 __glibcxx_requires_valid_range(__first, __middle);
4652 __glibcxx_requires_valid_range(__middle, __last);
4653 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4655 std::__partial_sort(__first, __middle, __last,
4656 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4674 template<
typename _RandomAccessIterator>
4675 _GLIBCXX20_CONSTEXPR
4677 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4678 _RandomAccessIterator __last)
4681 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4682 _RandomAccessIterator>)
4683 __glibcxx_function_requires(_LessThanComparableConcept<
4685 __glibcxx_requires_valid_range(__first, __nth);
4686 __glibcxx_requires_valid_range(__nth, __last);
4687 __glibcxx_requires_irreflexive(__first, __last);
4689 if (__first == __last || __nth == __last)
4692 std::__introselect(__first, __nth, __last,
4694 __gnu_cxx::__ops::__iter_less_iter());
4714 template<
typename _RandomAccessIterator,
typename _Compare>
4715 _GLIBCXX20_CONSTEXPR
4717 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4718 _RandomAccessIterator __last, _Compare __comp)
4721 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4722 _RandomAccessIterator>)
4723 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4726 __glibcxx_requires_valid_range(__first, __nth);
4727 __glibcxx_requires_valid_range(__nth, __last);
4728 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4730 if (__first == __last || __nth == __last)
4733 std::__introselect(__first, __nth, __last,
4735 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4752 template<
typename _RandomAccessIterator>
4753 _GLIBCXX20_CONSTEXPR
4755 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4758 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4759 _RandomAccessIterator>)
4760 __glibcxx_function_requires(_LessThanComparableConcept<
4762 __glibcxx_requires_valid_range(__first, __last);
4763 __glibcxx_requires_irreflexive(__first, __last);
4765 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4783 template<
typename _RandomAccessIterator,
typename _Compare>
4784 _GLIBCXX20_CONSTEXPR
4786 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4790 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4791 _RandomAccessIterator>)
4792 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4795 __glibcxx_requires_valid_range(__first, __last);
4796 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4798 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4801 template<
typename _InputIterator1,
typename _InputIterator2,
4802 typename _OutputIterator,
typename _Compare>
4803 _GLIBCXX20_CONSTEXPR
4805 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4806 _InputIterator2 __first2, _InputIterator2 __last2,
4807 _OutputIterator __result, _Compare __comp)
4809 while (__first1 != __last1 && __first2 != __last2)
4811 if (__comp(__first2, __first1))
4813 *__result = *__first2;
4818 *__result = *__first1;
4823 return std::copy(__first2, __last2,
4824 std::copy(__first1, __last1, __result));
4846 template<
typename _InputIterator1,
typename _InputIterator2,
4847 typename _OutputIterator>
4848 _GLIBCXX20_CONSTEXPR
4849 inline _OutputIterator
4850 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4851 _InputIterator2 __first2, _InputIterator2 __last2,
4852 _OutputIterator __result)
4855 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4856 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4857 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4859 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4861 __glibcxx_function_requires(_LessThanOpConcept<
4864 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4865 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4866 __glibcxx_requires_irreflexive2(__first1, __last1);
4867 __glibcxx_requires_irreflexive2(__first2, __last2);
4869 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4870 __first2, __last2, __result,
4871 __gnu_cxx::__ops::__iter_less_iter());
4897 template<
typename _InputIterator1,
typename _InputIterator2,
4898 typename _OutputIterator,
typename _Compare>
4899 _GLIBCXX20_CONSTEXPR
4900 inline _OutputIterator
4901 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4902 _InputIterator2 __first2, _InputIterator2 __last2,
4903 _OutputIterator __result, _Compare __comp)
4906 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4907 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4908 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4910 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4912 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4915 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4916 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4917 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4918 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4920 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4921 __first2, __last2, __result,
4922 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4925 template<
typename _RandomAccessIterator,
typename _Compare>
4927 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4930 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4932 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4935 if (__first == __last)
4939 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4942 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
4944 if (__builtin_expect(__buf.requested_size() == __buf.size(),
true))
4945 std::__stable_sort_adaptive(__first,
4946 __first + _DistanceType(__buf.size()),
4947 __last, __buf.begin(), __comp);
4948 else if (__builtin_expect(__buf.begin() == 0,
false))
4951 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
4952 _DistanceType(__buf.size()), __comp);
4975 template<
typename _RandomAccessIterator>
4977 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4980 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4981 _RandomAccessIterator>)
4982 __glibcxx_function_requires(_LessThanComparableConcept<
4984 __glibcxx_requires_valid_range(__first, __last);
4985 __glibcxx_requires_irreflexive(__first, __last);
4987 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4988 __gnu_cxx::__ops::__iter_less_iter());
5009 template<
typename _RandomAccessIterator,
typename _Compare>
5011 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5015 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5016 _RandomAccessIterator>)
5017 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5020 __glibcxx_requires_valid_range(__first, __last);
5021 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5023 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5024 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5027 template<
typename _InputIterator1,
typename _InputIterator2,
5028 typename _OutputIterator,
5030 _GLIBCXX20_CONSTEXPR
5032 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5033 _InputIterator2 __first2, _InputIterator2 __last2,
5034 _OutputIterator __result, _Compare __comp)
5036 while (__first1 != __last1 && __first2 != __last2)
5038 if (__comp(__first1, __first2))
5040 *__result = *__first1;
5043 else if (__comp(__first2, __first1))
5045 *__result = *__first2;
5050 *__result = *__first1;
5056 return std::copy(__first2, __last2,
5057 std::copy(__first1, __last1, __result));
5079 template<
typename _InputIterator1,
typename _InputIterator2,
5080 typename _OutputIterator>
5081 _GLIBCXX20_CONSTEXPR
5082 inline _OutputIterator
5083 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5084 _InputIterator2 __first2, _InputIterator2 __last2,
5085 _OutputIterator __result)
5088 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5089 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5090 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5092 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5094 __glibcxx_function_requires(_LessThanOpConcept<
5097 __glibcxx_function_requires(_LessThanOpConcept<
5100 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5101 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5102 __glibcxx_requires_irreflexive2(__first1, __last1);
5103 __glibcxx_requires_irreflexive2(__first2, __last2);
5105 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5106 __first2, __last2, __result,
5107 __gnu_cxx::__ops::__iter_less_iter());
5130 template<
typename _InputIterator1,
typename _InputIterator2,
5131 typename _OutputIterator,
typename _Compare>
5132 _GLIBCXX20_CONSTEXPR
5133 inline _OutputIterator
5134 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5135 _InputIterator2 __first2, _InputIterator2 __last2,
5136 _OutputIterator __result, _Compare __comp)
5139 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5140 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5141 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5143 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5145 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5148 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5151 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5152 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5153 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5154 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5156 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5157 __first2, __last2, __result,
5158 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5161 template<
typename _InputIterator1,
typename _InputIterator2,
5162 typename _OutputIterator,
5164 _GLIBCXX20_CONSTEXPR
5166 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5167 _InputIterator2 __first2, _InputIterator2 __last2,
5168 _OutputIterator __result, _Compare __comp)
5170 while (__first1 != __last1 && __first2 != __last2)
5171 if (__comp(__first1, __first2))
5173 else if (__comp(__first2, __first1))
5177 *__result = *__first1;
5203 template<
typename _InputIterator1,
typename _InputIterator2,
5204 typename _OutputIterator>
5205 _GLIBCXX20_CONSTEXPR
5206 inline _OutputIterator
5207 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5208 _InputIterator2 __first2, _InputIterator2 __last2,
5209 _OutputIterator __result)
5212 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5213 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5214 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5216 __glibcxx_function_requires(_LessThanOpConcept<
5219 __glibcxx_function_requires(_LessThanOpConcept<
5222 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5223 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5224 __glibcxx_requires_irreflexive2(__first1, __last1);
5225 __glibcxx_requires_irreflexive2(__first2, __last2);
5227 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5228 __first2, __last2, __result,
5229 __gnu_cxx::__ops::__iter_less_iter());
5253 template<
typename _InputIterator1,
typename _InputIterator2,
5254 typename _OutputIterator,
typename _Compare>
5255 _GLIBCXX20_CONSTEXPR
5256 inline _OutputIterator
5257 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5258 _InputIterator2 __first2, _InputIterator2 __last2,
5259 _OutputIterator __result, _Compare __comp)
5262 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5263 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5264 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5266 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5269 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5272 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5273 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5274 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5275 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5277 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5278 __first2, __last2, __result,
5279 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5282 template<
typename _InputIterator1,
typename _InputIterator2,
5283 typename _OutputIterator,
5285 _GLIBCXX20_CONSTEXPR
5287 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5288 _InputIterator2 __first2, _InputIterator2 __last2,
5289 _OutputIterator __result, _Compare __comp)
5291 while (__first1 != __last1 && __first2 != __last2)
5292 if (__comp(__first1, __first2))
5294 *__result = *__first1;
5298 else if (__comp(__first2, __first1))
5305 return std::copy(__first1, __last1, __result);
5328 template<
typename _InputIterator1,
typename _InputIterator2,
5329 typename _OutputIterator>
5330 _GLIBCXX20_CONSTEXPR
5331 inline _OutputIterator
5332 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5333 _InputIterator2 __first2, _InputIterator2 __last2,
5334 _OutputIterator __result)
5337 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5338 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5339 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5341 __glibcxx_function_requires(_LessThanOpConcept<
5344 __glibcxx_function_requires(_LessThanOpConcept<
5347 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5348 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5349 __glibcxx_requires_irreflexive2(__first1, __last1);
5350 __glibcxx_requires_irreflexive2(__first2, __last2);
5352 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5353 __first2, __last2, __result,
5354 __gnu_cxx::__ops::__iter_less_iter());
5380 template<
typename _InputIterator1,
typename _InputIterator2,
5381 typename _OutputIterator,
typename _Compare>
5382 _GLIBCXX20_CONSTEXPR
5383 inline _OutputIterator
5384 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5385 _InputIterator2 __first2, _InputIterator2 __last2,
5386 _OutputIterator __result, _Compare __comp)
5389 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5390 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5391 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5393 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5396 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5399 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5400 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5401 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5402 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5404 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5405 __first2, __last2, __result,
5406 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5409 template<
typename _InputIterator1,
typename _InputIterator2,
5410 typename _OutputIterator,
5412 _GLIBCXX20_CONSTEXPR
5414 __set_symmetric_difference(_InputIterator1 __first1,
5415 _InputIterator1 __last1,
5416 _InputIterator2 __first2,
5417 _InputIterator2 __last2,
5418 _OutputIterator __result,
5421 while (__first1 != __last1 && __first2 != __last2)
5422 if (__comp(__first1, __first2))
5424 *__result = *__first1;
5428 else if (__comp(__first2, __first1))
5430 *__result = *__first2;
5439 return std::copy(__first2, __last2,
5440 std::copy(__first1, __last1, __result));
5461 template<
typename _InputIterator1,
typename _InputIterator2,
5462 typename _OutputIterator>
5463 _GLIBCXX20_CONSTEXPR
5464 inline _OutputIterator
5465 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5466 _InputIterator2 __first2, _InputIterator2 __last2,
5467 _OutputIterator __result)
5470 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5471 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5472 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5474 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5476 __glibcxx_function_requires(_LessThanOpConcept<
5479 __glibcxx_function_requires(_LessThanOpConcept<
5482 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5483 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5484 __glibcxx_requires_irreflexive2(__first1, __last1);
5485 __glibcxx_requires_irreflexive2(__first2, __last2);
5487 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5488 __first2, __last2, __result,
5489 __gnu_cxx::__ops::__iter_less_iter());
5513 template<
typename _InputIterator1,
typename _InputIterator2,
5514 typename _OutputIterator,
typename _Compare>
5515 _GLIBCXX20_CONSTEXPR
5516 inline _OutputIterator
5517 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5518 _InputIterator2 __first2, _InputIterator2 __last2,
5519 _OutputIterator __result,
5523 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5524 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5525 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5527 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5529 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5532 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5535 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5536 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5537 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5538 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5540 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5541 __first2, __last2, __result,
5542 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5545 template<
typename _ForwardIterator,
typename _Compare>
5546 _GLIBCXX14_CONSTEXPR
5548 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5551 if (__first == __last)
5553 _ForwardIterator __result = __first;
5554 while (++__first != __last)
5555 if (__comp(__first, __result))
5567 template<
typename _ForwardIterator>
5568 _GLIBCXX14_CONSTEXPR
5570 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5573 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5574 __glibcxx_function_requires(_LessThanComparableConcept<
5576 __glibcxx_requires_valid_range(__first, __last);
5577 __glibcxx_requires_irreflexive(__first, __last);
5579 return _GLIBCXX_STD_A::__min_element(__first, __last,
5580 __gnu_cxx::__ops::__iter_less_iter());
5592 template<
typename _ForwardIterator,
typename _Compare>
5593 _GLIBCXX14_CONSTEXPR
5594 inline _ForwardIterator
5595 min_element(_ForwardIterator __first, _ForwardIterator __last,
5599 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5600 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5603 __glibcxx_requires_valid_range(__first, __last);
5604 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5606 return _GLIBCXX_STD_A::__min_element(__first, __last,
5607 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5610 template<
typename _ForwardIterator,
typename _Compare>
5611 _GLIBCXX14_CONSTEXPR
5613 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5616 if (__first == __last)
return __first;
5617 _ForwardIterator __result = __first;
5618 while (++__first != __last)
5619 if (__comp(__result, __first))
5631 template<
typename _ForwardIterator>
5632 _GLIBCXX14_CONSTEXPR
5633 inline _ForwardIterator
5634 max_element(_ForwardIterator __first, _ForwardIterator __last)
5637 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5638 __glibcxx_function_requires(_LessThanComparableConcept<
5640 __glibcxx_requires_valid_range(__first, __last);
5641 __glibcxx_requires_irreflexive(__first, __last);
5643 return _GLIBCXX_STD_A::__max_element(__first, __last,
5644 __gnu_cxx::__ops::__iter_less_iter());
5656 template<
typename _ForwardIterator,
typename _Compare>
5657 _GLIBCXX14_CONSTEXPR
5658 inline _ForwardIterator
5659 max_element(_ForwardIterator __first, _ForwardIterator __last,
5663 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5664 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5667 __glibcxx_requires_valid_range(__first, __last);
5668 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5670 return _GLIBCXX_STD_A::__max_element(__first, __last,
5671 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5674#if __cplusplus >= 201103L
5676 template<
typename _Tp>
5677 _GLIBCXX14_CONSTEXPR
5679 min(initializer_list<_Tp> __l)
5681 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5682 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5683 __gnu_cxx::__ops::__iter_less_iter());
5686 template<
typename _Tp,
typename _Compare>
5687 _GLIBCXX14_CONSTEXPR
5689 min(initializer_list<_Tp> __l, _Compare __comp)
5691 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5692 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5693 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5696 template<
typename _Tp>
5697 _GLIBCXX14_CONSTEXPR
5699 max(initializer_list<_Tp> __l)
5701 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5702 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5703 __gnu_cxx::__ops::__iter_less_iter());
5706 template<
typename _Tp,
typename _Compare>
5707 _GLIBCXX14_CONSTEXPR
5709 max(initializer_list<_Tp> __l, _Compare __comp)
5711 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5712 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5713 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5717#if __cplusplus >= 201402L
5719 template<
typename _InputIterator,
typename _RandomAccessIterator,
5720 typename _Size,
typename _UniformRandomBitGenerator>
5721 _RandomAccessIterator
5724 _Size __n, _UniformRandomBitGenerator&& __g)
5727 using __param_type =
typename __distrib_type::param_type;
5728 __distrib_type __d{};
5729 _Size __sample_sz = 0;
5730 while (__first != __last && __sample_sz != __n)
5732 __out[__sample_sz++] = *__first;
5735 for (
auto __pop_sz = __sample_sz; __first != __last;
5736 ++__first, (void) ++__pop_sz)
5738 const auto __k = __d(__g, __param_type{0, __pop_sz});
5740 __out[__k] = *__first;
5742 return __out + __sample_sz;
5746 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5747 typename _Size,
typename _UniformRandomBitGenerator>
5749 __sample(_ForwardIterator __first, _ForwardIterator __last,
5751 _OutputIterator __out, _Cat,
5752 _Size __n, _UniformRandomBitGenerator&& __g)
5755 using __param_type =
typename __distrib_type::param_type;
5760 if (__first == __last)
5763 __distrib_type __d{};
5765 __n =
std::min(__n, __unsampled_sz);
5770 const __uc_type __urngrange = __g.max() - __g.min();
5771 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5775 while (__n != 0 && __unsampled_sz >= 2)
5781 if (__p.
first < __n)
5783 *__out++ = *__first;
5789 if (__n == 0)
break;
5794 *__out++ = *__first;
5804 for (; __n != 0; ++__first)
5805 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5807 *__out++ = *__first;
5814#ifdef __glibcxx_sample
5816 template<typename _PopulationIterator, typename _SampleIterator,
5817 typename _Distance,
typename _UniformRandomBitGenerator>
5819 sample(_PopulationIterator __first, _PopulationIterator __last,
5820 _SampleIterator __out, _Distance __n,
5821 _UniformRandomBitGenerator&& __g)
5823 using __pop_cat =
typename
5825 using __samp_cat =
typename
5829 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5831 "output range must use a RandomAccessIterator when input range"
5832 " does not meet the ForwardIterator requirements");
5835 "sample size must be an integer type");
5838 return _GLIBCXX_STD_A::
5839 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5840 std::forward<_UniformRandomBitGenerator>(__g));
5844_GLIBCXX_END_NAMESPACE_ALGO
5845_GLIBCXX_END_NAMESPACE_VERSION
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Compare __comp)
This is a helper function for the merge routines.
constexpr _InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
constexpr _OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
constexpr _Tp __lg(_Tp __n)
This is a helper function for the sort routines and for random.tcc.
constexpr _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
constexpr _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
constexpr _ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
constexpr void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)
Take a random sample from a population.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
constexpr void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
constexpr _ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
constexpr _InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
Traits class for iterators.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
Marking output iterators.
Forward iterators support a superset of input iterator operations.
Bidirectional iterators support a superset of forward iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...