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 _ForwardIterator __first2 = __middle;
1260 if (__first == __middle)
1261 __middle = __first2;
1263 while (__first2 != __last);
1265 _ForwardIterator __ret = __first;
1267 __first2 = __middle;
1269 while (__first2 != __last)
1274 if (__first == __middle)
1275 __middle = __first2;
1276 else if (__first2 == __last)
1277 __first2 = __middle;
1283 template<
typename _B
idirectionalIterator>
1284 _BidirectionalIterator
1286 _BidirectionalIterator __middle,
1287 _BidirectionalIterator __last,
1291 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1292 _BidirectionalIterator>)
1297 while (__first != __middle && __middle != __last)
1303 if (__first == __middle)
1316 template<
typename _RandomAccessIterator>
1317 _RandomAccessIterator
1319 _RandomAccessIterator __middle,
1320 _RandomAccessIterator __last,
1324 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1325 _RandomAccessIterator>)
1327 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1329 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1332 _Distance __n = __last - __first;
1333 _Distance __k = __middle - __first;
1335 if (__k == __n - __k)
1341 _RandomAccessIterator __p = __first;
1342 _RandomAccessIterator __ret = __first + (__last - __middle);
1346 if (__k < __n - __k)
1348 if (__is_pod(_ValueType) && __k == 1)
1350 _ValueType __t = _GLIBCXX_MOVE(*__p);
1351 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1352 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1355 _RandomAccessIterator __q = __p + __k;
1356 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1365 std::swap(__n, __k);
1371 if (__is_pod(_ValueType) && __k == 1)
1373 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1374 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1375 *__p = _GLIBCXX_MOVE(__t);
1378 _RandomAccessIterator __q = __p + __n;
1380 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1389 std::swap(__n, __k);
1417 template<
typename _ForwardIterator>
1418 inline _ForwardIterator
1419 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1420 _ForwardIterator __last)
1423 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1425 __glibcxx_requires_valid_range(__first, __middle);
1426 __glibcxx_requires_valid_range(__middle, __last);
1428 if (__first == __middle)
1430 else if (__last == __middle)
1433 return std::__rotate(__first, __middle, __last,
1459 template<
typename _ForwardIterator,
typename _OutputIterator>
1460 inline _OutputIterator
1461 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1462 _ForwardIterator __last, _OutputIterator __result)
1465 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1466 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1467 typename iterator_traits<_ForwardIterator>::value_type>)
1468 __glibcxx_requires_valid_range(__first, __middle);
1469 __glibcxx_requires_valid_range(__middle, __last);
1471 return std::copy(__first, __middle,
1472 std::copy(__middle, __last, __result));
1476 template<
typename _ForwardIterator,
typename _Predicate>
1481 if (__first == __last)
1484 while (__pred(*__first))
1485 if (++__first == __last)
1488 _ForwardIterator __next = __first;
1490 while (++__next != __last)
1491 if (__pred(*__next))
1501 template<
typename _B
idirectionalIterator,
typename _Predicate>
1502 _BidirectionalIterator
1503 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1509 if (__first == __last)
1511 else if (__pred(*__first))
1517 if (__first == __last)
1519 else if (!
bool(__pred(*__last)))
1536 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1540 _ForwardIterator __last,
1541 _Predicate __pred, _Distance __len,
1543 _Distance __buffer_size)
1548 if (__len <= __buffer_size)
1550 _ForwardIterator __result1 = __first;
1551 _Pointer __result2 = __buffer;
1556 *__result2 = _GLIBCXX_MOVE(*__first);
1559 for (; __first != __last; ++__first)
1560 if (__pred(__first))
1562 *__result1 = _GLIBCXX_MOVE(*__first);
1567 *__result2 = _GLIBCXX_MOVE(*__first);
1571 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1575 _ForwardIterator __middle = __first;
1577 _ForwardIterator __left_split =
1579 __len / 2, __buffer,
1584 _Distance __right_len = __len - __len / 2;
1585 _ForwardIterator __right_split =
1592 __buffer, __buffer_size);
1594 return std::rotate(__left_split, __middle, __right_split);
1597 template<
typename _ForwardIterator,
typename _Predicate>
1599 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1604 if (__first == __last)
1607 typedef typename iterator_traits<_ForwardIterator>::value_type
1609 typedef typename iterator_traits<_ForwardIterator>::difference_type
1612 _Temporary_buffer<_ForwardIterator, _ValueType>
1616 _DistanceType(__buf.requested_size()),
1618 _DistanceType(__buf.size()));
1638 template<
typename _ForwardIterator,
typename _Predicate>
1639 inline _ForwardIterator
1640 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1644 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1646 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1647 typename iterator_traits<_ForwardIterator>::value_type>)
1648 __glibcxx_requires_valid_range(__first, __last);
1650 return std::__stable_partition(__first, __last,
1651 __gnu_cxx::__ops::__pred_iter(__pred));
1655 template<
typename _RandomAccessIterator,
typename _Compare>
1658 _RandomAccessIterator __middle,
1659 _RandomAccessIterator __last, _Compare __comp)
1661 std::__make_heap(__first, __middle, __comp);
1662 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1663 if (__comp(__i, __first))
1664 std::__pop_heap(__first, __middle, __i, __comp);
1669 template<
typename _InputIterator,
typename _RandomAccessIterator,
1671 _RandomAccessIterator
1672 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1673 _RandomAccessIterator __result_first,
1674 _RandomAccessIterator __result_last,
1677 typedef typename iterator_traits<_InputIterator>::value_type
1679 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1680 typedef typename _RItTraits::difference_type _DistanceType;
1682 if (__result_first == __result_last)
1683 return __result_last;
1684 _RandomAccessIterator __result_real_last = __result_first;
1685 while (__first != __last && __result_real_last != __result_last)
1687 *__result_real_last = *__first;
1688 ++__result_real_last;
1692 std::__make_heap(__result_first, __result_real_last, __comp);
1693 while (__first != __last)
1695 if (__comp(__first, __result_first))
1696 std::__adjust_heap(__result_first, _DistanceType(0),
1697 _DistanceType(__result_real_last
1699 _InputValueType(*__first), __comp);
1702 std::__sort_heap(__result_first, __result_real_last, __comp);
1703 return __result_real_last;
1724 template<
typename _InputIterator,
typename _RandomAccessIterator>
1725 inline _RandomAccessIterator
1726 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1727 _RandomAccessIterator __result_first,
1728 _RandomAccessIterator __result_last)
1730 #ifdef _GLIBCXX_CONCEPT_CHECKS 1731 typedef typename iterator_traits<_InputIterator>::value_type
1733 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1738 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1739 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1741 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1743 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1744 __glibcxx_requires_valid_range(__first, __last);
1745 __glibcxx_requires_irreflexive(__first, __last);
1746 __glibcxx_requires_valid_range(__result_first, __result_last);
1748 return std::__partial_sort_copy(__first, __last,
1749 __result_first, __result_last,
1750 __gnu_cxx::__ops::__iter_less_iter());
1773 template<
typename _InputIterator,
typename _RandomAccessIterator,
1775 inline _RandomAccessIterator
1776 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1777 _RandomAccessIterator __result_first,
1778 _RandomAccessIterator __result_last,
1781 #ifdef _GLIBCXX_CONCEPT_CHECKS 1782 typedef typename iterator_traits<_InputIterator>::value_type
1784 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1789 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1790 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1791 _RandomAccessIterator>)
1792 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1794 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1795 _InputValueType, _OutputValueType>)
1796 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1797 _OutputValueType, _OutputValueType>)
1798 __glibcxx_requires_valid_range(__first, __last);
1799 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1800 __glibcxx_requires_valid_range(__result_first, __result_last);
1802 return std::__partial_sort_copy(__first, __last,
1803 __result_first, __result_last,
1804 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1808 template<
typename _RandomAccessIterator,
typename _Compare>
1813 typename iterator_traits<_RandomAccessIterator>::value_type
1814 __val = _GLIBCXX_MOVE(*__last);
1815 _RandomAccessIterator __next = __last;
1817 while (__comp(__val, __next))
1819 *__last = _GLIBCXX_MOVE(*__next);
1823 *__last = _GLIBCXX_MOVE(__val);
1827 template<
typename _RandomAccessIterator,
typename _Compare>
1830 _RandomAccessIterator __last, _Compare __comp)
1832 if (__first == __last)
return;
1834 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1836 if (__comp(__i, __first))
1838 typename iterator_traits<_RandomAccessIterator>::value_type
1839 __val = _GLIBCXX_MOVE(*__i);
1840 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1841 *__first = _GLIBCXX_MOVE(__val);
1845 __gnu_cxx::__ops::__val_comp_iter(__comp));
1850 template<
typename _RandomAccessIterator,
typename _Compare>
1853 _RandomAccessIterator __last, _Compare __comp)
1855 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1857 __gnu_cxx::__ops::__val_comp_iter(__comp));
1864 enum { _S_threshold = 16 };
1867 template<
typename _RandomAccessIterator,
typename _Compare>
1870 _RandomAccessIterator __last, _Compare __comp)
1872 if (__last - __first >
int(_S_threshold))
1883 template<
typename _RandomAccessIterator,
typename _Compare>
1884 _RandomAccessIterator
1886 _RandomAccessIterator __last,
1887 _RandomAccessIterator __pivot, _Compare __comp)
1891 while (__comp(__first, __pivot))
1894 while (__comp(__pivot, __last))
1896 if (!(__first < __last))
1904 template<
typename _RandomAccessIterator,
typename _Compare>
1905 inline _RandomAccessIterator
1907 _RandomAccessIterator __last, _Compare __comp)
1909 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1915 template<
typename _RandomAccessIterator,
typename _Compare>
1917 __partial_sort(_RandomAccessIterator __first,
1918 _RandomAccessIterator __middle,
1919 _RandomAccessIterator __last,
1923 std::__sort_heap(__first, __middle, __comp);
1927 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1930 _RandomAccessIterator __last,
1931 _Size __depth_limit, _Compare __comp)
1933 while (__last - __first >
int(_S_threshold))
1935 if (__depth_limit == 0)
1937 std::__partial_sort(__first, __last, __last, __comp);
1941 _RandomAccessIterator __cut =
1950 template<
typename _RandomAccessIterator,
typename _Compare>
1952 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1955 if (__first != __last)
1964 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1966 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1967 _RandomAccessIterator __last, _Size __depth_limit,
1970 while (__last - __first > 3)
1972 if (__depth_limit == 0)
1980 _RandomAccessIterator __cut =
2010 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2011 inline _ForwardIterator
2012 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2013 const _Tp& __val, _Compare __comp)
2016 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2017 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2018 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2019 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2022 return std::__lower_bound(__first, __last, __val,
2023 __gnu_cxx::__ops::__iter_comp_val(__comp));
2026 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2028 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2029 const _Tp& __val, _Compare __comp)
2031 typedef typename iterator_traits<_ForwardIterator>::difference_type
2038 _DistanceType __half = __len >> 1;
2039 _ForwardIterator __middle = __first;
2041 if (__comp(__val, __middle))
2047 __len = __len - __half - 1;
2064 template<
typename _ForwardIterator,
typename _Tp>
2065 inline _ForwardIterator
2066 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2070 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2071 __glibcxx_function_requires(_LessThanOpConcept<
2072 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2073 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2075 return std::__upper_bound(__first, __last, __val,
2076 __gnu_cxx::__ops::__val_less_iter());
2094 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2095 inline _ForwardIterator
2096 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2097 const _Tp& __val, _Compare __comp)
2100 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2101 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2102 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2103 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2106 return std::__upper_bound(__first, __last, __val,
2107 __gnu_cxx::__ops::__val_comp_iter(__comp));
2110 template<
typename _ForwardIterator,
typename _Tp,
2111 typename _CompareItTp,
typename _CompareTpIt>
2112 pair<_ForwardIterator, _ForwardIterator>
2113 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2115 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2117 typedef typename iterator_traits<_ForwardIterator>::difference_type
2124 _DistanceType __half = __len >> 1;
2125 _ForwardIterator __middle = __first;
2127 if (__comp_it_val(__middle, __val))
2131 __len = __len - __half - 1;
2133 else if (__comp_val_it(__val, __middle))
2137 _ForwardIterator __left
2138 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2140 _ForwardIterator __right
2141 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2142 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2145 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2165 template<
typename _ForwardIterator,
typename _Tp>
2166 inline pair<_ForwardIterator, _ForwardIterator>
2167 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2171 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2172 __glibcxx_function_requires(_LessThanOpConcept<
2173 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2174 __glibcxx_function_requires(_LessThanOpConcept<
2175 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2176 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2177 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2179 return std::__equal_range(__first, __last, __val,
2180 __gnu_cxx::__ops::__iter_less_val(),
2181 __gnu_cxx::__ops::__val_less_iter());
2201 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2202 inline pair<_ForwardIterator, _ForwardIterator>
2203 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2204 const _Tp& __val, _Compare __comp)
2207 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2208 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2209 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2210 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2211 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2212 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2214 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2217 return std::__equal_range(__first, __last, __val,
2218 __gnu_cxx::__ops::__iter_comp_val(__comp),
2219 __gnu_cxx::__ops::__val_comp_iter(__comp));
2234 template<
typename _ForwardIterator,
typename _Tp>
2236 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2240 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2241 __glibcxx_function_requires(_LessThanOpConcept<
2242 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2243 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2244 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2246 _ForwardIterator __i
2247 = std::__lower_bound(__first, __last, __val,
2248 __gnu_cxx::__ops::__iter_less_val());
2249 return __i != __last && !(__val < *__i);
2267 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2269 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2270 const _Tp& __val, _Compare __comp)
2273 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2274 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2275 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2276 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2278 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2281 _ForwardIterator __i
2282 = std::__lower_bound(__first, __last, __val,
2283 __gnu_cxx::__ops::__iter_comp_val(__comp));
2284 return __i != __last && !bool(__comp(__val, *__i));
2290 template<
typename _InputIterator1,
typename _InputIterator2,
2291 typename _OutputIterator,
typename _Compare>
2294 _InputIterator2 __first2, _InputIterator2 __last2,
2295 _OutputIterator __result, _Compare __comp)
2297 while (__first1 != __last1 && __first2 != __last2)
2299 if (__comp(__first2, __first1))
2301 *__result = _GLIBCXX_MOVE(*__first2);
2306 *__result = _GLIBCXX_MOVE(*__first1);
2311 if (__first1 != __last1)
2312 _GLIBCXX_MOVE3(__first1, __last1, __result);
2316 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2317 typename _BidirectionalIterator3,
typename _Compare>
2320 _BidirectionalIterator1 __last1,
2321 _BidirectionalIterator2 __first2,
2322 _BidirectionalIterator2 __last2,
2323 _BidirectionalIterator3 __result,
2326 if (__first1 == __last1)
2328 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2331 else if (__first2 == __last2)
2338 if (__comp(__last2, __last1))
2340 *--__result = _GLIBCXX_MOVE(*__last1);
2341 if (__first1 == __last1)
2343 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2350 *--__result = _GLIBCXX_MOVE(*__last2);
2351 if (__first2 == __last2)
2359 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2361 _BidirectionalIterator1
2363 _BidirectionalIterator1 __middle,
2364 _BidirectionalIterator1 __last,
2365 _Distance __len1, _Distance __len2,
2366 _BidirectionalIterator2 __buffer,
2367 _Distance __buffer_size)
2369 _BidirectionalIterator2 __buffer_end;
2370 if (__len1 > __len2 && __len2 <= __buffer_size)
2374 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2375 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2376 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2381 else if (__len1 <= __buffer_size)
2385 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2386 _GLIBCXX_MOVE3(__middle, __last, __first);
2387 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2397 template<
typename _BidirectionalIterator,
typename _Distance,
2398 typename _Pointer,
typename _Compare>
2401 _BidirectionalIterator __middle,
2402 _BidirectionalIterator __last,
2403 _Distance __len1, _Distance __len2,
2404 _Pointer __buffer, _Distance __buffer_size,
2407 if (__len1 <= __len2 && __len1 <= __buffer_size)
2409 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2413 else if (__len2 <= __buffer_size)
2415 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2417 __buffer_end, __last, __comp);
2421 _BidirectionalIterator __first_cut = __first;
2422 _BidirectionalIterator __second_cut = __middle;
2423 _Distance __len11 = 0;
2424 _Distance __len22 = 0;
2425 if (__len1 > __len2)
2427 __len11 = __len1 / 2;
2430 = std::__lower_bound(__middle, __last, *__first_cut,
2431 __gnu_cxx::__ops::__iter_comp_val(__comp));
2436 __len22 = __len2 / 2;
2439 = std::__upper_bound(__first, __middle, *__second_cut,
2440 __gnu_cxx::__ops::__val_comp_iter(__comp));
2444 _BidirectionalIterator __new_middle
2446 __len1 - __len11, __len22, __buffer,
2449 __len22, __buffer, __buffer_size, __comp);
2452 __len2 - __len22, __buffer,
2453 __buffer_size, __comp);
2458 template<
typename _BidirectionalIterator,
typename _Distance,
2462 _BidirectionalIterator __middle,
2463 _BidirectionalIterator __last,
2464 _Distance __len1, _Distance __len2,
2467 if (__len1 == 0 || __len2 == 0)
2470 if (__len1 + __len2 == 2)
2472 if (__comp(__middle, __first))
2477 _BidirectionalIterator __first_cut = __first;
2478 _BidirectionalIterator __second_cut = __middle;
2479 _Distance __len11 = 0;
2480 _Distance __len22 = 0;
2481 if (__len1 > __len2)
2483 __len11 = __len1 / 2;
2486 = std::__lower_bound(__middle, __last, *__first_cut,
2487 __gnu_cxx::__ops::__iter_comp_val(__comp));
2492 __len22 = __len2 / 2;
2495 = std::__upper_bound(__first, __middle, *__second_cut,
2496 __gnu_cxx::__ops::__val_comp_iter(__comp));
2500 _BidirectionalIterator __new_middle
2501 =
std::rotate(__first_cut, __middle, __second_cut);
2503 __len11, __len22, __comp);
2505 __len1 - __len11, __len2 - __len22, __comp);
2508 template<
typename _B
idirectionalIterator,
typename _Compare>
2510 __inplace_merge(_BidirectionalIterator __first,
2511 _BidirectionalIterator __middle,
2512 _BidirectionalIterator __last,
2515 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2517 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2520 if (__first == __middle || __middle == __last)
2523 const _DistanceType __len1 =
std::distance(__first, __middle);
2524 const _DistanceType __len2 =
std::distance(__middle, __last);
2526 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2527 _TmpBuf __buf(__first, __len1 + __len2);
2529 if (__buf.begin() == 0)
2531 (__first, __middle, __last, __len1, __len2, __comp);
2534 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2535 _DistanceType(__buf.size()), __comp);
2556 template<
typename _B
idirectionalIterator>
2558 inplace_merge(_BidirectionalIterator __first,
2559 _BidirectionalIterator __middle,
2560 _BidirectionalIterator __last)
2563 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2564 _BidirectionalIterator>)
2565 __glibcxx_function_requires(_LessThanComparableConcept<
2566 typename iterator_traits<_BidirectionalIterator>::value_type>)
2567 __glibcxx_requires_sorted(__first, __middle);
2568 __glibcxx_requires_sorted(__middle, __last);
2569 __glibcxx_requires_irreflexive(__first, __last);
2571 std::__inplace_merge(__first, __middle, __last,
2572 __gnu_cxx::__ops::__iter_less_iter());
2597 template<
typename _B
idirectionalIterator,
typename _Compare>
2599 inplace_merge(_BidirectionalIterator __first,
2600 _BidirectionalIterator __middle,
2601 _BidirectionalIterator __last,
2605 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2606 _BidirectionalIterator>)
2607 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2608 typename iterator_traits<_BidirectionalIterator>::value_type,
2609 typename iterator_traits<_BidirectionalIterator>::value_type>)
2610 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2611 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2612 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2614 std::__inplace_merge(__first, __middle, __last,
2615 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2620 template<
typename _InputIterator,
typename _OutputIterator,
2624 _InputIterator __first2, _InputIterator __last2,
2625 _OutputIterator __result, _Compare __comp)
2627 while (__first1 != __last1 && __first2 != __last2)
2629 if (__comp(__first2, __first1))
2631 *__result = _GLIBCXX_MOVE(*__first2);
2636 *__result = _GLIBCXX_MOVE(*__first1);
2641 return _GLIBCXX_MOVE3(__first2, __last2,
2642 _GLIBCXX_MOVE3(__first1, __last1,
2646 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2647 typename _Distance,
typename _Compare>
2649 __merge_sort_loop(_RandomAccessIterator1 __first,
2650 _RandomAccessIterator1 __last,
2651 _RandomAccessIterator2 __result, _Distance __step_size,
2654 const _Distance __two_step = 2 * __step_size;
2656 while (__last - __first >= __two_step)
2659 __first + __step_size,
2660 __first + __two_step,
2662 __first += __two_step;
2664 __step_size =
std::min(_Distance(__last - __first), __step_size);
2667 __first + __step_size, __last, __result, __comp);
2670 template<
typename _RandomAccessIterator,
typename _Distance,
2673 __chunk_insertion_sort(_RandomAccessIterator __first,
2674 _RandomAccessIterator __last,
2675 _Distance __chunk_size, _Compare __comp)
2677 while (__last - __first >= __chunk_size)
2680 __first += __chunk_size;
2685 enum { _S_chunk_size = 7 };
2687 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2689 __merge_sort_with_buffer(_RandomAccessIterator __first,
2690 _RandomAccessIterator __last,
2691 _Pointer __buffer, _Compare __comp)
2693 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2696 const _Distance __len = __last - __first;
2697 const _Pointer __buffer_last = __buffer + __len;
2699 _Distance __step_size = _S_chunk_size;
2700 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2702 while (__step_size < __len)
2704 std::__merge_sort_loop(__first, __last, __buffer,
2705 __step_size, __comp);
2707 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2708 __step_size, __comp);
2713 template<
typename _RandomAccessIterator,
typename _Pointer,
2714 typename _Distance,
typename _Compare>
2716 __stable_sort_adaptive(_RandomAccessIterator __first,
2717 _RandomAccessIterator __last,
2718 _Pointer __buffer, _Distance __buffer_size,
2721 const _Distance __len = (__last - __first + 1) / 2;
2722 const _RandomAccessIterator __middle = __first + __len;
2723 if (__len > __buffer_size)
2725 std::__stable_sort_adaptive(__first, __middle, __buffer,
2726 __buffer_size, __comp);
2727 std::__stable_sort_adaptive(__middle, __last, __buffer,
2728 __buffer_size, __comp);
2732 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2733 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2736 _Distance(__middle - __first),
2737 _Distance(__last - __middle),
2738 __buffer, __buffer_size,
2743 template<
typename _RandomAccessIterator,
typename _Compare>
2746 _RandomAccessIterator __last, _Compare __comp)
2748 if (__last - __first < 15)
2753 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2769 template<
typename _InputIterator1,
typename _InputIterator2,
2772 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2773 _InputIterator2 __first2, _InputIterator2 __last2,
2776 while (__first1 != __last1 && __first2 != __last2)
2777 if (__comp(__first2, __first1))
2779 else if (__comp(__first1, __first2))
2787 return __first2 == __last2;
2808 template<
typename _InputIterator1,
typename _InputIterator2>
2810 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2811 _InputIterator2 __first2, _InputIterator2 __last2)
2814 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2815 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2816 __glibcxx_function_requires(_LessThanOpConcept<
2817 typename iterator_traits<_InputIterator1>::value_type,
2818 typename iterator_traits<_InputIterator2>::value_type>)
2819 __glibcxx_function_requires(_LessThanOpConcept<
2820 typename iterator_traits<_InputIterator2>::value_type,
2821 typename iterator_traits<_InputIterator1>::value_type>)
2822 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2823 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2824 __glibcxx_requires_irreflexive2(__first1, __last1);
2825 __glibcxx_requires_irreflexive2(__first2, __last2);
2827 return std::__includes(__first1, __last1, __first2, __last2,
2828 __gnu_cxx::__ops::__iter_less_iter());
2852 template<
typename _InputIterator1,
typename _InputIterator2,
2855 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2856 _InputIterator2 __first2, _InputIterator2 __last2,
2860 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2861 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2862 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2863 typename iterator_traits<_InputIterator1>::value_type,
2864 typename iterator_traits<_InputIterator2>::value_type>)
2865 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2866 typename iterator_traits<_InputIterator2>::value_type,
2867 typename iterator_traits<_InputIterator1>::value_type>)
2868 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2869 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2870 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2871 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2873 return std::__includes(__first1, __last1, __first2, __last2,
2874 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2887 template<
typename _B
idirectionalIterator,
typename _Compare>
2889 __next_permutation(_BidirectionalIterator __first,
2890 _BidirectionalIterator __last, _Compare __comp)
2892 if (__first == __last)
2894 _BidirectionalIterator __i = __first;
2903 _BidirectionalIterator __ii = __i;
2905 if (__comp(__i, __ii))
2907 _BidirectionalIterator __j = __last;
2908 while (!__comp(__i, --__j))
2936 template<
typename _B
idirectionalIterator>
2938 next_permutation(_BidirectionalIterator __first,
2939 _BidirectionalIterator __last)
2942 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2943 _BidirectionalIterator>)
2944 __glibcxx_function_requires(_LessThanComparableConcept<
2945 typename iterator_traits<_BidirectionalIterator>::value_type>)
2946 __glibcxx_requires_valid_range(__first, __last);
2947 __glibcxx_requires_irreflexive(__first, __last);
2949 return std::__next_permutation
2950 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2968 template<
typename _B
idirectionalIterator,
typename _Compare>
2970 next_permutation(_BidirectionalIterator __first,
2971 _BidirectionalIterator __last, _Compare __comp)
2974 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2975 _BidirectionalIterator>)
2976 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2977 typename iterator_traits<_BidirectionalIterator>::value_type,
2978 typename iterator_traits<_BidirectionalIterator>::value_type>)
2979 __glibcxx_requires_valid_range(__first, __last);
2980 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2982 return std::__next_permutation
2983 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2986 template<
typename _B
idirectionalIterator,
typename _Compare>
2988 __prev_permutation(_BidirectionalIterator __first,
2989 _BidirectionalIterator __last, _Compare __comp)
2991 if (__first == __last)
2993 _BidirectionalIterator __i = __first;
3002 _BidirectionalIterator __ii = __i;
3004 if (__comp(__ii, __i))
3006 _BidirectionalIterator __j = __last;
3007 while (!__comp(--__j, __i))
3036 template<
typename _B
idirectionalIterator>
3038 prev_permutation(_BidirectionalIterator __first,
3039 _BidirectionalIterator __last)
3042 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3043 _BidirectionalIterator>)
3044 __glibcxx_function_requires(_LessThanComparableConcept<
3045 typename iterator_traits<_BidirectionalIterator>::value_type>)
3046 __glibcxx_requires_valid_range(__first, __last);
3047 __glibcxx_requires_irreflexive(__first, __last);
3049 return std::__prev_permutation(__first, __last,
3050 __gnu_cxx::__ops::__iter_less_iter());
3068 template<
typename _B
idirectionalIterator,
typename _Compare>
3070 prev_permutation(_BidirectionalIterator __first,
3071 _BidirectionalIterator __last, _Compare __comp)
3074 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3075 _BidirectionalIterator>)
3076 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3077 typename iterator_traits<_BidirectionalIterator>::value_type,
3078 typename iterator_traits<_BidirectionalIterator>::value_type>)
3079 __glibcxx_requires_valid_range(__first, __last);
3080 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3082 return std::__prev_permutation(__first, __last,
3083 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3089 template<
typename _InputIterator,
typename _OutputIterator,
3090 typename _Predicate,
typename _Tp>
3092 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3093 _OutputIterator __result,
3094 _Predicate __pred,
const _Tp& __new_value)
3096 for (; __first != __last; ++__first, (void)++__result)
3097 if (__pred(__first))
3098 *__result = __new_value;
3100 *__result = *__first;
3118 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3119 inline _OutputIterator
3120 replace_copy(_InputIterator __first, _InputIterator __last,
3121 _OutputIterator __result,
3122 const _Tp& __old_value,
const _Tp& __new_value)
3125 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3126 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3127 typename iterator_traits<_InputIterator>::value_type>)
3128 __glibcxx_function_requires(_EqualOpConcept<
3129 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3130 __glibcxx_requires_valid_range(__first, __last);
3132 return std::__replace_copy_if(__first, __last, __result,
3133 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3152 template<
typename _InputIterator,
typename _OutputIterator,
3153 typename _Predicate,
typename _Tp>
3154 inline _OutputIterator
3155 replace_copy_if(_InputIterator __first, _InputIterator __last,
3156 _OutputIterator __result,
3157 _Predicate __pred,
const _Tp& __new_value)
3160 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3161 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3162 typename iterator_traits<_InputIterator>::value_type>)
3163 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3164 typename iterator_traits<_InputIterator>::value_type>)
3165 __glibcxx_requires_valid_range(__first, __last);
3167 return std::__replace_copy_if(__first, __last, __result,
3168 __gnu_cxx::__ops::__pred_iter(__pred),
3172 template<
typename _InputIterator,
typename _Predicate>
3173 typename iterator_traits<_InputIterator>::difference_type
3174 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3176 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3177 for (; __first != __last; ++__first)
3178 if (__pred(__first))
3183 #if __cplusplus >= 201103L 3191 template<
typename _ForwardIterator>
3193 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3205 template<
typename _ForwardIterator,
typename _Compare>
3207 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3211 template<
typename _ForwardIterator,
typename _Compare>
3213 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3216 if (__first == __last)
3219 _ForwardIterator __next = __first;
3220 for (++__next; __next != __last; __first = __next, (void)++__next)
3221 if (__comp(__next, __first))
3234 template<
typename _ForwardIterator>
3235 inline _ForwardIterator
3236 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3239 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3240 __glibcxx_function_requires(_LessThanComparableConcept<
3241 typename iterator_traits<_ForwardIterator>::value_type>)
3242 __glibcxx_requires_valid_range(__first, __last);
3243 __glibcxx_requires_irreflexive(__first, __last);
3245 return std::__is_sorted_until(__first, __last,
3246 __gnu_cxx::__ops::__iter_less_iter());
3258 template<
typename _ForwardIterator,
typename _Compare>
3259 inline _ForwardIterator
3260 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3264 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3265 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3266 typename iterator_traits<_ForwardIterator>::value_type,
3267 typename iterator_traits<_ForwardIterator>::value_type>)
3268 __glibcxx_requires_valid_range(__first, __last);
3269 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3271 return std::__is_sorted_until(__first, __last,
3272 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3283 template<
typename _Tp>
3284 _GLIBCXX14_CONSTEXPR
3285 inline pair<const _Tp&, const _Tp&>
3289 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3291 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3304 template<
typename _Tp,
typename _Compare>
3305 _GLIBCXX14_CONSTEXPR
3306 inline pair<const _Tp&, const _Tp&>
3307 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3313 template<
typename _ForwardIterator,
typename _Compare>
3314 _GLIBCXX14_CONSTEXPR
3315 pair<_ForwardIterator, _ForwardIterator>
3316 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3319 _ForwardIterator __next = __first;
3320 if (__first == __last
3321 || ++__next == __last)
3324 _ForwardIterator __min{}, __max{};
3325 if (__comp(__next, __first))
3339 while (__first != __last)
3342 if (++__next == __last)
3344 if (__comp(__first, __min))
3346 else if (!__comp(__first, __max))
3351 if (__comp(__next, __first))
3353 if (__comp(__next, __min))
3355 if (!__comp(__first, __max))
3360 if (__comp(__first, __min))
3362 if (!__comp(__next, __max))
3384 template<
typename _ForwardIterator>
3385 _GLIBCXX14_CONSTEXPR
3386 inline pair<_ForwardIterator, _ForwardIterator>
3387 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3390 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3391 __glibcxx_function_requires(_LessThanComparableConcept<
3392 typename iterator_traits<_ForwardIterator>::value_type>)
3393 __glibcxx_requires_valid_range(__first, __last);
3394 __glibcxx_requires_irreflexive(__first, __last);
3396 return std::__minmax_element(__first, __last,
3397 __gnu_cxx::__ops::__iter_less_iter());
3412 template<
typename _ForwardIterator,
typename _Compare>
3413 _GLIBCXX14_CONSTEXPR
3414 inline pair<_ForwardIterator, _ForwardIterator>
3415 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3419 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3420 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3421 typename iterator_traits<_ForwardIterator>::value_type,
3422 typename iterator_traits<_ForwardIterator>::value_type>)
3423 __glibcxx_requires_valid_range(__first, __last);
3424 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3426 return std::__minmax_element(__first, __last,
3427 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3431 template<
typename _Tp>
3432 _GLIBCXX14_CONSTEXPR
3434 min(initializer_list<_Tp> __l)
3435 {
return *std::min_element(__l.begin(), __l.end()); }
3437 template<
typename _Tp,
typename _Compare>
3438 _GLIBCXX14_CONSTEXPR
3440 min(initializer_list<_Tp> __l, _Compare __comp)
3443 template<
typename _Tp>
3444 _GLIBCXX14_CONSTEXPR
3446 max(initializer_list<_Tp> __l)
3449 template<
typename _Tp,
typename _Compare>
3450 _GLIBCXX14_CONSTEXPR
3452 max(initializer_list<_Tp> __l, _Compare __comp)
3455 template<
typename _Tp>
3456 _GLIBCXX14_CONSTEXPR
3457 inline pair<_Tp, _Tp>
3458 minmax(initializer_list<_Tp> __l)
3460 pair<const _Tp*, const _Tp*> __p =
3465 template<
typename _Tp,
typename _Compare>
3466 _GLIBCXX14_CONSTEXPR
3467 inline pair<_Tp, _Tp>
3468 minmax(initializer_list<_Tp> __l, _Compare __comp)
3470 pair<const _Tp*, const _Tp*> __p =
3475 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3476 typename _BinaryPredicate>
3478 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3479 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3483 for (; __first1 != __last1; ++__first1, (void)++__first2)
3484 if (!__pred(__first1, __first2))
3487 if (__first1 == __last1)
3492 _ForwardIterator2 __last2 = __first2;
3494 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3497 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3501 = std::__count_if(__first2, __last2,
3502 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3503 if (0 == __matches ||
3504 std::__count_if(__scan, __last1,
3505 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3524 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3526 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3527 _ForwardIterator2 __first2)
3530 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3531 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3532 __glibcxx_function_requires(_EqualOpConcept<
3533 typename iterator_traits<_ForwardIterator1>::value_type,
3534 typename iterator_traits<_ForwardIterator2>::value_type>)
3535 __glibcxx_requires_valid_range(__first1, __last1);
3537 return std::__is_permutation(__first1, __last1, __first2,
3538 __gnu_cxx::__ops::__iter_equal_to_iter());
3555 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3556 typename _BinaryPredicate>
3558 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3559 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3562 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3563 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3564 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3565 typename iterator_traits<_ForwardIterator1>::value_type,
3566 typename iterator_traits<_ForwardIterator2>::value_type>)
3567 __glibcxx_requires_valid_range(__first1, __last1);
3569 return std::__is_permutation(__first1, __last1, __first2,
3570 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3573 #if __cplusplus > 201103L 3574 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3575 typename _BinaryPredicate>
3577 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3578 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3579 _BinaryPredicate __pred)
3582 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3584 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3585 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3586 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3587 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3598 for (; __first1 != __last1 && __first2 != __last2;
3599 ++__first1, (void)++__first2)
3600 if (!__pred(__first1, __first2))
3605 if (__first1 == __last1)
3612 if (__d1 == 0 && __d2 == 0)
3618 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3621 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3624 auto __matches = std::__count_if(__first2, __last2,
3625 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3627 || std::__count_if(__scan, __last1,
3628 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3648 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3650 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3651 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3653 __glibcxx_requires_valid_range(__first1, __last1);
3654 __glibcxx_requires_valid_range(__first2, __last2);
3657 std::__is_permutation(__first1, __last1, __first2, __last2,
3658 __gnu_cxx::__ops::__iter_equal_to_iter());
3675 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3676 typename _BinaryPredicate>
3678 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3679 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3680 _BinaryPredicate __pred)
3682 __glibcxx_requires_valid_range(__first1, __last1);
3683 __glibcxx_requires_valid_range(__first2, __last2);
3685 return std::__is_permutation(__first1, __last1, __first2, __last2,
3686 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3689 #if __cplusplus > 201402L 3691 #define __cpp_lib_clamp 201603 3701 template<
typename _Tp>
3702 constexpr
const _Tp&
3703 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3705 __glibcxx_assert(!(__hi < __lo));
3706 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3719 template<
typename _Tp,
typename _Compare>
3720 constexpr
const _Tp&
3721 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3723 __glibcxx_assert(!__comp(__hi, __lo));
3724 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3729 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3751 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3752 pair<_IntType, _IntType>
3754 _UniformRandomBitGenerator&& __g)
3773 template<
typename _RandomAccessIterator,
3774 typename _UniformRandomNumberGenerator>
3776 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3777 _UniformRandomNumberGenerator&& __g)
3780 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3781 _RandomAccessIterator>)
3782 __glibcxx_requires_valid_range(__first, __last);
3784 if (__first == __last)
3787 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3790 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3792 typedef typename __distr_type::param_type __p_type;
3794 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3799 const __uc_type __urngrange = __g.max() - __g.min();
3800 const __uc_type __urange = __uc_type(__last - __first);
3802 if (__urngrange / __urange >= __urange)
3805 _RandomAccessIterator __i = __first + 1;
3811 if ((__urange % 2) == 0)
3813 __distr_type __d{0, 1};
3821 while (__i != __last)
3823 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3837 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3838 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3844 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3858 template<
typename _InputIterator,
typename _Function>
3860 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3863 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3864 __glibcxx_requires_valid_range(__first, __last);
3865 for (; __first != __last; ++__first)
3879 template<
typename _InputIterator,
typename _Tp>
3880 inline _InputIterator
3881 find(_InputIterator __first, _InputIterator __last,
3885 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3886 __glibcxx_function_requires(_EqualOpConcept<
3887 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3888 __glibcxx_requires_valid_range(__first, __last);
3890 __gnu_cxx::__ops::__iter_equals_val(__val));
3903 template<
typename _InputIterator,
typename _Predicate>
3904 inline _InputIterator
3905 find_if(_InputIterator __first, _InputIterator __last,
3909 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3910 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3911 typename iterator_traits<_InputIterator>::value_type>)
3912 __glibcxx_requires_valid_range(__first, __last);
3915 __gnu_cxx::__ops::__pred_iter(__pred));
3934 template<
typename _InputIterator,
typename _ForwardIterator>
3936 find_first_of(_InputIterator __first1, _InputIterator __last1,
3937 _ForwardIterator __first2, _ForwardIterator __last2)
3940 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3941 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3942 __glibcxx_function_requires(_EqualOpConcept<
3943 typename iterator_traits<_InputIterator>::value_type,
3944 typename iterator_traits<_ForwardIterator>::value_type>)
3945 __glibcxx_requires_valid_range(__first1, __last1);
3946 __glibcxx_requires_valid_range(__first2, __last2);
3948 for (; __first1 != __last1; ++__first1)
3949 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3950 if (*__first1 == *__iter)
3974 template<
typename _InputIterator,
typename _ForwardIterator,
3975 typename _BinaryPredicate>
3977 find_first_of(_InputIterator __first1, _InputIterator __last1,
3978 _ForwardIterator __first2, _ForwardIterator __last2,
3979 _BinaryPredicate __comp)
3982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3983 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3984 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3985 typename iterator_traits<_InputIterator>::value_type,
3986 typename iterator_traits<_ForwardIterator>::value_type>)
3987 __glibcxx_requires_valid_range(__first1, __last1);
3988 __glibcxx_requires_valid_range(__first2, __last2);
3990 for (; __first1 != __last1; ++__first1)
3991 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3992 if (__comp(*__first1, *__iter))
4006 template<
typename _ForwardIterator>
4007 inline _ForwardIterator
4008 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4011 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4012 __glibcxx_function_requires(_EqualityComparableConcept<
4013 typename iterator_traits<_ForwardIterator>::value_type>)
4014 __glibcxx_requires_valid_range(__first, __last);
4016 return std::__adjacent_find(__first, __last,
4017 __gnu_cxx::__ops::__iter_equal_to_iter());
4031 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4032 inline _ForwardIterator
4033 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4034 _BinaryPredicate __binary_pred)
4037 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4038 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4039 typename iterator_traits<_ForwardIterator>::value_type,
4040 typename iterator_traits<_ForwardIterator>::value_type>)
4041 __glibcxx_requires_valid_range(__first, __last);
4043 return std::__adjacent_find(__first, __last,
4044 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4056 template<
typename _InputIterator,
typename _Tp>
4057 inline typename iterator_traits<_InputIterator>::difference_type
4058 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4061 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4062 __glibcxx_function_requires(_EqualOpConcept<
4063 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4064 __glibcxx_requires_valid_range(__first, __last);
4066 return std::__count_if(__first, __last,
4067 __gnu_cxx::__ops::__iter_equals_val(__value));
4079 template<
typename _InputIterator,
typename _Predicate>
4080 inline typename iterator_traits<_InputIterator>::difference_type
4081 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4084 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4085 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4086 typename iterator_traits<_InputIterator>::value_type>)
4087 __glibcxx_requires_valid_range(__first, __last);
4089 return std::__count_if(__first, __last,
4090 __gnu_cxx::__ops::__pred_iter(__pred));
4119 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4120 inline _ForwardIterator1
4121 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4122 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4125 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4126 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4127 __glibcxx_function_requires(_EqualOpConcept<
4128 typename iterator_traits<_ForwardIterator1>::value_type,
4129 typename iterator_traits<_ForwardIterator2>::value_type>)
4130 __glibcxx_requires_valid_range(__first1, __last1);
4131 __glibcxx_requires_valid_range(__first2, __last2);
4133 return std::__search(__first1, __last1, __first2, __last2,
4134 __gnu_cxx::__ops::__iter_equal_to_iter());
4158 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4159 typename _BinaryPredicate>
4160 inline _ForwardIterator1
4161 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4162 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4163 _BinaryPredicate __predicate)
4166 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4167 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4168 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4169 typename iterator_traits<_ForwardIterator1>::value_type,
4170 typename iterator_traits<_ForwardIterator2>::value_type>)
4171 __glibcxx_requires_valid_range(__first1, __last1);
4172 __glibcxx_requires_valid_range(__first2, __last2);
4174 return std::__search(__first1, __last1, __first2, __last2,
4175 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4193 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4194 inline _ForwardIterator
4195 search_n(_ForwardIterator __first, _ForwardIterator __last,
4196 _Integer __count,
const _Tp& __val)
4199 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4200 __glibcxx_function_requires(_EqualOpConcept<
4201 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4202 __glibcxx_requires_valid_range(__first, __last);
4204 return std::__search_n(__first, __last, __count,
4205 __gnu_cxx::__ops::__iter_equals_val(__val));
4226 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4227 typename _BinaryPredicate>
4228 inline _ForwardIterator
4229 search_n(_ForwardIterator __first, _ForwardIterator __last,
4230 _Integer __count,
const _Tp& __val,
4231 _BinaryPredicate __binary_pred)
4234 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4235 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4236 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4237 __glibcxx_requires_valid_range(__first, __last);
4239 return std::__search_n(__first, __last, __count,
4240 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4243 #if __cplusplus > 201402L 4251 template<
typename _ForwardIterator,
typename _Searcher>
4252 inline _ForwardIterator
4253 search(_ForwardIterator __first, _ForwardIterator __last,
4254 const _Searcher& __searcher)
4255 {
return __searcher(__first, __last).first; }
4274 template<
typename _InputIterator,
typename _OutputIterator,
4275 typename _UnaryOperation>
4277 transform(_InputIterator __first, _InputIterator __last,
4278 _OutputIterator __result, _UnaryOperation __unary_op)
4281 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4282 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4284 __typeof__(__unary_op(*__first))>)
4285 __glibcxx_requires_valid_range(__first, __last);
4287 for (; __first != __last; ++__first, (void)++__result)
4288 *__result = __unary_op(*__first);
4311 template<
typename _InputIterator1,
typename _InputIterator2,
4312 typename _OutputIterator,
typename _BinaryOperation>
4314 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4315 _InputIterator2 __first2, _OutputIterator __result,
4316 _BinaryOperation __binary_op)
4319 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4320 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4321 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4323 __typeof__(__binary_op(*__first1,*__first2))>)
4324 __glibcxx_requires_valid_range(__first1, __last1);
4326 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4327 *__result = __binary_op(*__first1, *__first2);
4344 template<
typename _ForwardIterator,
typename _Tp>
4346 replace(_ForwardIterator __first, _ForwardIterator __last,
4347 const _Tp& __old_value,
const _Tp& __new_value)
4350 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4352 __glibcxx_function_requires(_EqualOpConcept<
4353 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4354 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4355 typename iterator_traits<_ForwardIterator>::value_type>)
4356 __glibcxx_requires_valid_range(__first, __last);
4358 for (; __first != __last; ++__first)
4359 if (*__first == __old_value)
4360 *__first = __new_value;
4376 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4378 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4379 _Predicate __pred,
const _Tp& __new_value)
4382 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4384 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4385 typename iterator_traits<_ForwardIterator>::value_type>)
4386 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4387 typename iterator_traits<_ForwardIterator>::value_type>)
4388 __glibcxx_requires_valid_range(__first, __last);
4390 for (; __first != __last; ++__first)
4391 if (__pred(*__first))
4392 *__first = __new_value;
4408 template<
typename _ForwardIterator,
typename _Generator>
4410 generate(_ForwardIterator __first, _ForwardIterator __last,
4414 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4415 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4416 typename iterator_traits<_ForwardIterator>::value_type>)
4417 __glibcxx_requires_valid_range(__first, __last);
4419 for (; __first != __last; ++__first)
4439 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4441 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4444 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4446 __typeof__(__gen())>)
4448 for (__decltype(__n + 0) __niter = __n;
4449 __niter > 0; --__niter, (void) ++__first)
4475 template<
typename _InputIterator,
typename _OutputIterator>
4476 inline _OutputIterator
4477 unique_copy(_InputIterator __first, _InputIterator __last,
4478 _OutputIterator __result)
4481 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4482 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4483 typename iterator_traits<_InputIterator>::value_type>)
4484 __glibcxx_function_requires(_EqualityComparableConcept<
4485 typename iterator_traits<_InputIterator>::value_type>)
4486 __glibcxx_requires_valid_range(__first, __last);
4488 if (__first == __last)
4491 __gnu_cxx::__ops::__iter_equal_to_iter(),
4515 template<
typename _InputIterator,
typename _OutputIterator,
4516 typename _BinaryPredicate>
4517 inline _OutputIterator
4518 unique_copy(_InputIterator __first, _InputIterator __last,
4519 _OutputIterator __result,
4520 _BinaryPredicate __binary_pred)
4523 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4524 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4525 typename iterator_traits<_InputIterator>::value_type>)
4526 __glibcxx_requires_valid_range(__first, __last);
4528 if (__first == __last)
4531 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4548 template<
typename _RandomAccessIterator>
4550 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4553 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4554 _RandomAccessIterator>)
4555 __glibcxx_requires_valid_range(__first, __last);
4557 if (__first != __last)
4558 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4561 _RandomAccessIterator __j = __first
4562 + std::rand() % ((__i - __first) + 1);
4564 std::iter_swap(__i, __j);
4583 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4585 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4586 #
if __cplusplus >= 201103L
4587 _RandomNumberGenerator&& __rand)
4589 _RandomNumberGenerator& __rand)
4593 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4594 _RandomAccessIterator>)
4595 __glibcxx_requires_valid_range(__first, __last);
4597 if (__first == __last)
4599 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4601 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4623 template<
typename _ForwardIterator,
typename _Predicate>
4624 inline _ForwardIterator
4625 partition(_ForwardIterator __first, _ForwardIterator __last,
4629 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4631 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4632 typename iterator_traits<_ForwardIterator>::value_type>)
4633 __glibcxx_requires_valid_range(__first, __last);
4656 template<
typename _RandomAccessIterator>
4658 partial_sort(_RandomAccessIterator __first,
4659 _RandomAccessIterator __middle,
4660 _RandomAccessIterator __last)
4663 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4664 _RandomAccessIterator>)
4665 __glibcxx_function_requires(_LessThanComparableConcept<
4666 typename iterator_traits<_RandomAccessIterator>::value_type>)
4667 __glibcxx_requires_valid_range(__first, __middle);
4668 __glibcxx_requires_valid_range(__middle, __last);
4669 __glibcxx_requires_irreflexive(__first, __last);
4671 std::__partial_sort(__first, __middle, __last,
4672 __gnu_cxx::__ops::__iter_less_iter());
4694 template<
typename _RandomAccessIterator,
typename _Compare>
4696 partial_sort(_RandomAccessIterator __first,
4697 _RandomAccessIterator __middle,
4698 _RandomAccessIterator __last,
4702 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4703 _RandomAccessIterator>)
4704 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4705 typename iterator_traits<_RandomAccessIterator>::value_type,
4706 typename iterator_traits<_RandomAccessIterator>::value_type>)
4707 __glibcxx_requires_valid_range(__first, __middle);
4708 __glibcxx_requires_valid_range(__middle, __last);
4709 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4711 std::__partial_sort(__first, __middle, __last,
4712 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4730 template<
typename _RandomAccessIterator>
4732 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4733 _RandomAccessIterator __last)
4736 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4737 _RandomAccessIterator>)
4738 __glibcxx_function_requires(_LessThanComparableConcept<
4739 typename iterator_traits<_RandomAccessIterator>::value_type>)
4740 __glibcxx_requires_valid_range(__first, __nth);
4741 __glibcxx_requires_valid_range(__nth, __last);
4742 __glibcxx_requires_irreflexive(__first, __last);
4744 if (__first == __last || __nth == __last)
4747 std::__introselect(__first, __nth, __last,
4749 __gnu_cxx::__ops::__iter_less_iter());
4769 template<
typename _RandomAccessIterator,
typename _Compare>
4771 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4772 _RandomAccessIterator __last, _Compare __comp)
4775 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4776 _RandomAccessIterator>)
4777 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4778 typename iterator_traits<_RandomAccessIterator>::value_type,
4779 typename iterator_traits<_RandomAccessIterator>::value_type>)
4780 __glibcxx_requires_valid_range(__first, __nth);
4781 __glibcxx_requires_valid_range(__nth, __last);
4782 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4784 if (__first == __last || __nth == __last)
4787 std::__introselect(__first, __nth, __last,
4789 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4806 template<
typename _RandomAccessIterator>
4808 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4811 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4812 _RandomAccessIterator>)
4813 __glibcxx_function_requires(_LessThanComparableConcept<
4814 typename iterator_traits<_RandomAccessIterator>::value_type>)
4815 __glibcxx_requires_valid_range(__first, __last);
4816 __glibcxx_requires_irreflexive(__first, __last);
4818 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4836 template<
typename _RandomAccessIterator,
typename _Compare>
4838 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4842 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4843 _RandomAccessIterator>)
4844 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4845 typename iterator_traits<_RandomAccessIterator>::value_type,
4846 typename iterator_traits<_RandomAccessIterator>::value_type>)
4847 __glibcxx_requires_valid_range(__first, __last);
4848 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4850 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4853 template<
typename _InputIterator1,
typename _InputIterator2,
4854 typename _OutputIterator,
typename _Compare>
4856 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4857 _InputIterator2 __first2, _InputIterator2 __last2,
4858 _OutputIterator __result, _Compare __comp)
4860 while (__first1 != __last1 && __first2 != __last2)
4862 if (__comp(__first2, __first1))
4864 *__result = *__first2;
4869 *__result = *__first1;
4874 return std::copy(__first2, __last2,
4875 std::copy(__first1, __last1, __result));
4897 template<
typename _InputIterator1,
typename _InputIterator2,
4898 typename _OutputIterator>
4899 inline _OutputIterator
4900 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4901 _InputIterator2 __first2, _InputIterator2 __last2,
4902 _OutputIterator __result)
4905 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4906 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4907 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4908 typename iterator_traits<_InputIterator1>::value_type>)
4909 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4910 typename iterator_traits<_InputIterator2>::value_type>)
4911 __glibcxx_function_requires(_LessThanOpConcept<
4912 typename iterator_traits<_InputIterator2>::value_type,
4913 typename iterator_traits<_InputIterator1>::value_type>)
4914 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4915 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4916 __glibcxx_requires_irreflexive2(__first1, __last1);
4917 __glibcxx_requires_irreflexive2(__first2, __last2);
4919 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4920 __first2, __last2, __result,
4921 __gnu_cxx::__ops::__iter_less_iter());
4947 template<
typename _InputIterator1,
typename _InputIterator2,
4948 typename _OutputIterator,
typename _Compare>
4949 inline _OutputIterator
4950 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4951 _InputIterator2 __first2, _InputIterator2 __last2,
4952 _OutputIterator __result, _Compare __comp)
4955 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4956 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4957 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4958 typename iterator_traits<_InputIterator1>::value_type>)
4959 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4960 typename iterator_traits<_InputIterator2>::value_type>)
4961 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4962 typename iterator_traits<_InputIterator2>::value_type,
4963 typename iterator_traits<_InputIterator1>::value_type>)
4964 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4965 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4966 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4967 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4969 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4970 __first2, __last2, __result,
4971 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4974 template<
typename _RandomAccessIterator,
typename _Compare>
4976 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4979 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4981 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4984 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4987 if (__buf.begin() == 0)
4990 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4991 _DistanceType(__buf.size()), __comp);
5011 template<
typename _RandomAccessIterator>
5013 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5016 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5017 _RandomAccessIterator>)
5018 __glibcxx_function_requires(_LessThanComparableConcept<
5019 typename iterator_traits<_RandomAccessIterator>::value_type>)
5020 __glibcxx_requires_valid_range(__first, __last);
5021 __glibcxx_requires_irreflexive(__first, __last);
5023 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5024 __gnu_cxx::__ops::__iter_less_iter());
5045 template<
typename _RandomAccessIterator,
typename _Compare>
5047 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5051 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5052 _RandomAccessIterator>)
5053 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5054 typename iterator_traits<_RandomAccessIterator>::value_type,
5055 typename iterator_traits<_RandomAccessIterator>::value_type>)
5056 __glibcxx_requires_valid_range(__first, __last);
5057 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5059 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5060 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5063 template<
typename _InputIterator1,
typename _InputIterator2,
5064 typename _OutputIterator,
5067 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5068 _InputIterator2 __first2, _InputIterator2 __last2,
5069 _OutputIterator __result, _Compare __comp)
5071 while (__first1 != __last1 && __first2 != __last2)
5073 if (__comp(__first1, __first2))
5075 *__result = *__first1;
5078 else if (__comp(__first2, __first1))
5080 *__result = *__first2;
5085 *__result = *__first1;
5091 return std::copy(__first2, __last2,
5092 std::copy(__first1, __last1, __result));
5114 template<
typename _InputIterator1,
typename _InputIterator2,
5115 typename _OutputIterator>
5116 inline _OutputIterator
5117 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5118 _InputIterator2 __first2, _InputIterator2 __last2,
5119 _OutputIterator __result)
5122 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5123 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5124 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5125 typename iterator_traits<_InputIterator1>::value_type>)
5126 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5127 typename iterator_traits<_InputIterator2>::value_type>)
5128 __glibcxx_function_requires(_LessThanOpConcept<
5129 typename iterator_traits<_InputIterator1>::value_type,
5130 typename iterator_traits<_InputIterator2>::value_type>)
5131 __glibcxx_function_requires(_LessThanOpConcept<
5132 typename iterator_traits<_InputIterator2>::value_type,
5133 typename iterator_traits<_InputIterator1>::value_type>)
5134 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5135 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5136 __glibcxx_requires_irreflexive2(__first1, __last1);
5137 __glibcxx_requires_irreflexive2(__first2, __last2);
5139 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5140 __first2, __last2, __result,
5141 __gnu_cxx::__ops::__iter_less_iter());
5164 template<
typename _InputIterator1,
typename _InputIterator2,
5165 typename _OutputIterator,
typename _Compare>
5166 inline _OutputIterator
5167 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5168 _InputIterator2 __first2, _InputIterator2 __last2,
5169 _OutputIterator __result, _Compare __comp)
5172 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5174 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5175 typename iterator_traits<_InputIterator1>::value_type>)
5176 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5177 typename iterator_traits<_InputIterator2>::value_type>)
5178 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5179 typename iterator_traits<_InputIterator1>::value_type,
5180 typename iterator_traits<_InputIterator2>::value_type>)
5181 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5182 typename iterator_traits<_InputIterator2>::value_type,
5183 typename iterator_traits<_InputIterator1>::value_type>)
5184 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5185 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5186 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5187 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5189 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5190 __first2, __last2, __result,
5191 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5194 template<
typename _InputIterator1,
typename _InputIterator2,
5195 typename _OutputIterator,
5198 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5199 _InputIterator2 __first2, _InputIterator2 __last2,
5200 _OutputIterator __result, _Compare __comp)
5202 while (__first1 != __last1 && __first2 != __last2)
5203 if (__comp(__first1, __first2))
5205 else if (__comp(__first2, __first1))
5209 *__result = *__first1;
5235 template<
typename _InputIterator1,
typename _InputIterator2,
5236 typename _OutputIterator>
5237 inline _OutputIterator
5238 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5239 _InputIterator2 __first2, _InputIterator2 __last2,
5240 _OutputIterator __result)
5243 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5244 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5245 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5246 typename iterator_traits<_InputIterator1>::value_type>)
5247 __glibcxx_function_requires(_LessThanOpConcept<
5248 typename iterator_traits<_InputIterator1>::value_type,
5249 typename iterator_traits<_InputIterator2>::value_type>)
5250 __glibcxx_function_requires(_LessThanOpConcept<
5251 typename iterator_traits<_InputIterator2>::value_type,
5252 typename iterator_traits<_InputIterator1>::value_type>)
5253 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5254 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5255 __glibcxx_requires_irreflexive2(__first1, __last1);
5256 __glibcxx_requires_irreflexive2(__first2, __last2);
5258 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5259 __first2, __last2, __result,
5260 __gnu_cxx::__ops::__iter_less_iter());
5284 template<
typename _InputIterator1,
typename _InputIterator2,
5285 typename _OutputIterator,
typename _Compare>
5286 inline _OutputIterator
5287 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5288 _InputIterator2 __first2, _InputIterator2 __last2,
5289 _OutputIterator __result, _Compare __comp)
5292 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5293 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5294 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5295 typename iterator_traits<_InputIterator1>::value_type>)
5296 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5297 typename iterator_traits<_InputIterator1>::value_type,
5298 typename iterator_traits<_InputIterator2>::value_type>)
5299 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5300 typename iterator_traits<_InputIterator2>::value_type,
5301 typename iterator_traits<_InputIterator1>::value_type>)
5302 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5303 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5304 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5305 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5307 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5308 __first2, __last2, __result,
5309 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5312 template<
typename _InputIterator1,
typename _InputIterator2,
5313 typename _OutputIterator,
5316 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5317 _InputIterator2 __first2, _InputIterator2 __last2,
5318 _OutputIterator __result, _Compare __comp)
5320 while (__first1 != __last1 && __first2 != __last2)
5321 if (__comp(__first1, __first2))
5323 *__result = *__first1;
5327 else if (__comp(__first2, __first1))
5334 return std::copy(__first1, __last1, __result);
5357 template<
typename _InputIterator1,
typename _InputIterator2,
5358 typename _OutputIterator>
5359 inline _OutputIterator
5360 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5361 _InputIterator2 __first2, _InputIterator2 __last2,
5362 _OutputIterator __result)
5365 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5366 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5367 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5368 typename iterator_traits<_InputIterator1>::value_type>)
5369 __glibcxx_function_requires(_LessThanOpConcept<
5370 typename iterator_traits<_InputIterator1>::value_type,
5371 typename iterator_traits<_InputIterator2>::value_type>)
5372 __glibcxx_function_requires(_LessThanOpConcept<
5373 typename iterator_traits<_InputIterator2>::value_type,
5374 typename iterator_traits<_InputIterator1>::value_type>)
5375 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5376 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5377 __glibcxx_requires_irreflexive2(__first1, __last1);
5378 __glibcxx_requires_irreflexive2(__first2, __last2);
5380 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5381 __first2, __last2, __result,
5382 __gnu_cxx::__ops::__iter_less_iter());
5408 template<
typename _InputIterator1,
typename _InputIterator2,
5409 typename _OutputIterator,
typename _Compare>
5410 inline _OutputIterator
5411 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5412 _InputIterator2 __first2, _InputIterator2 __last2,
5413 _OutputIterator __result, _Compare __comp)
5416 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5417 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5418 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5419 typename iterator_traits<_InputIterator1>::value_type>)
5420 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5421 typename iterator_traits<_InputIterator1>::value_type,
5422 typename iterator_traits<_InputIterator2>::value_type>)
5423 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5424 typename iterator_traits<_InputIterator2>::value_type,
5425 typename iterator_traits<_InputIterator1>::value_type>)
5426 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5427 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5428 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5429 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5431 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5432 __first2, __last2, __result,
5433 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5436 template<
typename _InputIterator1,
typename _InputIterator2,
5437 typename _OutputIterator,
5440 __set_symmetric_difference(_InputIterator1 __first1,
5441 _InputIterator1 __last1,
5442 _InputIterator2 __first2,
5443 _InputIterator2 __last2,
5444 _OutputIterator __result,
5447 while (__first1 != __last1 && __first2 != __last2)
5448 if (__comp(__first1, __first2))
5450 *__result = *__first1;
5454 else if (__comp(__first2, __first1))
5456 *__result = *__first2;
5465 return std::copy(__first2, __last2,
5466 std::copy(__first1, __last1, __result));
5487 template<
typename _InputIterator1,
typename _InputIterator2,
5488 typename _OutputIterator>
5489 inline _OutputIterator
5490 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5491 _InputIterator2 __first2, _InputIterator2 __last2,
5492 _OutputIterator __result)
5495 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5496 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5497 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5498 typename iterator_traits<_InputIterator1>::value_type>)
5499 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5500 typename iterator_traits<_InputIterator2>::value_type>)
5501 __glibcxx_function_requires(_LessThanOpConcept<
5502 typename iterator_traits<_InputIterator1>::value_type,
5503 typename iterator_traits<_InputIterator2>::value_type>)
5504 __glibcxx_function_requires(_LessThanOpConcept<
5505 typename iterator_traits<_InputIterator2>::value_type,
5506 typename iterator_traits<_InputIterator1>::value_type>)
5507 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5508 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5509 __glibcxx_requires_irreflexive2(__first1, __last1);
5510 __glibcxx_requires_irreflexive2(__first2, __last2);
5512 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5513 __first2, __last2, __result,
5514 __gnu_cxx::__ops::__iter_less_iter());
5538 template<
typename _InputIterator1,
typename _InputIterator2,
5539 typename _OutputIterator,
typename _Compare>
5540 inline _OutputIterator
5541 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5542 _InputIterator2 __first2, _InputIterator2 __last2,
5543 _OutputIterator __result,
5547 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5548 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5549 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5550 typename iterator_traits<_InputIterator1>::value_type>)
5551 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5552 typename iterator_traits<_InputIterator2>::value_type>)
5553 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5554 typename iterator_traits<_InputIterator1>::value_type,
5555 typename iterator_traits<_InputIterator2>::value_type>)
5556 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5557 typename iterator_traits<_InputIterator2>::value_type,
5558 typename iterator_traits<_InputIterator1>::value_type>)
5559 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5560 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5561 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5562 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5564 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5565 __first2, __last2, __result,
5566 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5569 template<
typename _ForwardIterator,
typename _Compare>
5570 _GLIBCXX14_CONSTEXPR
5572 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5575 if (__first == __last)
5577 _ForwardIterator __result = __first;
5578 while (++__first != __last)
5579 if (__comp(__first, __result))
5591 template<
typename _ForwardIterator>
5592 _GLIBCXX14_CONSTEXPR
5594 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5597 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5598 __glibcxx_function_requires(_LessThanComparableConcept<
5599 typename iterator_traits<_ForwardIterator>::value_type>)
5600 __glibcxx_requires_valid_range(__first, __last);
5601 __glibcxx_requires_irreflexive(__first, __last);
5603 return _GLIBCXX_STD_A::__min_element(__first, __last,
5604 __gnu_cxx::__ops::__iter_less_iter());
5616 template<
typename _ForwardIterator,
typename _Compare>
5617 _GLIBCXX14_CONSTEXPR
5618 inline _ForwardIterator
5619 min_element(_ForwardIterator __first, _ForwardIterator __last,
5623 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5624 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5625 typename iterator_traits<_ForwardIterator>::value_type,
5626 typename iterator_traits<_ForwardIterator>::value_type>)
5627 __glibcxx_requires_valid_range(__first, __last);
5628 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5630 return _GLIBCXX_STD_A::__min_element(__first, __last,
5631 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5634 template<
typename _ForwardIterator,
typename _Compare>
5635 _GLIBCXX14_CONSTEXPR
5637 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5640 if (__first == __last)
return __first;
5641 _ForwardIterator __result = __first;
5642 while (++__first != __last)
5643 if (__comp(__result, __first))
5655 template<
typename _ForwardIterator>
5656 _GLIBCXX14_CONSTEXPR
5657 inline _ForwardIterator
5658 max_element(_ForwardIterator __first, _ForwardIterator __last)
5661 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5662 __glibcxx_function_requires(_LessThanComparableConcept<
5663 typename iterator_traits<_ForwardIterator>::value_type>)
5664 __glibcxx_requires_valid_range(__first, __last);
5665 __glibcxx_requires_irreflexive(__first, __last);
5667 return _GLIBCXX_STD_A::__max_element(__first, __last,
5668 __gnu_cxx::__ops::__iter_less_iter());
5680 template<
typename _ForwardIterator,
typename _Compare>
5681 _GLIBCXX14_CONSTEXPR
5682 inline _ForwardIterator
5683 max_element(_ForwardIterator __first, _ForwardIterator __last,
5687 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5688 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5689 typename iterator_traits<_ForwardIterator>::value_type,
5690 typename iterator_traits<_ForwardIterator>::value_type>)
5691 __glibcxx_requires_valid_range(__first, __last);
5692 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5694 return _GLIBCXX_STD_A::__max_element(__first, __last,
5695 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5698 #if __cplusplus >= 201402L 5700 template<
typename _InputIterator,
typename _RandomAccessIterator,
5701 typename _Size,
typename _UniformRandomBitGenerator>
5702 _RandomAccessIterator
5705 _Size __n, _UniformRandomBitGenerator&& __g)
5708 using __param_type =
typename __distrib_type::param_type;
5709 __distrib_type __d{};
5710 _Size __sample_sz = 0;
5711 while (__first != __last && __sample_sz != __n)
5713 __out[__sample_sz++] = *__first;
5716 for (
auto __pop_sz = __sample_sz; __first != __last;
5717 ++__first, (void) ++__pop_sz)
5719 const auto __k = __d(__g, __param_type{0, __pop_sz});
5721 __out[__k] = *__first;
5723 return __out + __sample_sz;
5727 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5728 typename _Size,
typename _UniformRandomBitGenerator>
5730 __sample(_ForwardIterator __first, _ForwardIterator __last,
5732 _OutputIterator __out, _Cat,
5733 _Size __n, _UniformRandomBitGenerator&& __g)
5736 using __param_type =
typename __distrib_type::param_type;
5741 __distrib_type __d{};
5743 __n =
std::min(__n, __unsampled_sz);
5748 const __uc_type __urngrange = __g.max() - __g.min();
5749 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5753 while (__n != 0 && __unsampled_sz >= 2)
5759 if (__p.
first < __n)
5761 *__out++ = *__first;
5767 if (__n == 0)
break;
5772 *__out++ = *__first;
5782 for (; __n != 0; ++__first)
5783 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5785 *__out++ = *__first;
5791 #if __cplusplus > 201402L 5792 #define __cpp_lib_sample 201603 5794 template<
typename _PopulationIterator,
typename _SampleIterator,
5795 typename _Distance,
typename _UniformRandomBitGenerator>
5797 sample(_PopulationIterator __first, _PopulationIterator __last,
5798 _SampleIterator __out, _Distance __n,
5799 _UniformRandomBitGenerator&& __g)
5801 using __pop_cat =
typename 5802 std::iterator_traits<_PopulationIterator>::iterator_category;
5803 using __samp_cat =
typename 5804 std::iterator_traits<_SampleIterator>::iterator_category;
5807 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5808 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5809 "output range must use a RandomAccessIterator when input range" 5810 " does not meet the ForwardIterator requirements");
5812 static_assert(is_integral<_Distance>::value,
5813 "sample size must be an integer type");
5815 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5817 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5818 std::forward<_UniformRandomBitGenerator>(__g));
5823 _GLIBCXX_END_NAMESPACE_ALGO
5824 _GLIBCXX_END_NAMESPACE_VERSION
_GLIBCXX14_CONSTEXPR _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
Marking output iterators.
_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(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
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.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
ISO C++ entities toplevel namespace is std.
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.
_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...
_OutputIterator __sample(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag, _OutputIterator __out, _Cat, _Size __n, _UniformRandomBitGenerator &&__g)
Selection sampling algorithm.
_GLIBCXX14_CONSTEXPR _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
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.
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.
_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.
_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.
_T2 second
first is a copy of the first object
_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.
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.
_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 __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.
Random-access iterators support a superset of bidirectional iterator operations.
_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.
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
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.
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.
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
_T1 first
second_type is the second bound type
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
Struct holding two objects of arbitrary type.
Bidirectional iterators support a superset of forward iterator operations.
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is false.
Forward iterators support a superset of input iterator operations.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
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.
_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.
_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.
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.