65 #if __cplusplus >= 201103L 71 namespace std _GLIBCXX_VISIBILITY(default)
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator,
typename _Compare>
79 _Iterator __c, _Compare __comp)
85 else if (__comp(__a, __c))
90 else if (__comp(__a, __c))
92 else if (__comp(__b, __c))
99 template<
typename _InputIterator,
typename _Predicate>
100 inline _InputIterator
101 __find_if(_InputIterator __first, _InputIterator __last,
104 while (__first != __last && !__pred(__first))
110 template<
typename _RandomAccessIterator,
typename _Predicate>
111 _RandomAccessIterator
112 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
115 typename iterator_traits<_RandomAccessIterator>::difference_type
116 __trip_count = (__last - __first) >> 2;
118 for (; __trip_count > 0; --__trip_count)
137 switch (__last - __first)
157 template<
typename _Iterator,
typename _Predicate>
159 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
161 return __find_if(__first, __last, __pred,
166 template<
typename _InputIterator,
typename _Predicate>
167 inline _InputIterator
172 __gnu_cxx::__ops::__negate(__pred),
179 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
183 for (; __len; --__len, (void) ++__first)
184 if (!__pred(__first))
202 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
203 typename _BinaryPredicate>
205 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
206 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
207 _BinaryPredicate __predicate)
210 if (__first1 == __last1 || __first2 == __last2)
214 _ForwardIterator2 __p1(__first2);
215 if (++__p1 == __last2)
217 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
220 _ForwardIterator2 __p;
221 _ForwardIterator1 __current = __first1;
227 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
229 if (__first1 == __last1)
233 __current = __first1;
234 if (++__current == __last1)
237 while (__predicate(__current, __p))
239 if (++__p == __last2)
241 if (++__current == __last1)
254 template<
typename _ForwardIterator,
typename _Integer,
255 typename _UnaryPredicate>
258 _Integer __count, _UnaryPredicate __unary_pred,
262 while (__first != __last)
264 typename iterator_traits<_ForwardIterator>::difference_type
266 _ForwardIterator __i = __first;
268 while (__i != __last && __n != 1 && __unary_pred(__i))
286 template<
typename _RandomAccessIter,
typename _Integer,
287 typename _UnaryPredicate>
290 _Integer __count, _UnaryPredicate __unary_pred,
293 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
296 _DistanceType __tailSize = __last - __first;
297 _DistanceType __remainder = __count;
299 while (__remainder <= __tailSize)
301 __first += __remainder;
302 __tailSize -= __remainder;
305 _RandomAccessIter __backTrack = __first;
306 while (__unary_pred(--__backTrack))
308 if (--__remainder == 0)
309 return (__first - __count);
311 __remainder = __count + 1 - (__first - __backTrack);
316 template<
typename _ForwardIterator,
typename _Integer,
317 typename _UnaryPredicate>
319 __search_n(_ForwardIterator __first, _ForwardIterator __last,
321 _UnaryPredicate __unary_pred)
334 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
335 typename _BinaryPredicate>
337 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
338 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
339 forward_iterator_tag, forward_iterator_tag,
340 _BinaryPredicate __comp)
342 if (__first2 == __last2)
345 _ForwardIterator1 __result = __last1;
348 _ForwardIterator1 __new_result
349 = std::__search(__first1, __last1, __first2, __last2, __comp);
350 if (__new_result == __last1)
354 __result = __new_result;
355 __first1 = __new_result;
362 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
363 typename _BinaryPredicate>
364 _BidirectionalIterator1
365 __find_end(_BidirectionalIterator1 __first1,
366 _BidirectionalIterator1 __last1,
367 _BidirectionalIterator2 __first2,
368 _BidirectionalIterator2 __last2,
369 bidirectional_iterator_tag, bidirectional_iterator_tag,
370 _BinaryPredicate __comp)
373 __glibcxx_function_requires(_BidirectionalIteratorConcept<
374 _BidirectionalIterator1>)
375 __glibcxx_function_requires(_BidirectionalIteratorConcept<
376 _BidirectionalIterator2>)
378 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
379 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
381 _RevIterator1 __rlast1(__first1);
382 _RevIterator2 __rlast2(__first2);
383 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
384 _RevIterator2(__last2), __rlast2,
387 if (__rresult == __rlast1)
391 _BidirectionalIterator1 __result = __rresult.base();
423 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
424 inline _ForwardIterator1
425 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
426 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
430 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
431 __glibcxx_function_requires(_EqualOpConcept<
432 typename iterator_traits<_ForwardIterator1>::value_type,
433 typename iterator_traits<_ForwardIterator2>::value_type>)
434 __glibcxx_requires_valid_range(__first1, __last1);
435 __glibcxx_requires_valid_range(__first2, __last2);
437 return std::__find_end(__first1, __last1, __first2, __last2,
440 __gnu_cxx::__ops::__iter_equal_to_iter());
471 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
472 typename _BinaryPredicate>
473 inline _ForwardIterator1
474 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
475 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
476 _BinaryPredicate __comp)
479 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
481 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
482 typename iterator_traits<_ForwardIterator1>::value_type,
483 typename iterator_traits<_ForwardIterator2>::value_type>)
484 __glibcxx_requires_valid_range(__first1, __last1);
485 __glibcxx_requires_valid_range(__first2, __last2);
487 return std::__find_end(__first1, __last1, __first2, __last2,
490 __gnu_cxx::__ops::__iter_comp_iter(__comp));
493 #if __cplusplus >= 201103L 506 template<
typename _InputIterator,
typename _Predicate>
508 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
523 template<
typename _InputIterator,
typename _Predicate>
525 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
541 template<
typename _InputIterator,
typename _Predicate>
543 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
556 template<
typename _InputIterator,
typename _Predicate>
557 inline _InputIterator
558 find_if_not(_InputIterator __first, _InputIterator __last,
562 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
563 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
564 typename iterator_traits<_InputIterator>::value_type>)
565 __glibcxx_requires_valid_range(__first, __last);
567 __gnu_cxx::__ops::__pred_iter(__pred));
580 template<
typename _InputIterator,
typename _Predicate>
582 is_partitioned(_InputIterator __first, _InputIterator __last,
586 if (__first == __last)
601 template<
typename _ForwardIterator,
typename _Predicate>
603 partition_point(_ForwardIterator __first, _ForwardIterator __last,
607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
608 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
609 typename iterator_traits<_ForwardIterator>::value_type>)
612 __glibcxx_requires_valid_range(__first, __last);
614 typedef typename iterator_traits<_ForwardIterator>::difference_type
618 _DistanceType __half;
619 _ForwardIterator __middle;
626 if (__pred(*__middle))
630 __len = __len - __half - 1;
639 template<
typename _InputIterator,
typename _OutputIterator,
642 __remove_copy_if(_InputIterator __first, _InputIterator __last,
643 _OutputIterator __result, _Predicate __pred)
645 for (; __first != __last; ++__first)
646 if (!__pred(__first))
648 *__result = *__first;
668 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
669 inline _OutputIterator
670 remove_copy(_InputIterator __first, _InputIterator __last,
671 _OutputIterator __result,
const _Tp& __value)
674 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
675 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
676 typename iterator_traits<_InputIterator>::value_type>)
677 __glibcxx_function_requires(_EqualOpConcept<
678 typename iterator_traits<_InputIterator>::value_type, _Tp>)
679 __glibcxx_requires_valid_range(__first, __last);
681 return std::__remove_copy_if(__first, __last, __result,
682 __gnu_cxx::__ops::__iter_equals_val(__value));
700 template<
typename _InputIterator,
typename _OutputIterator,
702 inline _OutputIterator
703 remove_copy_if(_InputIterator __first, _InputIterator __last,
704 _OutputIterator __result, _Predicate __pred)
707 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
708 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
709 typename iterator_traits<_InputIterator>::value_type>)
710 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
711 typename iterator_traits<_InputIterator>::value_type>)
712 __glibcxx_requires_valid_range(__first, __last);
714 return std::__remove_copy_if(__first, __last, __result,
715 __gnu_cxx::__ops::__pred_iter(__pred));
718 #if __cplusplus >= 201103L 734 template<
typename _InputIterator,
typename _OutputIterator,
737 copy_if(_InputIterator __first, _InputIterator __last,
738 _OutputIterator __result, _Predicate __pred)
741 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
742 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
743 typename iterator_traits<_InputIterator>::value_type>)
744 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
745 typename iterator_traits<_InputIterator>::value_type>)
746 __glibcxx_requires_valid_range(__first, __last);
748 for (; __first != __last; ++__first)
749 if (__pred(*__first))
751 *__result = *__first;
757 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
759 __copy_n(_InputIterator __first, _Size __n,
760 _OutputIterator __result, input_iterator_tag)
766 *__result = *__first;
777 template<
typename _RandomAccessIterator,
typename _Size,
778 typename _OutputIterator>
779 inline _OutputIterator
780 __copy_n(_RandomAccessIterator __first, _Size __n,
781 _OutputIterator __result, random_access_iterator_tag)
782 {
return std::copy(__first, __first + __n, __result); }
797 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
798 inline _OutputIterator
799 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
802 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
803 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
804 typename iterator_traits<_InputIterator>::value_type>)
806 return std::__copy_n(__first, __n, __result,
825 template<
typename _InputIterator,
typename _OutputIterator1,
826 typename _OutputIterator2,
typename _Predicate>
827 pair<_OutputIterator1, _OutputIterator2>
828 partition_copy(_InputIterator __first, _InputIterator __last,
829 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
833 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
834 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
835 typename iterator_traits<_InputIterator>::value_type>)
836 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
837 typename iterator_traits<_InputIterator>::value_type>)
838 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
839 typename iterator_traits<_InputIterator>::value_type>)
840 __glibcxx_requires_valid_range(__first, __last);
842 for (; __first != __last; ++__first)
843 if (__pred(*__first))
845 *__out_true = *__first;
850 *__out_false = *__first;
858 template<
typename _ForwardIterator,
typename _Predicate>
860 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
864 if (__first == __last)
866 _ForwardIterator __result = __first;
868 for (; __first != __last; ++__first)
869 if (!__pred(__first))
871 *__result = _GLIBCXX_MOVE(*__first);
894 template<
typename _ForwardIterator,
typename _Tp>
895 inline _ForwardIterator
896 remove(_ForwardIterator __first, _ForwardIterator __last,
900 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
902 __glibcxx_function_requires(_EqualOpConcept<
903 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
904 __glibcxx_requires_valid_range(__first, __last);
906 return std::__remove_if(__first, __last,
907 __gnu_cxx::__ops::__iter_equals_val(__value));
927 template<
typename _ForwardIterator,
typename _Predicate>
928 inline _ForwardIterator
929 remove_if(_ForwardIterator __first, _ForwardIterator __last,
933 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
935 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
936 typename iterator_traits<_ForwardIterator>::value_type>)
937 __glibcxx_requires_valid_range(__first, __last);
939 return std::__remove_if(__first, __last,
940 __gnu_cxx::__ops::__pred_iter(__pred));
943 template<
typename _ForwardIterator,
typename _BinaryPredicate>
945 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
946 _BinaryPredicate __binary_pred)
948 if (__first == __last)
950 _ForwardIterator __next = __first;
951 while (++__next != __last)
953 if (__binary_pred(__first, __next))
960 template<
typename _ForwardIterator,
typename _BinaryPredicate>
962 __unique(_ForwardIterator __first, _ForwardIterator __last,
963 _BinaryPredicate __binary_pred)
966 __first = std::__adjacent_find(__first, __last, __binary_pred);
967 if (__first == __last)
971 _ForwardIterator __dest = __first;
973 while (++__first != __last)
974 if (!__binary_pred(__dest, __first))
975 *++__dest = _GLIBCXX_MOVE(*__first);
993 template<
typename _ForwardIterator>
994 inline _ForwardIterator
995 unique(_ForwardIterator __first, _ForwardIterator __last)
998 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1000 __glibcxx_function_requires(_EqualityComparableConcept<
1001 typename iterator_traits<_ForwardIterator>::value_type>)
1002 __glibcxx_requires_valid_range(__first, __last);
1004 return std::__unique(__first, __last,
1005 __gnu_cxx::__ops::__iter_equal_to_iter());
1023 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1024 inline _ForwardIterator
1025 unique(_ForwardIterator __first, _ForwardIterator __last,
1026 _BinaryPredicate __binary_pred)
1029 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1031 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1032 typename iterator_traits<_ForwardIterator>::value_type,
1033 typename iterator_traits<_ForwardIterator>::value_type>)
1034 __glibcxx_requires_valid_range(__first, __last);
1036 return std::__unique(__first, __last,
1037 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1046 template<
typename _ForwardIterator,
typename _OutputIterator,
1047 typename _BinaryPredicate>
1050 _OutputIterator __result, _BinaryPredicate __binary_pred,
1054 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1055 typename iterator_traits<_ForwardIterator>::value_type,
1056 typename iterator_traits<_ForwardIterator>::value_type>)
1058 _ForwardIterator __next = __first;
1059 *__result = *__first;
1060 while (++__next != __last)
1061 if (!__binary_pred(__first, __next))
1064 *++__result = *__first;
1075 template<
typename _InputIterator,
typename _OutputIterator,
1076 typename _BinaryPredicate>
1079 _OutputIterator __result, _BinaryPredicate __binary_pred,
1083 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1084 typename iterator_traits<_InputIterator>::value_type,
1085 typename iterator_traits<_InputIterator>::value_type>)
1087 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1088 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1090 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1091 *__result = __value;
1092 while (++__first != __last)
1093 if (!__rebound_pred(__first, __value))
1096 *++__result = __value;
1107 template<
typename _InputIterator,
typename _ForwardIterator,
1108 typename _BinaryPredicate>
1111 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1115 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1116 typename iterator_traits<_ForwardIterator>::value_type,
1117 typename iterator_traits<_InputIterator>::value_type>)
1118 *__result = *__first;
1119 while (++__first != __last)
1120 if (!__binary_pred(__result, __first))
1121 *++__result = *__first;
1130 template<
typename _B
idirectionalIterator>
1132 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1136 if (__first == __last || __first == --__last)
1150 template<
typename _RandomAccessIterator>
1152 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1155 if (__first == __last)
1158 while (__first < __last)
1178 template<
typename _B
idirectionalIterator>
1180 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1183 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1184 _BidirectionalIterator>)
1185 __glibcxx_requires_valid_range(__first, __last);
1205 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1207 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1208 _OutputIterator __result)
1211 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1212 _BidirectionalIterator>)
1213 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1214 typename iterator_traits<_BidirectionalIterator>::value_type>)
1215 __glibcxx_requires_valid_range(__first, __last);
1217 while (__first != __last)
1220 *__result = *__last;
1230 template<
typename _Eucl
ideanRingElement>
1231 _EuclideanRingElement
1232 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1236 _EuclideanRingElement __t = __m % __n;
1243 inline namespace _V2
1247 template<
typename _ForwardIterator>
1250 _ForwardIterator __middle,
1251 _ForwardIterator __last,
1254 if (__first == __middle)
1256 else if (__last == __middle)
1259 _ForwardIterator __first2 = __middle;
1265 if (__first == __middle)
1266 __middle = __first2;
1268 while (__first2 != __last);
1270 _ForwardIterator __ret = __first;
1272 __first2 = __middle;
1274 while (__first2 != __last)
1279 if (__first == __middle)
1280 __middle = __first2;
1281 else if (__first2 == __last)
1282 __first2 = __middle;
1288 template<
typename _B
idirectionalIterator>
1289 _BidirectionalIterator
1291 _BidirectionalIterator __middle,
1292 _BidirectionalIterator __last,
1296 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1297 _BidirectionalIterator>)
1299 if (__first == __middle)
1301 else if (__last == __middle)
1307 while (__first != __middle && __middle != __last)
1313 if (__first == __middle)
1326 template<
typename _RandomAccessIterator>
1327 _RandomAccessIterator
1329 _RandomAccessIterator __middle,
1330 _RandomAccessIterator __last,
1334 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1335 _RandomAccessIterator>)
1337 if (__first == __middle)
1339 else if (__last == __middle)
1342 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1344 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1347 _Distance __n = __last - __first;
1348 _Distance __k = __middle - __first;
1350 if (__k == __n - __k)
1356 _RandomAccessIterator __p = __first;
1357 _RandomAccessIterator __ret = __first + (__last - __middle);
1361 if (__k < __n - __k)
1363 if (__is_pod(_ValueType) && __k == 1)
1365 _ValueType __t = _GLIBCXX_MOVE(*__p);
1366 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1367 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1370 _RandomAccessIterator __q = __p + __k;
1371 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1380 std::swap(__n, __k);
1386 if (__is_pod(_ValueType) && __k == 1)
1388 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1389 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1390 *__p = _GLIBCXX_MOVE(__t);
1393 _RandomAccessIterator __q = __p + __n;
1395 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1404 std::swap(__n, __k);
1432 template<
typename _ForwardIterator>
1433 inline _ForwardIterator
1434 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1435 _ForwardIterator __last)
1438 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1440 __glibcxx_requires_valid_range(__first, __middle);
1441 __glibcxx_requires_valid_range(__middle, __last);
1443 return std::__rotate(__first, __middle, __last,
1469 template<
typename _ForwardIterator,
typename _OutputIterator>
1470 inline _OutputIterator
1471 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1472 _ForwardIterator __last, _OutputIterator __result)
1475 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1477 typename iterator_traits<_ForwardIterator>::value_type>)
1478 __glibcxx_requires_valid_range(__first, __middle);
1479 __glibcxx_requires_valid_range(__middle, __last);
1481 return std::copy(__first, __middle,
1482 std::copy(__middle, __last, __result));
1486 template<
typename _ForwardIterator,
typename _Predicate>
1491 if (__first == __last)
1494 while (__pred(*__first))
1495 if (++__first == __last)
1498 _ForwardIterator __next = __first;
1500 while (++__next != __last)
1501 if (__pred(*__next))
1511 template<
typename _B
idirectionalIterator,
typename _Predicate>
1512 _BidirectionalIterator
1513 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1519 if (__first == __last)
1521 else if (__pred(*__first))
1527 if (__first == __last)
1529 else if (!
bool(__pred(*__last)))
1546 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1550 _ForwardIterator __last,
1551 _Predicate __pred, _Distance __len,
1553 _Distance __buffer_size)
1558 if (__len <= __buffer_size)
1560 _ForwardIterator __result1 = __first;
1561 _Pointer __result2 = __buffer;
1566 *__result2 = _GLIBCXX_MOVE(*__first);
1569 for (; __first != __last; ++__first)
1570 if (__pred(__first))
1572 *__result1 = _GLIBCXX_MOVE(*__first);
1577 *__result2 = _GLIBCXX_MOVE(*__first);
1581 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1585 _ForwardIterator __middle = __first;
1587 _ForwardIterator __left_split =
1589 __len / 2, __buffer,
1594 _Distance __right_len = __len - __len / 2;
1595 _ForwardIterator __right_split =
1602 __buffer, __buffer_size);
1604 return std::rotate(__left_split, __middle, __right_split);
1607 template<
typename _ForwardIterator,
typename _Predicate>
1609 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1614 if (__first == __last)
1617 typedef typename iterator_traits<_ForwardIterator>::value_type
1619 typedef typename iterator_traits<_ForwardIterator>::difference_type
1622 _Temporary_buffer<_ForwardIterator, _ValueType>
1626 _DistanceType(__buf.requested_size()),
1628 _DistanceType(__buf.size()));
1648 template<
typename _ForwardIterator,
typename _Predicate>
1649 inline _ForwardIterator
1650 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1654 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1656 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1657 typename iterator_traits<_ForwardIterator>::value_type>)
1658 __glibcxx_requires_valid_range(__first, __last);
1660 return std::__stable_partition(__first, __last,
1661 __gnu_cxx::__ops::__pred_iter(__pred));
1665 template<
typename _RandomAccessIterator,
typename _Compare>
1668 _RandomAccessIterator __middle,
1669 _RandomAccessIterator __last, _Compare __comp)
1671 std::__make_heap(__first, __middle, __comp);
1672 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1673 if (__comp(__i, __first))
1674 std::__pop_heap(__first, __middle, __i, __comp);
1679 template<
typename _InputIterator,
typename _RandomAccessIterator,
1681 _RandomAccessIterator
1682 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1683 _RandomAccessIterator __result_first,
1684 _RandomAccessIterator __result_last,
1687 typedef typename iterator_traits<_InputIterator>::value_type
1689 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1690 typedef typename _RItTraits::difference_type _DistanceType;
1692 if (__result_first == __result_last)
1693 return __result_last;
1694 _RandomAccessIterator __result_real_last = __result_first;
1695 while (__first != __last && __result_real_last != __result_last)
1697 *__result_real_last = *__first;
1698 ++__result_real_last;
1702 std::__make_heap(__result_first, __result_real_last, __comp);
1703 while (__first != __last)
1705 if (__comp(__first, __result_first))
1706 std::__adjust_heap(__result_first, _DistanceType(0),
1707 _DistanceType(__result_real_last
1709 _InputValueType(*__first), __comp);
1712 std::__sort_heap(__result_first, __result_real_last, __comp);
1713 return __result_real_last;
1734 template<
typename _InputIterator,
typename _RandomAccessIterator>
1735 inline _RandomAccessIterator
1736 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1737 _RandomAccessIterator __result_first,
1738 _RandomAccessIterator __result_last)
1740 #ifdef _GLIBCXX_CONCEPT_CHECKS 1741 typedef typename iterator_traits<_InputIterator>::value_type
1743 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1748 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1749 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1751 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1753 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1754 __glibcxx_requires_valid_range(__first, __last);
1755 __glibcxx_requires_irreflexive(__first, __last);
1756 __glibcxx_requires_valid_range(__result_first, __result_last);
1758 return std::__partial_sort_copy(__first, __last,
1759 __result_first, __result_last,
1760 __gnu_cxx::__ops::__iter_less_iter());
1783 template<
typename _InputIterator,
typename _RandomAccessIterator,
1785 inline _RandomAccessIterator
1786 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1787 _RandomAccessIterator __result_first,
1788 _RandomAccessIterator __result_last,
1791 #ifdef _GLIBCXX_CONCEPT_CHECKS 1792 typedef typename iterator_traits<_InputIterator>::value_type
1794 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1799 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1800 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1801 _RandomAccessIterator>)
1802 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1805 _InputValueType, _OutputValueType>)
1806 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1807 _OutputValueType, _OutputValueType>)
1808 __glibcxx_requires_valid_range(__first, __last);
1809 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1810 __glibcxx_requires_valid_range(__result_first, __result_last);
1812 return std::__partial_sort_copy(__first, __last,
1813 __result_first, __result_last,
1814 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1818 template<
typename _RandomAccessIterator,
typename _Compare>
1823 typename iterator_traits<_RandomAccessIterator>::value_type
1824 __val = _GLIBCXX_MOVE(*__last);
1825 _RandomAccessIterator __next = __last;
1827 while (__comp(__val, __next))
1829 *__last = _GLIBCXX_MOVE(*__next);
1833 *__last = _GLIBCXX_MOVE(__val);
1837 template<
typename _RandomAccessIterator,
typename _Compare>
1840 _RandomAccessIterator __last, _Compare __comp)
1842 if (__first == __last)
return;
1844 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1846 if (__comp(__i, __first))
1848 typename iterator_traits<_RandomAccessIterator>::value_type
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>
1863 _RandomAccessIterator __last, _Compare __comp)
1865 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1867 __gnu_cxx::__ops::__val_comp_iter(__comp));
1874 enum { _S_threshold = 16 };
1877 template<
typename _RandomAccessIterator,
typename _Compare>
1880 _RandomAccessIterator __last, _Compare __comp)
1882 if (__last - __first >
int(_S_threshold))
1893 template<
typename _RandomAccessIterator,
typename _Compare>
1894 _RandomAccessIterator
1896 _RandomAccessIterator __last,
1897 _RandomAccessIterator __pivot, _Compare __comp)
1901 while (__comp(__first, __pivot))
1904 while (__comp(__pivot, __last))
1906 if (!(__first < __last))
1914 template<
typename _RandomAccessIterator,
typename _Compare>
1915 inline _RandomAccessIterator
1917 _RandomAccessIterator __last, _Compare __comp)
1919 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1925 template<
typename _RandomAccessIterator,
typename _Compare>
1927 __partial_sort(_RandomAccessIterator __first,
1928 _RandomAccessIterator __middle,
1929 _RandomAccessIterator __last,
1933 std::__sort_heap(__first, __middle, __comp);
1937 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1940 _RandomAccessIterator __last,
1941 _Size __depth_limit, _Compare __comp)
1943 while (__last - __first >
int(_S_threshold))
1945 if (__depth_limit == 0)
1947 std::__partial_sort(__first, __last, __last, __comp);
1951 _RandomAccessIterator __cut =
1960 template<
typename _RandomAccessIterator,
typename _Compare>
1962 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1965 if (__first != __last)
1974 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1976 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1977 _RandomAccessIterator __last, _Size __depth_limit,
1980 while (__last - __first > 3)
1982 if (__depth_limit == 0)
1990 _RandomAccessIterator __cut =
2020 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2021 inline _ForwardIterator
2022 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2023 const _Tp& __val, _Compare __comp)
2026 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2027 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2028 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2029 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2032 return std::__lower_bound(__first, __last, __val,
2033 __gnu_cxx::__ops::__iter_comp_val(__comp));
2036 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2038 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2039 const _Tp& __val, _Compare __comp)
2041 typedef typename iterator_traits<_ForwardIterator>::difference_type
2048 _DistanceType __half = __len >> 1;
2049 _ForwardIterator __middle = __first;
2051 if (__comp(__val, __middle))
2057 __len = __len - __half - 1;
2074 template<
typename _ForwardIterator,
typename _Tp>
2075 inline _ForwardIterator
2076 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2080 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2081 __glibcxx_function_requires(_LessThanOpConcept<
2082 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2083 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2085 return std::__upper_bound(__first, __last, __val,
2086 __gnu_cxx::__ops::__val_less_iter());
2104 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2105 inline _ForwardIterator
2106 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2107 const _Tp& __val, _Compare __comp)
2110 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2111 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2112 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2113 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2116 return std::__upper_bound(__first, __last, __val,
2117 __gnu_cxx::__ops::__val_comp_iter(__comp));
2120 template<
typename _ForwardIterator,
typename _Tp,
2121 typename _CompareItTp,
typename _CompareTpIt>
2122 pair<_ForwardIterator, _ForwardIterator>
2123 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2125 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2127 typedef typename iterator_traits<_ForwardIterator>::difference_type
2134 _DistanceType __half = __len >> 1;
2135 _ForwardIterator __middle = __first;
2137 if (__comp_it_val(__middle, __val))
2141 __len = __len - __half - 1;
2143 else if (__comp_val_it(__val, __middle))
2147 _ForwardIterator __left
2148 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2150 _ForwardIterator __right
2151 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2152 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2155 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2175 template<
typename _ForwardIterator,
typename _Tp>
2176 inline pair<_ForwardIterator, _ForwardIterator>
2177 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2181 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2182 __glibcxx_function_requires(_LessThanOpConcept<
2183 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2184 __glibcxx_function_requires(_LessThanOpConcept<
2185 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2186 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2187 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2189 return std::__equal_range(__first, __last, __val,
2190 __gnu_cxx::__ops::__iter_less_val(),
2191 __gnu_cxx::__ops::__val_less_iter());
2211 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2212 inline pair<_ForwardIterator, _ForwardIterator>
2213 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2214 const _Tp& __val, _Compare __comp)
2217 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2218 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2219 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2220 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2221 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2222 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2224 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2227 return std::__equal_range(__first, __last, __val,
2228 __gnu_cxx::__ops::__iter_comp_val(__comp),
2229 __gnu_cxx::__ops::__val_comp_iter(__comp));
2244 template<
typename _ForwardIterator,
typename _Tp>
2246 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2250 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2251 __glibcxx_function_requires(_LessThanOpConcept<
2252 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2253 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2254 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2256 _ForwardIterator __i
2257 = std::__lower_bound(__first, __last, __val,
2258 __gnu_cxx::__ops::__iter_less_val());
2259 return __i != __last && !(__val < *__i);
2277 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2279 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2280 const _Tp& __val, _Compare __comp)
2283 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2284 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2285 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2286 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2288 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2291 _ForwardIterator __i
2292 = std::__lower_bound(__first, __last, __val,
2293 __gnu_cxx::__ops::__iter_comp_val(__comp));
2294 return __i != __last && !bool(__comp(__val, *__i));
2300 template<
typename _InputIterator1,
typename _InputIterator2,
2301 typename _OutputIterator,
typename _Compare>
2304 _InputIterator2 __first2, _InputIterator2 __last2,
2305 _OutputIterator __result, _Compare __comp)
2307 while (__first1 != __last1 && __first2 != __last2)
2309 if (__comp(__first2, __first1))
2311 *__result = _GLIBCXX_MOVE(*__first2);
2316 *__result = _GLIBCXX_MOVE(*__first1);
2321 if (__first1 != __last1)
2322 _GLIBCXX_MOVE3(__first1, __last1, __result);
2326 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2327 typename _BidirectionalIterator3,
typename _Compare>
2330 _BidirectionalIterator1 __last1,
2331 _BidirectionalIterator2 __first2,
2332 _BidirectionalIterator2 __last2,
2333 _BidirectionalIterator3 __result,
2336 if (__first1 == __last1)
2338 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2341 else if (__first2 == __last2)
2348 if (__comp(__last2, __last1))
2350 *--__result = _GLIBCXX_MOVE(*__last1);
2351 if (__first1 == __last1)
2353 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2360 *--__result = _GLIBCXX_MOVE(*__last2);
2361 if (__first2 == __last2)
2369 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2371 _BidirectionalIterator1
2373 _BidirectionalIterator1 __middle,
2374 _BidirectionalIterator1 __last,
2375 _Distance __len1, _Distance __len2,
2376 _BidirectionalIterator2 __buffer,
2377 _Distance __buffer_size)
2379 _BidirectionalIterator2 __buffer_end;
2380 if (__len1 > __len2 && __len2 <= __buffer_size)
2384 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2385 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2386 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2391 else if (__len1 <= __buffer_size)
2395 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2396 _GLIBCXX_MOVE3(__middle, __last, __first);
2397 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2407 template<
typename _BidirectionalIterator,
typename _Distance,
2408 typename _Pointer,
typename _Compare>
2411 _BidirectionalIterator __middle,
2412 _BidirectionalIterator __last,
2413 _Distance __len1, _Distance __len2,
2414 _Pointer __buffer, _Distance __buffer_size,
2417 if (__len1 <= __len2 && __len1 <= __buffer_size)
2419 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2423 else if (__len2 <= __buffer_size)
2425 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2427 __buffer_end, __last, __comp);
2431 _BidirectionalIterator __first_cut = __first;
2432 _BidirectionalIterator __second_cut = __middle;
2433 _Distance __len11 = 0;
2434 _Distance __len22 = 0;
2435 if (__len1 > __len2)
2437 __len11 = __len1 / 2;
2440 = std::__lower_bound(__middle, __last, *__first_cut,
2441 __gnu_cxx::__ops::__iter_comp_val(__comp));
2446 __len22 = __len2 / 2;
2449 = std::__upper_bound(__first, __middle, *__second_cut,
2450 __gnu_cxx::__ops::__val_comp_iter(__comp));
2454 _BidirectionalIterator __new_middle
2456 __len1 - __len11, __len22, __buffer,
2459 __len22, __buffer, __buffer_size, __comp);
2462 __len2 - __len22, __buffer,
2463 __buffer_size, __comp);
2468 template<
typename _BidirectionalIterator,
typename _Distance,
2472 _BidirectionalIterator __middle,
2473 _BidirectionalIterator __last,
2474 _Distance __len1, _Distance __len2,
2477 if (__len1 == 0 || __len2 == 0)
2480 if (__len1 + __len2 == 2)
2482 if (__comp(__middle, __first))
2487 _BidirectionalIterator __first_cut = __first;
2488 _BidirectionalIterator __second_cut = __middle;
2489 _Distance __len11 = 0;
2490 _Distance __len22 = 0;
2491 if (__len1 > __len2)
2493 __len11 = __len1 / 2;
2496 = std::__lower_bound(__middle, __last, *__first_cut,
2497 __gnu_cxx::__ops::__iter_comp_val(__comp));
2502 __len22 = __len2 / 2;
2505 = std::__upper_bound(__first, __middle, *__second_cut,
2506 __gnu_cxx::__ops::__val_comp_iter(__comp));
2510 _BidirectionalIterator __new_middle
2511 =
std::rotate(__first_cut, __middle, __second_cut);
2513 __len11, __len22, __comp);
2515 __len1 - __len11, __len2 - __len22, __comp);
2518 template<
typename _B
idirectionalIterator,
typename _Compare>
2520 __inplace_merge(_BidirectionalIterator __first,
2521 _BidirectionalIterator __middle,
2522 _BidirectionalIterator __last,
2525 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2527 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2530 if (__first == __middle || __middle == __last)
2533 const _DistanceType __len1 =
std::distance(__first, __middle);
2534 const _DistanceType __len2 =
std::distance(__middle, __last);
2536 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2537 _TmpBuf __buf(__first, __len1 + __len2);
2539 if (__buf.begin() == 0)
2541 (__first, __middle, __last, __len1, __len2, __comp);
2544 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2545 _DistanceType(__buf.size()), __comp);
2566 template<
typename _B
idirectionalIterator>
2568 inplace_merge(_BidirectionalIterator __first,
2569 _BidirectionalIterator __middle,
2570 _BidirectionalIterator __last)
2573 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2574 _BidirectionalIterator>)
2575 __glibcxx_function_requires(_LessThanComparableConcept<
2576 typename iterator_traits<_BidirectionalIterator>::value_type>)
2577 __glibcxx_requires_sorted(__first, __middle);
2578 __glibcxx_requires_sorted(__middle, __last);
2579 __glibcxx_requires_irreflexive(__first, __last);
2581 std::__inplace_merge(__first, __middle, __last,
2582 __gnu_cxx::__ops::__iter_less_iter());
2607 template<
typename _B
idirectionalIterator,
typename _Compare>
2609 inplace_merge(_BidirectionalIterator __first,
2610 _BidirectionalIterator __middle,
2611 _BidirectionalIterator __last,
2615 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2616 _BidirectionalIterator>)
2617 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2618 typename iterator_traits<_BidirectionalIterator>::value_type,
2619 typename iterator_traits<_BidirectionalIterator>::value_type>)
2620 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2621 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2622 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2624 std::__inplace_merge(__first, __middle, __last,
2625 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2630 template<
typename _InputIterator,
typename _OutputIterator,
2634 _InputIterator __first2, _InputIterator __last2,
2635 _OutputIterator __result, _Compare __comp)
2637 while (__first1 != __last1 && __first2 != __last2)
2639 if (__comp(__first2, __first1))
2641 *__result = _GLIBCXX_MOVE(*__first2);
2646 *__result = _GLIBCXX_MOVE(*__first1);
2651 return _GLIBCXX_MOVE3(__first2, __last2,
2652 _GLIBCXX_MOVE3(__first1, __last1,
2656 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2657 typename _Distance,
typename _Compare>
2659 __merge_sort_loop(_RandomAccessIterator1 __first,
2660 _RandomAccessIterator1 __last,
2661 _RandomAccessIterator2 __result, _Distance __step_size,
2664 const _Distance __two_step = 2 * __step_size;
2666 while (__last - __first >= __two_step)
2669 __first + __step_size,
2670 __first + __two_step,
2672 __first += __two_step;
2674 __step_size =
std::min(_Distance(__last - __first), __step_size);
2677 __first + __step_size, __last, __result, __comp);
2680 template<
typename _RandomAccessIterator,
typename _Distance,
2683 __chunk_insertion_sort(_RandomAccessIterator __first,
2684 _RandomAccessIterator __last,
2685 _Distance __chunk_size, _Compare __comp)
2687 while (__last - __first >= __chunk_size)
2690 __first += __chunk_size;
2695 enum { _S_chunk_size = 7 };
2697 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2699 __merge_sort_with_buffer(_RandomAccessIterator __first,
2700 _RandomAccessIterator __last,
2701 _Pointer __buffer, _Compare __comp)
2703 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2706 const _Distance __len = __last - __first;
2707 const _Pointer __buffer_last = __buffer + __len;
2709 _Distance __step_size = _S_chunk_size;
2710 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2712 while (__step_size < __len)
2714 std::__merge_sort_loop(__first, __last, __buffer,
2715 __step_size, __comp);
2717 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2718 __step_size, __comp);
2723 template<
typename _RandomAccessIterator,
typename _Pointer,
2724 typename _Distance,
typename _Compare>
2726 __stable_sort_adaptive(_RandomAccessIterator __first,
2727 _RandomAccessIterator __last,
2728 _Pointer __buffer, _Distance __buffer_size,
2731 const _Distance __len = (__last - __first + 1) / 2;
2732 const _RandomAccessIterator __middle = __first + __len;
2733 if (__len > __buffer_size)
2735 std::__stable_sort_adaptive(__first, __middle, __buffer,
2736 __buffer_size, __comp);
2737 std::__stable_sort_adaptive(__middle, __last, __buffer,
2738 __buffer_size, __comp);
2742 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2743 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2746 _Distance(__middle - __first),
2747 _Distance(__last - __middle),
2748 __buffer, __buffer_size,
2753 template<
typename _RandomAccessIterator,
typename _Compare>
2756 _RandomAccessIterator __last, _Compare __comp)
2758 if (__last - __first < 15)
2763 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2779 template<
typename _InputIterator1,
typename _InputIterator2,
2782 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2783 _InputIterator2 __first2, _InputIterator2 __last2,
2786 while (__first1 != __last1 && __first2 != __last2)
2787 if (__comp(__first2, __first1))
2789 else if (__comp(__first1, __first2))
2797 return __first2 == __last2;
2818 template<
typename _InputIterator1,
typename _InputIterator2>
2820 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2821 _InputIterator2 __first2, _InputIterator2 __last2)
2824 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2825 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2826 __glibcxx_function_requires(_LessThanOpConcept<
2827 typename iterator_traits<_InputIterator1>::value_type,
2828 typename iterator_traits<_InputIterator2>::value_type>)
2829 __glibcxx_function_requires(_LessThanOpConcept<
2830 typename iterator_traits<_InputIterator2>::value_type,
2831 typename iterator_traits<_InputIterator1>::value_type>)
2832 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2833 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2834 __glibcxx_requires_irreflexive2(__first1, __last1);
2835 __glibcxx_requires_irreflexive2(__first2, __last2);
2837 return std::__includes(__first1, __last1, __first2, __last2,
2838 __gnu_cxx::__ops::__iter_less_iter());
2862 template<
typename _InputIterator1,
typename _InputIterator2,
2865 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2866 _InputIterator2 __first2, _InputIterator2 __last2,
2870 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2872 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2873 typename iterator_traits<_InputIterator1>::value_type,
2874 typename iterator_traits<_InputIterator2>::value_type>)
2875 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2876 typename iterator_traits<_InputIterator2>::value_type,
2877 typename iterator_traits<_InputIterator1>::value_type>)
2878 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2879 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2880 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2881 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2883 return std::__includes(__first1, __last1, __first2, __last2,
2884 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2897 template<
typename _B
idirectionalIterator,
typename _Compare>
2899 __next_permutation(_BidirectionalIterator __first,
2900 _BidirectionalIterator __last, _Compare __comp)
2902 if (__first == __last)
2904 _BidirectionalIterator __i = __first;
2913 _BidirectionalIterator __ii = __i;
2915 if (__comp(__i, __ii))
2917 _BidirectionalIterator __j = __last;
2918 while (!__comp(__i, --__j))
2946 template<
typename _B
idirectionalIterator>
2948 next_permutation(_BidirectionalIterator __first,
2949 _BidirectionalIterator __last)
2952 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2953 _BidirectionalIterator>)
2954 __glibcxx_function_requires(_LessThanComparableConcept<
2955 typename iterator_traits<_BidirectionalIterator>::value_type>)
2956 __glibcxx_requires_valid_range(__first, __last);
2957 __glibcxx_requires_irreflexive(__first, __last);
2959 return std::__next_permutation
2960 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2978 template<
typename _B
idirectionalIterator,
typename _Compare>
2980 next_permutation(_BidirectionalIterator __first,
2981 _BidirectionalIterator __last, _Compare __comp)
2984 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2985 _BidirectionalIterator>)
2986 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2987 typename iterator_traits<_BidirectionalIterator>::value_type,
2988 typename iterator_traits<_BidirectionalIterator>::value_type>)
2989 __glibcxx_requires_valid_range(__first, __last);
2990 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2992 return std::__next_permutation
2993 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2996 template<
typename _B
idirectionalIterator,
typename _Compare>
2998 __prev_permutation(_BidirectionalIterator __first,
2999 _BidirectionalIterator __last, _Compare __comp)
3001 if (__first == __last)
3003 _BidirectionalIterator __i = __first;
3012 _BidirectionalIterator __ii = __i;
3014 if (__comp(__ii, __i))
3016 _BidirectionalIterator __j = __last;
3017 while (!__comp(--__j, __i))
3046 template<
typename _B
idirectionalIterator>
3048 prev_permutation(_BidirectionalIterator __first,
3049 _BidirectionalIterator __last)
3052 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3053 _BidirectionalIterator>)
3054 __glibcxx_function_requires(_LessThanComparableConcept<
3055 typename iterator_traits<_BidirectionalIterator>::value_type>)
3056 __glibcxx_requires_valid_range(__first, __last);
3057 __glibcxx_requires_irreflexive(__first, __last);
3059 return std::__prev_permutation(__first, __last,
3060 __gnu_cxx::__ops::__iter_less_iter());
3078 template<
typename _B
idirectionalIterator,
typename _Compare>
3080 prev_permutation(_BidirectionalIterator __first,
3081 _BidirectionalIterator __last, _Compare __comp)
3084 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3085 _BidirectionalIterator>)
3086 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3087 typename iterator_traits<_BidirectionalIterator>::value_type,
3088 typename iterator_traits<_BidirectionalIterator>::value_type>)
3089 __glibcxx_requires_valid_range(__first, __last);
3090 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3092 return std::__prev_permutation(__first, __last,
3093 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3099 template<
typename _InputIterator,
typename _OutputIterator,
3100 typename _Predicate,
typename _Tp>
3102 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3103 _OutputIterator __result,
3104 _Predicate __pred,
const _Tp& __new_value)
3106 for (; __first != __last; ++__first, (void)++__result)
3107 if (__pred(__first))
3108 *__result = __new_value;
3110 *__result = *__first;
3128 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3129 inline _OutputIterator
3130 replace_copy(_InputIterator __first, _InputIterator __last,
3131 _OutputIterator __result,
3132 const _Tp& __old_value,
const _Tp& __new_value)
3135 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3136 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3137 typename iterator_traits<_InputIterator>::value_type>)
3138 __glibcxx_function_requires(_EqualOpConcept<
3139 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3140 __glibcxx_requires_valid_range(__first, __last);
3142 return std::__replace_copy_if(__first, __last, __result,
3143 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3162 template<
typename _InputIterator,
typename _OutputIterator,
3163 typename _Predicate,
typename _Tp>
3164 inline _OutputIterator
3165 replace_copy_if(_InputIterator __first, _InputIterator __last,
3166 _OutputIterator __result,
3167 _Predicate __pred,
const _Tp& __new_value)
3170 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3172 typename iterator_traits<_InputIterator>::value_type>)
3173 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3174 typename iterator_traits<_InputIterator>::value_type>)
3175 __glibcxx_requires_valid_range(__first, __last);
3177 return std::__replace_copy_if(__first, __last, __result,
3178 __gnu_cxx::__ops::__pred_iter(__pred),
3182 template<
typename _InputIterator,
typename _Predicate>
3183 typename iterator_traits<_InputIterator>::difference_type
3184 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3186 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3187 for (; __first != __last; ++__first)
3188 if (__pred(__first))
3193 #if __cplusplus >= 201103L 3201 template<
typename _ForwardIterator>
3203 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3215 template<
typename _ForwardIterator,
typename _Compare>
3217 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3221 template<
typename _ForwardIterator,
typename _Compare>
3223 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3226 if (__first == __last)
3229 _ForwardIterator __next = __first;
3230 for (++__next; __next != __last; __first = __next, (void)++__next)
3231 if (__comp(__next, __first))
3244 template<
typename _ForwardIterator>
3245 inline _ForwardIterator
3246 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3249 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3250 __glibcxx_function_requires(_LessThanComparableConcept<
3251 typename iterator_traits<_ForwardIterator>::value_type>)
3252 __glibcxx_requires_valid_range(__first, __last);
3253 __glibcxx_requires_irreflexive(__first, __last);
3255 return std::__is_sorted_until(__first, __last,
3256 __gnu_cxx::__ops::__iter_less_iter());
3268 template<
typename _ForwardIterator,
typename _Compare>
3269 inline _ForwardIterator
3270 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3274 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3275 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3276 typename iterator_traits<_ForwardIterator>::value_type,
3277 typename iterator_traits<_ForwardIterator>::value_type>)
3278 __glibcxx_requires_valid_range(__first, __last);
3279 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3281 return std::__is_sorted_until(__first, __last,
3282 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3293 template<
typename _Tp>
3294 _GLIBCXX14_CONSTEXPR
3295 inline pair<const _Tp&, const _Tp&>
3299 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3301 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3314 template<
typename _Tp,
typename _Compare>
3315 _GLIBCXX14_CONSTEXPR
3316 inline pair<const _Tp&, const _Tp&>
3317 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3323 template<
typename _ForwardIterator,
typename _Compare>
3324 _GLIBCXX14_CONSTEXPR
3325 pair<_ForwardIterator, _ForwardIterator>
3326 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3329 _ForwardIterator __next = __first;
3330 if (__first == __last
3331 || ++__next == __last)
3334 _ForwardIterator __min{}, __max{};
3335 if (__comp(__next, __first))
3349 while (__first != __last)
3352 if (++__next == __last)
3354 if (__comp(__first, __min))
3356 else if (!__comp(__first, __max))
3361 if (__comp(__next, __first))
3363 if (__comp(__next, __min))
3365 if (!__comp(__first, __max))
3370 if (__comp(__first, __min))
3372 if (!__comp(__next, __max))
3394 template<
typename _ForwardIterator>
3395 _GLIBCXX14_CONSTEXPR
3396 inline pair<_ForwardIterator, _ForwardIterator>
3397 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3400 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3401 __glibcxx_function_requires(_LessThanComparableConcept<
3402 typename iterator_traits<_ForwardIterator>::value_type>)
3403 __glibcxx_requires_valid_range(__first, __last);
3404 __glibcxx_requires_irreflexive(__first, __last);
3406 return std::__minmax_element(__first, __last,
3407 __gnu_cxx::__ops::__iter_less_iter());
3422 template<
typename _ForwardIterator,
typename _Compare>
3423 _GLIBCXX14_CONSTEXPR
3424 inline pair<_ForwardIterator, _ForwardIterator>
3425 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3430 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3431 typename iterator_traits<_ForwardIterator>::value_type,
3432 typename iterator_traits<_ForwardIterator>::value_type>)
3433 __glibcxx_requires_valid_range(__first, __last);
3434 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3436 return std::__minmax_element(__first, __last,
3437 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3441 template<
typename _Tp>
3442 _GLIBCXX14_CONSTEXPR
3444 min(initializer_list<_Tp> __l)
3445 {
return *std::min_element(__l.begin(), __l.end()); }
3447 template<
typename _Tp,
typename _Compare>
3448 _GLIBCXX14_CONSTEXPR
3450 min(initializer_list<_Tp> __l, _Compare __comp)
3453 template<
typename _Tp>
3454 _GLIBCXX14_CONSTEXPR
3456 max(initializer_list<_Tp> __l)
3459 template<
typename _Tp,
typename _Compare>
3460 _GLIBCXX14_CONSTEXPR
3462 max(initializer_list<_Tp> __l, _Compare __comp)
3465 template<
typename _Tp>
3466 _GLIBCXX14_CONSTEXPR
3467 inline pair<_Tp, _Tp>
3468 minmax(initializer_list<_Tp> __l)
3470 pair<const _Tp*, const _Tp*> __p =
3475 template<
typename _Tp,
typename _Compare>
3476 _GLIBCXX14_CONSTEXPR
3477 inline pair<_Tp, _Tp>
3478 minmax(initializer_list<_Tp> __l, _Compare __comp)
3480 pair<const _Tp*, const _Tp*> __p =
3485 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3486 typename _BinaryPredicate>
3488 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3489 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3493 for (; __first1 != __last1; ++__first1, (void)++__first2)
3494 if (!__pred(__first1, __first2))
3497 if (__first1 == __last1)
3502 _ForwardIterator2 __last2 = __first2;
3504 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3507 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3511 = std::__count_if(__first2, __last2,
3512 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3513 if (0 == __matches ||
3514 std::__count_if(__scan, __last1,
3515 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3534 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3536 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3537 _ForwardIterator2 __first2)
3540 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3541 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3542 __glibcxx_function_requires(_EqualOpConcept<
3543 typename iterator_traits<_ForwardIterator1>::value_type,
3544 typename iterator_traits<_ForwardIterator2>::value_type>)
3545 __glibcxx_requires_valid_range(__first1, __last1);
3547 return std::__is_permutation(__first1, __last1, __first2,
3548 __gnu_cxx::__ops::__iter_equal_to_iter());
3565 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3566 typename _BinaryPredicate>
3568 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3569 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3572 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3573 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3574 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3575 typename iterator_traits<_ForwardIterator1>::value_type,
3576 typename iterator_traits<_ForwardIterator2>::value_type>)
3577 __glibcxx_requires_valid_range(__first1, __last1);
3579 return std::__is_permutation(__first1, __last1, __first2,
3580 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3583 #if __cplusplus > 201103L 3584 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3585 typename _BinaryPredicate>
3587 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3588 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3589 _BinaryPredicate __pred)
3592 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3594 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3595 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3596 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3597 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3608 for (; __first1 != __last1 && __first2 != __last2;
3609 ++__first1, (void)++__first2)
3610 if (!__pred(__first1, __first2))
3615 if (__first1 == __last1)
3622 if (__d1 == 0 && __d2 == 0)
3628 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3631 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3634 auto __matches = std::__count_if(__first2, __last2,
3635 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3637 || std::__count_if(__scan, __last1,
3638 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3658 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3660 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3661 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3663 __glibcxx_requires_valid_range(__first1, __last1);
3664 __glibcxx_requires_valid_range(__first2, __last2);
3667 std::__is_permutation(__first1, __last1, __first2, __last2,
3668 __gnu_cxx::__ops::__iter_equal_to_iter());
3685 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3686 typename _BinaryPredicate>
3688 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3689 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3690 _BinaryPredicate __pred)
3692 __glibcxx_requires_valid_range(__first1, __last1);
3693 __glibcxx_requires_valid_range(__first2, __last2);
3695 return std::__is_permutation(__first1, __last1, __first2, __last2,
3696 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3699 #if __cplusplus > 201402L 3701 #define __cpp_lib_clamp 201603 3711 template<
typename _Tp>
3712 constexpr
const _Tp&
3713 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3715 __glibcxx_assert(!(__hi < __lo));
3716 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3729 template<
typename _Tp,
typename _Compare>
3730 constexpr
const _Tp&
3731 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3733 __glibcxx_assert(!__comp(__hi, __lo));
3734 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3739 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3761 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3762 pair<_IntType, _IntType>
3764 _UniformRandomBitGenerator&& __g)
3783 template<
typename _RandomAccessIterator,
3784 typename _UniformRandomNumberGenerator>
3786 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3787 _UniformRandomNumberGenerator&& __g)
3790 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3791 _RandomAccessIterator>)
3792 __glibcxx_requires_valid_range(__first, __last);
3794 if (__first == __last)
3797 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3800 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3802 typedef typename __distr_type::param_type __p_type;
3804 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3809 const __uc_type __urngrange = __g.max() - __g.min();
3810 const __uc_type __urange = __uc_type(__last - __first);
3812 if (__urngrange / __urange >= __urange)
3815 _RandomAccessIterator __i = __first + 1;
3821 if ((__urange % 2) == 0)
3823 __distr_type __d{0, 1};
3831 while (__i != __last)
3833 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3847 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3848 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3854 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3868 template<
typename _InputIterator,
typename _Function>
3870 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3873 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3874 __glibcxx_requires_valid_range(__first, __last);
3875 for (; __first != __last; ++__first)
3880 #if __cplusplus >= 201703L 3893 template<
typename _InputIterator,
typename _Size,
typename _Function>
3895 for_each_n(_InputIterator __first, _Size __n, _Function __f)
3897 typename iterator_traits<_InputIterator>::difference_type __n2 = __n;
3898 using _Cat =
typename iterator_traits<_InputIterator>::iterator_category;
3899 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3901 auto __last = __first + __n2;
3902 std::for_each(__first, __last, std::move(__f));
3926 template<
typename _InputIterator,
typename _Tp>
3927 inline _InputIterator
3928 find(_InputIterator __first, _InputIterator __last,
3932 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3933 __glibcxx_function_requires(_EqualOpConcept<
3934 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3935 __glibcxx_requires_valid_range(__first, __last);
3937 __gnu_cxx::__ops::__iter_equals_val(__val));
3950 template<
typename _InputIterator,
typename _Predicate>
3951 inline _InputIterator
3952 find_if(_InputIterator __first, _InputIterator __last,
3956 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3957 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3958 typename iterator_traits<_InputIterator>::value_type>)
3959 __glibcxx_requires_valid_range(__first, __last);
3962 __gnu_cxx::__ops::__pred_iter(__pred));
3981 template<
typename _InputIterator,
typename _ForwardIterator>
3983 find_first_of(_InputIterator __first1, _InputIterator __last1,
3984 _ForwardIterator __first2, _ForwardIterator __last2)
3987 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3988 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3989 __glibcxx_function_requires(_EqualOpConcept<
3990 typename iterator_traits<_InputIterator>::value_type,
3991 typename iterator_traits<_ForwardIterator>::value_type>)
3992 __glibcxx_requires_valid_range(__first1, __last1);
3993 __glibcxx_requires_valid_range(__first2, __last2);
3995 for (; __first1 != __last1; ++__first1)
3996 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3997 if (*__first1 == *__iter)
4021 template<
typename _InputIterator,
typename _ForwardIterator,
4022 typename _BinaryPredicate>
4024 find_first_of(_InputIterator __first1, _InputIterator __last1,
4025 _ForwardIterator __first2, _ForwardIterator __last2,
4026 _BinaryPredicate __comp)
4029 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4030 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4031 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4032 typename iterator_traits<_InputIterator>::value_type,
4033 typename iterator_traits<_ForwardIterator>::value_type>)
4034 __glibcxx_requires_valid_range(__first1, __last1);
4035 __glibcxx_requires_valid_range(__first2, __last2);
4037 for (; __first1 != __last1; ++__first1)
4038 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4039 if (__comp(*__first1, *__iter))
4053 template<
typename _ForwardIterator>
4054 inline _ForwardIterator
4055 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4058 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4059 __glibcxx_function_requires(_EqualityComparableConcept<
4060 typename iterator_traits<_ForwardIterator>::value_type>)
4061 __glibcxx_requires_valid_range(__first, __last);
4063 return std::__adjacent_find(__first, __last,
4064 __gnu_cxx::__ops::__iter_equal_to_iter());
4078 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4079 inline _ForwardIterator
4080 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4081 _BinaryPredicate __binary_pred)
4084 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4085 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4086 typename iterator_traits<_ForwardIterator>::value_type,
4087 typename iterator_traits<_ForwardIterator>::value_type>)
4088 __glibcxx_requires_valid_range(__first, __last);
4090 return std::__adjacent_find(__first, __last,
4091 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4103 template<
typename _InputIterator,
typename _Tp>
4104 inline typename iterator_traits<_InputIterator>::difference_type
4105 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4108 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4109 __glibcxx_function_requires(_EqualOpConcept<
4110 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4111 __glibcxx_requires_valid_range(__first, __last);
4113 return std::__count_if(__first, __last,
4114 __gnu_cxx::__ops::__iter_equals_val(__value));
4126 template<
typename _InputIterator,
typename _Predicate>
4127 inline typename iterator_traits<_InputIterator>::difference_type
4128 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4131 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4132 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4133 typename iterator_traits<_InputIterator>::value_type>)
4134 __glibcxx_requires_valid_range(__first, __last);
4136 return std::__count_if(__first, __last,
4137 __gnu_cxx::__ops::__pred_iter(__pred));
4166 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4167 inline _ForwardIterator1
4168 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4169 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4172 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4173 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4174 __glibcxx_function_requires(_EqualOpConcept<
4175 typename iterator_traits<_ForwardIterator1>::value_type,
4176 typename iterator_traits<_ForwardIterator2>::value_type>)
4177 __glibcxx_requires_valid_range(__first1, __last1);
4178 __glibcxx_requires_valid_range(__first2, __last2);
4180 return std::__search(__first1, __last1, __first2, __last2,
4181 __gnu_cxx::__ops::__iter_equal_to_iter());
4205 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4206 typename _BinaryPredicate>
4207 inline _ForwardIterator1
4208 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4209 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4210 _BinaryPredicate __predicate)
4213 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4214 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4215 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4216 typename iterator_traits<_ForwardIterator1>::value_type,
4217 typename iterator_traits<_ForwardIterator2>::value_type>)
4218 __glibcxx_requires_valid_range(__first1, __last1);
4219 __glibcxx_requires_valid_range(__first2, __last2);
4221 return std::__search(__first1, __last1, __first2, __last2,
4222 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4240 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4241 inline _ForwardIterator
4242 search_n(_ForwardIterator __first, _ForwardIterator __last,
4243 _Integer __count,
const _Tp& __val)
4246 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4247 __glibcxx_function_requires(_EqualOpConcept<
4248 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4249 __glibcxx_requires_valid_range(__first, __last);
4251 return std::__search_n(__first, __last, __count,
4252 __gnu_cxx::__ops::__iter_equals_val(__val));
4273 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4274 typename _BinaryPredicate>
4275 inline _ForwardIterator
4276 search_n(_ForwardIterator __first, _ForwardIterator __last,
4277 _Integer __count,
const _Tp& __val,
4278 _BinaryPredicate __binary_pred)
4281 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4282 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4283 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4284 __glibcxx_requires_valid_range(__first, __last);
4286 return std::__search_n(__first, __last, __count,
4287 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4290 #if __cplusplus > 201402L 4298 template<
typename _ForwardIterator,
typename _Searcher>
4299 inline _ForwardIterator
4300 search(_ForwardIterator __first, _ForwardIterator __last,
4301 const _Searcher& __searcher)
4302 {
return __searcher(__first, __last).first; }
4321 template<
typename _InputIterator,
typename _OutputIterator,
4322 typename _UnaryOperation>
4324 transform(_InputIterator __first, _InputIterator __last,
4325 _OutputIterator __result, _UnaryOperation __unary_op)
4328 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4329 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4331 __typeof__(__unary_op(*__first))>)
4332 __glibcxx_requires_valid_range(__first, __last);
4334 for (; __first != __last; ++__first, (void)++__result)
4335 *__result = __unary_op(*__first);
4358 template<
typename _InputIterator1,
typename _InputIterator2,
4359 typename _OutputIterator,
typename _BinaryOperation>
4361 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4362 _InputIterator2 __first2, _OutputIterator __result,
4363 _BinaryOperation __binary_op)
4366 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4367 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4368 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4370 __typeof__(__binary_op(*__first1,*__first2))>)
4371 __glibcxx_requires_valid_range(__first1, __last1);
4373 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4374 *__result = __binary_op(*__first1, *__first2);
4391 template<
typename _ForwardIterator,
typename _Tp>
4393 replace(_ForwardIterator __first, _ForwardIterator __last,
4394 const _Tp& __old_value,
const _Tp& __new_value)
4397 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4399 __glibcxx_function_requires(_EqualOpConcept<
4400 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4401 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4402 typename iterator_traits<_ForwardIterator>::value_type>)
4403 __glibcxx_requires_valid_range(__first, __last);
4405 for (; __first != __last; ++__first)
4406 if (*__first == __old_value)
4407 *__first = __new_value;
4423 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4425 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4426 _Predicate __pred,
const _Tp& __new_value)
4429 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4431 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4432 typename iterator_traits<_ForwardIterator>::value_type>)
4433 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4434 typename iterator_traits<_ForwardIterator>::value_type>)
4435 __glibcxx_requires_valid_range(__first, __last);
4437 for (; __first != __last; ++__first)
4438 if (__pred(*__first))
4439 *__first = __new_value;
4455 template<
typename _ForwardIterator,
typename _Generator>
4457 generate(_ForwardIterator __first, _ForwardIterator __last,
4461 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4462 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4463 typename iterator_traits<_ForwardIterator>::value_type>)
4464 __glibcxx_requires_valid_range(__first, __last);
4466 for (; __first != __last; ++__first)
4486 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4488 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4491 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4493 __typeof__(__gen())>)
4495 for (__decltype(__n + 0) __niter = __n;
4496 __niter > 0; --__niter, (void) ++__first)
4522 template<
typename _InputIterator,
typename _OutputIterator>
4523 inline _OutputIterator
4524 unique_copy(_InputIterator __first, _InputIterator __last,
4525 _OutputIterator __result)
4528 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4529 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4530 typename iterator_traits<_InputIterator>::value_type>)
4531 __glibcxx_function_requires(_EqualityComparableConcept<
4532 typename iterator_traits<_InputIterator>::value_type>)
4533 __glibcxx_requires_valid_range(__first, __last);
4535 if (__first == __last)
4538 __gnu_cxx::__ops::__iter_equal_to_iter(),
4562 template<
typename _InputIterator,
typename _OutputIterator,
4563 typename _BinaryPredicate>
4564 inline _OutputIterator
4565 unique_copy(_InputIterator __first, _InputIterator __last,
4566 _OutputIterator __result,
4567 _BinaryPredicate __binary_pred)
4570 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4571 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4572 typename iterator_traits<_InputIterator>::value_type>)
4573 __glibcxx_requires_valid_range(__first, __last);
4575 if (__first == __last)
4578 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4595 template<
typename _RandomAccessIterator>
4597 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4600 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4601 _RandomAccessIterator>)
4602 __glibcxx_requires_valid_range(__first, __last);
4604 if (__first != __last)
4605 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4608 _RandomAccessIterator __j = __first
4609 + std::rand() % ((__i - __first) + 1);
4611 std::iter_swap(__i, __j);
4630 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4632 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4633 #
if __cplusplus >= 201103L
4634 _RandomNumberGenerator&& __rand)
4636 _RandomNumberGenerator& __rand)
4640 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4641 _RandomAccessIterator>)
4642 __glibcxx_requires_valid_range(__first, __last);
4644 if (__first == __last)
4646 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4648 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4670 template<
typename _ForwardIterator,
typename _Predicate>
4671 inline _ForwardIterator
4672 partition(_ForwardIterator __first, _ForwardIterator __last,
4676 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4678 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4679 typename iterator_traits<_ForwardIterator>::value_type>)
4680 __glibcxx_requires_valid_range(__first, __last);
4703 template<
typename _RandomAccessIterator>
4705 partial_sort(_RandomAccessIterator __first,
4706 _RandomAccessIterator __middle,
4707 _RandomAccessIterator __last)
4710 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4711 _RandomAccessIterator>)
4712 __glibcxx_function_requires(_LessThanComparableConcept<
4713 typename iterator_traits<_RandomAccessIterator>::value_type>)
4714 __glibcxx_requires_valid_range(__first, __middle);
4715 __glibcxx_requires_valid_range(__middle, __last);
4716 __glibcxx_requires_irreflexive(__first, __last);
4718 std::__partial_sort(__first, __middle, __last,
4719 __gnu_cxx::__ops::__iter_less_iter());
4741 template<
typename _RandomAccessIterator,
typename _Compare>
4743 partial_sort(_RandomAccessIterator __first,
4744 _RandomAccessIterator __middle,
4745 _RandomAccessIterator __last,
4749 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4750 _RandomAccessIterator>)
4751 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4752 typename iterator_traits<_RandomAccessIterator>::value_type,
4753 typename iterator_traits<_RandomAccessIterator>::value_type>)
4754 __glibcxx_requires_valid_range(__first, __middle);
4755 __glibcxx_requires_valid_range(__middle, __last);
4756 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4758 std::__partial_sort(__first, __middle, __last,
4759 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4777 template<
typename _RandomAccessIterator>
4779 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4780 _RandomAccessIterator __last)
4783 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4784 _RandomAccessIterator>)
4785 __glibcxx_function_requires(_LessThanComparableConcept<
4786 typename iterator_traits<_RandomAccessIterator>::value_type>)
4787 __glibcxx_requires_valid_range(__first, __nth);
4788 __glibcxx_requires_valid_range(__nth, __last);
4789 __glibcxx_requires_irreflexive(__first, __last);
4791 if (__first == __last || __nth == __last)
4794 std::__introselect(__first, __nth, __last,
4796 __gnu_cxx::__ops::__iter_less_iter());
4816 template<
typename _RandomAccessIterator,
typename _Compare>
4818 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4819 _RandomAccessIterator __last, _Compare __comp)
4822 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4823 _RandomAccessIterator>)
4824 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4825 typename iterator_traits<_RandomAccessIterator>::value_type,
4826 typename iterator_traits<_RandomAccessIterator>::value_type>)
4827 __glibcxx_requires_valid_range(__first, __nth);
4828 __glibcxx_requires_valid_range(__nth, __last);
4829 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4831 if (__first == __last || __nth == __last)
4834 std::__introselect(__first, __nth, __last,
4836 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4853 template<
typename _RandomAccessIterator>
4855 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4858 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4859 _RandomAccessIterator>)
4860 __glibcxx_function_requires(_LessThanComparableConcept<
4861 typename iterator_traits<_RandomAccessIterator>::value_type>)
4862 __glibcxx_requires_valid_range(__first, __last);
4863 __glibcxx_requires_irreflexive(__first, __last);
4865 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4883 template<
typename _RandomAccessIterator,
typename _Compare>
4885 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4889 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4890 _RandomAccessIterator>)
4891 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4892 typename iterator_traits<_RandomAccessIterator>::value_type,
4893 typename iterator_traits<_RandomAccessIterator>::value_type>)
4894 __glibcxx_requires_valid_range(__first, __last);
4895 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4897 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4900 template<
typename _InputIterator1,
typename _InputIterator2,
4901 typename _OutputIterator,
typename _Compare>
4903 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4904 _InputIterator2 __first2, _InputIterator2 __last2,
4905 _OutputIterator __result, _Compare __comp)
4907 while (__first1 != __last1 && __first2 != __last2)
4909 if (__comp(__first2, __first1))
4911 *__result = *__first2;
4916 *__result = *__first1;
4921 return std::copy(__first2, __last2,
4922 std::copy(__first1, __last1, __result));
4944 template<
typename _InputIterator1,
typename _InputIterator2,
4945 typename _OutputIterator>
4946 inline _OutputIterator
4947 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4948 _InputIterator2 __first2, _InputIterator2 __last2,
4949 _OutputIterator __result)
4952 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4953 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4954 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4955 typename iterator_traits<_InputIterator1>::value_type>)
4956 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4957 typename iterator_traits<_InputIterator2>::value_type>)
4958 __glibcxx_function_requires(_LessThanOpConcept<
4959 typename iterator_traits<_InputIterator2>::value_type,
4960 typename iterator_traits<_InputIterator1>::value_type>)
4961 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4962 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4963 __glibcxx_requires_irreflexive2(__first1, __last1);
4964 __glibcxx_requires_irreflexive2(__first2, __last2);
4966 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4967 __first2, __last2, __result,
4968 __gnu_cxx::__ops::__iter_less_iter());
4994 template<
typename _InputIterator1,
typename _InputIterator2,
4995 typename _OutputIterator,
typename _Compare>
4996 inline _OutputIterator
4997 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4998 _InputIterator2 __first2, _InputIterator2 __last2,
4999 _OutputIterator __result, _Compare __comp)
5002 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5003 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5004 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5005 typename iterator_traits<_InputIterator1>::value_type>)
5006 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5007 typename iterator_traits<_InputIterator2>::value_type>)
5008 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5009 typename iterator_traits<_InputIterator2>::value_type,
5010 typename iterator_traits<_InputIterator1>::value_type>)
5011 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5012 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5013 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5014 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5016 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5017 __first2, __last2, __result,
5018 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5021 template<
typename _RandomAccessIterator,
typename _Compare>
5023 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5026 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5028 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5031 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5034 if (__buf.begin() == 0)
5037 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5038 _DistanceType(__buf.size()), __comp);
5058 template<
typename _RandomAccessIterator>
5060 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5063 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5064 _RandomAccessIterator>)
5065 __glibcxx_function_requires(_LessThanComparableConcept<
5066 typename iterator_traits<_RandomAccessIterator>::value_type>)
5067 __glibcxx_requires_valid_range(__first, __last);
5068 __glibcxx_requires_irreflexive(__first, __last);
5070 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5071 __gnu_cxx::__ops::__iter_less_iter());
5092 template<
typename _RandomAccessIterator,
typename _Compare>
5094 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5098 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5099 _RandomAccessIterator>)
5100 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5101 typename iterator_traits<_RandomAccessIterator>::value_type,
5102 typename iterator_traits<_RandomAccessIterator>::value_type>)
5103 __glibcxx_requires_valid_range(__first, __last);
5104 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5106 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5107 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5110 template<
typename _InputIterator1,
typename _InputIterator2,
5111 typename _OutputIterator,
5114 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5115 _InputIterator2 __first2, _InputIterator2 __last2,
5116 _OutputIterator __result, _Compare __comp)
5118 while (__first1 != __last1 && __first2 != __last2)
5120 if (__comp(__first1, __first2))
5122 *__result = *__first1;
5125 else if (__comp(__first2, __first1))
5127 *__result = *__first2;
5132 *__result = *__first1;
5138 return std::copy(__first2, __last2,
5139 std::copy(__first1, __last1, __result));
5161 template<
typename _InputIterator1,
typename _InputIterator2,
5162 typename _OutputIterator>
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,
5172 typename iterator_traits<_InputIterator1>::value_type>)
5173 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5174 typename iterator_traits<_InputIterator2>::value_type>)
5175 __glibcxx_function_requires(_LessThanOpConcept<
5176 typename iterator_traits<_InputIterator1>::value_type,
5177 typename iterator_traits<_InputIterator2>::value_type>)
5178 __glibcxx_function_requires(_LessThanOpConcept<
5179 typename iterator_traits<_InputIterator2>::value_type,
5180 typename iterator_traits<_InputIterator1>::value_type>)
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 inline _OutputIterator
5214 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5215 _InputIterator2 __first2, _InputIterator2 __last2,
5216 _OutputIterator __result, _Compare __comp)
5219 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5220 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5221 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5222 typename iterator_traits<_InputIterator1>::value_type>)
5223 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5224 typename iterator_traits<_InputIterator2>::value_type>)
5225 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5226 typename iterator_traits<_InputIterator1>::value_type,
5227 typename iterator_traits<_InputIterator2>::value_type>)
5228 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5229 typename iterator_traits<_InputIterator2>::value_type,
5230 typename iterator_traits<_InputIterator1>::value_type>)
5231 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5232 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5233 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5234 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5236 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5237 __first2, __last2, __result,
5238 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5241 template<
typename _InputIterator1,
typename _InputIterator2,
5242 typename _OutputIterator,
5245 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5246 _InputIterator2 __first2, _InputIterator2 __last2,
5247 _OutputIterator __result, _Compare __comp)
5249 while (__first1 != __last1 && __first2 != __last2)
5250 if (__comp(__first1, __first2))
5252 else if (__comp(__first2, __first1))
5256 *__result = *__first1;
5282 template<
typename _InputIterator1,
typename _InputIterator2,
5283 typename _OutputIterator>
5284 inline _OutputIterator
5285 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5286 _InputIterator2 __first2, _InputIterator2 __last2,
5287 _OutputIterator __result)
5290 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5291 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5292 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5293 typename iterator_traits<_InputIterator1>::value_type>)
5294 __glibcxx_function_requires(_LessThanOpConcept<
5295 typename iterator_traits<_InputIterator1>::value_type,
5296 typename iterator_traits<_InputIterator2>::value_type>)
5297 __glibcxx_function_requires(_LessThanOpConcept<
5298 typename iterator_traits<_InputIterator2>::value_type,
5299 typename iterator_traits<_InputIterator1>::value_type>)
5300 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5301 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5302 __glibcxx_requires_irreflexive2(__first1, __last1);
5303 __glibcxx_requires_irreflexive2(__first2, __last2);
5305 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5306 __first2, __last2, __result,
5307 __gnu_cxx::__ops::__iter_less_iter());
5331 template<
typename _InputIterator1,
typename _InputIterator2,
5332 typename _OutputIterator,
typename _Compare>
5333 inline _OutputIterator
5334 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5335 _InputIterator2 __first2, _InputIterator2 __last2,
5336 _OutputIterator __result, _Compare __comp)
5339 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5340 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5341 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5342 typename iterator_traits<_InputIterator1>::value_type>)
5343 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5344 typename iterator_traits<_InputIterator1>::value_type,
5345 typename iterator_traits<_InputIterator2>::value_type>)
5346 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5347 typename iterator_traits<_InputIterator2>::value_type,
5348 typename iterator_traits<_InputIterator1>::value_type>)
5349 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5350 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5351 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5352 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5354 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5355 __first2, __last2, __result,
5356 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5359 template<
typename _InputIterator1,
typename _InputIterator2,
5360 typename _OutputIterator,
5363 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5364 _InputIterator2 __first2, _InputIterator2 __last2,
5365 _OutputIterator __result, _Compare __comp)
5367 while (__first1 != __last1 && __first2 != __last2)
5368 if (__comp(__first1, __first2))
5370 *__result = *__first1;
5374 else if (__comp(__first2, __first1))
5381 return std::copy(__first1, __last1, __result);
5404 template<
typename _InputIterator1,
typename _InputIterator2,
5405 typename _OutputIterator>
5406 inline _OutputIterator
5407 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5408 _InputIterator2 __first2, _InputIterator2 __last2,
5409 _OutputIterator __result)
5412 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5413 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5414 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5415 typename iterator_traits<_InputIterator1>::value_type>)
5416 __glibcxx_function_requires(_LessThanOpConcept<
5417 typename iterator_traits<_InputIterator1>::value_type,
5418 typename iterator_traits<_InputIterator2>::value_type>)
5419 __glibcxx_function_requires(_LessThanOpConcept<
5420 typename iterator_traits<_InputIterator2>::value_type,
5421 typename iterator_traits<_InputIterator1>::value_type>)
5422 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5423 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5424 __glibcxx_requires_irreflexive2(__first1, __last1);
5425 __glibcxx_requires_irreflexive2(__first2, __last2);
5427 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5428 __first2, __last2, __result,
5429 __gnu_cxx::__ops::__iter_less_iter());
5455 template<
typename _InputIterator1,
typename _InputIterator2,
5456 typename _OutputIterator,
typename _Compare>
5457 inline _OutputIterator
5458 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5459 _InputIterator2 __first2, _InputIterator2 __last2,
5460 _OutputIterator __result, _Compare __comp)
5463 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5464 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5465 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5466 typename iterator_traits<_InputIterator1>::value_type>)
5467 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5468 typename iterator_traits<_InputIterator1>::value_type,
5469 typename iterator_traits<_InputIterator2>::value_type>)
5470 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5471 typename iterator_traits<_InputIterator2>::value_type,
5472 typename iterator_traits<_InputIterator1>::value_type>)
5473 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5474 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5475 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5476 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5478 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5479 __first2, __last2, __result,
5480 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5483 template<
typename _InputIterator1,
typename _InputIterator2,
5484 typename _OutputIterator,
5487 __set_symmetric_difference(_InputIterator1 __first1,
5488 _InputIterator1 __last1,
5489 _InputIterator2 __first2,
5490 _InputIterator2 __last2,
5491 _OutputIterator __result,
5494 while (__first1 != __last1 && __first2 != __last2)
5495 if (__comp(__first1, __first2))
5497 *__result = *__first1;
5501 else if (__comp(__first2, __first1))
5503 *__result = *__first2;
5512 return std::copy(__first2, __last2,
5513 std::copy(__first1, __last1, __result));
5534 template<
typename _InputIterator1,
typename _InputIterator2,
5535 typename _OutputIterator>
5536 inline _OutputIterator
5537 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5538 _InputIterator2 __first2, _InputIterator2 __last2,
5539 _OutputIterator __result)
5542 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5543 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5544 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5545 typename iterator_traits<_InputIterator1>::value_type>)
5546 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5547 typename iterator_traits<_InputIterator2>::value_type>)
5548 __glibcxx_function_requires(_LessThanOpConcept<
5549 typename iterator_traits<_InputIterator1>::value_type,
5550 typename iterator_traits<_InputIterator2>::value_type>)
5551 __glibcxx_function_requires(_LessThanOpConcept<
5552 typename iterator_traits<_InputIterator2>::value_type,
5553 typename iterator_traits<_InputIterator1>::value_type>)
5554 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5555 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5556 __glibcxx_requires_irreflexive2(__first1, __last1);
5557 __glibcxx_requires_irreflexive2(__first2, __last2);
5559 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5560 __first2, __last2, __result,
5561 __gnu_cxx::__ops::__iter_less_iter());
5585 template<
typename _InputIterator1,
typename _InputIterator2,
5586 typename _OutputIterator,
typename _Compare>
5587 inline _OutputIterator
5588 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5589 _InputIterator2 __first2, _InputIterator2 __last2,
5590 _OutputIterator __result,
5594 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5595 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5596 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5597 typename iterator_traits<_InputIterator1>::value_type>)
5598 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5599 typename iterator_traits<_InputIterator2>::value_type>)
5600 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5601 typename iterator_traits<_InputIterator1>::value_type,
5602 typename iterator_traits<_InputIterator2>::value_type>)
5603 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5604 typename iterator_traits<_InputIterator2>::value_type,
5605 typename iterator_traits<_InputIterator1>::value_type>)
5606 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5607 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5608 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5609 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5611 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5612 __first2, __last2, __result,
5613 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5616 template<
typename _ForwardIterator,
typename _Compare>
5617 _GLIBCXX14_CONSTEXPR
5619 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5622 if (__first == __last)
5624 _ForwardIterator __result = __first;
5625 while (++__first != __last)
5626 if (__comp(__first, __result))
5638 template<
typename _ForwardIterator>
5639 _GLIBCXX14_CONSTEXPR
5641 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5644 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5645 __glibcxx_function_requires(_LessThanComparableConcept<
5646 typename iterator_traits<_ForwardIterator>::value_type>)
5647 __glibcxx_requires_valid_range(__first, __last);
5648 __glibcxx_requires_irreflexive(__first, __last);
5650 return _GLIBCXX_STD_A::__min_element(__first, __last,
5651 __gnu_cxx::__ops::__iter_less_iter());
5663 template<
typename _ForwardIterator,
typename _Compare>
5664 _GLIBCXX14_CONSTEXPR
5665 inline _ForwardIterator
5666 min_element(_ForwardIterator __first, _ForwardIterator __last,
5670 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5671 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5672 typename iterator_traits<_ForwardIterator>::value_type,
5673 typename iterator_traits<_ForwardIterator>::value_type>)
5674 __glibcxx_requires_valid_range(__first, __last);
5675 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5677 return _GLIBCXX_STD_A::__min_element(__first, __last,
5678 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5681 template<
typename _ForwardIterator,
typename _Compare>
5682 _GLIBCXX14_CONSTEXPR
5684 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5687 if (__first == __last)
return __first;
5688 _ForwardIterator __result = __first;
5689 while (++__first != __last)
5690 if (__comp(__result, __first))
5702 template<
typename _ForwardIterator>
5703 _GLIBCXX14_CONSTEXPR
5704 inline _ForwardIterator
5705 max_element(_ForwardIterator __first, _ForwardIterator __last)
5708 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5709 __glibcxx_function_requires(_LessThanComparableConcept<
5710 typename iterator_traits<_ForwardIterator>::value_type>)
5711 __glibcxx_requires_valid_range(__first, __last);
5712 __glibcxx_requires_irreflexive(__first, __last);
5714 return _GLIBCXX_STD_A::__max_element(__first, __last,
5715 __gnu_cxx::__ops::__iter_less_iter());
5727 template<
typename _ForwardIterator,
typename _Compare>
5728 _GLIBCXX14_CONSTEXPR
5729 inline _ForwardIterator
5730 max_element(_ForwardIterator __first, _ForwardIterator __last,
5734 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5735 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5736 typename iterator_traits<_ForwardIterator>::value_type,
5737 typename iterator_traits<_ForwardIterator>::value_type>)
5738 __glibcxx_requires_valid_range(__first, __last);
5739 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5741 return _GLIBCXX_STD_A::__max_element(__first, __last,
5742 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5745 #if __cplusplus >= 201402L 5747 template<
typename _InputIterator,
typename _RandomAccessIterator,
5748 typename _Size,
typename _UniformRandomBitGenerator>
5749 _RandomAccessIterator
5752 _Size __n, _UniformRandomBitGenerator&& __g)
5755 using __param_type =
typename __distrib_type::param_type;
5756 __distrib_type __d{};
5757 _Size __sample_sz = 0;
5758 while (__first != __last && __sample_sz != __n)
5760 __out[__sample_sz++] = *__first;
5763 for (
auto __pop_sz = __sample_sz; __first != __last;
5764 ++__first, (void) ++__pop_sz)
5766 const auto __k = __d(__g, __param_type{0, __pop_sz});
5768 __out[__k] = *__first;
5770 return __out + __sample_sz;
5774 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5775 typename _Size,
typename _UniformRandomBitGenerator>
5777 __sample(_ForwardIterator __first, _ForwardIterator __last,
5779 _OutputIterator __out, _Cat,
5780 _Size __n, _UniformRandomBitGenerator&& __g)
5783 using __param_type =
typename __distrib_type::param_type;
5788 __distrib_type __d{};
5790 __n =
std::min(__n, __unsampled_sz);
5795 const __uc_type __urngrange = __g.max() - __g.min();
5796 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5800 while (__n != 0 && __unsampled_sz >= 2)
5806 if (__p.
first < __n)
5808 *__out++ = *__first;
5814 if (__n == 0)
break;
5819 *__out++ = *__first;
5829 for (; __n != 0; ++__first)
5830 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5832 *__out++ = *__first;
5838 #if __cplusplus > 201402L 5839 #define __cpp_lib_sample 201603 5841 template<
typename _PopulationIterator,
typename _SampleIterator,
5842 typename _Distance,
typename _UniformRandomBitGenerator>
5844 sample(_PopulationIterator __first, _PopulationIterator __last,
5845 _SampleIterator __out, _Distance __n,
5846 _UniformRandomBitGenerator&& __g)
5848 using __pop_cat =
typename 5849 std::iterator_traits<_PopulationIterator>::iterator_category;
5850 using __samp_cat =
typename 5851 std::iterator_traits<_SampleIterator>::iterator_category;
5854 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5855 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5856 "output range must use a RandomAccessIterator when input range" 5857 " does not meet the ForwardIterator requirements");
5859 static_assert(is_integral<_Distance>::value,
5860 "sample size must be an integer type");
5862 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5864 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5865 std::forward<_UniformRandomBitGenerator>(__g));
5870 _GLIBCXX_END_NAMESPACE_ALGO
5871 _GLIBCXX_END_NAMESPACE_VERSION
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_GLIBCXX14_CONSTEXPR _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Forward iterators support a superset of input iterator operations.
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
_InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
_OutputIterator __sample(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag, _OutputIterator __out, _Cat, _Size __n, _UniformRandomBitGenerator &&__g)
Selection sampling algorithm.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
_InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Struct holding two objects of arbitrary type.
Bidirectional iterators support a superset of forward iterator operations.
void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
_GLIBCXX14_CONSTEXPR _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
_T2 second
first is a copy of the first object
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_GLIBCXX14_CONSTEXPR pair< _ForwardIterator, _ForwardIterator > minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return a pair of iterators pointing to the minimum and maximum elements in a range.
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
Marking output iterators.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
Random-access iterators support a superset of bidirectional iterator operations.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
_T1 first
second_type is the second bound type
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is false.
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
ISO C++ entities toplevel namespace is std.
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.