65 #if __cplusplus >= 201103L
71 namespace std _GLIBCXX_VISIBILITY(default)
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator,
typename _Compare>
80 _Iterator __c, _Compare __comp)
86 else if (__comp(__a, __c))
91 else if (__comp(__a, __c))
93 else if (__comp(__b, __c))
100 template<
typename _InputIterator,
typename _Predicate>
102 inline _InputIterator
107 __gnu_cxx::__ops::__negate(__pred),
114 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
119 for (; __len; --__len, (void) ++__first)
120 if (!__pred(__first))
138 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
139 typename _BinaryPredicate>
142 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
143 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
144 _BinaryPredicate __predicate)
147 if (__first1 == __last1 || __first2 == __last2)
151 _ForwardIterator2 __p1(__first2);
152 if (++__p1 == __last2)
154 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
157 _ForwardIterator1 __current = __first1;
163 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
165 if (__first1 == __last1)
168 _ForwardIterator2 __p = __p1;
169 __current = __first1;
170 if (++__current == __last1)
173 while (__predicate(__current, __p))
175 if (++__p == __last2)
177 if (++__current == __last1)
190 template<
typename _ForwardIterator,
typename _Integer,
191 typename _UnaryPredicate>
195 _Integer __count, _UnaryPredicate __unary_pred,
199 while (__first != __last)
203 _ForwardIterator __i = __first;
205 while (__i != __last && __n != 1 && __unary_pred(__i))
223 template<
typename _RandomAccessIter,
typename _Integer,
224 typename _UnaryPredicate>
228 _Integer __count, _UnaryPredicate __unary_pred,
234 _DistanceType __tailSize = __last - __first;
235 _DistanceType __remainder = __count;
237 while (__remainder <= __tailSize)
239 __first += __remainder;
240 __tailSize -= __remainder;
243 _RandomAccessIter __backTrack = __first;
244 while (__unary_pred(--__backTrack))
246 if (--__remainder == 0)
247 return (__first - __count);
249 __remainder = __count + 1 - (__first - __backTrack);
254 template<
typename _ForwardIterator,
typename _Integer,
255 typename _UnaryPredicate>
258 __search_n(_ForwardIterator __first, _ForwardIterator __last,
260 _UnaryPredicate __unary_pred)
273 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
274 typename _BinaryPredicate>
277 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
278 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
279 forward_iterator_tag, forward_iterator_tag,
280 _BinaryPredicate __comp)
282 if (__first2 == __last2)
285 _ForwardIterator1 __result = __last1;
288 _ForwardIterator1 __new_result
289 = std::__search(__first1, __last1, __first2, __last2, __comp);
290 if (__new_result == __last1)
294 __result = __new_result;
295 __first1 = __new_result;
302 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
303 typename _BinaryPredicate>
305 _BidirectionalIterator1
306 __find_end(_BidirectionalIterator1 __first1,
307 _BidirectionalIterator1 __last1,
308 _BidirectionalIterator2 __first2,
309 _BidirectionalIterator2 __last2,
310 bidirectional_iterator_tag, bidirectional_iterator_tag,
311 _BinaryPredicate __comp)
314 __glibcxx_function_requires(_BidirectionalIteratorConcept<
315 _BidirectionalIterator1>)
316 __glibcxx_function_requires(_BidirectionalIteratorConcept<
317 _BidirectionalIterator2>)
319 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
320 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
322 _RevIterator1 __rlast1(__first1);
323 _RevIterator2 __rlast2(__first2);
324 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
325 _RevIterator2(__last2), __rlast2,
328 if (__rresult == __rlast1)
332 _BidirectionalIterator1 __result = __rresult.base();
364 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
366 inline _ForwardIterator1
367 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
368 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
371 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
372 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
373 __glibcxx_function_requires(_EqualOpConcept<
376 __glibcxx_requires_valid_range(__first1, __last1);
377 __glibcxx_requires_valid_range(__first2, __last2);
379 return std::__find_end(__first1, __last1, __first2, __last2,
382 __gnu_cxx::__ops::__iter_equal_to_iter());
413 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
414 typename _BinaryPredicate>
416 inline _ForwardIterator1
417 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
418 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
419 _BinaryPredicate __comp)
422 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
423 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
424 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
427 __glibcxx_requires_valid_range(__first1, __last1);
428 __glibcxx_requires_valid_range(__first2, __last2);
430 return std::__find_end(__first1, __last1, __first2, __last2,
433 __gnu_cxx::__ops::__iter_comp_iter(__comp));
436 #if __cplusplus >= 201103L
449 template<
typename _InputIterator,
typename _Predicate>
452 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
467 template<
typename _InputIterator,
typename _Predicate>
470 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
486 template<
typename _InputIterator,
typename _Predicate>
489 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
502 template<
typename _InputIterator,
typename _Predicate>
504 inline _InputIterator
505 find_if_not(_InputIterator __first, _InputIterator __last,
509 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
510 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
512 __glibcxx_requires_valid_range(__first, __last);
514 __gnu_cxx::__ops::__pred_iter(__pred));
527 template<
typename _InputIterator,
typename _Predicate>
530 is_partitioned(_InputIterator __first, _InputIterator __last,
534 if (__first == __last)
549 template<
typename _ForwardIterator,
typename _Predicate>
552 partition_point(_ForwardIterator __first, _ForwardIterator __last,
556 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
557 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
561 __glibcxx_requires_valid_range(__first, __last);
570 _DistanceType __half = __len >> 1;
571 _ForwardIterator __middle = __first;
573 if (__pred(*__middle))
577 __len = __len - __half - 1;
586 template<
typename _InputIterator,
typename _OutputIterator,
590 __remove_copy_if(_InputIterator __first, _InputIterator __last,
591 _OutputIterator __result, _Predicate __pred)
593 for (; __first != __last; ++__first)
594 if (!__pred(__first))
596 *__result = *__first;
616 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
618 inline _OutputIterator
619 remove_copy(_InputIterator __first, _InputIterator __last,
620 _OutputIterator __result,
const _Tp& __value)
623 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
624 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
626 __glibcxx_function_requires(_EqualOpConcept<
628 __glibcxx_requires_valid_range(__first, __last);
630 return std::__remove_copy_if(__first, __last, __result,
631 __gnu_cxx::__ops::__iter_equals_val(__value));
649 template<
typename _InputIterator,
typename _OutputIterator,
652 inline _OutputIterator
653 remove_copy_if(_InputIterator __first, _InputIterator __last,
654 _OutputIterator __result, _Predicate __pred)
657 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
658 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
660 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
662 __glibcxx_requires_valid_range(__first, __last);
664 return std::__remove_copy_if(__first, __last, __result,
665 __gnu_cxx::__ops::__pred_iter(__pred));
668 #if __cplusplus >= 201103L
684 template<
typename _InputIterator,
typename _OutputIterator,
688 copy_if(_InputIterator __first, _InputIterator __last,
689 _OutputIterator __result, _Predicate __pred)
692 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
693 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
695 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
697 __glibcxx_requires_valid_range(__first, __last);
699 for (; __first != __last; ++__first)
700 if (__pred(*__first))
702 *__result = *__first;
708 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
711 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result)
717 *__result = *__first;
728 template<
typename _CharT,
typename _Size>
729 __enable_if_t<__is_char<_CharT>::__value, _CharT*>
730 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT>>,
733 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
736 __copy_n(_InputIterator __first, _Size __n,
737 _OutputIterator __result, input_iterator_tag)
739 return std::__niter_wrap(__result,
740 __copy_n_a(__first, __n,
741 std::__niter_base(__result)));
744 template<
typename _RandomAccessIterator,
typename _Size,
745 typename _OutputIterator>
747 inline _OutputIterator
748 __copy_n(_RandomAccessIterator __first, _Size __n,
749 _OutputIterator __result, random_access_iterator_tag)
750 {
return std::copy(__first, __first + __n, __result); }
765 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
767 inline _OutputIterator
768 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
771 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
772 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
774 __glibcxx_requires_can_increment(__first, __n);
775 __glibcxx_requires_can_increment(__result, __n);
777 return std::__copy_n(__first, __n, __result,
796 template<
typename _InputIterator,
typename _OutputIterator1,
797 typename _OutputIterator2,
typename _Predicate>
799 pair<_OutputIterator1, _OutputIterator2>
800 partition_copy(_InputIterator __first, _InputIterator __last,
801 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
805 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
806 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
808 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
810 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
812 __glibcxx_requires_valid_range(__first, __last);
814 for (; __first != __last; ++__first)
815 if (__pred(*__first))
817 *__out_true = *__first;
822 *__out_false = *__first;
830 template<
typename _ForwardIterator,
typename _Predicate>
833 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
837 if (__first == __last)
839 _ForwardIterator __result = __first;
841 for (; __first != __last; ++__first)
842 if (!__pred(__first))
844 *__result = _GLIBCXX_MOVE(*__first);
867 template<
typename _ForwardIterator,
typename _Tp>
869 inline _ForwardIterator
870 remove(_ForwardIterator __first, _ForwardIterator __last,
874 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
876 __glibcxx_function_requires(_EqualOpConcept<
878 __glibcxx_requires_valid_range(__first, __last);
880 return std::__remove_if(__first, __last,
881 __gnu_cxx::__ops::__iter_equals_val(__value));
901 template<
typename _ForwardIterator,
typename _Predicate>
903 inline _ForwardIterator
904 remove_if(_ForwardIterator __first, _ForwardIterator __last,
908 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
910 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
912 __glibcxx_requires_valid_range(__first, __last);
914 return std::__remove_if(__first, __last,
915 __gnu_cxx::__ops::__pred_iter(__pred));
918 template<
typename _ForwardIterator,
typename _BinaryPredicate>
921 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
922 _BinaryPredicate __binary_pred)
924 if (__first == __last)
926 _ForwardIterator __next = __first;
927 while (++__next != __last)
929 if (__binary_pred(__first, __next))
936 template<
typename _ForwardIterator,
typename _BinaryPredicate>
939 __unique(_ForwardIterator __first, _ForwardIterator __last,
940 _BinaryPredicate __binary_pred)
943 __first = std::__adjacent_find(__first, __last, __binary_pred);
944 if (__first == __last)
948 _ForwardIterator __dest = __first;
950 while (++__first != __last)
951 if (!__binary_pred(__dest, __first))
952 *++__dest = _GLIBCXX_MOVE(*__first);
970 template<
typename _ForwardIterator>
972 inline _ForwardIterator
973 unique(_ForwardIterator __first, _ForwardIterator __last)
976 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
978 __glibcxx_function_requires(_EqualityComparableConcept<
980 __glibcxx_requires_valid_range(__first, __last);
982 return std::__unique(__first, __last,
983 __gnu_cxx::__ops::__iter_equal_to_iter());
1001 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1002 _GLIBCXX20_CONSTEXPR
1003 inline _ForwardIterator
1004 unique(_ForwardIterator __first, _ForwardIterator __last,
1005 _BinaryPredicate __binary_pred)
1008 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1010 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1013 __glibcxx_requires_valid_range(__first, __last);
1015 return std::__unique(__first, __last,
1016 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1025 template<
typename _ForwardIterator,
typename _OutputIterator,
1026 typename _BinaryPredicate>
1027 _GLIBCXX20_CONSTEXPR
1030 _OutputIterator __result, _BinaryPredicate __binary_pred,
1034 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1038 _ForwardIterator __next = __first;
1039 *__result = *__first;
1040 while (++__next != __last)
1041 if (!__binary_pred(__first, __next))
1044 *++__result = *__first;
1055 template<
typename _InputIterator,
typename _OutputIterator,
1056 typename _BinaryPredicate>
1057 _GLIBCXX20_CONSTEXPR
1060 _OutputIterator __result, _BinaryPredicate __binary_pred,
1064 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1069 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1071 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1072 *__result = __value;
1073 while (++__first != __last)
1074 if (!__rebound_pred(__first, __value))
1077 *++__result = __value;
1088 template<
typename _InputIterator,
typename _ForwardIterator,
1089 typename _BinaryPredicate>
1090 _GLIBCXX20_CONSTEXPR
1093 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1097 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1100 *__result = *__first;
1101 while (++__first != __last)
1102 if (!__binary_pred(__result, __first))
1103 *++__result = *__first;
1112 template<
typename _B
idirectionalIterator>
1113 _GLIBCXX20_CONSTEXPR
1115 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1119 if (__first == __last || __first == --__last)
1133 template<
typename _RandomAccessIterator>
1134 _GLIBCXX20_CONSTEXPR
1136 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1139 if (__first == __last)
1142 while (__first < __last)
1162 template<
typename _B
idirectionalIterator>
1163 _GLIBCXX20_CONSTEXPR
1165 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1168 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1169 _BidirectionalIterator>)
1170 __glibcxx_requires_valid_range(__first, __last);
1190 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1191 _GLIBCXX20_CONSTEXPR
1193 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1194 _OutputIterator __result)
1197 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1198 _BidirectionalIterator>)
1199 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1201 __glibcxx_requires_valid_range(__first, __last);
1203 while (__first != __last)
1206 *__result = *__last;
1216 template<
typename _Eucl
ideanRingElement>
1217 _GLIBCXX20_CONSTEXPR
1218 _EuclideanRingElement
1219 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1223 _EuclideanRingElement __t = __m % __n;
1230 inline namespace _V2
1234 template<
typename _ForwardIterator>
1235 _GLIBCXX20_CONSTEXPR
1238 _ForwardIterator __middle,
1239 _ForwardIterator __last,
1242 if (__first == __middle)
1244 else if (__last == __middle)
1247 _ForwardIterator __first2 = __middle;
1253 if (__first == __middle)
1254 __middle = __first2;
1256 while (__first2 != __last);
1258 _ForwardIterator __ret = __first;
1260 __first2 = __middle;
1262 while (__first2 != __last)
1267 if (__first == __middle)
1268 __middle = __first2;
1269 else if (__first2 == __last)
1270 __first2 = __middle;
1276 template<
typename _B
idirectionalIterator>
1277 _GLIBCXX20_CONSTEXPR
1278 _BidirectionalIterator
1280 _BidirectionalIterator __middle,
1281 _BidirectionalIterator __last,
1285 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1286 _BidirectionalIterator>)
1288 if (__first == __middle)
1290 else if (__last == __middle)
1296 while (__first != __middle && __middle != __last)
1302 if (__first == __middle)
1315 template<
typename _RandomAccessIterator>
1316 _GLIBCXX20_CONSTEXPR
1317 _RandomAccessIterator
1319 _RandomAccessIterator __middle,
1320 _RandomAccessIterator __last,
1324 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1325 _RandomAccessIterator>)
1327 if (__first == __middle)
1329 else if (__last == __middle)
1337 _Distance __n = __last - __first;
1338 _Distance __k = __middle - __first;
1340 if (__k == __n - __k)
1346 _RandomAccessIterator __p = __first;
1347 _RandomAccessIterator __ret = __first + (__last - __middle);
1351 if (__k < __n - __k)
1353 if (__is_pod(_ValueType) && __k == 1)
1355 _ValueType __t = _GLIBCXX_MOVE(*__p);
1356 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1357 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1360 _RandomAccessIterator __q = __p + __k;
1361 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1370 std::swap(__n, __k);
1376 if (__is_pod(_ValueType) && __k == 1)
1378 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1379 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1380 *__p = _GLIBCXX_MOVE(__t);
1383 _RandomAccessIterator __q = __p + __n;
1385 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1394 std::swap(__n, __k);
1422 template<
typename _ForwardIterator>
1423 _GLIBCXX20_CONSTEXPR
1424 inline _ForwardIterator
1425 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1426 _ForwardIterator __last)
1429 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1431 __glibcxx_requires_valid_range(__first, __middle);
1432 __glibcxx_requires_valid_range(__middle, __last);
1460 template<
typename _ForwardIterator,
typename _OutputIterator>
1461 _GLIBCXX20_CONSTEXPR
1462 inline _OutputIterator
1463 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1464 _ForwardIterator __last, _OutputIterator __result)
1467 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1468 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1470 __glibcxx_requires_valid_range(__first, __middle);
1471 __glibcxx_requires_valid_range(__middle, __last);
1473 return std::copy(__first, __middle,
1474 std::copy(__middle, __last, __result));
1478 template<
typename _ForwardIterator,
typename _Predicate>
1479 _GLIBCXX20_CONSTEXPR
1484 if (__first == __last)
1487 while (__pred(*__first))
1488 if (++__first == __last)
1491 _ForwardIterator __next = __first;
1493 while (++__next != __last)
1494 if (__pred(*__next))
1504 template<
typename _B
idirectionalIterator,
typename _Predicate>
1505 _GLIBCXX20_CONSTEXPR
1506 _BidirectionalIterator
1507 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1513 if (__first == __last)
1515 else if (__pred(*__first))
1521 if (__first == __last)
1523 else if (!
bool(__pred(*__last)))
1540 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1544 _ForwardIterator __last,
1545 _Predicate __pred, _Distance __len,
1547 _Distance __buffer_size)
1552 if (__len <= __buffer_size)
1554 _ForwardIterator __result1 = __first;
1555 _Pointer __result2 = __buffer;
1560 *__result2 = _GLIBCXX_MOVE(*__first);
1563 for (; __first != __last; ++__first)
1564 if (__pred(__first))
1566 *__result1 = _GLIBCXX_MOVE(*__first);
1571 *__result2 = _GLIBCXX_MOVE(*__first);
1575 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1579 _ForwardIterator __middle = __first;
1581 _ForwardIterator __left_split =
1583 __len / 2, __buffer,
1588 _Distance __right_len = __len - __len / 2;
1589 _ForwardIterator __right_split =
1596 __buffer, __buffer_size);
1598 return std::rotate(__left_split, __middle, __right_split);
1601 template<
typename _ForwardIterator,
typename _Predicate>
1603 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1608 if (__first == __last)
1611 typedef typename iterator_traits<_ForwardIterator>::value_type
1613 typedef typename iterator_traits<_ForwardIterator>::difference_type
1616 _Temporary_buffer<_ForwardIterator, _ValueType>
1620 _DistanceType(__buf.requested_size()),
1622 _DistanceType(__buf.size()));
1642 template<
typename _ForwardIterator,
typename _Predicate>
1643 inline _ForwardIterator
1644 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1648 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1650 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1652 __glibcxx_requires_valid_range(__first, __last);
1654 return std::__stable_partition(__first, __last,
1655 __gnu_cxx::__ops::__pred_iter(__pred));
1659 template<
typename _RandomAccessIterator,
typename _Compare>
1660 _GLIBCXX20_CONSTEXPR
1663 _RandomAccessIterator __middle,
1664 _RandomAccessIterator __last, _Compare __comp)
1666 std::__make_heap(__first, __middle, __comp);
1667 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1668 if (__comp(__i, __first))
1669 std::__pop_heap(__first, __middle, __i, __comp);
1674 template<
typename _InputIterator,
typename _RandomAccessIterator,
1676 _GLIBCXX20_CONSTEXPR
1677 _RandomAccessIterator
1678 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1679 _RandomAccessIterator __result_first,
1680 _RandomAccessIterator __result_last,
1683 typedef typename iterator_traits<_InputIterator>::value_type
1685 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1686 typedef typename _RItTraits::difference_type _DistanceType;
1688 if (__result_first == __result_last)
1689 return __result_last;
1690 _RandomAccessIterator __result_real_last = __result_first;
1691 while (__first != __last && __result_real_last != __result_last)
1693 *__result_real_last = *__first;
1694 ++__result_real_last;
1698 std::__make_heap(__result_first, __result_real_last, __comp);
1699 while (__first != __last)
1701 if (__comp(__first, __result_first))
1702 std::__adjust_heap(__result_first, _DistanceType(0),
1703 _DistanceType(__result_real_last
1705 _InputValueType(*__first), __comp);
1708 std::__sort_heap(__result_first, __result_real_last, __comp);
1709 return __result_real_last;
1730 template<
typename _InputIterator,
typename _RandomAccessIterator>
1731 _GLIBCXX20_CONSTEXPR
1732 inline _RandomAccessIterator
1733 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1734 _RandomAccessIterator __result_first,
1735 _RandomAccessIterator __result_last)
1737 #ifdef _GLIBCXX_CONCEPT_CHECKS
1745 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1746 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1748 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1750 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1751 __glibcxx_requires_valid_range(__first, __last);
1752 __glibcxx_requires_irreflexive(__first, __last);
1753 __glibcxx_requires_valid_range(__result_first, __result_last);
1755 return std::__partial_sort_copy(__first, __last,
1756 __result_first, __result_last,
1757 __gnu_cxx::__ops::__iter_less_iter());
1780 template<
typename _InputIterator,
typename _RandomAccessIterator,
1782 _GLIBCXX20_CONSTEXPR
1783 inline _RandomAccessIterator
1784 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1785 _RandomAccessIterator __result_first,
1786 _RandomAccessIterator __result_last,
1789 #ifdef _GLIBCXX_CONCEPT_CHECKS
1797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1799 _RandomAccessIterator>)
1800 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1802 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1803 _InputValueType, _OutputValueType>)
1804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1805 _OutputValueType, _OutputValueType>)
1806 __glibcxx_requires_valid_range(__first, __last);
1807 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1808 __glibcxx_requires_valid_range(__result_first, __result_last);
1810 return std::__partial_sort_copy(__first, __last,
1811 __result_first, __result_last,
1812 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1816 template<
typename _RandomAccessIterator,
typename _Compare>
1817 _GLIBCXX20_CONSTEXPR
1823 __val = _GLIBCXX_MOVE(*__last);
1824 _RandomAccessIterator __next = __last;
1826 while (__comp(__val, __next))
1828 *__last = _GLIBCXX_MOVE(*__next);
1832 *__last = _GLIBCXX_MOVE(__val);
1836 template<
typename _RandomAccessIterator,
typename _Compare>
1837 _GLIBCXX20_CONSTEXPR
1840 _RandomAccessIterator __last, _Compare __comp)
1842 if (__first == __last)
return;
1844 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1846 if (__comp(__i, __first))
1849 __val = _GLIBCXX_MOVE(*__i);
1850 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1851 *__first = _GLIBCXX_MOVE(__val);
1855 __gnu_cxx::__ops::__val_comp_iter(__comp));
1860 template<
typename _RandomAccessIterator,
typename _Compare>
1861 _GLIBCXX20_CONSTEXPR
1864 _RandomAccessIterator __last, _Compare __comp)
1866 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1868 __gnu_cxx::__ops::__val_comp_iter(__comp));
1875 enum { _S_threshold = 16 };
1878 template<
typename _RandomAccessIterator,
typename _Compare>
1879 _GLIBCXX20_CONSTEXPR
1882 _RandomAccessIterator __last, _Compare __comp)
1884 if (__last - __first >
int(_S_threshold))
1895 template<
typename _RandomAccessIterator,
typename _Compare>
1896 _GLIBCXX20_CONSTEXPR
1897 _RandomAccessIterator
1899 _RandomAccessIterator __last,
1900 _RandomAccessIterator __pivot, _Compare __comp)
1904 while (__comp(__first, __pivot))
1907 while (__comp(__pivot, __last))
1909 if (!(__first < __last))
1917 template<
typename _RandomAccessIterator,
typename _Compare>
1918 _GLIBCXX20_CONSTEXPR
1919 inline _RandomAccessIterator
1921 _RandomAccessIterator __last, _Compare __comp)
1923 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1929 template<
typename _RandomAccessIterator,
typename _Compare>
1930 _GLIBCXX20_CONSTEXPR
1932 __partial_sort(_RandomAccessIterator __first,
1933 _RandomAccessIterator __middle,
1934 _RandomAccessIterator __last,
1938 std::__sort_heap(__first, __middle, __comp);
1942 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1943 _GLIBCXX20_CONSTEXPR
1946 _RandomAccessIterator __last,
1947 _Size __depth_limit, _Compare __comp)
1949 while (__last - __first >
int(_S_threshold))
1951 if (__depth_limit == 0)
1953 std::__partial_sort(__first, __last, __last, __comp);
1957 _RandomAccessIterator __cut =
1966 template<
typename _RandomAccessIterator,
typename _Compare>
1967 _GLIBCXX20_CONSTEXPR
1969 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1972 if (__first != __last)
1981 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1982 _GLIBCXX20_CONSTEXPR
1984 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1985 _RandomAccessIterator __last, _Size __depth_limit,
1988 while (__last - __first > 3)
1990 if (__depth_limit == 0)
1998 _RandomAccessIterator __cut =
2028 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2029 _GLIBCXX20_CONSTEXPR
2030 inline _ForwardIterator
2031 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2032 const _Tp& __val, _Compare __comp)
2035 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2036 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2038 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2041 return std::__lower_bound(__first, __last, __val,
2042 __gnu_cxx::__ops::__iter_comp_val(__comp));
2045 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2046 _GLIBCXX20_CONSTEXPR
2048 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2049 const _Tp& __val, _Compare __comp)
2051 typedef typename iterator_traits<_ForwardIterator>::difference_type
2058 _DistanceType __half = __len >> 1;
2059 _ForwardIterator __middle = __first;
2061 if (__comp(__val, __middle))
2067 __len = __len - __half - 1;
2084 template<
typename _ForwardIterator,
typename _Tp>
2085 _GLIBCXX20_CONSTEXPR
2086 inline _ForwardIterator
2087 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2091 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2092 __glibcxx_function_requires(_LessThanOpConcept<
2094 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2096 return std::__upper_bound(__first, __last, __val,
2097 __gnu_cxx::__ops::__val_less_iter());
2115 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2116 _GLIBCXX20_CONSTEXPR
2117 inline _ForwardIterator
2118 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2119 const _Tp& __val, _Compare __comp)
2122 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2123 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2125 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2128 return std::__upper_bound(__first, __last, __val,
2129 __gnu_cxx::__ops::__val_comp_iter(__comp));
2132 template<
typename _ForwardIterator,
typename _Tp,
2133 typename _CompareItTp,
typename _CompareTpIt>
2134 _GLIBCXX20_CONSTEXPR
2135 pair<_ForwardIterator, _ForwardIterator>
2136 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2138 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2140 typedef typename iterator_traits<_ForwardIterator>::difference_type
2147 _DistanceType __half = __len >> 1;
2148 _ForwardIterator __middle = __first;
2150 if (__comp_it_val(__middle, __val))
2154 __len = __len - __half - 1;
2156 else if (__comp_val_it(__val, __middle))
2160 _ForwardIterator __left
2161 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2163 _ForwardIterator __right
2164 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2165 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2168 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2188 template<
typename _ForwardIterator,
typename _Tp>
2189 _GLIBCXX20_CONSTEXPR
2190 inline pair<_ForwardIterator, _ForwardIterator>
2191 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2195 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2196 __glibcxx_function_requires(_LessThanOpConcept<
2198 __glibcxx_function_requires(_LessThanOpConcept<
2200 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2201 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2203 return std::__equal_range(__first, __last, __val,
2204 __gnu_cxx::__ops::__iter_less_val(),
2205 __gnu_cxx::__ops::__val_less_iter());
2225 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2226 _GLIBCXX20_CONSTEXPR
2227 inline pair<_ForwardIterator, _ForwardIterator>
2228 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2229 const _Tp& __val, _Compare __comp)
2232 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2235 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2237 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2239 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2242 return std::__equal_range(__first, __last, __val,
2243 __gnu_cxx::__ops::__iter_comp_val(__comp),
2244 __gnu_cxx::__ops::__val_comp_iter(__comp));
2259 template<
typename _ForwardIterator,
typename _Tp>
2260 _GLIBCXX20_CONSTEXPR
2262 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2266 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2267 __glibcxx_function_requires(_LessThanOpConcept<
2269 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2270 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2272 _ForwardIterator __i
2273 = std::__lower_bound(__first, __last, __val,
2274 __gnu_cxx::__ops::__iter_less_val());
2275 return __i != __last && !(__val < *__i);
2293 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2294 _GLIBCXX20_CONSTEXPR
2296 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2297 const _Tp& __val, _Compare __comp)
2300 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2301 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2303 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2305 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2308 _ForwardIterator __i
2309 = std::__lower_bound(__first, __last, __val,
2310 __gnu_cxx::__ops::__iter_comp_val(__comp));
2311 return __i != __last && !bool(__comp(__val, *__i));
2317 template<
typename _InputIterator1,
typename _InputIterator2,
2318 typename _OutputIterator,
typename _Compare>
2321 _InputIterator2 __first2, _InputIterator2 __last2,
2322 _OutputIterator __result, _Compare __comp)
2324 while (__first1 != __last1 && __first2 != __last2)
2326 if (__comp(__first2, __first1))
2328 *__result = _GLIBCXX_MOVE(*__first2);
2333 *__result = _GLIBCXX_MOVE(*__first1);
2338 if (__first1 != __last1)
2339 _GLIBCXX_MOVE3(__first1, __last1, __result);
2343 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2344 typename _BidirectionalIterator3,
typename _Compare>
2347 _BidirectionalIterator1 __last1,
2348 _BidirectionalIterator2 __first2,
2349 _BidirectionalIterator2 __last2,
2350 _BidirectionalIterator3 __result,
2353 if (__first1 == __last1)
2355 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2358 else if (__first2 == __last2)
2365 if (__comp(__last2, __last1))
2367 *--__result = _GLIBCXX_MOVE(*__last1);
2368 if (__first1 == __last1)
2370 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2377 *--__result = _GLIBCXX_MOVE(*__last2);
2378 if (__first2 == __last2)
2386 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2388 _BidirectionalIterator1
2390 _BidirectionalIterator1 __middle,
2391 _BidirectionalIterator1 __last,
2392 _Distance __len1, _Distance __len2,
2393 _BidirectionalIterator2 __buffer,
2394 _Distance __buffer_size)
2396 _BidirectionalIterator2 __buffer_end;
2397 if (__len1 > __len2 && __len2 <= __buffer_size)
2401 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2402 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2403 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2408 else if (__len1 <= __buffer_size)
2412 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2413 _GLIBCXX_MOVE3(__middle, __last, __first);
2414 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2420 return std::rotate(__first, __middle, __last);
2424 template<
typename _BidirectionalIterator,
typename _Distance,
2425 typename _Pointer,
typename _Compare>
2428 _BidirectionalIterator __middle,
2429 _BidirectionalIterator __last,
2430 _Distance __len1, _Distance __len2,
2431 _Pointer __buffer, _Distance __buffer_size,
2434 if (__len1 <= __len2 && __len1 <= __buffer_size)
2436 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2440 else if (__len2 <= __buffer_size)
2442 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2444 __buffer_end, __last, __comp);
2448 _BidirectionalIterator __first_cut = __first;
2449 _BidirectionalIterator __second_cut = __middle;
2450 _Distance __len11 = 0;
2451 _Distance __len22 = 0;
2452 if (__len1 > __len2)
2454 __len11 = __len1 / 2;
2457 = std::__lower_bound(__middle, __last, *__first_cut,
2458 __gnu_cxx::__ops::__iter_comp_val(__comp));
2463 __len22 = __len2 / 2;
2466 = std::__upper_bound(__first, __middle, *__second_cut,
2467 __gnu_cxx::__ops::__val_comp_iter(__comp));
2471 _BidirectionalIterator __new_middle
2473 __len1 - __len11, __len22, __buffer,
2476 __len22, __buffer, __buffer_size, __comp);
2479 __len2 - __len22, __buffer,
2480 __buffer_size, __comp);
2485 template<
typename _BidirectionalIterator,
typename _Distance,
2489 _BidirectionalIterator __middle,
2490 _BidirectionalIterator __last,
2491 _Distance __len1, _Distance __len2,
2494 if (__len1 == 0 || __len2 == 0)
2497 if (__len1 + __len2 == 2)
2499 if (__comp(__middle, __first))
2504 _BidirectionalIterator __first_cut = __first;
2505 _BidirectionalIterator __second_cut = __middle;
2506 _Distance __len11 = 0;
2507 _Distance __len22 = 0;
2508 if (__len1 > __len2)
2510 __len11 = __len1 / 2;
2513 = std::__lower_bound(__middle, __last, *__first_cut,
2514 __gnu_cxx::__ops::__iter_comp_val(__comp));
2519 __len22 = __len2 / 2;
2522 = std::__upper_bound(__first, __middle, *__second_cut,
2523 __gnu_cxx::__ops::__val_comp_iter(__comp));
2527 _BidirectionalIterator __new_middle
2528 = std::rotate(__first_cut, __middle, __second_cut);
2530 __len11, __len22, __comp);
2532 __len1 - __len11, __len2 - __len22, __comp);
2535 template<
typename _B
idirectionalIterator,
typename _Compare>
2537 __inplace_merge(_BidirectionalIterator __first,
2538 _BidirectionalIterator __middle,
2539 _BidirectionalIterator __last,
2542 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2544 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2547 if (__first == __middle || __middle == __last)
2550 const _DistanceType __len1 =
std::distance(__first, __middle);
2551 const _DistanceType __len2 =
std::distance(__middle, __last);
2553 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2554 _TmpBuf __buf(__first, __len1 + __len2);
2556 if (__buf.begin() == 0)
2558 (__first, __middle, __last, __len1, __len2, __comp);
2561 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2562 _DistanceType(__buf.size()), __comp);
2583 template<
typename _B
idirectionalIterator>
2585 inplace_merge(_BidirectionalIterator __first,
2586 _BidirectionalIterator __middle,
2587 _BidirectionalIterator __last)
2590 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2591 _BidirectionalIterator>)
2592 __glibcxx_function_requires(_LessThanComparableConcept<
2594 __glibcxx_requires_sorted(__first, __middle);
2595 __glibcxx_requires_sorted(__middle, __last);
2596 __glibcxx_requires_irreflexive(__first, __last);
2598 std::__inplace_merge(__first, __middle, __last,
2599 __gnu_cxx::__ops::__iter_less_iter());
2624 template<
typename _B
idirectionalIterator,
typename _Compare>
2626 inplace_merge(_BidirectionalIterator __first,
2627 _BidirectionalIterator __middle,
2628 _BidirectionalIterator __last,
2632 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2633 _BidirectionalIterator>)
2634 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2637 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2638 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2639 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2641 std::__inplace_merge(__first, __middle, __last,
2642 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2647 template<
typename _InputIterator,
typename _OutputIterator,
2651 _InputIterator __first2, _InputIterator __last2,
2652 _OutputIterator __result, _Compare __comp)
2654 while (__first1 != __last1 && __first2 != __last2)
2656 if (__comp(__first2, __first1))
2658 *__result = _GLIBCXX_MOVE(*__first2);
2663 *__result = _GLIBCXX_MOVE(*__first1);
2668 return _GLIBCXX_MOVE3(__first2, __last2,
2669 _GLIBCXX_MOVE3(__first1, __last1,
2673 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2674 typename _Distance,
typename _Compare>
2676 __merge_sort_loop(_RandomAccessIterator1 __first,
2677 _RandomAccessIterator1 __last,
2678 _RandomAccessIterator2 __result, _Distance __step_size,
2681 const _Distance __two_step = 2 * __step_size;
2683 while (__last - __first >= __two_step)
2686 __first + __step_size,
2687 __first + __two_step,
2689 __first += __two_step;
2691 __step_size =
std::min(_Distance(__last - __first), __step_size);
2694 __first + __step_size, __last, __result, __comp);
2697 template<
typename _RandomAccessIterator,
typename _Distance,
2699 _GLIBCXX20_CONSTEXPR
2701 __chunk_insertion_sort(_RandomAccessIterator __first,
2702 _RandomAccessIterator __last,
2703 _Distance __chunk_size, _Compare __comp)
2705 while (__last - __first >= __chunk_size)
2708 __first += __chunk_size;
2713 enum { _S_chunk_size = 7 };
2715 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2717 __merge_sort_with_buffer(_RandomAccessIterator __first,
2718 _RandomAccessIterator __last,
2719 _Pointer __buffer, _Compare __comp)
2721 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2724 const _Distance __len = __last - __first;
2725 const _Pointer __buffer_last = __buffer + __len;
2727 _Distance __step_size = _S_chunk_size;
2728 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2730 while (__step_size < __len)
2732 std::__merge_sort_loop(__first, __last, __buffer,
2733 __step_size, __comp);
2735 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2736 __step_size, __comp);
2741 template<
typename _RandomAccessIterator,
typename _Pointer,
2742 typename _Distance,
typename _Compare>
2744 __stable_sort_adaptive(_RandomAccessIterator __first,
2745 _RandomAccessIterator __last,
2746 _Pointer __buffer, _Distance __buffer_size,
2749 const _Distance __len = (__last - __first + 1) / 2;
2750 const _RandomAccessIterator __middle = __first + __len;
2751 if (__len > __buffer_size)
2753 std::__stable_sort_adaptive(__first, __middle, __buffer,
2754 __buffer_size, __comp);
2755 std::__stable_sort_adaptive(__middle, __last, __buffer,
2756 __buffer_size, __comp);
2760 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2761 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2764 _Distance(__middle - __first),
2765 _Distance(__last - __middle),
2766 __buffer, __buffer_size,
2771 template<
typename _RandomAccessIterator,
typename _Compare>
2774 _RandomAccessIterator __last, _Compare __comp)
2776 if (__last - __first < 15)
2781 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2797 template<
typename _InputIterator1,
typename _InputIterator2,
2799 _GLIBCXX20_CONSTEXPR
2801 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2802 _InputIterator2 __first2, _InputIterator2 __last2,
2805 while (__first1 != __last1 && __first2 != __last2)
2806 if (__comp(__first2, __first1))
2808 else if (__comp(__first1, __first2))
2816 return __first2 == __last2;
2837 template<
typename _InputIterator1,
typename _InputIterator2>
2838 _GLIBCXX20_CONSTEXPR
2840 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2841 _InputIterator2 __first2, _InputIterator2 __last2)
2844 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2845 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2846 __glibcxx_function_requires(_LessThanOpConcept<
2849 __glibcxx_function_requires(_LessThanOpConcept<
2852 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2853 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2854 __glibcxx_requires_irreflexive2(__first1, __last1);
2855 __glibcxx_requires_irreflexive2(__first2, __last2);
2857 return std::__includes(__first1, __last1, __first2, __last2,
2858 __gnu_cxx::__ops::__iter_less_iter());
2882 template<
typename _InputIterator1,
typename _InputIterator2,
2884 _GLIBCXX20_CONSTEXPR
2886 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2887 _InputIterator2 __first2, _InputIterator2 __last2,
2891 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2892 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2893 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2896 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2899 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2900 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2901 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2902 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2904 return std::__includes(__first1, __last1, __first2, __last2,
2905 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2918 template<
typename _B
idirectionalIterator,
typename _Compare>
2919 _GLIBCXX20_CONSTEXPR
2921 __next_permutation(_BidirectionalIterator __first,
2922 _BidirectionalIterator __last, _Compare __comp)
2924 if (__first == __last)
2926 _BidirectionalIterator __i = __first;
2935 _BidirectionalIterator __ii = __i;
2937 if (__comp(__i, __ii))
2939 _BidirectionalIterator __j = __last;
2940 while (!__comp(__i, --__j))
2968 template<
typename _B
idirectionalIterator>
2969 _GLIBCXX20_CONSTEXPR
2971 next_permutation(_BidirectionalIterator __first,
2972 _BidirectionalIterator __last)
2975 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2976 _BidirectionalIterator>)
2977 __glibcxx_function_requires(_LessThanComparableConcept<
2979 __glibcxx_requires_valid_range(__first, __last);
2980 __glibcxx_requires_irreflexive(__first, __last);
2982 return std::__next_permutation
2983 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
3001 template<
typename _B
idirectionalIterator,
typename _Compare>
3002 _GLIBCXX20_CONSTEXPR
3004 next_permutation(_BidirectionalIterator __first,
3005 _BidirectionalIterator __last, _Compare __comp)
3008 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3009 _BidirectionalIterator>)
3010 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3013 __glibcxx_requires_valid_range(__first, __last);
3014 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3016 return std::__next_permutation
3017 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3020 template<
typename _B
idirectionalIterator,
typename _Compare>
3021 _GLIBCXX20_CONSTEXPR
3023 __prev_permutation(_BidirectionalIterator __first,
3024 _BidirectionalIterator __last, _Compare __comp)
3026 if (__first == __last)
3028 _BidirectionalIterator __i = __first;
3037 _BidirectionalIterator __ii = __i;
3039 if (__comp(__ii, __i))
3041 _BidirectionalIterator __j = __last;
3042 while (!__comp(--__j, __i))
3071 template<
typename _B
idirectionalIterator>
3072 _GLIBCXX20_CONSTEXPR
3074 prev_permutation(_BidirectionalIterator __first,
3075 _BidirectionalIterator __last)
3078 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3079 _BidirectionalIterator>)
3080 __glibcxx_function_requires(_LessThanComparableConcept<
3082 __glibcxx_requires_valid_range(__first, __last);
3083 __glibcxx_requires_irreflexive(__first, __last);
3085 return std::__prev_permutation(__first, __last,
3086 __gnu_cxx::__ops::__iter_less_iter());
3104 template<
typename _B
idirectionalIterator,
typename _Compare>
3105 _GLIBCXX20_CONSTEXPR
3107 prev_permutation(_BidirectionalIterator __first,
3108 _BidirectionalIterator __last, _Compare __comp)
3111 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3112 _BidirectionalIterator>)
3113 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3116 __glibcxx_requires_valid_range(__first, __last);
3117 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3119 return std::__prev_permutation(__first, __last,
3120 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3126 template<
typename _InputIterator,
typename _OutputIterator,
3127 typename _Predicate,
typename _Tp>
3128 _GLIBCXX20_CONSTEXPR
3130 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3131 _OutputIterator __result,
3132 _Predicate __pred,
const _Tp& __new_value)
3134 for (; __first != __last; ++__first, (void)++__result)
3135 if (__pred(__first))
3136 *__result = __new_value;
3138 *__result = *__first;
3156 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3157 _GLIBCXX20_CONSTEXPR
3158 inline _OutputIterator
3159 replace_copy(_InputIterator __first, _InputIterator __last,
3160 _OutputIterator __result,
3161 const _Tp& __old_value,
const _Tp& __new_value)
3164 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3165 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3167 __glibcxx_function_requires(_EqualOpConcept<
3169 __glibcxx_requires_valid_range(__first, __last);
3171 return std::__replace_copy_if(__first, __last, __result,
3172 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3191 template<
typename _InputIterator,
typename _OutputIterator,
3192 typename _Predicate,
typename _Tp>
3193 _GLIBCXX20_CONSTEXPR
3194 inline _OutputIterator
3195 replace_copy_if(_InputIterator __first, _InputIterator __last,
3196 _OutputIterator __result,
3197 _Predicate __pred,
const _Tp& __new_value)
3200 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3201 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3203 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3205 __glibcxx_requires_valid_range(__first, __last);
3207 return std::__replace_copy_if(__first, __last, __result,
3208 __gnu_cxx::__ops::__pred_iter(__pred),
3212 #if __cplusplus >= 201103L
3220 template<
typename _ForwardIterator>
3221 _GLIBCXX20_CONSTEXPR
3223 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3235 template<
typename _ForwardIterator,
typename _Compare>
3236 _GLIBCXX20_CONSTEXPR
3238 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3242 template<
typename _ForwardIterator,
typename _Compare>
3243 _GLIBCXX20_CONSTEXPR
3245 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3248 if (__first == __last)
3251 _ForwardIterator __next = __first;
3252 for (++__next; __next != __last; __first = __next, (void)++__next)
3253 if (__comp(__next, __first))
3266 template<
typename _ForwardIterator>
3267 _GLIBCXX20_CONSTEXPR
3268 inline _ForwardIterator
3269 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3272 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3273 __glibcxx_function_requires(_LessThanComparableConcept<
3275 __glibcxx_requires_valid_range(__first, __last);
3276 __glibcxx_requires_irreflexive(__first, __last);
3278 return std::__is_sorted_until(__first, __last,
3279 __gnu_cxx::__ops::__iter_less_iter());
3291 template<
typename _ForwardIterator,
typename _Compare>
3292 _GLIBCXX20_CONSTEXPR
3293 inline _ForwardIterator
3294 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3298 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3299 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3302 __glibcxx_requires_valid_range(__first, __last);
3303 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3305 return std::__is_sorted_until(__first, __last,
3306 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3317 template<
typename _Tp>
3318 _GLIBCXX14_CONSTEXPR
3319 inline pair<const _Tp&, const _Tp&>
3323 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3325 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3338 template<
typename _Tp,
typename _Compare>
3339 _GLIBCXX14_CONSTEXPR
3340 inline pair<const _Tp&, const _Tp&>
3341 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3347 template<
typename _ForwardIterator,
typename _Compare>
3348 _GLIBCXX14_CONSTEXPR
3349 pair<_ForwardIterator, _ForwardIterator>
3350 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3353 _ForwardIterator __next = __first;
3354 if (__first == __last
3355 || ++__next == __last)
3356 return std::make_pair(__first, __first);
3358 _ForwardIterator __min{}, __max{};
3359 if (__comp(__next, __first))
3373 while (__first != __last)
3376 if (++__next == __last)
3378 if (__comp(__first, __min))
3380 else if (!__comp(__first, __max))
3385 if (__comp(__next, __first))
3387 if (__comp(__next, __min))
3389 if (!__comp(__first, __max))
3394 if (__comp(__first, __min))
3396 if (!__comp(__next, __max))
3404 return std::make_pair(__min, __max);
3418 template<
typename _ForwardIterator>
3419 _GLIBCXX14_CONSTEXPR
3420 inline pair<_ForwardIterator, _ForwardIterator>
3421 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3424 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3425 __glibcxx_function_requires(_LessThanComparableConcept<
3427 __glibcxx_requires_valid_range(__first, __last);
3428 __glibcxx_requires_irreflexive(__first, __last);
3430 return std::__minmax_element(__first, __last,
3431 __gnu_cxx::__ops::__iter_less_iter());
3446 template<
typename _ForwardIterator,
typename _Compare>
3447 _GLIBCXX14_CONSTEXPR
3448 inline pair<_ForwardIterator, _ForwardIterator>
3449 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3453 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3454 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3457 __glibcxx_requires_valid_range(__first, __last);
3458 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3460 return std::__minmax_element(__first, __last,
3461 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3465 template<
typename _Tp>
3466 _GLIBCXX14_CONSTEXPR
3468 min(initializer_list<_Tp> __l)
3469 {
return *std::min_element(__l.begin(), __l.end()); }
3471 template<
typename _Tp,
typename _Compare>
3472 _GLIBCXX14_CONSTEXPR
3474 min(initializer_list<_Tp> __l, _Compare __comp)
3477 template<
typename _Tp>
3478 _GLIBCXX14_CONSTEXPR
3480 max(initializer_list<_Tp> __l)
3483 template<
typename _Tp,
typename _Compare>
3484 _GLIBCXX14_CONSTEXPR
3486 max(initializer_list<_Tp> __l, _Compare __comp)
3489 template<
typename _Tp>
3490 _GLIBCXX14_CONSTEXPR
3491 inline pair<_Tp, _Tp>
3492 minmax(initializer_list<_Tp> __l)
3494 pair<const _Tp*, const _Tp*> __p =
3496 return std::make_pair(*__p.first, *__p.second);
3499 template<
typename _Tp,
typename _Compare>
3500 _GLIBCXX14_CONSTEXPR
3501 inline pair<_Tp, _Tp>
3502 minmax(initializer_list<_Tp> __l, _Compare __comp)
3504 pair<const _Tp*, const _Tp*> __p =
3506 return std::make_pair(*__p.first, *__p.second);
3523 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3524 typename _BinaryPredicate>
3525 _GLIBCXX20_CONSTEXPR
3527 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3528 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3531 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3532 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3533 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3536 __glibcxx_requires_valid_range(__first1, __last1);
3538 return std::__is_permutation(__first1, __last1, __first2,
3539 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3542 #if __cplusplus > 201103L
3543 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3544 typename _BinaryPredicate>
3545 _GLIBCXX20_CONSTEXPR
3547 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3548 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3549 _BinaryPredicate __pred)
3552 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3554 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3555 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3556 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3557 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3568 for (; __first1 != __last1 && __first2 != __last2;
3569 ++__first1, (void)++__first2)
3570 if (!__pred(__first1, __first2))
3575 if (__first1 == __last1)
3582 if (__d1 == 0 && __d2 == 0)
3588 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3591 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3594 auto __matches = std::__count_if(__first2, __last2,
3595 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3597 || std::__count_if(__scan, __last1,
3598 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3618 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3619 _GLIBCXX20_CONSTEXPR
3621 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3622 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3624 __glibcxx_requires_valid_range(__first1, __last1);
3625 __glibcxx_requires_valid_range(__first2, __last2);
3628 std::__is_permutation(__first1, __last1, __first2, __last2,
3629 __gnu_cxx::__ops::__iter_equal_to_iter());
3646 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3647 typename _BinaryPredicate>
3648 _GLIBCXX20_CONSTEXPR
3650 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3651 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3652 _BinaryPredicate __pred)
3654 __glibcxx_requires_valid_range(__first1, __last1);
3655 __glibcxx_requires_valid_range(__first2, __last2);
3657 return std::__is_permutation(__first1, __last1, __first2, __last2,
3658 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3661 #if __cplusplus > 201402L
3663 #define __cpp_lib_clamp 201603
3673 template<
typename _Tp>
3674 constexpr
const _Tp&
3675 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3677 __glibcxx_assert(!(__hi < __lo));
3678 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3691 template<
typename _Tp,
typename _Compare>
3692 constexpr
const _Tp&
3693 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3695 __glibcxx_assert(!__comp(__hi, __lo));
3696 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3701 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
3723 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3724 pair<_IntType, _IntType>
3726 _UniformRandomBitGenerator&& __g)
3730 return std::make_pair(__x / __b1, __x % __b1);
3745 template<
typename _RandomAccessIterator,
3746 typename _UniformRandomNumberGenerator>
3748 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3749 _UniformRandomNumberGenerator&& __g)
3752 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3753 _RandomAccessIterator>)
3754 __glibcxx_requires_valid_range(__first, __last);
3756 if (__first == __last)
3762 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3764 typedef typename __distr_type::param_type __p_type;
3766 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3771 const __uc_type __urngrange = __g.max() - __g.min();
3772 const __uc_type __urange = __uc_type(__last - __first);
3774 if (__urngrange / __urange >= __urange)
3777 _RandomAccessIterator __i = __first + 1;
3783 if ((__urange % 2) == 0)
3785 __distr_type __d{0, 1};
3793 while (__i != __last)
3795 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3809 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3810 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3816 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3830 template<
typename _InputIterator,
typename _Function>
3831 _GLIBCXX20_CONSTEXPR
3833 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3836 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3837 __glibcxx_requires_valid_range(__first, __last);
3838 for (; __first != __last; ++__first)
3843 #if __cplusplus >= 201703L
3856 template<
typename _InputIterator,
typename _Size,
typename _Function>
3858 for_each_n(_InputIterator __first, _Size __n, _Function __f)
3860 auto __n2 = std::__size_to_integer(__n);
3861 using _Cat =
typename iterator_traits<_InputIterator>::iterator_category;
3862 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3866 auto __last = __first + __n2;
3867 std::for_each(__first, __last,
std::move(__f));
3891 template<
typename _InputIterator,
typename _Tp>
3892 _GLIBCXX20_CONSTEXPR
3893 inline _InputIterator
3894 find(_InputIterator __first, _InputIterator __last,
3898 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3899 __glibcxx_function_requires(_EqualOpConcept<
3901 __glibcxx_requires_valid_range(__first, __last);
3903 __gnu_cxx::__ops::__iter_equals_val(__val));
3916 template<
typename _InputIterator,
typename _Predicate>
3917 _GLIBCXX20_CONSTEXPR
3918 inline _InputIterator
3919 find_if(_InputIterator __first, _InputIterator __last,
3923 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3924 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3926 __glibcxx_requires_valid_range(__first, __last);
3929 __gnu_cxx::__ops::__pred_iter(__pred));
3948 template<
typename _InputIterator,
typename _ForwardIterator>
3949 _GLIBCXX20_CONSTEXPR
3951 find_first_of(_InputIterator __first1, _InputIterator __last1,
3952 _ForwardIterator __first2, _ForwardIterator __last2)
3955 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3956 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3957 __glibcxx_function_requires(_EqualOpConcept<
3960 __glibcxx_requires_valid_range(__first1, __last1);
3961 __glibcxx_requires_valid_range(__first2, __last2);
3963 for (; __first1 != __last1; ++__first1)
3964 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3965 if (*__first1 == *__iter)
3989 template<
typename _InputIterator,
typename _ForwardIterator,
3990 typename _BinaryPredicate>
3991 _GLIBCXX20_CONSTEXPR
3993 find_first_of(_InputIterator __first1, _InputIterator __last1,
3994 _ForwardIterator __first2, _ForwardIterator __last2,
3995 _BinaryPredicate __comp)
3998 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3999 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4000 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4003 __glibcxx_requires_valid_range(__first1, __last1);
4004 __glibcxx_requires_valid_range(__first2, __last2);
4006 for (; __first1 != __last1; ++__first1)
4007 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4008 if (__comp(*__first1, *__iter))
4022 template<
typename _ForwardIterator>
4023 _GLIBCXX20_CONSTEXPR
4024 inline _ForwardIterator
4025 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4028 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4029 __glibcxx_function_requires(_EqualityComparableConcept<
4031 __glibcxx_requires_valid_range(__first, __last);
4033 return std::__adjacent_find(__first, __last,
4034 __gnu_cxx::__ops::__iter_equal_to_iter());
4048 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4049 _GLIBCXX20_CONSTEXPR
4050 inline _ForwardIterator
4051 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4052 _BinaryPredicate __binary_pred)
4055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4056 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4059 __glibcxx_requires_valid_range(__first, __last);
4061 return std::__adjacent_find(__first, __last,
4062 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4074 template<
typename _InputIterator,
typename _Tp>
4075 _GLIBCXX20_CONSTEXPR
4076 inline typename iterator_traits<_InputIterator>::difference_type
4077 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4080 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4081 __glibcxx_function_requires(_EqualOpConcept<
4083 __glibcxx_requires_valid_range(__first, __last);
4085 return std::__count_if(__first, __last,
4086 __gnu_cxx::__ops::__iter_equals_val(__value));
4098 template<
typename _InputIterator,
typename _Predicate>
4099 _GLIBCXX20_CONSTEXPR
4100 inline typename iterator_traits<_InputIterator>::difference_type
4101 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4104 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4105 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4107 __glibcxx_requires_valid_range(__first, __last);
4109 return std::__count_if(__first, __last,
4110 __gnu_cxx::__ops::__pred_iter(__pred));
4139 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4140 _GLIBCXX20_CONSTEXPR
4141 inline _ForwardIterator1
4142 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4143 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4146 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4147 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4148 __glibcxx_function_requires(_EqualOpConcept<
4151 __glibcxx_requires_valid_range(__first1, __last1);
4152 __glibcxx_requires_valid_range(__first2, __last2);
4154 return std::__search(__first1, __last1, __first2, __last2,
4155 __gnu_cxx::__ops::__iter_equal_to_iter());
4179 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4180 typename _BinaryPredicate>
4181 _GLIBCXX20_CONSTEXPR
4182 inline _ForwardIterator1
4183 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4184 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4185 _BinaryPredicate __predicate)
4188 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4189 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4190 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4193 __glibcxx_requires_valid_range(__first1, __last1);
4194 __glibcxx_requires_valid_range(__first2, __last2);
4196 return std::__search(__first1, __last1, __first2, __last2,
4197 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4215 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4216 _GLIBCXX20_CONSTEXPR
4217 inline _ForwardIterator
4218 search_n(_ForwardIterator __first, _ForwardIterator __last,
4219 _Integer __count,
const _Tp& __val)
4222 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4223 __glibcxx_function_requires(_EqualOpConcept<
4225 __glibcxx_requires_valid_range(__first, __last);
4227 return std::__search_n(__first, __last, __count,
4228 __gnu_cxx::__ops::__iter_equals_val(__val));
4249 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4250 typename _BinaryPredicate>
4251 _GLIBCXX20_CONSTEXPR
4252 inline _ForwardIterator
4253 search_n(_ForwardIterator __first, _ForwardIterator __last,
4254 _Integer __count,
const _Tp& __val,
4255 _BinaryPredicate __binary_pred)
4258 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4259 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4261 __glibcxx_requires_valid_range(__first, __last);
4263 return std::__search_n(__first, __last, __count,
4264 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4267 #if __cplusplus > 201402L
4275 template<
typename _ForwardIterator,
typename _Searcher>
4276 inline _ForwardIterator
4277 search(_ForwardIterator __first, _ForwardIterator __last,
4278 const _Searcher& __searcher)
4279 {
return __searcher(__first, __last).first; }
4298 template<
typename _InputIterator,
typename _OutputIterator,
4299 typename _UnaryOperation>
4300 _GLIBCXX20_CONSTEXPR
4302 transform(_InputIterator __first, _InputIterator __last,
4303 _OutputIterator __result, _UnaryOperation __unary_op)
4306 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4307 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4309 __typeof__(__unary_op(*__first))>)
4310 __glibcxx_requires_valid_range(__first, __last);
4312 for (; __first != __last; ++__first, (void)++__result)
4313 *__result = __unary_op(*__first);
4336 template<
typename _InputIterator1,
typename _InputIterator2,
4337 typename _OutputIterator,
typename _BinaryOperation>
4338 _GLIBCXX20_CONSTEXPR
4340 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4341 _InputIterator2 __first2, _OutputIterator __result,
4342 _BinaryOperation __binary_op)
4345 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4346 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4347 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4349 __typeof__(__binary_op(*__first1,*__first2))>)
4350 __glibcxx_requires_valid_range(__first1, __last1);
4352 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4353 *__result = __binary_op(*__first1, *__first2);
4370 template<
typename _ForwardIterator,
typename _Tp>
4371 _GLIBCXX20_CONSTEXPR
4373 replace(_ForwardIterator __first, _ForwardIterator __last,
4374 const _Tp& __old_value,
const _Tp& __new_value)
4377 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4379 __glibcxx_function_requires(_EqualOpConcept<
4381 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4383 __glibcxx_requires_valid_range(__first, __last);
4385 for (; __first != __last; ++__first)
4386 if (*__first == __old_value)
4387 *__first = __new_value;
4403 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4404 _GLIBCXX20_CONSTEXPR
4406 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4407 _Predicate __pred,
const _Tp& __new_value)
4410 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4412 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4414 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4416 __glibcxx_requires_valid_range(__first, __last);
4418 for (; __first != __last; ++__first)
4419 if (__pred(*__first))
4420 *__first = __new_value;
4436 template<
typename _ForwardIterator,
typename _Generator>
4437 _GLIBCXX20_CONSTEXPR
4439 generate(_ForwardIterator __first, _ForwardIterator __last,
4443 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4444 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4446 __glibcxx_requires_valid_range(__first, __last);
4448 for (; __first != __last; ++__first)
4470 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4471 _GLIBCXX20_CONSTEXPR
4473 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4478 __typeof__(__gen())>)
4480 typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4481 for (_IntSize __niter = std::__size_to_integer(__n);
4482 __niter > 0; --__niter, (void) ++__first)
4508 template<
typename _InputIterator,
typename _OutputIterator>
4509 _GLIBCXX20_CONSTEXPR
4510 inline _OutputIterator
4511 unique_copy(_InputIterator __first, _InputIterator __last,
4512 _OutputIterator __result)
4515 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4516 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4518 __glibcxx_function_requires(_EqualityComparableConcept<
4520 __glibcxx_requires_valid_range(__first, __last);
4522 if (__first == __last)
4525 __gnu_cxx::__ops::__iter_equal_to_iter(),
4549 template<
typename _InputIterator,
typename _OutputIterator,
4550 typename _BinaryPredicate>
4551 _GLIBCXX20_CONSTEXPR
4552 inline _OutputIterator
4553 unique_copy(_InputIterator __first, _InputIterator __last,
4554 _OutputIterator __result,
4555 _BinaryPredicate __binary_pred)
4558 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4559 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4561 __glibcxx_requires_valid_range(__first, __last);
4563 if (__first == __last)
4566 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4583 template<
typename _RandomAccessIterator>
4585 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4588 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4589 _RandomAccessIterator>)
4590 __glibcxx_requires_valid_range(__first, __last);
4592 if (__first != __last)
4593 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4596 _RandomAccessIterator __j = __first
4597 + std::rand() % ((__i - __first) + 1);
4599 std::iter_swap(__i, __j);
4618 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4620 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4621 #
if __cplusplus >= 201103L
4622 _RandomNumberGenerator&& __rand)
4624 _RandomNumberGenerator& __rand)
4628 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4629 _RandomAccessIterator>)
4630 __glibcxx_requires_valid_range(__first, __last);
4632 if (__first == __last)
4634 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4636 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4658 template<
typename _ForwardIterator,
typename _Predicate>
4659 _GLIBCXX20_CONSTEXPR
4660 inline _ForwardIterator
4661 partition(_ForwardIterator __first, _ForwardIterator __last,
4665 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4667 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4669 __glibcxx_requires_valid_range(__first, __last);
4692 template<
typename _RandomAccessIterator>
4693 _GLIBCXX20_CONSTEXPR
4695 partial_sort(_RandomAccessIterator __first,
4696 _RandomAccessIterator __middle,
4697 _RandomAccessIterator __last)
4700 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4701 _RandomAccessIterator>)
4702 __glibcxx_function_requires(_LessThanComparableConcept<
4704 __glibcxx_requires_valid_range(__first, __middle);
4705 __glibcxx_requires_valid_range(__middle, __last);
4706 __glibcxx_requires_irreflexive(__first, __last);
4708 std::__partial_sort(__first, __middle, __last,
4709 __gnu_cxx::__ops::__iter_less_iter());
4731 template<
typename _RandomAccessIterator,
typename _Compare>
4732 _GLIBCXX20_CONSTEXPR
4734 partial_sort(_RandomAccessIterator __first,
4735 _RandomAccessIterator __middle,
4736 _RandomAccessIterator __last,
4740 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4741 _RandomAccessIterator>)
4742 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4745 __glibcxx_requires_valid_range(__first, __middle);
4746 __glibcxx_requires_valid_range(__middle, __last);
4747 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4749 std::__partial_sort(__first, __middle, __last,
4750 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4768 template<
typename _RandomAccessIterator>
4769 _GLIBCXX20_CONSTEXPR
4771 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4772 _RandomAccessIterator __last)
4775 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4776 _RandomAccessIterator>)
4777 __glibcxx_function_requires(_LessThanComparableConcept<
4779 __glibcxx_requires_valid_range(__first, __nth);
4780 __glibcxx_requires_valid_range(__nth, __last);
4781 __glibcxx_requires_irreflexive(__first, __last);
4783 if (__first == __last || __nth == __last)
4786 std::__introselect(__first, __nth, __last,
4788 __gnu_cxx::__ops::__iter_less_iter());
4808 template<
typename _RandomAccessIterator,
typename _Compare>
4809 _GLIBCXX20_CONSTEXPR
4811 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4812 _RandomAccessIterator __last, _Compare __comp)
4815 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4816 _RandomAccessIterator>)
4817 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4820 __glibcxx_requires_valid_range(__first, __nth);
4821 __glibcxx_requires_valid_range(__nth, __last);
4822 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4824 if (__first == __last || __nth == __last)
4827 std::__introselect(__first, __nth, __last,
4829 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4846 template<
typename _RandomAccessIterator>
4847 _GLIBCXX20_CONSTEXPR
4849 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4852 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4853 _RandomAccessIterator>)
4854 __glibcxx_function_requires(_LessThanComparableConcept<
4856 __glibcxx_requires_valid_range(__first, __last);
4857 __glibcxx_requires_irreflexive(__first, __last);
4859 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4877 template<
typename _RandomAccessIterator,
typename _Compare>
4878 _GLIBCXX20_CONSTEXPR
4880 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4884 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4885 _RandomAccessIterator>)
4886 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4889 __glibcxx_requires_valid_range(__first, __last);
4890 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4892 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4895 template<
typename _InputIterator1,
typename _InputIterator2,
4896 typename _OutputIterator,
typename _Compare>
4897 _GLIBCXX20_CONSTEXPR
4899 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4900 _InputIterator2 __first2, _InputIterator2 __last2,
4901 _OutputIterator __result, _Compare __comp)
4903 while (__first1 != __last1 && __first2 != __last2)
4905 if (__comp(__first2, __first1))
4907 *__result = *__first2;
4912 *__result = *__first1;
4917 return std::copy(__first2, __last2,
4918 std::copy(__first1, __last1, __result));
4940 template<
typename _InputIterator1,
typename _InputIterator2,
4941 typename _OutputIterator>
4942 _GLIBCXX20_CONSTEXPR
4943 inline _OutputIterator
4944 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4945 _InputIterator2 __first2, _InputIterator2 __last2,
4946 _OutputIterator __result)
4949 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4950 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4951 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4953 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4955 __glibcxx_function_requires(_LessThanOpConcept<
4958 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4959 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4960 __glibcxx_requires_irreflexive2(__first1, __last1);
4961 __glibcxx_requires_irreflexive2(__first2, __last2);
4963 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4964 __first2, __last2, __result,
4965 __gnu_cxx::__ops::__iter_less_iter());
4991 template<
typename _InputIterator1,
typename _InputIterator2,
4992 typename _OutputIterator,
typename _Compare>
4993 _GLIBCXX20_CONSTEXPR
4994 inline _OutputIterator
4995 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4996 _InputIterator2 __first2, _InputIterator2 __last2,
4997 _OutputIterator __result, _Compare __comp)
5000 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5001 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5002 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5004 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5006 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5009 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5010 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5011 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5012 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5014 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5015 __first2, __last2, __result,
5016 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5019 template<
typename _RandomAccessIterator,
typename _Compare>
5021 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5024 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5026 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5029 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5032 if (__buf.begin() == 0)
5035 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5036 _DistanceType(__buf.size()), __comp);
5056 template<
typename _RandomAccessIterator>
5058 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5061 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5062 _RandomAccessIterator>)
5063 __glibcxx_function_requires(_LessThanComparableConcept<
5065 __glibcxx_requires_valid_range(__first, __last);
5066 __glibcxx_requires_irreflexive(__first, __last);
5068 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5069 __gnu_cxx::__ops::__iter_less_iter());
5090 template<
typename _RandomAccessIterator,
typename _Compare>
5092 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5096 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5097 _RandomAccessIterator>)
5098 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5101 __glibcxx_requires_valid_range(__first, __last);
5102 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5104 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5105 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5108 template<
typename _InputIterator1,
typename _InputIterator2,
5109 typename _OutputIterator,
5111 _GLIBCXX20_CONSTEXPR
5113 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5114 _InputIterator2 __first2, _InputIterator2 __last2,
5115 _OutputIterator __result, _Compare __comp)
5117 while (__first1 != __last1 && __first2 != __last2)
5119 if (__comp(__first1, __first2))
5121 *__result = *__first1;
5124 else if (__comp(__first2, __first1))
5126 *__result = *__first2;
5131 *__result = *__first1;
5137 return std::copy(__first2, __last2,
5138 std::copy(__first1, __last1, __result));
5160 template<
typename _InputIterator1,
typename _InputIterator2,
5161 typename _OutputIterator>
5162 _GLIBCXX20_CONSTEXPR
5163 inline _OutputIterator
5164 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5165 _InputIterator2 __first2, _InputIterator2 __last2,
5166 _OutputIterator __result)
5169 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5170 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5173 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5175 __glibcxx_function_requires(_LessThanOpConcept<
5178 __glibcxx_function_requires(_LessThanOpConcept<
5181 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5182 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5183 __glibcxx_requires_irreflexive2(__first1, __last1);
5184 __glibcxx_requires_irreflexive2(__first2, __last2);
5186 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5187 __first2, __last2, __result,
5188 __gnu_cxx::__ops::__iter_less_iter());
5211 template<
typename _InputIterator1,
typename _InputIterator2,
5212 typename _OutputIterator,
typename _Compare>
5213 _GLIBCXX20_CONSTEXPR
5214 inline _OutputIterator
5215 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5216 _InputIterator2 __first2, _InputIterator2 __last2,
5217 _OutputIterator __result, _Compare __comp)
5220 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5221 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5222 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5224 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5226 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5229 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5232 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5233 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5234 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5235 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5237 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5238 __first2, __last2, __result,
5239 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5242 template<
typename _InputIterator1,
typename _InputIterator2,
5243 typename _OutputIterator,
5245 _GLIBCXX20_CONSTEXPR
5247 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5248 _InputIterator2 __first2, _InputIterator2 __last2,
5249 _OutputIterator __result, _Compare __comp)
5251 while (__first1 != __last1 && __first2 != __last2)
5252 if (__comp(__first1, __first2))
5254 else if (__comp(__first2, __first1))
5258 *__result = *__first1;
5284 template<
typename _InputIterator1,
typename _InputIterator2,
5285 typename _OutputIterator>
5286 _GLIBCXX20_CONSTEXPR
5287 inline _OutputIterator
5288 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5289 _InputIterator2 __first2, _InputIterator2 __last2,
5290 _OutputIterator __result)
5293 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5294 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5295 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5297 __glibcxx_function_requires(_LessThanOpConcept<
5300 __glibcxx_function_requires(_LessThanOpConcept<
5303 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5304 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5305 __glibcxx_requires_irreflexive2(__first1, __last1);
5306 __glibcxx_requires_irreflexive2(__first2, __last2);
5308 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5309 __first2, __last2, __result,
5310 __gnu_cxx::__ops::__iter_less_iter());
5334 template<
typename _InputIterator1,
typename _InputIterator2,
5335 typename _OutputIterator,
typename _Compare>
5336 _GLIBCXX20_CONSTEXPR
5337 inline _OutputIterator
5338 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5339 _InputIterator2 __first2, _InputIterator2 __last2,
5340 _OutputIterator __result, _Compare __comp)
5343 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5344 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5345 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5347 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5350 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5353 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5354 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5355 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5356 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5358 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5359 __first2, __last2, __result,
5360 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5363 template<
typename _InputIterator1,
typename _InputIterator2,
5364 typename _OutputIterator,
5366 _GLIBCXX20_CONSTEXPR
5368 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5369 _InputIterator2 __first2, _InputIterator2 __last2,
5370 _OutputIterator __result, _Compare __comp)
5372 while (__first1 != __last1 && __first2 != __last2)
5373 if (__comp(__first1, __first2))
5375 *__result = *__first1;
5379 else if (__comp(__first2, __first1))
5386 return std::copy(__first1, __last1, __result);
5409 template<
typename _InputIterator1,
typename _InputIterator2,
5410 typename _OutputIterator>
5411 _GLIBCXX20_CONSTEXPR
5412 inline _OutputIterator
5413 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5414 _InputIterator2 __first2, _InputIterator2 __last2,
5415 _OutputIterator __result)
5418 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5419 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5420 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5422 __glibcxx_function_requires(_LessThanOpConcept<
5425 __glibcxx_function_requires(_LessThanOpConcept<
5428 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5429 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5430 __glibcxx_requires_irreflexive2(__first1, __last1);
5431 __glibcxx_requires_irreflexive2(__first2, __last2);
5433 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5434 __first2, __last2, __result,
5435 __gnu_cxx::__ops::__iter_less_iter());
5461 template<
typename _InputIterator1,
typename _InputIterator2,
5462 typename _OutputIterator,
typename _Compare>
5463 _GLIBCXX20_CONSTEXPR
5464 inline _OutputIterator
5465 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5466 _InputIterator2 __first2, _InputIterator2 __last2,
5467 _OutputIterator __result, _Compare __comp)
5470 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5471 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5472 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5474 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5477 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5480 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5481 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5482 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5483 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5485 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5486 __first2, __last2, __result,
5487 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5490 template<
typename _InputIterator1,
typename _InputIterator2,
5491 typename _OutputIterator,
5493 _GLIBCXX20_CONSTEXPR
5495 __set_symmetric_difference(_InputIterator1 __first1,
5496 _InputIterator1 __last1,
5497 _InputIterator2 __first2,
5498 _InputIterator2 __last2,
5499 _OutputIterator __result,
5502 while (__first1 != __last1 && __first2 != __last2)
5503 if (__comp(__first1, __first2))
5505 *__result = *__first1;
5509 else if (__comp(__first2, __first1))
5511 *__result = *__first2;
5520 return std::copy(__first2, __last2,
5521 std::copy(__first1, __last1, __result));
5542 template<
typename _InputIterator1,
typename _InputIterator2,
5543 typename _OutputIterator>
5544 _GLIBCXX20_CONSTEXPR
5545 inline _OutputIterator
5546 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5547 _InputIterator2 __first2, _InputIterator2 __last2,
5548 _OutputIterator __result)
5551 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5552 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5553 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5555 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5557 __glibcxx_function_requires(_LessThanOpConcept<
5560 __glibcxx_function_requires(_LessThanOpConcept<
5563 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5564 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5565 __glibcxx_requires_irreflexive2(__first1, __last1);
5566 __glibcxx_requires_irreflexive2(__first2, __last2);
5568 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5569 __first2, __last2, __result,
5570 __gnu_cxx::__ops::__iter_less_iter());
5594 template<
typename _InputIterator1,
typename _InputIterator2,
5595 typename _OutputIterator,
typename _Compare>
5596 _GLIBCXX20_CONSTEXPR
5597 inline _OutputIterator
5598 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5599 _InputIterator2 __first2, _InputIterator2 __last2,
5600 _OutputIterator __result,
5604 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5605 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5606 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5608 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5610 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5613 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5616 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5617 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5618 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5619 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5621 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5622 __first2, __last2, __result,
5623 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5626 template<
typename _ForwardIterator,
typename _Compare>
5627 _GLIBCXX14_CONSTEXPR
5629 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5632 if (__first == __last)
5634 _ForwardIterator __result = __first;
5635 while (++__first != __last)
5636 if (__comp(__first, __result))
5648 template<
typename _ForwardIterator>
5649 _GLIBCXX14_CONSTEXPR
5651 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5654 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5655 __glibcxx_function_requires(_LessThanComparableConcept<
5657 __glibcxx_requires_valid_range(__first, __last);
5658 __glibcxx_requires_irreflexive(__first, __last);
5660 return _GLIBCXX_STD_A::__min_element(__first, __last,
5661 __gnu_cxx::__ops::__iter_less_iter());
5673 template<
typename _ForwardIterator,
typename _Compare>
5674 _GLIBCXX14_CONSTEXPR
5675 inline _ForwardIterator
5676 min_element(_ForwardIterator __first, _ForwardIterator __last,
5680 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5681 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5684 __glibcxx_requires_valid_range(__first, __last);
5685 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5687 return _GLIBCXX_STD_A::__min_element(__first, __last,
5688 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5691 template<
typename _ForwardIterator,
typename _Compare>
5692 _GLIBCXX14_CONSTEXPR
5694 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5697 if (__first == __last)
return __first;
5698 _ForwardIterator __result = __first;
5699 while (++__first != __last)
5700 if (__comp(__result, __first))
5712 template<
typename _ForwardIterator>
5713 _GLIBCXX14_CONSTEXPR
5714 inline _ForwardIterator
5715 max_element(_ForwardIterator __first, _ForwardIterator __last)
5718 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5719 __glibcxx_function_requires(_LessThanComparableConcept<
5721 __glibcxx_requires_valid_range(__first, __last);
5722 __glibcxx_requires_irreflexive(__first, __last);
5724 return _GLIBCXX_STD_A::__max_element(__first, __last,
5725 __gnu_cxx::__ops::__iter_less_iter());
5737 template<
typename _ForwardIterator,
typename _Compare>
5738 _GLIBCXX14_CONSTEXPR
5739 inline _ForwardIterator
5740 max_element(_ForwardIterator __first, _ForwardIterator __last,
5744 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5745 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5748 __glibcxx_requires_valid_range(__first, __last);
5749 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5751 return _GLIBCXX_STD_A::__max_element(__first, __last,
5752 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5755 #if __cplusplus >= 201402L
5757 template<
typename _InputIterator,
typename _RandomAccessIterator,
5758 typename _Size,
typename _UniformRandomBitGenerator>
5759 _RandomAccessIterator
5762 _Size __n, _UniformRandomBitGenerator&& __g)
5765 using __param_type =
typename __distrib_type::param_type;
5766 __distrib_type __d{};
5767 _Size __sample_sz = 0;
5768 while (__first != __last && __sample_sz != __n)
5770 __out[__sample_sz++] = *__first;
5773 for (
auto __pop_sz = __sample_sz; __first != __last;
5774 ++__first, (void) ++__pop_sz)
5776 const auto __k = __d(__g, __param_type{0, __pop_sz});
5778 __out[__k] = *__first;
5780 return __out + __sample_sz;
5784 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5785 typename _Size,
typename _UniformRandomBitGenerator>
5787 __sample(_ForwardIterator __first, _ForwardIterator __last,
5789 _OutputIterator __out, _Cat,
5790 _Size __n, _UniformRandomBitGenerator&& __g)
5793 using __param_type =
typename __distrib_type::param_type;
5798 __distrib_type __d{};
5800 __n =
std::min(__n, __unsampled_sz);
5805 const __uc_type __urngrange = __g.max() - __g.min();
5806 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5810 while (__n != 0 && __unsampled_sz >= 2)
5816 if (__p.
first < __n)
5818 *__out++ = *__first;
5824 if (__n == 0)
break;
5829 *__out++ = *__first;
5839 for (; __n != 0; ++__first)
5840 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5842 *__out++ = *__first;
5848 #if __cplusplus > 201402L
5849 #define __cpp_lib_sample 201603
5851 template<
typename _PopulationIterator,
typename _SampleIterator,
5852 typename _Distance,
typename _UniformRandomBitGenerator>
5854 sample(_PopulationIterator __first, _PopulationIterator __last,
5855 _SampleIterator __out, _Distance __n,
5856 _UniformRandomBitGenerator&& __g)
5858 using __pop_cat =
typename
5860 using __samp_cat =
typename
5864 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5865 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5866 "output range must use a RandomAccessIterator when input range"
5867 " does not meet the ForwardIterator requirements");
5869 static_assert(is_integral<_Distance>::value,
5870 "sample size must be an integer type");
5872 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5874 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5875 std::forward<_UniformRandomBitGenerator>(__g));
5880 _GLIBCXX_END_NAMESPACE_ALGO
5881 _GLIBCXX_END_NAMESPACE_VERSION